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
$80/FE34: A9 FF 9D
$80/FE37: 85 D0
$80/FE39: A5 02
$80/FE3B: 10 02
$80/FE3D: E6 D0
$80/FE3F: 09 00 80
$80/FE42: 85 CF
$80/FE44: F4 7E 7E
$80/FE47: AB
$80/FE48: AB
$80/FE49: 9C 22 02
$80/FE4C: E2 20
$80/FE4E: A0 00 00
$80/FE51: C2 20
$80/FE53: A9 00 00
$80/FE56: AA
$80/FE57: 22 C0 AE 81
PHB
LDA #$9DFF
STA $D0 [$00:00D0]
LDA $02 [$00:0002]
BPL $02 [$FE3F]
INC $D0
ORA #$8000
STA $CF [$00:00CF]
PEA $7E7E [$80:7E7E]
PLB
PLB
STZ $0222 [$7E:0222]
SEP #$20
LDY #$0000
REP #$20
LDA #$0000
TAX
JSL $81AEC0 [$81:AEC0]

[01]
[02]
[03]
[04]
[05]
[06]
[07]
[08]
[09]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]

[01] 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.
[02] Notez bien l'adresse.
[03] Charge le pointeur récupéré dans la routine precedente (cette routine peut
____varier. Voir après)
[04] Si c'est positif, aller à 80:FE3F
[05] Sinon, augmenter le bank par 1 : on a alors le bank 9E
[06] Fait un OR avec la valeur contenue dans l'accumulateur. Cela convertit les
____valeurs inferieures à 7FFFh.
[07] 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?
[08] Met 7E en adresse effective. Ca signifie que chaque appel à une valeur telle
____que $0222, sera précedée de $7F.
[09] Restaure 2 fois la pile
[10] Idem.
[11] Met cette adresse à zero. Elle sera reutilisée après.
[12] Met en 8 bits l'accumulateur
[13] Charge 0000 dans Y. Ca sera reutilisé après.
[14] Remet en 16 bits.
[15] Met l'accumulateur à 0
[16] Met X à 0 : Donc, on a nettoyé tous les registres : A X et Y.
[17] 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
$81/AEC3: 10 12
$81/AEC5: 48
$81/AEC6: A9 0F 00
$81/AEC9: 8D 22 02
$81/AECC: A7 CF
$81/AECE: EB
$81/AECF: 8D 24 02
$81/AED2: E6 CF
$81/AED4: E6 CF
$81/AED6: 68
$81/AED7: 0E 24 02
$81/AEDA: 6B
DEC $0222 [$7E:0222]
BPL $12 [$AED7]
PHA
LDA #$000F 
STA $0222 [$7E:0222]
LDA [$CF] [$9D:F0C8]
XBA
STA $0224 [$7E:0224]
INC $CF [$00:00CF]
INC $CF [$00:00CF]
PLA
ASL $0224 [$7E:0224]
RTL
[01]
[02]
[03]
[04]
[05]
[06]
[07]
[08]
[09]
[10]
[11]
[12]
[13]

[01] On décemente cette adresse de 1. C'est le compteur qui indique à quel
____endroit en est la lecture de l'arbre.
[02] Si la valeur est superieure ou égale à 0, on continue la décompression.
[03] Sinon, on sauvegarde l'accumulateur.
[04] Ici, c'est l'initialisation de la lecture de l'arbre : F = 15, et l'arbre est de 16
____"branches" .
[05] Que l'on met dans cette adresse memoire.
[06] 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".
[07] On "retourne" cette valeur.
[08] Que l'on met dans $0224
[09] Et on augmente l'adresse du texte deux fois, pour préparer la prochaine
____lecture.
[10] Idem.
[11] On restaure l'accumulateur.
[12] Et on commence la lecture du texte compressé : le ASL dit si le premier bit
____est un 1 ou un 0.
[13] 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
$80/FE5D: E8
$80/FE5E: E8
$80/FE5F: BF 00 80 9D
$80/FE63: 10 F1
$80/FE65: 29 7F 7F
$80/FE68: EB
$80/FE69: E2 20
$80/FE6B: C9 0A
$80/FE6D: F0 11
$80/FE6F: 99 A0 21
$80/FE72: C8
$80/FE73: EB
$80/FE74: F0 DB
$80/FE76: C9 0A
$80/FE78: F0 06
$80/FE7A: 99 A0 21
$80/FE7D: C8
$80/FE7E: 80 D1
$80/FE80: BB
$80/FE81: 9E A0 21
$80/FE84: C2 20
$80/FE86: 20 03 FB
BCC $02 [$FE5F]
INX
INX
LDA $9D8000,X [$9D:8002]
BPL $F1 [$FE56]
AND #$7F7F
XBA
SEP #$20
CMP #$0A
BEQ $11 [$FE80]
STA $21A0,Y [$7E:21A0]
INY
XBA
BEQ $DB [$FE51]
CMP #$0A
BEQ $06 [$FE80]
STA $21A0,Y [$7E:21A3]
INY
BRA $D1 [$FE51]
TYX
STZ $21A0,X [$7E:21A4]
REP #$20
JSR $FB03 [$7E:FB03]
[01]
[02]
[03]
[04]
[05]
[06]
[07]
[08]
[09]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]

[01] Si le flag carry est viré, alors va à FE5F.
[02] Sinon, augmente 2 fois X.
[03] Idem
[04] Charge une table qui se situe à 9D8000+X: le jeu lit l'arbre huffmann.
[05] Si la valeur est positive, alors on va à FE56(c'est la routine du dessus), pour
__- _transferer la valeur lue dans le X.
[06]
_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.
[07] On la met à l'envers, car après le STA, elle redeviendra à l'endroit.
[08] Mode 8 bits.
[09] On compare ça à #$0A, qui est le "ligne break", indiquant la fin d'une phrase.
[10] Si c'est égal, alors on a finit de décrypter la phrase.
[11] Sinon, on met l'accumulateur dans une zone où sera écrit toute la phrase.
[12] Augmente l'adresse de cette zone.
[13] On "retourne" encore l'accumulateur, car on est toujours en 8 bits...
[14] .......
[15] Pour pouvoir le comparer à #$01, qui est toujours le ligne break.
[16] Si c'est égal, alors on a finit de décrypter la phrase.
[17] Sinon, on met l'accumulateur dans une zone où sera écrit toute la phrase.
[18] On augmente encore l'adresse de la zone de texte décompressé.
[19] ...et on retourne dans la routine précedente, pour nettoyer le 1 et le X : une
____autre décompression de lettre commence...
[20]Ici, la décompression est finie : on transfert l'indicateur de position de la zone
___ de décompression dans X.
[21] ...pour pouvoir écrire 00 à la fin de la phrase décompressée.
[22]  16 bits mode engaged.
[23] Et on a finit de décompresser TOUTE notre phrase. On va maintenant l'afficher à l'ecran, mais c'est une autre histoire ;-)


J'ai é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
$80/FE9D: 48
$80/FE9E: A5 0A
$80/FEA0: 0A
$80/FEA1: AA
$80/FEA2: BD 80 D9
$80/FEA5: 85 02
$80/FEA7: 20 33 FE
LDA $00 [$00:0000]
PHA
LDA $0A [$00:000A]
ASL A
TAX
LDA $D980,X [$80:D9FA]
STA $02 [$00:0002]
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ées.

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