coregrind/m_debuginfo/tinfl.c

   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
 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