ZPAQ


ZPAQ is an open source command line archiver for Windows and Linux. It uses a journaling or append-only format which can be rolled back to an earlier state to retrieve older versions of files and directories. It supports fast incremental update by adding only files whose last-modified date has changed since the previous update. It compresses using deduplication and several algorithms depending on the data type and the selected compression level. To preserve forward and backward compatibility between versions as the compression algorithm is improved, it stores the decompression algorithm in the archive. The ZPAQ source code includes a public domain API, libzpaq, which provides compression and decompression services to C++ applications. The format is believed to be unencumbered by patents.

Archive format

Files are saved in the ZPAQ level 2 journaling format. 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.
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:
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 16 bit program counter, a condition flag bit, and two memory arrays, one of bytes and one of 32 bit words. 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.

ZPAQL Example

ZPAQL source code uses a textual syntax, with each space-delimited word assembling to one byte in most cases, and comments in parenthesis. The following example is the mid configuration, similar to level 5 compression. It describes an ICM-ISSE chain of components taking hashed contexts of orders 0 through 5, a MATCH taking an order 7 context, and as a final step, averaging these bit predictions using a MIX. There is no post-processing.
comp 3 3 0 0 8
0 icm 5
1 isse 13 0
2 isse 17 1
3 isse 18 2
4 isse 18 3
5 isse 19 4
6 match 22 24
7 mix 16 0 7 24 255
hcomp
c++ *c=a b=c a=0
d= 1 hash *d=a
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
d++ a=*c a<<= 8 *d=a
halt
end
The COMP parameters describe the log base 2 sizes of the word and byte arrays, 8 bytes each in the HCOMP section and not used in the PCOMP section. There are n = 8 numbered components. The components take parameters describing their table sizes and inputs. In particular, each ISSE takes its input from the previous component, and the MIX takes input from the 7 components starting at 0. The line "5 isse 19 4" says that the ISSE has a table size of 219+6 bit histories and takes its input from component 4.
In the HCOMP section, registers B and C point into the 8 byte rotating array M, and D points to the 8 word array H. M is used to store the last 8 bytes of input from the A register. C points to the head of this buffer. The HASH instruction computes:
a = * 773;
Thus, the code stores context hashes of various orders in H...H.

Deduplication

On update, ZPAQ divides the input files into fragments, computes their SHA-1 hashes, and compares them to the hashes stored in the archive. If there is a match, then the fragments are assumed to be identical, and only a pointer to the previously compressed fragment is stored. Otherwise the fragment is packed into a block to be compressed. Block sizes can be up to 16 MiB to 64 MiB depending on the compression level.
Files are divided into fragments on content-dependent boundaries. Rather than a Rabin fingerprint, ZPAQ uses a rolling hash that depends on the last 32 bytes that are not predicted by an order 1 context, plus any predicted bytes in between. If the leading 16 bits of the 32 bit hash are all 0, then a fragment boundary is marked. This gives an average fragment size of 64 KiB.
The rolling hash uses a 256 byte table containing the byte last seen in each possible order-1 context. The hash is updated by adding the next byte and then multiplying either by an odd constant if the byte was predicted or by an even number that is not a multiple of 4 if the byte was not predicted.

Compression

ZPAQ has 5 compression levels, from fastest to best. At all but the best level, it uses the statistics of the order-1 prediction table used for deduplication to test whether the input appears random. If so, it is stored without compression as a speed optimization. Otherwise, it selects a compression algorithm as follows:
In addition, ZPAQ will use an E8E9 transform to improve the compression of x86 code typically found in.exe and.dll files. An E8E9 transform scans for CALL and JMP instructions and replaces their relative addresses with absolute addresses. Then it inserts code into the PCOMP section to perform the inverse transform.

Error recovery

ZPAQ lacks error correction but has several features that limit damage if the archive is corrupted. On decompression, all SHA-1 hashes are checked. If the hash does not match or if some other error occurs, then a warning is printed and the block is ignored. Blocks begin with a 13 byte "locator tag" containing a randomly chosen but fixed string to allow start of the next block to be found by scanning. If a data fragment is lost, then all of the files referencing that fragment and the remaining fragments in the block are also lost. If a fragment table is lost, then it can be recovered from a redundant list of fragment sizes stored in the corresponding data block and by recomputing the hashes. In this case, a second hash of the whole data block is checked. If an index block is lost, then the corresponding files are lost. Index blocks are small in order to limit damage.
Updates are transacted by appending a temporary transaction header and then updating the header as the last step. If an update is interrupted, then the temporary header signals ZPAQ that no useful data is found after it. The next update will overwrite this excess data.

History