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

< 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 38 | 3a 20 7a 69 70 20 2d 20 | v25i148|: 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 37 2f 30 37 | 0a 53 65 6e 64 65 72 3a |art07/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 38 0a 41 72 | 63 68 69 76 65 2d 4e 61 |e 148.Ar|chive-Na|
|00000130| 6d 65 3a 20 7a 69 70 2f | 70 61 72 74 30 37 0a 0a |me: zip/|part07..|
|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 37 20 28 | 6f 66 20 37 29 2e 22 0a |hive 7 (|of 7).".|
|000002c0| 23 20 43 6f 6e 74 65 6e | 74 73 3a 20 20 69 6d 5f |# Conten|ts:  im_|
|000002d0| 63 74 72 65 65 2e 63 0a | 23 20 57 72 61 70 70 65 |ctree.c.|# Wrappe|
|000002e0| 64 20 62 79 20 76 69 78 | 69 65 40 63 6f 67 6e 69 |d by vix|ie@cogni|
|000002f0| 74 69 6f 6e 2e 70 61 2e | 64 65 63 2e 63 6f 6d 20 |tion.pa.|dec.com |
|00000300| 6f 6e 20 53 75 6e 20 4d | 61 72 20 20 31 20 31 38 |on Sun M|ar  1 18|
|00000310| 3a 35 37 3a 33 39 20 31 | 39 39 32 0a 50 41 54 48 |:57:39 1|992.PATH|
|00000320| 3d 2f 62 69 6e 3a 2f 75 | 73 72 2f 62 69 6e 3a 2f |=/bin:/u|sr/bin:/|
|00000330| 75 73 72 2f 75 63 62 20 | 3b 20 65 78 70 6f 72 74 |usr/ucb |; export|
|00000340| 20 50 41 54 48 0a 69 66 | 20 74 65 73 74 20 2d 66 | PATH.if| test -f|
|00000350| 20 27 69 6d 5f 63 74 72 | 65 65 2e 63 27 20 2d 61 | 'im_ctr|ee.c' -a|
|00000360| 20 22 24 7b 31 7d 22 20 | 21 3d 20 22 2d 63 22 20 | "${1}" |!= "-c" |
|00000370| 3b 20 74 68 65 6e 20 0a | 20 20 65 63 68 6f 20 73 |; then .|  echo s|
|00000380| 68 61 72 3a 20 57 69 6c | 6c 20 6e 6f 74 20 63 6c |har: Wil|l not cl|
|00000390| 6f 62 62 65 72 20 65 78 | 69 73 74 69 6e 67 20 66 |obber ex|isting f|
|000003a0| 69 6c 65 20 5c 22 27 69 | 6d 5f 63 74 72 65 65 2e |ile \"'i|m_ctree.|
|000003b0| 63 27 5c 22 0a 65 6c 73 | 65 0a 65 63 68 6f 20 73 |c'\".els|e.echo s|
|000003c0| 68 61 72 3a 20 45 78 74 | 72 61 63 74 69 6e 67 20 |har: Ext|racting |
|000003d0| 5c 22 27 69 6d 5f 63 74 | 72 65 65 2e 63 27 5c 22 |\"'im_ct|ree.c'\"|
|000003e0| 20 5c 28 34 35 35 32 33 | 20 63 68 61 72 61 63 74 | \(45523| charact|
|000003f0| 65 72 73 5c 29 0a 73 65 | 64 20 22 73 2f 5e 58 2f |ers\).se|d "s/^X/|
|00000400| 2f 22 20 3e 27 69 6d 5f | 63 74 72 65 65 2e 63 27 |/" >'im_|ctree.c'|
|00000410| 20 3c 3c 27 45 4e 44 5f | 4f 46 5f 46 49 4c 45 27 | <<'END_|OF_FILE'|
|00000420| 0a 58 2f 2a 0a 58 0a 58 | 20 43 6f 70 79 72 69 67 |.X/*.X.X| Copyrig|
|00000430| 68 74 20 28 43 29 20 31 | 39 39 30 2c 31 39 39 31 |ht (C) 1|990,1991|
|00000440| 20 4d 61 72 6b 20 41 64 | 6c 65 72 2c 20 52 69 63 | Mark Ad|ler, Ric|
|00000450| 68 61 72 64 20 42 2e 20 | 57 61 6c 65 73 2c 20 61 |hard B. |Wales, a|
|00000460| 6e 64 20 4a 65 61 6e 2d | 6c 6f 75 70 20 47 61 69 |nd Jean-|loup Gai|
|00000470| 6c 6c 79 2e 0a 58 20 50 | 65 72 6d 69 73 73 69 6f |lly..X P|ermissio|
|00000480| 6e 20 69 73 20 67 72 61 | 6e 74 65 64 20 74 6f 20 |n is gra|nted to |
|00000490| 61 6e 79 20 69 6e 64 69 | 76 69 64 75 61 6c 20 6f |any indi|vidual o|
|000004a0| 72 20 69 6e 73 74 69 74 | 75 74 69 6f 6e 20 74 6f |r instit|ution to|
|000004b0| 20 75 73 65 2c 20 63 6f | 70 79 2c 20 6f 72 0a 58 | use, co|py, or.X|
|000004c0| 20 72 65 64 69 73 74 72 | 69 62 75 74 65 20 74 68 | redistr|ibute th|
|000004d0| 69 73 20 73 6f 66 74 77 | 61 72 65 20 73 6f 20 6c |is softw|are so l|
|000004e0| 6f 6e 67 20 61 73 20 61 | 6c 6c 20 6f 66 20 74 68 |ong as a|ll of th|
|000004f0| 65 20 6f 72 69 67 69 6e | 61 6c 20 66 69 6c 65 73 |e origin|al files|
|00000500| 20 61 72 65 20 69 6e 63 | 6c 75 64 65 64 0a 58 20 | are inc|luded.X |
|00000510| 75 6e 6d 6f 64 69 66 69 | 65 64 2c 20 74 68 61 74 |unmodifi|ed, that|
|00000520| 20 69 74 20 69 73 20 6e | 6f 74 20 73 6f 6c 64 20 | it is n|ot sold |
|00000530| 66 6f 72 20 70 72 6f 66 | 69 74 2c 20 61 6e 64 20 |for prof|it, and |
|00000540| 74 68 61 74 20 74 68 69 | 73 20 63 6f 70 79 72 69 |that thi|s copyri|
|00000550| 67 68 74 20 6e 6f 74 69 | 63 65 0a 58 20 69 73 20 |ght noti|ce.X is |
|00000560| 72 65 74 61 69 6e 65 64 | 2e 0a 58 0a 58 2a 2f 0a |retained|..X.X*/.|
|00000570| 58 0a 58 2f 2a 0a 58 20 | 2a 20 20 69 6d 5f 63 74 |X.X/*.X |*  im_ct|
|00000580| 72 65 65 2e 63 20 62 79 | 20 52 69 63 68 61 72 64 |ree.c by| Richard|
|00000590| 20 42 2e 20 57 61 6c 65 | 73 2e 0a 58 20 2a 0a 58 | B. Wale|s..X *.X|
|000005a0| 20 2a 20 20 49 6e 63 6c | 75 64 65 73 20 6d 6f 64 | *  Incl|udes mod|
|000005b0| 69 66 69 63 61 74 69 6f | 6e 73 20 62 79 20 4a 65 |ificatio|ns by Je|
|000005c0| 61 6e 2d 4c 6f 75 70 20 | 47 61 69 6c 6c 79 2e 0a |an-Loup |Gailly..|
|000005d0| 58 20 2a 0a 58 20 2a 20 | 20 50 55 52 50 4f 53 45 |X *.X * | PURPOSE|
|000005e0| 0a 58 20 2a 0a 58 20 2a | 20 20 20 20 20 20 45 6e |.X *.X *|      En|
|000005f0| 63 6f 64 65 20 76 61 72 | 69 6f 75 73 20 73 65 74 |code var|ious set|
|00000600| 73 20 6f 66 20 73 6f 75 | 72 63 65 20 76 61 6c 75 |s of sou|rce valu|
|00000610| 65 73 20 75 73 69 6e 67 | 20 76 61 72 69 61 62 6c |es using| variabl|
|00000620| 65 2d 6c 65 6e 67 74 68 | 0a 58 20 2a 20 20 20 20 |e-length|.X *    |
|00000630| 20 20 62 69 6e 61 72 79 | 20 63 6f 64 65 20 74 72 |  binary| code tr|
|00000640| 65 65 73 2e 0a 58 20 2a | 0a 58 20 2a 20 20 44 49 |ees..X *|.X *  DI|
|00000650| 53 43 55 53 53 49 4f 4e | 0a 58 20 2a 0a 58 20 2a |SCUSSION|.X *.X *|
|00000660| 20 20 20 20 20 20 54 68 | 65 20 50 4b 5a 49 50 20 |      Th|e PKZIP |
|00000670| 22 69 6d 70 6c 6f 73 69 | 6f 6e 22 20 70 72 6f 63 |"implosi|on" proc|
|00000680| 65 73 73 20 75 73 65 73 | 20 73 65 76 65 72 61 6c |ess uses| several|
|00000690| 20 76 61 72 69 61 62 6c | 65 2d 64 65 70 74 68 20 | variabl|e-depth |
|000006a0| 62 69 6e 61 72 79 0a 58 | 20 2a 20 20 20 20 20 20 |binary.X| *      |
|000006b0| 63 6f 64 65 20 74 72 65 | 65 73 2c 20 73 69 6d 69 |code tre|es, simi|
|000006c0| 6c 61 72 20 74 6f 20 48 | 75 66 66 6d 61 6e 20 74 |lar to H|uffman t|
|000006d0| 72 65 65 73 2e 20 20 54 | 68 65 20 6d 6f 72 65 20 |rees.  T|he more |
|000006e0| 63 6f 6d 6d 6f 6e 20 73 | 6f 75 72 63 65 0a 58 20 |common s|ource.X |
|000006f0| 2a 20 20 20 20 20 20 76 | 61 6c 75 65 73 20 61 72 |*      v|alues ar|
|00000700| 65 20 72 65 70 72 65 73 | 65 6e 74 65 64 20 62 79 |e repres|ented by|
|00000710| 20 73 68 6f 72 74 65 72 | 20 62 69 74 20 73 65 71 | shorter| bit seq|
|00000720| 75 65 6e 63 65 73 2e 0a | 58 20 2a 0a 58 20 2a 20 |uences..|X *.X * |
|00000730| 20 20 20 20 20 45 61 63 | 68 20 63 6f 64 65 20 74 |     Eac|h code t|
|00000740| 72 65 65 20 69 73 20 73 | 74 6f 72 65 64 20 69 6e |ree is s|tored in|
|00000750| 20 74 68 65 20 5a 49 50 | 20 66 69 6c 65 20 69 6e | the ZIP| file in|
|00000760| 20 61 20 63 6f 6d 70 72 | 65 73 73 65 64 20 66 6f | a compr|essed fo|
|00000770| 72 6d 0a 58 20 2a 20 20 | 20 20 20 20 74 68 61 74 |rm.X *  |    that|
|00000780| 20 69 73 20 65 73 73 65 | 6e 74 69 61 6c 6c 79 20 | is esse|ntially |
|00000790| 61 20 72 75 6e 2d 6c 65 | 6e 67 74 68 2d 65 6e 63 |a run-le|ngth-enc|
|000007a0| 6f 64 65 64 20 6c 69 73 | 74 20 6f 66 20 74 68 65 |oded lis|t of the|
|000007b0| 20 6c 65 6e 67 74 68 73 | 20 6f 66 0a 58 20 2a 20 | lengths| of.X * |
|000007c0| 20 20 20 20 20 61 6c 6c | 20 74 68 65 20 63 6f 64 |     all| the cod|
|000007d0| 65 20 73 74 72 69 6e 67 | 73 20 28 69 6e 20 61 73 |e string|s (in as|
|000007e0| 63 65 6e 64 69 6e 67 20 | 6f 72 64 65 72 20 62 79 |cending |order by|
|000007f0| 20 73 6f 75 72 63 65 20 | 76 61 6c 75 65 73 29 2e | source |values).|
|00000800| 0a 58 20 2a 20 20 20 20 | 20 20 54 68 65 20 61 63 |.X *    |  The ac|
|00000810| 74 75 61 6c 20 63 6f 64 | 65 20 73 74 72 69 6e 67 |tual cod|e string|
|00000820| 73 20 61 72 65 20 72 65 | 63 6f 6e 73 74 72 75 63 |s are re|construc|
|00000830| 74 65 64 20 66 72 6f 6d | 20 74 68 65 20 6c 65 6e |ted from| the len|
|00000840| 67 74 68 73 20 69 6e 0a | 58 20 2a 20 20 20 20 20 |gths in.|X *     |
|00000850| 20 74 68 65 20 55 4e 5a | 49 50 20 70 72 6f 63 65 | the UNZ|IP proce|
|00000860| 73 73 2c 20 61 73 20 64 | 65 73 63 72 69 62 65 64 |ss, as d|escribed|
|00000870| 20 69 6e 20 74 68 65 20 | 22 61 70 70 6c 69 63 61 | in the |"applica|
|00000880| 74 69 6f 6e 20 6e 6f 74 | 65 22 0a 58 20 2a 20 20 |tion not|e".X *  |
|00000890| 20 20 20 20 28 41 50 50 | 4e 4f 54 45 2e 54 58 54 |    (APP|NOTE.TXT|
|000008a0| 29 20 64 69 73 74 72 69 | 62 75 74 65 64 20 61 73 |) distri|buted as|
|000008b0| 20 70 61 72 74 20 6f 66 | 20 50 4b 57 41 52 45 27 | part of| PKWARE'|
|000008c0| 73 20 50 4b 5a 49 50 20 | 70 72 6f 67 72 61 6d 2e |s PKZIP |program.|
|000008d0| 0a 58 20 2a 0a 58 20 2a | 20 20 20 20 20 20 42 65 |.X *.X *|      Be|
|000008e0| 63 61 75 73 65 20 6f 66 | 20 74 68 65 20 77 61 79 |cause of| the way|
|000008f0| 20 61 20 63 6f 64 65 20 | 74 72 65 65 20 69 73 20 | a code |tree is |
|00000900| 73 74 6f 72 65 64 20 69 | 6e 20 74 68 65 20 5a 49 |stored i|n the ZI|
|00000910| 50 20 66 69 6c 65 2c 20 | 74 68 65 0a 58 20 2a 20 |P file, |the.X * |
|00000920| 20 20 20 20 20 63 6f 64 | 65 73 20 6d 75 73 74 20 |     cod|es must |
|00000930| 63 6f 6e 66 6f 72 6d 20 | 74 6f 20 74 68 65 20 66 |conform |to the f|
|00000940| 6f 6c 6c 6f 77 69 6e 67 | 20 72 65 73 74 72 69 63 |ollowing| restric|
|00000950| 74 69 6f 6e 73 3a 0a 58 | 20 2a 0a 58 20 2a 20 20 |tions:.X| *.X *  |
|00000960| 20 20 20 20 28 31 29 20 | 4e 6f 20 63 6f 64 65 20 |    (1) |No code |
|00000970| 73 74 72 69 6e 67 20 6d | 61 79 20 65 76 65 72 20 |string m|ay ever |
|00000980| 65 78 63 65 65 64 20 31 | 36 20 62 69 74 73 20 69 |exceed 1|6 bits i|
|00000990| 6e 20 6c 65 6e 67 74 68 | 2e 0a 58 20 2a 0a 58 20 |n length|..X *.X |
|000009a0| 2a 20 20 20 20 20 20 28 | 32 29 20 49 66 20 61 6c |*      (|2) If al|
|000009b0| 6c 20 63 6f 64 65 20 73 | 74 72 69 6e 67 73 20 61 |l code s|trings a|
|000009c0| 72 65 20 65 78 74 65 6e | 64 65 64 20 74 6f 20 31 |re exten|ded to 1|
|000009d0| 36 20 62 69 74 73 20 62 | 79 20 70 61 64 64 69 6e |6 bits b|y paddin|
|000009e0| 67 20 6f 6e 0a 58 20 2a | 20 20 20 20 20 20 20 20 |g on.X *|        |
|000009f0| 20 20 74 68 65 20 72 69 | 67 68 74 20 28 6c 6f 77 |  the ri|ght (low|
|00000a00| 2d 6f 72 64 65 72 20 65 | 6e 64 29 20 77 69 74 68 |-order e|nd) with|
|00000a10| 20 7a 65 72 6f 73 2c 20 | 61 6e 64 20 74 68 65 6e | zeros, |and then|
|00000a20| 20 74 72 65 61 74 65 64 | 20 61 73 0a 58 20 2a 20 | treated| as.X * |
|00000a30| 20 20 20 20 20 20 20 20 | 20 75 6e 73 69 67 6e 65 |        | unsigne|
|00000a40| 64 20 31 36 2d 62 69 74 | 20 69 6e 74 65 67 65 72 |d 16-bit| integer|
|00000a50| 73 2c 20 74 68 65 6e 3a | 0a 58 20 2a 0a 58 20 2a |s, then:|.X *.X *|
|00000a60| 20 20 20 20 20 20 20 20 | 20 20 28 61 29 20 54 68 |        |  (a) Th|
|00000a70| 65 20 61 72 69 74 68 6d | 65 74 69 63 61 6c 6c 79 |e arithm|etically|
|00000a80| 20 68 69 67 68 65 72 20 | 31 36 2d 62 69 74 20 76 | higher |16-bit v|
|00000a90| 61 6c 75 65 73 20 6d 75 | 73 74 20 63 6f 72 72 65 |alues mu|st corre|
|00000aa0| 73 70 6f 6e 64 0a 58 20 | 2a 20 20 20 20 20 20 20 |spond.X |*       |
|00000ab0| 20 20 20 20 20 20 20 74 | 6f 20 74 68 65 20 73 68 |       t|o the sh|
|00000ac0| 6f 72 74 65 72 20 63 6f | 64 65 20 73 74 72 69 6e |orter co|de strin|
|00000ad0| 67 73 2e 0a 58 20 2a 0a | 58 20 2a 20 20 20 20 20 |gs..X *.|X *     |
|00000ae0| 20 20 20 20 20 28 62 29 | 20 49 66 20 74 77 6f 20 |     (b)| If two |
|00000af0| 73 6f 75 72 63 65 20 76 | 61 6c 75 65 73 20 6d 61 |source v|alues ma|
|00000b00| 70 20 69 6e 74 6f 20 63 | 6f 64 65 20 73 74 72 69 |p into c|ode stri|
|00000b10| 6e 67 73 20 6f 66 20 74 | 68 65 20 73 61 6d 65 0a |ngs of t|he same.|
|00000b20| 58 20 2a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |X *     |        |
|00000b30| 20 6c 65 6e 67 74 68 2c | 20 74 68 65 20 68 69 67 | length,| the hig|
|00000b40| 68 65 72 20 63 6f 64 65 | 20 73 74 72 69 6e 67 20 |her code| string |
|00000b50| 6d 75 73 74 20 63 6f 72 | 72 65 73 70 6f 6e 64 20 |must cor|respond |
|00000b60| 74 6f 20 74 68 65 0a 58 | 20 2a 20 20 20 20 20 20 |to the.X| *      |
|00000b70| 20 20 20 20 20 20 20 20 | 6c 6f 77 65 72 20 73 6f |        |lower so|
|00000b80| 75 72 63 65 20 76 61 6c | 75 65 20 28 77 68 65 72 |urce val|ue (wher|
|00000b90| 65 20 73 6f 75 72 63 65 | 20 76 61 6c 75 65 73 20 |e source| values |
|00000ba0| 61 72 65 20 74 72 65 61 | 74 65 64 20 61 73 0a 58 |are trea|ted as.X|
|00000bb0| 20 2a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | *      |        |
|00000bc0| 75 6e 73 69 67 6e 65 64 | 29 2e 0a 58 20 2a 0a 58 |unsigned|)..X *.X|
|00000bd0| 20 2a 20 20 20 20 20 20 | 46 75 72 74 68 65 72 2c | *      |Further,|
|00000be0| 20 73 68 6f 72 74 63 75 | 74 73 20 74 61 6b 65 6e | shortcu|ts taken|
|00000bf0| 20 62 79 20 50 4b 55 4e | 5a 49 50 20 31 2e 31 30 | by PKUN|ZIP 1.10|
|00000c00| 20 69 6e 20 74 68 65 20 | 77 61 79 20 69 74 20 64 | in the |way it d|
|00000c10| 65 63 6f 64 65 73 0a 58 | 20 2a 20 20 20 20 20 20 |ecodes.X| *      |
|00000c20| 74 68 65 20 63 6f 6d 70 | 72 65 73 73 65 64 20 64 |the comp|ressed d|
|00000c30| 61 74 61 20 76 69 61 20 | 74 68 65 20 74 72 65 65 |ata via |the tree|
|00000c40| 73 20 69 6d 70 6f 73 65 | 20 74 68 65 20 66 6f 6c |s impose| the fol|
|00000c50| 6c 6f 77 69 6e 67 20 65 | 78 74 72 61 0a 58 20 2a |lowing e|xtra.X *|
|00000c60| 20 20 20 20 20 20 6c 69 | 6d 69 74 61 74 69 6f 6e |      li|mitation|
|00000c70| 73 3a 0a 58 20 2a 0a 58 | 20 2a 20 20 20 20 20 20 |s:.X *.X| *      |
|00000c80| 28 33 29 20 4e 6f 20 63 | 6f 64 65 20 73 74 72 69 |(3) No c|ode stri|
|00000c90| 6e 67 20 69 6e 20 74 68 | 65 20 22 64 69 73 74 61 |ng in th|e "dista|
|00000ca0| 6e 63 65 22 20 74 72 65 | 65 20 63 61 6e 20 62 65 |nce" tre|e can be|
|00000cb0| 20 6c 6f 6e 67 65 72 20 | 74 68 61 6e 20 38 0a 58 | longer |than 8.X|
|00000cc0| 20 2a 20 20 20 20 20 20 | 20 20 20 20 62 69 74 73 | *      |    bits|
|00000cd0| 2e 0a 58 20 2a 0a 58 20 | 2a 20 20 20 20 20 20 28 |..X *.X |*      (|
|00000ce0| 34 29 20 54 68 65 20 6d | 61 78 69 6d 75 6d 20 6c |4) The m|aximum l|
|00000cf0| 65 6e 67 74 68 20 6f 66 | 20 61 6e 79 20 63 6f 64 |ength of| any cod|
|00000d00| 65 20 73 74 72 69 6e 67 | 20 69 73 20 6c 69 6d 69 |e string| is limi|
|00000d10| 74 65 64 20 62 79 20 74 | 68 65 0a 58 20 2a 20 20 |ted by t|he.X *  |
|00000d20| 20 20 20 20 20 20 20 20 | 6e 75 6d 62 65 72 20 6f |        |number o|
|00000d30| 66 20 69 6e 69 74 69 61 | 6c 20 7a 65 72 6f 20 62 |f initia|l zero b|
|00000d40| 69 74 73 2c 20 61 73 20 | 66 6f 6c 6c 6f 77 73 3a |its, as |follows:|
|00000d50| 0a 58 20 2a 0a 58 20 2a | 20 20 20 20 20 20 20 20 |.X *.X *|        |
|00000d60| 20 20 28 61 29 20 30 2d | 33 20 6c 65 61 64 69 6e |  (a) 0-|3 leadin|
|00000d70| 67 20 7a 65 72 6f 73 3a | 20 20 6d 61 78 69 6d 75 |g zeros:|  maximu|
|00000d80| 6d 20 6c 65 6e 67 74 68 | 20 69 73 20 38 2e 0a 58 |m length| is 8..X|
|00000d90| 20 2a 0a 58 20 2a 20 20 | 20 20 20 20 20 20 20 20 | *.X *  |        |
|00000da0| 28 62 29 20 34 2d 35 20 | 6c 65 61 64 69 6e 67 20 |(b) 4-5 |leading |
|00000db0| 7a 65 72 6f 73 3a 20 20 | 6d 61 78 69 6d 75 6d 20 |zeros:  |maximum |
|00000dc0| 6c 65 6e 67 74 68 20 69 | 73 20 31 32 2e 0a 58 20 |length i|s 12..X |
|00000dd0| 2a 0a 58 20 2a 20 20 20 | 20 20 20 20 20 20 20 28 |*.X *   |       (|
|00000de0| 63 29 20 36 2d 37 20 6c | 65 61 64 69 6e 67 20 7a |c) 6-7 l|eading z|
|00000df0| 65 72 6f 73 3a 20 20 6d | 61 78 69 6d 75 6d 20 6c |eros:  m|aximum l|
|00000e00| 65 6e 67 74 68 20 69 73 | 20 31 34 2e 0a 58 20 2a |ength is| 14..X *|
|00000e10| 0a 58 20 2a 20 20 20 20 | 20 20 28 35 29 20 49 6e |.X *    |  (5) In|
|00000e20| 20 74 68 65 20 22 6c 69 | 74 65 72 61 6c 22 20 74 | the "li|teral" t|
|00000e30| 72 65 65 2c 20 74 68 65 | 20 63 6f 64 65 20 73 74 |ree, the| code st|
|00000e40| 72 69 6e 67 20 63 6f 72 | 72 65 73 70 6f 6e 64 69 |ring cor|respondi|
|00000e50| 6e 67 20 74 6f 20 74 68 | 65 0a 58 20 2a 20 20 20 |ng to th|e.X *   |
|00000e60| 20 20 20 20 20 20 20 73 | 6f 75 72 63 65 20 76 61 |       s|ource va|
|00000e70| 6c 75 65 20 32 35 35 20 | 6d 75 73 74 20 62 65 20 |lue 255 |must be |
|00000e80| 61 74 20 6c 65 61 73 74 | 20 31 30 20 62 69 74 73 |at least| 10 bits|
|00000e90| 20 69 6e 20 6c 65 6e 67 | 74 68 2c 20 72 65 67 61 | in leng|th, rega|
|00000ea0| 72 64 2d 0a 58 20 2a 20 | 20 20 20 20 20 20 20 20 |rd-.X * |        |
|00000eb0| 20 6c 65 73 73 20 6f 66 | 20 74 68 65 20 66 72 65 | less of| the fre|
|00000ec0| 71 75 65 6e 63 79 20 6f | 66 20 74 68 65 20 76 61 |quency o|f the va|
|00000ed0| 6c 75 65 20 32 35 35 20 | 69 6e 20 74 68 65 20 66 |lue 255 |in the f|
|00000ee0| 69 6c 65 2e 0a 58 20 2a | 0a 58 20 2a 20 20 20 20 |ile..X *|.X *    |
|00000ef0| 20 20 50 4b 57 41 52 45 | 20 63 61 6c 6c 73 20 74 |  PKWARE| calls t|
|00000f00| 68 65 20 63 6f 64 65 20 | 74 72 65 65 73 20 22 53 |he code |trees "S|
|00000f10| 68 61 6e 6e 6f 6e 2d 46 | 61 6e 6f 20 74 72 65 65 |hannon-F|ano tree|
|00000f20| 73 22 2e 20 20 28 53 68 | 61 6e 6e 6f 6e 2d 46 61 |s".  (Sh|annon-Fa|
|00000f30| 6e 6f 0a 58 20 2a 20 20 | 20 20 20 20 63 6f 64 69 |no.X *  |    codi|
|00000f40| 6e 67 20 77 61 73 20 61 | 20 70 72 65 64 65 63 65 |ng was a| predece|
|00000f50| 73 73 6f 72 20 74 6f 20 | 74 68 65 20 62 65 74 74 |ssor to |the bett|
|00000f60| 65 72 2d 6b 6e 6f 77 6e | 20 48 75 66 66 6d 61 6e |er-known| Huffman|
|00000f70| 20 63 6f 64 69 6e 67 0a | 58 20 2a 20 20 20 20 20 | coding.|X *     |
|00000f80| 20 74 65 63 68 6e 69 71 | 75 65 3b 20 73 65 65 20 | techniq|ue; see |
|00000f90| 74 68 65 20 72 65 66 65 | 72 65 6e 63 65 73 20 62 |the refe|rences b|
|00000fa0| 65 6c 6f 77 2e 29 20 20 | 41 6c 74 68 6f 75 67 68 |elow.)  |Although|
|00000fb0| 20 69 74 20 61 70 70 65 | 61 72 73 20 74 68 61 74 | it appe|ars that|
|00000fc0| 0a 58 20 2a 20 20 20 20 | 20 20 74 68 65 20 53 68 |.X *    |  the Sh|
|00000fd0| 61 6e 6e 6f 6e 2d 46 61 | 6e 6f 20 28 74 6f 70 2d |annon-Fa|no (top-|
|00000fe0| 64 6f 77 6e 20 70 61 72 | 74 69 74 69 6f 6e 69 6e |down par|titionin|
|00000ff0| 67 29 20 61 6c 67 6f 72 | 69 74 68 6d 20 69 73 20 |g) algor|ithm is |
|00001000| 69 6e 20 66 61 63 74 0a | 58 20 2a 20 20 20 20 20 |in fact.|X *     |
|00001010| 20 75 73 65 64 20 62 79 | 20 50 4b 5a 49 50 20 69 | used by| PKZIP i|
|00001020| 6e 20 74 68 65 20 70 72 | 6f 63 65 73 73 20 6f 66 |n the pr|ocess of|
|00001030| 20 63 72 65 61 74 69 6e | 67 20 74 68 65 20 63 6f | creatin|g the co|
|00001040| 64 65 20 74 72 65 65 73 | 2c 20 74 68 65 0a 58 20 |de trees|, the.X |
|00001050| 2a 20 20 20 20 20 20 72 | 65 73 75 6c 74 69 6e 67 |*      r|esulting|
|00001060| 20 74 72 65 65 73 20 61 | 72 65 20 6e 6f 74 20 69 | trees a|re not i|
|00001070| 6e 20 66 61 63 74 20 22 | 70 75 72 65 22 20 53 68 |n fact "|pure" Sh|
|00001080| 61 6e 6e 6f 6e 2d 46 61 | 6e 6f 2c 20 62 65 63 61 |annon-Fa|no, beca|
|00001090| 75 73 65 20 6f 66 0a 58 | 20 2a 20 20 20 20 20 20 |use of.X| *      |
|000010a0| 74 68 65 20 65 78 74 72 | 61 20 70 72 6f 63 65 73 |the extr|a proces|
|000010b0| 73 69 6e 67 20 72 65 71 | 75 69 72 65 64 20 69 6e |sing req|uired in|
|000010c0| 20 6f 72 64 65 72 20 74 | 6f 20 6d 65 65 74 20 74 | order t|o meet t|
|000010d0| 68 65 20 72 65 73 74 72 | 69 63 74 69 6f 6e 73 0a |he restr|ictions.|
|000010e0| 58 20 2a 20 20 20 20 20 | 20 64 65 73 63 72 69 62 |X *     | describ|
|000010f0| 65 64 20 61 62 6f 76 65 | 2e 0a 58 20 2a 0a 58 20 |ed above|..X *.X |
|00001100| 2a 20 20 52 45 46 45 52 | 45 4e 43 45 53 0a 58 20 |*  REFER|ENCES.X |
|00001110| 2a 0a 58 20 2a 20 20 20 | 20 20 20 4c 79 6e 63 68 |*.X *   |   Lynch|
|00001120| 2c 20 54 68 6f 6d 61 73 | 20 4a 2e 0a 58 20 2a 20 |, Thomas| J..X * |
|00001130| 20 20 20 20 20 20 20 20 | 20 44 61 74 61 20 43 6f |        | Data Co|
|00001140| 6d 70 72 65 73 73 69 6f | 6e 3a 20 20 54 65 63 68 |mpressio|n:  Tech|
|00001150| 6e 69 71 75 65 73 20 61 | 6e 64 20 41 70 70 6c 69 |niques a|nd Appli|
|00001160| 63 61 74 69 6f 6e 73 2c | 20 70 70 2e 20 35 33 2d |cations,| pp. 53-|
|00001170| 35 35 2e 0a 58 20 2a 20 | 20 20 20 20 20 20 20 20 |55..X * |        |
|00001180| 20 4c 69 66 65 74 69 6d | 65 20 4c 65 61 72 6e 69 | Lifetim|e Learni|
|00001190| 6e 67 20 50 75 62 6c 69 | 63 61 74 69 6f 6e 73 2c |ng Publi|cations,|
|000011a0| 20 31 39 38 35 2e 20 20 | 49 53 42 4e 20 30 2d 35 | 1985.  |ISBN 0-5|
|000011b0| 33 34 2d 30 33 34 31 38 | 2d 37 2e 0a 58 20 2a 0a |34-03418|-7..X *.|
|000011c0| 58 20 2a 20 20 20 20 20 | 20 53 74 6f 72 65 72 2c |X *     | Storer,|
|000011d0| 20 4a 61 6d 65 73 20 41 | 2e 0a 58 20 2a 20 20 20 | James A|..X *   |
|000011e0| 20 20 20 20 20 20 20 44 | 61 74 61 20 43 6f 6d 70 |       D|ata Comp|
|000011f0| 72 65 73 73 69 6f 6e 3a | 20 20 4d 65 74 68 6f 64 |ression:|  Method|
|00001200| 73 20 61 6e 64 20 54 68 | 65 6f 72 79 2c 20 70 70 |s and Th|eory, pp|
|00001210| 2e 20 34 39 2d 35 30 2e | 0a 58 20 2a 20 20 20 20 |. 49-50.|.X *    |
|00001220| 20 20 20 20 20 20 43 6f | 6d 70 75 74 65 72 20 53 |      Co|mputer S|
|00001230| 63 69 65 6e 63 65 20 50 | 72 65 73 73 2c 20 31 39 |cience P|ress, 19|
|00001240| 38 38 2e 20 20 49 53 42 | 4e 20 30 2d 37 31 36 37 |88.  ISB|N 0-7167|
|00001250| 2d 38 31 35 36 2d 35 2e | 0a 58 20 2a 0a 58 20 2a |-8156-5.|.X *.X *|
|00001260| 20 20 49 4e 54 45 52 46 | 41 43 45 0a 58 20 2a 0a |  INTERF|ACE.X *.|
|00001270| 58 20 2a 20 20 20 20 20 | 20 49 6d 70 45 72 72 20 |X *     | ImpErr |
|00001280| 63 74 5f 69 6e 69 74 20 | 28 76 6f 69 64 29 0a 58 |ct_init |(void).X|
|00001290| 20 2a 20 20 20 20 20 20 | 20 20 20 20 49 6e 69 74 | *      |    Init|
|000012a0| 69 61 6c 69 7a 65 20 74 | 68 65 20 63 6f 64 65 20 |ialize t|he code |
|000012b0| 74 72 65 65 20 72 6f 75 | 74 69 6e 65 73 2e 20 20 |tree rou|tines.  |
|000012c0| 54 68 69 73 20 72 6f 75 | 74 69 6e 65 20 6d 75 73 |This rou|tine mus|
|000012d0| 74 20 62 65 0a 58 20 2a | 20 20 20 20 20 20 20 20 |t be.X *|        |
|000012e0| 20 20 63 61 6c 6c 65 64 | 20 62 65 66 6f 72 65 20 |  called| before |
|000012f0| 61 6e 79 20 6f 74 68 65 | 72 20 63 6f 64 65 20 74 |any othe|r code t|
|00001300| 72 65 65 20 72 6f 75 74 | 69 6e 65 73 20 6d 61 79 |ree rout|ines may|
|00001310| 20 62 65 20 63 61 6c 6c | 65 64 2e 0a 58 20 2a 0a | be call|ed..X *.|
|00001320| 58 20 2a 20 20 20 20 20 | 20 49 6d 70 45 72 72 20 |X *     | ImpErr |
|00001330| 63 74 5f 74 61 6c 6c 79 | 20 28 4d 41 54 43 48 20 |ct_tally| (MATCH |
|00001340| 2a 6d 61 29 0a 58 20 2a | 20 20 20 20 20 20 20 20 |*ma).X *|        |
|00001350| 20 20 54 61 6c 6c 79 20 | 61 20 22 73 74 72 69 6e |  Tally |a "strin|
|00001360| 67 20 6d 61 74 63 68 22 | 20 64 61 74 61 20 73 65 |g match"| data se|
|00001370| 74 2e 20 20 54 68 65 20 | 74 61 6c 6c 79 20 72 65 |t.  The |tally re|
|00001380| 73 75 6c 74 73 20 77 69 | 6c 6c 20 62 65 0a 58 20 |sults wi|ll be.X |
|00001390| 2a 20 20 20 20 20 20 20 | 20 20 20 75 73 65 64 20 |*       |   used |
|000013a0| 74 6f 20 64 65 74 65 72 | 6d 69 6e 65 20 68 6f 77 |to deter|mine how|
|000013b0| 20 6c 61 72 67 65 20 74 | 68 65 20 69 6d 70 6c 6f | large t|he implo|
|000013c0| 64 65 64 20 72 65 73 75 | 6c 74 20 77 69 6c 6c 20 |ded resu|lt will |
|000013d0| 62 65 2e 0a 58 20 2a 0a | 58 20 2a 20 20 20 20 20 |be..X *.|X *     |
|000013e0| 20 49 6d 70 45 72 72 20 | 63 74 5f 6d 6b 74 72 65 | ImpErr |ct_mktre|
|000013f0| 65 73 20 28 46 44 41 54 | 41 20 2a 66 64 29 0a 58 |es (FDAT|A *fd).X|
|00001400| 20 2a 20 20 20 20 20 20 | 20 20 20 20 43 6f 6e 73 | *      |    Cons|
|00001410| 74 72 75 63 74 20 61 6c | 6c 20 63 6f 64 65 20 74 |truct al|l code t|
|00001420| 72 65 65 73 2c 20 61 6e | 64 20 74 68 65 6e 20 64 |rees, an|d then d|
|00001430| 65 74 65 72 6d 69 6e 65 | 20 68 6f 77 20 62 69 67 |etermine| how big|
|00001440| 20 74 68 65 0a 58 20 2a | 20 20 20 20 20 20 20 20 | the.X *|        |
|00001450| 20 20 69 6d 70 6c 6f 64 | 65 64 20 66 69 6c 65 20 |  implod|ed file |
|00001460| 77 69 6c 6c 20 62 65 20 | 75 6e 64 65 72 20 62 6f |will be |under bo|
|00001470| 74 68 20 22 6c 69 74 65 | 72 61 6c 20 74 72 65 65 |th "lite|ral tree|
|00001480| 22 20 61 6e 64 20 22 6e | 6f 0a 58 20 2a 20 20 20 |" and "n|o.X *   |
|00001490| 20 20 20 20 20 20 20 6c | 69 74 65 72 61 6c 20 74 |       l|iteral t|
|000014a0| 72 65 65 22 20 63 6f 6e | 64 69 74 69 6f 6e 73 2e |ree" con|ditions.|
|000014b0| 20 20 43 68 6f 6f 73 65 | 20 74 68 65 20 62 65 73 |  Choose| the bes|
|000014c0| 74 20 6f 70 74 69 6f 6e | 2e 0a 58 20 2a 0a 58 20 |t option|..X *.X |
|000014d0| 2a 20 20 20 20 20 20 49 | 6d 70 45 72 72 20 63 74 |*      I|mpErr ct|
|000014e0| 5f 77 72 74 72 65 65 73 | 20 28 46 49 4c 45 20 2a |_wrtrees| (FILE *|
|000014f0| 6f 75 74 66 70 29 0a 58 | 20 2a 20 20 20 20 20 20 |outfp).X| *      |
|00001500| 20 20 20 20 4f 75 74 70 | 75 74 20 74 68 65 20 63 |    Outp|ut the c|
|00001510| 6f 64 65 20 74 72 65 65 | 73 20 74 6f 20 74 68 65 |ode tree|s to the|
|00001520| 20 5a 49 50 20 66 69 6c | 65 2e 0a 58 20 2a 0a 58 | ZIP fil|e..X *.X|
|00001530| 20 2a 20 20 20 20 20 20 | 49 6d 70 45 72 72 20 63 | *      |ImpErr c|
|00001540| 74 5f 77 72 64 61 74 61 | 20 28 46 49 4c 45 20 2a |t_wrdata| (FILE *|
|00001550| 6f 75 74 66 70 29 0a 58 | 20 2a 20 20 20 20 20 20 |outfp).X| *      |
|00001560| 20 20 20 20 4f 75 74 70 | 75 74 20 74 68 65 20 66 |    Outp|ut the f|
|00001570| 69 6c 65 20 64 61 74 61 | 20 74 6f 20 74 68 65 20 |ile data| to the |
|00001580| 5a 49 50 20 66 69 6c 65 | 2e 0a 58 20 2a 0a 58 20 |ZIP file|..X *.X |
|00001590| 2a 20 20 20 20 20 20 49 | 6d 70 45 72 72 20 63 74 |*      I|mpErr ct|
|000015a0| 5f 77 69 6e 64 75 70 20 | 28 76 6f 69 64 29 0a 58 |_windup |(void).X|
|000015b0| 20 2a 20 20 20 20 20 20 | 20 20 20 20 44 65 61 6c | *      |    Deal|
|000015c0| 6c 6f 63 61 74 65 20 61 | 6c 6c 20 63 6f 64 65 20 |locate a|ll code |
|000015d0| 74 72 65 65 73 2e 0a 58 | 20 2a 2f 0a 58 0a 58 0a |trees..X| */.X.X.|
|000015e0| 58 23 69 66 64 65 66 20 | 44 45 42 55 47 0a 58 23 |X#ifdef |DEBUG.X#|
|000015f0| 20 20 20 64 65 66 69 6e | 65 20 56 41 4c 49 44 41 |   defin|e VALIDA|
|00001600| 54 45 0a 58 23 65 6e 64 | 69 66 20 2f 2a 20 44 45 |TE.X#end|if /* DE|
|00001610| 42 55 47 20 2a 2f 0a 58 | 0a 58 23 69 6e 63 6c 75 |BUG */.X|.X#inclu|
|00001620| 64 65 20 22 69 6d 70 6c | 6f 64 65 2e 68 22 0a 58 |de "impl|ode.h".X|
|00001630| 0a 58 0a 58 2f 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |.X.X/***|********|
|00001640| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001650| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001660| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00001670| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 0a 58 20 2a |********|****.X *|
|00001680| 0a 58 20 2a 20 4c 6f 63 | 61 6c 20 64 61 74 61 20 |.X * Loc|al data |
|00001690| 75 73 65 64 20 62 79 20 | 74 68 65 20 22 63 6f 64 |used by |the "cod|
|000016a0| 65 20 74 72 65 65 22 20 | 72 6f 75 74 69 6e 65 73 |e tree" |routines|
|000016b0| 2e 0a 58 20 2a 2f 0a 58 | 0a 58 0a 58 2f 2a 20 44 |..X */.X|.X.X/* D|
|000016c0| 61 74 61 20 73 74 72 75 | 63 74 75 72 65 20 64 65 |ata stru|cture de|
|000016d0| 73 63 72 69 62 69 6e 67 | 20 61 20 73 69 6e 67 6c |scribing| a singl|
|000016e0| 65 20 76 61 6c 75 65 20 | 61 6e 64 20 69 74 73 20 |e value |and its |
|000016f0| 63 6f 64 65 20 73 74 72 | 69 6e 67 2e 20 2a 2f 0a |code str|ing. */.|
|00001700| 74 79 70 65 64 65 66 0a | 73 74 72 75 63 74 20 20 |typedef.|struct  |
|00001710| 63 74 5f 64 61 74 61 0a | 58 20 20 20 20 7b 20 20 |ct_data.|X    {  |
|00001720| 20 55 4c 5f 49 4e 54 20 | 20 63 74 5f 66 72 65 71 | UL_INT | ct_freq|
|00001730| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;       |        |
|00001740| 20 2f 2a 20 66 72 65 71 | 75 65 6e 63 79 20 63 6f | /* freq|uency co|
|00001750| 75 6e 74 20 2a 2f 0a 58 | 20 20 20 20 20 20 20 20 |unt */.X|        |
|00001760| 55 53 5f 49 4e 54 20 20 | 63 74 5f 63 6f 64 65 3b |US_INT  |ct_code;|
|00001770| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001780| 2f 2a 20 62 69 74 20 73 | 74 72 69 6e 67 20 2a 2f |/* bit s|tring */|
|00001790| 0a 58 20 20 20 20 20 20 | 20 20 55 5f 43 48 41 52 |.X      |  U_CHAR|
|000017a0| 20 20 63 74 5f 6c 65 6e | 3b 20 20 20 20 20 20 20 |  ct_len|;       |
|000017b0| 20 20 20 20 20 20 20 20 | 20 20 2f 2a 20 6c 65 6e |        |  /* len|
|000017c0| 67 74 68 20 6f 66 20 62 | 69 74 20 73 74 72 69 6e |gth of b|it strin|
|000017d0| 67 20 2a 2f 0a 58 20 20 | 20 20 20 20 20 20 55 5f |g */.X  |      U_|
|000017e0| 43 48 41 52 20 20 63 74 | 5f 76 61 6c 3b 20 20 20 |CHAR  ct|_val;   |
|000017f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 2a |        |      /*|
|00001800| 20 73 6f 75 72 63 65 20 | 76 61 6c 75 65 20 2a 2f | source |value */|
|00001810| 0a 58 20 20 20 20 7d 0a | 58 20 20 20 20 54 52 44 |.X    }.|X    TRD|
|00001820| 41 54 41 3b 0a 58 0a 58 | 0a 58 2f 2a 0a 58 20 2a |ATA;.X.X|.X/*.X *|
|00001830| 20 44 61 74 61 20 73 74 | 72 75 63 74 75 72 65 20 | Data st|ructure |
|00001840| 66 6f 72 20 72 65 2d 73 | 6f 72 74 69 6e 67 20 73 |for re-s|orting s|
|00001850| 6f 75 72 63 65 20 76 61 | 6c 75 65 73 20 62 79 20 |ource va|lues by |
|00001860| 62 69 74 20 73 74 72 69 | 6e 67 20 6c 65 6e 67 74 |bit stri|ng lengt|
|00001870| 68 3b 0a 58 20 2a 20 75 | 73 65 64 20 64 75 72 69 |h;.X * u|sed duri|
|00001880| 6e 67 20 74 72 65 65 20 | 67 65 6e 65 72 61 74 69 |ng tree |generati|
|00001890| 6f 6e 2e 0a 58 20 2a 2f | 0a 74 79 70 65 64 65 66 |on..X */|.typedef|
|000018a0| 0a 73 74 72 75 63 74 20 | 20 63 74 5f 72 65 73 6f |.struct | ct_reso|
|000018b0| 72 74 0a 58 20 20 20 20 | 7b 20 20 20 55 5f 43 48 |rt.X    |{   U_CH|
|000018c0| 41 52 20 20 63 74 5f 72 | 6c 65 6e 3b 20 20 20 20 |AR  ct_r|len;    |
|000018d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 6c |        |    /* l|
|000018e0| 65 6e 67 74 68 20 6f 66 | 20 62 69 74 20 73 74 72 |ength of| bit str|
|000018f0| 69 6e 67 20 2a 2f 0a 58 | 20 20 20 20 20 20 20 20 |ing */.X|        |
|00001900| 55 5f 43 48 41 52 20 20 | 63 74 5f 72 76 61 6c 3b |U_CHAR  |ct_rval;|
|00001910| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001920| 2f 2a 20 73 6f 75 72 63 | 65 20 76 61 6c 75 65 20 |/* sourc|e value |
|00001930| 2a 2f 0a 58 23 69 66 64 | 65 66 20 56 4d 53 0a 58 |*/.X#ifd|ef VMS.X|
|00001940| 20 20 20 20 20 20 20 20 | 55 53 5f 49 4e 54 20 20 |        |US_INT  |
|00001950| 64 75 6d 6d 79 3b 20 20 | 20 20 20 20 20 20 20 20 |dummy;  |        |
|00001960| 20 20 20 20 20 20 20 20 | 2f 2a 20 62 65 63 61 75 |        |/* becau|
|00001970| 73 65 20 6f 66 20 62 75 | 67 20 69 6e 20 71 73 6f |se of bu|g in qso|
|00001980| 72 74 28 29 20 2a 2f 0a | 58 23 65 6e 64 69 66 20 |rt() */.|X#endif |
|00001990| 2f 2a 20 56 4d 53 20 2a | 2f 0a 58 20 20 20 20 7d |/* VMS *|/.X    }|
|000019a0| 0a 58 20 20 20 20 52 45 | 53 4f 52 54 3b 0a 58 0a |.X    RE|SORT;.X.|
|000019b0| 58 0a 58 2f 2a 20 48 65 | 61 64 65 72 20 66 6f 72 |X.X/* He|ader for|
|000019c0| 20 61 20 63 6f 64 65 20 | 74 72 65 65 2e 20 2a 2f | a code |tree. */|
|000019d0| 0a 74 79 70 65 64 65 66 | 0a 73 74 72 75 63 74 20 |.typedef|.struct |
|000019e0| 20 63 74 5f 64 65 73 63 | 0a 58 20 20 20 20 7b 20 | ct_desc|.X    { |
|000019f0| 20 20 54 52 44 41 54 41 | 20 2a 63 74 5f 61 72 72 |  TRDATA| *ct_arr|
|00001a00| 61 79 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |ay;     |        |
|00001a10| 20 20 2f 2a 20 61 72 72 | 61 79 20 6f 66 20 54 52 |  /* arr|ay of TR|
|00001a20| 44 41 54 41 20 2a 2f 0a | 58 20 20 20 20 20 20 20 |DATA */.|X       |
|00001a30| 20 69 6e 74 20 20 20 20 | 20 63 74 5f 73 69 7a 65 | int    | ct_size|
|00001a40| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;       |        |
|00001a50| 20 2f 2a 20 23 20 6f 66 | 20 65 6e 74 72 69 65 73 | /* # of| entries|
|00001a60| 20 69 6e 20 74 72 65 65 | 20 2a 2f 0a 58 20 20 20 | in tree| */.X   |
|00001a70| 20 7d 0a 58 20 20 20 20 | 54 52 44 45 53 43 3b 0a | }.X    |TRDESC;.|
|00001a80| 58 0a 58 0a 58 2f 2a 0a | 58 20 2a 20 43 75 72 72 |X.X.X/*.|X * Curr|
|00001a90| 65 6e 74 6c 79 20 61 63 | 74 69 76 65 20 63 6f 64 |ently ac|tive cod|
|00001aa0| 65 20 74 72 65 65 73 2e | 0a 58 20 2a 20 57 65 20 |e trees.|.X * We |
|00001ab0| 61 6c 6c 6f 77 20 66 6f | 72 20 66 69 76 65 20 74 |allow fo|r five t|
|00001ac0| 72 65 65 73 20 28 6f 6e | 65 20 6c 69 74 65 72 61 |rees (on|e litera|
|00001ad0| 6c 20 74 72 65 65 2c 20 | 74 77 6f 20 6c 65 6e 67 |l tree, |two leng|
|00001ae0| 74 68 20 74 72 65 65 73 | 2c 20 61 6e 64 0a 58 20 |th trees|, and.X |
|00001af0| 2a 20 74 77 6f 20 64 69 | 73 74 61 6e 63 65 20 74 |* two di|stance t|
|00001b00| 72 65 65 73 29 20 73 6f | 20 74 68 61 74 20 77 65 |rees) so| that we|
|00001b10| 20 63 61 6e 20 65 76 61 | 6c 75 61 74 65 20 74 68 | can eva|luate th|
|00001b20| 65 20 74 6f 74 61 6c 20 | 63 6f 6d 70 72 65 73 73 |e total |compress|
|00001b30| 69 6f 6e 0a 58 20 2a 20 | 77 69 74 68 20 6f 72 20 |ion.X * |with or |
|00001b40| 77 69 74 68 6f 75 74 20 | 74 68 65 20 75 73 65 20 |without |the use |
|00001b50| 6f 66 20 74 68 65 20 6c | 69 74 65 72 61 6c 20 74 |of the l|iteral t|
|00001b60| 72 65 65 2e 20 20 52 65 | 6d 65 6d 62 65 72 20 74 |ree.  Re|member t|
|00001b70| 68 61 74 20 74 68 65 0a | 58 20 2a 20 6d 69 6e 69 |hat the.|X * mini|
|00001b80| 6d 75 6d 20 6d 61 74 63 | 68 69 6e 67 20 64 69 73 |mum matc|hing dis|
|00001b90| 74 61 6e 63 65 20 64 65 | 70 65 6e 64 73 20 6f 6e |tance de|pends on|
|00001ba0| 20 77 68 65 74 68 65 72 | 20 6f 72 20 6e 6f 74 20 | whether| or not |
|00001bb0| 61 20 6c 69 74 65 72 61 | 6c 20 74 72 65 65 0a 58 |a litera|l tree.X|
|00001bc0| 20 2a 20 69 73 20 75 73 | 65 64 3b 20 68 65 6e 63 | * is us|ed; henc|
|00001bd0| 65 2c 20 74 68 65 20 22 | 6c 65 6e 67 74 68 22 20 |e, the "|length" |
|00001be0| 61 6e 64 20 22 64 69 73 | 74 61 6e 63 65 22 20 74 |and "dis|tance" t|
|00001bf0| 72 65 65 73 20 77 69 6c | 6c 20 64 69 66 66 65 72 |rees wil|l differ|
|00001c00| 2e 0a 58 20 2a 2f 0a 58 | 23 64 65 66 69 6e 65 20 |..X */.X|#define |
|00001c10| 4d 41 58 54 52 45 45 53 | 20 20 20 20 20 20 20 20 |MAXTREES|        |
|00001c20| 35 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |5       |        |
|00001c30| 2f 2a 20 6d 61 78 20 23 | 20 6f 66 20 74 72 65 65 |/* max #| of tree|
|00001c40| 73 20 61 74 20 6f 6e 63 | 65 20 2a 2f 0a 6c 6f 63 |s at onc|e */.loc|
|00001c50| 61 6c 20 20 20 54 52 44 | 45 53 43 20 20 63 74 5f |al   TRD|ESC  ct_|
|00001c60| 74 61 62 6c 65 5b 4d 41 | 58 54 52 45 45 53 5d 3b |table[MA|XTREES];|
|00001c70| 0a 58 0a 58 0a 58 2f 2a | 20 4d 61 63 72 6f 20 74 |.X.X.X/*| Macro t|
|00001c80| 6f 20 76 61 6c 69 64 61 | 74 65 20 61 20 63 6f 64 |o valida|te a cod|
|00001c90| 65 20 74 72 65 65 20 68 | 61 6e 64 6c 65 2e 20 2a |e tree h|andle. *|
|00001ca0| 2f 0a 58 23 64 65 66 69 | 6e 65 20 56 41 4c 49 44 |/.X#defi|ne VALID|
|00001cb0| 5f 48 41 4e 44 4c 45 28 | 78 29 20 5c 0a 58 20 20 |_HANDLE(|x) \.X  |
|00001cc0| 20 20 20 20 20 20 28 28 | 78 29 20 3e 3d 20 30 20 |      ((|x) >= 0 |
|00001cd0| 26 26 20 28 78 29 20 3c | 20 4d 41 58 54 52 45 45 |&& (x) <| MAXTREE|
|00001ce0| 53 20 26 26 20 63 74 5f | 74 61 62 6c 65 5b 78 5d |S && ct_|table[x]|
|00001cf0| 2e 63 74 5f 61 72 72 61 | 79 20 21 3d 20 4e 55 4c |.ct_arra|y != NUL|
|00001d00| 4c 29 0a 58 0a 58 0a 58 | 2f 2a 0a 58 20 2a 20 41 |L).X.X.X|/*.X * A|
|00001d10| 73 73 6f 72 74 65 64 20 | 66 72 65 71 75 65 6e 63 |ssorted |frequenc|
|00001d20| 79 20 63 6f 75 6e 74 73 | 2e 0a 58 20 2a 20 54 68 |y counts|..X * Th|
|00001d30| 65 20 22 4d 69 6e 69 6d | 75 6d 20 4d 61 74 63 68 |e "Minim|um Match|
|00001d40| 20 4c 65 6e 67 74 68 22 | 20 28 4d 4d 4c 29 20 69 | Length"| (MML) i|
|00001d50| 73 20 32 20 69 66 20 61 | 20 22 6c 69 74 65 72 61 |s 2 if a| "litera|
|00001d60| 6c 20 63 68 61 72 61 63 | 74 65 72 22 20 63 6f 64 |l charac|ter" cod|
|00001d70| 65 0a 58 20 2a 20 74 72 | 65 65 20 69 73 20 6e 6f |e.X * tr|ee is no|
|00001d80| 74 20 75 73 65 64 2c 20 | 6f 72 20 33 20 69 66 20 |t used, |or 3 if |
|00001d90| 61 20 22 6c 69 74 65 72 | 61 6c 20 63 68 61 72 61 |a "liter|al chara|
|00001da0| 63 74 65 72 22 20 74 72 | 65 65 20 69 73 20 75 73 |cter" tr|ee is us|
|00001db0| 65 64 2e 20 20 54 68 75 | 73 2c 0a 58 20 2a 20 77 |ed.  Thu|s,.X * w|
|00001dc0| 65 20 6e 65 65 64 20 74 | 6f 20 6b 65 65 70 20 74 |e need t|o keep t|
|00001dd0| 77 6f 20 73 65 74 73 20 | 6f 66 20 22 6c 65 6e 67 |wo sets |of "leng|
|00001de0| 74 68 22 20 61 6e 64 20 | 22 64 69 73 74 61 6e 63 |th" and |"distanc|
|00001df0| 65 22 20 66 72 65 71 75 | 65 6e 63 79 20 63 6f 75 |e" frequ|ency cou|
|00001e00| 6e 74 73 2e 0a 58 20 2a | 20 41 6c 73 6f 2c 20 32 |nts..X *| Also, 2|
|00001e10| 2d 63 68 61 72 61 63 74 | 65 72 20 6d 61 74 63 68 |-charact|er match|
|00001e20| 65 73 20 6e 65 65 64 20 | 74 6f 20 62 65 20 63 6f |es need |to be co|
|00001e30| 75 6e 74 65 64 20 73 65 | 70 61 72 61 74 65 6c 79 |unted se|parately|
|00001e40| 3b 20 64 65 70 65 6e 64 | 69 6e 67 0a 58 20 2a 20 |; depend|ing.X * |
|00001e50| 6f 6e 20 77 68 65 74 68 | 65 72 20 61 20 22 6c 69 |on wheth|er a "li|
|00001e60| 74 65 72 61 6c 20 63 68 | 61 72 61 63 74 65 72 22 |teral ch|aracter"|
|00001e70| 20 74 72 65 65 20 69 73 | 20 75 73 65 64 20 6f 72 | tree is| used or|
|00001e80| 20 6e 6f 74 2c 20 74 68 | 65 73 65 20 77 69 6c 6c | not, th|ese will|
|00001e90| 20 62 65 0a 58 20 2a 20 | 70 72 6f 63 65 73 73 65 | be.X * |processe|
|00001ea0| 64 20 65 69 74 68 65 72 | 20 61 73 20 6c 69 74 65 |d either| as lite|
|00001eb0| 72 61 6c 20 63 68 61 72 | 61 63 74 65 72 73 20 6f |ral char|acters o|
|00001ec0| 72 20 61 73 20 64 69 73 | 74 61 6e 63 65 2f 6c 65 |r as dis|tance/le|
|00001ed0| 6e 67 74 68 20 70 61 69 | 72 73 2e 0a 58 20 2a 2f |ngth pai|rs..X */|
|00001ee0| 0a 58 0a 58 2f 2a 20 54 | 6f 74 61 6c 20 6e 75 6d |.X.X/* T|otal num|
|00001ef0| 62 65 72 20 6f 66 20 73 | 6f 75 72 63 65 20 76 61 |ber of s|ource va|
|00001f00| 6c 75 65 73 20 66 72 6f | 6d 20 50 61 73 73 20 4f |lues fro|m Pass O|
|00001f10| 6e 65 2e 20 2a 2f 0a 6c | 6f 63 61 6c 20 20 20 6c |ne. */.l|ocal   l|
|00001f20| 6f 6e 67 20 20 20 20 63 | 74 5f 6c 69 74 63 5f 6e |ong    c|t_litc_n|
|00001f30| 75 6d 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 2f |um;     |       /|
|00001f40| 2a 20 74 6f 74 61 6c 20 | 23 20 6c 69 74 65 72 61 |* total |# litera|
|00001f50| 6c 20 63 68 61 72 73 20 | 2a 2f 0a 6c 6f 63 61 6c |l chars |*/.local|
|00001f60| 20 20 20 6c 6f 6e 67 20 | 20 20 20 63 74 5f 6c 69 |   long |   ct_li|
|00001f70| 74 32 5f 6e 75 6d 3b 20 | 20 20 20 20 20 20 20 20 |t2_num; |        |
|00001f80| 20 20 20 2f 2a 20 74 6f | 74 61 6c 20 23 20 6f 66 |   /* to|tal # of|
|00001f90| 20 32 2d 63 68 61 72 20 | 6d 61 74 63 68 65 73 20 | 2-char |matches |
|00001fa0| 2a 2f 0a 6c 6f 63 61 6c | 20 20 20 6c 6f 6e 67 20 |*/.local|   long |
|00001fb0| 20 20 20 63 74 5f 73 74 | 72 67 5f 6e 75 6d 3b 20 |   ct_st|rg_num; |
|00001fc0| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 74 6f |        |   /* to|
|00001fd0| 74 61 6c 20 23 20 6f 66 | 20 73 74 72 69 6e 67 20 |tal # of| string |
|00001fe0| 6d 61 74 63 68 65 73 20 | 2a 2f 0a 58 0a 58 2f 2a |matches |*/.X.X/*|
|00001ff0| 20 53 6f 75 72 63 65 20 | 76 61 6c 75 65 20 66 72 | Source |value fr|
|00002000| 65 71 75 65 6e 63 69 65 | 73 20 66 6f 72 20 74 68 |equencie|s for th|
|00002010| 65 20 66 69 76 65 20 74 | 72 65 65 73 2e 20 2a 2f |e five t|rees. */|
|00002020| 0a 6c 6f 63 61 6c 20 20 | 20 6c 6f 6e 67 20 20 20 |.local  | long   |
|00002030| 20 63 74 5f 6c 69 74 63 | 5f 66 72 65 71 5b 32 35 | ct_litc|_freq[25|
|00002040| 36 5d 3b 20 20 20 20 20 | 20 2f 2a 20 6c 69 74 65 |6];     | /* lite|
|00002050| 72 61 6c 20 63 68 61 72 | 61 63 74 65 72 20 66 72 |ral char|acter fr|
|00002060| 65 71 73 20 2a 2f 0a 6c | 6f 63 61 6c 20 20 20 6c |eqs */.l|ocal   l|
|00002070| 6f 6e 67 20 20 20 20 63 | 74 5f 6c 65 6e 32 5f 66 |ong    c|t_len2_f|
|00002080| 72 65 71 5b 36 34 5d 3b | 20 20 20 20 20 20 20 2f |req[64];|       /|
|00002090| 2a 20 6c 65 6e 67 74 68 | 20 66 72 65 71 73 20 28 |* length| freqs (|
|000020a0| 4d 4d 4c 3d 32 29 20 2a | 2f 0a 6c 6f 63 61 6c 20 |MML=2) *|/.local |
|000020b0| 20 20 6c 6f 6e 67 20 20 | 20 20 63 74 5f 6c 65 6e |  long  |  ct_len|
|000020c0| 33 5f 66 72 65 71 5b 36 | 34 5d 3b 20 20 20 20 20 |3_freq[6|4];     |
|000020d0| 20 20 2f 2a 20 6c 65 6e | 67 74 68 20 66 72 65 71 |  /* len|gth freq|
|000020e0| 73 20 28 4d 4d 4c 3d 33 | 29 20 2a 2f 0a 6c 6f 63 |s (MML=3|) */.loc|
|000020f0| 61 6c 20 20 20 6c 6f 6e | 67 20 20 20 20 63 74 5f |al   lon|g    ct_|
|00002100| 64 73 74 32 5f 66 72 65 | 71 5b 36 34 5d 3b 20 20 |dst2_fre|q[64];  |
|00002110| 20 20 20 20 20 2f 2a 20 | 64 69 73 74 61 6e 63 65 |     /* |distance|
|00002120| 20 66 72 65 71 73 20 28 | 4d 4d 4c 3d 32 29 20 2a | freqs (|MML=2) *|
|00002130| 2f 0a 6c 6f 63 61 6c 20 | 20 20 6c 6f 6e 67 20 20 |/.local |  long  |
|00002140| 20 20 63 74 5f 64 73 74 | 33 5f 66 72 65 71 5b 36 |  ct_dst|3_freq[6|
|00002150| 34 5d 3b 20 20 20 20 20 | 20 20 2f 2a 20 64 69 73 |4];     |  /* dis|
|00002160| 74 61 6e 63 65 20 66 72 | 65 71 73 20 28 4d 4d 4c |tance fr|eqs (MML|
|00002170| 3d 33 29 20 2a 2f 0a 58 | 0a 58 2f 2a 20 4e 75 6d |=3) */.X|.X/* Num|
|00002180| 62 65 72 20 6f 66 20 62 | 69 74 73 20 73 61 76 65 |ber of b|its save|
|00002190| 64 20 62 79 20 75 73 69 | 6e 67 20 65 61 63 68 20 |d by usi|ng each |
|000021a0| 6f 66 20 74 68 65 20 74 | 72 65 65 73 2e 20 2a 2f |of the t|rees. */|
|000021b0| 0a 6c 6f 63 61 6c 20 20 | 20 6c 6f 6e 67 20 20 20 |.local  | long   |
|000021c0| 20 63 74 5f 6c 69 74 63 | 5f 73 61 76 65 64 3b 20 | ct_litc|_saved; |
|000021d0| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 6c 69 74 65 |        | /* lite|
|000021e0| 72 61 6c 20 74 72 65 65 | 20 2a 2f 0a 6c 6f 63 61 |ral tree| */.loca|
|000021f0| 6c 20 20 20 6c 6f 6e 67 | 20 20 20 20 63 74 5f 6c |l   long|    ct_l|
|00002200| 65 6e 32 5f 73 61 76 65 | 64 3b 20 20 20 20 20 20 |en2_save|d;      |
|00002210| 20 20 20 20 2f 2a 20 6c | 65 6e 67 74 68 20 74 72 |    /* l|ength tr|
|00002220| 65 65 20 28 4d 4d 4c 3d | 32 29 20 2a 2f 0a 6c 6f |ee (MML=|2) */.lo|
|00002230| 63 61 6c 20 20 20 6c 6f | 6e 67 20 20 20 20 63 74 |cal   lo|ng    ct|
|00002240| 5f 6c 65 6e 33 5f 73 61 | 76 65 64 3b 20 20 20 20 |_len3_sa|ved;    |
|00002250| 20 20 20 20 20 20 2f 2a | 20 6c 65 6e 67 74 68 20 |      /*| length |
|00002260| 74 72 65 65 20 28 4d 4d | 4c 3d 33 29 20 2a 2f 0a |tree (MM|L=3) */.|
|00002270| 6c 6f 63 61 6c 20 20 20 | 6c 6f 6e 67 20 20 20 20 |local   |long    |
|00002280| 63 74 5f 64 73 74 32 5f | 73 61 76 65 64 3b 20 20 |ct_dst2_|saved;  |
|00002290| 20 20 20 20 20 20 20 20 | 2f 2a 20 64 69 73 74 61 |        |/* dista|
|000022a0| 6e 63 65 20 74 72 65 65 | 20 28 4d 4d 4c 3d 32 29 |nce tree| (MML=2)|
|000022b0| 20 2a 2f 0a 6c 6f 63 61 | 6c 20 20 20 6c 6f 6e 67 | */.loca|l   long|
|000022c0| 20 20 20 20 63 74 5f 64 | 73 74 33 5f 73 61 76 65 |    ct_d|st3_save|
|000022d0| 64 3b 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 64 |d;      |    /* d|
|000022e0| 69 73 74 61 6e 63 65 20 | 74 72 65 65 20 28 4d 4d |istance |tree (MM|
|000022f0| 4c 3d 33 29 20 2a 2f 0a | 58 0a 58 2f 2a 20 48 61 |L=3) */.|X.X/* Ha|
|00002300| 6e 64 6c 65 73 20 66 6f | 72 20 74 68 65 20 63 6f |ndles fo|r the co|
|00002310| 64 65 20 74 72 65 65 73 | 20 74 6f 20 62 65 20 75 |de trees| to be u|
|00002320| 73 65 64 2e 20 2a 2f 0a | 6c 6f 63 61 6c 20 20 20 |sed. */.|local   |
|00002330| 69 6e 74 20 20 20 20 20 | 63 74 5f 6c 69 74 63 5f |int     |ct_litc_|
|00002340| 74 72 65 65 3b 20 20 20 | 20 20 20 20 20 20 20 20 |tree;   |        |
|00002350| 2f 2a 20 74 65 6d 70 20 | 6c 69 74 65 72 61 6c 20 |/* temp |literal |
|00002360| 74 72 65 65 20 2a 2f 0a | 6c 6f 63 61 6c 20 20 20 |tree */.|local   |
|00002370| 69 6e 74 20 20 20 20 20 | 63 74 5f 6c 65 6e 32 5f |int     |ct_len2_|
|00002380| 74 72 65 65 3b 20 20 20 | 20 20 20 20 20 20 20 20 |tree;   |        |
|00002390| 2f 2a 20 74 65 6d 70 20 | 6c 65 6e 67 74 68 20 74 |/* temp |length t|
|000023a0| 72 65 65 20 28 4d 4d 4c | 3d 32 29 20 2a 2f 0a 6c |ree (MML|=2) */.l|
|000023b0| 6f 63 61 6c 20 20 20 69 | 6e 74 20 20 20 20 20 63 |ocal   i|nt     c|
|000023c0| 74 5f 6c 65 6e 33 5f 74 | 72 65 65 3b 20 20 20 20 |t_len3_t|ree;    |
|000023d0| 20 20 20 20 20 20 20 2f | 2a 20 74 65 6d 70 20 6c |       /|* temp l|
|000023e0| 65 6e 67 74 68 20 74 72 | 65 65 20 28 4d 4d 4c 3d |ength tr|ee (MML=|
|000023f0| 33 29 20 2a 2f 0a 6c 6f | 63 61 6c 20 20 20 69 6e |3) */.lo|cal   in|
|00002400| 74 20 20 20 20 20 63 74 | 5f 64 73 74 32 5f 74 72 |t     ct|_dst2_tr|
|00002410| 65 65 3b 20 20 20 20 20 | 20 20 20 20 20 20 2f 2a |ee;     |      /*|
|00002420| 20 74 65 6d 70 20 64 69 | 73 74 61 6e 63 65 20 74 | temp di|stance t|
|00002430| 72 65 65 20 28 4d 4d 4c | 3d 32 29 20 2a 2f 0a 6c |ree (MML|=2) */.l|
|00002440| 6f 63 61 6c 20 20 20 69 | 6e 74 20 20 20 20 20 63 |ocal   i|nt     c|
|00002450| 74 5f 64 73 74 33 5f 74 | 72 65 65 3b 20 20 20 20 |t_dst3_t|ree;    |
|00002460| 20 20 20 20 20 20 20 2f | 2a 20 74 65 6d 70 20 64 |       /|* temp d|
|00002470| 69 73 74 61 6e 63 65 20 | 74 72 65 65 20 28 4d 4d |istance |tree (MM|
|00002480| 4c 3d 33 29 20 2a 2f 0a | 6c 6f 63 61 6c 20 20 20 |L=3) */.|local   |
|00002490| 69 6e 74 20 20 20 20 20 | 6c 69 74 5f 74 72 65 65 |int     |lit_tree|
|000024a0| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;       |        |
|000024b0| 2f 2a 20 6c 69 74 65 72 | 61 6c 20 74 72 65 65 20 |/* liter|al tree |
|000024c0| 28 2d 31 20 69 66 20 6e | 6f 6e 65 29 20 2a 2f 0a |(-1 if n|one) */.|
|000024d0| 6c 6f 63 61 6c 20 20 20 | 69 6e 74 20 20 20 20 20 |local   |int     |
|000024e0| 6c 65 6e 5f 74 72 65 65 | 3b 20 20 20 20 20 20 20 |len_tree|;       |
|000024f0| 20 20 20 20 20 20 20 20 | 2f 2a 20 6c 65 6e 67 74 |        |/* lengt|
|00002500| 68 20 74 72 65 65 20 2a | 2f 0a 6c 6f 63 61 6c 20 |h tree *|/.local |
|00002510| 20 20 69 6e 74 20 20 20 | 20 20 64 73 74 5f 74 72 |  int   |  dst_tr|
|00002520| 65 65 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |ee;     |        |
|00002530| 20 20 2f 2a 20 64 69 73 | 74 61 6e 63 65 20 74 72 |  /* dis|tance tr|
|00002540| 65 65 20 2a 2f 0a 58 0a | 58 0a 58 2f 2a 2a 2a 2a |ee */.X.|X.X/****|
|00002550| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002560| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002570| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002580| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002590| 2a 2a 2a 0a 58 20 2a 0a | 58 20 2a 20 4c 6f 63 61 |***.X *.|X * Loca|
|000025a0| 6c 20 28 73 74 61 74 69 | 63 29 20 72 6f 75 74 69 |l (stati|c) routi|
|000025b0| 6e 65 73 20 69 6e 20 74 | 68 69 73 20 66 69 6c 65 |nes in t|his file|
|000025c0| 2e 0a 58 20 2a 2f 0a 58 | 0a 6c 6f 63 61 6c 20 49 |..X */.X|.local I|
|000025d0| 6d 70 45 72 72 20 63 74 | 5f 61 6c 6c 6f 63 0a 58 |mpErr ct|_alloc.X|
|000025e0| 20 20 20 20 20 20 20 20 | 4f 46 20 28 28 69 6e 74 |        |OF ((int|
|000025f0| 20 73 69 7a 65 2c 20 69 | 6e 74 20 2a 68 61 6e 64 | size, i|nt *hand|
|00002600| 6c 65 29 29 3b 0a 58 0a | 6c 6f 63 61 6c 20 49 6d |le));.X.|local Im|
|00002610| 70 45 72 72 20 63 74 5f | 66 72 65 65 0a 58 20 20 |pErr ct_|free.X  |
|00002620| 20 20 20 20 20 20 4f 46 | 20 28 28 69 6e 74 20 68 |      OF| ((int h|
|00002630| 61 6e 64 6c 65 29 29 3b | 0a 58 0a 6c 6f 63 61 6c |andle));|.X.local|
|00002640| 20 49 6d 70 45 72 72 20 | 63 74 5f 6c 6f 61 64 66 | ImpErr |ct_loadf|
|00002650| 0a 58 20 20 20 20 20 20 | 20 20 4f 46 20 28 28 69 |.X      |  OF ((i|
|00002660| 6e 74 20 68 61 6e 64 6c | 65 2c 20 6c 6f 6e 67 20 |nt handl|e, long |
|00002670| 2a 66 72 65 71 29 29 3b | 0a 58 0a 6c 6f 63 61 6c |*freq));|.X.local|
|00002680| 20 49 6d 70 45 72 72 20 | 63 74 5f 7a 69 70 72 65 | ImpErr |ct_zipre|
|00002690| 70 0a 58 20 20 20 20 20 | 20 20 20 4f 46 20 28 28 |p.X     |   OF ((|
|000026a0| 69 6e 74 20 68 61 6e 64 | 6c 65 2c 20 55 5f 43 48 |int hand|le, U_CH|
|000026b0| 41 52 20 2a 2a 72 65 73 | 75 6c 74 29 29 3b 0a 58 |AR **res|ult));.X|
|000026c0| 0a 6c 6f 63 61 6c 20 49 | 6d 70 45 72 72 20 63 74 |.local I|mpErr ct|
|000026d0| 5f 67 65 6e 63 6f 64 65 | 73 0a 58 20 20 20 20 20 |_gencode|s.X     |
|000026e0| 20 20 20 4f 46 20 28 28 | 69 6e 74 20 68 61 6e 64 |   OF ((|int hand|
|000026f0| 6c 65 2c 20 69 6e 74 20 | 6d 69 6e 62 69 74 73 2c |le, int |minbits,|
|00002700| 20 69 6e 74 20 6d 61 78 | 62 69 74 73 2c 20 6c 6f | int max|bits, lo|
|00002710| 6e 67 20 2a 73 61 76 65 | 64 29 29 3b 0a 58 0a 6c |ng *save|d));.X.l|
|00002720| 6f 63 61 6c 20 49 6d 70 | 45 72 72 20 63 74 5f 73 |ocal Imp|Err ct_s|
|00002730| 70 6c 69 74 0a 58 20 20 | 20 20 20 20 20 20 4f 46 |plit.X  |      OF|
|00002740| 20 28 28 54 52 44 41 54 | 41 20 2a 70 61 72 74 2c | ((TRDAT|A *part,|
|00002750| 20 69 6e 74 20 73 69 7a | 65 2c 20 6c 6f 6e 67 20 | int siz|e, long |
|00002760| 66 72 65 71 2c 0a 58 20 | 20 20 20 20 20 20 20 20 |freq,.X |        |
|00002770| 20 20 20 20 69 6e 74 20 | 70 72 65 66 69 78 2c 20 |    int |prefix, |
|00002780| 69 6e 74 20 70 72 65 66 | 6c 65 6e 2c 20 69 6e 74 |int pref|len, int|
|00002790| 20 6d 69 6e 62 69 74 73 | 2c 20 69 6e 74 20 6d 61 | minbits|, int ma|
|000027a0| 78 62 69 74 73 29 29 3b | 0a 58 0a 6c 6f 63 61 6c |xbits));|.X.local|
|000027b0| 20 69 6e 74 20 63 74 5f | 66 73 6f 72 74 0a 58 20 | int ct_|fsort.X |
|000027c0| 20 20 20 20 20 20 20 4f | 46 20 28 28 54 52 44 41 |       O|F ((TRDA|
|000027d0| 54 41 20 2a 74 72 31 2c | 20 54 52 44 41 54 41 20 |TA *tr1,| TRDATA |
|000027e0| 2a 74 72 32 29 29 3b 0a | 58 0a 6c 6f 63 61 6c 20 |*tr2));.|X.local |
|000027f0| 69 6e 74 20 63 74 5f 72 | 73 6f 72 74 0a 58 20 20 |int ct_r|sort.X  |
|00002800| 20 20 20 20 20 20 4f 46 | 20 28 28 52 45 53 4f 52 |      OF| ((RESOR|
|00002810| 54 20 2a 63 72 31 2c 20 | 52 45 53 4f 52 54 20 2a |T *cr1, |RESORT *|
|00002820| 63 72 32 29 29 3b 0a 58 | 0a 58 0a 58 2f 2a 2a 2a |cr2));.X|.X.X/***|
|00002830| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002840| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002850| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002860| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002870| 2a 2a 2a 2a 0a 58 20 2a | 0a 58 20 2a 20 41 6c 6c |****.X *|.X * All|
|00002880| 6f 63 61 74 65 20 61 20 | 63 6f 64 65 20 74 72 65 |ocate a |code tre|
|00002890| 65 2e 0a 58 20 2a 2f 0a | 58 0a 6c 6f 63 61 6c 0a |e..X */.|X.local.|
|000028a0| 49 6d 70 45 72 72 0a 63 | 74 5f 61 6c 6c 6f 63 20 |ImpErr.c|t_alloc |
|000028b0| 28 73 69 7a 65 2c 20 68 | 61 6e 64 6c 65 29 0a 58 |(size, h|andle).X|
|000028c0| 20 20 20 20 69 6e 74 20 | 73 69 7a 65 3b 0a 58 20 |    int |size;.X |
|000028d0| 20 20 20 69 6e 74 20 2a | 68 61 6e 64 6c 65 3b 0a |   int *|handle;.|
|000028e0| 58 7b 20 20 20 72 65 67 | 69 73 74 65 72 20 54 52 |X{   reg|ister TR|
|000028f0| 44 41 54 41 20 2a 63 74 | 3b 0a 58 20 20 20 20 69 |DATA *ct|;.X    i|
|00002900| 6e 74 20 6e 3b 0a 58 0a | 58 23 69 66 64 65 66 20 |nt n;.X.|X#ifdef |
|00002910| 56 41 4c 49 44 41 54 45 | 0a 58 20 20 20 20 2f 2a |VALIDATE|.X    /*|
|00002920| 20 56 61 6c 69 64 61 74 | 65 20 74 68 65 20 61 72 | Validat|e the ar|
|00002930| 67 75 6d 65 6e 74 73 2e | 20 2a 2f 0a 58 20 20 20 |guments.| */.X   |
|00002940| 20 69 66 20 28 73 69 7a | 65 20 3c 20 32 20 7c 7c | if (siz|e < 2 |||
|00002950| 20 73 69 7a 65 20 3e 20 | 32 35 36 29 20 67 6f 74 | size > |256) got|
|00002960| 6f 20 62 61 64 61 72 67 | 3b 0a 58 20 20 20 20 69 |o badarg|;.X    i|
|00002970| 66 20 28 68 61 6e 64 6c | 65 20 3d 3d 20 4e 55 4c |f (handl|e == NUL|
|00002980| 4c 29 20 20 20 20 20 20 | 20 20 20 67 6f 74 6f 20 |L)      |   goto |
|00002990| 62 61 64 61 72 67 3b 0a | 58 23 65 6e 64 69 66 20 |badarg;.|X#endif |
|000029a0| 2f 2a 20 56 41 4c 49 44 | 41 54 45 20 2a 2f 0a 58 |/* VALID|ATE */.X|
|000029b0| 0a 58 20 20 20 20 2f 2a | 20 41 6c 6c 6f 63 61 74 |.X    /*| Allocat|
|000029c0| 65 20 61 6e 20 61 76 61 | 69 6c 61 62 6c 65 20 63 |e an ava|ilable c|
|000029d0| 6f 64 65 20 74 72 65 65 | 20 68 61 6e 64 6c 65 2e |ode tree| handle.|
|000029e0| 20 2a 2f 0a 58 20 20 20 | 20 66 6f 72 20 28 6e 20 | */.X   | for (n |
|000029f0| 3d 20 30 3b 0a 58 20 20 | 20 20 20 20 20 20 20 6e |= 0;.X  |       n|
|00002a00| 20 3c 20 4d 41 58 54 52 | 45 45 53 20 26 26 20 63 | < MAXTR|EES && c|
|00002a10| 74 5f 74 61 62 6c 65 5b | 6e 5d 2e 63 74 5f 61 72 |t_table[|n].ct_ar|
|00002a20| 72 61 79 20 21 3d 20 4e | 55 4c 4c 3b 0a 58 20 20 |ray != N|ULL;.X  |
|00002a30| 20 20 20 20 20 20 20 6e | 2b 2b 29 20 3b 0a 58 20 |       n|++) ;.X |
|00002a40| 20 20 20 69 66 20 28 6e | 20 3e 3d 20 4d 41 58 54 |   if (n| >= MAXT|
|00002a50| 52 45 45 53 29 20 72 65 | 74 75 72 6e 20 49 4d 5f |REES) re|turn IM_|
|00002a60| 4e 4f 43 54 42 4c 53 3b | 0a 58 20 20 20 20 2a 68 |NOCTBLS;|.X    *h|
|00002a70| 61 6e 64 6c 65 20 3d 20 | 6e 3b 0a 58 20 20 20 20 |andle = |n;.X    |
|00002a80| 63 74 5f 74 61 62 6c 65 | 5b 6e 5d 2e 63 74 5f 73 |ct_table|[n].ct_s|
|00002a90| 69 7a 65 20 20 3d 20 73 | 69 7a 65 3b 0a 58 0a 58 |ize  = s|ize;.X.X|
|00002aa0| 20 20 20 20 2f 2a 20 41 | 6c 6c 6f 63 61 74 65 20 |    /* A|llocate |
|00002ab0| 73 70 61 63 65 20 66 6f | 72 20 74 68 65 20 63 6f |space fo|r the co|
|00002ac0| 64 65 20 74 72 65 65 2e | 20 2a 2f 0a 58 20 20 20 |de tree.| */.X   |
|00002ad0| 20 63 74 20 3d 20 28 54 | 52 44 41 54 41 20 2a 29 | ct = (T|RDATA *)|
|00002ae0| 20 6d 61 6c 6c 6f 63 20 | 28 28 75 6e 73 69 67 6e | malloc |((unsign|
|00002af0| 65 64 29 20 28 73 69 7a | 65 20 2a 20 73 69 7a 65 |ed) (siz|e * size|
|00002b00| 6f 66 20 28 54 52 44 41 | 54 41 29 29 29 3b 0a 58 |of (TRDA|TA)));.X|
|00002b10| 20 20 20 20 69 66 20 28 | 63 74 20 3d 3d 20 4e 55 |    if (|ct == NU|
|00002b20| 4c 4c 29 20 72 65 74 75 | 72 6e 20 49 4d 5f 4e 4f |LL) retu|rn IM_NO|
|00002b30| 4d 45 4d 3b 0a 58 20 20 | 20 20 63 74 5f 74 61 62 |MEM;.X  |  ct_tab|
|00002b40| 6c 65 5b 6e 5d 2e 63 74 | 5f 61 72 72 61 79 20 3d |le[n].ct|_array =|
|00002b50| 20 63 74 3b 0a 58 0a 58 | 20 20 20 20 2f 2a 20 49 | ct;.X.X|    /* I|
|00002b60| 6e 69 74 69 61 6c 69 7a | 65 20 74 68 65 20 63 6f |nitializ|e the co|
|00002b70| 64 65 20 74 72 65 65 2e | 20 2a 2f 0a 58 20 20 20 |de tree.| */.X   |
|00002b80| 20 66 6f 72 20 28 6e 20 | 3d 20 30 3b 20 6e 20 3c | for (n |= 0; n <|
|00002b90| 20 73 69 7a 65 3b 20 6e | 2b 2b 2c 20 63 74 2b 2b | size; n|++, ct++|
|00002ba0| 29 0a 58 20 20 20 20 7b | 20 20 20 63 74 2d 3e 63 |).X    {|   ct->c|
|00002bb0| 74 5f 66 72 65 71 20 3d | 20 30 3b 0a 58 20 20 20 |t_freq =| 0;.X   |
|00002bc0| 20 20 20 20 20 63 74 2d | 3e 63 74 5f 63 6f 64 65 |     ct-|>ct_code|
|00002bd0| 20 3d 20 30 3b 0a 58 20 | 20 20 20 20 20 20 20 63 | = 0;.X |       c|
|00002be0| 74 2d 3e 63 74 5f 76 61 | 6c 20 20 3d 20 28 55 5f |t->ct_va|l  = (U_|
|00002bf0| 43 48 41 52 29 6e 3b 0a | 58 20 20 20 20 20 20 20 |CHAR)n;.|X       |
|00002c00| 20 63 74 2d 3e 63 74 5f | 6c 65 6e 20 20 3d 20 30 | ct->ct_|len  = 0|
|00002c10| 3b 0a 58 20 20 20 20 7d | 0a 58 0a 58 20 20 20 20 |;.X    }|.X.X    |
|00002c20| 2f 2a 20 54 68 61 74 27 | 73 20 61 6c 6c 2e 20 2a |/* That'|s all. *|
|00002c30| 2f 0a 58 20 20 20 20 72 | 65 74 75 72 6e 20 49 4d |/.X    r|eturn IM|
|00002c40| 5f 4f 4b 3b 0a 58 0a 58 | 23 69 66 64 65 66 20 56 |_OK;.X.X|#ifdef V|
|00002c50| 41 4c 49 44 41 54 45 0a | 62 61 64 61 72 67 3a 0a |ALIDATE.|badarg:.|
|00002c60| 58 20 20 20 20 66 70 72 | 69 6e 74 66 20 28 73 74 |X    fpr|intf (st|
|00002c70| 64 65 72 72 2c 20 22 5c | 6e 45 72 72 6f 72 20 69 |derr, "\|nError i|
|00002c80| 6e 20 63 74 5f 61 6c 6c | 6f 63 3a 20 62 61 64 20 |n ct_all|oc: bad |
|00002c90| 61 72 67 75 6d 65 6e 74 | 28 73 29 22 29 3b 0a 58 |argument|(s)");.X|
|00002ca0| 20 20 20 20 72 65 74 75 | 72 6e 20 49 4d 5f 42 41 |    retu|rn IM_BA|
|00002cb0| 44 41 52 47 3b 0a 58 23 | 65 6e 64 69 66 20 2f 2a |DARG;.X#|endif /*|
|00002cc0| 20 56 41 4c 49 44 41 54 | 45 20 2a 2f 0a 58 7d 0a | VALIDAT|E */.X}.|
|00002cd0| 58 0a 58 0a 58 2f 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |X.X.X/**|********|
|00002ce0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002cf0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002d00| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002d10| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 0a 58 20 |********|*****.X |
|00002d20| 2a 0a 58 20 2a 20 46 72 | 65 65 20 61 20 63 6f 64 |*.X * Fr|ee a cod|
|00002d30| 65 20 74 72 65 65 2e 0a | 58 20 2a 2f 0a 58 0a 6c |e tree..|X */.X.l|
|00002d40| 6f 63 61 6c 0a 49 6d 70 | 45 72 72 0a 63 74 5f 66 |ocal.Imp|Err.ct_f|
|00002d50| 72 65 65 20 28 68 61 6e | 64 6c 65 29 0a 58 20 20 |ree (han|dle).X  |
|00002d60| 20 20 69 6e 74 20 68 61 | 6e 64 6c 65 3b 0a 58 7b |  int ha|ndle;.X{|
|00002d70| 0a 58 23 69 66 64 65 66 | 20 56 41 4c 49 44 41 54 |.X#ifdef| VALIDAT|
|00002d80| 45 0a 58 20 20 20 20 2f | 2a 20 56 61 6c 69 64 61 |E.X    /|* Valida|
|00002d90| 74 65 20 74 68 65 20 61 | 72 67 75 6d 65 6e 74 2e |te the a|rgument.|
|00002da0| 20 2a 2f 0a 58 20 20 20 | 20 69 66 20 28 21 56 41 | */.X   | if (!VA|
|00002db0| 4c 49 44 5f 48 41 4e 44 | 4c 45 20 28 68 61 6e 64 |LID_HAND|LE (hand|
|00002dc0| 6c 65 29 29 20 67 6f 74 | 6f 20 62 61 64 61 72 67 |le)) got|o badarg|
|00002dd0| 3b 0a 58 23 65 6e 64 69 | 66 20 2f 2a 20 56 41 4c |;.X#endi|f /* VAL|
|00002de0| 49 44 41 54 45 20 2a 2f | 0a 58 0a 58 20 20 20 20 |IDATE */|.X.X    |
|00002df0| 2f 2a 20 46 72 65 65 20 | 74 68 65 20 63 6f 64 65 |/* Free |the code|
|00002e00| 20 74 72 65 65 2e 20 2a | 2f 0a 58 20 20 20 20 66 | tree. *|/.X    f|
|00002e10| 72 65 65 20 28 28 63 68 | 61 72 20 2a 29 20 63 74 |ree ((ch|ar *) ct|
|00002e20| 5f 74 61 62 6c 65 5b 68 | 61 6e 64 6c 65 5d 2e 63 |_table[h|andle].c|
|00002e30| 74 5f 61 72 72 61 79 29 | 3b 0a 58 20 20 20 20 63 |t_array)|;.X    c|
|00002e40| 74 5f 74 61 62 6c 65 5b | 68 61 6e 64 6c 65 5d 2e |t_table[|handle].|
|00002e50| 63 74 5f 61 72 72 61 79 | 20 3d 20 4e 55 4c 4c 3b |ct_array| = NULL;|
|00002e60| 0a 58 20 20 20 20 63 74 | 5f 74 61 62 6c 65 5b 68 |.X    ct|_table[h|
|00002e70| 61 6e 64 6c 65 5d 2e 63 | 74 5f 73 69 7a 65 20 20 |andle].c|t_size  |
|00002e80| 3d 20 30 3b 0a 58 0a 58 | 20 20 20 20 2f 2a 20 54 |= 0;.X.X|    /* T|
|00002e90| 68 61 74 27 73 20 61 6c | 6c 2e 20 2a 2f 0a 58 20 |hat's al|l. */.X |
|00002ea0| 20 20 20 72 65 74 75 72 | 6e 20 49 4d 5f 4f 4b 3b |   retur|n IM_OK;|
|00002eb0| 0a 58 0a 58 23 69 66 64 | 65 66 20 56 41 4c 49 44 |.X.X#ifd|ef VALID|
|00002ec0| 41 54 45 0a 62 61 64 61 | 72 67 3a 0a 58 20 20 20 |ATE.bada|rg:.X   |
|00002ed0| 20 66 70 72 69 6e 74 66 | 20 28 73 74 64 65 72 72 | fprintf| (stderr|
|00002ee0| 2c 20 22 5c 6e 45 72 72 | 6f 72 20 69 6e 20 63 74 |, "\nErr|or in ct|
|00002ef0| 5f 66 72 65 65 3a 20 62 | 61 64 20 61 72 67 75 6d |_free: b|ad argum|
|00002f00| 65 6e 74 28 73 29 22 29 | 3b 0a 58 20 20 20 20 72 |ent(s)")|;.X    r|
|00002f10| 65 74 75 72 6e 20 49 4d | 5f 42 41 44 41 52 47 3b |eturn IM|_BADARG;|
|00002f20| 0a 58 23 65 6e 64 69 66 | 20 2f 2a 20 56 41 4c 49 |.X#endif| /* VALI|
|00002f30| 44 41 54 45 20 2a 2f 0a | 58 7d 0a 58 0a 58 0a 58 |DATE */.|X}.X.X.X|
|00002f40| 2f 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |/*******|********|
|00002f50| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002f60| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002f70| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00002f80| 2a 2a 2a 2a 2a 2a 2a 2a | 0a 58 20 2a 0a 58 20 2a |********|.X *.X *|
|00002f90| 20 55 70 64 61 74 65 20 | 61 20 63 6f 64 65 20 74 | Update |a code t|
|00002fa0| 72 65 65 20 77 69 74 68 | 20 66 72 65 71 75 65 6e |ree with| frequen|
|00002fb0| 63 79 20 64 61 74 61 2e | 0a 58 20 2a 0a 58 20 2a |cy data.|.X *.X *|
|00002fc0| 20 49 6e 20 6f 72 64 65 | 72 20 74 6f 20 61 6c 6c | In orde|r to all|
|00002fd0| 6f 77 20 66 6f 72 20 74 | 68 65 20 6c 61 74 65 72 |ow for t|he later|
|00002fe0| 20 61 64 64 69 74 69 6f | 6e 20 6f 66 20 22 61 64 | additio|n of "ad|
|00002ff0| 61 70 74 69 76 65 22 20 | 63 6f 64 69 6e 67 2c 0a |aptive" |coding,.|
|00003000| 58 20 2a 20 74 68 65 20 | 6e 65 77 20 66 72 65 71 |X * the |new freq|
|00003010| 75 65 6e 63 69 65 73 20 | 61 72 65 20 61 64 64 65 |uencies |are adde|
|00003020| 64 20 74 6f 20 74 68 65 | 20 65 78 69 73 74 69 6e |d to the| existin|
|00003030| 67 20 64 61 74 61 2e 0a | 58 20 2a 2f 0a 58 0a 6c |g data..|X */.X.l|
|00003040| 6f 63 61 6c 0a 49 6d 70 | 45 72 72 0a 63 74 5f 6c |ocal.Imp|Err.ct_l|
|00003050| 6f 61 64 66 20 28 68 61 | 6e 64 6c 65 2c 20 66 72 |oadf (ha|ndle, fr|
|00003060| 65 71 29 0a 58 20 20 20 | 20 69 6e 74 20 20 20 68 |eq).X   | int   h|
|00003070| 61 6e 64 6c 65 3b 0a 58 | 20 20 20 20 6c 6f 6e 67 |andle;.X|    long|
|00003080| 20 2a 66 72 65 71 3b 0a | 58 7b 20 20 20 72 65 67 | *freq;.|X{   reg|
|00003090| 69 73 74 65 72 20 6c 6f | 6e 67 20 2a 66 3b 0a 58 |ister lo|ng *f;.X|
|000030a0| 20 20 20 20 72 65 67 69 | 73 74 65 72 20 54 52 44 |    regi|ster TRD|
|000030b0| 41 54 41 20 2a 63 74 3b | 0a 58 20 20 20 20 69 6e |ATA *ct;|.X    in|
|000030c0| 74 20 6e 3b 0a 58 0a 58 | 23 69 66 64 65 66 20 56 |t n;.X.X|#ifdef V|
|000030d0| 41 4c 49 44 41 54 45 0a | 58 20 20 20 20 2f 2a 20 |ALIDATE.|X    /* |
|000030e0| 56 61 6c 69 64 61 74 65 | 20 74 68 65 20 61 72 67 |Validate| the arg|
|000030f0| 75 6d 65 6e 74 73 2e 20 | 2a 2f 0a 58 20 20 20 20 |uments. |*/.X    |
|00003100| 69 66 20 28 21 56 41 4c | 49 44 5f 48 41 4e 44 4c |if (!VAL|ID_HANDL|
|00003110| 45 20 28 68 61 6e 64 6c | 65 29 29 20 67 6f 74 6f |E (handl|e)) goto|
|00003120| 20 62 61 64 61 72 67 3b | 0a 58 23 65 6e 64 69 66 | badarg;|.X#endif|
|00003130| 20 2f 2a 20 56 41 4c 49 | 44 41 54 45 20 2a 2f 0a | /* VALI|DATE */.|
|00003140| 58 0a 58 20 20 20 20 2f | 2a 20 41 64 64 20 69 6e |X.X    /|* Add in|
|00003150| 20 74 68 65 20 66 72 65 | 71 75 65 6e 63 69 65 73 | the fre|quencies|
|00003160| 2e 20 2a 2f 0a 58 20 20 | 20 20 66 6f 72 20 28 66 |. */.X  |  for (f|
|00003170| 20 3d 20 66 72 65 71 2c | 0a 58 20 20 20 20 20 20 | = freq,|.X      |
|00003180| 20 20 20 20 20 20 20 63 | 74 20 3d 20 63 74 5f 74 |       c|t = ct_t|
|00003190| 61 62 6c 65 5b 68 61 6e | 64 6c 65 5d 2e 63 74 5f |able[han|dle].ct_|
|000031a0| 61 72 72 61 79 2c 0a 58 | 20 20 20 20 20 20 20 20 |array,.X|        |
|000031b0| 20 20 20 20 20 6e 20 3d | 20 63 74 5f 74 61 62 6c |     n =| ct_tabl|
|000031c0| 65 5b 68 61 6e 64 6c 65 | 5d 2e 63 74 5f 73 69 7a |e[handle|].ct_siz|
|000031d0| 65 3b 0a 58 20 20 20 20 | 20 20 20 20 20 6e 20 3e |e;.X    |     n >|
|000031e0| 20 30 3b 0a 58 20 20 20 | 20 20 20 20 20 20 66 2b | 0;.X   |      f+|
|000031f0| 2b 2c 20 63 74 2b 2b 2c | 20 6e 2d 2d 29 0a 58 20 |+, ct++,| n--).X |
|00003200| 20 20 20 20 20 20 20 63 | 74 2d 3e 63 74 5f 66 72 |       c|t->ct_fr|
|00003210| 65 71 20 2b 3d 20 2a 66 | 3b 0a 58 0a 58 20 20 20 |eq += *f|;.X.X   |
|00003220| 20 2f 2a 20 54 68 61 74 | 27 73 20 61 6c 6c 2e 20 | /* That|'s all. |
|00003230| 2a 2f 0a 58 20 20 20 20 | 72 65 74 75 72 6e 20 49 |*/.X    |return I|
|00003240| 4d 5f 4f 4b 3b 0a 58 0a | 58 23 69 66 64 65 66 20 |M_OK;.X.|X#ifdef |
|00003250| 56 41 4c 49 44 41 54 45 | 0a 62 61 64 61 72 67 3a |VALIDATE|.badarg:|
|00003260| 0a 58 20 20 20 20 66 70 | 72 69 6e 74 66 20 28 73 |.X    fp|rintf (s|
|00003270| 74 64 65 72 72 2c 20 22 | 5c 6e 45 72 72 6f 72 20 |tderr, "|\nError |
|00003280| 69 6e 20 63 74 5f 6c 6f | 61 64 66 3a 20 62 61 64 |in ct_lo|adf: bad|
|00003290| 20 61 72 67 75 6d 65 6e | 74 28 73 29 22 29 3b 0a | argumen|t(s)");.|
|000032a0| 58 20 20 20 20 72 65 74 | 75 72 6e 20 49 4d 5f 42 |X    ret|urn IM_B|
|000032b0| 41 44 41 52 47 3b 0a 58 | 23 65 6e 64 69 66 20 2f |ADARG;.X|#endif /|
|000032c0| 2a 20 56 41 4c 49 44 41 | 54 45 20 2a 2f 0a 58 7d |* VALIDA|TE */.X}|
|000032d0| 0a 58 0a 58 0a 58 2f 2a | 2a 2a 2a 2a 2a 2a 2a 2a |.X.X.X/*|********|
|000032e0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|000032f0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003300| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003310| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 0a 58 |********|******.X|
|00003320| 20 2a 0a 58 20 2a 20 47 | 65 6e 65 72 61 74 65 20 | *.X * G|enerate |
|00003330| 74 68 65 20 5a 49 50 2d | 66 69 6c 65 20 72 65 70 |the ZIP-|file rep|
|00003340| 72 65 73 65 6e 74 61 74 | 69 6f 6e 20 66 6f 72 20 |resentat|ion for |
|00003350| 61 20 63 6f 64 65 20 74 | 72 65 65 2e 0a 58 20 2a |a code t|ree..X *|
|00003360| 0a 58 20 2a 20 54 68 65 | 20 72 65 74 75 72 6e 65 |.X * The| returne|
|00003370| 64 20 22 72 65 73 75 6c | 74 22 20 76 61 6c 75 65 |d "resul|t" value|
|00003380| 20 70 6f 69 6e 74 73 20 | 74 6f 20 73 74 61 74 69 | points |to stati|
|00003390| 63 20 64 61 74 61 20 77 | 68 69 63 68 20 77 69 6c |c data w|hich wil|
|000033a0| 6c 20 62 65 0a 58 20 2a | 20 6f 76 65 72 77 72 69 |l be.X *| overwri|
|000033b0| 74 74 65 6e 20 6f 6e 20 | 74 68 65 20 6e 65 78 74 |tten on |the next|
|000033c0| 20 63 61 6c 6c 20 74 6f | 20 22 63 74 5f 7a 69 70 | call to| "ct_zip|
|000033d0| 72 65 70 22 2e 0a 58 20 | 2a 0a 58 20 2a 20 54 68 |rep"..X |*.X * Th|
|000033e0| 65 20 6c 65 6e 67 74 68 | 20 6f 66 20 74 68 65 20 |e length| of the |
|000033f0| 72 65 73 75 6c 74 20 73 | 74 72 69 6e 67 20 69 73 |result s|tring is|
|00003400| 20 69 6d 70 6c 69 63 69 | 74 20 69 6e 20 74 68 65 | implici|t in the|
|00003410| 20 66 69 72 73 74 20 62 | 79 74 65 20 6f 66 0a 58 | first b|yte of.X|
|00003420| 20 2a 20 74 68 65 20 76 | 61 6c 75 65 2c 20 61 73 | * the v|alue, as|
|00003430| 20 73 70 65 63 69 66 69 | 65 64 20 69 6e 20 74 68 | specifi|ed in th|
|00003440| 65 20 50 4b 5a 49 50 20 | 61 70 70 6c 69 63 61 74 |e PKZIP |applicat|
|00003450| 69 6f 6e 73 20 6e 6f 74 | 65 2e 0a 58 20 2a 2f 0a |ions not|e..X */.|
|00003460| 58 0a 58 23 69 66 64 65 | 66 20 49 4d 50 44 45 42 |X.X#ifde|f IMPDEB|
|00003470| 55 47 0a 63 68 61 72 20 | 2a 74 72 65 65 6e 61 6d |UG.char |*treenam|
|00003480| 65 3b 0a 58 23 65 6e 64 | 69 66 20 2f 2a 20 49 4d |e;.X#end|if /* IM|
|00003490| 50 44 45 42 55 47 20 2a | 2f 0a 58 0a 6c 6f 63 61 |PDEBUG *|/.X.loca|
|000034a0| 6c 0a 49 6d 70 45 72 72 | 0a 63 74 5f 7a 69 70 72 |l.ImpErr|.ct_zipr|
|000034b0| 65 70 20 28 68 61 6e 64 | 6c 65 2c 20 72 65 73 75 |ep (hand|le, resu|
|000034c0| 6c 74 29 0a 58 20 20 20 | 20 69 6e 74 20 20 20 20 |lt).X   | int    |
|000034d0| 20 20 68 61 6e 64 6c 65 | 3b 0a 58 20 20 20 20 55 |  handle|;.X    U|
|000034e0| 5f 43 48 41 52 20 2a 2a | 72 65 73 75 6c 74 3b 0a |_CHAR **|result;.|
|000034f0| 58 7b 20 20 20 73 74 61 | 74 69 63 20 55 5f 43 48 |X{   sta|tic U_CH|
|00003500| 41 52 20 62 75 66 66 65 | 72 5b 32 35 37 5d 3b 20 |AR buffe|r[257]; |
|00003510| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 72 65 73 75 |        | /* resu|
|00003520| 6c 74 20 69 6e 66 6f 20 | 2a 2f 0a 58 20 20 20 20 |lt info |*/.X    |
|00003530| 72 65 67 69 73 74 65 72 | 20 55 5f 43 48 41 52 20 |register| U_CHAR |
|00003540| 2a 63 3b 0a 58 20 20 20 | 20 72 65 67 69 73 74 65 |*c;.X   | registe|
|00003550| 72 20 54 52 44 41 54 41 | 20 2a 63 74 3b 0a 58 20 |r TRDATA| *ct;.X |
|00003560| 20 20 20 69 6e 74 20 73 | 2c 20 6e 2c 20 6c 3b 0a |   int s|, n, l;.|
|00003570| 58 0a 58 23 69 66 64 65 | 66 20 56 41 4c 49 44 41 |X.X#ifde|f VALIDA|
|00003580| 54 45 0a 58 20 20 20 20 | 2f 2a 20 56 61 6c 69 64 |TE.X    |/* Valid|
|00003590| 61 74 65 20 74 68 65 20 | 61 72 67 75 6d 65 6e 74 |ate the |argument|
|000035a0| 73 2e 20 2a 2f 0a 58 20 | 20 20 20 69 66 20 28 21 |s. */.X |   if (!|
|000035b0| 56 41 4c 49 44 5f 48 41 | 4e 44 4c 45 20 28 68 61 |VALID_HA|NDLE (ha|
|000035c0| 6e 64 6c 65 29 29 20 67 | 6f 74 6f 20 62 61 64 61 |ndle)) g|oto bada|
|000035d0| 72 67 3b 0a 58 20 20 20 | 20 69 66 20 28 72 65 73 |rg;.X   | if (res|
|000035e0| 75 6c 74 20 3d 3d 20 4e | 55 4c 4c 29 20 20 20 20 |ult == N|ULL)    |
|000035f0| 20 20 20 20 20 67 6f 74 | 6f 20 62 61 64 61 72 67 |     got|o badarg|
|00003600| 3b 0a 58 23 65 6e 64 69 | 66 20 2f 2a 20 56 41 4c |;.X#endi|f /* VAL|
|00003610| 49 44 41 54 45 20 2a 2f | 0a 58 0a 58 23 69 66 64 |IDATE */|.X.X#ifd|
|00003620| 65 66 20 20 49 4d 50 44 | 45 42 55 47 0a 58 20 20 |ef  IMPD|EBUG.X  |
|00003630| 20 20 69 66 20 28 74 72 | 65 65 6e 61 6d 65 20 21 |  if (tr|eename !|
|00003640| 3d 20 4e 55 4c 4c 20 26 | 26 20 74 72 65 65 6e 61 |= NULL &|& treena|
|00003650| 6d 65 5b 30 5d 20 21 3d | 20 30 29 0a 58 20 20 20 |me[0] !=| 0).X   |
|00003660| 20 7b 20 20 20 2f 2a 20 | 50 72 69 6e 74 20 74 68 | {   /* |Print th|
|00003670| 65 20 63 6f 64 65 20 74 | 72 65 65 20 69 6e 66 6f |e code t|ree info|
|00003680| 2e 20 2a 2f 0a 58 20 20 | 20 20 20 20 20 20 66 70 |. */.X  |      fp|
|00003690| 72 69 6e 74 66 20 28 73 | 74 64 65 72 72 2c 20 22 |rintf (s|tderr, "|
|000036a0| 5c 6e 25 73 20 74 72 65 | 65 3a 5c 6e 20 20 76 61 |\n%s tre|e:\n  va|
|000036b0| 6c 75 65 20 20 20 20 20 | 20 6c 65 6e 20 20 20 73 |lue     | len   s|
|000036c0| 74 72 69 6e 67 5c 6e 22 | 2c 0a 58 20 20 20 20 20 |tring\n"|,.X     |
|000036d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 74 72 65 65 |        |    tree|
|000036e0| 6e 61 6d 65 29 3b 0a 58 | 20 20 20 20 20 20 20 20 |name);.X|        |
|000036f0| 66 6f 72 20 28 63 74 20 | 3d 20 63 74 5f 74 61 62 |for (ct |= ct_tab|
|00003700| 6c 65 5b 68 61 6e 64 6c | 65 5d 2e 63 74 5f 61 72 |le[handl|e].ct_ar|
|00003710| 72 61 79 2c 0a 58 20 20 | 20 20 20 20 20 20 20 20 |ray,.X  |        |
|00003720| 20 20 20 20 20 20 20 20 | 73 20 3d 20 63 74 5f 74 |        |s = ct_t|
|00003730| 61 62 6c 65 5b 68 61 6e | 64 6c 65 5d 2e 63 74 5f |able[han|dle].ct_|
|00003740| 73 69 7a 65 2c 0a 58 20 | 20 20 20 20 20 20 20 20 |size,.X |        |
|00003750| 20 20 20 20 20 20 20 20 | 20 6e 20 3d 20 30 3b 0a |        | n = 0;.|
|00003760| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 73 20 |X       |      s |
|00003770| 3e 20 30 3b 0a 58 20 20 | 20 20 20 20 20 20 20 20 |> 0;.X  |        |
|00003780| 20 20 20 63 74 2b 2b 2c | 20 6e 2b 2b 2c 20 73 2d |   ct++,| n++, s-|
|00003790| 2d 29 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |-).X    |        |
|000037a0| 66 70 72 69 6e 74 66 20 | 28 73 74 64 65 72 72 2c |fprintf |(stderr,|
|000037b0| 20 22 20 20 25 33 64 20 | 28 25 30 32 78 29 20 20 | "  %3d |(%02x)  |
|000037c0| 20 20 25 32 64 20 20 20 | 20 25 30 34 78 20 28 72 |  %2d   | %04x (r|
|000037d0| 65 76 20 25 30 34 78 29 | 5c 6e 22 2c 0a 58 20 20 |ev %04x)|\n",.X  |
|000037e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000037f0| 20 20 20 6e 2c 20 6e 2c | 20 63 74 2d 3e 63 74 5f |   n, n,| ct->ct_|
|00003800| 6c 65 6e 2c 0a 58 20 20 | 20 20 20 20 20 20 20 20 |len,.X  |        |
|00003810| 20 20 20 20 20 20 20 20 | 20 20 20 62 69 5f 72 65 |        |   bi_re|
|00003820| 76 65 72 73 65 28 63 74 | 2d 3e 63 74 5f 63 6f 64 |verse(ct|->ct_cod|
|00003830| 65 20 3c 3c 20 28 31 36 | 20 2d 20 63 74 2d 3e 63 |e << (16| - ct->c|
|00003840| 74 5f 6c 65 6e 29 2c 0a | 58 20 20 20 20 20 20 20 |t_len),.|X       |
|00003850| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003860| 20 20 20 20 20 20 20 20 | 20 63 74 2d 3e 63 74 5f |        | ct->ct_|
|00003870| 6c 65 6e 29 20 3c 3c 20 | 28 31 36 20 2d 20 63 74 |len) << |(16 - ct|
|00003880| 2d 3e 63 74 5f 6c 65 6e | 29 2c 0a 58 20 20 20 20 |->ct_len|),.X    |
|00003890| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000038a0| 20 63 74 2d 3e 63 74 5f | 63 6f 64 65 29 3b 0a 58 | ct->ct_|code);.X|
|000038b0| 20 20 20 20 7d 0a 58 23 | 65 6e 64 69 66 20 20 2f |    }.X#|endif  /|
|000038c0| 2a 20 49 4d 50 44 45 42 | 55 47 20 2a 2f 0a 58 0a |* IMPDEB|UG */.X.|
|000038d0| 58 20 20 20 20 2f 2a 20 | 47 65 6e 65 72 61 74 65 |X    /* |Generate|
|000038e0| 20 74 68 65 20 72 65 74 | 75 72 6e 65 64 20 76 61 | the ret|urned va|
|000038f0| 6c 75 65 2e 20 2a 2f 0a | 58 20 20 20 20 66 6f 72 |lue. */.|X    for|
|00003900| 20 28 63 20 3d 20 62 75 | 66 66 65 72 2b 31 2c 0a | (c = bu|ffer+1,.|
|00003910| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 20 63 74 |X       |      ct|
|00003920| 20 3d 20 63 74 5f 74 61 | 62 6c 65 5b 68 61 6e 64 | = ct_ta|ble[hand|
|00003930| 6c 65 5d 2e 63 74 5f 61 | 72 72 61 79 2c 0a 58 20 |le].ct_a|rray,.X |
|00003940| 20 20 20 20 20 20 20 20 | 20 20 20 20 73 20 3d 20 |        |    s = |
|00003950| 63 74 5f 74 61 62 6c 65 | 5b 68 61 6e 64 6c 65 5d |ct_table|[handle]|
|00003960| 2e 63 74 5f 73 69 7a 65 | 2c 0a 58 20 20 20 20 20 |.ct_size|,.X     |
|00003970| 20 20 20 20 20 20 20 20 | 6e 20 3d 20 30 2c 0a 58 |        |n = 0,.X|
|00003980| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 6c 20 3d |        |     l =|
|00003990| 20 63 74 2d 3e 63 74 5f | 6c 65 6e 3b 0a 58 20 20 | ct->ct_|len;.X  |
|000039a0| 20 20 20 20 20 20 20 73 | 20 3e 20 30 3b 0a 58 20 |       s| > 0;.X |
|000039b0| 20 20 20 20 20 20 20 20 | 63 74 2b 2b 2c 20 73 2d |        |ct++, s-|
|000039c0| 2d 29 0a 58 20 20 20 20 | 7b 20 20 20 69 66 20 28 |-).X    |{   if (|
|000039d0| 6c 20 3c 20 31 20 7c 7c | 20 6c 20 3e 20 31 36 29 |l < 1 ||| l > 16)|
|000039e0| 0a 58 20 20 20 20 20 20 | 20 20 7b 20 20 20 66 70 |.X      |  {   fp|
|000039f0| 72 69 6e 74 66 20 28 73 | 74 64 65 72 72 2c 20 22 |rintf (s|tderr, "|
|00003a00| 5c 6e 45 72 72 6f 72 20 | 69 6e 20 63 74 5f 7a 69 |\nError |in ct_zi|
|00003a10| 70 72 65 70 3a 20 62 61 | 64 20 63 6f 64 65 20 6c |prep: ba|d code l|
|00003a20| 65 6e 67 74 68 22 29 3b | 0a 58 20 20 20 20 20 20 |ength");|.X      |
|00003a30| 20 20 20 20 20 20 72 65 | 74 75 72 6e 20 49 4d 5f |      re|turn IM_|
|00003a40| 4c 4f 47 49 43 45 52 52 | 3b 0a 58 20 20 20 20 20 |LOGICERR|;.X     |
|00003a50| 20 20 20 7d 0a 58 20 20 | 20 20 20 20 20 20 69 66 |   }.X  |      if|
|00003a60| 20 28 6e 20 3e 3d 20 31 | 36 20 7c 7c 20 28 69 6e | (n >= 1|6 || (in|
|00003a70| 74 29 63 74 2d 3e 63 74 | 5f 6c 65 6e 20 21 3d 20 |t)ct->ct|_len != |
|00003a80| 6c 29 0a 58 20 20 20 20 | 20 20 20 20 7b 20 20 20 |l).X    |    {   |
|00003a90| 2a 63 2b 2b 20 3d 20 28 | 55 5f 43 48 41 52 29 28 |*c++ = (|U_CHAR)(|
|00003aa0| 28 28 28 6e 2d 31 29 20 | 3c 3c 20 34 29 20 26 20 |(((n-1) |<< 4) & |
|00003ab0| 30 78 66 30 29 20 7c 20 | 28 28 6c 2d 31 29 20 26 |0xf0) | |((l-1) &|
|00003ac0| 20 30 78 30 66 29 29 3b | 0a 58 20 20 20 20 20 20 | 0x0f));|.X      |
|00003ad0| 20 20 20 20 20 20 6e 20 | 3d 20 31 3b 20 6c 20 3d |      n |= 1; l =|
|00003ae0| 20 63 74 2d 3e 63 74 5f | 6c 65 6e 3b 0a 58 20 20 | ct->ct_|len;.X  |
|00003af0| 20 20 20 20 20 20 7d 0a | 58 20 20 20 20 20 20 20 |      }.|X       |
|00003b00| 20 65 6c 73 65 20 6e 2b | 2b 3b 0a 58 20 20 20 20 | else n+|+;.X    |
|00003b10| 7d 0a 58 20 20 20 20 69 | 66 20 28 6e 20 3e 20 30 |}.X    i|f (n > 0|
|00003b20| 29 0a 58 20 20 20 20 20 | 20 20 20 2a 63 2b 2b 20 |).X     |   *c++ |
|00003b30| 3d 20 28 55 5f 43 48 41 | 52 29 28 28 28 28 6e 2d |= (U_CHA|R)((((n-|
|00003b40| 31 29 20 3c 3c 20 34 29 | 20 26 20 30 78 66 30 29 |1) << 4)| & 0xf0)|
|00003b50| 20 7c 20 28 28 6c 2d 31 | 29 20 26 20 30 78 30 66 | | ((l-1|) & 0x0f|
|00003b60| 29 29 3b 0a 58 20 20 20 | 20 62 75 66 66 65 72 5b |));.X   | buffer[|
|00003b70| 30 5d 20 3d 20 28 55 5f | 43 48 41 52 29 28 28 63 |0] = (U_|CHAR)((c|
|00003b80| 20 2d 20 62 75 66 66 65 | 72 29 20 2d 20 32 29 3b | - buffe|r) - 2);|
|00003b90| 0a 58 0a 58 20 20 20 20 | 2f 2a 20 54 68 61 74 27 |.X.X    |/* That'|
|00003ba0| 73 20 61 6c 6c 2e 20 2a | 2f 0a 58 20 20 20 20 2a |s all. *|/.X    *|
|00003bb0| 72 65 73 75 6c 74 20 3d | 20 62 75 66 66 65 72 3b |result =| buffer;|
|00003bc0| 0a 58 20 20 20 20 72 65 | 74 75 72 6e 20 49 4d 5f |.X    re|turn IM_|
|00003bd0| 4f 4b 3b 0a 58 0a 58 23 | 69 66 64 65 66 20 56 41 |OK;.X.X#|ifdef VA|
|00003be0| 4c 49 44 41 54 45 0a 62 | 61 64 61 72 67 3a 0a 58 |LIDATE.b|adarg:.X|
|00003bf0| 20 20 20 20 66 70 72 69 | 6e 74 66 20 28 73 74 64 |    fpri|ntf (std|
|00003c00| 65 72 72 2c 20 22 5c 6e | 45 72 72 6f 72 20 69 6e |err, "\n|Error in|
|00003c10| 20 63 74 5f 7a 69 70 72 | 65 70 3a 20 62 61 64 20 | ct_zipr|ep: bad |
|00003c20| 61 72 67 75 6d 65 6e 74 | 28 73 29 22 29 3b 0a 58 |argument|(s)");.X|
|00003c30| 20 20 20 20 72 65 74 75 | 72 6e 20 49 4d 5f 42 41 |    retu|rn IM_BA|
|00003c40| 44 41 52 47 3b 0a 58 23 | 65 6e 64 69 66 20 2f 2a |DARG;.X#|endif /*|
|00003c50| 20 56 41 4c 49 44 41 54 | 45 20 2a 2f 0a 58 7d 0a | VALIDAT|E */.X}.|
|00003c60| 58 0a 58 0a 58 2f 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |X.X.X/**|********|
|00003c70| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003c80| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003c90| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003ca0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 0a 58 20 |********|*****.X |
|00003cb0| 2a 0a 58 20 2a 20 4c 6f | 6f 6b 20 75 70 20 74 68 |*.X * Lo|ok up th|
|00003cc0| 65 20 63 6f 64 65 20 73 | 74 72 69 6e 67 20 66 6f |e code s|tring fo|
|00003cd0| 72 20 61 20 67 69 76 65 | 6e 20 76 61 6c 75 65 2e |r a give|n value.|
|00003ce0| 0a 58 20 2a 2f 0a 58 0a | 58 23 64 65 66 69 6e 65 |.X */.X.|X#define|
|00003cf0| 20 63 74 5f 6c 6f 6f 6b | 75 70 28 68 61 6e 64 6c | ct_look|up(handl|
|00003d00| 65 2c 20 76 61 6c 75 65 | 2c 20 73 74 72 69 6e 67 |e, value|, string|
|00003d10| 2c 20 6c 65 6e 67 74 68 | 29 20 5c 0a 58 7b 20 20 |, length|) \.X{  |
|00003d20| 20 72 65 67 69 73 74 65 | 72 20 54 52 44 41 54 41 | registe|r TRDATA|
|00003d30| 20 2a 63 74 3b 20 5c 0a | 58 20 20 20 20 63 74 20 | *ct; \.|X    ct |
|00003d40| 3d 20 63 74 5f 74 61 62 | 6c 65 5b 68 61 6e 64 6c |= ct_tab|le[handl|
|00003d50| 65 5d 2e 63 74 5f 61 72 | 72 61 79 20 2b 20 28 76 |e].ct_ar|ray + (v|
|00003d60| 61 6c 75 65 29 3b 20 5c | 0a 58 20 20 20 20 73 74 |alue); \|.X    st|
|00003d70| 72 69 6e 67 20 3d 20 63 | 74 2d 3e 63 74 5f 63 6f |ring = c|t->ct_co|
|00003d80| 64 65 3b 20 5c 0a 58 20 | 20 20 20 6c 65 6e 67 74 |de; \.X |   lengt|
|00003d90| 68 20 3d 20 63 74 2d 3e | 63 74 5f 6c 65 6e 3b 20 |h = ct->|ct_len; |
|00003da0| 5c 0a 58 7d 0a 58 0a 58 | 0a 58 2f 2a 2a 2a 2a 2a |\.X}.X.X|.X/*****|
|00003db0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003dc0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003dd0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003de0| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00003df0| 2a 2a 0a 58 20 2a 0a 58 | 20 2a 20 47 65 6e 65 72 |**.X *.X| * Gener|
|00003e00| 61 74 65 20 74 68 65 20 | 63 6f 64 65 73 20 66 6f |ate the |codes fo|
|00003e10| 72 20 61 20 63 6f 64 65 | 20 74 72 65 65 2e 20 20 |r a code| tree.  |
|00003e20| 49 66 20 6f 6c 64 20 63 | 6f 64 65 73 20 61 6c 72 |If old c|odes alr|
|00003e30| 65 61 64 79 20 65 78 69 | 73 74 20 66 6f 72 0a 58 |eady exi|st for.X|
|00003e40| 20 2a 20 74 68 65 20 74 | 72 65 65 2c 20 74 68 65 | * the t|ree, the|
|00003e50| 79 20 61 72 65 20 64 69 | 73 63 61 72 64 65 64 2c |y are di|scarded,|
|00003e60| 20 61 6e 64 20 61 20 6e | 65 77 20 73 65 74 20 6f | and a n|ew set o|
|00003e70| 66 20 63 6f 64 65 73 20 | 69 73 20 67 65 6e 65 72 |f codes |is gener|
|00003e80| 61 74 65 64 0a 58 20 2a | 20 66 72 6f 6d 20 73 63 |ated.X *| from sc|
|00003e90| 72 61 74 63 68 2e 0a 58 | 20 2a 20 49 4e 20 61 73 |ratch..X| * IN as|
|00003ea0| 73 65 72 74 69 6f 6e 3a | 20 6d 61 5f 62 75 66 20 |sertion:| ma_buf |
|00003eb0| 69 73 20 61 6c 72 65 61 | 64 79 20 61 6c 6c 6f 63 |is alrea|dy alloc|
|00003ec0| 61 74 65 64 20 61 6e 64 | 20 63 61 6e 20 62 65 20 |ated and| can be |
|00003ed0| 6f 76 65 72 77 72 69 74 | 74 65 6e 2e 0a 58 20 2a |overwrit|ten..X *|
|00003ee0| 2f 0a 58 0a 6c 6f 63 61 | 6c 0a 49 6d 70 45 72 72 |/.X.loca|l.ImpErr|
|00003ef0| 0a 63 74 5f 67 65 6e 63 | 6f 64 65 73 20 28 68 61 |.ct_genc|odes (ha|
|00003f00| 6e 64 6c 65 2c 20 6d 69 | 6e 62 69 74 73 2c 20 6d |ndle, mi|nbits, m|
|00003f10| 61 78 62 69 74 73 2c 20 | 73 61 76 65 64 29 0a 58 |axbits, |saved).X|
|00003f20| 20 20 20 20 69 6e 74 20 | 20 20 68 61 6e 64 6c 65 |    int |  handle|
|00003f30| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;       |        |
|00003f40| 20 20 20 20 20 20 20 20 | 2f 2a 20 77 68 69 63 68 |        |/* which|
|00003f50| 20 74 72 65 65 20 2a 2f | 0a 58 20 20 20 20 69 6e | tree */|.X    in|
|00003f60| 74 20 20 20 6d 69 6e 62 | 69 74 73 3b 20 20 20 20 |t   minb|its;    |
|00003f70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003f80| 20 20 2f 2a 20 6d 69 6e | 20 63 6f 64 65 20 73 74 |  /* min| code st|
|00003f90| 72 69 6e 67 20 62 69 74 | 20 6c 65 6e 67 74 68 20 |ring bit| length |
|00003fa0| 2a 2f 0a 58 20 20 20 20 | 69 6e 74 20 20 20 6d 61 |*/.X    |int   ma|
|00003fb0| 78 62 69 74 73 3b 20 20 | 20 20 20 20 20 20 20 20 |xbits;  |        |
|00003fc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 6d |        |    /* m|
|00003fd0| 61 78 20 63 6f 64 65 20 | 73 74 72 69 6e 67 20 62 |ax code |string b|
|00003fe0| 69 74 20 6c 65 6e 67 74 | 68 20 2a 2f 0a 58 20 20 |it lengt|h */.X  |
|00003ff0| 20 20 6c 6f 6e 67 20 2a | 73 61 76 65 64 3b 20 20 |  long *|saved;  |
|00004000| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00004010| 20 20 20 20 20 20 2f 2a | 20 68 6f 77 20 6d 61 6e |      /*| how man|
|00004020| 79 20 62 69 74 73 20 73 | 61 76 65 64 20 2a 2f 0a |y bits s|aved */.|
|00004030| 58 7b 20 20 20 72 65 67 | 69 73 74 65 72 20 54 52 |X{   reg|ister TR|
|00004040| 44 41 54 41 20 2a 63 74 | 3b 0a 58 20 20 20 20 54 |DATA *ct|;.X    T|
|00004050| 52 44 41 54 41 20 2a 63 | 74 32 3b 0a 58 20 20 20 |RDATA *c|t2;.X   |
|00004060| 20 72 65 67 69 73 74 65 | 72 20 69 6e 74 20 6e 3b | registe|r int n;|
|00004070| 0a 58 20 20 20 20 55 4c | 5f 49 4e 54 20 66 3b 0a |.X    UL|_INT f;.|
|00004080| 58 20 20 20 20 72 65 67 | 69 73 74 65 72 20 52 45 |X    reg|ister RE|
|00004090| 53 4f 52 54 20 2a 63 72 | 3b 0a 58 20 20 20 20 69 |SORT *cr|;.X    i|
|000040a0| 6e 74 20 63 6f 64 65 2c | 20 73 72 63 6c 65 6e 3b |nt code,| srclen;|
|000040b0| 0a 58 20 20 20 20 6c 6f | 6e 67 20 74 6f 74 61 6c |.X    lo|ng total|
|000040c0| 66 72 65 71 2c 20 74 6f | 74 61 6c 62 69 74 73 3b |freq, to|talbits;|
|000040d0| 0a 58 20 20 20 20 49 6d | 70 45 72 72 20 72 65 74 |.X    Im|pErr ret|
|000040e0| 63 6f 64 65 3b 0a 58 20 | 20 20 20 52 45 53 4f 52 |code;.X |   RESOR|
|000040f0| 54 20 72 62 75 66 5b 32 | 35 36 5d 3b 0a 58 20 20 |T rbuf[2|56];.X  |
|00004100| 20 20 69 6e 74 20 73 69 | 7a 65 3b 20 2f 2a 20 61 |  int si|ze; /* a|
|00004110| 6c 69 61 73 20 66 6f 72 | 20 63 74 5f 74 61 62 6c |lias for| ct_tabl|
|00004120| 65 5b 68 61 6e 64 6c 65 | 5d 2e 63 74 5f 73 69 7a |e[handle|].ct_siz|
|00004130| 65 20 2a 2f 0a 58 20 20 | 20 20 69 6e 74 20 7a 3b |e */.X  |  int z;|
|00004140| 20 20 20 20 2f 2a 20 69 | 6e 64 65 78 20 6f 66 20 |    /* i|ndex of |
|00004150| 7a 65 72 6f 20 66 72 65 | 71 75 65 6e 63 79 20 65 |zero fre|quency e|
|00004160| 6c 65 6d 65 6e 74 20 2a | 2f 0a 58 20 20 20 20 69 |lement *|/.X    i|
|00004170| 6e 74 20 6e 7a 3b 20 20 | 20 2f 2a 20 69 6e 64 65 |nt nz;  | /* inde|
|00004180| 78 20 6f 66 20 6e 6f 6e | 20 7a 65 72 6f 20 66 72 |x of non| zero fr|
|00004190| 65 71 75 65 6e 63 79 20 | 65 6c 65 6d 65 6e 74 20 |equency |element |
|000041a0| 2a 2f 0a 58 0a 58 23 69 | 66 64 65 66 20 56 41 4c |*/.X.X#i|fdef VAL|
|000041b0| 49 44 41 54 45 0a 58 20 | 20 20 20 2f 2a 20 56 61 |IDATE.X |   /* Va|
|000041c0| 6c 69 64 61 74 65 20 74 | 68 65 20 61 72 67 75 6d |lidate t|he argum|
|000041d0| 65 6e 74 73 2e 20 2a 2f | 0a 58 20 20 20 20 69 66 |ents. */|.X    if|
|000041e0| 20 28 21 56 41 4c 49 44 | 5f 48 41 4e 44 4c 45 20 | (!VALID|_HANDLE |
|000041f0| 28 68 61 6e 64 6c 65 29 | 29 20 67 6f 74 6f 20 62 |(handle)|) goto b|
|00004200| 61 64 61 72 67 3b 0a 58 | 20 20 20 20 69 66 20 28 |adarg;.X|    if (|
|00004210| 6d 69 6e 62 69 74 73 20 | 3c 20 31 29 20 20 20 20 |minbits |< 1)    |
|00004220| 20 20 20 20 20 20 20 20 | 67 6f 74 6f 20 62 61 64 |        |goto bad|
|00004230| 61 72 67 3b 0a 58 20 20 | 20 20 69 66 20 28 6d 61 |arg;.X  |  if (ma|
|00004240| 78 62 69 74 73 20 3e 20 | 31 36 29 20 20 20 20 20 |xbits > |16)     |
|00004250| 20 20 20 20 20 20 67 6f | 74 6f 20 62 61 64 61 72 |      go|to badar|
|00004260| 67 3b 0a 58 20 20 20 20 | 69 66 20 28 6d 61 78 62 |g;.X    |if (maxb|
|00004270| 69 74 73 20 3c 20 6d 69 | 6e 62 69 74 73 29 20 20 |its < mi|nbits)  |
|00004280| 20 20 20 20 67 6f 74 6f | 20 62 61 64 61 72 67 3b |    goto| badarg;|
|00004290| 0a 58 20 20 20 20 69 66 | 20 28 73 61 76 65 64 20 |.X    if| (saved |
|000042a0| 3d 3d 20 4e 55 4c 4c 29 | 20 20 20 20 20 20 20 20 |== NULL)|        |
|000042b0| 20 20 67 6f 74 6f 20 62 | 61 64 61 72 67 3b 0a 58 |  goto b|adarg;.X|
|000042c0| 23 65 6e 64 69 66 20 2f | 2a 20 56 41 4c 49 44 41 |#endif /|* VALIDA|
|000042d0| 54 45 20 2a 2f 0a 58 20 | 20 20 20 73 69 7a 65 20 |TE */.X |   size |
|000042e0| 3d 20 63 74 5f 74 61 62 | 6c 65 5b 68 61 6e 64 6c |= ct_tab|le[handl|
|000042f0| 65 5d 2e 63 74 5f 73 69 | 7a 65 3b 0a 58 0a 58 20 |e].ct_si|ze;.X.X |
|00004300| 20 20 20 2f 2a 0a 58 20 | 20 20 20 20 2a 20 53 74 |   /*.X |    * St|
|00004310| 61 72 74 20 62 79 20 73 | 6f 72 74 69 6e 67 20 74 |art by s|orting t|
|00004320| 68 65 20 64 61 74 61 20 | 62 79 20 66 72 65 71 75 |he data |by frequ|
|00004330| 65 6e 63 79 2e 20 20 54 | 68 65 20 73 6f 75 72 63 |ency.  T|he sourc|
|00004340| 65 20 76 61 6c 75 65 73 | 20 77 69 74 68 0a 58 20 |e values| with.X |
|00004350| 20 20 20 20 2a 20 68 69 | 67 68 65 72 20 66 72 65 |    * hi|gher fre|
|00004360| 71 75 65 6e 63 79 20 6e | 65 65 64 20 74 6f 20 67 |quency n|eed to g|
|00004370| 65 74 20 74 68 65 20 73 | 68 6f 72 74 65 72 20 53 |et the s|horter S|
|00004380| 68 61 6e 6e 6f 6e 2d 46 | 61 6e 6f 20 63 6f 64 65 |hannon-F|ano code|
|00004390| 73 2e 0a 58 20 20 20 20 | 20 2a 20 46 69 72 73 74 |s..X    | * First|
|000043a0| 20 65 78 63 6c 75 64 65 | 20 74 68 65 20 65 6c 65 | exclude| the ele|
|000043b0| 6d 65 6e 74 73 20 77 69 | 74 68 20 7a 65 72 6f 20 |ments wi|th zero |
|000043c0| 66 72 65 71 75 65 6e 63 | 79 2c 20 74 6f 20 73 70 |frequenc|y, to sp|
|000043d0| 65 65 64 20 75 70 20 74 | 68 65 20 73 6f 72 74 2e |eed up t|he sort.|
|000043e0| 0a 58 20 20 20 20 20 2a | 20 54 68 69 73 20 6f 70 |.X     *| This op|
|000043f0| 74 69 6d 69 7a 61 74 69 | 6f 6e 20 69 73 20 76 65 |timizati|on is ve|
|00004400| 72 79 20 69 6d 70 6f 72 | 74 61 6e 74 20 66 6f 72 |ry impor|tant for|
|00004410| 20 73 6d 61 6c 6c 20 66 | 69 6c 65 73 2c 20 6f 74 | small f|iles, ot|
|00004420| 68 65 72 77 69 73 65 20 | 74 68 65 20 73 6f 72 74 |herwise |the sort|
|00004430| 0a 58 20 20 20 20 20 2a | 20 74 61 6b 65 73 20 6d |.X     *| takes m|
|00004440| 6f 73 74 20 6f 66 20 74 | 68 65 20 69 6d 70 6c 6f |ost of t|he implo|
|00004450| 64 65 20 74 69 6d 65 2e | 0a 58 20 20 20 20 20 2a |de time.|.X     *|
|00004460| 20 20 20 20 41 6c 73 6f | 20 64 65 74 65 72 6d 69 |    Also| determi|
|00004470| 6e 65 20 74 68 65 20 74 | 6f 74 61 6c 20 6f 66 20 |ne the t|otal of |
|00004480| 61 6c 6c 20 66 72 65 71 | 75 65 6e 63 69 65 73 2e |all freq|uencies.|
|00004490| 20 20 54 68 69 73 20 77 | 69 6c 6c 20 62 65 20 6e |  This w|ill be n|
|000044a0| 65 65 64 65 64 20 69 6e | 0a 58 20 20 20 20 20 2a |eeded in|.X     *|
|000044b0| 20 6f 72 64 65 72 20 74 | 6f 20 70 61 72 74 69 74 | order t|o partit|
|000044c0| 69 6f 6e 20 74 68 65 20 | 73 6f 75 72 63 65 20 76 |ion the |source v|
|000044d0| 61 6c 75 65 73 20 69 6e | 20 74 68 65 20 53 68 61 |alues in| the Sha|
|000044e0| 6e 6e 6f 6e 2d 46 61 6e | 6f 20 62 69 74 0a 58 20 |nnon-Fan|o bit.X |
|000044f0| 20 20 20 20 2a 20 73 74 | 72 69 6e 67 20 63 6f 6d |    * st|ring com|
|00004500| 70 75 74 61 74 69 6f 6e | 2e 20 46 69 6e 61 6c 6c |putation|. Finall|
|00004510| 79 20 63 6c 65 61 72 20 | 74 68 65 20 22 63 6f 64 |y clear |the "cod|
|00004520| 65 22 20 28 62 69 74 20 | 73 74 72 69 6e 67 29 20 |e" (bit |string) |
|00004530| 61 6e 64 20 22 6c 65 6e | 22 0a 58 20 20 20 20 20 |and "len|".X     |
|00004540| 2a 20 28 62 69 74 20 73 | 74 72 69 6e 67 20 6c 65 |* (bit s|tring le|
|00004550| 6e 67 74 68 29 20 66 69 | 65 6c 64 73 20 69 6e 20 |ngth) fi|elds in |
|00004560| 74 68 65 20 63 6f 64 65 | 20 74 72 65 65 20 61 72 |the code| tree ar|
|00004570| 72 61 79 2e 0a 58 20 20 | 20 20 20 2a 2f 0a 58 20 |ray..X  |   */.X |
|00004580| 20 20 20 74 6f 74 61 6c | 66 72 65 71 20 3d 20 30 |   total|freq = 0|
|00004590| 3b 0a 58 20 20 20 20 63 | 74 20 3d 20 63 74 5f 74 |;.X    c|t = ct_t|
|000045a0| 61 62 6c 65 5b 68 61 6e | 64 6c 65 5d 2e 63 74 5f |able[han|dle].ct_|
|000045b0| 61 72 72 61 79 3b 0a 58 | 20 20 20 20 2f 2a 20 43 |array;.X|    /* C|
|000045c0| 6f 70 79 20 63 74 20 69 | 6e 74 6f 20 61 20 74 65 |opy ct i|nto a te|
|000045d0| 6d 70 6f 20 2a 2f 0a 58 | 20 20 20 20 63 74 32 20 |mpo */.X|    ct2 |
|000045e0| 3d 20 28 54 52 44 41 54 | 41 2a 29 20 6d 61 5f 62 |= (TRDAT|A*) ma_b|
|000045f0| 75 66 3b 0a 58 20 20 20 | 20 6d 65 6d 63 70 79 28 |uf;.X   | memcpy(|
|00004600| 28 63 68 61 72 2a 29 63 | 74 32 2c 20 28 63 68 61 |(char*)c|t2, (cha|
|00004610| 72 2a 29 63 74 2c 20 73 | 69 7a 65 20 2a 20 73 69 |r*)ct, s|ize * si|
|00004620| 7a 65 6f 66 28 54 52 44 | 41 54 41 29 29 3b 0a 58 |zeof(TRD|ATA));.X|
|00004630| 20 20 20 20 66 6f 72 20 | 28 6e 7a 20 3d 20 30 2c |    for |(nz = 0,|
|00004640| 20 7a 20 3d 20 6e 20 3d | 20 73 69 7a 65 2d 31 3b | z = n =| size-1;|
|00004650| 20 6e 20 3e 3d 20 30 3b | 20 6e 2d 2d 29 20 7b 0a | n >= 0;| n--) {.|
|00004660| 58 20 20 20 20 20 20 20 | 20 69 6e 74 20 6d 3b 0a |X       | int m;.|
|00004670| 58 20 20 20 20 20 20 20 | 20 69 66 20 28 63 74 32 |X       | if (ct2|
|00004680| 5b 6e 5d 2e 63 74 5f 66 | 72 65 71 20 21 3d 20 30 |[n].ct_f|req != 0|
|00004690| 4c 29 20 7b 0a 58 20 20 | 20 20 20 20 20 20 20 20 |L) {.X  |        |
|000046a0| 20 20 6d 20 3d 20 6e 7a | 2b 2b 3b 0a 58 20 20 20 |  m = nz|++;.X   |
|000046b0| 20 20 20 20 20 20 20 20 | 20 74 6f 74 61 6c 66 72 |        | totalfr|
|000046c0| 65 71 20 2b 3d 20 28 63 | 74 5b 6d 5d 2e 63 74 5f |eq += (c|t[m].ct_|
|000046d0| 66 72 65 71 20 3d 20 63 | 74 32 5b 6e 5d 2e 63 74 |freq = c|t2[n].ct|
|000046e0| 5f 66 72 65 71 29 3b 0a | 58 20 20 20 20 20 20 20 |_freq);.|X       |
|000046f0| 20 7d 20 65 6c 73 65 20 | 7b 0a 58 20 20 20 20 20 | } else |{.X     |
|00004700| 20 20 20 20 20 20 20 6d | 20 3d 20 7a 2d 2d 3b 0a |       m| = z--;.|
|00004710| 58 20 20 20 20 20 20 20 | 20 20 20 20 20 63 74 5b |X       |     ct[|
|00004720| 6d 5d 2e 63 74 5f 66 72 | 65 71 20 3d 20 30 4c 3b |m].ct_fr|eq = 0L;|
|00004730| 0a 58 20 20 20 20 20 20 | 20 20 7d 0a 58 20 20 20 |.X      |  }.X   |
|00004740| 20 20 20 20 20 63 74 5b | 6d 5d 2e 63 74 5f 63 6f |     ct[|m].ct_co|
|00004750| 64 65 20 3d 20 30 3b 0a | 58 20 20 20 20 20 20 20 |de = 0;.|X       |
|00004760| 20 63 74 5b 6d 5d 2e 63 | 74 5f 6c 65 6e 20 3d 20 | ct[m].c|t_len = |
|00004770| 30 3b 0a 58 20 20 20 20 | 20 20 20 20 63 74 5b 6d |0;.X    |    ct[m|
|00004780| 5d 2e 63 74 5f 76 61 6c | 20 3d 20 28 55 5f 43 48 |].ct_val| = (U_CH|
|00004790| 41 52 29 6e 3b 20 2f 2a | 20 63 74 32 5b 6e 5d 2e |AR)n; /*| ct2[n].|
|000047a0| 63 74 5f 76 61 6c 20 2a | 2f 0a 58 20 20 20 20 7d |ct_val *|/.X    }|
|000047b0| 0a 58 20 20 20 20 71 73 | 6f 72 74 20 28 28 63 68 |.X    qs|ort ((ch|
|000047c0| 61 72 20 2a 29 20 28 63 | 74 5f 74 61 62 6c 65 5b |ar *) (c|t_table[|
|000047d0| 68 61 6e 64 6c 65 5d 2e | 63 74 5f 61 72 72 61 79 |handle].|ct_array|
|000047e0| 29 2c 20 6e 7a 2c 0a 58 | 20 20 20 20 20 20 20 20 |), nz,.X|        |
|000047f0| 20 20 20 73 69 7a 65 6f | 66 20 28 54 52 44 41 54 |   sizeo|f (TRDAT|
|00004800| 41 29 2c 20 28 69 6e 74 | 20 28 2a 29 28 29 29 63 |A), (int| (*)())c|
|00004810| 74 5f 66 73 6f 72 74 29 | 3b 0a 58 0a 58 20 20 20 |t_fsort)|;.X.X   |
|00004820| 20 2f 2a 0a 58 20 20 20 | 20 20 2a 20 47 65 6e 65 | /*.X   |  * Gene|
|00004830| 72 61 74 65 20 74 68 65 | 20 62 69 74 20 73 74 72 |rate the| bit str|
|00004840| 69 6e 67 73 20 76 69 61 | 20 61 20 53 68 61 6e 6e |ings via| a Shann|
|00004850| 6f 6e 2d 46 61 6e 6f 20 | 28 74 6f 70 2d 64 6f 77 |on-Fano |(top-dow|
|00004860| 6e 29 20 61 6c 67 6f 72 | 69 74 68 6d 2e 0a 58 20 |n) algor|ithm..X |
|00004870| 20 20 20 20 2a 2f 0a 58 | 20 20 20 20 72 65 74 63 |    */.X|    retc|
|00004880| 6f 64 65 20 3d 0a 58 20 | 20 20 20 20 20 20 20 63 |ode =.X |       c|
|00004890| 74 5f 73 70 6c 69 74 20 | 28 63 74 5f 74 61 62 6c |t_split |(ct_tabl|
|000048a0| 65 5b 68 61 6e 64 6c 65 | 5d 2e 63 74 5f 61 72 72 |e[handle|].ct_arr|
|000048b0| 61 79 2c 20 20 20 20 2f | 2a 20 70 61 72 74 69 74 |ay,    /|* partit|
|000048c0| 69 6f 6e 20 73 74 61 72 | 74 20 2a 2f 0a 58 20 20 |ion star|t */.X  |
|000048d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000048e0| 73 69 7a 65 2c 20 20 20 | 20 20 20 20 20 20 20 20 |size,   |        |
|000048f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 2a |        |      /*|
|00004900| 20 70 61 72 74 69 74 69 | 6f 6e 20 73 69 7a 65 20 | partiti|on size |
|00004910| 2a 2f 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |*/.X    |        |
|00004920| 20 20 20 20 20 20 74 6f | 74 61 6c 66 72 65 71 2c |      to|talfreq,|
|00004930| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00004940| 20 20 20 20 2f 2a 20 74 | 6f 74 61 6c 20 66 72 65 |    /* t|otal fre|
|00004950| 71 75 65 6e 63 79 20 2a | 2f 0a 58 20 20 20 20 20 |quency *|/.X     |
|00004960| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 30 2c 20 |        |     0, |
|00004970| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00004980| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 63 6f |        |   /* co|
|00004990| 64 65 20 73 74 72 69 6e | 67 20 70 72 65 66 69 78 |de strin|g prefix|
|000049a0| 20 2a 2f 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 | */.X   |        |
|000049b0| 20 20 20 20 20 20 20 30 | 2c 20 20 20 20 20 20 20 |       0|,       |
|000049c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000049d0| 20 20 20 20 20 2f 2a 20 | 23 20 62 69 74 73 20 69 |     /* |# bits i|
|000049e0| 6e 20 70 72 65 66 69 78 | 20 2a 2f 0a 58 20 20 20 |n prefix| */.X   |
|000049f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 6d |        |       m|
|00004a00| 69 6e 62 69 74 73 2c 20 | 20 20 20 20 20 20 20 20 |inbits, |        |
|00004a10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2f 2a 20 |        |     /* |
|00004a20| 6d 69 6e 69 6d 75 6d 20 | 74 72 65 65 20 64 65 70 |minimum |tree dep|
|00004a30| 74 68 20 2a 2f 0a 58 20 | 20 20 20 20 20 20 20 20 |th */.X |        |
|00004a40| 20 20 20 20 20 20 20 20 | 20 6d 61 78 62 69 74 73 |        | maxbits|
|00004a50| 29 3b 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |);      |        |
|00004a60| 20 20 20 20 20 20 20 2f | 2a 20 6d 61 78 69 6d 75 |       /|* maximu|
|00004a70| 6d 20 74 72 65 65 20 64 | 65 70 74 68 20 2a 2f 0a |m tree d|epth */.|
|00004a80| 58 20 20 20 20 69 66 20 | 28 72 65 74 63 6f 64 65 |X    if |(retcode|
|00004a90| 20 21 3d 20 49 4d 5f 4f | 4b 29 20 72 65 74 75 72 | != IM_O|K) retur|
|00004aa0| 6e 20 72 65 74 63 6f 64 | 65 3b 0a 58 0a 58 20 20 |n retcod|e;.X.X  |
|00004ab0| 20 20 2f 2a 0a 58 20 20 | 20 20 20 2a 20 54 68 65 |  /*.X  |   * The|
|00004ac0| 20 73 6f 75 72 63 65 20 | 76 61 6c 75 65 20 32 35 | source |value 25|
|00004ad0| 35 20 6e 65 65 64 73 20 | 74 6f 20 62 65 20 61 73 |5 needs |to be as|
|00004ae0| 73 69 67 6e 65 64 20 61 | 20 62 69 74 20 73 74 72 |signed a| bit str|
|00004af0| 69 6e 67 20 77 69 74 68 | 20 61 0a 58 20 20 20 20 |ing with| a.X    |
|00004b00| 20 2a 20 6c 65 6e 67 74 | 68 20 6f 66 20 61 74 20 | * lengt|h of at |
|00004b10| 6c 65 61 73 74 20 31 30 | 2c 20 69 6e 20 6f 72 64 |least 10|, in ord|
|00004b20| 65 72 20 74 6f 20 61 63 | 63 6f 6d 6d 6f 64 61 74 |er to ac|commodat|
|00004b30| 65 20 73 68 6f 72 74 63 | 75 74 73 20 69 6e 0a 58 |e shortc|uts in.X|
|00004b40| 20 20 20 20 20 2a 20 50 | 4b 55 4e 5a 49 50 27 73 |     * P|KUNZIP's|
|00004b50| 20 64 65 63 6f 64 69 6e | 67 20 61 6c 67 6f 72 69 | decodin|g algori|
|00004b60| 74 68 6d 2e 20 20 49 66 | 20 6e 6f 20 62 69 74 20 |thm.  If| no bit |
|00004b70| 73 74 72 69 6e 67 20 69 | 6e 20 74 68 65 20 74 72 |string i|n the tr|
|00004b80| 65 65 20 69 73 0a 58 20 | 20 20 20 20 2a 20 6f 66 |ee is.X |    * of|
|00004b90| 20 6c 65 6e 67 74 68 20 | 31 30 2c 20 77 65 20 61 | length |10, we a|
|00004ba0| 73 73 69 67 6e 20 32 35 | 35 20 74 6f 20 74 68 65 |ssign 25|5 to the|
|00004bb0| 20 6c 6f 6e 67 65 73 74 | 20 73 74 72 69 6e 67 20 | longest| string |
|00004bc0| 61 6e 64 20 68 6f 70 65 | 20 66 6f 72 0a 58 20 20 |and hope| for.X  |
|00004bd0| 20 20 20 2a 20 74 68 65 | 20 62 65 73 74 2e 0a 58 |   * the| best..X|
|00004be0| 20 20 20 20 20 2a 2f 0a | 58 20 20 20 20 6e 20 3d |     */.|X    n =|
|00004bf0| 20 73 69 7a 65 3b 0a 58 | 20 20 20 20 69 66 20 28 | size;.X|    if (|
|00004c00| 6e 20 3d 3d 20 32 35 36 | 29 0a 58 20 20 20 20 7b |n == 256|).X    {|
|00004c10| 20 20 20 66 6f 72 20 28 | 63 74 20 3d 20 63 74 5f |   for (|ct = ct_|
|00004c20| 74 61 62 6c 65 5b 68 61 | 6e 64 6c 65 5d 2e 63 74 |table[ha|ndle].ct|
|00004c30| 5f 61 72 72 61 79 3b 0a | 58 20 20 20 20 20 20 20 |_array;.|X       |
|00004c40| 20 20 20 20 20 20 6e 20 | 3e 20 30 20 26 26 20 63 |      n |> 0 && c|
|00004c50| 74 2d 3e 63 74 5f 76 61 | 6c 20 21 3d 20 32 35 35 |t->ct_va|l != 255|
|00004c60| 3b 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;.X     |        |
|00004c70| 6e 2d 2d 2c 20 63 74 2b | 2b 29 20 3b 0a 58 20 20 |n--, ct+|+) ;.X  |
|00004c80| 20 20 20 20 20 20 69 66 | 20 28 6e 20 3d 3d 20 30 |      if| (n == 0|
|00004c90| 29 0a 58 20 20 20 20 20 | 20 20 20 7b 20 20 20 66 |).X     |   {   f|
|00004ca0| 70 72 69 6e 74 66 20 28 | 73 74 64 65 72 72 2c 20 |printf (|stderr, |
|00004cb0| 22 5c 6e 45 72 72 6f 72 | 20 69 6e 20 63 74 5f 67 |"\nError| in ct_g|
|00004cc0| 65 6e 63 6f 64 65 73 3a | 20 6e 6f 20 76 61 6c 75 |encodes:| no valu|
|00004cd0| 65 20 32 35 35 22 29 3b | 0a 58 20 20 20 20 20 20 |e 255");|.X      |
|00004ce0| 20 20 20 20 20 20 72 65 | 74 75 72 6e 20 49 4d 5f |      re|turn IM_|
|00004cf0| 4c 4f 47 49 43 45 52 52 | 3b 0a 58 20 20 20 20 20 |LOGICERR|;.X     |
|00004d00| 20 20 20 7d 0a 58 20 20 | 20 20 20 20 20 20 69 66 |   }.X  |      if|
|00004d10| 20 28 63 74 2d 3e 63 74 | 5f 6c 65 6e 20 3c 20 31 | (ct->ct|_len < 1|
|00004d20| 30 29 0a 58 20 20 20 20 | 20 20 20 20 7b 20 20 20 |0).X    |    {   |
|00004d30| 63 74 32 20 3d 20 63 74 | 3b 0a 58 20 20 20 20 20 |ct2 = ct|;.X     |
|00004d40| 20 20 20 20 20 20 20 77 | 68 69 6c 65 20 28 6e 20 |       w|hile (n |
|00004d50| 3e 20 30 20 26 26 20 63 | 74 2d 3e 63 74 5f 6c 65 |> 0 && c|t->ct_le|
|00004d60| 6e 20 3c 20 31 30 29 20 | 6e 2d 2d 2c 20 63 74 2b |n < 10) |n--, ct+|
|00004d70| 2b 3b 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |+;.X    |        |
|00004d80| 69 66 20 28 6e 20 3d 3d | 20 30 29 20 63 74 2d 2d |if (n ==| 0) ct--|
|00004d90| 3b 20 20 20 2f 2a 20 6e | 6f 20 6c 65 6e 3e 3d 31 |;   /* n|o len>=1|
|00004da0| 30 20 69 6e 20 74 72 65 | 65 3b 20 75 73 65 20 6c |0 in tre|e; use l|
|00004db0| 6f 6e 67 65 73 74 20 2a | 2f 0a 58 20 20 20 20 20 |ongest *|/.X     |
|00004dc0| 20 20 20 20 20 20 20 6e | 20 3d 20 63 74 2d 3e 63 |       n| = ct->c|
|00004dd0| 74 5f 76 61 6c 3b 0a 58 | 20 20 20 20 20 20 20 20 |t_val;.X|        |
|00004de0| 20 20 20 20 20 20 20 20 | 63 74 2d 3e 63 74 5f 76 |        |ct->ct_v|
|00004df0| 61 6c 20 3d 20 63 74 32 | 2d 3e 63 74 5f 76 61 6c |al = ct2|->ct_val|
|00004e00| 3b 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;.X     |        |
|00004e10| 20 20 20 63 74 32 2d 3e | 63 74 5f 76 61 6c 20 3d |   ct2->|ct_val =|
|00004e20| 20 28 55 5f 43 48 41 52 | 29 6e 3b 0a 58 20 20 20 | (U_CHAR|)n;.X   |
|00004e30| 20 20 20 20 20 20 20 20 | 20 66 20 3d 20 63 74 2d |        | f = ct-|
|00004e40| 3e 63 74 5f 66 72 65 71 | 3b 0a 58 20 20 20 20 20 |>ct_freq|;.X     |
|00004e50| 20 20 20 20 20 20 20 20 | 20 20 20 63 74 2d 3e 63 |        |   ct->c|
|00004e60| 74 5f 66 72 65 71 20 3d | 20 63 74 32 2d 3e 63 74 |t_freq =| ct2->ct|
|00004e70| 5f 66 72 65 71 3b 0a 58 | 20 20 20 20 20 20 20 20 |_freq;.X|        |
|00004e80| 20 20 20 20 20 20 20 20 | 63 74 32 2d 3e 63 74 5f |        |ct2->ct_|
|00004e90| 66 72 65 71 20 3d 20 66 | 3b 0a 58 20 20 20 20 7d |freq = f|;.X    }|
|00004ea0| 20 20 20 7d 0a 58 0a 58 | 20 20 20 20 2f 2a 0a 58 |   }.X.X|    /*.X|
|00004eb0| 20 20 20 20 20 2a 20 54 | 68 65 20 73 6f 75 72 63 |     * T|he sourc|
|00004ec0| 65 20 76 61 6c 75 65 73 | 20 6e 65 65 64 20 74 6f |e values| need to|
|00004ed0| 20 62 65 20 72 65 2d 73 | 6f 72 74 65 64 20 73 6f | be re-s|orted so|
|00004ee0| 20 74 68 61 74 20 61 6c | 6c 20 73 6f 75 72 63 65 | that al|l source|
|00004ef0| 20 76 61 6c 75 65 73 0a | 58 20 20 20 20 20 2a 20 | values.|X     * |
|00004f00| 77 69 74 68 20 63 6f 64 | 65 20 73 74 72 69 6e 67 |with cod|e string|
|00004f10| 73 20 6f 66 20 74 68 65 | 20 73 61 6d 65 20 6c 65 |s of the| same le|
|00004f20| 6e 67 74 68 20 77 69 6c | 6c 20 62 65 20 69 6e 20 |ngth wil|l be in |
|00004f30| 61 73 63 65 6e 64 69 6e | 67 20 6f 72 64 65 72 2e |ascendin|g order.|
|00004f40| 0a 58 20 20 20 20 20 2a | 20 54 68 69 73 20 69 73 |.X     *| This is|
|00004f50| 20 62 65 63 61 75 73 65 | 20 6f 66 20 74 68 65 20 | because| of the |
|00004f60| 63 6f 6d 70 72 65 73 73 | 69 6f 6e 20 73 63 68 65 |compress|ion sche|
|00004f70| 6d 65 20 75 73 65 64 20 | 74 6f 20 72 65 70 72 65 |me used |to repre|
|00004f80| 73 65 6e 74 20 74 68 65 | 0a 58 20 20 20 20 20 2a |sent the|.X     *|
|00004f90| 20 74 72 65 65 20 69 6e | 20 74 68 65 20 5a 49 50 | tree in| the ZIP|
|00004fa0| 20 66 69 6c 65 2e 0a 58 | 20 20 20 20 20 2a 2f 0a | file..X|     */.|
|00004fb0| 58 20 20 20 20 66 6f 72 | 20 28 6e 20 3d 20 73 69 |X    for| (n = si|
|00004fc0| 7a 65 2c 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |ze,.X   |        |
|00004fd0| 20 20 63 74 20 3d 20 63 | 74 5f 74 61 62 6c 65 5b |  ct = c|t_table[|
|00004fe0| 68 61 6e 64 6c 65 5d 2e | 63 74 5f 61 72 72 61 79 |handle].|ct_array|
|00004ff0| 2c 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |,.X     |        |
|00005000| 63 72 20 3d 20 72 62 75 | 66 3b 0a 58 20 20 20 20 |cr = rbu|f;.X    |
|00005010| 20 20 20 20 20 6e 20 3e | 20 30 3b 0a 58 20 20 20 |     n >| 0;.X   |
|00005020| 20 20 20 20 20 20 6e 2d | 2d 2c 20 63 74 2b 2b 2c |      n-|-, ct++,|
|00005030| 20 63 72 2b 2b 29 0a 58 | 20 20 20 20 7b 20 20 20 | cr++).X|    {   |
|00005040| 63 72 2d 3e 63 74 5f 72 | 6c 65 6e 20 3d 20 63 74 |cr->ct_r|len = ct|
|00005050| 2d 3e 63 74 5f 6c 65 6e | 3b 0a 58 20 20 20 20 20 |->ct_len|;.X     |
|00005060| 20 20 20 63 72 2d 3e 63 | 74 5f 72 76 61 6c 20 3d |   cr->c|t_rval =|
|00005070| 20 63 74 2d 3e 63 74 5f | 76 61 6c 3b 0a 58 20 20 | ct->ct_|val;.X  |
|00005080| 20 20 7d 0a 58 20 20 20 | 20 6e 20 3d 20 73 69 7a |  }.X   | n = siz|
|00005090| 65 3b 0a 58 20 20 20 20 | 71 73 6f 72 74 20 28 28 |e;.X    |qsort ((|
|000050a0| 63 68 61 72 20 2a 29 20 | 72 62 75 66 2c 20 6e 2c |char *) |rbuf, n,|
|000050b0| 20 73 69 7a 65 6f 66 20 | 28 52 45 53 4f 52 54 29 | sizeof |(RESORT)|
|000050c0| 2c 20 28 69 6e 74 20 28 | 2a 29 28 29 29 63 74 5f |, (int (|*)())ct_|
|000050d0| 72 73 6f 72 74 29 3b 0a | 58 20 20 20 20 66 6f 72 |rsort);.|X    for|
|000050e0| 20 28 63 74 20 3d 20 63 | 74 5f 74 61 62 6c 65 5b | (ct = c|t_table[|
|000050f0| 68 61 6e 64 6c 65 5d 2e | 63 74 5f 61 72 72 61 79 |handle].|ct_array|
|00005100| 2c 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |,.X     |        |
|00005110| 63 72 20 3d 20 72 62 75 | 66 3b 0a 58 20 20 20 20 |cr = rbu|f;.X    |
|00005120| 20 20 20 20 20 6e 20 3e | 20 30 3b 0a 58 20 20 20 |     n >| 0;.X   |
|00005130| 20 20 20 20 20 20 6e 2d | 2d 2c 20 63 74 2b 2b 2c |      n-|-, ct++,|
|00005140| 20 63 72 2b 2b 29 0a 58 | 20 20 20 20 20 20 20 20 | cr++).X|        |
|00005150| 63 74 2d 3e 63 74 5f 76 | 61 6c 20 3d 20 63 72 2d |ct->ct_v|al = cr-|
|00005160| 3e 63 74 5f 72 76 61 6c | 3b 0a 58 0a 58 23 69 66 |>ct_rval|;.X.X#if|
|00005170| 64 65 66 20 44 55 4d 50 | 5f 54 52 45 45 0a 58 20 |def DUMP|_TREE.X |
|00005180| 20 20 20 70 72 69 6e 74 | 66 20 28 22 46 69 6e 69 |   print|f ("Fini|
|00005190| 73 68 65 64 20 74 72 65 | 65 3a 5c 6e 22 29 3b 0a |shed tre|e:\n");.|
|000051a0| 58 20 20 20 20 66 6f 72 | 20 28 6e 20 3d 20 73 69 |X    for| (n = si|
|000051b0| 7a 65 2c 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |ze,.X   |        |
|000051c0| 20 20 63 74 20 3d 20 63 | 74 5f 74 61 62 6c 65 5b |  ct = c|t_table[|
|000051d0| 68 61 6e 64 6c 65 5d 2e | 63 74 5f 61 72 72 61 79 |handle].|ct_array|
|000051e0| 3b 0a 58 20 20 20 20 20 | 20 20 20 20 6e 20 3e 20 |;.X     |    n > |
|000051f0| 30 3b 0a 58 20 20 20 20 | 20 20 20 20 20 6e 2d 2d |0;.X    |     n--|
|00005200| 2c 20 63 74 2b 2b 29 0a | 58 20 20 20 20 20 20 20 |, ct++).|X       |
|00005210| 20 70 72 69 6e 74 66 20 | 28 22 20 20 25 33 64 20 | printf |("  %3d |
|00005220| 28 30 78 25 30 32 78 29 | 20 20 6c 20 25 32 64 20 |(0x%02x)|  l %2d |
|00005230| 20 63 20 30 78 25 30 34 | 78 20 66 20 25 6c 64 5c | c 0x%04|x f %ld\|
|00005240| 6e 22 2c 0a 58 20 20 20 | 20 20 20 20 20 20 20 20 |n",.X   |        |
|00005250| 20 20 20 20 20 63 74 2d | 3e 63 74 5f 76 61 6c 2c |     ct-|>ct_val,|
|00005260| 20 63 74 2d 3e 63 74 5f | 76 61 6c 2c 20 63 74 2d | ct->ct_|val, ct-|
|00005270| 3e 63 74 5f 6c 65 6e 2c | 20 63 74 2d 3e 63 74 5f |>ct_len,| ct->ct_|
|00005280| 63 6f 64 65 2c 20 63 74 | 2d 3e 63 74 5f 66 72 65 |code, ct|->ct_fre|
|00005290| 71 29 3b 0a 58 20 20 20 | 20 70 75 74 63 68 61 72 |q);.X   | putchar|
|000052a0| 20 28 27 5c 6e 27 29 3b | 0a 58 23 65 6e 64 69 66 | ('\n');|.X#endif|
|000052b0| 20 2f 2a 20 44 55 4d 50 | 5f 54 52 45 45 20 2a 2f | /* DUMP|_TREE */|
|000052c0| 0a 58 0a 58 20 20 20 20 | 2f 2a 0a 58 20 20 20 20 |.X.X    |/*.X    |
|000052d0| 20 2a 20 46 69 6e 61 6c | 6c 79 2c 20 73 6f 72 74 | * Final|ly, sort|
|000052e0| 20 74 68 65 20 74 72 65 | 65 20 62 61 63 6b 20 69 | the tre|e back i|
|000052f0| 6e 20 61 73 63 65 6e 64 | 69 6e 67 20 6f 72 64 65 |n ascend|ing orde|
|00005300| 72 20 62 79 20 73 6f 75 | 72 63 65 20 76 61 6c 75 |r by sou|rce valu|
|00005310| 65 0a 58 20 20 20 20 20 | 2a 20 2d 2d 20 77 68 69 |e.X     |* -- whi|
|00005320| 63 68 20 69 73 20 74 68 | 65 20 6f 72 64 65 72 20 |ch is th|e order |
|00005330| 65 78 70 65 63 74 65 64 | 20 62 79 20 6f 74 68 65 |expected| by othe|
|00005340| 72 20 70 6f 72 74 69 6f | 6e 73 20 6f 66 20 74 68 |r portio|ns of th|
|00005350| 65 20 70 72 6f 67 72 61 | 6d 2e 0a 58 20 20 20 20 |e progra|m..X    |
|00005360| 20 2a 2f 0a 58 20 20 20 | 20 63 74 20 3d 20 63 74 | */.X   | ct = ct|
|00005370| 5f 74 61 62 6c 65 5b 68 | 61 6e 64 6c 65 5d 2e 63 |_table[h|andle].c|
|00005380| 74 5f 61 72 72 61 79 3b | 0a 58 20 20 20 20 2f 2a |t_array;|.X    /*|
|00005390| 20 43 6f 70 79 20 63 74 | 20 69 6e 74 6f 20 61 20 | Copy ct| into a |
|000053a0| 74 65 6d 70 6f 20 2a 2f | 0a 58 20 20 20 20 63 74 |tempo */|.X    ct|
|000053b0| 32 20 3d 20 28 54 52 44 | 41 54 41 2a 29 6d 61 5f |2 = (TRD|ATA*)ma_|
|000053c0| 62 75 66 3b 0a 58 20 20 | 20 20 6d 65 6d 63 70 79 |buf;.X  |  memcpy|
|000053d0| 28 28 63 68 61 72 2a 29 | 63 74 32 2c 20 28 63 68 |((char*)|ct2, (ch|
|000053e0| 61 72 2a 29 63 74 2c 20 | 73 69 7a 65 20 2a 20 73 |ar*)ct, |size * s|
|000053f0| 69 7a 65 6f 66 28 54 52 | 44 41 54 41 29 29 3b 0a |izeof(TR|DATA));.|
|00005400| 58 20 20 20 20 66 6f 72 | 20 28 6e 20 3d 20 73 69 |X    for| (n = si|
|00005410| 7a 65 2d 31 3b 20 6e 20 | 3e 3d 20 30 3b 20 6e 2d |ze-1; n |>= 0; n-|
|00005420| 2d 29 20 7b 0a 58 20 20 | 20 20 20 20 20 20 55 5f |-) {.X  |      U_|
|00005430| 43 48 41 52 20 76 20 3d | 20 63 74 32 5b 6e 5d 2e |CHAR v =| ct2[n].|
|00005440| 63 74 5f 76 61 6c 3b 0a | 58 20 20 20 20 20 20 20 |ct_val;.|X       |
|00005450| 20 63 74 5b 76 5d 2e 63 | 74 5f 66 72 65 71 20 3d | ct[v].c|t_freq =|
|00005460| 20 63 74 32 5b 6e 5d 2e | 63 74 5f 66 72 65 71 3b | ct2[n].|ct_freq;|
|00005470| 0a 58 20 20 20 20 20 20 | 20 20 63 74 5b 76 5d 2e |.X      |  ct[v].|
|00005480| 63 74 5f 63 6f 64 65 20 | 3d 20 63 74 32 5b 6e 5d |ct_code |= ct2[n]|
|00005490| 2e 63 74 5f 63 6f 64 65 | 3b 0a 58 20 20 20 20 20 |.ct_code|;.X     |
|000054a0| 20 20 20 63 74 5b 76 5d | 2e 63 74 5f 6c 65 6e 20 |   ct[v]|.ct_len |
|000054b0| 3d 20 63 74 32 5b 6e 5d | 2e 63 74 5f 6c 65 6e 3b |= ct2[n]|.ct_len;|
|000054c0| 0a 58 20 20 20 20 20 20 | 20 20 63 74 5b 76 5d 2e |.X      |  ct[v].|
|000054d0| 63 74 5f 76 61 6c 20 3d | 20 76 3b 0a 58 20 20 20 |ct_val =| v;.X   |
|000054e0| 20 7d 0a 58 0a 58 20 20 | 20 20 2f 2a 0a 58 20 20 | }.X.X  |  /*.X  |
|000054f0| 20 20 20 2a 20 44 65 74 | 65 72 6d 69 6e 65 20 68 |   * Det|ermine h|
|00005500| 6f 77 20 6d 61 6e 79 20 | 62 69 74 73 20 77 69 6c |ow many |bits wil|
|00005510| 6c 20 62 65 20 73 61 76 | 65 64 20 69 66 20 61 6c |l be sav|ed if al|
|00005520| 6c 20 74 68 65 20 73 6f | 75 72 63 65 20 64 61 74 |l the so|urce dat|
|00005530| 61 20 69 73 0a 58 20 20 | 20 20 20 2a 20 65 6e 63 |a is.X  |   * enc|
|00005540| 6f 64 65 64 20 75 73 69 | 6e 67 20 74 68 69 73 20 |oded usi|ng this |
|00005550| 6e 65 77 20 73 65 74 20 | 6f 66 20 63 6f 64 65 20 |new set |of code |
|00005560| 73 74 72 69 6e 67 73 2c | 20 61 73 20 6f 70 70 6f |strings,| as oppo|
|00005570| 73 65 64 20 74 6f 20 62 | 65 69 6e 67 0a 58 20 20 |sed to b|eing.X  |
|00005580| 20 20 20 2a 20 72 65 70 | 72 65 73 65 6e 74 65 64 |   * rep|resented|
|00005590| 20 64 69 72 65 63 74 6c | 79 20 69 6e 20 75 6e 65 | directl|y in une|
|000055a0| 6e 63 6f 64 65 64 20 66 | 6f 72 6d 2e 0a 58 20 20 |ncoded f|orm..X  |
|000055b0| 20 20 20 2a 2f 0a 58 20 | 20 20 20 2f 2a 20 23 20 |   */.X |   /* # |
|000055c0| 6f 66 20 62 69 74 73 20 | 6e 65 65 64 65 64 20 66 |of bits |needed f|
|000055d0| 6f 72 20 75 6e 65 6e 63 | 6f 64 65 64 20 73 6f 75 |or unenc|oded sou|
|000055e0| 72 63 65 20 76 61 6c 75 | 65 73 20 2a 2f 0a 58 20 |rce valu|es */.X |
|000055f0| 20 20 20 6e 20 3d 20 63 | 74 5f 74 61 62 6c 65 5b |   n = c|t_table[|
|00005600| 68 61 6e 64 6c 65 5d 2e | 63 74 5f 73 69 7a 65 3b |handle].|ct_size;|
|00005610| 0a 58 20 20 20 20 66 6f | 72 20 28 63 6f 64 65 20 |.X    fo|r (code |
|00005620| 3d 20 31 2c 20 73 72 63 | 6c 65 6e 20 3d 20 30 3b |= 1, src|len = 0;|
|00005630| 20 63 6f 64 65 20 3c 20 | 6e 3b 20 63 6f 64 65 20 | code < |n; code |
|00005640| 3c 3c 3d 20 31 2c 20 73 | 72 63 6c 65 6e 2b 2b 29 |<<= 1, s|rclen++)|
|00005650| 20 3b 0a 58 20 20 20 20 | 2f 2a 20 23 20 6f 66 20 | ;.X    |/* # of |
|00005660| 62 69 74 73 20 75 73 65 | 64 20 69 66 20 61 6c 6c |bits use|d if all|
|00005670| 20 73 6f 75 72 63 65 20 | 76 61 6c 75 65 73 20 65 | source |values e|
|00005680| 6e 63 6f 64 65 64 20 76 | 69 61 20 74 68 69 73 20 |ncoded v|ia this |
|00005690| 74 72 65 65 20 2a 2f 0a | 58 20 20 20 20 66 6f 72 |tree */.|X    for|
|000056a0| 20 28 63 74 20 3d 20 63 | 74 5f 74 61 62 6c 65 5b | (ct = c|t_table[|
|000056b0| 68 61 6e 64 6c 65 5d 2e | 63 74 5f 61 72 72 61 79 |handle].|ct_array|
|000056c0| 2c 0a 58 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |,.X     |        |
|000056d0| 74 6f 74 61 6c 62 69 74 | 73 20 3d 20 30 3b 0a 58 |totalbit|s = 0;.X|
|000056e0| 20 20 20 20 20 20 20 20 | 20 6e 20 3e 20 30 3b 0a |        | n > 0;.|
|000056f0| 58 20 20 20 20 20 20 20 | 20 20 6e 2d 2d 2c 20 63 |X       |  n--, c|
|00005700| 74 2b 2b 29 0a 58 20 20 | 20 20 20 20 20 20 74 6f |t++).X  |      to|
|00005710| 74 61 6c 62 69 74 73 20 | 2b 3d 20 63 74 2d 3e 63 |talbits |+= ct->c|
|00005720| 74 5f 66 72 65 71 20 2a | 20 63 74 2d 3e 63 74 5f |t_freq *| ct->ct_|
|00005730| 6c 65 6e 3b 0a 58 20 20 | 20 20 2f 2a 20 23 20 62 |len;.X  |  /* # b|
|00005740| 69 74 73 20 73 61 76 65 | 64 20 62 79 20 75 73 69 |its save|d by usi|
|00005750| 6e 67 20 74 68 65 20 74 | 72 65 65 20 2a 2f 0a 58 |ng the t|ree */.X|
|00005760| 20 20 20 20 2a 73 61 76 | 65 64 20 3d 20 28 74 6f |    *sav|ed = (to|
|00005770| 74 61 6c 66 72 65 71 20 | 2a 20 73 72 63 6c 65 6e |talfreq |* srclen|
|00005780| 29 20 2d 20 74 6f 74 61 | 6c 62 69 74 73 3b 0a 58 |) - tota|lbits;.X|
|00005790| 0a 58 20 20 20 20 2f 2a | 20 54 68 61 74 27 73 20 |.X    /*| That's |
|000057a0| 61 6c 6c 2e 20 2a 2f 0a | 58 20 20 20 20 72 65 74 |all. */.|X    ret|
|000057b0| 75 72 6e 20 49 4d 5f 4f | 4b 3b 0a 58 0a 58 23 69 |urn IM_O|K;.X.X#i|
|000057c0| 66 64 65 66 20 56 41 4c | 49 44 41 54 45 0a 62 61 |fdef VAL|IDATE.ba|
|000057d0| 64 61 72 67 3a 0a 58 20 | 20 20 20 66 70 72 69 6e |darg:.X |   fprin|
|000057e0| 74 66 20 28 73 74 64 65 | 72 72 2c 20 22 5c 6e 45 |tf (stde|rr, "\nE|
|000057f0| 72 72 6f 72 20 69 6e 20 | 63 74 5f 67 65 6e 63 6f |rror in |ct_genco|
|00005800| 64 65 73 3a 20 62 61 64 | 20 61 72 67 75 6d 65 6e |des: bad| argumen|
|00005810| 74 28 73 29 22 29 3b 0a | 58 20 20 20 20 72 65 74 |t(s)");.|X    ret|
|00005820| 75 72 6e 20 49 4d 5f 42 | 41 44 41 52 47 3b 0a 58 |urn IM_B|ADARG;.X|
|00005830| 23 65 6e 64 69 66 20 2f | 2a 20 56 41 4c 49 44 41 |#endif /|* VALIDA|
|00005840| 54 45 20 2a 2f 0a 58 7d | 0a 58 0a 58 0a 58 2f 2a |TE */.X}|.X.X.X/*|
|00005850| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00005860| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00005870| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00005880| 2a 2a 2a 2a 2a 2a 2a 2a | 2a 2a 2a 2a 2a 2a 2a 2a |********|********|
|00005890| 2a 2a 2a 2a 2a 2a 0a 58 | 20 2a 0a 58 20 2a 20 53 |******.X| *.X * S|
|000058a0| 70 6c 69 74 20 61 20 70 | 6f 72 74 69 6f 6e 20 6f |plit a p|ortion o|
|000058b0| 66 20 61 20 63 6f 64 65 | 20 74 72 65 65 20 69 6e |f a code| tree in|
|000058c0| 74 6f 20 74 77 6f 20 70 | 69 65 63 65 73 20 6f 66 |to two p|ieces of|
|000058d0| 20 61 70 70 72 6f 78 69 | 6d 61 74 65 6c 79 20 65 | approxi|mately e|
|000058e0| 71 75 61 6c 0a 58 20 2a | 20 74 6f 74 61 6c 20 66 |qual.X *| total f|
|000058f0| 72 65 71 75 65 6e 63 79 | 2e 20 20 54 68 69 73 20 |requency|.  This |
|00005900| 72 6f 75 74 69 6e 65 20 | 63 61 6c 6c 73 20 69 74 |routine |calls it|
|00005910| 73 65 6c 66 20 72 65 63 | 75 72 73 69 76 65 6c 79 |self rec|ursively|
|00005920| 20 69 6e 20 6f 72 64 65 | 72 20 74 6f 0a 58 20 2a | in orde|r to.X *|
|00005930| 20 67 65 6e 65 72 61 74 | 65 20 74 68 65 20 62 69 | generat|e the bi|
|00005940| 74 20 73 74 72 69 6e 67 | 73 20 66 6f 72 20 74 68 |t string|s for th|
|00005950| 65 20 65 6e 74 69 72 65 | 20 63 6f 64 65 20 74 72 |e entire| code tr|
|00005960| 65 65 2e 0a 58 20 2a 2f | 0a 58 0a 6c 6f 63 61 6c |ee..X */|.X.local|
|00005970| 0a 49 6d 70 45 72 72 0a | 63 74 5f 73 70 6c 69 74 |.ImpErr.|ct_split|
|00005980| 20 28 70 61 72 74 2c 20 | 73 69 7a 65 2c 20 66 72 | (part, |size, fr|
|00005990| 65 71 2c 20 70 72 65 66 | 69 78 2c 20 70 72 65 66 |eq, pref|ix, pref|
|000059a0| 6c 65 6e 2c 20 6d 69 6e | 62 69 74 73 2c 20 6d 61 |len, min|bits, ma|
|000059b0| 78 62 69 74 73 29 0a 58 | 20 20 20 20 54 52 44 41 |xbits).X|    TRDA|
|000059c0| 54 41 20 2a 70 61 72 74 | 3b 20 20 20 20 20 20 20 |TA *part|;       |
|000059d0| 20 20 20 20 20 20 20 20 | 2f 2a 20 73 74 61 72 74 |        |/* start|
|000059e0| 20 6f 66 20 70 61 72 74 | 69 74 69 6f 6e 20 2a 2f | of part|ition */|
|000059f0| 0a 58 20 20 20 20 69 6e | 74 20 20 20 20 20 73 69 |.X    in|t     si|
|00005a00| 7a 65 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |ze;     |        |
|00005a10| 20 20 2f 2a 20 23 20 65 | 6c 65 6d 65 6e 74 73 20 |  /* # e|lements |
|00005a20| 69 6e 20 70 61 72 74 69 | 74 69 6f 6e 20 2a 2f 0a |in parti|tion */.|
|00005a30| 58 20 20 20 20 6c 6f 6e | 67 20 20 20 20 66 72 65 |X    lon|g    fre|
|00005a40| 71 3b 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |q;      |        |
|00005a50| 20 2f 2a 20 73 75 6d 20 | 6f 66 20 66 72 65 71 75 | /* sum |of frequ|
|00005a60| 65 6e 63 69 65 73 20 69 | 6e 20 70 61 72 74 69 74 |encies i|n partit|
|00005a70| 69 6f 6e 20 2a 2f 0a 58 | 20 20 20 20 69 6e 74 20 |ion */.X|    int |
|00005a80| 20 20 20 20 70 72 65 66 | 69 78 3b 20 20 20 20 20 |    pref|ix;     |
|00005a90| 20 20 20 20 20 20 20 20 | 2f 2a 20 69 6e 69 74 69 |        |/* initi|
|00005aa0| 61 6c 20 63 6f 64 65 20 | 62 69 74 73 20 66 6f 72 |al code |bits for|
|00005ab0| 20 70 61 72 74 69 74 69 | 6f 6e 20 2a 2f 0a 58 20 | partiti|on */.X |
|00005ac0| 20 20 20 69 6e 74 20 20 | 20 20 20 70 72 65 66 6c |   int  |   prefl|
|00005ad0| 65 6e 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 2f |en;     |       /|
|00005ae0| 2a 20 23 20 62 69 74 73 | 20 69 6e 20 70 72 65 66 |* # bits| in pref|
|00005af0| 69 78 20 2a 2f 0a 58 20 | 20 20 20 69 6e 74 20 20 |ix */.X |   int  |
|00005b00| 20 20 20 6d 69 6e 62 69 | 74 73 3b 20 20 20 20 20 |   minbi|ts;     |
|00005b10| 20 20 20 20 20 20 20 2f | 2a 20 6d 69 6e 69 6d 75 |       /|* minimu|
|00005b20| 6d 20 70 65 72 6d 69 73 | 73 69 62 6c 65 20 62 69 |m permis|sible bi|
|00005b30| 74 20 6c 65 6e 67 74 68 | 20 2a 2f 0a 58 20 20 20 |t length| */.X   |
|00005b40| 20 69 6e 74 20 20 20 20 | 20 6d 61 78 62 69 74 73 | int    | maxbits|
|00005b50| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 2f 2a 20 |;       |     /* |
|00005b60| 6d 61 78 69 6d 75 6d 20 | 70 65 72 6d 69 73 73 69 |maximum |permissi|
|00005b70| 62 6c 65 20 62 69 74 20 | 6c 65 6e 67 74 68 20 2a |ble bit |length *|
|00005b80| 2f 0a 58 7b 20 20 20 72 | 65 67 69 73 74 65 72 20 |/.X{   r|egister |
|00005b90| 54 52 44 41 54 41 20 2a | 63 74 3b 0a 58 20 20 20 |TRDATA *|ct;.X   |
|00005ba0| 20 69 6e 74 20 74 6f 70 | 6d 61 78 62 69 74 73 2c | int top|maxbits,|
|00005bb0| 20 62 6f 74 6d 61 78 62 | 69 74 73 2c 20 6c 6f 63 | botmaxb|its, loc|
|00005bc0| 61 6c 6d 69 6e 62 69 74 | 73 3b 0a 58 20 20 20 20 |alminbit|s;.X    |
|00005bd0| 55 5f 49 4e 54 20 74 6f | 70 6d 61 78 76 61 6c 73 |U_INT to|pmaxvals|
|00005be0| 2c 20 62 6f 74 6d 61 78 | 76 61 6c 73 3b 0a 58 20 |, botmax|vals;.X |
|00005bf0| 20 20 20 69 6e 74 20 74 | 6f 70 73 69 7a 65 2c 20 |   int t|opsize, |
|00005c00| 62 6f 74 73 69 7a 65 3b | 0a 58 20 20 20 20 6c 6f |botsize;|.X    lo|
|00005c10| 6e 67 20 74 6f 70 66 72 | 65 71 2c 20 62 6f 74 66 |ng topfr|eq, botf|
|00005c20| 72 65 71 2c 20 68 61 6c | 66 66 72 65 71 2c 20 6f |req, hal|ffreq, o|
|00005c30| 6e 65 66 72 65 71 3b 0a | 58 20 20 20 20 69 6e 74 |nefreq;.|X    int|
|00005c40| 20 6e 2c 20 6d 2c 20 6c | 65 61 64 7a 65 72 6f 73 | n, m, l|eadzeros|
|00005c50| 3b 0a 58 20 20 20 20 69 | 6e 74 20 6d 61 78 73 68 |;.X    i|nt maxsh|
|00005c60| 6f 72 74 2c 20 6d 69 6e | 6c 6f 6e 67 3b 0a 58 20 |ort, min|long;.X |
|00005c70| 20 20 20 49 6d 70 45 72 | 72 20 72 65 74 63 6f 64 |   ImpEr|r retcod|
|00005c80| 65 3b 0a 58 20 20 20 20 | 73 74 61 74 69 63 20 6d |e;.X    |static m|
|00005c90| 61 78 61 72 72 61 79 5b | 31 37 5d 20 3d 0a 58 20 |axarray[|17] =.X |
|00005ca0| 20 20 20 20 20 20 20 7b | 20 38 2c 38 2c 38 2c 38 |       {| 8,8,8,8|
|00005cb0| 2c 31 32 2c 31 32 2c 31 | 34 2c 31 34 2c 31 36 2c |,12,12,1|4,14,16,|
|00005cc0| 31 36 2c 31 36 2c 31 36 | 2c 31 36 2c 31 36 2c 31 |16,16,16|,16,16,1|
|00005cd0| 36 2c 31 36 2c 31 36 20 | 7d 3b 0a 58 0a 58 23 69 |6,16,16 |};.X.X#i|
|00005ce0| 66 64 65 66 20 56 41 4c | 49 44 41 54 45 0a 58 20 |fdef VAL|IDATE.X |
|00005cf0| 20 20 20 69 66 20 28 70 | 61 72 74 20 3d 3d 20 4e |   if (p|art == N|
|00005d00| 55 4c 4c 29 20 20 20 20 | 20 20 20 20 20 20 20 67 |ULL)    |       g|
|00005d10| 6f 74 6f 20 62 61 64 61 | 72 67 3b 0a 58 20 20 20 |oto bada|rg;.X   |
|00005d20| 20 69 66 20 28 73 69 7a | 65 20 3c 20 31 29 20 20 | if (siz|e < 1)  |
|00005d30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 67 6f 74 |        |     got|
|00005d40| 6f 20 62 61 64 61 72 67 | 3b 0a 58 20 20 20 20 69 |o badarg|;.X    i|
|00005d50| 66 20 28 66 72 65 71 20 | 3c 20 30 29 20 20 20 20 |f (freq |< 0)    |
|00005d60| 20 20 20 20 20 20 20 20 | 20 20 20 67 6f 74 6f 20 |        |   goto |
|00005d70| 62 61 64 61 72 67 3b 0a | 58 20 20 20 20 69 66 20 |badarg;.|X    if |
|00005d80| 28 70 72 65 66 6c 65 6e | 20 3c 20 30 29 20 20 20 |(preflen| < 0)   |
|00005d90| 20 20 20 20 20 20 20 20 | 20 67 6f 74 6f 20 62 61 |        | goto ba|
|00005da0| 64 61 72 67 3b 0a 58 20 | 20 20 20 69 66 20 28 70 |darg;.X |   if (p|
|00005db0| 72 65 66 6c 65 6e 20 3e | 20 6d 61 78 62 69 74 73 |reflen >| maxbits|
|00005dc0| 29 20 20 20 20 20 20 67 | 6f 74 6f 20 62 61 64 61 |)      g|oto bada|
|00005dd0| 72 67 3b 0a 58 20 20 20 | 20 69 66 20 28 6d 69 6e |rg;.X   | if (min|
|00005de0| 62 69 74 73 20 3c 20 70 | 72 65 66 6c 65 6e 29 20 |bits < p|reflen) |
|00005df0| 20 20 20 20 20 67 6f 74 | 6f 20 62 61 64 61 72 67 |     got|o badarg|
|00005e00| 3b 0a 58 20 20 20 20 69 | 66 20 28 6d 61 78 62 69 |;.X    i|f (maxbi|
|00005e10| 74 73 20 3e 20 31 36 29 | 20 20 20 20 20 20 20 20 |ts > 16)|        |
|00005e20| 20 20 20 67 6f 74 6f 20 | 62 61 64 61 72 67 3b 0a |   goto |badarg;.|
|00005e30| 58 20 20 20 20 69 66 20 | 28 6d 61 78 62 69 74 73 |X    if |(maxbits|
|00005e40| 20 3c 20 6d 69 6e 62 69 | 74 73 29 20 20 20 20 20 | < minbi|ts)     |
|00005e50| 20 67 6f 74 6f 20 62 61 | 64 61 72 67 3b 0a 58 20 | goto ba|darg;.X |
|00005e60| 20 20 20 2f 2a 0a 58 20 | 20 20 20 70 75 74 63 20 |   /*.X |   putc |
|00005e70| 28 27 5c 6e 27 2c 20 73 | 74 64 65 72 72 29 3b 0a |('\n', s|tderr);.|
|00005e80| 58 20 20 20 20 66 6f 72 | 20 28 6e 20 3d 20 70 72 |X    for| (n = pr|
|00005e90| 65 66 6c 65 6e 3b 20 6e | 20 3e 20 30 3b 20 6e 2d |eflen; n| > 0; n-|
|00005ea0| 2d 29 20 66 70 72 69 6e | 74 66 20 28 73 74 64 65 |-) fprin|tf (stde|
|00005eb0| 72 72 2c 20 22 20 20 20 | 22 29 3b 0a 58 20 20 20 |rr, "   |");.X   |
|00005ec0| 20 66 70 72 69 6e 74 66 | 20 28 73 74 64 65 72 72 | fprintf| (stderr|
|00005ed0| 2c 20 22 63 74 5f 73 70 | 6c 69 74 20 28 73 7a 3d |, "ct_sp|lit (sz=|
|00005ee0| 25 64 2c 20 70 72 3d 25 | 30 34 78 5b 25 64 5d 2c |%d, pr=%|04x[%d],|
|00005ef0| 20 6d 69 6e 3d 25 64 2c | 20 6d 61 78 3d 25 64 29 | min=%d,| max=%d)|
|00005f00| 22 2c 0a 58 20 20 20 20 | 20 20 20 20 20 20 20 20 |",.X    |        |
|00005f10| 20 73 69 7a 65 2c 20 70 | 72 65 66 69 78 2c 20 70 | size, p|refix, p|
|00005f20| 72 65 66 6c 65 6e 2c 20 | 6d 69 6e 62 69 74 73 2c |reflen, |minbits,|
|00005f30| 20 6d 61 78 62 69 74 73 | 29 3b 0a 58 20 20 20 20 | maxbits|);.X    |
|00005f40| 2a 2f 0a 58 23 65 6e 64 | 69 66 20 2f 2a 20 56 41 |*/.X#end|if /* VA|
|00005f50| 4c 49 44 41 54 45 20 2a | 2f 0a 58 0a 58 20 20 20 |LIDATE *|/.X.X   |
|00005f60| 20 2f 2a 0a 58 20 20 20 | 20 20 2a 20 49 66 20 74 | /*.X   |  * If t|
|00005f70| 68 65 72 65 27 73 20 6f | 6e 6c 79 20 6f 6e 65 20 |here's o|nly one |
|00005f80| 65 6c 65 6d 65 6e 74 20 | 69 6e 20 74 68 69 73 20 |element |in this |
|00005f90| 70 61 72 74 69 74 69 6f | 6e 2c 20 77 65 20 73 69 |partitio|n, we si|
|00005fa0| 6d 70 6c 79 20 74 61 6b | 65 0a 58 20 20 20 20 20 |mply tak|e.X     |
|00005fb0| 2a 20 74 68 65 20 22 70 | 72 65 66 69 78 22 20 76 |* the "p|refix" v|
|00005fc0| 61 6c 75 65 20 61 73 20 | 74 68 65 20 63 6f 64 65 |alue as |the code|
|00005fd0| 20 73 74 72 69 6e 67 20 | 66 6f 72 20 74 68 65 20 | string |for the |
|00005fe0| 73 69 6e 67 6c 65 20 65 | 6c 65 6d 65 6e 74 2e 0a |single e|lement..|
|00005ff0| 58 20 20 20 20 20 2a 20 | 57 65 20 72 65 76 65 72 |X     * |We rever|
|00006000| 73 65 20 74 68 65 20 62 | 69 74 73 20 6f 66 20 74 |se the b|its of t|
|00006010| 68 65 20 70 72 65 66 69 | 78 20 66 6f 72 20 6d 6f |he prefi|x for mo|
|00006020| 72 65 20 65 66 66 69 63 | 69 65 6e 74 20 6f 75 74 |re effic|ient out|
|00006030| 70 75 74 2e 0a 58 20 20 | 20 20 20 2a 2f 0a 58 20 |put..X  |   */.X |
|00006040| 20 20 20 69 66 20 28 73 | 69 7a 65 20 3d 3d 20 31 |   if (s|ize == 1|
|00006050| 29 0a 58 20 20 20 20 7b | 20 20 20 70 61 72 74 2d |).X    {|   part-|
|00006060| 3e 63 74 5f 63 6f 64 65 | 20 3d 20 62 69 5f 72 65 |>ct_code| = bi_re|
|00006070| 76 65 72 73 65 28 70 72 | 65 66 69 78 2c 20 70 72 |verse(pr|efix, pr|
|00006080| 65 66 6c 65 6e 29 3b 0a | 58 20 20 20 20 20 20 20 |eflen);.|X       |
|00006090| 20 70 61 72 74 2d 3e 63 | 74 5f 6c 65 6e 20 20 3d | part->c|t_len  =|
|000060a0| 20 28 55 5f 43 48 41 52 | 29 70 72 65 66 6c 65 6e | (U_CHAR|)preflen|
|000060b0| 3b 0a 58 20 20 20 20 20 | 20 20 20 72 65 74 75 72 |;.X     |   retur|
|000060c0| 6e 20 49 4d 5f 4f 4b 3b | 0a 58 20 20 20 20 7d 0a |n IM_OK;|.X    }.|
|000060d0| 58 0a 58 20 20 20 20 2f | 2a 0a 58 20 20 20 20 20 |X.X    /|*.X     |
|000060e0| 2a 20 54 68 69 73 20 70 | 61 72 74 69 74 69 6f 6e |* This p|artition|
|000060f0| 20 77 69 6c 6c 20 62 65 | 20 64 69 76 69 64 65 64 | will be| divided|
|00006100| 20 69 6e 74 6f 20 74 77 | 6f 20 70 61 72 74 73 2e | into tw|o parts.|
|00006110| 20 20 54 68 65 20 22 74 | 6f 70 22 20 70 61 72 74 |  The "t|op" part|
|00006120| 0a 58 20 20 20 20 20 2a | 20 77 69 6c 6c 20 68 61 |.X     *| will ha|
|00006130| 76 65 20 61 20 22 31 22 | 20 62 69 74 20 61 70 70 |ve a "1"| bit app|
|00006140| 65 6e 64 65 64 20 74 6f | 20 69 74 73 20 22 70 72 |ended to| its "pr|
|00006150| 65 66 69 78 22 20 62 69 | 74 20 73 74 72 69 6e 67 |efix" bi|t string|
|00006160| 3b 20 74 68 65 0a 58 20 | 20 20 20 20 2a 20 22 62 |; the.X |    * "b|
|00006170| 6f 74 74 6f 6d 22 20 70 | 61 72 74 20 77 69 6c 6c |ottom" p|art will|
|00006180| 20 68 61 76 65 20 61 20 | 22 30 22 20 62 69 74 20 | have a |"0" bit |
|00006190| 61 70 70 65 6e 64 65 64 | 20 74 6f 20 69 74 73 20 |appended| to its |
|000061a0| 22 70 72 65 66 69 78 22 | 2e 0a 58 20 20 20 20 20 |"prefix"|..X     |
|000061b0| 2a 0a 58 20 20 20 20 20 | 2a 20 57 65 20 6e 65 65 |*.X     |* We nee|
|000061c0| 64 20 74 6f 20 64 65 74 | 65 72 6d 69 6e 65 20 74 |d to det|ermine t|
|000061d0| 68 65 20 6d 61 78 69 6d | 75 6d 20 6e 75 6d 62 65 |he maxim|um numbe|
|000061e0| 72 20 6f 66 20 73 6f 75 | 72 63 65 20 76 61 6c 75 |r of sou|rce valu|
|000061f0| 65 73 20 77 68 69 63 68 | 0a 58 20 20 20 20 20 2a |es which|.X     *|
|00006200| 20 6d 61 79 20 62 65 20 | 61 73 73 69 67 6e 65 64 | may be |assigned|
|00006210| 20 74 6f 20 74 68 65 20 | 74 77 6f 20 70 61 72 74 | to the |two part|
|00006220| 69 74 69 6f 6e 73 2e 20 | 20 54 68 65 20 66 69 72 |itions. | The fir|
|00006230| 73 74 20 69 73 73 75 65 | 20 74 6f 20 63 6f 6e 2d |st issue| to con-|
|00006240| 0a 58 20 20 20 20 20 2a | 20 73 69 64 65 72 20 69 |.X     *| sider i|
|00006250| 73 20 74 68 61 74 20 50 | 4b 55 4e 5a 49 50 20 31 |s that P|KUNZIP 1|
|00006260| 2e 31 30 27 73 20 74 72 | 65 65 2d 64 65 63 6f 64 |.10's tr|ee-decod|
|00006270| 69 6e 67 20 73 68 6f 72 | 74 63 75 74 73 20 72 65 |ing shor|tcuts re|
|00006280| 71 75 69 72 65 20 61 0a | 58 20 20 20 20 20 2a 20 |quire a.|X     * |
|00006290| 63 65 72 74 61 69 6e 20 | 6e 75 6d 62 65 72 20 6f |certain |number o|
|000062a0| 66 20 6c 65 61 64 69 6e | 67 20 22 30 22 20 62 69 |f leadin|g "0" bi|
|000062b0| 74 73 20 69 6e 20 65 61 | 63 68 20 63 6f 64 65 20 |ts in ea|ch code |
|000062c0| 73 74 72 69 6e 67 2c 20 | 64 65 70 65 6e 64 69 6e |string, |dependin|
|000062d0| 67 0a 58 20 20 20 20 20 | 2a 20 6f 6e 20 69 74 73 |g.X     |* on its|
|000062e0| 20 6c 65 6e 67 74 68 2e | 20 20 43 6f 64 65 20 73 | length.|  Code s|
|000062f0| 74 72 69 6e 67 73 20 6f | 66 20 39 2d 31 32 20 62 |trings o|f 9-12 b|
|00006300| 69 74 73 20 6d 75 73 74 | 20 68 61 76 65 20 61 74 |its must| have at|
|00006310| 20 6c 65 61 73 74 20 34 | 0a 58 20 20 20 20 20 2a | least 4|.X     *|
|00006320| 20 6c 65 61 64 69 6e 67 | 20 7a 65 72 6f 73 3b 20 | leading| zeros; |
|00006330| 73 74 72 69 6e 67 73 20 | 6f 66 20 31 33 20 6f 72 |strings |of 13 or|
|00006340| 20 31 34 20 62 69 74 73 | 2c 20 61 74 20 6c 65 61 | 14 bits|, at lea|
|00006350| 73 74 20 36 20 6c 65 61 | 64 69 6e 67 0a 58 20 20 |st 6 lea|ding.X  |
|00006360| 20 20 20 2a 20 7a 65 72 | 6f 73 3b 20 61 6e 64 20 |   * zer|os; and |
|00006370| 73 74 72 69 6e 67 73 20 | 6f 66 20 31 35 20 6f 72 |strings |of 15 or|
|00006380| 20 31 36 20 62 69 74 73 | 2c 20 61 74 20 6c 65 61 | 16 bits|, at lea|
|00006390| 73 74 20 38 20 6c 65 61 | 64 69 6e 67 20 7a 65 72 |st 8 lea|ding zer|
|000063a0| 6f 73 2e 0a 58 20 20 20 | 20 20 2a 0a 58 20 20 20 |os..X   |  *.X   |
|000063b0| 20 20 2a 20 49 66 20 74 | 68 65 20 22 70 72 65 66 |  * If t|he "pref|
|000063c0| 69 78 22 20 69 73 20 7a | 65 72 6f 2c 20 74 68 65 |ix" is z|ero, the|
|000063d0| 20 61 62 6f 76 65 20 6c | 69 6d 69 74 61 74 69 6f | above l|imitatio|
|000063e0| 6e 20 69 73 20 75 73 65 | 64 20 74 6f 20 72 65 73 |n is use|d to res|
|000063f0| 74 72 69 63 74 0a 58 20 | 20 20 20 20 2a 20 74 68 |trict.X |    * th|
+--------+-------------------------+-------------------------+--------+--------+