ZPAQ

Les fichiers sont enregistrés au format de journalisation ZPAQ niveau 2[2]. La norme définit deux formats - le streaming et la journalisation. Seul le format de journalisation prend en charge la déduplication, les attributs de répertoire et les versions de fichiers datées multiples.

Le format d'archive en continu est conçu pour être extrait en un seul passage. Une archive est divisée en une séquence de blocs qui peuvent être décompressés indépendamment en parallèle. Les blocs sont divisés en segments qui doivent être décompressés séquentiellement dans l'ordre. Chaque en-tête de bloc contient une description de l'algorithme de décompression. Chaque segment a un en-tête contenant un nom de fichier facultatif et un commentaire facultatif pour les métadonnées telles que la taille, la date et les attributs, et une somme de contrôle SHA-1 finale facultative des données d'origine pour la vérification de l'intégrité. Si le nom du fichier est omis, il est supposé être une continuation du dernier fichier nommé, qui peut être dans le bloc précédent. Ainsi, l'insertion, la suppression ou la réorganisation des blocs dans une archive en continu a pour effet d'effectuer les mêmes opérations sur les données que les blocs représentent.

Le format de journalisation consiste en une séquence de transactions, ou mises à jour. Une mise à jour contient 4 types de blocs : un bloc d'en-tête de transaction, une séquence de blocs de données, une séquence correspondante de tables de fragments et une séquence de blocs d'index. Un bloc d'en-tête de transaction contient la date de transaction et un pointeur sautant les blocs de données pour permettre une lecture rapide de l'index d'archive. Les blocs de données contiennent une séquence de fragments de fichiers compressés ensemble. Les tables de fragments donnent la taille et le hachage SHA-1 de chaque fragment. Les blocs d'index contiennent une liste des modifications apportées à l'index d'archive global. Une modification est soit une mise à jour de fichier, soit une suppression de fichier. Une mise à jour inclut un nom de fichier, la date de la dernière modification, des attributs et une liste de pointeurs de fragment dans les transactions en cours et précédentes. Les fragments peuvent être partagés par plusieurs fichiers. Une suppression ne supprime aucune donnée de l'archive, mais indique plutôt que le fichier ne doit pas être extrait à moins que l'archive ne soit restaurée à une date antérieure.

La norme ZPAQ ne spécifie pas d'algorithme de compression. Au lieu de cela, il spécifie un format pour représenter l'algorithme de décompression dans les en-têtes de bloc. Les algorithmes de décompression sont écrits dans un langage appelé ZPAQL et stockés sous forme de code d'octet qui peut être interprété ou converti directement en code x86 32 ou 64 bits et exécuté. Un programme ZPAQL comporte 3 parties.

• COMP - Une chaîne facultative de composants de modélisation de contexte.
• HCOMP - Code machine pour le calcul des contextes des composants COMP.
• PCOMP - Code machine facultatif pour le post-traitement des données décodées.

Les modèles COMP sont basés sur PAQ, qui compresse un bit à la fois en utilisant le codage arithmétique . Il existe 9 types de composants. Chaque composant prend un contexte et éventuellement les prédictions des composants précédents, et génère une prédiction ou une probabilité que le bit suivant soit un 1. La sortie du dernier composant est codée arithmétiquement. Les types de composants sont :

• CONST - Une prédiction fixe.
• CM - Modèle de contexte. Le contexte est utilisé pour rechercher une prédiction dans une table. Lors de la mise à jour, l'entrée sélectionnée est ajustée pour réduire l'erreur de prédiction.
• ICM - Modèle de contexte indirect. Le contexte est utilisé pour rechercher un état de 8 bits représentant un historique de bits récent. L'historique sélectionne une prédiction comme avec un CM.
• MIX - Un groupe de prédictions est combiné par moyenne pondérée dans le domaine logistique, ou log(p/(1-p)). Les poids sont sélectionnés par un contexte. Lors de la mise à jour, les pondérations sont ajustées pour favoriser les entrées les plus précises.
• MIX2 - Un MIX à 2 entrées avec des poids contraints de s'additionner à 1.
• AVG - Un MIX2 avec des poids fixes.
• SSE - Estimateur de symbole secondaire. Recherche une prédiction à partir d'une table interpolée en fonction d'un contexte et d'une prédiction quantifiée à partir d'un autre composant.
• ISSE - Estimateur indirect de symboles secondaires. Le contexte sélectionne un historique de bits comme avec un ICM, puis l'historique de bits sélectionne une paire de poids pour mélanger l'entrée avec une constante 1.
• MATCH - Recherche l'occurrence précédente du contexte et prédit le bit suivi, avec une force dépendant de la longueur de la correspondance.

La section HCOMP calcule les contextes des composants de la section COMP. C'est une machine virtuelle dont l'état est de 4 registres de 32 bits (A, B, C, D), un compteur de programme de 16 bits, un bit d'indicateur de condition et deux matrices de mémoire, une d'octets (M) et une de 32 bits. mots (H). Le début de H forme le tableau des contextes. Un programme de type langage assembleur est appelé une fois pour chaque octet codé ou décodé avec cet octet comme entrée dans A. Le contexte final vu par la section COMP est le contexte calculé combiné avec les bits précédemment vus de l'octet actuel.

La section optionnelle PCOMP est utilisée pour le post-traitement des données décodées. Il s'exécute dans une machine virtuelle distincte comme celle de HCOMP. Cependant, contrairement aux sections COMP et HCOMP qui sont utilisées à la fois pour la compression et la décompression, la section PCOMP n'est exécutée que pendant la décompression. Le compresseur est chargé d'effectuer l'opération inverse sur les données d'entrée avant le codage.

comp 3 3 0 0 8 (hh hm ph pm n)
   0 icm 5      (order 0...5 chain)
   1 isse 13 0
   2 isse 17 1
   3 isse 18 2
   4 isse 18 3
   5 isse 19 4
   6 match 22 24  (order 7)
   7 mix 16 0 7 24 255  (order 1)
 hcomp
   c++ *c=a b=c a=0 (save in rotating buffer M)
   d= 1 hash *d=a   (orders 1...5 for isse)
   b-- d++ hash *d=a
   b-- d++ hash *d=a
   b-- d++ hash *d=a
   b-- d++ hash *d=a
   b-- d++ hash b-- hash *d=a (order 7 for match)
   d++ a=*c a<<= 8 *d=a       (order 1 for mix)
   halt
 end

 a = (a + *b + 512) * 773;

• 15 février 2009 - version expérimentale de zpaq 0.01.
• 12 mars 2009 - Finalisation de la spécification zpaq 1.00 garantissant la rétrocompatibilité.
• 29 septembre 2009 - zpaq 1.06, spécification mise à jour vers la v1.01, ajout de balises de localisation pour prendre en charge les archives auto-extractibles.
• 14 octobre 2009 - zpaq 1.09 ajoute ZPAQL au traducteur C++ pour optimiser la vitesse.
• 27 septembre 2010 - API libzpaq 0.01 séparée.
• 21 janvier 2011 - pzpaq 0.01, première version multithread, réincorporée plus tard dans zpaq.
• 13 novembre 2011 - zpaq 4.00, ajoute le compilateur JIT (ZPAQL à x86) éliminant le besoin d'un compilateur C++ externe pour l'optimisation.
• 1^er février 2012 - zpaq 5.00, spécification mise à jour vers la v2.00 pour autoriser une section COMP vide (post-traitement uniquement).
• 28 septembre 2012 - zpaq 6.00, spécification mise à jour vers v2.01 ajoutant le format de journalisation.
• 23 janvier 2013 - zpaq 6.19, divise les fonctions de développement en un programme distinct, zpaqd.

• Squash, une couche d'abstraction de compression prenant en charge de nombreux codecs .
• PeaZip, un archiveur prenant en charge plus de 150 formats, y compris l'extraction du format de streaming ZPAQ.
• fastqz, un compresseur FASTQ construit à l'aide de libzpaq[3].
• zpaqfranz, couteau suisse pour le gestionnaire sérieux de sauvegarde et de reprise après sinistre.
• wcx_zpaq, un plug-in packer (wcx) pour Total Commander[4].

• (en) Site officiel
• ZPAQ sur GitHub
• Intro to zpaql with grayscale images