ZPAQ

Files are saved in the ZPAQ level 2 journaling format.[2] The standard defines two formats - streaming and journaling. Only the journaling format supports deduplication, directory attributes, and multiple dated file versions.

The streaming archive format is designed to be extracted in a single pass. An archive is divided into a sequence of blocks that can be decompressed independently in parallel. Blocks are divided into segments that must be decompressed sequentially in order. Each block header contains a description of the decompression algorithm. Each segment has a header containing an optional file name and an optional comment for meta-data such as size, date, and attributes, and an optional trailing SHA-1 checksum of the original data for integrity checking. If the file name is omitted, it is assumed to be a continuation of the last named file, which may be in the previous block. Thus, inserting, removing, or reordering the blocks in a streaming archive has the effect of performing the same operations on the data that the blocks represent.

The journaling format consists of a sequence of transactions, or updates. An update contains 4 types of blocks: a transaction header block, a sequence of data blocks, a corresponding sequence of fragment tables, and a sequence of index blocks. A transaction header block contains the transaction date and a pointer skipping over the data blocks to allow the archive index to be read quickly. The data blocks contain a sequence of file fragments compressed together. The fragment tables give the size and SHA-1 hash of each fragment. The index blocks contain a list of edits to the global archive index. An edit is either a file update or a file deletion. An update includes a file name, last modified date, attributes, and a list of fragment pointers into the current and previous transactions. Fragments may be shared by more than one file. A deletion does not remove any data from the archive, but rather indicates that the file is not to be extracted unless the archive is rolled back to an earlier date.

The ZPAQ standard does not specify a compression algorithm. Rather, it specifies a format for representing the decompression algorithm in the block headers. Decompression algorithms are written in a language called ZPAQL and stored as a byte code which can either be interpreted or converted directly to 32 or 64 bit x86 code and executed. A ZPAQL program has 3 parts.

• COMP - An optional chain of context modeling components.
• HCOMP - Machine code for computing contexts for the COMP components.
• PCOMP - Optional machine code for post-processing the decoded data.

The COMP models are based on PAQ, which compresses one bit at a time using arithmetic coding. There are 9 types of components. Each component takes a context and possibly the predictions of earlier components, and outputs a prediction or probability that the next bit will be a 1. The output of the last component is arithmetic coded. The component types are:

• CONST - A fixed prediction.
• CM - Context model. The context is used to look up a prediction in a table. On update, the selected entry is adjusted to reduce the prediction error.
• ICM - Indirect context model. The context is used to look up an 8 bit state representing a recent bit history. The history selects a prediction as with a CM.
• MIX - A group of predictions are combined by weighted averaging in the logistic domain, or log(p/(1-p)). The weights are selected by a context. On update, the weights are adjusted to favor the more accurate inputs.
• MIX2 - A 2 input MIX with weights constrained to add to 1.
• AVG - A MIX2 with fixed weights.
• SSE - Secondary symbol estimator. Looks up a prediction from an interpolated table given a context and quantized prediction from another component.
• ISSE - Indirect secondary symbol estimator. The context selects a bit history as with an ICM, and then the bit history selects a pair of weights to mix the input with a constant 1.
• MATCH - Searches for the previous occurrence of the context and predicts whatever bit followed, with a strength depending on the length of the match.

The HCOMP section computes the contexts for the components in the COMP section. It is a virtual machine whose state is 4 32-bit registers (A, B, C, D), a 16 bit program counter, a condition flag bit, and two memory arrays, one of bytes (M) and one of 32 bit words (H). The beginning of H forms the array of contexts. An assembly language-like program is called once for each coded or decoded byte with that byte as input in A. The final context seen by the COMP section is the computed context combined with the previously seen bits of the current byte.

The optional PCOMP section is used for post-processing the decoded data. It runs in a separate virtual machine like that of HCOMP. However, unlike the COMP and HCOMP sections which are used for both compression and decompression, the PCOMP section is run only during decompression. The compressor is responsible for performing the inverse operation on the input data prior to coding.

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;

• Feb. 15, 2009 - zpaq 0.01 experimental release.
• Mar. 12, 2009 - zpaq 1.00 specification finalized guaranteeing backward compatibility.
• Sept. 29, 2009 - zpaq 1.06, specification updated to v1.01 add locator tags to support self extracting archives.
• Oct. 14, 2009 - zpaq 1.09 adds ZPAQL to C++ translator as a speed optimization.
• Sept. 27, 2010 - separate libzpaq 0.01 API.
• Jan. 21, 2011 - pzpaq 0.01, first multi-threaded version, later incorporated back into zpaq.
• Nov. 13, 2011 - zpaq 4.00, adds JIT compiler (ZPAQL to x86) eliminating need for external C++ compiler for optimization.
• Feb. 1, 2012 - zpaq 5.00, specification updated to v2.00 to allow empty COMP section (post-processing only).
• Sept. 28, 2012 - zpaq 6.00, specification updated to v2.01 adding journaling format.
• Jan. 23, 2013 - zpaq 6.19, splits development functions to a separate program, zpaqd.

• Squash, a compression abstraction layer supporting many codecs.
• PeaZip, an archiver supporting over 150 formats including ZPAQ streaming format extraction.
• fastqz, a FASTQ compressor built using libzpaq.[3]
• zpaqfranz, Swiss army knife for the serious backup and disaster recovery manager.
• wcx_zpaq, a packer plug-in (wcx) for Total Commander.[4]

• Official website
• zpaq on GitHub
• Intro to zpaql with grayscale images