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 /* deflate.c -- compress data using the deflation algorithm
jonathonfletcher 0:54f5be781526 2 * Copyright (C) 1995-2012 Jean-loup Gailly and Mark Adler
jonathonfletcher 0:54f5be781526 3 * For conditions of distribution and use, see copyright notice in zlib.h
jonathonfletcher 0:54f5be781526 4 */
jonathonfletcher 0:54f5be781526 5
jonathonfletcher 0:54f5be781526 6 /*
jonathonfletcher 0:54f5be781526 7 * ALGORITHM
jonathonfletcher 0:54f5be781526 8 *
jonathonfletcher 0:54f5be781526 9 * The "deflation" process depends on being able to identify portions
jonathonfletcher 0:54f5be781526 10 * of the input text which are identical to earlier input (within a
jonathonfletcher 0:54f5be781526 11 * sliding window trailing behind the input currently being processed).
jonathonfletcher 0:54f5be781526 12 *
jonathonfletcher 0:54f5be781526 13 * The most straightforward technique turns out to be the fastest for
jonathonfletcher 0:54f5be781526 14 * most input files: try all possible matches and select the longest.
jonathonfletcher 0:54f5be781526 15 * The key feature of this algorithm is that insertions into the string
jonathonfletcher 0:54f5be781526 16 * dictionary are very simple and thus fast, and deletions are avoided
jonathonfletcher 0:54f5be781526 17 * completely. Insertions are performed at each input character, whereas
jonathonfletcher 0:54f5be781526 18 * string matches are performed only when the previous match ends. So it
jonathonfletcher 0:54f5be781526 19 * is preferable to spend more time in matches to allow very fast string
jonathonfletcher 0:54f5be781526 20 * insertions and avoid deletions. The matching algorithm for small
jonathonfletcher 0:54f5be781526 21 * strings is inspired from that of Rabin & Karp. A brute force approach
jonathonfletcher 0:54f5be781526 22 * is used to find longer strings when a small match has been found.
jonathonfletcher 0:54f5be781526 23 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
jonathonfletcher 0:54f5be781526 24 * (by Leonid Broukhis).
jonathonfletcher 0:54f5be781526 25 * A previous version of this file used a more sophisticated algorithm
jonathonfletcher 0:54f5be781526 26 * (by Fiala and Greene) which is guaranteed to run in linear amortized
jonathonfletcher 0:54f5be781526 27 * time, but has a larger average cost, uses more memory and is patented.
jonathonfletcher 0:54f5be781526 28 * However the F&G algorithm may be faster for some highly redundant
jonathonfletcher 0:54f5be781526 29 * files if the parameter max_chain_length (described below) is too large.
jonathonfletcher 0:54f5be781526 30 *
jonathonfletcher 0:54f5be781526 31 * ACKNOWLEDGEMENTS
jonathonfletcher 0:54f5be781526 32 *
jonathonfletcher 0:54f5be781526 33 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
jonathonfletcher 0:54f5be781526 34 * I found it in 'freeze' written by Leonid Broukhis.
jonathonfletcher 0:54f5be781526 35 * Thanks to many people for bug reports and testing.
jonathonfletcher 0:54f5be781526 36 *
jonathonfletcher 0:54f5be781526 37 * REFERENCES
jonathonfletcher 0:54f5be781526 38 *
jonathonfletcher 0:54f5be781526 39 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
jonathonfletcher 0:54f5be781526 40 * Available in http://tools.ietf.org/html/rfc1951
jonathonfletcher 0:54f5be781526 41 *
jonathonfletcher 0:54f5be781526 42 * A description of the Rabin and Karp algorithm is given in the book
jonathonfletcher 0:54f5be781526 43 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
jonathonfletcher 0:54f5be781526 44 *
jonathonfletcher 0:54f5be781526 45 * Fiala,E.R., and Greene,D.H.
jonathonfletcher 0:54f5be781526 46 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
jonathonfletcher 0:54f5be781526 47 *
jonathonfletcher 0:54f5be781526 48 */
jonathonfletcher 0:54f5be781526 49
jonathonfletcher 0:54f5be781526 50 /* @(#) $Id$ */
jonathonfletcher 0:54f5be781526 51
jonathonfletcher 0:54f5be781526 52 #include "deflate.h"
jonathonfletcher 0:54f5be781526 53
jonathonfletcher 0:54f5be781526 54 const char deflate_copyright[] =
jonathonfletcher 0:54f5be781526 55 " deflate 1.2.7 Copyright 1995-2012 Jean-loup Gailly and Mark Adler ";
jonathonfletcher 0:54f5be781526 56 /*
jonathonfletcher 0:54f5be781526 57 If you use the zlib library in a product, an acknowledgment is welcome
jonathonfletcher 0:54f5be781526 58 in the documentation of your product. If for some reason you cannot
jonathonfletcher 0:54f5be781526 59 include such an acknowledgment, I would appreciate that you keep this
jonathonfletcher 0:54f5be781526 60 copyright string in the executable of your product.
jonathonfletcher 0:54f5be781526 61 */
jonathonfletcher 0:54f5be781526 62
jonathonfletcher 0:54f5be781526 63 /* ===========================================================================
jonathonfletcher 0:54f5be781526 64 * Function prototypes.
jonathonfletcher 0:54f5be781526 65 */
jonathonfletcher 0:54f5be781526 66 typedef enum {
jonathonfletcher 0:54f5be781526 67 need_more, /* block not completed, need more input or more output */
jonathonfletcher 0:54f5be781526 68 block_done, /* block flush performed */
jonathonfletcher 0:54f5be781526 69 finish_started, /* finish started, need only more output at next deflate */
jonathonfletcher 0:54f5be781526 70 finish_done /* finish done, accept no more input or output */
jonathonfletcher 0:54f5be781526 71 } block_state;
jonathonfletcher 0:54f5be781526 72
jonathonfletcher 0:54f5be781526 73 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
jonathonfletcher 0:54f5be781526 74 /* Compression function. Returns the block state after the call. */
jonathonfletcher 0:54f5be781526 75
jonathonfletcher 0:54f5be781526 76 local void fill_window OF((deflate_state *s));
jonathonfletcher 0:54f5be781526 77 local block_state deflate_stored OF((deflate_state *s, int flush));
jonathonfletcher 0:54f5be781526 78 local block_state deflate_fast OF((deflate_state *s, int flush));
jonathonfletcher 0:54f5be781526 79 #ifndef FASTEST
jonathonfletcher 0:54f5be781526 80 local block_state deflate_slow OF((deflate_state *s, int flush));
jonathonfletcher 0:54f5be781526 81 #endif
jonathonfletcher 0:54f5be781526 82 local block_state deflate_rle OF((deflate_state *s, int flush));
jonathonfletcher 0:54f5be781526 83 local block_state deflate_huff OF((deflate_state *s, int flush));
jonathonfletcher 0:54f5be781526 84 local void lm_init OF((deflate_state *s));
jonathonfletcher 0:54f5be781526 85 local void putShortMSB OF((deflate_state *s, uInt b));
jonathonfletcher 0:54f5be781526 86 local void flush_pending OF((z_streamp strm));
jonathonfletcher 0:54f5be781526 87 local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
jonathonfletcher 0:54f5be781526 88 #ifdef ASMV
jonathonfletcher 0:54f5be781526 89 void match_init OF((void)); /* asm code initialization */
jonathonfletcher 0:54f5be781526 90 uInt longest_match OF((deflate_state *s, IPos cur_match));
jonathonfletcher 0:54f5be781526 91 #else
jonathonfletcher 0:54f5be781526 92 local uInt longest_match OF((deflate_state *s, IPos cur_match));
jonathonfletcher 0:54f5be781526 93 #endif
jonathonfletcher 0:54f5be781526 94
jonathonfletcher 0:54f5be781526 95 #ifdef DEBUG
jonathonfletcher 0:54f5be781526 96 local void check_match OF((deflate_state *s, IPos start, IPos match,
jonathonfletcher 0:54f5be781526 97 int length));
jonathonfletcher 0:54f5be781526 98 #endif
jonathonfletcher 0:54f5be781526 99
jonathonfletcher 0:54f5be781526 100 /* ===========================================================================
jonathonfletcher 0:54f5be781526 101 * Local data
jonathonfletcher 0:54f5be781526 102 */
jonathonfletcher 0:54f5be781526 103
jonathonfletcher 0:54f5be781526 104 #define NIL 0
jonathonfletcher 0:54f5be781526 105 /* Tail of hash chains */
jonathonfletcher 0:54f5be781526 106
jonathonfletcher 0:54f5be781526 107 #ifndef TOO_FAR
jonathonfletcher 0:54f5be781526 108 # define TOO_FAR 4096
jonathonfletcher 0:54f5be781526 109 #endif
jonathonfletcher 0:54f5be781526 110 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
jonathonfletcher 0:54f5be781526 111
jonathonfletcher 0:54f5be781526 112 /* Values for max_lazy_match, good_match and max_chain_length, depending on
jonathonfletcher 0:54f5be781526 113 * the desired pack level (0..9). The values given below have been tuned to
jonathonfletcher 0:54f5be781526 114 * exclude worst case performance for pathological files. Better values may be
jonathonfletcher 0:54f5be781526 115 * found for specific files.
jonathonfletcher 0:54f5be781526 116 */
jonathonfletcher 0:54f5be781526 117 typedef struct config_s {
jonathonfletcher 0:54f5be781526 118 ush good_length; /* reduce lazy search above this match length */
jonathonfletcher 0:54f5be781526 119 ush max_lazy; /* do not perform lazy search above this match length */
jonathonfletcher 0:54f5be781526 120 ush nice_length; /* quit search above this match length */
jonathonfletcher 0:54f5be781526 121 ush max_chain;
jonathonfletcher 0:54f5be781526 122 compress_func func;
jonathonfletcher 0:54f5be781526 123 } config;
jonathonfletcher 0:54f5be781526 124
jonathonfletcher 0:54f5be781526 125 #ifdef FASTEST
jonathonfletcher 0:54f5be781526 126 local const config configuration_table[2] = {
jonathonfletcher 0:54f5be781526 127 /* good lazy nice chain */
jonathonfletcher 0:54f5be781526 128 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
jonathonfletcher 0:54f5be781526 129 /* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */
jonathonfletcher 0:54f5be781526 130 #else
jonathonfletcher 0:54f5be781526 131 local const config configuration_table[10] = {
jonathonfletcher 0:54f5be781526 132 /* good lazy nice chain */
jonathonfletcher 0:54f5be781526 133 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
jonathonfletcher 0:54f5be781526 134 /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */
jonathonfletcher 0:54f5be781526 135 /* 2 */ {4, 5, 16, 8, deflate_fast},
jonathonfletcher 0:54f5be781526 136 /* 3 */ {4, 6, 32, 32, deflate_fast},
jonathonfletcher 0:54f5be781526 137
jonathonfletcher 0:54f5be781526 138 /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
jonathonfletcher 0:54f5be781526 139 /* 5 */ {8, 16, 32, 32, deflate_slow},
jonathonfletcher 0:54f5be781526 140 /* 6 */ {8, 16, 128, 128, deflate_slow},
jonathonfletcher 0:54f5be781526 141 /* 7 */ {8, 32, 128, 256, deflate_slow},
jonathonfletcher 0:54f5be781526 142 /* 8 */ {32, 128, 258, 1024, deflate_slow},
jonathonfletcher 0:54f5be781526 143 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
jonathonfletcher 0:54f5be781526 144 #endif
jonathonfletcher 0:54f5be781526 145
jonathonfletcher 0:54f5be781526 146 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
jonathonfletcher 0:54f5be781526 147 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
jonathonfletcher 0:54f5be781526 148 * meaning.
jonathonfletcher 0:54f5be781526 149 */
jonathonfletcher 0:54f5be781526 150
jonathonfletcher 0:54f5be781526 151 #define EQUAL 0
jonathonfletcher 0:54f5be781526 152 /* result of memcmp for equal strings */
jonathonfletcher 0:54f5be781526 153
jonathonfletcher 0:54f5be781526 154 #ifndef NO_DUMMY_DECL
jonathonfletcher 0:54f5be781526 155 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
jonathonfletcher 0:54f5be781526 156 #endif
jonathonfletcher 0:54f5be781526 157
jonathonfletcher 0:54f5be781526 158 /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */
jonathonfletcher 0:54f5be781526 159 #define RANK(f) (((f) << 1) - ((f) > 4 ? 9 : 0))
jonathonfletcher 0:54f5be781526 160
jonathonfletcher 0:54f5be781526 161 /* ===========================================================================
jonathonfletcher 0:54f5be781526 162 * Update a hash value with the given input byte
jonathonfletcher 0:54f5be781526 163 * IN assertion: all calls to to UPDATE_HASH are made with consecutive
jonathonfletcher 0:54f5be781526 164 * input characters, so that a running hash key can be computed from the
jonathonfletcher 0:54f5be781526 165 * previous key instead of complete recalculation each time.
jonathonfletcher 0:54f5be781526 166 */
jonathonfletcher 0:54f5be781526 167 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
jonathonfletcher 0:54f5be781526 168
jonathonfletcher 0:54f5be781526 169
jonathonfletcher 0:54f5be781526 170 /* ===========================================================================
jonathonfletcher 0:54f5be781526 171 * Insert string str in the dictionary and set match_head to the previous head
jonathonfletcher 0:54f5be781526 172 * of the hash chain (the most recent string with same hash key). Return
jonathonfletcher 0:54f5be781526 173 * the previous length of the hash chain.
jonathonfletcher 0:54f5be781526 174 * If this file is compiled with -DFASTEST, the compression level is forced
jonathonfletcher 0:54f5be781526 175 * to 1, and no hash chains are maintained.
jonathonfletcher 0:54f5be781526 176 * IN assertion: all calls to to INSERT_STRING are made with consecutive
jonathonfletcher 0:54f5be781526 177 * input characters and the first MIN_MATCH bytes of str are valid
jonathonfletcher 0:54f5be781526 178 * (except for the last MIN_MATCH-1 bytes of the input file).
jonathonfletcher 0:54f5be781526 179 */
jonathonfletcher 0:54f5be781526 180 #ifdef FASTEST
jonathonfletcher 0:54f5be781526 181 #define INSERT_STRING(s, str, match_head) \
jonathonfletcher 0:54f5be781526 182 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
jonathonfletcher 0:54f5be781526 183 match_head = s->head[s->ins_h], \
jonathonfletcher 0:54f5be781526 184 s->head[s->ins_h] = (Pos)(str))
jonathonfletcher 0:54f5be781526 185 #else
jonathonfletcher 0:54f5be781526 186 #define INSERT_STRING(s, str, match_head) \
jonathonfletcher 0:54f5be781526 187 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
jonathonfletcher 0:54f5be781526 188 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
jonathonfletcher 0:54f5be781526 189 s->head[s->ins_h] = (Pos)(str))
jonathonfletcher 0:54f5be781526 190 #endif
jonathonfletcher 0:54f5be781526 191
jonathonfletcher 0:54f5be781526 192 /* ===========================================================================
jonathonfletcher 0:54f5be781526 193 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
jonathonfletcher 0:54f5be781526 194 * prev[] will be initialized on the fly.
jonathonfletcher 0:54f5be781526 195 */
jonathonfletcher 0:54f5be781526 196 #define CLEAR_HASH(s) \
jonathonfletcher 0:54f5be781526 197 s->head[s->hash_size-1] = NIL; \
jonathonfletcher 0:54f5be781526 198 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
jonathonfletcher 0:54f5be781526 199
jonathonfletcher 0:54f5be781526 200 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 201 int ZEXPORT deflateInit_(strm, level, version, stream_size)
jonathonfletcher 0:54f5be781526 202 z_streamp strm;
jonathonfletcher 0:54f5be781526 203 int level;
jonathonfletcher 0:54f5be781526 204 const char *version;
jonathonfletcher 0:54f5be781526 205 int stream_size;
jonathonfletcher 0:54f5be781526 206 {
jonathonfletcher 0:54f5be781526 207 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
jonathonfletcher 0:54f5be781526 208 Z_DEFAULT_STRATEGY, version, stream_size);
jonathonfletcher 0:54f5be781526 209 /* To do: ignore strm->next_in if we use it as window */
jonathonfletcher 0:54f5be781526 210 }
jonathonfletcher 0:54f5be781526 211
jonathonfletcher 0:54f5be781526 212 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 213 int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
jonathonfletcher 0:54f5be781526 214 version, stream_size)
jonathonfletcher 0:54f5be781526 215 z_streamp strm;
jonathonfletcher 0:54f5be781526 216 int level;
jonathonfletcher 0:54f5be781526 217 int method;
jonathonfletcher 0:54f5be781526 218 int windowBits;
jonathonfletcher 0:54f5be781526 219 int memLevel;
jonathonfletcher 0:54f5be781526 220 int strategy;
jonathonfletcher 0:54f5be781526 221 const char *version;
jonathonfletcher 0:54f5be781526 222 int stream_size;
jonathonfletcher 0:54f5be781526 223 {
jonathonfletcher 0:54f5be781526 224 deflate_state *s;
jonathonfletcher 0:54f5be781526 225 int wrap = 1;
jonathonfletcher 0:54f5be781526 226 static const char my_version[] = ZLIB_VERSION;
jonathonfletcher 0:54f5be781526 227
jonathonfletcher 0:54f5be781526 228 ushf *overlay;
jonathonfletcher 0:54f5be781526 229 /* We overlay pending_buf and d_buf+l_buf. This works since the average
jonathonfletcher 0:54f5be781526 230 * output size for (length,distance) codes is <= 24 bits.
jonathonfletcher 0:54f5be781526 231 */
jonathonfletcher 0:54f5be781526 232
jonathonfletcher 0:54f5be781526 233 if (version == Z_NULL || version[0] != my_version[0] ||
jonathonfletcher 0:54f5be781526 234 stream_size != sizeof(z_stream)) {
jonathonfletcher 0:54f5be781526 235 return Z_VERSION_ERROR;
jonathonfletcher 0:54f5be781526 236 }
jonathonfletcher 0:54f5be781526 237 if (strm == Z_NULL) return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 238
jonathonfletcher 0:54f5be781526 239 strm->msg = Z_NULL;
jonathonfletcher 0:54f5be781526 240 if (strm->zalloc == (alloc_func)0) {
jonathonfletcher 0:54f5be781526 241 #ifdef Z_SOLO
jonathonfletcher 0:54f5be781526 242 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 243 #else
jonathonfletcher 0:54f5be781526 244 strm->zalloc = zcalloc;
jonathonfletcher 0:54f5be781526 245 strm->opaque = (voidpf)0;
jonathonfletcher 0:54f5be781526 246 #endif
jonathonfletcher 0:54f5be781526 247 }
jonathonfletcher 0:54f5be781526 248 if (strm->zfree == (free_func)0)
jonathonfletcher 0:54f5be781526 249 #ifdef Z_SOLO
jonathonfletcher 0:54f5be781526 250 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 251 #else
jonathonfletcher 0:54f5be781526 252 strm->zfree = zcfree;
jonathonfletcher 0:54f5be781526 253 #endif
jonathonfletcher 0:54f5be781526 254
jonathonfletcher 0:54f5be781526 255 #ifdef FASTEST
jonathonfletcher 0:54f5be781526 256 if (level != 0) level = 1;
jonathonfletcher 0:54f5be781526 257 #else
jonathonfletcher 0:54f5be781526 258 if (level == Z_DEFAULT_COMPRESSION) level = 6;
jonathonfletcher 0:54f5be781526 259 #endif
jonathonfletcher 0:54f5be781526 260
jonathonfletcher 0:54f5be781526 261 if (windowBits < 0) { /* suppress zlib wrapper */
jonathonfletcher 0:54f5be781526 262 wrap = 0;
jonathonfletcher 0:54f5be781526 263 windowBits = -windowBits;
jonathonfletcher 0:54f5be781526 264 }
jonathonfletcher 0:54f5be781526 265 #ifdef GZIP
jonathonfletcher 0:54f5be781526 266 else if (windowBits > 15) {
jonathonfletcher 0:54f5be781526 267 wrap = 2; /* write gzip wrapper instead */
jonathonfletcher 0:54f5be781526 268 windowBits -= 16;
jonathonfletcher 0:54f5be781526 269 }
jonathonfletcher 0:54f5be781526 270 #endif
jonathonfletcher 0:54f5be781526 271 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
jonathonfletcher 0:54f5be781526 272 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
jonathonfletcher 0:54f5be781526 273 strategy < 0 || strategy > Z_FIXED) {
jonathonfletcher 0:54f5be781526 274 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 275 }
jonathonfletcher 0:54f5be781526 276 if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */
jonathonfletcher 0:54f5be781526 277 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
jonathonfletcher 0:54f5be781526 278 if (s == Z_NULL) return Z_MEM_ERROR;
jonathonfletcher 0:54f5be781526 279 strm->state = (struct internal_state FAR *)s;
jonathonfletcher 0:54f5be781526 280 s->strm = strm;
jonathonfletcher 0:54f5be781526 281
jonathonfletcher 0:54f5be781526 282 s->wrap = wrap;
jonathonfletcher 0:54f5be781526 283 s->gzhead = Z_NULL;
jonathonfletcher 0:54f5be781526 284 s->w_bits = windowBits;
jonathonfletcher 0:54f5be781526 285 s->w_size = 1 << s->w_bits;
jonathonfletcher 0:54f5be781526 286 s->w_mask = s->w_size - 1;
jonathonfletcher 0:54f5be781526 287
jonathonfletcher 0:54f5be781526 288 s->hash_bits = memLevel + 7;
jonathonfletcher 0:54f5be781526 289 s->hash_size = 1 << s->hash_bits;
jonathonfletcher 0:54f5be781526 290 s->hash_mask = s->hash_size - 1;
jonathonfletcher 0:54f5be781526 291 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
jonathonfletcher 0:54f5be781526 292
jonathonfletcher 0:54f5be781526 293 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
jonathonfletcher 0:54f5be781526 294 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
jonathonfletcher 0:54f5be781526 295 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
jonathonfletcher 0:54f5be781526 296
jonathonfletcher 0:54f5be781526 297 s->high_water = 0; /* nothing written to s->window yet */
jonathonfletcher 0:54f5be781526 298
jonathonfletcher 0:54f5be781526 299 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
jonathonfletcher 0:54f5be781526 300
jonathonfletcher 0:54f5be781526 301 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
jonathonfletcher 0:54f5be781526 302 s->pending_buf = (uchf *) overlay;
jonathonfletcher 0:54f5be781526 303 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
jonathonfletcher 0:54f5be781526 304
jonathonfletcher 0:54f5be781526 305 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
jonathonfletcher 0:54f5be781526 306 s->pending_buf == Z_NULL) {
jonathonfletcher 0:54f5be781526 307 s->status = FINISH_STATE;
jonathonfletcher 0:54f5be781526 308 strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
jonathonfletcher 0:54f5be781526 309 deflateEnd (strm);
jonathonfletcher 0:54f5be781526 310 return Z_MEM_ERROR;
jonathonfletcher 0:54f5be781526 311 }
jonathonfletcher 0:54f5be781526 312 s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
jonathonfletcher 0:54f5be781526 313 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
jonathonfletcher 0:54f5be781526 314
jonathonfletcher 0:54f5be781526 315 s->level = level;
jonathonfletcher 0:54f5be781526 316 s->strategy = strategy;
jonathonfletcher 0:54f5be781526 317 s->method = (Byte)method;
jonathonfletcher 0:54f5be781526 318
jonathonfletcher 0:54f5be781526 319 return deflateReset(strm);
jonathonfletcher 0:54f5be781526 320 }
jonathonfletcher 0:54f5be781526 321
jonathonfletcher 0:54f5be781526 322 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 323 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
jonathonfletcher 0:54f5be781526 324 z_streamp strm;
jonathonfletcher 0:54f5be781526 325 const Bytef *dictionary;
jonathonfletcher 0:54f5be781526 326 uInt dictLength;
jonathonfletcher 0:54f5be781526 327 {
jonathonfletcher 0:54f5be781526 328 deflate_state *s;
jonathonfletcher 0:54f5be781526 329 uInt str, n;
jonathonfletcher 0:54f5be781526 330 int wrap;
jonathonfletcher 0:54f5be781526 331 unsigned avail;
jonathonfletcher 0:54f5be781526 332 unsigned char *next;
jonathonfletcher 0:54f5be781526 333
jonathonfletcher 0:54f5be781526 334 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL)
jonathonfletcher 0:54f5be781526 335 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 336 s = strm->state;
jonathonfletcher 0:54f5be781526 337 wrap = s->wrap;
jonathonfletcher 0:54f5be781526 338 if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead)
jonathonfletcher 0:54f5be781526 339 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 340
jonathonfletcher 0:54f5be781526 341 /* when using zlib wrappers, compute Adler-32 for provided dictionary */
jonathonfletcher 0:54f5be781526 342 if (wrap == 1)
jonathonfletcher 0:54f5be781526 343 strm->adler = adler32(strm->adler, dictionary, dictLength);
jonathonfletcher 0:54f5be781526 344 s->wrap = 0; /* avoid computing Adler-32 in read_buf */
jonathonfletcher 0:54f5be781526 345
jonathonfletcher 0:54f5be781526 346 /* if dictionary would fill window, just replace the history */
jonathonfletcher 0:54f5be781526 347 if (dictLength >= s->w_size) {
jonathonfletcher 0:54f5be781526 348 if (wrap == 0) { /* already empty otherwise */
jonathonfletcher 0:54f5be781526 349 CLEAR_HASH(s);
jonathonfletcher 0:54f5be781526 350 s->strstart = 0;
jonathonfletcher 0:54f5be781526 351 s->block_start = 0L;
jonathonfletcher 0:54f5be781526 352 s->insert = 0;
jonathonfletcher 0:54f5be781526 353 }
jonathonfletcher 0:54f5be781526 354 dictionary += dictLength - s->w_size; /* use the tail */
jonathonfletcher 0:54f5be781526 355 dictLength = s->w_size;
jonathonfletcher 0:54f5be781526 356 }
jonathonfletcher 0:54f5be781526 357
jonathonfletcher 0:54f5be781526 358 /* insert dictionary into window and hash */
jonathonfletcher 0:54f5be781526 359 avail = strm->avail_in;
jonathonfletcher 0:54f5be781526 360 next = strm->next_in;
jonathonfletcher 0:54f5be781526 361 strm->avail_in = dictLength;
jonathonfletcher 0:54f5be781526 362 strm->next_in = (Bytef *)dictionary;
jonathonfletcher 0:54f5be781526 363 fill_window(s);
jonathonfletcher 0:54f5be781526 364 while (s->lookahead >= MIN_MATCH) {
jonathonfletcher 0:54f5be781526 365 str = s->strstart;
jonathonfletcher 0:54f5be781526 366 n = s->lookahead - (MIN_MATCH-1);
jonathonfletcher 0:54f5be781526 367 do {
jonathonfletcher 0:54f5be781526 368 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
jonathonfletcher 0:54f5be781526 369 #ifndef FASTEST
jonathonfletcher 0:54f5be781526 370 s->prev[str & s->w_mask] = s->head[s->ins_h];
jonathonfletcher 0:54f5be781526 371 #endif
jonathonfletcher 0:54f5be781526 372 s->head[s->ins_h] = (Pos)str;
jonathonfletcher 0:54f5be781526 373 str++;
jonathonfletcher 0:54f5be781526 374 } while (--n);
jonathonfletcher 0:54f5be781526 375 s->strstart = str;
jonathonfletcher 0:54f5be781526 376 s->lookahead = MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 377 fill_window(s);
jonathonfletcher 0:54f5be781526 378 }
jonathonfletcher 0:54f5be781526 379 s->strstart += s->lookahead;
jonathonfletcher 0:54f5be781526 380 s->block_start = (long)s->strstart;
jonathonfletcher 0:54f5be781526 381 s->insert = s->lookahead;
jonathonfletcher 0:54f5be781526 382 s->lookahead = 0;
jonathonfletcher 0:54f5be781526 383 s->match_length = s->prev_length = MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 384 s->match_available = 0;
jonathonfletcher 0:54f5be781526 385 strm->next_in = next;
jonathonfletcher 0:54f5be781526 386 strm->avail_in = avail;
jonathonfletcher 0:54f5be781526 387 s->wrap = wrap;
jonathonfletcher 0:54f5be781526 388 return Z_OK;
jonathonfletcher 0:54f5be781526 389 }
jonathonfletcher 0:54f5be781526 390
jonathonfletcher 0:54f5be781526 391 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 392 int ZEXPORT deflateResetKeep (strm)
jonathonfletcher 0:54f5be781526 393 z_streamp strm;
jonathonfletcher 0:54f5be781526 394 {
jonathonfletcher 0:54f5be781526 395 deflate_state *s;
jonathonfletcher 0:54f5be781526 396
jonathonfletcher 0:54f5be781526 397 if (strm == Z_NULL || strm->state == Z_NULL ||
jonathonfletcher 0:54f5be781526 398 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {
jonathonfletcher 0:54f5be781526 399 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 400 }
jonathonfletcher 0:54f5be781526 401
jonathonfletcher 0:54f5be781526 402 strm->total_in = strm->total_out = 0;
jonathonfletcher 0:54f5be781526 403 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
jonathonfletcher 0:54f5be781526 404 strm->data_type = Z_UNKNOWN;
jonathonfletcher 0:54f5be781526 405
jonathonfletcher 0:54f5be781526 406 s = (deflate_state *)strm->state;
jonathonfletcher 0:54f5be781526 407 s->pending = 0;
jonathonfletcher 0:54f5be781526 408 s->pending_out = s->pending_buf;
jonathonfletcher 0:54f5be781526 409
jonathonfletcher 0:54f5be781526 410 if (s->wrap < 0) {
jonathonfletcher 0:54f5be781526 411 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
jonathonfletcher 0:54f5be781526 412 }
jonathonfletcher 0:54f5be781526 413 s->status = s->wrap ? INIT_STATE : BUSY_STATE;
jonathonfletcher 0:54f5be781526 414 strm->adler =
jonathonfletcher 0:54f5be781526 415 #ifdef GZIP
jonathonfletcher 0:54f5be781526 416 s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
jonathonfletcher 0:54f5be781526 417 #endif
jonathonfletcher 0:54f5be781526 418 adler32(0L, Z_NULL, 0);
jonathonfletcher 0:54f5be781526 419 s->last_flush = Z_NO_FLUSH;
jonathonfletcher 0:54f5be781526 420
jonathonfletcher 0:54f5be781526 421 _tr_init(s);
jonathonfletcher 0:54f5be781526 422
jonathonfletcher 0:54f5be781526 423 return Z_OK;
jonathonfletcher 0:54f5be781526 424 }
jonathonfletcher 0:54f5be781526 425
jonathonfletcher 0:54f5be781526 426 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 427 int ZEXPORT deflateReset (strm)
jonathonfletcher 0:54f5be781526 428 z_streamp strm;
jonathonfletcher 0:54f5be781526 429 {
jonathonfletcher 0:54f5be781526 430 int ret;
jonathonfletcher 0:54f5be781526 431
jonathonfletcher 0:54f5be781526 432 ret = deflateResetKeep(strm);
jonathonfletcher 0:54f5be781526 433 if (ret == Z_OK)
jonathonfletcher 0:54f5be781526 434 lm_init(strm->state);
jonathonfletcher 0:54f5be781526 435 return ret;
jonathonfletcher 0:54f5be781526 436 }
jonathonfletcher 0:54f5be781526 437
jonathonfletcher 0:54f5be781526 438 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 439 int ZEXPORT deflateSetHeader (strm, head)
jonathonfletcher 0:54f5be781526 440 z_streamp strm;
jonathonfletcher 0:54f5be781526 441 gz_headerp head;
jonathonfletcher 0:54f5be781526 442 {
jonathonfletcher 0:54f5be781526 443 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 444 if (strm->state->wrap != 2) return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 445 strm->state->gzhead = head;
jonathonfletcher 0:54f5be781526 446 return Z_OK;
jonathonfletcher 0:54f5be781526 447 }
jonathonfletcher 0:54f5be781526 448
jonathonfletcher 0:54f5be781526 449 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 450 int ZEXPORT deflatePending (strm, pending, bits)
jonathonfletcher 0:54f5be781526 451 unsigned *pending;
jonathonfletcher 0:54f5be781526 452 int *bits;
jonathonfletcher 0:54f5be781526 453 z_streamp strm;
jonathonfletcher 0:54f5be781526 454 {
jonathonfletcher 0:54f5be781526 455 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 456 if (pending != Z_NULL)
jonathonfletcher 0:54f5be781526 457 *pending = strm->state->pending;
jonathonfletcher 0:54f5be781526 458 if (bits != Z_NULL)
jonathonfletcher 0:54f5be781526 459 *bits = strm->state->bi_valid;
jonathonfletcher 0:54f5be781526 460 return Z_OK;
jonathonfletcher 0:54f5be781526 461 }
jonathonfletcher 0:54f5be781526 462
jonathonfletcher 0:54f5be781526 463 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 464 int ZEXPORT deflatePrime (strm, bits, value)
jonathonfletcher 0:54f5be781526 465 z_streamp strm;
jonathonfletcher 0:54f5be781526 466 int bits;
jonathonfletcher 0:54f5be781526 467 int value;
jonathonfletcher 0:54f5be781526 468 {
jonathonfletcher 0:54f5be781526 469 deflate_state *s;
jonathonfletcher 0:54f5be781526 470 int put;
jonathonfletcher 0:54f5be781526 471
jonathonfletcher 0:54f5be781526 472 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 473 s = strm->state;
jonathonfletcher 0:54f5be781526 474 if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3))
jonathonfletcher 0:54f5be781526 475 return Z_BUF_ERROR;
jonathonfletcher 0:54f5be781526 476 do {
jonathonfletcher 0:54f5be781526 477 put = Buf_size - s->bi_valid;
jonathonfletcher 0:54f5be781526 478 if (put > bits)
jonathonfletcher 0:54f5be781526 479 put = bits;
jonathonfletcher 0:54f5be781526 480 s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid);
jonathonfletcher 0:54f5be781526 481 s->bi_valid += put;
jonathonfletcher 0:54f5be781526 482 _tr_flush_bits(s);
jonathonfletcher 0:54f5be781526 483 value >>= put;
jonathonfletcher 0:54f5be781526 484 bits -= put;
jonathonfletcher 0:54f5be781526 485 } while (bits);
jonathonfletcher 0:54f5be781526 486 return Z_OK;
jonathonfletcher 0:54f5be781526 487 }
jonathonfletcher 0:54f5be781526 488
jonathonfletcher 0:54f5be781526 489 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 490 int ZEXPORT deflateParams(strm, level, strategy)
jonathonfletcher 0:54f5be781526 491 z_streamp strm;
jonathonfletcher 0:54f5be781526 492 int level;
jonathonfletcher 0:54f5be781526 493 int strategy;
jonathonfletcher 0:54f5be781526 494 {
jonathonfletcher 0:54f5be781526 495 deflate_state *s;
jonathonfletcher 0:54f5be781526 496 compress_func func;
jonathonfletcher 0:54f5be781526 497 int err = Z_OK;
jonathonfletcher 0:54f5be781526 498
jonathonfletcher 0:54f5be781526 499 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 500 s = strm->state;
jonathonfletcher 0:54f5be781526 501
jonathonfletcher 0:54f5be781526 502 #ifdef FASTEST
jonathonfletcher 0:54f5be781526 503 if (level != 0) level = 1;
jonathonfletcher 0:54f5be781526 504 #else
jonathonfletcher 0:54f5be781526 505 if (level == Z_DEFAULT_COMPRESSION) level = 6;
jonathonfletcher 0:54f5be781526 506 #endif
jonathonfletcher 0:54f5be781526 507 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
jonathonfletcher 0:54f5be781526 508 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 509 }
jonathonfletcher 0:54f5be781526 510 func = configuration_table[s->level].func;
jonathonfletcher 0:54f5be781526 511
jonathonfletcher 0:54f5be781526 512 if ((strategy != s->strategy || func != configuration_table[level].func) &&
jonathonfletcher 0:54f5be781526 513 strm->total_in != 0) {
jonathonfletcher 0:54f5be781526 514 /* Flush the last buffer: */
jonathonfletcher 0:54f5be781526 515 err = deflate(strm, Z_BLOCK);
jonathonfletcher 0:54f5be781526 516 }
jonathonfletcher 0:54f5be781526 517 if (s->level != level) {
jonathonfletcher 0:54f5be781526 518 s->level = level;
jonathonfletcher 0:54f5be781526 519 s->max_lazy_match = configuration_table[level].max_lazy;
jonathonfletcher 0:54f5be781526 520 s->good_match = configuration_table[level].good_length;
jonathonfletcher 0:54f5be781526 521 s->nice_match = configuration_table[level].nice_length;
jonathonfletcher 0:54f5be781526 522 s->max_chain_length = configuration_table[level].max_chain;
jonathonfletcher 0:54f5be781526 523 }
jonathonfletcher 0:54f5be781526 524 s->strategy = strategy;
jonathonfletcher 0:54f5be781526 525 return err;
jonathonfletcher 0:54f5be781526 526 }
jonathonfletcher 0:54f5be781526 527
jonathonfletcher 0:54f5be781526 528 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 529 int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
jonathonfletcher 0:54f5be781526 530 z_streamp strm;
jonathonfletcher 0:54f5be781526 531 int good_length;
jonathonfletcher 0:54f5be781526 532 int max_lazy;
jonathonfletcher 0:54f5be781526 533 int nice_length;
jonathonfletcher 0:54f5be781526 534 int max_chain;
jonathonfletcher 0:54f5be781526 535 {
jonathonfletcher 0:54f5be781526 536 deflate_state *s;
jonathonfletcher 0:54f5be781526 537
jonathonfletcher 0:54f5be781526 538 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 539 s = strm->state;
jonathonfletcher 0:54f5be781526 540 s->good_match = good_length;
jonathonfletcher 0:54f5be781526 541 s->max_lazy_match = max_lazy;
jonathonfletcher 0:54f5be781526 542 s->nice_match = nice_length;
jonathonfletcher 0:54f5be781526 543 s->max_chain_length = max_chain;
jonathonfletcher 0:54f5be781526 544 return Z_OK;
jonathonfletcher 0:54f5be781526 545 }
jonathonfletcher 0:54f5be781526 546
jonathonfletcher 0:54f5be781526 547 /* =========================================================================
jonathonfletcher 0:54f5be781526 548 * For the default windowBits of 15 and memLevel of 8, this function returns
jonathonfletcher 0:54f5be781526 549 * a close to exact, as well as small, upper bound on the compressed size.
jonathonfletcher 0:54f5be781526 550 * They are coded as constants here for a reason--if the #define's are
jonathonfletcher 0:54f5be781526 551 * changed, then this function needs to be changed as well. The return
jonathonfletcher 0:54f5be781526 552 * value for 15 and 8 only works for those exact settings.
jonathonfletcher 0:54f5be781526 553 *
jonathonfletcher 0:54f5be781526 554 * For any setting other than those defaults for windowBits and memLevel,
jonathonfletcher 0:54f5be781526 555 * the value returned is a conservative worst case for the maximum expansion
jonathonfletcher 0:54f5be781526 556 * resulting from using fixed blocks instead of stored blocks, which deflate
jonathonfletcher 0:54f5be781526 557 * can emit on compressed data for some combinations of the parameters.
jonathonfletcher 0:54f5be781526 558 *
jonathonfletcher 0:54f5be781526 559 * This function could be more sophisticated to provide closer upper bounds for
jonathonfletcher 0:54f5be781526 560 * every combination of windowBits and memLevel. But even the conservative
jonathonfletcher 0:54f5be781526 561 * upper bound of about 14% expansion does not seem onerous for output buffer
jonathonfletcher 0:54f5be781526 562 * allocation.
jonathonfletcher 0:54f5be781526 563 */
jonathonfletcher 0:54f5be781526 564 uLong ZEXPORT deflateBound(strm, sourceLen)
jonathonfletcher 0:54f5be781526 565 z_streamp strm;
jonathonfletcher 0:54f5be781526 566 uLong sourceLen;
jonathonfletcher 0:54f5be781526 567 {
jonathonfletcher 0:54f5be781526 568 deflate_state *s;
jonathonfletcher 0:54f5be781526 569 uLong complen, wraplen;
jonathonfletcher 0:54f5be781526 570 Bytef *str;
jonathonfletcher 0:54f5be781526 571
jonathonfletcher 0:54f5be781526 572 /* conservative upper bound for compressed data */
jonathonfletcher 0:54f5be781526 573 complen = sourceLen +
jonathonfletcher 0:54f5be781526 574 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
jonathonfletcher 0:54f5be781526 575
jonathonfletcher 0:54f5be781526 576 /* if can't get parameters, return conservative bound plus zlib wrapper */
jonathonfletcher 0:54f5be781526 577 if (strm == Z_NULL || strm->state == Z_NULL)
jonathonfletcher 0:54f5be781526 578 return complen + 6;
jonathonfletcher 0:54f5be781526 579
jonathonfletcher 0:54f5be781526 580 /* compute wrapper length */
jonathonfletcher 0:54f5be781526 581 s = strm->state;
jonathonfletcher 0:54f5be781526 582 switch (s->wrap) {
jonathonfletcher 0:54f5be781526 583 case 0: /* raw deflate */
jonathonfletcher 0:54f5be781526 584 wraplen = 0;
jonathonfletcher 0:54f5be781526 585 break;
jonathonfletcher 0:54f5be781526 586 case 1: /* zlib wrapper */
jonathonfletcher 0:54f5be781526 587 wraplen = 6 + (s->strstart ? 4 : 0);
jonathonfletcher 0:54f5be781526 588 break;
jonathonfletcher 0:54f5be781526 589 case 2: /* gzip wrapper */
jonathonfletcher 0:54f5be781526 590 wraplen = 18;
jonathonfletcher 0:54f5be781526 591 if (s->gzhead != Z_NULL) { /* user-supplied gzip header */
jonathonfletcher 0:54f5be781526 592 if (s->gzhead->extra != Z_NULL)
jonathonfletcher 0:54f5be781526 593 wraplen += 2 + s->gzhead->extra_len;
jonathonfletcher 0:54f5be781526 594 str = s->gzhead->name;
jonathonfletcher 0:54f5be781526 595 if (str != Z_NULL)
jonathonfletcher 0:54f5be781526 596 do {
jonathonfletcher 0:54f5be781526 597 wraplen++;
jonathonfletcher 0:54f5be781526 598 } while (*str++);
jonathonfletcher 0:54f5be781526 599 str = s->gzhead->comment;
jonathonfletcher 0:54f5be781526 600 if (str != Z_NULL)
jonathonfletcher 0:54f5be781526 601 do {
jonathonfletcher 0:54f5be781526 602 wraplen++;
jonathonfletcher 0:54f5be781526 603 } while (*str++);
jonathonfletcher 0:54f5be781526 604 if (s->gzhead->hcrc)
jonathonfletcher 0:54f5be781526 605 wraplen += 2;
jonathonfletcher 0:54f5be781526 606 }
jonathonfletcher 0:54f5be781526 607 break;
jonathonfletcher 0:54f5be781526 608 default: /* for compiler happiness */
jonathonfletcher 0:54f5be781526 609 wraplen = 6;
jonathonfletcher 0:54f5be781526 610 }
jonathonfletcher 0:54f5be781526 611
jonathonfletcher 0:54f5be781526 612 /* if not default parameters, return conservative bound */
jonathonfletcher 0:54f5be781526 613 if (s->w_bits != 15 || s->hash_bits != 8 + 7)
jonathonfletcher 0:54f5be781526 614 return complen + wraplen;
jonathonfletcher 0:54f5be781526 615
jonathonfletcher 0:54f5be781526 616 /* default settings: return tight bound for that case */
jonathonfletcher 0:54f5be781526 617 return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
jonathonfletcher 0:54f5be781526 618 (sourceLen >> 25) + 13 - 6 + wraplen;
jonathonfletcher 0:54f5be781526 619 }
jonathonfletcher 0:54f5be781526 620
jonathonfletcher 0:54f5be781526 621 /* =========================================================================
jonathonfletcher 0:54f5be781526 622 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
jonathonfletcher 0:54f5be781526 623 * IN assertion: the stream state is correct and there is enough room in
jonathonfletcher 0:54f5be781526 624 * pending_buf.
jonathonfletcher 0:54f5be781526 625 */
jonathonfletcher 0:54f5be781526 626 local void putShortMSB (s, b)
jonathonfletcher 0:54f5be781526 627 deflate_state *s;
jonathonfletcher 0:54f5be781526 628 uInt b;
jonathonfletcher 0:54f5be781526 629 {
jonathonfletcher 0:54f5be781526 630 put_byte(s, (Byte)(b >> 8));
jonathonfletcher 0:54f5be781526 631 put_byte(s, (Byte)(b & 0xff));
jonathonfletcher 0:54f5be781526 632 }
jonathonfletcher 0:54f5be781526 633
jonathonfletcher 0:54f5be781526 634 /* =========================================================================
jonathonfletcher 0:54f5be781526 635 * Flush as much pending output as possible. All deflate() output goes
jonathonfletcher 0:54f5be781526 636 * through this function so some applications may wish to modify it
jonathonfletcher 0:54f5be781526 637 * to avoid allocating a large strm->next_out buffer and copying into it.
jonathonfletcher 0:54f5be781526 638 * (See also read_buf()).
jonathonfletcher 0:54f5be781526 639 */
jonathonfletcher 0:54f5be781526 640 local void flush_pending(strm)
jonathonfletcher 0:54f5be781526 641 z_streamp strm;
jonathonfletcher 0:54f5be781526 642 {
jonathonfletcher 0:54f5be781526 643 unsigned len;
jonathonfletcher 0:54f5be781526 644 deflate_state *s = strm->state;
jonathonfletcher 0:54f5be781526 645
jonathonfletcher 0:54f5be781526 646 _tr_flush_bits(s);
jonathonfletcher 0:54f5be781526 647 len = s->pending;
jonathonfletcher 0:54f5be781526 648 if (len > strm->avail_out) len = strm->avail_out;
jonathonfletcher 0:54f5be781526 649 if (len == 0) return;
jonathonfletcher 0:54f5be781526 650
jonathonfletcher 0:54f5be781526 651 zmemcpy(strm->next_out, s->pending_out, len);
jonathonfletcher 0:54f5be781526 652 strm->next_out += len;
jonathonfletcher 0:54f5be781526 653 s->pending_out += len;
jonathonfletcher 0:54f5be781526 654 strm->total_out += len;
jonathonfletcher 0:54f5be781526 655 strm->avail_out -= len;
jonathonfletcher 0:54f5be781526 656 s->pending -= len;
jonathonfletcher 0:54f5be781526 657 if (s->pending == 0) {
jonathonfletcher 0:54f5be781526 658 s->pending_out = s->pending_buf;
jonathonfletcher 0:54f5be781526 659 }
jonathonfletcher 0:54f5be781526 660 }
jonathonfletcher 0:54f5be781526 661
jonathonfletcher 0:54f5be781526 662 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 663 int ZEXPORT deflate (strm, flush)
jonathonfletcher 0:54f5be781526 664 z_streamp strm;
jonathonfletcher 0:54f5be781526 665 int flush;
jonathonfletcher 0:54f5be781526 666 {
jonathonfletcher 0:54f5be781526 667 int old_flush; /* value of flush param for previous deflate call */
jonathonfletcher 0:54f5be781526 668 deflate_state *s;
jonathonfletcher 0:54f5be781526 669
jonathonfletcher 0:54f5be781526 670 if (strm == Z_NULL || strm->state == Z_NULL ||
jonathonfletcher 0:54f5be781526 671 flush > Z_BLOCK || flush < 0) {
jonathonfletcher 0:54f5be781526 672 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 673 }
jonathonfletcher 0:54f5be781526 674 s = strm->state;
jonathonfletcher 0:54f5be781526 675
jonathonfletcher 0:54f5be781526 676 if (strm->next_out == Z_NULL ||
jonathonfletcher 0:54f5be781526 677 (strm->next_in == Z_NULL && strm->avail_in != 0) ||
jonathonfletcher 0:54f5be781526 678 (s->status == FINISH_STATE && flush != Z_FINISH)) {
jonathonfletcher 0:54f5be781526 679 ERR_RETURN(strm, Z_STREAM_ERROR);
jonathonfletcher 0:54f5be781526 680 }
jonathonfletcher 0:54f5be781526 681 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
jonathonfletcher 0:54f5be781526 682
jonathonfletcher 0:54f5be781526 683 s->strm = strm; /* just in case */
jonathonfletcher 0:54f5be781526 684 old_flush = s->last_flush;
jonathonfletcher 0:54f5be781526 685 s->last_flush = flush;
jonathonfletcher 0:54f5be781526 686
jonathonfletcher 0:54f5be781526 687 /* Write the header */
jonathonfletcher 0:54f5be781526 688 if (s->status == INIT_STATE) {
jonathonfletcher 0:54f5be781526 689 #ifdef GZIP
jonathonfletcher 0:54f5be781526 690 if (s->wrap == 2) {
jonathonfletcher 0:54f5be781526 691 strm->adler = crc32(0L, Z_NULL, 0);
jonathonfletcher 0:54f5be781526 692 put_byte(s, 31);
jonathonfletcher 0:54f5be781526 693 put_byte(s, 139);
jonathonfletcher 0:54f5be781526 694 put_byte(s, 8);
jonathonfletcher 0:54f5be781526 695 if (s->gzhead == Z_NULL) {
jonathonfletcher 0:54f5be781526 696 put_byte(s, 0);
jonathonfletcher 0:54f5be781526 697 put_byte(s, 0);
jonathonfletcher 0:54f5be781526 698 put_byte(s, 0);
jonathonfletcher 0:54f5be781526 699 put_byte(s, 0);
jonathonfletcher 0:54f5be781526 700 put_byte(s, 0);
jonathonfletcher 0:54f5be781526 701 put_byte(s, s->level == 9 ? 2 :
jonathonfletcher 0:54f5be781526 702 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
jonathonfletcher 0:54f5be781526 703 4 : 0));
jonathonfletcher 0:54f5be781526 704 put_byte(s, OS_CODE);
jonathonfletcher 0:54f5be781526 705 s->status = BUSY_STATE;
jonathonfletcher 0:54f5be781526 706 }
jonathonfletcher 0:54f5be781526 707 else {
jonathonfletcher 0:54f5be781526 708 put_byte(s, (s->gzhead->text ? 1 : 0) +
jonathonfletcher 0:54f5be781526 709 (s->gzhead->hcrc ? 2 : 0) +
jonathonfletcher 0:54f5be781526 710 (s->gzhead->extra == Z_NULL ? 0 : 4) +
jonathonfletcher 0:54f5be781526 711 (s->gzhead->name == Z_NULL ? 0 : 8) +
jonathonfletcher 0:54f5be781526 712 (s->gzhead->comment == Z_NULL ? 0 : 16)
jonathonfletcher 0:54f5be781526 713 );
jonathonfletcher 0:54f5be781526 714 put_byte(s, (Byte)(s->gzhead->time & 0xff));
jonathonfletcher 0:54f5be781526 715 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
jonathonfletcher 0:54f5be781526 716 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
jonathonfletcher 0:54f5be781526 717 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
jonathonfletcher 0:54f5be781526 718 put_byte(s, s->level == 9 ? 2 :
jonathonfletcher 0:54f5be781526 719 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
jonathonfletcher 0:54f5be781526 720 4 : 0));
jonathonfletcher 0:54f5be781526 721 put_byte(s, s->gzhead->os & 0xff);
jonathonfletcher 0:54f5be781526 722 if (s->gzhead->extra != Z_NULL) {
jonathonfletcher 0:54f5be781526 723 put_byte(s, s->gzhead->extra_len & 0xff);
jonathonfletcher 0:54f5be781526 724 put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
jonathonfletcher 0:54f5be781526 725 }
jonathonfletcher 0:54f5be781526 726 if (s->gzhead->hcrc)
jonathonfletcher 0:54f5be781526 727 strm->adler = crc32(strm->adler, s->pending_buf,
jonathonfletcher 0:54f5be781526 728 s->pending);
jonathonfletcher 0:54f5be781526 729 s->gzindex = 0;
jonathonfletcher 0:54f5be781526 730 s->status = EXTRA_STATE;
jonathonfletcher 0:54f5be781526 731 }
jonathonfletcher 0:54f5be781526 732 }
jonathonfletcher 0:54f5be781526 733 else
jonathonfletcher 0:54f5be781526 734 #endif
jonathonfletcher 0:54f5be781526 735 {
jonathonfletcher 0:54f5be781526 736 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
jonathonfletcher 0:54f5be781526 737 uInt level_flags;
jonathonfletcher 0:54f5be781526 738
jonathonfletcher 0:54f5be781526 739 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
jonathonfletcher 0:54f5be781526 740 level_flags = 0;
jonathonfletcher 0:54f5be781526 741 else if (s->level < 6)
jonathonfletcher 0:54f5be781526 742 level_flags = 1;
jonathonfletcher 0:54f5be781526 743 else if (s->level == 6)
jonathonfletcher 0:54f5be781526 744 level_flags = 2;
jonathonfletcher 0:54f5be781526 745 else
jonathonfletcher 0:54f5be781526 746 level_flags = 3;
jonathonfletcher 0:54f5be781526 747 header |= (level_flags << 6);
jonathonfletcher 0:54f5be781526 748 if (s->strstart != 0) header |= PRESET_DICT;
jonathonfletcher 0:54f5be781526 749 header += 31 - (header % 31);
jonathonfletcher 0:54f5be781526 750
jonathonfletcher 0:54f5be781526 751 s->status = BUSY_STATE;
jonathonfletcher 0:54f5be781526 752 putShortMSB(s, header);
jonathonfletcher 0:54f5be781526 753
jonathonfletcher 0:54f5be781526 754 /* Save the adler32 of the preset dictionary: */
jonathonfletcher 0:54f5be781526 755 if (s->strstart != 0) {
jonathonfletcher 0:54f5be781526 756 putShortMSB(s, (uInt)(strm->adler >> 16));
jonathonfletcher 0:54f5be781526 757 putShortMSB(s, (uInt)(strm->adler & 0xffff));
jonathonfletcher 0:54f5be781526 758 }
jonathonfletcher 0:54f5be781526 759 strm->adler = adler32(0L, Z_NULL, 0);
jonathonfletcher 0:54f5be781526 760 }
jonathonfletcher 0:54f5be781526 761 }
jonathonfletcher 0:54f5be781526 762 #ifdef GZIP
jonathonfletcher 0:54f5be781526 763 if (s->status == EXTRA_STATE) {
jonathonfletcher 0:54f5be781526 764 if (s->gzhead->extra != Z_NULL) {
jonathonfletcher 0:54f5be781526 765 uInt beg = s->pending; /* start of bytes to update crc */
jonathonfletcher 0:54f5be781526 766
jonathonfletcher 0:54f5be781526 767 while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {
jonathonfletcher 0:54f5be781526 768 if (s->pending == s->pending_buf_size) {
jonathonfletcher 0:54f5be781526 769 if (s->gzhead->hcrc && s->pending > beg)
jonathonfletcher 0:54f5be781526 770 strm->adler = crc32(strm->adler, s->pending_buf + beg,
jonathonfletcher 0:54f5be781526 771 s->pending - beg);
jonathonfletcher 0:54f5be781526 772 flush_pending(strm);
jonathonfletcher 0:54f5be781526 773 beg = s->pending;
jonathonfletcher 0:54f5be781526 774 if (s->pending == s->pending_buf_size)
jonathonfletcher 0:54f5be781526 775 break;
jonathonfletcher 0:54f5be781526 776 }
jonathonfletcher 0:54f5be781526 777 put_byte(s, s->gzhead->extra[s->gzindex]);
jonathonfletcher 0:54f5be781526 778 s->gzindex++;
jonathonfletcher 0:54f5be781526 779 }
jonathonfletcher 0:54f5be781526 780 if (s->gzhead->hcrc && s->pending > beg)
jonathonfletcher 0:54f5be781526 781 strm->adler = crc32(strm->adler, s->pending_buf + beg,
jonathonfletcher 0:54f5be781526 782 s->pending - beg);
jonathonfletcher 0:54f5be781526 783 if (s->gzindex == s->gzhead->extra_len) {
jonathonfletcher 0:54f5be781526 784 s->gzindex = 0;
jonathonfletcher 0:54f5be781526 785 s->status = NAME_STATE;
jonathonfletcher 0:54f5be781526 786 }
jonathonfletcher 0:54f5be781526 787 }
jonathonfletcher 0:54f5be781526 788 else
jonathonfletcher 0:54f5be781526 789 s->status = NAME_STATE;
jonathonfletcher 0:54f5be781526 790 }
jonathonfletcher 0:54f5be781526 791 if (s->status == NAME_STATE) {
jonathonfletcher 0:54f5be781526 792 if (s->gzhead->name != Z_NULL) {
jonathonfletcher 0:54f5be781526 793 uInt beg = s->pending; /* start of bytes to update crc */
jonathonfletcher 0:54f5be781526 794 int val;
jonathonfletcher 0:54f5be781526 795
jonathonfletcher 0:54f5be781526 796 do {
jonathonfletcher 0:54f5be781526 797 if (s->pending == s->pending_buf_size) {
jonathonfletcher 0:54f5be781526 798 if (s->gzhead->hcrc && s->pending > beg)
jonathonfletcher 0:54f5be781526 799 strm->adler = crc32(strm->adler, s->pending_buf + beg,
jonathonfletcher 0:54f5be781526 800 s->pending - beg);
jonathonfletcher 0:54f5be781526 801 flush_pending(strm);
jonathonfletcher 0:54f5be781526 802 beg = s->pending;
jonathonfletcher 0:54f5be781526 803 if (s->pending == s->pending_buf_size) {
jonathonfletcher 0:54f5be781526 804 val = 1;
jonathonfletcher 0:54f5be781526 805 break;
jonathonfletcher 0:54f5be781526 806 }
jonathonfletcher 0:54f5be781526 807 }
jonathonfletcher 0:54f5be781526 808 val = s->gzhead->name[s->gzindex++];
jonathonfletcher 0:54f5be781526 809 put_byte(s, val);
jonathonfletcher 0:54f5be781526 810 } while (val != 0);
jonathonfletcher 0:54f5be781526 811 if (s->gzhead->hcrc && s->pending > beg)
jonathonfletcher 0:54f5be781526 812 strm->adler = crc32(strm->adler, s->pending_buf + beg,
jonathonfletcher 0:54f5be781526 813 s->pending - beg);
jonathonfletcher 0:54f5be781526 814 if (val == 0) {
jonathonfletcher 0:54f5be781526 815 s->gzindex = 0;
jonathonfletcher 0:54f5be781526 816 s->status = COMMENT_STATE;
jonathonfletcher 0:54f5be781526 817 }
jonathonfletcher 0:54f5be781526 818 }
jonathonfletcher 0:54f5be781526 819 else
jonathonfletcher 0:54f5be781526 820 s->status = COMMENT_STATE;
jonathonfletcher 0:54f5be781526 821 }
jonathonfletcher 0:54f5be781526 822 if (s->status == COMMENT_STATE) {
jonathonfletcher 0:54f5be781526 823 if (s->gzhead->comment != Z_NULL) {
jonathonfletcher 0:54f5be781526 824 uInt beg = s->pending; /* start of bytes to update crc */
jonathonfletcher 0:54f5be781526 825 int val;
jonathonfletcher 0:54f5be781526 826
jonathonfletcher 0:54f5be781526 827 do {
jonathonfletcher 0:54f5be781526 828 if (s->pending == s->pending_buf_size) {
jonathonfletcher 0:54f5be781526 829 if (s->gzhead->hcrc && s->pending > beg)
jonathonfletcher 0:54f5be781526 830 strm->adler = crc32(strm->adler, s->pending_buf + beg,
jonathonfletcher 0:54f5be781526 831 s->pending - beg);
jonathonfletcher 0:54f5be781526 832 flush_pending(strm);
jonathonfletcher 0:54f5be781526 833 beg = s->pending;
jonathonfletcher 0:54f5be781526 834 if (s->pending == s->pending_buf_size) {
jonathonfletcher 0:54f5be781526 835 val = 1;
jonathonfletcher 0:54f5be781526 836 break;
jonathonfletcher 0:54f5be781526 837 }
jonathonfletcher 0:54f5be781526 838 }
jonathonfletcher 0:54f5be781526 839 val = s->gzhead->comment[s->gzindex++];
jonathonfletcher 0:54f5be781526 840 put_byte(s, val);
jonathonfletcher 0:54f5be781526 841 } while (val != 0);
jonathonfletcher 0:54f5be781526 842 if (s->gzhead->hcrc && s->pending > beg)
jonathonfletcher 0:54f5be781526 843 strm->adler = crc32(strm->adler, s->pending_buf + beg,
jonathonfletcher 0:54f5be781526 844 s->pending - beg);
jonathonfletcher 0:54f5be781526 845 if (val == 0)
jonathonfletcher 0:54f5be781526 846 s->status = HCRC_STATE;
jonathonfletcher 0:54f5be781526 847 }
jonathonfletcher 0:54f5be781526 848 else
jonathonfletcher 0:54f5be781526 849 s->status = HCRC_STATE;
jonathonfletcher 0:54f5be781526 850 }
jonathonfletcher 0:54f5be781526 851 if (s->status == HCRC_STATE) {
jonathonfletcher 0:54f5be781526 852 if (s->gzhead->hcrc) {
jonathonfletcher 0:54f5be781526 853 if (s->pending + 2 > s->pending_buf_size)
jonathonfletcher 0:54f5be781526 854 flush_pending(strm);
jonathonfletcher 0:54f5be781526 855 if (s->pending + 2 <= s->pending_buf_size) {
jonathonfletcher 0:54f5be781526 856 put_byte(s, (Byte)(strm->adler & 0xff));
jonathonfletcher 0:54f5be781526 857 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
jonathonfletcher 0:54f5be781526 858 strm->adler = crc32(0L, Z_NULL, 0);
jonathonfletcher 0:54f5be781526 859 s->status = BUSY_STATE;
jonathonfletcher 0:54f5be781526 860 }
jonathonfletcher 0:54f5be781526 861 }
jonathonfletcher 0:54f5be781526 862 else
jonathonfletcher 0:54f5be781526 863 s->status = BUSY_STATE;
jonathonfletcher 0:54f5be781526 864 }
jonathonfletcher 0:54f5be781526 865 #endif
jonathonfletcher 0:54f5be781526 866
jonathonfletcher 0:54f5be781526 867 /* Flush as much pending output as possible */
jonathonfletcher 0:54f5be781526 868 if (s->pending != 0) {
jonathonfletcher 0:54f5be781526 869 flush_pending(strm);
jonathonfletcher 0:54f5be781526 870 if (strm->avail_out == 0) {
jonathonfletcher 0:54f5be781526 871 /* Since avail_out is 0, deflate will be called again with
jonathonfletcher 0:54f5be781526 872 * more output space, but possibly with both pending and
jonathonfletcher 0:54f5be781526 873 * avail_in equal to zero. There won't be anything to do,
jonathonfletcher 0:54f5be781526 874 * but this is not an error situation so make sure we
jonathonfletcher 0:54f5be781526 875 * return OK instead of BUF_ERROR at next call of deflate:
jonathonfletcher 0:54f5be781526 876 */
jonathonfletcher 0:54f5be781526 877 s->last_flush = -1;
jonathonfletcher 0:54f5be781526 878 return Z_OK;
jonathonfletcher 0:54f5be781526 879 }
jonathonfletcher 0:54f5be781526 880
jonathonfletcher 0:54f5be781526 881 /* Make sure there is something to do and avoid duplicate consecutive
jonathonfletcher 0:54f5be781526 882 * flushes. For repeated and useless calls with Z_FINISH, we keep
jonathonfletcher 0:54f5be781526 883 * returning Z_STREAM_END instead of Z_BUF_ERROR.
jonathonfletcher 0:54f5be781526 884 */
jonathonfletcher 0:54f5be781526 885 } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
jonathonfletcher 0:54f5be781526 886 flush != Z_FINISH) {
jonathonfletcher 0:54f5be781526 887 ERR_RETURN(strm, Z_BUF_ERROR);
jonathonfletcher 0:54f5be781526 888 }
jonathonfletcher 0:54f5be781526 889
jonathonfletcher 0:54f5be781526 890 /* User must not provide more input after the first FINISH: */
jonathonfletcher 0:54f5be781526 891 if (s->status == FINISH_STATE && strm->avail_in != 0) {
jonathonfletcher 0:54f5be781526 892 ERR_RETURN(strm, Z_BUF_ERROR);
jonathonfletcher 0:54f5be781526 893 }
jonathonfletcher 0:54f5be781526 894
jonathonfletcher 0:54f5be781526 895 /* Start a new block or continue the current one.
jonathonfletcher 0:54f5be781526 896 */
jonathonfletcher 0:54f5be781526 897 if (strm->avail_in != 0 || s->lookahead != 0 ||
jonathonfletcher 0:54f5be781526 898 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
jonathonfletcher 0:54f5be781526 899 block_state bstate;
jonathonfletcher 0:54f5be781526 900
jonathonfletcher 0:54f5be781526 901 bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
jonathonfletcher 0:54f5be781526 902 (s->strategy == Z_RLE ? deflate_rle(s, flush) :
jonathonfletcher 0:54f5be781526 903 (*(configuration_table[s->level].func))(s, flush));
jonathonfletcher 0:54f5be781526 904
jonathonfletcher 0:54f5be781526 905 if (bstate == finish_started || bstate == finish_done) {
jonathonfletcher 0:54f5be781526 906 s->status = FINISH_STATE;
jonathonfletcher 0:54f5be781526 907 }
jonathonfletcher 0:54f5be781526 908 if (bstate == need_more || bstate == finish_started) {
jonathonfletcher 0:54f5be781526 909 if (strm->avail_out == 0) {
jonathonfletcher 0:54f5be781526 910 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
jonathonfletcher 0:54f5be781526 911 }
jonathonfletcher 0:54f5be781526 912 return Z_OK;
jonathonfletcher 0:54f5be781526 913 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
jonathonfletcher 0:54f5be781526 914 * of deflate should use the same flush parameter to make sure
jonathonfletcher 0:54f5be781526 915 * that the flush is complete. So we don't have to output an
jonathonfletcher 0:54f5be781526 916 * empty block here, this will be done at next call. This also
jonathonfletcher 0:54f5be781526 917 * ensures that for a very small output buffer, we emit at most
jonathonfletcher 0:54f5be781526 918 * one empty block.
jonathonfletcher 0:54f5be781526 919 */
jonathonfletcher 0:54f5be781526 920 }
jonathonfletcher 0:54f5be781526 921 if (bstate == block_done) {
jonathonfletcher 0:54f5be781526 922 if (flush == Z_PARTIAL_FLUSH) {
jonathonfletcher 0:54f5be781526 923 _tr_align(s);
jonathonfletcher 0:54f5be781526 924 } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
jonathonfletcher 0:54f5be781526 925 _tr_stored_block(s, (char*)0, 0L, 0);
jonathonfletcher 0:54f5be781526 926 /* For a full flush, this empty block will be recognized
jonathonfletcher 0:54f5be781526 927 * as a special marker by inflate_sync().
jonathonfletcher 0:54f5be781526 928 */
jonathonfletcher 0:54f5be781526 929 if (flush == Z_FULL_FLUSH) {
jonathonfletcher 0:54f5be781526 930 CLEAR_HASH(s); /* forget history */
jonathonfletcher 0:54f5be781526 931 if (s->lookahead == 0) {
jonathonfletcher 0:54f5be781526 932 s->strstart = 0;
jonathonfletcher 0:54f5be781526 933 s->block_start = 0L;
jonathonfletcher 0:54f5be781526 934 s->insert = 0;
jonathonfletcher 0:54f5be781526 935 }
jonathonfletcher 0:54f5be781526 936 }
jonathonfletcher 0:54f5be781526 937 }
jonathonfletcher 0:54f5be781526 938 flush_pending(strm);
jonathonfletcher 0:54f5be781526 939 if (strm->avail_out == 0) {
jonathonfletcher 0:54f5be781526 940 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
jonathonfletcher 0:54f5be781526 941 return Z_OK;
jonathonfletcher 0:54f5be781526 942 }
jonathonfletcher 0:54f5be781526 943 }
jonathonfletcher 0:54f5be781526 944 }
jonathonfletcher 0:54f5be781526 945 Assert(strm->avail_out > 0, "bug2");
jonathonfletcher 0:54f5be781526 946
jonathonfletcher 0:54f5be781526 947 if (flush != Z_FINISH) return Z_OK;
jonathonfletcher 0:54f5be781526 948 if (s->wrap <= 0) return Z_STREAM_END;
jonathonfletcher 0:54f5be781526 949
jonathonfletcher 0:54f5be781526 950 /* Write the trailer */
jonathonfletcher 0:54f5be781526 951 #ifdef GZIP
jonathonfletcher 0:54f5be781526 952 if (s->wrap == 2) {
jonathonfletcher 0:54f5be781526 953 put_byte(s, (Byte)(strm->adler & 0xff));
jonathonfletcher 0:54f5be781526 954 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
jonathonfletcher 0:54f5be781526 955 put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
jonathonfletcher 0:54f5be781526 956 put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
jonathonfletcher 0:54f5be781526 957 put_byte(s, (Byte)(strm->total_in & 0xff));
jonathonfletcher 0:54f5be781526 958 put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
jonathonfletcher 0:54f5be781526 959 put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
jonathonfletcher 0:54f5be781526 960 put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
jonathonfletcher 0:54f5be781526 961 }
jonathonfletcher 0:54f5be781526 962 else
jonathonfletcher 0:54f5be781526 963 #endif
jonathonfletcher 0:54f5be781526 964 {
jonathonfletcher 0:54f5be781526 965 putShortMSB(s, (uInt)(strm->adler >> 16));
jonathonfletcher 0:54f5be781526 966 putShortMSB(s, (uInt)(strm->adler & 0xffff));
jonathonfletcher 0:54f5be781526 967 }
jonathonfletcher 0:54f5be781526 968 flush_pending(strm);
jonathonfletcher 0:54f5be781526 969 /* If avail_out is zero, the application will call deflate again
jonathonfletcher 0:54f5be781526 970 * to flush the rest.
jonathonfletcher 0:54f5be781526 971 */
jonathonfletcher 0:54f5be781526 972 if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
jonathonfletcher 0:54f5be781526 973 return s->pending != 0 ? Z_OK : Z_STREAM_END;
jonathonfletcher 0:54f5be781526 974 }
jonathonfletcher 0:54f5be781526 975
jonathonfletcher 0:54f5be781526 976 /* ========================================================================= */
jonathonfletcher 0:54f5be781526 977 int ZEXPORT deflateEnd (strm)
jonathonfletcher 0:54f5be781526 978 z_streamp strm;
jonathonfletcher 0:54f5be781526 979 {
jonathonfletcher 0:54f5be781526 980 int status;
jonathonfletcher 0:54f5be781526 981
jonathonfletcher 0:54f5be781526 982 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 983
jonathonfletcher 0:54f5be781526 984 status = strm->state->status;
jonathonfletcher 0:54f5be781526 985 if (status != INIT_STATE &&
jonathonfletcher 0:54f5be781526 986 status != EXTRA_STATE &&
jonathonfletcher 0:54f5be781526 987 status != NAME_STATE &&
jonathonfletcher 0:54f5be781526 988 status != COMMENT_STATE &&
jonathonfletcher 0:54f5be781526 989 status != HCRC_STATE &&
jonathonfletcher 0:54f5be781526 990 status != BUSY_STATE &&
jonathonfletcher 0:54f5be781526 991 status != FINISH_STATE) {
jonathonfletcher 0:54f5be781526 992 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 993 }
jonathonfletcher 0:54f5be781526 994
jonathonfletcher 0:54f5be781526 995 /* Deallocate in reverse order of allocations: */
jonathonfletcher 0:54f5be781526 996 TRY_FREE(strm, strm->state->pending_buf);
jonathonfletcher 0:54f5be781526 997 TRY_FREE(strm, strm->state->head);
jonathonfletcher 0:54f5be781526 998 TRY_FREE(strm, strm->state->prev);
jonathonfletcher 0:54f5be781526 999 TRY_FREE(strm, strm->state->window);
jonathonfletcher 0:54f5be781526 1000
jonathonfletcher 0:54f5be781526 1001 ZFREE(strm, strm->state);
jonathonfletcher 0:54f5be781526 1002 strm->state = Z_NULL;
jonathonfletcher 0:54f5be781526 1003
jonathonfletcher 0:54f5be781526 1004 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
jonathonfletcher 0:54f5be781526 1005 }
jonathonfletcher 0:54f5be781526 1006
jonathonfletcher 0:54f5be781526 1007 /* =========================================================================
jonathonfletcher 0:54f5be781526 1008 * Copy the source state to the destination state.
jonathonfletcher 0:54f5be781526 1009 * To simplify the source, this is not supported for 16-bit MSDOS (which
jonathonfletcher 0:54f5be781526 1010 * doesn't have enough memory anyway to duplicate compression states).
jonathonfletcher 0:54f5be781526 1011 */
jonathonfletcher 0:54f5be781526 1012 int ZEXPORT deflateCopy (dest, source)
jonathonfletcher 0:54f5be781526 1013 z_streamp dest;
jonathonfletcher 0:54f5be781526 1014 z_streamp source;
jonathonfletcher 0:54f5be781526 1015 {
jonathonfletcher 0:54f5be781526 1016 #ifdef MAXSEG_64K
jonathonfletcher 0:54f5be781526 1017 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 1018 #else
jonathonfletcher 0:54f5be781526 1019 deflate_state *ds;
jonathonfletcher 0:54f5be781526 1020 deflate_state *ss;
jonathonfletcher 0:54f5be781526 1021 ushf *overlay;
jonathonfletcher 0:54f5be781526 1022
jonathonfletcher 0:54f5be781526 1023
jonathonfletcher 0:54f5be781526 1024 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
jonathonfletcher 0:54f5be781526 1025 return Z_STREAM_ERROR;
jonathonfletcher 0:54f5be781526 1026 }
jonathonfletcher 0:54f5be781526 1027
jonathonfletcher 0:54f5be781526 1028 ss = source->state;
jonathonfletcher 0:54f5be781526 1029
jonathonfletcher 0:54f5be781526 1030 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
jonathonfletcher 0:54f5be781526 1031
jonathonfletcher 0:54f5be781526 1032 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
jonathonfletcher 0:54f5be781526 1033 if (ds == Z_NULL) return Z_MEM_ERROR;
jonathonfletcher 0:54f5be781526 1034 dest->state = (struct internal_state FAR *) ds;
jonathonfletcher 0:54f5be781526 1035 zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state));
jonathonfletcher 0:54f5be781526 1036 ds->strm = dest;
jonathonfletcher 0:54f5be781526 1037
jonathonfletcher 0:54f5be781526 1038 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
jonathonfletcher 0:54f5be781526 1039 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
jonathonfletcher 0:54f5be781526 1040 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
jonathonfletcher 0:54f5be781526 1041 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
jonathonfletcher 0:54f5be781526 1042 ds->pending_buf = (uchf *) overlay;
jonathonfletcher 0:54f5be781526 1043
jonathonfletcher 0:54f5be781526 1044 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
jonathonfletcher 0:54f5be781526 1045 ds->pending_buf == Z_NULL) {
jonathonfletcher 0:54f5be781526 1046 deflateEnd (dest);
jonathonfletcher 0:54f5be781526 1047 return Z_MEM_ERROR;
jonathonfletcher 0:54f5be781526 1048 }
jonathonfletcher 0:54f5be781526 1049 /* following zmemcpy do not work for 16-bit MSDOS */
jonathonfletcher 0:54f5be781526 1050 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
jonathonfletcher 0:54f5be781526 1051 zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos));
jonathonfletcher 0:54f5be781526 1052 zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos));
jonathonfletcher 0:54f5be781526 1053 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
jonathonfletcher 0:54f5be781526 1054
jonathonfletcher 0:54f5be781526 1055 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
jonathonfletcher 0:54f5be781526 1056 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
jonathonfletcher 0:54f5be781526 1057 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
jonathonfletcher 0:54f5be781526 1058
jonathonfletcher 0:54f5be781526 1059 ds->l_desc.dyn_tree = ds->dyn_ltree;
jonathonfletcher 0:54f5be781526 1060 ds->d_desc.dyn_tree = ds->dyn_dtree;
jonathonfletcher 0:54f5be781526 1061 ds->bl_desc.dyn_tree = ds->bl_tree;
jonathonfletcher 0:54f5be781526 1062
jonathonfletcher 0:54f5be781526 1063 return Z_OK;
jonathonfletcher 0:54f5be781526 1064 #endif /* MAXSEG_64K */
jonathonfletcher 0:54f5be781526 1065 }
jonathonfletcher 0:54f5be781526 1066
jonathonfletcher 0:54f5be781526 1067 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1068 * Read a new buffer from the current input stream, update the adler32
jonathonfletcher 0:54f5be781526 1069 * and total number of bytes read. All deflate() input goes through
jonathonfletcher 0:54f5be781526 1070 * this function so some applications may wish to modify it to avoid
jonathonfletcher 0:54f5be781526 1071 * allocating a large strm->next_in buffer and copying from it.
jonathonfletcher 0:54f5be781526 1072 * (See also flush_pending()).
jonathonfletcher 0:54f5be781526 1073 */
jonathonfletcher 0:54f5be781526 1074 local int read_buf(strm, buf, size)
jonathonfletcher 0:54f5be781526 1075 z_streamp strm;
jonathonfletcher 0:54f5be781526 1076 Bytef *buf;
jonathonfletcher 0:54f5be781526 1077 unsigned size;
jonathonfletcher 0:54f5be781526 1078 {
jonathonfletcher 0:54f5be781526 1079 unsigned len = strm->avail_in;
jonathonfletcher 0:54f5be781526 1080
jonathonfletcher 0:54f5be781526 1081 if (len > size) len = size;
jonathonfletcher 0:54f5be781526 1082 if (len == 0) return 0;
jonathonfletcher 0:54f5be781526 1083
jonathonfletcher 0:54f5be781526 1084 strm->avail_in -= len;
jonathonfletcher 0:54f5be781526 1085
jonathonfletcher 0:54f5be781526 1086 zmemcpy(buf, strm->next_in, len);
jonathonfletcher 0:54f5be781526 1087 if (strm->state->wrap == 1) {
jonathonfletcher 0:54f5be781526 1088 strm->adler = adler32(strm->adler, buf, len);
jonathonfletcher 0:54f5be781526 1089 }
jonathonfletcher 0:54f5be781526 1090 #ifdef GZIP
jonathonfletcher 0:54f5be781526 1091 else if (strm->state->wrap == 2) {
jonathonfletcher 0:54f5be781526 1092 strm->adler = crc32(strm->adler, buf, len);
jonathonfletcher 0:54f5be781526 1093 }
jonathonfletcher 0:54f5be781526 1094 #endif
jonathonfletcher 0:54f5be781526 1095 strm->next_in += len;
jonathonfletcher 0:54f5be781526 1096 strm->total_in += len;
jonathonfletcher 0:54f5be781526 1097
jonathonfletcher 0:54f5be781526 1098 return (int)len;
jonathonfletcher 0:54f5be781526 1099 }
jonathonfletcher 0:54f5be781526 1100
jonathonfletcher 0:54f5be781526 1101 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1102 * Initialize the "longest match" routines for a new zlib stream
jonathonfletcher 0:54f5be781526 1103 */
jonathonfletcher 0:54f5be781526 1104 local void lm_init (s)
jonathonfletcher 0:54f5be781526 1105 deflate_state *s;
jonathonfletcher 0:54f5be781526 1106 {
jonathonfletcher 0:54f5be781526 1107 s->window_size = (ulg)2L*s->w_size;
jonathonfletcher 0:54f5be781526 1108
jonathonfletcher 0:54f5be781526 1109 CLEAR_HASH(s);
jonathonfletcher 0:54f5be781526 1110
jonathonfletcher 0:54f5be781526 1111 /* Set the default configuration parameters:
jonathonfletcher 0:54f5be781526 1112 */
jonathonfletcher 0:54f5be781526 1113 s->max_lazy_match = configuration_table[s->level].max_lazy;
jonathonfletcher 0:54f5be781526 1114 s->good_match = configuration_table[s->level].good_length;
jonathonfletcher 0:54f5be781526 1115 s->nice_match = configuration_table[s->level].nice_length;
jonathonfletcher 0:54f5be781526 1116 s->max_chain_length = configuration_table[s->level].max_chain;
jonathonfletcher 0:54f5be781526 1117
jonathonfletcher 0:54f5be781526 1118 s->strstart = 0;
jonathonfletcher 0:54f5be781526 1119 s->block_start = 0L;
jonathonfletcher 0:54f5be781526 1120 s->lookahead = 0;
jonathonfletcher 0:54f5be781526 1121 s->insert = 0;
jonathonfletcher 0:54f5be781526 1122 s->match_length = s->prev_length = MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 1123 s->match_available = 0;
jonathonfletcher 0:54f5be781526 1124 s->ins_h = 0;
jonathonfletcher 0:54f5be781526 1125 #ifndef FASTEST
jonathonfletcher 0:54f5be781526 1126 #ifdef ASMV
jonathonfletcher 0:54f5be781526 1127 match_init(); /* initialize the asm code */
jonathonfletcher 0:54f5be781526 1128 #endif
jonathonfletcher 0:54f5be781526 1129 #endif
jonathonfletcher 0:54f5be781526 1130 }
jonathonfletcher 0:54f5be781526 1131
jonathonfletcher 0:54f5be781526 1132 #ifndef FASTEST
jonathonfletcher 0:54f5be781526 1133 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1134 * Set match_start to the longest match starting at the given string and
jonathonfletcher 0:54f5be781526 1135 * return its length. Matches shorter or equal to prev_length are discarded,
jonathonfletcher 0:54f5be781526 1136 * in which case the result is equal to prev_length and match_start is
jonathonfletcher 0:54f5be781526 1137 * garbage.
jonathonfletcher 0:54f5be781526 1138 * IN assertions: cur_match is the head of the hash chain for the current
jonathonfletcher 0:54f5be781526 1139 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
jonathonfletcher 0:54f5be781526 1140 * OUT assertion: the match length is not greater than s->lookahead.
jonathonfletcher 0:54f5be781526 1141 */
jonathonfletcher 0:54f5be781526 1142 #ifndef ASMV
jonathonfletcher 0:54f5be781526 1143 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
jonathonfletcher 0:54f5be781526 1144 * match.S. The code will be functionally equivalent.
jonathonfletcher 0:54f5be781526 1145 */
jonathonfletcher 0:54f5be781526 1146 local uInt longest_match(s, cur_match)
jonathonfletcher 0:54f5be781526 1147 deflate_state *s;
jonathonfletcher 0:54f5be781526 1148 IPos cur_match; /* current match */
jonathonfletcher 0:54f5be781526 1149 {
jonathonfletcher 0:54f5be781526 1150 unsigned chain_length = s->max_chain_length;/* max hash chain length */
jonathonfletcher 0:54f5be781526 1151 register Bytef *scan = s->window + s->strstart; /* current string */
jonathonfletcher 0:54f5be781526 1152 register Bytef *match; /* matched string */
jonathonfletcher 0:54f5be781526 1153 register int len; /* length of current match */
jonathonfletcher 0:54f5be781526 1154 int best_len = s->prev_length; /* best match length so far */
jonathonfletcher 0:54f5be781526 1155 int nice_match = s->nice_match; /* stop if match long enough */
jonathonfletcher 0:54f5be781526 1156 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
jonathonfletcher 0:54f5be781526 1157 s->strstart - (IPos)MAX_DIST(s) : NIL;
jonathonfletcher 0:54f5be781526 1158 /* Stop when cur_match becomes <= limit. To simplify the code,
jonathonfletcher 0:54f5be781526 1159 * we prevent matches with the string of window index 0.
jonathonfletcher 0:54f5be781526 1160 */
jonathonfletcher 0:54f5be781526 1161 Posf *prev = s->prev;
jonathonfletcher 0:54f5be781526 1162 uInt wmask = s->w_mask;
jonathonfletcher 0:54f5be781526 1163
jonathonfletcher 0:54f5be781526 1164 #ifdef UNALIGNED_OK
jonathonfletcher 0:54f5be781526 1165 /* Compare two bytes at a time. Note: this is not always beneficial.
jonathonfletcher 0:54f5be781526 1166 * Try with and without -DUNALIGNED_OK to check.
jonathonfletcher 0:54f5be781526 1167 */
jonathonfletcher 0:54f5be781526 1168 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
jonathonfletcher 0:54f5be781526 1169 register ush scan_start = *(ushf*)scan;
jonathonfletcher 0:54f5be781526 1170 register ush scan_end = *(ushf*)(scan+best_len-1);
jonathonfletcher 0:54f5be781526 1171 #else
jonathonfletcher 0:54f5be781526 1172 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
jonathonfletcher 0:54f5be781526 1173 register Byte scan_end1 = scan[best_len-1];
jonathonfletcher 0:54f5be781526 1174 register Byte scan_end = scan[best_len];
jonathonfletcher 0:54f5be781526 1175 #endif
jonathonfletcher 0:54f5be781526 1176
jonathonfletcher 0:54f5be781526 1177 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
jonathonfletcher 0:54f5be781526 1178 * It is easy to get rid of this optimization if necessary.
jonathonfletcher 0:54f5be781526 1179 */
jonathonfletcher 0:54f5be781526 1180 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
jonathonfletcher 0:54f5be781526 1181
jonathonfletcher 0:54f5be781526 1182 /* Do not waste too much time if we already have a good match: */
jonathonfletcher 0:54f5be781526 1183 if (s->prev_length >= s->good_match) {
jonathonfletcher 0:54f5be781526 1184 chain_length >>= 2;
jonathonfletcher 0:54f5be781526 1185 }
jonathonfletcher 0:54f5be781526 1186 /* Do not look for matches beyond the end of the input. This is necessary
jonathonfletcher 0:54f5be781526 1187 * to make deflate deterministic.
jonathonfletcher 0:54f5be781526 1188 */
jonathonfletcher 0:54f5be781526 1189 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
jonathonfletcher 0:54f5be781526 1190
jonathonfletcher 0:54f5be781526 1191 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
jonathonfletcher 0:54f5be781526 1192
jonathonfletcher 0:54f5be781526 1193 do {
jonathonfletcher 0:54f5be781526 1194 Assert(cur_match < s->strstart, "no future");
jonathonfletcher 0:54f5be781526 1195 match = s->window + cur_match;
jonathonfletcher 0:54f5be781526 1196
jonathonfletcher 0:54f5be781526 1197 /* Skip to next match if the match length cannot increase
jonathonfletcher 0:54f5be781526 1198 * or if the match length is less than 2. Note that the checks below
jonathonfletcher 0:54f5be781526 1199 * for insufficient lookahead only occur occasionally for performance
jonathonfletcher 0:54f5be781526 1200 * reasons. Therefore uninitialized memory will be accessed, and
jonathonfletcher 0:54f5be781526 1201 * conditional jumps will be made that depend on those values.
jonathonfletcher 0:54f5be781526 1202 * However the length of the match is limited to the lookahead, so
jonathonfletcher 0:54f5be781526 1203 * the output of deflate is not affected by the uninitialized values.
jonathonfletcher 0:54f5be781526 1204 */
jonathonfletcher 0:54f5be781526 1205 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
jonathonfletcher 0:54f5be781526 1206 /* This code assumes sizeof(unsigned short) == 2. Do not use
jonathonfletcher 0:54f5be781526 1207 * UNALIGNED_OK if your compiler uses a different size.
jonathonfletcher 0:54f5be781526 1208 */
jonathonfletcher 0:54f5be781526 1209 if (*(ushf*)(match+best_len-1) != scan_end ||
jonathonfletcher 0:54f5be781526 1210 *(ushf*)match != scan_start) continue;
jonathonfletcher 0:54f5be781526 1211
jonathonfletcher 0:54f5be781526 1212 /* It is not necessary to compare scan[2] and match[2] since they are
jonathonfletcher 0:54f5be781526 1213 * always equal when the other bytes match, given that the hash keys
jonathonfletcher 0:54f5be781526 1214 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
jonathonfletcher 0:54f5be781526 1215 * strstart+3, +5, ... up to strstart+257. We check for insufficient
jonathonfletcher 0:54f5be781526 1216 * lookahead only every 4th comparison; the 128th check will be made
jonathonfletcher 0:54f5be781526 1217 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
jonathonfletcher 0:54f5be781526 1218 * necessary to put more guard bytes at the end of the window, or
jonathonfletcher 0:54f5be781526 1219 * to check more often for insufficient lookahead.
jonathonfletcher 0:54f5be781526 1220 */
jonathonfletcher 0:54f5be781526 1221 Assert(scan[2] == match[2], "scan[2]?");
jonathonfletcher 0:54f5be781526 1222 scan++, match++;
jonathonfletcher 0:54f5be781526 1223 do {
jonathonfletcher 0:54f5be781526 1224 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
jonathonfletcher 0:54f5be781526 1225 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
jonathonfletcher 0:54f5be781526 1226 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
jonathonfletcher 0:54f5be781526 1227 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
jonathonfletcher 0:54f5be781526 1228 scan < strend);
jonathonfletcher 0:54f5be781526 1229 /* The funny "do {}" generates better code on most compilers */
jonathonfletcher 0:54f5be781526 1230
jonathonfletcher 0:54f5be781526 1231 /* Here, scan <= window+strstart+257 */
jonathonfletcher 0:54f5be781526 1232 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
jonathonfletcher 0:54f5be781526 1233 if (*scan == *match) scan++;
jonathonfletcher 0:54f5be781526 1234
jonathonfletcher 0:54f5be781526 1235 len = (MAX_MATCH - 1) - (int)(strend-scan);
jonathonfletcher 0:54f5be781526 1236 scan = strend - (MAX_MATCH-1);
jonathonfletcher 0:54f5be781526 1237
jonathonfletcher 0:54f5be781526 1238 #else /* UNALIGNED_OK */
jonathonfletcher 0:54f5be781526 1239
jonathonfletcher 0:54f5be781526 1240 if (match[best_len] != scan_end ||
jonathonfletcher 0:54f5be781526 1241 match[best_len-1] != scan_end1 ||
jonathonfletcher 0:54f5be781526 1242 *match != *scan ||
jonathonfletcher 0:54f5be781526 1243 *++match != scan[1]) continue;
jonathonfletcher 0:54f5be781526 1244
jonathonfletcher 0:54f5be781526 1245 /* The check at best_len-1 can be removed because it will be made
jonathonfletcher 0:54f5be781526 1246 * again later. (This heuristic is not always a win.)
jonathonfletcher 0:54f5be781526 1247 * It is not necessary to compare scan[2] and match[2] since they
jonathonfletcher 0:54f5be781526 1248 * are always equal when the other bytes match, given that
jonathonfletcher 0:54f5be781526 1249 * the hash keys are equal and that HASH_BITS >= 8.
jonathonfletcher 0:54f5be781526 1250 */
jonathonfletcher 0:54f5be781526 1251 scan += 2, match++;
jonathonfletcher 0:54f5be781526 1252 Assert(*scan == *match, "match[2]?");
jonathonfletcher 0:54f5be781526 1253
jonathonfletcher 0:54f5be781526 1254 /* We check for insufficient lookahead only every 8th comparison;
jonathonfletcher 0:54f5be781526 1255 * the 256th check will be made at strstart+258.
jonathonfletcher 0:54f5be781526 1256 */
jonathonfletcher 0:54f5be781526 1257 do {
jonathonfletcher 0:54f5be781526 1258 } while (*++scan == *++match && *++scan == *++match &&
jonathonfletcher 0:54f5be781526 1259 *++scan == *++match && *++scan == *++match &&
jonathonfletcher 0:54f5be781526 1260 *++scan == *++match && *++scan == *++match &&
jonathonfletcher 0:54f5be781526 1261 *++scan == *++match && *++scan == *++match &&
jonathonfletcher 0:54f5be781526 1262 scan < strend);
jonathonfletcher 0:54f5be781526 1263
jonathonfletcher 0:54f5be781526 1264 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
jonathonfletcher 0:54f5be781526 1265
jonathonfletcher 0:54f5be781526 1266 len = MAX_MATCH - (int)(strend - scan);
jonathonfletcher 0:54f5be781526 1267 scan = strend - MAX_MATCH;
jonathonfletcher 0:54f5be781526 1268
jonathonfletcher 0:54f5be781526 1269 #endif /* UNALIGNED_OK */
jonathonfletcher 0:54f5be781526 1270
jonathonfletcher 0:54f5be781526 1271 if (len > best_len) {
jonathonfletcher 0:54f5be781526 1272 s->match_start = cur_match;
jonathonfletcher 0:54f5be781526 1273 best_len = len;
jonathonfletcher 0:54f5be781526 1274 if (len >= nice_match) break;
jonathonfletcher 0:54f5be781526 1275 #ifdef UNALIGNED_OK
jonathonfletcher 0:54f5be781526 1276 scan_end = *(ushf*)(scan+best_len-1);
jonathonfletcher 0:54f5be781526 1277 #else
jonathonfletcher 0:54f5be781526 1278 scan_end1 = scan[best_len-1];
jonathonfletcher 0:54f5be781526 1279 scan_end = scan[best_len];
jonathonfletcher 0:54f5be781526 1280 #endif
jonathonfletcher 0:54f5be781526 1281 }
jonathonfletcher 0:54f5be781526 1282 } while ((cur_match = prev[cur_match & wmask]) > limit
jonathonfletcher 0:54f5be781526 1283 && --chain_length != 0);
jonathonfletcher 0:54f5be781526 1284
jonathonfletcher 0:54f5be781526 1285 if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
jonathonfletcher 0:54f5be781526 1286 return s->lookahead;
jonathonfletcher 0:54f5be781526 1287 }
jonathonfletcher 0:54f5be781526 1288 #endif /* ASMV */
jonathonfletcher 0:54f5be781526 1289
jonathonfletcher 0:54f5be781526 1290 #else /* FASTEST */
jonathonfletcher 0:54f5be781526 1291
jonathonfletcher 0:54f5be781526 1292 /* ---------------------------------------------------------------------------
jonathonfletcher 0:54f5be781526 1293 * Optimized version for FASTEST only
jonathonfletcher 0:54f5be781526 1294 */
jonathonfletcher 0:54f5be781526 1295 local uInt longest_match(s, cur_match)
jonathonfletcher 0:54f5be781526 1296 deflate_state *s;
jonathonfletcher 0:54f5be781526 1297 IPos cur_match; /* current match */
jonathonfletcher 0:54f5be781526 1298 {
jonathonfletcher 0:54f5be781526 1299 register Bytef *scan = s->window + s->strstart; /* current string */
jonathonfletcher 0:54f5be781526 1300 register Bytef *match; /* matched string */
jonathonfletcher 0:54f5be781526 1301 register int len; /* length of current match */
jonathonfletcher 0:54f5be781526 1302 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
jonathonfletcher 0:54f5be781526 1303
jonathonfletcher 0:54f5be781526 1304 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
jonathonfletcher 0:54f5be781526 1305 * It is easy to get rid of this optimization if necessary.
jonathonfletcher 0:54f5be781526 1306 */
jonathonfletcher 0:54f5be781526 1307 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
jonathonfletcher 0:54f5be781526 1308
jonathonfletcher 0:54f5be781526 1309 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
jonathonfletcher 0:54f5be781526 1310
jonathonfletcher 0:54f5be781526 1311 Assert(cur_match < s->strstart, "no future");
jonathonfletcher 0:54f5be781526 1312
jonathonfletcher 0:54f5be781526 1313 match = s->window + cur_match;
jonathonfletcher 0:54f5be781526 1314
jonathonfletcher 0:54f5be781526 1315 /* Return failure if the match length is less than 2:
jonathonfletcher 0:54f5be781526 1316 */
jonathonfletcher 0:54f5be781526 1317 if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 1318
jonathonfletcher 0:54f5be781526 1319 /* The check at best_len-1 can be removed because it will be made
jonathonfletcher 0:54f5be781526 1320 * again later. (This heuristic is not always a win.)
jonathonfletcher 0:54f5be781526 1321 * It is not necessary to compare scan[2] and match[2] since they
jonathonfletcher 0:54f5be781526 1322 * are always equal when the other bytes match, given that
jonathonfletcher 0:54f5be781526 1323 * the hash keys are equal and that HASH_BITS >= 8.
jonathonfletcher 0:54f5be781526 1324 */
jonathonfletcher 0:54f5be781526 1325 scan += 2, match += 2;
jonathonfletcher 0:54f5be781526 1326 Assert(*scan == *match, "match[2]?");
jonathonfletcher 0:54f5be781526 1327
jonathonfletcher 0:54f5be781526 1328 /* We check for insufficient lookahead only every 8th comparison;
jonathonfletcher 0:54f5be781526 1329 * the 256th check will be made at strstart+258.
jonathonfletcher 0:54f5be781526 1330 */
jonathonfletcher 0:54f5be781526 1331 do {
jonathonfletcher 0:54f5be781526 1332 } while (*++scan == *++match && *++scan == *++match &&
jonathonfletcher 0:54f5be781526 1333 *++scan == *++match && *++scan == *++match &&
jonathonfletcher 0:54f5be781526 1334 *++scan == *++match && *++scan == *++match &&
jonathonfletcher 0:54f5be781526 1335 *++scan == *++match && *++scan == *++match &&
jonathonfletcher 0:54f5be781526 1336 scan < strend);
jonathonfletcher 0:54f5be781526 1337
jonathonfletcher 0:54f5be781526 1338 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
jonathonfletcher 0:54f5be781526 1339
jonathonfletcher 0:54f5be781526 1340 len = MAX_MATCH - (int)(strend - scan);
jonathonfletcher 0:54f5be781526 1341
jonathonfletcher 0:54f5be781526 1342 if (len < MIN_MATCH) return MIN_MATCH - 1;
jonathonfletcher 0:54f5be781526 1343
jonathonfletcher 0:54f5be781526 1344 s->match_start = cur_match;
jonathonfletcher 0:54f5be781526 1345 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
jonathonfletcher 0:54f5be781526 1346 }
jonathonfletcher 0:54f5be781526 1347
jonathonfletcher 0:54f5be781526 1348 #endif /* FASTEST */
jonathonfletcher 0:54f5be781526 1349
jonathonfletcher 0:54f5be781526 1350 #ifdef DEBUG
jonathonfletcher 0:54f5be781526 1351 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1352 * Check that the match at match_start is indeed a match.
jonathonfletcher 0:54f5be781526 1353 */
jonathonfletcher 0:54f5be781526 1354 local void check_match(s, start, match, length)
jonathonfletcher 0:54f5be781526 1355 deflate_state *s;
jonathonfletcher 0:54f5be781526 1356 IPos start, match;
jonathonfletcher 0:54f5be781526 1357 int length;
jonathonfletcher 0:54f5be781526 1358 {
jonathonfletcher 0:54f5be781526 1359 /* check that the match is indeed a match */
jonathonfletcher 0:54f5be781526 1360 if (zmemcmp(s->window + match,
jonathonfletcher 0:54f5be781526 1361 s->window + start, length) != EQUAL) {
jonathonfletcher 0:54f5be781526 1362 fprintf(stderr, " start %u, match %u, length %d\n",
jonathonfletcher 0:54f5be781526 1363 start, match, length);
jonathonfletcher 0:54f5be781526 1364 do {
jonathonfletcher 0:54f5be781526 1365 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
jonathonfletcher 0:54f5be781526 1366 } while (--length != 0);
jonathonfletcher 0:54f5be781526 1367 z_error("invalid match");
jonathonfletcher 0:54f5be781526 1368 }
jonathonfletcher 0:54f5be781526 1369 if (z_verbose > 1) {
jonathonfletcher 0:54f5be781526 1370 fprintf(stderr,"\\[%d,%d]", start-match, length);
jonathonfletcher 0:54f5be781526 1371 do { putc(s->window[start++], stderr); } while (--length != 0);
jonathonfletcher 0:54f5be781526 1372 }
jonathonfletcher 0:54f5be781526 1373 }
jonathonfletcher 0:54f5be781526 1374 #else
jonathonfletcher 0:54f5be781526 1375 # define check_match(s, start, match, length)
jonathonfletcher 0:54f5be781526 1376 #endif /* DEBUG */
jonathonfletcher 0:54f5be781526 1377
jonathonfletcher 0:54f5be781526 1378 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1379 * Fill the window when the lookahead becomes insufficient.
jonathonfletcher 0:54f5be781526 1380 * Updates strstart and lookahead.
jonathonfletcher 0:54f5be781526 1381 *
jonathonfletcher 0:54f5be781526 1382 * IN assertion: lookahead < MIN_LOOKAHEAD
jonathonfletcher 0:54f5be781526 1383 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
jonathonfletcher 0:54f5be781526 1384 * At least one byte has been read, or avail_in == 0; reads are
jonathonfletcher 0:54f5be781526 1385 * performed for at least two bytes (required for the zip translate_eol
jonathonfletcher 0:54f5be781526 1386 * option -- not supported here).
jonathonfletcher 0:54f5be781526 1387 */
jonathonfletcher 0:54f5be781526 1388 local void fill_window(s)
jonathonfletcher 0:54f5be781526 1389 deflate_state *s;
jonathonfletcher 0:54f5be781526 1390 {
jonathonfletcher 0:54f5be781526 1391 register unsigned n, m;
jonathonfletcher 0:54f5be781526 1392 register Posf *p;
jonathonfletcher 0:54f5be781526 1393 unsigned more; /* Amount of free space at the end of the window. */
jonathonfletcher 0:54f5be781526 1394 uInt wsize = s->w_size;
jonathonfletcher 0:54f5be781526 1395
jonathonfletcher 0:54f5be781526 1396 Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead");
jonathonfletcher 0:54f5be781526 1397
jonathonfletcher 0:54f5be781526 1398 do {
jonathonfletcher 0:54f5be781526 1399 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
jonathonfletcher 0:54f5be781526 1400
jonathonfletcher 0:54f5be781526 1401 /* Deal with !@#$% 64K limit: */
jonathonfletcher 0:54f5be781526 1402 if (sizeof(int) <= 2) {
jonathonfletcher 0:54f5be781526 1403 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
jonathonfletcher 0:54f5be781526 1404 more = wsize;
jonathonfletcher 0:54f5be781526 1405
jonathonfletcher 0:54f5be781526 1406 } else if (more == (unsigned)(-1)) {
jonathonfletcher 0:54f5be781526 1407 /* Very unlikely, but possible on 16 bit machine if
jonathonfletcher 0:54f5be781526 1408 * strstart == 0 && lookahead == 1 (input done a byte at time)
jonathonfletcher 0:54f5be781526 1409 */
jonathonfletcher 0:54f5be781526 1410 more--;
jonathonfletcher 0:54f5be781526 1411 }
jonathonfletcher 0:54f5be781526 1412 }
jonathonfletcher 0:54f5be781526 1413
jonathonfletcher 0:54f5be781526 1414 /* If the window is almost full and there is insufficient lookahead,
jonathonfletcher 0:54f5be781526 1415 * move the upper half to the lower one to make room in the upper half.
jonathonfletcher 0:54f5be781526 1416 */
jonathonfletcher 0:54f5be781526 1417 if (s->strstart >= wsize+MAX_DIST(s)) {
jonathonfletcher 0:54f5be781526 1418
jonathonfletcher 0:54f5be781526 1419 zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
jonathonfletcher 0:54f5be781526 1420 s->match_start -= wsize;
jonathonfletcher 0:54f5be781526 1421 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
jonathonfletcher 0:54f5be781526 1422 s->block_start -= (long) wsize;
jonathonfletcher 0:54f5be781526 1423
jonathonfletcher 0:54f5be781526 1424 /* Slide the hash table (could be avoided with 32 bit values
jonathonfletcher 0:54f5be781526 1425 at the expense of memory usage). We slide even when level == 0
jonathonfletcher 0:54f5be781526 1426 to keep the hash table consistent if we switch back to level > 0
jonathonfletcher 0:54f5be781526 1427 later. (Using level 0 permanently is not an optimal usage of
jonathonfletcher 0:54f5be781526 1428 zlib, so we don't care about this pathological case.)
jonathonfletcher 0:54f5be781526 1429 */
jonathonfletcher 0:54f5be781526 1430 n = s->hash_size;
jonathonfletcher 0:54f5be781526 1431 p = &s->head[n];
jonathonfletcher 0:54f5be781526 1432 do {
jonathonfletcher 0:54f5be781526 1433 m = *--p;
jonathonfletcher 0:54f5be781526 1434 *p = (Pos)(m >= wsize ? m-wsize : NIL);
jonathonfletcher 0:54f5be781526 1435 } while (--n);
jonathonfletcher 0:54f5be781526 1436
jonathonfletcher 0:54f5be781526 1437 n = wsize;
jonathonfletcher 0:54f5be781526 1438 #ifndef FASTEST
jonathonfletcher 0:54f5be781526 1439 p = &s->prev[n];
jonathonfletcher 0:54f5be781526 1440 do {
jonathonfletcher 0:54f5be781526 1441 m = *--p;
jonathonfletcher 0:54f5be781526 1442 *p = (Pos)(m >= wsize ? m-wsize : NIL);
jonathonfletcher 0:54f5be781526 1443 /* If n is not on any hash chain, prev[n] is garbage but
jonathonfletcher 0:54f5be781526 1444 * its value will never be used.
jonathonfletcher 0:54f5be781526 1445 */
jonathonfletcher 0:54f5be781526 1446 } while (--n);
jonathonfletcher 0:54f5be781526 1447 #endif
jonathonfletcher 0:54f5be781526 1448 more += wsize;
jonathonfletcher 0:54f5be781526 1449 }
jonathonfletcher 0:54f5be781526 1450 if (s->strm->avail_in == 0) break;
jonathonfletcher 0:54f5be781526 1451
jonathonfletcher 0:54f5be781526 1452 /* If there was no sliding:
jonathonfletcher 0:54f5be781526 1453 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
jonathonfletcher 0:54f5be781526 1454 * more == window_size - lookahead - strstart
jonathonfletcher 0:54f5be781526 1455 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
jonathonfletcher 0:54f5be781526 1456 * => more >= window_size - 2*WSIZE + 2
jonathonfletcher 0:54f5be781526 1457 * In the BIG_MEM or MMAP case (not yet supported),
jonathonfletcher 0:54f5be781526 1458 * window_size == input_size + MIN_LOOKAHEAD &&
jonathonfletcher 0:54f5be781526 1459 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
jonathonfletcher 0:54f5be781526 1460 * Otherwise, window_size == 2*WSIZE so more >= 2.
jonathonfletcher 0:54f5be781526 1461 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
jonathonfletcher 0:54f5be781526 1462 */
jonathonfletcher 0:54f5be781526 1463 Assert(more >= 2, "more < 2");
jonathonfletcher 0:54f5be781526 1464
jonathonfletcher 0:54f5be781526 1465 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
jonathonfletcher 0:54f5be781526 1466 s->lookahead += n;
jonathonfletcher 0:54f5be781526 1467
jonathonfletcher 0:54f5be781526 1468 /* Initialize the hash value now that we have some input: */
jonathonfletcher 0:54f5be781526 1469 if (s->lookahead + s->insert >= MIN_MATCH) {
jonathonfletcher 0:54f5be781526 1470 uInt str = s->strstart - s->insert;
jonathonfletcher 0:54f5be781526 1471 s->ins_h = s->window[str];
jonathonfletcher 0:54f5be781526 1472 UPDATE_HASH(s, s->ins_h, s->window[str + 1]);
jonathonfletcher 0:54f5be781526 1473 #if MIN_MATCH != 3
jonathonfletcher 0:54f5be781526 1474 Call UPDATE_HASH() MIN_MATCH-3 more times
jonathonfletcher 0:54f5be781526 1475 #endif
jonathonfletcher 0:54f5be781526 1476 while (s->insert) {
jonathonfletcher 0:54f5be781526 1477 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
jonathonfletcher 0:54f5be781526 1478 #ifndef FASTEST
jonathonfletcher 0:54f5be781526 1479 s->prev[str & s->w_mask] = s->head[s->ins_h];
jonathonfletcher 0:54f5be781526 1480 #endif
jonathonfletcher 0:54f5be781526 1481 s->head[s->ins_h] = (Pos)str;
jonathonfletcher 0:54f5be781526 1482 str++;
jonathonfletcher 0:54f5be781526 1483 s->insert--;
jonathonfletcher 0:54f5be781526 1484 if (s->lookahead + s->insert < MIN_MATCH)
jonathonfletcher 0:54f5be781526 1485 break;
jonathonfletcher 0:54f5be781526 1486 }
jonathonfletcher 0:54f5be781526 1487 }
jonathonfletcher 0:54f5be781526 1488 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
jonathonfletcher 0:54f5be781526 1489 * but this is not important since only literal bytes will be emitted.
jonathonfletcher 0:54f5be781526 1490 */
jonathonfletcher 0:54f5be781526 1491
jonathonfletcher 0:54f5be781526 1492 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
jonathonfletcher 0:54f5be781526 1493
jonathonfletcher 0:54f5be781526 1494 /* If the WIN_INIT bytes after the end of the current data have never been
jonathonfletcher 0:54f5be781526 1495 * written, then zero those bytes in order to avoid memory check reports of
jonathonfletcher 0:54f5be781526 1496 * the use of uninitialized (or uninitialised as Julian writes) bytes by
jonathonfletcher 0:54f5be781526 1497 * the longest match routines. Update the high water mark for the next
jonathonfletcher 0:54f5be781526 1498 * time through here. WIN_INIT is set to MAX_MATCH since the longest match
jonathonfletcher 0:54f5be781526 1499 * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
jonathonfletcher 0:54f5be781526 1500 */
jonathonfletcher 0:54f5be781526 1501 if (s->high_water < s->window_size) {
jonathonfletcher 0:54f5be781526 1502 ulg curr = s->strstart + (ulg)(s->lookahead);
jonathonfletcher 0:54f5be781526 1503 ulg init;
jonathonfletcher 0:54f5be781526 1504
jonathonfletcher 0:54f5be781526 1505 if (s->high_water < curr) {
jonathonfletcher 0:54f5be781526 1506 /* Previous high water mark below current data -- zero WIN_INIT
jonathonfletcher 0:54f5be781526 1507 * bytes or up to end of window, whichever is less.
jonathonfletcher 0:54f5be781526 1508 */
jonathonfletcher 0:54f5be781526 1509 init = s->window_size - curr;
jonathonfletcher 0:54f5be781526 1510 if (init > WIN_INIT)
jonathonfletcher 0:54f5be781526 1511 init = WIN_INIT;
jonathonfletcher 0:54f5be781526 1512 zmemzero(s->window + curr, (unsigned)init);
jonathonfletcher 0:54f5be781526 1513 s->high_water = curr + init;
jonathonfletcher 0:54f5be781526 1514 }
jonathonfletcher 0:54f5be781526 1515 else if (s->high_water < (ulg)curr + WIN_INIT) {
jonathonfletcher 0:54f5be781526 1516 /* High water mark at or above current data, but below current data
jonathonfletcher 0:54f5be781526 1517 * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
jonathonfletcher 0:54f5be781526 1518 * to end of window, whichever is less.
jonathonfletcher 0:54f5be781526 1519 */
jonathonfletcher 0:54f5be781526 1520 init = (ulg)curr + WIN_INIT - s->high_water;
jonathonfletcher 0:54f5be781526 1521 if (init > s->window_size - s->high_water)
jonathonfletcher 0:54f5be781526 1522 init = s->window_size - s->high_water;
jonathonfletcher 0:54f5be781526 1523 zmemzero(s->window + s->high_water, (unsigned)init);
jonathonfletcher 0:54f5be781526 1524 s->high_water += init;
jonathonfletcher 0:54f5be781526 1525 }
jonathonfletcher 0:54f5be781526 1526 }
jonathonfletcher 0:54f5be781526 1527
jonathonfletcher 0:54f5be781526 1528 Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD,
jonathonfletcher 0:54f5be781526 1529 "not enough room for search");
jonathonfletcher 0:54f5be781526 1530 }
jonathonfletcher 0:54f5be781526 1531
jonathonfletcher 0:54f5be781526 1532 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1533 * Flush the current block, with given end-of-file flag.
jonathonfletcher 0:54f5be781526 1534 * IN assertion: strstart is set to the end of the current match.
jonathonfletcher 0:54f5be781526 1535 */
jonathonfletcher 0:54f5be781526 1536 #define FLUSH_BLOCK_ONLY(s, last) { \
jonathonfletcher 0:54f5be781526 1537 _tr_flush_block(s, (s->block_start >= 0L ? \
jonathonfletcher 0:54f5be781526 1538 (charf *)&s->window[(unsigned)s->block_start] : \
jonathonfletcher 0:54f5be781526 1539 (charf *)Z_NULL), \
jonathonfletcher 0:54f5be781526 1540 (ulg)((long)s->strstart - s->block_start), \
jonathonfletcher 0:54f5be781526 1541 (last)); \
jonathonfletcher 0:54f5be781526 1542 s->block_start = s->strstart; \
jonathonfletcher 0:54f5be781526 1543 flush_pending(s->strm); \
jonathonfletcher 0:54f5be781526 1544 Tracev((stderr,"[FLUSH]")); \
jonathonfletcher 0:54f5be781526 1545 }
jonathonfletcher 0:54f5be781526 1546
jonathonfletcher 0:54f5be781526 1547 /* Same but force premature exit if necessary. */
jonathonfletcher 0:54f5be781526 1548 #define FLUSH_BLOCK(s, last) { \
jonathonfletcher 0:54f5be781526 1549 FLUSH_BLOCK_ONLY(s, last); \
jonathonfletcher 0:54f5be781526 1550 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
jonathonfletcher 0:54f5be781526 1551 }
jonathonfletcher 0:54f5be781526 1552
jonathonfletcher 0:54f5be781526 1553 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1554 * Copy without compression as much as possible from the input stream, return
jonathonfletcher 0:54f5be781526 1555 * the current block state.
jonathonfletcher 0:54f5be781526 1556 * This function does not insert new strings in the dictionary since
jonathonfletcher 0:54f5be781526 1557 * uncompressible data is probably not useful. This function is used
jonathonfletcher 0:54f5be781526 1558 * only for the level=0 compression option.
jonathonfletcher 0:54f5be781526 1559 * NOTE: this function should be optimized to avoid extra copying from
jonathonfletcher 0:54f5be781526 1560 * window to pending_buf.
jonathonfletcher 0:54f5be781526 1561 */
jonathonfletcher 0:54f5be781526 1562 local block_state deflate_stored(s, flush)
jonathonfletcher 0:54f5be781526 1563 deflate_state *s;
jonathonfletcher 0:54f5be781526 1564 int flush;
jonathonfletcher 0:54f5be781526 1565 {
jonathonfletcher 0:54f5be781526 1566 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
jonathonfletcher 0:54f5be781526 1567 * to pending_buf_size, and each stored block has a 5 byte header:
jonathonfletcher 0:54f5be781526 1568 */
jonathonfletcher 0:54f5be781526 1569 ulg max_block_size = 0xffff;
jonathonfletcher 0:54f5be781526 1570 ulg max_start;
jonathonfletcher 0:54f5be781526 1571
jonathonfletcher 0:54f5be781526 1572 if (max_block_size > s->pending_buf_size - 5) {
jonathonfletcher 0:54f5be781526 1573 max_block_size = s->pending_buf_size - 5;
jonathonfletcher 0:54f5be781526 1574 }
jonathonfletcher 0:54f5be781526 1575
jonathonfletcher 0:54f5be781526 1576 /* Copy as much as possible from input to output: */
jonathonfletcher 0:54f5be781526 1577 for (;;) {
jonathonfletcher 0:54f5be781526 1578 /* Fill the window as much as possible: */
jonathonfletcher 0:54f5be781526 1579 if (s->lookahead <= 1) {
jonathonfletcher 0:54f5be781526 1580
jonathonfletcher 0:54f5be781526 1581 Assert(s->strstart < s->w_size+MAX_DIST(s) ||
jonathonfletcher 0:54f5be781526 1582 s->block_start >= (long)s->w_size, "slide too late");
jonathonfletcher 0:54f5be781526 1583
jonathonfletcher 0:54f5be781526 1584 fill_window(s);
jonathonfletcher 0:54f5be781526 1585 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
jonathonfletcher 0:54f5be781526 1586
jonathonfletcher 0:54f5be781526 1587 if (s->lookahead == 0) break; /* flush the current block */
jonathonfletcher 0:54f5be781526 1588 }
jonathonfletcher 0:54f5be781526 1589 Assert(s->block_start >= 0L, "block gone");
jonathonfletcher 0:54f5be781526 1590
jonathonfletcher 0:54f5be781526 1591 s->strstart += s->lookahead;
jonathonfletcher 0:54f5be781526 1592 s->lookahead = 0;
jonathonfletcher 0:54f5be781526 1593
jonathonfletcher 0:54f5be781526 1594 /* Emit a stored block if pending_buf will be full: */
jonathonfletcher 0:54f5be781526 1595 max_start = s->block_start + max_block_size;
jonathonfletcher 0:54f5be781526 1596 if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
jonathonfletcher 0:54f5be781526 1597 /* strstart == 0 is possible when wraparound on 16-bit machine */
jonathonfletcher 0:54f5be781526 1598 s->lookahead = (uInt)(s->strstart - max_start);
jonathonfletcher 0:54f5be781526 1599 s->strstart = (uInt)max_start;
jonathonfletcher 0:54f5be781526 1600 FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1601 }
jonathonfletcher 0:54f5be781526 1602 /* Flush if we may have to slide, otherwise block_start may become
jonathonfletcher 0:54f5be781526 1603 * negative and the data will be gone:
jonathonfletcher 0:54f5be781526 1604 */
jonathonfletcher 0:54f5be781526 1605 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
jonathonfletcher 0:54f5be781526 1606 FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1607 }
jonathonfletcher 0:54f5be781526 1608 }
jonathonfletcher 0:54f5be781526 1609 s->insert = 0;
jonathonfletcher 0:54f5be781526 1610 if (flush == Z_FINISH) {
jonathonfletcher 0:54f5be781526 1611 FLUSH_BLOCK(s, 1);
jonathonfletcher 0:54f5be781526 1612 return finish_done;
jonathonfletcher 0:54f5be781526 1613 }
jonathonfletcher 0:54f5be781526 1614 if ((long)s->strstart > s->block_start)
jonathonfletcher 0:54f5be781526 1615 FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1616 return block_done;
jonathonfletcher 0:54f5be781526 1617 }
jonathonfletcher 0:54f5be781526 1618
jonathonfletcher 0:54f5be781526 1619 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1620 * Compress as much as possible from the input stream, return the current
jonathonfletcher 0:54f5be781526 1621 * block state.
jonathonfletcher 0:54f5be781526 1622 * This function does not perform lazy evaluation of matches and inserts
jonathonfletcher 0:54f5be781526 1623 * new strings in the dictionary only for unmatched strings or for short
jonathonfletcher 0:54f5be781526 1624 * matches. It is used only for the fast compression options.
jonathonfletcher 0:54f5be781526 1625 */
jonathonfletcher 0:54f5be781526 1626 local block_state deflate_fast(s, flush)
jonathonfletcher 0:54f5be781526 1627 deflate_state *s;
jonathonfletcher 0:54f5be781526 1628 int flush;
jonathonfletcher 0:54f5be781526 1629 {
jonathonfletcher 0:54f5be781526 1630 IPos hash_head; /* head of the hash chain */
jonathonfletcher 0:54f5be781526 1631 int bflush; /* set if current block must be flushed */
jonathonfletcher 0:54f5be781526 1632
jonathonfletcher 0:54f5be781526 1633 for (;;) {
jonathonfletcher 0:54f5be781526 1634 /* Make sure that we always have enough lookahead, except
jonathonfletcher 0:54f5be781526 1635 * at the end of the input file. We need MAX_MATCH bytes
jonathonfletcher 0:54f5be781526 1636 * for the next match, plus MIN_MATCH bytes to insert the
jonathonfletcher 0:54f5be781526 1637 * string following the next match.
jonathonfletcher 0:54f5be781526 1638 */
jonathonfletcher 0:54f5be781526 1639 if (s->lookahead < MIN_LOOKAHEAD) {
jonathonfletcher 0:54f5be781526 1640 fill_window(s);
jonathonfletcher 0:54f5be781526 1641 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
jonathonfletcher 0:54f5be781526 1642 return need_more;
jonathonfletcher 0:54f5be781526 1643 }
jonathonfletcher 0:54f5be781526 1644 if (s->lookahead == 0) break; /* flush the current block */
jonathonfletcher 0:54f5be781526 1645 }
jonathonfletcher 0:54f5be781526 1646
jonathonfletcher 0:54f5be781526 1647 /* Insert the string window[strstart .. strstart+2] in the
jonathonfletcher 0:54f5be781526 1648 * dictionary, and set hash_head to the head of the hash chain:
jonathonfletcher 0:54f5be781526 1649 */
jonathonfletcher 0:54f5be781526 1650 hash_head = NIL;
jonathonfletcher 0:54f5be781526 1651 if (s->lookahead >= MIN_MATCH) {
jonathonfletcher 0:54f5be781526 1652 INSERT_STRING(s, s->strstart, hash_head);
jonathonfletcher 0:54f5be781526 1653 }
jonathonfletcher 0:54f5be781526 1654
jonathonfletcher 0:54f5be781526 1655 /* Find the longest match, discarding those <= prev_length.
jonathonfletcher 0:54f5be781526 1656 * At this point we have always match_length < MIN_MATCH
jonathonfletcher 0:54f5be781526 1657 */
jonathonfletcher 0:54f5be781526 1658 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
jonathonfletcher 0:54f5be781526 1659 /* To simplify the code, we prevent matches with the string
jonathonfletcher 0:54f5be781526 1660 * of window index 0 (in particular we have to avoid a match
jonathonfletcher 0:54f5be781526 1661 * of the string with itself at the start of the input file).
jonathonfletcher 0:54f5be781526 1662 */
jonathonfletcher 0:54f5be781526 1663 s->match_length = longest_match (s, hash_head);
jonathonfletcher 0:54f5be781526 1664 /* longest_match() sets match_start */
jonathonfletcher 0:54f5be781526 1665 }
jonathonfletcher 0:54f5be781526 1666 if (s->match_length >= MIN_MATCH) {
jonathonfletcher 0:54f5be781526 1667 check_match(s, s->strstart, s->match_start, s->match_length);
jonathonfletcher 0:54f5be781526 1668
jonathonfletcher 0:54f5be781526 1669 _tr_tally_dist(s, s->strstart - s->match_start,
jonathonfletcher 0:54f5be781526 1670 s->match_length - MIN_MATCH, bflush);
jonathonfletcher 0:54f5be781526 1671
jonathonfletcher 0:54f5be781526 1672 s->lookahead -= s->match_length;
jonathonfletcher 0:54f5be781526 1673
jonathonfletcher 0:54f5be781526 1674 /* Insert new strings in the hash table only if the match length
jonathonfletcher 0:54f5be781526 1675 * is not too large. This saves time but degrades compression.
jonathonfletcher 0:54f5be781526 1676 */
jonathonfletcher 0:54f5be781526 1677 #ifndef FASTEST
jonathonfletcher 0:54f5be781526 1678 if (s->match_length <= s->max_insert_length &&
jonathonfletcher 0:54f5be781526 1679 s->lookahead >= MIN_MATCH) {
jonathonfletcher 0:54f5be781526 1680 s->match_length--; /* string at strstart already in table */
jonathonfletcher 0:54f5be781526 1681 do {
jonathonfletcher 0:54f5be781526 1682 s->strstart++;
jonathonfletcher 0:54f5be781526 1683 INSERT_STRING(s, s->strstart, hash_head);
jonathonfletcher 0:54f5be781526 1684 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
jonathonfletcher 0:54f5be781526 1685 * always MIN_MATCH bytes ahead.
jonathonfletcher 0:54f5be781526 1686 */
jonathonfletcher 0:54f5be781526 1687 } while (--s->match_length != 0);
jonathonfletcher 0:54f5be781526 1688 s->strstart++;
jonathonfletcher 0:54f5be781526 1689 } else
jonathonfletcher 0:54f5be781526 1690 #endif
jonathonfletcher 0:54f5be781526 1691 {
jonathonfletcher 0:54f5be781526 1692 s->strstart += s->match_length;
jonathonfletcher 0:54f5be781526 1693 s->match_length = 0;
jonathonfletcher 0:54f5be781526 1694 s->ins_h = s->window[s->strstart];
jonathonfletcher 0:54f5be781526 1695 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
jonathonfletcher 0:54f5be781526 1696 #if MIN_MATCH != 3
jonathonfletcher 0:54f5be781526 1697 Call UPDATE_HASH() MIN_MATCH-3 more times
jonathonfletcher 0:54f5be781526 1698 #endif
jonathonfletcher 0:54f5be781526 1699 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
jonathonfletcher 0:54f5be781526 1700 * matter since it will be recomputed at next deflate call.
jonathonfletcher 0:54f5be781526 1701 */
jonathonfletcher 0:54f5be781526 1702 }
jonathonfletcher 0:54f5be781526 1703 } else {
jonathonfletcher 0:54f5be781526 1704 /* No match, output a literal byte */
jonathonfletcher 0:54f5be781526 1705 Tracevv((stderr,"%c", s->window[s->strstart]));
jonathonfletcher 0:54f5be781526 1706 _tr_tally_lit (s, s->window[s->strstart], bflush);
jonathonfletcher 0:54f5be781526 1707 s->lookahead--;
jonathonfletcher 0:54f5be781526 1708 s->strstart++;
jonathonfletcher 0:54f5be781526 1709 }
jonathonfletcher 0:54f5be781526 1710 if (bflush) FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1711 }
jonathonfletcher 0:54f5be781526 1712 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 1713 if (flush == Z_FINISH) {
jonathonfletcher 0:54f5be781526 1714 FLUSH_BLOCK(s, 1);
jonathonfletcher 0:54f5be781526 1715 return finish_done;
jonathonfletcher 0:54f5be781526 1716 }
jonathonfletcher 0:54f5be781526 1717 if (s->last_lit)
jonathonfletcher 0:54f5be781526 1718 FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1719 return block_done;
jonathonfletcher 0:54f5be781526 1720 }
jonathonfletcher 0:54f5be781526 1721
jonathonfletcher 0:54f5be781526 1722 #ifndef FASTEST
jonathonfletcher 0:54f5be781526 1723 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1724 * Same as above, but achieves better compression. We use a lazy
jonathonfletcher 0:54f5be781526 1725 * evaluation for matches: a match is finally adopted only if there is
jonathonfletcher 0:54f5be781526 1726 * no better match at the next window position.
jonathonfletcher 0:54f5be781526 1727 */
jonathonfletcher 0:54f5be781526 1728 local block_state deflate_slow(s, flush)
jonathonfletcher 0:54f5be781526 1729 deflate_state *s;
jonathonfletcher 0:54f5be781526 1730 int flush;
jonathonfletcher 0:54f5be781526 1731 {
jonathonfletcher 0:54f5be781526 1732 IPos hash_head; /* head of hash chain */
jonathonfletcher 0:54f5be781526 1733 int bflush; /* set if current block must be flushed */
jonathonfletcher 0:54f5be781526 1734
jonathonfletcher 0:54f5be781526 1735 /* Process the input block. */
jonathonfletcher 0:54f5be781526 1736 for (;;) {
jonathonfletcher 0:54f5be781526 1737 /* Make sure that we always have enough lookahead, except
jonathonfletcher 0:54f5be781526 1738 * at the end of the input file. We need MAX_MATCH bytes
jonathonfletcher 0:54f5be781526 1739 * for the next match, plus MIN_MATCH bytes to insert the
jonathonfletcher 0:54f5be781526 1740 * string following the next match.
jonathonfletcher 0:54f5be781526 1741 */
jonathonfletcher 0:54f5be781526 1742 if (s->lookahead < MIN_LOOKAHEAD) {
jonathonfletcher 0:54f5be781526 1743 fill_window(s);
jonathonfletcher 0:54f5be781526 1744 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
jonathonfletcher 0:54f5be781526 1745 return need_more;
jonathonfletcher 0:54f5be781526 1746 }
jonathonfletcher 0:54f5be781526 1747 if (s->lookahead == 0) break; /* flush the current block */
jonathonfletcher 0:54f5be781526 1748 }
jonathonfletcher 0:54f5be781526 1749
jonathonfletcher 0:54f5be781526 1750 /* Insert the string window[strstart .. strstart+2] in the
jonathonfletcher 0:54f5be781526 1751 * dictionary, and set hash_head to the head of the hash chain:
jonathonfletcher 0:54f5be781526 1752 */
jonathonfletcher 0:54f5be781526 1753 hash_head = NIL;
jonathonfletcher 0:54f5be781526 1754 if (s->lookahead >= MIN_MATCH) {
jonathonfletcher 0:54f5be781526 1755 INSERT_STRING(s, s->strstart, hash_head);
jonathonfletcher 0:54f5be781526 1756 }
jonathonfletcher 0:54f5be781526 1757
jonathonfletcher 0:54f5be781526 1758 /* Find the longest match, discarding those <= prev_length.
jonathonfletcher 0:54f5be781526 1759 */
jonathonfletcher 0:54f5be781526 1760 s->prev_length = s->match_length, s->prev_match = s->match_start;
jonathonfletcher 0:54f5be781526 1761 s->match_length = MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 1762
jonathonfletcher 0:54f5be781526 1763 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
jonathonfletcher 0:54f5be781526 1764 s->strstart - hash_head <= MAX_DIST(s)) {
jonathonfletcher 0:54f5be781526 1765 /* To simplify the code, we prevent matches with the string
jonathonfletcher 0:54f5be781526 1766 * of window index 0 (in particular we have to avoid a match
jonathonfletcher 0:54f5be781526 1767 * of the string with itself at the start of the input file).
jonathonfletcher 0:54f5be781526 1768 */
jonathonfletcher 0:54f5be781526 1769 s->match_length = longest_match (s, hash_head);
jonathonfletcher 0:54f5be781526 1770 /* longest_match() sets match_start */
jonathonfletcher 0:54f5be781526 1771
jonathonfletcher 0:54f5be781526 1772 if (s->match_length <= 5 && (s->strategy == Z_FILTERED
jonathonfletcher 0:54f5be781526 1773 #if TOO_FAR <= 32767
jonathonfletcher 0:54f5be781526 1774 || (s->match_length == MIN_MATCH &&
jonathonfletcher 0:54f5be781526 1775 s->strstart - s->match_start > TOO_FAR)
jonathonfletcher 0:54f5be781526 1776 #endif
jonathonfletcher 0:54f5be781526 1777 )) {
jonathonfletcher 0:54f5be781526 1778
jonathonfletcher 0:54f5be781526 1779 /* If prev_match is also MIN_MATCH, match_start is garbage
jonathonfletcher 0:54f5be781526 1780 * but we will ignore the current match anyway.
jonathonfletcher 0:54f5be781526 1781 */
jonathonfletcher 0:54f5be781526 1782 s->match_length = MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 1783 }
jonathonfletcher 0:54f5be781526 1784 }
jonathonfletcher 0:54f5be781526 1785 /* If there was a match at the previous step and the current
jonathonfletcher 0:54f5be781526 1786 * match is not better, output the previous match:
jonathonfletcher 0:54f5be781526 1787 */
jonathonfletcher 0:54f5be781526 1788 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
jonathonfletcher 0:54f5be781526 1789 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
jonathonfletcher 0:54f5be781526 1790 /* Do not insert strings in hash table beyond this. */
jonathonfletcher 0:54f5be781526 1791
jonathonfletcher 0:54f5be781526 1792 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
jonathonfletcher 0:54f5be781526 1793
jonathonfletcher 0:54f5be781526 1794 _tr_tally_dist(s, s->strstart -1 - s->prev_match,
jonathonfletcher 0:54f5be781526 1795 s->prev_length - MIN_MATCH, bflush);
jonathonfletcher 0:54f5be781526 1796
jonathonfletcher 0:54f5be781526 1797 /* Insert in hash table all strings up to the end of the match.
jonathonfletcher 0:54f5be781526 1798 * strstart-1 and strstart are already inserted. If there is not
jonathonfletcher 0:54f5be781526 1799 * enough lookahead, the last two strings are not inserted in
jonathonfletcher 0:54f5be781526 1800 * the hash table.
jonathonfletcher 0:54f5be781526 1801 */
jonathonfletcher 0:54f5be781526 1802 s->lookahead -= s->prev_length-1;
jonathonfletcher 0:54f5be781526 1803 s->prev_length -= 2;
jonathonfletcher 0:54f5be781526 1804 do {
jonathonfletcher 0:54f5be781526 1805 if (++s->strstart <= max_insert) {
jonathonfletcher 0:54f5be781526 1806 INSERT_STRING(s, s->strstart, hash_head);
jonathonfletcher 0:54f5be781526 1807 }
jonathonfletcher 0:54f5be781526 1808 } while (--s->prev_length != 0);
jonathonfletcher 0:54f5be781526 1809 s->match_available = 0;
jonathonfletcher 0:54f5be781526 1810 s->match_length = MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 1811 s->strstart++;
jonathonfletcher 0:54f5be781526 1812
jonathonfletcher 0:54f5be781526 1813 if (bflush) FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1814
jonathonfletcher 0:54f5be781526 1815 } else if (s->match_available) {
jonathonfletcher 0:54f5be781526 1816 /* If there was no match at the previous position, output a
jonathonfletcher 0:54f5be781526 1817 * single literal. If there was a match but the current match
jonathonfletcher 0:54f5be781526 1818 * is longer, truncate the previous match to a single literal.
jonathonfletcher 0:54f5be781526 1819 */
jonathonfletcher 0:54f5be781526 1820 Tracevv((stderr,"%c", s->window[s->strstart-1]));
jonathonfletcher 0:54f5be781526 1821 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
jonathonfletcher 0:54f5be781526 1822 if (bflush) {
jonathonfletcher 0:54f5be781526 1823 FLUSH_BLOCK_ONLY(s, 0);
jonathonfletcher 0:54f5be781526 1824 }
jonathonfletcher 0:54f5be781526 1825 s->strstart++;
jonathonfletcher 0:54f5be781526 1826 s->lookahead--;
jonathonfletcher 0:54f5be781526 1827 if (s->strm->avail_out == 0) return need_more;
jonathonfletcher 0:54f5be781526 1828 } else {
jonathonfletcher 0:54f5be781526 1829 /* There is no previous match to compare with, wait for
jonathonfletcher 0:54f5be781526 1830 * the next step to decide.
jonathonfletcher 0:54f5be781526 1831 */
jonathonfletcher 0:54f5be781526 1832 s->match_available = 1;
jonathonfletcher 0:54f5be781526 1833 s->strstart++;
jonathonfletcher 0:54f5be781526 1834 s->lookahead--;
jonathonfletcher 0:54f5be781526 1835 }
jonathonfletcher 0:54f5be781526 1836 }
jonathonfletcher 0:54f5be781526 1837 Assert (flush != Z_NO_FLUSH, "no flush?");
jonathonfletcher 0:54f5be781526 1838 if (s->match_available) {
jonathonfletcher 0:54f5be781526 1839 Tracevv((stderr,"%c", s->window[s->strstart-1]));
jonathonfletcher 0:54f5be781526 1840 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
jonathonfletcher 0:54f5be781526 1841 s->match_available = 0;
jonathonfletcher 0:54f5be781526 1842 }
jonathonfletcher 0:54f5be781526 1843 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
jonathonfletcher 0:54f5be781526 1844 if (flush == Z_FINISH) {
jonathonfletcher 0:54f5be781526 1845 FLUSH_BLOCK(s, 1);
jonathonfletcher 0:54f5be781526 1846 return finish_done;
jonathonfletcher 0:54f5be781526 1847 }
jonathonfletcher 0:54f5be781526 1848 if (s->last_lit)
jonathonfletcher 0:54f5be781526 1849 FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1850 return block_done;
jonathonfletcher 0:54f5be781526 1851 }
jonathonfletcher 0:54f5be781526 1852 #endif /* FASTEST */
jonathonfletcher 0:54f5be781526 1853
jonathonfletcher 0:54f5be781526 1854 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1855 * For Z_RLE, simply look for runs of bytes, generate matches only of distance
jonathonfletcher 0:54f5be781526 1856 * one. Do not maintain a hash table. (It will be regenerated if this run of
jonathonfletcher 0:54f5be781526 1857 * deflate switches away from Z_RLE.)
jonathonfletcher 0:54f5be781526 1858 */
jonathonfletcher 0:54f5be781526 1859 local block_state deflate_rle(s, flush)
jonathonfletcher 0:54f5be781526 1860 deflate_state *s;
jonathonfletcher 0:54f5be781526 1861 int flush;
jonathonfletcher 0:54f5be781526 1862 {
jonathonfletcher 0:54f5be781526 1863 int bflush; /* set if current block must be flushed */
jonathonfletcher 0:54f5be781526 1864 uInt prev; /* byte at distance one to match */
jonathonfletcher 0:54f5be781526 1865 Bytef *scan, *strend; /* scan goes up to strend for length of run */
jonathonfletcher 0:54f5be781526 1866
jonathonfletcher 0:54f5be781526 1867 for (;;) {
jonathonfletcher 0:54f5be781526 1868 /* Make sure that we always have enough lookahead, except
jonathonfletcher 0:54f5be781526 1869 * at the end of the input file. We need MAX_MATCH bytes
jonathonfletcher 0:54f5be781526 1870 * for the longest run, plus one for the unrolled loop.
jonathonfletcher 0:54f5be781526 1871 */
jonathonfletcher 0:54f5be781526 1872 if (s->lookahead <= MAX_MATCH) {
jonathonfletcher 0:54f5be781526 1873 fill_window(s);
jonathonfletcher 0:54f5be781526 1874 if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) {
jonathonfletcher 0:54f5be781526 1875 return need_more;
jonathonfletcher 0:54f5be781526 1876 }
jonathonfletcher 0:54f5be781526 1877 if (s->lookahead == 0) break; /* flush the current block */
jonathonfletcher 0:54f5be781526 1878 }
jonathonfletcher 0:54f5be781526 1879
jonathonfletcher 0:54f5be781526 1880 /* See how many times the previous byte repeats */
jonathonfletcher 0:54f5be781526 1881 s->match_length = 0;
jonathonfletcher 0:54f5be781526 1882 if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
jonathonfletcher 0:54f5be781526 1883 scan = s->window + s->strstart - 1;
jonathonfletcher 0:54f5be781526 1884 prev = *scan;
jonathonfletcher 0:54f5be781526 1885 if (prev == *++scan && prev == *++scan && prev == *++scan) {
jonathonfletcher 0:54f5be781526 1886 strend = s->window + s->strstart + MAX_MATCH;
jonathonfletcher 0:54f5be781526 1887 do {
jonathonfletcher 0:54f5be781526 1888 } while (prev == *++scan && prev == *++scan &&
jonathonfletcher 0:54f5be781526 1889 prev == *++scan && prev == *++scan &&
jonathonfletcher 0:54f5be781526 1890 prev == *++scan && prev == *++scan &&
jonathonfletcher 0:54f5be781526 1891 prev == *++scan && prev == *++scan &&
jonathonfletcher 0:54f5be781526 1892 scan < strend);
jonathonfletcher 0:54f5be781526 1893 s->match_length = MAX_MATCH - (int)(strend - scan);
jonathonfletcher 0:54f5be781526 1894 if (s->match_length > s->lookahead)
jonathonfletcher 0:54f5be781526 1895 s->match_length = s->lookahead;
jonathonfletcher 0:54f5be781526 1896 }
jonathonfletcher 0:54f5be781526 1897 Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan");
jonathonfletcher 0:54f5be781526 1898 }
jonathonfletcher 0:54f5be781526 1899
jonathonfletcher 0:54f5be781526 1900 /* Emit match if have run of MIN_MATCH or longer, else emit literal */
jonathonfletcher 0:54f5be781526 1901 if (s->match_length >= MIN_MATCH) {
jonathonfletcher 0:54f5be781526 1902 check_match(s, s->strstart, s->strstart - 1, s->match_length);
jonathonfletcher 0:54f5be781526 1903
jonathonfletcher 0:54f5be781526 1904 _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);
jonathonfletcher 0:54f5be781526 1905
jonathonfletcher 0:54f5be781526 1906 s->lookahead -= s->match_length;
jonathonfletcher 0:54f5be781526 1907 s->strstart += s->match_length;
jonathonfletcher 0:54f5be781526 1908 s->match_length = 0;
jonathonfletcher 0:54f5be781526 1909 } else {
jonathonfletcher 0:54f5be781526 1910 /* No match, output a literal byte */
jonathonfletcher 0:54f5be781526 1911 Tracevv((stderr,"%c", s->window[s->strstart]));
jonathonfletcher 0:54f5be781526 1912 _tr_tally_lit (s, s->window[s->strstart], bflush);
jonathonfletcher 0:54f5be781526 1913 s->lookahead--;
jonathonfletcher 0:54f5be781526 1914 s->strstart++;
jonathonfletcher 0:54f5be781526 1915 }
jonathonfletcher 0:54f5be781526 1916 if (bflush) FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1917 }
jonathonfletcher 0:54f5be781526 1918 s->insert = 0;
jonathonfletcher 0:54f5be781526 1919 if (flush == Z_FINISH) {
jonathonfletcher 0:54f5be781526 1920 FLUSH_BLOCK(s, 1);
jonathonfletcher 0:54f5be781526 1921 return finish_done;
jonathonfletcher 0:54f5be781526 1922 }
jonathonfletcher 0:54f5be781526 1923 if (s->last_lit)
jonathonfletcher 0:54f5be781526 1924 FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1925 return block_done;
jonathonfletcher 0:54f5be781526 1926 }
jonathonfletcher 0:54f5be781526 1927
jonathonfletcher 0:54f5be781526 1928 /* ===========================================================================
jonathonfletcher 0:54f5be781526 1929 * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.
jonathonfletcher 0:54f5be781526 1930 * (It will be regenerated if this run of deflate switches away from Huffman.)
jonathonfletcher 0:54f5be781526 1931 */
jonathonfletcher 0:54f5be781526 1932 local block_state deflate_huff(s, flush)
jonathonfletcher 0:54f5be781526 1933 deflate_state *s;
jonathonfletcher 0:54f5be781526 1934 int flush;
jonathonfletcher 0:54f5be781526 1935 {
jonathonfletcher 0:54f5be781526 1936 int bflush; /* set if current block must be flushed */
jonathonfletcher 0:54f5be781526 1937
jonathonfletcher 0:54f5be781526 1938 for (;;) {
jonathonfletcher 0:54f5be781526 1939 /* Make sure that we have a literal to write. */
jonathonfletcher 0:54f5be781526 1940 if (s->lookahead == 0) {
jonathonfletcher 0:54f5be781526 1941 fill_window(s);
jonathonfletcher 0:54f5be781526 1942 if (s->lookahead == 0) {
jonathonfletcher 0:54f5be781526 1943 if (flush == Z_NO_FLUSH)
jonathonfletcher 0:54f5be781526 1944 return need_more;
jonathonfletcher 0:54f5be781526 1945 break; /* flush the current block */
jonathonfletcher 0:54f5be781526 1946 }
jonathonfletcher 0:54f5be781526 1947 }
jonathonfletcher 0:54f5be781526 1948
jonathonfletcher 0:54f5be781526 1949 /* Output a literal byte */
jonathonfletcher 0:54f5be781526 1950 s->match_length = 0;
jonathonfletcher 0:54f5be781526 1951 Tracevv((stderr,"%c", s->window[s->strstart]));
jonathonfletcher 0:54f5be781526 1952 _tr_tally_lit (s, s->window[s->strstart], bflush);
jonathonfletcher 0:54f5be781526 1953 s->lookahead--;
jonathonfletcher 0:54f5be781526 1954 s->strstart++;
jonathonfletcher 0:54f5be781526 1955 if (bflush) FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1956 }
jonathonfletcher 0:54f5be781526 1957 s->insert = 0;
jonathonfletcher 0:54f5be781526 1958 if (flush == Z_FINISH) {
jonathonfletcher 0:54f5be781526 1959 FLUSH_BLOCK(s, 1);
jonathonfletcher 0:54f5be781526 1960 return finish_done;
jonathonfletcher 0:54f5be781526 1961 }
jonathonfletcher 0:54f5be781526 1962 if (s->last_lit)
jonathonfletcher 0:54f5be781526 1963 FLUSH_BLOCK(s, 0);
jonathonfletcher 0:54f5be781526 1964 return block_done;
jonathonfletcher 0:54f5be781526 1965 }