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