Mercurial > hg > CbC > CbC_gcc

annotate zlib/inftrees.c @ 51:ae3a4bfb450b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add some files of version 4.4.3 that have been forgotten.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Sun, 07 Feb 2010 18:27:48 +0900
parents
children 04ced10e8804
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
51
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* inftrees.c -- generate Huffman trees for efficient decoding
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 * Copyright (C) 1995-2005 Mark Adler
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 * For conditions of distribution and use, see copyright notice in zlib.h
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 #include "zutil.h"
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 #include "inftrees.h"
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 #define MAXBITS 15
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 const char inflate_copyright[] =
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 " inflate 1.2.3 Copyright 1995-2005 Mark Adler ";
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 /*
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 If you use the zlib library in a product, an acknowledgment is welcome
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 in the documentation of your product. If for some reason you cannot
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 include such an acknowledgment, I would appreciate that you keep this
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 copyright string in the executable of your product.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 /*
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 Build a set of tables to decode the provided canonical Huffman code.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 The code lengths are lens[0..codes-1]. The result starts at *table,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 whose indices are 0..2^bits-1. work is a writable array of at least
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 lens shorts, which is used as a work area. type is the type of code
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 to be generated, CODES, LENS, or DISTS. On return, zero is success,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 on return points to the next available entry's address. bits is the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 requested root table index bits, and on return it is the actual root
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 table index bits. It will differ if the request is greater than the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 longest code or if it is less than the shortest code.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 int inflate_table(type, lens, codes, table, bits, work)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 codetype type;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 unsigned short FAR *lens;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 unsigned codes;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 code FAR * FAR *table;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 unsigned FAR *bits;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 unsigned short FAR *work;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 unsigned len; /* a code's length in bits */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 unsigned sym; /* index of code symbols */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 unsigned min, max; /* minimum and maximum code lengths */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 unsigned root; /* number of index bits for root table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 unsigned curr; /* number of index bits for current table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 unsigned drop; /* code bits to drop for sub-table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 int left; /* number of prefix codes available */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 unsigned used; /* code entries in table used */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 unsigned huff; /* Huffman code */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 unsigned incr; /* for incrementing code, index */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 unsigned fill; /* index for replicating entries */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 unsigned low; /* low bits for current root entry */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 unsigned mask; /* mask for low root bits */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 code this; /* table entry for duplication */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 code FAR *next; /* next available space in table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 const unsigned short FAR *base; /* base value table to use */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 const unsigned short FAR *extra; /* extra bits table to use */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 int end; /* use base and extra for symbol > end */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 unsigned short count[MAXBITS+1]; /* number of codes of each length */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 8193, 12289, 16385, 24577, 0, 0};
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 28, 28, 29, 29, 64, 64};
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 /*
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 Process a set of code lengths to create a canonical Huffman code. The
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 code lengths are lens[0..codes-1]. Each length corresponds to the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 symbols 0..codes-1. The Huffman code is generated by first sorting the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 symbols by length from short to long, and retaining the symbol order
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 for codes with equal lengths. Then the code starts with all zero bits
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 for the first code of the shortest length, and the codes are integer
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 increments for the same length, and zeros are appended as the length
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 increases. For the deflate format, these bits are stored backwards
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 from their more natural integer increment ordering, and so when the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 decoding tables are built in the large loop below, the integer codes
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 are incremented backwards.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 This routine assumes, but does not check, that all of the entries in
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 lens[] are in the range 0..MAXBITS. The caller must assure this.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 1..MAXBITS is interpreted as that code length. zero means that that
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 symbol does not occur in this code.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 The codes are sorted by computing a count of codes for each length,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 creating from that a table of starting indices for each length in the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 sorted table, and then entering the symbols in order in the sorted
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 table. The sorted table is work[], with that space being provided by
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 the caller.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
98
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 The length counts are used for other purposes as well, i.e. finding
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 the minimum and maximum length codes, determining if there are any
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 codes at all, checking for a valid set of lengths, and looking ahead
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 at length counts to determine sub-table sizes when building the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 decoding tables.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
105
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 for (len = 0; len <= MAXBITS; len++)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 count[len] = 0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 for (sym = 0; sym < codes; sym++)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 count[lens[sym]]++;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 /* bound code lengths, force root to be within code lengths */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 root = *bits;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 for (max = MAXBITS; max >= 1; max--)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 if (count[max] != 0) break;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 if (root > max) root = max;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 if (max == 0) { /* no symbols to code at all */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 this.op = (unsigned char)64; /* invalid code marker */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 this.bits = (unsigned char)1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 this.val = (unsigned short)0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 *(*table)++ = this; /* make a table to force an error */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 *(*table)++ = this;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 *bits = 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 return 0; /* no symbols, but wait for decoding to report error */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 for (min = 1; min <= MAXBITS; min++)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 if (count[min] != 0) break;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 if (root < min) root = min;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
129
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 /* check for an over-subscribed or incomplete set of lengths */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 left = 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 for (len = 1; len <= MAXBITS; len++) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 left <<= 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 left -= count[len];
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 if (left < 0) return -1; /* over-subscribed */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
136 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 if (left > 0 && (type == CODES || max != 1))
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 return -1; /* incomplete set */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
139
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 /* generate offsets into symbol table for each length for sorting */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 offs[1] = 0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 for (len = 1; len < MAXBITS; len++)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 offs[len + 1] = offs[len] + count[len];
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
144
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 /* sort symbols by length, by symbol order within each length */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 for (sym = 0; sym < codes; sym++)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
148
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 /*
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 Create and fill in decoding tables. In this loop, the table being
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 filled is at next and has curr index bits. The code being used is huff
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 with length len. That code is converted to an index by dropping drop
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 bits off of the bottom. For codes where len is less than drop + curr,
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 those top drop + curr - len bits are incremented through all values to
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 fill the table with replicated entries.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
156
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 root is the number of index bits for the root table. When len exceeds
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 root, sub-tables are created pointed to by the root entry with an index
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 of the low root bits of huff. This is saved in low to check for when a
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 new sub-table should be started. drop is zero when the root table is
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 being filled, and drop is root when sub-tables are being filled.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
162
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 When a new sub-table is needed, it is necessary to look ahead in the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 code lengths to determine what size sub-table is needed. The length
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
165 counts are used for this, and so count[] is decremented as codes are
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 entered in the tables.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
167
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 used keeps track of how many table entries have been allocated from the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
169 provided *table space. It is checked when a LENS table is being made
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 against the space in *table, ENOUGH, minus the maximum space needed by
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 the worst case distance code, MAXD. This should never happen, but the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 This assumes that when type == LENS, bits == 9.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
174
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
175 sym increments through all symbols, and the loop terminates when
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 all codes of length max, i.e. all codes, have been processed. This
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 routine permits incomplete codes, so another loop after this one fills
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
178 in the rest of the decoding tables with invalid code markers.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
180
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
181 /* set up for code type */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 switch (type) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
183 case CODES:
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 base = extra = work; /* dummy value--not used */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
185 end = 19;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 break;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 case LENS:
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 base = lbase;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 base -= 257;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
190 extra = lext;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 extra -= 257;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
192 end = 256;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 break;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 default: /* DISTS */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 base = dbase;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
196 extra = dext;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
197 end = -1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
199
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
200 /* initialize state for loop */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 huff = 0; /* starting code */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 sym = 0; /* starting code symbol */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 len = min; /* starting code length */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 next = *table; /* current table to fill in */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 curr = root; /* current table index bits */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 drop = 0; /* current bits to drop from code for index */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
207 low = (unsigned)(-1); /* trigger new sub-table when len > root */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 used = 1U << root; /* use root table entries */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 mask = used - 1; /* mask for comparing low */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
210
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
211 /* check available table space */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 if (type == LENS && used >= ENOUGH - MAXD)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
213 return 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
214
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
215 /* process all codes and make table entries */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 for (;;) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 /* create table entry */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
218 this.bits = (unsigned char)(len - drop);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
219 if ((int)(work[sym]) < end) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
220 this.op = (unsigned char)0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 this.val = work[sym];
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
223 else if ((int)(work[sym]) > end) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
224 this.op = (unsigned char)(extra[work[sym]]);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 this.val = base[work[sym]];
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
226 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
227 else {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 this.op = (unsigned char)(32 + 64); /* end of block */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
229 this.val = 0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
230 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
231
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 /* replicate for those indices with low len bits equal to huff */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
233 incr = 1U << (len - drop);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
234 fill = 1U << curr;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
235 min = fill; /* save offset to next table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 do {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
237 fill -= incr;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
238 next[(huff >> drop) + fill] = this;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
239 } while (fill != 0);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
240
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 /* backwards increment the len-bit code huff */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
242 incr = 1U << (len - 1);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
243 while (huff & incr)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
244 incr >>= 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
245 if (incr != 0) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
246 huff &= incr - 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
247 huff += incr;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
248 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
249 else
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
250 huff = 0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
251
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
252 /* go to next symbol, update count, len */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
253 sym++;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
254 if (--(count[len]) == 0) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
255 if (len == max) break;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
256 len = lens[work[sym]];
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
257 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
258
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
259 /* create new sub-table if needed */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
260 if (len > root && (huff & mask) != low) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
261 /* if first time, transition to sub-tables */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
262 if (drop == 0)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
263 drop = root;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
264
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
265 /* increment past last table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
266 next += min; /* here min is 1 << curr */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
267
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
268 /* determine length of next table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
269 curr = len - drop;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
270 left = (int)(1 << curr);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
271 while (curr + drop < max) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
272 left -= count[curr + drop];
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
273 if (left <= 0) break;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
274 curr++;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
275 left <<= 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
276 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
277
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
278 /* check for enough space */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
279 used += 1U << curr;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
280 if (type == LENS && used >= ENOUGH - MAXD)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
281 return 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
282
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
283 /* point entry in root table to sub-table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
284 low = huff & mask;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
285 (*table)[low].op = (unsigned char)curr;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
286 (*table)[low].bits = (unsigned char)root;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
287 (*table)[low].val = (unsigned short)(next - *table);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
288 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
289 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
290
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
291 /*
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
292 Fill in rest of table for incomplete codes. This loop is similar to the
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
293 loop above in incrementing huff for table indices. It is assumed that
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
294 len is equal to curr + drop, so there is no loop needed to increment
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
295 through high index bits. When the current sub-table is filled, the loop
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
296 drops back to the root table to fill in any remaining entries there.
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
297 */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
298 this.op = (unsigned char)64; /* invalid code marker */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
299 this.bits = (unsigned char)(len - drop);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
300 this.val = (unsigned short)0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
301 while (huff != 0) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
302 /* when done with sub-table, drop back to root table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
303 if (drop != 0 && (huff & mask) != low) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
304 drop = 0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
305 len = root;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
306 next = *table;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
307 this.bits = (unsigned char)len;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
308 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
309
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
310 /* put invalid code marker in table */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
311 next[huff >> drop] = this;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
312
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
313 /* backwards increment the len-bit code huff */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
314 incr = 1U << (len - 1);
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
315 while (huff & incr)
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
316 incr >>= 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
317 if (incr != 0) {
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
318 huff &= incr - 1;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
319 huff += incr;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
320 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
321 else
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
322 huff = 0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
323 }
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
324
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
325 /* set return parameters */
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
326 *table += used;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
327 *bits = root;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
328 return 0;
ae3a4bfb450b add some files of version 4.4.3 that have been forgotten.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
329 }