Deckard es un replicante

La delta compression est une technique de compression des données. Si je m’arrêtais là, je pourrais me contenter de faire un tour sur twitter ou de dormir plus tôt. Au lieu de cela, je vous ai concocté un petit exemple adapté aux jeux vidéo en ligne. C’est beaucoup plus rigolo et d’autre part ça me permet de dérouiller mon C++. Définissons une structure de données assez simple qui représente l’envoi d’informations périodiques d’un joueur au serveur de jeu. Généralement un jeu comme un FPS envoi à intervalle régulier l’état de son personnage au serveur. Valve appelle cela un “tick rate” car cela représente la fréquence de synchronisation entre le client et le serveur. Tout ce qui se passe entre ces intervalles de temps est interpolé. Cette structure de données est décomposée en deux parties : l’en-tête et le corps. L’en-tête représente l’action jouée par le joueur, une BITMAP et un checksum. La BITMAP va nous servir pour l’algorithme de compression. Le checksum est inutile. Le très bon Fabien Sanglard décrit l’utilisation d’un tel checksum dans le protocole de Quake2 comme un moyen de vérifier que les paquets n’ont pas été altérés (autrement dit, l’anti-triche du pauvre). Je l’ai juste ajouté par soucis de réalisme à l’exemple (et aussi pour aligner la structure en mémoire mais ne le dites pas trop fort). Le corps contient les informations sur le monde du jeu. Ce sont ces données là qui seront compressées.

typedef struct header
{
	unsigned char action:4, compress:4;
	unsigned char csum;
} t_header;

typedef struct body
{
	unsigned short int orientation;
	unsigned short int pos_x;
	unsigned short int pos_y;
} t_body;

typedef struct message
{
	t_header head;
	t_body body;
} t_message; /* 8 bytes */

Notre message ressemble a ça :

|action|compress|csum|orientation|pos_x|pos_y|

Nous allons simuler le déplacement d’un personnage imaginaire suivant le chemin tracé ci-dessous (sur l’axe des x et des y).

Notez que sur le premier tronçon, le personnage ne change pas d’orientation et que sur les deux derniers il s’oriente aléatoirement. Il y a une dernière étape non visible sur le tracé et pour cause, le personnage ne bouge plus, il se contente juste de regarder à droite et gauche suivant son envie (aussi connue sous le nom “la pause du campeur”). Avec cette simulation nous allons voir de manière immédiate quel est l’intérêt de la delta compression. Vous me direz que je tourne autour du pot depuis le début, et bien c’est vrai. Prenons juste le paquet présenté plus haut.

|action|compress|csum|orientation|pos_x|pos_y|

Supposons que je le compare avec celui envoyé précédemment ou autrement dit p(t) avec p(t-1). Nous ne touchons pas à l’en-tête du paquet, mais seulement aux trois derniers champs. Ainsi si le personnage n’a pas bougé, une opération comme p(t) – p(t-1) nous donnera :

|action|compress|csum|

La delta compression est une technique basée sur la comparaison avec les précédents envois. Elle part du principe qu’il ne sert à rien de renvoyer une information qui n’a pas changé. Si l’on refait un exemple avec des valeurs numérique cette fois:

t-1 : |action|compress|csum|60|10|10| (personnage regardant à 60° et positionné en (10,10))

t : |action|compress|csum|60|15|10| (personnage regardant à 60° et positionné en (15,10))

Le paquet résultant sera :

|action|compress|csum|15|

Et là, vous devez immédiatement vous demander comment le destinataire va pouvoir recomposer le message original. Et bien grâce au champ de bits “compress”. Plongeons dans l’algorithme.

bool Network::Compress(unsigned short int *orig_arg, unsigned short int *old_arg, unsigned short int* current_ptr, int *len, char *mask)
{
	// true if no compression
	bool inc = false;
	// search changed
	if(*orig_arg != *old_arg)
	{
		// put it in buffer
		memcpy(current_ptr, orig_arg, sizeof(*orig_arg));
		*len += sizeof(short int);
		inc = true;
	}
	else
	{
		// save unchanged
		*mask += 1;
	}

	// shift
	*mask <<=1;

	return inc;
}

Déroulons l’algorithme dans l’ordre d’exécution. Les deux premiers arguments sont les mêmes paramètres séparés d’un intervalle de temps. Dans l’exemple précédent pour pos_x, les valeurs 10 et 15. Si ces deux valeurs sont différentes, la delta compression ne s’applique pas. On place la dernière valeur dans le buffer du message qui sera envoyé par un socket (en augmentant la taille du buffer de la taille de l’argument ajouté). La partie intéressante est juste après. Si les deux arguments avaient été égaux, on aurait juste ajouté 1 à la valeur du BITMAP. Et dans les deux cas nous décalerons ensuite. Le BITMAP permet de dire à l’autre bout qui devra recomposer le message quel morceaux ont été enlevé ou non. Je vous rappel que mon champ ‘compress’ tient sur 4 bits. Reprenons l’exemple précedent.

t-1 : |action|compress|csum|60|10|10| (personnage regardant à 60° et positionné en (10,10))

t : |action|compress|csum|60|15|10| (personnage regardant à 60° et positionné en (15,10))

Je compare 60 et 60. C’est égal donc je delta compresse. J’ajoute un au mask et je décale à gauche. Donc compress = ’0010′ Je prends ensuite 10 et 15 qui sont différents. Je ne delta compresse pas mais je décale encore une fois à gauche. Donc compress = ’0100′. Pour le dernier cas, 10 et 10, je delta compresse également. Donc compress = ’1001. (vous remarquerez le bug de mon implémentation, le deuxième zéro est faux car je n’aurai pas du décaler pour le premier passage). Pour corriger l’exemple disons que le résultat obtenu est compress =’0101′. Comme nous n’avons que 3 arguments, nous ne regardons que les trois derniers bits. Un 1 signifie que l’argument a été compressé et un 0 non. Ainsi le serveur sait en recevant ce message que pour le reconstituer il doit insérer les arguments désignés par les 1 (autrement dit, le premier argument et le dernier). L’algorithme complet donne ceci:

int Network::Send(t_message *message)
{
	char *snd_buffer;
	int snd_len = 0;

	if(delta_compress)
	{
		// can be allocate just one time, simpler to do it here dynamically
		snd_buffer = (char *)malloc(sizeof(t_message));
		snd_len = 2*sizeof(char);

		unsigned short int *current_ptr = (unsigned short int*)(snd_buffer + snd_len);

		// copy header into buffer
		memcpy(snd_buffer, &(message->head), snd_len);

		// change mask
		char mask = 0x00;

		if(Compress(&(message->body.orientation), &(old_message.body.orientation), current_ptr, &snd_len, &mask)) current_ptr++;
		if(Compress(&(message->body.pos_x), &(old_message.body.pos_x), current_ptr, &snd_len, &mask)) current_ptr++;
		if(Compress(&(message->body.pos_y), &(old_message.body.pos_y), current_ptr, &snd_len, &mask)) current_ptr++;

		// set new mask
		snd_buffer[1] = mask;

		// save (new) old buffer, we save the whole message but we can only save the body since compression only apply to it
		memcpy(&old_message, message, sizeof(t_message));

	}
	else
	{
		snd_buffer = (char*)message;
		snd_len = sizeof(t_message);
	}
	sendto(sock, snd_buffer, snd_len, 0, (struct sockaddr*)&sout, sizeof(struct sockaddr));

	if(delta_compress) free(snd_buffer);

	return snd_len;
}

La classe Network qui encapsule toute la logique permet de désactiver la delta compression (symbolisée par le booléen delta_compress). Voilà rien d’extraordinaire, j’ai quand même réussi à laisser passer un beau bug sur le bitmap. En terme de performance et d’optimisation de la bande passante, les résultats sont assez bons: Ce graphique représente la taille de messages (en octet) dans le temps. On distingue très nettement les 4 paliers (avancer sur x, diagonale en tournant, avancer sur x en tournant, immobile en tournant). La ligne rouge représente la même expérimentation sans delta compression (on retrouve bien la taille de 8 octets de notre message). On aperçoit des variations dans les 3 derniers paliers à cause du caractère aléatoire de la rotation. Calculons un ratio de compression juste pour avoir quelques chiffres tangibles. Chaque palier est constitué de 200 échantillons. Le pire des cas envoie donc 800*8 octets = 6400 octets. En oubliant les oscillations et en conservant le pire des résultats avec la delta compression, nous obtenons 4*200 + 8*200 + 6*200 + 4*200 = 4400 octets. Soit un ratio de 4400 / 6400 = 68% donc 32% de compression. Bon, ce n’est pas vraiment représentatif de l’activité réelle d’un joueur mais c’est tout de même un beau résultat. Surtout que dans le cas d’un si petit paquet, une compression de type Inflate (Zlib) était à proscrire car l’overhead de l’en-tête de zlib est déjà de 4 octets (au minimum).