1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/zlib/inftrees.c	Thu Sep 08 06:28:38 2011 +0300
     1.3 @@ -0,0 +1,329 @@
     1.4 +/* inftrees.c -- generate Huffman trees for efficient decoding
     1.5 + * Copyright (C) 1995-2005 Mark Adler
     1.6 + * For conditions of distribution and use, see copyright notice in zlib.h
     1.7 + */
     1.8 +
     1.9 +#include "zutil.h"
    1.10 +#include "inftrees.h"
    1.11 +
    1.12 +#define MAXBITS 15
    1.13 +
    1.14 +const char inflate_copyright[] =
    1.15 +   " inflate 1.2.3 Copyright 1995-2005 Mark Adler ";
    1.16 +/*
    1.17 +  If you use the zlib library in a product, an acknowledgment is welcome
    1.18 +  in the documentation of your product. If for some reason you cannot
    1.19 +  include such an acknowledgment, I would appreciate that you keep this
    1.20 +  copyright string in the executable of your product.
    1.21 + */
    1.22 +
    1.23 +/*
    1.24 +   Build a set of tables to decode the provided canonical Huffman code.
    1.25 +   The code lengths are lens[0..codes-1].  The result starts at *table,
    1.26 +   whose indices are 0..2^bits-1.  work is a writable array of at least
    1.27 +   lens shorts, which is used as a work area.  type is the type of code
    1.28 +   to be generated, CODES, LENS, or DISTS.  On return, zero is success,
    1.29 +   -1 is an invalid code, and +1 means that ENOUGH isn't enough.  table
    1.30 +   on return points to the next available entry's address.  bits is the
    1.31 +   requested root table index bits, and on return it is the actual root
    1.32 +   table index bits.  It will differ if the request is greater than the
    1.33 +   longest code or if it is less than the shortest code.
    1.34 + */
    1.35 +int inflate_table(type, lens, codes, table, bits, work)
    1.36 +codetype type;
    1.37 +unsigned short FAR *lens;
    1.38 +unsigned codes;
    1.39 +code FAR * FAR *table;
    1.40 +unsigned FAR *bits;
    1.41 +unsigned short FAR *work;
    1.42 +{
    1.43 +    unsigned len;               /* a code's length in bits */
    1.44 +    unsigned sym;               /* index of code symbols */
    1.45 +    unsigned min, max;          /* minimum and maximum code lengths */
    1.46 +    unsigned root;              /* number of index bits for root table */
    1.47 +    unsigned curr;              /* number of index bits for current table */
    1.48 +    unsigned drop;              /* code bits to drop for sub-table */
    1.49 +    int left;                   /* number of prefix codes available */
    1.50 +    unsigned used;              /* code entries in table used */
    1.51 +    unsigned huff;              /* Huffman code */
    1.52 +    unsigned incr;              /* for incrementing code, index */
    1.53 +    unsigned fill;              /* index for replicating entries */
    1.54 +    unsigned low;               /* low bits for current root entry */
    1.55 +    unsigned mask;              /* mask for low root bits */
    1.56 +    code this;                  /* table entry for duplication */
    1.57 +    code FAR *next;             /* next available space in table */
    1.58 +    const unsigned short FAR *base;     /* base value table to use */
    1.59 +    const unsigned short FAR *extra;    /* extra bits table to use */
    1.60 +    int end;                    /* use base and extra for symbol > end */
    1.61 +    unsigned short count[MAXBITS+1];    /* number of codes of each length */
    1.62 +    unsigned short offs[MAXBITS+1];     /* offsets in table for each length */
    1.63 +    static const unsigned short lbase[31] = { /* Length codes 257..285 base */
    1.64 +        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
    1.65 +        35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
    1.66 +    static const unsigned short lext[31] = { /* Length codes 257..285 extra */
    1.67 +        16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
    1.68 +        19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
    1.69 +    static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
    1.70 +        1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
    1.71 +        257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
    1.72 +        8193, 12289, 16385, 24577, 0, 0};
    1.73 +    static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
    1.74 +        16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
    1.75 +        23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
    1.76 +        28, 28, 29, 29, 64, 64};
    1.77 +
    1.78 +    /*
    1.79 +       Process a set of code lengths to create a canonical Huffman code.  The
    1.80 +       code lengths are lens[0..codes-1].  Each length corresponds to the
    1.81 +       symbols 0..codes-1.  The Huffman code is generated by first sorting the
    1.82 +       symbols by length from short to long, and retaining the symbol order
    1.83 +       for codes with equal lengths.  Then the code starts with all zero bits
    1.84 +       for the first code of the shortest length, and the codes are integer
    1.85 +       increments for the same length, and zeros are appended as the length
    1.86 +       increases.  For the deflate format, these bits are stored backwards
    1.87 +       from their more natural integer increment ordering, and so when the
    1.88 +       decoding tables are built in the large loop below, the integer codes
    1.89 +       are incremented backwards.
    1.90 +
    1.91 +       This routine assumes, but does not check, that all of the entries in
    1.92 +       lens[] are in the range 0..MAXBITS.  The caller must assure this.
    1.93 +       1..MAXBITS is interpreted as that code length.  zero means that that
    1.94 +       symbol does not occur in this code.
    1.95 +
    1.96 +       The codes are sorted by computing a count of codes for each length,
    1.97 +       creating from that a table of starting indices for each length in the
    1.98 +       sorted table, and then entering the symbols in order in the sorted
    1.99 +       table.  The sorted table is work[], with that space being provided by
   1.100 +       the caller.
   1.101 +
   1.102 +       The length counts are used for other purposes as well, i.e. finding
   1.103 +       the minimum and maximum length codes, determining if there are any
   1.104 +       codes at all, checking for a valid set of lengths, and looking ahead
   1.105 +       at length counts to determine sub-table sizes when building the
   1.106 +       decoding tables.
   1.107 +     */
   1.108 +
   1.109 +    /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
   1.110 +    for (len = 0; len <= MAXBITS; len++)
   1.111 +        count[len] = 0;
   1.112 +    for (sym = 0; sym < codes; sym++)
   1.113 +        count[lens[sym]]++;
   1.114 +
   1.115 +    /* bound code lengths, force root to be within code lengths */
   1.116 +    root = *bits;
   1.117 +    for (max = MAXBITS; max >= 1; max--)
   1.118 +        if (count[max] != 0) break;
   1.119 +    if (root > max) root = max;
   1.120 +    if (max == 0) {                     /* no symbols to code at all */
   1.121 +        this.op = (unsigned char)64;    /* invalid code marker */
   1.122 +        this.bits = (unsigned char)1;
   1.123 +        this.val = (unsigned short)0;
   1.124 +        *(*table)++ = this;             /* make a table to force an error */
   1.125 +        *(*table)++ = this;
   1.126 +        *bits = 1;
   1.127 +        return 0;     /* no symbols, but wait for decoding to report error */
   1.128 +    }
   1.129 +    for (min = 1; min <= MAXBITS; min++)
   1.130 +        if (count[min] != 0) break;
   1.131 +    if (root < min) root = min;
   1.132 +
   1.133 +    /* check for an over-subscribed or incomplete set of lengths */
   1.134 +    left = 1;
   1.135 +    for (len = 1; len <= MAXBITS; len++) {
   1.136 +        left <<= 1;
   1.137 +        left -= count[len];
   1.138 +        if (left < 0) return -1;        /* over-subscribed */
   1.139 +    }
   1.140 +    if (left > 0 && (type == CODES || max != 1))
   1.141 +        return -1;                      /* incomplete set */
   1.142 +
   1.143 +    /* generate offsets into symbol table for each length for sorting */
   1.144 +    offs[1] = 0;
   1.145 +    for (len = 1; len < MAXBITS; len++)
   1.146 +        offs[len + 1] = offs[len] + count[len];
   1.147 +
   1.148 +    /* sort symbols by length, by symbol order within each length */
   1.149 +    for (sym = 0; sym < codes; sym++)
   1.150 +        if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
   1.151 +
   1.152 +    /*
   1.153 +       Create and fill in decoding tables.  In this loop, the table being
   1.154 +       filled is at next and has curr index bits.  The code being used is huff
   1.155 +       with length len.  That code is converted to an index by dropping drop
   1.156 +       bits off of the bottom.  For codes where len is less than drop + curr,
   1.157 +       those top drop + curr - len bits are incremented through all values to
   1.158 +       fill the table with replicated entries.
   1.159 +
   1.160 +       root is the number of index bits for the root table.  When len exceeds
   1.161 +       root, sub-tables are created pointed to by the root entry with an index
   1.162 +       of the low root bits of huff.  This is saved in low to check for when a
   1.163 +       new sub-table should be started.  drop is zero when the root table is
   1.164 +       being filled, and drop is root when sub-tables are being filled.
   1.165 +
   1.166 +       When a new sub-table is needed, it is necessary to look ahead in the
   1.167 +       code lengths to determine what size sub-table is needed.  The length
   1.168 +       counts are used for this, and so count[] is decremented as codes are
   1.169 +       entered in the tables.
   1.170 +
   1.171 +       used keeps track of how many table entries have been allocated from the
   1.172 +       provided *table space.  It is checked when a LENS table is being made
   1.173 +       against the space in *table, ENOUGH, minus the maximum space needed by
   1.174 +       the worst case distance code, MAXD.  This should never happen, but the
   1.175 +       sufficiency of ENOUGH has not been proven exhaustively, hence the check.
   1.176 +       This assumes that when type == LENS, bits == 9.
   1.177 +
   1.178 +       sym increments through all symbols, and the loop terminates when
   1.179 +       all codes of length max, i.e. all codes, have been processed.  This
   1.180 +       routine permits incomplete codes, so another loop after this one fills
   1.181 +       in the rest of the decoding tables with invalid code markers.
   1.182 +     */
   1.183 +
   1.184 +    /* set up for code type */
   1.185 +    switch (type) {
   1.186 +    case CODES:
   1.187 +        base = extra = work;    /* dummy value--not used */
   1.188 +        end = 19;
   1.189 +        break;
   1.190 +    case LENS:
   1.191 +        base = lbase;
   1.192 +        base -= 257;
   1.193 +        extra = lext;
   1.194 +        extra -= 257;
   1.195 +        end = 256;
   1.196 +        break;
   1.197 +    default:            /* DISTS */
   1.198 +        base = dbase;
   1.199 +        extra = dext;
   1.200 +        end = -1;
   1.201 +    }
   1.202 +
   1.203 +    /* initialize state for loop */
   1.204 +    huff = 0;                   /* starting code */
   1.205 +    sym = 0;                    /* starting code symbol */
   1.206 +    len = min;                  /* starting code length */
   1.207 +    next = *table;              /* current table to fill in */
   1.208 +    curr = root;                /* current table index bits */
   1.209 +    drop = 0;                   /* current bits to drop from code for index */
   1.210 +    low = (unsigned)(-1);       /* trigger new sub-table when len > root */
   1.211 +    used = 1U << root;          /* use root table entries */
   1.212 +    mask = used - 1;            /* mask for comparing low */
   1.213 +
   1.214 +    /* check available table space */
   1.215 +    if (type == LENS && used >= ENOUGH - MAXD)
   1.216 +        return 1;
   1.217 +
   1.218 +    /* process all codes and make table entries */
   1.219 +    for (;;) {
   1.220 +        /* create table entry */
   1.221 +        this.bits = (unsigned char)(len - drop);
   1.222 +        if ((int)(work[sym]) < end) {
   1.223 +            this.op = (unsigned char)0;
   1.224 +            this.val = work[sym];
   1.225 +        }
   1.226 +        else if ((int)(work[sym]) > end) {
   1.227 +            this.op = (unsigned char)(extra[work[sym]]);
   1.228 +            this.val = base[work[sym]];
   1.229 +        }
   1.230 +        else {
   1.231 +            this.op = (unsigned char)(32 + 64);         /* end of block */
   1.232 +            this.val = 0;
   1.233 +        }
   1.234 +
   1.235 +        /* replicate for those indices with low len bits equal to huff */
   1.236 +        incr = 1U << (len - drop);
   1.237 +        fill = 1U << curr;
   1.238 +        min = fill;                 /* save offset to next table */
   1.239 +        do {
   1.240 +            fill -= incr;
   1.241 +            next[(huff >> drop) + fill] = this;
   1.242 +        } while (fill != 0);
   1.243 +
   1.244 +        /* backwards increment the len-bit code huff */
   1.245 +        incr = 1U << (len - 1);
   1.246 +        while (huff & incr)
   1.247 +            incr >>= 1;
   1.248 +        if (incr != 0) {
   1.249 +            huff &= incr - 1;
   1.250 +            huff += incr;
   1.251 +        }
   1.252 +        else
   1.253 +            huff = 0;
   1.254 +
   1.255 +        /* go to next symbol, update count, len */
   1.256 +        sym++;
   1.257 +        if (--(count[len]) == 0) {
   1.258 +            if (len == max) break;
   1.259 +            len = lens[work[sym]];
   1.260 +        }
   1.261 +
   1.262 +        /* create new sub-table if needed */
   1.263 +        if (len > root && (huff & mask) != low) {
   1.264 +            /* if first time, transition to sub-tables */
   1.265 +            if (drop == 0)
   1.266 +                drop = root;
   1.267 +
   1.268 +            /* increment past last table */
   1.269 +            next += min;            /* here min is 1 << curr */
   1.270 +
   1.271 +            /* determine length of next table */
   1.272 +            curr = len - drop;
   1.273 +            left = (int)(1 << curr);
   1.274 +            while (curr + drop < max) {
   1.275 +                left -= count[curr + drop];
   1.276 +                if (left <= 0) break;
   1.277 +                curr++;
   1.278 +                left <<= 1;
   1.279 +            }
   1.280 +
   1.281 +            /* check for enough space */
   1.282 +            used += 1U << curr;
   1.283 +            if (type == LENS && used >= ENOUGH - MAXD)
   1.284 +                return 1;
   1.285 +
   1.286 +            /* point entry in root table to sub-table */
   1.287 +            low = huff & mask;
   1.288 +            (*table)[low].op = (unsigned char)curr;
   1.289 +            (*table)[low].bits = (unsigned char)root;
   1.290 +            (*table)[low].val = (unsigned short)(next - *table);
   1.291 +        }
   1.292 +    }
   1.293 +
   1.294 +    /*
   1.295 +       Fill in rest of table for incomplete codes.  This loop is similar to the
   1.296 +       loop above in incrementing huff for table indices.  It is assumed that
   1.297 +       len is equal to curr + drop, so there is no loop needed to increment
   1.298 +       through high index bits.  When the current sub-table is filled, the loop
   1.299 +       drops back to the root table to fill in any remaining entries there.
   1.300 +     */
   1.301 +    this.op = (unsigned char)64;                /* invalid code marker */
   1.302 +    this.bits = (unsigned char)(len - drop);
   1.303 +    this.val = (unsigned short)0;
   1.304 +    while (huff != 0) {
   1.305 +        /* when done with sub-table, drop back to root table */
   1.306 +        if (drop != 0 && (huff & mask) != low) {
   1.307 +            drop = 0;
   1.308 +            len = root;
   1.309 +            next = *table;
   1.310 +            this.bits = (unsigned char)len;
   1.311 +        }
   1.312 +
   1.313 +        /* put invalid code marker in table */
   1.314 +        next[huff >> drop] = this;
   1.315 +
   1.316 +        /* backwards increment the len-bit code huff */
   1.317 +        incr = 1U << (len - 1);
   1.318 +        while (huff & incr)
   1.319 +            incr >>= 1;
   1.320 +        if (incr != 0) {
   1.321 +            huff &= incr - 1;
   1.322 +            huff += incr;
   1.323 +        }
   1.324 +        else
   1.325 +            huff = 0;
   1.326 +    }
   1.327 +
   1.328 +    /* set return parameters */
   1.329 +    *table += used;
   1.330 +    *bits = root;
   1.331 +    return 0;
   1.332 +}