Basic gzip/gunzip in memory buffer examples using zlib code.

Dependencies:   mbed-rtos mbed

There are small changes needed to the zconf.h file in the zlib distribution (I used 1.2.7). The zlib license applies to the zlib code - I have only imported a subset of the source.

The MBED has limited memory, so we need the following (near the top of zconf.h) to restrict memory allocation sizes:

#define    MAX_MEM_LEVEL    3
#define    MAX_WBITS        10

Because MAX_MEM_LEVEL and MAX_WBITS are so much lower than the default, there is a danger that the mbed cannot gunzip data compressed by a 'normal' zlib build. My use-case is to gzip on the mbed more than gunzip on the mbed so I have not given much time to this issue.

I also included this (also near the top of zconf.h) to prefix defines with Z_

#define    Z_PREFIX

In zconf.h, in the zlib distribution, the includes for <fcntl.h> and <sys/types.h> need commenting out when using the online compiler. No need when using GCC4MBED.

I also looked at miniz. I chose zlib because I needed the gzip headers and miniz does not implement them.

The sample main.cpp reads source data, compresses it, decompresses it, and finally compares the input data with the output data to confirm they are the same.

    unsigned char input_data[2048];
    unsigned long input_data_length = 0;
    FILE *ifp = fopen("/local/src.txt", "r");
    if (ifp) {
        int br = fread(input_data, 1, sizeof(input_data), ifp);
        fclose(ifp);
        input_data_length = br;
    }
    printf("%s:%d: input_data_length:%lu%s", __FILE__, __LINE__, input_data_length, newline);
 
 
    unsigned char gzip_data[2048];
    unsigned long gzip_data_length = 0;
    if (input_data_length > 0) {
        gzip_data_length = sizeof(gzip_data);
        int rv = gzip(gzip_data, &gzip_data_length, input_data, input_data_length);
        if (Z_OK == rv) {
            FILE *ofp = fopen("/local/dst.gz", "w");
            if (ofp) {
                int bw = fwrite(gzip_data, 1, gzip_data_length, ofp);
                fclose(ofp);
            }
        } else {
            printf("%s:%d: %d%s", __FILE__, __LINE__, rv, newline);
        }
    }
    printf("%s:%d: gzip_data_length:%lu%s", __FILE__, __LINE__, gzip_data_length, newline);
 
 
    unsigned char output_data[2048];
    unsigned long output_data_length = 0;
    if (gzip_data_length > 0) {
        output_data_length = sizeof(output_data);
        int rv = gunzip(output_data, &output_data_length, gzip_data, gzip_data_length);
        if (Z_OK != rv) {
            printf("%s:%d: %d%s", __FILE__, __LINE__, rv, newline);
        }
    }
    printf("%s:%d: output_data_length:%lu%s", __FILE__, __LINE__, output_data_length, newline);
 
 
    if (input_data_length > 0 and input_data_length > 0) {
        bool input_matches_output = false;
        if (input_data_length == output_data_length) {
            input_matches_output = true;
            for ( size_t i = 0 ; input_matches_output && i < input_data_length ; i++ ) {
                if (input_data[i] != output_data[i]) {
                    input_matches_output = false;
                }
            }
        }
        printf("%s:%d: input (%lu bytes) %s output (%lu bytes)%s", __FILE__, __LINE__, input_data_length, input_matches_output?"matches":"does not match", output_data_length, newline);
    } else {
        printf("%s:%d: input and/or output length is 0%s", __FILE__, __LINE__, newline);
    }
Committer:
jonathonfletcher
Date:
Sun Oct 21 07:46:41 2012 +0000
Revision:
0:54f5be781526
initial checkin

Who changed what in which revision?

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