kusano fc6ab3
/* inftree9.c -- generate Huffman trees for efficient decoding
kusano fc6ab3
 * Copyright (C) 1995-2013 Mark Adler
kusano fc6ab3
 * For conditions of distribution and use, see copyright notice in zlib.h
kusano fc6ab3
 */
kusano fc6ab3
kusano fc6ab3
#include "zutil.h"
kusano fc6ab3
#include "inftree9.h"
kusano fc6ab3
kusano fc6ab3
#define MAXBITS 15
kusano fc6ab3
kusano fc6ab3
const char inflate9_copyright[] =
kusano fc6ab3
   " inflate9 1.2.8 Copyright 1995-2013 Mark Adler ";
kusano fc6ab3
/*
kusano fc6ab3
  If you use the zlib library in a product, an acknowledgment is welcome
kusano fc6ab3
  in the documentation of your product. If for some reason you cannot
kusano fc6ab3
  include such an acknowledgment, I would appreciate that you keep this
kusano fc6ab3
  copyright string in the executable of your product.
kusano fc6ab3
 */
kusano fc6ab3
kusano fc6ab3
/*
kusano fc6ab3
   Build a set of tables to decode the provided canonical Huffman code.
kusano fc6ab3
   The code lengths are lens[0..codes-1].  The result starts at *table,
kusano fc6ab3
   whose indices are 0..2^bits-1.  work is a writable array of at least
kusano fc6ab3
   lens shorts, which is used as a work area.  type is the type of code
kusano fc6ab3
   to be generated, CODES, LENS, or DISTS.  On return, zero is success,
kusano fc6ab3
   -1 is an invalid code, and +1 means that ENOUGH isn't enough.  table
kusano fc6ab3
   on return points to the next available entry's address.  bits is the
kusano fc6ab3
   requested root table index bits, and on return it is the actual root
kusano fc6ab3
   table index bits.  It will differ if the request is greater than the
kusano fc6ab3
   longest code or if it is less than the shortest code.
kusano fc6ab3
 */
kusano fc6ab3
int inflate_table9(type, lens, codes, table, bits, work)
kusano fc6ab3
codetype type;
kusano fc6ab3
unsigned short FAR *lens;
kusano fc6ab3
unsigned codes;
kusano fc6ab3
code FAR * FAR *table;
kusano fc6ab3
unsigned FAR *bits;
kusano fc6ab3
unsigned short FAR *work;
kusano fc6ab3
{
kusano fc6ab3
    unsigned len;               /* a code's length in bits */
kusano fc6ab3
    unsigned sym;               /* index of code symbols */
kusano fc6ab3
    unsigned min, max;          /* minimum and maximum code lengths */
kusano fc6ab3
    unsigned root;              /* number of index bits for root table */
kusano fc6ab3
    unsigned curr;              /* number of index bits for current table */
kusano fc6ab3
    unsigned drop;              /* code bits to drop for sub-table */
kusano fc6ab3
    int left;                   /* number of prefix codes available */
kusano fc6ab3
    unsigned used;              /* code entries in table used */
kusano fc6ab3
    unsigned huff;              /* Huffman code */
kusano fc6ab3
    unsigned incr;              /* for incrementing code, index */
kusano fc6ab3
    unsigned fill;              /* index for replicating entries */
kusano fc6ab3
    unsigned low;               /* low bits for current root entry */
kusano fc6ab3
    unsigned mask;              /* mask for low root bits */
kusano fc6ab3
    code this;                  /* table entry for duplication */
kusano fc6ab3
    code FAR *next;             /* next available space in table */
kusano fc6ab3
    const unsigned short FAR *base;     /* base value table to use */
kusano fc6ab3
    const unsigned short FAR *extra;    /* extra bits table to use */
kusano fc6ab3
    int end;                    /* use base and extra for symbol > end */
kusano fc6ab3
    unsigned short count[MAXBITS+1];    /* number of codes of each length */
kusano fc6ab3
    unsigned short offs[MAXBITS+1];     /* offsets in table for each length */
kusano fc6ab3
    static const unsigned short lbase[31] = { /* Length codes 257..285 base */
kusano fc6ab3
        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17,
kusano fc6ab3
        19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115,
kusano fc6ab3
        131, 163, 195, 227, 3, 0, 0};
kusano fc6ab3
    static const unsigned short lext[31] = { /* Length codes 257..285 extra */
kusano fc6ab3
        128, 128, 128, 128, 128, 128, 128, 128, 129, 129, 129, 129,
kusano fc6ab3
        130, 130, 130, 130, 131, 131, 131, 131, 132, 132, 132, 132,
kusano fc6ab3
        133, 133, 133, 133, 144, 72, 78};
kusano fc6ab3
    static const unsigned short dbase[32] = { /* Distance codes 0..31 base */
kusano fc6ab3
        1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49,
kusano fc6ab3
        65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073,
kusano fc6ab3
        4097, 6145, 8193, 12289, 16385, 24577, 32769, 49153};
kusano fc6ab3
    static const unsigned short dext[32] = { /* Distance codes 0..31 extra */
kusano fc6ab3
        128, 128, 128, 128, 129, 129, 130, 130, 131, 131, 132, 132,
kusano fc6ab3
        133, 133, 134, 134, 135, 135, 136, 136, 137, 137, 138, 138,
kusano fc6ab3
        139, 139, 140, 140, 141, 141, 142, 142};
kusano fc6ab3
kusano fc6ab3
    /*
kusano fc6ab3
       Process a set of code lengths to create a canonical Huffman code.  The
kusano fc6ab3
       code lengths are lens[0..codes-1].  Each length corresponds to the
kusano fc6ab3
       symbols 0..codes-1.  The Huffman code is generated by first sorting the
kusano fc6ab3
       symbols by length from short to long, and retaining the symbol order
kusano fc6ab3
       for codes with equal lengths.  Then the code starts with all zero bits
kusano fc6ab3
       for the first code of the shortest length, and the codes are integer
kusano fc6ab3
       increments for the same length, and zeros are appended as the length
kusano fc6ab3
       increases.  For the deflate format, these bits are stored backwards
kusano fc6ab3
       from their more natural integer increment ordering, and so when the
kusano fc6ab3
       decoding tables are built in the large loop below, the integer codes
kusano fc6ab3
       are incremented backwards.
kusano fc6ab3
kusano fc6ab3
       This routine assumes, but does not check, that all of the entries in
kusano fc6ab3
       lens[] are in the range 0..MAXBITS.  The caller must assure this.
kusano fc6ab3
       1..MAXBITS is interpreted as that code length.  zero means that that
kusano fc6ab3
       symbol does not occur in this code.
kusano fc6ab3
kusano fc6ab3
       The codes are sorted by computing a count of codes for each length,
kusano fc6ab3
       creating from that a table of starting indices for each length in the
kusano fc6ab3
       sorted table, and then entering the symbols in order in the sorted
kusano fc6ab3
       table.  The sorted table is work[], with that space being provided by
kusano fc6ab3
       the caller.
kusano fc6ab3
kusano fc6ab3
       The length counts are used for other purposes as well, i.e. finding
kusano fc6ab3
       the minimum and maximum length codes, determining if there are any
kusano fc6ab3
       codes at all, checking for a valid set of lengths, and looking ahead
kusano fc6ab3
       at length counts to determine sub-table sizes when building the
kusano fc6ab3
       decoding tables.
kusano fc6ab3
     */
kusano fc6ab3
kusano fc6ab3
    /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
kusano fc6ab3
    for (len = 0; len <= MAXBITS; len++)
kusano fc6ab3
        count[len] = 0;
kusano fc6ab3
    for (sym = 0; sym < codes; sym++)
kusano fc6ab3
        count[lens[sym]]++;
kusano fc6ab3
kusano fc6ab3
    /* bound code lengths, force root to be within code lengths */
kusano fc6ab3
    root = *bits;
kusano fc6ab3
    for (max = MAXBITS; max >= 1; max--)
kusano fc6ab3
        if (count[max] != 0) break;
kusano fc6ab3
    if (root > max) root = max;
kusano fc6ab3
    if (max == 0) return -1;            /* no codes! */
kusano fc6ab3
    for (min = 1; min <= MAXBITS; min++)
kusano fc6ab3
        if (count[min] != 0) break;
kusano fc6ab3
    if (root < min) root = min;
kusano fc6ab3
kusano fc6ab3
    /* check for an over-subscribed or incomplete set of lengths */
kusano fc6ab3
    left = 1;
kusano fc6ab3
    for (len = 1; len <= MAXBITS; len++) {
kusano fc6ab3
        left <<= 1;
kusano fc6ab3
        left -= count[len];
kusano fc6ab3
        if (left < 0) return -1;        /* over-subscribed */
kusano fc6ab3
    }
kusano fc6ab3
    if (left > 0 && (type == CODES || max != 1))
kusano fc6ab3
        return -1;                      /* incomplete set */
kusano fc6ab3
kusano fc6ab3
    /* generate offsets into symbol table for each length for sorting */
kusano fc6ab3
    offs[1] = 0;
kusano fc6ab3
    for (len = 1; len < MAXBITS; len++)
kusano fc6ab3
        offs[len + 1] = offs[len] + count[len];
kusano fc6ab3
kusano fc6ab3
    /* sort symbols by length, by symbol order within each length */
kusano fc6ab3
    for (sym = 0; sym < codes; sym++)
kusano fc6ab3
        if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
kusano fc6ab3
kusano fc6ab3
    /*
kusano fc6ab3
       Create and fill in decoding tables.  In this loop, the table being
kusano fc6ab3
       filled is at next and has curr index bits.  The code being used is huff
kusano fc6ab3
       with length len.  That code is converted to an index by dropping drop
kusano fc6ab3
       bits off of the bottom.  For codes where len is less than drop + curr,
kusano fc6ab3
       those top drop + curr - len bits are incremented through all values to
kusano fc6ab3
       fill the table with replicated entries.
kusano fc6ab3
kusano fc6ab3
       root is the number of index bits for the root table.  When len exceeds
kusano fc6ab3
       root, sub-tables are created pointed to by the root entry with an index
kusano fc6ab3
       of the low root bits of huff.  This is saved in low to check for when a
kusano fc6ab3
       new sub-table should be started.  drop is zero when the root table is
kusano fc6ab3
       being filled, and drop is root when sub-tables are being filled.
kusano fc6ab3
kusano fc6ab3
       When a new sub-table is needed, it is necessary to look ahead in the
kusano fc6ab3
       code lengths to determine what size sub-table is needed.  The length
kusano fc6ab3
       counts are used for this, and so count[] is decremented as codes are
kusano fc6ab3
       entered in the tables.
kusano fc6ab3
kusano fc6ab3
       used keeps track of how many table entries have been allocated from the
kusano fc6ab3
       provided *table space.  It is checked for LENS and DIST tables against
kusano fc6ab3
       the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in
kusano fc6ab3
       the initial root table size constants.  See the comments in inftree9.h
kusano fc6ab3
       for more information.
kusano fc6ab3
kusano fc6ab3
       sym increments through all symbols, and the loop terminates when
kusano fc6ab3
       all codes of length max, i.e. all codes, have been processed.  This
kusano fc6ab3
       routine permits incomplete codes, so another loop after this one fills
kusano fc6ab3
       in the rest of the decoding tables with invalid code markers.
kusano fc6ab3
     */
kusano fc6ab3
kusano fc6ab3
    /* set up for code type */
kusano fc6ab3
    switch (type) {
kusano fc6ab3
    case CODES:
kusano fc6ab3
        base = extra = work;    /* dummy value--not used */
kusano fc6ab3
        end = 19;
kusano fc6ab3
        break;
kusano fc6ab3
    case LENS:
kusano fc6ab3
        base = lbase;
kusano fc6ab3
        base -= 257;
kusano fc6ab3
        extra = lext;
kusano fc6ab3
        extra -= 257;
kusano fc6ab3
        end = 256;
kusano fc6ab3
        break;
kusano fc6ab3
    default:            /* DISTS */
kusano fc6ab3
        base = dbase;
kusano fc6ab3
        extra = dext;
kusano fc6ab3
        end = -1;
kusano fc6ab3
    }
kusano fc6ab3
kusano fc6ab3
    /* initialize state for loop */
kusano fc6ab3
    huff = 0;                   /* starting code */
kusano fc6ab3
    sym = 0;                    /* starting code symbol */
kusano fc6ab3
    len = min;                  /* starting code length */
kusano fc6ab3
    next = *table;              /* current table to fill in */
kusano fc6ab3
    curr = root;                /* current table index bits */
kusano fc6ab3
    drop = 0;                   /* current bits to drop from code for index */
kusano fc6ab3
    low = (unsigned)(-1);       /* trigger new sub-table when len > root */
kusano fc6ab3
    used = 1U << root;          /* use root table entries */
kusano fc6ab3
    mask = used - 1;            /* mask for comparing low */
kusano fc6ab3
kusano fc6ab3
    /* check available table space */
kusano fc6ab3
    if ((type == LENS && used >= ENOUGH_LENS) ||
kusano fc6ab3
        (type == DISTS && used >= ENOUGH_DISTS))
kusano fc6ab3
        return 1;
kusano fc6ab3
kusano fc6ab3
    /* process all codes and make table entries */
kusano fc6ab3
    for (;;) {
kusano fc6ab3
        /* create table entry */
kusano fc6ab3
        this.bits = (unsigned char)(len - drop);
kusano fc6ab3
        if ((int)(work[sym]) < end) {
kusano fc6ab3
            this.op = (unsigned char)0;
kusano fc6ab3
            this.val = work[sym];
kusano fc6ab3
        }
kusano fc6ab3
        else if ((int)(work[sym]) > end) {
kusano fc6ab3
            this.op = (unsigned char)(extra[work[sym]]);
kusano fc6ab3
            this.val = base[work[sym]];
kusano fc6ab3
        }
kusano fc6ab3
        else {
kusano fc6ab3
            this.op = (unsigned char)(32 + 64);         /* end of block */
kusano fc6ab3
            this.val = 0;
kusano fc6ab3
        }
kusano fc6ab3
kusano fc6ab3
        /* replicate for those indices with low len bits equal to huff */
kusano fc6ab3
        incr = 1U << (len - drop);
kusano fc6ab3
        fill = 1U << curr;
kusano fc6ab3
        do {
kusano fc6ab3
            fill -= incr;
kusano fc6ab3
            next[(huff >> drop) + fill] = this;
kusano fc6ab3
        } while (fill != 0);
kusano fc6ab3
kusano fc6ab3
        /* backwards increment the len-bit code huff */
kusano fc6ab3
        incr = 1U << (len - 1);
kusano fc6ab3
        while (huff & incr)
kusano fc6ab3
            incr >>= 1;
kusano fc6ab3
        if (incr != 0) {
kusano fc6ab3
            huff &= incr - 1;
kusano fc6ab3
            huff += incr;
kusano fc6ab3
        }
kusano fc6ab3
        else
kusano fc6ab3
            huff = 0;
kusano fc6ab3
kusano fc6ab3
        /* go to next symbol, update count, len */
kusano fc6ab3
        sym++;
kusano fc6ab3
        if (--(count[len]) == 0) {
kusano fc6ab3
            if (len == max) break;
kusano fc6ab3
            len = lens[work[sym]];
kusano fc6ab3
        }
kusano fc6ab3
kusano fc6ab3
        /* create new sub-table if needed */
kusano fc6ab3
        if (len > root && (huff & mask) != low) {
kusano fc6ab3
            /* if first time, transition to sub-tables */
kusano fc6ab3
            if (drop == 0)
kusano fc6ab3
                drop = root;
kusano fc6ab3
kusano fc6ab3
            /* increment past last table */
kusano fc6ab3
            next += 1U << curr;
kusano fc6ab3
kusano fc6ab3
            /* determine length of next table */
kusano fc6ab3
            curr = len - drop;
kusano fc6ab3
            left = (int)(1 << curr);
kusano fc6ab3
            while (curr + drop < max) {
kusano fc6ab3
                left -= count[curr + drop];
kusano fc6ab3
                if (left <= 0) break;
kusano fc6ab3
                curr++;
kusano fc6ab3
                left <<= 1;
kusano fc6ab3
            }
kusano fc6ab3
kusano fc6ab3
            /* check for enough space */
kusano fc6ab3
            used += 1U << curr;
kusano fc6ab3
            if ((type == LENS && used >= ENOUGH_LENS) ||
kusano fc6ab3
                (type == DISTS && used >= ENOUGH_DISTS))
kusano fc6ab3
                return 1;
kusano fc6ab3
kusano fc6ab3
            /* point entry in root table to sub-table */
kusano fc6ab3
            low = huff & mask;
kusano fc6ab3
            (*table)[low].op = (unsigned char)curr;
kusano fc6ab3
            (*table)[low].bits = (unsigned char)root;
kusano fc6ab3
            (*table)[low].val = (unsigned short)(next - *table);
kusano fc6ab3
        }
kusano fc6ab3
    }
kusano fc6ab3
kusano fc6ab3
    /*
kusano fc6ab3
       Fill in rest of table for incomplete codes.  This loop is similar to the
kusano fc6ab3
       loop above in incrementing huff for table indices.  It is assumed that
kusano fc6ab3
       len is equal to curr + drop, so there is no loop needed to increment
kusano fc6ab3
       through high index bits.  When the current sub-table is filled, the loop
kusano fc6ab3
       drops back to the root table to fill in any remaining entries there.
kusano fc6ab3
     */
kusano fc6ab3
    this.op = (unsigned char)64;                /* invalid code marker */
kusano fc6ab3
    this.bits = (unsigned char)(len - drop);
kusano fc6ab3
    this.val = (unsigned short)0;
kusano fc6ab3
    while (huff != 0) {
kusano fc6ab3
        /* when done with sub-table, drop back to root table */
kusano fc6ab3
        if (drop != 0 && (huff & mask) != low) {
kusano fc6ab3
            drop = 0;
kusano fc6ab3
            len = root;
kusano fc6ab3
            next = *table;
kusano fc6ab3
            curr = root;
kusano fc6ab3
            this.bits = (unsigned char)len;
kusano fc6ab3
        }
kusano fc6ab3
kusano fc6ab3
        /* put invalid code marker in table */
kusano fc6ab3
        next[huff >> drop] = this;
kusano fc6ab3
kusano fc6ab3
        /* backwards increment the len-bit code huff */
kusano fc6ab3
        incr = 1U << (len - 1);
kusano fc6ab3
        while (huff & incr)
kusano fc6ab3
            incr >>= 1;
kusano fc6ab3
        if (incr != 0) {
kusano fc6ab3
            huff &= incr - 1;
kusano fc6ab3
            huff += incr;
kusano fc6ab3
        }
kusano fc6ab3
        else
kusano fc6ab3
            huff = 0;
kusano fc6ab3
    }
kusano fc6ab3
kusano fc6ab3
    /* set return parameters */
kusano fc6ab3
    *table += used;
kusano fc6ab3
    *bits = root;
kusano fc6ab3
    return 0;
kusano fc6ab3
}