[Docs] [txt|pdf] [Tracker] [Email] [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: February 23, 1999
                                               Expiration:   August 23, 1999


        The VCDIFF Generic Differencing and Compression Data Format
                       <draft-korn-vcdiff-00.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.  Delta Instructions ...........................................  3
    3.  Vcdiff Encoding Format .......................................  4
    4.  Instruction Code Tables ...................................... 10
    5.  Compression and Differencing Algorithms ...................... 15
    6.  Summary ...................................................... 19
        ACKNOWLEDGEMENTS ............................................. 19
        REFERENCES ................................................... 19
        AUTHOR'S ADDRESS ............................................. 20

1.  Executive Summary

    Storage and transmission of files and file versions can be greatly
    improved via the use of compression and differencing techniques.
    Since files are often transported across machines with distinct
    architectures and performance characteristics, encoded data should be
    in a form that is portable and easy to decode. This document describes
    Vcdiff, a new encoding format that satisfies these requirements.
    The format enables the construction of a single efficient decoder
    that is independent of encoding algorithms.

    Data differencing is the process of computing a compact and invertible
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


    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 much smaller than the original
    data files.

    Data differencing and data compression are traditionally treated as
    distinct types of data processing.  However, compression can be thought
    of as a special case of differencing in which the source data is empty.
    This blending of differencing and compression was first introduced in
    the Vdelta tool [1] by Korn and Vo.  The basic idea was 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:

        1.  Concatenate source and target data.
        2.  Process the resulting data from left to right using a parsing
                scheme similar to LZ'77.
        3.  Start to output when the target data is reached.

    Parsing can be implemented on top of various string matching algorithms,
    for example using suffix trees [4], each with different space and time
    performance characteristics.  Vdelta uses an efficient string matching
    algorithm previously shown to compare well against other well-known
    techniques as shown in [5].  However, even with the relatively efficient
    memory usage for Vdelta, memory requirement for string matching can be
    prohibitive when processing large files.  To handle this, data
    compressors and differencers typically partition input files into
    chunks called windows and process each window separately. Except for
    unpublished work by Vo, little has been done on designing effective
    windowing schemes. Current techniques, including Vdelta, simply use
    windows with corresponding addresses across the source and target files.
    Such a pair of corresponding windows also often have the same size.

    From the point of view of data transporting and data storage, it is
    desirable to remove all issues concerning string matching and windowing
    algorithms from the decoding phase. This would enable client-server
    applications in which a server may serve multiple clients whose computing
    characteristics are unknown to it.  However, all current differencing and
    compressing tools, including Vdelta, fell short in this aspect since their
    data encoding formats depend on both the string matching and windowing
    algorithms that they use. To solve this problem, we propose here a new
    data encoding format, Vcdiff, for encoding delta and compressed files.
    Vcdiff achieves the below characteristics:

    1.  Algorithm genericity:
        Both the data format and the decoding algorithm are
        independent of string matching algorithms or windowing schemes.
    2.  Decoding efficiency:
        A target file can be reconstructed in time proportional to
        its size and the space used to do so is proportional to
        the maximal window size.
    3.  Output compactness:
        A delta or compressed file is compactly represented.
    4.  Data portability:
        The encoding format is free from byte order and word size issues.

                                   -2-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999



    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 terms "delta file" to indicate the
    compressed output for both cases.


2.  Delta Instructions

    A large target file is partitioned into sections called windows, each
    of which is processed separately. Each target window T with length n
    may be compared against some source data segment S with length m bytes.
    A source data segment may come from the already processed part of the
    target file or it may come the source file, if one is given. It is
    assumed that there is sufficient memory so that both T and S can be
    treated as strings stored in main memory. For the purpose of addressing
    bytes in a source segment and target window, it is convenient to think
    of S and T as substrings of a superstring U formed by concatenating
    T to S like this:

        s[0]s[1]...s[m-1]t[0]t[1]...t[n-1]

    An index in S or T is referred to by its location in U.  For example,
    index i in T will be referred to as m+i.  Note also that indices start
    from zero.

    The instructions to encode and direct the reconstruction of a target
    window are called delta instructions.  There are three types:

    1.  ADD:
        This instruction type requires two arguments, a size s and a
        sequence of s bytes to be copied to reconstruct the target window.
    2.  COPY:
        This instruction type requires two arguments, a size s and an
        address p in the string U.  The arguments specify the substring
        of U that must be copied. Note that such a substring must be
        entirely contained in one of S or T.
    3.  RUN:
        This instruction type requires two arguments, a size s and a byte c
        that will be repeated s times.

    For example, given the source and target strings

        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 e f g h

    the target string can be constructed from the source string with the
    following instructions:

        COPY  4, 0
        ADD   4, w x y z
        COPY  4, 4
        COPY 16, 24

    Note that the third COPY instruction copies data from T itself since
    address 24 is position 8 in T.  Note also that parts of the data
    to be copied by this instruction will be reconstructed during the copy
    operation.  Thus, periodic sequences, i.e., sequences with regularly
    repeated subsequences, can be efficiently encoded. Although a run of

                                   -3-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


    the same byte can be thought of as a periodic sequence with period 1,
    we provide a separate RUN instruction because for certain types of
    files such as executable code, runs of the same bytes are frequent and
    can benefit from having a compact representation.


3.  Vcdiff Encoding Format

    Algorithms will be presented in ANSI-C.  To ease the presentation,
    error checking will be generally omitted.  Certain elementary functions
    shall be assumed without formal description.  For example, get_byte()
    reads single byte from the delta file. Other like functions will be
    mentioned during the course of the presentation.

    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.  Bits shall be named from right to
    left so that the first bit has lowest value, 1, and the eight bit has
    value (1<<7) or 128.


3.1 Delta File Layout

    A large target file is typically processed in non-overlapping sections
    called target windows. We shall assert that each window is at most
    2^31 in length.  A target window may be processed against some source
    data segment. For compression, a source segment would be from some
    earlier part of the target file while, for differencing, it may also
    be from the source file.

    The following is the layout of a delta file.

                Header
                First window
                Second window
                ....

    The delta file starts with a 4-byte header identifying the file type,
    0xd6, 0xc3, 0xc4, 0. The first three bytes are the ASCII letters
    'V', 'C' and 'D' or-ed with the eighth bit. The fourth byte is a
    version number, currently set to zero.

    Following the 4-byte header are a number of sections, each of which
    encodes a target window.  During target file reconstruction, windows
    are processed in the order that they appear in the delta file.
    Each window section starts with the below header data:

    1.  The number of bytes used to encode this window. This includes
        all header data. If this value is zero, the reconstruction ends.
        The encoding of the value uses four bytes based on the portable
        format to encode integers in the range [0,2^31] (Section 3.2).

    2.  The size of the target window is encoded as a variable-sized
        unsigned integer (Section 3.2).

    3.  An indicator byte whose low four bits signal the type of source
        segment and the high four bits signal any change in the instruction
        code table. The bits are interpreted as follows:


                                   -4-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


        a.  The low four bits of the indicator byte are 0 for no source
            segment, 1 for the source segment from the source file, and 2
            for from the target file. When there is a source segment,
            next in the delta file are two unsigned integers for the size
            of this segment and its position in the respective file.

        b.  The high four bits of the indicator byte after right-shifting
            4 bits are 0 for no instruction code table change, 1 for
            switching to a code table already defined, and 2 for defining
            a new code table. When the indicator bits are non-zero, next
            in the delta stream will be a byte indicating the index of
            the new table. If the indicator bits have value 2, next will
            be the data defining the new table. Note that the initial code
            table always has index 0. Section 4 discusses instruction
            tables in detail.

    Below is the algorithm to decode a target file:

     1. Vcdcode_t  *Tab;

     2. get_byte(); get_byte(); get_byte(); get_byte();
     3. for(;;)
     4. {   if((n_head = get_rint(1<<31)) == 0 || iseof())
     5.          break;

     6.     n_tar = get_uint();

     7.     if(((indicator = get_byte())&0xf) > 0)
     8.     {    n_src = get_uint();
     9.          p_src = get_uint();
    10.          src = get_source(indicator&0xf, n_src, p_src);
    11.     }
    12.     else n_src = p_src = 0;

    13.     if((indicator >>= 4) > 0)
    14.          Tab = get_codetab(indicator);

    15.     win_decode(Tab, src,n_src, tar,n_tar);
    16.     put_target(tar,n_tar);
    17. }

    Line 1 declares Tab which points to the current instruction code table.
    Line 2 reads the four-byte header.
    Line 4 reads the number of bytes for the encoding of this window.
    Line 6 read the size of a target window to be reconstructed.
    Lines 7-12 obtain the source data segment. The function get_source()
        constructs the source data segment which could be from the
        source file or from the target file depending on the value of i.
    Lines 13-14 process data to define a new instruction code table, if any.
        The function get_codetab() will be discussed in Section 4.2.
    Lines 15-16 call win_decode() to decode the target window, then
        call put_target() to write it to the target file.

    The elementary functions get_source() and put_target() shall be assumed
    without description.


3.2 Integer Encoding Formats


                                   -5-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


    It is important that sizes of delta instructions be encoded compactly.
    Vcdiff encodes these values as unsigned integers using the variable
    sized portable format that was introduced in the Sfio library [6].
    Each unsigned integer is encoded as a sequence of bytes.  The eighth
    bit of a byte is the continuation bit, and, when on, indicates that
    the next byte is part the same integer.

    Below are the algorithms to encode and decode unsigned integers. The
    type uchar_t is the C type unsigned char and int_t is the largest
    supported integer type.  We assume that all values fit into int_t. For
    absolute data portability, any encoded value should be small enough to
    fit the int_t of a decoding machine. For example, this means that a file
    with size larger than 2^32 will not be decodable on a machine whose
    integers are restricted to 32 bits. This is reasonable since such a
    machine does not support large files anyway.

     1. #define MORE_SHIFT  7
     2. #define MORE_BIT    (1 << MORE_SHIFT)

     3. int put_uint(int_t v)
     4. {   uchar_t c[2*sizeof(int_t)], *s;

     5.     s = &c[sizeof(c)-1];
     6.     *s = v & (MORE_BIT-1);
     7.     while((v >>= MORE_SHIFT) != 0)
     8.         *--s = (v & (MORE_BIT-1)) | MORE_BIT;

     9.     put_data(s, (&c[sizeof(c)]) - s);

    10.     return  &c[sizeof(c)]-s;
    11. }

    12. int_t get_uint()
    13. {   int_t b, v;

    14.     for(v = 0;; )
    15.     {   b = get_byte();
    16.         v = (v << MORE_SHIFT) | (b & (MORE_BIT-1));
    17.         if(!(b & MORE_BIT) )
    18.             return v;
    18.     }
    19. }

    Line 9 calls put_data() to write the encoded integer to the
        delta file. This elementary function shall be assumed
        without description.


                        +---------------------+
                        | 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 as an unsigned integer uses two bytes with values 96 and 57.

                                   -6-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999



    The address of a COPY instruction is an unsigned integers with a
    known range, i.e., it cannot be larger than the current position.
    Such a value can be encoded more compactly than as done in the Sfio
    scheme. For example, if a value is known to be in the range 0-255,
    it can be encoded with a single byte. On the other hand, if the same
    value happens to be larger than 127, it would require two bytes to
    encode in the Sfio scheme. Below are the algorithms to encode
    integers with known ranges.


     1. #define BYTE_SHIFT  8
     2. #define BYTE_MASK   ((1 << BYTE_SHIFT) - 1)

     3. int put_rint(int_t v, int_t range)
     4. {   uchar_t c[sizeof(int_t)], *s;
     5.     s = &c[sizeof(c)-1];
     6.     *s = v & BYTE_MASK;
     7.     while((range >>= BYTE_SHIFT) != 0)
     8.     {   *--s = v & BYTE_MASK;
     9.         v >>= BYTE_SHIFT;
    10.     }
    11.     put_data(s, (&c[sizeof(c)]) - s);
    12.     return (&c[sizeof(c)]) - s;
    13. }

    14. int_t get_rint(int_t range)
    15. {   int_t v;
    16.     for(v = 0; range > 0; range >>= BYTE_SHIFT)
    17.         v = (v << BYTE_SHIFT) | get_byte();
    18.     return v;
    19. }


3.3 Delta Instruction Coding Format

    The delta instructions are encoded in a stream of control bytes and
    associated data. Each control byte is an index into an instruction
    code table of 256 entries whose type, Vcdcode_t, is defined below:

     1. typedef struct _vcdinst_s
     2. {   unsigned char type;  /* instruction type           */
     3.     unsigned char size;  /* >0 if size is coded here   */
     4.     unsigned char 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;

    Thus, each control byte may identify up to two instructions.
    Below are the different instruction types:

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


                                   -7-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


    Each instruction has a size n of the data involved. If the field
    Vcdinst_t.size is non-zero, it is the value for n.  Otherwise,
    n is encoded next in the delta file as an unsigned integer.
    Following this is respectively the n bytes of data for an ADD
    instruction, or the byte to be repeated for a RUN instruction,
    or the copying address for a COPY instruction.

    The COPY address can be encoded in different ways. The field
    Vcdinst_t.mode defines the address encoding mode:

     1. #define VCD_SELF  0      /* coded as itself            */
     2. #define VCD_HERE  1      /* coded off current position */
     3. #define VCD_SAME  2      /* index into "same" cache    */
     4. #define VCD_NEAR  3      /* index into "near" cache    */

    The values VCD_SAME and VCD_NEAR indicate two address caching
    methods designed to take advantage of the fact that different
    versions of a data source often arise from small modifications.
    As such, successive copying addresses tend to have addresses
    that are either identical or close to one another. An address A
    of a COPY instruction is coded as follows:

    1.  Let H be the current location of target data to be processed.
        If H-A is in the range [0,255], the address mode is VCD_HERE
        and A is coded in a single byte with value H-A.
    2.  256 addresses are kept in a "same" cache. The low eight bits
        of A are used to index the cache. If A matches this address,
        then the mode is VCD_SAME and A is coded in a single byte
        representing the matching index.
    3.  4 addresses are kept in a "near" cache. This cache is updated
        in a round robin manner. A is checked against each element E of
        the cache. If A-E is in the range [-127,128], the address mode
        is VCD_NEAR plus the index of E while A is coded in a single
        byte with value A-E+127.
    4.  If none of the above cases apply, the address mode is VCD_SELF
        and A is coded as an integer in the range [0-H] where H is
        the current location.

    Below are the algorithms to initialize and update address caches.

     1. typedef struct _cache_s
     2. {   int   n;
     3.     int   near[4];
     4.     int   same[256];
     5. } Cache_t;
     6. cache_init(Cache_t* ka)
     7. {    int i;
     8.      for(i = 0; i < 4; ++i)
     9.          ka->near[i] = 0;
    10.      ka->n = 0;
    11.      for(i = 0; i < 256; ++i)
    12.          ka->same[i] = 0;
    13. }
    14. cache_update(Cache_t* ka, int_t addr)
    15. {    ka->near[ka->n] = addr;
    16.      if((ka->n += 1) >= 4)
    17.          ka->n = 0;
    18.      ka->same[addr&255] = addr;
    19. }

                                   -8-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999




    Below is the function to encode a COPY address:

     1. int addr_encode(Cache_t* ka, int addr, int here, int* best)
     2. {   int  i, d, mode = -1;

     3.     if((d = (here-addr)) < 256)
     4.     {    *best = d;
     5.          mode = VCD_HERE;
     6.     }
     7.     else if(ka->same[d = addr&255] == addr)
     8.     {    *best = d;
     9.          mode = VCD_SAME;
    10.     }
    11.     else
    12.     {    for(i = 0; i < 4; ++i)
    13.          {    if((d = addr - ka->k_near[i]) >= -127 && d <= 128)
    14.               {    *best = d + 127;
    15.                    mode = VCD_NEAR+i;
    16.               }
    17.          }
    18.     }
    19.     if(mode < 0)
    20.     {    *best = addr;
    21.          mode = VCD_SELF;
    22.     }

    23.     cache_update(ka,addr);
    24.     return mode;
    25. }

    Lines 3-6 check for coding against the current location.
    Lines 7-10 check for coding against the same[] cache.
    Lines 12-17 check for coding against the near[] cache.
    Lines 19-22 encode the address as itself if no other mode was chosen.
    Lines 23-24 update the cache, then return the selected mode.


    Below is the function to decode a COPY address:

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

     3.     if(type == VCD_SELF)
     4.          addr = get_rint(here);
     5.     else if(type == VCD_HERE)
     6.          addr = here - get_byte();
     7.     else if(type == VCD_SAME)
     8.          addr = ka->same[get_byte()];
     9.     else addr = ka->near[type] + get_byte() - 127;

    10.     cache_update(ka, addr);
    11.     return addr;
    12. }





                                   -9-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


3.4 Decoding A Target Window

    The algorithm to decode a target window is as follows:

     1. win_decode(Vcdcode_t* tab,uchar_t* src,int nsrc,uchar_t* tar,int ntar)
     2. {    int_t     here, size, addr, i;
     3.      Cache_t   ka;
     4.      Vcdcode_t *code;
     5.      Vcdinst_t *inst;

     6.      cache_init(&ka);
     7.      for(here = 0; here < n_tar; )
     8.      {    code = &tab[get_byte()];
     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 = get_uint();
    15.                if(inst->type == VCD_ADD)
    16.                {    for(; size > 0; --size)
    17.                          tar[here++] = get_byte();
    18.                }
    19.                else if(inst->type == VCD_RUN)
    20.                {    int  c = get_byte();
    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);
    27.                     from = addr < nsrc ? src+addr : tar+addr-nsrc;
    28.                     for(; size > 0; --size)
    29.                          tar[here++] = *from++;
    30.                }
    31.           }
    32.      }
    33. }

    Line 1 declares the formal arguments to win_decode(). The argument
        "tab" defines the instruction code table.
    Line 6 initializes the address caches.
    Line 8 reads a control byte and gets the corresponding code.
    Lines 9-32 process the pair of delta instructions defined by the code.


4.  Instruction Code Tables

    Each target window is based on some instruction code table. Delta
    file compactness can be enhanced by tailoring such code tables
    to particular data characteristics.

    Vcdiff provides support for up to 256 instruction tables with
    indices in the range [0,255]. However, the first 8 indices [0,7]
    are reserved by Vcdiff for certain predefined code tables and
    should not be reset by applications.




                                   -10-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


4.1 Decoding a Code Table in the Delta File

    To output a table to a delta file, it is necessary to encode it in
    a portable form. Further, it is desirable to do that compactly.
    To accomplish this, we first represent a table as a string. As each
    instruction consists of 3 bytes and each table entry codes 2
    instructions, the total size needed is 6*256 or 1536 bytes. Two
    functions tab2str() and str2tab() are used for converting between
    a table to a string and vice versa.  Below is the description of
    tab2str(). str2tab() is just as straightforward so its description
    will be omitted. Note that bytes of the same type are grouped together.
    This helps with the step to compress the data.


     1. tab2str(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 function get_codetab() to get a new instruction code
    table to decode a target window:

     1. Vcdcode_t  *Code[256];

     2. Vcdcode_t* get_codetab(int indicator)
     3. {   int      index;
     4.     uchar_t  *diff, data[1536];

     5.     index = get_byte();
     6.     if(indicator == 2)
     7.     {   diff = tab2str(Code[get_byte()]);
     8.         win_decode(Code[0], diff, 1536, data, 1536);
     9.         Code[index] = str2tab(data);
    10.     }
    11.     return Code[index];
    12. }

    Line 1 indicates that Vcdiff allows up to 256 code tables.
    Line 5 reads the index of the new code table.
    Lines 6-10 construct a new table from data in the delta stream.
        Such a table is always encoded using the reserved code table
        Code[0]. In addition, it is compared against a previously defined
        table to minimize the amount of data needed to transmit in the
        delta file.
    Line 7 reads the index of the table used to compare with the
        new table to construct the delta instructions.

                                   -11-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


    Line 8 calls win_decode() to recompute the string representation
        of the table.
    Line 9 sets the new table in the given index.
    Line 11 returns the code table.


4.2 Reserved Instruction Code Tables

    Using COPY instructions with small sizes sometimes adversely affect
    compactness. Thus, it is advantageous to restrict COPY instructions
    to some minimum sizes. Then, code tables can be designed to take
    advantage of this restriction to optimize delta file compactness.
    Vcdiff provides two reserved instruction code tables with indices
    0 and 1 for minimium COPY sizes of 4 and 3 respectively. As noted
    earlier, the starting code table has index 0 so it is optimized
    for minimum COPY size of 4. Note also that even when a table
    optimized for a particular minimum COPY size, this does not mean that
    a COPY instruction with a smaller size cannot be encoded. It simply
    means that the size of such an instruction must be coded separately
    as an unsigned integer.


         TYPE    SIZE      MODE    TYPE    SIZE     MODE    INDEX
      -------------------------------------------------------------
      1.  RUN     0                NOOP                       0
      2.  ADD     0                NOOP                       1
      3.  ADD   [1,14]             NOOP                     [2,15]
      4. COPY     0       [0,6]    NOOP                    [16,22]
      5. COPY   [M,M+10]  [0,6]    NOOP                    [23,99]
      6. COPY     0       [0,6]     ADD   [1,4]           [100,127]
      7. COPY   [M,M+3]   [0,6]     ADD   [1,4]           [128,239]
      8. COPY   [M,M+3]    SELF    COPY   [M,M+3]   SELF  [240,255]
      -------------------------------------------------------------

                            Table 2.


    For a given minimum COPY size M, Table 2 shows how the 256 code
    values are partitioned into different categories of indices:

    1.  Index 0 defines a RUN instruction whose size is always
        coded separately as an unsigned integer. This is signified
        by having the "size" field being 0.
    2.  Index 1 defines an ADD instruction with size coded separately.
    3.  Indices 2-15 define 14 ADD instructions with sizes in the
        range [1,14].
    4.  Indices 16-22 define 7 COPY instructions for the 7 different
        address encoding modes discusses in Section 3.3. The sizes
        of these instructions are coded separately.
    5.  Indices 23-99 define 77 COPY instructions using all 7
        addressing modes and having sizes in the range [M,M+10].
    6.  Indices 100-127 defines 28 pairs of COPY and ADD instructions.
        The COPY sizes are coded separately while the ADD sizes are
        in the range [1,4].
    7.  Indices 128-239 define 112 pairs of COPY and ADD instructions
        whose sizes are in the ranges [M,M+3] and [1,4] respectively.
    8.  Finally, indices 240-255 defines 16 pairs of COPY and COPY
        instructions with sizes in the range [M,M+3] and both using
        the same VCD_SELF addressing mode.

                                   -12-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999



    Next we present the algorithms to construct an instruction code
    table as described above. Where appropriate, the algorithms also
    construct the inverted tables usable for data encoding. Any part
    of a table not explicitly set will be assumed to be initialized
    to be either zero or the null pointer as the case warranted.

     1. mk_codetab(Vcdcode_t tab[256], int add[16], int copy[15][7],
     2.              int copyadd[8][7][5], int copycopy[8][8], int M)
     3. {
     4.     tab[0].inst1.type = VCD_RUN;
     5.     tab[0].inst1.size = 0;
     6.     tab[0].inst2.type = VCD_NOOP;

     7.     mk_add(tab, add);
     8.     mk_copy(tab, copy, M);
     9.     mk_copyadd(tab, copyadd, M);
    10.     mk_copycopy(tab, copycopy, M);
    11. }

    Lines 1-2 declare the arguments for mk_codetab(). The inverted
        tables add[], copy[][], copyadd[][][], and copycopy[][] are
        designed to be indexed by sizes and address modes. The argument
        M is the minimum COPY size used for the table.
    Lines 4-6 construct the RUN instruction.
    Lines 7-10 calls various subroutines to construct different parts
        of the instruction table.


    Below is the algorithm to construct the single ADD instructions:

     1. mk_add(Vcdcode_t tab[256], int add[16])
     2. {   int s, n;

     3.     tab[1].inst1.type = VCD_ADD;
     4.     tab[1].inst1.size = 0;
     5.     tab[1].inst2.type = VCD_NOOP;
     6.     add[0] = 1;

     7.     for(n = 2, s = 1; s <= 14; ++s, ++n)
     8.     {   tab[n].inst1.type = VCD_ADD;
     9.         tab[n].inst1.size = s;
    10.         tab[n].inst2.type = VCD_NOOP;
    11.         add[s] = n;
    12.     }
    13. }

    Lines 3-6 construct the ADD instruction with size coded separately.
        Location 0 in the inverted table add[] points to this code.
    Lines 7-12 construct the ADD instructions with size in the range
        [1-14] as discussed earlier.









                                   -13-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999



    Below is the function to construct the single COPY instructions:

     1. mk_copy(Vcdcode_t tab[256], int copy[15][7], int M)
     2. {   int s, m, n;

     3.     for(n = 16, m = 0; m < 7; ++m, ++n)
     4.     {   tab[n].inst1.type = VCD_COPY;
     5.         tab[n].inst1.size = 0;
     6.         tab[n].inst1.mode = m;
     7.         tab[n].inst2.type = VCD_NOOP;
     8.         copy[0][m] = n;
     9.     }

    10.     for(s = M; s <= M+10; ++s)
    11.     {   for(m = 0; m < 7; ++m, ++n)
    12.         {   tab[n].inst1.type = VCD_COPY;
    13.             tab[n].inst1.size = s;
    14.             tab[n].inst1.mode = m;
    15.             tab[n].inst2.type = VCD_NOOP;
    16.             copy[s][m] = n;
    17.         }
    18.     }
    20. }

    Lines 3-9 construct the 7 COPY instructions with sizes coded
        separately.
    Lines 10-18 construct the 77 COPY instructions with sizes in
        the range [M,M+10].


    The below function constructs the pairs of COPY/ADD instructions:

     1. mk_copyadd(Vcdcode_t tab[256], int copyadd[8][7][5], int M)
     2. {   int s, m, a, n;
     3.     for(n = 100, m = 0; m < 7; ++m)
     4.     {   for(a = 1; a <= 4; ++a, ++n)
     5.         {   tab[n].inst1.type = VCD_COPY;
     6.             tab[n].inst1.size = 0;
     7.             tab[n].inst1.mode = m;
     8.             tab[n].inst2.type = VCD_ADD;
     9.             tab[n].inst2.size = a;
    10.             copyadd[0][m][a] = n;
    11.         }
    12.     }
    13.     for(s = M; s <= M+3; ++s)
    14.     {   for(m = 0; m < 7; ++m)
    15.         {   for(a = 1; a <= 4; ++a, ++n)
    16.             {   tab[n].inst1.type = VCD_COPY;
    17.                 tab[n].inst1.size = s;
    18.                 tab[n].inst1.mode = m;
    19.                 tab[n].inst2.type = VCD_ADD;
    20.                 tab[n].inst2.size = a;
    21.                 copyadd[s][m][a] = n;
    22.             }
    23.         }
    24.     }
    25. }


                                   -14-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999




    Finally, the algorithm to construct the 16 COPY/COPY pairs:

     1. mk_copycopy(Vcdcode_t tab[256], int copycopy[8][8], int M)
     2. {   int s, c, n;
     3.     for(n = 240, s = M; s <= M+3; ++s)
     4.     {   for(c = M; c <= M+3; ++c, ++n)
     5.         {   tab[n].inst1.type = VCD_COPY;
     6.             tab[n].inst1.size = s;
     7.             tab[n].inst1.mode = VCD_SELF;
     8.             tab[n].inst2.type = VCD_COPY;
     9.             tab[n].inst2.size = c;
    10.             tab[n].inst2.mode = VCD_SELF;
    11.             copycopy[s][c] = n;
    12.         }
    13.     }
    14. }


5.  Compression and Differencing Algorithms

    Sections 3 and 4 describe in full how to reconstruct a target file
    from data in a delta file. In this section, we discuss briefly
    general algorithms for compressors and differencers. Two abstract
    functions shall be assumed:

    win_match(): This function computes a source segment, if any, to be
        compared with a target window. It returns 0, 1 or 2 for no source
        segment, source segment from the source file, or source segment
        from the target file.
    str_match(): This function computes a string in either the source
        segment or the target window that matches with a prefix of the
        target data being processed. Such a matched string can be encoded
        as a COPY instruction.

    The performance of an encoder in terms of time as well as output
    compactness depends on what algorithms are used to implement the
    two window and string matching functions. However, as shown earlier,
    the reconstruction of a target file is completely independent of
    such choices.

    Below is the algorithm for processing a target file:

     1. put_byte(0xd6); put_byte(0xc3); put_byte(0xc4); put_byte(0);
     2. for(p_tar = 0; ; p_tar += n_tar)
     3. {   if((n_tar = get_target(&tar)) <= 0)
     4.         break;
     5.     n_delta = put_rint(0, (1<<31));
     6.     n_delta += put_uint(n_tar);
     7.     type = win_match(tar, n_tar, p_tar, &src, &n_src, &p_src);
     8.     n_delta += put_byte(type);
     9.     if(type > 0)
    10.     {   n_delta += put_uint(n_src);
    11.         n_delta += put_uint(p_src);
    12.     }
    13.     n_delta += win_encode(src,n_src, tar,n_tar);
    14.     put_delsize(n_delta);
    15. }

                                   -15-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999



    Line 1 outputs the four header bytes.
    Lines 3-4 get a target window. If there is none, the loop is terminated.
    Line 5 outputs a place holder for the total size of the delta code used
         for this window.
    Line 6 outputs the size of the target window.
    Line 7 calls win_match() to compute a source segment if any. Note
        that the current position in the target file, p_tar, is passed
        to win_match() so that it can ensure that a source segment from
        the target file will come entirely before p_tar.
    Line 8 outputs the indicator byte for the window. Here, we assume
        that the default instruction code table with index 0 is used.
    Lines 9-12 output the size and position of the source segment as needed.
    Line 13 calls win_encode() to encode the target window.
    Line 14 overwrites the value written out on Line 5 with the actual size
        of the delta. The function put_delsize() is straightforward so its
        description will be omitted.


    Below is the function to encode a target window:

     1. int win_encode(uchar_t* src, int n_src, uchar_t* tar, int n_tar)
     2. {   int      add, here, addr, s, size = 0;
     3.     Cache_t  ka;

     4.     cache_init(&ka);

     5.     for(here = 0; add = -1; here < n_tar; )
     6.     {   if( (s = chk_run(tar, n_tar, here)) > 0)
     7.              addr = -1;
     8.         else s = str_match(src,n_src,tar,n_tar,here,&addr);
     9.         if(s > 0)
    10.         {    if(add >= 0)
    11.                   size += put_add(here-add, tar+here-add);
    12.              if(addr < 0)
    13.                   size += put_run(s, tar[here]);
    14.              else size += put_copy(&ka, s, addr, here);

    15.              add = -1;
    16.              here += s;
    17.         }
    18.         else
    19.         {    if(add < 0)
    20.                   add = here;
    21.              here += 1;
    22.         }
    23.     }
    24.     if(add >= 0)
    25.          size += put_add(here-add, tar+here-add);
    26.     else size += put_copy(0,0,0,0);

    27.     return size;
    28. }

    Line 4 initializes the address caches.
    Lines 6-8 check to see if there is a RUN or a COPY. In the latter case,
        str_match() returns the address of the COPY in addr. The function
        chk_run() is straightforward to implement so its description will
        be omitted.

                                   -16-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


    Lines 9-17 output the appropriate delta instruction.
    Lines 19-22 get executed if there is no run or match. In this case, data
        is collected for an ADD instruction.
    Lines 24-25 output the last unmatched part of the target window in an
        ADD instruction.
    Line 26 forces the last saved COPY instruction (if any) to be output.
        See the function put_copy() below.
    Line 27 returns the number of bytes used for encoding the data.

    To finish up the encoding algorithm, we need to describe the functions
    put_add(), put_run() and put_copy(). We shall assume that the default
    code instruction table 0 is used. The below code declares the tables
    and define a few convenience macro functions.

     1. Vcdcode_t Tab[256];
     2. Vcdcode_t *Add[16];
     3. Vcdcode_t *Copy[15][7];
     4. Vcdcode_t *Copyadd[8][7][5];
     5. Vcdcode_t *Copycopy[8][8];

     6. #define INDEXADD(a)     ((a >= 1 && a <= 14) ? a : 0)
     7. #define INDEXCOPY(c)    ((c >= 4 && c <= 14) ? c : 0)
     8. #define INDEXCOPYADD(c) ((c >= 4 && c <=  7) ? c : 0)
     9. #define ISTINYADD(a)    ((a >= 1 && a <= 4) ? 1 : 0)
    10. #define ISTINYCOPY(c)   ((c >= 4 && c <= 7) ? 1 : 0)

    Lines 6-8 define functions to compute the index into the tables
        Add, Copy, and Copyadd for some given ADD or COPY size.
    Lines 9-10 define functions to test if a given size is small. These
        are used to determine if certain pair of instructions could be
        coded using a single byte code.


    Below is the function to output a COPY instruction.

     1. int Size, Addr, Here, Mode;

     2. int put_copy(Cache_t* ka, int size, int addr, int here)
     3. {   int code, mode = 0, best = 0, ndel = 0;

     4.     if(size > 0)
     5.         mode = addr_encode(ka, addr, here, &best);

     6.     if(Size > 0)
     7.     {   if(Mode == mode && mode == VCD_SELF &&
     8.            ISTINYCOPY(Size) && ISTINYCOPY(size) )
     9.         {    code = Copycopy[Size][size];
    10.              ndel += put_byte(code);
    11.              ndel += put_rint(Addr, Here);
    12.              ndel += put_rint(addr, here);
    13.              Size = -1;
    14.              return ndel;
    15.         }
    16.         code = Copy[INDEXCOPY(Size)][Mode];
    17.         ndel += put_byte(code);
    18.         if(Tab[code].inst1.size == 0)
    19.              ndel += put_uint(Size);
    20.         if(Mode == VDC_SELF)
    21.              ndel += put_rint(Addr,Here);

                                   -17-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999


    22.         else ndel += put_byte(Addr);
    23.     }

    24.     Size = size;
    25.     Addr = best;
    26.     Mode = mode;
    27.     Here = here;

    28.     return ndel;
    29. }

    Line 1 defines variables to save a COPY instruction so that it
        may be coded jointly with another instruction later.
    Lines 4-5 compute the mode and value to encode the given COPY
        address if there is one (i.e., "size" is positive).
    Lines 6-23 process a previously saved COPY instruction.
    Lines 7-15 output a code that encode both COPY instructions.
    Lines 16-22 output the previously saved COPY instruction singly.
    Lines 24-27 save the current COPY instruction if it has not
        already output as discussed.


    Below is the function to output an ADD instruction:

     1. int put_add(int size, uchar_t* data)
     2. {   int code, ndel = 0;

     3.     if(Size > 0)
     4.     {   if(ISTINYADD(size))
     5.         {    code = Copyadd[INDEXCOPYADD(Size)][Mode][size];
     6.              ndel += put_byte(code);
     7.              if(Tab[code].inst1.size == 0)
     8.                   ndel += put_uint(Size);
     9.              if(Mode == VCD_SELF)
    10.                   ndel += put_rint(Addr,Here);
    11.              else ndel += put_byte(Addr);
    12.              for(; size > 0; --size, ++data)
    13.                   ndel += put_byte(*data);
    14.              return ndel;
    15.         }
    16.         else ndel += put_copy(0,0,0,0);
    17.     }

    18.     code = Add[INDEXADD(size)];
    19.     ndel += put_byte(code);
    20.     if(Tab[code].inst1.size == 0)
    21.         ndel += put_uint(size);
    22.     ndel += size;
    23.     for(; size > 0; --size, ++data)
    24.         put_byte(*data);

    25.     return ndel;
    26. }

    Lines 3-17 consider the case when there is a previously saved
        COPY instruction. In that case, if the ADD size is small,
        a single code is output for both COPY and ADD instructions.
        Otherwise, the COPY instruction is output by itself.
    Lines 18-24 output an ADD instruction by itself.

                                   -18-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999



    Below is the function to output a RUN instruction:

     1. int put_run(int size, int byte)
     2. {   int ndel = 0;
     3.     if(Size > 0)
     4.         ndel += put_copy(0,0,0,0);
     5.     ndel += put_byte(0);
     6.     ndel += put_uint(size);
     7.     ndel += put_byte(byte);
     8.     return ndel;
     9. }

    Lines 3-4 output a previously saved COPY instruction, if any.
    Lines 5-7 output the RUN instruction.


6.  Summary

    We have described a general and portable data format for compression
    differencing. Reference [7] shows that the format is compact. For
    compression, it is better than Unix compress and close to gzip. For
    differencing, it is better than all known methods. The decoding
    algorithms run in linear time and require working space proportional
    to window sizes. This makes it suitable for data communication
    among computers.


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


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.

    [7] D.G. Korn and K.P. Vo, A Generic Differencing and Compression
        Data Format, Technical Report AT&T Labs HA1630000-021899-02TM,
        February 1999.

                                   -19-
RFC 0   VCDIFF Generic Differencing and Compression Data Fornmat   Feb 1999





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


EXPIRATION DATE

    August 23, 1999


































                                   -20-


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