Memory Full

Compression de décompresseur en Auvergne

Written by Gonzague/NPS in April 2018

Salut bande de nazes et de nazis, ici Gonzague du NPS !
Portant haut l’étendard du crack de qualité, le NPS veille à ce que ses fichiers soient le mieux compressés possible, surtout vu le prix des 3" (salauds de spéculateurs).
Aussi avons-nous jeté un œil nonchalant mais attentif à la routine de décompression utilisée dans Isometrikum, démoulée un peu plus tôt par un Roudoudou aidé de quelques comparses plus ou moins recommandables [NDX : pour plus d'information sur la conception de cette routine, lisez Memory Full!].


Nul (ha) besoin de s'y connaître en compression arithmétique pour déceler tout de go que l'entrée est lue comme une queue de bits, égrenés un à un de gauche à droite suivez mon regard, pas comme chez les mahométans.
Pour se faire en pratique, un simple décalage logique à gauche réitéré sur l'octet courant conviendra. Reste à savoir quand passer à l'octet suivant. Ben oui, octuple buse, quand l'octet est à zéro, comment déterminer s'il a été épuisé ou s'il s'agit de bits 0 à consommer ? La solution de bourrin, en vogue dans les années z80, consiste à adjoindre un compteur. Comme si les registres poussaient sur les arbres.
Amslive (15 de mémoire [NDX : page &0c très exactement]) donne l'astuce suivante :

  • SL1 A pour obtenir le premier bit. On insert subrepticement un 1 à droite qui servira de marqueur, ou sentinelle, ou endive.
  • [NDX : en vieux français, SLL est parfois mis pour SL1. Cependant, SL1 n'est pas le symétrique de SRL comme SLA l'est de SRA : SRL introduit un bit 0 à gauche, alors que SL1 glisse un bit 1 à droite. C'est pourquoi il est préférable d'écrire par convention SL1 au lieu de SLL (ce que fait Orgams).]
  • ADD A pour obtenir les bits suivants. L'octet passe à zéro uniquement quand notre sentinelle échoie dans la CARRY, ce qui indique via le drapeau Z que la réserve de bits est à sec, pour parler comme Aragon.

C'est exactement le principe à l’œuvre dans la version 68000, à ceci près qu'on lit 32 bits d'un coup avant de passer aux suivants. Simplement parce que leurs registres travaillent sur 32 bits et/ou que cela fait plus de sens en terme d'accès mémoire. Mon pote suggère que c'est à cause de l'architecture MILF, mais il n'y connaît rien et ne se lave même pas les mains avant les repas.
Il faut avoir les yeux trop en face des trous pour conserver une telle gestion sur notre petit Z80.

En outre, la version Z80 sauvegardait outrageusement le drapeau Carry, alors qu'une rapide analyse montre qu'il était nécessairement mis dans cette branche.
Cela illustre d'ailleurs un principe générique d'optimisation : chercher si certaines conditions se trouvent systématiquement remplies (par construction ou pour un fichier donnée), de sorte à ne plus avoir à les tester ou pire, gérer un cas particulier qui ne se produira jamais.

Une complémentaire contraction connue et conséquente consiste à conserver le maximum de variables dans les registres, plutôt que de les manipuler en mémoire.
Cela tant que les acrobaties nécessaires ne contrebalancent pas les gains.
Ainsi, D2 semble assez bien s’accommoder d'un stockage en mémoire. A un moment, on lui ôte le résultat d'un calcul sans grand intérêt (mis à part la garantie du succès de la routine). Il n'est mis à jour que si le résultat est positif. Si D2 était dans un registre, il faudrait :

  • soit rectifier l'opération (assez lourd avec les registres d'index, puisqu'il n'y a ni SUB ni SBC possible en 16 bits).

  • soit comparer préalablement sans soustraction.
    Ça me donne une idée, mais passons.

Enfin, supprimer les intermédiaires, parasites rapaces vivant sur le dos du producteur sédentaire je m'égare. Pourquoi avoir un index dans le tampon plutôt qu'un pointeur direct ?
Ce tampon était incompris, vu comme une informe séquence de &C00 octets.
Alors qu'il est constitué de parties bien distinctes (et ne totalisant pas du tout 3k) :

  • 256 mots pour les contextes littéraux sur les adresses paires (1er mot: type)

  • 256 mots pour les contextes littéraux sur les adresses impaires (1er mot: type)

  • 1 mot débouchant sur la prochaine info à lire : longueur VS référence
  •  
  • 2*n mots débouchant sur la longueur d'une référence

  • 2*n mots débouchant sur la position d'une référence (position relative)

Où n est le nombre de bits nécessaire pour encoder longueur/position (13 max si le fichier d'origine fait 8k).

Voilà en gros comment faire maigrir un code boursouflé.

Pour les ceusses souhaitant se pencher sur la question et tailler cette routine comme un bonzaï80 de compétition, de nombreuses pistes existent.

  • Envisager RRD pour le décalage 4 bits [NDX : petit topo sur l'instruction RLD, en attendant l'encyclopédie z80 de Roudoudou !]

  • Ne pas initialiser les probabilités du tout :
    • utiliser le fait que la mémoire est à zéro après un RUN"gap

    • corriger le +&80 à la volée.

    • voire, modifier les routines de calculs pour prendre ce décalage en compte

  • Poster votre routine sur https://codegolf.stackexchange.com/ Bonne chance.

  • Inviter votre voisine à prendre un thé.

  • Merde où ai-je posé mes notes ?

Gonzague

--------------------------------

NDX : de quoi que ça cause, à la fin ?? Le gonz Roudoudou a écrit, avec l'aide d'Antonio Villena, Hicks et Urusergi, une superbe routine de décompression de 245 octets en appel unique, et de 254 octets en appels multiples. Le gonz Gonzague, expert en manipulation de bits, propose aujourd'hui une version de 209 octets, plus rapide de 20% à la décompression. Pour comparer et récupérer tout ce petit monde :