/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / pascal / LZRW.ZIP / LZRW1.TEX

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |%=======|========|
|00000010| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00000020| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00000030| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00000040| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00000050| 0a 25 0a 25 20 54 68 69 | 73 20 64 6f 63 75 6d 65 |.%.% Thi|s docume|
|00000060| 6e 74 20 63 6f 6e 74 61 | 69 6e 73 20 74 68 65 20 |nt conta|ins the |
|00000070| 70 61 70 65 72 3a 0a 25 | 0a 25 20 20 20 20 22 41 |paper:.%|.%    "A|
|00000080| 6e 20 45 78 74 72 65 6d | 65 6c 79 20 46 61 73 74 |n Extrem|ely Fast|
|00000090| 20 5a 69 76 2d 4c 65 6d | 70 65 6c 20 44 61 74 61 | Ziv-Lem|pel Data|
|000000a0| 20 43 6f 6d 70 72 65 73 | 73 69 6f 6e 20 41 6c 67 | Compres|sion Alg|
|000000b0| 6f 72 69 74 68 6d 22 2c | 0a 25 20 20 20 20 49 45 |orithm",|.%    IE|
|000000c0| 45 45 20 43 6f 6d 70 75 | 74 65 72 20 53 6f 63 69 |EE Compu|ter Soci|
|000000d0| 65 74 79 20 44 61 74 61 | 20 43 6f 6d 70 72 65 73 |ety Data| Compres|
|000000e0| 73 69 6f 6e 20 43 6f 6e | 66 65 72 65 6e 63 65 2c |sion Con|ference,|
|000000f0| 0a 25 20 20 20 20 38 2d | 31 31 20 41 70 72 69 6c |.%    8-|11 April|
|00000100| 20 31 39 39 31 2c 20 53 | 6e 6f 77 62 69 72 64 2c | 1991, S|nowbird,|
|00000110| 20 55 74 61 68 2c 0a 25 | 20 20 20 20 45 64 69 74 | Utah,.%|    Edit|
|00000120| 65 64 20 62 79 20 4a 61 | 6d 65 73 20 41 2e 20 53 |ed by Ja|mes A. S|
|00000130| 74 6f 72 65 72 20 61 6e | 64 20 4a 6f 68 6e 20 48 |torer an|d John H|
|00000140| 2e 20 52 65 69 66 2e 0a | 25 0a 25 20 52 65 70 72 |. Reif..|%.% Repr|
|00000150| 69 6e 74 73 20 63 61 6e | 20 62 65 20 6f 62 74 61 |ints can| be obta|
|00000160| 69 6e 65 64 20 66 72 6f | 6d 20 74 68 65 20 49 45 |ined fro|m the IE|
|00000170| 45 45 20 66 72 6f 6d 20 | 77 68 6f 6d 20 74 68 65 |EE from |whom the|
|00000180| 20 65 6e 74 69 72 65 20 | 63 6f 6e 66 65 72 65 6e | entire |conferen|
|00000190| 63 65 0a 25 20 70 72 6f | 63 65 65 64 69 6e 67 73 |ce.% pro|ceedings|
|000001a0| 20 61 72 65 20 61 6c 73 | 6f 20 61 76 61 69 6c 61 | are als|o availa|
|000001b0| 62 6c 65 2e 0a 25 0a 25 | 20 20 20 49 45 45 45 20 |ble..%.%|   IEEE |
|000001c0| 43 6f 6d 70 75 74 65 72 | 20 53 6f 63 69 65 74 79 |Computer| Society|
|000001d0| 0a 25 20 20 20 50 4f 20 | 42 6f 78 20 33 30 31 34 |.%   PO |Box 3014|
|000001e0| 0a 25 20 20 20 31 30 36 | 36 32 20 4c 6f 73 20 56 |.%   106|62 Los V|
|000001f0| 61 71 75 65 72 6f 73 20 | 43 69 72 63 6c 65 0a 25 |aqueros |Circle.%|
|00000200| 20 20 20 4c 6f 73 20 41 | 6c 61 6d 69 74 6f 73 20 |   Los A|lamitos |
|00000210| 43 41 20 39 30 37 32 30 | 2d 31 32 36 34 0a 25 20 |CA 90720|-1264.% |
|00000220| 20 20 55 53 41 0a 25 20 | 20 20 50 68 3a 20 2b 31 |  USA.% |  Ph: +1|
|00000230| 20 28 37 31 34 29 20 38 | 32 31 2d 38 33 38 30 0a | (714) 8|21-8380.|
|00000240| 25 0a 25 20 54 68 65 20 | 66 75 6e 6e 79 20 49 45 |%.% The |funny IE|
|00000250| 45 45 20 64 69 67 69 74 | 73 20 61 70 70 65 61 72 |EE digit|s appear|
|00000260| 69 6e 67 20 69 6e 20 74 | 68 65 20 70 72 6f 63 65 |ing in t|he proce|
|00000270| 65 64 69 6e 67 73 20 62 | 65 6e 65 61 74 68 20 6d |edings b|eneath m|
|00000280| 79 20 70 61 70 65 72 0a | 25 20 61 72 65 3a 20 54 |y paper.|% are: T|
|00000290| 48 30 33 37 33 2d 31 2f | 39 31 2f 30 30 30 30 2f |H0373-1/|91/0000/|
|000002a0| 30 33 36 32 2f 24 30 31 | 2e 30 30 20 28 63 29 20 |0362/$01|.00 (c) |
|000002b0| 31 39 39 31 20 49 45 45 | 45 0a 25 0a 25 20 54 68 |1991 IEE|E.%.% Th|
|000002c0| 65 20 70 61 70 65 72 20 | 69 73 20 69 6e 20 4c 61 |e paper |is in La|
|000002d0| 54 65 58 20 66 6f 72 6d | 61 74 2e 20 54 68 65 20 |TeX form|at. The |
|000002e0| 65 6e 74 69 72 65 20 74 | 65 78 74 20 69 73 20 68 |entire t|ext is h|
|000002f0| 65 72 65 20 62 75 74 20 | 74 68 65 20 64 69 61 67 |ere but |the diag|
|00000300| 72 61 6d 73 20 77 65 72 | 65 0a 25 20 63 72 65 61 |rams wer|e.% crea|
|00000310| 74 65 64 20 75 73 69 6e | 67 20 61 20 64 72 61 77 |ted usin|g a draw|
|00000320| 69 6e 67 20 70 72 6f 67 | 72 61 6d 2c 20 70 72 69 |ing prog|ram, pri|
|00000330| 6e 74 65 64 20 61 6e 64 | 20 73 74 75 63 6b 20 69 |nted and| stuck i|
|00000340| 6e 20 73 65 70 61 72 61 | 74 65 6c 79 2c 20 73 6f |n separa|tely, so|
|00000350| 20 68 65 72 65 0a 25 20 | 74 68 65 72 65 20 61 72 | here.% |there ar|
|00000360| 65 20 6a 75 73 74 20 62 | 6c 61 6e 6b 20 73 70 61 |e just b|lank spa|
|00000370| 63 65 73 20 77 68 65 72 | 65 20 74 68 65 20 64 69 |ces wher|e the di|
|00000380| 61 67 72 61 6d 73 20 61 | 72 65 20 73 75 70 70 6f |agrams a|re suppo|
|00000390| 73 65 64 20 74 6f 20 62 | 65 2e 0a 25 0a 25 20 54 |sed to b|e..%.% T|
|000003a0| 6f 20 74 79 70 65 73 65 | 74 20 74 68 69 73 20 64 |o typese|t this d|
|000003b0| 6f 63 75 6d 65 6e 74 20 | 79 6f 75 20 6e 65 65 64 |ocument |you need|
|000003c0| 20 74 6f 20 67 69 76 65 | 20 74 68 65 20 22 6c 61 | to give| the "la|
|000003d0| 74 65 78 22 20 63 6f 6d | 6d 61 6e 64 2c 20 6e 6f |tex" com|mand, no|
|000003e0| 74 20 74 68 65 0a 25 20 | 22 74 65 78 22 20 63 6f |t the.% |"tex" co|
|000003f0| 6d 6d 61 6e 64 2e 20 4c | 61 74 65 78 20 77 69 6c |mmand. L|atex wil|
|00000400| 6c 20 67 65 6e 65 72 61 | 74 65 20 61 20 22 2e 64 |l genera|te a ".d|
|00000410| 76 69 22 20 66 69 6c 65 | 20 77 68 69 63 68 20 63 |vi" file| which c|
|00000420| 61 6e 20 74 68 65 6e 20 | 62 65 20 70 72 69 6e 74 |an then |be print|
|00000430| 65 64 0a 25 20 75 73 69 | 6e 67 20 61 20 73 70 65 |ed.% usi|ng a spe|
|00000440| 63 69 61 6c 20 70 72 69 | 6e 74 69 6e 67 20 63 6f |cial pri|nting co|
|00000450| 6d 6d 61 6e 64 20 28 73 | 75 63 68 20 61 73 20 22 |mmand (s|uch as "|
|00000460| 6c 70 72 20 2d 20 64 22 | 29 2e 20 53 65 65 20 79 |lpr - d"|). See y|
|00000470| 6f 75 72 20 6c 6f 63 61 | 6c 0a 25 20 74 79 70 65 |our loca|l.% type|
|00000480| 73 65 74 74 69 6e 67 20 | 47 75 72 75 20 66 6f 72 |setting |Guru for|
|00000490| 20 6d 6f 72 65 20 69 6e | 66 6f 72 6d 61 74 69 6f | more in|formatio|
|000004a0| 6e 2e 0a 25 0a 25 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |n..%.%==|========|
|000004b0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000004c0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000004d0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000004e0| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|000004f0| 3d 3d 3d 3d 3d 0a 0a 5c | 64 6f 63 75 6d 65 6e 74 |=====..\|document|
|00000500| 73 74 79 6c 65 5b 31 32 | 70 74 5d 7b 61 72 74 69 |style[12|pt]{arti|
|00000510| 63 6c 65 7d 0a 5c 70 61 | 67 65 73 74 79 6c 65 7b |cle}.\pa|gestyle{|
|00000520| 65 6d 70 74 79 7d 20 25 | 20 54 75 72 6e 20 6f 66 |empty} %| Turn of|
|00000530| 66 20 70 61 67 65 20 6e | 75 6d 62 65 72 69 6e 67 |f page n|umbering|
|00000540| 2e 0a 5c 74 6f 70 6d 61 | 72 67 69 6e 3d 30 2e 35 |..\topma|rgin=0.5|
|00000550| 63 6d 0a 5c 74 65 78 74 | 68 65 69 67 68 74 3d 32 |cm.\text|height=2|
|00000560| 33 63 6d 0a 5c 74 65 78 | 74 77 69 64 74 68 3d 31 |3cm.\tex|twidth=1|
|00000570| 35 63 6d 0a 0a 5c 74 69 | 74 6c 65 7b 41 6e 20 45 |5cm..\ti|tle{An E|
|00000580| 78 74 72 65 6d 65 6c 79 | 20 46 61 73 74 20 5a 69 |xtremely| Fast Zi|
|00000590| 76 2d 4c 65 6d 70 65 6c | 5c 5c 44 61 74 61 20 43 |v-Lempel|\\Data C|
|000005a0| 6f 6d 70 72 65 73 73 69 | 6f 6e 20 41 6c 67 6f 72 |ompressi|on Algor|
|000005b0| 69 74 68 6d 7d 0a 0a 5c | 61 75 74 68 6f 72 7b 7b |ithm}..\|author{{|
|000005c0| 5c 62 66 20 52 6f 73 73 | 20 4e 2e 20 57 69 6c 6c |\bf Ross| N. Will|
|000005d0| 69 61 6d 73 7d 5c 5c 0a | 5c 5c 0a 52 65 6e 61 69 |iams}\\.|\\.Renai|
|000005e0| 73 73 61 6e 63 65 20 53 | 6f 66 74 77 61 72 65 5c |ssance S|oftware\|
|000005f0| 5c 0a 47 50 4f 20 42 6f | 78 20 31 37 31 5c 5c 0a |\.GPO Bo|x 171\\.|
|00000600| 41 64 65 6c 61 69 64 65 | 20 35 30 30 31 2c 20 41 |Adelaide| 5001, A|
|00000610| 75 73 74 72 61 6c 69 61 | 5c 5c 0a 5c 5c 0a 7b 5c |ustralia|\\.\\.{\|
|00000620| 74 74 20 72 6f 73 73 40 | 73 70 61 6d 2e 75 61 2e |tt ross@|spam.ua.|
|00000630| 6f 7a 2e 61 75 7d 7d 0a | 5c 64 61 74 65 7b 7d 0a |oz.au}}.|\date{}.|
|00000640| 0a 5c 62 65 67 69 6e 7b | 64 6f 63 75 6d 65 6e 74 |.\begin{|document|
|00000650| 7d 0a 5c 70 61 67 65 73 | 74 79 6c 65 7b 65 6d 70 |}.\pages|tyle{emp|
|00000660| 74 79 7d 0a 5c 6d 61 6b | 65 74 69 74 6c 65 0a 5c |ty}.\mak|etitle.\|
|00000670| 70 61 72 73 6b 69 70 3d | 38 70 74 0a 0a 5c 64 65 |parskip=|8pt..\de|
|00000680| 66 5c 62 6f 6c 64 23 31 | 7b 7b 5c 62 66 20 23 31 |f\bold#1|{{\bf #1|
|00000690| 7d 7d 0a 5c 64 65 66 5c | 62 23 31 7b 7b 5c 62 66 |}}.\def\|b#1{{\bf|
|000006a0| 20 23 31 7d 7d 0a 5c 64 | 65 66 5c 69 23 31 7b 7b | #1}}.\d|ef\i#1{{|
|000006b0| 5c 69 74 20 23 31 7d 7d | 0a 5c 64 65 66 5c 70 61 |\it #1}}|.\def\pa|
|000006c0| 70 65 72 23 31 7b 5c 62 | 6f 6c 64 7b 5b 23 31 5d |per#1{\b|old{[#1]|
|000006d0| 7d 5c 61 6c 6c 6f 77 62 | 72 65 61 6b 7b 7d 7d 0a |}\allowb|reak{}}.|
|000006e0| 5c 64 65 66 5c 64 71 23 | 31 7b 60 60 7b 23 31 7d |\def\dq#|1{``{#1}|
|000006f0| 27 27 7d 0a 5c 64 65 66 | 5c 63 68 65 63 6b 65 64 |''}.\def|\checked|
|00000700| 23 31 7b 7d 0a 25 5c 64 | 65 66 5c 66 69 78 23 31 |#1{}.%\d|ef\fix#1|
|00000710| 7b 5c 65 72 72 6d 65 73 | 73 61 67 65 7b 46 49 58 |{\errmes|sage{FIX|
|00000720| 20 49 54 20 55 50 20 4e | 4f 54 45 21 21 21 7d 7d | IT UP N|OTE!!!}}|
|00000730| 0a 25 5c 64 65 66 5c 66 | 69 78 23 31 7b 5c 66 6f |.%\def\f|ix#1{\fo|
|00000740| 6f 74 6e 6f 74 65 7b 24 | 5c 62 75 6c 6c 65 74 24 |otnote{$|\bullet$|
|00000750| 20 23 31 7d 7d 0a 5c 64 | 65 66 5c 66 69 78 23 31 | #1}}.\d|ef\fix#1|
|00000760| 7b 7d 0a 5c 64 65 66 5c | 74 61 6c 6b 61 62 6f 75 |{}.\def\|talkabou|
|00000770| 74 23 31 7b 5c 6e 6f 69 | 6e 64 65 6e 74 20 7b 5c |t#1{\noi|ndent {\|
|00000780| 62 66 20 23 31 7d 7d 0a | 5c 64 65 66 5c 74 61 6c |bf #1}}.|\def\tal|
|00000790| 6b 61 62 6f 75 74 66 69 | 72 73 74 70 61 72 23 31 |kaboutfi|rstpar#1|
|000007a0| 7b 7b 5c 62 66 20 23 31 | 7d 7d 0a 5c 64 65 66 5c |{{\bf #1|}}.\def\|
|000007b0| 63 6f 6d 6d 65 6e 74 23 | 31 7b 7b 28 5c 69 74 20 |comment#|1{{(\it |
|000007c0| 43 6f 6d 6d 65 6e 74 3a | 20 23 31 29 7d 7d 0a 25 |Comment:| #1)}}.%|
|000007d0| 5c 64 65 66 5c 63 69 74 | 65 66 69 67 75 72 65 23 |\def\cit|efigure#|
|000007e0| 31 7b 7b 5c 62 66 20 46 | 69 67 75 72 65 7e 5c 72 |1{{\bf F|igure~\r|
|000007f0| 65 66 7b 66 69 67 3a 23 | 31 7d 7d 7d 0a 5c 64 65 |ef{fig:#|1}}}.\de|
|00000800| 66 5c 63 69 74 65 66 69 | 67 75 72 65 23 31 7b 7b |f\citefi|gure#1{{|
|00000810| 5c 62 66 20 46 69 67 75 | 72 65 7e 23 31 7d 7d 0a |\bf Figu|re~#1}}.|
|00000820| 5c 64 65 66 5c 70 23 31 | 7b 7b 5c 74 74 20 23 31 |\def\p#1|{{\tt #1|
|00000830| 7d 7d 0a 5c 64 65 66 5c | 73 74 61 72 74 73 6d 61 |}}.\def\|startsma|
|00000840| 6c 6c 7b 5c 62 65 67 69 | 6e 67 72 6f 75 70 7b 7d |ll{\begi|ngroup{}|
|00000850| 5c 66 6f 6f 74 6e 6f 74 | 65 73 69 7a 65 7d 0a 5c |\footnot|esize}.\|
|00000860| 64 65 66 5c 65 6e 64 73 | 6d 61 6c 6c 7b 5c 65 6e |def\ends|mall{\en|
|00000870| 64 67 72 6f 75 70 7b 7d | 7d 0a 5c 64 65 66 5c 6f |dgroup{}|}.\def\o|
|00000880| 70 74 23 31 7b 5c 6e 6f | 69 6e 64 65 6e 74 5c 62 |pt#1{\no|indent\b|
|00000890| 6f 6c 64 7b 23 31 7d 7d | 0a 5c 64 65 66 5c 73 74 |old{#1}}|.\def\st|
|000008a0| 61 72 74 73 6d 61 6c 6c | 7b 5c 62 65 67 69 6e 67 |artsmall|{\beging|
|000008b0| 72 6f 75 70 7b 7d 5c 66 | 6f 6f 74 6e 6f 74 65 73 |roup{}\f|ootnotes|
|000008c0| 69 7a 65 7d 0a 5c 64 65 | 66 5c 65 6e 64 73 6d 61 |ize}.\de|f\endsma|
|000008d0| 6c 6c 7b 5c 65 6e 64 67 | 72 6f 75 70 7b 7d 7d 0a |ll{\endg|roup{}}.|
|000008e0| 5c 64 65 66 5c 6d 79 63 | 61 70 74 69 6f 6e 23 31 |\def\myc|aption#1|
|000008f0| 7b 5c 62 65 67 69 6e 7b | 71 75 6f 74 61 74 69 6f |{\begin{|quotatio|
|00000900| 6e 7d 5c 66 6f 6f 74 6e | 6f 74 65 73 69 7a 65 5c |n}\footn|otesize\|
|00000910| 6e 6f 69 6e 64 65 6e 74 | 20 23 31 5c 65 6e 64 7b |noindent| #1\end{|
|00000920| 71 75 6f 74 61 74 69 6f | 6e 7d 7d 0a 5c 64 65 66 |quotatio|n}}.\def|
|00000930| 5c 6d 79 74 69 74 6c 65 | 23 31 23 32 7b 5c 63 61 |\mytitle|#1#2{\ca|
|00000940| 70 74 69 6f 6e 7b 23 32 | 7d 5c 6c 61 62 65 6c 7b |ption{#2|}\label{|
|00000950| 66 69 67 3a 23 31 7d 7d | 0a 5c 64 65 66 5c 65 67 |fig:#1}}|.\def\eg|
|00000960| 23 31 7b 65 2e 67 2e 7e | 7d 0a 5c 64 65 66 5c 69 |#1{e.g.~|}.\def\i|
|00000970| 65 23 31 7b 69 2e 65 2e | 7e 7d 0a 0a 5c 6c 6f 6e |e#1{i.e.|~}..\lon|
|00000980| 67 5c 64 65 66 5c 62 69 | 67 63 61 70 74 69 6f 6e |g\def\bi|gcaption|
|00000990| 23 31 23 32 23 33 7b 25 | 0a 5c 62 65 67 69 6e 7b |#1#2#3{%|.\begin{|
|000009a0| 71 75 6f 74 61 74 69 6f | 6e 7d 0a 5c 6e 6f 72 6d |quotatio|n}.\norm|
|000009b0| 61 6c 73 69 7a 65 5c 6e | 6f 69 6e 64 65 6e 74 20 |alsize\n|oindent |
|000009c0| 23 33 0a 5c 65 6e 64 7b | 71 75 6f 74 61 74 69 6f |#3.\end{|quotatio|
|000009d0| 6e 7d 0a 5c 63 65 6e 74 | 65 72 6c 69 6e 65 7b 5c |n}.\cent|erline{\|
|000009e0| 62 7b 46 69 67 75 72 65 | 7e 23 31 3a 20 23 32 7d |b{Figure|~#1: #2}|
|000009f0| 7d 0a 7d 0a 0a 5c 6c 6f | 6e 67 5c 64 65 66 5c 62 |}.}..\lo|ng\def\b|
|00000a00| 69 67 63 61 70 74 69 6f | 6e 6e 6f 64 65 73 63 23 |igcaptio|nnodesc#|
|00000a10| 31 23 32 7b 25 0a 5c 6d | 65 64 73 6b 69 70 0a 5c |1#2{%.\m|edskip.\|
|00000a20| 63 65 6e 74 65 72 6c 69 | 6e 65 7b 5c 62 7b 46 69 |centerli|ne{\b{Fi|
|00000a30| 67 75 72 65 7e 23 31 3a | 20 23 32 7d 7d 0a 7d 0a |gure~#1:| #2}}.}.|
|00000a40| 0a 25 20 45 2e 67 2e 20 | 5c 62 69 67 63 61 70 74 |.% E.g. |\bigcapt|
|00000a50| 69 6f 6e 7b 7a 69 76 64 | 69 61 67 7d 7b 43 6f 6d |ion{zivd|iag}{Com|
|00000a60| 70 72 65 73 73 65 64 20 | 64 61 74 61 20 66 6f 72 |pressed |data for|
|00000a70| 6d 61 74 2e 7d 7b 54 68 | 69 73 20 64 69 61 67 72 |mat.}{Th|is diagr|
|00000a80| 61 6d 0a 25 73 68 6f 77 | 73 2e 2e 2e 7d 0a 0a 5c |am.%show|s...}..\|
|00000a90| 73 6c 6f 70 70 79 0a 0a | 5c 62 65 67 69 6e 7b 61 |sloppy..|\begin{a|
|00000aa0| 62 73 74 72 61 63 74 7d | 0a 25 0a 5c 6e 6f 69 6e |bstract}|.%.\noin|
|00000ab0| 64 65 6e 74 5c 6e 6f 72 | 6d 61 6c 73 69 7a 65 20 |dent\nor|malsize |
|00000ac0| 41 20 20 6e 65 77 2c 20 | 73 69 6d 70 6c 65 2c 20 |A  new, |simple, |
|00000ad0| 65 78 74 72 65 6d 65 6c | 79 20 66 61 73 74 2c 20 |extremel|y fast, |
|00000ae0| 20 6c 6f 63 61 6c 6c 79 | 20 61 64 61 70 74 69 76 | locally| adaptiv|
|00000af0| 65 0a 64 61 74 61 20 20 | 63 6f 6d 70 72 65 73 73 |e.data  |compress|
|00000b00| 69 6f 6e 20 20 61 6c 67 | 6f 72 69 74 68 6d 20 20 |ion  alg|orithm  |
|00000b10| 6f 66 20 20 74 68 65 20 | 4c 5a 37 37 20 20 63 6c |of  the |LZ77  cl|
|00000b20| 61 73 73 20 20 69 73 20 | 20 70 72 65 73 65 6e 74 |ass  is | present|
|00000b30| 65 64 2e 20 20 54 68 65 | 0a 61 6c 67 6f 72 69 74 |ed.  The|.algorit|
|00000b40| 68 6d 2c 20 63 61 6c 6c | 65 64 20 20 4c 5a 52 57 |hm, call|ed  LZRW|
|00000b50| 31 2c 20 61 6c 6d 6f 73 | 74 20 68 61 6c 76 65 73 |1, almos|t halves|
|00000b60| 20 20 74 68 65 20 73 69 | 7a 65 20 6f 66 20 74 65 |  the si|ze of te|
|00000b70| 78 74 20 20 66 69 6c 65 | 73 2c 20 75 73 65 73 0a |xt  file|s, uses.|
|00000b80| 31 36 4b 20 6f 66 20 6d | 65 6d 6f 72 79 2c 20 61 |16K of m|emory, a|
|00000b90| 6e 64 20 72 65 71 75 69 | 72 65 73 20 20 61 62 6f |nd requi|res  abo|
|00000ba0| 75 74 20 31 33 7e 6d 61 | 63 68 69 6e 65 20 69 6e |ut 13~ma|chine in|
|00000bb0| 73 74 72 75 63 74 69 6f | 6e 73 20 74 6f 20 63 6f |structio|ns to co|
|00000bc0| 6d 70 72 65 73 73 0a 61 | 6e 64 20 61 62 6f 75 74 |mpress.a|nd about|
|00000bd0| 20 34 7e 6d 61 63 68 69 | 6e 65 20 69 6e 73 74 72 | 4~machi|ne instr|
|00000be0| 75 63 74 69 6f 6e 73 20 | 74 6f 20 64 65 63 6f 6d |uctions |to decom|
|00000bf0| 70 72 65 73 73 20 65 61 | 63 68 20 62 79 74 65 2e |press ea|ch byte.|
|00000c00| 20 54 68 69 73 20 72 65 | 73 75 6c 74 73 0a 69 6e | This re|sults.in|
|00000c10| 20 20 73 70 65 65 64 73 | 20 6f 66 20 20 61 62 6f |  speeds| of  abo|
|00000c20| 75 74 20 37 37 4b 20 20 | 61 6e 64 20 20 32 35 30 |ut 77K  |and  250|
|00000c30| 4b 20 62 79 74 65 73 20 | 20 70 65 72 20 20 73 65 |K bytes | per  se|
|00000c40| 63 6f 6e 64 20 6f 6e 20 | 20 61 20 6f 6e 65 20 20 |cond on | a one  |
|00000c50| 4d 49 50 53 0a 6d 61 63 | 68 69 6e 65 2e 20 54 68 |MIPS.mac|hine. Th|
|00000c60| 65 20 61 6c 67 6f 72 69 | 74 68 6d 20 20 72 75 6e |e algori|thm  run|
|00000c70| 73 20 69 6e 20 6c 69 6e | 65 61 72 20 74 69 6d 65 |s in lin|ear time|
|00000c80| 20 61 6e 64 20 68 61 73 | 20 20 61 20 67 6f 6f 64 | and has|  a good|
|00000c90| 20 77 6f 72 73 74 20 63 | 61 73 65 0a 72 75 6e 6e | worst c|ase.runn|
|00000ca0| 69 6e 67 20 74 69 6d 65 | 2e 20 20 49 74 20 61 64 |ing time|.  It ad|
|00000cb0| 61 70 74 73 20 71 75 69 | 63 6b 6c 79 20 20 61 6e |apts qui|ckly  an|
|00000cc0| 64 20 68 61 73 20 61 20 | 20 6e 65 67 6c 69 67 69 |d has a | negligi|
|00000cd0| 62 6c 65 20 69 6e 69 74 | 69 61 6c 69 7a 61 74 69 |ble init|ializati|
|00000ce0| 6f 6e 0a 6f 76 65 72 68 | 65 61 64 2c 20 6d 61 6b |on.overh|ead, mak|
|00000cf0| 69 6e 67 20 20 69 74 20 | 66 61 73 74 20 61 6e 64 |ing  it |fast and|
|00000d00| 20 20 65 66 66 69 63 69 | 65 6e 74 20 66 6f 72 20 |  effici|ent for |
|00000d10| 20 73 6d 61 6c 6c 20 62 | 6c 6f 63 6b 73 20 6f 66 | small b|locks of|
|00000d20| 20 20 64 61 74 61 20 61 | 73 0a 77 65 6c 6c 20 61 |  data a|s.well a|
|00000d30| 73 20 6c 61 72 67 65 20 | 6f 6e 65 73 2e 0a 25 0a |s large |ones..%.|
|00000d40| 5c 65 6e 64 7b 61 62 73 | 74 72 61 63 74 7d 0a 0a |\end{abs|tract}..|
|00000d50| 5c 73 65 63 74 69 6f 6e | 7b 49 6e 74 72 6f 64 75 |\section|{Introdu|
|00000d60| 63 74 69 6f 6e 7d 0a 0a | 54 65 78 74 20 20 64 61 |ction}..|Text  da|
|00000d70| 74 61 20 20 63 6f 6d 70 | 72 65 73 73 69 6f 6e 20 |ta  comp|ression |
|00000d80| 74 65 63 68 6e 69 71 75 | 65 73 20 20 63 61 6e 20 |techniqu|es  can |
|00000d90| 20 62 65 20 20 70 61 72 | 74 69 74 69 6f 6e 65 64 | be  par|titioned|
|00000da0| 20 69 6e 74 6f 20 20 61 | 64 20 20 68 6f 63 0a 74 | into  a|d  hoc.t|
|00000db0| 65 63 68 6e 69 71 75 65 | 73 2c 20 20 64 69 63 74 |echnique|s,  dict|
|00000dc0| 69 6f 6e 61 72 79 20 74 | 65 63 68 6e 69 71 75 65 |ionary t|echnique|
|00000dd0| 73 2c 20 20 61 6e 64 20 | 20 73 74 61 74 69 73 74 |s,  and | statist|
|00000de0| 69 63 61 6c 20 74 65 63 | 68 6e 69 71 75 65 73 20 |ical tec|hniques |
|00000df0| 20 28 73 65 65 0a 72 65 | 76 69 65 77 73 20 20 20 | (see.re|views   |
|00000e00| 69 6e 20 20 5c 70 61 70 | 65 72 7b 57 69 6c 6c 69 |in  \pap|er{Willi|
|00000e10| 61 6d 73 39 30 7d 5c 70 | 61 70 65 72 7b 42 65 6c |ams90}\p|aper{Bel|
|00000e20| 6c 39 30 61 7d 5c 70 61 | 70 65 72 7b 53 74 6f 72 |l90a}\pa|per{Stor|
|00000e30| 65 72 38 38 7d 29 2e 20 | 20 20 4f 66 0a 74 68 65 |er88}). |  Of.the|
|00000e40| 73 65 2c 20 74 68 65 20 | 20 63 6c 61 73 73 20 6f |se, the | class o|
|00000e50| 66 20 61 64 61 70 74 69 | 76 65 20 20 64 69 63 74 |f adapti|ve  dict|
|00000e60| 69 6f 6e 61 72 79 20 61 | 6c 67 6f 72 69 74 68 6d |ionary a|lgorithm|
|00000e70| 73 20 70 69 6f 6e 65 65 | 72 65 64 20 20 62 79 20 |s pionee|red  by |
|00000e80| 5a 69 76 0a 61 6e 64 20 | 4c 65 6d 70 65 6c 5c 70 |Ziv.and |Lempel\p|
|00000e90| 61 70 65 72 7b 5a 69 76 | 37 37 7d 5c 70 61 70 65 |aper{Ziv|77}\pape|
|00000ea0| 72 7b 5a 69 76 37 38 7d | 20 70 72 6f 76 69 64 65 |r{Ziv78}| provide|
|00000eb0| 73 20 74 68 65 20 6d 6f | 73 74 20 70 72 61 63 74 |s the mo|st pract|
|00000ec0| 69 63 61 6c 20 74 72 61 | 64 65 0a 6f 66 66 20 62 |ical tra|de.off b|
|00000ed0| 65 74 77 65 65 6e 20 66 | 6c 65 78 69 62 69 6c 69 |etween f|lexibili|
|00000ee0| 74 79 2c 20 63 6f 6d 70 | 72 65 73 73 69 6f 6e 2c |ty, comp|ression,|
|00000ef0| 20 61 6e 64 20 73 70 65 | 65 64 2e 20 4d 6f 73 74 | and spe|ed. Most|
|00000f00| 20 6d 6f 64 65 72 6e 20 | 74 65 78 74 20 64 61 74 | modern |text dat|
|00000f10| 61 0a 63 6f 6d 70 72 65 | 73 73 69 6f 6e 20 70 72 |a.compre|ssion pr|
|00000f20| 6f 67 72 61 6d 73 2c 20 | 69 6e 63 6c 75 64 69 6e |ograms, |includin|
|00000f30| 67 20 74 68 65 20 20 70 | 6f 70 75 6c 61 72 20 55 |g the  p|opular U|
|00000f40| 6e 69 78 20 5c 69 7b 63 | 6f 6d 70 72 65 73 73 7d |nix \i{c|ompress}|
|00000f50| 20 75 74 69 6c 69 74 79 | 0a 28 64 65 72 69 76 65 | utility|.(derive|
|00000f60| 64 20 66 72 6f 6d 20 5c | 70 61 70 65 72 7b 57 65 |d from \|paper{We|
|00000f70| 6c 63 68 38 34 7d 29 2c | 20 75 73 65 20 5a 69 76 |lch84}),| use Ziv|
|00000f80| 20 61 6e 64 20 4c 65 6d | 70 65 6c 20 28 4c 5a 29 | and Lem|pel (LZ)|
|00000f90| 20 61 6c 67 6f 72 69 74 | 68 6d 73 2e 0a 0a 41 6c | algorit|hms...Al|
|00000fa0| 74 68 6f 75 67 68 20 63 | 75 72 72 65 6e 74 20 4c |though c|urrent L|
|00000fb0| 5a 20 61 6c 67 6f 72 69 | 74 68 6d 73 20 61 72 65 |Z algori|thms are|
|00000fc0| 20 67 65 6e 65 72 61 6c | 6c 79 20 66 61 73 74 2c | general|ly fast,|
|00000fd0| 20 74 68 65 79 20 61 72 | 65 20 6e 6f 74 20 61 6c | they ar|e not al|
|00000fe0| 77 61 79 73 0a 66 61 73 | 74 20 20 65 6e 6f 75 67 |ways.fas|t  enoug|
|00000ff0| 68 20 20 66 6f 72 20 65 | 6d 62 65 64 64 65 64 20 |h  for e|mbedded |
|00001000| 20 72 65 61 6c 2d 74 69 | 6d 65 20 20 73 79 73 74 | real-ti|me  syst|
|00001010| 65 6d 73 20 20 77 69 74 | 68 20 74 69 67 68 74 20 |ems  wit|h tight |
|00001020| 20 74 68 72 6f 75 67 68 | 70 75 74 0a 72 65 71 75 | through|put.requ|
|00001030| 69 72 65 6d 65 6e 74 73 | 2e 20 49 6e 20 20 73 75 |irements|. In  su|
|00001040| 63 68 20 73 79 73 74 65 | 6d 73 20 20 74 69 6d 65 |ch syste|ms  time|
|00001050| 20 69 73 20 20 74 68 65 | 20 69 6d 70 6f 72 74 61 | is  the| importa|
|00001060| 6e 74 20 20 63 6f 6e 73 | 74 72 61 69 6e 74 20 61 |nt  cons|traint a|
|00001070| 6e 64 0a 64 65 73 69 67 | 6e 65 72 73 20 20 6f 66 |nd.desig|ners  of|
|00001080| 20 63 6f 6d 70 72 65 73 | 73 69 6f 6e 20 20 61 6c | compres|sion  al|
|00001090| 67 6f 72 69 74 68 6d 73 | 20 20 6d 75 73 74 20 20 |gorithms|  must  |
|000010a0| 63 6f 6e 63 65 6e 74 72 | 61 74 65 20 70 72 69 6d |concentr|ate prim|
|000010b0| 61 72 69 6c 79 20 20 6f | 6e 0a 73 70 65 65 64 2c |arily  o|n.speed,|
|000010c0| 20 77 69 74 68 20 63 6f | 6d 70 72 65 73 73 69 6f | with co|mpressio|
|000010d0| 6e 20 74 61 6b 69 6e 67 | 20 73 65 63 6f 6e 64 20 |n taking| second |
|000010e0| 70 6c 61 63 65 2e 20 54 | 68 69 73 20 70 61 70 65 |place. T|his pape|
|000010f0| 72 20 70 72 65 73 65 6e | 74 73 20 61 20 6e 65 77 |r presen|ts a new|
|00001100| 0a 4c 5a 20 76 61 72 69 | 61 6e 74 20 20 63 61 6c |.LZ vari|ant  cal|
|00001110| 6c 65 64 20 4c 5a 52 57 | 31 20 74 68 61 74 20 77 |led LZRW|1 that w|
|00001120| 61 73 20 20 64 65 73 69 | 67 6e 65 64 20 77 69 74 |as  desi|gned wit|
|00001130| 68 20 73 70 65 65 64 20 | 61 73 20 20 74 68 65 20 |h speed |as  the |
|00001140| 70 72 69 6d 61 72 79 0a | 6f 62 6a 65 63 74 69 76 |primary.|objectiv|
|00001150| 65 2e 20 54 68 65 20 61 | 6c 67 6f 72 69 74 68 6d |e. The a|lgorithm|
|00001160| 20 74 61 6b 65 73 20 6f | 6e 6c 79 20 61 20 66 65 | takes o|nly a fe|
|00001170| 77 20 69 6e 73 74 72 75 | 63 74 69 6f 6e 73 20 74 |w instru|ctions t|
|00001180| 6f 20 70 72 6f 63 65 73 | 73 20 65 61 63 68 0a 62 |o proces|s each.b|
|00001190| 79 74 65 2c 20 62 75 74 | 20 20 73 74 69 6c 6c 20 |yte, but|  still |
|000011a0| 79 69 65 6c 64 73 20 75 | 73 65 66 75 6c 20 63 6f |yields u|seful co|
|000011b0| 6d 70 72 65 73 73 69 6f | 6e 2e 20 20 4c 5a 52 57 |mpressio|n.  LZRW|
|000011c0| 31 20 69 73 20 62 61 73 | 65 64 20 6f 6e 20 20 74 |1 is bas|ed on  t|
|000011d0| 68 65 20 41 31 0a 61 6c | 67 6f 72 69 74 68 6d 20 |he A1.al|gorithm |
|000011e0| 62 79 20 46 69 61 6c 61 | 20 61 6e 64 20 47 72 65 |by Fiala| and Gre|
|000011f0| 65 6e 65 5c 70 61 70 65 | 72 7b 46 69 61 6c 61 38 |ene\pape|r{Fiala8|
|00001200| 38 7d 20 20 77 68 69 63 | 68 20 69 74 73 65 6c 66 |8}  whic|h itself|
|00001210| 20 69 73 20 61 20 6d 65 | 6d 62 65 72 0a 6f 66 20 | is a me|mber.of |
|00001220| 74 68 65 20 63 6c 61 73 | 73 20 6f 66 20 4c 5a 37 |the clas|s of LZ7|
|00001230| 37 20 61 6c 67 6f 72 69 | 74 68 6d 73 5c 70 61 70 |7 algori|thms\pap|
|00001240| 65 72 7b 5a 69 76 37 37 | 7d 2e 0a 0a 5c 73 65 63 |er{Ziv77|}...\sec|
|00001250| 74 69 6f 6e 7b 54 68 65 | 20 4c 5a 52 57 31 20 41 |tion{The| LZRW1 A|
|00001260| 6c 67 6f 72 69 74 68 6d | 7d 0a 0a 4c 5a 52 57 31 |lgorithm|}..LZRW1|
|00001270| 20 75 73 65 73 20 74 68 | 65 20 73 69 6e 67 6c 65 | uses th|e single|
|00001280| 20 70 61 73 73 20 20 6c | 69 74 65 72 61 6c 2f 63 | pass  l|iteral/c|
|00001290| 6f 70 79 20 6d 65 63 68 | 61 6e 69 73 6d 20 6f 66 |opy mech|anism of|
|000012a0| 20 5c 70 61 70 65 72 7b | 4c 5a 37 37 7d 2e 20 41 | \paper{|LZ77}. A|
|000012b0| 74 0a 65 61 63 68 20 73 | 74 65 70 2c 20 74 68 65 |t.each s|tep, the|
|000012c0| 20 6e 65 78 74 20 66 65 | 77 20 62 79 74 65 73 20 | next fe|w bytes |
|000012d0| 6f 66 20 69 6e 70 75 74 | 20 61 72 65 20 74 72 61 |of input| are tra|
|000012e0| 6e 73 6d 69 74 74 65 64 | 20 65 69 74 68 65 72 20 |nsmitted| either |
|000012f0| 64 69 72 65 63 74 6c 79 | 0a 61 73 20 20 61 20 73 |directly|.as  a s|
|00001300| 74 72 69 6e 67 20 20 6f | 72 20 61 73 20 20 61 20 |tring  o|r as  a |
|00001310| 70 6f 69 6e 74 65 72 20 | 20 74 6f 20 74 68 65 20 |pointer | to the |
|00001320| 20 74 65 78 74 20 61 6c | 72 65 61 64 79 20 20 74 | text al|ready  t|
|00001330| 72 61 6e 73 6d 69 74 74 | 65 64 20 28 74 68 65 0a |ransmitt|ed (the.|
|00001340| 5c 62 7b 68 69 73 74 6f | 72 79 7d 29 2e 20 5c 63 |\b{histo|ry}). \c|
|00001350| 69 74 65 66 69 67 75 72 | 65 7b 31 7d 20 20 73 68 |itefigur|e{1}  sh|
|00001360| 6f 77 73 20 68 6f 77 20 | 61 20 70 61 72 74 69 63 |ows how |a partic|
|00001370| 75 6c 61 72 20 20 6d 65 | 73 73 61 67 65 20 77 6f |ular  me|ssage wo|
|00001380| 75 6c 64 20 62 65 0a 64 | 69 76 69 64 65 64 20 20 |uld be.d|ivided  |
|00001390| 69 6e 74 6f 20 5c 62 7b | 6c 69 74 65 72 61 6c 20 |into \b{|literal |
|000013a0| 20 69 74 65 6d 73 7d 20 | 20 61 6e 64 20 5c 62 7b | items} | and \b{|
|000013b0| 63 6f 70 79 20 20 69 74 | 65 6d 73 7d 20 20 69 66 |copy  it|ems}  if|
|000013c0| 20 74 68 65 20 20 6d 69 | 6e 69 6d 75 6d 0a 6c 65 | the  mi|nimum.le|
|000013d0| 6e 67 74 68 20 6f 66 20 | 61 6e 20 20 75 6e 63 6f |ngth of |an  unco|
|000013e0| 6d 70 72 65 73 73 65 64 | 20 63 6f 70 79 20 69 74 |mpressed| copy it|
|000013f0| 65 6d 20 77 65 72 65 20 | 74 68 72 65 65 20 20 62 |em were |three  b|
|00001400| 79 74 65 73 2e 20 43 6f | 6d 70 72 65 73 73 69 6f |ytes. Co|mpressio|
|00001410| 6e 20 69 73 0a 61 63 68 | 69 65 76 65 64 20 20 62 |n is.ach|ieved  b|
|00001420| 79 20 72 65 70 72 65 73 | 65 6e 74 69 6e 67 20 20 |y repres|enting  |
|00001430| 61 73 20 6d 75 63 68 20 | 20 6f 66 20 74 68 65 20 |as much | of the |
|00001440| 20 6d 65 73 73 61 67 65 | 20 75 73 69 6e 67 20 20 | message| using  |
|00001450| 63 6f 70 79 20 69 74 65 | 6d 73 2c 0a 72 65 73 6f |copy ite|ms,.reso|
|00001460| 72 74 69 6e 67 20 74 6f | 20 20 6c 69 74 65 72 61 |rting to|  litera|
|00001470| 6c 20 69 74 65 6d 73 20 | 6f 6e 6c 79 20 77 68 65 |l items |only whe|
|00001480| 6e 20 20 61 20 6d 61 74 | 63 68 20 6f 66 20 74 68 |n  a mat|ch of th|
|00001490| 72 65 65 20 20 6f 72 20 | 6d 6f 72 65 20 62 79 74 |ree  or |more byt|
|000014a0| 65 73 0a 63 61 6e 6e 6f | 74 20 62 65 20 66 6f 75 |es.canno|t be fou|
|000014b0| 6e 64 2e 0a 0a 5c 62 65 | 67 69 6e 7b 66 69 67 75 |nd...\be|gin{figu|
|000014c0| 72 65 7d 5b 68 74 5d 0a | 5c 76 73 70 61 63 65 7b |re}[ht].|\vspace{|
|000014d0| 34 2e 35 63 6d 7d 0a 5c | 62 69 67 63 61 70 74 69 |4.5cm}.\|bigcapti|
|000014e0| 6f 6e 7b 31 7d 7b 54 68 | 65 20 6c 69 74 65 72 61 |on{1}{Th|e litera|
|000014f0| 6c 2f 63 6f 70 79 20 63 | 6f 6d 70 72 65 73 73 69 |l/copy c|ompressi|
|00001500| 6f 6e 20 74 65 63 68 6e | 69 71 75 65 2e 7d 7b 25 |on techn|ique.}{%|
|00001510| 0a 25 0a 4c 5a 37 37 20 | 63 6c 61 73 73 20 61 6c |.%.LZ77 |class al|
|00001520| 67 6f 72 69 74 68 6d 73 | 20 28 6f 66 20 77 68 69 |gorithms| (of whi|
|00001530| 63 68 20 4c 5a 52 57 31 | 20 69 73 20 61 20 6d 65 |ch LZRW1| is a me|
|00001540| 6d 62 65 72 29 20 61 63 | 68 69 65 76 65 20 63 6f |mber) ac|hieve co|
|00001550| 6d 70 72 65 73 73 69 6f | 6e 0a 62 79 20 63 6f 6e |mpressio|n.by con|
|00001560| 76 65 72 74 69 6e 67 20 | 74 68 65 20 74 65 78 74 |verting |the text|
|00001570| 20 69 6e 74 6f 20 61 20 | 73 65 71 75 65 6e 63 65 | into a |sequence|
|00001580| 20 20 6f 66 20 69 74 65 | 6d 73 2c 20 65 61 63 68 |  of ite|ms, each|
|00001590| 20 6f 66 20 77 68 69 63 | 68 20 63 61 6e 20 62 65 | of whic|h can be|
|000015a0| 0a 65 69 74 68 65 72 20 | 61 20 20 6c 69 74 65 72 |.either |a  liter|
|000015b0| 61 6c 20 69 74 65 6d 20 | 6f 72 20 20 61 20 63 6f |al item |or  a co|
|000015c0| 70 79 20 69 74 65 6d 2e | 20 20 4c 69 74 65 72 61 |py item.|  Litera|
|000015d0| 6c 20 69 74 65 6d 73 20 | 63 6f 6e 73 69 73 74 20 |l items |consist |
|000015e0| 20 6f 66 20 74 68 65 0a | 74 65 78 74 20 74 68 65 | of the.|text the|
|000015f0| 79 20 20 72 65 70 72 65 | 73 65 6e 74 2e 20 43 6f |y  repre|sent. Co|
|00001600| 70 79 20 69 74 65 6d 73 | 20 20 63 6f 6e 73 69 73 |py items|  consis|
|00001610| 74 20 6f 66 20 20 61 6e | 20 6f 66 66 73 65 74 20 |t of  an| offset |
|00001620| 61 6e 64 20 20 61 20 70 | 6f 69 6e 74 65 72 0a 74 |and  a p|ointer.t|
|00001630| 68 61 74 20 74 6f 67 65 | 74 68 65 72 20 70 6f 69 |hat toge|ther poi|
|00001640| 6e 74 20 74 6f 20 61 20 | 73 75 62 73 74 72 69 6e |nt to a |substrin|
|00001650| 67 20 6f 66 20 74 68 65 | 20 74 65 78 74 20 61 6c |g of the| text al|
|00001660| 72 65 61 64 79 20 74 72 | 61 6e 73 6d 69 74 74 65 |ready tr|ansmitte|
|00001670| 64 2e 0a 25 0a 7d 0a 5c | 65 6e 64 7b 66 69 67 75 |d..%.}.\|end{figu|
|00001680| 72 65 7d 0a 0a 5c 63 69 | 74 65 66 69 67 75 72 65 |re}..\ci|tefigure|
|00001690| 7b 32 7d 20 20 73 68 6f | 77 73 20 68 6f 77 20 20 |{2}  sho|ws how  |
|000016a0| 4c 5a 52 57 31 20 20 61 | 72 72 61 6e 67 65 73 20 |LZRW1  a|rranges |
|000016b0| 74 68 65 20 20 69 74 65 | 6d 73 20 69 6e 74 6f 20 |the  ite|ms into |
|000016c0| 20 63 6f 6d 70 72 65 73 | 73 65 64 0a 64 61 74 61 | compres|sed.data|
|000016d0| 2e 20 41 20 6c 69 74 65 | 72 61 6c 20 69 74 65 6d |. A lite|ral item|
|000016e0| 20 63 6f 6e 74 61 69 6e | 73 20 61 20 20 73 69 6e | contain|s a  sin|
|000016f0| 67 6c 65 20 62 79 74 65 | 20 74 68 61 74 20 69 73 |gle byte| that is|
|00001700| 20 63 6f 64 65 64 20 64 | 69 72 65 63 74 6c 79 2e | coded d|irectly.|
|00001710| 20 41 0a 63 6f 70 79 20 | 20 69 74 65 6d 20 20 63 | A.copy | item  c|
|00001720| 6f 6e 74 61 69 6e 73 20 | 20 74 77 6f 20 20 62 79 |ontains | two  by|
|00001730| 74 65 73 20 74 68 61 74 | 20 20 73 70 65 63 69 66 |tes that|  specif|
|00001740| 79 20 20 74 68 65 20 20 | 6c 65 6e 67 74 68 5b 33 |y  the  |length[3|
|00001750| 2c 31 36 5d 20 20 61 6e | 64 0a 6f 66 66 73 65 74 |,16]  an|d.offset|
|00001760| 5b 31 2c 34 30 39 35 5d | 20 6f 66 20 61 20 73 74 |[1,4095]| of a st|
|00001770| 72 69 6e 67 20 61 70 70 | 65 61 72 69 6e 67 20 69 |ring app|earing i|
|00001780| 6e 20 20 74 68 65 20 6d | 6f 73 74 20 72 65 63 65 |n  the m|ost rece|
|00001790| 6e 74 20 34 30 39 35 20 | 62 79 74 65 73 20 6f 66 |nt 4095 |bytes of|
|000017a0| 0a 74 68 65 20 68 69 73 | 74 6f 72 79 20 28 74 68 |.the his|tory (th|
|000017b0| 65 20 5c 62 7b 4c 65 6d | 70 65 6c 7d 29 2e 20 43 |e \b{Lem|pel}). C|
|000017c0| 6f 6e 74 72 6f 6c 20 20 | 62 69 74 73 20 69 6e 64 |ontrol  |bits ind|
|000017d0| 69 63 61 74 65 20 77 68 | 65 74 68 65 72 20 69 74 |icate wh|ether it|
|000017e0| 65 6d 73 20 61 72 65 0a | 6c 69 74 65 72 61 6c 20 |ems are.|literal |
|000017f0| 6f 72 20 63 6f 70 79 20 | 69 74 65 6d 73 2c 20 61 |or copy |items, a|
|00001800| 6e 64 20 61 72 65 20 63 | 6c 75 73 74 65 72 65 64 |nd are c|lustered|
|00001810| 20 69 6e 74 6f 20 67 72 | 6f 75 70 73 20 6f 66 20 | into gr|oups of |
|00001820| 31 36 20 74 6f 20 70 72 | 65 73 65 72 76 65 0a 62 |16 to pr|eserve.b|
|00001830| 79 74 65 20 61 6c 69 67 | 6e 6d 65 6e 74 2e 0a 0a |yte alig|nment...|
|00001840| 5c 62 65 67 69 6e 7b 66 | 69 67 75 72 65 7d 5b 68 |\begin{f|igure}[h|
|00001850| 74 5d 0a 5c 76 73 70 61 | 63 65 7b 39 63 6d 7d 0a |t].\vspa|ce{9cm}.|
|00001860| 5c 62 69 67 63 61 70 74 | 69 6f 6e 7b 32 7d 7b 4c |\bigcapt|ion{2}{L|
|00001870| 5a 52 57 31 27 73 20 63 | 6f 6d 70 72 65 73 73 65 |ZRW1's c|ompresse|
|00001880| 64 20 64 61 74 61 20 66 | 6f 72 6d 61 74 2e 7d 7b |d data f|ormat.}{|
|00001890| 25 0a 25 0a 54 68 69 73 | 20 66 69 67 75 72 65 20 |%.%.This| figure |
|000018a0| 67 69 76 65 73 20 4c 5a | 52 57 31 27 73 20 63 6f |gives LZ|RW1's co|
|000018b0| 6d 70 72 65 73 73 65 64 | 20 20 64 61 74 61 20 66 |mpressed|  data f|
|000018c0| 6f 72 6d 61 74 2e 20 4c | 5a 52 57 31 20 75 73 65 |ormat. L|ZRW1 use|
|000018d0| 73 20 61 20 73 69 6e 67 | 6c 65 0a 62 69 74 20 74 |s a sing|le.bit t|
|000018e0| 6f 20 64 65 74 65 72 6d | 69 6e 65 20 77 68 65 74 |o determ|ine whet|
|000018f0| 68 65 72 20 20 65 61 63 | 68 20 69 74 65 6d 20 69 |her  eac|h item i|
|00001900| 73 20 61 20 6c 69 74 65 | 72 61 6c 20 69 74 65 6d |s a lite|ral item|
|00001910| 20 20 6f 72 20 61 20 63 | 6f 70 79 20 69 74 65 6d |  or a c|opy item|
|00001920| 2e 0a 54 6f 20 70 72 65 | 73 65 72 76 65 20 20 62 |..To pre|serve  b|
|00001930| 79 74 65 20 61 6c 69 67 | 6e 6d 65 6e 74 2c 20 69 |yte alig|nment, i|
|00001940| 74 65 6d 73 20 20 61 72 | 65 20 63 6c 75 73 74 65 |tems  ar|e cluste|
|00001950| 72 65 64 20 69 6e 74 6f | 20 20 31 36 2d 69 74 65 |red into|  16-ite|
|00001960| 6d 20 67 72 6f 75 70 73 | 0a 70 72 65 63 65 64 65 |m groups|.precede|
|00001970| 64 20 62 79 20 61 20 31 | 36 2d 62 69 74 20 63 6f |d by a 1|6-bit co|
|00001980| 6e 74 72 6f 6c 20 77 6f | 72 64 2e 0a 25 0a 7d 0a |ntrol wo|rd..%.}.|
|00001990| 5c 65 6e 64 7b 66 69 67 | 75 72 65 7d 0a 0a 5c 63 |\end{fig|ure}..\c|
|000019a0| 69 74 65 66 69 67 75 72 | 65 7b 33 7d 20 67 69 76 |itefigur|e{3} giv|
|000019b0| 65 73 20 61 20 73 6e 61 | 70 73 68 6f 74 20 6f 66 |es a sna|pshot of|
|000019c0| 20 20 74 68 65 20 4c 5a | 52 57 31 20 63 6f 6d 70 |  the LZ|RW1 comp|
|000019d0| 72 65 73 73 69 6f 6e 20 | 61 6c 67 6f 72 69 74 68 |ression |algorith|
|000019e0| 6d 20 69 6e 0a 65 78 65 | 63 75 74 69 6f 6e 2e 20 |m in.exe|cution. |
|000019f0| 20 54 68 65 20 61 6c 67 | 6f 72 69 74 68 6d 27 73 | The alg|orithm's|
|00001a00| 20 20 64 61 74 61 20 20 | 73 74 72 75 63 74 75 72 |  data  |structur|
|00001a10| 65 73 2c 20 77 68 69 63 | 68 20 20 66 6f 72 6d 20 |es, whic|h  form |
|00001a20| 69 74 73 20 20 73 6f 75 | 72 63 65 0a 6d 6f 64 65 |its  sou|rce.mode|
|00001a30| 6c 2c 20 63 6f 6e 73 69 | 73 74 20 6f 66 20 61 20 |l, consi|st of a |
|00001a40| 66 65 77 20 73 63 61 6c | 61 72 20 20 76 61 72 69 |few scal|ar  vari|
|00001a50| 61 62 6c 65 73 2c 20 74 | 68 65 20 69 6e 70 75 74 |ables, t|he input|
|00001a60| 20 62 6c 6f 63 6b 2c 20 | 61 6e 64 20 61 20 68 61 | block, |and a ha|
|00001a70| 73 68 0a 74 61 62 6c 65 | 20 6f 66 20 20 34 30 39 |sh.table| of  409|
|00001a80| 36 20 70 6f 69 6e 74 65 | 72 73 2e 20 54 68 65 20 |6 pointe|rs. The |
|00001a90| 68 61 73 68 20 20 74 61 | 62 6c 65 20 6d 61 70 73 |hash  ta|ble maps|
|00001aa0| 20 61 6e 79 20 74 68 72 | 65 65 20 20 62 79 74 65 | any thr|ee  byte|
|00001ab0| 20 6b 65 79 20 74 6f 20 | 61 0a 73 69 6e 67 6c 65 | key to |a.single|
|00001ac0| 20 70 6f 69 6e 74 65 72 | 20 74 68 61 74 20 63 61 | pointer| that ca|
|00001ad0| 6e 20 70 6f 69 6e 74 20 | 61 6e 79 77 68 65 72 65 |n point |anywhere|
|00001ae0| 20 20 69 6e 20 6d 65 6d | 6f 72 79 2c 20 62 75 74 |  in mem|ory, but|
|00001af0| 20 77 68 69 63 68 20 69 | 73 20 6c 69 6b 65 6c 79 | which i|s likely|
|00001b00| 0a 74 6f 20 70 6f 69 6e | 74 20 74 6f 20 61 20 20 |.to poin|t to a  |
|00001b10| 6d 61 74 63 68 69 6e 67 | 20 6b 65 79 20 73 6f 6d |matching| key som|
|00001b20| 65 77 68 65 72 65 20 69 | 6e 20 74 68 65 20 4c 65 |ewhere i|n the Le|
|00001b30| 6d 70 65 6c 2e 20 20 41 | 74 20 65 61 63 68 20 73 |mpel.  A|t each s|
|00001b40| 74 65 70 20 74 68 65 0a | 68 61 73 68 20 74 61 62 |tep the.|hash tab|
|00001b50| 6c 65 20 69 73 20 75 73 | 65 64 20 74 6f 20 74 72 |le is us|ed to tr|
|00001b60| 79 20 74 6f 20 66 69 6e | 64 20 20 61 20 6d 61 74 |y to fin|d  a mat|
|00001b70| 63 68 20 69 6e 20 74 68 | 65 20 4c 65 6d 70 65 6c |ch in th|e Lempel|
|00001b80| 20 66 6f 72 20 74 68 65 | 20 66 69 72 73 74 0a 74 | for the| first.t|
|00001b90| 68 72 65 65 20 6f 72 20 | 20 6d 6f 72 65 20 62 79 |hree or | more by|
|00001ba0| 74 65 73 20 6f 66 20 20 | 74 68 65 20 5c 62 7b 5a |tes of  |the \b{Z|
|00001bb0| 69 76 7d 20 28 74 68 65 | 20 6e 65 78 74 20 20 31 |iv} (the| next  1|
|00001bc0| 36 20 62 79 74 65 73 20 | 74 6f 20 20 62 65 20 63 |6 bytes |to  be c|
|00001bd0| 6f 64 65 64 29 0a 77 69 | 74 68 20 61 20 6d 61 74 |oded).wi|th a mat|
|00001be0| 63 68 20 20 72 65 73 75 | 6c 74 69 6e 67 20 69 6e |ch  resu|lting in|
|00001bf0| 20 74 68 65 20 67 65 6e | 65 72 61 74 69 6f 6e 20 | the gen|eration |
|00001c00| 6f 66 20 61 20 20 63 6f | 70 79 20 69 74 65 6d 2e |of a  co|py item.|
|00001c10| 20 42 65 63 61 75 73 65 | 20 74 68 65 0a 61 6c 67 | Because| the.alg|
|00001c20| 6f 72 69 74 68 6d 20 63 | 68 65 63 6b 73 20 61 6c |orithm c|hecks al|
|00001c30| 6c 20 70 6f 69 6e 74 65 | 72 73 20 74 68 61 74 20 |l pointe|rs that |
|00001c40| 69 74 20 66 65 74 63 68 | 65 73 20 66 72 6f 6d 20 |it fetch|es from |
|00001c50| 74 68 65 20 68 61 73 68 | 20 74 61 62 6c 65 2c 20 |the hash| table, |
|00001c60| 74 68 65 0a 68 61 73 68 | 20 74 61 62 6c 65 20 20 |the.hash| table  |
|00001c70| 64 6f 65 73 20 6e 6f 74 | 20 6e 65 65 64 20 20 74 |does not| need  t|
|00001c80| 6f 20 62 65 20 20 69 6e | 69 74 69 61 6c 69 7a 65 |o be  in|itialize|
|00001c90| 64 2e 20 4c 5a 52 57 31 | 20 75 70 64 61 74 65 73 |d. LZRW1| updates|
|00001ca0| 20 20 69 74 73 20 68 61 | 73 68 0a 74 61 62 6c 65 |  its ha|sh.table|
|00001cb0| 20 61 66 74 65 72 20 65 | 76 65 72 79 20 20 69 74 | after e|very  it|
|00001cc0| 65 6d 20 72 61 74 68 65 | 72 20 74 68 61 6e 20 65 |em rathe|r than e|
|00001cd0| 76 65 72 79 20 62 79 74 | 65 2c 20 6d 61 6b 69 6e |very byt|e, makin|
|00001ce0| 67 20 20 74 68 65 20 68 | 61 73 68 20 74 61 62 6c |g  the h|ash tabl|
|00001cf0| 65 0a 75 70 64 61 74 65 | 20 72 61 74 65 20 20 69 |e.update| rate  i|
|00001d00| 6e 76 65 72 73 65 6c 79 | 20 70 72 6f 70 6f 72 74 |nversely| proport|
|00001d10| 69 6f 6e 61 6c 20 20 74 | 6f 20 63 6f 6d 70 72 65 |ional  t|o compre|
|00001d20| 73 73 69 6f 6e 2e 20 54 | 68 69 73 20 20 70 6f 6c |ssion. T|his  pol|
|00001d30| 69 63 79 20 61 6c 73 6f | 0a 65 78 70 6c 6f 69 74 |icy also|.exploit|
|00001d40| 73 20 74 68 65 20 70 68 | 72 61 73 65 20 73 74 72 |s the ph|rase str|
|00001d50| 75 63 74 75 72 65 5c 70 | 61 70 65 72 7b 4c 61 6e |ucture\p|aper{Lan|
|00001d60| 67 64 6f 6e 38 34 7d 20 | 70 72 65 73 65 6e 74 20 |gdon84} |present |
|00001d70| 69 6e 20 6d 6f 73 74 20 | 64 61 74 61 2e 0a 0a 44 |in most |data...D|
|00001d80| 65 63 6f 6d 70 72 65 73 | 73 69 6f 6e 20 69 73 20 |ecompres|sion is |
|00001d90| 65 78 74 72 65 6d 65 6c | 79 20 73 69 6d 70 6c 65 |extremel|y simple|
|00001da0| 20 61 6e 64 20 66 61 73 | 74 2e 20 54 68 65 20 64 | and fas|t. The d|
|00001db0| 65 63 6f 6d 70 72 65 73 | 73 6f 72 20 70 72 6f 63 |ecompres|sor proc|
|00001dc0| 65 73 73 65 73 0a 6f 6e | 65 20 69 74 65 6d 20 61 |esses.on|e item a|
|00001dd0| 74 20 20 61 20 74 69 6d | 65 2c 20 74 72 61 6e 73 |t  a tim|e, trans|
|00001de0| 6c 61 74 69 6e 67 20 69 | 74 20 20 69 6e 74 6f 20 |lating i|t  into |
|00001df0| 6f 6e 65 20 6f 72 20 6d | 6f 72 65 20 20 62 79 74 |one or m|ore  byt|
|00001e00| 65 73 20 77 68 69 63 68 | 20 61 72 65 0a 61 70 70 |es which| are.app|
|00001e10| 65 6e 64 65 64 20 74 6f | 20 74 68 65 20 65 6e 64 |ended to| the end|
|00001e20| 20 6f 66 20 74 68 65 20 | 6f 75 74 70 75 74 2e 20 | of the |output. |
|00001e30| 20 49 66 20 74 68 65 20 | 69 74 65 6d 20 69 73 20 | If the |item is |
|00001e40| 61 20 6c 69 74 65 72 61 | 6c 20 69 74 65 6d 2c 20 |a litera|l item, |
|00001e50| 69 74 73 0a 73 69 6e 67 | 6c 65 20 20 6c 69 74 65 |its.sing|le  lite|
|00001e60| 72 61 6c 20 62 79 74 65 | 20 20 69 73 20 61 70 70 |ral byte|  is app|
|00001e70| 65 6e 64 65 64 2e 20 20 | 49 66 20 74 68 65 20 20 |ended.  |If the  |
|00001e80| 69 74 65 6d 20 69 73 20 | 20 61 20 63 6f 70 79 20 |item is | a copy |
|00001e90| 20 69 74 65 6d 2c 20 74 | 68 65 0a 6c 65 6e 67 74 | item, t|he.lengt|
|00001ea0| 68 20 61 6e 64 20 6f 66 | 66 73 65 74 20 66 69 65 |h and of|fset fie|
|00001eb0| 6c 64 73 20 61 72 65 20 | 75 73 65 64 20 20 74 6f |lds are |used  to|
|00001ec0| 20 6c 6f 63 61 74 65 20 | 61 6e 64 20 63 6f 70 79 | locate |and copy|
|00001ed0| 20 61 20 73 74 72 69 6e | 67 20 61 6c 72 65 61 64 | a strin|g alread|
|00001ee0| 79 0a 69 6e 20 74 68 65 | 20 6f 75 74 70 75 74 20 |y.in the| output |
|00001ef0| 62 6c 6f 63 6b 2e 20 43 | 6f 6e 74 72 6f 6c 20 62 |block. C|ontrol b|
|00001f00| 69 74 73 20 6d 75 73 74 | 20 62 65 20 62 75 66 66 |its must| be buff|
|00001f10| 65 72 65 64 2e 0a 0a 4c | 5a 52 57 31 27 73 20 68 |ered...L|ZRW1's h|
|00001f20| 61 73 68 20 66 75 6e 63 | 74 69 6f 6e 20 69 73 20 |ash func|tion is |
|00001f30| 63 6f 6e 73 74 72 75 63 | 74 65 64 20 20 69 6e 20 |construc|ted  in |
|00001f40| 61 63 63 6f 72 64 61 6e | 63 65 20 77 69 74 68 20 |accordan|ce with |
|00001f50| 74 68 65 20 61 64 76 69 | 63 65 20 69 6e 0a 5c 70 |the advi|ce in.\p|
|00001f60| 61 70 65 72 7b 4b 6e 75 | 74 68 38 31 7d 20 61 6e |aper{Knu|th81} an|
|00001f70| 64 20 20 73 65 65 6d 73 | 20 74 6f 20 20 62 65 20 |d  seems| to  be |
|00001f80| 6e 65 61 72 20 20 6f 70 | 74 69 6d 61 6c 2e 20 41 |near  op|timal. A|
|00001f90| 20 20 72 65 63 65 6e 74 | 6c 79 20 70 75 62 6c 69 |  recent|ly publi|
|00001fa0| 73 68 65 64 0a 68 61 73 | 68 20 66 75 6e 63 74 69 |shed.has|h functi|
|00001fb0| 6f 6e 20 74 68 61 74 20 | 75 73 65 64 20 61 20 6c |on that |used a l|
|00001fc0| 6f 6f 6b 75 70 20 74 61 | 62 6c 65 5c 70 61 70 65 |ookup ta|ble\pape|
|00001fd0| 72 7b 50 65 61 72 73 6f | 6e 39 30 7d 20 77 61 73 |r{Pearso|n90} was|
|00001fe0| 20 74 72 69 65 64 2c 20 | 62 75 74 0a 79 69 65 6c | tried, |but.yiel|
|00001ff0| 64 65 64 20 69 64 65 6e | 74 69 63 61 6c 20 70 65 |ded iden|tical pe|
|00002000| 72 66 6f 72 6d 61 6e 63 | 65 2e 20 4c 5a 52 57 31 |rformanc|e. LZRW1|
|00002010| 27 73 20 68 61 73 68 20 | 74 61 62 6c 65 20 70 72 |'s hash |table pr|
|00002020| 6f 76 69 64 65 73 20 61 | 74 20 6d 6f 73 74 20 74 |ovides a|t most t|
|00002030| 68 65 0a 6d 6f 73 74 20 | 72 65 63 65 6e 74 20 4c |he.most |recent L|
|00002040| 65 6d 70 65 6c 20 6d 61 | 74 63 68 20 6f 66 20 61 |empel ma|tch of a|
|00002050| 20 6b 65 79 2e 20 42 65 | 6c 6c 5c 70 61 70 65 72 | key. Be|ll\paper|
|00002060| 7b 42 65 6c 6c 39 30 62 | 7d 20 64 69 73 63 75 73 |{Bell90b|} discus|
|00002070| 73 65 73 20 6f 74 68 65 | 72 0a 4c 5a 37 37 20 73 |ses othe|r.LZ77 s|
|00002080| 65 61 72 63 68 20 74 65 | 63 68 6e 69 71 75 65 73 |earch te|chniques|
|00002090| 2e 0a 0a 41 20 70 72 65 | 63 69 73 65 20 73 70 65 |...A pre|cise spe|
|000020a0| 63 69 66 69 63 61 74 69 | 6f 6e 20 20 6f 66 20 74 |cificati|on  of t|
|000020b0| 68 65 20 4c 5a 52 57 31 | 20 74 65 78 74 20 20 64 |he LZRW1| text  d|
|000020c0| 61 74 61 20 63 6f 6d 70 | 72 65 73 73 69 6f 6e 20 |ata comp|ression |
|000020d0| 61 6c 67 6f 72 69 74 68 | 6d 0a 69 73 20 67 69 76 |algorith|m.is giv|
|000020e0| 65 6e 20 69 6e 20 5c 62 | 7b 46 69 67 75 72 65 73 |en in \b|{Figures|
|000020f0| 7e 34 2d 2d 36 7d 20 77 | 68 69 63 68 20 70 72 6f |~4--6} w|hich pro|
|00002100| 76 69 64 65 20 61 20 74 | 75 72 6e 6b 65 79 20 69 |vide a t|urnkey i|
|00002110| 6d 70 6c 65 6d 65 6e 74 | 61 74 69 6f 6e 20 69 6e |mplement|ation in|
|00002120| 0a 74 68 65 7e 43 20 70 | 72 6f 67 72 61 6d 6d 69 |.the~C p|rogrammi|
|00002130| 6e 67 20 6c 61 6e 67 75 | 61 67 65 5c 70 61 70 65 |ng langu|age\pape|
|00002140| 72 7b 4b 65 72 6e 69 67 | 68 61 6e 38 38 7d 2e 0a |r{Kernig|han88}..|
|00002150| 0a 5c 73 65 63 74 69 6f | 6e 7b 45 78 70 65 72 69 |.\sectio|n{Experi|
|00002160| 6d 65 6e 74 73 7d 0a 0a | 54 6f 20 74 65 73 74 20 |ments}..|To test |
|00002170| 69 74 73 20 20 70 65 72 | 66 6f 72 6d 61 6e 63 65 |its  per|formance|
|00002180| 2c 20 4c 5a 52 57 31 20 | 77 61 73 20 69 6d 70 6c |, LZRW1 |was impl|
|00002190| 65 6d 65 6e 74 65 64 20 | 69 6e 20 68 69 67 68 20 |emented |in high |
|000021a0| 20 61 6e 64 20 6c 6f 77 | 20 6c 65 76 65 6c 0a 6c | and low| level.l|
|000021b0| 61 6e 67 75 61 67 65 73 | 20 61 6e 64 20 61 70 70 |anguages| and app|
|000021c0| 6c 69 65 64 20 20 74 6f | 20 74 68 65 20 73 74 61 |lied  to| the sta|
|000021d0| 6e 64 61 72 64 20 63 6f | 72 70 75 73 20 6f 66 20 |ndard co|rpus of |
|000021e0| 20 74 65 73 74 20 66 69 | 6c 65 73 20 64 65 73 63 | test fi|les desc|
|000021f0| 72 69 62 65 64 0a 69 6e | 20 41 70 70 65 6e 64 69 |ribed.in| Appendi|
|00002200| 78 7e 42 20 6f 66 20 5c | 70 61 70 65 72 7b 42 65 |x~B of \|paper{Be|
|00002210| 6c 6c 39 30 61 7d 2e 0a | 0a 5c 63 69 74 65 66 69 |ll90a}..|.\citefi|
|00002220| 67 75 72 65 7b 37 7d 20 | 67 69 76 65 73 20 20 74 |gure{7} |gives  t|
|00002230| 68 65 20 72 65 73 75 6c | 74 73 20 20 6f 66 20 72 |he resul|ts  of r|
|00002240| 75 6e 6e 69 6e 67 20 74 | 68 65 20 20 43 7e 69 6d |unning t|he  C~im|
|00002250| 70 6c 65 6d 65 6e 74 61 | 74 69 6f 6e 20 6f 66 0a |plementa|tion of.|
|00002260| 4c 5a 52 57 31 20 6f 66 | 20 5c 62 7b 46 69 67 75 |LZRW1 of| \b{Figu|
|00002270| 72 65 73 7e 34 2d 2d 36 | 7d 20 20 61 67 61 69 6e |res~4--6|}  again|
|00002280| 73 74 20 61 20 73 69 6d | 69 6c 61 72 20 69 6d 70 |st a sim|ilar imp|
|00002290| 6c 65 6d 65 6e 74 61 74 | 69 6f 6e 20 20 6f 66 20 |lementat|ion  of |
|000022a0| 74 68 65 20 41 31 0a 61 | 6c 67 6f 72 69 74 68 6d |the A1.a|lgorithm|
|000022b0| 20 20 61 6e 64 20 20 61 | 67 61 69 6e 73 74 20 20 |  and  a|gainst  |
|000022c0| 74 68 65 20 20 55 6e 69 | 78 20 20 5c 69 7b 63 6f |the  Uni|x  \i{co|
|000022d0| 6d 70 72 65 73 73 7d 20 | 20 75 74 69 6c 69 74 79 |mpress} | utility|
|000022e0| 20 20 28 4c 5a 43 29 20 | 20 6f 6e 20 61 0a 50 79 |  (LZC) | on a.Py|
|000022f0| 72 61 6d 69 64 7e 39 38 | 32 30 20 63 6f 6d 70 75 |ramid~98|20 compu|
|00002300| 74 65 72 20 72 75 6e 6e | 69 6e 67 20 55 6e 69 78 |ter runn|ing Unix|
|00002310| 2e 20 20 4c 5a 52 57 31 | 20 63 6f 6d 70 72 65 73 |.  LZRW1| compres|
|00002320| 73 65 73 20 61 62 6f 75 | 74 20 31 30 5c 25 20 77 |ses abou|t 10\% w|
|00002330| 6f 72 73 65 0a 74 68 61 | 6e 20 4c 5a 43 2c 20 20 |orse.tha|n LZC,  |
|00002340| 62 75 74 20 72 75 6e 73 | 20 20 66 6f 75 72 20 74 |but runs|  four t|
|00002350| 69 6d 65 73 20 66 61 73 | 74 65 72 2e 20 20 4c 5a |imes fas|ter.  LZ|
|00002360| 52 57 31 20 63 6f 6d 70 | 72 65 73 73 65 73 20 20 |RW1 comp|resses  |
|00002370| 61 62 6f 75 74 20 34 2e | 33 5c 25 0a 77 6f 72 73 |about 4.|3\%.wors|
|00002380| 65 20 74 68 61 6e 20 74 | 68 65 20 41 31 20 61 6c |e than t|he A1 al|
|00002390| 67 6f 72 69 74 68 6d 2c | 20 62 75 74 20 72 75 6e |gorithm,| but run|
|000023a0| 73 20 74 65 6e 20 74 69 | 6d 65 73 20 66 61 73 74 |s ten ti|mes fast|
|000023b0| 65 72 2e 20 54 68 69 73 | 20 69 6e 64 69 63 61 74 |er. This| indicat|
|000023c0| 65 73 0a 74 68 61 74 20 | 41 31 27 73 20 20 65 78 |es.that |A1's  ex|
|000023d0| 68 61 75 73 74 69 76 65 | 20 73 65 61 72 63 68 20 |haustive| search |
|000023e0| 6f 66 20 74 68 65 20 20 | 4c 65 6d 70 65 6c 20 61 |of the  |Lempel a|
|000023f0| 6e 64 20 69 74 73 20 75 | 73 65 20 20 6f 66 20 61 |nd its u|se  of a|
|00002400| 20 74 77 6f 2d 62 79 74 | 65 0a 6d 69 6e 69 6d 75 | two-byt|e.minimu|
|00002410| 6d 20 63 6f 70 79 20 6c | 65 6e 67 74 68 20 64 6f |m copy l|ength do|
|00002420| 65 73 20 6e 6f 74 20 67 | 72 65 61 74 6c 79 20 69 |es not g|reatly i|
|00002430| 6d 70 72 6f 76 65 20 69 | 74 73 20 63 6f 6d 70 72 |mprove i|ts compr|
|00002440| 65 73 73 69 6f 6e 2e 0a | 0a 5c 63 69 74 65 66 69 |ession..|.\citefi|
|00002450| 67 75 72 65 7b 38 7d 20 | 20 67 69 76 65 73 20 20 |gure{8} | gives  |
|00002460| 74 68 65 20 20 70 65 72 | 66 6f 72 6d 61 6e 63 65 |the  per|formance|
|00002470| 20 20 6f 66 20 20 61 6e | 20 20 68 61 6e 64 2d 6f |  of  an|  hand-o|
|00002480| 70 74 69 6d 69 7a 65 64 | 20 20 36 38 30 30 30 0a |ptimized|  68000.|
|00002490| 61 73 73 65 6d 62 6c 79 | 20 20 6c 61 6e 67 75 61 |assembly|  langua|
|000024a0| 67 65 20 20 69 6d 70 6c | 65 6d 65 6e 74 61 74 69 |ge  impl|ementati|
|000024b0| 6f 6e 20 6f 66 20 20 4c | 5a 52 57 31 20 20 72 75 |on of  L|ZRW1  ru|
|000024c0| 6e 6e 69 6e 67 20 20 69 | 74 20 6f 6e 20 20 61 6e |nning  i|t on  an|
|000024d0| 20 20 38 4d 48 7a 0a 4d | 61 63 69 6e 74 6f 73 68 |  8MHz.M|acintosh|
|000024e0| 2d 53 45 20 20 63 6f 6d | 70 75 74 65 72 2e 20 4c |-SE  com|puter. L|
|000024f0| 5a 52 57 31 20 20 61 63 | 68 69 65 76 65 73 20 20 |ZRW1  ac|hieves  |
|00002500| 72 65 61 73 6f 6e 61 62 | 6c 65 20 63 6f 6d 70 72 |reasonab|le compr|
|00002510| 65 73 73 69 6f 6e 20 20 | 77 68 69 6c 65 0a 72 65 |ession  |while.re|
|00002520| 71 75 69 72 69 6e 67 20 | 61 6e 20 61 76 65 72 61 |quiring |an avera|
|00002530| 67 65 20 6f 66 20 6a 75 | 73 74 20 74 68 69 72 74 |ge of ju|st thirt|
|00002540| 65 65 6e 20 6d 61 63 68 | 69 6e 65 20 69 6e 73 74 |een mach|ine inst|
|00002550| 72 75 63 74 69 6f 6e 73 | 20 74 6f 20 63 6f 6d 70 |ructions| to comp|
|00002560| 72 65 73 73 0a 61 6e 64 | 20 66 6f 75 72 20 6d 61 |ress.and| four ma|
|00002570| 63 68 69 6e 65 20 69 6e | 73 74 72 75 63 74 69 6f |chine in|structio|
|00002580| 6e 73 20 74 6f 20 64 65 | 63 6f 6d 70 72 65 73 73 |ns to de|compress|
|00002590| 20 65 61 63 68 20 62 79 | 74 65 2e 20 54 68 65 20 | each by|te. The |
|000025a0| 70 65 72 66 6f 72 6d 61 | 6e 63 65 0a 6f 66 20 20 |performa|nce.of  |
|000025b0| 4c 5a 52 57 31 20 20 6f | 6e 20 20 74 68 65 20 20 |LZRW1  o|n  the  |
|000025c0| 66 69 6c 65 73 20 5c 69 | 7b 7a 65 72 6f 73 7d 20 |files \i|{zeros} |
|000025d0| 20 61 6e 64 20 20 5c 69 | 7b 6e 6f 69 73 65 7d 20 | and  \i|{noise} |
|000025e0| 20 64 65 6d 6f 6e 73 74 | 72 61 74 65 73 20 20 74 | demonst|rates  t|
|000025f0| 68 65 0a 73 74 61 62 69 | 6c 69 74 79 20 6f 66 20 |he.stabi|lity of |
|00002600| 74 68 65 20 61 6c 67 6f | 72 69 74 68 6d 2e 20 46 |the algo|rithm. F|
|00002610| 6f 72 20 74 68 65 20 20 | 36 38 30 30 30 20 72 75 |or the  |68000 ru|
|00002620| 6e 73 2c 20 65 61 63 68 | 20 66 69 6c 65 20 77 61 |ns, each| file wa|
|00002630| 73 20 64 69 76 69 64 65 | 64 0a 69 6e 74 6f 20 20 |s divide|d.into  |
|00002640| 31 36 4b 20 62 6c 6f 63 | 6b 73 20 20 65 61 63 68 |16K bloc|ks  each|
|00002650| 20 20 6f 66 20 77 68 69 | 63 68 20 20 77 61 73 20 |  of whi|ch  was |
|00002660| 20 63 6f 6d 70 72 65 73 | 73 65 64 20 69 6e 64 65 | compres|sed inde|
|00002670| 70 65 6e 64 65 6e 74 6c | 79 2e 20 20 54 68 69 73 |pendentl|y.  This|
|00002680| 0a 69 6d 70 61 69 72 65 | 64 20 63 6f 6d 70 72 65 |.impaire|d compre|
|00002690| 73 73 69 6f 6e 20 62 79 | 20 20 61 74 20 6d 6f 73 |ssion by|  at mos|
|000026a0| 74 20 32 5c 25 20 61 62 | 73 6f 6c 75 74 65 2e 20 |t 2\% ab|solute. |
|000026b0| 54 68 69 73 20 20 66 61 | 63 74 20 63 6f 75 70 6c |This  fa|ct coupl|
|000026c0| 65 64 20 77 69 74 68 0a | 4c 5a 52 57 31 27 73 20 |ed with.|LZRW1's |
|000026d0| 20 6e 65 67 6c 69 67 69 | 62 6c 65 20 69 6e 69 74 | negligi|ble init|
|000026e0| 69 61 6c 69 7a 61 74 69 | 6f 6e 20 20 63 6f 73 74 |ializati|on  cost|
|000026f0| 20 6d 61 6b 65 73 20 20 | 4c 5a 52 57 31 20 69 64 | makes  |LZRW1 id|
|00002700| 65 61 6c 20 20 66 6f 72 | 20 73 6d 61 6c 6c 0a 62 |eal  for| small.b|
|00002710| 6c 6f 63 6b 73 20 6f 66 | 20 64 61 74 61 2e 0a 0a |locks of| data...|
|00002720| 5c 73 65 63 74 69 6f 6e | 7b 43 6f 6e 63 6c 75 73 |\section|{Conclus|
|00002730| 69 6f 6e 7d 0a 0a 55 73 | 65 20 6f 66 20 61 20 20 |ion}..Us|e of a  |
|00002740| 73 69 6d 70 6c 65 20 68 | 61 73 68 20 74 61 62 6c |simple h|ash tabl|
|00002750| 65 20 6d 65 63 68 61 6e | 69 73 6d 20 61 6c 6f 6e |e mechan|ism alon|
|00002760| 67 20 20 77 69 74 68 20 | 72 75 74 68 6c 65 73 73 |g  with |ruthless|
|00002770| 20 65 6c 69 6d 69 6e 61 | 74 69 6f 6e 0a 6f 66 20 | elimina|tion.of |
|00002780| 68 6f 75 73 65 6b 65 65 | 70 69 6e 67 20 68 61 73 |housekee|ping has|
|00002790| 20 20 6c 65 64 20 74 6f | 20 74 68 65 20 65 78 74 |  led to| the ext|
|000027a0| 72 65 6d 65 6c 79 20 66 | 61 73 74 20 20 4c 5a 52 |remely f|ast  LZR|
|000027b0| 57 31 20 74 65 78 74 20 | 63 6f 6d 70 72 65 73 73 |W1 text |compress|
|000027c0| 69 6f 6e 0a 61 6c 67 6f | 72 69 74 68 6d 20 74 68 |ion.algo|rithm th|
|000027d0| 61 74 20 72 65 71 75 69 | 72 65 73 20 61 62 6f 75 |at requi|res abou|
|000027e0| 74 20 31 33 20 6d 61 63 | 68 69 6e 65 20 69 6e 73 |t 13 mac|hine ins|
|000027f0| 74 72 75 63 74 69 6f 6e | 73 20 74 6f 20 63 6f 6d |truction|s to com|
|00002800| 70 72 65 73 73 20 65 61 | 63 68 0a 62 79 74 65 20 |press ea|ch.byte |
|00002810| 61 6e 64 20 20 61 62 6f | 75 74 20 34 20 6d 61 63 |and  abo|ut 4 mac|
|00002820| 68 69 6e 65 20 20 69 6e | 73 74 72 75 63 74 69 6f |hine  in|structio|
|00002830| 6e 73 20 74 6f 20 64 65 | 63 6f 6d 70 72 65 73 73 |ns to de|compress|
|00002840| 20 65 61 63 68 20 20 62 | 79 74 65 2e 20 54 68 69 | each  b|yte. Thi|
|00002850| 73 0a 72 65 73 75 6c 74 | 73 20 20 69 6e 20 73 70 |s.result|s  in sp|
|00002860| 65 65 64 73 20 20 6f 66 | 20 61 62 6f 75 74 20 20 |eeds  of| about  |
|00002870| 37 37 4b 20 61 6e 64 20 | 20 32 35 30 4b 20 70 65 |77K and | 250K pe|
|00002880| 72 20 20 73 65 63 6f 6e | 64 20 6f 6e 20 20 61 20 |r  secon|d on  a |
|00002890| 6f 6e 65 20 20 4d 49 50 | 0a 6d 61 63 68 69 6e 65 |one  MIP|.machine|
|000028a0| 2e 20 20 4c 5a 52 57 31 | 20 63 6f 6d 70 72 65 73 |.  LZRW1| compres|
|000028b0| 73 65 73 20 20 74 65 6e | 20 70 65 72 63 65 6e 74 |ses  ten| percent|
|000028c0| 20 20 77 6f 72 73 65 20 | 74 68 61 6e 20 20 74 68 |  worse |than  th|
|000028d0| 65 20 70 6f 70 75 6c 61 | 72 20 20 55 6e 69 78 0a |e popula|r  Unix.|
|000028e0| 5c 69 7b 63 6f 6d 70 72 | 65 73 73 7d 20 75 74 69 |\i{compr|ess} uti|
|000028f0| 6c 69 74 79 2c 20 62 75 | 74 20 20 72 75 6e 73 20 |lity, bu|t  runs |
|00002900| 66 6f 75 72 20 74 69 6d | 65 73 20 66 61 73 74 65 |four tim|es faste|
|00002910| 72 2c 20 20 6d 61 6b 69 | 6e 67 20 69 74 20 70 6f |r,  maki|ng it po|
|00002920| 73 73 69 62 6c 79 0a 74 | 68 65 20 66 61 73 74 65 |ssibly.t|he faste|
|00002930| 73 74 20 61 64 61 70 74 | 69 76 65 20 74 65 78 74 |st adapt|ive text|
|00002940| 20 63 6f 6d 70 72 65 73 | 73 69 6f 6e 20 61 6c 67 | compres|sion alg|
|00002950| 6f 72 69 74 68 6d 20 79 | 65 74 2e 0a 0a 5c 73 65 |orithm y|et...\se|
|00002960| 63 74 69 6f 6e 7b 52 65 | 66 65 72 65 6e 63 65 73 |ction{Re|ferences|
|00002970| 7d 0a 0a 5c 70 61 70 65 | 72 7b 42 65 6c 6c 39 30 |}..\pape|r{Bell90|
|00002980| 61 7d 20 20 42 65 6c 6c | 20 20 20 54 2e 43 2e 2c |a}  Bell|   T.C.,|
|00002990| 20 20 43 6c 65 61 72 79 | 20 20 4a 2e 47 2e 2c 20 |  Cleary|  J.G., |
|000029a0| 20 57 69 74 74 65 6e 20 | 20 20 49 2e 48 2e 2c 20 | Witten |  I.H., |
|000029b0| 20 5c 64 71 7b 54 65 78 | 74 0a 43 6f 6d 70 72 65 | \dq{Tex|t.Compre|
|000029c0| 73 73 69 6f 6e 7d 2c 20 | 50 72 65 6e 74 69 63 65 |ssion}, |Prentice|
|000029d0| 20 48 61 6c 6c 2c 20 45 | 6e 67 6c 65 77 6f 6f 64 | Hall, E|nglewood|
|000029e0| 20 43 6c 69 66 66 73 2c | 20 4e 65 77 20 4a 65 72 | Cliffs,| New Jer|
|000029f0| 73 65 79 2c 20 31 39 39 | 30 2e 0a 0a 5c 6e 6f 69 |sey, 199|0...\noi|
|00002a00| 6e 64 65 6e 74 5c 70 61 | 70 65 72 7b 42 65 6c 6c |ndent\pa|per{Bell|
|00002a10| 39 30 62 7d 20 42 65 6c | 6c 20 54 2e 43 2e 2c 20 |90b} Bel|l T.C., |
|00002a20| 5c 64 71 7b 4c 6f 6e 67 | 65 73 74 20 4d 61 74 63 |\dq{Long|est Matc|
|00002a30| 68 20 53 74 72 69 6e 67 | 20 53 65 61 72 63 68 69 |h String| Searchi|
|00002a40| 6e 67 0a 46 6f 72 20 20 | 20 5a 69 76 2d 4c 65 6d |ng.For  | Ziv-Lem|
|00002a50| 70 65 6c 20 20 43 6f 6d | 70 72 65 73 73 69 6f 6e |pel  Com|pression|
|00002a60| 7d 2c 20 20 20 44 65 70 | 61 72 74 6d 65 6e 74 20 |},   Dep|artment |
|00002a70| 20 20 6f 66 20 20 43 6f | 6d 70 75 74 65 72 20 20 |  of  Co|mputer  |
|00002a80| 20 53 63 69 65 6e 63 65 | 2c 0a 55 6e 69 76 65 72 | Science|,.Univer|
|00002a90| 73 69 74 79 20 6f 66 20 | 43 61 6e 74 65 72 62 75 |sity of |Canterbu|
|00002aa0| 72 79 2c 20 43 68 72 69 | 73 74 63 68 75 72 63 68 |ry, Chri|stchurch|
|00002ab0| 2c 20 4e 65 77 20 5a 65 | 61 6c 61 6e 64 2e 0a 0a |, New Ze|aland...|
|00002ac0| 5c 6e 6f 69 6e 64 65 6e | 74 5c 70 61 70 65 72 7b |\noinden|t\paper{|
|00002ad0| 46 69 61 6c 61 38 38 7d | 20 46 69 61 6c 61 7e 45 |Fiala88}| Fiala~E|
|00002ae0| 2e 52 2e 2c 20 47 72 65 | 65 6e 65 7e 44 2e 48 2e |.R., Gre|ene~D.H.|
|00002af0| 2c 20 5c 64 71 7b 44 61 | 74 61 20 43 6f 6d 70 72 |, \dq{Da|ta Compr|
|00002b00| 65 73 73 69 6f 6e 0a 77 | 69 74 68 20 46 69 6e 69 |ession.w|ith Fini|
|00002b10| 74 65 20 20 57 69 6e 64 | 6f 77 73 7d 2c 20 5c 69 |te  Wind|ows}, \i|
|00002b20| 7b 43 6f 6d 6d 75 6e 69 | 63 61 74 69 6f 6e 73 20 |{Communi|cations |
|00002b30| 6f 66 20 74 68 65 20 20 | 41 43 4d 7d 2c 20 56 6f |of the  |ACM}, Vo|
|00002b40| 6c 2e 7e 33 32 2c 20 4e | 6f 2e 7e 34 2c 0a 70 70 |l.~32, N|o.~4,.pp|
|00002b50| 2e 7e 34 39 30 2d 2d 35 | 30 35 2e 0a 0a 5c 6e 6f |.~490--5|05...\no|
|00002b60| 69 6e 64 65 6e 74 5c 70 | 61 70 65 72 7b 4b 65 72 |indent\p|aper{Ker|
|00002b70| 6e 69 67 68 61 6e 38 38 | 7d 20 20 4b 65 72 6e 69 |nighan88|}  Kerni|
|00002b80| 67 68 61 6e 7e 42 2e 57 | 2e 2c 20 52 69 74 63 68 |ghan~B.W|., Ritch|
|00002b90| 69 65 7e 44 2e 4d 2e 2c | 20 20 5c 64 71 7b 54 68 |ie~D.M.,|  \dq{Th|
|00002ba0| 65 20 43 0a 50 72 6f 67 | 72 61 6d 6d 69 6e 67 20 |e C.Prog|ramming |
|00002bb0| 4c 61 6e 67 75 61 67 65 | 7d 2c 20 20 50 72 65 6e |Language|},  Pren|
|00002bc0| 74 69 63 65 20 48 61 6c | 6c 2c 20 20 45 6e 67 6c |tice Hal|l,  Engl|
|00002bd0| 65 77 6f 6f 64 20 43 6c | 69 66 66 73 2c 20 20 4e |ewood Cl|iffs,  N|
|00002be0| 65 77 20 4a 65 72 73 65 | 79 2c 0a 31 39 38 38 2e |ew Jerse|y,.1988.|
|00002bf0| 0a 0a 5c 6e 6f 69 6e 64 | 65 6e 74 5c 70 61 70 65 |..\noind|ent\pape|
|00002c00| 72 7b 4b 6e 75 74 68 38 | 31 7d 20 4b 6e 75 74 68 |r{Knuth8|1} Knuth|
|00002c10| 7e 44 2e 45 2e 2c 20 20 | 5c 64 71 7b 53 6f 72 74 |~D.E.,  |\dq{Sort|
|00002c20| 69 6e 67 20 61 6e 64 20 | 20 53 65 61 72 63 68 69 |ing and | Searchi|
|00002c30| 6e 67 7d 2c 20 54 68 65 | 0a 41 72 74 20 20 6f 66 |ng}, The|.Art  of|
|00002c40| 20 20 43 6f 6d 70 75 74 | 65 72 20 20 50 72 6f 67 |  Comput|er  Prog|
|00002c50| 72 61 6d 6d 69 6e 67 2c | 20 20 20 56 6f 6c 2e 7e |ramming,|   Vol.~|
|00002c60| 32 33 2c 20 20 41 64 64 | 69 73 6f 6e 2d 57 65 73 |23,  Add|ison-Wes|
|00002c70| 6c 65 79 20 20 50 75 62 | 6c 69 73 68 69 6e 67 0a |ley  Pub|lishing.|
|00002c80| 43 6f 6d 70 61 6e 79 2c | 20 52 65 61 64 69 6e 67 |Company,| Reading|
|00002c90| 2c 20 4d 61 73 73 61 63 | 68 75 73 65 74 74 73 2c |, Massac|husetts,|
|00002ca0| 20 31 39 37 33 2e 0a 0a | 5c 6e 6f 69 6e 64 65 6e | 1973...|\noinden|
|00002cb0| 74 5c 70 61 70 65 72 7b | 4c 61 6e 67 64 6f 6e 38 |t\paper{|Langdon8|
|00002cc0| 34 7d 20 20 20 4c 61 6e | 67 64 6f 6e 7e 47 2e 47 |4}   Lan|gdon~G.G|
|00002cd0| 2c 20 20 20 20 5c 64 71 | 7b 4f 6e 20 20 20 50 61 |,    \dq|{On   Pa|
|00002ce0| 72 73 69 6e 67 20 20 20 | 56 65 72 73 75 73 0a 4d |rsing   |Versus.M|
|00002cf0| 69 78 65 64 2d 4f 72 64 | 65 72 20 20 4d 6f 64 65 |ixed-Ord|er  Mode|
|00002d00| 6c 20 20 53 74 72 75 63 | 74 75 72 65 73 20 20 66 |l  Struc|tures  f|
|00002d10| 6f 72 20 44 61 74 61 20 | 20 43 6f 6d 70 72 65 73 |or Data | Compres|
|00002d20| 73 69 6f 6e 7d 2c 20 20 | 49 42 4d 20 20 52 65 73 |sion},  |IBM  Res|
|00002d30| 65 61 72 63 68 0a 52 65 | 70 6f 72 74 20 52 4a 2d |earch.Re|port RJ-|
|00002d40| 34 31 36 33 20 28 34 36 | 30 39 31 29 20 31 2f 31 |4163 (46|091) 1/1|
|00002d50| 38 2f 38 34 2c 20 49 42 | 4d 20 20 52 65 73 65 61 |8/84, IB|M  Resea|
|00002d60| 72 63 68 20 4c 61 62 6f | 72 61 74 6f 72 79 2c 20 |rch Labo|ratory, |
|00002d70| 53 61 6e 20 4a 6f 73 65 | 2c 20 43 41 0a 39 35 31 |San Jose|, CA.951|
|00002d80| 39 33 2c 20 31 39 38 34 | 2e 0a 0a 5c 6e 6f 69 6e |93, 1984|...\noin|
|00002d90| 64 65 6e 74 5c 70 61 70 | 65 72 7b 50 65 61 72 73 |dent\pap|er{Pears|
|00002da0| 6f 6e 39 30 7d 20 20 20 | 20 50 65 61 72 73 6f 6e |on90}   | Pearson|
|00002db0| 7e 50 2e 4b 2e 2c 20 20 | 20 5c 64 71 7b 46 61 73 |~P.K.,  | \dq{Fas|
|00002dc0| 74 20 20 20 20 48 61 73 | 68 69 6e 67 20 20 20 6f |t    Has|hing   o|
|00002dd0| 66 0a 56 61 72 69 61 62 | 6c 65 2d 4c 65 6e 67 74 |f.Variab|le-Lengt|
|00002de0| 68 20 54 65 78 74 20 53 | 74 72 69 6e 67 73 7d 2c |h Text S|trings},|
|00002df0| 20 5c 69 7b 43 6f 6d 6d | 75 6e 69 63 61 74 69 6f | \i{Comm|unicatio|
|00002e00| 6e 73 20 6f 66 20 74 68 | 65 20 41 43 4d 7d 2c 20 |ns of th|e ACM}, |
|00002e10| 56 6f 6c 2e 7e 33 33 2c | 0a 4e 6f 2e 7e 36 2c 20 |Vol.~33,|.No.~6, |
|00002e20| 4a 75 6e 65 7e 31 39 39 | 30 2c 20 70 70 2e 7e 36 |June~199|0, pp.~6|
|00002e30| 37 37 2d 2d 36 38 30 2e | 0a 0a 5c 6e 6f 69 6e 64 |77--680.|..\noind|
|00002e40| 65 6e 74 5c 70 61 70 65 | 72 7b 53 74 6f 72 65 72 |ent\pape|r{Storer|
|00002e50| 38 38 7d 20 20 53 74 6f | 72 65 72 7e 4a 2e 41 2e |88}  Sto|rer~J.A.|
|00002e60| 2c 20 5c 64 71 7b 44 61 | 74 61 20 20 43 6f 6d 70 |, \dq{Da|ta  Comp|
|00002e70| 72 65 73 73 69 6f 6e 3a | 20 4d 65 74 68 6f 64 73 |ression:| Methods|
|00002e80| 0a 61 6e 64 20 20 54 68 | 65 6f 72 79 7d 2c 20 20 |.and  Th|eory},  |
|00002e90| 20 43 6f 6d 70 75 74 65 | 72 20 20 53 63 69 65 6e | Compute|r  Scien|
|00002ea0| 63 65 20 20 20 50 72 65 | 73 73 2c 20 20 31 38 30 |ce   Pre|ss,  180|
|00002eb0| 33 20 20 20 52 65 73 65 | 61 72 63 68 20 20 42 6f |3   Rese|arch  Bo|
|00002ec0| 75 6c 76 61 72 64 2c 0a | 52 6f 63 6b 76 69 6c 6c |ulvard,.|Rockvill|
|00002ed0| 65 2c 20 4d 61 72 79 6c | 61 6e 64 20 32 30 38 35 |e, Maryl|and 2085|
|00002ee0| 30 2c 20 31 39 38 38 2e | 0a 0a 5c 6e 6f 69 6e 64 |0, 1988.|..\noind|
|00002ef0| 65 6e 74 5c 70 61 70 65 | 72 7b 57 65 6c 63 68 38 |ent\pape|r{Welch8|
|00002f00| 34 7d 20 20 20 20 57 65 | 6c 63 68 20 20 20 20 54 |4}    We|lch    T|
|00002f10| 2e 41 2e 2c 20 20 20 5c | 64 71 7b 41 20 20 20 20 |.A.,   \|dq{A    |
|00002f20| 54 65 63 68 6e 69 71 75 | 65 20 20 20 20 66 6f 72 |Techniqu|e    for|
|00002f30| 0a 48 69 67 68 2d 50 65 | 72 66 6f 72 6d 61 6e 63 |.High-Pe|rformanc|
|00002f40| 65 20 44 61 74 61 20 43 | 6f 6d 70 72 65 73 73 69 |e Data C|ompressi|
|00002f50| 6f 6e 7d 2c 20 5c 69 7b | 49 45 45 45 20 43 6f 6d |on}, \i{|IEEE Com|
|00002f60| 70 75 74 65 72 7d 2c 20 | 56 6f 6c 2e 7e 31 37 2c |puter}, |Vol.~17,|
|00002f70| 20 4e 6f 2e 7e 36 2c 0a | 70 70 2e 7e 38 2d 2d 31 | No.~6,.|pp.~8--1|
|00002f80| 39 2e 0a 0a 5c 6e 6f 69 | 6e 64 65 6e 74 5c 70 61 |9...\noi|ndent\pa|
|00002f90| 70 65 72 7b 57 69 6c 6c | 69 61 6d 73 39 30 7d 20 |per{Will|iams90} |
|00002fa0| 20 20 20 57 69 6c 6c 69 | 61 6d 73 20 20 20 52 2e |   Willi|ams   R.|
|00002fb0| 4e 2e 2c 20 20 20 20 5c | 64 71 7b 41 64 61 70 74 |N.,    \|dq{Adapt|
|00002fc0| 69 76 65 20 20 20 44 61 | 74 61 0a 43 6f 6d 70 72 |ive   Da|ta.Compr|
|00002fd0| 65 73 73 69 6f 6e 7d 2c | 20 4b 6c 75 77 65 72 20 |ession},| Kluwer |
|00002fe0| 41 63 61 64 65 6d 69 63 | 20 50 75 62 6c 69 73 68 |Academic| Publish|
|00002ff0| 65 72 73 2c 20 31 39 39 | 30 2e 0a 0a 5c 6e 6f 69 |ers, 199|0...\noi|
|00003000| 6e 64 65 6e 74 5c 70 61 | 70 65 72 7b 5a 69 76 37 |ndent\pa|per{Ziv7|
|00003010| 37 7d 20 5a 69 76 20 20 | 4a 2e 2c 20 4c 65 6d 70 |7} Ziv  |J., Lemp|
|00003020| 65 6c 20 20 41 2e 2c 20 | 5c 64 71 7b 41 20 20 55 |el  A., |\dq{A  U|
|00003030| 6e 69 76 65 72 73 61 6c | 20 41 6c 67 6f 72 69 74 |niversal| Algorit|
|00003040| 68 6d 0a 66 6f 72 20 53 | 65 71 75 65 6e 74 69 61 |hm.for S|equentia|
|00003050| 6c 20 44 61 74 61 20 43 | 6f 6d 70 72 65 73 73 69 |l Data C|ompressi|
|00003060| 6f 6e 7d 2c 20 20 5c 69 | 7b 49 45 45 45 20 54 72 |on},  \i|{IEEE Tr|
|00003070| 61 6e 73 61 63 74 69 6f | 6e 73 20 6f 6e 20 49 6e |ansactio|ns on In|
|00003080| 66 6f 72 6d 61 74 69 6f | 6e 0a 54 68 65 6f 72 79 |formatio|n.Theory|
|00003090| 7d 2c 20 56 6f 6c 2e 7e | 32 33 2c 20 4e 6f 2e 7e |}, Vol.~|23, No.~|
|000030a0| 33 2c 20 70 70 2e 7e 33 | 33 37 2d 2d 33 34 33 2e |3, pp.~3|37--343.|
|000030b0| 0a 0a 5c 6e 6f 69 6e 64 | 65 6e 74 5c 70 61 70 65 |..\noind|ent\pape|
|000030c0| 72 7b 5a 69 76 37 38 7d | 20 20 20 5a 69 76 20 20 |r{Ziv78}|   Ziv  |
|000030d0| 4a 2e 2c 20 20 20 4c 65 | 6d 70 65 6c 20 20 20 41 |J.,   Le|mpel   A|
|000030e0| 2e 2c 20 20 5c 64 71 7b | 43 6f 6d 70 72 65 73 73 |.,  \dq{|Compress|
|000030f0| 69 6f 6e 20 20 20 6f 66 | 0a 49 6e 64 69 76 69 64 |ion   of|.Individ|
|00003100| 75 61 6c 20 53 65 71 75 | 65 6e 63 65 73 20 20 76 |ual Sequ|ences  v|
|00003110| 69 61 20 56 61 72 69 61 | 62 6c 65 2d 52 61 74 65 |ia Varia|ble-Rate|
|00003120| 20 43 6f 64 69 6e 67 7d | 2c 20 20 5c 69 7b 49 45 | Coding}|,  \i{IE|
|00003130| 45 45 20 54 72 61 6e 73 | 61 63 74 69 6f 6e 73 0a |EE Trans|actions.|
|00003140| 6f 6e 20 49 6e 66 6f 72 | 6d 61 74 69 6f 6e 20 54 |on Infor|mation T|
|00003150| 68 65 6f 72 79 7d 2c 20 | 56 6f 6c 2e 7e 32 34 2c |heory}, |Vol.~24,|
|00003160| 20 4e 6f 2e 7e 35 2c 20 | 70 70 2e 7e 35 33 30 2d | No.~5, |pp.~530-|
|00003170| 2d 35 33 36 2e 0a 0a 0a | 0a 5c 62 65 67 69 6e 7b |-536....|.\begin{|
|00003180| 66 69 67 75 72 65 7d 0a | 5c 76 73 70 61 63 65 7b |figure}.|\vspace{|
|00003190| 31 32 63 6d 7d 0a 5c 62 | 69 67 63 61 70 74 69 6f |12cm}.\b|igcaptio|
|000031a0| 6e 7b 33 7d 7b 54 68 65 | 20 4c 5a 52 57 31 20 61 |n{3}{The| LZRW1 a|
|000031b0| 6c 67 6f 72 69 74 68 6d | 20 69 6e 20 65 78 65 63 |lgorithm| in exec|
|000031c0| 75 74 69 6f 6e 2e 7d 7b | 25 0a 25 0a 54 68 69 73 |ution.}{|%.%.This|
|000031d0| 20 66 69 67 75 72 65 20 | 20 67 69 76 65 73 20 61 | figure | gives a|
|000031e0| 20 20 73 6e 61 70 73 68 | 6f 74 20 6f 66 20 74 68 |  snapsh|ot of th|
|000031f0| 65 20 20 4c 5a 52 57 31 | 20 63 6f 6d 70 72 65 73 |e  LZRW1| compres|
|00003200| 73 69 6f 6e 20 20 61 6c | 67 6f 72 69 74 68 6d 20 |sion  al|gorithm |
|00003210| 69 6e 0a 65 78 65 63 75 | 74 69 6f 6e 2e 20 54 68 |in.execu|tion. Th|
|00003220| 65 20 68 6f 72 69 7a 6f | 6e 74 61 6c 20 20 62 61 |e horizo|ntal  ba|
|00003230| 72 20 72 65 70 72 65 73 | 65 6e 74 73 20 74 68 65 |r repres|ents the|
|00003240| 20 69 6e 70 75 74 20 20 | 62 6c 6f 63 6b 20 28 69 | input  |block (i|
|00003250| 6e 20 6d 65 6d 6f 72 79 | 29 0a 77 68 69 63 68 20 |n memory|).which |
|00003260| 69 73 20 75 73 65 64 20 | 20 64 69 72 65 63 74 6c |is used | directl|
|00003270| 79 20 61 73 20 61 20 72 | 65 61 64 2d 6f 6e 6c 79 |y as a r|ead-only|
|00003280| 20 64 61 74 61 20 73 74 | 72 75 63 74 75 72 65 2e | data st|ructure.|
|00003290| 20 20 54 68 65 20 68 61 | 73 68 20 74 61 62 6c 65 |  The ha|sh table|
|000032a0| 0a 6d 61 70 73 20 74 68 | 72 65 65 2d 62 79 74 65 |.maps th|ree-byte|
|000032b0| 20 20 6b 65 79 73 20 74 | 6f 20 70 6f 69 6e 74 65 |  keys t|o pointe|
|000032c0| 72 73 20 20 74 68 61 74 | 20 63 61 6e 20 70 6f 69 |rs  that| can poi|
|000032d0| 6e 74 20 61 6e 79 77 68 | 65 72 65 20 20 69 6e 20 |nt anywh|ere  in |
|000032e0| 6d 65 6d 6f 72 79 2c 0a | 62 75 74 20 77 68 69 63 |memory,.|but whic|
|000032f0| 68 20 61 72 65 20 6c 69 | 6b 65 6c 79 20 74 6f 20 |h are li|kely to |
|00003300| 70 6f 69 6e 74 20 74 6f | 20 61 20 72 65 63 65 6e |point to| a recen|
|00003310| 74 20 6f 63 63 75 72 72 | 65 6e 63 65 20 6f 66 20 |t occurr|ence of |
|00003320| 74 68 65 20 6b 65 79 20 | 69 6e 20 74 68 65 0a 69 |the key |in the.i|
|00003330| 6e 70 75 74 20 61 6c 72 | 65 61 64 79 20 20 73 63 |nput alr|eady  sc|
|00003340| 61 6e 6e 65 64 20 28 74 | 68 65 20 68 69 73 74 6f |anned (t|he histo|
|00003350| 72 79 29 2e 20 41 74 20 | 20 65 61 63 68 20 73 74 |ry). At | each st|
|00003360| 65 70 20 74 68 65 20 68 | 61 73 68 20 20 74 61 62 |ep the h|ash  tab|
|00003370| 6c 65 20 69 73 0a 75 73 | 65 64 20 74 6f 20 6d 61 |le is.us|ed to ma|
|00003380| 70 20 74 68 65 20 66 69 | 72 73 74 20 74 68 72 65 |p the fi|rst thre|
|00003390| 65 20 62 79 74 65 73 20 | 20 6f 66 20 74 68 65 20 |e bytes | of the |
|000033a0| 5a 69 76 20 28 64 65 66 | 69 6e 65 64 20 74 6f 20 |Ziv (def|ined to |
|000033b0| 62 65 20 74 68 65 20 66 | 69 72 73 74 0a 73 69 78 |be the f|irst.six|
|000033c0| 74 65 65 6e 20 62 79 74 | 65 73 20 6f 66 20 74 68 |teen byt|es of th|
|000033d0| 65 20 72 65 6d 61 69 6e | 69 6e 67 20 70 61 72 74 |e remain|ing part|
|000033e0| 20 20 6f 66 20 6d 65 73 | 73 61 67 65 29 20 74 6f |  of mes|sage) to|
|000033f0| 20 73 75 63 68 20 61 20 | 70 6f 69 6e 74 65 72 2e | such a |pointer.|
|00003400| 20 54 6f 0a 6b 65 65 70 | 20 74 68 65 20 68 61 73 | To.keep| the has|
|00003410| 68 20 20 74 61 62 6c 65 | 20 75 70 20 74 6f 20 64 |h  table| up to d|
|00003420| 61 74 65 2c 20 20 74 68 | 65 20 68 61 73 68 20 74 |ate,  th|e hash t|
|00003430| 61 62 6c 65 20 65 6e 74 | 72 79 20 20 66 72 6f 6d |able ent|ry  from|
|00003440| 20 77 68 69 63 68 20 74 | 68 65 0a 70 6f 69 6e 74 | which t|he.point|
|00003450| 65 72 20 77 61 73 20 6a | 75 73 74 20 66 65 74 63 |er was j|ust fetc|
|00003460| 68 65 64 20 20 69 73 20 | 72 65 70 6c 61 63 65 64 |hed  is |replaced|
|00003470| 20 62 79 20 61 20 70 6f | 69 6e 74 65 72 20 74 6f | by a po|inter to|
|00003480| 20 20 74 68 65 20 5a 69 | 76 2e 20 49 66 20 74 68 |  the Zi|v. If th|
|00003490| 65 0a 70 6f 69 6e 74 65 | 72 20 66 65 74 63 68 65 |e.pointe|r fetche|
|000034a0| 64 20 20 70 6f 69 6e 74 | 73 20 74 6f 20 6f 6e 65 |d  point|s to one|
|000034b0| 20 20 6f 66 20 74 68 65 | 20 6d 6f 73 74 20 20 72 |  of the| most  r|
|000034c0| 65 63 65 6e 74 20 34 30 | 39 35 20 62 79 74 65 73 |ecent 40|95 bytes|
|000034d0| 20 20 6f 66 20 74 68 65 | 0a 68 69 73 74 6f 72 79 |  of the|.history|
|000034e0| 20 28 74 68 65 20 4c 65 | 6d 70 65 6c 29 20 20 61 | (the Le|mpel)  a|
|000034f0| 6e 64 20 70 6f 69 6e 74 | 73 20 74 6f 20 61 20 20 |nd point|s to a  |
|00003500| 6d 61 74 63 68 20 77 69 | 74 68 20 74 68 65 20 5a |match wi|th the Z|
|00003510| 69 76 20 20 6f 66 20 61 | 74 20 6c 65 61 73 74 0a |iv  of a|t least.|
|00003520| 74 68 72 65 65 20 20 62 | 79 74 65 73 2c 20 20 61 |three  b|ytes,  a|
|00003530| 20 20 63 6f 70 79 20 20 | 69 74 65 6d 20 69 73 20 |  copy  |item is |
|00003540| 20 63 6f 6e 73 74 72 75 | 63 74 65 64 20 20 72 65 | constru|cted  re|
|00003550| 70 72 65 73 65 6e 74 69 | 6e 67 20 20 74 68 65 20 |presenti|ng  the |
|00003560| 20 62 79 74 65 73 0a 6d | 61 74 63 68 65 64 2c 20 | bytes.m|atched, |
|00003570| 20 6f 74 68 65 72 77 69 | 73 65 20 61 20 20 6c 69 | otherwi|se a  li|
|00003580| 74 65 72 61 6c 20 20 69 | 74 65 6d 20 69 73 20 20 |teral  i|tem is  |
|00003590| 63 6f 6e 73 74 72 75 63 | 74 65 64 20 72 65 70 72 |construc|ted repr|
|000035a0| 65 73 65 6e 74 69 6e 67 | 20 20 74 68 65 0a 66 69 |esenting|  the.fi|
|000035b0| 72 73 74 20 62 79 74 65 | 20 69 6e 20 74 68 65 20 |rst byte| in the |
|000035c0| 5a 69 76 2e 20 42 65 63 | 61 75 73 65 20 20 74 68 |Ziv. Bec|ause  th|
|000035d0| 65 20 61 6c 67 6f 72 69 | 74 68 6d 20 63 68 65 63 |e algori|thm chec|
|000035e0| 6b 73 20 74 68 65 20 70 | 6f 69 6e 74 65 72 73 20 |ks the p|ointers |
|000035f0| 74 68 61 74 0a 69 74 20 | 20 6f 62 74 61 69 6e 73 |that.it | obtains|
|00003600| 20 20 66 72 6f 6d 20 20 | 74 68 65 20 20 68 61 73 |  from  |the  has|
|00003610| 68 20 20 74 61 62 6c 65 | 2c 20 20 20 74 68 65 20 |h  table|,   the |
|00003620| 20 68 61 73 68 20 20 74 | 61 62 6c 65 20 20 6e 65 | hash  t|able  ne|
|00003630| 65 64 20 20 6e 6f 74 20 | 20 62 65 0a 69 6e 69 74 |ed  not | be.init|
|00003640| 69 61 6c 69 7a 65 64 2e | 0a 25 0a 7d 20 5c 65 6e |ialized.|.%.} \en|
|00003650| 64 7b 66 69 67 75 72 65 | 7d 0a 0a 5c 62 65 67 69 |d{figure|}..\begi|
|00003660| 6e 7b 66 69 67 75 72 65 | 7d 0a 5c 73 74 61 72 74 |n{figure|}.\start|
|00003670| 73 6d 61 6c 6c 0a 5c 62 | 65 67 69 6e 7b 76 65 72 |small.\b|egin{ver|
|00003680| 62 61 74 69 6d 7d 0a 76 | 6f 69 64 20 6c 7a 72 77 |batim}.v|oid lzrw|
|00003690| 31 5f 63 6f 6d 70 72 65 | 73 73 28 70 5f 73 72 63 |1_compre|ss(p_src|
|000036a0| 5f 66 69 72 73 74 2c 73 | 72 63 5f 6c 65 6e 2c 70 |_first,s|rc_len,p|
|000036b0| 5f 64 73 74 5f 66 69 72 | 73 74 2c 70 5f 64 73 74 |_dst_fir|st,p_dst|
|000036c0| 5f 6c 65 6e 29 0a 2f 2a | 20 49 6e 70 75 74 20 20 |_len)./*| Input  |
|000036d0| 3a 20 53 70 65 63 69 66 | 79 20 69 6e 70 75 74 20 |: Specif|y input |
|000036e0| 62 6c 6f 63 6b 20 75 73 | 69 6e 67 20 70 5f 73 72 |block us|ing p_sr|
|000036f0| 63 5f 66 69 72 73 74 20 | 61 6e 64 20 73 72 63 5f |c_first |and src_|
|00003700| 6c 65 6e 2e 20 20 20 20 | 20 20 20 20 20 20 2a 2f |len.    |      */|
|00003710| 0a 2f 2a 20 49 6e 70 75 | 74 20 20 3a 20 50 6f 69 |./* Inpu|t  : Poi|
|00003720| 6e 74 20 70 5f 64 73 74 | 5f 66 69 72 73 74 20 74 |nt p_dst|_first t|
|00003730| 6f 20 74 68 65 20 73 74 | 61 72 74 20 6f 66 20 74 |o the st|art of t|
|00003740| 68 65 20 6f 75 74 70 75 | 74 20 7a 6f 6e 65 20 28 |he outpu|t zone (|
|00003750| 4f 5a 29 2e 20 20 20 20 | 20 2a 2f 0a 2f 2a 20 49 |OZ).    | */./* I|
|00003760| 6e 70 75 74 20 20 3a 20 | 50 6f 69 6e 74 20 70 5f |nput  : |Point p_|
|00003770| 64 73 74 5f 6c 65 6e 20 | 74 6f 20 61 20 55 4c 4f |dst_len |to a ULO|
|00003780| 4e 47 20 74 6f 20 72 65 | 63 65 69 76 65 20 74 68 |NG to re|ceive th|
|00003790| 65 20 6f 75 74 70 75 74 | 20 6c 65 6e 67 74 68 2e |e output| length.|
|000037a0| 20 20 20 20 2a 2f 0a 2f | 2a 20 49 6e 70 75 74 20 |    */./|* Input |
|000037b0| 20 3a 20 49 6e 70 75 74 | 20 62 6c 6f 63 6b 20 61 | : Input| block a|
|000037c0| 6e 64 20 6f 75 74 70 75 | 74 20 7a 6f 6e 65 20 6d |nd outpu|t zone m|
|000037d0| 75 73 74 20 6e 6f 74 20 | 6f 76 65 72 6c 61 70 2e |ust not |overlap.|
|000037e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2a |        |       *|
|000037f0| 2f 0a 2f 2a 20 4f 75 74 | 70 75 74 20 3a 20 4c 65 |/./* Out|put : Le|
|00003800| 6e 67 74 68 20 6f 66 20 | 6f 75 74 70 75 74 20 62 |ngth of |output b|
|00003810| 6c 6f 63 6b 20 77 72 69 | 74 74 65 6e 20 74 6f 20 |lock wri|tten to |
|00003820| 2a 70 5f 64 73 74 5f 6c | 65 6e 2e 20 20 20 20 20 |*p_dst_l|en.     |
|00003830| 20 20 20 20 20 20 20 20 | 20 20 2a 2f 0a 2f 2a 20 |        |  */./* |
|00003840| 4f 75 74 70 75 74 20 3a | 20 4f 75 74 70 75 74 20 |Output :| Output |
|00003850| 62 6c 6f 63 6b 20 69 6e | 20 4d 65 6d 5b 70 5f 64 |block in| Mem[p_d|
|00003860| 73 74 5f 66 69 72 73 74 | 2e 2e 70 5f 64 73 74 5f |st_first|..p_dst_|
|00003870| 66 69 72 73 74 2b 2a 70 | 5f 64 73 74 5f 6c 65 6e |first+*p|_dst_len|
|00003880| 2d 31 5d 2e 20 2a 2f 0a | 2f 2a 20 4f 75 74 70 75 |-1]. */.|/* Outpu|
|00003890| 74 20 3a 20 4d 61 79 20 | 77 72 69 74 65 20 69 6e |t : May |write in|
|000038a0| 20 4f 5a 3d 4d 65 6d 5b | 70 5f 64 73 74 5f 66 69 | OZ=Mem[|p_dst_fi|
|000038b0| 72 73 74 2e 2e 70 5f 64 | 73 74 5f 66 69 72 73 74 |rst..p_d|st_first|
|000038c0| 2b 73 72 63 5f 6c 65 6e | 2b 32 35 36 2d 31 5d 2e |+src_len|+256-1].|
|000038d0| 2a 2f 0a 2f 2a 20 4f 75 | 74 70 75 74 20 3a 20 55 |*/./* Ou|tput : U|
|000038e0| 70 6f 6e 20 63 6f 6d 70 | 6c 65 74 69 6f 6e 20 67 |pon comp|letion g|
|000038f0| 75 61 72 61 6e 74 65 65 | 64 20 2a 70 5f 64 73 74 |uarantee|d *p_dst|
|00003900| 5f 6c 65 6e 3c 3d 73 72 | 63 5f 6c 65 6e 2b 46 4c |_len<=sr|c_len+FL|
|00003910| 41 47 5f 42 59 54 45 53 | 2e 20 20 2a 2f 0a 55 42 |AG_BYTES|.  */.UB|
|00003920| 59 54 45 20 2a 70 5f 73 | 72 63 5f 66 69 72 73 74 |YTE *p_s|rc_first|
|00003930| 2c 2a 70 5f 64 73 74 5f | 66 69 72 73 74 3b 20 55 |,*p_dst_|first; U|
|00003940| 4c 4f 4e 47 20 73 72 63 | 5f 6c 65 6e 2c 2a 70 5f |LONG src|_len,*p_|
|00003950| 64 73 74 5f 6c 65 6e 3b | 0a 23 64 65 66 69 6e 65 |dst_len;|.#define|
|00003960| 20 50 53 20 2a 70 2b 2b | 21 3d 2a 73 2b 2b 20 20 | PS *p++|!=*s++  |
|00003970| 2f 2a 20 42 6f 64 79 20 | 6f 66 20 69 6e 6e 65 72 |/* Body |of inner|
|00003980| 20 75 6e 72 6f 6c 6c 65 | 64 20 6d 61 74 63 68 69 | unrolle|d matchi|
|00003990| 6e 67 20 6c 6f 6f 70 2e | 20 20 20 20 20 20 20 20 |ng loop.|        |
|000039a0| 20 2a 2f 0a 23 64 65 66 | 69 6e 65 20 49 54 45 4d | */.#def|ine ITEM|
|000039b0| 4d 41 58 20 31 36 20 20 | 20 20 20 2f 2a 20 4d 61 |MAX 16  |   /* Ma|
|000039c0| 78 69 6d 75 6d 20 6e 75 | 6d 62 65 72 20 6f 66 20 |ximum nu|mber of |
|000039d0| 62 79 74 65 73 20 69 6e | 20 61 6e 20 65 78 70 61 |bytes in| an expa|
|000039e0| 6e 64 65 64 20 69 74 65 | 6d 2e 20 20 2a 2f 0a 7b |nded ite|m.  */.{|
|000039f0| 55 42 59 54 45 20 2a 70 | 5f 73 72 63 3d 70 5f 73 |UBYTE *p|_src=p_s|
|00003a00| 72 63 5f 66 69 72 73 74 | 2c 2a 70 5f 64 73 74 3d |rc_first|,*p_dst=|
|00003a10| 70 5f 64 73 74 5f 66 69 | 72 73 74 3b 0a 20 55 42 |p_dst_fi|rst;. UB|
|00003a20| 59 54 45 20 2a 70 5f 73 | 72 63 5f 70 6f 73 74 3d |YTE *p_s|rc_post=|
|00003a30| 70 5f 73 72 63 5f 66 69 | 72 73 74 2b 73 72 63 5f |p_src_fi|rst+src_|
|00003a40| 6c 65 6e 2c 2a 70 5f 64 | 73 74 5f 70 6f 73 74 3d |len,*p_d|st_post=|
|00003a50| 70 5f 64 73 74 5f 66 69 | 72 73 74 2b 73 72 63 5f |p_dst_fi|rst+src_|
|00003a60| 6c 65 6e 3b 0a 20 55 42 | 59 54 45 20 2a 70 5f 73 |len;. UB|YTE *p_s|
|00003a70| 72 63 5f 6d 61 78 31 3d | 70 5f 73 72 63 5f 70 6f |rc_max1=|p_src_po|
|00003a80| 73 74 2d 49 54 45 4d 4d | 41 58 2c 2a 70 5f 73 72 |st-ITEMM|AX,*p_sr|
|00003a90| 63 5f 6d 61 78 31 36 3d | 70 5f 73 72 63 5f 70 6f |c_max16=|p_src_po|
|00003aa0| 73 74 2d 31 36 2a 49 54 | 45 4d 4d 41 58 3b 0a 20 |st-16*IT|EMMAX;. |
|00003ab0| 55 42 59 54 45 20 2a 68 | 61 73 68 5b 34 30 39 36 |UBYTE *h|ash[4096|
|00003ac0| 5d 2c 2a 70 5f 63 6f 6e | 74 72 6f 6c 3b 20 55 57 |],*p_con|trol; UW|
|00003ad0| 4f 52 44 20 63 6f 6e 74 | 72 6f 6c 3d 30 2c 63 6f |ORD cont|rol=0,co|
|00003ae0| 6e 74 72 6f 6c 5f 62 69 | 74 73 3d 30 3b 0a 20 2a |ntrol_bi|ts=0;. *|
|00003af0| 70 5f 64 73 74 3d 46 4c | 41 47 5f 43 4f 4d 50 52 |p_dst=FL|AG_COMPR|
|00003b00| 45 53 53 3b 20 70 5f 64 | 73 74 2b 3d 46 4c 41 47 |ESS; p_d|st+=FLAG|
|00003b10| 5f 42 59 54 45 53 3b 20 | 70 5f 63 6f 6e 74 72 6f |_BYTES; |p_contro|
|00003b20| 6c 3d 70 5f 64 73 74 3b | 20 70 5f 64 73 74 2b 3d |l=p_dst;| p_dst+=|
|00003b30| 32 3b 0a 20 77 68 69 6c | 65 20 28 54 52 55 45 29 |2;. whil|e (TRUE)|
|00003b40| 0a 20 20 20 7b 55 42 59 | 54 45 20 2a 70 2c 2a 73 |.   {UBY|TE *p,*s|
|00003b50| 3b 20 55 57 4f 52 44 20 | 75 6e 72 6f 6c 6c 3d 31 |; UWORD |unroll=1|
|00003b60| 36 2c 6c 65 6e 2c 69 6e | 64 65 78 3b 20 55 4c 4f |6,len,in|dex; ULO|
|00003b70| 4e 47 20 6f 66 66 73 65 | 74 3b 0a 20 20 20 20 69 |NG offse|t;.    i|
|00003b80| 66 20 28 70 5f 64 73 74 | 3e 70 5f 64 73 74 5f 70 |f (p_dst|>p_dst_p|
|00003b90| 6f 73 74 29 20 67 6f 74 | 6f 20 6f 76 65 72 72 75 |ost) got|o overru|
|00003ba0| 6e 3b 0a 20 20 20 20 69 | 66 20 28 70 5f 73 72 63 |n;.    i|f (p_src|
|00003bb0| 3e 70 5f 73 72 63 5f 6d | 61 78 31 36 29 0a 20 20 |>p_src_m|ax16).  |
|00003bc0| 20 20 20 20 7b 75 6e 72 | 6f 6c 6c 3d 31 3b 0a 20 |    {unr|oll=1;. |
|00003bd0| 20 20 20 20 20 20 69 66 | 20 28 70 5f 73 72 63 3e |      if| (p_src>|
|00003be0| 70 5f 73 72 63 5f 6d 61 | 78 31 29 0a 20 20 20 20 |p_src_ma|x1).    |
|00003bf0| 20 20 20 20 20 7b 69 66 | 20 28 70 5f 73 72 63 3d |     {if| (p_src=|
|00003c00| 3d 70 5f 73 72 63 5f 70 | 6f 73 74 29 20 62 72 65 |=p_src_p|ost) bre|
|00003c10| 61 6b 3b 20 67 6f 74 6f | 20 6c 69 74 65 72 61 6c |ak; goto| literal|
|00003c20| 3b 7d 7d 0a 20 20 20 20 | 62 65 67 69 6e 5f 75 6e |;}}.    |begin_un|
|00003c30| 72 6f 6c 6c 65 64 5f 6c | 6f 6f 70 3a 0a 20 20 20 |rolled_l|oop:.   |
|00003c40| 20 20 20 20 69 6e 64 65 | 78 3d 28 28 34 30 35 34 |    inde|x=((4054|
|00003c50| 33 2a 28 28 28 28 70 5f | 73 72 63 5b 30 5d 3c 3c |3*((((p_|src[0]<<|
|00003c60| 34 29 5e 70 5f 73 72 63 | 5b 31 5d 29 3c 3c 34 29 |4)^p_src|[1])<<4)|
|00003c70| 5e 70 5f 73 72 63 5b 32 | 5d 29 29 3e 3e 34 29 20 |^p_src[2|]))>>4) |
|00003c80| 26 20 30 78 46 46 46 3b | 0a 20 20 20 20 20 20 20 |& 0xFFF;|.       |
|00003c90| 70 3d 68 61 73 68 5b 69 | 6e 64 65 78 5d 3b 20 68 |p=hash[i|ndex]; h|
|00003ca0| 61 73 68 5b 69 6e 64 65 | 78 5d 3d 73 3d 70 5f 73 |ash[inde|x]=s=p_s|
|00003cb0| 72 63 3b 20 6f 66 66 73 | 65 74 3d 73 2d 70 3b 0a |rc; offs|et=s-p;.|
|00003cc0| 20 20 20 20 20 20 20 69 | 66 20 28 6f 66 66 73 65 |       i|f (offse|
|00003cd0| 74 3e 34 30 39 35 20 7c | 7c 20 70 3c 70 5f 73 72 |t>4095 ||| p<p_sr|
|00003ce0| 63 5f 66 69 72 73 74 20 | 7c 7c 20 6f 66 66 73 65 |c_first ||| offse|
|00003cf0| 74 3d 3d 30 20 7c 7c 20 | 50 53 20 7c 7c 20 50 53 |t==0 || |PS || PS|
|00003d00| 20 7c 7c 20 50 53 29 0a | 20 20 20 20 20 20 20 20 | || PS).|        |
|00003d10| 20 20 7b 6c 69 74 65 72 | 61 6c 3a 20 2a 70 5f 64 |  {liter|al: *p_d|
|00003d20| 73 74 2b 2b 3d 2a 70 5f | 73 72 63 2b 2b 3b 20 63 |st++=*p_|src++; c|
|00003d30| 6f 6e 74 72 6f 6c 3e 3e | 3d 31 3b 20 63 6f 6e 74 |ontrol>>|=1; cont|
|00003d40| 72 6f 6c 5f 62 69 74 73 | 2b 2b 3b 7d 0a 20 20 20 |rol_bits|++;}.   |
|00003d50| 20 20 20 20 65 6c 73 65 | 0a 20 20 20 20 20 20 20 |    else|.       |
|00003d60| 20 20 7b 50 53 20 7c 7c | 20 50 53 20 7c 7c 20 50 |  {PS ||| PS || P|
|00003d70| 53 20 7c 7c 20 50 53 20 | 7c 7c 20 50 53 20 7c 7c |S || PS ||| PS |||
|00003d80| 20 50 53 20 7c 7c 20 50 | 53 20 7c 7c 0a 20 20 20 | PS || P|S ||.   |
|00003d90| 20 20 20 20 20 20 20 50 | 53 20 7c 7c 20 50 53 20 |       P|S || PS |
|00003da0| 7c 7c 20 50 53 20 7c 7c | 20 50 53 20 7c 7c 20 50 ||| PS ||| PS || P|
|00003db0| 53 20 7c 7c 20 50 53 20 | 7c 7c 20 73 2b 2b 3b 20 |S || PS ||| s++; |
|00003dc0| 6c 65 6e 3d 73 2d 70 5f | 73 72 63 2d 31 3b 0a 20 |len=s-p_|src-1;. |
|00003dd0| 20 20 20 20 20 20 20 20 | 20 2a 70 5f 64 73 74 2b |        | *p_dst+|
|00003de0| 2b 3d 28 28 6f 66 66 73 | 65 74 26 30 78 46 30 30 |+=((offs|et&0xF00|
|00003df0| 29 3e 3e 34 29 2b 28 6c | 65 6e 2d 31 29 3b 20 2a |)>>4)+(l|en-1); *|
|00003e00| 70 5f 64 73 74 2b 2b 3d | 6f 66 66 73 65 74 26 30 |p_dst++=|offset&0|
|00003e10| 78 46 46 3b 0a 20 20 20 | 20 20 20 20 20 20 20 70 |xFF;.   |       p|
|00003e20| 5f 73 72 63 2b 3d 6c 65 | 6e 3b 20 63 6f 6e 74 72 |_src+=le|n; contr|
|00003e30| 6f 6c 3d 28 63 6f 6e 74 | 72 6f 6c 3e 3e 31 29 7c |ol=(cont|rol>>1)||
|00003e40| 30 78 38 30 30 30 3b 20 | 63 6f 6e 74 72 6f 6c 5f |0x8000; |control_|
|00003e50| 62 69 74 73 2b 2b 3b 7d | 0a 20 20 20 20 65 6e 64 |bits++;}|.    end|
|00003e60| 5f 75 6e 72 6f 6c 6c 65 | 64 5f 6c 6f 6f 70 3a 20 |_unrolle|d_loop: |
|00003e70| 69 66 20 28 2d 2d 75 6e | 72 6f 6c 6c 29 20 67 6f |if (--un|roll) go|
|00003e80| 74 6f 20 62 65 67 69 6e | 5f 75 6e 72 6f 6c 6c 65 |to begin|_unrolle|
|00003e90| 64 5f 6c 6f 6f 70 3b 0a | 20 20 20 20 69 66 20 28 |d_loop;.|    if (|
|00003ea0| 63 6f 6e 74 72 6f 6c 5f | 62 69 74 73 3d 3d 31 36 |control_|bits==16|
|00003eb0| 29 0a 20 20 20 20 20 20 | 7b 2a 70 5f 63 6f 6e 74 |).      |{*p_cont|
|00003ec0| 72 6f 6c 3d 63 6f 6e 74 | 72 6f 6c 26 30 78 46 46 |rol=cont|rol&0xFF|
|00003ed0| 3b 20 2a 28 70 5f 63 6f | 6e 74 72 6f 6c 2b 31 29 |; *(p_co|ntrol+1)|
|00003ee0| 3d 63 6f 6e 74 72 6f 6c | 3e 3e 38 3b 0a 20 20 20 |=control|>>8;.   |
|00003ef0| 20 20 20 20 70 5f 63 6f | 6e 74 72 6f 6c 3d 70 5f |    p_co|ntrol=p_|
|00003f00| 64 73 74 3b 20 70 5f 64 | 73 74 2b 3d 32 3b 20 63 |dst; p_d|st+=2; c|
|00003f10| 6f 6e 74 72 6f 6c 3d 63 | 6f 6e 74 72 6f 6c 5f 62 |ontrol=c|ontrol_b|
|00003f20| 69 74 73 3d 30 3b 7d 0a | 20 20 20 7d 0a 20 63 6f |its=0;}.|   }. co|
|00003f30| 6e 74 72 6f 6c 3e 3e 3d | 31 36 2d 63 6f 6e 74 72 |ntrol>>=|16-contr|
|00003f40| 6f 6c 5f 62 69 74 73 3b | 0a 20 2a 70 5f 63 6f 6e |ol_bits;|. *p_con|
|00003f50| 74 72 6f 6c 2b 2b 3d 63 | 6f 6e 74 72 6f 6c 26 30 |trol++=c|ontrol&0|
|00003f60| 78 46 46 3b 20 2a 70 5f | 63 6f 6e 74 72 6f 6c 2b |xFF; *p_|control+|
|00003f70| 2b 3d 63 6f 6e 74 72 6f | 6c 3e 3e 38 3b 0a 20 69 |+=contro|l>>8;. i|
|00003f80| 66 20 28 70 5f 63 6f 6e | 74 72 6f 6c 3d 3d 70 5f |f (p_con|trol==p_|
|00003f90| 64 73 74 29 20 70 5f 64 | 73 74 2d 3d 32 3b 0a 20 |dst) p_d|st-=2;. |
|00003fa0| 2a 70 5f 64 73 74 5f 6c | 65 6e 3d 70 5f 64 73 74 |*p_dst_l|en=p_dst|
|00003fb0| 2d 70 5f 64 73 74 5f 66 | 69 72 73 74 3b 0a 20 72 |-p_dst_f|irst;. r|
|00003fc0| 65 74 75 72 6e 3b 0a 20 | 6f 76 65 72 72 75 6e 3a |eturn;. |overrun:|
|00003fd0| 20 66 61 73 74 5f 63 6f | 70 79 28 70 5f 73 72 63 | fast_co|py(p_src|
|00003fe0| 5f 66 69 72 73 74 2c 70 | 5f 64 73 74 5f 66 69 72 |_first,p|_dst_fir|
|00003ff0| 73 74 2b 46 4c 41 47 5f | 42 59 54 45 53 2c 73 72 |st+FLAG_|BYTES,sr|
|00004000| 63 5f 6c 65 6e 29 3b 0a | 20 20 20 20 20 20 20 20 |c_len);.|        |
|00004010| 20 20 2a 70 5f 64 73 74 | 5f 66 69 72 73 74 3d 46 |  *p_dst|_first=F|
|00004020| 4c 41 47 5f 43 4f 50 59 | 3b 20 2a 70 5f 64 73 74 |LAG_COPY|; *p_dst|
|00004030| 5f 6c 65 6e 3d 73 72 63 | 5f 6c 65 6e 2b 46 4c 41 |_len=src|_len+FLA|
|00004040| 47 5f 42 59 54 45 53 3b | 0a 7d 0a 5c 65 6e 64 7b |G_BYTES;|.}.\end{|
|00004050| 76 65 72 62 61 74 69 6d | 7d 0a 5c 65 6e 64 73 6d |verbatim|}.\endsm|
|00004060| 61 6c 6c 0a 5c 62 69 67 | 63 61 70 74 69 6f 6e 6e |all.\big|captionn|
|00004070| 6f 64 65 73 63 7b 34 7d | 7b 54 68 65 20 4c 5a 52 |odesc{4}|{The LZR|
|00004080| 57 31 20 63 6f 6d 70 72 | 65 73 73 69 6f 6e 20 61 |W1 compr|ession a|
|00004090| 6c 67 6f 72 69 74 68 6d | 2e 7d 0a 5c 65 6e 64 7b |lgorithm|.}.\end{|
|000040a0| 66 69 67 75 72 65 7d 0a | 0a 5c 62 65 67 69 6e 7b |figure}.|.\begin{|
|000040b0| 66 69 67 75 72 65 7d 0a | 5c 73 74 61 72 74 73 6d |figure}.|\startsm|
|000040c0| 61 6c 6c 0a 5c 62 65 67 | 69 6e 7b 76 65 72 62 61 |all.\beg|in{verba|
|000040d0| 74 69 6d 7d 0a 23 64 65 | 66 69 6e 65 20 55 42 59 |tim}.#de|fine UBY|
|000040e0| 54 45 20 75 6e 73 69 67 | 6e 65 64 20 63 68 61 72 |TE unsig|ned char|
|000040f0| 20 2f 2a 20 55 6e 73 69 | 67 6e 65 64 20 20 20 20 | /* Unsi|gned    |
|00004100| 20 62 79 74 65 20 28 31 | 20 62 79 74 65 20 29 20 | byte (1| byte ) |
|00004110| 20 20 20 20 20 20 20 2a | 2f 0a 23 64 65 66 69 6e |       *|/.#defin|
|00004120| 65 20 55 57 4f 52 44 20 | 75 6e 73 69 67 6e 65 64 |e UWORD |unsigned|
|00004130| 20 69 6e 74 20 20 2f 2a | 20 55 6e 73 69 67 6e 65 | int  /*| Unsigne|
|00004140| 64 20 20 20 20 20 77 6f | 72 64 20 28 32 20 62 79 |d     wo|rd (2 by|
|00004150| 74 65 73 29 20 20 20 20 | 20 20 20 20 2a 2f 0a 23 |tes)    |    */.#|
|00004160| 64 65 66 69 6e 65 20 55 | 4c 4f 4e 47 20 75 6e 73 |define U|LONG uns|
|00004170| 69 67 6e 65 64 20 6c 6f | 6e 67 20 2f 2a 20 55 6e |igned lo|ng /* Un|
|00004180| 73 69 67 6e 65 64 20 6c | 6f 6e 67 77 6f 72 64 20 |signed l|ongword |
|00004190| 28 34 20 62 79 74 65 73 | 29 20 20 20 20 20 20 20 |(4 bytes|)       |
|000041a0| 20 2a 2f 0a 23 64 65 66 | 69 6e 65 20 46 4c 41 47 | */.#def|ine FLAG|
|000041b0| 5f 42 59 54 45 53 20 20 | 20 20 34 20 20 20 20 20 |_BYTES  |  4     |
|000041c0| 2f 2a 20 4e 75 6d 62 65 | 72 20 6f 66 20 62 79 74 |/* Numbe|r of byt|
|000041d0| 65 73 20 75 73 65 64 20 | 62 79 20 63 6f 70 79 20 |es used |by copy |
|000041e0| 66 6c 61 67 2e 20 2a 2f | 0a 23 64 65 66 69 6e 65 |flag. */|.#define|
|000041f0| 20 46 4c 41 47 5f 43 4f | 4d 50 52 45 53 53 20 30 | FLAG_CO|MPRESS 0|
|00004200| 20 20 20 20 20 2f 2a 20 | 53 69 67 6e 61 6c 73 20 |     /* |Signals |
|00004210| 74 68 61 74 20 63 6f 6d | 70 72 65 73 73 69 6f 6e |that com|pression|
|00004220| 20 6f 63 63 75 72 72 65 | 64 2e 20 2a 2f 0a 23 64 | occurre|d. */.#d|
|00004230| 65 66 69 6e 65 20 46 4c | 41 47 5f 43 4f 50 59 20 |efine FL|AG_COPY |
|00004240| 20 20 20 20 31 20 20 20 | 20 20 2f 2a 20 53 69 67 |    1   |  /* Sig|
|00004250| 6e 61 6c 73 20 74 68 61 | 74 20 61 20 63 6f 70 79 |nals tha|t a copy|
|00004260| 6f 76 65 72 20 20 6f 63 | 63 75 72 72 65 64 2e 20 |over  oc|curred. |
|00004270| 2a 2f 0a 76 6f 69 64 20 | 66 61 73 74 5f 63 6f 70 |*/.void |fast_cop|
|00004280| 79 28 70 5f 73 72 63 2c | 70 5f 64 73 74 2c 6c 65 |y(p_src,|p_dst,le|
|00004290| 6e 29 20 2f 2a 20 46 61 | 73 74 20 63 6f 70 79 20 |n) /* Fa|st copy |
|000042a0| 72 6f 75 74 69 6e 65 2e | 20 20 20 20 20 20 20 20 |routine.|        |
|000042b0| 20 20 20 20 20 2a 2f 0a | 55 42 59 54 45 20 2a 70 |     */.|UBYTE *p|
|000042c0| 5f 73 72 63 2c 2a 70 5f | 64 73 74 3b 20 7b 77 68 |_src,*p_|dst; {wh|
|000042d0| 69 6c 65 20 28 6c 65 6e | 2d 2d 29 20 2a 70 5f 64 |ile (len|--) *p_d|
|000042e0| 73 74 2b 2b 3d 2a 70 5f | 73 72 63 2b 2b 3b 7d 0a |st++=*p_|src++;}.|
|000042f0| 5c 65 6e 64 7b 76 65 72 | 62 61 74 69 6d 7d 0a 5c |\end{ver|batim}.\|
|00004300| 65 6e 64 73 6d 61 6c 6c | 0a 5c 62 69 67 63 61 70 |endsmall|.\bigcap|
|00004310| 74 69 6f 6e 6e 6f 64 65 | 73 63 7b 35 7d 7b 44 65 |tionnode|sc{5}{De|
|00004320| 66 69 6e 69 74 69 6f 6e | 73 20 75 73 65 64 20 62 |finition|s used b|
|00004330| 79 20 4c 5a 52 57 31 20 | 63 6f 64 65 2e 7d 0a 5c |y LZRW1 |code.}.\|
|00004340| 65 6e 64 7b 66 69 67 75 | 72 65 7d 0a 0a 5c 62 65 |end{figu|re}..\be|
|00004350| 67 69 6e 7b 66 69 67 75 | 72 65 7d 0a 5c 73 74 61 |gin{figu|re}.\sta|
|00004360| 72 74 73 6d 61 6c 6c 0a | 5c 62 65 67 69 6e 7b 76 |rtsmall.|\begin{v|
|00004370| 65 72 62 61 74 69 6d 7d | 0a 76 6f 69 64 20 6c 7a |erbatim}|.void lz|
|00004380| 72 77 31 5f 64 65 63 6f | 6d 70 72 65 73 73 28 70 |rw1_deco|mpress(p|
|00004390| 5f 73 72 63 5f 66 69 72 | 73 74 2c 73 72 63 5f 6c |_src_fir|st,src_l|
|000043a0| 65 6e 2c 70 5f 64 73 74 | 5f 66 69 72 73 74 2c 70 |en,p_dst|_first,p|
|000043b0| 5f 64 73 74 5f 6c 65 6e | 29 0a 2f 2a 20 49 6e 70 |_dst_len|)./* Inp|
|000043c0| 75 74 20 20 3a 20 53 70 | 65 63 69 66 79 20 69 6e |ut  : Sp|ecify in|
|000043d0| 70 75 74 20 62 6c 6f 63 | 6b 20 75 73 69 6e 67 20 |put bloc|k using |
|000043e0| 70 5f 73 72 63 5f 66 69 | 72 73 74 20 61 6e 64 20 |p_src_fi|rst and |
|000043f0| 73 72 63 5f 6c 65 6e 2e | 20 20 20 20 20 20 20 20 |src_len.|        |
|00004400| 20 20 2a 2f 0a 2f 2a 20 | 49 6e 70 75 74 20 20 3a |  */./* |Input  :|
|00004410| 20 50 6f 69 6e 74 20 70 | 5f 64 73 74 5f 66 69 72 | Point p|_dst_fir|
|00004420| 73 74 20 74 6f 20 74 68 | 65 20 73 74 61 72 74 20 |st to th|e start |
|00004430| 6f 66 20 74 68 65 20 6f | 75 74 70 75 74 20 7a 6f |of the o|utput zo|
|00004440| 6e 65 2e 20 20 20 20 20 | 20 20 20 20 20 2a 2f 0a |ne.     |     */.|
|00004450| 2f 2a 20 49 6e 70 75 74 | 20 20 3a 20 50 6f 69 6e |/* Input|  : Poin|
|00004460| 74 20 70 5f 64 73 74 5f | 6c 65 6e 20 74 6f 20 61 |t p_dst_|len to a|
|00004470| 20 55 4c 4f 4e 47 20 74 | 6f 20 72 65 63 65 69 76 | ULONG t|o receiv|
|00004480| 65 20 74 68 65 20 6f 75 | 74 70 75 74 20 6c 65 6e |e the ou|tput len|
|00004490| 67 74 68 2e 20 20 20 20 | 2a 2f 0a 2f 2a 20 49 6e |gth.    |*/./* In|
|000044a0| 70 75 74 20 20 3a 20 49 | 6e 70 75 74 20 62 6c 6f |put  : I|nput blo|
|000044b0| 63 6b 20 61 6e 64 20 6f | 75 74 70 75 74 20 7a 6f |ck and o|utput zo|
|000044c0| 6e 65 20 6d 75 73 74 20 | 6e 6f 74 20 6f 76 65 72 |ne must |not over|
|000044d0| 6c 61 70 2e 20 55 73 65 | 72 20 6b 6e 6f 77 73 20 |lap. Use|r knows |
|000044e0| 20 20 20 2a 2f 0a 2f 2a | 20 49 6e 70 75 74 20 20 |   */./*| Input  |
|000044f0| 3a 20 75 70 70 65 72 62 | 6f 75 6e 64 20 6f 6e 20 |: upperb|ound on |
|00004500| 6f 75 74 70 75 74 20 62 | 6c 6f 63 6b 20 6c 65 6e |output b|lock len|
|00004510| 67 74 68 20 66 72 6f 6d | 20 65 61 72 6c 69 65 72 |gth from| earlier|
|00004520| 20 63 6f 6d 70 72 65 73 | 73 69 6f 6e 2e 20 2a 2f | compres|sion. */|
|00004530| 0a 2f 2a 20 49 6e 70 75 | 74 20 20 3a 20 49 6e 20 |./* Inpu|t  : In |
|00004540| 61 6e 79 20 63 61 73 65 | 2c 20 6d 61 78 69 6d 75 |any case|, maximu|
|00004550| 6d 20 65 78 70 61 6e 73 | 69 6f 6e 20 70 6f 73 73 |m expans|ion poss|
|00004560| 69 62 6c 65 20 69 73 20 | 65 69 67 68 74 20 74 69 |ible is |eight ti|
|00004570| 6d 65 73 2e 20 20 20 20 | 20 2a 2f 0a 2f 2a 20 4f |mes.    | */./* O|
|00004580| 75 74 70 75 74 20 3a 20 | 4c 65 6e 67 74 68 20 6f |utput : |Length o|
|00004590| 66 20 6f 75 74 70 75 74 | 20 62 6c 6f 63 6b 20 77 |f output| block w|
|000045a0| 72 69 74 74 65 6e 20 74 | 6f 20 2a 70 5f 64 73 74 |ritten t|o *p_dst|
|000045b0| 5f 6c 65 6e 2e 20 20 20 | 20 20 20 20 20 20 20 20 |_len.   |        |
|000045c0| 20 20 20 20 2a 2f 0a 2f | 2a 20 4f 75 74 70 75 74 |    */./|* Output|
|000045d0| 20 3a 20 4f 75 74 70 75 | 74 20 62 6c 6f 63 6b 20 | : Outpu|t block |
|000045e0| 69 6e 20 4d 65 6d 5b 70 | 5f 64 73 74 5f 66 69 72 |in Mem[p|_dst_fir|
|000045f0| 73 74 2e 2e 70 5f 64 73 | 74 5f 66 69 72 73 74 2b |st..p_ds|t_first+|
|00004600| 2a 70 5f 64 73 74 5f 6c | 65 6e 2d 31 5d 2e 20 2a |*p_dst_l|en-1]. *|
|00004610| 2f 0a 2f 2a 20 4f 75 74 | 70 75 74 20 3a 20 57 72 |/./* Out|put : Wr|
|00004620| 69 74 65 73 20 6f 6e 6c | 79 20 20 69 6e 20 4d 65 |ites onl|y  in Me|
|00004630| 6d 5b 70 5f 64 73 74 5f | 66 69 72 73 74 2e 2e 70 |m[p_dst_|first..p|
|00004640| 5f 64 73 74 5f 66 69 72 | 73 74 2b 2a 70 5f 64 73 |_dst_fir|st+*p_ds|
|00004650| 74 5f 6c 65 6e 2d 31 5d | 2e 20 2a 2f 0a 55 42 59 |t_len-1]|. */.UBY|
|00004660| 54 45 20 2a 70 5f 73 72 | 63 5f 66 69 72 73 74 2c |TE *p_sr|c_first,|
|00004670| 20 2a 70 5f 64 73 74 5f | 66 69 72 73 74 3b 20 55 | *p_dst_|first; U|
|00004680| 4c 4f 4e 47 20 73 72 63 | 5f 6c 65 6e 2c 20 2a 70 |LONG src|_len, *p|
|00004690| 5f 64 73 74 5f 6c 65 6e | 3b 0a 7b 55 57 4f 52 44 |_dst_len|;.{UWORD|
|000046a0| 20 63 6f 6e 74 72 6f 6c | 62 69 74 73 3d 30 2c 20 | control|bits=0, |
|000046b0| 63 6f 6e 74 72 6f 6c 3b | 0a 20 55 42 59 54 45 20 |control;|. UBYTE |
|000046c0| 2a 70 5f 73 72 63 3d 70 | 5f 73 72 63 5f 66 69 72 |*p_src=p|_src_fir|
|000046d0| 73 74 2b 46 4c 41 47 5f | 42 59 54 45 53 2c 20 2a |st+FLAG_|BYTES, *|
|000046e0| 70 5f 64 73 74 3d 70 5f | 64 73 74 5f 66 69 72 73 |p_dst=p_|dst_firs|
|000046f0| 74 2c 0a 20 20 20 20 20 | 20 20 2a 70 5f 73 72 63 |t,.     |  *p_src|
|00004700| 5f 70 6f 73 74 3d 70 5f | 73 72 63 5f 66 69 72 73 |_post=p_|src_firs|
|00004710| 74 2b 73 72 63 5f 6c 65 | 6e 3b 0a 20 69 66 20 28 |t+src_le|n;. if (|
|00004720| 2a 70 5f 73 72 63 5f 66 | 69 72 73 74 3d 3d 46 4c |*p_src_f|irst==FL|
|00004730| 41 47 5f 43 4f 50 59 29 | 0a 20 20 20 7b 66 61 73 |AG_COPY)|.   {fas|
|00004740| 74 5f 63 6f 70 79 28 70 | 5f 73 72 63 5f 66 69 72 |t_copy(p|_src_fir|
|00004750| 73 74 2b 46 4c 41 47 5f | 42 59 54 45 53 2c 70 5f |st+FLAG_|BYTES,p_|
|00004760| 64 73 74 5f 66 69 72 73 | 74 2c 73 72 63 5f 6c 65 |dst_firs|t,src_le|
|00004770| 6e 2d 46 4c 41 47 5f 42 | 59 54 45 53 29 3b 0a 20 |n-FLAG_B|YTES);. |
|00004780| 20 20 20 2a 70 5f 64 73 | 74 5f 6c 65 6e 3d 73 72 |   *p_ds|t_len=sr|
|00004790| 63 5f 6c 65 6e 2d 46 4c | 41 47 5f 42 59 54 45 53 |c_len-FL|AG_BYTES|
|000047a0| 3b 20 72 65 74 75 72 6e | 3b 7d 0a 20 77 68 69 6c |; return|;}. whil|
|000047b0| 65 20 28 70 5f 73 72 63 | 21 3d 70 5f 73 72 63 5f |e (p_src|!=p_src_|
|000047c0| 70 6f 73 74 29 0a 20 20 | 20 7b 69 66 20 28 63 6f |post).  | {if (co|
|000047d0| 6e 74 72 6f 6c 62 69 74 | 73 3d 3d 30 29 0a 20 20 |ntrolbit|s==0).  |
|000047e0| 20 20 20 20 7b 63 6f 6e | 74 72 6f 6c 3d 2a 70 5f |    {con|trol=*p_|
|000047f0| 73 72 63 2b 2b 3b 20 63 | 6f 6e 74 72 6f 6c 7c 3d |src++; c|ontrol|=|
|00004800| 28 2a 70 5f 73 72 63 2b | 2b 29 3c 3c 38 3b 20 63 |(*p_src+|+)<<8; c|
|00004810| 6f 6e 74 72 6f 6c 62 69 | 74 73 3d 31 36 3b 7d 0a |ontrolbi|ts=16;}.|
|00004820| 20 20 20 20 69 66 20 28 | 63 6f 6e 74 72 6f 6c 26 |    if (|control&|
|00004830| 31 29 0a 20 20 20 20 20 | 20 7b 55 57 4f 52 44 20 |1).     | {UWORD |
|00004840| 6f 66 66 73 65 74 2c 6c | 65 6e 3b 20 55 42 59 54 |offset,l|en; UBYT|
|00004850| 45 20 2a 70 3b 0a 20 20 | 20 20 20 20 20 6f 66 66 |E *p;.  |     off|
|00004860| 73 65 74 3d 28 2a 70 5f | 73 72 63 26 30 78 46 30 |set=(*p_|src&0xF0|
|00004870| 29 3c 3c 34 3b 20 6c 65 | 6e 3d 31 2b 28 2a 70 5f |)<<4; le|n=1+(*p_|
|00004880| 73 72 63 2b 2b 26 30 78 | 46 29 3b 0a 20 20 20 20 |src++&0x|F);.    |
|00004890| 20 20 20 6f 66 66 73 65 | 74 2b 3d 2a 70 5f 73 72 |   offse|t+=*p_sr|
|000048a0| 63 2b 2b 26 30 78 46 46 | 3b 20 70 3d 70 5f 64 73 |c++&0xFF|; p=p_ds|
|000048b0| 74 2d 6f 66 66 73 65 74 | 3b 0a 20 20 20 20 20 20 |t-offset|;.      |
|000048c0| 20 77 68 69 6c 65 20 28 | 6c 65 6e 2d 2d 29 20 2a | while (|len--) *|
|000048d0| 70 5f 64 73 74 2b 2b 3d | 2a 70 2b 2b 3b 7d 0a 20 |p_dst++=|*p++;}. |
|000048e0| 20 20 20 65 6c 73 65 0a | 20 20 20 20 20 20 20 2a |   else.|       *|
|000048f0| 70 5f 64 73 74 2b 2b 3d | 2a 70 5f 73 72 63 2b 2b |p_dst++=|*p_src++|
|00004900| 3b 0a 20 20 20 20 63 6f | 6e 74 72 6f 6c 3e 3e 3d |;.    co|ntrol>>=|
|00004910| 31 3b 20 63 6f 6e 74 72 | 6f 6c 62 69 74 73 2d 2d |1; contr|olbits--|
|00004920| 3b 0a 20 20 20 7d 0a 20 | 2a 70 5f 64 73 74 5f 6c |;.   }. |*p_dst_l|
|00004930| 65 6e 3d 70 5f 64 73 74 | 2d 70 5f 64 73 74 5f 66 |en=p_dst|-p_dst_f|
|00004940| 69 72 73 74 3b 0a 7d 0a | 5c 65 6e 64 7b 76 65 72 |irst;.}.|\end{ver|
|00004950| 62 61 74 69 6d 7d 0a 5c | 65 6e 64 73 6d 61 6c 6c |batim}.\|endsmall|
|00004960| 0a 5c 62 69 67 63 61 70 | 74 69 6f 6e 6e 6f 64 65 |.\bigcap|tionnode|
|00004970| 73 63 7b 36 7d 7b 54 68 | 65 20 4c 5a 52 57 31 20 |sc{6}{Th|e LZRW1 |
|00004980| 64 65 63 6f 6d 70 72 65 | 73 73 69 6f 6e 20 61 6c |decompre|ssion al|
|00004990| 67 6f 72 69 74 68 6d 2e | 7d 0a 5c 65 6e 64 7b 66 |gorithm.|}.\end{f|
|000049a0| 69 67 75 72 65 7d 0a 0a | 0a 5c 62 65 67 69 6e 7b |igure}..|.\begin{|
|000049b0| 66 69 67 75 72 65 7d 0a | 5c 62 65 67 69 6e 7b 63 |figure}.|\begin{c|
|000049c0| 65 6e 74 65 72 7d 0a 5c | 62 65 67 69 6e 7b 74 61 |enter}.\|begin{ta|
|000049d0| 62 75 6c 61 72 7d 7b 7c | 6c 72 7c 72 72 72 7c 7c |bular}{||lr|rrr|||
|000049e0| 72 7c 72 7c 72 7c 7d 0a | 5c 63 6c 69 6e 65 7b 33 |r|r|r|}.|\cline{3|
|000049f0| 2d 38 7d 0a 5c 6d 75 6c | 74 69 63 6f 6c 75 6d 6e |-8}.\mul|ticolumn|
|00004a00| 7b 32 7d 7b 6c 7c 7d 7b | 5c 68 62 6f 78 7b 7d 7d |{2}{l|}{|\hbox{}}|
|00004a10| 20 20 26 20 5c 6d 75 6c | 74 69 63 6f 6c 75 6d 6e |  & \mul|ticolumn|
|00004a20| 7b 33 7d 7b 63 7c 7c 7d | 7b 5c 25 52 65 6d 7d 20 |{3}{c||}|{\%Rem} |
|00004a30| 26 20 5c 6d 75 6c 74 69 | 63 6f 6c 75 6d 6e 7b 33 |& \multi|column{3|
|00004a40| 7d 7b 63 7c 7d 7b 4b 2f | 53 65 63 7d 20 5c 5c 20 |}{c|}{K/|Sec} \\ |
|00004a50| 5c 68 6c 69 6e 65 0a 46 | 69 6c 65 20 20 20 26 20 |\hline.F|ile   & |
|00004a60| 20 20 20 20 20 4b 20 26 | 20 20 20 41 31 20 26 20 |     K &|   A1 & |
|00004a70| 20 4c 5a 43 20 26 20 20 | 52 57 31 20 26 20 5c 6d | LZC &  |RW1 & \m|
|00004a80| 75 6c 74 69 63 6f 6c 75 | 6d 6e 7b 31 7d 7b 63 7d |ulticolu|mn{1}{c}|
|00004a90| 7b 41 31 7d 20 26 20 5c | 6d 75 6c 74 69 63 6f 6c |{A1} & \|multicol|
|00004aa0| 75 6d 6e 7b 31 7d 7b 63 | 7d 7b 4c 5a 43 7d 20 26 |umn{1}{c|}{LZC} &|
|00004ab0| 20 5c 6d 75 6c 74 69 63 | 6f 6c 75 6d 6e 7b 31 7d | \multic|olumn{1}|
|00004ac0| 7b 63 7c 7d 7b 52 57 31 | 7d 20 5c 5c 20 5c 68 6c |{c|}{RW1|} \\ \hl|
|00004ad0| 69 6e 65 0a 62 69 62 20 | 20 20 20 26 20 20 20 20 |ine.bib |   &    |
|00004ae0| 31 30 39 20 26 20 35 33 | 2e 38 20 26 20 34 31 2e |109 & 53|.8 & 41.|
|00004af0| 38 20 26 20 35 39 2e 34 | 20 26 20 20 32 37 7e 7e |8 & 59.4| &  27~~|
|00004b00| 34 33 35 20 26 20 20 35 | 38 7e 7e 7e 39 34 20 26 |435 &  5|8~~~94 &|
|00004b10| 20 32 31 33 7e 7e 33 38 | 38 20 5c 5c 0a 62 6f 6f | 213~~38|8 \\.boo|
|00004b20| 6b 31 20 20 26 20 20 20 | 20 37 35 31 20 26 20 36 |k1  &   | 751 & 6|
|00004b30| 31 2e 36 20 26 20 34 33 | 2e 32 20 26 20 36 37 2e |1.6 & 43|.2 & 67.|
|00004b40| 39 20 26 20 20 32 31 7e | 7e 34 31 39 20 26 20 20 |9 &  21~|~419 &  |
|00004b50| 34 36 7e 7e 7e 39 30 20 | 26 20 31 38 36 7e 7e 33 |46~~~90 |& 186~~3|
|00004b60| 36 38 20 5c 5c 0a 62 6f | 6f 6b 32 20 20 26 20 20 |68 \\.bo|ok2  &  |
|00004b70| 20 20 35 39 37 20 26 20 | 35 32 2e 35 20 26 20 34 |  597 & |52.5 & 4|
|00004b80| 31 2e 31 20 26 20 35 39 | 2e 30 20 26 20 20 32 34 |1.1 & 59|.0 &  24|
|00004b90| 7e 7e 34 33 35 20 26 20 | 20 34 39 7e 7e 7e 39 32 |~~435 & | 49~~~92|
|00004ba0| 20 26 20 32 31 35 7e 7e | 33 37 35 20 5c 5c 0a 67 | & 215~~|375 \\.g|
|00004bb0| 65 6f 20 20 20 20 26 20 | 20 20 20 31 30 30 20 26 |eo    & |   100 &|
|00004bc0| 20 39 34 2e 30 20 26 20 | 37 36 2e 30 20 26 20 38 | 94.0 & |76.0 & 8|
|00004bd0| 34 2e 34 20 26 20 20 31 | 33 7e 7e 32 37 30 20 26 |4.4 &  1|3~~270 &|
|00004be0| 20 20 34 38 7e 7e 7e 37 | 34 20 26 20 31 36 37 7e |  48~~~7|4 & 167~|
|00004bf0| 7e 33 31 33 20 5c 5c 0a | 6e 65 77 73 20 20 20 26 |~313 \\.|news   &|
|00004c00| 20 20 20 20 33 36 38 20 | 26 20 35 36 2e 38 20 26 |    368 |& 56.8 &|
|00004c10| 20 34 38 2e 33 20 26 20 | 36 31 2e 33 20 26 20 20 | 48.3 & |61.3 &  |
|00004c20| 32 37 7e 7e 34 33 33 20 | 26 20 20 34 34 7e 7e 7e |27~~433 |&  44~~~|
|00004c30| 38 37 20 26 20 32 31 30 | 7e 7e 33 39 32 20 5c 5c |87 & 210|~~392 \\|
|00004c40| 0a 6f 62 6a 31 20 20 20 | 26 20 20 20 20 20 32 31 |.obj1   |&     21|
|00004c50| 20 26 20 36 30 2e 38 20 | 26 20 36 35 2e 33 20 26 | & 60.8 |& 65.3 &|
|00004c60| 20 36 31 2e 37 20 26 20 | 20 20 34 7e 7e 33 35 30 | 61.7 & |  4~~350|
|00004c70| 20 26 20 20 35 33 7e 7e | 7e 37 35 20 26 20 31 39 | &  53~~|~75 & 19|
|00004c80| 31 7e 7e 34 32 30 20 5c | 5c 0a 6f 62 6a 32 20 20 |1~~420 \|\.obj2  |
|00004c90| 20 26 20 20 20 20 32 34 | 31 20 26 20 34 37 2e 30 | &    24|1 & 47.0|
|00004ca0| 20 26 20 35 32 2e 31 20 | 26 20 35 31 2e 33 20 26 | & 52.1 |& 51.3 &|
|00004cb0| 20 20 32 33 7e 7e 34 38 | 32 20 26 20 20 34 31 7e |  23~~48|2 &  41~|
|00004cc0| 7e 7e 38 36 20 26 20 32 | 32 35 7e 7e 34 32 33 20 |~~86 & 2|25~~423 |
|00004cd0| 5c 5c 0a 70 61 70 65 72 | 31 20 26 20 20 20 20 20 |\\.paper|1 &     |
|00004ce0| 35 32 20 26 20 35 31 2e | 35 20 26 20 34 37 2e 32 |52 & 51.|5 & 47.2|
|00004cf0| 20 26 20 35 37 2e 38 20 | 26 20 20 32 36 7e 7e 34 | & 57.8 |&  26~~4|
|00004d00| 33 33 20 26 20 20 35 38 | 7e 7e 7e 39 31 20 26 20 |33 &  58|~~~91 & |
|00004d10| 32 32 36 7e 7e 33 37 31 | 20 5c 5c 0a 70 61 70 65 |226~~371| \\.pape|
|00004d20| 72 32 20 26 20 20 20 20 | 20 38 30 20 26 20 35 34 |r2 &    | 80 & 54|
|00004d30| 2e 30 20 26 20 34 34 2e | 30 20 26 20 36 31 2e 30 |.0 & 44.|0 & 61.0|
|00004d40| 20 26 20 20 32 33 7e 7e | 34 30 31 20 26 20 20 36 | &  23~~|401 &  6|
|00004d50| 34 7e 7e 7e 39 34 20 26 | 20 32 30 36 7e 7e 33 38 |4~~~94 &| 206~~38|
|00004d60| 32 20 5c 5c 0a 70 69 63 | 20 20 20 20 26 20 20 20 |2 \\.pic|    &   |
|00004d70| 20 35 30 31 20 26 2a 32 | 33 2e 33 20 26 20 31 32 | 501 &*2|3.3 & 12|
|00004d80| 2e 31 20 26 20 32 35 2e | 36 20 26 20 20 33 37 7e |.1 & 25.|6 &  37~|
|00004d90| 7e 36 30 34 20 26 20 31 | 30 38 7e 7e 31 34 38 20 |~604 & 1|08~~148 |
|00004da0| 26 20 33 34 36 7e 7e 35 | 30 36 20 5c 5c 0a 70 72 |& 346~~5|06 \\.pr|
|00004db0| 6f 67 63 20 20 26 20 20 | 20 20 20 33 39 20 26 20 |ogc  &  |   39 & |
|00004dc0| 34 39 2e 31 20 26 20 34 | 38 2e 33 20 26 20 35 34 |49.1 & 4|8.3 & 54|
|00004dd0| 2e 36 20 26 20 20 32 39 | 7e 7e 33 38 37 20 26 20 |.6 &  29|~~387 & |
|00004de0| 20 35 35 7e 7e 7e 39 30 | 20 26 20 32 34 32 7e 7e | 55~~~90| & 242~~|
|00004df0| 33 38 37 20 5c 5c 0a 70 | 72 6f 67 6c 20 20 26 20 |387 \\.p|rogl  & |
|00004e00| 20 20 20 20 37 30 20 26 | 20 33 35 2e 35 20 26 20 |    70 &| 35.5 & |
|00004e10| 33 37 2e 39 20 26 20 34 | 33 2e 37 20 26 20 20 32 |37.9 & 4|3.7 &  2|
|00004e20| 30 7e 7e 34 36 36 20 26 | 20 20 36 35 7e 7e 31 30 |0~~466 &|  65~~10|
|00004e30| 33 20 26 20 32 34 31 7e | 7e 34 31 32 20 5c 5c 0a |3 & 241~|~412 \\.|
|00004e40| 70 72 6f 67 70 20 20 26 | 20 20 20 20 20 34 38 20 |progp  &|     48 |
|00004e50| 26 20 33 35 2e 34 20 26 | 20 33 38 2e 39 20 26 20 |& 35.4 &| 38.9 & |
|00004e60| 34 32 2e 38 20 26 20 20 | 31 39 7e 7e 34 33 38 20 |42.8 &  |19~~438 |
|00004e70| 26 20 20 36 33 7e 7e 7e | 39 38 20 26 20 32 34 31 |&  63~~~|98 & 241|
|00004e80| 7e 7e 33 34 34 20 5c 5c | 0a 74 72 61 6e 73 20 20 |~~344 \\|.trans  |
|00004e90| 26 20 20 20 20 20 39 31 | 20 26 20 34 30 2e 38 20 |&     91| & 40.8 |
|00004ea0| 26 20 34 30 2e 38 20 26 | 20 34 36 2e 31 20 26 20 |& 40.8 &| 46.1 & |
|00004eb0| 20 32 35 7e 7e 34 35 37 | 20 26 20 20 36 31 7e 7e | 25~~457| &  61~~|
|00004ec0| 7e 39 36 20 26 20 32 34 | 31 7e 7e 34 33 36 20 5c |~96 & 24|1~~436 \|
|00004ed0| 5c 20 5c 68 6c 69 6e 65 | 0a 41 76 65 72 61 67 65 |\ \hline|.Average|
|00004ee0| 26 20 20 20 20 32 31 39 | 20 26 20 35 31 2e 32 20 |&    219| & 51.2 |
|00004ef0| 26 20 34 35 2e 35 20 26 | 20 35 35 2e 35 20 26 20 |& 45.5 &| 55.5 & |
|00004f00| 20 32 32 7e 7e 34 32 39 | 20 26 20 20 35 38 7e 7e | 22~~429| &  58~~|
|00004f10| 7e 39 34 20 26 20 32 32 | 34 7e 7e 33 39 34 20 5c |~94 & 22|4~~394 \|
|00004f20| 5c 20 5c 68 6c 69 6e 65 | 0a 5c 65 6e 64 7b 74 61 |\ \hline|.\end{ta|
|00004f30| 62 75 6c 61 72 7d 0a 5c | 65 6e 64 7b 63 65 6e 74 |bular}.\|end{cent|
|00004f40| 65 72 7d 0a 5c 62 69 67 | 63 61 70 74 69 6f 6e 7b |er}.\big|caption{|
|00004f50| 37 7d 25 0a 7b 50 65 72 | 66 6f 72 6d 61 6e 63 65 |7}%.{Per|formance|
|00004f60| 20 6f 66 20 61 6c 67 6f | 72 69 74 68 6d 73 20 6f | of algo|rithms o|
|00004f70| 6e 20 61 20 50 79 72 61 | 6d 69 64 7e 39 38 32 30 |n a Pyra|mid~9820|
|00004f80| 2e 7d 7b 25 0a 25 0a 54 | 68 69 73 20 74 61 62 6c |.}{%.%.T|his tabl|
|00004f90| 65 20 20 63 6f 6d 70 61 | 72 65 73 20 74 68 65 20 |e  compa|res the |
|00004fa0| 70 65 72 66 6f 72 6d 61 | 6e 63 65 20 20 6f 66 20 |performa|nce  of |
|00004fb0| 74 68 65 20 20 41 31 20 | 28 61 20 73 69 6d 70 6c |the  A1 |(a simpl|
|00004fc0| 65 20 20 4c 5a 37 37 20 | 63 6c 61 73 73 0a 61 6c |e  LZ77 |class.al|
|00004fd0| 67 6f 72 69 74 68 6d 20 | 62 79 20 46 69 61 6c 61 |gorithm |by Fiala|
|00004fe0| 20 61 6e 64 20 47 72 65 | 65 6e 65 29 2c 20 20 4c | and Gre|ene),  L|
|00004ff0| 5a 43 20 28 55 6e 69 78 | 20 5c 69 7b 63 6f 6d 70 |ZC (Unix| \i{comp|
|00005000| 72 65 73 73 7d 20 77 68 | 69 63 68 20 69 73 20 62 |ress} wh|ich is b|
|00005010| 61 73 65 64 0a 6f 6e 20 | 74 68 65 20 4c 5a 57 20 |ased.on |the LZW |
|00005020| 61 6c 67 6f 72 69 74 68 | 6d 29 2c 20 61 6e 64 20 |algorith|m), and |
|00005030| 4c 5a 52 57 31 20 20 28 | 74 68 65 20 74 6f 70 69 |LZRW1  (|the topi|
|00005040| 63 20 6f 66 20 74 68 69 | 73 20 70 61 70 65 72 29 |c of thi|s paper)|
|00005050| 20 61 6c 67 6f 72 69 74 | 68 6d 73 0a 63 6f 64 65 | algorit|hms.code|
|00005060| 64 20 69 6e 7e 43 20 61 | 6e 64 20 72 75 6e 6e 69 |d in~C a|nd runni|
|00005070| 6e 67 20 6f 6e 20 20 61 | 20 50 79 72 61 6d 69 64 |ng on  a| Pyramid|
|00005080| 7e 39 38 32 30 20 63 6f | 6d 70 75 74 65 72 2e 20 |~9820 co|mputer. |
|00005090| 54 68 65 20 69 6d 70 6c | 65 6d 65 6e 74 61 74 69 |The impl|ementati|
|000050a0| 6f 6e 0a 6f 66 20 41 31 | 20 75 73 65 64 20 20 61 |on.of A1| used  a|
|000050b0| 20 68 61 73 68 20 74 61 | 62 6c 65 20 69 6e 64 65 | hash ta|ble inde|
|000050c0| 78 69 6e 67 20 69 6e 74 | 6f 20 61 20 20 62 6f 75 |xing int|o a  bou|
|000050d0| 6e 64 65 64 20 62 75 66 | 66 65 72 20 61 72 72 61 |nded buf|fer arra|
|000050e0| 79 20 68 6f 6c 64 69 6e | 67 0a 6c 69 6e 6b 65 64 |y holdin|g.linked|
|000050f0| 20 6c 69 73 74 73 20 6f | 66 20 68 61 73 68 20 6d | lists o|f hash m|
|00005100| 61 74 63 68 65 73 2e 20 | 41 20 20 73 74 61 6e 64 |atches. |A  stand|
|00005110| 61 72 64 20 63 6f 72 70 | 75 73 20 6f 66 20 66 69 |ard corp|us of fi|
|00005120| 6c 65 73 20 77 61 73 20 | 75 73 65 64 20 66 6f 72 |les was |used for|
|00005130| 0a 74 68 65 20 20 74 65 | 73 74 2e 20 20 54 68 65 |.the  te|st.  The|
|00005140| 20 20 5c 25 52 65 6d 20 | 20 63 6f 6c 75 6d 6e 73 |  \%Rem | columns|
|00005150| 20 20 20 67 69 76 65 20 | 20 63 6f 6d 70 72 65 73 |   give | compres|
|00005160| 73 69 6f 6e 20 20 61 73 | 20 20 61 20 20 70 65 72 |sion  as|  a  per|
|00005170| 63 65 6e 74 61 67 65 0a | 72 65 6d 61 69 6e 69 6e |centage.|remainin|
|00005180| 67 2e 20 54 68 65 20 20 | 4b 2f 53 65 63 20 63 6f |g. The  |K/Sec co|
|00005190| 6c 75 6d 6e 73 20 20 67 | 69 76 65 20 74 68 65 20 |lumns  g|ive the |
|000051a0| 63 6f 6d 70 72 65 73 73 | 69 6f 6e 20 20 61 6e 64 |compress|ion  and|
|000051b0| 20 64 65 63 6f 6d 70 72 | 65 73 73 69 6f 6e 0a 73 | decompr|ession.s|
|000051c0| 70 65 65 64 73 20 69 6e | 20 6b 69 6c 6f 62 79 74 |peeds in| kilobyt|
|000051d0| 65 73 20 28 31 30 32 34 | 29 20 70 65 72 20 20 73 |es (1024|) per  s|
|000051e0| 65 63 6f 6e 64 2e 20 44 | 65 63 6f 6d 70 72 65 73 |econd. D|ecompres|
|000051f0| 73 69 6f 6e 20 73 70 65 | 65 64 73 20 61 72 65 20 |sion spe|eds are |
|00005200| 67 69 76 65 6e 0a 72 65 | 6c 61 74 69 76 65 20 74 |given.re|lative t|
|00005210| 6f 20 20 5c 69 7b 6f 75 | 74 70 75 74 7d 20 28 75 |o  \i{ou|tput} (u|
|00005220| 6e 63 6f 6d 70 72 65 73 | 73 65 64 29 20 20 62 79 |ncompres|sed)  by|
|00005230| 74 65 73 2e 20 53 70 65 | 65 64 73 20 20 77 65 72 |tes. Spe|eds  wer|
|00005240| 65 20 63 61 6c 63 75 6c | 61 74 65 64 0a 66 72 6f |e calcul|ated.fro|
|00005250| 6d 20 20 74 68 65 20 5c | 69 7b 75 73 65 72 7d 20 |m  the \|i{user} |
|00005260| 20 74 69 6d 65 20 66 69 | 65 6c 64 20 20 67 69 76 | time fi|eld  giv|
|00005270| 65 6e 20 62 79 20 20 61 | 6e 20 61 70 70 6c 69 63 |en by  a|n applic|
|00005280| 61 74 69 6f 6e 20 20 6f | 66 20 74 68 65 20 20 75 |ation  o|f the  u|
|00005290| 6e 69 78 0a 5c 69 7b 74 | 69 6d 65 7d 20 20 63 6f |nix.\i{t|ime}  co|
|000052a0| 6d 6d 61 6e 64 20 74 6f | 20 20 61 20 20 62 6c 6f |mmand to|  a  blo|
|000052b0| 63 6b 20 6f 66 20 20 74 | 65 6e 20 20 63 6f 6e 73 |ck of  t|en  cons|
|000052c0| 65 63 75 74 69 76 65 20 | 63 6f 6d 70 72 65 73 73 |ecutive |compress|
|000052d0| 69 6f 6e 20 20 72 75 6e | 73 2e 0a 28 2a 4e 6f 74 |ion  run|s..(*Not|
|000052e0| 65 3a 20 54 68 65 20 41 | 31 20 61 6c 67 6f 72 69 |e: The A|1 algori|
|000052f0| 74 68 6d 20 74 6f 6f 6b | 20 73 6f 20 6c 6f 6e 67 |thm took| so long|
|00005300| 20 20 74 6f 20 72 75 6e | 20 6f 6e 20 74 68 65 20 |  to run| on the |
|00005310| 66 69 6c 65 20 5c 69 7b | 70 69 63 7d 20 74 68 61 |file \i{|pic} tha|
|00005320| 74 0a 69 74 20 20 77 61 | 73 20 74 65 72 6d 69 6e |t.it  wa|s termin|
|00005330| 61 74 65 64 20 20 61 6e | 64 20 72 65 2d 72 75 6e |ated  an|d re-run|
|00005340| 2c 20 20 66 6f 72 20 74 | 68 65 20 20 66 69 6c 65 |,  for t|he  file|
|00005350| 20 5c 69 7b 70 69 63 7d | 20 20 6f 6e 6c 79 2c 20 | \i{pic}|  only, |
|00005360| 77 69 74 68 20 20 61 6e | 0a 75 70 70 65 72 62 6f |with  an|.upperbo|
|00005370| 75 6e 64 20 20 6f 66 20 | 74 65 6e 20 20 6f 6e 20 |und  of |ten  on |
|00005380| 20 69 74 73 20 20 73 65 | 61 72 63 68 29 2e 20 41 | its  se|arch). A|
|00005390| 20 20 63 6f 6d 70 61 72 | 69 73 6f 6e 20 20 6f 66 |  compar|ison  of|
|000053a0| 20 20 4c 5a 52 57 31 20 | 74 6f 20 20 69 74 73 0a |  LZRW1 |to  its.|
|000053b0| 61 6e 63 65 73 74 6f 72 | 20 61 6c 67 6f 72 69 74 |ancestor| algorit|
|000053c0| 68 6d 20 41 31 20 20 73 | 68 6f 77 73 20 74 68 61 |hm A1  s|hows tha|
|000053d0| 74 2c 20 77 68 69 6c 65 | 20 4c 5a 52 57 31 20 20 |t, while| LZRW1  |
|000053e0| 63 6f 6d 70 72 65 73 73 | 65 73 20 61 62 6f 75 74 |compress|es about|
|000053f0| 20 34 2e 33 5c 25 0a 77 | 6f 72 73 65 20 20 74 68 | 4.3\%.w|orse  th|
|00005400| 61 6e 20 74 68 65 20 20 | 41 31 20 20 61 6c 67 6f |an the  |A1  algo|
|00005410| 72 69 74 68 6d 2c 20 4c | 5a 52 57 31 20 20 72 75 |rithm, L|ZRW1  ru|
|00005420| 6e 73 20 20 74 65 6e 20 | 20 74 69 6d 65 73 20 66 |ns  ten | times f|
|00005430| 61 73 74 65 72 2e 20 20 | 4c 5a 52 57 31 0a 63 6f |aster.  |LZRW1.co|
|00005440| 6d 70 72 65 73 73 65 73 | 20 61 62 6f 75 74 20 20 |mpresses| about  |
|00005450| 31 30 5c 25 20 61 62 73 | 6f 6c 75 74 65 20 20 77 |10\% abs|olute  w|
|00005460| 6f 72 73 65 20 74 68 61 | 6e 20 4c 5a 57 2c 20 20 |orse tha|n LZW,  |
|00005470| 62 75 74 20 72 75 6e 73 | 20 20 66 6f 75 72 20 74 |but runs|  four t|
|00005480| 69 6d 65 73 0a 66 61 73 | 74 65 72 2e 20 4c 5a 52 |imes.fas|ter. LZR|
|00005490| 57 31 20 63 6f 6d 70 72 | 65 73 73 65 73 20 72 65 |W1 compr|esses re|
|000054a0| 6c 61 74 69 76 65 6c 79 | 20 70 6f 6f 72 6c 79 20 |latively| poorly |
|000054b0| 6f 6e 20 45 6e 67 6c 69 | 73 68 20 74 65 78 74 20 |on Engli|sh text |
|000054c0| 66 69 6c 65 73 20 28 65 | 2e 67 2e 0a 62 6f 6f 6b |files (e|.g..book|
|000054d0| 31 29 2c 20 62 75 74 20 | 63 6f 6d 70 72 65 73 73 |1), but |compress|
|000054e0| 65 73 20 72 65 6c 61 74 | 69 76 65 6c 79 20 77 65 |es relat|ively we|
|000054f0| 6c 6c 20 20 6f 6e 20 6e | 6f 6e 2d 45 6e 67 6c 69 |ll  on n|on-Engli|
|00005500| 73 68 20 74 65 78 74 20 | 66 69 6c 65 73 20 73 75 |sh text |files su|
|00005510| 63 68 0a 61 73 20 70 72 | 6f 67 72 61 6d 20 20 74 |ch.as pr|ogram  t|
|00005520| 65 78 74 73 20 61 6e 64 | 20 6f 62 6a 65 63 74 20 |exts and| object |
|00005530| 20 66 69 6c 65 73 20 66 | 6f 72 20 77 68 69 63 68 | files f|or which|
|00005540| 20 20 69 74 20 62 65 74 | 74 65 72 73 20 4c 5a 57 |  it bet|ters LZW|
|00005550| 20 20 6f 6e 20 62 6f 74 | 68 0a 63 6f 6d 70 72 65 |  on bot|h.compre|
|00005560| 73 73 69 6f 6e 20 61 6e | 64 20 73 70 65 65 64 2e |ssion an|d speed.|
|00005570| 0a 25 0a 7d 0a 5c 65 6e | 64 7b 66 69 67 75 72 65 |.%.}.\en|d{figure|
|00005580| 7d 0a 0a 5c 62 65 67 69 | 6e 7b 66 69 67 75 72 65 |}..\begi|n{figure|
|00005590| 7d 0a 5c 62 65 67 69 6e | 7b 63 65 6e 74 65 72 7d |}.\begin|{center}|
|000055a0| 0a 5c 62 65 67 69 6e 7b | 74 61 62 75 6c 61 72 7d |.\begin{|tabular}|
|000055b0| 7b 7c 6c 72 72 7c 72 7c | 72 7c 72 7c 7d 0a 5c 68 |{|lrr|r||r|r|}.\h|
|000055c0| 6c 69 6e 65 0a 25 4e 6f | 74 65 3a 20 4b 42 79 74 |line.%No|te: KByt|
|000055d0| 65 73 20 61 72 65 20 72 | 6f 75 6e 64 65 64 20 74 |es are r|ounded t|
|000055e0| 6f 20 74 68 65 20 6e 65 | 61 72 65 73 74 20 4b 2e |o the ne|arest K.|
|000055f0| 0a 25 4e 6f 74 65 3a 20 | 31 36 4b 20 62 6c 6f 63 |.%Note: |16K bloc|
|00005600| 6b 73 20 63 6f 6c 75 6d | 6e 20 64 69 72 65 63 74 |ks colum|n direct|
|00005610| 20 66 72 6f 6d 20 74 65 | 73 74 20 68 61 72 6e 65 | from te|st harne|
|00005620| 73 73 2e 0a 25 4e 6f 74 | 65 3a 20 4b 2f 53 65 63 |ss..%Not|e: K/Sec|
|00005630| 20 72 6f 75 6e 64 65 64 | 20 74 6f 20 74 68 65 20 | rounded| to the |
|00005640| 6e 65 61 72 65 73 74 20 | 4b 2e 0a 25 4e 6f 74 65 |nearest |K..%Note|
|00005650| 3a 20 49 6e 73 74 72 2f | 62 79 74 65 20 72 6f 75 |: Instr/|byte rou|
|00005660| 6e 64 65 64 20 74 6f 20 | 74 68 65 20 6e 65 61 72 |nded to |the near|
|00005670| 65 73 74 20 30 2e 31 20 | 6f 66 20 61 6e 20 69 6e |est 0.1 |of an in|
|00005680| 73 74 72 75 63 74 69 6f | 6e 2e 0a 25 4e 6f 74 65 |structio|n..%Note|
|00005690| 3a 20 30 35 2d 46 65 62 | 2d 39 31 3a 20 49 20 68 |: 05-Feb|-91: I h|
|000056a0| 61 76 65 20 63 68 65 63 | 6b 65 64 20 61 6c 6c 20 |ave chec|ked all |
|000056b0| 74 68 65 20 64 61 74 61 | 20 69 6e 20 74 68 69 73 |the data| in this|
|000056c0| 20 74 61 62 6c 65 20 61 | 6e 64 20 69 74 20 69 73 | table a|nd it is|
|000056d0| 20 4f 4b 2e 0a 46 69 6c | 65 20 20 20 26 20 20 20 | OK..Fil|e   &   |
|000056e0| 20 20 20 4b 20 26 20 20 | 20 2f 31 36 4b 20 26 20 |   K &  | /16K & |
|000056f0| 5c 25 52 65 6d 20 26 20 | 20 20 20 4b 2f 53 65 63 |\%Rem & |   K/Sec|
|00005700| 20 20 20 20 20 20 26 20 | 49 6e 73 2f 42 79 74 65 |      & |Ins/Byte|
|00005710| 20 20 20 5c 5c 20 5c 68 | 6c 69 6e 65 0a 62 69 62 |   \\ \h|line.bib|
|00005720| 20 20 20 20 26 20 20 20 | 20 31 30 39 20 26 20 20 |    &   | 109 &  |
|00005730| 20 20 20 20 37 20 26 20 | 20 36 31 2e 30 20 26 20 |    7 & | 61.0 & |
|00005740| 20 20 20 34 33 7e 7e 31 | 34 37 20 20 20 20 20 26 |   43~~1|47     &|
|00005750| 20 31 33 2e 34 7e 7e 34 | 2e 31 20 20 20 5c 5c 0a | 13.4~~4|.1   \\.|
|00005760| 62 6f 6f 6b 31 20 20 26 | 20 20 20 20 37 35 31 20 |book1  &|    751 |
|00005770| 26 20 20 20 20 20 34 37 | 20 26 20 20 36 39 2e 35 |&     47| &  69.5|
|00005780| 20 26 20 20 20 20 34 30 | 7e 7e 31 33 32 20 20 20 | &    40|~~132   |
|00005790| 20 20 26 20 31 34 2e 37 | 7e 7e 34 2e 36 20 20 20 |  & 14.7|~~4.6   |
|000057a0| 5c 5c 0a 62 6f 6f 6b 32 | 20 20 26 20 20 20 20 35 |\\.book2|  &    5|
|000057b0| 39 37 20 26 20 20 20 20 | 20 33 38 20 26 20 20 36 |97 &    | 38 &  6|
|000057c0| 30 2e 35 20 26 20 20 20 | 20 34 34 7e 7e 31 34 32 |0.5 &   | 44~~142|
|000057d0| 20 20 20 20 20 26 20 31 | 33 2e 31 7e 7e 34 2e 33 |     & 1|3.1~~4.3|
|000057e0| 20 20 20 5c 5c 0a 67 65 | 6f 20 20 20 20 26 20 20 |   \\.ge|o    &  |
|000057f0| 20 20 31 30 30 20 26 20 | 20 20 20 20 20 37 20 26 |  100 & |     7 &|
|00005800| 20 20 38 35 2e 36 20 26 | 20 20 20 20 33 31 7e 7e |  85.6 &|    31~~|
|00005810| 31 33 31 20 20 20 20 20 | 26 20 31 38 2e 35 7e 7e |131     |& 18.5~~|
|00005820| 34 2e 37 20 20 20 5c 5c | 0a 6e 65 77 73 20 20 20 |4.7   \\|.news   |
|00005830| 26 20 20 20 20 33 36 38 | 20 26 20 20 20 20 20 32 |&    368| &     2|
|00005840| 34 20 26 20 20 36 33 2e | 30 20 26 20 20 20 20 34 |4 &  63.|0 &    4|
|00005850| 31 7e 7e 31 35 30 20 20 | 20 20 20 26 20 31 34 2e |1~~150  |   & 14.|
|00005860| 30 7e 7e 34 2e 30 20 20 | 20 5c 5c 0a 6f 62 6a 31 |0~~4.0  | \\.obj1|
|00005870| 20 20 20 26 20 20 20 20 | 20 32 31 20 26 20 20 20 |   &    | 21 &   |
|00005880| 20 20 20 32 20 26 20 20 | 36 31 2e 39 20 26 20 20 |   2 &  |61.9 &  |
|00005890| 20 20 34 31 7e 7e 31 36 | 31 20 20 20 20 20 26 20 |  41~~16|1     & |
|000058a0| 31 34 2e 32 7e 7e 33 2e | 37 20 20 20 5c 5c 0a 6f |14.2~~3.|7   \\.o|
|000058b0| 62 6a 32 20 20 20 26 20 | 20 20 20 32 34 31 20 26 |bj2   & |   241 &|
|000058c0| 20 20 20 20 20 31 36 20 | 26 20 20 35 32 2e 35 20 |     16 |&  52.5 |
|000058d0| 26 20 20 20 20 34 39 7e | 7e 31 35 36 20 20 20 20 |&    49~|~156    |
|000058e0| 20 26 20 31 31 2e 38 7e | 7e 33 2e 38 20 20 20 5c | & 11.8~|~3.8   \|
|000058f0| 5c 0a 70 61 70 65 72 31 | 20 26 20 20 20 20 20 35 |\.paper1| &     5|
|00005900| 32 20 26 20 20 20 20 20 | 20 34 20 26 20 20 35 39 |2 &     | 4 &  59|
|00005910| 2e 35 20 26 20 20 20 20 | 34 35 7e 7e 31 34 33 20 |.5 &    |45~~143 |
|00005920| 20 20 20 20 26 20 31 32 | 2e 39 7e 7e 34 2e 32 20 |    & 12|.9~~4.2 |
|00005930| 20 20 5c 5c 0a 70 61 70 | 65 72 32 20 26 20 20 20 |  \\.pap|er2 &   |
|00005940| 20 20 38 30 20 26 20 20 | 20 20 20 20 36 20 26 20 |  80 &  |    6 & |
|00005950| 20 36 32 2e 34 20 26 20 | 20 20 20 34 34 7e 7e 31 | 62.4 & |   44~~1|
|00005960| 33 38 20 20 20 20 20 26 | 20 31 33 2e 33 7e 7e 34 |38     &| 13.3~~4|
|00005970| 2e 34 20 20 20 5c 5c 0a | 70 69 63 20 20 20 20 26 |.4   \\.|pic    &|
|00005980| 20 20 20 20 35 30 31 20 | 26 20 20 20 20 20 33 32 |    501 |&     32|
|00005990| 20 26 20 20 32 35 2e 38 | 20 26 20 20 20 20 38 37 | &  25.8| &    87|
|000059a0| 7e 7e 31 38 37 20 20 20 | 20 20 26 20 20 36 2e 35 |~~187   |  &  6.5|
|000059b0| 7e 7e 33 2e 31 20 20 20 | 5c 5c 0a 70 72 6f 67 63 |~~3.1   |\\.progc|
|000059c0| 20 20 26 20 20 20 20 20 | 33 39 20 26 20 20 20 20 |  &     |39 &    |
|000059d0| 20 20 33 20 26 20 20 35 | 35 2e 37 20 26 20 20 20 |  3 &  5|5.7 &   |
|000059e0| 20 34 37 7e 7e 31 34 39 | 20 20 20 20 20 26 20 31 | 47~~149|     & 1|
|000059f0| 32 2e 33 7e 7e 34 2e 30 | 20 20 20 5c 5c 0a 70 72 |2.3~~4.0|   \\.pr|
|00005a00| 6f 67 6c 20 20 26 20 20 | 20 20 20 37 30 20 26 20 |ogl  &  |   70 & |
|00005a10| 20 20 20 20 20 35 20 26 | 20 20 34 34 2e 37 20 26 |     5 &|  44.7 &|
|00005a20| 20 20 20 20 35 38 7e 7e | 31 35 37 20 20 20 20 20 |    58~~|157     |
|00005a30| 26 20 31 30 2e 30 7e 7e | 33 2e 38 20 20 20 5c 5c |& 10.0~~|3.8   \\|
|00005a40| 0a 70 72 6f 67 70 20 20 | 26 20 20 20 20 20 34 38 |.progp  |&     48|
|00005a50| 20 26 20 20 20 20 20 20 | 34 20 26 20 20 34 34 2e | &      |4 &  44.|
|00005a60| 32 20 26 20 20 20 20 35 | 38 7e 7e 31 35 38 20 20 |2 &    5|8~~158  |
|00005a70| 20 20 20 26 20 20 39 2e | 39 7e 7e 33 2e 37 20 20 |   &  9.|9~~3.7  |
|00005a80| 20 5c 5c 0a 74 72 61 6e | 73 20 20 26 20 20 20 20 | \\.tran|s  &    |
|00005a90| 20 39 31 20 26 20 20 20 | 20 20 20 36 20 26 20 20 | 91 &   |   6 &  |
|00005aa0| 34 37 2e 39 20 26 20 20 | 20 20 35 33 7e 7e 31 36 |47.9 &  |  53~~16|
|00005ab0| 32 20 20 20 20 20 26 20 | 31 30 2e 39 7e 7e 33 2e |2     & |10.9~~3.|
|00005ac0| 37 20 20 20 5c 5c 20 5c | 68 6c 69 6e 65 0a 41 76 |7   \\ \|hline.Av|
|00005ad0| 65 72 61 67 65 26 20 20 | 20 20 32 31 39 20 26 20 |erage&  |  219 & |
|00005ae0| 20 20 20 20 31 34 20 26 | 20 20 35 36 2e 37 20 26 |    14 &|  56.7 &|
|00005af0| 20 20 20 20 34 39 7e 7e | 31 35 31 20 20 20 20 20 |    49~~|151     |
|00005b00| 26 20 31 32 2e 35 7e 7e | 34 2e 30 20 20 20 5c 5c |& 12.5~~|4.0   \\|
|00005b10| 20 5c 68 6c 69 6e 65 0a | 5c 6d 75 6c 74 69 63 6f | \hline.|\multico|
|00005b20| 6c 75 6d 6e 7b 36 7d 7b | 63 7d 7b 5c 68 62 6f 78 |lumn{6}{|c}{\hbox|
|00005b30| 7b 7d 7d 5c 5c 20 5c 68 | 6c 69 6e 65 0a 7a 65 72 |{}}\\ \h|line.zer|
|00005b40| 6f 73 20 20 26 20 20 20 | 20 20 37 38 20 26 20 20 |os  &   |  78 &  |
|00005b50| 20 20 20 20 35 20 26 20 | 20 31 33 2e 34 20 26 20 |    5 & | 13.4 & |
|00005b60| 20 20 31 33 36 7e 7e 32 | 30 35 20 20 20 20 20 26 |  136~~2|05     &|
|00005b70| 20 20 34 2e 31 7e 7e 32 | 2e 37 20 20 20 5c 5c 0a |  4.1~~2|.7   \\.|
|00005b80| 6e 6f 69 73 65 20 20 26 | 20 20 20 20 20 37 38 20 |noise  &|     78 |
|00005b90| 26 20 20 20 20 20 20 35 | 20 26 20 31 30 30 2e 30 |&      5| & 100.0|
|00005ba0| 20 26 20 20 20 20 32 33 | 7e 7e 31 31 37 38 20 20 | &    23|~~1178  |
|00005bb0| 20 20 26 20 32 34 2e 34 | 7e 30 2e 32 35 20 20 20 |  & 24.4|~0.25   |
|00005bc0| 5c 5c 20 20 5c 68 6c 69 | 6e 65 0a 5c 65 6e 64 7b |\\  \hli|ne.\end{|
|00005bd0| 74 61 62 75 6c 61 72 7d | 0a 5c 65 6e 64 7b 63 65 |tabular}|.\end{ce|
|00005be0| 6e 74 65 72 7d 0a 5c 62 | 69 67 63 61 70 74 69 6f |nter}.\b|igcaptio|
|00005bf0| 6e 7b 38 7d 7b 50 65 72 | 66 6f 72 6d 61 6e 63 65 |n{8}{Per|formance|
|00005c00| 20 6f 66 20 6f 70 74 69 | 6d 69 7a 65 64 20 36 38 | of opti|mized 68|
|00005c10| 30 30 30 20 4c 5a 52 57 | 31 2e 7d 7b 25 0a 25 0a |000 LZRW|1.}{%.%.|
|00005c20| 54 68 69 73 20 74 61 62 | 6c 65 20 67 69 76 65 73 |This tab|le gives|
|00005c30| 20 20 74 68 65 20 70 65 | 72 66 6f 72 6d 61 6e 63 |  the pe|rformanc|
|00005c40| 65 20 6f 66 20 61 6e 20 | 20 68 61 6e 64 2d 6f 70 |e of an | hand-op|
|00005c50| 74 69 6d 69 7a 65 64 20 | 36 38 30 30 30 20 61 73 |timized |68000 as|
|00005c60| 73 65 6d 62 6c 79 0a 6c | 61 6e 67 75 61 67 65 20 |sembly.l|anguage |
|00005c70| 20 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 20 | impleme|ntation |
|00005c80| 6f 66 20 20 4c 5a 52 57 | 31 20 20 72 75 6e 6e 69 |of  LZRW|1  runni|
|00005c90| 6e 67 20 6f 6e 20 20 61 | 6e 20 20 38 4d 48 7a 2c |ng on  a|n  8MHz,|
|00005ca0| 20 32 34 2d 62 69 74 20 | 20 62 75 73 2c 0a 4d 61 | 24-bit | bus,.Ma|
|00005cb0| 63 69 6e 74 6f 73 68 2d | 53 45 20 63 6f 6d 70 75 |cintosh-|SE compu|
|00005cc0| 74 65 72 2e 20 20 54 68 | 65 20 69 6e 70 75 74 20 |ter.  Th|e input |
|00005cd0| 66 69 6c 65 73 20 20 77 | 65 72 65 20 64 69 76 69 |files  w|ere divi|
|00005ce0| 64 65 64 20 69 6e 74 6f | 20 20 31 36 4b 20 62 6c |ded into|  16K bl|
|00005cf0| 6f 63 6b 73 0a 77 68 69 | 63 68 20 20 77 65 72 65 |ocks.whi|ch  were|
|00005d00| 20 20 63 6f 6d 70 72 65 | 73 73 65 64 20 20 69 6e |  compre|ssed  in|
|00005d10| 64 65 70 65 6e 64 65 6e | 74 6c 79 2e 20 20 54 68 |dependen|tly.  Th|
|00005d20| 65 20 5c 25 52 65 6d 20 | 20 63 6f 6c 75 6d 6e 20 |e \%Rem | column |
|00005d30| 20 67 69 76 65 73 20 20 | 74 68 65 0a 63 6f 6d 70 | gives  |the.comp|
|00005d40| 72 65 73 73 69 6f 6e 20 | 20 61 73 20 61 20 20 70 |ression | as a  p|
|00005d50| 65 72 63 65 6e 74 61 67 | 65 20 72 65 6d 61 69 6e |ercentag|e remain|
|00005d60| 69 6e 67 2e 20 20 54 68 | 65 20 4b 2f 53 65 63 20 |ing.  Th|e K/Sec |
|00005d70| 20 63 6f 6c 75 6d 6e 20 | 67 69 76 65 73 20 20 74 | column |gives  t|
|00005d80| 68 65 0a 63 6f 6d 70 72 | 65 73 73 69 6f 6e 20 61 |he.compr|ession a|
|00005d90| 6e 64 20 20 64 65 63 6f | 6d 70 72 65 73 73 69 6f |nd  deco|mpressio|
|00005da0| 6e 20 73 70 65 65 64 73 | 20 69 6e 20 6b 69 6c 6f |n speeds| in kilo|
|00005db0| 62 79 74 65 73 20 20 28 | 31 30 32 34 29 20 70 65 |bytes  (|1024) pe|
|00005dc0| 72 20 73 65 63 6f 6e 64 | 2e 0a 44 65 63 6f 6d 70 |r second|..Decomp|
|00005dd0| 72 65 73 73 69 6f 6e 20 | 73 70 65 65 64 73 20 20 |ression |speeds  |
|00005de0| 61 72 65 20 67 69 76 65 | 6e 20 72 65 6c 61 74 69 |are give|n relati|
|00005df0| 76 65 20 74 6f 20 20 5c | 69 7b 6f 75 74 70 75 74 |ve to  \|i{output|
|00005e00| 7d 20 28 75 6e 63 6f 6d | 70 72 65 73 73 65 64 29 |} (uncom|pressed)|
|00005e10| 0a 62 79 74 65 73 2e 20 | 54 68 65 20 20 73 70 65 |.bytes. |The  spe|
|00005e20| 65 64 73 20 61 72 65 20 | 66 6f 72 20 65 78 65 63 |eds are |for exec|
|00005e30| 75 74 69 6f 6e 20 20 6f | 6e 6c 79 20 61 6e 64 20 |ution  o|nly and |
|00005e40| 64 6f 20 6e 6f 74 20 20 | 69 6e 63 6c 75 64 65 20 |do not  |include |
|00005e50| 49 4f 2e 20 54 68 65 0a | 49 6e 73 2f 42 79 74 65 |IO. The.|Ins/Byte|
|00005e60| 20 20 63 6f 6c 75 6d 6e | 20 20 67 69 76 65 73 20 |  column|  gives |
|00005e70| 20 74 68 65 20 20 61 76 | 65 72 61 67 65 20 20 6e | the  av|erage  n|
|00005e80| 75 6d 62 65 72 20 20 6f | 66 20 20 36 38 30 30 30 |umber  o|f  68000|
|00005e90| 20 20 69 6e 73 74 72 75 | 63 74 69 6f 6e 73 0a 72 |  instru|ctions.r|
|00005ea0| 65 71 75 69 72 65 64 20 | 74 6f 20 70 72 6f 63 65 |equired |to proce|
|00005eb0| 73 73 20 65 61 63 68 20 | 62 79 74 65 20 64 75 72 |ss each |byte dur|
|00005ec0| 69 6e 67 20 63 6f 6d 70 | 72 65 73 73 69 6f 6e 20 |ing comp|ression |
|00005ed0| 61 6e 64 20 64 65 63 6f | 6d 70 72 65 73 73 69 6f |and deco|mpressio|
|00005ee0| 6e 20 61 6e 64 0a 77 61 | 73 20 20 6f 62 74 61 69 |n and.wa|s  obtai|
|00005ef0| 6e 65 64 20 62 79 20 20 | 69 6e 73 65 72 74 69 6e |ned by  |insertin|
|00005f00| 67 20 63 6f 75 6e 74 69 | 6e 67 20 20 69 6e 73 74 |g counti|ng  inst|
|00005f10| 72 75 63 74 69 6f 6e 73 | 20 69 6e 74 6f 20 20 74 |ructions| into  t|
|00005f20| 68 65 20 63 6f 64 65 20 | 20 61 6e 64 0a 70 65 72 |he code | and.per|
|00005f30| 66 6f 72 6d 69 6e 67 20 | 20 61 20 73 65 70 61 72 |forming | a separ|
|00005f40| 61 74 65 20 20 72 75 6e | 2e 20 41 6c 6c 20 20 72 |ate  run|. All  r|
|00005f50| 65 73 75 6c 74 73 20 20 | 77 65 72 65 20 72 6f 75 |esults  |were rou|
|00005f60| 6e 64 65 64 20 20 74 6f | 20 74 68 65 20 20 67 69 |nded  to| the  gi|
|00005f70| 76 65 6e 0a 61 63 63 75 | 72 61 63 79 2e 20 41 20 |ven.accu|racy. A |
|00005f80| 20 63 6f 6d 70 61 72 69 | 73 6f 6e 20 6f 66 20 20 | compari|son of  |
|00005f90| 74 68 65 73 65 20 72 65 | 73 75 6c 74 73 20 20 74 |these re|sults  t|
|00005fa0| 6f 20 74 68 6f 73 65 20 | 20 6f 66 20 5c 63 69 74 |o those | of \cit|
|00005fb0| 65 66 69 67 75 72 65 7b | 37 7d 0a 73 68 6f 77 73 |efigure{|7}.shows|
|00005fc0| 20 74 68 61 74 20 20 74 | 68 65 20 64 69 76 69 73 | that  t|he divis|
|00005fd0| 69 6f 6e 20 6f 66 20 20 | 74 68 65 20 69 6e 70 75 |ion of  |the inpu|
|00005fe0| 74 20 20 66 69 6c 65 20 | 69 6e 74 6f 20 31 36 4b |t  file |into 16K|
|00005ff0| 20 20 62 6c 6f 63 6b 73 | 20 77 6f 72 73 65 6e 65 |  blocks| worsene|
|00006000| 64 0a 63 6f 6d 70 72 65 | 73 73 69 6f 6e 20 20 62 |d.compre|ssion  b|
|00006010| 79 20 61 6e 20 20 61 76 | 65 72 61 67 65 20 6f 66 |y an  av|erage of|
|00006020| 20 20 6f 6e 6c 79 20 31 | 2e 32 5c 25 20 20 61 62 |  only 1|.2\%  ab|
|00006030| 73 6f 6c 75 74 65 20 77 | 69 74 68 20 20 74 68 65 |solute w|ith  the|
|00006040| 20 6d 61 78 69 6d 75 6d | 0a 69 6d 70 61 63 74 20 | maximum|.impact |
|00006050| 62 65 69 6e 67 20 31 2e | 38 5c 25 20 61 62 73 6f |being 1.|8\% abso|
|00006060| 6c 75 74 65 2e 20 54 68 | 65 20 72 65 73 75 6c 74 |lute. Th|e result|
|00006070| 73 20 66 6f 72 20 74 68 | 65 20 66 69 6c 65 73 20 |s for th|e files |
|00006080| 5c 69 7b 7a 65 72 6f 73 | 7d 20 28 7a 65 72 6f 0a |\i{zeros|} (zero.|
|00006090| 62 79 74 65 73 29 20 20 | 61 6e 64 20 20 5c 69 7b |bytes)  |and  \i{|
|000060a0| 6e 6f 69 73 65 7d 20 20 | 28 75 6e 69 66 6f 72 6d |noise}  |(uniform|
|000060b0| 6c 79 20 20 61 6e 64 20 | 20 69 6e 64 65 70 65 6e |ly  and | indepen|
|000060c0| 64 65 6e 74 6c 79 20 20 | 72 61 6e 64 6f 6d 20 20 |dently  |random  |
|000060d0| 62 79 74 65 73 29 0a 73 | 75 67 67 65 73 74 20 20 |bytes).s|uggest  |
|000060e0| 74 68 61 74 20 4c 5a 52 | 57 31 27 73 20 20 62 65 |that LZR|W1's  be|
|000060f0| 73 74 20 72 75 6e 6e 69 | 6e 67 20 20 74 69 6d 65 |st runni|ng  time|
|00006100| 20 69 73 20 20 61 62 6f | 75 74 20 6f 6e 65 20 20 | is  abo|ut one  |
|00006110| 74 68 69 72 64 20 6f 66 | 20 20 69 74 73 0a 61 76 |third of|  its.av|
|00006120| 65 72 61 67 65 20 72 75 | 6e 6e 69 6e 67 20 74 69 |erage ru|nning ti|
|00006130| 6d 65 2c 20 20 61 6e 64 | 20 74 68 61 74 20 69 74 |me,  and| that it|
|00006140| 73 20 77 6f 72 73 74 20 | 72 75 6e 6e 69 6e 67 20 |s worst |running |
|00006150| 74 69 6d 65 20 20 69 73 | 20 61 62 6f 75 74 20 74 |time  is| about t|
|00006160| 77 69 63 65 0a 69 74 73 | 20 61 76 65 72 61 67 65 |wice.its| average|
|00006170| 20 72 75 6e 6e 69 6e 67 | 20 74 69 6d 65 2e 20 46 | running| time. F|
|00006180| 6f 72 20 6f 72 64 69 6e | 61 72 79 20 74 65 78 74 |or ordin|ary text|
|00006190| 20 64 61 74 61 2c 20 4c | 5a 52 57 31 20 72 65 71 | data, L|ZRW1 req|
|000061a0| 75 69 72 65 73 20 61 62 | 6f 75 74 0a 31 33 7e 69 |uires ab|out.13~i|
|000061b0| 6e 73 74 72 75 63 74 69 | 6f 6e 73 20 20 74 6f 20 |nstructi|ons  to |
|000061c0| 63 6f 6d 70 72 65 73 73 | 20 20 61 6e 64 20 61 62 |compress|  and ab|
|000061d0| 6f 75 74 20 20 34 7e 69 | 6e 73 74 72 75 63 74 69 |out  4~i|nstructi|
|000061e0| 6f 6e 73 20 74 6f 20 20 | 64 65 63 6f 6d 70 72 65 |ons to  |decompre|
|000061f0| 73 73 0a 65 61 63 68 20 | 62 79 74 65 2e 0a 25 0a |ss.each |byte..%.|
|00006200| 7d 0a 5c 65 6e 64 7b 66 | 69 67 75 72 65 7d 0a 25 |}.\end{f|igure}.%|
|00006210| 53 74 61 6e 64 61 72 64 | 20 64 65 76 69 61 74 69 |Standard| deviati|
|00006220| 6f 6e 20 66 6f 72 20 31 | 36 4b 20 63 68 61 6e 67 |on for 1|6K chang|
|00006230| 65 3d 30 2e 35 31 0a 0a | 5c 65 6e 64 7b 64 6f 63 |e=0.51..|\end{doc|
|00006240| 75 6d 65 6e 74 7d 0a 0a | 0a 0a 0a 0a             |ument}..|....    |
+--------+-------------------------+-------------------------+--------+--------+