ZPAQ

ZPAQ

Informations

Développé par	Matt Mahoney
Dernière version	7.15 (22 septembre 2016)
Dépôt	github.com/zpaq/zpaq
Écrit en	C++
Système d'exploitation	Type Unix
Formats lus	ZPAQ Archive (d)
Formats écrits	ZPAQ Archive (d)
Type	Logiciel de compression de données Archiveur de fichiers
Licence	MIT, Public domain
Site web	mattmahoney.net/dc/zpaq.html

ZPAQ est un archiveur de ligne de commande open source pour Windows et Linux. Il utilise un format de journalisation ou d'ajout uniquement qui peut être restauré à un état antérieur pour récupérer les anciennes versions des fichiers et des répertoires. Il prend en charge la mise à jour incrémentielle rapide en ajoutant uniquement les fichiers dont la date de dernière modification a changé depuis la mise à jour précédente. Il compresse à l'aide de la déduplication et de plusieurs algorithmes ( LZ77, BWT et mixage de contexte ) en fonction du type de données et du niveau de compression sélectionné. Pour préserver la compatibilité ascendante et descendante entre les versions à mesure que l'algorithme de compression est amélioré, il stocke l'algorithme de décompression dans l'archive. Le code source ZPAQ inclut une API de domaine public, libzpaq, qui fournit des services de compression et de décompression aux applications C++. Le format est considéré comme non protégé par des brevets.

Format d'archive

Les fichiers sont enregistrés au format de journalisation ZPAQ niveau 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.

Exemple ZPAQL

Le code source ZPAQL utilise une syntaxe textuelle, chaque mot délimité par des espaces s'assemblant sur un octet dans la plupart des cas, et les commentaires entre parenthèses. L'exemple suivant est la configuration intermédiaire, similaire à la compression de niveau 5. Il décrit une chaîne ICM-ISSE de composants prenant des contextes hachés d'ordres 0 à 5, un MATCH prenant un contexte d'ordre 7 et, comme étape finale, la moyenne de ces prédictions de bits à l'aide d'un MIX. Il n'y a pas de post-traitement.

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

Les paramètres COMP décrivent les tailles de base 2 du journal des tableaux de mots et d'octets (hh, hm), 8 octets chacun dans la section HCOMP et non utilisés dans la section PCOMP. Il y a n = 8 composants numérotés. Les composants prennent des paramètres décrivant leurs tailles de table et leurs entrées. En particulier, chaque ISSE prend son entrée du composant précédent, et le MIX prend l'entrée des 7 composants en commençant à 0. La ligne "5 isse 19 4" indique que l'ISSE a une taille de table de 2 historiques de ^{19 + 6} bits et prend son entrée du composant 4.

Dans la section HCOMP, les registres B et C pointent vers le tableau rotatif de 8 octets M, et D pointe vers le tableau de 8 mots H. M est utilisé pour stocker les 8 derniers octets d'entrée du registre A. C pointe vers la tête de ce tampon. L'instruction HASH calcule :

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

Ainsi, le code stocke des hachages de contexte de différents ordres dans H[0]. . . H[7].

Déduplication

Lors de la mise à jour, ZPAQ divise les fichiers d'entrée en fragments, calcule leurs hachages SHA-1 et les compare aux hachages stockés dans l'archive. S'il y a correspondance, les fragments sont supposés être identiques et seul un pointeur vers le fragment précédemment compressé est stocké. Sinon, le fragment est compressé dans un bloc pour être compressé. La taille des blocs peut aller jusqu'à 16 Mio à 64 Mio selon le niveau de compression.

Les fichiers sont divisés en fragments sur des limites dépendantes du contenu. Plutôt qu'une empreinte digitale Rabin, ZPAQ utilise un hachage roulant qui dépend des 32 derniers octets qui ne sont pas prédits par un contexte d'ordre 1, plus tous les octets prédits entre les deux. Si les 16 premiers bits du hachage de 32 bits sont tous 0, alors une limite de fragment est marquée. Cela donne une taille moyenne de fragment de 64 KiB.

Le hachage roulant utilise une table de 256 octets contenant le dernier octet vu dans chaque contexte d'ordre 1 possible. Le hachage est mis à jour en ajoutant l'octet suivant puis en le multipliant soit par une constante impaire si l'octet a été prédit, soit par un nombre pair qui n'est pas un multiple de 4 si l'octet n'a pas été prédit.

Compression

ZPAQ a 5 niveaux de compression, du plus rapide au meilleur. À tous les niveaux sauf au meilleur, il utilise les statistiques de la table de prédiction d'ordre 1 utilisée pour la déduplication pour tester si l'entrée semble aléatoire. Si tel est le cas, il est stocké sans compression en tant qu'optimisation de la vitesse.

ZPAQ utilisera une transformation E8E9 pour améliorer la compression du code x86 généralement présent dans les fichiers .exe et .dll. Une transformation E8E9 recherche les instructions CALL et JMP (opcodes E8 et E9 hex) et remplace leurs adresses relatives par des adresses absolues. Ensuite, il insère du code dans la section PCOMP pour effectuer la transformation inverse.

Récupération d'erreur

ZPAQ manque de correction d'erreur mais possède plusieurs fonctionnalités qui limitent les dommages si l'archive est corrompue. Lors de la décompression, tous les hachages SHA-1 sont vérifiés. Si le hachage ne correspond pas ou si une autre erreur se produit, un avertissement est imprimé et le bloc est ignoré. Les blocs commencent par une "balise de localisation" de 13 octets contenant une chaîne choisie au hasard mais fixe pour permettre au début du bloc suivant d'être trouvé par balayage. Si un fragment de données est perdu, tous les fichiers faisant référence à ce fragment et les fragments restants dans le bloc sont également perdus. Si une table de fragments est perdue, elle peut être récupérée à partir d'une liste redondante de tailles de fragments stockées dans le bloc de données correspondant et en recalculant les hachages. Dans ce cas, un deuxième hachage de l'ensemble du bloc de données est vérifié. Si un bloc d'index est perdu, les fichiers correspondants sont perdus. Les blocs d'index sont petits (16 ko) afin de limiter les dégâts.

Les mises à jour sont traitées en ajoutant un en-tête de transaction temporaire, puis en mettant à jour l'en-tête comme dernière étape. Si une mise à jour est interrompue, l'en-tête temporaire signale au ZPAQ qu'aucune donnée utile n'est trouvée après. La prochaine mise à jour écrasera ces données excédentaires.

Utilisation de base

Créer une archive et mettre à jour une archive

zpaq add directory/archive.zpaq directory/source_directory -mX -key password

Les options -mX (avec X étant le niveau de compression de 0 à 5) et -key (qui effectue le chiffrement AES-256 ) peuvent être omises. Le niveau de compression 0 ne compresse pas les données, mais exécute toujours la déduplication des données. Les niveaux de compression 4 et 5 peuvent être très chronophages. La valeur par défaut (1) utilise une simple compression LZ77.

Lister le contenu des archives

zpaq list archive.zpaq répertorie les fichiers et répertoires de la version la plus récente. L'ajout de -all listera toutes les versions de tous les fichiers et répertoires, au format version_number/directory/file_name . La sortie peut être traitée ultérieurement avec grep et d'autres outils.

Extraction des fichiers

zpaq extract archive.zpaq la dernière version de l'intégralité de l'archive dans le répertoire actif. zpaq extract backup.zpaq path que le répertoire (ou fichier) spécifié. L'ajout de l'option -until N sélectionne la version, où les nombres négatifs sont autorisés. -2 extraira la troisième version la plus récente de l'archive. L'option -to indique à ZPAQ où enregistrer les fichiers extraits.

zpaq extract backup.zpaq -all -only "*muppet*" extraira toutes les versions de tous les fichiers et répertoires dont le nom contient "muppet". Différentes versions de fichiers seront placées dans différents répertoires ( 0001/ 0002/ 0003/ et cetera). -only est facultatif.

Histoire

• 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.

Projets liés

• 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.
• 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.

Liens externes

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