|
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
|