RFC 3284
The VCDIFF Generic Differencing and Compression Data Format
RFC 3284: The VCDIFF Generic Differencing and Compression Data Format 🎀
okay bestie, this one is from June 2002 🌸 It's a Standards Track document from the Network Working Group, which means it's meant to become an actual Internet standard 💅
The authors are four people: D. Korn (AT&T Labs), J. MacDonald (UC Berkeley), J. Mogul (Hewlett-Packard Company), and K. Vo (AT&T Labs) ✨ The header doesn't list anything it obsoletes or updates, so it's not replacing or patching any older RFC 🦋
Status of this Memo 💜
this part is the official "here's what this doc is" bit. It specifies an Internet standards track protocol for the Internet community and asks for discussion and suggestions for improvements 🫶 For the current standardization state and status, you check the current edition of the "Internet Official Protocol Standards" (STD 1). Distribution of this memo is unlimited 🌈
Copyright Notice 🔒
Copyright (C) The Internet Society (2002). All Rights Reserved. legal stuff, but it's there 💅
Abstract ✨
so the TL;DR is that this memo describes VCDIFF, a general, efficient and portable data format for encoding compressed and/or differencing data, so it can be easily transported among computers 🧚
Table of Contents 🌸
1. Executive Summary ........................................... 2
2. Conventions ................................................. 4
3. Delta Instructions .......................................... 5
4. Delta File Organization ..................................... 6
5. Delta Instruction Encoding .................................. 12
6. Decoding a Target Window .................................... 20
7. Application-Defined Code Tables ............................. 21
8. Performance ................................................. 22
9. Further Issues .............................................. 24
10. Summary ..................................................... 25
11. Acknowledgements ............................................ 25
12. Security Considerations ..................................... 25
13. Source Code Availability .................................... 25
14. Intellectual Property Rights ................................ 26
15. IANA Considerations ......................................... 26
16. References .................................................. 26
17. Authors' Addresses .......................................... 28
18. Full Copyright Statement .................................... 291. Executive Summary 🔥
okay so compression and differencing can seriously level up how we store and send files and file versions 📦 Files get bounced between machines with totally different architectures and performance, so the data has to be encoded in a portable form that can be decoded with little or no knowledge of the encoders. That's the whole vibe of this doc: it describes Vcdiff, a compact, portable encoding format built for exactly this 💖
Okay, quick definitions, bestie 🧚 Data differencing is computing a compact, invertible encoding of a "target file" given a "source file". Data compression is basically the same thing, just without any source data. The UNIX utilities diff, compress, and gzip are the famous examples of these tools 🍓 For differencing, the encoded result is called a "delta file", and for compression it's called a "compressed file". Both are great for storage and transmission because they're often smaller than the originals ✨
Differencing and compression are usually treated as separate kinds of data processing, but the Vdelta technique by Korn and Vo [1] shows that compression can be seen as a special case of differencing where the source data is empty 🤯 The core idea is to unify the string parsing scheme from the Lempel-Ziv'77 (LZ'77) style compressors [2] with the block-move technique of Tichy [3]. Loosely speaking, it goes like this:
- a. Concatenate source and target data.
- b. Parse the data from left to right as in LZ'77 but make sure that a parsed segment starts the target data.
- c. Start to output when reaching target data.
Parsing is based on string matching algorithms, like suffix trees [4] or hashing, and they each have different time and space performance characteristics 🦋 Vdelta uses a fast string matching algorithm that needs less memory than other techniques [5,6]. Even so, the memory requirement can still be a dealbreaker for large files 😭 The common fix is to split an input file into chunks called "windows" and process each one separately. Here's the tea: except for unpublished work by Vo, little has been done on designing effective windowing schemes. Current techniques, Vdelta included, just use source and target windows with corresponding addresses across the source and target files 💅
String matching and windowing algorithms have a huge influence on the compression rate of delta and compressed files. But it's really desirable to have a portable encoding format that doesn't depend on those algorithms 🫶 That's what lets you build client-server apps where a server can serve clients with unknown computing characteristics. Sadly, every differencing and compression tool so far, Vdelta too, falls short here. Their storage formats are tangled up with the string matching and/or windowing algorithms they use 😩
Vcdiff fixes all of this 👑 It has the following characteristics:
- Output compactness: The basic encoding format compactly represents compressed or delta files. Applications can further extend the basic encoding format with "secondary encoders" to get even more compression.
- Data portability: The basic encoding format is free from machine byte order and word size issues. This means data can be encoded on one machine and decoded on a different machine with a different architecture.
- Algorithm genericity: The decoding algorithm is independent from string matching and windowing algorithms. This allows competition among implementations of the encoder while keeping the same decoder 🌈
- Decoding efficiency: Except for secondary encoder issues, the decoding algorithm runs in time proportionate to the size of the target file and uses space proportionate to the maximal window size. Vcdiff differs from more conventional compressors in that it uses only byte-aligned data, which avoids bit-level operations. That speeds up decoding, at the slight cost of compression efficiency ⚡
The combined differencing and compression method is called "delta compression" [14]. Since this way of processing data treats compression as a special case of differencing, the term "delta file" is used for the compressed output in both cases 🧚
2. Conventions 💜
the basic data unit is a byte. For portability, Vcdiff shall limit a byte to its lower eight bits, even on machines with larger bytes 🎀 Bits in a byte are ordered from right to left, so the least significant bit (LSB) has value 1 and the most significant bit (MSB) has value 128.
For explaining things in this doc, the LSB is numbered 0 and the MSB is numbered 7. Bit numbers never show up in the encoded format itself, so don't go looking for them 🙈
Vcdiff encodes unsigned integers with a portable, variable-sized format (originally introduced in the Sfio library [7]). It treats an integer as a number in base 128. Each digit is stored in the lower seven bits of a byte. Every byte except the least significant one has its MSB turned on, which signals that there are still more digits coming 🔥 Two key properties make this really good for a compression format:
- a. The encoding is portable among systems using 8-bit bytes, and
- b. Small values are encoded compactly.
Let's do an example, bestie 🍓 Take the value 123456789. It can be written as four 7-bit digits, which are 58, 111, 26, and 21, ordered from most to least significant. Here's the 8-bit byte encoding of those digits. Notice that the MSBs of 58, 111 and 26 are on:
+-------------------------------------------+
| 10111010 | 11101111 | 10011010 | 00010101 |
+-------------------------------------------+
MSB+58 MSB+111 MSB+26 0+21From here on, "byte" and "integer" refer to a byte and an unsigned integer as just described 💖
Some algorithms in the C language are shown now and then to clarify the descriptions. That C code is only for clarification and is not part of the actual specification of the Vcdiff format 🌸
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14, RFC 2119 [12]. That's the official rulebook for the caps words, so pay attention to them 📜✨
3. Delta Instructions ✨
okay so a big target file gets chopped up into chunks called "target windows" 🧩. They're non-overlapping, and they get processed one at a time, in order, based on where they sit in the target file.
A target window T, of length t, may be compared against some source data segment S, of length s. By design, that source segment S comes from either the source file (if there is one) or from a part of the target file that's earlier than T. So during decoding, S is totally known by the time T is being decoded. 🔍
The way we pick T, t, S and s is up to some window selection algorithm, and that choice can hugely change how big the encoding ends up being. BUT (and this is the best part) these choices are encoded in the output, so the decoder doesn't need to know anything about the window selection algorithm. Iconic. 💅
Let's say S[j] is the jth byte in S, and T[k] is the kth byte in T. For the delta instructions, we treat S and T as substrings of one big superstring U, made by sticking them together like this:
S[0]S[1]...S[s-1]T[0]T[1]...T[t-1]The "address" of a byte in S or T is just its location in U. For example, the address of T[k] is s+k. 🦋
The instructions that encode and direct the rebuilding of a target window are called delta instructions. There are three types:
ADD: This one has two arguments, a size x and a sequence of x bytes to be copied. 🌸COPY: This one has two arguments, a size x and an address p in the string U. Those arguments point to the substring of U that must be copied. We shall assert that such a substring must be entirely contained in either S or T. 🎀RUN: This one has two arguments, a size x and a byte b, which gets repeated x times. 🍓
Here are some example source and target windows, plus the delta instructions that encode the target window in terms of the source window. Look at how clean this is 😭
a b c d e f g h i j k l m n o p
a b c d w x y z e f g h e f g h e f g h e f g h z z z z
COPY 4, 0
ADD 4, w x y z
COPY 4, 4
COPY 12, 24
RUN 4, zSo the first letter 'a' in the target window is at location 16 in the superstring. ✨ Also, the fourth instruction, "COPY 12, 24", copies data from T itself, since address 24 is position 8 in T. This example also shows that it's totally fine for the data being copied to overlap with the data being copied from, as long as the latter starts earlier. That's what makes it so efficient for encoding periodic sequences, aka sequences with regularly repeated subsequences. 🔁 And the RUN instruction is a compact way to encode a sequence that repeats the same byte, even though that kind of sequence can be thought of as a periodic sequence with period 1. Main character energy 👑
To rebuild the target window, the decoder just goes through one delta instruction at a time and copies the data, either from the source window or from the target window being reconstructed, depending on the instruction's type and its associated address (if it has one). 🧚
4. Delta File Organization 🧚
okay this is the big-picture layout 🗺️ A Vcdiff delta file starts with a Header section, followed by a sequence of Window sections. The Header section has magic bytes to identify the file type, plus info about data processing beyond the basic encoding format. The Window sections are where the target windows get encoded. 🌈
Here's the overall organization of a delta file. The indented items break down the ones right above them. Anything in square brackets might or might not be in the file, depending on what the Indicator byte above it says. 💖
Header
Header1 - byte
Header2 - byte
Header3 - byte
Header4 - byte
Hdr_Indicator - byte
[Secondary compressor ID] - byte
[Length of code table data] - integer
[Code table data]
Size of near cache - byte
Size of same cache - byte
Compressed code table data
Window1
Win_Indicator - byte
[Source segment size] - integer
[Source segment position] - integer
The delta encoding of the target window
Length of the delta encoding - integer
The delta encoding
Size of the target window - integer
Delta_Indicator - byte
Length of data for ADDs and RUNs - integer
Length of instructions and sizes - integer
Length of addresses for COPYs - integer
Data section for ADDs and RUNs - array of bytes
Instructions and sizes section - array of bytes
Addresses section for COPYs - array of bytes
Window2
...4.1 The Header Section 🎀
Every delta file starts with a header section laid out like this. Quick reminder: square brackets mean the item is optional. 🫶
Header1 - byte = 0xD6
Header2 - byte = 0xC3
Header3 - byte = 0xC4
Header4 - byte
Hdr_Indicator - byte
[Secondary compressor ID] - byte
[Length of code table data] - integer
[Code table data]The first three Header bytes are the ASCII characters 'V', 'C' and 'D', but with their most significant bits turned on (in hex, that's 0xD6, 0xC3, and 0xC4). 🔥 The fourth Header byte is currently set to zero. In the future, it might be used to show the version of Vcdiff. 👀
The Hdr_Indicator byte tells you whether there's any initialization data needed to help rebuild the data in the Window sections. This byte MAY have non-zero values for either, both, or neither of the two bits VCD_DECOMPRESS and VCD_CODETABLE below:
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^
| |
| +-- VCD_DECOMPRESS
+---- VCD_CODETABLEIf bit 0 (VCD_DECOMPRESS) is non-zero, that means a secondary compressor may have been used to further compress certain parts of the delta encoding data, as described in Sections 4.3 and 6. In that case, the ID of the secondary compressor comes next. If this bit is zero, the compressor ID byte isn't included. 🍓
If bit 1 (VCD_CODETABLE) is non-zero, that means an application-defined code table is to be used for decoding the delta instructions. This table is itself compressed. The length of the data that makes up this compressed code table comes next, followed by the data. Section 7 talks all about application-defined code tables. If this bit is zero, the code table data length and the code table data aren't included. 💜
If both bits are set, the compressor ID byte gets included before the code table data length and the code table data. Don't skip it! 🙈
4.2 The Format of a Window Section 💅
Each Window section is organized like this:
Win_Indicator - byte
[Source segment length] - integer
[Source segment position] - integer
The delta encoding of the target windowHere are the details on the different items: 🌷
- Win_Indicator: This byte is a set of bits, as shown:
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^
| |
| +-- VCD_SOURCE
+---- VCD_TARGETIf bit 0 (VCD_SOURCE) is non-zero, that means a segment of data from the "source" file was used as the corresponding source window to encode the target window. The decoder uses that same source data segment to decode the target window. 🦋
If bit 1 (VCD_TARGET) is non-zero, that means a segment of data from the "target" file was used as the corresponding source window to encode the target window. Same deal: this same source data segment gets used to decode the target window. ✨
The Win_Indicator byte MUST NOT have more than one of the bits set (non-zero). It MAY have none of these bits set. 🫧
If one of these bits is set, the byte is followed by two integers that tell you, in order, the length and the position of the source data segment in the relevant file. If the indicator byte is zero, the target window was compressed by itself without comparing against another data segment, and those two integers aren't included. 🌸
- The delta encoding of the target window: This contains the delta encoding of the target window, either in terms of the source data segment (i.e.,
VCD_SOURCEorVCD_TARGETwas set) or by itself if no source window is specified. The data format is discussed next. 🧚
4.3 The Delta Encoding of a Target Window ✨
okay so this is the layout for one target window's delta encoding, bestie 🎀 it's a lot but it's giving organized:
Length of the delta encoding - integer
The delta encoding
Length of the target window - integer
Delta_Indicator - byte
Length of data for ADDs and RUNs - integer
Length of instructions section - integer
Length of addresses for COPYs - integer
Data section for ADDs and RUNs - array of bytes
Instructions and sizes section - array of bytes
Addresses section for COPYs - array of bytesLength of the delta encoding 💖: this integer gives the total number of remaining bytes that make up the data of the delta encoding for this target window.
The delta encoding 🦋: this contains the data representing the delta encoding, which is described next.
Length of the target window 📏: this integer is the actual size of the target window after decompression. A decoder can use this value to allocate memory to store the uncompressed data.
Delta_Indicator 🔥: this byte is a set of bits, as shown:
7 6 5 4 3 2 1 0
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
^ ^ ^
| | |
| | +-- VCD_DATACOMP
| +---- VCD_INSTCOMP
+------ VCD_ADDRCOMPVCD_DATACOMP: bit value 1. 💜VCD_INSTCOMP: bit value 2. 💜VCD_ADDRCOMP: bit value 4. 💜
As discussed, the delta encoding is made of COPY, ADD and RUN instructions 🌸. The ADD and RUN instructions come with unmatched data (aka data that doesn't specifically match anything in the source window or in some earlier part of the target window), and the COPY instructions have addresses of where the matches happen. Optionally, these types of data MAY be further compressed using a secondary compressor. So Vcdiff splits the encoding of the delta instructions into three parts:
- a. the unmatched data in the ADD and RUN instructions,
- b. the delta instructions and their accompanying sizes, and
- c. the addresses of the COPY instructions.
If the bit VCD_DECOMPRESS (Section 4.1) was on, each of these sections may have been compressed using the specified secondary compressor. Bit positions 0 (VCD_DATACOMP), 1 (VCD_INSTCOMP), and 2 (VCD_ADDRCOMP) each indicate, if non-zero, that the matching part is compressed. Then these parts MUST be decompressed before decoding the delta instructions. 🚨
Length of data for ADDs and RUNs 🧃: this is the length (in bytes) of the section storing the unmatched data that goes with the ADD and RUN instructions.
Length of instructions section 📝: this is the length (in bytes) of the delta instructions and their accompanying sizes.
Length of addresses for COPYs 📍: this is the length (in bytes) of the section storing the addresses of the COPY instructions.
Data section for ADDs and RUNs 🍓: this sequence of bytes encodes the unmatched data for the ADD and RUN instructions.
Instructions and sizes section 🧁: this sequence of bytes encodes the instructions and their sizes.
Addresses section for COPYs 🗺️: this sequence of bytes encodes the addresses of the COPY instructions.
5. Delta Instruction Encoding 🧚
The delta instructions from Section 3 are the results of string matching. For lots of data differencing apps where the changes between source and target data are small, any straightforward representation of these instructions would be fine 👌. BUT for stuff like binary file differencing or data compression, it really matters to encode these instructions well so you get good compression rates. The keys to pulling that off are encoding the addresses of COPY instructions efficiently and encoding the sizes of all the delta instructions efficiently. 💅
5.1 Address Encoding Modes of COPY Instructions 🦋
Addresses of COPY instructions are locations of matches, and they often show up close together or even exactly equal to each other. That's because data in local regions is often copied over with minor changes 🙈. So coding a newly matched address against some recently matched addresses can be super beneficial. To take advantage of this and encode COPY addresses more efficiently, the Vcdiff data format supports two different types of address caches. Both the encoder and the decoder maintain these caches, so the decoder's caches stay synchronized with the encoder's caches 🤝.
a. A "near" cache is an array with "s_near" slots, each containing an address used for encoding addresses nearby to previously encoded addresses (in the positive direction only). The near cache also maintains a "next_slot" index into the near cache. New entries to the near cache always go into the next_slot index, which keeps a circular buffer of the s_near most recent addresses. 🔄
b. A "same" cache is an array with "s_same", with a multiple of 256 slots, each containing an address. The same cache maintains a hash table of recent addresses used for repeatedly encoding the exact same address 👯.
By default, the parameters s_near and s_same are set to 4 and 3 respectively. An encoder MAY modify these values, but then it MUST encode the new values in the encoding itself, as discussed in Section 7, so that the decoder can set up its own caches properly. ✨
At the start of processing a target window, an implementation (encoder or decoder) initializes all of the slots in both caches to zero. The next_slot pointer of the near cache is set to point to slot zero 🎯.
Each time a COPY instruction is processed by the encoder or decoder, the implementation's caches get updated like this, where "addr" is the address in the COPY instruction:
a. The slot in the near cache referenced by the next_slot index is set to addr. Then the next_slot index is incremented modulo s_near. ➕
b. The slot in the same cache whose index is addr%(s_same*256) is set to addr. [We use the C notations of % for modulo and * for multiplication.] 🧮
5.2 Example code for maintaining caches 💻
To make the above super clear, here are examples of cache data structures and the algorithms to initialize and update them:
typedef struct _cache_s
{
int* near; /* array of size s_near */
int s_near;
int next_slot; /* the circular index for near */
int* same; /* array of size s_same*256 */
int s_same;
} Cache_t;
cache_init(Cache_t* ka)
{
int i;
ka->next_slot = 0;
for(i = 0; i < ka->s_near; ++i)
ka->near[i] = 0;
for(i = 0; i < ka->s_same*256; ++i)
ka->same[i] = 0;
}
cache_update(Cache_t* ka, int addr)
{
if(ka->s_near > 0)
{ ka->near[ka->next_slot] = addr;
ka->next_slot = (ka->next_slot + 1) % ka->s_near;
}
if(ka->s_same > 0)
ka->same[addr % (ka->s_same*256)] = addr;
}5.3 Encoding of COPY instruction addresses 🌈
The address of a COPY instruction is encoded using different modes, depending on which type of cached address is used, if any.
Let "addr" be the address of a COPY instruction to be decoded, and "here" be the current location in the target data (aka the start of the data about to be encoded or decoded). Let near[j] be the jth element in the near cache, and same[k] be the kth element in the same cache. Here are the possible address modes:
VCD_SELF: this mode has value 0. The address was encoded by itself as an integer. 🧍VCD_HERE: this mode has value 1. The address was encoded as the integer valuehere - addr. 📌- Near modes: the "near modes" are in the range
[2,s_near+1]. Let m be the mode of the address encoding. The address was encoded as the integer valueaddr - near[m-2]. 🏠 - Same modes: the "same modes" are in the range
[s_near+2,s_near+s_same+1]. Let m be the mode of the encoding. The address was encoded as a single byte b such thataddr == same[(m - (s_near+2))*256 + b]. 🎀
5.4 Example code for encoding and decoding of COPY instruction addresses 🫶
Here are some example algorithms to show how the address modes work. The encoder gets to choose its address modes freely. The sample addr_encode() algorithm is just one way of picking a mode. The addr_decode() algorithm will uniquely decode addresses no matter which choice the encoder's algorithm made 🧩.
Note that the address caches get updated immediately after an address is encoded or decoded. That way, the decoder is always synchronized with the encoder 💜.
int addr_encode(Cache_t* ka, int addr, int here, int* mode)
{
int i, d, bestd, bestm;
/* Attempt to find the address mode that yields the
* smallest integer value for "d", the encoded address
* value, thereby minimizing the encoded size of the
* address. */
bestd = addr; bestm = VCD_SELF; /* VCD_SELF == 0 */
if((d = here-addr) < bestd)
{ bestd = d; bestm = VCD_HERE; } /* VCD_HERE == 1 */
for(i = 0; i < ka->s_near; ++i)
if((d = addr - ka->near[i]) >= 0 && d < bestd)
{ bestd = d; bestm = i+2; }
if(ka->s_same > 0 && ka->same[d = addr%(ka->s_same*256)] == addr)
{ bestd = d%256; bestm = ka->s_near + 2 + d/256; }
cache_update(ka,addr);
*mode = bestm; /* this returns the address encoding mode */
return bestd; /* this returns the encoded address */
}Heads up 👀: the addr_encode() algorithm picks the best address mode using a local optimization, but that might not lead to the best encoding efficiency, because different modes lead to different instruction encodings, as described below.
The functions addrint() and addrbyte() used in addr_decode() get an integer or a byte, respectively, from the "Addresses section for COPYs" (Section 4.3). These utilities won't be described here. We just recall that an integer is represented as a compact variable-sized string of bytes, as described in Section 2 (i.e., base 128) 🔢.
int addr_decode(Cache_t* ka, int here, int mode)
{ int addr, m;
if(mode == VCD_SELF)
addr = addrint();
else if(mode == VCD_HERE)
addr = here - addrint();
else if((m = mode - 2) >= 0 && m < ka->s_near) /* near cache */
addr = ka->near[m] + addrint();
else /* same cache */
{ m = mode - (2 + ka->s_near);
addr = ka->same[m*256 + addrbyte()];
}
cache_update(ka, addr);
return addr;
}5.4 Instruction Codes ✨
okay so matches are usually super short 🥺 with little bits of unmatched data hanging out in between. That means COPY and ADD instructions are often tiny too 💅. This is especially true for binary stuff like executable files, or structured data like HTML or XML 🌸. So compression can get a glow-up if you squish the sizes and instruction types together, and also combine neighbouring delta instructions when their data sizes are small enough 💖. Whether those combos are worth it depends on lots of things, like the data you're working with and the string matching algorithm you're using 🔍. For example, if a bunch of COPY instructions all share the same data size, it might be worth encoding those more compactly than the rest ✨.
The Vcdiff format is designed so a decoder doesn't need to know what choices the encoder made 🧚. The trick is the "instruction code table" 💜, which has 256 entries. Each entry defines either a single delta instruction or a pair of instructions that got combined 👯. Heads up: the code table itself only lives in main memory, not in the delta file (unless you're using an application-defined code table, which is described in Section 7). The encoded data just includes the index of each instruction, and since there are only 256 indices, each index fits in a single byte 🎀.
Each instruction code entry has six fields, and each one is a single byte with an unsigned value 🦋:
+-----------------------------------------------+
| inst1 | size1 | mode1 | inst2 | size2 | mode2 |
+-----------------------------------------------+Each triple (inst,size,mode) defines a delta instruction. Here's what the fields mean:
inst: An "inst" field can have one of the four values: NOOP (0), ADD (1), RUN (2) or COPY (3), which tell you the instruction type. NOOP means no instruction is specified. In that case, both the corresponding size and mode fields will be zero 🙈.size: A "size" field is zero or positive 💖. A value of zero means the size of the instruction is encoded separately as an integer in the "Instructions and sizes section" (Section 6). A positive value for "size" defines the actual data size. Since the size is restricted to a byte, the maximum value for any instruction with its size implicitly defined in the code table is 255 🔥.mode: A "mode" field only matters when the associated delta instruction is a COPY ✨. It defines the mode used to encode the associated addresses. For other instructions, it's always zero.
5.6 The Code Table 👑
Okay, now that we've talked about address modes and instruction code tables, we can define a "Code Table" 🌈. It's made up of the following:
s_near: the size of the near cache,s_same: the size of the same cache,i_code: the 256-entry instruction code table.
Vcdiff itself defines a "default code table" where s_near is 4 and s_same is 3 🍓. So there are 9 address modes for a COPY instruction. The first two are VCD_SELF (0) and VCD_HERE (1) 💜. Modes 2, 3, 4 and 5 are for addresses coded against the near cache, and modes 6, 7 and 8 are for addresses coded against the same cache 🦋.
TYPE SIZE MODE TYPE SIZE MODE INDEX
---------------------------------------------------------------
1. RUN 0 0 NOOP 0 0 0
2. ADD 0, [1,17] 0 NOOP 0 0 [1,18]
3. COPY 0, [4,18] 0 NOOP 0 0 [19,34]
4. COPY 0, [4,18] 1 NOOP 0 0 [35,50]
5. COPY 0, [4,18] 2 NOOP 0 0 [51,66]
6. COPY 0, [4,18] 3 NOOP 0 0 [67,82]
7. COPY 0, [4,18] 4 NOOP 0 0 [83,98]
8. COPY 0, [4,18] 5 NOOP 0 0 [99,114]
9. COPY 0, [4,18] 6 NOOP 0 0 [115,130]
10. COPY 0, [4,18] 7 NOOP 0 0 [131,146]
11. COPY 0, [4,18] 8 NOOP 0 0 [147,162]
12. ADD [1,4] 0 COPY [4,6] 0 [163,174]
13. ADD [1,4] 0 COPY [4,6] 1 [175,186]
14. ADD [1,4] 0 COPY [4,6] 2 [187,198]
15. ADD [1,4] 0 COPY [4,6] 3 [199,210]
16. ADD [1,4] 0 COPY [4,6] 4 [211,222]
17. ADD [1,4] 0 COPY [4,6] 5 [223,234]
18. ADD [1,4] 0 COPY 4 6 [235,238]
19. ADD [1,4] 0 COPY 4 7 [239,242]
20. ADD [1,4] 0 COPY 4 8 [243,246]
21. COPY 4 [0,8] ADD 1 0 [247,255]
---------------------------------------------------------------The default instruction code table is shown above in a compact format that we only use for describing things 🧁. See section 7 for how an instruction code table is represented in the Vcdiff encoding format. In this depiction, a zero value for size means the size is coded separately. The mode of non-COPY instructions is shown as 0, even though those modes aren't used.
In the depiction, each numbered line stands for one or more entries in the actual instruction code table (remember, an entry can represent up to two combined delta instructions 🫶). The last column, "INDEX", shows which index value, or range of index values, that line covers. (The notation [i,j] means values from i through j, inclusive 💅.) The first 6 columns of a line describe the pairs of instructions used for the corresponding index value(s).
If a line has a column entry using the [i,j] notation, that line is instantiated for each value in the range from i to j, inclusive ✨. The notation "0, [i,j]" means the line is instantiated for the value 0 and for each value in the range from i to j, inclusive.
If a line has more than one entry using the [i,j] notation, that's a "nested loop" for turning the line into a range of table entries 🌀. The first such [i,j] range is the outer loop, and the second one is the inner loop.
These examples should make it all click 🙌:
Line 1 shows the single RUN instruction with index 0. Since the size field is 0, this RUN instruction always has its actual size encoded separately.
Line 2 shows the 18 single ADD instructions. The ADD instruction with size field 0 (meaning its actual size is coded separately) has index 1. ADD instructions with sizes from 1 to 17 use code indices 2 to 18, and their sizes are as given, so they won't be separately encoded 💜.
After the single ADD instructions come the single COPY instructions, ordered by their address encoding modes 🦋. For example, line 11 shows the COPY instructions with mode 8, which is the last of the same cache. In this case, the COPY instruction with size field 0 has index 147. Again, its actual size gets coded separately.
Lines 12 to 21 show the pairs of instructions that get combined together 👯. For example, line 12 depicts the 12 entries where an ADD instruction is combined with an immediately following COPY instruction. The entries with indices 163, 164 and 165 represent the pairs where the ADD instructions all have size 1, while the COPY instructions have mode 0 (VCD_SELF) and sizes 4, 5 and 6 respectively 🎀.
The last line, line 21, shows the eight instruction pairs where the first instruction is a COPY and the second is an ADD 🔥. In this case, all the COPY instructions have size 4 with modes ranging from 0 to 8, and all the ADD instructions have size 1. So the entry with the largest index, 255, combines a COPY instruction of size 4 and mode 8 with an ADD instruction of size 1 💀.
The minimum size of 4 for COPY instructions in the default code table was picked from experiments showing that leaving out small matches (less than 4 bytes long) improved the compression rates 📈✨.
6. Decoding a Target Window ✨
okay so bestie, remember Section 4.3? It told us the delta instructions and their data get packed into three byte arrays 🎀
Data section for ADDs and RUNs,
Instructions and sizes section, and
Addresses section for COPYs.Sometimes these get squished even more by some secondary compressor 🗜️ So once that's been undone, we end up with three arrays:
inst: bytes coding the instructions and sizes.data: unmatched data associated with ADDs and RUNs.addr: bytes coding the addresses of COPYs.
Here's how they're organized 💅
inst: a sequence of (index, [size1], [size2]) tuples, where "index" is an index into the instruction code table, and size1 and size2 are integers that MAY or MAY NOT be included in the tuple. The entry with the given "index" in the instruction code table can define up to two delta instructions. If the first delta instruction is not aVCD_NOOPand its size is zero, then size1 MUST be present. Otherwise, size1 MUST be omitted, and the size of the instruction (if it's notVCD_NOOP) is whatever the table says. Size2 works the exact same way, but for the second delta instruction 🫶data: a sequence of data values, encoded as bytes.addr: a sequence of address values. Addresses are normally encoded as integers, like we saw in Section 2 (aka base 128) 🔢 BUT since the same cache spits out addresses in the range [0,255], same cache addresses are ALWAYS encoded as a single byte. Such a glow-up 😭
So basically, each tuple in inst has an index that points at an entry in the instruction code table, and that entry tells us:
- a. whether one or two instructions got encoded, and what types they are 👀
- b. if the sizes are encoded separately, those sizes show up in order right inside the tuple
- c. if the instructions come with data (ADDs or RUNs), that data lives in the
dataarray - d. if the instructions are COPYs, their coded addresses are in the
addrarray
The decoding procedure is honestly so simple 🥹 You read one code index at a time, look up that entry in the code table, then consume the sizes, data and addresses it tells you to. The decoder keeps a little next-element pointer for each array, and "consuming" a tuple, a data value, or an address just means bumping that pointer forward 👉
Here's an example so it clicks ✨ Say that while processing the target window, the next unconsumed tuple in inst has an index of 19. The first instruction is a COPY, and its size is the very next integer in inst. Since this COPY's mode is VCD_SELF, its address is the next integer you consume from addr. The data array stays untouched 🙈 And because the second instruction for code index 19 is a NOOP, that tuple is totally finished. Done and dusted 💖
7. APPLICATION-DEFINED CODE TABLES 🧚
Okay so the default code table in Vcdiff is great for general-purpose encoders, BUT sometimes another table just slaps harder 🔥 For example, if a file has a bunch of identical chunks of data, it can be worth having a COPY instruction sized exactly to fit those chunks, so the whole instruction fits in a single byte. Iconic efficiency 👑 A special table like that MUST be encoded in the delta file, so the decoder can rebuild it before it starts decoding the data.
Vcdiff lets you specify an application-defined code table in a delta file using this data:
Size of near cache - byte
Size of same cache - byte
Compressed code table dataThe "compressed code table data" is the delta between the default code table (the source) and the new code table (the target). It's encoded the same way Section 4.3 describes for encoding a target window against a source window 🦋 Here's how that delta gets computed:
- a. Turn the new instruction code table into a string called "code" that's 1536 bytes long, following these steps in order:
- i. Add, in order, the 256 bytes for the types of the first instructions in the instruction pairs.
- ii. Add, in order, the 256 bytes for the types of the second instructions in the instruction pairs.
- iii. Add, in order, the 256 bytes for the sizes of the first instructions in the instruction pairs.
- iv. Add, in order, the 256 bytes for the sizes of the second instructions in the instruction pairs.
- v. Add, in order, the 256 bytes for the modes of the first instructions in the instruction pairs.
- vi. Add, in order, the 256 bytes for the modes of the second instructions in the instruction pairs.
- b. Do the same thing with the default code table to make a string called "dflt" 🌸
- c. Treat "code" as a target window and "dflt" as its source data, then run an encoding algorithm to get the delta of "code" in terms of "dflt". This computation MUST use the default code table for encoding the delta instructions 💜
The decoder can then reverse all of this, using the method from Section 6 along with the default code table, to rebuild the new code table 🎀 The decoder doesn't need to know anything about which encoding algorithm was used in step (c), and that's the magic part. It can still decode the table because the Vcdiff format doesn't depend on the encoding algorithm, and because the encoder in step (c) always uses the known default code table 🫶
8. Performance 🏆
The encoding format is super compact 🤏 If you're only doing compression (using the LZ-77 string parsing strategy and no secondary compressors), the typical compression rate beats Unix compress and gets close to gzip. For differencing, the data format beats every known method when it comes to its stated goal, which is mainly decoding speed and encoding efficiency. Main character energy ✨
We compared compress, gzip and Vcdiff using the archives of three versions of the Gnu C compiler: gcc-2.95.1.tar, gcc-2.95.2.tar and gcc-2.95.3.tar. Gzip ran at its default compression level, and the Vcdiff data came from the Vcodex/Vcdiff software (Section 13) 💻
Here are the different Vcdiff runs:
- Vcdiff: vcdiff is used as a compressor only.
- Vcdiff-d: vcdiff is used as a differencer only. It just compares target data against source data. Since these files are huge, they get broken into windows. Each target window, starting at some file offset in the target file, gets compared against a source window with the same file offset (in the source file). The source window is also a bit bigger than the target window so there are more chances to match 🦋
- Vcdiff-dc: This is like Vcdiff-d, but vcdiff can also compare target data against target data when it makes sense. So vcdiff does differencing AND compression at the same time 🔥 The windowing algorithm is the same as above. However, the above hint is recinded in this case.
- Vcdiff-dcw: This is like Vcdiff-dc, but the windowing algorithm uses a content-based heuristic to pick a source window that's more likely to match a given target window. So the source data often won't line up with the file offsets of the target window 🧩
gcc-2.95.1 gcc-2.95.2 gcc-2.95.3
---------------------------------------------------------
1. raw size 55,746,560 55,797,760 55,787,520
2. compress - 19,939,390 19,939,453
3. gzip - 12,973,443 12,998,097
4. Vcdiff - 15,358,786 15,371,737
5. Vcdiff-d - 100,971 26,383,849
6. Vcdiff-dc - 97,246 14,461,203
7. Vcdiff-dcw - 256,445 1,248,543The table above shows the raw sizes of the tar files and how big the compressed results are 📊 The differencing results in the gcc-2.95.2 column came from compressing gcc-2.95.2 given gcc-2.95.1. The gcc-2.95.3 column results came from compressing gcc-2.95.3 given gcc-2.95.2.
Rows 2, 3 and 4 show that, for compression only, Vcdiff's rate is worse than gzip and better than compress. Not bad, not bad 💅
The last three rows in the gcc-2.95.2 column show that when two file versions are super similar, differencing can give dramatically good compression rates 🤯 Vcdiff-d and Vcdiff-dc both use the same simple window selection method (lining things up by file offsets), but Vcdiff-dc also compresses, so its output is a tiny bit smaller. Vcdiff-dcw uses a content-based algorithm to hunt for source data that's likely to match a target window. It does a good job, but it doesn't always find the best matches, and in this case the best matches are the ones the simple Vcdiff-d method found. So the Vcdiff-dcw output is slightly bigger 🙃
The gcc-2.95.3 column flips the script 🔄 The files and their contents got rearranged or changed enough between the gcc-2.95.3.tar and gcc-2.95.2 archives that lining windows up by file offsets just stops working. So Vcdiff-d and Vcdiff-dc don't perform well. By mixing compression in with differencing, Vcdiff-dc still manages to beat Vcdiff, which only does compression. The content-based window matching in Vcdiff-dcw is great at pairing the right source and target windows, so Vcdiff-dcw is the overall winner 🏆👑
9. Further Issues ✨
okay so this section is basically the "stuff we didn't cover" corner 🫠 and there are two big things bestie needs to know about 🎀
9.1. Secondary compressors
Okay so remember how we said in Section 4.3 that certain sections in the delta encoding of a window can be squished even further by a secondary compressor? 💅 In their experience, the basic Vcdiff format is totally adequate for most purposes, so secondary compressors are seldom needed 🫶 For normal differencing, where the files have long stretches of matches, most of the compression win is already handled by normal string matching, so again, secondary compressors are seldom needed in that case 🌸
BUT (and this is a big but 😭) for stuff beyond differencing of nearly identical files, secondary compressors might be needed to get the maximal compressed results 🔥
So the vibe here is: leave the Vcdiff data format as defined in this document so that secondary compressors can be plugged in later when they become necessary 🦋 The formats of the compressed data from those compressors, or any compressors defined in the future, are left open to their implementations 🧚 Examples they mention include Huffman encoding, arithmetic encoding, and splay tree encoding [8,9] 💜
9.2. Large file system vs. small file system
This one is giving "the same file means different things on different machines" 🙈 As discussed in Section 4, a target window in a large file may be compared against some source window in another file or in the same file (from some earlier part) 🍓 In that case, the file offset of the source window is specified as a variable-sized integer in the delta encoding ✨
Here's the tea ☕ The encoding might be computed on a system that supports way bigger files than the system where the data gets decoded (like 64-bit file systems vs. 32-bit file systems) 💀 If that happens, some target data may not be recoverable 😭 They note this problem could afflict any compression format, and it ought to be resolved with a generic negotiation mechanism in the appropriate protocol(s) 🔥
10. Summary 🌈
okay recap time 💖 We described Vcdiff, a general and portable encoding format for compression and differencing ✨ It's good because it lets you implement a decoder without knowing anything about the encoders 🫶 And ignoring secondary compressors not defined within the format, the decoding algorithms run in linear time and need working space proportional to window size 🦋 Iconic, periodt 💅
11. Acknowledgements 🎀
Thanks are due to Balachander Krishnamurthy, Jeff Mogul and Arthur Van Hoff, who provided much encouragement to publicize Vcdiff 🫶 Jeff in particular helped clarify the description of the data format presented here 👑
12. Security Considerations 🔒
⚠️ Okay bestie, read this part carefully 😭
Vcdiff only provides a format to encode compressed and differenced data 🎀 It does not address any issues about how that data is actually stored in a given file system or in the run-time memory of a computer system 💀 Therefore, they do not anticipate any security issues with respect to Vcdiff 🙈
13. Source Code Availability 💻
Vcdiff is implemented as a data transforming method in Phong Vo's Vcodex library 🧚 AT&T Corp. has made the source code for Vcodex available for anyone to use to transmit data via HTTP/1.1 Delta Encoding [10,11] ✨ The source code and its license are accessible at the URL below 💖
http://www.research.att.com/sw/tools14. Intellectual Property Rights ⚖️
The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification in this document 🌸 For more information, check the online list of claimed rights at <http://www.ietf.org/ipr.html> 🔗
The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document, or the extent to which any license under such rights might or might not be available 🫠 It also doesn't represent that it has made any effort to identify any such rights 💅 Info on the IETF's procedures for rights in standards-track and standards-related documentation can be found in BCP 11 📚 Copies of claims of rights made available for publication, and any assurances of licenses to be made available, or the result of an attempt to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification, can be obtained from the IETF Secretariat 🦋
15. IANA Considerations 📋
The Internet Assigned Numbers Authority (IANA) administers the number space for Secondary Compressor ID values 🔢 Values and their meaning must be documented in an RFC or other peer-reviewed, permanent, and readily available reference, in sufficient detail so that interoperability between independent implementations is possible 🫶 Subject to these constraints, name assignments are First Come, First Served, see RFC 2434 [13] 🌈 Legal ID values are in the range 1..255 💜
This document does not define any values in this number space 🙌
16. References 📚
- [1] D.G. Korn and K.P. Vo, Vdelta: Differencing and Compression, Practical Reusable Unix Software, Editor B. Krishnamurthy, John Wiley & Sons, Inc., 1995.
- [2] J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Trans. on Information Theory, 23(3):337-343, 1977.
- [3] W. Tichy, The String-to-String Correction Problem with Block Moves, ACM Transactions on Computer Systems, 2(4):309-321, November 1984.
- [4] E.M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM, 23:262-272, 1976.
- [5] J.J. Hunt, K.P. Vo, W. Tichy, An Empirical Study of Delta Algorithms, IEEE Software Configuration and Maintenance Workshop, 1996.
- [6] J.J. Hunt, K.P. Vo, W. Tichy, Delta Algorithms: An Empirical Analysis, ACM Trans. on Software Engineering and Methodology, 7:192-214, 1998.
- [7] D.G. Korn, K.P. Vo, Sfio: A buffered I/O Library, Proc. of the Summer '91 Usenix Conference, 1991.
- [8] D. W. Jones, Application of Splay Trees to Data Compression, CACM, 31(8):996:1007.
- [9] M. Nelson, J. Gailly, The Data Compression Book, ISBN 1-55851-434-1, M&T Books, New York, NY, 1995.
- [10] J.C. Mogul, F. Douglis, A. Feldmann, and B. Krishnamurthy, Potential benefits of delta encoding and data compression for HTTP, SIGCOMM '97, Cannes, France, 1997.
- [11] Mogul, J., Krishnamurthy, B., Douglis, F., Feldmann, A., Goland, Y. and A. Van Hoff, "Delta Encoding in HTTP", RFC 3229, January 2002.
- [12] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
- [13] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998.
- [14] D.G. Korn and K.P. Vo, Engineering a Differencing and Compression Data Format, Submitted to Usenix'2002, 2001.
17. Authors' Addresses 📮
- Kiem-Phong Vo (main contact) AT&T Labs, Room D223 180 Park Avenue Florham Park, NJ 07932 Phone: 1 973 360 8630 EMail: kpv@research.att.com
- David G. Korn AT&T Labs, Room D237 180 Park Avenue Florham Park, NJ 07932 Phone: 1 973 360 8602 EMail: dgk@research.att.com
- Jeffrey C. Mogul Western Research Laboratory Hewlett-Packard Company 1501 Page Mill Road, MS 1251 Palo Alto, California, 94304, U.S.A. Phone: 1 650 857 2206 (email preferred) EMail: JeffMogul@acm.org
- Joshua P. MacDonald Computer Science Division University of California, Berkeley 345 Soda Hall Berkeley, CA 94720 EMail: jmacd@cs.berkeley.edu
18. Full Copyright Statement ©️
Copyright (C) The Internet Society (2002). All Rights Reserved. 💜
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works 🌸 However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards, in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English 🌐
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns 🫶
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE 🙏
Acknowledgement 🌷
Funding for the RFC Editor function is currently provided by the Internet Society 💖
📦 where this page comes from
- ietf: rfc3284 2002-07
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms