Buckets:
| - Warning: parts of this document are obsolete or incomplete - | |
| ---------------- | |
| PAQ8PX INTERNALS | |
| ---------------- | |
| ARITHMETIC CODING | |
| The binary data is arithmetic coded as the shortest base 256 fixed point | |
| number x = SUM_i x_i 256^-1-i such that p(<y) <= x < p(<=y), where y is the | |
| input string, x_i is the i'th coded byte, p(<y) (and p(<=y)) means the | |
| probability that a string is lexicographically less than (less than | |
| or equal to) y according to the model, _ denotes subscript, and ^ denotes | |
| exponentiation. | |
| The model p(y) for y is a conditional bit stream, | |
| p(y) = PROD_j p(y_j | y_0..j-1) where y_0..j-1 denotes the first j | |
| bits of y, and y_j is the next bit. Compression depends almost entirely | |
| on the ability to predict the next bit accurately. | |
| MODEL MIXING | |
| paq8px uses a neural network to combine a large number of models. The | |
| i'th model independently predicts | |
| p1_i = p(y_j = 1 | y_0..j-1), p0_i = 1 - p1_i. | |
| The network computes the next bit probability | |
| p1 = squash(SUM_i w_i t_i), p0 = 1 - p1 (1) | |
| where t_i = stretch(p1_i) is the i'th input, p1_i is the prediction of | |
| the i'th model, p1 is the output prediction, stretch(p) = ln(p/(1-p)), | |
| and squash(s) = 1/(1+exp(-s)). Note that squash() and stretch() are | |
| inverses of each other. | |
| After bit y_j (0 or 1) is received, the network is trained: | |
| w_i := w_i + eta t_i (y_j - p1) (2) | |
| where eta is an ad-hoc learning rate, t_i is the i'th input, (y_j - p1) | |
| is the prediction error for the j'th input but, and w_i is the i'th | |
| weight. Note that this differs from back propagation: | |
| w_i := w_i + eta t_i (y_j - p1) p0 p1 (3) | |
| which is a gradient descent in weight space to minimize root mean square | |
| error. Rather, the goal in compression is to minimize coding cost, | |
| which is -log(p0) if y = 1 or -log(p1) if y = 0. Taking | |
| the partial derivative of cost with respect to w_i yields (2). | |
| MODELS | |
| Most models are context models. A function of the context (last few | |
| bytes) is mapped by a lookup table or hash table to a state which depends | |
| on the bit history (prior sequence of 0 and 1 bits seen in this context). | |
| The bit history is then mapped to p1_i by a fixed or adaptive function. | |
| There are several types of bit history states: | |
| - Run Map. The state is (b,n) where b is the last bit seen (0 or 1) and | |
| n is the number of consecutive times this value was seen. The initial | |
| state is (0,0). The output is computed directly: | |
| t_i = (2b - 1)K log(n + 1). | |
| where K is ad-hoc, around 4 to 10. When bit y_j is seen, the state | |
| is updated: | |
| (b,n) := (b,n+1) if y_j = b, else (y_j,1). | |
| - Stationary Map. The state is p, initially 1/2. The output is | |
| t_i = stretch(p). The state is updated at ad-hoc rate K (around 0.01): | |
| p := p + K(y_j - p) | |
| - Nonstationary Map. This is a compromise between a stationary map, which | |
| assumes uniform statistics, and a run map, which adapts quickly by | |
| discarding old statistics. An 8 bit state represents (n0,n1,h), initially | |
| (0,0,0) where: | |
| n0 is the number of 0 bits seen "recently". | |
| n1 is the number of 1 bits seen "recently". | |
| n = n0 + n1. | |
| h is the full bit history for 0 <= n <= 4, | |
| the last bit seen (0 or 1) if 5 <= n <= 15, | |
| 0 for n >= 16. | |
| The primary output is t_i := stretch(sm(n0,n1,h)), where sm(.) is | |
| a stationary map with K = 1/256, initialized to | |
| sm(n0,n1,h) = (n1+(1/64))/(n+2/64). Four additional inputs are also | |
| be computed to improve compression slightly: | |
| p1_i = sm(n0,n1,h) | |
| p0_i = 1 - p1_i | |
| t_i := stretch(p_1) | |
| t_i+1 := K1 (p1_i - p0_i) | |
| t_i+2 := K2 stretch(p1) if n0 = 0, -K2 stretch(p1) if n1 = 0, else 0 | |
| t_i+3 := K3 (-p0_i if n1 = 0, p1_i if n0 = 0, else 0) | |
| t_i+4 := K3 (-p0_i if n0 = 0, p1_i if n1 = 0, else 0) | |
| where K1..K4 are ad-hoc constants. | |
| h is updated as follows: | |
| If n < 4, append y_j to h. | |
| Else if n <= 16, set h := y_j. | |
| Else h = 0. | |
| The update rule is biased toward newer data in a way that allows | |
| n0 or n1, but not both, to grow large by discarding counts of the | |
| opposite bit. Large counts are incremented probabilistically. | |
| Specifically, when y_j = 0 then the update rule is: | |
| n0 := n0 + 1, n < 29 | |
| n0 + 1 with probability 2^(27-n0)/2 else n0, 29 <= n0 < 41 | |
| n0, n = 41. | |
| n1 := n1, n1 <= 5 | |
| round(8/3 lg n1), if n1 > 5 | |
| swapping (n0,n1) when y_j = 1. | |
| Furthermore, to allow an 8 bit representation for (n0,n1,h), states | |
| exceeding the following values of n0 or n1 are replaced with the | |
| state with the closest ratio n0:n1 obtained by decrementing the | |
| smaller count: (41,0,h), (40,1,h), (12,2,h), (5,3,h), (4,4,h), | |
| (3,5,h), (2,12,h), (1,40,h), (0,41,h). For example: | |
| (12,2,1) 0-> (7,1,0) because there is no state (13,2,0). | |
| - Match Model. The state is (c,b), initially (0,0), where c is 1 if | |
| the context was previously seen, else 0, and b is the next bit in | |
| this context. The prediction is: | |
| t_i := (2b - 1)Kc log(m + 1) | |
| where m is the length of the context. The update rule is c := 1, | |
| b := y_j. A match model can be implemented efficiently by storing | |
| input in a buffer and storing pointers into the buffer into a hash | |
| table indexed by context. Then c is indicated by a hash table entry | |
| and b can be retrieved from the buffer. | |
| CONTEXTS | |
| High compression is achieved by combining a large number of contexts. | |
| Most (not all) contexts start on a byte boundary and end on the bit | |
| immediately preceding the predicted bit. The contexts below are | |
| modeled with both a run map and a nonstationary map unless indicated. | |
| - Order n. The last n bytes, up to about 16. For general purpose data. | |
| Most of the compression occurs here for orders up to about 6. | |
| An order 0 context includes only the 0-7 bits of the partially coded | |
| byte and the number of these bits (255 possible values). | |
| - Sparse. Usually 1 or 2 of the last 8 bytes preceding the byte containing | |
| the predicted bit, e.g (2), (3),..., (8), (1,3), (1,4), (1,5), (1,6), | |
| (2,3), (2,4), (3,6), (4,8). The ordinary order 1 and 2 context, (1) | |
| or (1,2) are included above. Useful for binary data. | |
| - Text. Contexts consists of whole words (a-z, converted to lower case | |
| and skipping other values). Contexts may be sparse, e.g (0,2) meaning | |
| the current (partially coded) word and the second word preceding the | |
| current one. Useful contexts are (0), (0,1), (0,1,2), (0,2), (0,3), | |
| (0,4). The preceding byte may or may not be included as context in the | |
| current word. | |
| - Formatted text. The column number (determined by the position of | |
| the last linefeed) is combined with other contexts: the character to | |
| the left and the character above it. | |
| - Fixed record length. The record length is determined by searching for | |
| byte sequences with a uniform stride length. Once this is found, then | |
| the record length is combined with the context of the bytes immediately | |
| preceding it and the corresponding byte locations in the previous | |
| one or two records (as with formatted text). | |
| - Context gap. The distance to the previous occurrence of the order 1 | |
| or order 2 context is combined with other low order (1-2) contexts. | |
| - FAX. For 2-level bitmapped images. Contexts are the surrounding | |
| pixels already seen. Image width is assumed to be 1728 bits (as | |
| in calgary/pic). | |
| - Image. For uncompressed 24-bit color BMP, TIFF and TGA images. Contexts | |
| are the high order bits of the surrounding pixels and linear | |
| combinations of those pixels, including other color planes. The | |
| image width is detected from the file header. When an image is | |
| detected, other models are turned off to improve speed. | |
| - JPEG. Files are further compressed by partially uncompressing back | |
| to the DCT coefficients to provide context for the next Huffman code. | |
| Only baseline DCT-Huffman coded files are modeled. (This ia about | |
| 90% of images, the others are usually progressive coded). JPEG images | |
| embedded in other files (quite common) are detected by headers. The | |
| baseline JPEG coding process is: | |
| - Convert to grayscale and 2 chroma colorspace. | |
| - Sometimes downsample the chroma images 2:1 or 4:1 in X and/or Y. | |
| - Divide each of the 3 images into 8x8 blocks. | |
| - Convert using 2-d discrete cosine transform (DCT) to 64 12-bit signed | |
| coefficients. | |
| - Quantize the coefficients by integer division (lossy). | |
| - Split the image into horizontal slices coded independently, separated | |
| by restart codes. | |
| - Scan each block starting with the DC (0,0) coefficient in zigzag order | |
| to the (7,7) coefficient, interleaving the 3 color components in | |
| order to scan the whole image left to right starting at the top. | |
| - Subtract the previous DC component from the current in each color. | |
| - Code the coefficients using RS codes, where R is a run of R zeros (0-15) | |
| and s indicates 0-11 bits of a signed value to follow. (There is a | |
| special RS code (EOB) to indicate the rest of the 64 coefficients are 0). | |
| - Huffman code the RS symbol, followed by s literal bits. | |
| The most useful contexts are the current partially coded Huffman code | |
| (including s following bits) combined with the coefficient position | |
| (0-63), color (0-2), and last few RS codes. | |
| - Match. When a context match of 400 bytes or longer is detected, | |
| the next bit of the match is predicted and other models are turned | |
| off to improve speed. | |
| - Exe. When a x86 file (.exe, .obj, .dll) is detected, sparse contexts | |
| with gaps of 1-12 selecting only the prefix, opcode, and the bits | |
| of the modR/m byte that are relevant to parsing are selected. | |
| This model is turned off otherwise. | |
| - Indirect. The history of the last 1-3 bytes in the context of the | |
| last 1-2 bytes is combined with this 1-2 byte context. | |
| - DMC. A bitwise n-th order context is built from a state machine using | |
| DMC, described in http://plg.uwaterloo.ca/~ftp/dmc/dmc.c | |
| The effect is to extend a single context, one bit at a time and predict | |
| the next bit based on the history in this context. The model here differs | |
| in that two predictors are used. One is a pair of counts as in the original | |
| DMC. The second predictor is a bit history state mapped adaptively to | |
| a probability as as in a Nonstationary Map. | |
| ARCHITECTURE | |
| The context models are mixed by several of several hundred neural networks | |
| selected by a low-order context. The outputs of these networks are | |
| combined using a second neural network, then fed through several stages of | |
| adaptive probability maps (APM) before arithmetic coding. | |
| For images, only one neural network is used and its context is fixed. | |
| An APM is a stationary map combining a context and an input probability. | |
| The input probability is stretched and divided into 32 segments to | |
| combine with other contexts. The output is interpolated between two | |
| adjacent quantized values of stretch(p1). There are 2 APM stages in series: | |
| p1 := (p1 + 3 APM(order 0, p1)) / 4. | |
| p1 := (APM(order 1, p1) + 2 APM(order 2, p1) + APM(order 3, p1)) / 4. | |
| PREPROCESSING | |
| paq8px uses preprocessing transforms on certain data types to improve | |
| compression. To improve reliability, the decoding transform is | |
| tested during compression to ensure that the input file can be | |
| restored. If the decoder output is not identical to the input file | |
| due to a bug, then the transform is abandoned and the data is compressed | |
| without a transform so that it will still decompress correctly. | |
| The input is split into blocks with the format <type> <decoded size> <data> | |
| where <type> is 1 byte (0 = no transform), <decoded size> is the size | |
| of the data after decoding, which may be different than the size of <data>. | |
| Blocks do not span file boundaries, and have a maximum size of 4MB to | |
| 2GB depending on compression level. Large files are split into blocks | |
| of this size. The preprocessor has 3 parts: | |
| - Detector. Splits the input into smaller blocks depending on data type. | |
| - Coder. Input is a block to be compressed. Output is a temporary | |
| file. The coder determines whether a transform is to be applied | |
| based on file type, and if so, which one. A coder may use lots | |
| of resources (memory, time) and make multiple passes through the | |
| input file. The file type is stored (as one byte) during compression. | |
| - Decoder. Performs the inverse transform of the coder. It uses few | |
| resources (fast, low memory) and runs in a single pass (stream oriented). | |
| It takes input either from a file or the arithmetic decoder. Each call | |
| to the decoder returns a single decoded byte. | |
| The following transforms are used: | |
| - EXE: CALL (0xE8) and JMP (0xE9) address operands are converted from | |
| relative to absolute address. The transform is to replace the sequence | |
| E8/E9 xx xx xx 00/FF by adding file offset modulo 2^25 (signed range, | |
| little-endian format). Data to transform is identified by trying the | |
| transform and applying a crude compression test: testing whether the | |
| byte following the E8/E8 (LSB of the address) occurred more recently | |
| in the transformed data than the original and within 4KB 4 times in | |
| a row. The block ends when this does not happen for 4KB. | |
| - JPEG: detected by SOI and SOF and ending with EOI or any nondecodable | |
| data. No transform is applied. The purpose is to separate images | |
| embedded in executables to block the EXE transform, and for a future | |
| place to insert a transform. | |
| IMPLEMENTATION | |
| Hash tables are designed to minimize cache misses, which consume most | |
| of the CPU time. | |
| Most of the memory is used by the nonstationary context models. | |
| Contexts are represented by 32 bits, possibly a hash. These are | |
| mapped to a bit history, represented by 1 byte. The hash table is | |
| organized into 64-byte buckets on cache line boundaries. Each bucket | |
| contains 7 x 7 bit histories, 7 16-bit checksums, and a 2 element LRU | |
| queue packed into one byte. Each 7 byte element represents 7 histories | |
| for a context ending on a 3-bit boundary plus 0-2 more bits. One | |
| element (for bits 0-1, which have 4 unused bytes) also contains a run model | |
| consisting of the last byte seen and a count (as 1 byte each). | |
| Run models use 4 byte hash elements consisting of a 2 byte checksum, a | |
| repeat count (0-255) and the byte value. The count also serves as | |
| a priority. | |
| Stationary models are most appropriate for small contexts, so the | |
| context is used as a direct table lookup without hashing. | |
| The match model maintains a pointer to the last match until a mismatching | |
| bit is found. At the start of the next byte, the hash table is referenced | |
| to find another match. The hash table of pointers is updated after each | |
| whole byte. There is no checksum. Collisions are detected by comparing | |
| the current and matched context in a rotating buffer. | |
Xet Storage Details
- Size:
- 14.7 kB
- Xet hash:
- 72fa1377c4d757d52c5f3a2ee923dfb4fed961e60bb19e7ea4efce1874608a39
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.