Cours programmation réseau en C++

Sérialisation de bits

Bousk

Après avoir vu comment sérialiser des données, nous allons maintenant passer à l’étape suivante et optimiser cette sérialisation afin de minimiser la bande passante utilisée.

Les données seront désormais manipulées en termes de bits et non d’octets.

Commentez

- Titre : Cours programmation réseau en C++

- Auteur : Bousk

- Parution : 29 octobre 2019

- Mise à jour : 23 octobre 2019

- Public visé :

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2019 Cyrille (Bousk) Bousquet. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- I-A. Sérialisation de bits…

- I-A-1. … mais envoi d’octets

- II. Sérialiser des intervalles de valeurs

- II-A. Compter les bits utiles

- II-B. Interface de sérialisation

- II-B-1. Interface de sérialisation

- II-B-2. Interface de désérialisation

- III. Implémentations de la sérialisation et désérialisation de bits

- III-A. Sérialisation de bits

- III-A-1. Explications

- III-A-1-a. Détail des opérations

- III-A-2. Implémentations

- III-A-3. writeBits(const uint8* buffer, const uint8 buffersize, const uint8 nbBits)

- III-A-3-a. Pré-requis et big-endian

- III-A-3-b. Détail sur les bits

- III-A-3-c. Tassage de bits

- III-A-3-d. Découpage des valeurs

- III-A-3-e. Implémentations

- III-B. Désérialisation de bits

- III-B-1. Détails des opérations

- III-B-2. Implémentations

- III-B-3. readBits(const uint8 nbBits, uint8* const buffer, const uint8 bufferSize)

- III-B-4. Cas du bool

- IV. Tests

- V. Conclusion

I - Introduction

L’objectif de ce chapitre est d’optimiser notre sérialisation afin de minimiser la taille des données à envoyer.

Par exemple, dans le chapitre précédent un booléen était sérialisé sur un octet. Sachant qu’un booléen est finalement défini par un seul bit, ça fait 7 bits inutiles.

Même constat pour une énumération qui ne contient que quelques entrées et n’a certainement pas besoin de 256 valeurs différentes.

Imaginez vouloir envoyer une valeur entière que vous savez être comprise dans l’intervalle [0, 15]. Vous pouvez l’envoyer via un uint8, mais un uint8 a des valeurs dans l’intervalle [0, 255] et est donc déjà bien plus gros que nécessaire pour accueillir une telle valeur.

La valeur 15 tient sur 4 bits (15 = 0b1111), soit la moitié d’un uint8. Il serait donc intéressant de pouvoir transférer cette valeur sur 4 bits uniquement. D’autant plus intéressant si vous avez deux valeurs de ce type à envoyer : les deux valeurs peuvent tenir et être envoyées en un seul uint8 au lieu de deux !

En minimisant les données sérialisées, nous avons donc également la possibilité d’en envoyer plus. Ainsi, la bande passante pour chaque message sera moindre et par conséquent notre débit utile sera plus élevé : pour une même quantité de données transférée, plus d’informations, de variables, de paquets ou de messages seront envoyés.

Ce travail pourrait être réalisé par l’application, mais ici nous voulons rendre ceci transparent pour l’utilisateur. D’autant plus que nous en avons une utilité en interne lorsque nous sérialisons les différents en-têtes du moteur.

Ceci n’est pas seulement utile dans le cadre de transfert UDP. Vous pouvez très bien utiliser ce type de sérialisation pour envoyer vos données via TCP ou tout simplement pour un système de sauvegarde.

Minimiser les données est autant de l’optimisation qu’un point important : ça peut faire la différence entre un message envoyé en plusieurs parties ou non et avoir une incidence directe sur la latence des messages et donc leur utilisation par les autres parties du code comme le gameplay.

I-A - Sérialisation de bits…

À la fin de ce chapitre nous aurons amélioré nos classes de sérialisation et de désérialisation pour pouvoir manipuler des bits plutôt que des octets.

I-A-1 - … mais envoi d’octets

La sérialisation de bits n’est pas une solution parfaite.

Les tampons transférés sont toujours des tampons d’octets. Aussi il convient de tasser ses données, sous peine de perdre quelques bits – ce qui n’est pas toujours possible et généralement un moindre mal.

Si vous sérialisez un unique booléen, bien qu’il tienne sur un bit, s’il est seul alors un octet entier sera envoyé pour le contenir. Vous pouvez donc remplir votre message de sept autres booléens, ou d’entiers qui tiennent sur autant de bits.

Tout comme chaque envoi de données entraîne l’utilisation d’un en-tête, il faut peser chaque donnée afin que l’envoi soit intéressant (envoyer un simple booléen, voire rien du tout, est par exemple le pire cas possible - mais malheureusement parfois nécessaire).

II - Sérialiser des intervalles de valeurs

Commençons par ajouter la possibilité de sérialiser une valeur comprise dans un intervalle.

L’idée est de déterminer combien de bits sont nécessaires en fonction de cet intervalle, afin de ne sérialiser que ces bits.

II-A - Compter les bits utiles

Le nombre de bits utiles sera le nombre de bits nécessaire pour couvrir une valeur :

- Pour représenter la valeur 1, il faut 1 bit. 1 en binaire s’écrit 0b1.

- Pour représenter la valeur 2, il faut 2 bits. 2 en binaire s’écrit 0b10.

- Pour représenter la valeur 3, il faut 2 bits. 3 en binaire s’écrit 0b11.

- Pour représenter la valeur 4, il faut 3 bits. 4 en binaire s’écrit 0b100

- Etc.

Pour compter le nombre de bits, il suffit de réaliser des divisions entières successives jusqu’à ce que la valeur soit nulle :

Utils.cpp

1. namespace Bousk

2. {

3. namespace Utils

4. {

5. uint8 CountNeededBits(uint64 v)

6. {

7. assert(v != 0);

8. uint8 bits = 0;

9. while (v)

10. {

11. ++bits;

12. v /= 2;

13. }

14. return bits;

15. }

16. }

17. }

Si vous utilisez C++14 ou supérieur vous pouvez marquer cette fonction constexpr.

Seule une implémentation pour un entier non signé sur 64 bits est nécessaire : cette fonction sera utilisée pour compter le nombre de bits nécessaire pour un intervalle (et donc une valeur non signée). Et les types de plus petite taille seront promus en uint64 par le compilateur.

Vous pouvez aussi retrouver une implémentation utilisant le décalage de bits vers la droite. Bien que cette opération soit l’équivalente d’une division par 2 sur les systèmes les plus courants, on n’est jamais à l’abri d’un comportement inattendu ou spécifique sur un CPU donné, donc autant limiter le risque en écrivant directement la division par 2. Le compilateur fera le travail d’optimisation nécessaire.

II-B - Interface de sérialisation

Nous devons maintenant ajouter les méthodes correspondantes à nos classes de sérialisation et désérialisation.

II-B-1 - Interface de sérialisation

Commençons par améliorer l’interface de notre classe Serializer :

Serializer.hpp

1. bool write(uint8 data, uint8 minValue, uint8 maxValue);

2. bool write(uint16 data, uint16 minValue, uint16 maxValue);

3. bool write(uint32 data, uint32 minValue, uint32 maxValue);

5. bool write(int8 data, int8 minValue, int8 maxValue);

6. bool write(int16 data, int16 minValue, int16 maxValue);

7. bool write(int32 data, int32 minValue, int32 maxValue);

La bonne nouvelle est que nous pouvons factoriser les méthodes déjà existantes afin de limiter le nombre d’implémentations :

Serializer.hpp

1. inline bool write(uint8 data) { return write(data, std::numeric_limits<uint8>::min(), std::numeric_limits<uint8>::max()); }

2. inline bool write(uint16 data) { return write(data, std::numeric_limits<uint16>::min(), std::numeric_limits<uint16>::max()); }

3. inline bool write(uint32 data) { return write(data, std::numeric_limits<uint32>::min(), std::numeric_limits<uint32>::max()); }

5. inline bool write(int8 data) { return write(data, std::numeric_limits<int8>::min(), std::numeric_limits<int8>::max()); }

6. inline bool write(int16 data) { return write(data, std::numeric_limits<int16>::min(), std::numeric_limits<int16>::max()); }

7. inline bool write(int32 data) { return write(data, std::numeric_limits<int32>::min(), std::numeric_limits<int32>::max()); }

De la même manière, la sérialisation d’un booléen peut être factorisée avec cette nouvelle interface :

Serializer.hpp

inline bool write(bool data) { return write(data ? BoolTrue : BoolFalse, static_cast<uint8>(0), static_cast<uint8>(1)); }

Et la fonction writeBytes disparaît pour laisser place à

Serializer.hpp

bool writeBits(const uint8* buffer, const uint8 buffersize, const uint8 nbBits);

II-B-2 - Interface de désérialisation

De la même manière, les méthodes correspondantes à la désérialisation seront ajoutées à la classe Deserializer :

Deserializer.hpp

1. bool read(uint8& data, uint8 minValue, uint8 maxValue);

2. bool read(uint16& data, uint16 minValue, uint16 maxValue);

3. bool read(uint32& data, uint32 minValue, uint32 maxValue);

4. inline bool read(uint8& data) { return read(data, std::numeric_limits<uint8>::min(), std::numeric_limits<uint8>::max()); }

5. inline bool read(uint16& data) { return read(data, std::numeric_limits<uint16>::min(), std::numeric_limits<uint16>::max()); }

6. inline bool read(uint32& data) { return read(data, std::numeric_limits<uint32>::min(), std::numeric_limits<uint32>::max()); }

8. bool read(int8& data, int8 minValue, int8 maxValue);

9. bool read(int16& data, int16 minValue, int16 maxValue);

10. bool read(int32& data, int32 minValue, int32 maxValue);

11. inline bool read(int8& data) { return read(data, std::numeric_limits<int8>::min(), std::numeric_limits<int8>::max()); }

12. inline bool read(int16& data) { return read(data, std::numeric_limits<int16>::min(), std::numeric_limits<int16>::max()); }

13. inline bool read(int32& data) { return read(data, std::numeric_limits<int32>::min(), std::numeric_limits<int32>::max()); }

Notez que la lecture d’un booléen ne peut pas se factoriser ici.

De même, readBytes disparaît en faveur de

Deserializer.hpp

bool readBits(uint8 nbBits, uint8* buffer, uint8 bufferSize);

III - Implémentations de la sérialisation et désérialisation de bits

Maintenant que nous avons défini la nouvelle interface, voyons comment implémenter ces méthodes, et comment réussir à minimiser les données transférées grâce à elles.

III-A - Sérialisation de bits

Commençons par le plus haut niveau et les fonctions write pour chaque type entier.

III-A-1 - Explications

Le chiffre 2 en binaire s’écrit 0b10. Mais ceci est vrai parce qu’il est admis que nous commençons à compter de 0 : 0b00 représente 0, 0b01 représente 1 et enfin 0b10 représente 2.

Mais rien ne nous oblige à suivre cette règle. Et si nous décidions de commencer à compter non pas de 0 mais de 1 ?

Alors 0b0 représente 1, et maintenant 2 est représenté par 0b1. Dans ce cas, envoyer 2 ne nécessite plus que 1 bit.

Nous sommes maîtres de notre protocole et de ce fait toutes les règles sont intégrées dans l’exécutable que nous distribuons et sont donc connues de chaque client.

Ainsi si nous voulons commencer à compter non pas de 0 mais de 1, nous pouvons nous le permettre.

C’est ceci qui rend notre sérialisation binaire et son optimisation possible : nous contrôlons comment nous manipulons nos données.

III-A-1-a - Détail des opérations

Chaque méthode suit la même signature : write(valeur, borne inférieure, borne supérieure).

Il est absolument primordial que la valeur soit comprise dans l’intervalle, bornes incluses.

À partir des bornes, nous pouvons calculer N la différence entre la borne supérieure et inférieure.

Puis, l’astuce consiste à soustraire la borne inférieure à notre valeur, afin de ramener notre valeur sur [0, N].

Ainsi, sérialiser 3 sur [0, 15] nécessitera 4 bits, les 4 bits nécessaires à sérialiser 15 (15 = 0b1111).

Mais sérialiser 3 sur [1, 4], revient donc à sérialiser 2 sur [0, 3] et ne nécessitera que 2 bits (3 = 0b11).

De sorte à voir le gain plus nettement : sérialiser une valeur X sur un intervalle [65 520, 65 535], revient à sérialiser X – 65 520 sur [0, 15] et ne nécessite donc que 4 bits ! Au lieu des 16 nécessaires pour accueillir X dans sa valeur initiale.

Je vous ai présenté ici les deux extrêmes, mais vous comprenez l’idée : ce n’est plus la valeur qui définit la taille des données, mais son intervalle de valeurs possibles.

Ainsi nous arrivons à la généralisation suivante : sérialiser X sur [A, B] revient à sérialiser X–A sur [0, B–A] et les bits nécessaires sont ceux utiles à représenter B-A.

III-A-2 - Implémentations

Avec les explications du paragraphe précédent, nous parvenons à cette implémentation pour les entiers signés :

Serializer.cpp

1. bool Serializer::write(const int8 data, const int8 minValue, const int8 maxValue)

2. {

3. static_assert(sizeof(int8) == sizeof(uint8), "");

4. assert(minValue < maxValue);

5. assert(minValue <= data && data <= maxValue);

6. const uint8 rangedData = static_cast<uint8>(data - minValue);

7. const uint8 range = static_cast<uint8>(maxValue - minValue);

8. return write(rangedData, static_cast<uint8>(0), range);

9. }

10. bool Serializer::write(const int16 data, const int16 minValue, const int16 maxValue)

11. {

12. static_assert(sizeof(int16) == sizeof(uint16), "");

13. assert(minValue < maxValue);

14. assert(minValue <= data && data <= maxValue);

15. const uint16 rangedData = static_cast<uint16>(data - minValue);

16. const uint16 range = static_cast<uint16>(maxValue - minValue);

17. return write(rangedData, static_cast<uint16>(0), range);

18. }

19. bool Serializer::write(const int32 data, const int32 minValue, const int32 maxValue)

20. {

21. static_assert(sizeof(int32) == sizeof(uint32), "");

22. assert(minValue < maxValue);

23. assert(minValue <= data && data <= maxValue);

24. const uint32 rangedData = static_cast<uint32>(data - minValue);

25. const uint32 range = static_cast<uint32>(maxValue - minValue);

26. return write(rangedData, static_cast<uint32>(0), range);

27. }

Semblable à ce que nous avons dans le chapitre précédent, avec factorisation pour utiliser les implémentations non signées.

Les implémentations non signées sont similaires :

Serializer.cpp

1. bool Serializer::write(const uint8 data, const uint8 minValue, const uint8 maxValue)

2. {

3. assert(minValue < maxValue);

4. assert(minValue <= data && data <= maxValue);

5. const uint8 rangedData = data - minValue;

6. const uint8 range = maxValue - minValue;

7. return writeBits(&rangedData, 1, Utils::CountNeededBits(range));

8. }

9. bool Serializer::write(const uint16 data, const uint16 minValue, const uint16 maxValue)

10. {

11. assert(minValue < maxValue);

12. assert(minValue <= data && data <= maxValue);

13. const uint16 rangedData = data - minValue;

14. const uint16 range = maxValue - minValue;

15. uint16 conv;

16. Conversion::ToNetwork(rangedData, conv);

17. return writeBits(reinterpret_cast<const uint8*>(&conv), 2, Utils::CountNeededBits(range));

18. }

19. bool Serializer::write(const uint32 data, const uint32 minValue, const uint32 maxValue)

20. {

21. assert(minValue < maxValue);

22. assert(minValue <= data && data <= maxValue);

23. const uint32 rangedData = data - minValue;

24. const uint32 range = maxValue - minValue;

25. uint32 conv;

26. Conversion::ToNetwork(rangedData, conv);

27. return writeBits(reinterpret_cast<const uint8*>(&conv), 4, Utils::CountNeededBits(range));

28. }

Dans les deux cas, entiers signés ou non, les opérations sont identiques : calcul de l’intervalle puis calcul de la valeur ramenée sur l’intervalle via soustraction de la valeur de la borne inférieure.

Enfin, dans le cas d’un entier signé, on fait appel à l’implémentation non signée, sinon nous convertissons les données en network-endian puis appelons notre fonction writeBits en lui indiquant la taille des données et combien de bits elle doit en extraire et écrire.

Certains remarqueront que les différentes implémentations de write peuvent se factoriser avec une fonction template.

Je ne souhaite pas proposer une interface template ici parce qu’il arrive trop souvent (en fait quasi systématiquement) que celle-ci soit détournée et spécialisée pour pouvoir sérialiser tout et n’importe quoi.

Seules les interfaces pour les types supportés sont donc disponibles, quitte à avoir du code semblable. Si vraiment la factorisation via template vous intéresse alors celle-ci devrait être totalement interne et ne surtout pas être disponible dans l’interface publique.

III-A-3 - writeBits(const uint8* buffer, const uint8 buffersize, const uint8 nbBits)

III-A-3-a - Pré-requis et big-endian

Afin de pouvoir être désérialisée correctement, la représentation des nombres doit être fixée et connue de chaque exécutable. Ici nous fournissons le même exécutable et utilisons la représentation Nertwork-Endian définie au chapitre précédent.

Afin de comprendre l’implémentation de writeBits, il faut une compréhension correcte de la représentation big-endian des variables, des octets qui composent nos données sous cette représentation et des bits qui composent chaque octet.

De par leur représentation big-endian, nous savons qu’ils sont ordonnés de l’octet de poids le plus fort, vers celui de poids le plus faible. Nous devons donc lire les octets de droite à gauche puisque ce sont les octets de poids le plus faible qui contiennent les premières informations.

III-A-3-b - Détail sur les bits

Chaque octet est représenté de bits qui sont également ordonnés du poids le plus fort vers le plus faible. Donc les bits qui nous intéressent dans ces octets sont situés à droite.

Nous supposerons que les octets sont composés de 8 bits. Si la plateforme utilise une taille différente (ce qui existe) le code devra être adapté. Ces plateformes ne sont pas notre cible principale.

Par exemple, prenons un uint32 valant 23. Sa représentation hexadécimale en big-endian est 0x00000017. Il sera composé des 4 octets suivants :

Adresse

0

1

2

3

Valeur de l’octet

0x00

0x00

0x00

0x17

Valeurs des bits

0b00000000

0b00000000

0b00000000

0b00010111

Et vous retrouvez notre affirmation initiale : l’octet intéressant se trouve à droite et les bits intéressants sont situés également à droite dans cet octet.

III-A-3-c - Tassage de bits

La sérialisation binaire devra donc tasser les bits utiles dans des octets.

Ainsi, les données seront tassées à gauche à l’intérieur de chaque octet. Si nous voulons écrire 15 sur 4 bits dans un octet vide, nous n’écrirons pas 0b00010111, mais 0b10111000. Puis après l’écriture d’un true il vaudra 0b10111100.

Ce choix est arbitraire, vous pouvez préférer tasser les données sur la droite.

III-A-3-d - Découpage des valeurs

Continuons sur notre exemple précédent qui possède 1 octet valant 0b10111100.

Ajoutons 9 sur [0, 15] qui s’écrit sur 4 bits 0b1001. Notre octet ne possède plus que 2 bits libres, il va donc falloir découper notre nouvelle valeur.

Nous ajouterons les deux premiers bits (qui sont les deux les plus à droite) sur l’octet existant afin de le compléter, puis créerons un nouvel octet pour accueillir les deux bits restants.

Après ces opérations, nous aurons 2 octets valant respectivement 0b10111101 et 0b10000000.

III-A-3-e - Implémentations

Passons à l’implémentation de ces principes. Il s’agira essentiellement de décalages d’octets et de bits.

Puisque nous travaillons sur les bits, il faut avoir un suivi de ceux utilisés dans le dernier octet. Nous ajoutons donc une variable membre uint8 mUsedBits à cette fin qui sera initialisée à 0.

Serializer.cpp

1. bool Serializer::writeBits(const uint8* const buffer, const uint8 buffersize, const uint8 nbBits)

2. {

3. static_assert(CHAR_BIT == 8, "");

4. uint8 totalWrittenBits = 0;

5. // buffer est en network/big endian, donc les octets doivent être lus de droite (buffer + buffersize - 1) à gauche (buffer)

6. for (uint8 readingBytesOffset = 1; readingBytesOffset <= buffersize && totalWrittenBits < nbBits; ++readingBytesOffset)

7. {

8. const uint8 srcByte = *(buffer + buffersize - readingBytesOffset);

9. const uint8 bitsToWrite = std::min(8, nbBits - totalWrittenBits);

10. uint8 writtenBits = 0;

11. if (mUsedBits)

12. {

13. // Il existe un octet auquel tasser les données

14. const uint8 remainingBitsInCurrentByte = 8 - mUsedBits;

15. const uint8 nbBitsToPack = std::min(bitsToWrite, remainingBitsInCurrentByte);

16. // Extraction des bits à partir de droite

17. const uint8 rightBitsToPack = srcByte & Utils::CreateRightBitsMask(nbBitsToPack);

18. // Alignement de ces bits à gauche pour les tasser à l’octet existant

19. const uint8 bitsShiftToAlignLeft = remainingBitsInCurrentByte - nbBitsToPack;

20. const uint8 leftAlignedBits = rightBitsToPack << bitsShiftToAlignLeft;

21. mBuffer.back() |= leftAlignedBits;

22. writtenBits += nbBitsToPack;

23. }

24. const uint8 remainingBits = bitsToWrite - writtenBits;

25. if (remainingBits)

26. {

27. // Extraction des bits à écrire

28. const uint8 leftBitsToPack = srcByte & Utils::CreateBitsMask(remainingBits, writtenBits);

29. // Alignement de ces bits à gauche sur le nouvel octet

30. const uint8 bitsShiftToAlignLeft = 8 - writtenBits - remainingBits;

31. const uint8 leftAlignedBits = leftBitsToPack << bitsShiftToAlignLeft;

32. // Ajout du nouvel octet au tampon

33. mBuffer.push_back(leftAlignedBits);

34. writtenBits += remainingBits;

35. }

36. // Mise à jour des compteurs

37. totalWrittenBits += writtenBits;

38. mUsedBits += writtenBits;

39. mUsedBits %= 8;

40. }

41. return totalWrittenBits == nbBits;

42. }

Avec l’ajout de quelques fonctions utilitaires :

Utils.hpp

uint8 CreateRightBitsMask(uint8 rightBits);
uint8 CreateBitsMask(uint8 nbBits, uint8 rightBitsToSkip);

Implémentées ainsi :

Utils.cpp

1. uint8 CreateRightBitsMask(uint8 rightBits)

2. {

3. assert(rightBits >= 1 && rightBits <= 8);

4. switch (rightBits)

5. {

6. case 1: return 0b00000001;

7. case 2: return 0b00000011;

8. case 3: return 0b00000111;

9. case 4: return 0b00001111;

10. case 5: return 0b00011111;

11. case 6: return 0b00111111;

12. case 7: return 0b01111111;

13. case 8: return 0b11111111;

14. }

15. return 0;

16. }

17. uint8 CreateBitsMask(uint8 nbBits, uint8 rightBitsToSkip)

18. {

19. assert(rightBitsToSkip < 8);

20. assert(rightBitsToSkip + nbBits <= 8);

21. return CreateRightBitsMask(nbBits) << rightBitsToSkip;

22. }

III-B - Désérialisation de bits

Maintenant que nous savons sérialiser nos données, passons à leur désérialisation.

III-B-1 - Détails des opérations

Il s’agira bien sûr de faire les opérations inverses de la sérialisation pour retrouver les données d’origine.

Puisque les données sont tassées sur la gauche par le sérialiseur, nous devons donc lire les bits de gauche à droite sur chaque octet.

Puis, après lecture des bits nécessaires, il faudra ajouter la valeur minimale afin de retrouver la valeur de départ sur l’intervalle de départ.

III-B-2 - Implémentations

Tout comme pour la sérialisation, la désérialisation de valeurs signées utilisera les implémentations de valeurs non signées.

Deserializer.cpp

1. bool Deserializer::read(int8& data, const int8 minValue, const int8 maxValue)

2. {

3. static_assert(sizeof(int8) == sizeof(uint8), "");

4. assert(minValue < maxValue);

5. const uint8 range = static_cast<uint8>(maxValue - minValue);

6. if (read(reinterpret_cast<uint8&>(data), 0, range))

7. {

8. data += minValue;

9. return true;

10. }

11. return false;

12. }

13. bool Deserializer::read(int16& data, const int16 minValue, const int16 maxValue)

14. {

15. static_assert(sizeof(int16) == sizeof(uint16), "");

16. assert(minValue < maxValue);

17. const uint16 range = static_cast<uint16>(maxValue - minValue);

18. if (read(reinterpret_cast<uint16&>(data), 0, range))

19. {

20. data += minValue;

21. return true;

22. }

23. return false;

24. }

25. bool Deserializer::read(int32& data, const int32 minValue, const int32 maxValue)

26. {

27. static_assert(sizeof(int32) == sizeof(uint32), "");

28. assert(minValue < maxValue);

29. const uint32 range = static_cast<uint32>(maxValue - minValue);

30. if (read(reinterpret_cast<uint32&>(data), 0, range))

31. {

32. data += minValue;

33. return true;

34. }

35. return false;

36. }

Avec les implémentations non signées suivantes :

Deserializer.cpp

1. bool Deserializer::read(uint8& data, const uint8 minValue, const uint8 maxValue)

2. {

3. assert(minValue < maxValue);

4. const uint8 range = maxValue - minValue;

5. uint8 bytesRead = 0;

6. if (readBits(Utils::CountNeededBits(range), &bytesRead, 1))

7. {

8. data = bytesRead;

9. if (data <= range)

10. {

11. data += minValue;

12. return true;

13. }

14. }

15. return false;

16. }

17. bool Deserializer::read(uint16& data, const uint16 minValue, const uint16 maxValue)

18. {

19. assert(minValue < maxValue);

20. const uint16 range = maxValue - minValue;

21. uint8 bytesRead[2]{ 0 };

22. if (readBits(Utils::CountNeededBits(range), bytesRead, 2))

23. {

24. Conversion::ToLocal(bytesRead, data);

25. if (data <= range)

26. {

27. data += minValue;

28. return true;

29. }

30. }

31. return false;

32. }

33. bool Deserializer::read(uint32& data, const uint32 minValue, const uint32 maxValue)

34. {

35. assert(minValue < maxValue);

36. const uint32 range = maxValue - minValue;

37. uint8 bytesRead[4]{ 0 };

38. if (readBits(Utils::CountNeededBits(range), bytesRead, 4))

39. {

40. Conversion::ToLocal(bytesRead, data);

41. if (data <= range)

42. {

43. data += minValue;

44. return true;

45. }

46. }

47. return false;

48. }

Il est critique d’initialiser les tampons avec des valeurs nulles. La lecture ne fait qu’extraire et écraser les bits nécessaires dans ceux-ci.

III-B-3 - readBits(const uint8 nbBits, uint8* const buffer, const uint8 bufferSize)

Voilà la fonction principale de lecture des données. Elle permet d’extraire un certain nombre de bits vers un tampon d’octets.

En sortie de cette fonction, en cas de succès, le tampon représente les données en network-endian. C’est la fonction appelante qui doit réordonner ce tampon vers l’endianness locale – ce que vous pouvez constater dans les implémentations des paragraphes précédents.

Deserializer.cpp

1. bool Deserializer::readBits(const uint8 nbBits, uint8* const buffer, const uint8 bufferSize)

2. {

3. static_assert(CHAR_BIT == 8, "");

4. assert(nbBits <= bufferSize * 8);

5. if (remainingBits() < nbBits)

6. return false;

8. uint8 totalReadBits = 0;

9. for (uint8 writingBytesOffset = 1; writingBytesOffset <= bufferSize && totalReadBits < nbBits; ++writingBytesOffset)

10. {

11. // buffer doit être en network/big endian, donc les octets doivent être écrits de droite (buffer + bufferSize - 1) à gauche (buffer)

12. uint8& dstByte = *(buffer + bufferSize - writingBytesOffset);

13. const uint8 bitsToRead = std::min(8, nbBits - totalReadBits);

14. uint8 bitsRead = 0;

15. {

16. const uint8 srcByte = *(mBuffer + mBytesRead);

17. // Lecture des premiers bits depuis l’octet en cours de lecture

18. const uint8 remainingBitsInCurrentByte = 8 - mBitsRead;

19. const uint8 leftBitsToSkip = mBitsRead;

20. const uint8 bitsToReadFromCurrentByte = std::min(bitsToRead, remainingBitsInCurrentByte);

21. const uint8 remainingBitsOnTheRight = 8 - bitsToReadFromCurrentByte - leftBitsToSkip;

22. // Extraction des bits les plus à gauche

23. const uint8 readMask = Utils::CreateBitsMask(bitsToReadFromCurrentByte, remainingBitsOnTheRight);

24. const uint8 bits = srcByte & readMask;

25. // Alignement de ces bits à droite dans l’octet final

26. const uint8 bitsAlignedRight = bits >> remainingBitsOnTheRight;

27. dstByte |= bitsAlignedRight;

29. bitsRead += bitsToReadFromCurrentByte;

30. mBitsRead += bitsToReadFromCurrentByte;

31. mBytesRead += mBitsRead / 8;

32. mBitsRead %= 8;

33. }

35. if (bitsRead < bitsToRead)

36. {

37. const uint8 srcByte = *(mBuffer + mBytesRead);

38. // Lecture des bits manquants pour former l’octet final depuis l’octet suivant du tampon

39. const uint8 bitsToReadFromCurrentByte = bitsToRead - bitsRead;

40. const uint8 remainingBitsOnTheRight = 8 - bitsToReadFromCurrentByte;

41. // Les bits à lire sont alignés sur la gauche

42. const uint8 readMask = Utils::CreateBitsMask(bitsToReadFromCurrentByte, remainingBitsOnTheRight);

43. const uint8 bits = srcByte & readMask;

44. // Aligner les bits sur la droite pour les tasser à gauche de la première partie lue

45. const uint8 bitsAlignedRightToPack = bits >> (8 - bitsToReadFromCurrentByte - bitsRead);

46. dstByte |= bitsAlignedRightToPack;

48. bitsRead += bitsToReadFromCurrentByte;

49. mBitsRead += bitsToReadFromCurrentByte;

50. mBytesRead += mBitsRead / 8;

51. mBitsRead %= 8;

52. }

54. // Mise à jour des compteurs

55. totalReadBits += bitsRead;

56. }

58. return totalReadBits == nbBits;

59. }

III-B-4 - Cas du bool

La désérialisation d’un booléen sera la lecture d’un bit qui définira la valeur du booléen.

Pour cette raison et la nécessité d’une variable intermédiaire, nous ne pouvons pas la factoriser comme pour l’implémentation de la sérialisation.

Deserializer.cpp

1. bool Deserializer::read(bool& data)

2. {

3. uint8 byteRead;

4. if (read(byteRead, 0, 1))

5. {

6. data = (byteRead == BoolTrue);

7. return true;

8. }

9. return false;

10. }

Ici, nous lisons une valeur uint8 sur l’intervalle [0, 1], qui lira donc un seul bit. Puis nous utilisons le fait que les données sont alignées à droite après lecture pour pouvoir comparer à notre constante BoolTrue qui vaut 0b00000001.

IV - Tests

Finissons avec l’écriture de quelques tests supplémentaires afin de vérifier que nos nouvelles implémentations fonctionnent comme attendu :

Types_Test.cpp

1. void Serialization_Test::TestBits()

2. {

3. {

4. Bousk::Serialization::Serializer serializer;

6. #define WRITE_AS(TYPE, VALUE, RANGE_MIN, RANGE_MAX) serializer.write(static_cast<TYPE>(VALUE), static_cast<TYPE>(RANGE_MIN), static_cast<TYPE>(RANGE_MAX))

7. // Écriture d’un octet entier

8. CHECK(WRITE_AS(Bousk::uint8, 5, 0, 255));

9. CHECK(serializer.bufferSize() == 1);

10. CHECK(serializer.mUsedBits == 0);

11. CHECK(serializer.mBuffer[0] == 0b00000101);

12. // Écriture de 4 bits

13. CHECK(WRITE_AS(Bousk::int8, 3, -7, 8)); // 3 sur [-7, 8] => 10 sur [0, 15] => 1010

14. CHECK(serializer.bufferSize() == 2);

15. CHECK(serializer.mUsedBits == 4);

16. CHECK(serializer.mBuffer[0] == 0b00000101);

17. CHECK(serializer.mBuffer[1] == 0b10100000);

18. // Écriture de 5 bits

19. CHECK(WRITE_AS(Bousk::uint8, 18, 0, 31)); // => 1 0010

20. CHECK(serializer.bufferSize() == 3);

21. CHECK(serializer.mUsedBits == 1);

22. CHECK(serializer.mBuffer[0] == 0b00000101);

23. CHECK(serializer.mBuffer[1] == 0b10100010);

24. CHECK(serializer.mBuffer[2] == 0b10000000);

25. // Écriture de 2 booléens

26. CHECK(serializer.write(true));

27. CHECK(serializer.bufferSize() == 3);

28. CHECK(serializer.mUsedBits == 2);

29. CHECK(serializer.mBuffer[0] == 0b00000101);

30. CHECK(serializer.mBuffer[1] == 0b10100010);

31. CHECK(serializer.mBuffer[2] == 0b11000000);

32. CHECK(serializer.write(false));

33. CHECK(serializer.bufferSize() == 3);

34. CHECK(serializer.mUsedBits == 3);

35. CHECK(serializer.mBuffer[0] == 0b00000101);

36. CHECK(serializer.mBuffer[1] == 0b10100010);

37. CHECK(serializer.mBuffer[2] == 0b11000000);

38. // Tassage d’une valeur sur 13 bits

39. CHECK(WRITE_AS(Bousk::int16, 3578, -4000, 4000)); // 7578 [0, 8000] => 11101 100 11010

40. CHECK(serializer.bufferSize() == 4);

41. CHECK(serializer.mUsedBits == 0);

42. CHECK(serializer.mBuffer[0] == 0b00000101);

43. CHECK(serializer.mBuffer[1] == 0b10100010);

44. CHECK(serializer.mBuffer[2] == 0b11011010);

45. CHECK(serializer.mBuffer[3] == 0b10011101);

46. // Écriture d’une valeur uint32 sur 9 bits

47. CHECK(WRITE_AS(Bousk::uint32, 123, 0, 256));

48. CHECK(serializer.bufferSize() == 6);

49. CHECK(serializer.mUsedBits == 1);

50. CHECK(serializer.mBuffer[0] == 0b00000101);

51. CHECK(serializer.mBuffer[1] == 0b10100010);

52. CHECK(serializer.mBuffer[2] == 0b11011010);

53. CHECK(serializer.mBuffer[3] == 0b10011101);

54. CHECK(serializer.mBuffer[4] == 0b01111011);

55. CHECK(serializer.mBuffer[5] == 0b00000000);

56. #undef WRITE_AS

58. Bousk::Serialization::Deserializer deserializer(serializer.buffer(), serializer.bufferSize());

59. #define READ_AND_CHECK(TYPE, EXPECTED_VALUE, RANGE_MIN, RANGE_MAX)                                        \

60. do {                                                                                            \

61. TYPE data;                                                                                    \

62. CHECK(deserializer.read(data, static_cast<TYPE>(RANGE_MIN), static_cast<TYPE>(RANGE_MAX)));    \

63. CHECK(data == static_cast<TYPE>(EXPECTED_VALUE));                                \

64. } while(0)

65. #define READ_AND_CHECK_BOOL(EXPECTED_VALUE)    \

66. do {                                \

67. bool data;                        \

68. CHECK(deserializer.read(data));    \

69. CHECK(data == EXPECTED_VALUE);    \

70. } while(0)

71. // Octet entier

72. READ_AND_CHECK(Bousk::uint8, 5, 0, 255);

73. CHECK(deserializer.bufferReadBits() == 8);

74. // 4 bits

75. READ_AND_CHECK(Bousk::int8, 3, -7, 8);

76. CHECK(deserializer.mBytesRead == 1);

77. CHECK(deserializer.mBitsRead == 4);

78. CHECK(deserializer.bufferReadBits() == 12);

79. // 5 bits

80. READ_AND_CHECK(Bousk::uint8, 18, 0, 31);

81. CHECK(deserializer.mBytesRead == 2);

82. CHECK(deserializer.mBitsRead == 1);

83. CHECK(deserializer.bufferReadBits() == 17);

84. // Lecture de 2 booléens

85. READ_AND_CHECK_BOOL(true);

86. CHECK(deserializer.mBytesRead == 2);

87. CHECK(deserializer.mBitsRead == 2);

88. CHECK(deserializer.bufferReadBits() == 18);

89. READ_AND_CHECK_BOOL(false);

90. CHECK(deserializer.mBytesRead == 2);

91. CHECK(deserializer.mBitsRead == 3);

92. CHECK(deserializer.bufferReadBits() == 19);

93. // Valeur sur 13 bits

94. READ_AND_CHECK(Bousk::int16, 3578, -4000, 4000);

95. CHECK(deserializer.mBytesRead == 4);

96. CHECK(deserializer.mBitsRead == 0);

97. CHECK(deserializer.bufferReadBits() == 32);

98. // 9 bits uint32

99. READ_AND_CHECK(Bousk::int32, 123, 0, 256);

100. CHECK(deserializer.mBytesRead == 5);

101. CHECK(deserializer.mBitsRead == 1);

102. CHECK(deserializer.bufferReadBits() == 41);

103. #undef READ_AND_CHECK

104. #undef READ_AND_CHECK_BOOL

105. }

106. }

V - Conclusion

La sérialisation binaire permet une compression des données sans perte d’information. Mais ce n’est pas une solution magique : il faut expliquer à votre équipe comment l’utiliser correctement afin d’en voir le bénéfice, que chacun prenne le temps de définir l’intervalle de valeurs probant pour chaque donnée au lieu d’envoyer des uint16, int32, etc. entièrement.

Le gain direct est la possibilité d’envoyer plus de données pour une bande-passante équivalente. Ce qui permet de transférer plus d’informations entre les machines dans un même temps donné. Ou une utilisation moindre de la bande-passante pour une quantité de données identique. Votre réplication sera donc améliorée et plus rapide.

En conséquence de cette réplication plus rapide, vous pourrez également constater dans certains cas une meilleure latence ou une meilleure réactivité de votre gameplay : ce qui nécessitait auparavant trois messages et autant de datagrammes peut maintenant être fait en un seul, économisant alors deux RTT.

Certains messages, généralement ceux contenant le plus de données pouvant bénéficier d’un intervalle (points de vie …), auront une compression plus importante.

Gardez toutefois à l’esprit que ceci a un coût : le traitement fait sur les données, si nombre d’entre elles nécessitent d’être découpées sur plusieurs octets, consomme du CPU. Cette surconsommation est souvent minime, mais non négligeable dans certains cas(1). Essayez donc d’aligner vos données autant que possible pour limiter ces coupes.

Le code source est désormais disponible sur Github.

Article précédent

<< Bases de la sérialisation

Sérialisation avancée >>

(1) Anecdote : au cours de ma carrière, suite à l’implémentation de ce système dans notre moteur réseau, un programmeur gameplay vient me voir avec un bug « j’ai une chute de FPS qui empire au fil du temps » et impossible de le reproduire sur ma machine. En profilant sur son poste, nous constatons que writeBits pouvait prendre plusieurs millisecondes dans le cas d’envoi d’un tampon de uint8 qu’il envoyait en utilisant l’interface de vector et qui faisait un découpage de chaque entrée parce que les données précédant le vector n’étaient pas alignées. Ce découpage des données entraînant donc un surcoût CPU, non négligeable dans son cas. L’exact même exécutable, quand lancé sur ma machine, affichait une exécution de quelques nanosecondes et aucun problème pour les mêmes données. La différence venait de nos CPU respectifs : tous deux des i7, mais le sien était d’une ou une demie génération plus ancienne (i.e. i7-920 vs i7-960). Nous avons appelé ça avec mon lead « le seul cas où "ça marche sur ma machine" est accepté comme correct ».