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 (at) 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 (at) 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 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. 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 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 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
