Construire un protocole de jeu en réseau

Bonjour, je suis Glenn Fiedler. Je suis un programmeur réseau de jeu vidéo avec plus de 15 ans d'expérience en tant que professionnel de l'industrie. Désormais, j'ai fondé et dirige The Network Protocol Company où j'aide à mettre en réseau le jeu des personnes nous sollicitant, et sur mon temps libre j'écris du code open source et des articles comme celui que vous êtes en train de lire actuellement. Avant de créer ma compagnie, j'ai travaillé comme ingénieur logiciel chez Irrational Games, Sony Santa Monica, Respawn Entertainment et beaucoup d'autres.

Bienvenue sur Créer un protocole réseau de jeu vidéo . Dans cette série d'articles, je vais mettre en place un protocole réseau client/serveur de niveau professionnel pour jeux d'action comme les jeux de tirs à la première personne (First Person Shooter - FPS). Le meilleur choix est d'utiliser un protocole spécifique basé sur UDP. Je vais vous montrer ce dont il s'agit, à quoi le protocole ressemble, et comment le mettre en place vous-même.

Si vous venez du monde du développement web, vous avez probablement utilisé du XML, JSON ou YAML pour transférer des données en format textuel via le réseau. Ceci marche plutôt bien dans le monde du développement web, mais dans un jeu vidéo, les protocoles textuels sont rarement utilisés. Dans cet article, je vais vous montrer pourquoi .

Considérez un serveur web. Il reçoit les requêtes, effectue sa tâche de manière asynchrone puis envoie les réponses aux clients. Il n'a pas d'état et généralement n'est pas temps réel (bien qu'une réponse rapide soit préférable). À l'inverse, un serveur de jeu est une simulation temps réel d'une partie, et a toujours un état donné. Ce sont des situations totalement différentes !

Les modèles de trafic réseau sont également différents. Au lieu de requêtes sporadiques de dizaines de milliers de clients, un serveur de jeu a un plus petit nombre de clients, mais doit traiter un flux continu de paquets envoyés par chacun d'eux 60 fois par seconde. Il reçoit ces entrées, effectue la simulation adéquate, puis envoie l'état du monde à chaque client à une certaine fréquence (20, 30 ou même 60 fois par seconde).

Et cet état est énorme . Des milliers d'objets avec des centaines de propriétés chacun. Les programmeurs réseau passent beaucoup de temps à optimiser comment cet état est envoyé via le réseau, avec encodage delta, astuces de remplissage d'octets et formats binaires codés à la main, parce qu'il s'agit de l'essentiel de leur trafic réseau.

Mais avant d'aller plus loin, que se passerait-il si nous encodions l'état du monde en XML ?

<world_update world_time="0.0">
  <object id="1" class="player">
    <property name="position" value="(0,0,0)"</property>
    <property name="orientation" value="(1,0,0,0)"</property>
    <property name="velocity" value="(10,0,0)"</property>
    <property name="health" value="100"></property>
    <property name="weapon" value="110"></property>
    ... 100s more properties per-object ...
   </object>
 <object id="100" class="grunt">
   <property name="position" value="(100,100,0)"</property>
   <property name="health" value="10"</property>
 </object>
 <object id="110" class="weapon">
   <property type="semi-automatic"></property>
   <property ammo_in_clip="8"></property>
   <property round_in_chamber="true"></property>
 </object>
 ... 1000 objets supplémentaires ...
</world_update>

Comme vous le voyez, la plus grosse partie du fichier XML sert à décrire la donnée plutôt qu'à indiquer sa valeur.

JSON est un peu plus compact :

{
  "world_time": 0.0,
  "objects": {
    1: {
      "class": "player",
      "position": "(0,0,0)",
      "orientation": "(1,0,0,0)",
      "velocity": "(10,0,0)",
      "health": 100,
      "weapon": 110
    }
    100: {
      "class": "grunt",
      "position": "(100,100,0)",
      "health": 10
    }
    110: {
      "class": "weapon",
      "type": "semi-automatic"
      "ammo_in_clip": 8,
      "round_in_chamber": 1 
    }
  }
}

Mais ce n'est pas encore bon…

Et si, au lieu de décrire complètement l'état du monde dans chaque paquet, nous découpions ceci en deux parties ?

1. Un schéma qui décrit une collection d'objets classe et propriétés par classe, envoyé une seule fois quand le client se connecte au serveur.
2. Les données envoyées rapidement (20, 30 ou 60 fois par seconde) du serveur au client, encodées suivant ce schéma .

Un schéma pourrait ressembler à ça :

{
  "classes": {
    0: "player" {
      "properties": {
        0: {
          "name": "position",
          "type": "vec3f"
        }
        1: {
          "name": "orientation",
          "type": "quat4f"
        }
        2: {
          "name": "velocity",
          "type": "vec3f"
        }
        3: {
          "name": "health",
          "type": "float"
        }
        4: {
          "name": "weapon",
          "type": "object", 
        }
      }
    }
    1: "grunt": {
      "properties": {
        0: {
          "name": "position",
          "type": "vec3f"
        }
        1: {
          "name": "health",
          "type": "float"
        }
      }
    }
    2: "weapon": {
      "properties": {
        0: {
          "name": "type",
          "type": "enum",
          "enum_values": [ "revolver", "semi-automatic" ]
        }
        1: {
          "name": "ammo_in_clip",
          "type": "integer",
          "range": "0..9",
        }
        2: {
          "name": "round_in_chamber",
          "type": "integer",
          "range": "0..1"
        }
      }
    }  
  }
}

Maintenant, le client connaît les classes du monde et le nombre, nom, type et valeurs possibles et propriétés de chaque classe. Par exemple, si un objet est une instance de classe 2, nous savons qu'il s'agit d'une arme, et la propriété 0 de cet objet est le type d'arme : revolver (0) ou semi-automatique (1).

Avec ce savoir, nous pouvons déjà envoyer des parties de l'état du monde de façons bien plus compactes :

{
  "world_time": 0.0,
  "objects": {
    1: [0,"(0,0,0)","(1,0,0,0)","(10,0,0)",100,110],
    100: [1,"(100,100,0)",10],
    110: [2,1,8,1]
  }
}

Et nous pouvons avoir une encore meilleure compression en utilisant un format de texte personnalisé :

0.0
1:0,0,0,0,1,0,0,0,10,0,0,100,110
100:1,100,100,0,10
110:2,1,8,1

Comme vous pouvez le voir, en programmation réseau de jeu, il s'agit surtout de ce que vous n'envoyez pas plutôt que ce que vous envoyez. L'astuce ici est que quand le serveur et le client ont tous deux connaissances de la structure des données, beaucoup d'informations qui devraient sinon être envoyées peuvent être omises. C'est un des cas où avoir des états est une bonne chose .

Nous avons bien progressé sur notre format textuel jusque-là, passant d'un flux qui décrit totalement les données (plus de description des données que de données en soit) à un format textuel sans attribut tellement plus efficace.

Mais il reste des lacunes qu'un format texte ne peut combler :

1. La plupart des données envoyées sont dans l'intervalle A-Z, a-z et 0-1, et quelques autres symboles. Il s'agit d'une perte du reste des 0-255 valeurs possibles pour chaque caractère envoyé. D'un point de vue théorique, c'est un encodage inefficace.
2. La représentation en texte d'une valeur entière est dans le cas général beaucoup moins efficiente que le format binaire. Par exemple, le plus grand entier non signé 32 bits « 4294967295  » prend 10 octets en texte, en binaire il en prend juste 4.
3. En texte, même les plus petits nombres dans l'intervalle 0-9 nécessitent au moins un octet. En binaire, les plus petites valeurs comme « 0,11,31,100  » peuvent être envoyées avec moins de 8 bits si nous connaissons leur intervalle par avance.
4. Si un entier est négatif, vous devez utiliser un octet entier pour le signe « -  » pour l'indiquer.
5. Les nombres flottants dépensent un octet pour spécifier la virgule « , ».
6. La représentation textuelle des valeurs numériques est à longueur variable : « 5  », « 12345  », « 3.141593  ». À cause de ceci, nous devons utiliser un octet comme séparateur après chaque valeur pour savoir où elle se termine. Aucun séparateur n'est nécessaire en binaire puisque le nombre de bits requis peut être déterminé en fonction de l'intervalle de valeurs possibles, qui est connu de part et d'autre.
7. Les séparateurs de lignes « \n  » et d'autres séparateurs sont nécessaires pour distinguer les variables appartenant à un objet et au suivant. Quand vous avez des centaines d'objets, ça rentre en ligne de compte.

Pour faire court, si nous voulons optimiser davantage, il est nécessaire de passer à un format binaire.

Dans le monde du web, il y a de bonnes bibliothèques qui permettent de lire et écrire des formats binaires comme BJSON, Protocol Buffers, Flatbuffers, Thrift, Cap'n Proto et MsgPack. Dans certains cas, ces bibliothèques peuvent être d'une grande aide pour votre protocole réseau.

Mais dans d'autres cas, en particulier dans les jeux de tirs à la première personne où l'efficacité est primordiale, un protocole binaire personnalisé à cette fin est une bien meilleure option.

Il y a plusieurs raisons à cela. Les formats binaires à destination du web sont conçus pour une situation où le contrôle des versions est extrêmement important (si vous mettez à jour votre backend, les clients plus anciens devraient toujours être capables de communiquer en utilisant l'ancien format). Les formats de données langage-agnostiques sont également importants ; un backend écrit en golang devrait être capable de communiquer avec un client web qui tourne dans un navigateur en JavaScript, et les microservices écrits en différents langages devraient pouvoir communiquer sans avoir à mettre à jour tous leurs composants en même temps.

Les serveurs de jeu pour FPS AAA sont des bestiaux totalement différents. Le client et le serveur sont le plus souvent écrits dans le même langage (C++) parce que de larges portions du code de jeu doivent être exécutées de manière identique sur le serveur et le client pour la prédiction côté client. Le contrôle des versions est beaucoup plus simple également, parce que si un client incompatible essaye de se connecter au serveur, il sera tout simplement refusé. Ça peut sembler être problématique, mais en pratique, les clients doivent toujours posséder la dernière version avant de pouvoir utiliser les fonctionnalités en ligne de toute façon. Et pendant le développement, l'algorithme de matchmaking peut s'assurer que les clients sont redirigés vers des serveurs compatibles.

Donc si vous n'avez pas besoin de contrôler les versions et de supporter plusieurs langages, quels sont les avantages de ces bibliothèques ? Le confort. Facile à utiliser. Pas besoin de créer, tester, maintenir et fixer votre propre format binaire. Mais ce confort se paye par le fait que ces bibliothèques sont moins efficaces qu'un protocole que nous pouvons créer nous-mêmes. Nous en savons plus sur les données que nous envoyons que toute bibliothèque ne pourra jamais et nous pouvons profiter de cet avantage pour envoyer moins de bits en développant notre propre format binaire personnalisé.

Une façon de créer votre propre protocole binaire est d'utiliser le format de données de vos structures C/C++ en mémoire en tant que telles. On commence souvent par ici, donc même si je ne recommande pas cette approche, explorons-la un peu avant de voir ses défauts.

D'abord, définissez un ensemble de paquets, typiquement en tant qu'union de struct  :

struct Packet
{
    enum PacketTypeEnum { PACKET_A, PACKET_B, PACKET_C };

    uint8_t packetType;
 
    union
    {
        struct PacketA
        {
            int x,y,z;
        } a;

        struct PacketB
        {
            int numElements;
            int elements[MaxElements];
        } b;

        struct PacketC
        {
            bool x;
            short y;
            int z;
        } c;
    }; 
};

Quand vous écrivez un paquet, mettez le premier octet du paquet à la valeur de son type (0, 1 ou 2). Puis, selon le type de paquet, utilisez memcpy pour copier la bonne structure de l'union dans le paquet. Pour la lecture, faîtes l'inverse : lisez le premier octet, puis selon le type de paquet, copier les données du paquet dans la structure correspondante.

Ça ne pourrait pas être plus simple. Alors pourquoi la plupart des jeux évitent-ils cette approche ?

La première raison est que les différents compilateurs et plateformes fournissent différents remplissages (packing) de structures. Si vous vous aventurez sur cette voie, vous passerez du temps à jouer avec #pragma pack pour vous assurer que les différents compilateurs et plateformes ont une représentation mémoire des structures exactement identiques. Pas que ce soit impossible, mais ce n'est certainement pas trivial.

Ensuite l'endianness . La plupart des ordinateurs sont en little endian (Intel), mais les cœurs PowerPC sont en big endian. Historiquement, les données étaient envoyées à travers le réseau en big endian (aussi appelé network byte order), mais vous n'avez aucune raison de suivre cette tradition. Bien souvent les protocoles modernes utilisent du little endian pour minimiser la quantité de travail.

Mais si vous devez supporter la communication entre machines little endian et big endian , l'approche de copie mémoire de structure ne marchera simplement pas. Vous devrez au moins écrire une fonction d'inversion d'octets entre l'endianness de la machine et du réseau pour chaque lecture et écriture de chaque variable de votre structure.

Il y a également d'autres problèmes. Si votre structure contient des pointeurs, vous ne pouvez pas juste sérialiser cette valeur et attendre qu'elle soit valable sur la machine distante. Aussi, si vous avez des structures à taille variable, comme un tableau de 32 éléments, mais qu'il est vide ou ne contient que quelques éléments la plupart du temps, c'est un gâchis de devoir envoyer le tableau entier à chaque fois. Une meilleure approche serait de supporter un encodage de taille variable qui n'envoie que le nombre d'éléments actuellement présents dans le tableau.

Enfin, le coup de grâce est la sécurité.

C'est un risque majeur de sécurité que d'accepter des données du réseau. Et je ne peux imaginer quelque chose qui nécessite plus de confiance que de copier des données reçues depuis le réseau et juste les copier dans une structure. Ouaiis ! Et si quelqu'un crée un paquet malveillant et vous l'envoie avec la valeur 0XFFFFFFFF dans numElements de PacketB provoquant un accès à l'ensemble de la mémoire quand vous traitez ce paquet ?

Vous devriez, non vous devez , au moins faire quelques vérifications de chaque champ, que la valeur est bornée, au lieu d'accepter ce qui vous est envoyé aveuglément. Voilà pourquoi l'approche memcpy est rarement utilisée au niveau professionnel.

Le prochain niveau de complexité est les fonctions d'écriture (write ) et lecture (read ) par paquet.

Commencez avec les opérations simples suivantes :

void WriteInteger( Buffer & buffer, uint32_t value );
void WriteShort( Buffer & buffer, uint16_t value );
void WriteChar( Buffer & buffer, uint8_t value );

uint32_t ReadInteger( Buffer & buffer );
uint16_t ReadShort( Buffer & buffer );
uint8_t ReadByte( Buffer & buffer );

Ceci s'applique sur une structure tampon qui garde la position dans le paquet :

struct Buffer
{
    uint8_t * data;     // pointer to buffer data
    int size;           // size of buffer data (bytes)
    int index;          // index of next byte to be read/written
};

La fonction d'écriture (write ) ressemble à ceci :

void WriteInteger( Buffer & buffer, uint32_t value )
{
    assert( buffer.index + 4 <= size );
#ifdef BIG_ENDIAN
    *((uint32_t*)(buffer.data+buffer.index)) = bswap( value ); 
#else // #ifdef BIG_ENDIAN
    *((uint32_t*)(buffer.data+buffer.index)) = value; 
#endif // #ifdef BIG_ENDIAN
    buffer.index += 4;
}

Et la fonction de lecture (read ) à :

uint32_t ReadInteger( Buffer & buffer )
{
    assert( buffer.index + 4 <= size );
    uint32_t value;
#ifdef BIG_ENDIAN
    value = bswap( *((uint32_t*)(buffer.data+buffer.index)) );
#else // #ifdef BIG_ENDIAN
    value = *((uint32_t*)(buffer.data+buffer.index));
#endif // #ifdef BIG_ENDIAN
    buffer.index += 4;
    return value;
}

Maintenant, au lieu de copier les données du paquet dans des structures pour la lecture et écriture, implémentez les fonctions read et write pour chaque type de paquet :

struct PacketA
{
    int x,y,z;

    void Write( Buffer & buffer )
    {
        WriteInteger( buffer, x );
        WriteInteger( buffer, y );
        WriteInteger( buffer, z );
    }

    void Read( Buffer & buffer )
    {
        ReadInteger( buffer, x );
        ReadInteger( buffer, y );
        ReadInteger( buffer, z ); 
    }
};

struct PacketB
{
    int numElements;
    int elements[MaxElements];

    void Write( Buffer & buffer )
    {
        WriteInteger( buffer, numElements );
        for ( int i = 0; i < numElements; ++i )
            WriteInteger( buffer, elements[i] );
    }

    void Read( Buffer & buffer )
    {
        ReadInteger( buffer, numElements );
        for ( int i = 0; i < numElements; ++i )
            ReadInteger( buffer, elements[i] );
    }
};

struct PacketC
{
    bool x;
    short y;
    int z;

    void Write( Buffer & buffer )
    {
        WriteByte( buffer, x );
        WriteShort( buffer, y );
        WriteInt( buffer, z );
    }

    void Read( Buffer & buffer )
    {
        ReadByte( buffer, x );
        ReadShort( buffer, y );
        ReadInt( buffer, z );
    }
};

Quand vous lisez ou écrivez un paquet, commencez le paquet avec un octet pour spécifier le type de paquet ReadByte ou WriteByte, puis selon son type, appelez Read ou Write sur la structure de l'union correspondante.

C'est un réel progrès. Maintenant, nous avons un système qui permet aux machines avec différents endianness de communiquer et de supporter des structures contenant des éléments de taille variable.

Jusque-là, nous avons lu et écrit des paquets au niveau de l'octet.

Mais si nous avons une valeur dans l'intervalle [0,1000], nous n'avons besoin que de 10 bits pour représenter toutes les valeurs possibles. Ne serait-il pas intéressant si nous pouvions écrire que 10 bits, au lieu d'en utiliser 16 ?

Il serait vraiment intéressant de pouvoir envoyer un booléen en utilisant un bit, au lieu d'un octet.

Une façon d'implémenter ceci est d'organiser manuellement vos structures C++ en entiers tassés avec des champs de bits et unions, comme grouper tous les booléens en un entier via une union et les sérialiser groupés. Mais c'est fastidieux et sujet à erreur, il n'y a aucune garantie que les différents compilateurs C++ représentent les champs de bits en mémoire de façons strictement identiques.

Une façon plus souple pour un très léger surcoût en CPU à la lecture et écriture du paquet est un bitpacker . Il s'agit d'un code capable de lire et écrire des non-multiples de 8 bits dans un tampon. Pour y parvenir, il doit réaliser quelques opérations manuelles de décalage de bits parce que les données lues et écrites ne correspondent à aucun type machine ( byte , short , int ).

Beaucoup (la plupart ?) des personnes écrivent un bitpacker qui fonctionne au niveau de l'octet. Ce qui signifie qu'ils écrivent les octets dans la mémoire comme ils viennent. C'est plus simple à coder, mais l'idéal est de lire et écrire un mot à la fois, parce que les machines modernes sont optimisées pour travailler de cette manière au lieu de manipuler des octets à travers un tampon comme en 1985.

Si vous voulez écrire 32 bits en une fois, vous aurez besoin d'un mot intermédiaire de taille double, c'est-à-dire uint64_t . La raison est que vous avez besoin de la moitié pour le dépassement. Par exemple, si vous venez d'écrire 30 bits dans ce mot, puis une autre valeur de 10 bits, vous avez besoin de stocker 30+10 = 40 octets, au moins jusqu'à ce que vous sortiez les premiers 32 bits vers le tampon.

Nous allons travailler au niveau du mot de 32 bits, donc notre bitpacker d'écriture ressemblera à quelque chose comme ça :

uint64_t scratch;
int scratch_bits;
int word_index;
uint32_t * buffer;

Quand nous commençons à l'utiliser, toutes ces variables sont initialisées à zéro, à l'exception de buffer qui pointe vers le début du paquet dans lequel nous écrivons. Puisque nous accédons aux données du paquet au niveau du mot, et non du bit, soyez sûr que la taille du tampon est multiple de 4 octets.

Disons que nous voulons écrire 3 bits suivis de 10 bits, puis 24. Notre but est de tasser ça au mieux dans scratch , puis de l'écrire dans buffer , 32 bits à la fois. Notez que 3+10+24=37. Nous devons gérer ce cas où le nombre total de bits n'est pas divisible par 32. Il s'agit en fait du cas le plus courant .

Commencez par écrire les 3 bits dans scratch comme ceci :

Xxx

scratch_bits vaut maintenant 3.

Puis écrivez les 10 bits :

Yyyyyyyyyyxxx

scratch_bits vaut maintenant 13 (3+10).

Ensuite écrivez les 24 bits :

Zzzzzzzzzzzzzzzzzzzzzzzzyyyyyyyyyyxxx

La variable scratch_bits vaut maintenant 37 (3+10+24). Nous dépassons maintenant les 32 bits dans notre variable scratch de 64 bits et avons 5 bits de dépassement (overflow) dans les 32 bits supérieurs. Envoyez les 32 premiers bits de scratch vers la mémoire, incrémentez word_index de un, décalez scratch de 32 bits puis retirez 32 de scratch_bits. scratch vaut maintenant :

Zzzzz

Nous avons fini d'écrire les bits, mais il reste des données dans scratch non envoyées au tampon. Il est important de penser à manuellement vider les bits restant de scratch vers la mémoire à la fin de l'opération d'écriture.

Quand nous envoyons un mot en mémoire, il est converti en little endian . Pour comprendre en quoi c'est important, considérez ce qu'il se passe si nous envoyons les octets en big endian  :

DCBA000E

Puisque nous remplissons les bits du mot de droite à gauche, le dernier octet dans le paquet E est actuellement à droite. Si nous essayons d'envoyer ce tampon dans un paquet de cinq octets (la quantité de données que nous devons envoyer), ce paquet aura un 0 comme dernier octet au lieu de E. Ouch !

Mais quand nous écrivons dans la mémoire en little endian , les octets y sont inversés comme ceci :

ABCDE000

Et nous pouvons écrire cinq octets et constater le E final. Et voilà !

Pour lire les données depuis le bitpacker , commencez avec le tampon envoyé à travers le réseau :

ABCDE

Le lecteur de bit aura cette forme :

uint64_t scratch;
int scratch_bits;
int total_bits;
int num_bits_read;
int word_index;
uint32_t * buffer;

On commence par initialiser à 0 toutes les variables, sauf total_bits qui prend la taille du paquet en nombre d'octets * 8, et buffer qui pointe vers le début du paquet.

L'utilisateur demande à lire trois bits. Puisque scratch_bits vaut 0, on lit dans le premier mot. Copiez ce mot dans scratch , décalez vers la gauche de scratch_bits (qui vaut 0…). Ajoutez 32 à scratch_bits .

Maintenant, lisez les trois premiers bits en copiant scratch vers une autre variable en utilisant le masque &((1<<3)-1) , ce qui donne la valeur de :

Xxx

Décalez scratch vers la droite de 3 bits puis soustrayez 3 de scratch_bits  :

Zzzzzzzzzzzzzzzzzzzyyyyyyyyyy

Lisez les 10 bits suivants de la même façon. scratch contient maintenant :

Zzzzzzzzzzzzzzzzzzz

La lecture suivante demande 24 bits, mais scratch_bits vaut 19 (=32-10-3).

Il est temps de lire dans le mot suivant. Copiez la mémoire dans scratch après l'avoir décalé de scratch_bits (19) vers la gauche. Maintenant vous avez tous les bits nécessaires pour z dans scratch  :

Zzzzzzzzzzzzzzzzzzzzzzzz

Lisez les 24 bits puis décalez scratch de 24 bits vers la droite. scratch est maintenant rempli de 0. On a fini.

Les bitpackers sont une excellente optimisation par rapport à l'écriture et lecture au niveau de l'octet, mais écrire et lire des valeurs entières dans un paquet en spécifiant le nombre de bits à lire ou écrire n'est pas l'interface la plus facile à utiliser.

Considérez cet exemple :

const int MaxElements = 32;

struct PacketB
{
    int numElements;
    int elements[MaxElements];

    void Write( BitWriter & writer )
    {
        WriteBits( writer, numElements, 6 );
        for ( int i = 0; i < numElements; ++i )
            WriteBits( writer, elements[i] );
    }

    void Read( BitReader & reader )
    {
        ReadBits( reader, numElements, 6 );
        for ( int i = 0; i < numElements; ++i )
            ReadBits( reader, elements[i] );
    }
};

Ce code a l'air bon à première vue, mais imaginons que plus tard, vous ou quelqu'un de votre équipe augmentez MaxElements de 32 à 200, mais oublie de mettre à jour le nombre de bits requis à 7 . Maintenant, le bit fort de numElements est silencieusement tronqué à l'envoi. C'est assez difficile de traquer une erreur comme ça a posteriori.

L'option la plus simple est de travailler dans l'autre sens et définir le nombre maximum d'éléments en fonction du nombre de bits envoyés :

const int MaxElementBits = 7;
const int MaxElements = ( 1 << MaxElementBits ) - 1;

Une autre option est de calculer le nombre de bits requis à la compilation :

template <uint32_t x> struct PopCount
{
    enum { a = x - ( ( x >> 1 ) & 0x55555555 ),
           b = ( ( ( a >> 2 ) & 0x33333333 ) + ( a & 0x33333333 ) ),
           c = ( ( ( b >> 4 ) + b ) & 0x0f0f0f0f ),
           d = c + ( c >> 8 ),
           e = d + ( d >> 16 ),
    result = e & 0x0000003f }; 
};

template <uint32_t x> struct Log2
{
    enum { a = x | ( x >> 1 ),
           b = a | ( a >> 2 ),
           c = b | ( b >> 4 ),
           d = c | ( c >> 8 ),
           e = d | ( d >> 16 ),
           f = e >> 1,
    result = PopCount<f>::result };
};

template <int64_t min, int64_t max> struct BitsRequired
{
    static const uint32_t result = 
        ( min == max ) ? 0 : ( Log2<uint32_t(max-min)>::result + 1 );
};

#define BITS_REQUIRED( min, max ) BitsRequired<min,max>::result

Maintenant, vous pouvez modifier le nombre de bits à souhait, et vous pouvez spécifier des valeurs maximales non-puissance de deux et tout fonctionne comme attendu.

const int MaxElements = 32;
const int MaxElementBits = BITS_REQUIRED( 0, MaxElements );

Mais soyez prudent quand un tableau n'a pas une taille puissance de deux, parce que la valeur sérialisée laisse l'opportunité à une personne mal intentionnée de construire un paquet qui corrompt votre mémoire !

Dans l'exemple ci-dessus MaxElements vaut 32, donc MaxElementBits vaut 6. Ça semble correct puisque toutes les valeurs valides pour numElements  : [0,32] rentrent sur six bits. Le problème est qu'il existe également d'autres valeurs de six bits de long qui sont hors bornes de notre tableau : [33,63]. Un assaillant peut utiliser ceci pour construire un paquet malveillant contenant une de ces valeurs pour nous faire corrompre la mémoire.

Ce qui conduit à l'inévitable conclusion qu'il ne suffit pas juste de spécifier le nombre de bits requis en lisant ou écrivant une valeur, nous devons à la place spécifier ses bornes de validité : [min, max]. Ainsi si une valeur hors borne est détectée, nous pouvons arrêter la lecture du paquet.

J'ai implémenté ceci en utilisant les exceptions C++ par le passé, mais quand j'ai profilé ce code je l'ai trouvé incroyablement lent. De mon expérience, il est bien plus rapide de prendre une des deux approches suivantes : lever un drapeau (flag) sur le lecteur de bit pour indiquer qu'il doit s'avorter, ou retourner false depuis les fonctions de lecture en cas d'erreur. Mais maintenant, afin d'être totalement sans danger au cours de la lecture, vous devez vérifier ce flag ou code de retour à chaque opération de lecture ou il est possible de tomber dans une boucle de corruption de mémoire.

const int MaxElements = 32;
const int MaxElementBits = BITS_REQUIRED( 0, MaxElements );

struct PacketB
{
    int numElements;
    int elements[MaxElements];

    void Write( BitWriter & writer )
    {
        WriteBits( writer, numElements, MaxElementBits );
            for ( int i = 0; i < numElements; ++i )
        WriteBits( writer, elements[i], 32 );
    }

    void Read( BitReader & reader )
    {
        ReadBits( reader, numElements, MaxElementBits );
        
        if ( numElements > MaxElements )
        {
            reader.Abort();
            return;
        }
        
        for ( int i = 0; i < numElements; ++i )
        {
            if ( reader.IsOverflow() )
                break;

            ReadBits( buffer, elements[i], 32 );
        }
    }
};

Si vous oubliez la moindre de ces vérifications, vous vous exposez à des débordements de tampon (buffer overflow ) et boucles infinies en lisant un paquet. Vous ne voulez évidemment pas que ce soit une étape manuelle quand vous écrivez une fonction de lecture de paquet. C'est trop important pour laisser une erreur d'inattention se glisser. Vous voulez que ce soit automatisé .

Dans le prochain article, je vous montrerai une bien belle façon de réaliser ceci en C++.

Cet article est une traduction autorisée de l'article de Glenn Fiedler.