Les VarInts

Si vous êtes ammené à utiliser ou étudier le protocole Protobuf de Google, vous y découvrirez un élément particulièrement intéressant, les VarInts.

Ce format de stockage peut être intéressant à mettre en oeuvre. Il est simple et présente des avantages en terme de volumétrie.
Imaginons que les valeurs suivantes pour un même champs et leur équivalent binaire:

• 50 : 0110010
• 322 : 00000001 11000010
• 70000 : 00000001 00010001 01110000

On constate que pour un même champs, les valeurs prennent des tailles différentes.
Si l'on souhaite stocker jusquà la valeur 70000, il faut alors 24 bits.

Admettons que majoritairement, les valeurs du champs soient des nombres entre 0 et 65535, soit entre 1 et 2 octets, avec quelques valeurs sur 3 octets.
Il est dommage de perdre des octets au niveau place, surtout si comme pour une trame réseau, cela devenir gênant au niveau volume.

L'idée des VarInts est la même que UTF-8.
Le bit de poid fort (le 8ème bit) va indiqué s'il le nombre est stocké aussi sur l'octet suivant. Exemple :
Pour la valeur 50, la valeur binaire est 0 110010. L'octet de poid fort est à zéro, donc, le chiffre est stocké sur 1 octet.
Pour la valeur 322, soit 0000000101000010 en binaire, nous alons découper la valeur binaire en 7 bits :

0000000101000010
----------------
00
0000010
1000010

Une fois cette opération fait, est ajouter 1 ou 0 suivant si il y a une suite. Dans l'exemple, cela donne :

00
00000010
11000010

Ce qui donne une valeur fausse de 706.
Le traitement est identique la valeur 70000.

Il n'est pas possible de stocker les valeurs comme ça sur un disque, car il n'est pas possible en l'état de traiter correctement les valeurs.
Il est nécesaire d'inverser l'ordre des octets. Ainsi, sur disque sera écrit la valeur 11000010 puis la valeur 00000010.
De ce fait, une lecture séquentielle est possible. Voici l'algorithme :

Lire le premier octet.
Si bit de poids fort est 1
  Mettre bit de poid fort à 0
  Lecture deuxième octet
  Initialiser un nombre 16 bits à 0
  Mettre le deuxième octets dedans et décaler 7 bits vers la gauche
  Faire un ou logique avec le premier octet modifié
Fin Si

Le traitement des nombres signés est identique.
L'inconvénient majeur qui apparait, c'est le temps de traitement, plus coûteux qu'une simple lecture.
Deuxième inconvénient, c'est que le nombre 255, au lieu d'être enrigistré sur 1 octet, le sera sur 2.
La mise en place des VarInts est donc un choix à étudier précisément suivant les cas.