Nous avons essayé de décoder un format binaire avec PHP

Nous nous sommes récemment intéressés à un format de données binaires appelé Smile. Notre objectif était d’écrire un encodeur / décodeur en PHP pour ce format, dans le cadre d’un exercice pratique pour mon alternance chez JoliCode. Nous vous expliquons dans cet article comment nous nous y sommes pris et comment ça s’est passé.

Section intitulée le-protocole-smile-qu-est-ce-que-c-estLe protocole Smile, qu’est-ce que c’est ?

Le protocole Smile est un format de données qui permet d’encoder en binaire des fichiers JSON. Il s’agit d’un format avec un potentiel intéressant car il promet une taille de fichier fortement diminuée, et donc des temps d’écriture et de lecture réduits. Ces promesses sont accompagnées d’un benchmark sur GitHub. Dans ce benchmark, nous voyons en effet que l’implémentation Smile de Jackson est plus rapide et produit des fichiers plus légers : elle a mis un total de 1805 nanosecondes pour produire un fichier de 252 octets, contre 2216 nanosecondes pour produire un fichier de 293 octets pour son équivalent JSON.

Ce format se distingue par les 3 premiers octets qui composent tout fichier smile : il s’agit du smiley :) suivi par un saut de ligne. Il propose également une fonctionnalité intéressante pour réduire la taille de ses fichiers : l’utilisation de “backrefs”. Les backrefs sont des identifiants attribués à toutes les clés rencontrées lors de l’encodage du fichier JSON. Lorsque cette clé sera rencontrée à nouveau, plutôt que d’être répétée, l’identifiant qui lui a été attribué la remplacera, faisant profiter d’une économie d’octets. Associée au format binaire, cette feature permet de réduire considérablement la taille de certains fichiers. En option, il est d’ailleurs possible de l’activer également pour les valeurs.

Le poids de fichiers JSON accompagnés de leur équivalent en Smile.

L’équipe derrière ce protocole est celle de Jackson, une librairie Java permettant de parser du JSON ainsi que de nombreux autres formats de données. La librairie a naturellement implémenté son propre parser Smile, faisant office de référence.

Ce format étant supporté par Elasticsearch et étant porteur de belles promesses, nous avons décidé de nous y intéresser. Nous avons ainsi fait le constat qu’il existe déjà de nombreuses implémentations du protocole dans différents langages. Cependant il n’en existe pas en PHP, notre langage de prédilection. Avec l’idée d’éventuellement utiliser le protocole dans nos projets, nous avons donc décidé de réaliser notre propre implémentation.

En ce qui me concerne, il ne s’agissait pas d’une mince affaire puisque je n’avais jusque là jamais eu l’occasion de travailler avec du binaire, et des opérations telles que la suivante m’inspiraient bien peu :

$sharedValueReference = (($firstByte & 3) << 8) | ($secondByte & 255);

Fort heureusement, nous pouvions compter sur Jackson et les autres librairies existantes pour nous aider. Si nous avons commencé par nous appuyer sur la librairie en Python, nous avons fini par nous tourner vers les librairies en JavaScript et en Go, proposant des approches différentes et couvrant davantage de types.

Nous avons commencé ce projet par le décodeur, comme la plupart des autres librairies. Pour tester ce décodeur, nous avons emprunté les fichiers de test de la librairie Go, qui nous semblaient très pertinents. Pour cet article, notre mission sera de décoder en JSON le fichier Smile suivant :

:)
ú‡test key#û

Nous montrons ici la représentation ASCII de notre fichier binaire pour des soucis de lisibilité. Il s’agit d’une version réduite de l’un de nos fichiers de tests. C’est parti !

Section intitulée decoder-du-binaire-en-phpDécoder du binaire en PHP

La première étape que nous allons devoir effectuer, c’est de déconditionner (unpack en anglais) notre chaîne binaire afin de pouvoir la lire. PHP propose une fonction native pour effectuer cette opération : unpack. De nombreux formats de sortie nous sont proposés. Les autres librairies font unanimement le choix du format hexadécimal afin de traiter ces données, mais dans notre cas nous avons fait le choix du format décimal. En effet, le résultat de la fonction PHP est plus facile à traiter en format décimal qu’en format hexadécimal.

unpack('H*', $smileData);
// output : [1 => "3a290a03fa8774657374206b657923fb”]

Résultat obtenu en utilisant la fonction unpack sur notre fichier Smile en demandant une sortie au format hexadécimal.

unpack('C*', $smileData);
// output : [58, 41, 10, 3, 250, 135, 116, 101, 115, 116, 32, 107, 101, 121, 35, 251]

Résultat obtenu avec une sortie au format décimal : il s’agit de celle que nous avons retenue et que nous utiliserons pour la suite de l’article.

In fine cela ne change rien, dans les 2 cas nous obtenons une suite d’octets. Dans le premier cas ils sont en base 16 et dans le second ils sont en base 10, c’est la seule différence – à ceci près qu’il est plus simple de manipuler un tableau de nombres qu’une chaîne de caractères.

Nous allons désormais pouvoir utiliser ces octets pour reconstituer notre fichier JSON. Le protocole Smile définit en effet une signification pour chacun d’entre eux.

L’octet avec la valeur décimale 250 par exemple, que nous trouvons en 5ème position, indique le début d’un objet. L’octet avec la valeur décimale 251, en dernière position, indique la fermeture d’un objet.

Cela ressemble donc bien à un fichier JSON.

Notre objet JSON est précédé de 4 octets propres au format Smile : les 3 octets “:)\n” (58, 41 et 10 en décimal) constituant le header Smile évoqué précédemment, puis un octet indiquant les options qui ont été choisies pour encoder ce fichier, comme l’activation des backrefs pour les valeurs, elle aussi abordée auparavant.

Une fois les 3 octets du header ignorés et l’octet des options pris en compte, nous allons pouvoir nous atteler à notre objet JSON. Nous allons itérer sur notre tableau d’octets et, pour chaque octet, nous allons effectuer un match afin de savoir à quoi correspond cet octet et comment allons-nous devoir le décoder. Ces informations sont disponibles sur les spécifications du format. Il faudra toutefois faire une conversion du format hexadécimal au format décimal, les spécifications du protocole utilisant le premier.

Nous pouvons d’ores et déjà enlever les octets d’ouverture et de fermeture de l’objet, en plus des octets propres aux fichiers Smile. Notre tableau d’octets est donc désormais le suivant :

[135, 116, 101, 115, 116, 32, 107, 101, 121, 35]

Et notre résultat JSON est le suivant :

{
}

Nous avons ici affaire à un objet. Dans un objet, le premier élément que nous rencontrons est une clé. L’octet 135 servira donc à définir le type de cette clé. En nous référant aux spécifications, nous apprenons que cet octet, pour les clés, indique que nous sommes face à un short ASCII. Puisque nous sommes en présence d’une clé, nous sauvegardons aussi en mémoire une référence à cette clé afin de la réutiliser plus tard : c’est le système de backrefs.

Smile n’encode pas les chaînes de caractères, elles sont laissées telles quelles. Nous aurons donc besoin de transformer tous les octets de cette chaîne de caractères en véritables caractères, et il faut pour cela utiliser une fonction native de PHP : chr. Toutefois, nous allons avoir besoin de connaître la longueur de cette chaîne de caractères. Pour ce faire, nous allons appliquer une petite opération à notre octet ASCII :

$length = ($byte & 31) + $bits;

$byte est notre octet ASCII, qui vaut dans notre exemple 135. $bits est une valeur arbitraire dépendant de la taille de l’ASCII. Dans notre cas, nous décodons une clé qui est un short ASCII, $bits va avoir une valeur de 1. Nous effectuons donc l’opération suivante : (135 & 31) + 1.

En réalisant notre calcul, nous obtenons 8. La clé de notre objet est donc une chaîne de 8 caractères ASCII. Nous allons ainsi pouvoir appliquer chr aux 8 prochains octets de notre tableau afin de retrouver une chaîne de caractères en UTF-8. Une fois cette opération effectuée, notre fichier JSON ressemble à cela :

{
    "test key":
}

Nous pouvons enlever de notre tableau d’octets l’identifiant short ASCII ainsi que les 8 suivants que nous venons de décoder (nous vous conseillons en réalité d’utiliser un pointeur, nous simplifions notre explication pour les besoins de l’article). Notre tableau d’octets est donc désormais le suivant :

[35]

Il ne nous reste qu’un octet à décoder ! Nous venons de décoder une clé, ce qui suit est donc forcément une valeur. Dans les spécifications, nous voyons que l’octet 35, pour les valeurs, vaut « true ». Nous pouvons enlever ce dernier octet de notre tableau et ajouter « true » à notre JSON :

{
    "test key": true
}

Il s’agit bien d’un fichier JSON valide. Success !

Nous avons bien sûr pris ici un exemple simple. La plupart du temps, nous devons effectuer des calculs compliqués pour décoder des fichiers Smile, surtout lorsque cela concerne des nombres. Si vous souhaitez voir à quoi ressemblent ces calculs, vous pouvez les trouver sur GitHub. La plupart proviennent de Jackson.

Section intitulée la-fin-de-l-aventureLa fin de l’aventure

Si cette tentative a été enrichissante, elle n’a malheureusement pas abouti. En effet, après avoir atteint un stade satisfaisant de notre décodeur, nous avons effectué un bench afin de voir si nous pouvions envisager d’utiliser notre implémentation. Malheureusement, ce bench s’est avéré extrêmement mauvais :

Décoder un fichier Smile avec notre implémentation a mis une moyenne de 1.558 secondes contre une moyenne de 12 millisecondes pour un json_decode natif, ce qui est 129 fois plus long. Bien sûr, notre implémentation pourrait être optimisée afin de réduire cette différence. Néanmoins, l’écart de performances constaté étant considérable, il nous semble utopique d’espérer se rapprocher des performances d’un json_decode.

Pour cette raison, nous avons décidé à contre-cœur de laisser là notre tentative. En effet, bien que la réduction du poids soit intéressante sur certains fichiers, la perte de performances nous a semblé vraiment trop importante pour que nous puissions considérer l’utilisation d’une telle implémentation. Le coût CPU fait perdre tous les gains réseaux que nous pourrions avoir.

Si vous souhaitez en voir davantage sur notre librairie, le code source est disponible sur GitHub. Si vous souhaitez l’améliorer ou l’optimiser n’hésitez pas, nous sommes ouverts !