diff options
Diffstat (limited to 'doc/rfc/rfc3284.txt')
| -rw-r--r-- | doc/rfc/rfc3284.txt | 1627 |
1 files changed, 1627 insertions, 0 deletions
diff --git a/doc/rfc/rfc3284.txt b/doc/rfc/rfc3284.txt new file mode 100644 index 0000000..69c906d --- /dev/null +++ b/doc/rfc/rfc3284.txt @@ -0,0 +1,1627 @@ + + + + + + +Network Working Group D. Korn +Request for Comments: 3284 AT&T Labs +Category: Standards Track J. MacDonald + UC Berkeley + J. Mogul + Hewlett-Packard Company + K. Vo + AT&T Labs + June 2002 + + + The VCDIFF Generic Differencing and Compression Data Format + +Status of this Memo + + This document specifies an Internet standards track protocol for the + Internet community, and requests discussion and suggestions for + improvements. Please refer to the current edition of the "Internet + Official Protocol Standards" (STD 1) for the standardization state + and status of this protocol. Distribution of this memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (2002). All Rights Reserved. + +Abstract + + This memo describes VCDIFF, a general, efficient and portable data + format suitable for encoding compressed and/or differencing data so + that they can be easily transported among computers. + + + + + + + + + + + + + + + + + + + + + +Korn, et. al. Standards Track [Page 1] + +RFC 3284 VCDIFF June 2002 + + +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 .................................... 29 + +1. Executive Summary + + Compression and differencing techniques can greatly improve storage + and transmission of files and file versions. Since files are often + transported across machines with distinct architectures and + performance characteristics, such data should be encoded in a form + that is portable and can be decoded with little or no knowledge of + the encoders. This document describes Vcdiff, a compact portable + encoding format designed for these purposes. + + Data differencing is the process of computing a compact and + invertible encoding of a "target file" given a "source file". Data + compression is similar, but without the use of source data. The UNIX + utilities diff, compress, and gzip are well-known examples of data + differencing and compression tools. For data differencing, the + computed encoding is called a "delta file", and for data compression, + it is called a "compressed file". Delta and compressed files are + good for storage and transmission as they are often smaller than the + originals. + + Data differencing and data compression are traditionally treated as + distinct types of data processing. However, as shown in the Vdelta + technique by Korn and Vo [1], compression can be thought of as a + special case of differencing in which the source data is empty. The + basic idea is to unify the string parsing scheme used in the Lempel- + Ziv'77 (LZ'77) style compressors [2] and the block-move technique of + Tichy [3]. Loosely speaking, this works as follows: + + + +Korn, et. al. Standards Track [Page 2] + +RFC 3284 VCDIFF June 2002 + + + 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, such as suffix trees + [4] or hashing with different time and space performance + characteristics. Vdelta uses a fast string matching algorithm that + requires less memory than other techniques [5,6]. However, even with + this algorithm, the memory requirement can still be prohibitive for + large files. A common way to deal with memory limitation is to + partition an input file into chunks called "windows" and process them + separately. Here, except for unpublished work by Vo, little has been + done on designing effective windowing schemes. Current techniques, + including Vdelta, simply use source and target windows with + corresponding addresses across source and target files. + + String matching and windowing algorithms have great influence on the + compression rate of delta and compressed files. However, it is + desirable to have a portable encoding format that is independent of + such algorithms. This enables the construction of client-server + applications in which a server may serve clients with unknown + computing characteristics. Unfortunately, all current differencing + and compressing tools, including Vdelta, fall short in this respect. + Their storage formats are closely intertwined with the implemented + string matching and/or windowing algorithms. + + The encoding format Vcdiff proposed here addresses the above issues. + Vcdiff achieves the characteristics below: + + Output compactness: + The basic encoding format compactly represents compressed or + delta files. Applications can further extend the basic + encoding format with "secondary encoders" to achieve more + compression. + + Data portability: + The basic encoding format is free from machine byte order and + word size issues. This allows data to be encoded on one + machine and decoded on a different machine with 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. + + + + + +Korn, et. al. Standards Track [Page 3] + +RFC 3284 VCDIFF June 2002 + + + 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, thus avoiding bit-level operations, which + improves decoding speed at the slight cost of compression + efficiency. + + The combined differencing and compression method is called "delta + compression" [14]. As this way of data processing treats compression + as a special case of differencing, we shall use the term "delta file" + to indicate the compressed output for 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. The + bits in a byte are ordered from right to left so that the least + significant bit (LSB) has value 1, and the most significant bit + (MSB), has value 128. + + For purposes of exposition in this document, we adopt the convention + that the LSB is numbered 0, and the MSB is numbered 7. Bit numbers + never appear in the encoded format itself. + + Vcdiff encodes unsigned integer values using a portable, variable- + sized format (originally introduced in the Sfio library [7]). This + encoding treats an integer as a number in base 128. Then, each digit + in this representation is encoded in the lower seven bits of a byte. + Except for the least significant byte, other bytes have their most + significant bit turned on to indicate that there are still more + digits in the encoding. The two key properties of this integer + encoding that are beneficial to a data compression format are: + + a. The encoding is portable among systems using 8-bit bytes, and + b. Small values are encoded compactly. + + For example, consider the value 123456789, which can be represented + with four 7-bit digits whose values are 58, 111, 26, 21 in order from + most to least significant. Below is the 8-bit byte encoding of these + digits. Note that the MSBs of 58, 111 and 26 are on. + + +-------------------------------------------+ + | 10111010 | 11101111 | 10011010 | 00010101 | + +-------------------------------------------+ + MSB+58 MSB+111 MSB+26 0+21 + + + + +Korn, et. al. Standards Track [Page 4] + +RFC 3284 VCDIFF June 2002 + + + Henceforth, the terms "byte" and "integer" will refer to a byte and + an unsigned integer as described. + + Algorithms in the C language are occasionally exhibited to clarify + the descriptions. Such C code is meant for clarification only, 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]. + +3. Delta Instructions + + A large target file is partitioned into non-overlapping sections + called "target windows". These target windows are processed + separately and sequentially based on their order in the target file. + + A target window T, of length t, may be compared against some source + data segment S, of length s. By construction, this source data + segment S comes either from the source file, if one is used, or from + a part of the target file earlier than T. In this way, during + decoding, S is completely known when T is being decoded. + + The choices of T, t, S and s are made by some window selection + algorithm, which can greatly affect the size of the encoding. + However, as seen later, these choices are encoded so that no + knowledge of the window selection algorithm is needed during + decoding. + + Assume that S[j] represents the jth byte in S, and T[k] represents + the kth byte in T. Then, for the delta instructions, we treat the + data windows S and T as substrings of a superstring U, formed by + concatenating them 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 referred to by its location in + U. For example, the address of T[k] is s+k. + + The instructions to encode and direct the reconstruction of a target + window are called delta instructions. There are three types: + + ADD: This instruction has two arguments, a size x and a sequence + of x bytes to be copied. + COPY: This instruction has two arguments, a size x and an address + p in the string U. The arguments specify the substring of U + that must be copied. We shall assert that such a substring + must be entirely contained in either S or T. + + + +Korn, et. al. Standards Track [Page 5] + +RFC 3284 VCDIFF June 2002 + + + RUN: This instruction has two arguments, a size x and a byte b, + that will be repeated x times. + + Below are example source and target windows and the delta + instructions that encode the target window in terms of the source + window. + + 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, z + + Thus, the first letter 'a' in the target window is at location 16 in + the superstring. Note that the fourth instruction, "COPY 12, 24", + copies data from T itself since address 24 is position 8 in T. This + instruction also shows that it is fine to overlap the data to be + copied with the data being copied from, as long as the latter starts + earlier. This enables efficient encoding of periodic sequences, + i.e., sequences with regularly repeated subsequences. The RUN + instruction is a compact way to encode a sequence repeating the same + byte even though such a sequence can be thought of as a periodic + sequence with period 1. + + To reconstruct the target window, one simply processes one delta + instruction at a time and copies the data, either from the source + window or the target window being reconstructed, based on the type of + the instruction and the associated address, if any. + +4. Delta File Organization + + A Vcdiff delta file starts with a Header section followed by a + sequence of Window sections. The Header section includes magic bytes + to identify the file type, and information concerning data processing + beyond the basic encoding format. The Window sections encode the + target windows. + + Below is the overall organization of a delta file. The indented + items refine the ones immediately above them. An item in square + brackets may or may not be present in the file depending on the + information encoded in the Indicator byte above it. + + + + + + + +Korn, et. al. Standards Track [Page 6] + +RFC 3284 VCDIFF June 2002 + + + 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 + + Each delta file starts with a header section organized as below. + Note the convention that square-brackets enclose optional items. + + 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] + + + + + + + + +Korn, et. al. Standards Track [Page 7] + +RFC 3284 VCDIFF June 2002 + + + The first three Header bytes are the ASCII characters 'V', 'C' and + 'D' with their most significant bits turned on (in hexadecimal, the + values are 0xD6, 0xC3, and 0xC4). The fourth Header byte is + currently set to zero. In the future, it might be used to indicate + the version of Vcdiff. + + The Hdr_Indicator byte shows if there is any initialization data + required to aid in the reconstruction of 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_CODETABLE + + If bit 0 (VCD_DECOMPRESS) is non-zero, this indicates that 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 is given next. If + this bit is zero, the compressor ID byte is not included. + + If bit 1 (VCD_CODETABLE) is non-zero, this indicates that an + application-defined code table is to be used for decoding the delta + instructions. This table itself is compressed. The length of the + data comprising this compressed code table and the data follow next. + Section 7 discusses application-defined code tables. If this bit is + zero, the code table data length and the code table data are not + included. + + If both bits are set, then the compressor ID byte is included before + the code table data length and the code table data. + +4.2 The Format of a Window Section + + Each Window section is organized as follows: + + Win_Indicator - byte + [Source segment length] - integer + [Source segment position] - integer + The delta encoding of the target window + + + + + + +Korn, et. al. Standards Track [Page 8] + +RFC 3284 VCDIFF June 2002 + + + Below are the details of the various items: + + Win_Indicator: + This byte is a set of bits, as shown: + + 7 6 5 4 3 2 1 0 + +-+-+-+-+-+-+-+-+ + | | | | | | | | | + +-+-+-+-+-+-+-+-+ + ^ ^ + | | + | +-- VCD_SOURCE + +---- VCD_TARGET + + If bit 0 (VCD_SOURCE) is non-zero, this indicates that a + segment of data from the "source" file was used as the + corresponding source window of data to encode the target + window. The decoder will use this same source data segment to + decode the target window. + + If bit 1 (VCD_TARGET) is non-zero, this indicates that a + segment of data from the "target" file was used as the + corresponding source window of data to encode the target + window. As above, this same source data segment is 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 to indicate respectively, the length and 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 these two + integers are not 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_SOURCE or + VCD_TARGET was set) or by itself if no source window is + specified. This data format is discussed next. + + + + + + + + + +Korn, et. al. Standards Track [Page 9] + +RFC 3284 VCDIFF June 2002 + + +4.3 The Delta Encoding of a Target Window + + The delta encoding of a target window is organized as follows: + + 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 bytes + + Length of the delta encoding: + This integer gives the total number of remaining bytes that + comprise 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 indicates 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_ADDRCOMP + + VCD_DATACOMP: bit value 1. + VCD_INSTCOMP: bit value 2. + VCD_ADDRCOMP: bit value 4. + + + + + + +Korn, et. al. Standards Track [Page 10] + +RFC 3284 VCDIFF June 2002 + + + As discussed, the delta encoding consists of COPY, ADD and RUN + instructions. The ADD and RUN instructions have accompanying + unmatched data (that is, data that does not specifically match + any data in the source window or in some earlier part of the + target window) and the COPY instructions have addresses of + where the matches occur. OPTIONALLY, these types of data MAY + be further compressed using a secondary compressor. Thus, + Vcdiff separates the encoding of the delta instructions into + three parts: + + a. The unmatched data in the ADD and RUN instructions, + b. The delta instructions and 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. The bit positions 0 (VCD_DATACOMP), 1 + (VCD_INSTCOMP), and 2 (VCD_ADDRCOMP) respectively indicate, if + non-zero, that the corresponding parts are 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 of data storing + the unmatched data accompanying the ADD and RUN instructions. + + Length of instructions section: + This is the length (in bytes) of the delta instructions and + 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. + + + + + + +Korn, et. al. Standards Track [Page 11] + +RFC 3284 VCDIFF June 2002 + + +5. Delta Instruction Encoding + + The delta instructions described in Section 3 represent the results + of string matching. For many data differencing applications in which + the changes between source and target data are small, any + straightforward representation of these instructions would be + adequate. However, for applications including differencing of binary + files or data compression, it is important to encode these + instructions well to achieve good compression rates. The keys to + this achievement is to efficiently encode the addresses of COPY + instructions and the sizes of all delta instructions. + +5.1 Address Encoding Modes of COPY Instructions + + Addresses of COPY instructions are locations of matches and often + occur close by or even exactly equal to one another. This is because + data in local regions are often replicated with minor changes. In + turn, this means that coding a newly matched address against some + recently matched addresses can be beneficial. To take advantage of + this phenomenon and encode addresses of COPY instructions more + efficiently, the Vcdiff data format supports the use of two different + types of address caches. Both the encoder and decoder maintain these + caches, so that decoder's caches remain 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 to the near cache. New entries to + the near cache are always inserted in the next_slot index, which + maintains 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 repeated encoding of the + exact same address. + + By default, the parameters s_near and s_same are respectively set to + 4 and 3. 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 properly set up its own caches. + + 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. + + + + + +Korn, et. al. Standards Track [Page 12] + +RFC 3284 VCDIFF June 2002 + + + Each time a COPY instruction is processed by the encoder or decoder, + the implementation's caches are updated as follows, 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. The next_slot index is then 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 clear the above description, below are examples of cache data + structures and 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; + } + + + +Korn, et. al. Standards Track [Page 13] + +RFC 3284 VCDIFF June 2002 + + +5.3 Encoding of COPY instruction addresses + + The address of a COPY instruction is encoded using different modes, + depending on the type of cached address 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 (i.e., 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. Below 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 value "here - 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 value "addr - 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 that "addr == + same[(m - (s_near+2))*256 + b]". + +5.4 Example code for encoding and decoding of COPY instruction addresses + + We show example algorithms below to demonstrate the use of address + modes more clearly. The encoder has the freedom to choose address + modes, the sample addr_encode() algorithm merely shows one way of + picking the address mode. The decoding algorithm addr_decode() will + uniquely decode addresses, regardless of the encoder's algorithm + choice. + + Note that the address caches are updated immediately after an address + is encoded or decoded. In this way, the decoder is always + synchronized with the encoder. + + + + + + + + + + + + + +Korn, et. al. Standards Track [Page 14] + +RFC 3284 VCDIFF June 2002 + + + 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 */ + } + + Note that the addr_encode() algorithm chooses the best address mode + using a local optimization, but that may 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(), obtain + from the "Addresses section for COPYs" (Section 4.3), an integer or a + byte, respectively. These utilities will not be described here. We + simply recall that an integer is represented as a compact variable- + sized string of bytes, as described in Section 2 (i.e., base 128). + + + + + + + + + + + + + + +Korn, et. al. Standards Track [Page 15] + +RFC 3284 VCDIFF June 2002 + + + 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 + + Matches are often short in lengths and separated by small amounts of + unmatched data. That is, the lengths of COPY and ADD instructions + are often small. This is particularly true of binary data such as + executable files or structured data, such as HTML or XML. In such + cases, compression can be improved by combining the encoding of the + sizes and the instruction types, as well as combining the encoding of + adjacent delta instructions with sufficiently small data sizes. + Effective choices of when to perform such combinations depend on many + factors including the data being processed and the string matching + algorithm in use. For example, if many COPY instructions have the + same data sizes, it may be worthwhile to encode these instructions + more compactly than others. + + The Vcdiff data format is designed so that a decoder does not need to + be aware of the choices made in encoding algorithms. This is + achieved with the notion of an "instruction code table", containing + 256 entries. Each entry defines, either a single delta instruction + or a pair of instructions that have been combined. Note that the + code table itself only exists in main memory, not in the delta file + (unless using an application-defined code table, described in Section + 7). The encoded data simply includes the index of each instruction + and, since there are only 256 indices, each index can be represented + as a single byte. + + + + + + + +Korn, et. al. Standards Track [Page 16] + +RFC 3284 VCDIFF June 2002 + + + Each instruction code entry contains six fields, each of which is a + single byte with an unsigned value: + + +-----------------------------------------------+ + | inst1 | size1 | mode1 | inst2 | size2 | mode2 | + +-----------------------------------------------+ + + Each triple (inst,size,mode) defines a delta instruction. The + meanings of these fields are as follows: + + inst: An "inst" field can have one of the four values: NOOP (0), + ADD (1), RUN (2) or COPY (3) to indicate the instruction + types. NOOP means that no instruction is specified. In + this case, both the corresponding size and mode fields will + be zero. + + size: A "size" field is zero or positive. A value zero means that + the size associated with 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. Note that since the size is + restricted to a byte, the maximum value for any instruction + with size implicitly defined in the code table is 255. + + mode: A "mode" field is significant only when the associated delta + instruction is a COPY. It defines the mode used to encode + the associated addresses. For other instructions, this is + always zero. + +5.6 The Code Table + + Following the discussions on address modes and instruction code + tables, we define a "Code Table" to have the data below: + + 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" in which s_near is 4 and + s_same is 3. Thus, 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. + + + + + + + + +Korn, et. al. Standards Track [Page 17] + +RFC 3284 VCDIFF June 2002 + + + 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 depicted above, in a compact + representation that we use only for descriptive purposes. See + section 7 for the specification of how an instruction code table is + represented in the Vcdiff encoding format. In the depiction, a zero + value for size indicates that the size is separately coded. The mode + of non-COPY instructions is represented as 0, even though they are + not used. + + In the depiction, each numbered line represents one or more entries + in the actual instruction code table (recall that an entry in the + instruction code table may represent up to two combined delta + instructions.) The last column ("INDEX") shows which index value, or + range of index values, of the entries are covered by that line. (The + notation [i,j] means values from i through j, inclusively.) The + first 6 columns of a line in the depiction, describe the pairs of + instructions used for the corresponding index value(s). + + If a line in the depiction includes a column entry using the [i,j] + notation, this means that the line is instantiated for each value in + the range from i to j, inclusively. The notation "0, [i,j]" means + that the line is instantiated for the value 0 and for each value in + the range from i to j, inclusively. + + + + +Korn, et. al. Standards Track [Page 18] + +RFC 3284 VCDIFF June 2002 + + + If a line in the depiction includes more than one entry using the + [i,j] notation, implying a "nested loop" to convert the line to a + range of table entries, the first such [i,j] range specifies the + outer loop, and the second specifies the inner loop. + + The below examples should make clear the above description: + + Line 1 shows the single RUN instruction with index 0. As 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 (i.e., the 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 will not be separately + encoded.) + + Following the single ADD instructions are the single COPY + instructions ordered by their address encoding modes. For example, + line 11 shows the COPY instructions with mode 8, i.e., the last of + the same cache. In this case, the COPY instruction with size field 0 + has index 147. Again, the actual size of this instruction will be + coded separately. + + Lines 12 to 21 show the pairs of instructions that are combined + together. For example, line 12 depicts the 12 entries in which an + ADD instruction is combined with an immediately following COPY + instruction. The entries with indices 163, 164, 165 represent the + pairs in which 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 COPY instructions have size 4 with mode ranging from 0 to 8 and + all the ADD instructions have size 1. Thus, 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 choice of the minimum size 4 for COPY instructions in the default + code table was made from experiments that showed that excluding small + matches (less then 4 bytes long) improved the compression rates. + + + + + + + + + +Korn, et. al. Standards Track [Page 19] + +RFC 3284 VCDIFF June 2002 + + +6. Decoding a Target Window + + Section 4.3 discusses that the delta instructions and associated data + are encoded in three arrays of bytes: + + Data section for ADDs and RUNs, + Instructions and sizes section, and + Addresses section for COPYs. + + Further, these data sections may have been further compressed by some + secondary compressor. Assuming that any such compressed data has + been decompressed so that we now have three arrays: + + inst: bytes coding the instructions and sizes. + data: unmatched data associated with ADDs and RUNs. + addr: bytes coding the addresses of COPYs. + + These arrays are organized as follows: + + 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 as follows. The entry with the given "index" + in the instruction code table potentially defines two delta + instructions. If the first delta instruction is not a + VCD_NOOP and its size is zero, then size1 MUST be present. + Otherwise, size1 MUST be omitted and the size of the + instruction (if it is not VCD_NOOP) is as defined in the + table. The presence or absence of size2 is defined + similarly with respect to 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 as described in Section 2 (i.e., base + 128). However, since the same cache emits addresses in the + range [0,255], same cache addresses are always encoded as a + single byte. + + To summarize, each tuple in the "inst" array includes an index to + some entry in the instruction code table that determines: + + a. Whether one or two instructions were encoded and their types. + + b. If the instructions have their sizes encoded separately, these + sizes will follow, in order, in the tuple. + + + + + +Korn, et. al. Standards Track [Page 20] + +RFC 3284 VCDIFF June 2002 + + + c. If the instructions have accompanying data, i.e., ADDs or RUNs, + their data will be in the array "data". + + d. Similarly, if the instructions are COPYs, the coded addresses are + found in the array "addr". + + The decoding procedure simply processes the arrays by reading one + code index at a time, looking up the corresponding instruction code + entry, then consuming the respective sizes, data and addresses + following the directions in this entry. In other words, the decoder + maintains an implicit next-element pointer for each array; + "consuming" an instruction tuple, data, or address value implies + incrementing the associated pointer. + + For example, if during the processing of the target window, the next + unconsumed tuple in the inst array has an index value of 19, then the + first instruction is a COPY, whose size is found as the immediately + following integer in the inst array. Since the mode of this COPY + instruction is VCD_SELF, the corresponding address is found by + consuming the next integer in the addr array. The data array is left + intact. As the second instruction for code index 19 is a NOOP, this + tuple is finished. + +7. APPLICATION-DEFINED CODE TABLES + + Although the default code table used in Vcdiff is good for general + purpose encoders, there are times when other code tables may perform + better. For example, to code a file with many identical segments of + data, it may be advantageous to have a COPY instruction with the + specific size of these data segments, so that the instruction can be + encoded in a single byte. Such a special code table MUST then be + encoded in the delta file so that the decoder can reconstruct it + before decoding the data. + + Vcdiff allows an application-defined code table to be specified in a + delta file with the following data: + + Size of near cache - byte + Size of same cache - byte + Compressed code table data + + The "compressed code table data" encodes the delta between the + default code table (source) and the new code table (target) in the + same manner as described in Section 4.3 for encoding a target window + in terms of a source window. This delta is computed using the + following steps: + + + + + +Korn, et. al. Standards Track [Page 21] + +RFC 3284 VCDIFF June 2002 + + + a. Convert the new instruction code table into a string, "code", of + 1536 bytes using the below steps in order: + + i. Add in order the 256 bytes representing the types of the first + instructions in the instruction pairs. + ii. Add in order the 256 bytes representing the types of the + second instructions in the instruction pairs. + iii. Add in order the 256 bytes representing the sizes of the first + instructions in the instruction pairs. + iv. Add in order the 256 bytes representing the sizes of the + second instructions in the instruction pairs. + v. Add in order the 256 bytes representing the modes of the first + instructions in the instruction pairs. + vi. Add in order the 256 bytes representing the modes of the + second instructions in the instruction pairs. + + b. Similarly, convert the default code table into a string "dflt". + + c. Treat the string "code" as a target window and "dflt" as the + corresponding source data and apply an encoding algorithm to + compute the delta encoding of "code" in terms of "dflt". This + computation MUST use the default code table for encoding the delta + instructions. + + The decoder can then reverse the above steps to decode the compressed + table data using the method of Section 6, employing the default code + table, to generate the new code table. Note that the decoder does + not need to know about the details of the encoding algorithm used in + step (c). It is able to decode the new code table because the Vcdiff + format is independent from the choice of encoding algorithm, and + because the encoder in step (c) uses the known, default code table. + +8. Performance + + The encoding format is compact. For compression only, using the LZ- + 77 string parsing strategy and without any secondary compressors, the + typical compression rate is better than Unix compress and close to + gzip. For differencing, the data format is better than all known + methods in terms of its stated goal, which is primarily decoding + speed and encoding efficiency. + + We compare the performance of 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 was used at its default + compression level. The Vcdiff data were obtained using the + Vcodex/Vcdiff software (Section 13). + + + + + +Korn, et. al. Standards Track [Page 22] + +RFC 3284 VCDIFF June 2002 + + + Below are the different Vcdiff runs: + + Vcdiff: vcdiff is used as a compressor only. + + Vcdiff-d: vcdiff is used as a differencer only. That is, it only + compares target data against source data. Since the files + involved are large, they are broken into windows. In this + case, each target window, starting at some file offset in the + target file, is compared against a source window with the same + file offset (in the source file). The source window is also + slightly larger than the target window to increase matching + opportunities. + + Vcdiff-dc: This is similar to Vcdiff-d, but vcdiff can also + compare target data against target data as applicable. Thus, + vcdiff both computes differences and compresses data. The + windowing algorithm is the same as above. However, the above + hint is recinded in this case. + + Vcdiff-dcw: This is similar to Vcdiff-dc but the windowing + algorithm uses a content-based heuristic to select a source + window that is more likely to match with a given target window. + Thus, the source data segment selected for a target window + often will not be aligned with the file offsets of this 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,543 + + The above table shows the raw sizes of the tar files and the sizes of + the compressed results. The differencing results in the gcc-2.95.2 + column were obtained by compressing gcc-2.95.2, given gcc-2.95.1. + The same results for the column gcc-2.95.3 were obtained by + compressing gcc-2.95.3, given gcc-2.95.2. + + Rows 2, 3 and 4 show that, for compression only, the compression rate + from Vcdiff is worse than gzip and better than compress. + + + + + + + +Korn, et. al. Standards Track [Page 23] + +RFC 3284 VCDIFF June 2002 + + + The last three rows in the column gcc-2.95.2 show that when two file + versions are very similar, differencing can give dramatically good + compression rates. Vcdiff-d and Vcdiff-dc use the same simple window + selection method of aligning by file offsets, but Vcdiff-dc also does + compression so its output is slightly smaller. Vcdiff-dcw uses a + content-based algorithm to search for source data that likely will + match a given target window. Although it does a good job, the + algorithm does not always find the best matches, which in this case, + are given by the simple algorithm of Vcdiff-d. As a result, the + output size for Vcdiff-dcw is slightly larger. + + The situation is reversed in the gcc-2.95.3 column. Here, the files + and their contents were sufficiently rearranged or changed between + the making of the gcc-2.95.3.tar archive and the gcc-2.95.2 archive + so that the simple method of aligning windows by file offsets no + longer works. As a result, Vcdiff-d and Vcdiff-dc do not perform + well. By allowing compression, along with differencing, Vcdiff-dc + manages to beat Vcdiff-c, which does compression only. The content- + based window matching algorithm in Vcdiff-dcw is effective in + matching the right source and target windows so that Vcdiff-dcw is + the overall winner. + +9. Further Issues + + This document does not address a few issues: + + Secondary compressors: + As discussed in Section 4.3, certain sections in the delta + encoding of a window may be further compressed by a secondary + compressor. In our experience, the basic Vcdiff format is + adequate for most purposes so that secondary compressors are + seldom needed. In particular, for normal use of data + differencing, where the files to be compared have long stretches + of matches, much of the gain in compression rate is already + achieved by normal string matching. Thus, the use of secondary + compressors is seldom needed in this case. However, for + applications beyond differencing of such nearly identical files, + secondary compressors may be needed to achieve maximal compressed + results. + + Therefore, we recommend leaving the Vcdiff data format defined as + in this document so that the use of secondary compressors can be + implemented when they become needed in the future. The formats of + the compressed data via such compressors or any compressors that + may be defined in the future are left open to their + implementations. These could include Huffman encoding, arithmetic + encoding, and splay tree encoding [8,9]. + + + + +Korn, et. al. Standards Track [Page 24] + +RFC 3284 VCDIFF June 2002 + + + Large file system vs. small file system: + 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. There is a possibility that the encoding was + computed on a system supporting much larger files than in a system + where the data may be decoded (e.g., 64-bit file systems vs. 32- + bit file systems). In that case, some target data may not be + recoverable. This problem could afflict any compression format, + and ought to be resolved with a generic negotiation mechanism in + the appropriate protocol(s). + +10. Summary + + We have described Vcdiff, a general and portable encoding format for + compression and differencing. The format is good in that it allows + implementing a decoder without knowledge of the encoders. Further, + ignoring the use of secondary compressors not defined within the + format, the decoding algorithms run in linear time and requires + working space proportional to window size. + +11. Acknowledgements + + Thanks are due to Balachander Krishnamurthy, Jeff Mogul and Arthur + Van Hoff who provided much encouragement to publicize Vcdiff. In + particular, Jeff helped in clarifying the description of the data + format presented here. + +12. Security Considerations + + Vcdiff only provides a format to encode compressed and differenced + data. It does not address any issues concerning how such data are, + in fact, stored in a given file system or the run-time memory of a + computer system. Therefore, we 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 according license is + accessible at the below URL: + + http://www.research.att.com/sw/tools + + + + + +Korn, et. al. Standards Track [Page 25] + +RFC 3284 VCDIFF June 2002 + + +14. Intellectual Property Rights + + The IETF has been notified of intellectual property rights claimed in + regard to some or all of the specification contained in this + document. For more information consult 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; neither does it represent that it + has made any effort to identify any such rights. Information on the + IETF's procedures with respect to 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 made 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. + + + + + +Korn, et. al. Standards Track [Page 26] + +RFC 3284 VCDIFF June 2002 + + + [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. + + + + + + + + + + + + + + + +Korn, et. al. Standards Track [Page 27] + +RFC 3284 VCDIFF June 2002 + + +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 + + + + + + + + + + + + + + +Korn, et. al. Standards Track [Page 28] + +RFC 3284 VCDIFF June 2002 + + +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. + + + + + + + + + + + + + + + + + + + +Korn, et. al. Standards Track [Page 29] + |