Ze Skeud's guide sur l'asm

 

_
_
Sommaire
_Introduction
_SNES
_Compression
_Megadrive
_Final Thoughts
_


 
 
 

Next world : compression.





 

Les explications de cette page proviennent de mon travail sur Shadowrun, petit jeu sympa, mais avec TOUT de compressé, sauf le texte d'intro (meme les menus!).
Je n'ai pas vraiment envie de faire la traduction de ce jeu (je n'y ai pas joué plus de 5 minutes!), mais j'ai surtout voulu m'entrainer sur un jeu au texte compressé, et ainsi faire profiter de mon experience les autres personnes qui pourraient etre interessées.
De plus, il y a aussi mon exquisse de nouvelle routine de texte, qui ne fonctionne pas encore (problème de stack, et je n'ai pas le temps de m'en occuper), mais l'essentiel est là tout de même.

Mais comment trouver où est le texte compressé?

Je n'ai pas trouvé la "solution" miracle, car ma méthode est chiante et longue (10 15 minutes pour trouver la routine, des fois 20 30 selon la taille du .log).
Pour la connaitre, il suffit de..... lire à la fin de la page sur la modif de texte ;-), partie "a l'aide..."(ca me fait chier de faire copier coller!)

Ce que j'ai fait : j'ai imprimé les 2 .log, et j'ai comparé ligne par ligne le code, en notant les différences. (OUI! Je me suis fait CHIER!).
Une fois l'adresse trouvée, j'ai pu isoler la routine du texte, en analysant le code autour. C'est à dire, en repérant les JSR, BSR, ou autre RTS. Car, comme c'est une routine de texte, elle est appellée souvent. C'est donc très certainement une sous-routine.

Mais comment elle marche cette routine (bis repetita) ?

Voilà la routine de shadowrun qui sert à decompresser TOUTES les données compressées (texte, et 'peut-être' aussi les images, je n'ai pas approfondi).
Les commentaires sont a coté de chaque ligne, mais pour une meilleure compréhension, il faut les lire après avoir lu jusqu'au ¤ .

$80/FE33: 8B           PHB
$80/FE34: A9 FF 9D     LDA #$9DFF       charge le bank où se situe le texte compressé. Notez qu'il y a FF a la fin : il ne sert à rien. Plus d'infos après.
$80/FE37: 85 D0        STA $D0 [$00:00D0]
Le met dans $D0. Notez bien l'adresse.
$80/FE39: A5 02        LDA $02 [$00:0002] Charge le pointeur récupéré dans la routine precedente (cette routine peut varier. Voir après)
$80/FE3B: 10 02        BPL $02 [$FE3F]    Si c'est positif, aller à 80:FE3F
$80/FE3D: E6 D0        INC $D0          Sinon, augmenter le bank par 1 : on a alors le bank 9E
$80/FE3F: 09 00 80     ORA #$8000       Fait un OR avec la valeur contenue dans l'accumulateur. Cela convertit les valeurs inferieures à 7FFFh.
$80/FE42: 85 CF        STA $CF [$00:00CF] Le met dans CF (souvenez vous, on avait dans D0 le bank. Mais comme c'etait 16 bits, le bank se  situe   D1. A D0, il y a le FF. Et suite à cette commande, à D0, il y a une partie du pointeur. Vous suivez?
$80/FE44: F4 7E 7E     PEA $7E7E [$80:7E7E] Met 7E en adresse effective. Ca signifie que chaque appel à une valeur telle que $0222, sera précedée de $7F.
$80/FE47: AB           PLB                 restaure 2 fois la pile
$80/FE48: AB           PLB               Idem.
$80/FE49: 9C 22 02     STZ $0222 [$7E:0222]Met cette adresse à zero. Elle sera reutilisée après.
$80/FE4C: E2 20        SEP #$20          Met en 8 bits l'accumulateur
$80/FE4E: A0 00 00     LDY #$0000        Charge 0000 dans Y. Ca sera reutilisé après.
$80/FE51: C2 20        REP #$20          Remet en 16 bits.
$80/FE53: A9 00 00     LDA #$0000        Met l'accumulateur à 0
$80/FE56: AA           TAX               Met X à 0 : Donc, on a nettoyé tous les registres : A X et Y.
$80/FE57: 22 C0 AE 81  JSL $81AEC0 [$81:AEC0] C'est parti pour la fète!

Je vais donc "traduire" cette routine, car je pense que les commentaires pourraient ne pas suffir.
Le jeu charge le bank du texte. Mais, etrangement, il charge #$9DFF, et non seulement #$9D. Pourquoi? Parceque, faire un SEP #$20 d'abord, et un REP $# ensuite est long. De plus, cette donnée superflue sera ecrasée par le pointeur.
Ensuite, le jeu recupère le pointeur qu'il a lu la routine precedente. Si ce pointeur est superieur à 7FFF, il est négatif. Et oui. En valeur signées, le 7FFF est le maximum (32767) et le FFFF le minimum (-32767). Cela explique le BPL, branch if PLUS.
Si c'est négatif, il faut alors augmenter le bank. Car les lowrom commencent à 80:8000 (notez le 8000). Donc, 8000 + 8000 = 10000. on se retrouverait alors à 81:8000.
Puis, le jeu fait un OR #$8000 avec ce pointeur. Comme ca, le pointeur se situe entre 8000 et FFFF, ce qu'il faut pour une low rom.
Et il met ce "nouveau" pointeur dans $CF ET $D0 (effaçant ainsi le FF, mais je me repète là...).
Il prépare après la console à recevoir des données, car il va aller dans une routine qui en a besoin : Adresse effective : $7E, restaure deux fois la pile, met $0222, A, X et Y à 0. Puis, plonge....

Cette routine est appelée à chaque fois que les deux octets de texte compressé sont décompressés, et mis dans la memoire.
Elle initialise donc la lecture de l'arbre (le LDA #000F)

$81/AEC0: CE 22 02     DEC $0222 [$7E:0222] On décemente cette adresse de 1. C'est le compteur qui indique à quel endroit en est la lecture de l'arbre.
$81/AEC3: 10 12        BPL $12 [$AED7]       Si la valeur est superieure ou égale à 0, on continue la décompression
$81/AEC5: 48           PHA                  Sinon, on sauvegarde l'accumulateur.
$81/AEC6: A9 0F 00     LDA #$000F           Ici, c'est l'initialisation de la lecture de l'arbre : F = 15, et l'arbre est de 16 "branches"
$81/AEC9: 8D 22 02     STA $0222 [$7E:0222] Que l'on met dans cette adresse memoire.
$81/AECC: A7 CF        LDA [$CF] [$9D:F0C8]  Grâce à la routine précedente, dans $CF se situe l'adresse du texte compressé. Cette commande signifie "lit à l'adresse contenue dans $CF, et met ce que tu as lu dans l'accumulateur"
$81/AECE: EB           XBA                  On "retourne" cette valeur.
$81/AECF: 8D 24 02     STA $0224 [$7E:0224] Que l'on met dans $0224
$81/AED2: E6 CF        INC $CF [$00:00CF]    Et on augmente l'adresse du texte deux fois, pour préparer la prochaine lecture.
$81/AED4: E6 CF        INC $CF [$00:00CF]    Idem
$81/AED6: 68           PLA                  On restaure l'accumulateur
$81/AED7: 0E 24 02     ASL $0224 [$7E:0224] Et on commence la lecture du texte compressé : le ASL dit si le premier bit est un 1 ou un 0.
$81/AEDA: 6B           RTL                  On va traverser l'arbre selon la valeur du bit lu

C'est parti pour la VRAI routine de décompression.. NB : Cette routine se situe après la première routine, étudiée au dessus.

$80/FE5B: 90 02        BCC $02 [$FE5F]        Si le flag carry est viré, alors va à FE5F
$80/FE5D: E8           INX                  Sinon, augmente 2 fois X
$80/FE5E: E8           INX                  Idem
$80/FE5F: BF 00 80 9D  LDA $9D8000,X [$9D:8002]Charge une table qui se situe à 9D8000+X : le jeu lit l'arbre huffmann.
$80/FE63: 10 F1        BPL $F1 [$FE56]        Si la valeur est positive, alors on va à FE56(c'est la routine du dessus), pour transferer la valeur lue dans le X.
$80/FE65: 29 7F 7F     AND #$7F7F           Sinon, le jeu fait un AND, ce qui permet de convertir les valeurs superieures à 8000 en valeurs comprises entre 0 et 8000 (l'inverse de tout à l'heure). C'est une partie decompressée du texte.
$80/FE68: EB           XBA                  On la met à l'envers, car après le STA, elle redeviendra à l'endroit.
$80/FE69: E2 20        SEP #$20             Mode 8 bits
$80/FE6B: C9 0A        CMP #$0A                              On compare ça à #$0A, qui est le "ligne break", indiquant la fin d'une phrase.
$80/FE6D: F0 11        BEQ $11 [$FE80]        Si c'est égal, alors on a finit de décrypter la phrase.
$80/FE6F: 99 A0 21     STA $21A0,Y [$7E:21A0] Sinon, on met l'accumulateur dans une zone où sera écrit toute la phrase.
$80/FE72: C8           INY                    Augmente l'adresse de cette zone
$80/FE73: EB           XBA                  on "retourne" encore l'accumulateur, car on est toujours en 8 bits...
$80/FE74: F0 DB        BEQ $DB [$FE51]        .......
$80/FE76: C9 0A        CMP #$0A             Pour pouvoir le comparer à #$01, qui est toujours le ligne break.
$80/FE78: F0 06        BEQ $06 [$FE80]        Si c'est égal, alors on a finit de décrypter la phrase.
$80/FE7A: 99 A0 21     STA $21A0,Y [$7E:21A3] Sinon, on met l'accumulateur dans une zone où sera écrit toute la phrase.
$80/FE7D: C8           INY                    On augmente encore l'adresse de la zone de texte décompressé
$80/FE7E: 80 D1        BRA $D1 [$FE51]        ..et on retourne dans la routine précedente, pour nettoyer le 1 et le X : une autre décompression de lettre commence...
$80/FE80: BB           TYX                  Ici, la décompression est finie : on transfert l'indicateur de position de la zone de décompression dans X
$80/FE81: 9E A0 21     STZ $21A0,X [$7E:21A4] ..pour pouvoir écrire 00 à la fin de la phrase décompressée
$80/FE84: C2 20        REP #$20                16 bits mode engaged..
$80/FE86: 20 03 FB     JSR $FB03 [$7E:FB03] Et on a fint de décompresser TOUTE notre phrase. On va maintenant l'afficherà l'ecran, mais c'est une autre histoire ;-)
 

Jai étudié la routine du texte qui s'affiche au tout début du jeu (quand les docteurs parlent ensemble, ou lorsque vous ne pouvez vaire certaines actions "too far away" par exemple). Ci-dessous, voici à quel endroit la routine de décompression est appelée pour ce type de dialogue.

$80/FE9B: A5 00        LDA $00 [$00:0000]
$80/FE9D: 48           PHA
$80/FE9E: A5 0A        LDA $0A [$00:000A]
$80/FEA0: 0A           ASL A
$80/FEA1: AA           TAX
$80/FEA2: BD 80 D9     LDA $D980,X [$80:D9FA]
$80/FEA5: 85 02        STA $02 [$00:0002]
$80/FEA7: 20 33 FE     JSR $FE33 [$80:FE33]

¤ <=========== IL est LA!!!

Maintenant, je vais "traduire" cet algorithme.

-------- Avant d'entrer dans cette sous-routine, à $02, il y a le pointeur du texte compressé.-------

1. Chargement du bank de la zone compressée : 9D, mis dans une zone mémoire $D0. Chargement du pointeur à $02. Vérification si on a dépassé ou pas le bank. Si oui, augmenter 9D de 1, si non, on n'augmente rien du tout. Puis, on fait un OR #$8000 du pointeur, pour ramener sa valeur au dessus de 8000h (parce que la rom est une low rom.) On met ce pointeur fraichement converti dans $CF. A ce niveau, dans CF et D0, il y a le pointeur et le bank de la zone compressée.
2.On nettoie les registres A X et Y, puis on va à $81/AEC0.
3. Là, le jeu vérifie si on est déjà en cours de décompression : non. Donc, il met le nombre de branches de l'arbre dans $0222 : il marque le début niveau de progression de la lecture. Puis, utilisation de $CF et $D0 pour lire la donnée compressée, sur 16 bits. Il retourne cette donnée, qui est mise dans $0224, puis l'adresse de la donnée compressée est augmentée de 2, pour plus tard.
4. Le début de la lecture commence là, à $81/AED7 : le ASL permet de connaitre le premier bit, si c'est un 1 ou un 0. Si c'est un 1, le flag "carry" se met, sinon, il y a rien. Le ASL se fait sur l'adresse $0224, où la donnée compressée se trouve (vous vous souvenez?)
5. Début de la lecture de l'arbre, en fonction du carry, donc du premier bit de la donnée compressée. si c'est un 0, le jeu augmente de 2 la valeur de X, sinon, il n'augmente pas X. Avec cette valeur, il lit l'arbre : LDA $9D8000,X. La valeur de l'arbre est positive (inferieure à 8000h)? On va dire oui pour cette fois. A ce moment là, le jeu retourne à $FE56, pour transferer la valeur 16 bits lue dans l'arbre dans X. Puis, décrémetation de $0222, car on a lu une branche de l'arbre. On a pas finit de le lire, on continue alors! On retourne à $81/AED7, et la lecture bit à bit continue : Si 1, etc....
6. On lit encore la table, avec dans X, la VALEUR lue précedemment, additionnée ou non de 2, selon le bit lu. Mais maintenant, la donnée lue dans l'arbre est négative (superieure à 8000h) : On jumpe dans la routine qui inscrit la donnée décompressée.
7. Le jeu fait un AND $7F7F, pour convertir la valeur négative en valeur positive. Puis, on vérifie si la donnée décompressée contient un ligne break : 0A. On va dire qu'elle n'en contient pas. alors, cette donnée est mise dans 7E21A0 + Y, qui est la zone décompressée. Puis, comme la donnée décompressée ne contenait pas de 0A, on continue à lire l'arbre.
8. Rebelotte comme pour le 5, jusqu'a ce que la lecture soit finie : 7E0222 a atteint 0. Alors, on recommence la décompression mais avec une nouvelle donnée compressée.

Pour comprendre cette routine, il faudrat connaitre le principe de base de la compression huffmann. Je résume donc...
Quand le compresseur compresse (logique!), il trie les lettre qu'il rencontre le plus, un peu comme un optimiseur de DTE. En fait, dans sa forme basique, le huffmann est du DTE (DUAL, donc 2, mais cela varie selon les méthodes), mais optimisé pour prendre le moins de place. Ensuite, tout cela est inscrit dans un "arbre". Le texte compressé permet de parcourir l'arbre, en récuperant les données décompressée. C'est pourquoi une chaine hexa 16bits  peut parfois donner des valeurs décompressée de 5 octets, ou meme 1 octet : c'est selon le taux de repétition de la chaine.
 
 

Voilà, vous savez maintenant comment le texte se décompresse.

REMARQUE...
comme vous pouvez le voir, cette routine est facile à comprendre, et à rajouter dans un jeu.
Mais je cherche desespérement un moyen de coder un compresseur huffmann pour aller avec....

AUTRE REMARQUE...
J'avais commencé à coder une routine pour charger du texte décompressé. La première version ne fonctionnait pas. La deuxième, très peu... Et pis ca m'a fait chier!
En plus, il y a une autre sorte de texte, compressé de la même façon, mais je n'ai pas pu comprendre comment fonctionnait la routine qui recuperait les pointeurs des phrases compressés.

PS: Ma routine de texte qui fonctionne pas est dans le fichier shadorout.txt