git.cworth.org Git - vogl/blob - src/voglcore/vogl_miniz.cpp

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_miniz.cpp
  28 #include "vogl_core.h"
  29 #include "vogl_miniz.h"
  30
  31 typedef unsigned char mz_validate_uint16[sizeof(mz_uint16) == 2 ? 1 : -1];
  32 typedef unsigned char mz_validate_uint32[sizeof(mz_uint32) == 4 ? 1 : -1];
  33 typedef unsigned char mz_validate_uint64[sizeof(mz_uint64) == 8 ? 1 : -1];
  34
  35 #ifdef __cplusplus
  36 extern "C" {
  37 #endif
  38
  39 // ------------------- zlib-style API's
  40
  41 mz_ulong mz_adler32(mz_ulong adler, const unsigned char *ptr, size_t buf_len)
  42 {
  43     mz_uint32 i, s1 = (mz_uint32)(adler & 0xffff), s2 = (mz_uint32)(adler >> 16);
  44     size_t block_len = buf_len % 5552;
  45     if (!ptr)
  46         return MZ_ADLER32_INIT;
  47     while (buf_len)
  48     {
  49         for (i = 0; i + 7 < block_len; i += 8, ptr += 8)
  50         {
  51             s1 += ptr[0], s2 += s1;
  52             s1 += ptr[1], s2 += s1;
  53             s1 += ptr[2], s2 += s1;
  54             s1 += ptr[3], s2 += s1;
  55             s1 += ptr[4], s2 += s1;
  56             s1 += ptr[5], s2 += s1;
  57             s1 += ptr[6], s2 += s1;
  58             s1 += ptr[7], s2 += s1;
  59         }
  60         for (; i < block_len; ++i)
  61             s1 += *ptr++, s2 += s1;
  62         s1 %= 65521U, s2 %= 65521U;
  63         buf_len -= block_len;
  64         block_len = 5552;
  65     }
  66     return (s2 << 16) + s1;
  67 }
  68
  69 // Karl Malbrain's compact CRC-32. See "A compact CCITT crc16 and crc32 C implementation that balances processor cache usage against speed": http://www.geocities.com/malbrain/
  70 #if 0
  71         mz_ulong mz_crc32(mz_ulong crc, const mz_uint8 *ptr, size_t buf_len)
  72         {
  73                 static const mz_uint32 s_crc32[16] =
  74                 {
  75                         0, 0x1db71064, 0x3b6e20c8, 0x26d930ac, 0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,
  76                         0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c, 0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c
  77                 };
  78                 mz_uint32 crcu32 = (mz_uint32)crc;
  79                 if (!ptr) return MZ_CRC32_INIT;
  80                 crcu32 = ~crcu32;
  81                 while (buf_len--)
  82                 {
  83                         mz_uint8 b = *ptr++;
  84                         crcu32 = (crcu32 >> 4) ^ s_crc32[(crcu32 & 0xF) ^ (b & 0xF)];
  85                         crcu32 = (crcu32 >> 4) ^ s_crc32[(crcu32 & 0xF) ^ (b >> 4)];
  86                 }
  87                 return ~crcu32;
  88         }
  89 #else
  90 // Faster, but larger CPU cache footprint.
  91 mz_ulong mz_crc32(mz_ulong crc, const mz_uint8 *ptr, size_t buf_len)
  92 {
  93     static const mz_uint32 s_crc_table[256] =
  94         {
  95             0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535,
  96             0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD,
  97             0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D,
  98             0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
  99             0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,
 100             0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
 101             0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC,
 102             0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
 103             0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB,
 104             0xB6662D3D, 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F,
 105             0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB,
 106             0x086D3D2D, 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
 107             0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA,
 108             0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 0x4DB26158, 0x3AB551CE,
 109             0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A,
 110             0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
 111             0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409,
 112             0xCE61E49F, 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
 113             0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739,
 114             0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
 115             0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344, 0x8708A3D2, 0x1E01F268,
 116             0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0,
 117             0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8,
 118             0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
 119             0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF,
 120             0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703,
 121             0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7,
 122             0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
 123             0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE,
 124             0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
 125             0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, 0x88085AE6,
 126             0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
 127             0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D,
 128             0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5,
 129             0x47B2CF7F, 0x30B5FFE9, 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605,
 130             0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
 131             0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
 132         };
 133
 134     mz_uint32 crc32 = (mz_uint32)crc ^ 0xFFFFFFFF;
 135     const mz_uint8 *pByte_buf = (const mz_uint8 *)ptr;
 136
 137     while (buf_len >= 4)
 138     {
 139         crc32 = (crc32 >> 8) ^ s_crc_table[(crc32 ^ pByte_buf[0]) & 0xFF];
 140         crc32 = (crc32 >> 8) ^ s_crc_table[(crc32 ^ pByte_buf[1]) & 0xFF];
 141         crc32 = (crc32 >> 8) ^ s_crc_table[(crc32 ^ pByte_buf[2]) & 0xFF];
 142         crc32 = (crc32 >> 8) ^ s_crc_table[(crc32 ^ pByte_buf[3]) & 0xFF];
 143         pByte_buf += 4;
 144         buf_len -= 4;
 145     }
 146
 147     while (buf_len)
 148     {
 149         crc32 = (crc32 >> 8) ^ s_crc_table[(crc32 ^ pByte_buf[0]) & 0xFF];
 150         ++pByte_buf;
 151         --buf_len;
 152     }
 153
 154     return ~crc32;
 155 }
 156 #endif
 157
 158 void mz_free(void *p)
 159 {
 160     MZ_FREE(p);
 161 }
 162
 163 #ifndef MINIZ_NO_ZLIB_APIS
 164
 165 void *miniz_def_alloc_func(void *opaque, size_t items, size_t size)
 166 {
 167     (void)opaque, (void)items, (void)size;
 168     return MZ_MALLOC(items * size);
 169 }
 170 void miniz_def_free_func(void *opaque, void *address)
 171 {
 172     (void)opaque, (void)address;
 173     MZ_FREE(address);
 174 }
 175 void *miniz_def_realloc_func(void *opaque, void *address, size_t items, size_t size)
 176 {
 177     (void)opaque, (void)address, (void)items, (void)size;
 178     return MZ_REALLOC(address, items * size);
 179 }
 180
 181 const char *mz_version(void)
 182 {
 183     return MZ_VERSION;
 184 }
 185
 186 int mz_deflateInit(mz_streamp pStream, int level)
 187 {
 188     return mz_deflateInit2(pStream, level, MZ_DEFLATED, MZ_DEFAULT_WINDOW_BITS, 9, MZ_DEFAULT_STRATEGY);
 189 }
 190
 191 int mz_deflateInit2(mz_streamp pStream, int level, int method, int window_bits, int mem_level, int strategy)
 192 {
 193     tdefl_compressor *pComp;
 194     mz_uint comp_flags = TDEFL_COMPUTE_ADLER32 | tdefl_create_comp_flags_from_zip_params(level, window_bits, strategy);
 195
 196     if (!pStream)
 197         return MZ_STREAM_ERROR;
 198     if ((method != MZ_DEFLATED) || ((mem_level < 1) || (mem_level > 9)) || ((window_bits != MZ_DEFAULT_WINDOW_BITS) && (-window_bits != MZ_DEFAULT_WINDOW_BITS)))
 199         return MZ_PARAM_ERROR;
 200
 201     pStream->data_type = 0;
 202     pStream->adler = MZ_ADLER32_INIT;
 203     pStream->msg = NULL;
 204     pStream->reserved = 0;
 205     pStream->total_in = 0;
 206     pStream->total_out = 0;
 207     if (!pStream->zalloc)
 208         pStream->zalloc = miniz_def_alloc_func;
 209     if (!pStream->zfree)
 210         pStream->zfree = miniz_def_free_func;
 211
 212     pComp = (tdefl_compressor *)pStream->zalloc(pStream->opaque, 1, sizeof(tdefl_compressor));
 213     if (!pComp)
 214         return MZ_MEM_ERROR;
 215
 216     pStream->state = (struct mz_internal_state *)pComp;
 217
 218     if (tdefl_init(pComp, NULL, NULL, comp_flags) != TDEFL_STATUS_OKAY)
 219     {
 220         mz_deflateEnd(pStream);
 221         return MZ_PARAM_ERROR;
 222     }
 223
 224     return MZ_OK;
 225 }
 226
 227 int mz_deflateReset(mz_streamp pStream)
 228 {
 229     if ((!pStream) || (!pStream->state) || (!pStream->zalloc) || (!pStream->zfree))
 230         return MZ_STREAM_ERROR;
 231     pStream->total_in = pStream->total_out = 0;
 232     tdefl_init((tdefl_compressor *)pStream->state, NULL, NULL, ((tdefl_compressor *)pStream->state)->m_flags);
 233     return MZ_OK;
 234 }
 235
 236 int mz_deflate(mz_streamp pStream, int flush)
 237 {
 238     size_t in_bytes, out_bytes;
 239     mz_ulong orig_total_in, orig_total_out;
 240     int mz_status = MZ_OK;
 241
 242     if ((!pStream) || (!pStream->state) || (flush < 0) || (flush > MZ_FINISH) || (!pStream->next_out))
 243         return MZ_STREAM_ERROR;
 244     if (!pStream->avail_out)
 245         return MZ_BUF_ERROR;
 246
 247     if (flush == MZ_PARTIAL_FLUSH)
 248         flush = MZ_SYNC_FLUSH;
 249
 250     if (((tdefl_compressor *)pStream->state)->m_prev_return_status == TDEFL_STATUS_DONE)
 251         return (flush == MZ_FINISH) ? MZ_STREAM_END : MZ_BUF_ERROR;
 252
 253     orig_total_in = pStream->total_in;
 254     orig_total_out = pStream->total_out;
 255     for (;;)
 256     {
 257         tdefl_status defl_status;
 258         in_bytes = pStream->avail_in;
 259         out_bytes = pStream->avail_out;
 260
 261         defl_status = tdefl_compress((tdefl_compressor *)pStream->state, pStream->next_in, &in_bytes, pStream->next_out, &out_bytes, (tdefl_flush)flush);
 262         pStream->next_in += (mz_uint)in_bytes;
 263         pStream->avail_in -= (mz_uint)in_bytes;
 264         pStream->total_in += (mz_uint)in_bytes;
 265         pStream->adler = tdefl_get_adler32((tdefl_compressor *)pStream->state);
 266
 267         pStream->next_out += (mz_uint)out_bytes;
 268         pStream->avail_out -= (mz_uint)out_bytes;
 269         pStream->total_out += (mz_uint)out_bytes;
 270
 271         if (defl_status < 0)
 272         {
 273             mz_status = MZ_STREAM_ERROR;
 274             break;
 275         }
 276         else if (defl_status == TDEFL_STATUS_DONE)
 277         {
 278             mz_status = MZ_STREAM_END;
 279             break;
 280         }
 281         else if (!pStream->avail_out)
 282             break;
 283         else if ((!pStream->avail_in) && (flush != MZ_FINISH))
 284         {
 285             if ((flush) || (pStream->total_in != orig_total_in) || (pStream->total_out != orig_total_out))
 286                 break;
 287             return MZ_BUF_ERROR; // Can't make forward progress without some input.
 288         }
 289     }
 290     return mz_status;
 291 }
 292
 293 int mz_deflateEnd(mz_streamp pStream)
 294 {
 295     if (!pStream)
 296         return MZ_STREAM_ERROR;
 297     if (pStream->state)
 298     {
 299         pStream->zfree(pStream->opaque, pStream->state);
 300         pStream->state = NULL;
 301     }
 302     return MZ_OK;
 303 }
 304
 305 mz_ulong mz_deflateBound(mz_streamp pStream, mz_ulong source_len)
 306 {
 307     (void)pStream;
 308     // This is really over conservative. (And lame, but it's actually pretty tricky to compute a true upper bound given the way tdefl's blocking works.)
 309     return MZ_MAX(128 + (source_len * 110) / 100, 128 + source_len + ((source_len / (31 * 1024)) + 1) * 5);
 310 }
 311
 312 int mz_compress2(unsigned char *pDest, mz_ulong *pDest_len, const unsigned char *pSource, mz_ulong source_len, int level)
 313 {
 314     int status;
 315     mz_stream stream;
 316     memset(&stream, 0, sizeof(stream));
 317
 318     // In case mz_ulong is 64-bits (argh I hate longs).
 319     if ((source_len | *pDest_len) > 0xFFFFFFFFU)
 320         return MZ_PARAM_ERROR;
 321
 322     stream.next_in = pSource;
 323     stream.avail_in = (mz_uint32)source_len;
 324     stream.next_out = pDest;
 325     stream.avail_out = (mz_uint32) * pDest_len;
 326
 327     status = mz_deflateInit(&stream, level);
 328     if (status != MZ_OK)
 329         return status;
 330
 331     status = mz_deflate(&stream, MZ_FINISH);
 332     if (status != MZ_STREAM_END)
 333     {
 334         mz_deflateEnd(&stream);
 335         return (status == MZ_OK) ? MZ_BUF_ERROR : status;
 336     }
 337
 338     *pDest_len = stream.total_out;
 339     return mz_deflateEnd(&stream);
 340 }
 341
 342 int mz_compress(unsigned char *pDest, mz_ulong *pDest_len, const unsigned char *pSource, mz_ulong source_len)
 343 {
 344     return mz_compress2(pDest, pDest_len, pSource, source_len, MZ_DEFAULT_COMPRESSION);
 345 }
 346
 347 mz_ulong mz_compressBound(mz_ulong source_len)
 348 {
 349     return mz_deflateBound(NULL, source_len);
 350 }
 351
 352 typedef struct
 353 {
 354     tinfl_decompressor m_decomp;
 355     mz_uint m_dict_ofs, m_dict_avail, m_first_call, m_has_flushed;
 356     int m_window_bits;
 357     mz_uint8 m_dict[TINFL_LZ_DICT_SIZE];
 358     tinfl_status m_last_status;
 359 } inflate_state;
 360
 361 int mz_inflateInit2(mz_streamp pStream, int window_bits)
 362 {
 363     inflate_state *pDecomp;
 364     if (!pStream)
 365         return MZ_STREAM_ERROR;
 366     if ((window_bits != MZ_DEFAULT_WINDOW_BITS) && (-window_bits != MZ_DEFAULT_WINDOW_BITS))
 367         return MZ_PARAM_ERROR;
 368
 369     pStream->data_type = 0;
 370     pStream->adler = 0;
 371     pStream->msg = NULL;
 372     pStream->total_in = 0;
 373     pStream->total_out = 0;
 374     pStream->reserved = 0;
 375     if (!pStream->zalloc)
 376         pStream->zalloc = miniz_def_alloc_func;
 377     if (!pStream->zfree)
 378         pStream->zfree = miniz_def_free_func;
 379
 380     pDecomp = (inflate_state *)pStream->zalloc(pStream->opaque, 1, sizeof(inflate_state));
 381     if (!pDecomp)
 382         return MZ_MEM_ERROR;
 383
 384     pStream->state = (struct mz_internal_state *)pDecomp;
 385
 386     tinfl_init(&pDecomp->m_decomp);
 387     pDecomp->m_dict_ofs = 0;
 388     pDecomp->m_dict_avail = 0;
 389     pDecomp->m_last_status = TINFL_STATUS_NEEDS_MORE_INPUT;
 390     pDecomp->m_first_call = 1;
 391     pDecomp->m_has_flushed = 0;
 392     pDecomp->m_window_bits = window_bits;
 393
 394     return MZ_OK;
 395 }
 396
 397 int mz_inflateInit(mz_streamp pStream)
 398 {
 399     return mz_inflateInit2(pStream, MZ_DEFAULT_WINDOW_BITS);
 400 }
 401
 402 int mz_inflate(mz_streamp pStream, int flush)
 403 {
 404     inflate_state *pState;
 405     mz_uint n, first_call, decomp_flags = TINFL_FLAG_COMPUTE_ADLER32;
 406     size_t in_bytes, out_bytes, orig_avail_in;
 407     tinfl_status status;
 408
 409     if ((!pStream) || (!pStream->state))
 410         return MZ_STREAM_ERROR;
 411     if (flush == MZ_PARTIAL_FLUSH)
 412         flush = MZ_SYNC_FLUSH;
 413     if ((flush) && (flush != MZ_SYNC_FLUSH) && (flush != MZ_FINISH))
 414         return MZ_STREAM_ERROR;
 415
 416     pState = (inflate_state *)pStream->state;
 417     if (pState->m_window_bits > 0)
 418         decomp_flags |= TINFL_FLAG_PARSE_ZLIB_HEADER;
 419     orig_avail_in = pStream->avail_in;
 420
 421     first_call = pState->m_first_call;
 422     pState->m_first_call = 0;
 423     if (pState->m_last_status < 0)
 424         return MZ_DATA_ERROR;
 425
 426     if (pState->m_has_flushed && (flush != MZ_FINISH))
 427         return MZ_STREAM_ERROR;
 428     pState->m_has_flushed |= (flush == MZ_FINISH);
 429
 430     if ((flush == MZ_FINISH) && (first_call))
 431     {
 432         // MZ_FINISH on the first call implies that the input and output buffers are large enough to hold the entire compressed/decompressed file.
 433         decomp_flags |= TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF;
 434         in_bytes = pStream->avail_in;
 435         out_bytes = pStream->avail_out;
 436         status = tinfl_decompress(&pState->m_decomp, pStream->next_in, &in_bytes, pStream->next_out, pStream->next_out, &out_bytes, decomp_flags);
 437         pState->m_last_status = status;
 438         pStream->next_in += (mz_uint)in_bytes;
 439         pStream->avail_in -= (mz_uint)in_bytes;
 440         pStream->total_in += (mz_uint)in_bytes;
 441         pStream->adler = tinfl_get_adler32(&pState->m_decomp);
 442         pStream->next_out += (mz_uint)out_bytes;
 443         pStream->avail_out -= (mz_uint)out_bytes;
 444         pStream->total_out += (mz_uint)out_bytes;
 445
 446         if (status < 0)
 447             return MZ_DATA_ERROR;
 448         else if (status != TINFL_STATUS_DONE)
 449         {
 450             pState->m_last_status = TINFL_STATUS_FAILED;
 451             return MZ_BUF_ERROR;
 452         }
 453         return MZ_STREAM_END;
 454     }
 455     // flush != MZ_FINISH then we must assume there's more input.
 456     if (flush != MZ_FINISH)
 457         decomp_flags |= TINFL_FLAG_HAS_MORE_INPUT;
 458
 459     if (pState->m_dict_avail)
 460     {
 461         n = MZ_MIN(pState->m_dict_avail, pStream->avail_out);
 462         memcpy(pStream->next_out, pState->m_dict + pState->m_dict_ofs, n);
 463         pStream->next_out += n;
 464         pStream->avail_out -= n;
 465         pStream->total_out += n;
 466         pState->m_dict_avail -= n;
 467         pState->m_dict_ofs = (pState->m_dict_ofs + n) & (TINFL_LZ_DICT_SIZE - 1);
 468         return ((pState->m_last_status == TINFL_STATUS_DONE) && (!pState->m_dict_avail)) ? MZ_STREAM_END : MZ_OK;
 469     }
 470
 471     for (;;)
 472     {
 473         in_bytes = pStream->avail_in;
 474         out_bytes = TINFL_LZ_DICT_SIZE - pState->m_dict_ofs;
 475
 476         status = tinfl_decompress(&pState->m_decomp, pStream->next_in, &in_bytes, pState->m_dict, pState->m_dict + pState->m_dict_ofs, &out_bytes, decomp_flags);
 477         pState->m_last_status = status;
 478
 479         pStream->next_in += (mz_uint)in_bytes;
 480         pStream->avail_in -= (mz_uint)in_bytes;
 481         pStream->total_in += (mz_uint)in_bytes;
 482         pStream->adler = tinfl_get_adler32(&pState->m_decomp);
 483
 484         pState->m_dict_avail = (mz_uint)out_bytes;
 485
 486         n = MZ_MIN(pState->m_dict_avail, pStream->avail_out);
 487         memcpy(pStream->next_out, pState->m_dict + pState->m_dict_ofs, n);
 488         pStream->next_out += n;
 489         pStream->avail_out -= n;
 490         pStream->total_out += n;
 491         pState->m_dict_avail -= n;
 492         pState->m_dict_ofs = (pState->m_dict_ofs + n) & (TINFL_LZ_DICT_SIZE - 1);
 493
 494         if (status < 0)
 495             return MZ_DATA_ERROR; // Stream is corrupted (there could be some uncompressed data left in the output dictionary - oh well).
 496         else if ((status == TINFL_STATUS_NEEDS_MORE_INPUT) && (!orig_avail_in))
 497             return MZ_BUF_ERROR; // Signal caller that we can't make forward progress without supplying more input or by setting flush to MZ_FINISH.
 498         else if (flush == MZ_FINISH)
 499         {
 500             // The output buffer MUST be large to hold the remaining uncompressed data when flush==MZ_FINISH.
 501             if (status == TINFL_STATUS_DONE)
 502                 return pState->m_dict_avail ? MZ_BUF_ERROR : MZ_STREAM_END;
 503             // status here must be TINFL_STATUS_HAS_MORE_OUTPUT, which means there's at least 1 more byte on the way. If there's no more room left in the output buffer then something is wrong.
 504             else if (!pStream->avail_out)
 505                 return MZ_BUF_ERROR;
 506         }
 507         else if ((status == TINFL_STATUS_DONE) || (!pStream->avail_in) || (!pStream->avail_out) || (pState->m_dict_avail))
 508             break;
 509     }
 510
 511     return ((status == TINFL_STATUS_DONE) && (!pState->m_dict_avail)) ? MZ_STREAM_END : MZ_OK;
 512 }
 513
 514 int mz_inflateEnd(mz_streamp pStream)
 515 {
 516     if (!pStream)
 517         return MZ_STREAM_ERROR;
 518     if (pStream->state)
 519     {
 520         pStream->zfree(pStream->opaque, pStream->state);
 521         pStream->state = NULL;
 522     }
 523     return MZ_OK;
 524 }
 525
 526 int mz_uncompress(unsigned char *pDest, mz_ulong *pDest_len, const unsigned char *pSource, mz_ulong source_len)
 527 {
 528     mz_stream stream;
 529     int status;
 530     memset(&stream, 0, sizeof(stream));
 531
 532     // In case mz_ulong is 64-bits (argh I hate longs).
 533     if ((source_len | *pDest_len) > 0xFFFFFFFFU)
 534         return MZ_PARAM_ERROR;
 535
 536     stream.next_in = pSource;
 537     stream.avail_in = (mz_uint32)source_len;
 538     stream.next_out = pDest;
 539     stream.avail_out = (mz_uint32) * pDest_len;
 540
 541     status = mz_inflateInit(&stream);
 542     if (status != MZ_OK)
 543         return status;
 544
 545     status = mz_inflate(&stream, MZ_FINISH);
 546     if (status != MZ_STREAM_END)
 547     {
 548         mz_inflateEnd(&stream);
 549         return ((status == MZ_BUF_ERROR) && (!stream.avail_in)) ? MZ_DATA_ERROR : status;
 550     }
 551     *pDest_len = stream.total_out;
 552
 553     return mz_inflateEnd(&stream);
 554 }
 555
 556 const char *mz_error(int err)
 557 {
 558     static struct
 559     {
 560         int m_err;
 561         const char *m_pDesc;
 562     } s_error_descs[] =
 563           {
 564               { MZ_OK, "" }, { MZ_STREAM_END, "stream end" }, { MZ_NEED_DICT, "need dictionary" }, { MZ_ERRNO, "file error" }, { MZ_STREAM_ERROR, "stream error" },
 565               { MZ_DATA_ERROR, "data error" }, { MZ_MEM_ERROR, "out of memory" }, { MZ_BUF_ERROR, "buf error" }, { MZ_VERSION_ERROR, "version error" }, { MZ_PARAM_ERROR, "parameter error" }
 566           };
 567     mz_uint i;
 568     for (i = 0; i < sizeof(s_error_descs) / sizeof(s_error_descs[0]); ++i)
 569         if (s_error_descs[i].m_err == err)
 570             return s_error_descs[i].m_pDesc;
 571     return NULL;
 572 }
 573
 574 #endif //MINIZ_NO_ZLIB_APIS
 575
 576 // ------------------- Low-level Decompression (completely independent from all compression API's)
 577
 578 #define TINFL_MEMCPY(d, s, l) memcpy(d, s, l)
 579 #define TINFL_MEMSET(p, c, l) memset(p, c, l)
 580
 581 #define TINFL_CR_BEGIN  \
 582     switch (r->m_state) \
 583     {                   \
 584         case 0:
 585 #define TINFL_CR_RETURN(state_index, result) \
 586     do                                       \
 587     {                                        \
 588         status = result;                     \
 589         r->m_state = state_index;            \
 590         goto common_exit;                    \
 591         case state_index:                    \
 592             ;                                \
 593     }                                        \
 594     MZ_MACRO_END
 595 #define TINFL_CR_RETURN_FOREVER(state_index, result) \
 596     do                                               \
 597     {                                                \
 598         for (;;)                                     \
 599         {                                            \
 600             TINFL_CR_RETURN(state_index, result);    \
 601         }                                            \
 602     }                                                \
 603     MZ_MACRO_END
 604 #define TINFL_CR_FINISH }
 605
 606 #define TINFL_GET_BYTE(state_index, c)                                                                                                                          \
 607     do                                                                                                                                                          \
 608     {                                                                                                                                                           \
 609         while (pIn_buf_cur >= pIn_buf_end)                                                                                                                      \
 610         {                                                                                                                                                       \
 611             TINFL_CR_RETURN(state_index, (decomp_flags &TINFL_FLAG_HAS_MORE_INPUT) ? TINFL_STATUS_NEEDS_MORE_INPUT : TINFL_STATUS_FAILED_CANNOT_MAKE_PROGRESS); \
 612         }                                                                                                                                                       \
 613         c = *pIn_buf_cur++;                                                                                                                                     \
 614     }                                                                                                                                                           \
 615     MZ_MACRO_END
 616
 617 #define TINFL_NEED_BITS(state_index, n)                \
 618     do                                                 \
 619     {                                                  \
 620         mz_uint c;                                     \
 621         TINFL_GET_BYTE(state_index, c);                \
 622         bit_buf |= (((tinfl_bit_buf_t)c) << num_bits); \
 623         num_bits += 8;                                 \
 624     } while (num_bits < (mz_uint)(n))
 625 #define TINFL_SKIP_BITS(state_index, n)      \
 626     do                                       \
 627     {                                        \
 628         if (num_bits < (mz_uint)(n))         \
 629         {                                    \
 630             TINFL_NEED_BITS(state_index, n); \
 631         }                                    \
 632         bit_buf >>= (n);                     \
 633         num_bits -= (n);                     \
 634     }                                        \
 635     MZ_MACRO_END
 636 #define TINFL_GET_BITS(state_index, b, n)    \
 637     do                                       \
 638     {                                        \
 639         if (num_bits < (mz_uint)(n))         \
 640         {                                    \
 641             TINFL_NEED_BITS(state_index, n); \
 642         }                                    \
 643         b = bit_buf & ((1 << (n)) - 1);      \
 644         bit_buf >>= (n);                     \
 645         num_bits -= (n);                     \
 646     }                                        \
 647     MZ_MACRO_END
 648
 649 // TINFL_HUFF_BITBUF_FILL() is only used rarely, when the number of bytes remaining in the input buffer falls below 2.
 650 // 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
 651 // 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
 652 // bit buffer contains >=15 bits (deflate's max. Huffman code size).
 653 #define TINFL_HUFF_BITBUF_FILL(state_index, pHuff)                             \
 654     do                                                                         \
 655     {                                                                          \
 656         temp = (pHuff)->m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)];     \
 657         if (temp >= 0)                                                         \
 658         {                                                                      \
 659             code_len = temp >> 9;                                              \
 660             if ((code_len) && (num_bits >= code_len))                          \
 661                 break;                                                         \
 662         }                                                                      \
 663         else if (num_bits > TINFL_FAST_LOOKUP_BITS)                            \
 664         {                                                                      \
 665             code_len = TINFL_FAST_LOOKUP_BITS;                                 \
 666             do                                                                 \
 667             {                                                                  \
 668                 temp = (pHuff)->m_tree[~temp + ((bit_buf >> code_len++) & 1)]; \
 669             } while ((temp < 0) && (num_bits >= (code_len + 1)));              \
 670             if (temp >= 0)                                                     \
 671                 break;                                                         \
 672         }                                                                      \
 673         TINFL_GET_BYTE(state_index, c);                                        \
 674         bit_buf |= (((tinfl_bit_buf_t)c) << num_bits);                         \
 675         num_bits += 8;                                                         \
 676     } while (num_bits < 15);
 677
 678 // 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
 679 // 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
 680 // 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.
 681 // The slow path is only executed at the very end of the input buffer.
 682 // v1.16: The original macro handled the case at the very end of the passed-in input buffer, but we also need to handle the case where the user passes in 1+zillion bytes
 683 // following the deflate data and our non-conservative read-ahead path won't kick in here on this code. This is much trickier.
 684 #define TINFL_HUFF_DECODE(state_index, sym, pHuff)                                                                                  \
 685     do                                                                                                                              \
 686     {                                                                                                                               \
 687         int temp;                                                                                                                   \
 688         mz_uint code_len, c;                                                                                                        \
 689         if (num_bits < 15)                                                                                                          \
 690         {                                                                                                                           \
 691             if ((pIn_buf_end - pIn_buf_cur) < 2)                                                                                    \
 692             {                                                                                                                       \
 693                 TINFL_HUFF_BITBUF_FILL(state_index, pHuff);                                                                         \
 694             }                                                                                                                       \
 695             else                                                                                                                    \
 696             {                                                                                                                       \
 697                 bit_buf |= (((tinfl_bit_buf_t)pIn_buf_cur[0]) << num_bits) | (((tinfl_bit_buf_t)pIn_buf_cur[1]) << (num_bits + 8)); \
 698                 pIn_buf_cur += 2;                                                                                                   \
 699                 num_bits += 16;                                                                                                     \
 700             }                                                                                                                       \
 701         }                                                                                                                           \
 702         if ((temp = (pHuff)->m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0)                                               \
 703             code_len = temp >> 9, temp &= 511;                                                                                      \
 704         else                                                                                                                        \
 705         {                                                                                                                           \
 706             code_len = TINFL_FAST_LOOKUP_BITS;                                                                                      \
 707             do                                                                                                                      \
 708             {                                                                                                                       \
 709                 temp = (pHuff)->m_tree[~temp + ((bit_buf >> code_len++) & 1)];                                                      \
 710             } while (temp < 0);                                                                                                     \
 711         }                                                                                                                           \
 712         sym = temp;                                                                                                                 \
 713         bit_buf >>= code_len;                                                                                                       \
 714         num_bits -= code_len;                                                                                                       \
 715     }                                                                                                                               \
 716     MZ_MACRO_END
 717
 718 tinfl_status tinfl_decompress(tinfl_decompressor *r, const mz_uint8 *pIn_buf_next, size_t *pIn_buf_size, mz_uint8 *pOut_buf_start, mz_uint8 *pOut_buf_next, size_t *pOut_buf_size, const mz_uint32 decomp_flags)
 719 {
 720     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 };
 721     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 };
 722     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 };
 723     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 };
 724     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 };
 725     static const int s_min_table_sizes[3] = { 257, 1, 4 };
 726
 727     tinfl_status status = TINFL_STATUS_FAILED;
 728     mz_uint32 num_bits, dist, counter, num_extra;
 729     tinfl_bit_buf_t bit_buf;
 730     const mz_uint8 *pIn_buf_cur = pIn_buf_next, *const pIn_buf_end = pIn_buf_next + *pIn_buf_size;
 731     mz_uint8 *pOut_buf_cur = pOut_buf_next, *const pOut_buf_end = pOut_buf_next + *pOut_buf_size;
 732     size_t out_buf_size_mask = (decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF) ? (size_t) - 1 : ((pOut_buf_next - pOut_buf_start) + *pOut_buf_size) - 1, dist_from_out_buf_start;
 733
 734     // 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).
 735     if (((out_buf_size_mask + 1) & out_buf_size_mask) || (pOut_buf_next < pOut_buf_start))
 736     {
 737         *pIn_buf_size = *pOut_buf_size = 0;
 738         return TINFL_STATUS_BAD_PARAM;
 739     }
 740
 741     num_bits = r->m_num_bits;
 742     bit_buf = r->m_bit_buf;
 743     dist = r->m_dist;
 744     counter = r->m_counter;
 745     num_extra = r->m_num_extra;
 746     dist_from_out_buf_start = r->m_dist_from_out_buf_start;
 747     TINFL_CR_BEGIN
 748
 749     bit_buf = num_bits = dist = counter = num_extra = r->m_zhdr0 = r->m_zhdr1 = 0;
 750     r->m_z_adler32 = r->m_check_adler32 = 1;
 751     if (decomp_flags & TINFL_FLAG_PARSE_ZLIB_HEADER)
 752     {
 753         TINFL_GET_BYTE(1, r->m_zhdr0);
 754         TINFL_GET_BYTE(2, r->m_zhdr1);
 755         counter = (((r->m_zhdr0 * 256 + r->m_zhdr1) % 31 != 0) || (r->m_zhdr1 & 32) || ((r->m_zhdr0 & 15) != 8));
 756         if (!(decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF))
 757             counter |= (((1U << (8U + (r->m_zhdr0 >> 4))) > 32768U) || ((out_buf_size_mask + 1) < (size_t)(1U << (8U + (r->m_zhdr0 >> 4)))));
 758         if (counter)
 759         {
 760             TINFL_CR_RETURN_FOREVER(36, TINFL_STATUS_FAILED);
 761         }
 762     }
 763
 764     do
 765     {
 766         TINFL_GET_BITS(3, r->m_final, 3);
 767         r->m_type = r->m_final >> 1;
 768         if (r->m_type == 0)
 769         {
 770             TINFL_SKIP_BITS(5, num_bits & 7);
 771             for (counter = 0; counter < 4; ++counter)
 772             {
 773                 if (num_bits)
 774                     TINFL_GET_BITS(6, r->m_raw_header[counter], 8);
 775                 else
 776                     TINFL_GET_BYTE(7, r->m_raw_header[counter]);
 777             }
 778             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))))
 779             {
 780                 TINFL_CR_RETURN_FOREVER(39, TINFL_STATUS_FAILED);
 781             }
 782             while ((counter) && (num_bits))
 783             {
 784                 TINFL_GET_BITS(51, dist, 8);
 785                 while (pOut_buf_cur >= pOut_buf_end)
 786                 {
 787                     TINFL_CR_RETURN(52, TINFL_STATUS_HAS_MORE_OUTPUT);
 788                 }
 789                 *pOut_buf_cur++ = (mz_uint8)dist;
 790                 counter--;
 791             }
 792             while (counter)
 793             {
 794                 size_t n;
 795                 while (pOut_buf_cur >= pOut_buf_end)
 796                 {
 797                     TINFL_CR_RETURN(9, TINFL_STATUS_HAS_MORE_OUTPUT);
 798                 }
 799                 while (pIn_buf_cur >= pIn_buf_end)
 800                 {
 801                     TINFL_CR_RETURN(38, (decomp_flags & TINFL_FLAG_HAS_MORE_INPUT) ? TINFL_STATUS_NEEDS_MORE_INPUT : TINFL_STATUS_FAILED_CANNOT_MAKE_PROGRESS);
 802                 }
 803                 n = MZ_MIN(MZ_MIN((size_t)(pOut_buf_end - pOut_buf_cur), (size_t)(pIn_buf_end - pIn_buf_cur)), counter);
 804                 TINFL_MEMCPY(pOut_buf_cur, pIn_buf_cur, n);
 805                 pIn_buf_cur += n;
 806                 pOut_buf_cur += n;
 807                 counter -= (mz_uint)n;
 808             }
 809         }
 810         else if (r->m_type == 3)
 811         {
 812             TINFL_CR_RETURN_FOREVER(10, TINFL_STATUS_FAILED);
 813         }
 814         else
 815         {
 816             if (r->m_type == 1)
 817             {
 818                 mz_uint8 *p = r->m_tables[0].m_code_size;
 819                 mz_uint i;
 820                 r->m_table_sizes[0] = 288;
 821                 r->m_table_sizes[1] = 32;
 822                 TINFL_MEMSET(r->m_tables[1].m_code_size, 5, 32);
 823                 for (i = 0; i <= 143; ++i)
 824                     *p++ = 8;
 825                 for (; i <= 255; ++i)
 826                     *p++ = 9;
 827                 for (; i <= 279; ++i)
 828                     *p++ = 7;
 829                 for (; i <= 287; ++i)
 830                     *p++ = 8;
 831             }
 832             else
 833             {
 834                 for (counter = 0; counter < 3; counter++)
 835                 {
 836                     TINFL_GET_BITS(11, r->m_table_sizes[counter], "\05\05\04"[counter]);
 837                     r->m_table_sizes[counter] += s_min_table_sizes[counter];
 838                 }
 839                 MZ_CLEAR_OBJ(r->m_tables[2].m_code_size);
 840                 for (counter = 0; counter < r->m_table_sizes[2]; counter++)
 841                 {
 842                     mz_uint s;
 843                     TINFL_GET_BITS(14, s, 3);
 844                     r->m_tables[2].m_code_size[s_length_dezigzag[counter]] = (mz_uint8)s;
 845                 }
 846                 r->m_table_sizes[2] = 19;
 847             }
 848             for (; (int)r->m_type >= 0; r->m_type--)
 849             {
 850                 int tree_next, tree_cur;
 851                 tinfl_huff_table *pTable;
 852                 mz_uint i, j, used_syms, total, sym_index, next_code[17], total_syms[16];
 853                 pTable = &r->m_tables[r->m_type];
 854                 MZ_CLEAR_OBJ(total_syms);
 855                 MZ_CLEAR_OBJ(pTable->m_look_up);
 856                 MZ_CLEAR_OBJ(pTable->m_tree);
 857                 for (i = 0; i < r->m_table_sizes[r->m_type]; ++i)
 858                     total_syms[pTable->m_code_size[i]]++;
 859                 used_syms = 0, total = 0;
 860                 next_code[0] = next_code[1] = 0;
 861                 for (i = 1; i <= 15; ++i)
 862                 {
 863                     used_syms += total_syms[i];
 864                     next_code[i + 1] = (total = ((total + total_syms[i]) << 1));
 865                 }
 866                 if ((65536 != total) && (used_syms > 1))
 867                 {
 868                     TINFL_CR_RETURN_FOREVER(35, TINFL_STATUS_FAILED);
 869                 }
 870                 for (tree_next = -1, sym_index = 0; sym_index < r->m_table_sizes[r->m_type]; ++sym_index)
 871                 {
 872                     mz_uint rev_code = 0, l, cur_code, code_size = pTable->m_code_size[sym_index];
 873                     if (!code_size)
 874                         continue;
 875                     cur_code = next_code[code_size]++;
 876                     for (l = code_size; l > 0; l--, cur_code >>= 1)
 877                         rev_code = (rev_code << 1) | (cur_code & 1);
 878                     if (code_size <= TINFL_FAST_LOOKUP_BITS)
 879                     {
 880                         mz_int16 k = (mz_int16)((code_size << 9) | sym_index);
 881                         while (rev_code < TINFL_FAST_LOOKUP_SIZE)
 882                         {
 883                             pTable->m_look_up[rev_code] = k;
 884                             rev_code += (1 << code_size);
 885                         }
 886                         continue;
 887                     }
 888                     if (0 == (tree_cur = pTable->m_look_up[rev_code & (TINFL_FAST_LOOKUP_SIZE - 1)]))
 889                     {
 890                         pTable->m_look_up[rev_code & (TINFL_FAST_LOOKUP_SIZE - 1)] = (mz_int16)tree_next;
 891                         tree_cur = tree_next;
 892                         tree_next -= 2;
 893                     }
 894                     rev_code >>= (TINFL_FAST_LOOKUP_BITS - 1);
 895                     for (j = code_size; j > (TINFL_FAST_LOOKUP_BITS + 1); j--)
 896                     {
 897                         tree_cur -= ((rev_code >>= 1) & 1);
 898                         if (!pTable->m_tree[-tree_cur - 1])
 899                         {
 900                             pTable->m_tree[-tree_cur - 1] = (mz_int16)tree_next;
 901                             tree_cur = tree_next;
 902                             tree_next -= 2;
 903                         }
 904                         else
 905                             tree_cur = pTable->m_tree[-tree_cur - 1];
 906                     }
 907                     tree_cur -= ((rev_code >>= 1) & 1);
 908                     pTable->m_tree[-tree_cur - 1] = (mz_int16)sym_index;
 909                 }
 910                 if (r->m_type == 2)
 911                 {
 912                     for (counter = 0; counter < (r->m_table_sizes[0] + r->m_table_sizes[1]);)
 913                     {
 914                         mz_uint s;
 915                         TINFL_HUFF_DECODE(16, dist, &r->m_tables[2]);
 916                         if (dist < 16)
 917                         {
 918                             r->m_len_codes[counter++] = (mz_uint8)dist;
 919                             continue;
 920                         }
 921                         if ((dist == 16) && (!counter))
 922                         {
 923                             TINFL_CR_RETURN_FOREVER(17, TINFL_STATUS_FAILED);
 924                         }
 925                         num_extra = "\02\03\07"[dist - 16];
 926                         TINFL_GET_BITS(18, s, num_extra);
 927                         s += "\03\03\013"[dist - 16];
 928                         TINFL_MEMSET(r->m_len_codes + counter, (dist == 16) ? r->m_len_codes[counter - 1] : 0, s);
 929                         counter += s;
 930                     }
 931                     if ((r->m_table_sizes[0] + r->m_table_sizes[1]) != counter)
 932                     {
 933                         TINFL_CR_RETURN_FOREVER(21, TINFL_STATUS_FAILED);
 934                     }
 935                     TINFL_MEMCPY(r->m_tables[0].m_code_size, r->m_len_codes, r->m_table_sizes[0]);
 936                     TINFL_MEMCPY(r->m_tables[1].m_code_size, r->m_len_codes + r->m_table_sizes[0], r->m_table_sizes[1]);
 937                 }
 938             }
 939             for (;;)
 940             {
 941                 mz_uint8 *pSrc;
 942                 for (;;)
 943                 {
 944                     if (((pIn_buf_end - pIn_buf_cur) < 4) || ((pOut_buf_end - pOut_buf_cur) < 2))
 945                     {
 946                         TINFL_HUFF_DECODE(23, counter, &r->m_tables[0]);
 947                         if (counter >= 256)
 948                             break;
 949                         while (pOut_buf_cur >= pOut_buf_end)
 950                         {
 951                             TINFL_CR_RETURN(24, TINFL_STATUS_HAS_MORE_OUTPUT);
 952                         }
 953                         *pOut_buf_cur++ = (mz_uint8)counter;
 954                     }
 955                     else
 956                     {
 957                         int sym2;
 958                         mz_uint code_len;
 959 #if TINFL_USE_64BIT_BITBUF
 960                         if (num_bits < 30)
 961                         {
 962                             bit_buf |= (((tinfl_bit_buf_t)MZ_READ_LE32(pIn_buf_cur)) << num_bits);
 963                             pIn_buf_cur += 4;
 964                             num_bits += 32;
 965                         }
 966 #else
 967                         if (num_bits < 15)
 968                         {
 969                             bit_buf |= (((tinfl_bit_buf_t)MZ_READ_LE16(pIn_buf_cur)) << num_bits);
 970                             pIn_buf_cur += 2;
 971                             num_bits += 16;
 972                         }
 973 #endif
 974                         if ((sym2 = r->m_tables[0].m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0)
 975                             code_len = sym2 >> 9;
 976                         else
 977                         {
 978                             code_len = TINFL_FAST_LOOKUP_BITS;
 979                             do
 980                             {
 981                                 sym2 = r->m_tables[0].m_tree[~sym2 + ((bit_buf >> code_len++) & 1)];
 982                             } while (sym2 < 0);
 983                         }
 984                         counter = sym2;
 985                         bit_buf >>= code_len;
 986                         num_bits -= code_len;
 987                         if (counter & 256)
 988                             break;
 989
 990 #if !TINFL_USE_64BIT_BITBUF
 991                         if (num_bits < 15)
 992                         {
 993                             bit_buf |= (((tinfl_bit_buf_t)MZ_READ_LE16(pIn_buf_cur)) << num_bits);
 994                             pIn_buf_cur += 2;
 995                             num_bits += 16;
 996                         }
 997 #endif
 998                         if ((sym2 = r->m_tables[0].m_look_up[bit_buf & (TINFL_FAST_LOOKUP_SIZE - 1)]) >= 0)
 999                             code_len = sym2 >> 9;
1000                         else
1001                         {
1002                             code_len = TINFL_FAST_LOOKUP_BITS;
1003                             do
1004                             {
1005                                 sym2 = r->m_tables[0].m_tree[~sym2 + ((bit_buf >> code_len++) & 1)];
1006                             } while (sym2 < 0);
1007                         }
1008                         bit_buf >>= code_len;
1009                         num_bits -= code_len;
1010
1011                         pOut_buf_cur[0] = (mz_uint8)counter;
1012                         if (sym2 & 256)
1013                         {
1014                             pOut_buf_cur++;
1015                             counter = sym2;
1016                             break;
1017                         }
1018                         pOut_buf_cur[1] = (mz_uint8)sym2;
1019                         pOut_buf_cur += 2;
1020                     }
1021                 }
1022                 if ((counter &= 511) == 256)
1023                     break;
1024
1025                 num_extra = s_length_extra[counter - 257];
1026                 counter = s_length_base[counter - 257];
1027                 if (num_extra)
1028                 {
1029                     mz_uint extra_bits;
1030                     TINFL_GET_BITS(25, extra_bits, num_extra);
1031                     counter += extra_bits;
1032                 }
1033
1034                 TINFL_HUFF_DECODE(26, dist, &r->m_tables[1]);
1035                 num_extra = s_dist_extra[dist];
1036                 dist = s_dist_base[dist];
1037                 if (num_extra)
1038                 {
1039                     mz_uint extra_bits;
1040                     TINFL_GET_BITS(27, extra_bits, num_extra);
1041                     dist += extra_bits;
1042                 }
1043
1044                 dist_from_out_buf_start = pOut_buf_cur - pOut_buf_start;
1045                 if ((dist > dist_from_out_buf_start) && (decomp_flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF))
1046                 {
1047                     TINFL_CR_RETURN_FOREVER(37, TINFL_STATUS_FAILED);
1048                 }
1049
1050                 pSrc = pOut_buf_start + ((dist_from_out_buf_start - dist) & out_buf_size_mask);
1051
1052                 if ((MZ_MAX(pOut_buf_cur, pSrc) + counter) > pOut_buf_end)
1053                 {
1054                     while (counter--)
1055                     {
1056                         while (pOut_buf_cur >= pOut_buf_end)
1057                         {
1058                             TINFL_CR_RETURN(53, TINFL_STATUS_HAS_MORE_OUTPUT);
1059                         }
1060                         *pOut_buf_cur++ = pOut_buf_start[(dist_from_out_buf_start++ - dist) & out_buf_size_mask];
1061                     }
1062                     continue;
1063                 }
1064 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES
1065                 else if ((counter >= 9) && (counter <= dist))
1066                 {
1067                     const mz_uint8 *pSrc_end = pSrc + (counter & ~7);
1068                     do
1069                     {
1070                         ((mz_uint32 *)pOut_buf_cur)[0] = ((const mz_uint32 *)pSrc)[0];
1071                         ((mz_uint32 *)pOut_buf_cur)[1] = ((const mz_uint32 *)pSrc)[1];
1072                         pOut_buf_cur += 8;
1073                     } while ((pSrc += 8) < pSrc_end);
1074                     if ((counter &= 7) < 3)
1075                     {
1076                         if (counter)
1077                         {
1078                             pOut_buf_cur[0] = pSrc[0];
1079                             if (counter > 1)
1080                                 pOut_buf_cur[1] = pSrc[1];
1081                             pOut_buf_cur += counter;
1082                         }
1083                         continue;
1084                     }
1085                 }
1086 #endif
1087                 do
1088                 {
1089                     pOut_buf_cur[0] = pSrc[0];
1090                     pOut_buf_cur[1] = pSrc[1];
1091                     pOut_buf_cur[2] = pSrc[2];
1092                     pOut_buf_cur += 3;
1093                     pSrc += 3;
1094                 } while ((int)(counter -= 3) > 2);
1095                 if ((int)counter > 0)
1096                 {
1097                     pOut_buf_cur[0] = pSrc[0];
1098                     if ((int)counter > 1)
1099                         pOut_buf_cur[1] = pSrc[1];
1100                     pOut_buf_cur += counter;
1101                 }
1102             }
1103         }
1104     } while (!(r->m_final & 1));
1105
1106     // Ensure byte alignment and put back any bytes from the bitbuf if we've looked ahead too far on gzip, or other Deflate streams followed by arbitrary data.
1107     // I'm being super conservative here. A number of simplifications can be made to the byte alignment part, and the Adler32 check shouldn't ever need to worry about reading from the bitbuf now.
1108     TINFL_SKIP_BITS(32, num_bits & 7);
1109     while ((pIn_buf_cur > pIn_buf_next) && (num_bits >= 8))
1110     {
1111         --pIn_buf_cur;
1112         num_bits -= 8;
1113     }
1114     bit_buf &= (tinfl_bit_buf_t)((1ULL << num_bits) - 1ULL);
1115     MZ_ASSERT(!num_bits); // if this assert fires then we've read beyond the end of non-deflate/zlib streams with following data (such as gzip streams).
1116
1117     if (decomp_flags & TINFL_FLAG_PARSE_ZLIB_HEADER)
1118     {
1119         for (counter = 0; counter < 4; ++counter)
1120         {
1121             mz_uint s;
1122             if (num_bits)
1123                 TINFL_GET_BITS(41, s, 8);
1124             else
1125                 TINFL_GET_BYTE(42, s);
1126             r->m_z_adler32 = (r->m_z_adler32 << 8) | s;
1127         }
1128     }
1129     TINFL_CR_RETURN_FOREVER(34, TINFL_STATUS_DONE);
1130
1131     TINFL_CR_FINISH
1132
1133 common_exit:
1134     // As long as we aren't telling the caller that we NEED more input to make forward progress:
1135     // Put back any bytes from the bitbuf in case we've looked ahead too far on gzip, or other Deflate streams followed by arbitrary data.
1136     // We need to be very careful here to NOT push back any bytes we definitely know we need to make forward progress, though, or we'll lock the caller up into an inf loop.
1137     if ((status != TINFL_STATUS_NEEDS_MORE_INPUT) && (status != TINFL_STATUS_FAILED_CANNOT_MAKE_PROGRESS))
1138     {
1139         while ((pIn_buf_cur > pIn_buf_next) && (num_bits >= 8))
1140         {
1141             --pIn_buf_cur;
1142             num_bits -= 8;
1143         }
1144     }
1145     r->m_num_bits = num_bits;
1146     r->m_bit_buf = bit_buf & (tinfl_bit_buf_t)((1ULL << num_bits) - 1ULL);
1147     r->m_dist = dist;
1148     r->m_counter = counter;
1149     r->m_num_extra = num_extra;
1150     r->m_dist_from_out_buf_start = dist_from_out_buf_start;
1151     *pIn_buf_size = pIn_buf_cur - pIn_buf_next;
1152     *pOut_buf_size = pOut_buf_cur - pOut_buf_next;
1153     if ((decomp_flags & (TINFL_FLAG_PARSE_ZLIB_HEADER | TINFL_FLAG_COMPUTE_ADLER32)) && (status >= 0))
1154     {
1155         const mz_uint8 *ptr = pOut_buf_next;
1156         size_t buf_len = *pOut_buf_size;
1157         mz_uint32 i, s1 = r->m_check_adler32 & 0xffff, s2 = r->m_check_adler32 >> 16;
1158         size_t block_len = buf_len % 5552;
1159         while (buf_len)
1160         {
1161             for (i = 0; i + 7 < block_len; i += 8, ptr += 8)
1162             {
1163                 s1 += ptr[0], s2 += s1;
1164                 s1 += ptr[1], s2 += s1;
1165                 s1 += ptr[2], s2 += s1;
1166                 s1 += ptr[3], s2 += s1;
1167                 s1 += ptr[4], s2 += s1;
1168                 s1 += ptr[5], s2 += s1;
1169                 s1 += ptr[6], s2 += s1;
1170                 s1 += ptr[7], s2 += s1;
1171             }
1172             for (; i < block_len; ++i)
1173                 s1 += *ptr++, s2 += s1;
1174             s1 %= 65521U, s2 %= 65521U;
1175             buf_len -= block_len;
1176             block_len = 5552;
1177         }
1178         r->m_check_adler32 = (s2 << 16) + s1;
1179         if ((status == TINFL_STATUS_DONE) && (decomp_flags & TINFL_FLAG_PARSE_ZLIB_HEADER) && (r->m_check_adler32 != r->m_z_adler32))
1180             status = TINFL_STATUS_ADLER32_MISMATCH;
1181     }
1182     return status;
1183 }
1184
1185 // Higher level helper functions.
1186 void *tinfl_decompress_mem_to_heap(const void *pSrc_buf, size_t src_buf_len, size_t *pOut_len, int flags)
1187 {
1188     tinfl_decompressor decomp;
1189     void *pBuf = NULL, *pNew_buf;
1190     size_t src_buf_ofs = 0, out_buf_capacity = 0;
1191     *pOut_len = 0;
1192     tinfl_init(&decomp);
1193     for (;;)
1194     {
1195         size_t src_buf_size = src_buf_len - src_buf_ofs, dst_buf_size = out_buf_capacity - *pOut_len, new_out_buf_capacity;
1196         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,
1197                                                (flags & ~TINFL_FLAG_HAS_MORE_INPUT) | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF);
1198         if ((status < 0) || (status == TINFL_STATUS_NEEDS_MORE_INPUT))
1199         {
1200             MZ_FREE(pBuf);
1201             *pOut_len = 0;
1202             return NULL;
1203         }
1204         src_buf_ofs += src_buf_size;
1205         *pOut_len += dst_buf_size;
1206         if (status == TINFL_STATUS_DONE)
1207             break;
1208         new_out_buf_capacity = out_buf_capacity * 2;
1209         if (new_out_buf_capacity < 128)
1210             new_out_buf_capacity = 128;
1211         pNew_buf = MZ_REALLOC(pBuf, new_out_buf_capacity);
1212         if (!pNew_buf)
1213         {
1214             MZ_FREE(pBuf);
1215             *pOut_len = 0;
1216             return NULL;
1217         }
1218         pBuf = pNew_buf;
1219         out_buf_capacity = new_out_buf_capacity;
1220     }
1221     return pBuf;
1222 }
1223
1224 size_t tinfl_decompress_mem_to_mem(void *pOut_buf, size_t out_buf_len, const void *pSrc_buf, size_t src_buf_len, int flags)
1225 {
1226     tinfl_decompressor decomp;
1227     tinfl_status status;
1228     tinfl_init(&decomp);
1229     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);
1230     return (status != TINFL_STATUS_DONE) ? TINFL_DECOMPRESS_MEM_TO_MEM_FAILED : out_buf_len;
1231 }
1232
1233 int tinfl_decompress_mem_to_callback(const void *pIn_buf, size_t *pIn_buf_size, tinfl_put_buf_func_ptr pPut_buf_func, void *pPut_buf_user, int flags)
1234 {
1235     int result = 0;
1236     tinfl_decompressor decomp;
1237     mz_uint8 *pDict = (mz_uint8 *)MZ_MALLOC(TINFL_LZ_DICT_SIZE);
1238     size_t in_buf_ofs = 0, dict_ofs = 0;
1239     if (!pDict)
1240         return TINFL_STATUS_FAILED;
1241     tinfl_init(&decomp);
1242     for (;;)
1243     {
1244         size_t in_buf_size = *pIn_buf_size - in_buf_ofs, dst_buf_size = TINFL_LZ_DICT_SIZE - dict_ofs;
1245         tinfl_status status = tinfl_decompress(&decomp, (const mz_uint8 *)pIn_buf + in_buf_ofs, &in_buf_size, pDict, pDict + dict_ofs, &dst_buf_size,
1246                                                (flags & ~(TINFL_FLAG_HAS_MORE_INPUT | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF)));
1247         in_buf_ofs += in_buf_size;
1248         if ((dst_buf_size) && (!(*pPut_buf_func)(pDict + dict_ofs, (int)dst_buf_size, pPut_buf_user)))
1249             break;
1250         if (status != TINFL_STATUS_HAS_MORE_OUTPUT)
1251         {
1252             result = (status == TINFL_STATUS_DONE);
1253             break;
1254         }
1255         dict_ofs = (dict_ofs + dst_buf_size) & (TINFL_LZ_DICT_SIZE - 1);
1256     }
1257     MZ_FREE(pDict);
1258     *pIn_buf_size = in_buf_ofs;
1259     return result;
1260 }
1261
1262 // ------------------- Low-level Compression (independent from all decompression API's)
1263
1264 // Purposely making these tables static for faster init and thread safety.
1265 static const mz_uint16 s_tdefl_len_sym[256] =
1266     {
1267         257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268, 269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272,
1268         273, 273, 273, 273, 273, 273, 273, 273, 274, 274, 274, 274, 274, 274, 274, 274, 275, 275, 275, 275, 275, 275, 275, 275, 276, 276, 276, 276, 276, 276, 276, 276,
1269         277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278,
1270         279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280,
1271         281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281,
1272         282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282,
1273         283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283,
1274         284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 285
1275     };
1276
1277 static const mz_uint8 s_tdefl_len_extra[256] =
1278     {
1279         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
1280         4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
1281         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1282         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0
1283     };
1284
1285 static const mz_uint8 s_tdefl_small_dist_sym[512] =
1286     {
1287         0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11,
1288         11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13,
1289         13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
1290         14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
1291         14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
1292         15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
1293         16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
1294         16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
1295         16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
1296         17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
1297         17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
1298         17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17
1299     };
1300
1301 static const mz_uint8 s_tdefl_small_dist_extra[512] =
1302     {
1303         0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
1304         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1305         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1306         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1307         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1308         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1309         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1310         7, 7, 7, 7, 7, 7, 7, 7
1311     };
1312
1313 static const mz_uint8 s_tdefl_large_dist_sym[128] =
1314     {
1315         0, 0, 18, 19, 20, 20, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
1316         26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
1317         28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
1318     };
1319
1320 static const mz_uint8 s_tdefl_large_dist_extra[128] =
1321     {
1322         0, 0, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
1323         12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
1324         13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13
1325     };
1326
1327 // Radix sorts tdefl_sym_freq[] array by 16-bit key m_key. Returns ptr to sorted values.
1328 typedef struct
1329 {
1330     mz_uint16 m_key, m_sym_index;
1331 } tdefl_sym_freq;
1332 static tdefl_sym_freq *tdefl_radix_sort_syms(mz_uint num_syms, tdefl_sym_freq *pSyms0, tdefl_sym_freq *pSyms1)
1333 {
1334     mz_uint32 total_passes = 2, pass_shift, pass, i, hist[256 * 2];
1335     tdefl_sym_freq *pCur_syms = pSyms0, *pNew_syms = pSyms1;
1336     MZ_CLEAR_OBJ(hist);
1337     for (i = 0; i < num_syms; i++)
1338     {
1339         mz_uint freq = pSyms0[i].m_key;
1340         hist[freq & 0xFF]++;
1341         hist[256 + ((freq >> 8) & 0xFF)]++;
1342     }
1343     while ((total_passes > 1) && (num_syms == hist[(total_passes - 1) * 256]))
1344         total_passes--;
1345     for (pass_shift = 0, pass = 0; pass < total_passes; pass++, pass_shift += 8)
1346     {
1347         const mz_uint32 *pHist = &hist[pass << 8];
1348         mz_uint offsets[256], cur_ofs = 0;
1349         for (i = 0; i < 256; i++)
1350         {
1351             offsets[i] = cur_ofs;
1352             cur_ofs += pHist[i];
1353         }
1354         for (i = 0; i < num_syms; i++)
1355             pNew_syms[offsets[(pCur_syms[i].m_key >> pass_shift) & 0xFF]++] = pCur_syms[i];
1356         {
1357             tdefl_sym_freq *t = pCur_syms;
1358             pCur_syms = pNew_syms;
1359             pNew_syms = t;
1360         }
1361     }
1362     return pCur_syms;
1363 }
1364
1365 // tdefl_calculate_minimum_redundancy() originally written by: Alistair Moffat, alistair@cs.mu.oz.au, Jyrki Katajainen, jyrki@diku.dk, November 1996.
1366 static void tdefl_calculate_minimum_redundancy(tdefl_sym_freq *A, int n)
1367 {
1368     int root, leaf, next, avbl, used, dpth;
1369     if (n == 0)
1370         return;
1371     else if (n == 1)
1372     {
1373         A[0].m_key = 1;
1374         return;
1375     }
1376     A[0].m_key += A[1].m_key;
1377     root = 0;
1378     leaf = 2;
1379     for (next = 1; next < n - 1; next++)
1380     {
1381         if (leaf >= n || A[root].m_key < A[leaf].m_key)
1382         {
1383             A[next].m_key = A[root].m_key;
1384             A[root++].m_key = (mz_uint16)next;
1385         }
1386         else
1387             A[next].m_key = A[leaf++].m_key;
1388         if (leaf >= n || (root < next && A[root].m_key < A[leaf].m_key))
1389         {
1390             A[next].m_key = (mz_uint16)(A[next].m_key + A[root].m_key);
1391             A[root++].m_key = (mz_uint16)next;
1392         }
1393         else
1394             A[next].m_key = (mz_uint16)(A[next].m_key + A[leaf++].m_key);
1395     }
1396     A[n - 2].m_key = 0;
1397     for (next = n - 3; next >= 0; next--)
1398         A[next].m_key = A[A[next].m_key].m_key + 1;
1399     avbl = 1;
1400     used = dpth = 0;
1401     root = n - 2;
1402     next = n - 1;
1403     while (avbl > 0)
1404     {
1405         while (root >= 0 && (int)A[root].m_key == dpth)
1406         {
1407             used++;
1408             root--;
1409         }
1410         while (avbl > used)
1411         {
1412             A[next--].m_key = (mz_uint16)(dpth);
1413             avbl--;
1414         }
1415         avbl = 2 * used;
1416         dpth++;
1417         used = 0;
1418     }
1419 }
1420
1421 // Limits canonical Huffman code table's max code size.
1422 enum
1423 {
1424     TDEFL_MAX_SUPPORTED_HUFF_CODESIZE = 32
1425 };
1426 static void tdefl_huffman_enforce_max_code_size(int *pNum_codes, int code_list_len, int max_code_size)
1427 {
1428     int i;
1429     mz_uint32 total = 0;
1430     if (code_list_len <= 1)
1431         return;
1432     for (i = max_code_size + 1; i <= TDEFL_MAX_SUPPORTED_HUFF_CODESIZE; i++)
1433         pNum_codes[max_code_size] += pNum_codes[i];
1434     for (i = max_code_size; i > 0; i--)
1435         total += (((mz_uint32)pNum_codes[i]) << (max_code_size - i));
1436     while (total != (1UL << max_code_size))
1437     {
1438         pNum_codes[max_code_size]--;
1439         for (i = max_code_size - 1; i > 0; i--)
1440             if (pNum_codes[i])
1441             {
1442                 pNum_codes[i]--;
1443                 pNum_codes[i + 1] += 2;
1444                 break;
1445             }
1446         total--;
1447     }
1448 }
1449
1450 static void tdefl_optimize_huffman_table(tdefl_compressor *d, int table_num, int table_len, int code_size_limit, int static_table)
1451 {
1452     int i, j, l, num_codes[1 + TDEFL_MAX_SUPPORTED_HUFF_CODESIZE];
1453     mz_uint next_code[TDEFL_MAX_SUPPORTED_HUFF_CODESIZE + 1];
1454     MZ_CLEAR_OBJ(num_codes);
1455     if (static_table)
1456     {
1457         for (i = 0; i < table_len; i++)
1458             num_codes[d->m_huff_code_sizes[table_num][i]]++;
1459     }
1460     else
1461     {
1462         tdefl_sym_freq syms0[TDEFL_MAX_HUFF_SYMBOLS], syms1[TDEFL_MAX_HUFF_SYMBOLS], *pSyms;
1463         int num_used_syms = 0;
1464         const mz_uint16 *pSym_count = &d->m_huff_count[table_num][0];
1465         for (i = 0; i < table_len; i++)
1466             if (pSym_count[i])
1467             {
1468                 syms0[num_used_syms].m_key = (mz_uint16)pSym_count[i];
1469                 syms0[num_used_syms++].m_sym_index = (mz_uint16)i;
1470             }
1471
1472         pSyms = tdefl_radix_sort_syms(num_used_syms, syms0, syms1);
1473         tdefl_calculate_minimum_redundancy(pSyms, num_used_syms);
1474
1475         for (i = 0; i < num_used_syms; i++)
1476             num_codes[pSyms[i].m_key]++;
1477
1478         tdefl_huffman_enforce_max_code_size(num_codes, num_used_syms, code_size_limit);
1479
1480         MZ_CLEAR_OBJ(d->m_huff_code_sizes[table_num]);
1481         MZ_CLEAR_OBJ(d->m_huff_codes[table_num]);
1482         for (i = 1, j = num_used_syms; i <= code_size_limit; i++)
1483             for (l = num_codes[i]; l > 0; l--)
1484                 d->m_huff_code_sizes[table_num][pSyms[--j].m_sym_index] = (mz_uint8)(i);
1485     }
1486
1487     next_code[1] = 0;
1488     for (j = 0, i = 2; i <= code_size_limit; i++)
1489         next_code[i] = j = ((j + num_codes[i - 1]) << 1);
1490
1491     for (i = 0; i < table_len; i++)
1492     {
1493         mz_uint rev_code = 0, code, code_size;
1494         if ((code_size = d->m_huff_code_sizes[table_num][i]) == 0)
1495             continue;
1496         code = next_code[code_size]++;
1497         for (l = code_size; l > 0; l--, code >>= 1)
1498             rev_code = (rev_code << 1) | (code & 1);
1499         d->m_huff_codes[table_num][i] = (mz_uint16)rev_code;
1500     }
1501 }
1502
1503 #define TDEFL_PUT_BITS(b, l)                                       \
1504     do                                                             \
1505     {                                                              \
1506         mz_uint bits = b;                                          \
1507         mz_uint len = l;                                           \
1508         MZ_ASSERT(bits <= ((1U << len) - 1U));                     \
1509         d->m_bit_buffer |= (bits << d->m_bits_in);                 \
1510         d->m_bits_in += len;                                       \
1511         while (d->m_bits_in >= 8)                                  \
1512         {                                                          \
1513             if (d->m_pOutput_buf < d->m_pOutput_buf_end)           \
1514                 *d->m_pOutput_buf++ = (mz_uint8)(d->m_bit_buffer); \
1515             d->m_bit_buffer >>= 8;                                 \
1516             d->m_bits_in -= 8;                                     \
1517         }                                                          \
1518     \
1519 }                                                           \
1520     MZ_MACRO_END
1521
1522 #define TDEFL_RLE_PREV_CODE_SIZE()                                                                                       \
1523     {                                                                                                                    \
1524         if (rle_repeat_count)                                                                                            \
1525         {                                                                                                                \
1526             if (rle_repeat_count < 3)                                                                                    \
1527             {                                                                                                            \
1528                 d->m_huff_count[2][prev_code_size] = (mz_uint16)(d->m_huff_count[2][prev_code_size] + rle_repeat_count); \
1529                 while (rle_repeat_count--)                                                                               \
1530                     packed_code_sizes[num_packed_code_sizes++] = prev_code_size;                                         \
1531             }                                                                                                            \
1532             else                                                                                                         \
1533             {                                                                                                            \
1534                 d->m_huff_count[2][16] = (mz_uint16)(d->m_huff_count[2][16] + 1);                                        \
1535                 packed_code_sizes[num_packed_code_sizes++] = 16;                                                         \
1536                 packed_code_sizes[num_packed_code_sizes++] = (mz_uint8)(rle_repeat_count - 3);                           \
1537             \
1538 }                                                                                                         \
1539             rle_repeat_count = 0;                                                                                        \
1540         }                                                                                                                \
1541     }
1542
1543 #define TDEFL_RLE_ZERO_CODE_SIZE()                                                         \
1544     {                                                                                      \
1545         if (rle_z_count)                                                                   \
1546         {                                                                                  \
1547             if (rle_z_count < 3)                                                           \
1548             {                                                                              \
1549                 d->m_huff_count[2][0] = (mz_uint16)(d->m_huff_count[2][0] + rle_z_count);  \
1550                 while (rle_z_count--)                                                      \
1551                     packed_code_sizes[num_packed_code_sizes++] = 0;                        \
1552             }                                                                              \
1553             else if (rle_z_count <= 10)                                                    \
1554             {                                                                              \
1555                 d->m_huff_count[2][17] = (mz_uint16)(d->m_huff_count[2][17] + 1);          \
1556                 packed_code_sizes[num_packed_code_sizes++] = 17;                           \
1557                 packed_code_sizes[num_packed_code_sizes++] = (mz_uint8)(rle_z_count - 3);  \
1558             }                                                                              \
1559             else                                                                           \
1560             {                                                                              \
1561                 d->m_huff_count[2][18] = (mz_uint16)(d->m_huff_count[2][18] + 1);          \
1562                 packed_code_sizes[num_packed_code_sizes++] = 18;                           \
1563                 packed_code_sizes[num_packed_code_sizes++] = (mz_uint8)(rle_z_count - 11); \
1564             \
1565 }                                                                           \
1566             rle_z_count = 0;                                                               \
1567         }                                                                                  \
1568     }
1569
1570 static mz_uint8 s_tdefl_packed_code_size_syms_swizzle[] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
1571
1572 static void tdefl_start_dynamic_block(tdefl_compressor *d)
1573 {
1574     int num_lit_codes, num_dist_codes, num_bit_lengths;
1575     mz_uint i, total_code_sizes_to_pack, num_packed_code_sizes, rle_z_count, rle_repeat_count, packed_code_sizes_index;
1576     mz_uint8 code_sizes_to_pack[TDEFL_MAX_HUFF_SYMBOLS_0 + TDEFL_MAX_HUFF_SYMBOLS_1], packed_code_sizes[TDEFL_MAX_HUFF_SYMBOLS_0 + TDEFL_MAX_HUFF_SYMBOLS_1], prev_code_size = 0xFF;
1577
1578     d->m_huff_count[0][256] = 1;
1579
1580     tdefl_optimize_huffman_table(d, 0, TDEFL_MAX_HUFF_SYMBOLS_0, 15, MZ_FALSE);
1581     tdefl_optimize_huffman_table(d, 1, TDEFL_MAX_HUFF_SYMBOLS_1, 15, MZ_FALSE);
1582
1583     for (num_lit_codes = 286; num_lit_codes > 257; num_lit_codes--)
1584         if (d->m_huff_code_sizes[0][num_lit_codes - 1])
1585             break;
1586     for (num_dist_codes = 30; num_dist_codes > 1; num_dist_codes--)
1587         if (d->m_huff_code_sizes[1][num_dist_codes - 1])
1588             break;
1589
1590     memcpy(code_sizes_to_pack, &d->m_huff_code_sizes[0][0], num_lit_codes);
1591     memcpy(code_sizes_to_pack + num_lit_codes, &d->m_huff_code_sizes[1][0], num_dist_codes);
1592     total_code_sizes_to_pack = num_lit_codes + num_dist_codes;
1593     num_packed_code_sizes = 0;
1594     rle_z_count = 0;
1595     rle_repeat_count = 0;
1596
1597     memset(&d->m_huff_count[2][0], 0, sizeof(d->m_huff_count[2][0]) * TDEFL_MAX_HUFF_SYMBOLS_2);
1598     for (i = 0; i < total_code_sizes_to_pack; i++)
1599     {
1600         mz_uint8 code_size = code_sizes_to_pack[i];
1601         if (!code_size)
1602         {
1603             TDEFL_RLE_PREV_CODE_SIZE();
1604             if (++rle_z_count == 138)
1605             {
1606                 TDEFL_RLE_ZERO_CODE_SIZE();
1607             }
1608         }
1609         else
1610         {
1611             TDEFL_RLE_ZERO_CODE_SIZE();
1612             if (code_size != prev_code_size)
1613             {
1614                 TDEFL_RLE_PREV_CODE_SIZE();
1615                 d->m_huff_count[2][code_size] = (mz_uint16)(d->m_huff_count[2][code_size] + 1);
1616                 packed_code_sizes[num_packed_code_sizes++] = code_size;
1617             }
1618             else if (++rle_repeat_count == 6)
1619             {
1620                 TDEFL_RLE_PREV_CODE_SIZE();
1621             }
1622         }
1623         prev_code_size = code_size;
1624     }
1625     if (rle_repeat_count)
1626     {
1627         TDEFL_RLE_PREV_CODE_SIZE();
1628     }
1629     else
1630     {
1631         TDEFL_RLE_ZERO_CODE_SIZE();
1632     }
1633
1634     tdefl_optimize_huffman_table(d, 2, TDEFL_MAX_HUFF_SYMBOLS_2, 7, MZ_FALSE);
1635
1636     TDEFL_PUT_BITS(2, 2);
1637
1638     TDEFL_PUT_BITS(num_lit_codes - 257, 5);
1639     TDEFL_PUT_BITS(num_dist_codes - 1, 5);
1640
1641     for (num_bit_lengths = 18; num_bit_lengths >= 0; num_bit_lengths--)
1642         if (d->m_huff_code_sizes[2][s_tdefl_packed_code_size_syms_swizzle[num_bit_lengths]])
1643             break;
1644     num_bit_lengths = MZ_MAX(4, (num_bit_lengths + 1));
1645     TDEFL_PUT_BITS(num_bit_lengths - 4, 4);
1646     for (i = 0; (int)i < num_bit_lengths; i++)
1647         TDEFL_PUT_BITS(d->m_huff_code_sizes[2][s_tdefl_packed_code_size_syms_swizzle[i]], 3);
1648
1649     for (packed_code_sizes_index = 0; packed_code_sizes_index < num_packed_code_sizes;)
1650     {
1651         mz_uint code = packed_code_sizes[packed_code_sizes_index++];
1652         MZ_ASSERT(code < TDEFL_MAX_HUFF_SYMBOLS_2);
1653         TDEFL_PUT_BITS(d->m_huff_codes[2][code], d->m_huff_code_sizes[2][code]);
1654         if (code >= 16)
1655             TDEFL_PUT_BITS(packed_code_sizes[packed_code_sizes_index++], "\02\03\07"[code - 16]);
1656     }
1657 }
1658
1659 static void tdefl_start_static_block(tdefl_compressor *d)
1660 {
1661     mz_uint i;
1662     mz_uint8 *p = &d->m_huff_code_sizes[0][0];
1663
1664     for (i = 0; i <= 143; ++i)
1665         *p++ = 8;
1666     for (; i <= 255; ++i)
1667         *p++ = 9;
1668     for (; i <= 279; ++i)
1669         *p++ = 7;
1670     for (; i <= 287; ++i)
1671         *p++ = 8;
1672
1673     memset(d->m_huff_code_sizes[1], 5, 32);
1674
1675     tdefl_optimize_huffman_table(d, 0, 288, 15, MZ_TRUE);
1676     tdefl_optimize_huffman_table(d, 1, 32, 15, MZ_TRUE);
1677
1678     TDEFL_PUT_BITS(1, 2);
1679 }
1680
1681 static const mz_uint mz_bitmasks[17] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
1682
1683 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES &&MINIZ_LITTLE_ENDIAN &&MINIZ_HAS_64BIT_REGISTERS
1684 static mz_bool tdefl_compress_lz_codes(tdefl_compressor *d)
1685 {
1686     mz_uint flags;
1687     mz_uint8 *pLZ_codes;
1688     mz_uint8 *pOutput_buf = d->m_pOutput_buf;
1689     mz_uint8 *pLZ_code_buf_end = d->m_pLZ_code_buf;
1690     mz_uint64 bit_buffer = d->m_bit_buffer;
1691     mz_uint bits_in = d->m_bits_in;
1692
1693 #define TDEFL_PUT_BITS_FAST(b, l)                    \
1694     {                                                \
1695         bit_buffer |= (((mz_uint64)(b)) << bits_in); \
1696         bits_in += (l);                              \
1697     }
1698
1699     flags = 1;
1700     for (pLZ_codes = d->m_lz_code_buf; pLZ_codes < pLZ_code_buf_end; flags >>= 1)
1701     {
1702         if (flags == 1)
1703             flags = *pLZ_codes++ | 0x100;
1704
1705         if (flags & 1)
1706         {
1707             mz_uint s0, s1, n0, n1, sym, num_extra_bits;
1708             mz_uint match_len = pLZ_codes[0], match_dist = *(const mz_uint16 *)(pLZ_codes + 1);
1709             pLZ_codes += 3;
1710
1711             MZ_ASSERT(d->m_huff_code_sizes[0][s_tdefl_len_sym[match_len]]);
1712             TDEFL_PUT_BITS_FAST(d->m_huff_codes[0][s_tdefl_len_sym[match_len]], d->m_huff_code_sizes[0][s_tdefl_len_sym[match_len]]);
1713             TDEFL_PUT_BITS_FAST(match_len & mz_bitmasks[s_tdefl_len_extra[match_len]], s_tdefl_len_extra[match_len]);
1714
1715             // This sequence coaxes MSVC into using cmov's vs. jmp's.
1716             s0 = s_tdefl_small_dist_sym[match_dist & 511];
1717             n0 = s_tdefl_small_dist_extra[match_dist & 511];
1718             s1 = s_tdefl_large_dist_sym[match_dist >> 8];
1719             n1 = s_tdefl_large_dist_extra[match_dist >> 8];
1720             sym = (match_dist < 512) ? s0 : s1;
1721             num_extra_bits = (match_dist < 512) ? n0 : n1;
1722
1723             MZ_ASSERT(d->m_huff_code_sizes[1][sym]);
1724             TDEFL_PUT_BITS_FAST(d->m_huff_codes[1][sym], d->m_huff_code_sizes[1][sym]);
1725             TDEFL_PUT_BITS_FAST(match_dist & mz_bitmasks[num_extra_bits], num_extra_bits);
1726         }
1727         else
1728         {
1729             mz_uint lit = *pLZ_codes++;
1730             MZ_ASSERT(d->m_huff_code_sizes[0][lit]);
1731             TDEFL_PUT_BITS_FAST(d->m_huff_codes[0][lit], d->m_huff_code_sizes[0][lit]);
1732
1733             if (((flags & 2) == 0) && (pLZ_codes < pLZ_code_buf_end))
1734             {
1735                 flags >>= 1;
1736                 lit = *pLZ_codes++;
1737                 MZ_ASSERT(d->m_huff_code_sizes[0][lit]);
1738                 TDEFL_PUT_BITS_FAST(d->m_huff_codes[0][lit], d->m_huff_code_sizes[0][lit]);
1739
1740                 if (((flags & 2) == 0) && (pLZ_codes < pLZ_code_buf_end))
1741                 {
1742                     flags >>= 1;
1743                     lit = *pLZ_codes++;
1744                     MZ_ASSERT(d->m_huff_code_sizes[0][lit]);
1745                     TDEFL_PUT_BITS_FAST(d->m_huff_codes[0][lit], d->m_huff_code_sizes[0][lit]);
1746                 }
1747             }
1748         }
1749
1750         if (pOutput_buf >= d->m_pOutput_buf_end)
1751             return MZ_FALSE;
1752
1753         *(mz_uint64 *)pOutput_buf = bit_buffer;
1754         pOutput_buf += (bits_in >> 3);
1755         bit_buffer >>= (bits_in & ~7);
1756         bits_in &= 7;
1757     }
1758
1759 #undef TDEFL_PUT_BITS_FAST
1760
1761     d->m_pOutput_buf = pOutput_buf;
1762     d->m_bits_in = 0;
1763     d->m_bit_buffer = 0;
1764
1765     while (bits_in)
1766     {
1767         mz_uint32 n = MZ_MIN(bits_in, 16);
1768         TDEFL_PUT_BITS((mz_uint)bit_buffer & mz_bitmasks[n], n);
1769         bit_buffer >>= n;
1770         bits_in -= n;
1771     }
1772
1773     TDEFL_PUT_BITS(d->m_huff_codes[0][256], d->m_huff_code_sizes[0][256]);
1774
1775     return (d->m_pOutput_buf < d->m_pOutput_buf_end);
1776 }
1777 #else
1778 static mz_bool tdefl_compress_lz_codes(tdefl_compressor *d)
1779 {
1780     mz_uint flags;
1781     mz_uint8 *pLZ_codes;
1782
1783     flags = 1;
1784     for (pLZ_codes = d->m_lz_code_buf; pLZ_codes < d->m_pLZ_code_buf; flags >>= 1)
1785     {
1786         if (flags == 1)
1787             flags = *pLZ_codes++ | 0x100;
1788         if (flags & 1)
1789         {
1790             mz_uint sym, num_extra_bits;
1791             mz_uint match_len = pLZ_codes[0], match_dist = (pLZ_codes[1] | (pLZ_codes[2] << 8));
1792             pLZ_codes += 3;
1793
1794             MZ_ASSERT(d->m_huff_code_sizes[0][s_tdefl_len_sym[match_len]]);
1795             TDEFL_PUT_BITS(d->m_huff_codes[0][s_tdefl_len_sym[match_len]], d->m_huff_code_sizes[0][s_tdefl_len_sym[match_len]]);
1796             TDEFL_PUT_BITS(match_len & mz_bitmasks[s_tdefl_len_extra[match_len]], s_tdefl_len_extra[match_len]);
1797
1798             if (match_dist < 512)
1799             {
1800                 sym = s_tdefl_small_dist_sym[match_dist];
1801                 num_extra_bits = s_tdefl_small_dist_extra[match_dist];
1802             }
1803             else
1804             {
1805                 sym = s_tdefl_large_dist_sym[match_dist >> 8];
1806                 num_extra_bits = s_tdefl_large_dist_extra[match_dist >> 8];
1807             }
1808             MZ_ASSERT(d->m_huff_code_sizes[1][sym]);
1809             TDEFL_PUT_BITS(d->m_huff_codes[1][sym], d->m_huff_code_sizes[1][sym]);
1810             TDEFL_PUT_BITS(match_dist & mz_bitmasks[num_extra_bits], num_extra_bits);
1811         }
1812         else
1813         {
1814             mz_uint lit = *pLZ_codes++;
1815             MZ_ASSERT(d->m_huff_code_sizes[0][lit]);
1816             TDEFL_PUT_BITS(d->m_huff_codes[0][lit], d->m_huff_code_sizes[0][lit]);
1817         }
1818     }
1819
1820     TDEFL_PUT_BITS(d->m_huff_codes[0][256], d->m_huff_code_sizes[0][256]);
1821
1822     return (d->m_pOutput_buf < d->m_pOutput_buf_end);
1823 }
1824 #endif // MINIZ_USE_UNALIGNED_LOADS_AND_STORES && MINIZ_LITTLE_ENDIAN && MINIZ_HAS_64BIT_REGISTERS
1825
1826 static mz_bool tdefl_compress_block(tdefl_compressor *d, mz_bool static_block)
1827 {
1828     if (static_block)
1829         tdefl_start_static_block(d);
1830     else
1831         tdefl_start_dynamic_block(d);
1832     return tdefl_compress_lz_codes(d);
1833 }
1834
1835 static int tdefl_flush_block(tdefl_compressor *d, int flush)
1836 {
1837     mz_uint saved_bit_buf, saved_bits_in;
1838     mz_uint8 *pSaved_output_buf;
1839     mz_bool comp_block_succeeded = MZ_FALSE;
1840     int n, use_raw_block = ((d->m_flags & TDEFL_FORCE_ALL_RAW_BLOCKS) != 0) && (d->m_lookahead_pos - d->m_lz_code_buf_dict_pos) <= d->m_dict_size;
1841     mz_uint8 *pOutput_buf_start = ((d->m_pPut_buf_func == NULL) && ((*d->m_pOut_buf_size - d->m_out_buf_ofs) >= TDEFL_OUT_BUF_SIZE)) ? ((mz_uint8 *)d->m_pOut_buf + d->m_out_buf_ofs) : d->m_output_buf;
1842
1843     d->m_pOutput_buf = pOutput_buf_start;
1844     d->m_pOutput_buf_end = d->m_pOutput_buf + TDEFL_OUT_BUF_SIZE - 16;
1845
1846     MZ_ASSERT(!d->m_output_flush_remaining);
1847     d->m_output_flush_ofs = 0;
1848     d->m_output_flush_remaining = 0;
1849
1850     *d->m_pLZ_flags = (mz_uint8)(*d->m_pLZ_flags >> d->m_num_flags_left);
1851     d->m_pLZ_code_buf -= (d->m_num_flags_left == 8);
1852
1853     if ((d->m_flags & TDEFL_WRITE_ZLIB_HEADER) && (!d->m_block_index))
1854     {
1855         TDEFL_PUT_BITS(0x78, 8);
1856         TDEFL_PUT_BITS(0x01, 8);
1857     }
1858
1859     TDEFL_PUT_BITS(flush == TDEFL_FINISH, 1);
1860
1861     pSaved_output_buf = d->m_pOutput_buf;
1862     saved_bit_buf = d->m_bit_buffer;
1863     saved_bits_in = d->m_bits_in;
1864
1865     if (!use_raw_block)
1866         comp_block_succeeded = tdefl_compress_block(d, (d->m_flags & TDEFL_FORCE_ALL_STATIC_BLOCKS) || (d->m_total_lz_bytes < 48));
1867
1868     // If the block gets expanded, forget the current contents of the output buffer and send a raw block instead.
1869     if (((use_raw_block) || ((d->m_total_lz_bytes) && ((d->m_pOutput_buf - pSaved_output_buf + 1U) >= d->m_total_lz_bytes))) &&
1870         ((d->m_lookahead_pos - d->m_lz_code_buf_dict_pos) <= d->m_dict_size))
1871     {
1872         mz_uint i;
1873         d->m_pOutput_buf = pSaved_output_buf;
1874         d->m_bit_buffer = saved_bit_buf, d->m_bits_in = saved_bits_in;
1875         TDEFL_PUT_BITS(0, 2);
1876         if (d->m_bits_in)
1877         {
1878             TDEFL_PUT_BITS(0, 8 - d->m_bits_in);
1879         }
1880         for (i = 2; i; --i, d->m_total_lz_bytes ^= 0xFFFF)
1881         {
1882             TDEFL_PUT_BITS(d->m_total_lz_bytes & 0xFFFF, 16);
1883         }
1884         for (i = 0; i < d->m_total_lz_bytes; ++i)
1885         {
1886             TDEFL_PUT_BITS(d->m_dict[(d->m_lz_code_buf_dict_pos + i) & TDEFL_LZ_DICT_SIZE_MASK], 8);
1887         }
1888     }
1889     // Check for the extremely unlikely (if not impossible) case of the compressed block not fitting into the output buffer when using dynamic codes.
1890     else if (!comp_block_succeeded)
1891     {
1892         d->m_pOutput_buf = pSaved_output_buf;
1893         d->m_bit_buffer = saved_bit_buf, d->m_bits_in = saved_bits_in;
1894         tdefl_compress_block(d, MZ_TRUE);
1895     }
1896
1897     if (flush)
1898     {
1899         if (flush == TDEFL_FINISH)
1900         {
1901             if (d->m_bits_in)
1902             {
1903                 TDEFL_PUT_BITS(0, 8 - d->m_bits_in);
1904             }
1905             if (d->m_flags & TDEFL_WRITE_ZLIB_HEADER)
1906             {
1907                 mz_uint i, a = d->m_adler32;
1908                 for (i = 0; i < 4; i++)
1909                 {
1910                     TDEFL_PUT_BITS((a >> 24) & 0xFF, 8);
1911                     a <<= 8;
1912                 }
1913             }
1914         }
1915         else
1916         {
1917             mz_uint i, z = 0;
1918             TDEFL_PUT_BITS(0, 3);
1919             if (d->m_bits_in)
1920             {
1921                 TDEFL_PUT_BITS(0, 8 - d->m_bits_in);
1922             }
1923             for (i = 2; i; --i, z ^= 0xFFFF)
1924             {
1925                 TDEFL_PUT_BITS(z & 0xFFFF, 16);
1926             }
1927         }
1928     }
1929
1930     MZ_ASSERT(d->m_pOutput_buf < d->m_pOutput_buf_end);
1931
1932     memset(&d->m_huff_count[0][0], 0, sizeof(d->m_huff_count[0][0]) * TDEFL_MAX_HUFF_SYMBOLS_0);
1933     memset(&d->m_huff_count[1][0], 0, sizeof(d->m_huff_count[1][0]) * TDEFL_MAX_HUFF_SYMBOLS_1);
1934
1935     d->m_pLZ_code_buf = d->m_lz_code_buf + 1;
1936     d->m_pLZ_flags = d->m_lz_code_buf;
1937     d->m_num_flags_left = 8;
1938     d->m_lz_code_buf_dict_pos += d->m_total_lz_bytes;
1939     d->m_total_lz_bytes = 0;
1940     d->m_block_index++;
1941
1942     if ((n = (int)(d->m_pOutput_buf - pOutput_buf_start)) != 0)
1943     {
1944         if (d->m_pPut_buf_func)
1945         {
1946             *d->m_pIn_buf_size = d->m_pSrc - (const mz_uint8 *)d->m_pIn_buf;
1947             if (!(*d->m_pPut_buf_func)(d->m_output_buf, n, d->m_pPut_buf_user))
1948                 return (d->m_prev_return_status = TDEFL_STATUS_PUT_BUF_FAILED);
1949         }
1950         else if (pOutput_buf_start == d->m_output_buf)
1951         {
1952             int bytes_to_copy = (int)MZ_MIN((size_t)n, (size_t)(*d->m_pOut_buf_size - d->m_out_buf_ofs));
1953             memcpy((mz_uint8 *)d->m_pOut_buf + d->m_out_buf_ofs, d->m_output_buf, bytes_to_copy);
1954             d->m_out_buf_ofs += bytes_to_copy;
1955             if ((n -= bytes_to_copy) != 0)
1956             {
1957                 d->m_output_flush_ofs = bytes_to_copy;
1958                 d->m_output_flush_remaining = n;
1959             }
1960         }
1961         else
1962         {
1963             d->m_out_buf_ofs += n;
1964         }
1965     }
1966
1967     return d->m_output_flush_remaining;
1968 }
1969
1970 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES
1971 #define TDEFL_READ_UNALIGNED_WORD(p) *(const mz_uint16 *)(p)
1972 static MZ_FORCEINLINE void tdefl_find_match(tdefl_compressor *d, mz_uint lookahead_pos, mz_uint max_dist, mz_uint max_match_len, mz_uint *pMatch_dist, mz_uint *pMatch_len)
1973 {
1974     mz_uint dist, pos = lookahead_pos & TDEFL_LZ_DICT_SIZE_MASK, match_len = *pMatch_len, probe_pos = pos, next_probe_pos, probe_len;
1975     mz_uint num_probes_left = d->m_max_probes[match_len >= 32];
1976     const mz_uint16 *s = (const mz_uint16 *)(d->m_dict + pos), *p, *q;
1977     mz_uint16 c01 = TDEFL_READ_UNALIGNED_WORD(&d->m_dict[pos + match_len - 1]), s01 = TDEFL_READ_UNALIGNED_WORD(s);
1978     MZ_ASSERT(max_match_len <= TDEFL_MAX_MATCH_LEN);
1979     if (max_match_len <= match_len)
1980         return;
1981     for (;;)
1982     {
1983         for (;;)
1984         {
1985             if (--num_probes_left == 0)
1986                 return;
1987 #define TDEFL_PROBE                                                                             \
1988     next_probe_pos = d->m_next[probe_pos];                                                      \
1989     if ((!next_probe_pos) || ((dist = (mz_uint16)(lookahead_pos - next_probe_pos)) > max_dist)) \
1990         return;                                                                                 \
1991     probe_pos = next_probe_pos & TDEFL_LZ_DICT_SIZE_MASK;                                       \
1992     if (TDEFL_READ_UNALIGNED_WORD(&d->m_dict[probe_pos + match_len - 1]) == c01)                \
1993         break;
1994             TDEFL_PROBE;
1995             TDEFL_PROBE;
1996             TDEFL_PROBE;
1997         }
1998         if (!dist)
1999             break;
2000         q = (const mz_uint16 *)(d->m_dict + probe_pos);
2001         if (TDEFL_READ_UNALIGNED_WORD(q) != s01)
2002             continue;
2003         p = s;
2004         probe_len = 32;
2005         do
2006         {
2007         } while ((TDEFL_READ_UNALIGNED_WORD(++p) == TDEFL_READ_UNALIGNED_WORD(++q)) && (TDEFL_READ_UNALIGNED_WORD(++p) == TDEFL_READ_UNALIGNED_WORD(++q)) &&
2008                  (TDEFL_READ_UNALIGNED_WORD(++p) == TDEFL_READ_UNALIGNED_WORD(++q)) && (TDEFL_READ_UNALIGNED_WORD(++p) == TDEFL_READ_UNALIGNED_WORD(++q)) && (--probe_len > 0));
2009         if (!probe_len)
2010         {
2011             *pMatch_dist = dist;
2012             *pMatch_len = MZ_MIN(max_match_len, (mz_uint)TDEFL_MAX_MATCH_LEN);
2013             break;
2014         }
2015         else if ((probe_len = ((mz_uint)(p - s) * 2) + (mz_uint)(*(const mz_uint8 *)p == *(const mz_uint8 *)q)) > match_len)
2016         {
2017             *pMatch_dist = dist;
2018             if ((*pMatch_len = match_len = MZ_MIN(max_match_len, probe_len)) == max_match_len)
2019                 break;
2020             c01 = TDEFL_READ_UNALIGNED_WORD(&d->m_dict[pos + match_len - 1]);
2021         }
2022     }
2023 }
2024 #else
2025 static MZ_FORCEINLINE void tdefl_find_match(tdefl_compressor *d, mz_uint lookahead_pos, mz_uint max_dist, mz_uint max_match_len, mz_uint *pMatch_dist, mz_uint *pMatch_len)
2026 {
2027     mz_uint dist, pos = lookahead_pos & TDEFL_LZ_DICT_SIZE_MASK, match_len = *pMatch_len, probe_pos = pos, next_probe_pos, probe_len;
2028     mz_uint num_probes_left = d->m_max_probes[match_len >= 32];
2029     const mz_uint8 *s = d->m_dict + pos, *p, *q;
2030     mz_uint8 c0 = d->m_dict[pos + match_len], c1 = d->m_dict[pos + match_len - 1];
2031     MZ_ASSERT(max_match_len <= TDEFL_MAX_MATCH_LEN);
2032     if (max_match_len <= match_len)
2033         return;
2034     for (;;)
2035     {
2036         for (;;)
2037         {
2038             if (--num_probes_left == 0)
2039                 return;
2040 #define TDEFL_PROBE                                                                               \
2041     next_probe_pos = d->m_next[probe_pos];                                                        \
2042     if ((!next_probe_pos) || ((dist = (mz_uint16)(lookahead_pos - next_probe_pos)) > max_dist))   \
2043         return;                                                                                   \
2044     probe_pos = next_probe_pos & TDEFL_LZ_DICT_SIZE_MASK;                                         \
2045     if ((d->m_dict[probe_pos + match_len] == c0) && (d->m_dict[probe_pos + match_len - 1] == c1)) \
2046         break;
2047             TDEFL_PROBE;
2048             TDEFL_PROBE;
2049             TDEFL_PROBE;
2050         }
2051         if (!dist)
2052             break;
2053         p = s;
2054         q = d->m_dict + probe_pos;
2055         for (probe_len = 0; probe_len < max_match_len; probe_len++)
2056             if (*p++ != *q++)
2057                 break;
2058         if (probe_len > match_len)
2059         {
2060             *pMatch_dist = dist;
2061             if ((*pMatch_len = match_len = probe_len) == max_match_len)
2062                 return;
2063             c0 = d->m_dict[pos + match_len];
2064             c1 = d->m_dict[pos + match_len - 1];
2065         }
2066     }
2067 }
2068 #endif // #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES
2069
2070 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES &&MINIZ_LITTLE_ENDIAN
2071 static mz_bool tdefl_compress_fast(tdefl_compressor *d)
2072 {
2073     // Faster, minimally featured LZRW1-style match+parse loop with better register utilization. Intended for applications where raw throughput is valued more highly than ratio.
2074     mz_uint lookahead_pos = d->m_lookahead_pos, lookahead_size = d->m_lookahead_size, dict_size = d->m_dict_size, total_lz_bytes = d->m_total_lz_bytes, num_flags_left = d->m_num_flags_left;
2075     mz_uint8 *pLZ_code_buf = d->m_pLZ_code_buf, *pLZ_flags = d->m_pLZ_flags;
2076     mz_uint cur_pos = lookahead_pos & TDEFL_LZ_DICT_SIZE_MASK;
2077
2078     while ((d->m_src_buf_left) || ((d->m_flush) && (lookahead_size)))
2079     {
2080         const mz_uint TDEFL_COMP_FAST_LOOKAHEAD_SIZE = 4096;
2081         mz_uint dst_pos = (lookahead_pos + lookahead_size) & TDEFL_LZ_DICT_SIZE_MASK;
2082         mz_uint num_bytes_to_process = (mz_uint)MZ_MIN(d->m_src_buf_left, TDEFL_COMP_FAST_LOOKAHEAD_SIZE - lookahead_size);
2083         d->m_src_buf_left -= num_bytes_to_process;
2084         lookahead_size += num_bytes_to_process;
2085
2086         while (num_bytes_to_process)
2087         {
2088             mz_uint32 n = MZ_MIN(TDEFL_LZ_DICT_SIZE - dst_pos, num_bytes_to_process);
2089             memcpy(d->m_dict + dst_pos, d->m_pSrc, n);
2090             if (dst_pos < (TDEFL_MAX_MATCH_LEN - 1))
2091                 memcpy(d->m_dict + TDEFL_LZ_DICT_SIZE + dst_pos, d->m_pSrc, MZ_MIN(n, (TDEFL_MAX_MATCH_LEN - 1) - dst_pos));
2092             d->m_pSrc += n;
2093             dst_pos = (dst_pos + n) & TDEFL_LZ_DICT_SIZE_MASK;
2094             num_bytes_to_process -= n;
2095         }
2096
2097         dict_size = MZ_MIN(TDEFL_LZ_DICT_SIZE - lookahead_size, dict_size);
2098         if ((!d->m_flush) && (lookahead_size < TDEFL_COMP_FAST_LOOKAHEAD_SIZE))
2099             break;
2100
2101         while (lookahead_size >= 4)
2102         {
2103             mz_uint cur_match_dist, cur_match_len = 1;
2104             mz_uint8 *pCur_dict = d->m_dict + cur_pos;
2105             mz_uint first_trigram = (*(const mz_uint32 *)pCur_dict) & 0xFFFFFF;
2106             mz_uint hash = (first_trigram ^ (first_trigram >> (24 - (TDEFL_LZ_HASH_BITS - 8)))) & TDEFL_LEVEL1_HASH_SIZE_MASK;
2107             mz_uint probe_pos = d->m_hash[hash];
2108             d->m_hash[hash] = (mz_uint16)lookahead_pos;
2109
2110             if (((cur_match_dist = (mz_uint16)(lookahead_pos - probe_pos)) <= dict_size) && ((*(const mz_uint32 *)(d->m_dict + (probe_pos &= TDEFL_LZ_DICT_SIZE_MASK)) & 0xFFFFFF) == first_trigram))
2111             {
2112                 const mz_uint16 *p = (const mz_uint16 *)pCur_dict;
2113                 const mz_uint16 *q = (const mz_uint16 *)(d->m_dict + probe_pos);
2114                 mz_uint32 probe_len = 32;
2115                 do
2116                 {
2117                 } while ((TDEFL_READ_UNALIGNED_WORD(++p) == TDEFL_READ_UNALIGNED_WORD(++q)) && (TDEFL_READ_UNALIGNED_WORD(++p) == TDEFL_READ_UNALIGNED_WORD(++q)) &&
2118                          (TDEFL_READ_UNALIGNED_WORD(++p) == TDEFL_READ_UNALIGNED_WORD(++q)) && (TDEFL_READ_UNALIGNED_WORD(++p) == TDEFL_READ_UNALIGNED_WORD(++q)) && (--probe_len > 0));
2119                 cur_match_len = ((mz_uint)(p - (const mz_uint16 *)pCur_dict) * 2) + (mz_uint)(*(const mz_uint8 *)p == *(const mz_uint8 *)q);
2120                 if (!probe_len)
2121                     cur_match_len = cur_match_dist ? TDEFL_MAX_MATCH_LEN : 0;
2122
2123                 if ((cur_match_len < TDEFL_MIN_MATCH_LEN) || ((cur_match_len == TDEFL_MIN_MATCH_LEN) && (cur_match_dist >= 8U * 1024U)))
2124                 {
2125                     cur_match_len = 1;
2126                     *pLZ_code_buf++ = (mz_uint8)first_trigram;
2127                     *pLZ_flags = (mz_uint8)(*pLZ_flags >> 1);
2128                     d->m_huff_count[0][(mz_uint8)first_trigram]++;
2129                 }
2130                 else
2131                 {
2132                     mz_uint32 s0, s1;
2133                     cur_match_len = MZ_MIN(cur_match_len, lookahead_size);
2134
2135                     MZ_ASSERT((cur_match_len >= TDEFL_MIN_MATCH_LEN) && (cur_match_dist >= 1) && (cur_match_dist <= TDEFL_LZ_DICT_SIZE));
2136
2137                     cur_match_dist--;
2138
2139                     pLZ_code_buf[0] = (mz_uint8)(cur_match_len - TDEFL_MIN_MATCH_LEN);
2140                     *(mz_uint16 *)(&pLZ_code_buf[1]) = (mz_uint16)cur_match_dist;
2141                     pLZ_code_buf += 3;
2142                     *pLZ_flags = (mz_uint8)((*pLZ_flags >> 1) | 0x80);
2143
2144                     s0 = s_tdefl_small_dist_sym[cur_match_dist & 511];
2145                     s1 = s_tdefl_large_dist_sym[cur_match_dist >> 8];
2146                     d->m_huff_count[1][(cur_match_dist < 512) ? s0 : s1]++;
2147
2148                     d->m_huff_count[0][s_tdefl_len_sym[cur_match_len - TDEFL_MIN_MATCH_LEN]]++;
2149                 }
2150             }
2151             else
2152             {
2153                 *pLZ_code_buf++ = (mz_uint8)first_trigram;
2154                 *pLZ_flags = (mz_uint8)(*pLZ_flags >> 1);
2155                 d->m_huff_count[0][(mz_uint8)first_trigram]++;
2156             }
2157
2158             if (--num_flags_left == 0)
2159             {
2160                 num_flags_left = 8;
2161                 pLZ_flags = pLZ_code_buf++;
2162             }
2163
2164             total_lz_bytes += cur_match_len;
2165             lookahead_pos += cur_match_len;
2166             dict_size = MZ_MIN(dict_size + cur_match_len, (mz_uint)TDEFL_LZ_DICT_SIZE);
2167             cur_pos = (cur_pos + cur_match_len) & TDEFL_LZ_DICT_SIZE_MASK;
2168             MZ_ASSERT(lookahead_size >= cur_match_len);
2169             lookahead_size -= cur_match_len;
2170
2171             if (pLZ_code_buf > &d->m_lz_code_buf[TDEFL_LZ_CODE_BUF_SIZE - 8])
2172             {
2173                 int n;
2174                 d->m_lookahead_pos = lookahead_pos;
2175                 d->m_lookahead_size = lookahead_size;
2176                 d->m_dict_size = dict_size;
2177                 d->m_total_lz_bytes = total_lz_bytes;
2178                 d->m_pLZ_code_buf = pLZ_code_buf;
2179                 d->m_pLZ_flags = pLZ_flags;
2180                 d->m_num_flags_left = num_flags_left;
2181                 if ((n = tdefl_flush_block(d, 0)) != 0)
2182                     return (n < 0) ? MZ_FALSE : MZ_TRUE;
2183                 total_lz_bytes = d->m_total_lz_bytes;
2184                 pLZ_code_buf = d->m_pLZ_code_buf;
2185                 pLZ_flags = d->m_pLZ_flags;
2186                 num_flags_left = d->m_num_flags_left;
2187             }
2188         }
2189
2190         while (lookahead_size)
2191         {
2192             mz_uint8 lit = d->m_dict[cur_pos];
2193
2194             total_lz_bytes++;
2195             *pLZ_code_buf++ = lit;
2196             *pLZ_flags = (mz_uint8)(*pLZ_flags >> 1);
2197             if (--num_flags_left == 0)
2198             {
2199                 num_flags_left = 8;
2200                 pLZ_flags = pLZ_code_buf++;
2201             }
2202
2203             d->m_huff_count[0][lit]++;
2204
2205             lookahead_pos++;
2206             dict_size = MZ_MIN(dict_size + 1, (mz_uint)TDEFL_LZ_DICT_SIZE);
2207             cur_pos = (cur_pos + 1) & TDEFL_LZ_DICT_SIZE_MASK;
2208             lookahead_size--;
2209
2210             if (pLZ_code_buf > &d->m_lz_code_buf[TDEFL_LZ_CODE_BUF_SIZE - 8])
2211             {
2212                 int n;
2213                 d->m_lookahead_pos = lookahead_pos;
2214                 d->m_lookahead_size = lookahead_size;
2215                 d->m_dict_size = dict_size;
2216                 d->m_total_lz_bytes = total_lz_bytes;
2217                 d->m_pLZ_code_buf = pLZ_code_buf;
2218                 d->m_pLZ_flags = pLZ_flags;
2219                 d->m_num_flags_left = num_flags_left;
2220                 if ((n = tdefl_flush_block(d, 0)) != 0)
2221                     return (n < 0) ? MZ_FALSE : MZ_TRUE;
2222                 total_lz_bytes = d->m_total_lz_bytes;
2223                 pLZ_code_buf = d->m_pLZ_code_buf;
2224                 pLZ_flags = d->m_pLZ_flags;
2225                 num_flags_left = d->m_num_flags_left;
2226             }
2227         }
2228     }
2229
2230     d->m_lookahead_pos = lookahead_pos;
2231     d->m_lookahead_size = lookahead_size;
2232     d->m_dict_size = dict_size;
2233     d->m_total_lz_bytes = total_lz_bytes;
2234     d->m_pLZ_code_buf = pLZ_code_buf;
2235     d->m_pLZ_flags = pLZ_flags;
2236     d->m_num_flags_left = num_flags_left;
2237     return MZ_TRUE;
2238 }
2239 #endif // MINIZ_USE_UNALIGNED_LOADS_AND_STORES && MINIZ_LITTLE_ENDIAN
2240
2241 static MZ_FORCEINLINE void tdefl_record_literal(tdefl_compressor *d, mz_uint8 lit)
2242 {
2243     d->m_total_lz_bytes++;
2244     *d->m_pLZ_code_buf++ = lit;
2245     *d->m_pLZ_flags = (mz_uint8)(*d->m_pLZ_flags >> 1);
2246     if (--d->m_num_flags_left == 0)
2247     {
2248         d->m_num_flags_left = 8;
2249         d->m_pLZ_flags = d->m_pLZ_code_buf++;
2250     }
2251     d->m_huff_count[0][lit]++;
2252 }
2253
2254 static MZ_FORCEINLINE void tdefl_record_match(tdefl_compressor *d, mz_uint match_len, mz_uint match_dist)
2255 {
2256     mz_uint32 s0, s1;
2257
2258     MZ_ASSERT((match_len >= TDEFL_MIN_MATCH_LEN) && (match_dist >= 1) && (match_dist <= TDEFL_LZ_DICT_SIZE));
2259
2260     d->m_total_lz_bytes += match_len;
2261
2262     d->m_pLZ_code_buf[0] = (mz_uint8)(match_len - TDEFL_MIN_MATCH_LEN);
2263
2264     match_dist -= 1;
2265     d->m_pLZ_code_buf[1] = (mz_uint8)(match_dist & 0xFF);
2266     d->m_pLZ_code_buf[2] = (mz_uint8)(match_dist >> 8);
2267     d->m_pLZ_code_buf += 3;
2268
2269     *d->m_pLZ_flags = (mz_uint8)((*d->m_pLZ_flags >> 1) | 0x80);
2270     if (--d->m_num_flags_left == 0)
2271     {
2272         d->m_num_flags_left = 8;
2273         d->m_pLZ_flags = d->m_pLZ_code_buf++;
2274     }
2275
2276     s0 = s_tdefl_small_dist_sym[match_dist & 511];
2277     s1 = s_tdefl_large_dist_sym[(match_dist >> 8) & 127];
2278     d->m_huff_count[1][(match_dist < 512) ? s0 : s1]++;
2279
2280     if (match_len >= TDEFL_MIN_MATCH_LEN)
2281         d->m_huff_count[0][s_tdefl_len_sym[match_len - TDEFL_MIN_MATCH_LEN]]++;
2282 }
2283
2284 static mz_bool tdefl_compress_normal(tdefl_compressor *d)
2285 {
2286     const mz_uint8 *pSrc = d->m_pSrc;
2287     size_t src_buf_left = d->m_src_buf_left;
2288     tdefl_flush flush = d->m_flush;
2289
2290     while ((src_buf_left) || ((flush) && (d->m_lookahead_size)))
2291     {
2292         mz_uint len_to_move, cur_match_dist, cur_match_len, cur_pos;
2293         // Update dictionary and hash chains. Keeps the lookahead size equal to TDEFL_MAX_MATCH_LEN.
2294         if ((d->m_lookahead_size + d->m_dict_size) >= (TDEFL_MIN_MATCH_LEN - 1))
2295         {
2296             mz_uint dst_pos = (d->m_lookahead_pos + d->m_lookahead_size) & TDEFL_LZ_DICT_SIZE_MASK, ins_pos = d->m_lookahead_pos + d->m_lookahead_size - 2;
2297             mz_uint hash = (d->m_dict[ins_pos & TDEFL_LZ_DICT_SIZE_MASK] << TDEFL_LZ_HASH_SHIFT) ^ d->m_dict[(ins_pos + 1) & TDEFL_LZ_DICT_SIZE_MASK];
2298             mz_uint num_bytes_to_process = (mz_uint)MZ_MIN(src_buf_left, TDEFL_MAX_MATCH_LEN - d->m_lookahead_size);
2299             const mz_uint8 *pSrc_end = pSrc + num_bytes_to_process;
2300             src_buf_left -= num_bytes_to_process;
2301             d->m_lookahead_size += num_bytes_to_process;
2302             while (pSrc != pSrc_end)
2303             {
2304                 mz_uint8 c = *pSrc++;
2305                 d->m_dict[dst_pos] = c;
2306                 if (dst_pos < (TDEFL_MAX_MATCH_LEN - 1))
2307                     d->m_dict[TDEFL_LZ_DICT_SIZE + dst_pos] = c;
2308                 hash = ((hash << TDEFL_LZ_HASH_SHIFT) ^ c) & (TDEFL_LZ_HASH_SIZE - 1);
2309                 d->m_next[ins_pos & TDEFL_LZ_DICT_SIZE_MASK] = d->m_hash[hash];
2310                 d->m_hash[hash] = (mz_uint16)(ins_pos);
2311                 dst_pos = (dst_pos + 1) & TDEFL_LZ_DICT_SIZE_MASK;
2312                 ins_pos++;
2313             }
2314         }
2315         else
2316         {
2317             while ((src_buf_left) && (d->m_lookahead_size < TDEFL_MAX_MATCH_LEN))
2318             {
2319                 mz_uint8 c = *pSrc++;
2320                 mz_uint dst_pos = (d->m_lookahead_pos + d->m_lookahead_size) & TDEFL_LZ_DICT_SIZE_MASK;
2321                 src_buf_left--;
2322                 d->m_dict[dst_pos] = c;
2323                 if (dst_pos < (TDEFL_MAX_MATCH_LEN - 1))
2324                     d->m_dict[TDEFL_LZ_DICT_SIZE + dst_pos] = c;
2325                 if ((++d->m_lookahead_size + d->m_dict_size) >= TDEFL_MIN_MATCH_LEN)
2326                 {
2327                     mz_uint ins_pos = d->m_lookahead_pos + (d->m_lookahead_size - 1) - 2;
2328                     mz_uint hash = ((d->m_dict[ins_pos & TDEFL_LZ_DICT_SIZE_MASK] << (TDEFL_LZ_HASH_SHIFT * 2)) ^ (d->m_dict[(ins_pos + 1) & TDEFL_LZ_DICT_SIZE_MASK] << TDEFL_LZ_HASH_SHIFT) ^ c) & (TDEFL_LZ_HASH_SIZE - 1);
2329                     d->m_next[ins_pos & TDEFL_LZ_DICT_SIZE_MASK] = d->m_hash[hash];
2330                     d->m_hash[hash] = (mz_uint16)(ins_pos);
2331                 }
2332             }
2333         }
2334         d->m_dict_size = MZ_MIN(TDEFL_LZ_DICT_SIZE - d->m_lookahead_size, d->m_dict_size);
2335         if ((!flush) && (d->m_lookahead_size < TDEFL_MAX_MATCH_LEN))
2336             break;
2337
2338         // Simple lazy/greedy parsing state machine.
2339         len_to_move = 1;
2340         cur_match_dist = 0;
2341         cur_match_len = d->m_saved_match_len ? d->m_saved_match_len : (TDEFL_MIN_MATCH_LEN - 1);
2342         cur_pos = d->m_lookahead_pos & TDEFL_LZ_DICT_SIZE_MASK;
2343         if (d->m_flags & (TDEFL_RLE_MATCHES | TDEFL_FORCE_ALL_RAW_BLOCKS))
2344         {
2345             if ((d->m_dict_size) && (!(d->m_flags & TDEFL_FORCE_ALL_RAW_BLOCKS)))
2346             {
2347                 mz_uint8 c = d->m_dict[(cur_pos - 1) & TDEFL_LZ_DICT_SIZE_MASK];
2348                 cur_match_len = 0;
2349                 while (cur_match_len < d->m_lookahead_size)
2350                 {
2351                     if (d->m_dict[cur_pos + cur_match_len] != c)
2352                         break;
2353                     cur_match_len++;
2354                 }
2355                 if (cur_match_len < TDEFL_MIN_MATCH_LEN)
2356                     cur_match_len = 0;
2357                 else
2358                     cur_match_dist = 1;
2359             }
2360         }
2361         else
2362         {
2363             tdefl_find_match(d, d->m_lookahead_pos, d->m_dict_size, d->m_lookahead_size, &cur_match_dist, &cur_match_len);
2364         }
2365         if (((cur_match_len == TDEFL_MIN_MATCH_LEN) && (cur_match_dist >= 8U * 1024U)) || (cur_pos == cur_match_dist) || ((d->m_flags & TDEFL_FILTER_MATCHES) && (cur_match_len <= 5)))
2366         {
2367             cur_match_dist = cur_match_len = 0;
2368         }
2369         if (d->m_saved_match_len)
2370         {
2371             if (cur_match_len > d->m_saved_match_len)
2372             {
2373                 tdefl_record_literal(d, (mz_uint8)d->m_saved_lit);
2374                 if (cur_match_len >= 128)
2375                 {
2376                     tdefl_record_match(d, cur_match_len, cur_match_dist);
2377                     d->m_saved_match_len = 0;
2378                     len_to_move = cur_match_len;
2379                 }
2380                 else
2381                 {
2382                     d->m_saved_lit = d->m_dict[cur_pos];
2383                     d->m_saved_match_dist = cur_match_dist;
2384                     d->m_saved_match_len = cur_match_len;
2385                 }
2386             }
2387             else
2388             {
2389                 tdefl_record_match(d, d->m_saved_match_len, d->m_saved_match_dist);
2390                 len_to_move = d->m_saved_match_len - 1;
2391                 d->m_saved_match_len = 0;
2392             }
2393         }
2394         else if (!cur_match_dist)
2395             tdefl_record_literal(d, d->m_dict[MZ_MIN(cur_pos, sizeof(d->m_dict) - 1)]);
2396         else if ((d->m_greedy_parsing) || (d->m_flags & TDEFL_RLE_MATCHES) || (cur_match_len >= 128))
2397         {
2398             tdefl_record_match(d, cur_match_len, cur_match_dist);
2399             len_to_move = cur_match_len;
2400         }
2401         else
2402         {
2403             d->m_saved_lit = d->m_dict[MZ_MIN(cur_pos, sizeof(d->m_dict) - 1)];
2404             d->m_saved_match_dist = cur_match_dist;
2405             d->m_saved_match_len = cur_match_len;
2406         }
2407         // Move the lookahead forward by len_to_move bytes.
2408         d->m_lookahead_pos += len_to_move;
2409         MZ_ASSERT(d->m_lookahead_size >= len_to_move);
2410         d->m_lookahead_size -= len_to_move;
2411         d->m_dict_size = MZ_MIN(d->m_dict_size + len_to_move, (mz_uint)TDEFL_LZ_DICT_SIZE);
2412         // Check if it's time to flush the current LZ codes to the internal output buffer.
2413         if ((d->m_pLZ_code_buf > &d->m_lz_code_buf[TDEFL_LZ_CODE_BUF_SIZE - 8]) ||
2414             ((d->m_total_lz_bytes > 31 * 1024) && (((((mz_uint)(d->m_pLZ_code_buf - d->m_lz_code_buf) * 115) >> 7) >= d->m_total_lz_bytes) || (d->m_flags & TDEFL_FORCE_ALL_RAW_BLOCKS))))
2415         {
2416             int n;
2417             d->m_pSrc = pSrc;
2418             d->m_src_buf_left = src_buf_left;
2419             if ((n = tdefl_flush_block(d, 0)) != 0)
2420                 return (n < 0) ? MZ_FALSE : MZ_TRUE;
2421         }
2422     }
2423
2424     d->m_pSrc = pSrc;
2425     d->m_src_buf_left = src_buf_left;
2426     return MZ_TRUE;
2427 }
2428
2429 static tdefl_status tdefl_flush_output_buffer(tdefl_compressor *d)
2430 {
2431     if (d->m_pIn_buf_size)
2432     {
2433         *d->m_pIn_buf_size = d->m_pSrc - (const mz_uint8 *)d->m_pIn_buf;
2434     }
2435
2436     if (d->m_pOut_buf_size)
2437     {
2438         size_t n = MZ_MIN(*d->m_pOut_buf_size - d->m_out_buf_ofs, d->m_output_flush_remaining);
2439         memcpy((mz_uint8 *)d->m_pOut_buf + d->m_out_buf_ofs, d->m_output_buf + d->m_output_flush_ofs, n);
2440         d->m_output_flush_ofs += (mz_uint)n;
2441         d->m_output_flush_remaining -= (mz_uint)n;
2442         d->m_out_buf_ofs += n;
2443
2444         *d->m_pOut_buf_size = d->m_out_buf_ofs;
2445     }
2446
2447     return (d->m_finished && !d->m_output_flush_remaining) ? TDEFL_STATUS_DONE : TDEFL_STATUS_OKAY;
2448 }
2449
2450 tdefl_status tdefl_compress(tdefl_compressor *d, const void *pIn_buf, size_t *pIn_buf_size, void *pOut_buf, size_t *pOut_buf_size, tdefl_flush flush)
2451 {
2452     if (!d)
2453     {
2454         if (pIn_buf_size)
2455             *pIn_buf_size = 0;
2456         if (pOut_buf_size)
2457             *pOut_buf_size = 0;
2458         return TDEFL_STATUS_BAD_PARAM;
2459     }
2460
2461     d->m_pIn_buf = pIn_buf;
2462     d->m_pIn_buf_size = pIn_buf_size;
2463     d->m_pOut_buf = pOut_buf;
2464     d->m_pOut_buf_size = pOut_buf_size;
2465     d->m_pSrc = (const mz_uint8 *)(pIn_buf);
2466     d->m_src_buf_left = pIn_buf_size ? *pIn_buf_size : 0;
2467     d->m_out_buf_ofs = 0;
2468     d->m_flush = flush;
2469
2470     if (((d->m_pPut_buf_func != NULL) == ((pOut_buf != NULL) || (pOut_buf_size != NULL))) || (d->m_prev_return_status != TDEFL_STATUS_OKAY) ||
2471         (d->m_wants_to_finish && (flush != TDEFL_FINISH)) || (pIn_buf_size && *pIn_buf_size && !pIn_buf) || (pOut_buf_size && *pOut_buf_size && !pOut_buf))
2472     {
2473         if (pIn_buf_size)
2474             *pIn_buf_size = 0;
2475         if (pOut_buf_size)
2476             *pOut_buf_size = 0;
2477         return (d->m_prev_return_status = TDEFL_STATUS_BAD_PARAM);
2478     }
2479     d->m_wants_to_finish |= (flush == TDEFL_FINISH);
2480
2481     if ((d->m_output_flush_remaining) || (d->m_finished))
2482         return (d->m_prev_return_status = tdefl_flush_output_buffer(d));
2483
2484 #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES &&MINIZ_LITTLE_ENDIAN
2485     if (((d->m_flags & TDEFL_MAX_PROBES_MASK) == 1) &&
2486         ((d->m_flags & TDEFL_GREEDY_PARSING_FLAG) != 0) &&
2487         ((d->m_flags & (TDEFL_FILTER_MATCHES | TDEFL_FORCE_ALL_RAW_BLOCKS | TDEFL_RLE_MATCHES)) == 0))
2488     {
2489         if (!tdefl_compress_fast(d))
2490             return d->m_prev_return_status;
2491     }
2492     else
2493 #endif // #if MINIZ_USE_UNALIGNED_LOADS_AND_STORES && MINIZ_LITTLE_ENDIAN
2494     {
2495         if (!tdefl_compress_normal(d))
2496             return d->m_prev_return_status;
2497     }
2498
2499     if ((d->m_flags & (TDEFL_WRITE_ZLIB_HEADER | TDEFL_COMPUTE_ADLER32)) && (pIn_buf))
2500         d->m_adler32 = (mz_uint32)mz_adler32(d->m_adler32, (const mz_uint8 *)pIn_buf, d->m_pSrc - (const mz_uint8 *)pIn_buf);
2501
2502     if ((flush) && (!d->m_lookahead_size) && (!d->m_src_buf_left) && (!d->m_output_flush_remaining))
2503     {
2504         if (tdefl_flush_block(d, flush) < 0)
2505             return d->m_prev_return_status;
2506         d->m_finished = (flush == TDEFL_FINISH);
2507         if (flush == TDEFL_FULL_FLUSH)
2508         {
2509             MZ_CLEAR_OBJ(d->m_hash);
2510             MZ_CLEAR_OBJ(d->m_next);
2511             d->m_dict_size = 0;
2512         }
2513     }
2514
2515     return (d->m_prev_return_status = tdefl_flush_output_buffer(d));
2516 }
2517
2518 tdefl_status tdefl_compress_buffer(tdefl_compressor *d, const void *pIn_buf, size_t in_buf_size, tdefl_flush flush)
2519 {
2520     MZ_ASSERT(d->m_pPut_buf_func);
2521     return tdefl_compress(d, pIn_buf, &in_buf_size, NULL, NULL, flush);
2522 }
2523
2524 tdefl_status tdefl_init(tdefl_compressor *d, tdefl_put_buf_func_ptr pPut_buf_func, void *pPut_buf_user, int flags)
2525 {
2526     d->m_pPut_buf_func = pPut_buf_func;
2527     d->m_pPut_buf_user = pPut_buf_user;
2528     d->m_flags = (mz_uint)(flags);
2529     d->m_max_probes[0] = 1 + ((flags & 0xFFF) + 2) / 3;
2530     d->m_greedy_parsing = (flags & TDEFL_GREEDY_PARSING_FLAG) != 0;
2531     d->m_max_probes[1] = 1 + (((flags & 0xFFF) >> 2) + 2) / 3;
2532     if (!(flags & TDEFL_NONDETERMINISTIC_PARSING_FLAG))
2533         MZ_CLEAR_OBJ(d->m_hash);
2534     d->m_lookahead_pos = d->m_lookahead_size = d->m_dict_size = d->m_total_lz_bytes = d->m_lz_code_buf_dict_pos = d->m_bits_in = 0;
2535     d->m_output_flush_ofs = d->m_output_flush_remaining = d->m_finished = d->m_block_index = d->m_bit_buffer = d->m_wants_to_finish = 0;
2536     d->m_pLZ_code_buf = d->m_lz_code_buf + 1;
2537     d->m_pLZ_flags = d->m_lz_code_buf;
2538     d->m_num_flags_left = 8;
2539     d->m_pOutput_buf = d->m_output_buf;
2540     d->m_pOutput_buf_end = d->m_output_buf;
2541     d->m_prev_return_status = TDEFL_STATUS_OKAY;
2542     d->m_saved_match_dist = d->m_saved_match_len = d->m_saved_lit = 0;
2543     d->m_adler32 = 1;
2544     d->m_pIn_buf = NULL;
2545     d->m_pOut_buf = NULL;
2546     d->m_pIn_buf_size = NULL;
2547     d->m_pOut_buf_size = NULL;
2548     d->m_flush = TDEFL_NO_FLUSH;
2549     d->m_pSrc = NULL;
2550     d->m_src_buf_left = 0;
2551     d->m_out_buf_ofs = 0;
2552     memset(&d->m_huff_count[0][0], 0, sizeof(d->m_huff_count[0][0]) * TDEFL_MAX_HUFF_SYMBOLS_0);
2553     memset(&d->m_huff_count[1][0], 0, sizeof(d->m_huff_count[1][0]) * TDEFL_MAX_HUFF_SYMBOLS_1);
2554     return TDEFL_STATUS_OKAY;
2555 }
2556
2557 tdefl_status tdefl_get_prev_return_status(tdefl_compressor *d)
2558 {
2559     return d->m_prev_return_status;
2560 }
2561
2562 mz_uint32 tdefl_get_adler32(tdefl_compressor *d)
2563 {
2564     return d->m_adler32;
2565 }
2566
2567 mz_bool tdefl_compress_mem_to_output(const void *pBuf, size_t buf_len, tdefl_put_buf_func_ptr pPut_buf_func, void *pPut_buf_user, int flags)
2568 {
2569     tdefl_compressor *pComp;
2570     mz_bool succeeded;
2571     if (((buf_len) && (!pBuf)) || (!pPut_buf_func))
2572         return MZ_FALSE;
2573     pComp = (tdefl_compressor *)MZ_MALLOC(sizeof(tdefl_compressor));
2574     if (!pComp)
2575         return MZ_FALSE;
2576     succeeded = (tdefl_init(pComp, pPut_buf_func, pPut_buf_user, flags) == TDEFL_STATUS_OKAY);
2577     succeeded = succeeded && (tdefl_compress_buffer(pComp, pBuf, buf_len, TDEFL_FINISH) == TDEFL_STATUS_DONE);
2578     MZ_FREE(pComp);
2579     return succeeded;
2580 }
2581
2582 typedef struct
2583 {
2584     size_t m_size, m_capacity;
2585     mz_uint8 *m_pBuf;
2586     mz_bool m_expandable;
2587 } tdefl_output_buffer;
2588
2589 static mz_bool tdefl_output_buffer_putter(const void *pBuf, int len, void *pUser)
2590 {
2591     tdefl_output_buffer *p = (tdefl_output_buffer *)pUser;
2592     size_t new_size = p->m_size + len;
2593     if (new_size > p->m_capacity)
2594     {
2595         size_t new_capacity = p->m_capacity;
2596         mz_uint8 *pNew_buf;
2597         if (!p->m_expandable)
2598             return MZ_FALSE;
2599         do
2600         {
2601             new_capacity = MZ_MAX(128U, new_capacity << 1U);
2602         } while (new_size > new_capacity);
2603         pNew_buf = (mz_uint8 *)MZ_REALLOC(p->m_pBuf, new_capacity);
2604         if (!pNew_buf)
2605             return MZ_FALSE;
2606         p->m_pBuf = pNew_buf;
2607         p->m_capacity = new_capacity;
2608     }
2609     memcpy((mz_uint8 *)p->m_pBuf + p->m_size, pBuf, len);
2610     p->m_size = new_size;
2611     return MZ_TRUE;
2612 }
2613
2614 void *tdefl_compress_mem_to_heap(const void *pSrc_buf, size_t src_buf_len, size_t *pOut_len, int flags)
2615 {
2616     tdefl_output_buffer out_buf;
2617     MZ_CLEAR_OBJ(out_buf);
2618     if (!pOut_len)
2619         return MZ_FALSE;
2620     else
2621         *pOut_len = 0;
2622     out_buf.m_expandable = MZ_TRUE;
2623     if (!tdefl_compress_mem_to_output(pSrc_buf, src_buf_len, tdefl_output_buffer_putter, &out_buf, flags))
2624         return NULL;
2625     *pOut_len = out_buf.m_size;
2626     return out_buf.m_pBuf;
2627 }
2628
2629 size_t tdefl_compress_mem_to_mem(void *pOut_buf, size_t out_buf_len, const void *pSrc_buf, size_t src_buf_len, int flags)
2630 {
2631     tdefl_output_buffer out_buf;
2632     MZ_CLEAR_OBJ(out_buf);
2633     if (!pOut_buf)
2634         return 0;
2635     out_buf.m_pBuf = (mz_uint8 *)pOut_buf;
2636     out_buf.m_capacity = out_buf_len;
2637     if (!tdefl_compress_mem_to_output(pSrc_buf, src_buf_len, tdefl_output_buffer_putter, &out_buf, flags))
2638         return 0;
2639     return out_buf.m_size;
2640 }
2641
2642 #ifndef MINIZ_NO_ZLIB_APIS
2643 static const mz_uint s_tdefl_num_probes[11] = { 0, 1, 6, 32, 16, 32, 128, 256, 512, 768, 1500 };
2644
2645 // level may actually range from [0,10] (10 is a "hidden" max level, where we want a bit more compression and it's fine if throughput to fall off a cliff on some files).
2646 mz_uint tdefl_create_comp_flags_from_zip_params(int level, int window_bits, int strategy)
2647 {
2648     mz_uint comp_flags = s_tdefl_num_probes[(level >= 0) ? MZ_MIN(10, level) : MZ_DEFAULT_LEVEL] | ((level <= 3) ? TDEFL_GREEDY_PARSING_FLAG : 0);
2649     if (window_bits > 0)
2650         comp_flags |= TDEFL_WRITE_ZLIB_HEADER;
2651
2652     if (!level)
2653         comp_flags |= TDEFL_FORCE_ALL_RAW_BLOCKS;
2654     else if (strategy == MZ_FILTERED)
2655         comp_flags |= TDEFL_FILTER_MATCHES;
2656     else if (strategy == MZ_HUFFMAN_ONLY)
2657         comp_flags &= ~TDEFL_MAX_PROBES_MASK;
2658     else if (strategy == MZ_FIXED)
2659         comp_flags |= TDEFL_FORCE_ALL_STATIC_BLOCKS;
2660     else if (strategy == MZ_RLE)
2661         comp_flags |= TDEFL_RLE_MATCHES;
2662
2663     return comp_flags;
2664 }
2665 #endif //MINIZ_NO_ZLIB_APIS
2666
2667 #ifdef _MSC_VER
2668 #pragma warning(push)
2669 #pragma warning(disable : 4204) // nonstandard extension used : non-constant aggregate initializer (also supported by GNU C and C99, so no big deal)
2670 #endif
2671
2672 // Simple PNG writer function by Alex Evans, 2011. Released into the public domain: https://gist.github.com/908299, more context at
2673 // http://altdevblogaday.org/2011/04/06/a-smaller-jpg-encoder/.
2674 // This is actually a modification of Alex's original code so PNG files generated by this function pass pngcheck.
2675 void *tdefl_write_image_to_png_file_in_memory_ex(const void *pImage, int w, int h, int num_chans, size_t *pLen_out, mz_uint level, mz_bool flip)
2676 {
2677     // Using a local copy of this array here in case MINIZ_NO_ZLIB_APIS was defined.
2678     static const mz_uint s_tdefl_png_num_probes[11] = { 0, 1, 6, 32, 16, 32, 128, 256, 512, 768, 1500 };
2679     tdefl_compressor *pComp = (tdefl_compressor *)MZ_MALLOC(sizeof(tdefl_compressor));
2680     tdefl_output_buffer out_buf;
2681     int i, bpl = w * num_chans, y, z;
2682     mz_uint32 c;
2683     *pLen_out = 0;
2684     if (!pComp)
2685         return NULL;
2686     MZ_CLEAR_OBJ(out_buf);
2687     out_buf.m_expandable = MZ_TRUE;
2688     out_buf.m_capacity = 57 + MZ_MAX(64, (1 + bpl) * h);
2689     if (NULL == (out_buf.m_pBuf = (mz_uint8 *)MZ_MALLOC(out_buf.m_capacity)))
2690     {
2691         MZ_FREE(pComp);
2692         return NULL;
2693     }
2694     // write dummy header
2695     for (z = 41; z; --z)
2696         tdefl_output_buffer_putter(&z, 1, &out_buf);
2697     // compress image data
2698     tdefl_init(pComp, tdefl_output_buffer_putter, &out_buf, s_tdefl_png_num_probes[MZ_MIN(10, level)] | TDEFL_WRITE_ZLIB_HEADER);
2699     for (y = 0; y < h; ++y)
2700     {
2701         tdefl_compress_buffer(pComp, &z, 1, TDEFL_NO_FLUSH);
2702         tdefl_compress_buffer(pComp, (mz_uint8 *)pImage + (flip ? (h - 1 - y) : y) * bpl, bpl, TDEFL_NO_FLUSH);
2703     }
2704     if (tdefl_compress_buffer(pComp, NULL, 0, TDEFL_FINISH) != TDEFL_STATUS_DONE)
2705     {
2706         MZ_FREE(pComp);
2707         MZ_FREE(out_buf.m_pBuf);
2708         return NULL;
2709     }
2710     // write real header
2711     *pLen_out = out_buf.m_size - 41;
2712     {
2713         static const mz_uint8 chans[] = { 0x00, 0x00, 0x04, 0x02, 0x06 };
2714         mz_uint8 pnghdr[41] = { 0x89, 0x50, 0x4e, 0x47, 0x0d, 0x0a, 0x1a, 0x0a, 0x00, 0x00, 0x00, 0x0d, 0x49, 0x48, 0x44, 0x52,
2715                                 0, 0, (mz_uint8)(w >> 8), (mz_uint8)w, 0, 0, (mz_uint8)(h >> 8), (mz_uint8)h, 8, chans[num_chans], 0, 0, 0, 0, 0, 0, 0,
2716                                 (mz_uint8)(*pLen_out >> 24), (mz_uint8)(*pLen_out >> 16), (mz_uint8)(*pLen_out >> 8), (mz_uint8) * pLen_out, 0x49, 0x44, 0x41, 0x54 };
2717         c = (mz_uint32)mz_crc32(MZ_CRC32_INIT, pnghdr + 12, 17);
2718         for (i = 0; i < 4; ++i, c <<= 8)
2719             ((mz_uint8 *)(pnghdr + 29))[i] = (mz_uint8)(c >> 24);
2720         memcpy(out_buf.m_pBuf, pnghdr, 41);
2721     }
2722     // write footer (IDAT CRC-32, followed by IEND chunk)
2723     if (!tdefl_output_buffer_putter("\0\0\0\0\0\0\0\0\x49\x45\x4e\x44\xae\x42\x60\x82", 16, &out_buf))
2724     {
2725         *pLen_out = 0;
2726         MZ_FREE(pComp);
2727         MZ_FREE(out_buf.m_pBuf);
2728         return NULL;
2729     }
2730     c = (mz_uint32)mz_crc32(MZ_CRC32_INIT, out_buf.m_pBuf + 41 - 4, *pLen_out + 4);
2731     for (i = 0; i < 4; ++i, c <<= 8)
2732         (out_buf.m_pBuf + out_buf.m_size - 16)[i] = (mz_uint8)(c >> 24);
2733     // compute final size of file, grab compressed data buffer and return
2734     *pLen_out += 57;
2735     MZ_FREE(pComp);
2736     return out_buf.m_pBuf;
2737 }
2738 void *tdefl_write_image_to_png_file_in_memory(const void *pImage, int w, int h, int num_chans, size_t *pLen_out)
2739 {
2740     // Level 6 corresponds to TDEFL_DEFAULT_MAX_PROBES or MZ_DEFAULT_LEVEL (but we can't depend on MZ_DEFAULT_LEVEL being available in case the zlib API's where #defined out)
2741     return tdefl_write_image_to_png_file_in_memory_ex(pImage, w, h, num_chans, pLen_out, 6, MZ_FALSE);
2742 }
2743
2744 #ifdef _MSC_VER
2745 #pragma warning(pop)
2746 #endif
2747
2748 #ifdef __cplusplus
2749 }
2750 #endif
2751
2752 /*
2753   This is free and unencumbered software released into the public domain.
2754
2755   Anyone is free to copy, modify, publish, use, compile, sell, or
2756   distribute this software, either in source code form or as a compiled
2757   binary, for any purpose, commercial or non-commercial, and by any
2758   means.
2759
2760   In jurisdictions that recognize copyright laws, the author or authors
2761   of this software dedicate any and all copyright interest in the
2762   software to the public domain. We make this dedication for the benefit
2763   of the public at large and to the detriment of our heirs and
2764   successors. We intend this dedication to be an overt act of
2765   relinquishment in perpetuity of all present and future rights to this
2766   software under copyright law.
2767
2768   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
2769   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
2770   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
2771   IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
2772   OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
2773   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
2774   OTHER DEALINGS IN THE SOFTWARE.
2775
2776   For more information, please refer to <http://unlicense.org/>
2777 */