Le principe de la compression RLE

Bien le bonjour à vous !

Voici un petit document permettant d'expliquer le fonctionnement de la compression RLE.

C'est un document sans grande prétention étant donné que le peu de connaissance que j'ai de cette compression est seulement ce que Meradrin m'a expliqué, c'est à dire le strict minimum 🙂

Donc il est possible que j'ai oublié des choses. Si c'est le cas n'hésitez pas à me contacter.

Mais pour aider à comprendre, je m'appuierai sur un exemple concret.

Table des matières


1) Introduction

Un jour comme un autre, (enfin, c'est ce que je croyais) PERIGOURDIN, un jeune hackeur du groupe Génération IX, vint me demander de l'aide pour un jeu qu'il était en train de hacker.

Ma générosité se fit entendre à ce moment-là et je pris donc la rom du jeu pour regarder ce problème.

J'ouvris donc la rom sous mon éditeur hexadécimal et après un moment de recherche, qui ne fut pas très long (étant donné que PERI m'avait donné l'adresse du texte en question ;)), je me trouvais devant un problème que je n'avait jamais rencontré : certaines lettres étaient manquantes et des octets étranges se trouvaient dans le texte.

Ne sachant pas comment résoudre ce problème (bah oui, je suis pas un super hackeur ;)), je me suis permis de poser la question à mes compatriotes du chan de Génération IX.

Après un petit moment, Orphis m'apprit qu'il s'agissait d'une compression de type RLE.

Pour une raison que j'ignore aujourd'hui (je m'en rappelle plus :p), je n'ai pas eu d'explications détaillées de cette compression à ce moment-là.
Cependant, le lendemain, Meradrin proposa de me l'expliquer.
Ni une, ni deux, j'ai ouvert mes 2 yeux et lu tout ce qu'il me racontait.

Aujourd'hui, après un long moment (presque un an) et des demandes incessantes de la part de Ti Dragon (:D), je vais moi-même essayer de vous expliquer cette compression.

C'est parti !!

 

2) A quoi ça sert ?

Et bien, il s'agit bien évidemment d'une compression et, comme toute compression, elle permet de réduire la taille de ce que l'on veut compresser (textes, images...).

Cependant, cette compression est plus souvent utilisée pour compresser des images que des textes pour la simple et bonne raison qu'elle compresse une suite d'octets identiques (2 ou plus).

Et comme tout le monde le sait, on trouve rarement des mots avec plus de 2 lettres identiques.

 

3) Comment ça marche ?

La compression RLE ou de son vrai nom : Run Length Encoding.

Toute compression RLE commence par un octet, appelé "skip", (tout du moins, c'est comme ça que Meradrin le nomme :)) qui fait office d'indicateur afin de savoir combien d'octets ne sont pas compressés.

Une fois ce nombre d'octets passé, on trouve un nouvel octet qui indique le nombre de fois que doit être répété l'octet qui suit.

Ensuite, on trouve un nouveau skip pour les prochains octets et ainsi de suite...

Donc pour résumé, on a 1 octet (skip) pour nous dire combien d'octets sont "normaux" puis 1 octet pour le nombre de répétition puis 1 octet à répéter puis un nouveau skip.

Prenons l'exemple bidon suivant : ABCCCCCCDEFG
En RLE, on pourrait écrire : <01>A<01>B<06>C<01>D<01>E<01>F<01>G où l'octet devant chaque lettre est l'octet de répétition.

Cependant, comme le dit Meradrin : "Mais ne trouves tu pas idiot de rajouter 1 octet pour dire qu'il y a 1 octet de répétition ?"

C'est pour ça que le skip existe : pour dire que les X prochains octets sont compressés ou non. Pour notre exemple, on pourrait donc écrire : <02>AB<06>C<04>DEFG où <02> et <04> sont des skip et un octet de répétition.

Cependant, ceci n'est pas un exemple tout à fait correct car certains bits du skip indiquent si les données sont compressées ou non, mais nous verrons cela plus concrètement dans l'exemple qui suit.

Tout le monde arrive à suivre ?

Quelle que soit la réponse, nous allons maintenant prendre un exemple concret 🙂

PS : Généralement les données sont codée ligne par ligne (comme dans notre cas) mais il existe des variantes où les données sont codées en colonnes voire en zigzag.

N'ayant pas d'exemple sous la main, je ne peux détailler ces variantes mais elles doivent fonctionner de la même façon.

 

4) Un petit exemple pour bien assimiler ce qui vient d'être dit

Nous allons étudier la compression RLE avec le jeu Double Dragon 3 sur NES.

Dans ce jeu, le texte d'introduction est compressé en RLE.

Premièrement, on peut se poser quelques questions :

- Q1 : Pourquoi avoir seulement compressé l'introduction et pas le reste du script ?
- R1 : Il est "inutile" de compresser du texte en RLE donc pas la peine de compresser le script.
Mais alors pourquoi l'introduction est compressée ?

- Q2 : Pourquoi les développeurs ont compressés du texte en RLE ? Alors qu'on va seulement pouvoir compresser 2 caractères sur 2 octets. Donc aucun gain de place.
- R2 : L'introduction du jeu comprend une image et du texte. Donc la seule explication que je vois est qu'ils ont compressé les images
de l'intro et comme le texte se trouve au même endroit, il a également été compressé. Peut-être qu'ils ont même compressé toute la bank...
Mais je peux rien affirmer car je n'ai pas vérifié 😉

Bref, revenons à nos moutons : munissez-vous de votre éditeur hexadécimal préféré (pour moi ce sera Translhextion).

Ouvrez votre rom (Double Dragon III - The Sacred Stones (U).nes) et rendez-vous à l'adresse : 0x011373
(J'ai utilisé le (U) car la (E) avait planté chez moi)

Nous nous trouvons en face d'un premier bloc de texte de l'introduction qui, comme vous le constaterez, est presque totalement visible excepté quelques passages.

-------Texte compressé-------
MA<00>YEAR HAS<00>P
A<02>SHED SINCE)<00>BB
I<02>MHY<00>AND<00>JI<02>MJY
<00>DEFEATED(<00>MTHE<00>
SHADOW<00>WA<02>REIORS
.
-----------------------------

------Texte décompressé------
A YEAR HAS PASSED SINCE
BIMMY AND JIMMY DEFEATED
THE SHADOW WARRIORS.
-----------------------------

Tout d'abord, je signale que les <00> correspondent à des espaces mais les espaces normaux existent aussi et je n'ai pas compris (pas vraiment cherché) la différence.

Nous avons appris précédemment que la compression RLE commençait toujours par un octet (skip).

Etant donné que la première lettre de notre texte est le "A" de "A YEAR", on peut en déduire que le "M" qui précède est notre skip.
Ici, la valeur hexadécimal de "M" est 0x4D.

Pour notre exemple, Meradrin m'a appris que les 3 premiers bits du skip indiquent si les prochains octets sont compressés ou non.

Pour savoir cela, il a regardé le code ASM du jeu mais si vous ne connaissez pas l'ASM (comme moi), la seule solution est de faire des tests en modifiant les octets.

ATTENTION !!
Pour ce cas présent, les 3 premiers bits nous renseignent sur les octets compressés ou non mais pour un autre jeu, cela peut être complètement différent.

Donc, 0x4D en binaire donne : 0100 1101.
Les 3 premiers bits (010) nous indiquent que les prochains caractères ne sont pas compressés.

Il nous reste 01101 que l'on transforme en décimal = 13.

On sait maintenant que les 13 prochains octets après le "M" ne sont pas compressés.
Et c'est bien le cas :

 A      1
 <00>   2
 Y      3
 E      4
 A      5
 R      6
        7
 H      8
 A      9
 S      10
 <00>   11
 P      12
 A      13

Les 2 octets suivants correspondent à l'octet de répétition et à l'octet à répéter : <02>S

Ici 02 donne en binaire : 0000 0010

Donc les 3 premiers bits (000) nous indiquent que les données sont compressées et le reste (00010) signifie que l'on doit répéter 2 fois la lettre "S", pour avoir le mot "PASSED".

L'octet qui suit, "H" (0x48 = 010 01000) est un nouveau skip de 8 octets cette fois.

 E 1
 D 2
   3
 S 4
 I 5
 N 6
 C 7
 E 8

Puis on répète 9 fois l'octet <00> qui correspond à des espaces et ainsi de suite jusqu'à la fin du texte.

Par contre, je n'ai pas saisi la différence entre l'octet de répétition <02> et <29>. Ca a l'air de ressembler à un multiplicateur du nombre d'octets à répéter.

 

5) Crédits

* Auteur et apprenti : BahaBulle
* Explications : Meradrin
* Forums : tous les romhackeurs et traducteurs s'amusent sur http://romhack.org
* Chans IRC : #generation_ix et #finaltranslation sur le serveur irc.worldnet.net

Si vous avez des remarques et des suggestions à faire, n'hésitez pas à contacter l'auteur de ce tutoriel, BahaBulle.

Meradrin préfère rester dans l'ombre et continuer à voler au secours du romhackeur en détresse et du traducteur orphelin (car il n'a pas de romhackeur assez compétent pour lui extraire les textes de son jeu favori).

 

6) Remerciements

Je remercie bien évidemment Meradrin pour m'avoir expliqué la compression RLE.

Je remercie également les personnes qui ont répondu à mes questions avant l'intervention de Meradrin : Oprhis, SOR et j'en passe 😉

 

7) Légalité

Ce tutoriel a été écrit par BahaBulle sur les explications de Meradrin.

Vous êtes libres de l'utiliser comme bon vous semble mais nous ne pourrons être tenus responsables de quoi que ce soit vis à vis de son utilisation. Nous demandons juste que vous conserviez le fichier en l'état, sans rien y changer.

Ce tutoriel est GRATUIT et ne peut en aucun cas être vendu, vous ne pouvez tirer aucun profit de ce fichier et de son contenu.

MERCI !!

Adviennes que pourra