0000: 3c 68 31 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 <h1 align="cente
0010: 72 22 3e 0a 46 6f 73 73 69 6c 20 44 65 6c 74 61 r">.Fossil Delta
0020: 20 45 6e 63 6f 64 69 6e 67 20 41 6c 67 6f 72 69 Encoding Algori
0030: 74 68 6d 0a 3c 2f 68 31 3e 0a 0a 3c 70 3e 41 20 thm.</h1>..<p>A
0040: 6b 65 79 20 63 6f 6d 70 6f 6e 65 6e 74 20 66 6f key component fo
0050: 72 20 74 68 65 20 65 66 66 69 63 69 65 6e 74 20 r the efficient
0060: 73 74 6f 72 61 67 65 20 6f 66 20 6d 75 6c 74 69 storage of multi
0070: 70 6c 65 20 72 65 76 69 73 69 6f 6e 73 20 6f 66 ple revisions of
0080: 0a 61 20 66 69 6c 65 20 69 6e 20 66 6f 73 73 69 .a file in fossi
0090: 6c 20 72 65 70 6f 73 69 74 6f 72 69 65 73 20 69 l repositories i
00a0: 73 20 74 68 65 20 75 73 65 20 6f 66 20 64 65 6c s the use of del
00b0: 74 61 2d 63 6f 6d 70 72 65 73 73 69 6f 6e 2c 20 ta-compression,
00c0: 69 2e 65 2e 20 74 6f 0a 73 74 6f 72 65 20 6f 6e i.e. to.store on
00d0: 6c 79 20 74 68 65 20 63 68 61 6e 67 65 73 20 62 ly the changes b
00e0: 65 74 77 65 65 6e 20 72 65 76 69 73 69 6f 6e 73 etween revisions
00f0: 20 69 6e 73 74 65 61 64 20 6f 66 20 74 68 65 20 instead of the
0100: 77 68 6f 6c 65 0a 66 69 6c 65 2e 3c 2f 70 3e 0a whole.file.</p>.
0110: 0a 3c 70 3e 54 68 69 73 20 64 6f 63 75 6d 65 6e .<p>This documen
0120: 74 20 64 65 73 63 72 69 62 65 73 20 74 68 65 20 t describes the
0130: 65 6e 63 6f 64 69 6e 67 20 61 6c 67 6f 72 69 74 encoding algorit
0140: 68 6d 20 75 73 65 64 20 62 79 20 46 6f 73 73 69 hm used by Fossi
0150: 6c 20 74 6f 0a 67 65 6e 65 72 61 74 65 20 64 65 l to.generate de
0160: 6c 74 61 73 2e 20 49 74 20 69 73 20 74 61 72 67 ltas. It is targ
0170: 65 74 65 64 20 61 74 20 64 65 76 65 6c 6f 70 65 eted at develope
0180: 72 73 20 77 6f 72 6b 69 6e 67 20 6f 6e 20 65 69 rs working on ei
0190: 74 68 65 72 0a 3c 61 20 68 72 65 66 3d 22 69 6e ther.<a href="in
01a0: 64 65 78 2e 68 74 6d 6c 22 3e 66 6f 73 73 69 6c dex.html">fossil
01b0: 3c 2f 61 3e 20 69 74 73 65 6c 66 2c 20 6f 72 20 </a> itself, or
01c0: 6f 6e 20 74 6f 6f 6c 73 20 63 6f 6d 70 61 74 69 on tools compati
01d0: 62 6c 65 20 77 69 74 68 0a 69 74 2e 20 54 68 65 ble with.it. The
01e0: 20 65 78 61 63 74 20 66 6f 72 6d 61 74 20 6f 66 exact format of
01f0: 20 74 68 65 20 67 65 6e 65 72 61 74 65 64 20 62 the generated b
0200: 79 74 65 2d 73 65 71 75 65 6e 63 65 73 2c 20 77 yte-sequences, w
0210: 68 69 6c 65 20 69 6e 20 67 65 6e 65 72 61 6c 0a hile in general.
0220: 6e 6f 74 20 6e 65 63 65 73 73 61 72 79 20 74 6f not necessary to
0230: 20 75 6e 64 65 72 73 74 61 6e 64 20 65 6e 63 6f understand enco
0240: 64 65 72 20 6f 70 65 72 61 74 69 6f 6e 2c 20 63 der operation, c
0250: 61 6e 20 62 65 20 66 6f 75 6e 64 20 69 6e 20 74 an be found in t
0260: 68 65 0a 63 6f 6d 70 61 6e 69 6f 6e 20 73 70 65 he.companion spe
0270: 63 69 66 69 63 61 74 69 6f 6e 20 74 69 74 6c 65 cification title
0280: 64 20 22 3c 61 20 68 72 65 66 3d 22 64 65 6c 74 d "<a href="delt
0290: 61 5f 66 6f 72 6d 61 74 2e 68 74 6d 6c 22 3e 46 a_format.html">F
02a0: 6f 73 73 69 6c 0a 44 65 6c 74 61 20 46 6f 72 6d ossil.Delta Form
02b0: 61 74 3c 2f 61 3e 22 2e 0a 3c 2f 70 3e 0a 0a 3c at</a>"..</p>..<
02c0: 70 3e 54 68 65 20 65 6e 74 69 72 65 20 61 6c 67 p>The entire alg
02d0: 6f 72 69 74 68 6d 20 69 73 20 69 6e 73 70 69 72 orithm is inspir
02e0: 65 64 0a 62 79 20 3c 61 20 68 72 65 66 3d 22 68 ed.by <a href="h
02f0: 74 74 70 3a 2f 2f 73 61 6d 62 61 2e 61 6e 75 2e ttp://samba.anu.
0300: 65 64 75 2e 61 75 2f 72 73 79 6e 63 2f 22 3e 72 edu.au/rsync/">r
0310: 73 79 6e 63 3c 2f 61 3e 2e 3c 2f 70 3e 0a 0a 3c sync</a>.</p>..<
0320: 61 20 6e 61 6d 65 3d 22 61 72 67 72 65 73 70 61 a name="argrespa
0330: 72 61 6d 22 3e 3c 68 32 3e 31 2e 30 20 41 72 67 ram"><h2>1.0 Arg
0340: 75 6d 65 6e 74 73 2c 20 52 65 73 75 6c 74 73 2c uments, Results,
0350: 20 61 6e 64 20 50 61 72 61 6d 65 74 65 72 73 3c and Parameters<
0360: 2f 68 32 3e 0a 0a 3c 70 3e 54 68 65 20 65 6e 63 /h2>..<p>The enc
0370: 6f 64 65 72 20 74 61 6b 65 73 20 74 77 6f 20 62 oder takes two b
0380: 79 74 65 2d 73 65 71 75 65 6e 63 65 73 20 61 73 yte-sequences as
0390: 20 69 6e 70 75 74 2c 20 74 68 65 20 22 6f 72 69 input, the "ori
03a0: 67 69 6e 61 6c 22 2c 20 61 6e 64 0a 74 68 65 20 ginal", and.the
03b0: 22 74 61 72 67 65 74 22 2c 20 61 6e 64 20 72 65 "target", and re
03c0: 74 75 72 6e 73 20 61 20 73 69 6e 67 6c 65 20 62 turns a single b
03d0: 79 74 65 2d 73 65 71 75 65 6e 63 65 20 63 6f 6e yte-sequence con
03e0: 74 61 69 6e 69 6e 67 20 74 68 65 0a 22 64 65 6c taining the."del
03f0: 74 61 22 20 77 68 69 63 68 20 74 72 61 6e 73 66 ta" which transf
0400: 6f 72 6d 73 20 74 68 65 20 6f 72 69 67 69 6e 61 orms the origina
0410: 6c 20 69 6e 74 6f 20 74 68 65 20 74 61 72 67 65 l into the targe
0420: 74 20 75 70 6f 6e 20 69 74 73 0a 61 70 70 6c 69 t upon its.appli
0430: 63 61 74 69 6f 6e 2e 3c 2f 70 3e 0a 0a 3c 70 3e cation.</p>..<p>
0440: 4e 6f 74 65 20 74 68 61 74 20 74 68 65 20 64 61 Note that the da
0450: 74 61 20 6f 66 20 61 20 22 62 79 74 65 2d 73 65 ta of a "byte-se
0460: 71 75 65 6e 63 65 22 20 69 6e 63 6c 75 64 65 73 quence" includes
0470: 20 69 74 73 20 6c 65 6e 67 74 68 2c 0a 69 2e 65 its length,.i.e
0480: 2e 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 . the number of
0490: 62 79 74 65 73 20 63 6f 6e 74 61 69 6e 65 64 20 bytes contained
04a0: 69 6e 20 74 68 65 20 73 65 71 75 65 6e 63 65 2e in the sequence.
04b0: 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 65 20 61 6c 67 </p>..<p>The alg
04c0: 6f 72 69 74 68 6d 20 68 61 73 20 6f 6e 65 20 70 orithm has one p
04d0: 61 72 61 6d 65 74 65 72 20 6e 61 6d 65 64 20 22 arameter named "
04e0: 4e 48 41 53 48 22 2c 20 74 68 65 20 73 69 7a 65 NHASH", the size
04f0: 20 6f 66 20 74 68 65 0a 22 73 6c 69 64 69 6e 67 of the."sliding
0500: 20 77 69 6e 64 6f 77 22 20 66 6f 72 20 74 68 65 window" for the
0510: 20 22 72 6f 6c 6c 69 6e 67 20 68 61 73 68 22 2c "rolling hash",
0520: 20 69 6e 20 62 79 74 65 73 2e 20 54 68 65 73 65 in bytes. These
0530: 20 74 77 6f 20 74 65 72 6d 73 20 61 72 65 0a 65 two terms are.e
0540: 78 70 6c 61 69 6e 65 64 20 69 6e 20 74 68 65 20 xplained in the
0550: 6e 65 78 74 20 73 65 63 74 69 6f 6e 2e 20 54 68 next section. Th
0560: 65 20 76 61 6c 75 65 20 6f 66 20 74 68 69 73 20 e value of this
0570: 70 61 72 61 6d 65 74 65 72 20 68 61 73 20 74 6f parameter has to
0580: 20 62 65 20 61 0a 70 6f 77 65 72 20 6f 66 20 74 be a.power of t
0590: 77 6f 20 66 6f 72 20 74 68 65 20 61 6c 67 6f 72 wo for the algor
05a0: 69 74 68 6d 20 74 6f 20 77 6f 72 6b 2e 20 46 6f ithm to work. Fo
05b0: 72 20 46 6f 73 73 69 6c 20 74 68 65 20 76 61 6c r Fossil the val
05c0: 75 65 20 6f 66 20 74 68 69 73 0a 70 61 72 61 6d ue of this.param
05d0: 65 74 65 72 20 69 73 20 73 65 74 20 74 6f 20 22 eter is set to "
05e0: 31 36 22 2e 3c 2f 70 3e 0a 0a 3c 61 20 6e 61 6d 16".</p>..<a nam
05f0: 65 3d 22 6f 70 65 72 61 74 69 6f 6e 22 3e 3c 68 e="operation"><h
0600: 32 3e 32 2e 30 20 4f 70 65 72 61 74 69 6f 6e 3c 2>2.0 Operation<
0610: 2f 68 32 3e 0a 0a 3c 70 3e 54 68 65 20 61 6c 67 /h2>..<p>The alg
0620: 6f 72 69 74 68 6d 20 69 73 20 73 70 6c 69 74 20 orithm is split
0630: 69 6e 74 6f 20 74 68 72 65 65 20 70 68 61 73 65 into three phase
0640: 73 20 77 68 69 63 68 20 67 65 6e 65 72 61 74 65 s which generate
0650: 0a 74 68 65 20 3c 61 20 68 72 65 66 3d 22 64 65 .the <a href="de
0660: 6c 74 61 5f 66 6f 72 6d 61 74 2e 68 74 6d 6c 23 lta_format.html#
0670: 68 65 61 64 65 72 22 3e 68 65 61 64 65 72 3c 2f header">header</
0680: 61 3e 2c 0a 3c 61 20 68 72 65 66 3d 22 64 65 6c a>,.<a href="del
0690: 74 61 5f 66 6f 72 6d 61 74 2e 68 74 6d 6c 23 73 ta_format.html#s
06a0: 6c 69 73 74 22 3e 73 65 67 6d 65 6e 74 20 6c 69 list">segment li
06b0: 73 74 3c 2f 61 3e 2c 0a 61 6e 64 20 3c 61 20 68 st</a>,.and <a h
06c0: 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 ref="delta_forma
06d0: 74 2e 68 74 6d 6c 23 74 72 61 69 6c 65 72 22 3e t.html#trailer">
06e0: 74 72 61 69 6c 65 72 3c 2f 61 3e 20 6f 66 20 74 trailer</a> of t
06f0: 68 65 20 64 65 6c 74 61 2c 20 70 65 72 0a 69 74 he delta, per.it
0700: 73 20 67 65 6e 65 72 61 6c 20 3c 61 20 68 72 65 s general <a hre
0710: 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 74 2e f="delta_format.
0720: 68 74 6d 6c 23 73 74 72 75 63 74 75 72 65 22 3e html#structure">
0730: 73 74 72 75 63 74 75 72 65 3c 2f 61 3e 2e 3c 2f structure</a>.</
0740: 70 3e 0a 0a 3c 70 3e 54 68 65 20 74 77 6f 20 70 p>..<p>The two p
0750: 68 61 73 65 73 20 67 65 6e 65 72 61 74 69 6e 67 hases generating
0760: 20 68 65 61 64 65 72 20 61 6e 64 20 74 72 61 69 header and trai
0770: 6c 65 72 20 61 72 65 20 6e 6f 74 20 63 6f 76 65 ler are not cove
0780: 72 65 64 20 68 65 72 65 0a 61 73 20 74 68 65 69 red here.as thei
0790: 72 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e r implementation
07a0: 20 74 72 69 76 69 61 6c 6c 79 20 66 6f 6c 6c 6f trivially follo
07b0: 77 73 20 64 69 72 65 63 74 6c 79 20 66 72 6f 6d ws directly from
07c0: 20 74 68 65 0a 73 70 65 63 69 66 69 63 61 74 69 the.specificati
07d0: 6f 6e 20 6f 66 20 74 68 65 20 3c 61 20 68 72 65 on of the <a hre
07e0: 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 74 2e f="delta_format.
07f0: 68 74 6d 6c 22 3e 64 65 6c 74 61 20 66 6f 72 6d html">delta form
0800: 61 74 3c 2f 61 3e 2e 3c 2f 70 3e 0a 0a 3c 70 3e at</a>.</p>..<p>
0810: 54 68 69 73 20 6c 65 61 76 65 73 20 74 68 65 20 This leaves the
0820: 73 65 67 6d 65 6e 74 2d 6c 69 73 74 2e 20 49 74 segment-list. It
0830: 73 20 67 65 6e 65 72 61 74 69 6f 6e 20 69 73 20 s generation is
0840: 64 6f 6e 65 20 69 6e 20 74 77 6f 20 70 68 61 73 done in two phas
0850: 65 73 2c 0a 61 20 70 72 65 2d 70 72 6f 63 65 73 es,.a pre-proces
0860: 73 69 6e 67 20 73 74 65 70 20 6f 70 65 72 61 74 sing step operat
0870: 69 6e 67 20 6f 6e 20 74 68 65 20 22 6f 72 69 67 ing on the "orig
0880: 69 6e 61 6c 22 20 62 79 74 65 2d 73 65 71 75 65 inal" byte-seque
0890: 6e 63 65 2c 0a 66 6f 6c 6c 6f 77 65 64 20 62 79 nce,.followed by
08a0: 20 74 68 65 20 70 72 6f 63 65 73 73 69 6e 67 20 the processing
08b0: 6f 66 20 74 68 65 20 22 74 61 72 67 65 74 22 20 of the "target"
08c0: 62 79 74 65 2d 73 65 71 75 65 6e 63 65 20 75 73 byte-sequence us
08d0: 69 6e 67 20 74 68 65 0a 69 6e 66 6f 72 6d 61 74 ing the.informat
08e0: 69 6f 6e 20 67 61 74 68 65 72 65 64 20 62 79 20 ion gathered by
08f0: 74 68 65 20 66 69 72 73 74 20 73 74 65 70 2e 3c the first step.<
0900: 2f 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 70 72 /p>..<a name="pr
0910: 65 70 72 6f 63 65 73 73 69 6e 67 22 3e 3c 68 33 eprocessing"><h3
0920: 3e 32 2e 31 20 50 72 65 70 72 6f 63 65 73 73 69 >2.1 Preprocessi
0930: 6e 67 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 3c ng the original<
0940: 2f 68 33 3e 0a 0a 3c 70 3e 41 20 6d 61 6a 6f 72 /h3>..<p>A major
0950: 20 70 61 72 74 20 6f 66 20 74 68 65 20 70 72 6f part of the pro
0960: 63 65 73 73 69 6e 67 20 6f 66 20 74 68 65 20 22 cessing of the "
0970: 74 61 72 67 65 74 22 20 69 73 20 74 6f 20 66 69 target" is to fi
0980: 6e 64 20 61 20 72 61 6e 67 65 0a 69 6e 20 74 68 nd a range.in th
0990: 65 20 22 6f 72 69 67 69 6e 61 6c 22 20 77 68 69 e "original" whi
09a0: 63 68 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 ch contains the
09b0: 73 61 6d 65 20 63 6f 6e 74 65 6e 74 20 61 73 20 same content as
09c0: 66 6f 75 6e 64 20 61 74 20 74 68 65 0a 63 75 72 found at the.cur
09d0: 72 65 6e 74 20 6c 6f 63 61 74 69 6f 6e 20 69 6e rent location in
09e0: 20 74 68 65 20 22 74 61 72 67 65 74 22 2e 3c 2f the "target".</
09f0: 70 3e 0a 0a 3c 70 3e 41 20 6e 61 69 76 65 20 61 p>..<p>A naive a
0a00: 70 70 72 6f 61 63 68 20 74 6f 20 74 68 69 73 20 pproach to this
0a10: 77 6f 75 6c 64 20 62 65 20 74 6f 20 73 65 61 72 would be to sear
0a20: 63 68 20 74 68 65 20 77 68 6f 6c 65 20 22 6f 72 ch the whole "or
0a30: 69 67 69 6e 61 6c 22 0a 66 6f 72 20 73 75 63 68 iginal".for such
0a40: 20 63 6f 6e 74 65 6e 74 2e 20 54 68 69 73 20 68 content. This h
0a50: 6f 77 65 76 65 72 20 69 73 20 76 65 72 79 20 69 owever is very i
0a60: 6e 65 66 66 69 63 69 65 6e 74 20 61 73 20 69 74 nefficient as it
0a70: 20 77 6f 75 6c 64 20 73 65 61 72 63 68 0a 74 68 would search.th
0a80: 65 20 73 61 6d 65 20 70 61 72 74 73 20 6f 66 20 e same parts of
0a90: 74 68 65 20 22 6f 72 69 67 69 6e 61 6c 22 20 6f the "original" o
0aa0: 76 65 72 20 61 6e 64 20 6f 76 65 72 2e 20 57 68 ver and over. Wh
0ab0: 61 74 20 69 73 20 64 6f 6e 65 20 69 6e 73 74 65 at is done inste
0ac0: 61 64 0a 69 73 20 74 6f 20 73 61 6d 70 6c 65 20 ad.is to sample
0ad0: 74 68 65 20 22 6f 72 69 67 69 6e 61 6c 22 20 61 the "original" a
0ae0: 74 20 72 65 67 75 6c 61 72 20 69 6e 74 65 72 76 t regular interv
0af0: 61 6c 73 2c 20 63 6f 6d 70 75 74 65 20 73 69 67 als, compute sig
0b00: 6e 61 74 75 72 65 73 0a 66 6f 72 20 74 68 65 20 natures.for the
0b10: 73 61 6d 70 6c 65 64 20 6c 6f 63 61 74 69 6f 6e sampled location
0b20: 73 20 61 6e 64 20 73 74 6f 72 65 20 74 68 65 6d s and store them
0b30: 20 69 6e 20 61 20 68 61 73 68 20 74 61 62 6c 65 in a hash table
0b40: 20 6b 65 79 65 64 20 62 79 0a 74 68 65 73 65 20 keyed by.these
0b50: 73 69 67 6e 61 74 75 72 65 73 2e 3c 2f 70 3e 0a signatures.</p>.
0b60: 0a 3c 70 3e 54 68 61 74 20 69 73 20 77 68 61 74 .<p>That is what
0b70: 20 68 61 70 70 65 6e 73 20 69 6e 20 74 68 69 73 happens in this
0b80: 20 73 74 65 70 2e 20 54 68 65 20 66 6f 6c 6c 6f step. The follo
0b90: 77 69 6e 67 20 70 72 6f 63 65 73 73 69 6e 67 20 wing processing
0ba0: 73 74 65 70 0a 63 61 6e 20 74 68 65 6e 20 74 68 step.can then th
0bb0: 65 20 63 6f 6d 70 75 74 65 20 73 69 67 6e 61 74 e compute signat
0bc0: 75 72 65 20 66 6f 72 20 69 74 73 20 63 75 72 72 ure for its curr
0bd0: 65 6e 74 20 6c 6f 63 61 74 69 6f 6e 20 61 6e 64 ent location and
0be0: 20 74 68 65 6e 20 68 61 73 0a 74 6f 20 73 65 61 then has.to sea
0bf0: 72 63 68 20 6f 6e 6c 79 20 61 20 6e 61 72 72 6f rch only a narro
0c00: 77 20 73 65 74 20 6f 66 20 6c 6f 63 61 74 69 6f w set of locatio
0c10: 6e 73 20 69 6e 20 74 68 65 20 22 6f 72 69 67 69 ns in the "origi
0c20: 6e 61 6c 22 20 66 6f 72 0a 70 6f 73 73 69 62 6c nal" for.possibl
0c30: 65 20 6d 61 74 63 68 65 73 2c 20 6e 61 6d 65 6c e matches, namel
0c40: 79 20 74 68 6f 73 65 20 77 68 69 63 68 20 68 61 y those which ha
0c50: 76 65 20 74 68 65 20 73 61 6d 65 20 73 69 67 6e ve the same sign
0c60: 61 74 75 72 65 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 ature.</p>..<p>I
0c70: 6e 20 64 65 74 61 69 6c 3a 3c 2f 70 3e 0a 0a 3c n detail:</p>..<
0c80: 6f 6c 3e 0a 3c 6c 69 3e 54 68 65 20 22 6f 72 69 ol>.<li>The "ori
0c90: 67 69 6e 61 6c 22 20 69 73 20 73 70 6c 69 74 20 ginal" is split
0ca0: 69 6e 74 6f 20 63 68 75 6e 6b 73 20 6f 66 20 4e into chunks of N
0cb0: 48 41 53 48 20 62 79 74 65 73 2e 20 4e 6f 74 65 HASH bytes. Note
0cc0: 20 74 68 61 74 20 61 0a 70 61 72 74 69 61 6c 20 that a.partial
0cd0: 63 68 75 6e 6b 20 6f 66 20 6c 65 73 73 20 74 68 chunk of less th
0ce0: 61 6e 20 4e 48 41 53 48 20 62 79 74 65 73 20 61 an NHASH bytes a
0cf0: 74 20 74 68 65 20 65 6e 64 20 6f 66 20 22 6f 72 t the end of "or
0d00: 69 67 69 6e 61 6c 22 20 69 73 0a 69 67 6e 6f 72 iginal" is.ignor
0d10: 65 64 2e 0a 3c 2f 6c 69 3e 0a 3c 6c 69 3e 54 68 ed..</li>.<li>Th
0d20: 65 20 3c 61 20 68 72 65 66 3d 22 23 72 6f 6c 6c e <a href="#roll
0d30: 68 61 73 68 22 3e 72 6f 6c 6c 69 6e 67 20 68 61 hash">rolling ha
0d40: 73 68 3c 2f 61 3e 20 6f 66 20 65 61 63 68 20 63 sh</a> of each c
0d50: 68 75 6e 6b 20 69 73 0a 63 6f 6d 70 75 74 65 64 hunk is.computed
0d60: 2e 0a 3c 2f 6c 69 3e 0a 3c 6c 69 3e 41 20 68 61 ..</li>.<li>A ha
0d70: 73 68 74 61 62 6c 65 20 69 73 20 66 69 6c 6c 65 shtable is fille
0d80: 64 2c 20 6d 61 70 70 69 6e 67 20 66 72 6f 6d 20 d, mapping from
0d90: 74 68 65 20 68 61 73 68 65 73 20 6f 66 20 74 68 the hashes of th
0da0: 65 20 63 68 75 6e 6b 73 20 74 6f 0a 74 68 65 20 e chunks to.the
0db0: 6c 69 73 74 20 6f 66 20 63 68 75 6e 6b 20 6c 6f list of chunk lo
0dc0: 63 61 74 69 6f 6e 73 20 68 61 76 69 6e 67 20 74 cations having t
0dd0: 68 69 73 20 68 61 73 68 2e 0a 3c 2f 6c 69 3e 0a his hash..</li>.
0de0: 3c 2f 6f 6c 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 </ol>..<a name="
0df0: 70 72 6f 63 65 73 73 69 6e 67 22 3e 3c 68 33 3e processing"><h3>
0e00: 32 2e 31 20 50 72 6f 63 65 73 73 69 6e 67 20 74 2.1 Processing t
0e10: 68 65 20 74 61 72 67 65 74 3c 2f 68 33 3e 0a 0a he target</h3>..
0e20: 3c 70 3e 54 68 69 73 2c 20 74 68 65 20 6d 61 69 <p>This, the mai
0e30: 6e 20 70 68 61 73 65 20 6f 66 20 74 68 65 20 65 n phase of the e
0e40: 6e 63 6f 64 65 72 2c 20 70 72 6f 63 65 73 73 65 ncoder, processe
0e50: 73 20 74 68 65 20 74 61 72 67 65 74 20 69 6e 20 s the target in
0e60: 61 20 6c 6f 6f 70 0a 66 72 6f 6d 20 62 65 67 69 a loop.from begi
0e70: 6e 6e 69 6e 67 20 74 6f 20 65 6e 64 2e 20 54 68 nning to end. Th
0e80: 65 20 73 74 61 74 65 20 6f 66 20 74 68 65 20 65 e state of the e
0e90: 6e 63 6f 64 65 72 20 69 73 20 63 61 70 74 75 72 ncoder is captur
0ea0: 65 64 20 62 79 20 74 77 6f 0a 6c 6f 63 61 74 69 ed by two.locati
0eb0: 6f 6e 73 2c 20 74 68 65 20 22 62 61 73 65 22 20 ons, the "base"
0ec0: 61 6e 64 20 74 68 65 20 22 73 6c 69 64 65 22 2e and the "slide".
0ed0: 20 22 62 61 73 65 22 20 70 6f 69 6e 74 73 20 74 "base" points t
0ee0: 6f 20 74 68 65 20 66 69 72 73 74 20 62 79 74 65 o the first byte
0ef0: 0a 6f 66 20 74 68 65 20 74 61 72 67 65 74 20 66 .of the target f
0f00: 6f 72 20 77 68 69 63 68 20 6e 6f 20 64 65 6c 74 or which no delt
0f10: 61 20 6f 75 74 70 75 74 20 68 61 73 20 62 65 65 a output has bee
0f20: 6e 20 67 65 6e 65 72 61 74 65 64 20 79 65 74 2c n generated yet,
0f30: 20 61 6e 64 0a 22 73 6c 69 64 65 22 20 69 73 20 and."slide" is
0f40: 74 68 65 20 6c 6f 63 61 74 69 6f 6e 20 6f 66 20 the location of
0f50: 74 68 65 20 77 69 6e 64 6f 77 20 75 73 65 64 20 the window used
0f60: 74 6f 20 6c 6f 6f 6b 20 69 6e 20 74 68 65 20 22 to look in the "
0f70: 6f 72 69 67 69 6e 22 20 66 6f 72 0a 63 6f 6d 6d origin" for.comm
0f80: 6f 6e 61 6c 69 74 69 65 73 2e 20 54 68 69 73 20 onalities. This
0f90: 77 69 6e 64 6f 77 20 69 73 20 4e 48 41 53 48 20 window is NHASH
0fa0: 62 79 74 65 73 20 6c 6f 6e 67 2e 3c 2f 70 3e 0a bytes long.</p>.
0fb0: 0a 3c 70 3e 49 6e 69 74 69 61 6c 6c 79 20 62 6f .<p>Initially bo
0fc0: 74 68 20 22 62 61 73 65 22 20 61 6e 64 20 22 73 th "base" and "s
0fd0: 6c 69 64 65 22 20 70 6f 69 6e 74 20 74 6f 20 74 lide" point to t
0fe0: 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 he beginning of
0ff0: 74 68 65 0a 22 74 61 72 67 65 74 22 2e 20 49 6e the."target". In
1000: 20 65 61 63 68 20 69 74 65 72 61 74 69 6f 6e 20 each iteration
1010: 6f 66 20 74 68 65 20 6c 6f 6f 70 20 74 68 65 20 of the loop the
1020: 65 6e 63 6f 64 65 72 20 64 65 63 69 64 65 73 20 encoder decides
1030: 77 68 65 74 68 65 72 20 74 6f 0a 3c 75 6c 3e 0a whether to.<ul>.
1040: 3c 6c 69 3e 65 6d 69 74 20 61 20 73 69 6e 67 6c <li>emit a singl
1050: 65 20 69 6e 73 74 72 75 63 74 69 6f 6e 0a 74 6f e instruction.to
1060: 20 3c 61 20 68 72 65 66 3d 22 64 65 6c 74 61 5f <a href="delta_
1070: 66 6f 72 6d 61 74 2e 68 74 6d 6c 23 63 6f 70 79 format.html#copy
1080: 72 61 6e 67 65 22 3e 63 6f 70 79 20 61 20 72 61 range">copy a ra
1090: 6e 67 65 3c 2f 61 3e 2c 20 6f 72 0a 3c 2f 6c 69 nge</a>, or.</li
10a0: 3e 0a 3c 6c 69 3e 65 6d 69 74 20 74 77 6f 20 69 >.<li>emit two i
10b0: 6e 73 74 72 75 63 74 69 6f 6e 73 2c 20 66 69 72 nstructions, fir
10c0: 73 74 0a 74 6f 20 3c 61 20 68 72 65 66 3d 22 64 st.to <a href="d
10d0: 65 6c 74 61 5f 66 6f 72 6d 61 74 2e 68 74 6d 6c elta_format.html
10e0: 23 69 6e 73 65 72 74 6c 69 74 22 3e 69 6e 73 65 #insertlit">inse
10f0: 72 74 20 61 20 6c 69 74 65 72 61 6c 3c 2f 61 3e rt a literal</a>
1100: 2c 20 74 68 65 6e 0a 74 6f 20 3c 61 20 68 72 65 , then.to <a hre
1110: 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 74 2e f="delta_format.
1120: 68 74 6d 6c 23 63 6f 70 79 72 61 6e 67 65 22 3e html#copyrange">
1130: 63 6f 70 79 20 61 20 72 61 6e 67 65 3c 2f 61 3e copy a range</a>
1140: 2c 20 6f 72 0a 3c 2f 6c 69 3e 0a 3c 6c 69 3e 6d , or.</li>.<li>m
1150: 6f 76 65 20 74 68 65 20 77 69 6e 64 6f 77 20 66 ove the window f
1160: 6f 72 77 61 72 64 20 6f 6e 65 20 62 79 74 65 2e orward one byte.
1170: 0a 3c 2f 6c 69 3e 0a 3c 2f 75 6c 3e 0a 3c 2f 70 .</li>.</ul>.</p
1180: 3e 0a 0a 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 >..<img src="enc
1190: 6f 64 65 31 30 2e 67 69 66 22 20 61 6c 69 67 6e ode10.gif" align
11a0: 3d 22 72 69 67 68 74 22 20 68 73 70 61 63 65 3d ="right" hspace=
11b0: 22 31 30 22 3e 0a 3c 70 3e 54 6f 20 6d 61 6b 65 "10">.<p>To make
11c0: 20 74 68 69 73 20 64 65 63 69 73 69 6f 6e 20 74 this decision t
11d0: 68 65 20 65 6e 63 6f 64 65 72 20 66 69 72 73 74 he encoder first
11e0: 20 63 6f 6d 70 75 74 65 73 20 74 68 65 20 68 61 computes the ha
11f0: 73 68 20 76 61 6c 75 65 20 66 6f 72 0a 74 68 65 sh value for.the
1200: 20 4e 48 41 53 48 20 62 79 74 65 73 20 69 6e 20 NHASH bytes in
1210: 74 68 65 20 77 69 6e 64 6f 77 20 61 6e 64 20 74 the window and t
1220: 68 65 6e 20 6c 6f 6f 6b 73 20 61 74 20 61 6c 6c hen looks at all
1230: 20 74 68 65 20 6c 6f 63 61 74 69 6f 6e 73 20 69 the locations i
1240: 6e 0a 74 68 65 20 22 6f 72 69 67 69 6e 22 20 77 n.the "origin" w
1250: 68 69 63 68 20 68 61 76 65 20 74 68 65 20 73 61 hich have the sa
1260: 6d 65 20 73 69 67 6e 61 74 75 72 65 2e 20 54 68 me signature. Th
1270: 69 73 20 70 61 72 74 20 75 73 65 73 20 74 68 65 is part uses the
1280: 20 68 61 73 68 0a 74 61 62 6c 65 20 63 72 65 61 hash.table crea
1290: 74 65 64 20 62 79 20 74 68 65 20 70 72 65 2d 70 ted by the pre-p
12a0: 72 6f 63 65 73 73 69 6e 67 20 73 74 65 70 20 74 rocessing step t
12b0: 6f 20 65 66 66 69 65 6e 74 6c 79 20 66 69 6e 64 o effiently find
12c0: 20 74 68 65 73 65 0a 6c 6f 63 61 74 69 6f 6e 73 these.locations
12d0: 2e 3c 2f 70 3e 0a 0a 3c 70 3e 46 6f 72 20 65 61 .</p>..<p>For ea
12e0: 63 68 20 6f 66 20 74 68 65 20 70 6f 73 73 69 62 ch of the possib
12f0: 6c 65 20 63 61 6e 64 69 64 61 74 65 73 20 74 68 le candidates th
1300: 65 20 65 6e 63 6f 64 65 72 20 66 69 6e 64 73 20 e encoder finds
1310: 74 68 65 20 6d 61 78 69 6d 61 6c 0a 72 61 6e 67 the maximal.rang
1320: 65 20 6f 66 20 62 79 74 65 73 20 63 6f 6d 6d 6f e of bytes commo
1330: 6e 20 74 6f 20 62 6f 74 68 20 22 6f 72 69 67 69 n to both "origi
1340: 6e 22 20 61 6e 64 20 22 74 61 72 67 65 74 22 2c n" and "target",
1350: 20 67 6f 69 6e 67 20 66 6f 72 77 61 72 64 20 61 going forward a
1360: 6e 64 0a 62 61 63 6b 77 61 72 64 20 66 72 6f 6d nd.backward from
1370: 20 22 73 6c 69 64 65 22 20 69 6e 20 74 68 65 20 "slide" in the
1380: 22 74 61 72 67 65 74 22 2c 20 61 6e 64 20 74 68 "target", and th
1390: 65 20 63 61 6e 64 69 64 61 74 65 20 6c 6f 63 61 e candidate loca
13a0: 74 69 6f 6e 20 69 6e 0a 74 68 65 20 22 6f 72 69 tion in.the "ori
13b0: 67 69 6e 22 2e 20 54 68 69 73 20 73 65 61 72 63 gin". This searc
13c0: 68 20 69 73 20 63 6f 6e 73 74 72 61 69 6e 65 64 h is constrained
13d0: 20 6f 6e 20 74 68 65 20 73 69 64 65 20 6f 66 20 on the side of
13e0: 74 68 65 20 22 74 61 72 67 65 74 22 0a 62 79 20 the "target".by
13f0: 74 68 65 20 22 62 61 73 65 22 20 28 62 61 63 6b the "base" (back
1400: 77 61 72 64 20 73 65 61 72 63 68 29 2c 20 61 6e ward search), an
1410: 64 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 d the end of the
1420: 20 22 74 61 72 67 65 74 22 20 28 66 6f 72 77 61 "target" (forwa
1430: 72 64 0a 73 65 61 72 63 68 29 2c 20 61 6e 64 20 rd.search), and
1440: 6f 6e 20 74 68 65 20 73 69 64 65 20 6f 66 20 74 on the side of t
1450: 68 65 20 22 6f 72 69 67 69 6e 22 20 62 79 20 74 he "origin" by t
1460: 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 61 6e 64 he beginning and
1470: 20 65 6e 64 20 6f 66 0a 74 68 65 20 22 6f 72 69 end of.the "ori
1480: 67 69 6e 22 2c 20 72 65 73 70 65 63 74 69 76 65 gin", respective
1490: 6c 79 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 65 72 ly.</p>..<p>Ther
14a0: 65 20 61 72 65 20 69 6e 70 75 74 20 66 69 6c 65 e are input file
14b0: 73 20 66 6f 72 20 77 68 69 63 68 20 74 68 65 20 s for which the
14c0: 68 61 73 68 20 63 68 61 69 6e 73 20 67 65 6e 65 hash chains gene
14d0: 72 61 74 65 64 20 62 79 20 74 68 65 0a 70 72 65 rated by the.pre
14e0: 2d 70 72 6f 63 65 73 73 69 6e 67 20 73 74 65 70 -processing step
14f0: 20 63 61 6e 20 62 65 63 6f 6d 65 20 76 65 72 79 can become very
1500: 20 6c 6f 6e 67 2c 20 6c 65 61 64 69 6e 67 20 74 long, leading t
1510: 6f 20 6c 6f 6e 67 20 73 65 61 72 63 68 20 74 69 o long search ti
1520: 6d 65 73 0a 61 6e 64 20 61 66 66 65 63 74 69 6e mes.and affectin
1530: 67 20 74 68 65 20 70 65 72 66 6f 72 6d 61 6e 63 g the performanc
1540: 65 20 6f 66 20 74 68 65 20 64 65 6c 74 61 20 67 e of the delta g
1550: 65 6e 65 72 61 74 6f 72 2e 20 54 6f 20 6c 69 6d enerator. To lim
1560: 69 74 20 74 68 65 0a 65 66 66 65 63 74 20 73 75 it the.effect su
1570: 63 68 20 6c 6f 6e 67 20 63 68 61 69 6e 73 20 63 ch long chains c
1580: 61 6e 20 68 61 76 65 20 74 68 65 20 61 63 74 75 an have the actu
1590: 61 6c 20 73 65 61 72 63 68 20 66 6f 72 20 63 61 al search for ca
15a0: 6e 64 69 64 61 74 65 73 20 69 73 0a 62 6f 75 6e ndidates is.boun
15b0: 64 65 64 2c 20 6c 6f 6f 6b 69 6e 67 20 61 74 20 ded, looking at
15c0: 6d 6f 73 74 20 4e 20 63 61 6e 64 69 64 61 74 65 most N candidate
15d0: 73 2e 20 43 75 72 72 65 6e 74 6c 79 20 4e 20 69 s. Currently N i
15e0: 73 20 73 65 74 20 74 6f 20 32 35 30 2e 3c 2f 70 s set to 250.</p
15f0: 3e 0a 0a 3c 70 3e 46 72 6f 6d 20 74 68 65 20 72 >..<p>From the r
1600: 61 6e 67 65 73 20 66 6f 72 20 61 6c 6c 20 74 68 anges for all th
1610: 65 20 63 61 6e 64 69 64 61 74 65 73 20 74 68 65 e candidates the
1620: 20 62 65 73 74 20 28 3d 20 6c 61 72 67 65 73 74 best (= largest
1630: 29 20 63 6f 6d 6d 6f 6e 0a 72 61 6e 67 65 20 69 ) common.range i
1640: 73 20 74 61 6b 65 6e 20 61 6e 64 20 69 74 20 69 s taken and it i
1650: 73 20 64 65 74 65 72 6d 69 6e 65 64 20 68 6f 77 s determined how
1660: 20 6d 61 6e 79 20 62 79 74 65 73 20 61 72 65 20 many bytes are
1670: 6e 65 65 64 65 64 20 74 6f 0a 65 6e 63 6f 64 65 needed to.encode
1680: 20 74 68 65 20 62 79 74 65 73 20 62 65 74 77 65 the bytes betwe
1690: 65 6e 20 74 68 65 20 22 62 61 73 65 22 20 61 6e en the "base" an
16a0: 64 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 61 d the end of tha
16b0: 74 20 72 61 6e 67 65 2e 20 49 66 20 74 68 65 0a t range. If the.
16c0: 72 61 6e 67 65 20 65 78 74 65 6e 64 65 64 20 62 range extended b
16d0: 61 63 6b 20 74 6f 20 74 68 65 20 22 62 61 73 65 ack to the "base
16e0: 22 20 74 68 65 6e 20 74 68 69 73 20 63 61 6e 20 " then this can
16f0: 62 65 20 64 6f 6e 65 20 69 6e 20 61 20 73 69 6e be done in a sin
1700: 67 6c 65 0a 63 6f 70 79 20 69 6e 73 74 72 75 63 gle.copy instruc
1710: 74 69 6f 6e 2e 20 4f 74 68 65 72 77 69 73 65 2c tion. Otherwise,
1720: 20 69 2e 65 20 69 66 20 74 68 65 72 65 20 69 73 i.e if there is
1730: 20 61 20 67 61 70 20 62 65 74 77 65 65 6e 20 74 a gap between t
1740: 68 65 20 22 62 61 73 65 22 0a 61 6e 64 20 74 68 he "base".and th
1750: 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 74 e beginning of t
1760: 68 65 20 72 61 6e 67 65 20 74 68 65 6e 20 74 77 he range then tw
1770: 6f 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 20 61 o instructions a
1780: 72 65 20 6e 65 65 64 65 64 2c 20 6f 6e 65 0a 74 re needed, one.t
1790: 6f 20 69 6e 73 65 72 74 20 74 68 65 20 62 79 74 o insert the byt
17a0: 65 73 20 69 6e 20 74 68 65 20 67 61 70 20 61 73 es in the gap as
17b0: 20 61 20 6c 69 74 65 72 61 6c 2c 20 61 6e 64 20 a literal, and
17c0: 61 20 63 6f 70 79 20 69 6e 73 74 72 75 63 74 69 a copy instructi
17d0: 6f 6e 0a 66 6f 72 20 74 68 65 20 72 61 6e 67 65 on.for the range
17e0: 20 69 74 73 65 6c 66 2e 20 54 68 65 20 67 65 6e itself. The gen
17f0: 65 72 61 6c 20 73 69 74 75 61 74 69 6f 6e 20 61 eral situation a
1800: 74 20 74 68 69 73 20 70 6f 69 6e 74 20 63 61 6e t this point can
1810: 20 62 65 20 73 65 65 6e 0a 69 6e 20 74 68 65 20 be seen.in the
1820: 70 69 63 74 75 72 65 20 74 6f 20 74 68 65 20 72 picture to the r
1830: 69 67 68 74 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 66 ight.</p>..<p>If
1840: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 62 the number of b
1850: 79 74 65 73 20 6e 65 65 64 65 64 20 74 6f 20 65 ytes needed to e
1860: 6e 63 6f 64 65 20 62 6f 74 68 20 67 61 70 20 28 ncode both gap (
1870: 69 66 20 70 72 65 73 65 6e 74 29 2c 20 61 6e 64 if present), and
1880: 0a 72 61 6e 67 65 20 69 73 20 6c 65 73 73 20 74 .range is less t
1890: 68 61 6e 20 74 68 65 20 6e 75 6d 62 65 72 20 6f han the number o
18a0: 66 20 62 79 74 65 73 20 77 65 20 61 72 65 20 65 f bytes we are e
18b0: 6e 63 6f 64 69 6e 67 20 74 68 65 20 65 6e 63 6f ncoding the enco
18c0: 64 65 72 0a 77 69 6c 6c 20 65 6d 69 74 20 74 68 der.will emit th
18d0: 65 20 6e 65 63 65 73 73 61 72 79 20 69 6e 73 74 e necessary inst
18e0: 72 75 63 74 69 6f 6e 73 20 61 73 20 64 65 73 63 ructions as desc
18f0: 72 69 62 65 64 20 61 62 6f 76 65 2c 20 73 65 74 ribed above, set
1900: 20 22 62 61 73 65 22 0a 61 6e 64 20 22 73 6c 69 "base".and "sli
1910: 64 65 22 20 74 6f 20 74 68 65 20 65 6e 64 20 6f de" to the end o
1920: 66 20 74 68 65 20 65 6e 63 6f 64 65 64 20 72 61 f the encoded ra
1930: 6e 67 65 20 61 6e 64 20 73 74 61 72 74 20 74 68 nge and start th
1940: 65 20 6e 65 78 74 0a 69 74 65 72 61 74 69 6f 6e e next.iteration
1950: 20 61 74 20 74 68 61 74 20 70 6f 69 6e 74 2e 3c at that point.<
1960: 2f 70 3e 0a 0a 3c 70 3e 49 66 2c 20 6f 6e 20 74 /p>..<p>If, on t
1970: 68 65 20 6f 74 68 65 72 20 68 61 6e 64 2c 20 74 he other hand, t
1980: 68 65 20 65 6e 63 6f 64 65 72 20 65 69 74 68 65 he encoder eithe
1990: 72 20 64 69 64 20 6e 6f 74 20 66 69 6e 64 20 63 r did not find c
19a0: 61 6e 64 69 64 61 74 65 0a 6c 6f 63 61 74 69 6f andidate.locatio
19b0: 6e 73 20 69 6e 20 74 68 65 20 6f 72 69 67 69 6e ns in the origin
19c0: 2c 20 6f 72 20 74 68 65 20 62 65 73 74 20 72 61 , or the best ra
19d0: 6e 67 65 20 63 6f 6d 69 6e 67 20 6f 75 74 20 6f nge coming out o
19e0: 66 20 74 68 65 20 73 65 61 72 63 68 0a 6e 65 65 f the search.nee
19f0: 64 65 64 20 6d 6f 72 65 20 62 79 74 65 73 20 74 ded more bytes t
1a00: 6f 20 65 6e 63 6f 64 65 20 74 68 65 20 72 61 6e o encode the ran
1a10: 67 65 20 74 68 61 6e 20 74 68 65 72 65 20 77 65 ge than there we
1a20: 72 65 20 62 79 74 65 73 20 69 6e 20 74 68 65 0a re bytes in the.
1a30: 72 61 6e 67 65 2c 20 74 68 65 6e 20 6e 6f 20 69 range, then no i
1a40: 6e 73 74 72 75 63 74 69 6f 6e 73 20 61 72 65 20 nstructions are
1a50: 65 6d 69 74 74 65 64 20 61 6e 64 20 74 68 65 20 emitted and the
1a60: 77 69 6e 64 6f 77 20 69 73 20 6d 6f 76 65 64 20 window is moved
1a70: 6f 6e 65 0a 62 79 74 65 20 66 6f 72 77 61 72 64 one.byte forward
1a80: 2e 20 54 68 65 20 22 62 61 73 65 22 20 69 73 20 . The "base" is
1a90: 6c 65 66 74 20 75 6e 63 68 61 6e 67 65 64 20 69 left unchanged i
1aa0: 6e 20 74 68 61 74 20 63 61 73 65 2e 3c 2f 70 3e n that case.</p>
1ab0: 0a 0a 3c 70 3e 54 68 65 20 70 72 6f 63 65 73 73 ..<p>The process
1ac0: 69 6e 67 20 6c 6f 6f 70 20 73 74 6f 70 73 20 61 ing loop stops a
1ad0: 74 20 6f 6e 65 20 6f 66 20 74 77 6f 20 63 6f 6e t one of two con
1ae0: 64 69 74 69 6f 6e 73 3a 0a 3c 6f 6c 3e 0a 3c 6c ditions:.<ol>.<l
1af0: 69 3e 54 68 65 20 65 6e 63 6f 64 65 72 20 64 65 i>The encoder de
1b00: 63 69 64 65 64 20 74 6f 20 6d 6f 76 65 20 74 68 cided to move th
1b10: 65 20 77 69 6e 64 6f 77 20 66 6f 72 77 61 72 64 e window forward
1b20: 2c 20 62 75 74 20 74 68 65 20 65 6e 64 20 6f 66 , but the end of
1b30: 20 74 68 65 0a 77 69 6e 64 6f 77 20 72 65 61 63 the.window reac
1b40: 68 65 64 20 74 68 65 20 65 6e 64 20 6f 66 20 74 hed the end of t
1b50: 68 65 20 22 74 61 72 67 65 74 22 2e 20 0a 3c 2f he "target". .</
1b60: 6c 69 3e 0a 3c 6c 69 3e 41 66 74 65 72 20 74 68 li>.<li>After th
1b70: 65 20 65 6d 69 73 73 69 6f 6e 20 6f 66 20 69 6e e emission of in
1b80: 73 74 72 75 63 74 69 6f 6e 73 20 74 68 65 20 6e structions the n
1b90: 65 77 20 22 62 61 73 65 22 20 6c 6f 63 61 74 69 ew "base" locati
1ba0: 6f 6e 20 69 73 0a 77 69 74 68 69 6e 20 4e 48 41 on is.within NHA
1bb0: 53 48 20 62 79 74 65 73 20 6f 66 20 65 6e 64 20 SH bytes of end
1bc0: 6f 66 20 74 68 65 20 22 74 61 72 67 65 74 22 2c of the "target",
1bd0: 20 69 2e 65 2e 20 74 68 65 72 65 20 61 72 65 20 i.e. there are
1be0: 6e 6f 20 6d 6f 72 65 20 74 68 61 6e 0a 61 74 20 no more than.at
1bf0: 6d 6f 73 74 20 4e 48 41 53 48 20 62 79 74 65 73 most NHASH bytes
1c00: 20 6c 65 66 74 2e 0a 3c 2f 6c 69 3e 0a 3c 2f 6f left..</li>.</o
1c10: 6c 3e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 49 66 20 74 l>.</p>..<p>If t
1c20: 68 65 20 70 72 6f 63 65 73 73 69 6e 67 20 6c 6f he processing lo
1c30: 6f 70 20 6c 65 66 74 20 62 79 74 65 73 20 75 6e op left bytes un
1c40: 65 6e 63 6f 64 65 64 2c 20 69 2e 65 2e 20 22 62 encoded, i.e. "b
1c50: 61 73 65 22 20 6e 6f 74 0a 65 78 61 63 74 6c 79 ase" not.exactly
1c60: 20 61 74 20 74 68 65 20 65 6e 64 20 6f 66 20 74 at the end of t
1c70: 68 65 20 22 74 61 72 67 65 74 22 2c 20 61 73 20 he "target", as
1c80: 69 73 20 70 6f 73 73 69 62 6c 65 20 66 6f 72 20 is possible for
1c90: 62 6f 74 68 20 65 6e 64 0a 63 6f 6e 64 69 74 69 both end.conditi
1ca0: 6f 6e 73 2c 20 74 68 65 6e 20 6f 6e 65 20 6c 61 ons, then one la
1cb0: 73 74 20 69 6e 73 65 72 74 20 69 6e 73 74 72 75 st insert instru
1cc0: 63 74 69 6f 6e 20 69 73 20 65 6d 69 74 74 65 64 ction is emitted
1cd0: 20 74 6f 20 70 75 74 20 74 68 65 73 65 0a 62 79 to put these.by
1ce0: 74 65 73 20 69 6e 74 6f 20 74 68 65 20 64 65 6c tes into the del
1cf0: 74 61 2e 3c 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d ta.<p>..<a name=
1d00: 22 65 78 63 65 70 74 69 6f 6e 73 22 3e 3c 68 32 "exceptions"><h2
1d10: 3e 33 2e 30 20 45 78 63 65 70 74 69 6f 6e 73 3c >3.0 Exceptions<
1d20: 2f 68 32 3e 0a 0a 3c 70 3e 49 66 20 74 68 65 20 /h2>..<p>If the
1d30: 22 6f 72 69 67 69 6e 61 6c 22 20 69 73 20 61 74 "original" is at
1d40: 20 6d 6f 73 74 20 4e 48 41 53 48 20 62 79 74 65 most NHASH byte
1d50: 73 20 6c 6f 6e 67 20 6e 6f 20 63 6f 6d 70 72 65 s long no compre
1d60: 73 73 69 6f 6e 20 6f 66 0a 63 68 61 6e 67 65 73 ssion of.changes
1d70: 20 69 73 20 70 6f 73 73 69 62 6c 65 2c 20 61 6e is possible, an
1d80: 64 20 74 68 65 20 73 65 67 6d 65 6e 74 2d 6c 69 d the segment-li
1d90: 73 74 20 6f 66 20 74 68 65 20 64 65 6c 74 61 20 st of the delta
1da0: 63 6f 6e 73 69 73 74 73 20 6f 66 20 61 0a 73 69 consists of a.si
1db0: 6e 67 6c 65 20 6c 69 74 65 72 61 6c 20 77 68 69 ngle literal whi
1dc0: 63 68 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 ch contains the
1dd0: 65 6e 74 69 72 65 20 22 74 61 72 67 65 74 22 2e entire "target".
1de0: 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 69 73 20 69 73 </p>..<p>This is
1df0: 20 61 63 74 75 61 6c 6c 79 20 65 71 75 69 76 61 actually equiva
1e00: 6c 65 6e 74 20 74 6f 20 74 68 65 20 73 65 63 6f lent to the seco
1e10: 6e 64 20 65 6e 64 20 63 6f 6e 64 69 74 69 6f 6e nd end condition
1e20: 20 6f 66 20 74 68 65 0a 70 72 6f 63 65 73 73 69 of the.processi
1e30: 6e 67 20 6c 6f 6f 70 20 64 65 73 63 72 69 62 65 ng loop describe
1e40: 64 20 69 6e 20 74 68 65 20 70 72 65 76 69 6f 75 d in the previou
1e50: 73 20 73 65 63 74 69 6f 6e 2c 20 6a 75 73 74 20 s section, just
1e60: 63 68 65 63 6b 65 64 20 62 65 66 6f 72 65 0a 61 checked before.a
1e70: 63 74 75 61 6c 6c 79 20 65 6e 74 65 72 69 6e 67 ctually entering
1e80: 20 74 68 65 20 6c 6f 6f 70 2e 3c 2f 70 3e 0a 0a the loop.</p>..
1e90: 3c 61 20 6e 61 6d 65 3d 22 72 6f 6c 6c 68 61 73 <a name="rollhas
1ea0: 68 22 3e 3c 68 32 3e 34 2e 30 20 54 68 65 20 72 h"><h2>4.0 The r
1eb0: 6f 6c 6c 69 6e 67 20 68 61 73 68 3c 2f 68 32 3e olling hash</h2>
1ec0: 0a 0a 3c 70 3e 54 68 65 20 72 6f 6c 6c 69 6e 67 ..<p>The rolling
1ed0: 20 68 61 73 68 20 64 65 73 63 72 69 62 65 64 20 hash described
1ee0: 62 65 6c 6f 77 20 61 6e 64 20 75 73 65 64 20 74 below and used t
1ef0: 6f 20 63 6f 6d 70 75 74 65 20 63 6f 6e 74 65 6e o compute conten
1f00: 74 0a 73 69 67 6e 61 74 75 72 65 73 20 77 61 73 t.signatures was
1f10: 20 63 68 6f 73 65 6e 20 6e 6f 74 20 6f 6e 6c 79 chosen not only
1f20: 20 66 6f 72 20 67 6f 6f 64 20 68 61 73 68 69 6e for good hashin
1f30: 67 20 70 72 6f 70 65 72 74 69 65 73 2c 20 62 75 g properties, bu
1f40: 74 20 61 6c 73 6f 0a 74 6f 20 65 6e 61 62 6c 65 t also.to enable
1f50: 20 74 68 65 20 65 61 73 79 20 28 69 6e 63 72 65 the easy (incre
1f60: 6d 65 6e 74 61 6c 29 20 72 65 63 61 6c 63 75 6c mental) recalcul
1f70: 61 74 69 6f 6e 20 6f 66 20 69 74 73 20 76 61 6c ation of its val
1f80: 75 65 20 66 6f 72 20 61 0a 73 6c 69 64 69 6e 67 ue for a.sliding
1f90: 20 77 69 6e 64 6f 77 2c 20 69 2e 65 2e 20 77 68 window, i.e. wh
1fa0: 65 72 65 20 74 68 65 20 6f 6c 64 65 73 74 20 62 ere the oldest b
1fb0: 79 74 65 20 69 73 20 72 65 6d 6f 76 65 64 20 66 yte is removed f
1fc0: 72 6f 6d 20 74 68 65 20 77 69 6e 64 6f 77 0a 61 rom the window.a
1fd0: 6e 64 20 61 20 6e 65 77 20 62 79 74 65 20 69 73 nd a new byte is
1fe0: 20 73 68 69 66 74 65 64 20 69 6e 2e 3c 70 3e 0a shifted in.<p>.
1ff0: 0a 3c 61 20 6e 61 6d 65 3d 22 72 68 64 65 66 22 .<a name="rhdef"
2000: 3e 3c 68 33 3e 34 2e 31 20 44 65 66 69 6e 69 74 ><h3>4.1 Definit
2010: 69 6f 6e 3c 2f 68 33 3e 0a 0a 3c 70 3e 41 73 73 ion</h3>..<p>Ass
2020: 75 6d 69 6e 67 20 61 6e 20 61 72 72 61 79 20 5a uming an array Z
2030: 20 6f 66 20 4e 48 41 53 48 20 62 79 74 65 73 20 of NHASH bytes
2040: 28 69 6e 64 65 78 69 6e 67 20 73 74 61 72 74 69 (indexing starti
2050: 6e 67 20 61 74 20 30 29 20 74 68 65 0a 68 61 73 ng at 0) the.has
2060: 68 20 56 20 69 73 20 63 6f 6d 70 75 74 65 64 20 h V is computed
2070: 76 69 61 3c 2f 70 3e 0a 0a 3c 70 20 61 6c 69 67 via</p>..<p alig
2080: 6e 3d 63 65 6e 74 65 72 3e 3c 74 61 62 6c 65 3e n=center><table>
2090: 3c 74 72 3e 3c 74 64 3e 0a 3c 70 3e 3c 69 6d 67 <tr><td>.<p><img
20a0: 20 73 72 63 3d 22 65 6e 63 6f 64 65 31 2e 67 69 src="encode1.gi
20b0: 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 f" align="center
20c0: 22 3e 3c 2f 70 3e 0a 3c 70 3e 3c 69 6d 67 20 73 "></p>.<p><img s
20d0: 72 63 3d 22 65 6e 63 6f 64 65 32 2e 67 69 66 22 rc="encode2.gif"
20e0: 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e align="center">
20f0: 3c 2f 70 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 </p>.<p><img src
2100: 3d 22 65 6e 63 6f 64 65 33 2e 67 69 66 22 20 61 ="encode3.gif" a
2110: 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f lign="center"></
2120: 70 3e 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 74 p>.</td></tr></t
2130: 61 62 6c 65 3e 3c 2f 70 3e 0a 0a 77 68 65 72 65 able></p>..where
2140: 20 41 20 61 6e 64 20 42 20 61 72 65 20 75 6e 73 A and B are uns
2150: 69 67 6e 65 64 20 31 36 2d 62 69 74 20 69 6e 74 igned 16-bit int
2160: 65 67 65 72 73 20 28 68 65 6e 63 65 20 74 68 65 egers (hence the
2170: 20 3c 75 3e 6d 6f 64 3c 2f 75 3e 29 2c 20 61 6e <u>mod</u>), an
2180: 64 0a 56 20 69 73 20 61 20 33 32 2d 62 69 74 20 d.V is a 32-bit
2190: 75 6e 73 69 67 6e 65 64 20 69 6e 74 65 67 65 72 unsigned integer
21a0: 20 77 69 74 68 20 42 20 61 73 20 4d 53 42 2c 20 with B as MSB,
21b0: 41 20 61 73 20 4c 53 42 2e 0a 0a 3c 61 20 6e 61 A as LSB...<a na
21c0: 6d 65 3d 22 72 68 69 6e 63 72 22 3e 3c 68 33 3e me="rhincr"><h3>
21d0: 34 2e 32 20 49 6e 63 72 65 6d 65 6e 74 61 6c 20 4.2 Incremental
21e0: 72 65 63 61 6c 63 75 6c 61 74 69 6f 6e 3c 2f 68 recalculation</h
21f0: 33 3e 0a 0a 3c 70 3e 41 73 73 75 6d 69 6e 67 20 3>..<p>Assuming
2200: 61 6e 20 61 72 72 61 79 20 5a 20 6f 66 20 4e 48 an array Z of NH
2210: 41 53 48 20 62 79 74 65 73 20 28 69 6e 64 65 78 ASH bytes (index
2220: 69 6e 67 20 73 74 61 72 74 69 6e 67 20 61 74 20 ing starting at
2230: 30 29 20 77 69 74 68 0a 68 61 73 68 20 56 20 28 0) with.hash V (
2240: 61 6e 64 20 63 6f 6d 70 6f 6e 65 6e 74 73 20 41 and components A
2250: 20 61 6e 64 20 42 29 2c 20 74 68 65 20 64 72 6f and B), the dro
2260: 70 70 65 64 0a 62 79 74 65 20 3c 69 6d 67 20 73 pped.byte <img s
2270: 72 63 3d 22 65 6e 63 6f 64 65 34 2e 67 69 66 22 rc="encode4.gif"
2280: 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e align="center">
2290: 2c 20 61 6e 64 20 74 68 65 20 6e 65 77 20 62 79 , and the new by
22a0: 74 65 0a 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 te.<img src="enc
22b0: 6f 64 65 35 2e 67 69 66 22 20 61 6c 69 67 6e 3d ode5.gif" align=
22c0: 22 63 65 6e 74 65 72 22 3e 20 2c 20 74 68 65 20 "center"> , the
22d0: 6e 65 77 20 68 61 73 68 20 63 61 6e 0a 62 65 20 new hash can.be
22e0: 63 6f 6d 70 75 74 65 64 20 69 6e 63 72 65 6d 65 computed increme
22f0: 6e 74 61 6c 6c 79 20 76 69 61 3a 20 3c 2f 70 3e ntally via: </p>
2300: 0a 0a 3c 70 20 61 6c 69 67 6e 3d 63 65 6e 74 65 ..<p align=cente
2310: 72 3e 3c 74 61 62 6c 65 3e 3c 74 72 3e 3c 74 64 r><table><tr><td
2320: 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 65 >.<p><img src="e
2330: 6e 63 6f 64 65 36 2e 67 69 66 22 20 61 6c 69 67 ncode6.gif" alig
2340: 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a n="center"></p>.
2350: 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 <p><img src="enc
2360: 6f 64 65 37 2e 67 69 66 22 20 61 6c 69 67 6e 3d ode7.gif" align=
2370: 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c 70 "center"></p>.<p
2380: 3e 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 ><img src="encod
2390: 65 38 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 e8.gif" align="c
23a0: 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c 2f 74 64 enter"></p>.</td
23b0: 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e 3c 2f ></tr></table></
23c0: 70 3e 0a 0a 3c 70 3e 46 6f 72 20 41 2c 20 74 68 p>..<p>For A, th
23d0: 65 20 72 65 67 75 6c 61 72 20 73 75 6d 2c 20 69 e regular sum, i
23e0: 74 20 63 61 6e 20 62 65 20 73 65 65 6e 20 65 61 t can be seen ea
23f0: 73 69 6c 79 20 74 68 61 74 20 74 68 69 73 20 74 sily that this t
2400: 68 65 20 63 6f 72 72 65 63 74 0a 77 61 79 20 72 he correct.way r
2410: 65 63 6f 6d 70 75 74 69 6e 67 20 74 68 61 74 20 ecomputing that
2420: 63 6f 6d 70 6f 6e 65 6e 74 2e 3c 2f 70 3e 0a 0a component.</p>..
2430: 3c 70 3e 46 6f 72 20 42 2c 20 74 68 65 20 77 65 <p>For B, the we
2440: 69 67 68 74 65 64 20 73 75 6d 2c 20 6e 6f 74 65 ighted sum, note
2450: 20 66 69 72 73 74 20 74 68 61 74 20 3c 69 6d 67 first that <img
2460: 20 73 72 63 3d 22 65 6e 63 6f 64 65 34 2e 67 69 src="encode4.gi
2470: 66 22 0a 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 f".align="center
2480: 22 3e 20 68 61 73 20 74 68 65 20 77 65 69 67 68 "> has the weigh
2490: 74 20 4e 48 41 53 48 20 69 6e 20 74 68 65 20 73 t NHASH in the s
24a0: 75 6d 2c 20 73 6f 20 74 68 61 74 20 69 73 20 77 um, so that is w
24b0: 68 61 74 20 68 61 73 0a 74 6f 20 62 65 20 72 65 hat has.to be re
24c0: 6d 6f 76 65 64 2e 20 54 68 65 6e 20 61 64 64 69 moved. Then addi
24d0: 6e 67 20 69 6e 20 3c 69 6d 67 20 73 72 63 3d 22 ng in <img src="
24e0: 65 6e 63 6f 64 65 39 2e 67 69 66 22 20 61 6c 69 encode9.gif" ali
24f0: 67 6e 3d 22 63 65 6e 74 65 72 22 3e 0a 61 64 64 gn="center">.add
2500: 73 20 6f 6e 65 20 77 65 69 67 68 74 20 66 61 63 s one weight fac
2510: 74 6f 72 20 74 6f 20 61 6c 6c 20 74 68 65 20 6f tor to all the o
2520: 74 68 65 72 20 76 61 6c 75 65 73 20 6f 66 20 5a ther values of Z
2530: 2c 20 61 6e 64 20 61 74 20 6c 61 73 74 20 61 64 , and at last ad
2540: 64 73 0a 69 6e 20 3c 69 6d 67 20 73 72 63 3d 22 ds.in <img src="
2550: 65 6e 63 6f 64 65 35 2e 67 69 66 22 20 61 6c 69 encode5.gif" ali
2560: 67 6e 3d 22 63 65 6e 74 65 72 22 3e 20 77 69 74 gn="center"> wit
2570: 68 20 77 65 69 67 68 74 20 31 2c 20 61 6c 73 6f h weight 1, also
2580: 0a 67 65 6e 65 72 61 74 69 6e 67 20 74 68 65 20 .generating the
2590: 63 6f 72 72 65 63 74 20 6e 65 77 20 73 75 6d 3c correct new sum<
25a0: 2f 70 3e 0a /p>.