@@ -1,4 +1,5 @@
+<nowiki>
<h1 align="center">
Fossil Delta Encoding Algorithm
</h1>
@@ -8,19 +9,19 @@
file.</p>
<p>This document describes the encoding algorithm used by Fossil to
generate deltas. It is targeted at developers working on either
-<a href="index.html">fossil</a> itself, or on tools compatible with
+<a href="index.wiki">fossil</a> itself, or on tools compatible with
it. The exact format of the generated byte-sequences, while in general
not necessary to understand encoder operation, can be found in the
-companion specification titled "<a href="delta_format.html">Fossil
+companion specification titled "<a href="delta_format.wiki">Fossil
Delta Format</a>".
</p>
<p>The entire algorithm is inspired
by <a href="http://samba.anu.edu.au/rsync/">rsync</a>.</p>
-<a name="argresparam"><h2>1.0 Arguments, Results, and Parameters</h2>
+<a name="argresparam"></a><h2>1.0 Arguments, Results, and Parameters</h2>
<p>The encoder takes two byte-sequences as input, the "original", and
the "target", and returns a single byte-sequence containing the
"delta" which transforms the original into the target upon its
@@ -34,26 +35,26 @@
explained in the next section. The value of this parameter has to be a
power of two for the algorithm to work. For Fossil the value of this
parameter is set to "16".</p>
-<a name="operation"><h2>2.0 Operation</h2>
+<a name="operation"></a><h2>2.0 Operation</h2>
<p>The algorithm is split into three phases which generate
-the <a href="delta_format.html#header">header</a>,
-<a href="delta_format.html#slist">segment list</a>,
-and <a href="delta_format.html#trailer">trailer</a> of the delta, per
-its general <a href="delta_format.html#structure">structure</a>.</p>
+the <a href="delta_format.wiki#header">header</a>,
+<a href="delta_format.wiki#slist">segment list</a>,
+and <a href="delta_format.wiki#trailer">trailer</a> of the delta, per
+its general <a href="delta_format.wiki#structure">structure</a>.</p>
<p>The two phases generating header and trailer are not covered here
as their implementation trivially follows directly from the
-specification of the <a href="delta_format.html">delta format</a>.</p>
+specification of the <a href="delta_format.wiki">delta format</a>.</p>
<p>This leaves the segment-list. Its generation is done in two phases,
a pre-processing step operating on the "original" byte-sequence,
followed by the processing of the "target" byte-sequence using the
information gathered by the first step.</p>
-<a name="preprocessing"><h3>2.1 Preprocessing the original</h3>
+<a name="preprocessing"></a><h3>2.1 Preprocessing the original</h3>
<p>A major part of the processing of the "target" is to find a range
in the "original" which contains the same content as found at the
current location in the "target".</p>
@@ -84,9 +85,9 @@
the list of chunk locations having this hash.
</li>
</ol>
-<a name="processing"><h3>2.1 Processing the target</h3>
+<a name="processing"></a><h3>2.1 Processing the target</h3>
<p>This, the main phase of the encoder, processes the target in a loop
from beginning to end. The state of the encoder is captured by two
locations, the "base" and the "slide". "base" points to the first byte
@@ -97,13 +98,13 @@
<p>Initially both "base" and "slide" point to the beginning of the
"target". In each iteration of the loop the encoder decides whether to
<ul>
<li>emit a single instruction
-to <a href="delta_format.html#copyrange">copy a range</a>, or
+to <a href="delta_format.wiki#copyrange">copy a range</a>, or
</li>
<li>emit two instructions, first
-to <a href="delta_format.html#insertlit">insert a literal</a>, then
-to <a href="delta_format.html#copyrange">copy a range</a>, or
+to <a href="delta_format.wiki#insertlit">insert a literal</a>, then
+to <a href="delta_format.wiki#copyrange">copy a range</a>, or
</li>
<li>move the window forward one byte.
</li>
</ul>
@@ -168,9 +169,9 @@
exactly at the end of the "target", as is possible for both end
conditions, then one last insert instruction is emitted to put these
bytes into the delta.<p>
-<a name="exceptions"><h2>3.0 Exceptions</h2>
+<a name="exceptions"></a><h2>3.0 Exceptions</h2>
<p>If the "original" is at most NHASH bytes long no compression of
changes is possible, and the segment-list of the delta consists of a
single literal which contains the entire "target".</p>
@@ -178,17 +179,17 @@
<p>This is actually equivalent to the second end condition of the
processing loop described in the previous section, just checked before
actually entering the loop.</p>
-<a name="rollhash"><h2>4.0 The rolling hash</h2>
+<a name="rollhash"></a><h2>4.0 The rolling hash</h2>
<p>The rolling hash described below and used to compute content
signatures was chosen not only for good hashing properties, but also
to enable the easy (incremental) recalculation of its value for a
sliding window, i.e. where the oldest byte is removed from the window
and a new byte is shifted in.<p>
-<a name="rhdef"><h3>4.1 Definition</h3>
+<a name="rhdef"></a><h3>4.1 Definition</h3>
<p>Assuming an array Z of NHASH bytes (indexing starting at 0) the
hash V is computed via</p>
@@ -200,9 +201,9 @@
where A and B are unsigned 16-bit integers (hence the <u>mod</u>), and
V is a 32-bit unsigned integer with B as MSB, A as LSB.
-<a name="rhincr"><h3>4.2 Incremental recalculation</h3>
+<a name="rhincr"></a><h3>4.2 Incremental recalculation</h3>
<p>Assuming an array Z of NHASH bytes (indexing starting at 0) with
hash V (and components A and B), the dropped
byte <img src="encode4.gif" align="center">, and the new byte