LZMA : L'autre grand enfant de LZ77

Si on place les algorithmes de compression populaires sur une frise chronologique, LZMA pourrait être le grand successeur de DEFLATE. Il a été introduit avec le publication du programme 7-Zip (et son format .7Z), publié pour la première fois en 1999. C’est un point commun avec DEFLATE, qui lui émane de la publication de PKZip (l’ancêtre de WinZip), un autre logiciel de compression populaire.

LZMA compresse un peu mieux que DEFLATE. Il n’est pas aussi utilisé que celui-ci, mais les développeurs l’aiment bien, et LZMA compresse mieux que DEFLATE : c’est pour ça qu’il est utilisé. Une partie des systèmes Linux l’utilisent couramment pour compresser des logiciels (sous l’extension .XZ).

LZMA est encore un algorithme à fenêtre glissante, lui aussi héritier des concepts de LZSS. Par rapport à DEFLATE, il se distingue notamment en permettant l’utilisation de fenêtres glissantes de très grande taille, et en lieu et place du codage Huffman, il utilise un autre type de codage efficace : le range coding.

Le range coding, c'est du gâteau  🍰

Le range coding est semblable à un autre algorithme assez connu, nommé arithmetic coding (codage arithmétique). Je vais vous expliquer le range coding tel qu’utilisé par LZMA.

Le range coding va encoder des données successives dans un grand nombre, plutôt qu’une suite de bits brute. Plus il y aura de données, plus le nombre sera grand.

Nous allons représenter notre nombre comme un gâteau. Notre "gâteau" est un nombre de 32 bits : 0xffffffff.

On décide que notre gâteau doit encoder une suite de bits. Comment peut-on décider que notre nombre puisse dire que le premier bit de la valeur à encoder est soit 0, soit 1 ?

Fastoche ! On va couper notre gâteau en deux : notre gâteau va de 0 à 0xffffffff. La (quasi-)moitié de 0xffffffff, c’est 0x7fffffff. On pourra simplement faire comprendre au décodeur que si notre nombre est sous 0x7fffffff, alors le prochain bit à décoder est un 0, et si le nombre est au-dessus de 0x7fffffff, alors le prochain bit est à 1 !

Oui, je découpe mes gâteaux avec une truelle.
Oui, je découpe mes gâteaux avec une truelle.

Du coup, notre nombre à encoder devient soit, par exemple, compris entre 0 et 0x7fffffff si le premier bit est un 0, soit compris entre 0x80000000 et 0xffffffff si le premier bit est un 1.

Comment fait-on pour coder notre second bit maintenant ? Fastoche ! On va simplement re-découper notre nombre en deux !

Si notre premier bit est un 0, alors notre nombre encodé sera entre 0 et 0x7fffffff. Donc si notre second bit est un 1, alors notre nombre à encoder sera dans la moitié haute de la plage 0 à 0x7fffffff, donc entre 0x40000000 et 0x7fffffff.

Deuxième étape.
Deuxième étape.

Et si notre troisième bit est un 0, alors notre nombre sera dans la plage basse de la plage de 0x40000000 à 0x7fffffff, donc de 0x40000000 à 0x5fffffff.

Oh la la Einstein ! Tu nous trompes ! Ce que tu es en train de faire, pour l’instant, c’est exactement comme l’encodage "normal" d’un bit : lorsque tu divises par deux la plage, c’est comme si tu faisais glisser ton octet d’un bit vers la droite ! Faire glisser un bit vers la droite, c’est comme diviser par deux ! Diviser par deux puis encore par deux, c’est diviser par quatre, ce qui est comme comme faire glisser de deux bits ! Chaque bit coûte un bit !

Eh oui ! vous avez remarqué ! Dans ces cette configuration, le « range coding » fonctionne exactement l’encodage d’un nombre binaire classique. En effet, notre nombre 0x5fffffff qui est compris dans notre plage vaut par exemple 01011111111111111111111111111111, ce qui est la manière dont l’information serait encodée en écrivant un nombre binaire normal.

De même que 0x40000000, l’autre extrémité, vaut 01000000000000000000000000000000.

Mais tout ça, c’est parce que je ne vous ai pas expliqué la grande subtilité pratique du range coding : en réalité, au fur et à mesure que vous « découpez » votre nombre, la taille de chaque part change ! En effet, si vous avez plus de 0 que de 1, le décodeur (tout comme l’encodeur) va renforcer la taille de la sous-part suivante qui sera associée à 0 : au lieu d’avoir 50 % de 0 et 50 % de 1, vous aurez par exemple 60 % de 0 et 40 % de 1 ! Du coup, "0" vous coûtera 0.8 bit à coder, quand "1" vous coûtera 1.2 bit d’information à décoder !

La deuxième étape, dans la réalité.
La deuxième étape, dans la réalité.

Vous avez bien compris. Notre décodeur est « intelligent » et sait voir quand il y a plus de 0 que de 1 : quand vous aurez plus de 0 que de 1, la « probabilité » que votre bit suivant soit un 0 sera renforcée (et celle que votre nombre suivant soit un 1 sera diminuée) : du coup, il faudra faire des « divisions de gâteau » de moins en moins grandes, et vous garderez de plus en plus de nombre !

Du coup, s’il y a beaucoup plus de 0 que de 1, alors la probabilité associée à 0 sera énormément renforcée, du coup, ajouter un zéro coûtera très peu cher en espace (nombre) alors qu’ajouter un 1 deviendra très cher !

Et lorsqu’on décompresse, que fait-on quand il n’y a plus assez de nombre, car on en a trop consommé ? (C’est à dire que notre nombre n’est plus assez précis pour qu’on sache dans quelle sous-part on se trouve) ? En bien on en ajoute, tout simplement : on ajoute des bits à la fin du nombre, depuis le flux de lecture. Comme ça, et en écrivant notre code on peut (presque) coder des nombres infiniment grands et codant une infinité de bits, mais où le poids d’un 0 ou d’un 1 a été pondéré.

La seconde grande force du range coding, c’est que, s’il peut coder deux valeurs qui sont "0" ou "1", donc diviser notre gâteau en deux à chaque fois, eh bien il peut aussi diviser notre gâteau en 256, ou en 3096, ou en ce qu’on veut. Dans ce cas, chaque sous-part aura la taille qu’on souhaite. Dans les faits, cela permet des optimisations. Pratique !

Pour être bien clair, quelle est la différence entre range coding et « arithmetic coding » ? Aucune, si ce n’est la manière dont on l’explique. Le range coding part du prince de prendre un nombre entier de la taille du flux à décoder et de le fractionner successivement, l’arithmetic coding part du principe de prendre le nombre décimal 11 et de le diviser successivement. Mais dans les deux cas, votre très volumineux nombre est encodé de la même manière et les deux concepts désignent les mêmes idées pour les mêmes résultats, aux détails d’implémentation près.

« Range coding » est le terme employé par le concepteur de LZMA, c’est pourquoi je l’ai employé ici, mais « arithmetic coding » est plus utilisé dans l’informatique en général.

Le format LZMA

Passé une courte en-tête de 13 octets, tout le flux LZMA est encodé en « range coding ». Le flux LZMA est donc un même grand nombre à lire et à décoder progressivement ; et à l’intérieur, c’est « presque » comme LZSS ou DEFLATE : des instructions soit de copie d’octets, soit de répétition. Ce format étant plus récent, les tailles de fenêtres glissantes possibles sont aussi plus élevées qu’avec DEFLATE.

Attention : même s’il n’y a qu’un seul flux de range coding, les probabilités (la taille des parts) ne sont pas les mêmes (et évoluent indépendamment) selon le type d’information que vous lisez. Cela fait qu’il y a plusieurs contextes de probabilités de range coding à maintenir en parallèle et pour cela, LZMA est un brin complexe à implémenter.

On va commencer par regarder l’en-tête fixe de 13 octets (tout est en little-endian) :

Nom du champ

Taille en octets

Description

properties

1

Propriétés du flux. Quatre valeurs sont encodées dans cet octet :

  • literal_context_bits (alias « lc ») : (octet % 9)

  • literal_position_bits (alias « lp ») : (octet / 9) % 5

  • position_bits (alias « pb ») : octet / (9 * 5)

Comme je l’ai rapidement expliqué ci-dessus, LZMA maintient de nombreux contextes de range coding (probabilité que le bit suivant soit un 0 ou un 1) différents en fonction de la situation.

Pour identifier le contexte suivant à utiliser, on va prendre des bits, soit sur le dernier octet lu, soit sur notre position dans le flux décompressé (par exemple, utiliser des contextes différents tous les 4 octets, ce qui peut être plus efficace pour compresser du langage machine où les adresses et/ou les instructions sont codées et alignées sur 4 ou 8 octets), ainsi que d’autres informations relevant du contexte (les dernières instructions LZMA lues, les derniers bits lus au sein de l’octet courant…).

Cela peut faire énormément d’informations différentes qui peuvent déterminer le contexte à utiliser, et énormément de contextes différents également. Pour s’adapter à la situation et aux caractéristiques du flux décompressé, LZMA donne la possibilité de modérer ou régler le nombre de contextes : par exemple, ne prendre que les "literal_context" bits les plus hauts du dernier octet lu, ne changer de contextes que tous les "literal_position" bits de contenus décompressés, etc.

dictionary_size

4

Taille du dictionnaire (de la fenêtre glissante), en octets.

uncompressed_size

8

Taille décompressée du flux LZMA. Si elle n’est pas connue, elle peut être laissée à 0xffffffffffffffff.

Le plus souvent, l’octet de propriétés est laissé à la valeur par défaut (0x5d), et la taille de la fenêtre glissante est au moins de 8 Ko (0x800000 octets), ce qui fait que notre flux LZMA commencera par les octets 5d 00 00.

Après l’en-tête, le premier octet du flux compressé est, par convention, toujours un zéro.

Ensuite, le flux à décompresser est un très grand flux range-codé en big-endian (forcément, sinon ce n’est plus du range coding). Il contient ce qui est appelé par la norme des « paquets ».

Le nom de LZMA signifie « Lempel-Ziv Markov ». Pourquoi Markov ?

En informatique, les chaînes de Markov sont un concept qui désigne le fait de faire évoluer un état à partir de la dernière donnée reçue, sans revenir sur les données précédentes.

C’est ce que fait LZMA lorsqu’il fait évoluer la probabilité d’un contexte du range coder à partir du dernier bit reçu.

L'état LZMA

Le décodeur LZMA peut être dans un état à la fois. Cet état est un nombre entier défini selon la situation du décodage (les instructions lues jusqu’ici).

Chaque contexte LZMA correspond à un ou plusieurs contextes (probabilités de 0 ou de 1 évoluant parallèlement) du range codeur.

La notion d’état est définie dans le fichier « lzma_specification.txt » du SDK (le SDK LZMA - « Software Development Kit », ou kit de développement logiciel est une grande archive qui contient la spécification LZMA, ainsi que des implémentations de LZMA dans différents langages), à partir de : « The "state" variable can get the value from 0 to 11. ».

L’état dépend des dernières actions effectuées (jusqu’aux trois ou quatre dernières) et n’est utilisé qu’à des fins heuristiques (déterminer l’option la plus adaptée - qui compressera probablement le mieux dans un cas donné, sur la base de l’observation des situations les plus proches uniquement).

L’état sert à optimiser le range coding lors de la lecture de nouvelles instructions, et pas de données brutes elles-même (pour cela il y a encore d’autres types d’états, constitués à partir des derniers bits ou octets décodés !). Il essaie de prédire ce que pourrait être prochaine action en fonction des précédentes.

L’état change à chaque nouvelle instruction lue par le décodeur (par exemple, la copie d’un octet brut ou une répétition).

L’état initial est « 0 ». Voici un tableau qui montre l’évolution de l’état en fonction des instructions lues par le décodeur / encodées par le décodeur (puisque l’état est maintenu par les deux).

Nom de l’instruction lue

Nouvel état, si la dernière action était une lecture d’octet brut (LITERAL)

Nouvel état, si la dernière action était une répétition

LITERAL (lecture d’un octet brut)

0, sauf si le dernier état était supérieur à 3, dans ce cas on enlève 3.

On enlève 3, sauf si le dernier état était supérieur à 9, dans ce cas on enlève 6.

MATCH (répétition en utilisant une nouvelle paire taille/distance)

7

10

SHORTREP (répétition réutilisant la dernière distance, d’un octet seulement)

9

11

LONGREP (répétition utilisant une des 4 dernières distances, pour une taille donnée)

8

11

Je viens de vous montrer les 4 instructions LZMA existantes (LITERAL, aussi appelée LIT ou CHAR, MATCH, SHORTREP et LONGREP, aussi appelée REP). Retenez-les bien, il n’y en a pas d’autres.

Une instruction, suivie des données afférentes (taille, distance, octet brut) peut être appelée « paquet ».

LZMA en Python

Voici la chaîne compressée que nous allons essayer de décoder (toujours en hexadécimal) :

5d00008000ffffffffffffffff0026184927701622bc8488f910d0e8a97ac23c8186ce02cd6d88a8122f609bef44eabf402a5645b510b414c7a347da70a3c50f4f33c9e27b3a0a7e75872f276c1733cb875dd3b0e10e80d5bf2b4cadd6706e20ecc38c3238888720f9202d5373436ccc9984d3d1d87bc2bb85128bfff8e62480

On va réutiliser la classe LecteurDeBits définie dans le précédent chapitre, mais on va aussi en définir une autre LecteurDeBitsRangeCode, qui nous permettra de lire progressivement le (très) grand nombre entier qui constitue le flux range codé :

"""
    Cette classe remplacera LecteurDeBits une fois qu'on sera
    en mode range codé (après l'en-tête LZMA)
"""

class LecteurDeBitsRangeCode:
    
    def __init__(self, entree : bytes):
        
        self.octets = BytesIO(entree)
        
        self.taille_code = 0xffffffff # La taille de notre nombre (« code ») (après découpages successifs)
        self.code = 0

        # Lecture de la valeur initiale de code (range coding)
        # Par convention, le premier octet est toujours à zéro
        
        assert self.octets.read(1)[0] == 0
        
        for position in range(4): # Big endian
            self.code = (self.code << 8) | self.octets.read(1)[0]
        
        assert self.code < self.taille_code
        

    def reprendre_des_bits_si_besoin(self):
        
        # On s'assure qu'il nous reste au moins 3 octets de code pour effectuer
        # notre décodage, sinon, les découpages risquent de ne plus être assez
        # précis : on en reprend un
        
        if self.taille_code <= 0xffffff:

            self.taille_code <<= 8
            self.code <<= 8
            
            self.code |= self.octets.read(1)[0]


Également, une classe qui effectuera le décodage du range coding pour un contexte (probabilité) à la fois :

"""
    Classe contenant un seul contexte de range decoder (une seule probabilité
    de répartition entre 0" et "1") donné. Plusieurs contextes évoluent en
    parallèle dans le vrai code.
"""

class RangeDecoder:

    """
        :param probabilite_initiale : comme le veut la spécification LZMA,
        les probabilités sont codées entre 0 et 0x800 (sur 11 bits). Elles
        commencent à 0x400 (50 %).
    """

    def __init__(self, lecteur_de_bits : LecteurDeBitsRangeCode, probabilite_initiale : int = 0x400):
        
        self.lecteur_de_bits : LecteurDeBitsRangeCode = lecteur_de_bits
        
        self.probabilite : int = probabilite_initiale # 0 - 0x800
    
    def lire_bit(self, utiliser_probas = True):
        
        if utiliser_probas:
            milieu_du_code_pondere = self.lecteur_de_bits.taille_code // 0x800 * self.probabilite
        else:
            milieu_du_code_pondere = self.lecteur_de_bits.taille_code // 2
            
        if self.lecteur_de_bits.code < milieu_du_code_pondere: # Limite basse : on a un "0"
            
            bit_lu = 0
            
            # On renforce la probabilité de lire un 0 ensuite, ce qui fera que
            # "0" nous demandera un peu moins de place à coder mais "1" un peu
            # plus.
            #
            # La première fois on la renforce de 32, mais on la renforcera
            # progressivement de moins en moins au fur et à mesure qu'on
            # s'approchera de 0x800.
            
            self.probabilite += (0x800 - self.probabilite) // 32
            
            # Il ne restera que la moitié basse (pondérée) du code à décoder
            # pour le prochain bit à lire, pour s'en souvenir on divise la taille.
            
            self.lecteur_de_bits.taille_code = milieu_du_code_pondere
            
        else: # Limite haute : on a un "1"
            
            bit_lu = 1
            
            self.probabilite -= self.probabilite // 32
            
            # On ne laisse que la moitié haute du code pour la prochaine
            # fois.
            
            self.lecteur_de_bits.code -= milieu_du_code_pondere
            if utiliser_probas:
                self.lecteur_de_bits.taille_code -= milieu_du_code_pondere
            else:
                self.lecteur_de_bits.taille_code = milieu_du_code_pondere
        
        
        self.lecteur_de_bits.reprendre_des_bits_si_besoin()
        
        return bit_lu

Enfin, voici la partie qui décodera le flux LZMA, en utilisant les classes ci-dessus :


class DecodeurLZMA:

    def decode(self, entree : bytes) -> bytes:
        
        self.flux_decompresse = b''
        
        self.dernieres_distances : List[int] = [0] * 4
        
        # Lecture de l'en-tête LZMA
        
        lecteur_de_bits = LecteurDeBits(entree)
        
        properties = lecteur_de_bits.lire_bits(8)
        
        self.literal_context_bits = properties % 9
        literal_position_bits = (properties // 9) % 5
        position_bits = properties // 9 // 5
        
        if position_bits > 4:
            raise ValueError('En-tête LZMA invalide')
        
        self.taille_fenetre = lecteur_de_bits.lire_bits(32)
        
        self.uncompressed_size = lecteur_de_bits.lire_bits(64)
        
        # Lecture range codée (sur le contenu présent après l'en-tête)
        
        lecteur_de_bits = LecteurDeBitsRangeCode(entree[13:])
        
        # Comme la norme LZMA demande de créer beaucoup de contextes
        # de range decoding différents, avec des probabilités
        # maintenues sépartement, on va simplifier notre code en
        # identifiant leurs noms par des tuples de chaînes et de
        # nombres.
        #
        # L'accès de chaque nouvelle tuple au sein du dictionnaire
        # entraînera la création d'un nouvel object RangeDecoder
        # associé au lecteur de bits range codés, et la création
        # d'un nouveau contexte de probabilité (au départ à 50 %)

        self.nom_vers_range_decodeur : Dict[tuple, RangeDecoder] = defaultdict(lambda: RangeDecoder(lecteur_de_bits))
        
        # Lecture des paquets LZMA range codés
        
        self.state = 0
        
        self.masque_pos_state = (1 << position_bits) - 1
        self.masque_lit_state = (1 << literal_position_bits) - 1
        
        while len(self.flux_decompresse) < self.uncompressed_size:
            
            try:
                    
                pos_state = len(self.flux_decompresse) & self.masque_pos_state
                
                bit_choice = self.nom_vers_range_decodeur[('IsMatch', self.state, pos_state)].lire_bit()

                if bit_choice == 0: # Lire un octet brut (paquet "LITERAL")
                    
                    self.LITERAL()


                elif bit_choice == 1: # Lire une répétition
                    
                    is_rep = self.nom_vers_range_decodeur[('IsRep', self.state)].lire_bit()
                    
                    if is_rep == 0: # Répétition simple (paquet "MATCH")
                        self.MATCH()
                    
                    elif is_rep == 1:
                        is_rep0 = self.nom_vers_range_decodeur[('IsRepG0', self.state)].lire_bit()
                        
                        if is_rep0 == 0:
                            is_rep0_long = self.nom_vers_range_decodeur[('IsRep0Long', self.state, pos_state)].lire_bit()
                            
                            if is_rep0_long == 0: # SHORTREP : répéter un octet de la dernière distance
                                self.SHORTREP()
                                
                            elif is_rep0_long == 1: # LONGREP[0] : répéter plusieurs octets de la dernière distance
                                self.LONGREP(0)
                        
                        elif is_rep0 == 1:
                            is_rep1 = self.nom_vers_range_decodeur[('IsRepG1', self.state)].lire_bit()
                            
                            if is_rep1 == 0: # LONGREP[1] : pour l'avant-dernière distance
                                self.LONGREP(1)
                                
                            elif is_rep1 == 1:
                                is_rep2 = self.nom_vers_range_decodeur[('IsRepG2', self.state)].lire_bit()
                                
                                if is_rep2 == 0: # LONGREP[2] : pour l'avant-avant-dernière distance
                                    self.LONGREP(2)
                                    
                                elif is_rep2 == 1: # LONGREP[3] : pour l'avant-avant-avant-dernière distance
                                    self.LONGREP(3)
                                
        
            except EOFError: # Propager la fin de flux, lorsqu'on rencontre une distance de "0xffffffff" octets
                
                break
        
        return self.flux_decompresse

    # Instruction pour lire un octet brut

    def LITERAL(self):
        
        dernier_octet_decompresse = self.flux_decompresse[-1] if self.flux_decompresse else 0
    
        octet_lu = 0
    
        on_vient_apres_une_repetition = (self.state >= 7)
    
        # Si on vient après une répétition, on va mélanger notre
        # état avec les bits de l'octet situé à la position
        # corresponante dans la répétition
    
        if on_vient_apres_une_repetition:
            
            octet_a_distance_dans_la_derniere_repetition = self.flux_decompresse[-(1 + self.dernieres_distances[-1])]
            
            for position_bit in range(8):
            
                bit_dans_la_derniere_repetition = (octet_a_distance_dans_la_derniere_repetition >> (7 - position_bit)) & 1
            
                bit_lu = self.nom_vers_range_decodeur[('LiteralWithMatchByte',
                    len(self.flux_decompresse) & self.masque_lit_state, # total_pos
                    dernier_octet_decompresse >> (8 - self.literal_context_bits), # prev_byte
                    octet_lu, # octet_lu
                    position_bit, # bits_lu
                    bit_dans_la_derniere_repetition
                )].lire_bit()
            
                octet_lu <<= 1
                octet_lu |= bit_lu
                
                if bit_lu != bit_dans_la_derniere_repetition:
                    
                    # Si l'octet lu ne continue plus comme
                    # l'octet de la répétition précédente,
                    #  alors on lit le reste de l'octet avec
                    # le contexte « normal »
                    
                    octet_lu = self.bit_tree_decode(('LiteralNormal',
                            len(self.flux_decompresse) & self.masque_lit_state, # total_pos
                            dernier_octet_decompresse >> (8 - self.literal_context_bits), # prev_byte
                        ), None, 8, use_pos_state = False,
                        
                        bit_tree_lu = octet_lu, debut_bit_tree = position_bit + 1)
                    
                    break

        else:
            octet_lu = self.bit_tree_decode(('LiteralNormal',
                len(self.flux_decompresse) & self.masque_lit_state, # total_pos
                dernier_octet_decompresse >> (8 - self.literal_context_bits), # prev_byte
            ), None, 8, use_pos_state = False)
            
        # On ajoute l'octet décodé
            
        self.flux_decompresse += bytes([octet_lu])
        
        # On met à jour l'état
        
        if self.state > 9:
            self.state -= 6
        elif self.state > 3:
            self.state -= 3
        else:
            self.state = 0
    
    # Instruction pour effectuer une répétition simple
    
    def MATCH(self):
        
        match_len = 2 + self.len_decode('LenDecoder')
        
        pos_slot = self.bit_tree_decode(('PosSlot', min(5, match_len)), None, 6, use_pos_state = False)
        
        if pos_slot >= 4:
            num_direct_bits = (pos_slot >> 1) - 1
            distance = (2 | (pos_slot & 1)) << num_direct_bits
            if pos_slot < 14:
                distance += self.bit_tree_decode('SpecPos', None, num_direct_bits + (distance - pos_slot - 1),
                    use_pos_state = False, reverse = True,
                    debut_bit_tree = distance - pos_slot - 1)
            else:
                distance += self.bit_tree_decode('AlignFixed', None, num_direct_bits - 4, utiliser_probas = False) << 4
                distance += self.bit_tree_decode('Align', None, 4, use_pos_state = False, reverse = True)

        else:
            distance = pos_slot
        
        self.dernieres_distances.append(distance)
        
        if distance == 0xffffffff:
            raise EOFError
        
        # Effectuer la répétition
        
        assert distance < len(self.flux_decompresse)
        assert distance < self.taille_fenetre
        
        self.repeter_donnees(distance, match_len)
    
        # Mettre à jour l'état
    
        if self.state < 7:
            self.state = 7
        else:
            self.state = 10
        
    def SHORTREP(self): # Réutiliser la dernière distance pour un octet
        if self.state < 7:
            self.state = 9
        else:
            self.state = 11
        
        self.repeter_donnees(self.dernieres_distances[-1], 1)
        
    def LONGREP(self, num): # Réutiliser l'une des dernières distances pour une taille donnée
        match_len = 2 + self.len_decode('RepLenDecoder')
        
        # On remet la distance à répéter à la fin de la liste des dernières
        # distances, si elle ne l'est pas déjà
        
        self.dernieres_distances.append(self.dernieres_distances.pop(-(1 + num)))
        
        distance = self.dernieres_distances[-1]
        
        self.repeter_donnees(distance, match_len)
        
        if self.state < 7:
            self.state = 8
        else:
            self.state = 11
    
    # Fonction pour répéter des données, et revenir au début des données
    # à répéter si la taille indiquée est plus grande que les données
    # disponibles
    
    def repeter_donnees(self, distance, match_len):
    
        debut_slice = len(self.flux_decompresse) - (1 + distance)
        fin_slice = match_len
    
        a_repeter = self.flux_decompresse[debut_slice:debut_slice + fin_slice]
        
        fin_slice -= len(self.flux_decompresse) - debut_slice
        
        while fin_slice > 0:
            a_repeter += self.flux_decompresse[debut_slice:debut_slice + fin_slice]
            
            fin_slice -= min(len(self.flux_decompresse), debut_slice + fin_slice) - debut_slice
    
        # Ajouter les données
    
        self.flux_decompresse += a_repeter

    
    # Décoder une taille (taille de taille, et contexte des bits de la
    # taille, et contexte des bits de la taille de la taille (!) variables
    # selon la taille de la taille, vous voyez que l'optimisation n'est
    # pas en reste ?)
    
    def len_decode(self, len_decoder_name):
        
        if self.nom_vers_range_decodeur[('LenChoice', len_decoder_name)].lire_bit() == 0:
            
            return self.bit_tree_decode('LenLow', len_decoder_name, 3)
        
        else:
            
            if self.nom_vers_range_decodeur[('LenChoice2', len_decoder_name)].lire_bit() == 0:
                
                return (1 << 3) + self.bit_tree_decode('LenMid', len_decoder_name, 3)
            
            else:
                
                return (1 << 4) + self.bit_tree_decode('LenHigh', len_decoder_name, 8, use_pos_state = False)
    
    """
        bit_tree_decode : Décoder une chaîne de bits, dont le contexte de range
        conding dépend des bits lus jusqu'à là eux-mêmes
    """
    
    def bit_tree_decode(self, bit_tree_decoder_name, len_decoder_name, num_bits,
        use_pos_state = True, utiliser_probas = True, reverse = False,
        
        bit_tree_lu = 0, debut_bit_tree = 0):
    
        # Passer sur chaque bit
        
        for position_bit in range(debut_bit_tree, num_bits):
        
            bit_lu = self.nom_vers_range_decodeur[(
                bit_tree_decoder_name,
                len_decoder_name,
                
                bit_tree_lu,
                position_bit,
                
                (len(self.flux_decompresse) & self.masque_pos_state) if use_pos_state else None,
            )].lire_bit(utiliser_probas = utiliser_probas)
            
            # Les bits sont généralement écrits dans l'ordre MSB (most
            # significant bit first, bit le plus important en premier),
            # mais certaines information peuvent être en LSB
            
            if not reverse:
                bit_tree_lu <<= 1
                bit_tree_lu |= bit_lu
            else:
                bit_tree_lu |= bit_lu << (position_bit - debut_bit_tree)
        
        return bit_tree_lu

Elle s’appelle de la sorte :

print(DecodeurLZMA().decode(bytes.fromhex('5d00008000ffffffffffffffff0026184927701622bc8488f910d0e8a97ac23c8186ce02cd6d88a8122f609bef44eabf402a5645b510b414c7a347da70a3c50f4f33c9e27b3a0a7e75872f276c1733cb875dd3b0e10e80d5bf2b4cadd6706e20ecc38c3238888720f9202d5373436ccc9984d3d1d87bc2bb85128bfff8e62480')).decode('utf8'))

Voici ce que donne notre code, une fois les différents morceaux recollés ensemble :

#!/usr/bin/python3
#-*- encoding: Utf-8 -*-

from typing import List, Dict, Set, Sequence, Union
from collections import defaultdict
from io import BytesIO

class LecteurDeBits:
    
    def __init__(self, entree : bytes):
        
        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
    
"""
    Cette classe remplacera LecteurDeBits une fois qu'on sera
    en mode range codé (après l'en-tête LZMA)
"""

class LecteurDeBitsRangeCode:
    
    def __init__(self, entree : bytes):
        
        self.octets = BytesIO(entree)
        
        self.taille_code = 0xffffffff # La taille de notre nombre (« code ») (après découpages successifs)
        self.code = 0

        # Lecture de la valeur initiale de code (range coding)
        # Par convention, le premier octet est toujours à zéro
        
        assert self.octets.read(1)[0] == 0
        
        for position in range(4): # Big endian
            self.code = (self.code << 8) | self.octets.read(1)[0]
        
        assert self.code < self.taille_code
        

    def reprendre_des_bits_si_besoin(self):
        
        # On s'assure qu'il nous reste au moins 3 octets de code pour effectuer
        # notre décodage, sinon, les découpages risquent de ne plus être assez
        # précis : on en reprend un
        
        if self.taille_code <= 0xffffff:

            self.taille_code <<= 8
            self.code <<= 8
            
            self.code |= self.octets.read(1)[0]








"""
    Classe contenant un seul contexte de range decoder (une seule probabilité
    de répartition entre 0" et "1") donné. Plusieurs contextes évoluent en
    parallèle dans le vrai code.
"""

class RangeDecoder:

    """
        :param probabilite_initiale : comme le veut la spécification LZMA,
        les probabilités sont codées entre 0 et 0x800 (sur 11 bits). Elles
        commencent à 0x400 (50 %).
    """

    def __init__(self, lecteur_de_bits : LecteurDeBitsRangeCode, probabilite_initiale : int = 0x400):
        
        self.lecteur_de_bits : LecteurDeBitsRangeCode = lecteur_de_bits
        
        self.probabilite : int = probabilite_initiale # 0 - 0x800
    
    def lire_bit(self, utiliser_probas = True):
        
        if utiliser_probas:
            milieu_du_code_pondere = self.lecteur_de_bits.taille_code // 0x800 * self.probabilite
        else:
            milieu_du_code_pondere = self.lecteur_de_bits.taille_code // 2
            
        if self.lecteur_de_bits.code < milieu_du_code_pondere: # Limite basse : on a un "0"
            
            bit_lu = 0
            
            # On renforce la probabilité de lire un 0 ensuite, ce qui fera que
            # "0" nous demandera un peu moins de place à coder mais "1" un peu
            # plus.
            #
            # La première fois on la renforce de 32, mais on la renforcera
            # progressivement de moins en moins au fur et à mesure qu'on
            # s'approchera de 0x800.
            
            self.probabilite += (0x800 - self.probabilite) // 32
            
            # Il ne restera que la moitié basse (pondérée) du code à décoder
            # pour le prochain bit à lire, pour s'en souvenir on divise la taille.
            
            self.lecteur_de_bits.taille_code = milieu_du_code_pondere
            
        else: # Limite haute : on a un "1"
            
            bit_lu = 1
            
            self.probabilite -= self.probabilite // 32
            
            # On ne laisse que la moitié haute du code pour la prochaine
            # fois.
            
            self.lecteur_de_bits.code -= milieu_du_code_pondere
            if utiliser_probas:
                self.lecteur_de_bits.taille_code -= milieu_du_code_pondere
            else:
                self.lecteur_de_bits.taille_code = milieu_du_code_pondere
        
        
        self.lecteur_de_bits.reprendre_des_bits_si_besoin()
        
        return bit_lu
        
        


class DecodeurLZMA:

    def decode(self, entree : bytes) -> bytes:
        
        self.flux_decompresse = b''
        
        self.dernieres_distances : List[int] = [0] * 4
        
        # Lecture de l'en-tête LZMA
        
        lecteur_de_bits = LecteurDeBits(entree)
        
        properties = lecteur_de_bits.lire_bits(8)
        
        self.literal_context_bits = properties % 9
        literal_position_bits = (properties // 9) % 5
        position_bits = properties // 9 // 5
        
        if position_bits > 4:
            raise ValueError('En-tête LZMA invalide')
        
        self.taille_fenetre = lecteur_de_bits.lire_bits(32)
        
        self.uncompressed_size = lecteur_de_bits.lire_bits(64)
        
        # Lecture range codée (sur le contenu présent après l'en-tête)
        
        lecteur_de_bits = LecteurDeBitsRangeCode(entree[13:])
        
        # Comme la norme LZMA demande de créer beaucoup de contextes
        # de range decoding différents, avec des probabilités
        # maintenues sépartement, on va simplifier notre code en
        # identifiant leurs noms par des tuples de chaînes et de
        # nombres.
        #
        # L'accès de chaque nouvelle tuple au sein du dictionnaire
        # entraînera la création d'un nouvel object RangeDecoder
        # associé au lecteur de bits range codés, et la création
        # d'un nouveau contexte de probabilité (au départ à 50 %)

        self.nom_vers_range_decodeur : Dict[tuple, RangeDecoder] = defaultdict(lambda: RangeDecoder(lecteur_de_bits))
        
        # Lecture des paquets LZMA range codés
        
        self.state = 0
        
        self.masque_pos_state = (1 << position_bits) - 1
        self.masque_lit_state = (1 << literal_position_bits) - 1
        
        while len(self.flux_decompresse) < self.uncompressed_size:
            
            try:
                    
                pos_state = len(self.flux_decompresse) & self.masque_pos_state
                
                bit_choice = self.nom_vers_range_decodeur[('IsMatch', self.state, pos_state)].lire_bit()

                if bit_choice == 0: # Lire un octet brut (paquet "LITERAL")
                    
                    self.LITERAL()


                elif bit_choice == 1: # Lire une répétition
                    
                    is_rep = self.nom_vers_range_decodeur[('IsRep', self.state)].lire_bit()
                    
                    if is_rep == 0: # Répétition simple (paquet "MATCH")
                        self.MATCH()
                    
                    elif is_rep == 1:
                        is_rep0 = self.nom_vers_range_decodeur[('IsRepG0', self.state)].lire_bit()
                        
                        if is_rep0 == 0:
                            is_rep0_long = self.nom_vers_range_decodeur[('IsRep0Long', self.state, pos_state)].lire_bit()
                            
                            if is_rep0_long == 0: # SHORTREP : répéter un octet de la dernière distance
                                self.SHORTREP()
                                
                            elif is_rep0_long == 1: # LONGREP[0] : répéter plusieurs octets de la dernière distance
                                self.LONGREP(0)
                        
                        elif is_rep0 == 1:
                            is_rep1 = self.nom_vers_range_decodeur[('IsRepG1', self.state)].lire_bit()
                            
                            if is_rep1 == 0: # LONGREP[1] : pour l'avant-dernière distance
                                self.LONGREP(1)
                                
                            elif is_rep1 == 1:
                                is_rep2 = self.nom_vers_range_decodeur[('IsRepG2', self.state)].lire_bit()
                                
                                if is_rep2 == 0: # LONGREP[2] : pour l'avant-avant-dernière distance
                                    self.LONGREP(2)
                                    
                                elif is_rep2 == 1: # LONGREP[3] : pour l'avant-avant-avant-dernière distance
                                    self.LONGREP(3)
                                
        
            except EOFError: # Propager la fin de flux, lorsqu'on rencontre une distance de "0xffffffff" octets
                
                break
        
        return self.flux_decompresse

    # Instruction pour lire un octet brut

    def LITERAL(self):
        
        dernier_octet_decompresse = self.flux_decompresse[-1] if self.flux_decompresse else 0
    
        octet_lu = 0
    
        on_vient_apres_une_repetition = (self.state >= 7)
    
        # Si on vient après une répétition, on va mélanger notre
        # état avec les bits de l'octet situé à la position
        # corresponante dans la répétition
    
        if on_vient_apres_une_repetition:
            
            octet_a_distance_dans_la_derniere_repetition = self.flux_decompresse[-(1 + self.dernieres_distances[-1])]
            
            for position_bit in range(8):
            
                bit_dans_la_derniere_repetition = (octet_a_distance_dans_la_derniere_repetition >> (7 - position_bit)) & 1
            
                bit_lu = self.nom_vers_range_decodeur[('LiteralWithMatchByte',
                    len(self.flux_decompresse) & self.masque_lit_state, # total_pos
                    dernier_octet_decompresse >> (8 - self.literal_context_bits), # prev_byte
                    octet_lu, # octet_lu
                    position_bit, # bits_lu
                    bit_dans_la_derniere_repetition
                )].lire_bit()
            
                octet_lu <<= 1
                octet_lu |= bit_lu
                
                if bit_lu != bit_dans_la_derniere_repetition:
                    
                    # Si l'octet lu ne continue plus comme
                    # l'octet de la répétition précédente,
                    #  alors on lit le reste de l'octet avec
                    # le contexte « normal »
                    
                    octet_lu = self.bit_tree_decode(('LiteralNormal',
                            len(self.flux_decompresse) & self.masque_lit_state, # total_pos
                            dernier_octet_decompresse >> (8 - self.literal_context_bits), # prev_byte
                        ), None, 8, use_pos_state = False,
                        
                        bit_tree_lu = octet_lu, debut_bit_tree = position_bit + 1)
                    
                    break

        else:
            octet_lu = self.bit_tree_decode(('LiteralNormal',
                len(self.flux_decompresse) & self.masque_lit_state, # total_pos
                dernier_octet_decompresse >> (8 - self.literal_context_bits), # prev_byte
            ), None, 8, use_pos_state = False)
            
        # On ajoute l'octet décodé
            
        self.flux_decompresse += bytes([octet_lu])
        
        # On met à jour l'état
        
        if self.state > 9:
            self.state -= 6
        elif self.state > 3:
            self.state -= 3
        else:
            self.state = 0
    
    # Instruction pour effectuer une répétition simple
    
    def MATCH(self):
        
        match_len = 2 + self.len_decode('LenDecoder')
        
        pos_slot = self.bit_tree_decode(('PosSlot', min(5, match_len)), None, 6, use_pos_state = False)
        
        if pos_slot >= 4:
            num_direct_bits = (pos_slot >> 1) - 1
            distance = (2 | (pos_slot & 1)) << num_direct_bits
            if pos_slot < 14:
                distance += self.bit_tree_decode('SpecPos', None, num_direct_bits + (distance - pos_slot - 1),
                    use_pos_state = False, reverse = True,
                    debut_bit_tree = distance - pos_slot - 1)
            else:
                distance += self.bit_tree_decode('AlignFixed', None, num_direct_bits - 4, utiliser_probas = False) << 4
                distance += self.bit_tree_decode('Align', None, 4, use_pos_state = False, reverse = True)

        else:
            distance = pos_slot
        
        self.dernieres_distances.append(distance)
        
        if distance == 0xffffffff:
            raise EOFError
        
        # Effectuer la répétition
        
        assert distance < len(self.flux_decompresse)
        assert distance < self.taille_fenetre
        
        self.repeter_donnees(distance, match_len)
    
        # Mettre à jour l'état
    
        if self.state < 7:
            self.state = 7
        else:
            self.state = 10
        
    def SHORTREP(self): # Réutiliser la dernière distance pour un octet
        if self.state < 7:
            self.state = 9
        else:
            self.state = 11
        
        self.repeter_donnees(self.dernieres_distances[-1], 1)
        
    def LONGREP(self, num): # Réutiliser l'une des dernières distances pour une taille donnée
        match_len = 2 + self.len_decode('RepLenDecoder')
        
        # On remet la distance à répéter à la fin de la liste des dernières
        # distances, si elle ne l'est pas déjà
        
        self.dernieres_distances.append(self.dernieres_distances.pop(-(1 + num)))
        
        distance = self.dernieres_distances[-1]
        
        self.repeter_donnees(distance, match_len)
        
        if self.state < 7:
            self.state = 8
        else:
            self.state = 11
    
    # Fonction pour répéter des données, et revenir au début des données
    # à répéter si la taille indiquée est plus grande que les données
    # disponibles
    
    def repeter_donnees(self, distance, match_len):
    
        debut_slice = len(self.flux_decompresse) - (1 + distance)
        fin_slice = match_len
    
        a_repeter = self.flux_decompresse[debut_slice:debut_slice + fin_slice]
        
        fin_slice -= len(self.flux_decompresse) - debut_slice
        
        while fin_slice > 0:
            a_repeter += self.flux_decompresse[debut_slice:debut_slice + fin_slice]
            
            fin_slice -= min(len(self.flux_decompresse), debut_slice + fin_slice) - debut_slice
    
        # Ajouter les données
    
        self.flux_decompresse += a_repeter

    
    # Décoder une taille (taille de taille, et contexte des bits de la
    # taille, et contexte des bits de la taille de la taille (!) variables
    # selon la taille de la taille, vous voyez que l'optimisation n'est
    # pas en reste ?)
    
    def len_decode(self, len_decoder_name):
        
        if self.nom_vers_range_decodeur[('LenChoice', len_decoder_name)].lire_bit() == 0:
            
            return self.bit_tree_decode('LenLow', len_decoder_name, 3)
        
        else:
            
            if self.nom_vers_range_decodeur[('LenChoice2', len_decoder_name)].lire_bit() == 0:
                
                return (1 << 3) + self.bit_tree_decode('LenMid', len_decoder_name, 3)
            
            else:
                
                return (1 << 4) + self.bit_tree_decode('LenHigh', len_decoder_name, 8, use_pos_state = False)
    
    """
        bit_tree_decode : Décoder une chaîne de bits, dont le contexte de range
        conding dépend des bits lus jusqu'à là eux-mêmes
    """
    
    def bit_tree_decode(self, bit_tree_decoder_name, len_decoder_name, num_bits,
        use_pos_state = True, utiliser_probas = True, reverse = False,
        
        bit_tree_lu = 0, debut_bit_tree = 0):
    
        # Passer sur chaque bit
        
        for position_bit in range(debut_bit_tree, num_bits):
        
            bit_lu = self.nom_vers_range_decodeur[(
                bit_tree_decoder_name,
                len_decoder_name,
                
                bit_tree_lu,
                position_bit,
                
                (len(self.flux_decompresse) & self.masque_pos_state) if use_pos_state else None,
            )].lire_bit(utiliser_probas = utiliser_probas)
            
            # Les bits sont généralement écrits dans l'ordre MSB (most
            # significant bit first, bit le plus important en premier),
            # mais certaines information peuvent être en LSB
            
            if not reverse:
                bit_tree_lu <<= 1
                bit_tree_lu |= bit_lu
            else:
                bit_tree_lu |= bit_lu << (position_bit - debut_bit_tree)
        
        return bit_tree_lu

        
print(DecodeurLZMA().decode(bytes.fromhex('5d00008000ffffffffffffffff0026184927701622bc8488f910d0e8a97ac23c8186ce02cd6d88a8122f609bef44eabf402a5645b510b414c7a347da70a3c50f4f33c9e27b3a0a7e75872f276c1733cb875dd3b0e10e80d5bf2b4cadd6706e20ecc38c3238888720f9202d5373436ccc9984d3d1d87bc2bb85128bfff8e62480')).decode('utf8'))


Voici le résultat qui s’affiche lorsqu’on lance le programme :

Laissez passer, je vais m'en occuper
Laissez passer, je vais t'faire oublier
Laisse-moi m'en occuper, oui, laisse-moi t'faire oublier
Tout le mal qu'on t'a fait, je serai ton bouclier

Il s’agit du refrain de ce morceau de Maître Gims.

Tu n’as pas pu faire ça !

Maintenant, ce tutoriel a été ambiancé ! :soleil:


En conclusion, nous avons pu observer que les grands algorithmes de la génération de DEFLATE et LZMA sont optimisés à deux niveaux, les séquences de bits et les séquences d’octets. Pour les séquences d’octets, les principes n’ont pas évolué depuis LZSS et on retrouve notre bonne vieille fenêtre glissante.

Pour les séquences de bits, le but est toujours de faire prendre moins de place aux séquences qui reviennent souvent (et plus aux séquences qui reviennent rarement), on remplace le codage Huffman par le range coding avec LZMA, celui-ci ayant la particularité de s’adapter automatiquement et progressivement au contexte, plutôt que d’utiliser des codes pré-définis.

Liens utiles :