compresseur - décompresseur LZ48
par roudoudou - cet article est sous licence
modification,reproduction libre, citation de l'auteur

________________________________

sources:
Z80 assembly decrunch routine
Z80 assembly cruncher (maj 26 septembre 2016)
C source file


Pour les besoins d'un futur projet, j'ai besoin d'un compresseur/décompresseur qui soit capable de plusieurs choses:
- compresser correctement des petits morceaux de données
- ne refuse pas de produire un fichier si les données sont incompressibles
- soit très rapide à décompresser
- la décompression puisse s'exécuter d'une ROM et sans mémoire tampon

Il n'y a à ce jour aucun compresseur existant qui réponde à ces besoins

J'ai donc inventé un nouveau format de compression adapté d'un format existant, le LZ4 de Yann Collet. Les modifications apportées tirent avantage de l'architecture du Z80. Le format est architecturé autour de la routine de décompression, charge au compresseur de produire un fichier adapté à la routine de décompression. Cela permet de générer un flux dont le traitement est simplifié au maximum.
La routine de décompression fait seulement 83 octets


Description d'un flux LZ48 complet


Tout flux commence par un octet de donnée litérale que l'on recopie tel que.

Ensuite s'enchainent un ou plusieurs blocs jusqu'au dernier bloc dont l'offset sera NULL

Description du token:
Il contient à la fois une longueur de données litérales à recopier et une longueur de clef

4 bits du haut: longueur litérale entre 0 et 15
Si la longueur est égale à 15, alors on lit un octet de plus de longueur étendue (valeur entre 0 et 255) qu'on ajoute à la longueur en cours.
Si la longueur étendue est égale à 255 alors on lit à nouveau un autre octet de longueur étendue et ainsi de suite.

4 bits du bas: longueur de clef entre 0 et 15
Si la longueur est égale à 15, alors on lit un octet de plus de longueur étendue (valeur entre 0 et 255) qu'on ajoute à la longueur en cours.
Si la longueur étendue est égale à 255 alors on lit à nouveau un autre octet de longueur étendue et ainsi de suite.

Enfin, on ajoutera 3 à la longueur de clef finale car c'est la longueur minimale d'une clef.

Description de l'offset:
Distance absolue de l'offset courant à l'offset de la clef à recopier, -1 octet
pour copier de l'octet précédent, la valeur d'offset est 0
pour copier du cinquième octet précédent, la valeur d'offset est 4
pour copier 255 octets en arrière, la valeur d'offset est 254
pour terminer le flux, la valeur d'offset est 255


Le format LZ48 étant un pur format à l'octet (pas d'offset ou de longueur 16bits), il n'y a aucune problématique little-endian ou big-endian.



Merci à Yann Collet pour le LZ4 original / Octoate pour la motivation à optimiser le décompresseur


© 2016 www.roudoudou.com