cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

deftree.c (38837B)


      1/* +++ trees.c */
      2/* trees.c -- output deflated data using Huffman coding
      3 * Copyright (C) 1995-1996 Jean-loup Gailly
      4 * For conditions of distribution and use, see copyright notice in zlib.h 
      5 */
      6
      7/*
      8 *  ALGORITHM
      9 *
     10 *      The "deflation" process uses several Huffman trees. The more
     11 *      common source values are represented by shorter bit sequences.
     12 *
     13 *      Each code tree is stored in a compressed form which is itself
     14 * a Huffman encoding of the lengths of all the code strings (in
     15 * ascending order by source values).  The actual code strings are
     16 * reconstructed from the lengths in the inflate process, as described
     17 * in the deflate specification.
     18 *
     19 *  REFERENCES
     20 *
     21 *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
     22 *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
     23 *
     24 *      Storer, James A.
     25 *          Data Compression:  Methods and Theory, pp. 49-50.
     26 *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
     27 *
     28 *      Sedgewick, R.
     29 *          Algorithms, p290.
     30 *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
     31 */
     32
     33/* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */
     34
     35/* #include "deflate.h" */
     36
     37#include <linux/zutil.h>
     38#include <linux/bitrev.h>
     39#include "defutil.h"
     40
     41#ifdef DEBUG_ZLIB
     42#  include <ctype.h>
     43#endif
     44
     45/* ===========================================================================
     46 * Constants
     47 */
     48
     49#define MAX_BL_BITS 7
     50/* Bit length codes must not exceed MAX_BL_BITS bits */
     51
     52#define END_BLOCK 256
     53/* end of block literal code */
     54
     55#define REP_3_6      16
     56/* repeat previous bit length 3-6 times (2 bits of repeat count) */
     57
     58#define REPZ_3_10    17
     59/* repeat a zero length 3-10 times  (3 bits of repeat count) */
     60
     61#define REPZ_11_138  18
     62/* repeat a zero length 11-138 times  (7 bits of repeat count) */
     63
     64static const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
     65   = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
     66
     67static const int extra_dbits[D_CODES] /* extra bits for each distance code */
     68   = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
     69
     70static const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
     71   = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
     72
     73static const uch bl_order[BL_CODES]
     74   = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
     75/* The lengths of the bit length codes are sent in order of decreasing
     76 * probability, to avoid transmitting the lengths for unused bit length codes.
     77 */
     78
     79/* ===========================================================================
     80 * Local data. These are initialized only once.
     81 */
     82
     83static ct_data static_ltree[L_CODES+2];
     84/* The static literal tree. Since the bit lengths are imposed, there is no
     85 * need for the L_CODES extra codes used during heap construction. However
     86 * The codes 286 and 287 are needed to build a canonical tree (see zlib_tr_init
     87 * below).
     88 */
     89
     90static ct_data static_dtree[D_CODES];
     91/* The static distance tree. (Actually a trivial tree since all codes use
     92 * 5 bits.)
     93 */
     94
     95static uch dist_code[512];
     96/* distance codes. The first 256 values correspond to the distances
     97 * 3 .. 258, the last 256 values correspond to the top 8 bits of
     98 * the 15 bit distances.
     99 */
    100
    101static uch length_code[MAX_MATCH-MIN_MATCH+1];
    102/* length code for each normalized match length (0 == MIN_MATCH) */
    103
    104static int base_length[LENGTH_CODES];
    105/* First normalized length for each code (0 = MIN_MATCH) */
    106
    107static int base_dist[D_CODES];
    108/* First normalized distance for each code (0 = distance of 1) */
    109
    110struct static_tree_desc_s {
    111    const ct_data *static_tree;  /* static tree or NULL */
    112    const int *extra_bits;       /* extra bits for each code or NULL */
    113    int     extra_base;          /* base index for extra_bits */
    114    int     elems;               /* max number of elements in the tree */
    115    int     max_length;          /* max bit length for the codes */
    116};
    117
    118static static_tree_desc  static_l_desc =
    119{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
    120
    121static static_tree_desc  static_d_desc =
    122{static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};
    123
    124static static_tree_desc  static_bl_desc =
    125{(const ct_data *)0, extra_blbits, 0,   BL_CODES, MAX_BL_BITS};
    126
    127/* ===========================================================================
    128 * Local (static) routines in this file.
    129 */
    130
    131static void tr_static_init (void);
    132static void init_block     (deflate_state *s);
    133static void pqdownheap     (deflate_state *s, ct_data *tree, int k);
    134static void gen_bitlen     (deflate_state *s, tree_desc *desc);
    135static void gen_codes      (ct_data *tree, int max_code, ush *bl_count);
    136static void build_tree     (deflate_state *s, tree_desc *desc);
    137static void scan_tree      (deflate_state *s, ct_data *tree, int max_code);
    138static void send_tree      (deflate_state *s, ct_data *tree, int max_code);
    139static int  build_bl_tree  (deflate_state *s);
    140static void send_all_trees (deflate_state *s, int lcodes, int dcodes,
    141                           int blcodes);
    142static void compress_block (deflate_state *s, ct_data *ltree,
    143                           ct_data *dtree);
    144static void set_data_type  (deflate_state *s);
    145static void bi_flush       (deflate_state *s);
    146static void copy_block     (deflate_state *s, char *buf, unsigned len,
    147                           int header);
    148
    149#ifndef DEBUG_ZLIB
    150#  define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
    151   /* Send a code of the given tree. c and tree must not have side effects */
    152
    153#else /* DEBUG_ZLIB */
    154#  define send_code(s, c, tree) \
    155     { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
    156       send_bits(s, tree[c].Code, tree[c].Len); }
    157#endif
    158
    159#define d_code(dist) \
    160   ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
    161/* Mapping from a distance to a distance code. dist is the distance - 1 and
    162 * must not have side effects. dist_code[256] and dist_code[257] are never
    163 * used.
    164 */
    165
    166/* ===========================================================================
    167 * Initialize the various 'constant' tables. In a multi-threaded environment,
    168 * this function may be called by two threads concurrently, but this is
    169 * harmless since both invocations do exactly the same thing.
    170 */
    171static void tr_static_init(void)
    172{
    173    static int static_init_done;
    174    int n;        /* iterates over tree elements */
    175    int bits;     /* bit counter */
    176    int length;   /* length value */
    177    int code;     /* code value */
    178    int dist;     /* distance index */
    179    ush bl_count[MAX_BITS+1];
    180    /* number of codes at each bit length for an optimal tree */
    181
    182    if (static_init_done) return;
    183
    184    /* Initialize the mapping length (0..255) -> length code (0..28) */
    185    length = 0;
    186    for (code = 0; code < LENGTH_CODES-1; code++) {
    187        base_length[code] = length;
    188        for (n = 0; n < (1<<extra_lbits[code]); n++) {
    189            length_code[length++] = (uch)code;
    190        }
    191    }
    192    Assert (length == 256, "tr_static_init: length != 256");
    193    /* Note that the length 255 (match length 258) can be represented
    194     * in two different ways: code 284 + 5 bits or code 285, so we
    195     * overwrite length_code[255] to use the best encoding:
    196     */
    197    length_code[length-1] = (uch)code;
    198
    199    /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
    200    dist = 0;
    201    for (code = 0 ; code < 16; code++) {
    202        base_dist[code] = dist;
    203        for (n = 0; n < (1<<extra_dbits[code]); n++) {
    204            dist_code[dist++] = (uch)code;
    205        }
    206    }
    207    Assert (dist == 256, "tr_static_init: dist != 256");
    208    dist >>= 7; /* from now on, all distances are divided by 128 */
    209    for ( ; code < D_CODES; code++) {
    210        base_dist[code] = dist << 7;
    211        for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
    212            dist_code[256 + dist++] = (uch)code;
    213        }
    214    }
    215    Assert (dist == 256, "tr_static_init: 256+dist != 512");
    216
    217    /* Construct the codes of the static literal tree */
    218    for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
    219    n = 0;
    220    while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
    221    while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
    222    while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
    223    while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
    224    /* Codes 286 and 287 do not exist, but we must include them in the
    225     * tree construction to get a canonical Huffman tree (longest code
    226     * all ones)
    227     */
    228    gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
    229
    230    /* The static distance tree is trivial: */
    231    for (n = 0; n < D_CODES; n++) {
    232        static_dtree[n].Len = 5;
    233        static_dtree[n].Code = bitrev32((u32)n) >> (32 - 5);
    234    }
    235    static_init_done = 1;
    236}
    237
    238/* ===========================================================================
    239 * Initialize the tree data structures for a new zlib stream.
    240 */
    241void zlib_tr_init(
    242	deflate_state *s
    243)
    244{
    245    tr_static_init();
    246
    247    s->compressed_len = 0L;
    248
    249    s->l_desc.dyn_tree = s->dyn_ltree;
    250    s->l_desc.stat_desc = &static_l_desc;
    251
    252    s->d_desc.dyn_tree = s->dyn_dtree;
    253    s->d_desc.stat_desc = &static_d_desc;
    254
    255    s->bl_desc.dyn_tree = s->bl_tree;
    256    s->bl_desc.stat_desc = &static_bl_desc;
    257
    258    s->bi_buf = 0;
    259    s->bi_valid = 0;
    260    s->last_eob_len = 8; /* enough lookahead for inflate */
    261#ifdef DEBUG_ZLIB
    262    s->bits_sent = 0L;
    263#endif
    264
    265    /* Initialize the first block of the first file: */
    266    init_block(s);
    267}
    268
    269/* ===========================================================================
    270 * Initialize a new block.
    271 */
    272static void init_block(
    273	deflate_state *s
    274)
    275{
    276    int n; /* iterates over tree elements */
    277
    278    /* Initialize the trees. */
    279    for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;
    280    for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;
    281    for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
    282
    283    s->dyn_ltree[END_BLOCK].Freq = 1;
    284    s->opt_len = s->static_len = 0L;
    285    s->last_lit = s->matches = 0;
    286}
    287
    288#define SMALLEST 1
    289/* Index within the heap array of least frequent node in the Huffman tree */
    290
    291
    292/* ===========================================================================
    293 * Remove the smallest element from the heap and recreate the heap with
    294 * one less element. Updates heap and heap_len.
    295 */
    296#define pqremove(s, tree, top) \
    297{\
    298    top = s->heap[SMALLEST]; \
    299    s->heap[SMALLEST] = s->heap[s->heap_len--]; \
    300    pqdownheap(s, tree, SMALLEST); \
    301}
    302
    303/* ===========================================================================
    304 * Compares to subtrees, using the tree depth as tie breaker when
    305 * the subtrees have equal frequency. This minimizes the worst case length.
    306 */
    307#define smaller(tree, n, m, depth) \
    308   (tree[n].Freq < tree[m].Freq || \
    309   (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
    310
    311/* ===========================================================================
    312 * Restore the heap property by moving down the tree starting at node k,
    313 * exchanging a node with the smallest of its two sons if necessary, stopping
    314 * when the heap property is re-established (each father smaller than its
    315 * two sons).
    316 */
    317static void pqdownheap(
    318	deflate_state *s,
    319	ct_data *tree,  /* the tree to restore */
    320	int k		/* node to move down */
    321)
    322{
    323    int v = s->heap[k];
    324    int j = k << 1;  /* left son of k */
    325    while (j <= s->heap_len) {
    326        /* Set j to the smallest of the two sons: */
    327        if (j < s->heap_len &&
    328            smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
    329            j++;
    330        }
    331        /* Exit if v is smaller than both sons */
    332        if (smaller(tree, v, s->heap[j], s->depth)) break;
    333
    334        /* Exchange v with the smallest son */
    335        s->heap[k] = s->heap[j];  k = j;
    336
    337        /* And continue down the tree, setting j to the left son of k */
    338        j <<= 1;
    339    }
    340    s->heap[k] = v;
    341}
    342
    343/* ===========================================================================
    344 * Compute the optimal bit lengths for a tree and update the total bit length
    345 * for the current block.
    346 * IN assertion: the fields freq and dad are set, heap[heap_max] and
    347 *    above are the tree nodes sorted by increasing frequency.
    348 * OUT assertions: the field len is set to the optimal bit length, the
    349 *     array bl_count contains the frequencies for each bit length.
    350 *     The length opt_len is updated; static_len is also updated if stree is
    351 *     not null.
    352 */
    353static void gen_bitlen(
    354	deflate_state *s,
    355	tree_desc *desc    /* the tree descriptor */
    356)
    357{
    358    ct_data *tree        = desc->dyn_tree;
    359    int max_code         = desc->max_code;
    360    const ct_data *stree = desc->stat_desc->static_tree;
    361    const int *extra     = desc->stat_desc->extra_bits;
    362    int base             = desc->stat_desc->extra_base;
    363    int max_length       = desc->stat_desc->max_length;
    364    int h;              /* heap index */
    365    int n, m;           /* iterate over the tree elements */
    366    int bits;           /* bit length */
    367    int xbits;          /* extra bits */
    368    ush f;              /* frequency */
    369    int overflow = 0;   /* number of elements with bit length too large */
    370
    371    for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
    372
    373    /* In a first pass, compute the optimal bit lengths (which may
    374     * overflow in the case of the bit length tree).
    375     */
    376    tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
    377
    378    for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
    379        n = s->heap[h];
    380        bits = tree[tree[n].Dad].Len + 1;
    381        if (bits > max_length) bits = max_length, overflow++;
    382        tree[n].Len = (ush)bits;
    383        /* We overwrite tree[n].Dad which is no longer needed */
    384
    385        if (n > max_code) continue; /* not a leaf node */
    386
    387        s->bl_count[bits]++;
    388        xbits = 0;
    389        if (n >= base) xbits = extra[n-base];
    390        f = tree[n].Freq;
    391        s->opt_len += (ulg)f * (bits + xbits);
    392        if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
    393    }
    394    if (overflow == 0) return;
    395
    396    Trace((stderr,"\nbit length overflow\n"));
    397    /* This happens for example on obj2 and pic of the Calgary corpus */
    398
    399    /* Find the first bit length which could increase: */
    400    do {
    401        bits = max_length-1;
    402        while (s->bl_count[bits] == 0) bits--;
    403        s->bl_count[bits]--;      /* move one leaf down the tree */
    404        s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
    405        s->bl_count[max_length]--;
    406        /* The brother of the overflow item also moves one step up,
    407         * but this does not affect bl_count[max_length]
    408         */
    409        overflow -= 2;
    410    } while (overflow > 0);
    411
    412    /* Now recompute all bit lengths, scanning in increasing frequency.
    413     * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
    414     * lengths instead of fixing only the wrong ones. This idea is taken
    415     * from 'ar' written by Haruhiko Okumura.)
    416     */
    417    for (bits = max_length; bits != 0; bits--) {
    418        n = s->bl_count[bits];
    419        while (n != 0) {
    420            m = s->heap[--h];
    421            if (m > max_code) continue;
    422            if (tree[m].Len != (unsigned) bits) {
    423                Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
    424                s->opt_len += ((long)bits - (long)tree[m].Len)
    425                              *(long)tree[m].Freq;
    426                tree[m].Len = (ush)bits;
    427            }
    428            n--;
    429        }
    430    }
    431}
    432
    433/* ===========================================================================
    434 * Generate the codes for a given tree and bit counts (which need not be
    435 * optimal).
    436 * IN assertion: the array bl_count contains the bit length statistics for
    437 * the given tree and the field len is set for all tree elements.
    438 * OUT assertion: the field code is set for all tree elements of non
    439 *     zero code length.
    440 */
    441static void gen_codes(
    442	ct_data *tree,             /* the tree to decorate */
    443	int max_code,              /* largest code with non zero frequency */
    444	ush *bl_count             /* number of codes at each bit length */
    445)
    446{
    447    ush next_code[MAX_BITS+1]; /* next code value for each bit length */
    448    ush code = 0;              /* running code value */
    449    int bits;                  /* bit index */
    450    int n;                     /* code index */
    451
    452    /* The distribution counts are first used to generate the code values
    453     * without bit reversal.
    454     */
    455    for (bits = 1; bits <= MAX_BITS; bits++) {
    456        next_code[bits] = code = (code + bl_count[bits-1]) << 1;
    457    }
    458    /* Check that the bit counts in bl_count are consistent. The last code
    459     * must be all ones.
    460     */
    461    Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
    462            "inconsistent bit counts");
    463    Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
    464
    465    for (n = 0;  n <= max_code; n++) {
    466        int len = tree[n].Len;
    467        if (len == 0) continue;
    468        /* Now reverse the bits */
    469        tree[n].Code = bitrev32((u32)(next_code[len]++)) >> (32 - len);
    470
    471        Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
    472             n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
    473    }
    474}
    475
    476/* ===========================================================================
    477 * Construct one Huffman tree and assigns the code bit strings and lengths.
    478 * Update the total bit length for the current block.
    479 * IN assertion: the field freq is set for all tree elements.
    480 * OUT assertions: the fields len and code are set to the optimal bit length
    481 *     and corresponding code. The length opt_len is updated; static_len is
    482 *     also updated if stree is not null. The field max_code is set.
    483 */
    484static void build_tree(
    485	deflate_state *s,
    486	tree_desc *desc	 /* the tree descriptor */
    487)
    488{
    489    ct_data *tree         = desc->dyn_tree;
    490    const ct_data *stree  = desc->stat_desc->static_tree;
    491    int elems             = desc->stat_desc->elems;
    492    int n, m;          /* iterate over heap elements */
    493    int max_code = -1; /* largest code with non zero frequency */
    494    int node;          /* new node being created */
    495
    496    /* Construct the initial heap, with least frequent element in
    497     * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
    498     * heap[0] is not used.
    499     */
    500    s->heap_len = 0, s->heap_max = HEAP_SIZE;
    501
    502    for (n = 0; n < elems; n++) {
    503        if (tree[n].Freq != 0) {
    504            s->heap[++(s->heap_len)] = max_code = n;
    505            s->depth[n] = 0;
    506        } else {
    507            tree[n].Len = 0;
    508        }
    509    }
    510
    511    /* The pkzip format requires that at least one distance code exists,
    512     * and that at least one bit should be sent even if there is only one
    513     * possible code. So to avoid special checks later on we force at least
    514     * two codes of non zero frequency.
    515     */
    516    while (s->heap_len < 2) {
    517        node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
    518        tree[node].Freq = 1;
    519        s->depth[node] = 0;
    520        s->opt_len--; if (stree) s->static_len -= stree[node].Len;
    521        /* node is 0 or 1 so it does not have extra bits */
    522    }
    523    desc->max_code = max_code;
    524
    525    /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
    526     * establish sub-heaps of increasing lengths:
    527     */
    528    for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
    529
    530    /* Construct the Huffman tree by repeatedly combining the least two
    531     * frequent nodes.
    532     */
    533    node = elems;              /* next internal node of the tree */
    534    do {
    535        pqremove(s, tree, n);  /* n = node of least frequency */
    536        m = s->heap[SMALLEST]; /* m = node of next least frequency */
    537
    538        s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
    539        s->heap[--(s->heap_max)] = m;
    540
    541        /* Create a new node father of n and m */
    542        tree[node].Freq = tree[n].Freq + tree[m].Freq;
    543        s->depth[node] = (uch) (max(s->depth[n], s->depth[m]) + 1);
    544        tree[n].Dad = tree[m].Dad = (ush)node;
    545#ifdef DUMP_BL_TREE
    546        if (tree == s->bl_tree) {
    547            fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
    548                    node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
    549        }
    550#endif
    551        /* and insert the new node in the heap */
    552        s->heap[SMALLEST] = node++;
    553        pqdownheap(s, tree, SMALLEST);
    554
    555    } while (s->heap_len >= 2);
    556
    557    s->heap[--(s->heap_max)] = s->heap[SMALLEST];
    558
    559    /* At this point, the fields freq and dad are set. We can now
    560     * generate the bit lengths.
    561     */
    562    gen_bitlen(s, (tree_desc *)desc);
    563
    564    /* The field len is now set, we can generate the bit codes */
    565    gen_codes ((ct_data *)tree, max_code, s->bl_count);
    566}
    567
    568/* ===========================================================================
    569 * Scan a literal or distance tree to determine the frequencies of the codes
    570 * in the bit length tree.
    571 */
    572static void scan_tree(
    573	deflate_state *s,
    574	ct_data *tree,   /* the tree to be scanned */
    575	int max_code     /* and its largest code of non zero frequency */
    576)
    577{
    578    int n;                     /* iterates over all tree elements */
    579    int prevlen = -1;          /* last emitted length */
    580    int curlen;                /* length of current code */
    581    int nextlen = tree[0].Len; /* length of next code */
    582    int count = 0;             /* repeat count of the current code */
    583    int max_count = 7;         /* max repeat count */
    584    int min_count = 4;         /* min repeat count */
    585
    586    if (nextlen == 0) max_count = 138, min_count = 3;
    587    tree[max_code+1].Len = (ush)0xffff; /* guard */
    588
    589    for (n = 0; n <= max_code; n++) {
    590        curlen = nextlen; nextlen = tree[n+1].Len;
    591        if (++count < max_count && curlen == nextlen) {
    592            continue;
    593        } else if (count < min_count) {
    594            s->bl_tree[curlen].Freq += count;
    595        } else if (curlen != 0) {
    596            if (curlen != prevlen) s->bl_tree[curlen].Freq++;
    597            s->bl_tree[REP_3_6].Freq++;
    598        } else if (count <= 10) {
    599            s->bl_tree[REPZ_3_10].Freq++;
    600        } else {
    601            s->bl_tree[REPZ_11_138].Freq++;
    602        }
    603        count = 0; prevlen = curlen;
    604        if (nextlen == 0) {
    605            max_count = 138, min_count = 3;
    606        } else if (curlen == nextlen) {
    607            max_count = 6, min_count = 3;
    608        } else {
    609            max_count = 7, min_count = 4;
    610        }
    611    }
    612}
    613
    614/* ===========================================================================
    615 * Send a literal or distance tree in compressed form, using the codes in
    616 * bl_tree.
    617 */
    618static void send_tree(
    619	deflate_state *s,
    620	ct_data *tree, /* the tree to be scanned */
    621	int max_code   /* and its largest code of non zero frequency */
    622)
    623{
    624    int n;                     /* iterates over all tree elements */
    625    int prevlen = -1;          /* last emitted length */
    626    int curlen;                /* length of current code */
    627    int nextlen = tree[0].Len; /* length of next code */
    628    int count = 0;             /* repeat count of the current code */
    629    int max_count = 7;         /* max repeat count */
    630    int min_count = 4;         /* min repeat count */
    631
    632    /* tree[max_code+1].Len = -1; */  /* guard already set */
    633    if (nextlen == 0) max_count = 138, min_count = 3;
    634
    635    for (n = 0; n <= max_code; n++) {
    636        curlen = nextlen; nextlen = tree[n+1].Len;
    637        if (++count < max_count && curlen == nextlen) {
    638            continue;
    639        } else if (count < min_count) {
    640            do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
    641
    642        } else if (curlen != 0) {
    643            if (curlen != prevlen) {
    644                send_code(s, curlen, s->bl_tree); count--;
    645            }
    646            Assert(count >= 3 && count <= 6, " 3_6?");
    647            send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
    648
    649        } else if (count <= 10) {
    650            send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
    651
    652        } else {
    653            send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
    654        }
    655        count = 0; prevlen = curlen;
    656        if (nextlen == 0) {
    657            max_count = 138, min_count = 3;
    658        } else if (curlen == nextlen) {
    659            max_count = 6, min_count = 3;
    660        } else {
    661            max_count = 7, min_count = 4;
    662        }
    663    }
    664}
    665
    666/* ===========================================================================
    667 * Construct the Huffman tree for the bit lengths and return the index in
    668 * bl_order of the last bit length code to send.
    669 */
    670static int build_bl_tree(
    671	deflate_state *s
    672)
    673{
    674    int max_blindex;  /* index of last bit length code of non zero freq */
    675
    676    /* Determine the bit length frequencies for literal and distance trees */
    677    scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
    678    scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
    679
    680    /* Build the bit length tree: */
    681    build_tree(s, (tree_desc *)(&(s->bl_desc)));
    682    /* opt_len now includes the length of the tree representations, except
    683     * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
    684     */
    685
    686    /* Determine the number of bit length codes to send. The pkzip format
    687     * requires that at least 4 bit length codes be sent. (appnote.txt says
    688     * 3 but the actual value used is 4.)
    689     */
    690    for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
    691        if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
    692    }
    693    /* Update opt_len to include the bit length tree and counts */
    694    s->opt_len += 3*(max_blindex+1) + 5+5+4;
    695    Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
    696            s->opt_len, s->static_len));
    697
    698    return max_blindex;
    699}
    700
    701/* ===========================================================================
    702 * Send the header for a block using dynamic Huffman trees: the counts, the
    703 * lengths of the bit length codes, the literal tree and the distance tree.
    704 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
    705 */
    706static void send_all_trees(
    707	deflate_state *s,
    708	int lcodes,  /* number of codes for each tree */
    709	int dcodes,  /* number of codes for each tree */
    710	int blcodes  /* number of codes for each tree */
    711)
    712{
    713    int rank;                    /* index in bl_order */
    714
    715    Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
    716    Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
    717            "too many codes");
    718    Tracev((stderr, "\nbl counts: "));
    719    send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
    720    send_bits(s, dcodes-1,   5);
    721    send_bits(s, blcodes-4,  4); /* not -3 as stated in appnote.txt */
    722    for (rank = 0; rank < blcodes; rank++) {
    723        Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
    724        send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
    725    }
    726    Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
    727
    728    send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
    729    Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
    730
    731    send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
    732    Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
    733}
    734
    735/* ===========================================================================
    736 * Send a stored block
    737 */
    738void zlib_tr_stored_block(
    739	deflate_state *s,
    740	char *buf,        /* input block */
    741	ulg stored_len,   /* length of input block */
    742	int eof           /* true if this is the last block for a file */
    743)
    744{
    745    send_bits(s, (STORED_BLOCK<<1)+eof, 3);  /* send block type */
    746    s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
    747    s->compressed_len += (stored_len + 4) << 3;
    748
    749    copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
    750}
    751
    752/* Send just the `stored block' type code without any length bytes or data.
    753 */
    754void zlib_tr_stored_type_only(
    755	deflate_state *s
    756)
    757{
    758    send_bits(s, (STORED_BLOCK << 1), 3);
    759    bi_windup(s);
    760    s->compressed_len = (s->compressed_len + 3) & ~7L;
    761}
    762
    763
    764/* ===========================================================================
    765 * Send one empty static block to give enough lookahead for inflate.
    766 * This takes 10 bits, of which 7 may remain in the bit buffer.
    767 * The current inflate code requires 9 bits of lookahead. If the
    768 * last two codes for the previous block (real code plus EOB) were coded
    769 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
    770 * the last real code. In this case we send two empty static blocks instead
    771 * of one. (There are no problems if the previous block is stored or fixed.)
    772 * To simplify the code, we assume the worst case of last real code encoded
    773 * on one bit only.
    774 */
    775void zlib_tr_align(
    776	deflate_state *s
    777)
    778{
    779    send_bits(s, STATIC_TREES<<1, 3);
    780    send_code(s, END_BLOCK, static_ltree);
    781    s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
    782    bi_flush(s);
    783    /* Of the 10 bits for the empty block, we have already sent
    784     * (10 - bi_valid) bits. The lookahead for the last real code (before
    785     * the EOB of the previous block) was thus at least one plus the length
    786     * of the EOB plus what we have just sent of the empty static block.
    787     */
    788    if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
    789        send_bits(s, STATIC_TREES<<1, 3);
    790        send_code(s, END_BLOCK, static_ltree);
    791        s->compressed_len += 10L;
    792        bi_flush(s);
    793    }
    794    s->last_eob_len = 7;
    795}
    796
    797/* ===========================================================================
    798 * Determine the best encoding for the current block: dynamic trees, static
    799 * trees or store, and output the encoded block to the zip file. This function
    800 * returns the total compressed length for the file so far.
    801 */
    802ulg zlib_tr_flush_block(
    803	deflate_state *s,
    804	char *buf,        /* input block, or NULL if too old */
    805	ulg stored_len,   /* length of input block */
    806	int eof           /* true if this is the last block for a file */
    807)
    808{
    809    ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
    810    int max_blindex = 0;  /* index of last bit length code of non zero freq */
    811
    812    /* Build the Huffman trees unless a stored block is forced */
    813    if (s->level > 0) {
    814
    815	 /* Check if the file is ascii or binary */
    816	if (s->data_type == Z_UNKNOWN) set_data_type(s);
    817
    818	/* Construct the literal and distance trees */
    819	build_tree(s, (tree_desc *)(&(s->l_desc)));
    820	Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
    821		s->static_len));
    822
    823	build_tree(s, (tree_desc *)(&(s->d_desc)));
    824	Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
    825		s->static_len));
    826	/* At this point, opt_len and static_len are the total bit lengths of
    827	 * the compressed block data, excluding the tree representations.
    828	 */
    829
    830	/* Build the bit length tree for the above two trees, and get the index
    831	 * in bl_order of the last bit length code to send.
    832	 */
    833	max_blindex = build_bl_tree(s);
    834
    835	/* Determine the best encoding. Compute first the block length in bytes*/
    836	opt_lenb = (s->opt_len+3+7)>>3;
    837	static_lenb = (s->static_len+3+7)>>3;
    838
    839	Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
    840		opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
    841		s->last_lit));
    842
    843	if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
    844
    845    } else {
    846        Assert(buf != (char*)0, "lost buf");
    847	opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
    848    }
    849
    850    /* If compression failed and this is the first and last block,
    851     * and if the .zip file can be seeked (to rewrite the local header),
    852     * the whole file is transformed into a stored file:
    853     */
    854#ifdef STORED_FILE_OK
    855#  ifdef FORCE_STORED_FILE
    856    if (eof && s->compressed_len == 0L) { /* force stored file */
    857#  else
    858    if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) {
    859#  endif
    860        /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
    861        if (buf == (char*)0) error ("block vanished");
    862
    863        copy_block(s, buf, (unsigned)stored_len, 0); /* without header */
    864        s->compressed_len = stored_len << 3;
    865        s->method = STORED;
    866    } else
    867#endif /* STORED_FILE_OK */
    868
    869#ifdef FORCE_STORED
    870    if (buf != (char*)0) { /* force stored block */
    871#else
    872    if (stored_len+4 <= opt_lenb && buf != (char*)0) {
    873                       /* 4: two words for the lengths */
    874#endif
    875        /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
    876         * Otherwise we can't have processed more than WSIZE input bytes since
    877         * the last block flush, because compression would have been
    878         * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
    879         * transform a block into a stored block.
    880         */
    881        zlib_tr_stored_block(s, buf, stored_len, eof);
    882
    883#ifdef FORCE_STATIC
    884    } else if (static_lenb >= 0) { /* force static trees */
    885#else
    886    } else if (static_lenb == opt_lenb) {
    887#endif
    888        send_bits(s, (STATIC_TREES<<1)+eof, 3);
    889        compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
    890        s->compressed_len += 3 + s->static_len;
    891    } else {
    892        send_bits(s, (DYN_TREES<<1)+eof, 3);
    893        send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
    894                       max_blindex+1);
    895        compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
    896        s->compressed_len += 3 + s->opt_len;
    897    }
    898    Assert (s->compressed_len == s->bits_sent, "bad compressed size");
    899    init_block(s);
    900
    901    if (eof) {
    902        bi_windup(s);
    903        s->compressed_len += 7;  /* align on byte boundary */
    904    }
    905    Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
    906           s->compressed_len-7*eof));
    907
    908    return s->compressed_len >> 3;
    909}
    910
    911/* ===========================================================================
    912 * Save the match info and tally the frequency counts. Return true if
    913 * the current block must be flushed.
    914 */
    915int zlib_tr_tally(
    916	deflate_state *s,
    917	unsigned dist,  /* distance of matched string */
    918	unsigned lc     /* match length-MIN_MATCH or unmatched char (if dist==0) */
    919)
    920{
    921    s->d_buf[s->last_lit] = (ush)dist;
    922    s->l_buf[s->last_lit++] = (uch)lc;
    923    if (dist == 0) {
    924        /* lc is the unmatched char */
    925        s->dyn_ltree[lc].Freq++;
    926    } else {
    927        s->matches++;
    928        /* Here, lc is the match length - MIN_MATCH */
    929        dist--;             /* dist = match distance - 1 */
    930        Assert((ush)dist < (ush)MAX_DIST(s) &&
    931               (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
    932               (ush)d_code(dist) < (ush)D_CODES,  "zlib_tr_tally: bad match");
    933
    934        s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
    935        s->dyn_dtree[d_code(dist)].Freq++;
    936    }
    937
    938    /* Try to guess if it is profitable to stop the current block here */
    939    if ((s->last_lit & 0xfff) == 0 && s->level > 2) {
    940        /* Compute an upper bound for the compressed length */
    941        ulg out_length = (ulg)s->last_lit*8L;
    942        ulg in_length = (ulg)((long)s->strstart - s->block_start);
    943        int dcode;
    944        for (dcode = 0; dcode < D_CODES; dcode++) {
    945            out_length += (ulg)s->dyn_dtree[dcode].Freq *
    946                (5L+extra_dbits[dcode]);
    947        }
    948        out_length >>= 3;
    949        Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
    950               s->last_lit, in_length, out_length,
    951               100L - out_length*100L/in_length));
    952        if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
    953    }
    954    return (s->last_lit == s->lit_bufsize-1);
    955    /* We avoid equality with lit_bufsize because of wraparound at 64K
    956     * on 16 bit machines and because stored blocks are restricted to
    957     * 64K-1 bytes.
    958     */
    959}
    960
    961/* ===========================================================================
    962 * Send the block data compressed using the given Huffman trees
    963 */
    964static void compress_block(
    965	deflate_state *s,
    966	ct_data *ltree, /* literal tree */
    967	ct_data *dtree  /* distance tree */
    968)
    969{
    970    unsigned dist;      /* distance of matched string */
    971    int lc;             /* match length or unmatched char (if dist == 0) */
    972    unsigned lx = 0;    /* running index in l_buf */
    973    unsigned code;      /* the code to send */
    974    int extra;          /* number of extra bits to send */
    975
    976    if (s->last_lit != 0) do {
    977        dist = s->d_buf[lx];
    978        lc = s->l_buf[lx++];
    979        if (dist == 0) {
    980            send_code(s, lc, ltree); /* send a literal byte */
    981            Tracecv(isgraph(lc), (stderr," '%c' ", lc));
    982        } else {
    983            /* Here, lc is the match length - MIN_MATCH */
    984            code = length_code[lc];
    985            send_code(s, code+LITERALS+1, ltree); /* send the length code */
    986            extra = extra_lbits[code];
    987            if (extra != 0) {
    988                lc -= base_length[code];
    989                send_bits(s, lc, extra);       /* send the extra length bits */
    990            }
    991            dist--; /* dist is now the match distance - 1 */
    992            code = d_code(dist);
    993            Assert (code < D_CODES, "bad d_code");
    994
    995            send_code(s, code, dtree);       /* send the distance code */
    996            extra = extra_dbits[code];
    997            if (extra != 0) {
    998                dist -= base_dist[code];
    999                send_bits(s, dist, extra);   /* send the extra distance bits */
   1000            }
   1001        } /* literal or match pair ? */
   1002
   1003        /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
   1004        Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
   1005
   1006    } while (lx < s->last_lit);
   1007
   1008    send_code(s, END_BLOCK, ltree);
   1009    s->last_eob_len = ltree[END_BLOCK].Len;
   1010}
   1011
   1012/* ===========================================================================
   1013 * Set the data type to ASCII or BINARY, using a crude approximation:
   1014 * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
   1015 * IN assertion: the fields freq of dyn_ltree are set and the total of all
   1016 * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
   1017 */
   1018static void set_data_type(
   1019	deflate_state *s
   1020)
   1021{
   1022    int n = 0;
   1023    unsigned ascii_freq = 0;
   1024    unsigned bin_freq = 0;
   1025    while (n < 7)        bin_freq += s->dyn_ltree[n++].Freq;
   1026    while (n < 128)    ascii_freq += s->dyn_ltree[n++].Freq;
   1027    while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
   1028    s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
   1029}
   1030
   1031/* ===========================================================================
   1032 * Copy a stored block, storing first the length and its
   1033 * one's complement if requested.
   1034 */
   1035static void copy_block(
   1036	deflate_state *s,
   1037	char    *buf,     /* the input data */
   1038	unsigned len,     /* its length */
   1039	int      header   /* true if block header must be written */
   1040)
   1041{
   1042    bi_windup(s);        /* align on byte boundary */
   1043    s->last_eob_len = 8; /* enough lookahead for inflate */
   1044
   1045    if (header) {
   1046        put_short(s, (ush)len);   
   1047        put_short(s, (ush)~len);
   1048#ifdef DEBUG_ZLIB
   1049        s->bits_sent += 2*16;
   1050#endif
   1051    }
   1052#ifdef DEBUG_ZLIB
   1053    s->bits_sent += (ulg)len<<3;
   1054#endif
   1055    /* bundle up the put_byte(s, *buf++) calls */
   1056    memcpy(&s->pending_buf[s->pending], buf, len);
   1057    s->pending += len;
   1058}
   1059