À la fin de l'article sur la compression LZ, il avait été question de fréquence d'apparition des nombres pour les offsets de référence et les longueurs de motif. Cette constatation avait amené lors de l'article sur ZX0 à regarder le codage gamma, qui permet de coder des entiers avec un nombre de bits variable afin d'optimiser la taille des petits nombres (qui sont plus fréquents).
Revenons sur cette histoire de fréquence en l'étendant à tous les symboles présents dans les données à compresser. Il serait intéressant d'avoir un codage dépendant de la fréquence d'apparition des symboles : plus le symbole est fréquent, plus son code est court.
Ce codage est obtenu avec l'algorithme de Huffman.
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.
Dans l'article précédent sur la compression, l'idée était de remplacer les successions d'éléments identiques par un couple (nombre de répétitions, valeur). Cela fonctionne bien avec des plages de données contenant un même élément, mais beaucoup moins bien lorsque les données changent fréquemment.
La séquence suivante, par exemple, sera très mal compressée par cette méthode RLE :
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
En effet, cette séquence ne contient aucune répétition d'un élément unique. Chaque élément est différent du précédent. Avec la méthode RLE, on devrait écrire :
(1, .), (1, #), (1, .), (1, #), ...
On peut avoir envie de se dire, avec cette séquence, que le motif à répéter est .# et qu'on le répète 16 fois. Mais on pourrait aussi se dire que c'est 4 fois le motif .#.#.#.#. Ou encore 2 fois le motif .#.#.#.#.#.#.#.#. Dans tous les cas, il nous faudrait une sorte de dictionnaire pour référencer les motifs que l'on voudrait répéter.
Avec la publication de la version 0.9 de Briques Stellaires, ma contribution à la Game Jam « Retro Programmers United for Obscure Systems » session PHC-25 est l'occasion de revenir sur cette session et ma proposition.
Vu les caractéristiques modestes mais sympathiques du PHC-25, j'ai eu envie de faire un jeu plutôt action. Exercice toujours délicat pour ces machines peu utilisées dont les émulateurs sont très très perfectibles, pour ne pas dire à côté de la plaque. Mais ayant eu un accès temporaire à la machine, je ne me suis dit que... allez pourquoi pas.
J'étais parti sur un twist du classique casse-brique. Au final, le temps passant toujours à sa proverbiale vitesse, le jeu est... un casse-brique tout ce qu'il y a de plus standard.
Mais voyons un peu les détails potentiellement intéressants du développement.
L'environnement de développement
Je suis parti pour cette contribution sur un développement en assembleur Z80 …
Dès le début de l'informatique, même si je ne saurais pas dater exactement quand, il a été question de stocker ou transmettre des données de manière efficace. Comment stocker ou transmettre un maximum de données avec un minimum d'espace ou de bande passante ? La compression de données répond à cette problématique avec des algorithmes qui repèrent l'information redondante pour la représenter de manière plus concise, ou bien qui éliminent des données jugées'(selon certains critères) moins utiles que d'autres.
Dans ce premier article, nous allons voir ce que j'imagine être la plus simple des méthodes et qui vient souvent à l'esprit en premier lorsque l'on découvre le sujet : la compression RLE (Run Length Encoding).
Le flux d'entrée
Imaginons une image en niveaux de gris que l'on pourrait représenter de cette manière :
