lucidiot's cybrecluster

Well-Known Binary standard avec Kaitai Struct, première partie

Lucidiot Informatique 2022-01-26
Fini le XML, on passe au YAML.


Dans le précédent article, j'ai donné beaucoup de contexte théorique et technocratique sur les formats d'échange de géométries et notamment le Well-Known Binary, mais nous n'avons même pas encore vu à quoi ça ressemblait vraiment. C'est ce que nous allons voir à présent ; nous allons aujourd'hui nous attarder exclusivement au Well-Known Binary standard, la variante du WKB la plus basique.

Cette variante ne contient que le point, la ligne brisée, le polygone, les versions multiples de ceux-ci, et la collection de géométries qui peut contenir toutes les autres ainsi qu'elle-même. Le tout n'est qu'en deux dimensions et on ne parlera pas d'identifiant de système de référence spatiale. Comparé à la totalité du WKB, ce n'est finalement pas grand chose, mais puisqu'on va introduire moult notions sur ce format binaire, ça va déjà être un beau morceau.

Références

Dans un premier temps, voyons rapidement quelques documents et pages Web qui peuvent être utiles pour se faire une idée de la définition de ce Well-Known Binary standard :

Pour le développement du fichier qui sera expliqué ensuite dans cet article, je me suis également muni des deux outils que je connais le mieux pour jouer avec des géométries et générer des données binaires à tester :

Entités simples

On avait précédemment défini les entités simples comme étant des entités à deux dimensions qui ne contiennent pas d'autres entités. Dans le WKB standard, cela correspond à trois types : les points, les lignes brisées, et les polygones.

Attributs communs

Voici la traduction en WKB d'un point défini en WKT par POINT (1 2), sous forme hexadécimale.

01 01 00 00 00 00 00 00 00 00 00 F0 3F 00 00 00 00 00 00 00 40 Boutisme Type X Y Coordonné e Coordonné e

Le Well-Known Binary utilise seulement trois types de données, et on les retrouve tous ici :

Boutisme

Le tout premier attribut du Well-Known Binary est un byte, un seul octet qui n'a que deux valeurs possibles : zéro, ou un. Ça aurait pu être un seul bit, mais puisque quasiment tout en informatique s'aligne maintenant sur chaque octet, c'est plus simple de stocker ça dans un octet.

Ce tout premier octet indique le boutisme, ou en anglais l'endianness. Le boutisme est la manière dont on représente un nombre entier ; certaines architectures de processeur préféreront une façon plus qu'une autre pour des raisons de performance. Il existe des variantes peu connues comme le "mi-boutisme", mais les deux façons les plus connues sont le petit-boutisme (little-endian) et le gros-boutisme (big-endian). Le boutisme a un impact dès qu'on a une valeur qui occupe plusieurs octets puisqu'il choisit dans quel ordre on va stocker ces octets. Voici un exemple, deux fois le même nombre sur quatre octets avec des boutismes différents :

Quand on représente un nombre décimal, le chiffre le plus à droite est le chiffre le moins important : c'est celui des unités, donc il vaut beaucoup moins que le chiffre le plus à gauche, dont le changement aurait un bien plus grand impact. C'est le même principe dans une représentation binaire : le bit le plus à droite est appelé bit de poids faible, et ne permettra de représenter vraiment qu'un zéro ou un un, alors que son voisin pourra représenter zéro ou deux, et le suivant zéro ou quatre, etc., jusqu'au bit de poids fort, le plus à gauche.

Peu importe le boutisme, on ne change jamais l'ordre des 8 bits à l'intérieur d'un seul octet. Par contre, on change l'ordre des octets eux-mêmes. Le gros-boutisme est le plus lisible par les humains, puisque l'octet de poids fort reste tout à gauche. À l'inverse, le petit-boutisme est moins lisible, mais a historiquement été privilégié par les premiers processeurs puisqu'ils avaient un nombre limité de transistors. Aujourd'hui, les processeurs sont suffisamment complexes pour qu'utiliser le gros-boutisme ne coûte en fait plus grand chose, et aide les développeurs à lire du code machine.

Dans l'exemple ci-dessus, la valeur du boutisme a été définie à 1, ce qui correspond au petit-boutisme. Il faudra donc tout inverser dans sa tête tout le temps !

Type de géométrie

Après le boutisme vient le type de géométrie, un uint32. Dans le contexte du WKB standard, le type de géométrie est un nombre assez simple qui n'a que quelques valeurs possibles :

  1. Géométrie sans vrai type. Ça n'est pas censé exister, mais c'est défini.
  2. Point
  3. Ligne brisée
  4. Polygone
  5. Ensemble de points
  6. Ensemble de lignes brisées
  7. Ensemble de polygones
  8. Collection de géométries

Avec le WKB ISO et l'EWKB, on va avoir bien plus de types qui vont s'ajouter à la liste, ainsi que des informations supplémentaires stockées dans les nombreux bits inutilisés parmi ces 4 octets. Mais on verra ça bien sûr plus tard.

Dans l'exemple, on a 01 00 00 00. On utilise du petit-boutisme, donc il faut tout retourner : 00 00 00 01, on a donc un 1 en décimal, soit un point.

Point

Les deux derniers attributs de ce premier exemple sont deux nombres à virgule flottante qui correspondent respectivement à la coordonnée X et la coordonnée Y. Le standard IEEE 754 est vraiment complexe, donc je ne vais pas ici m'amuser à essayer de décoder le binaire moi-même cette fois-ci !

Ligne brisée

Une ligne brisée est définie comme étant une liste de points. On représente une liste de points en indiquant d'abord le nombre de points, pour qu'un lecteur puisse déterminer combien de paires de coordonnées lire, puis on liste les coordonnées les unes après les autres.

01 04 00 00 00 02 00 00 00 Point 1 Point 2 Boutisme Type Nombre de points Points Point : 00 00 00 00 00 00 F0 3F 00 00 00 00 00 00 00 40 X Y Coordonné e Coordonné e

Le type de géométrie est cette fois défini à 2, et on a un nouveau uint32 représentant le nombre de points, qui est ici défini à 3. On aura ensuite une succession de nombres à virgules flottantes, d'abord les X et Y du premier point, puis du second, puis du troisième.

Polygone

Un polygone est défini — sans rentrer dans les détails — comme une liste de lignes brisées, appelées anneaux linéaires. On a donc une liste de liste de points.

Une vue sous une forme d'arbre serait donc quelque chose comme ceci :

Au niveau binaire, on observera ceci :

01 03 00 00 00 02 00 00 00 Anneau 1 Anneau 2 Boutisme Type Nombre d'anneaux Anneaux Anneau : 02 00 00 00 Point 1 Point 2 Nombre de points Points

Après le type de géométrie, on a donc d'abord un nombre entier pour compter les lignes brisées, puis une répétition des lignes brisées : un nombre de points, suivi des paires de coordonnées de chaque point, le tout répété une fois par ligne brisée.

Kaitai Struct

Notre but aujourd'hui va être d'écrire une librairie permettant de lire un fichier WKB. Voici grosso merdo ce à quoi ressemblerait du code C# qui voudrait traiter du WKB avec notre librairie :

using WKBParser;

var geometry = new Geometry("/path/to/linestring.wkb");
Console.WriteLine(geometry.Type); // LineString (ligne brisée)
// 1.0 2.0, 3.0 4.0, …
foreach (var point in geometry.Body.Points)
    Console.WriteLine("{0} {1}", point.X, point.Y);

Mais ce ne serait pas forcément que du C# : on pourra aussi le faire en Java, JavaScript, Python, Lua, Perl, C++, Go, Nim, PHP ou Ruby. On pourra également afficher des diagrammes, ou avoir de la documentation générée autour de ce format de fichier.

Pour faire tout ça sans avoir à apprendre à traiter du binaire dans une dizaine de langages, on va avoir recours à Kaitai Struct. Kaitai Struct est un programme en Python qui traite un fichier YAML spécifique, appelé Kaitai Struct YAML (KSY) et peut générer du code. Le projet est plutôt mature, et on dispose pour nous aider d'une bonne documentation, d'un guide stylistique, d'un IDE en ligne et d'une collection de formats déjà créés.

Structure d'un fichier Kaitai Struct YAML

Un fichier KSY se composera d'au moins deux sections : meta et seq. La section meta contient quelques métadonnées sur le format de fichier, comme son nom, la version minimum nécessaire de Kaitai Struct, ou des références à des documentations externes. La section seq décrit une séquence d'attributs qui représentent l'ensemble du fichier. On pourrait par exemple écrire un fichier pour juste lire un fichier texte. C'est idiot, mais c'est possible :

meta:
  id: textfile
  title: Text file
  file-extension: txt
  license: WTFPL
  xref:
    forensicswiki: Text_File_(TXT)
    justsolve: Plain_text
    mime: text/plain
    pronom: x-fmt/111
    wikidata: Q1145976
seq:
  - id: text
    type: str
    encoding: utf8
    size-eos: true

On a ici un fichier publié sous licence WTFPL pour un format ayant généralement l'extension .txt. Diverses bases de données de formats de fichier connaissent ce format : Just Solve, Forensics Wiki, PRONOM, Wikidata. L'IANA lui a même donné un type MIME, text/plain.

Le fichier contient un unique attribut : text, une chaîne de caractères au format UTF-8 qui s'arrête à la fin du fichier. Vous pouvez avec ce fichier générer une façon inutilement complexe de lire un fichier texte dans un des langages supportés par Kaitai !

Console.WriteLine(new TextFile("/path/to/text.txt").Text);

Gérer un point

Maintenant que toutes les bases ont été posées, nous allons nous consacrer au premier objectif : pouvoir lire un point, la géométrie la plus simple de toutes. On va donc en définir les quatre attributs : le boutisme, le type de géométrie, et les deux coordonnées. Mais d'abord, écrivons le préambule, la section meta.

Préambule

Le format Well-Known Binary est plutôt mal connu ; la seule référence que nous pourrons donner parmi celles permises par Kaitai sera la norme ISO. Il n'y a pas non plus d'extensions courantes pour les fichiers, bien que j'utilise personnellement toujours .wkb. On pourrait lister toutes les applications utilisant couramment le format avec l'option application, mais il y en a énormément et le guide de style de Kaitai nous indique de ne pas faire ça s'il y a trop d'applications en même temps. Notre section meta sera donc bien plus courte :

meta:
  id: wkb_std
  title: Standard Well-Known Binary
  license: AGPL-3.0-or-later
  xref:
    iso: 19125-1:2004

Nous allons cependant pouvoir profiter d'une section utilisée un peu moins couramment. Pour un format qui a une quelconque documentation officielle, on peut faire référence à celle-ci en utilisant une section séparée, appelée doc-ref :

doc-ref:
  - https://www.ogc.org/standards/sfa
  - http://libgeos.org/specifications/wkb/

J'y ai mis le standard OGC, puisque c'est aussi là qu'on trouvera une définition du WKB, et la page de documentation de GEOS puisque c'est elle qui définit ce qu'est la variante standard du WKB.

Boutisme

Passons aux choses sérieuses. Notre premier attribut est le boutisme, un entier non signé à un octet. Les types dans Kaitai Struct ne sont pas nommés byte ou uint32 mais ont des noms spécifiques à Kaitai. Pour un entier signé (positif ou négatif), on utilise s, et pour un entier non signé, u. On fait suivre cette lettre du nombre d'octets utilisé, donc ici un seul :

seq:
  - id: endianness
    type: u1

Gérer le boutisme avec Kaitai Struct est en temps normal assez simple, puisqu'on peut ajouter un endian: le ou endian: be dans meta ou sur un seul attribut. Mais gérer un boutisme défini par le contenu du format de fichier est un peu plus haut perché, et nous verrons cela un peu plus tard. Pour l'instant, on va s'en ficher. On définira endian: le ou endian: be directement dans meta pour pouvoir tester des fichiers particuliers si on le souhaite.

Type de géométrie

Après le boutisme vient le type de géométrie. On pourrait le lire directement comme étant un nombre entier non signé à 4 octets :

- id: type
  type: u4

On peut cependant faire mieux que ça. On connaît la liste des valeurs autorisées pour ce nombre, et on connaît en plus le sens de ces valeurs ; ce n'est pas juste un 1, c'est un point. Pour encoder cette information dans Kaitai, on va utiliser une énumération. À côté de seq, nous utiliserons donc une nouvelle section, enums :

enums:
  geometry_type:
    0: geometry
    1: point
    2: line_string
    3: polygon
    4: multi_point
    5: multi_line_string
    6: multi_polygon
    7: geometry_collection

Nous pouvons ensuite assigner cette énumération à notre nombre ; Kaitai commencera par interpréter les octets en tant que nombre, puis fera correspondre le nombre ainsi compris à l'énumération.

- id: type
  type: u4
  enum: geometry_type

Coordonnées

Les deux coordonnées X et Y sont toutes les deux des nombres à virgule flottante double-précision, c'est-à-dire qu'ils occupent 8 octets. Kaitai prend en charge aussi la simple précision, donc on dispose de f4 et f8.

- id: x
  type: f8
- id: y
  type: f8

Il n'y a pas grand chose de plus à faire pour traiter ces deux nombres, et avec ça, nous avons désormais de quoi traiter un simple point.

Gérer une ligne brisée

On peut passer au niveau supérieur et s'essayer à la ligne brisée. On garde le même attribut pour le boutisme et le type de géométrie, mais les coordonnées vont fonctionner différemment. D'abord, nous allons définir un type de notre propre création avec la section types :

types:
  point:
    seq:
      - id: x
        type: f8
      - id: y
        type: f8

Nous pourrons ainsi réutiliser ce type avec type: point, et le répéter plusieurs fois pour former la ligne brisée.

Nombre de points

Le nombre de points est un entier non signé à 4 octets, donc il est assez trivial :

- id: count
  type: u4

Liste de points

Pour la liste de points, on va utiliser notre type point :

- id: points
  type: point

Kaitai nous fournit plusieurs façons de faire des répétitions, puisqu'il y a moult façons de faire répéter des choses dans un fichier binaire. On peut répéter jusqu'à la fin du fichier, répéter jusqu'à ce qu'une condition particulière soit vraie, ou répéter autant de fois que spécifié par une expression. Par expression et condition, je veux dire des courtes lignes dans le petit langage interne de Kaitai, qui permet de faire quelques opérations sur les attributs déjà traités. Dans notre cas, nous n'allons pas faire grand chose d'extravagant, et allons juste nous référer à count, le nombre de points que nous venons de lire :

- id: points
  type: point
  repeat: expr
  repeat-expr: count

Avec ces paramètres, on répétera X, puis Y, puis X, etc. autant de fois que spécifié par count. Dans un langage de programmation, points deviendra alors un tableau ou une liste contenant plusieurs points.

Sélection du type

Ces deux nouveaux attributs sont tout ce qu'il nous fallait pour en arriver aux lignes brisées. Mais comment va-t-on faire pour sélectionner entre le point et la ligne brisée selon l'attribut de type ? On va utiliser pour cela une fonctionnalité avancée appellée switch-on.

D'abord, plaçons notre ligne brisée dans un type à part, car nous allons aussi y faire référence ailleurs :

types:
  point: ...
  line_string:
    seq:
      - id: count
        type: u4
      - id: points
        type: point
        repeat: expr
        repeat-expr: count

Nous allons maintenant modifier notre séquence principale pour qu'elle corresponde à ceci :

Nous pourrions utiliser des bons vieux if :

seq:
  - id: endianness
    type: u1
  - id: type
    type: u4
    enum: geometry_type
  - id: point
    type: point
    if: type == geometry_type::point
  - id: line_string
    type: line_string
    if: type == geometry_type::line_string

Ça fonctionne, mais quand on se retrouvera avec au moins une vingtaine de types dans les deux autres variantes du WKB, on ne va pas trop apprécier. On peut raccourcir en utilisant switch-on :

seq:
  - id: endianness
    type: u1
  - id: type
    type: u4
    enum: geometry_type
  - id: data
    type:
      switch-on: type
      cases:
        geometry_type::point: point
        geometry_type::line_string: line_string

La simplification sera surtout notable pour le code généré, puisqu'on aura un seul attribut body au lieu d'avoir des dizaines d'attributs à tester un par un pour trouver lequel ne vaut pas null.

Gérer un polygone

Un polygone est, dans les limites de ce qui nous intéresse pour juste lire le fichier binaire, une liste de lignes brisées. On a le même système de nombre de lignes brisées suivi de leur répétition, donc on peut définir facilement notre type :

types:
  polygon:
    seq:
      - id: count
        type: u4
      - id: rings
        type: line_string
        repeat: expr
        repeat-expr: count

On ajoutera aussi bien sûr geometry_type::polygon: polygon dans notre switch-on précédent.

Gérer le boutisme

On ne parlera pas pour aujourd'hui du traitement des autres géométries, qui sont une toute autre affaire. On va donc pour aujourd'hui affronter un autre obstacle, la gestion du boutisme. Comme je l'ai dit plus haut, on pourrait utiliser le paramètre endian sur chaque attribut ou dans la section meta pour indiquer le boutisme, mais cela implique que ce boutisme soit fixe. Pour gérer un boutisme plus dynamique, Kaitai propose une solution dans sa documentation :

seq:
  - id: endianness
    type: u1
  - id: geometry
    type: geometry
types:
  geometry:
    # ...
    meta:
      endian:
        switch-on: _root.endianness
        cases:
          0: be
          1: le

On utilise la section meta, qui est aussi autorisée à l'intérieur d'un type personnalisé, pour définir le boutisme à l'échelle d'un type entier. On définit le boutisme avec un switch-on sur l'attribut de boutisme, qu'on a sorti complètement de la géométrie elle-même. Ainsi, l'attribut n'est pas influencé par le boutisme (et donc par lui-même) et peut être lu par Kaitai avant que sa valeur ne soit utilisée.

L'expression dans le switch-on est un tout petit peu plus compliqué : au lieu de juste mettre un nom d'attribut comme on a fait tout à l'heure avec count ou type, on utilise cette fois _root.endianness. endianness est le nom de l'attribut de boutisme, mais _root. signifie qu'on part de la racine de notre fichier pour aller le trouver. Si on mettait seulement endianness, Kaitai essaierait d'accéder à l'attribut au sein de notre type geometry, mais il n'y est pas défini.

On peut également utiliser _parent au lieu de _root pour accéder à l'élément parent, et cela reviendrait au même dans notre cas. Mais ce sera une fonctionnalité utile pour la seconde partie de notre traitement du WKB standard, avec les entités complexes.

Spécification actuelle

Voilà où nous en sommes arrivés pour le moment dans notre fichier KSY :

meta:
  id: wkb_std
  title: Standard Well-Known Binary
  license: AGPL-3.0-or-later
  xref:
    iso: 19125-1:2004
doc-ref:
  - https://www.ogc.org/standards/sfa
  - http://libgeos.org/specifications/wkb/

enums:
  geometry_type:
    0: geometry
    1: point
    2: line_string
    3: polygon
    4: multi_point
    5: multi_line_string
    6: multi_polygon
    7: geometry_collection

seq:
  - id: endianness
    type: u1
  - id: geometry
    type: geometry

types:
  point:
    seq:
      - id: x
        type: f8
      - id: y
        type: f8

  line_string:
    seq:
      - id: count
        type: u4
      - id: points
        type: point
        repeat: expr
        repeat-expr: count

  polygon:
    seq:
      - id: count
        type: u4
      - id: rings
        type: line_string
        repeat: expr
        repeat-expr: count

  geometry:
    seq:
      - id: type
        type: u4
        enum: geometry_type
      - id: data
        type:
          switch-on: type
          cases:
            geometry_type::point: point
            geometry_type::line_string: line_string
            geometry_type::polygon: polygon
    meta:
      endian:
        switch-on: _root.endianness
        cases:
          0: be
          1: le

Le parsing du WKB est encore loin d'être terminé. Il nous reste les quatre types de collections de géométries à gérer pour le WKB standard, puis nous devrons passer aux deux autres WKB ! Attendez-vous à encore moult posts sur le sujet.


  1. J'ai utilisé les nombres à échelle longue ici, qui est l'échelle supposémment standard en Europe de l'Ouest. Les anglophones parleraient probablement de septuacentillion. L'article anglais sur les noms des grands nombres avec celui sur l'échelle longue et courte donnent de longues explications sur le sujet. ↩︎


Commentaires

Il n'y a pour l'instant aucun commentaire. Soyez le premier !