1 /* tinfl.c v1.16 beta - public domain inflate with zlib header parsing/adler32 checking (inflate-only subset of miniz.c)
2 See "unlicense" statement at the end of this file.
3 Rich Geldreich <richgel99@gmail.com>, last updated Oct. 19, 2013
4 Implements the decompression side of RFC 1950: http://www.ietf.org/rfc/rfc1950.txt and RFC 1951: http://www.ietf.org/rfc/rfc1951.txt
5
6 There entire decompressor coroutine function is implemented in a *single* C function: tinfl_decompress().
7 All other C functions in this file are optional high-level usage examples.
8 */
9 #ifndef TINFL_HEADER_INCLUDED
10 #define TINFL_HEADER_INCLUDED
11
12 #include <stdlib.h>
13
14 typedef unsigned char mz_uint8;
15 typedef signed short mz_int16;
16 typedef unsigned short mz_uint16;
17 typedef unsigned int mz_uint32;
18 typedef unsigned int mz_uint;
19 typedef unsigned long long mz_uint64;
20
21 #if defined(_M_IX86) || defined(_M_X64)
22 // Set MINIZ_USE_UNALIGNED_LOADS_AND_STORES to 1 if integer loads and stores to unaligned addresses are acceptable on the target platform (slightly faster).
23 #define MINIZ_USE_UNALIGNED_LOADS_AND_STORES 1
24 // Set MINIZ_LITTLE_ENDIAN to 1 if the processor is little endian.
25 #define MINIZ_LITTLE_ENDIAN 1
26 #endif
27
28 #if defined(_WIN64) || defined(__MINGW64__) || defined(_LP64) || defined(__LP64__)
29 // Set MINIZ_HAS_64BIT_REGISTERS to 1 if the processor has 64-bit general purpose registers (enables 64-bit bitbuffer in inflator)
30 #define MINIZ_HAS_64BIT_REGISTERS 1
31 #endif
32
33 // Works around MSVC's spammy "warning C4127: conditional expression is constant" message.
34 #ifdef _MSC_VER
35 #define MZ_MACRO_END while (0, 0)
36 #else
37 #define MZ_MACRO_END while (0)
38 #endif
39
40 // Decompression flags used by tinfl_decompress().
41 // TINFL_FLAG_PARSE_ZLIB_HEADER: If set, the input has a valid zlib header and ends with an adler32 checksum (it's a valid zlib stream). Otherwise, the input is a raw deflate stream.
42 // TINFL_FLAG_HAS_MORE_INPUT: If set, there are more input bytes available beyond the end of the supplied input buffer. If clear, the input buffer contains all remaining input.
43 // TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF: If set, the output buffer is large enough to hold the entire decompressed stream. If clear, the output buffer is at least the size of the dictionary (typically 32KB).
44 // TINFL_FLAG_COMPUTE_ADLER32: Force adler-32 checksum computation of the decompressed bytes.
45 enum
46 {
47 TINFL_FLAG_PARSE_ZLIB_HEADER = 1,
48 TINFL_FLAG_HAS_MORE_INPUT = 2,
49 TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF = 4,
50 TINFL_FLAG_COMPUTE_ADLER32 = 8
51 };
52
53 // High level decompression functions:
54 // tinfl_decompress_mem_to_heap() decompresses a block in memory to a heap block allocated via malloc().
55 // On entry:
56 // pSrc_buf, src_buf_len: Pointer and size of the Deflate or zlib source data to decompress.
57 // On return:
58 // Function returns a pointer to the decompressed data, or NULL on failure.
59 // *pOut_len will be set to the decompressed data's size, which could be larger than src_buf_len on uncompressible data.
60 // The caller must free() the returned block when it's no longer needed.
61 void *tinfl_decompress_mem_to_heap(const void *pSrc_buf, size_t src_buf_len, size_t *pOut_len, int flags);
62
63 // tinfl_decompress_mem_to_mem() decompresses a block in memory to another block in memory.
64 // Returns TINFL_DECOMPRESS_MEM_TO_MEM_FAILED on failure, or the number of bytes written on success.
65 #define TINFL_DECOMPRESS_MEM_TO_MEM_FAILED ((size_t)(-1))
66 size_t tinfl_decompress_mem_to_mem(void *pOut_buf, size_t out_buf_len, const void *pSrc_buf, size_t src_buf_len, int flags);
67
68 // tinfl_decompress_mem_to_callback() decompresses a block in memory to an internal 32KB buffer, and a user provided callback function will be called to flush the buffer.
69 // Returns 1 on success or 0 on failure.
70 typedef int (*tinfl_put_buf_func_ptr)(const void* pBuf, int len, void *pUser);
71 int tinfl_decompress_mem_to_callback(const void *pIn_buf, size_t *pIn_buf_size, tinfl_put_buf_func_ptr pPut_buf_func, void *pPut_buf_user, int flags);
72
73 struct tinfl_decompressor_tag; typedef struct tinfl_decompressor_tag tinfl_decompressor;
74
75 // Max size of LZ dictionary.
76 #define TINFL_LZ_DICT_SIZE 32768
77
78 // Return status.
79 typedef enum
80 {
81 // This flags indicates the inflator needs 1 or more input bytes to make forward progress, but the caller is indicating that no more are available. The compressed data
82 // is probably corrupted. If you call the inflator again with more bytes it'll try to continue processing the input but this is a BAD sign (either the data is corrupted or you called it incorrectly).
83 // If you call it again with no input you'll just get TINFL_STATUS_FAILED_CANNOT_MAKE_PROGRESS again.
84 TINFL_STATUS_FAILED_CANNOT_MAKE_PROGRESS = -4,
85
86 // This flag indicates that one or more of the input parameters was obviously bogus. (You can try calling it again, but if you get this error the calling code is wrong.)
87 TINFL_STATUS_BAD_PARAM = -3,
88
89 // This flags indicate the inflator is finished but the adler32 check of the uncompressed data didn't match. If you call it again it'll return TINFL_STATUS_DONE.
90 TINFL_STATUS_ADLER32_MISMATCH = -2,
91
92 // This flags indicate the inflator has somehow failed (bad code, corrupted input, etc.). If you call it again without resetting via tinfl_init() it it'll just keep on returning the same status failure code.
93 TINFL_STATUS_FAILED = -1,
94
95 // Any status code less than TINFL_STATUS_DONE must indicate a failure.
96
97 // This flag indicates the inflator has returned every byte of uncompressed data that it can, has consumed every byte that it needed, has successfully reached the end of the deflate stream, and
98 // if zlib headers and adler32 checking enabled that it has successfully checked the uncompressed data's adler32. If you call it again you'll just get TINFL_STATUS_DONE over and over again.
99 TINFL_STATUS_DONE = 0,
100
101 // This flag indicates the inflator MUST have more input data (even 1 byte) before it can make any more forward progress, or you need to clear the TINFL_FLAG_HAS_MORE_INPUT
102 // flag on the next call if you don't have any more source data. If the source data was somehow corrupted it's also possible (but unlikely) for the inflator to keep on demanding input to
103 // proceed, so be sure to properly set the TINFL_FLAG_HAS_MORE_INPUT flag.
104 TINFL_STATUS_NEEDS_MORE_INPUT = 1,
105
106 // This flag indicates the inflator definitely has 1 or more bytes of uncompressed data available, but it cannot write this data into the output buffer.
107 // Note if the source compressed data was corrupted it's possible for the inflator to return a lot of uncompressed data to the caller. I've been assuming you know how much uncompressed data to expect
108 // (either exact or worst case) and will stop calling the inflator and fail after receiving too much. In pure streaming scenarios where you have no idea how many bytes to expect this may not be possible
109 // so I may need to add some code to address this.
110 TINFL_STATUS_HAS_MORE_OUTPUT = 2
111
112 } tinfl_status;
113
114 // Initializes the decompressor to its initial state.
115 #define tinfl_init(r) do { (r)->m_state = 0; } MZ_MACRO_END
116 #define tinfl_get_adler32(r) (r)->m_check_adler32
117
118 // Main low-level decompressor coroutine function. This is the only function actually needed for decompression. All the other functions are just high-level helpers for improved usability.
119 // This is a universal API, i.e. it can be used as a building block to build any desired higher level decompression API. In the limit case, it can be called once per every byte input or output.
120 tinfl_status tinfl_decompress(tinfl_decompressor *r, const mz_uint8 *pIn_buf_next, size_t *pIn_buf_size, mz_uint8 *pOut_buf_start, mz_uint8 *pOut_buf_next, size_t *pOut_buf_size, const mz_uint32 decomp_flags);
121
122 // Internal/private bits follow.
123 enum
124 {
125 TINFL_MAX_HUFF_TABLES = 3, TINFL_MAX_HUFF_SYMBOLS_0 = 288, TINFL_MAX_HUFF_SYMBOLS_1 = 32, TINFL_MAX_HUFF_SYMBOLS_2 = 19,
126 TINFL_FAST_LOOKUP_BITS = 10, TINFL_FAST_LOOKUP_SIZE = 1 << TINFL_FAST_LOOKUP_BITS
127 };
128
129 typedef struct
130 {
131 mz_uint8 m_code_size[TINFL_MAX_HUFF_SYMBOLS_0];
132 mz_int16 m_look_up[TINFL_FAST_LOOKUP_SIZE], m_tree[TINFL_MAX_HUFF_SYMBOLS_0 * 2];
133 } tinfl_huff_table;
134
135 #if MINIZ_HAS_64BIT_REGISTERS
136 #define TINFL_USE_64BIT_BITBUF 1
137 #endif
138
139 #if TINFL_USE_64BIT_BITBUF
140 typedef mz_uint64 tinfl_bit_buf_t;
141 #define TINFL_BITBUF_SIZE (64)
142 #else
143 typedef mz_uint32 tinfl_bit_buf_t;
144 #define TINFL_BITBUF_SIZE (32)
145 #endif
146
147 struct tinfl_decompressor_tag
148 {
149 mz_uint32 m_state, m_num_bits, m_zhdr0, m_zhdr1, m_z_adler32, m_final, m_type, m_check_adler32, m_dist, m_counter, m_num_extra, m_table_sizes[TINFL_MAX_HUFF_TABLES];
150 tinfl_bit_buf_t m_bit_buf;
151 size_t m_dist_from_out_buf_start;
152 tinfl_huff_table m_tables[TINFL_MAX_HUFF_TABLES];
153 mz_uint8 m_raw_header[4], m_len_codes[TINFL_MAX_HUFF_SYMBOLS_0 + TINFL_MAX_HUFF_SYMBOLS_1 + 137];
154 };
155
156 #endif // #ifdef TINFL_HEADER_INCLUDED
157
158 // ------------------- End of Header: Implementation follows. (If you only want the header, define MINIZ_HEADER_FILE_ONLY.)
159
160 #ifndef TINFL_HEADER_FILE_ONLY
161
162 #include <string.h>
163
164 // MZ_MALLOC, etc. are only used by the optional high-level helper functions.
165 #ifdef MINIZ_NO_MALLOC
166 #define MZ_MALLOC(x) NULL
167 #define MZ_FREE(x) (void)x, ((void)0)
168 #define MZ_REALLOC(p, x) NULL
169 #else
170 #define MZ_MALLOC(x) malloc(x)
171 #define MZ_FREE(x) free(x)
172 #define MZ_REALLOC(p, x) realloc(p, x)
173 #endif
174
175 #define MZ_MAX(a,b) (((a)>(b))?(a):(b))
176 #define MZ_MIN(a,b) (((a)<(b))?(a):(b))
177 #define MZ_CLEAR_OBJ(obj) memset(&(obj), 0, sizeof(obj))
178
179 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES && MINIZ_LITTLE_ENDIAN
180 #define MZ_READ_LE16(p) *((const mz_uint16 *)(p))
181 #define MZ_READ_LE32(p) *((const mz_uint32 *)(p))
182 #else
183 #define MZ_READ_LE16(p) ((mz_uint32)(((const mz_uint8 *)(p))[0]) | ((mz_uint32)(((const mz_uint8 *)(p))[1]) << 8U))
184 #define MZ_READ_LE32(p) ((mz_uint32)(((const mz_uint8 *)(p))[0]) | ((mz_uint32)(((const mz_uint8 *)(p))[1]) << 8U) | ((mz_uint32)(((const mz_uint8 *)(p))[2]) << 16U) | ((mz_uint32)(((const mz_uint8 *)(p))[3]) << 24U))
185 #endif
186
187 #define TINFL_MEMCPY(d, s, l) memcpy(d, s, l)
188 #define TINFL_MEMSET(p, c, l) memset(p, c, l)
189
190 #define TINFL_CR_BEGIN switch(r->m_state) { case 0:
191 #define TINFL_CR_RETURN(state_index, result) do { status = result; r->m_state = state_index; goto common_exit; case state_index:; } MZ_MACRO_END
192 #define TINFL_CR_RETURN_FOREVER(state_index, result) do { for ( ; ; ) { TINFL_CR_RETURN(state_index, result); } } MZ_MACRO_END
193 #define TINFL_CR_FINISH }
194
195 #define TINFL_GET_BYTE(state_index, c) do { \
196 while (pIn_buf_cur >= pIn_buf_end) { \
197 TINFL_CR_RETURN(state_index, (decomp_flags & TINFL_FLAG_HAS_MORE_INPUT) ? TINFL_STATUS_NEEDS_MORE_INPUT : TINFL_STATUS_FAILED_CANNOT_MAKE_PROGRESS); \
198 } c = *pIn_buf_cur++; } MZ_MACRO_END
199
200 #define TINFL_NEED_BITS(state_index, n) do { mz_uint c; TINFL_GET_BYTE(state_index, c); bit_buf |= (((tinfl_bit_buf_t)c) << num_bits); num_bits += 8; } while (num_bits < (mz_uint)(n))
201 #define TINFL_SKIP_BITS(state_index, n) do { if (num_bits < (mz_uint)(n)) { TINFL_NEED_BITS(state_index, n); } bit_buf >>= (n); num_bits -= (n); } MZ_MACRO_END
202 #define TINFL_GET_BITS(state_index, b, n) do { if (num_bits < (mz_uint)(n)) { TINFL_NEED_BITS(state_index, n); } b = bit_buf & ((1 << (n)) - 1); bit_buf >>= (n); num_bits -= (n); } MZ_MACRO_END
203
204 // TINFL_HUFF_BITBUF_FILL() is only used rarely, when the number of bytes remaining in the input buffer falls below 2.
205 // It reads just enough bytes from the input stream that are needed to decode the next Huffman code (and absolutely no more). It works by trying to fully decode a
206 // Huffman code by using whatever bits are currently present in the bit buffer. If this fails, it reads another byte, and tries again until it succeeds or until the
207 // bit buffer contains >=15 bits (deflate's max. Huffman code size).
208 #define TINFL_HUFF_BITBUF_FILL(state_index, pHuff) \
209 do { \
210 temp = (pHuff)->m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]; \
211 if (temp >= 0) { \
212 code_len = temp >> 9; \
213 if ((code_len) && (num_bits >= code_len)) \
214 break; \
215 } else if (num_bits > TINFL_FAST_LOOKUP_BITS) { \
216 code_len = TINFL_FAST_LOOKUP_BITS; \
217 do { \
218 temp = (pHuff)->m_tree[~temp + ((bit_buf >> code_len++) & 1)]; \
219 } while ((temp < 0) && (num_bits >= (code_len + 1))); if (temp >= 0) break; \
220 } TINFL_GET_BYTE(state_index, c); bit_buf |= (((tinfl_bit_buf_t)c) << num_bits); num_bits += 8; \
221 } while (num_bits < 15);
222
223 // TINFL_HUFF_DECODE() decodes the next Huffman coded symbol. It's more complex than you would initially expect because the zlib API expects the decompressor to never read
224 // beyond the final byte of the deflate stream. (In other words, when this macro wants to read another byte from the input, it REALLY needs another byte in order to fully
225 // decode the next Huffman code.) Handling this properly is particularly important on raw deflate (non-zlib) streams, which aren't followed by a byte aligned adler-32.
226 // The slow path is only executed at the very end of the input buffer.
227 // v1.16: The original macro handled the case at the very end of the passed-in input buffer, but we also need to handle the case where the user passes in 1+zillion bytes
228 // following the deflate data and our non-conservative read-ahead path won't kick in here on this code. This is much trickier.
229 #define TINFL_HUFF_DECODE(state_index, sym, pHuff) do { \
230 int temp; mz_uint code_len, c; \
231 if (num_bits < 15) { \
232 if ((pIn_buf_end - pIn_buf_cur) < 2) { \
233 TINFL_HUFF_BITBUF_FILL(state_index, pHuff); \
234 } else { \
235 bit_buf |= (((tinfl_bit_buf_t)pIn_buf_cur[0]) << num_bits) | (((tinfl_bit_buf_t)pIn_buf_cur[1]) << (num_bits + 8)); pIn_buf_cur += 2; num_bits += 16; \
236 } \
237 } \
238 if ((temp = (pHuff)->m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0) \
239 code_len = temp >> 9, temp &= 511; \
240 else { \
241 code_len = TINFL_FAST_LOOKUP_BITS; do { temp = (pHuff)->m_tree[~temp + ((bit_buf >> code_len++) & 1)]; } while (temp < 0); \
242 } sym = temp; bit_buf >>= code_len; num_bits -= code_len; } MZ_MACRO_END
243
tinfl_decompress(tinfl_decompressor * r,const mz_uint8 * pIn_buf_next,size_t * pIn_buf_size,mz_uint8 * pOut_buf_start,mz_uint8 * pOut_buf_next,size_t * pOut_buf_size,const mz_uint32 decomp_flags)244 tinfl_status tinfl_decompress(tinfl_decompressor *r, const mz_uint8 *pIn_buf_next, size_t *pIn_buf_size, mz_uint8 *pOut_buf_start, mz_uint8 *pOut_buf_next, size_t *pOut_buf_size, const mz_uint32 decomp_flags)
245 {
246 static const int s_length_base[31] = { 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,0,0 };
247 static const int s_length_extra[31]= { 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,0,0 };
248 static const int s_dist_base[32] = { 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,0,0};
249 static const int s_dist_extra[32] = { 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};
250 static const mz_uint8 s_length_dezigzag[19] = { 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15 };
251 static const int s_min_table_sizes[3] = { 257, 1, 4 };
252
253 tinfl_status status = TINFL_STATUS_FAILED; mz_uint32 num_bits, dist, counter, num_extra; tinfl_bit_buf_t bit_buf;
254 const mz_uint8 *pIn_buf_cur = pIn_buf_next, *const pIn_buf_end = pIn_buf_next + *pIn_buf_size;
255 mz_uint8 *pOut_buf_cur = pOut_buf_next, *const pOut_buf_end = pOut_buf_next + *pOut_buf_size;
256 size_t out_buf_size_mask = (decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF) ? (size_t)-1 : ((pOut_buf_next - pOut_buf_start) + *pOut_buf_size) - 1, dist_from_out_buf_start;
257
258 // Ensure the output buffer's size is a power of 2, unless the output buffer is large enough to hold the entire output file (in which case it doesn't matter).
259 if (((out_buf_size_mask + 1) & out_buf_size_mask) || (pOut_buf_next < pOut_buf_start)) { *pIn_buf_size = *pOut_buf_size = 0; return TINFL_STATUS_BAD_PARAM; }
260
261 num_bits = r->m_num_bits; bit_buf = r->m_bit_buf; dist = r->m_dist; counter = r->m_counter; num_extra = r->m_num_extra; dist_from_out_buf_start = r->m_dist_from_out_buf_start;
262 TINFL_CR_BEGIN
263
264 bit_buf = num_bits = dist = counter = num_extra = r->m_zhdr0 = r->m_zhdr1 = 0; r->m_z_adler32 = r->m_check_adler32 = 1;
265 if (decomp_flags & TINFL_FLAG_PARSE_ZLIB_HEADER)
266 {
267 TINFL_GET_BYTE(1, r->m_zhdr0); TINFL_GET_BYTE(2, r->m_zhdr1);
268 counter = (((r->m_zhdr0 * 256 + r->m_zhdr1) % 31 != 0) || (r->m_zhdr1 & 32) || ((r->m_zhdr0 & 15) != 8));
269 if (!(decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF)) counter |= (((1U << (8U + (r->m_zhdr0 >> 4))) > 32768U) || ((out_buf_size_mask + 1) < (size_t)(1U << (8U + (r->m_zhdr0 >> 4)))));
270 if (counter) { TINFL_CR_RETURN_FOREVER(36, TINFL_STATUS_FAILED); }
271 }
272
273 do
274 {
275 TINFL_GET_BITS(3, r->m_final, 3); r->m_type = r->m_final >> 1;
276 if (r->m_type == 0)
277 {
278 TINFL_SKIP_BITS(5, num_bits & 7);
279 for (counter = 0; counter < 4; ++counter) { if (num_bits) TINFL_GET_BITS(6, r->m_raw_header[counter], 8); else TINFL_GET_BYTE(7, r->m_raw_header[counter]); }
280 if ((counter = (r->m_raw_header[0] | (r->m_raw_header[1] << 8))) != (mz_uint)(0xFFFF ^ (r->m_raw_header[2] | (r->m_raw_header[3] << 8)))) { TINFL_CR_RETURN_FOREVER(39, TINFL_STATUS_FAILED); }
281 while ((counter) && (num_bits))
282 {
283 TINFL_GET_BITS(51, dist, 8);
284 while (pOut_buf_cur >= pOut_buf_end) { TINFL_CR_RETURN(52, TINFL_STATUS_HAS_MORE_OUTPUT); }
285 *pOut_buf_cur++ = (mz_uint8)dist;
286 counter--;
287 }
288 while (counter)
289 {
290 size_t n; while (pOut_buf_cur >= pOut_buf_end) { TINFL_CR_RETURN(9, TINFL_STATUS_HAS_MORE_OUTPUT); }
291 while (pIn_buf_cur >= pIn_buf_end)
292 {
293 TINFL_CR_RETURN(38, (decomp_flags & TINFL_FLAG_HAS_MORE_INPUT) ? TINFL_STATUS_NEEDS_MORE_INPUT : TINFL_STATUS_FAILED_CANNOT_MAKE_PROGRESS);
294 }
295 n = MZ_MIN(MZ_MIN((size_t)(pOut_buf_end - pOut_buf_cur), (size_t)(pIn_buf_end - pIn_buf_cur)), counter);
296 TINFL_MEMCPY(pOut_buf_cur, pIn_buf_cur, n); pIn_buf_cur += n; pOut_buf_cur += n; counter -= (mz_uint)n;
297 }
298 }
299 else if (r->m_type == 3)
300 {
301 TINFL_CR_RETURN_FOREVER(10, TINFL_STATUS_FAILED);
302 }
303 else
304 {
305 if (r->m_type == 1)
306 {
307 mz_uint8 *p = r->m_tables[0].m_code_size; mz_uint i;
308 r->m_table_sizes[0] = 288; r->m_table_sizes[1] = 32; TINFL_MEMSET(r->m_tables[1].m_code_size, 5, 32);
309 for ( i = 0; i <= 143; ++i) *p++ = 8; for ( ; i <= 255; ++i) *p++ = 9; for ( ; i <= 279; ++i) *p++ = 7; for ( ; i <= 287; ++i) *p++ = 8;
310 }
311 else
312 {
313 for (counter = 0; counter < 3; counter++) { TINFL_GET_BITS(11, r->m_table_sizes[counter], "\05\05\04"[counter]); r->m_table_sizes[counter] += s_min_table_sizes[counter]; }
314 MZ_CLEAR_OBJ(r->m_tables[2].m_code_size); for (counter = 0; counter < r->m_table_sizes[2]; counter++) { mz_uint s; TINFL_GET_BITS(14, s, 3); r->m_tables[2].m_code_size[s_length_dezigzag[counter]] = (mz_uint8)s; }
315 r->m_table_sizes[2] = 19;
316 }
317 for ( ; (int)r->m_type >= 0; r->m_type--)
318 {
319 int tree_next, tree_cur; tinfl_huff_table *pTable;
320 mz_uint i, j, used_syms, total, sym_index, next_code[17], total_syms[16]; pTable = &r->m_tables[r->m_type]; MZ_CLEAR_OBJ(total_syms); MZ_CLEAR_OBJ(pTable->m_look_up); MZ_CLEAR_OBJ(pTable->m_tree);
321 for (i = 0; i < r->m_table_sizes[r->m_type]; ++i) total_syms[pTable->m_code_size[i]]++;
322 used_syms = 0, total = 0; next_code[0] = next_code[1] = 0;
323 for (i = 1; i <= 15; ++i) { used_syms += total_syms[i]; next_code[i + 1] = (total = ((total + total_syms[i]) << 1)); }
324 if ((65536 != total) && (used_syms > 1))
325 {
326 TINFL_CR_RETURN_FOREVER(35, TINFL_STATUS_FAILED);
327 }
328 for (tree_next = -1, sym_index = 0; sym_index < r->m_table_sizes[r->m_type]; ++sym_index)
329 {
330 mz_uint rev_code = 0, l, cur_code, code_size = pTable->m_code_size[sym_index]; if (!code_size) continue;
331 cur_code = next_code[code_size]++; for (l = code_size; l > 0; l--, cur_code >>= 1) rev_code = (rev_code << 1) | (cur_code & 1);
332 if (code_size <= TINFL_FAST_LOOKUP_BITS) { mz_int16 k = (mz_int16)((code_size << 9) | sym_index); while (rev_code < TINFL_FAST_LOOKUP_SIZE) { pTable->m_look_up[rev_code] = k; rev_code += (1 << code_size); } continue; }
333 if (0 == (tree_cur = pTable->m_look_up[rev_code & (TINFL_FAST_LOOKUP_SIZE - 1)])) { pTable->m_look_up[rev_code & (TINFL_FAST_LOOKUP_SIZE - 1)] = (mz_int16)tree_next; tree_cur = tree_next; tree_next -= 2; }
334 rev_code >>= (TINFL_FAST_LOOKUP_BITS - 1);
335 for (j = code_size; j > (TINFL_FAST_LOOKUP_BITS + 1); j--)
336 {
337 tree_cur -= ((rev_code >>= 1) & 1);
338 if (!pTable->m_tree[-tree_cur - 1]) { pTable->m_tree[-tree_cur - 1] = (mz_int16)tree_next; tree_cur = tree_next; tree_next -= 2; } else tree_cur = pTable->m_tree[-tree_cur - 1];
339 }
340 tree_cur -= ((rev_code >>= 1) & 1); pTable->m_tree[-tree_cur - 1] = (mz_int16)sym_index;
341 }
342 if (r->m_type == 2)
343 {
344 for (counter = 0; counter < (r->m_table_sizes[0] + r->m_table_sizes[1]); )
345 {
346 mz_uint s; TINFL_HUFF_DECODE(16, dist, &r->m_tables[2]); if (dist < 16) { r->m_len_codes[counter++] = (mz_uint8)dist; continue; }
347 if ((dist == 16) && (!counter))
348 {
349 TINFL_CR_RETURN_FOREVER(17, TINFL_STATUS_FAILED);
350 }
351 num_extra = "\02\03\07"[dist - 16]; TINFL_GET_BITS(18, s, num_extra); s += "\03\03\013"[dist - 16];
352 TINFL_MEMSET(r->m_len_codes + counter, (dist == 16) ? r->m_len_codes[counter - 1] : 0, s); counter += s;
353 }
354 if ((r->m_table_sizes[0] + r->m_table_sizes[1]) != counter)
355 {
356 TINFL_CR_RETURN_FOREVER(21, TINFL_STATUS_FAILED);
357 }
358 TINFL_MEMCPY(r->m_tables[0].m_code_size, r->m_len_codes, r->m_table_sizes[0]); TINFL_MEMCPY(r->m_tables[1].m_code_size, r->m_len_codes + r->m_table_sizes[0], r->m_table_sizes[1]);
359 }
360 }
361 for ( ; ; )
362 {
363 mz_uint8 *pSrc;
364 for ( ; ; )
365 {
366 if (((pIn_buf_end - pIn_buf_cur) < 4) || ((pOut_buf_end - pOut_buf_cur) < 2))
367 {
368 TINFL_HUFF_DECODE(23, counter, &r->m_tables[0]);
369 if (counter >= 256)
370 break;
371 while (pOut_buf_cur >= pOut_buf_end) { TINFL_CR_RETURN(24, TINFL_STATUS_HAS_MORE_OUTPUT); }
372 *pOut_buf_cur++ = (mz_uint8)counter;
373 }
374 else
375 {
376 int sym2; mz_uint code_len;
377 #if TINFL_USE_64BIT_BITBUF
378 if (num_bits < 30) { bit_buf |= (((tinfl_bit_buf_t)MZ_READ_LE32(pIn_buf_cur)) << num_bits); pIn_buf_cur += 4; num_bits += 32; }
379 #else
380 if (num_bits < 15) { bit_buf |= (((tinfl_bit_buf_t)MZ_READ_LE16(pIn_buf_cur)) << num_bits); pIn_buf_cur += 2; num_bits += 16; }
381 #endif
382 if ((sym2 = r->m_tables[0].m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0)
383 code_len = sym2 >> 9;
384 else
385 {
386 code_len = TINFL_FAST_LOOKUP_BITS; do { sym2 = r->m_tables[0].m_tree[~sym2 + ((bit_buf >> code_len++) & 1)]; } while (sym2 < 0);
387 }
388 counter = sym2; bit_buf >>= code_len; num_bits -= code_len;
389 if (counter & 256)
390 break;
391
392 #if !TINFL_USE_64BIT_BITBUF
393 if (num_bits < 15) { bit_buf |= (((tinfl_bit_buf_t)MZ_READ_LE16(pIn_buf_cur)) << num_bits); pIn_buf_cur += 2; num_bits += 16; }
394 #endif
395 if ((sym2 = r->m_tables[0].m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0)
396 code_len = sym2 >> 9;
397 else
398 {
399 code_len = TINFL_FAST_LOOKUP_BITS; do { sym2 = r->m_tables[0].m_tree[~sym2 + ((bit_buf >> code_len++) & 1)]; } while (sym2 < 0);
400 }
401 bit_buf >>= code_len; num_bits -= code_len;
402
403 pOut_buf_cur[0] = (mz_uint8)counter;
404 if (sym2 & 256)
405 {
406 pOut_buf_cur++;
407 counter = sym2;
408 break;
409 }
410 pOut_buf_cur[1] = (mz_uint8)sym2;
411 pOut_buf_cur += 2;
412 }
413 }
414 if ((counter &= 511) == 256) break;
415
416 num_extra = s_length_extra[counter - 257]; counter = s_length_base[counter - 257];
417 if (num_extra) { mz_uint extra_bits; TINFL_GET_BITS(25, extra_bits, num_extra); counter += extra_bits; }
418
419 TINFL_HUFF_DECODE(26, dist, &r->m_tables[1]);
420 num_extra = s_dist_extra[dist]; dist = s_dist_base[dist];
421 if (num_extra) { mz_uint extra_bits; TINFL_GET_BITS(27, extra_bits, num_extra); dist += extra_bits; }
422
423 dist_from_out_buf_start = pOut_buf_cur - pOut_buf_start;
424 if ((dist > dist_from_out_buf_start) && (decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF))
425 {
426 TINFL_CR_RETURN_FOREVER(37, TINFL_STATUS_FAILED);
427 }
428
429 pSrc = pOut_buf_start + ((dist_from_out_buf_start - dist) & out_buf_size_mask);
430
431 if ((MZ_MAX(pOut_buf_cur, pSrc) + counter) > pOut_buf_end)
432 {
433 while (counter--)
434 {
435 while (pOut_buf_cur >= pOut_buf_end) { TINFL_CR_RETURN(53, TINFL_STATUS_HAS_MORE_OUTPUT); }
436 *pOut_buf_cur++ = pOut_buf_start[(dist_from_out_buf_start++ - dist) & out_buf_size_mask];
437 }
438 continue;
439 }
440 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES
441 else if ((counter >= 9) && (counter <= dist))
442 {
443 const mz_uint8 *pSrc_end = pSrc + (counter & ~7);
444 do
445 {
446 ((mz_uint32 *)pOut_buf_cur)[0] = ((const mz_uint32 *)pSrc)[0];
447 ((mz_uint32 *)pOut_buf_cur)[1] = ((const mz_uint32 *)pSrc)[1];
448 pOut_buf_cur += 8;
449 } while ((pSrc += 8) < pSrc_end);
450 if ((counter &= 7) < 3)
451 {
452 if (counter)
453 {
454 pOut_buf_cur[0] = pSrc[0];
455 if (counter > 1)
456 pOut_buf_cur[1] = pSrc[1];
457 pOut_buf_cur += counter;
458 }
459 continue;
460 }
461 }
462 #endif
463 do
464 {
465 pOut_buf_cur[0] = pSrc[0];
466 pOut_buf_cur[1] = pSrc[1];
467 pOut_buf_cur[2] = pSrc[2];
468 pOut_buf_cur += 3; pSrc += 3;
469 } while ((int)(counter -= 3) > 2);
470 if ((int)counter > 0)
471 {
472 pOut_buf_cur[0] = pSrc[0];
473 if ((int)counter > 1)
474 pOut_buf_cur[1] = pSrc[1];
475 pOut_buf_cur += counter;
476 }
477 }
478 }
479 } while (!(r->m_final & 1));
480
481 // Ensure byte alignment and put back any bytes from the bitbuf if we've looked ahead too far on gzip, or other Deflate streams followed by arbitrary data.
482 // I'm being super conservative here. A number of simplifications can be made to the byte alignment part, and the Adler32 check shouldn't ever need to worry about reading from the bitbuf now.
483 TINFL_SKIP_BITS(32, num_bits & 7);
484 while ((pIn_buf_cur > pIn_buf_next) && (num_bits >= 8)) { --pIn_buf_cur; num_bits -= 8; } bit_buf &= (tinfl_bit_buf_t)((1ULL << num_bits) - 1ULL);
485 //MZ_ASSERT(!num_bits); // if this assert fires then we've read beyond the end of non-deflate/zlib streams with following data (such as gzip streams).
486
487 if (decomp_flags & TINFL_FLAG_PARSE_ZLIB_HEADER)
488 {
489 for (counter = 0; counter < 4; ++counter) { mz_uint s; if (num_bits) TINFL_GET_BITS(41, s, 8); else TINFL_GET_BYTE(42, s); r->m_z_adler32 = (r->m_z_adler32 << 8) | s; }
490 }
491 TINFL_CR_RETURN_FOREVER(34, TINFL_STATUS_DONE);
492
493 TINFL_CR_FINISH
494
495 common_exit:
496 // As long as we aren't telling the caller that we NEED more input to make forward progress:
497 // Put back any bytes from the bitbuf in case we've looked ahead too far on gzip, or other Deflate streams followed by arbitrary data.
498 // We need to be very careful here to NOT push back any bytes we definitely know we need to make forward progress, though, or we'll lock the caller up into an inf loop.
499 if ((status != TINFL_STATUS_NEEDS_MORE_INPUT) && (status != TINFL_STATUS_FAILED_CANNOT_MAKE_PROGRESS)) { while ((pIn_buf_cur > pIn_buf_next) && (num_bits >= 8)) { --pIn_buf_cur; num_bits -= 8; } }
500 r->m_num_bits = num_bits; r->m_bit_buf = bit_buf & (tinfl_bit_buf_t)((1ULL << num_bits) - 1ULL); r->m_dist = dist; r->m_counter = counter; r->m_num_extra = num_extra; r->m_dist_from_out_buf_start = dist_from_out_buf_start;
501 *pIn_buf_size = pIn_buf_cur - pIn_buf_next; *pOut_buf_size = pOut_buf_cur - pOut_buf_next;
502 if ((decomp_flags & (TINFL_FLAG_PARSE_ZLIB_HEADER | TINFL_FLAG_COMPUTE_ADLER32)) && (status >= 0))
503 {
504 const mz_uint8 *ptr = pOut_buf_next; size_t buf_len = *pOut_buf_size;
505 mz_uint32 i, s1 = r->m_check_adler32 & 0xffff, s2 = r->m_check_adler32 >> 16; size_t block_len = buf_len % 5552;
506 while (buf_len)
507 {
508 for (i = 0; i + 7 < block_len; i += 8, ptr += 8)
509 {
510 s1 += ptr[0], s2 += s1; s1 += ptr[1], s2 += s1; s1 += ptr[2], s2 += s1; s1 += ptr[3], s2 += s1;
511 s1 += ptr[4], s2 += s1; s1 += ptr[5], s2 += s1; s1 += ptr[6], s2 += s1; s1 += ptr[7], s2 += s1;
512 }
513 for ( ; i < block_len; ++i) s1 += *ptr++, s2 += s1;
514 s1 %= 65521U, s2 %= 65521U; buf_len -= block_len; block_len = 5552;
515 }
516 r->m_check_adler32 = (s2 << 16) + s1; if ((status == TINFL_STATUS_DONE) && (decomp_flags & TINFL_FLAG_PARSE_ZLIB_HEADER) && (r->m_check_adler32 != r->m_z_adler32)) status = TINFL_STATUS_ADLER32_MISMATCH;
517 }
518 return status;
519 }
520
521 // Higher level helper functions.
tinfl_decompress_mem_to_heap(const void * pSrc_buf,size_t src_buf_len,size_t * pOut_len,int flags)522 void *tinfl_decompress_mem_to_heap(const void *pSrc_buf, size_t src_buf_len, size_t *pOut_len, int flags)
523 {
524 tinfl_decompressor decomp; void *pBuf = NULL, *pNew_buf; size_t src_buf_ofs = 0, out_buf_capacity = 0;
525 *pOut_len = 0;
526 tinfl_init(&decomp);
527 for ( ; ; )
528 {
529 size_t src_buf_size = src_buf_len - src_buf_ofs, dst_buf_size = out_buf_capacity - *pOut_len, new_out_buf_capacity;
530 tinfl_status status = tinfl_decompress(&decomp, (const mz_uint8*)pSrc_buf + src_buf_ofs, &src_buf_size, (mz_uint8*)pBuf, pBuf ? (mz_uint8*)pBuf + *pOut_len : NULL, &dst_buf_size,
531 (flags & ~TINFL_FLAG_HAS_MORE_INPUT) | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF);
532 if ((status < 0) || (status == TINFL_STATUS_NEEDS_MORE_INPUT))
533 {
534 MZ_FREE(pBuf); *pOut_len = 0; return NULL;
535 }
536 src_buf_ofs += src_buf_size;
537 *pOut_len += dst_buf_size;
538 if (status == TINFL_STATUS_DONE) break;
539 new_out_buf_capacity = out_buf_capacity * 2; if (new_out_buf_capacity < 128) new_out_buf_capacity = 128;
540 pNew_buf = MZ_REALLOC(pBuf, new_out_buf_capacity);
541 if (!pNew_buf)
542 {
543 MZ_FREE(pBuf); *pOut_len = 0; return NULL;
544 }
545 pBuf = pNew_buf; out_buf_capacity = new_out_buf_capacity;
546 }
547 return pBuf;
548 }
549
tinfl_decompress_mem_to_mem(void * pOut_buf,size_t out_buf_len,const void * pSrc_buf,size_t src_buf_len,int flags)550 size_t tinfl_decompress_mem_to_mem(void *pOut_buf, size_t out_buf_len, const void *pSrc_buf, size_t src_buf_len, int flags)
551 {
552 tinfl_decompressor decomp; tinfl_status status; tinfl_init(&decomp);
553 status = tinfl_decompress(&decomp, (const mz_uint8*)pSrc_buf, &src_buf_len, (mz_uint8*)pOut_buf, (mz_uint8*)pOut_buf, &out_buf_len, (flags & ~TINFL_FLAG_HAS_MORE_INPUT) | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF);
554 return (status != TINFL_STATUS_DONE) ? TINFL_DECOMPRESS_MEM_TO_MEM_FAILED : out_buf_len;
555 }
556
tinfl_decompress_mem_to_callback(const void * pIn_buf,size_t * pIn_buf_size,tinfl_put_buf_func_ptr pPut_buf_func,void * pPut_buf_user,int flags)557 int tinfl_decompress_mem_to_callback(const void *pIn_buf, size_t *pIn_buf_size, tinfl_put_buf_func_ptr pPut_buf_func, void *pPut_buf_user, int flags)
558 {
559 int result = 0;
560 tinfl_decompressor decomp;
561 mz_uint8 *pDict = (mz_uint8*)MZ_MALLOC(TINFL_LZ_DICT_SIZE); size_t in_buf_ofs = 0, dict_ofs = 0;
562 if (!pDict)
563 return TINFL_STATUS_FAILED;
564 tinfl_init(&decomp);
565 for ( ; ; )
566 {
567 size_t in_buf_size = *pIn_buf_size - in_buf_ofs, dst_buf_size = TINFL_LZ_DICT_SIZE - dict_ofs;
568 tinfl_status status = tinfl_decompress(&decomp, (const mz_uint8*)pIn_buf + in_buf_ofs, &in_buf_size, pDict, pDict + dict_ofs, &dst_buf_size,
569 (flags & ~(TINFL_FLAG_HAS_MORE_INPUT | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF)));
570 in_buf_ofs += in_buf_size;
571 if ((dst_buf_size) && (!(*pPut_buf_func)(pDict + dict_ofs, (int)dst_buf_size, pPut_buf_user)))
572 break;
573 if (status != TINFL_STATUS_HAS_MORE_OUTPUT)
574 {
575 result = (status == TINFL_STATUS_DONE);
576 break;
577 }
578 dict_ofs = (dict_ofs + dst_buf_size) & (TINFL_LZ_DICT_SIZE - 1);
579 }
580 MZ_FREE(pDict);
581 *pIn_buf_size = in_buf_ofs;
582 return result;
583 }
584
585 #endif // #ifndef TINFL_HEADER_FILE_ONLY
586
587 /*
588 This is free and unencumbered software released into the public domain.
589
590 Anyone is free to copy, modify, publish, use, compile, sell, or
591 distribute this software, either in source code form or as a compiled
592 binary, for any purpose, commercial or non-commercial, and by any
593 means.
594
595 In jurisdictions that recognize copyright laws, the author or authors
596 of this software dedicate any and all copyright interest in the
597 software to the public domain. We make this dedication for the benefit
598 of the public at large and to the detriment of our heirs and
599 successors. We intend this dedication to be an overt act of
600 relinquishment in perpetuity of all present and future rights to this
601 software under copyright law.
602
603 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
604 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
605 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
606 IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
607 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
608 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
609 OTHER DEALINGS IN THE SOFTWARE.
610
611 For more information, please refer to <http://unlicense.org/>
612 */
613