/* =========================================================================== * Initialize a new block. */local void init_block(s)    deflate_state *s;{    int n; /* iterates over tree elements */    /* Initialize the trees. */    for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;    for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;    for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;    s->dyn_ltree[END_BLOCK].Freq = 1;    s->opt_len = s->static_len = 0L;    s->last_lit = s->matches = 0;}#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(s, tree, top) \{\    top = s->heap[SMALLEST]; \    s->heap[SMALLEST] = s->heap[s->heap_len--]; \    pqdownheap(s, 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, depth) \   (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(s, tree, k)    deflate_state *s;    ct_data *tree;  /* the tree to restore */    int k;               /* node to move down */{    int v = s->heap[k];    int j = k << 1;  /* left son of k */    while (j <= s->heap_len) {        /* Set j to the smallest of the two sons: */        if (j < s->heap_len &&            smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {            j++;        }        /* Exit if v is smaller than both sons */        if (smaller(tree, v, s->heap[j], s->depth)) break;        /* Exchange v with the smallest son */        s->heap[k] = s->heap[j];  k = j;        /* And continue down the tree, setting j to the left son of k */        j <<= 1;    }    s->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(s, desc)    deflate_state *s;    tree_desc *desc;    /* the tree descriptor */{    ct_data *tree        = desc->dyn_tree;    int max_code         = desc->max_code;    const ct_data *stree = desc->stat_desc->static_tree;    const intf *extra    = desc->stat_desc->extra_bits;    int base             = desc->stat_desc->extra_base;    int max_length       = desc->stat_desc->max_length;    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++) s->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[s->heap[s->heap_max]].Len = 0; /* root of the heap */    for (h = s->heap_max+1; h < HEAP_SIZE; h++) {        n = s->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 */        s->bl_count[bits]++;        xbits = 0;        if (n >= base) xbits = extra[n-base];        f = tree[n].Freq;        s->opt_len += (ulg)f * (bits + xbits);        if (stree) s->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 (s->bl_count[bits] == 0) bits--;        s->bl_count[bits]--;      /* move one leaf down the tree */        s->bl_count[bits+1] += 2; /* move one overflow item as its brother */        s->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 = s->bl_count[bits];        while (n != 0) {            m = s->heap[--h];            if (m > max_code) continue;            if ((unsigned) tree[m].Len != (unsigned) bits) {                Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));                s->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, bl_count)    ct_data *tree;             /* the tree to decorate */    int max_code;              /* largest code with non zero frequency */    ushf *bl_count;            /* number of codes at each bit length */{    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);        Tracecv(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(s, desc)    deflate_state *s;    tree_desc *desc; /* the tree descriptor */{    ct_data *tree         = desc->dyn_tree;    const ct_data *stree  = desc->stat_desc->static_tree;    int elems             = desc->stat_desc->elems;    int n, m;          /* iterate over heap elements */    int max_code = -1; /* largest code with non zero frequency */    int node;          /* new node being created */    /* 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.     */    s->heap_len = 0, s->heap_max = HEAP_SIZE;    for (n = 0; n < elems; n++) {        if (tree[n].Freq != 0) {            s->heap[++(s->heap_len)] = max_code = n;            s->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 (s->heap_len < 2) {        node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);        tree[node].Freq = 1;        s->depth[node] = 0;        s->opt_len--; if (stree) s->static_len -= stree[node].Len;        /* node 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 = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);    /* Construct the Huffman tree by repeatedly combining the least two     * frequent nodes.     */    node = elems;              /* next internal node of the tree */    do {        pqremove(s, tree, n);  /* n = node of least frequency */        m = s->heap[SMALLEST]; /* m = node of next least frequency */        s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */        s->heap[--(s->heap_max)] = m;        /* Create a new node father of n and m */        tree[node].Freq = tree[n].Freq + tree[m].Freq;        s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?                                s->depth[n] : s->depth[m]) + 1);        tree[n].Dad = tree[m].Dad = (ush)node;#ifdef DUMP_BL_TREE        if (tree == s->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 */        s->heap[SMALLEST] = node++;        pqdownheap(s, tree, SMALLEST);    } while (s->heap_len >= 2);    s->heap[--(s->heap_max)] = s->heap[SMALLEST];    /* At this point, the fields freq and dad are set. We can now     * generate the bit lengths.     */    gen_bitlen(s, (tree_desc *)desc);    /* The field len is now set, we can generate the bit codes */    gen_codes ((ct_data *)tree, max_code, s->bl_count);}/* =========================================================================== * Scan a literal or distance tree to determine the frequencies of the codes * in the bit length tree. */local void scan_tree (s, tree, max_code)    deflate_state *s;    ct_data *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) {            s->bl_tree[curlen].Freq += count;        } else if (curlen != 0) {            if (curlen != prevlen) s->bl_tree[curlen].Freq++;            s->bl_tree[REP_3_6].Freq++;        } else if (count <= 10) {            s->bl_tree[REPZ_3_10].Freq++;        } else {            s->bl_tree[REPZ_11_138].Freq++;        }        count = 0; prevlen = curlen;        if (nextlen == 0) {            max_count = 138, min_count = 3;        } else if (curlen == nextlen) {            max_count = 6, min_count = 3;        } else {            max_count = 7, min_count = 4;        }    }}/* =========================================================================== * Send a literal or distance tree in compressed form, using the codes in * bl_tree. */local void send_tree (s, tree, max_code)    deflate_state *s;    ct_data *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 */    /* tree[max_code+1].Len = -1; */  /* guard already set */    if (nextlen == 0) max_count = 138, min_count = 3;    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) {            do { send_code(s, curlen, s->bl_tree); } while (--count != 0);        } else if (curlen != 0) {            if (curlen != prevlen) {                send_code(s, curlen, s->bl_tree); count--;            }            Assert(count >= 3 && count <= 6, " 3_6?");            send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);        } else if (count <= 10) {            send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);        } else {            send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);        }        count = 0; prevlen = curlen;        if (nextlen == 0) {            max_count = 138, min_count = 3;        } else if (curlen == nextlen) {            max_count = 6, min_count = 3;        } else {            max_count = 7, min_count = 4;        }    }}/* =========================================================================== * Construct the Huffman tree for the bit lengths and return the index in * bl_order of the last bit length code to send. */local int build_bl_tree(s)    deflate_state *s;{    int max_blindex;  /* index of last bit length code of non zero freq */    /* Determine the bit length frequencies for literal and distance trees */    scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);    scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);    /* Build the bit length tree: */    build_tree(s, (tree_desc *)(&(s->bl_desc)));    /* opt_len now includes the length of the tree representations, except