/*---------------------------------------------------------------------------- Yet another implementation of inflate/gunzip Chris Giese http://SisAndHappy.com/ChrisGiese/ I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide. If this is not legally possible: I grant any entity the right to use this work for any purpose, without any conditions, unless such conditions are required by law. 10 Dec. 2021: Extensively redone. The new architecture makes the code cleaner, more elegant, better structured, and easier to read and understand; mainly by doing two things: - Filling the input buffer and emptying the output buffer is now done with callbacks. - Unrecoverable errors are handled with longjmp(); eliminating most code like this: if((k = (unsigned)read_le_bits(&s->inbuf, 2) + 3) < 0) return k; to pass error return values back up the call tree: // longjmp() called by read_le_bits() if exception occurs k = (unsigned)read_le_bits(&s->inbuf, 2) + 3); No more ugly state machine to make inflate() work if the input buffer runs dry or the output buffer fills up at exactly the wrong moment. Other fixes and improvements: - Now getting output file name from the .gz file; if present - Now calculating and checking CRC32 - Now checking decompressed file size against the value stored at the end of the .gz file 28 Feb. 2013: initial release To do: - If no output file name stored in the .gz file, generate a better name than "foo" - Maybe extend this code to unzip .zip files, too - Handle MTIME, CRC16 I can't find any .gz or .tgz file that uses CRC16 - The Huffman decoders in fixed_inflate() should be built only once, used as necessary, and destroyed when the program exits. You are currently building and destroying them whenever you process a block that uses fixed inflate. - Support zlib format as well as gzip format. zlib is very simple: CMF FLG optional 4-byte DICTID compressed data 4-byte Adler32 checksum CMF b7-4=CMINFO=lg2(lz77_window_size)-8 (=7 for 32Kbyte window) CMF b3-0=CM=compression method=8 for deflate FLG b7-6=FLEVEL=compression level: 0=fastest,1=fast,2=default,3=best FLG b5=DICTID is present FLG b4-0=check bits for b7-5; chosen so that read_be16(CMF:FLG) is an integer multiple of 31 DICTID=Adler32 checksum of dictionary ----------------------------------------------------------------------------*/ #if 0 #include #else typedef unsigned char uint8_t; typedef unsigned short uint16_t; typedef unsigned long uint32_t; typedef signed long int32_t; typedef int intptr_t; #endif #if defined(__GNUC__) #define INLINE __inline__ #else #define INLINE /* nothing */ #endif #if 0 #define DEBUG(X) X #else #define DEBUG(X) /* nothing */ #endif #define COUNT(X) (sizeof(X) / sizeof((X)[0])) #define ERR_UNKNOWN -1 #define ERR_OPEN_INPUT -2 #define ERR_OPEN_OUTPUT -3 #define ERR_BAD_FORMAT -4 /* file not in expected format */ #define ERR_BAD_ARG -5 /* invalid argument to function */ #define ERR_READ -6 /* EOF */ #define ERR_WRITE -7 /* disk full? */ #define ERR_BAD_DATA -8 /* invalid data in file */ #define ERR_NO_MEM -9 /* can't allocate heap memory */ #define ERR_NOT_SUPP -10 DEBUG(int g_debug = 1;) /*---------------------------------------------------------------------------- BITWISE I/O ----------------------------------------------------------------------------*/ #include /* jmp_buf, longjmp() */ #include /* NULL, memcpy() */ #include /* exit() */ #include /* NULL, putchar() */ typedef struct { /* bit buffer */ uint32_t bits; unsigned num_bits; /* byte buffer */ uint8_t *buf; unsigned alloc; /* bytes allocated at buf */ unsigned max; /* maximum value of ptr */ unsigned ptr; /* where to read/write next byte */ /* callback to read/write byte buffer */ int (*callback)(intptr_t handle, uint8_t *buf, unsigned count); intptr_t handle; /* exception handling */ jmp_buf *err; } bitbuf_t; /***************************************************************************** Like fread(). Short read is not necessarily an error so return a value < count if EOF instead of calling longjmp(b->err, ...) *****************************************************************************/ int buf_read(bitbuf_t *b, void *buf0, unsigned count) { uint8_t *buf = buf0; unsigned j, k; int i; if(b == NULL || buf0 == NULL) { DEBUG( if(g_debug) printf("buf_read(): invalid argument\n");) longjmp(*b->err, ERR_BAD_ARG); } for(j = 0; j < count; ) { if((k = b->max - b->ptr) != 0) { if(k > count) k = count - j; memcpy(&buf[j], &b->buf[b->ptr], k); j += k; b->ptr += k; } if(b->ptr >= b->max) { if((i = b->callback(b->handle, b->buf, b->ptr)) < 0) { DEBUG( if(g_debug) printf("buf_read(): error %d " "from callback\n", i);) longjmp(*b->err, i); } b->max = i; b->ptr = 0; if(i == 0) break; } } return j; } /***************************************************************************** Like fgetc(). Short read is not necessarily an error so return ERR_READ if EOF instead of calling longjmp(b->err, ...). *****************************************************************************/ INLINE int buf_getc(bitbuf_t *b) { int i; if(b->ptr >= b->max) { if((i = b->callback(b->handle, b->buf, b->ptr)) < 0) { DEBUG( if(g_debug) printf("buf_getc(): error %d " "from callback\n", i);) longjmp(*b->err, i); } else if(i == 0) return ERR_READ; b->max = i; b->ptr = 0; } return b->buf[b->ptr++]; } /***************************************************************************** Like fputc(). Returns ERR_WRITE if write does not complete; calls longjmp(b->err, ...) if unrecoverable error from callback. *****************************************************************************/ INLINE int buf_putc(bitbuf_t *b, int c) { int i; if(b->ptr >= b->max) { if((i = b->callback(b->handle, b->buf, b->ptr)) < 0) { DEBUG( if(g_debug) printf("buf_putc(): error %d " "from callback\n", i);) longjmp(*b->err, i); } // xxx - use longjmp() here? unrecoverable error? else if(i != b->ptr) return ERR_WRITE; b->max = b->alloc; b->ptr = 0; } b->buf[b->ptr++] = c; return 0; } /****************************************************************************/ #define dump_bits(B,C) \ { \ uint32_t j; \ \ for(j = 1L << ((C) - 1); j != 0; j >>= 1) \ putchar((j & (B)) ? '1' : '0'); \ } /***************************************************************************** Advances the bit buffer by 'C' bits. *****************************************************************************/ #define consume_le_bits(B, C) \ { \ (B)->bits >>= (C); \ (B)->num_bits -= (C); \ } /****************************************************************************/ #define consume_be_bits(B, C) (B)->num_bits -= (C) /***************************************************************************** Reads and returns a 'num_bits'-bits value from the bit buffer. The bit buffer will be (re)filled from the byte buffer if necessary. The byte buffer will be (re)filled using b->callback() if necessary. The bit buffer is not advanced (peek; not read). Short read is not necessarily an error so return ERR_READ if EOF instead of calling longjmp(b->err, ...). *****************************************************************************/ INLINE int32_t peek_le_bits(bitbuf_t *b, unsigned num_bits) { uint32_t j, mask; int i; while(b->num_bits < num_bits) { if(b->ptr >= b->max) { if((i = b->callback(b->handle, b->buf, b->ptr)) < 0) { DEBUG( if(g_debug) printf("peek_le_bits(): error %d " "from callback\n", i);) longjmp(*b->err, i); } else if(i == 0) return ERR_READ; b->max = i; b->ptr = 0; } j = b->buf[b->ptr]; b->ptr++; /* write incoming bytes to MSB of b->bits */ j <<= b->num_bits; b->bits |= j; b->num_bits += 8; } /* read outgoing value from LSB of b->bits */ mask = (1L << num_bits) - 1; return b->bits & mask; } /****************************************************************************/ INLINE int32_t peek_be_bits(bitbuf_t *b, unsigned num_bits) { uint32_t mask, rv; unsigned j; int i; while(b->num_bits < num_bits) { if(b->ptr >= b->max) { if((i = b->callback(b->handle, b->buf, b->ptr)) < 0) { DEBUG( if(g_debug) printf("peek_be_bits(): error %d " "from callback\n", i);) longjmp(*b->err, i); } else if(i == 0) return ERR_READ; b->max = i; b->ptr = 0; } j = b->buf[b->ptr]; b->ptr++; /* read incoming bytes to LSB of b->bits */ b->bits <<= 8; b->bits |= j; b->num_bits += 8; } /* read incoming value from MSB of b->bits */ mask = (1L << num_bits) - 1; rv = b->bits; rv >>= (b->num_bits - num_bits); return (rv & mask); } /***************************************************************************** Same as peek_be_bits() with two exceptions: - The bit buffer is advanced after the value is read from it - Uses longjmp to throw an exception if an error occurs *****************************************************************************/ INLINE int32_t read_le_bits(bitbuf_t *b, unsigned num_bits) { int32_t rv; if((rv = peek_le_bits(b, num_bits)) >= 0) consume_le_bits(b, num_bits); return rv; } /****************************************************************************/ INLINE int32_t read_be_bits(bitbuf_t *b, unsigned num_bits) { int32_t rv; if((rv = peek_be_bits(b, num_bits)) >= 0) consume_be_bits(b, num_bits); return rv; } /*---------------------------------------------------------------------------- HUFFMAN DECODE ----------------------------------------------------------------------------*/ #include /* malloc(), free() */ #include /* memset() */ #include /* printf() */ /* a fast (O(1); constant-time), array-based decoder will be used for Huffman codes that are of width FAST_BITS or narrower */ #define FAST_BITS 8 #define FAST_TABLE_SIZE (1 << FAST_BITS) /* decoder returns a value of this type */ typedef int huff_val_t; typedef struct { uint8_t code_wd; huff_val_t val; } huff_code_t; /* node used in slow (O(lg(N)), tree-based Huffman decoder */ typedef struct _huff_node { struct _huff_node *child0, *child1; huff_val_t val; } huff_node_t; typedef struct { /* number of unique Huffman codes (=number of unique uncompressed values) */ unsigned num_codes; /* number of allocated elements in 'tree' */ unsigned num_nodes; /* number of used elements in 'tree' */ unsigned used_nodes; /* slow (O(lg(N))) decoder tree */ huff_node_t *tree; /* fast (O(1)) decoder array; for narrow Huffman codes */ huff_code_t array[FAST_TABLE_SIZE]; unsigned big_endian : 1; } huffdec_t; /****************************************************************************/ static void destroy_huffdec(huffdec_t *h) { if(h->tree != NULL) free(h->tree); /* zero the struct to cause an error or segfault if it's referenced after this function is called */ memset(h, 0, sizeof(huffdec_t)); free(h); } /***************************************************************************** Adds one leaf to slow Huffman decoder tree h->tree. The leaf has value 'val' and Huffman code 'code' which is 'code_wd' bits wide. Returns 0 if success, <0 if error. *****************************************************************************/ static int add_node_to_decoder_tree(huffdec_t *h, uint32_t code, unsigned code_wd, huff_val_t val) { huff_node_t *n; uint32_t mask; n = h->tree; /* this is independent of bit order */ mask = 1L << (code_wd - 1); for(; code_wd != 0; code_wd--) { if(mask & code) { if(n->child1 == NULL) { if(h->used_nodes >= h->num_nodes) { DEBUG( if(g_debug) printf("add_node_to_" "decoder_tree(): " "invalid data\n");) return ERR_BAD_DATA; } n->child1 = &h->tree[h->used_nodes]; h->used_nodes++; } n = n->child1; } else { if(n->child0 == NULL) { if(h->used_nodes >= h->num_nodes) { DEBUG( if(g_debug) printf("add_node_to_" "decoder_tree(): " "invalid data\n");) return ERR_BAD_DATA; } n->child0 = &h->tree[h->used_nodes]; h->used_nodes++; } n = n->child0; } mask >>= 1; } n->val = val; return 0; } /***************************************************************************** Permutes the bits in 'code' end-for-end. This is needed for fast decode of little endian Huffman (e.g. deflate compression). *****************************************************************************/ static uint32_t reverse_bits(uint32_t code, unsigned code_wd) { uint32_t rv, in_mask, out_mask; rv = 0; in_mask = 1; out_mask = 1L << (code_wd - 1); for(; code_wd != 0; code_wd--) { if(code & in_mask) rv |= out_mask; in_mask <<= 1; out_mask >>= 1; } return rv; } /***************************************************************************** Adds entries to fast Huffman decoder array h->array. Each entry has value 'val' and Huffman code 'code' which is 'code_wd' bits wide. Returns 0 if success, <0 if error. *****************************************************************************/ static int add_node_to_decoder_array(huffdec_t *h, uint32_t code, unsigned code_wd, huff_val_t val) { unsigned delta_wd, reps, j, k; huff_code_t *array; if(code_wd > FAST_BITS) return ERR_BAD_ARG; /* replicate code j times, where j=2^(FAST_BITS-code_wd) */ delta_wd = FAST_BITS - code_wd; reps = 1 << delta_wd; /* ...starting with entry j=code<<(FAST_BITS-code_wd) */ j = (unsigned)(code << delta_wd); array = h->array; for(; reps != 0; reps--) { if(h->big_endian) k = j; else k = (unsigned)reverse_bits(j, FAST_BITS); if(array[k].code_wd != 0) return ERR_UNKNOWN; array[k].val = val; array[k].code_wd = code_wd; j++; } return 0; } /***************************************************************************** Adds an entry to both the fast, array-based Huffman decoder array h->array and the slow, tree-based Huffman decoder s->tree. Entry has value 'val' and Huffman code 'code' which is 'code_wd' bits wide. Returns 0 if success, <0 if error. Code width is limited to 25 bits because you can't read another byte into the bit buffer when it's that full: A BCDEFGHI JKLMNOPQ RSTUVWXY |33222222|22221111|111111 | | |10987654|32109876|54321098|76543210| *****************************************************************************/ static int add_node_to_huffdec(huffdec_t *h, uint32_t code, unsigned code_wd, huff_val_t val) { int i; if(h == NULL || code_wd > 25 || code > 0x1FFFFFFuL) return ERR_BAD_ARG; DEBUG( if(g_debug) { printf("Adding decode node for: "); dump_bits(code, code_wd); printf(" -> %d\n", val); }) /* add node to slow Huffman decompression tree */ if((i = add_node_to_decoder_tree(h, code, code_wd, val)) < 0) return i; /* for narrow codes: add node to fast Huffman decompression table */ if(code_wd <= FAST_BITS) return add_node_to_decoder_array(h, code, code_wd, val); return 0; } /***************************************************************************** Builds Huffman decoder from the code_width:value pairs in 'array'. The number of pairs is 'num_codes'. Returns 0 if success, <0 if error. *****************************************************************************/ int create_canonical_huffdec(huffdec_t **h_ptr, huff_code_t *array, unsigned num_codes, int big_endian) { unsigned c, j, width, prev_wd; huffdec_t *h; int err; if(h_ptr == NULL || array == NULL) return ERR_BAD_ARG; if((h = calloc(1, sizeof(huffdec_t))) == NULL) return ERR_NO_MEM; h->num_codes = num_codes; h->big_endian = big_endian; h->used_nodes = 1; /* zero out the fast Huffman decoder array (already done by calloc) memset(s->array, 0, sizeof(s->array)); find maximum Huffman code width */ width = 0; for(j = 0; j < num_codes; j++) { if(width < array[j].code_wd) width = array[j].code_wd; } /* allocate memory for slow Huffman decoder tree */ h->num_nodes = num_codes * 2; if((h->tree = calloc(sizeof(huff_node_t), h->num_nodes)) == NULL) { free(h); return ERR_NO_MEM; } /* assign codes, from narrowest to widest, starting with c=0 ("canonical" Huffman codes) */ c = 0; prev_wd = 0; /* initialize both the table and tree decoders */ for(j = 0; j < h->num_codes; j++) { /* fetch code width; check if it's changed */ if((width = array[j].code_wd) == 0) continue; /* double the code value each time the code width increases by 1 */ if(width != prev_wd) { c <<= width - prev_wd; prev_wd = width; } if((err = add_node_to_huffdec(h, /*code=*/c, array[j].code_wd, array[j].val)) < 0) { destroy_huffdec(h); return err; } /* increment Huffman code */ c++; } (*h_ptr) = h; return 0; } /***************************************************************************** Slow (O(lg(N))), binary-tree-based Huffman decoder for wide codes. This routine is called by the fast, array-based Huffman decoders if the code is too wide for them to handle. Returns if success, else uses longjmp to signal an error. NOTE: If you modify this code to return to the caller if the bit buffer is empty (instead of calling fread() on buf->f to refill it)(zlib does this), note that local variable 'huff_node_t *n' represents state that may be lost. *****************************************************************************/ static huff_val_t read_huffed_slow(huffdec_t *h, bitbuf_t *b) { huff_node_t *n; unsigned j; n = h->tree; do { j = h->big_endian ? (unsigned)read_be_bits(b, 1) : (unsigned)read_le_bits(b, 1); DEBUG( if(g_debug) putchar(j ? '1' : '0');) if((j && n->child1 == NULL) || (!j && n->child0 == NULL)) { DEBUG( if(g_debug) printf("read_huffed_slow(): invalid data\n");) longjmp(*b->err, ERR_BAD_DATA); } n = j ? n->child1 : n->child0; } while(n->child0 != NULL || n->child1 != NULL); DEBUG( if(g_debug) printf(" -> 0x%02X\n", n->val);) return n->val; } /***************************************************************************** Reads little-endian Huffman-coded value from 'b', decodes it with Huffman decoder 'h'. Returns if success, else uses longjmp to signal an error. *****************************************************************************/ static INLINE huff_val_t read_huffed_le(huffdec_t *h, bitbuf_t *b) { huff_code_t *c; int i; if((i = (int)peek_le_bits(b, FAST_BITS)) >= 0 && (c = &h->array[i])->code_wd != 0) { DEBUG( if(g_debug) { dump_bits(reverse_bits(i, c->code_wd), c->code_wd); printf(" -> 0x%02X\n", c->val); }) consume_le_bits(b, c->code_wd); return c->val; } return read_huffed_slow(h, b); } /****************************************************************************/ static INLINE huff_val_t read_huffed_be(huffdec_t *h, bitbuf_t *b) { huff_code_t *c; int i; if((i = (int)peek_be_bits(b, FAST_BITS)) >= 0 && (c = &h->array[i])->code_wd != 0) { DEBUG( if(g_debug) { dump_bits(i, c->code_wd); printf(" -> 0x%02X\n", c->val); }) consume_be_bits(b, c->code_wd); return c->val; } return read_huffed_slow(h, b); } /*---------------------------------------------------------------------------- INFLATE DECOMPRESSION Amount of input required: function bits description -------- ------- ------------------------------------- (block 1 last-block flag header) 2 block type (stored, dynamic, fixed) do_stored() 32 16-bit length of stored block, and two's complement N*8 N=length of stored block fixed_inflate() (setup; then call do_inflate()) 0 (this function requires no input data for setup) dynamic_inflate() (setup; then call do_inflate()) 14 Huffman decoder sizes (A, B, and C) A=4-bit number of code-widths=4-19 B=5-bit number of length/literal values=257-288 C=5-bit number of distance values=1-32 3*A code-widths for the code-width Huffman decoder for(j = 0; j < B+C; j++) { 1-15 variable-length Huffman-compressed value 0,2,3,7 (OPTIONAL) repeat count for previous or zero value } do_inflate() do { 1-15 variable-length Huffman-compressed literal/length value (the following are OPTIONAL) 0-5 extra bits for string length 1-15 variable-length Huffman-compressed distance value 0-13 extra bits for string distance } while(decoded_byte != 256) ----------------------------------------------------------------------------*/ #include /* malloc(), free(), qsort() */ #include /* NULL, memchr() */ #include /* printf() */ #include /* O_RDONLY, O_BINARY, etc. */ #include /* open */ typedef struct { /* input & output buffers */ bitbuf_t inbuf, outbuf; /* Huffman decoders for literal bytes/string lengths and string distances */ uint16_t ll_count; uint8_t dist_count; huffdec_t *ll_decoder, *dist_decoder; /* LZ77 (LZSS) string buffer */ uint16_t lz77_in, lz77_out, lz77_mask, lz77_len; uint8_t *lz77_buf; /* exception handling */ jmp_buf err; } inflate_t; /****************************************************************************/ static uint16_t read_le16(const void *buf0) { const uint8_t *buf = buf0; uint16_t rv; rv = buf[1]; /* MSB */ rv <<= 8; rv |= buf[0]; /* LSB */ return rv; } /****************************************************************************/ static void do_stored(inflate_t *s) { uint8_t buf[4]; unsigned j; int i; DEBUG( if(g_debug) printf("do_stored():\n");) /* flush input bit buffer */ s->inbuf.num_bits &= ~7; if((i = buf_read(&s->inbuf, buf, 4)) < 0) { DEBUG( if(g_debug) printf("do_stored(): unknown error from buf_read()\n");) longjmp(s->err, ERR_UNKNOWN); } else if(i != 4) { DEBUG( if(g_debug) printf("do_stored(): error reading input\n");) longjmp(s->err, ERR_READ); } /* BUT IT WORKED WITH TURBO C... if((j = read_le16(buf)) != ~read_le16(&buf[2])) */ if((j = read_le16(buf)) != (~read_le16(&buf[2]) & 0xFFFF)) { DEBUG( if(g_debug) printf("do_stored(): invalid data\n");) longjmp(s->err, ERR_BAD_DATA); } DEBUG( if(g_debug) printf("\tdo_stored(): copying %u bytes...\n", j);) for(; j != 0; j--) { if((i = buf_getc(&s->inbuf)) < 0) { DEBUG( if(g_debug) printf("do_stored(): error reading input\n");) longjmp(s->err, ERR_READ); } s->lz77_buf[s->lz77_in] = i; s->lz77_in = (s->lz77_in + 1) & s->lz77_mask; if((i = buf_putc(&s->outbuf, i)) < 0) { DEBUG( if(g_debug) printf("do_stored(): error writing output\n");) longjmp(s->err, ERR_WRITE); } } DEBUG( if(g_debug) printf("\tdo_stored(): done\n");) } /****************************************************************************/ static void do_inflate(inflate_t *s) { /* tables from [Page 11] of RFC1951 */ static const uint8_t num_length_extra_bits[29] = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 }; static const uint16_t length_start[29] = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 }; static const uint8_t num_dist_extra_bits[30] = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 }; static const uint16_t dist_start[30] = { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 }; /**/ unsigned j; DEBUG( if(g_debug) printf("do_inflate():\n");) while(1) { /* Huffman-coded value */ j = read_huffed_le(s->ll_decoder, &s->inbuf); /* code<256: literal value */ if(j < 256) { s->lz77_buf[s->lz77_in] = j; s->lz77_in = (s->lz77_in + 1) & s->lz77_mask; if(buf_putc(&s->outbuf, j) < 0) { DEBUG( if(g_debug) printf("do_inflate(): error " "writing output\n");) longjmp(s->err, ERR_WRITE); } } /* code=256: end of compressed data */ else if(j == 256) { DEBUG( if(g_debug) printf("\tdo_inflate(): done\n");) return; } /* code>256: string length... */ else if(j < s->ll_count) { j -= 257; /* ...plus string length "extra" bits */ s->lz77_len = length_start[j] + (unsigned)read_le_bits(&s->inbuf, num_length_extra_bits[j]); /* Huffman-coded string distance... */ if((j = (unsigned)read_huffed_le(s->dist_decoder, &s->inbuf)) > 29) { DEBUG( if(g_debug) printf("do_inflate(): " "invalid data\n");) longjmp(s->err, ERR_BAD_DATA); } /* ...plus string distance "extra" bits */ j = dist_start[j] + (unsigned)read_le_bits(&s->inbuf, num_dist_extra_bits[j]); DEBUG( if(g_debug) printf("do_inflate: repeated string; " "len=%u, dist=%u\n", s->lz77_len, j);) s->lz77_out = (s->lz77_in - j) & s->lz77_mask; /* copy repeated string from buffer to output (and back to the buffer) -- this is basically LZ77/LZSS compression */ for(j = 0; j < s->lz77_len; j++) { uint8_t c; c = s->lz77_buf[s->lz77_out]; s->lz77_out = (s->lz77_out + 1) & s->lz77_mask; s->lz77_buf[s->lz77_in] = c; s->lz77_in = (s->lz77_in + 1) & s->lz77_mask; if(buf_putc(&s->outbuf, c) < 0) { DEBUG( if(g_debug) printf("do_inflate(): error " "writing output\n");) longjmp(s->err, ERR_WRITE); } } s->lz77_len = 0; } } } /***************************************************************************** huff_code_t comparison function for qsort(); used before calling create_canonical_huffdec() *****************************************************************************/ static int code_cmp(const void *left0, const void *right0) { const huff_code_t *left = left0; const huff_code_t *right = right0; /* sort first (primary key) on huff_code_t->width, ascending order */ if(left->code_wd < right->code_wd) return -1; if(left->code_wd > right->code_wd) return +1; /* sort second (secondary key) on huff_code_t->val, ascending order */ if(left->val < right->val) return -1; if(left->val > right->val) return +1; return 0; } /****************************************************************************/ static void fixed_inflate(inflate_t *s) { huff_code_t array[288]; unsigned num_codes, j; int i; DEBUG( if(g_debug) printf("fixed_inflate():\n");) memset(array, 0, sizeof(array)); /* fixed code widths from section 3.2.6 of RFC-1951.TXT */ num_codes = 288; for(j = 0; j < 144; j++) { array[j].val = j; array[j].code_wd = 8; } for(; j < 256; j++) { array[j].val = j; array[j].code_wd = 9; } for(; j < 280; j++) { array[j].val = j; array[j].code_wd = 7; } for(; j < num_codes; j++) { array[j].val = j; array[j].code_wd = 8; } s->ll_count = 288; s->dist_count = 30; DEBUG( if(g_debug) printf("\tfixed_inflate(): building length/literal " "Huffman decoder...\n");) qsort(array, num_codes, sizeof(huff_code_t), code_cmp); if((i = create_canonical_huffdec(&s->ll_decoder, array, num_codes, 0)) != 0) { DEBUG( if(g_debug) printf("fixed_inflate(): error %d from " "create_canonical_huffdec()\n", i);) longjmp(s->err, i); } num_codes = 30; for(j = 0; j < num_codes; j++) { array[j].val = j; array[j].code_wd = 5; } DEBUG( if(g_debug) printf("fixed_inflate(): building distance " "Huffman decoder...\n");) qsort(array, num_codes, sizeof(huff_code_t), code_cmp); if((i = create_canonical_huffdec(&s->dist_decoder, array, num_codes, 0)) != 0) { DEBUG( if(g_debug) printf("fixed_inflate(): error %d from " "create_canonical_huffdec()\n", i);) destroy_huffdec(s->ll_decoder); longjmp(s->err, i); } DEBUG( if(g_debug) printf("\tfixed_inflate(): calling do_inflate()\n");) do_inflate(s); } /****************************************************************************/ static void dynamic_inflate(inflate_t *s) { /* PKZIP code order obfuscation? Or what? */ static const uint8_t b_order[19] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; /**/ huffdec_t *code_wd_decoder; huff_code_t array[320]; /* 320 = max(288 + 32, 19) */ uint8_t code_wd_count; unsigned j, k, m; int i; j = (unsigned)read_le_bits(&s->inbuf, 14); s->ll_count = (j & 0x1F) + 257; /* 257-288 entries */ j >>= 5; s->dist_count = (j & 0x1F) + 1; /* 1-32 */ j >>= 5; code_wd_count = (j & 0x0F) + 4; /* 4-19 */ DEBUG( if(g_debug) { printf("dynamic_inflate(): s->ll_count=%u, s->dist_count=%u, " "code_wd_count=%u\n", s->ll_count, s->dist_count, code_wd_count); printf("\tdynamic_inflate(): building " "code-width Huffman decoder...\n"); }) /* build code-width Huffman decoder */ for(j = 0; j < code_wd_count; j++) { array[j].val = j; array[b_order[j]].code_wd = (unsigned)read_le_bits(&s->inbuf, 3); } for(; j < 19; j++) { array[j].val = j; array[b_order[j]].code_wd = 0; } qsort(array, 19, sizeof(huff_code_t), code_cmp); if((i = create_canonical_huffdec(&code_wd_decoder, array, 19, 0)) != 0) { DEBUG( if(g_debug) printf("dynamic_inflate(): error %d from " "create_canonical_huffdec()\n", i);) longjmp(s->err, i); } /* get code widths for both length/literal and distance Huffman decoders */ DEBUG( if(g_debug) printf("\tdynamic_inflate(): getting code widths " "for Huffman decoders...\n");) for(j = 0; j < s->ll_count + s->dist_count; ) { DEBUG( if(g_debug) printf("%3u: ", j);) k = read_huffed_le(code_wd_decoder, &s->inbuf); /* code width<16: literal code width values */ if(k < 16) { array[j].val = j % s->ll_count; array[j].code_wd = k; j++; } /* code width=16: store the previous code width 3-6 times */ else if(k == 16) { m = array[j - 1].code_wd; k = (unsigned)read_le_bits(&s->inbuf, 2) + 3; goto STORE; } /* code width=17: store 3-10 zero values */ else if(k == 17) { m = 0; k = (unsigned)read_le_bits(&s->inbuf, 3) + 3; goto STORE; } /* code width=18: store 11-138 zero values */ else if(k == 18) { m = 0; k = (unsigned)read_le_bits(&s->inbuf, 7) + 11; STORE: for(; k != 0; k--) { array[j].val = j % s->ll_count; array[j].code_wd = m; DEBUG( if(g_debug) printf("\t%3u: -> 0x%02X\n", j, m);) j++; } } else { DEBUG( if(g_debug) printf("dynamic_inflate(): invalid " "code width %u\n", k);) longjmp(s->err, ERR_BAD_DATA); } } /* create Huffman decoder for literal bytes/string length values */ DEBUG( if(g_debug) printf("\tdynamic_inflate(): building literal/" "string length Huffman decoder...\n");) qsort(&array[0], s->ll_count, sizeof(huff_code_t), code_cmp); if((i = create_canonical_huffdec(&s->ll_decoder, array, s->ll_count, 0)) != 0) { DEBUG( if(g_debug) printf("dynamic_inflate(): error %d from " "create_canonical_huffdec()\n", i);) longjmp(s->err, i); } /* create Huffman decoder for string distance values */ DEBUG( if(g_debug) printf("\tdynamic_inflate(): building " "string distance Huffman decoder...\n");) qsort(&array[s->ll_count], s->dist_count, sizeof(huff_code_t), code_cmp); if((i = create_canonical_huffdec(&s->dist_decoder, &array[s->ll_count], s->dist_count, 0)) != 0) { DEBUG( if(g_debug) printf("dynamic_inflate(): error %d from " "create_canonical_huffdec()\n", i);) longjmp(s->err, i); } /* once s->ll_decoder and s->dist_decoder are constructed, we no longer need code_wd_decoder */ destroy_huffdec(code_wd_decoder); DEBUG( if(g_debug) printf("\tdynamic_inflate(): calling do_inflate()\n");) do_inflate(s); } /****************************************************************************/ void inflate(inflate_t *s, unsigned lz77_buf_size) { char last_block = 0; unsigned j; if((s->lz77_buf = malloc(lz77_buf_size)) == NULL) longjmp(s->err, ERR_NO_MEM); s->lz77_mask = 32768u - 1; while(!last_block) { /* destroy previous Huffman decoders; if any */ if(s->ll_decoder != NULL) { destroy_huffdec(s->ll_decoder); s->ll_decoder = NULL; } if(s->dist_decoder != NULL) { destroy_huffdec(s->dist_decoder); s->dist_decoder = NULL; } /* read 1-bit "last block" flag (BFINAL) and 2-bit block type (BTYPE) */ j = (unsigned)read_le_bits(&s->inbuf, 3); last_block = j & 1; j >>= 1; DEBUG( if(g_debug) printf("last_block=%u, block type=%u\n", (unsigned)last_block, j);) /* inflate type 0 = stored block */ if(j == 0) do_stored(s); /* inflate type 1 = deflated block using fixed compression tables (defined in flate spec) */ else if(j == 1) fixed_inflate(s); /* inflate type 2 = deflated block using dynamic compression tables (stored in flate stream) */ else if(j == 2) dynamic_inflate(s); else { DEBUG( if(g_debug) printf("Invalid deflate block type 3\n");) longjmp(s->err, ERR_BAD_DATA); } } } /****************************************************************************/ void destroy_inflate(inflate_t *state) { if(state->ll_decoder != NULL) destroy_huffdec(state->ll_decoder); if(state->dist_decoder != NULL) destroy_huffdec(state->dist_decoder); if(state->lz77_buf != NULL) free(state->lz77_buf); memset(state, 0, sizeof(inflate_t)); } /*---------------------------------------------------------------------------- GZIP FILE DECOMPRESSION ----------------------------------------------------------------------------*/ #define crc32_byte(C) \ { \ uint32_t c = g_crc32 ^ 0xFFFFFFFFL; \ \ c = g_crc32_table[(unsigned)(c ^ (C)) & 0xFF] \ ^ (c >> 8); \ g_crc32 = c ^ 0xFFFFFFFFL; \ } static uint32_t g_crc32; static uint32_t g_crc32_table[256]; /****************************************************************************/ static void init_crc32(void) { unsigned j, k; uint32_t c; for(j = 0; j < COUNT(g_crc32_table); j++) { c = j; for(k = 0; k < 8; k++) { if(c & 1) { c >>= 1; c ^= 0xEDB88320L; } else c >>= 1; } g_crc32_table[j] = c; } } /****************************************************************************/ static void crc32_bytes(uint8_t *buf, unsigned count) { uint32_t c = g_crc32 ^ 0xFFFFFFFFL; unsigned j; for(j = 0; j < count; j++) c = g_crc32_table[(unsigned)(c ^ buf[j]) & 0xFF] ^ (c >> 8); g_crc32 = c ^ 0xFFFFFFFFL; } /****************************************************************************/ static int input_callback(intptr_t handle, uint8_t *buf, unsigned count) { return read(handle, buf, count); } /****************************************************************************/ static int output_callback(intptr_t handle, uint8_t *buf, unsigned count) { crc32_bytes(buf, count); return write(handle, buf, count); } /****************************************************************************/ static uint32_t read_le32(const void *buf0) { const uint8_t *buf = buf0; uint32_t rv; rv = buf[3]; /* MSB */ rv <<= 8; rv |= buf[2]; rv <<= 8; rv |= buf[1]; rv <<= 8; rv |= buf[0]; /* LSB */ return rv; } /****************************************************************************/ int main(int arg_c, char *arg_v[]) { static const char *err_msg[] = { NULL, "Unknown error", "Can't open input file", "Can't open output file", "File not in expected format", "Invalid argument to function (software error?)", "Read failed (unexpected end of file)", "Write failed (disk full?)", "Invalid data", "Out of memory", "Data/file has unsupported option or feature" }; /**/ uint8_t buf[10], ibuf[256], obuf[256]; // xxx - if no output file name stored in the .gz file, // create output file name from input file name char out_name[256] = "foo"; uint32_t crc, ssize, asize; inflate_t state; unsigned j; int i; if(arg_c != 2) { printf("Usage: cgunzip file.gz\n\n"); return 1; } /* initialize */ memset(&state, 0, sizeof(state)); state.inbuf.buf = ibuf; state.inbuf.alloc = state.inbuf.max = state.inbuf.ptr = sizeof(ibuf); state.inbuf.callback = input_callback; state.inbuf.err = &state.err; state.outbuf.buf = obuf; state.outbuf.alloc = state.outbuf.max = sizeof(obuf); state.outbuf.callback = output_callback; state.outbuf.err = &state.err; /* set up error trapping */ if((i = setjmp(state.err)) != 0) { printf("Error %d\n", i); i = -i; if(i < COUNT(err_msg)) printf("\t%s\n", err_msg[i]); printf("File offset into infile '%s': %lu\n", arg_v[1], tell(state.inbuf.handle)); printf("Input buffer: ptr=%u, count=%u\n", state.inbuf.ptr, state.inbuf.max); if(state.outbuf.handle != 0) close(state.outbuf.handle); // xxx - this won't close state.inbuf.handle if it's stdin -- problem? if(state.inbuf.handle != 0) close(state.inbuf.handle); /* destroy_inflate() zeroes the entire inflate_t object so do this after the calls to close() */ destroy_inflate(&state); remove(out_name); return 2; } init_crc32(); /* open input file, validate */ if((state.inbuf.handle = open(arg_v[1], O_RDONLY | O_BINARY)) == -1) longjmp(state.err, ERR_OPEN_INPUT); /* +---+---+---+---+---+---+---+---+---+---+ |ID1|ID2|CM |FLG| MTIME |XFL|OS | (more-->) +---+---+---+---+---+---+---+---+---+---+ */ if(buf_read(&state.inbuf, buf, 10) != 10 || buf[0] != 0x1F || buf[1] != 0x8B) longjmp(state.err, ERR_BAD_FORMAT); if(buf[2] != 8) longjmp(state.err, ERR_NOT_SUPP); crc32_bytes(buf, 10); /* process flags */ if(buf[3] & 0x04) /* FEXTRA */ { if(buf_read(&state.inbuf, ibuf, 2) != 2) longjmp(state.err, ERR_READ); crc32_bytes(ibuf, 2); for(j = read_le16(ibuf); j != 0; j--) { if((i = buf_getc(&state.inbuf)) < 0) longjmp(state.err, i); crc32_byte(i); } } if(buf[3] & 0x08) /* FNAME */ { for(j = 0; j + 1 < sizeof(out_name); j++) { if((i = buf_getc(&state.inbuf)) < 0) longjmp(state.err, i); else if(i == 0) break; out_name[j] = i; crc32_byte(i); } out_name[j] = '\0'; } if(buf[3] & 0x10) /* FCOMMENT */ { do { if((i = buf_getc(&state.inbuf)) < 0) longjmp(state.err, i); crc32_byte(i); } while(i != 0); } if(buf[3] & 0x02) /* FHCRC */ { if(buf_read(&state.inbuf, ibuf, 2) != 2) longjmp(state.err, ERR_READ); crc = read_le16(ibuf); // xxx - UNTESTED. I have yet to see a .gz file that uses this: if(crc != (uint16_t)g_crc32) { printf("CRC16 error: calculated value=0x%X, " "value from file=0x%lX\n", (uint16_t)g_crc32, crc); longjmp(state.err, ERR_BAD_DATA); } } if((buf[3] & 0xE0) != 0) longjmp(state.err, ERR_NOT_SUPP); // xxx - buf[4-7] is mtime /* Open output file. Don't forget the permissions value here; like I did. */ if((state.outbuf.handle = open(out_name, /* O_WRONLY | O_BINARY | O_CREAT | O_TRUNC)) == -1) */ O_WRONLY | O_BINARY | O_CREAT | O_TRUNC, 0644)) == -1) longjmp(state.err, ERR_OPEN_OUTPUT); /* do inflate */ g_crc32 = 0; inflate(&state, 32768u); /* flush output buffer */ if(state.outbuf.ptr != 0) { crc32_bytes(state.outbuf.buf, state.outbuf.ptr); write(state.outbuf.handle, state.outbuf.buf, state.outbuf.ptr); } /* Now we want 8 bytes; 4 for the CRC32 and 4 for the uncompressed size. Align the bit buffer to a byte offset... */ if(state.inbuf.num_bits & 7) (void)read_le_bits(&state.inbuf, state.inbuf.num_bits & 7); /* ...then retreive whole bytes from it; if any... */ for(j = 0; j < 8 && state.inbuf.num_bits >= 8; j++) buf[j] = read_le_bits(&state.inbuf, 8); /* ...and read whatever more bytes you need from the byte buffer & input file */ if(j < 8) { if(buf_read(&state.inbuf, &buf[j], 8 - j) != 8 - j) longjmp(state.err, ERR_READ); } crc = read_le32(buf); ssize = read_le32(&buf[4]); asize = tell(state.outbuf.handle); if(ssize != asize) printf("Warning: actual decompressed file size (%lu) " "!= stored size (%lu)\n", asize, ssize); DEBUG( else printf("Decompressed file size=stored size=%lu\n", asize);) if(crc != g_crc32) printf("Warning: calculated CRC32 (0x%lX) != stored " "CRC32 (0x%lX)\n", g_crc32, crc); DEBUG( else printf("Calculated CRC32=CRC from file=0x%lX\n", g_crc32);) /* cleanup */ close(state.outbuf.handle); close(state.inbuf.handle); destroy_inflate(&state); return 0; }