[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits] [IPR]

Versions: 00 01 02 03 04 05 RFC 3284

Network Services Research Lab                  David Korn  and  Kiem-Phong Vo
                                                                    AT&T Labs
                                               Submission:     March 12, 2001
                                               Expiration: September 12, 2001


        The VCDIFF Generic Differencing and Compression Data Format
                       <draft-korn-vcdiff-03.txt>


Status of this Memo

    This document is an Internet-Draft and is in full conformance
    with all provisions of Section 10 of RFC2026.

    Internet-Drafts are working documents of the Internet Engineering
    Task Force (IETF), its areas, and its working groups.  Note that
    other groups may also distribute working documents as
    Internet-Drafts.

    Internet-Drafts are draft documents valid for a maximum of six
    months and may be updated, replaced, or obsoleted by other
    documents at any time.  It is inappropriate to use Internet-
    Drafts as reference material or to cite them other than as
    "work in progress."

    The list of current Internet-Drafts can be accessed at
    http://www.ietf.org/ietf/1id-abstracts.txt

    The list of Internet-Draft Shadow Directories can be accessed at
    http://www.ietf.org/shadow.html.

Abstract

    This memo describes a general and efficient data format suitable
    for encoding compressed and/or differencing data so that they can
    be easily transported among computers.

Table of Contents:

    1.  EXECUTIVE SUMMARY ............................................  1
    2.  ALGORITHM CONVENTIONS ........................................  3
    3.  DELTA INSTRUCTIONS ...........................................  4
    4.  VCDIFF ENCODING FORMAT .......................................  5
    5.  INSTRUCTION CODE TABLES ...................................... 14
    6.  FURTHER ISSUES ............................................... 16
    7.  SUMMARY ...................................................... 17
    8.  ACKNOWLEDGEMENTS ............................................. 17
    9.  SECURITY CONSIDERATIONS ...................................... 17
   10.  REFERENCES ................................................... 18
   11.  AUTHOR'S ADDRESS ............................................. 18
   12.  APPENDIX: SECTION LAY-OUT IN A DELTA FILE..................... 19
   13.  EXPIRATION DATE .............................................. 19




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

RFC 3   VCDIFF Generic Differencing and Compression Data 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 because 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 style
    compressors [2], and the block-move technique of Tichy [3].  Loosely
    speaking, this works as follows:

        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 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].  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
    windows of the same size with corresponding addresses across source and
    target files.

    String matching and windowing algorithms have large 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 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 resspect. Their storage formats are closely intertwined
    with the implemented string matching and windowing algorithms.

    The encoding format Vcdiff proposed here addresses the above issues.
    Vcdiff achieves the below characteristics:

        Output compactness:
            The basic encoding format compactly represents compressed or delta
            files. Applications can further extend the basic encoding format with
            "secondary encoders" (e.g., a Huffman or arithmetic encoder) 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

                                   -2-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


            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 proportional to the size of the target file and uses space
            proportional to the maximal window size.

    The Vcdiff data format and the algorithms for decoding data shall be
    described next.  Since Vcdiff treats compression as a special case of
    differencing, we shall use the term "delta file" to indicate the
    compressed output for both cases.


2. ALGORITHM CONVENTIONS

    Algorithms to encode and decode the Vcdiff data format will be presented
    in the ANSI-C language. To simplify the presentation, we shall generally
    omit error checking and resource allocation and deallocation. In addition,
    the below conventions will be observed:

        a. Tokens with all upper cases letters will be C macros.
        b. Variables with capitalized names are global.
        c. Code fragments will be presented with line numbers to be used
           in the subsequent COMMENTS sections.

    Data will be encoded in byte units.  For portability, control data
    generated by Vcdiff shall be limited to the lower eight bits of a byte
    even on machines with larger bytes. The bits in a byte are named from
    right to left so that the first bit has the lowest value, 1<<0 or 1,
    and the eighth bit has value 1<<7 or 128.

    To facilitate the algorithms, we shall assume a few types and functions
    for I/O on streams.  To be definite, we shall use interfaces similar to
    that provided in the Sfio library [6].  Below are descriptions of some of
    these types and functions. Others can be found in reference [6].

        uchar_t:
            This is the type "unsigned char". When coded in a delta file,
            this takes a single byte.

        uint_t:
            This is some unsigned integer type that is at least as large
            as an "unsigned int" and should be large enough to hold file
            offsets.  In general, unsigned integers are coded in a portable
            variable-sized format to be described in Section 4.2.

        Sfio_t:
            This is the type of a stream.

        Sfio_t* sfstropen(uchar_t* buf, int n):
            This is not an Sfio function but it can be easily implemented
            on top of the Sfio primitive sfnew(). sfstropen() creates a stream
            from a given buffer with a given size. We shall assume that such
            a stream is both readable and writable. As with Sfio, a stream
            opened for writing will extend its buffer as necessary to
            accommodate output data.





                                   -3-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001



3.  DELTA INSTRUCTIONS

    A target file is partitioned into non-overlapping sections or windows
    to be processed separately. A target window T of length t may be
    compared against some source data segment S of length s.  Such a source
    data segment may come from some earlier part of the target file or
    it may come from the source file, if there is one. It is assumed that
    there is sufficient memory so that both T and S can be processed
    in main memory.

    For string processing, we treat S and T as substrings of a superstring U
    formed by concatenating T and S like this:

        S[0]S[1]...S[s-1]T[0]T[1]...T[t-1]

    The index of a byte in S or T is referred to by its location in U.
    For example, the index of T[i] is s+i.

    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 s and a sequence of
            s bytes to be copied.

        COPY: This instruction has two arguments, a size s 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.

        RUN: This instruction has two arguments, a size s and a byte b that
            will be repeated s times.

    Below are example source and target strings and the delta instructions
    that encode the target string in terms of the source string.


        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 string will be 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.
    In addition, some part of the data to be copied is reconstructed along
    with the copying.  This allows 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.





                                   -4-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


4.  VCDIFF ENCODING FORMAT

    A large target file is partitioned into non-overlapping sections called
    "target windows". Window sizes should be chosen so that each window can
    be completely processed in memory during both encoding and decoding.
    A target window may be compared against some source data segment or none.
    For compression, such a source segment would be from some earlier part of
    the target file while, for differencing, it is often from the source file.


4.1 Delta File Layout

    A Vcdiff delta file is organized into sections as follows:

        Header
        Window 1
        Window 2
        ...

    The header of a delta file includes magic bytes to identify file
    type and information concerning data processing beyond the basic
    encoding format. The window sections encode the target windows.


4.1.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 - uchar_t
        Header2 - uchar_t
        Header3 - uchar_t
        Header4 - uchar_t
        Indicator - uchar_t
        [Secondary compressor - uchar_t]
        [Length of instruction code table data - uint_t]
        [Instruction code table data]


   The first four Header bytes are defined below. The first three bytes
   are the ASCII characters 'V', 'C' and 'D' or-ed with the eighth bit.
   The fourth byte is currently set to zero. In the future, it may be
   used to indicate the version of Vcdiff.

        #define VCD_HEADER1    (0x56 | (1<<7))  /* 'V' | (1<<7) */
        #define VCD_HEADER2    (0x43 | (1<<7))  /* 'C' | (1<<7) */
        #define VCD_HEADER3    (0x44 | (1<<7))  /* 'D' | (1<<7) */
        #define VCD_HEADER4    (0)              /* version      */


    The Indicator byte shows if there are any initialization data
    required to aid in the reconstruction of data in the Window sections.
    This byte is composed from some subset of the following bits:

        #define VCD_DECOMPRESS (1<<0)
        #define VCD_CODETABLE  (1<<1)


    The bit VCD_DECOMPRESS indicates that a secondary compressor may have
    been used to further compress certain parts of the delta data as described

                                   -5-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


    in Section 4.1.3. In that case, the index of the decompressor is given
    in a subsequent byte.

    The Length of instruction code table and the Instruction code table
    data sections are in the delta file only if the bit VCD_CODETABLE is
    on. The processing of this table will be described in Section 5.


4.1.2 The Format of a Window

    Each window is organized as follows:

        Indicator - uchar_t
        [Source segment size - uint_t]
        [Source segment position - uint_t]
        Length of the delta encoding - uint_t
        The delta encoding

    Below are the detail of the various items:

        Indicator:
            This byte should be zero or one of the below values:

                #define VCD_SRCWINDOW   (1<<0)
                #define VCD_TARWINDOW   (1<<1)

            The value VCD_SRCWINDOW indicates that there is a segment
            of data from the source file used for differencing against
            the current window.  Likewise, VCD_TARWINDOW indicates a
            similar segment of data from the target file. In these cases,
            encoded next are two integers to indicate respectively
            the size and position of the data segment in the relevant file.
            If this byte is zero, the window was compressed without using
            a source segment.

        Length of the delta encoding:
            This is a variable-sized integer that tells the length of
            the delta encoding data for this window.

        The delta encoding:
            This contains the data representing the delta encoding.

4.1.3 The Delta Encoding

    The delta encoding of a window is organized as follows:

        Length of target window - uint_t
        Indicator - uchar_t
        Length of ADD and RUN data section - uint_t
        Length of instruction section - uint_t
        Length of COPY address section - uint_t
        Data section for ADD and RUN instructions
        Instructions section
        Addresses section for COPY instructions

        Length of target window:
            This is a variable-sized integer indicating the size of the
            target window. The decoder can use this value to allocate
            the necessary memory to decode the window.


                                   -6-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


        Indicator:
            This byte is composed from some subset of the below bits:

                #define VCD_DATACOMP    (1<<0)
                #define VCD_INSTCOMP    (1<<1)
                #define VCD_ADDRCOMP    (1<<2)

            The delta encoding is separated into three parts: the unmatched
            data accompanying the ADD and RUN instructions, the coding of
            the instructions, and the encoded addresses of the COPY
            instructions. If the bit VCD_DECOMPRESS (Section 4.1.1) was on,
            each of these sections may have been compressed using the
            given secondary compressor. The above bits indicate these cases.

        Length of ADD and RUN data section:
            This is the length of the section of data storing the unmatched
            data accompanying the ADD and RUN instructions (which may have
            been compressed using a secondary compressor as discussed).

        Length of instruction section:
            This is similar to the above but for the delta instructions.

        Length of COPY address section:
            This is similar to the above but for the addresses of the COPY
            instructions.

        Data section for ADD and RUN instructions:
            This section contains the unmatched data for the ADD and RUN
            instructions (which may have been further compressed).

        Instructions section:
            This section contains the instructions.

        Addresses section for COPY instructions:
            This section contains the addresses of the COPY instructions.


4.1.4 Processing a Delta File

    Below is the basic algorithm to decode a delta file:

     1. sfgetc(Delta);
     2. sfgetc(Delta);
     3. sfgetc(Delta);
     4. sfgetc(Delta);

     5. Compressor = -1;
     6. Codetable = Dflttable;
     7. if((indi = sfgetc(Delta)) != 0)
     8. {   if(indi & VCD_DECOMPRESS)
     9.          Compressor = sfgetc(Delta);
    10.     if(indi & VCD_CODETABLE)
    11.     {    n_tbl = sfgetu(Delta);
    12.          tbl = getdata(Delta, n_tbl, -1);
    13.          Codetable = gettable(tbl, n_tbl);
    14.     }
    15. }

    16. for(;;)
    17. {   if((indi = sfgetc(Delta)) < 0)

                                   -7-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


    18.          break;

    19.     if(indi != 0)
    20.     {    n_src = sfgetu(Delta);
    21.          p_src = sfgetu(Delta);
    22.          if(indi == VCD_TARWINDOW)
    23.               src = getdata(Target, n_src, p_src);
    24.          else src = getdata(Source, n_src, p_src);
    25.     }
    26.     else n_src = 0;

    27.     n_del = sfgetu(Delta);
    28.     del = getdata(Delta, n_del, -1);
    29.     n_tar = win_inflate(&tar, src, n_src, del, n_del);
    30.     sfwrite(Target, tar, n_tar);
    31. }

COMMENTS.

   1-4: These lines read the four magic header bytes that indicate
        the type of this file.
  5-15: These lines first initialize the indices of secondary encoders
        and code table to default values. Then, the initialization
        data, if any, is processed to reset these variables.
        The function getdata() reads from the given stream the segment of
        data at the given position or the current position (if this
        argument is -1). The function gettable() will be described later.
 16-31: These lines read window data and decode them.
 19-26: These lines determine if there is a source segment of data and read
        it from the indicated file.
 27-30: These lines read the delta encoding data, get processing space,
        call win_inflate() to decode target data, then write the results
        to the target file.


    Next is the function to recompute a target window:

     1. int win_inflate(uchar_t** tarp,
     2.             uchar_t* src, int n_src,
     3.             uchar_t* del, int n_del)
     4. {   int      n_tar, n_data, n_inst, n_addr;
     5.     uchar_t  ctrl, *tar, *data, *inst, *addr;
     6.     Sfio_t   *delf, *dataf, *instf, *addrf;

     7.     delf = sfstropen(del, n_del);

     8.     n_tar = sfgetu(delf);
     9.     ctrl  = sfgetc(delf);
    10.     n_data = sfgetu(del);
    11.     n_inst = sfgetu(del);
    12.     n_addr = sfgetu(del);

    13.     tar = malloc(n_tar);
    14.     data = getdata(delf, n_data, -1);
    15.     inst = getdata(delf, n_inst, -1);
    16.     addr = getdata(delf, n_addr, -1);

    17.     if(ctrl&VCD_DATACOMP)
    18.          n_data = decompress(Compressor, data, n_data, &data);
    19.     if(ctrl&VCD_INSTCOMP)

                                   -8-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


    20.          n_inst = decompress(Compressor, inst, n_inst, &inst);
    21.     if(ctrl&VCD_ADDRCOMP)
    22.          n_addr = decompress(Compressor, addr, n_addr, &addr);

    23.     dataf = sfstropen(data, n_data);
    24.     instf = sfstropen(inst, n_inst);
    25.     addrf = sfstropen(addr, n_addr);
    26.     win_decode(tar, n_tar, src, n_src, dataf, instf, addrf);

    27.     *tarp = tar;
    28.     return n_tar;
    29. }


COMMENTS.

     7: This line creates a stream to read the delta encoding data.
  8-16: These lines read the sizes of the various datasets, then allocate
        memory and read in data as necessary.
 17-22: These lines decompress the above data if necessary.  The function
        decompress() invokes the respective decompressor. It returns the
        size of the decompressed data while the decompressed data itself
        is returned via the last argument. See Section 6 for proposed
        values for Compressor.
 23-26: These lines call win_decode() (Section 4.4) to actually
        reconstruct target data.
 27-28: These lines return the reconstructed target data.




4.2 Encoding Integers Using a Variable-Sized Format

    Vcdiff encodes integer values using the variable-size format introduced
    in the Sfio library [6] for encoding unsigned values. The code presented
    below is not quite correct with respect to type handling as in Sfio but
    they show the ideas. The encoding treats an integer as a number in base
    128 so that each digit can be coded in one byte. The eighth bit of such
    a byte is the continuation bit. It is 1 if there are more digits to come
    or 0 if it is the last digit.



                        +---------------------+
                        | 11100000 | 00111001 |
                        +---------------------+
                          byte 0       byte 1

                                Table 1



    Table 1 shows the variable sized encoding of 12345.  The bytes in
    the encoding are presented in binary to make clear the use of
    the continuation bit. Omitting the continuation bit, the encoding
    of 12345 uses two bytes with values 96 and 57.





                                   -9-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


    Below are the algorithms:

     1. int sfputu(Sfio_t* f, uint_t v)
     2. {   uchar_t c[2*sizeof(uint_t)], *s;

     3.     s = &c[sizeof(c)-1];
     4.     *s = v & 127;
     5.     while((v >>= 7) != 0)
     6.          *--s = (v & 127) | (1<<7);

     7.     sfwrite(f, s, (&c[sizeof(c)]) - s);
     8.     return  &c[sizeof(c)]-s;
     9. }

    10. uint_t sfgetu(Sfio_t* f)
    11. {   uint_t b, v;

    12.     for(v = 0;; )
    13.     {    b = sfgetc(f);
    14.          v = (v << 7) | (b & 127);
    15.          if(!(b & 128) )
    16.               return v;
    17.     }
    18. }

COMMENTS.

     1: This line declares the formal arguments to sfputu(), a stream f
        to store the encoding and the value v to be encoded.
     2: This line declares an array large enough to store the encoding.
   4-6: These lines extract digits in base 128 and store them in the array.
        Note that the right-most digit is extracted first and does not
        carry a continuation bit.
   7-8: These lines write the encoding out to the given stream f and
        return the length of that encoding.
 10-18: These lines define the decoding algorithm.


4.3 Delta Instruction Coding Format

    Delta instructions are encoded as control bytes with associated data.
    Each control byte is an index into an instruction code table of 256
    entries. Below are the relevant data structures:

     1. typedef struct _vcdinst_s
     2. {   uchar_t    type;   /* instruction type           */
     3.     uchar_t    size;   /* >0 if size is coded here   */
     4.     uchar_t    mode;   /* address mode for COPYs     */
     5. } Vcdinst_t;

     6. typedef struct _vcdcode_s
     7. {   Vcdinst_t  inst1;  /* first instruction          */
     8.     Vcdinst_t  inst2;  /* second instruction         */
     9. } Vcdcode_t;

    10. typedef struct _vcdtable_s
    11. {   uchar_t    s_same; /* s_same*256 addresses       */
    12.     uchar_t    s_near; /* s_near addresses           */
    13.     Vcdcode_t  code[256]; /* the instruction codes   */
    14. } Vcdtable_t;

                                   -10-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001



COMMENTS.

   1-5: An instruction is defined by its type, the size of the
        associated data and, in the case of a COPY, the mode of
        how the address is encoded.
   6-9: As shown, a code in the range [0-255] can encode up to
        two instructions. The default Vcdiff code table uses this
        feature to merge adjacent ADD and COPY instructions with
        small sizes.
 10-14: These lines define the encoding table. Addresses may be
        encoded against two optional caches, same and near,
        to be described later.

    Below are the values identifying the instructions:

        #define VCD_NOOP  0      /* not an instruction       */
        #define VCD_ADD   1      /* an ADD instruction       */
        #define VCD_RUN   2      /* a  RUN instruction       */
        #define VCD_COPY  3      /* a COPY instruction       */

    Each instruction has a size s of the data involved.  If the field
    Vcdinst_t.size is non-zero, it is the value for s.  Otherwise,
    s is encoded next in the instruction dataset as a variable-sized
    integer.  If the instruction is a COPY, the copy address will follow
    next in the instruction dataset. Its encoding depends on some
    addressing scheme to be discussed next.

    A COPY address is encoded using different modes as indicated by
    the values of the field Vcdinst_t.mode. Vcdiff allows this field
    to have values in the range [0-15]. The first two values are:

        #define VCD_SELF  0
        #define VCD_HERE  1

    If Vcdtable_t.s_near is positive, the next s_near values
    indicate addresses coded using the "near" cache. Then,
    if Vcdtable_t.s_same is positive, the next s_same values indicate
    addresses coded using the "same" cache.

    Let "addr" be the address of a COPY instruction and "here" the
    current location in the target data. During decoding a delta
    encoding data stream, the address modes have the below meanings:

        VCD_SELF: addr is encoded separately in the next variable-sized
            integer.

        VCD_HERE: Let i be the next variable-sized integer. Then, addr
            is here-i.

        Near cache: The "near" cache keeps s_near addresses. Let m be
            the mode of the instruction and i the next variable-sized
            integer. In addition, let n be m - (VCD_HERE+1).
            Then addr is near[m] + i.

        Same cache: The "same" cache keeps s_same*256 addresses.
            Let m be the mode (Vcdinst_t.mode) of the instruction and
            b the next byte. In addition, let n be m - (VCD_HERE+1+s_near).
            Then, addr is same[m*256 + b].


                                   -11-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001



    Below are the algorithms to maintain address caches.

     1. typedef struct _cache_s
     2. {   int*  near;      /* array of size s_near        */
     3.     int   s_near;
     4.     int   n;         /* the circular index for near */
     5.     int*  same;      /* array of size s_same*256    */
     6.     int   s_same;
     7. } Cache_t;

     8. Cache_t* cache_open(int s_near, int s_same)
     9. {   int   i;
    10.     Cache_t* ka = malloc(sizeof(Cache_t));
    11.     ka->near = malloc(s_near*256*sizeof(int));
    12.     ka->same = malloc(s_same*sizeof(int));
    13.     ka->s_near = s_near;
    14.     ka->s_same = s_same;

    15.     for(i = 0; i < ka->s_near; ++i)
    16.          ka->near[i] = 0;
    17.     for(i = 0; i < ka->s_same*256; ++i)
    18.          ka->same[i] = 0;
    19.     ka->n = 0;
    20. }

    21. cache_update(Cache_t* ka, uint_t addr)
    22. {   if(ka->s_same > 0)
    23.         ka->same[addr % (ka->s_same*256)] = addr;
    24.     if(ka->s_near > 0)
    25.     {   ka->near[ka->n] = addr;
    26.         if((ka->n += 1) >= ka->s_near)
    27.             ka->n = 0;
    28.     }
    29. }

COMMENTS.

   1-7: These lines define the caches.
  8-20: These lines create a cache with addresses initialized to zero.
 21-29: These lines update the caches given an address.  Note that
        the "near" cache is updated in a round-robin manner.


    Below is the function to encode a COPY address:

     1. int addr_encode(Cache_t* ka, int addr, int here, int* mode)
     2. {   int  i, d, bestd, bestm;

     3.     bestd = addr; bestm = VCD_SELF;

     4.     if(sfulen(d = here-addr) < sfulen(bestd))
     5.         { bestd = d; bestm = VCD_HERE; }

     6.     for(i = 0; i < ka->s_near; ++i)
     7.     {   if((d = addr - ka->near[i] < 0)
     8.             continue;
     9.         if(sfulen(d) < sfulen(bestd))
    10.             { bestd = d; bestm = VCD_HERE+1 + i; }
    11.     }

                                   -12-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001



    12.     if(sfulen(bestd) > 1 && ka->s_same > 0 &&
    13.        ks->same[d = addr%(ka->s_same*256)] == addr)
    14.         { bestd = d; bestm = (VCD_HERE+1) + ka->s_near + d/256; }

    15.     cache_update(ka,addr);
    16.     *mode = bestm;
    17.     return bestd;
    18. }

COMMENTS.

     1: This lines declare the formal arguments. "addr" is the address
        to be encoded. "here" is the current location in the target data.
        "mode" is used to return the address mode. The encoded address
        itself is returned by the function.
  3-11: "addr" is encoded as one of VCD_SELF, VCD_HERE or some "near" mode
        depending on which addressing scheme uses the least space.
        The sfulen() function computes the number of bytes required to encode
        a given integer.
 12-14: If the coded address based on the above schemes still use more than
        one byte, the "same" cache is used to see if "addr" can be encoded
        in a single byte.
    15: This line updates the address caches.


    Below is the function to decode a COPY address:

     1. int addr_decode(Cache_t* ka, int here, int type, Sfio_t* addrf)
     2. {   int  addr, m;

     3.     if(type == VCD_SELF)
     4.          addr = sfgetu(addrf);
     5.     else if(type == VCD_HERE)
     6.          addr = here - sfgetu(addrf);
     7.     else if((m = type - (VCD_HERE+1)) >= 0 && m < ka->s_near)
     8.          addr = ka->near[m] + sfgetu(addrf);
     9.     else
    10.     {    m = type - (VCD_HERE+1 + ka->s_near);
    11.          addr = ka->same[m*256 + sfgetc(addrf)];
    12.     }

    13.     cache_update(ka, addr);
    14.     return addr;
    15. }


4.4 Decoding A Target Window

    The algorithm to decode a target window is as follows:

     1. win_decode(uchar_t* tar, int n_tar, uchar_t* src, int n_src,
     2.            Sfio_t* dataf, Sfio_t* instf, Sfio_t* addrf)
     3. {    uint_t      here, size, addr, i;
     4.      Vcdinst_t  *inst;
     5.      Vcdcode_t  *code, *table = Codetable->code;
     6.      Vcdcache_t *ka = cache_open(Codetable->s_near,Codetable->s_same);

     7.      for(here = 0; here < n_tar; )
     8.      {    code = &table[sfgetc(instf)];

                                   -13-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


     9.           for(i = 1; i <= 2; ++i)
    10.           {    inst = i == 1 ? &code->inst1 : &code->inst2;
    11.                if(inst->type == VCD_NOOP)
    12.                     continue;
    13.                if((size = inst->size) == 0)
    14.                     size = sfgetu(instf);
    15.                if(inst->type == VCD_ADD)
    16.                {    for(; size > 0; --size)
    17.                          tar[here++] = sfgetc(dataf);
    18.                }
    19.                else if(inst->type == VCD_RUN)
    20.                {    int  c = sfgetc(dataf);
    21.                     for(; size > 0; --size)
    22.                          tar[here++] = c;
    23.                }
    24.                else if(inst->type == VCD_COPY)
    25.                {    uchar_t* from;
    26.                     addr = addr_decode(&ka,here,inst->mode,addrf);
    27.                     from = addr < nsrc ? src+addr : tar+addr-nsrc;
    28.                     for(; size > 0; --size)
    29.                          tar[here++] = *from++;
    30.                }
    31.           }
    32.      }
    33. }

COMMENTS.

     5: "table" is initialized to be the instruction code table to be used.
     6: This line initializes the address caches.
     8: This line reads a control byte from the instruction dataset and gets
        the corresponding code table to decode instructions.
  9-32: These lines process the given pair of delta instructions. Note that
        the data for VCD_ADD and VCD_RUN are read from the raw dataset.


5.  INSTRUCTION CODE TABLES

    Delta instructions are encoded based on some instruction code table.
    Vcdiff provides a default instruction code table. As noted in Section
    4.1.1, an application can change this table in the Header section of
    a delta file.

5.1 The Default Instruction Code Table

    A COPY instruction with small data size may use more encoding space than
    the data itself. Thus, it is good to require COPY instructions to have
    some minimum sizes. In turn, a code table can take advantage of such
    a requirement to enhance compactness. Vcdiff provides a default instruction
    code table with the below characteristics:

        s_near: the near cache has 4 entries.
        s_same: the same cache has 3*256 entries.
        COPY: the minimum size for a COPY is 4.

    Thus, there are 9 address modes for a COPY instruction. The first two
    are VCD_SELF and VCD_HERE. Following these are the 4 modes for addresses
    coded against the near cache. The last three modes are for addresses
    coded against the same cache.


                                   -14-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


    Table 2 below summarizes the code in the default table. The first 6
    columns describe the pairs of instructions per code and the last
    column shows the index range in the code table for these pairs.
    The single RUN instruction shown on the first row always encodes
    the size separately. The second row shows the single ADD instructions.
    The ADD instruction with size 0 (i.e., its size is coded separately
    as a variable-sized integer) has the code index 1. ADD instructions
    with sizes from 1 to 17 use code indices 2 to 18 and their sizes
    will not be separately encoded. The last row shows instruction pairs
    where the first instruction is a COPY while the second is an ADD.
    In this case, only a COPY instruction of size 4 immediately followed
    by an ADD instruction of size 1 would be coded as a pair. The code
    indices for such pairs range from 247 to 255.


           TYPE    SIZE     MODE    TYPE     SIZE     MODE     INDEX
        ---------------------------------------------------------------
          RUN       0         -     NOOP       -        -        0
          ADD   0, [1,17]     -     NOOP       -        -      [1,18]
         COPY   0, [4,18]     0     NOOP       -        -     [19,34]
         COPY   0, [4,18]     1     NOOP       -        -     [35,50]
         COPY   0, [4,18]     2     NOOP       -        -     [51,66]
         COPY   0, [4,18]     3     NOOP       -        -     [67,82]
         COPY   0, [4,18]     4     NOOP       -        -     [83,98]
         COPY   0, [4,18]     5     NOOP       -        -     [99,114]
         COPY   0, [4,18]     6     NOOP       -        -    [115,130]
         COPY   0, [4,18]     7     NOOP       -        -    [131,146]
         COPY   0, [4,18]     8     NOOP       -        -    [147,162]
          ADD     [1-4]       -     COPY     [4-6]      0    [163,174]
          ADD     [1-4]       -     COPY     [4-6]      1    [175,186]
          ADD     [1-4]       -     COPY     [4-6]      2    [187,198]
          ADD     [1-4]       -     COPY     [4-6]      3    [199,210]
          ADD     [1-4]       -     COPY     [4-6]      4    [211,222]
          ADD     [1-4]       -     COPY     [4-6]      5    [223,234]
          ADD     [1-4]       -     COPY       4        6    [235,238]
          ADD     [1-4]       -     COPY       4        7    [239,242]
          ADD     [1-4]       -     COPY       4        8    [243,246]
         COPY       4       [0-8]    ADD       1        -    [247,255]
        ---------------------------------------------------------------

                                Table 2

5.2 Instruction Code Table Encoding

    The format of an instruction code table is as follows:

        Size of near cache - uchar_t
        Size of same cache - uchar_t
        Compressed table data

    Since each instruction is 3 bytes, an instruction code table can be
    represented by a string of length 2*3*256 or 1536 bytes. For compact
    storage, this string is compared against the string of the default
    table to generate an encoding in the same Vcdiff format.

    Two functions tbl2str() and str2tbl() are used for converting between
    a code table and its code string.  Below is the description of tbl2str().
    str2tbl() is just as straightforward so its description will be omitted.
    Note that bytes of the same type are grouped together to induce more
    matching and increase compression.

                                   -15-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001



     1. tbl2str(Vcdcode_t* tab, uchar_t data[6*256])
     2. {    int  i, n;
     3.      n = 0;
     4.      for(i = 0; i < 256; ++i)
     5.           data[n++] = tab[i].inst1.type;
     6.      for(i = 0; i < 256; ++i)
     7.           data[n++] = tab[i].inst2.type;
     8.      for(i = 0; i < 256; ++i)
     9.           data[n++] = tab[i].inst1.size;
    10.      for(i = 0; i < 256; ++i)
    11.           data[n++] = tab[i].inst2.size;
    12.      for(i = 0; i < 256; ++i)
    13.           data[n++] = tab[i].inst1.mode;
    14.      for(i = 0; i < 256; ++i)
    15.           data[n++] = tab[i].inst2.mode;
    16. }


    Below is the algorithm to reconstruct an instruction code table:

     1. Vcdtable_t* gettable(uchar_t* data, int n_data)
     2. {   uchar_t    src[6*256], *tar;
     3.     int        n_tar;
     3.     Vcdtable_t *table;

     4.     table = malloc(sizeof(Vcdtable_t));
     5.     table->s_near = *data++;
     6.     table->s_same = *data++;

     7.     tbl2str(Dflttable, src);
     8.     n_tar = win_inflate(&tar, src, 6*256, data, n_data-2);
     9.     table->code = str2tbl(tar);
    10. }


COMMENTS.

   4-6: These lines allocate memory for the new code table and initialize
        the sizes of the near and same caches using the given data.
   7:   This line constructs the string corresponding to the default
        instruction code table.
   8-9: These lines construct the new table.




6. FURTHER ISSUES

    There are two issues not yet addressed:

    Secondary compressors:
        As discussed in Section 4.1.1, 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 ordinarily, secondary compressors are
        not needed. However, such compressors can be occasionally
        useful for further compressing the unmatched data in RUN and ADD
        instructions when Vcdiff is used only for compression.


                                   -16-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


        We reserve the following values for the indices of a few common
        compressors:

            #define VC_HUFFMAN   1    /* Huffman encoding       */
            #define VC_ARITH     2    /* arithmetic encoding    */
            #define VC_SPLAY     3    /* splay tree encoding    */

        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.

    Large file system vs. small file system:
        As discussed in Section 4.1.2, 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 that 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 state is detectable when such a
        large integer is encountered during decoding.




7.  SUMMARY

    We have described a general and portable encoding format for compression
    and differencing. The format is compact. For compression only, using
    the same 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 same data format is better than all known methods.
    Ignoring secondary compressor issues, the decoding algorithms run in linear
    time and require working space proportional to window sizes.



8.  ACKNOWLEDGEMENTS

    Thanks are due to Balachander Krishnamurthy, Jeff Mogul and Arthur Van Hoff
    who provided much encouragement to publicize Vcdiff.




9.  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.









                                   -17-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


10. 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 Transactions on Information Theory,
        23(3):337-343, May 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] G.S. Fowler, D.G. Korn, K.P. Vo, Sfio: A buffered I/O Library,
        Accepted for publication in Software Practice & Experience, 1999.








11. AUTHOR'S ADDRESS

    Kiem-Phong Vo (main contact)
    AT&T Labs, Room D223
    180 Park Avenue
    Florham Park, NJ 07932

    Phone: 973-360-8630
    Email: kpv@research.att.com

    David G. Korn
    AT&T Labs, Room D237
    180 Park Avenue
    Florham Park, NJ 07932

    Phone: 973-360-8602
    Email: dgk@research.att.com














                                   -18-

RFC 3   VCDIFF Generic Differencing and Compression Data Format   March 2001


12. APPENDIX: SECTION LAY-OUT IN A DELTA FILE

   For reference convenience, the lay-out of the various sections
   in a delta file are summarized below. An indented section means further
   refinement of the item above it.

        Header
                (0x56 | (1<<7)) - uchar_t
                (0x43 | (1<<7)) - uchar_t
                (0x44 | (1<<7)) - uchar_t
                (0)             - uchar_t
                Indicator - uchar_t
                [Secondary compressor - uchar_t]
                [Length of instruction code table data - uint_t]
                [Instruction code table data]
                        Size of near cache - uchar_t
                        Size of same cache - uchar_t
                        Compressed table data
        Window1
                Indicator - uchar_t
                [Source segment size - uint_t]
                [Source segment position - uint_t]
                Length of the delta encoding - uint_t
                The delta encoding
                        Length of target window - uint_t
                        Indicator - uchar_t
                        Length of ADD and RUN data section - uint_t
                        Length of instructions section - uint_t
                        Length of COPY addresses section - uint_t
                        Data section for ADD and RUN instructions
                        Instructions section
                        Addresses section for COPY instructions
        Window2
        ...








13.  EXPIRATION DATE

    September 12, 2001
















                                   -19-


Html markup produced by rfcmarkup 1.108, available from http://tools.ietf.org/tools/rfcmarkup/