/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume25 / zip / part04

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 4e 65 77 73 67 72 6f 75 | 70 73 3a 20 63 6f 6d 70 |Newsgrou|ps: comp|
|00000010| 2e 73 6f 75 72 63 65 73 | 2e 75 6e 69 78 0a 46 72 |.sources|.unix.Fr|
|00000020| 6f 6d 3a 20 6d 61 64 6c | 65 72 40 63 63 6f 2e 63 |om: madl|er@cco.c|
|00000030| 61 6c 74 65 63 68 2e 65 | 64 75 20 28 4d 61 72 6b |altech.e|du (Mark|
|00000040| 20 41 64 6c 65 72 29 0a | 53 75 62 6a 65 63 74 3a | Adler).|Subject:|
|00000050| 20 76 32 35 69 31 34 35 | 3a 20 7a 69 70 20 2d 20 | v25i145|: zip - |
|00000060| 66 69 6c 65 20 63 6f 6d | 70 72 65 73 73 69 6f 6e |file com|pression|
|00000070| 2f 61 72 63 68 69 76 65 | 20 74 6f 6f 6c 2c 20 50 |/archive| tool, P|
|00000080| 61 72 74 30 34 2f 30 37 | 0a 53 65 6e 64 65 72 3a |art04/07|.Sender:|
|00000090| 20 75 6e 69 78 2d 73 6f | 75 72 63 65 73 2d 6d 6f | unix-so|urces-mo|
|000000a0| 64 65 72 61 74 6f 72 40 | 70 61 2e 64 65 63 2e 63 |derator@|pa.dec.c|
|000000b0| 6f 6d 0a 41 70 70 72 6f | 76 65 64 3a 20 76 69 78 |om.Appro|ved: vix|
|000000c0| 69 65 40 70 61 2e 64 65 | 63 2e 63 6f 6d 0a 0a 53 |ie@pa.de|c.com..S|
|000000d0| 75 62 6d 69 74 74 65 64 | 2d 42 79 3a 20 6d 61 64 |ubmitted|-By: mad|
|000000e0| 6c 65 72 40 63 63 6f 2e | 63 61 6c 74 65 63 68 2e |ler@cco.|caltech.|
|000000f0| 65 64 75 20 28 4d 61 72 | 6b 20 41 64 6c 65 72 29 |edu (Mar|k Adler)|
|00000100| 0a 50 6f 73 74 69 6e 67 | 2d 4e 75 6d 62 65 72 3a |.Posting|-Number:|
|00000110| 20 56 6f 6c 75 6d 65 20 | 32 35 2c 20 49 73 73 75 | Volume |25, Issu|
|00000120| 65 20 31 34 35 0a 41 72 | 63 68 69 76 65 2d 4e 61 |e 145.Ar|chive-Na|
|00000130| 6d 65 3a 20 7a 69 70 2f | 70 61 72 74 30 34 0a 0a |me: zip/|part04..|
|00000140| 23 21 20 2f 62 69 6e 2f | 73 68 0a 23 20 54 68 69 |#! /bin/|sh.# Thi|
|00000150| 73 20 69 73 20 61 20 73 | 68 65 6c 6c 20 61 72 63 |s is a s|hell arc|
|00000160| 68 69 76 65 2e 20 20 52 | 65 6d 6f 76 65 20 61 6e |hive.  R|emove an|
|00000170| 79 74 68 69 6e 67 20 62 | 65 66 6f 72 65 20 74 68 |ything b|efore th|
|00000180| 69 73 20 6c 69 6e 65 2c | 20 74 68 65 6e 20 75 6e |is line,| then un|
|00000190| 70 61 63 6b 0a 23 20 69 | 74 20 62 79 20 73 61 76 |pack.# i|t by sav|
|000001a0| 69 6e 67 20 69 74 20 69 | 6e 74 6f 20 61 20 66 69 |ing it i|nto a fi|
|000001b0| 6c 65 20 61 6e 64 20 74 | 79 70 69 6e 67 20 22 73 |le and t|yping "s|
|000001c0| 68 20 66 69 6c 65 22 2e | 20 20 54 6f 20 6f 76 65 |h file".|  To ove|
|000001d0| 72 77 72 69 74 65 20 65 | 78 69 73 74 69 6e 67 0a |rwrite e|xisting.|
|000001e0| 23 20 66 69 6c 65 73 2c | 20 74 79 70 65 20 22 73 |# files,| type "s|
|000001f0| 68 20 66 69 6c 65 20 2d | 63 22 2e 20 20 59 6f 75 |h file -|c".  You|
|00000200| 20 63 61 6e 20 61 6c 73 | 6f 20 66 65 65 64 20 74 | can als|o feed t|
|00000210| 68 69 73 20 61 73 20 73 | 74 61 6e 64 61 72 64 20 |his as s|tandard |
|00000220| 69 6e 70 75 74 20 76 69 | 61 0a 23 20 75 6e 73 68 |input vi|a.# unsh|
|00000230| 61 72 2c 20 6f 72 20 62 | 79 20 74 79 70 69 6e 67 |ar, or b|y typing|
|00000240| 20 22 73 68 20 3c 66 69 | 6c 65 22 2c 20 65 2e 67 | "sh <fi|le", e.g|
|00000250| 2e 2e 20 20 49 66 20 74 | 68 69 73 20 61 72 63 68 |..  If t|his arch|
|00000260| 69 76 65 20 69 73 20 63 | 6f 6d 70 6c 65 74 65 2c |ive is c|omplete,|
|00000270| 20 79 6f 75 0a 23 20 77 | 69 6c 6c 20 73 65 65 20 | you.# w|ill see |
|00000280| 74 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 6d 65 |the foll|owing me|
|00000290| 73 73 61 67 65 20 61 74 | 20 74 68 65 20 65 6e 64 |ssage at| the end|
|000002a0| 3a 0a 23 09 09 22 45 6e | 64 20 6f 66 20 61 72 63 |:.#.."En|d of arc|
|000002b0| 68 69 76 65 20 34 20 28 | 6f 66 20 37 29 2e 22 0a |hive 4 (|of 7).".|
|000002c0| 23 20 43 6f 6e 74 65 6e | 74 73 3a 20 20 69 6d 5f |# Conten|ts:  im_|
|000002d0| 6c 6d 61 74 2e 63 20 7a | 69 70 2e 63 20 7a 69 70 |lmat.c z|ip.c zip|
|000002e0| 2e 64 6f 63 0a 23 20 57 | 72 61 70 70 65 64 20 62 |.doc.# W|rapped b|
|000002f0| 79 20 76 69 78 69 65 40 | 63 6f 67 6e 69 74 69 6f |y vixie@|cognitio|
|00000300| 6e 2e 70 61 2e 64 65 63 | 2e 63 6f 6d 20 6f 6e 20 |n.pa.dec|.com on |
|00000310| 53 75 6e 20 4d 61 72 20 | 20 31 20 31 38 3a 35 37 |Sun Mar | 1 18:57|
|00000320| 3a 33 38 20 31 39 39 32 | 0a 50 41 54 48 3d 2f 62 |:38 1992|.PATH=/b|
|00000330| 69 6e 3a 2f 75 73 72 2f | 62 69 6e 3a 2f 75 73 72 |in:/usr/|bin:/usr|
|00000340| 2f 75 63 62 20 3b 20 65 | 78 70 6f 72 74 20 50 41 |/ucb ; e|xport PA|
|00000350| 54 48 0a 69 66 20 74 65 | 73 74 20 2d 66 20 27 69 |TH.if te|st -f 'i|
|00000360| 6d 5f 6c 6d 61 74 2e 63 | 27 20 2d 61 20 22 24 7b |m_lmat.c|' -a "${|
|00000370| 31 7d 22 20 21 3d 20 22 | 2d 63 22 20 3b 20 74 68 |1}" != "|-c" ; th|
|00000380| 65 6e 20 0a 20 20 65 63 | 68 6f 20 73 68 61 72 3a |en .  ec|ho shar:|
|00000390| 20 57 69 6c 6c 20 6e 6f | 74 20 63 6c 6f 62 62 65 | Will no|t clobbe|
|000003a0| 72 20 65 78 69 73 74 69 | 6e 67 20 66 69 6c 65 20 |r existi|ng file |
|000003b0| 5c 22 27 69 6d 5f 6c 6d | 61 74 2e 63 27 5c 22 0a |\"'im_lm|at.c'\".|
|000003c0| 65 6c 73 65 0a 65 63 68 | 6f 20 73 68 61 72 3a 20 |else.ech|o shar: |
|000003d0| 45 78 74 72 61 63 74 69 | 6e 67 20 5c 22 27 69 6d |Extracti|ng \"'im|
|000003e0| 5f 6c 6d 61 74 2e 63 27 | 5c 22 20 5c 28 32 37 35 |_lmat.c'|\" \(275|
|000003f0| 39 37 20 63 68 61 72 61 | 63 74 65 72 73 5c 29 0a |97 chara|cters\).|
|00000400| 73 65 64 20 22 73 2f 5e | 58 2f 2f 22 20 3e 27 69 |sed "s/^|X//" >'i|
|00000410| 6d 5f 6c 6d 61 74 2e 63 | 27 20 3c 3c 27 45 4e 44 |m_lmat.c|' <<'END|
|00000420| 5f 4f 46 5f 46 49 4c 45 | 27 0a 58 2f 2a 0a 58 0a |_OF_FILE|'.X/*.X.|
|00000430| 58 20 43 6f 70 79 72 69 | 67 68 74 20 28 43 29 20 |X Copyri|ght (C) |
|00000440| 31 39 39 30 2c 31 39 39 | 31 20 4d 61 72 6b 20 41 |1990,199|1 Mark A|
|00000450| 64 6c 65 72 2c 20 52 69 | 63 68 61 72 64 20 42 2e |dler, Ri|chard B.|
|00000460| 20 57 61 6c 65 73 2c 20 | 61 6e 64 20 4a 65 61 6e | Wales, |and Jean|
|00000470| 2d 6c 6f 75 70 20 47 61 | 69 6c 6c 79 2e 0a 58 20 |-loup Ga|illy..X |
|00000480| 50 65 72 6d 69 73 73 69 | 6f 6e 20 69 73 20 67 72 |Permissi|on is gr|
|00000490| 61 6e 74 65 64 20 74 6f | 20 61 6e 79 20 69 6e 64 |anted to| any ind|
|000004a0| 69 76 69 64 75 61 6c 20 | 6f 72 20 69 6e 73 74 69 |ividual |or insti|
|000004b0| 74 75 74 69 6f 6e 20 74 | 6f 20 75 73 65 2c 20 63 |tution t|o use, c|
|000004c0| 6f 70 79 2c 20 6f 72 0a | 58 20 72 65 64 69 73 74 |opy, or.|X redist|
|000004d0| 72 69 62 75 74 65 20 74 | 68 69 73 20 73 6f 66 74 |ribute t|his soft|
|000004e0| 77 61 72 65 20 73 6f 20 | 6c 6f 6e 67 20 61 73 20 |ware so |long as |
|000004f0| 61 6c 6c 20 6f 66 20 74 | 68 65 20 6f 72 69 67 69 |all of t|he origi|
|00000500| 6e 61 6c 20 66 69 6c 65 | 73 20 61 72 65 20 69 6e |nal file|s are in|
|00000510| 63 6c 75 64 65 64 0a 58 | 20 75 6e 6d 6f 64 69 66 |cluded.X| unmodif|
|00000520| 69 65 64 2c 20 74 68 61 | 74 20 69 74 20 69 73 20 |ied, tha|t it is |
|00000530| 6e 6f 74 20 73 6f 6c 64 | 20 66 6f 72 20 70 72 6f |not sold| for pro|
|00000540| 66 69 74 2c 20 61 6e 64 | 20 74 68 61 74 20 74 68 |fit, and| that th|
|00000550| 69 73 20 63 6f 70 79 72 | 69 67 68 74 20 6e 6f 74 |is copyr|ight not|
|00000560| 69 63 65 0a 58 20 69 73 | 20 72 65 74 61 69 6e 65 |ice.X is| retaine|
|00000570| 64 2e 0a 58 0a 58 2a 2f | 0a 58 0a 58 2f 2a 0a 58 |d..X.X*/|.X.X/*.X|
|00000580| 20 2a 20 20 69 6d 5f 6c | 6d 61 74 2e 63 20 62 79 | *  im_l|mat.c by|
|00000590| 20 4a 65 61 6e 2d 6c 6f | 75 70 20 47 61 69 6c 6c | Jean-lo|up Gaill|
|000005a0| 79 2e 0a 58 20 2a 0a 58 | 20 2a 20 20 50 55 52 50 |y..X *.X| *  PURP|
|000005b0| 4f 53 45 0a 58 20 2a 0a | 58 20 2a 20 20 20 20 20 |OSE.X *.|X *     |
|000005c0| 20 49 64 65 6e 74 69 66 | 79 20 6e 65 77 20 74 65 | Identif|y new te|
|000005d0| 78 74 20 61 73 20 72 65 | 70 65 74 69 74 69 6f 6e |xt as re|petition|
|000005e0| 73 20 6f 66 20 6f 6c 64 | 20 74 65 78 74 20 77 69 |s of old| text wi|
|000005f0| 74 68 69 6e 20 61 20 66 | 69 78 65 64 2d 0a 58 20 |thin a f|ixed-.X |
|00000600| 2a 20 20 20 20 20 20 6c | 65 6e 67 74 68 20 73 6c |*      l|ength sl|
|00000610| 69 64 69 6e 67 20 77 69 | 6e 64 6f 77 20 74 72 61 |iding wi|ndow tra|
|00000620| 69 6c 69 6e 67 20 62 65 | 68 69 6e 64 20 74 68 65 |iling be|hind the|
|00000630| 20 6e 65 77 20 74 65 78 | 74 2e 0a 58 20 2a 0a 58 | new tex|t..X *.X|
|00000640| 20 2a 20 20 44 49 53 43 | 55 53 53 49 4f 4e 0a 58 | *  DISC|USSION.X|
|00000650| 20 2a 0a 58 20 2a 20 20 | 20 20 20 20 54 68 65 20 | *.X *  |    The |
|00000660| 22 69 6d 70 6c 6f 73 69 | 6f 6e 22 20 70 72 6f 63 |"implosi|on" proc|
|00000670| 65 73 73 20 64 65 70 65 | 6e 64 73 20 6f 6e 20 62 |ess depe|nds on b|
|00000680| 65 69 6e 67 20 61 62 6c | 65 20 74 6f 20 69 64 65 |eing abl|e to ide|
|00000690| 6e 74 69 66 79 20 70 6f | 72 74 69 6f 6e 73 0a 58 |ntify po|rtions.X|
|000006a0| 20 2a 20 20 20 20 20 20 | 6f 66 20 74 68 65 20 69 | *      |of the i|
|000006b0| 6e 70 75 74 20 74 65 78 | 74 20 77 68 69 63 68 20 |nput tex|t which |
|000006c0| 61 72 65 20 69 64 65 6e | 74 69 63 61 6c 20 74 6f |are iden|tical to|
|000006d0| 20 65 61 72 6c 69 65 72 | 20 69 6e 70 75 74 20 28 | earlier| input (|
|000006e0| 77 69 74 68 69 6e 20 61 | 0a 58 20 2a 20 20 20 20 |within a|.X *    |
|000006f0| 20 20 73 6c 69 64 69 6e | 67 20 77 69 6e 64 6f 77 |  slidin|g window|
|00000700| 20 74 72 61 69 6c 69 6e | 67 20 62 65 68 69 6e 64 | trailin|g behind|
|00000710| 20 74 68 65 20 69 6e 70 | 75 74 20 63 75 72 72 65 | the inp|ut curre|
|00000720| 6e 74 6c 79 20 62 65 69 | 6e 67 20 70 72 6f 63 65 |ntly bei|ng proce|
|00000730| 73 73 65 64 29 2e 0a 58 | 20 2a 0a 58 20 2a 20 20 |ssed)..X| *.X *  |
|00000740| 20 20 20 20 54 68 65 20 | 6d 6f 73 74 20 73 74 72 |    The |most str|
|00000750| 61 69 67 68 74 66 6f 72 | 77 61 72 64 20 74 65 63 |aightfor|ward tec|
|00000760| 68 6e 69 71 75 65 20 74 | 75 72 6e 73 20 6f 75 74 |hnique t|urns out|
|00000770| 20 74 6f 20 62 65 20 74 | 68 65 20 66 61 73 74 65 | to be t|he faste|
|00000780| 73 74 20 66 6f 72 0a 58 | 20 2a 20 20 20 20 20 20 |st for.X| *      |
|00000790| 6d 6f 73 74 20 69 6e 70 | 75 74 20 66 69 6c 65 73 |most inp|ut files|
|000007a0| 3a 20 74 72 79 20 61 6c | 6c 20 70 6f 73 73 69 62 |: try al|l possib|
|000007b0| 6c 65 20 6d 61 74 63 68 | 65 73 20 61 6e 64 20 73 |le match|es and s|
|000007c0| 65 6c 65 63 74 20 74 68 | 65 20 6c 6f 6e 67 65 73 |elect th|e longes|
|000007d0| 74 2e 0a 58 20 2a 20 20 | 20 20 20 20 54 68 65 20 |t..X *  |    The |
|000007e0| 6b 65 79 20 66 65 61 74 | 75 72 65 20 69 73 20 6f |key feat|ure is o|
|000007f0| 66 20 74 68 69 73 20 61 | 6c 67 6f 72 69 74 68 6d |f this a|lgorithm|
|00000800| 20 69 73 20 74 68 61 74 | 20 69 6e 73 65 72 74 69 | is that| inserti|
|00000810| 6f 6e 20 61 6e 64 20 64 | 65 6c 65 74 69 6f 6e 73 |on and d|eletions|
|00000820| 0a 58 20 2a 20 20 20 20 | 20 20 66 72 6f 6d 20 74 |.X *    |  from t|
|00000830| 68 65 20 73 74 72 69 6e | 67 20 64 69 63 74 69 6f |he strin|g dictio|
|00000840| 6e 61 72 79 20 61 72 65 | 20 76 65 72 79 20 73 69 |nary are| very si|
|00000850| 6d 70 6c 65 20 61 6e 64 | 20 74 68 75 73 20 66 61 |mple and| thus fa|
|00000860| 73 74 2e 20 49 6e 73 65 | 72 74 69 6f 6e 73 0a 58 |st. Inse|rtions.X|
|00000870| 20 2a 20 20 20 20 20 20 | 61 6e 64 20 64 65 6c 65 | *      |and dele|
|00000880| 74 69 6f 6e 73 20 61 72 | 65 20 70 65 72 66 6f 72 |tions ar|e perfor|
|00000890| 6d 65 64 20 61 74 20 65 | 61 63 68 20 69 6e 70 75 |med at e|ach inpu|
|000008a0| 74 20 63 68 61 72 61 63 | 74 65 72 2c 20 77 68 65 |t charac|ter, whe|
|000008b0| 72 65 61 73 20 73 74 72 | 69 6e 67 0a 58 20 2a 20 |reas str|ing.X * |
|000008c0| 20 20 20 20 20 6d 61 74 | 63 68 65 73 20 61 72 65 |     mat|ches are|
|000008d0| 20 70 65 72 66 6f 72 6d | 65 64 20 6f 6e 6c 79 20 | perform|ed only |
|000008e0| 77 68 65 6e 20 74 68 65 | 20 70 72 65 76 69 6f 75 |when the| previou|
|000008f0| 73 20 6d 61 74 63 68 20 | 65 6e 64 73 2e 20 53 6f |s match |ends. So|
|00000900| 20 69 74 20 69 73 0a 58 | 20 2a 20 20 20 20 20 20 | it is.X| *      |
|00000910| 70 72 65 66 65 72 61 62 | 6c 65 20 74 6f 20 73 70 |preferab|le to sp|
|00000920| 65 6e 64 20 6d 6f 72 65 | 20 74 69 6d 65 20 69 6e |end more| time in|
|00000930| 20 6d 61 74 63 68 65 73 | 20 74 6f 20 61 6c 6c 6f | matches| to allo|
|00000940| 77 20 76 65 72 79 20 66 | 61 73 74 20 73 74 72 69 |w very f|ast stri|
|00000950| 6e 67 0a 58 20 2a 20 20 | 20 20 20 20 69 6e 73 65 |ng.X *  |    inse|
|00000960| 72 74 69 6f 6e 73 20 61 | 6e 64 20 64 65 6c 65 74 |rtions a|nd delet|
|00000970| 69 6f 6e 73 2e 20 54 68 | 65 20 6d 61 74 63 68 69 |ions. Th|e matchi|
|00000980| 6e 67 20 61 6c 67 6f 72 | 69 74 68 6d 20 66 6f 72 |ng algor|ithm for|
|00000990| 20 73 6d 61 6c 6c 20 73 | 74 72 69 6e 67 73 0a 58 | small s|trings.X|
|000009a0| 20 2a 20 20 20 20 20 20 | 69 73 20 69 6e 73 70 69 | *      |is inspi|
|000009b0| 72 65 64 20 66 72 6f 6d | 20 74 68 61 74 20 6f 66 |red from| that of|
|000009c0| 20 52 61 62 69 6e 20 26 | 20 4b 61 72 70 2e 20 41 | Rabin &| Karp. A|
|000009d0| 20 62 72 75 74 65 20 66 | 6f 72 63 65 20 61 70 70 | brute f|orce app|
|000009e0| 72 6f 61 63 68 20 69 73 | 0a 58 20 2a 20 20 20 20 |roach is|.X *    |
|000009f0| 20 20 75 73 65 64 20 74 | 6f 20 66 69 6e 64 20 6c |  used t|o find l|
|00000a00| 6f 6e 67 65 72 20 73 74 | 72 69 6e 67 73 20 77 68 |onger st|rings wh|
|00000a10| 65 6e 20 61 20 73 6d 61 | 6c 6c 20 6d 61 74 63 68 |en a sma|ll match|
|00000a20| 20 68 61 73 20 62 65 65 | 6e 20 66 6f 75 6e 64 2e | has bee|n found.|
|00000a30| 0a 58 20 2a 20 20 20 20 | 20 20 41 20 73 69 6d 69 |.X *    |  A simi|
|00000a40| 6c 61 72 20 61 6c 67 6f | 72 69 74 68 6d 20 69 73 |lar algo|rithm is|
|00000a50| 20 75 73 65 64 20 69 6e | 20 66 72 65 65 7a 65 20 | used in| freeze |
|00000a60| 28 62 79 20 4c 65 6f 6e | 69 64 20 42 72 6f 75 6b |(by Leon|id Brouk|
|00000a70| 68 69 73 29 20 62 75 74 | 20 74 68 65 0a 58 20 2a |his) but| the.X *|
|00000a80| 20 20 20 20 20 20 61 6c | 67 6f 72 69 74 68 6d 20 |      al|gorithm |
|00000a90| 75 73 65 64 20 68 65 72 | 65 20 69 73 20 66 61 73 |used her|e is fas|
|00000aa0| 74 65 72 2e 0a 58 20 2a | 20 20 20 20 20 20 20 20 |ter..X *|        |
|00000ab0| 20 41 20 70 72 65 76 69 | 6f 75 73 20 76 65 72 73 | A previ|ous vers|
|00000ac0| 69 6f 6e 20 6f 66 20 74 | 68 69 73 20 66 69 6c 65 |ion of t|his file|
|00000ad0| 20 75 73 65 64 20 61 20 | 6d 6f 72 65 20 73 6f 70 | used a |more sop|
|00000ae0| 68 69 73 74 69 63 61 74 | 65 64 20 61 6c 67 6f 72 |histicat|ed algor|
|00000af0| 69 74 68 6d 0a 58 20 2a | 20 20 20 20 20 20 28 62 |ithm.X *|      (b|
|00000b00| 79 20 46 69 61 6c 61 20 | 61 6e 64 20 47 72 65 65 |y Fiala |and Gree|
|00000b10| 6e 65 29 20 77 68 69 63 | 68 20 69 73 20 67 75 61 |ne) whic|h is gua|
|00000b20| 72 61 6e 74 65 65 64 20 | 74 6f 20 72 75 6e 20 69 |ranteed |to run i|
|00000b30| 6e 20 6c 69 6e 65 61 72 | 20 61 6d 6f 72 74 69 7a |n linear| amortiz|
|00000b40| 65 64 0a 58 20 2a 20 20 | 20 20 20 20 74 69 6d 65 |ed.X *  |    time|
|00000b50| 2c 20 62 75 74 20 68 61 | 73 20 61 20 6c 61 72 67 |, but ha|s a larg|
|00000b60| 65 72 20 61 76 65 72 61 | 67 65 20 63 6f 73 74 20 |er avera|ge cost |
|00000b70| 61 6e 64 20 75 73 65 73 | 20 6d 6f 72 65 20 6d 65 |and uses| more me|
|00000b80| 6d 6f 72 79 2e 20 48 6f | 77 65 76 65 72 0a 58 20 |mory. Ho|wever.X |
|00000b90| 2a 20 20 20 20 20 20 74 | 68 65 20 46 26 47 20 61 |*      t|he F&G a|
|00000ba0| 6c 67 6f 72 69 74 68 6d | 20 6d 61 79 20 62 65 20 |lgorithm| may be |
|00000bb0| 66 61 73 74 65 72 20 66 | 6f 72 20 73 6f 6d 65 20 |faster f|or some |
|00000bc0| 68 69 67 68 6c 79 20 72 | 65 64 75 6e 64 61 6e 74 |highly r|edundant|
|00000bd0| 20 66 69 6c 65 73 20 69 | 66 0a 58 20 2a 20 20 20 | files i|f.X *   |
|00000be0| 20 20 20 74 68 65 20 70 | 61 72 61 6d 65 74 65 72 |   the p|arameter|
|00000bf0| 20 6d 61 78 5f 63 68 61 | 69 6e 5f 6c 65 6e 67 74 | max_cha|in_lengt|
|00000c00| 68 20 28 64 65 73 63 72 | 69 62 65 64 20 62 65 6c |h (descr|ibed bel|
|00000c10| 6f 77 29 20 69 73 20 74 | 6f 6f 20 6c 61 72 67 65 |ow) is t|oo large|
|00000c20| 2e 0a 58 20 2a 0a 58 20 | 2a 20 20 41 43 4b 4e 4f |..X *.X |*  ACKNO|
|00000c30| 57 4c 45 44 47 45 4d 45 | 4e 54 53 0a 58 20 2a 0a |WLEDGEME|NTS.X *.|
|00000c40| 58 20 2a 20 20 20 20 20 | 20 52 69 63 68 20 57 61 |X *     | Rich Wa|
|00000c50| 6c 65 73 20 64 65 66 69 | 6e 65 64 20 74 68 65 20 |les defi|ned the |
|00000c60| 69 6e 74 65 72 66 61 63 | 65 2c 20 70 72 6f 76 69 |interfac|e, provi|
|00000c70| 64 65 64 20 74 68 65 20 | 6e 65 63 65 73 73 61 72 |ded the |necessar|
|00000c80| 79 20 69 6e 66 6f 72 6d | 61 74 69 6f 6e 0a 58 20 |y inform|ation.X |
|00000c90| 2a 20 20 20 20 20 20 74 | 6f 20 65 6e 73 75 72 65 |*      t|o ensure|
|00000ca0| 20 63 6f 6d 70 61 74 69 | 62 69 6c 69 74 79 20 77 | compati|bility w|
|00000cb0| 69 74 68 20 70 6b 75 6e | 7a 69 70 20 31 2e 30 20 |ith pkun|zip 1.0 |
|00000cc0| 28 6e 6f 74 20 61 6e 20 | 65 61 73 79 20 6a 6f 62 |(not an |easy job|
|00000cd0| 29 20 61 6e 64 0a 58 20 | 2a 20 20 20 20 20 20 73 |) and.X |*      s|
|00000ce0| 75 67 67 65 73 74 65 64 | 20 74 68 65 20 73 6f 6c |uggested| the sol|
|00000cf0| 75 74 69 6f 6e 20 28 6e | 20 3d 3d 20 31 20 2b 20 |ution (n| == 1 + |
|00000d00| 6e 2d 31 29 20 61 64 6f | 70 74 65 64 20 68 65 72 |n-1) ado|pted her|
|00000d10| 65 2e 0a 58 20 2a 20 20 | 20 20 20 20 54 68 65 20 |e..X *  |    The |
|00000d20| 69 64 65 61 20 6f 66 20 | 6c 61 7a 79 20 65 76 61 |idea of |lazy eva|
|00000d30| 6c 75 61 74 69 6f 6e 20 | 6f 66 20 6d 61 74 63 68 |luation |of match|
|00000d40| 65 73 20 69 73 20 64 75 | 65 20 74 6f 20 4a 61 6e |es is du|e to Jan|
|00000d50| 20 4d 61 72 6b 20 57 61 | 6d 73 2c 20 61 6e 64 0a | Mark Wa|ms, and.|
|00000d60| 58 20 2a 20 20 20 20 20 | 20 49 20 66 6f 75 6e 64 |X *     | I found|
|00000d70| 20 69 74 20 69 6e 20 27 | 66 72 65 65 7a 65 27 20 | it in '|freeze' |
|00000d80| 77 72 69 74 74 65 6e 20 | 62 79 20 4c 65 6f 6e 69 |written |by Leoni|
|00000d90| 64 20 42 72 6f 75 6b 68 | 69 73 2e 0a 58 20 2a 20 |d Broukh|is..X * |
|00000da0| 20 20 20 20 20 53 70 65 | 63 69 61 6c 20 74 68 61 |     Spe|cial tha|
|00000db0| 6e 6b 73 20 74 6f 20 4b | 61 69 2d 55 77 65 20 52 |nks to K|ai-Uwe R|
|00000dc0| 6f 6d 6d 65 6c 20 66 6f | 72 20 74 68 65 20 4f 53 |ommel fo|r the OS|
|00000dd0| 2f 32 20 70 6f 72 74 2c | 20 74 6f 20 47 6c 65 6e |/2 port,| to Glen|
|00000de0| 6e 20 4a 2e 0a 58 20 2a | 20 20 20 20 20 20 41 6e |n J..X *|      An|
|00000df0| 64 72 65 77 73 20 66 6f | 72 20 74 68 65 20 56 4d |drews fo|r the VM|
|00000e00| 53 20 70 6f 72 74 2c 20 | 61 6e 64 20 74 6f 20 6d |S port, |and to m|
|00000e10| 61 6e 79 20 6f 74 68 65 | 72 20 69 6e 66 6f 2d 7a |any othe|r info-z|
|00000e20| 69 70 70 65 72 73 20 66 | 6f 72 20 74 65 73 74 69 |ippers f|or testi|
|00000e30| 6e 67 2e 0a 58 20 2a 0a | 58 20 2a 20 20 52 45 46 |ng..X *.|X *  REF|
|00000e40| 45 52 45 4e 43 45 53 0a | 58 20 2a 0a 58 20 2a 20 |ERENCES.|X *.X * |
|00000e50| 20 20 20 20 20 41 20 64 | 65 73 63 72 69 70 74 69 |     A d|escripti|
|00000e60| 6f 6e 20 6f 66 20 74 68 | 65 20 52 61 62 69 6e 20 |on of th|e Rabin |
|00000e70| 61 6e 64 20 4b 61 72 70 | 20 61 6c 67 6f 72 69 74 |and Karp| algorit|
|00000e80| 68 6d 20 69 73 20 67 69 | 76 65 6e 20 69 6e 20 74 |hm is gi|ven in t|
|00000e90| 68 65 20 62 6f 6f 6b 0a | 58 20 2a 20 20 20 20 20 |he book.|X *     |
|00000ea0| 20 20 20 20 20 22 41 6c | 67 6f 72 69 74 68 6d 73 |     "Al|gorithms|
|00000eb0| 22 20 62 79 20 52 2e 20 | 53 65 64 67 65 77 69 63 |" by R. |Sedgewic|
|00000ec0| 6b 2c 20 41 64 64 69 73 | 6f 6e 2d 57 65 73 6c 65 |k, Addis|on-Wesle|
|00000ed0| 79 2c 20 70 32 35 32 2e | 0a 58 20 2a 0a 58 20 2a |y, p252.|.X *.X *|
|00000ee0| 20 20 20 20 20 20 46 69 | 61 6c 61 2c 45 2e 52 2e |      Fi|ala,E.R.|
|00000ef0| 2c 20 61 6e 64 20 47 72 | 65 65 6e 65 2c 44 2e 48 |, and Gr|eene,D.H|
|00000f00| 2e 0a 58 20 2a 20 20 20 | 20 20 20 20 20 20 20 44 |..X *   |       D|
|00000f10| 61 74 61 20 43 6f 6d 70 | 72 65 73 73 69 6f 6e 20 |ata Comp|ression |
|00000f20| 77 69 74 68 20 46 69 6e | 69 74 65 20 57 69 6e 64 |with Fin|ite Wind|
|00000f30| 6f 77 73 2c 20 43 41 43 | 4d 2c 20 33 32 2c 34 20 |ows, CAC|M, 32,4 |
|00000f40| 28 31 39 38 39 29 20 34 | 39 30 2d 35 39 35 2e 0a |(1989) 4|90-595..|
|00000f50| 58 20 2a 0a 58 20 2a 20 | 20 49 4e 54 45 52 46 41 |X *.X * | INTERFA|
|00000f60| 43 45 0a 58 20 2a 0a 58 | 20 2a 20 20 20 20 20 20 |CE.X *.X| *      |
|00000f70| 49 6d 70 45 72 72 20 6c | 6d 5f 69 6e 69 74 20 28 |ImpErr l|m_init (|
|00000f80| 69 6e 74 20 70 61 63 6b | 5f 6c 65 76 65 6c 29 0a |int pack|_level).|
|00000f90| 58 20 2a 20 20 20 20 20 | 20 20 20 20 20 49 6e 69 |X *     |     Ini|
|00000fa0| 74 69 61 6c 69 7a 65 20 | 74 68 65 20 22 6c 6f 6e |tialize |the "lon|
|00000fb0| 67 65 73 74 20 6d 61 74 | 63 68 22 20 72 6f 75 74 |gest mat|ch" rout|
|00000fc0| 69 6e 65 73 20 66 6f 72 | 20 61 20 6e 65 77 20 66 |ines for| a new f|
|00000fd0| 69 6c 65 2e 0a 58 20 2a | 20 20 20 20 20 20 20 20 |ile..X *|        |
|00000fe0| 20 20 54 68 65 20 67 6c | 6f 62 61 6c 20 76 61 72 |  The gl|obal var|
|00000ff0| 69 61 62 6c 65 20 66 64 | 20 69 73 20 61 6e 20 69 |iable fd| is an i|
|00001000| 6d 70 6c 69 63 69 74 20 | 70 61 72 61 6d 65 74 65 |mplicit |paramete|
|00001010| 72 2e 0a 58 20 2a 0a 58 | 20 2a 20 20 20 20 20 20 |r..X *.X| *      |
|00001020| 49 6d 70 45 72 72 20 6c | 6d 5f 69 6e 70 75 74 20 |ImpErr l|m_input |
|00001030| 28 55 5f 43 48 41 52 20 | 2a 62 6c 6f 63 6b 2c 20 |(U_CHAR |*block, |
|00001040| 55 5f 49 4e 54 20 63 6f | 75 6e 74 29 0a 58 20 2a |U_INT co|unt).X *|
|00001050| 20 20 20 20 20 20 20 20 | 20 20 50 72 6f 63 65 73 |        |  Proces|
|00001060| 73 20 61 20 62 6c 6f 63 | 6b 20 6f 66 20 69 6e 70 |s a bloc|k of inp|
|00001070| 75 74 20 63 68 61 72 61 | 63 74 65 72 73 2e 0a 58 |ut chara|cters..X|
|00001080| 20 2a 0a 58 20 2a 20 20 | 20 20 20 20 49 6d 70 45 | *.X *  |    ImpE|
|00001090| 72 72 20 6c 6d 5f 77 69 | 6e 64 75 70 20 28 76 6f |rr lm_wi|ndup (vo|
|000010a0| 69 64 29 0a 58 20 2a 20 | 20 20 20 20 20 20 20 20 |id).X * |        |
|000010b0| 20 46 6c 75 73 68 20 6f | 75 74 20 74 68 65 20 72 | Flush o|ut the r|
|000010c0| 65 6d 61 69 6e 69 6e 67 | 20 75 6e 70 72 6f 63 65 |emaining| unproce|
|000010d0| 73 73 65 64 20 69 6e 70 | 75 74 2e 0a 58 20 2a 2f |ssed inp|ut..X */|
|000010e0| 0a 58 0a 58 23 69 6e 63 | 6c 75 64 65 20 22 69 6d |.X.X#inc|lude "im|
|000010f0| 70 6c 6f 64 65 2e 68 22 | 0a 58 0a 58 2f 2a 2a 2a |plode.h"|.X.X/***|
|00001100| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001110| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001120| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001130| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001140| 2a 2a 2a 2a 0a 58 20 2a | 0a 58 20 2a 20 43 6f 6e |****.X *|.X * Con|
|00001150| 66 69 67 75 72 61 74 69 | 6f 6e 20 70 61 72 61 6d |figurati|on param|
|00001160| 65 74 65 72 73 0a 58 20 | 2a 2f 0a 58 0a 58 23 64 |eters.X |*/.X.X#d|
|00001170| 65 66 69 6e 65 20 4d 41 | 58 5f 4d 41 54 43 48 5f |efine MA|X_MATCH_|
|00001180| 4c 45 4e 47 54 48 20 20 | 33 32 30 0a 58 2f 2a 20 |LENGTH  |320.X/* |
|00001190| 54 68 65 20 6d 61 78 69 | 6d 75 6d 20 6d 61 74 63 |The maxi|mum matc|
|000011a0| 68 20 6c 65 6e 67 74 68 | 2e 20 33 32 30 20 3d 20 |h length|. 320 = |
|000011b0| 36 34 20 2b 20 32 35 36 | 2e 20 28 49 66 20 74 68 |64 + 256|. (If th|
|000011c0| 65 20 6c 65 6e 67 74 68 | 20 69 73 20 67 72 65 61 |e length| is grea|
|000011d0| 74 65 72 20 74 68 61 6e | 0a 58 20 2a 20 36 33 2c |ter than|.X * 63,|
|000011e0| 20 70 6b 7a 69 70 20 75 | 73 65 73 20 61 6e 20 65 | pkzip u|ses an e|
|000011f0| 78 74 72 61 20 62 79 74 | 65 2e 29 0a 58 20 2a 2f |xtra byt|e.).X */|
|00001200| 0a 58 0a 58 23 64 65 66 | 69 6e 65 20 4d 41 58 5f |.X.X#def|ine MAX_|
|00001210| 57 42 49 54 53 20 20 31 | 33 0a 58 23 64 65 66 69 |WBITS  1|3.X#defi|
|00001220| 6e 65 20 57 53 49 5a 45 | 20 28 31 20 3c 3c 20 4d |ne WSIZE| (1 << M|
|00001230| 41 58 5f 57 42 49 54 53 | 29 0a 58 2f 2a 20 4d 61 |AX_WBITS|).X/* Ma|
|00001240| 78 69 6d 75 6d 20 77 69 | 6e 64 6f 77 20 73 69 7a |ximum wi|ndow siz|
|00001250| 65 20 3d 20 38 4b 20 2a | 2f 0a 58 0a 58 2f 2a 20 |e = 8K *|/.X.X/* |
|00001260| 43 6f 6e 73 74 61 6e 74 | 73 20 75 73 65 64 20 74 |Constant|s used t|
|00001270| 6f 20 64 69 6d 65 6e 73 | 69 6f 6e 20 74 68 65 20 |o dimens|ion the |
|00001280| 68 61 73 68 20 74 61 62 | 6c 65 3a 20 2a 2f 0a 58 |hash tab|le: */.X|
|00001290| 23 64 65 66 69 6e 65 20 | 48 41 53 48 5f 42 49 54 |#define |HASH_BIT|
|000012a0| 53 20 20 31 34 0a 58 2f | 2a 20 48 41 53 48 5f 42 |S  14.X/|* HASH_B|
|000012b0| 49 54 53 20 6d 75 73 74 | 20 62 65 20 3e 3d 20 31 |ITS must| be >= 1|
|000012c0| 33 2c 20 73 65 65 20 6c | 6f 6e 67 65 73 74 5f 6d |3, see l|ongest_m|
|000012d0| 61 74 63 68 28 29 20 2a | 2f 0a 58 0a 58 23 64 65 |atch() *|/.X.X#de|
|000012e0| 66 69 6e 65 20 48 41 53 | 48 5f 53 49 5a 45 20 28 |fine HAS|H_SIZE (|
|000012f0| 31 3c 3c 48 41 53 48 5f | 42 49 54 53 29 0a 58 23 |1<<HASH_|BITS).X#|
|00001300| 64 65 66 69 6e 65 20 48 | 41 53 48 5f 4d 41 53 4b |define H|ASH_MASK|
|00001310| 20 28 48 41 53 48 5f 53 | 49 5a 45 2d 31 29 0a 58 | (HASH_S|IZE-1).X|
|00001320| 0a 58 23 69 66 20 64 65 | 66 69 6e 65 64 28 4d 53 |.X#if de|fined(MS|
|00001330| 44 4f 53 29 20 7c 7c 20 | 64 65 66 69 6e 65 64 28 |DOS) || |defined(|
|00001340| 69 33 38 36 29 20 7c 7c | 20 64 65 66 69 6e 65 64 |i386) ||| defined|
|00001350| 28 6d 63 36 38 30 32 30 | 29 20 7c 7c 20 64 65 66 |(mc68020|) || def|
|00001360| 69 6e 65 64 28 76 61 78 | 29 0a 58 23 20 20 20 64 |ined(vax|).X#   d|
|00001370| 65 66 69 6e 65 20 55 4e | 41 4c 49 47 4e 45 44 5f |efine UN|ALIGNED_|
|00001380| 4f 4b 0a 58 20 20 20 20 | 2f 2a 20 44 65 66 69 6e |OK.X    |/* Defin|
|00001390| 65 20 74 68 69 73 20 73 | 79 6d 62 6f 6c 20 69 66 |e this s|ymbol if|
|000013a0| 20 79 6f 75 72 20 74 61 | 72 67 65 74 20 61 6c 6c | your ta|rget all|
|000013b0| 6f 77 73 20 61 63 63 65 | 73 73 20 74 6f 20 75 6e |ows acce|ss to un|
|000013c0| 61 6c 69 67 6e 65 64 20 | 64 61 74 61 2e 0a 58 20 |aligned |data..X |
|000013d0| 20 20 20 20 2a 20 54 68 | 69 73 20 69 73 20 6e 6f |    * Th|is is no|
|000013e0| 74 20 6d 61 6e 64 61 74 | 6f 72 79 2c 20 6a 75 73 |t mandat|ory, jus|
|000013f0| 74 20 61 20 73 70 65 65 | 64 20 6f 70 74 69 6d 69 |t a spee|d optimi|
|00001400| 7a 61 74 69 6f 6e 2e 20 | 54 68 65 20 63 6f 6d 70 |zation. |The comp|
|00001410| 72 65 73 73 65 64 0a 58 | 20 20 20 20 20 2a 20 6f |ressed.X|     * o|
|00001420| 75 74 70 75 74 20 69 73 | 20 73 74 72 69 63 74 6c |utput is| strictl|
|00001430| 79 20 69 64 65 6e 74 69 | 63 61 6c 2e 0a 58 20 20 |y identi|cal..X  |
|00001440| 20 20 20 2a 2f 0a 58 23 | 65 6e 64 69 66 0a 58 23 |   */.X#|endif.X#|
|00001450| 69 66 64 65 66 20 5f 5f | 54 55 52 42 4f 43 5f 5f |ifdef __|TURBOC__|
|00001460| 0a 58 23 20 20 20 64 65 | 66 69 6e 65 20 44 59 4e |.X#   de|fine DYN|
|00001470| 5f 41 4c 4c 4f 43 0a 58 | 20 20 20 20 2f 2a 20 54 |_ALLOC.X|    /* T|
|00001480| 75 72 62 6f 20 43 20 32 | 2e 30 20 64 6f 65 73 20 |urbo C 2|.0 does |
|00001490| 6e 6f 74 20 61 63 63 65 | 70 74 20 66 61 72 20 73 |not acce|pt far s|
|000014a0| 74 61 74 69 63 20 61 6c | 6c 6f 63 61 74 69 6f 6e |tatic al|location|
|000014b0| 73 20 69 6e 20 73 6d 61 | 6c 6c 20 6d 6f 64 65 6c |s in sma|ll model|
|000014c0| 20 2a 2f 0a 58 23 65 6e | 64 69 66 0a 58 0a 58 2f | */.X#en|dif.X.X/|
|000014d0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000014e0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000014f0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001500| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001510| 2a 2a 2a 2a 2a 2a 2a 0a | 58 20 2a 0a 58 20 2a 20 |*******.|X *.X * |
|00001520| 4c 6f 63 61 6c 20 64 61 | 74 61 20 75 73 65 64 20 |Local da|ta used |
|00001530| 62 79 20 74 68 65 20 22 | 6c 6f 6e 67 65 73 74 20 |by the "|longest |
|00001540| 6d 61 74 63 68 22 20 72 | 6f 75 74 69 6e 65 73 2e |match" r|outines.|
|00001550| 0a 58 20 2a 2f 0a 58 0a | 58 23 69 66 20 48 41 53 |.X */.X.|X#if HAS|
|00001560| 48 5f 42 49 54 53 20 3c | 3d 20 31 34 0a 58 20 20 |H_BITS <|= 14.X  |
|00001570| 20 74 79 70 65 64 65 66 | 20 75 6e 73 69 67 6e 65 | typedef| unsigne|
|00001580| 64 20 73 68 6f 72 74 20 | 48 61 73 68 3b 0a 58 23 |d short |Hash;.X#|
|00001590| 65 6c 73 65 0a 58 20 20 | 20 2f 2a 20 44 65 66 69 |else.X  | /* Defi|
|000015a0| 6e 65 64 20 6a 75 73 74 | 20 66 6f 72 20 73 61 66 |ned just| for saf|
|000015b0| 65 74 79 2c 20 73 69 6e | 63 65 20 76 61 6c 75 65 |ety, sin|ce value|
|000015c0| 73 20 3e 20 31 34 20 64 | 6f 20 6e 6f 74 20 73 70 |s > 14 d|o not sp|
|000015d0| 65 65 64 20 75 70 20 69 | 6d 70 6c 6f 73 69 6f 6e |eed up i|mplosion|
|000015e0| 20 2a 2f 0a 58 20 20 20 | 74 79 70 65 64 65 66 20 | */.X   |typedef |
|000015f0| 75 6e 73 69 67 6e 65 64 | 20 6c 6f 6e 67 20 48 61 |unsigned| long Ha|
|00001600| 73 68 3b 0a 58 23 65 6e | 64 69 66 0a 58 0a 74 79 |sh;.X#en|dif.X.ty|
|00001610| 70 65 64 65 66 20 75 6e | 73 69 67 6e 65 64 20 73 |pedef un|signed s|
|00001620| 68 6f 72 74 20 50 6f 73 | 3b 0a 74 79 70 65 64 65 |hort Pos|;.typede|
|00001630| 66 20 75 6e 73 69 67 6e | 65 64 20 69 6e 74 20 20 |f unsign|ed int  |
|00001640| 49 50 6f 73 3b 0a 58 2f | 2a 20 41 20 50 6f 73 20 |IPos;.X/|* A Pos |
|00001650| 69 73 20 61 6e 20 69 6e | 64 65 78 20 69 6e 20 74 |is an in|dex in t|
|00001660| 68 65 20 63 68 61 72 61 | 63 74 65 72 20 77 69 6e |he chara|cter win|
|00001670| 64 6f 77 2e 20 57 65 20 | 75 73 65 20 73 68 6f 72 |dow. We |use shor|
|00001680| 74 20 69 6e 73 74 65 61 | 64 20 6f 66 20 69 6e 74 |t instea|d of int|
|00001690| 20 74 6f 0a 58 20 2a 20 | 73 61 76 65 20 73 70 61 | to.X * |save spa|
|000016a0| 63 65 20 69 6e 20 74 68 | 65 20 76 61 72 69 6f 75 |ce in th|e variou|
|000016b0| 73 20 74 61 62 6c 65 73 | 2e 20 49 50 6f 73 20 69 |s tables|. IPos i|
|000016c0| 73 20 75 73 65 64 20 6f | 6e 6c 79 20 66 6f 72 20 |s used o|nly for |
|000016d0| 70 61 72 61 6d 65 74 65 | 72 20 70 61 73 73 69 6e |paramete|r passin|
|000016e0| 67 2e 0a 58 20 2a 2f 0a | 58 0a 69 6e 74 20 6e 65 |g..X */.|X.int ne|
|000016f0| 61 72 20 6d 69 6e 5f 6d | 61 74 63 68 5f 6c 65 6e |ar min_m|atch_len|
|00001700| 67 74 68 3b 0a 58 2f 2a | 20 4d 69 6e 69 6d 75 6d |gth;.X/*| Minimum|
|00001710| 20 6d 61 74 63 68 20 6c | 65 6e 67 74 68 2c 20 32 | match l|ength, 2|
|00001720| 20 66 6f 72 20 62 69 6e | 61 72 79 20 66 69 6c 65 | for bin|ary file|
|00001730| 73 2c 20 33 20 66 6f 72 | 20 61 73 63 69 69 20 66 |s, 3 for| ascii f|
|00001740| 69 6c 65 73 2e 0a 58 20 | 2a 20 28 62 61 64 20 6c |iles..X |* (bad l|
|00001750| 75 63 6b 20 66 6f 72 20 | 65 62 63 64 69 63 20 75 |uck for |ebcdic u|
|00001760| 73 65 72 73 3b 20 6e 6f | 74 20 62 65 63 61 75 73 |sers; no|t becaus|
|00001770| 65 20 74 68 65 79 20 6d | 61 79 20 6e 6f 74 20 67 |e they m|ay not g|
|00001780| 65 74 20 6f 70 74 69 6d | 61 6c 0a 58 20 2a 20 63 |et optim|al.X * c|
|00001790| 6f 6d 70 72 65 73 73 69 | 6f 6e 2c 20 62 75 74 20 |ompressi|on, but |
|000017a0| 62 65 63 61 75 73 65 20 | 74 68 65 79 20 68 61 76 |because |they hav|
|000017b0| 65 20 74 6f 20 75 73 65 | 20 65 62 63 64 69 63 20 |e to use| ebcdic |
|000017c0| 6d 61 63 68 69 6e 65 73 | 20 3a 2d 29 0a 58 20 2a |machines| :-).X *|
|000017d0| 20 41 20 7a 65 72 6f 20 | 76 61 6c 75 65 20 6d 65 | A zero |value me|
|000017e0| 61 6e 73 20 74 68 61 74 | 20 74 68 65 20 6d 69 6e |ans that| the min|
|000017f0| 5f 6d 61 74 63 68 5f 6c | 65 6e 67 74 68 20 69 73 |_match_l|ength is|
|00001800| 20 6e 6f 74 20 79 65 74 | 20 64 65 74 65 72 6d 69 | not yet| determi|
|00001810| 6e 65 64 2e 0a 58 20 2a | 2f 0a 58 0a 55 5f 43 48 |ned..X *|/.X.U_CH|
|00001820| 41 52 20 6e 65 61 72 20 | 77 69 6e 64 6f 77 5b 4d |AR near |window[M|
|00001830| 41 58 5f 4d 41 54 43 48 | 5f 4c 45 4e 47 54 48 20 |AX_MATCH|_LENGTH |
|00001840| 2b 20 57 53 49 5a 45 20 | 2b 20 42 53 5a 5d 3b 0a |+ WSIZE |+ BSZ];.|
|00001850| 58 2f 2a 20 4d 41 58 5f | 4d 41 54 43 48 5f 4c 45 |X/* MAX_|MATCH_LE|
|00001860| 4e 47 54 48 20 62 79 74 | 65 73 20 61 72 65 20 64 |NGTH byt|es are d|
|00001870| 75 70 6c 69 63 61 74 65 | 64 20 61 74 20 62 6f 74 |uplicate|d at bot|
|00001880| 68 20 65 6e 64 73 20 6f | 66 20 74 68 65 20 77 69 |h ends o|f the wi|
|00001890| 6e 64 6f 77 2c 0a 58 20 | 2a 20 74 6f 20 73 70 65 |ndow,.X |* to spe|
|000018a0| 65 64 20 75 70 20 73 74 | 72 69 6e 67 20 63 6f 6d |ed up st|ring com|
|000018b0| 70 61 72 69 73 6f 6e 73 | 2e 20 54 68 65 20 42 53 |parisons|. The BS|
|000018c0| 5a 20 65 78 74 72 61 20 | 62 79 74 65 73 20 61 6c |Z extra |bytes al|
|000018d0| 6c 6f 77 20 61 20 62 6c | 6f 63 6b 20 63 6f 70 79 |low a bl|ock copy|
|000018e0| 0a 58 20 2a 20 6f 66 20 | 74 68 65 20 69 6e 70 75 |.X * of |the inpu|
|000018f0| 74 20 62 75 66 66 65 72 | 20 69 6e 74 6f 20 74 68 |t buffer| into th|
|00001900| 65 20 77 69 6e 64 6f 77 | 20 69 6e 73 74 65 61 64 |e window| instead|
|00001910| 20 6f 66 20 61 20 63 6f | 70 79 20 6f 6e 65 20 62 | of a co|py one b|
|00001920| 79 74 65 20 61 74 20 61 | 20 74 69 6d 65 2e 0a 58 |yte at a| time..X|
|00001930| 20 2a 2f 0a 58 0a 58 23 | 64 65 66 69 6e 65 20 4d | */.X.X#|define M|
|00001940| 41 58 5f 44 49 53 54 20 | 28 57 53 49 5a 45 20 2b |AX_DIST |(WSIZE +|
|00001950| 20 42 53 5a 29 0a 58 2f | 2a 20 4d 61 78 69 6d 75 | BSZ).X/|* Maximu|
|00001960| 6d 20 74 68 65 6f 72 65 | 74 69 63 61 6c 20 64 69 |m theore|tical di|
|00001970| 73 74 61 6e 63 65 20 62 | 65 74 77 65 65 6e 20 74 |stance b|etween t|
|00001980| 77 6f 20 64 69 73 74 69 | 6e 63 74 20 62 79 74 65 |wo disti|nct byte|
|00001990| 73 20 69 6e 20 74 68 65 | 20 77 69 6e 64 6f 77 2e |s in the| window.|
|000019a0| 0a 58 20 2a 20 41 63 74 | 75 61 6c 20 64 69 73 74 |.X * Act|ual dist|
|000019b0| 61 6e 63 65 73 20 61 72 | 65 20 6c 69 6d 69 74 65 |ances ar|e limite|
|000019c0| 64 20 74 6f 20 62 75 66 | 73 69 7a 65 2e 0a 58 20 |d to buf|size..X |
|000019d0| 2a 2f 0a 58 0a 58 23 64 | 65 66 69 6e 65 20 4e 49 |*/.X.X#d|efine NI|
|000019e0| 4c 20 20 4d 41 58 5f 44 | 49 53 54 0a 58 2f 2a 20 |L  MAX_D|IST.X/* |
|000019f0| 54 61 69 6c 20 6f 66 20 | 68 61 73 68 20 63 68 61 |Tail of |hash cha|
|00001a00| 69 6e 73 20 2a 2f 0a 58 | 0a 58 23 69 66 64 65 66 |ins */.X|.X#ifdef|
|00001a10| 20 44 59 4e 5f 41 4c 4c | 4f 43 0a 58 20 20 20 48 | DYN_ALL|OC.X   H|
|00001a20| 61 73 68 20 66 61 72 20 | 2a 6e 65 78 74 20 3d 20 |ash far |*next = |
|00001a30| 4e 55 4c 4c 3b 0a 58 20 | 20 20 50 6f 73 20 20 66 |NULL;.X |  Pos  f|
|00001a40| 61 72 20 2a 70 72 65 76 | 20 3d 20 4e 55 4c 4c 3b |ar *prev| = NULL;|
|00001a50| 0a 58 23 65 6c 73 65 0a | 58 20 20 20 48 61 73 68 |.X#else.|X   Hash|
|00001a60| 20 66 61 72 20 6e 65 78 | 74 5b 4d 41 58 5f 44 49 | far nex|t[MAX_DI|
|00001a70| 53 54 2b 31 5d 3b 0a 58 | 20 20 20 50 6f 73 20 20 |ST+1];.X|   Pos  |
|00001a80| 66 61 72 20 70 72 65 76 | 5b 4d 41 58 5f 44 49 53 |far prev|[MAX_DIS|
|00001a90| 54 2b 48 41 53 48 5f 53 | 49 5a 45 2b 31 5d 3b 0a |T+HASH_S|IZE+1];.|
|00001aa0| 58 23 65 6e 64 69 66 0a | 58 2f 2a 20 6e 65 78 74 |X#endif.|X/* next|
|00001ab0| 20 69 73 20 61 20 6c 69 | 6e 6b 20 74 6f 20 61 20 | is a li|nk to a |
|00001ac0| 6d 6f 72 65 20 72 65 63 | 65 6e 74 20 73 74 72 69 |more rec|ent stri|
|00001ad0| 6e 67 20 77 69 74 68 20 | 73 61 6d 65 20 68 61 73 |ng with |same has|
|00001ae0| 68 20 69 6e 64 65 78 2c | 20 6f 72 20 74 6f 20 74 |h index,| or to t|
|00001af0| 68 65 20 68 65 61 64 0a | 58 20 2a 20 6f 66 20 61 |he head.|X * of a|
|00001b00| 20 68 61 73 68 20 74 61 | 62 6c 65 20 63 68 61 69 | hash ta|ble chai|
|00001b10| 6e 20 69 66 20 74 68 65 | 72 65 20 69 73 20 6e 6f |n if the|re is no|
|00001b20| 20 73 75 63 68 20 73 74 | 72 69 6e 67 2e 20 6e 65 | such st|ring. ne|
|00001b30| 78 74 5b 4e 49 4c 5d 20 | 69 73 20 75 73 65 64 20 |xt[NIL] |is used |
|00001b40| 74 6f 0a 58 20 2a 20 61 | 76 6f 69 64 20 65 78 74 |to.X * a|void ext|
|00001b50| 72 61 20 63 68 65 63 6b | 73 2e 20 6e 65 78 74 5b |ra check|s. next[|
|00001b60| 73 5d 20 69 73 20 4e 49 | 4c 20 69 66 20 73 74 72 |s] is NI|L if str|
|00001b70| 69 6e 67 20 73 20 69 73 | 20 6e 6f 74 20 79 65 74 |ing s is| not yet|
|00001b80| 20 69 6e 20 74 68 65 20 | 64 69 63 74 69 6f 6e 61 | in the |dictiona|
|00001b90| 72 79 0a 58 20 2a 0a 58 | 20 2a 20 70 72 65 76 20 |ry.X *.X| * prev |
|00001ba0| 69 73 20 61 20 6c 69 6e | 6b 20 74 6f 20 61 6e 20 |is a lin|k to an |
|00001bb0| 6f 6c 64 65 72 20 73 74 | 72 69 6e 67 20 77 69 74 |older st|ring wit|
|00001bc0| 68 20 73 61 6d 65 20 68 | 61 73 68 20 69 6e 64 65 |h same h|ash inde|
|00001bd0| 78 20 28 66 69 72 73 74 | 20 4d 41 58 5f 44 49 53 |x (first| MAX_DIS|
|00001be0| 54 0a 58 20 2a 20 76 61 | 6c 75 65 73 29 20 6f 72 |T.X * va|lues) or|
|00001bf0| 20 68 65 61 64 20 6f 66 | 20 68 61 73 68 20 63 68 | head of| hash ch|
|00001c00| 61 69 6e 20 28 6c 61 73 | 74 20 48 41 53 48 5f 53 |ain (las|t HASH_S|
|00001c10| 49 5a 45 20 76 61 6c 75 | 65 73 29 2e 20 70 72 65 |IZE valu|es). pre|
|00001c20| 76 5b 4e 49 4c 5d 20 69 | 73 20 75 73 65 64 0a 58 |v[NIL] i|s used.X|
|00001c30| 20 2a 20 74 6f 20 61 76 | 6f 69 64 20 65 78 74 72 | * to av|oid extr|
|00001c40| 61 20 63 68 65 63 6b 73 | 2e 0a 58 20 2a 2f 0a 58 |a checks|..X */.X|
|00001c50| 23 64 65 66 69 6e 65 20 | 6d 61 74 63 68 5f 68 65 |#define |match_he|
|00001c60| 61 64 20 28 70 72 65 76 | 2b 28 4d 41 58 5f 44 49 |ad (prev|+(MAX_DI|
|00001c70| 53 54 2b 31 29 29 0a 58 | 0a 48 61 73 68 20 6e 65 |ST+1)).X|.Hash ne|
|00001c80| 61 72 20 69 6e 73 5f 68 | 3b 20 20 2f 2a 20 68 61 |ar ins_h|;  /* ha|
|00001c90| 73 68 20 69 6e 64 65 78 | 20 6f 66 20 73 74 72 69 |sh index| of stri|
|00001ca0| 6e 67 20 74 6f 20 62 65 | 20 69 6e 73 65 72 74 65 |ng to be| inserte|
|00001cb0| 64 2e 20 2a 2f 0a 58 0a | 69 6e 74 20 6e 65 61 72 |d. */.X.|int near|
|00001cc0| 20 68 5f 73 68 69 66 74 | 3b 0a 58 2f 2a 20 4e 75 | h_shift|;.X/* Nu|
|00001cd0| 6d 62 65 72 20 6f 66 20 | 62 69 74 73 20 62 79 20 |mber of |bits by |
|00001ce0| 77 68 69 63 68 20 69 6e | 73 5f 68 20 6d 75 73 74 |which in|s_h must|
|00001cf0| 20 62 65 20 73 68 69 66 | 74 65 64 20 61 74 20 65 | be shif|ted at e|
|00001d00| 61 63 68 0a 58 20 2a 20 | 69 6e 70 75 74 20 73 74 |ach.X * |input st|
|00001d10| 65 70 2e 20 49 74 20 6d | 75 73 74 20 62 65 20 73 |ep. It m|ust be s|
|00001d20| 75 63 68 20 74 68 61 74 | 20 61 66 74 65 72 20 6d |uch that| after m|
|00001d30| 69 6e 5f 6d 61 74 63 68 | 5f 6c 65 6e 67 74 68 20 |in_match|_length |
|00001d40| 73 74 65 70 73 2c 20 74 | 68 65 20 6f 6c 64 65 73 |steps, t|he oldes|
|00001d50| 74 0a 58 20 2a 20 62 79 | 74 65 20 6e 6f 20 6c 6f |t.X * by|te no lo|
|00001d60| 6e 67 65 72 20 74 61 6b | 65 73 20 70 61 72 74 20 |nger tak|es part |
|00001d70| 69 6e 20 74 68 65 20 68 | 61 73 68 20 6b 65 79 2c |in the h|ash key,|
|00001d80| 20 74 68 61 74 20 69 73 | 3a 0a 58 20 2a 20 20 20 | that is|:.X *   |
|00001d90| 68 5f 73 68 69 66 74 20 | 2a 20 6d 69 6e 5f 6d 61 |h_shift |* min_ma|
|00001da0| 74 63 68 5f 6c 65 6e 67 | 74 68 20 3e 3d 20 48 41 |tch_leng|th >= HA|
|00001db0| 53 48 5f 42 49 54 53 0a | 58 20 2a 2f 0a 58 0a 4d |SH_BITS.|X */.X.M|
|00001dc0| 41 54 43 48 20 2a 6d 61 | 5f 62 75 66 20 3d 20 4e |ATCH *ma|_buf = N|
|00001dd0| 55 4c 4c 3b 0a 58 2f 2a | 20 42 75 66 66 65 72 20 |ULL;.X/*| Buffer |
|00001de0| 75 73 65 64 20 74 6f 20 | 73 70 65 65 64 20 75 70 |used to |speed up|
|00001df0| 20 72 65 61 64 69 6e 67 | 2f 77 72 69 74 69 6e 67 | reading|/writing|
|00001e00| 20 74 6f 2f 66 72 6f 6d | 20 74 65 6d 70 20 66 69 | to/from| temp fi|
|00001e10| 6c 65 20 2a 2f 0a 58 23 | 64 65 66 69 6e 65 20 4d |le */.X#|define M|
|00001e20| 41 5f 42 55 46 45 4e 44 | 20 28 6d 61 5f 62 75 66 |A_BUFEND| (ma_buf|
|00001e30| 2b 4d 41 5f 42 55 46 53 | 49 5a 45 29 0a 58 0a 4d |+MA_BUFS|IZE).X.M|
|00001e40| 41 54 43 48 20 2a 6d 61 | 3b 0a 58 2f 2a 20 50 6f |ATCH *ma|;.X/* Po|
|00001e50| 69 6e 74 65 72 20 74 6f | 20 74 68 65 20 6d 6f 73 |inter to| the mos|
|00001e60| 74 20 72 65 63 65 6e 74 | 20 6d 61 74 63 68 2e 20 |t recent| match. |
|00001e70| 2a 2f 0a 58 0a 69 6e 74 | 20 6e 65 61 72 20 73 74 |*/.X.int| near st|
|00001e80| 61 72 74 5f 6c 65 6e 67 | 74 68 3b 0a 58 2f 2a 20 |art_leng|th;.X/* |
|00001e90| 4d 61 74 63 68 65 73 20 | 6e 6f 74 20 67 72 65 61 |Matches |not grea|
|00001ea0| 74 65 72 20 74 68 61 6e | 20 74 68 69 73 20 61 72 |ter than| this ar|
|00001eb0| 65 20 64 69 73 63 61 72 | 64 65 64 2e 20 54 68 69 |e discar|ded. Thi|
|00001ec0| 73 20 69 73 20 75 73 65 | 64 20 69 6e 20 74 68 65 |s is use|d in the|
|00001ed0| 20 6c 61 7a 79 20 6d 61 | 74 63 68 0a 58 20 2a 20 | lazy ma|tch.X * |
|00001ee0| 65 76 61 6c 75 61 74 69 | 6f 6e 2e 20 49 66 20 73 |evaluati|on. If s|
|00001ef0| 74 61 72 74 5f 6c 65 6e | 67 74 68 20 3e 20 31 2c |tart_len|gth > 1,|
|00001f00| 20 6d 61 20 69 73 20 61 | 20 76 61 6c 69 64 20 67 | ma is a| valid g|
|00001f10| 75 65 73 73 20 6f 66 20 | 6c 65 6e 67 74 68 20 73 |uess of |length s|
|00001f20| 74 61 72 74 5f 6c 65 6e | 67 74 68 0a 58 20 2a 20 |tart_len|gth.X * |
|00001f30| 61 6e 64 20 63 74 5f 74 | 61 6c 6c 79 20 68 61 73 |and ct_t|ally has|
|00001f40| 20 6e 6f 74 20 79 65 74 | 20 62 65 65 6e 20 63 61 | not yet| been ca|
|00001f50| 6c 6c 65 64 2e 0a 58 20 | 2a 2f 0a 58 0a 58 20 20 |lled..X |*/.X.X  |
|00001f60| 20 20 20 20 20 20 69 6e | 74 20 6e 65 61 72 20 73 |      in|t near s|
|00001f70| 74 72 73 74 61 72 74 3b | 20 20 20 20 20 20 2f 2a |trstart;|      /*|
|00001f80| 20 73 74 61 72 74 20 6f | 66 20 73 74 72 69 6e 67 | start o|f string|
|00001f90| 20 74 6f 20 69 6e 73 65 | 72 74 20 2a 2f 0a 58 20 | to inse|rt */.X |
|00001fa0| 20 20 20 20 20 20 20 69 | 6e 74 20 6e 65 61 72 20 |       i|nt near |
|00001fb0| 73 74 72 73 69 7a 65 3b | 20 20 20 20 20 20 20 2f |strsize;|       /|
|00001fc0| 2a 20 6c 65 6e 67 74 68 | 20 6f 66 20 73 74 72 69 |* length| of stri|
|00001fd0| 6e 67 20 74 6f 20 69 6e | 73 65 72 74 20 2a 2f 0a |ng to in|sert */.|
|00001fe0| 58 20 20 20 20 20 20 20 | 20 69 6e 74 20 6e 65 61 |X       | int nea|
|00001ff0| 72 20 6d 61 74 63 68 5f | 6c 65 6e 67 74 68 3b 20 |r match_|length; |
|00002000| 20 2f 2a 20 6c 65 6e 67 | 74 68 20 6f 66 20 63 75 | /* leng|th of cu|
|00002010| 72 72 65 6e 74 20 62 65 | 73 74 20 6d 61 74 63 68 |rrent be|st match|
|00002020| 20 2a 2f 0a 58 20 20 20 | 20 20 20 20 20 69 6e 74 | */.X   |     int|
|00002030| 20 6e 65 61 72 20 62 75 | 66 73 69 7a 65 3b 20 20 | near bu|fsize;  |
|00002040| 20 20 20 20 20 2f 2a 20 | 23 20 6f 66 20 73 6c 6f |     /* |# of slo|
|00002050| 74 73 20 69 6e 20 77 69 | 6e 64 6f 77 20 2a 2f 0a |ts in wi|ndow */.|
|00002060| 58 20 20 20 20 20 20 20 | 20 69 6e 74 20 6e 65 61 |X       | int nea|
|00002070| 72 20 63 68 65 63 6b 70 | 6f 69 6e 74 3b 20 20 20 |r checkp|oint;   |
|00002080| 20 2f 2a 20 6c 6f 6f 6b | 20 66 6f 72 20 6e 65 77 | /* look| for new|
|00002090| 20 6d 61 74 63 68 20 61 | 74 20 74 68 69 73 20 70 | match a|t this p|
|000020a0| 6f 69 6e 74 20 2a 2f 0a | 73 74 61 74 69 63 20 20 |oint */.|static  |
|000020b0| 69 6e 74 20 20 20 20 20 | 20 69 6e 73 65 72 74 5f |int     | insert_|
|000020c0| 70 6f 69 6e 74 3b 20 20 | 2f 2a 20 70 6f 73 69 74 |point;  |/* posit|
|000020d0| 69 6f 6e 20 6f 66 20 6e | 65 78 74 20 69 6e 70 75 |ion of n|ext inpu|
|000020e0| 74 20 62 75 66 66 65 72 | 20 2a 2f 0a 58 0a 73 74 |t buffer| */.X.st|
|000020f0| 61 74 69 63 20 20 69 6e | 74 20 20 20 20 20 20 6d |atic  in|t      m|
|00002100| 61 78 5f 6c 61 7a 79 5f | 6d 61 74 63 68 3b 0a 58 |ax_lazy_|match;.X|
|00002110| 2f 2a 20 57 65 20 74 72 | 79 20 6c 61 7a 79 20 65 |/* We tr|y lazy e|
|00002120| 76 61 6c 75 61 74 69 6f | 6e 20 6f 6e 6c 79 20 66 |valuatio|n only f|
|00002130| 6f 72 20 6d 61 74 63 68 | 65 73 20 6f 66 20 6c 65 |or match|es of le|
|00002140| 6e 67 74 68 20 32 2e 2e | 6d 61 78 5f 6c 61 7a 79 |ngth 2..|max_lazy|
|00002150| 5f 6d 61 74 63 68 2c 20 | 74 6f 0a 58 20 2a 20 73 |_match, |to.X * s|
|00002160| 70 65 65 64 20 75 70 20 | 74 68 65 20 69 6d 70 6c |peed up |the impl|
|00002170| 6f 73 69 6f 6e 2e 20 57 | 65 20 75 73 65 20 30 20 |osion. W|e use 0 |
|00002180| 66 6f 72 20 6d 61 78 69 | 6d 75 6d 20 73 70 65 65 |for maxi|mum spee|
|00002190| 64 2c 20 30 2e 39 2a 4d | 41 58 5f 4d 41 54 43 48 |d, 0.9*M|AX_MATCH|
|000021a0| 5f 4c 45 4e 47 54 48 0a | 58 20 2a 20 66 6f 72 20 |_LENGTH.|X * for |
|000021b0| 6d 61 78 69 6d 75 6d 20 | 63 6f 6d 70 72 65 73 73 |maximum |compress|
|000021c0| 69 6f 6e 2e 0a 58 20 2a | 2f 0a 58 0a 58 20 20 20 |ion..X *|/.X.X   |
|000021d0| 20 20 20 20 20 69 6e 74 | 20 6e 65 61 72 20 6d 61 |     int| near ma|
|000021e0| 78 5f 63 68 61 69 6e 5f | 6c 65 6e 67 74 68 3b 0a |x_chain_|length;.|
|000021f0| 58 2f 2a 20 54 6f 20 73 | 70 65 65 64 20 75 70 20 |X/* To s|peed up |
|00002200| 69 6d 70 6c 6f 73 69 6f | 6e 2c 20 68 61 73 68 20 |implosio|n, hash |
|00002210| 63 68 61 69 6e 73 20 61 | 72 65 20 74 72 75 6e 63 |chains a|re trunc|
|00002220| 61 74 65 64 20 74 6f 20 | 74 68 69 73 20 6c 65 6e |ated to |this len|
|00002230| 67 74 68 2e 0a 58 20 2a | 20 41 20 68 69 67 68 65 |gth..X *| A highe|
|00002240| 72 20 6c 69 6d 69 74 20 | 69 6d 70 72 6f 76 65 73 |r limit |improves|
|00002250| 20 63 6f 6d 70 72 65 73 | 73 69 6f 6e 20 72 61 74 | compres|sion rat|
|00002260| 69 6f 20 62 75 74 20 64 | 65 67 72 61 64 65 73 20 |io but d|egrades |
|00002270| 74 68 65 20 73 70 65 65 | 64 2e 0a 58 20 2a 20 57 |the spee|d..X * W|
|00002280| 65 20 75 73 65 20 34 30 | 20 66 6f 72 20 6d 61 78 |e use 40| for max|
|00002290| 69 6d 75 6d 20 73 70 65 | 65 64 2c 20 39 36 30 20 |imum spe|ed, 960 |
|000022a0| 66 6f 72 20 6d 61 78 69 | 6d 75 6d 20 63 6f 6d 70 |for maxi|mum comp|
|000022b0| 72 65 73 73 69 6f 6e 2e | 20 56 61 6c 75 65 73 0a |ression.| Values.|
|000022c0| 58 20 2a 20 62 65 6c 6f | 77 20 32 30 20 61 72 65 |X * belo|w 20 are|
|000022d0| 20 6e 6f 74 20 72 65 63 | 6f 6d 6d 65 6e 64 65 64 | not rec|ommended|
|000022e0| 2e 0a 58 20 2a 2f 0a 58 | 0a 58 2f 2a 20 56 61 6c |..X */.X|.X/* Val|
|000022f0| 75 65 73 20 66 6f 72 20 | 6d 61 78 5f 6c 61 7a 79 |ues for |max_lazy|
|00002300| 5f 6d 61 74 63 68 20 61 | 6e 64 20 6d 61 78 5f 63 |_match a|nd max_c|
|00002310| 68 61 69 6e 5f 6c 65 6e | 67 74 68 2c 20 64 65 70 |hain_len|gth, dep|
|00002320| 65 6e 64 69 6e 67 20 6f | 6e 20 74 68 65 20 64 65 |ending o|n the de|
|00002330| 73 69 72 65 64 0a 58 20 | 2a 20 70 61 63 6b 20 6c |sired.X |* pack l|
|00002340| 65 76 65 6c 20 28 30 2e | 2e 39 29 2e 20 54 68 65 |evel (0.|.9). The|
|00002350| 20 76 61 6c 75 65 73 20 | 67 69 76 65 6e 20 62 65 | values |given be|
|00002360| 6c 6f 77 20 68 61 76 65 | 20 62 65 65 6e 20 74 75 |low have| been tu|
|00002370| 6e 65 64 20 74 6f 20 65 | 78 63 6c 75 64 65 0a 58 |ned to e|xclude.X|
|00002380| 20 2a 20 77 6f 72 73 74 | 20 63 61 73 65 20 70 65 | * worst| case pe|
|00002390| 72 66 6f 72 6d 61 6e 63 | 65 20 66 6f 72 20 70 61 |rformanc|e for pa|
|000023a0| 74 68 6f 6c 6f 67 69 63 | 61 6c 20 66 69 6c 65 73 |thologic|al files|
|000023b0| 2e 20 42 65 74 74 65 72 | 20 76 61 6c 75 65 73 20 |. Better| values |
|000023c0| 6d 61 79 20 62 65 0a 58 | 20 2a 20 66 6f 75 6e 64 |may be.X| * found|
|000023d0| 20 66 6f 72 20 73 70 65 | 63 69 66 69 63 20 66 69 | for spe|cific fi|
|000023e0| 6c 65 73 2e 20 4e 6f 74 | 65 20 74 68 61 74 20 74 |les. Not|e that t|
|000023f0| 68 65 20 63 75 72 72 65 | 6e 74 20 61 6c 67 6f 72 |he curre|nt algor|
|00002400| 69 74 68 6d 20 72 65 71 | 75 69 72 65 73 20 0a 58 |ithm req|uires .X|
|00002410| 20 2a 20 6d 61 78 5f 6c | 61 7a 79 20 3e 3d 20 32 | * max_l|azy >= 2|
|00002420| 2e 0a 58 20 2a 2f 0a 74 | 79 70 65 64 65 66 20 73 |..X */.t|ypedef s|
|00002430| 74 72 75 63 74 20 63 6f | 6e 66 69 67 20 7b 0a 58 |truct co|nfig {.X|
|00002440| 20 20 20 69 6e 74 20 6d | 61 78 5f 6c 61 7a 79 3b |   int m|ax_lazy;|
|00002450| 0a 58 20 20 20 69 6e 74 | 20 6d 61 78 5f 63 68 61 |.X   int| max_cha|
|00002460| 69 6e 3b 0a 58 7d 20 63 | 6f 6e 66 69 67 3b 0a 58 |in;.X} c|onfig;.X|
|00002470| 0a 73 74 61 74 69 63 20 | 63 6f 6e 66 69 67 20 63 |.static |config c|
|00002480| 6f 6e 66 69 67 75 72 61 | 74 69 6f 6e 5f 74 61 62 |onfigura|tion_tab|
|00002490| 6c 65 5b 31 30 5d 20 3d | 20 7b 0a 58 2f 2a 20 30 |le[10] =| {.X/* 0|
|000024a0| 20 2a 2f 20 7b 32 2c 20 | 20 20 20 20 20 20 20 20 | */ {2, |        |
|000024b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 4d 41 58 5f |        |    MAX_|
|000024c0| 4d 41 54 43 48 5f 4c 45 | 4e 47 54 48 2f 38 7d 2c |MATCH_LE|NGTH/8},|
|000024d0| 20 2f 2a 20 6d 61 78 69 | 6d 75 6d 20 73 70 65 65 | /* maxi|mum spee|
|000024e0| 64 20 2a 2f 0a 58 2f 2a | 20 31 20 2a 2f 20 7b 34 |d */.X/*| 1 */ {4|
|000024f0| 2c 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |,       |        |
|00002500| 20 20 20 20 20 20 4d 41 | 58 5f 4d 41 54 43 48 5f |      MA|X_MATCH_|
|00002510| 4c 45 4e 47 54 48 2f 34 | 7d 2c 0a 58 2f 2a 20 32 |LENGTH/4|},.X/* 2|
|00002520| 20 2a 2f 20 7b 35 2c 20 | 20 20 20 20 20 20 20 20 | */ {5, |        |
|00002530| 20 20 20 20 20 20 20 20 | 20 20 20 20 4d 41 58 5f |        |    MAX_|
|00002540| 4d 41 54 43 48 5f 4c 45 | 4e 47 54 48 2f 32 7d 2c |MATCH_LE|NGTH/2},|
|00002550| 0a 58 2f 2a 20 33 20 2a | 2f 20 7b 4d 41 58 5f 4d |.X/* 3 *|/ {MAX_M|
|00002560| 41 54 43 48 5f 4c 45 4e | 47 54 48 2f 31 36 2c 20 |ATCH_LEN|GTH/16, |
|00002570| 20 20 4d 41 58 5f 4d 41 | 54 43 48 5f 4c 45 4e 47 |  MAX_MA|TCH_LENG|
|00002580| 54 48 2f 32 7d 2c 0a 58 | 2f 2a 20 34 20 2a 2f 20 |TH/2},.X|/* 4 */ |
|00002590| 7b 4d 41 58 5f 4d 41 54 | 43 48 5f 4c 45 4e 47 54 |{MAX_MAT|CH_LENGT|
|000025a0| 48 2f 31 36 2c 20 20 20 | 33 2a 4d 41 58 5f 4d 41 |H/16,   |3*MAX_MA|
|000025b0| 54 43 48 5f 4c 45 4e 47 | 54 48 2f 34 7d 2c 0a 58 |TCH_LENG|TH/4},.X|
|000025c0| 2f 2a 20 35 20 2a 2f 20 | 7b 4d 41 58 5f 4d 41 54 |/* 5 */ |{MAX_MAT|
|000025d0| 43 48 5f 4c 45 4e 47 54 | 48 2f 31 36 2c 20 20 20 |CH_LENGT|H/16,   |
|000025e0| 4d 41 58 5f 4d 41 54 43 | 48 5f 4c 45 4e 47 54 48 |MAX_MATC|H_LENGTH|
|000025f0| 7d 2c 0a 58 2f 2a 20 36 | 20 2a 2f 20 7b 4d 41 58 |},.X/* 6| */ {MAX|
|00002600| 5f 4d 41 54 43 48 5f 4c | 45 4e 47 54 48 2f 31 36 |_MATCH_L|ENGTH/16|
|00002610| 2c 20 20 20 33 2a 4d 41 | 58 5f 4d 41 54 43 48 5f |,   3*MA|X_MATCH_|
|00002620| 4c 45 4e 47 54 48 2f 32 | 7d 2c 0a 58 2f 2a 20 37 |LENGTH/2|},.X/* 7|
|00002630| 20 2a 2f 20 7b 4d 41 58 | 5f 4d 41 54 43 48 5f 4c | */ {MAX|_MATCH_L|
|00002640| 45 4e 47 54 48 2f 31 36 | 2c 20 20 20 32 2a 4d 41 |ENGTH/16|,   2*MA|
|00002650| 58 5f 4d 41 54 43 48 5f | 4c 45 4e 47 54 48 7d 2c |X_MATCH_|LENGTH},|
|00002660| 0a 58 2f 2a 20 38 20 2a | 2f 20 7b 39 2a 4d 41 58 |.X/* 8 *|/ {9*MAX|
|00002670| 5f 4d 41 54 43 48 5f 4c | 45 4e 47 54 48 2f 31 30 |_MATCH_L|ENGTH/10|
|00002680| 2c 20 32 2a 4d 41 58 5f | 4d 41 54 43 48 5f 4c 45 |, 2*MAX_|MATCH_LE|
|00002690| 4e 47 54 48 7d 2c 0a 58 | 2f 2a 20 39 20 2a 2f 20 |NGTH},.X|/* 9 */ |
|000026a0| 7b 39 2a 4d 41 58 5f 4d | 41 54 43 48 5f 4c 45 4e |{9*MAX_M|ATCH_LEN|
|000026b0| 47 54 48 2f 31 30 2c 20 | 33 2a 4d 41 58 5f 4d 41 |GTH/10, |3*MAX_MA|
|000026c0| 54 43 48 5f 4c 45 4e 47 | 54 48 7d 7d 3b 20 2f 2a |TCH_LENG|TH}}; /*|
|000026d0| 20 6d 61 78 69 6d 75 6d | 20 63 6f 6d 70 72 65 73 | maximum| compres|
|000026e0| 73 69 6f 6e 20 2a 2f 0a | 58 0a 58 0a 58 23 64 65 |sion */.|X.X.X#de|
|000026f0| 66 69 6e 65 20 4d 49 4e | 28 61 2c 62 29 20 28 28 |fine MIN|(a,b) ((|
|00002700| 61 29 20 3c 3d 20 28 62 | 29 20 3f 20 28 61 29 20 |a) <= (b|) ? (a) |
|00002710| 3a 20 28 62 29 29 0a 58 | 2f 2a 20 54 68 65 20 61 |: (b)).X|/* The a|
|00002720| 72 67 75 6d 65 6e 74 73 | 20 6d 75 73 74 20 6e 6f |rguments| must no|
|00002730| 74 20 68 61 76 65 20 73 | 69 64 65 20 65 66 66 65 |t have s|ide effe|
|00002740| 63 74 73 2e 20 2a 2f 0a | 58 0a 58 23 64 65 66 69 |cts. */.|X.X#defi|
|00002750| 6e 65 20 45 51 55 41 4c | 20 30 0a 58 2f 2a 20 72 |ne EQUAL| 0.X/* r|
|00002760| 65 73 75 6c 74 20 6f 66 | 20 73 74 72 6e 63 6d 70 |esult of| strncmp|
|00002770| 20 66 6f 72 20 65 71 75 | 61 6c 20 73 74 72 69 6e | for equ|al strin|
|00002780| 67 73 20 2a 2f 0a 58 0a | 58 2f 2a 20 20 50 72 6f |gs */.X.|X/*  Pro|
|00002790| 74 6f 74 79 70 65 73 20 | 66 6f 72 20 6c 6f 63 61 |totypes |for loca|
|000027a0| 6c 20 66 75 6e 63 74 69 | 6f 6e 73 20 2a 2f 0a 58 |l functi|ons */.X|
|000027b0| 0a 73 74 61 74 69 63 20 | 76 6f 69 64 20 20 20 73 |.static |void   s|
|000027c0| 65 74 5f 6d 69 6e 5f 6d | 61 74 63 68 5f 6c 65 6e |et_min_m|atch_len|
|000027d0| 67 74 68 20 4f 46 20 28 | 28 55 5f 43 48 41 52 20 |gth OF (|(U_CHAR |
|000027e0| 2a 62 6c 6f 63 6b 2c 20 | 55 5f 49 4e 54 20 63 6f |*block, |U_INT co|
|000027f0| 75 6e 74 29 29 3b 0a 58 | 20 20 20 20 20 20 20 49 |unt));.X|       I|
|00002800| 6d 70 45 72 72 20 77 72 | 69 74 65 5f 6d 61 74 63 |mpErr wr|ite_matc|
|00002810| 68 20 4f 46 20 28 28 49 | 50 6f 73 20 6d 61 5f 73 |h OF ((I|Pos ma_s|
|00002820| 74 61 72 74 2c 20 69 6e | 74 20 6d 61 5f 6c 65 6e |tart, in|t ma_len|
|00002830| 67 74 68 29 29 3b 0a 58 | 20 20 20 20 20 20 20 49 |gth));.X|       I|
|00002840| 50 6f 73 20 20 20 6c 6f | 6e 67 65 73 74 5f 6d 61 |Pos   lo|ngest_ma|
|00002850| 74 63 68 20 4f 46 20 28 | 28 49 50 6f 73 20 63 75 |tch OF (|(IPos cu|
|00002860| 72 5f 6d 61 74 63 68 29 | 29 3b 0a 58 20 20 20 20 |r_match)|);.X    |
|00002870| 20 20 20 49 6d 70 45 72 | 72 20 6c 6d 5f 70 72 6f |   ImpEr|r lm_pro|
|00002880| 63 65 73 73 20 4f 46 20 | 28 28 55 5f 49 4e 54 20 |cess OF |((U_INT |
|00002890| 63 6f 75 6e 74 29 29 3b | 0a 58 0a 58 2f 2a 2a 2a |count));|.X.X/***|
|000028a0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000028b0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000028c0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000028d0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000028e0| 2a 2a 2a 2a 0a 58 20 2a | 0a 58 20 2a 20 49 6e 69 |****.X *|.X * Ini|
|000028f0| 74 69 61 6c 69 7a 65 20 | 74 68 65 20 22 6c 6f 6e |tialize |the "lon|
|00002900| 67 65 73 74 20 6d 61 74 | 63 68 22 20 72 6f 75 74 |gest mat|ch" rout|
|00002910| 69 6e 65 73 20 66 6f 72 | 20 61 20 6e 65 77 20 66 |ines for| a new f|
|00002920| 69 6c 65 2e 0a 58 20 2a | 20 54 68 65 20 67 6c 6f |ile..X *| The glo|
|00002930| 62 61 6c 20 76 61 72 69 | 61 62 6c 65 20 66 64 20 |bal vari|able fd |
|00002940| 69 73 20 61 6e 20 69 6d | 70 6c 69 63 69 74 20 70 |is an im|plicit p|
|00002950| 61 72 61 6d 65 74 65 72 | 2e 0a 58 20 2a 2f 0a 49 |arameter|..X */.I|
|00002960| 6d 70 45 72 72 20 6c 6d | 5f 69 6e 69 74 20 28 70 |mpErr lm|_init (p|
|00002970| 61 63 6b 5f 6c 65 76 65 | 6c 29 0a 58 20 20 20 20 |ack_leve|l).X    |
|00002980| 69 6e 74 20 70 61 63 6b | 5f 6c 65 76 65 6c 3b 20 |int pack|_level; |
|00002990| 2f 2a 20 30 3a 20 62 65 | 73 74 20 73 70 65 65 64 |/* 0: be|st speed|
|000029a0| 2c 20 39 3a 20 62 65 73 | 74 20 63 6f 6d 70 72 65 |, 9: bes|t compre|
|000029b0| 73 73 69 6f 6e 2c 20 6f | 74 68 65 72 3a 20 64 65 |ssion, o|ther: de|
|000029c0| 66 61 75 6c 74 20 2a 2f | 0a 58 7b 0a 58 20 20 20 |fault */|.X{.X   |
|000029d0| 20 72 65 67 69 73 74 65 | 72 20 69 6e 74 20 69 3b | registe|r int i;|
|000029e0| 0a 58 0a 58 20 20 20 20 | 2f 2a 20 56 61 6c 69 64 |.X.X    |/* Valid|
|000029f0| 61 74 65 20 74 68 65 20 | 61 72 67 75 6d 65 6e 74 |ate the |argument|
|00002a00| 73 20 2a 2f 0a 58 20 20 | 20 20 62 75 66 73 69 7a |s */.X  |  bufsiz|
|00002a10| 65 20 3d 20 66 64 2e 66 | 64 5f 62 75 66 73 69 7a |e = fd.f|d_bufsiz|
|00002a20| 65 3b 0a 58 20 20 20 20 | 73 74 72 73 69 7a 65 20 |e;.X    |strsize |
|00002a30| 3d 20 4d 49 4e 20 28 66 | 64 2e 66 64 5f 73 74 72 |= MIN (f|d.fd_str|
|00002a40| 73 69 7a 65 2c 20 4d 41 | 58 5f 4d 41 54 43 48 5f |size, MA|X_MATCH_|
|00002a50| 4c 45 4e 47 54 48 29 3b | 0a 58 20 20 20 20 69 66 |LENGTH);|.X    if|
|00002a60| 20 28 62 75 66 73 69 7a | 65 20 3e 20 57 53 49 5a | (bufsiz|e > WSIZ|
|00002a70| 45 29 20 20 20 20 20 20 | 20 20 20 20 72 65 74 75 |E)      |    retu|
|00002a80| 72 6e 20 49 4d 5f 42 41 | 44 41 52 47 3b 0a 58 20 |rn IM_BA|DARG;.X |
|00002a90| 20 20 20 69 66 20 28 62 | 75 66 73 69 7a 65 20 3c |   if (b|ufsize <|
|00002aa0| 20 32 20 2a 20 73 74 72 | 73 69 7a 65 29 20 20 20 | 2 * str|size)   |
|00002ab0| 20 72 65 74 75 72 6e 20 | 49 4d 5f 42 41 44 41 52 | return |IM_BADAR|
|00002ac0| 47 3b 0a 58 20 20 20 20 | 69 66 20 28 70 61 63 6b |G;.X    |if (pack|
|00002ad0| 5f 6c 65 76 65 6c 20 3c | 20 30 20 7c 7c 20 70 61 |_level <| 0 || pa|
|00002ae0| 63 6b 5f 6c 65 76 65 6c | 20 3e 20 39 29 20 72 65 |ck_level| > 9) re|
|00002af0| 74 75 72 6e 20 49 4d 5f | 42 41 44 41 52 47 3b 0a |turn IM_|BADARG;.|
|00002b00| 58 0a 58 20 20 20 20 2f | 2a 20 4d 61 6b 65 20 73 |X.X    /|* Make s|
|00002b10| 75 72 65 20 22 62 75 66 | 73 69 7a 65 22 20 69 73 |ure "buf|size" is|
|00002b20| 20 61 20 70 6f 77 65 72 | 20 6f 66 20 32 20 2a 2f | a power| of 2 */|
|00002b30| 0a 58 20 20 20 20 69 66 | 20 28 28 62 75 66 73 69 |.X    if| ((bufsi|
|00002b40| 7a 65 20 26 20 28 62 75 | 66 73 69 7a 65 20 2d 20 |ze & (bu|fsize - |
|00002b50| 31 29 29 20 21 3d 20 30 | 29 20 72 65 74 75 72 6e |1)) != 0|) return|
|00002b60| 20 49 4d 5f 42 41 44 41 | 52 47 3b 0a 58 0a 58 20 | IM_BADA|RG;.X.X |
|00002b70| 20 20 20 2f 2a 20 55 73 | 65 20 64 79 6e 61 6d 69 |   /* Us|e dynami|
|00002b80| 63 20 61 6c 6c 6f 63 61 | 74 69 6f 6e 20 69 66 20 |c alloca|tion if |
|00002b90| 63 6f 6d 70 69 6c 65 72 | 20 64 6f 65 73 20 6e 6f |compiler| does no|
|00002ba0| 74 20 6c 69 6b 65 20 62 | 69 67 20 73 74 61 74 69 |t like b|ig stati|
|00002bb0| 63 20 61 72 72 61 79 73 | 3a 20 2a 2f 0a 58 23 69 |c arrays|: */.X#i|
|00002bc0| 66 64 65 66 20 44 59 4e | 5f 41 4c 4c 4f 43 0a 58 |fdef DYN|_ALLOC.X|
|00002bd0| 20 20 20 20 69 66 20 28 | 70 72 65 76 20 3d 3d 20 |    if (|prev == |
|00002be0| 4e 55 4c 4c 29 20 7b 0a | 58 20 20 20 20 20 20 20 |NULL) {.|X       |
|00002bf0| 6e 65 78 74 20 3d 20 28 | 48 61 73 68 20 66 61 72 |next = (|Hash far|
|00002c00| 2a 29 66 61 72 6d 61 6c | 6c 6f 63 28 28 55 5f 49 |*)farmal|loc((U_I|
|00002c10| 4e 54 29 28 4d 41 58 5f | 44 49 53 54 2b 39 29 2a |NT)(MAX_|DIST+9)*|
|00002c20| 73 69 7a 65 6f 66 28 48 | 61 73 68 29 29 3b 0a 58 |sizeof(H|ash));.X|
|00002c30| 20 20 20 20 20 20 20 70 | 72 65 76 20 3d 20 28 50 |       p|rev = (P|
|00002c40| 6f 73 20 66 61 72 2a 29 | 20 66 61 72 6d 61 6c 6c |os far*)| farmall|
|00002c50| 6f 63 28 28 55 5f 49 4e | 54 29 28 4d 41 58 5f 44 |oc((U_IN|T)(MAX_D|
|00002c60| 49 53 54 2b 48 41 53 48 | 5f 53 49 5a 45 2b 39 29 |IST+HASH|_SIZE+9)|
|00002c70| 2a 73 69 7a 65 6f 66 28 | 50 6f 73 29 29 3b 0a 58 |*sizeof(|Pos));.X|
|00002c80| 20 20 20 20 20 20 20 2f | 2a 20 57 65 20 61 6c 6c |       /|* We all|
|00002c90| 6f 63 61 74 65 20 31 36 | 20 65 78 74 72 61 20 62 |ocate 16| extra b|
|00002ca0| 79 74 65 73 20 66 6f 72 | 20 74 68 65 20 6e 6f 72 |ytes for| the nor|
|00002cb0| 6d 61 6c 69 7a 61 74 69 | 6f 6e 20 75 6e 64 65 72 |malizati|on under|
|00002cc0| 20 4d 53 44 4f 53 20 2a | 2f 0a 58 20 20 20 20 20 | MSDOS *|/.X     |
|00002cd0| 20 20 69 66 20 28 70 72 | 65 76 20 3d 3d 20 4e 55 |  if (pr|ev == NU|
|00002ce0| 4c 4c 20 7c 7c 20 6e 65 | 78 74 20 3d 3d 20 4e 55 |LL || ne|xt == NU|
|00002cf0| 4c 4c 29 20 72 65 74 75 | 72 6e 20 49 4d 5f 4e 4f |LL) retu|rn IM_NO|
|00002d00| 4d 45 4d 3b 0a 58 0a 58 | 23 20 20 20 69 66 20 64 |MEM;.X.X|#   if d|
|00002d10| 65 66 69 6e 65 64 28 4d | 53 44 4f 53 29 20 26 26 |efined(M|SDOS) &&|
|00002d20| 20 21 64 65 66 69 6e 65 | 64 28 4f 53 32 29 0a 58 | !define|d(OS2).X|
|00002d30| 20 20 20 20 20 20 20 2f | 2a 20 4e 6f 72 6d 61 6c |       /|* Normal|
|00002d40| 69 7a 65 20 74 6f 20 70 | 6f 69 6e 74 65 72 73 20 |ize to p|ointers |
|00002d50| 77 69 74 68 20 6f 66 66 | 73 65 74 20 30 20 28 72 |with off|set 0 (r|
|00002d60| 65 71 75 69 72 65 64 20 | 62 79 20 61 73 6d 20 76 |equired |by asm v|
|00002d70| 65 72 73 69 6f 6e 29 2e | 0a 58 20 20 20 20 20 20 |ersion).|.X      |
|00002d80| 20 20 2a 20 46 6f 72 20 | 4f 53 2f 32 2c 20 77 65 |  * For |OS/2, we|
|00002d90| 20 63 61 6e 27 74 20 6f | 66 20 63 6f 75 72 73 65 | can't o|f course|
|00002da0| 20 70 6c 61 79 20 73 75 | 63 68 20 6e 61 73 74 79 | play su|ch nasty|
|00002db0| 20 67 61 6d 65 73 2e 0a | 58 20 20 20 20 20 20 20 | games..|X       |
|00002dc0| 20 2a 2f 0a 58 23 64 65 | 66 69 6e 65 20 4e 4f 52 | */.X#de|fine NOR|
|00002dd0| 4d 41 4c 49 5a 45 28 70 | 74 72 29 20 7b 20 5c 0a |MALIZE(p|tr) { \.|
|00002de0| 58 20 20 20 2a 28 28 69 | 6e 74 2a 29 26 70 74 72 |X   *((i|nt*)&ptr|
|00002df0| 2b 31 29 20 2b 3d 20 28 | 28 75 6e 73 69 67 6e 65 |+1) += (|(unsigne|
|00002e00| 64 29 28 70 74 72 2d 30 | 29 20 2b 20 31 35 29 20 |d)(ptr-0|) + 15) |
|00002e10| 3e 3e 20 34 3b 20 5c 0a | 58 20 20 20 2a 28 69 6e |>> 4; \.|X   *(in|
|00002e20| 74 2a 29 26 70 74 72 20 | 3d 20 30 3b 20 5c 0a 58 |t*)&ptr |= 0; \.X|
|00002e30| 7d 0a 58 20 20 20 20 20 | 20 20 4e 4f 52 4d 41 4c |}.X     |  NORMAL|
|00002e40| 49 5a 45 28 70 72 65 76 | 29 3b 20 4e 4f 52 4d 41 |IZE(prev|); NORMA|
|00002e50| 4c 49 5a 45 28 6e 65 78 | 74 29 3b 0a 58 23 20 20 |LIZE(nex|t);.X#  |
|00002e60| 20 65 6e 64 69 66 0a 58 | 20 20 20 20 7d 0a 58 23 | endif.X|    }.X#|
|00002e70| 65 6e 64 69 66 20 2f 2a | 20 44 59 4e 5f 41 4c 4c |endif /*| DYN_ALL|
|00002e80| 4f 43 20 2a 2f 0a 58 0a | 58 20 20 20 20 2f 2a 20 |OC */.X.|X    /* |
|00002e90| 49 6e 69 74 69 61 6c 69 | 7a 65 20 74 68 65 20 68 |Initiali|ze the h|
|00002ea0| 61 73 68 20 74 61 62 6c | 65 73 2e 20 2a 2f 0a 58 |ash tabl|es. */.X|
|00002eb0| 20 20 20 20 66 6f 72 20 | 28 69 20 3d 20 30 3b 20 |    for |(i = 0; |
|00002ec0| 20 69 20 3c 20 48 41 53 | 48 5f 53 49 5a 45 3b 20 | i < HAS|H_SIZE; |
|00002ed0| 69 2b 2b 29 20 6d 61 74 | 63 68 5f 68 65 61 64 5b |i++) mat|ch_head[|
|00002ee0| 69 5d 20 3d 20 4e 49 4c | 3b 0a 58 20 20 20 20 66 |i] = NIL|;.X    f|
|00002ef0| 6f 72 20 28 69 20 3d 20 | 30 3b 20 20 69 20 3c 3d |or (i = |0;  i <=|
|00002f00| 20 4d 41 58 5f 44 49 53 | 54 3b 20 69 2b 2b 29 20 | MAX_DIS|T; i++) |
|00002f10| 6e 65 78 74 5b 69 5d 20 | 3d 20 4e 49 4c 3b 0a 58 |next[i] |= NIL;.X|
|00002f20| 20 20 20 20 2f 2a 20 70 | 72 65 76 5b 30 2e 2e 4d |    /* p|rev[0..M|
|00002f30| 41 58 5f 44 49 53 54 5d | 20 77 69 6c 6c 20 62 65 |AX_DIST]| will be|
|00002f40| 20 69 6e 69 74 69 61 6c | 69 7a 65 64 20 6f 6e 20 | initial|ized on |
|00002f50| 74 68 65 20 66 6c 79 20 | 2a 2f 0a 58 20 20 20 20 |the fly |*/.X    |
|00002f60| 69 6e 73 5f 68 20 3d 20 | 30 3b 0a 58 0a 58 20 20 |ins_h = |0;.X.X  |
|00002f70| 20 20 2f 2a 20 41 73 73 | 75 6d 65 20 73 74 72 73 |  /* Ass|ume strs|
|00002f80| 69 7a 65 20 7a 65 72 6f | 73 20 62 65 66 6f 72 65 |ize zero|s before|
|00002f90| 20 74 68 65 20 69 6e 70 | 75 74 20 28 62 79 74 65 | the inp|ut (byte|
|00002fa0| 73 20 62 65 79 6f 6e 64 | 20 73 74 72 73 69 7a 65 |s beyond| strsize|
|00002fb0| 0a 58 20 20 20 20 20 2a | 20 63 61 6e 20 62 65 20 |.X     *| can be |
|00002fc0| 67 61 72 62 61 67 65 29 | 3a 0a 58 20 20 20 20 20 |garbage)|:.X     |
|00002fd0| 2a 2f 0a 58 20 20 20 20 | 6d 65 6d 73 65 74 28 28 |*/.X    |memset((|
|00002fe0| 63 68 61 72 2a 29 77 69 | 6e 64 6f 77 2c 20 30 2c |char*)wi|ndow, 0,|
|00002ff0| 20 4d 41 58 5f 4d 41 54 | 43 48 5f 4c 45 4e 47 54 | MAX_MAT|CH_LENGT|
|00003000| 48 29 3b 0a 58 20 20 20 | 20 2f 2a 20 49 74 20 69 |H);.X   | /* It i|
|00003010| 73 20 6e 6f 74 20 6e 65 | 63 65 73 73 61 72 79 20 |s not ne|cessary |
|00003020| 74 6f 20 64 75 70 6c 69 | 63 61 74 65 20 74 68 69 |to dupli|cate thi|
|00003030| 73 20 61 74 20 74 68 65 | 20 65 6e 64 20 6f 66 20 |s at the| end of |
|00003040| 74 68 65 20 77 69 6e 64 | 6f 77 2e 0a 58 20 20 20 |the wind|ow..X   |
|00003050| 20 20 2a 20 44 75 70 6c | 69 63 61 74 69 6f 6e 20 |  * Dupl|ication |
|00003060| 77 69 6c 6c 20 73 74 61 | 72 74 20 6f 6e 6c 79 20 |will sta|rt only |
|00003070| 61 66 74 65 72 20 74 68 | 65 20 66 69 72 73 74 20 |after th|e first |
|00003080| 77 72 61 70 20 61 72 6f | 75 6e 64 2e 0a 58 20 20 |wrap aro|und..X  |
|00003090| 20 20 20 2a 2f 0a 58 20 | 20 20 20 69 6e 73 65 72 |   */.X |   inser|
|000030a0| 74 5f 70 6f 69 6e 74 20 | 3d 20 4d 41 58 5f 4d 41 |t_point |= MAX_MA|
|000030b0| 54 43 48 5f 4c 45 4e 47 | 54 48 3b 0a 58 0a 58 20 |TCH_LENG|TH;.X.X |
|000030c0| 20 20 20 2f 2a 20 46 6f | 72 63 65 20 61 20 63 68 |   /* Fo|rce a ch|
|000030d0| 65 63 6b 20 66 6f 72 20 | 74 68 65 20 66 69 6c 65 |eck for |the file|
|000030e0| 20 74 79 70 65 20 28 61 | 73 63 69 69 2f 62 69 6e | type (a|scii/bin|
|000030f0| 61 72 79 29 20 61 6e 64 | 20 73 65 74 20 74 68 65 |ary) and| set the|
|00003100| 20 64 65 66 61 75 6c 74 | 0a 58 20 20 20 20 20 2a | default|.X     *|
|00003110| 20 63 6f 6e 66 69 67 75 | 72 61 74 69 6f 6e 20 70 | configu|ration p|
|00003120| 61 72 61 6d 65 74 65 72 | 73 3a 0a 58 20 20 20 20 |arameter|s:.X    |
|00003130| 20 2a 2f 0a 58 20 20 20 | 20 6d 69 6e 5f 6d 61 74 | */.X   | min_mat|
|00003140| 63 68 5f 6c 65 6e 67 74 | 68 20 3d 20 30 3b 0a 58 |ch_lengt|h = 0;.X|
|00003150| 20 20 20 20 6d 61 78 5f | 6c 61 7a 79 5f 6d 61 74 |    max_|lazy_mat|
|00003160| 63 68 20 20 20 3d 20 63 | 6f 6e 66 69 67 75 72 61 |ch   = c|onfigura|
|00003170| 74 69 6f 6e 5f 74 61 62 | 6c 65 5b 70 61 63 6b 5f |tion_tab|le[pack_|
|00003180| 6c 65 76 65 6c 5d 2e 6d | 61 78 5f 6c 61 7a 79 3b |level].m|ax_lazy;|
|00003190| 0a 58 20 20 20 20 6d 61 | 78 5f 63 68 61 69 6e 5f |.X    ma|x_chain_|
|000031a0| 6c 65 6e 67 74 68 20 3d | 20 63 6f 6e 66 69 67 75 |length =| configu|
|000031b0| 72 61 74 69 6f 6e 5f 74 | 61 62 6c 65 5b 70 61 63 |ration_t|able[pac|
|000031c0| 6b 5f 6c 65 76 65 6c 5d | 2e 6d 61 78 5f 63 68 61 |k_level]|.max_cha|
|000031d0| 69 6e 3b 0a 58 0a 58 20 | 20 20 20 2f 2a 20 44 6f |in;.X.X |   /* Do|
|000031e0| 20 6e 6f 74 20 72 65 70 | 6f 72 74 20 6d 61 74 63 | not rep|ort matc|
|000031f0| 68 65 73 20 62 65 66 6f | 72 65 20 74 68 65 20 66 |hes befo|re the f|
|00003200| 69 72 73 74 20 73 74 72 | 73 69 7a 65 20 73 74 72 |irst str|size str|
|00003210| 69 6e 67 73 20 68 61 76 | 65 20 62 65 65 6e 0a 58 |ings hav|e been.X|
|00003220| 20 20 20 20 20 2a 20 69 | 6e 73 65 72 74 65 64 20 |     * i|nserted |
|00003230| 69 6e 20 74 68 65 20 73 | 75 66 66 69 78 20 74 72 |in the s|uffix tr|
|00003240| 65 65 3a 0a 58 20 20 20 | 20 20 2a 2f 0a 58 20 20 |ee:.X   |  */.X  |
|00003250| 20 20 73 74 72 73 74 61 | 72 74 20 3d 20 30 3b 0a |  strsta|rt = 0;.|
|00003260| 58 20 20 20 20 63 68 65 | 63 6b 70 6f 69 6e 74 20 |X    che|ckpoint |
|00003270| 3d 20 73 74 72 73 69 7a | 65 3b 0a 58 20 20 20 20 |= strsiz|e;.X    |
|00003280| 69 66 20 28 6d 61 5f 62 | 75 66 20 3d 3d 20 4e 55 |if (ma_b|uf == NU|
|00003290| 4c 4c 29 20 7b 0a 58 20 | 20 20 20 20 20 20 20 6d |LL) {.X |       m|
|000032a0| 61 5f 62 75 66 20 3d 20 | 28 4d 41 54 43 48 20 2a |a_buf = |(MATCH *|
|000032b0| 29 20 6d 61 6c 6c 6f 63 | 20 28 28 75 6e 73 69 67 |) malloc| ((unsig|
|000032c0| 6e 65 64 29 20 28 4d 41 | 5f 42 55 46 53 49 5a 45 |ned) (MA|_BUFSIZE|
|000032d0| 20 2a 20 73 69 7a 65 6f | 66 20 28 4d 41 54 43 48 | * sizeo|f (MATCH|
|000032e0| 29 29 29 3b 0a 58 20 20 | 20 20 20 20 20 20 69 66 |)));.X  |      if|
|000032f0| 20 28 6d 61 5f 62 75 66 | 20 3d 3d 20 4e 55 4c 4c | (ma_buf| == NULL|
|00003300| 29 20 72 65 74 75 72 6e | 20 49 4d 5f 4e 4f 4d 45 |) return| IM_NOME|
|00003310| 4d 3b 0a 58 20 20 20 20 | 7d 0a 58 20 20 20 20 6d |M;.X    |}.X    m|
|00003320| 61 20 3d 20 6d 61 5f 62 | 75 66 20 2d 20 31 3b 0a |a = ma_b|uf - 1;.|
|00003330| 58 20 20 20 20 73 74 61 | 72 74 5f 6c 65 6e 67 74 |X    sta|rt_lengt|
|00003340| 68 20 3d 20 31 3b 0a 58 | 0a 58 20 20 20 20 2f 2a |h = 1;.X|.X    /*|
|00003350| 20 41 6c 6c 20 64 6f 6e | 65 2e 20 2a 2f 0a 58 20 | All don|e. */.X |
|00003360| 20 20 20 72 65 74 75 72 | 6e 20 49 4d 5f 4f 4b 3b |   retur|n IM_OK;|
|00003370| 0a 58 7d 0a 58 0a 58 2f | 2a 2a 2a 2a 2a 2a 2a 2a |.X}.X.X/|********|
|00003380| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003390| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000033a0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000033b0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 0a |********|*******.|
|000033c0| 58 20 2a 0a 58 20 2a 20 | 4f 75 74 70 75 74 20 74 |X *.X * |Output t|
|000033d0| 68 65 20 6d 61 74 63 68 | 20 69 6e 66 6f 2e 0a 58 |he match| info..X|
|000033e0| 20 2a 20 49 4e 20 61 73 | 73 65 72 74 69 6f 6e 73 | * IN as|sertions|
|000033f0| 3a 20 54 68 65 20 6d 61 | 74 63 68 69 6e 67 20 73 |: The ma|tching s|
|00003400| 74 72 69 6e 67 73 20 73 | 74 61 72 74 20 61 74 20 |trings s|tart at |
|00003410| 73 74 72 73 74 61 72 74 | 20 61 6e 64 20 6d 61 5f |strstart| and ma_|
|00003420| 73 74 61 72 74 0a 58 20 | 2a 20 20 20 20 61 6e 64 |start.X |*    and|
|00003430| 20 68 61 76 65 20 61 20 | 6c 65 6e 67 74 68 20 6f | have a |length o|
|00003440| 66 20 6d 61 5f 6c 65 6e | 67 74 68 20 62 79 74 65 |f ma_len|gth byte|
|00003450| 73 2e 0a 58 20 2a 20 20 | 20 20 49 66 20 6d 61 5f |s..X *  |  If ma_|
|00003460| 6c 65 6e 67 74 68 20 69 | 73 20 6e 6f 74 20 67 72 |length i|s not gr|
|00003470| 65 61 74 65 72 20 74 68 | 61 6e 20 73 74 61 72 74 |eater th|an start|
|00003480| 5f 6c 65 6e 67 74 68 2c | 20 6d 61 5f 73 74 61 72 |_length,| ma_star|
|00003490| 74 20 69 73 20 67 61 72 | 62 61 67 65 2e 0a 58 20 |t is gar|bage..X |
|000034a0| 2a 20 20 20 20 73 74 72 | 73 74 61 74 20 3d 3d 20 |*    str|stat == |
|000034b0| 63 68 65 63 6b 70 6f 69 | 6e 74 2e 20 49 66 20 73 |checkpoi|nt. If s|
|000034c0| 74 61 72 74 5f 6c 65 6e | 67 74 68 20 3e 20 31 2c |tart_len|gth > 1,|
|000034d0| 20 6d 61 20 69 73 20 74 | 68 65 0a 58 20 2a 20 20 | ma is t|he.X *  |
|000034e0| 20 20 70 72 65 76 69 6f | 75 73 20 6d 61 74 63 68 |  previo|us match|
|000034f0| 20 77 68 69 63 68 20 68 | 61 73 20 6e 6f 74 20 79 | which h|as not y|
|00003500| 65 74 20 62 65 65 6e 20 | 6f 75 74 70 75 74 2e 0a |et been |output..|
|00003510| 58 20 2a 20 4f 55 54 20 | 61 73 73 65 72 74 69 6f |X * OUT |assertio|
|00003520| 6e 3a 20 63 68 65 63 6b | 70 6f 69 6e 74 20 69 73 |n: check|point is|
|00003530| 20 72 65 73 65 74 20 61 | 63 63 6f 72 64 69 6e 67 | reset a|ccording|
|00003540| 20 74 6f 20 74 68 65 20 | 6d 61 74 63 68 20 6c 65 | to the |match le|
|00003550| 6e 67 74 68 0a 58 20 2a | 20 20 20 20 61 63 74 75 |ngth.X *|    actu|
|00003560| 61 6c 6c 79 20 63 68 6f | 73 65 6e 2e 0a 58 20 2a |ally cho|sen..X *|
|00003570| 20 20 20 20 6d 61 20 69 | 73 20 73 65 74 20 74 6f |    ma i|s set to|
|00003580| 20 74 68 65 20 63 75 72 | 72 65 6e 74 20 6d 61 74 | the cur|rent mat|
|00003590| 63 68 2c 20 77 69 74 68 | 20 73 74 61 72 74 5f 6c |ch, with| start_l|
|000035a0| 65 6e 67 74 68 20 73 65 | 74 20 61 70 70 72 6f 70 |ength se|t approp|
|000035b0| 72 69 61 74 65 6c 79 2e | 0a 58 20 2a 2f 0a 49 6d |riately.|.X */.Im|
|000035c0| 70 45 72 72 20 77 72 69 | 74 65 5f 6d 61 74 63 68 |pErr wri|te_match|
|000035d0| 28 6d 61 5f 73 74 61 72 | 74 2c 20 6d 61 5f 6c 65 |(ma_star|t, ma_le|
|000035e0| 6e 67 74 68 29 0a 58 20 | 20 20 20 49 50 6f 73 20 |ngth).X |   IPos |
|000035f0| 6d 61 5f 73 74 61 72 74 | 3b 20 20 20 20 20 20 20 |ma_start|;       |
|00003600| 20 20 20 20 2f 2a 20 73 | 74 61 72 74 20 6f 66 20 |    /* s|tart of |
|00003610| 6d 61 74 63 68 65 64 20 | 73 74 72 69 6e 67 20 2a |matched |string *|
|00003620| 2f 0a 58 20 20 20 20 69 | 6e 74 20 6d 61 5f 6c 65 |/.X    i|nt ma_le|
|00003630| 6e 67 74 68 3b 20 20 20 | 20 20 20 20 20 20 20 20 |ngth;   |        |
|00003640| 2f 2a 20 6c 65 6e 67 74 | 68 20 6f 66 20 63 6f 6d |/* lengt|h of com|
|00003650| 70 6c 65 74 65 20 6d 61 | 74 63 68 20 2a 2f 0a 58 |plete ma|tch */.X|
|00003660| 7b 0a 58 20 20 20 20 69 | 6e 74 20 6d 61 5f 64 69 |{.X    i|nt ma_di|
|00003670| 73 74 20 3d 20 30 3b 20 | 20 20 20 20 20 20 20 20 |st = 0; |        |
|00003680| 2f 2a 20 64 69 73 74 61 | 6e 63 65 20 6f 66 20 63 |/* dista|nce of c|
|00003690| 75 72 72 65 6e 74 20 6d | 61 74 63 68 20 2a 2f 0a |urrent m|atch */.|
|000036a0| 58 0a 58 20 20 20 20 2f | 2a 20 6d 61 5f 6c 65 6e |X.X    /|* ma_len|
|000036b0| 67 74 68 20 63 61 6e 20 | 62 65 20 74 6f 6f 20 6c |gth can |be too l|
|000036c0| 61 72 67 65 20 74 6f 77 | 61 72 64 73 20 74 68 65 |arge tow|ards the|
|000036d0| 20 65 6e 64 20 6f 66 20 | 74 68 65 20 69 6e 70 75 | end of |the inpu|
|000036e0| 74 3a 20 2a 2f 0a 58 20 | 20 20 20 69 66 20 28 6d |t: */.X |   if (m|
|000036f0| 61 5f 6c 65 6e 67 74 68 | 20 3e 20 73 74 72 73 69 |a_length| > strsi|
|00003700| 7a 65 29 20 6d 61 5f 6c | 65 6e 67 74 68 20 3d 20 |ze) ma_l|ength = |
|00003710| 73 74 72 73 69 7a 65 3b | 0a 58 0a 58 23 69 66 64 |strsize;|.X.X#ifd|
|00003720| 65 66 20 44 45 42 55 47 | 0a 58 20 20 20 20 2f 2a |ef DEBUG|.X    /*|
|00003730| 20 63 68 65 63 6b 20 74 | 68 61 74 20 74 68 65 20 | check t|hat the |
|00003740| 6d 61 74 63 68 20 69 73 | 20 69 6e 64 65 65 64 20 |match is| indeed |
|00003750| 61 20 6d 61 74 63 68 20 | 2a 2f 0a 58 20 20 20 20 |a match |*/.X    |
|00003760| 69 66 20 28 6d 61 5f 6c | 65 6e 67 74 68 20 3e 20 |if (ma_l|ength > |
|00003770| 73 74 61 72 74 5f 6c 65 | 6e 67 74 68 20 26 26 0a |start_le|ngth &&.|
|00003780| 58 20 20 20 20 20 20 20 | 20 73 74 72 6e 63 6d 70 |X       | strncmp|
|00003790| 28 77 69 6e 64 6f 77 20 | 2b 20 6d 61 5f 73 74 61 |(window |+ ma_sta|
|000037a0| 72 74 2c 20 77 69 6e 64 | 6f 77 20 2b 20 73 74 72 |rt, wind|ow + str|
|000037b0| 73 74 61 72 74 2c 20 6d | 61 5f 6c 65 6e 67 74 68 |start, m|a_length|
|000037c0| 29 20 21 3d 20 45 51 55 | 41 4c 29 20 7b 0a 58 20 |) != EQU|AL) {.X |
|000037d0| 20 20 20 20 20 20 20 66 | 70 72 69 6e 74 66 28 73 |       f|printf(s|
|000037e0| 74 64 65 72 72 2c 0a 58 | 20 20 20 20 20 20 20 20 |tderr,.X|        |
|000037f0| 20 20 20 20 22 77 72 69 | 74 65 5f 6d 61 74 63 68 |    "wri|te_match|
|00003800| 3a 20 6d 61 5f 73 74 61 | 72 74 20 25 64 2c 20 73 |: ma_sta|rt %d, s|
|00003810| 74 72 73 74 61 72 74 20 | 25 64 2c 20 6d 61 5f 6c |trstart |%d, ma_l|
|00003820| 65 6e 67 74 68 20 25 64 | 5c 6e 22 2c 0a 58 20 20 |ength %d|\n",.X  |
|00003830| 20 20 20 20 20 20 20 20 | 20 20 6d 61 5f 73 74 61 |        |  ma_sta|
|00003840| 72 74 2c 20 73 74 72 73 | 74 61 72 74 2c 20 6d 61 |rt, strs|tart, ma|
|00003850| 5f 6c 65 6e 67 74 68 29 | 3b 0a 58 20 20 20 20 20 |_length)|;.X     |
|00003860| 20 20 20 65 78 69 74 28 | 31 29 3b 0a 58 20 20 20 |   exit(|1);.X   |
|00003870| 20 7d 0a 58 23 65 6e 64 | 69 66 0a 58 20 20 20 20 | }.X#end|if.X    |
|00003880| 2f 2a 20 50 4b 55 4e 5a | 49 50 20 61 63 63 65 70 |/* PKUNZ|IP accep|
|00003890| 74 73 20 6d 6f 73 74 20 | 6f 76 65 72 6c 61 70 70 |ts most |overlapp|
|000038a0| 69 6e 67 20 6d 61 74 63 | 68 65 73 2e 20 20 48 6f |ing matc|hes.  Ho|
|000038b0| 77 65 76 65 72 2c 20 77 | 68 65 6e 20 74 68 65 0a |wever, w|hen the.|
|000038c0| 58 20 20 20 20 20 2a 20 | 64 69 73 74 61 6e 63 65 |X     * |distance|
|000038d0| 20 68 61 73 20 74 68 65 | 20 76 61 6c 75 65 20 31 | has the| value 1|
|000038e0| 2c 20 76 65 72 73 69 6f | 6e 73 20 6f 66 20 50 4b |, versio|ns of PK|
|000038f0| 55 4e 5a 49 50 20 70 72 | 69 6f 72 20 74 6f 20 31 |UNZIP pr|ior to 1|
|00003900| 2e 31 30 20 64 6f 6e 27 | 74 0a 58 20 20 20 20 20 |.10 don'|t.X     |
|00003910| 2a 20 68 61 6e 64 6c 65 | 20 74 68 65 20 6f 76 65 |* handle| the ove|
|00003920| 72 6c 61 70 20 70 72 6f | 70 65 72 6c 79 20 2d 2d |rlap pro|perly --|
|00003930| 20 61 6e 64 20 76 65 72 | 73 69 6f 6e 20 31 2e 31 | and ver|sion 1.1|
|00003940| 30 20 68 61 6e 64 6c 65 | 73 20 74 68 65 0a 58 20 |0 handle|s the.X |
|00003950| 20 20 20 20 2a 20 6f 76 | 65 72 6c 61 70 20 63 6f |    * ov|erlap co|
|00003960| 72 72 65 63 74 6c 79 20 | 6f 6e 6c 79 20 69 66 20 |rrectly |only if |
|00003970| 74 68 65 20 6c 65 6e 67 | 74 68 20 69 73 20 6c 69 |the leng|th is li|
|00003980| 6d 69 74 65 64 20 74 6f | 20 36 32 20 70 6c 75 73 |mited to| 62 plus|
|00003990| 20 74 68 65 0a 58 20 20 | 20 20 20 2a 20 6d 69 6e | the.X  |   * min|
|000039a0| 69 6d 75 6d 20 6d 61 74 | 63 68 20 6c 65 6e 67 74 |imum mat|ch lengt|
|000039b0| 68 3b 20 69 2e 65 2e 2c | 20 6f 6e 6c 79 20 69 66 |h; i.e.,| only if|
|000039c0| 20 74 68 65 72 65 20 69 | 73 20 6e 6f 20 73 75 70 | there i|s no sup|
|000039d0| 70 6c 65 6d 65 6e 74 61 | 72 79 0a 58 20 20 20 20 |plementa|ry.X    |
|000039e0| 20 2a 20 6c 65 6e 67 74 | 68 20 62 79 74 65 2e 20 | * lengt|h byte. |
|000039f0| 20 28 46 72 6f 6d 20 70 | 68 6f 6e 65 20 63 6f 6e | (From p|hone con|
|00003a00| 76 65 72 73 61 74 69 6f | 6e 20 77 69 74 68 20 50 |versatio|n with P|
|00003a10| 68 69 6c 20 4b 61 74 7a | 2c 20 32 33 20 4a 61 6e |hil Katz|, 23 Jan|
|00003a20| 75 61 72 79 0a 58 20 20 | 20 20 20 2a 20 31 39 39 |uary.X  |   * 199|
|00003a30| 31 2e 29 20 54 68 65 20 | 63 6f 6d 70 72 65 73 73 |1.) The |compress|
|00003a40| 69 6f 6e 20 72 61 74 69 | 6f 20 69 73 20 67 65 6e |ion rati|o is gen|
|00003a50| 65 72 61 6c 6c 79 20 62 | 65 74 74 65 72 20 77 68 |erally b|etter wh|
|00003a60| 65 6e 20 77 65 20 64 6f | 20 6e 6f 74 0a 58 20 20 |en we do| not.X  |
|00003a70| 20 20 20 2a 20 6c 69 6d | 69 74 20 74 68 65 20 6d |   * lim|it the m|
|00003a80| 61 74 63 68 20 6c 65 6e | 67 74 68 20 74 6f 20 36 |atch len|gth to 6|
|00003a90| 34 2c 20 73 6f 20 77 65 | 20 72 65 6d 6f 76 65 20 |4, so we| remove |
|00003aa0| 64 69 73 74 61 6e 63 65 | 2d 6f 6e 65 20 6d 61 74 |distance|-one mat|
|00003ab0| 63 68 65 73 0a 58 20 20 | 20 20 20 2a 20 63 6f 6d |ches.X  |   * com|
|00003ac0| 70 6c 65 74 65 6c 79 2e | 20 28 42 75 74 20 50 4b |pletely.| (But PK|
|00003ad0| 55 4e 5a 49 50 20 31 2e | 30 31 20 61 6c 73 6f 20 |UNZIP 1.|01 also |
|00003ae0| 72 65 6a 65 63 74 73 20 | 73 6f 6d 65 20 64 69 73 |rejects |some dis|
|00003af0| 74 61 6e 63 65 2d 74 77 | 6f 20 6d 61 74 63 68 65 |tance-tw|o matche|
|00003b00| 73 2e 0a 58 20 20 20 20 | 20 2a 20 54 68 69 73 20 |s..X    | * This |
|00003b10| 63 6f 75 6c 64 20 62 65 | 20 66 69 78 65 64 20 62 |could be| fixed b|
|00003b20| 75 74 20 77 6f 75 6c 64 | 20 64 65 67 72 61 64 65 |ut would| degrade|
|00003b30| 20 63 6f 6d 70 72 65 73 | 73 69 6f 6e 2e 29 0a 58 | compres|sion.).X|
|00003b40| 20 20 20 20 20 2a 2f 0a | 58 20 20 20 20 69 66 20 |     */.|X    if |
|00003b50| 28 6d 61 5f 6c 65 6e 67 | 74 68 20 3e 20 31 29 20 |(ma_leng|th > 1) |
|00003b60| 7b 0a 58 20 20 20 20 20 | 20 20 20 6d 61 5f 64 69 |{.X     |   ma_di|
|00003b70| 73 74 20 3d 20 73 74 72 | 73 74 61 72 74 20 2d 20 |st = str|start - |
|00003b80| 6d 61 5f 73 74 61 72 74 | 3b 0a 58 20 20 20 20 20 |ma_start|;.X     |
|00003b90| 20 20 20 69 66 20 28 6d | 61 5f 64 69 73 74 20 3c |   if (m|a_dist <|
|00003ba0| 20 30 29 20 6d 61 5f 64 | 69 73 74 20 2b 3d 20 4d | 0) ma_d|ist += M|
|00003bb0| 41 58 5f 44 49 53 54 3b | 0a 58 20 20 20 20 20 20 |AX_DIST;|.X      |
|00003bc0| 20 20 69 66 20 28 6d 61 | 5f 64 69 73 74 20 3d 3d |  if (ma|_dist ==|
|00003bd0| 20 31 29 20 7b 0a 58 20 | 20 20 20 20 20 20 20 20 | 1) {.X |        |
|00003be0| 20 20 20 2f 2a 20 6b 65 | 65 70 20 74 68 65 20 70 |   /* ke|ep the p|
|00003bf0| 72 65 76 69 6f 75 73 20 | 6d 61 74 63 68 20 69 66 |revious |match if|
|00003c00| 20 69 74 20 77 61 73 20 | 64 65 6c 61 79 65 64 20 | it was |delayed |
|00003c10| 2a 2f 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |*/.X    |        |
|00003c20| 69 66 20 28 73 74 61 72 | 74 5f 6c 65 6e 67 74 68 |if (star|t_length|
|00003c30| 20 3e 20 31 29 20 7b 0a | 58 20 20 20 20 20 20 20 | > 1) {.|X       |
|00003c40| 20 20 20 20 20 20 20 20 | 20 6d 61 5f 6c 65 6e 67 |        | ma_leng|
|00003c50| 74 68 20 3d 20 31 3b 0a | 58 20 20 20 20 20 20 20 |th = 1;.|X       |
|00003c60| 20 20 20 20 20 7d 20 65 | 6c 73 65 20 7b 0a 58 20 |     } e|lse {.X |
|00003c70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2f |        |       /|
|00003c80| 2a 20 54 72 75 6e 63 61 | 74 65 20 74 68 65 20 6d |* Trunca|te the m|
|00003c90| 61 74 63 68 20 74 6f 20 | 31 20 2a 2f 0a 58 20 20 |atch to |1 */.X  |
|00003ca0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 49 6d |        |      Im|
|00003cb0| 70 45 72 72 20 72 65 74 | 63 6f 64 65 20 3d 20 77 |pErr ret|code = w|
|00003cc0| 72 69 74 65 5f 6d 61 74 | 63 68 28 6d 61 5f 73 74 |rite_mat|ch(ma_st|
|00003cd0| 61 72 74 2c 20 31 29 3b | 0a 58 20 20 20 20 20 20 |art, 1);|.X      |
|00003ce0| 20 20 20 20 20 20 20 20 | 20 20 69 66 20 28 72 65 |        |  if (re|
|00003cf0| 74 63 6f 64 65 20 21 3d | 20 49 4d 5f 4f 4b 29 20 |tcode !=| IM_OK) |
|00003d00| 72 65 74 75 72 6e 20 72 | 65 74 63 6f 64 65 3b 0a |return r|etcode;.|
|00003d10| 58 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |X.X     |        |
|00003d20| 20 20 20 2f 2a 20 45 6d | 69 74 20 61 20 6d 61 74 |   /* Em|it a mat|
|00003d30| 63 68 20 77 69 74 68 20 | 61 20 64 69 73 74 61 6e |ch with |a distan|
|00003d40| 63 65 20 6f 66 20 74 77 | 6f 20 61 6e 64 20 61 20 |ce of tw|o and a |
|00003d50| 6c 65 6e 67 74 68 20 72 | 65 64 75 63 65 64 20 62 |length r|educed b|
|00003d60| 79 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |y.X     |        |
|00003d70| 20 20 20 20 2a 20 6f 6e | 65 2e 20 54 68 69 73 20 |    * on|e. This |
|00003d80| 72 65 64 75 63 65 64 20 | 6d 61 74 63 68 20 6d 61 |reduced |match ma|
|00003d90| 79 20 62 65 20 64 65 6c | 61 79 65 64 2e 0a 58 20 |y be del|ayed..X |
|00003da0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003db0| 2a 2f 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |*/.X    |        |
|00003dc0| 20 20 20 20 63 68 65 63 | 6b 70 6f 69 6e 74 20 3d |    chec|kpoint =|
|00003dd0| 20 2b 2b 73 74 72 73 74 | 61 72 74 3b 0a 58 20 20 | ++strst|art;.X  |
|00003de0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 72 65 |        |      re|
|00003df0| 74 63 6f 64 65 20 3d 20 | 77 72 69 74 65 5f 6d 61 |tcode = |write_ma|
|00003e00| 74 63 68 28 6d 61 5f 73 | 74 61 72 74 2c 20 6d 61 |tch(ma_s|tart, ma|
|00003e10| 5f 6c 65 6e 67 74 68 2d | 31 29 3b 0a 58 20 20 20 |_length-|1);.X   |
|00003e20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 73 74 72 |        |     str|
|00003e30| 73 74 61 72 74 2d 2d 3b | 0a 58 20 20 20 20 20 20 |start--;|.X      |
|00003e40| 20 20 20 20 20 20 20 20 | 20 20 72 65 74 75 72 6e |        |  return|
|00003e50| 20 72 65 74 63 6f 64 65 | 3b 20 2f 2a 20 4c 65 61 | retcode|; /* Lea|
|00003e60| 76 65 20 63 68 65 63 6b | 70 6f 69 6e 74 20 75 6e |ve check|point un|
|00003e70| 63 68 61 6e 67 65 64 20 | 2a 2f 0a 58 20 20 20 20 |changed |*/.X    |
|00003e80| 20 20 20 20 20 20 20 20 | 7d 20 2f 2a 20 73 74 61 |        |} /* sta|
|00003e90| 72 74 5f 6c 65 6e 67 74 | 68 20 3e 20 31 20 2a 2f |rt_lengt|h > 1 */|
|00003ea0| 0a 58 20 20 20 20 20 20 | 20 20 7d 20 2f 2a 20 6d |.X      |  } /* m|
|00003eb0| 61 5f 64 69 73 74 20 3d | 3d 20 31 20 2a 2f 0a 58 |a_dist =|= 1 */.X|
|00003ec0| 20 20 20 20 7d 20 2f 2a | 20 6d 61 5f 6c 65 6e 67 |    } /*| ma_leng|
|00003ed0| 74 68 20 3e 20 31 20 2a | 2f 0a 58 0a 58 20 20 20 |th > 1 *|/.X.X   |
|00003ee0| 20 2f 2a 20 49 66 20 74 | 68 65 20 70 72 65 76 69 | /* If t|he previ|
|00003ef0| 6f 75 73 20 6d 61 74 63 | 68 20 68 61 73 20 62 65 |ous matc|h has be|
|00003f00| 65 6e 20 64 65 6c 61 79 | 65 64 2c 20 6b 65 65 70 |en delay|ed, keep|
|00003f10| 20 69 74 20 6f 72 20 70 | 72 65 66 65 72 20 74 68 | it or p|refer th|
|00003f20| 65 0a 58 20 20 20 20 20 | 2a 20 63 75 72 72 65 6e |e.X     |* curren|
|00003f30| 74 20 6d 61 74 63 68 3a | 0a 58 20 20 20 20 20 2a |t match:|.X     *|
|00003f40| 2f 0a 58 20 20 20 20 69 | 66 20 28 73 74 61 72 74 |/.X    i|f (start|
|00003f50| 5f 6c 65 6e 67 74 68 20 | 3e 20 31 29 20 7b 0a 58 |_length |> 1) {.X|
|00003f60| 20 20 20 20 20 20 20 20 | 2f 2a 20 4b 65 65 70 20 |        |/* Keep |
|00003f70| 74 68 65 20 70 72 65 76 | 69 6f 75 73 20 6d 61 74 |the prev|ious mat|
|00003f80| 63 68 20 69 66 20 69 74 | 20 69 73 20 6e 6f 74 20 |ch if it| is not |
|00003f90| 73 68 6f 72 74 65 72 20 | 74 68 61 6e 20 74 68 65 |shorter |than the|
|00003fa0| 20 63 75 72 72 65 6e 74 | 20 6f 6e 65 2e 0a 58 20 | current| one..X |
|00003fb0| 20 20 20 20 20 20 20 20 | 2a 20 4f 74 68 65 72 77 |        |* Otherw|
|00003fc0| 69 73 65 2c 20 65 6d 69 | 74 20 6f 6e 6c 79 20 74 |ise, emi|t only t|
|00003fd0| 68 65 20 66 69 72 73 74 | 20 62 79 74 65 20 6f 66 |he first| byte of|
|00003fe0| 20 74 68 65 20 70 72 65 | 76 69 6f 75 73 20 6d 61 | the pre|vious ma|
|00003ff0| 74 63 68 2c 0a 58 20 20 | 20 20 20 20 20 20 20 2a |tch,.X  |       *|
|00004000| 20 66 6f 6c 6c 6f 77 65 | 64 20 62 79 20 74 68 65 | followe|d by the|
|00004010| 20 63 75 72 72 65 6e 74 | 20 6d 61 74 63 68 2e 20 | current| match. |
|00004020| 49 66 20 77 65 20 68 61 | 76 65 20 61 20 64 65 6c |If we ha|ve a del|
|00004030| 61 79 65 64 20 6d 61 74 | 63 68 20 66 6f 72 0a 58 |ayed mat|ch for.X|
|00004040| 20 20 20 20 20 20 20 20 | 20 2a 20 74 68 65 20 6c |        | * the l|
|00004050| 61 73 74 20 62 79 74 65 | 73 20 6f 66 20 74 68 65 |ast byte|s of the|
|00004060| 20 69 6e 70 75 74 20 66 | 69 6c 65 2c 20 74 68 65 | input f|ile, the|
|00004070| 20 6e 65 78 74 20 6d 61 | 74 63 68 20 77 69 6c 6c | next ma|tch will|
|00004080| 20 6e 65 63 65 73 73 61 | 72 69 6c 79 0a 58 20 20 | necessa|rily.X  |
|00004090| 20 20 20 20 20 20 20 2a | 20 62 65 20 73 6d 61 6c |       *| be smal|
|000040a0| 6c 65 72 2c 20 73 6f 20 | 63 74 5f 74 61 6c 6c 79 |ler, so |ct_tally|
|000040b0| 20 77 69 6c 6c 20 63 6f | 72 72 65 63 74 6c 79 20 | will co|rrectly |
|000040c0| 62 65 20 63 61 6c 6c 65 | 64 20 66 6f 72 20 74 68 |be calle|d for th|
|000040d0| 65 20 64 65 6c 61 79 65 | 64 0a 58 20 20 20 20 20 |e delaye|d.X     |
|000040e0| 20 20 20 20 2a 20 6d 61 | 74 63 68 2e 0a 58 20 20 |    * ma|tch..X  |
|000040f0| 20 20 20 20 20 20 20 2a | 2f 0a 58 20 20 20 20 20 |       *|/.X     |
|00004100| 20 20 20 69 66 20 28 73 | 74 61 72 74 5f 6c 65 6e |   if (s|tart_len|
|00004110| 67 74 68 20 3e 3d 20 6d | 61 5f 6c 65 6e 67 74 68 |gth >= m|a_length|
|00004120| 29 20 7b 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |) {.X   |        |
|00004130| 20 2f 2a 20 4b 65 65 70 | 20 74 68 65 20 70 72 65 | /* Keep| the pre|
|00004140| 76 69 6f 75 73 20 6d 61 | 74 63 68 20 2a 2f 0a 58 |vious ma|tch */.X|
|00004150| 20 20 20 20 20 20 20 20 | 20 20 20 20 69 66 20 28 |        |    if (|
|00004160| 73 74 61 72 74 5f 6c 65 | 6e 67 74 68 20 3d 3d 20 |start_le|ngth == |
|00004170| 32 29 20 7b 0a 58 20 20 | 20 20 20 20 20 20 20 20 |2) {.X  |        |
|00004180| 20 20 20 20 20 20 6d 61 | 2d 3e 6d 61 5f 64 69 73 |      ma|->ma_dis|
|00004190| 74 20 3d 20 2d 20 6d 61 | 2d 3e 6d 61 5f 64 69 73 |t = - ma|->ma_dis|
|000041a0| 74 3b 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |t;.X    |        |
|000041b0| 20 20 20 20 6d 61 2d 3e | 6c 2e 6d 61 5f 6c 69 74 |    ma->|l.ma_lit|
|000041c0| 63 5b 31 5d 20 3d 20 77 | 69 6e 64 6f 77 5b 73 74 |c[1] = w|indow[st|
|000041d0| 72 73 74 61 72 74 5d 3b | 20 2f 2a 20 6c 69 74 63 |rstart];| /* litc|
|000041e0| 5b 30 5d 20 61 6c 72 65 | 61 64 79 20 73 65 74 20 |[0] alre|ady set |
|000041f0| 2a 2f 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |*/.X    |        |
|00004200| 7d 20 65 6c 73 65 20 7b | 0a 58 20 20 20 20 20 20 |} else {|.X      |
|00004210| 20 20 20 20 20 20 20 20 | 20 20 6d 61 2d 3e 6c 2e |        |  ma->l.|
|00004220| 6d 61 5f 6c 65 6e 67 74 | 68 20 3d 20 73 74 61 72 |ma_lengt|h = star|
|00004230| 74 5f 6c 65 6e 67 74 68 | 3b 20 2f 2a 20 6f 76 65 |t_length|; /* ove|
|00004240| 72 77 72 69 74 65 20 6d | 61 2d 3e 6c 2e 6d 61 5f |rwrite m|a->l.ma_|
|00004250| 6c 69 74 63 20 2a 2f 0a | 58 20 20 20 20 20 20 20 |litc */.|X       |
|00004260| 20 20 20 20 20 7d 0a 58 | 20 20 20 20 20 20 20 20 |     }.X|        |
|00004270| 20 20 20 20 63 68 65 63 | 6b 70 6f 69 6e 74 20 3d |    chec|kpoint =|
|00004280| 20 73 74 72 73 74 61 72 | 74 20 2b 20 73 74 61 72 | strstar|t + star|
|00004290| 74 5f 6c 65 6e 67 74 68 | 20 2d 20 31 3b 0a 58 20 |t_length| - 1;.X |
|000042a0| 20 20 20 20 20 20 20 20 | 20 20 20 73 74 61 72 74 |        |   start|
|000042b0| 5f 6c 65 6e 67 74 68 20 | 3d 20 31 3b 0a 58 20 20 |_length |= 1;.X  |
|000042c0| 20 20 20 20 20 20 20 20 | 20 20 72 65 74 75 72 6e |        |  return|
|000042d0| 20 63 74 5f 74 61 6c 6c | 79 20 28 6d 61 29 3b 0a | ct_tall|y (ma);.|
|000042e0| 58 20 20 20 20 20 20 20 | 20 7d 0a 58 20 20 20 20 |X       | }.X    |
|000042f0| 20 20 20 20 2f 2a 20 53 | 68 6f 72 74 65 6e 20 74 |    /* S|horten t|
|00004300| 68 65 20 70 72 65 76 69 | 6f 75 73 20 6d 61 74 63 |he previ|ous matc|
|00004310| 68 20 74 6f 20 7a 65 72 | 6f 20 2a 2f 0a 58 20 20 |h to zer|o */.X  |
|00004320| 20 20 20 20 20 20 6d 61 | 2d 3e 6d 61 5f 64 69 73 |      ma|->ma_dis|
|00004330| 74 20 3d 20 30 3b 20 2f | 2a 20 6b 65 65 70 20 6d |t = 0; /|* keep m|
|00004340| 61 2d 3e 6c 2e 6d 61 5f | 6c 69 74 63 20 2a 2f 0a |a->l.ma_|litc */.|
|00004350| 58 20 20 20 20 20 20 20 | 20 73 74 61 72 74 5f 6c |X       | start_l|
|00004360| 65 6e 67 74 68 20 3d 20 | 31 3b 0a 58 20 20 20 20 |ength = |1;.X    |
|00004370| 20 20 20 20 28 76 6f 69 | 64 29 20 63 74 5f 74 61 |    (voi|d) ct_ta|
|00004380| 6c 6c 79 20 28 6d 61 29 | 3b 20 2f 2a 20 69 67 6e |lly (ma)|; /* ign|
|00004390| 6f 72 65 20 72 65 73 75 | 6c 74 2c 20 63 74 5f 74 |ore resu|lt, ct_t|
|000043a0| 61 6c 6c 79 20 63 61 6e | 6e 6f 74 20 66 61 69 6c |ally can|not fail|
|000043b0| 20 2a 2f 0a 58 20 20 20 | 20 7d 0a 58 0a 58 20 20 | */.X   | }.X.X  |
|000043c0| 20 20 69 66 20 28 2b 2b | 6d 61 20 3d 3d 20 4d 41 |  if (++|ma == MA|
|000043d0| 5f 42 55 46 45 4e 44 29 | 20 7b 0a 58 20 20 20 20 |_BUFEND)| {.X    |
|000043e0| 20 20 20 20 6d 61 20 3d | 20 6d 61 5f 62 75 66 3b |    ma =| ma_buf;|
|000043f0| 0a 58 20 20 20 20 20 20 | 20 20 69 66 20 28 74 77 |.X      |  if (tw|
|00004400| 72 69 74 65 20 28 28 63 | 68 61 72 20 2a 29 20 6d |rite ((c|har *) m|
|00004410| 61 2c 20 73 69 7a 65 6f | 66 28 4d 41 54 43 48 29 |a, sizeo|f(MATCH)|
|00004420| 2c 20 4d 41 5f 42 55 46 | 53 49 5a 45 2c 20 66 64 |, MA_BUF|SIZE, fd|
|00004430| 2e 66 64 5f 74 65 6d 70 | 29 0a 58 20 20 20 20 20 |.fd_temp|).X     |
|00004440| 20 20 20 20 20 20 20 21 | 3d 20 4d 41 5f 42 55 46 |       !|= MA_BUF|
|00004450| 53 49 5a 45 29 20 72 65 | 74 75 72 6e 20 49 4d 5f |SIZE) re|turn IM_|
|00004460| 49 4f 45 52 52 3b 0a 58 | 20 20 20 20 7d 0a 58 0a |IOERR;.X|    }.X.|
|00004470| 58 20 20 20 20 2f 2a 20 | 4b 65 65 70 20 74 68 65 |X    /* |Keep the|
|00004480| 20 63 75 72 72 65 6e 74 | 20 6d 61 74 63 68 20 61 | current| match a|
|00004490| 73 20 67 75 65 73 73 20 | 6f 6e 6c 79 20 69 66 20 |s guess |only if |
|000044a0| 69 74 73 20 6c 65 6e 67 | 74 68 20 69 73 20 73 6d |its leng|th is sm|
|000044b0| 61 6c 6c 2c 0a 58 20 20 | 20 20 20 2a 20 74 72 79 |all,.X  |   * try|
|000044c0| 69 6e 67 20 74 6f 20 66 | 69 6e 64 20 61 20 62 65 |ing to f|ind a be|
|000044d0| 74 74 65 72 20 6d 61 74 | 63 68 20 61 74 20 74 68 |tter mat|ch at th|
|000044e0| 65 20 6e 65 78 74 20 73 | 74 65 70 2e 20 49 66 20 |e next s|tep. If |
|000044f0| 73 70 65 65 64 20 69 73 | 20 6e 6f 74 0a 58 20 20 |speed is| not.X  |
|00004500| 20 20 20 2a 20 63 72 69 | 74 69 63 61 6c 2c 20 77 |   * cri|tical, w|
|00004510| 65 20 75 73 65 20 74 68 | 69 73 20 6c 61 7a 79 20 |e use th|is lazy |
|00004520| 6d 65 63 68 61 6e 69 73 | 6d 20 66 6f 72 20 61 6c |mechanis|m for al|
|00004530| 6c 20 6c 65 6e 67 74 68 | 73 2e 0a 58 20 20 20 20 |l length|s..X    |
|00004540| 20 2a 2f 0a 58 20 20 20 | 20 69 66 20 28 6d 61 5f | */.X   | if (ma_|
|00004550| 6c 65 6e 67 74 68 20 3e | 20 31 29 20 7b 0a 58 20 |length >| 1) {.X |
|00004560| 20 20 20 20 20 20 20 6d | 61 2d 3e 6d 61 5f 64 69 |       m|a->ma_di|
|00004570| 73 74 20 3d 20 6d 61 5f | 64 69 73 74 3b 0a 58 20 |st = ma_|dist;.X |
|00004580| 20 20 20 20 20 20 20 69 | 66 20 28 6d 61 5f 6c 65 |       i|f (ma_le|
|00004590| 6e 67 74 68 20 3c 3d 20 | 6d 61 78 5f 6c 61 7a 79 |ngth <= |max_lazy|
|000045a0| 5f 6d 61 74 63 68 29 20 | 7b 0a 58 20 20 20 20 20 |_match) |{.X     |
|000045b0| 20 20 20 20 20 20 2f 2a | 20 53 65 74 20 6d 61 5f |      /*| Set ma_|
|000045c0| 6c 69 74 63 5b 30 5d 3a | 20 74 68 69 73 20 69 73 |litc[0]:| this is|
|000045d0| 20 74 68 65 20 6f 6e 6c | 79 20 77 61 79 20 74 6f | the onl|y way to|
|000045e0| 20 69 64 65 6e 74 69 66 | 79 20 74 68 65 20 75 6e | identif|y the un|
|000045f0| 6d 61 74 63 68 65 64 0a | 58 20 20 20 20 20 20 20 |matched.|X       |
|00004600| 20 20 20 20 20 2a 20 64 | 61 74 61 20 69 66 20 74 |     * d|ata if t|
|00004610| 68 65 20 64 65 6c 61 79 | 65 64 20 6d 61 74 63 68 |he delay|ed match|
|00004620| 20 77 69 6c 6c 20 62 65 | 20 74 72 75 6e 63 61 74 | will be| truncat|
|00004630| 65 64 20 74 6f 20 31 2e | 20 49 74 20 69 73 20 61 |ed to 1.| It is a|
|00004640| 6c 73 6f 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |lso.X   |        |
|00004650| 20 2a 20 75 73 65 66 75 | 6c 20 69 66 20 6d 61 5f | * usefu|l if ma_|
|00004660| 6c 65 6e 67 74 68 20 3d | 3d 20 32 3a 20 69 74 20 |length =|= 2: it |
|00004670| 6d 61 79 20 62 65 20 6d | 6f 72 65 20 65 66 66 69 |may be m|ore effi|
|00004680| 63 69 65 6e 74 20 69 6e | 20 74 68 69 73 20 63 61 |cient in| this ca|
|00004690| 73 65 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |se.X    |        |
|000046a0| 2a 20 74 6f 20 65 6e 63 | 6f 64 65 20 74 68 65 20 |* to enc|ode the |
|000046b0| 69 6e 64 69 76 69 64 75 | 61 6c 20 63 68 61 72 61 |individu|al chara|
|000046c0| 63 74 65 72 73 20 72 61 | 74 68 65 72 20 74 68 61 |cters ra|ther tha|
|000046d0| 6e 20 74 68 65 20 6d 61 | 74 63 68 20 69 6e 66 6f |n the ma|tch info|
|000046e0| 2e 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 2a |..X     |       *|
|000046f0| 2f 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 6d |/.X     |       m|
|00004700| 61 2d 3e 6c 2e 6d 61 5f | 6c 69 74 63 5b 30 5d 20 |a->l.ma_|litc[0] |
|00004710| 3d 20 77 69 6e 64 6f 77 | 5b 73 74 72 73 74 61 72 |= window|[strstar|
|00004720| 74 5d 3b 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |t];.X   |        |
|00004730| 20 73 74 61 72 74 5f 6c | 65 6e 67 74 68 20 3d 20 | start_l|ength = |
|00004740| 6d 61 5f 6c 65 6e 67 74 | 68 3b 0a 58 20 20 20 20 |ma_lengt|h;.X    |
|00004750| 20 20 20 20 20 20 20 20 | 63 68 65 63 6b 70 6f 69 |        |checkpoi|
|00004760| 6e 74 20 3d 20 73 74 72 | 73 74 61 72 74 20 2b 20 |nt = str|start + |
|00004770| 31 3b 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |1;.X    |        |
|00004780| 72 65 74 75 72 6e 20 49 | 4d 5f 4f 4b 3b 0a 58 20 |return I|M_OK;.X |
|00004790| 20 20 20 20 20 20 20 7d | 0a 58 20 20 20 20 20 20 |       }|.X      |
|000047a0| 20 20 2f 2a 20 41 74 20 | 74 68 69 73 20 70 6f 69 |  /* At |this poi|
|000047b0| 6e 74 2c 20 6d 61 5f 6c | 65 6e 67 74 68 20 3e 3d |nt, ma_l|ength >=|
|000047c0| 20 33 2c 20 6e 6f 20 6e | 65 65 64 20 66 6f 72 20 | 3, no n|eed for |
|000047d0| 6d 61 5f 6c 69 74 63 20 | 2a 2f 0a 58 20 20 20 20 |ma_litc |*/.X    |
|000047e0| 20 20 20 20 6d 61 2d 3e | 6c 2e 6d 61 5f 6c 65 6e |    ma->|l.ma_len|
|000047f0| 67 74 68 20 3d 20 6d 61 | 5f 6c 65 6e 67 74 68 3b |gth = ma|_length;|
|00004800| 0a 58 20 20 20 20 20 20 | 20 20 63 68 65 63 6b 70 |.X      |  checkp|
|00004810| 6f 69 6e 74 20 3d 20 73 | 74 72 73 74 61 72 74 20 |oint = s|trstart |
|00004820| 2b 20 6d 61 5f 6c 65 6e | 67 74 68 3b 0a 58 20 20 |+ ma_len|gth;.X  |
|00004830| 20 20 7d 20 65 6c 73 65 | 20 7b 0a 58 20 20 20 20 |  } else| {.X    |
|00004840| 20 20 20 20 6d 61 2d 3e | 6d 61 5f 64 69 73 74 20 |    ma->|ma_dist |
|00004850| 3d 20 30 3b 0a 58 20 20 | 20 20 20 20 20 20 6d 61 |= 0;.X  |      ma|
|00004860| 2d 3e 6c 2e 6d 61 5f 6c | 69 74 63 5b 30 5d 20 3d |->l.ma_l|itc[0] =|
|00004870| 20 77 69 6e 64 6f 77 5b | 73 74 72 73 74 61 72 74 | window[|strstart|
|00004880| 5d 3b 20 2f 2a 20 6d 61 | 5f 6c 69 74 63 5b 31 5d |]; /* ma|_litc[1]|
|00004890| 20 69 73 20 6e 6f 74 20 | 72 65 71 75 69 72 65 64 | is not |required|
|000048a0| 20 2a 2f 0a 58 20 20 20 | 20 20 20 20 20 63 68 65 | */.X   |     che|
|000048b0| 63 6b 70 6f 69 6e 74 20 | 3d 20 73 74 72 73 74 61 |ckpoint |= strsta|
|000048c0| 72 74 20 2b 20 31 3b 0a | 58 20 20 20 20 7d 0a 58 |rt + 1;.|X    }.X|
|000048d0| 20 20 20 20 72 65 74 75 | 72 6e 20 63 74 5f 74 61 |    retu|rn ct_ta|
|000048e0| 6c 6c 79 20 28 6d 61 29 | 3b 0a 58 20 20 20 20 2f |lly (ma)|;.X    /|
|000048f0| 2a 20 4b 65 65 70 20 73 | 74 61 72 74 5f 6c 65 6e |* Keep s|tart_len|
|00004900| 67 74 68 20 3d 3d 20 31 | 20 2a 2f 0a 58 7d 0a 58 |gth == 1| */.X}.X|
|00004910| 0a 58 2f 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |.X/*****|********|
|00004920| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00004930| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00004940| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00004950| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 0a 58 20 2a 0a 58 |********|**.X *.X|
|00004960| 20 2a 20 44 65 74 65 72 | 6d 69 6e 65 20 74 68 65 | * Deter|mine the|
|00004970| 20 6d 69 6e 69 6d 75 6d | 20 6d 61 74 63 68 20 6c | minimum| match l|
|00004980| 65 6e 67 74 68 2c 20 62 | 61 73 65 64 20 6f 6e 20 |ength, b|ased on |
|00004990| 74 68 65 20 74 79 70 65 | 20 6f 66 20 64 61 74 61 |the type| of data|
|000049a0| 0a 58 20 2a 20 69 6e 20 | 74 68 65 20 67 69 76 65 |.X * in |the give|
|000049b0| 6e 20 69 6e 70 75 74 20 | 62 75 66 66 65 72 3a 20 |n input |buffer: |
|000049c0| 32 20 66 6f 72 20 62 69 | 6e 61 72 79 20 64 61 74 |2 for bi|nary dat|
|000049d0| 61 2c 20 33 20 6f 74 68 | 65 72 77 69 73 65 2e 20 |a, 3 oth|erwise. |
|000049e0| 53 65 74 20 61 6c 73 6f | 0a 58 20 2a 20 68 5f 73 |Set also|.X * h_s|
|000049f0| 68 69 66 74 20 61 63 63 | 6f 72 64 69 6e 67 20 74 |hift acc|ording t|
|00004a00| 6f 20 74 68 65 20 63 68 | 6f 73 65 6e 20 6d 69 6e |o the ch|osen min|
|00004a10| 5f 6d 61 74 63 68 5f 6c | 65 6e 67 74 68 2c 20 61 |_match_l|ength, a|
|00004a20| 6e 64 20 72 65 64 75 63 | 65 0a 58 20 2a 20 6d 61 |nd reduc|e.X * ma|
|00004a30| 78 5f 63 68 61 69 6e 5f | 6c 65 6e 67 74 68 20 66 |x_chain_|length f|
|00004a40| 6f 72 20 62 69 6e 61 72 | 79 20 66 69 6c 65 73 2e |or binar|y files.|
|00004a50| 0a 58 20 2a 20 20 20 20 | 49 66 20 74 68 65 20 67 |.X *    |If the g|
|00004a60| 75 65 73 73 20 61 62 6f | 75 74 20 64 61 74 61 20 |uess abo|ut data |
|00004a70| 74 79 70 65 20 69 73 20 | 77 72 6f 6e 67 2c 20 74 |type is |wrong, t|
|00004a80| 68 69 73 20 6f 6e 6c 79 | 20 61 66 66 65 63 74 73 |his only| affects|
|00004a90| 20 74 68 65 0a 58 20 2a | 20 63 6f 6d 70 72 65 73 | the.X *| compres|
|00004aa0| 73 69 6f 6e 20 72 61 74 | 69 6f 20 61 6e 64 20 73 |sion rat|io and s|
|00004ab0| 70 65 65 64 20 62 75 74 | 20 6e 6f 74 20 74 68 65 |peed but| not the|
|00004ac0| 20 63 6f 72 72 65 63 74 | 6e 65 73 73 20 6f 66 20 | correct|ness of |
|00004ad0| 74 68 65 20 61 6c 67 6f | 72 69 74 68 6d 73 2e 0a |the algo|rithms..|
|00004ae0| 58 20 2a 20 49 66 20 74 | 68 65 72 65 20 61 72 65 |X * If t|here are|
|00004af0| 20 6d 6f 72 65 20 74 68 | 61 6e 20 32 30 25 20 62 | more th|an 20% b|
|00004b00| 79 74 65 73 20 77 68 69 | 63 68 20 73 65 65 6d 20 |ytes whi|ch seem |
|00004b10| 6e 6f 6e 20 61 73 63 69 | 69 20 69 6e 20 74 68 65 |non asci|i in the|
|00004b20| 20 66 69 72 73 74 0a 58 | 20 2a 20 35 30 30 20 62 | first.X| * 500 b|
|00004b30| 79 74 65 73 2c 20 77 65 | 20 61 73 73 75 6d 65 20 |ytes, we| assume |
|00004b40| 74 68 61 74 20 74 68 65 | 20 64 61 74 61 20 69 73 |that the| data is|
|00004b50| 20 62 69 6e 61 72 79 2e | 20 28 57 65 20 61 63 63 | binary.| (We acc|
|00004b60| 65 70 74 20 64 61 74 61 | 0a 58 20 2a 20 77 69 74 |ept data|.X * wit|
|00004b70| 68 20 61 20 66 65 77 20 | 68 69 67 68 20 62 69 74 |h a few |high bit|
|00004b80| 73 20 73 65 74 20 61 73 | 20 61 73 63 69 69 20 74 |s set as| ascii t|
|00004b90| 6f 20 74 61 6b 65 20 69 | 6e 74 6f 20 61 63 63 6f |o take i|nto acco|
|00004ba0| 75 6e 74 20 73 70 65 63 | 69 61 6c 0a 58 20 2a 20 |unt spec|ial.X * |
|00004bb0| 77 6f 72 64 20 70 72 6f | 63 65 73 73 6f 72 20 66 |word pro|cessor f|
|00004bc0| 6f 72 6d 61 74 73 2e 29 | 0a 58 20 2a 2f 0a 73 74 |ormats.)|.X */.st|
|00004bd0| 61 74 69 63 20 76 6f 69 | 64 20 73 65 74 5f 6d 69 |atic voi|d set_mi|
|00004be0| 6e 5f 6d 61 74 63 68 5f | 6c 65 6e 67 74 68 20 28 |n_match_|length (|
|00004bf0| 62 6c 6f 63 6b 2c 20 63 | 6f 75 6e 74 29 0a 58 20 |block, c|ount).X |
|00004c00| 20 20 20 55 5f 43 48 41 | 52 20 2a 62 6c 6f 63 6b |   U_CHA|R *block|
|00004c10| 3b 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 69 6e |;       |   /* in|
|00004c20| 70 75 74 20 64 61 74 61 | 20 2a 2f 0a 58 20 20 20 |put data| */.X   |
|00004c30| 20 55 5f 49 4e 54 20 20 | 63 6f 75 6e 74 3b 20 20 | U_INT  |count;  |
|00004c40| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 23 20 6f 66 |        | /* # of|
|00004c50| 20 69 6e 70 75 74 20 63 | 68 61 72 27 73 20 2a 2f | input c|har's */|
|00004c60| 0a 58 7b 0a 58 20 20 20 | 20 69 6e 74 20 6e 6f 6e |.X{.X   | int non|
|00004c70| 5f 61 73 63 69 69 20 3d | 20 30 3b 0a 58 20 20 20 |_ascii =| 0;.X   |
|00004c80| 20 6d 69 6e 5f 6d 61 74 | 63 68 5f 6c 65 6e 67 74 | min_mat|ch_lengt|
|00004c90| 68 20 3d 20 33 3b 20 20 | 2f 2a 20 44 65 66 61 75 |h = 3;  |/* Defau|
|00004ca0| 6c 74 20 61 73 63 69 69 | 20 2a 2f 0a 58 20 20 20 |lt ascii| */.X   |
|00004cb0| 20 69 66 20 28 63 6f 75 | 6e 74 20 3e 3d 20 35 30 | if (cou|nt >= 50|
|00004cc0| 30 29 20 7b 0a 58 20 20 | 20 20 20 20 20 20 63 6f |0) {.X  |      co|
|00004cd0| 75 6e 74 20 3d 20 35 30 | 30 3b 0a 58 20 20 20 20 |unt = 50|0;.X    |
|00004ce0| 20 20 20 20 77 68 69 6c | 65 20 28 2d 2d 63 6f 75 |    whil|e (--cou|
|00004cf0| 6e 74 20 21 3d 20 30 29 | 20 7b 0a 58 20 20 20 20 |nt != 0)| {.X    |
|00004d00| 20 20 20 20 20 20 20 20 | 69 66 20 28 2a 62 6c 6f |        |if (*blo|
|00004d10| 63 6b 20 3c 3d 20 36 20 | 7c 7c 20 2a 62 6c 6f 63 |ck <= 6 ||| *bloc|
|00004d20| 6b 20 3e 3d 20 30 78 38 | 30 29 20 6e 6f 6e 5f 61 |k >= 0x8|0) non_a|
|00004d30| 73 63 69 69 2b 2b 3b 0a | 58 20 20 20 20 20 20 20 |scii++;.|X       |
|00004d40| 20 20 20 20 20 62 6c 6f | 63 6b 2b 2b 3b 0a 58 20 |     blo|ck++;.X |
|00004d50| 20 20 20 20 20 20 20 7d | 0a 58 20 20 20 20 20 20 |       }|.X      |
|00004d60| 20 20 69 66 20 28 6e 6f | 6e 5f 61 73 63 69 69 20 |  if (no|n_ascii |
|00004d70| 3e 20 31 30 30 29 20 7b | 0a 58 20 20 20 20 20 20 |> 100) {|.X      |
|00004d80| 20 20 20 20 20 20 6d 69 | 6e 5f 6d 61 74 63 68 5f |      mi|n_match_|
|00004d90| 6c 65 6e 67 74 68 20 3d | 20 32 3b 0a 58 20 20 20 |length =| 2;.X   |
|00004da0| 20 20 20 20 20 20 20 20 | 20 6d 61 78 5f 63 68 61 |        | max_cha|
|00004db0| 69 6e 5f 6c 65 6e 67 74 | 68 20 3e 3e 3d 20 32 3b |in_lengt|h >>= 2;|
|00004dc0| 0a 58 20 20 20 20 20 20 | 20 20 7d 0a 58 20 20 20 |.X      |  }.X   |
|00004dd0| 20 7d 0a 58 20 20 20 20 | 68 5f 73 68 69 66 74 20 | }.X    |h_shift |
|00004de0| 3d 20 28 48 41 53 48 5f | 42 49 54 53 2b 6d 69 6e |= (HASH_|BITS+min|
|00004df0| 5f 6d 61 74 63 68 5f 6c | 65 6e 67 74 68 2d 31 29 |_match_l|ength-1)|
|00004e00| 2f 6d 69 6e 5f 6d 61 74 | 63 68 5f 6c 65 6e 67 74 |/min_mat|ch_lengt|
|00004e10| 68 3b 0a 58 23 69 66 64 | 65 66 20 44 45 42 55 47 |h;.X#ifd|ef DEBUG|
|00004e20| 0a 58 20 20 20 20 66 70 | 72 69 6e 74 66 28 73 74 |.X    fp|rintf(st|
|00004e30| 64 65 72 72 2c 22 20 28 | 6d 69 6e 5f 6d 61 74 63 |derr," (|min_matc|
|00004e40| 68 5f 6c 65 6e 67 74 68 | 20 25 64 29 20 22 2c 20 |h_length| %d) ", |
|00004e50| 6d 69 6e 5f 6d 61 74 63 | 68 5f 6c 65 6e 67 74 68 |min_matc|h_length|
|00004e60| 29 3b 0a 58 23 65 6e 64 | 69 66 0a 58 7d 0a 58 0a |);.X#end|if.X}.X.|
|00004e70| 58 2f 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |X/******|********|
|00004e80| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00004e90| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00004ea0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00004eb0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 0a 58 20 2a 0a 58 20 |********|*.X *.X |
|00004ec0| 2a 20 49 6e 73 65 72 74 | 20 73 74 72 69 6e 67 20 |* Insert| string |
|00004ed0| 73 20 69 6e 20 74 68 65 | 20 64 69 63 74 69 6f 6e |s in the| diction|
|00004ee0| 61 72 79 20 61 6e 64 20 | 73 65 74 20 6c 61 73 74 |ary and |set last|
|00004ef0| 5f 6d 61 74 63 68 20 74 | 6f 20 74 68 65 20 70 72 |_match t|o the pr|
|00004f00| 65 76 69 6f 75 73 20 68 | 65 61 64 0a 58 20 2a 20 |evious h|ead.X * |
|00004f10| 6f 66 20 74 68 65 20 68 | 61 73 68 20 63 68 61 69 |of the h|ash chai|
|00004f20| 6e 20 28 74 68 65 20 6d | 6f 73 74 20 72 65 63 65 |n (the m|ost rece|
|00004f30| 6e 74 20 73 74 72 69 6e | 67 20 77 69 74 68 20 73 |nt strin|g with s|
|00004f40| 61 6d 65 20 68 61 73 68 | 20 6b 65 79 29 2e 0a 58 |ame hash| key)..X|
|00004f50| 20 2a 20 49 4e 20 20 61 | 73 73 65 72 74 69 6f 6e | * IN  a|ssertion|
|00004f60| 3a 20 61 6c 6c 20 63 61 | 6c 6c 73 20 74 6f 20 74 |: all ca|lls to t|
|00004f70| 6f 20 49 4e 53 45 52 54 | 5f 53 54 52 49 4e 47 20 |o INSERT|_STRING |
|00004f80| 61 72 65 20 6d 61 64 65 | 20 77 69 74 68 20 63 6f |are made| with co|
|00004f90| 6e 73 65 63 75 74 69 76 | 65 0a 58 20 2a 20 20 20 |nsecutiv|e.X *   |
|00004fa0| 20 69 6e 70 75 74 20 63 | 68 61 72 61 63 74 65 72 | input c|haracter|
|00004fb0| 73 2c 20 73 6f 20 74 68 | 61 74 20 61 20 72 75 6e |s, so th|at a run|
|00004fc0| 6e 69 6e 67 20 68 61 73 | 68 20 6b 65 79 20 63 61 |ning has|h key ca|
|00004fd0| 6e 20 62 65 20 63 6f 6d | 70 75 74 65 64 20 66 72 |n be com|puted fr|
|00004fe0| 6f 6d 20 74 68 65 0a 58 | 20 2a 20 20 20 20 70 72 |om the.X| *    pr|
|00004ff0| 65 76 69 6f 75 73 20 6b | 65 79 20 69 6e 73 74 65 |evious k|ey inste|
|00005000| 61 64 20 6f 66 20 63 6f | 6d 70 6c 65 74 65 20 72 |ad of co|mplete r|
|00005010| 65 63 61 6c 63 75 6c 61 | 74 69 6f 6e 20 65 61 63 |ecalcula|tion eac|
|00005020| 68 20 74 69 6d 65 2e 0a | 58 20 2a 2f 0a 58 23 64 |h time..|X */.X#d|
|00005030| 65 66 69 6e 65 20 49 4e | 53 45 52 54 5f 53 54 52 |efine IN|SERT_STR|
|00005040| 49 4e 47 28 73 2c 20 6c | 61 73 74 5f 6d 61 74 63 |ING(s, l|ast_matc|
|00005050| 68 29 20 5c 0a 58 7b 20 | 5c 0a 58 20 20 20 20 69 |h) \.X{ |\.X    i|
|00005060| 6e 73 5f 68 20 3d 20 28 | 28 69 6e 73 5f 68 3c 3c |ns_h = (|(ins_h<<|
|00005070| 68 5f 73 68 69 66 74 29 | 20 5e 20 77 69 6e 64 6f |h_shift)| ^ windo|
|00005080| 77 5b 73 20 2b 20 6d 69 | 6e 5f 6d 61 74 63 68 5f |w[s + mi|n_match_|
|00005090| 6c 65 6e 67 74 68 2d 31 | 5d 29 20 26 20 48 41 53 |length-1|]) & HAS|
|000050a0| 48 5f 4d 41 53 4b 3b 20 | 5c 0a 58 20 20 20 20 70 |H_MASK; |\.X    p|
|000050b0| 72 65 76 5b 73 5d 20 3d | 20 6c 61 73 74 5f 6d 61 |rev[s] =| last_ma|
|000050c0| 74 63 68 20 3d 20 6d 61 | 74 63 68 5f 68 65 61 64 |tch = ma|tch_head|
|000050d0| 5b 69 6e 73 5f 68 5d 3b | 20 5c 0a 58 20 20 20 20 |[ins_h];| \.X    |
|000050e0| 6e 65 78 74 5b 6c 61 73 | 74 5f 6d 61 74 63 68 5d |next[las|t_match]|
|000050f0| 20 3d 20 70 72 65 76 5b | 6e 65 78 74 5b 73 5d 20 | = prev[|next[s] |
|00005100| 3d 20 69 6e 73 5f 68 20 | 2b 20 4d 41 58 5f 44 49 |= ins_h |+ MAX_DI|
|00005110| 53 54 2b 31 5d 20 3d 20 | 73 3b 20 5c 0a 58 7d 0a |ST+1] = |s; \.X}.|
|00005120| 58 20 20 20 20 2f 2a 20 | 6e 65 78 74 5b 4e 49 4c |X    /* |next[NIL|
|00005130| 5d 20 69 73 20 67 61 72 | 62 61 67 65 2c 20 77 65 |] is gar|bage, we|
|00005140| 20 63 61 6e 20 6f 76 65 | 72 77 72 69 74 65 20 69 | can ove|rwrite i|
|00005150| 74 20 69 66 20 73 20 69 | 73 20 61 20 74 61 69 6c |t if s i|s a tail|
|00005160| 20 2a 2f 0a 58 0a 58 2f | 2a 2a 2a 2a 2a 2a 2a 2a | */.X.X/|********|
|00005170| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00005180| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00005190| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000051a0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 0a |********|*******.|
|000051b0| 58 20 2a 0a 58 20 2a 20 | 52 65 6d 6f 76 65 20 73 |X *.X * |Remove s|
|000051c0| 74 72 69 6e 67 20 73 20 | 66 72 6f 6d 20 74 68 65 |tring s |from the|
|000051d0| 20 64 69 63 74 69 6f 6e | 61 72 79 2c 20 6f 72 20 | diction|ary, or |
|000051e0| 64 6f 20 6e 6f 74 68 69 | 6e 67 20 69 66 20 73 20 |do nothi|ng if s |
|000051f0| 69 73 20 6e 6f 74 20 79 | 65 74 0a 58 20 2a 20 69 |is not y|et.X * i|
|00005200| 6e 20 74 68 65 20 64 69 | 63 74 69 6f 6e 61 72 79 |n the di|ctionary|
|00005210| 2e 0a 58 20 2a 20 49 4e | 20 61 73 73 65 72 74 69 |..X * IN| asserti|
|00005220| 6f 6e 3a 20 73 20 69 73 | 20 74 68 65 20 74 61 69 |on: s is| the tai|
|00005230| 6c 20 6f 66 20 69 74 73 | 20 68 61 73 68 20 63 68 |l of its| hash ch|
|00005240| 61 69 6e 20 28 74 68 65 | 20 6f 6c 64 65 73 74 20 |ain (the| oldest |
|00005250| 73 74 72 69 6e 67 29 2e | 0a 58 20 2a 2f 0a 58 23 |string).|.X */.X#|
|00005260| 64 65 66 69 6e 65 20 44 | 45 4c 45 54 45 5f 53 54 |define D|ELETE_ST|
|00005270| 52 49 4e 47 28 73 29 20 | 20 7b 70 72 65 76 5b 6e |RING(s) | {prev[n|
|00005280| 65 78 74 5b 73 5d 5d 20 | 3d 20 4e 49 4c 3b 7d 0a |ext[s]] |= NIL;}.|
|00005290| 58 2f 2a 20 4e 6f 20 65 | 66 66 65 63 74 20 69 66 |X/* No e|ffect if|
|000052a0| 20 6e 65 78 74 5b 73 5d | 20 3d 3d 20 4e 49 4c 20 | next[s]| == NIL |
|000052b0| 28 73 20 6e 6f 74 20 69 | 6e 20 64 69 63 74 69 6f |(s not i|n dictio|
|000052c0| 6e 61 72 79 29 20 2a 2f | 0a 58 0a 58 2f 2a 2a 2a |nary) */|.X.X/***|
|000052d0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000052e0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000052f0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00005300| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00005310| 2a 2a 2a 2a 0a 58 20 2a | 0a 58 20 2a 20 46 69 6e |****.X *|.X * Fin|
|00005320| 64 20 74 68 65 20 6c 6f | 6e 67 65 73 74 20 6d 61 |d the lo|ngest ma|
|00005330| 74 63 68 20 73 74 61 72 | 74 69 6e 67 20 61 74 20 |tch star|ting at |
|00005340| 74 68 65 20 67 69 76 65 | 6e 20 73 74 72 69 6e 67 |the give|n string|
|00005350| 2e 20 52 65 74 75 72 6e | 20 69 74 73 20 70 6f 73 |. Return| its pos|
|00005360| 69 74 69 6f 6e 0a 58 20 | 2a 20 61 6e 64 20 73 65 |ition.X |* and se|
|00005370| 74 20 69 74 73 20 6c 65 | 6e 67 74 68 20 69 6e 20 |t its le|ngth in |
|00005380| 6d 61 74 63 68 5f 6c 65 | 6e 67 74 68 2e 20 4d 61 |match_le|ngth. Ma|
|00005390| 74 63 68 65 73 20 73 68 | 6f 72 74 65 72 20 6f 72 |tches sh|orter or|
|000053a0| 20 65 71 75 61 6c 20 74 | 6f 0a 58 20 2a 20 73 74 | equal t|o.X * st|
|000053b0| 61 72 74 5f 6c 65 6e 67 | 74 68 20 61 72 65 20 64 |art_leng|th are d|
|000053c0| 69 73 63 61 72 64 65 64 | 2c 20 69 6e 20 77 68 69 |iscarded|, in whi|
|000053d0| 63 68 20 63 61 73 65 20 | 6d 61 74 63 68 5f 6c 65 |ch case |match_le|
|000053e0| 6e 67 74 68 20 69 73 20 | 75 6e 63 68 61 6e 67 65 |ngth is |unchange|
|000053f0| 64 0a 58 20 2a 20 61 6e | 64 20 74 68 65 20 72 65 |d.X * an|d the re|
|00005400| 73 75 6c 74 20 70 6f 73 | 69 74 69 6f 6e 20 69 73 |sult pos|ition is|
|00005410| 20 4e 49 4c 2e 0a 58 20 | 2a 20 49 4e 20 61 73 73 | NIL..X |* IN ass|
|00005420| 65 72 74 69 6f 6e 73 3a | 20 63 75 72 5f 6d 61 74 |ertions:| cur_mat|
|00005430| 63 68 20 69 73 20 74 68 | 65 20 68 65 61 64 20 6f |ch is th|e head o|
|00005440| 66 20 74 68 65 20 68 61 | 73 68 20 63 68 61 69 6e |f the ha|sh chain|
|00005450| 20 66 6f 72 20 74 68 65 | 20 63 75 72 72 65 6e 74 | for the| current|
|00005460| 0a 58 20 2a 20 20 20 73 | 74 72 69 6e 67 20 28 73 |.X *   s|tring (s|
|00005470| 74 72 73 74 61 72 74 29 | 20 61 6e 64 20 69 73 20 |trstart)| and is |
|00005480| 6e 6f 74 20 4e 49 4c 2c | 20 61 6e 64 20 73 74 61 |not NIL,| and sta|
|00005490| 72 74 5f 6c 65 6e 67 74 | 68 20 3e 3d 20 31 0a 58 |rt_lengt|h >= 1.X|
|000054a0| 20 2a 2f 0a 58 23 69 66 | 20 21 64 65 66 69 6e 65 | */.X#if| !define|
|000054b0| 64 28 4d 53 44 4f 53 29 | 20 7c 7c 20 64 65 66 69 |d(MSDOS)| || defi|
|000054c0| 6e 65 64 28 4e 4f 5f 41 | 53 4d 29 0a 58 2f 2a 20 |ned(NO_A|SM).X/* |
|000054d0| 46 6f 72 20 4d 53 44 4f | 53 2c 20 61 20 76 65 72 |For MSDO|S, a ver|
|000054e0| 73 69 6f 6e 20 6f 66 20 | 74 68 69 73 20 72 6f 75 |sion of |this rou|
|000054f0| 74 69 6e 65 20 77 72 69 | 74 74 65 6e 20 69 6e 20 |tine wri|tten in |
|00005500| 61 73 73 65 6d 62 6c 65 | 72 20 69 73 20 69 6e 20 |assemble|r is in |
|00005510| 69 6d 5f 6c 6d 2e 61 73 | 6d 2e 0a 58 20 2a 20 54 |im_lm.as|m..X * T|
|00005520| 68 65 20 61 6c 67 6f 72 | 69 74 68 6d 73 20 61 72 |he algor|ithms ar|
|00005530| 65 20 73 74 72 69 63 74 | 6c 79 20 65 71 75 69 76 |e strict|ly equiv|
|00005540| 61 6c 65 6e 74 2c 20 73 | 6f 20 74 68 65 20 43 20 |alent, s|o the C |
|00005550| 76 65 72 73 69 6f 6e 20 | 63 61 6e 20 62 65 20 75 |version |can be u|
|00005560| 73 65 64 0a 58 20 2a 20 | 69 6e 73 74 65 61 64 20 |sed.X * |instead |
|00005570| 69 66 20 79 6f 75 20 64 | 6f 20 6e 6f 74 20 68 61 |if you d|o not ha|
|00005580| 76 65 20 6d 61 73 6d 20 | 6f 72 20 74 61 73 6d 2e |ve masm |or tasm.|
|00005590| 20 28 55 70 64 61 74 65 | 20 74 68 65 20 6d 61 6b | (Update| the mak|
|000055a0| 65 66 69 6c 65 20 69 6e | 20 74 68 69 73 20 63 61 |efile in| this ca|
|000055b0| 73 65 2e 29 0a 58 20 2a | 2f 0a 49 50 6f 73 20 6c |se.).X *|/.IPos l|
|000055c0| 6f 6e 67 65 73 74 5f 6d | 61 74 63 68 28 63 75 72 |ongest_m|atch(cur|
|000055d0| 5f 6d 61 74 63 68 29 0a | 58 20 20 20 20 49 50 6f |_match).|X    IPo|
|000055e0| 73 20 63 75 72 5f 6d 61 | 74 63 68 3b 0a 58 7b 0a |s cur_ma|tch;.X{.|
|000055f0| 58 20 20 20 20 72 65 67 | 69 73 74 65 72 20 55 5f |X    reg|ister U_|
|00005600| 43 48 41 52 20 2a 6d 61 | 74 63 68 3b 20 20 20 20 |CHAR *ma|tch;    |
|00005610| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2f |        |       /|
|00005620| 2a 20 70 6f 69 6e 74 65 | 72 20 69 6e 20 6d 61 74 |* pointe|r in mat|
|00005630| 63 68 65 64 20 73 74 72 | 69 6e 67 20 2a 2f 0a 58 |ched str|ing */.X|
|00005640| 20 20 20 20 72 65 67 69 | 73 74 65 72 20 55 5f 43 |    regi|ster U_C|
|00005650| 48 41 52 20 2a 73 63 61 | 6e 20 3d 20 77 69 6e 64 |HAR *sca|n = wind|
|00005660| 6f 77 20 2b 20 73 74 72 | 73 74 61 72 74 3b 2f 2a |ow + str|start;/*|
|00005670| 20 70 6f 69 6e 74 65 72 | 20 69 6e 20 63 75 72 72 | pointer| in curr|
|00005680| 65 6e 74 20 73 74 72 69 | 6e 67 20 2a 2f 0a 58 20 |ent stri|ng */.X |
|00005690| 20 20 20 72 65 67 69 73 | 74 65 72 20 69 6e 74 20 |   regis|ter int |
|000056a0| 6c 65 6e 3b 20 20 20 20 | 20 20 20 20 20 20 20 20 |len;    |        |
|000056b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2f 2a 20 |        |     /* |
|000056c0| 6c 65 6e 67 74 68 20 6f | 66 20 63 75 72 72 65 6e |length o|f curren|
|000056d0| 74 20 6d 61 74 63 68 20 | 2a 2f 0a 58 20 20 20 20 |t match |*/.X    |
|000056e0| 49 50 6f 73 20 63 75 72 | 5f 62 65 73 74 20 3d 20 |IPos cur|_best = |
|000056f0| 4e 49 4c 3b 20 20 20 20 | 20 20 20 20 20 20 20 20 |NIL;    |        |
|00005700| 20 20 20 20 20 20 20 20 | 20 20 2f 2a 20 62 65 73 |        |  /* bes|
|00005710| 74 20 6d 61 74 63 68 20 | 73 6f 20 66 61 72 20 2a |t match |so far *|
|00005720| 2f 0a 58 20 20 20 20 72 | 65 67 69 73 74 65 72 20 |/.X    r|egister |
|00005730| 69 6e 74 20 6d 61 5f 6c | 65 6e 67 74 68 20 3d 20 |int ma_l|ength = |
|00005740| 73 74 61 72 74 5f 6c 65 | 6e 67 74 68 3b 20 20 20 |start_le|ngth;   |
|00005750| 20 2f 2a 20 62 65 73 74 | 20 6d 61 74 63 68 20 6c | /* best| match l|
|00005760| 65 6e 67 74 68 20 73 6f | 20 66 61 72 20 2a 2f 0a |ength so| far */.|
|00005770| 58 20 20 20 20 69 6e 74 | 20 63 68 61 69 6e 5f 63 |X    int| chain_c|
|00005780| 6f 75 6e 74 20 3d 20 6d | 61 78 5f 63 68 61 69 6e |ount = m|ax_chain|
|00005790| 5f 6c 65 6e 67 74 68 3b | 20 20 20 20 20 20 20 2f |_length;|       /|
|000057a0| 2a 20 75 73 65 64 20 74 | 6f 20 6c 69 6d 69 74 20 |* used t|o limit |
|000057b0| 68 61 73 68 20 63 68 61 | 69 6e 73 20 2a 2f 0a 58 |hash cha|ins */.X|
|000057c0| 20 20 20 20 74 79 70 65 | 64 65 66 20 75 6e 73 69 |    type|def unsi|
|000057d0| 67 6e 65 64 20 73 68 6f | 72 74 20 55 53 3b 0a 58 |gned sho|rt US;.X|
|000057e0| 20 20 20 20 74 79 70 65 | 64 65 66 20 75 6e 73 69 |    type|def unsi|
|000057f0| 67 6e 65 64 20 6c 6f 6e | 67 20 20 55 4c 3b 0a 58 |gned lon|g  UL;.X|
|00005800| 23 69 66 64 65 66 20 55 | 4e 41 4c 49 47 4e 45 44 |#ifdef U|NALIGNED|
|00005810| 5f 4f 4b 0a 58 20 20 20 | 20 72 65 67 69 73 74 65 |_OK.X   | registe|
|00005820| 72 20 55 53 20 73 63 61 | 6e 5f 73 74 61 72 74 20 |r US sca|n_start |
|00005830| 3d 20 2a 28 55 53 2a 29 | 73 63 61 6e 3b 0a 58 20 |= *(US*)|scan;.X |
|00005840| 20 20 20 72 65 67 69 73 | 74 65 72 20 55 53 20 73 |   regis|ter US s|
|00005850| 63 61 6e 5f 65 6e 64 20 | 20 20 3d 20 2a 28 55 53 |can_end |  = *(US|
|00005860| 2a 29 28 73 63 61 6e 2b | 6d 61 5f 6c 65 6e 67 74 |*)(scan+|ma_lengt|
|00005870| 68 2d 31 29 3b 0a 58 23 | 65 6c 73 65 0a 58 20 20 |h-1);.X#|else.X  |
|00005880| 20 20 72 65 67 69 73 74 | 65 72 20 55 5f 43 48 41 |  regist|er U_CHA|
|00005890| 52 20 73 63 61 6e 5f 73 | 74 61 72 74 20 3d 20 2a |R scan_s|tart = *|
|000058a0| 73 63 61 6e 3b 0a 58 20 | 20 20 20 72 65 67 69 73 |scan;.X |   regis|
|000058b0| 74 65 72 20 55 5f 43 48 | 41 52 20 73 63 61 6e 5f |ter U_CH|AR scan_|
|000058c0| 65 6e 64 31 20 20 3d 20 | 73 63 61 6e 5b 6d 61 5f |end1  = |scan[ma_|
|000058d0| 6c 65 6e 67 74 68 2d 31 | 5d 3b 0a 58 20 20 20 20 |length-1|];.X    |
|000058e0| 72 65 67 69 73 74 65 72 | 20 55 5f 43 48 41 52 20 |register| U_CHAR |
|000058f0| 73 63 61 6e 5f 65 6e 64 | 20 20 20 3d 20 73 63 61 |scan_end|   = sca|
|00005900| 6e 5b 6d 61 5f 6c 65 6e | 67 74 68 5d 3b 0a 58 23 |n[ma_len|gth];.X#|
|00005910| 65 6e 64 69 66 0a 58 20 | 20 20 20 64 6f 20 7b 0a |endif.X |   do {.|
|00005920| 58 20 20 20 20 20 20 20 | 20 6d 61 74 63 68 20 3d |X       | match =|
|00005930| 20 77 69 6e 64 6f 77 20 | 2b 20 63 75 72 5f 6d 61 | window |+ cur_ma|
|00005940| 74 63 68 3b 0a 58 20 20 | 20 20 20 20 20 20 2f 2a |tch;.X  |      /*|
|00005950| 20 53 6b 69 70 20 74 6f | 20 6e 65 78 74 20 6d 61 | Skip to| next ma|
|00005960| 74 63 68 20 69 66 20 74 | 68 65 20 6d 61 74 63 68 |tch if t|he match|
|00005970| 20 6c 65 6e 67 74 68 20 | 63 61 6e 6e 6f 74 20 69 | length |cannot i|
|00005980| 6e 63 72 65 61 73 65 0a | 58 20 20 20 20 20 20 20 |ncrease.|X       |
|00005990| 20 20 2a 20 6f 72 20 69 | 66 20 74 68 65 20 6d 61 |  * or i|f the ma|
|000059a0| 74 63 68 20 6c 65 6e 67 | 74 68 20 69 73 20 6c 65 |tch leng|th is le|
|000059b0| 73 73 20 74 68 61 6e 20 | 32 3a 0a 58 20 20 20 20 |ss than |2:.X    |
|000059c0| 20 20 20 20 20 2a 2f 0a | 58 23 69 66 64 65 66 20 |     */.|X#ifdef |
|000059d0| 55 4e 41 4c 49 47 4e 45 | 44 5f 4f 4b 0a 58 20 20 |UNALIGNE|D_OK.X  |
|000059e0| 20 20 20 20 20 20 2f 2a | 20 54 68 69 73 20 63 6f |      /*| This co|
|000059f0| 64 65 20 61 73 73 75 6d | 65 73 20 73 69 7a 65 6f |de assum|es sizeo|
|00005a00| 66 28 75 6e 73 69 67 6e | 65 64 20 73 68 6f 72 74 |f(unsign|ed short|
|00005a10| 29 20 3d 3d 20 32 20 61 | 6e 64 0a 58 20 20 20 20 |) == 2 a|nd.X    |
|00005a20| 20 20 20 20 20 2a 20 73 | 69 7a 65 6f 66 28 75 6e |     * s|izeof(un|
|00005a30| 73 69 67 6e 65 64 20 6c | 6f 6e 67 29 20 3d 3d 20 |signed l|ong) == |
|00005a40| 34 2e 20 44 6f 20 6e 6f | 74 20 75 73 65 20 55 4e |4. Do no|t use UN|
|00005a50| 41 4c 49 47 4e 45 44 5f | 4f 4b 20 69 66 20 79 6f |ALIGNED_|OK if yo|
|00005a60| 75 72 0a 58 20 20 20 20 | 20 20 20 20 20 2a 20 63 |ur.X    |     * c|
|00005a70| 6f 6d 70 69 6c 65 72 20 | 75 73 65 73 20 64 69 66 |ompiler |uses dif|
|00005a80| 66 65 72 65 6e 74 20 73 | 69 7a 65 73 2e 0a 58 20 |ferent s|izes..X |
|00005a90| 20 20 20 20 20 20 20 20 | 2a 2f 0a 58 20 20 20 20 |        |*/.X    |
|00005aa0| 20 20 20 20 69 66 20 28 | 2a 28 55 53 2a 29 28 6d |    if (|*(US*)(m|
|00005ab0| 61 74 63 68 2b 6d 61 5f | 6c 65 6e 67 74 68 2d 31 |atch+ma_|length-1|
|00005ac0| 29 20 21 3d 20 73 63 61 | 6e 5f 65 6e 64 20 7c 7c |) != sca|n_end |||
|00005ad0| 0a 58 20 20 20 20 20 20 | 20 20 20 20 20 20 2a 28 |.X      |      *(|
|00005ae0| 55 53 2a 29 6d 61 74 63 | 68 20 21 3d 20 73 63 61 |US*)matc|h != sca|
|00005af0| 6e 5f 73 74 61 72 74 29 | 20 63 6f 6e 74 69 6e 75 |n_start)| continu|
|00005b00| 65 3b 0a 58 0a 58 20 20 | 20 20 20 20 20 20 6c 65 |e;.X.X  |      le|
|00005b10| 6e 20 3d 20 6d 69 6e 5f | 6d 61 74 63 68 5f 6c 65 |n = min_|match_le|
|00005b20| 6e 67 74 68 20 2d 20 34 | 3b 0a 58 20 20 20 20 20 |ngth - 4|;.X     |
|00005b30| 20 20 20 2f 2a 20 49 66 | 20 6d 69 6e 5f 6d 61 74 |   /* If| min_mat|
|00005b40| 63 68 5f 6c 65 6e 67 74 | 68 20 3d 3d 20 33 2c 20 |ch_lengt|h == 3, |
|00005b50| 69 74 20 69 73 20 6e 6f | 74 20 6e 65 63 65 73 73 |it is no|t necess|
|00005b60| 61 72 79 20 74 6f 20 63 | 6f 6d 70 61 72 65 0a 58 |ary to c|ompare.X|
|00005b70| 20 20 20 20 20 20 20 20 | 20 2a 20 73 63 61 6e 5b |        | * scan[|
|00005b80| 32 5d 20 61 6e 64 20 6d | 61 74 63 68 5b 32 5d 20 |2] and m|atch[2] |
|00005b90| 73 69 6e 63 65 20 74 68 | 65 79 20 61 72 65 20 61 |since th|ey are a|
|00005ba0| 6c 77 61 79 73 20 65 71 | 75 61 6c 20 77 68 65 6e |lways eq|ual when|
|00005bb0| 20 74 68 65 20 6f 74 68 | 65 72 0a 58 20 20 20 20 | the oth|er.X    |
|00005bc0| 20 20 20 20 20 2a 20 62 | 79 74 65 73 20 6d 61 74 |     * b|ytes mat|
|00005bd0| 63 68 2c 20 67 69 76 65 | 6e 20 74 68 61 74 20 74 |ch, give|n that t|
|00005be0| 68 65 20 68 61 73 68 20 | 6b 65 79 73 20 61 72 65 |he hash |keys are|
|00005bf0| 20 65 71 75 61 6c 20 61 | 6e 64 20 74 68 61 74 0a | equal a|nd that.|
|00005c00| 58 20 20 20 20 20 20 20 | 20 20 2a 20 48 41 53 48 |X       |  * HASH|
|00005c10| 5f 42 49 54 53 20 3e 3d | 20 38 2e 0a 58 20 20 20 |_BITS >=| 8..X   |
|00005c20| 20 20 20 20 20 20 2a 2f | 0a 58 23 20 20 20 20 20 |      */|.X#     |
|00005c30| 20 20 64 65 66 69 6e 65 | 20 4d 4c 20 4d 41 58 5f |  define| ML MAX_|
|00005c40| 4d 41 54 43 48 5f 4c 45 | 4e 47 54 48 0a 58 20 20 |MATCH_LE|NGTH.X  |
|00005c50| 20 20 20 20 20 20 64 6f | 20 7b 7d 20 77 68 69 6c |      do| {} whil|
|00005c60| 65 20 28 28 6c 65 6e 2b | 3d 34 29 20 3c 20 4d 4c |e ((len+|=4) < ML|
|00005c70| 20 26 26 20 2a 28 55 4c | 2a 29 28 73 63 61 6e 2b | && *(UL|*)(scan+|
|00005c80| 6c 65 6e 29 20 3d 3d 20 | 2a 28 55 4c 2a 29 28 6d |len) == |*(UL*)(m|
|00005c90| 61 74 63 68 2b 6c 65 6e | 29 29 3b 0a 58 0a 58 20 |atch+len|));.X.X |
|00005ca0| 20 20 20 20 20 20 20 69 | 66 20 28 2a 28 55 53 2a |       i|f (*(US*|
|00005cb0| 29 28 73 63 61 6e 2b 6c | 65 6e 29 20 3d 3d 20 2a |)(scan+l|en) == *|
|00005cc0| 28 55 53 2a 29 28 6d 61 | 74 63 68 2b 6c 65 6e 29 |(US*)(ma|tch+len)|
|00005cd0| 29 20 6c 65 6e 20 2b 3d | 20 32 3b 0a 58 20 20 20 |) len +=| 2;.X   |
|00005ce0| 20 20 20 20 20 69 66 20 | 28 73 63 61 6e 5b 6c 65 |     if |(scan[le|
|00005cf0| 6e 5d 20 3d 3d 20 6d 61 | 74 63 68 5b 6c 65 6e 5d |n] == ma|tch[len]|
|00005d00| 29 20 6c 65 6e 2b 2b 3b | 0a 58 0a 58 23 65 6c 73 |) len++;|.X.X#els|
|00005d10| 65 20 2f 2a 20 55 4e 41 | 4c 49 47 4e 45 44 5f 4f |e /* UNA|LIGNED_O|
|00005d20| 4b 20 2a 2f 0a 58 20 20 | 20 20 20 20 20 20 69 66 |K */.X  |      if|
|00005d30| 20 28 6d 61 74 63 68 5b | 6d 61 5f 6c 65 6e 67 74 | (match[|ma_lengt|
|00005d40| 68 5d 20 21 3d 20 73 63 | 61 6e 5f 65 6e 64 20 7c |h] != sc|an_end ||
|00005d50| 7c 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 6d ||.X     |       m|
|00005d60| 61 74 63 68 5b 6d 61 5f | 6c 65 6e 67 74 68 2d 31 |atch[ma_|length-1|
|00005d70| 5d 20 21 3d 20 73 63 61 | 6e 5f 65 6e 64 31 20 7c |] != sca|n_end1 ||
|00005d80| 7c 20 2a 6d 61 74 63 68 | 20 21 3d 20 73 63 61 6e || *match| != scan|
|00005d90| 5f 73 74 61 72 74 29 0a | 58 20 20 20 20 20 20 20 |_start).|X       |
|00005da0| 20 20 20 20 63 6f 6e 74 | 69 6e 75 65 3b 0a 58 20 |    cont|inue;.X |
|00005db0| 20 20 20 20 20 20 20 2f | 2a 20 49 74 20 69 73 20 |       /|* It is |
|00005dc0| 6e 6f 74 20 6e 65 63 65 | 73 73 61 72 79 20 74 6f |not nece|ssary to|
|00005dd0| 20 63 6f 6d 70 61 72 65 | 20 73 63 61 6e 5b 31 5d | compare| scan[1]|
|00005de0| 20 61 6e 64 20 6d 61 74 | 63 68 5b 31 5d 20 73 69 | and mat|ch[1] si|
|00005df0| 6e 63 65 20 74 68 65 79 | 0a 58 20 20 20 20 20 20 |nce they|.X      |
|00005e00| 20 20 20 2a 20 61 72 65 | 20 61 6c 77 61 79 73 20 |   * are| always |
|00005e10| 65 71 75 61 6c 20 77 68 | 65 6e 20 74 68 65 20 6f |equal wh|en the o|
|00005e20| 74 68 65 72 20 62 79 74 | 65 73 20 6d 61 74 63 68 |ther byt|es match|
|00005e30| 2c 20 67 69 76 65 6e 20 | 74 68 61 74 0a 58 20 20 |, given |that.X  |
|00005e40| 20 20 20 20 20 20 20 2a | 20 74 68 65 20 68 61 73 |       *| the has|
|00005e50| 68 20 6b 65 79 73 20 61 | 72 65 20 65 71 75 61 6c |h keys a|re equal|
|00005e60| 20 61 6e 64 20 74 68 61 | 74 20 68 5f 73 68 69 66 | and tha|t h_shif|
|00005e70| 74 2b 38 20 3c 3d 20 48 | 41 53 48 5f 42 49 54 53 |t+8 <= H|ASH_BITS|
|00005e80| 2c 0a 58 20 20 20 20 20 | 20 20 20 20 2a 20 74 68 |,.X     |    * th|
|00005e90| 61 74 20 69 73 2c 20 77 | 68 65 6e 20 74 68 65 20 |at is, w|hen the |
|00005ea0| 6c 61 73 74 20 62 79 74 | 65 20 69 73 20 65 6e 74 |last byt|e is ent|
|00005eb0| 69 72 65 6c 79 20 69 6e | 63 6c 75 64 65 64 20 69 |irely in|cluded i|
|00005ec0| 6e 20 74 68 65 20 68 61 | 73 68 20 6b 65 79 2e 0a |n the ha|sh key..|
|00005ed0| 58 20 20 20 20 20 20 20 | 20 20 2a 20 54 68 65 20 |X       |  * The |
|00005ee0| 63 6f 6e 64 69 74 69 6f | 6e 20 69 73 20 65 71 75 |conditio|n is equ|
|00005ef0| 69 76 61 6c 65 6e 74 20 | 74 6f 0a 58 20 20 20 20 |ivalent |to.X    |
|00005f00| 20 20 20 20 20 2a 20 20 | 20 20 20 20 20 28 48 41 |     *  |     (HA|
|00005f10| 53 48 5f 42 49 54 53 2b | 32 29 2f 33 20 2b 20 38 |SH_BITS+|2)/3 + 8|
|00005f20| 20 3c 3d 20 48 41 53 48 | 5f 42 49 54 53 0a 58 20 | <= HASH|_BITS.X |
|00005f30| 20 20 20 20 20 20 20 20 | 2a 20 6f 72 3a 20 48 41 |        |* or: HA|
|00005f40| 53 48 5f 42 49 54 53 20 | 3e 3d 20 31 33 20 28 73 |SH_BITS |>= 13 (s|
|00005f50| 65 65 20 73 65 74 5f 6d | 69 6e 5f 6d 61 74 63 68 |ee set_m|in_match|
|00005f60| 5f 6c 65 6e 67 74 68 28 | 29 29 2e 0a 58 20 20 20 |_length(|))..X   |
|00005f70| 20 20 20 20 20 20 2a 20 | 41 6c 73 6f 2c 20 77 65 |      * |Also, we|
|00005f80| 20 63 68 65 63 6b 20 66 | 6f 72 20 61 20 6d 61 74 | check f|or a mat|
|00005f90| 63 68 20 61 74 20 6d 61 | 5f 6c 65 6e 67 74 68 2d |ch at ma|_length-|
|00005fa0| 31 20 74 6f 20 67 65 74 | 20 72 69 64 20 71 75 69 |1 to get| rid qui|
|00005fb0| 63 6b 6c 79 20 6f 66 0a | 58 20 20 20 20 20 20 20 |ckly of.|X       |
|00005fc0| 20 20 2a 20 74 68 65 20 | 6d 61 74 63 68 20 77 69 |  * the |match wi|
|00005fd0| 74 68 20 74 68 65 20 73 | 75 66 66 69 78 20 6f 66 |th the s|uffix of|
|00005fe0| 20 74 68 65 20 6d 61 74 | 63 68 20 6d 61 64 65 20 | the mat|ch made |
|00005ff0| 61 74 20 74 68 65 20 70 | 72 65 76 69 6f 75 73 20 |at the p|revious |
|00006000| 73 74 65 70 2c 0a 58 20 | 20 20 20 20 20 20 20 20 |step,.X |        |
|00006010| 2a 20 77 68 69 63 68 20 | 69 73 20 6b 6e 6f 77 6e |* which |is known|
|00006020| 20 74 6f 20 66 61 69 6c | 2e 0a 58 20 20 20 20 20 | to fail|..X     |
|00006030| 20 20 20 20 2a 2f 0a 58 | 20 20 20 20 20 20 20 20 |    */.X|        |
|00006040| 6c 65 6e 20 3d 20 31 3b | 0a 58 20 20 20 20 20 20 |len = 1;|.X      |
|00006050| 20 20 64 6f 20 7b 7d 20 | 77 68 69 6c 65 20 28 2b |  do {} |while (+|
|00006060| 2b 6c 65 6e 20 3c 20 4d | 41 58 5f 4d 41 54 43 48 |+len < M|AX_MATCH|
|00006070| 5f 4c 45 4e 47 54 48 20 | 26 26 20 73 63 61 6e 5b |_LENGTH |&& scan[|
|00006080| 6c 65 6e 5d 20 3d 3d 20 | 6d 61 74 63 68 5b 6c 65 |len] == |match[le|
|00006090| 6e 5d 29 3b 0a 58 0a 58 | 23 65 6e 64 69 66 20 2f |n]);.X.X|#endif /|
|000060a0| 2a 20 55 4e 41 4c 49 47 | 4e 45 44 5f 4f 4b 20 2a |* UNALIG|NED_OK *|
|000060b0| 2f 0a 58 0a 58 20 20 20 | 20 20 20 20 20 69 66 20 |/.X.X   |     if |
|000060c0| 28 6c 65 6e 20 3e 20 6d | 61 5f 6c 65 6e 67 74 68 |(len > m|a_length|
|000060d0| 29 20 7b 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |) {.X   |        |
|000060e0| 20 63 75 72 5f 62 65 73 | 74 20 3d 20 63 75 72 5f | cur_bes|t = cur_|
|000060f0| 6d 61 74 63 68 2c 20 6d | 61 5f 6c 65 6e 67 74 68 |match, m|a_length|
|00006100| 20 3d 20 6c 65 6e 3b 0a | 58 20 20 20 20 20 20 20 | = len;.|X       |
|00006110| 20 20 20 20 20 69 66 20 | 28 6c 65 6e 20 3e 3d 20 |     if |(len >= |
|00006120| 73 74 72 73 69 7a 65 29 | 20 62 72 65 61 6b 3b 0a |strsize)| break;.|
|00006130| 58 23 69 66 64 65 66 20 | 55 4e 41 4c 49 47 4e 45 |X#ifdef |UNALIGNE|
|00006140| 44 5f 4f 4b 0a 58 20 20 | 20 20 20 20 20 20 20 20 |D_OK.X  |        |
|00006150| 20 20 73 63 61 6e 5f 65 | 6e 64 20 3d 20 2a 28 55 |  scan_e|nd = *(U|
|00006160| 53 2a 29 28 73 63 61 6e | 2b 6d 61 5f 6c 65 6e 67 |S*)(scan|+ma_leng|
|00006170| 74 68 2d 31 29 3b 0a 58 | 23 65 6c 73 65 0a 58 20 |th-1);.X|#else.X |
|00006180| 20 20 20 20 20 20 20 20 | 20 20 20 73 63 61 6e 5f |        |   scan_|
|00006190| 65 6e 64 31 20 20 3d 20 | 73 63 61 6e 5b 6d 61 5f |end1  = |scan[ma_|
|000061a0| 6c 65 6e 67 74 68 2d 31 | 5d 3b 0a 58 20 20 20 20 |length-1|];.X    |
|000061b0| 20 20 20 20 20 20 20 20 | 73 63 61 6e 5f 65 6e 64 |        |scan_end|
|000061c0| 20 20 20 3d 20 73 63 61 | 6e 5b 6d 61 5f 6c 65 6e |   = sca|n[ma_len|
|000061d0| 67 74 68 5d 3b 0a 58 23 | 65 6e 64 69 66 0a 58 20 |gth];.X#|endif.X |
|000061e0| 20 20 20 20 20 20 20 7d | 0a 58 20 20 20 20 7d 20 |       }|.X    } |
|000061f0| 77 68 69 6c 65 20 28 2d | 2d 63 68 61 69 6e 5f 63 |while (-|-chain_c|
|00006200| 6f 75 6e 74 20 21 3d 20 | 30 20 26 26 20 28 63 75 |ount != |0 && (cu|
|00006210| 72 5f 6d 61 74 63 68 20 | 3d 20 70 72 65 76 5b 63 |r_match |= prev[c|
|00006220| 75 72 5f 6d 61 74 63 68 | 5d 29 20 21 3d 20 4e 49 |ur_match|]) != NI|
|00006230| 4c 29 3b 0a 58 0a 58 20 | 20 20 20 69 66 20 28 6d |L);.X.X |   if (m|
|00006240| 61 5f 6c 65 6e 67 74 68 | 20 3e 20 73 74 61 72 74 |a_length| > start|
|00006250| 5f 6c 65 6e 67 74 68 29 | 20 6d 61 74 63 68 5f 6c |_length)| match_l|
|00006260| 65 6e 67 74 68 20 3d 20 | 6d 61 5f 6c 65 6e 67 74 |ength = |ma_lengt|
|00006270| 68 3b 0a 58 20 20 20 20 | 72 65 74 75 72 6e 20 63 |h;.X    |return c|
|00006280| 75 72 5f 62 65 73 74 3b | 0a 58 7d 0a 58 23 65 6e |ur_best;|.X}.X#en|
|00006290| 64 69 66 20 2f 2a 20 4d | 53 44 4f 53 20 2a 2f 0a |dif /* M|SDOS */.|
|000062a0| 58 0a 58 2f 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |X.X/****|********|
|000062b0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000062c0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000062d0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000062e0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 0a 58 20 2a 0a |********|***.X *.|
|000062f0| 58 20 2a 20 50 72 6f 63 | 65 73 73 20 61 20 62 6c |X * Proc|ess a bl|
|00006300| 6f 63 6b 20 6f 66 20 69 | 6e 70 75 74 20 63 68 61 |ock of i|nput cha|
|00006310| 72 61 63 74 65 72 73 2c | 20 67 65 6e 65 72 61 74 |racters,| generat|
|00006320| 69 6e 67 20 7a 65 72 6f | 20 6f 72 20 6d 6f 72 65 |ing zero| or more|
|00006330| 20 6d 61 74 63 68 0a 58 | 20 2a 20 69 6e 66 6f 20 | match.X| * info |
|00006340| 72 65 63 6f 72 64 73 20 | 61 73 20 61 70 70 72 6f |records |as appro|
|00006350| 70 72 69 61 74 65 2e 0a | 58 20 2a 20 49 4e 20 61 |priate..|X * IN a|
|00006360| 73 73 65 72 74 69 6f 6e | 3a 20 63 6f 75 6e 74 20 |ssertion|: count |
|00006370| 3c 3d 20 42 53 5a 0a 58 | 20 2a 2f 0a 49 6d 70 45 |<= BSZ.X| */.ImpE|
|00006380| 72 72 20 6c 6d 5f 69 6e | 70 75 74 20 28 62 6c 6f |rr lm_in|put (blo|
|00006390| 63 6b 2c 20 63 6f 75 6e | 74 29 0a 58 20 20 20 20 |ck, coun|t).X    |
|000063a0| 55 5f 43 48 41 52 20 2a | 62 6c 6f 63 6b 3b 20 20 |U_CHAR *|block;  |
|000063b0| 20 20 20 20 20 20 20 20 | 2f 2a 20 69 6e 70 75 74 |        |/* input|
|000063c0| 20 64 61 74 61 20 2a 2f | 0a 58 20 20 20 20 55 5f | data */|.X    U_|
|000063d0| 49 4e 54 20 20 63 6f 75 | 6e 74 3b 20 20 20 20 20 |INT  cou|nt;     |
|000063e0| 20 20 20 20 20 20 2f 2a | 20 23 20 6f 66 20 69 6e |      /*| # of in|
|000063f0| 70 75 74 20 63 68 61 72 | 27 73 20 2a 2f 0a 58 7b |put char|'s */.X{|
+--------+-------------------------+-------------------------+--------+--------+