Run Length Encoding

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

Le codage RLE - Run Length Encoding (codage des répétitions) permet la compression de données en se basant sur la répétition successive de caractères, couleur, etc. Etant donné que l'on a assez peu de répétitions de caractères dans les mots écrits à l'aide de l'alphabet latin (on ne voit guère que des doublements de consonnes en français), on utilisera principalement cet algoritme pour les images dont le nombre de couleurs maximum est limité (8, 16 ou 256 couleurs) de manière à favoriser les répétitions.


Introduction

Un jour comme un autre, (enfin, c'est ce que je croyais), PERIGOURDIN (un jeune ROMhackeur du groupe Génération IX), vint me demander de l'aide pour un jeu qu'il était en train de ROMhacker. Ma générosité se fit entendre à ce moment-là et je pris donc la ROM dudit jeu afin de jeter un oeil au 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 casse-tête que je n'avais 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 qui rôdent sur IRC (chan de Génération IX). Après un petit moment, Orphis (ROMhackeur très doué de Final Translation) m'apprit qu'il s'agissait d'une compression de type 'RLE - Run Length Encoding'.

Pour une raison que j'ignore aujourd'hui (je ne m'en rappelle plus, à vrai dire), je n'ai pas eu d'explications détaillées de cette compression à ce moment-là. Cependant, le lendemain, Meradrin (autre fantastique ROMhackeur de Final Translation) 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 (le ROMhackeur qui ne programme pas), je vais moi-même essayer de vous expliquer cette compression.

C'est parti !!

A quoi ça sert le codage RLE ?

Eh 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, etc.) : il y a une vingtaine d'année, la place était un luxe dont nous ne souffrons plus trop aujourd'hui. Du coup, pour gagner de la place, on cherchait à compresser les données. Parmi les algorithmes de compression, il y a le RLE.

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.

Comment ça marche ?

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ésumer, 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, et enfin 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 <XX> devant chaque lettre est un octet de répétition (il indique combien de fois est répétée la lettre qui le suit).

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 cela que le 'skip' existe : il permet de dire si 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 <06> un octet de répétition.

Cependant, ceci n'est pas un exemple tout à fait correct car, en réalité, 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 !


Remarque : généralement, les données sont codées 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.

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

Nous allons étudier la compression RLE dans la ROM du jeu Double Dragon 3 sur NES. En effet, dans ce jeu, le texte d'introduction est compressé en RLE.

Dans un premier temps, on peut se poser quelques questions :

  • Q1 : Pourquoi avoir seulement compressé l'introduction et pas le reste du script ?
  • 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... Il n'y aura donc aucun gain de place.

Pour l'instant, je vous propose les réponses suivantes :

  • R1 : Il est "inutile" de compresser du texte en RLE (comme on l'a dit au tout début) donc pas la peine de compresser le script. Mais alors, pourquoi l'introduction est-elle compressée sacré bon sang d'bonsoir ?
  • R2 : L'introduction du jeu comprend une image et du texte. Donc, la seule explication est qu'ils ont compressé tout le bloc : les images de l'intro et le texte qui se trouve au même endroit. Du coup, on se retrouve dans le cas "logique" où le codage RLE permet de compresser une image.


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

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

Dans le jeu, le texte (décompressé) apparaît de la manière suivante :

  A YEAR HAS PASSED SINCE
  BILLY AND JIMMY DEFEATED
  THE SHADOW WARRIORS.

Nous avons appris précédemment que la compression RLE commençait toujours par un octet, le '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 assembleur (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. Rappelez-vous que je me base sur un exemple et vous devrez n'en retenir que les principes (la méthode générale).


Cette précision étant faite, revenons à notre compression : 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 <00> sont des espaces mais je ne sais pas trop pourquoi les programmeurs ont utilisé deux valeurs différentes pour les définir : dès fois, il ne vaut mieux pas chercher à comprendre)

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 en binaire) est un nouveau skip de 8 octets cette fois (vous noterez une nouvelle fois le 010 qui indique qu'il s'agit d'un skip puis les cinq octets suivants qui indiquent le nombre de lettres à passer) :

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

Puis, si vous avez bien suivi ce document, vous verrez qu'on répète 9 fois l'octet <00> qui correspond à des espaces et ainsi de suite jusqu'à la fin du texte.


Il reste cependant une toute petite zone d'ombre : 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 (ce qui peut être tout à fait plausible : après tout, si les 3 premiers bits indiquent une commande, il y aura donc 8 commandes possibles à définir en comptant celle définissant le 'skip' et celle définissant qu'il y a un octet à compresser).