home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: LaTeX Document
(document/latex).
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| LaTeX Document (document/latex)
| magic
| Supported |
| 1%
| dexvert
| Corel 10 Texture (image/corel10Texture)
| ext
| Unsupported |
| 1%
| dexvert
| Croteam texture file (image/croteamTextureFile)
| ext
| Unsupported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| LaTeX 2e document text
| default
| |
| 99%
| file
| LaTeX document text
| default
| |
| 98%
| file
| LaTeX document, ASCII text
| default
| |
| 100%
| TrID
| LaTeX 2e document
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
| 100%
| xdgMime
| text/x-tex
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 5c 64 6f 63 75 6d 65 6e | 74 63 6c 61 73 73 5b 61 |\documen|tclass[a|
|00000010| 34 70 61 70 65 72 5d 7b | 61 72 74 69 63 6c 65 7d |4paper]{|article}|
|00000020| 0a 5c 62 65 67 69 6e 7b | 64 6f 63 75 6d 65 6e 74 |.\begin{|document|
|00000030| 7d 0a 0a 0a 5c 74 69 74 | 6c 65 7b 54 68 65 20 72 |}...\tit|le{The r|
|00000040| 73 79 6e 63 20 61 6c 67 | 6f 72 69 74 68 6d 7d 0a |sync alg|orithm}.|
|00000050| 0a 5c 61 75 74 68 6f 72 | 7b 41 6e 64 72 65 77 20 |.\author|{Andrew |
|00000060| 54 72 69 64 67 65 6c 6c | 20 5c 71 75 61 64 5c 71 |Tridgell| \quad\q|
|00000070| 75 61 64 20 50 61 75 6c | 20 4d 61 63 6b 65 72 72 |uad Paul| Mackerr|
|00000080| 61 73 5c 5c 0a 44 65 70 | 61 72 74 6d 65 6e 74 20 |as\\.Dep|artment |
|00000090| 6f 66 20 43 6f 6d 70 75 | 74 65 72 20 53 63 69 65 |of Compu|ter Scie|
|000000a0| 6e 63 65 20 5c 5c 0a 41 | 75 73 74 72 61 6c 69 61 |nce \\.A|ustralia|
|000000b0| 6e 20 4e 61 74 69 6f 6e | 61 6c 20 55 6e 69 76 65 |n Nation|al Unive|
|000000c0| 72 73 69 74 79 20 5c 5c | 0a 43 61 6e 62 65 72 72 |rsity \\|.Canberr|
|000000d0| 61 2c 20 41 43 54 20 30 | 32 30 30 2c 20 41 75 73 |a, ACT 0|200, Aus|
|000000e0| 74 72 61 6c 69 61 7d 0a | 0a 5c 6d 61 6b 65 74 69 |tralia}.|.\maketi|
|000000f0| 74 6c 65 0a 0a 5c 62 65 | 67 69 6e 7b 61 62 73 74 |tle..\be|gin{abst|
|00000100| 72 61 63 74 7d 0a 20 20 | 54 68 69 73 20 72 65 70 |ract}. |This rep|
|00000110| 6f 72 74 20 70 72 65 73 | 65 6e 74 73 20 61 6e 20 |ort pres|ents an |
|00000120| 61 6c 67 6f 72 69 74 68 | 6d 20 66 6f 72 20 75 70 |algorith|m for up|
|00000130| 64 61 74 69 6e 67 20 61 | 20 66 69 6c 65 20 6f 6e |dating a| file on|
|00000140| 20 6f 6e 65 20 6d 61 63 | 68 69 6e 65 0a 20 20 74 | one mac|hine. t|
|00000150| 6f 20 62 65 20 69 64 65 | 6e 74 69 63 61 6c 20 74 |o be ide|ntical t|
|00000160| 6f 20 61 20 66 69 6c 65 | 20 6f 6e 20 61 6e 6f 74 |o a file| on anot|
|00000170| 68 65 72 20 6d 61 63 68 | 69 6e 65 2e 20 20 57 65 |her mach|ine. We|
|00000180| 20 61 73 73 75 6d 65 20 | 74 68 61 74 20 74 68 65 | assume |that the|
|00000190| 0a 20 20 74 77 6f 20 6d | 61 63 68 69 6e 65 73 20 |. two m|achines |
|000001a0| 61 72 65 20 63 6f 6e 6e | 65 63 74 65 64 20 62 79 |are conn|ected by|
|000001b0| 20 61 20 6c 6f 77 2d 62 | 61 6e 64 77 69 64 74 68 | a low-b|andwidth|
|000001c0| 20 68 69 67 68 2d 6c 61 | 74 65 6e 63 79 0a 20 20 | high-la|tency. |
|000001d0| 62 69 2d 64 69 72 65 63 | 74 69 6f 6e 61 6c 20 63 |bi-direc|tional c|
|000001e0| 6f 6d 6d 75 6e 69 63 61 | 74 69 6f 6e 73 20 6c 69 |ommunica|tions li|
|000001f0| 6e 6b 2e 20 20 54 68 65 | 20 61 6c 67 6f 72 69 74 |nk. The| algorit|
|00000200| 68 6d 20 69 64 65 6e 74 | 69 66 69 65 73 20 70 61 |hm ident|ifies pa|
|00000210| 72 74 73 0a 20 20 6f 66 | 20 74 68 65 20 73 6f 75 |rts. of| the sou|
|00000220| 72 63 65 20 66 69 6c 65 | 20 77 68 69 63 68 20 61 |rce file| which a|
|00000230| 72 65 20 69 64 65 6e 74 | 69 63 61 6c 20 74 6f 20 |re ident|ical to |
|00000240| 73 6f 6d 65 20 70 61 72 | 74 20 6f 66 20 74 68 65 |some par|t of the|
|00000250| 0a 20 20 64 65 73 74 69 | 6e 61 74 69 6f 6e 20 66 |. desti|nation f|
|00000260| 69 6c 65 2c 20 61 6e 64 | 20 6f 6e 6c 79 20 73 65 |ile, and| only se|
|00000270| 6e 64 73 20 74 68 6f 73 | 65 20 70 61 72 74 73 20 |nds thos|e parts |
|00000280| 77 68 69 63 68 20 63 61 | 6e 6e 6f 74 20 62 65 20 |which ca|nnot be |
|00000290| 6d 61 74 63 68 65 64 0a | 20 20 69 6e 20 74 68 69 |matched.| in thi|
|000002a0| 73 20 77 61 79 2e 20 20 | 45 66 66 65 63 74 69 76 |s way. |Effectiv|
|000002b0| 65 6c 79 2c 20 74 68 65 | 20 61 6c 67 6f 72 69 74 |ely, the| algorit|
|000002c0| 68 6d 20 63 6f 6d 70 75 | 74 65 73 20 61 20 73 65 |hm compu|tes a se|
|000002d0| 74 20 6f 66 0a 20 20 64 | 69 66 66 65 72 65 6e 63 |t of. d|ifferenc|
|000002e0| 65 73 20 77 69 74 68 6f | 75 74 20 68 61 76 69 6e |es witho|ut havin|
|000002f0| 67 20 62 6f 74 68 20 66 | 69 6c 65 73 20 6f 6e 20 |g both f|iles on |
|00000300| 74 68 65 20 73 61 6d 65 | 20 6d 61 63 68 69 6e 65 |the same| machine|
|00000310| 2e 20 20 54 68 65 0a 20 | 20 61 6c 67 6f 72 69 74 |. The. | algorit|
|00000320| 68 6d 20 77 6f 72 6b 73 | 20 62 65 73 74 20 77 68 |hm works| best wh|
|00000330| 65 6e 20 74 68 65 20 66 | 69 6c 65 73 20 61 72 65 |en the f|iles are|
|00000340| 20 73 69 6d 69 6c 61 72 | 2c 20 62 75 74 20 77 69 | similar|, but wi|
|00000350| 6c 6c 20 61 6c 73 6f 0a | 20 20 66 75 6e 63 74 69 |ll also.| functi|
|00000360| 6f 6e 20 63 6f 72 72 65 | 63 74 6c 79 20 61 6e 64 |on corre|ctly and|
|00000370| 20 72 65 61 73 6f 6e 61 | 62 6c 79 20 65 66 66 69 | reasona|bly effi|
|00000380| 63 69 65 6e 74 6c 79 20 | 77 68 65 6e 20 74 68 65 |ciently |when the|
|00000390| 20 66 69 6c 65 73 20 61 | 72 65 0a 20 20 71 75 69 | files a|re. qui|
|000003a0| 74 65 20 64 69 66 66 65 | 72 65 6e 74 2e 0a 5c 65 |te diffe|rent..\e|
|000003b0| 6e 64 7b 61 62 73 74 72 | 61 63 74 7d 0a 0a 5c 73 |nd{abstr|act}..\s|
|000003c0| 65 63 74 69 6f 6e 7b 54 | 68 65 20 70 72 6f 62 6c |ection{T|he probl|
|000003d0| 65 6d 7d 0a 0a 49 6d 61 | 67 69 6e 65 20 79 6f 75 |em}..Ima|gine you|
|000003e0| 20 68 61 76 65 20 74 77 | 6f 20 66 69 6c 65 73 2c | have tw|o files,|
|000003f0| 20 24 41 24 20 61 6e 64 | 20 24 42 24 2c 20 61 6e | $A$ and| $B$, an|
|00000400| 64 20 79 6f 75 20 77 69 | 73 68 20 74 6f 20 75 70 |d you wi|sh to up|
|00000410| 64 61 74 65 20 24 42 24 | 20 74 6f 20 62 65 0a 74 |date $B$| to be.t|
|00000420| 68 65 20 73 61 6d 65 20 | 61 73 20 24 41 24 2e 20 |he same |as $A$. |
|00000430| 54 68 65 20 6f 62 76 69 | 6f 75 73 20 6d 65 74 68 |The obvi|ous meth|
|00000440| 6f 64 20 69 73 20 74 6f | 20 63 6f 70 79 20 24 41 |od is to| copy $A|
|00000450| 24 20 6f 6e 74 6f 20 24 | 42 24 2e 0a 0a 4e 6f 77 |$ onto $|B$...Now|
|00000460| 20 69 6d 61 67 69 6e 65 | 20 74 68 61 74 20 74 68 | imagine| that th|
|00000470| 65 20 74 77 6f 20 66 69 | 6c 65 73 20 61 72 65 20 |e two fi|les are |
|00000480| 6f 6e 20 6d 61 63 68 69 | 6e 65 73 20 63 6f 6e 6e |on machi|nes conn|
|00000490| 65 63 74 65 64 20 62 79 | 20 61 20 73 6c 6f 77 0a |ected by| a slow.|
|000004a0| 63 6f 6d 6d 75 6e 69 63 | 61 74 69 6f 6e 73 20 6c |communic|ations l|
|000004b0| 69 6e 6b 2c 20 66 6f 72 | 20 65 78 61 6d 70 6c 65 |ink, for| example|
|000004c0| 20 61 20 64 69 61 6c 20 | 75 70 20 49 50 20 6c 69 | a dial |up IP li|
|000004d0| 6e 6b 2e 20 20 49 66 20 | 24 41 24 20 69 73 20 6c |nk. If |$A$ is l|
|000004e0| 61 72 67 65 2c 0a 63 6f | 70 79 69 6e 67 20 24 41 |arge,.co|pying $A|
|000004f0| 24 20 6f 6e 74 6f 20 24 | 42 24 20 77 69 6c 6c 20 |$ onto $|B$ will |
|00000500| 62 65 20 73 6c 6f 77 2e | 20 20 54 6f 20 6d 61 6b |be slow.| To mak|
|00000510| 65 20 69 74 20 66 61 73 | 74 65 72 20 79 6f 75 20 |e it fas|ter you |
|00000520| 63 6f 75 6c 64 0a 63 6f | 6d 70 72 65 73 73 20 24 |could.co|mpress $|
|00000530| 41 24 20 62 65 66 6f 72 | 65 20 73 65 6e 64 69 6e |A$ befor|e sendin|
|00000540| 67 20 69 74 2c 20 62 75 | 74 20 74 68 61 74 20 77 |g it, bu|t that w|
|00000550| 69 6c 6c 20 75 73 75 61 | 6c 6c 79 20 6f 6e 6c 79 |ill usua|lly only|
|00000560| 20 67 61 69 6e 20 61 0a | 66 61 63 74 6f 72 20 6f | gain a.|factor o|
|00000570| 66 20 32 20 74 6f 20 34 | 2e 0a 0a 4e 6f 77 20 61 |f 2 to 4|...Now a|
|00000580| 73 73 75 6d 65 20 74 68 | 61 74 20 24 41 24 20 61 |ssume th|at $A$ a|
|00000590| 6e 64 20 24 42 24 20 61 | 72 65 20 71 75 69 74 65 |nd $B$ a|re quite|
|000005a0| 20 73 69 6d 69 6c 61 72 | 2c 20 70 65 72 68 61 70 | similar|, perhap|
|000005b0| 73 20 62 6f 74 68 20 64 | 65 72 69 76 65 64 0a 66 |s both d|erived.f|
|000005c0| 72 6f 6d 20 74 68 65 20 | 73 61 6d 65 20 6f 72 69 |rom the |same ori|
|000005d0| 67 69 6e 61 6c 20 66 69 | 6c 65 2e 20 54 6f 20 72 |ginal fi|le. To r|
|000005e0| 65 61 6c 6c 79 20 73 70 | 65 65 64 20 74 68 69 6e |eally sp|eed thin|
|000005f0| 67 73 20 75 70 20 79 6f | 75 20 77 6f 75 6c 64 20 |gs up yo|u would |
|00000600| 6e 65 65 64 0a 74 6f 20 | 74 61 6b 65 20 61 64 76 |need.to |take adv|
|00000610| 61 6e 74 61 67 65 20 6f | 66 20 74 68 69 73 20 73 |antage o|f this s|
|00000620| 69 6d 69 6c 61 72 69 74 | 79 2e 20 41 20 63 6f 6d |imilarit|y. A com|
|00000630| 6d 6f 6e 20 6d 65 74 68 | 6f 64 20 69 73 20 74 6f |mon meth|od is to|
|00000640| 20 73 65 6e 64 20 6a 75 | 73 74 0a 74 68 65 20 64 | send ju|st.the d|
|00000650| 69 66 66 65 72 65 6e 63 | 65 73 20 62 65 74 77 65 |ifferenc|es betwe|
|00000660| 65 6e 20 24 41 24 20 61 | 6e 64 20 24 42 24 20 64 |en $A$ a|nd $B$ d|
|00000670| 6f 77 6e 20 74 68 65 20 | 6c 69 6e 6b 20 61 6e 64 |own the |link and|
|00000680| 20 74 68 65 6e 20 75 73 | 65 20 74 68 69 73 0a 6c | then us|e this.l|
|00000690| 69 73 74 20 6f 66 20 64 | 69 66 66 65 72 65 6e 63 |ist of d|ifferenc|
|000006a0| 65 73 20 74 6f 20 72 65 | 63 6f 6e 73 74 72 75 63 |es to re|construc|
|000006b0| 74 20 74 68 65 20 66 69 | 6c 65 2e 0a 0a 54 68 65 |t the fi|le...The|
|000006c0| 20 70 72 6f 62 6c 65 6d | 20 69 73 20 74 68 61 74 | problem| is that|
|000006d0| 20 74 68 65 20 6e 6f 72 | 6d 61 6c 20 6d 65 74 68 | the nor|mal meth|
|000006e0| 6f 64 73 20 66 6f 72 20 | 63 72 65 61 74 69 6e 67 |ods for |creating|
|000006f0| 20 61 20 73 65 74 20 6f | 66 0a 64 69 66 66 65 72 | a set o|f.differ|
|00000700| 65 6e 63 65 73 20 62 65 | 74 77 65 65 6e 20 74 77 |ences be|tween tw|
|00000710| 6f 20 66 69 6c 65 73 20 | 72 65 6c 79 20 6f 6e 20 |o files |rely on |
|00000720| 62 65 69 6e 67 20 61 62 | 6c 65 20 74 6f 20 72 65 |being ab|le to re|
|00000730| 61 64 20 62 6f 74 68 20 | 66 69 6c 65 73 2e 0a 54 |ad both |files..T|
|00000740| 68 75 73 20 74 68 65 79 | 20 72 65 71 75 69 72 65 |hus they| require|
|00000750| 20 74 68 61 74 20 62 6f | 74 68 20 66 69 6c 65 73 | that bo|th files|
|00000760| 20 61 72 65 20 61 76 61 | 69 6c 61 62 6c 65 20 62 | are ava|ilable b|
|00000770| 65 66 6f 72 65 68 61 6e | 64 20 61 74 20 6f 6e 65 |eforehan|d at one|
|00000780| 20 65 6e 64 0a 6f 66 20 | 74 68 65 20 6c 69 6e 6b | end.of |the link|
|00000790| 2e 20 20 49 66 20 74 68 | 65 79 20 61 72 65 20 6e |. If th|ey are n|
|000007a0| 6f 74 20 62 6f 74 68 20 | 61 76 61 69 6c 61 62 6c |ot both |availabl|
|000007b0| 65 20 6f 6e 20 74 68 65 | 20 73 61 6d 65 20 6d 61 |e on the| same ma|
|000007c0| 63 68 69 6e 65 2c 0a 74 | 68 65 73 65 20 61 6c 67 |chine,.t|hese alg|
|000007d0| 6f 72 69 74 68 6d 73 20 | 63 61 6e 6e 6f 74 20 62 |orithms |cannot b|
|000007e0| 65 20 75 73 65 64 20 28 | 6f 6e 63 65 20 79 6f 75 |e used (|once you|
|000007f0| 20 68 61 64 20 63 6f 70 | 69 65 64 20 74 68 65 20 | had cop|ied the |
|00000800| 66 69 6c 65 20 6f 76 65 | 72 2c 0a 79 6f 75 20 77 |file ove|r,.you w|
|00000810| 6f 75 6c 64 6e 27 74 20 | 6e 65 65 64 20 74 68 65 |ouldn't |need the|
|00000820| 20 64 69 66 66 65 72 65 | 6e 63 65 73 29 2e 20 20 | differe|nces). |
|00000830| 54 68 69 73 20 69 73 20 | 74 68 65 20 70 72 6f 62 |This is |the prob|
|00000840| 6c 65 6d 20 74 68 61 74 | 20 72 73 79 6e 63 0a 61 |lem that| rsync.a|
|00000850| 64 64 72 65 73 73 65 73 | 2e 0a 0a 54 68 65 20 72 |ddresses|...The r|
|00000860| 73 79 6e 63 20 61 6c 67 | 6f 72 69 74 68 6d 20 65 |sync alg|orithm e|
|00000870| 66 66 69 63 69 65 6e 74 | 6c 79 20 63 6f 6d 70 75 |fficient|ly compu|
|00000880| 74 65 73 20 77 68 69 63 | 68 20 70 61 72 74 73 20 |tes whic|h parts |
|00000890| 6f 66 20 61 20 73 6f 75 | 72 63 65 20 66 69 6c 65 |of a sou|rce file|
|000008a0| 0a 6d 61 74 63 68 20 73 | 6f 6d 65 20 70 61 72 74 |.match s|ome part|
|000008b0| 20 6f 66 20 61 6e 20 65 | 78 69 73 74 69 6e 67 20 | of an e|xisting |
|000008c0| 64 65 73 74 69 6e 61 74 | 69 6f 6e 20 66 69 6c 65 |destinat|ion file|
|000008d0| 2e 20 20 54 68 65 73 65 | 20 70 61 72 74 73 20 6e |. These| parts n|
|000008e0| 65 65 64 20 6e 6f 74 0a | 62 65 20 73 65 6e 74 20 |eed not.|be sent |
|000008f0| 61 63 72 6f 73 73 20 74 | 68 65 20 6c 69 6e 6b 3b |across t|he link;|
|00000900| 20 61 6c 6c 20 74 68 61 | 74 20 69 73 20 6e 65 65 | all tha|t is nee|
|00000910| 64 65 64 20 69 73 20 61 | 20 72 65 66 65 72 65 6e |ded is a| referen|
|00000920| 63 65 20 74 6f 20 74 68 | 65 20 70 61 72 74 0a 6f |ce to th|e part.o|
|00000930| 66 20 74 68 65 20 64 65 | 73 74 69 6e 61 74 69 6f |f the de|stinatio|
|00000940| 6e 20 66 69 6c 65 2e 20 | 20 4f 6e 6c 79 20 70 61 |n file. | Only pa|
|00000950| 72 74 73 20 6f 66 20 74 | 68 65 20 73 6f 75 72 63 |rts of t|he sourc|
|00000960| 65 20 66 69 6c 65 20 77 | 68 69 63 68 20 61 72 65 |e file w|hich are|
|00000970| 20 6e 6f 74 0a 6d 61 74 | 63 68 65 64 20 69 6e 20 | not.mat|ched in |
|00000980| 74 68 69 73 20 77 61 79 | 20 6e 65 65 64 20 74 6f |this way| need to|
|00000990| 20 62 65 20 73 65 6e 74 | 20 76 65 72 62 61 74 69 | be sent| verbati|
|000009a0| 6d 2e 20 20 54 68 65 20 | 72 65 63 65 69 76 65 72 |m. The |receiver|
|000009b0| 20 63 61 6e 20 74 68 65 | 6e 0a 63 6f 6e 73 74 72 | can the|n.constr|
|000009c0| 75 63 74 20 61 20 63 6f | 70 79 20 6f 66 20 74 68 |uct a co|py of th|
|000009d0| 65 20 73 6f 75 72 63 65 | 20 66 69 6c 65 20 75 73 |e source| file us|
|000009e0| 69 6e 67 20 74 68 65 20 | 72 65 66 65 72 65 6e 63 |ing the |referenc|
|000009f0| 65 73 20 74 6f 20 70 61 | 72 74 73 20 6f 66 0a 74 |es to pa|rts of.t|
|00000a00| 68 65 20 65 78 69 73 74 | 69 6e 67 20 64 65 73 74 |he exist|ing dest|
|00000a10| 69 6e 61 74 69 6f 6e 20 | 66 69 6c 65 20 61 6e 64 |ination |file and|
|00000a20| 20 74 68 65 20 76 65 72 | 62 61 74 69 6d 20 6d 61 | the ver|batim ma|
|00000a30| 74 65 72 69 61 6c 2e 0a | 0a 54 72 69 76 69 61 6c |terial..|.Trivial|
|00000a40| 6c 79 2c 20 74 68 65 20 | 64 61 74 61 20 73 65 6e |ly, the |data sen|
|00000a50| 74 20 74 6f 20 74 68 65 | 20 72 65 63 65 69 76 65 |t to the| receive|
|00000a60| 72 20 63 61 6e 20 62 65 | 20 63 6f 6d 70 72 65 73 |r can be| compres|
|00000a70| 73 65 64 20 75 73 69 6e | 67 20 61 6e 79 0a 6f 66 |sed usin|g any.of|
|00000a80| 20 61 20 72 61 6e 67 65 | 20 6f 66 20 63 6f 6d 6d | a range| of comm|
|00000a90| 6f 6e 20 63 6f 6d 70 72 | 65 73 73 69 6f 6e 20 61 |on compr|ession a|
|00000aa0| 6c 67 6f 72 69 74 68 6d | 73 2c 20 66 6f 72 20 66 |lgorithm|s, for f|
|00000ab0| 75 72 74 68 65 72 20 73 | 70 65 65 64 0a 69 6d 70 |urther s|peed.imp|
|00000ac0| 72 6f 76 65 6d 65 6e 74 | 73 2e 0a 0a 5c 73 65 63 |rovement|s...\sec|
|00000ad0| 74 69 6f 6e 7b 54 68 65 | 20 72 73 79 6e 63 20 61 |tion{The| rsync a|
|00000ae0| 6c 67 6f 72 69 74 68 6d | 7d 0a 0a 53 75 70 70 6f |lgorithm|}..Suppo|
|00000af0| 73 65 20 77 65 20 68 61 | 76 65 20 74 77 6f 20 67 |se we ha|ve two g|
|00000b00| 65 6e 65 72 61 6c 20 70 | 75 72 70 6f 73 65 20 63 |eneral p|urpose c|
|00000b10| 6f 6d 70 75 74 65 72 73 | 20 24 5c 61 6c 70 68 61 |omputers| $\alpha|
|00000b20| 24 20 61 6e 64 20 24 5c | 62 65 74 61 24 2e 0a 43 |$ and $\|beta$..C|
|00000b30| 6f 6d 70 75 74 65 72 20 | 24 5c 61 6c 70 68 61 24 |omputer |$\alpha$|
|00000b40| 20 68 61 73 20 61 63 63 | 65 73 73 20 74 6f 20 61 | has acc|ess to a|
|00000b50| 20 66 69 6c 65 20 24 41 | 24 20 61 6e 64 20 24 5c | file $A|$ and $\|
|00000b60| 62 65 74 61 24 20 68 61 | 73 20 61 63 63 65 73 73 |beta$ ha|s access|
|00000b70| 20 74 6f 0a 66 69 6c 65 | 20 24 42 24 2c 20 77 68 | to.file| $B$, wh|
|00000b80| 65 72 65 20 24 41 24 20 | 61 6e 64 20 24 42 24 20 |ere $A$ |and $B$ |
|00000b90| 61 72 65 20 60 60 73 69 | 6d 69 6c 61 72 27 27 2e |are ``si|milar''.|
|00000ba0| 20 20 54 68 65 72 65 20 | 69 73 20 61 20 73 6c 6f | There |is a slo|
|00000bb0| 77 0a 63 6f 6d 6d 75 6e | 69 63 61 74 69 6f 6e 73 |w.commun|ications|
|00000bc0| 20 6c 69 6e 6b 20 62 65 | 74 77 65 65 6e 20 24 5c | link be|tween $\|
|00000bd0| 61 6c 70 68 61 24 20 61 | 6e 64 20 24 5c 62 65 74 |alpha$ a|nd $\bet|
|00000be0| 61 24 2e 0a 0a 54 68 65 | 20 72 73 79 6e 63 20 61 |a$...The| rsync a|
|00000bf0| 6c 67 6f 72 69 74 68 6d | 20 63 6f 6e 73 69 73 74 |lgorithm| consist|
|00000c00| 73 20 6f 66 20 74 68 65 | 20 66 6f 6c 6c 6f 77 69 |s of the| followi|
|00000c10| 6e 67 20 73 74 65 70 73 | 3a 0a 0a 5c 62 65 67 69 |ng steps|:..\begi|
|00000c20| 6e 7b 65 6e 75 6d 65 72 | 61 74 65 7d 0a 5c 69 74 |n{enumer|ate}.\it|
|00000c30| 65 6d 20 24 5c 62 65 74 | 61 24 20 73 70 6c 69 74 |em $\bet|a$ split|
|00000c40| 73 20 74 68 65 20 66 69 | 6c 65 20 24 42 24 20 69 |s the fi|le $B$ i|
|00000c50| 6e 74 6f 20 61 20 73 65 | 72 69 65 73 20 6f 66 20 |nto a se|ries of |
|00000c60| 6e 6f 6e 2d 6f 76 65 72 | 6c 61 70 70 69 6e 67 0a |non-over|lapping.|
|00000c70| 20 20 66 69 78 65 64 2d | 73 69 7a 65 64 20 62 6c | fixed-|sized bl|
|00000c80| 6f 63 6b 73 20 6f 66 20 | 73 69 7a 65 20 53 20 62 |ocks of |size S b|
|00000c90| 79 74 65 73 5c 66 6f 6f | 74 6e 6f 74 65 7b 57 65 |ytes\foo|tnote{We|
|00000ca0| 20 68 61 76 65 20 66 6f | 75 6e 64 20 74 68 61 74 | have fo|und that|
|00000cb0| 0a 20 20 76 61 6c 75 65 | 73 20 6f 66 20 53 20 62 |. value|s of S b|
|00000cc0| 65 74 77 65 65 6e 20 35 | 30 30 20 61 6e 64 20 31 |etween 5|00 and 1|
|00000cd0| 30 30 30 20 61 72 65 20 | 71 75 69 74 65 20 67 6f |000 are |quite go|
|00000ce0| 6f 64 20 66 6f 72 20 6d | 6f 73 74 20 70 75 72 70 |od for m|ost purp|
|00000cf0| 6f 73 65 73 7d 2e 0a 20 | 20 54 68 65 20 6c 61 73 |oses}.. | The las|
|00000d00| 74 20 62 6c 6f 63 6b 20 | 6d 61 79 20 62 65 20 73 |t block |may be s|
|00000d10| 68 6f 72 74 65 72 20 74 | 68 61 6e 20 24 53 24 20 |horter t|han $S$ |
|00000d20| 62 79 74 65 73 2e 0a 0a | 5c 69 74 65 6d 20 46 6f |bytes...|\item Fo|
|00000d30| 72 20 65 61 63 68 20 6f | 66 20 74 68 65 73 65 20 |r each o|f these |
|00000d40| 62 6c 6f 63 6b 73 20 24 | 5c 62 65 74 61 24 20 63 |blocks $|\beta$ c|
|00000d50| 61 6c 63 75 6c 61 74 65 | 73 20 74 77 6f 20 63 68 |alculate|s two ch|
|00000d60| 65 63 6b 73 75 6d 73 3a | 0a 20 20 61 20 77 65 61 |ecksums:|. a wea|
|00000d70| 6b 20 60 60 72 6f 6c 6c | 69 6e 67 27 27 20 33 32 |k ``roll|ing'' 32|
|00000d80| 2d 62 69 74 20 63 68 65 | 63 6b 73 75 6d 20 28 64 |-bit che|cksum (d|
|00000d90| 65 73 63 72 69 62 65 64 | 20 62 65 6c 6f 77 29 20 |escribed| below) |
|00000da0| 61 6e 64 20 61 20 73 74 | 72 6f 6e 67 0a 20 20 31 |and a st|rong. 1|
|00000db0| 32 38 2d 62 69 74 20 4d | 44 34 20 63 68 65 63 6b |28-bit M|D4 check|
|00000dc0| 73 75 6d 2e 0a 0a 5c 69 | 74 65 6d 20 24 5c 62 65 |sum...\i|tem $\be|
|00000dd0| 74 61 24 20 73 65 6e 64 | 73 20 74 68 65 73 65 20 |ta$ send|s these |
|00000de0| 63 68 65 63 6b 73 75 6d | 73 20 74 6f 20 24 5c 61 |checksum|s to $\a|
|00000df0| 6c 70 68 61 24 2e 0a 20 | 20 0a 5c 69 74 65 6d 20 |lpha$.. | .\item |
|00000e00| 24 5c 61 6c 70 68 61 24 | 20 73 65 61 72 63 68 65 |$\alpha$| searche|
|00000e10| 73 20 74 68 72 6f 75 67 | 68 20 24 41 24 20 74 6f |s throug|h $A$ to|
|00000e20| 20 66 69 6e 64 20 61 6c | 6c 20 62 6c 6f 63 6b 73 | find al|l blocks|
|00000e30| 20 6f 66 20 6c 65 6e 67 | 74 68 20 24 53 24 0a 20 | of leng|th $S$. |
|00000e40| 20 62 79 74 65 73 20 28 | 61 74 20 61 6e 79 20 6f | bytes (|at any o|
|00000e50| 66 66 73 65 74 2c 20 6e | 6f 74 20 6a 75 73 74 20 |ffset, n|ot just |
|00000e60| 6d 75 6c 74 69 70 6c 65 | 73 20 6f 66 20 24 53 24 |multiple|s of $S$|
|00000e70| 29 20 74 68 61 74 20 68 | 61 76 65 20 74 68 65 20 |) that h|ave the |
|00000e80| 73 61 6d 65 0a 20 20 77 | 65 61 6b 20 61 6e 64 20 |same. w|eak and |
|00000e90| 73 74 72 6f 6e 67 20 63 | 68 65 63 6b 73 75 6d 20 |strong c|hecksum |
|00000ea0| 61 73 20 6f 6e 65 20 6f | 66 20 74 68 65 20 62 6c |as one o|f the bl|
|00000eb0| 6f 63 6b 73 20 6f 66 20 | 24 42 24 2e 20 54 68 69 |ocks of |$B$. Thi|
|00000ec0| 73 20 63 61 6e 20 62 65 | 0a 20 20 64 6f 6e 65 20 |s can be|. done |
|00000ed0| 69 6e 20 61 20 73 69 6e | 67 6c 65 20 70 61 73 73 |in a sin|gle pass|
|00000ee0| 20 76 65 72 79 20 71 75 | 69 63 6b 6c 79 20 75 73 | very qu|ickly us|
|00000ef0| 69 6e 67 20 61 20 73 70 | 65 63 69 61 6c 20 70 72 |ing a sp|ecial pr|
|00000f00| 6f 70 65 72 74 79 20 6f | 66 20 74 68 65 0a 20 20 |operty o|f the. |
|00000f10| 72 6f 6c 6c 69 6e 67 20 | 63 68 65 63 6b 73 75 6d |rolling |checksum|
|00000f20| 20 64 65 73 63 72 69 62 | 65 64 20 62 65 6c 6f 77 | describ|ed below|
|00000f30| 2e 0a 20 20 0a 5c 69 74 | 65 6d 20 24 5c 61 6c 70 |.. .\it|em $\alp|
|00000f40| 68 61 24 20 73 65 6e 64 | 73 20 24 5c 62 65 74 61 |ha$ send|s $\beta|
|00000f50| 24 20 61 20 73 65 71 75 | 65 6e 63 65 20 6f 66 20 |$ a sequ|ence of |
|00000f60| 69 6e 73 74 72 75 63 74 | 69 6f 6e 73 20 66 6f 72 |instruct|ions for|
|00000f70| 0a 20 20 63 6f 6e 73 74 | 72 75 63 74 69 6e 67 20 |. const|ructing |
|00000f80| 61 20 63 6f 70 79 20 6f | 66 20 24 41 24 2e 20 20 |a copy o|f $A$. |
|00000f90| 45 61 63 68 20 69 6e 73 | 74 72 75 63 74 69 6f 6e |Each ins|truction|
|00000fa0| 20 69 73 20 65 69 74 68 | 65 72 20 61 20 72 65 66 | is eith|er a ref|
|00000fb0| 65 72 65 6e 63 65 0a 20 | 20 74 6f 20 61 20 62 6c |erence. | to a bl|
|00000fc0| 6f 63 6b 20 6f 66 20 24 | 42 24 2c 20 6f 72 20 6c |ock of $|B$, or l|
|00000fd0| 69 74 65 72 61 6c 20 64 | 61 74 61 2e 20 20 4c 69 |iteral d|ata. Li|
|00000fe0| 74 65 72 61 6c 20 64 61 | 74 61 20 69 73 20 73 65 |teral da|ta is se|
|00000ff0| 6e 74 20 6f 6e 6c 79 20 | 66 6f 72 0a 20 20 74 68 |nt only |for. th|
|00001000| 6f 73 65 20 73 65 63 74 | 69 6f 6e 73 20 6f 66 20 |ose sect|ions of |
|00001010| 24 41 24 20 77 68 69 63 | 68 20 64 69 64 20 6e 6f |$A$ whic|h did no|
|00001020| 74 20 6d 61 74 63 68 20 | 61 6e 79 20 6f 66 20 74 |t match |any of t|
|00001030| 68 65 20 62 6c 6f 63 6b | 73 20 6f 66 20 24 42 24 |he block|s of $B$|
|00001040| 2e 0a 5c 65 6e 64 7b 65 | 6e 75 6d 65 72 61 74 65 |..\end{e|numerate|
|00001050| 7d 0a 0a 54 68 65 20 65 | 6e 64 20 72 65 73 75 6c |}..The e|nd resul|
|00001060| 74 20 69 73 20 74 68 61 | 74 20 24 5c 62 65 74 61 |t is tha|t $\beta|
|00001070| 24 20 67 65 74 73 20 61 | 20 63 6f 70 79 20 6f 66 |$ gets a| copy of|
|00001080| 20 24 41 24 2c 20 62 75 | 74 20 6f 6e 6c 79 20 74 | $A$, bu|t only t|
|00001090| 68 65 20 70 69 65 63 65 | 73 0a 6f 66 20 24 41 24 |he piece|s.of $A$|
|000010a0| 20 74 68 61 74 20 61 72 | 65 20 6e 6f 74 20 66 6f | that ar|e not fo|
|000010b0| 75 6e 64 20 69 6e 20 24 | 42 24 20 28 70 6c 75 73 |und in $|B$ (plus|
|000010c0| 20 61 20 73 6d 61 6c 6c | 20 61 6d 6f 75 6e 74 20 | a small| amount |
|000010d0| 6f 66 20 64 61 74 61 20 | 66 6f 72 0a 63 68 65 63 |of data |for.chec|
|000010e0| 6b 73 75 6d 73 20 61 6e | 64 20 62 6c 6f 63 6b 20 |ksums an|d block |
|000010f0| 69 6e 64 65 78 65 73 29 | 20 61 72 65 20 73 65 6e |indexes)| are sen|
|00001100| 74 20 6f 76 65 72 20 74 | 68 65 20 6c 69 6e 6b 2e |t over t|he link.|
|00001110| 20 54 68 65 20 61 6c 67 | 6f 72 69 74 68 6d 0a 61 | The alg|orithm.a|
|00001120| 6c 73 6f 20 6f 6e 6c 79 | 20 72 65 71 75 69 72 65 |lso only| require|
|00001130| 73 20 6f 6e 65 20 72 6f | 75 6e 64 20 74 72 69 70 |s one ro|und trip|
|00001140| 2c 20 77 68 69 63 68 20 | 6d 69 6e 69 6d 69 73 65 |, which |minimise|
|00001150| 73 20 74 68 65 20 69 6d | 70 61 63 74 20 6f 66 20 |s the im|pact of |
|00001160| 74 68 65 0a 6c 69 6e 6b | 20 6c 61 74 65 6e 63 79 |the.link| latency|
|00001170| 2e 0a 0a 54 68 65 20 6d | 6f 73 74 20 69 6d 70 6f |...The m|ost impo|
|00001180| 72 74 61 6e 74 20 64 65 | 74 61 69 6c 73 20 6f 66 |rtant de|tails of|
|00001190| 20 74 68 65 20 61 6c 67 | 6f 72 69 74 68 6d 20 61 | the alg|orithm a|
|000011a0| 72 65 20 74 68 65 20 72 | 6f 6c 6c 69 6e 67 20 63 |re the r|olling c|
|000011b0| 68 65 63 6b 73 75 6d 0a | 61 6e 64 20 74 68 65 20 |hecksum.|and the |
|000011c0| 61 73 73 6f 63 69 61 74 | 65 64 20 6d 75 6c 74 69 |associat|ed multi|
|000011d0| 2d 61 6c 74 65 72 6e 61 | 74 65 20 73 65 61 72 63 |-alterna|te searc|
|000011e0| 68 20 6d 65 63 68 61 6e | 69 73 6d 20 77 68 69 63 |h mechan|ism whic|
|000011f0| 68 20 61 6c 6c 6f 77 73 | 20 74 68 65 0a 61 6c 6c |h allows| the.all|
|00001200| 2d 6f 66 66 73 65 74 73 | 20 63 68 65 63 6b 73 75 |-offsets| checksu|
|00001210| 6d 20 73 65 61 72 63 68 | 20 74 6f 20 70 72 6f 63 |m search| to proc|
|00001220| 65 65 64 20 76 65 72 79 | 20 71 75 69 63 6b 6c 79 |eed very| quickly|
|00001230| 2e 20 54 68 65 73 65 20 | 77 69 6c 6c 20 62 65 0a |. These |will be.|
|00001240| 64 69 73 63 75 73 73 65 | 64 20 69 6e 20 67 72 65 |discusse|d in gre|
|00001250| 61 74 65 72 20 64 65 74 | 61 69 6c 20 62 65 6c 6f |ater det|ail belo|
|00001260| 77 2e 0a 0a 5c 73 65 63 | 74 69 6f 6e 7b 52 6f 6c |w...\sec|tion{Rol|
|00001270| 6c 69 6e 67 20 63 68 65 | 63 6b 73 75 6d 7d 0a 0a |ling che|cksum}..|
|00001280| 54 68 65 20 77 65 61 6b | 20 72 6f 6c 6c 69 6e 67 |The weak| rolling|
|00001290| 20 63 68 65 63 6b 73 75 | 6d 20 75 73 65 64 20 69 | checksu|m used i|
|000012a0| 6e 20 74 68 65 20 72 73 | 79 6e 63 20 61 6c 67 6f |n the rs|ync algo|
|000012b0| 72 69 74 68 6d 20 6e 65 | 65 64 73 20 74 6f 20 68 |rithm ne|eds to h|
|000012c0| 61 76 65 0a 74 68 65 20 | 70 72 6f 70 65 72 74 79 |ave.the |property|
|000012d0| 20 74 68 61 74 20 69 74 | 20 69 73 20 76 65 72 79 | that it| is very|
|000012e0| 20 63 68 65 61 70 20 74 | 6f 20 63 61 6c 63 75 6c | cheap t|o calcul|
|000012f0| 61 74 65 20 74 68 65 20 | 63 68 65 63 6b 73 75 6d |ate the |checksum|
|00001300| 20 6f 66 20 61 0a 62 75 | 66 66 65 72 20 24 58 5f | of a.bu|ffer $X_|
|00001310| 32 20 2e 2e 20 58 5f 7b | 6e 2b 31 7d 24 20 67 69 |2 .. X_{|n+1}$ gi|
|00001320| 76 65 6e 20 74 68 65 20 | 63 68 65 63 6b 73 75 6d |ven the |checksum|
|00001330| 20 6f 66 20 62 75 66 66 | 65 72 20 24 58 5f 31 20 | of buff|er $X_1 |
|00001340| 2e 2e 20 58 5f 6e 24 20 | 61 6e 64 0a 74 68 65 20 |.. X_n$ |and.the |
|00001350| 76 61 6c 75 65 73 20 6f | 66 20 74 68 65 20 62 79 |values o|f the by|
|00001360| 74 65 73 20 24 58 5f 31 | 24 20 61 6e 64 20 24 58 |tes $X_1|$ and $X|
|00001370| 5f 7b 6e 2b 31 7d 24 2e | 0a 0a 54 68 65 20 77 65 |_{n+1}$.|..The we|
|00001380| 61 6b 20 63 68 65 63 6b | 73 75 6d 20 61 6c 67 6f |ak check|sum algo|
|00001390| 72 69 74 68 6d 20 77 65 | 20 75 73 65 64 20 69 6e |rithm we| used in|
|000013a0| 20 6f 75 72 20 69 6d 70 | 6c 65 6d 65 6e 74 61 74 | our imp|lementat|
|000013b0| 69 6f 6e 20 77 61 73 20 | 69 6e 73 70 69 72 65 64 |ion was |inspired|
|000013c0| 0a 62 79 20 4d 61 72 6b | 20 41 64 6c 65 72 27 73 |.by Mark| Adler's|
|000013d0| 20 61 64 6c 65 72 2d 33 | 32 20 63 68 65 63 6b 73 | adler-3|2 checks|
|000013e0| 75 6d 2e 20 20 4f 75 72 | 20 63 68 65 63 6b 73 75 |um. Our| checksu|
|000013f0| 6d 20 69 73 20 64 65 66 | 69 6e 65 64 20 62 79 0a |m is def|ined by.|
|00001400| 24 24 20 61 28 6b 2c 6c | 29 20 3d 20 28 5c 73 75 |$$ a(k,l|) = (\su|
|00001410| 6d 5f 7b 69 3d 6b 7d 5e | 6c 20 58 5f 69 29 20 5c |m_{i=k}^|l X_i) \|
|00001420| 62 6d 6f 64 20 4d 20 24 | 24 0a 24 24 20 62 28 6b |bmod M $|$.$$ b(k|
|00001430| 2c 6c 29 20 3d 20 28 5c | 73 75 6d 5f 7b 69 3d 6b |,l) = (\|sum_{i=k|
|00001440| 7d 5e 6c 20 28 6c 2d 69 | 2b 31 29 58 5f 69 29 20 |}^l (l-i|+1)X_i) |
|00001450| 5c 62 6d 6f 64 20 4d 20 | 24 24 0a 24 24 20 73 28 |\bmod M |$$.$$ s(|
|00001460| 6b 2c 6c 29 20 3d 20 61 | 28 6b 2c 6c 29 20 2b 20 |k,l) = a|(k,l) + |
|00001470| 32 5e 7b 31 36 7d 20 62 | 28 6b 2c 6c 29 20 24 24 |2^{16} b|(k,l) $$|
|00001480| 0a 0a 77 68 65 72 65 20 | 24 73 28 6b 2c 6c 29 24 |..where |$s(k,l)$|
|00001490| 20 69 73 20 74 68 65 20 | 72 6f 6c 6c 69 6e 67 20 | is the |rolling |
|000014a0| 63 68 65 63 6b 73 75 6d | 20 6f 66 20 74 68 65 20 |checksum| of the |
|000014b0| 62 79 74 65 73 20 24 58 | 5f 6b 20 5c 6c 64 6f 74 |bytes $X|_k \ldot|
|000014c0| 73 20 58 5f 6c 24 2e 0a | 46 6f 72 20 73 69 6d 70 |s X_l$..|For simp|
|000014d0| 6c 69 63 69 74 79 20 61 | 6e 64 20 73 70 65 65 64 |licity a|nd speed|
|000014e0| 2c 20 77 65 20 75 73 65 | 20 24 4d 20 3d 20 32 5e |, we use| $M = 2^|
|000014f0| 7b 31 36 7d 24 2e 20 20 | 0a 0a 54 68 65 20 69 6d |{16}$. |..The im|
|00001500| 70 6f 72 74 61 6e 74 20 | 70 72 6f 70 65 72 74 79 |portant |property|
|00001510| 20 6f 66 20 74 68 69 73 | 20 63 68 65 63 6b 73 75 | of this| checksu|
|00001520| 6d 20 69 73 20 74 68 61 | 74 20 73 75 63 63 65 73 |m is tha|t succes|
|00001530| 73 69 76 65 20 76 61 6c | 75 65 73 20 63 61 6e 0a |sive val|ues can.|
|00001540| 62 65 20 63 6f 6d 70 75 | 74 65 64 20 76 65 72 79 |be compu|ted very|
|00001550| 20 65 66 66 69 63 69 65 | 6e 74 6c 79 20 75 73 69 | efficie|ntly usi|
|00001560| 6e 67 20 74 68 65 20 72 | 65 63 75 72 72 65 6e 63 |ng the r|ecurrenc|
|00001570| 65 20 72 65 6c 61 74 69 | 6f 6e 73 0a 0a 24 24 20 |e relati|ons..$$ |
|00001580| 61 28 6b 2b 31 2c 6c 2b | 31 29 20 3d 20 28 61 28 |a(k+1,l+|1) = (a(|
|00001590| 6b 2c 6c 29 20 2d 20 58 | 5f 6b 20 2b 20 58 5f 7b |k,l) - X|_k + X_{|
|000015a0| 6c 2b 31 7d 29 20 5c 62 | 6d 6f 64 20 4d 20 24 24 |l+1}) \b|mod M $$|
|000015b0| 0a 24 24 20 62 28 6b 2b | 31 2c 6c 2b 31 29 20 3d |.$$ b(k+|1,l+1) =|
|000015c0| 20 28 62 28 6b 2c 6c 29 | 20 2d 20 28 6c 2d 6b 2b | (b(k,l)| - (l-k+|
|000015d0| 31 29 20 58 5f 6b 20 2b | 20 61 28 6b 2b 31 2c 6c |1) X_k +| a(k+1,l|
|000015e0| 2b 31 29 29 20 5c 62 6d | 6f 64 20 4d 20 24 24 0a |+1)) \bm|od M $$.|
|000015f0| 0a 54 68 75 73 20 74 68 | 65 20 63 68 65 63 6b 73 |.Thus th|e checks|
|00001600| 75 6d 20 63 61 6e 20 62 | 65 20 63 61 6c 63 75 6c |um can b|e calcul|
|00001610| 61 74 65 64 20 66 6f 72 | 20 62 6c 6f 63 6b 73 20 |ated for| blocks |
|00001620| 6f 66 20 6c 65 6e 67 74 | 68 20 53 20 61 74 20 61 |of lengt|h S at a|
|00001630| 6c 6c 0a 70 6f 73 73 69 | 62 6c 65 20 6f 66 66 73 |ll.possi|ble offs|
|00001640| 65 74 73 20 77 69 74 68 | 69 6e 20 61 20 66 69 6c |ets with|in a fil|
|00001650| 65 20 69 6e 20 61 20 60 | 60 72 6f 6c 6c 69 6e 67 |e in a `|`rolling|
|00001660| 27 27 20 66 61 73 68 69 | 6f 6e 2c 20 77 69 74 68 |'' fashi|on, with|
|00001670| 20 76 65 72 79 0a 6c 69 | 74 74 6c 65 20 63 6f 6d | very.li|ttle com|
|00001680| 70 75 74 61 74 69 6f 6e | 20 61 74 20 65 61 63 68 |putation| at each|
|00001690| 20 70 6f 69 6e 74 2e 0a | 0a 44 65 73 70 69 74 65 | point..|.Despite|
|000016a0| 20 69 74 73 20 73 69 6d | 70 6c 69 63 69 74 79 2c | its sim|plicity,|
|000016b0| 20 74 68 69 73 20 63 68 | 65 63 6b 73 75 6d 20 77 | this ch|ecksum w|
|000016c0| 61 73 20 66 6f 75 6e 64 | 20 74 6f 20 62 65 20 71 |as found| to be q|
|000016d0| 75 69 74 65 20 61 64 65 | 71 75 61 74 65 20 61 73 |uite ade|quate as|
|000016e0| 0a 61 20 66 69 72 73 74 | 20 6c 65 76 65 6c 20 63 |.a first| level c|
|000016f0| 68 65 63 6b 20 66 6f 72 | 20 61 20 6d 61 74 63 68 |heck for| a match|
|00001700| 20 6f 66 20 74 77 6f 20 | 66 69 6c 65 20 62 6c 6f | of two |file blo|
|00001710| 63 6b 73 2e 20 20 57 65 | 20 68 61 76 65 20 66 6f |cks. We| have fo|
|00001720| 75 6e 64 20 69 6e 0a 70 | 72 61 63 74 69 63 65 20 |und in.p|ractice |
|00001730| 74 68 61 74 20 74 68 65 | 20 70 72 6f 62 61 62 69 |that the| probabi|
|00001740| 6c 69 74 79 20 6f 66 20 | 74 68 69 73 20 63 68 65 |lity of |this che|
|00001750| 63 6b 73 75 6d 20 6d 61 | 74 63 68 69 6e 67 20 77 |cksum ma|tching w|
|00001760| 68 65 6e 20 74 68 65 0a | 62 6c 6f 63 6b 73 20 61 |hen the.|blocks a|
|00001770| 72 65 20 6e 6f 74 20 65 | 71 75 61 6c 20 69 73 20 |re not e|qual is |
|00001780| 71 75 69 74 65 20 6c 6f | 77 2e 20 20 54 68 69 73 |quite lo|w. This|
|00001790| 20 69 73 20 69 6d 70 6f | 72 74 61 6e 74 20 62 65 | is impo|rtant be|
|000017a0| 63 61 75 73 65 20 74 68 | 65 20 6d 75 63 68 0a 6d |cause th|e much.m|
|000017b0| 6f 72 65 20 65 78 70 65 | 6e 73 69 76 65 20 73 74 |ore expe|nsive st|
|000017c0| 72 6f 6e 67 20 63 68 65 | 63 6b 73 75 6d 20 6d 75 |rong che|cksum mu|
|000017d0| 73 74 20 62 65 20 63 61 | 6c 63 75 6c 61 74 65 64 |st be ca|lculated|
|000017e0| 20 66 6f 72 20 65 61 63 | 68 20 62 6c 6f 63 6b 20 | for eac|h block |
|000017f0| 77 68 65 72 65 0a 74 68 | 65 20 77 65 61 6b 20 63 |where.th|e weak c|
|00001800| 68 65 63 6b 73 75 6d 20 | 6d 61 74 63 68 65 73 2e |hecksum |matches.|
|00001810| 0a 0a 5c 73 65 63 74 69 | 6f 6e 7b 43 68 65 63 6b |..\secti|on{Check|
|00001820| 73 75 6d 20 73 65 61 72 | 63 68 69 6e 67 7d 0a 0a |sum sear|ching}..|
|00001830| 4f 6e 63 65 20 24 5c 61 | 6c 70 68 61 24 20 68 61 |Once $\a|lpha$ ha|
|00001840| 73 20 72 65 63 65 69 76 | 65 64 20 74 68 65 20 6c |s receiv|ed the l|
|00001850| 69 73 74 20 6f 66 20 63 | 68 65 63 6b 73 75 6d 73 |ist of c|hecksums|
|00001860| 20 6f 66 20 74 68 65 20 | 62 6c 6f 63 6b 73 20 6f | of the |blocks o|
|00001870| 66 20 24 42 24 2c 0a 69 | 74 20 6d 75 73 74 20 73 |f $B$,.i|t must s|
|00001880| 65 61 72 63 68 20 24 41 | 24 20 66 6f 72 20 61 6e |earch $A|$ for an|
|00001890| 79 20 62 6c 6f 63 6b 73 | 20 61 74 20 61 6e 79 20 |y blocks| at any |
|000018a0| 6f 66 66 73 65 74 20 74 | 68 61 74 20 6d 61 74 63 |offset t|hat matc|
|000018b0| 68 20 74 68 65 0a 63 68 | 65 63 6b 73 75 6d 20 6f |h the.ch|ecksum o|
|000018c0| 66 20 73 6f 6d 65 20 62 | 6c 6f 63 6b 20 6f 66 20 |f some b|lock of |
|000018d0| 24 42 24 2e 20 20 54 68 | 65 20 62 61 73 69 63 20 |$B$. Th|e basic |
|000018e0| 73 74 72 61 74 65 67 79 | 20 69 73 20 74 6f 20 63 |strategy| is to c|
|000018f0| 6f 6d 70 75 74 65 20 74 | 68 65 0a 33 32 2d 62 69 |ompute t|he.32-bi|
|00001900| 74 20 72 6f 6c 6c 69 6e | 67 20 63 68 65 63 6b 73 |t rollin|g checks|
|00001910| 75 6d 20 66 6f 72 20 61 | 20 62 6c 6f 63 6b 20 6f |um for a| block o|
|00001920| 66 20 6c 65 6e 67 74 68 | 20 24 53 24 20 73 74 61 |f length| $S$ sta|
|00001930| 72 74 69 6e 67 20 61 74 | 20 65 61 63 68 0a 62 79 |rting at| each.by|
|00001940| 74 65 20 6f 66 20 24 41 | 24 20 69 6e 20 74 75 72 |te of $A|$ in tur|
|00001950| 6e 2c 20 61 6e 64 20 66 | 6f 72 20 65 61 63 68 20 |n, and f|or each |
|00001960| 63 68 65 63 6b 73 75 6d | 2c 20 73 65 61 72 63 68 |checksum|, search|
|00001970| 20 74 68 65 20 6c 69 73 | 74 20 66 6f 72 20 61 0a | the lis|t for a.|
|00001980| 6d 61 74 63 68 2e 20 20 | 54 6f 20 64 6f 20 74 68 |match. |To do th|
|00001990| 69 73 20 6f 75 72 20 69 | 6d 70 6c 65 6d 65 6e 74 |is our i|mplement|
|000019a0| 61 74 69 6f 6e 20 75 73 | 65 73 20 61 0a 73 69 6d |ation us|es a.sim|
|000019b0| 70 6c 65 20 33 20 6c 65 | 76 65 6c 20 73 65 61 72 |ple 3 le|vel sear|
|000019c0| 63 68 69 6e 67 20 73 63 | 68 65 6d 65 2e 0a 0a 54 |ching sc|heme...T|
|000019d0| 68 65 20 66 69 72 73 74 | 20 6c 65 76 65 6c 20 75 |he first| level u|
|000019e0| 73 65 73 20 61 20 31 36 | 2d 62 69 74 20 68 61 73 |ses a 16|-bit has|
|000019f0| 68 20 6f 66 20 74 68 65 | 20 33 32 2d 62 69 74 20 |h of the| 32-bit |
|00001a00| 72 6f 6c 6c 69 6e 67 20 | 63 68 65 63 6b 73 75 6d |rolling |checksum|
|00001a10| 20 61 6e 64 0a 61 20 24 | 32 5e 7b 31 36 7d 24 20 | and.a $|2^{16}$ |
|00001a20| 65 6e 74 72 79 20 68 61 | 73 68 20 74 61 62 6c 65 |entry ha|sh table|
|00001a30| 2e 20 20 54 68 65 20 6c | 69 73 74 20 6f 66 20 63 |. The l|ist of c|
|00001a40| 68 65 63 6b 73 75 6d 20 | 76 61 6c 75 65 73 20 28 |hecksum |values (|
|00001a50| 69 2e 65 2e 2c 20 74 68 | 65 0a 63 68 65 63 6b 73 |i.e., th|e.checks|
|00001a60| 75 6d 73 20 66 72 6f 6d | 20 74 68 65 20 62 6c 6f |ums from| the blo|
|00001a70| 63 6b 73 20 6f 66 20 24 | 42 24 29 20 69 73 20 73 |cks of $|B$) is s|
|00001a80| 6f 72 74 65 64 20 61 63 | 63 6f 72 64 69 6e 67 20 |orted ac|cording |
|00001a90| 74 6f 20 74 68 65 20 31 | 36 2d 62 69 74 0a 68 61 |to the 1|6-bit.ha|
|00001aa0| 73 68 20 6f 66 20 74 68 | 65 20 33 32 2d 62 69 74 |sh of th|e 32-bit|
|00001ab0| 20 72 6f 6c 6c 69 6e 67 | 20 63 68 65 63 6b 73 75 | rolling| checksu|
|00001ac0| 6d 2e 20 20 45 61 63 68 | 20 65 6e 74 72 79 20 69 |m. Each| entry i|
|00001ad0| 6e 20 74 68 65 20 68 61 | 73 68 20 74 61 62 6c 65 |n the ha|sh table|
|00001ae0| 0a 70 6f 69 6e 74 73 20 | 74 6f 20 74 68 65 20 66 |.points |to the f|
|00001af0| 69 72 73 74 20 65 6c 65 | 6d 65 6e 74 20 6f 66 20 |irst ele|ment of |
|00001b00| 74 68 65 20 6c 69 73 74 | 20 66 6f 72 20 74 68 61 |the list| for tha|
|00001b10| 74 20 68 61 73 68 20 76 | 61 6c 75 65 2c 20 6f 72 |t hash v|alue, or|
|00001b20| 0a 63 6f 6e 74 61 69 6e | 73 20 61 20 6e 75 6c 6c |.contain|s a null|
|00001b30| 20 76 61 6c 75 65 20 69 | 66 20 6e 6f 20 65 6c 65 | value i|f no ele|
|00001b40| 6d 65 6e 74 20 6f 66 20 | 74 68 65 20 6c 69 73 74 |ment of |the list|
|00001b50| 20 68 61 73 20 74 68 61 | 74 20 68 61 73 68 20 76 | has tha|t hash v|
|00001b60| 61 6c 75 65 2e 0a 0a 41 | 74 20 65 61 63 68 20 6f |alue...A|t each o|
|00001b70| 66 66 73 65 74 20 69 6e | 20 74 68 65 20 66 69 6c |ffset in| the fil|
|00001b80| 65 20 74 68 65 20 33 32 | 2d 62 69 74 20 72 6f 6c |e the 32|-bit rol|
|00001b90| 6c 69 6e 67 20 63 68 65 | 63 6b 73 75 6d 20 61 6e |ling che|cksum an|
|00001ba0| 64 20 69 74 73 20 31 36 | 2d 62 69 74 0a 68 61 73 |d its 16|-bit.has|
|00001bb0| 68 20 61 72 65 20 63 61 | 6c 63 75 6c 61 74 65 64 |h are ca|lculated|
|00001bc0| 2e 20 20 49 66 20 74 68 | 65 20 68 61 73 68 20 74 |. If th|e hash t|
|00001bd0| 61 62 6c 65 20 65 6e 74 | 72 79 20 66 6f 72 20 74 |able ent|ry for t|
|00001be0| 68 61 74 20 68 61 73 68 | 20 76 61 6c 75 65 20 69 |hat hash| value i|
|00001bf0| 73 0a 6e 6f 74 20 61 20 | 6e 75 6c 6c 20 76 61 6c |s.not a |null val|
|00001c00| 75 65 2c 20 74 68 65 20 | 73 65 63 6f 6e 64 20 6c |ue, the |second l|
|00001c10| 65 76 65 6c 20 63 68 65 | 63 6b 20 69 73 20 69 6e |evel che|ck is in|
|00001c20| 76 6f 6b 65 64 2e 0a 0a | 54 68 65 20 73 65 63 6f |voked...|The seco|
|00001c30| 6e 64 20 6c 65 76 65 6c | 20 63 68 65 63 6b 20 69 |nd level| check i|
|00001c40| 6e 76 6f 6c 76 65 73 20 | 73 63 61 6e 6e 69 6e 67 |nvolves |scanning|
|00001c50| 20 74 68 65 20 73 6f 72 | 74 65 64 20 63 68 65 63 | the sor|ted chec|
|00001c60| 6b 73 75 6d 20 6c 69 73 | 74 0a 73 74 61 72 74 69 |ksum lis|t.starti|
|00001c70| 6e 67 20 77 69 74 68 20 | 74 68 65 20 65 6e 74 72 |ng with |the entr|
|00001c80| 79 20 70 6f 69 6e 74 65 | 64 20 74 6f 20 62 79 20 |y pointe|d to by |
|00001c90| 74 68 65 20 68 61 73 68 | 20 74 61 62 6c 65 20 65 |the hash| table e|
|00001ca0| 6e 74 72 79 2c 20 6c 6f | 6f 6b 69 6e 67 0a 66 6f |ntry, lo|oking.fo|
|00001cb0| 72 20 61 6e 20 65 6e 74 | 72 79 20 77 68 6f 73 65 |r an ent|ry whose|
|00001cc0| 20 33 32 2d 62 69 74 20 | 72 6f 6c 6c 69 6e 67 20 | 32-bit |rolling |
|00001cd0| 63 68 65 63 6b 73 75 6d | 20 6d 61 74 63 68 65 73 |checksum| matches|
|00001ce0| 20 74 68 65 20 63 75 72 | 72 65 6e 74 20 76 61 6c | the cur|rent val|
|00001cf0| 75 65 2e 0a 54 68 65 20 | 73 63 61 6e 20 74 65 72 |ue..The |scan ter|
|00001d00| 6d 69 6e 61 74 65 73 20 | 77 68 65 6e 20 69 74 20 |minates |when it |
|00001d10| 72 65 61 63 68 65 73 20 | 61 6e 20 65 6e 74 72 79 |reaches |an entry|
|00001d20| 20 77 68 6f 73 65 20 31 | 36 2d 62 69 74 20 68 61 | whose 1|6-bit ha|
|00001d30| 73 68 0a 64 69 66 66 65 | 72 73 2e 20 20 49 66 20 |sh.diffe|rs. If |
|00001d40| 74 68 69 73 20 73 65 61 | 72 63 68 20 66 69 6e 64 |this sea|rch find|
|00001d50| 73 20 61 20 6d 61 74 63 | 68 2c 20 74 68 65 20 74 |s a matc|h, the t|
|00001d60| 68 69 72 64 20 6c 65 76 | 65 6c 20 63 68 65 63 6b |hird lev|el check|
|00001d70| 20 69 73 0a 69 6e 76 6f | 6b 65 64 2e 0a 0a 54 68 | is.invo|ked...Th|
|00001d80| 65 20 74 68 69 72 64 20 | 6c 65 76 65 6c 20 63 68 |e third |level ch|
|00001d90| 65 63 6b 20 69 6e 76 6f | 6c 76 65 73 20 63 61 6c |eck invo|lves cal|
|00001da0| 63 75 6c 61 74 69 6e 67 | 20 74 68 65 20 73 74 72 |culating| the str|
|00001db0| 6f 6e 67 20 63 68 65 63 | 6b 73 75 6d 20 66 6f 72 |ong chec|ksum for|
|00001dc0| 20 74 68 65 0a 63 75 72 | 72 65 6e 74 20 6f 66 66 | the.cur|rent off|
|00001dd0| 73 65 74 20 69 6e 20 74 | 68 65 20 66 69 6c 65 20 |set in t|he file |
|00001de0| 61 6e 64 20 63 6f 6d 70 | 61 72 69 6e 67 20 69 74 |and comp|aring it|
|00001df0| 20 77 69 74 68 20 74 68 | 65 20 73 74 72 6f 6e 67 | with th|e strong|
|00001e00| 20 63 68 65 63 6b 73 75 | 6d 0a 76 61 6c 75 65 20 | checksu|m.value |
|00001e10| 69 6e 20 74 68 65 20 63 | 75 72 72 65 6e 74 20 6c |in the c|urrent l|
|00001e20| 69 73 74 20 65 6e 74 72 | 79 2e 20 20 49 66 20 74 |ist entr|y. If t|
|00001e30| 68 65 20 74 77 6f 20 73 | 74 72 6f 6e 67 20 63 68 |he two s|trong ch|
|00001e40| 65 63 6b 73 75 6d 73 20 | 6d 61 74 63 68 2c 0a 77 |ecksums |match,.w|
|00001e50| 65 20 61 73 73 75 6d 65 | 20 74 68 61 74 20 77 65 |e assume| that we|
|00001e60| 20 68 61 76 65 20 66 6f | 75 6e 64 20 61 20 62 6c | have fo|und a bl|
|00001e70| 6f 63 6b 20 6f 66 20 24 | 41 24 20 77 68 69 63 68 |ock of $|A$ which|
|00001e80| 20 6d 61 74 63 68 65 73 | 20 61 20 62 6c 6f 63 6b | matches| a block|
|00001e90| 20 6f 66 0a 24 42 24 2e | 20 20 49 6e 20 66 61 63 | of.$B$.| In fac|
|00001ea0| 74 20 74 68 65 20 62 6c | 6f 63 6b 73 20 63 6f 75 |t the bl|ocks cou|
|00001eb0| 6c 64 20 62 65 20 64 69 | 66 66 65 72 65 6e 74 2c |ld be di|fferent,|
|00001ec0| 20 62 75 74 20 74 68 65 | 20 70 72 6f 62 61 62 69 | but the| probabi|
|00001ed0| 6c 69 74 79 20 6f 66 0a | 74 68 69 73 20 69 73 20 |lity of.|this is |
|00001ee0| 6d 69 63 72 6f 73 63 6f | 70 69 63 2c 20 61 6e 64 |microsco|pic, and|
|00001ef0| 20 69 6e 20 70 72 61 63 | 74 69 63 65 20 74 68 69 | in prac|tice thi|
|00001f00| 73 20 69 73 20 61 20 72 | 65 61 73 6f 6e 61 62 6c |s is a r|easonabl|
|00001f10| 65 20 61 73 73 75 6d 70 | 74 69 6f 6e 2e 0a 0a 57 |e assump|tion...W|
|00001f20| 68 65 6e 20 61 20 6d 61 | 74 63 68 20 69 73 20 66 |hen a ma|tch is f|
|00001f30| 6f 75 6e 64 2c 20 24 5c | 61 6c 70 68 61 24 20 73 |ound, $\|alpha$ s|
|00001f40| 65 6e 64 73 20 24 5c 62 | 65 74 61 24 20 74 68 65 |ends $\b|eta$ the|
|00001f50| 20 64 61 74 61 20 69 6e | 20 24 41 24 20 62 65 74 | data in| $A$ bet|
|00001f60| 77 65 65 6e 0a 74 68 65 | 20 63 75 72 72 65 6e 74 |ween.the| current|
|00001f70| 20 66 69 6c 65 20 6f 66 | 66 73 65 74 20 61 6e 64 | file of|fset and|
|00001f80| 20 74 68 65 20 65 6e 64 | 20 6f 66 20 74 68 65 20 | the end| of the |
|00001f90| 70 72 65 76 69 6f 75 73 | 20 6d 61 74 63 68 2c 20 |previous| match, |
|00001fa0| 66 6f 6c 6c 6f 77 65 64 | 20 62 79 0a 74 68 65 20 |followed| by.the |
|00001fb0| 69 6e 64 65 78 20 6f 66 | 20 74 68 65 20 62 6c 6f |index of| the blo|
|00001fc0| 63 6b 20 69 6e 20 24 42 | 24 20 74 68 61 74 20 6d |ck in $B|$ that m|
|00001fd0| 61 74 63 68 65 64 2e 20 | 20 54 68 69 73 20 64 61 |atched. | This da|
|00001fe0| 74 61 20 69 73 20 73 65 | 6e 74 0a 69 6d 6d 65 64 |ta is se|nt.immed|
|00001ff0| 69 61 74 65 6c 79 20 61 | 20 6d 61 74 63 68 20 69 |iately a| match i|
|00002000| 73 20 66 6f 75 6e 64 2c | 20 77 68 69 63 68 20 61 |s found,| which a|
|00002010| 6c 6c 6f 77 73 20 75 73 | 20 74 6f 20 6f 76 65 72 |llows us| to over|
|00002020| 6c 61 70 20 74 68 65 0a | 63 6f 6d 6d 75 6e 69 63 |lap the.|communic|
|00002030| 61 74 69 6f 6e 20 77 69 | 74 68 20 66 75 72 74 68 |ation wi|th furth|
|00002040| 65 72 20 63 6f 6d 70 75 | 74 61 74 69 6f 6e 2e 0a |er compu|tation..|
|00002050| 0a 49 66 20 6e 6f 20 6d | 61 74 63 68 20 69 73 20 |.If no m|atch is |
|00002060| 66 6f 75 6e 64 20 61 74 | 20 61 20 67 69 76 65 6e |found at| a given|
|00002070| 20 6f 66 66 73 65 74 20 | 69 6e 20 74 68 65 20 66 | offset |in the f|
|00002080| 69 6c 65 2c 20 74 68 65 | 20 72 6f 6c 6c 69 6e 67 |ile, the| rolling|
|00002090| 0a 63 68 65 63 6b 73 75 | 6d 20 69 73 20 75 70 64 |.checksu|m is upd|
|000020a0| 61 74 65 64 20 74 6f 20 | 74 68 65 20 6e 65 78 74 |ated to |the next|
|000020b0| 20 6f 66 66 73 65 74 20 | 61 6e 64 20 74 68 65 20 | offset |and the |
|000020c0| 73 65 61 72 63 68 20 70 | 72 6f 63 65 65 64 73 2e |search p|roceeds.|
|000020d0| 20 20 49 66 20 61 0a 6d | 61 74 63 68 20 69 73 20 | If a.m|atch is |
|000020e0| 66 6f 75 6e 64 2c 20 74 | 68 65 20 73 65 61 72 63 |found, t|he searc|
|000020f0| 68 20 69 73 20 72 65 73 | 74 61 72 74 65 64 20 61 |h is res|tarted a|
|00002100| 74 20 74 68 65 20 65 6e | 64 20 6f 66 20 74 68 65 |t the en|d of the|
|00002110| 20 6d 61 74 63 68 65 64 | 0a 62 6c 6f 63 6b 2e 20 | matched|.block. |
|00002120| 20 54 68 69 73 20 73 74 | 72 61 74 65 67 79 20 73 | This st|rategy s|
|00002130| 61 76 65 73 20 61 20 63 | 6f 6e 73 69 64 65 72 61 |aves a c|onsidera|
|00002140| 62 6c 65 20 61 6d 6f 75 | 6e 74 20 6f 66 20 63 6f |ble amou|nt of co|
|00002150| 6d 70 75 74 61 74 69 6f | 6e 20 66 6f 72 0a 74 68 |mputatio|n for.th|
|00002160| 65 20 63 6f 6d 6d 6f 6e | 20 63 61 73 65 20 77 68 |e common| case wh|
|00002170| 65 72 65 20 74 68 65 20 | 74 77 6f 20 66 69 6c 65 |ere the |two file|
|00002180| 73 20 61 72 65 20 6e 65 | 61 72 6c 79 20 69 64 65 |s are ne|arly ide|
|00002190| 6e 74 69 63 61 6c 2e 20 | 20 49 6e 0a 61 64 64 69 |ntical. | In.addi|
|000021a0| 74 69 6f 6e 2c 20 69 74 | 20 77 6f 75 6c 64 20 62 |tion, it| would b|
|000021b0| 65 20 61 20 73 69 6d 70 | 6c 65 20 6d 61 74 74 65 |e a simp|le matte|
|000021c0| 72 20 74 6f 20 65 6e 63 | 6f 64 65 20 74 68 65 20 |r to enc|ode the |
|000021d0| 62 6c 6f 63 6b 20 69 6e | 64 65 78 65 73 20 61 73 |block in|dexes as|
|000021e0| 0a 72 75 6e 73 2c 20 66 | 6f 72 20 74 68 65 20 63 |.runs, f|or the c|
|000021f0| 6f 6d 6d 6f 6e 20 63 61 | 73 65 20 77 68 65 72 65 |ommon ca|se where|
|00002200| 20 61 20 70 6f 72 74 69 | 6f 6e 20 6f 66 20 24 41 | a porti|on of $A|
|00002210| 24 20 6d 61 74 63 68 65 | 73 20 61 20 73 65 72 69 |$ matche|s a seri|
|00002220| 65 73 20 6f 66 0a 62 6c | 6f 63 6b 73 20 6f 66 20 |es of.bl|ocks of |
|00002230| 24 42 24 20 69 6e 20 6f | 72 64 65 72 2e 0a 0a 5c |$B$ in o|rder...\|
|00002240| 73 65 63 74 69 6f 6e 7b | 50 69 70 65 6c 69 6e 69 |section{|Pipelini|
|00002250| 6e 67 7d 0a 0a 54 68 65 | 20 61 62 6f 76 65 20 73 |ng}..The| above s|
|00002260| 65 63 74 69 6f 6e 73 20 | 64 65 73 63 72 69 62 65 |ections |describe|
|00002270| 20 74 68 65 20 70 72 6f | 63 65 73 73 20 66 6f 72 | the pro|cess for|
|00002280| 20 63 6f 6e 73 74 72 75 | 63 74 69 6e 67 20 61 20 | constru|cting a |
|00002290| 63 6f 70 79 20 6f 66 20 | 6f 6e 65 0a 66 69 6c 65 |copy of |one.file|
|000022a0| 20 6f 6e 20 61 20 72 65 | 6d 6f 74 65 20 73 79 73 | on a re|mote sys|
|000022b0| 74 65 6d 2e 20 20 49 66 | 20 77 65 20 68 61 76 65 |tem. If| we have|
|000022c0| 20 61 20 73 65 76 65 72 | 61 6c 20 66 69 6c 65 73 | a sever|al files|
|000022d0| 20 74 6f 20 63 6f 70 79 | 2c 20 77 65 20 63 61 6e | to copy|, we can|
|000022e0| 0a 67 61 69 6e 20 61 20 | 63 6f 6e 73 69 64 65 72 |.gain a |consider|
|000022f0| 61 62 6c 65 20 6c 61 74 | 65 6e 63 79 20 61 64 76 |able lat|ency adv|
|00002300| 61 6e 74 61 67 65 20 62 | 79 20 70 69 70 65 6c 69 |antage b|y pipeli|
|00002310| 6e 69 6e 67 20 74 68 65 | 20 70 72 6f 63 65 73 73 |ning the| process|
|00002320| 2e 0a 0a 54 68 69 73 20 | 69 6e 76 6f 6c 76 65 73 |...This |involves|
|00002330| 20 24 5c 62 65 74 61 24 | 20 69 6e 69 74 69 61 74 | $\beta$| initiat|
|00002340| 69 6e 67 20 74 77 6f 20 | 69 6e 64 65 70 65 6e 64 |ing two |independ|
|00002350| 65 6e 74 20 70 72 6f 63 | 65 73 73 65 73 2e 20 4f |ent proc|esses. O|
|00002360| 6e 65 20 6f 66 20 74 68 | 65 0a 70 72 6f 63 65 73 |ne of th|e.proces|
|00002370| 73 65 73 20 67 65 6e 65 | 72 61 74 65 73 20 61 6e |ses gene|rates an|
|00002380| 64 20 73 65 6e 64 73 20 | 74 68 65 20 63 68 65 63 |d sends |the chec|
|00002390| 6b 73 75 6d 73 20 74 6f | 20 24 5c 61 6c 70 68 61 |ksums to| $\alpha|
|000023a0| 24 20 77 68 69 6c 65 20 | 74 68 65 0a 6f 74 68 65 |$ while |the.othe|
|000023b0| 72 20 72 65 63 65 69 76 | 65 73 20 74 68 65 20 64 |r receiv|es the d|
|000023c0| 69 66 66 65 72 65 6e 63 | 65 20 69 6e 66 6f 72 6d |ifferenc|e inform|
|000023d0| 61 74 69 6f 6e 20 66 72 | 6f 6d 20 24 5c 61 6c 70 |ation fr|om $\alp|
|000023e0| 68 61 24 20 61 6e 64 0a | 72 65 63 6f 6e 73 74 72 |ha$ and.|reconstr|
|000023f0| 75 63 74 73 20 74 68 65 | 20 66 69 6c 65 73 2e 20 |ucts the| files. |
|00002400| 0a 0a 49 66 20 74 68 65 | 20 63 6f 6d 6d 75 6e 69 |..If the| communi|
|00002410| 63 61 74 69 6f 6e 73 20 | 6c 69 6e 6b 20 69 73 20 |cations |link is |
|00002420| 62 75 66 66 65 72 65 64 | 20 74 68 65 6e 20 74 68 |buffered| then th|
|00002430| 65 73 65 20 74 77 6f 20 | 70 72 6f 63 65 73 73 65 |ese two |processe|
|00002440| 73 20 63 61 6e 0a 70 72 | 6f 63 65 65 64 20 69 6e |s can.pr|oceed in|
|00002450| 64 65 70 65 6e 64 65 6e | 74 6c 79 20 61 6e 64 20 |dependen|tly and |
|00002460| 74 68 65 20 6c 69 6e 6b | 20 73 68 6f 75 6c 64 20 |the link| should |
|00002470| 62 65 20 6b 65 70 74 20 | 66 75 6c 6c 79 20 75 74 |be kept |fully ut|
|00002480| 69 6c 69 73 65 64 20 69 | 6e 0a 62 6f 74 68 20 64 |ilised i|n.both d|
|00002490| 69 72 65 63 74 69 6f 6e | 73 20 66 6f 72 20 6d 6f |irection|s for mo|
|000024a0| 73 74 20 6f 66 20 74 68 | 65 20 74 69 6d 65 2e 20 |st of th|e time. |
|000024b0| 0a 0a 5c 73 65 63 74 69 | 6f 6e 7b 52 65 73 75 6c |..\secti|on{Resul|
|000024c0| 74 73 7d 0a 0a 54 6f 20 | 74 65 73 74 20 74 68 65 |ts}..To |test the|
|000024d0| 20 61 6c 67 6f 72 69 74 | 68 6d 2c 20 74 61 72 20 | algorit|hm, tar |
|000024e0| 66 69 6c 65 73 20 77 65 | 72 65 20 63 72 65 61 74 |files we|re creat|
|000024f0| 65 64 20 6f 66 20 74 68 | 65 20 4c 69 6e 75 78 20 |ed of th|e Linux |
|00002500| 6b 65 72 6e 65 6c 0a 73 | 6f 75 72 63 65 73 20 66 |kernel.s|ources f|
|00002510| 6f 72 20 74 77 6f 20 76 | 65 72 73 69 6f 6e 73 20 |or two v|ersions |
|00002520| 6f 66 20 74 68 65 20 6b | 65 72 6e 65 6c 2e 20 54 |of the k|ernel. T|
|00002530| 68 65 20 74 77 6f 20 6b | 65 72 6e 65 6c 20 76 65 |he two k|ernel ve|
|00002540| 72 73 69 6f 6e 73 20 77 | 65 72 65 0a 31 2e 39 39 |rsions w|ere.1.99|
|00002550| 2e 31 30 20 61 6e 64 20 | 32 2e 30 2e 30 2e 20 54 |.10 and |2.0.0. T|
|00002560| 68 65 73 65 20 74 61 72 | 20 66 69 6c 65 73 20 61 |hese tar| files a|
|00002570| 72 65 20 61 70 70 72 6f | 78 69 6d 61 74 65 6c 79 |re appro|ximately|
|00002580| 20 32 34 4d 42 20 69 6e | 20 73 69 7a 65 20 61 6e | 24MB in| size an|
|00002590| 64 0a 61 72 65 20 73 65 | 70 61 72 61 74 65 64 20 |d.are se|parated |
|000025a0| 62 79 20 35 20 72 65 6c | 65 61 73 65 64 20 70 61 |by 5 rel|eased pa|
|000025b0| 74 63 68 20 6c 65 76 65 | 6c 73 2e 0a 0a 4f 75 74 |tch leve|ls...Out|
|000025c0| 20 6f 66 20 74 68 65 20 | 32 34 34 31 20 66 69 6c | of the |2441 fil|
|000025d0| 65 73 20 69 6e 20 74 68 | 65 20 31 2e 39 39 2e 31 |es in th|e 1.99.1|
|000025e0| 30 20 72 65 6c 65 61 73 | 65 2c 20 32 39 31 20 66 |0 releas|e, 291 f|
|000025f0| 69 6c 65 73 20 68 61 64 | 20 63 68 61 6e 67 65 64 |iles had| changed|
|00002600| 20 69 6e 0a 74 68 65 20 | 32 2e 30 2e 30 20 72 65 | in.the |2.0.0 re|
|00002610| 6c 65 61 73 65 2c 20 31 | 39 20 66 69 6c 65 73 20 |lease, 1|9 files |
|00002620| 68 61 64 20 62 65 65 6e | 20 72 65 6d 6f 76 65 64 |had been| removed|
|00002630| 20 61 6e 64 20 32 35 20 | 66 69 6c 65 73 20 68 61 | and 25 |files ha|
|00002640| 64 20 62 65 65 6e 0a 61 | 64 64 65 64 2e 0a 0a 41 |d been.a|dded...A|
|00002650| 20 60 60 64 69 66 66 27 | 27 20 6f 66 20 74 68 65 | ``diff'|' of the|
|00002660| 20 74 77 6f 20 74 61 72 | 20 66 69 6c 65 73 20 75 | two tar| files u|
|00002670| 73 69 6e 67 20 74 68 65 | 20 73 74 61 6e 64 61 72 |sing the| standar|
|00002680| 64 20 47 4e 55 20 64 69 | 66 66 20 75 74 69 6c 69 |d GNU di|ff utili|
|00002690| 74 79 0a 70 72 6f 64 75 | 63 65 64 20 6f 76 65 72 |ty.produ|ced over|
|000026a0| 20 33 32 20 74 68 6f 75 | 73 61 6e 64 20 6c 69 6e | 32 thou|sand lin|
|000026b0| 65 73 20 6f 66 20 6f 75 | 74 70 75 74 20 74 6f 74 |es of ou|tput tot|
|000026c0| 61 6c 6c 69 6e 67 20 32 | 2e 31 20 4d 42 2e 0a 0a |alling 2|.1 MB...|
|000026d0| 54 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 74 61 |The foll|owing ta|
|000026e0| 62 6c 65 20 73 68 6f 77 | 73 20 74 68 65 20 72 65 |ble show|s the re|
|000026f0| 73 75 6c 74 73 20 66 6f | 72 20 72 73 79 6e 63 20 |sults fo|r rsync |
|00002700| 62 65 74 77 65 65 6e 20 | 74 68 65 20 74 77 6f 20 |between |the two |
|00002710| 66 69 6c 65 73 0a 77 69 | 74 68 20 61 20 76 61 72 |files.wi|th a var|
|00002720| 79 69 6e 67 20 62 6c 6f | 63 6b 20 73 69 7a 65 2e |ying blo|ck size.|
|00002730| 5c 66 6f 6f 74 6e 6f 74 | 65 7b 41 6c 6c 20 74 68 |\footnot|e{All th|
|00002740| 65 20 74 65 73 74 73 20 | 69 6e 20 74 68 69 73 20 |e tests |in this |
|00002750| 73 65 63 74 69 6f 6e 20 | 77 65 72 65 0a 20 20 63 |section |were. c|
|00002760| 61 72 72 69 65 64 20 6f | 75 74 20 75 73 69 6e 67 |arried o|ut using|
|00002770| 20 72 73 79 6e 63 20 76 | 65 72 73 69 6f 6e 20 30 | rsync v|ersion 0|
|00002780| 2e 35 7d 0a 0a 5c 76 73 | 70 61 63 65 2a 7b 35 6d |.5}..\vs|pace*{5m|
|00002790| 6d 7d 0a 5c 62 65 67 69 | 6e 7b 74 61 62 75 6c 61 |m}.\begi|n{tabula|
|000027a0| 72 7d 7b 7c 6c 7c 6c 7c | 6c 7c 6c 7c 6c 7c 6c 7c |r}{|l|l||l|l|l|l||
|000027b0| 6c 7c 7d 20 5c 68 6c 69 | 6e 65 0a 7b 5c 62 66 20 |l|} \hli|ne.{\bf |
|000027c0| 62 6c 6f 63 6b 7d 20 26 | 20 7b 5c 62 66 20 6d 61 |block} &| {\bf ma|
|000027d0| 74 63 68 65 73 7d 20 26 | 20 7b 5c 62 66 20 74 61 |tches} &| {\bf ta|
|000027e0| 67 7d 20 20 26 20 7b 5c | 62 66 20 66 61 6c 73 65 |g} & {\|bf false|
|000027f0| 7d 20 20 26 20 7b 5c 62 | 66 20 64 61 74 61 7d 20 |} & {\b|f data} |
|00002800| 26 20 7b 5c 62 66 20 77 | 72 69 74 74 65 6e 7d 20 |& {\bf w|ritten} |
|00002810| 20 26 20 7b 5c 62 66 20 | 72 65 61 64 7d 20 5c 5c | & {\bf |read} \\|
|00002820| 0a 7b 5c 62 66 20 73 69 | 7a 65 7d 20 20 26 20 20 |.{\bf si|ze} & |
|00002830| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 26 20 7b | | & {|
|00002840| 5c 62 66 20 68 69 74 73 | 7d 20 26 20 7b 5c 62 66 |\bf hits|} & {\bf|
|00002850| 20 61 6c 61 72 6d 73 7d | 20 26 20 20 20 20 20 20 | alarms}| & |
|00002860| 20 20 20 20 20 20 26 20 | 20 20 20 20 20 20 20 20 | & | |
|00002870| 20 20 20 20 20 20 20 26 | 20 20 20 20 20 20 20 20 | &| |
|00002880| 20 20 20 20 5c 5c 20 5c | 68 6c 69 6e 65 20 5c 68 | \\ \|hline \h|
|00002890| 6c 69 6e 65 0a 0a 33 30 | 30 20 20 20 20 20 20 20 |line..30|0 |
|000028a0| 20 20 26 20 36 34 32 34 | 37 20 20 20 20 20 20 20 | & 6424|7 |
|000028b0| 20 20 26 20 33 38 31 37 | 34 33 34 20 20 20 20 26 | & 3817|434 &|
|000028c0| 20 39 34 38 20 20 20 20 | 20 20 20 20 20 20 26 20 | 948 | & |
|000028d0| 35 33 31 32 32 30 30 20 | 20 20 20 26 20 35 36 32 |5312200 | & 562|
|000028e0| 39 31 35 38 20 20 20 20 | 20 20 20 20 26 20 31 36 |9158 | & 16|
|000028f0| 33 32 32 38 34 20 20 20 | 5c 5c 20 5c 68 6c 69 6e |32284 |\\ \hlin|
|00002900| 65 0a 35 30 30 20 20 20 | 20 20 20 20 20 20 26 20 |e.500 | & |
|00002910| 34 36 39 38 39 20 20 20 | 20 20 20 20 20 20 26 20 |46989 | & |
|00002920| 36 32 30 30 31 33 20 20 | 20 20 20 26 20 36 34 20 |620013 | & 64 |
|00002930| 20 20 20 20 20 20 20 20 | 20 20 26 20 31 30 39 31 | | & 1091|
|00002940| 39 30 30 20 20 20 20 26 | 20 31 32 38 33 39 30 36 |900 &| 1283906|
|00002950| 20 20 20 20 20 20 20 20 | 26 20 39 37 39 33 38 34 | |& 979384|
|00002960| 20 20 20 20 5c 5c 20 5c | 68 6c 69 6e 65 0a 37 30 | \\ \|hline.70|
|00002970| 30 20 20 20 20 20 20 20 | 20 20 26 20 33 33 32 35 |0 | & 3325|
|00002980| 35 20 20 20 20 20 20 20 | 20 20 26 20 35 37 31 39 |5 | & 5719|
|00002990| 37 30 20 20 20 20 20 26 | 20 32 32 20 20 20 20 20 |70 &| 22 |
|000029a0| 20 20 20 20 20 20 26 20 | 31 33 30 37 38 30 30 20 | & |1307800 |
|000029b0| 20 20 20 26 20 31 34 34 | 34 33 34 36 20 20 20 20 | & 144|4346 |
|000029c0| 20 20 20 20 26 20 36 39 | 39 35 36 34 20 20 20 20 | & 69|9564 |
|000029d0| 5c 5c 20 5c 68 6c 69 6e | 65 0a 39 30 30 20 20 20 |\\ \hlin|e.900 |
|000029e0| 20 20 20 20 20 20 26 20 | 32 35 36 38 36 20 20 20 | & |25686 |
|000029f0| 20 20 20 20 20 20 26 20 | 35 32 35 30 35 38 20 20 | & |525058 |
|00002a00| 20 20 20 26 20 32 34 20 | 20 20 20 20 20 20 20 20 | & 24 | |
|00002a10| 20 20 26 20 31 34 36 39 | 35 30 30 20 20 20 20 26 | & 1469|500 &|
|00002a20| 20 31 35 37 35 34 33 38 | 20 20 20 20 20 20 20 20 | 1575438| |
|00002a30| 26 20 35 34 34 31 32 34 | 20 20 20 20 5c 5c 20 5c |& 544124| \\ \|
|00002a40| 68 6c 69 6e 65 0a 31 31 | 30 30 20 20 20 20 20 20 |hline.11|00 |
|00002a50| 20 20 26 20 32 30 38 34 | 38 20 20 20 20 20 20 20 | & 2084|8 |
|00002a60| 20 20 26 20 34 39 36 38 | 34 34 20 20 20 20 20 26 | & 4968|44 &|
|00002a70| 20 32 31 20 20 20 20 20 | 20 20 20 20 20 20 26 20 | 21 | & |
|00002a80| 31 36 35 34 35 30 30 20 | 20 20 20 26 20 31 37 34 |1654500 | & 174|
|00002a90| 30 38 33 38 20 20 20 20 | 20 20 20 20 26 20 34 34 |0838 | & 44|
|00002aa0| 35 32 30 34 20 20 20 20 | 5c 5c 20 5c 68 6c 69 6e |5204 |\\ \hlin|
|00002ab0| 65 0a 5c 65 6e 64 7b 74 | 61 62 75 6c 61 72 7d 0a |e.\end{t|abular}.|
|00002ac0| 5c 76 73 70 61 63 65 2a | 7b 35 6d 6d 7d 0a 0a 49 |\vspace*|{5mm}..I|
|00002ad0| 6e 20 65 61 63 68 20 63 | 61 73 65 2c 20 74 68 65 |n each c|ase, the|
|00002ae0| 20 43 50 55 20 74 69 6d | 65 20 74 61 6b 65 6e 20 | CPU tim|e taken |
|00002af0| 77 61 73 20 6c 65 73 73 | 20 74 68 61 6e 20 74 68 |was less| than th|
|00002b00| 65 0a 74 69 6d 65 20 69 | 74 20 74 61 6b 65 73 20 |e.time i|t takes |
|00002b10| 74 6f 20 72 75 6e 20 60 | 60 64 69 66 66 27 27 20 |to run `|`diff'' |
|00002b20| 6f 6e 20 74 68 65 20 74 | 77 6f 20 66 69 6c 65 73 |on the t|wo files|
|00002b30| 2e 5c 66 6f 6f 74 6e 6f | 74 65 7b 54 68 65 20 77 |.\footno|te{The w|
|00002b40| 61 6c 6c 0a 20 20 63 6c | 6f 63 6b 20 74 69 6d 65 |all. cl|ock time|
|00002b50| 20 77 61 73 20 61 70 70 | 72 6f 78 69 6d 61 74 65 | was app|roximate|
|00002b60| 6c 79 20 32 20 6d 69 6e | 75 74 65 73 20 70 65 72 |ly 2 min|utes per|
|00002b70| 20 72 75 6e 20 6f 6e 20 | 61 20 35 30 20 4d 48 7a | run on |a 50 MHz|
|00002b80| 20 53 50 41 52 43 20 31 | 30 0a 20 20 72 75 6e 6e | SPARC 1|0. runn|
|00002b90| 69 6e 67 20 53 75 6e 4f | 53 2c 20 75 73 69 6e 67 |ing SunO|S, using|
|00002ba0| 20 72 73 68 20 6f 76 65 | 72 20 6c 6f 6f 70 62 61 | rsh ove|r loopba|
|00002bb0| 63 6b 20 66 6f 72 20 63 | 6f 6d 6d 75 6e 69 63 61 |ck for c|ommunica|
|00002bc0| 74 69 6f 6e 2e 20 20 47 | 4e 55 20 64 69 66 66 0a |tion. G|NU diff.|
|00002bd0| 20 20 74 6f 6f 6b 20 61 | 62 6f 75 74 20 34 20 6d | took a|bout 4 m|
|00002be0| 69 6e 75 74 65 73 2e 7d | 0a 0a 54 68 65 20 63 6f |inutes.}|..The co|
|00002bf0| 6c 75 6d 6e 73 20 69 6e | 20 74 68 65 20 74 61 62 |lumns in| the tab|
|00002c00| 6c 65 20 61 72 65 20 61 | 73 20 66 6f 6c 6c 6f 77 |le are a|s follow|
|00002c10| 73 3a 0a 0a 5c 62 65 67 | 69 6e 7b 64 65 73 63 72 |s:..\beg|in{descr|
|00002c20| 69 70 74 69 6f 6e 7d 0a | 5c 69 74 65 6d 20 5b 62 |iption}.|\item [b|
|00002c30| 6c 6f 63 6b 20 73 69 7a | 65 5d 20 54 68 65 20 73 |lock siz|e] The s|
|00002c40| 69 7a 65 20 69 6e 20 62 | 79 74 65 73 20 6f 66 20 |ize in b|ytes of |
|00002c50| 74 68 65 20 63 68 65 63 | 6b 73 75 6d 6d 65 64 20 |the chec|ksummed |
|00002c60| 62 6c 6f 63 6b 73 2e 0a | 5c 69 74 65 6d 20 5b 6d |blocks..|\item [m|
|00002c70| 61 74 63 68 65 73 5d 20 | 54 68 65 20 6e 75 6d 62 |atches] |The numb|
|00002c80| 65 72 20 6f 66 20 74 69 | 6d 65 73 20 61 20 62 6c |er of ti|mes a bl|
|00002c90| 6f 63 6b 20 6f 66 20 24 | 42 24 20 77 61 73 20 66 |ock of $|B$ was f|
|00002ca0| 6f 75 6e 64 20 69 6e 20 | 24 41 24 2e 0a 5c 69 74 |ound in |$A$..\it|
|00002cb0| 65 6d 20 5b 74 61 67 20 | 68 69 74 73 5d 20 54 68 |em [tag |hits] Th|
|00002cc0| 65 20 6e 75 6d 62 65 72 | 20 6f 66 20 74 69 6d 65 |e number| of time|
|00002cd0| 73 20 74 68 65 20 31 36 | 20 62 69 74 20 68 61 73 |s the 16| bit has|
|00002ce0| 68 20 6f 66 20 74 68 65 | 20 72 6f 6c 6c 69 6e 67 |h of the| rolling|
|00002cf0| 0a 20 20 63 68 65 63 6b | 73 75 6d 20 6d 61 74 63 |. check|sum matc|
|00002d00| 68 65 64 20 61 20 68 61 | 73 68 20 6f 66 20 6f 6e |hed a ha|sh of on|
|00002d10| 65 20 6f 66 20 74 68 65 | 20 63 68 65 63 6b 73 75 |e of the| checksu|
|00002d20| 6d 73 20 66 72 6f 6d 20 | 24 42 24 2e 0a 5c 69 74 |ms from |$B$..\it|
|00002d30| 65 6d 20 5b 66 61 6c 73 | 65 20 61 6c 61 72 6d 73 |em [fals|e alarms|
|00002d40| 5d 20 54 68 65 20 6e 75 | 6d 62 65 72 20 6f 66 20 |] The nu|mber of |
|00002d50| 74 69 6d 65 73 20 74 68 | 65 20 33 32 20 62 69 74 |times th|e 32 bit|
|00002d60| 20 72 6f 6c 6c 69 6e 67 | 20 63 68 65 63 6b 73 75 | rolling| checksu|
|00002d70| 6d 0a 20 20 6d 61 74 63 | 68 65 64 20 62 75 74 20 |m. matc|hed but |
|00002d80| 74 68 65 20 73 74 72 6f | 6e 67 20 63 68 65 63 6b |the stro|ng check|
|00002d90| 73 75 6d 20 64 69 64 6e | 27 74 2e 0a 5c 69 74 65 |sum didn|'t..\ite|
|00002da0| 6d 20 5b 64 61 74 61 5d | 20 54 68 65 20 61 6d 6f |m [data]| The amo|
|00002db0| 75 6e 74 20 6f 66 20 66 | 69 6c 65 20 64 61 74 61 |unt of f|ile data|
|00002dc0| 20 74 72 61 6e 73 66 65 | 72 72 65 64 20 76 65 72 | transfe|rred ver|
|00002dd0| 62 61 74 69 6d 2c 20 69 | 6e 20 62 79 74 65 73 2e |batim, i|n bytes.|
|00002de0| 0a 5c 69 74 65 6d 20 5b | 77 72 69 74 74 65 6e 5d |.\item [|written]|
|00002df0| 20 54 68 65 20 74 6f 74 | 61 6c 20 6e 75 6d 62 65 | The tot|al numbe|
|00002e00| 72 20 6f 66 20 62 79 74 | 65 73 20 77 72 69 74 74 |r of byt|es writt|
|00002e10| 65 6e 20 62 79 20 24 5c | 61 6c 70 68 61 24 0a 20 |en by $\|alpha$. |
|00002e20| 20 69 6e 63 6c 75 64 69 | 6e 67 20 70 72 6f 74 6f | includi|ng proto|
|00002e30| 63 6f 6c 20 6f 76 65 72 | 68 65 61 64 73 2e 20 54 |col over|heads. T|
|00002e40| 68 69 73 20 69 73 20 61 | 6c 6d 6f 73 74 20 61 6c |his is a|lmost al|
|00002e50| 6c 20 66 69 6c 65 20 64 | 61 74 61 2e 0a 5c 69 74 |l file d|ata..\it|
|00002e60| 65 6d 20 5b 72 65 61 64 | 5d 20 54 68 65 20 74 6f |em [read|] The to|
|00002e70| 74 61 6c 20 6e 75 6d 62 | 65 72 20 6f 66 20 62 79 |tal numb|er of by|
|00002e80| 74 65 73 20 72 65 61 64 | 20 62 79 20 24 5c 61 6c |tes read| by $\al|
|00002e90| 70 68 61 24 20 69 6e 63 | 6c 75 64 69 6e 67 0a 20 |pha$ inc|luding. |
|00002ea0| 20 70 72 6f 74 6f 63 6f | 6c 20 6f 76 65 72 68 65 | protoco|l overhe|
|00002eb0| 61 64 73 2e 20 54 68 69 | 73 20 69 73 20 61 6c 6d |ads. Thi|s is alm|
|00002ec0| 6f 73 74 20 61 6c 6c 20 | 63 68 65 63 6b 73 75 6d |ost all |checksum|
|00002ed0| 20 69 6e 66 6f 72 6d 61 | 74 69 6f 6e 2e 0a 5c 65 | informa|tion..\e|
|00002ee0| 6e 64 7b 64 65 73 63 72 | 69 70 74 69 6f 6e 7d 0a |nd{descr|iption}.|
|00002ef0| 0a 54 68 65 20 72 65 73 | 75 6c 74 73 20 64 65 6d |.The res|ults dem|
|00002f00| 6f 6e 73 74 72 61 74 65 | 20 74 68 61 74 20 66 6f |onstrate| that fo|
|00002f10| 72 20 62 6c 6f 63 6b 20 | 73 69 7a 65 73 20 61 62 |r block |sizes ab|
|00002f20| 6f 76 65 20 33 30 30 20 | 62 79 74 65 73 2c 20 6f |ove 300 |bytes, o|
|00002f30| 6e 6c 79 20 61 0a 73 6d | 61 6c 6c 20 66 72 61 63 |nly a.sm|all frac|
|00002f40| 74 69 6f 6e 20 28 61 72 | 6f 75 6e 64 20 35 5c 25 |tion (ar|ound 5\%|
|00002f50| 29 20 6f 66 20 74 68 65 | 20 66 69 6c 65 20 77 61 |) of the| file wa|
|00002f60| 73 20 74 72 61 6e 73 66 | 65 72 72 65 64 2e 20 54 |s transf|erred. T|
|00002f70| 68 65 20 61 6d 6f 75 6e | 74 0a 74 72 61 6e 73 66 |he amoun|t.transf|
|00002f80| 65 72 72 65 64 20 77 61 | 73 20 61 6c 73 6f 20 63 |erred wa|s also c|
|00002f90| 6f 6e 73 69 64 65 72 61 | 62 6c 79 20 6c 65 73 73 |onsidera|bly less|
|00002fa0| 20 74 68 61 6e 20 74 68 | 65 20 73 69 7a 65 20 6f | than th|e size o|
|00002fb0| 66 20 74 68 65 20 64 69 | 66 66 20 66 69 6c 65 0a |f the di|ff file.|
|00002fc0| 74 68 61 74 20 77 6f 75 | 6c 64 20 68 61 76 65 20 |that wou|ld have |
|00002fd0| 62 65 65 6e 20 74 72 61 | 6e 73 66 65 72 72 65 64 |been tra|nsferred|
|00002fe0| 20 69 66 20 74 68 65 20 | 64 69 66 66 2f 70 61 74 | if the |diff/pat|
|00002ff0| 63 68 20 6d 65 74 68 6f | 64 20 6f 66 20 75 70 64 |ch metho|d of upd|
|00003000| 61 74 69 6e 67 0a 61 20 | 72 65 6d 6f 74 65 20 66 |ating.a |remote f|
|00003010| 69 6c 65 20 77 61 73 20 | 75 73 65 64 2e 0a 0a 54 |ile was |used...T|
|00003020| 68 65 20 63 68 65 63 6b | 73 75 6d 73 20 74 68 65 |he check|sums the|
|00003030| 6d 73 65 6c 76 65 73 20 | 74 6f 6f 6b 20 75 70 20 |mselves |took up |
|00003040| 61 20 63 6f 6e 73 69 64 | 65 72 61 62 6c 65 20 61 |a consid|erable a|
|00003050| 6d 6f 75 6e 74 20 6f 66 | 20 73 70 61 63 65 2c 0a |mount of| space,.|
|00003060| 61 6c 74 68 6f 75 67 68 | 20 6d 75 63 68 20 6c 65 |although| much le|
|00003070| 73 73 20 74 68 61 6e 20 | 74 68 65 20 73 69 7a 65 |ss than |the size|
|00003080| 20 6f 66 20 74 68 65 20 | 64 61 74 61 20 74 72 61 | of the |data tra|
|00003090| 6e 73 66 65 72 72 65 64 | 20 69 6e 20 65 61 63 68 |nsferred| in each|
|000030a0| 0a 63 61 73 65 2e 20 45 | 61 63 68 20 70 61 69 72 |.case. E|ach pair|
|000030b0| 20 6f 66 20 63 68 65 63 | 6b 73 75 6d 73 20 63 6f | of chec|ksums co|
|000030c0| 6e 73 75 6d 65 73 20 32 | 30 20 62 79 74 65 73 3a |nsumes 2|0 bytes:|
|000030d0| 20 34 20 62 79 74 65 73 | 20 66 6f 72 20 74 68 65 | 4 bytes| for the|
|000030e0| 0a 72 6f 6c 6c 69 6e 67 | 20 63 68 65 63 6b 73 75 |.rolling| checksu|
|000030f0| 6d 20 70 6c 75 73 20 31 | 36 20 62 79 74 65 73 20 |m plus 1|6 bytes |
|00003100| 66 6f 72 20 74 68 65 20 | 31 32 38 2d 62 69 74 20 |for the |128-bit |
|00003110| 4d 44 34 20 63 68 65 63 | 6b 73 75 6d 2e 0a 0a 54 |MD4 chec|ksum...T|
|00003120| 68 65 20 6e 75 6d 62 65 | 72 20 6f 66 20 66 61 6c |he numbe|r of fal|
|00003130| 73 65 20 61 6c 61 72 6d | 73 20 77 61 73 20 6c 65 |se alarm|s was le|
|00003140| 73 73 20 74 68 61 6e 20 | 24 31 2f 31 30 30 30 24 |ss than |$1/1000$|
|00003150| 20 6f 66 20 74 68 65 20 | 6e 75 6d 62 65 72 20 6f | of the |number o|
|00003160| 66 0a 74 72 75 65 20 6d | 61 74 63 68 65 73 2c 20 |f.true m|atches, |
|00003170| 69 6e 64 69 63 61 74 69 | 6e 67 20 74 68 61 74 20 |indicati|ng that |
|00003180| 74 68 65 20 33 32 20 62 | 69 74 20 72 6f 6c 6c 69 |the 32 b|it rolli|
|00003190| 6e 67 20 63 68 65 63 6b | 73 75 6d 20 69 73 20 71 |ng check|sum is q|
|000031a0| 75 69 74 65 0a 67 6f 6f | 64 20 61 74 20 73 63 72 |uite.goo|d at scr|
|000031b0| 65 65 6e 69 6e 67 20 6f | 75 74 20 66 61 6c 73 65 |eening o|ut false|
|000031c0| 20 6d 61 74 63 68 65 73 | 2e 20 0a 0a 54 68 65 20 | matches|. ..The |
|000031d0| 6e 75 6d 62 65 72 20 6f | 66 20 74 61 67 20 68 69 |number o|f tag hi|
|000031e0| 74 73 20 69 6e 64 69 63 | 61 74 65 73 20 74 68 61 |ts indic|ates tha|
|000031f0| 74 20 74 68 65 20 73 65 | 63 6f 6e 64 20 6c 65 76 |t the se|cond lev|
|00003200| 65 6c 20 6f 66 20 74 68 | 65 0a 63 68 65 63 6b 73 |el of th|e.checks|
|00003210| 75 6d 20 73 65 61 72 63 | 68 20 61 6c 67 6f 72 69 |um searc|h algori|
|00003220| 74 68 6d 20 77 61 73 20 | 69 6e 76 6f 6b 65 64 20 |thm was |invoked |
|00003230| 61 62 6f 75 74 20 6f 6e | 63 65 20 65 76 65 72 79 |about on|ce every|
|00003240| 20 35 30 0a 63 68 61 72 | 61 63 74 65 72 73 2e 20 | 50.char|acters. |
|00003250| 20 54 68 69 73 20 69 73 | 20 71 75 69 74 65 20 68 | This is| quite h|
|00003260| 69 67 68 20 62 65 63 61 | 75 73 65 20 74 68 65 20 |igh beca|use the |
|00003270| 74 6f 74 61 6c 20 6e 75 | 6d 62 65 72 20 6f 66 20 |total nu|mber of |
|00003280| 62 6c 6f 63 6b 73 20 69 | 6e 0a 74 68 65 20 66 69 |blocks i|n.the fi|
|00003290| 6c 65 20 69 73 20 61 20 | 6c 61 72 67 65 20 66 72 |le is a |large fr|
|000032a0| 61 63 74 69 6f 6e 20 6f | 66 20 74 68 65 20 73 69 |action o|f the si|
|000032b0| 7a 65 20 6f 66 20 74 68 | 65 20 74 61 67 20 68 61 |ze of th|e tag ha|
|000032c0| 73 68 20 74 61 62 6c 65 | 2e 20 46 6f 72 0a 73 6d |sh table|. For.sm|
|000032d0| 61 6c 6c 65 72 20 66 69 | 6c 65 73 20 77 65 20 77 |aller fi|les we w|
|000032e0| 6f 75 6c 64 20 65 78 70 | 65 63 74 20 74 68 65 20 |ould exp|ect the |
|000032f0| 74 61 67 20 68 69 74 20 | 72 61 74 65 20 74 6f 20 |tag hit |rate to |
|00003300| 62 65 20 6d 75 63 68 20 | 63 6c 6f 73 65 72 20 74 |be much |closer t|
|00003310| 6f 0a 74 68 65 20 6e 75 | 6d 62 65 72 20 6f 66 20 |o.the nu|mber of |
|00003320| 6d 61 74 63 68 65 73 2e | 20 20 46 6f 72 20 65 78 |matches.| For ex|
|00003330| 74 72 65 6d 65 6c 79 20 | 6c 61 72 67 65 20 66 69 |tremely |large fi|
|00003340| 6c 65 73 2c 20 77 65 20 | 73 68 6f 75 6c 64 20 70 |les, we |should p|
|00003350| 72 6f 62 61 62 6c 79 0a | 69 6e 63 72 65 61 73 65 |robably.|increase|
|00003360| 20 74 68 65 20 73 69 7a | 65 20 6f 66 20 74 68 65 | the siz|e of the|
|00003370| 20 68 61 73 68 20 74 61 | 62 6c 65 2e 0a 0a 54 68 | hash ta|ble...Th|
|00003380| 65 20 6e 65 78 74 20 74 | 61 62 6c 65 20 73 68 6f |e next t|able sho|
|00003390| 77 73 20 73 69 6d 69 6c | 61 72 20 72 65 73 75 6c |ws simil|ar resul|
|000033a0| 74 73 20 66 6f 72 20 61 | 20 6d 75 63 68 20 73 6d |ts for a| much sm|
|000033b0| 61 6c 6c 65 72 20 73 65 | 74 20 6f 66 20 66 69 6c |aller se|t of fil|
|000033c0| 65 73 2e 0a 49 6e 20 74 | 68 69 73 20 63 61 73 65 |es..In t|his case|
|000033d0| 20 74 68 65 20 66 69 6c | 65 73 20 77 65 72 65 20 | the fil|es were |
|000033e0| 6e 6f 74 20 70 61 63 6b | 65 64 20 69 6e 74 6f 20 |not pack|ed into |
|000033f0| 61 20 74 61 72 20 66 69 | 6c 65 20 66 69 72 73 74 |a tar fi|le first|
|00003400| 2e 20 52 61 74 68 65 72 | 2c 0a 72 73 79 6e 63 20 |. Rather|,.rsync |
|00003410| 77 61 73 20 69 6e 76 6f | 6b 65 64 20 77 69 74 68 |was invo|ked with|
|00003420| 20 61 6e 20 6f 70 74 69 | 6f 6e 20 74 6f 20 72 65 | an opti|on to re|
|00003430| 63 75 72 73 69 76 65 6c | 79 20 64 65 73 63 65 6e |cursivel|y descen|
|00003440| 64 20 74 68 65 20 64 69 | 72 65 63 74 6f 72 79 0a |d the di|rectory.|
|00003450| 74 72 65 65 2e 20 54 68 | 65 20 66 69 6c 65 73 20 |tree. Th|e files |
|00003460| 75 73 65 64 20 77 65 72 | 65 20 66 72 6f 6d 20 74 |used wer|e from t|
|00003470| 77 6f 20 73 6f 75 72 63 | 65 20 72 65 6c 65 61 73 |wo sourc|e releas|
|00003480| 65 73 20 6f 66 20 61 6e | 6f 74 68 65 72 20 73 6f |es of an|other so|
|00003490| 66 74 77 61 72 65 0a 70 | 61 63 6b 61 67 65 20 63 |ftware.p|ackage c|
|000034a0| 61 6c 6c 65 64 20 53 61 | 6d 62 61 2e 20 54 68 65 |alled Sa|mba. The|
|000034b0| 20 74 6f 74 61 6c 20 73 | 6f 75 72 63 65 20 63 6f | total s|ource co|
|000034c0| 64 65 20 73 69 7a 65 20 | 69 73 20 31 2e 37 20 4d |de size |is 1.7 M|
|000034d0| 42 20 61 6e 64 20 74 68 | 65 0a 64 69 66 66 20 62 |B and th|e.diff b|
|000034e0| 65 74 77 65 65 6e 20 74 | 68 65 20 74 77 6f 20 72 |etween t|he two r|
|000034f0| 65 6c 65 61 73 65 73 20 | 69 73 20 34 31 35 35 20 |eleases |is 4155 |
|00003500| 6c 69 6e 65 73 20 6c 6f | 6e 67 20 74 6f 74 61 6c |lines lo|ng total|
|00003510| 6c 69 6e 67 20 31 32 30 | 20 6b 42 2e 0a 0a 5c 76 |ling 120| kB...\v|
|00003520| 73 70 61 63 65 2a 7b 35 | 6d 6d 7d 0a 5c 62 65 67 |space*{5|mm}.\beg|
|00003530| 69 6e 7b 74 61 62 75 6c | 61 72 7d 7b 7c 6c 7c 6c |in{tabul|ar}{|l|l|
|00003540| 7c 6c 7c 6c 7c 6c 7c 6c | 7c 6c 7c 7d 20 5c 68 6c ||l|l|l|l||l|} \hl|
|00003550| 69 6e 65 0a 7b 5c 62 66 | 20 62 6c 6f 63 6b 7d 20 |ine.{\bf| block} |
|00003560| 26 20 7b 5c 62 66 20 6d | 61 74 63 68 65 73 7d 20 |& {\bf m|atches} |
|00003570| 26 20 7b 5c 62 66 20 74 | 61 67 7d 20 20 26 20 7b |& {\bf t|ag} & {|
|00003580| 5c 62 66 20 66 61 6c 73 | 65 7d 20 20 26 20 7b 5c |\bf fals|e} & {\|
|00003590| 62 66 20 64 61 74 61 7d | 20 26 20 7b 5c 62 66 20 |bf data}| & {\bf |
|000035a0| 77 72 69 74 74 65 6e 7d | 20 20 26 20 7b 5c 62 66 |written}| & {\bf|
|000035b0| 20 72 65 61 64 7d 20 5c | 5c 0a 7b 5c 62 66 20 73 | read} \|\.{\bf s|
|000035c0| 69 7a 65 7d 20 20 26 20 | 20 20 20 20 20 20 20 20 |ize} & | |
|000035d0| 20 20 20 20 20 20 26 20 | 7b 5c 62 66 20 68 69 74 | & |{\bf hit|
|000035e0| 73 7d 20 26 20 7b 5c 62 | 66 20 61 6c 61 72 6d 73 |s} & {\b|f alarms|
|000035f0| 7d 20 26 20 20 20 20 20 | 20 20 20 20 20 20 20 26 |} & | &|
|00003600| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003610| 26 20 20 20 20 20 20 20 | 20 20 20 20 20 5c 5c 20 |& | \\ |
|00003620| 5c 68 6c 69 6e 65 20 5c | 68 6c 69 6e 65 0a 0a 33 |\hline \|hline..3|
|00003630| 30 30 20 20 20 20 20 20 | 20 20 20 26 20 33 37 32 |00 | & 372|
|00003640| 37 20 20 20 20 20 20 20 | 20 20 20 26 20 33 38 39 |7 | & 389|
|00003650| 39 20 20 20 20 20 20 20 | 26 20 30 20 20 20 20 20 |9 |& 0 |
|00003660| 20 20 20 20 20 20 20 26 | 20 31 32 39 37 37 35 20 | &| 129775 |
|00003670| 20 20 20 20 26 20 31 35 | 33 39 39 39 20 20 20 20 | & 15|3999 |
|00003680| 20 20 20 20 20 26 20 38 | 33 39 34 38 20 20 20 20 | & 8|3948 |
|00003690| 20 20 20 5c 5c 20 5c 68 | 6c 69 6e 65 0a 35 30 30 | \\ \h|line.500|
|000036a0| 20 20 20 20 20 20 20 20 | 20 26 20 32 31 35 38 20 | | & 2158 |
|000036b0| 20 20 20 20 20 20 20 20 | 20 26 20 32 33 32 35 20 | | & 2325 |
|000036c0| 20 20 20 20 20 20 26 20 | 30 20 20 20 20 20 20 20 | & |0 |
|000036d0| 20 20 20 20 20 26 20 31 | 37 31 35 37 34 20 20 20 | & 1|71574 |
|000036e0| 20 20 26 20 31 38 39 33 | 33 30 20 20 20 20 20 20 | & 1893|30 |
|000036f0| 20 20 20 26 20 35 30 39 | 30 38 20 20 20 20 20 20 | & 509|08 |
|00003700| 20 5c 5c 20 5c 68 6c 69 | 6e 65 0a 37 30 30 20 20 | \\ \hli|ne.700 |
|00003710| 20 20 20 20 20 20 20 26 | 20 31 35 31 37 20 20 20 | &| 1517 |
|00003720| 20 20 20 20 20 20 20 26 | 20 31 36 34 39 20 20 20 | &| 1649 |
|00003730| 20 20 20 20 26 20 30 20 | 20 20 20 20 20 20 20 20 | & 0 | |
|00003740| 20 20 20 26 20 31 39 35 | 30 32 34 20 20 20 20 20 | & 195|024 |
|00003750| 26 20 32 31 30 31 34 34 | 20 20 20 20 20 20 20 20 |& 210144| |
|00003760| 20 26 20 33 36 38 32 38 | 20 20 20 20 20 20 20 20 | & 36828| |
|00003770| 5c 5c 20 5c 68 6c 69 6e | 65 0a 39 30 30 20 20 20 |\\ \hlin|e.900 |
|00003780| 20 20 20 20 20 20 26 20 | 31 31 35 36 20 20 20 20 | & |1156 |
|00003790| 20 20 20 20 20 20 26 20 | 31 32 38 31 20 20 20 20 | & |1281 |
|000037a0| 20 20 20 26 20 30 20 20 | 20 20 20 20 20 20 20 20 | & 0 | |
|000037b0| 20 20 26 20 32 32 32 38 | 34 37 20 20 20 20 20 26 | & 2228|47 &|
|000037c0| 20 32 33 36 34 37 31 20 | 20 20 20 20 20 20 20 20 | 236471 | |
|000037d0| 26 20 32 39 30 34 38 20 | 20 20 20 20 20 20 20 5c |& 29048 | \|
|000037e0| 5c 20 5c 68 6c 69 6e 65 | 0a 31 31 30 30 20 20 20 |\ \hline|.1100 |
|000037f0| 20 20 20 20 20 26 20 39 | 32 31 20 20 20 20 20 20 | & 9|21 |
|00003800| 20 20 20 20 20 26 20 31 | 30 34 39 20 20 20 20 20 | & 1|049 |
|00003810| 20 20 26 20 30 20 20 20 | 20 20 20 20 20 20 20 20 | & 0 | |
|00003820| 20 26 20 32 35 30 30 37 | 33 20 20 20 20 20 26 20 | & 25007|3 & |
|00003830| 32 36 32 37 32 35 20 20 | 20 20 20 20 20 20 20 26 |262725 | &|
|00003840| 20 32 33 39 38 38 20 20 | 20 20 20 20 20 20 5c 5c | 23988 | \\|
|00003850| 20 5c 68 6c 69 6e 65 0a | 5c 65 6e 64 7b 74 61 62 | \hline.|\end{tab|
|00003860| 75 6c 61 72 7d 0a 5c 76 | 73 70 61 63 65 2a 7b 35 |ular}.\v|space*{5|
|00003870| 6d 6d 7d 0a 0a 0a 5c 73 | 65 63 74 69 6f 6e 7b 41 |mm}...\s|ection{A|
|00003880| 76 61 69 6c 61 62 69 6c | 69 74 79 7d 0a 0a 41 6e |vailabil|ity}..An|
|00003890| 20 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 20 | impleme|ntation |
|000038a0| 6f 66 20 72 73 79 6e 63 | 20 77 68 69 63 68 20 70 |of rsync| which p|
|000038b0| 72 6f 76 69 64 65 73 20 | 61 20 63 6f 6e 76 65 6e |rovides |a conven|
|000038c0| 69 65 6e 74 20 69 6e 74 | 65 72 66 61 63 65 0a 73 |ient int|erface.s|
|000038d0| 69 6d 69 6c 61 72 20 74 | 6f 20 74 68 65 20 63 6f |imilar t|o the co|
|000038e0| 6d 6d 6f 6e 20 55 4e 49 | 58 20 63 6f 6d 6d 61 6e |mmon UNI|X comman|
|000038f0| 64 20 72 63 70 20 68 61 | 73 20 62 65 65 6e 20 77 |d rcp ha|s been w|
|00003900| 72 69 74 74 65 6e 20 61 | 6e 64 20 69 73 0a 61 76 |ritten a|nd is.av|
|00003910| 61 69 6c 61 62 6c 65 20 | 66 6f 72 20 64 6f 77 6e |ailable |for down|
|00003920| 6c 6f 61 64 20 66 72 6f | 6d 20 66 74 70 3a 2f 2f |load fro|m ftp://|
|00003930| 73 61 6d 62 61 2e 61 6e | 75 2e 65 64 75 2e 61 75 |samba.an|u.edu.au|
|00003940| 2f 70 75 62 2f 72 73 79 | 6e 63 2e 0a 0a 5c 65 6e |/pub/rsy|nc...\en|
|00003950| 64 7b 64 6f 63 75 6d 65 | 6e 74 7d 0a |d{docume|nt}. |
+--------+-------------------------+-------------------------+--------+--------+
