The VCDIFF Generic Differencing and Compression Data Format
Extracted elements (29)
The decoding algorithm is intentionally independent of the encoder's string matching and windowing algorithms, so that encoder implementations can compete and improve without requiring decoder updates. The delta file encodes all information the decoder needs (window positions, instruction choices) explicitly.
The delta encoding separates ADD/RUN data, instructions and sizes, and COPY addresses into three distinct byte arrays within each window. This separation enables optional independent secondary compression of each section and allows linear-time decoding with working space proportional to window size.
The minimum COPY instruction size of 4 in the default code table was chosen based on experiments showing that excluding short matches (less than 4 bytes) improved overall compression rates. The code table design allows encoders to override this for domain-specific data.
The secondary compressor mechanism is defined in the format but its specific compressor formats are intentionally left open. The authors found the basic Vcdiff format adequate for most differencing use cases and recommend keeping the format stable so secondary compressors can be defined later without breaking the core format.
Vcdiff treats data compression as a special case of differencing where the source data is empty, unifying Lempel-Ziv'77 string parsing and Tichy block-move differencing into a single framework. This allows a single format to serve both compression-only and delta-compression use cases.
Vcdiff uses only byte-aligned data, avoiding bit-level operations. This trades a slight reduction in compression efficiency for significantly improved decoding speed, which is the primary design goal for the decoder side.
Source window file offsets are encoded as variable-sized integers and may represent 64-bit values on large file systems. When delta files produced on a 64-bit system are decoded on a 32-bit system, source window positions that exceed 32-bit addressable space may make portions of the target data unrecoverable. The RFC notes this should be resolved by a generic negotiation mechanism at the protocol level.
ADD and RUN data sections, the instructions section, and COPY addresses section MAY be further compressed using a secondary compressor if VCD_DECOMPRESS is set in the header and the corresponding Delta_Indicator bits are set.
An encoder MAY modify the near cache size (s_near) and same cache size (s_same) from their defaults, but then MUST encode the new values in the delta file (via the application-defined code table mechanism) so the decoder can properly initialize its caches.
If VCD_DECOMPRESS was set in the header and any of VCD_DATACOMP, VCD_INSTCOMP, or VCD_ADDRCOMP bits are set in Delta_Indicator, those sections MUST be decompressed using the specified secondary compressor before decoding the delta instructions.
In the instructions array, if the first delta instruction of a code entry is not NOOP and its table size is zero, then size1 MUST be present as the next integer; otherwise size1 MUST be omitted. The same rule applies to size2 for the second instruction.
The Win_Indicator byte MUST NOT have more than one of VCD_SOURCE and VCD_TARGET bits set. It MAY have neither bit set, in which case the target window was encoded without reference to any external source window.
Vcdiff SHALL limit a byte to its lower eight bits even on machines with larger bytes, ensuring byte-level portability across all conforming platforms.
When encoding an application-defined code table as a VCDIFF delta, the computation MUST use the default code table for encoding the delta instructions (not the new table being transmitted). This allows the decoder to reconstruct the new table without prior knowledge of it.
An application-defined code table is transmitted as a VCDIFF delta of the new 1536-byte serialized table (ordered as 256 type1, 256 type2, 256 size1, 256 size2, 256 mode1, 256 mode2 bytes) against the serialized default code table. The delta encoding of the code table itself MUST use the default code table.
COPY address encoding uses two cache types maintained synchronously by encoder and decoder: a 'near' cache (circular buffer of s_near most-recent addresses, default 4) for nearby addresses, and a 'same' cache (hash table of s_same*256 slots, default s_same=3) for exact repeated addresses. Caches are initialized to zero at the start of each target window.
COPY addresses are encoded using one of several modes: VCD_SELF (0) encodes the raw address as an integer; VCD_HERE (1) encodes 'here - addr'; near modes [2, s_near+1] encode 'addr - near[m-2]'; same modes [s_near+2, s_near+s_same+1] encode a single byte b such that addr == same[(m-(s_near+2))*256+b].
Target and source windows are conceptually concatenated into a superstring U = S[0..s-1]T[0..t-1]. COPY instruction addresses are positions within U; the address of T[k] is s+k. This unified address space allows COPY instructions to reference either source or target data.
The default code table defines s_near=4 and s_same=3, giving 9 COPY address modes. It provides 256 instruction entries including single RUN (index 0), 18 single ADD entries, single COPY entries for all 9 modes, and combined ADD+COPY and COPY+ADD pairs for common small-size patterns (indices 163-255).
Three delta instruction types encode target window reconstruction: ADD (size x plus x literal bytes), COPY (size x and address p in superstring U, data must lie entirely within S or T), and RUN (size x and byte b repeated x times). COPY supports overlap when the copy source starts before the destination, enabling efficient encoding of periodic sequences.
IANA administers the Secondary Compressor ID number space (values 1..255). New values must be documented in an RFC or equivalent peer-reviewed reference with sufficient detail for interoperability. Assignments are First Come, First Served per RFC 2434. This document defines no values in this space.
The RFC states that Vcdiff only provides an encoding format for compressed and differenced data and does not address storage in file systems or runtime memory management. The authors do not anticipate any security issues specific to the Vcdiff format itself.
An instruction code table entry consists of six fields (inst1, size1, mode1, inst2, size2, mode2), each a single unsigned byte. The 256-entry table is referenced by a single-byte index in the instructions array; if a size field is zero, the actual size is encoded separately as an integer following the index.
Each Window section begins with a Win_Indicator byte: bit 0 (VCD_SOURCE) indicates the source window came from the source file; bit 1 (VCD_TARGET) indicates the source window came from an earlier part of the target file. If either bit is set, two integers follow giving source segment length and position.
The delta encoding of a target window contains, in order: length of delta encoding (integer), target window size (integer), Delta_Indicator (byte), length of ADD/RUN data (integer), length of instructions section (integer), length of COPY addresses (integer), followed by the three data arrays themselves.
The Delta_Indicator byte within the delta encoding of a target window has three bits: VCD_DATACOMP (bit 0), VCD_INSTCOMP (bit 1), and VCD_ADDRCOMP (bit 2), indicating whether the ADD/RUN data section, the instructions section, and the COPY addresses section (respectively) have been compressed with the secondary compressor.
The Hdr_Indicator byte has two defined bits: bit 0 (VCD_DECOMPRESS) signals a secondary compressor ID follows, and bit 1 (VCD_CODETABLE) signals that an application-defined code table length and data follow. If both bits are set, the compressor ID precedes the code table data.
The VCDIFF delta file begins with four magic header bytes: Header1=0xD6, Header2=0xC3, Header3=0xC4 (ASCII 'V', 'C', 'D' with MSBs set to 1), and Header4 currently set to zero (reserved for future version indication).
Unsigned integers are encoded in a portable variable-length base-128 format: each 7-bit digit occupies the lower bits of a byte, and all bytes except the least significant have their MSB set to indicate more bytes follow. This ensures portability across 8-bit byte systems and compact encoding of small values.