← Back to branch summary

~ubuntu-branches/ubuntu/saucy/clamav/saucy

« back to all changes in this revision

Viewing changes to win32/3rdparty/zlib/contrib/infback9/inftree9.c

  • Committer: Bazaar Package Importer
  • Author(s): Leonel Nunez
  • Date: 2008-02-11 22:52:13 UTC
  • mfrom: (1.1.6 upstream)
  • mto: This revision was merged to the branch mainline in revision 38.
  • Revision ID: james.westby@ubuntu.com-20080211225213-p2uwj4czso1w2f8h
Tags: upstream-0.92~dfsg
Import upstream version 0.92~dfsg

Show diffs side-by-side

added added

removed removed

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