0000: 3c 68 74 6d 6c 3e 0a 3c 68 65 61 64 3e 0a 3c 74 <html>.<head>.<t
0010: 69 74 6c 65 3e 46 6f 73 73 69 6c 20 44 65 6c 74 itle>Fossil Delt
0020: 61 20 45 6e 63 6f 64 69 6e 67 20 41 6c 67 6f 72 a Encoding Algor
0030: 69 74 68 6d 3c 2f 74 69 74 6c 65 3e 0a 3c 2f 68 ithm</title>.</h
0040: 65 61 64 3e 0a 3c 62 6f 64 79 20 62 67 63 6f 6c ead>.<body bgcol
0050: 6f 72 3d 22 77 68 69 74 65 22 3e 0a 3c 70 3e 5b or="white">.<p>[
0060: 20 3c 61 20 68 72 65 66 3d 22 69 6e 64 65 78 2e <a href="index.
0070: 68 74 6d 6c 22 3e 49 6e 64 65 78 3c 2f 61 3e 20 html">Index</a>
0080: 5d 3c 2f 70 3e 0a 3c 68 72 3e 0a 3c 68 31 20 61 ]</p>.<hr>.<h1 a
0090: 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 0a 46 lign="center">.F
00a0: 6f 73 73 69 6c 20 44 65 6c 74 61 20 45 6e 63 6f ossil Delta Enco
00b0: 64 69 6e 67 20 41 6c 67 6f 72 69 74 68 6d 0a 3c ding Algorithm.<
00c0: 2f 68 31 3e 0a 0a 3c 70 3e 41 20 6b 65 79 20 63 /h1>..<p>A key c
00d0: 6f 6d 70 6f 6e 65 6e 74 20 66 6f 72 20 74 68 65 omponent for the
00e0: 20 65 66 66 69 63 69 65 6e 74 20 73 74 6f 72 61 efficient stora
00f0: 67 65 20 6f 66 20 6d 75 6c 74 69 70 6c 65 20 72 ge of multiple r
0100: 65 76 69 73 69 6f 6e 73 20 6f 66 0a 61 20 66 69 evisions of.a fi
0110: 6c 65 20 69 6e 20 66 6f 73 73 69 6c 20 72 65 70 le in fossil rep
0120: 6f 73 69 74 6f 72 69 65 73 20 69 73 20 74 68 65 ositories is the
0130: 20 75 73 65 20 6f 66 20 64 65 6c 74 61 2d 63 6f use of delta-co
0140: 6d 70 72 65 73 73 69 6f 6e 2c 20 69 2e 65 2e 20 mpression, i.e.
0150: 74 6f 0a 73 74 6f 72 65 20 6f 6e 6c 79 20 74 68 to.store only th
0160: 65 20 63 68 61 6e 67 65 73 20 62 65 74 77 65 65 e changes betwee
0170: 6e 20 72 65 76 69 73 69 6f 6e 73 20 69 6e 73 74 n revisions inst
0180: 65 61 64 20 6f 66 20 74 68 65 20 77 68 6f 6c 65 ead of the whole
0190: 0a 66 69 6c 65 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 .file.</p>..<p>T
01a0: 68 69 73 20 64 6f 63 75 6d 65 6e 74 20 64 65 73 his document des
01b0: 63 72 69 62 65 73 20 74 68 65 20 65 6e 63 6f 64 cribes the encod
01c0: 69 6e 67 20 61 6c 67 6f 72 69 74 68 6d 20 75 73 ing algorithm us
01d0: 65 64 20 62 79 20 46 6f 73 73 69 6c 20 74 6f 0a ed by Fossil to.
01e0: 67 65 6e 65 72 61 74 65 20 64 65 6c 74 61 73 2e generate deltas.
01f0: 20 49 74 20 69 73 20 74 61 72 67 65 74 65 64 20 It is targeted
0200: 61 74 20 64 65 76 65 6c 6f 70 65 72 73 20 77 6f at developers wo
0210: 72 6b 69 6e 67 20 6f 6e 20 65 69 74 68 65 72 0a rking on either.
0220: 3c 61 20 68 72 65 66 3d 22 69 6e 64 65 78 2e 68 <a href="index.h
0230: 74 6d 6c 22 3e 66 6f 73 73 69 6c 3c 2f 61 3e 20 tml">fossil</a>
0240: 69 74 73 65 6c 66 2c 20 6f 72 20 6f 6e 20 74 6f itself, or on to
0250: 6f 6c 73 20 63 6f 6d 70 61 74 69 62 6c 65 20 77 ols compatible w
0260: 69 74 68 0a 69 74 2e 20 54 68 65 20 65 78 61 63 ith.it. The exac
0270: 74 20 66 6f 72 6d 61 74 20 6f 66 20 74 68 65 20 t format of the
0280: 67 65 6e 65 72 61 74 65 64 20 62 79 74 65 2d 73 generated byte-s
0290: 65 71 75 65 6e 63 65 73 2c 20 77 68 69 6c 65 20 equences, while
02a0: 69 6e 20 67 65 6e 65 72 61 6c 0a 6e 6f 74 20 6e in general.not n
02b0: 65 63 65 73 73 61 72 79 20 74 6f 20 75 6e 64 65 ecessary to unde
02c0: 72 73 74 61 6e 64 20 65 6e 63 6f 64 65 72 20 6f rstand encoder o
02d0: 70 65 72 61 74 69 6f 6e 2c 20 63 61 6e 20 62 65 peration, can be
02e0: 20 66 6f 75 6e 64 20 69 6e 20 74 68 65 0a 63 6f found in the.co
02f0: 6d 70 61 6e 69 6f 6e 20 73 70 65 63 69 66 69 63 mpanion specific
0300: 61 74 69 6f 6e 20 74 69 74 6c 65 64 20 22 3c 61 ation titled "<a
0310: 20 68 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 href="delta_for
0320: 6d 61 74 2e 68 74 6d 6c 22 3e 46 6f 73 73 69 6c mat.html">Fossil
0330: 0a 44 65 6c 74 61 20 46 6f 72 6d 61 74 3c 2f 61 .Delta Format</a
0340: 3e 22 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 65 >"..</p>..<p>The
0350: 20 65 6e 74 69 72 65 20 61 6c 67 6f 72 69 74 68 entire algorith
0360: 6d 20 69 73 20 69 6e 73 70 69 72 65 64 0a 62 79 m is inspired.by
0370: 20 3c 61 20 68 72 65 66 3d 22 68 74 74 70 3a 2f <a href="http:/
0380: 2f 73 61 6d 62 61 2e 61 6e 75 2e 65 64 75 2e 61 /samba.anu.edu.a
0390: 75 2f 72 73 79 6e 63 2f 22 3e 72 73 79 6e 63 3c u/rsync/">rsync<
03a0: 2f 61 3e 2e 3c 2f 70 3e 0a 0a 3c 61 20 6e 61 6d /a>.</p>..<a nam
03b0: 65 3d 22 61 72 67 72 65 73 70 61 72 61 6d 22 3e e="argresparam">
03c0: 3c 68 32 3e 31 2e 30 20 41 72 67 75 6d 65 6e 74 <h2>1.0 Argument
03d0: 73 2c 20 52 65 73 75 6c 74 73 2c 20 61 6e 64 20 s, Results, and
03e0: 50 61 72 61 6d 65 74 65 72 73 3c 2f 68 32 3e 0a Parameters</h2>.
03f0: 0a 3c 70 3e 54 68 65 20 65 6e 63 6f 64 65 72 20 .<p>The encoder
0400: 74 61 6b 65 73 20 74 77 6f 20 62 79 74 65 2d 73 takes two byte-s
0410: 65 71 75 65 6e 63 65 73 20 61 73 20 69 6e 70 75 equences as inpu
0420: 74 2c 20 74 68 65 20 22 6f 72 69 67 69 6e 61 6c t, the "original
0430: 22 2c 20 61 6e 64 0a 74 68 65 20 22 74 61 72 67 ", and.the "targ
0440: 65 74 22 2c 20 61 6e 64 20 72 65 74 75 72 6e 73 et", and returns
0450: 20 61 20 73 69 6e 67 6c 65 20 62 79 74 65 2d 73 a single byte-s
0460: 65 71 75 65 6e 63 65 20 63 6f 6e 74 61 69 6e 69 equence containi
0470: 6e 67 20 74 68 65 0a 22 64 65 6c 74 61 22 20 77 ng the."delta" w
0480: 68 69 63 68 20 74 72 61 6e 73 66 6f 72 6d 73 20 hich transforms
0490: 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 69 6e 74 the original int
04a0: 6f 20 74 68 65 20 74 61 72 67 65 74 20 75 70 6f o the target upo
04b0: 6e 20 69 74 73 0a 61 70 70 6c 69 63 61 74 69 6f n its.applicatio
04c0: 6e 2e 3c 2f 70 3e 0a 0a 3c 70 3e 4e 6f 74 65 20 n.</p>..<p>Note
04d0: 74 68 61 74 20 74 68 65 20 64 61 74 61 20 6f 66 that the data of
04e0: 20 61 20 22 62 79 74 65 2d 73 65 71 75 65 6e 63 a "byte-sequenc
04f0: 65 22 20 69 6e 63 6c 75 64 65 73 20 69 74 73 20 e" includes its
0500: 6c 65 6e 67 74 68 2c 0a 69 2e 65 2e 20 74 68 65 length,.i.e. the
0510: 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 number of bytes
0520: 20 63 6f 6e 74 61 69 6e 65 64 20 69 6e 20 74 68 contained in th
0530: 65 20 73 65 71 75 65 6e 63 65 2e 3c 2f 70 3e 0a e sequence.</p>.
0540: 0a 3c 70 3e 54 68 65 20 61 6c 67 6f 72 69 74 68 .<p>The algorith
0550: 6d 20 68 61 73 20 6f 6e 65 20 70 61 72 61 6d 65 m has one parame
0560: 74 65 72 20 6e 61 6d 65 64 20 22 4e 48 41 53 48 ter named "NHASH
0570: 22 2c 20 74 68 65 20 73 69 7a 65 20 6f 66 20 74 ", the size of t
0580: 68 65 0a 22 73 6c 69 64 69 6e 67 20 77 69 6e 64 he."sliding wind
0590: 6f 77 22 20 66 6f 72 20 74 68 65 20 22 72 6f 6c ow" for the "rol
05a0: 6c 69 6e 67 20 68 61 73 68 22 2c 20 69 6e 20 62 ling hash", in b
05b0: 79 74 65 73 2e 20 54 68 65 73 65 20 74 77 6f 20 ytes. These two
05c0: 74 65 72 6d 73 20 61 72 65 0a 65 78 70 6c 61 69 terms are.explai
05d0: 6e 65 64 20 69 6e 20 74 68 65 20 6e 65 78 74 20 ned in the next
05e0: 73 65 63 74 69 6f 6e 2e 20 54 68 65 20 76 61 6c section. The val
05f0: 75 65 20 6f 66 20 74 68 69 73 20 70 61 72 61 6d ue of this param
0600: 65 74 65 72 20 68 61 73 20 74 6f 20 62 65 20 61 eter has to be a
0610: 0a 70 6f 77 65 72 20 6f 66 20 74 77 6f 20 66 6f .power of two fo
0620: 72 20 74 68 65 20 61 6c 67 6f 72 69 74 68 6d 20 r the algorithm
0630: 74 6f 20 77 6f 72 6b 2e 20 46 6f 72 20 46 6f 73 to work. For Fos
0640: 73 69 6c 20 74 68 65 20 76 61 6c 75 65 20 6f 66 sil the value of
0650: 20 74 68 69 73 0a 70 61 72 61 6d 65 74 65 72 20 this.parameter
0660: 69 73 20 73 65 74 20 74 6f 20 22 31 36 22 2e 3c is set to "16".<
0670: 2f 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 6f 70 /p>..<a name="op
0680: 65 72 61 74 69 6f 6e 22 3e 3c 68 32 3e 32 2e 30 eration"><h2>2.0
0690: 20 4f 70 65 72 61 74 69 6f 6e 3c 2f 68 32 3e 0a Operation</h2>.
06a0: 0a 3c 70 3e 54 68 65 20 61 6c 67 6f 72 69 74 68 .<p>The algorith
06b0: 6d 20 69 73 20 73 70 6c 69 74 20 69 6e 74 6f 20 m is split into
06c0: 74 68 72 65 65 20 70 68 61 73 65 73 20 77 68 69 three phases whi
06d0: 63 68 20 67 65 6e 65 72 61 74 65 0a 74 68 65 20 ch generate.the
06e0: 3c 61 20 68 72 65 66 3d 22 64 65 6c 74 61 5f 66 <a href="delta_f
06f0: 6f 72 6d 61 74 2e 68 74 6d 6c 23 68 65 61 64 65 ormat.html#heade
0700: 72 22 3e 68 65 61 64 65 72 3c 2f 61 3e 2c 0a 3c r">header</a>,.<
0710: 61 20 68 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f a href="delta_fo
0720: 72 6d 61 74 2e 68 74 6d 6c 23 73 6c 69 73 74 22 rmat.html#slist"
0730: 3e 73 65 67 6d 65 6e 74 20 6c 69 73 74 3c 2f 61 >segment list</a
0740: 3e 2c 0a 61 6e 64 20 3c 61 20 68 72 65 66 3d 22 >,.and <a href="
0750: 64 65 6c 74 61 5f 66 6f 72 6d 61 74 2e 68 74 6d delta_format.htm
0760: 6c 23 74 72 61 69 6c 65 72 22 3e 74 72 61 69 6c l#trailer">trail
0770: 65 72 3c 2f 61 3e 20 6f 66 20 74 68 65 20 64 65 er</a> of the de
0780: 6c 74 61 2c 20 70 65 72 0a 69 74 73 20 67 65 6e lta, per.its gen
0790: 65 72 61 6c 20 3c 61 20 68 72 65 66 3d 22 64 65 eral <a href="de
07a0: 6c 74 61 5f 66 6f 72 6d 61 74 2e 68 74 6d 6c 23 lta_format.html#
07b0: 73 74 72 75 63 74 75 72 65 22 3e 73 74 72 75 63 structure">struc
07c0: 74 75 72 65 3c 2f 61 3e 2e 3c 2f 70 3e 0a 0a 3c ture</a>.</p>..<
07d0: 70 3e 54 68 65 20 74 77 6f 20 70 68 61 73 65 73 p>The two phases
07e0: 20 67 65 6e 65 72 61 74 69 6e 67 20 68 65 61 64 generating head
07f0: 65 72 20 61 6e 64 20 74 72 61 69 6c 65 72 20 61 er and trailer a
0800: 72 65 20 6e 6f 74 20 63 6f 76 65 72 65 64 20 68 re not covered h
0810: 65 72 65 0a 61 73 20 74 68 65 69 72 20 69 6d 70 ere.as their imp
0820: 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 74 72 69 76 lementation triv
0830: 69 61 6c 6c 79 20 66 6f 6c 6c 6f 77 73 20 64 69 ially follows di
0840: 72 65 63 74 6c 79 20 66 72 6f 6d 20 74 68 65 0a rectly from the.
0850: 73 70 65 63 69 66 69 63 61 74 69 6f 6e 20 6f 66 specification of
0860: 20 74 68 65 20 3c 61 20 68 72 65 66 3d 22 64 65 the <a href="de
0870: 6c 74 61 5f 66 6f 72 6d 61 74 2e 68 74 6d 6c 22 lta_format.html"
0880: 3e 64 65 6c 74 61 20 66 6f 72 6d 61 74 3c 2f 61 >delta format</a
0890: 3e 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 69 73 20 >.</p>..<p>This
08a0: 6c 65 61 76 65 73 20 74 68 65 20 73 65 67 6d 65 leaves the segme
08b0: 6e 74 2d 6c 69 73 74 2e 20 49 74 73 20 67 65 6e nt-list. Its gen
08c0: 65 72 61 74 69 6f 6e 20 69 73 20 64 6f 6e 65 20 eration is done
08d0: 69 6e 20 74 77 6f 20 70 68 61 73 65 73 2c 0a 61 in two phases,.a
08e0: 20 70 72 65 2d 70 72 6f 63 65 73 73 69 6e 67 20 pre-processing
08f0: 73 74 65 70 20 6f 70 65 72 61 74 69 6e 67 20 6f step operating o
0900: 6e 20 74 68 65 20 22 6f 72 69 67 69 6e 61 6c 22 n the "original"
0910: 20 62 79 74 65 2d 73 65 71 75 65 6e 63 65 2c 0a byte-sequence,.
0920: 66 6f 6c 6c 6f 77 65 64 20 62 79 20 74 68 65 20 followed by the
0930: 70 72 6f 63 65 73 73 69 6e 67 20 6f 66 20 74 68 processing of th
0940: 65 20 22 74 61 72 67 65 74 22 20 62 79 74 65 2d e "target" byte-
0950: 73 65 71 75 65 6e 63 65 20 75 73 69 6e 67 20 74 sequence using t
0960: 68 65 0a 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 67 he.information g
0970: 61 74 68 65 72 65 64 20 62 79 20 74 68 65 20 66 athered by the f
0980: 69 72 73 74 20 73 74 65 70 2e 3c 2f 70 3e 0a 0a irst step.</p>..
0990: 3c 61 20 6e 61 6d 65 3d 22 70 72 65 70 72 6f 63 <a name="preproc
09a0: 65 73 73 69 6e 67 22 3e 3c 68 33 3e 32 2e 31 20 essing"><h3>2.1
09b0: 50 72 65 70 72 6f 63 65 73 73 69 6e 67 20 74 68 Preprocessing th
09c0: 65 20 6f 72 69 67 69 6e 61 6c 3c 2f 68 33 3e 0a e original</h3>.
09d0: 0a 3c 70 3e 41 20 6d 61 6a 6f 72 20 70 61 72 74 .<p>A major part
09e0: 20 6f 66 20 74 68 65 20 70 72 6f 63 65 73 73 69 of the processi
09f0: 6e 67 20 6f 66 20 74 68 65 20 22 74 61 72 67 65 ng of the "targe
0a00: 74 22 20 69 73 20 74 6f 20 66 69 6e 64 20 61 20 t" is to find a
0a10: 72 61 6e 67 65 0a 69 6e 20 74 68 65 20 22 6f 72 range.in the "or
0a20: 69 67 69 6e 61 6c 22 20 77 68 69 63 68 20 63 6f iginal" which co
0a30: 6e 74 61 69 6e 73 20 74 68 65 20 73 61 6d 65 20 ntains the same
0a40: 63 6f 6e 74 65 6e 74 20 61 73 20 66 6f 75 6e 64 content as found
0a50: 20 61 74 20 74 68 65 0a 63 75 72 72 65 6e 74 20 at the.current
0a60: 6c 6f 63 61 74 69 6f 6e 20 69 6e 20 74 68 65 20 location in the
0a70: 22 74 61 72 67 65 74 22 2e 3c 2f 70 3e 0a 0a 3c "target".</p>..<
0a80: 70 3e 41 20 6e 61 69 76 65 20 61 70 70 72 6f 61 p>A naive approa
0a90: 63 68 20 74 6f 20 74 68 69 73 20 77 6f 75 6c 64 ch to this would
0aa0: 20 62 65 20 74 6f 20 73 65 61 72 63 68 20 74 68 be to search th
0ab0: 65 20 77 68 6f 6c 65 20 22 6f 72 69 67 69 6e 61 e whole "origina
0ac0: 6c 22 0a 66 6f 72 20 73 75 63 68 20 63 6f 6e 74 l".for such cont
0ad0: 65 6e 74 2e 20 54 68 69 73 20 68 6f 77 65 76 65 ent. This howeve
0ae0: 72 20 69 73 20 76 65 72 79 20 69 6e 65 66 66 69 r is very ineffi
0af0: 63 69 65 6e 74 20 61 73 20 69 74 20 77 6f 75 6c cient as it woul
0b00: 64 20 73 65 61 72 63 68 0a 74 68 65 20 73 61 6d d search.the sam
0b10: 65 20 70 61 72 74 73 20 6f 66 20 74 68 65 20 22 e parts of the "
0b20: 6f 72 69 67 69 6e 61 6c 22 20 6f 76 65 72 20 61 original" over a
0b30: 6e 64 20 6f 76 65 72 2e 20 57 68 61 74 20 69 73 nd over. What is
0b40: 20 64 6f 6e 65 20 69 6e 73 74 65 61 64 0a 69 73 done instead.is
0b50: 20 74 6f 20 73 61 6d 70 6c 65 20 74 68 65 20 22 to sample the "
0b60: 6f 72 69 67 69 6e 61 6c 22 20 61 74 20 72 65 67 original" at reg
0b70: 75 6c 61 72 20 69 6e 74 65 72 76 61 6c 73 2c 20 ular intervals,
0b80: 63 6f 6d 70 75 74 65 20 73 69 67 6e 61 74 75 72 compute signatur
0b90: 65 73 0a 66 6f 72 20 74 68 65 20 73 61 6d 70 6c es.for the sampl
0ba0: 65 64 20 6c 6f 63 61 74 69 6f 6e 73 20 61 6e 64 ed locations and
0bb0: 20 73 74 6f 72 65 20 74 68 65 6d 20 69 6e 20 61 store them in a
0bc0: 20 68 61 73 68 20 74 61 62 6c 65 20 6b 65 79 65 hash table keye
0bd0: 64 20 62 79 0a 74 68 65 73 65 20 73 69 67 6e 61 d by.these signa
0be0: 74 75 72 65 73 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 tures.</p>..<p>T
0bf0: 68 61 74 20 69 73 20 77 68 61 74 20 68 61 70 70 hat is what happ
0c00: 65 6e 73 20 69 6e 20 74 68 69 73 20 73 74 65 70 ens in this step
0c10: 2e 20 54 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 . The following
0c20: 70 72 6f 63 65 73 73 69 6e 67 20 73 74 65 70 0a processing step.
0c30: 63 61 6e 20 74 68 65 6e 20 74 68 65 20 63 6f 6d can then the com
0c40: 70 75 74 65 20 73 69 67 6e 61 74 75 72 65 20 66 pute signature f
0c50: 6f 72 20 69 74 73 20 63 75 72 72 65 6e 74 20 6c or its current l
0c60: 6f 63 61 74 69 6f 6e 20 61 6e 64 20 74 68 65 6e ocation and then
0c70: 20 68 61 73 0a 74 6f 20 73 65 61 72 63 68 20 6f has.to search o
0c80: 6e 6c 79 20 61 20 6e 61 72 72 6f 77 20 73 65 74 nly a narrow set
0c90: 20 6f 66 20 6c 6f 63 61 74 69 6f 6e 73 20 69 6e of locations in
0ca0: 20 74 68 65 20 22 6f 72 69 67 69 6e 61 6c 22 20 the "original"
0cb0: 66 6f 72 0a 70 6f 73 73 69 62 6c 65 20 6d 61 74 for.possible mat
0cc0: 63 68 65 73 2c 20 6e 61 6d 65 6c 79 20 74 68 6f ches, namely tho
0cd0: 73 65 20 77 68 69 63 68 20 68 61 76 65 20 74 68 se which have th
0ce0: 65 20 73 61 6d 65 20 73 69 67 6e 61 74 75 72 65 e same signature
0cf0: 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 6e 20 64 65 74 .</p>..<p>In det
0d00: 61 69 6c 3a 3c 2f 70 3e 0a 0a 3c 6f 6c 3e 0a 3c ail:</p>..<ol>.<
0d10: 6c 69 3e 54 68 65 20 22 6f 72 69 67 69 6e 61 6c li>The "original
0d20: 22 20 69 73 20 73 70 6c 69 74 20 69 6e 74 6f 20 " is split into
0d30: 63 68 75 6e 6b 73 20 6f 66 20 4e 48 41 53 48 20 chunks of NHASH
0d40: 62 79 74 65 73 2e 20 4e 6f 74 65 20 74 68 61 74 bytes. Note that
0d50: 20 61 0a 70 61 72 74 69 61 6c 20 63 68 75 6e 6b a.partial chunk
0d60: 20 6f 66 20 6c 65 73 73 20 74 68 61 6e 20 4e 48 of less than NH
0d70: 41 53 48 20 62 79 74 65 73 20 61 74 20 74 68 65 ASH bytes at the
0d80: 20 65 6e 64 20 6f 66 20 22 6f 72 69 67 69 6e 61 end of "origina
0d90: 6c 22 20 69 73 0a 69 67 6e 6f 72 65 64 2e 0a 3c l" is.ignored..<
0da0: 2f 6c 69 3e 0a 3c 6c 69 3e 54 68 65 20 3c 61 20 /li>.<li>The <a
0db0: 68 72 65 66 3d 22 23 72 6f 6c 6c 68 61 73 68 22 href="#rollhash"
0dc0: 3e 72 6f 6c 6c 69 6e 67 20 68 61 73 68 3c 2f 61 >rolling hash</a
0dd0: 3e 20 6f 66 20 65 61 63 68 20 63 68 75 6e 6b 20 > of each chunk
0de0: 69 73 0a 63 6f 6d 70 75 74 65 64 2e 0a 3c 2f 6c is.computed..</l
0df0: 69 3e 0a 3c 6c 69 3e 41 20 68 61 73 68 74 61 62 i>.<li>A hashtab
0e00: 6c 65 20 69 73 20 66 69 6c 6c 65 64 2c 20 6d 61 le is filled, ma
0e10: 70 70 69 6e 67 20 66 72 6f 6d 20 74 68 65 20 68 pping from the h
0e20: 61 73 68 65 73 20 6f 66 20 74 68 65 20 63 68 75 ashes of the chu
0e30: 6e 6b 73 20 74 6f 0a 74 68 65 20 6c 69 73 74 20 nks to.the list
0e40: 6f 66 20 63 68 75 6e 6b 20 6c 6f 63 61 74 69 6f of chunk locatio
0e50: 6e 73 20 68 61 76 69 6e 67 20 74 68 69 73 20 68 ns having this h
0e60: 61 73 68 2e 0a 3c 2f 6c 69 3e 0a 3c 2f 6f 6c 3e ash..</li>.</ol>
0e70: 0a 0a 3c 61 20 6e 61 6d 65 3d 22 70 72 6f 63 65 ..<a name="proce
0e80: 73 73 69 6e 67 22 3e 3c 68 33 3e 32 2e 31 20 50 ssing"><h3>2.1 P
0e90: 72 6f 63 65 73 73 69 6e 67 20 74 68 65 20 74 61 rocessing the ta
0ea0: 72 67 65 74 3c 2f 68 33 3e 0a 0a 3c 70 3e 54 68 rget</h3>..<p>Th
0eb0: 69 73 2c 20 74 68 65 20 6d 61 69 6e 20 70 68 61 is, the main pha
0ec0: 73 65 20 6f 66 20 74 68 65 20 65 6e 63 6f 64 65 se of the encode
0ed0: 72 2c 20 70 72 6f 63 65 73 73 65 73 20 74 68 65 r, processes the
0ee0: 20 74 61 72 67 65 74 20 69 6e 20 61 20 6c 6f 6f target in a loo
0ef0: 70 0a 66 72 6f 6d 20 62 65 67 69 6e 6e 69 6e 67 p.from beginning
0f00: 20 74 6f 20 65 6e 64 2e 20 54 68 65 20 73 74 61 to end. The sta
0f10: 74 65 20 6f 66 20 74 68 65 20 65 6e 63 6f 64 65 te of the encode
0f20: 72 20 69 73 20 63 61 70 74 75 72 65 64 20 62 79 r is captured by
0f30: 20 74 77 6f 0a 6c 6f 63 61 74 69 6f 6e 73 2c 20 two.locations,
0f40: 74 68 65 20 22 62 61 73 65 22 20 61 6e 64 20 74 the "base" and t
0f50: 68 65 20 22 73 6c 69 64 65 22 2e 20 22 62 61 73 he "slide". "bas
0f60: 65 22 20 70 6f 69 6e 74 73 20 74 6f 20 74 68 65 e" points to the
0f70: 20 66 69 72 73 74 20 62 79 74 65 0a 6f 66 20 74 first byte.of t
0f80: 68 65 20 74 61 72 67 65 74 20 66 6f 72 20 77 68 he target for wh
0f90: 69 63 68 20 6e 6f 20 64 65 6c 74 61 20 6f 75 74 ich no delta out
0fa0: 70 75 74 20 68 61 73 20 62 65 65 6e 20 67 65 6e put has been gen
0fb0: 65 72 61 74 65 64 20 79 65 74 2c 20 61 6e 64 0a erated yet, and.
0fc0: 22 73 6c 69 64 65 22 20 69 73 20 74 68 65 20 6c "slide" is the l
0fd0: 6f 63 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 77 ocation of the w
0fe0: 69 6e 64 6f 77 20 75 73 65 64 20 74 6f 20 6c 6f indow used to lo
0ff0: 6f 6b 20 69 6e 20 74 68 65 20 22 6f 72 69 67 69 ok in the "origi
1000: 6e 22 20 66 6f 72 0a 63 6f 6d 6d 6f 6e 61 6c 69 n" for.commonali
1010: 74 69 65 73 2e 20 54 68 69 73 20 77 69 6e 64 6f ties. This windo
1020: 77 20 69 73 20 4e 48 41 53 48 20 62 79 74 65 73 w is NHASH bytes
1030: 20 6c 6f 6e 67 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 long.</p>..<p>I
1040: 6e 69 74 69 61 6c 6c 79 20 62 6f 74 68 20 22 62 nitially both "b
1050: 61 73 65 22 20 61 6e 64 20 22 73 6c 69 64 65 22 ase" and "slide"
1060: 20 70 6f 69 6e 74 20 74 6f 20 74 68 65 20 62 65 point to the be
1070: 67 69 6e 6e 69 6e 67 20 6f 66 20 74 68 65 0a 22 ginning of the."
1080: 74 61 72 67 65 74 22 2e 20 49 6e 20 65 61 63 68 target". In each
1090: 20 69 74 65 72 61 74 69 6f 6e 20 6f 66 20 74 68 iteration of th
10a0: 65 20 6c 6f 6f 70 20 74 68 65 20 65 6e 63 6f 64 e loop the encod
10b0: 65 72 20 64 65 63 69 64 65 73 20 77 68 65 74 68 er decides wheth
10c0: 65 72 20 74 6f 0a 3c 75 6c 3e 0a 3c 6c 69 3e 65 er to.<ul>.<li>e
10d0: 6d 69 74 20 61 20 73 69 6e 67 6c 65 20 69 6e 73 mit a single ins
10e0: 74 72 75 63 74 69 6f 6e 0a 74 6f 20 3c 61 20 68 truction.to <a h
10f0: 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 ref="delta_forma
1100: 74 2e 68 74 6d 6c 23 63 6f 70 79 72 61 6e 67 65 t.html#copyrange
1110: 22 3e 63 6f 70 79 20 61 20 72 61 6e 67 65 3c 2f ">copy a range</
1120: 61 3e 2c 20 6f 72 0a 3c 2f 6c 69 3e 0a 3c 6c 69 a>, or.</li>.<li
1130: 3e 65 6d 69 74 20 74 77 6f 20 69 6e 73 74 72 75 >emit two instru
1140: 63 74 69 6f 6e 73 2c 20 66 69 72 73 74 0a 74 6f ctions, first.to
1150: 20 3c 61 20 68 72 65 66 3d 22 64 65 6c 74 61 5f <a href="delta_
1160: 66 6f 72 6d 61 74 2e 68 74 6d 6c 23 69 6e 73 65 format.html#inse
1170: 72 74 6c 69 74 22 3e 69 6e 73 65 72 74 20 61 20 rtlit">insert a
1180: 6c 69 74 65 72 61 6c 3c 2f 61 3e 2c 20 74 68 65 literal</a>, the
1190: 6e 0a 74 6f 20 3c 61 20 68 72 65 66 3d 22 64 65 n.to <a href="de
11a0: 6c 74 61 5f 66 6f 72 6d 61 74 2e 68 74 6d 6c 23 lta_format.html#
11b0: 63 6f 70 79 72 61 6e 67 65 22 3e 63 6f 70 79 20 copyrange">copy
11c0: 61 20 72 61 6e 67 65 3c 2f 61 3e 2c 20 6f 72 0a a range</a>, or.
11d0: 3c 2f 6c 69 3e 0a 3c 6c 69 3e 6d 6f 76 65 20 74 </li>.<li>move t
11e0: 68 65 20 77 69 6e 64 6f 77 20 66 6f 72 77 61 72 he window forwar
11f0: 64 20 6f 6e 65 20 62 79 74 65 2e 0a 3c 2f 6c 69 d one byte..</li
1200: 3e 0a 3c 2f 75 6c 3e 0a 3c 2f 70 3e 0a 0a 3c 69 >.</ul>.</p>..<i
1210: 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 31 30 mg src="encode10
1220: 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 72 69 67 .gif" align="rig
1230: 68 74 22 20 68 73 70 61 63 65 3d 22 31 30 22 3e ht" hspace="10">
1240: 0a 3c 70 3e 54 6f 20 6d 61 6b 65 20 74 68 69 73 .<p>To make this
1250: 20 64 65 63 69 73 69 6f 6e 20 74 68 65 20 65 6e decision the en
1260: 63 6f 64 65 72 20 66 69 72 73 74 20 63 6f 6d 70 coder first comp
1270: 75 74 65 73 20 74 68 65 20 68 61 73 68 20 76 61 utes the hash va
1280: 6c 75 65 20 66 6f 72 0a 74 68 65 20 4e 48 41 53 lue for.the NHAS
1290: 48 20 62 79 74 65 73 20 69 6e 20 74 68 65 20 77 H bytes in the w
12a0: 69 6e 64 6f 77 20 61 6e 64 20 74 68 65 6e 20 6c indow and then l
12b0: 6f 6f 6b 73 20 61 74 20 61 6c 6c 20 74 68 65 20 ooks at all the
12c0: 6c 6f 63 61 74 69 6f 6e 73 20 69 6e 0a 74 68 65 locations in.the
12d0: 20 22 6f 72 69 67 69 6e 22 20 77 68 69 63 68 20 "origin" which
12e0: 68 61 76 65 20 74 68 65 20 73 61 6d 65 20 73 69 have the same si
12f0: 67 6e 61 74 75 72 65 2e 20 54 68 69 73 20 70 61 gnature. This pa
1300: 72 74 20 75 73 65 73 20 74 68 65 20 68 61 73 68 rt uses the hash
1310: 0a 74 61 62 6c 65 20 63 72 65 61 74 65 64 20 62 .table created b
1320: 79 20 74 68 65 20 70 72 65 2d 70 72 6f 63 65 73 y the pre-proces
1330: 73 69 6e 67 20 73 74 65 70 20 74 6f 20 65 66 66 sing step to eff
1340: 69 65 6e 74 6c 79 20 66 69 6e 64 20 74 68 65 73 iently find thes
1350: 65 0a 6c 6f 63 61 74 69 6f 6e 73 2e 3c 2f 70 3e e.locations.</p>
1360: 0a 0a 3c 70 3e 46 6f 72 20 65 61 63 68 20 6f 66 ..<p>For each of
1370: 20 74 68 65 20 70 6f 73 73 69 62 6c 65 20 63 61 the possible ca
1380: 6e 64 69 64 61 74 65 73 20 74 68 65 20 65 6e 63 ndidates the enc
1390: 6f 64 65 72 20 66 69 6e 64 73 20 74 68 65 20 6d oder finds the m
13a0: 61 78 69 6d 61 6c 0a 72 61 6e 67 65 20 6f 66 20 aximal.range of
13b0: 62 79 74 65 73 20 63 6f 6d 6d 6f 6e 20 74 6f 20 bytes common to
13c0: 62 6f 74 68 20 22 6f 72 69 67 69 6e 22 20 61 6e both "origin" an
13d0: 64 20 22 74 61 72 67 65 74 22 2c 20 67 6f 69 6e d "target", goin
13e0: 67 20 66 6f 72 77 61 72 64 20 61 6e 64 0a 62 61 g forward and.ba
13f0: 63 6b 77 61 72 64 20 66 72 6f 6d 20 22 73 6c 69 ckward from "sli
1400: 64 65 22 20 69 6e 20 74 68 65 20 22 74 61 72 67 de" in the "targ
1410: 65 74 22 2c 20 61 6e 64 20 74 68 65 20 63 61 6e et", and the can
1420: 64 69 64 61 74 65 20 6c 6f 63 61 74 69 6f 6e 20 didate location
1430: 69 6e 0a 74 68 65 20 22 6f 72 69 67 69 6e 22 2e in.the "origin".
1440: 20 54 68 69 73 20 73 65 61 72 63 68 20 69 73 20 This search is
1450: 63 6f 6e 73 74 72 61 69 6e 65 64 20 6f 6e 20 74 constrained on t
1460: 68 65 20 73 69 64 65 20 6f 66 20 74 68 65 20 22 he side of the "
1470: 74 61 72 67 65 74 22 0a 62 79 20 74 68 65 20 22 target".by the "
1480: 62 61 73 65 22 20 28 62 61 63 6b 77 61 72 64 20 base" (backward
1490: 73 65 61 72 63 68 29 2c 20 61 6e 64 20 74 68 65 search), and the
14a0: 20 65 6e 64 20 6f 66 20 74 68 65 20 22 74 61 72 end of the "tar
14b0: 67 65 74 22 20 28 66 6f 72 77 61 72 64 0a 73 65 get" (forward.se
14c0: 61 72 63 68 29 2c 20 61 6e 64 20 6f 6e 20 74 68 arch), and on th
14d0: 65 20 73 69 64 65 20 6f 66 20 74 68 65 20 22 6f e side of the "o
14e0: 72 69 67 69 6e 22 20 62 79 20 74 68 65 20 62 65 rigin" by the be
14f0: 67 69 6e 6e 69 6e 67 20 61 6e 64 20 65 6e 64 20 ginning and end
1500: 6f 66 0a 74 68 65 20 22 6f 72 69 67 69 6e 22 2c of.the "origin",
1510: 20 72 65 73 70 65 63 74 69 76 65 6c 79 2e 3c 2f respectively.</
1520: 70 3e 0a 0a 3c 70 3e 54 68 65 72 65 20 61 72 65 p>..<p>There are
1530: 20 69 6e 70 75 74 20 66 69 6c 65 73 20 66 6f 72 input files for
1540: 20 77 68 69 63 68 20 74 68 65 20 68 61 73 68 20 which the hash
1550: 63 68 61 69 6e 73 20 67 65 6e 65 72 61 74 65 64 chains generated
1560: 20 62 79 20 74 68 65 0a 70 72 65 2d 70 72 6f 63 by the.pre-proc
1570: 65 73 73 69 6e 67 20 73 74 65 70 20 63 61 6e 20 essing step can
1580: 62 65 63 6f 6d 65 20 76 65 72 79 20 6c 6f 6e 67 become very long
1590: 2c 20 6c 65 61 64 69 6e 67 20 74 6f 20 6c 6f 6e , leading to lon
15a0: 67 20 73 65 61 72 63 68 20 74 69 6d 65 73 0a 61 g search times.a
15b0: 6e 64 20 61 66 66 65 63 74 69 6e 67 20 74 68 65 nd affecting the
15c0: 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 6f 66 20 performance of
15d0: 74 68 65 20 64 65 6c 74 61 20 67 65 6e 65 72 61 the delta genera
15e0: 74 6f 72 2e 20 54 6f 20 6c 69 6d 69 74 20 74 68 tor. To limit th
15f0: 65 0a 65 66 66 65 63 74 20 73 75 63 68 20 6c 6f e.effect such lo
1600: 6e 67 20 63 68 61 69 6e 73 20 63 61 6e 20 68 61 ng chains can ha
1610: 76 65 20 74 68 65 20 61 63 74 75 61 6c 20 73 65 ve the actual se
1620: 61 72 63 68 20 66 6f 72 20 63 61 6e 64 69 64 61 arch for candida
1630: 74 65 73 20 69 73 0a 62 6f 75 6e 64 65 64 2c 20 tes is.bounded,
1640: 6c 6f 6f 6b 69 6e 67 20 61 74 20 6d 6f 73 74 20 looking at most
1650: 4e 20 63 61 6e 64 69 64 61 74 65 73 2e 20 43 75 N candidates. Cu
1660: 72 72 65 6e 74 6c 79 20 4e 20 69 73 20 73 65 74 rrently N is set
1670: 20 74 6f 20 32 35 30 2e 3c 2f 70 3e 0a 0a 3c 70 to 250.</p>..<p
1680: 3e 46 72 6f 6d 20 74 68 65 20 72 61 6e 67 65 73 >From the ranges
1690: 20 66 6f 72 20 61 6c 6c 20 74 68 65 20 63 61 6e for all the can
16a0: 64 69 64 61 74 65 73 20 74 68 65 20 62 65 73 74 didates the best
16b0: 20 28 3d 20 6c 61 72 67 65 73 74 29 20 63 6f 6d (= largest) com
16c0: 6d 6f 6e 0a 72 61 6e 67 65 20 69 73 20 74 61 6b mon.range is tak
16d0: 65 6e 20 61 6e 64 20 69 74 20 69 73 20 64 65 74 en and it is det
16e0: 65 72 6d 69 6e 65 64 20 68 6f 77 20 6d 61 6e 79 ermined how many
16f0: 20 62 79 74 65 73 20 61 72 65 20 6e 65 65 64 65 bytes are neede
1700: 64 20 74 6f 0a 65 6e 63 6f 64 65 20 74 68 65 20 d to.encode the
1710: 62 79 74 65 73 20 62 65 74 77 65 65 6e 20 74 68 bytes between th
1720: 65 20 22 62 61 73 65 22 20 61 6e 64 20 74 68 65 e "base" and the
1730: 20 65 6e 64 20 6f 66 20 74 68 61 74 20 72 61 6e end of that ran
1740: 67 65 2e 20 49 66 20 74 68 65 0a 72 61 6e 67 65 ge. If the.range
1750: 20 65 78 74 65 6e 64 65 64 20 62 61 63 6b 20 74 extended back t
1760: 6f 20 74 68 65 20 22 62 61 73 65 22 20 74 68 65 o the "base" the
1770: 6e 20 74 68 69 73 20 63 61 6e 20 62 65 20 64 6f n this can be do
1780: 6e 65 20 69 6e 20 61 20 73 69 6e 67 6c 65 0a 63 ne in a single.c
1790: 6f 70 79 20 69 6e 73 74 72 75 63 74 69 6f 6e 2e opy instruction.
17a0: 20 4f 74 68 65 72 77 69 73 65 2c 20 69 2e 65 20 Otherwise, i.e
17b0: 69 66 20 74 68 65 72 65 20 69 73 20 61 20 67 61 if there is a ga
17c0: 70 20 62 65 74 77 65 65 6e 20 74 68 65 20 22 62 p between the "b
17d0: 61 73 65 22 0a 61 6e 64 20 74 68 65 20 62 65 67 ase".and the beg
17e0: 69 6e 6e 69 6e 67 20 6f 66 20 74 68 65 20 72 61 inning of the ra
17f0: 6e 67 65 20 74 68 65 6e 20 74 77 6f 20 69 6e 73 nge then two ins
1800: 74 72 75 63 74 69 6f 6e 73 20 61 72 65 20 6e 65 tructions are ne
1810: 65 64 65 64 2c 20 6f 6e 65 0a 74 6f 20 69 6e 73 eded, one.to ins
1820: 65 72 74 20 74 68 65 20 62 79 74 65 73 20 69 6e ert the bytes in
1830: 20 74 68 65 20 67 61 70 20 61 73 20 61 20 6c 69 the gap as a li
1840: 74 65 72 61 6c 2c 20 61 6e 64 20 61 20 63 6f 70 teral, and a cop
1850: 79 20 69 6e 73 74 72 75 63 74 69 6f 6e 0a 66 6f y instruction.fo
1860: 72 20 74 68 65 20 72 61 6e 67 65 20 69 74 73 65 r the range itse
1870: 6c 66 2e 20 54 68 65 20 67 65 6e 65 72 61 6c 20 lf. The general
1880: 73 69 74 75 61 74 69 6f 6e 20 61 74 20 74 68 69 situation at thi
1890: 73 20 70 6f 69 6e 74 20 63 61 6e 20 62 65 20 73 s point can be s
18a0: 65 65 6e 0a 69 6e 20 74 68 65 20 70 69 63 74 75 een.in the pictu
18b0: 72 65 20 74 6f 20 74 68 65 20 72 69 67 68 74 2e re to the right.
18c0: 3c 2f 70 3e 0a 0a 3c 70 3e 49 66 20 74 68 65 20 </p>..<p>If the
18d0: 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 number of bytes
18e0: 6e 65 65 64 65 64 20 74 6f 20 65 6e 63 6f 64 65 needed to encode
18f0: 20 62 6f 74 68 20 67 61 70 20 28 69 66 20 70 72 both gap (if pr
1900: 65 73 65 6e 74 29 2c 20 61 6e 64 0a 72 61 6e 67 esent), and.rang
1910: 65 20 69 73 20 6c 65 73 73 20 74 68 61 6e 20 74 e is less than t
1920: 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 he number of byt
1930: 65 73 20 77 65 20 61 72 65 20 65 6e 63 6f 64 69 es we are encodi
1940: 6e 67 20 74 68 65 20 65 6e 63 6f 64 65 72 0a 77 ng the encoder.w
1950: 69 6c 6c 20 65 6d 69 74 20 74 68 65 20 6e 65 63 ill emit the nec
1960: 65 73 73 61 72 79 20 69 6e 73 74 72 75 63 74 69 essary instructi
1970: 6f 6e 73 20 61 73 20 64 65 73 63 72 69 62 65 64 ons as described
1980: 20 61 62 6f 76 65 2c 20 73 65 74 20 22 62 61 73 above, set "bas
1990: 65 22 0a 61 6e 64 20 22 73 6c 69 64 65 22 20 74 e".and "slide" t
19a0: 6f 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 o the end of the
19b0: 20 65 6e 63 6f 64 65 64 20 72 61 6e 67 65 20 61 encoded range a
19c0: 6e 64 20 73 74 61 72 74 20 74 68 65 20 6e 65 78 nd start the nex
19d0: 74 0a 69 74 65 72 61 74 69 6f 6e 20 61 74 20 74 t.iteration at t
19e0: 68 61 74 20 70 6f 69 6e 74 2e 3c 2f 70 3e 0a 0a hat point.</p>..
19f0: 3c 70 3e 49 66 2c 20 6f 6e 20 74 68 65 20 6f 74 <p>If, on the ot
1a00: 68 65 72 20 68 61 6e 64 2c 20 74 68 65 20 65 6e her hand, the en
1a10: 63 6f 64 65 72 20 65 69 74 68 65 72 20 64 69 64 coder either did
1a20: 20 6e 6f 74 20 66 69 6e 64 20 63 61 6e 64 69 64 not find candid
1a30: 61 74 65 0a 6c 6f 63 61 74 69 6f 6e 73 20 69 6e ate.locations in
1a40: 20 74 68 65 20 6f 72 69 67 69 6e 2c 20 6f 72 20 the origin, or
1a50: 74 68 65 20 62 65 73 74 20 72 61 6e 67 65 20 63 the best range c
1a60: 6f 6d 69 6e 67 20 6f 75 74 20 6f 66 20 74 68 65 oming out of the
1a70: 20 73 65 61 72 63 68 0a 6e 65 65 64 65 64 20 6d search.needed m
1a80: 6f 72 65 20 62 79 74 65 73 20 74 6f 20 65 6e 63 ore bytes to enc
1a90: 6f 64 65 20 74 68 65 20 72 61 6e 67 65 20 74 68 ode the range th
1aa0: 61 6e 20 74 68 65 72 65 20 77 65 72 65 20 62 79 an there were by
1ab0: 74 65 73 20 69 6e 20 74 68 65 0a 72 61 6e 67 65 tes in the.range
1ac0: 2c 20 74 68 65 6e 20 6e 6f 20 69 6e 73 74 72 75 , then no instru
1ad0: 63 74 69 6f 6e 73 20 61 72 65 20 65 6d 69 74 74 ctions are emitt
1ae0: 65 64 20 61 6e 64 20 74 68 65 20 77 69 6e 64 6f ed and the windo
1af0: 77 20 69 73 20 6d 6f 76 65 64 20 6f 6e 65 0a 62 w is moved one.b
1b00: 79 74 65 20 66 6f 72 77 61 72 64 2e 20 54 68 65 yte forward. The
1b10: 20 22 62 61 73 65 22 20 69 73 20 6c 65 66 74 20 "base" is left
1b20: 75 6e 63 68 61 6e 67 65 64 20 69 6e 20 74 68 61 unchanged in tha
1b30: 74 20 63 61 73 65 2e 3c 2f 70 3e 0a 0a 3c 70 3e t case.</p>..<p>
1b40: 54 68 65 20 70 72 6f 63 65 73 73 69 6e 67 20 6c The processing l
1b50: 6f 6f 70 20 73 74 6f 70 73 20 61 74 20 6f 6e 65 oop stops at one
1b60: 20 6f 66 20 74 77 6f 20 63 6f 6e 64 69 74 69 6f of two conditio
1b70: 6e 73 3a 0a 3c 6f 6c 3e 0a 3c 6c 69 3e 54 68 65 ns:.<ol>.<li>The
1b80: 20 65 6e 63 6f 64 65 72 20 64 65 63 69 64 65 64 encoder decided
1b90: 20 74 6f 20 6d 6f 76 65 20 74 68 65 20 77 69 6e to move the win
1ba0: 64 6f 77 20 66 6f 72 77 61 72 64 2c 20 62 75 74 dow forward, but
1bb0: 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 0a the end of the.
1bc0: 77 69 6e 64 6f 77 20 72 65 61 63 68 65 64 20 74 window reached t
1bd0: 68 65 20 65 6e 64 20 6f 66 20 74 68 65 20 22 74 he end of the "t
1be0: 61 72 67 65 74 22 2e 20 0a 3c 2f 6c 69 3e 0a 3c arget". .</li>.<
1bf0: 6c 69 3e 41 66 74 65 72 20 74 68 65 20 65 6d 69 li>After the emi
1c00: 73 73 69 6f 6e 20 6f 66 20 69 6e 73 74 72 75 63 ssion of instruc
1c10: 74 69 6f 6e 73 20 74 68 65 20 6e 65 77 20 22 62 tions the new "b
1c20: 61 73 65 22 20 6c 6f 63 61 74 69 6f 6e 20 69 73 ase" location is
1c30: 0a 77 69 74 68 69 6e 20 4e 48 41 53 48 20 62 79 .within NHASH by
1c40: 74 65 73 20 6f 66 20 65 6e 64 20 6f 66 20 74 68 tes of end of th
1c50: 65 20 22 74 61 72 67 65 74 22 2c 20 69 2e 65 2e e "target", i.e.
1c60: 20 74 68 65 72 65 20 61 72 65 20 6e 6f 20 6d 6f there are no mo
1c70: 72 65 20 74 68 61 6e 0a 61 74 20 6d 6f 73 74 20 re than.at most
1c80: 4e 48 41 53 48 20 62 79 74 65 73 20 6c 65 66 74 NHASH bytes left
1c90: 2e 0a 3c 2f 6c 69 3e 0a 3c 2f 6f 6c 3e 0a 3c 2f ..</li>.</ol>.</
1ca0: 70 3e 0a 0a 3c 70 3e 49 66 20 74 68 65 20 70 72 p>..<p>If the pr
1cb0: 6f 63 65 73 73 69 6e 67 20 6c 6f 6f 70 20 6c 65 ocessing loop le
1cc0: 66 74 20 62 79 74 65 73 20 75 6e 65 6e 63 6f 64 ft bytes unencod
1cd0: 65 64 2c 20 69 2e 65 2e 20 22 62 61 73 65 22 20 ed, i.e. "base"
1ce0: 6e 6f 74 0a 65 78 61 63 74 6c 79 20 61 74 20 74 not.exactly at t
1cf0: 68 65 20 65 6e 64 20 6f 66 20 74 68 65 20 22 74 he end of the "t
1d00: 61 72 67 65 74 22 2c 20 61 73 20 69 73 20 70 6f arget", as is po
1d10: 73 73 69 62 6c 65 20 66 6f 72 20 62 6f 74 68 20 ssible for both
1d20: 65 6e 64 0a 63 6f 6e 64 69 74 69 6f 6e 73 2c 20 end.conditions,
1d30: 74 68 65 6e 20 6f 6e 65 20 6c 61 73 74 20 69 6e then one last in
1d40: 73 65 72 74 20 69 6e 73 74 72 75 63 74 69 6f 6e sert instruction
1d50: 20 69 73 20 65 6d 69 74 74 65 64 20 74 6f 20 70 is emitted to p
1d60: 75 74 20 74 68 65 73 65 0a 62 79 74 65 73 20 69 ut these.bytes i
1d70: 6e 74 6f 20 74 68 65 20 64 65 6c 74 61 2e 3c 70 nto the delta.<p
1d80: 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 65 78 63 65 >..<a name="exce
1d90: 70 74 69 6f 6e 73 22 3e 3c 68 32 3e 33 2e 30 20 ptions"><h2>3.0
1da0: 45 78 63 65 70 74 69 6f 6e 73 3c 2f 68 32 3e 0a Exceptions</h2>.
1db0: 0a 3c 70 3e 49 66 20 74 68 65 20 22 6f 72 69 67 .<p>If the "orig
1dc0: 69 6e 61 6c 22 20 69 73 20 61 74 20 6d 6f 73 74 inal" is at most
1dd0: 20 4e 48 41 53 48 20 62 79 74 65 73 20 6c 6f 6e NHASH bytes lon
1de0: 67 20 6e 6f 20 63 6f 6d 70 72 65 73 73 69 6f 6e g no compression
1df0: 20 6f 66 0a 63 68 61 6e 67 65 73 20 69 73 20 70 of.changes is p
1e00: 6f 73 73 69 62 6c 65 2c 20 61 6e 64 20 74 68 65 ossible, and the
1e10: 20 73 65 67 6d 65 6e 74 2d 6c 69 73 74 20 6f 66 segment-list of
1e20: 20 74 68 65 20 64 65 6c 74 61 20 63 6f 6e 73 69 the delta consi
1e30: 73 74 73 20 6f 66 20 61 0a 73 69 6e 67 6c 65 20 sts of a.single
1e40: 6c 69 74 65 72 61 6c 20 77 68 69 63 68 20 63 6f literal which co
1e50: 6e 74 61 69 6e 73 20 74 68 65 20 65 6e 74 69 72 ntains the entir
1e60: 65 20 22 74 61 72 67 65 74 22 2e 3c 2f 70 3e 0a e "target".</p>.
1e70: 0a 3c 70 3e 54 68 69 73 20 69 73 20 61 63 74 75 .<p>This is actu
1e80: 61 6c 6c 79 20 65 71 75 69 76 61 6c 65 6e 74 20 ally equivalent
1e90: 74 6f 20 74 68 65 20 73 65 63 6f 6e 64 20 65 6e to the second en
1ea0: 64 20 63 6f 6e 64 69 74 69 6f 6e 20 6f 66 20 74 d condition of t
1eb0: 68 65 0a 70 72 6f 63 65 73 73 69 6e 67 20 6c 6f he.processing lo
1ec0: 6f 70 20 64 65 73 63 72 69 62 65 64 20 69 6e 20 op described in
1ed0: 74 68 65 20 70 72 65 76 69 6f 75 73 20 73 65 63 the previous sec
1ee0: 74 69 6f 6e 2c 20 6a 75 73 74 20 63 68 65 63 6b tion, just check
1ef0: 65 64 20 62 65 66 6f 72 65 0a 61 63 74 75 61 6c ed before.actual
1f00: 6c 79 20 65 6e 74 65 72 69 6e 67 20 74 68 65 20 ly entering the
1f10: 6c 6f 6f 70 2e 3c 2f 70 3e 0a 0a 3c 61 20 6e 61 loop.</p>..<a na
1f20: 6d 65 3d 22 72 6f 6c 6c 68 61 73 68 22 3e 3c 68 me="rollhash"><h
1f30: 32 3e 34 2e 30 20 54 68 65 20 72 6f 6c 6c 69 6e 2>4.0 The rollin
1f40: 67 20 68 61 73 68 3c 2f 68 32 3e 0a 0a 3c 70 3e g hash</h2>..<p>
1f50: 54 68 65 20 72 6f 6c 6c 69 6e 67 20 68 61 73 68 The rolling hash
1f60: 20 64 65 73 63 72 69 62 65 64 20 62 65 6c 6f 77 described below
1f70: 20 61 6e 64 20 75 73 65 64 20 74 6f 20 63 6f 6d and used to com
1f80: 70 75 74 65 20 63 6f 6e 74 65 6e 74 0a 73 69 67 pute content.sig
1f90: 6e 61 74 75 72 65 73 20 77 61 73 20 63 68 6f 73 natures was chos
1fa0: 65 6e 20 6e 6f 74 20 6f 6e 6c 79 20 66 6f 72 20 en not only for
1fb0: 67 6f 6f 64 20 68 61 73 68 69 6e 67 20 70 72 6f good hashing pro
1fc0: 70 65 72 74 69 65 73 2c 20 62 75 74 20 61 6c 73 perties, but als
1fd0: 6f 0a 74 6f 20 65 6e 61 62 6c 65 20 74 68 65 20 o.to enable the
1fe0: 65 61 73 79 20 28 69 6e 63 72 65 6d 65 6e 74 61 easy (incrementa
1ff0: 6c 29 20 72 65 63 61 6c 63 75 6c 61 74 69 6f 6e l) recalculation
2000: 20 6f 66 20 69 74 73 20 76 61 6c 75 65 20 66 6f of its value fo
2010: 72 20 61 0a 73 6c 69 64 69 6e 67 20 77 69 6e 64 r a.sliding wind
2020: 6f 77 2c 20 69 2e 65 2e 20 77 68 65 72 65 20 74 ow, i.e. where t
2030: 68 65 20 6f 6c 64 65 73 74 20 62 79 74 65 20 69 he oldest byte i
2040: 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 s removed from t
2050: 68 65 20 77 69 6e 64 6f 77 0a 61 6e 64 20 61 20 he window.and a
2060: 6e 65 77 20 62 79 74 65 20 69 73 20 73 68 69 66 new byte is shif
2070: 74 65 64 20 69 6e 2e 3c 70 3e 0a 0a 3c 61 20 6e ted in.<p>..<a n
2080: 61 6d 65 3d 22 72 68 64 65 66 22 3e 3c 68 33 3e ame="rhdef"><h3>
2090: 34 2e 31 20 44 65 66 69 6e 69 74 69 6f 6e 3c 2f 4.1 Definition</
20a0: 68 33 3e 0a 0a 3c 70 3e 41 73 73 75 6d 69 6e 67 h3>..<p>Assuming
20b0: 20 61 6e 20 61 72 72 61 79 20 5a 20 6f 66 20 4e an array Z of N
20c0: 48 41 53 48 20 62 79 74 65 73 20 28 69 6e 64 65 HASH bytes (inde
20d0: 78 69 6e 67 20 73 74 61 72 74 69 6e 67 20 61 74 xing starting at
20e0: 20 30 29 20 74 68 65 0a 68 61 73 68 20 56 20 69 0) the.hash V i
20f0: 73 20 63 6f 6d 70 75 74 65 64 20 76 69 61 3c 2f s computed via</
2100: 70 3e 0a 0a 3c 70 20 61 6c 69 67 6e 3d 63 65 6e p>..<p align=cen
2110: 74 65 72 3e 3c 74 61 62 6c 65 3e 3c 74 72 3e 3c ter><table><tr><
2120: 74 64 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 3d td>.<p><img src=
2130: 22 65 6e 63 6f 64 65 31 2e 67 69 66 22 20 61 6c "encode1.gif" al
2140: 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f 70 ign="center"></p
2150: 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 65 >.<p><img src="e
2160: 6e 63 6f 64 65 32 2e 67 69 66 22 20 61 6c 69 67 ncode2.gif" alig
2170: 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a n="center"></p>.
2180: 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 <p><img src="enc
2190: 6f 64 65 33 2e 67 69 66 22 20 61 6c 69 67 6e 3d ode3.gif" align=
21a0: 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c 2f "center"></p>.</
21b0: 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e td></tr></table>
21c0: 3c 2f 70 3e 0a 0a 77 68 65 72 65 20 41 20 61 6e </p>..where A an
21d0: 64 20 42 20 61 72 65 20 75 6e 73 69 67 6e 65 64 d B are unsigned
21e0: 20 31 36 2d 62 69 74 20 69 6e 74 65 67 65 72 73 16-bit integers
21f0: 20 28 68 65 6e 63 65 20 74 68 65 20 3c 75 3e 6d (hence the <u>m
2200: 6f 64 3c 2f 75 3e 29 2c 20 61 6e 64 0a 56 20 69 od</u>), and.V i
2210: 73 20 61 20 33 32 2d 62 69 74 20 75 6e 73 69 67 s a 32-bit unsig
2220: 6e 65 64 20 69 6e 74 65 67 65 72 20 77 69 74 68 ned integer with
2230: 20 42 20 61 73 20 4d 53 42 2c 20 41 20 61 73 20 B as MSB, A as
2240: 4c 53 42 2e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 72 LSB...<a name="r
2250: 68 69 6e 63 72 22 3e 3c 68 33 3e 34 2e 32 20 49 hincr"><h3>4.2 I
2260: 6e 63 72 65 6d 65 6e 74 61 6c 20 72 65 63 61 6c ncremental recal
2270: 63 75 6c 61 74 69 6f 6e 3c 2f 68 33 3e 0a 0a 3c culation</h3>..<
2280: 70 3e 41 73 73 75 6d 69 6e 67 20 61 6e 20 61 72 p>Assuming an ar
2290: 72 61 79 20 5a 20 6f 66 20 4e 48 41 53 48 20 62 ray Z of NHASH b
22a0: 79 74 65 73 20 28 69 6e 64 65 78 69 6e 67 20 73 ytes (indexing s
22b0: 74 61 72 74 69 6e 67 20 61 74 20 30 29 20 77 69 tarting at 0) wi
22c0: 74 68 0a 68 61 73 68 20 56 20 28 61 6e 64 20 63 th.hash V (and c
22d0: 6f 6d 70 6f 6e 65 6e 74 73 20 41 20 61 6e 64 20 omponents A and
22e0: 42 29 2c 20 74 68 65 20 64 72 6f 70 70 65 64 0a B), the dropped.
22f0: 62 79 74 65 20 3c 69 6d 67 20 73 72 63 3d 22 65 byte <img src="e
2300: 6e 63 6f 64 65 34 2e 67 69 66 22 20 61 6c 69 67 ncode4.gif" alig
2310: 6e 3d 22 63 65 6e 74 65 72 22 3e 2c 20 61 6e 64 n="center">, and
2320: 20 74 68 65 20 6e 65 77 20 62 79 74 65 0a 3c 69 the new byte.<i
2330: 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 35 2e mg src="encode5.
2340: 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 gif" align="cent
2350: 65 72 22 3e 20 2c 20 74 68 65 20 6e 65 77 20 68 er"> , the new h
2360: 61 73 68 20 63 61 6e 0a 62 65 20 63 6f 6d 70 75 ash can.be compu
2370: 74 65 64 20 69 6e 63 72 65 6d 65 6e 74 61 6c 6c ted incrementall
2380: 79 20 76 69 61 3a 20 3c 2f 70 3e 0a 0a 3c 70 20 y via: </p>..<p
2390: 61 6c 69 67 6e 3d 63 65 6e 74 65 72 3e 3c 74 61 align=center><ta
23a0: 62 6c 65 3e 3c 74 72 3e 3c 74 64 3e 0a 3c 70 3e ble><tr><td>.<p>
23b0: 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 <img src="encode
23c0: 36 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 6.gif" align="ce
23d0: 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c 70 3e 3c 69 nter"></p>.<p><i
23e0: 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 37 2e mg src="encode7.
23f0: 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 gif" align="cent
2400: 65 72 22 3e 3c 2f 70 3e 0a 3c 70 3e 3c 69 6d 67 er"></p>.<p><img
2410: 20 73 72 63 3d 22 65 6e 63 6f 64 65 38 2e 67 69 src="encode8.gi
2420: 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 f" align="center
2430: 22 3e 3c 2f 70 3e 0a 3c 2f 74 64 3e 3c 2f 74 72 "></p>.</td></tr
2440: 3e 3c 2f 74 61 62 6c 65 3e 3c 2f 70 3e 0a 0a 3c ></table></p>..<
2450: 70 3e 46 6f 72 20 41 2c 20 74 68 65 20 72 65 67 p>For A, the reg
2460: 75 6c 61 72 20 73 75 6d 2c 20 69 74 20 63 61 6e ular sum, it can
2470: 20 62 65 20 73 65 65 6e 20 65 61 73 69 6c 79 20 be seen easily
2480: 74 68 61 74 20 74 68 69 73 20 74 68 65 20 63 6f that this the co
2490: 72 72 65 63 74 0a 77 61 79 20 72 65 63 6f 6d 70 rrect.way recomp
24a0: 75 74 69 6e 67 20 74 68 61 74 20 63 6f 6d 70 6f uting that compo
24b0: 6e 65 6e 74 2e 3c 2f 70 3e 0a 0a 3c 70 3e 46 6f nent.</p>..<p>Fo
24c0: 72 20 42 2c 20 74 68 65 20 77 65 69 67 68 74 65 r B, the weighte
24d0: 64 20 73 75 6d 2c 20 6e 6f 74 65 20 66 69 72 73 d sum, note firs
24e0: 74 20 74 68 61 74 20 3c 69 6d 67 20 73 72 63 3d t that <img src=
24f0: 22 65 6e 63 6f 64 65 34 2e 67 69 66 22 0a 61 6c "encode4.gif".al
2500: 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 20 68 61 ign="center"> ha
2510: 73 20 74 68 65 20 77 65 69 67 68 74 20 4e 48 41 s the weight NHA
2520: 53 48 20 69 6e 20 74 68 65 20 73 75 6d 2c 20 73 SH in the sum, s
2530: 6f 20 74 68 61 74 20 69 73 20 77 68 61 74 20 68 o that is what h
2540: 61 73 0a 74 6f 20 62 65 20 72 65 6d 6f 76 65 64 as.to be removed
2550: 2e 20 54 68 65 6e 20 61 64 64 69 6e 67 20 69 6e . Then adding in
2560: 20 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 <img src="encod
2570: 65 39 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 e9.gif" align="c
2580: 65 6e 74 65 72 22 3e 0a 61 64 64 73 20 6f 6e 65 enter">.adds one
2590: 20 77 65 69 67 68 74 20 66 61 63 74 6f 72 20 74 weight factor t
25a0: 6f 20 61 6c 6c 20 74 68 65 20 6f 74 68 65 72 20 o all the other
25b0: 76 61 6c 75 65 73 20 6f 66 20 5a 2c 20 61 6e 64 values of Z, and
25c0: 20 61 74 20 6c 61 73 74 20 61 64 64 73 0a 69 6e at last adds.in
25d0: 20 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 <img src="encod
25e0: 65 35 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 e5.gif" align="c
25f0: 65 6e 74 65 72 22 3e 20 77 69 74 68 20 77 65 69 enter"> with wei
2600: 67 68 74 20 31 2c 20 61 6c 73 6f 0a 67 65 6e 65 ght 1, also.gene
2610: 72 61 74 69 6e 67 20 74 68 65 20 63 6f 72 72 65 rating the corre
2620: 63 74 20 6e 65 77 20 73 75 6d 3c 2f 70 3e 0a 0a ct new sum</p>..
2630: 3c 2f 62 6f 64 79 3e 0a 3c 2f 68 74 6d 6c 3e 0a </body>.</html>.