I. Introduction▲
Bonjour, je suis Glenn Fiedler et bienvenue sur le deuxième article de Construire un protocole de jeu en réseau .
Dans l'article précédent nous avons discuté des différentes manières de lire et écrire des paquets dans les jeux multijoueurs. Nous avons rapidement mis de côté l'envoi de l'état du jeu via des formats textes comme XML ou JSON parce qu'ils sont vraiment inefficaces et nous avons décidé d'écrire notre propre protocole binaire. Nous avons implémenté un bitpacker pour ne pas avoir à perdre jusque 7 bits pour un booléen, résoudre les problèmes d'endianness, écrire un mot entier au lieu d'octets et faire en sorte qu'il soit aussi simple et rapide que possible sans astuce spécifique à une plateforme.
Après ce premier article, il restait à résoudre les problèmes suivants :
- Nous avons besoin de vérifier si les valeurs entières sont hors de l'intervalle de valeurs attendu et interrompre la lecture du paquet parce que des personnes malveillantes peuvent envoyer un paquet qui essayera de corrompre la mémoire. L'interruption de la lecture du paquet doit être automatique et ne pas utiliser les exceptions parce qu'elles sont vraiment lentes ;
- Séparer les fonctions de lecture et d'écriture est un cauchemar à maintenir si ces fonctions sont écrites manuellement. Nous aimerions écrire le code de sérialisation pour un paquet donné une seule fois, mais ne pas avoir de surcoût à l'exécution (en termes de chemins conditionnels, appels virtuels, etc.).
Comment faire ? Lisez la suite de cet article et je vous montrerai exactement comment j'y parviens en C++. J'ai mis du temps à développer et peaufiner cette technique alors j'espère que vous la trouverez utile et qu'il s'agira au moins d'un bon substitut par rapport à la façon dont vous le faites ou l'avez vu faire dans d'autres moteurs de jeux.
II. Fonction de sérialisation de paquets unifiée▲
Commençons par l'objectif. Voici ce que nous voulons avoir à la fin :
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.
struct PacketA
{
int x,y,z;
template <typename Stream> bool Serialize( Stream & stream )
{
serialize_bits( stream, x, 32 );
serialize_bits( stream, y, 32 );
serialize_bits( stream, z, 32 );
return true;
}
};
struct PacketB
{
int numElements;
int elements[MaxElements];
template <typename Stream> bool Serialize( Stream & stream )
{
serialize_int( stream, numElements, 0, MaxElements );
for ( int i = 0; i < numElements; ++i )
serialize_bits( buffer, elements[i], 32 );
return true;
}
};
struct PacketC
{
bool x;
short y;
int z;
template <typename Stream> bool Serialize( Stream & stream )
{
serialize_int( stream, x, 8 );
serialize_int( stream, y, 16 );
serialize_int( stream, z, 32 );
return true;
}
};
Remarquez qu'il y a une seule fonction de sérialisation par structure de paquet au lieu de fonctions read et write séparées. C'est cool ! La quantité de code de sérialisation est diminuée de moitié et maintenant vous devez déployer de sérieux efforts pour désynchroniser la lecture et l'écriture.
L'astuce pour que ce soit efficace est que la classe stream soit template dans la fonction. Il y a deux types de stream dans mon système : ReadStream et WriteStream. Chaque classe a les mêmes méthodes, mais elles n'ont aucun lien entre elles. Une classe lit les valeurs d'un flux binaire vers les variables, l'autre écrit les valeurs des variables dans un flux binaire. ReadStream et WriteStream sont de simples wrappers aux classes BitReader et BitWriter de l'article précédent.
Il y a bien sûr d'autres voies à cette approche. Si vous n'appréciez pas les templates vous pourriez avoir une interface stream et l'implémenter avec la lecture et l'écriture pour chaque classe de sérialisation. Mais vous avez maintenant une fonction virtuelle appelée pour chaque sérialisation. Un surcoût excessif selon moi.
Une autre option est d'avoir une super-class stream qui peut être configurée pour agir en lecture ou écriture à l'exécution. Ceci peut être plus rapide que la méthode virtuelle, mais vous avez toujours une branche conditionnelle pour chaque sérialisation pour choisir entre lecture ou écriture, ce ne sera donc pas aussi rapide qu'une fonction read et write codée à la main.
Je préfère la méthode du template parce que ça laisse le compilateur faire le travail de génération et optimisation des fonctions read et write pour vous. Vous pouvez aussi coder des fonctions de sérialisation de cette manière et laisser le compilateur optimiser ce qu'il souhaite en spécialisant read et write :
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.
struct RigidBody
{
vec3f position;
quat3f orientation;
vec3f linear_velocity;
vec3f angular_velocity;
template <typename Stream> bool Serialize( Stream & stream )
{
serialize_vector( stream, position );
serialize_quaternion( stream, orientation );
bool at_rest = Stream::IsWriting ? velocity.length() == 0 : 1;
serialize_bool( stream, at_rest );
if ( !at_rest )
{
serialize_vector( stream, linear_velocity );
serialize_vector( stream, angular_velocity );
}
else if ( Stream::IsReading )
{
linear_velocity = vec3f(0,0,0);
angular_velocity = vec3f(0,0,0);
}
return true;
}
};
Alors que ça peut sembler non efficace, ça l'est ! La spécialisation de template de cette fonction optimise toutes les branches conditionnelles selon le type de stream. Pas mal hein ?
III. Vérification des bornes et abandon de lecture▲
Maintenant que vous avez tordu le cou du compilateur pour générer des fonctions read et write optimisées, nous devons automatiser la vérification des erreurs à la lecture pour se protéger contre les paquets malveillants.
La première étape est d'inclure les bornes de l'entier à la fonction de sérialisation au lieu d'utiliser uniquement le nombre de bits. Pensez-y. La fonction de sérialisation peut extrapoler le nombre de bits requis depuis les valeurs minimales et maximales :
serialize_int( stream, numElements, 0, MaxElements );Ceci permet à l'interface de supporter aisément la sérialisation d'entiers signés et la fonction de sérialisation peut vérifier la valeur lue depuis le réseau et s'assurer qu'elle est dans la plage de valeurs attendues. Si la valeur est hors borne, avorter la lecture immédiatement et ignorer le paquet.
Puisque nous ne pouvons pas utiliser les exceptions pour gérer cet abandon (trop lentes), voici comment nous allons faire.
Dans ma configuration serialize_int n'est actuellement pas une fonction, c'est une macro sournoise comme ceci :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#define serialize_int( stream, value, min, max ) \
do \
{ \
assert( min < max ); \
int32_t int32_value; \
if ( Stream::IsWriting ) \
{ \
assert( value >= min ); \
assert( value <= max ); \
int32_value = (int32_t) value; \
} \
if ( !stream.SerializeInteger( int32_value, min, max ) ) \
return false; \
if ( Stream::IsReading ) \
{ \
value = int32_value; \
if ( value < min || value > max ) \
return false; \
} \
} while (0)
Je suis une très mauvaise personne ici parce que j'utilise la macro pour insérer le code de vérification des résultats de SerializeInteger et retourner false en cas d'erreur. Ceci vous donne un comportement similaire à une exception dans le sens où la pile d'exécution revient au début de la fonction de sérialisation en cas d'erreur, mais vous n'avez aucun coût contrairement aux exceptions pour y parvenir. Le branchement pour dérouler est très peu commun (les erreurs de sérialisation sont rares) donc les prédictions de branchements ne devraient poser aucun souci.
Un autre cas qui nécessite l'interruption est si la lecture atteint la fin du tampon. C'est également un branchement plutôt rare, mais ça doit être vérifié pour chaque opération de sérialisation parce que lire après la fin du tampon est un comportement indéterminé. Si nous ne réalisons pas cette vérification, nous pourrions rencontrer des boucles infinies. Tandis qu'il est courant de retourner la valeur 0 quand on lit après la fin d'un flux (d'après l'article précédent), il n'y a aucune garantie que ceci entraîne la fin de la fonction de sérialisation correctement si elle utilise des boucles. Cette vérification du débordement est nécessaire afin d'avoir un comportement bien défini.
Une dernière chose. En sérialisant les données, je n'interromps jamais l'écriture en vérifiant les bornes ou après la fin du flux. Vous pouvez être beaucoup plus souple sur l'écriture puisque si un problème survient c'est quasi garanti d'être de votre faute. Il suffit d'assurer que tout est correct, via assertions, (bornes correctes, fin du flux non atteint) pour chaque sérialisation et vous êtes bon.
IV. Sérialiser flottants et vecteurs▲
Le flux d'octets ne sérialise que des valeurs entières. Comment pouvons-nous sérialiser une valeur flottante ?
Ça a l'air technique, mais ne l'est pas. Un nombre flottant en mémoire est juste une valeur sur 32 bits comme toutes les autres. Votre ordinateur ne sait pas si un mot de 32 bits en mémoire est un entier, un flottant ou une partie de chaîne de caractères. C'est juste une valeur sur 32 bits . Par chance, le langage C++ (contrairement à quelques autres) nous laisse travailler avec cette propriété fondamentale.
Vous pouvez accéder la valeur entière derrière un nombre flottant avec une union :
2.
3.
4.
5.
6.
7.
8.
9.
union FloatInt
{
float float_value;
uint32_t int_value;
};
FloatInt tmp;
tmp.float_value = 10.0f;
printf( "float value as an integer: %x\n", tmp.int_value );
Vous pouvez aussi y parvenir via un uint32_t*, mais d'expérience ça ne passe pas avec GCC -O2, donc je préfère la technique de l'union à la place. Des amis ont aussi fait remarquer (à juste titre) que le seul moyen absolument standard d'avoir le flottant comme entier est de convertir un pointeur vers le flottant en uint8_t* et reconstruire la valeur entière depuis les valeurs des quatre octets accédés individuellement via un pointeur d'octet. Ça semble une manière un peu absurde de le faire selon moi. Mesdames et messieurs… C++ !
En attendant, ces cinq dernières années, je n'ai eu aucun problème avec la technique de l'union. Voici comment je sérialise une valeur flottante non compressée :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
template <typename Stream>
bool serialize_float_internal( Stream & stream,
float & value )
{
union FloatInt
{
float float_value;
uint32_t int_value;
};
FloatInt tmp;
if ( Stream::IsWriting )
tmp.float_value = value;
bool result = stream.SerializeBits( tmp.int_value, 32 );
if ( Stream::IsReading )
value = tmp.float_value;
return result;
}
Encapsulez ceci dans une macro serialize_float pour facilement gérer les erreurs à la lecture :
2.
3.
4.
5.
6.
#define serialize_float( stream, value ) \
do \
{ \
if ( !protocol2::serialize_float_internal( stream, value ) ) \
return false; \
} while (0)
Parfois vous n'avez pas besoin de toute la précision offerte par un type flottant. Comment pouvez-vous compresser une valeur flottante ? La première étape est de borner cette valeur puis de la quantifier afin d'en faire une représentation entière.
Par exemple, si vous savez qu'un flottant est dans les bornes [-10, +10] et qu'une précision suffisante pour cette valeur est 0,01, alors vous pouvez juste multiplier ce nombre par 100 pour l'avoir entre [-1000, +1000] et sérialiser en entier. Du côté de la réception, divisez juste par 100.0 pour retrouver la valeur flottante.
Voici une version généralisée de ce concept :
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.
template <typename Stream>
bool serialize_compressed_float_internal( Stream & stream,
float & value,
float min,
float max,
float res )
{
const float delta = max - min;
const float values = delta / res;
const uint32_t maxIntegerValue = (uint32_t) ceil( values );
const int bits = bits_required( 0, maxIntegerValue );
uint32_t integerValue = 0;
if ( Stream::IsWriting )
{
float normalizedValue =
clamp( ( value - min ) / delta, 0.0f, 1.0f );
integerValue = (uint32_t) floor( normalizedValue *
maxIntegerValue + 0.5f );
}
if ( !stream.SerializeBits( integerValue, bits ) )
return false;
if ( Stream::IsReading )
{
const float normalizedValue =
integerValue / float( maxIntegerValue );
value = normalizedValue * delta + min;
}
return true;
}
Une fois que vous pouvez sérialiser des valeurs flottantes, il est trivial d'ajouter à la sérialisation de vecteurs et quaternions. J'utilise une version modifiée de la superbe bibliothèque vectorial pour les vecteurs mathématiques dans mes projets et j'implémente la sérialisation de ces objets comme ceci :
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.
template <typename Stream>
bool serialize_vector_internal( Stream & stream,
vec3f & vector )
{
float values[3];
if ( Stream::IsWriting )
vector.store( values );
serialize_float( stream, values[0] );
serialize_float( stream, values[1] );
serialize_float( stream, values[2] );
if ( Stream::IsReading )
vector.load( values );
return true;
}
template <typename Stream>
bool serialize_quaternion_internal( Stream & stream,
quat4f & quaternion )
{
float values[4];
if ( Stream::IsWriting )
quaternion.store( values );
serialize_float( stream, values[0] );
serialize_float( stream, values[1] );
serialize_float( stream, values[2] );
serialize_float( stream, values[3] );
if ( Stream::IsReading )
quaternion.load( values );
return true;
}
#define serialize_vector( stream, value ) \
do \
{ \
if ( !serialize_vector_internal( stream, value ) ) \
return false; \
} \
while(0)
#define serialize_quaternion( stream, value ) \
do \
{ \
if ( !serialize_quaternion_internal( stream, value ) ) \
return false; \
} \
while(0)
Si vous savez que les composantes de votre vecteur sont bornées, vous pouvez les compresser comme ceci :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
template <typename Stream>
bool serialize_compressed_vector_internal( Stream & stream,
vec3f & vector,
float min,
float max,
float res )
{
float values[3];
if ( Stream::IsWriting )
vector.store( values );
serialize_compressed_float( stream, values[0], min, max, res );
serialize_compressed_float( stream, values[1], min, max, res );
serialize_compressed_float( stream, values[2], min, max, res );
if ( Stream::IsReading )
vector.load( values );
return true;
}
Si vous voulez compresser une orientation à travers le réseau, ne vous contentez pas de la compresser comme vecteur 8.8.8.8 borné par [-1, +1]. Vous pouvez avoir un bien meilleur résultat si vous utilisez le plus petit représentant du quaternion. Voyez le code exemple de cet article pour une implémentation.
V. Sérialiser chaînes de caractères et tableaux▲
Et si vous voulez sérialiser une chaîne de caractères ?
Est-ce une bonne idée d'envoyer la chaîne avec le caractère nul de fin de chaîne ? Je ne pense pas. Vous cherchez juste les ennuis ! Au lieu de ça, traitez la chaîne comme un tableau d'octets préfixé de sa longueur. Donc, afin d'envoyer une chaîne de caractères via le réseau, nous devons travailler sur comment envoyer un tableau d'octets efficacement.
Première observation : pourquoi se fatiguer à tasser un tableau d'octets dans notre flux juste pour qu'ils soient aléatoirement décalés de [0, 7] bits ? Pourquoi ne pas se contenter d'aligner à l'octet avant d'écrire le tableau, pour que ses données soient parfaitement alignées dans le paquet, afin que chaque octet du tableau corresponde à un octet du paquet. Vous perdez seulement [0,7] bit pour chaque tableau sérialisé, selon l'alignement, mais ce n'est pas un très grave selon moi.
Comment aligner le flux à l'octet ? À partir de l'index du bit actuel dans le flux, calculez le nombre de bits nécessaires pour atteindre l'octet suivant, combien de bits manquent pour que cet index soit divisible par 8, puis insérez ce nombre de bits en remplissage. En bonne pratique, remplissez-les de 0 afin qu'à la lecture vous puissiez vérifier que oui , vous lisez un octet aligné et oui, il est en effet rempli de zéro jusqu'à l'index du prochain octet. Si un bit non nul est lu dans le remplissage, interrompez la lecture et rejetez le paquet.
Voici mon code pour aligner un flux à l'octet suivant :
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.
void BitWriter::WriteAlign()
{
const int remainderBits = m_bitsWritten % 8;
if ( remainderBits != 0 )
{
uint32_t zero = 0;
WriteBits( zero, 8 - remainderBits );
assert( ( m_bitsWritten % 8 ) == 0 );
}
}
bool BitReader::ReadAlign()
{
const int remainderBits = m_bitsRead % 8;
if ( remainderBits != 0 )
{
uint32_t value = ReadBits( 8 - remainderBits );
assert( m_bitsRead % 8 == 0 );
if ( value != 0 )
return false;
}
return true;
}
#define serialize_align( stream ) \
do \
{ \
if ( !stream.SerializeAlign() ) \
return false; \
} while (0)
Nous pouvons maintenant utiliser cette opération d'alignement pour écrire efficacement un tableau d'octets dans notre flux binaire : puisque nous sommes alignés à l'octet, nous pouvons faire la majeure partie du travail via memcpy . La seule astuce est, puisque la lecture et écriture se fait au niveau du mot, qu'il est nécessaire d'avoir du code spécifique pour gérer le début et la fin du tableau, pour s'assurer que tous les bits dans scratch sont écrits en mémoire au début, et que le scratch soit correctement configuré pour les écritures suivantes après la sérialisation de notre tableau.
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.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
void BitWriter::WriteBytes( const uint8_t* data, int bytes )
{
assert( GetAlignBits() == 0 );
assert( m_bitsWritten + bytes * 8 <= m_numBits );
assert( ( m_bitsWritten % 32 ) == 0 ||
( m_bitsWritten % 32 ) == 8 ||
( m_bitsWritten % 32 ) == 16 ||
( m_bitsWritten % 32 ) == 24 );
int headBytes = ( 4 - ( m_bitsWritten % 32 ) / 8 ) % 4;
if ( headBytes > bytes )
headBytes = bytes;
for ( int i = 0; i < headBytes; ++i )
WriteBits( data[i], 8 );
if ( headBytes == bytes )
return;
assert( GetAlignBits() == 0 );
int numWords = ( bytes - headBytes ) / 4;
if ( numWords > 0 )
{
assert( ( m_bitsWritten % 32 ) == 0 );
memcpy( &m_data[m_wordIndex], data+headBytes, numWords*4 );
m_bitsWritten += numWords * 32;
m_wordIndex += numWords;
m_scratch = 0;
}
assert( GetAlignBits() == 0 );
int tailStart = headBytes + numWords * 4;
int tailBytes = bytes - tailStart;
assert( tailBytes >= 0 && tailBytes < 4 );
for ( int i = 0; i < tailBytes; ++i )
WriteBits( data[tailStart+i], 8 );
assert( GetAlignBits() == 0 );
assert( headBytes + numWords * 4 + tailBytes == bytes );
}
void ReadBytes( uint8_t* data, int bytes )
{
assert( GetAlignBits() == 0 );
assert( m_bitsRead + bytes * 8 <= m_numBits );
assert( ( m_bitsRead % 32 ) == 0 ||
( m_bitsRead % 32 ) == 8 ||
( m_bitsRead % 32 ) == 16 ||
( m_bitsRead % 32 ) == 24 );
int headBytes = ( 4 - ( m_bitsRead % 32 ) / 8 ) % 4;
if ( headBytes > bytes )
headBytes = bytes;
for ( int i = 0; i < headBytes; ++i )
data[i] = ReadBits( 8 );
if ( headBytes == bytes )
return;
assert( GetAlignBits() == 0 );
int numWords = ( bytes - headBytes ) / 4;
if ( numWords > 0 )
{
assert( ( m_bitsRead % 32 ) == 0 );
memcpy( data + headBytes, &m_data[m_wordIndex], numWords * 4 );
m_bitsRead += numWords * 32;
m_wordIndex += numWords;
m_scratchBits = 0;
}
assert( GetAlignBits() == 0 );
int tailStart = headBytes + numWords * 4;
int tailBytes = bytes - tailStart;
assert( tailBytes >= 0 && tailBytes < 4 );
for ( int i = 0; i < tailBytes; ++i )
data[tailStart+i] = ReadBits( 8 );
assert( GetAlignBits() == 0 );
assert( headBytes + numWords * 4 + tailBytes == bytes );
}
template <typename Stream>
bool serialize_bytes_internal( Stream & stream,
uint8_t* data,
int bytes )
{
return stream.SerializeBytes( data, bytes );
}
#define serialize_bytes( stream, data, bytes ) \
do \
{ \
if ( !serialize_bytes_internal( stream, data, bytes ) ) \
return false; \
} while (0)
Nous pouvons maintenant sérialiser une chaîne de caractères en sérialisant sa longueur suivie de ses données :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
template <typename Stream>
bool serialize_string_internal( Stream & stream,
char* string,
int buffer_size )
{
uint32_t length;
if ( Stream::IsWriting )
{
length = strlen( string );
assert( length < buffer_size - 1 );
}
serialize_int( stream, length, 0, buffer_size - 1 );
serialize_bytes( stream, (uint8_t*)string, length );
if ( Stream::IsReading )
string[length] = '\0';
}
#define serialize_string( stream, string, buffer_size ) \
do \
{ \
if ( !serialize_string_internal( stream, \
string, buffer_size ) ) \
return false; \
} while (0)
Comme vous pouvez le constater, vous pouvez avoir des sérialisations assez complexes à partir de simples primitives.
VI. Sérialiser une partie de tableau▲
Lors de l'implémentation d'un protocole réseau de jeu, tôt ou tard vous aurez besoin de sérialiser un tableau d'objets. Peut-être que le serveur doit envoyer tous les objets à un client, ou un tableau d'évènements ou de messages. C'est assez simple si vous envoyez tous les objets dans le tableau vers le client, mais qu'en est-il si vous voulez envoyer uniquement un sous-ensemble du tableau ?
La première approche et la plus simple est d'itérer sur l'ensemble des objets du tableau et de sérialiser un booléen par objet pour indiquer si cet objet doit être envoyé ou non. Si ce booléen vaut 1 alors les données de l'objet suivent, sinon il est omis et le booléen pour l'objet suivant suit immédiatement dans le flux.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
template <typename Stream>
bool serialize_scene_a( Stream & stream, Scene & scene )
{
for ( int i = 0; i < MaxObjects; ++i )
{
serialize_bool( stream, scene.objects[i].send );
if ( !scene.objects[i].send )
{
if ( Stream::IsReading )
memset( &scene.objects[i], 0, sizeof( Object ) );
continue;
}
serialize_object( stream, scene.objects[i] );
}
return true;
}
Mais que se passe-t-il si le tableau est très large, disons 4000 objets dans la scène ? 4000/8 = 500. Houla. On a un surcoût de 500 octets, même si vous envoyez uniquement un ou deux objets ! C'est… pas bon. Pouvons-nous changer ça pour avoir un surcoût proportionnel au nombre d'objets à envoyer et non au total d'objets du tableau ?
Maintenant oui, nous avons fait quelque chose d'intéressant. Nous itérons une collection d'objets pour l'écriture (tous les objets du tableau) et une collection différente pour la lecture (sous-ensemble d'objets envoyés). À cet instant le concept de sérialisation unifiée pour la lecture et écriture ne fonctionne pas. Pour de tels cas, il est mieux de séparer la lecture et l'écriture dans des fonctions séparées comme ceci :
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.
bool write_scene_b( protocol2::WriteStream & stream, Scene & scene )
{
int num_objects_sent = 0;
for ( int i = 0; i < MaxObjects; ++i )
{
if ( scene.objects[i].send )
num_objects_sent++;
}
write_int( stream, num_objects_sent, 0, MaxObjects );
for ( int i = 0; i < MaxObjects; ++i )
{
if ( !scene.objects[i].send )
continue;
write_int( stream, i, 0, MaxObjects - 1 );
write_object( stream, scene.objects[i] );
}
return true;
}
bool read_scene_b( protocol2::ReadStream & stream, Scene & scene )
{
memset( &scene, 0, sizeof( scene ) );
int num_objects_sent;
read_int( stream, num_objects_sent, 0, MaxObjects );
for ( int i = 0; i < num_objects_sent; ++i )
{
int index;
read_int( stream, index, 0, MaxObjects - 1 );
read_object( stream, scene.objects[index] );
}
return true;
}
Comme autre solution, vous pourriez générer une structure de données séparées avec le sous-ensemble des objets mis à jour, et implémenter une sérialisation pour ce tableau d'objets mis à jour. Mais devoir générer une
struct
C++ pour chaque structure de données que vous voulez sérialiser est très laborieux. Finalement vous voulez itérer sur plusieurs structures de données en parallèle et effectivement écrire une structure de données dynamique
via le flux binaire. C'est quelque chose de très banal lors de la mise en place de méthodes de sérialisation plus avancées comme le delta encoding
. Dès que vous le faites ainsi, la sérialisation unifiée n'a plus de raison d'être.
Mon conseil est que quand vous voulez le faire, ne vous tracassez pas, séparez juste la lecture et l'écriture. Unifier lecture et écriture ne vaut pas le coup face aux problèmes qui se poseront quand vous générez dynamiquement une structure de données à l'écriture. Ma règle d'or est que la sérialisation compliquée justifie probablement d'avoir à séparer les fonctions de lecture et écriture, mais si possible, essayez de garder les dénominateurs communs unifiés (c'est-à-dire les objets, évènements, quoi que ce soit que vous sérialisiez).
Un dernier point. Le code plus haut itère sur la collection d'objets deux fois lors de l'écriture. Une première fois pour déterminer le nombre d'objets qui ont été modifiés, et une seconde fois pour réellement sérialiser le sous-ensemble des objets modifiés. Pouvons-nous y parvenir en une seule passe ? Absolument ! Vous pouvez utiliser une autre astuce, une valeur sentinelle pour indiquer la fin du tableau, plutôt que de sérialiser le nombre d'objets présents dans le tableau en amont. De cette manière vous pouvez itérer sur le tableau une unique fois lors de l'envoi, et quand il n'y a plus d'objets à envoyer, sérialiser la valeur sentinelle pour indiquer la fin du tableau :
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.
bool write_scene_c( protocol2::WriteStream & stream, Scene & scene )
{
for ( int i = 0; i < MaxObjects; ++i )
{
if ( !scene.objects[i].send )
continue;
write_int( stream, i, 0, MaxObjects );
write_object( stream, scene.objects[i] );
}
write_int( stream, MaxObjects, 0, MaxObjects );
return true;
}
bool read_scene_c( protocol2::ReadStream & stream, Scene & scene )
{
memset( &scene, 0, sizeof( scene ) );
while ( true )
{
int index; read_int( stream, index, 0, MaxObjects );
if ( index == MaxObjects )
break;
read_object( stream, scene.objects[index] );
}
return true;
}
C'est plutôt simple et ça fonctionne très bien si l'ensemble des objets envoyés est un petit pourcentage du total des objets. Mais que se passe-t-il si un grand nombre d'objets sont envoyés, disons la moitié des 4000 objets de la scène. On aura 2000 indices d'objet avec chaque index coûtant 12 bits… ce qui fait 24 000 bits ou 3000 octets (presque 3 ko !) de perte à indexer des objets dans votre paquet.
Vous pouvez amoindrir ceci en encodant chaque index d'objet relativement au précédent. Pensez-y, nous itérons de gauche à droite sur notre tableau, donc les indices commencent à 0 et vont jusque MaxObjets - 1 . Statistiquement parlant, vous avez toutes les chances d'avoir des objets proches les uns des autres et si l'index suivant est +1, ou même +10 ou +30 que le précédent, en moyenne, vous aurez besoin de bien moins de bits pour représenter cette différence que pour représenter un index absolu.
Voici une façon d'encoder l'index de l'objet sous forme d'entier relativement à l'index du précédent objet, tout en dépensant moins de bits sur des valeurs statistiquement plus probables (par exemple de petites différences entre des indices successifs, ou à l'inverse de grandes différences) :
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.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
template <typename Stream>
bool serialize_object_index_internal( Stream & stream,
int & previous,
int & current )
{
uint32_t difference;
if ( Stream::IsWriting )
{
assert( previous < current );
difference = current - previous;
assert( difference > 0 );
}
// +1 (1 bit)
bool plusOne;
if ( Stream::IsWriting )
plusOne = difference == 1;
serialize_bool( stream, plusOne );
if ( plusOne )
{
if ( Stream::IsReading )
current = previous + 1;
previous = current;
return true;
}
// [+2,5] -> [0,3] (2 bits)
bool twoBits;
if ( Stream::IsWriting )
twoBits = difference <= 5;
serialize_bool( stream, twoBits );
if ( twoBits )
{
serialize_int( stream, difference, 2, 5 );
if ( Stream::IsReading )
current = previous + difference;
previous = current;
return true;
}
// [6,13] -> [0,7] (3 bits)
bool threeBits;
if ( Stream::IsWriting )
threeBits = difference <= 13;
serialize_bool( stream, threeBits );
if ( threeBits )
{
serialize_int( stream, difference, 6, 13 );
if ( Stream::IsReading )
current = previous + difference;
previous = current;
return true;
}
// [14,29] -> [0,15] (4 bits)
bool fourBits;
if ( Stream::IsWriting )
fourBits = difference <= 29;
serialize_bool( stream, fourBits );
if ( fourBits )
{
serialize_int( stream, difference, 14, 29 );
if ( Stream::IsReading )
current = previous + difference;
previous = current;
return true;
}
// [30,61] -> [0,31] (5 bits)
bool fiveBits;
if ( Stream::IsWriting )
fiveBits = difference <= 61;
serialize_bool( stream, fiveBits );
if ( fiveBits )
{
serialize_int( stream, difference, 30, 61 );
if ( Stream::IsReading )
current = previous + difference;
previous = current;
return true;
}
// [62,125] -> [0,63] (6 bits)
bool sixBits;
if ( Stream::IsWriting )
sixBits = difference <= 125;
serialize_bool( stream, sixBits );
if ( sixBits )
{
serialize_int( stream, difference, 62, 125 );
if ( Stream::IsReading )
current = previous + difference;
previous = current;
return true;
}
// [126,MaxObjects+1]
serialize_int( stream, difference, 126, MaxObjects + 1 );
if ( Stream::IsReading )
current = previous + difference;
previous = current;
return true;
}
template <typename Stream>
bool serialize_scene_d( Stream & stream, Scene & scene )
{
int previous_index = -1;
if ( Stream::IsWriting )
{
for ( int i = 0; i < MaxObjects; ++i )
{
if ( !scene.objects[i].send )
continue;
write_object_index( stream, previous_index, i );
write_object( stream, scene.objects[i] );
}
write_object_index( stream, previous_index, MaxObjects );
}
else
{
while ( true )
{
int index;
read_object_index( stream, previous_index, index );
if ( index == MaxObjects )
break;
read_object( stream, scene.objects[index] );
}
}
return true;
}
En général pas mal de bande passante sera économisée parce que les indices d'objets auront tendance à être regroupés. Au cas où l'objet suivant est envoyé, il s'agit d'un unique bit pour l'index suivant qui vaudra +1 et 5 bits par index pour +2 à +5. En moyenne on aura entre 2x à 3x moins de surcoût pour nos index. Mais remarquez que des indices plus élevés et éloignés coûteront beaucoup plus cher pour chaque index qu'un encodage non relatif (12 bits par index). Ce qui semble mauvais ne l'est pas parce que, pensez-y, même si vous atteignez le « pire cas » (indices d'objets séparés uniformément de 128 index), combien d'objets pouvez-vous avoir dans un tableau de 4000 objets ? Juste 32. Pas d'inquiétude !
VII. ID de protocole, CRC32 et vérifications de sérialisation▲
À ce moment, vous devez vraiment vous poser des questions. Waouh ! Ce truc semble vraiment fragile. C'est un flux binaire totalement arbitraire. Un château de cartes. Que se passe-t-il si par un moyen quelconque read et write se désynchronisent ? Si quelqu'un envoie des paquets contenant des octets aléatoires à votre serveur. Combien de temps avant qu'une suite d'octets entraîne un crash de votre application ?
J'ai de bonnes nouvelles pour vous et le reste de l'industrie du jeu vidéo puisque la plupart des serveurs reposent sur ce procédé. Il y a des techniques que vous pouvez utiliser pour réduire ou virtuellement éliminer la possibilité de corruption de données une fois les données sérialisées.
La première technique est d'inclure un identifiant de protocole dans votre paquet. Typiquement, les quatre premiers octets peuvent être utilisés pour insérer une valeur raisonnablement rare et unique, peut-être 0x123456789 parce que personne d'autre ne pensera jamais à l'utiliser. Mais sérieusement, mettez un hash de votre identifiant de protocole et votre version de protocole dans les premiers 32 bits de chaque paquet et vous vous en sortirez bien. Au moins si un paquet est envoyé à votre port d'une autre application (souvenez-vous que les paquets UDP peuvent venir de n'importe quelle combinaison IP/port à tout moment) vous pouvez facilement l'écarter :
2.
[protocol id] (32bits)
(packet data)
Le niveau suivant de protection est d'inclure un CRC32 de votre paquet dans l'en-tête. Ça vous permettra de détecter les paquets corrompus (ça arrive, rappelez-vous que le checksum IP n'est que 16 bits, et beaucoup d'informations ne seront pas vérifiées par un checksum de 16 bits…). Maintenant l'en-tête de votre paquet ressemble à ça :
2.
3.
[protocol id] (32bits)
[crc32] (32bits)
(packet data)
Là vous devez grincer des dents. Attends. Je dois utiliser 8 octets par paquet juste pour implémenter mon propre checksum et identifiant de protocole ? Et bien, vous ne devez pas . Vous pouvez vous inspirer du checksum IPv4, et faire de l'identifiant de protocole un préfixe magique . Par exemple : vous ne l'envoyez pas, mais si l'émetteur et le receveur connaissent tous deux l'identifiant de protocole et que le CRC32 est calculé comme si le paquet était préfixé par l'identifiant de protocole, le CRC32 sera incorrect si l'émetteur n'a pas le même identifiant de protocole que le receveur, permettant de sauver quatre octets par paquet :
2.
3.
[protocol id] (32bits) // not actually sent, but used to calc crc32
[crc32] (32bits)
(packet data)
Bien sûr le CRC32 ne protège que contre les malformations aléatoires de paquet, et n'est pas une protection contre un émetteur mal intentionné qui peut aisément modifier ou construire un paquet malveillant puis ajuster correctement le CRC32 dans les quatre premiers bits. Pour vous protéger face à ça, vous devrez utiliser une fonction de hash plus cryptographiquement sécurisée éventuellement combinée avec un échange de clés secrètes entre le client et le serveur via HTTPS effectué par le serveur de matchmaking avant que le client ne tente de se connecter au serveur de jeux (une clé différente pour chaque client, connue uniquement par le serveur et ce client particulier).
Une technique pour finir, peut-être plus une vérification d'erreur de programmation de votre côté et émetteurs mal intentionnés (bien que redondante une fois que vous chiffrez et signez votre paquet) est la vérification de sérialisation . Typiquement, quelque part au milieu du paquet, avant ou après une section de sérialisation compliquée, ajoutez juste une valeur entière connue de 32 bits, et vérifiez qu'elle est lue à la réception avec la même valeur. Si la valeur est incorrecte, abandonnez la lecture et rejetez le paquet .
J'aime faire ça entre les sections de mon paquet quand je les écris, au moins je sais quelle partie de la sérialisation de mon paquet s'est désynchronisée entre lecture et écriture pendant le développement de mon protocole (ça va arriver quoi que vous fassiez pour l'éviter…). Une autre astuce cool que j'aime utiliser est de sérialiser une vérification de protocole à la toute fin du paquet. C'est super, super utile parce que ça aide à détecter les troncations de paquets (comme l'ignoble troncation little endian vs big endian du dernier mot de l'article précédent ).
Le paquet ressemble maintenant à ça :
2.
3.
4.
[protocol id] (32bits)// non envoyé, mais utilisée pour calculer le crc32
[crc32] (32bits)
(packet data)
[end of packet serialize check] (32 bits)
Vous pouvez juste retirer ces vérifications de protocole dans votre application finale si vous voulez, particulièrement si vous avez un bon chiffrement et une bonne signature de paquets, puisqu'elles ne devraient plus être nécessaires à ce stade.
VIII. Remerciements▲
Cet article est une traduction autorisée de l'article de Glenn Fiedler.
| Article précédent | Article suivant |
|---|---|
| << Lecture et écriture des paquets |