"Fossies" - the Fresh Open Source Software Archive

Member "src/Common/zlib/trees.c" (10 Oct 2018, 43761 Bytes) of package /windows/misc/VeraCrypt_1.23-Hotfix-2_Source.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "trees.c" see the Fossies "Dox" file reference documentation.

    1 /* trees.c -- output deflated data using Huffman coding
    2  * Copyright (C) 1995-2017 Jean-loup Gailly
    3  * detect_data_type() function provided freely by Cosmin Truta, 2006
    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 /* @(#) $Id$ */
   34 
   35 /* #define GEN_TREES_H */
   36 
   37 #include "deflate.h"
   38 
   39 #ifdef ZLIB_DEBUG
   40 #  include <ctype.h>
   41 #endif
   42 
   43 /* ===========================================================================
   44  * Constants
   45  */
   46 
   47 #define MAX_BL_BITS 7
   48 /* Bit length codes must not exceed MAX_BL_BITS bits */
   49 
   50 #define END_BLOCK 256
   51 /* end of block literal code */
   52 
   53 #define REP_3_6      16
   54 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
   55 
   56 #define REPZ_3_10    17
   57 /* repeat a zero length 3-10 times  (3 bits of repeat count) */
   58 
   59 #define REPZ_11_138  18
   60 /* repeat a zero length 11-138 times  (7 bits of repeat count) */
   61 
   62 local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
   63    = {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};
   64 
   65 local const int extra_dbits[D_CODES] /* extra bits for each distance code */
   66    = {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};
   67 
   68 local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
   69    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
   70 
   71 local const uch bl_order[BL_CODES]
   72    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
   73 /* The lengths of the bit length codes are sent in order of decreasing
   74  * probability, to avoid transmitting the lengths for unused bit length codes.
   75  */
   76 
   77 /* ===========================================================================
   78  * Local data. These are initialized only once.
   79  */
   80 
   81 #define DIST_CODE_LEN  512 /* see definition of array dist_code below */
   82 
   83 #if defined(GEN_TREES_H) || !defined(STDC)
   84 /* non ANSI compilers may not accept trees.h */
   85 
   86 local ct_data static_ltree[L_CODES+2];
   87 /* The static literal tree. Since the bit lengths are imposed, there is no
   88  * need for the L_CODES extra codes used during heap construction. However
   89  * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
   90  * below).
   91  */
   92 
   93 local ct_data static_dtree[D_CODES];
   94 /* The static distance tree. (Actually a trivial tree since all codes use
   95  * 5 bits.)
   96  */
   97 
   98 uch _dist_code[DIST_CODE_LEN];
   99 /* Distance codes. The first 256 values correspond to the distances
  100  * 3 .. 258, the last 256 values correspond to the top 8 bits of
  101  * the 15 bit distances.
  102  */
  103 
  104 uch _length_code[MAX_MATCH-MIN_MATCH+1];
  105 /* length code for each normalized match length (0 == MIN_MATCH) */
  106 
  107 local int base_length[LENGTH_CODES];
  108 /* First normalized length for each code (0 = MIN_MATCH) */
  109 
  110 local int base_dist[D_CODES];
  111 /* First normalized distance for each code (0 = distance of 1) */
  112 
  113 #else
  114 #  include "trees.h"
  115 #endif /* GEN_TREES_H */
  116 
  117 struct static_tree_desc_s {
  118     const ct_data *static_tree;  /* static tree or NULL */
  119     const intf *extra_bits;      /* extra bits for each code or NULL */
  120     int     extra_base;          /* base index for extra_bits */
  121     int     elems;               /* max number of elements in the tree */
  122     int     max_length;          /* max bit length for the codes */
  123 };
  124 
  125 local const static_tree_desc  static_l_desc =
  126 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
  127 
  128 local const static_tree_desc  static_d_desc =
  129 {static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};
  130 
  131 local const static_tree_desc  static_bl_desc =
  132 {(const ct_data *)0, extra_blbits, 0,   BL_CODES, MAX_BL_BITS};
  133 
  134 /* ===========================================================================
  135  * Local (static) routines in this file.
  136  */
  137 
  138 local void tr_static_init OF((void));
  139 local void init_block     OF((deflate_state *s));
  140 local void pqdownheap     OF((deflate_state *s, ct_data *tree, int k));
  141 local void gen_bitlen     OF((deflate_state *s, tree_desc *desc));
  142 local void gen_codes      OF((ct_data *tree, int max_code, ushf *bl_count));
  143 local void build_tree     OF((deflate_state *s, tree_desc *desc));
  144 local void scan_tree      OF((deflate_state *s, ct_data *tree, int max_code));
  145 local void send_tree      OF((deflate_state *s, ct_data *tree, int max_code));
  146 local int  build_bl_tree  OF((deflate_state *s));
  147 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
  148                               int blcodes));
  149 local void compress_block OF((deflate_state *s, const ct_data *ltree,
  150                               const ct_data *dtree));
  151 local int  detect_data_type OF((deflate_state *s));
  152 local unsigned bi_reverse OF((unsigned value, int length));
  153 local void bi_windup      OF((deflate_state *s));
  154 local void bi_flush       OF((deflate_state *s));
  155 
  156 #ifdef GEN_TREES_H
  157 local void gen_trees_header OF((void));
  158 #endif
  159 
  160 #ifndef ZLIB_DEBUG
  161 #  define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
  162    /* Send a code of the given tree. c and tree must not have side effects */
  163 
  164 #else /* !ZLIB_DEBUG */
  165 #  define send_code(s, c, tree) \
  166      { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
  167        send_bits(s, tree[c].Code, tree[c].Len); }
  168 #endif
  169 
  170 /* ===========================================================================
  171  * Output a short LSB first on the stream.
  172  * IN assertion: there is enough room in pendingBuf.
  173  */
  174 #define put_short(s, w) { \
  175     put_byte(s, (uch)((w) & 0xff)); \
  176     put_byte(s, (uch)((ush)(w) >> 8)); \
  177 }
  178 
  179 /* ===========================================================================
  180  * Send a value on a given number of bits.
  181  * IN assertion: length <= 16 and value fits in length bits.
  182  */
  183 #ifdef ZLIB_DEBUG
  184 local void send_bits      OF((deflate_state *s, int value, int length));
  185 
  186 local void send_bits(s, value, length)
  187     deflate_state *s;
  188     int value;  /* value to send */
  189     int length; /* number of bits */
  190 {
  191     Tracevv((stderr," l %2d v %4x ", length, value));
  192     Assert(length > 0 && length <= 15, "invalid length");
  193     s->bits_sent += (ulg)length;
  194 
  195     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
  196      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
  197      * unused bits in value.
  198      */
  199     if (s->bi_valid > (int)Buf_size - length) {
  200         s->bi_buf |= (ush)value << s->bi_valid;
  201         put_short(s, s->bi_buf);
  202         s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
  203         s->bi_valid += length - Buf_size;
  204     } else {
  205         s->bi_buf |= (ush)value << s->bi_valid;
  206         s->bi_valid += length;
  207     }
  208 }
  209 #else /* !ZLIB_DEBUG */
  210 
  211 #define send_bits(s, value, length) \
  212 { int len = length;\
  213   if (s->bi_valid > (int)Buf_size - len) {\
  214     int val = (int)value;\
  215     s->bi_buf |= (ush)val << s->bi_valid;\
  216     put_short(s, s->bi_buf);\
  217     s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
  218     s->bi_valid += len - Buf_size;\
  219   } else {\
  220     s->bi_buf |= (ush)(value) << s->bi_valid;\
  221     s->bi_valid += len;\
  222   }\
  223 }
  224 #endif /* ZLIB_DEBUG */
  225 
  226 
  227 /* the arguments must not have side effects */
  228 
  229 /* ===========================================================================
  230  * Initialize the various 'constant' tables.
  231  */
  232 local void tr_static_init()
  233 {
  234 #if defined(GEN_TREES_H) || !defined(STDC)
  235     static int static_init_done = 0;
  236     int n;        /* iterates over tree elements */
  237     int bits;     /* bit counter */
  238     int length;   /* length value */
  239     int code;     /* code value */
  240     int dist;     /* distance index */
  241     ush bl_count[MAX_BITS+1];
  242     /* number of codes at each bit length for an optimal tree */
  243 
  244     if (static_init_done) return;
  245 
  246     /* For some embedded targets, global variables are not initialized: */
  247 #ifdef NO_INIT_GLOBAL_POINTERS
  248     static_l_desc.static_tree = static_ltree;
  249     static_l_desc.extra_bits = extra_lbits;
  250     static_d_desc.static_tree = static_dtree;
  251     static_d_desc.extra_bits = extra_dbits;
  252     static_bl_desc.extra_bits = extra_blbits;
  253 #endif
  254 
  255     /* Initialize the mapping length (0..255) -> length code (0..28) */
  256     length = 0;
  257     for (code = 0; code < LENGTH_CODES-1; code++) {
  258         base_length[code] = length;
  259         for (n = 0; n < (1<<extra_lbits[code]); n++) {
  260             _length_code[length++] = (uch)code;
  261         }
  262     }
  263     Assert (length == 256, "tr_static_init: length != 256");
  264     /* Note that the length 255 (match length 258) can be represented
  265      * in two different ways: code 284 + 5 bits or code 285, so we
  266      * overwrite length_code[255] to use the best encoding:
  267      */
  268     _length_code[length-1] = (uch)code;
  269 
  270     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
  271     dist = 0;
  272     for (code = 0 ; code < 16; code++) {
  273         base_dist[code] = dist;
  274         for (n = 0; n < (1<<extra_dbits[code]); n++) {
  275             _dist_code[dist++] = (uch)code;
  276         }
  277     }
  278     Assert (dist == 256, "tr_static_init: dist != 256");
  279     dist >>= 7; /* from now on, all distances are divided by 128 */
  280     for ( ; code < D_CODES; code++) {
  281         base_dist[code] = dist << 7;
  282         for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
  283             _dist_code[256 + dist++] = (uch)code;
  284         }
  285     }
  286     Assert (dist == 256, "tr_static_init: 256+dist != 512");
  287 
  288     /* Construct the codes of the static literal tree */
  289     for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
  290     n = 0;
  291     while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
  292     while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
  293     while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
  294     while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
  295     /* Codes 286 and 287 do not exist, but we must include them in the
  296      * tree construction to get a canonical Huffman tree (longest code
  297      * all ones)
  298      */
  299     gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
  300 
  301     /* The static distance tree is trivial: */
  302     for (n = 0; n < D_CODES; n++) {
  303         static_dtree[n].Len = 5;
  304         static_dtree[n].Code = bi_reverse((unsigned)n, 5);
  305     }
  306     static_init_done = 1;
  307 
  308 #  ifdef GEN_TREES_H
  309     gen_trees_header();
  310 #  endif
  311 #endif /* defined(GEN_TREES_H) || !defined(STDC) */
  312 }
  313 
  314 /* ===========================================================================
  315  * Genererate the file trees.h describing the static trees.
  316  */
  317 #ifdef GEN_TREES_H
  318 #  ifndef ZLIB_DEBUG
  319 #    include <stdio.h>
  320 #  endif
  321 
  322 #  define SEPARATOR(i, last, width) \
  323       ((i) == (last)? "\n};\n\n" :    \
  324        ((i) % (width) == (width)-1 ? ",\n" : ", "))
  325 
  326 void gen_trees_header()
  327 {
  328     FILE *header = fopen("trees.h", "w");
  329     int i;
  330 
  331     Assert (header != NULL, "Can't open trees.h");
  332     fprintf(header,
  333             "/* header created automatically with -DGEN_TREES_H */\n\n");
  334 
  335     fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
  336     for (i = 0; i < L_CODES+2; i++) {
  337         fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
  338                 static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
  339     }
  340 
  341     fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
  342     for (i = 0; i < D_CODES; i++) {
  343         fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
  344                 static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
  345     }
  346 
  347     fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
  348     for (i = 0; i < DIST_CODE_LEN; i++) {
  349         fprintf(header, "%2u%s", _dist_code[i],
  350                 SEPARATOR(i, DIST_CODE_LEN-1, 20));
  351     }
  352 
  353     fprintf(header,
  354         "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
  355     for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
  356         fprintf(header, "%2u%s", _length_code[i],
  357                 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
  358     }
  359 
  360     fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
  361     for (i = 0; i < LENGTH_CODES; i++) {
  362         fprintf(header, "%1u%s", base_length[i],
  363                 SEPARATOR(i, LENGTH_CODES-1, 20));
  364     }
  365 
  366     fprintf(header, "local const int base_dist[D_CODES] = {\n");
  367     for (i = 0; i < D_CODES; i++) {
  368         fprintf(header, "%5u%s", base_dist[i],
  369                 SEPARATOR(i, D_CODES-1, 10));
  370     }
  371 
  372     fclose(header);
  373 }
  374 #endif /* GEN_TREES_H */
  375 
  376 /* ===========================================================================
  377  * Initialize the tree data structures for a new zlib stream.
  378  */
  379 void ZLIB_INTERNAL _tr_init(s)
  380     deflate_state *s;
  381 {
  382     tr_static_init();
  383 
  384     s->l_desc.dyn_tree = s->dyn_ltree;
  385     s->l_desc.stat_desc = &static_l_desc;
  386 
  387     s->d_desc.dyn_tree = s->dyn_dtree;
  388     s->d_desc.stat_desc = &static_d_desc;
  389 
  390     s->bl_desc.dyn_tree = s->bl_tree;
  391     s->bl_desc.stat_desc = &static_bl_desc;
  392 
  393     s->bi_buf = 0;
  394     s->bi_valid = 0;
  395 #ifdef ZLIB_DEBUG
  396     s->compressed_len = 0L;
  397     s->bits_sent = 0L;
  398 #endif
  399 
  400     /* Initialize the first block of the first file: */
  401     init_block(s);
  402 }
  403 
  404 /* ===========================================================================
  405  * Initialize a new block.
  406  */
  407 local void init_block(s)
  408     deflate_state *s;
  409 {
  410     int n; /* iterates over tree elements */
  411 
  412     /* Initialize the trees. */
  413     for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;
  414     for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;
  415     for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
  416 
  417     s->dyn_ltree[END_BLOCK].Freq = 1;
  418     s->opt_len = s->static_len = 0L;
  419     s->last_lit = s->matches = 0;
  420 }
  421 
  422 #define SMALLEST 1
  423 /* Index within the heap array of least frequent node in the Huffman tree */
  424 
  425 
  426 /* ===========================================================================
  427  * Remove the smallest element from the heap and recreate the heap with
  428  * one less element. Updates heap and heap_len.
  429  */
  430 #define pqremove(s, tree, top) \
  431 {\
  432     top = s->heap[SMALLEST]; \
  433     s->heap[SMALLEST] = s->heap[s->heap_len--]; \
  434     pqdownheap(s, tree, SMALLEST); \
  435 }
  436 
  437 /* ===========================================================================
  438  * Compares to subtrees, using the tree depth as tie breaker when
  439  * the subtrees have equal frequency. This minimizes the worst case length.
  440  */
  441 #define smaller(tree, n, m, depth) \
  442    (tree[n].Freq < tree[m].Freq || \
  443    (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
  444 
  445 /* ===========================================================================
  446  * Restore the heap property by moving down the tree starting at node k,
  447  * exchanging a node with the smallest of its two sons if necessary, stopping
  448  * when the heap property is re-established (each father smaller than its
  449  * two sons).
  450  */
  451 local void pqdownheap(s, tree, k)
  452     deflate_state *s;
  453     ct_data *tree;  /* the tree to restore */
  454     int k;               /* node to move down */
  455 {
  456     int v = s->heap[k];
  457     int j = k << 1;  /* left son of k */
  458     while (j <= s->heap_len) {
  459         /* Set j to the smallest of the two sons: */
  460         if (j < s->heap_len &&
  461             smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
  462             j++;
  463         }
  464         /* Exit if v is smaller than both sons */
  465         if (smaller(tree, v, s->heap[j], s->depth)) break;
  466 
  467         /* Exchange v with the smallest son */
  468         s->heap[k] = s->heap[j];  k = j;
  469 
  470         /* And continue down the tree, setting j to the left son of k */
  471         j <<= 1;
  472     }
  473     s->heap[k] = v;
  474 }
  475 
  476 /* ===========================================================================
  477  * Compute the optimal bit lengths for a tree and update the total bit length
  478  * for the current block.
  479  * IN assertion: the fields freq and dad are set, heap[heap_max] and
  480  *    above are the tree nodes sorted by increasing frequency.
  481  * OUT assertions: the field len is set to the optimal bit length, the
  482  *     array bl_count contains the frequencies for each bit length.
  483  *     The length opt_len is updated; static_len is also updated if stree is
  484  *     not null.
  485  */
  486 local void gen_bitlen(s, desc)
  487     deflate_state *s;
  488     tree_desc *desc;    /* the tree descriptor */
  489 {
  490     ct_data *tree        = desc->dyn_tree;
  491     int max_code         = desc->max_code;
  492     const ct_data *stree = desc->stat_desc->static_tree;
  493     const intf *extra    = desc->stat_desc->extra_bits;
  494     int base             = desc->stat_desc->extra_base;
  495     int max_length       = desc->stat_desc->max_length;
  496     int h;              /* heap index */
  497     int n, m;           /* iterate over the tree elements */
  498     int bits;           /* bit length */
  499     int xbits;          /* extra bits */
  500     ush f;              /* frequency */
  501     int overflow = 0;   /* number of elements with bit length too large */
  502 
  503     for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
  504 
  505     /* In a first pass, compute the optimal bit lengths (which may
  506      * overflow in the case of the bit length tree).
  507      */
  508     tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
  509 
  510     for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
  511         n = s->heap[h];
  512         bits = tree[tree[n].Dad].Len + 1;
  513         if (bits > max_length) bits = max_length, overflow++;
  514         tree[n].Len = (ush)bits;
  515         /* We overwrite tree[n].Dad which is no longer needed */
  516 
  517         if (n > max_code) continue; /* not a leaf node */
  518 
  519         s->bl_count[bits]++;
  520         xbits = 0;
  521         if (n >= base) xbits = extra[n-base];
  522         f = tree[n].Freq;
  523         s->opt_len += (ulg)f * (unsigned)(bits + xbits);
  524         if (stree) s->static_len += (ulg)f * (unsigned)(stree[n].Len + xbits);
  525     }
  526     if (overflow == 0) return;
  527 
  528     Tracev((stderr,"\nbit length overflow\n"));
  529     /* This happens for example on obj2 and pic of the Calgary corpus */
  530 
  531     /* Find the first bit length which could increase: */
  532     do {
  533         bits = max_length-1;
  534         while (s->bl_count[bits] == 0) bits--;
  535         s->bl_count[bits]--;      /* move one leaf down the tree */
  536         s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
  537         s->bl_count[max_length]--;
  538         /* The brother of the overflow item also moves one step up,
  539          * but this does not affect bl_count[max_length]
  540          */
  541         overflow -= 2;
  542     } while (overflow > 0);
  543 
  544     /* Now recompute all bit lengths, scanning in increasing frequency.
  545      * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
  546      * lengths instead of fixing only the wrong ones. This idea is taken
  547      * from 'ar' written by Haruhiko Okumura.)
  548      */
  549     for (bits = max_length; bits != 0; bits--) {
  550         n = s->bl_count[bits];
  551         while (n != 0) {
  552             m = s->heap[--h];
  553             if (m > max_code) continue;
  554             if ((unsigned) tree[m].Len != (unsigned) bits) {
  555                 Tracev((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
  556                 s->opt_len += ((ulg)bits - tree[m].Len) * tree[m].Freq;
  557                 tree[m].Len = (ush)bits;
  558             }
  559             n--;
  560         }
  561     }
  562 }
  563 
  564 /* ===========================================================================
  565  * Generate the codes for a given tree and bit counts (which need not be
  566  * optimal).
  567  * IN assertion: the array bl_count contains the bit length statistics for
  568  * the given tree and the field len is set for all tree elements.
  569  * OUT assertion: the field code is set for all tree elements of non
  570  *     zero code length.
  571  */
  572 local void gen_codes (tree, max_code, bl_count)
  573     ct_data *tree;             /* the tree to decorate */
  574     int max_code;              /* largest code with non zero frequency */
  575     ushf *bl_count;            /* number of codes at each bit length */
  576 {
  577     ush next_code[MAX_BITS+1]; /* next code value for each bit length */
  578     unsigned code = 0;         /* running code value */
  579     int bits;                  /* bit index */
  580     int n;                     /* code index */
  581 
  582     /* The distribution counts are first used to generate the code values
  583      * without bit reversal.
  584      */
  585     for (bits = 1; bits <= MAX_BITS; bits++) {
  586         code = (code + bl_count[bits-1]) << 1;
  587         next_code[bits] = (ush)code;
  588     }
  589     /* Check that the bit counts in bl_count are consistent. The last code
  590      * must be all ones.
  591      */
  592     Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
  593             "inconsistent bit counts");
  594     Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
  595 
  596     for (n = 0;  n <= max_code; n++) {
  597         int len = tree[n].Len;
  598         if (len == 0) continue;
  599         /* Now reverse the bits */
  600         tree[n].Code = (ush)bi_reverse(next_code[len]++, len);
  601 
  602         Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
  603              n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
  604     }
  605 }
  606 
  607 /* ===========================================================================
  608  * Construct one Huffman tree and assigns the code bit strings and lengths.
  609  * Update the total bit length for the current block.
  610  * IN assertion: the field freq is set for all tree elements.
  611  * OUT assertions: the fields len and code are set to the optimal bit length
  612  *     and corresponding code. The length opt_len is updated; static_len is
  613  *     also updated if stree is not null. The field max_code is set.
  614  */
  615 local void build_tree(s, desc)
  616     deflate_state *s;
  617     tree_desc *desc; /* the tree descriptor */
  618 {
  619     ct_data *tree         = desc->dyn_tree;
  620     const ct_data *stree  = desc->stat_desc->static_tree;
  621     int elems             = desc->stat_desc->elems;
  622     int n, m;          /* iterate over heap elements */
  623     int max_code = -1; /* largest code with non zero frequency */
  624     int node;          /* new node being created */
  625 
  626     /* Construct the initial heap, with least frequent element in
  627      * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
  628      * heap[0] is not used.
  629      */
  630     s->heap_len = 0, s->heap_max = HEAP_SIZE;
  631 
  632     for (n = 0; n < elems; n++) {
  633         if (tree[n].Freq != 0) {
  634             s->heap[++(s->heap_len)] = max_code = n;
  635             s->depth[n] = 0;
  636         } else {
  637             tree[n].Len = 0;
  638         }
  639     }
  640 
  641     /* The pkzip format requires that at least one distance code exists,
  642      * and that at least one bit should be sent even if there is only one
  643      * possible code. So to avoid special checks later on we force at least
  644      * two codes of non zero frequency.
  645      */
  646     while (s->heap_len < 2) {
  647         node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
  648         tree[node].Freq = 1;
  649         s->depth[node] = 0;
  650         s->opt_len--; if (stree) s->static_len -= stree[node].Len;
  651         /* node is 0 or 1 so it does not have extra bits */
  652     }
  653     desc->max_code = max_code;
  654 
  655     /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
  656      * establish sub-heaps of increasing lengths:
  657      */
  658     for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
  659 
  660     /* Construct the Huffman tree by repeatedly combining the least two
  661      * frequent nodes.
  662      */
  663     node = elems;              /* next internal node of the tree */
  664     do {
  665         pqremove(s, tree, n);  /* n = node of least frequency */
  666         m = s->heap[SMALLEST]; /* m = node of next least frequency */
  667 
  668         s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
  669         s->heap[--(s->heap_max)] = m;
  670 
  671         /* Create a new node father of n and m */
  672         tree[node].Freq = tree[n].Freq + tree[m].Freq;
  673         s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
  674                                 s->depth[n] : s->depth[m]) + 1);
  675         tree[n].Dad = tree[m].Dad = (ush)node;
  676 #ifdef DUMP_BL_TREE
  677         if (tree == s->bl_tree) {
  678             fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
  679                     node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
  680         }
  681 #endif
  682         /* and insert the new node in the heap */
  683         s->heap[SMALLEST] = node++;
  684         pqdownheap(s, tree, SMALLEST);
  685 
  686     } while (s->heap_len >= 2);
  687 
  688     s->heap[--(s->heap_max)] = s->heap[SMALLEST];
  689 
  690     /* At this point, the fields freq and dad are set. We can now
  691      * generate the bit lengths.
  692      */
  693     gen_bitlen(s, (tree_desc *)desc);
  694 
  695     /* The field len is now set, we can generate the bit codes */
  696     gen_codes ((ct_data *)tree, max_code, s->bl_count);
  697 }
  698 
  699 /* ===========================================================================
  700  * Scan a literal or distance tree to determine the frequencies of the codes
  701  * in the bit length tree.
  702  */
  703 local void scan_tree (s, tree, max_code)
  704     deflate_state *s;
  705     ct_data *tree;   /* the tree to be scanned */
  706     int max_code;    /* and its largest code of non zero frequency */
  707 {
  708     int n;                     /* iterates over all tree elements */
  709     int prevlen = -1;          /* last emitted length */
  710     int curlen;                /* length of current code */
  711     int nextlen = tree[0].Len; /* length of next code */
  712     int count = 0;             /* repeat count of the current code */
  713     int max_count = 7;         /* max repeat count */
  714     int min_count = 4;         /* min repeat count */
  715 
  716     if (nextlen == 0) max_count = 138, min_count = 3;
  717     tree[max_code+1].Len = (ush)0xffff; /* guard */
  718 
  719     for (n = 0; n <= max_code; n++) {
  720         curlen = nextlen; nextlen = tree[n+1].Len;
  721         if (++count < max_count && curlen == nextlen) {
  722             continue;
  723         } else if (count < min_count) {
  724             s->bl_tree[curlen].Freq += count;
  725         } else if (curlen != 0) {
  726             if (curlen != prevlen) s->bl_tree[curlen].Freq++;
  727             s->bl_tree[REP_3_6].Freq++;
  728         } else if (count <= 10) {
  729             s->bl_tree[REPZ_3_10].Freq++;
  730         } else {
  731             s->bl_tree[REPZ_11_138].Freq++;
  732         }
  733         count = 0; prevlen = curlen;
  734         if (nextlen == 0) {
  735             max_count = 138, min_count = 3;
  736         } else if (curlen == nextlen) {
  737             max_count = 6, min_count = 3;
  738         } else {
  739             max_count = 7, min_count = 4;
  740         }
  741     }
  742 }
  743 
  744 /* ===========================================================================
  745  * Send a literal or distance tree in compressed form, using the codes in
  746  * bl_tree.
  747  */
  748 local void send_tree (s, tree, max_code)
  749     deflate_state *s;
  750     ct_data *tree; /* the tree to be scanned */
  751     int max_code;       /* and its largest code of non zero frequency */
  752 {
  753     int n;                     /* iterates over all tree elements */
  754     int prevlen = -1;          /* last emitted length */
  755     int curlen;                /* length of current code */
  756     int nextlen = tree[0].Len; /* length of next code */
  757     int count = 0;             /* repeat count of the current code */
  758     int max_count = 7;         /* max repeat count */
  759     int min_count = 4;         /* min repeat count */
  760 
  761     /* tree[max_code+1].Len = -1; */  /* guard already set */
  762     if (nextlen == 0) max_count = 138, min_count = 3;
  763 
  764     for (n = 0; n <= max_code; n++) {
  765         curlen = nextlen; nextlen = tree[n+1].Len;
  766         if (++count < max_count && curlen == nextlen) {
  767             continue;
  768         } else if (count < min_count) {
  769             do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
  770 
  771         } else if (curlen != 0) {
  772             if (curlen != prevlen) {
  773                 send_code(s, curlen, s->bl_tree); count--;
  774             }
  775             Assert(count >= 3 && count <= 6, " 3_6?");
  776             send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
  777 
  778         } else if (count <= 10) {
  779             send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
  780 
  781         } else {
  782             send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
  783         }
  784         count = 0; prevlen = curlen;
  785         if (nextlen == 0) {
  786             max_count = 138, min_count = 3;
  787         } else if (curlen == nextlen) {
  788             max_count = 6, min_count = 3;
  789         } else {
  790             max_count = 7, min_count = 4;
  791         }
  792     }
  793 }
  794 
  795 /* ===========================================================================
  796  * Construct the Huffman tree for the bit lengths and return the index in
  797  * bl_order of the last bit length code to send.
  798  */
  799 local int build_bl_tree(s)
  800     deflate_state *s;
  801 {
  802     int max_blindex;  /* index of last bit length code of non zero freq */
  803 
  804     /* Determine the bit length frequencies for literal and distance trees */
  805     scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
  806     scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
  807 
  808     /* Build the bit length tree: */
  809     build_tree(s, (tree_desc *)(&(s->bl_desc)));
  810     /* opt_len now includes the length of the tree representations, except
  811      * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
  812      */
  813 
  814     /* Determine the number of bit length codes to send. The pkzip format
  815      * requires that at least 4 bit length codes be sent. (appnote.txt says
  816      * 3 but the actual value used is 4.)
  817      */
  818     for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
  819         if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
  820     }
  821     /* Update opt_len to include the bit length tree and counts */
  822     s->opt_len += 3*((ulg)max_blindex+1) + 5+5+4;
  823     Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
  824             s->opt_len, s->static_len));
  825 
  826     return max_blindex;
  827 }
  828 
  829 /* ===========================================================================
  830  * Send the header for a block using dynamic Huffman trees: the counts, the
  831  * lengths of the bit length codes, the literal tree and the distance tree.
  832  * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
  833  */
  834 local void send_all_trees(s, lcodes, dcodes, blcodes)
  835     deflate_state *s;
  836     int lcodes, dcodes, blcodes; /* number of codes for each tree */
  837 {
  838     int rank;                    /* index in bl_order */
  839 
  840     Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
  841     Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
  842             "too many codes");
  843     Tracev((stderr, "\nbl counts: "));
  844     send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
  845     send_bits(s, dcodes-1,   5);
  846     send_bits(s, blcodes-4,  4); /* not -3 as stated in appnote.txt */
  847     for (rank = 0; rank < blcodes; rank++) {
  848         Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
  849         send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
  850     }
  851     Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
  852 
  853     send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
  854     Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
  855 
  856     send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
  857     Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
  858 }
  859 
  860 /* ===========================================================================
  861  * Send a stored block
  862  */
  863 void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last)
  864     deflate_state *s;
  865     charf *buf;       /* input block */
  866     ulg stored_len;   /* length of input block */
  867     int last;         /* one if this is the last block for a file */
  868 {
  869     send_bits(s, (STORED_BLOCK<<1)+last, 3);    /* send block type */
  870     bi_windup(s);        /* align on byte boundary */
  871     put_short(s, (ush)stored_len);
  872     put_short(s, (ush)~stored_len);
  873     zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
  874     s->pending += stored_len;
  875 #ifdef ZLIB_DEBUG
  876     s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
  877     s->compressed_len += (stored_len + 4) << 3;
  878     s->bits_sent += 2*16;
  879     s->bits_sent += stored_len<<3;
  880 #endif
  881 }
  882 
  883 /* ===========================================================================
  884  * Flush the bits in the bit buffer to pending output (leaves at most 7 bits)
  885  */
  886 void ZLIB_INTERNAL _tr_flush_bits(s)
  887     deflate_state *s;
  888 {
  889     bi_flush(s);
  890 }
  891 
  892 /* ===========================================================================
  893  * Send one empty static block to give enough lookahead for inflate.
  894  * This takes 10 bits, of which 7 may remain in the bit buffer.
  895  */
  896 void ZLIB_INTERNAL _tr_align(s)
  897     deflate_state *s;
  898 {
  899     send_bits(s, STATIC_TREES<<1, 3);
  900     send_code(s, END_BLOCK, static_ltree);
  901 #ifdef ZLIB_DEBUG
  902     s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
  903 #endif
  904     bi_flush(s);
  905 }
  906 
  907 /* ===========================================================================
  908  * Determine the best encoding for the current block: dynamic trees, static
  909  * trees or store, and write out the encoded block.
  910  */
  911 void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last)
  912     deflate_state *s;
  913     charf *buf;       /* input block, or NULL if too old */
  914     ulg stored_len;   /* length of input block */
  915     int last;         /* one if this is the last block for a file */
  916 {
  917     ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
  918     int max_blindex = 0;  /* index of last bit length code of non zero freq */
  919 
  920     /* Build the Huffman trees unless a stored block is forced */
  921     if (s->level > 0) {
  922 
  923         /* Check if the file is binary or text */
  924         if (s->strm->data_type == Z_UNKNOWN)
  925             s->strm->data_type = detect_data_type(s);
  926 
  927         /* Construct the literal and distance trees */
  928         build_tree(s, (tree_desc *)(&(s->l_desc)));
  929         Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
  930                 s->static_len));
  931 
  932         build_tree(s, (tree_desc *)(&(s->d_desc)));
  933         Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
  934                 s->static_len));
  935         /* At this point, opt_len and static_len are the total bit lengths of
  936          * the compressed block data, excluding the tree representations.
  937          */
  938 
  939         /* Build the bit length tree for the above two trees, and get the index
  940          * in bl_order of the last bit length code to send.
  941          */
  942         max_blindex = build_bl_tree(s);
  943 
  944         /* Determine the best encoding. Compute the block lengths in bytes. */
  945         opt_lenb = (s->opt_len+3+7)>>3;
  946         static_lenb = (s->static_len+3+7)>>3;
  947 
  948         Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
  949                 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
  950                 s->last_lit));
  951 
  952         if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
  953 
  954     } else {
  955         Assert(buf != (char*)0, "lost buf");
  956         opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
  957     }
  958 
  959 #ifdef FORCE_STORED
  960     if (buf != (char*)0) { /* force stored block */
  961 #else
  962     if (stored_len+4 <= opt_lenb && buf != (char*)0) {
  963                        /* 4: two words for the lengths */
  964 #endif
  965         /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
  966          * Otherwise we can't have processed more than WSIZE input bytes since
  967          * the last block flush, because compression would have been
  968          * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
  969          * transform a block into a stored block.
  970          */
  971         _tr_stored_block(s, buf, stored_len, last);
  972 
  973 #ifdef FORCE_STATIC
  974     } else if (static_lenb >= 0) { /* force static trees */
  975 #else
  976     } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
  977 #endif
  978         send_bits(s, (STATIC_TREES<<1)+last, 3);
  979         compress_block(s, (const ct_data *)static_ltree,
  980                        (const ct_data *)static_dtree);
  981 #ifdef ZLIB_DEBUG
  982         s->compressed_len += 3 + s->static_len;
  983 #endif
  984     } else {
  985         send_bits(s, (DYN_TREES<<1)+last, 3);
  986         send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
  987                        max_blindex+1);
  988         compress_block(s, (const ct_data *)s->dyn_ltree,
  989                        (const ct_data *)s->dyn_dtree);
  990 #ifdef ZLIB_DEBUG
  991         s->compressed_len += 3 + s->opt_len;
  992 #endif
  993     }
  994     Assert (s->compressed_len == s->bits_sent, "bad compressed size");
  995     /* The above check is made mod 2^32, for files larger than 512 MB
  996      * and uLong implemented on 32 bits.
  997      */
  998     init_block(s);
  999 
 1000     if (last) {
 1001         bi_windup(s);
 1002 #ifdef ZLIB_DEBUG
 1003         s->compressed_len += 7;  /* align on byte boundary */
 1004 #endif
 1005     }
 1006     Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
 1007            s->compressed_len-7*last));
 1008 }
 1009 
 1010 /* ===========================================================================
 1011  * Save the match info and tally the frequency counts. Return true if
 1012  * the current block must be flushed.
 1013  */
 1014 int ZLIB_INTERNAL _tr_tally (s, dist, lc)
 1015     deflate_state *s;
 1016     unsigned dist;  /* distance of matched string */
 1017     unsigned lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */
 1018 {
 1019     s->d_buf[s->last_lit] = (ush)dist;
 1020     s->l_buf[s->last_lit++] = (uch)lc;
 1021     if (dist == 0) {
 1022         /* lc is the unmatched char */
 1023         s->dyn_ltree[lc].Freq++;
 1024     } else {
 1025         s->matches++;
 1026         /* Here, lc is the match length - MIN_MATCH */
 1027         dist--;             /* dist = match distance - 1 */
 1028         Assert((ush)dist < (ush)MAX_DIST(s) &&
 1029                (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
 1030                (ush)d_code(dist) < (ush)D_CODES,  "_tr_tally: bad match");
 1031 
 1032         s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
 1033         s->dyn_dtree[d_code(dist)].Freq++;
 1034     }
 1035 
 1036 #ifdef TRUNCATE_BLOCK
 1037     /* Try to guess if it is profitable to stop the current block here */
 1038     if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
 1039         /* Compute an upper bound for the compressed length */
 1040         ulg out_length = (ulg)s->last_lit*8L;
 1041         ulg in_length = (ulg)((long)s->strstart - s->block_start);
 1042         int dcode;
 1043         for (dcode = 0; dcode < D_CODES; dcode++) {
 1044             out_length += (ulg)s->dyn_dtree[dcode].Freq *
 1045                 (5L+extra_dbits[dcode]);
 1046         }
 1047         out_length >>= 3;
 1048         Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
 1049                s->last_lit, in_length, out_length,
 1050                100L - out_length*100L/in_length));
 1051         if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
 1052     }
 1053 #endif
 1054     return (s->last_lit == s->lit_bufsize-1);
 1055     /* We avoid equality with lit_bufsize because of wraparound at 64K
 1056      * on 16 bit machines and because stored blocks are restricted to
 1057      * 64K-1 bytes.
 1058      */
 1059 }
 1060 
 1061 /* ===========================================================================
 1062  * Send the block data compressed using the given Huffman trees
 1063  */
 1064 local void compress_block(s, ltree, dtree)
 1065     deflate_state *s;
 1066     const ct_data *ltree; /* literal tree */
 1067     const ct_data *dtree; /* distance tree */
 1068 {
 1069     unsigned dist;      /* distance of matched string */
 1070     int lc;             /* match length or unmatched char (if dist == 0) */
 1071     unsigned lx = 0;    /* running index in l_buf */
 1072     unsigned code;      /* the code to send */
 1073     int extra;          /* number of extra bits to send */
 1074 
 1075     if (s->last_lit != 0) do {
 1076         dist = s->d_buf[lx];
 1077         lc = s->l_buf[lx++];
 1078         if (dist == 0) {
 1079             send_code(s, lc, ltree); /* send a literal byte */
 1080             Tracecv(isgraph(lc), (stderr," '%c' ", lc));
 1081         } else {
 1082             /* Here, lc is the match length - MIN_MATCH */
 1083             code = _length_code[lc];
 1084             send_code(s, code+LITERALS+1, ltree); /* send the length code */
 1085             extra = extra_lbits[code];
 1086             if (extra != 0) {
 1087                 lc -= base_length[code];
 1088                 send_bits(s, lc, extra);       /* send the extra length bits */
 1089             }
 1090             dist--; /* dist is now the match distance - 1 */
 1091             code = d_code(dist);
 1092             Assert (code < D_CODES, "bad d_code");
 1093 
 1094             send_code(s, code, dtree);       /* send the distance code */
 1095             extra = extra_dbits[code];
 1096             if (extra != 0) {
 1097                 dist -= (unsigned)base_dist[code];
 1098                 send_bits(s, dist, extra);   /* send the extra distance bits */
 1099             }
 1100         } /* literal or match pair ? */
 1101 
 1102         /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
 1103         Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
 1104                "pendingBuf overflow");
 1105 
 1106     } while (lx < s->last_lit);
 1107 
 1108     send_code(s, END_BLOCK, ltree);
 1109 }
 1110 
 1111 /* ===========================================================================
 1112  * Check if the data type is TEXT or BINARY, using the following algorithm:
 1113  * - TEXT if the two conditions below are satisfied:
 1114  *    a) There are no non-portable control characters belonging to the
 1115  *       "black list" (0..6, 14..25, 28..31).
 1116  *    b) There is at least one printable character belonging to the
 1117  *       "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
 1118  * - BINARY otherwise.
 1119  * - The following partially-portable control characters form a
 1120  *   "gray list" that is ignored in this detection algorithm:
 1121  *   (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
 1122  * IN assertion: the fields Freq of dyn_ltree are set.
 1123  */
 1124 local int detect_data_type(s)
 1125     deflate_state *s;
 1126 {
 1127     /* black_mask is the bit mask of black-listed bytes
 1128      * set bits 0..6, 14..25, and 28..31
 1129      * 0xf3ffc07f = binary 11110011111111111100000001111111
 1130      */
 1131     unsigned long black_mask = 0xf3ffc07fUL;
 1132     int n;
 1133 
 1134     /* Check for non-textual ("black-listed") bytes. */
 1135     for (n = 0; n <= 31; n++, black_mask >>= 1)
 1136         if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
 1137             return Z_BINARY;
 1138 
 1139     /* Check for textual ("white-listed") bytes. */
 1140     if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
 1141             || s->dyn_ltree[13].Freq != 0)
 1142         return Z_TEXT;
 1143     for (n = 32; n < LITERALS; n++)
 1144         if (s->dyn_ltree[n].Freq != 0)
 1145             return Z_TEXT;
 1146 
 1147     /* There are no "black-listed" or "white-listed" bytes:
 1148      * this stream either is empty or has tolerated ("gray-listed") bytes only.
 1149      */
 1150     return Z_BINARY;
 1151 }
 1152 
 1153 /* ===========================================================================
 1154  * Reverse the first len bits of a code, using straightforward code (a faster
 1155  * method would use a table)
 1156  * IN assertion: 1 <= len <= 15
 1157  */
 1158 local unsigned bi_reverse(code, len)
 1159     unsigned code; /* the value to invert */
 1160     int len;       /* its bit length */
 1161 {
 1162     register unsigned res = 0;
 1163     do {
 1164         res |= code & 1;
 1165         code >>= 1, res <<= 1;
 1166     } while (--len > 0);
 1167     return res >> 1;
 1168 }
 1169 
 1170 /* ===========================================================================
 1171  * Flush the bit buffer, keeping at most 7 bits in it.
 1172  */
 1173 local void bi_flush(s)
 1174     deflate_state *s;
 1175 {
 1176     if (s->bi_valid == 16) {
 1177         put_short(s, s->bi_buf);
 1178         s->bi_buf = 0;
 1179         s->bi_valid = 0;
 1180     } else if (s->bi_valid >= 8) {
 1181         put_byte(s, (Byte)s->bi_buf);
 1182         s->bi_buf >>= 8;
 1183         s->bi_valid -= 8;
 1184     }
 1185 }
 1186 
 1187 /* ===========================================================================
 1188  * Flush the bit buffer and align the output on a byte boundary
 1189  */
 1190 local void bi_windup(s)
 1191     deflate_state *s;
 1192 {
 1193     if (s->bi_valid > 8) {
 1194         put_short(s, s->bi_buf);
 1195     } else if (s->bi_valid > 0) {
 1196         put_byte(s, (Byte)s->bi_buf);
 1197     }
 1198     s->bi_buf = 0;
 1199     s->bi_valid = 0;
 1200 #ifdef ZLIB_DEBUG
 1201     s->bits_sent = (s->bits_sent+7) & ~7;
 1202 #endif
 1203 }