← Back to branch summary

~svn/ubuntu/oneiric/subversion/ppa

« back to all changes in this revision

Viewing changes to notes/svndiff

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-12-05 01:26:14 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051205012614-qom4xfypgtsqc2xq
Tags: 1.2.3dfsg1-3ubuntu1
Merge with the final Debian release of 1.2.3dfsg1-3, bringing in
fixes to the clean target, better documentation of the libdb4.3
upgrade and build fixes to work with swig1.3_1.3.27.

Show diffs side-by-side

added added

removed removed

Lines of Context:
notes/svndiff
 
1
This file describes the svndiff format used by the Subversion code.
 
2
Its design borrows many ideas from the vdelta and vcdiff encoding
 
3
formats from AT&T Research Labs, but it is much simpler and thus a
 
4
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 zero
 
20
byte which represents a version number.  After the header come one or
 
21
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 in bytes
 
30
        The length of the new data in bytes
 
31
        The window's instructions
 
32
        The window's new data (as raw data)
 
33
 
 
34
Integers (including the first five items listed above) are encoded
 
35
using a variable-length format.  The high bit of each byte is used as
 
36
a continuation bit; 1 indicates that there is more data and 0
 
37
indicates the final byte.  The other seven bits of each byte are data.
 
38
Higher-order bits are encoded before lower-order bits.  As an example,
 
39
130 would be encoded as two bytes, 10000001 followed by 00000010.
 
40
 
 
41
Instructions are encoded as follows: the two high bits of the first
 
42
byte compose an instruction selector, as follows:
 
43
 
 
44
        00      Copy from source view
 
45
        01      Copy from target view
 
46
        10      Copy from new data
 
47
        11      invalid
 
48
 
 
49
The remaining six bits of the first byte indicate the length of the
 
50
copy.  If those six bytes are all zero, then the length is encoded as
 
51
an integer immediately following the first byte of the instruction.
 
52
If the instruction selector is 00 or 01, then the instruction encoding
 
53
continues with an offset encoded as an integer.  If the instruction
 
54
selector is 10, then the offset into the new data is implicit; each
 
55
copy from the new data is always for "the next <length> bytes" after
 
56
the last copy.
 
57
 
 
58
A copy from the target view must begin at a location before than the
 
59
current position in the target view, but its length may extend past
 
60
the current position.  In this case, the target data copied is
 
61
repeated, as happens naturally if the copy is performed byte by byte
 
62
starting at the beginning.
 
63
 
 
64
Following are some example instruction encodings.
 
65
 
 
66
        Copy 11 bytes from offset 0 in source view:
 
67
        00001011 00000000
 
68
 
 
69
        Copy 64 bytes from offset 128 in target view:
 
70
        01000000 00100000 10000001 00000000
 
71
 
 
72
        Copy the next 63 bytes of new data:
 
73
        10111111
 
74
 
 
75
Following is a complete example of an svndiff between the source
 
76
document "aaaabbbbcccc" and the target document "aaaaccccdddddddd":
 
77
 
 
78
        01010011 01010110 01001110 00000000     Header ("SVN\0")
 
79
 
 
80
        00000000                                Source view offset 0
 
81
        00001100                                Source view length 12
 
82
        00010000                                Target view length 16
 
83
        00000111                                Instruction length 7
 
84
        00000001                                New data length 1
 
85
 
 
86
        00000100 00000000                       Source, len 4, offset 0
 
87
        00000100 00001000                       Source, len 4, offset 8
 
88
        10000001                                New, len 1
 
89
        01000111 00001000                       Target, len 7, offset 8
 
90
 
 
91
        01100100                                The new data: 'd'