ZPAQ
   HOME

TheInfoList



OR:

ZPAQ is an
open source Open source is source code that is made freely available for possible modification and redistribution. Products include permission to use the source code, design documents, or content of the product. The open-source model is a decentralized sof ...
command line A command-line interpreter or command-line processor uses a command-line interface (CLI) to receive commands from a user in the form of lines of text. This provides a means of setting parameters for the environment, invoking executables and pro ...
archiver An archive is an accumulation of historical records or materials – in any medium – or the physical facility in which they are located. Archives contain primary source documents that have accumulated over the course of an individual or ...
for
Windows Windows is a group of several proprietary graphical operating system families developed and marketed by Microsoft. Each family caters to a certain sector of the computing industry. For example, Windows NT for consumers, Windows Server for serv ...
and
Linux Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which ...
. 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 The term deduplication refers generally to eliminating duplicate or redundant information. *Data deduplication, in computer storage, refers to the elimination of redundant data *Record linkage Record linkage (also known as data matching, data l ...
and several algorithms (
LZ77 LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as LZ1 and LZ2 respectively. These two algorithms form the basis for many variations includin ...
, BWT, and
context mixing Context mixing is a type of data compression algorithm in which the next-symbol predictions of two or more statistical models are combined to yield a prediction that is often more accurate than any of the individual predictions. For example, one si ...
) 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 The public domain (PD) consists of all the creative work A creative work is a manifestation of creative effort including fine artwork (sculpture, paintings, drawing, sketching, performance art), dance, writing (literature), filmmaking, ...
API An application programming interface (API) is a way for two or more computer programs to communicate with each other. It is a type of software Interface (computing), interface, offering a service to other pieces of software. A document or standa ...
, libzpaq, which provides compression and decompression services to
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
applications. The format is believed to be unencumbered by
patent A patent is a type of intellectual property that gives its owner the legal right to exclude others from making, using, or selling an invention for a limited period of time in exchange for publishing an enabling disclosure of the invention."A p ...
s.


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 In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecima ...
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 PAQ is a series of lossless data compression archivers that have gone through collaborative development to top rankings on several benchmarks measuring compression ratio (although at the expense of speed and memory usage). Specialized versions ...
, which compresses one bit at a time using
arithmetic coding Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic e ...
. 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 In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
-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 (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 The COMP parameters describe the log base 2 sizes of the word and byte arrays (hh, hm), 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 = (a + *b + 512) * 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 The Rabin fingerprinting scheme is a method for implementing fingerprints using polynomials over a finite field. It was proposed by Michael O. Rabin. Scheme Given an ''n''-bit message ''m''0,...,''m''n-1, we view it as a polynomial of degree ''n''- ...
, ZPAQ uses a
rolling hash A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input. A few hash functions allow a rolling hash to be computed very quickly—the new hash value ...
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. 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 (opcodes E8 and E9 hex) 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 (16 KiB) 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.


Basic usage


Creating an archive, and updating an archive

zpaq add directory/archive.zpaq directory/source_directory -mX -key password The options -mX (with X being the compression level from 0 to 5) and -key (which performs
AES-256 The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001. AES is a variant ...
encryption) can be omitted. The 0 compression level does not compress data, but still carries out data deduplication. The compression levels 4 and 5 can be very time-consuming. The default (1) uses simple LZ77 compression.


Listing archive contents

zpaq list archive.zpaq lists the files and directories of the most recent version. Adding -all will list all versions of all files and directories, in the format version_number/directory/file_name. The output can be further processed with
grep grep is a command-line utility for searching plain-text data sets for lines that match a regular expression. Its name comes from the ed command ''g/re/p'' (''globally search for a regular expression and print matching lines''), which has the sam ...
and other tools.


Extracting files

zpaq extract archive.zpaq will un-pack the last version of the entire archive in the active directory. zpaq extract backup.zpaq path will only extract the specified directory (or file). Appending the -until N option selects the version, where negative numbers are allowed. -2 would extract the third most recent version of the archive. The optional -to tells ZPAQ where to save the extracted files. zpaq extract backup.zpaq -all -only "*muppet*" will extract all versions of all files and directories whose name contains "muppet". Different file versions will be placed in different directories (0001/ 0002/ 0003/ et cetera). -only is optional.


History

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


Related projects


Squash
a compression abstraction layer supporting many
codec A codec is a device or computer program that encodes or decodes a data stream or signal. ''Codec'' is a portmanteau of coder/decoder. In electronic communications, an endec is a device that acts as both an encoder and a decoder on a signal or da ...
s.
PeaZip
an archiver supporting over 150 formats including ZPAQ streaming format extraction.
fastqz
a
FASTQ FASTQ format is a text-based format for storing both a biological sequence (usually nucleotide sequence) and its corresponding quality scores. Both the sequence letter and quality score are each encoded with a single ASCII character for brevity. I ...
compressor built using libzpaq.
zpaqfranz
Swiss army knife for the serious backup and disaster recovery manager.

a packer plug-in (wcx) for Total Commander.


References


External links

* *

{{DEFAULTSORT:Zpaq Archive formats Free data compression software Open formats Lossless compression algorithms