Memory Full

Shrinkler

Written by Roudoudou in March 2018

Le Shrinkler est un compresseur créé sur Amiga en 2014 par Blueberry (un demomaker du groupe Loonies) afin de compresser au maximum des programmes de petite taille. Ce compresseur est-il un candidat idéal pour de prochaines productions sur CPC, c'est ce que nous allons voir plus en détail dans cet article.

Présentation du Shrinkler
Il existe assez peu d'algorithmes de compression sur Amstrad. Les plus populaires et les plus performants sont des dérivés du LZ, parfois mélangé avec du RLE pour les répétitions. Pour rappel, une clef LZ indique une séquence précédemment décompressée à répéter par une longueur et un offset. Certains algorithmes gèrent plusieurs types de clefs afin de réutiliser un offset ou une longueur.

Les différences de performances entre compresseurs tiennent surtout de la façon dont sont enregistrées les clefs LZ. Le stockage de ces clefs peut se faire de façon alignée pour LZ48, semi-alignée pour ZX7 à purement variable pour Exomizer. L'intérêt de ne pas aligner les données est évidemment de gagner en compression, au prix d'une lenteur accrue car il faut gérer les informations bit à bit. La compression de données non alignées et variables ajoute l'obligation d'utiliser une machine plus puissante avec beaucoup de mémoire et de puissance processeur. En effet, les formats non alignés utilisant des longueurs variables de bits pour leur codage, le compresseur possède une phase d'optimisation où il va tester toutes les combinaisons possibles afin éventuellement de reculer pour mieux sauter et augmenter la densité d'information.

Un petit tableau indicatif de vitesse/ratio entre ces trois types de compresseurs et Shrinkler (le fichier utilisé est l'exécutable de Boulder Dash, en référence à des tests précédents qui l'utilisaient) :

Type de compressionTailleVitesse décompression
RAW (pas de compression)28709x 1.0 (référence)
LZ413987x 1.5
ZX711651x 4.3
Exomizer11026x 14.4
Shrinkler10092x 300



Jusqu'à présent, Exomizer avait détrôné tous les autres en ratio de compression, ce qui le rendait incontournable dès lors qu'on n'avait pas besoin de rapidité. Le format est très optimisé et je reconnais m'être cassé les dents en essayant différentes solutions de stockage LZ inspirées du LZMA de 7-zip, c'est-à-dire en conservant un historique des dernières clefs pour éventuellement en reprendre le motif. Il ne restait pas beaucoup de solutions pour détrôner Exomizer autre que la compression arithmétique ou les réseaux de neurones. Comme je pense que Madram s'occupe déjà d'une prochaine version de CPC_T en réseaux de neurones, il ne me restait que la compression arithmétique. Arrive alors Beb sur le forum de cpcwiki qui ouvre un sujet "cruncher request" à propos du Shrinkler. "Est-ce que quelqu'un s'est déjà penché dessus ? "

Le Shrinkler est un cruncher Amiga pour processeur 68000 et Blueberry -l'auteur du cruncher- décrit lui même le Shrinkler comme une version striped-down (allégée) du LZMA dont je parlais plus haut. D'après Wikipedia, l'acronyme LZMA veut dire Lempel–Ziv–Markov Algorithm, ce qu'est déjà Exomizer en fait mais la réelle supériorité du LZMA dont est dérivé le Shrinkler tient surtout dans la compression arithmétique de son flux de bits qui lui donne en pratique des résultats de compression excellents.

Pourquoi alléger le format de compression s'il est très bon ? Tout d'abord, contrairement aux systèmes modernes, les décompresseurs ne s'installent pas sur un système, il faut l'embarquer dans l'exécutable pour le rendre auto-extractible. Et comme le Shrinkler se destine aux petits fichiers, il aurait été contreproductif de gérer tous les cas de figure du LZMA car cela aurait augmenté la taille du décompresseur, mais aussi celle du flux de bits, avec à la clef une probable perte de compression.

La compression arithmétique
En théorie, la compression arithmétique utilise un intervalle de travail et une probabilité par symbole. En pratique cette méthode est trop complexe car il faut modifier autant de probabilités et d'intervalles que de symboles. De plus, soit il faut stocker ce tableau dans le fichier compressé -ce qui s'avère volumineux- soit il faut initialiser ce tableau avec une valeur moyenne et mettre à jour tous les symboles à chaque itération, ce qui s'avère cette fois beaucoup trop complexe pour nos ordinateurs limités en puissance et en mémoire.

SymboleProbabilitéIntervalle
F1/4[0:0.25[
L1/4[0.25;0.5[
C1/8[0.5;0.625[
.........



Plutôt que de travailler avec des symboles (et autant d'intervalles que de symboles...), utiliser un tableau pour les deux états d'un bit est bien plus simple car comme on le voit ci-dessous, avec seulement deux valeurs, on connait déjà les bornes 0 et 1 de l'intervalle, ne reste que le pivot comme valeur commune.

Bit nProbabilitéIntervalle
01/4[0;0.25[
13/4[0.25;1[



Ce qui se simplifie pour chaque bit par une seule valeur, la valeur pivot.

Bit nProba 0Pivot
1/40.25



Afin de rendre performante la prédiction des bits, le Shrinkler utilise une centaine de contextes. Un contexte pour chaque numéro de bit dans un symbole, une longueur de clef ou un offset de clef. Le Shrinkler est d'autant plus adapté à la compression 68000 qu'il intègre un contexte en fonction de la parité mémoire. En effet, le 68000 ne sait pas exécuter un opcode sur une adresse impaire, c'est pourquoi les adresses paires contiendront toujours les racines des opcodes tandis que les adresses impaires auront plutôt des valeurs litérales (pour simplifier). La conséquence directe est une amélioration des statistiques sur les adresses paires. Bien que nous ne profitions pas de ce raffinement en compressant du code Z80, la prédiction des bits reste bonne puisque pour rappel, on peut espérer un gain de compression d'environ 10% rapport à Exomizer.

Lorsqu'on compresse un fichier, les clefs LZ sont souvent de petite longueur et exceptionnellement longues. Donc quand elles sont de petites longueur, le flux de bits est très prédictif, tandis que quand la clef est longue on se moque d'une mauvaise prédiction car une longue clef fait gagner beaucoup d'octets. L'optimiseur se chargeant d'harmoniser au possible ces valeurs (via un calcul brutal) pour améliorer encore un peu plus la prédiction.

Adapter du code 68000 au Z80
Je n'avais jamais fait de 68000 jusqu'à maintenant. Ce que j'en connaissais se résumait à : plus de registres. En même temps, il y a rarement des instructions assembleurs tordues sur les vieux CPU, les instructions SIMD (instructions simples à données multiples) n'existaient pas encore dans ces processeurs. Restait quand même à trouver de la doc 68000. Je ne vous cache pas la galère. Je tombe sur quelques écrits de demomakers. Horribles. Du style "l'assembleur ça se mérite, on ne va pas vous l'expliquer tout cru" ou "Je suis nul en pédagogie mais je vais essayer de faire passer ça pour de l'élitisme". Je me console alors sur de la doc technique pure à peine meilleure. Certaines syntaxes sont curieuses comme les branchements conditionnels qui ont tous des noms différents en fonction du type de saut. Si ces syntaxes sont claires une fois qu'on a lu la documentation, laquelle choisir pour tomber sur la doc ? Ah ! Ah ! Bien évidemment, aucun ne renvoie de résultat avec un moteur de recherche, il faut en fait utiliser un mot clef qui n'est pas une instruction assembleur. Consternant. Heureusement, le jeu d'instruction est très basique et le code de Blueberry est simple à lire. Je localise rapidement la verrue destinée à appeler une barre de progression, ainsi que les sauvegardes habituelles de registres pour être appelé depuis système. Je dégage aussi la réservation d'espace mémoire dans la pile car sur CPC je fais d'emblée le choix d'un buffer statique, plus simple à mettre en oeuvre.

La difficulté de porter un code 68000 sur Z80 tient en deux points :
- le Z80 a moins de registre, il faudra donc certainement utiliser des variables en mémoire.
- le Z80 travaille au maximum sur 16 bits. Il faudra donc décomposer les instructions 32 bits.

En analysant un peu l'algorithme, je me suis rendu compte qu'il n'y avait heureusement qu'un seul registre pleinement utilisé en 32 bits. Tout le reste des opérations se contentait de 16 bits. Il y avait bien la longueur de clef LZ à recopier mais nous savons déjà que dans notre cas (avec un espace mémoire de 64K maximum), cette longueur ne sera jamais supérieure à 16 bits. Donc sa traduction en Z80 peut se limiter à 16 bits.

Je commence donc à convertir de façon brute le code. L'idée est d'avoir un code fonctionnel en premier lieu. Des variables pour chaque registre, une routine pour la multiplication qui n'existe pas sur Z80. Il y a rapidement des choses qu'il devient évident de ne pas traduire. En effet, le 68000 n'est pas capable, par exemple, d'accéder directement aux 8 bits de poids fort d'un registre. Il lui faut décaler le registre de 8 bits. Idem pour récupérer les 16 bits forts d'un registre 32 bits après une multiplication. Dans notre cas, la multiplication utilisant deux registres 16 bits pour le résultat, il suffit d'utiliser directement ce registre sans s'occuper de l'autre...

Notre bon vieux Z80 n'est pas particulièrement doué quand il s'agit d'indexer des valeurs dans un tableau. En général on s'en sort en faisant coïncider nos valeurs avec un tableau de 256 cases. Ainsi, il suffit de modifier le poids faible de l'adresse du tableau pour récupérer notre valeur. Et si on veut stocker des valeurs 16 bits, il n'y a qu'à incrémenter l'octet de poids fort pour récupérer nos données.

De son côté, le 68000 dispose d'une super incrémentation qui s'applique indifféremment aux registres 8, 16 ou 32 bits et cerise sur le gâteau, avec une valeur de 1 à 8 ! Son temps d'exécution est aussi le même que l'on soit en 8 bits ou en 16 bits. Cette instruction porte le doux nom de ADDQ pour Add Quick (Addition rapide). Malheureusement pour nous, l'algorithme du Shrinkler a besoin d'indexer sur 3000 octets pour les probabilités. Le trick de l'offset 8 bits ne pourra pas s'appliquer. Par contre, pour nous éviter une addition de trop, il est beaucoup plus simple de localiser le tableau des probabilités à un emplacement statique plutôt que réserver de l'espace dans la pile, ce que j'avais pressenti avant même d'écrire la première ligne de code.

Pour son calcul d'adresse, le Motorola utilise une instruction qui n'existe pas sur Z80, le chargement d'adresse effective avec l'instruction LEA (load effective adress) :

En assembleur 68000 :

      lea.l 4+SINGLE_BIT_CONTEXTS*2(a7,d6.l),a1 ; a1 = d6+a7+4+single*2
      add.l d6,a1                               ; a1 = a1 + d6


En assembleur x86 on pourrait l'écrire en une seule instruction:

      lea esi,[4+SINGLE_BIT_CONTEXTS*2+eax*2+ebx] ; esi = eax*2+ebx+4+single*2


Et en basic

a1=a7+d6+4+SINGLE_BIT_CONTEXTS*2 
a1=a1+d6


Dans notre cas, nous le traduirons par:

      ld  hl,d6
      add hl,hl
      ld  de,2+tableau_proba ; +2 pour ajuster l'offset à partir du premier
                             ; contexte qui est négatif pour ne pas se retrouver
                             ; avant le tableau
      add hl,de


Le reste du code 68000 est assez similaire à ce que nous avons l'habitude de pratiquer sur Z80, les instructions de branchement ont simplement d'autres noms et le principe des conditions est identique.

Après quelques simulations conjointes avec des émulateurs 68000 et Z80, je débusque les derniers bugs (principalement des retenues mal propagées) et obtient enfin une version fonctionnelle. Mon code n'utilise pas encore le jeu de registres secondaires, c'est volontaire car je sais qu'il est préférable de le garder sous le coude pour une grosse optimisation, mais pour cela, il faut s'imprégner un peu plus de l'algorithme !

À force de lire et relire mon code, je réalise quelques optimisations de taille pour gagner des octets. Le décompresseur est encore gros, il faut le rendre compétitif rapport à Exomizer sur de petits fichiers. Je diffuse rapidement le source sur cpcwiki. Cela fait bien longtemps que le record de compression (et de lenteur) est tenu par Exomizer aussi l'arrivée d'un nouveau cruncher plus performant (et encore plus lent !) ne laisse pas indifférent.

Factorisation de code
Contrairement au 68000 qui peut faire (par exemple) des décalages multiples ou une multiplication en une seule instruction, nous sommes obligés de décomposer ces instructions complexes en instructions plus simples, avec une boucle. J'étais passablement embêté car en sortie de chacune de mes boucles, j'avais soit une retenue toujours à 1, soit une retenue imprévisible. Et comble de malchance, j'avais besoin de faire une soustraction 16 bits à chaque fois derrière. Sachant que les soustractions 16 bits sur Z80 n'existent que sous la forme SBC, soit soustraction avec prise en compte de la retenue. Une des idées était donc de modifier les comptage des boucles pour remettre la carry à zéro à tous les coups.

Quand Antonio Villena s'en mêle
Antonio est l'une des personnes qui a le plus contribué à optimiser en taille le décompresseur Z80. Je vous présente ici quelques optimisations notables issues de la version finale.

      ld  a,(hl)
      sub 2
      ld  (hl),a
      jr  nc,label ; 6 octets au total


devient

      dec (hl)
      dec (hl)
      ret m    ; 3 octets au total, deux fois moins de place pour la même chose!


La subtilité de l'optimisation vient du fait que la valeur en (hl) qu'on décrémente est toujours paire et inférieure à 128. On ne risque pas de rater une retenue en décrémentant. Justement, la deuxième subtilité est que l'instruction DEC, contrairement au SUB, ne touche pas la retenue. Par contre le flag S est modifié. Ainsi, en guise de retenue, on peut tester le signe de la valeur qui devient négative.

La supériorité du registre HL
Le code utilise au maximum le registre HL car les opcodes de chargements ou écritures mémoire occupent 1 octet de moins que pour les registres BC, DE, IX, IY.

On peut aussi initialiser le registre HL avec une opération mathématique plutôt qu'un chargement de valeur littérale:
SBC HL,HL
Si la carry est nulle alors HL vaudra zéro
Si la carry est mise alors HL vaudra -1

Quand un opcode en vaut deux
On peut utiliser une valeur de compteur pour le rebouclage qui soit aussi un opcode mais il faut que cet opcode puisse être un multiple dont la condition finale est testable simplement.

À force de triturer le code dans tous les sens, Antonio a remarqué qu'un de ses sauts relatifs avait une valeur de -19, soit le préfixe bien connu #ED en hexadécimal. Or il se trouve qu'une addition 16 bits n'était pas loin, il n'en faut pas plus pour supprimer un octet de cette instruction et mutualiser l'adresse relative avec l'opcode d'addition.

#18 #ED LabelADC Jr  label ; saut relatif en -19
#6A              ld  l,d


En sautant à labelADC+1 on a bien l'équivalent de

#ED #6A          adc hl,hl



Optimisation du chargement mémoire
Les instructions qui utilisent les registres IX ou IY sont coûteuses en temps mais aussi en occupation mémoire. Or il se trouve qu'on ne recharge une nouvelle valeur que quand le registre DATA courant est vide. Cela implique que nos registres de traitement sont vides et la carry est toujours nulle.

      ld  e,4      ; je profite que DE soit vide pour ne toucher que e
      add ix,de    ; je pré-incrémente car je vais écraser DE de suite
      ld  e,(ix-1) 
      ld  d,(ix-2) 
      ld  l,(ix-3) 
      ld  h,(ix-4) ; 16 octets 


L'idée d'Antonio est de charger HL et DE avec les mêmes instructions, grâce à la permutation de registre EX HL,DE et à la permutation de retenue, qui fera office de compteur de valeur 2.

reload
      ld  h,(ix+0) 
      inc ix 
      ld  l,(ix+0) 
      inc ix 
      ex  hl,de 
      ccf           ; inverse la carry. Première itération, la carry est à 1,
                    ; deuxième itération à zéro et on sort 
      jr  nc,reload ; 14 octets


Voilà pour les optimisations de code les plus notables et intéressantes. Il y a eu aussi un gros travail de factorisation, en faisant du code spaghetti. L'idée majeure est de déporter le plus possible le code factorisable en fin de fonction. Ainsi d'autres fonctions peuvent sauter sur une fin de fonction commune. Le meilleur étant la condition de sortie du décompresseur qui ne fait pas de RET mais continue son exécution dans une fonction de calcul qui ne touche pas la mémoire et effectue le RET final.

Dernier mot sur les performances
Quand on parle des performances d'un cruncher, on parler souvent de vitesse pour décompresser une certaine quantité de données mais dans le cas de Shrinkler qui fait de nombreux calculs pour chaque bit lu, il est préférable de parler de vitesse par octet décodé. L'algorithme décode le flux à environ 5 secondes par kilo-octet de données crunchées, la copie des données finales étant négligeable comparée à l'interprétation du flux crunché. De fait, le cruncher est destiné à des petites productions (4K) où il faudra déjà attendre un peu moins de 20s plutôt que des productions plus grosses, sauf éventuellement si on ajoute un petit quelque chose sous interruption pour faire patienter l'utilisateur.