.7Z File Format – Codec algorithms

Copy, Delta and Swap

Copy (00) passes its input through.

Delta (03) has one property byte, distance − 1. Each output byte is the input byte plus the output byte distance places earlier (modulo 256); the first distance bytes are added to zero. It helps data made of samples or pixels, because the encoder subtracted each byte from the one distance bytes before it.

Swap2 (02 03 02) and Swap4 (02 03 04) reverse the byte order of every 2-byte or 4-byte word. They are their own inverse. A last partial word, shorter than the width, is left alone. They have no properties.

Branch filters (BCJ)

Machine code calls and jumps to places with relative addresses, so the same call to the same function has a different operand at every call site, and a compressor finds no repeats. The filter converts the operand of each call to an absolute address before compression; the decoder converts it back by subtracting the position of the instruction. Everything else passes unchanged. Each filter looks for one instruction pattern at the alignment of its architecture; bytes at the end of the data too few to hold a whole instruction stay as they are. The conversion is done on the whole unpacked stream, from position 0: a start address can be given as an optional 4-byte property for ARM64 and RISC-V (a multiple of 4 and of 2).

The ARM64 and RISC-V filters are the same as the filters of that name in the .xz format (xz 5.4 and 5.8 define them as filter IDs 0A and 0B), and 7-Zip and xz share the other filters’ behaviour: the xz decoder on this site unpacks the data of a 7z folder with any of them identically.

BCJ2

BCJ2 (03 03 01 1B) is the x86 filter of 7-Zip with four streams instead of one. A call to a faraway place is a poor candidate for conversion, and one converted wrongly makes the compressed data larger, so BCJ2 does not convert blindly: it separates the code from the addresses and records for each call whether it was taken out. The coder has four input streams and one output, in this order:

Decoding: copy bytes from MAIN to the output one at a time. After a byte E8, E9, or a byte 8x that follows 0F, decode one bit with the range decoder below. Bit 0: carry on copying. Bit 1: take 4 bytes from CALL (after E8) or JUMP (otherwise), read them big-endian, subtract the output position after those four bytes (a count that includes the bytes already put out and the 4 about to be), and write the result as 4 little-endian bytes. The byte before the next opcode check is the last byte written. The probability of a bit is kept in a model chosen by the opcode: one for 0F 8x, one for E9, and 256 for E8, picked by the byte in front of the E8.

The range decoder is binary and adaptive, as in LZMA: 11-bit probabilities starting at 1024, a shift of 5 on updates, a 32-bit range that is refilled a byte at a time when it falls below 2²⁴. The RC stream starts with a byte that must be 0, then four bytes that start the code value (which must not be FFFFFFFF). In a 7z folder the coder’s four inputs are usually fed by LZMA coders on MAIN, CALL and JUMP with the RC stream stored plain, joined with three bind pairs, which makes a folder with four packed streams.

Deflate64

Deflate64 (04 01 09), also ZIP’s method 9, is Deflate with three changes: the window is 64 KiB, so distances reach 65,536; distance codes 30 and 31 exist (bases 32,769 and 49,153, each with 14 extra bits); and length code 285 means a length of 3 to 65,538 (base 3, 16 extra bits) instead of 258. Everything else, the three block types, the Huffman code lengths and the bit order, is as in RFC 1951.

PPMd variant H

PPMd (03 04 01) predicts each byte from the bytes before it. It keeps a tree of contexts, each the last n bytes seen; a context holds the symbols that have followed it and how often. To code a byte it starts in the longest context that matches the data so far and codes the byte there, or, if the byte has not followed that context, codes an escape and falls back to the next shorter context (the symbols the longer one rules out are excluded from the count), as far as order 0, which holds every byte. The properties give the largest context length (the order, 2 to 64) and the memory the model may use.

The model

• A context is 12 bytes: the number of symbols (NumStats, 16 bits), the sum of their frequencies plus the escape frequency (SummFreq), a pointer to the symbol list, and a pointer to the suffix context (the same context without its oldest byte). A context with one symbol keeps that symbol inside the context record, where the sum and the list pointer would be.
• A state (a symbol in a context) is 6 bytes: the byte, a frequency (1 to 124), and a 32-bit successor: the context that follows, one byte longer. A successor can also point into the raw text kept at the bottom of the memory (a symbol seen once whose context has not been built yet); such a pointer is turned into a real context the second time it is followed.
• The symbols of a context are kept sorted by frequency, largest first, most of the time: a symbol that is coded moves up when its frequency passes its neighbour’s. When a frequency would pass 124 the whole list is halved (Rescale); symbols that reach 0 are dropped, except in contexts below the highest order.
• A context with one symbol is a binary context. Its escape probability is not counted but looked up in a table of 14-bit adaptive probabilities (BinSumm, 128 × 64) indexed by the symbol’s frequency and a few bits of history: whether the last symbol was predicted, the run of successes, the size of the suffix context and the high bits of the last two symbols.
• The escape frequency of a larger context is not counted either: it comes from a secondary escape estimation (SEE), a table of 25 × 16 adaptive sums chosen by the number of symbols that are not excluded, the relation of the suffix context’s size, whether the context is crowded, and the high bits of the last symbol.
• After a byte is coded, the model is updated: the byte’s frequency grows by 4; missing contexts between the one that coded it and the longest are created, each with a single symbol and a frequency guessed from the same symbol’s frequency in the suffix context; the symbol is added to every context between the one that found it and the longest that did not have it.

Memory and restart

The model lives in one block of the size the properties give, and its allocator is part of the format. The block is used from both ends: the raw text grows up from the bottom; contexts are taken from the top; symbol lists, which are 12-byte units in runs of 1 to 128 units, come from a free list for each of 38 sizes, or from the gap between. When the free lists and the gap are used up, free neighbouring blocks are merged (once in 255 attempts), and if that does not help the model restarts: it is rebuilt empty, as at the start, and the data goes on. A decoder must restart at exactly the same byte as the encoder, which depends on every allocation, so the allocator must be reproduced exactly: the unit sizes, the free lists, the merging and the splitting of larger blocks. A decoder that does not do so decodes correctly until the first restart and is wrong after it.

The range coder

7-Zip codes the symbols with a carry-less binary-range-style coder over a total frequency, not Shkarin’s original coder. The stream starts with a byte that must be 0 and four bytes of code; the range starts at 2³² − 1. To decode, the range is divided by the total (the sum of the frequencies of the symbols not excluded, plus the escape frequency) and the code divided by the result gives a number from 0 up; walking the symbols’ frequencies, the symbol whose cumulative interval holds it is found. The code then loses the start of that interval times the range, the range is multiplied by the symbol’s frequency, and bytes are shifted in while the range is below 2²⁴. A binary context uses a single threshold instead: the range shifted right by 14 times the probability.

There are two PPMd variants in 7-Zip’s source: Ppmd7 (this one, variant H, used by 7z and, with a different range coder, by ZIP’s method 98 in its variant I form Ppmd8), and the .pmd file’s own container. The 7z decoder does not look for an end mark: it decodes exactly the unpacked size of the folder.