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 /* inftrees.c -- generate Huffman trees for efficient decoding
jonathonfletcher 0:54f5be781526 2 * Copyright (C) 1995-2012 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 #include "zutil.h"
jonathonfletcher 0:54f5be781526 7 #include "inftrees.h"
jonathonfletcher 0:54f5be781526 8
jonathonfletcher 0:54f5be781526 9 #define MAXBITS 15
jonathonfletcher 0:54f5be781526 10
jonathonfletcher 0:54f5be781526 11 const char inflate_copyright[] =
jonathonfletcher 0:54f5be781526 12 " inflate 1.2.7 Copyright 1995-2012 Mark Adler ";
jonathonfletcher 0:54f5be781526 13 /*
jonathonfletcher 0:54f5be781526 14 If you use the zlib library in a product, an acknowledgment is welcome
jonathonfletcher 0:54f5be781526 15 in the documentation of your product. If for some reason you cannot
jonathonfletcher 0:54f5be781526 16 include such an acknowledgment, I would appreciate that you keep this
jonathonfletcher 0:54f5be781526 17 copyright string in the executable of your product.
jonathonfletcher 0:54f5be781526 18 */
jonathonfletcher 0:54f5be781526 19
jonathonfletcher 0:54f5be781526 20 /*
jonathonfletcher 0:54f5be781526 21 Build a set of tables to decode the provided canonical Huffman code.
jonathonfletcher 0:54f5be781526 22 The code lengths are lens[0..codes-1]. The result starts at *table,
jonathonfletcher 0:54f5be781526 23 whose indices are 0..2^bits-1. work is a writable array of at least
jonathonfletcher 0:54f5be781526 24 lens shorts, which is used as a work area. type is the type of code
jonathonfletcher 0:54f5be781526 25 to be generated, CODES, LENS, or DISTS. On return, zero is success,
jonathonfletcher 0:54f5be781526 26 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
jonathonfletcher 0:54f5be781526 27 on return points to the next available entry's address. bits is the
jonathonfletcher 0:54f5be781526 28 requested root table index bits, and on return it is the actual root
jonathonfletcher 0:54f5be781526 29 table index bits. It will differ if the request is greater than the
jonathonfletcher 0:54f5be781526 30 longest code or if it is less than the shortest code.
jonathonfletcher 0:54f5be781526 31 */
jonathonfletcher 0:54f5be781526 32 int ZLIB_INTERNAL inflate_table(type, lens, codes, table, bits, work)
jonathonfletcher 0:54f5be781526 33 codetype type;
jonathonfletcher 0:54f5be781526 34 unsigned short FAR *lens;
jonathonfletcher 0:54f5be781526 35 unsigned codes;
jonathonfletcher 0:54f5be781526 36 code FAR * FAR *table;
jonathonfletcher 0:54f5be781526 37 unsigned FAR *bits;
jonathonfletcher 0:54f5be781526 38 unsigned short FAR *work;
jonathonfletcher 0:54f5be781526 39 {
jonathonfletcher 0:54f5be781526 40 unsigned len; /* a code's length in bits */
jonathonfletcher 0:54f5be781526 41 unsigned sym; /* index of code symbols */
jonathonfletcher 0:54f5be781526 42 unsigned min, max; /* minimum and maximum code lengths */
jonathonfletcher 0:54f5be781526 43 unsigned root; /* number of index bits for root table */
jonathonfletcher 0:54f5be781526 44 unsigned curr; /* number of index bits for current table */
jonathonfletcher 0:54f5be781526 45 unsigned drop; /* code bits to drop for sub-table */
jonathonfletcher 0:54f5be781526 46 int left; /* number of prefix codes available */
jonathonfletcher 0:54f5be781526 47 unsigned used; /* code entries in table used */
jonathonfletcher 0:54f5be781526 48 unsigned huff; /* Huffman code */
jonathonfletcher 0:54f5be781526 49 unsigned incr; /* for incrementing code, index */
jonathonfletcher 0:54f5be781526 50 unsigned fill; /* index for replicating entries */
jonathonfletcher 0:54f5be781526 51 unsigned low; /* low bits for current root entry */
jonathonfletcher 0:54f5be781526 52 unsigned mask; /* mask for low root bits */
jonathonfletcher 0:54f5be781526 53 code here; /* table entry for duplication */
jonathonfletcher 0:54f5be781526 54 code FAR *next; /* next available space in table */
jonathonfletcher 0:54f5be781526 55 const unsigned short FAR *base; /* base value table to use */
jonathonfletcher 0:54f5be781526 56 const unsigned short FAR *extra; /* extra bits table to use */
jonathonfletcher 0:54f5be781526 57 int end; /* use base and extra for symbol > end */
jonathonfletcher 0:54f5be781526 58 unsigned short count[MAXBITS+1]; /* number of codes of each length */
jonathonfletcher 0:54f5be781526 59 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
jonathonfletcher 0:54f5be781526 60 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
jonathonfletcher 0:54f5be781526 61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
jonathonfletcher 0:54f5be781526 62 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
jonathonfletcher 0:54f5be781526 63 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
jonathonfletcher 0:54f5be781526 64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
jonathonfletcher 0:54f5be781526 65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 78, 68};
jonathonfletcher 0:54f5be781526 66 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
jonathonfletcher 0:54f5be781526 67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
jonathonfletcher 0:54f5be781526 68 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
jonathonfletcher 0:54f5be781526 69 8193, 12289, 16385, 24577, 0, 0};
jonathonfletcher 0:54f5be781526 70 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
jonathonfletcher 0:54f5be781526 71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
jonathonfletcher 0:54f5be781526 72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
jonathonfletcher 0:54f5be781526 73 28, 28, 29, 29, 64, 64};
jonathonfletcher 0:54f5be781526 74
jonathonfletcher 0:54f5be781526 75 /*
jonathonfletcher 0:54f5be781526 76 Process a set of code lengths to create a canonical Huffman code. The
jonathonfletcher 0:54f5be781526 77 code lengths are lens[0..codes-1]. Each length corresponds to the
jonathonfletcher 0:54f5be781526 78 symbols 0..codes-1. The Huffman code is generated by first sorting the
jonathonfletcher 0:54f5be781526 79 symbols by length from short to long, and retaining the symbol order
jonathonfletcher 0:54f5be781526 80 for codes with equal lengths. Then the code starts with all zero bits
jonathonfletcher 0:54f5be781526 81 for the first code of the shortest length, and the codes are integer
jonathonfletcher 0:54f5be781526 82 increments for the same length, and zeros are appended as the length
jonathonfletcher 0:54f5be781526 83 increases. For the deflate format, these bits are stored backwards
jonathonfletcher 0:54f5be781526 84 from their more natural integer increment ordering, and so when the
jonathonfletcher 0:54f5be781526 85 decoding tables are built in the large loop below, the integer codes
jonathonfletcher 0:54f5be781526 86 are incremented backwards.
jonathonfletcher 0:54f5be781526 87
jonathonfletcher 0:54f5be781526 88 This routine assumes, but does not check, that all of the entries in
jonathonfletcher 0:54f5be781526 89 lens[] are in the range 0..MAXBITS. The caller must assure this.
jonathonfletcher 0:54f5be781526 90 1..MAXBITS is interpreted as that code length. zero means that that
jonathonfletcher 0:54f5be781526 91 symbol does not occur in this code.
jonathonfletcher 0:54f5be781526 92
jonathonfletcher 0:54f5be781526 93 The codes are sorted by computing a count of codes for each length,
jonathonfletcher 0:54f5be781526 94 creating from that a table of starting indices for each length in the
jonathonfletcher 0:54f5be781526 95 sorted table, and then entering the symbols in order in the sorted
jonathonfletcher 0:54f5be781526 96 table. The sorted table is work[], with that space being provided by
jonathonfletcher 0:54f5be781526 97 the caller.
jonathonfletcher 0:54f5be781526 98
jonathonfletcher 0:54f5be781526 99 The length counts are used for other purposes as well, i.e. finding
jonathonfletcher 0:54f5be781526 100 the minimum and maximum length codes, determining if there are any
jonathonfletcher 0:54f5be781526 101 codes at all, checking for a valid set of lengths, and looking ahead
jonathonfletcher 0:54f5be781526 102 at length counts to determine sub-table sizes when building the
jonathonfletcher 0:54f5be781526 103 decoding tables.
jonathonfletcher 0:54f5be781526 104 */
jonathonfletcher 0:54f5be781526 105
jonathonfletcher 0:54f5be781526 106 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
jonathonfletcher 0:54f5be781526 107 for (len = 0; len <= MAXBITS; len++)
jonathonfletcher 0:54f5be781526 108 count[len] = 0;
jonathonfletcher 0:54f5be781526 109 for (sym = 0; sym < codes; sym++)
jonathonfletcher 0:54f5be781526 110 count[lens[sym]]++;
jonathonfletcher 0:54f5be781526 111
jonathonfletcher 0:54f5be781526 112 /* bound code lengths, force root to be within code lengths */
jonathonfletcher 0:54f5be781526 113 root = *bits;
jonathonfletcher 0:54f5be781526 114 for (max = MAXBITS; max >= 1; max--)
jonathonfletcher 0:54f5be781526 115 if (count[max] != 0) break;
jonathonfletcher 0:54f5be781526 116 if (root > max) root = max;
jonathonfletcher 0:54f5be781526 117 if (max == 0) { /* no symbols to code at all */
jonathonfletcher 0:54f5be781526 118 here.op = (unsigned char)64; /* invalid code marker */
jonathonfletcher 0:54f5be781526 119 here.bits = (unsigned char)1;
jonathonfletcher 0:54f5be781526 120 here.val = (unsigned short)0;
jonathonfletcher 0:54f5be781526 121 *(*table)++ = here; /* make a table to force an error */
jonathonfletcher 0:54f5be781526 122 *(*table)++ = here;
jonathonfletcher 0:54f5be781526 123 *bits = 1;
jonathonfletcher 0:54f5be781526 124 return 0; /* no symbols, but wait for decoding to report error */
jonathonfletcher 0:54f5be781526 125 }
jonathonfletcher 0:54f5be781526 126 for (min = 1; min < max; min++)
jonathonfletcher 0:54f5be781526 127 if (count[min] != 0) break;
jonathonfletcher 0:54f5be781526 128 if (root < min) root = min;
jonathonfletcher 0:54f5be781526 129
jonathonfletcher 0:54f5be781526 130 /* check for an over-subscribed or incomplete set of lengths */
jonathonfletcher 0:54f5be781526 131 left = 1;
jonathonfletcher 0:54f5be781526 132 for (len = 1; len <= MAXBITS; len++) {
jonathonfletcher 0:54f5be781526 133 left <<= 1;
jonathonfletcher 0:54f5be781526 134 left -= count[len];
jonathonfletcher 0:54f5be781526 135 if (left < 0) return -1; /* over-subscribed */
jonathonfletcher 0:54f5be781526 136 }
jonathonfletcher 0:54f5be781526 137 if (left > 0 && (type == CODES || max != 1))
jonathonfletcher 0:54f5be781526 138 return -1; /* incomplete set */
jonathonfletcher 0:54f5be781526 139
jonathonfletcher 0:54f5be781526 140 /* generate offsets into symbol table for each length for sorting */
jonathonfletcher 0:54f5be781526 141 offs[1] = 0;
jonathonfletcher 0:54f5be781526 142 for (len = 1; len < MAXBITS; len++)
jonathonfletcher 0:54f5be781526 143 offs[len + 1] = offs[len] + count[len];
jonathonfletcher 0:54f5be781526 144
jonathonfletcher 0:54f5be781526 145 /* sort symbols by length, by symbol order within each length */
jonathonfletcher 0:54f5be781526 146 for (sym = 0; sym < codes; sym++)
jonathonfletcher 0:54f5be781526 147 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
jonathonfletcher 0:54f5be781526 148
jonathonfletcher 0:54f5be781526 149 /*
jonathonfletcher 0:54f5be781526 150 Create and fill in decoding tables. In this loop, the table being
jonathonfletcher 0:54f5be781526 151 filled is at next and has curr index bits. The code being used is huff
jonathonfletcher 0:54f5be781526 152 with length len. That code is converted to an index by dropping drop
jonathonfletcher 0:54f5be781526 153 bits off of the bottom. For codes where len is less than drop + curr,
jonathonfletcher 0:54f5be781526 154 those top drop + curr - len bits are incremented through all values to
jonathonfletcher 0:54f5be781526 155 fill the table with replicated entries.
jonathonfletcher 0:54f5be781526 156
jonathonfletcher 0:54f5be781526 157 root is the number of index bits for the root table. When len exceeds
jonathonfletcher 0:54f5be781526 158 root, sub-tables are created pointed to by the root entry with an index
jonathonfletcher 0:54f5be781526 159 of the low root bits of huff. This is saved in low to check for when a
jonathonfletcher 0:54f5be781526 160 new sub-table should be started. drop is zero when the root table is
jonathonfletcher 0:54f5be781526 161 being filled, and drop is root when sub-tables are being filled.
jonathonfletcher 0:54f5be781526 162
jonathonfletcher 0:54f5be781526 163 When a new sub-table is needed, it is necessary to look ahead in the
jonathonfletcher 0:54f5be781526 164 code lengths to determine what size sub-table is needed. The length
jonathonfletcher 0:54f5be781526 165 counts are used for this, and so count[] is decremented as codes are
jonathonfletcher 0:54f5be781526 166 entered in the tables.
jonathonfletcher 0:54f5be781526 167
jonathonfletcher 0:54f5be781526 168 used keeps track of how many table entries have been allocated from the
jonathonfletcher 0:54f5be781526 169 provided *table space. It is checked for LENS and DIST tables against
jonathonfletcher 0:54f5be781526 170 the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in
jonathonfletcher 0:54f5be781526 171 the initial root table size constants. See the comments in inftrees.h
jonathonfletcher 0:54f5be781526 172 for more information.
jonathonfletcher 0:54f5be781526 173
jonathonfletcher 0:54f5be781526 174 sym increments through all symbols, and the loop terminates when
jonathonfletcher 0:54f5be781526 175 all codes of length max, i.e. all codes, have been processed. This
jonathonfletcher 0:54f5be781526 176 routine permits incomplete codes, so another loop after this one fills
jonathonfletcher 0:54f5be781526 177 in the rest of the decoding tables with invalid code markers.
jonathonfletcher 0:54f5be781526 178 */
jonathonfletcher 0:54f5be781526 179
jonathonfletcher 0:54f5be781526 180 /* set up for code type */
jonathonfletcher 0:54f5be781526 181 switch (type) {
jonathonfletcher 0:54f5be781526 182 case CODES:
jonathonfletcher 0:54f5be781526 183 base = extra = work; /* dummy value--not used */
jonathonfletcher 0:54f5be781526 184 end = 19;
jonathonfletcher 0:54f5be781526 185 break;
jonathonfletcher 0:54f5be781526 186 case LENS:
jonathonfletcher 0:54f5be781526 187 base = lbase;
jonathonfletcher 0:54f5be781526 188 base -= 257;
jonathonfletcher 0:54f5be781526 189 extra = lext;
jonathonfletcher 0:54f5be781526 190 extra -= 257;
jonathonfletcher 0:54f5be781526 191 end = 256;
jonathonfletcher 0:54f5be781526 192 break;
jonathonfletcher 0:54f5be781526 193 default: /* DISTS */
jonathonfletcher 0:54f5be781526 194 base = dbase;
jonathonfletcher 0:54f5be781526 195 extra = dext;
jonathonfletcher 0:54f5be781526 196 end = -1;
jonathonfletcher 0:54f5be781526 197 }
jonathonfletcher 0:54f5be781526 198
jonathonfletcher 0:54f5be781526 199 /* initialize state for loop */
jonathonfletcher 0:54f5be781526 200 huff = 0; /* starting code */
jonathonfletcher 0:54f5be781526 201 sym = 0; /* starting code symbol */
jonathonfletcher 0:54f5be781526 202 len = min; /* starting code length */
jonathonfletcher 0:54f5be781526 203 next = *table; /* current table to fill in */
jonathonfletcher 0:54f5be781526 204 curr = root; /* current table index bits */
jonathonfletcher 0:54f5be781526 205 drop = 0; /* current bits to drop from code for index */
jonathonfletcher 0:54f5be781526 206 low = (unsigned)(-1); /* trigger new sub-table when len > root */
jonathonfletcher 0:54f5be781526 207 used = 1U << root; /* use root table entries */
jonathonfletcher 0:54f5be781526 208 mask = used - 1; /* mask for comparing low */
jonathonfletcher 0:54f5be781526 209
jonathonfletcher 0:54f5be781526 210 /* check available table space */
jonathonfletcher 0:54f5be781526 211 if ((type == LENS && used >= ENOUGH_LENS) ||
jonathonfletcher 0:54f5be781526 212 (type == DISTS && used >= ENOUGH_DISTS))
jonathonfletcher 0:54f5be781526 213 return 1;
jonathonfletcher 0:54f5be781526 214
jonathonfletcher 0:54f5be781526 215 /* process all codes and make table entries */
jonathonfletcher 0:54f5be781526 216 for (;;) {
jonathonfletcher 0:54f5be781526 217 /* create table entry */
jonathonfletcher 0:54f5be781526 218 here.bits = (unsigned char)(len - drop);
jonathonfletcher 0:54f5be781526 219 if ((int)(work[sym]) < end) {
jonathonfletcher 0:54f5be781526 220 here.op = (unsigned char)0;
jonathonfletcher 0:54f5be781526 221 here.val = work[sym];
jonathonfletcher 0:54f5be781526 222 }
jonathonfletcher 0:54f5be781526 223 else if ((int)(work[sym]) > end) {
jonathonfletcher 0:54f5be781526 224 here.op = (unsigned char)(extra[work[sym]]);
jonathonfletcher 0:54f5be781526 225 here.val = base[work[sym]];
jonathonfletcher 0:54f5be781526 226 }
jonathonfletcher 0:54f5be781526 227 else {
jonathonfletcher 0:54f5be781526 228 here.op = (unsigned char)(32 + 64); /* end of block */
jonathonfletcher 0:54f5be781526 229 here.val = 0;
jonathonfletcher 0:54f5be781526 230 }
jonathonfletcher 0:54f5be781526 231
jonathonfletcher 0:54f5be781526 232 /* replicate for those indices with low len bits equal to huff */
jonathonfletcher 0:54f5be781526 233 incr = 1U << (len - drop);
jonathonfletcher 0:54f5be781526 234 fill = 1U << curr;
jonathonfletcher 0:54f5be781526 235 min = fill; /* save offset to next table */
jonathonfletcher 0:54f5be781526 236 do {
jonathonfletcher 0:54f5be781526 237 fill -= incr;
jonathonfletcher 0:54f5be781526 238 next[(huff >> drop) + fill] = here;
jonathonfletcher 0:54f5be781526 239 } while (fill != 0);
jonathonfletcher 0:54f5be781526 240
jonathonfletcher 0:54f5be781526 241 /* backwards increment the len-bit code huff */
jonathonfletcher 0:54f5be781526 242 incr = 1U << (len - 1);
jonathonfletcher 0:54f5be781526 243 while (huff & incr)
jonathonfletcher 0:54f5be781526 244 incr >>= 1;
jonathonfletcher 0:54f5be781526 245 if (incr != 0) {
jonathonfletcher 0:54f5be781526 246 huff &= incr - 1;
jonathonfletcher 0:54f5be781526 247 huff += incr;
jonathonfletcher 0:54f5be781526 248 }
jonathonfletcher 0:54f5be781526 249 else
jonathonfletcher 0:54f5be781526 250 huff = 0;
jonathonfletcher 0:54f5be781526 251
jonathonfletcher 0:54f5be781526 252 /* go to next symbol, update count, len */
jonathonfletcher 0:54f5be781526 253 sym++;
jonathonfletcher 0:54f5be781526 254 if (--(count[len]) == 0) {
jonathonfletcher 0:54f5be781526 255 if (len == max) break;
jonathonfletcher 0:54f5be781526 256 len = lens[work[sym]];
jonathonfletcher 0:54f5be781526 257 }
jonathonfletcher 0:54f5be781526 258
jonathonfletcher 0:54f5be781526 259 /* create new sub-table if needed */
jonathonfletcher 0:54f5be781526 260 if (len > root && (huff & mask) != low) {
jonathonfletcher 0:54f5be781526 261 /* if first time, transition to sub-tables */
jonathonfletcher 0:54f5be781526 262 if (drop == 0)
jonathonfletcher 0:54f5be781526 263 drop = root;
jonathonfletcher 0:54f5be781526 264
jonathonfletcher 0:54f5be781526 265 /* increment past last table */
jonathonfletcher 0:54f5be781526 266 next += min; /* here min is 1 << curr */
jonathonfletcher 0:54f5be781526 267
jonathonfletcher 0:54f5be781526 268 /* determine length of next table */
jonathonfletcher 0:54f5be781526 269 curr = len - drop;
jonathonfletcher 0:54f5be781526 270 left = (int)(1 << curr);
jonathonfletcher 0:54f5be781526 271 while (curr + drop < max) {
jonathonfletcher 0:54f5be781526 272 left -= count[curr + drop];
jonathonfletcher 0:54f5be781526 273 if (left <= 0) break;
jonathonfletcher 0:54f5be781526 274 curr++;
jonathonfletcher 0:54f5be781526 275 left <<= 1;
jonathonfletcher 0:54f5be781526 276 }
jonathonfletcher 0:54f5be781526 277
jonathonfletcher 0:54f5be781526 278 /* check for enough space */
jonathonfletcher 0:54f5be781526 279 used += 1U << curr;
jonathonfletcher 0:54f5be781526 280 if ((type == LENS && used >= ENOUGH_LENS) ||
jonathonfletcher 0:54f5be781526 281 (type == DISTS && used >= ENOUGH_DISTS))
jonathonfletcher 0:54f5be781526 282 return 1;
jonathonfletcher 0:54f5be781526 283
jonathonfletcher 0:54f5be781526 284 /* point entry in root table to sub-table */
jonathonfletcher 0:54f5be781526 285 low = huff & mask;
jonathonfletcher 0:54f5be781526 286 (*table)[low].op = (unsigned char)curr;
jonathonfletcher 0:54f5be781526 287 (*table)[low].bits = (unsigned char)root;
jonathonfletcher 0:54f5be781526 288 (*table)[low].val = (unsigned short)(next - *table);
jonathonfletcher 0:54f5be781526 289 }
jonathonfletcher 0:54f5be781526 290 }
jonathonfletcher 0:54f5be781526 291
jonathonfletcher 0:54f5be781526 292 /* fill in remaining table entry if code is incomplete (guaranteed to have
jonathonfletcher 0:54f5be781526 293 at most one remaining entry, since if the code is incomplete, the
jonathonfletcher 0:54f5be781526 294 maximum code length that was allowed to get this far is one bit) */
jonathonfletcher 0:54f5be781526 295 if (huff != 0) {
jonathonfletcher 0:54f5be781526 296 here.op = (unsigned char)64; /* invalid code marker */
jonathonfletcher 0:54f5be781526 297 here.bits = (unsigned char)(len - drop);
jonathonfletcher 0:54f5be781526 298 here.val = (unsigned short)0;
jonathonfletcher 0:54f5be781526 299 next[huff] = here;
jonathonfletcher 0:54f5be781526 300 }
jonathonfletcher 0:54f5be781526 301
jonathonfletcher 0:54f5be781526 302 /* set return parameters */
jonathonfletcher 0:54f5be781526 303 *table += used;
jonathonfletcher 0:54f5be781526 304 *bits = root;
jonathonfletcher 0:54f5be781526 305 return 0;
jonathonfletcher 0:54f5be781526 306 }