C'est une très petite bibliothèque de compression et de décompression pour les systèmes embarqués.
Elle est très rapide et ne consomme pas trop de ressources.
Elle utilise moins de 100 lignes de code, compile à moins de 820 octets sur ARM (moins de 300 octets pour le décompresseur seulement).
Il n'est pas aussi efficace que Heatshrink en termes de taux de compression, mais il est beaucoup plus rapide (8x plus rapide en compression et 4.5x plus rapide en décompression).
Le code sous licence GPLv3 est disponible ici
L'algorithme est basé sur le compresseur LZJB d'OpenZFS. Il s'agit d'un Lempel Ziv avec des modifications de Jeff Bonwick.
Comme tous les autres algorithmes LZ, la compression fonctionne en trouvant les sous-chaînes identiques dans le flux source et en les remplaçant par des références (décalage de la position actuelle par rapport au texte source, et longueur de la sous-chaîne correspondante). Le compresseur analyse le flux source et calcule un hachage des 3 octets suivants. Ce hachage est utilisé pour indexer une table de hachage stockant la dernière position de la valeur hachée. Au démarrage, aucune position n'est enregistrée dans la table de hachage. Ensuite, la première position est enregistrée et la recherche continue.
En cas de préfixe de sous-chaîne identique, le hachage correspondra et l'offset du flux source sera récupéré dans la table de hachage.
À partir de ce décalage, l'algorithme calcule la longueur maximale de la sous-chaîne identique.
Ensuite, le compresseur émettra une référence de correspondance au lieu de la sous-chaîne (la référence étant ici beaucoup plus petite que la sous-chaîne).
Pour que le décompresseur soit capable de reconstruire le flux source, il doit savoir quand une séquence de code est une correspondance et quand c'est le flux source. Cela se fait à l'aide d'un bitmap de 8 bits qui stocke le fait que les octets suivants sont des sources ou des références (un bit à 1 est utilisé pour marquer une référence). Donc pour chaque 8 octets de données compressées, il y a un octet supplémentaire pour le type de bitmap.
Cela rend la décompression très rapide et simple (elle fait principalement un seul test de bit par octet de sortie). La compression n'est pas non plus complexe et peut être intégrée dans le logiciel.
L'inconvénient de ce système est le taux de compression relativement moins efficace par rapport aux autres algorithmes de compression qui utilisent en plus un codage entropique.
Le fichier source utilisé pour ce benchmark est un fichier G-Code de 309 564 bytes
| Algorithm | Compressor binary size | Decompressor binary size | Internal memory | Compressed data size |
|---|---|---|---|---|
| Heatshrink | 1964 bytes (ARM) | 1336 bytes (ARM) | < 40 bytes (decomp) | 135 398 bytes |
| Heatshrink | 2176 bytes (AVR) | 1268 bytes (AVR) | < 40 bytes (decomp) | |
| T2C | 528 bytes (ARM) | 292 bytes (ARM) | 512/4 bytes (comp/decomp) | 196 217 bytes |
| T2C | 618 bytes (AVR) | 300 bytes (AVR) | 512/4 bytes (comp/decomp) | |
| T2C(128) | 528 bytes (ARM) | 292 bytes (ARM) | 256/4 bytes (comp/decomp) | 199 021 bytes |
| T2C(128) | 618 bytes (AVR) | 300 bytes (AVR) | 256/4 bytes (comp/decomp) |
T2C peut être compilé avec une table de hash plus petite (jusqu'à 128 buckets / 256 bytes) mais cela réduit sont facteur de compression. Quelque soit la taille de la table de hash, le code du décompresseur pourra décompresser le flux.
Heatshrink n'est pas conçu pour la compression embarquée. La compression doit être réalisée par un CPU puissant et seulement la décompression est conçue pour fonctionner sur un CPU embarqué.