notes/svndiff

   1 This file describes the svndiff version 0, 1 and 2 formats used by the
   2 Subversion code.  Its design borrows many ideas from the vdelta and
   3 vcdiff encoding formats from AT&T Research Labs, but it is much
   4 simpler and thus a little less compact.
   5
   6 From the point of view of svndiff, a delta is a sequence of windows,
   7 each containing a list of instructions for reconstructing a contiguous
   8 section of the target using a contiguous section of the source as a
   9 reference.  The section of the target being reconstructed is called
  10 the "target view"; the section of the source being referenced is
  11 called the "source view."  Source views must not slide backwards from
  12 one window to the next; this allows svndiffs to be applied using a
  13 single pass through the source file.  Instructions in a window direct
  14 copies to be made into the target view from one of three places: from
  15 the source view, from the portion of the target view which has already
  16 been reconstructed, or from a block of new data encoded inside the
  17 window.
  18
  19 An svndiff document begins with four bytes, "SVN" followed by a byte
  20 which represents a format version number.  After the header come one
  21 or more windows, until the document ends.  (So the decoder must have
  22 external context indicating when there is no more svndiff data.)
  23
  24 A window is the concatenation of the following:
  25
  26         The source view offset
  27         The source view length
  28         The target view length
  29         The length of the instructions section in bytes
  30         The length of the new data section in bytes
  31         [original length of the instructions section in bytes (version 1)]
  32         The window's instructions section
  33         [original length of the new data section in bytes (version 1)]
  34         The window's new data section
  35
  36 In svndiff version 1 and 2, the instructions and new data sections may
  37 be compressed.  Version 1 uses zlib for compression.  Version 2 uses LZ4
  38 for compression.  In order to determine the original size in these
  39 compressed formats, an integer is appended to the beginning of each of
  40 the sections.  If the original size matches the encoded size (minus the
  41 length of the original size integer) from the header, the data is not
  42 compressed.  If the original size is different than the encoded size
  43 from the header, the remaining data in the section is compressed.
  44
  45 Integers (including the offset and all of the lengths) are encoded using a
  46 variable-length format.  The high bit of each byte is used as a
  47 continuation bit; 1 indicates that there is more data and 0 indicates
  48 the final byte.  The other seven bits of each byte are data.
  49 Higher-order bits are encoded before lower-order bits.  As an example,
  50 130 would be encoded as two bytes, 10000001 followed by 00000010.
  51
  52 Instructions are encoded as follows: the two high bits of the first
  53 byte compose an instruction selector, as follows:
  54
  55         00      Copy from source view
  56         01      Copy from target view
  57         10      Copy from new data
  58         11      invalid
  59
  60 The remaining six bits of the first byte indicate the length of the
  61 copy.  If those six bits are all zero, then the length is encoded as
  62 an integer immediately following the first byte of the instruction.
  63 If the instruction selector is 00 or 01, then the instruction encoding
  64 continues with an offset encoded as an integer.  If the instruction
  65 selector is 10, then the offset into the new data is implicit; each
  66 copy from the new data is always for "the next <length> bytes" after
  67 the last copy.
  68
  69 A copy from the target view must begin at a location before the
  70 current position in the target view, but its length may extend past
  71 the current position.  In this case, the target data copied is
  72 repeated, as happens naturally if the copy is performed byte by byte
  73 starting at the beginning.
  74
  75 Following are some example instruction encodings.
  76
  77         Copy 11 bytes from offset 0 in source view:
  78         00001011 00000000
  79
  80         Copy 64 bytes from offset 128 in target view:
  81         01000000 01000000 10000001 00000000
  82
  83         Copy the next 63 bytes of new data:
  84         10111111
  85
  86 Following is a complete example of an svndiff between the source
  87 document "aaaabbbbcccc" and the target document "aaaaccccdddddddd":
  88
  89         01010011 01010110 01001110 00000000     Header ("SVN\0")
  90
  91         00000000                                Source view offset 0
  92         00001100                                Source view length 12
  93         00010000                                Target view length 16
  94         00000111                                Instruction length 7
  95         00000001                                New data length 1
  96
  97         00000100 00000000                       Source, len 4, offset 0
  98         00000100 00001000                       Source, len 4, offset 8
  99         10000001                                New, len 1
 100         01000111 00001000                       Target, len 7, offset 8
 101
 102         01100100                                The new data: 'd'