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