La compression de Huffman

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

Le codage de Huffman est un algorithme de compression qui fut mis au point en 1952 par David Huffman. C'est une compression de type statistique qui, par exemple (pour ce qui concerne le ROMhacking et la traduction de jeux vidéos), analyse la fréquence d'apparition de lettres ou groupes de lettres afin de leur attribuer le moins de bits possible : étant utilisées plus souvent sur un nombre de bits réduits, elles prennent moins de place qu'un codage classique sur 8 ou 16 bits. On comprend très vite l'intérêt de ce genre de compression dans un script de jeux vidéos.

Introduction

Un jour, je discutais avec Meradrin (grand bidouilleur devant l'Eternel). Ce dernier ROMhackait Shining Force 2 sur Mega Drive. Les Shining Force sont réputés pour leur compression pourrie qui ne ravit guère les gens qui ont tenté d'en extraire les textes et pour cause... il s'agit d'une compression de type Huffman. Contrairement au LZXX, cette compressoin ne laisse RIEN voir des textes qui se trouve dans le jeu. J'ai alors demandé à Meradrin de m'expliquer ce qu'était EN GROS le Huffman.

Et il a pris un exemple pour m'expliquer. Donc, je ne vais pas vous faire de cours théorique sur ce qu'est la compression Huffman. Je vais tout simplement utiliser l'exemple qu'il m'a donné pour que vous compreniez bien COMMENT on compresse en Huffman.

Je n'expliquerai pas le point de vue purement mathématique de la compression (notamment le fait que ce codage soit bijectif). Le but est de faire comprendre comment fonctionne l'algoritme par un exemple simple.

La phrase d'exemple qui tue

Toute l'explication s'appuiera de cette phrase magique et mythique prononcée par Meradrin lui-même :

  vive toto le toto

A partir de là, notre explication peut commencer.

De l'intérêt de savoir compter

Comme je le disais plus haut, la compression de Huffman s'appuie sur une analyse de fréquence d'apparition des lettres de l'alphabet (lorsque l'on analyse un script, bien entendu). Ainsi, dans un premier temps, nous allons compter les occurences de chaque lettre :

  v = 2
  i = 1
  l = 1
  e = 2
  t = 4
  o = 4
  _ = 3

On remarque donc que certaines lettres sont plus fréquentes que d'autres. Par exemple, le t apparaît 4 fois alors que le i n'apparaît qu'une seule fois. On voit déjà dans cette première étape que beaucoup de lettres ne vont pas être codées, ce qui constitue en soit une première mini compression.

Dans le domaine des jeux vidéos, les lettres sont codées en 8 bits (1 octet) voire 16 bits (2 octets). Le codage sur un octet (256 caractères maximum) correspond souvent à l'utilisation d'alphabets alors que le codage sur 2 octets (65 536 caractères maximum) correspond davantage à l'utilisation d'idéogrammes (kanji japonais, hanzi chinois, etc.). Il serait également possible d'encoder des mots entiers ou des groupes de lettres (on pourrait y ajouter une DTE - Dual Tile Encoding - Codage en Double Caractère) si cela en vallait le coup. Il n'y a aucune restriction dans le nombre d'octets choisis pour encoder ni dans ce que l'on souhaite encoder.

Bref, sachant qu'un octet fait 255 caractères, on va garder un système de codage d'un octet par lettre, ce qui est largement suffisant pour notre alphabet. Cela sera d'autant plus facile à comprendre.


Trier pour mieux s'y retrouver

Principe relativement simple que de trier - votre mère vous répétait assez souvent "RANGE TA CHAMBRE" lorsque vous veniez vous plaindre "je ne retrouve plus mon jeuuuuuuu, bouhouhou". Eh bien votre mère saurait probablement faire cette partie mieux que vous. Il faut en effet ranger les lettres par leur nombre d'occurences. Allons-y :

  1  'o'
  2  't'
  3  ' '
  4  'v'
  5  'e'
  6  'l'
  7  'i'

Voici donc la première colonne de ce que l'on appelle un "tableau de Huffman". On pourrait également utiliser un "arbre de Huffman". Mais mettez ces termes de côté, car le tout est de comprendre le principe. Après, rien ne vous empêchera de vouloir en savoir plus en fouillant le web ou en faisant de la structure de données et du C.

Ceci constitue donc le premier tri. Le but est de rajouter des colonnes de plus en plus petites de manière à créer un escalier ; dans le cas d'un arbre, on part des feuilles et on remonte vers le tronc en passant par les branches (c'est peut-être plus explicite ainsi). Si vous ne comprenez pas tout de suite, ce n'est pas grave car voici vomment il faut procéder.

Additonner, c'est tellement simple

De manière à donner plus d'importances aux lettres de "poids faible" (peu d'occurence), on prend concatène les deux dernières lettres puis on additionnez leur nombre d'occurence. Dans un arbre, on associe donc deux noeuds (intersection de deux branches).

Pour notre exemple, il faut concaténer 'l' et 'i' --> 'li' et le nombre d'occurence devient 1 + 1 = 2 ("c'est un point de vue" selon certain mais ne nous dispersons pas). En effet, sur ce noeud, on détermine le nombre d'occurences de "soit l, soit i".

A présent, il faut retrier tout ça, ce qui nous amène une nouvelle colonne :

  1  'o'  = 4
  2  't'  = 4
  3  ' '  = 3
  4  'v'  = 2
  5  'e'  = 2
  6  'li' = 2

Les '=' sont là à titre indicatif mais notez-les bien. Voici donc notre nouveau tableau :

   _________________
  |   |  1   |  2   |
  |---|------|------|
  | 1 | 'o'  | 'o'  |
  | 2 | 't'  | 't'  |
  | 3 | ' '  | ' '  |
  | 4 | 'v'  | 'v'  |
  | 5 | 'e'  | 'e'  |
  | 6 | 'l'  | 'li' |
  | 7 | 'i'  |      |
   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Je pense que vous commencer à comprendre pourquoi on parle d'escalier. Si ce n'est pas encore très clair alors passons à l'étape suivante.

Là encore, il vous faut choisir dans notre tableau, les deux groupements de lettre(s) qui ont le moins d'occurences. Ici, il s'agit de 'li' et 'e' --> 'eli'. Le nombre d'occurences de "soit 'e', soit 'l', soit 'i'" devient donc 2 + 2 = 4. Ainsi, une nouvelle colonne est créée en fonction du nombre d'occurences :

  1  'o'   = 4
  2  't'   = 4
  3  'eli' = 4
  4  ' '   = 3
  5  'v'   = 2

Ce qui nous amène inévitablement à un nouveau tableau :

   ___________________________
  |   |   1   |   2   |   3   |
  |---|-------|-------|-------|
  | 1 |  'o'  |  'o'  |  'o'  |
  | 2 |  't'  |  't'  |  't'  |
  | 3 |  ' '  |  ' '  | 'eli' |
  | 4 |  'v'  |  'v'  |  ' '  |
  | 5 |  'e'  |  'e'  |  'v'  |
  | 6 |  'l'  |  'li' |       |
  | 7 |  'i'  |       |       |
   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Allez, je vous laisse faire le tableau complet. Avant d'aller plus loin, essayez donc de faire la colonne suivante et, si vous vous sentez d'attaque, essayez donc de faire le reste du tableau.

(lalali lalaaaa lalilalaaa lalalalalalaliiii la laaa - musique d'ambiance)

Mmmmh ? Ca y est ? Alors voici ce que vous pouvez obtenir si vous avez bien suivi le système de 'concaténation', 'calcul du nombre d'occurences' puis 'tri des occurences'.

Les colonnes manquantes :

  ' v'  = 5      'teli' = 8       ' vo'  = 9       ' voteli' = 17
  'o'   = 4      ' v'   = 5       'teli' = 8
  't'   = 4      'o'    = 4
  'eli' = 4

Le tableau final (nous n'avons pas besoin de la dernière colonne : c'était pour savoir si vous aviez bien compris le principe) :

   _______________________________________________________________
  |   |    1    |    2    |    3    |    4    |    5    |    6    |
  |---|---------|---------|---------|---------|---------|---------|
  | 1 |   'o'   |   'o'   |   'o'   |   ' v'  | 'teli'  |  ' vo'  | 
  | 2 |   't'   |   't'   |   't'   |   'o'   |  ' v'   | 'teli'  |
  | 3 |   ' '   |   ' '   |  'eli'  |   't'   |   'o'   |         |
  | 4 |   'v'   |   'v'   |   ' '   |  'eli'  |         |         |
  | 5 |   'e'   |   'e'   |   'v'   |         |         |         |
  | 6 |   'l'   |   'li'  |         |         |         |         |
  | 7 |   'i'   |         |         |         |         |         |
   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Notez que l'ordre des lettres concaténées n'a aucune importance.

Définir une nouvelle table

C'est une partie peut-être un peu plus ardue. Nous allons utiliser les écritures binaires, c'est-à-dire 1 ou 0 (pour rappel, l'hexadécimal est en base 16 alors que le binaire est en base 2).

Prenons notre tableau à l'envers, à savoir par la dernière colonne (la 6). Prenons les deux dernières lignes de celle-ci... bon, il n'y en a que deux alors vous ne devrier pas vous tromper. Ce sont en effet les deux noeuds de poids les plus forts, ceux qui contiennent le plus d'occurences d'apparition de lettres.

Pour toutes les lettres de la première des lignes sélectionnées, à savoir ' vo', nous allons poser un 1 et pour toutes les lettres de la seconde des lignes sélectionnées, à savoir 'teli', nous allons poser un 0. Voici donc notre table temporaire :

  ' '=1
  'v'=1
  'o'=1
  't'=0
  'e'=0
  'l'=0
  'i'=0

Passons maintenant à la colonne d'avant (la n°5, celle qui contient 'teli', ' v' et 'o'). Une nouvelle fois, prenons les 2 dernières lignes de cette colonne. Il s'agit de ' v' et 'o'. Procédez comme suit :

  • pour toutes les lettres de la première des lignes sélectionnées, à savoir ' v', nous allons poser un 1 derrière les nombres déjà posés précédemment ;
  • pour toutes les lettres de la seconde des lignes sélectionnées, à savoir 'o', nous allons poser un 0 derrière les nombres déjà posés précédemment ;
  • pour les lettres se trouvant dans les autres lignes, on ne met rien.

Voici donc notre nouvelle table temporaire :

  ' '=11
  'v'=11
  'o'=10
  't'=0
  'e'=0
  'l'=0
  'i'=0

Vous commencez à comprendre ce qu'il faut faire ? Si ce n'est pas le cas, on continue une troisième fois. Prenons la colonne encore d'avant (la n°4, celle qui contient ' v', 'o', 't', et 'eli') - n'oublions pas que l'on va dans le sens inverse, c'est-à-dire en partant de la droite du tableau. Prenons les 2 dernières lignes de cette colonne, à savoir 't' et 'eli'. Procédez une nouvelle fois de cette manière :

  • pour toutes les lettres de la première des lignes sélectionnées, à savoir 't', nous allons poser un 1 derrière les nombres déjà posés précédemment ;
  • pour toutes les lettres de la seconde des lignes sélectionnées, à savoir 'eli', nous allons poser un 0 derrière les nombres déjà posés précédemment
  • pour les lettres se trouvant dans les autres lignes, on ne met rien.

Voici donc notre nouvelle table temporaire :

  ' '=11
  'v'=11
  'o'=10
  't'=01
  'e'=00
  'l'=00
  'i'=00

Vous remarquez qu'on rajoute des bits de codage aux dernières lignes du tableau : de cette manière, les lettres qui apparaissement le plus souvent sont codées sur moins de bits ce qui leur permet de prendre moins de place !

A présent, vous devriez comprendre le principe de fabrication de la table. Il ne s'agit que de 1 et de 0 que l'on applique sur les lettres de poids le plus faible. Allez, je vous laisse essayer de trouver la table final en utilisant le même algorithme.

(tatatidiii daaa... tatatidiii daaa... taaa tatatatatatadidididaaaaa - autre musique)

Mmmmhhh ? Ca y est ? Donc, en continuant selon le même schéma, vous devriez obtenir la table binaire suivante :

  ' '=111
  'v'=110
  'o'=10
  't'=01
  'e'=001
  'l'=0001
  'i'=0000

Comme on peut le voir, le 'o' et le 't' ne font que 2 bits (ce sont les lettres les plus fréquentes - elle sont toujours restées en haut du tableau, ce qui fait qu'elles n'ont eu que peu de 0 et de 1) alors que le 'l' et le 'i' font 4 bits (ce sont les lettres les moins fréquentes - elles sont toujours restées en bas du tableau, dans les dernières lignes et ont donc souvent bénéficiés de l'ajout de 0 et de 1).


Compressons, compressons

Si les Shadocks pompaient, nous, nous allons compresser comme des fous ! Avec la table binaire obtenue, nous pouvons réécrire notre phrase de la façon suivante :

  'v'  'i'   'v'  'e'  ' '  't' 'o' 't' 'o' ' '  'l'   'e'  ' '  't' 'o' 't' 'o'
  110  0000  110  001  111  01  10  01  10  111  0001  001  111  01  10  01  10

Soit, en concaténant tout ça et en regroupant par groupe de 8 bits :

  11000001 10001111 01100110 11100010 01111011 00110

Et comme il nous manque des bits pour obtenir des octets entiers, on va rajouter des 0 à la fin, ce qui nous donne :

  11000001 10001111 01100110 11100010 01111011 00110000

Nous nous retrouvons donc avec une phrase compressée qui, en hexadécimal, va nous donner :

  C1 8F 66 E2 7B 30

Donc, vous voyez bien qu'en recherche relative, rien n'est apparent, même pas un bout de phrase (contrairement à la compression LZSS où l'on peut avoir quelques séquences de phrase). Nous avions 17 lettres au départ (soit 17 octets puisque nous avons pris en compte un codage des lettres sur un seul octet chacune), nous nous retrouvons avec 6 octets. Pas mal, hein ? Un taux de compression de 65% !

Pour décompresser, il FAUT connaître la table binaire ou le tableau/l'arbre de Huffman et c'est bien là qu'est la difficulté au niveau du ROMhacking.

Bref, on pourrait tout de même se demander si, en lisant tout ça, il n'y avait qu'une seule phrase possible. Eh bien faites le test : prenez votre table et essayer de faire une autre phrase. Commencez en partant du début de la séquence binaire. C'est tout simplement impossible. Il n'y a donc qu'une seule phrase possible (bijectivité de l'algoritme de compression d'Huffman - qui est démontré mathématiquement mais ce n'est pas le but de ce document) ! On se rend même compte que les 0 à la fin sont en trop. Bien que ces derniers puissent cependant créer des problèmes, il y a en général un octet de fin qui indique au programme qu'il doit arrêter de lire.

Du côté du code

Avant toute chose, sachez que cette partie est uniquement dédiée aux personnes ayant des connaissances en assembleur et en programmation. Bien entendu, les curieux peuvent venir y jeter un oeil (histoire de faire naître des vocations) mais n'attendez pas des détails poussés sur les morceaux de code développés ici.


Bref, la théorie, c'est sympa, mais il est intéressant de voir tout de même ce qu'il se passe du côté des jeux vidéos. Prenons pour exemple Shadowrun sur Super NES (un petit jeu de 1 Mo, mais costaud niveau programmation !). Tout est compressé (textes, graphismes) avec un algorithme de type Huffman. L'arbre fait 4 Ko (ce qui est plutôt gros, mais compréhensible vu qu'il concerne le texte ET les graphismes).

Voici donc la routine :

 1: $80/FE33: 8B           PHB
 2: $80/FE34: A9 FF 9D     LDA #$9DFF
 3: $80/FE37: 85 D0        STA $D0 [$00:00D0]
 4: $80/FE39: A5 02        LDA $02 [$00:0002]
 5: $80/FE3B: 10 02        BPL $02 [$FE3F]
 6: $80/FE3D: E6 D0        INC $D0
 7: $80/FE3F: 09 00 80     ORA #$8000
 8: $80/FE42: 85 CF        STA $CF [$00:00CF]
 9: $80/FE44: F4 7E 7E     PEA $7E7E [$80:7E7E]
10: $80/FE47: AB           PLB 
11: $80/FE48: AB           PLB
12: $80/FE49: 9C 22 02     STZ $0222 [$7E:0222]
13: $80/FE4C: E2 20        SEP #$20 
14: $80/FE4E: A0 00 00     LDY #$0000
15: $80/FE51: C2 20        REP #$20
16: $80/FE53: A9 00 00     LDA #$0000
17: $80/FE56: AA           TAX 
18: $80/FE57: 22 C0 AE 81  JSL $81AEC0 [$81:AEC0]

1 : Sauvegarde de la pile.

2 et 3 : Chargement de la bank où se situe le texte compressé. La bank est sur 16 bits, mais seul 0x9D sera utilisé. C'est un signe qu'une optimisation a eu lieu (et montre que cette routine a été programmée en assembleur). Il est enregistré dans $D1 (D0 contient le FF, et sera réécrit ensuite).

8 : On récupère l'autre partie de l'adresse du texte, qu'on enregistre dans $CF et $D0 (effaçant ainsi le 0xFF). Les autres lignes initialisent des variables, juste avant l'exécution de la fonction principale de décompression.

18: On saute vers la sous-routine décrite ci-dessous :

 1: $81/AEC0: CE 22 02     DEC $0222 [$7E:0222]
 2: $81/AEC3: 10 12        BPL $12 [$AED7]
 3: $81/AEC5: 48           PHA
 4: $81/AEC6: A9 0F 00     LDA #$000F
 5: $81/AEC9: 8D 22 02     STA $0222 [$7E:0222]
 6: $81/AECC: A7 CF        LDA [$CF] [$9D:F0C8]
 7: $81/AECE: EB           XBA
 8: $81/AECF: 8D 24 02     STA $0224 [$7E:0224]
 9: $81/AED2: E6 CF        INC $CF [$00:00CF]
10: $81/AED4: E6 CF        INC $CF [$00:00CF]
11: $81/AED6: 68           PLA
12: $81/AED7: 0E 24 02     ASL $0224 [$7E:0224]
13: $81/AEDA: 6B           RTL

1 : $7E:0222 est un compteur de lecture de l'arbre. Lors du premier passage, cette valeur devient négative, ce qui fait que le branchement au 2: ne sera jamais fait.

4 et 5 : L'arbre a une taille de 16 branches. On enregistre cela dans le compteur mentionné précédemment.

6 : Si vous avez bien tout suivi, vous savez que $CF contient le pointeur du texte compressé. Non ? Alors relisez mieux cette partie !

7 et 8 : On intervertit la chaine compressée lue précédemment, et on l'invertit avant de l'enregistrer dans $7E:0224

9 et 10 : Incrémentation du compteur de lecture de 2 octets. L'arbre a 16 branches et, donc, chaque bloc de données compressé est sur 2 octets (soit 16 bits).

12 : Le parcours de l'arbre se fait par lecture des bits. Le meilleur moyen est d'effectuer un décalage, d'où l'utilisation de l'opérateur ASL.


Après l'appel de la sous-routine, la décompression commence :

 1: $80/FE5B: 90 02        BCC $02 [$FE5F] 
 2: $80/FE5D: E8           INX
 3: $80/FE5E: E8           INX
 4: $80/FE5F: BF 00 80 9D  LDA $9D8000,X [$9D:8002]
 5: $80/FE63: 10 F1        BPL $F1 [$FE56]
 6: $80/FE65: 29 7F 7F     AND #$7F7F
 7: $80/FE68: EB           XBA
 8: $80/FE69: E2 20        SEP #$20
 9: $80/FE6B: C9 0A        CMP #$0A
10: $80/FE6D: F0 11        BEQ $11 [$FE80]
11: $80/FE6F: 99 A0 21     STA $21A0,Y [$7E:21A0]
12: $80/FE72: C8           INY
13: $80/FE73: EB           XBA
14: $80/FE74: F0 DB        BEQ $DB [$FE51]
15: $80/FE76: C9 0A        CMP #$0A
16: $80/FE78: F0 06        BEQ $06 [$FE80]
17: $80/FE7A: 99 A0 21     STA $21A0,Y [$7E:21A3]
18: $80/FE7D: C8           INY
19: $80/FE7E: 80 D1        BRA $D1 [$FE51]
20: $80/FE80: BB           TYX
21: $80/FE81: 9E A0 21     STZ $21A0,X [$7E:21A4]
22: $80/FE84: C2 20        REP #$20
23: $80/FE86: 20 03 FB     JSR $FB03 [$7E:FB03]

1 : Si vous avez bien révisé, vous devez connaître le comportement de ASL. BCC permet de savoir si un "1" ou un "0" a été lu, pour parcourir l'arbre.

2 et 3 : On a lu un 1, on augmente de 2 l'adresse de lecture de l'arbre.

4 : L'arbre se situe à $9D:8000. On charge 2 octets.

5 : Si cette valeur est supérieure à 0x7FFF, on continue la lecture de l'arbre

6 : Sinon, c'est qu'on a atteint la fin d'une branche, on a donc nos deux octets décompressés que l'on enregistre ensuite.

La suite du code sert à vérifier si c'est la fin de la phrase (9 et 15), et à enregistrer les données décompressées (17 et 21).

Le mot de la fin

Comme vous pouvez le constater, j'ai essayé de rester simple. Il y a certainement beaucoup d'autres choses cachées derrière tout ça. Néanmoins, vous connaissez à présent le principal, en ce qui concerne une compression statique. Il existe également la compression dynamique qui crée un arbre de Huffman "à la volée" de manière à optimiser la compression. Cependant, le temps de calcul peut être énorme. C'est pourquoi, il est plus simple de créer un arbre global sur l'ensemble d'un script plutôt que de s'attacher à des blocs.

En somme, on a compris comment les textes étaient compressés mais comment ROMhacker une ROM en connaissant ce principe ? Il n'y a pas de mystère : il faut s'armer d'un émulateur possédant un débugger et fouiller dans le code ASM lorsque le texte s'affiche. Meradrin dit lui-même "il faut des yeux magiques" : il faut regarder où se trouve la police dans la VRAM (ça peut compliquer les choses lorsque la police est une VWF - Variable Width Font, Police à Largeur Variable) puis remonter le code ASM qui va forcément indiquer à un moment donné la routine qui affiche le texte. A partir de là, évidemment, on se rend compte que ce n'est pas un affichage tout simple qui fait appel à des adresses où se trouvent les lettres. On tombe sur l'arbre de Huffman ou un truc encore plus horrible qui pourrait s'apparenter à ça.

Bref, il faut pas mal de pratique dans la programmation et en ASM pour trouver tout ça car c'est très loin d'être évident, même quand on a trouvé le principe.