* the lengths of the bit lengths codes and the 5+5+4 bits for the counts.     */    /* Determine the number of bit length codes to send. The pkzip format     * requires that at least 4 bit length codes be sent. (appnote.txt says     * 3 but the actual value used is 4.)     */    for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {        if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;    }    /* Update opt_len to include the bit length tree and counts */    s->opt_len += 3*(max_blindex+1) + 5+5+4;    Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",            s->opt_len, s->static_len));    return max_blindex;}/* =========================================================================== * Send the header for a block using dynamic Huffman trees: the counts, the * lengths of the bit length codes, the literal tree and the distance tree. * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. */local void send_all_trees(s, lcodes, dcodes, blcodes)    deflate_state *s;    int lcodes, dcodes, blcodes; /* number of codes for each tree */{    int rank;                    /* index in bl_order */    Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");    Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,            "too many codes");    Tracev((stderr, "\nbl counts: "));    send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */    send_bits(s, dcodes-1,   5);    send_bits(s, blcodes-4,  4); /* not -3 as stated in appnote.txt */    for (rank = 0; rank < blcodes; rank++) {        Tracev((stderr, "\nbl code %2d ", bl_order[rank]));        send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);    }    Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));    send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */    Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));    send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */    Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));}/* =========================================================================== * Send a stored block */void _tr_stored_block(s, buf, stored_len, eof)    deflate_state *s;    charf *buf;       /* input block */    ulg stored_len;   /* length of input block */    int eof;          /* true if this is the last block for a file */{    send_bits(s, (STORED_BLOCK<<1)+eof, 3);  /* send block type */#ifdef DEBUG    s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;    s->compressed_len += (stored_len + 4) << 3;#endif    copy_block(s, buf, (unsigned)stored_len, 1); /* with header */}/* =========================================================================== * Send one empty static block to give enough lookahead for inflate. * This takes 10 bits, of which 7 may remain in the bit buffer. * The current inflate code requires 9 bits of lookahead. If the * last two codes for the previous block (real code plus EOB) were coded * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode * the last real code. In this case we send two empty static blocks instead * of one. (There are no problems if the previous block is stored or fixed.) * To simplify the code, we assume the worst case of last real code encoded * on one bit only. */void _tr_align(s)    deflate_state *s;{    send_bits(s, STATIC_TREES<<1, 3);    send_code(s, END_BLOCK, static_ltree);#ifdef DEBUG    s->compressed_len += 10L; /* 3 for block type, 7 for EOB */#endif    bi_flush(s);    /* Of the 10 bits for the empty block, we have already sent     * (10 - bi_valid) bits. The lookahead for the last real code (before     * the EOB of the previous block) was thus at least one plus the length     * of the EOB plus what we have just sent of the empty static block.     */    if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {        send_bits(s, STATIC_TREES<<1, 3);        send_code(s, END_BLOCK, static_ltree);#ifdef DEBUG        s->compressed_len += 10L;#endif        bi_flush(s);    }    s->last_eob_len = 7;}/* =========================================================================== * Determine the best encoding for the current block: dynamic trees, static * trees or store, and output the encoded block to the zip file. */void _tr_flush_block(s, buf, stored_len, eof)    deflate_state *s;    charf *buf;       /* input block, or NULL if too old */    ulg stored_len;   /* length of input block */    int eof;          /* true if this is the last block for a file */{    ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */    int max_blindex = 0;  /* index of last bit length code of non zero freq */    /* Build the Huffman trees unless a stored block is forced */    if (s->level > 0) {        /* Check if the file is binary or text */        if (stored_len > 0 && s->strm->data_type == Z_UNKNOWN)            set_data_type(s);        /* Construct the literal and distance trees */        build_tree(s, (tree_desc *)(&(s->l_desc)));        Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,                s->static_len));        build_tree(s, (tree_desc *)(&(s->d_desc)));        Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,                s->static_len));        /* At this point, opt_len and static_len are the total bit lengths of         * the compressed block data, excluding the tree representations.         */        /* Build the bit length tree for the above two trees, and get the index         * in bl_order of the last bit length code to send.         */        max_blindex = build_bl_tree(s);        /* Determine the best encoding. Compute the block lengths in bytes. */        opt_lenb = (s->opt_len+3+7)>>3;        static_lenb = (s->static_len+3+7)>>3;        Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",                opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,                s->last_lit));        if (static_lenb <= opt_lenb) opt_lenb = static_lenb;    } else {        Assert(buf != (char*)0, "lost buf");        opt_lenb = static_lenb = stored_len + 5; /* force a stored block */    }#ifdef FORCE_STORED    if (buf != (char*)0) { /* force stored block */#else    if (stored_len+4 <= opt_lenb && buf != (char*)0) {                       /* 4: two words for the lengths */#endif        /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.         * Otherwise we can't have processed more than WSIZE input bytes since         * the last block flush, because compression would have been         * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to         * transform a block into a stored block.         */        _tr_stored_block(s, buf, stored_len, eof);#ifdef FORCE_STATIC    } else if (static_lenb >= 0) { /* force static trees */#else    } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {#endif        send_bits(s, (STATIC_TREES<<1)+eof, 3);        compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);#ifdef DEBUG        s->compressed_len += 3 + s->static_len;#endif    } else {        send_bits(s, (DYN_TREES<<1)+eof, 3);        send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,                       max_blindex+1);        compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);#ifdef DEBUG        s->compressed_len += 3 + s->opt_len;#endif    }    Assert (s->compressed_len == s->bits_sent, "bad compressed size");    /* The above check is made mod 2^32, for files larger than 512 MB     * and uLong implemented on 32 bits.     */    init_block(s);    if (eof) {        bi_windup(s);#ifdef DEBUG        s->compressed_len += 7;  /* align on byte boundary */#endif    }    Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,           s->compressed_len-7*eof));}/* =========================================================================== * Save the match info and tally the frequency counts. Return true if * the current block must be flushed. */int _tr_tally (s, dist, lc)    deflate_state *s;    unsigned dist;  /* distance of matched string */    unsigned lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */{    s->d_buf[s->last_lit] = (ush)dist;    s->l_buf[s->last_lit++] = (uch)lc;    if (dist == 0) {        /* lc is the unmatched char */        s->dyn_ltree[lc].Freq++;    } else {        s->matches++;        /* Here, lc is the match length - MIN_MATCH */        dist--;             /* dist = match distance - 1 */        Assert((ush)dist < (ush)MAX_DIST(s) &&               (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&               (ush)d_code(dist) < (ush)D_CODES,  "_tr_tally: bad match");        s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;        s->dyn_dtree[d_code(dist)].Freq++;    }#ifdef TRUNCATE_BLOCK    /* Try to guess if it is profitable to stop the current block here */    if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {        /* Compute an upper bound for the compressed length */        ulg out_length = (ulg)s->last_lit*8L;        ulg in_length = (ulg)((long)s->strstart - s->block_start);        int dcode;        for (dcode = 0; dcode < D_CODES; dcode++) {            out_length += (ulg)s->dyn_dtree[dcode].Freq *                (5L+extra_dbits[dcode]);        }        out_length >>= 3;        Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",               s->last_lit, in_length, out_length,               100L - out_length*100L/in_length));        if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;    }#endif    return (s->last_lit == s->lit_bufsize-1);    /* We avoid equality with lit_bufsize because of wraparound at 64K     * on 16 bit machines and because stored blocks are restricted to     * 64K-1 bytes.     */}/* =========================================================================== * Send the block data compressed using the given Huffman trees */local void compress_block(s, ltree, dtree)    deflate_state *s;    ct_data *ltree; /* literal tree */    ct_data *dtree; /* distance tree */{    unsigned dist;      /* distance of matched string */    int lc;             /* match length or unmatched char (if dist == 0) */    unsigned lx = 0;    /* running index in l_buf */    unsigned code;      /* the code to send */    int extra;          /* number of extra bits to send */    if (s->last_lit != 0) do {        dist = s->d_buf[lx];        lc = s->l_buf[lx++];        if (dist == 0) {            send_code(s, lc, ltree); /* send a literal byte */            Tracecv(isgraph(lc), (stderr," '%c' ", lc));        } else {            /* Here, lc is the match length - MIN_MATCH */            code = _length_code[lc];            send_code(s, code+LITERALS+1, ltree); /* send the length code */            extra = extra_lbits[code];            if (extra != 0) {                lc -= base_length[code];                send_bits(s, lc, extra);       /* send the extra length bits */            }            dist--; /* dist is now the match distance - 1 */            code = d_code(dist);            Assert (code < D_CODES, "bad d_code");            send_code(s, code, dtree);       /* send the distance code */            extra = extra_dbits[code];            if (extra != 0) {                dist -= base_dist[code];                send_bits(s, dist, extra);   /* send the extra distance bits */            }        } /* literal or match pair ? */        /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */        Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,               "pendingBuf overflow");    } while (lx < s->last_lit);    send_code(s, END_BLOCK, ltree);    s->last_eob_len = ltree[END_BLOCK].Len;}/* =========================================================================== * Set the data type to BINARY or TEXT, using a crude approximation: * set it to Z_TEXT if all symbols are either printable characters (33 to 255) * or white spaces (9 to 13, or 32); or set it to Z_BINARY otherwise. * IN assertion: the fields Freq of dyn_ltree are set. */local void set_data_type(s)    deflate_state *s;{    int n;    for (n = 0; n < 9; n++)        if (s->dyn_ltree[n].Freq != 0)            break;    if (n == 9)        for (n = 14; n < 32; n++)            if (s->dyn_ltree[n].Freq != 0)                break;    s->strm->data_type = (n == 32) ? Z_TEXT : Z_BINARY;}/* =========================================================================== * Reverse the first len bits of a code, using straightforward code (a faster * method would use a table) * IN assertion: 1 <= len <= 15 */local unsigned bi_reverse(code, len)    unsigned code; /* the value to invert */    int len;       /* its bit length */{    register unsigned res = 0;    do {        res |= code & 1;        code >>= 1, res <<= 1;    } while (--len > 0);    return res >> 1;}/* =========================================================================== * Flush the bit buffer, keeping at most 7 bits in it. */local void bi_flush(s)    deflate_state *s;{    if (s->bi_valid == 16) {        put_short(s, s->bi_buf);        s->bi_buf = 0;        s->bi_valid = 0;    } else if (s->bi_valid >= 8) {        put_byte(s, (Byte)s->bi_buf);        s->bi_buf >>= 8;        s->bi_valid -= 8;    }}/* =========================================================================== * Flush the bit buffer and align the output on a byte boundary */local void bi_windup(s)    deflate_state *s;{    if (s->bi_valid > 8) {        put_short(s, s->bi_buf);    } else if (s->bi_valid > 0) {        put_byte(s, (Byte)s->bi_buf);    }    s->bi_buf = 0;    s->bi_valid = 0;#ifdef DEBUG    s->bits_sent = (s->bits_sent+7) & ~7;#endif}/* =========================================================================== * Copy a stored block, storing first the length and its * one's complement if requested. */local void copy_block(s, buf, len, header)    deflate_state *s;    charf    *buf;    /* the input data */    unsigned len;     /* its length */    int      header;  /* true if block header must be written */{    bi_windup(s);        /* align on byte boundary */    s->last_eob_len = 8; /* enough lookahead for inflate */    if (header) {        put_short(s, (ush)len);        put_short(s, (ush)~len);#ifdef DEBUG        s->bits_sent += 2*16;#endif    }#ifdef DEBUG    s->bits_sent += (ulg)len<<3;#endif    while (len--) {        put_byte(s, *buf++);    }}