Cours programmation réseau en C++

Sérialisation de bits

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.

33 commentaires Donner une note  l'article (5) 

Article lu   fois.

L'auteur

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

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
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
namespace Bousk
{
	namespace Utils
	{
		uint8 CountNeededBits(uint64 v)
		{
			assert(v != 0);
			uint8 bits = 0;
			while (v)
			{
				++bits;
				v /= 2;
			}
			return bits;
		}
	}
}

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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
bool write(uint8 data, uint8 minValue, uint8 maxValue);
bool write(uint16 data, uint16 minValue, uint16 maxValue);
bool write(uint32 data, uint32 minValue, uint32 maxValue);
			
bool write(int8 data, int8 minValue, int8 maxValue);
bool write(int16 data, int16 minValue, int16 maxValue);
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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
inline bool write(uint8 data) { return write(data, std::numeric_limits<uint8>::min(), std::numeric_limits<uint8>::max()); }
inline bool write(uint16 data) { return write(data, std::numeric_limits<uint16>::min(), std::numeric_limits<uint16>::max()); }
inline bool write(uint32 data) { return write(data, std::numeric_limits<uint32>::min(), std::numeric_limits<uint32>::max()); }
			
inline bool write(int8 data) { return write(data, std::numeric_limits<int8>::min(), std::numeric_limits<int8>::max()); }
inline bool write(int16 data) { return write(data, std::numeric_limits<int16>::min(), std::numeric_limits<int16>::max()); }
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
Sélectionnez
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
Sélectionnez
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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
bool read(uint8& data, uint8 minValue, uint8 maxValue);
bool read(uint16& data, uint16 minValue, uint16 maxValue);
bool read(uint32& data, uint32 minValue, uint32 maxValue);
inline bool read(uint8& data) { return read(data, std::numeric_limits<uint8>::min(), std::numeric_limits<uint8>::max()); }
inline bool read(uint16& data) { return read(data, std::numeric_limits<uint16>::min(), std::numeric_limits<uint16>::max()); }
inline bool read(uint32& data) { return read(data, std::numeric_limits<uint32>::min(), std::numeric_limits<uint32>::max()); }

bool read(int8& data, int8 minValue, int8 maxValue);
bool read(int16& data, int16 minValue, int16 maxValue);
bool read(int32& data, int32 minValue, int32 maxValue);
inline bool read(int8& data) { return read(data, std::numeric_limits<int8>::min(), std::numeric_limits<int8>::max()); }
inline bool read(int16& data) { return read(data, std::numeric_limits<int16>::min(), std::numeric_limits<int16>::max()); }
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
Sélectionnez
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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
bool Serializer::write(const int8 data, const int8 minValue, const int8 maxValue)
{
	static_assert(sizeof(int8) == sizeof(uint8), "");
	assert(minValue < maxValue);
	assert(minValue <= data && data <= maxValue);
	const uint8 rangedData = static_cast<uint8>(data - minValue);
	const uint8 range = static_cast<uint8>(maxValue - minValue);
	return write(rangedData, static_cast<uint8>(0), range);
}
bool Serializer::write(const int16 data, const int16 minValue, const int16 maxValue)
{
	static_assert(sizeof(int16) == sizeof(uint16), "");
	assert(minValue < maxValue);
	assert(minValue <= data && data <= maxValue);
	const uint16 rangedData = static_cast<uint16>(data - minValue);
	const uint16 range = static_cast<uint16>(maxValue - minValue);
	return write(rangedData, static_cast<uint16>(0), range);
}
bool Serializer::write(const int32 data, const int32 minValue, const int32 maxValue)
{
	static_assert(sizeof(int32) == sizeof(uint32), "");
	assert(minValue < maxValue);
	assert(minValue <= data && data <= maxValue);
	const uint32 rangedData = static_cast<uint32>(data - minValue);
	const uint32 range = static_cast<uint32>(maxValue - minValue);
	return write(rangedData, static_cast<uint32>(0), range);
}

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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
bool Serializer::write(const uint8 data, const uint8 minValue, const uint8 maxValue)
{
	assert(minValue < maxValue);
	assert(minValue <= data && data <= maxValue);
	const uint8 rangedData = data - minValue;
	const uint8 range = maxValue - minValue;
	return writeBits(&rangedData, 1, Utils::CountNeededBits(range));
}
bool Serializer::write(const uint16 data, const uint16 minValue, const uint16 maxValue)
{
	assert(minValue < maxValue);
	assert(minValue <= data && data <= maxValue);
	const uint16 rangedData = data - minValue;
	const uint16 range = maxValue - minValue;
	uint16 conv;
	Conversion::ToNetwork(rangedData, conv);
	return writeBits(reinterpret_cast<const uint8*>(&conv), 2, Utils::CountNeededBits(range));
}
bool Serializer::write(const uint32 data, const uint32 minValue, const uint32 maxValue)
{
	assert(minValue < maxValue);
	assert(minValue <= data && data <= maxValue);
	const uint32 rangedData = data - minValue;
	const uint32 range = maxValue - minValue;
	uint32 conv;
	Conversion::ToNetwork(rangedData, conv);
	return writeBits(reinterpret_cast<const uint8*>(&conv), 4, Utils::CountNeededBits(range));
}

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 0b 10 01 . 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 0b101111 01 et 0b 10 000000.

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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
bool Serializer::writeBits(const uint8* const buffer, const uint8 buffersize, const uint8 nbBits)
{
	static_assert(CHAR_BIT == 8, "");
	uint8 totalWrittenBits = 0;
	// buffer est en network/big endian, donc les octets doivent être lus de droite (buffer + buffersize - 1) à gauche (buffer)
	for (uint8 readingBytesOffset = 1; readingBytesOffset <= buffersize && totalWrittenBits < nbBits; ++readingBytesOffset)
	{
		const uint8 srcByte = *(buffer + buffersize - readingBytesOffset);
		const uint8 bitsToWrite = std::min(8, nbBits - totalWrittenBits);
		uint8 writtenBits = 0;
		if (mUsedBits)
		{
			// Il existe un octet auquel tasser les données
			const uint8 remainingBitsInCurrentByte = 8 - mUsedBits;
			const uint8 nbBitsToPack = std::min(bitsToWrite, remainingBitsInCurrentByte);
			// Extraction des bits à partir de droite
			const uint8 rightBitsToPack = srcByte & Utils::CreateRightBitsMask(nbBitsToPack);
			// Alignement de ces bits à gauche pour les tasser à l’octet existant
			const uint8 bitsShiftToAlignLeft = remainingBitsInCurrentByte - nbBitsToPack;
			const uint8 leftAlignedBits = rightBitsToPack << bitsShiftToAlignLeft;
			mBuffer.back() |= leftAlignedBits;
			writtenBits += nbBitsToPack;
		}
		const uint8 remainingBits = bitsToWrite - writtenBits;
		if (remainingBits)
		{
			// Extraction des bits à écrire
			const uint8 leftBitsToPack = srcByte & Utils::CreateBitsMask(remainingBits, writtenBits);
			// Alignement de ces bits à gauche sur le nouvel octet
			const uint8 bitsShiftToAlignLeft = 8 - writtenBits - remainingBits;
			const uint8 leftAlignedBits = leftBitsToPack << bitsShiftToAlignLeft;
			// Ajout du nouvel octet au tampon
			mBuffer.push_back(leftAlignedBits);
			writtenBits += remainingBits;
		}
		// Mise à jour des compteurs
		totalWrittenBits += writtenBits;
		mUsedBits += writtenBits;
		mUsedBits %= 8;
	}
	return totalWrittenBits == nbBits;
}

Avec l’ajout de quelques fonctions utilitaires :

Utils.hpp
Cacher/Afficher le codeSélectionnez

Implémentées ainsi :

Utils.cpp
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
uint8 CreateRightBitsMask(uint8 rightBits)
{
	assert(rightBits >= 1 && rightBits <= 8);
	switch (rightBits)
	{
	case 1: return 0b00000001;
	case 2: return 0b00000011;
	case 3: return 0b00000111;
	case 4: return 0b00001111;
	case 5: return 0b00011111;
	case 6: return 0b00111111;
	case 7: return 0b01111111;
	case 8: return 0b11111111;
	}
	return 0;
}
uint8 CreateBitsMask(uint8 nbBits, uint8 rightBitsToSkip)
{
	assert(rightBitsToSkip < 8);
	assert(rightBitsToSkip + nbBits <= 8);
	return CreateRightBitsMask(nbBits) << rightBitsToSkip;
}

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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
bool Deserializer::read(int8& data, const int8 minValue, const int8 maxValue)
{
	static_assert(sizeof(int8) == sizeof(uint8), "");
	assert(minValue < maxValue);
	const uint8 range = static_cast<uint8>(maxValue - minValue);
	if (read(reinterpret_cast<uint8&>(data), 0, range))
	{
		data += minValue;
		return true;
	}
	return false;
}
bool Deserializer::read(int16& data, const int16 minValue, const int16 maxValue)
{
	static_assert(sizeof(int16) == sizeof(uint16), "");
	assert(minValue < maxValue);
	const uint16 range = static_cast<uint16>(maxValue - minValue);
	if (read(reinterpret_cast<uint16&>(data), 0, range))
	{
		data += minValue;
		return true;
	}
	return false;
}
bool Deserializer::read(int32& data, const int32 minValue, const int32 maxValue)
{
	static_assert(sizeof(int32) == sizeof(uint32), "");
	assert(minValue < maxValue);
	const uint32 range = static_cast<uint32>(maxValue - minValue);
	if (read(reinterpret_cast<uint32&>(data), 0, range))
	{
		data += minValue;
		return true;
	}
	return false;
}

Avec les implémentations non signées suivantes :

Deserializer.cpp
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
bool Deserializer::read(uint8& data, const uint8 minValue, const uint8 maxValue)
{
	assert(minValue < maxValue);
	const uint8 range = maxValue - minValue;
	uint8 bytesRead = 0;
	if (readBits(Utils::CountNeededBits(range), &bytesRead, 1))
	{
		data = bytesRead;
		if (data <= range)
		{
			data += minValue;
			return true;
		}
	}
	return false;
}
bool Deserializer::read(uint16& data, const uint16 minValue, const uint16 maxValue)
{
	assert(minValue < maxValue);
	const uint16 range = maxValue - minValue;
	uint8 bytesRead[2]{ 0 };
	if (readBits(Utils::CountNeededBits(range), bytesRead, 2))
	{
		Conversion::ToLocal(bytesRead, data);
		if (data <= range)
		{
			data += minValue;
			return true;
		}
	}
	return false;
}
bool Deserializer::read(uint32& data, const uint32 minValue, const uint32 maxValue)
{
	assert(minValue < maxValue);
	const uint32 range = maxValue - minValue;
	uint8 bytesRead[4]{ 0 };
	if (readBits(Utils::CountNeededBits(range), bytesRead, 4))
	{
		Conversion::ToLocal(bytesRead, data);
		if (data <= range)
		{
			data += minValue;
			return true;
		}
	}
	return false;
}

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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
bool Deserializer::readBits(const uint8 nbBits, uint8* const buffer, const uint8 bufferSize)
{
	static_assert(CHAR_BIT == 8, "");
	assert(nbBits <= bufferSize * 8);
	if (remainingBits() < nbBits)
		return false;

	uint8 totalReadBits = 0;
	for (uint8 writingBytesOffset = 1; writingBytesOffset <= bufferSize && totalReadBits < nbBits; ++writingBytesOffset)
	{
		// buffer doit être en network/big endian, donc les octets doivent être écrits de droite (buffer + bufferSize - 1) à gauche (buffer)
		uint8& dstByte = *(buffer + bufferSize - writingBytesOffset);
		const uint8 bitsToRead = std::min(8, nbBits - totalReadBits);
		uint8 bitsRead = 0;
		{
			const uint8 srcByte = *(mBuffer + mBytesRead);
			// Lecture des premiers bits depuis l’octet en cours de lecture
			const uint8 remainingBitsInCurrentByte = 8 - mBitsRead;
			const uint8 leftBitsToSkip = mBitsRead;
			const uint8 bitsToReadFromCurrentByte = std::min(bitsToRead, remainingBitsInCurrentByte);
			const uint8 remainingBitsOnTheRight = 8 - bitsToReadFromCurrentByte - leftBitsToSkip;
			// Extraction des bits les plus à gauche
			const uint8 readMask = Utils::CreateBitsMask(bitsToReadFromCurrentByte, remainingBitsOnTheRight);
			const uint8 bits = srcByte & readMask;
			// Alignement de ces bits à droite dans l’octet final
			const uint8 bitsAlignedRight = bits >> remainingBitsOnTheRight;
			dstByte |= bitsAlignedRight;

			bitsRead += bitsToReadFromCurrentByte;
			mBitsRead += bitsToReadFromCurrentByte;
			mBytesRead += mBitsRead / 8;
			mBitsRead %= 8;
		}

		if (bitsRead < bitsToRead)
		{
			const uint8 srcByte = *(mBuffer + mBytesRead);
			// Lecture des bits manquants pour former l’octet final depuis l’octet suivant du tampon
			const uint8 bitsToReadFromCurrentByte = bitsToRead - bitsRead;
			const uint8 remainingBitsOnTheRight = 8 - bitsToReadFromCurrentByte;
			// Les bits à lire sont alignés sur la gauche
			const uint8 readMask = Utils::CreateBitsMask(bitsToReadFromCurrentByte, remainingBitsOnTheRight);
			const uint8 bits = srcByte & readMask;
			// Aligner les bits sur la droite pour les tasser à gauche de la première partie lue
			const uint8 bitsAlignedRightToPack = bits >> (8 - bitsToReadFromCurrentByte - bitsRead);
			dstByte |= bitsAlignedRightToPack;

			bitsRead += bitsToReadFromCurrentByte;
			mBitsRead += bitsToReadFromCurrentByte;
			mBytesRead += mBitsRead / 8;
			mBitsRead %= 8;
		}

		// Mise à jour des compteurs
		totalReadBits += bitsRead;
	}

	return totalReadBits == nbBits;
}

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
Cacher/Afficher le codeSélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
bool Deserializer::read(bool& data)
{
	uint8 byteRead;
	if (read(byteRead, 0, 1))
	{
		data = (byteRead == BoolTrue);
		return true;
	}
	return false;
}

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
Cacher/Afficher le codeSélectionnez

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

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   


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 ».

  

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 ni 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.