====
zpaq
====

Journaling incremental deduplicating archiver
---------------------------------------------


Synopsis
========

::

	zpaq <archive.zpaq> [file|dir to be compressed]... -options...


Availability
============

zpaq is designed for use in Windows and Linux

Description
===========

zpaq is for creating journaling compressed archives for incremental
backups of files and directory trees. Incremental update of an entire
disk is fast because only those files whose last-modified date has
changed are added.

zpaq is journaling, which means that the archive is (mostly) append-only,
and both the old and new versions are saved. You can extract the old
versions by rolling back the archive to an earlier version.

zpaq deduplicates: it saves identical files or file fragments only once
by comparing SHA-1 hashes to those stored in the archive.

zpaq compresses in the open-standard ZPAQ level 2 (v2.01) format
specified at http://mattmahoney.net/zpaq/
The format is self describing, meaning that new versions of the
archiver that improve compression will still produce archives that
older decompressers can read, because the decompression instructions
are stored in the archive.

Commands
========

a or -add
	Add files and directory trees to the archive. Directories are scanned
	recursively to add subdirectories and their contents. Only ordinary
	files and directories are added, not special types (devices, symbolic
	links, etc). Symbolic links are not followed. File names and directories
	may be specified with absolute or relative paths or no paths, and will
	be saved that way. The last-modified date is saved, rounded to the nearest
	second. Windows attributes or Linux permissions are saved. However,
	additional metadata such as owner, group, extended attributes (xattrs,
	ACLs, alternate streams) are not saved.

	Before adding files, the last-modifed date is compared with the
	date stored in the archive. Files are added only if the dates
	differ or if the file is not already in the archive, or if -force
	is specified.

	When a file is changed, both the old and new versions are saved to
	the archive. When a directory is added, any files that existed in
	the old version of the directory but not the new version are marked
	as deleted in the current version but remain in the archive.

x or -extract
	Extract files and directores (default: all) from the archive.
	Files will be extracted by creating filenames as saved in the archive.
	If any of the external files already exist then zpaq will exit with
	an error and not extract any files unless -force is given to allow
	files to be overwritten. Last-modified dates and attributes will be
	restored as saved. Attributes saved in Windows will not be restored
	in Linux and vice versa. If there are multiple versions of a file
	saved, then the latest version will be extracted unless an earlier
	version is specified with -version.


l or -list
	List the archive contents. Each file or directory is shown with a
	version number, date, attributes, uncompressed size, and file name.
	There may be multiple versions of a single file with different
	version numbers. A second table lists for each version number the
	date of the update, number of files added and deleted, and the number
	of MB added before and after compression. Attributes are shown as
	a string of characters like "DASHRI" in Windows (directory, archive,
	system, hidden, read-only, indexed), or an octal number like "100644"
	(as passed to chmod(), meaning rw-r--r--) in Linux.


d or -delete
	Mark files and directories in the archive as deleted. This actually
	makes the archive slightly larger. The files can still be extracted
	by rolling back to an earlier version using -until.


Options
=======

-not <file|dir>...
	Exclude files and directories (before renaming) from being added,
	extracted, or listed. For example "zpaq a arc calgary -not calgary/book1"
	will add all the files in calgary except book1.

-to <file|dir>...
	Rename extracted files and directories. Each argument to -to is matched
	to an argument to -add or -extract in the same order. For example,
	"zpaq x arc calgary -to out" extracts calgary/book2 to out/book2, etc.
	"zpaq a arc newfile -to file" saves the name of file as newfile.

-until N | -until YYYYMMDD[HH[MM[SS]]]
	Roll back the archive to an earlier version. With -list and -extract,
	versions later than N will be ignored. With -add, the archive
	will be truncated at N, discarding any subsquently added contents
	before updating. The version can also be specified as a date and time
	(UCT time zone) as an 8, 10, 12, or 14 digit number in the range
	19000101 to 29991231235959 with the last 6 digits defaulting to 235959.
	The default is the latest version. For backward compatibility, -version
	is equivalent to -until.

-force
	Add files even if the dates match. If a file really is identical,
	then it will not be added. When extracting, output files will be
	overwritten.

-quiet
	Display only errors and warnings. When adding or extracting,
	don't print anything unless there is an error.

-threads N
	Set the number of threads to N for parallel compression and decompression.
	The default is to detect the number of processor cores and use that value
	or the limit according to -method, whichever is less. The number of cores
	is detected from the environment variable %NUMBER_OF_PROCESSORS% in
	Windows or /proc/cpuinfo in Linux.

-method 0...4
	Select compression method, where M is a digit, possibly followed by
	a list of arguments. Each argument consists of a single letter C
	followed by a list of 0 or more non-negative integers separated by
	commas or periods with no spaces. The default is "1". The meanings are
	as follows:

	M ranges from 0 to 9. Higher numbers compress better but are slower
	and require more memory. M selects the base algorithm and block size
	as follows:

	  0 = No compression.
	  1 = LZ77 with variable length codes and no context modeling.
	  2 = LZ77 with byte aligned codes and a context model.
	  3 = BWT (Burrows-Wheeler transform).
	  4..9 = CM (Context mixing).

	The block size is 16 MB for M=0..4 and 2^M MB for M=4..9.

	No other arguments are required. If omitted, then the compression algorithm
	will be selected based on an analysis of the input data and may vary from
	block to block. Otherwise, any arguments override the analysis and exactly
	specify the compression algorithm for all blocks. The arguments are as
	follows:

	  n - No further preprocessing.
	  e - E8E8 preprocessing (M=1..9 only).

	The E8E9 preprocessor replaces input sequences of the form
	(E8|E9 xx xx xx 00|FF) by adding the sequence offset from the
	start of the block to the 3 middle bytes (LSB first), mod 2^24. This
	improves compression of x86 code (.exe and .dll files).

	Additional options apply to M=3..9 only.

	  c - Context model (CM or ICM).
	  i - ISSE chain.
	  a - MATCH.
	  m - MIX.
	  t - MIX2.
	  s - SSE
	  w - Word model ISSE chain.

	Memory usage per component is generally limited to the block size, but
	may be less for small contexts. The numeric arguments to each model
	are as follows:

	  c

	N1 is 0 for an ICM and 1..256 to specify a CM with limit argument N1-1.
	Higher values are better for stationary sources. Default is 0.

	N2 in 1..255 includes (offset mod N2) in the context hash. N2 in 1000..1255
	includes the distance to the last occurrence of N2-1000 in the context
	hash. The default is 0 which includes neither of these contexts.

	N3,... in 0..255 specifies a list of byte context masks reading back from
	the most recently coded byte. Each mask is ANDed with the context byte
	before hashing. a value of 1000 or more is equivalent to a sequence
	of N-1000 zeros. Only the last 65536 bytes of context are saved.

	  i

	ISSE chain. Each ISSE takes a prediction from the previous component
	as input. There must be a previous component. The arguments N,...
	specify an increase of N in the context order from previous component's
	context, which is hashed together with the most recently coded bytes.

	  a

	Specifies a MATCH. The context hash is computed as hash := hash*N1+c+1
	where c is the most recently coded byte. The range of N1 is 0..255 and
	the default is 24, which gives an order 8 context for a block size
	of 2^24. N2 and N3 specify how many times to halve the memory usage
	of the buffer and hash table, respectively. The default for each is
	the block size.

	  m

	Specifies a MIX. The input is all previous components. N1 is the context
	size in bits. The context is not hashed. If N1 is not a multiple of 8
	then the low bits of the oldest byte are discarded. The default is 8.
	N2 specifies the update rate. The default is 24.

	  t

	Specifies a MIX2. The input is the previous 2 components. N1 and N2
	are the same as MIX.

	  s

	Specifies an SSE. The input is the previous component. N1 is the context
	size in bits as in a MIX or MIX2. N2 and N3 are the start and limit
	arguments. The default is 8,32,255.

	  w

	Word-model ICM-ISSE chain for modeling text. N1 is the length of the
	chain, with word-level context orders of 0..N1-1. A word is defined
	as a sequence of characters in the range N2..N2+N3-1 after ANDing
	with N4. The default is 1,65,26,223, representing the set [A-Za-z].

	  -method config.cfg

	If the argument to -method does not start with a digit, then use the
	ZPAQL model in the file config.cfg. ZPAQL is described in libzpaq.h.
	Pre-processing (PCOMP section) is not supported. Numeric arguments
	($1..$9) are not supported and default to 0. Filename extension .cfg
	will be appended if not present.

	  -summary N

	When listing contents, show only the top N files, directories, and
	filename extensions by total size. The default is 20. Also show
	a table of deduplication statistics and a table of version dates.

	  -since N

	List only versions N and later. If N is negative then list only the
	last -N updates. Default is 0 (all).

	  -above N

	List only files at least N bytes in size. Default is -1 (all including
	unknown sizes).

list options
============

-summary [N]
	Show top N files and types (default: 20)

-since N
	List from N'th update or last -N updates

-above N
	List files N bytes or larger


NOTES
=====

The archive file name must end with ".zpaq" or the extension will be
assumed. Directory names should be written without a trailing slash.
Commands a, x, l can be written as -add, -extract, or -list respectively
for backward compatibility. Options can be abbreviated as long as it is
not ambiguous, like -th or -thr (but not -t) for -threads.
It is recommended that if zpaq is run from a script that abbreviations
not be used because future versions might add options that would make
existing abbreviations ambiguous.

For all commands, file names and directories may be specified with
wildcards. A * matches any string of length 0 or more up to the
next slash. A ? matches exactly one character. In Linux, names with
wildcards must be quoted to protect them from the shell. In Windows,
the forward (/) and back (\) slash are equivalent and stored as (/).
When adding directories, a trailing slash like c:\ is eqivalent
to all of the files in that directory but not the directory itself,
as in c:\*

ARCHIVE FORMAT
==============

Data is compressed in the journaling format described in section 8
of http://mattmahoney.net/dc/zpaq201.pdf
However, zpaq can extract any conforming archive including streaming
format. All blocks include locator tags, file names, comments, and
SHA-1 hashes, although they are not required to extract.

The c (version header), and h (hash table) blocks are stored with
method 0. The i blocks (index) are split into blocks of about 16 KB
(to reduce losses in case of archive damage) and compressed with method 1.
The d (data) blocks are compressed depending on the selected method.

Updates are transacted by writing -1 for the value of csize in the c block,
then appending the other blocks, and finally committing the update by
rewriting csize with the total size of the d blocks. If an error occurs
during update or if it is interrupted, then the -1 signals the end of
valid data in the archive. The next update will overwrite this block and
all subsequent data.

For deduplication, files are fragmented by a rolling hash that depends
on the last 32 bytes that are not predicted by an order-1 context and
selected with probability 2^-16, with a minimum size of 4096 or EOF,
whichever is first, and a maximum size of 520192 bytes. The hash is
initially 0 and updated for each byte c:

  hash := (hash + c + 1) * 314159265 (mod 2^32)  if c is predicted,
  hash := (hash + c + 1) * 271828182 (mod 2^32)  if c is not predicted.

and a boundary occurs after byte c if hash < 65536. c is predicted
if the previous occurrence of the byte before c is also followed by c
(or 0 if the context appears for the first time in the fragment).
If the SHA-1 hash of the fragment matches one already compressed,
then the fragments are assumed to be identical and stored only once.

The number of predicted and mispredicted bytes in each block are counted.
For methods 1 through 4, if the fraction of predicted bytes is less
than 1/16, 1/32, 1/64, 1/128 respectively, then the block is assumed
to be not compressible and is stored as with method 0. Methods 5 through 9
always compress.

Files are sorted by filename extension (like ".exe", ".html", ".jpg")
and then lexicographically by name. Non-matching fragments are packed into
blocks of about 16 MB and compressed in parallel by separate threads
and appended to the archive. Blocks are packaged into a transacted update
consisting of a temporary header, compressed blocks, and compressed
index listing fragment hashes and sizes and a list of added and deleted
files. For each added file, the date, attributes, and list of fragment
indexes is stored.

Each transaction header stores the date of the update and compressed data
size. The size is temporarily set to an invalid value (-1) and updated as the
last step. If -add encounters an error or is interrupted by the
user with Ctrl-C, resulting in an invalid header followed by corrupted
data, then zpaq will interpret the invalid value as the end of the
archive. It will ignore anything that follows, and the next -add command
will overwrite it.

Method 0 deduplicates file fragments but does not otherwise compress.
Methods 1e through 9e preprocess the input block with a E8E9 transform
before compression, while 1n through 9n do not.

Method 1 is LZ77 using variable length bit codes without context
modeling. Literals are coded as 2 bits 00, followed by the literal
length as an interleaved Elias Gamma code, followed by the uncompressed
literals. An n-bit binary number is coded in 2n-1 bits by dropping the
leading 1, putting a 1 in front of all other bits, and appending a 0,
e.g. abcd -> 1,b,1,c,1,d,0.

A match with an m-bit offset and n-bit length is coded by giving
the length of m (01000..11111 -> 0..23), then 2n-3 interleaved bits
for the length (4 or more, with the last 2 bits coded directly), and m
bits of the offset (1..16777215).

Matches are found by indexing a hash of the next 4 bytes in the
input buffer into a table of size 4M which is grouped into 512K
buckets of 8 pointers each. The longest match is coded, provided
the length is at least 4, or 5 if the offset > 64K and the last
output was a literal. Ties are broken by favoring the smaller offset.
Bucket elements are selected for replacement using the low 3 bits
of the output count.

Method 2 is also LZ77, but the codes are byte aligned and context
modeled rather than coded directly. It also searches 4 order-7
context hashes and 4 order-4 hashes, rather than 8 order-4 hashes
like method 1. Method 2 first codes as follows, according to the
high 2 bits of the first byte:

  00 = literal of length 1..64, followed by uncompressed bytes.
  01 = match of length 4..11 and offset 1..2048.
  10 = match of length 1..64 and offset of 1..65536.
  11 = match of length 1..64 and offset of 1..16777216.

AUTHOR
======

	Matt Mahoney <mattmahoneyfl@gmail.com>

LICENSE
=======

	Copyright (C) 2013, Dell Inc. Written by Matt Mahoney.

	This program is free software; you can redistribute it and/or
	modify it under the terms of the GNU General Public License as
	published by the Free Software Foundation; either version 3 of
	the License, or (at your option) any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
	General Public License for more details at
	Visit <http://www.gnu.org/copyleft/gpl.html>.

SEE ALSO
========

	All versions of this software can be found at
	http://mattmahoney.net/dc/zpaq.html
