• Compression de données, le format ZX0 (2025-11-02)

  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.

  ---

• Compression de données, référencer les répétitions (2025-10-24)

  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.

  Et c'est une manière assez courante de compresser des données : référencer un dictionnaire.

  Cependant, un dictionnaire, ça prend de la place. Et dans la compression que nous allons voir aujourd'hui, la méthode est d'utiliser les données elles-mêmes comme dictionnaire pour éviter de construire (et stocker) un dictionnaire à part. C'est la méthode LZ (Lempel-Ziv), du nom de ses inventeurs, ou en tout cas une manière dérivée de LZ.

  Le dictionnaire

  L'idée est la suivante : lorsque l'on en est à un point du flux de décompression, toutes les données précédemment décompressées sont disponibles en mémoire.

  Imaginons par exemple, avec la séquence précédente, que l'on a déjà décompressé les deux premiers caractères : .#. On peut tout à fait commencer à référencer ce motif dans le flux à decompresser qui arrive. La séquence à décompresser suivante pourrait être « répète le motif de longueur 2 qui commence 2 positions avant ». Ce qui donnerait, une fois ajouté aux données déjà décompressées : .#.#.

  À l'étape suivante, on pourrait avoir : « répète le motif de longueur 4 qui commence 4 positions avant ». On aurait à présent : .#.#.#.#

  Et ainsi de suite.

  Codage général

  Ainsi, il nous faut construire un flux compressé qui est une suite d'éléments unitaires (des séquences qui n'ont pas encore été vues) et de références à des motifs déjà vus (avec une paire (position en amont, longueur)).

  Sans entrer dans une implémentation précise, pour le motif précédent, on pourrait avoir ceci :

  .# (suite d'éléments unitaires)
  (-2,2) (référence au motif de longueur 2, 2 positions avant)
  (-4,4) (référence au motif de longueur 4, 4 positions avant)
  (-8,8) (référence au motif de longueur 8, 8 positions avant)
  (-16,16) (référence au motif de longueur 16, 16 positions avant)
  

  Si on utilise un élément marqueur pour indiquer si ce qui suit est une suite d'éléments unitaires ou une référence, cela donnerait globalement 15 éléments pour représenter les 32 éléments de l'original. Soit une taille finale d'un peu plus de 40% de l'original.

  Pas mal.

  Note : en vrai, on ne référencera pas des motifs aussi petits que deux éléments, car le gain en taille ne serait pas suffisant. Avec ce codage simpliste, il faut au moins 4 éléments pour référencer un motif de manière efficace.

  Méthode de compression

  Afin de compresser un flux de données avec cette méthode, à chaque étape, il faut chercher dans le flux en entrée si le motif qui suit est présent dans les données précédentes. Et ce pour la longueur la plus grande possible.

  Pour l'exemple, lorsque l'on commence le flux, le premier caractère est un .. Ce caractère n'est pas encore dans les données présentes (puisque c'est le premier). On l'écrit donc comme élément unitaire dans le flux compressé. De même pour le caractère suivant, un #, que l'on écrit aussi en tant qu'élément unitaires à la suite du premier.

  Pour la suite, on a dans le buffer à traiter une séquence .#.#.#.#.... On cherche le plus long motif qui est déjà dans les données. Ici, c'est .#, que l'on trouve à la position -2 (2 positions avant). On écrit donc la référence (-2,2) dans le flux compressé.

  Et ainsi de suite, jusqu'à la fin du flux d'entrée.

  Essai sur la séquence de l'article précédent

  Je reprends l'image en niveaux de gris de l'article précédent sur la compression RLE :

  ................
  ....#######.....
  ..##@@@@@@@##...
  .##@OOOOOOO@##..
  .#@OoooooooO@#..
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  .#@OoooooooO@#..
  .##@OOOOOOO@##..
  ..##@@@@@@@##...
  ....#######.....
  ................
  

  Dans le cas RLE, j'avais supprimé les sauts de ligne pour ne garder qu'une suite d'éléments et profiter des plages formées par la fin d'une ligne et le début de la ligne suivante. Ici, je vais les garder, c'est beaucoup moins génant puisque la méthode compresse les séquences répétées.

  Passé par l'algorithme décrit précédemment, voici ce que l'on obtient :

    Littéral:  (0, '....')
    Référence: (1, (-4, 4))
    Référence: (1, (-8, 8))
    Littéral:  (0, '\n')
    Référence: (1, (-5, 4))
    Littéral:  (0, '#######')
    Référence: (1, (-17, 8))
    Littéral:  (0, '##@@@@@@@')
    Référence: (1, (-19, 5))
    Littéral:  (0, '\n')
    Référence: (1, (-16, 4))
    Littéral:  (0, 'OOOOOOO')
    Référence: (1, (-18, 5))
    Littéral:  (0, '\n.#@OoooooooO@')
    Référence: (1, (-17, 4))
    Référence: (1, (-16, 10))
    Référence: (1, (-18, 6))
    Référence: (1, (-17, 17))
    Référence: (1, (-34, 34))
    Référence: (1, (-34, 34))
    Littéral:  (0, '\n.')
    Référence: (1, (-18, 10))
    Référence: (1, (-16, 4))
    Référence: (1, (-17, 4))
    Littéral:  (0, '#@OOOOOOO@#')
    Référence: (1, (-17, 5))
    Référence: (1, (-18, 4))
    Littéral:  (0, '@@@@@')
    Référence: (1, (-16, 5))
    Référence: (1, (-17, 4))
    Référence: (1, (-19, 4))
    Littéral:  (0, '###')
    Référence: (1, (-15, 5))
    Référence: (1, (-17, 7))
    Référence: (1, (-10, 5))
    Référence: (1, (-7, 7))
  

  Ce qui donne une entrée de 272 éléments (256 éléments plus les retours chariots) compressée en 156 éléments, soit environ 57% de la taille initiale.

  C'est légèrement moins bien que la méthode RLE pour ce cas qui avait été construit spécialement pour que ça fonctionne bien en RLE. Donc... ce n'est pas mal du tout (et on a les retours chariots en bonus).

  Peut-on faire mieux ?

  Comme la dernière fois, pour le moment, on a une implémentation assez générique que l'on compte en éléments. Si on considère que ces éléments sont en fait des octets, il y a beaucoup de place perdue, ne serait-ce que par l'utilisation d'un octet complet pour différencier les littéraux des références.

  De même, on peut se poser la question de l'utilisation d'un octet complet pour la position et la longueur dans les références, alors que les plus grandes valeurs absolues utilisées dans cet exemple sont 34. On pourrait limiter ces valeurs à 4 bits chacun pour coder les deux valeurs sur un seul octet.

  J'ai fait l'essai... et ce n'est pas brillant. La compression est alors assez mauvaise, passant alors à un résultat compressé de 225 octets.

  Par contre, en utilisant une valeur maximale de 32, alors on retrouve le taux de compression précédente.

  Mais plus que la valeur maximale, il est intéressant de s'intéresser à la répartition des valeurs utilisées.

  Grâce à un petit programme d'analyse, voici ce que j'obtiens pour cet exemple :

  Distribution des longueurs de référence:
    Valeur | Occurrences | Histogramme
    -------|-------------|------------
         4 |           9 | #########
         5 |           6 | ######
         6 |           1 | #
         7 |           2 | ##
         8 |           2 | ##
        10 |           2 | ##
        17 |           1 | #
        34 |           2 | ##
    Statistiques: Min=4, Max=34, Moyenne=8.28, Médiane=5.0
  
  Distribution des positions de référence (valeurs absolues):
    Valeur | Occurrences | Histogramme
    -------|-------------|------------
         4 |           1 | #
         5 |           1 | #
         7 |           1 | #
         8 |           1 | #
        10 |           1 | #
        15 |           1 | #
        16 |           4 | ####
        17 |           7 | #######
        18 |           4 | ####
        19 |           2 | ##
        34 |           2 | ##
    Statistiques: Min=4, Max=34, Moyenne=16.40, Médiane=17.0
  
  Distribution combinée (longueurs + positions):
    Valeur | Occurrences | Histogramme
    -------|-------------|------------
         4 |          10 | ##########
         5 |           7 | #######
         6 |           1 | #
         7 |           3 | ###
         8 |           3 | ###
        10 |           3 | ###
        15 |           1 | #
        16 |           4 | ####
        17 |           8 | ########
        18 |           4 | ####
        19 |           2 | ##
        34 |           4 | ####
    Statistiques: Min=4, Max=34, Moyenne=12.34, Médiane=10.0
  

  On peut remarquer que même si l'amplitude des valeurs est grande (de 4 à 34), la moitié des valeurs utilisées sont plutôt petites (entre 4 et 10), et la moyenne n'est pas très élevée non plus. Est-ce que ça ne vaudrait pas le coup d'utiliser un codage variable pour ces valeurs, afin de privilégier les petites valeurs ?

  C'est sur cette piste que part l'algorithme ZX0, que nous verrons dans un prochain article.

  À noter que une piste est possible en calculant une représentation des valeurs adaptée à leurs distributions. Pour cela, on peut utiliser un codage de Huffman, et c'est la piste utilisée par l'algorithme DEFLATE (utilisé dans les fichiers ZIP et PNG entre autres).

  Conclusion

  Avec cette méthode de compression par références dans un dictionnaire construit, il est possible de compresser des flux de données avec beaucoup plus de variations qu'avec la méthode RLE. LZ est en fait la base de beaucoup d'algorithmes de compression sans pertes. Le temps de compression est « élevé » car il est nécessaire de chercher des motifs dans des plages de données (la recherche peut d'ailleurs être paramétrée selon ce que l'on veut). La décompression est en revanche assez rapide, il n'y a pas de calculs ou d'opérations complexes à faire.

  Supplément

  Le code que j'ai utilisé lors de l'écriture pour vérifier les exemples est disponible ici.

  ---

• Briques Stellaires, jeu pour PHC-25 (2025-10-12)

  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. Je le regretterai plus d'une fois, quand il m'a fallu mettre au point la routine de rebond. Mais comme je savais que cela serait potentiellement compliqué avec des regressions très probables, j'ai cherché dès le début un environnement me permettant de faire des tests unitaires.

  J'avais déjà mis en place des tests unitaires pour le jeu sur VG5000, cependant, ils devaient être lancés en même temps que l'exécutable principal. Puis c'était un bricolage rapide qui manquait de fonctionnalités.

  Je suis donc parti sur un environnement déjà fait : DeZog. C'est un environnement intégré à Visual Code, initialement fait et spécialisé pour le ZX Spectrum, mais qui peut être utilisé comme environnement Z80 générique. DeZog supporte l'exécution de tests unitaires, avec de nombreuses assertions, le tout pouvant tourner dans un émulateur interne.

  DeZog implémente aussi un lien de debuggage avec différents émulateurs, dont MAME. Parfait pour la mise au point.

  Les choix pour le PHC-25

  Il y a plusieurs modes graphiques sur le PHC-25, qui utilise comme VDP un clone du MC6847 avec le maximum de RAM vidéo supportée. On peut considérer qu'il y a deux grandes classes de modes graphiques : des modes alpha-numérique/semi-graphique, et des modes bitmap, avec des variations dans les contraintes.

  Pour le jeu, j'ai choisi un mode alpha-numérique/semi-graphique qui permet d'avoir une résolution en « gros pixels » de 68x48. C'est suffisant pour un casse-brique.

  Pas de son ni de joystick, car le PHC-25 a besoin d'une extension pour cela. Et puis... le temps, toujours le temps.

  Liste d'affichage

  Sur le PHC-25, le MC6847 utilise pour RAM vidéo une mémoire directement accessible par le bus du Z80. Et lorsqu'il y a arbitrage, c'est le Z80 qui gagne. Ainsi, des accès à la mémoire vidéo pendant le rafraîchissement de l'écran provoquent des parasites bien visibles.

  Il faut donc absolument éviter d'accéder à la mémoire vidéo pendant le rafraîchissement. C'est d'ailleurs ce que fait la ROM du PHC-25 où les commandes graphiques sont appliquées progressivement pendant l'interruption (INT), branchée sur VBLANK.

  Et c'est aussi ce que je fais dans Briques Stellaires. Après avoir passé le Z80 en mode d'interruption IM2 (il n'y a pas de possibilité prévue par le système pour s'accrocher à l'interruption en IM1), je déroule des listes d'affichages au moment de l'interruption. Ces listes d'affichages sont elles-mêmes construites pendant le reste du temps, par des accès en RAM normale exclusivement.

  Ces listes d'affichages sont de type : afficher une brique, effacer une brique, effacer et afficher la balle,...

  Le traitement de l'affichage du contour de jeu ainsi que des pages de titre et de score est un peu différent : je prépare l'affichage dans un buffer auxiliaire de la taille de l'écran, puis je copie ce buffer en RAM vidéo pendant le VBLANK, petit à petit.

  L'affichage de la raquette est similaire : il est fait dans le buffer auxiliaire, puis la ligne correspondante est copiée en RAM vidéo pendant le VBLANK systématiquement. C'est un choix que j'ai fait assez tôt car je ne savais pas trop à quelle vitesse la raquette allait bouger et je voulais un système simple, avec un temps fixe pendant la VBLANK.

  La physique

  Voilà qui m'a pris plus de temps que prévu. Je savais que cela allait être délicat, avec des rebonds particuliers et des vitesses non entières. En effet, les coordonnées de la balle sont en virgule fixe, 8 bits pour la partie entière, 8 bits pour la partie fractionnaire. Là encore, c'est un choix que j'ai fait assez tôt, car je ne savais pas quelle vitesse de balle allait être intéressante. Et avec la résolution de l'écran, des vitesses entières allaient donner des mouvements bien trop rapides.

  Pour les collisions, je trace une ligne entre la position précédente et la position actuelle de la balle, point par point, en testant les collisions avec les briques, la raquette et les bords. La ligne ne fait rarement plus de deux pixels, mais là encore, cela permet de gérer différentes vitesses, donc des vitesses supérieures à 1 par axe.

  Par contre, j'ai simplifié : une collision arrête immédiatement la trajectoire. Je ne cherche pas à compléter le mouvement restant après le rebond. Aux vitesses utilisées au final par le jeu, la différence est imperceptible.

  La gestion de variables

  Puisque le jeu est sur cassette, il est toujours intéressant de minimiser la taille des données encodées. Pour gagner de la place, j'ai implémenté avec le système de STRUCT et de macros de sasmjsplus qui permet de « déclarer » des variables près du code, mais qui sont toutes regroupées à la fin du code lors de l'assemblage.

  Au démarrage du programme, je fixe toute la zone à zéro. Un peu à la manière d'une section BSS dans un programme C.

  J'avais envisagé d'utiliser un système de compression, surtout pour les niveaux. Mais le manque de temps et finalement la taille relativement modeste du programme (moins de 3ko) m'ont fait abandonner cette idée.

  Conclusion

  Briques Stellaires est un casse-brique très rudimentaire. Et autant que je puisse m'en souvenir, c'est la première fois que je programme un casse-brique. Je me suis perdu dans la gestion de collisions et malgré les tests unitaires qui m'ont gardé sur les rails, j'y ai passé beaucoup de temps. Un peu avant la date limite de la jam, j'ai coupé dans toutes mes idées un peu originales pour me concentrer sur l'essentiel : un jeu auquel on peut jouer.

  

  ---

• Compression de données, compter les répétitions (2025-07-28)

  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 :

  ................
  ....#######.....
  ..##@@@@@@@##...
  .##@OOOOOOO@##..
  .#@OoooooooO@#..
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  .#@OoooooooO@#..
  .##@OOOOOOO@##..
  ..##@@@@@@@##...
  ....#######.....
  ................
  

  Les niveaux de gris sont représentés par des caractères, et chaque caractère représente un pixel de l'image. L'image est de 16 lignes et 16 colonnes, soit 256 éléments. Ne nous occupons pas pour le moment de comment coder ces éléments. Ce sont juste des éléments.

  L'idée générale

  L'idée de la compression RLE vient de la constatation rapide qu'il existe des suites de données identiques dans les données, et que l'on peut même facilement énoncer. Par exemple, sur la première ligne, on peut dire qu'il y a 16 fois la valeur .. Sur la deuxième ligne, on peut dire qu'il y a 4 fois la valeur . puis 7 fois la valeur # puis 5 fois la valeur .. Et ainsi de suite.

  C'est le principe de la compression RLE : on va remplacer les suites d'éléments identiques par deux éléments : le nombre de répétitions et la valeur répétée. Par exemple, la première ligne devient (16, '.'), la deuxième ligne devient (4, '.'), (7, '#'), (5, '.').

  Voilà ce que cela donne pour l'image complète, si on met toutes les lignes bout à bout (sans les sauts de ligne) :

  (20,.), (7,#), (7,.), (2,#), (7,@), (2,#), (4,.), (2,#), (1,@), (7,O), (1,@), (2,#), (3,.), (1,#), (1,@), (1,O), (7,o), (1,O), (1,@), (1,#), (2,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (2,.), (1,#), (1,@), (1,O), (7,o), (1,O), (1,@), (1,#), (3,.), (2,#), (1,@), (7,O), (1,@), (2,#), (4,.), (2,#), (7,@), (2,#), (7,.), (7,#), (21,.)
  

  Ce qui donne 89 couples de valeurs, soit 178 éléments au total. Contre 256 éléments dans l'image d'origine. On a donc bien réduit le nombre d'éléments nécessaires pour représenter l'image.

  Mais attention, ce qui permet la réduction, ce sont les suites de même valeur.

  Si les données sont constituées de valeurs souvent changeantes, la compression ne va pas bien fonctionner, voire donner plus d´éléments en sortie. Par exemple, si l'image n’était constituée que de valeurs différentes de leurs précédentes, on devrait à chaque fois écrire (1, élément), et donc au final doubler le nombre d'éléments nécessaires. Pas très efficace.

  Codage du flux compressé

  Jusqu'à maintenant, on n'a parlé que d'éléments. Cependant, ces éléments doivent être codés d'une manière ou d'une autre pour être stockés sur la machine. Par exemple, on peut considérer assez facilement que le flux d'entrée est codé en caractères sur 8 bits. C'est trop pour 4 valeurs différentes (2 bits sont suffisants), mais on peut imaginer avoir d'autres valeurs sur les 256 possibles dans d'autres images.

  On va donc garder cette représentation en 8 bits pour les éléments valeurs. Même en sortie.

  Pour le nombre de répétitions, il faut faire un choix sur le plus grand nombre de répétitions possibles. Ces choix vont dépendre de la nature des données. Pour un premier choix, on va faire simple : 256 répétition maximum. Une image de 16x16 éléments monochrome serait donc codée par deux valeurs en 8 bits : (0, valeur). En effet, comme une répétition de 0 n'a pas de sens, on se sert du 0 pour coder 256.

  Deux octets au lieu de 256, c'est pas mal. Mais on peut aussi imaginer que les images monochromes ne sont pas représentatives.

  En prenant un octet pour les répétitions et un octet pour la valeur, le codage et le décodage sont très simples et la taille pour l'image exemple est de 178 octets, soit 178 octets pour 256 éléments.

  Peut-on faire mieux ?

  Oui. Il y a plusieurs manières différentes de coder un flux compressé RLE. La méthode indiquée précédemment est la plus simple. Mais on peut en imaginer d'autres.

  Par exemple, on peut réserver une plage de nombres dans l'indication des répétitions pour indiquer un nombre d'octets à suivre qui seront recopiés tels quels (parce qu'ils ne présentaient pas de répétition en entrée).

  Par exemple, sur un morceau en entrée comme :

  ....#.#.#.....
  

  On code les valeurs

  (r4, '.'), (c5, '#.#.#'), (r3, '.')
  

  Où r signifie "répétition" et c signifie "copie".

  D'un point de vue codage, on peut choisir que les valeurs 0 à 127 représentent des répétitions, et les valeurs 128 à 255 représentent des copies.

  Voilà ce que cela donne pour l'image complète avec cette méthode :

  (20,.), (7,#), (7,.), (2,#), (7,@), (2,#), (4,.), (2,#), (129,@), (7,O), (129,@), (2,#), (3,.), (131,#@O), (7,o), (131,O@#), (2,.), (131,#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (131,O@#), (2,.), (131,#@O), (7,o), (131,O@#), (3,.), (2,#), (129,@), (7,O), (129,@), (2,#), (4,.), (2,#), (7,@), (2,#), (7,.), (7,#), (21,.)
  

  47 éléments au lieu de 89. Des éléments de taille variable cependant. Ici la taille en octets est de 136 plutôt que 178. Ce qui est un nouveau gain (au prix d'une toute petite complexité supplémentaire à traiter à la décompression)

  Peut-on faire encore mieux ?

  Vous pouvez trouver d'autres manières de coder un flux compressé RLE. En fonction de la plateforme, de la nature des données, de la taille des éléments, etc, il est possible de trouver des ajustements et des variations qui permettent de gagner de la place.

  Conclusion

  La compression RLE est une méthode simple à comprendre et à implémenter. Le temps de compression et de décompression sont très rapides car les calculs sont très simples.

  Elle peut donner de bons résultats sur des données avec beaucoup de plages de même valeur. C'est aussi une méthode non destructive : une fois décompressées, les données sont identiques à l'original avant compression.

  Dans un prochain article, nous verrons une autre méthode de compression classique et qui fonctionne bien sur des répétitions de motifs.

  Supplément

  Le code que j'ai utilisé lors de l'écriture pour vérifier les exemples est disponible ici.

  ---

• PHC-25, et Z80 en IM 2 (2025-06-09)

  Ça y est, la nouvelle saison des Retro Programmers United for Obscure System a démarré. Et cette fois, c'est le PHC-25 qui est à l'honneur. Un ordinateur de Sanyo à base de Z80 (d'un clone plus précisément) et d'un MC6845 (... un clone aussi) et plutôt bien fourni en mémoire vive pour cette classe de machines : 16 ko de RAM et 6 ko pour la VRAM, accessible directement par le Z80 (avec des contraintes de timing si on veut éviter des parasites graphiques).

  Bien entendu, comme toutes les machines concernées par cette game jam, le PHC-25 est un ordinateur qui n'a pas une grande logithèque, et pas non plus beaucoup d'activité ni de documentation. C'est le principe.

  Pour cette Jam, je suis parti sur l'idée que le programme sera en assembleur. Certains vont certainement encore faire des miracles en BASIC, mais ce n'est pas ma tasse de thé, même si je l'ai enté par le passé. Avec la communauté des participants, nous nous sommes donc penchés sur la compréhension de la machine. Pas facile là encore car nous ne sommes pas nombreux à avoir un PHC-25, il faut donc continuellement passer par les bonnes âmes qui peuvent lancer nos tests.

  Après quelques jours, j'ai commencé à mettre mes notes, un programme d'exemple et une manière de packager un programme assembleur sur gitlab. C'est principalement le résultat d'un travail de recherche collectif.

  J'ai pu aussi corriger deux petits trucs dans MAME, qui reste loin d'être parfait pour le PHC-25, mais qui est un tout petit peu mieux qu'il y a deux semaines. La machine reste assez simple et peu exotique par rapport à d'autres que l'on a traitées auparavant.

  IM 2

  Lors de nos discussions et analyse, il est apparu que la ROM du PHC-25 lançait une ISR (Interrupt Service Routine) à chaque synchronisation verticale. C'est classique. Pendant cette ISR, la ROM fait les modifications en VRAM en fonction des modifications d'affichages demandées par le BASIC, cela pour éviter les parasites graphiques. Il y a aussi une lecture du clavier, la gestion du son,...

  Mais aucune possibilité de reroutage. Là où l'on trouve dans d'autres machines un « hook » sur lequel on peut attacher son propre code, ici, il n'y a rien.

  La proposition a été faite de passer le Z80 en IM 2, afin de gérer entièrement l'interruption. Cela fonctionne, et ce que je vais expliquer ici. À noter que l'IM 2 est une fonctionnalité du Z80 et que la grande partie de ce qui suit est valable pour d'autres machines similaires à base de Z80.

  Interrupt Mode ?

  Le Z80 peut fonctionner selon trois modes d'interruption. Le mode 0 est le mode par défaut. C'est un mode reliquat du 8080. Dans ce mode, lorsque l'interruption est reçue, le Z80 va lire l'instruction suivante qui va lui être présentée depuis un mécanisme externe. Généralement, c'est une instruction RST qui est utilisée, afin de brancher à l'une des routines RESTART du Z80.

  Mais la plupart, si ce n'est toutes, des machines familiales à base de Z80 utilisent le mode 1, qui est beaucoup plus simple. Dans ce mode, lorsque l'interruption est reçue, le Z80 branche tout simplement à l'adresse fixe 0x0038, à partir de laquelle on place l'ISR. C'est ce que fait le PHC-25. Mais comme son ISR n'offre pas de moyen d'extension, on est vite limité si on veut prendre les choses en main.

  Le mode 2, ou IM 2, est un mode qui est normalement fait pour être utilisé avec un contrôleur d'interruption externe. Dans ce mode, l'interruption est suivie d'une valeur paire sur 8 bits. Cette valeur est utilisée comme index dans une table d'adresses d'ISRs. Le Z80 va lire l'adresse de l'ISR à partir de cette table, puis il va brancher à cette adresse.

  Cependant, le PHC-25 n'a pas de contrôleur d'interruption externe. Ainsi, la valeur reçue peut être un peu n'importe quoi (et même pas forcément paire). L'astuce consiste donc à utiliser une table dont toutes les entrées pointent vers la même adresse. Comme l'index peut-être paire ou impaire, cela implique une contrainte supplémentaire : l'adresse de l'ISR doit être composée de deux octets identiques ($FEFE par exemple). Autre petit piège, comme la valeur 255 peut-être reçue, la table doit contenir 257 octets, et non pas 256 uniquement.

  En pratique

  Voici le code commenté pour mettre en place l'IM 2 sur le PHC-25 :

      ; Code pour l'assembleur SjASMPlus
  
      org $c009   ; Adresse de départ du programme.
                  ; On commence à $C009, car c'est l'adresse de départ
                  ; avec le chargeur BASIC utilisé. Mais vous pouvez
                  ; adapter.
  
  start:
      call install_im2    ; Le programme démarre par l'installation de l'IM 2
  
  infinite_loop:
      halt                ; Attente de l'interruption
      jp infinite_loop    ; Puis boucle
  
  
      ; Installation de l'IM 2
  install_im2:
      di      ; On commence par désactiver les interruptions
              ; Comme on va modifier la configuration,
              ; on ne veut pas qu'elles se déclenchent pendant ce temps
  
  
      ; Déplace la pile
      ; Peut-être optionnel, mais comme ça, on sait où elle est
      ; On ne pourra pas retourner dans la ROM, mais de toute façon
      ; elle ne fonctionnerait pas en IM2.
      pop hl                  ; sauve l'adresse de retour de la routine
      ld  sp,$fffe            ; place la pile à $FFFE
      push hl                 ; Pousse l'adresse de retour sur la pile
                              ; À présent, le RET peut retourner à l'endroit de l'appel
  
  
      ; Remplit la table des vecteurs d'interruption
      ld      hl,$fe00        ; La table démarre en $FE00
      ld      e,l
      ld      d,h
      inc     de              ; Idiome de remplissage de mémoire
      ld      bc,257          ; De longueur 257 octets
      ld      a,$fd           ; Contenant l'adresse $fdfd
      ld      (hl),a
      ldir                    ; Remplissage de mémoire
  
      ; On place un saut vers l'ISR dans le vecteur d'interruption
      ld      hl,$fdfd        ; L'adresse du vecteur
      ld      a,$c3           ; Instruction de saut (JP) vers xxxx
      ld      (hl),a
      inc     hl
      ld      de,isr          ; L'adresse de l'ISR
      ld      (hl),e
      inc     hl
      ld      (hl),d          ; Met l'adresse de l'ISR après l'instruction JP
  
      ; Place la table des vecteurs d'interruption ($FExx)
      ld      a,$fe
      ld      i,a             ; Met l'adresse haute à $FE
      im      2               ; Commute en Mode d'Interruption 2
  
      ; All set
      ei                      ; Réactive les interruptions
      ret
  
  char:
      db      32
  
      ; Routine de service d'interruption
      ; Appelée au début de la synchronisation verticale
      ; Affiche un caractère en haut à gauche de l'écran
      ; (en mode SCREEN 1)
  isr:
      ld      hl,char
      ld      a,(hl)
      inc     (hl)
      ld      hl,$6000
      ld      (hl),a
      ei
      reti
  

  ---

Page 1 / 24 (suivant) »