Les compressions MTE et DTE

De T.R.A.F - Wiki
Aller à : navigation, rechercher

Lorsque j'ai voulu traduire un opus de l'une des meilleures séries d'aventure/plates-formes, Gargoyle's Quest II sur NES, j'étais loin de m'imaginer que j'allais trimer... et pas qu'un peu. Je ne suis qu'un modeste ROMhacker dont les compétences en programmation s'arrêtent aux connaissances théoriques issues de la programmation BASIC que j'ai apprise étant jeune et aux divers cours que l'on peut suivre au cours d'études supérieures. Bref, rien de bien transcendant pour m'attaquer à des ROMs tarabiscottées.

C'est vraiment par amour pour ce jeu que je suis allé jusqu'au bout. Et c'est pour cette raison que je vais aujourd'hui vous parler de la source de cette galère (pour qui ne sait pas programmer) : la compression MTE (Multiple Tile Encoding - Encodage de plusieurs caractères)...

Bon, je dramatise un peu : cette compression n'est pas compliquée en soi mais elle demande beaucoup d'efforts afin de la maîtriser.


Que sont donc les MTE et les DTE ?

La compression MTE (Multiple Tile Encoding), comme son nom l'indique, va encoder un groupement d'octet (plusieurs groupements formant ce que l'on appelle un "dictionnaire") sur une suite d'octets dont la taille est inférieure. Par exemple, pour un dictionnaire de 300 mots ou suite de lettres, chacun de ces mots peut être encodé sur deux octets (sachant que deux octets représentent une capacité de 65 536 mots possibles ; en effet, 0xFFFF = 65 535 ce qui fait 65 536 possibilité en comptant 0x0000).

Par extension, on définit également la DTE (Dual Tile Encoding). Il s'agit d'un cas particulier de MTE puisque, dans ce cas précis, on encode deux octets en un seul. Là aussi, il existe un dictionnaire possédant toutes les paires d'octets nécessaires à la compression de données.

Bien sûr, ce système de dictionnaire est utile lorsque de nombreux mots ou suites de lettres sont répétées. Avec ce dictionnaire, on utilise également un alphabet classique (table de caractères) car il est évident que notre dictionnaire ne pourra pas encoder à lui seul l'ensemble des chaînes de caractères du script. Prenons cette phrase relativement connue :

  les chaussettes de l'archiduchesse sont-elles sèches ? archi-sèches !

Mettons que notre dictionnaire contienne les suites de lettres suivants et que chacun de ces suites de lettres soit codée sur un seul octet :

  'les '   'sèches '   'sse'   'archi'   'ch'

Si on devait visualiser la phrase précédente, on verrait ceci dans notre éditeur hexadécimal :

  ##au#ttes de l'#du#e# sont-el##? #-#!

Au départ, on avait 69 caractères. A l'arrivée, on a 37 pour le texte et 21 pour le dictionnaire (car lui aussi prend de la place), ce qui fait 58 caractères au total, ce qui représente une compression de 16% dans notre cas.

Le cas particulier de la DTE aurait aussi bien fonctionné pour cette phrase avec le dictionnaire suivant :

  'ch'   'es'   'se'   'ar'   ' s'

Notre phrase apparaîtrait alors comme ceci dans un éditeur hexadécimal :

  l# #aus#tt# de l'##idu####ont-ell##è## ? ##i-sè## !

Là, on a 51 caractères dûs au texte compressé et 10 caractères dûs au dictionnaire, soit 61 caractères au total (assez peu différent de la méthode utilisant la MTE, finalement). Par contre, on voit bien qu'en répétant plusieurs fois la phrase, le taux de compression MTE augmente plus vite que le taux de compression DTE puisque la taille du dictionnaire ne varie pas alors que celle du texte, si.

Cela vous semble toujours un peu difficile à imaginer ? Ne vous inquiétez pas : rentrons dans le vif du sujet avec l'exemple de Gargoyle's Quest II - The Demon Darkness sur NES. Avant toute chose, néanmoins, sachez que j'utiliserai le terme 'mot' de façon complètement générique : il désignera aussi bien des mots entiers que des chaînes de caractères qui ne veulent rien dire.

La recherche de texte

En regardant l'exemple précédent, on se rend compte que le texte est loin d'être entièrement visible et qu'une recherche de texte peut donner des résultats pourvu qu'on cherche les bons mots. Ici, par exemple, il aurait fallu chercher "sont".

Dans le cas de Gargoyle's Quest II, j'ai cherché le nom du héros, FIREBRAND. Surprise, ce mot n'apparaît qu'une seule fois dans le jeu alors qu'en y jouant, on constate qu'il est répété de très nombreuses fois. Pensant à une coïncidence (un agencement d'octets qui, relativement parlant, réussirait à écrire FIREBRAND), je me mets à chercher d'autres mots. Certains apparaissent (une seule fois, dans les mêmes environs que FIREBRAND et avec la même table de caractères), d'autres pas.

Dans ces cas-là, que fait-on ? On se dit que la coïncidence n'en est pas une et on file regarder ce qu'il se passe à l'endroit où les textes ont été surpris. L'avantage est qu'avec ces recherches, on a réussi à définir la table de caractères suivante :

  /FD
  *FF
  00= 
  01=A
  02=B
  03=C
  04=D
  05=E
  06=F
  07=G
  08=H
  09=I
  0A=J
  0B=K
  0C=L
  0D=M
  0E=N
  0F=O
  10=P
  11=Q
  12=R
  13=S
  14=T
  15=U
  16=V
  17=W
  18=X
  19=Y
  1A=Z
  48=.
  49=,
  4A="
  4B='
  4C=/
  71=+
  72=!
  73=?
  74=-

A l'adresse 0x00D3FC, je me suis retrouvé avec une suite de mots, chacun d'entre eux étant séparés par l'octet 0xFF (plus ou moins). Bravo, je venais de trouver le dictionnaire de la MTE :

  ############ *PO
  T*DROP*STICK*WAT
  ER*SCALES*VIAL*M
  AELSTROM*CD/DKNS
  *CD/PGST*CD/LATH
  E*CD/GHOUL*SOULS
  TREAM*FINGERNAIL
  *HOOF*FALLEN ANG
  EL*HIPPOGRIFF*BE
  REAL*DRAGON*ATLA
  S*BUSTER*TORNADO
  *CLAW*DARKFIRE*F
  IREBRAND*BARR*HE
  CATE*LETHE*DAGON
  *RUSHIFELL*VERON
  A*BREAGER*UH... 
  UH... UH..#BLACK
   LIGHT*THEY SAY*
  MAGIC POWER*THE 
  MAGIC*GHOUL REAL
  M*GO TO*FIREBRAN
  D OBTAINED\*OF T
  HE*TO THE*THAN B
  EFORE*IN THE*DES
  TRUCTION*GENERAT
  ION*LABORATORY*I
  NCREASED*LABYRIN
  TH*LOOSEKEEP*SOM
  ETHING*COMPLETE*
  etc.

Pensant qu'il s'agissait éventuellement des menus (j'avais un doute puisque certains mots n'avaient rien à voir avec ceux des menus), je me suis mis à chercher d'autres mots ou chaînes de caractères qui ne figuraient pas dans cette suite de mots. Au bout de quelques minutes de recherche, je constate que quelques bouts de texte apparaissent un peu plus loin dans la ROM, aux environs de l'adresse 0x00D9F0, avec la même table de caractères que celle utilisée pour le dictionnaire :

   HO##R##\##CEIV#
  ####WHEN##COGNIZ
  ED\AS A#######'S
  ###+######N\####
  S'\#####ONCE PEO
  PLE\LEAVE#######
  Y##\#####HMMM###
  I WONDER\####S\#
  QM##*# ##### JUS
  T\A TRAINEE#####

On constate effectivement que des bouts de mots apparaissent un peu partout. Voici donc notre script ! On remarque également d'autres octets qui permettent d'annoncer la fin d'une section ou la fin d'une ligne : en réalité, ces octets sont des DTE ; par exemple 0xFE indique "." + une fin de section (0xFF), et 0xF8 indique "," + un retour à la ligne (0xFD).

La construction de la table

Outre les principes de base pour créer une table classique (avec ponctuation et toutes ces choses) qui nous permet d'ailleurs de visualiser le dictionnaire et le script morcelé, il faut construire notre table MTE. Nous avons le dictionnaire, très bien. Mais quelle est la valeur hexadécimale de chacun de ces mots ? Sur combien d'octets ces mots sont-ils codés ?

Regardons les premières phrases. On constate que, là où il y a des trous, il y a des paires d'octets qui commencent systématiquement par 0xF2, 0xF3, 0xF4 et 0xF5. Du coup, on en conclut que chacun des mots de la MTE est codé sur 2 octets. A présent, il faut définir leur valeur.

En lisant le texte dans l'éditeur hexadécimal et en jouant au jeu, on commence à trouver quelques valeurs. On se rend assez vite compte que les mots du dictionnaires sont dans le même ordre que les octets qui les définissent. Enfin, pas tout à fait : en regardant la table de pointeurs qui définit le dictionnaire, on constate que certains se répetent : cela signifie que deux pointeurs successifs redirigent vers le même mot. Du coup, un même mot peut avoir deux valeurs, ce qui se confirme lorsqu'on construit la table et que l'on compare les valeurs obtenues à celles que l'on devrait obtenir dans le jeu en lisant le script morcelé dans l'éditeur hexadécimal. Voici un morceau de l'extraction du dictionnaire avec Pointer Tables :

  D2AC
   <FF>
  
  D2AD
  POT<FF>
  
  D2AE
  DROP<FF>
  
  D2AF
  STICK<FF>
  
  D2B0
  WATER<FF>
  
  D2B1
  SCALES<FF>
  
  D2B2
  VIAL<FF>
  
  D2B3
  MAELSTROM<FF>

Vous croyez qu'on a fini ? Pas tout à fait. Ce jeu possède une petite particularité. Prenons le mot le plus couramment utilisé, FIREBRAND. Dans de nombreuses phrase, on constate que FIREBRAND prend tantôt la valeur 0xF200 tantôt la valeur 0xF300. En y regardant de plus prêt, il s'agit en fait d'un subterfuge utilisé par les programmeurs afin de définir le mot ' FIREBRAND' et le mot 'FIREBRAND' : seul un espace sépare ces deux mots. Du coup, le dictionnaire est virtuellement constitué de 328 mots : 164 mots et leur version avec un espace supplémentaire.

Voici donc un morceau de la table finale du script principal :

  F211= TO THE
  F212= THAN BEFORE
  F213= IN THE
  F214= DESTRUCTION
  F215= GENERATION
  F216= LABORATORY
  F217= INCREASED
  F218= LABYRINTH
  F219= LOOSEKEEP
  F21A= SOMETHING
  F21B= COMPLETE
  ...
  F31A=SOMETHING
  F31B=COMPLETE
  F31C=EXCHANGE
  F31D=MATERIAL
  F31E=MOUNTAIN
  F31F=OBTAINED
  F320=OVERFLOW
  F321=PASSWORD
  F322=POSSIBLE


La réinsertion du script

Notez que ce jeu n'est écrit qu'en majuscule, ce qui simplifie grandement le travail de création de dictionnaire puisque ce dernier ne va chercher que parmi 26 lettres et quelques signes de ponctuation.

Ceci dit, une fois que vous avez extrait votre script et que vous l'avez traduit (20 ko ne devraient pas vous prendre trop de temps), il va falloir le réinsérer. Or, vous vous en doutez bien, les mots anglais du dictionnaire ne vont pas vous être utile dans l'encodage de votre traduction et pour cause : vous n'utilisez quasiment aucun de ces mots.

La création de la table

Il va donc vous falloir créer votre propre table MTE. Fort heureusement, vous n'aurez pas à faire cela à la main. Des outils comme le Hareng-Tool vous permettent d'optimiser votre table MTE en fonction de votre script. Cet outil est très simple à utiliser (quoiqu'en ligne de commande) et vous permet très rapidement d'avoir accès à une liste de mots triés selon leur efficacité à diminuer la taille de votre script.

Etant donné que, grâce à la table de pointeurs, vous avez pu extraire le dictionnaire anglais, il va maintenant falloir insérer ces mots français optimisés à leur place (en sachant que vous allez être limités soit par le nombre de mots du dictionnaire, soit par la taille globale du dictionnaire). Toutefois, quelques mots utilisés dans les menus du jeu (eh oui) vont vous être imposés (bien qu'ils ne soient pas répétés des centaines de fois). Faites donc attention à ce que vous pouvez modifier et ce que vous devez traduire. Faites également attention à ce que vos traductions soient conformes aux mots que vous avez utilisés dans votre script : sans ça, la MTE ne servira pas à grand chose !

Voici un extrait de mon dictionnaire optimisé (avant réinsertion) :

  F209= ENTRAINEMENT
  F20A= SEIGNEUR
  F20B= GUERRIER
  F20C= ENT
  F20D= A RECU
  ...
  F341=ENVAHIT 
  F342=RESSUSCITE
  F343=DETRUI
  F344=MATERIAU
  F345=DIRIGEAIT VERS

Astuce d'utilisation de la table MTE

Il existe une astuce très intéressante pour éviter de prendre de la place inutilement dans le dictionnaire : la réutilisation de bouts de chaîne.

Mettons que vous ayez l'optimisation suivante :

  regarde
  combat
  montagne
  ciel
  garde
  mon
  bat

On constate que certains blocs sont inclus dans d'autres : c'est le cas de 'garde' dans 'regarde', de 'mon' dans 'montagne' et de 'bat' dans 'combat'. Etant donné que chaque mot de votre dictionnaire possède un pointeur et que la fin d'un mot est marqué par un octet (ici c'est 0xFF), il est donc possible de réutiliser des morceaux de mots pour définir ceux qui sont plus petits.

En réfléchissant bien, vous devriez vous rendre compte que cela n'est pas possible pour l'un d'entre eux... Vous avez trouvé ? On ne peut en effet pas réutiliser le 'mon' de 'montagne' puisque ce morceau se situe au début du mot ! Par contre, lorsque le morceau se situe à la fin comme pour 'garde' et 'bat', il est possible de placer les pointeurs de ces mots sur le 'g' de 'regarde' et le 'b' de 'bat' respectivement. Du coup, lorsque vous réinsérez votre dictionnaire, vous avez deux possibilités :

  • soit vous cherchez des pointeurs non utilisés et vous les redirigez (à la main) vers ces bouts de mots. Dans votre table de réinsertion, vous connaissez en théorie la valeur de ces morceaux de mots puisque, je vous le rappelle, les pointeurs du dictionnaire sont dans le même ordre que les octets d'encodage (ou alors dans un ordre connu, si vous avez bien fait votre travail) ;
  • soit vous écrivez la première partie du mot dans votre dictionnaire de réinsertion sans mettre de marque de fin (vous ne mettez pas de <FF>) puis, pour le pointeur en dessous, vous mettez la deuxième partie du mot en n'oubliant pas l'octet de fin. Pour en revenir à notre exemple, notre dictionnaire de réinsertion pourrait ressembler à ceci :
  <PT0001>
  re
  
  <PT0002>
  garde<FF>
  
  <PT0003>
  com
  
  <PT0004>
  bat<FF>
  
  <PT0005>
  montagne<FF>
  
  <PT0006>
  mon<FF>
  
  <PT0007>
  ciel<FF>

Pour en revenir à Gargoyle's Quest II, voici un extrait de ma table de réinsertion ou se trouve la réutilisation d'un morceau de mot :

  F347=PALAIS DU ROI
  F348=ROI
  F34E=PLUS HAUT QU'AVANT
  F34F=AVANT
  F511=HIPPOGRIFFE
  F379=GRIFFE

Et voilà à quoi ressemble mon dictionnaire de réinsertion avec cette astuce :

  D30D
  PALAIS DU 
  
  D30E
  ROI<FF>
  
  D314
  PLUS HAUT QU'
  
  D315
  AVANT<FF>
  
  D33F
  HIPPOGRIFFE<FF>

Comme vous pouvez le constater, le mot 'HIPPOGRIFFE' est seul dans le dictionnaire : le mot 'GRIFFE' n'existe pas et, pourtant, il va être utilisé. Comme il a été dit plus haut, certains mots du dictionnaire MTE étaient réservés aux menus, ce qui est le cas de 'HIPPOGRIFFE' et des pointeurs situés avant et après : on ne pouvait pas utiliser la seconde méthode de réinsertion. Il a donc fallu que j'utilise la première méthode afin de pouvoir utiliser le mot 'GRIFFE', à savoir chercher un pointeur libre et le recalculer à la main (il restait des pointeurs libres étant donné, d'une part, qu'il y en avait déjà dans le script original - les fameuses répétitions - et, d'autre part, que les mots français étaient plus long que les mots anglais, ce qui faisait moins de mots dans le dictionnaire).

En revanche, pour les deux autres mots, j'ai utilisé la seconde méthode : rien à faire, le logiciel de réinsertion s'occupe de tout. Impeccable.

Les MTE et DTE graphiques

Vous avez remarqué que la place, en particulier dans le dictionnaire, est très précieuse. Rajouter deux ou trois mots au dictionnaire, même très courts, peuvent vous faire gagner quelques précieux octets dans le script. Dans Gargoyle's Quest II, cette place est d'autant plus précieuse qu'il n'y a nulle part dans la bank du script où l'on peut déplacer du texte. En bref... il n'y a pas de place du tout ! Ajoutez à cela que la langue française dispose de moins de répétitions que la langue anglaise (notamment dans l'utilisation des verbes) et on comprendra que le dictionnaire français risque d'être moins performant que le dictionnaire anglais.

Que nous reste-t-il alors ? L'aspect graphique. Le gros avantage de Gargoyle's Quest II est que, s'il ne possède aucune place au niveau du script, il lui en reste pas mal côté graphismes... Alors pourquoi s'en priver ?

Utilisation de DTE

Commençons par les compressions les plus simples et qui feront gagner énormément de place : les DTE graphiques (coder deux octets dans un seul). Que pouvons-nous lister comme DTE simples à mettre en oeuvre ? Il existe trois classes, habituellement :

  • les lettres avec apostrophes,
  • les signes de ponctuation avec espace (notons que les trois points de suspensions peuvent être mis dans un seul caractère),
  • l'association de lettres fines (cela ne fonctionne que pour les minuscules, pas pour les majuscules).

Dans notre jeu, le script n'est écrit qu'en majuscule. Nous nous contenterons donc des deux premières catégories. Nous dessinerons donc, dans un seul caractère, ce genre de choses :

  ┌───┬───┬───┬───┬───┬───┐
  │ D'│ J'│ L'│ M'│ N'│ U'│
  ├───┼───┼───┼───┼───┼───┤
  │!  │.  │,  │...│?  │:  │
  └───┴───┴───┴───┴───┴───┘

Je ne vous ferai pas l'affront de savoir comment retrouver les valeurs hexadécimales de votre DTE graphique : si vous savez construire une simple table de caractères, vous savez donc comment retrouver les valeurs manquantes.

Dans le cas plus étendu où vous auriez des minuscules, vous pourriez créer des associations très connues de "lettres fines" (3 pixels de large ou moins) :

  ┌──┬──┬──┬──┬──┬──┐
  │li│ll│ri│ti│il│rr│
  └──┴──┴──┴──┴──┴──┘

Et voici un exemple de trois tiles (8x8 pixels) traitées selon les tableaux que je viens de faire (les caractères sont de style "Courrier" ; il s'agit de la police de largeur fixe que l'on trouve par défaut dans tous les fichiers au format texte pur) :

  ┌──┬──┬──┬──┬──┬──┬──┬──┐    ┌──┬──┬──┬──┬──┬──┬──┬──┐    ┌──┬──┬──┬──┬──┬──┬──┬──┐
  │██│██│██│██│  │  │██│  │    │  │██│██│  │  │  │  │  │    │██│██│  │  │  │██│  │  │
  ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤
  │  │██│  │  │██│  │██│  │    │██│  │  │██│  │  │  │  │    │  │██│  │  │  │  │  │  │
  ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤
  │  │██│  │  │██│  │  │  │    │  │  │  │██│  │  │  │  │    │  │██│  │  │██│██│  │  │
  ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤
  │  │██│  │  │██│  │  │  │    │  │  │██│  │  │  │  │  │    │  │██│  │  │  │██│  │  │
  ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤
  │  │██│  │  │██│  │  │  │    │  │██│  │  │  │  │  │  │    │  │██│  │  │  │██│  │  │
  ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤
  │  │██│  │  │██│  │  │  │    │  │  │  │  │  │  │  │  │    │  │██│  │  │  │██│  │  │
  ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤
  │██│██│██│██│  │  │  │  │    │  │██│  │  │  │  │  │  │    │██│██│██│  │██│██│██│  │
  ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤    ├──┼──┼──┼──┼──┼──┼──┼──┤
  │  │  │  │  │  │  │  │  │    │  │  │  │  │  │  │  │  │    │  │  │  │  │  │  │  │  │
  └──┴──┴──┴──┴──┴──┴──┴──┘    └──┴──┴──┴──┴──┴──┴──┴──┘    └──┴──┴──┴──┴──┴──┴──┴──┘

Vous noterez que la ligne du bas et la colonne de droite (en fait, une colonne et une ligne situées aux extrémités) doivent rester vierges dans la plupart des jeux : ce sont elles qui assurent en général la séparation des lettres de manières horizontale et verticale (on peut faire une exception sur les lettres à queue inférieure comme les p, q, j, etc. ou réduire la hauteur des lettres à 6 pixels et non 7 dans le cas présent).

Utilisation de MTE

Vous venez de le voir, la DTE n'a pas beaucoup affecté le dictionnaire (certains mots font tout de même usage de ces caractères) mais le script dans son ensemble. L'utlisation de la MTE va en revanche nous permettre de raccourcir la taille totale de notre dictionnaire d'origine afin de pouvoir faire rentrer d'autres mots qui nous feront gagner de la place dans notre script.

Une MTE graphique consiste à coder un mot de X lettres à l'aide de Y tiles avec Y < X. En général, on prend les mots les plus longs car ils peuvent nous faire gagner plus d'octets sans qu'on ait besoin de trop déformer les lettres (nous avons juste à les rapprocher... en déformant les lettres, cela finit par se voir dans le jeu, ce qui n'est pas propre ! Notez que, parfois, on n'a pas vraiment le choix).

Dans notre cas on avait, par exemple, FIREBRAND et ROYAUME DES GOULES qui se prêtaient bien à ce genre d'exercices. Quelques octets dans la table ont ainsi pu être gagné, ce qui a permis de rajouter quelques autres mots au dictionnaire. Rien de bien mirobolant mais, dans notre cas, chaque octet compte quand on n'a pas la moindre once de place !