length_code[length-1] = (uch)code;    /* Initialize the mapping dist (0..32K) -> dist code (0..29) */    dist = 0;    for (code = 0 ; code < 16; code++) {        base_dist[code] = dist;        for (n = 0; n < (1<<extra_dbits[code]); n++) {            dist_code[dist++] = (uch)code;        }    }    Assert (dist == 256, "ct_init: dist != 256");    dist >>= 7; /* from now on, all distances are divided by 128 */    for ( ; code < D_CODES; code++) {        base_dist[code] = dist << 7;        for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {            dist_code[256 + dist++] = (uch)code;        }    }    Assert (dist == 256, "ct_init: 256+dist != 512");    /* Construct the codes of the static literal tree */    for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;    n = 0;    while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;    while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;    while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;    while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;    /* Codes 286 and 287 do not exist, but we must include them in the     * tree construction to get a canonical Huffman tree (longest code     * all ones)     */    gen_codes((ct_data near *)static_ltree, L_CODES+1);    /* The static distance tree is trivial: */    for (n = 0; n < D_CODES; n++) {        static_dtree[n].Len = 5;        static_dtree[n].Code = bi_reverse(n, 5);    }    /* Initialize the first block of the first file: */    init_block();}/* =========================================================================== * Initialize a new block. */local void init_block(){    int n; /* iterates over tree elements */    /* Initialize the trees. */    for (n = 0; n < L_CODES;  n++) dyn_ltree[n].Freq = 0;    for (n = 0; n < D_CODES;  n++) dyn_dtree[n].Freq = 0;    for (n = 0; n < BL_CODES; n++) bl_tree[n].Freq = 0;    dyn_ltree[END_BLOCK].Freq = 1;    opt_len = static_len = 0L;    last_lit = last_dist = last_flags = 0;    flags = 0; flag_bit = 1;}#define SMALLEST 1/* Index within the heap array of least frequent node in the Huffman tree *//* =========================================================================== * Remove the smallest element from the heap and recreate the heap with * one less element. Updates heap and heap_len. */#define pqremove(tree, top) \{\    top = heap[SMALLEST]; \    heap[SMALLEST] = heap[heap_len--]; \    pqdownheap(tree, SMALLEST); \}/* =========================================================================== * Compares to subtrees, using the tree depth as tie breaker when * the subtrees have equal frequency. This minimizes the worst case length. */#define smaller(tree, n, m) \   (tree[n].Freq < tree[m].Freq || \   (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))/* =========================================================================== * Restore the heap property by moving down the tree starting at node k, * exchanging a node with the smallest of its two sons if necessary, stopping * when the heap property is re-established (each father smaller than its * two sons). */local void pqdownheap(tree, k)    ct_data near *tree;  /* the tree to restore */    int k;               /* node to move down */{    int v = heap[k];    int j = k << 1;  /* left son of k */    while (j <= heap_len) {        /* Set j to the smallest of the two sons: */        if (j < heap_len && smaller(tree, heap[j+1], heap[j])) j++;        /* Exit if v is smaller than both sons */        if (smaller(tree, v, heap[j])) break;        /* Exchange v with the smallest son */        heap[k] = heap[j];  k = j;        /* And continue down the tree, setting j to the left son of k */        j <<= 1;    }    heap[k] = v;}/* =========================================================================== * Compute the optimal bit lengths for a tree and update the total bit length * for the current block. * IN assertion: the fields freq and dad are set, heap[heap_max] and *    above are the tree nodes sorted by increasing frequency. * OUT assertions: the field len is set to the optimal bit length, the *     array bl_count contains the frequencies for each bit length. *     The length opt_len is updated; static_len is also updated if stree is *     not null. */local void gen_bitlen(desc)    tree_desc near *desc; /* the tree descriptor */{    ct_data near *tree  = desc->dyn_tree;    int near *extra     = desc->extra_bits;    int base            = desc->extra_base;    int max_code        = desc->max_code;    int max_length      = desc->max_length;    ct_data near *stree = desc->static_tree;    int h;              /* heap index */    int n, m;           /* iterate over the tree elements */    int bits;           /* bit length */    int xbits;          /* extra bits */    ush f;              /* frequency */    int overflow = 0;   /* number of elements with bit length too large */    for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;    /* In a first pass, compute the optimal bit lengths (which may     * overflow in the case of the bit length tree).     */    tree[heap[heap_max]].Len = 0; /* root of the heap */    for (h = heap_max+1; h < HEAP_SIZE; h++) {        n = heap[h];        bits = tree[tree[n].Dad].Len + 1;        if (bits > max_length) bits = max_length, overflow++;        tree[n].Len = (ush)bits;        /* We overwrite tree[n].Dad which is no longer needed */        if (n > max_code) continue; /* not a leaf node */        bl_count[bits]++;        xbits = 0;        if (n >= base) xbits = extra[n-base];        f = tree[n].Freq;        opt_len += (ulg)f * (bits + xbits);        if (stree) static_len += (ulg)f * (stree[n].Len + xbits);    }    if (overflow == 0) return;    Trace((stderr,"\nbit length overflow\n"));    /* This happens for example on obj2 and pic of the Calgary corpus */    /* Find the first bit length which could increase: */    do {        bits = max_length-1;        while (bl_count[bits] == 0) bits--;        bl_count[bits]--;      /* move one leaf down the tree */        bl_count[bits+1] += 2; /* move one overflow item as its brother */        bl_count[max_length]--;        /* The brother of the overflow item also moves one step up,         * but this does not affect bl_count[max_length]         */        overflow -= 2;    } while (overflow > 0);    /* Now recompute all bit lengths, scanning in increasing frequency.     * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all     * lengths instead of fixing only the wrong ones. This idea is taken     * from 'ar' written by Haruhiko Okumura.)     */    for (bits = max_length; bits != 0; bits--) {        n = bl_count[bits];        while (n != 0) {            m = heap[--h];            if (m > max_code) continue;            if (tree[m].Len != (unsigned) bits) {                Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));                opt_len += ((long)bits-(long)tree[m].Len)*(long)tree[m].Freq;                tree[m].Len = (ush)bits;            }            n--;        }    }}/* =========================================================================== * Generate the codes for a given tree and bit counts (which need not be * optimal). * IN assertion: the array bl_count contains the bit length statistics for * the given tree and the field len is set for all tree elements. * OUT assertion: the field code is set for all tree elements of non *     zero code length. */local void gen_codes (tree, max_code)    ct_data near *tree;        /* the tree to decorate */    int max_code;              /* largest code with non zero frequency */{    ush next_code[MAX_BITS+1]; /* next code value for each bit length */    ush code = 0;              /* running code value */    int bits;                  /* bit index */    int n;                     /* code index */    /* The distribution counts are first used to generate the code values     * without bit reversal.     */    for (bits = 1; bits <= MAX_BITS; bits++) {        next_code[bits] = code = (code + bl_count[bits-1]) << 1;    }    /* Check that the bit counts in bl_count are consistent. The last code     * must be all ones.     */    Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,            "inconsistent bit counts");    Tracev((stderr,"\ngen_codes: max_code %d ", max_code));    for (n = 0;  n <= max_code; n++) {        int len = tree[n].Len;        if (len == 0) continue;        /* Now reverse the bits */        tree[n].Code = bi_reverse(next_code[len]++, len);        Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",             n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));    }}/* =========================================================================== * Construct one Huffman tree and assigns the code bit strings and lengths. * Update the total bit length for the current block. * IN assertion: the field freq is set for all tree elements. * OUT assertions: the fields len and code are set to the optimal bit length *     and corresponding code. The length opt_len is updated; static_len is *     also updated if stree is not null. The field max_code is set. */local void build_tree(desc)    tree_desc near *desc; /* the tree descriptor */{    ct_data near *tree   = desc->dyn_tree;    ct_data near *stree  = desc->static_tree;    int elems            = desc->elems;    int n, m;          /* iterate over heap elements */    int max_code = -1; /* largest code with non zero frequency */    int node = elems;  /* next internal node of the tree */    /* Construct the initial heap, with least frequent element in     * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].     * heap[0] is not used.     */    heap_len = 0, heap_max = HEAP_SIZE;    for (n = 0; n < elems; n++) {        if (tree[n].Freq != 0) {            heap[++heap_len] = max_code = n;            depth[n] = 0;        } else {            tree[n].Len = 0;        }    }    /* The pkzip format requires that at least one distance code exists,     * and that at least one bit should be sent even if there is only one     * possible code. So to avoid special checks later on we force at least     * two codes of non zero frequency.     */    while (heap_len < 2) {        int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0);        tree[new].Freq = 1;        depth[new] = 0;        opt_len--; if (stree) static_len -= stree[new].Len;        /* new is 0 or 1 so it does not have extra bits */    }    desc->max_code = max_code;    /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,     * establish sub-heaps of increasing lengths:     */    for (n = heap_len/2; n >= 1; n--) pqdownheap(tree, n);    /* Construct the Huffman tree by repeatedly combining the least two     * frequent nodes.     */    do {        pqremove(tree, n);   /* n = node of least frequency */        m = heap[SMALLEST];  /* m = node of next least frequency */        heap[--heap_max] = n; /* keep the nodes sorted by frequency */        heap[--heap_max] = m;        /* Create a new node father of n and m */        tree[node].Freq = tree[n].Freq + tree[m].Freq;        depth[node] = (uch) (MAX(depth[n], depth[m]) + 1);        tree[n].Dad = tree[m].Dad = (ush)node;#ifdef DUMP_BL_TREE        if (tree == bl_tree) {            fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",                    node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);        }#endif        /* and insert the new node in the heap */        heap[SMALLEST] = node++;        pqdownheap(tree, SMALLEST);    } while (heap_len >= 2);    heap[--heap_max] = heap[SMALLEST];    /* At this point, the fields freq and dad are set. We can now     * generate the bit lengths.     */    gen_bitlen((tree_desc near *)desc);    /* The field len is now set, we can generate the bit codes */    gen_codes ((ct_data near *)tree, max_code);}/* =========================================================================== * Scan a literal or distance tree to determine the frequencies of the codes * in the bit length tree. Updates opt_len to take into account the repeat * counts. (The contribution of the bit length codes will be added later * during the construction of bl_tree.) */local void scan_tree (tree, max_code)    ct_data near *tree; /* the tree to be scanned */    int max_code;       /* and its largest code of non zero frequency */{    int n;                     /* iterates over all tree elements */    int prevlen = -1;          /* last emitted length */    int curlen;                /* length of current code */    int nextlen = tree[0].Len; /* length of next code */    int count = 0;             /* repeat count of the current code */    int max_count = 7;         /* max repeat count */    int min_count = 4;         /* min repeat count */    if (nextlen == 0) max_count = 138, min_count = 3;    tree[max_code+1].Len = (ush)0xffff; /* guard */    for (n = 0; n <= max_code; n++) {        curlen = nextlen; nextlen = tree[n+1].Len;        if (++count < max_count && curlen == nextlen) {            continue;        } else if (count < min_count) {            bl_tree[curlen].Freq += count;        } else if (curlen != 0) {            if (curlen != prevlen) bl_tree[curlen].Freq++;            bl_tree[REP_3_6].Freq++;