0000: 3c 74 69 74 6c 65 3e 46 6f 73 73 69 6c 20 44 65 <title>Fossil De
0010: 6c 74 61 20 45 6e 63 6f 64 69 6e 67 20 41 6c 67 lta Encoding Alg
0020: 6f 72 69 74 68 6d 3c 2f 74 69 74 6c 65 3e 0a 3c orithm</title>.<
0030: 6e 6f 77 69 6b 69 3e 0a 3c 68 32 3e 41 62 73 74 nowiki>.<h2>Abst
0040: 72 61 63 74 3c 2f 68 32 3e 0a 0a 3c 70 3e 41 20 ract</h2>..<p>A
0050: 6b 65 79 20 63 6f 6d 70 6f 6e 65 6e 74 20 66 6f key component fo
0060: 72 20 74 68 65 20 65 66 66 69 63 69 65 6e 74 20 r the efficient
0070: 73 74 6f 72 61 67 65 20 6f 66 20 6d 75 6c 74 69 storage of multi
0080: 70 6c 65 20 72 65 76 69 73 69 6f 6e 73 20 6f 66 ple revisions of
0090: 0a 61 20 66 69 6c 65 20 69 6e 20 66 6f 73 73 69 .a file in fossi
00a0: 6c 20 72 65 70 6f 73 69 74 6f 72 69 65 73 20 69 l repositories i
00b0: 73 20 74 68 65 20 75 73 65 20 6f 66 20 64 65 6c s the use of del
00c0: 74 61 2d 63 6f 6d 70 72 65 73 73 69 6f 6e 2c 20 ta-compression,
00d0: 69 2e 65 2e 20 74 6f 0a 73 74 6f 72 65 20 6f 6e i.e. to.store on
00e0: 6c 79 20 74 68 65 20 63 68 61 6e 67 65 73 20 62 ly the changes b
00f0: 65 74 77 65 65 6e 20 72 65 76 69 73 69 6f 6e 73 etween revisions
0100: 20 69 6e 73 74 65 61 64 20 6f 66 20 74 68 65 20 instead of the
0110: 77 68 6f 6c 65 0a 66 69 6c 65 2e 3c 2f 70 3e 0a whole.file.</p>.
0120: 0a 3c 70 3e 54 68 69 73 20 64 6f 63 75 6d 65 6e .<p>This documen
0130: 74 20 64 65 73 63 72 69 62 65 73 20 74 68 65 20 t describes the
0140: 65 6e 63 6f 64 69 6e 67 20 61 6c 67 6f 72 69 74 encoding algorit
0150: 68 6d 20 75 73 65 64 20 62 79 20 46 6f 73 73 69 hm used by Fossi
0160: 6c 20 74 6f 0a 67 65 6e 65 72 61 74 65 20 64 65 l to.generate de
0170: 6c 74 61 73 2e 20 49 74 20 69 73 20 74 61 72 67 ltas. It is targ
0180: 65 74 65 64 20 61 74 20 64 65 76 65 6c 6f 70 65 eted at develope
0190: 72 73 20 77 6f 72 6b 69 6e 67 20 6f 6e 20 65 69 rs working on ei
01a0: 74 68 65 72 0a 3c 61 20 68 72 65 66 3d 22 69 6e ther.<a href="in
01b0: 64 65 78 2e 77 69 6b 69 22 3e 66 6f 73 73 69 6c dex.wiki">fossil
01c0: 3c 2f 61 3e 20 69 74 73 65 6c 66 2c 20 6f 72 20 </a> itself, or
01d0: 6f 6e 20 74 6f 6f 6c 73 20 63 6f 6d 70 61 74 69 on tools compati
01e0: 62 6c 65 20 77 69 74 68 0a 69 74 2e 20 54 68 65 ble with.it. The
01f0: 20 65 78 61 63 74 20 66 6f 72 6d 61 74 20 6f 66 exact format of
0200: 20 74 68 65 20 67 65 6e 65 72 61 74 65 64 20 62 the generated b
0210: 79 74 65 2d 73 65 71 75 65 6e 63 65 73 2c 20 77 yte-sequences, w
0220: 68 69 6c 65 20 69 6e 20 67 65 6e 65 72 61 6c 0a hile in general.
0230: 6e 6f 74 20 6e 65 63 65 73 73 61 72 79 20 74 6f not necessary to
0240: 20 75 6e 64 65 72 73 74 61 6e 64 20 65 6e 63 6f understand enco
0250: 64 65 72 20 6f 70 65 72 61 74 69 6f 6e 2c 20 63 der operation, c
0260: 61 6e 20 62 65 20 66 6f 75 6e 64 20 69 6e 20 74 an be found in t
0270: 68 65 0a 63 6f 6d 70 61 6e 69 6f 6e 20 73 70 65 he.companion spe
0280: 63 69 66 69 63 61 74 69 6f 6e 20 74 69 74 6c 65 cification title
0290: 64 20 22 3c 61 20 68 72 65 66 3d 22 64 65 6c 74 d "<a href="delt
02a0: 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 22 3e 46 a_format.wiki">F
02b0: 6f 73 73 69 6c 0a 44 65 6c 74 61 20 46 6f 72 6d ossil.Delta Form
02c0: 61 74 3c 2f 61 3e 22 2e 0a 3c 2f 70 3e 0a 0a 3c at</a>"..</p>..<
02d0: 70 3e 54 68 65 20 61 6c 67 6f 72 69 74 68 6d 20 p>The algorithm
02e0: 69 73 20 69 6e 73 70 69 72 65 64 0a 62 79 20 3c is inspired.by <
02f0: 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f 2f 73 a href="http://s
0300: 61 6d 62 61 2e 61 6e 75 2e 65 64 75 2e 61 75 2f amba.anu.edu.au/
0310: 72 73 79 6e 63 2f 22 3e 72 73 79 6e 63 3c 2f 61 rsync/">rsync</a
0320: 3e 2e 3c 2f 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d >.</p>..<a name=
0330: 22 61 72 67 72 65 73 70 61 72 61 6d 22 3e 3c 2f "argresparam"></
0340: 61 3e 3c 68 32 3e 31 2e 30 20 41 72 67 75 6d 65 a><h2>1.0 Argume
0350: 6e 74 73 2c 20 52 65 73 75 6c 74 73 2c 20 61 6e nts, Results, an
0360: 64 20 50 61 72 61 6d 65 74 65 72 73 3c 2f 68 32 d Parameters</h2
0370: 3e 0a 0a 3c 70 3e 54 68 65 20 65 6e 63 6f 64 65 >..<p>The encode
0380: 72 20 74 61 6b 65 73 20 74 77 6f 20 62 79 74 65 r takes two byte
0390: 2d 73 65 71 75 65 6e 63 65 73 20 61 73 20 69 6e -sequences as in
03a0: 70 75 74 2c 20 74 68 65 20 22 6f 72 69 67 69 6e put, the "origin
03b0: 61 6c 22 2c 20 61 6e 64 0a 74 68 65 20 22 74 61 al", and.the "ta
03c0: 72 67 65 74 22 2c 20 61 6e 64 20 72 65 74 75 72 rget", and retur
03d0: 6e 73 20 61 20 73 69 6e 67 6c 65 20 62 79 74 65 ns a single byte
03e0: 2d 73 65 71 75 65 6e 63 65 20 63 6f 6e 74 61 69 -sequence contai
03f0: 6e 69 6e 67 20 74 68 65 0a 22 64 65 6c 74 61 22 ning the."delta"
0400: 20 77 68 69 63 68 20 74 72 61 6e 73 66 6f 72 6d which transform
0410: 73 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 69 s the original i
0420: 6e 74 6f 20 74 68 65 20 74 61 72 67 65 74 20 75 nto the target u
0430: 70 6f 6e 20 69 74 73 0a 61 70 70 6c 69 63 61 74 pon its.applicat
0440: 69 6f 6e 2e 3c 2f 70 3e 0a 0a 3c 70 3e 4e 6f 74 ion.</p>..<p>Not
0450: 65 20 74 68 61 74 20 74 68 65 20 64 61 74 61 20 e that the data
0460: 6f 66 20 61 20 22 62 79 74 65 2d 73 65 71 75 65 of a "byte-seque
0470: 6e 63 65 22 20 69 6e 63 6c 75 64 65 73 20 69 74 nce" includes it
0480: 73 20 6c 65 6e 67 74 68 2c 0a 69 2e 65 2e 20 74 s length,.i.e. t
0490: 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 he number of byt
04a0: 65 73 20 63 6f 6e 74 61 69 6e 65 64 20 69 6e 20 es contained in
04b0: 74 68 65 20 73 65 71 75 65 6e 63 65 2e 3c 2f 70 the sequence.</p
04c0: 3e 0a 0a 3c 70 3e 54 68 65 20 61 6c 67 6f 72 69 >..<p>The algori
04d0: 74 68 6d 20 68 61 73 20 6f 6e 65 20 70 61 72 61 thm has one para
04e0: 6d 65 74 65 72 20 6e 61 6d 65 64 20 22 4e 48 41 meter named "NHA
04f0: 53 48 22 2c 20 74 68 65 20 73 69 7a 65 20 6f 66 SH", the size of
0500: 20 74 68 65 0a 22 73 6c 69 64 69 6e 67 20 77 69 the."sliding wi
0510: 6e 64 6f 77 22 20 66 6f 72 20 74 68 65 20 22 72 ndow" for the "r
0520: 6f 6c 6c 69 6e 67 20 68 61 73 68 22 2c 20 69 6e olling hash", in
0530: 20 62 79 74 65 73 2e 20 54 68 65 73 65 20 74 77 bytes. These tw
0540: 6f 20 74 65 72 6d 73 20 61 72 65 0a 65 78 70 6c o terms are.expl
0550: 61 69 6e 65 64 20 69 6e 20 74 68 65 20 6e 65 78 ained in the nex
0560: 74 20 73 65 63 74 69 6f 6e 2e 20 54 68 65 20 76 t section. The v
0570: 61 6c 75 65 20 6f 66 20 74 68 69 73 20 70 61 72 alue of this par
0580: 61 6d 65 74 65 72 20 68 61 73 20 74 6f 20 62 65 ameter has to be
0590: 20 61 0a 70 6f 77 65 72 20 6f 66 20 74 77 6f 20 a.power of two
05a0: 66 6f 72 20 74 68 65 20 61 6c 67 6f 72 69 74 68 for the algorith
05b0: 6d 20 74 6f 20 77 6f 72 6b 2e 20 46 6f 72 20 46 m to work. For F
05c0: 6f 73 73 69 6c 20 74 68 65 20 76 61 6c 75 65 20 ossil the value
05d0: 6f 66 20 74 68 69 73 0a 70 61 72 61 6d 65 74 65 of this.paramete
05e0: 72 20 69 73 20 73 65 74 20 74 6f 20 22 31 36 22 r is set to "16"
05f0: 2e 3c 2f 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 .</p>..<a name="
0600: 6f 70 65 72 61 74 69 6f 6e 22 3e 3c 2f 61 3e 3c operation"></a><
0610: 68 32 3e 32 2e 30 20 4f 70 65 72 61 74 69 6f 6e h2>2.0 Operation
0620: 3c 2f 68 32 3e 0a 0a 3c 70 3e 54 68 65 20 61 6c </h2>..<p>The al
0630: 67 6f 72 69 74 68 6d 20 69 73 20 73 70 6c 69 74 gorithm is split
0640: 20 69 6e 74 6f 20 74 68 72 65 65 20 70 68 61 73 into three phas
0650: 65 73 20 77 68 69 63 68 20 67 65 6e 65 72 61 74 es which generat
0660: 65 0a 74 68 65 20 3c 61 20 68 72 65 66 3d 22 64 e.the <a href="d
0670: 65 6c 74 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 elta_format.wiki
0680: 23 68 65 61 64 65 72 22 3e 68 65 61 64 65 72 3c #header">header<
0690: 2f 61 3e 2c 0a 3c 61 20 68 72 65 66 3d 22 64 65 /a>,.<a href="de
06a0: 6c 74 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 23 lta_format.wiki#
06b0: 73 6c 69 73 74 22 3e 73 65 67 6d 65 6e 74 20 6c slist">segment l
06c0: 69 73 74 3c 2f 61 3e 2c 0a 61 6e 64 20 3c 61 20 ist</a>,.and <a
06d0: 68 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d href="delta_form
06e0: 61 74 2e 77 69 6b 69 23 74 72 61 69 6c 65 72 22 at.wiki#trailer"
06f0: 3e 74 72 61 69 6c 65 72 3c 2f 61 3e 20 6f 66 20 >trailer</a> of
0700: 74 68 65 20 64 65 6c 74 61 2c 20 70 65 72 0a 69 the delta, per.i
0710: 74 73 20 67 65 6e 65 72 61 6c 20 3c 61 20 68 72 ts general <a hr
0720: 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 74 ef="delta_format
0730: 2e 77 69 6b 69 23 73 74 72 75 63 74 75 72 65 22 .wiki#structure"
0740: 3e 73 74 72 75 63 74 75 72 65 3c 2f 61 3e 2e 3c >structure</a>.<
0750: 2f 70 3e 0a 0a 3c 70 3e 54 68 65 20 74 77 6f 20 /p>..<p>The two
0760: 70 68 61 73 65 73 20 67 65 6e 65 72 61 74 69 6e phases generatin
0770: 67 20 68 65 61 64 65 72 20 61 6e 64 20 74 72 61 g header and tra
0780: 69 6c 65 72 20 61 72 65 20 6e 6f 74 20 63 6f 76 iler are not cov
0790: 65 72 65 64 20 68 65 72 65 0a 61 73 20 74 68 65 ered here.as the
07a0: 69 72 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f ir implementatio
07b0: 6e 20 74 72 69 76 69 61 6c 6c 79 20 66 6f 6c 6c n trivially foll
07c0: 6f 77 73 20 64 69 72 65 63 74 6c 79 20 66 72 6f ows directly fro
07d0: 6d 20 74 68 65 0a 73 70 65 63 69 66 69 63 61 74 m the.specificat
07e0: 69 6f 6e 20 6f 66 20 74 68 65 20 3c 61 20 68 72 ion of the <a hr
07f0: 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 74 ef="delta_format
0800: 2e 77 69 6b 69 22 3e 64 65 6c 74 61 20 66 6f 72 .wiki">delta for
0810: 6d 61 74 3c 2f 61 3e 2e 3c 2f 70 3e 0a 0a 3c 70 mat</a>.</p>..<p
0820: 3e 54 68 69 73 20 6c 65 61 76 65 73 20 74 68 65 >This leaves the
0830: 20 73 65 67 6d 65 6e 74 2d 6c 69 73 74 2e 20 49 segment-list. I
0840: 74 73 20 67 65 6e 65 72 61 74 69 6f 6e 20 69 73 ts generation is
0850: 20 64 6f 6e 65 20 69 6e 20 74 77 6f 20 70 68 61 done in two pha
0860: 73 65 73 2c 0a 61 20 70 72 65 2d 70 72 6f 63 65 ses,.a pre-proce
0870: 73 73 69 6e 67 20 73 74 65 70 20 6f 70 65 72 61 ssing step opera
0880: 74 69 6e 67 20 6f 6e 20 74 68 65 20 22 6f 72 69 ting on the "ori
0890: 67 69 6e 61 6c 22 20 62 79 74 65 2d 73 65 71 75 ginal" byte-sequ
08a0: 65 6e 63 65 2c 0a 66 6f 6c 6c 6f 77 65 64 20 62 ence,.followed b
08b0: 79 20 74 68 65 20 70 72 6f 63 65 73 73 69 6e 67 y the processing
08c0: 20 6f 66 20 74 68 65 20 22 74 61 72 67 65 74 22 of the "target"
08d0: 20 62 79 74 65 2d 73 65 71 75 65 6e 63 65 20 75 byte-sequence u
08e0: 73 69 6e 67 20 74 68 65 0a 69 6e 66 6f 72 6d 61 sing the.informa
08f0: 74 69 6f 6e 20 67 61 74 68 65 72 65 64 20 62 79 tion gathered by
0900: 20 74 68 65 20 66 69 72 73 74 20 73 74 65 70 2e the first step.
0910: 3c 2f 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 70 </p>..<a name="p
0920: 72 65 70 72 6f 63 65 73 73 69 6e 67 22 3e 3c 2f reprocessing"></
0930: 61 3e 3c 68 33 3e 32 2e 31 20 50 72 65 70 72 6f a><h3>2.1 Prepro
0940: 63 65 73 73 69 6e 67 20 74 68 65 20 6f 72 69 67 cessing the orig
0950: 69 6e 61 6c 3c 2f 68 33 3e 0a 0a 3c 70 3e 41 20 inal</h3>..<p>A
0960: 6d 61 6a 6f 72 20 70 61 72 74 20 6f 66 20 74 68 major part of th
0970: 65 20 70 72 6f 63 65 73 73 69 6e 67 20 6f 66 20 e processing of
0980: 74 68 65 20 22 74 61 72 67 65 74 22 20 69 73 20 the "target" is
0990: 74 6f 20 66 69 6e 64 20 61 20 72 61 6e 67 65 0a to find a range.
09a0: 69 6e 20 74 68 65 20 22 6f 72 69 67 69 6e 61 6c in the "original
09b0: 22 20 77 68 69 63 68 20 63 6f 6e 74 61 69 6e 73 " which contains
09c0: 20 74 68 65 20 73 61 6d 65 20 63 6f 6e 74 65 6e the same conten
09d0: 74 20 61 73 20 66 6f 75 6e 64 20 61 74 20 74 68 t as found at th
09e0: 65 0a 63 75 72 72 65 6e 74 20 6c 6f 63 61 74 69 e.current locati
09f0: 6f 6e 20 69 6e 20 74 68 65 20 22 74 61 72 67 65 on in the "targe
0a00: 74 22 2e 3c 2f 70 3e 0a 0a 3c 70 3e 41 20 6e 61 t".</p>..<p>A na
0a10: 69 76 65 20 61 70 70 72 6f 61 63 68 20 74 6f 20 ive approach to
0a20: 74 68 69 73 20 77 6f 75 6c 64 20 62 65 20 74 6f this would be to
0a30: 20 73 65 61 72 63 68 20 74 68 65 20 77 68 6f 6c search the whol
0a40: 65 20 22 6f 72 69 67 69 6e 61 6c 22 0a 66 6f 72 e "original".for
0a50: 20 73 75 63 68 20 63 6f 6e 74 65 6e 74 2e 20 54 such content. T
0a60: 68 69 73 20 68 6f 77 65 76 65 72 20 69 73 20 76 his however is v
0a70: 65 72 79 20 69 6e 65 66 66 69 63 69 65 6e 74 20 ery inefficient
0a80: 61 73 20 69 74 20 77 6f 75 6c 64 20 73 65 61 72 as it would sear
0a90: 63 68 0a 74 68 65 20 73 61 6d 65 20 70 61 72 74 ch.the same part
0aa0: 73 20 6f 66 20 74 68 65 20 22 6f 72 69 67 69 6e s of the "origin
0ab0: 61 6c 22 20 6f 76 65 72 20 61 6e 64 20 6f 76 65 al" over and ove
0ac0: 72 2e 20 57 68 61 74 20 69 73 20 64 6f 6e 65 20 r. What is done
0ad0: 69 6e 73 74 65 61 64 0a 69 73 20 74 6f 20 73 61 instead.is to sa
0ae0: 6d 70 6c 65 20 74 68 65 20 22 6f 72 69 67 69 6e mple the "origin
0af0: 61 6c 22 20 61 74 20 72 65 67 75 6c 61 72 20 69 al" at regular i
0b00: 6e 74 65 72 76 61 6c 73 2c 20 63 6f 6d 70 75 74 ntervals, comput
0b10: 65 20 73 69 67 6e 61 74 75 72 65 73 0a 66 6f 72 e signatures.for
0b20: 20 74 68 65 20 73 61 6d 70 6c 65 64 20 6c 6f 63 the sampled loc
0b30: 61 74 69 6f 6e 73 20 61 6e 64 20 73 74 6f 72 65 ations and store
0b40: 20 74 68 65 6d 20 69 6e 20 61 20 68 61 73 68 20 them in a hash
0b50: 74 61 62 6c 65 20 6b 65 79 65 64 20 62 79 0a 74 table keyed by.t
0b60: 68 65 73 65 20 73 69 67 6e 61 74 75 72 65 73 2e hese signatures.
0b70: 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 61 74 20 69 73 </p>..<p>That is
0b80: 20 77 68 61 74 20 68 61 70 70 65 6e 73 20 69 6e what happens in
0b90: 20 74 68 69 73 20 73 74 65 70 2e 20 54 68 65 20 this step. The
0ba0: 66 6f 6c 6c 6f 77 69 6e 67 20 70 72 6f 63 65 73 following proces
0bb0: 73 69 6e 67 20 73 74 65 70 0a 63 61 6e 20 74 68 sing step.can th
0bc0: 65 6e 20 74 68 65 20 63 6f 6d 70 75 74 65 20 73 en the compute s
0bd0: 69 67 6e 61 74 75 72 65 20 66 6f 72 20 69 74 73 ignature for its
0be0: 20 63 75 72 72 65 6e 74 20 6c 6f 63 61 74 69 6f current locatio
0bf0: 6e 20 61 6e 64 20 74 68 65 6e 20 68 61 73 0a 74 n and then has.t
0c00: 6f 20 73 65 61 72 63 68 20 6f 6e 6c 79 20 61 20 o search only a
0c10: 6e 61 72 72 6f 77 20 73 65 74 20 6f 66 20 6c 6f narrow set of lo
0c20: 63 61 74 69 6f 6e 73 20 69 6e 20 74 68 65 20 22 cations in the "
0c30: 6f 72 69 67 69 6e 61 6c 22 20 66 6f 72 0a 70 6f original" for.po
0c40: 73 73 69 62 6c 65 20 6d 61 74 63 68 65 73 2c 20 ssible matches,
0c50: 6e 61 6d 65 6c 79 20 74 68 6f 73 65 20 77 68 69 namely those whi
0c60: 63 68 20 68 61 76 65 20 74 68 65 20 73 61 6d 65 ch have the same
0c70: 20 73 69 67 6e 61 74 75 72 65 2e 3c 2f 70 3e 0a signature.</p>.
0c80: 0a 3c 70 3e 49 6e 20 64 65 74 61 69 6c 3a 3c 2f .<p>In detail:</
0c90: 70 3e 0a 0a 3c 6f 6c 3e 0a 3c 6c 69 3e 54 68 65 p>..<ol>.<li>The
0ca0: 20 22 6f 72 69 67 69 6e 61 6c 22 20 69 73 20 73 "original" is s
0cb0: 70 6c 69 74 20 69 6e 74 6f 20 63 68 75 6e 6b 73 plit into chunks
0cc0: 20 6f 66 20 4e 48 41 53 48 20 62 79 74 65 73 2e of NHASH bytes.
0cd0: 20 4e 6f 74 65 20 74 68 61 74 20 61 0a 70 61 72 Note that a.par
0ce0: 74 69 61 6c 20 63 68 75 6e 6b 20 6f 66 20 6c 65 tial chunk of le
0cf0: 73 73 20 74 68 61 6e 20 4e 48 41 53 48 20 62 79 ss than NHASH by
0d00: 74 65 73 20 61 74 20 74 68 65 20 65 6e 64 20 6f tes at the end o
0d10: 66 20 22 6f 72 69 67 69 6e 61 6c 22 20 69 73 0a f "original" is.
0d20: 69 67 6e 6f 72 65 64 2e 0a 3c 2f 6c 69 3e 0a 3c ignored..</li>.<
0d30: 6c 69 3e 54 68 65 20 3c 61 20 68 72 65 66 3d 22 li>The <a href="
0d40: 23 72 6f 6c 6c 68 61 73 68 22 3e 72 6f 6c 6c 69 #rollhash">rolli
0d50: 6e 67 20 68 61 73 68 3c 2f 61 3e 20 6f 66 20 65 ng hash</a> of e
0d60: 61 63 68 20 63 68 75 6e 6b 20 69 73 0a 63 6f 6d ach chunk is.com
0d70: 70 75 74 65 64 2e 0a 3c 2f 6c 69 3e 0a 3c 6c 69 puted..</li>.<li
0d80: 3e 41 20 68 61 73 68 20 74 61 62 6c 65 20 69 73 >A hash table is
0d90: 20 66 69 6c 6c 65 64 2c 20 6d 61 70 70 69 6e 67 filled, mapping
0da0: 20 66 72 6f 6d 20 74 68 65 20 68 61 73 68 65 73 from the hashes
0db0: 20 6f 66 20 74 68 65 20 63 68 75 6e 6b 73 20 74 of the chunks t
0dc0: 6f 0a 74 68 65 20 6c 69 73 74 20 6f 66 20 63 68 o.the list of ch
0dd0: 75 6e 6b 20 6c 6f 63 61 74 69 6f 6e 73 20 68 61 unk locations ha
0de0: 76 69 6e 67 20 74 68 69 73 20 68 61 73 68 2e 0a ving this hash..
0df0: 3c 2f 6c 69 3e 0a 3c 2f 6f 6c 3e 0a 0a 3c 61 20 </li>.</ol>..<a
0e00: 6e 61 6d 65 3d 22 70 72 6f 63 65 73 73 69 6e 67 name="processing
0e10: 22 3e 3c 2f 61 3e 3c 68 33 3e 32 2e 31 20 50 72 "></a><h3>2.1 Pr
0e20: 6f 63 65 73 73 69 6e 67 20 74 68 65 20 74 61 72 ocessing the tar
0e30: 67 65 74 3c 2f 68 33 3e 0a 0a 3c 70 3e 54 68 69 get</h3>..<p>Thi
0e40: 73 2c 20 74 68 65 20 6d 61 69 6e 20 70 68 61 73 s, the main phas
0e50: 65 20 6f 66 20 74 68 65 20 65 6e 63 6f 64 65 72 e of the encoder
0e60: 2c 20 70 72 6f 63 65 73 73 65 73 20 74 68 65 20 , processes the
0e70: 74 61 72 67 65 74 20 69 6e 20 61 20 6c 6f 6f 70 target in a loop
0e80: 0a 66 72 6f 6d 20 62 65 67 69 6e 6e 69 6e 67 20 .from beginning
0e90: 74 6f 20 65 6e 64 2e 20 54 68 65 20 73 74 61 74 to end. The stat
0ea0: 65 20 6f 66 20 74 68 65 20 65 6e 63 6f 64 65 72 e of the encoder
0eb0: 20 69 73 20 63 61 70 74 75 72 65 64 20 62 79 20 is captured by
0ec0: 74 77 6f 0a 6c 6f 63 61 74 69 6f 6e 73 2c 20 74 two.locations, t
0ed0: 68 65 20 22 62 61 73 65 22 20 61 6e 64 20 74 68 he "base" and th
0ee0: 65 20 22 73 6c 69 64 65 22 2e 20 22 62 61 73 65 e "slide". "base
0ef0: 22 20 70 6f 69 6e 74 73 20 74 6f 20 74 68 65 20 " points to the
0f00: 66 69 72 73 74 20 62 79 74 65 0a 6f 66 20 74 68 first byte.of th
0f10: 65 20 74 61 72 67 65 74 20 66 6f 72 20 77 68 69 e target for whi
0f20: 63 68 20 6e 6f 20 64 65 6c 74 61 20 6f 75 74 70 ch no delta outp
0f30: 75 74 20 68 61 73 20 62 65 65 6e 20 67 65 6e 65 ut has been gene
0f40: 72 61 74 65 64 20 79 65 74 2c 20 61 6e 64 0a 22 rated yet, and."
0f50: 73 6c 69 64 65 22 20 69 73 20 74 68 65 20 6c 6f slide" is the lo
0f60: 63 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 77 69 cation of the wi
0f70: 6e 64 6f 77 20 75 73 65 64 20 74 6f 20 6c 6f 6f ndow used to loo
0f80: 6b 20 69 6e 20 74 68 65 20 22 6f 72 69 67 69 6e k in the "origin
0f90: 22 20 66 6f 72 0a 63 6f 6d 6d 6f 6e 61 6c 69 74 " for.commonalit
0fa0: 69 65 73 2e 20 54 68 69 73 20 77 69 6e 64 6f 77 ies. This window
0fb0: 20 69 73 20 4e 48 41 53 48 20 62 79 74 65 73 20 is NHASH bytes
0fc0: 6c 6f 6e 67 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 6e long.</p>..<p>In
0fd0: 69 74 69 61 6c 6c 79 20 62 6f 74 68 20 22 62 61 itially both "ba
0fe0: 73 65 22 20 61 6e 64 20 22 73 6c 69 64 65 22 20 se" and "slide"
0ff0: 70 6f 69 6e 74 20 74 6f 20 74 68 65 20 62 65 67 point to the beg
1000: 69 6e 6e 69 6e 67 20 6f 66 20 74 68 65 0a 22 74 inning of the."t
1010: 61 72 67 65 74 22 2e 20 49 6e 20 65 61 63 68 20 arget". In each
1020: 69 74 65 72 61 74 69 6f 6e 20 6f 66 20 74 68 65 iteration of the
1030: 20 6c 6f 6f 70 20 74 68 65 20 65 6e 63 6f 64 65 loop the encode
1040: 72 20 64 65 63 69 64 65 73 20 77 68 65 74 68 65 r decides whethe
1050: 72 20 74 6f 0a 3c 75 6c 3e 0a 3c 6c 69 3e 65 6d r to.<ul>.<li>em
1060: 69 74 20 61 20 73 69 6e 67 6c 65 20 69 6e 73 74 it a single inst
1070: 72 75 63 74 69 6f 6e 0a 74 6f 20 3c 61 20 68 72 ruction.to <a hr
1080: 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 74 ef="delta_format
1090: 2e 77 69 6b 69 23 63 6f 70 79 72 61 6e 67 65 22 .wiki#copyrange"
10a0: 3e 63 6f 70 79 20 61 20 72 61 6e 67 65 3c 2f 61 >copy a range</a
10b0: 3e 2c 20 6f 72 0a 3c 2f 6c 69 3e 0a 3c 6c 69 3e >, or.</li>.<li>
10c0: 65 6d 69 74 20 74 77 6f 20 69 6e 73 74 72 75 63 emit two instruc
10d0: 74 69 6f 6e 73 2c 20 66 69 72 73 74 0a 74 6f 20 tions, first.to
10e0: 3c 61 20 68 72 65 66 3d 22 64 65 6c 74 61 5f 66 <a href="delta_f
10f0: 6f 72 6d 61 74 2e 77 69 6b 69 23 69 6e 73 65 72 ormat.wiki#inser
1100: 74 6c 69 74 22 3e 69 6e 73 65 72 74 20 61 20 6c tlit">insert a l
1110: 69 74 65 72 61 6c 3c 2f 61 3e 2c 20 74 68 65 6e iteral</a>, then
1120: 0a 74 6f 20 3c 61 20 68 72 65 66 3d 22 64 65 6c .to <a href="del
1130: 74 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 23 63 ta_format.wiki#c
1140: 6f 70 79 72 61 6e 67 65 22 3e 63 6f 70 79 20 61 opyrange">copy a
1150: 20 72 61 6e 67 65 3c 2f 61 3e 2c 20 6f 72 0a 3c range</a>, or.<
1160: 2f 6c 69 3e 0a 3c 6c 69 3e 6d 6f 76 65 20 74 68 /li>.<li>move th
1170: 65 20 77 69 6e 64 6f 77 20 66 6f 72 77 61 72 64 e window forward
1180: 20 6f 6e 65 20 62 79 74 65 2e 0a 3c 2f 6c 69 3e one byte..</li>
1190: 0a 3c 2f 75 6c 3e 0a 3c 2f 70 3e 0a 0a 3c 69 6d .</ul>.</p>..<im
11a0: 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 31 30 2e g src="encode10.
11b0: 67 69 66 22 20 61 6c 69 67 6e 3d 22 72 69 67 68 gif" align="righ
11c0: 74 22 20 68 73 70 61 63 65 3d 22 31 30 22 3e 0a t" hspace="10">.
11d0: 3c 70 3e 54 6f 20 6d 61 6b 65 20 74 68 69 73 20 <p>To make this
11e0: 64 65 63 69 73 69 6f 6e 20 74 68 65 20 65 6e 63 decision the enc
11f0: 6f 64 65 72 20 66 69 72 73 74 20 63 6f 6d 70 75 oder first compu
1200: 74 65 73 20 74 68 65 20 68 61 73 68 20 76 61 6c tes the hash val
1210: 75 65 20 66 6f 72 0a 74 68 65 20 4e 48 41 53 48 ue for.the NHASH
1220: 20 62 79 74 65 73 20 69 6e 20 74 68 65 20 77 69 bytes in the wi
1230: 6e 64 6f 77 20 61 6e 64 20 74 68 65 6e 20 6c 6f ndow and then lo
1240: 6f 6b 73 20 61 74 20 61 6c 6c 20 74 68 65 20 6c oks at all the l
1250: 6f 63 61 74 69 6f 6e 73 20 69 6e 0a 74 68 65 20 ocations in.the
1260: 22 6f 72 69 67 69 6e 22 20 77 68 69 63 68 20 68 "origin" which h
1270: 61 76 65 20 74 68 65 20 73 61 6d 65 20 73 69 67 ave the same sig
1280: 6e 61 74 75 72 65 2e 20 54 68 69 73 20 70 61 72 nature. This par
1290: 74 20 75 73 65 73 20 74 68 65 20 68 61 73 68 0a t uses the hash.
12a0: 74 61 62 6c 65 20 63 72 65 61 74 65 64 20 62 79 table created by
12b0: 20 74 68 65 20 70 72 65 2d 70 72 6f 63 65 73 73 the pre-process
12c0: 69 6e 67 20 73 74 65 70 20 74 6f 20 65 66 66 69 ing step to effi
12d0: 63 69 65 6e 74 6c 79 20 66 69 6e 64 20 74 68 65 ciently find the
12e0: 73 65 0a 6c 6f 63 61 74 69 6f 6e 73 2e 3c 2f 70 se.locations.</p
12f0: 3e 0a 0a 3c 70 3e 46 6f 72 20 65 61 63 68 20 6f >..<p>For each o
1300: 66 20 74 68 65 20 70 6f 73 73 69 62 6c 65 20 63 f the possible c
1310: 61 6e 64 69 64 61 74 65 73 20 74 68 65 20 65 6e andidates the en
1320: 63 6f 64 65 72 20 66 69 6e 64 73 20 74 68 65 20 coder finds the
1330: 6d 61 78 69 6d 61 6c 0a 72 61 6e 67 65 20 6f 66 maximal.range of
1340: 20 62 79 74 65 73 20 63 6f 6d 6d 6f 6e 20 74 6f bytes common to
1350: 20 62 6f 74 68 20 22 6f 72 69 67 69 6e 22 20 61 both "origin" a
1360: 6e 64 20 22 74 61 72 67 65 74 22 2c 20 67 6f 69 nd "target", goi
1370: 6e 67 20 66 6f 72 77 61 72 64 20 61 6e 64 0a 62 ng forward and.b
1380: 61 63 6b 77 61 72 64 20 66 72 6f 6d 20 22 73 6c ackward from "sl
1390: 69 64 65 22 20 69 6e 20 74 68 65 20 22 74 61 72 ide" in the "tar
13a0: 67 65 74 22 2c 20 61 6e 64 20 74 68 65 20 63 61 get", and the ca
13b0: 6e 64 69 64 61 74 65 20 6c 6f 63 61 74 69 6f 6e ndidate location
13c0: 20 69 6e 0a 74 68 65 20 22 6f 72 69 67 69 6e 22 in.the "origin"
13d0: 2e 20 54 68 69 73 20 73 65 61 72 63 68 20 69 73 . This search is
13e0: 20 63 6f 6e 73 74 72 61 69 6e 65 64 20 6f 6e 20 constrained on
13f0: 74 68 65 20 73 69 64 65 20 6f 66 20 74 68 65 20 the side of the
1400: 22 74 61 72 67 65 74 22 0a 62 79 20 74 68 65 20 "target".by the
1410: 22 62 61 73 65 22 20 28 62 61 63 6b 77 61 72 64 "base" (backward
1420: 20 73 65 61 72 63 68 29 2c 20 61 6e 64 20 74 68 search), and th
1430: 65 20 65 6e 64 20 6f 66 20 74 68 65 20 22 74 61 e end of the "ta
1440: 72 67 65 74 22 20 28 66 6f 72 77 61 72 64 0a 73 rget" (forward.s
1450: 65 61 72 63 68 29 2c 20 61 6e 64 20 6f 6e 20 74 earch), and on t
1460: 68 65 20 73 69 64 65 20 6f 66 20 74 68 65 20 22 he side of the "
1470: 6f 72 69 67 69 6e 22 20 62 79 20 74 68 65 20 62 origin" by the b
1480: 65 67 69 6e 6e 69 6e 67 20 61 6e 64 20 65 6e 64 eginning and end
1490: 20 6f 66 0a 74 68 65 20 22 6f 72 69 67 69 6e 22 of.the "origin"
14a0: 2c 20 72 65 73 70 65 63 74 69 76 65 6c 79 2e 3c , respectively.<
14b0: 2f 70 3e 0a 0a 3c 70 3e 54 68 65 72 65 20 61 72 /p>..<p>There ar
14c0: 65 20 69 6e 70 75 74 20 66 69 6c 65 73 20 66 6f e input files fo
14d0: 72 20 77 68 69 63 68 20 74 68 65 20 68 61 73 68 r which the hash
14e0: 20 63 68 61 69 6e 73 20 67 65 6e 65 72 61 74 65 chains generate
14f0: 64 20 62 79 20 74 68 65 0a 70 72 65 2d 70 72 6f d by the.pre-pro
1500: 63 65 73 73 69 6e 67 20 73 74 65 70 20 63 61 6e cessing step can
1510: 20 62 65 63 6f 6d 65 20 76 65 72 79 20 6c 6f 6e become very lon
1520: 67 2c 20 6c 65 61 64 69 6e 67 20 74 6f 20 6c 6f g, leading to lo
1530: 6e 67 20 73 65 61 72 63 68 20 74 69 6d 65 73 0a ng search times.
1540: 61 6e 64 20 61 66 66 65 63 74 69 6e 67 20 74 68 and affecting th
1550: 65 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 6f 66 e performance of
1560: 20 74 68 65 20 64 65 6c 74 61 20 67 65 6e 65 72 the delta gener
1570: 61 74 6f 72 2e 20 54 6f 20 6c 69 6d 69 74 20 74 ator. To limit t
1580: 68 65 0a 65 66 66 65 63 74 20 73 75 63 68 20 6c he.effect such l
1590: 6f 6e 67 20 63 68 61 69 6e 73 20 63 61 6e 20 68 ong chains can h
15a0: 61 76 65 20 74 68 65 20 61 63 74 75 61 6c 20 73 ave the actual s
15b0: 65 61 72 63 68 20 66 6f 72 20 63 61 6e 64 69 64 earch for candid
15c0: 61 74 65 73 20 69 73 0a 62 6f 75 6e 64 65 64 2c ates is.bounded,
15d0: 20 6c 6f 6f 6b 69 6e 67 20 61 74 20 6d 6f 73 74 looking at most
15e0: 20 4e 20 63 61 6e 64 69 64 61 74 65 73 2e 20 43 N candidates. C
15f0: 75 72 72 65 6e 74 6c 79 20 4e 20 69 73 20 73 65 urrently N is se
1600: 74 20 74 6f 20 32 35 30 2e 3c 2f 70 3e 0a 0a 3c t to 250.</p>..<
1610: 70 3e 46 72 6f 6d 20 74 68 65 20 72 61 6e 67 65 p>From the range
1620: 73 20 66 6f 72 20 61 6c 6c 20 74 68 65 20 63 61 s for all the ca
1630: 6e 64 69 64 61 74 65 73 20 74 68 65 20 62 65 73 ndidates the bes
1640: 74 20 28 3d 20 6c 61 72 67 65 73 74 29 20 63 6f t (= largest) co
1650: 6d 6d 6f 6e 0a 72 61 6e 67 65 20 69 73 20 74 61 mmon.range is ta
1660: 6b 65 6e 20 61 6e 64 20 69 74 20 69 73 20 64 65 ken and it is de
1670: 74 65 72 6d 69 6e 65 64 20 68 6f 77 20 6d 61 6e termined how man
1680: 79 20 62 79 74 65 73 20 61 72 65 20 6e 65 65 64 y bytes are need
1690: 65 64 20 74 6f 0a 65 6e 63 6f 64 65 20 74 68 65 ed to.encode the
16a0: 20 62 79 74 65 73 20 62 65 74 77 65 65 6e 20 74 bytes between t
16b0: 68 65 20 22 62 61 73 65 22 20 61 6e 64 20 74 68 he "base" and th
16c0: 65 20 65 6e 64 20 6f 66 20 74 68 61 74 20 72 61 e end of that ra
16d0: 6e 67 65 2e 20 49 66 20 74 68 65 0a 72 61 6e 67 nge. If the.rang
16e0: 65 20 65 78 74 65 6e 64 65 64 20 62 61 63 6b 20 e extended back
16f0: 74 6f 20 74 68 65 20 22 62 61 73 65 22 20 74 68 to the "base" th
1700: 65 6e 20 74 68 69 73 20 63 61 6e 20 62 65 20 64 en this can be d
1710: 6f 6e 65 20 69 6e 20 61 20 73 69 6e 67 6c 65 0a one in a single.
1720: 63 6f 70 79 20 69 6e 73 74 72 75 63 74 69 6f 6e copy instruction
1730: 2e 20 4f 74 68 65 72 77 69 73 65 2c 20 69 2e 65 . Otherwise, i.e
1740: 20 69 66 20 74 68 65 72 65 20 69 73 20 61 20 67 if there is a g
1750: 61 70 20 62 65 74 77 65 65 6e 20 74 68 65 20 22 ap between the "
1760: 62 61 73 65 22 0a 61 6e 64 20 74 68 65 20 62 65 base".and the be
1770: 67 69 6e 6e 69 6e 67 20 6f 66 20 74 68 65 20 72 ginning of the r
1780: 61 6e 67 65 20 74 68 65 6e 20 74 77 6f 20 69 6e ange then two in
1790: 73 74 72 75 63 74 69 6f 6e 73 20 61 72 65 20 6e structions are n
17a0: 65 65 64 65 64 2c 20 6f 6e 65 0a 74 6f 20 69 6e eeded, one.to in
17b0: 73 65 72 74 20 74 68 65 20 62 79 74 65 73 20 69 sert the bytes i
17c0: 6e 20 74 68 65 20 67 61 70 20 61 73 20 61 20 6c n the gap as a l
17d0: 69 74 65 72 61 6c 2c 20 61 6e 64 20 61 20 63 6f iteral, and a co
17e0: 70 79 20 69 6e 73 74 72 75 63 74 69 6f 6e 0a 66 py instruction.f
17f0: 6f 72 20 74 68 65 20 72 61 6e 67 65 20 69 74 73 or the range its
1800: 65 6c 66 2e 20 54 68 65 20 67 65 6e 65 72 61 6c elf. The general
1810: 20 73 69 74 75 61 74 69 6f 6e 20 61 74 20 74 68 situation at th
1820: 69 73 20 70 6f 69 6e 74 20 63 61 6e 20 62 65 20 is point can be
1830: 73 65 65 6e 0a 69 6e 20 74 68 65 20 70 69 63 74 seen.in the pict
1840: 75 72 65 20 74 6f 20 74 68 65 20 72 69 67 68 74 ure to the right
1850: 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 66 20 74 68 65 .</p>..<p>If the
1860: 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 number of bytes
1870: 20 6e 65 65 64 65 64 20 74 6f 20 65 6e 63 6f 64 needed to encod
1880: 65 20 62 6f 74 68 20 67 61 70 20 28 69 66 20 70 e both gap (if p
1890: 72 65 73 65 6e 74 29 2c 20 61 6e 64 0a 72 61 6e resent), and.ran
18a0: 67 65 20 69 73 20 6c 65 73 73 20 74 68 61 6e 20 ge is less than
18b0: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 the number of by
18c0: 74 65 73 20 77 65 20 61 72 65 20 65 6e 63 6f 64 tes we are encod
18d0: 69 6e 67 20 74 68 65 20 65 6e 63 6f 64 65 72 0a ing the encoder.
18e0: 77 69 6c 6c 20 65 6d 69 74 20 74 68 65 20 6e 65 will emit the ne
18f0: 63 65 73 73 61 72 79 20 69 6e 73 74 72 75 63 74 cessary instruct
1900: 69 6f 6e 73 20 61 73 20 64 65 73 63 72 69 62 65 ions as describe
1910: 64 20 61 62 6f 76 65 2c 20 73 65 74 20 22 62 61 d above, set "ba
1920: 73 65 22 0a 61 6e 64 20 22 73 6c 69 64 65 22 20 se".and "slide"
1930: 74 6f 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 to the end of th
1940: 65 20 65 6e 63 6f 64 65 64 20 72 61 6e 67 65 20 e encoded range
1950: 61 6e 64 20 73 74 61 72 74 20 74 68 65 20 6e 65 and start the ne
1960: 78 74 0a 69 74 65 72 61 74 69 6f 6e 20 61 74 20 xt.iteration at
1970: 74 68 61 74 20 70 6f 69 6e 74 2e 3c 2f 70 3e 0a that point.</p>.
1980: 0a 3c 70 3e 49 66 2c 20 6f 6e 20 74 68 65 20 6f .<p>If, on the o
1990: 74 68 65 72 20 68 61 6e 64 2c 20 74 68 65 20 65 ther hand, the e
19a0: 6e 63 6f 64 65 72 20 65 69 74 68 65 72 20 64 69 ncoder either di
19b0: 64 20 6e 6f 74 20 66 69 6e 64 20 63 61 6e 64 69 d not find candi
19c0: 64 61 74 65 0a 6c 6f 63 61 74 69 6f 6e 73 20 69 date.locations i
19d0: 6e 20 74 68 65 20 6f 72 69 67 69 6e 2c 20 6f 72 n the origin, or
19e0: 20 74 68 65 20 62 65 73 74 20 72 61 6e 67 65 20 the best range
19f0: 63 6f 6d 69 6e 67 20 6f 75 74 20 6f 66 20 74 68 coming out of th
1a00: 65 20 73 65 61 72 63 68 0a 6e 65 65 64 65 64 20 e search.needed
1a10: 6d 6f 72 65 20 62 79 74 65 73 20 74 6f 20 65 6e more bytes to en
1a20: 63 6f 64 65 20 74 68 65 20 72 61 6e 67 65 20 74 code the range t
1a30: 68 61 6e 20 74 68 65 72 65 20 77 65 72 65 20 62 han there were b
1a40: 79 74 65 73 20 69 6e 20 74 68 65 0a 72 61 6e 67 ytes in the.rang
1a50: 65 2c 20 74 68 65 6e 20 6e 6f 20 69 6e 73 74 72 e, then no instr
1a60: 75 63 74 69 6f 6e 73 20 61 72 65 20 65 6d 69 74 uctions are emit
1a70: 74 65 64 20 61 6e 64 20 74 68 65 20 77 69 6e 64 ted and the wind
1a80: 6f 77 20 69 73 20 6d 6f 76 65 64 20 6f 6e 65 0a ow is moved one.
1a90: 62 79 74 65 20 66 6f 72 77 61 72 64 2e 20 54 68 byte forward. Th
1aa0: 65 20 22 62 61 73 65 22 20 69 73 20 6c 65 66 74 e "base" is left
1ab0: 20 75 6e 63 68 61 6e 67 65 64 20 69 6e 20 74 68 unchanged in th
1ac0: 61 74 20 63 61 73 65 2e 3c 2f 70 3e 0a 0a 3c 70 at case.</p>..<p
1ad0: 3e 54 68 65 20 70 72 6f 63 65 73 73 69 6e 67 20 >The processing
1ae0: 6c 6f 6f 70 20 73 74 6f 70 73 20 61 74 20 6f 6e loop stops at on
1af0: 65 20 6f 66 20 74 77 6f 20 63 6f 6e 64 69 74 69 e of two conditi
1b00: 6f 6e 73 3a 0a 3c 6f 6c 3e 0a 3c 6c 69 3e 54 68 ons:.<ol>.<li>Th
1b10: 65 20 65 6e 63 6f 64 65 72 20 64 65 63 69 64 65 e encoder decide
1b20: 64 20 74 6f 20 6d 6f 76 65 20 74 68 65 20 77 69 d to move the wi
1b30: 6e 64 6f 77 20 66 6f 72 77 61 72 64 2c 20 62 75 ndow forward, bu
1b40: 74 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 t the end of the
1b50: 0a 77 69 6e 64 6f 77 20 72 65 61 63 68 65 64 20 .window reached
1b60: 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 20 22 the end of the "
1b70: 74 61 72 67 65 74 22 2e 20 0a 3c 2f 6c 69 3e 0a target". .</li>.
1b80: 3c 6c 69 3e 41 66 74 65 72 20 74 68 65 20 65 6d <li>After the em
1b90: 69 73 73 69 6f 6e 20 6f 66 20 69 6e 73 74 72 75 ission of instru
1ba0: 63 74 69 6f 6e 73 20 74 68 65 20 6e 65 77 20 22 ctions the new "
1bb0: 62 61 73 65 22 20 6c 6f 63 61 74 69 6f 6e 20 69 base" location i
1bc0: 73 0a 77 69 74 68 69 6e 20 4e 48 41 53 48 20 62 s.within NHASH b
1bd0: 79 74 65 73 20 6f 66 20 65 6e 64 20 6f 66 20 74 ytes of end of t
1be0: 68 65 20 22 74 61 72 67 65 74 22 2c 20 69 2e 65 he "target", i.e
1bf0: 2e 20 74 68 65 72 65 20 61 72 65 20 6e 6f 20 6d . there are no m
1c00: 6f 72 65 20 74 68 61 6e 0a 61 74 20 6d 6f 73 74 ore than.at most
1c10: 20 4e 48 41 53 48 20 62 79 74 65 73 20 6c 65 66 NHASH bytes lef
1c20: 74 2e 0a 3c 2f 6c 69 3e 0a 3c 2f 6f 6c 3e 0a 3c t..</li>.</ol>.<
1c30: 2f 70 3e 0a 0a 3c 70 3e 49 66 20 74 68 65 20 70 /p>..<p>If the p
1c40: 72 6f 63 65 73 73 69 6e 67 20 6c 6f 6f 70 20 6c rocessing loop l
1c50: 65 66 74 20 62 79 74 65 73 20 75 6e 65 6e 63 6f eft bytes unenco
1c60: 64 65 64 2c 20 69 2e 65 2e 20 22 62 61 73 65 22 ded, i.e. "base"
1c70: 20 6e 6f 74 0a 65 78 61 63 74 6c 79 20 61 74 20 not.exactly at
1c80: 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 20 22 the end of the "
1c90: 74 61 72 67 65 74 22 2c 20 61 73 20 69 73 20 70 target", as is p
1ca0: 6f 73 73 69 62 6c 65 20 66 6f 72 20 62 6f 74 68 ossible for both
1cb0: 20 65 6e 64 0a 63 6f 6e 64 69 74 69 6f 6e 73 2c end.conditions,
1cc0: 20 74 68 65 6e 20 6f 6e 65 20 6c 61 73 74 20 69 then one last i
1cd0: 6e 73 65 72 74 20 69 6e 73 74 72 75 63 74 69 6f nsert instructio
1ce0: 6e 20 69 73 20 65 6d 69 74 74 65 64 20 74 6f 20 n is emitted to
1cf0: 70 75 74 20 74 68 65 73 65 0a 62 79 74 65 73 20 put these.bytes
1d00: 69 6e 74 6f 20 74 68 65 20 64 65 6c 74 61 2e 3c into the delta.<
1d10: 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 65 78 63 p>..<a name="exc
1d20: 65 70 74 69 6f 6e 73 22 3e 3c 2f 61 3e 3c 68 32 eptions"></a><h2
1d30: 3e 33 2e 30 20 45 78 63 65 70 74 69 6f 6e 73 3c >3.0 Exceptions<
1d40: 2f 68 32 3e 0a 0a 3c 70 3e 49 66 20 74 68 65 20 /h2>..<p>If the
1d50: 22 6f 72 69 67 69 6e 61 6c 22 20 69 73 20 61 74 "original" is at
1d60: 20 6d 6f 73 74 20 4e 48 41 53 48 20 62 79 74 65 most NHASH byte
1d70: 73 20 6c 6f 6e 67 20 6e 6f 20 63 6f 6d 70 72 65 s long no compre
1d80: 73 73 69 6f 6e 20 6f 66 0a 63 68 61 6e 67 65 73 ssion of.changes
1d90: 20 69 73 20 70 6f 73 73 69 62 6c 65 2c 20 61 6e is possible, an
1da0: 64 20 74 68 65 20 73 65 67 6d 65 6e 74 2d 6c 69 d the segment-li
1db0: 73 74 20 6f 66 20 74 68 65 20 64 65 6c 74 61 20 st of the delta
1dc0: 63 6f 6e 73 69 73 74 73 20 6f 66 20 61 0a 73 69 consists of a.si
1dd0: 6e 67 6c 65 20 6c 69 74 65 72 61 6c 20 77 68 69 ngle literal whi
1de0: 63 68 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 ch contains the
1df0: 65 6e 74 69 72 65 20 22 74 61 72 67 65 74 22 2e entire "target".
1e00: 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 69 73 20 69 73 </p>..<p>This is
1e10: 20 61 63 74 75 61 6c 6c 79 20 65 71 75 69 76 61 actually equiva
1e20: 6c 65 6e 74 20 74 6f 20 74 68 65 20 73 65 63 6f lent to the seco
1e30: 6e 64 20 65 6e 64 20 63 6f 6e 64 69 74 69 6f 6e nd end condition
1e40: 20 6f 66 20 74 68 65 0a 70 72 6f 63 65 73 73 69 of the.processi
1e50: 6e 67 20 6c 6f 6f 70 20 64 65 73 63 72 69 62 65 ng loop describe
1e60: 64 20 69 6e 20 74 68 65 20 70 72 65 76 69 6f 75 d in the previou
1e70: 73 20 73 65 63 74 69 6f 6e 2c 20 6a 75 73 74 20 s section, just
1e80: 63 68 65 63 6b 65 64 20 62 65 66 6f 72 65 0a 61 checked before.a
1e90: 63 74 75 61 6c 6c 79 20 65 6e 74 65 72 69 6e 67 ctually entering
1ea0: 20 74 68 65 20 6c 6f 6f 70 2e 3c 2f 70 3e 0a 0a the loop.</p>..
1eb0: 3c 61 20 6e 61 6d 65 3d 22 72 6f 6c 6c 68 61 73 <a name="rollhas
1ec0: 68 22 3e 3c 2f 61 3e 3c 68 32 3e 34 2e 30 20 54 h"></a><h2>4.0 T
1ed0: 68 65 20 72 6f 6c 6c 69 6e 67 20 68 61 73 68 3c he rolling hash<
1ee0: 2f 68 32 3e 0a 0a 3c 70 3e 54 68 65 20 72 6f 6c /h2>..<p>The rol
1ef0: 6c 69 6e 67 20 68 61 73 68 20 64 65 73 63 72 69 ling hash descri
1f00: 62 65 64 20 62 65 6c 6f 77 20 61 6e 64 20 75 73 bed below and us
1f10: 65 64 20 74 6f 20 63 6f 6d 70 75 74 65 20 63 6f ed to compute co
1f20: 6e 74 65 6e 74 0a 73 69 67 6e 61 74 75 72 65 73 ntent.signatures
1f30: 20 77 61 73 20 63 68 6f 73 65 6e 20 6e 6f 74 20 was chosen not
1f40: 6f 6e 6c 79 20 66 6f 72 20 67 6f 6f 64 20 68 61 only for good ha
1f50: 73 68 69 6e 67 20 70 72 6f 70 65 72 74 69 65 73 shing properties
1f60: 2c 20 62 75 74 20 61 6c 73 6f 0a 74 6f 20 65 6e , but also.to en
1f70: 61 62 6c 65 20 74 68 65 20 65 61 73 79 20 28 69 able the easy (i
1f80: 6e 63 72 65 6d 65 6e 74 61 6c 29 20 72 65 63 61 ncremental) reca
1f90: 6c 63 75 6c 61 74 69 6f 6e 20 6f 66 20 69 74 73 lculation of its
1fa0: 20 76 61 6c 75 65 20 66 6f 72 20 61 0a 73 6c 69 value for a.sli
1fb0: 64 69 6e 67 20 77 69 6e 64 6f 77 2c 20 69 2e 65 ding window, i.e
1fc0: 2e 20 77 68 65 72 65 20 74 68 65 20 6f 6c 64 65 . where the olde
1fd0: 73 74 20 62 79 74 65 20 69 73 20 72 65 6d 6f 76 st byte is remov
1fe0: 65 64 20 66 72 6f 6d 20 74 68 65 20 77 69 6e 64 ed from the wind
1ff0: 6f 77 0a 61 6e 64 20 61 20 6e 65 77 20 62 79 74 ow.and a new byt
2000: 65 20 69 73 20 73 68 69 66 74 65 64 20 69 6e 2e e is shifted in.
2010: 3c 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 72 68 <p>..<a name="rh
2020: 64 65 66 22 3e 3c 2f 61 3e 3c 68 33 3e 34 2e 31 def"></a><h3>4.1
2030: 20 44 65 66 69 6e 69 74 69 6f 6e 3c 2f 68 33 3e Definition</h3>
2040: 0a 0a 3c 70 3e 41 73 73 75 6d 69 6e 67 20 61 6e ..<p>Assuming an
2050: 20 61 72 72 61 79 20 5a 20 6f 66 20 4e 48 41 53 array Z of NHAS
2060: 48 20 62 79 74 65 73 20 28 69 6e 64 65 78 69 6e H bytes (indexin
2070: 67 20 73 74 61 72 74 69 6e 67 20 61 74 20 30 29 g starting at 0)
2080: 20 74 68 65 0a 68 61 73 68 20 56 20 69 73 20 63 the.hash V is c
2090: 6f 6d 70 75 74 65 64 20 76 69 61 3c 2f 70 3e 0a omputed via</p>.
20a0: 0a 3c 70 20 61 6c 69 67 6e 3d 63 65 6e 74 65 72 .<p align=center
20b0: 3e 3c 74 61 62 6c 65 3e 3c 74 72 3e 3c 74 64 3e ><table><tr><td>
20c0: 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 65 6e .<p><img src="en
20d0: 63 6f 64 65 31 2e 67 69 66 22 20 61 6c 69 67 6e code1.gif" align
20e0: 3d 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c ="center"></p>.<
20f0: 70 3e 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f p><img src="enco
2100: 64 65 32 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 de2.gif" align="
2110: 63 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c 70 3e center"></p>.<p>
2120: 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 <img src="encode
2130: 33 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 3.gif" align="ce
2140: 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c 2f 74 64 3e nter"></p>.</td>
2150: 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e 3c 2f 70 </tr></table></p
2160: 3e 0a 0a 77 68 65 72 65 20 41 20 61 6e 64 20 42 >..where A and B
2170: 20 61 72 65 20 75 6e 73 69 67 6e 65 64 20 31 36 are unsigned 16
2180: 2d 62 69 74 20 69 6e 74 65 67 65 72 73 20 28 68 -bit integers (h
2190: 65 6e 63 65 20 74 68 65 20 3c 75 3e 6d 6f 64 3c ence the <u>mod<
21a0: 2f 75 3e 29 2c 20 61 6e 64 0a 56 20 69 73 20 61 /u>), and.V is a
21b0: 20 33 32 2d 62 69 74 20 75 6e 73 69 67 6e 65 64 32-bit unsigned
21c0: 20 69 6e 74 65 67 65 72 20 77 69 74 68 20 42 20 integer with B
21d0: 61 73 20 4d 53 42 2c 20 41 20 61 73 20 4c 53 42 as MSB, A as LSB
21e0: 2e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 72 68 69 6e ...<a name="rhin
21f0: 63 72 22 3e 3c 2f 61 3e 3c 68 33 3e 34 2e 32 20 cr"></a><h3>4.2
2200: 49 6e 63 72 65 6d 65 6e 74 61 6c 20 72 65 63 61 Incremental reca
2210: 6c 63 75 6c 61 74 69 6f 6e 3c 2f 68 33 3e 0a 0a lculation</h3>..
2220: 3c 70 3e 41 73 73 75 6d 69 6e 67 20 61 6e 20 61 <p>Assuming an a
2230: 72 72 61 79 20 5a 20 6f 66 20 4e 48 41 53 48 20 rray Z of NHASH
2240: 62 79 74 65 73 20 28 69 6e 64 65 78 69 6e 67 20 bytes (indexing
2250: 73 74 61 72 74 69 6e 67 20 61 74 20 30 29 20 77 starting at 0) w
2260: 69 74 68 0a 68 61 73 68 20 56 20 28 61 6e 64 20 ith.hash V (and
2270: 63 6f 6d 70 6f 6e 65 6e 74 73 20 41 20 61 6e 64 components A and
2280: 20 42 29 2c 20 74 68 65 20 64 72 6f 70 70 65 64 B), the dropped
2290: 0a 62 79 74 65 20 3c 69 6d 67 20 73 72 63 3d 22 .byte <img src="
22a0: 65 6e 63 6f 64 65 34 2e 67 69 66 22 20 61 6c 69 encode4.gif" ali
22b0: 67 6e 3d 22 63 65 6e 74 65 72 22 3e 2c 20 61 6e gn="center">, an
22c0: 64 20 74 68 65 20 6e 65 77 20 62 79 74 65 0a 3c d the new byte.<
22d0: 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 35 img src="encode5
22e0: 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e .gif" align="cen
22f0: 74 65 72 22 3e 20 2c 20 74 68 65 20 6e 65 77 20 ter"> , the new
2300: 68 61 73 68 20 63 61 6e 0a 62 65 20 63 6f 6d 70 hash can.be comp
2310: 75 74 65 64 20 69 6e 63 72 65 6d 65 6e 74 61 6c uted incremental
2320: 6c 79 20 76 69 61 3a 20 3c 2f 70 3e 0a 0a 3c 70 ly via: </p>..<p
2330: 20 61 6c 69 67 6e 3d 63 65 6e 74 65 72 3e 3c 74 align=center><t
2340: 61 62 6c 65 3e 3c 74 72 3e 3c 74 64 3e 0a 3c 70 able><tr><td>.<p
2350: 3e 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 ><img src="encod
2360: 65 36 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 e6.gif" align="c
2370: 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c 70 3e 3c enter"></p>.<p><
2380: 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 37 img src="encode7
2390: 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e .gif" align="cen
23a0: 74 65 72 22 3e 3c 2f 70 3e 0a 3c 70 3e 3c 69 6d ter"></p>.<p><im
23b0: 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 38 2e 67 g src="encode8.g
23c0: 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 if" align="cente
23d0: 72 22 3e 3c 2f 70 3e 0a 3c 2f 74 64 3e 3c 2f 74 r"></p>.</td></t
23e0: 72 3e 3c 2f 74 61 62 6c 65 3e 3c 2f 70 3e 0a 0a r></table></p>..
23f0: 3c 70 3e 46 6f 72 20 41 2c 20 74 68 65 20 72 65 <p>For A, the re
2400: 67 75 6c 61 72 20 73 75 6d 2c 20 69 74 20 63 61 gular sum, it ca
2410: 6e 20 62 65 20 73 65 65 6e 20 65 61 73 69 6c 79 n be seen easily
2420: 20 74 68 61 74 20 74 68 69 73 20 74 68 65 20 63 that this the c
2430: 6f 72 72 65 63 74 0a 77 61 79 20 72 65 63 6f 6d orrect.way recom
2440: 70 75 74 69 6e 67 20 74 68 61 74 20 63 6f 6d 70 puting that comp
2450: 6f 6e 65 6e 74 2e 3c 2f 70 3e 0a 0a 3c 70 3e 46 onent.</p>..<p>F
2460: 6f 72 20 42 2c 20 74 68 65 20 77 65 69 67 68 74 or B, the weight
2470: 65 64 20 73 75 6d 2c 20 6e 6f 74 65 20 66 69 72 ed sum, note fir
2480: 73 74 20 74 68 61 74 20 3c 69 6d 67 20 73 72 63 st that <img src
2490: 3d 22 65 6e 63 6f 64 65 34 2e 67 69 66 22 0a 61 ="encode4.gif".a
24a0: 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 20 68 lign="center"> h
24b0: 61 73 20 74 68 65 20 77 65 69 67 68 74 20 4e 48 as the weight NH
24c0: 41 53 48 20 69 6e 20 74 68 65 20 73 75 6d 2c 20 ASH in the sum,
24d0: 73 6f 20 74 68 61 74 20 69 73 20 77 68 61 74 20 so that is what
24e0: 68 61 73 0a 74 6f 20 62 65 20 72 65 6d 6f 76 65 has.to be remove
24f0: 64 2e 20 54 68 65 6e 20 61 64 64 69 6e 67 20 69 d. Then adding i
2500: 6e 20 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f n <img src="enco
2510: 64 65 39 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 de9.gif" align="
2520: 63 65 6e 74 65 72 22 3e 0a 61 64 64 73 20 6f 6e center">.adds on
2530: 65 20 77 65 69 67 68 74 20 66 61 63 74 6f 72 20 e weight factor
2540: 74 6f 20 61 6c 6c 20 74 68 65 20 6f 74 68 65 72 to all the other
2550: 20 76 61 6c 75 65 73 20 6f 66 20 5a 2c 20 61 6e values of Z, an
2560: 64 20 61 74 20 6c 61 73 74 20 61 64 64 73 0a 69 d at last adds.i
2570: 6e 20 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f n <img src="enco
2580: 64 65 35 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 de5.gif" align="
2590: 63 65 6e 74 65 72 22 3e 20 77 69 74 68 20 77 65 center"> with we
25a0: 69 67 68 74 20 31 2c 20 61 6c 73 6f 0a 67 65 6e ight 1, also.gen
25b0: 65 72 61 74 69 6e 67 20 74 68 65 20 63 6f 72 72 erating the corr
25c0: 65 63 74 20 6e 65 77 20 73 75 6d 3c 2f 70 3e 0a ect new sum</p>.