1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Oracle designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Oracle in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  */

    24 

    25 /* trees.c -- output deflated data using Huffman coding

    26  * Copyright (C) 1995-2012 Jean-loup Gailly

    27  * detect_data_type() function provided freely by Cosmin Truta, 2006

    28  * For conditions of distribution and use, see copyright notice in zlib.h

    29  */

    30 

    31 /*

    32  *  ALGORITHM

    33  *

    34  *      The "deflation" process uses several Huffman trees. The more

    35  *      common source values are represented by shorter bit sequences.

    36  *

    37  *      Each code tree is stored in a compressed form which is itself

    38  * a Huffman encoding of the lengths of all the code strings (in

    39  * ascending order by source values).  The actual code strings are

    40  * reconstructed from the lengths in the inflate process, as described

    41  * in the deflate specification.

    42  *

    43  *  REFERENCES

    44  *

    45  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".

    46  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc

    47  *

    48  *      Storer, James A.

    49  *          Data Compression:  Methods and Theory, pp. 49-50.

    50  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.

    51  *

    52  *      Sedgewick, R.

    53  *          Algorithms, p290.

    54  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.

    55  */

    56 

    57 /* @(#) $Id$ */

    58 

    59 /* #define GEN_TREES_H */

    60 

    61 #include "deflate.h"

    62 

    63 #ifdef DEBUG

    64 #  include <ctype.h>

    65 #endif

    66 

    67 /* ===========================================================================

    68  * Constants

    69  */

    70 

    71 #define MAX_BL_BITS 7

    72 /* Bit length codes must not exceed MAX_BL_BITS bits */

    73 

    74 #define END_BLOCK 256

    75 /* end of block literal code */

    76 

    77 #define REP_3_6      16

    78 /* repeat previous bit length 3-6 times (2 bits of repeat count) */

    79 

    80 #define REPZ_3_10    17

    81 /* repeat a zero length 3-10 times  (3 bits of repeat count) */

    82 

    83 #define REPZ_11_138  18

    84 /* repeat a zero length 11-138 times  (7 bits of repeat count) */

    85 

    86 local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */

    87    = {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};

    88 

    89 local const int extra_dbits[D_CODES] /* extra bits for each distance code */

    90    = {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};

    91 

    92 local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */

    93    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};

    94 

    95 local const uch bl_order[BL_CODES]

    96    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};

    97 /* The lengths of the bit length codes are sent in order of decreasing

    98  * probability, to avoid transmitting the lengths for unused bit length codes.

    99  */

   100 

   101 /* ===========================================================================

   102  * Local data. These are initialized only once.

   103  */

   104 

   105 #define DIST_CODE_LEN  512 /* see definition of array dist_code below */

   106 

   107 #if defined(GEN_TREES_H) || !defined(STDC)

   108 /* non ANSI compilers may not accept trees.h */

   109 

   110 local ct_data static_ltree[L_CODES+2];

   111 /* The static literal tree. Since the bit lengths are imposed, there is no

   112  * need for the L_CODES extra codes used during heap construction. However

   113  * The codes 286 and 287 are needed to build a canonical tree (see _tr_init

   114  * below).

   115  */

   116 

   117 local ct_data static_dtree[D_CODES];

   118 /* The static distance tree. (Actually a trivial tree since all codes use

   119  * 5 bits.)

   120  */

   121 

   122 uch _dist_code[DIST_CODE_LEN];

   123 /* Distance codes. The first 256 values correspond to the distances

   124  * 3 .. 258, the last 256 values correspond to the top 8 bits of

   125  * the 15 bit distances.

   126  */

   127 

   128 uch _length_code[MAX_MATCH-MIN_MATCH+1];

   129 /* length code for each normalized match length (0 == MIN_MATCH) */

   130 

   131 local int base_length[LENGTH_CODES];

   132 /* First normalized length for each code (0 = MIN_MATCH) */

   133 

   134 local int base_dist[D_CODES];

   135 /* First normalized distance for each code (0 = distance of 1) */

   136 

   137 #else

   138 #  include "trees.h"

   139 #endif /* GEN_TREES_H */

   140 

   141 struct static_tree_desc_s {

   142     const ct_data *static_tree;  /* static tree or NULL */

   143     const intf *extra_bits;      /* extra bits for each code or NULL */

   144     int     extra_base;          /* base index for extra_bits */

   145     int     elems;               /* max number of elements in the tree */

   146     int     max_length;          /* max bit length for the codes */

   147 };

   148 

   149 local static_tree_desc  static_l_desc =

   150 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};

   151 

   152 local static_tree_desc  static_d_desc =

   153 {static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};

   154 

   155 local static_tree_desc  static_bl_desc =

   156 {(const ct_data *)0, extra_blbits, 0,   BL_CODES, MAX_BL_BITS};

   157 

   158 /* ===========================================================================

   159  * Local (static) routines in this file.

   160  */

   161 

   162 local void tr_static_init OF((void));

   163 local void init_block     OF((deflate_state *s));

   164 local void pqdownheap     OF((deflate_state *s, ct_data *tree, int k));

   165 local void gen_bitlen     OF((deflate_state *s, tree_desc *desc));

   166 local void gen_codes      OF((ct_data *tree, int max_code, ushf *bl_count));

   167 local void build_tree     OF((deflate_state *s, tree_desc *desc));

   168 local void scan_tree      OF((deflate_state *s, ct_data *tree, int max_code));

   169 local void send_tree      OF((deflate_state *s, ct_data *tree, int max_code));

   170 local int  build_bl_tree  OF((deflate_state *s));

   171 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,

   172                               int blcodes));

   173 local void compress_block OF((deflate_state *s, const ct_data *ltree,

   174                               const ct_data *dtree));

   175 local int  detect_data_type OF((deflate_state *s));

   176 local unsigned bi_reverse OF((unsigned value, int length));

   177 local void bi_windup      OF((deflate_state *s));

   178 local void bi_flush       OF((deflate_state *s));

   179 local void copy_block     OF((deflate_state *s, charf *buf, unsigned len,

   180                               int header));

   181 

   182 #ifdef GEN_TREES_H

   183 local void gen_trees_header OF((void));

   184 #endif

   185 

   186 #ifndef DEBUG

   187 #  define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)

   188    /* Send a code of the given tree. c and tree must not have side effects */

   189 

   190 #else /* DEBUG */

   191 #  define send_code(s, c, tree) \

   192      { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \

   193        send_bits(s, tree[c].Code, tree[c].Len); }

   194 #endif

   195 

   196 /* ===========================================================================

   197  * Output a short LSB first on the stream.

   198  * IN assertion: there is enough room in pendingBuf.

   199  */

   200 #define put_short(s, w) { \

   201     put_byte(s, (uch)((w) & 0xff)); \

   202     put_byte(s, (uch)((ush)(w) >> 8)); \

   203 }

   204 

   205 /* ===========================================================================

   206  * Send a value on a given number of bits.

   207  * IN assertion: length <= 16 and value fits in length bits.

   208  */

   209 #ifdef DEBUG

   210 local void send_bits      OF((deflate_state *s, int value, int length));

   211 

   212 local void send_bits(s, value, length)

   213     deflate_state *s;

   214     int value;  /* value to send */

   215     int length; /* number of bits */

   216 {

   217     Tracevv((stderr," l %2d v %4x ", length, value));

   218     Assert(length > 0 && length <= 15, "invalid length");

   219     s->bits_sent += (ulg)length;

   220 

   221     /* If not enough room in bi_buf, use (valid) bits from bi_buf and

   222      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))

   223      * unused bits in value.

   224      */

   225     if (s->bi_valid > (int)Buf_size - length) {

   226         s->bi_buf |= (ush)value << s->bi_valid;

   227         put_short(s, s->bi_buf);

   228         s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);

   229         s->bi_valid += length - Buf_size;

   230     } else {

   231         s->bi_buf |= (ush)value << s->bi_valid;

   232         s->bi_valid += length;

   233     }

   234 }

   235 #else /* !DEBUG */

   236 

   237 #define send_bits(s, value, length) \

   238 { int len = length;\

   239   if (s->bi_valid > (int)Buf_size - len) {\

   240     int val = value;\

   241     s->bi_buf |= (ush)val << s->bi_valid;\

   242     put_short(s, s->bi_buf);\

   243     s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\

   244     s->bi_valid += len - Buf_size;\

   245   } else {\

   246     s->bi_buf |= (ush)(value) << s->bi_valid;\

   247     s->bi_valid += len;\

   248   }\

   249 }

   250 #endif /* DEBUG */

   251 

   252 

   253 /* the arguments must not have side effects */

   254 

   255 /* ===========================================================================

   256  * Initialize the various 'constant' tables.

   257  */

   258 local void tr_static_init()

   259 {

   260 #if defined(GEN_TREES_H) || !defined(STDC)

   261     static int static_init_done = 0;

   262     int n;        /* iterates over tree elements */

   263     int bits;     /* bit counter */

   264     int length;   /* length value */

   265     int code;     /* code value */

   266     int dist;     /* distance index */

   267     ush bl_count[MAX_BITS+1];

   268     /* number of codes at each bit length for an optimal tree */

   269 

   270     if (static_init_done) return;

   271 

   272     /* For some embedded targets, global variables are not initialized: */

   273 #ifdef NO_INIT_GLOBAL_POINTERS

   274     static_l_desc.static_tree = static_ltree;

   275     static_l_desc.extra_bits = extra_lbits;

   276     static_d_desc.static_tree = static_dtree;

   277     static_d_desc.extra_bits = extra_dbits;

   278     static_bl_desc.extra_bits = extra_blbits;

   279 #endif

   280 

   281     /* Initialize the mapping length (0..255) -> length code (0..28) */

   282     length = 0;

   283     for (code = 0; code < LENGTH_CODES-1; code++) {

   284         base_length[code] = length;

   285         for (n = 0; n < (1<<extra_lbits[code]); n++) {

   286             _length_code[length++] = (uch)code;

   287         }

   288     }

   289     Assert (length == 256, "tr_static_init: length != 256");

   290     /* Note that the length 255 (match length 258) can be represented

   291      * in two different ways: code 284 + 5 bits or code 285, so we

   292      * overwrite length_code[255] to use the best encoding:

   293      */

   294     _length_code[length-1] = (uch)code;

   295 

   296     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */

   297     dist = 0;

   298     for (code = 0 ; code < 16; code++) {

   299         base_dist[code] = dist;

   300         for (n = 0; n < (1<<extra_dbits[code]); n++) {

   301             _dist_code[dist++] = (uch)code;

   302         }

   303     }

   304     Assert (dist == 256, "tr_static_init: dist != 256");

   305     dist >>= 7; /* from now on, all distances are divided by 128 */

   306     for ( ; code < D_CODES; code++) {

   307         base_dist[code] = dist << 7;

   308         for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {

   309             _dist_code[256 + dist++] = (uch)code;

   310         }

   311     }

   312     Assert (dist == 256, "tr_static_init: 256+dist != 512");

   313 

   314     /* Construct the codes of the static literal tree */

   315     for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;

   316     n = 0;

   317     while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;

   318     while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;

   319     while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;

   320     while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;

   321     /* Codes 286 and 287 do not exist, but we must include them in the

   322      * tree construction to get a canonical Huffman tree (longest code

   323      * all ones)

   324      */

   325     gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);

   326 

   327     /* The static distance tree is trivial: */

   328     for (n = 0; n < D_CODES; n++) {

   329         static_dtree[n].Len = 5;

   330         static_dtree[n].Code = bi_reverse((unsigned)n, 5);

   331     }

   332     static_init_done = 1;

   333 

   334 #  ifdef GEN_TREES_H

   335     gen_trees_header();

   336 #  endif

   337 #endif /* defined(GEN_TREES_H) || !defined(STDC) */

   338 }

   339 

   340 /* ===========================================================================

   341  * Genererate the file trees.h describing the static trees.

   342  */

   343 #ifdef GEN_TREES_H

   344 #  ifndef DEBUG

   345 #    include <stdio.h>

   346 #  endif

   347 

   348 #  define SEPARATOR(i, last, width) \

   349       ((i) == (last)? "\n};\n\n" :    \

   350        ((i) % (width) == (width)-1 ? ",\n" : ", "))

   351 

   352 void gen_trees_header()

   353 {

   354     FILE *header = fopen("trees.h", "w");

   355     int i;

   356 

   357     Assert (header != NULL, "Can't open trees.h");

   358     fprintf(header,

   359             "/* header created automatically with -DGEN_TREES_H */\n\n");

   360 

   361     fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");

   362     for (i = 0; i < L_CODES+2; i++) {

   363         fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,

   364                 static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));

   365     }

   366 

   367     fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");

   368     for (i = 0; i < D_CODES; i++) {

   369         fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,

   370                 static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));

   371     }

   372 

   373     fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");

   374     for (i = 0; i < DIST_CODE_LEN; i++) {

   375         fprintf(header, "%2u%s", _dist_code[i],

   376                 SEPARATOR(i, DIST_CODE_LEN-1, 20));

   377     }

   378 

   379     fprintf(header,

   380         "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");

   381     for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {

   382         fprintf(header, "%2u%s", _length_code[i],

   383                 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));

   384     }

   385 

   386     fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");

   387     for (i = 0; i < LENGTH_CODES; i++) {

   388         fprintf(header, "%1u%s", base_length[i],

   389                 SEPARATOR(i, LENGTH_CODES-1, 20));

   390     }

   391 

   392     fprintf(header, "local const int base_dist[D_CODES] = {\n");

   393     for (i = 0; i < D_CODES; i++) {

   394         fprintf(header, "%5u%s", base_dist[i],

   395                 SEPARATOR(i, D_CODES-1, 10));

   396     }

   397 

   398     fclose(header);

   399 }

   400 #endif /* GEN_TREES_H */

   401 

   402 /* ===========================================================================

   403  * Initialize the tree data structures for a new zlib stream.

   404  */

   405 void ZLIB_INTERNAL _tr_init(s)

   406     deflate_state *s;

   407 {

   408     tr_static_init();

   409 

   410     s->l_desc.dyn_tree = s->dyn_ltree;

   411     s->l_desc.stat_desc = &static_l_desc;

   412 

   413     s->d_desc.dyn_tree = s->dyn_dtree;

   414     s->d_desc.stat_desc = &static_d_desc;

   415 

   416     s->bl_desc.dyn_tree = s->bl_tree;

   417     s->bl_desc.stat_desc = &static_bl_desc;

   418 

   419     s->bi_buf = 0;

   420     s->bi_valid = 0;

   421 #ifdef DEBUG

   422     s->compressed_len = 0L;

   423     s->bits_sent = 0L;

   424 #endif

   425 

   426     /* Initialize the first block of the first file: */

   427     init_block(s);

   428 }

   429 

   430 /* ===========================================================================

   431  * Initialize a new block.

   432  */

   433 local void init_block(s)

   434     deflate_state *s;

   435 {

   436     int n; /* iterates over tree elements */

   437 

   438     /* Initialize the trees. */

   439     for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;

   440     for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;

   441     for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;

   442 

   443     s->dyn_ltree[END_BLOCK].Freq = 1;

   444     s->opt_len = s->static_len = 0L;

   445     s->last_lit = s->matches = 0;

   446 }

   447 

   448 #define SMALLEST 1

   449 /* Index within the heap array of least frequent node in the Huffman tree */

   450 

   451 

   452 /* ===========================================================================

   453  * Remove the smallest element from the heap and recreate the heap with

   454  * one less element. Updates heap and heap_len.

   455  */

   456 #define pqremove(s, tree, top) \

   457 {\

   458     top = s->heap[SMALLEST]; \

   459     s->heap[SMALLEST] = s->heap[s->heap_len--]; \

   460     pqdownheap(s, tree, SMALLEST); \

   461 }

   462 

   463 /* ===========================================================================

   464  * Compares to subtrees, using the tree depth as tie breaker when

   465  * the subtrees have equal frequency. This minimizes the worst case length.

   466  */

   467 #define smaller(tree, n, m, depth) \

   468    (tree[n].Freq < tree[m].Freq || \

   469    (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))

   470 

   471 /* ===========================================================================

   472  * Restore the heap property by moving down the tree starting at node k,

   473  * exchanging a node with the smallest of its two sons if necessary, stopping

   474  * when the heap property is re-established (each father smaller than its

   475  * two sons).

   476  */

   477 local void pqdownheap(s, tree, k)

   478     deflate_state *s;

   479     ct_data *tree;  /* the tree to restore */

   480     int k;               /* node to move down */

   481 {

   482     int v = s->heap[k];

   483     int j = k << 1;  /* left son of k */

   484     while (j <= s->heap_len) {

   485         /* Set j to the smallest of the two sons: */

   486         if (j < s->heap_len &&

   487             smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {

   488             j++;

   489         }

   490         /* Exit if v is smaller than both sons */

   491         if (smaller(tree, v, s->heap[j], s->depth)) break;

   492 

   493         /* Exchange v with the smallest son */

   494         s->heap[k] = s->heap[j];  k = j;

   495 

   496         /* And continue down the tree, setting j to the left son of k */

   497         j <<= 1;

   498     }

   499     s->heap[k] = v;

   500 }

   501 

   502 /* ===========================================================================

   503  * Compute the optimal bit lengths for a tree and update the total bit length

   504  * for the current block.

   505  * IN assertion: the fields freq and dad are set, heap[heap_max] and

   506  *    above are the tree nodes sorted by increasing frequency.

   507  * OUT assertions: the field len is set to the optimal bit length, the

   508  *     array bl_count contains the frequencies for each bit length.

   509  *     The length opt_len is updated; static_len is also updated if stree is

   510  *     not null.

   511  */

   512 local void gen_bitlen(s, desc)

   513     deflate_state *s;

   514     tree_desc *desc;    /* the tree descriptor */

   515 {

   516     ct_data *tree        = desc->dyn_tree;

   517     int max_code         = desc->max_code;

   518     const ct_data *stree = desc->stat_desc->static_tree;

   519     const intf *extra    = desc->stat_desc->extra_bits;

   520     int base             = desc->stat_desc->extra_base;

   521     int max_length       = desc->stat_desc->max_length;

   522     int h;              /* heap index */

   523     int n, m;           /* iterate over the tree elements */

   524     int bits;           /* bit length */

   525     int xbits;          /* extra bits */

   526     ush f;              /* frequency */

   527     int overflow = 0;   /* number of elements with bit length too large */

   528 

   529     for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;

   530 

   531     /* In a first pass, compute the optimal bit lengths (which may

   532      * overflow in the case of the bit length tree).

   533      */

   534     tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */

   535 

   536     for (h = s->heap_max+1; h < HEAP_SIZE; h++) {

   537         n = s->heap[h];

   538         bits = tree[tree[n].Dad].Len + 1;

   539         if (bits > max_length) bits = max_length, overflow++;

   540         tree[n].Len = (ush)bits;

   541         /* We overwrite tree[n].Dad which is no longer needed */

   542 

   543         if (n > max_code) continue; /* not a leaf node */

   544 

   545         s->bl_count[bits]++;

   546         xbits = 0;

   547         if (n >= base) xbits = extra[n-base];

   548         f = tree[n].Freq;

   549         s->opt_len += (ulg)f * (bits + xbits);

   550         if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);

   551     }

   552     if (overflow == 0) return;

   553 

   554     Trace((stderr,"\nbit length overflow\n"));

   555     /* This happens for example on obj2 and pic of the Calgary corpus */

   556 

   557     /* Find the first bit length which could increase: */

   558     do {

   559         bits = max_length-1;

   560         while (s->bl_count[bits] == 0) bits--;

   561         s->bl_count[bits]--;      /* move one leaf down the tree */

   562         s->bl_count[bits+1] += 2; /* move one overflow item as its brother */

   563         s->bl_count[max_length]--;

   564         /* The brother of the overflow item also moves one step up,

   565          * but this does not affect bl_count[max_length]

   566          */

   567         overflow -= 2;

   568     } while (overflow > 0);

   569 

   570     /* Now recompute all bit lengths, scanning in increasing frequency.

   571      * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all

   572      * lengths instead of fixing only the wrong ones. This idea is taken

   573      * from 'ar' written by Haruhiko Okumura.)

   574      */

   575     for (bits = max_length; bits != 0; bits--) {

   576         n = s->bl_count[bits];

   577         while (n != 0) {

   578             m = s->heap[--h];

   579             if (m > max_code) continue;

   580             if ((unsigned) tree[m].Len != (unsigned) bits) {

   581                 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));

   582                 s->opt_len += ((long)bits - (long)tree[m].Len)

   583                               *(long)tree[m].Freq;

   584                 tree[m].Len = (ush)bits;

   585             }

   586             n--;

   587         }

   588     }

   589 }

   590 

   591 /* ===========================================================================

   592  * Generate the codes for a given tree and bit counts (which need not be

   593  * optimal).

   594  * IN assertion: the array bl_count contains the bit length statistics for

   595  * the given tree and the field len is set for all tree elements.

   596  * OUT assertion: the field code is set for all tree elements of non

   597  *     zero code length.

   598  */

   599 local void gen_codes (tree, max_code, bl_count)

   600     ct_data *tree;             /* the tree to decorate */

   601     int max_code;              /* largest code with non zero frequency */

   602     ushf *bl_count;            /* number of codes at each bit length */

   603 {

   604     ush next_code[MAX_BITS+1]; /* next code value for each bit length */

   605     ush code = 0;              /* running code value */

   606     int bits;                  /* bit index */

   607     int n;                     /* code index */

   608 

   609     /* The distribution counts are first used to generate the code values

   610      * without bit reversal.

   611      */

   612     for (bits = 1; bits <= MAX_BITS; bits++) {

   613         next_code[bits] = code = (code + bl_count[bits-1]) << 1;

   614     }

   615     /* Check that the bit counts in bl_count are consistent. The last code

   616      * must be all ones.

   617      */

   618     Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,

   619             "inconsistent bit counts");

   620     Tracev((stderr,"\ngen_codes: max_code %d ", max_code));

   621 

   622     for (n = 0;  n <= max_code; n++) {

   623         int len = tree[n].Len;

   624         if (len == 0) continue;

   625         /* Now reverse the bits */

   626         tree[n].Code = bi_reverse(next_code[len]++, len);

   627 

   628         Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",

   629              n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));

   630     }

   631 }

   632 

   633 /* ===========================================================================

   634  * Construct one Huffman tree and assigns the code bit strings and lengths.

   635  * Update the total bit length for the current block.

   636  * IN assertion: the field freq is set for all tree elements.

   637  * OUT assertions: the fields len and code are set to the optimal bit length

   638  *     and corresponding code. The length opt_len is updated; static_len is

   639  *     also updated if stree is not null. The field max_code is set.

   640  */

   641 local void build_tree(s, desc)

   642     deflate_state *s;

   643     tree_desc *desc; /* the tree descriptor */

   644 {

   645     ct_data *tree         = desc->dyn_tree;

   646     const ct_data *stree  = desc->stat_desc->static_tree;

   647     int elems             = desc->stat_desc->elems;

   648     int n, m;          /* iterate over heap elements */

   649     int max_code = -1; /* largest code with non zero frequency */

   650     int node;          /* new node being created */

   651 

   652     /* Construct the initial heap, with least frequent element in

   653      * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].

   654      * heap[0] is not used.

   655      */

   656     s->heap_len = 0, s->heap_max = HEAP_SIZE;

   657 

   658     for (n = 0; n < elems; n++) {

   659         if (tree[n].Freq != 0) {

   660             s->heap[++(s->heap_len)] = max_code = n;

   661             s->depth[n] = 0;

   662         } else {

   663             tree[n].Len = 0;

   664         }

   665     }

   666 

   667     /* The pkzip format requires that at least one distance code exists,

   668      * and that at least one bit should be sent even if there is only one

   669      * possible code. So to avoid special checks later on we force at least

   670      * two codes of non zero frequency.

   671      */

   672     while (s->heap_len < 2) {

   673         node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);

   674         tree[node].Freq = 1;

   675         s->depth[node] = 0;

   676         s->opt_len--; if (stree) s->static_len -= stree[node].Len;

   677         /* node is 0 or 1 so it does not have extra bits */

   678     }

   679     desc->max_code = max_code;

   680 

   681     /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,

   682      * establish sub-heaps of increasing lengths:

   683      */

   684     for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);

   685 

   686     /* Construct the Huffman tree by repeatedly combining the least two

   687      * frequent nodes.

   688      */

   689     node = elems;              /* next internal node of the tree */

   690     do {

   691         pqremove(s, tree, n);  /* n = node of least frequency */

   692         m = s->heap[SMALLEST]; /* m = node of next least frequency */

   693 

   694         s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */

   695         s->heap[--(s->heap_max)] = m;

   696 

   697         /* Create a new node father of n and m */

   698         tree[node].Freq = tree[n].Freq + tree[m].Freq;

   699         s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?

   700                                 s->depth[n] : s->depth[m]) + 1);

   701         tree[n].Dad = tree[m].Dad = (ush)node;

   702 #ifdef DUMP_BL_TREE

   703         if (tree == s->bl_tree) {

   704             fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",

   705                     node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);

   706         }

   707 #endif

   708         /* and insert the new node in the heap */

   709         s->heap[SMALLEST] = node++;

   710         pqdownheap(s, tree, SMALLEST);

   711 

   712     } while (s->heap_len >= 2);

   713 

   714     s->heap[--(s->heap_max)] = s->heap[SMALLEST];

   715 

   716     /* At this point, the fields freq and dad are set. We can now

   717      * generate the bit lengths.

   718      */

   719     gen_bitlen(s, (tree_desc *)desc);

   720 

   721     /* The field len is now set, we can generate the bit codes */

   722     gen_codes ((ct_data *)tree, max_code, s->bl_count);

   723 }

   724 

   725 /* ===========================================================================

   726  * Scan a literal or distance tree to determine the frequencies of the codes

   727  * in the bit length tree.

   728  */

   729 local void scan_tree (s, tree, max_code)

   730     deflate_state *s;

   731     ct_data *tree;   /* the tree to be scanned */

   732     int max_code;    /* and its largest code of non zero frequency */

   733 {

   734     int n;                     /* iterates over all tree elements */

   735     int prevlen = -1;          /* last emitted length */

   736     int curlen;                /* length of current code */

   737     int nextlen = tree[0].Len; /* length of next code */

   738     int count = 0;             /* repeat count of the current code */

   739     int max_count = 7;         /* max repeat count */

   740     int min_count = 4;         /* min repeat count */

   741 

   742     if (nextlen == 0) max_count = 138, min_count = 3;

   743     tree[max_code+1].Len = (ush)0xffff; /* guard */

   744 

   745     for (n = 0; n <= max_code; n++) {

   746         curlen = nextlen; nextlen = tree[n+1].Len;

   747         if (++count < max_count && curlen == nextlen) {

   748             continue;

   749         } else if (count < min_count) {

   750             s->bl_tree[curlen].Freq += count;

   751         } else if (curlen != 0) {

   752             if (curlen != prevlen) s->bl_tree[curlen].Freq++;

   753             s->bl_tree[REP_3_6].Freq++;

   754         } else if (count <= 10) {

   755             s->bl_tree[REPZ_3_10].Freq++;

   756         } else {

   757             s->bl_tree[REPZ_11_138].Freq++;

   758         }

   759         count = 0; prevlen = curlen;

   760         if (nextlen == 0) {

   761             max_count = 138, min_count = 3;

   762         } else if (curlen == nextlen) {

   763             max_count = 6, min_count = 3;

   764         } else {

   765             max_count = 7, min_count = 4;

   766         }

   767     }

   768 }

   769 

   770 /* ===========================================================================

   771  * Send a literal or distance tree in compressed form, using the codes in

   772  * bl_tree.

   773  */

   774 local void send_tree (s, tree, max_code)

   775     deflate_state *s;

   776     ct_data *tree; /* the tree to be scanned */

   777     int max_code;       /* and its largest code of non zero frequency */

   778 {

   779     int n;                     /* iterates over all tree elements */

   780     int prevlen = -1;          /* last emitted length */

   781     int curlen;                /* length of current code */

   782     int nextlen = tree[0].Len; /* length of next code */

   783     int count = 0;             /* repeat count of the current code */

   784     int max_count = 7;         /* max repeat count */

   785     int min_count = 4;         /* min repeat count */

   786 

   787     /* tree[max_code+1].Len = -1; */  /* guard already set */

   788     if (nextlen == 0) max_count = 138, min_count = 3;

   789 

   790     for (n = 0; n <= max_code; n++) {

   791         curlen = nextlen; nextlen = tree[n+1].Len;

   792         if (++count < max_count && curlen == nextlen) {

   793             continue;

   794         } else if (count < min_count) {

   795             do { send_code(s, curlen, s->bl_tree); } while (--count != 0);

   796 

   797         } else if (curlen != 0) {

   798             if (curlen != prevlen) {

   799                 send_code(s, curlen, s->bl_tree); count--;

   800             }

   801             Assert(count >= 3 && count <= 6, " 3_6?");

   802             send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);

   803 

   804         } else if (count <= 10) {

   805             send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);

   806 

   807         } else {

   808             send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);

   809         }

   810         count = 0; prevlen = curlen;

   811         if (nextlen == 0) {

   812             max_count = 138, min_count = 3;

   813         } else if (curlen == nextlen) {

   814             max_count = 6, min_count = 3;

   815         } else {

   816             max_count = 7, min_count = 4;

   817         }

   818     }

   819 }

   820 

   821 /* ===========================================================================

   822  * Construct the Huffman tree for the bit lengths and return the index in

   823  * bl_order of the last bit length code to send.

   824  */

   825 local int build_bl_tree(s)

   826     deflate_state *s;

   827 {

   828     int max_blindex;  /* index of last bit length code of non zero freq */

   829 

   830     /* Determine the bit length frequencies for literal and distance trees */

   831     scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);

   832     scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);

   833 

   834     /* Build the bit length tree: */

   835     build_tree(s, (tree_desc *)(&(s->bl_desc)));

   836     /* opt_len now includes the length of the tree representations, except

   837      * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.

   838      */

   839 

   840     /* Determine the number of bit length codes to send. The pkzip format

   841      * requires that at least 4 bit length codes be sent. (appnote.txt says

   842      * 3 but the actual value used is 4.)

   843      */

   844     for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {

   845         if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;

   846     }

   847     /* Update opt_len to include the bit length tree and counts */

   848     s->opt_len += 3*(max_blindex+1) + 5+5+4;

   849     Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",

   850             s->opt_len, s->static_len));

   851 

   852     return max_blindex;

   853 }

   854 

   855 /* ===========================================================================

   856  * Send the header for a block using dynamic Huffman trees: the counts, the

   857  * lengths of the bit length codes, the literal tree and the distance tree.

   858  * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.

   859  */

   860 local void send_all_trees(s, lcodes, dcodes, blcodes)

   861     deflate_state *s;

   862     int lcodes, dcodes, blcodes; /* number of codes for each tree */

   863 {

   864     int rank;                    /* index in bl_order */

   865 

   866     Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");

   867     Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,

   868             "too many codes");

   869     Tracev((stderr, "\nbl counts: "));

   870     send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */

   871     send_bits(s, dcodes-1,   5);

   872     send_bits(s, blcodes-4,  4); /* not -3 as stated in appnote.txt */

   873     for (rank = 0; rank < blcodes; rank++) {

   874         Tracev((stderr, "\nbl code %2d ", bl_order[rank]));

   875         send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);

   876     }

   877     Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));

   878 

   879     send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */

   880     Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));

   881 

   882     send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */

   883     Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));

   884 }

   885 

   886 /* ===========================================================================

   887  * Send a stored block

   888  */

   889 void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last)

   890     deflate_state *s;

   891     charf *buf;       /* input block */

   892     ulg stored_len;   /* length of input block */

   893     int last;         /* one if this is the last block for a file */

   894 {

   895     send_bits(s, (STORED_BLOCK<<1)+last, 3);    /* send block type */

   896 #ifdef DEBUG

   897     s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;

   898     s->compressed_len += (stored_len + 4) << 3;

   899 #endif

   900     copy_block(s, buf, (unsigned)stored_len, 1); /* with header */

   901 }

   902 

   903 /* ===========================================================================

   904  * Flush the bits in the bit buffer to pending output (leaves at most 7 bits)

   905  */

   906 void ZLIB_INTERNAL _tr_flush_bits(s)

   907     deflate_state *s;

   908 {

   909     bi_flush(s);

   910 }

   911 

   912 /* ===========================================================================

   913  * Send one empty static block to give enough lookahead for inflate.

   914  * This takes 10 bits, of which 7 may remain in the bit buffer.

   915  */

   916 void ZLIB_INTERNAL _tr_align(s)

   917     deflate_state *s;

   918 {

   919     send_bits(s, STATIC_TREES<<1, 3);

   920     send_code(s, END_BLOCK, static_ltree);

   921 #ifdef DEBUG

   922     s->compressed_len += 10L; /* 3 for block type, 7 for EOB */

   923 #endif

   924     bi_flush(s);

   925 }

   926 

   927 /* ===========================================================================

   928  * Determine the best encoding for the current block: dynamic trees, static

   929  * trees or store, and output the encoded block to the zip file.

   930  */

   931 void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last)

   932     deflate_state *s;

   933     charf *buf;       /* input block, or NULL if too old */

   934     ulg stored_len;   /* length of input block */

   935     int last;         /* one if this is the last block for a file */

   936 {

   937     ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */

   938     int max_blindex = 0;  /* index of last bit length code of non zero freq */

   939 

   940     /* Build the Huffman trees unless a stored block is forced */

   941     if (s->level > 0) {

   942 

   943         /* Check if the file is binary or text */

   944         if (s->strm->data_type == Z_UNKNOWN)

   945             s->strm->data_type = detect_data_type(s);

   946 

   947         /* Construct the literal and distance trees */

   948         build_tree(s, (tree_desc *)(&(s->l_desc)));

   949         Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,

   950                 s->static_len));

   951 

   952         build_tree(s, (tree_desc *)(&(s->d_desc)));

   953         Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,

   954                 s->static_len));

   955         /* At this point, opt_len and static_len are the total bit lengths of

   956          * the compressed block data, excluding the tree representations.

   957          */

   958 

   959         /* Build the bit length tree for the above two trees, and get the index

   960          * in bl_order of the last bit length code to send.

   961          */

   962         max_blindex = build_bl_tree(s);

   963 

   964         /* Determine the best encoding. Compute the block lengths in bytes. */

   965         opt_lenb = (s->opt_len+3+7)>>3;

   966         static_lenb = (s->static_len+3+7)>>3;

   967 

   968         Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",

   969                 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,

   970                 s->last_lit));

   971 

   972         if (static_lenb <= opt_lenb) opt_lenb = static_lenb;

   973 

   974     } else {

   975         Assert(buf != (char*)0, "lost buf");

   976         opt_lenb = static_lenb = stored_len + 5; /* force a stored block */

   977     }

   978 

   979 #ifdef FORCE_STORED

   980     if (buf != (char*)0) { /* force stored block */

   981 #else

   982     if (stored_len+4 <= opt_lenb && buf != (char*)0) {

   983                        /* 4: two words for the lengths */

   984 #endif

   985         /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.

   986          * Otherwise we can't have processed more than WSIZE input bytes since

   987          * the last block flush, because compression would have been

   988          * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to

   989          * transform a block into a stored block.

   990          */

   991         _tr_stored_block(s, buf, stored_len, last);

   992 

   993 #ifdef FORCE_STATIC

   994     } else if (static_lenb >= 0) { /* force static trees */

   995 #else

   996     } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {

   997 #endif

   998         send_bits(s, (STATIC_TREES<<1)+last, 3);

   999         compress_block(s, (const ct_data *)static_ltree,

  1000                        (const ct_data *)static_dtree);

  1001 #ifdef DEBUG

  1002         s->compressed_len += 3 + s->static_len;

  1003 #endif

  1004     } else {

  1005         send_bits(s, (DYN_TREES<<1)+last, 3);

  1006         send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,

  1007                        max_blindex+1);

  1008         compress_block(s, (const ct_data *)s->dyn_ltree,

  1009                        (const ct_data *)s->dyn_dtree);

  1010 #ifdef DEBUG

  1011         s->compressed_len += 3 + s->opt_len;

  1012 #endif

  1013     }

  1014     Assert (s->compressed_len == s->bits_sent, "bad compressed size");

  1015     /* The above check is made mod 2^32, for files larger than 512 MB

  1016      * and uLong implemented on 32 bits.

  1017      */

  1018     init_block(s);

  1019 

  1020     if (last) {

  1021         bi_windup(s);

  1022 #ifdef DEBUG

  1023         s->compressed_len += 7;  /* align on byte boundary */

  1024 #endif

  1025     }

  1026     Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,

  1027            s->compressed_len-7*last));

  1028 }

  1029 

  1030 /* ===========================================================================

  1031  * Save the match info and tally the frequency counts. Return true if

  1032  * the current block must be flushed.

  1033  */

  1034 int ZLIB_INTERNAL _tr_tally (s, dist, lc)

  1035     deflate_state *s;

  1036     unsigned dist;  /* distance of matched string */

  1037     unsigned lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */

  1038 {

  1039     s->d_buf[s->last_lit] = (ush)dist;

  1040     s->l_buf[s->last_lit++] = (uch)lc;

  1041     if (dist == 0) {

  1042         /* lc is the unmatched char */

  1043         s->dyn_ltree[lc].Freq++;

  1044     } else {

  1045         s->matches++;

  1046         /* Here, lc is the match length - MIN_MATCH */

  1047         dist--;             /* dist = match distance - 1 */

  1048         Assert((ush)dist < (ush)MAX_DIST(s) &&

  1049                (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&

  1050                (ush)d_code(dist) < (ush)D_CODES,  "_tr_tally: bad match");

  1051 

  1052         s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;

  1053         s->dyn_dtree[d_code(dist)].Freq++;

  1054     }

  1055 

  1056 #ifdef TRUNCATE_BLOCK

  1057     /* Try to guess if it is profitable to stop the current block here */

  1058     if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {

  1059         /* Compute an upper bound for the compressed length */

  1060         ulg out_length = (ulg)s->last_lit*8L;

  1061         ulg in_length = (ulg)((long)s->strstart - s->block_start);

  1062         int dcode;

  1063         for (dcode = 0; dcode < D_CODES; dcode++) {

  1064             out_length += (ulg)s->dyn_dtree[dcode].Freq *

  1065                 (5L+extra_dbits[dcode]);

  1066         }

  1067         out_length >>= 3;

  1068         Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",

  1069                s->last_lit, in_length, out_length,

  1070                100L - out_length*100L/in_length));

  1071         if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;

  1072     }

  1073 #endif

  1074     return (s->last_lit == s->lit_bufsize-1);

  1075     /* We avoid equality with lit_bufsize because of wraparound at 64K

  1076      * on 16 bit machines and because stored blocks are restricted to

  1077      * 64K-1 bytes.

  1078      */

  1079 }

  1080 

  1081 /* ===========================================================================

  1082  * Send the block data compressed using the given Huffman trees

  1083  */

  1084 local void compress_block(s, ltree, dtree)

  1085     deflate_state *s;

  1086     const ct_data *ltree; /* literal tree */

  1087     const ct_data *dtree; /* distance tree */

  1088 {

  1089     unsigned dist;      /* distance of matched string */

  1090     int lc;             /* match length or unmatched char (if dist == 0) */

  1091     unsigned lx = 0;    /* running index in l_buf */

  1092     unsigned code;      /* the code to send */

  1093     int extra;          /* number of extra bits to send */

  1094 

  1095     if (s->last_lit != 0) do {

  1096         dist = s->d_buf[lx];

  1097         lc = s->l_buf[lx++];

  1098         if (dist == 0) {

  1099             send_code(s, lc, ltree); /* send a literal byte */

  1100             Tracecv(isgraph(lc), (stderr," '%c' ", lc));

  1101         } else {

  1102             /* Here, lc is the match length - MIN_MATCH */

  1103             code = _length_code[lc];

  1104             send_code(s, code+LITERALS+1, ltree); /* send the length code */

  1105             extra = extra_lbits[code];

  1106             if (extra != 0) {

  1107                 lc -= base_length[code];

  1108                 send_bits(s, lc, extra);       /* send the extra length bits */

  1109             }

  1110             dist--; /* dist is now the match distance - 1 */

  1111             code = d_code(dist);

  1112             Assert (code < D_CODES, "bad d_code");

  1113 

  1114             send_code(s, code, dtree);       /* send the distance code */

  1115             extra = extra_dbits[code];

  1116             if (extra != 0) {

  1117                 dist -= base_dist[code];

  1118                 send_bits(s, dist, extra);   /* send the extra distance bits */

  1119             }

  1120         } /* literal or match pair ? */

  1121 

  1122         /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */

  1123         Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,

  1124                "pendingBuf overflow");

  1125 

  1126     } while (lx < s->last_lit);

  1127 

  1128     send_code(s, END_BLOCK, ltree);

  1129 }

  1130 

  1131 /* ===========================================================================

  1132  * Check if the data type is TEXT or BINARY, using the following algorithm:

  1133  * - TEXT if the two conditions below are satisfied:

  1134  *    a) There are no non-portable control characters belonging to the