6f1af23ebe3… — Fossil SCM

A art/encode1.tex

+2

		--- a/art/encode1.tex
		+++ b/art/encode1.tex
		@@ -0,0 +1,2 @@
	1	+\LARGE A = (\sum_{i=0}^{NHASH-1} z_i) \bmod 2^{16}
	2	+

	--- a/art/encode1.tex
	+++ b/art/encode1.tex
	@@ -0,0 +1,2 @@

	--- a/art/encode1.tex
	+++ b/art/encode1.tex
	@@ -0,0 +1,2 @@
1	\LARGE A = (\sum_{i=0}^{NHASH-1} z_i) \bmod 2^{16}
2

A art/encode2.tex

+1

		--- a/art/encode2.tex
		+++ b/art/encode2.tex
		@@ -0,0 +1 @@
	1	+\LARGE B = (\sum_{i=0}^{NHASH-1} (NHASH-i)z_i) \bmod 2^{16}

	--- a/art/encode2.tex
	+++ b/art/encode2.tex
	@@ -0,0 +1 @@

	--- a/art/encode2.tex
	+++ b/art/encode2.tex
	@@ -0,0 +1 @@
1	\LARGE B = (\sum_{i=0}^{NHASH-1} (NHASH-i)z_i) \bmod 2^{16}

A art/encode3.tex

+1

		--- a/art/encode3.tex
		+++ b/art/encode3.tex
		@@ -0,0 +1 @@
	1	+\LARGE V = 2^{16}B + A

	--- a/art/encode3.tex
	+++ b/art/encode3.tex
	@@ -0,0 +1 @@

	--- a/art/encode3.tex
	+++ b/art/encode3.tex
	@@ -0,0 +1 @@
1	\LARGE V = 2^{16}B + A

A art/encode4.tex

+1

		--- a/art/encode4.tex
		+++ b/art/encode4.tex
		@@ -0,0 +1 @@
	1	+\LARGE z_0

	--- a/art/encode4.tex
	+++ b/art/encode4.tex
	@@ -0,0 +1 @@

	--- a/art/encode4.tex
	+++ b/art/encode4.tex
	@@ -0,0 +1 @@
1	\LARGE z_0

A art/encode5.tex

+1

		--- a/art/encode5.tex
		+++ b/art/encode5.tex
		@@ -0,0 +1 @@
	1	+\LARGE z_{new}

	--- a/art/encode5.tex
	+++ b/art/encode5.tex
	@@ -0,0 +1 @@

	--- a/art/encode5.tex
	+++ b/art/encode5.tex
	@@ -0,0 +1 @@
1	\LARGE z_{new}

A art/encode6.tex

+1

		--- a/art/encode6.tex
		+++ b/art/encode6.tex
		@@ -0,0 +1 @@
	1	+\LARGE A_{new} = (A - z_0 + z_{new}) \bmod 2^{16}

	--- a/art/encode6.tex
	+++ b/art/encode6.tex
	@@ -0,0 +1 @@

	--- a/art/encode6.tex
	+++ b/art/encode6.tex
	@@ -0,0 +1 @@
1	\LARGE A_{new} = (A - z_0 + z_{new}) \bmod 2^{16}

A art/encode7.tex

+1

		--- a/art/encode7.tex
		+++ b/art/encode7.tex
		@@ -0,0 +1 @@
	1	+\LARGE B_{new} = (B - z_0 NHASH + A_{new}) \bmod 2^{16}

	--- a/art/encode7.tex
	+++ b/art/encode7.tex
	@@ -0,0 +1 @@

	--- a/art/encode7.tex
	+++ b/art/encode7.tex
	@@ -0,0 +1 @@
1	\LARGE B_{new} = (B - z_0 NHASH + A_{new}) \bmod 2^{16}

A art/encode8.tex

+1

		--- a/art/encode8.tex
		+++ b/art/encode8.tex
		@@ -0,0 +1 @@
	1	+\LARGE V_{new} = 2^{16}B_{new} + A_{new}

	--- a/art/encode8.tex
	+++ b/art/encode8.tex
	@@ -0,0 +1 @@

	--- a/art/encode8.tex
	+++ b/art/encode8.tex
	@@ -0,0 +1 @@
1	\LARGE V_{new} = 2^{16}B_{new} + A_{new}

A art/encode9.tex

+1

		--- a/art/encode9.tex
		+++ b/art/encode9.tex
		@@ -0,0 +1 @@
	1	+\LARGE A_{new}

	--- a/art/encode9.tex
	+++ b/art/encode9.tex
	@@ -0,0 +1 @@

	--- a/art/encode9.tex
	+++ b/art/encode9.tex
	@@ -0,0 +1 @@
1	\LARGE A_{new}

M src/delta.c

+1 -1

		--- src/delta.c
		+++ src/delta.c
		@@ -265,11 +265,11 @@
265	265	** delta that may contain some binary data.
266	266	**
267	267	** Algorithm:
268	268	**
269	269	** The encoder first builds a hash table to help it find matching
270		-** patterns in the source file. 16-byte chucks of the source file
	270	+** patterns in the source file. 16-byte chunks of the source file
271	271	** sampled at evenly spaced intervals are used to populate the hash
272	272	** table.
273	273	**
274	274	** Next we begin scanning the target file using a sliding 16-byte
275	275	** window. The hash of the 16-byte window in the target is used to
276	276
277	277	ADDED tools/encode_math.sh
278	278	ADDED www/delta_encoder_algorithm.html

	--- src/delta.c
	+++ src/delta.c
	@@ -265,11 +265,11 @@
265	** delta that may contain some binary data.
266	**
267	** Algorithm:
268	**
269	** The encoder first builds a hash table to help it find matching
270	** patterns in the source file. 16-byte chucks of the source file
271	** sampled at evenly spaced intervals are used to populate the hash
272	** table.
273	**
274	** Next we begin scanning the target file using a sliding 16-byte
275	** window. The hash of the 16-byte window in the target is used to
276
277	DDED tools/encode_math.sh
278	DDED www/delta_encoder_algorithm.html

	--- src/delta.c
	+++ src/delta.c
	@@ -265,11 +265,11 @@
265	** delta that may contain some binary data.
266	**
267	** Algorithm:
268	**
269	** The encoder first builds a hash table to help it find matching
270	** patterns in the source file. 16-byte chunks of the source file
271	** sampled at evenly spaced intervals are used to populate the hash
272	** table.
273	**
274	** Next we begin scanning the target file using a sliding 16-byte
275	** window. The hash of the 16-byte window in the target is used to
276
277	DDED tools/encode_math.sh
278	DDED www/delta_encoder_algorithm.html

A tools/encode_math.sh

+12

		--- a/tools/encode_math.sh
		+++ b/tools/encode_math.sh
		@@ -0,0 +1,12 @@
	1	+#!/bin/sh
	2	+bindir="`dirname "$0"`"
	3	+topdir="`dirname "$bindir"`"
	4	+mimetex -d "`cat "$topdir/art/encode1.tex"`" > "$topdir/www/encode1.gif"
	5	+mimetex -d "`cat "$topdir/art/encode2.tex"`" > "$topdir/www/encode2.gif"
	6	+mimetex -d "`cat "$topdir/art/encode3.tex"`" > "$topdir/www/encode3.gif"
	7	+mimetex -d "`cat "$topdir/art/encode4.tex"`" > "$topdir/www/encode4.gif"
	8	+mimetex -d "`cat "$topdir/art/encode5.tex"`" > "$topdir/www/encode5.gif"
	9	+mimetex -d "`cat "$topdir/art/encode6.tex"`" > "$topdir/www/encode6.gif"
	10	+mimetex -d "`cat "$topdir/art/encode7.tex"`" > "$topdir/www/encode7.gif"
	11	+mimetex -d "`cat "$topdir/art/encode8.tex"`" > "$topdir/www/encode8.gif"
	12	+mimetex -d "`cat "$topdir/art/encode9.tex"`" > "$topdir/www/encode9.gif"

	--- a/tools/encode_math.sh
	+++ b/tools/encode_math.sh
	@@ -0,0 +1,12 @@

	--- a/tools/encode_math.sh
	+++ b/tools/encode_math.sh
	@@ -0,0 +1,12 @@
1	#!/bin/sh
2	bindir="`dirname "$0"`"
3	topdir="`dirname "$bindir"`"
4	mimetex -d "`cat "$topdir/art/encode1.tex"`" > "$topdir/www/encode1.gif"
5	mimetex -d "`cat "$topdir/art/encode2.tex"`" > "$topdir/www/encode2.gif"
6	mimetex -d "`cat "$topdir/art/encode3.tex"`" > "$topdir/www/encode3.gif"
7	mimetex -d "`cat "$topdir/art/encode4.tex"`" > "$topdir/www/encode4.gif"
8	mimetex -d "`cat "$topdir/art/encode5.tex"`" > "$topdir/www/encode5.gif"
9	mimetex -d "`cat "$topdir/art/encode6.tex"`" > "$topdir/www/encode6.gif"
10	mimetex -d "`cat "$topdir/art/encode7.tex"`" > "$topdir/www/encode7.gif"
11	mimetex -d "`cat "$topdir/art/encode8.tex"`" > "$topdir/www/encode8.gif"
12	mimetex -d "`cat "$topdir/art/encode9.tex"`" > "$topdir/www/encode9.gif"

A www/delta_encoder_algorithm.html

+149

		--- a/www/delta_encoder_algorithm.html
		+++ b/www/delta_encoder_algorithm.html
		@@ -0,0 +1,149 @@
	1	+<html>
	2	+<head>
	3	+<title>Fossil Delta Encoding Algorithm</title>
	4	+</head>
	5	+<body bgcolor="white">
	6	+<p>[ <a href="index.html">Index</a> ]</p>
	7	+<hr>
	8	+<h1 align="center">
	9	+Fossil Delta Encoding Algorithm
	10	+</h1>
	11	+
	12	+<p>A key component for the efficient storage of multiple revisions of
	13	+a file in fossil repositories is the use of delta-compression, i.e. to
	14	+store only the changes between revisions instead of the whole
	15	+file.</p>
	16	+
	17	+<p>This document describes the encoding algorithm used by Fossil to
	18	+generate deltas. It is targeted at developers working on either
	19	+<a href="index.html">fossil</a> itself, or on tools compatible with
	20	+it. The exact format of the generated byte-sequences, while in general
	21	+not necessary to understand encoder operation, can be found in the
	22	+companion specification titled "<a href="delta_format.html">Fossil
	23	+Delta Format</a>".
	24	+</p>
	25	+
	26	+<p>The entire algorithm is inspired
	27	+by <a href="http://samba.anu.edu.au/rsync/">rsync</a>.</p>
	28	+
	29	+<a name="argresparam"><h2>1.0 Arguments, Results, and Parameters</h2>
	30	+
	31	+<p>The encoder takes two byte-sequences as input, the "original", and
	32	+the "target", and returns a single byte-sequence containing the
	33	+"delta" which transforms the original into the target upon its
	34	+application.</p>
	35	+
	36	+<p>Note that the data of a "byte-sequence" includes its length,
	37	+i.e. the number of bytes contained in the sequence.</p>
	38	+
	39	+<p>The algorithm has one parameter named "NHASH", the size of the
	40	+"sliding window" for the "rolling hash", in bytes. These two terms are
	41	+explained in the next section. The value of this parameter has to be a
	42	+power of two for the algorithm to work. For Fossil the value of this
	43	+parameter is set to "16".</p>
	44	+
	45	+<a name="operation"><h2>2.0 Operation</h2>
	46	+
	47	+<p>The algorithm is split into three phases which generate
	48	+the <a href="delta_format.html#header">header</a>,
	49	+<a href="delta_format.html#slist">segment list</a>,
	50	+and <a href="delta_format.html#trailer">trailer</a> of the delta, per
	51	+its general <a href="delta_format.html#structure">structure</a>.</p>
	52	+
	53	+<pb>... to be completed ... </bcharacter <a href="index.html<html>
	54	+<head>
	55	+<title>Fossil2>4.1 Definition</h222
	56	+<hr>
	57	+<h1 align="center">
	58	+Fossil Delta Encoding Algorithm
	59	+</h1>
	60	+
	61	+<p>A key component for the efficient storage of multiple revisions of
	62	+a file in fossil repositories is the use of delta-compression, i.e. to
	63	+store only the changes between revisions instead of the whole
	64	+file.</p>
	65	+
	66	+<p>This document describes the encoding algorithm used by Fossil to
	67	+generate deltas. It is targeted at developers working on either
	68	+<a href="index.html">fossil</a> itself, or on tools compatible with
	69	+it. The exact format of the generated byte-sequences, while in general
	70	+not necessary to understand encoder operation, can be found in the
	71	+companion specification titled "<a href="delta_format.html">Fossil
	72	+Delta Format</a>".
	73	+</p>
	74	+
	75	+<p>The entire algorithm is inspired
	76	+by <a href="http://samba.anu.edu.au/rsync/">rsync</a>.</p>
	77	+
	78	+<a name="argresparam"><h2>1.0 Arguments, Results, and Parameters</h2>
	79	+
	80	+<p>The encoder takes t<html>
	81	+<head>
	82	+<title>Fossil Delta Encoding Algorithm</title>
	83	+</head>
	84	+<body bgcolor="white">
	85	+<p>[ <a href="index.html">Index</a> ]</p>
	86	+<hr>
	87	+<h1 align="center">
	88	+Fossil Delta Encoding Algorithm
	89	+</h1>
	90	+
	91	+<p>A key component for the efficient storage of multiple revisions of
	92	+a file in fossil repositories is the use of delta-compression, i.e. to
	93	+store only the changes between revisions instead of the whole
	94	+file.</p>
	95	+
	96	+<p>This document describes the encoding algorithm used by Fossil to
	97	+generate deltas. It is targeted at developers working on either
	98	+<a href="index.html">fossil</a> itself, or on tools compatible with
	99	+it. The exact format of the generated byte-sequences, while in general
	100	+not necessary to understand encoder operation, can be found in the
	101	+companion specification titled "<a href="delta_format.html">Fossil
	102	+Delta Format</a>".
	103	+</p>
	104	+
	105	+<p>The entire algorithm is inspired
	106	+by <a href="http://samba.anu.edu.au/rsync/">rsync</a>.</p>
	107	+
	108	+<a name="argresparam"><h2>1.0 Arguments, Results, and Parameters</h2>
	109	+
	110	+<p>The encoder takes two byte-sequences as input, the "original", and
	111	+the "target", and returns a single byte-sequence containing the
	112	+"delta" which transforms the original into the target upon its
	113	+application.</p>
	114	+
	115	+<p>Note that the data of a "byte-sequence" includes its length,
	116	+i.e. the number of bytes contained in the sequence.</p>
	117	+
	118	+<p>The algorithm has one parameter named "NHASH", the size of the
	119	+"sliding window" for the "rolling hash", in bytes. These two terms are
	120	+explained in the next section. The value of this parameter has to be a
	121	+power of two for the algorithm to work. For Fossil the value of this
	122	+parameter is set to "16".</p>
	123	+
	124	+<a name="operation"><h2>2.0 Operation</h2>
	125	+
	126	+<p>The algorithm is split into three phases which generate
	127	+the <a href="delta_format.html#header">header</a>,
	128	+<a href="delta_format.html#slist">segment list</a>,
	129	+and <a href="delta_format.html#trailer">trailer</a> of the delta, per
	130	+its general <a href="delta_format.html#structure">structure</a>.</p>
	131	+
	132	+<p>The two phases generating header and trailer are not covered here
	133	+as their implementation trivially follows directly from the
	134	+specification of the <a href="delta_format.html">delta format</a>.</p>
	135	+
	136	+<p>This leaves the segment-list. Its generation is done in two phases,
	137	+a pre-processing step operating on the "original" byte-sequence,
	138	+followed by the processing of the "target" byte-sequence using the
	139	+information gathered by the first step.</p>
	140	+
	141	+<a name="preprocessing"><h3>2.1 Preprocessing the original</h3>
	142	+
	143	+<p>A major part of the processing of the "target" is to find a range
	144	+in the "original" which contains the same content as found at the
	145	+current location in the "target".</p>
	146	+
	147	+<p>A naive approach to this would be to search the whole "original"
	148	+for such content. This however is very inefficient as it would search
	149	+the same

	--- a/www/delta_encoder_algorithm.html
	+++ b/www/delta_encoder_algorithm.html
	@@ -0,0 +1,149 @@

	--- a/www/delta_encoder_algorithm.html
	+++ b/www/delta_encoder_algorithm.html
	@@ -0,0 +1,149 @@
1	<html>
2	<head>
3	<title>Fossil Delta Encoding Algorithm</title>
4	</head>
5	<body bgcolor="white">
6	<p>[ <a href="index.html">Index</a> ]</p>
7	<hr>
8	<h1 align="center">
9	Fossil Delta Encoding Algorithm
10	</h1>
11
12	<p>A key component for the efficient storage of multiple revisions of
13	a file in fossil repositories is the use of delta-compression, i.e. to
14	store only the changes between revisions instead of the whole
15	file.</p>
16
17	<p>This document describes the encoding algorithm used by Fossil to
18	generate deltas. It is targeted at developers working on either
19	<a href="index.html">fossil</a> itself, or on tools compatible with
20	it. The exact format of the generated byte-sequences, while in general
21	not necessary to understand encoder operation, can be found in the
22	companion specification titled "<a href="delta_format.html">Fossil
23	Delta Format</a>".
24	</p>
25
26	<p>The entire algorithm is inspired
27	by <a href="http://samba.anu.edu.au/rsync/">rsync</a>.</p>
28
29	<a name="argresparam"><h2>1.0 Arguments, Results, and Parameters</h2>
30
31	<p>The encoder takes two byte-sequences as input, the "original", and
32	the "target", and returns a single byte-sequence containing the
33	"delta" which transforms the original into the target upon its
34	application.</p>
35
36	<p>Note that the data of a "byte-sequence" includes its length,
37	i.e. the number of bytes contained in the sequence.</p>
38
39	<p>The algorithm has one parameter named "NHASH", the size of the
40	"sliding window" for the "rolling hash", in bytes. These two terms are
41	explained in the next section. The value of this parameter has to be a
42	power of two for the algorithm to work. For Fossil the value of this
43	parameter is set to "16".</p>
44
45	<a name="operation"><h2>2.0 Operation</h2>
46
47	<p>The algorithm is split into three phases which generate
48	the <a href="delta_format.html#header">header</a>,
49	<a href="delta_format.html#slist">segment list</a>,
50	and <a href="delta_format.html#trailer">trailer</a> of the delta, per
51	its general <a href="delta_format.html#structure">structure</a>.</p>
52
53	<pb>... to be completed ... </bcharacter <a href="index.html<html>
54	<head>
55	<title>Fossil2>4.1 Definition</h222
56	<hr>
57	<h1 align="center">
58	Fossil Delta Encoding Algorithm
59	</h1>
60
61	<p>A key component for the efficient storage of multiple revisions of
62	a file in fossil repositories is the use of delta-compression, i.e. to
63	store only the changes between revisions instead of the whole
64	file.</p>
65
66	<p>This document describes the encoding algorithm used by Fossil to
67	generate deltas. It is targeted at developers working on either
68	<a href="index.html">fossil</a> itself, or on tools compatible with
69	it. The exact format of the generated byte-sequences, while in general
70	not necessary to understand encoder operation, can be found in the
71	companion specification titled "<a href="delta_format.html">Fossil
72	Delta Format</a>".
73	</p>
74
75	<p>The entire algorithm is inspired
76	by <a href="http://samba.anu.edu.au/rsync/">rsync</a>.</p>
77
78	<a name="argresparam"><h2>1.0 Arguments, Results, and Parameters</h2>
79
80	<p>The encoder takes t<html>
81	<head>
82	<title>Fossil Delta Encoding Algorithm</title>
83	</head>
84	<body bgcolor="white">
85	<p>[ <a href="index.html">Index</a> ]</p>
86	<hr>
87	<h1 align="center">
88	Fossil Delta Encoding Algorithm
89	</h1>
90
91	<p>A key component for the efficient storage of multiple revisions of
92	a file in fossil repositories is the use of delta-compression, i.e. to
93	store only the changes between revisions instead of the whole
94	file.</p>
95
96	<p>This document describes the encoding algorithm used by Fossil to
97	generate deltas. It is targeted at developers working on either
98	<a href="index.html">fossil</a> itself, or on tools compatible with
99	it. The exact format of the generated byte-sequences, while in general
100	not necessary to understand encoder operation, can be found in the
101	companion specification titled "<a href="delta_format.html">Fossil
102	Delta Format</a>".
103	</p>
104
105	<p>The entire algorithm is inspired
106	by <a href="http://samba.anu.edu.au/rsync/">rsync</a>.</p>
107
108	<a name="argresparam"><h2>1.0 Arguments, Results, and Parameters</h2>
109
110	<p>The encoder takes two byte-sequences as input, the "original", and
111	the "target", and returns a single byte-sequence containing the
112	"delta" which transforms the original into the target upon its
113	application.</p>
114
115	<p>Note that the data of a "byte-sequence" includes its length,
116	i.e. the number of bytes contained in the sequence.</p>
117
118	<p>The algorithm has one parameter named "NHASH", the size of the
119	"sliding window" for the "rolling hash", in bytes. These two terms are
120	explained in the next section. The value of this parameter has to be a
121	power of two for the algorithm to work. For Fossil the value of this
122	parameter is set to "16".</p>
123
124	<a name="operation"><h2>2.0 Operation</h2>
125
126	<p>The algorithm is split into three phases which generate
127	the <a href="delta_format.html#header">header</a>,
128	<a href="delta_format.html#slist">segment list</a>,
129	and <a href="delta_format.html#trailer">trailer</a> of the delta, per
130	its general <a href="delta_format.html#structure">structure</a>.</p>
131
132	<p>The two phases generating header and trailer are not covered here
133	as their implementation trivially follows directly from the
134	specification of the <a href="delta_format.html">delta format</a>.</p>
135
136	<p>This leaves the segment-list. Its generation is done in two phases,
137	a pre-processing step operating on the "original" byte-sequence,
138	followed by the processing of the "target" byte-sequence using the
139	information gathered by the first step.</p>
140
141	<a name="preprocessing"><h3>2.1 Preprocessing the original</h3>
142
143	<p>A major part of the processing of the "target" is to find a range
144	in the "original" which contains the same content as found at the
145	current location in the "target".</p>
146
147	<p>A naive approach to this would be to search the whole "original"
148	for such content. This however is very inefficient as it would search
149	the same

M www/delta_format.html

+13 -11

		--- www/delta_format.html
		+++ www/delta_format.html
		@@ -1,10 +1,12 @@
1	1	<html>
2	2	<head>
3	3	<title>Fossil Delta Format</title>
4	4	</head>
5	5	<body bgcolor="white">
	6	+<p>[ <a href="index.html">Index</a> ]</p>
	7	+<hr>
6	8	<h1 align="center">
7	9	Fossil Delta Format
8	10	</h1>
9	11
10	12	<p>A key component for the efficient storage of multiple revisions of
		@@ -15,21 +17,21 @@
15	17	<p>This document describes the format used to encode such changes,
16	18	also known as "delta". It is targeted at developers working on either
17	19	<a href="index.html">fossil</a> itself, or on tools compatible with
18	20	it.</p>
19	21
20		-<h2>Structure</h2>
	22	+<a name="structure"><h2>1.0 Structure</h2>
21	23	<img src="delta1.gif" align="left" hspace="10">
22	24
23	25	<p>A delta consists of three parts, a "header", a "trailer", and a
24	26	"segment-list" between them.</p>
25	27
26	28	<p>Both header and trailer provide information about the target
27	29	helping the decoder, and the segment-list describes how the target can
28	30	be constructed from the original.</p>
29	31
30		-<h3>Header</h3>
	32	+<a name="header"><h3>1.1 Header</h3>
31	33	<img src="delta6.gif" align="left" hspace="10">
32	34
33	35	<p>The header consists of a single number followed by a newline
34	36	character (ASCII 0x0a). The number is the length of the target in
35	37	bytes.</p>
		@@ -37,11 +39,11 @@
37	39	<p>This means that, given a delta, the decoder can compute the size of
38	40	the target (and allocate any necessary memory based on that) by simply
39	41	reading the first line of the delta and decoding the number found
40	42	there. In other words, before it has to decode everything else.</p>
41	43
42		-<h3>Trailer</h3>
	44	+<a name="trailer"><h3>1.2 Trailer</h3>
43	45	<img src="delta5.gif" align="left" hspace="10">
44	46
45	47	<p>The trailer consists of a single number followed by a semicolon (ASCII
46	48	0x3b). This number is a checksum of the target and can be used by a
47	49	decoder to verify that the delta applied correctly, reconstructing the
		@@ -54,11 +56,11 @@
54	56
55	57	<p>By putting this information at the end of the delta a decoder has
56	58	it available immediately after the target has been reconstructed
57	59	fully.</p>
58	60
59		-<h3>Segment-List</h3>
	61	+<a name="slist"><h3>1.3 Segment-List</h3>
60	62	<img src="delta2.gif" align="left" hspace="10">
61	63
62	64	<p>The segment-list of a delta describes how to create the target from
63	65	the original by a combination of inserting literal byte-sequences and
64	66	copying ranges of bytes from the original. This is there the
		@@ -67,20 +69,20 @@
67	69
68	70	<p>The target is constructed from beginning to end, with the data
69	71	generated by each instruction appended after the data of all previous
70	72	instructions, with no gaps.</p>
71	73
72		-<h4>Insert Literal</h4>
	74	+<a name="insertlit"><h4>1.3.1 Insert Literal</h4>
73	75
74	76	<p>A literal is specified by two elements, the size of the literal in
75	77	bytes, and the bytes of the literal itself.</p>
76	78
77	79	<img src="delta4.gif" align="left" hspace="10">
78	80	<p>The length is written first, followed by a colon character (ASCII
79	81	0x3a), followed by the bytes of the literal.</p>
80	82
81		-<h4>Copy Range</h4>
	83	+<a name="copyrange"><h4>1.3.2 Copy Range</h4>
82	84
83	85	<p>A range to copy is specified by two numbers, the offset of the
84	86	first byte in the original to copy, and the size of the range, in
85	87	bytes. The size zero is special, its usage indicates that the range
86	88	extends to the end of the original.</p>
		@@ -87,11 +89,11 @@
87	89
88	90	<img src="delta3.gif" align="left" hspace="10">
89	91	<p>The length is written first, followed by an "at" character (ASCII
90	92	0x40), then the offset, followed by a comma (ASCII 0x2c).</p>
91	93
92		-<h2>Encoding of integers</h2>
	94	+<a name="intcoding"><h2>2.0 Encoding of integers</h2>
93	95
94	96	<p>
95	97	The format currently handles only 32 bit integer numbers. They are
96	98	written base-64 encoded, MSB first, and without leading
97	99	"0"-characters, except if they are significant (i.e. 0 => "0").
		@@ -100,13 +102,13 @@
100	102	<p>
101	103	The base-64 coding is described in
102	104	<a href="http://www.ietf.org/rfc/rfc3548.txt">RFC 3548</a>.
103	105	</p>
104	106
105		-<h2>Examples</h2>
	107	+<a name="examples"><h2>3.0 Examples</h2>
106	108
107		-<h3>Number encoding</h3>
	109	+<a name="examplesint"><h3>3.1 Integer encoding</h3>
108	110
109	111	<table border=1>
110	112	<tr>
111	113	<th>Value</th>
112	114	<th>Encoding</th>
		@@ -123,11 +125,11 @@
123	125	<td>-1101438770</td>
124	126	<td>2zMM3E</td>
125	127	</tr>
126	128	</table>
127	129
128		-<h3>Delta</h3>
	130	+<a name="examplesdelta"><h3>3.2 Delta encoding</h3>
129	131
130	132	<p>An example of a delta using the specified encoding is:</p>
131	133
132	134	<table border=1><tr><td><pre>
133	135	1Xb
		@@ -199,11 +201,11 @@
199	201
200	202	</pre></td></tr></table>
201	203
202	204
203	205
204		-<h2>Notes</h2>
	206	+<a name="notes"><h2>Notes</h2>
205	207
206	208	<ul>
207	209	<li>Pure text files generate a pure text delta.
208	210	</li>
209	211	<li>Binary files generate a delta that may contain some binary data.
210	212
211	213	ADDED www/encode1.gif
212	214	ADDED www/encode2.gif
213	215	ADDED www/encode3.gif
214	216	ADDED www/encode4.gif
215	217	ADDED www/encode5.gif
216	218	ADDED www/encode6.gif
217	219	ADDED www/encode7.gif
218	220	ADDED www/encode8.gif
219	221	ADDED www/encode9.gif

	--- www/delta_format.html
	+++ www/delta_format.html
	@@ -1,10 +1,12 @@
1	<html>
2	<head>
3	<title>Fossil Delta Format</title>
4	</head>
5	<body bgcolor="white">


6	<h1 align="center">
7	Fossil Delta Format
8	</h1>
9
10	<p>A key component for the efficient storage of multiple revisions of
	@@ -15,21 +17,21 @@
15	<p>This document describes the format used to encode such changes,
16	also known as "delta". It is targeted at developers working on either
17	<a href="index.html">fossil</a> itself, or on tools compatible with
18	it.</p>
19
20	<h2>Structure</h2>
21	<img src="delta1.gif" align="left" hspace="10">
22
23	<p>A delta consists of three parts, a "header", a "trailer", and a
24	"segment-list" between them.</p>
25
26	<p>Both header and trailer provide information about the target
27	helping the decoder, and the segment-list describes how the target can
28	be constructed from the original.</p>
29
30	<h3>Header</h3>
31	<img src="delta6.gif" align="left" hspace="10">
32
33	<p>The header consists of a single number followed by a newline
34	character (ASCII 0x0a). The number is the length of the target in
35	bytes.</p>
	@@ -37,11 +39,11 @@
37	<p>This means that, given a delta, the decoder can compute the size of
38	the target (and allocate any necessary memory based on that) by simply
39	reading the first line of the delta and decoding the number found
40	there. In other words, before it has to decode everything else.</p>
41
42	<h3>Trailer</h3>
43	<img src="delta5.gif" align="left" hspace="10">
44
45	<p>The trailer consists of a single number followed by a semicolon (ASCII
46	0x3b). This number is a checksum of the target and can be used by a
47	decoder to verify that the delta applied correctly, reconstructing the
	@@ -54,11 +56,11 @@
54
55	<p>By putting this information at the end of the delta a decoder has
56	it available immediately after the target has been reconstructed
57	fully.</p>
58
59	<h3>Segment-List</h3>
60	<img src="delta2.gif" align="left" hspace="10">
61
62	<p>The segment-list of a delta describes how to create the target from
63	the original by a combination of inserting literal byte-sequences and
64	copying ranges of bytes from the original. This is there the
	@@ -67,20 +69,20 @@
67
68	<p>The target is constructed from beginning to end, with the data
69	generated by each instruction appended after the data of all previous
70	instructions, with no gaps.</p>
71
72	<h4>Insert Literal</h4>
73
74	<p>A literal is specified by two elements, the size of the literal in
75	bytes, and the bytes of the literal itself.</p>
76
77	<img src="delta4.gif" align="left" hspace="10">
78	<p>The length is written first, followed by a colon character (ASCII
79	0x3a), followed by the bytes of the literal.</p>
80
81	<h4>Copy Range</h4>
82
83	<p>A range to copy is specified by two numbers, the offset of the
84	first byte in the original to copy, and the size of the range, in
85	bytes. The size zero is special, its usage indicates that the range
86	extends to the end of the original.</p>
	@@ -87,11 +89,11 @@
87
88	<img src="delta3.gif" align="left" hspace="10">
89	<p>The length is written first, followed by an "at" character (ASCII
90	0x40), then the offset, followed by a comma (ASCII 0x2c).</p>
91
92	<h2>Encoding of integers</h2>
93
94	<p>
95	The format currently handles only 32 bit integer numbers. They are
96	written base-64 encoded, MSB first, and without leading
97	"0"-characters, except if they are significant (i.e. 0 => "0").
	@@ -100,13 +102,13 @@
100	<p>
101	The base-64 coding is described in
102	<a href="http://www.ietf.org/rfc/rfc3548.txt">RFC 3548</a>.
103	</p>
104
105	<h2>Examples</h2>
106
107	<h3>Number encoding</h3>
108
109	<table border=1>
110	<tr>
111	<th>Value</th>
112	<th>Encoding</th>
	@@ -123,11 +125,11 @@
123	<td>-1101438770</td>
124	<td>2zMM3E</td>
125	</tr>
126	</table>
127
128	<h3>Delta</h3>
129
130	<p>An example of a delta using the specified encoding is:</p>
131
132	<table border=1><tr><td><pre>
133	1Xb
	@@ -199,11 +201,11 @@
199
200	</pre></td></tr></table>
201
202
203
204	<h2>Notes</h2>
205
206	<ul>
207	<li>Pure text files generate a pure text delta.
208	</li>
209	<li>Binary files generate a delta that may contain some binary data.
210
211	DDED www/encode1.gif
212	DDED www/encode2.gif
213	DDED www/encode3.gif
214	DDED www/encode4.gif
215	DDED www/encode5.gif
216	DDED www/encode6.gif
217	DDED www/encode7.gif
218	DDED www/encode8.gif
219	DDED www/encode9.gif

	--- www/delta_format.html
	+++ www/delta_format.html
	@@ -1,10 +1,12 @@
1	<html>
2	<head>
3	<title>Fossil Delta Format</title>
4	</head>
5	<body bgcolor="white">
6	<p>[ <a href="index.html">Index</a> ]</p>
7	<hr>
8	<h1 align="center">
9	Fossil Delta Format
10	</h1>
11
12	<p>A key component for the efficient storage of multiple revisions of
	@@ -15,21 +17,21 @@
17	<p>This document describes the format used to encode such changes,
18	also known as "delta". It is targeted at developers working on either
19	<a href="index.html">fossil</a> itself, or on tools compatible with
20	it.</p>
21
22	<a name="structure"><h2>1.0 Structure</h2>
23	<img src="delta1.gif" align="left" hspace="10">
24
25	<p>A delta consists of three parts, a "header", a "trailer", and a
26	"segment-list" between them.</p>
27
28	<p>Both header and trailer provide information about the target
29	helping the decoder, and the segment-list describes how the target can
30	be constructed from the original.</p>
31
32	<a name="header"><h3>1.1 Header</h3>
33	<img src="delta6.gif" align="left" hspace="10">
34
35	<p>The header consists of a single number followed by a newline
36	character (ASCII 0x0a). The number is the length of the target in
37	bytes.</p>
	@@ -37,11 +39,11 @@
39	<p>This means that, given a delta, the decoder can compute the size of
40	the target (and allocate any necessary memory based on that) by simply
41	reading the first line of the delta and decoding the number found
42	there. In other words, before it has to decode everything else.</p>
43
44	<a name="trailer"><h3>1.2 Trailer</h3>
45	<img src="delta5.gif" align="left" hspace="10">
46
47	<p>The trailer consists of a single number followed by a semicolon (ASCII
48	0x3b). This number is a checksum of the target and can be used by a
49	decoder to verify that the delta applied correctly, reconstructing the
	@@ -54,11 +56,11 @@
56
57	<p>By putting this information at the end of the delta a decoder has
58	it available immediately after the target has been reconstructed
59	fully.</p>
60
61	<a name="slist"><h3>1.3 Segment-List</h3>
62	<img src="delta2.gif" align="left" hspace="10">
63
64	<p>The segment-list of a delta describes how to create the target from
65	the original by a combination of inserting literal byte-sequences and
66	copying ranges of bytes from the original. This is there the
	@@ -67,20 +69,20 @@
69
70	<p>The target is constructed from beginning to end, with the data
71	generated by each instruction appended after the data of all previous
72	instructions, with no gaps.</p>
73
74	<a name="insertlit"><h4>1.3.1 Insert Literal</h4>
75
76	<p>A literal is specified by two elements, the size of the literal in
77	bytes, and the bytes of the literal itself.</p>
78
79	<img src="delta4.gif" align="left" hspace="10">
80	<p>The length is written first, followed by a colon character (ASCII
81	0x3a), followed by the bytes of the literal.</p>
82
83	<a name="copyrange"><h4>1.3.2 Copy Range</h4>
84
85	<p>A range to copy is specified by two numbers, the offset of the
86	first byte in the original to copy, and the size of the range, in
87	bytes. The size zero is special, its usage indicates that the range
88	extends to the end of the original.</p>
	@@ -87,11 +89,11 @@
89
90	<img src="delta3.gif" align="left" hspace="10">
91	<p>The length is written first, followed by an "at" character (ASCII
92	0x40), then the offset, followed by a comma (ASCII 0x2c).</p>
93
94	<a name="intcoding"><h2>2.0 Encoding of integers</h2>
95
96	<p>
97	The format currently handles only 32 bit integer numbers. They are
98	written base-64 encoded, MSB first, and without leading
99	"0"-characters, except if they are significant (i.e. 0 => "0").
	@@ -100,13 +102,13 @@
102	<p>
103	The base-64 coding is described in
104	<a href="http://www.ietf.org/rfc/rfc3548.txt">RFC 3548</a>.
105	</p>
106
107	<a name="examples"><h2>3.0 Examples</h2>
108
109	<a name="examplesint"><h3>3.1 Integer encoding</h3>
110
111	<table border=1>
112	<tr>
113	<th>Value</th>
114	<th>Encoding</th>
	@@ -123,11 +125,11 @@
125	<td>-1101438770</td>
126	<td>2zMM3E</td>
127	</tr>
128	</table>
129
130	<a name="examplesdelta"><h3>3.2 Delta encoding</h3>
131
132	<p>An example of a delta using the specified encoding is:</p>
133
134	<table border=1><tr><td><pre>
135	1Xb
	@@ -199,11 +201,11 @@
201
202	</pre></td></tr></table>
203
204
205
206	<a name="notes"><h2>Notes</h2>
207
208	<ul>
209	<li>Pure text files generate a pure text delta.
210	</li>
211	<li>Binary files generate a delta that may contain some binary data.
212
213	DDED www/encode1.gif
214	DDED www/encode2.gif
215	DDED www/encode3.gif
216	DDED www/encode4.gif
217	DDED www/encode5.gif
218	DDED www/encode6.gif
219	DDED www/encode7.gif
220	DDED www/encode8.gif
221	DDED www/encode9.gif

A www/encode1.gif

Binary file

A www/encode2.gif

Binary file

A www/encode3.gif

Binary file

A www/encode4.gif

Binary file

A www/encode5.gif

Binary file

A www/encode6.gif

Binary file

A www/encode7.gif

Binary file

A www/encode8.gif

Binary file

A www/encode9.gif

Binary file

M www/index.html

+2

		--- www/index.html
		+++ www/index.html
		@@ -88,9 +88,11 @@
88	88	helps insure project integrity.</li>
89	89	<li>The <a href="fileformat.html">file format</a> used by every content
90	90	file stored in the repository.</li>
91	91	<li>The <a href="delta_format.html">format of deltas</a> used to
92	92	efficiently store changes between file revisions.</li>
	93	+<li>The <a href="delta_encoder_algorithm.html">encoder algorithm</a> used to
	94	+efficiently generate deltas.</li>
93	95	</ul>
94	96
95	97	</body>
96	98	</html>
97	99

	--- www/index.html
	+++ www/index.html
	@@ -88,9 +88,11 @@
88	helps insure project integrity.</li>
89	<li>The <a href="fileformat.html">file format</a> used by every content
90	file stored in the repository.</li>
91	<li>The <a href="delta_format.html">format of deltas</a> used to
92	efficiently store changes between file revisions.</li>


93	</ul>
94
95	</body>
96	</html>
97

	--- www/index.html
	+++ www/index.html
	@@ -88,9 +88,11 @@
88	helps insure project integrity.</li>
89	<li>The <a href="fileformat.html">file format</a> used by every content
90	file stored in the repository.</li>
91	<li>The <a href="delta_format.html">format of deltas</a> used to
92	efficiently store changes between file revisions.</li>
93	<li>The <a href="delta_encoder_algorithm.html">encoder algorithm</a> used to
94	efficiently generate deltas.</li>
95	</ul>
96
97	</body>
98	</html>
99

Fossil SCM

Keyboard Shortcuts