Si vous avez lu les précédents chapitres, vous avez pu faire la découverte de différents algorithmes, notamment LZSS et LZW. Mais, parmi les algorithmes de compression, il y a une star que vous ignorez encore : c’est DEFLATE, un algorithme que vous retrouvez partout.
Vous décompressez un .ZIP ? C’est DEFLATE. Vous affichez un .PNG ? DEFLATE. Votre navigateur charge une page web décompressée ? Encore DEFLATE. Vous téléchargez le code source d’un programme, et il est compressé en .TAR.GZ ? Encore et une nouvelle fois du DEFLATE !
D’ailleurs, si votre navigateur charge un fichier .PNG, et que le serveur web re-compresse le contenu du fichier chargé à la volée, il n’est pas impossible que vous transfériez du DEFLATE dans du DEFLATE. C’est dire si cet algorithme, créé en 1993 et normalisé en 1996, est partout.
DEFLATE n’est pas entièrement différent de ce que nous avons vu jusqu’ici. C’est ce qu’on appelle un algorithme à fenêtre glissante, comme LZSS. Mais contrairement à LZSS, il utilise une petite astuce pour que les informations ainsi que les répétitions d’informations elles-mêmes prennent moins de place : les codes de Huffman.
- Le codage de Huffman : en dire autant avec des mots plus courts
- Le codage Huffman appliqué à DEFLATE
- Le fonctionnement de DEFLATE
- Un décodeur DEFLATE en Python
Le codage de Huffman : en dire autant avec des mots plus courts
Avant de commencer à vous parler de DEFLATE, je vais vous parler de codage de Huffman.
Pour vous faire comprendre ce que c’est, je ne vais pas tout de suite vous parler d’octets, mais d’abord de numéros de téléphones.
Comme vous le savez sans doute, il existe des numéros de téléphones de différentes tailles. Pour appeler les pompiers, c’est le 18, pour appeler le numéro du Père Noël 
, c’est le 36 30, et pour appeler la piscine Édouard Pailleron, c’est le 01 40 40 27 70.
Avec nos smartphones, et avec les téléphones fixes récents, vous composez d’abord votre numéro, et ensuite vous avez un bouton pour déclencher l’appel. Mais avec les vieux téléphones fixes, vous tapiez juste le numéro, vous attendiez quelques secondes, puis la sonnerie se déclenchait.
Quand j’étais petit, et que je devais composer un numéro, j’avais très peur de ne pas taper assez vite le numéro et que la sonnerie se déclenche avant que je n’aie fini de taper. (Heuresement, cela n’arrivait jamais.)
En réalité, je ne risquais vraiment pas d’appeler quelqu’un par erreur en n’allant pas assez vite. Pourquoi ? Parce que les numéros commencent différemment selon leur taille, ainsi plusieurs numéros de tailles différentes ne se recouvrent jamais. Par exemple, les numéros qui commencent par "1" font généralement deux chiffres, sauf les numéros qui commencent par "11" qui en font plus souvent six (mais il n’y a pas de numéro 11 tout court) ; ceux qui commencent par "3" font généralement quatre chiffres, et ceux qui commencent par "0" font généralement dix chiffres. 
Eh bien, le principe des codes de Huffman, c’est de faire exactement pareil, mais avec les bits : admettons que vous ayez plusieurs informations différentes à coder : si vous étiez une peux vieux jeu et classique, vous pourriez décider, par exemple, de toutes les coder sur 4 bits : par exemple, 0 s’encoderait en "0000", 1 s’encoderait en "0001", 2 s’encoderait en "0011", 3 s’encoderait en "0100".
Mais, ça ne va pas. Imaginons que dans mans mon cas, "2" revienne plus souvent, alors que je n’ai presque jamais de "1". Pourquoi je devrais quand même utiliser quatre bits pour le stocker, et perdre de la place à chaque fois, alors que pourrais, par exemple, utiliser seulement 1 bit pour stocker "2", et utiliser plus de bits pour les informations qui reviennent moins souvent ?
Eh bien, ça pourrait marcher, à une seule condition : que le codage d’1 bit que je vais utiliser pour stocker "2" ne commence JAMAIS comme les codages, plus longs, des autres informations. Vous avez compris, ce sera le même chose qu’avec les numéros de téléphones ! C’est le principe du codage d’Huffman. Contrairement aux numéros de téléphones, les codes de Huffman successifs sont toujours les plus courts possibles.
Du coup, si mes informations à coder sont "0", "1", "2" et "3", et que je peux les ranger de la plus à la moins courante de cette façon : "2" > "0" > "3", "1", alors je peux par exemple leur assigner ces codes :
"2" = 0
"0" = 10
"3" = 110
"1" = 111
C’est cohérent avec mes besoins, le code de "2" est le moins long et celui de "1" est l’un des plus longs, et surtout deux codes différents ne commencent jamais pareil.
Du coup, si je suis un programme, je suis une machine un peu bête, je vais me mettre à lire les bits un par un (puisque je ne peux regarder qu’à un endroit à la fois) pour retrouver la valeur d’origine à partir du code.
Ce qui serait le plus pratique pour moi, ce serait d’avoir un genre d’arbre qui me permettrait de savoir quel bit lire à la suite d’un autre. Un peu comme ça :
Eh bien, cela s’appelle un arbre d’Huffman, et c’est grosso modo une représentation du cheminement logique que va devoir suivre votre programme pour décoder une valeur écrite en codage Huffman. C’est aussi un moyen de s’assurer que le principe du codage Huffman est bien respecté : chaque branche de l’arbre a au maximum deux ramifications (en jargon technique, on appelle ce type d’arbre un arbre binaire).
Pour comparaison, voici grosso modo l’arbre (qui n’est pas un arbre binaire mais un arbre décimal, donc pas un arbre d’Huffman) qui me permet de savoir quelle taille fera mon numéro de téléphone :
(Dans la réalité, c’est plus complexe, les autres premiers chiffres que 0, 1 et 3 devaient vous servir à pouvoir appeler avec d’autres opérateurs avant que les box n’apparaissent, sans compter les numéros internationaux qui peuvent avoir différentes tailles et commencer par « 00 », etc. Sans compter les services spéciaux proposés par chaque opérateur mobile, souvent des numéros à trois chiffres, les numéros des services payants par SMS qui commencent par « 8 »… C’est le fruit d’une longue évolution historique qui fait que la téléphonie, ce n’est pas simple !)
Vous avez remarqué, j’aime beaucoup les diagrammes, en particulier les flowcharts. C’est parce que je pense comme une machine. Eh eh eh.
Petit jargon utile : ci-dessus, j’ai représenté notre arbre d’Huffman sous forme de graphe. Ce graphe dispose de nœuds (ce que j’ai représenté par des ronds) qui sont reliées par des arêtes, ou liens (en anglais « edges », ce que j’ai représenté par des traits). Notre arbre se parcourt de haut en bas, il a un sens, il s’agit donc d’un graphe orienté (ou graphe dirigé).
Le codage Huffman appliqué à DEFLATE
Avec DEFLATE, le codage Huffman est utilisé, mais soumis à quelques règles importantes :
- Si des codes de différentes tailles cohabitent, alors les codes plus courts se situeront alphabétiquement avant les codes plus longs (quand je parle d’ordre alphabétique, c’est une comparaison effectuée sur le début de chaque code mais de gauche à droite - comme les mots dans le dictionnaire).
Je m’explique : si des codes de 7, 8 et 9 bits cohabitent, alors les codes de 7 bits pourront par exemple commencer par "000", ou "0010", puis ceux de 8 bits commencer par "0011", "01", "10", "11000", puis ceux de 9 bits commencer par "11001", "111", etc. C’est vraiment la même chose qu’avec l’ordre des mots dans le dictionnaire, mais votre alphabet a deux lettres, 0 et 1.
- Au sein de codes d’une même taille, si nos codes représentent des nombres binaires (et ce sera le cas), alors les valeurs se situeront aussi dans l’ordre alphabétique (si nos codes de 7 bits représentent des nombres qui partent de 40, alors on aura d’abord "0000000" pour "40", "0000001" pour "41", "0000011" pour "42", "0000100" pour "43", etc.).
À partir de cela, il suffit de distribuer de distribuer nos différent codes (par exemple du plus fréquent au moins fréquent) à travers un certain nombre de tailles de bits, et grâce aux règles ci-dessous, on saura automatiquement comment chaque code s’écrira en binaire. C’est magique !
Par défaut, et comme on le verra plus tard, DEFLATE nous demande de choisir l’ordre de 288 codes (allant de 0 à 287), dont 256 représentent des octets bruts, et de les placer dans un arbre de Huffman. Soit le compresseur calcule et fournit son propre arbre au décompresseur (en général c’est le cas), soit, s’il décide que c’est plus intéressant, il utilise un arbre pré-défini.
Vous avez bien compris, la norme nous donne des tranches de codes et les associe à des tailles de bits, et c’est à nous de deviner les codes ensuite ! Car on peut le faire seulement avec les règles ci-dessus !
Ils nous donnent quand même les tranches de codes associées, pour nous aider un peu, mais ne seraient techniquement pas obligés de le faire.
Pour votre culture, le codage Huffman n’est pas utilisé que par DEFLATE. JPEG et MP3 (qui sont des algorithmes de compression avec perte dont nous parlerons plus tard) en utilisent aussi, par exemple.
Le fonctionnement de DEFLATE
Bon, accrochez-vous, maintenant c’est mastoc !
DEFLATE, ce n’est pas juste une suite d’octets, c’est une suite de bits. Cette suite de bits, je vous l’explique avec le schéma ci-dessous.
C’est un peu plus complexe que ce qu’on avait vu jusqu’à là, mais ça a du sens : c’est presque comme LZSS, on a juste utilisé des codes Huffman pour prendre moins de place, et on a encodé nos arbre Huffman avec des codes Huffman pour qu’ils prennent eux-mêmes moins de place.
Poto ! J’ai entendu que tu aimais Huffman, alors je t’ai mis du Huffman dans du Huffman.
Parmi les différents types de blocs, on peut supposer que « 00 » sera utilisé si vos données sont vraiment incompressibles (par exemple du contenu chiffré ou aléatoire - on dit alors que « l’entropie » des données est forte), et que « 01 » sera utilisé si votre contenu est court. « 10 » sera utilisé dans la plupart des cas.
Un décodeur DEFLATE en Python
Vous pensez être capable de décoder DEFLATE vous-même ? Chiche, lisez la norme et le code C d’origine. Sinon, je vais vous montrer une petite implémentation que j’ai faîte dans le cadre de ce tutoriel.
D’abord, un petit aparté sur un détail que vous devez connaître : on n’utilise jamais DEFLATE « tel quel ». On l’encapsule le plus souvent dans deux formats très simples et assez semblables, qui peuvent être soit Zlib, soit Gzip.
Le format Zlib : DEFLATE (presque) dans son plus simple appareil
Zlib est un format très simple qui dispose d’un en-tête et d’une en-pied (d’octets ajoutés avant et après le flux DEFLATE). Tout comme DEFLATE, Zlib dispose de sa propre norme, la RFC 1950. Les RFC sont des normes produites par l’IETF (Internet Engineering Task Force, soit « organisation dédiée à l’ingénierie d’Internet »), un groupe d’ingénieurs américain qui est à l’origine de la plupart des normes importantes des protocoles qui constituent Internet. Elles sont en général écrites dans un anglais clair et limpide.
Les différents champs de l’en-tête Zlib sont disposés comme suit (en ordre little-endian, et le premier champ est le plus à droite du premier octet) :
| Taille en bits | Champ | Description |
|---|---|---|
| 4 | CM - Compression method | Une seule valeur : "8" pour le format DEFLATE |
| 4 | CINFO - Compression info | Le nombre de bits de la fenêtre glissante, moins 8. En général, ça sera "7", soit 15 bits de fenêtre glissante, soit une fenêtre glissante avec une position de 0 à 32767. |
| 5 | FCHECK | Une fois qu’on a écrit le reste de l’en-tête, on ajoute ici le reste de division nécessaire à ce que les deux octets d’en-tête vus en ordre big endian soient un multiple de 31 (valeur de vérification). |
| 1 | FDICT | Si ce bit est à 1, alors l’en-tête va être suivie par un identifiant d’arbre (DICTID) de 32 bits, qui permet d’utiliser un arbre de Huffman pré-défini particulier et spécifique au format ou protocole dans lequel Zlib est utilisé. Ici, on ne l’utilisera pas. |
| 2 | FLEVEL | Le niveau de compression utilisé à l’origine : 0 = le plus rapide, 1 = rapide, 2 = par défaut, 3 = le plus efficace mais le plus lent. Il ne nous est pas utile pour décompresser, par contre il est très utile si jamais on veut recompresser un flux pour l’optimiser. |
Quant à l’en-pied, il n’y a qu’un seul champ :
| Taille en bits | Champ | Description |
|---|---|---|
| 32 | ADLER32 | Le code Adler32 du contenu décompressé (pour vérification). |
Adler32 (créée par Mark Adler, un des créateurs de Zlib) est ce qu’on appelle une fonction de hachage : elle va prendre en entrée des octets, va tous les mélanger entre eux, et à la fin, on obtient un nombre de 32 bits produit par le compresseur qui va ensuite être reproduit par le décompresseur, et va ainsi lui permettre de vérifier que toutes les données à décompresser ont bien été transmises comme il faut (si c’est le cas, les deux nombres seront identiques).
Voici comment fonctionne Adler32 (on pourrait écrire ce code de façon plus courte, mais j’ai voulu bien décomposer chaque étape de ce qu’il fait) :
def mon_adler32(entree : bytes) -> int:
somme_des_octets = 0
somme_de_chaque_octet_fois_sa_position_depuis_la_fin = 0
# enumerate() = passer sur chaque octet, avec à la fois la position (en
# partant de zéro) et l'octet
for position, octet in enumerate(entree):
position_depuis_la_fin = len(entree) - position
somme_des_octets += octet
somme_de_chaque_octet_fois_sa_position_depuis_la_fin += octet * position_depuis_la_fin
# On ajoute des valeurs pour ne pas risquer de rester à zéro
somme_des_octets += 1
somme_de_chaque_octet_fois_sa_position_depuis_la_fin += len(entree)
# On effectue un modulo sur les deux sommes (qui vont passer sous 16 bits
# en taille)
somme_de_chaque_octet_fois_sa_position_depuis_la_fin %= 65521
somme_des_octets %= 65521
# On renvoie les deux sommes, chacune sur 16 bits
return (somme_de_chaque_octet_fois_sa_position_depuis_la_fin << 16) | somme_des_octets
La version optimisée d’Adler32 (qui fait exactement la même chose, mais en moins clair et en plus rapide) :
def mon_adler32(entree : bytes) -> int:
somme_1 = 1
somme_2 = 0
for octet in entree:
somme_1 += octet
somme_2 += somme_1
somme_1 %= 65521
somme_2 %= 65521
return (somme_2 << 16) | somme_1
Les nombres produits par Adler32 ne font que 32 bits, il sont faciles à falsifier, c’est à dire qu’il est simple de trouver une autre chaîne d’octets qui produit le même résultat de 32 bits (même s’il est peu probable que ça arrive accidentellement : un bit qui change et c’est tout le résultat qui change). C’est pour ça qu’Adler32 ne sert qu’à vérifier s’il n’y a pas eu d’erreur de transmission ; on dit qu’il s’agit d’une « fonction de hachage d’intégrité » (ou somme de contrôle).
À contrario, d’autres fonctions de hachage, comme la famille SHA, produisent des nombres beaucoup plus longs et qui sont beaucoup plus durs à falsifier. Ils peuvent aussi être utilisés dans des contextes de chiffrement et de vérification de messages chiffrés. On les appellent « fonctions de hachages cryptographiques » (et une falsification, intentionnelle ou non, est appelée « collision »).
Si vous avez tout bien suivi, vous devriez être capable d’écrire un morceau de ZLIB+DEFLATE non-compressé, sans Huffman, à la main comme je le fais ci-dessous.
$ python3
Python 3.6.9 (default, Nov 7 2019, 10:44:02)
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>
>>> from zlib import decompress, adler32
>>>
>>> decompress(b'\x78\x01\x01\x04\x00\xfb\xffABCD' + adler32(b'ABCD').to_bytes(4, 'big'))
b'ABCD'
>>>
Je vous explique :
\x78= Compression method =8(DEFLATE), compression info =7(les distances se comptent sur 15 bits, soit 32 kilo-octets de fenêtre glissante - le paramètre le plus courant)\x01= FLEVEL =0(la compression la plus rapide, pour le coup c’est presque vrai !), FDICT =0(si on utilise un arbre de Huffman pré-défini, alors ce sera celui spécifié par la norme DEFLATE), FCHECK =-0x7800 % 31=1(maintenant on a un multiple de 31 !)
Ensuite, on passe à DEFLATE :
\x01: Bits00= on va avoir du contenu décompressé à copier tel quel, sans Huffman, et1= c’est le dernier bloc (après avoir lu ces derniers champs, on change d’octet)\x04\x00: une taille de 4 octets, écrite en order little-endian, toujours\xfb\xff: la même chose mais avec tous les bits inversés, pour vérification : en Python, cela se calcule comme ça :0x0400 ^ 0xffff- l’opérateur^s’appelle « Binary XOR - Exclusive OR » (OU exclusif), il veut dire que lorsqu’un bit est à 1 l’un des deux côtés (avec0xffffc’est toujours le cas), ben on doit l’inverser de l’autreABCD: notre contenu à copier tel quel- (Fin du dernier bloc DEFLATE, on revient à Zlib)
- Ensuite,
\x02\x98\x01\x0b, notre somme ADLER32 qui s’écrit en ordre big-endian (c’est une exception)
Vous êtes prêts ? On va attaquer le code !
Les mains dans le cambouis : notre code Python
DEFLATE est un peu trop complexe pour que sa décompression soit implémentée entièrement dans une fonction, comme je l’ai fait avec les précédents algorithmes. Du coup, je vais créer une fonction et deux classes : une classe pour implémenter le décodage de Huffman pour un arbre donné, et une classe pour faire la lecture d’un flux de bits à partir d’un flux d’octets.
Si vous ne savez pas ce qu’est une classe, vous pouvez aller voir par ici. En gros, en Python, un objet est une variable d’un certain type (une chaîne est un objet, un entier est un objet, etc.) qui contient à la fois des variables internes (les attributs) et des fonctions internes (les méthodes). Une classe, c’est un bloc de code qui vous permet de définir un nouveau type d’objet, avec ses méthodes et ses attributs.
Quand j’écris 'mon texte'.upper(), j’appelle la méthode upper() de la chaîne 'mon texte', qui est un objet de type str (en anglais, « string » = « chaîne »), et qui me retourne ma chaîne en majuscules (« uppercase » = « majuscules »).
Voici le contenu (toujours en hexadécimal) que je vais devoir essayer de décoder :
789c734bcc2cd6cd495548cecfcd4d5528ce54c8523fbcb20428a890737801977362914249a94231885f58aa9ea55e5c0a6415004541b25e30a559a5c525a91021302bb12c31af04a401a83757bd28352f393fafa428b598a034e90662ea0000a2914fcd
Si vous pensez être capable d’écrire votre propre décodeur DEFLATE, ben c’est le moment. Sinon, on y va.
Vous remarquerez que mon code est toujours annoté : simplement, je ne mets plus les annotations à l’extérieur du code, mais à l’intérieur, via des commentaires. Vous pouvez continuer à le parcourir de haut en bas !
Tout d’abord, il nous faut notre classe pour lire des bits.
# "LecteurDeBits" sera notre classe qui prendra en entrée des octets, et exposera
# des méthodes permettant de lire des flux de bits en ordre little endian (c'est
# à dire en ajoutant chaque octet successif à gauche de l'autre, et en prenant
# à chaque fois les bits les plus à droite).
class LecteurDeBits:
# "self" est la variable qui fait référence à l'objet actuel.
# Lorsque vous écrivez « objet.methode(argument) », Python ajoute toujours
# un premier argument "self" implicite.
# "__init__" est la première méthode qui est appelée lorsque vous créée
# un objet (en écrivant « classe(argument) ») : vous appelez en fait
# « classe.__init__(argument) » et vous obtenez un nouvel objet en retour
def __init__(self, entree : bytes):
# Un BytesIO est un lecteur d'octets avec une
# position donnée.
self.octets = BytesIO(entree)
# On initialise nos attributs.
self.bits_non_lus = 0
self.taille_bits_non_lus = 0
"""
Lire un entier composé d'un certain nombre de bits
"""
def lire_bits(self, nombre_bits : int) -> int:
while self.taille_bits_non_lus < nombre_bits:
prochain_octet = self.octets.read(1)
"""
Si notre lecture du BytesIO a retourné une chaîne vide, alors
ça veut dire qu'il n'y a plus d'octets de disponibles, on va
déclencher une erreur
"""
if not prochain_octet:
raise EOFError
"""
On n'oublie pas de convertir notre chaîne d'un octet en
entier en ne prenant explicitement que le premier octet: "[0]"
On l'ajoute à nos bits non lus
"""
self.bits_non_lus |= prochain_octet[0] << self.taille_bits_non_lus
self.taille_bits_non_lus += 8
masque_bits_lus = (1 << nombre_bits) - 1
bits_lus = self.bits_non_lus & masque_bits_lus
self.bits_non_lus >>= nombre_bits
self.taille_bits_non_lus -= nombre_bits
return bits_lus
"""
Lire simplement des octets
"""
def lire_octets(self, nombre_octets : int) -> bytes:
self.aligner_bits_sur_octet()
octets_lus = self.octets.read(nombre_octets)
if len(octets_lus) < nombre_octets:
raise EOFError # Pas assez d'octets, déclencher une erreur, EOF = End of file = Fin de fichier
return octets_lus
"""
Se rendre au début de l'octet suivant
"""
def aligner_bits_sur_octet(self):
self.bits_non_lus = 0
self.taille_bits_non_lus = 0
Ensuite, notre classe qui doit savoir décoder des codes de Huffman, et deviner ces codes à partir d’une liste de valeurs et de leurs tailles respectives.
# Notre décodeur de Huffman.
class DecodeurHuffman:
"""
La méthode "__init__" (en jargon technique, on l'appelle « notre
constructeur » prendra comme premier argument une association (un
dictionnaire Python) entre des valeurs (des entiers), et leurs tailles
de codes respectives d'autres entiers). À partir de ça, les codes
Huffman seront calculés automatiquement.
"""
def __init__(self, valeur_vers_taille_de_code : Dict[int, int], lecteur_de_bits : LecteurDeBits):
# Chaîne de code = chaîne représentant un code écrit en chiffres binaires
self.chaine_de_code_vers_valeur : Dict[str, int] = {}
self.lecteur_de_bits : LecteurDeBits = lecteur_de_bits
derniere_taille_de_code : int = None
dernier_code : int = None
"""
Comme expliqué plus haut dans le tutoriel, on va numéroter nos
codes selon leurs tailles de codes respectives, puis selon leurs
valeurs.
Du coup, il va falloir passer sur les valeurs dans l'ordre, en
prenent d'abord en compte la taille de code.
Cette petite fonction, que l'on va passer à la fonction de tri de
Python ("sorted"), devrait nous être très utile pour trier d'abord
par tailles de codes, et ensuite par valeurs.
"""
def tri_valeurs(valeur_et_taille_de_code):
valeur, taille_de_code = valeur_et_taille_de_code # On prend la tuple...
return (taille_de_code, valeur) # ... et on la change de sens pour dire qu'on trie par tailles de code d'abord
for valeur, taille_de_code in sorted(valeur_vers_taille_de_code.items(), key = tri_valeurs):
if not taille_de_code:
continue # Taille de code de 0 ! On passe !
if dernier_code is None:
code = 0
else:
if taille_de_code < derniere_taille_de_code:
# Vu qu'on passe sur les tailles de code dans l'ordre, de
# la plus petite à la plus grande, ça n'arrive très
# logiquement jamais.
raise Exception
elif taille_de_code > derniere_taille_de_code:
code = (dernier_code + 1) << (taille_de_code - derniere_taille_de_code)
else:
code = dernier_code + 1
# On transforme notre code en chaîne contenant des chiffres
# binaires : on utilise "format" pour créer la chaîne (qui
# sera la plus courte possible), puis "zfill" qui va nous
# ajouter le bon nombre de zéros à gauche
chaine_de_code = format(code, 'b').zfill(taille_de_code)
self.chaine_de_code_vers_valeur[chaine_de_code] = valeur
dernier_code = code
derniere_taille_de_code = taille_de_code
"""
Maintenant qu'on a constitué tous nos codes dans
"chaine_de_code_vers_valeur", il va falloir créer la structure
représentant notre arbre.
Notre arbre sera fait de dictionnaires Python imbriqués entre eux,
avec pour chacun au plus deux clefs, "0" et "1", et dont la valeur
correspond soit à notre valeur Huffman (un entier), soit à un
autre dictionnaire s'il faut continuer dans l'arbre.
"""
# L'anotation de type "Union" signifie « une de ces valeurs » (comme
# toutes les annotations de type, elle a uniquement une valeur
# d'information)
self.mon_arbre : Dict[int, Union[dict, int]] = {}
for chaine_de_code, valeur in self.chaine_de_code_vers_valeur.items():
# Pour chaque code, on va descendre dans l'arbre, en créant au
# passage les dictionaires imbiqués successifs pour chaque bit
# (sauf le dernier), et assigner le dernier bit à la valeur
# associée au code
noeud_actuel_dans_l_arbre = self.mon_arbre
# Descendre dans l'arbre...
for chiffre_bit in chaine_de_code[:-1]:
bit = int(chiffre_bit) # Conversion de chaîne en entier
if bit not in noeud_actuel_dans_l_arbre:
noeud_actuel_dans_l_arbre[bit] = {} # Création de dictionnaire
noeud_actuel_dans_l_arbre = noeud_actuel_dans_l_arbre[bit]
# ...on est au bout
dernier_bit = int(chaine_de_code[-1])
noeud_actuel_dans_l_arbre[dernier_bit] = valeur
# On a créé notre arbre, c'est tout bon !
"""
Maintenant : voici la fonction qu'on va appeler tout le temps pour
faire le décodage : elle va lire le code à partir du lecteur de bits.
Elle commence en haut de l'arbre, puis elle avance d'un bit à la fois,
jusqu'à avoir trouvé la valeur.
"""
def lire_prochaine_valeur(self) -> int:
noeud_actuel_dans_l_arbre = self.mon_arbre
while True:
prochain_bit : int = self.lecteur_de_bits.lire_bits(1)
noeud_actuel_dans_l_arbre = noeud_actuel_dans_l_arbre[prochain_bit]
# On est tombé sur un entier ? Chouette, on a trouvé notre valeur !
if type(noeud_actuel_dans_l_arbre) == int:
return noeud_actuel_dans_l_arbre
Enfin, notre fonction de décodage pour Zlib+DEFLATE.
def mon_decodeur_zlib(entree : bytes) -> bytes:
# Lecture de l'en-tête ZLIB
lecteur_de_bits = LecteurDeBits(entree)
compression_method = lecteur_de_bits.lire_bits(4)
compression_info = lecteur_de_bits.lire_bits(4)
fcheck = lecteur_de_bits.lire_bits(5)
fdict = lecteur_de_bits.lire_bits(1)
flevel = lecteur_de_bits.lire_bits(2)
if fdict:
dict_id = lecteur_de_bits.lire_bits(32)
assert compression_method == 8 # DEFLATE
assert int.from_bytes(entree[:2], 'big') % 31 == 0
# Lecture des blocs DEFLATE
contenu_decompresse = b''
while True:
blocs_restants_ensuite = lecteur_de_bits.lire_bits(1) != 1
type_de_bloc = lecteur_de_bits.lire_bits(2)
if type_de_bloc == 0: # Contenu stocké sans compression
lecteur_de_bits.aligner_bits_sur_octet()
taille_a_lire = lecteur_de_bits.lire_bits(16)
assert lecteur_de_bits.lire_bits(16) ^ 0xffff == taille_a_lire
contenu_decompresse += lecteur_de_bits.lire_octets(taille_a_lire)
elif type_de_bloc in (0b01, 0b10): # Instructions codées en Huffman
if type_de_bloc == 0b01: # Arbre pré-défini - d'après https://tools.ietf.org/html/rfc1951#page-12
valeur_vers_taille_de_code = {}
for valeur in range(256, 279 + 1):
valeur_vers_taille_de_code[valeur] = 7
for valeur in range(0, 143 + 1):
valeur_vers_taille_de_code[valeur] = 8
for valeur in range(280, 287 + 1):
valeur_vers_taille_de_code[valeur] = 8
for valeur in range(144, 255 + 1):
valeur_vers_taille_de_code[valeur] = 9
# ^ Les octets hors de la plage ASCII (0-127)
# sont statiquement les moins courants, on va
# les coder sur le plus de bits.
arbre_des_instructions = DecodeurHuffman(valeur_vers_taille_de_code, lecteur_de_bits)
arbre_des_distances = DecodeurHuffman({position: 5 for position in range(0, 31 + 1)}, lecteur_de_bits)
elif type_de_bloc == 0b10: # Arbre inclus dans le flux DEFLATE (voir https://tools.ietf.org/html/rfc1951#page-13)
taille_arbre_des_instructions = lecteur_de_bits.lire_bits(5) + 257
taille_arbre_des_distances = lecteur_de_bits.lire_bits(5) + 1
taille_arbre_des_tailles_de_code = lecteur_de_bits.lire_bits(4) + 4
# La norme demande de lire les tailles de valeurs de l'arbre de tailles de code
# les plus fréquentes d'abord, comme ça, s'il y en a des moins fréquentes et qu'elles
# sont à la fin, eh bien on peut diminuer "taille_arbre_des_tailles_de_code" et
# ne pas les lire du tout (et gagner de la place)
valeurs_des_tailles_de_code_dans_l_ordre = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]
tailles_de_valeurs_de_l_arbre_de_tailles : Dict[int] = {}
for position in range(taille_arbre_des_tailles_de_code):
vraie_position = valeurs_des_tailles_de_code_dans_l_ordre[position]
tailles_de_valeurs_de_l_arbre_de_tailles[vraie_position] = lecteur_de_bits.lire_bits(3)
arbre_des_tailles_de_code = DecodeurHuffman(tailles_de_valeurs_de_l_arbre_de_tailles, lecteur_de_bits)
def obtenir_n_tailles_de_code(nombre_tailles_de_code):
tailles_de_code : List[int] = []
while len(tailles_de_code) < nombre_tailles_de_code:
code_de_taille = arbre_des_tailles_de_code.lire_prochaine_valeur() # Code de taille de code !
if code_de_taille < 16:
tailles_de_code.append(code_de_taille)
elif code_de_taille == 16:
tailles_de_code += [tailles_de_code[-1]] * (3 + lecteur_de_bits.lire_bits(2))
elif code_de_taille == 17:
tailles_de_code += [0] * (3 + lecteur_de_bits.lire_bits(3))
elif code_de_taille == 18:
tailles_de_code += [0] * (11 + lecteur_de_bits.lire_bits(7))
return tailles_de_code
arbre_des_instructions = DecodeurHuffman(
dict(enumerate(obtenir_n_tailles_de_code(taille_arbre_des_instructions))),
lecteur_de_bits)
arbre_des_distances = DecodeurHuffman(
dict(enumerate(obtenir_n_tailles_de_code(taille_arbre_des_distances))),
lecteur_de_bits)
# On a nos arbres, passage à la décompression
while True:
code_instruction = arbre_des_instructions.lire_prochaine_valeur()
if code_instruction == 256: # Fin du bloc
break
elif code_instruction < 256:
contenu_decompresse += bytes([code_instruction])
else: # Répétition - voir https://tools.ietf.org/html/rfc1951#page-12
if code_instruction < 265:
taille_repetition = 3 + (code_instruction - 257)
# À partir de 265, on a des codes de répétition qui
# indiquent que la taille de la répétition est partiellement
# codée sur des bits supplémentaires.
#
# Pour les interpréter, il faut considérer qu'il faut les
# interpréter comme ça :
# - D'abord, les soustraire à 265 (logique)
# - Ensuite :
# - Les deux bits les plus bas font partie intégrante de
# la taille de répétition (!)
# - Le reste des bits indiquent le nombre de bits
# supplémentaires
#
# Au final, la taille de répéition est construite de cette
# manière
# - Le bit le plus haut est mis à 1 (logique, il l'est
# toujours pour un nombre de bits donnée, sinon notre
# taille ne ferait pas « un certain nombre de bits »)
# - Ensuite, on met les deux bits issus du code de
# répétition
# - Ensuite, on met le reste des bits supplémentaires, lus
# depuis le flux de bits
elif code_instruction < 285:
extra_bits = 1 + ((code_instruction - 265) >> 2)
taille_repetition = 3 + ((0b100 | ((code_instruction - 265) & 0b11)) << extra_bits)
taille_repetition += lecteur_de_bits.lire_bits(extra_bits)
else:
raise ValueError("Type de code d'instruction DEFLATE invalide : %d" % code_instruction)
# Pour la distance de répétition, c'est presque la même
# logique, sauf qu'il n'y a qu'un bit du code qui part
# dans la distance produite
code_distance = arbre_des_distances.lire_prochaine_valeur()
if code_distance < 4:
distance = 1 + code_distance
else:
extra_bits = 1 + ((code_distance - 4) >> 1)
# LE SAVIEZ-VOUS ?
#
# Lorsque je fais glisser des bits vers la gauche, je
# pourrais aussi faire une multiplication. Ces
# opérations sont équivalentes :
#
# "n << 1" et "n * 2"
# "n << 2" et "n * 4"
# "n << 3" et "n * 8"
# etc.
#
# De même, lorsque je fais glisser des bits vers la
# droite, je pourrais aussi faire une division :
# ces opérations sont aussi semblables
#
# "n >> 1" et "n // 2"
# "n >> 2" et "n // 4"
# "n >> 3" et "n // 8"
# etc.
#
# ("https://" est l'opération de la division entière en
# Python, par opposition à "/" qui est l'opération de
# la division décimale)
#
# Ce n'est pas tout : ces opérations d'extraction de
# bits et ces opérations de modulo/reste sont aussi
# équivalentes :
# "n & 1" et "n % 2"
# "n & 3" et "n % 4"
# "n & 7" et "n & 8"
# etc.
distance = 1 + ((0b10 | ((code_distance - 2) & 1)) << extra_bits)
distance += lecteur_de_bits.lire_bits(extra_bits)
# On a décodé la taille et la distance (et on voit qu'ils sont
# savamment économisé de la place en répartissant les bits de
# la taille et la distance entre la fin des valeurs Huffman,
# et des bits en plus qui sont lus au cas par cas)
# Maintenant, on peut effectuer la copie du contenu répété
# Si on n'a pas assez du contenu à répéter dans notre buffer
# pour la taille demandée, c'est qu'on doit le répéter
# plusieurs fois jusqu'à la satisfaire
contenu_a_repeter = contenu_decompresse[
-distance:
-distance + taille_repetition if (-distance + taille_repetition) < 0 else None
]
while contenu_a_repeter and len(contenu_a_repeter) < taille_repetition:
contenu_a_repeter *= 2
contenu_a_repeter = contenu_a_repeter[:taille_repetition]
contenu_decompresse += contenu_a_repeter
else:
raise ValueError('Type de bloc DEFLATE invalide : « 11 ». Est-ce bien du DEFLATE ?')
if not blocs_restants_ensuite:
lecteur_de_bits.aligner_bits_sur_octet()
break
# Vérification de l'en-pied ZLIB
somme_adler32 = int.from_bytes(entree[-4:], 'big')
assert mon_adler32(contenu_decompresse) == somme_adler32
return contenu_decompresse
C’est tout bon : il ne reste plus qu’à obtenir la valeur en clair de notre message secret !
print(mon_decodeur_zlib(bytes.fromhex('789c734bcc2cd6cd495548cecfcd4d5528ce54c8523fbcb20428a890737801977362914249a94231885f58aa9ea55e5c0a6415004541b25e30a559a5c525a91021302bb12c31af04a401a83757bd28352f393fafa428b598a034e90662ea0000a2914fcd').decode('utf8'))
Voici le code en entier :
#!/usr/bin/python3
#-*- encoding: Utf-8 -*-
from typing import List, Dict, Set, Sequence, Union
from io import BytesIO
def mon_adler32(entree : bytes) -> int:
somme_des_octets = 0
somme_de_chaque_octet_fois_sa_position_depuis_la_fin = 0
# enumerate() = passer sur chaque octet, avec à la fois la position (en
# partant de zéro) et l'octet
for position, octet in enumerate(entree):
position_depuis_la_fin = len(entree) - position
somme_des_octets += octet
somme_de_chaque_octet_fois_sa_position_depuis_la_fin += octet * position_depuis_la_fin
# On ajoute des valeurs pour ne pas risquer de rester à zéro
somme_des_octets += 1
somme_de_chaque_octet_fois_sa_position_depuis_la_fin += len(entree)
# On effectue un modulo sur les deux sommes (qui vont passer sous 16 bits
# en taille)
somme_de_chaque_octet_fois_sa_position_depuis_la_fin %= 65521
somme_des_octets %= 65521
# On renvoie les deux sommes, chacune sur 16 bits
return (somme_de_chaque_octet_fois_sa_position_depuis_la_fin << 16) | somme_des_octets
# "LecteurDeBits" sera notre classe qui prendra en entrée des octets, et exposera
# des méthodes permettant de lire des flux de bits en ordre little endian (c'est
# à dire en ajoutant chaque octet successif à gauche de l'autre, et en prenant
# à chaque fois les bits les plus à droite).
class LecteurDeBits:
# "self" est la variable qui fait référence à l'objet actuel.
# Lorsque vous écrivez « objet.methode(argument) », Python ajoute toujours
# un premier argument "self" implicite.
# "__init__" est la première méthode qui est appelée lorsque vous créée
# un objet (en écrivant « classe(argument) ») : vous appelez en fait
# « classe.__init__(argument) » et vous obtenez un nouvel objet en retour
def __init__(self, entree : bytes):
# Un BytesIO est un lecteur d'octets avec une
# position donnée.
self.octets = BytesIO(entree)
# On initialise nos attributs.
self.bits_non_lus = 0
self.taille_bits_non_lus = 0
"""
Lire un entier composé d'un certain nombre de bits
"""
def lire_bits(self, nombre_bits : int) -> int:
while self.taille_bits_non_lus < nombre_bits:
prochain_octet = self.octets.read(1)
"""
Si notre lecture du BytesIO a retourné une chaîne vide, alors
ça veut dire qu'il n'y a plus d'octets de disponibles, on va
déclencher une erreur
"""
if not prochain_octet:
raise EOFError
"""
On n'oublie pas de convertir notre chaîne d'un octet en
entier en ne prenant explicitement que le premier octet: "[0]"
On l'ajoute à nos bits non lus
"""
self.bits_non_lus |= prochain_octet[0] << self.taille_bits_non_lus
self.taille_bits_non_lus += 8
masque_bits_lus = (1 << nombre_bits) - 1
bits_lus = self.bits_non_lus & masque_bits_lus
self.bits_non_lus >>= nombre_bits
self.taille_bits_non_lus -= nombre_bits
return bits_lus
"""
Lire simplement des octets
"""
def lire_octets(self, nombre_octets : int) -> bytes:
self.aligner_bits_sur_octet()
octets_lus = self.octets.read(nombre_octets)
if len(octets_lus) < nombre_octets:
raise EOFError # Pas assez d'octets, déclencher une erreur, EOF = End of file = Fin de fichier
return octets_lus
"""
Se rendre au début de l'octet suivant
"""
def aligner_bits_sur_octet(self):
self.bits_non_lus = 0
self.taille_bits_non_lus = 0
# Notre décodeur de Huffman.
class DecodeurHuffman:
"""
La méthode "__init__" (en jargon technique, on l'appelle « notre
constructeur » prendra comme premier argument une association (un
dictionnaire Python) entre des valeurs (des entiers), et leurs tailles
de codes respectives d'autres entiers). À partir de ça, les codes
Huffman seront calculés automatiquement.
"""
def __init__(self, valeur_vers_taille_de_code : Dict[int, int], lecteur_de_bits : LecteurDeBits):
# Chaîne de code = chaîne représentant un code écrit en chiffres binaires
self.chaine_de_code_vers_valeur : Dict[str, int] = {}
self.lecteur_de_bits : LecteurDeBits = lecteur_de_bits
derniere_taille_de_code : int = None
dernier_code : int = None
"""
Comme expliqué plus haut dans le tutoriel, on va numéroter nos
codes selon leurs tailles de codes respectives, puis selon leurs
valeurs.
Du coup, il va falloir passer sur les valeurs dans l'ordre, en
prenent d'abord en compte la taille de code.
Cette petite fonction, que l'on va passer à la fonction de tri de
Python ("sorted"), devrait nous être très utile pour trier d'abord
par tailles de codes, et ensuite par valeurs.
"""
def tri_valeurs(valeur_et_taille_de_code):
valeur, taille_de_code = valeur_et_taille_de_code # On prend la tuple...
return (taille_de_code, valeur) # ... et on la change de sens pour dire qu'on trie par tailles de code d'abord
for valeur, taille_de_code in sorted(valeur_vers_taille_de_code.items(), key = tri_valeurs):
if not taille_de_code:
continue # Taille de code de 0 ! On passe !
if dernier_code is None:
code = 0
else:
if taille_de_code < derniere_taille_de_code:
# Vu qu'on passe sur les tailles de code dans l'ordre, de
# la plus petite à la plus grande, ça n'arrive très
# logiquement jamais.
raise Exception
elif taille_de_code > derniere_taille_de_code:
code = (dernier_code + 1) << (taille_de_code - derniere_taille_de_code)
else:
code = dernier_code + 1
# On transforme notre code en chaîne contenant des chiffres
# binaires : on utilise "format" pour créer la chaîne (qui
# sera la plus courte possible), puis "zfill" qui va nous
# ajouter le bon nombre de zéros à gauche
chaine_de_code = format(code, 'b').zfill(taille_de_code)
self.chaine_de_code_vers_valeur[chaine_de_code] = valeur
dernier_code = code
derniere_taille_de_code = taille_de_code
"""
Maintenant qu'on a constitué tous nos codes dans
"chaine_de_code_vers_valeur", il va falloir créer la structure
représentant notre arbre.
Notre arbre sera fait de dictionnaires Python imbriqués entre eux,
avec pour chacun au plus deux clefs, "0" et "1", et dont la valeur
correspond soit à notre valeur Huffman (un entier), soit à un
autre dictionnaire s'il faut continuer dans l'arbre.
"""
# L'anotation de type "Union" signifie « une de ces valeurs » (comme
# toutes les annotations de type, elle a uniquement une valeur
# d'information)
self.mon_arbre : Dict[int, Union[dict, int]] = {}
for chaine_de_code, valeur in self.chaine_de_code_vers_valeur.items():
# Pour chaque code, on va descendre dans l'arbre, en créant au
# passage les dictionaires imbiqués successifs pour chaque bit
# (sauf le dernier), et assigner le dernier bit à la valeur
# associée au code
noeud_actuel_dans_l_arbre = self.mon_arbre
# Descendre dans l'arbre...
for chiffre_bit in chaine_de_code[:-1]:
bit = int(chiffre_bit) # Conversion de chaîne en entier
if bit not in noeud_actuel_dans_l_arbre:
noeud_actuel_dans_l_arbre[bit] = {} # Création de dictionnaire
noeud_actuel_dans_l_arbre = noeud_actuel_dans_l_arbre[bit]
# ...on est au bout
dernier_bit = int(chaine_de_code[-1])
noeud_actuel_dans_l_arbre[dernier_bit] = valeur
# On a créé notre arbre, c'est tout bon !
"""
Maintenant : voici la fonction qu'on va appeler tout le temps pour
faire le décodage : elle va lire le code à partir du lecteur de bits.
Elle commence en haut de l'arbre, puis elle avance d'un bit à la fois,
jusqu'à avoir trouvé la valeur.
"""
def lire_prochaine_valeur(self) -> int:
noeud_actuel_dans_l_arbre = self.mon_arbre
while True:
prochain_bit : int = self.lecteur_de_bits.lire_bits(1)
noeud_actuel_dans_l_arbre = noeud_actuel_dans_l_arbre[prochain_bit]
# On est tombé sur un entier ? Chouette, on a trouvé notre valeur !
if type(noeud_actuel_dans_l_arbre) == int:
return noeud_actuel_dans_l_arbre
def mon_decodeur_zlib(entree : bytes) -> bytes:
# Lecture de l'en-tête ZLIB
lecteur_de_bits = LecteurDeBits(entree)
compression_method = lecteur_de_bits.lire_bits(4)
compression_info = lecteur_de_bits.lire_bits(4)
fcheck = lecteur_de_bits.lire_bits(5)
fdict = lecteur_de_bits.lire_bits(1)
flevel = lecteur_de_bits.lire_bits(2)
if fdict:
dict_id = lecteur_de_bits.lire_bits(32)
assert compression_method == 8 # DEFLATE
assert int.from_bytes(entree[:2], 'big') % 31 == 0
# Lecture des blocs DEFLATE
contenu_decompresse = b''
while True:
blocs_restants_ensuite = lecteur_de_bits.lire_bits(1) != 1
type_de_bloc = lecteur_de_bits.lire_bits(2)
if type_de_bloc == 0: # Contenu stocké sans compression
lecteur_de_bits.aligner_bits_sur_octet()
taille_a_lire = lecteur_de_bits.lire_bits(16)
assert lecteur_de_bits.lire_bits(16) ^ 0xffff == taille_a_lire
contenu_decompresse += lecteur_de_bits.lire_octets(taille_a_lire)
elif type_de_bloc in (0b01, 0b10): # Instructions codées en Huffman
if type_de_bloc == 0b01: # Arbre pré-défini - d'après https://tools.ietf.org/html/rfc1951#page-12
valeur_vers_taille_de_code = {}
for valeur in range(256, 279 + 1):
valeur_vers_taille_de_code[valeur] = 7
for valeur in range(0, 143 + 1):
valeur_vers_taille_de_code[valeur] = 8
for valeur in range(280, 287 + 1):
valeur_vers_taille_de_code[valeur] = 8
for valeur in range(144, 255 + 1):
valeur_vers_taille_de_code[valeur] = 9
# ^ Les octets hors de la plage ASCII (0-127)
# sont statiquement les moins courants, on va
# les coder sur le plus de bits.
arbre_des_instructions = DecodeurHuffman(valeur_vers_taille_de_code, lecteur_de_bits)
arbre_des_distances = DecodeurHuffman({position: 5 for position in range(0, 31 + 1)}, lecteur_de_bits)
elif type_de_bloc == 0b10: # Arbre inclus dans le flux DEFLATE (voir https://tools.ietf.org/html/rfc1951#page-13)
taille_arbre_des_instructions = lecteur_de_bits.lire_bits(5) + 257
taille_arbre_des_distances = lecteur_de_bits.lire_bits(5) + 1
taille_arbre_des_tailles_de_code = lecteur_de_bits.lire_bits(4) + 4
# La norme demande de lire les tailles de valeurs de l'arbre de tailles de code
# les plus fréquentes d'abord, comme ça, s'il y en a des moins fréquentes et qu'elles
# sont à la fin, eh bien on peut diminuer "taille_arbre_des_tailles_de_code" et
# ne pas les lire du tout (et gagner de la place)
valeurs_des_tailles_de_code_dans_l_ordre = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]
tailles_de_valeurs_de_l_arbre_de_tailles : Dict[int] = {}
for position in range(taille_arbre_des_tailles_de_code):
vraie_position = valeurs_des_tailles_de_code_dans_l_ordre[position]
tailles_de_valeurs_de_l_arbre_de_tailles[vraie_position] = lecteur_de_bits.lire_bits(3)
arbre_des_tailles_de_code = DecodeurHuffman(tailles_de_valeurs_de_l_arbre_de_tailles, lecteur_de_bits)
def obtenir_n_tailles_de_code(nombre_tailles_de_code):
tailles_de_code : List[int] = []
while len(tailles_de_code) < nombre_tailles_de_code:
code_de_taille = arbre_des_tailles_de_code.lire_prochaine_valeur() # Code de taille de code !
if code_de_taille < 16:
tailles_de_code.append(code_de_taille)
elif code_de_taille == 16:
tailles_de_code += [tailles_de_code[-1]] * (3 + lecteur_de_bits.lire_bits(2))
elif code_de_taille == 17:
tailles_de_code += [0] * (3 + lecteur_de_bits.lire_bits(3))
elif code_de_taille == 18:
tailles_de_code += [0] * (11 + lecteur_de_bits.lire_bits(7))
return tailles_de_code
arbre_des_instructions = DecodeurHuffman(
dict(enumerate(obtenir_n_tailles_de_code(taille_arbre_des_instructions))),
lecteur_de_bits)
arbre_des_distances = DecodeurHuffman(
dict(enumerate(obtenir_n_tailles_de_code(taille_arbre_des_distances))),
lecteur_de_bits)
# On a nos arbres, passage à la décompression
while True:
code_instruction = arbre_des_instructions.lire_prochaine_valeur()
if code_instruction == 256: # Fin du bloc
break
elif code_instruction < 256:
contenu_decompresse += bytes([code_instruction])
else: # Répétition - voir https://tools.ietf.org/html/rfc1951#page-12
if code_instruction < 265:
taille_repetition = 3 + (code_instruction - 257)
# À partir de 265, on a des codes de répétition qui
# indiquent que la taille de la répétition est partiellement
# codée sur des bits supplémentaires.
#
# Pour les interpréter, il faut considérer qu'il faut les
# interpréter comme ça :
# - D'abord, les soustraire à 265 (logique)
# - Ensuite :
# - Les deux bits les plus bas font partie intégrante de
# la taille de répétition (!)
# - Le reste des bits indiquent le nombre de bits
# supplémentaires
#
# Au final, la taille de répéition est construite de cette
# manière
# - Le bit le plus haut est mis à 1 (logique, il l'est
# toujours pour un nombre de bits donnée, sinon notre
# taille ne ferait pas « un certain nombre de bits »)
# - Ensuite, on met les deux bits issus du code de
# répétition
# - Ensuite, on met le reste des bits supplémentaires, lus
# depuis le flux de bits
elif code_instruction < 285:
extra_bits = 1 + ((code_instruction - 265) >> 2)
taille_repetition = 3 + ((0b100 | ((code_instruction - 265) & 0b11)) << extra_bits)
taille_repetition += lecteur_de_bits.lire_bits(extra_bits)
else:
raise ValueError("Type de code d'instruction DEFLATE invalide : %d" % code_instruction)
# Pour la distance de répétition, c'est presque la même
# logique, sauf qu'il n'y a qu'un bit du code qui part
# dans la distance produite
code_distance = arbre_des_distances.lire_prochaine_valeur()
if code_distance < 4:
distance = 1 + code_distance
else:
extra_bits = 1 + ((code_distance - 4) >> 1)
# LE SAVIEZ-VOUS ?
#
# Lorsque je fais glisser des bits vers la gauche, je
# pourrais aussi faire une multiplication. Ces
# opérations sont équivalentes :
#
# "n << 1" et "n * 2"
# "n << 2" et "n * 4"
# "n << 3" et "n * 8"
# etc.
#
# De même, lorsque je fais glisser des bits vers la
# droite, je pourrais aussi faire une division :
# ces opérations sont aussi semblables
#
# "n >> 1" et "n // 2"
# "n >> 2" et "n // 4"
# "n >> 3" et "n // 8"
# etc.
#
# ("https://" est l'opération de la division entière en
# Python, par opposition à "/" qui est l'opération de
# la division décimale)
#
# Ce n'est pas tout : ces opérations d'extraction de
# bits et ces opérations de modulo/reste sont aussi
# équivalentes :
# "n & 1" et "n % 2"
# "n & 3" et "n % 4"
# "n & 7" et "n & 8"
# etc.
distance = 1 + ((0b10 | ((code_distance - 2) & 1)) << extra_bits)
distance += lecteur_de_bits.lire_bits(extra_bits)
# On a décodé la taille et la distance (et on voit qu'ils sont
# savamment économisé de la place en répartissant les bits de
# la taille et la distance entre la fin des valeurs Huffman,
# et des bits en plus qui sont lus au cas par cas)
# Maintenant, on peut effectuer la copie du contenu répété
# Si on n'a pas assez du contenu à répéter dans notre buffer
# pour la taille demandée, c'est qu'on doit le répéter
# plusieurs fois jusqu'à la satisfaire
contenu_a_repeter = contenu_decompresse[
-distance:
-distance + taille_repetition if (-distance + taille_repetition) < 0 else None
]
while contenu_a_repeter and len(contenu_a_repeter) < taille_repetition:
contenu_a_repeter *= 2
contenu_a_repeter = contenu_a_repeter[:taille_repetition]
contenu_decompresse += contenu_a_repeter
else:
raise ValueError('Type de bloc DEFLATE invalide : « 11 ». Est-ce bien du DEFLATE ?')
if not blocs_restants_ensuite:
lecteur_de_bits.aligner_bits_sur_octet()
break
# Vérification de l'en-pied ZLIB
somme_adler32 = int.from_bytes(entree[-4:], 'big')
assert mon_adler32(contenu_decompresse) == somme_adler32
return contenu_decompresse
print(mon_decodeur_zlib(bytes.fromhex('789c734bcc2cd6cd495548cecfcd4d5528ce54c8523fbcb20428a890737801977362914249a94231885f58aa9ea55e5c0a6415004541b25e30a559a5c525a91021302bb12c31af04a401a83757bd28352f393fafa428b598a034e90662ea0000a2914fcd')).decode('utf8'))
Voici la sortie décompressée obtenue.
Fais-le comme si j'étais là
Car tu sais qu'j'suis par là
J'étais juste là
Juste avant qu'tu m'rencontres
Juste avant qu'tu m'rencontres
J'étais juste là
Juste avant qu'tu m'rencontres
J'étais juste là
Il s’agit du pré-refrain de cet obscur morceau de rap.
Liens utiles :