0000: 3c 6e 6f 77 69 6b 69 3e 0a 3c 68 31 20 61 6c 69 <nowiki>.<h1 ali
0010: 67 6e 3d 22 63 65 6e 74 65 72 22 3e 0a 46 6f 73 gn="center">.Fos
0020: 73 69 6c 20 44 65 6c 74 61 20 45 6e 63 6f 64 69 sil Delta Encodi
0030: 6e 67 20 41 6c 67 6f 72 69 74 68 6d 0a 3c 2f 68 ng Algorithm.</h
0040: 31 3e 0a 0a 3c 70 3e 41 20 6b 65 79 20 63 6f 6d 1>..<p>A key com
0050: 70 6f 6e 65 6e 74 20 66 6f 72 20 74 68 65 20 65 ponent for the e
0060: 66 66 69 63 69 65 6e 74 20 73 74 6f 72 61 67 65 fficient storage
0070: 20 6f 66 20 6d 75 6c 74 69 70 6c 65 20 72 65 76 of multiple rev
0080: 69 73 69 6f 6e 73 20 6f 66 0a 61 20 66 69 6c 65 isions of.a file
0090: 20 69 6e 20 66 6f 73 73 69 6c 20 72 65 70 6f 73 in fossil repos
00a0: 69 74 6f 72 69 65 73 20 69 73 20 74 68 65 20 75 itories is the u
00b0: 73 65 20 6f 66 20 64 65 6c 74 61 2d 63 6f 6d 70 se of delta-comp
00c0: 72 65 73 73 69 6f 6e 2c 20 69 2e 65 2e 20 74 6f ression, i.e. to
00d0: 0a 73 74 6f 72 65 20 6f 6e 6c 79 20 74 68 65 20 .store only the
00e0: 63 68 61 6e 67 65 73 20 62 65 74 77 65 65 6e 20 changes between
00f0: 72 65 76 69 73 69 6f 6e 73 20 69 6e 73 74 65 61 revisions instea
0100: 64 20 6f 66 20 74 68 65 20 77 68 6f 6c 65 0a 66 d of the whole.f
0110: 69 6c 65 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 69 ile.</p>..<p>Thi
0120: 73 20 64 6f 63 75 6d 65 6e 74 20 64 65 73 63 72 s document descr
0130: 69 62 65 73 20 74 68 65 20 65 6e 63 6f 64 69 6e ibes the encodin
0140: 67 20 61 6c 67 6f 72 69 74 68 6d 20 75 73 65 64 g algorithm used
0150: 20 62 79 20 46 6f 73 73 69 6c 20 74 6f 0a 67 65 by Fossil to.ge
0160: 6e 65 72 61 74 65 20 64 65 6c 74 61 73 2e 20 49 nerate deltas. I
0170: 74 20 69 73 20 74 61 72 67 65 74 65 64 20 61 74 t is targeted at
0180: 20 64 65 76 65 6c 6f 70 65 72 73 20 77 6f 72 6b developers work
0190: 69 6e 67 20 6f 6e 20 65 69 74 68 65 72 0a 3c 61 ing on either.<a
01a0: 20 68 72 65 66 3d 22 69 6e 64 65 78 2e 77 69 6b href="index.wik
01b0: 69 22 3e 66 6f 73 73 69 6c 3c 2f 61 3e 20 69 74 i">fossil</a> it
01c0: 73 65 6c 66 2c 20 6f 72 20 6f 6e 20 74 6f 6f 6c self, or on tool
01d0: 73 20 63 6f 6d 70 61 74 69 62 6c 65 20 77 69 74 s compatible wit
01e0: 68 0a 69 74 2e 20 54 68 65 20 65 78 61 63 74 20 h.it. The exact
01f0: 66 6f 72 6d 61 74 20 6f 66 20 74 68 65 20 67 65 format of the ge
0200: 6e 65 72 61 74 65 64 20 62 79 74 65 2d 73 65 71 nerated byte-seq
0210: 75 65 6e 63 65 73 2c 20 77 68 69 6c 65 20 69 6e uences, while in
0220: 20 67 65 6e 65 72 61 6c 0a 6e 6f 74 20 6e 65 63 general.not nec
0230: 65 73 73 61 72 79 20 74 6f 20 75 6e 64 65 72 73 essary to unders
0240: 74 61 6e 64 20 65 6e 63 6f 64 65 72 20 6f 70 65 tand encoder ope
0250: 72 61 74 69 6f 6e 2c 20 63 61 6e 20 62 65 20 66 ration, can be f
0260: 6f 75 6e 64 20 69 6e 20 74 68 65 0a 63 6f 6d 70 ound in the.comp
0270: 61 6e 69 6f 6e 20 73 70 65 63 69 66 69 63 61 74 anion specificat
0280: 69 6f 6e 20 74 69 74 6c 65 64 20 22 3c 61 20 68 ion titled "<a h
0290: 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 ref="delta_forma
02a0: 74 2e 77 69 6b 69 22 3e 46 6f 73 73 69 6c 0a 44 t.wiki">Fossil.D
02b0: 65 6c 74 61 20 46 6f 72 6d 61 74 3c 2f 61 3e 22 elta Format</a>"
02c0: 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 65 20 61 ..</p>..<p>The a
02d0: 6c 67 6f 72 69 74 68 6d 20 69 73 20 69 6e 73 70 lgorithm is insp
02e0: 69 72 65 64 0a 62 79 20 3c 61 20 68 72 65 66 3d ired.by <a href=
02f0: 22 68 74 74 70 3a 2f 2f 73 61 6d 62 61 2e 61 6e "http://samba.an
0300: 75 2e 65 64 75 2e 61 75 2f 72 73 79 6e 63 2f 22 u.edu.au/rsync/"
0310: 3e 72 73 79 6e 63 3c 2f 61 3e 2e 3c 2f 70 3e 0a >rsync</a>.</p>.
0320: 0a 3c 61 20 6e 61 6d 65 3d 22 61 72 67 72 65 73 .<a name="argres
0330: 70 61 72 61 6d 22 3e 3c 2f 61 3e 3c 68 32 3e 31 param"></a><h2>1
0340: 2e 30 20 41 72 67 75 6d 65 6e 74 73 2c 20 52 65 .0 Arguments, Re
0350: 73 75 6c 74 73 2c 20 61 6e 64 20 50 61 72 61 6d sults, and Param
0360: 65 74 65 72 73 3c 2f 68 32 3e 0a 0a 3c 70 3e 54 eters</h2>..<p>T
0370: 68 65 20 65 6e 63 6f 64 65 72 20 74 61 6b 65 73 he encoder takes
0380: 20 74 77 6f 20 62 79 74 65 2d 73 65 71 75 65 6e two byte-sequen
0390: 63 65 73 20 61 73 20 69 6e 70 75 74 2c 20 74 68 ces as input, th
03a0: 65 20 22 6f 72 69 67 69 6e 61 6c 22 2c 20 61 6e e "original", an
03b0: 64 0a 74 68 65 20 22 74 61 72 67 65 74 22 2c 20 d.the "target",
03c0: 61 6e 64 20 72 65 74 75 72 6e 73 20 61 20 73 69 and returns a si
03d0: 6e 67 6c 65 20 62 79 74 65 2d 73 65 71 75 65 6e ngle byte-sequen
03e0: 63 65 20 63 6f 6e 74 61 69 6e 69 6e 67 20 74 68 ce containing th
03f0: 65 0a 22 64 65 6c 74 61 22 20 77 68 69 63 68 20 e."delta" which
0400: 74 72 61 6e 73 66 6f 72 6d 73 20 74 68 65 20 6f transforms the o
0410: 72 69 67 69 6e 61 6c 20 69 6e 74 6f 20 74 68 65 riginal into the
0420: 20 74 61 72 67 65 74 20 75 70 6f 6e 20 69 74 73 target upon its
0430: 0a 61 70 70 6c 69 63 61 74 69 6f 6e 2e 3c 2f 70 .application.</p
0440: 3e 0a 0a 3c 70 3e 4e 6f 74 65 20 74 68 61 74 20 >..<p>Note that
0450: 74 68 65 20 64 61 74 61 20 6f 66 20 61 20 22 62 the data of a "b
0460: 79 74 65 2d 73 65 71 75 65 6e 63 65 22 20 69 6e yte-sequence" in
0470: 63 6c 75 64 65 73 20 69 74 73 20 6c 65 6e 67 74 cludes its lengt
0480: 68 2c 0a 69 2e 65 2e 20 74 68 65 20 6e 75 6d 62 h,.i.e. the numb
0490: 65 72 20 6f 66 20 62 79 74 65 73 20 63 6f 6e 74 er of bytes cont
04a0: 61 69 6e 65 64 20 69 6e 20 74 68 65 20 73 65 71 ained in the seq
04b0: 75 65 6e 63 65 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 uence.</p>..<p>T
04c0: 68 65 20 61 6c 67 6f 72 69 74 68 6d 20 68 61 73 he algorithm has
04d0: 20 6f 6e 65 20 70 61 72 61 6d 65 74 65 72 20 6e one parameter n
04e0: 61 6d 65 64 20 22 4e 48 41 53 48 22 2c 20 74 68 amed "NHASH", th
04f0: 65 20 73 69 7a 65 20 6f 66 20 74 68 65 0a 22 73 e size of the."s
0500: 6c 69 64 69 6e 67 20 77 69 6e 64 6f 77 22 20 66 liding window" f
0510: 6f 72 20 74 68 65 20 22 72 6f 6c 6c 69 6e 67 20 or the "rolling
0520: 68 61 73 68 22 2c 20 69 6e 20 62 79 74 65 73 2e hash", in bytes.
0530: 20 54 68 65 73 65 20 74 77 6f 20 74 65 72 6d 73 These two terms
0540: 20 61 72 65 0a 65 78 70 6c 61 69 6e 65 64 20 69 are.explained i
0550: 6e 20 74 68 65 20 6e 65 78 74 20 73 65 63 74 69 n the next secti
0560: 6f 6e 2e 20 54 68 65 20 76 61 6c 75 65 20 6f 66 on. The value of
0570: 20 74 68 69 73 20 70 61 72 61 6d 65 74 65 72 20 this parameter
0580: 68 61 73 20 74 6f 20 62 65 20 61 0a 70 6f 77 65 has to be a.powe
0590: 72 20 6f 66 20 74 77 6f 20 66 6f 72 20 74 68 65 r of two for the
05a0: 20 61 6c 67 6f 72 69 74 68 6d 20 74 6f 20 77 6f algorithm to wo
05b0: 72 6b 2e 20 46 6f 72 20 46 6f 73 73 69 6c 20 74 rk. For Fossil t
05c0: 68 65 20 76 61 6c 75 65 20 6f 66 20 74 68 69 73 he value of this
05d0: 0a 70 61 72 61 6d 65 74 65 72 20 69 73 20 73 65 .parameter is se
05e0: 74 20 74 6f 20 22 31 36 22 2e 3c 2f 70 3e 0a 0a t to "16".</p>..
05f0: 3c 61 20 6e 61 6d 65 3d 22 6f 70 65 72 61 74 69 <a name="operati
0600: 6f 6e 22 3e 3c 2f 61 3e 3c 68 32 3e 32 2e 30 20 on"></a><h2>2.0
0610: 4f 70 65 72 61 74 69 6f 6e 3c 2f 68 32 3e 0a 0a Operation</h2>..
0620: 3c 70 3e 54 68 65 20 61 6c 67 6f 72 69 74 68 6d <p>The algorithm
0630: 20 69 73 20 73 70 6c 69 74 20 69 6e 74 6f 20 74 is split into t
0640: 68 72 65 65 20 70 68 61 73 65 73 20 77 68 69 63 hree phases whic
0650: 68 20 67 65 6e 65 72 61 74 65 0a 74 68 65 20 3c h generate.the <
0660: 61 20 68 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f a href="delta_fo
0670: 72 6d 61 74 2e 77 69 6b 69 23 68 65 61 64 65 72 rmat.wiki#header
0680: 22 3e 68 65 61 64 65 72 3c 2f 61 3e 2c 0a 3c 61 ">header</a>,.<a
0690: 20 68 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 href="delta_for
06a0: 6d 61 74 2e 77 69 6b 69 23 73 6c 69 73 74 22 3e mat.wiki#slist">
06b0: 73 65 67 6d 65 6e 74 20 6c 69 73 74 3c 2f 61 3e segment list</a>
06c0: 2c 0a 61 6e 64 20 3c 61 20 68 72 65 66 3d 22 64 ,.and <a href="d
06d0: 65 6c 74 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 elta_format.wiki
06e0: 23 74 72 61 69 6c 65 72 22 3e 74 72 61 69 6c 65 #trailer">traile
06f0: 72 3c 2f 61 3e 20 6f 66 20 74 68 65 20 64 65 6c r</a> of the del
0700: 74 61 2c 20 70 65 72 0a 69 74 73 20 67 65 6e 65 ta, per.its gene
0710: 72 61 6c 20 3c 61 20 68 72 65 66 3d 22 64 65 6c ral <a href="del
0720: 74 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 23 73 ta_format.wiki#s
0730: 74 72 75 63 74 75 72 65 22 3e 73 74 72 75 63 74 tructure">struct
0740: 75 72 65 3c 2f 61 3e 2e 3c 2f 70 3e 0a 0a 3c 70 ure</a>.</p>..<p
0750: 3e 54 68 65 20 74 77 6f 20 70 68 61 73 65 73 20 >The two phases
0760: 67 65 6e 65 72 61 74 69 6e 67 20 68 65 61 64 65 generating heade
0770: 72 20 61 6e 64 20 74 72 61 69 6c 65 72 20 61 72 r and trailer ar
0780: 65 20 6e 6f 74 20 63 6f 76 65 72 65 64 20 68 65 e not covered he
0790: 72 65 0a 61 73 20 74 68 65 69 72 20 69 6d 70 6c re.as their impl
07a0: 65 6d 65 6e 74 61 74 69 6f 6e 20 74 72 69 76 69 ementation trivi
07b0: 61 6c 6c 79 20 66 6f 6c 6c 6f 77 73 20 64 69 72 ally follows dir
07c0: 65 63 74 6c 79 20 66 72 6f 6d 20 74 68 65 0a 73 ectly from the.s
07d0: 70 65 63 69 66 69 63 61 74 69 6f 6e 20 6f 66 20 pecification of
07e0: 74 68 65 20 3c 61 20 68 72 65 66 3d 22 64 65 6c the <a href="del
07f0: 74 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 22 3e ta_format.wiki">
0800: 64 65 6c 74 61 20 66 6f 72 6d 61 74 3c 2f 61 3e delta format</a>
0810: 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 69 73 20 6c .</p>..<p>This l
0820: 65 61 76 65 73 20 74 68 65 20 73 65 67 6d 65 6e eaves the segmen
0830: 74 2d 6c 69 73 74 2e 20 49 74 73 20 67 65 6e 65 t-list. Its gene
0840: 72 61 74 69 6f 6e 20 69 73 20 64 6f 6e 65 20 69 ration is done i
0850: 6e 20 74 77 6f 20 70 68 61 73 65 73 2c 0a 61 20 n two phases,.a
0860: 70 72 65 2d 70 72 6f 63 65 73 73 69 6e 67 20 73 pre-processing s
0870: 74 65 70 20 6f 70 65 72 61 74 69 6e 67 20 6f 6e tep operating on
0880: 20 74 68 65 20 22 6f 72 69 67 69 6e 61 6c 22 20 the "original"
0890: 62 79 74 65 2d 73 65 71 75 65 6e 63 65 2c 0a 66 byte-sequence,.f
08a0: 6f 6c 6c 6f 77 65 64 20 62 79 20 74 68 65 20 70 ollowed by the p
08b0: 72 6f 63 65 73 73 69 6e 67 20 6f 66 20 74 68 65 rocessing of the
08c0: 20 22 74 61 72 67 65 74 22 20 62 79 74 65 2d 73 "target" byte-s
08d0: 65 71 75 65 6e 63 65 20 75 73 69 6e 67 20 74 68 equence using th
08e0: 65 0a 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 67 61 e.information ga
08f0: 74 68 65 72 65 64 20 62 79 20 74 68 65 20 66 69 thered by the fi
0900: 72 73 74 20 73 74 65 70 2e 3c 2f 70 3e 0a 0a 3c rst step.</p>..<
0910: 61 20 6e 61 6d 65 3d 22 70 72 65 70 72 6f 63 65 a name="preproce
0920: 73 73 69 6e 67 22 3e 3c 2f 61 3e 3c 68 33 3e 32 ssing"></a><h3>2
0930: 2e 31 20 50 72 65 70 72 6f 63 65 73 73 69 6e 67 .1 Preprocessing
0940: 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 3c 2f 68 the original</h
0950: 33 3e 0a 0a 3c 70 3e 41 20 6d 61 6a 6f 72 20 70 3>..<p>A major p
0960: 61 72 74 20 6f 66 20 74 68 65 20 70 72 6f 63 65 art of the proce
0970: 73 73 69 6e 67 20 6f 66 20 74 68 65 20 22 74 61 ssing of the "ta
0980: 72 67 65 74 22 20 69 73 20 74 6f 20 66 69 6e 64 rget" is to find
0990: 20 61 20 72 61 6e 67 65 0a 69 6e 20 74 68 65 20 a range.in the
09a0: 22 6f 72 69 67 69 6e 61 6c 22 20 77 68 69 63 68 "original" which
09b0: 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 73 61 contains the sa
09c0: 6d 65 20 63 6f 6e 74 65 6e 74 20 61 73 20 66 6f me content as fo
09d0: 75 6e 64 20 61 74 20 74 68 65 0a 63 75 72 72 65 und at the.curre
09e0: 6e 74 20 6c 6f 63 61 74 69 6f 6e 20 69 6e 20 74 nt location in t
09f0: 68 65 20 22 74 61 72 67 65 74 22 2e 3c 2f 70 3e he "target".</p>
0a00: 0a 0a 3c 70 3e 41 20 6e 61 69 76 65 20 61 70 70 ..<p>A naive app
0a10: 72 6f 61 63 68 20 74 6f 20 74 68 69 73 20 77 6f roach to this wo
0a20: 75 6c 64 20 62 65 20 74 6f 20 73 65 61 72 63 68 uld be to search
0a30: 20 74 68 65 20 77 68 6f 6c 65 20 22 6f 72 69 67 the whole "orig
0a40: 69 6e 61 6c 22 0a 66 6f 72 20 73 75 63 68 20 63 inal".for such c
0a50: 6f 6e 74 65 6e 74 2e 20 54 68 69 73 20 68 6f 77 ontent. This how
0a60: 65 76 65 72 20 69 73 20 76 65 72 79 20 69 6e 65 ever is very ine
0a70: 66 66 69 63 69 65 6e 74 20 61 73 20 69 74 20 77 fficient as it w
0a80: 6f 75 6c 64 20 73 65 61 72 63 68 0a 74 68 65 20 ould search.the
0a90: 73 61 6d 65 20 70 61 72 74 73 20 6f 66 20 74 68 same parts of th
0aa0: 65 20 22 6f 72 69 67 69 6e 61 6c 22 20 6f 76 65 e "original" ove
0ab0: 72 20 61 6e 64 20 6f 76 65 72 2e 20 57 68 61 74 r and over. What
0ac0: 20 69 73 20 64 6f 6e 65 20 69 6e 73 74 65 61 64 is done instead
0ad0: 0a 69 73 20 74 6f 20 73 61 6d 70 6c 65 20 74 68 .is to sample th
0ae0: 65 20 22 6f 72 69 67 69 6e 61 6c 22 20 61 74 20 e "original" at
0af0: 72 65 67 75 6c 61 72 20 69 6e 74 65 72 76 61 6c regular interval
0b00: 73 2c 20 63 6f 6d 70 75 74 65 20 73 69 67 6e 61 s, compute signa
0b10: 74 75 72 65 73 0a 66 6f 72 20 74 68 65 20 73 61 tures.for the sa
0b20: 6d 70 6c 65 64 20 6c 6f 63 61 74 69 6f 6e 73 20 mpled locations
0b30: 61 6e 64 20 73 74 6f 72 65 20 74 68 65 6d 20 69 and store them i
0b40: 6e 20 61 20 68 61 73 68 20 74 61 62 6c 65 20 6b n a hash table k
0b50: 65 79 65 64 20 62 79 0a 74 68 65 73 65 20 73 69 eyed by.these si
0b60: 67 6e 61 74 75 72 65 73 2e 3c 2f 70 3e 0a 0a 3c gnatures.</p>..<
0b70: 70 3e 54 68 61 74 20 69 73 20 77 68 61 74 20 68 p>That is what h
0b80: 61 70 70 65 6e 73 20 69 6e 20 74 68 69 73 20 73 appens in this s
0b90: 74 65 70 2e 20 54 68 65 20 66 6f 6c 6c 6f 77 69 tep. The followi
0ba0: 6e 67 20 70 72 6f 63 65 73 73 69 6e 67 20 73 74 ng processing st
0bb0: 65 70 0a 63 61 6e 20 74 68 65 6e 20 74 68 65 20 ep.can then the
0bc0: 63 6f 6d 70 75 74 65 20 73 69 67 6e 61 74 75 72 compute signatur
0bd0: 65 20 66 6f 72 20 69 74 73 20 63 75 72 72 65 6e e for its curren
0be0: 74 20 6c 6f 63 61 74 69 6f 6e 20 61 6e 64 20 74 t location and t
0bf0: 68 65 6e 20 68 61 73 0a 74 6f 20 73 65 61 72 63 hen has.to searc
0c00: 68 20 6f 6e 6c 79 20 61 20 6e 61 72 72 6f 77 20 h only a narrow
0c10: 73 65 74 20 6f 66 20 6c 6f 63 61 74 69 6f 6e 73 set of locations
0c20: 20 69 6e 20 74 68 65 20 22 6f 72 69 67 69 6e 61 in the "origina
0c30: 6c 22 20 66 6f 72 0a 70 6f 73 73 69 62 6c 65 20 l" for.possible
0c40: 6d 61 74 63 68 65 73 2c 20 6e 61 6d 65 6c 79 20 matches, namely
0c50: 74 68 6f 73 65 20 77 68 69 63 68 20 68 61 76 65 those which have
0c60: 20 74 68 65 20 73 61 6d 65 20 73 69 67 6e 61 74 the same signat
0c70: 75 72 65 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 6e 20 ure.</p>..<p>In
0c80: 64 65 74 61 69 6c 3a 3c 2f 70 3e 0a 0a 3c 6f 6c detail:</p>..<ol
0c90: 3e 0a 3c 6c 69 3e 54 68 65 20 22 6f 72 69 67 69 >.<li>The "origi
0ca0: 6e 61 6c 22 20 69 73 20 73 70 6c 69 74 20 69 6e nal" is split in
0cb0: 74 6f 20 63 68 75 6e 6b 73 20 6f 66 20 4e 48 41 to chunks of NHA
0cc0: 53 48 20 62 79 74 65 73 2e 20 4e 6f 74 65 20 74 SH bytes. Note t
0cd0: 68 61 74 20 61 0a 70 61 72 74 69 61 6c 20 63 68 hat a.partial ch
0ce0: 75 6e 6b 20 6f 66 20 6c 65 73 73 20 74 68 61 6e unk of less than
0cf0: 20 4e 48 41 53 48 20 62 79 74 65 73 20 61 74 20 NHASH bytes at
0d00: 74 68 65 20 65 6e 64 20 6f 66 20 22 6f 72 69 67 the end of "orig
0d10: 69 6e 61 6c 22 20 69 73 0a 69 67 6e 6f 72 65 64 inal" is.ignored
0d20: 2e 0a 3c 2f 6c 69 3e 0a 3c 6c 69 3e 54 68 65 20 ..</li>.<li>The
0d30: 3c 61 20 68 72 65 66 3d 22 23 72 6f 6c 6c 68 61 <a href="#rollha
0d40: 73 68 22 3e 72 6f 6c 6c 69 6e 67 20 68 61 73 68 sh">rolling hash
0d50: 3c 2f 61 3e 20 6f 66 20 65 61 63 68 20 63 68 75 </a> of each chu
0d60: 6e 6b 20 69 73 0a 63 6f 6d 70 75 74 65 64 2e 0a nk is.computed..
0d70: 3c 2f 6c 69 3e 0a 3c 6c 69 3e 41 20 68 61 73 68 </li>.<li>A hash
0d80: 74 61 62 6c 65 20 69 73 20 66 69 6c 6c 65 64 2c table is filled,
0d90: 20 6d 61 70 70 69 6e 67 20 66 72 6f 6d 20 74 68 mapping from th
0da0: 65 20 68 61 73 68 65 73 20 6f 66 20 74 68 65 20 e hashes of the
0db0: 63 68 75 6e 6b 73 20 74 6f 0a 74 68 65 20 6c 69 chunks to.the li
0dc0: 73 74 20 6f 66 20 63 68 75 6e 6b 20 6c 6f 63 61 st of chunk loca
0dd0: 74 69 6f 6e 73 20 68 61 76 69 6e 67 20 74 68 69 tions having thi
0de0: 73 20 68 61 73 68 2e 0a 3c 2f 6c 69 3e 0a 3c 2f s hash..</li>.</
0df0: 6f 6c 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 70 72 ol>..<a name="pr
0e00: 6f 63 65 73 73 69 6e 67 22 3e 3c 2f 61 3e 3c 68 ocessing"></a><h
0e10: 33 3e 32 2e 31 20 50 72 6f 63 65 73 73 69 6e 67 3>2.1 Processing
0e20: 20 74 68 65 20 74 61 72 67 65 74 3c 2f 68 33 3e the target</h3>
0e30: 0a 0a 3c 70 3e 54 68 69 73 2c 20 74 68 65 20 6d ..<p>This, the m
0e40: 61 69 6e 20 70 68 61 73 65 20 6f 66 20 74 68 65 ain phase of the
0e50: 20 65 6e 63 6f 64 65 72 2c 20 70 72 6f 63 65 73 encoder, proces
0e60: 73 65 73 20 74 68 65 20 74 61 72 67 65 74 20 69 ses the target i
0e70: 6e 20 61 20 6c 6f 6f 70 0a 66 72 6f 6d 20 62 65 n a loop.from be
0e80: 67 69 6e 6e 69 6e 67 20 74 6f 20 65 6e 64 2e 20 ginning to end.
0e90: 54 68 65 20 73 74 61 74 65 20 6f 66 20 74 68 65 The state of the
0ea0: 20 65 6e 63 6f 64 65 72 20 69 73 20 63 61 70 74 encoder is capt
0eb0: 75 72 65 64 20 62 79 20 74 77 6f 0a 6c 6f 63 61 ured by two.loca
0ec0: 74 69 6f 6e 73 2c 20 74 68 65 20 22 62 61 73 65 tions, the "base
0ed0: 22 20 61 6e 64 20 74 68 65 20 22 73 6c 69 64 65 " and the "slide
0ee0: 22 2e 20 22 62 61 73 65 22 20 70 6f 69 6e 74 73 ". "base" points
0ef0: 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 62 79 to the first by
0f00: 74 65 0a 6f 66 20 74 68 65 20 74 61 72 67 65 74 te.of the target
0f10: 20 66 6f 72 20 77 68 69 63 68 20 6e 6f 20 64 65 for which no de
0f20: 6c 74 61 20 6f 75 74 70 75 74 20 68 61 73 20 62 lta output has b
0f30: 65 65 6e 20 67 65 6e 65 72 61 74 65 64 20 79 65 een generated ye
0f40: 74 2c 20 61 6e 64 0a 22 73 6c 69 64 65 22 20 69 t, and."slide" i
0f50: 73 20 74 68 65 20 6c 6f 63 61 74 69 6f 6e 20 6f s the location o
0f60: 66 20 74 68 65 20 77 69 6e 64 6f 77 20 75 73 65 f the window use
0f70: 64 20 74 6f 20 6c 6f 6f 6b 20 69 6e 20 74 68 65 d to look in the
0f80: 20 22 6f 72 69 67 69 6e 22 20 66 6f 72 0a 63 6f "origin" for.co
0f90: 6d 6d 6f 6e 61 6c 69 74 69 65 73 2e 20 54 68 69 mmonalities. Thi
0fa0: 73 20 77 69 6e 64 6f 77 20 69 73 20 4e 48 41 53 s window is NHAS
0fb0: 48 20 62 79 74 65 73 20 6c 6f 6e 67 2e 3c 2f 70 H bytes long.</p
0fc0: 3e 0a 0a 3c 70 3e 49 6e 69 74 69 61 6c 6c 79 20 >..<p>Initially
0fd0: 62 6f 74 68 20 22 62 61 73 65 22 20 61 6e 64 20 both "base" and
0fe0: 22 73 6c 69 64 65 22 20 70 6f 69 6e 74 20 74 6f "slide" point to
0ff0: 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f the beginning o
1000: 66 20 74 68 65 0a 22 74 61 72 67 65 74 22 2e 20 f the."target".
1010: 49 6e 20 65 61 63 68 20 69 74 65 72 61 74 69 6f In each iteratio
1020: 6e 20 6f 66 20 74 68 65 20 6c 6f 6f 70 20 74 68 n of the loop th
1030: 65 20 65 6e 63 6f 64 65 72 20 64 65 63 69 64 65 e encoder decide
1040: 73 20 77 68 65 74 68 65 72 20 74 6f 0a 3c 75 6c s whether to.<ul
1050: 3e 0a 3c 6c 69 3e 65 6d 69 74 20 61 20 73 69 6e >.<li>emit a sin
1060: 67 6c 65 20 69 6e 73 74 72 75 63 74 69 6f 6e 0a gle instruction.
1070: 74 6f 20 3c 61 20 68 72 65 66 3d 22 64 65 6c 74 to <a href="delt
1080: 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 23 63 6f a_format.wiki#co
1090: 70 79 72 61 6e 67 65 22 3e 63 6f 70 79 20 61 20 pyrange">copy a
10a0: 72 61 6e 67 65 3c 2f 61 3e 2c 20 6f 72 0a 3c 2f range</a>, or.</
10b0: 6c 69 3e 0a 3c 6c 69 3e 65 6d 69 74 20 74 77 6f li>.<li>emit two
10c0: 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 2c 20 66 instructions, f
10d0: 69 72 73 74 0a 74 6f 20 3c 61 20 68 72 65 66 3d irst.to <a href=
10e0: 22 64 65 6c 74 61 5f 66 6f 72 6d 61 74 2e 77 69 "delta_format.wi
10f0: 6b 69 23 69 6e 73 65 72 74 6c 69 74 22 3e 69 6e ki#insertlit">in
1100: 73 65 72 74 20 61 20 6c 69 74 65 72 61 6c 3c 2f sert a literal</
1110: 61 3e 2c 20 74 68 65 6e 0a 74 6f 20 3c 61 20 68 a>, then.to <a h
1120: 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 ref="delta_forma
1130: 74 2e 77 69 6b 69 23 63 6f 70 79 72 61 6e 67 65 t.wiki#copyrange
1140: 22 3e 63 6f 70 79 20 61 20 72 61 6e 67 65 3c 2f ">copy a range</
1150: 61 3e 2c 20 6f 72 0a 3c 2f 6c 69 3e 0a 3c 6c 69 a>, or.</li>.<li
1160: 3e 6d 6f 76 65 20 74 68 65 20 77 69 6e 64 6f 77 >move the window
1170: 20 66 6f 72 77 61 72 64 20 6f 6e 65 20 62 79 74 forward one byt
1180: 65 2e 0a 3c 2f 6c 69 3e 0a 3c 2f 75 6c 3e 0a 3c e..</li>.</ul>.<
1190: 2f 70 3e 0a 0a 3c 69 6d 67 20 73 72 63 3d 22 65 /p>..<img src="e
11a0: 6e 63 6f 64 65 31 30 2e 67 69 66 22 20 61 6c 69 ncode10.gif" ali
11b0: 67 6e 3d 22 72 69 67 68 74 22 20 68 73 70 61 63 gn="right" hspac
11c0: 65 3d 22 31 30 22 3e 0a 3c 70 3e 54 6f 20 6d 61 e="10">.<p>To ma
11d0: 6b 65 20 74 68 69 73 20 64 65 63 69 73 69 6f 6e ke this decision
11e0: 20 74 68 65 20 65 6e 63 6f 64 65 72 20 66 69 72 the encoder fir
11f0: 73 74 20 63 6f 6d 70 75 74 65 73 20 74 68 65 20 st computes the
1200: 68 61 73 68 20 76 61 6c 75 65 20 66 6f 72 0a 74 hash value for.t
1210: 68 65 20 4e 48 41 53 48 20 62 79 74 65 73 20 69 he NHASH bytes i
1220: 6e 20 74 68 65 20 77 69 6e 64 6f 77 20 61 6e 64 n the window and
1230: 20 74 68 65 6e 20 6c 6f 6f 6b 73 20 61 74 20 61 then looks at a
1240: 6c 6c 20 74 68 65 20 6c 6f 63 61 74 69 6f 6e 73 ll the locations
1250: 20 69 6e 0a 74 68 65 20 22 6f 72 69 67 69 6e 22 in.the "origin"
1260: 20 77 68 69 63 68 20 68 61 76 65 20 74 68 65 20 which have the
1270: 73 61 6d 65 20 73 69 67 6e 61 74 75 72 65 2e 20 same signature.
1280: 54 68 69 73 20 70 61 72 74 20 75 73 65 73 20 74 This part uses t
1290: 68 65 20 68 61 73 68 0a 74 61 62 6c 65 20 63 72 he hash.table cr
12a0: 65 61 74 65 64 20 62 79 20 74 68 65 20 70 72 65 eated by the pre
12b0: 2d 70 72 6f 63 65 73 73 69 6e 67 20 73 74 65 70 -processing step
12c0: 20 74 6f 20 65 66 66 69 65 6e 74 6c 79 20 66 69 to effiently fi
12d0: 6e 64 20 74 68 65 73 65 0a 6c 6f 63 61 74 69 6f nd these.locatio
12e0: 6e 73 2e 3c 2f 70 3e 0a 0a 3c 70 3e 46 6f 72 20 ns.</p>..<p>For
12f0: 65 61 63 68 20 6f 66 20 74 68 65 20 70 6f 73 73 each of the poss
1300: 69 62 6c 65 20 63 61 6e 64 69 64 61 74 65 73 20 ible candidates
1310: 74 68 65 20 65 6e 63 6f 64 65 72 20 66 69 6e 64 the encoder find
1320: 73 20 74 68 65 20 6d 61 78 69 6d 61 6c 0a 72 61 s the maximal.ra
1330: 6e 67 65 20 6f 66 20 62 79 74 65 73 20 63 6f 6d nge of bytes com
1340: 6d 6f 6e 20 74 6f 20 62 6f 74 68 20 22 6f 72 69 mon to both "ori
1350: 67 69 6e 22 20 61 6e 64 20 22 74 61 72 67 65 74 gin" and "target
1360: 22 2c 20 67 6f 69 6e 67 20 66 6f 72 77 61 72 64 ", going forward
1370: 20 61 6e 64 0a 62 61 63 6b 77 61 72 64 20 66 72 and.backward fr
1380: 6f 6d 20 22 73 6c 69 64 65 22 20 69 6e 20 74 68 om "slide" in th
1390: 65 20 22 74 61 72 67 65 74 22 2c 20 61 6e 64 20 e "target", and
13a0: 74 68 65 20 63 61 6e 64 69 64 61 74 65 20 6c 6f the candidate lo
13b0: 63 61 74 69 6f 6e 20 69 6e 0a 74 68 65 20 22 6f cation in.the "o
13c0: 72 69 67 69 6e 22 2e 20 54 68 69 73 20 73 65 61 rigin". This sea
13d0: 72 63 68 20 69 73 20 63 6f 6e 73 74 72 61 69 6e rch is constrain
13e0: 65 64 20 6f 6e 20 74 68 65 20 73 69 64 65 20 6f ed on the side o
13f0: 66 20 74 68 65 20 22 74 61 72 67 65 74 22 0a 62 f the "target".b
1400: 79 20 74 68 65 20 22 62 61 73 65 22 20 28 62 61 y the "base" (ba
1410: 63 6b 77 61 72 64 20 73 65 61 72 63 68 29 2c 20 ckward search),
1420: 61 6e 64 20 74 68 65 20 65 6e 64 20 6f 66 20 74 and the end of t
1430: 68 65 20 22 74 61 72 67 65 74 22 20 28 66 6f 72 he "target" (for
1440: 77 61 72 64 0a 73 65 61 72 63 68 29 2c 20 61 6e ward.search), an
1450: 64 20 6f 6e 20 74 68 65 20 73 69 64 65 20 6f 66 d on the side of
1460: 20 74 68 65 20 22 6f 72 69 67 69 6e 22 20 62 79 the "origin" by
1470: 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 61 the beginning a
1480: 6e 64 20 65 6e 64 20 6f 66 0a 74 68 65 20 22 6f nd end of.the "o
1490: 72 69 67 69 6e 22 2c 20 72 65 73 70 65 63 74 69 rigin", respecti
14a0: 76 65 6c 79 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 vely.</p>..<p>Th
14b0: 65 72 65 20 61 72 65 20 69 6e 70 75 74 20 66 69 ere are input fi
14c0: 6c 65 73 20 66 6f 72 20 77 68 69 63 68 20 74 68 les for which th
14d0: 65 20 68 61 73 68 20 63 68 61 69 6e 73 20 67 65 e hash chains ge
14e0: 6e 65 72 61 74 65 64 20 62 79 20 74 68 65 0a 70 nerated by the.p
14f0: 72 65 2d 70 72 6f 63 65 73 73 69 6e 67 20 73 74 re-processing st
1500: 65 70 20 63 61 6e 20 62 65 63 6f 6d 65 20 76 65 ep can become ve
1510: 72 79 20 6c 6f 6e 67 2c 20 6c 65 61 64 69 6e 67 ry long, leading
1520: 20 74 6f 20 6c 6f 6e 67 20 73 65 61 72 63 68 20 to long search
1530: 74 69 6d 65 73 0a 61 6e 64 20 61 66 66 65 63 74 times.and affect
1540: 69 6e 67 20 74 68 65 20 70 65 72 66 6f 72 6d 61 ing the performa
1550: 6e 63 65 20 6f 66 20 74 68 65 20 64 65 6c 74 61 nce of the delta
1560: 20 67 65 6e 65 72 61 74 6f 72 2e 20 54 6f 20 6c generator. To l
1570: 69 6d 69 74 20 74 68 65 0a 65 66 66 65 63 74 20 imit the.effect
1580: 73 75 63 68 20 6c 6f 6e 67 20 63 68 61 69 6e 73 such long chains
1590: 20 63 61 6e 20 68 61 76 65 20 74 68 65 20 61 63 can have the ac
15a0: 74 75 61 6c 20 73 65 61 72 63 68 20 66 6f 72 20 tual search for
15b0: 63 61 6e 64 69 64 61 74 65 73 20 69 73 0a 62 6f candidates is.bo
15c0: 75 6e 64 65 64 2c 20 6c 6f 6f 6b 69 6e 67 20 61 unded, looking a
15d0: 74 20 6d 6f 73 74 20 4e 20 63 61 6e 64 69 64 61 t most N candida
15e0: 74 65 73 2e 20 43 75 72 72 65 6e 74 6c 79 20 4e tes. Currently N
15f0: 20 69 73 20 73 65 74 20 74 6f 20 32 35 30 2e 3c is set to 250.<
1600: 2f 70 3e 0a 0a 3c 70 3e 46 72 6f 6d 20 74 68 65 /p>..<p>From the
1610: 20 72 61 6e 67 65 73 20 66 6f 72 20 61 6c 6c 20 ranges for all
1620: 74 68 65 20 63 61 6e 64 69 64 61 74 65 73 20 74 the candidates t
1630: 68 65 20 62 65 73 74 20 28 3d 20 6c 61 72 67 65 he best (= large
1640: 73 74 29 20 63 6f 6d 6d 6f 6e 0a 72 61 6e 67 65 st) common.range
1650: 20 69 73 20 74 61 6b 65 6e 20 61 6e 64 20 69 74 is taken and it
1660: 20 69 73 20 64 65 74 65 72 6d 69 6e 65 64 20 68 is determined h
1670: 6f 77 20 6d 61 6e 79 20 62 79 74 65 73 20 61 72 ow many bytes ar
1680: 65 20 6e 65 65 64 65 64 20 74 6f 0a 65 6e 63 6f e needed to.enco
1690: 64 65 20 74 68 65 20 62 79 74 65 73 20 62 65 74 de the bytes bet
16a0: 77 65 65 6e 20 74 68 65 20 22 62 61 73 65 22 20 ween the "base"
16b0: 61 6e 64 20 74 68 65 20 65 6e 64 20 6f 66 20 74 and the end of t
16c0: 68 61 74 20 72 61 6e 67 65 2e 20 49 66 20 74 68 hat range. If th
16d0: 65 0a 72 61 6e 67 65 20 65 78 74 65 6e 64 65 64 e.range extended
16e0: 20 62 61 63 6b 20 74 6f 20 74 68 65 20 22 62 61 back to the "ba
16f0: 73 65 22 20 74 68 65 6e 20 74 68 69 73 20 63 61 se" then this ca
1700: 6e 20 62 65 20 64 6f 6e 65 20 69 6e 20 61 20 73 n be done in a s
1710: 69 6e 67 6c 65 0a 63 6f 70 79 20 69 6e 73 74 72 ingle.copy instr
1720: 75 63 74 69 6f 6e 2e 20 4f 74 68 65 72 77 69 73 uction. Otherwis
1730: 65 2c 20 69 2e 65 20 69 66 20 74 68 65 72 65 20 e, i.e if there
1740: 69 73 20 61 20 67 61 70 20 62 65 74 77 65 65 6e is a gap between
1750: 20 74 68 65 20 22 62 61 73 65 22 0a 61 6e 64 20 the "base".and
1760: 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 the beginning of
1770: 20 74 68 65 20 72 61 6e 67 65 20 74 68 65 6e 20 the range then
1780: 74 77 6f 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 two instructions
1790: 20 61 72 65 20 6e 65 65 64 65 64 2c 20 6f 6e 65 are needed, one
17a0: 0a 74 6f 20 69 6e 73 65 72 74 20 74 68 65 20 62 .to insert the b
17b0: 79 74 65 73 20 69 6e 20 74 68 65 20 67 61 70 20 ytes in the gap
17c0: 61 73 20 61 20 6c 69 74 65 72 61 6c 2c 20 61 6e as a literal, an
17d0: 64 20 61 20 63 6f 70 79 20 69 6e 73 74 72 75 63 d a copy instruc
17e0: 74 69 6f 6e 0a 66 6f 72 20 74 68 65 20 72 61 6e tion.for the ran
17f0: 67 65 20 69 74 73 65 6c 66 2e 20 54 68 65 20 67 ge itself. The g
1800: 65 6e 65 72 61 6c 20 73 69 74 75 61 74 69 6f 6e eneral situation
1810: 20 61 74 20 74 68 69 73 20 70 6f 69 6e 74 20 63 at this point c
1820: 61 6e 20 62 65 20 73 65 65 6e 0a 69 6e 20 74 68 an be seen.in th
1830: 65 20 70 69 63 74 75 72 65 20 74 6f 20 74 68 65 e picture to the
1840: 20 72 69 67 68 74 2e 3c 2f 70 3e 0a 0a 3c 70 3e right.</p>..<p>
1850: 49 66 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 If the number of
1860: 20 62 79 74 65 73 20 6e 65 65 64 65 64 20 74 6f bytes needed to
1870: 20 65 6e 63 6f 64 65 20 62 6f 74 68 20 67 61 70 encode both gap
1880: 20 28 69 66 20 70 72 65 73 65 6e 74 29 2c 20 61 (if present), a
1890: 6e 64 0a 72 61 6e 67 65 20 69 73 20 6c 65 73 73 nd.range is less
18a0: 20 74 68 61 6e 20 74 68 65 20 6e 75 6d 62 65 72 than the number
18b0: 20 6f 66 20 62 79 74 65 73 20 77 65 20 61 72 65 of bytes we are
18c0: 20 65 6e 63 6f 64 69 6e 67 20 74 68 65 20 65 6e encoding the en
18d0: 63 6f 64 65 72 0a 77 69 6c 6c 20 65 6d 69 74 20 coder.will emit
18e0: 74 68 65 20 6e 65 63 65 73 73 61 72 79 20 69 6e the necessary in
18f0: 73 74 72 75 63 74 69 6f 6e 73 20 61 73 20 64 65 structions as de
1900: 73 63 72 69 62 65 64 20 61 62 6f 76 65 2c 20 73 scribed above, s
1910: 65 74 20 22 62 61 73 65 22 0a 61 6e 64 20 22 73 et "base".and "s
1920: 6c 69 64 65 22 20 74 6f 20 74 68 65 20 65 6e 64 lide" to the end
1930: 20 6f 66 20 74 68 65 20 65 6e 63 6f 64 65 64 20 of the encoded
1940: 72 61 6e 67 65 20 61 6e 64 20 73 74 61 72 74 20 range and start
1950: 74 68 65 20 6e 65 78 74 0a 69 74 65 72 61 74 69 the next.iterati
1960: 6f 6e 20 61 74 20 74 68 61 74 20 70 6f 69 6e 74 on at that point
1970: 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 66 2c 20 6f 6e .</p>..<p>If, on
1980: 20 74 68 65 20 6f 74 68 65 72 20 68 61 6e 64 2c the other hand,
1990: 20 74 68 65 20 65 6e 63 6f 64 65 72 20 65 69 74 the encoder eit
19a0: 68 65 72 20 64 69 64 20 6e 6f 74 20 66 69 6e 64 her did not find
19b0: 20 63 61 6e 64 69 64 61 74 65 0a 6c 6f 63 61 74 candidate.locat
19c0: 69 6f 6e 73 20 69 6e 20 74 68 65 20 6f 72 69 67 ions in the orig
19d0: 69 6e 2c 20 6f 72 20 74 68 65 20 62 65 73 74 20 in, or the best
19e0: 72 61 6e 67 65 20 63 6f 6d 69 6e 67 20 6f 75 74 range coming out
19f0: 20 6f 66 20 74 68 65 20 73 65 61 72 63 68 0a 6e of the search.n
1a00: 65 65 64 65 64 20 6d 6f 72 65 20 62 79 74 65 73 eeded more bytes
1a10: 20 74 6f 20 65 6e 63 6f 64 65 20 74 68 65 20 72 to encode the r
1a20: 61 6e 67 65 20 74 68 61 6e 20 74 68 65 72 65 20 ange than there
1a30: 77 65 72 65 20 62 79 74 65 73 20 69 6e 20 74 68 were bytes in th
1a40: 65 0a 72 61 6e 67 65 2c 20 74 68 65 6e 20 6e 6f e.range, then no
1a50: 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 20 61 72 instructions ar
1a60: 65 20 65 6d 69 74 74 65 64 20 61 6e 64 20 74 68 e emitted and th
1a70: 65 20 77 69 6e 64 6f 77 20 69 73 20 6d 6f 76 65 e window is move
1a80: 64 20 6f 6e 65 0a 62 79 74 65 20 66 6f 72 77 61 d one.byte forwa
1a90: 72 64 2e 20 54 68 65 20 22 62 61 73 65 22 20 69 rd. The "base" i
1aa0: 73 20 6c 65 66 74 20 75 6e 63 68 61 6e 67 65 64 s left unchanged
1ab0: 20 69 6e 20 74 68 61 74 20 63 61 73 65 2e 3c 2f in that case.</
1ac0: 70 3e 0a 0a 3c 70 3e 54 68 65 20 70 72 6f 63 65 p>..<p>The proce
1ad0: 73 73 69 6e 67 20 6c 6f 6f 70 20 73 74 6f 70 73 ssing loop stops
1ae0: 20 61 74 20 6f 6e 65 20 6f 66 20 74 77 6f 20 63 at one of two c
1af0: 6f 6e 64 69 74 69 6f 6e 73 3a 0a 3c 6f 6c 3e 0a onditions:.<ol>.
1b00: 3c 6c 69 3e 54 68 65 20 65 6e 63 6f 64 65 72 20 <li>The encoder
1b10: 64 65 63 69 64 65 64 20 74 6f 20 6d 6f 76 65 20 decided to move
1b20: 74 68 65 20 77 69 6e 64 6f 77 20 66 6f 72 77 61 the window forwa
1b30: 72 64 2c 20 62 75 74 20 74 68 65 20 65 6e 64 20 rd, but the end
1b40: 6f 66 20 74 68 65 0a 77 69 6e 64 6f 77 20 72 65 of the.window re
1b50: 61 63 68 65 64 20 74 68 65 20 65 6e 64 20 6f 66 ached the end of
1b60: 20 74 68 65 20 22 74 61 72 67 65 74 22 2e 20 0a the "target". .
1b70: 3c 2f 6c 69 3e 0a 3c 6c 69 3e 41 66 74 65 72 20 </li>.<li>After
1b80: 74 68 65 20 65 6d 69 73 73 69 6f 6e 20 6f 66 20 the emission of
1b90: 69 6e 73 74 72 75 63 74 69 6f 6e 73 20 74 68 65 instructions the
1ba0: 20 6e 65 77 20 22 62 61 73 65 22 20 6c 6f 63 61 new "base" loca
1bb0: 74 69 6f 6e 20 69 73 0a 77 69 74 68 69 6e 20 4e tion is.within N
1bc0: 48 41 53 48 20 62 79 74 65 73 20 6f 66 20 65 6e HASH bytes of en
1bd0: 64 20 6f 66 20 74 68 65 20 22 74 61 72 67 65 74 d of the "target
1be0: 22 2c 20 69 2e 65 2e 20 74 68 65 72 65 20 61 72 ", i.e. there ar
1bf0: 65 20 6e 6f 20 6d 6f 72 65 20 74 68 61 6e 0a 61 e no more than.a
1c00: 74 20 6d 6f 73 74 20 4e 48 41 53 48 20 62 79 74 t most NHASH byt
1c10: 65 73 20 6c 65 66 74 2e 0a 3c 2f 6c 69 3e 0a 3c es left..</li>.<
1c20: 2f 6f 6c 3e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 49 66 /ol>.</p>..<p>If
1c30: 20 74 68 65 20 70 72 6f 63 65 73 73 69 6e 67 20 the processing
1c40: 6c 6f 6f 70 20 6c 65 66 74 20 62 79 74 65 73 20 loop left bytes
1c50: 75 6e 65 6e 63 6f 64 65 64 2c 20 69 2e 65 2e 20 unencoded, i.e.
1c60: 22 62 61 73 65 22 20 6e 6f 74 0a 65 78 61 63 74 "base" not.exact
1c70: 6c 79 20 61 74 20 74 68 65 20 65 6e 64 20 6f 66 ly at the end of
1c80: 20 74 68 65 20 22 74 61 72 67 65 74 22 2c 20 61 the "target", a
1c90: 73 20 69 73 20 70 6f 73 73 69 62 6c 65 20 66 6f s is possible fo
1ca0: 72 20 62 6f 74 68 20 65 6e 64 0a 63 6f 6e 64 69 r both end.condi
1cb0: 74 69 6f 6e 73 2c 20 74 68 65 6e 20 6f 6e 65 20 tions, then one
1cc0: 6c 61 73 74 20 69 6e 73 65 72 74 20 69 6e 73 74 last insert inst
1cd0: 72 75 63 74 69 6f 6e 20 69 73 20 65 6d 69 74 74 ruction is emitt
1ce0: 65 64 20 74 6f 20 70 75 74 20 74 68 65 73 65 0a ed to put these.
1cf0: 62 79 74 65 73 20 69 6e 74 6f 20 74 68 65 20 64 bytes into the d
1d00: 65 6c 74 61 2e 3c 70 3e 0a 0a 3c 61 20 6e 61 6d elta.<p>..<a nam
1d10: 65 3d 22 65 78 63 65 70 74 69 6f 6e 73 22 3e 3c e="exceptions"><
1d20: 2f 61 3e 3c 68 32 3e 33 2e 30 20 45 78 63 65 70 /a><h2>3.0 Excep
1d30: 74 69 6f 6e 73 3c 2f 68 32 3e 0a 0a 3c 70 3e 49 tions</h2>..<p>I
1d40: 66 20 74 68 65 20 22 6f 72 69 67 69 6e 61 6c 22 f the "original"
1d50: 20 69 73 20 61 74 20 6d 6f 73 74 20 4e 48 41 53 is at most NHAS
1d60: 48 20 62 79 74 65 73 20 6c 6f 6e 67 20 6e 6f 20 H bytes long no
1d70: 63 6f 6d 70 72 65 73 73 69 6f 6e 20 6f 66 0a 63 compression of.c
1d80: 68 61 6e 67 65 73 20 69 73 20 70 6f 73 73 69 62 hanges is possib
1d90: 6c 65 2c 20 61 6e 64 20 74 68 65 20 73 65 67 6d le, and the segm
1da0: 65 6e 74 2d 6c 69 73 74 20 6f 66 20 74 68 65 20 ent-list of the
1db0: 64 65 6c 74 61 20 63 6f 6e 73 69 73 74 73 20 6f delta consists o
1dc0: 66 20 61 0a 73 69 6e 67 6c 65 20 6c 69 74 65 72 f a.single liter
1dd0: 61 6c 20 77 68 69 63 68 20 63 6f 6e 74 61 69 6e al which contain
1de0: 73 20 74 68 65 20 65 6e 74 69 72 65 20 22 74 61 s the entire "ta
1df0: 72 67 65 74 22 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 rget".</p>..<p>T
1e00: 68 69 73 20 69 73 20 61 63 74 75 61 6c 6c 79 20 his is actually
1e10: 65 71 75 69 76 61 6c 65 6e 74 20 74 6f 20 74 68 equivalent to th
1e20: 65 20 73 65 63 6f 6e 64 20 65 6e 64 20 63 6f 6e e second end con
1e30: 64 69 74 69 6f 6e 20 6f 66 20 74 68 65 0a 70 72 dition of the.pr
1e40: 6f 63 65 73 73 69 6e 67 20 6c 6f 6f 70 20 64 65 ocessing loop de
1e50: 73 63 72 69 62 65 64 20 69 6e 20 74 68 65 20 70 scribed in the p
1e60: 72 65 76 69 6f 75 73 20 73 65 63 74 69 6f 6e 2c revious section,
1e70: 20 6a 75 73 74 20 63 68 65 63 6b 65 64 20 62 65 just checked be
1e80: 66 6f 72 65 0a 61 63 74 75 61 6c 6c 79 20 65 6e fore.actually en
1e90: 74 65 72 69 6e 67 20 74 68 65 20 6c 6f 6f 70 2e tering the loop.
1ea0: 3c 2f 70 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 72 </p>..<a name="r
1eb0: 6f 6c 6c 68 61 73 68 22 3e 3c 2f 61 3e 3c 68 32 ollhash"></a><h2
1ec0: 3e 34 2e 30 20 54 68 65 20 72 6f 6c 6c 69 6e 67 >4.0 The rolling
1ed0: 20 68 61 73 68 3c 2f 68 32 3e 0a 0a 3c 70 3e 54 hash</h2>..<p>T
1ee0: 68 65 20 72 6f 6c 6c 69 6e 67 20 68 61 73 68 20 he rolling hash
1ef0: 64 65 73 63 72 69 62 65 64 20 62 65 6c 6f 77 20 described below
1f00: 61 6e 64 20 75 73 65 64 20 74 6f 20 63 6f 6d 70 and used to comp
1f10: 75 74 65 20 63 6f 6e 74 65 6e 74 0a 73 69 67 6e ute content.sign
1f20: 61 74 75 72 65 73 20 77 61 73 20 63 68 6f 73 65 atures was chose
1f30: 6e 20 6e 6f 74 20 6f 6e 6c 79 20 66 6f 72 20 67 n not only for g
1f40: 6f 6f 64 20 68 61 73 68 69 6e 67 20 70 72 6f 70 ood hashing prop
1f50: 65 72 74 69 65 73 2c 20 62 75 74 20 61 6c 73 6f erties, but also
1f60: 0a 74 6f 20 65 6e 61 62 6c 65 20 74 68 65 20 65 .to enable the e
1f70: 61 73 79 20 28 69 6e 63 72 65 6d 65 6e 74 61 6c asy (incremental
1f80: 29 20 72 65 63 61 6c 63 75 6c 61 74 69 6f 6e 20 ) recalculation
1f90: 6f 66 20 69 74 73 20 76 61 6c 75 65 20 66 6f 72 of its value for
1fa0: 20 61 0a 73 6c 69 64 69 6e 67 20 77 69 6e 64 6f a.sliding windo
1fb0: 77 2c 20 69 2e 65 2e 20 77 68 65 72 65 20 74 68 w, i.e. where th
1fc0: 65 20 6f 6c 64 65 73 74 20 62 79 74 65 20 69 73 e oldest byte is
1fd0: 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 removed from th
1fe0: 65 20 77 69 6e 64 6f 77 0a 61 6e 64 20 61 20 6e e window.and a n
1ff0: 65 77 20 62 79 74 65 20 69 73 20 73 68 69 66 74 ew byte is shift
2000: 65 64 20 69 6e 2e 3c 70 3e 0a 0a 3c 61 20 6e 61 ed in.<p>..<a na
2010: 6d 65 3d 22 72 68 64 65 66 22 3e 3c 2f 61 3e 3c me="rhdef"></a><
2020: 68 33 3e 34 2e 31 20 44 65 66 69 6e 69 74 69 6f h3>4.1 Definitio
2030: 6e 3c 2f 68 33 3e 0a 0a 3c 70 3e 41 73 73 75 6d n</h3>..<p>Assum
2040: 69 6e 67 20 61 6e 20 61 72 72 61 79 20 5a 20 6f ing an array Z o
2050: 66 20 4e 48 41 53 48 20 62 79 74 65 73 20 28 69 f NHASH bytes (i
2060: 6e 64 65 78 69 6e 67 20 73 74 61 72 74 69 6e 67 ndexing starting
2070: 20 61 74 20 30 29 20 74 68 65 0a 68 61 73 68 20 at 0) the.hash
2080: 56 20 69 73 20 63 6f 6d 70 75 74 65 64 20 76 69 V is computed vi
2090: 61 3c 2f 70 3e 0a 0a 3c 70 20 61 6c 69 67 6e 3d a</p>..<p align=
20a0: 63 65 6e 74 65 72 3e 3c 74 61 62 6c 65 3e 3c 74 center><table><t
20b0: 72 3e 3c 74 64 3e 0a 3c 70 3e 3c 69 6d 67 20 73 r><td>.<p><img s
20c0: 72 63 3d 22 65 6e 63 6f 64 65 31 2e 67 69 66 22 rc="encode1.gif"
20d0: 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e align="center">
20e0: 3c 2f 70 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 </p>.<p><img src
20f0: 3d 22 65 6e 63 6f 64 65 32 2e 67 69 66 22 20 61 ="encode2.gif" a
2100: 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f lign="center"></
2110: 70 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 p>.<p><img src="
2120: 65 6e 63 6f 64 65 33 2e 67 69 66 22 20 61 6c 69 encode3.gif" ali
2130: 67 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e gn="center"></p>
2140: 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 .</td></tr></tab
2150: 6c 65 3e 3c 2f 70 3e 0a 0a 77 68 65 72 65 20 41 le></p>..where A
2160: 20 61 6e 64 20 42 20 61 72 65 20 75 6e 73 69 67 and B are unsig
2170: 6e 65 64 20 31 36 2d 62 69 74 20 69 6e 74 65 67 ned 16-bit integ
2180: 65 72 73 20 28 68 65 6e 63 65 20 74 68 65 20 3c ers (hence the <
2190: 75 3e 6d 6f 64 3c 2f 75 3e 29 2c 20 61 6e 64 0a u>mod</u>), and.
21a0: 56 20 69 73 20 61 20 33 32 2d 62 69 74 20 75 6e V is a 32-bit un
21b0: 73 69 67 6e 65 64 20 69 6e 74 65 67 65 72 20 77 signed integer w
21c0: 69 74 68 20 42 20 61 73 20 4d 53 42 2c 20 41 20 ith B as MSB, A
21d0: 61 73 20 4c 53 42 2e 0a 0a 3c 61 20 6e 61 6d 65 as LSB...<a name
21e0: 3d 22 72 68 69 6e 63 72 22 3e 3c 2f 61 3e 3c 68 ="rhincr"></a><h
21f0: 33 3e 34 2e 32 20 49 6e 63 72 65 6d 65 6e 74 61 3>4.2 Incrementa
2200: 6c 20 72 65 63 61 6c 63 75 6c 61 74 69 6f 6e 3c l recalculation<
2210: 2f 68 33 3e 0a 0a 3c 70 3e 41 73 73 75 6d 69 6e /h3>..<p>Assumin
2220: 67 20 61 6e 20 61 72 72 61 79 20 5a 20 6f 66 20 g an array Z of
2230: 4e 48 41 53 48 20 62 79 74 65 73 20 28 69 6e 64 NHASH bytes (ind
2240: 65 78 69 6e 67 20 73 74 61 72 74 69 6e 67 20 61 exing starting a
2250: 74 20 30 29 20 77 69 74 68 0a 68 61 73 68 20 56 t 0) with.hash V
2260: 20 28 61 6e 64 20 63 6f 6d 70 6f 6e 65 6e 74 73 (and components
2270: 20 41 20 61 6e 64 20 42 29 2c 20 74 68 65 20 64 A and B), the d
2280: 72 6f 70 70 65 64 0a 62 79 74 65 20 3c 69 6d 67 ropped.byte <img
2290: 20 73 72 63 3d 22 65 6e 63 6f 64 65 34 2e 67 69 src="encode4.gi
22a0: 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 f" align="center
22b0: 22 3e 2c 20 61 6e 64 20 74 68 65 20 6e 65 77 20 ">, and the new
22c0: 62 79 74 65 0a 3c 69 6d 67 20 73 72 63 3d 22 65 byte.<img src="e
22d0: 6e 63 6f 64 65 35 2e 67 69 66 22 20 61 6c 69 67 ncode5.gif" alig
22e0: 6e 3d 22 63 65 6e 74 65 72 22 3e 20 2c 20 74 68 n="center"> , th
22f0: 65 20 6e 65 77 20 68 61 73 68 20 63 61 6e 0a 62 e new hash can.b
2300: 65 20 63 6f 6d 70 75 74 65 64 20 69 6e 63 72 65 e computed incre
2310: 6d 65 6e 74 61 6c 6c 79 20 76 69 61 3a 20 3c 2f mentally via: </
2320: 70 3e 0a 0a 3c 70 20 61 6c 69 67 6e 3d 63 65 6e p>..<p align=cen
2330: 74 65 72 3e 3c 74 61 62 6c 65 3e 3c 74 72 3e 3c ter><table><tr><
2340: 74 64 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 3d td>.<p><img src=
2350: 22 65 6e 63 6f 64 65 36 2e 67 69 66 22 20 61 6c "encode6.gif" al
2360: 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f 70 ign="center"></p
2370: 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 65 >.<p><img src="e
2380: 6e 63 6f 64 65 37 2e 67 69 66 22 20 61 6c 69 67 ncode7.gif" alig
2390: 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a n="center"></p>.
23a0: 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 <p><img src="enc
23b0: 6f 64 65 38 2e 67 69 66 22 20 61 6c 69 67 6e 3d ode8.gif" align=
23c0: 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e 0a 3c 2f "center"></p>.</
23d0: 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 6c 65 3e td></tr></table>
23e0: 3c 2f 70 3e 0a 0a 3c 70 3e 46 6f 72 20 41 2c 20 </p>..<p>For A,
23f0: 74 68 65 20 72 65 67 75 6c 61 72 20 73 75 6d 2c the regular sum,
2400: 20 69 74 20 63 61 6e 20 62 65 20 73 65 65 6e 20 it can be seen
2410: 65 61 73 69 6c 79 20 74 68 61 74 20 74 68 69 73 easily that this
2420: 20 74 68 65 20 63 6f 72 72 65 63 74 0a 77 61 79 the correct.way
2430: 20 72 65 63 6f 6d 70 75 74 69 6e 67 20 74 68 61 recomputing tha
2440: 74 20 63 6f 6d 70 6f 6e 65 6e 74 2e 3c 2f 70 3e t component.</p>
2450: 0a 0a 3c 70 3e 46 6f 72 20 42 2c 20 74 68 65 20 ..<p>For B, the
2460: 77 65 69 67 68 74 65 64 20 73 75 6d 2c 20 6e 6f weighted sum, no
2470: 74 65 20 66 69 72 73 74 20 74 68 61 74 20 3c 69 te first that <i
2480: 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 34 2e mg src="encode4.
2490: 67 69 66 22 0a 61 6c 69 67 6e 3d 22 63 65 6e 74 gif".align="cent
24a0: 65 72 22 3e 20 68 61 73 20 74 68 65 20 77 65 69 er"> has the wei
24b0: 67 68 74 20 4e 48 41 53 48 20 69 6e 20 74 68 65 ght NHASH in the
24c0: 20 73 75 6d 2c 20 73 6f 20 74 68 61 74 20 69 73 sum, so that is
24d0: 20 77 68 61 74 20 68 61 73 0a 74 6f 20 62 65 20 what has.to be
24e0: 72 65 6d 6f 76 65 64 2e 20 54 68 65 6e 20 61 64 removed. Then ad
24f0: 64 69 6e 67 20 69 6e 20 3c 69 6d 67 20 73 72 63 ding in <img src
2500: 3d 22 65 6e 63 6f 64 65 39 2e 67 69 66 22 20 61 ="encode9.gif" a
2510: 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 0a 61 lign="center">.a
2520: 64 64 73 20 6f 6e 65 20 77 65 69 67 68 74 20 66 dds one weight f
2530: 61 63 74 6f 72 20 74 6f 20 61 6c 6c 20 74 68 65 actor to all the
2540: 20 6f 74 68 65 72 20 76 61 6c 75 65 73 20 6f 66 other values of
2550: 20 5a 2c 20 61 6e 64 20 61 74 20 6c 61 73 74 20 Z, and at last
2560: 61 64 64 73 0a 69 6e 20 3c 69 6d 67 20 73 72 63 adds.in <img src
2570: 3d 22 65 6e 63 6f 64 65 35 2e 67 69 66 22 20 61 ="encode5.gif" a
2580: 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 20 77 lign="center"> w
2590: 69 74 68 20 77 65 69 67 68 74 20 31 2c 20 61 6c ith weight 1, al
25a0: 73 6f 0a 67 65 6e 65 72 61 74 69 6e 67 20 74 68 so.generating th
25b0: 65 20 63 6f 72 72 65 63 74 20 6e 65 77 20 73 75 e correct new su
25c0: 6d 3c 2f 70 3e 0a m</p>.