1 /*--------------------------------------------------------------------*/
2 /*--- Tiny zlib decompressor tinfl.c ---*/
3 /*--------------------------------------------------------------------*/
4
5 /* tinfl.c v1.11 - public domain inflate with zlib header parsing/adler32
6 checking (inflate-only subset of miniz.c)
7
8 Rich Geldreich <richgel99@gmail.com>, last updated May 20, 2011
9
10 Implements RFC 1950: http://www.ietf.org/rfc/rfc1950.txt
11 and RFC 1951: http://www.ietf.org/rfc/rfc1951.txt
12
13 The original file has been modified in order to be a part of Valgrind
14 project, a dynamic binary instrumentation framework.
15 RT-RK Institute for Computer Based Systems, 2016 (mips-valgrind@rt-rk.com)
16
17 This program is free software; you can redistribute it and/or
18 modify it under the terms of the GNU General Public License as
19 published by the Free Software Foundation; either version 2 of the
20 License, or (at your option) any later version.
21
22 This program is distributed in the hope that it will be useful, but
23 WITHOUT ANY WARRANTY; without even the implied warranty of
24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 General Public License for more details.
26
27 You should have received a copy of the GNU General Public License
28 along with this program; if not, write to the Free Software
29 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
30 02111-1307, USA.
31
32 The GNU General Public License is contained in the file COPYING.
33 */
34
35 #ifndef TINFL_HEADER_INCLUDED
36 #define TINFL_HEADER_INCLUDED
37
38 /* The entire decompressor coroutine is implemented in tinfl_decompress().
39 The other functions are optional high-level helpers. */
40
41 #include "pub_core_basics.h"
42
43 typedef UChar mz_uint8;
44 typedef Short mz_int16;
45 typedef UShort mz_uint16;
46 typedef UInt mz_uint32;
47 typedef UInt mz_uint;
48 typedef ULong mz_uint64;
49
50 #if defined(VGA_x86) || defined(VGA_amd64)
51 // Set MINIZ_USE_UNALIGNED_LOADS_AND_STORES to 1 if integer loads and stores to
52 // unaligned addresses are acceptable on the target platform (slightly faster).
53 #define MINIZ_USE_UNALIGNED_LOADS_AND_STORES 1
54 #endif
55
56 #define MINIZ_LITTLE_ENDIAN ( defined(VG_LITTLEENDIAN) )
57 #define MINIZ_HAS_64BIT_REGISTERS ( VG_WORDSIZE == 8 )
58
59 // Works around MSVC's spammy "warning C4127: conditional expression is
60 // constant" message.
61 #ifdef _MSC_VER
62 #define MZ_MACRO_END while (0, 0)
63 #else
64 #define MZ_MACRO_END while (0)
65 #endif
66
67 /* Decompression flags used by tinfl_decompress().
68
69 TINFL_FLAG_PARSE_ZLIB_HEADER: If set, the input has a valid zlib header and
70 ends with an adler32 checksum (it's a valid zlib stream). Otherwise, the
71 input is a raw deflate stream.
72
73 TINFL_FLAG_HAS_MORE_INPUT: If set, there are more input bytes available
74 beyond the end of the supplied input buffer. If clear, the input buffer
75 contains all remaining input.
76
77 TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF: If set, the output buffer is large
78 enough to hold the entire decompressed stream. If clear, the output buffer
79 is at least the size of the dictionary (typically 32KB).
80
81 TINFL_FLAG_COMPUTE_ADLER32: Force adler-32 checksum computation of the
82 decompressed bytes.
83 */
84
85 enum
86 {
87 TINFL_FLAG_PARSE_ZLIB_HEADER = 1,
88 TINFL_FLAG_HAS_MORE_INPUT = 2,
89 TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF = 4,
90 TINFL_FLAG_COMPUTE_ADLER32 = 8
91 };
92
93 // High level decompression functions:
94 // tinfl_decompress_mem_to_heap() decompresses a block in memory to a heap block allocated via malloc().
95 // On entry:
96 // pSrc_buf, src_buf_len: Pointer and size of the Deflate or zlib source data to decompress.
97 // On return:
98 // Function returns a pointer to the decompressed data, or NULL on failure.
99 // *pOut_len will be set to the decompressed data's size, which could be larger than src_buf_len on uncompressible data.
100 // The caller must free() the returned block when it's no longer needed.
101 void *tinfl_decompress_mem_to_heap(const void *pSrc_buf, SizeT src_buf_len, SizeT *pOut_len, int flags);
102
103 // tinfl_decompress_mem_to_mem() decompresses a block in memory to another block in memory.
104 // Returns TINFL_DECOMPRESS_MEM_TO_MEM_FAILED on failure, or the number of bytes written on success.
105 #define TINFL_DECOMPRESS_MEM_TO_MEM_FAILED ((SizeT)(-1))
106 SizeT tinfl_decompress_mem_to_mem(void *pOut_buf, SizeT out_buf_len, const void *pSrc_buf, SizeT src_buf_len, int flags);
107
108 // 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.
109 // Returns 1 on success or 0 on failure.
110 typedef int (*tinfl_put_buf_func_ptr)(const void* pBuf, int len, void *pUser);
111 int tinfl_decompress_mem_to_callback(const void *pIn_buf, SizeT *pIn_buf_size, tinfl_put_buf_func_ptr pPut_buf_func, void *pPut_buf_user, int flags);
112
113 struct tinfl_decompressor_tag; typedef struct tinfl_decompressor_tag tinfl_decompressor;
114
115 // Max size of LZ dictionary.
116 #define TINFL_LZ_DICT_SIZE 32768
117
118 // Return status.
119 typedef enum
120 {
121 TINFL_STATUS_BAD_PARAM = -3,
122 TINFL_STATUS_ADLER32_MISMATCH = -2,
123 TINFL_STATUS_FAILED = -1,
124 TINFL_STATUS_DONE = 0,
125 TINFL_STATUS_NEEDS_MORE_INPUT = 1,
126 TINFL_STATUS_HAS_MORE_OUTPUT = 2
127 } tinfl_status;
128
129 // Initializes the decompressor to its initial state.
130 #define tinfl_init(r) do { (r)->m_state = 0; } MZ_MACRO_END
131 #define tinfl_get_adler32(r) (r)->m_check_adler32
132
133 // 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.
134 // 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.
135 tinfl_status tinfl_decompress(tinfl_decompressor *r, const mz_uint8 *pIn_buf_next, SizeT *pIn_buf_size, mz_uint8 *pOut_buf_start, mz_uint8 *pOut_buf_next, SizeT *pOut_buf_size, const mz_uint32 decomp_flags);
136
137 // Internal/private bits follow.
138 enum
139 {
140 TINFL_MAX_HUFF_TABLES = 3, TINFL_MAX_HUFF_SYMBOLS_0 = 288, TINFL_MAX_HUFF_SYMBOLS_1 = 32, TINFL_MAX_HUFF_SYMBOLS_2 = 19,
141 TINFL_FAST_LOOKUP_BITS = 10, TINFL_FAST_LOOKUP_SIZE = 1 << TINFL_FAST_LOOKUP_BITS
142 };
143
144 typedef struct
145 {
146 mz_uint8 m_code_size[TINFL_MAX_HUFF_SYMBOLS_0];
147 mz_int16 m_look_up[TINFL_FAST_LOOKUP_SIZE], m_tree[TINFL_MAX_HUFF_SYMBOLS_0 * 2];
148 } tinfl_huff_table;
149
150 #if MINIZ_HAS_64BIT_REGISTERS
151 #define TINFL_USE_64BIT_BITBUF 1
152 #endif
153
154 #if TINFL_USE_64BIT_BITBUF
155 typedef mz_uint64 tinfl_bit_buf_t;
156 #define TINFL_BITBUF_SIZE (64)
157 #else
158 typedef mz_uint32 tinfl_bit_buf_t;
159 #define TINFL_BITBUF_SIZE (32)
160 #endif
161
162 struct tinfl_decompressor_tag
163 {
164 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];
165 tinfl_bit_buf_t m_bit_buf;
166 SizeT m_dist_from_out_buf_start;
167 tinfl_huff_table m_tables[TINFL_MAX_HUFF_TABLES];
168 mz_uint8 m_raw_header[4], m_len_codes[TINFL_MAX_HUFF_SYMBOLS_0 + TINFL_MAX_HUFF_SYMBOLS_1 + 137];
169 };
170
171 #endif // #ifdef TINFL_HEADER_INCLUDED
172
173 // ------------------- End of Header: Implementation follows. (If you only want the header, define MINIZ_HEADER_FILE_ONLY.)
174
175 #ifndef TINFL_HEADER_FILE_ONLY
176
177 #include "pub_core_mallocfree.h"
178 #include "pub_core_libcbase.h"
179
180 #define MZ_MAX(a,b) (((a)>(b))?(a):(b))
181 #define MZ_MIN(a,b) (((a)<(b))?(a):(b))
182 #define MZ_CLEAR_OBJ(obj) VG_(memset)(&(obj), 0, sizeof(obj))
183
184 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES && MINIZ_LITTLE_ENDIAN
185 #define MZ_READ_LE16(p) *((const mz_uint16 *)(p))
186 #define MZ_READ_LE32(p) *((const mz_uint32 *)(p))
187 #else
188 #define MZ_READ_LE16(p) ((mz_uint32)(((const mz_uint8 *)(p))[0]) | ((mz_uint32)(((const mz_uint8 *)(p))[1]) << 8U))
189 #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))
190 #endif
191
192 #define TINFL_MEMCPY(d, s, l) VG_(memcpy)(d, s, l)
193 #define TINFL_MEMSET(p, c, l) VG_(memset)(p, c, l)
194
195 #define TINFL_CR_BEGIN switch(r->m_state) { case 0:
196 #define TINFL_CR_RETURN(state_index, result) do { status = result; r->m_state = state_index; goto common_exit; case state_index:; } MZ_MACRO_END
197 #define TINFL_CR_RETURN_FOREVER(state_index, result) do { for ( ; ; ) { TINFL_CR_RETURN(state_index, result); } } MZ_MACRO_END
198 #define TINFL_CR_FINISH }
199
200 // TODO: If the caller has indicated that there's no more input, and we attempt to read beyond the input buf, then something is wrong with the input because the inflator never
201 // reads ahead more than it needs to. Currently TINFL_GET_BYTE() pads the end of the stream with 0's in this scenario.
202 #define TINFL_GET_BYTE(state_index, c) do { \
203 if (pIn_buf_cur >= pIn_buf_end) { \
204 for ( ; ; ) { \
205 if (decomp_flags & TINFL_FLAG_HAS_MORE_INPUT) { \
206 TINFL_CR_RETURN(state_index, TINFL_STATUS_NEEDS_MORE_INPUT); \
207 if (pIn_buf_cur < pIn_buf_end) { \
208 c = *pIn_buf_cur++; \
209 break; \
210 } \
211 } else { \
212 c = 0; \
213 break; \
214 } \
215 } \
216 } else c = *pIn_buf_cur++; } MZ_MACRO_END
217
218 #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))
219 #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
220 #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
221
222 // TINFL_HUFF_BITBUF_FILL() is only used rarely, when the number of bytes remaining in the input buffer falls below 2.
223 // 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
224 // 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
225 // bit buffer contains >=15 bits (deflate's max. Huffman code size).
226 #define TINFL_HUFF_BITBUF_FILL(state_index, pHuff) \
227 do { \
228 temp = (pHuff)->m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]; \
229 if (temp >= 0) { \
230 code_len = temp >> 9; \
231 if ((code_len) && (num_bits >= code_len)) \
232 break; \
233 } else if (num_bits > TINFL_FAST_LOOKUP_BITS) { \
234 code_len = TINFL_FAST_LOOKUP_BITS; \
235 do { \
236 temp = (pHuff)->m_tree[~temp + ((bit_buf >> code_len++) & 1)]; \
237 } while ((temp < 0) && (num_bits >= (code_len + 1))); if (temp >= 0) break; \
238 } TINFL_GET_BYTE(state_index, c); bit_buf |= (((tinfl_bit_buf_t)c) << num_bits); num_bits += 8; \
239 } while (num_bits < 15);
240
241 // 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
242 // 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
243 // 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.
244 // The slow path is only executed at the very end of the input buffer.
245 #define TINFL_HUFF_DECODE(state_index, sym, pHuff) do { \
246 int temp; mz_uint code_len, c; \
247 if (num_bits < 15) { \
248 if ((pIn_buf_end - pIn_buf_cur) < 2) { \
249 TINFL_HUFF_BITBUF_FILL(state_index, pHuff); \
250 } else { \
251 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; \
252 } \
253 } \
254 if ((temp = (pHuff)->m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0) \
255 code_len = temp >> 9, temp &= 511; \
256 else { \
257 code_len = TINFL_FAST_LOOKUP_BITS; do { temp = (pHuff)->m_tree[~temp + ((bit_buf >> code_len++) & 1)]; } while (temp < 0); \
258 } sym = temp; bit_buf >>= code_len; num_bits -= code_len; } MZ_MACRO_END
259
tinfl_decompress(tinfl_decompressor * r,const mz_uint8 * pIn_buf_next,SizeT * pIn_buf_size,mz_uint8 * pOut_buf_start,mz_uint8 * pOut_buf_next,SizeT * pOut_buf_size,const mz_uint32 decomp_flags)260 tinfl_status tinfl_decompress(tinfl_decompressor *r, const mz_uint8 *pIn_buf_next, SizeT *pIn_buf_size, mz_uint8 *pOut_buf_start, mz_uint8 *pOut_buf_next, SizeT *pOut_buf_size, const mz_uint32 decomp_flags)
261 {
262 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 };
263 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 };
264 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};
265 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};
266 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 };
267 static const int s_min_table_sizes[3] = { 257, 1, 4 };
268
269 tinfl_status status = TINFL_STATUS_FAILED; mz_uint32 num_bits, dist, counter, num_extra; tinfl_bit_buf_t bit_buf;
270 const mz_uint8 *pIn_buf_cur = pIn_buf_next, *const pIn_buf_end = pIn_buf_next + *pIn_buf_size;
271 mz_uint8 *pOut_buf_cur = pOut_buf_next, *const pOut_buf_end = pOut_buf_next + *pOut_buf_size;
272 SizeT out_buf_size_mask = (decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF) ? (SizeT)-1 : ((pOut_buf_next - pOut_buf_start) + *pOut_buf_size) - 1, dist_from_out_buf_start;
273
274 // 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).
275 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; }
276
277 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;
278 TINFL_CR_BEGIN
279
280 bit_buf = num_bits = dist = counter = num_extra = r->m_zhdr0 = r->m_zhdr1 = 0; r->m_z_adler32 = r->m_check_adler32 = 1;
281 if (decomp_flags & TINFL_FLAG_PARSE_ZLIB_HEADER)
282 {
283 TINFL_GET_BYTE(1, r->m_zhdr0); TINFL_GET_BYTE(2, r->m_zhdr1);
284 counter = (((r->m_zhdr0 * 256 + r->m_zhdr1) % 31 != 0) || (r->m_zhdr1 & 32) || ((r->m_zhdr0 & 15) != 8));
285 if (!(decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF)) counter |= (((1U << (8U + (r->m_zhdr0 >> 4))) > 32768U) || ((out_buf_size_mask + 1) < (SizeT)(1U << (8U + (r->m_zhdr0 >> 4)))));
286 if (counter) { TINFL_CR_RETURN_FOREVER(36, TINFL_STATUS_FAILED); }
287 }
288
289 do
290 {
291 TINFL_GET_BITS(3, r->m_final, 3); r->m_type = r->m_final >> 1;
292 if (r->m_type == 0)
293 {
294 TINFL_SKIP_BITS(5, num_bits & 7);
295 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]); }
296 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); }
297 while ((counter) && (num_bits))
298 {
299 TINFL_GET_BITS(51, dist, 8);
300 while (pOut_buf_cur >= pOut_buf_end) { TINFL_CR_RETURN(52, TINFL_STATUS_HAS_MORE_OUTPUT); }
301 *pOut_buf_cur++ = (mz_uint8)dist;
302 counter--;
303 }
304 while (counter)
305 {
306 SizeT n; while (pOut_buf_cur >= pOut_buf_end) { TINFL_CR_RETURN(9, TINFL_STATUS_HAS_MORE_OUTPUT); }
307 while (pIn_buf_cur >= pIn_buf_end)
308 {
309 if (decomp_flags & TINFL_FLAG_HAS_MORE_INPUT)
310 {
311 TINFL_CR_RETURN(38, TINFL_STATUS_NEEDS_MORE_INPUT);
312 }
313 else
314 {
315 TINFL_CR_RETURN_FOREVER(40, TINFL_STATUS_FAILED);
316 }
317 }
318 n = MZ_MIN(MZ_MIN((SizeT)(pOut_buf_end - pOut_buf_cur), (SizeT)(pIn_buf_end - pIn_buf_cur)), counter);
319 TINFL_MEMCPY(pOut_buf_cur, pIn_buf_cur, n); pIn_buf_cur += n; pOut_buf_cur += n; counter -= (mz_uint)n;
320 }
321 }
322 else if (r->m_type == 3)
323 {
324 TINFL_CR_RETURN_FOREVER(10, TINFL_STATUS_FAILED);
325 }
326 else
327 {
328 if (r->m_type == 1)
329 {
330 mz_uint8 *p = r->m_tables[0].m_code_size; mz_uint i;
331 r->m_table_sizes[0] = 288; r->m_table_sizes[1] = 32; TINFL_MEMSET(r->m_tables[1].m_code_size, 5, 32);
332 for ( i = 0; i <= 143; ++i) *p++ = 8;
333 for ( ; i <= 255; ++i) *p++ = 9;
334 for ( ; i <= 279; ++i) *p++ = 7;
335 for ( ; i <= 287; ++i) *p++ = 8;
336 }
337 else
338 {
339 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]; }
340 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; }
341 r->m_table_sizes[2] = 19;
342 }
343 for ( ; (int)r->m_type >= 0; r->m_type--)
344 {
345 int tree_next, tree_cur; tinfl_huff_table *pTable;
346 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);
347 for (i = 0; i < r->m_table_sizes[r->m_type]; ++i) total_syms[pTable->m_code_size[i]]++;
348 used_syms = 0, total = 0; next_code[0] = next_code[1] = 0;
349 for (i = 1; i <= 15; ++i) { used_syms += total_syms[i]; next_code[i + 1] = (total = ((total + total_syms[i]) << 1)); }
350 if ((65536 != total) && (used_syms > 1))
351 {
352 TINFL_CR_RETURN_FOREVER(35, TINFL_STATUS_FAILED);
353 }
354 for (tree_next = -1, sym_index = 0; sym_index < r->m_table_sizes[r->m_type]; ++sym_index)
355 {
356 mz_uint rev_code = 0, l, cur_code, code_size = pTable->m_code_size[sym_index]; if (!code_size) continue;
357 cur_code = next_code[code_size]++; for (l = code_size; l > 0; l--, cur_code >>= 1) rev_code = (rev_code << 1) | (cur_code & 1);
358 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; }
359 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; }
360 rev_code >>= (TINFL_FAST_LOOKUP_BITS - 1);
361 for (j = code_size; j > (TINFL_FAST_LOOKUP_BITS + 1); j--)
362 {
363 tree_cur -= ((rev_code >>= 1) & 1);
364 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];
365 }
366 tree_cur -= ((rev_code >>= 1) & 1); pTable->m_tree[-tree_cur - 1] = (mz_int16)sym_index;
367 }
368 if (r->m_type == 2)
369 {
370 for (counter = 0; counter < (r->m_table_sizes[0] + r->m_table_sizes[1]); )
371 {
372 mz_uint s; TINFL_HUFF_DECODE(16, dist, &r->m_tables[2]); if (dist < 16) { r->m_len_codes[counter++] = (mz_uint8)dist; continue; }
373 if ((dist == 16) && (!counter))
374 {
375 TINFL_CR_RETURN_FOREVER(17, TINFL_STATUS_FAILED);
376 }
377 num_extra = "\02\03\07"[dist - 16]; TINFL_GET_BITS(18, s, num_extra); s += "\03\03\013"[dist - 16];
378 TINFL_MEMSET(r->m_len_codes + counter, (dist == 16) ? r->m_len_codes[counter - 1] : 0, s); counter += s;
379 }
380 if ((r->m_table_sizes[0] + r->m_table_sizes[1]) != counter)
381 {
382 TINFL_CR_RETURN_FOREVER(21, TINFL_STATUS_FAILED);
383 }
384 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]);
385 }
386 }
387 for ( ; ; )
388 {
389 mz_uint8 *pSrc;
390 for ( ; ; )
391 {
392 if (((pIn_buf_end - pIn_buf_cur) < 4) || ((pOut_buf_end - pOut_buf_cur) < 2))
393 {
394 TINFL_HUFF_DECODE(23, counter, &r->m_tables[0]);
395 if (counter >= 256)
396 break;
397 while (pOut_buf_cur >= pOut_buf_end) { TINFL_CR_RETURN(24, TINFL_STATUS_HAS_MORE_OUTPUT); }
398 *pOut_buf_cur++ = (mz_uint8)counter;
399 }
400 else
401 {
402 int sym2; mz_uint code_len;
403 #if TINFL_USE_64BIT_BITBUF
404 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; }
405 #else
406 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; }
407 #endif
408 if ((sym2 = r->m_tables[0].m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0)
409 code_len = sym2 >> 9;
410 else
411 {
412 code_len = TINFL_FAST_LOOKUP_BITS; do { sym2 = r->m_tables[0].m_tree[~sym2 + ((bit_buf >> code_len++) & 1)]; } while (sym2 < 0);
413 }
414 counter = sym2; bit_buf >>= code_len; num_bits -= code_len;
415 if (counter & 256)
416 break;
417
418 #if !TINFL_USE_64BIT_BITBUF
419 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; }
420 #endif
421 if ((sym2 = r->m_tables[0].m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0)
422 code_len = sym2 >> 9;
423 else
424 {
425 code_len = TINFL_FAST_LOOKUP_BITS; do { sym2 = r->m_tables[0].m_tree[~sym2 + ((bit_buf >> code_len++) & 1)]; } while (sym2 < 0);
426 }
427 bit_buf >>= code_len; num_bits -= code_len;
428
429 pOut_buf_cur[0] = (mz_uint8)counter;
430 if (sym2 & 256)
431 {
432 pOut_buf_cur++;
433 counter = sym2;
434 break;
435 }
436 pOut_buf_cur[1] = (mz_uint8)sym2;
437 pOut_buf_cur += 2;
438 }
439 }
440 if ((counter &= 511) == 256) break;
441
442 num_extra = s_length_extra[counter - 257]; counter = s_length_base[counter - 257];
443 if (num_extra) { mz_uint extra_bits; TINFL_GET_BITS(25, extra_bits, num_extra); counter += extra_bits; }
444
445 TINFL_HUFF_DECODE(26, dist, &r->m_tables[1]);
446 num_extra = s_dist_extra[dist]; dist = s_dist_base[dist];
447 if (num_extra) { mz_uint extra_bits; TINFL_GET_BITS(27, extra_bits, num_extra); dist += extra_bits; }
448
449 dist_from_out_buf_start = pOut_buf_cur - pOut_buf_start;
450 if ((dist > dist_from_out_buf_start) && (decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF))
451 {
452 TINFL_CR_RETURN_FOREVER(37, TINFL_STATUS_FAILED);
453 }
454
455 pSrc = pOut_buf_start + ((dist_from_out_buf_start - dist) & out_buf_size_mask);
456
457 if ((MZ_MAX(pOut_buf_cur, pSrc) + counter) > pOut_buf_end)
458 {
459 while (counter--)
460 {
461 while (pOut_buf_cur >= pOut_buf_end) { TINFL_CR_RETURN(53, TINFL_STATUS_HAS_MORE_OUTPUT); }
462 *pOut_buf_cur++ = pOut_buf_start[(dist_from_out_buf_start++ - dist) & out_buf_size_mask];
463 }
464 continue;
465 }
466 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES
467 else if ((counter >= 9) && (counter <= dist))
468 {
469 const mz_uint8 *pSrc_end = pSrc + (counter & ~7);
470 do
471 {
472 ((mz_uint32 *)pOut_buf_cur)[0] = ((const mz_uint32 *)pSrc)[0];
473 ((mz_uint32 *)pOut_buf_cur)[1] = ((const mz_uint32 *)pSrc)[1];
474 pOut_buf_cur += 8;
475 } while ((pSrc += 8) < pSrc_end);
476 if ((counter &= 7) < 3)
477 {
478 if (counter)
479 {
480 pOut_buf_cur[0] = pSrc[0];
481 if (counter > 1)
482 pOut_buf_cur[1] = pSrc[1];
483 pOut_buf_cur += counter;
484 }
485 continue;
486 }
487 }
488 #endif
489 do
490 {
491 pOut_buf_cur[0] = pSrc[0];
492 pOut_buf_cur[1] = pSrc[1];
493 pOut_buf_cur[2] = pSrc[2];
494 pOut_buf_cur += 3; pSrc += 3;
495 } while ((int)(counter -= 3) > 2);
496 if ((int)counter > 0)
497 {
498 pOut_buf_cur[0] = pSrc[0];
499 if ((int)counter > 1)
500 pOut_buf_cur[1] = pSrc[1];
501 pOut_buf_cur += counter;
502 }
503 }
504 }
505 } while (!(r->m_final & 1));
506 if (decomp_flags & TINFL_FLAG_PARSE_ZLIB_HEADER)
507 {
508 TINFL_SKIP_BITS(32, num_bits & 7); 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; }
509 }
510 TINFL_CR_RETURN_FOREVER(34, TINFL_STATUS_DONE);
511 TINFL_CR_FINISH
512
513 common_exit:
514 r->m_num_bits = num_bits; r->m_bit_buf = bit_buf; 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;
515 *pIn_buf_size = pIn_buf_cur - pIn_buf_next; *pOut_buf_size = pOut_buf_cur - pOut_buf_next;
516 if ((decomp_flags & (TINFL_FLAG_PARSE_ZLIB_HEADER | TINFL_FLAG_COMPUTE_ADLER32)) && (status >= 0))
517 {
518 const mz_uint8 *ptr = pOut_buf_next; SizeT buf_len = *pOut_buf_size;
519 mz_uint32 i, s1 = r->m_check_adler32 & 0xffff, s2 = r->m_check_adler32 >> 16; SizeT block_len = buf_len % 5552;
520 while (buf_len)
521 {
522 for (i = 0; i + 7 < block_len; i += 8, ptr += 8)
523 {
524 s1 += ptr[0], s2 += s1; s1 += ptr[1], s2 += s1; s1 += ptr[2], s2 += s1; s1 += ptr[3], s2 += s1;
525 s1 += ptr[4], s2 += s1; s1 += ptr[5], s2 += s1; s1 += ptr[6], s2 += s1; s1 += ptr[7], s2 += s1;
526 }
527 for ( ; i < block_len; ++i) s1 += *ptr++, s2 += s1;
528 s1 %= 65521U, s2 %= 65521U; buf_len -= block_len; block_len = 5552;
529 }
530 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;
531 }
532 return status;
533 }
534
535 // Higher level helper functions.
tinfl_decompress_mem_to_heap(const void * pSrc_buf,SizeT src_buf_len,SizeT * pOut_len,int flags)536 void *tinfl_decompress_mem_to_heap(const void *pSrc_buf, SizeT src_buf_len, SizeT *pOut_len, int flags)
537 {
538 tinfl_decompressor decomp; void *pBuf = NULL, *pNew_buf; SizeT src_buf_ofs = 0, out_buf_capacity = 0;
539 *pOut_len = 0;
540 tinfl_init(&decomp);
541 for ( ; ; )
542 {
543 SizeT src_buf_size = src_buf_len - src_buf_ofs, dst_buf_size = out_buf_capacity - *pOut_len, new_out_buf_capacity;
544 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,
545 (flags & ~TINFL_FLAG_HAS_MORE_INPUT) | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF);
546 if ((status < 0) || (status == TINFL_STATUS_NEEDS_MORE_INPUT))
547 {
548 VG_(free)(pBuf); *pOut_len = 0; return NULL;
549 }
550 src_buf_ofs += src_buf_size;
551 *pOut_len += dst_buf_size;
552 if (status == TINFL_STATUS_DONE) break;
553 new_out_buf_capacity = out_buf_capacity * 2; if (new_out_buf_capacity < 128) new_out_buf_capacity = 128;
554 pNew_buf = VG_(realloc)("tinfl.tinfl_decompress_mem_to_heap.1", pBuf, new_out_buf_capacity);
555 if (!pNew_buf)
556 {
557 VG_(free)(pBuf); *pOut_len = 0; return NULL;
558 }
559 pBuf = pNew_buf; out_buf_capacity = new_out_buf_capacity;
560 }
561 return pBuf;
562 }
563
tinfl_decompress_mem_to_mem(void * pOut_buf,SizeT out_buf_len,const void * pSrc_buf,SizeT src_buf_len,int flags)564 SizeT tinfl_decompress_mem_to_mem(void *pOut_buf, SizeT out_buf_len, const void *pSrc_buf, SizeT src_buf_len, int flags)
565 {
566 tinfl_decompressor decomp; tinfl_status status; tinfl_init(&decomp);
567 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);
568 return (status != TINFL_STATUS_DONE) ? TINFL_DECOMPRESS_MEM_TO_MEM_FAILED : out_buf_len;
569 }
570
tinfl_decompress_mem_to_callback(const void * pIn_buf,SizeT * pIn_buf_size,tinfl_put_buf_func_ptr pPut_buf_func,void * pPut_buf_user,int flags)571 int tinfl_decompress_mem_to_callback(const void *pIn_buf, SizeT *pIn_buf_size, tinfl_put_buf_func_ptr pPut_buf_func, void *pPut_buf_user, int flags)
572 {
573 int result = 0;
574 tinfl_decompressor decomp;
575 mz_uint8 *pDict = (mz_uint8*)VG_(malloc)("tinfl.tinfl_decompress_mem_to_callback.1", TINFL_LZ_DICT_SIZE); SizeT in_buf_ofs = 0, dict_ofs = 0;
576 if (!pDict)
577 return TINFL_STATUS_FAILED;
578 tinfl_init(&decomp);
579 for ( ; ; )
580 {
581 SizeT in_buf_size = *pIn_buf_size - in_buf_ofs, dst_buf_size = TINFL_LZ_DICT_SIZE - dict_ofs;
582 tinfl_status status = tinfl_decompress(&decomp, (const mz_uint8*)pIn_buf + in_buf_ofs, &in_buf_size, pDict, pDict + dict_ofs, &dst_buf_size,
583 (flags & ~(TINFL_FLAG_HAS_MORE_INPUT | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF)));
584 in_buf_ofs += in_buf_size;
585 if ((dst_buf_size) && (!(*pPut_buf_func)(pDict + dict_ofs, (int)dst_buf_size, pPut_buf_user)))
586 break;
587 if (status != TINFL_STATUS_HAS_MORE_OUTPUT)
588 {
589 result = (status == TINFL_STATUS_DONE);
590 break;
591 }
592 dict_ofs = (dict_ofs + dst_buf_size) & (TINFL_LZ_DICT_SIZE - 1);
593 }
594 VG_(free)(pDict);
595 *pIn_buf_size = in_buf_ofs;
596 return result;
597 }
598
599 #endif // #ifndef TINFL_HEADER_FILE_ONLY
600