Deflate
Algorithme utilisé par Up ! System
L'algorithme Deflate est une combinaison de la méthode Lempel et Ziv de 1977 (LZ77) et de celle d'Huffman. Il est du à l'Internet Engineering Task Force (IETF).
Il s'agit de l'algorithme le plus efficace à ce jour nonobstant la typologie du flux à compresser.
Cet algorithme est une norme étant donné que chaque paramètre des méthodes sont fixés par des constantes.
De nombreuses applications, standards ou normes utilisent cet l'algorithme. Par exemple, les commandes compress, gzip, pkzip ou les images au format Portable Network Graphic (PNG).
Méthode LZ77
L'algorithme mis au point par les mathématiciens Lempel et Ziv en 1977 (LZ77) a pour principe de coder sur un paquet de bits les suites d'octets qui se répètent.
La répétition est recherchée dans une fenêtre glissante sur le flux se terminant à la position courante dans le flux.
La répétition est caractèrisée par un couple (Distance, Longueur) où :
- Distance représente la distance en octets entre la position courante dans le flux et le modèle de répétition dans la fenêtre.
La distance est donc inférieure à la taille de la fenêtre.
- Longueur représente la longueur en octets de la répétition.
La longueur est donc inférieure à la taille de la fenêtre.
La taille minimale d'une suite d'octets se répétant est trois octets. La taille minimale d'un codage d'une suite d'octets est 9 bits. La taille minimale du codage d'un octet n'appartenant à aucune suite est 9 bits.
Le codage en bits le plus simple possible est le suivant :
- Premier bit à 0.
L'octet suivant n'est pas répété. Les huit bits qui suivent sont ceux de l'octet.
- Premier bit à 1.
Les octets suivants sont répétés. Les seize bits qui suivent sont ceux de la distance et les seize suivants sont ceux de la longueur.
Cela suppose que la taille de la fenêtre est au plus 65535.
Algorithme Deflate
L'algorithme Deflate est paramétré avec les valeurs suivantes :
- La taille de la fenêtre est 32768.
- La distance maximale est 32768.
- La longueur maximale est 255 + 3 = 258, puisqu'il faut au moins une répétition de trois octets.
Au lieu d'utiliser un codage simple pour reconnaître les répétitions, les distances et les longueurs, deux encodages Huffman sont utilisés.
- Un encodage pour les longueurs et les octets non répétés appelés litéraux.
- Un encodage pour les distances.
Ces encodages Huffman ont des caractéristiques particulières :
- Les encodages les plus courts sont utilisés avant les plus longs.
Par exemple, 0 puis 10, puis 110, etc.
- Pour une longueur de code donnée, les codes correspondants sont alloués par ordre croissant aux valeurs classées par ordre croissant.
Par exemple, 000 puis 001, puis 010, etc.
- Les valeurs non encodées non aucun code.
Par exemple, si les distances 18 et 20 sont utilisées mais par 19, alors cette dernière n'a pas de code et ceux de 18 et 19 sont consécutifs.
Il en résulte que, connaissant les longueurs de codes pour chaque valeur, il est possible de calculer les codes correspondants.
Un flux compressé par la méthode Deflate est découpé en tronçons, de taille variable, pouvant être compressé ou non.
Les premiers bits formant l'en-tête du bloc indiquent leur nature :
- Bit 1 - Témoin de dernier bloc.
Le bit vaut 1 s'il s'agit du dernier bloc et 0 sinon.
- Bits 2 à 3 - Mode de compression.
00 signifie que le contenu du bloc n'est pas compressé.
01 signifie que le contenu du bloc est compressé en employant les tables de statistiques Huffman par défaut.
10 signifie que le contenu du bloc est compressé en employant des tables de statistiques Huffman spécifiques.
11 est une situation impossible.
Bloc non compressé
La lecture du flux est recalé sur un octet entier. Les bits résiduels de l'octet en cours de lecture sont donc ignorés.
Le format d'un bloc non compressé est le suivant :
- Les deux premiers octets représentent le nombre d'octets non compressés.
Cette taille limitée à 32768 est encodée en big endian.
- Les deux seconds octets représentent le complément à deux de la valeur précédente.
- Les octets non compressés.
Bloc compressé avec les tables de statistiques Huffman par défaut
Pour les littéraux et les longueurs, étant donné qu'il existe 256 valeurs à distiguer plus une pour savoir s'il s'agit d'un littéral ou d'une longueur, le codage Huffman normalisé devrait comporter de 1 à 257 bits soit plus de 32 octets !
Aussi, un codage spécial est employé :
- Codage direct pour les littéraux.
De 0 à 143, le codage est sur 8 bits.
De 144 à 255, le codage est sur 9 bits.
- Codage direct pour la marque de fin de bloc.
La marque de fin de bloc est 256. Son codage est sur 9 bits.
- Codage par plages pour les longueurs.
Le codage indique la plage. Un complément codé sur des bits supplémentaires qui suivent le codage indique permet de calculer la valeur :
Valeur = DebutPlage + Complement avec Complement Entre 0 Et FinPlage-DebutPlage.
| Code. | Taille du code
en nombre de bits. | Longueur. | Nombre de bits
du complément. |
| 257 | 7 | 3 | 0 |
| 258 | 7 | 4 | 0 |
| 259 | 7 | 5 | 0 |
| 260 | 7 | 6 | 0 |
| 261 | 7 | 7 | 0 |
| 262 | 7 | 8 | 0 |
| 263 | 7 | 9 | 0 |
| 264 | 7 | 10 | 0 |
| 265 | 7 | 11 à 12 | 1 |
| 266 | 7 | 13 à 14 | 1 |
| 267 | 7 | 15 à 16 | 1 |
| 268 | 7 | 17 à 18 | 1 |
| 269 | 7 | 19 à 22 | 2 |
| 270 | 7 | 23 à 26 | 2 |
| 271 | 7 | 27 à 30 | 2 |
| 272 | 7 | 31 à 34 | 2 |
| 273 | 7 | 35 à 42 | 3 |
| 274 | 7 | 43 à 50 | 3 |
| 275 | 7 | 51 à 58 | 3 |
| 276 | 7 | 59 à 66 | 3 |
| 277 | 7 | 67 à 82 | 4 |
| 278 | 7 | 83 à 98 | 4 |
| 279 | 7 | 99 à 114 | 4 |
| 280 | 8 | 115 à 130 | 4 |
| 281 | 8 | 131 à 162 | 5 |
| 282 | 8 | 163 à 194 | 5 |
| 283 | 8 | 195 à 226 | 5 |
| 284 | 8 | 227 à 257 | 5 |
| 283 | 8 | 258 à 258 | 0 |
Pour les distances, étant donné qu'il existe 32768 valeurs à distiguer, le codage Huffman normalisé devrait comporter de 1 à 32768 bits soit plus de 4096 octets !
Aussi, un codage par plage est également employé :
| Code. | Taille du code
en nombre de bits. | Distance. | Nombre de bits
du complément. |
| 0 | 5 | 1 | 0 |
| 1 | 5 | 2 | 0 |
| 2 | 5 | 3 | 0 |
| 3 | 5 | 4 | 0 |
| 4 | 5 | 5 à 6 | 1 |
| 5 | 5 | 7 à 8 | 1 |
| 6 | 5 | 9 à 12 | 2 |
| 7 | 5 | 13 à 16 | 2 |
| 8 | 5 | 17 à 24 | 3 |
| 9 | 5 | 25 à 32 | 3 |
| 10 | 5 | 33 à 48 | 4 |
| 11 | 5 | 49 à 64 | 4 |
| 12 | 5 | 65 à 96 | 5 |
| 13 | 5 | 97 à 128 | 5 |
| 14 | 5 | 129 à 192 | 6 |
| 15 | 5 | 193 à 256 | 6 |
| 16 | 5 | 257 à 384 | 7 |
| 17 | 5 | 385 à 512 | 7 |
| 18 | 5 | 513 à 768 | 8 |
| 19 | 5 | 769 à 1024 | 8 |
| 20 | 5 | 1025 à 1536 | 9 |
| 21 | 5 | 1537 à 2048 | 9 |
| 22 | 5 | 2049 à 3072 | 10 |
| 23 | 5 | 3073 à 4096 | 10 |
| 24 | 5 | 4097 à 6144 | 11 |
| 25 | 5 | 6145 à 8192 | 11 |
| 26 | 5 | 8193 à 12288 | 12 |
| 27 | 5 | 12289 à 16384 | 12 |
| 28 | 5 | 16385 à 24576 | 13 |
| 29 | 5 | 24577 à 32768 | 13 |
Le format d'un bloc compressé avec les tables par défaut est le suivant :
- Lecture du code Huffman d'un littéral, de la marque de fin de bloc ou d'une longueur.
Le code étant écrit sur le nombre de bits indiqués précédemment, le flux est lu bit à bit pour construire incrémentalement un code faisant partie de la table des codes des littéraux et des longueurs. - Si le code ne fait pas partie de la table des codes des littéraux et des longueurs quand le nombre de bits maximum est lu alors le flux compressé est erroné.
- Si le code désigne une plage non réduite à une valeur alors lecture des bits du complément et calcul de la valeur.
- Si la valeur est comprise entre 0 et 255, alors il s'agit d'un littéral i.e. d'un octet non répété.
- Ecriture de l'octet non répété dans le flux non compressé.
- Bouclage.
- Si la valeur est 256, alors la fin du bloc est atteinte.
- Si la valeur est comprise entre 257 et 283, alors il s'agit d'une longueur d'une répétition.
- Lecture du code Huffman de la distance.
Le code étant écrit sur le nombre de bits indiqués précédemment, le flux est lu bit à bit pour construire incrémentalement un code faisant partie de la table des distances. - Si le code ne fait pas partie de la table des distances quand le nombre de bits maximum est lu alors le flux compressé est erroné.
- Si le code désigne une plage non réduite à une distance alors lecture des bits du complément et calcul de la distance.
- Si la distance renvoie avant le début du flux alors le flux compressé est erroné.
- Recopie des octets désignés.
- Bouclage.
Bloc compressé avec des tables de statistiques Huffman par défaut
Pour construire les tables Huffman, seules les longueurs de codes sont utiles pour chaque valeur avec le nombre maximal de valeurs.
Elles sont encodées en utilisant également une table Huffman.
Le format d'un bloc compressé avec les tables spécifiques est le suivant :
- Bits 1 à 5 : Nombre N1 de codes pour les littéraux et de longueurs.
Cette valeur à laquelle il faut ajouter 257 limite les codes des longueurs à 31, comme dans la table par défaut.
Le même codage par plage avec des bits pour un complément est utilisé.
- Bits 6 à 10 : Nombre N2 de codes pour les distances.
Cette valeur à laquelle il faut ajouter 1 limite les codes des distances à 32, comme dans la table par défaut.
Le même codage par plage avec des bits pour un complément est utilisé.
- Bits 11 à 14 : Nombre N3 de codes pour les codes de littéraux ou de longueurs.
Cette valeur à laquelle il faut ajouter 4 limite les codes pour les codes de littéraux ou de longueurs à 19.
- Bits 15 à 15 + (N3+4) * 3 : N3+4 codes de longueur de codes.
Une valeur de 0 signifie que le code n'est pas employé.
Un codage par plage avec des bits pour un complément est utilisé :
| Code. | Taille du code
en nombre de bits. | Code. | Nombre de bits
du complément. |
| 0 | 3 | 0 | 0 |
| 1 | 3 | 1 | 0 |
| 2 | 3 | 2 | 0 |
| 3 | 3 | 3 | 0 |
| 4 | 3 | 4 | 1 |
| 5 | 3 | 5 | 1 |
| 6 | 3 | 6 | 2 |
| 7 | 3 | 7 | 2 |
| 8 | 3 | 8 | 3 |
| 9 | 3 | 9 | 3 |
| 10 | 3 | 10 | 4 |
| 11 | 3 | 11 | 4 |
| 12 | 3 | 12 | 5 |
| 13 | 3 | 13 | 5 |
| 14 | 3 | 14 | 6 |
| 15 | 3 | 15 | 6 |
| 16 | 3 | 16 à 19 | 2 |
| 17 | 3 | 20 à 27 | 3 |
| 18 | 3 | 28 à 155 | 7 |
Ces longueurs de codes sont énumérées dans l'ordre 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1 et 15 !
- Bits ? à ? : N1 codes des longueurs de codes des littéraux et des longueurs.
Une valeur de 0 signifie que le littéral ou ou la longueur n'est pas employée.
- Bits ? à ? : N2 codes des longueurs de codes des distances.
Une valeur de 0 signifie que la distance n'est pas employée.
Le reste du format d'un bloc compressé est identique à celui de la section précédente.
Exemple d'un flux compressé par l'algorithme Deflate
Flux non compressé
/* ------------------------------------------------------------------- */
/* Fichier : clientftp.upl */
/* Objet : Exemple d'emploi d'Up ! Network. */
/* */
/* Module : Up ! Application System. */
/* Auteur-Date : DUVAL Jean-Pierre - Novembre 2003. */
/* ------------------------------------------------------------------- */
/* Observations */
/* */
/* */
/* ------------------------------------------------------------------- */
Source Composant "Exemple d'emploi d'Up ! Network" Version 4.0.0;
ImporterModule
UpsFts(, ImporterDefinitions);
Variable
/******/
MonServeur : Nul Ou ServeurFtp;
Principal
/*******/
Debut
MonServeur=ServeurFtp("ftp://local:21");
MonServeur.ChangerConnexion("anonymous", "contact@mon-domaine.com");
MonServeur.ChangerEtatTypeDonnees(TypeDonneesAscii);
CopierFichier("C:/tmp2/essai.txt", "ftp://local:21/tmp/essai.txt");
MonServeur.ChangerEtatTypeDonnees(TypeDonneesImage);
CopierFichier("ftp://local:21/tmp/essai.doc", "C:/tmp2/essai.doc");
MonServeur=Nul;
Fin Principal
Flux compressé
00000000 abeb 4a0b abab a044 1091 2136 25a8 e250 +kJ.++ D..!6%(bP
00000010 84a0 b4be 7405 8976 9993 9899 95a2 5050 . 4>t..v....."PP
00000020 5050 6a50 939c 9995 9ea4 96a4 a05e a5a0 PPjP.....$.$ ^%
00000030 9c04 8408 618b 1253 e20c 8462 5fe4 a6a5 ....a..Sb..b_d&%
00000040 6902 2035 283a d44a ced0 4e4a a84a 2b82 i. 5(:TJNPNJ(J+.
00000050 2e7e 6409 885a 0505 1507 e95a 4a79 fa29 .~d..Z....iZJyz)
00000060 b5e1 3262 44fd b913 5726 fb3f 294a 05c2 5a2bD}9.W&{?)J.B
00000070 8572 80dc 0b8d 0504 e4cc 9c8d 24cc fcf2 .r.\....dL..$L|r
00000080 841d 4d1d 24ac e896 b8c1 2162 1c69 6925 ..M.$,h.8A!b.ii%
00000090 6968 975d 2469 2540 b10e 90b0 ce2f 8a0f ih.]$i%@1..0N/..
000000a0 52b2 33cb b000 60f2 8a55 4175 41fa 7e9a R23K0.`r.UAuAz~.
000000b0 5676 4809 a626 0606 312a 6482 3124 8c5d VvH.&&..1*d.1$.]
000000c0 0973 b27f 92a3 95a2 a606 f8a8 c4ea 0988 .s2..#."&.x(Dj..
000000d0 d870 5024 98a2 4a0a 4ea0 e7e9 68a4 e554 XpP$."J.N gih$eT
000000e0 1ce7 e768 27e8 e467 a914 1484 d253 aa4a .ggh'hdg)...RS*J
000000f0 10d2 b454 60a4 40c2 bcc4 bcc0 d674 74f2 .R4T`$@B<D<@Vttr
00000100 0575 4549 2b44 1649 e740 5d24 2d05 1bb5 .uEI+D.Ig@]$-..5
00000110 2502 c360 42db 9714 0328 dd25 65a6 67a6 %.C`B[...(]%e&g&
00000120 41c3 e2c8 15d4 348d 14cc 8c94 e4a8 17a2 ACbH.T4..L..d(."
00000130 b4b4 044b e097 8fb3 f3d0 6062 880c 9480 44.K`..3sP`b....
00000140 c935 fa96 7141 fe95 402a 0016 300a d602 I5z.qA~.@*..0.V.
00000150 8a66 7a4e 6682 4670 32d8 0add d256 4a96 .fzNf.Fp2X.]RVJ.
00000160 90e8 42e9 b442 c561 4823 866a 5f5f 9c9f .hBi4BEaH#.j__..
00000170 9391 9c6a 6261 5204 de08 562f 39cc 48cf ...jbaR.^.V/9LHO
00000180 4bca d139 cfcf 4f4a d401 738b 0a52 33d3 KJQ9OOOJT.s..R3S
00000190 f3d5 33b3 f4b4 6a4b 8a0a 5273 f3d4 9232 sU33t4jK..RssT.2
000001a0 748e 14b4 0bb2 6060 a178 0900 9811 2760 t..4.2``!x....'`
000001b0 1d69 2469 212a 6825 5d01 3112 b46b 0240 .i$i!*h%].1.4k.@
000001c0 6dc6 8e4e 6664 0ad1 ce7e 800c c542 d0b2 mF.Nfd.QN~..EBP2
000001d0 b0a4 e6d4 bf49 3b40 c4bf 2b47 4723 32bd 0$fT?I;@D?+GG#2=
000001e0 4951 4809 af12 675e 0946 240a 2196 ede6 IQH./.g^.F$.!.mf
000001f0 7646 5e54 49db b131 69a5 27e4 c138 9123 vF^TI[11i%'dA8.#
00000200 73c0 9104 89bb 6d03 13cd 674e d333 ca02 s@...;m..MgNS3J.
00000210 224c e800 "Lh.