Après avoir présenté dans l'article précédent sur la compression LZ l'idée générale de référencement arrière de données déjà présentes en mémoire, cet article va se concentrer sur une implémentation spécifique de la famille LZ : le ZX0, un algorithme développé par Einar Saukas avec pour double objectif une taille très compacte pour le code de décompression et une recherche des choix optimaux lors de la compression.
Au niveau du code de décompression, sur Z80 et pour reprendre les exemples fournis dans le README officiel, on a les chiffres suivants :
- Routine "Standard" : 68 octets
- Routine "Turbo" : 126 octets, environ 21% plus rapide
- Routine "Fast" : 187 octets, environ 25% plus rapide
- Routine "Mega" : 673 octets, environ 28% plus rapide
Pour obtenir un code de décompression aussi compact, les choix faits dans le format ZX0 sont adaptés à un décodage avec peu de calculs et des calculs simples.
Rentrons dans les détails.
Le double flux
ZX0 utilise deux flux de données distincts. Le premier flux contient les informations sur les blocs : quel type de bloc (littéral ou référence arrière), les offsets et les longueurs. Ce flux est lu bit par bit. Le second flux contient les données littérales elles-mêmes, lues octet par octet.
Il suffit donc d'avoir une routine qui lit le bit suivant du premier flux et une routine qui lit l'octet suivant du second flux. Un pointeur suffit pour le second flux. Le premier flux est un peu plus complexe : il nécessite un pointeur, un octet courant et un compteur de bits restants dans l'octet courant. Cela reste très simple.
Ces deux flux sont entrelacés. Lorsque l'une des deux routines a besoin d'un nouvel octet, elle le lit depuis les données compressées. Cela signifie qu'en fait, un seul pointeur est nécessaire pour parcourir les deux flux. De manière symétrique, cela signifie que lors de la compression, les données doivent être écrites en un seul flux en entrelaçant les deux types de données au fur et à mesure qu'elles forment un octet complet.
Encodage des nombres
À la fin de l'article précédent, la constatation était que les références avaient souvent des petites longueurs et qu'il pouvait être intéressant de trouver un moyen d'encoder ces petites longueurs de manière efficace.
ZX0 prend acte et utilise un codage nommé « codage gamma » ou encore « codage gamma d'Elias » ("Elias Gamma coding").
Principe du codage gamma
Le codage gamma propose d’écrire un nombre en deux parties : la longueur binaire nécessaire et la valeur restante depuis la puissance de 2 inférieure.
La longueur du nombre en binaire est encodée de manière unaire : on regarde combien de bits sont nécessaires pour écrire le nombre en binaire, on écrit cette valeur moins un en unaire (avec autant de 0 que le nombre voulu), puis on termine avec un 1. Incidemment, cela représente la puissance de deux inférieure nécessaire pour coder le nombre.
Par exemple, pour le nombre 3, qui s'écrit 11 en binaire (2 bits), on écrit 01 (un 0 suivi d'un 1). Pour le nombre 10, qui s'écrit 1010 en binaire (4 bits), on écrit 0001 (trois 0 suivis d'un 1).
Pour la valeur restante, on prend le nombre, on enlève la plus grande puissance de 2 qui ne dépasse pas ce nombre, puis on écrit le reste en binaire, sur le nombre de bits calculé précédemment (le nombre de fois où on a trouvé 0 avant le 1).
Par exemple, pour le nombre 3, la plus grande puissance de 2 inférieure est 2 (\(2^1\)), donc le reste est \(3 - 2 = 1\), qui s'écrit 1 en binaire sur 1 bit. Pour le nombre 10, la plus grande puissance de 2 inférieure est 8 (\(2^3\)), donc le reste est \(10 - 8 = 2\), qui s'écrit 010 en binaire sur 3 bits.
Ainsi on a :
3 -> 01 1 (pour un total de 3 bits)
10 -> 0001 010 (pour un total de 7 bits)
Ce codage est efficace pour les petits nombres (jusqu'à 15), car il peut les écrire avec moins de 8 bits. En revanche, il devient moins efficace pour les nombres plus grands (par exemple 16 occupe 9 bits en codage gamma).
Ce codage offre aussi l'avantage d'être sur un nombre de bits variable et de permettre la « découverte » de cette taille lors de la lecture.
Mais pour rendre le décodage encore plus simple, ZX0 utilise une variante appelée « codage gamma entrelacé » qui permet de lire tous les bits dans l'ordre en une seule passe. L'entrelacement se fait entre la partie unaire et la partie binaire (dans le sens du plus petit bit vers le plus grand). Les bits de la première partie (unaire) sont les bits impaires et les bits de la seconde partie (binaire) sont les bits paires.
Exemples :
3 codé 01 1 devient 011
10 codé 0001 010 devient 0001001
Avec ce système, il suffit de lire un bit et s'arrêter s'il est à 1, sinon lire un autre bit pour la partie binaire, l'ajouter à l'accumulateur préalablement décalé vers la gauche. Puis recommencer jusqu'à trouver un 1. Pour que l'algorithme fonctionne, l'accumulateur doit être initialisé à 1.
Par exemple, pour décoder 011 :
- Lire 0 (unaire), on continue
- Lire 1 (binaire), accumulateur = 1 << 1 | 1 = 3
- Lire 1 (unaire), on s'arrête, valeur finale = 3
Et pour décoder 0001001 :
- Lire 0 (unaire), on continue
- Lire 0 (binaire), accumulateur = 1 << 1 | 0 = 2
- Lire 0 (unaire), on continue
- Lire 1 (binaire), accumulateur = 2 << 1 | 1 = 5
- Lire 0 (unaire), on continue
- Lire 0 (binaire), accumulateur = 5 << 1 | 0 = 10
- Lire 1 (unaire), on s'arrête, valeur finale = 10
Les types de blocs
Maintenant que l'on sait qu'il y a deux flux et comment encoder les nombres, voyons comment ZX0 organise les blocs de données. Il existe trois types de blocs :
- Bloc littéral : contient les données littérales. Est associé à une longueur.
- Bloc de référence : référence une séquence de données précédemment rencontrée. Est associé à un offset et une longueur.
- Bloc de référence de même offset : tout comme un bloc de référence, mais réutilise le dernier offset utilisé et ne spécifie donc que la longueur.
Pour différencier ces trois types de blocs, ZX0 utilise un seul bit. Un seul bit pour désigner trois types de blocs ? Cela est possible car certaines contraintes logiques existent entre les blocs :
- Deux blocs littéraux ne peuvent pas se suivre (sinon ils seraient fusionnés en un seul bloc littéral).
- Un bloc de référence de même offset ne peut apparaître qu'après un bloc littéral.
- Le premier bloc est toujours un bloc littéral (et d'ailleurs le tout premier bit qui devrait indiquer le type de bloc est omis).
Ainsi, le bloc littéral et le bloc de référence de même offset sont tous deux indiqués par un 0 et le bloc de référence avec nouvel offset est indiqué par un 1. Le contexte permet de savoir quel type de bloc est concerné entre les deux premiers.
Les longueurs sont encodées en utilisant le codage gamma entrelacé décrit précédemment. Pour les offsets, c'est un peu plus compliqué : l'offset est divisé en deux parties, le MSB (Most Significant Byte) utilise le codage gamma entrelacé, tandis que le LSB (Least Significant Byte) est stocké tel quel sur 7 bits (au lieu de 8). Comme on ne peut pas encoder 0 en gamma, le MSB de l'offset est stocké avec une valeur augmentée de 1.
Autre petite optimisation : puisqu'une référence avec nouvel offset a toujours une longueur minimale de 2, la longueur stockée pour une référence est en fait la longueur moins 1.
Exemples :
0 011 -> bloc littéral de longueur 3
(ou bien référence de longueur 3 selon le contexte)
1 1 0000011 0001001 -> bloc de référence avec nouvel offset de longueur 3
(1 en codage gamma pour MSB = 0)
(0000011 pour LSB = 3)
et longueur 11 (10 + 1)
Recherche optimale
Lors de l'article précédent qui présentait l'idée derrière la compression LZ, il avait été question de prendre en référence arrière la plus grande séquence identique possible. Cela fonctionne : c'est un type d'algorithme glouton (greedy). Cependant, cette méthode n'est pas forcément (pas souvent ?) optimale. Peut-être que prendre à un endroit le motif le plus long empêche de faire un meilleur choix de référence un peu plus loin. Ou bien peut-être que cela cause des codages gamma sur trop de bits. L'algorithme ZX0 fait le choix de trouver la solution optimale.
Pour cela, à chaque position lors de la compression, l'algorithme va examiner tous les offsets possible et regarder s'il est possible de faire une référence arrière et maintenir une chaîne optimale en calculant le coût total si une référence devait être faite à cet endroit.
L'algorithme fait appel à de la programmation dynamique pour obtenir un code compact et efficace. Efficace, mais pas rapide : la compression avec ZX0 est lente avec des fichiers un peu conséquents, c'est son principal inconvénient. Mais en échange, on est assuré que, avec les choix de codage de ce format, le résultat est le plus compact possible.
Test sur l'exemple
Reprenons à nouveau l'image en niveaux de gris des deux articles précédents et voyons ce que cela donne avec le format ZX0.
L'exemple, pour rappel :
................
....#######.....
..##@@@@@@@##...
.##@OOOOOOO@##..
.#@OoooooooO@#..
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
.#@OoooooooO@#..
.##@OOOOOOO@##..
..##@@@@@@@##...
....#######.....
................
Le résultat de la compression avec ZX0 est le suivant :
File compressed from 272 to 51 bytes! (delta 3)
Soit un fichier final ayant un peu moins de 19% de la taille originale. Pour rappel, la compression RLE et LZ « naïve » avaient donné un fichier de 57% la taille originale. C'est nettement mieux.
Voici le contenu de fichier final :
0000000 95 2e 89 0a 2e a4 23 f7 de b9 ed 40 fe ff ef de
0000010 ee e0 4f fe 7f dc fb de e1 6f 9f fe dd fc de e0
0000020 f7 dc 91 de 1f 12 5d d7 ce 75 8a d9 46 1d d7 02
0000030 55 55 80
On peut s'amuser à décoder le début à la main.
On garde le premier octet $95 (10010101 en binaire) en mémoire, il s'agit des informations de blocs. Le premier bloc est toujours un bloc littéral, on commence donc par une longueur en codage gamma entrelacé. 1 signifie une longueur de 1. On lit donc le premier octet du flux littéral : $2e (le caractère .). Nous voici avec notre premier caractère décodé.
On continue à lire ce qu'il reste de notre octet $95 : le bit suivant est un 0. Puisque le bloc précédent était un bloc littéral, ce 0 indique un bloc de référence de même offset. Le offset précédent est initialisé à 1 en début d'algorithme. On a donc une référence de 1 en arrière (le caractère . déjà décodé). Reste à lire la longueur en codage gamma entrelacé : 010101... le nombre n'est pas terminé, il nous faut un nouvel octet depuis le flux. C'est $89 (10001001 en binaire).
On continue la lecture : 1. Le bit de fin du codage gamma. Ce qui donne au final 0101011, soit 0001 111 en désentrelacé, soit une longueur de 15. On copie donc 15 fois le caractère trouvé une position avant. Nous voici avec 16 caractères . décodés. À noter qu'il n'y avait qu'un seul octet dans le flux littéral, mais la copie avance en recopiant le caractère déjà décodé. Avec une référence arrière de 1, il y a autant de copie de . que nécessaire.
Continuons. Le prochain bloc est indiqué par le bit suivant : 0. Puisque le bloc précédent était une référence, ce 0 indique un bloc littéral. On lit la longueur en codage gamma entrelacé : 001, soit 01 0 en non entrelacé, ce qui signifie 2. On lit donc les deux octets suivants dans le flux littéral : $0a (le caractère de retour chariot) et $2e (le caractère .). Nous venons de compléter la première ligne de l'image et de débuter la seconde.
Vous pouvez continuer si vous le souhaitez, mais je m'arrête ici pour cet exemple.
Fonctionnalités avancées
Avant de refermer cet article, il est intéressant de noter que ZX0 propose quelques fonctionnalités supplémentaires.
La compression à rebours
Plutôt que de compresser les données du début à la fin du fichier d'entrée, ZX0 permet de compresser les données en commençant par la fin du fichier d'entrée. L'algorithme est le même, sauf que le flux commence par la fin et que les références « arrières » sont « plus loin » en mémoire (puisque le début du flux est à la fin du fichier).
Cela est intéressant dans des scénarios où les données compressées et décompressées se recouvrent (ce qui est tout à fait possible aussi avec la compression standard) et que l'on veut « viser » l'adresse mémoire la plus haute disponible.
En effet, lors d'un recouvrement, l'algorithme à besoin d'un « décalage minimum » entre les deux flux de données (indiqué par le « delta » affiché lors de la compression). Pour bien comprendre ce que signifie ce delta et l'intérêt de la compression à rebours, le mieux est de consulter les diagrammes fournis dans le README.
Compression avec préfixe
Très pratique pour des décompressions « par morceaux », il est possible de fournir au compresseur un préfixe de données que l'on sait seront déjà présentes en mémoire lors de la décompression juste avant les nouvelles données à décompresser.
Le compresseur pourra donc piocher les références dans ce préfixe, sans pour autant inclure ces données dans le flux compressé. Bien entendu, il faut garantir que ces données seront bien présentes en mémoire lors de la décompression, puisque le décompresseur va les référencer.
Mode rapide
Enfin, du fait de la recherche optimale, la compression avec ZX0 peut être assez lente. Le compresseur propose donc une option « rapide » pour diminuer le temps de compression. L'option -q a pour effet de réduire fortement la fenêtre de recherche des références arrière qui est normalement de 32640 octets et passe à 2176 octets.
La recherche optimale est toujours effectuée, mais en allant chercher beaucoup moins loin les blocs pouvant être référencés. Cela diminue fortement le temps de compression, mais potentiellement aussi le taux de compression.
Pour l'exemple ci-dessus, dont la taille totale est bien inférieure à 2176 octets, cela ne change rien du tout. Ni en temps, ni en taille finale.
Conclusion
ZX0 est un algorithme de compression assez populaire sur les machines 8 bits. Le code source est disponible, il est simple à mettre en oeuvre, le code de décompression est très compact. Il a même été porté sur d'autres processeurs que le Z80.
Bien qu'un peu lent à compresser, le résultat de compression est bon et la décompression rapide. Ça en fait un très bon choix.
J'espère avoir pu vous donner une idée des choix faits par cet algorithme de compression/décompression et de son fonctionnement. Pas de code source dans cet article, j'ai directement utilisé l'implémentation officielle.
