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: 20 74 61 62 6c 65 20 69 73 20 66 69 6c 6c 65 64 table is filled
0d90: 2c 20 6d 61 70 70 69 6e 67 20 66 72 6f 6d 20 74 , mapping from t
0da0: 68 65 20 68 61 73 68 65 73 20 6f 66 20 74 68 65 he hashes of the
0db0: 20 63 68 75 6e 6b 73 20 74 6f 0a 74 68 65 20 6c chunks to.the l
0dc0: 69 73 74 20 6f 66 20 63 68 75 6e 6b 20 6c 6f 63 ist of chunk loc
0dd0: 61 74 69 6f 6e 73 20 68 61 76 69 6e 67 20 74 68 ations having th
0de0: 69 73 20 68 61 73 68 2e 0a 3c 2f 6c 69 3e 0a 3c is hash..</li>.<
0df0: 2f 6f 6c 3e 0a 0a 3c 61 20 6e 61 6d 65 3d 22 70 /ol>..<a name="p
0e00: 72 6f 63 65 73 73 69 6e 67 22 3e 3c 2f 61 3e 3c rocessing"></a><
0e10: 68 33 3e 32 2e 31 20 50 72 6f 63 65 73 73 69 6e h3>2.1 Processin
0e20: 67 20 74 68 65 20 74 61 72 67 65 74 3c 2f 68 33 g the target</h3
0e30: 3e 0a 0a 3c 70 3e 54 68 69 73 2c 20 74 68 65 20 >..<p>This, the
0e40: 6d 61 69 6e 20 70 68 61 73 65 20 6f 66 20 74 68 main phase of th
0e50: 65 20 65 6e 63 6f 64 65 72 2c 20 70 72 6f 63 65 e encoder, proce
0e60: 73 73 65 73 20 74 68 65 20 74 61 72 67 65 74 20 sses the target
0e70: 69 6e 20 61 20 6c 6f 6f 70 0a 66 72 6f 6d 20 62 in a loop.from b
0e80: 65 67 69 6e 6e 69 6e 67 20 74 6f 20 65 6e 64 2e eginning to end.
0e90: 20 54 68 65 20 73 74 61 74 65 20 6f 66 20 74 68 The state of th
0ea0: 65 20 65 6e 63 6f 64 65 72 20 69 73 20 63 61 70 e encoder is cap
0eb0: 74 75 72 65 64 20 62 79 20 74 77 6f 0a 6c 6f 63 tured by two.loc
0ec0: 61 74 69 6f 6e 73 2c 20 74 68 65 20 22 62 61 73 ations, the "bas
0ed0: 65 22 20 61 6e 64 20 74 68 65 20 22 73 6c 69 64 e" and the "slid
0ee0: 65 22 2e 20 22 62 61 73 65 22 20 70 6f 69 6e 74 e". "base" point
0ef0: 73 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 62 s to the first b
0f00: 79 74 65 0a 6f 66 20 74 68 65 20 74 61 72 67 65 yte.of the targe
0f10: 74 20 66 6f 72 20 77 68 69 63 68 20 6e 6f 20 64 t for which no d
0f20: 65 6c 74 61 20 6f 75 74 70 75 74 20 68 61 73 20 elta output has
0f30: 62 65 65 6e 20 67 65 6e 65 72 61 74 65 64 20 79 been generated y
0f40: 65 74 2c 20 61 6e 64 0a 22 73 6c 69 64 65 22 20 et, and."slide"
0f50: 69 73 20 74 68 65 20 6c 6f 63 61 74 69 6f 6e 20 is the location
0f60: 6f 66 20 74 68 65 20 77 69 6e 64 6f 77 20 75 73 of the window us
0f70: 65 64 20 74 6f 20 6c 6f 6f 6b 20 69 6e 20 74 68 ed to look in th
0f80: 65 20 22 6f 72 69 67 69 6e 22 20 66 6f 72 0a 63 e "origin" for.c
0f90: 6f 6d 6d 6f 6e 61 6c 69 74 69 65 73 2e 20 54 68 ommonalities. Th
0fa0: 69 73 20 77 69 6e 64 6f 77 20 69 73 20 4e 48 41 is window is NHA
0fb0: 53 48 20 62 79 74 65 73 20 6c 6f 6e 67 2e 3c 2f SH bytes long.</
0fc0: 70 3e 0a 0a 3c 70 3e 49 6e 69 74 69 61 6c 6c 79 p>..<p>Initially
0fd0: 20 62 6f 74 68 20 22 62 61 73 65 22 20 61 6e 64 both "base" and
0fe0: 20 22 73 6c 69 64 65 22 20 70 6f 69 6e 74 20 74 "slide" point t
0ff0: 6f 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 o the beginning
1000: 6f 66 20 74 68 65 0a 22 74 61 72 67 65 74 22 2e of the."target".
1010: 20 49 6e 20 65 61 63 68 20 69 74 65 72 61 74 69 In each iterati
1020: 6f 6e 20 6f 66 20 74 68 65 20 6c 6f 6f 70 20 74 on of the loop t
1030: 68 65 20 65 6e 63 6f 64 65 72 20 64 65 63 69 64 he encoder decid
1040: 65 73 20 77 68 65 74 68 65 72 20 74 6f 0a 3c 75 es whether to.<u
1050: 6c 3e 0a 3c 6c 69 3e 65 6d 69 74 20 61 20 73 69 l>.<li>emit a si
1060: 6e 67 6c 65 20 69 6e 73 74 72 75 63 74 69 6f 6e ngle instruction
1070: 0a 74 6f 20 3c 61 20 68 72 65 66 3d 22 64 65 6c .to <a href="del
1080: 74 61 5f 66 6f 72 6d 61 74 2e 77 69 6b 69 23 63 ta_format.wiki#c
1090: 6f 70 79 72 61 6e 67 65 22 3e 63 6f 70 79 20 61 opyrange">copy a
10a0: 20 72 61 6e 67 65 3c 2f 61 3e 2c 20 6f 72 0a 3c range</a>, or.<
10b0: 2f 6c 69 3e 0a 3c 6c 69 3e 65 6d 69 74 20 74 77 /li>.<li>emit tw
10c0: 6f 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 2c 20 o instructions,
10d0: 66 69 72 73 74 0a 74 6f 20 3c 61 20 68 72 65 66 first.to <a href
10e0: 3d 22 64 65 6c 74 61 5f 66 6f 72 6d 61 74 2e 77 ="delta_format.w
10f0: 69 6b 69 23 69 6e 73 65 72 74 6c 69 74 22 3e 69 iki#insertlit">i
1100: 6e 73 65 72 74 20 61 20 6c 69 74 65 72 61 6c 3c nsert a literal<
1110: 2f 61 3e 2c 20 74 68 65 6e 0a 74 6f 20 3c 61 20 /a>, then.to <a
1120: 68 72 65 66 3d 22 64 65 6c 74 61 5f 66 6f 72 6d href="delta_form
1130: 61 74 2e 77 69 6b 69 23 63 6f 70 79 72 61 6e 67 at.wiki#copyrang
1140: 65 22 3e 63 6f 70 79 20 61 20 72 61 6e 67 65 3c e">copy a range<
1150: 2f 61 3e 2c 20 6f 72 0a 3c 2f 6c 69 3e 0a 3c 6c /a>, or.</li>.<l
1160: 69 3e 6d 6f 76 65 20 74 68 65 20 77 69 6e 64 6f i>move the windo
1170: 77 20 66 6f 72 77 61 72 64 20 6f 6e 65 20 62 79 w forward one by
1180: 74 65 2e 0a 3c 2f 6c 69 3e 0a 3c 2f 75 6c 3e 0a te..</li>.</ul>.
1190: 3c 2f 70 3e 0a 0a 3c 69 6d 67 20 73 72 63 3d 22 </p>..<img src="
11a0: 65 6e 63 6f 64 65 31 30 2e 67 69 66 22 20 61 6c encode10.gif" al
11b0: 69 67 6e 3d 22 72 69 67 68 74 22 20 68 73 70 61 ign="right" hspa
11c0: 63 65 3d 22 31 30 22 3e 0a 3c 70 3e 54 6f 20 6d ce="10">.<p>To m
11d0: 61 6b 65 20 74 68 69 73 20 64 65 63 69 73 69 6f ake this decisio
11e0: 6e 20 74 68 65 20 65 6e 63 6f 64 65 72 20 66 69 n the encoder fi
11f0: 72 73 74 20 63 6f 6d 70 75 74 65 73 20 74 68 65 rst computes the
1200: 20 68 61 73 68 20 76 61 6c 75 65 20 66 6f 72 0a hash value for.
1210: 74 68 65 20 4e 48 41 53 48 20 62 79 74 65 73 20 the NHASH bytes
1220: 69 6e 20 74 68 65 20 77 69 6e 64 6f 77 20 61 6e in the window an
1230: 64 20 74 68 65 6e 20 6c 6f 6f 6b 73 20 61 74 20 d then looks at
1240: 61 6c 6c 20 74 68 65 20 6c 6f 63 61 74 69 6f 6e all the location
1250: 73 20 69 6e 0a 74 68 65 20 22 6f 72 69 67 69 6e s in.the "origin
1260: 22 20 77 68 69 63 68 20 68 61 76 65 20 74 68 65 " which have the
1270: 20 73 61 6d 65 20 73 69 67 6e 61 74 75 72 65 2e same signature.
1280: 20 54 68 69 73 20 70 61 72 74 20 75 73 65 73 20 This part uses
1290: 74 68 65 20 68 61 73 68 0a 74 61 62 6c 65 20 63 the hash.table c
12a0: 72 65 61 74 65 64 20 62 79 20 74 68 65 20 70 72 reated by the pr
12b0: 65 2d 70 72 6f 63 65 73 73 69 6e 67 20 73 74 65 e-processing ste
12c0: 70 20 74 6f 20 65 66 66 69 63 69 65 6e 74 6c 79 p to efficiently
12d0: 20 66 69 6e 64 20 74 68 65 73 65 0a 6c 6f 63 61 find these.loca
12e0: 74 69 6f 6e 73 2e 3c 2f 70 3e 0a 0a 3c 70 3e 46 tions.</p>..<p>F
12f0: 6f 72 20 65 61 63 68 20 6f 66 20 74 68 65 20 70 or each of the p
1300: 6f 73 73 69 62 6c 65 20 63 61 6e 64 69 64 61 74 ossible candidat
1310: 65 73 20 74 68 65 20 65 6e 63 6f 64 65 72 20 66 es the encoder f
1320: 69 6e 64 73 20 74 68 65 20 6d 61 78 69 6d 61 6c inds the maximal
1330: 0a 72 61 6e 67 65 20 6f 66 20 62 79 74 65 73 20 .range of bytes
1340: 63 6f 6d 6d 6f 6e 20 74 6f 20 62 6f 74 68 20 22 common to both "
1350: 6f 72 69 67 69 6e 22 20 61 6e 64 20 22 74 61 72 origin" and "tar
1360: 67 65 74 22 2c 20 67 6f 69 6e 67 20 66 6f 72 77 get", going forw
1370: 61 72 64 20 61 6e 64 0a 62 61 63 6b 77 61 72 64 ard and.backward
1380: 20 66 72 6f 6d 20 22 73 6c 69 64 65 22 20 69 6e from "slide" in
1390: 20 74 68 65 20 22 74 61 72 67 65 74 22 2c 20 61 the "target", a
13a0: 6e 64 20 74 68 65 20 63 61 6e 64 69 64 61 74 65 nd the candidate
13b0: 20 6c 6f 63 61 74 69 6f 6e 20 69 6e 0a 74 68 65 location in.the
13c0: 20 22 6f 72 69 67 69 6e 22 2e 20 54 68 69 73 20 "origin". This
13d0: 73 65 61 72 63 68 20 69 73 20 63 6f 6e 73 74 72 search is constr
13e0: 61 69 6e 65 64 20 6f 6e 20 74 68 65 20 73 69 64 ained on the sid
13f0: 65 20 6f 66 20 74 68 65 20 22 74 61 72 67 65 74 e of the "target
1400: 22 0a 62 79 20 74 68 65 20 22 62 61 73 65 22 20 ".by the "base"
1410: 28 62 61 63 6b 77 61 72 64 20 73 65 61 72 63 68 (backward search
1420: 29 2c 20 61 6e 64 20 74 68 65 20 65 6e 64 20 6f ), and the end o
1430: 66 20 74 68 65 20 22 74 61 72 67 65 74 22 20 28 f the "target" (
1440: 66 6f 72 77 61 72 64 0a 73 65 61 72 63 68 29 2c forward.search),
1450: 20 61 6e 64 20 6f 6e 20 74 68 65 20 73 69 64 65 and on the side
1460: 20 6f 66 20 74 68 65 20 22 6f 72 69 67 69 6e 22 of the "origin"
1470: 20 62 79 20 74 68 65 20 62 65 67 69 6e 6e 69 6e by the beginnin
1480: 67 20 61 6e 64 20 65 6e 64 20 6f 66 0a 74 68 65 g and end of.the
1490: 20 22 6f 72 69 67 69 6e 22 2c 20 72 65 73 70 65 "origin", respe
14a0: 63 74 69 76 65 6c 79 2e 3c 2f 70 3e 0a 0a 3c 70 ctively.</p>..<p
14b0: 3e 54 68 65 72 65 20 61 72 65 20 69 6e 70 75 74 >There are input
14c0: 20 66 69 6c 65 73 20 66 6f 72 20 77 68 69 63 68 files for which
14d0: 20 74 68 65 20 68 61 73 68 20 63 68 61 69 6e 73 the hash chains
14e0: 20 67 65 6e 65 72 61 74 65 64 20 62 79 20 74 68 generated by th
14f0: 65 0a 70 72 65 2d 70 72 6f 63 65 73 73 69 6e 67 e.pre-processing
1500: 20 73 74 65 70 20 63 61 6e 20 62 65 63 6f 6d 65 step can become
1510: 20 76 65 72 79 20 6c 6f 6e 67 2c 20 6c 65 61 64 very long, lead
1520: 69 6e 67 20 74 6f 20 6c 6f 6e 67 20 73 65 61 72 ing to long sear
1530: 63 68 20 74 69 6d 65 73 0a 61 6e 64 20 61 66 66 ch times.and aff
1540: 65 63 74 69 6e 67 20 74 68 65 20 70 65 72 66 6f ecting the perfo
1550: 72 6d 61 6e 63 65 20 6f 66 20 74 68 65 20 64 65 rmance of the de
1560: 6c 74 61 20 67 65 6e 65 72 61 74 6f 72 2e 20 54 lta generator. T
1570: 6f 20 6c 69 6d 69 74 20 74 68 65 0a 65 66 66 65 o limit the.effe
1580: 63 74 20 73 75 63 68 20 6c 6f 6e 67 20 63 68 61 ct such long cha
1590: 69 6e 73 20 63 61 6e 20 68 61 76 65 20 74 68 65 ins can have the
15a0: 20 61 63 74 75 61 6c 20 73 65 61 72 63 68 20 66 actual search f
15b0: 6f 72 20 63 61 6e 64 69 64 61 74 65 73 20 69 73 or candidates is
15c0: 0a 62 6f 75 6e 64 65 64 2c 20 6c 6f 6f 6b 69 6e .bounded, lookin
15d0: 67 20 61 74 20 6d 6f 73 74 20 4e 20 63 61 6e 64 g at most N cand
15e0: 69 64 61 74 65 73 2e 20 43 75 72 72 65 6e 74 6c idates. Currentl
15f0: 79 20 4e 20 69 73 20 73 65 74 20 74 6f 20 32 35 y N is set to 25
1600: 30 2e 3c 2f 70 3e 0a 0a 3c 70 3e 46 72 6f 6d 20 0.</p>..<p>From
1610: 74 68 65 20 72 61 6e 67 65 73 20 66 6f 72 20 61 the ranges for a
1620: 6c 6c 20 74 68 65 20 63 61 6e 64 69 64 61 74 65 ll the candidate
1630: 73 20 74 68 65 20 62 65 73 74 20 28 3d 20 6c 61 s the best (= la
1640: 72 67 65 73 74 29 20 63 6f 6d 6d 6f 6e 0a 72 61 rgest) common.ra
1650: 6e 67 65 20 69 73 20 74 61 6b 65 6e 20 61 6e 64 nge is taken and
1660: 20 69 74 20 69 73 20 64 65 74 65 72 6d 69 6e 65 it is determine
1670: 64 20 68 6f 77 20 6d 61 6e 79 20 62 79 74 65 73 d how many bytes
1680: 20 61 72 65 20 6e 65 65 64 65 64 20 74 6f 0a 65 are needed to.e
1690: 6e 63 6f 64 65 20 74 68 65 20 62 79 74 65 73 20 ncode the bytes
16a0: 62 65 74 77 65 65 6e 20 74 68 65 20 22 62 61 73 between the "bas
16b0: 65 22 20 61 6e 64 20 74 68 65 20 65 6e 64 20 6f e" and the end o
16c0: 66 20 74 68 61 74 20 72 61 6e 67 65 2e 20 49 66 f that range. If
16d0: 20 74 68 65 0a 72 61 6e 67 65 20 65 78 74 65 6e the.range exten
16e0: 64 65 64 20 62 61 63 6b 20 74 6f 20 74 68 65 20 ded back to the
16f0: 22 62 61 73 65 22 20 74 68 65 6e 20 74 68 69 73 "base" then this
1700: 20 63 61 6e 20 62 65 20 64 6f 6e 65 20 69 6e 20 can be done in
1710: 61 20 73 69 6e 67 6c 65 0a 63 6f 70 79 20 69 6e a single.copy in
1720: 73 74 72 75 63 74 69 6f 6e 2e 20 4f 74 68 65 72 struction. Other
1730: 77 69 73 65 2c 20 69 2e 65 20 69 66 20 74 68 65 wise, i.e if the
1740: 72 65 20 69 73 20 61 20 67 61 70 20 62 65 74 77 re is a gap betw
1750: 65 65 6e 20 74 68 65 20 22 62 61 73 65 22 0a 61 een the "base".a
1760: 6e 64 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 nd the beginning
1770: 20 6f 66 20 74 68 65 20 72 61 6e 67 65 20 74 68 of the range th
1780: 65 6e 20 74 77 6f 20 69 6e 73 74 72 75 63 74 69 en two instructi
1790: 6f 6e 73 20 61 72 65 20 6e 65 65 64 65 64 2c 20 ons are needed,
17a0: 6f 6e 65 0a 74 6f 20 69 6e 73 65 72 74 20 74 68 one.to insert th
17b0: 65 20 62 79 74 65 73 20 69 6e 20 74 68 65 20 67 e bytes in the g
17c0: 61 70 20 61 73 20 61 20 6c 69 74 65 72 61 6c 2c ap as a literal,
17d0: 20 61 6e 64 20 61 20 63 6f 70 79 20 69 6e 73 74 and a copy inst
17e0: 72 75 63 74 69 6f 6e 0a 66 6f 72 20 74 68 65 20 ruction.for the
17f0: 72 61 6e 67 65 20 69 74 73 65 6c 66 2e 20 54 68 range itself. Th
1800: 65 20 67 65 6e 65 72 61 6c 20 73 69 74 75 61 74 e general situat
1810: 69 6f 6e 20 61 74 20 74 68 69 73 20 70 6f 69 6e ion at this poin
1820: 74 20 63 61 6e 20 62 65 20 73 65 65 6e 0a 69 6e t can be seen.in
1830: 20 74 68 65 20 70 69 63 74 75 72 65 20 74 6f 20 the picture to
1840: 74 68 65 20 72 69 67 68 74 2e 3c 2f 70 3e 0a 0a the right.</p>..
1850: 3c 70 3e 49 66 20 74 68 65 20 6e 75 6d 62 65 72 <p>If the number
1860: 20 6f 66 20 62 79 74 65 73 20 6e 65 65 64 65 64 of bytes needed
1870: 20 74 6f 20 65 6e 63 6f 64 65 20 62 6f 74 68 20 to encode both
1880: 67 61 70 20 28 69 66 20 70 72 65 73 65 6e 74 29 gap (if present)
1890: 2c 20 61 6e 64 0a 72 61 6e 67 65 20 69 73 20 6c , and.range is l
18a0: 65 73 73 20 74 68 61 6e 20 74 68 65 20 6e 75 6d ess than the num
18b0: 62 65 72 20 6f 66 20 62 79 74 65 73 20 77 65 20 ber of bytes we
18c0: 61 72 65 20 65 6e 63 6f 64 69 6e 67 20 74 68 65 are encoding the
18d0: 20 65 6e 63 6f 64 65 72 0a 77 69 6c 6c 20 65 6d encoder.will em
18e0: 69 74 20 74 68 65 20 6e 65 63 65 73 73 61 72 79 it the necessary
18f0: 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 20 61 73 instructions as
1900: 20 64 65 73 63 72 69 62 65 64 20 61 62 6f 76 65 described above
1910: 2c 20 73 65 74 20 22 62 61 73 65 22 0a 61 6e 64 , set "base".and
1920: 20 22 73 6c 69 64 65 22 20 74 6f 20 74 68 65 20 "slide" to the
1930: 65 6e 64 20 6f 66 20 74 68 65 20 65 6e 63 6f 64 end of the encod
1940: 65 64 20 72 61 6e 67 65 20 61 6e 64 20 73 74 61 ed range and sta
1950: 72 74 20 74 68 65 20 6e 65 78 74 0a 69 74 65 72 rt the next.iter
1960: 61 74 69 6f 6e 20 61 74 20 74 68 61 74 20 70 6f ation at that po
1970: 69 6e 74 2e 3c 2f 70 3e 0a 0a 3c 70 3e 49 66 2c int.</p>..<p>If,
1980: 20 6f 6e 20 74 68 65 20 6f 74 68 65 72 20 68 61 on the other ha
1990: 6e 64 2c 20 74 68 65 20 65 6e 63 6f 64 65 72 20 nd, the encoder
19a0: 65 69 74 68 65 72 20 64 69 64 20 6e 6f 74 20 66 either did not f
19b0: 69 6e 64 20 63 61 6e 64 69 64 61 74 65 0a 6c 6f ind candidate.lo
19c0: 63 61 74 69 6f 6e 73 20 69 6e 20 74 68 65 20 6f cations in the o
19d0: 72 69 67 69 6e 2c 20 6f 72 20 74 68 65 20 62 65 rigin, or the be
19e0: 73 74 20 72 61 6e 67 65 20 63 6f 6d 69 6e 67 20 st range coming
19f0: 6f 75 74 20 6f 66 20 74 68 65 20 73 65 61 72 63 out of the searc
1a00: 68 0a 6e 65 65 64 65 64 20 6d 6f 72 65 20 62 79 h.needed more by
1a10: 74 65 73 20 74 6f 20 65 6e 63 6f 64 65 20 74 68 tes to encode th
1a20: 65 20 72 61 6e 67 65 20 74 68 61 6e 20 74 68 65 e range than the
1a30: 72 65 20 77 65 72 65 20 62 79 74 65 73 20 69 6e re were bytes in
1a40: 20 74 68 65 0a 72 61 6e 67 65 2c 20 74 68 65 6e the.range, then
1a50: 20 6e 6f 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 no instructions
1a60: 20 61 72 65 20 65 6d 69 74 74 65 64 20 61 6e 64 are emitted and
1a70: 20 74 68 65 20 77 69 6e 64 6f 77 20 69 73 20 6d the window is m
1a80: 6f 76 65 64 20 6f 6e 65 0a 62 79 74 65 20 66 6f oved one.byte fo
1a90: 72 77 61 72 64 2e 20 54 68 65 20 22 62 61 73 65 rward. The "base
1aa0: 22 20 69 73 20 6c 65 66 74 20 75 6e 63 68 61 6e " is left unchan
1ab0: 67 65 64 20 69 6e 20 74 68 61 74 20 63 61 73 65 ged in that case
1ac0: 2e 3c 2f 70 3e 0a 0a 3c 70 3e 54 68 65 20 70 72 .</p>..<p>The pr
1ad0: 6f 63 65 73 73 69 6e 67 20 6c 6f 6f 70 20 73 74 ocessing loop st
1ae0: 6f 70 73 20 61 74 20 6f 6e 65 20 6f 66 20 74 77 ops at one of tw
1af0: 6f 20 63 6f 6e 64 69 74 69 6f 6e 73 3a 0a 3c 6f o conditions:.<o
1b00: 6c 3e 0a 3c 6c 69 3e 54 68 65 20 65 6e 63 6f 64 l>.<li>The encod
1b10: 65 72 20 64 65 63 69 64 65 64 20 74 6f 20 6d 6f er decided to mo
1b20: 76 65 20 74 68 65 20 77 69 6e 64 6f 77 20 66 6f ve the window fo
1b30: 72 77 61 72 64 2c 20 62 75 74 20 74 68 65 20 65 rward, but the e
1b40: 6e 64 20 6f 66 20 74 68 65 0a 77 69 6e 64 6f 77 nd of the.window
1b50: 20 72 65 61 63 68 65 64 20 74 68 65 20 65 6e 64 reached the end
1b60: 20 6f 66 20 74 68 65 20 22 74 61 72 67 65 74 22 of the "target"
1b70: 2e 20 0a 3c 2f 6c 69 3e 0a 3c 6c 69 3e 41 66 74 . .</li>.<li>Aft
1b80: 65 72 20 74 68 65 20 65 6d 69 73 73 69 6f 6e 20 er the emission
1b90: 6f 66 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 20 of instructions
1ba0: 74 68 65 20 6e 65 77 20 22 62 61 73 65 22 20 6c the new "base" l
1bb0: 6f 63 61 74 69 6f 6e 20 69 73 0a 77 69 74 68 69 ocation is.withi
1bc0: 6e 20 4e 48 41 53 48 20 62 79 74 65 73 20 6f 66 n NHASH bytes of
1bd0: 20 65 6e 64 20 6f 66 20 74 68 65 20 22 74 61 72 end of the "tar
1be0: 67 65 74 22 2c 20 69 2e 65 2e 20 74 68 65 72 65 get", i.e. there
1bf0: 20 61 72 65 20 6e 6f 20 6d 6f 72 65 20 74 68 61 are no more tha
1c00: 6e 0a 61 74 20 6d 6f 73 74 20 4e 48 41 53 48 20 n.at most NHASH
1c10: 62 79 74 65 73 20 6c 65 66 74 2e 0a 3c 2f 6c 69 bytes left..</li
1c20: 3e 0a 3c 2f 6f 6c 3e 0a 3c 2f 70 3e 0a 0a 3c 70 >.</ol>.</p>..<p
1c30: 3e 49 66 20 74 68 65 20 70 72 6f 63 65 73 73 69 >If the processi
1c40: 6e 67 20 6c 6f 6f 70 20 6c 65 66 74 20 62 79 74 ng loop left byt
1c50: 65 73 20 75 6e 65 6e 63 6f 64 65 64 2c 20 69 2e es unencoded, i.
1c60: 65 2e 20 22 62 61 73 65 22 20 6e 6f 74 0a 65 78 e. "base" not.ex
1c70: 61 63 74 6c 79 20 61 74 20 74 68 65 20 65 6e 64 actly at the end
1c80: 20 6f 66 20 74 68 65 20 22 74 61 72 67 65 74 22 of the "target"
1c90: 2c 20 61 73 20 69 73 20 70 6f 73 73 69 62 6c 65 , as is possible
1ca0: 20 66 6f 72 20 62 6f 74 68 20 65 6e 64 0a 63 6f for both end.co
1cb0: 6e 64 69 74 69 6f 6e 73 2c 20 74 68 65 6e 20 6f nditions, then o
1cc0: 6e 65 20 6c 61 73 74 20 69 6e 73 65 72 74 20 69 ne last insert i
1cd0: 6e 73 74 72 75 63 74 69 6f 6e 20 69 73 20 65 6d nstruction is em
1ce0: 69 74 74 65 64 20 74 6f 20 70 75 74 20 74 68 65 itted to put the
1cf0: 73 65 0a 62 79 74 65 73 20 69 6e 74 6f 20 74 68 se.bytes into th
1d00: 65 20 64 65 6c 74 61 2e 3c 70 3e 0a 0a 3c 61 20 e delta.<p>..<a
1d10: 6e 61 6d 65 3d 22 65 78 63 65 70 74 69 6f 6e 73 name="exceptions
1d20: 22 3e 3c 2f 61 3e 3c 68 32 3e 33 2e 30 20 45 78 "></a><h2>3.0 Ex
1d30: 63 65 70 74 69 6f 6e 73 3c 2f 68 32 3e 0a 0a 3c ceptions</h2>..<
1d40: 70 3e 49 66 20 74 68 65 20 22 6f 72 69 67 69 6e p>If the "origin
1d50: 61 6c 22 20 69 73 20 61 74 20 6d 6f 73 74 20 4e al" is at most N
1d60: 48 41 53 48 20 62 79 74 65 73 20 6c 6f 6e 67 20 HASH bytes long
1d70: 6e 6f 20 63 6f 6d 70 72 65 73 73 69 6f 6e 20 6f no compression o
1d80: 66 0a 63 68 61 6e 67 65 73 20 69 73 20 70 6f 73 f.changes is pos
1d90: 73 69 62 6c 65 2c 20 61 6e 64 20 74 68 65 20 73 sible, and the s
1da0: 65 67 6d 65 6e 74 2d 6c 69 73 74 20 6f 66 20 74 egment-list of t
1db0: 68 65 20 64 65 6c 74 61 20 63 6f 6e 73 69 73 74 he delta consist
1dc0: 73 20 6f 66 20 61 0a 73 69 6e 67 6c 65 20 6c 69 s of a.single li
1dd0: 74 65 72 61 6c 20 77 68 69 63 68 20 63 6f 6e 74 teral which cont
1de0: 61 69 6e 73 20 74 68 65 20 65 6e 74 69 72 65 20 ains the entire
1df0: 22 74 61 72 67 65 74 22 2e 3c 2f 70 3e 0a 0a 3c "target".</p>..<
1e00: 70 3e 54 68 69 73 20 69 73 20 61 63 74 75 61 6c p>This is actual
1e10: 6c 79 20 65 71 75 69 76 61 6c 65 6e 74 20 74 6f ly equivalent to
1e20: 20 74 68 65 20 73 65 63 6f 6e 64 20 65 6e 64 20 the second end
1e30: 63 6f 6e 64 69 74 69 6f 6e 20 6f 66 20 74 68 65 condition of the
1e40: 0a 70 72 6f 63 65 73 73 69 6e 67 20 6c 6f 6f 70 .processing loop
1e50: 20 64 65 73 63 72 69 62 65 64 20 69 6e 20 74 68 described in th
1e60: 65 20 70 72 65 76 69 6f 75 73 20 73 65 63 74 69 e previous secti
1e70: 6f 6e 2c 20 6a 75 73 74 20 63 68 65 63 6b 65 64 on, just checked
1e80: 20 62 65 66 6f 72 65 0a 61 63 74 75 61 6c 6c 79 before.actually
1e90: 20 65 6e 74 65 72 69 6e 67 20 74 68 65 20 6c 6f entering the lo
1ea0: 6f 70 2e 3c 2f 70 3e 0a 0a 3c 61 20 6e 61 6d 65 op.</p>..<a name
1eb0: 3d 22 72 6f 6c 6c 68 61 73 68 22 3e 3c 2f 61 3e ="rollhash"></a>
1ec0: 3c 68 32 3e 34 2e 30 20 54 68 65 20 72 6f 6c 6c <h2>4.0 The roll
1ed0: 69 6e 67 20 68 61 73 68 3c 2f 68 32 3e 0a 0a 3c ing hash</h2>..<
1ee0: 70 3e 54 68 65 20 72 6f 6c 6c 69 6e 67 20 68 61 p>The rolling ha
1ef0: 73 68 20 64 65 73 63 72 69 62 65 64 20 62 65 6c sh described bel
1f00: 6f 77 20 61 6e 64 20 75 73 65 64 20 74 6f 20 63 ow and used to c
1f10: 6f 6d 70 75 74 65 20 63 6f 6e 74 65 6e 74 0a 73 ompute content.s
1f20: 69 67 6e 61 74 75 72 65 73 20 77 61 73 20 63 68 ignatures was ch
1f30: 6f 73 65 6e 20 6e 6f 74 20 6f 6e 6c 79 20 66 6f osen not only fo
1f40: 72 20 67 6f 6f 64 20 68 61 73 68 69 6e 67 20 70 r good hashing p
1f50: 72 6f 70 65 72 74 69 65 73 2c 20 62 75 74 20 61 roperties, but a
1f60: 6c 73 6f 0a 74 6f 20 65 6e 61 62 6c 65 20 74 68 lso.to enable th
1f70: 65 20 65 61 73 79 20 28 69 6e 63 72 65 6d 65 6e e easy (incremen
1f80: 74 61 6c 29 20 72 65 63 61 6c 63 75 6c 61 74 69 tal) recalculati
1f90: 6f 6e 20 6f 66 20 69 74 73 20 76 61 6c 75 65 20 on of its value
1fa0: 66 6f 72 20 61 0a 73 6c 69 64 69 6e 67 20 77 69 for a.sliding wi
1fb0: 6e 64 6f 77 2c 20 69 2e 65 2e 20 77 68 65 72 65 ndow, i.e. where
1fc0: 20 74 68 65 20 6f 6c 64 65 73 74 20 62 79 74 65 the oldest byte
1fd0: 20 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d is removed from
1fe0: 20 74 68 65 20 77 69 6e 64 6f 77 0a 61 6e 64 20 the window.and
1ff0: 61 20 6e 65 77 20 62 79 74 65 20 69 73 20 73 68 a new byte is sh
2000: 69 66 74 65 64 20 69 6e 2e 3c 70 3e 0a 0a 3c 61 ifted in.<p>..<a
2010: 20 6e 61 6d 65 3d 22 72 68 64 65 66 22 3e 3c 2f name="rhdef"></
2020: 61 3e 3c 68 33 3e 34 2e 31 20 44 65 66 69 6e 69 a><h3>4.1 Defini
2030: 74 69 6f 6e 3c 2f 68 33 3e 0a 0a 3c 70 3e 41 73 tion</h3>..<p>As
2040: 73 75 6d 69 6e 67 20 61 6e 20 61 72 72 61 79 20 suming an array
2050: 5a 20 6f 66 20 4e 48 41 53 48 20 62 79 74 65 73 Z of NHASH bytes
2060: 20 28 69 6e 64 65 78 69 6e 67 20 73 74 61 72 74 (indexing start
2070: 69 6e 67 20 61 74 20 30 29 20 74 68 65 0a 68 61 ing at 0) the.ha
2080: 73 68 20 56 20 69 73 20 63 6f 6d 70 75 74 65 64 sh V is computed
2090: 20 76 69 61 3c 2f 70 3e 0a 0a 3c 70 20 61 6c 69 via</p>..<p ali
20a0: 67 6e 3d 63 65 6e 74 65 72 3e 3c 74 61 62 6c 65 gn=center><table
20b0: 3e 3c 74 72 3e 3c 74 64 3e 0a 3c 70 3e 3c 69 6d ><tr><td>.<p><im
20c0: 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 31 2e 67 g src="encode1.g
20d0: 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 if" align="cente
20e0: 72 22 3e 3c 2f 70 3e 0a 3c 70 3e 3c 69 6d 67 20 r"></p>.<p><img
20f0: 73 72 63 3d 22 65 6e 63 6f 64 65 32 2e 67 69 66 src="encode2.gif
2100: 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 " align="center"
2110: 3e 3c 2f 70 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 ></p>.<p><img sr
2120: 63 3d 22 65 6e 63 6f 64 65 33 2e 67 69 66 22 20 c="encode3.gif"
2130: 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 3c align="center"><
2140: 2f 70 3e 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f /p>.</td></tr></
2150: 74 61 62 6c 65 3e 3c 2f 70 3e 0a 0a 77 68 65 72 table></p>..wher
2160: 65 20 41 20 61 6e 64 20 42 20 61 72 65 20 75 6e e A and B are un
2170: 73 69 67 6e 65 64 20 31 36 2d 62 69 74 20 69 6e signed 16-bit in
2180: 74 65 67 65 72 73 20 28 68 65 6e 63 65 20 74 68 tegers (hence th
2190: 65 20 3c 75 3e 6d 6f 64 3c 2f 75 3e 29 2c 20 61 e <u>mod</u>), a
21a0: 6e 64 0a 56 20 69 73 20 61 20 33 32 2d 62 69 74 nd.V is a 32-bit
21b0: 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 65 67 65 unsigned intege
21c0: 72 20 77 69 74 68 20 42 20 61 73 20 4d 53 42 2c r with B as MSB,
21d0: 20 41 20 61 73 20 4c 53 42 2e 0a 0a 3c 61 20 6e A as LSB...<a n
21e0: 61 6d 65 3d 22 72 68 69 6e 63 72 22 3e 3c 2f 61 ame="rhincr"></a
21f0: 3e 3c 68 33 3e 34 2e 32 20 49 6e 63 72 65 6d 65 ><h3>4.2 Increme
2200: 6e 74 61 6c 20 72 65 63 61 6c 63 75 6c 61 74 69 ntal recalculati
2210: 6f 6e 3c 2f 68 33 3e 0a 0a 3c 70 3e 41 73 73 75 on</h3>..<p>Assu
2220: 6d 69 6e 67 20 61 6e 20 61 72 72 61 79 20 5a 20 ming an array Z
2230: 6f 66 20 4e 48 41 53 48 20 62 79 74 65 73 20 28 of NHASH bytes (
2240: 69 6e 64 65 78 69 6e 67 20 73 74 61 72 74 69 6e indexing startin
2250: 67 20 61 74 20 30 29 20 77 69 74 68 0a 68 61 73 g at 0) with.has
2260: 68 20 56 20 28 61 6e 64 20 63 6f 6d 70 6f 6e 65 h V (and compone
2270: 6e 74 73 20 41 20 61 6e 64 20 42 29 2c 20 74 68 nts A and B), th
2280: 65 20 64 72 6f 70 70 65 64 0a 62 79 74 65 20 3c e dropped.byte <
2290: 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 65 34 img src="encode4
22a0: 2e 67 69 66 22 20 61 6c 69 67 6e 3d 22 63 65 6e .gif" align="cen
22b0: 74 65 72 22 3e 2c 20 61 6e 64 20 74 68 65 20 6e ter">, and the n
22c0: 65 77 20 62 79 74 65 0a 3c 69 6d 67 20 73 72 63 ew byte.<img src
22d0: 3d 22 65 6e 63 6f 64 65 35 2e 67 69 66 22 20 61 ="encode5.gif" a
22e0: 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 20 2c lign="center"> ,
22f0: 20 74 68 65 20 6e 65 77 20 68 61 73 68 20 63 61 the new hash ca
2300: 6e 0a 62 65 20 63 6f 6d 70 75 74 65 64 20 69 6e n.be computed in
2310: 63 72 65 6d 65 6e 74 61 6c 6c 79 20 76 69 61 3a crementally via:
2320: 20 3c 2f 70 3e 0a 0a 3c 70 20 61 6c 69 67 6e 3d </p>..<p align=
2330: 63 65 6e 74 65 72 3e 3c 74 61 62 6c 65 3e 3c 74 center><table><t
2340: 72 3e 3c 74 64 3e 0a 3c 70 3e 3c 69 6d 67 20 73 r><td>.<p><img s
2350: 72 63 3d 22 65 6e 63 6f 64 65 36 2e 67 69 66 22 rc="encode6.gif"
2360: 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e align="center">
2370: 3c 2f 70 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 </p>.<p><img src
2380: 3d 22 65 6e 63 6f 64 65 37 2e 67 69 66 22 20 61 ="encode7.gif" a
2390: 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f lign="center"></
23a0: 70 3e 0a 3c 70 3e 3c 69 6d 67 20 73 72 63 3d 22 p>.<p><img src="
23b0: 65 6e 63 6f 64 65 38 2e 67 69 66 22 20 61 6c 69 encode8.gif" ali
23c0: 67 6e 3d 22 63 65 6e 74 65 72 22 3e 3c 2f 70 3e gn="center"></p>
23d0: 0a 3c 2f 74 64 3e 3c 2f 74 72 3e 3c 2f 74 61 62 .</td></tr></tab
23e0: 6c 65 3e 3c 2f 70 3e 0a 0a 3c 70 3e 46 6f 72 20 le></p>..<p>For
23f0: 41 2c 20 74 68 65 20 72 65 67 75 6c 61 72 20 73 A, the regular s
2400: 75 6d 2c 20 69 74 20 63 61 6e 20 62 65 20 73 65 um, it can be se
2410: 65 6e 20 65 61 73 69 6c 79 20 74 68 61 74 20 74 en easily that t
2420: 68 69 73 20 74 68 65 20 63 6f 72 72 65 63 74 0a his the correct.
2430: 77 61 79 20 72 65 63 6f 6d 70 75 74 69 6e 67 20 way recomputing
2440: 74 68 61 74 20 63 6f 6d 70 6f 6e 65 6e 74 2e 3c that component.<
2450: 2f 70 3e 0a 0a 3c 70 3e 46 6f 72 20 42 2c 20 74 /p>..<p>For B, t
2460: 68 65 20 77 65 69 67 68 74 65 64 20 73 75 6d 2c he weighted sum,
2470: 20 6e 6f 74 65 20 66 69 72 73 74 20 74 68 61 74 note first that
2480: 20 3c 69 6d 67 20 73 72 63 3d 22 65 6e 63 6f 64 <img src="encod
2490: 65 34 2e 67 69 66 22 0a 61 6c 69 67 6e 3d 22 63 e4.gif".align="c
24a0: 65 6e 74 65 72 22 3e 20 68 61 73 20 74 68 65 20 enter"> has the
24b0: 77 65 69 67 68 74 20 4e 48 41 53 48 20 69 6e 20 weight NHASH in
24c0: 74 68 65 20 73 75 6d 2c 20 73 6f 20 74 68 61 74 the sum, so that
24d0: 20 69 73 20 77 68 61 74 20 68 61 73 0a 74 6f 20 is what has.to
24e0: 62 65 20 72 65 6d 6f 76 65 64 2e 20 54 68 65 6e be removed. Then
24f0: 20 61 64 64 69 6e 67 20 69 6e 20 3c 69 6d 67 20 adding in <img
2500: 73 72 63 3d 22 65 6e 63 6f 64 65 39 2e 67 69 66 src="encode9.gif
2510: 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 " align="center"
2520: 3e 0a 61 64 64 73 20 6f 6e 65 20 77 65 69 67 68 >.adds one weigh
2530: 74 20 66 61 63 74 6f 72 20 74 6f 20 61 6c 6c 20 t factor to all
2540: 74 68 65 20 6f 74 68 65 72 20 76 61 6c 75 65 73 the other values
2550: 20 6f 66 20 5a 2c 20 61 6e 64 20 61 74 20 6c 61 of Z, and at la
2560: 73 74 20 61 64 64 73 0a 69 6e 20 3c 69 6d 67 20 st adds.in <img
2570: 73 72 63 3d 22 65 6e 63 6f 64 65 35 2e 67 69 66 src="encode5.gif
2580: 22 20 61 6c 69 67 6e 3d 22 63 65 6e 74 65 72 22 " align="center"
2590: 3e 20 77 69 74 68 20 77 65 69 67 68 74 20 31 2c > with weight 1,
25a0: 20 61 6c 73 6f 0a 67 65 6e 65 72 61 74 69 6e 67 also.generating
25b0: 20 74 68 65 20 63 6f 72 72 65 63 74 20 6e 65 77 the correct new
25c0: 20 73 75 6d 3c 2f 70 3e 0a sum</p>.