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