Home | History | Annotate | Download | only in lodepng
      1 /*
      2 LodePNG version 20131222
      3 
      4 Copyright (c) 2005-2013 Lode Vandevenne
      5 
      6 This software is provided 'as-is', without any express or implied
      7 warranty. In no event will the authors be held liable for any damages
      8 arising from the use of this software.
      9 
     10 Permission is granted to anyone to use this software for any purpose,
     11 including commercial applications, and to alter it and redistribute it
     12 freely, subject to the following restrictions:
     13 
     14     1. The origin of this software must not be misrepresented; you must not
     15     claim that you wrote the original software. If you use this software
     16     in a product, an acknowledgment in the product documentation would be
     17     appreciated but is not required.
     18 
     19     2. Altered source versions must be plainly marked as such, and must not be
     20     misrepresented as being the original software.
     21 
     22     3. This notice may not be removed or altered from any source
     23     distribution.
     24 */
     25 
     26 /*
     27 The manual and changelog are in the header file "lodepng.h"
     28 Rename this file to lodepng.cpp to use it for C++, or to lodepng.c to use it for C.
     29 */
     30 
     31 #include "lodepng.h"
     32 
     33 #include <stdio.h>
     34 #include <stdlib.h>
     35 
     36 #ifdef LODEPNG_COMPILE_CPP
     37 #include <fstream>
     38 #endif /*LODEPNG_COMPILE_CPP*/
     39 
     40 #define VERSION_STRING "20131222"
     41 
     42 /*
     43 This source file is built up in the following large parts. The code sections
     44 with the "LODEPNG_COMPILE_" #defines divide this up further in an intermixed way.
     45 -Tools for C and common code for PNG and Zlib
     46 -C Code for Zlib (huffman, deflate, ...)
     47 -C Code for PNG (file format chunks, adam7, PNG filters, color conversions, ...)
     48 -The C++ wrapper around all of the above
     49 */
     50 
     51 /*The malloc, realloc and free functions defined here with "lodepng_" in front
     52 of the name, so that you can easily change them to others related to your
     53 platform if needed. Everything else in the code calls these. Pass
     54 -DLODEPNG_NO_COMPILE_ALLOCATORS to the compiler, or comment out
     55 #define LODEPNG_COMPILE_ALLOCATORS in the header, to disable the ones here and
     56 define them in your own project's source files without needing to change
     57 lodepng source code. Don't forget to remove "static" if you copypaste them
     58 from here.*/
     59 
     60 #ifdef LODEPNG_COMPILE_ALLOCATORS
     61 static void* lodepng_malloc(size_t size)
     62 {
     63   return malloc(size);
     64 }
     65 
     66 static void* lodepng_realloc(void* ptr, size_t new_size)
     67 {
     68   return realloc(ptr, new_size);
     69 }
     70 
     71 static void lodepng_free(void* ptr)
     72 {
     73   free(ptr);
     74 }
     75 #else /*LODEPNG_COMPILE_ALLOCATORS*/
     76 void* lodepng_malloc(size_t size);
     77 void* lodepng_realloc(void* ptr, size_t new_size);
     78 void lodepng_free(void* ptr);
     79 #endif /*LODEPNG_COMPILE_ALLOCATORS*/
     80 
     81 /* ////////////////////////////////////////////////////////////////////////// */
     82 /* ////////////////////////////////////////////////////////////////////////// */
     83 /* // Tools for C, and common code for PNG and Zlib.                       // */
     84 /* ////////////////////////////////////////////////////////////////////////// */
     85 /* ////////////////////////////////////////////////////////////////////////// */
     86 
     87 /*
     88 Often in case of an error a value is assigned to a variable and then it breaks
     89 out of a loop (to go to the cleanup phase of a function). This macro does that.
     90 It makes the error handling code shorter and more readable.
     91 
     92 Example: if(!uivector_resizev(&frequencies_ll, 286, 0)) ERROR_BREAK(83);
     93 */
     94 #define CERROR_BREAK(errorvar, code)\
     95 {\
     96   errorvar = code;\
     97   break;\
     98 }
     99 
    100 /*version of CERROR_BREAK that assumes the common case where the error variable is named "error"*/
    101 #define ERROR_BREAK(code) CERROR_BREAK(error, code)
    102 
    103 /*Set error var to the error code, and return it.*/
    104 #define CERROR_RETURN_ERROR(errorvar, code)\
    105 {\
    106   errorvar = code;\
    107   return code;\
    108 }
    109 
    110 /*Try the code, if it returns error, also return the error.*/
    111 #define CERROR_TRY_RETURN(call)\
    112 {\
    113   unsigned error = call;\
    114   if(error) return error;\
    115 }
    116 
    117 /*
    118 About uivector, ucvector and string:
    119 -All of them wrap dynamic arrays or text strings in a similar way.
    120 -LodePNG was originally written in C++. The vectors replace the std::vectors that were used in the C++ version.
    121 -The string tools are made to avoid problems with compilers that declare things like strncat as deprecated.
    122 -They're not used in the interface, only internally in this file as static functions.
    123 -As with many other structs in this file, the init and cleanup functions serve as ctor and dtor.
    124 */
    125 
    126 #ifdef LODEPNG_COMPILE_ZLIB
    127 /*dynamic vector of unsigned ints*/
    128 typedef struct uivector
    129 {
    130   unsigned* data;
    131   size_t size; /*size in number of unsigned longs*/
    132   size_t allocsize; /*allocated size in bytes*/
    133 } uivector;
    134 
    135 static void uivector_cleanup(void* p)
    136 {
    137   ((uivector*)p)->size = ((uivector*)p)->allocsize = 0;
    138   lodepng_free(((uivector*)p)->data);
    139   ((uivector*)p)->data = NULL;
    140 }
    141 
    142 /*returns 1 if success, 0 if failure ==> nothing done*/
    143 static unsigned uivector_resize(uivector* p, size_t size)
    144 {
    145   if(size * sizeof(unsigned) > p->allocsize)
    146   {
    147     size_t newsize = size * sizeof(unsigned) * 2;
    148     void* data = lodepng_realloc(p->data, newsize);
    149     if(data)
    150     {
    151       p->allocsize = newsize;
    152       p->data = (unsigned*)data;
    153       p->size = size;
    154     }
    155     else return 0;
    156   }
    157   else p->size = size;
    158   return 1;
    159 }
    160 
    161 /*resize and give all new elements the value*/
    162 static unsigned uivector_resizev(uivector* p, size_t size, unsigned value)
    163 {
    164   size_t oldsize = p->size, i;
    165   if(!uivector_resize(p, size)) return 0;
    166   for(i = oldsize; i < size; i++) p->data[i] = value;
    167   return 1;
    168 }
    169 
    170 static void uivector_init(uivector* p)
    171 {
    172   p->data = NULL;
    173   p->size = p->allocsize = 0;
    174 }
    175 
    176 #ifdef LODEPNG_COMPILE_ENCODER
    177 /*returns 1 if success, 0 if failure ==> nothing done*/
    178 static unsigned uivector_push_back(uivector* p, unsigned c)
    179 {
    180   if(!uivector_resize(p, p->size + 1)) return 0;
    181   p->data[p->size - 1] = c;
    182   return 1;
    183 }
    184 
    185 /*copy q to p, returns 1 if success, 0 if failure ==> nothing done*/
    186 static unsigned uivector_copy(uivector* p, const uivector* q)
    187 {
    188   size_t i;
    189   if(!uivector_resize(p, q->size)) return 0;
    190   for(i = 0; i < q->size; i++) p->data[i] = q->data[i];
    191   return 1;
    192 }
    193 #endif /*LODEPNG_COMPILE_ENCODER*/
    194 #endif /*LODEPNG_COMPILE_ZLIB*/
    195 
    196 /* /////////////////////////////////////////////////////////////////////////// */
    197 
    198 /*dynamic vector of unsigned chars*/
    199 typedef struct ucvector
    200 {
    201   unsigned char* data;
    202   size_t size; /*used size*/
    203   size_t allocsize; /*allocated size*/
    204 } ucvector;
    205 
    206 /*returns 1 if success, 0 if failure ==> nothing done*/
    207 static unsigned ucvector_resize(ucvector* p, size_t size)
    208 {
    209   if(size * sizeof(unsigned char) > p->allocsize)
    210   {
    211     size_t newsize = size * sizeof(unsigned char) * 2;
    212     void* data = lodepng_realloc(p->data, newsize);
    213     if(data)
    214     {
    215       p->allocsize = newsize;
    216       p->data = (unsigned char*)data;
    217       p->size = size;
    218     }
    219     else return 0; /*error: not enough memory*/
    220   }
    221   else p->size = size;
    222   return 1;
    223 }
    224 
    225 #ifdef LODEPNG_COMPILE_PNG
    226 
    227 static void ucvector_cleanup(void* p)
    228 {
    229   ((ucvector*)p)->size = ((ucvector*)p)->allocsize = 0;
    230   lodepng_free(((ucvector*)p)->data);
    231   ((ucvector*)p)->data = NULL;
    232 }
    233 
    234 static void ucvector_init(ucvector* p)
    235 {
    236   p->data = NULL;
    237   p->size = p->allocsize = 0;
    238 }
    239 
    240 #ifdef LODEPNG_COMPILE_DECODER
    241 /*resize and give all new elements the value*/
    242 static unsigned ucvector_resizev(ucvector* p, size_t size, unsigned char value)
    243 {
    244   size_t oldsize = p->size, i;
    245   if(!ucvector_resize(p, size)) return 0;
    246   for(i = oldsize; i < size; i++) p->data[i] = value;
    247   return 1;
    248 }
    249 #endif /*LODEPNG_COMPILE_DECODER*/
    250 #endif /*LODEPNG_COMPILE_PNG*/
    251 
    252 #ifdef LODEPNG_COMPILE_ZLIB
    253 /*you can both convert from vector to buffer&size and vica versa. If you use
    254 init_buffer to take over a buffer and size, it is not needed to use cleanup*/
    255 static void ucvector_init_buffer(ucvector* p, unsigned char* buffer, size_t size)
    256 {
    257   p->data = buffer;
    258   p->allocsize = p->size = size;
    259 }
    260 #endif /*LODEPNG_COMPILE_ZLIB*/
    261 
    262 #if (defined(LODEPNG_COMPILE_PNG) && defined(LODEPNG_COMPILE_ANCILLARY_CHUNKS)) || defined(LODEPNG_COMPILE_ENCODER)
    263 /*returns 1 if success, 0 if failure ==> nothing done*/
    264 static unsigned ucvector_push_back(ucvector* p, unsigned char c)
    265 {
    266   if(!ucvector_resize(p, p->size + 1)) return 0;
    267   p->data[p->size - 1] = c;
    268   return 1;
    269 }
    270 #endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
    271 
    272 
    273 /* ////////////////////////////////////////////////////////////////////////// */
    274 
    275 #ifdef LODEPNG_COMPILE_PNG
    276 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
    277 /*returns 1 if success, 0 if failure ==> nothing done*/
    278 static unsigned string_resize(char** out, size_t size)
    279 {
    280   char* data = (char*)lodepng_realloc(*out, size + 1);
    281   if(data)
    282   {
    283     data[size] = 0; /*null termination char*/
    284     *out = data;
    285   }
    286   return data != 0;
    287 }
    288 
    289 /*init a {char*, size_t} pair for use as string*/
    290 static void string_init(char** out)
    291 {
    292   *out = NULL;
    293   string_resize(out, 0);
    294 }
    295 
    296 /*free the above pair again*/
    297 static void string_cleanup(char** out)
    298 {
    299   lodepng_free(*out);
    300   *out = NULL;
    301 }
    302 
    303 static void string_set(char** out, const char* in)
    304 {
    305   size_t insize = strlen(in), i = 0;
    306   if(string_resize(out, insize))
    307   {
    308     for(i = 0; i < insize; i++)
    309     {
    310       (*out)[i] = in[i];
    311     }
    312   }
    313 }
    314 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
    315 #endif /*LODEPNG_COMPILE_PNG*/
    316 
    317 /* ////////////////////////////////////////////////////////////////////////// */
    318 
    319 unsigned lodepng_read32bitInt(const unsigned char* buffer)
    320 {
    321   return (buffer[0] << 24) | (buffer[1] << 16) | (buffer[2] << 8) | buffer[3];
    322 }
    323 
    324 #if defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)
    325 /*buffer must have at least 4 allocated bytes available*/
    326 static void lodepng_set32bitInt(unsigned char* buffer, unsigned value)
    327 {
    328   buffer[0] = (unsigned char)((value >> 24) & 0xff);
    329   buffer[1] = (unsigned char)((value >> 16) & 0xff);
    330   buffer[2] = (unsigned char)((value >>  8) & 0xff);
    331   buffer[3] = (unsigned char)((value      ) & 0xff);
    332 }
    333 #endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
    334 
    335 #ifdef LODEPNG_COMPILE_ENCODER
    336 static void lodepng_add32bitInt(ucvector* buffer, unsigned value)
    337 {
    338   ucvector_resize(buffer, buffer->size + 4); /*todo: give error if resize failed*/
    339   lodepng_set32bitInt(&buffer->data[buffer->size - 4], value);
    340 }
    341 #endif /*LODEPNG_COMPILE_ENCODER*/
    342 
    343 /* ////////////////////////////////////////////////////////////////////////// */
    344 /* / File IO                                                                / */
    345 /* ////////////////////////////////////////////////////////////////////////// */
    346 
    347 #ifdef LODEPNG_COMPILE_DISK
    348 
    349 unsigned lodepng_load_file(unsigned char** out, size_t* outsize, const char* filename)
    350 {
    351   FILE* file;
    352   long size;
    353 
    354   /*provide some proper output values if error will happen*/
    355   *out = 0;
    356   *outsize = 0;
    357 
    358   file = fopen(filename, "rb");
    359   if(!file) return 78;
    360 
    361   /*get filesize:*/
    362   fseek(file , 0 , SEEK_END);
    363   size = ftell(file);
    364   rewind(file);
    365 
    366   /*read contents of the file into the vector*/
    367   *outsize = 0;
    368   *out = (unsigned char*)lodepng_malloc((size_t)size);
    369   if(size && (*out)) (*outsize) = fread(*out, 1, (size_t)size, file);
    370 
    371   fclose(file);
    372   if(!(*out) && size) return 83; /*the above malloc failed*/
    373   return 0;
    374 }
    375 
    376 /*write given buffer to the file, overwriting the file, it doesn't append to it.*/
    377 unsigned lodepng_save_file(const unsigned char* buffer, size_t buffersize, const char* filename)
    378 {
    379   FILE* file;
    380   file = fopen(filename, "wb" );
    381   if(!file) return 79;
    382   fwrite((char*)buffer , 1 , buffersize, file);
    383   fclose(file);
    384   return 0;
    385 }
    386 
    387 #endif /*LODEPNG_COMPILE_DISK*/
    388 
    389 /* ////////////////////////////////////////////////////////////////////////// */
    390 /* ////////////////////////////////////////////////////////////////////////// */
    391 /* // End of common code and tools. Begin of Zlib related code.            // */
    392 /* ////////////////////////////////////////////////////////////////////////// */
    393 /* ////////////////////////////////////////////////////////////////////////// */
    394 
    395 #ifdef LODEPNG_COMPILE_ZLIB
    396 #ifdef LODEPNG_COMPILE_ENCODER
    397 /*TODO: this ignores potential out of memory errors*/
    398 #define addBitToStream(/*size_t**/ bitpointer, /*ucvector**/ bitstream, /*unsigned char*/ bit)\
    399 {\
    400   /*add a new byte at the end*/\
    401   if(((*bitpointer) & 7) == 0) ucvector_push_back(bitstream, (unsigned char)0);\
    402   /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/\
    403   (bitstream->data[bitstream->size - 1]) |= (bit << ((*bitpointer) & 0x7));\
    404   (*bitpointer)++;\
    405 }
    406 
    407 static void addBitsToStream(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
    408 {
    409   size_t i;
    410   for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> i) & 1));
    411 }
    412 
    413 static void addBitsToStreamReversed(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
    414 {
    415   size_t i;
    416   for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> (nbits - 1 - i)) & 1));
    417 }
    418 #endif /*LODEPNG_COMPILE_ENCODER*/
    419 
    420 #ifdef LODEPNG_COMPILE_DECODER
    421 
    422 #define READBIT(bitpointer, bitstream) ((bitstream[bitpointer >> 3] >> (bitpointer & 0x7)) & (unsigned char)1)
    423 
    424 static unsigned char readBitFromStream(size_t* bitpointer, const unsigned char* bitstream)
    425 {
    426   unsigned char result = (unsigned char)(READBIT(*bitpointer, bitstream));
    427   (*bitpointer)++;
    428   return result;
    429 }
    430 
    431 static unsigned readBitsFromStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
    432 {
    433   unsigned result = 0, i;
    434   for(i = 0; i < nbits; i++)
    435   {
    436     result += ((unsigned)READBIT(*bitpointer, bitstream)) << i;
    437     (*bitpointer)++;
    438   }
    439   return result;
    440 }
    441 #endif /*LODEPNG_COMPILE_DECODER*/
    442 
    443 /* ////////////////////////////////////////////////////////////////////////// */
    444 /* / Deflate - Huffman                                                      / */
    445 /* ////////////////////////////////////////////////////////////////////////// */
    446 
    447 #define FIRST_LENGTH_CODE_INDEX 257
    448 #define LAST_LENGTH_CODE_INDEX 285
    449 /*256 literals, the end code, some length codes, and 2 unused codes*/
    450 #define NUM_DEFLATE_CODE_SYMBOLS 288
    451 /*the distance codes have their own symbols, 30 used, 2 unused*/
    452 #define NUM_DISTANCE_SYMBOLS 32
    453 /*the code length codes. 0-15: code lengths, 16: copy previous 3-6 times, 17: 3-10 zeros, 18: 11-138 zeros*/
    454 #define NUM_CODE_LENGTH_CODES 19
    455 
    456 /*the base lengths represented by codes 257-285*/
    457 static const unsigned LENGTHBASE[29]
    458   = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
    459      67, 83, 99, 115, 131, 163, 195, 227, 258};
    460 
    461 /*the extra bits used by codes 257-285 (added to base length)*/
    462 static const unsigned LENGTHEXTRA[29]
    463   = {0, 0, 0, 0, 0, 0, 0,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,
    464       4,  4,  4,   4,   5,   5,   5,   5,   0};
    465 
    466 /*the base backwards distances (the bits of distance codes appear after length codes and use their own huffman tree)*/
    467 static const unsigned DISTANCEBASE[30]
    468   = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
    469      769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
    470 
    471 /*the extra bits of backwards distances (added to base)*/
    472 static const unsigned DISTANCEEXTRA[30]
    473   = {0, 0, 0, 0, 1, 1, 2,  2,  3,  3,  4,  4,  5,  5,   6,   6,   7,   7,   8,
    474        8,    9,    9,   10,   10,   11,   11,   12,    12,    13,    13};
    475 
    476 /*the order in which "code length alphabet code lengths" are stored, out of this
    477 the huffman tree of the dynamic huffman tree lengths is generated*/
    478 static const unsigned CLCL_ORDER[NUM_CODE_LENGTH_CODES]
    479   = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
    480 
    481 /* ////////////////////////////////////////////////////////////////////////// */
    482 
    483 /*
    484 Huffman tree struct, containing multiple representations of the tree
    485 */
    486 typedef struct HuffmanTree
    487 {
    488   unsigned* tree2d;
    489   unsigned* tree1d;
    490   unsigned* lengths; /*the lengths of the codes of the 1d-tree*/
    491   unsigned maxbitlen; /*maximum number of bits a single code can get*/
    492   unsigned numcodes; /*number of symbols in the alphabet = number of codes*/
    493 } HuffmanTree;
    494 
    495 /*function used for debug purposes to draw the tree in ascii art with C++*/
    496 /*
    497 static void HuffmanTree_draw(HuffmanTree* tree)
    498 {
    499   std::cout << "tree. length: " << tree->numcodes << " maxbitlen: " << tree->maxbitlen << std::endl;
    500   for(size_t i = 0; i < tree->tree1d.size; i++)
    501   {
    502     if(tree->lengths.data[i])
    503       std::cout << i << " " << tree->tree1d.data[i] << " " << tree->lengths.data[i] << std::endl;
    504   }
    505   std::cout << std::endl;
    506 }*/
    507 
    508 static void HuffmanTree_init(HuffmanTree* tree)
    509 {
    510   tree->tree2d = 0;
    511   tree->tree1d = 0;
    512   tree->lengths = 0;
    513 }
    514 
    515 static void HuffmanTree_cleanup(HuffmanTree* tree)
    516 {
    517   lodepng_free(tree->tree2d);
    518   lodepng_free(tree->tree1d);
    519   lodepng_free(tree->lengths);
    520 }
    521 
    522 /*the tree representation used by the decoder. return value is error*/
    523 static unsigned HuffmanTree_make2DTree(HuffmanTree* tree)
    524 {
    525   unsigned nodefilled = 0; /*up to which node it is filled*/
    526   unsigned treepos = 0; /*position in the tree (1 of the numcodes columns)*/
    527   unsigned n, i;
    528 
    529   tree->tree2d = (unsigned*)lodepng_malloc(tree->numcodes * 2 * sizeof(unsigned));
    530   if(!tree->tree2d) return 83; /*alloc fail*/
    531 
    532   /*
    533   convert tree1d[] to tree2d[][]. In the 2D array, a value of 32767 means
    534   uninited, a value >= numcodes is an address to another bit, a value < numcodes
    535   is a code. The 2 rows are the 2 possible bit values (0 or 1), there are as
    536   many columns as codes - 1.
    537   A good huffmann tree has N * 2 - 1 nodes, of which N - 1 are internal nodes.
    538   Here, the internal nodes are stored (what their 0 and 1 option point to).
    539   There is only memory for such good tree currently, if there are more nodes
    540   (due to too long length codes), error 55 will happen
    541   */
    542   for(n = 0; n < tree->numcodes * 2; n++)
    543   {
    544     tree->tree2d[n] = 32767; /*32767 here means the tree2d isn't filled there yet*/
    545   }
    546 
    547   for(n = 0; n < tree->numcodes; n++) /*the codes*/
    548   {
    549     for(i = 0; i < tree->lengths[n]; i++) /*the bits for this code*/
    550     {
    551       unsigned char bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1);
    552       if(treepos > tree->numcodes - 2) return 55; /*oversubscribed, see comment in lodepng_error_text*/
    553       if(tree->tree2d[2 * treepos + bit] == 32767) /*not yet filled in*/
    554       {
    555         if(i + 1 == tree->lengths[n]) /*last bit*/
    556         {
    557           tree->tree2d[2 * treepos + bit] = n; /*put the current code in it*/
    558           treepos = 0;
    559         }
    560         else
    561         {
    562           /*put address of the next step in here, first that address has to be found of course
    563           (it's just nodefilled + 1)...*/
    564           nodefilled++;
    565           /*addresses encoded with numcodes added to it*/
    566           tree->tree2d[2 * treepos + bit] = nodefilled + tree->numcodes;
    567           treepos = nodefilled;
    568         }
    569       }
    570       else treepos = tree->tree2d[2 * treepos + bit] - tree->numcodes;
    571     }
    572   }
    573 
    574   for(n = 0; n < tree->numcodes * 2; n++)
    575   {
    576     if(tree->tree2d[n] == 32767) tree->tree2d[n] = 0; /*remove possible remaining 32767's*/
    577   }
    578 
    579   return 0;
    580 }
    581 
    582 /*
    583 Second step for the ...makeFromLengths and ...makeFromFrequencies functions.
    584 numcodes, lengths and maxbitlen must already be filled in correctly. return
    585 value is error.
    586 */
    587 static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree)
    588 {
    589   uivector blcount;
    590   uivector nextcode;
    591   unsigned bits, n, error = 0;
    592 
    593   uivector_init(&blcount);
    594   uivector_init(&nextcode);
    595 
    596   tree->tree1d = (unsigned*)lodepng_malloc(tree->numcodes * sizeof(unsigned));
    597   if(!tree->tree1d) error = 83; /*alloc fail*/
    598 
    599   if(!uivector_resizev(&blcount, tree->maxbitlen + 1, 0)
    600   || !uivector_resizev(&nextcode, tree->maxbitlen + 1, 0))
    601     error = 83; /*alloc fail*/
    602 
    603   if(!error)
    604   {
    605     /*step 1: count number of instances of each code length*/
    606     for(bits = 0; bits < tree->numcodes; bits++) blcount.data[tree->lengths[bits]]++;
    607     /*step 2: generate the nextcode values*/
    608     for(bits = 1; bits <= tree->maxbitlen; bits++)
    609     {
    610       nextcode.data[bits] = (nextcode.data[bits - 1] + blcount.data[bits - 1]) << 1;
    611     }
    612     /*step 3: generate all the codes*/
    613     for(n = 0; n < tree->numcodes; n++)
    614     {
    615       if(tree->lengths[n] != 0) tree->tree1d[n] = nextcode.data[tree->lengths[n]]++;
    616     }
    617   }
    618 
    619   uivector_cleanup(&blcount);
    620   uivector_cleanup(&nextcode);
    621 
    622   if(!error) return HuffmanTree_make2DTree(tree);
    623   else return error;
    624 }
    625 
    626 /*
    627 given the code lengths (as stored in the PNG file), generate the tree as defined
    628 by Deflate. maxbitlen is the maximum bits that a code in the tree can have.
    629 return value is error.
    630 */
    631 static unsigned HuffmanTree_makeFromLengths(HuffmanTree* tree, const unsigned* bitlen,
    632                                             size_t numcodes, unsigned maxbitlen)
    633 {
    634   unsigned i;
    635   tree->lengths = (unsigned*)lodepng_malloc(numcodes * sizeof(unsigned));
    636   if(!tree->lengths) return 83; /*alloc fail*/
    637   for(i = 0; i < numcodes; i++) tree->lengths[i] = bitlen[i];
    638   tree->numcodes = (unsigned)numcodes; /*number of symbols*/
    639   tree->maxbitlen = maxbitlen;
    640   return HuffmanTree_makeFromLengths2(tree);
    641 }
    642 
    643 #ifdef LODEPNG_COMPILE_ENCODER
    644 
    645 /*
    646 A coin, this is the terminology used for the package-merge algorithm and the
    647 coin collector's problem. This is used to generate the huffman tree.
    648 A coin can be multiple coins (when they're merged)
    649 */
    650 typedef struct Coin
    651 {
    652   uivector symbols;
    653   float weight; /*the sum of all weights in this coin*/
    654 } Coin;
    655 
    656 static void coin_init(Coin* c)
    657 {
    658   uivector_init(&c->symbols);
    659 }
    660 
    661 /*argument c is void* so that this dtor can be given as function pointer to the vector resize function*/
    662 static void coin_cleanup(void* c)
    663 {
    664   uivector_cleanup(&((Coin*)c)->symbols);
    665 }
    666 
    667 static void coin_copy(Coin* c1, const Coin* c2)
    668 {
    669   c1->weight = c2->weight;
    670   uivector_copy(&c1->symbols, &c2->symbols);
    671 }
    672 
    673 static void add_coins(Coin* c1, const Coin* c2)
    674 {
    675   size_t i;
    676   for(i = 0; i < c2->symbols.size; i++) uivector_push_back(&c1->symbols, c2->symbols.data[i]);
    677   c1->weight += c2->weight;
    678 }
    679 
    680 static void init_coins(Coin* coins, size_t num)
    681 {
    682   size_t i;
    683   for(i = 0; i < num; i++) coin_init(&coins[i]);
    684 }
    685 
    686 static void cleanup_coins(Coin* coins, size_t num)
    687 {
    688   size_t i;
    689   for(i = 0; i < num; i++) coin_cleanup(&coins[i]);
    690 }
    691 
    692 static int coin_compare(const void* a, const void* b) {
    693   float wa = ((const Coin*)a)->weight;
    694   float wb = ((const Coin*)b)->weight;
    695   return wa > wb ? 1 : wa < wb ? -1 : 0;
    696 }
    697 
    698 static unsigned append_symbol_coins(Coin* coins, const unsigned* frequencies, unsigned numcodes, size_t sum)
    699 {
    700   unsigned i;
    701   unsigned j = 0; /*index of present symbols*/
    702   for(i = 0; i < numcodes; i++)
    703   {
    704     if(frequencies[i] != 0) /*only include symbols that are present*/
    705     {
    706       coins[j].weight = frequencies[i] / (float)sum;
    707       uivector_push_back(&coins[j].symbols, i);
    708       j++;
    709     }
    710   }
    711   return 0;
    712 }
    713 
    714 unsigned lodepng_huffman_code_lengths(unsigned* lengths, const unsigned* frequencies,
    715                                       size_t numcodes, unsigned maxbitlen)
    716 {
    717   unsigned i, j;
    718   size_t sum = 0, numpresent = 0;
    719   unsigned error = 0;
    720   Coin* coins; /*the coins of the currently calculated row*/
    721   Coin* prev_row; /*the previous row of coins*/
    722   unsigned numcoins;
    723   unsigned coinmem;
    724 
    725   if(numcodes == 0) return 80; /*error: a tree of 0 symbols is not supposed to be made*/
    726 
    727   for(i = 0; i < numcodes; i++)
    728   {
    729     if(frequencies[i] > 0)
    730     {
    731       numpresent++;
    732       sum += frequencies[i];
    733     }
    734   }
    735 
    736   for(i = 0; i < numcodes; i++) lengths[i] = 0;
    737 
    738   /*ensure at least two present symbols. There should be at least one symbol
    739   according to RFC 1951 section 3.2.7. To decoders incorrectly require two. To
    740   make these work as well ensure there are at least two symbols. The
    741   Package-Merge code below also doesn't work correctly if there's only one
    742   symbol, it'd give it the theoritical 0 bits but in practice zlib wants 1 bit*/
    743   if(numpresent == 0)
    744   {
    745     lengths[0] = lengths[1] = 1; /*note that for RFC 1951 section 3.2.7, only lengths[0] = 1 is needed*/
    746   }
    747   else if(numpresent == 1)
    748   {
    749     for(i = 0; i < numcodes; i++)
    750     {
    751       if(frequencies[i])
    752       {
    753         lengths[i] = 1;
    754         lengths[i == 0 ? 1 : 0] = 1;
    755         break;
    756       }
    757     }
    758   }
    759   else
    760   {
    761     /*Package-Merge algorithm represented by coin collector's problem
    762     For every symbol, maxbitlen coins will be created*/
    763 
    764     coinmem = numpresent * 2; /*max amount of coins needed with the current algo*/
    765     coins = (Coin*)lodepng_malloc(sizeof(Coin) * coinmem);
    766     prev_row = (Coin*)lodepng_malloc(sizeof(Coin) * coinmem);
    767     if(!coins || !prev_row)
    768     {
    769       lodepng_free(coins);
    770       lodepng_free(prev_row);
    771       return 83; /*alloc fail*/
    772     }
    773     init_coins(coins, coinmem);
    774     init_coins(prev_row, coinmem);
    775 
    776     /*first row, lowest denominator*/
    777     error = append_symbol_coins(coins, frequencies, numcodes, sum);
    778     numcoins = numpresent;
    779     qsort(coins, numcoins, sizeof(Coin), coin_compare);
    780     if(!error)
    781     {
    782       unsigned numprev = 0;
    783       for(j = 1; j <= maxbitlen && !error; j++) /*each of the remaining rows*/
    784       {
    785         unsigned tempnum;
    786         Coin* tempcoins;
    787         /*swap prev_row and coins, and their amounts*/
    788         tempcoins = prev_row; prev_row = coins; coins = tempcoins;
    789         tempnum = numprev; numprev = numcoins; numcoins = tempnum;
    790 
    791         cleanup_coins(coins, numcoins);
    792         init_coins(coins, numcoins);
    793 
    794         numcoins = 0;
    795 
    796         /*fill in the merged coins of the previous row*/
    797         for(i = 0; i + 1 < numprev; i += 2)
    798         {
    799           /*merge prev_row[i] and prev_row[i + 1] into new coin*/
    800           Coin* coin = &coins[numcoins++];
    801           coin_copy(coin, &prev_row[i]);
    802           add_coins(coin, &prev_row[i + 1]);
    803         }
    804         /*fill in all the original symbols again*/
    805         if(j < maxbitlen)
    806         {
    807           error = append_symbol_coins(coins + numcoins, frequencies, numcodes, sum);
    808           numcoins += numpresent;
    809         }
    810         qsort(coins, numcoins, sizeof(Coin), coin_compare);
    811       }
    812     }
    813 
    814     if(!error)
    815     {
    816       /*calculate the lenghts of each symbol, as the amount of times a coin of each symbol is used*/
    817       for(i = 0; i < numpresent - 1; i++)
    818       {
    819         Coin* coin = &coins[i];
    820         for(j = 0; j < coin->symbols.size; j++) lengths[coin->symbols.data[j]]++;
    821       }
    822     }
    823 
    824     cleanup_coins(coins, coinmem);
    825     lodepng_free(coins);
    826     cleanup_coins(prev_row, coinmem);
    827     lodepng_free(prev_row);
    828   }
    829 
    830   return error;
    831 }
    832 
    833 /*Create the Huffman tree given the symbol frequencies*/
    834 static unsigned HuffmanTree_makeFromFrequencies(HuffmanTree* tree, const unsigned* frequencies,
    835                                                 size_t mincodes, size_t numcodes, unsigned maxbitlen)
    836 {
    837   unsigned error = 0;
    838   while(!frequencies[numcodes - 1] && numcodes > mincodes) numcodes--; /*trim zeroes*/
    839   tree->maxbitlen = maxbitlen;
    840   tree->numcodes = (unsigned)numcodes; /*number of symbols*/
    841   tree->lengths = (unsigned*)lodepng_realloc(tree->lengths, numcodes * sizeof(unsigned));
    842   if(!tree->lengths) return 83; /*alloc fail*/
    843   /*initialize all lengths to 0*/
    844   memset(tree->lengths, 0, numcodes * sizeof(unsigned));
    845 
    846   error = lodepng_huffman_code_lengths(tree->lengths, frequencies, numcodes, maxbitlen);
    847   if(!error) error = HuffmanTree_makeFromLengths2(tree);
    848   return error;
    849 }
    850 
    851 static unsigned HuffmanTree_getCode(const HuffmanTree* tree, unsigned index)
    852 {
    853   return tree->tree1d[index];
    854 }
    855 
    856 static unsigned HuffmanTree_getLength(const HuffmanTree* tree, unsigned index)
    857 {
    858   return tree->lengths[index];
    859 }
    860 #endif /*LODEPNG_COMPILE_ENCODER*/
    861 
    862 /*get the literal and length code tree of a deflated block with fixed tree, as per the deflate specification*/
    863 static unsigned generateFixedLitLenTree(HuffmanTree* tree)
    864 {
    865   unsigned i, error = 0;
    866   unsigned* bitlen = (unsigned*)lodepng_malloc(NUM_DEFLATE_CODE_SYMBOLS * sizeof(unsigned));
    867   if(!bitlen) return 83; /*alloc fail*/
    868 
    869   /*288 possible codes: 0-255=literals, 256=endcode, 257-285=lengthcodes, 286-287=unused*/
    870   for(i =   0; i <= 143; i++) bitlen[i] = 8;
    871   for(i = 144; i <= 255; i++) bitlen[i] = 9;
    872   for(i = 256; i <= 279; i++) bitlen[i] = 7;
    873   for(i = 280; i <= 287; i++) bitlen[i] = 8;
    874 
    875   error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DEFLATE_CODE_SYMBOLS, 15);
    876 
    877   lodepng_free(bitlen);
    878   return error;
    879 }
    880 
    881 /*get the distance code tree of a deflated block with fixed tree, as specified in the deflate specification*/
    882 static unsigned generateFixedDistanceTree(HuffmanTree* tree)
    883 {
    884   unsigned i, error = 0;
    885   unsigned* bitlen = (unsigned*)lodepng_malloc(NUM_DISTANCE_SYMBOLS * sizeof(unsigned));
    886   if(!bitlen) return 83; /*alloc fail*/
    887 
    888   /*there are 32 distance codes, but 30-31 are unused*/
    889   for(i = 0; i < NUM_DISTANCE_SYMBOLS; i++) bitlen[i] = 5;
    890   error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DISTANCE_SYMBOLS, 15);
    891 
    892   lodepng_free(bitlen);
    893   return error;
    894 }
    895 
    896 #ifdef LODEPNG_COMPILE_DECODER
    897 
    898 /*
    899 returns the code, or (unsigned)(-1) if error happened
    900 inbitlength is the length of the complete buffer, in bits (so its byte length times 8)
    901 */
    902 static unsigned huffmanDecodeSymbol(const unsigned char* in, size_t* bp,
    903                                     const HuffmanTree* codetree, size_t inbitlength)
    904 {
    905   unsigned treepos = 0, ct;
    906   for(;;)
    907   {
    908     if(*bp >= inbitlength) return (unsigned)(-1); /*error: end of input memory reached without endcode*/
    909     /*
    910     decode the symbol from the tree. The "readBitFromStream" code is inlined in
    911     the expression below because this is the biggest bottleneck while decoding
    912     */
    913     ct = codetree->tree2d[(treepos << 1) + READBIT(*bp, in)];
    914     (*bp)++;
    915     if(ct < codetree->numcodes) return ct; /*the symbol is decoded, return it*/
    916     else treepos = ct - codetree->numcodes; /*symbol not yet decoded, instead move tree position*/
    917 
    918     if(treepos >= codetree->numcodes) return (unsigned)(-1); /*error: it appeared outside the codetree*/
    919   }
    920 }
    921 #endif /*LODEPNG_COMPILE_DECODER*/
    922 
    923 #ifdef LODEPNG_COMPILE_DECODER
    924 
    925 /* ////////////////////////////////////////////////////////////////////////// */
    926 /* / Inflator (Decompressor)                                                / */
    927 /* ////////////////////////////////////////////////////////////////////////// */
    928 
    929 /*get the tree of a deflated block with fixed tree, as specified in the deflate specification*/
    930 static void getTreeInflateFixed(HuffmanTree* tree_ll, HuffmanTree* tree_d)
    931 {
    932   /*TODO: check for out of memory errors*/
    933   generateFixedLitLenTree(tree_ll);
    934   generateFixedDistanceTree(tree_d);
    935 }
    936 
    937 /*get the tree of a deflated block with dynamic tree, the tree itself is also Huffman compressed with a known tree*/
    938 static unsigned getTreeInflateDynamic(HuffmanTree* tree_ll, HuffmanTree* tree_d,
    939                                       const unsigned char* in, size_t* bp, size_t inlength)
    940 {
    941   /*make sure that length values that aren't filled in will be 0, or a wrong tree will be generated*/
    942   unsigned error = 0;
    943   unsigned n, HLIT, HDIST, HCLEN, i;
    944   size_t inbitlength = inlength * 8;
    945 
    946   /*see comments in deflateDynamic for explanation of the context and these variables, it is analogous*/
    947   unsigned* bitlen_ll = 0; /*lit,len code lengths*/
    948   unsigned* bitlen_d = 0; /*dist code lengths*/
    949   /*code length code lengths ("clcl"), the bit lengths of the huffman tree used to compress bitlen_ll and bitlen_d*/
    950   unsigned* bitlen_cl = 0;
    951   HuffmanTree tree_cl; /*the code tree for code length codes (the huffman tree for compressed huffman trees)*/
    952 
    953   if((*bp) >> 3 >= inlength - 2) return 49; /*error: the bit pointer is or will go past the memory*/
    954 
    955   /*number of literal/length codes + 257. Unlike the spec, the value 257 is added to it here already*/
    956   HLIT =  readBitsFromStream(bp, in, 5) + 257;
    957   /*number of distance codes. Unlike the spec, the value 1 is added to it here already*/
    958   HDIST = readBitsFromStream(bp, in, 5) + 1;
    959   /*number of code length codes. Unlike the spec, the value 4 is added to it here already*/
    960   HCLEN = readBitsFromStream(bp, in, 4) + 4;
    961 
    962   HuffmanTree_init(&tree_cl);
    963 
    964   while(!error)
    965   {
    966     /*read the code length codes out of 3 * (amount of code length codes) bits*/
    967 
    968     bitlen_cl = (unsigned*)lodepng_malloc(NUM_CODE_LENGTH_CODES * sizeof(unsigned));
    969     if(!bitlen_cl) ERROR_BREAK(83 /*alloc fail*/);
    970 
    971     for(i = 0; i < NUM_CODE_LENGTH_CODES; i++)
    972     {
    973       if(i < HCLEN) bitlen_cl[CLCL_ORDER[i]] = readBitsFromStream(bp, in, 3);
    974       else bitlen_cl[CLCL_ORDER[i]] = 0; /*if not, it must stay 0*/
    975     }
    976 
    977     error = HuffmanTree_makeFromLengths(&tree_cl, bitlen_cl, NUM_CODE_LENGTH_CODES, 7);
    978     if(error) break;
    979 
    980     /*now we can use this tree to read the lengths for the tree that this function will return*/
    981     bitlen_ll = (unsigned*)lodepng_malloc(NUM_DEFLATE_CODE_SYMBOLS * sizeof(unsigned));
    982     bitlen_d = (unsigned*)lodepng_malloc(NUM_DISTANCE_SYMBOLS * sizeof(unsigned));
    983     if(!bitlen_ll || !bitlen_d) ERROR_BREAK(83 /*alloc fail*/);
    984     for(i = 0; i < NUM_DEFLATE_CODE_SYMBOLS; i++) bitlen_ll[i] = 0;
    985     for(i = 0; i < NUM_DISTANCE_SYMBOLS; i++) bitlen_d[i] = 0;
    986 
    987     /*i is the current symbol we're reading in the part that contains the code lengths of lit/len and dist codes*/
    988     i = 0;
    989     while(i < HLIT + HDIST)
    990     {
    991       unsigned code = huffmanDecodeSymbol(in, bp, &tree_cl, inbitlength);
    992       if(code <= 15) /*a length code*/
    993       {
    994         if(i < HLIT) bitlen_ll[i] = code;
    995         else bitlen_d[i - HLIT] = code;
    996         i++;
    997       }
    998       else if(code == 16) /*repeat previous*/
    999       {
   1000         unsigned replength = 3; /*read in the 2 bits that indicate repeat length (3-6)*/
   1001         unsigned value; /*set value to the previous code*/
   1002 
   1003         if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
   1004         if (i == 0) ERROR_BREAK(54); /*can't repeat previous if i is 0*/
   1005 
   1006         replength += readBitsFromStream(bp, in, 2);
   1007 
   1008         if(i < HLIT + 1) value = bitlen_ll[i - 1];
   1009         else value = bitlen_d[i - HLIT - 1];
   1010         /*repeat this value in the next lengths*/
   1011         for(n = 0; n < replength; n++)
   1012         {
   1013           if(i >= HLIT + HDIST) ERROR_BREAK(13); /*error: i is larger than the amount of codes*/
   1014           if(i < HLIT) bitlen_ll[i] = value;
   1015           else bitlen_d[i - HLIT] = value;
   1016           i++;
   1017         }
   1018       }
   1019       else if(code == 17) /*repeat "0" 3-10 times*/
   1020       {
   1021         unsigned replength = 3; /*read in the bits that indicate repeat length*/
   1022         if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
   1023 
   1024         replength += readBitsFromStream(bp, in, 3);
   1025 
   1026         /*repeat this value in the next lengths*/
   1027         for(n = 0; n < replength; n++)
   1028         {
   1029           if(i >= HLIT + HDIST) ERROR_BREAK(14); /*error: i is larger than the amount of codes*/
   1030 
   1031           if(i < HLIT) bitlen_ll[i] = 0;
   1032           else bitlen_d[i - HLIT] = 0;
   1033           i++;
   1034         }
   1035       }
   1036       else if(code == 18) /*repeat "0" 11-138 times*/
   1037       {
   1038         unsigned replength = 11; /*read in the bits that indicate repeat length*/
   1039         if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
   1040 
   1041         replength += readBitsFromStream(bp, in, 7);
   1042 
   1043         /*repeat this value in the next lengths*/
   1044         for(n = 0; n < replength; n++)
   1045         {
   1046           if(i >= HLIT + HDIST) ERROR_BREAK(15); /*error: i is larger than the amount of codes*/
   1047 
   1048           if(i < HLIT) bitlen_ll[i] = 0;
   1049           else bitlen_d[i - HLIT] = 0;
   1050           i++;
   1051         }
   1052       }
   1053       else /*if(code == (unsigned)(-1))*/ /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
   1054       {
   1055         if(code == (unsigned)(-1))
   1056         {
   1057           /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
   1058           (10=no endcode, 11=wrong jump outside of tree)*/
   1059           error = (*bp) > inbitlength ? 10 : 11;
   1060         }
   1061         else error = 16; /*unexisting code, this can never happen*/
   1062         break;
   1063       }
   1064     }
   1065     if(error) break;
   1066 
   1067     if(bitlen_ll[256] == 0) ERROR_BREAK(64); /*the length of the end code 256 must be larger than 0*/
   1068 
   1069     /*now we've finally got HLIT and HDIST, so generate the code trees, and the function is done*/
   1070     error = HuffmanTree_makeFromLengths(tree_ll, bitlen_ll, NUM_DEFLATE_CODE_SYMBOLS, 15);
   1071     if(error) break;
   1072     error = HuffmanTree_makeFromLengths(tree_d, bitlen_d, NUM_DISTANCE_SYMBOLS, 15);
   1073 
   1074     break; /*end of error-while*/
   1075   }
   1076 
   1077   lodepng_free(bitlen_cl);
   1078   lodepng_free(bitlen_ll);
   1079   lodepng_free(bitlen_d);
   1080   HuffmanTree_cleanup(&tree_cl);
   1081 
   1082   return error;
   1083 }
   1084 
   1085 /*inflate a block with dynamic of fixed Huffman tree*/
   1086 static unsigned inflateHuffmanBlock(ucvector* out, const unsigned char* in, size_t* bp,
   1087                                     size_t* pos, size_t inlength, unsigned btype)
   1088 {
   1089   unsigned error = 0;
   1090   HuffmanTree tree_ll; /*the huffman tree for literal and length codes*/
   1091   HuffmanTree tree_d; /*the huffman tree for distance codes*/
   1092   size_t inbitlength = inlength * 8;
   1093 
   1094   HuffmanTree_init(&tree_ll);
   1095   HuffmanTree_init(&tree_d);
   1096 
   1097   if(btype == 1) getTreeInflateFixed(&tree_ll, &tree_d);
   1098   else if(btype == 2) error = getTreeInflateDynamic(&tree_ll, &tree_d, in, bp, inlength);
   1099 
   1100   while(!error) /*decode all symbols until end reached, breaks at end code*/
   1101   {
   1102     /*code_ll is literal, length or end code*/
   1103     unsigned code_ll = huffmanDecodeSymbol(in, bp, &tree_ll, inbitlength);
   1104     if(code_ll <= 255) /*literal symbol*/
   1105     {
   1106       if((*pos) >= out->size)
   1107       {
   1108         /*reserve more room at once*/
   1109         if(!ucvector_resize(out, ((*pos) + 1) * 2)) ERROR_BREAK(83 /*alloc fail*/);
   1110       }
   1111       out->data[(*pos)] = (unsigned char)(code_ll);
   1112       (*pos)++;
   1113     }
   1114     else if(code_ll >= FIRST_LENGTH_CODE_INDEX && code_ll <= LAST_LENGTH_CODE_INDEX) /*length code*/
   1115     {
   1116       unsigned code_d, distance;
   1117       unsigned numextrabits_l, numextrabits_d; /*extra bits for length and distance*/
   1118       size_t start, forward, backward, length;
   1119 
   1120       /*part 1: get length base*/
   1121       length = LENGTHBASE[code_ll - FIRST_LENGTH_CODE_INDEX];
   1122 
   1123       /*part 2: get extra bits and add the value of that to length*/
   1124       numextrabits_l = LENGTHEXTRA[code_ll - FIRST_LENGTH_CODE_INDEX];
   1125       if(*bp >= inbitlength) ERROR_BREAK(51); /*error, bit pointer will jump past memory*/
   1126       length += readBitsFromStream(bp, in, numextrabits_l);
   1127 
   1128       /*part 3: get distance code*/
   1129       code_d = huffmanDecodeSymbol(in, bp, &tree_d, inbitlength);
   1130       if(code_d > 29)
   1131       {
   1132         if(code_ll == (unsigned)(-1)) /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
   1133         {
   1134           /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
   1135           (10=no endcode, 11=wrong jump outside of tree)*/
   1136           error = (*bp) > inlength * 8 ? 10 : 11;
   1137         }
   1138         else error = 18; /*error: invalid distance code (30-31 are never used)*/
   1139         break;
   1140       }
   1141       distance = DISTANCEBASE[code_d];
   1142 
   1143       /*part 4: get extra bits from distance*/
   1144       numextrabits_d = DISTANCEEXTRA[code_d];
   1145       if(*bp >= inbitlength) ERROR_BREAK(51); /*error, bit pointer will jump past memory*/
   1146 
   1147       distance += readBitsFromStream(bp, in, numextrabits_d);
   1148 
   1149       /*part 5: fill in all the out[n] values based on the length and dist*/
   1150       start = (*pos);
   1151       if(distance > start) ERROR_BREAK(52); /*too long backward distance*/
   1152       backward = start - distance;
   1153       if((*pos) + length >= out->size)
   1154       {
   1155         /*reserve more room at once*/
   1156         if(!ucvector_resize(out, ((*pos) + length) * 2)) ERROR_BREAK(83 /*alloc fail*/);
   1157       }
   1158 
   1159       for(forward = 0; forward < length; forward++)
   1160       {
   1161         out->data[(*pos)] = out->data[backward];
   1162         (*pos)++;
   1163         backward++;
   1164         if(backward >= start) backward = start - distance;
   1165       }
   1166     }
   1167     else if(code_ll == 256)
   1168     {
   1169       break; /*end code, break the loop*/
   1170     }
   1171     else /*if(code == (unsigned)(-1))*/ /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
   1172     {
   1173       /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
   1174       (10=no endcode, 11=wrong jump outside of tree)*/
   1175       error = (*bp) > inlength * 8 ? 10 : 11;
   1176       break;
   1177     }
   1178   }
   1179 
   1180   HuffmanTree_cleanup(&tree_ll);
   1181   HuffmanTree_cleanup(&tree_d);
   1182 
   1183   return error;
   1184 }
   1185 
   1186 static unsigned inflateNoCompression(ucvector* out, const unsigned char* in, size_t* bp, size_t* pos, size_t inlength)
   1187 {
   1188   /*go to first boundary of byte*/
   1189   size_t p;
   1190   unsigned LEN, NLEN, n, error = 0;
   1191   while(((*bp) & 0x7) != 0) (*bp)++;
   1192   p = (*bp) / 8; /*byte position*/
   1193 
   1194   /*read LEN (2 bytes) and NLEN (2 bytes)*/
   1195   if(p >= inlength - 4) return 52; /*error, bit pointer will jump past memory*/
   1196   LEN = in[p] + 256 * in[p + 1]; p += 2;
   1197   NLEN = in[p] + 256 * in[p + 1]; p += 2;
   1198 
   1199   /*check if 16-bit NLEN is really the one's complement of LEN*/
   1200   if(LEN + NLEN != 65535) return 21; /*error: NLEN is not one's complement of LEN*/
   1201 
   1202   if((*pos) + LEN >= out->size)
   1203   {
   1204     if(!ucvector_resize(out, (*pos) + LEN)) return 83; /*alloc fail*/
   1205   }
   1206 
   1207   /*read the literal data: LEN bytes are now stored in the out buffer*/
   1208   if(p + LEN > inlength) return 23; /*error: reading outside of in buffer*/
   1209   for(n = 0; n < LEN; n++) out->data[(*pos)++] = in[p++];
   1210 
   1211   (*bp) = p * 8;
   1212 
   1213   return error;
   1214 }
   1215 
   1216 static unsigned lodepng_inflatev(ucvector* out,
   1217                                  const unsigned char* in, size_t insize,
   1218                                  const LodePNGDecompressSettings* settings)
   1219 {
   1220   /*bit pointer in the "in" data, current byte is bp >> 3, current bit is bp & 0x7 (from lsb to msb of the byte)*/
   1221   size_t bp = 0;
   1222   unsigned BFINAL = 0;
   1223   size_t pos = 0; /*byte position in the out buffer*/
   1224 
   1225   unsigned error = 0;
   1226 
   1227   (void)settings;
   1228 
   1229   while(!BFINAL)
   1230   {
   1231     unsigned BTYPE;
   1232     if(bp + 2 >= insize * 8) return 52; /*error, bit pointer will jump past memory*/
   1233     BFINAL = readBitFromStream(&bp, in);
   1234     BTYPE = 1 * readBitFromStream(&bp, in);
   1235     BTYPE += 2 * readBitFromStream(&bp, in);
   1236 
   1237     if(BTYPE == 3) return 20; /*error: invalid BTYPE*/
   1238     else if(BTYPE == 0) error = inflateNoCompression(out, in, &bp, &pos, insize); /*no compression*/
   1239     else error = inflateHuffmanBlock(out, in, &bp, &pos, insize, BTYPE); /*compression, BTYPE 01 or 10*/
   1240 
   1241     if(error) return error;
   1242   }
   1243 
   1244   /*Only now we know the true size of out, resize it to that*/
   1245   if(!ucvector_resize(out, pos)) error = 83; /*alloc fail*/
   1246 
   1247   return error;
   1248 }
   1249 
   1250 unsigned lodepng_inflate(unsigned char** out, size_t* outsize,
   1251                          const unsigned char* in, size_t insize,
   1252                          const LodePNGDecompressSettings* settings)
   1253 {
   1254   unsigned error;
   1255   ucvector v;
   1256   ucvector_init_buffer(&v, *out, *outsize);
   1257   error = lodepng_inflatev(&v, in, insize, settings);
   1258   *out = v.data;
   1259   *outsize = v.size;
   1260   return error;
   1261 }
   1262 
   1263 static unsigned inflate(unsigned char** out, size_t* outsize,
   1264                         const unsigned char* in, size_t insize,
   1265                         const LodePNGDecompressSettings* settings)
   1266 {
   1267   if(settings->custom_inflate)
   1268   {
   1269     return settings->custom_inflate(out, outsize, in, insize, settings);
   1270   }
   1271   else
   1272   {
   1273     return lodepng_inflate(out, outsize, in, insize, settings);
   1274   }
   1275 }
   1276 
   1277 #endif /*LODEPNG_COMPILE_DECODER*/
   1278 
   1279 #ifdef LODEPNG_COMPILE_ENCODER
   1280 
   1281 /* ////////////////////////////////////////////////////////////////////////// */
   1282 /* / Deflator (Compressor)                                                  / */
   1283 /* ////////////////////////////////////////////////////////////////////////// */
   1284 
   1285 static const size_t MAX_SUPPORTED_DEFLATE_LENGTH = 258;
   1286 
   1287 /*bitlen is the size in bits of the code*/
   1288 static void addHuffmanSymbol(size_t* bp, ucvector* compressed, unsigned code, unsigned bitlen)
   1289 {
   1290   addBitsToStreamReversed(bp, compressed, code, bitlen);
   1291 }
   1292 
   1293 /*search the index in the array, that has the largest value smaller than or equal to the given value,
   1294 given array must be sorted (if no value is smaller, it returns the size of the given array)*/
   1295 static size_t searchCodeIndex(const unsigned* array, size_t array_size, size_t value)
   1296 {
   1297   /*linear search implementation*/
   1298   /*for(size_t i = 1; i < array_size; i++) if(array[i] > value) return i - 1;
   1299   return array_size - 1;*/
   1300 
   1301   /*binary search implementation (not that much faster) (precondition: array_size > 0)*/
   1302   size_t left  = 1;
   1303   size_t right = array_size - 1;
   1304   while(left <= right)
   1305   {
   1306     size_t mid = (left + right) / 2;
   1307     if(array[mid] <= value) left = mid + 1; /*the value to find is more to the right*/
   1308     else if(array[mid - 1] > value) right = mid - 1; /*the value to find is more to the left*/
   1309     else return mid - 1;
   1310   }
   1311   return array_size - 1;
   1312 }
   1313 
   1314 static void addLengthDistance(uivector* values, size_t length, size_t distance)
   1315 {
   1316   /*values in encoded vector are those used by deflate:
   1317   0-255: literal bytes
   1318   256: end
   1319   257-285: length/distance pair (length code, followed by extra length bits, distance code, extra distance bits)
   1320   286-287: invalid*/
   1321 
   1322   unsigned length_code = (unsigned)searchCodeIndex(LENGTHBASE, 29, length);
   1323   unsigned extra_length = (unsigned)(length - LENGTHBASE[length_code]);
   1324   unsigned dist_code = (unsigned)searchCodeIndex(DISTANCEBASE, 30, distance);
   1325   unsigned extra_distance = (unsigned)(distance - DISTANCEBASE[dist_code]);
   1326 
   1327   uivector_push_back(values, length_code + FIRST_LENGTH_CODE_INDEX);
   1328   uivector_push_back(values, extra_length);
   1329   uivector_push_back(values, dist_code);
   1330   uivector_push_back(values, extra_distance);
   1331 }
   1332 
   1333 static const unsigned HASH_BIT_MASK = 65535;
   1334 static const unsigned HASH_NUM_VALUES = 65536;
   1335 static const unsigned HASH_NUM_CHARACTERS = 3;
   1336 static const unsigned HASH_SHIFT = 2;
   1337 /*
   1338 The HASH_NUM_CHARACTERS value is used to make encoding faster by using longer
   1339 sequences to generate a hash value from the stream bytes. Setting it to 3
   1340 gives exactly the same compression as the brute force method, since deflate's
   1341 run length encoding starts with lengths of 3. Setting it to higher values,
   1342 like 6, can make the encoding faster (not always though!), but will cause the
   1343 encoding to miss any length between 3 and this value, so that the compression
   1344 may be worse (but this can vary too depending on the image, sometimes it is
   1345 even a bit better instead).
   1346 The HASH_NUM_VALUES is the amount of unique possible hash values that
   1347 combinations of bytes can give, the higher it is the more memory is needed, but
   1348 if it's too low the advantage of hashing is gone.
   1349 */
   1350 
   1351 typedef struct Hash
   1352 {
   1353   int* head; /*hash value to head circular pos*/
   1354   int* val; /*circular pos to hash value*/
   1355   /*circular pos to prev circular pos*/
   1356   unsigned short* chain;
   1357   unsigned short* zeros;
   1358 } Hash;
   1359 
   1360 static unsigned hash_init(Hash* hash, unsigned windowsize)
   1361 {
   1362   unsigned i;
   1363   hash->head = (int*)lodepng_malloc(sizeof(int) * HASH_NUM_VALUES);
   1364   hash->val = (int*)lodepng_malloc(sizeof(int) * windowsize);
   1365   hash->chain = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
   1366   hash->zeros = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
   1367 
   1368   if(!hash->head || !hash->val || !hash->chain || !hash->zeros) return 83; /*alloc fail*/
   1369 
   1370   /*initialize hash table*/
   1371   for(i = 0; i < HASH_NUM_VALUES; i++) hash->head[i] = -1;
   1372   for(i = 0; i < windowsize; i++) hash->val[i] = -1;
   1373   for(i = 0; i < windowsize; i++) hash->chain[i] = i; /*same value as index indicates uninitialized*/
   1374 
   1375   return 0;
   1376 }
   1377 
   1378 static void hash_cleanup(Hash* hash)
   1379 {
   1380   lodepng_free(hash->head);
   1381   lodepng_free(hash->val);
   1382   lodepng_free(hash->chain);
   1383   lodepng_free(hash->zeros);
   1384 }
   1385 
   1386 static unsigned getHash(const unsigned char* data, size_t size, size_t pos)
   1387 {
   1388   unsigned result = 0;
   1389   if (HASH_NUM_CHARACTERS == 3 && pos + 2 < size) {
   1390     result ^= (data[pos + 0] << (0 * HASH_SHIFT));
   1391     result ^= (data[pos + 1] << (1 * HASH_SHIFT));
   1392     result ^= (data[pos + 2] << (2 * HASH_SHIFT));
   1393   } else {
   1394     size_t amount, i;
   1395     if(pos >= size) return 0;
   1396     amount = HASH_NUM_CHARACTERS;
   1397     if(pos + amount >= size) amount = size - pos;
   1398     for(i = 0; i < amount; i++) result ^= (data[pos + i] << (i * HASH_SHIFT));
   1399   }
   1400   return result & HASH_BIT_MASK;
   1401 }
   1402 
   1403 static unsigned countZeros(const unsigned char* data, size_t size, size_t pos)
   1404 {
   1405   const unsigned char* start = data + pos;
   1406   const unsigned char* end = start + MAX_SUPPORTED_DEFLATE_LENGTH;
   1407   if(end > data + size) end = data + size;
   1408   data = start;
   1409   while (data != end && *data == 0) data++;
   1410   /*subtracting two addresses returned as 32-bit number (max value is MAX_SUPPORTED_DEFLATE_LENGTH)*/
   1411   return (unsigned)(data - start);
   1412 }
   1413 
   1414 /*wpos = pos & (windowsize - 1)*/
   1415 static void updateHashChain(Hash* hash, size_t wpos, int hashval)
   1416 {
   1417   hash->val[wpos] = hashval;
   1418   if(hash->head[hashval] != -1) hash->chain[wpos] = hash->head[hashval];
   1419   hash->head[hashval] = wpos;
   1420 }
   1421 
   1422 /*
   1423 LZ77-encode the data. Return value is error code. The input are raw bytes, the output
   1424 is in the form of unsigned integers with codes representing for example literal bytes, or
   1425 length/distance pairs.
   1426 It uses a hash table technique to let it encode faster. When doing LZ77 encoding, a
   1427 sliding window (of windowsize) is used, and all past bytes in that window can be used as
   1428 the "dictionary". A brute force search through all possible distances would be slow, and
   1429 this hash technique is one out of several ways to speed this up.
   1430 */
   1431 static unsigned encodeLZ77(uivector* out, Hash* hash,
   1432                            const unsigned char* in, size_t inpos, size_t insize, unsigned windowsize,
   1433                            unsigned minmatch, unsigned nicematch, unsigned lazymatching)
   1434 {
   1435   unsigned pos, i, error = 0;
   1436   /*for large window lengths, assume the user wants no compression loss. Otherwise, max hash chain length speedup.*/
   1437   unsigned maxchainlength = windowsize >= 8192 ? windowsize : windowsize / 8;
   1438   unsigned maxlazymatch = windowsize >= 8192 ? MAX_SUPPORTED_DEFLATE_LENGTH : 64;
   1439 
   1440   unsigned usezeros = 1; /*not sure if setting it to false for windowsize < 8192 is better or worse*/
   1441   unsigned numzeros = 0;
   1442 
   1443   unsigned offset; /*the offset represents the distance in LZ77 terminology*/
   1444   unsigned length;
   1445   unsigned lazy = 0;
   1446   unsigned lazylength = 0, lazyoffset = 0;
   1447   unsigned hashval;
   1448   unsigned current_offset, current_length;
   1449   const unsigned char *lastptr, *foreptr, *backptr;
   1450   unsigned hashpos, prevpos;
   1451 
   1452   if(windowsize <= 0 || windowsize > 32768) return 60; /*error: windowsize smaller/larger than allowed*/
   1453   if((windowsize & (windowsize - 1)) != 0) return 90; /*error: must be power of two*/
   1454 
   1455   if(nicematch > MAX_SUPPORTED_DEFLATE_LENGTH) nicematch = MAX_SUPPORTED_DEFLATE_LENGTH;
   1456 
   1457   for(pos = inpos; pos < insize; pos++)
   1458   {
   1459     size_t wpos = pos & (windowsize - 1); /*position for in 'circular' hash buffers*/
   1460     unsigned chainlength = 0;
   1461 
   1462     hashval = getHash(in, insize, pos);
   1463     updateHashChain(hash, wpos, hashval);
   1464 
   1465     if(usezeros && hashval == 0)
   1466     {
   1467       if (numzeros == 0) numzeros = countZeros(in, insize, pos);
   1468       else if (pos + numzeros >= insize || in[pos + numzeros - 1] != 0) numzeros--;
   1469       hash->zeros[wpos] = numzeros;
   1470     }
   1471     else
   1472     {
   1473       numzeros = 0;
   1474     }
   1475 
   1476     /*the length and offset found for the current position*/
   1477     length = 0;
   1478     offset = 0;
   1479 
   1480     prevpos = hash->head[hashval];
   1481     hashpos = hash->chain[prevpos];
   1482 
   1483     lastptr = &in[insize < pos + MAX_SUPPORTED_DEFLATE_LENGTH ? insize : pos + MAX_SUPPORTED_DEFLATE_LENGTH];
   1484 
   1485     /*search for the longest string*/
   1486     for(;;)
   1487     {
   1488       /*stop when went completely around the circular buffer*/
   1489       if(prevpos < wpos && hashpos > prevpos && hashpos <= wpos) break;
   1490       if(prevpos > wpos && (hashpos <= wpos || hashpos > prevpos)) break;
   1491       if(chainlength++ >= maxchainlength) break;
   1492 
   1493       current_offset = hashpos <= wpos ? wpos - hashpos : wpos - hashpos + windowsize;
   1494       if(current_offset > 0)
   1495       {
   1496         /*test the next characters*/
   1497         foreptr = &in[pos];
   1498         backptr = &in[pos - current_offset];
   1499 
   1500         /*common case in PNGs is lots of zeros. Quickly skip over them as a speedup*/
   1501         if(usezeros && hashval == 0 && hash->val[hashpos] == 0 /*hashval[hashpos] may be out of date*/)
   1502         {
   1503           unsigned skip = hash->zeros[hashpos];
   1504           if(skip > numzeros) skip = numzeros;
   1505           backptr += skip;
   1506           foreptr += skip;
   1507         }
   1508 
   1509         while(foreptr != lastptr && *backptr == *foreptr) /*maximum supported length by deflate is max length*/
   1510         {
   1511           ++backptr;
   1512           ++foreptr;
   1513         }
   1514         current_length = (unsigned)(foreptr - &in[pos]);
   1515 
   1516         if(current_length > length)
   1517         {
   1518           length = current_length; /*the longest length*/
   1519           offset = current_offset; /*the offset that is related to this longest length*/
   1520           /*jump out once a length of max length is found (speed gain). This also jumps
   1521           out if length is MAX_SUPPORTED_DEFLATE_LENGTH*/
   1522           if(current_length >= nicematch) break;
   1523         }
   1524       }
   1525 
   1526       if(hashpos == hash->chain[hashpos]) break;
   1527 
   1528       prevpos = hashpos;
   1529       hashpos = hash->chain[hashpos];
   1530     }
   1531 
   1532     if(lazymatching)
   1533     {
   1534       if(!lazy && length >= 3 && length <= maxlazymatch && length < MAX_SUPPORTED_DEFLATE_LENGTH)
   1535       {
   1536         lazy = 1;
   1537         lazylength = length;
   1538         lazyoffset = offset;
   1539         continue; /*try the next byte*/
   1540       }
   1541       if(lazy)
   1542       {
   1543         lazy = 0;
   1544         if(pos == 0) ERROR_BREAK(81);
   1545         if(length > lazylength + 1)
   1546         {
   1547           /*push the previous character as literal*/
   1548           if(!uivector_push_back(out, in[pos - 1])) ERROR_BREAK(83 /*alloc fail*/);
   1549         }
   1550         else
   1551         {
   1552           length = lazylength;
   1553           offset = lazyoffset;
   1554           hash->head[hashval] = -1; /*the same hashchain update will be done, this ensures no wrong alteration*/
   1555           pos--;
   1556         }
   1557       }
   1558     }
   1559     if(length >= 3 && offset > windowsize) ERROR_BREAK(86 /*too big (or overflown negative) offset*/);
   1560 
   1561     /*encode it as length/distance pair or literal value*/
   1562     if(length < 3) /*only lengths of 3 or higher are supported as length/distance pair*/
   1563     {
   1564       if(!uivector_push_back(out, in[pos])) ERROR_BREAK(83 /*alloc fail*/);
   1565     }
   1566     else if(length < minmatch || (length == 3 && offset > 4096))
   1567     {
   1568       /*compensate for the fact that longer offsets have more extra bits, a
   1569       length of only 3 may be not worth it then*/
   1570       if(!uivector_push_back(out, in[pos])) ERROR_BREAK(83 /*alloc fail*/);
   1571     }
   1572     else
   1573     {
   1574       addLengthDistance(out, length, offset);
   1575       for(i = 1; i < length; i++)
   1576       {
   1577         pos++;
   1578         wpos = pos & (windowsize - 1);
   1579         hashval = getHash(in, insize, pos);
   1580         updateHashChain(hash, wpos, hashval);
   1581         if(usezeros && hashval == 0)
   1582         {
   1583           if (numzeros == 0) numzeros = countZeros(in, insize, pos);
   1584           else if (pos + numzeros >= insize || in[pos + numzeros - 1] != 0) numzeros--;
   1585           hash->zeros[wpos] = numzeros;
   1586         }
   1587         else
   1588         {
   1589           numzeros = 0;
   1590         }
   1591       }
   1592     }
   1593   } /*end of the loop through each character of input*/
   1594 
   1595   return error;
   1596 }
   1597 
   1598 /* /////////////////////////////////////////////////////////////////////////// */
   1599 
   1600 static unsigned deflateNoCompression(ucvector* out, const unsigned char* data, size_t datasize)
   1601 {
   1602   /*non compressed deflate block data: 1 bit BFINAL,2 bits BTYPE,(5 bits): it jumps to start of next byte,
   1603   2 bytes LEN, 2 bytes NLEN, LEN bytes literal DATA*/
   1604 
   1605   size_t i, j, numdeflateblocks = (datasize + 65534) / 65535;
   1606   unsigned datapos = 0;
   1607   for(i = 0; i < numdeflateblocks; i++)
   1608   {
   1609     unsigned BFINAL, BTYPE, LEN, NLEN;
   1610     unsigned char firstbyte;
   1611 
   1612     BFINAL = (i == numdeflateblocks - 1);
   1613     BTYPE = 0;
   1614 
   1615     firstbyte = (unsigned char)(BFINAL + ((BTYPE & 1) << 1) + ((BTYPE & 2) << 1));
   1616     ucvector_push_back(out, firstbyte);
   1617 
   1618     LEN = 65535;
   1619     if(datasize - datapos < 65535) LEN = (unsigned)datasize - datapos;
   1620     NLEN = 65535 - LEN;
   1621 
   1622     ucvector_push_back(out, (unsigned char)(LEN % 256));
   1623     ucvector_push_back(out, (unsigned char)(LEN / 256));
   1624     ucvector_push_back(out, (unsigned char)(NLEN % 256));
   1625     ucvector_push_back(out, (unsigned char)(NLEN / 256));
   1626 
   1627     /*Decompressed data*/
   1628     for(j = 0; j < 65535 && datapos < datasize; j++)
   1629     {
   1630       ucvector_push_back(out, data[datapos++]);
   1631     }
   1632   }
   1633 
   1634   return 0;
   1635 }
   1636 
   1637 /*
   1638 write the lz77-encoded data, which has lit, len and dist codes, to compressed stream using huffman trees.
   1639 tree_ll: the tree for lit and len codes.
   1640 tree_d: the tree for distance codes.
   1641 */
   1642 static void writeLZ77data(size_t* bp, ucvector* out, const uivector* lz77_encoded,
   1643                           const HuffmanTree* tree_ll, const HuffmanTree* tree_d)
   1644 {
   1645   size_t i = 0;
   1646   for(i = 0; i < lz77_encoded->size; i++)
   1647   {
   1648     unsigned val = lz77_encoded->data[i];
   1649     addHuffmanSymbol(bp, out, HuffmanTree_getCode(tree_ll, val), HuffmanTree_getLength(tree_ll, val));
   1650     if(val > 256) /*for a length code, 3 more things have to be added*/
   1651     {
   1652       unsigned length_index = val - FIRST_LENGTH_CODE_INDEX;
   1653       unsigned n_length_extra_bits = LENGTHEXTRA[length_index];
   1654       unsigned length_extra_bits = lz77_encoded->data[++i];
   1655 
   1656       unsigned distance_code = lz77_encoded->data[++i];
   1657 
   1658       unsigned distance_index = distance_code;
   1659       unsigned n_distance_extra_bits = DISTANCEEXTRA[distance_index];
   1660       unsigned distance_extra_bits = lz77_encoded->data[++i];
   1661 
   1662       addBitsToStream(bp, out, length_extra_bits, n_length_extra_bits);
   1663       addHuffmanSymbol(bp, out, HuffmanTree_getCode(tree_d, distance_code),
   1664                        HuffmanTree_getLength(tree_d, distance_code));
   1665       addBitsToStream(bp, out, distance_extra_bits, n_distance_extra_bits);
   1666     }
   1667   }
   1668 }
   1669 
   1670 /*Deflate for a block of type "dynamic", that is, with freely, optimally, created huffman trees*/
   1671 static unsigned deflateDynamic(ucvector* out, size_t* bp, Hash* hash,
   1672                                const unsigned char* data, size_t datapos, size_t dataend,
   1673                                const LodePNGCompressSettings* settings, int final)
   1674 {
   1675   unsigned error = 0;
   1676 
   1677   /*
   1678   A block is compressed as follows: The PNG data is lz77 encoded, resulting in
   1679   literal bytes and length/distance pairs. This is then huffman compressed with
   1680   two huffman trees. One huffman tree is used for the lit and len values ("ll"),
   1681   another huffman tree is used for the dist values ("d"). These two trees are
   1682   stored using their code lengths, and to compress even more these code lengths
   1683   are also run-length encoded and huffman compressed. This gives a huffman tree
   1684   of code lengths "cl". The code lenghts used to describe this third tree are
   1685   the code length code lengths ("clcl").
   1686   */
   1687 
   1688   /*The lz77 encoded data, represented with integers since there will also be length and distance codes in it*/
   1689   uivector lz77_encoded;
   1690   HuffmanTree tree_ll; /*tree for lit,len values*/
   1691   HuffmanTree tree_d; /*tree for distance codes*/
   1692   HuffmanTree tree_cl; /*tree for encoding the code lengths representing tree_ll and tree_d*/
   1693   uivector frequencies_ll; /*frequency of lit,len codes*/
   1694   uivector frequencies_d; /*frequency of dist codes*/
   1695   uivector frequencies_cl; /*frequency of code length codes*/
   1696   uivector bitlen_lld; /*lit,len,dist code lenghts (int bits), literally (without repeat codes).*/
   1697   uivector bitlen_lld_e; /*bitlen_lld encoded with repeat codes (this is a rudemtary run length compression)*/
   1698   /*bitlen_cl is the code length code lengths ("clcl"). The bit lengths of codes to represent tree_cl
   1699   (these are written as is in the file, it would be crazy to compress these using yet another huffman
   1700   tree that needs to be represented by yet another set of code lengths)*/
   1701   uivector bitlen_cl;
   1702   size_t datasize = dataend - datapos;
   1703 
   1704   /*
   1705   Due to the huffman compression of huffman tree representations ("two levels"), there are some anologies:
   1706   bitlen_lld is to tree_cl what data is to tree_ll and tree_d.
   1707   bitlen_lld_e is to bitlen_lld what lz77_encoded is to data.
   1708   bitlen_cl is to bitlen_lld_e what bitlen_lld is to lz77_encoded.
   1709   */
   1710 
   1711   unsigned BFINAL = final;
   1712   size_t numcodes_ll, numcodes_d, i;
   1713   unsigned HLIT, HDIST, HCLEN;
   1714 
   1715   uivector_init(&lz77_encoded);
   1716   HuffmanTree_init(&tree_ll);
   1717   HuffmanTree_init(&tree_d);
   1718   HuffmanTree_init(&tree_cl);
   1719   uivector_init(&frequencies_ll);
   1720   uivector_init(&frequencies_d);
   1721   uivector_init(&frequencies_cl);
   1722   uivector_init(&bitlen_lld);
   1723   uivector_init(&bitlen_lld_e);
   1724   uivector_init(&bitlen_cl);
   1725 
   1726   /*This while loop never loops due to a break at the end, it is here to
   1727   allow breaking out of it to the cleanup phase on error conditions.*/
   1728   while(!error)
   1729   {
   1730     if(settings->use_lz77)
   1731     {
   1732       error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize,
   1733                          settings->minmatch, settings->nicematch, settings->lazymatching);
   1734       if(error) break;
   1735     }
   1736     else
   1737     {
   1738       if(!uivector_resize(&lz77_encoded, datasize)) ERROR_BREAK(83 /*alloc fail*/);
   1739       for(i = datapos; i < dataend; i++) lz77_encoded.data[i] = data[i]; /*no LZ77, but still will be Huffman compressed*/
   1740     }
   1741 
   1742     if(!uivector_resizev(&frequencies_ll, 286, 0)) ERROR_BREAK(83 /*alloc fail*/);
   1743     if(!uivector_resizev(&frequencies_d, 30, 0)) ERROR_BREAK(83 /*alloc fail*/);
   1744 
   1745     /*Count the frequencies of lit, len and dist codes*/
   1746     for(i = 0; i < lz77_encoded.size; i++)
   1747     {
   1748       unsigned symbol = lz77_encoded.data[i];
   1749       frequencies_ll.data[symbol]++;
   1750       if(symbol > 256)
   1751       {
   1752         unsigned dist = lz77_encoded.data[i + 2];
   1753         frequencies_d.data[dist]++;
   1754         i += 3;
   1755       }
   1756     }
   1757     frequencies_ll.data[256] = 1; /*there will be exactly 1 end code, at the end of the block*/
   1758 
   1759     /*Make both huffman trees, one for the lit and len codes, one for the dist codes*/
   1760     error = HuffmanTree_makeFromFrequencies(&tree_ll, frequencies_ll.data, 257, frequencies_ll.size, 15);
   1761     if(error) break;
   1762     /*2, not 1, is chosen for mincodes: some buggy PNG decoders require at least 2 symbols in the dist tree*/
   1763     error = HuffmanTree_makeFromFrequencies(&tree_d, frequencies_d.data, 2, frequencies_d.size, 15);
   1764     if(error) break;
   1765 
   1766     numcodes_ll = tree_ll.numcodes; if(numcodes_ll > 286) numcodes_ll = 286;
   1767     numcodes_d = tree_d.numcodes; if(numcodes_d > 30) numcodes_d = 30;
   1768     /*store the code lengths of both generated trees in bitlen_lld*/
   1769     for(i = 0; i < numcodes_ll; i++) uivector_push_back(&bitlen_lld, HuffmanTree_getLength(&tree_ll, (unsigned)i));
   1770     for(i = 0; i < numcodes_d; i++) uivector_push_back(&bitlen_lld, HuffmanTree_getLength(&tree_d, (unsigned)i));
   1771 
   1772     /*run-length compress bitlen_ldd into bitlen_lld_e by using repeat codes 16 (copy length 3-6 times),
   1773     17 (3-10 zeroes), 18 (11-138 zeroes)*/
   1774     for(i = 0; i < (unsigned)bitlen_lld.size; i++)
   1775     {
   1776       unsigned j = 0; /*amount of repititions*/
   1777       while(i + j + 1 < (unsigned)bitlen_lld.size && bitlen_lld.data[i + j + 1] == bitlen_lld.data[i]) j++;
   1778 
   1779       if(bitlen_lld.data[i] == 0 && j >= 2) /*repeat code for zeroes*/
   1780       {
   1781         j++; /*include the first zero*/
   1782         if(j <= 10) /*repeat code 17 supports max 10 zeroes*/
   1783         {
   1784           uivector_push_back(&bitlen_lld_e, 17);
   1785           uivector_push_back(&bitlen_lld_e, j - 3);
   1786         }
   1787         else /*repeat code 18 supports max 138 zeroes*/
   1788         {
   1789           if(j > 138) j = 138;
   1790           uivector_push_back(&bitlen_lld_e, 18);
   1791           uivector_push_back(&bitlen_lld_e, j - 11);
   1792         }
   1793         i += (j - 1);
   1794       }
   1795       else if(j >= 3) /*repeat code for value other than zero*/
   1796       {
   1797         size_t k;
   1798         unsigned num = j / 6, rest = j % 6;
   1799         uivector_push_back(&bitlen_lld_e, bitlen_lld.data[i]);
   1800         for(k = 0; k < num; k++)
   1801         {
   1802           uivector_push_back(&bitlen_lld_e, 16);
   1803           uivector_push_back(&bitlen_lld_e, 6 - 3);
   1804         }
   1805         if(rest >= 3)
   1806         {
   1807           uivector_push_back(&bitlen_lld_e, 16);
   1808           uivector_push_back(&bitlen_lld_e, rest - 3);
   1809         }
   1810         else j -= rest;
   1811         i += j;
   1812       }
   1813       else /*too short to benefit from repeat code*/
   1814       {
   1815         uivector_push_back(&bitlen_lld_e, bitlen_lld.data[i]);
   1816       }
   1817     }
   1818 
   1819     /*generate tree_cl, the huffmantree of huffmantrees*/
   1820 
   1821     if(!uivector_resizev(&frequencies_cl, NUM_CODE_LENGTH_CODES, 0)) ERROR_BREAK(83 /*alloc fail*/);
   1822     for(i = 0; i < bitlen_lld_e.size; i++)
   1823     {
   1824       frequencies_cl.data[bitlen_lld_e.data[i]]++;
   1825       /*after a repeat code come the bits that specify the number of repetitions,
   1826       those don't need to be in the frequencies_cl calculation*/
   1827       if(bitlen_lld_e.data[i] >= 16) i++;
   1828     }
   1829 
   1830     error = HuffmanTree_makeFromFrequencies(&tree_cl, frequencies_cl.data,
   1831                                             frequencies_cl.size, frequencies_cl.size, 7);
   1832     if(error) break;
   1833 
   1834     if(!uivector_resize(&bitlen_cl, tree_cl.numcodes)) ERROR_BREAK(83 /*alloc fail*/);
   1835     for(i = 0; i < tree_cl.numcodes; i++)
   1836     {
   1837       /*lenghts of code length tree is in the order as specified by deflate*/
   1838       bitlen_cl.data[i] = HuffmanTree_getLength(&tree_cl, CLCL_ORDER[i]);
   1839     }
   1840     while(bitlen_cl.data[bitlen_cl.size - 1] == 0 && bitlen_cl.size > 4)
   1841     {
   1842       /*remove zeros at the end, but minimum size must be 4*/
   1843       if(!uivector_resize(&bitlen_cl, bitlen_cl.size - 1)) ERROR_BREAK(83 /*alloc fail*/);
   1844     }
   1845     if(error) break;
   1846 
   1847     /*
   1848     Write everything into the output
   1849 
   1850     After the BFINAL and BTYPE, the dynamic block consists out of the following:
   1851     - 5 bits HLIT, 5 bits HDIST, 4 bits HCLEN
   1852     - (HCLEN+4)*3 bits code lengths of code length alphabet
   1853     - HLIT + 257 code lenghts of lit/length alphabet (encoded using the code length
   1854       alphabet, + possible repetition codes 16, 17, 18)
   1855     - HDIST + 1 code lengths of distance alphabet (encoded using the code length
   1856       alphabet, + possible repetition codes 16, 17, 18)
   1857     - compressed data
   1858     - 256 (end code)
   1859     */
   1860 
   1861     /*Write block type*/
   1862     addBitToStream(bp, out, BFINAL);
   1863     addBitToStream(bp, out, 0); /*first bit of BTYPE "dynamic"*/
   1864     addBitToStream(bp, out, 1); /*second bit of BTYPE "dynamic"*/
   1865 
   1866     /*write the HLIT, HDIST and HCLEN values*/
   1867     HLIT = (unsigned)(numcodes_ll - 257);
   1868     HDIST = (unsigned)(numcodes_d - 1);
   1869     HCLEN = (unsigned)bitlen_cl.size - 4;
   1870     /*trim zeroes for HCLEN. HLIT and HDIST were already trimmed at tree creation*/
   1871     while(!bitlen_cl.data[HCLEN + 4 - 1] && HCLEN > 0) HCLEN--;
   1872     addBitsToStream(bp, out, HLIT, 5);
   1873     addBitsToStream(bp, out, HDIST, 5);
   1874     addBitsToStream(bp, out, HCLEN, 4);
   1875 
   1876     /*write the code lenghts of the code length alphabet*/
   1877     for(i = 0; i < HCLEN + 4; i++) addBitsToStream(bp, out, bitlen_cl.data[i], 3);
   1878 
   1879     /*write the lenghts of the lit/len AND the dist alphabet*/
   1880     for(i = 0; i < bitlen_lld_e.size; i++)
   1881     {
   1882       addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_cl, bitlen_lld_e.data[i]),
   1883                        HuffmanTree_getLength(&tree_cl, bitlen_lld_e.data[i]));
   1884       /*extra bits of repeat codes*/
   1885       if(bitlen_lld_e.data[i] == 16) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 2);
   1886       else if(bitlen_lld_e.data[i] == 17) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 3);
   1887       else if(bitlen_lld_e.data[i] == 18) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 7);
   1888     }
   1889 
   1890     /*write the compressed data symbols*/
   1891     writeLZ77data(bp, out, &lz77_encoded, &tree_ll, &tree_d);
   1892     /*error: the length of the end code 256 must be larger than 0*/
   1893     if(HuffmanTree_getLength(&tree_ll, 256) == 0) ERROR_BREAK(64);
   1894 
   1895     /*write the end code*/
   1896     addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, 256), HuffmanTree_getLength(&tree_ll, 256));
   1897 
   1898     break; /*end of error-while*/
   1899   }
   1900 
   1901   /*cleanup*/
   1902   uivector_cleanup(&lz77_encoded);
   1903   HuffmanTree_cleanup(&tree_ll);
   1904   HuffmanTree_cleanup(&tree_d);
   1905   HuffmanTree_cleanup(&tree_cl);
   1906   uivector_cleanup(&frequencies_ll);
   1907   uivector_cleanup(&frequencies_d);
   1908   uivector_cleanup(&frequencies_cl);
   1909   uivector_cleanup(&bitlen_lld_e);
   1910   uivector_cleanup(&bitlen_lld);
   1911   uivector_cleanup(&bitlen_cl);
   1912 
   1913   return error;
   1914 }
   1915 
   1916 static unsigned deflateFixed(ucvector* out, size_t* bp, Hash* hash,
   1917                              const unsigned char* data,
   1918                              size_t datapos, size_t dataend,
   1919                              const LodePNGCompressSettings* settings, int final)
   1920 {
   1921   HuffmanTree tree_ll; /*tree for literal values and length codes*/
   1922   HuffmanTree tree_d; /*tree for distance codes*/
   1923 
   1924   unsigned BFINAL = final;
   1925   unsigned error = 0;
   1926   size_t i;
   1927 
   1928   HuffmanTree_init(&tree_ll);
   1929   HuffmanTree_init(&tree_d);
   1930 
   1931   generateFixedLitLenTree(&tree_ll);
   1932   generateFixedDistanceTree(&tree_d);
   1933 
   1934   addBitToStream(bp, out, BFINAL);
   1935   addBitToStream(bp, out, 1); /*first bit of BTYPE*/
   1936   addBitToStream(bp, out, 0); /*second bit of BTYPE*/
   1937 
   1938   if(settings->use_lz77) /*LZ77 encoded*/
   1939   {
   1940     uivector lz77_encoded;
   1941     uivector_init(&lz77_encoded);
   1942     error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize,
   1943                        settings->minmatch, settings->nicematch, settings->lazymatching);
   1944     if(!error) writeLZ77data(bp, out, &lz77_encoded, &tree_ll, &tree_d);
   1945     uivector_cleanup(&lz77_encoded);
   1946   }
   1947   else /*no LZ77, but still will be Huffman compressed*/
   1948   {
   1949     for(i = datapos; i < dataend; i++)
   1950     {
   1951       addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, data[i]), HuffmanTree_getLength(&tree_ll, data[i]));
   1952     }
   1953   }
   1954   /*add END code*/
   1955   if(!error) addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, 256), HuffmanTree_getLength(&tree_ll, 256));
   1956 
   1957   /*cleanup*/
   1958   HuffmanTree_cleanup(&tree_ll);
   1959   HuffmanTree_cleanup(&tree_d);
   1960 
   1961   return error;
   1962 }
   1963 
   1964 static unsigned lodepng_deflatev(ucvector* out, const unsigned char* in, size_t insize,
   1965                                  const LodePNGCompressSettings* settings)
   1966 {
   1967   unsigned error = 0;
   1968   size_t i, blocksize, numdeflateblocks;
   1969   size_t bp = 0; /*the bit pointer*/
   1970   Hash hash;
   1971 
   1972   if(settings->btype > 2) return 61;
   1973   else if(settings->btype == 0) return deflateNoCompression(out, in, insize);
   1974   else if(settings->btype == 1) blocksize = insize;
   1975   else /*if(settings->btype == 2)*/
   1976   {
   1977     blocksize = insize / 8 + 8;
   1978     if(blocksize < 65535) blocksize = 65535;
   1979   }
   1980 
   1981   numdeflateblocks = (insize + blocksize - 1) / blocksize;
   1982   if(numdeflateblocks == 0) numdeflateblocks = 1;
   1983 
   1984   error = hash_init(&hash, settings->windowsize);
   1985   if(error) return error;
   1986 
   1987   for(i = 0; i < numdeflateblocks && !error; i++)
   1988   {
   1989     int final = i == numdeflateblocks - 1;
   1990     size_t start = i * blocksize;
   1991     size_t end = start + blocksize;
   1992     if(end > insize) end = insize;
   1993 
   1994     if(settings->btype == 1) error = deflateFixed(out, &bp, &hash, in, start, end, settings, final);
   1995     else if(settings->btype == 2) error = deflateDynamic(out, &bp, &hash, in, start, end, settings, final);
   1996   }
   1997 
   1998   hash_cleanup(&hash);
   1999 
   2000   return error;
   2001 }
   2002 
   2003 unsigned lodepng_deflate(unsigned char** out, size_t* outsize,
   2004                          const unsigned char* in, size_t insize,
   2005                          const LodePNGCompressSettings* settings)
   2006 {
   2007   unsigned error;
   2008   ucvector v;
   2009   ucvector_init_buffer(&v, *out, *outsize);
   2010   error = lodepng_deflatev(&v, in, insize, settings);
   2011   *out = v.data;
   2012   *outsize = v.size;
   2013   return error;
   2014 }
   2015 
   2016 static unsigned deflate(unsigned char** out, size_t* outsize,
   2017                         const unsigned char* in, size_t insize,
   2018                         const LodePNGCompressSettings* settings)
   2019 {
   2020   if(settings->custom_deflate)
   2021   {
   2022     return settings->custom_deflate(out, outsize, in, insize, settings);
   2023   }
   2024   else
   2025   {
   2026     return lodepng_deflate(out, outsize, in, insize, settings);
   2027   }
   2028 }
   2029 
   2030 #endif /*LODEPNG_COMPILE_DECODER*/
   2031 
   2032 /* ////////////////////////////////////////////////////////////////////////// */
   2033 /* / Adler32                                                                  */
   2034 /* ////////////////////////////////////////////////////////////////////////// */
   2035 
   2036 static unsigned update_adler32(unsigned adler, const unsigned char* data, unsigned len)
   2037 {
   2038    unsigned s1 = adler & 0xffff;
   2039    unsigned s2 = (adler >> 16) & 0xffff;
   2040 
   2041   while(len > 0)
   2042   {
   2043     /*at least 5550 sums can be done before the sums overflow, saving a lot of module divisions*/
   2044     unsigned amount = len > 5550 ? 5550 : len;
   2045     len -= amount;
   2046     while(amount > 0)
   2047     {
   2048       s1 += (*data++);
   2049       s2 += s1;
   2050       amount--;
   2051     }
   2052     s1 %= 65521;
   2053     s2 %= 65521;
   2054   }
   2055 
   2056   return (s2 << 16) | s1;
   2057 }
   2058 
   2059 /*Return the adler32 of the bytes data[0..len-1]*/
   2060 static unsigned adler32(const unsigned char* data, unsigned len)
   2061 {
   2062   return update_adler32(1L, data, len);
   2063 }
   2064 
   2065 /* ////////////////////////////////////////////////////////////////////////// */
   2066 /* / Zlib                                                                   / */
   2067 /* ////////////////////////////////////////////////////////////////////////// */
   2068 
   2069 #ifdef LODEPNG_COMPILE_DECODER
   2070 
   2071 unsigned lodepng_zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
   2072                                  size_t insize, const LodePNGDecompressSettings* settings)
   2073 {
   2074   unsigned error = 0;
   2075   unsigned CM, CINFO, FDICT;
   2076 
   2077   if(insize < 2) return 53; /*error, size of zlib data too small*/
   2078   /*read information from zlib header*/
   2079   if((in[0] * 256 + in[1]) % 31 != 0)
   2080   {
   2081     /*error: 256 * in[0] + in[1] must be a multiple of 31, the FCHECK value is supposed to be made that way*/
   2082     return 24;
   2083   }
   2084 
   2085   CM = in[0] & 15;
   2086   CINFO = (in[0] >> 4) & 15;
   2087   /*FCHECK = in[1] & 31;*/ /*FCHECK is already tested above*/
   2088   FDICT = (in[1] >> 5) & 1;
   2089   /*FLEVEL = (in[1] >> 6) & 3;*/ /*FLEVEL is not used here*/
   2090 
   2091   if(CM != 8 || CINFO > 7)
   2092   {
   2093     /*error: only compression method 8: inflate with sliding window of 32k is supported by the PNG spec*/
   2094     return 25;
   2095   }
   2096   if(FDICT != 0)
   2097   {
   2098     /*error: the specification of PNG says about the zlib stream:
   2099       "The additional flags shall not specify a preset dictionary."*/
   2100     return 26;
   2101   }
   2102 
   2103   error = inflate(out, outsize, in + 2, insize - 2, settings);
   2104   if(error) return error;
   2105 
   2106   if(!settings->ignore_adler32)
   2107   {
   2108     unsigned ADLER32 = lodepng_read32bitInt(&in[insize - 4]);
   2109     unsigned checksum = adler32(*out, (unsigned)(*outsize));
   2110     if(checksum != ADLER32) return 58; /*error, adler checksum not correct, data must be corrupted*/
   2111   }
   2112 
   2113   return 0; /*no error*/
   2114 }
   2115 
   2116 static unsigned zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
   2117                                 size_t insize, const LodePNGDecompressSettings* settings)
   2118 {
   2119   if(settings->custom_zlib)
   2120   {
   2121     return settings->custom_zlib(out, outsize, in, insize, settings);
   2122   }
   2123   else
   2124   {
   2125     return lodepng_zlib_decompress(out, outsize, in, insize, settings);
   2126   }
   2127 }
   2128 
   2129 #endif /*LODEPNG_COMPILE_DECODER*/
   2130 
   2131 #ifdef LODEPNG_COMPILE_ENCODER
   2132 
   2133 unsigned lodepng_zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
   2134                                size_t insize, const LodePNGCompressSettings* settings)
   2135 {
   2136   /*initially, *out must be NULL and outsize 0, if you just give some random *out
   2137   that's pointing to a non allocated buffer, this'll crash*/
   2138   ucvector outv;
   2139   size_t i;
   2140   unsigned error;
   2141   unsigned char* deflatedata = 0;
   2142   size_t deflatesize = 0;
   2143 
   2144   unsigned ADLER32;
   2145   /*zlib data: 1 byte CMF (CM+CINFO), 1 byte FLG, deflate data, 4 byte ADLER32 checksum of the Decompressed data*/
   2146   unsigned CMF = 120; /*0b01111000: CM 8, CINFO 7. With CINFO 7, any window size up to 32768 can be used.*/
   2147   unsigned FLEVEL = 0;
   2148   unsigned FDICT = 0;
   2149   unsigned CMFFLG = 256 * CMF + FDICT * 32 + FLEVEL * 64;
   2150   unsigned FCHECK = 31 - CMFFLG % 31;
   2151   CMFFLG += FCHECK;
   2152 
   2153   /*ucvector-controlled version of the output buffer, for dynamic array*/
   2154   ucvector_init_buffer(&outv, *out, *outsize);
   2155 
   2156   ucvector_push_back(&outv, (unsigned char)(CMFFLG / 256));
   2157   ucvector_push_back(&outv, (unsigned char)(CMFFLG % 256));
   2158 
   2159   error = deflate(&deflatedata, &deflatesize, in, insize, settings);
   2160 
   2161   if(!error)
   2162   {
   2163     ADLER32 = adler32(in, (unsigned)insize);
   2164     for(i = 0; i < deflatesize; i++) ucvector_push_back(&outv, deflatedata[i]);
   2165     lodepng_free(deflatedata);
   2166     lodepng_add32bitInt(&outv, ADLER32);
   2167   }
   2168 
   2169   *out = outv.data;
   2170   *outsize = outv.size;
   2171 
   2172   return error;
   2173 }
   2174 
   2175 /* compress using the default or custom zlib function */
   2176 static unsigned zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
   2177                               size_t insize, const LodePNGCompressSettings* settings)
   2178 {
   2179   if(settings->custom_zlib)
   2180   {
   2181     return settings->custom_zlib(out, outsize, in, insize, settings);
   2182   }
   2183   else
   2184   {
   2185     return lodepng_zlib_compress(out, outsize, in, insize, settings);
   2186   }
   2187 }
   2188 
   2189 #endif /*LODEPNG_COMPILE_ENCODER*/
   2190 
   2191 #else /*no LODEPNG_COMPILE_ZLIB*/
   2192 
   2193 #ifdef LODEPNG_COMPILE_DECODER
   2194 static unsigned zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
   2195                                 size_t insize, const LodePNGDecompressSettings* settings)
   2196 {
   2197   if (!settings->custom_zlib) return 87; /*no custom zlib function provided */
   2198   return settings->custom_zlib(out, outsize, in, insize, settings);
   2199 }
   2200 #endif /*LODEPNG_COMPILE_DECODER*/
   2201 #ifdef LODEPNG_COMPILE_ENCODER
   2202 static unsigned zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
   2203                               size_t insize, const LodePNGCompressSettings* settings)
   2204 {
   2205   if (!settings->custom_zlib) return 87; /*no custom zlib function provided */
   2206   return settings->custom_zlib(out, outsize, in, insize, settings);
   2207 }
   2208 #endif /*LODEPNG_COMPILE_ENCODER*/
   2209 
   2210 #endif /*LODEPNG_COMPILE_ZLIB*/
   2211 
   2212 /* ////////////////////////////////////////////////////////////////////////// */
   2213 
   2214 #ifdef LODEPNG_COMPILE_ENCODER
   2215 
   2216 /*this is a good tradeoff between speed and compression ratio*/
   2217 #define DEFAULT_WINDOWSIZE 2048
   2218 
   2219 void lodepng_compress_settings_init(LodePNGCompressSettings* settings)
   2220 {
   2221   /*compress with dynamic huffman tree (not in the mathematical sense, just not the predefined one)*/
   2222   settings->btype = 2;
   2223   settings->use_lz77 = 1;
   2224   settings->windowsize = DEFAULT_WINDOWSIZE;
   2225   settings->minmatch = 3;
   2226   settings->nicematch = 128;
   2227   settings->lazymatching = 1;
   2228 
   2229   settings->custom_zlib = 0;
   2230   settings->custom_deflate = 0;
   2231   settings->custom_context = 0;
   2232 }
   2233 
   2234 const LodePNGCompressSettings lodepng_default_compress_settings = {2, 1, DEFAULT_WINDOWSIZE, 3, 128, 1, 0, 0, 0};
   2235 
   2236 
   2237 #endif /*LODEPNG_COMPILE_ENCODER*/
   2238 
   2239 #ifdef LODEPNG_COMPILE_DECODER
   2240 
   2241 void lodepng_decompress_settings_init(LodePNGDecompressSettings* settings)
   2242 {
   2243   settings->ignore_adler32 = 0;
   2244 
   2245   settings->custom_zlib = 0;
   2246   settings->custom_inflate = 0;
   2247   settings->custom_context = 0;
   2248 }
   2249 
   2250 const LodePNGDecompressSettings lodepng_default_decompress_settings = {0, 0, 0, 0};
   2251 
   2252 #endif /*LODEPNG_COMPILE_DECODER*/
   2253 
   2254 /* ////////////////////////////////////////////////////////////////////////// */
   2255 /* ////////////////////////////////////////////////////////////////////////// */
   2256 /* // End of Zlib related code. Begin of PNG related code.                 // */
   2257 /* ////////////////////////////////////////////////////////////////////////// */
   2258 /* ////////////////////////////////////////////////////////////////////////// */
   2259 
   2260 #ifdef LODEPNG_COMPILE_PNG
   2261 
   2262 /* ////////////////////////////////////////////////////////////////////////// */
   2263 /* / CRC32                                                                  / */
   2264 /* ////////////////////////////////////////////////////////////////////////// */
   2265 
   2266 /* CRC polynomial: 0xedb88320 */
   2267 static unsigned lodepng_crc32_table[256] = {
   2268            0u, 1996959894u, 3993919788u, 2567524794u,  124634137u, 1886057615u, 3915621685u, 2657392035u,
   2269    249268274u, 2044508324u, 3772115230u, 2547177864u,  162941995u, 2125561021u, 3887607047u, 2428444049u,
   2270    498536548u, 1789927666u, 4089016648u, 2227061214u,  450548861u, 1843258603u, 4107580753u, 2211677639u,
   2271    325883990u, 1684777152u, 4251122042u, 2321926636u,  335633487u, 1661365465u, 4195302755u, 2366115317u,
   2272    997073096u, 1281953886u, 3579855332u, 2724688242u, 1006888145u, 1258607687u, 3524101629u, 2768942443u,
   2273    901097722u, 1119000684u, 3686517206u, 2898065728u,  853044451u, 1172266101u, 3705015759u, 2882616665u,
   2274    651767980u, 1373503546u, 3369554304u, 3218104598u,  565507253u, 1454621731u, 3485111705u, 3099436303u,
   2275    671266974u, 1594198024u, 3322730930u, 2970347812u,  795835527u, 1483230225u, 3244367275u, 3060149565u,
   2276   1994146192u,   31158534u, 2563907772u, 4023717930u, 1907459465u,  112637215u, 2680153253u, 3904427059u,
   2277   2013776290u,  251722036u, 2517215374u, 3775830040u, 2137656763u,  141376813u, 2439277719u, 3865271297u,
   2278   1802195444u,  476864866u, 2238001368u, 4066508878u, 1812370925u,  453092731u, 2181625025u, 4111451223u,
   2279   1706088902u,  314042704u, 2344532202u, 4240017532u, 1658658271u,  366619977u, 2362670323u, 4224994405u,
   2280   1303535960u,  984961486u, 2747007092u, 3569037538u, 1256170817u, 1037604311u, 2765210733u, 3554079995u,
   2281   1131014506u,  879679996u, 2909243462u, 3663771856u, 1141124467u,  855842277u, 2852801631u, 3708648649u,
   2282   1342533948u,  654459306u, 3188396048u, 3373015174u, 1466479909u,  544179635u, 3110523913u, 3462522015u,
   2283   1591671054u,  702138776u, 2966460450u, 3352799412u, 1504918807u,  783551873u, 3082640443u, 3233442989u,
   2284   3988292384u, 2596254646u,   62317068u, 1957810842u, 3939845945u, 2647816111u,   81470997u, 1943803523u,
   2285   3814918930u, 2489596804u,  225274430u, 2053790376u, 3826175755u, 2466906013u,  167816743u, 2097651377u,
   2286   4027552580u, 2265490386u,  503444072u, 1762050814u, 4150417245u, 2154129355u,  426522225u, 1852507879u,
   2287   4275313526u, 2312317920u,  282753626u, 1742555852u, 4189708143u, 2394877945u,  397917763u, 1622183637u,
   2288   3604390888u, 2714866558u,  953729732u, 1340076626u, 3518719985u, 2797360999u, 1068828381u, 1219638859u,
   2289   3624741850u, 2936675148u,  906185462u, 1090812512u, 3747672003u, 2825379669u,  829329135u, 1181335161u,
   2290   3412177804u, 3160834842u,  628085408u, 1382605366u, 3423369109u, 3138078467u,  570562233u, 1426400815u,
   2291   3317316542u, 2998733608u,  733239954u, 1555261956u, 3268935591u, 3050360625u,  752459403u, 1541320221u,
   2292   2607071920u, 3965973030u, 1969922972u,   40735498u, 2617837225u, 3943577151u, 1913087877u,   83908371u,
   2293   2512341634u, 3803740692u, 2075208622u,  213261112u, 2463272603u, 3855990285u, 2094854071u,  198958881u,
   2294   2262029012u, 4057260610u, 1759359992u,  534414190u, 2176718541u, 4139329115u, 1873836001u,  414664567u,
   2295   2282248934u, 4279200368u, 1711684554u,  285281116u, 2405801727u, 4167216745u, 1634467795u,  376229701u,
   2296   2685067896u, 3608007406u, 1308918612u,  956543938u, 2808555105u, 3495958263u, 1231636301u, 1047427035u,
   2297   2932959818u, 3654703836u, 1088359270u,  936918000u, 2847714899u, 3736837829u, 1202900863u,  817233897u,
   2298   3183342108u, 3401237130u, 1404277552u,  615818150u, 3134207493u, 3453421203u, 1423857449u,  601450431u,
   2299   3009837614u, 3294710456u, 1567103746u,  711928724u, 3020668471u, 3272380065u, 1510334235u,  755167117u
   2300 };
   2301 
   2302 /*Return the CRC of the bytes buf[0..len-1].*/
   2303 unsigned lodepng_crc32(const unsigned char* buf, size_t len)
   2304 {
   2305   unsigned c = 0xffffffffL;
   2306   size_t n;
   2307 
   2308   for(n = 0; n < len; n++)
   2309   {
   2310     c = lodepng_crc32_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
   2311   }
   2312   return c ^ 0xffffffffL;
   2313 }
   2314 
   2315 /* ////////////////////////////////////////////////////////////////////////// */
   2316 /* / Reading and writing single bits and bytes from/to stream for LodePNG   / */
   2317 /* ////////////////////////////////////////////////////////////////////////// */
   2318 
   2319 static unsigned char readBitFromReversedStream(size_t* bitpointer, const unsigned char* bitstream)
   2320 {
   2321   unsigned char result = (unsigned char)((bitstream[(*bitpointer) >> 3] >> (7 - ((*bitpointer) & 0x7))) & 1);
   2322   (*bitpointer)++;
   2323   return result;
   2324 }
   2325 
   2326 static unsigned readBitsFromReversedStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
   2327 {
   2328   unsigned result = 0;
   2329   size_t i;
   2330   for(i = nbits - 1; i < nbits; i--)
   2331   {
   2332     result += (unsigned)readBitFromReversedStream(bitpointer, bitstream) << i;
   2333   }
   2334   return result;
   2335 }
   2336 
   2337 #ifdef LODEPNG_COMPILE_DECODER
   2338 static void setBitOfReversedStream0(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
   2339 {
   2340   /*the current bit in bitstream must be 0 for this to work*/
   2341   if(bit)
   2342   {
   2343     /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/
   2344     bitstream[(*bitpointer) >> 3] |= (bit << (7 - ((*bitpointer) & 0x7)));
   2345   }
   2346   (*bitpointer)++;
   2347 }
   2348 #endif /*LODEPNG_COMPILE_DECODER*/
   2349 
   2350 static void setBitOfReversedStream(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
   2351 {
   2352   /*the current bit in bitstream may be 0 or 1 for this to work*/
   2353   if(bit == 0) bitstream[(*bitpointer) >> 3] &=  (unsigned char)(~(1 << (7 - ((*bitpointer) & 0x7))));
   2354   else         bitstream[(*bitpointer) >> 3] |=  (1 << (7 - ((*bitpointer) & 0x7)));
   2355   (*bitpointer)++;
   2356 }
   2357 
   2358 /* ////////////////////////////////////////////////////////////////////////// */
   2359 /* / PNG chunks                                                             / */
   2360 /* ////////////////////////////////////////////////////////////////////////// */
   2361 
   2362 unsigned lodepng_chunk_length(const unsigned char* chunk)
   2363 {
   2364   return lodepng_read32bitInt(&chunk[0]);
   2365 }
   2366 
   2367 void lodepng_chunk_type(char type[5], const unsigned char* chunk)
   2368 {
   2369   unsigned i;
   2370   for(i = 0; i < 4; i++) type[i] = chunk[4 + i];
   2371   type[4] = 0; /*null termination char*/
   2372 }
   2373 
   2374 unsigned char lodepng_chunk_type_equals(const unsigned char* chunk, const char* type)
   2375 {
   2376   if(strlen(type) != 4) return 0;
   2377   return (chunk[4] == type[0] && chunk[5] == type[1] && chunk[6] == type[2] && chunk[7] == type[3]);
   2378 }
   2379 
   2380 unsigned char lodepng_chunk_ancillary(const unsigned char* chunk)
   2381 {
   2382   return((chunk[4] & 32) != 0);
   2383 }
   2384 
   2385 unsigned char lodepng_chunk_private(const unsigned char* chunk)
   2386 {
   2387   return((chunk[6] & 32) != 0);
   2388 }
   2389 
   2390 unsigned char lodepng_chunk_safetocopy(const unsigned char* chunk)
   2391 {
   2392   return((chunk[7] & 32) != 0);
   2393 }
   2394 
   2395 unsigned char* lodepng_chunk_data(unsigned char* chunk)
   2396 {
   2397   return &chunk[8];
   2398 }
   2399 
   2400 const unsigned char* lodepng_chunk_data_const(const unsigned char* chunk)
   2401 {
   2402   return &chunk[8];
   2403 }
   2404 
   2405 unsigned lodepng_chunk_check_crc(const unsigned char* chunk)
   2406 {
   2407   unsigned length = lodepng_chunk_length(chunk);
   2408   unsigned CRC = lodepng_read32bitInt(&chunk[length + 8]);
   2409   /*the CRC is taken of the data and the 4 chunk type letters, not the length*/
   2410   unsigned checksum = lodepng_crc32(&chunk[4], length + 4);
   2411   if(CRC != checksum) return 1;
   2412   else return 0;
   2413 }
   2414 
   2415 void lodepng_chunk_generate_crc(unsigned char* chunk)
   2416 {
   2417   unsigned length = lodepng_chunk_length(chunk);
   2418   unsigned CRC = lodepng_crc32(&chunk[4], length + 4);
   2419   lodepng_set32bitInt(chunk + 8 + length, CRC);
   2420 }
   2421 
   2422 unsigned char* lodepng_chunk_next(unsigned char* chunk)
   2423 {
   2424   unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
   2425   return &chunk[total_chunk_length];
   2426 }
   2427 
   2428 const unsigned char* lodepng_chunk_next_const(const unsigned char* chunk)
   2429 {
   2430   unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
   2431   return &chunk[total_chunk_length];
   2432 }
   2433 
   2434 unsigned lodepng_chunk_append(unsigned char** out, size_t* outlength, const unsigned char* chunk)
   2435 {
   2436   unsigned i;
   2437   unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
   2438   unsigned char *chunk_start, *new_buffer;
   2439   size_t new_length = (*outlength) + total_chunk_length;
   2440   if(new_length < total_chunk_length || new_length < (*outlength)) return 77; /*integer overflow happened*/
   2441 
   2442   new_buffer = (unsigned char*)lodepng_realloc(*out, new_length);
   2443   if(!new_buffer) return 83; /*alloc fail*/
   2444   (*out) = new_buffer;
   2445   (*outlength) = new_length;
   2446   chunk_start = &(*out)[new_length - total_chunk_length];
   2447 
   2448   for(i = 0; i < total_chunk_length; i++) chunk_start[i] = chunk[i];
   2449 
   2450   return 0;
   2451 }
   2452 
   2453 unsigned lodepng_chunk_create(unsigned char** out, size_t* outlength, unsigned length,
   2454                               const char* type, const unsigned char* data)
   2455 {
   2456   unsigned i;
   2457   unsigned char *chunk, *new_buffer;
   2458   size_t new_length = (*outlength) + length + 12;
   2459   if(new_length < length + 12 || new_length < (*outlength)) return 77; /*integer overflow happened*/
   2460   new_buffer = (unsigned char*)lodepng_realloc(*out, new_length);
   2461   if(!new_buffer) return 83; /*alloc fail*/
   2462   (*out) = new_buffer;
   2463   (*outlength) = new_length;
   2464   chunk = &(*out)[(*outlength) - length - 12];
   2465 
   2466   /*1: length*/
   2467   lodepng_set32bitInt(chunk, (unsigned)length);
   2468 
   2469   /*2: chunk name (4 letters)*/
   2470   chunk[4] = type[0];
   2471   chunk[5] = type[1];
   2472   chunk[6] = type[2];
   2473   chunk[7] = type[3];
   2474 
   2475   /*3: the data*/
   2476   for(i = 0; i < length; i++) chunk[8 + i] = data[i];
   2477 
   2478   /*4: CRC (of the chunkname characters and the data)*/
   2479   lodepng_chunk_generate_crc(chunk);
   2480 
   2481   return 0;
   2482 }
   2483 
   2484 /* ////////////////////////////////////////////////////////////////////////// */
   2485 /* / Color types and such                                                   / */
   2486 /* ////////////////////////////////////////////////////////////////////////// */
   2487 
   2488 /*return type is a LodePNG error code*/
   2489 static unsigned checkColorValidity(LodePNGColorType colortype, unsigned bd) /*bd = bitdepth*/
   2490 {
   2491   switch(colortype)
   2492   {
   2493     case 0: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8 || bd == 16)) return 37; break; /*grey*/
   2494     case 2: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*RGB*/
   2495     case 3: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8            )) return 37; break; /*palette*/
   2496     case 4: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*grey + alpha*/
   2497     case 6: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*RGBA*/
   2498     default: return 31;
   2499   }
   2500   return 0; /*allowed color type / bits combination*/
   2501 }
   2502 
   2503 static unsigned getNumColorChannels(LodePNGColorType colortype)
   2504 {
   2505   switch(colortype)
   2506   {
   2507     case 0: return 1; /*grey*/
   2508     case 2: return 3; /*RGB*/
   2509     case 3: return 1; /*palette*/
   2510     case 4: return 2; /*grey + alpha*/
   2511     case 6: return 4; /*RGBA*/
   2512   }
   2513   return 0; /*unexisting color type*/
   2514 }
   2515 
   2516 static unsigned lodepng_get_bpp_lct(LodePNGColorType colortype, unsigned bitdepth)
   2517 {
   2518   /*bits per pixel is amount of channels * bits per channel*/
   2519   return getNumColorChannels(colortype) * bitdepth;
   2520 }
   2521 
   2522 /* ////////////////////////////////////////////////////////////////////////// */
   2523 
   2524 void lodepng_color_mode_init(LodePNGColorMode* info)
   2525 {
   2526   info->key_defined = 0;
   2527   info->key_r = info->key_g = info->key_b = 0;
   2528   info->colortype = LCT_RGBA;
   2529   info->bitdepth = 8;
   2530   info->palette = 0;
   2531   info->palettesize = 0;
   2532 }
   2533 
   2534 void lodepng_color_mode_cleanup(LodePNGColorMode* info)
   2535 {
   2536   lodepng_palette_clear(info);
   2537 }
   2538 
   2539 unsigned lodepng_color_mode_copy(LodePNGColorMode* dest, const LodePNGColorMode* source)
   2540 {
   2541   size_t i;
   2542   lodepng_color_mode_cleanup(dest);
   2543   *dest = *source;
   2544   if(source->palette)
   2545   {
   2546     dest->palette = (unsigned char*)lodepng_malloc(1024);
   2547     if(!dest->palette && source->palettesize) return 83; /*alloc fail*/
   2548     for(i = 0; i < source->palettesize * 4; i++) dest->palette[i] = source->palette[i];
   2549   }
   2550   return 0;
   2551 }
   2552 
   2553 static int lodepng_color_mode_equal(const LodePNGColorMode* a, const LodePNGColorMode* b)
   2554 {
   2555   size_t i;
   2556   if(a->colortype != b->colortype) return 0;
   2557   if(a->bitdepth != b->bitdepth) return 0;
   2558   if(a->key_defined != b->key_defined) return 0;
   2559   if(a->key_defined)
   2560   {
   2561     if(a->key_r != b->key_r) return 0;
   2562     if(a->key_g != b->key_g) return 0;
   2563     if(a->key_b != b->key_b) return 0;
   2564   }
   2565   if(a->palettesize != b->palettesize) return 0;
   2566   for(i = 0; i < a->palettesize * 4; i++)
   2567   {
   2568     if(a->palette[i] != b->palette[i]) return 0;
   2569   }
   2570   return 1;
   2571 }
   2572 
   2573 void lodepng_palette_clear(LodePNGColorMode* info)
   2574 {
   2575   if(info->palette) lodepng_free(info->palette);
   2576   info->palette = 0;
   2577   info->palettesize = 0;
   2578 }
   2579 
   2580 unsigned lodepng_palette_add(LodePNGColorMode* info,
   2581                              unsigned char r, unsigned char g, unsigned char b, unsigned char a)
   2582 {
   2583   unsigned char* data;
   2584   /*the same resize technique as C++ std::vectors is used, and here it's made so that for a palette with
   2585   the max of 256 colors, it'll have the exact alloc size*/
   2586   if(!info->palette) /*allocate palette if empty*/
   2587   {
   2588     /*room for 256 colors with 4 bytes each*/
   2589     data = (unsigned char*)lodepng_realloc(info->palette, 1024);
   2590     if(!data) return 83; /*alloc fail*/
   2591     else info->palette = data;
   2592   }
   2593   info->palette[4 * info->palettesize + 0] = r;
   2594   info->palette[4 * info->palettesize + 1] = g;
   2595   info->palette[4 * info->palettesize + 2] = b;
   2596   info->palette[4 * info->palettesize + 3] = a;
   2597   info->palettesize++;
   2598   return 0;
   2599 }
   2600 
   2601 unsigned lodepng_get_bpp(const LodePNGColorMode* info)
   2602 {
   2603   /*calculate bits per pixel out of colortype and bitdepth*/
   2604   return lodepng_get_bpp_lct(info->colortype, info->bitdepth);
   2605 }
   2606 
   2607 unsigned lodepng_get_channels(const LodePNGColorMode* info)
   2608 {
   2609   return getNumColorChannels(info->colortype);
   2610 }
   2611 
   2612 unsigned lodepng_is_greyscale_type(const LodePNGColorMode* info)
   2613 {
   2614   return info->colortype == LCT_GREY || info->colortype == LCT_GREY_ALPHA;
   2615 }
   2616 
   2617 unsigned lodepng_is_alpha_type(const LodePNGColorMode* info)
   2618 {
   2619   return (info->colortype & 4) != 0; /*4 or 6*/
   2620 }
   2621 
   2622 unsigned lodepng_is_palette_type(const LodePNGColorMode* info)
   2623 {
   2624   return info->colortype == LCT_PALETTE;
   2625 }
   2626 
   2627 unsigned lodepng_has_palette_alpha(const LodePNGColorMode* info)
   2628 {
   2629   size_t i;
   2630   for(i = 0; i < info->palettesize; i++)
   2631   {
   2632     if(info->palette[i * 4 + 3] < 255) return 1;
   2633   }
   2634   return 0;
   2635 }
   2636 
   2637 unsigned lodepng_can_have_alpha(const LodePNGColorMode* info)
   2638 {
   2639   return info->key_defined
   2640       || lodepng_is_alpha_type(info)
   2641       || lodepng_has_palette_alpha(info);
   2642 }
   2643 
   2644 size_t lodepng_get_raw_size(unsigned w, unsigned h, const LodePNGColorMode* color)
   2645 {
   2646   return (w * h * lodepng_get_bpp(color) + 7) / 8;
   2647 }
   2648 
   2649 size_t lodepng_get_raw_size_lct(unsigned w, unsigned h, LodePNGColorType colortype, unsigned bitdepth)
   2650 {
   2651   return (w * h * lodepng_get_bpp_lct(colortype, bitdepth) + 7) / 8;
   2652 }
   2653 
   2654 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
   2655 
   2656 static void LodePNGUnknownChunks_init(LodePNGInfo* info)
   2657 {
   2658   unsigned i;
   2659   for(i = 0; i < 3; i++) info->unknown_chunks_data[i] = 0;
   2660   for(i = 0; i < 3; i++) info->unknown_chunks_size[i] = 0;
   2661 }
   2662 
   2663 static void LodePNGUnknownChunks_cleanup(LodePNGInfo* info)
   2664 {
   2665   unsigned i;
   2666   for(i = 0; i < 3; i++) lodepng_free(info->unknown_chunks_data[i]);
   2667 }
   2668 
   2669 static unsigned LodePNGUnknownChunks_copy(LodePNGInfo* dest, const LodePNGInfo* src)
   2670 {
   2671   unsigned i;
   2672 
   2673   LodePNGUnknownChunks_cleanup(dest);
   2674 
   2675   for(i = 0; i < 3; i++)
   2676   {
   2677     size_t j;
   2678     dest->unknown_chunks_size[i] = src->unknown_chunks_size[i];
   2679     dest->unknown_chunks_data[i] = (unsigned char*)lodepng_malloc(src->unknown_chunks_size[i]);
   2680     if(!dest->unknown_chunks_data[i] && dest->unknown_chunks_size[i]) return 83; /*alloc fail*/
   2681     for(j = 0; j < src->unknown_chunks_size[i]; j++)
   2682     {
   2683       dest->unknown_chunks_data[i][j] = src->unknown_chunks_data[i][j];
   2684     }
   2685   }
   2686 
   2687   return 0;
   2688 }
   2689 
   2690 /******************************************************************************/
   2691 
   2692 static void LodePNGText_init(LodePNGInfo* info)
   2693 {
   2694   info->text_num = 0;
   2695   info->text_keys = NULL;
   2696   info->text_strings = NULL;
   2697 }
   2698 
   2699 static void LodePNGText_cleanup(LodePNGInfo* info)
   2700 {
   2701   size_t i;
   2702   for(i = 0; i < info->text_num; i++)
   2703   {
   2704     string_cleanup(&info->text_keys[i]);
   2705     string_cleanup(&info->text_strings[i]);
   2706   }
   2707   lodepng_free(info->text_keys);
   2708   lodepng_free(info->text_strings);
   2709 }
   2710 
   2711 static unsigned LodePNGText_copy(LodePNGInfo* dest, const LodePNGInfo* source)
   2712 {
   2713   size_t i = 0;
   2714   dest->text_keys = 0;
   2715   dest->text_strings = 0;
   2716   dest->text_num = 0;
   2717   for(i = 0; i < source->text_num; i++)
   2718   {
   2719     CERROR_TRY_RETURN(lodepng_add_text(dest, source->text_keys[i], source->text_strings[i]));
   2720   }
   2721   return 0;
   2722 }
   2723 
   2724 void lodepng_clear_text(LodePNGInfo* info)
   2725 {
   2726   LodePNGText_cleanup(info);
   2727 }
   2728 
   2729 unsigned lodepng_add_text(LodePNGInfo* info, const char* key, const char* str)
   2730 {
   2731   char** new_keys = (char**)(lodepng_realloc(info->text_keys, sizeof(char*) * (info->text_num + 1)));
   2732   char** new_strings = (char**)(lodepng_realloc(info->text_strings, sizeof(char*) * (info->text_num + 1)));
   2733   if(!new_keys || !new_strings)
   2734   {
   2735     lodepng_free(new_keys);
   2736     lodepng_free(new_strings);
   2737     return 83; /*alloc fail*/
   2738   }
   2739 
   2740   info->text_num++;
   2741   info->text_keys = new_keys;
   2742   info->text_strings = new_strings;
   2743 
   2744   string_init(&info->text_keys[info->text_num - 1]);
   2745   string_set(&info->text_keys[info->text_num - 1], key);
   2746 
   2747   string_init(&info->text_strings[info->text_num - 1]);
   2748   string_set(&info->text_strings[info->text_num - 1], str);
   2749 
   2750   return 0;
   2751 }
   2752 
   2753 /******************************************************************************/
   2754 
   2755 static void LodePNGIText_init(LodePNGInfo* info)
   2756 {
   2757   info->itext_num = 0;
   2758   info->itext_keys = NULL;
   2759   info->itext_langtags = NULL;
   2760   info->itext_transkeys = NULL;
   2761   info->itext_strings = NULL;
   2762 }
   2763 
   2764 static void LodePNGIText_cleanup(LodePNGInfo* info)
   2765 {
   2766   size_t i;
   2767   for(i = 0; i < info->itext_num; i++)
   2768   {
   2769     string_cleanup(&info->itext_keys[i]);
   2770     string_cleanup(&info->itext_langtags[i]);
   2771     string_cleanup(&info->itext_transkeys[i]);
   2772     string_cleanup(&info->itext_strings[i]);
   2773   }
   2774   lodepng_free(info->itext_keys);
   2775   lodepng_free(info->itext_langtags);
   2776   lodepng_free(info->itext_transkeys);
   2777   lodepng_free(info->itext_strings);
   2778 }
   2779 
   2780 static unsigned LodePNGIText_copy(LodePNGInfo* dest, const LodePNGInfo* source)
   2781 {
   2782   size_t i = 0;
   2783   dest->itext_keys = 0;
   2784   dest->itext_langtags = 0;
   2785   dest->itext_transkeys = 0;
   2786   dest->itext_strings = 0;
   2787   dest->itext_num = 0;
   2788   for(i = 0; i < source->itext_num; i++)
   2789   {
   2790     CERROR_TRY_RETURN(lodepng_add_itext(dest, source->itext_keys[i], source->itext_langtags[i],
   2791                                         source->itext_transkeys[i], source->itext_strings[i]));
   2792   }
   2793   return 0;
   2794 }
   2795 
   2796 void lodepng_clear_itext(LodePNGInfo* info)
   2797 {
   2798   LodePNGIText_cleanup(info);
   2799 }
   2800 
   2801 unsigned lodepng_add_itext(LodePNGInfo* info, const char* key, const char* langtag,
   2802                            const char* transkey, const char* str)
   2803 {
   2804   char** new_keys = (char**)(lodepng_realloc(info->itext_keys, sizeof(char*) * (info->itext_num + 1)));
   2805   char** new_langtags = (char**)(lodepng_realloc(info->itext_langtags, sizeof(char*) * (info->itext_num + 1)));
   2806   char** new_transkeys = (char**)(lodepng_realloc(info->itext_transkeys, sizeof(char*) * (info->itext_num + 1)));
   2807   char** new_strings = (char**)(lodepng_realloc(info->itext_strings, sizeof(char*) * (info->itext_num + 1)));
   2808   if(!new_keys || !new_langtags || !new_transkeys || !new_strings)
   2809   {
   2810     lodepng_free(new_keys);
   2811     lodepng_free(new_langtags);
   2812     lodepng_free(new_transkeys);
   2813     lodepng_free(new_strings);
   2814     return 83; /*alloc fail*/
   2815   }
   2816 
   2817   info->itext_num++;
   2818   info->itext_keys = new_keys;
   2819   info->itext_langtags = new_langtags;
   2820   info->itext_transkeys = new_transkeys;
   2821   info->itext_strings = new_strings;
   2822 
   2823   string_init(&info->itext_keys[info->itext_num - 1]);
   2824   string_set(&info->itext_keys[info->itext_num - 1], key);
   2825 
   2826   string_init(&info->itext_langtags[info->itext_num - 1]);
   2827   string_set(&info->itext_langtags[info->itext_num - 1], langtag);
   2828 
   2829   string_init(&info->itext_transkeys[info->itext_num - 1]);
   2830   string_set(&info->itext_transkeys[info->itext_num - 1], transkey);
   2831 
   2832   string_init(&info->itext_strings[info->itext_num - 1]);
   2833   string_set(&info->itext_strings[info->itext_num - 1], str);
   2834 
   2835   return 0;
   2836 }
   2837 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
   2838 
   2839 void lodepng_info_init(LodePNGInfo* info)
   2840 {
   2841   lodepng_color_mode_init(&info->color);
   2842   info->interlace_method = 0;
   2843   info->compression_method = 0;
   2844   info->filter_method = 0;
   2845 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
   2846   info->background_defined = 0;
   2847   info->background_r = info->background_g = info->background_b = 0;
   2848 
   2849   LodePNGText_init(info);
   2850   LodePNGIText_init(info);
   2851 
   2852   info->time_defined = 0;
   2853   info->phys_defined = 0;
   2854 
   2855   LodePNGUnknownChunks_init(info);
   2856 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
   2857 }
   2858 
   2859 void lodepng_info_cleanup(LodePNGInfo* info)
   2860 {
   2861   lodepng_color_mode_cleanup(&info->color);
   2862 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
   2863   LodePNGText_cleanup(info);
   2864   LodePNGIText_cleanup(info);
   2865 
   2866   LodePNGUnknownChunks_cleanup(info);
   2867 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
   2868 }
   2869 
   2870 unsigned lodepng_info_copy(LodePNGInfo* dest, const LodePNGInfo* source)
   2871 {
   2872   lodepng_info_cleanup(dest);
   2873   *dest = *source;
   2874   lodepng_color_mode_init(&dest->color);
   2875   CERROR_TRY_RETURN(lodepng_color_mode_copy(&dest->color, &source->color));
   2876 
   2877 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
   2878   CERROR_TRY_RETURN(LodePNGText_copy(dest, source));
   2879   CERROR_TRY_RETURN(LodePNGIText_copy(dest, source));
   2880 
   2881   LodePNGUnknownChunks_init(dest);
   2882   CERROR_TRY_RETURN(LodePNGUnknownChunks_copy(dest, source));
   2883 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
   2884   return 0;
   2885 }
   2886 
   2887 void lodepng_info_swap(LodePNGInfo* a, LodePNGInfo* b)
   2888 {
   2889   LodePNGInfo temp = *a;
   2890   *a = *b;
   2891   *b = temp;
   2892 }
   2893 
   2894 /* ////////////////////////////////////////////////////////////////////////// */
   2895 
   2896 /*index: bitgroup index, bits: bitgroup size(1, 2 or 4), in: bitgroup value, out: octet array to add bits to*/
   2897 static void addColorBits(unsigned char* out, size_t index, unsigned bits, unsigned in)
   2898 {
   2899   unsigned m = bits == 1 ? 7 : bits == 2 ? 3 : 1; /*8 / bits - 1*/
   2900   /*p = the partial index in the byte, e.g. with 4 palettebits it is 0 for first half or 1 for second half*/
   2901   unsigned p = index & m;
   2902   in &= (1 << bits) - 1; /*filter out any other bits of the input value*/
   2903   in = in << (bits * (m - p));
   2904   if(p == 0) out[index * bits / 8] = in;
   2905   else out[index * bits / 8] |= in;
   2906 }
   2907 
   2908 typedef struct ColorTree ColorTree;
   2909 
   2910 /*
   2911 One node of a color tree
   2912 This is the data structure used to count the number of unique colors and to get a palette
   2913 index for a color. It's like an octree, but because the alpha channel is used too, each
   2914 node has 16 instead of 8 children.
   2915 */
   2916 struct ColorTree
   2917 {
   2918   ColorTree* children[16]; /*up to 16 pointers to ColorTree of next level*/
   2919   int index; /*the payload. Only has a meaningful value if this is in the last level*/
   2920 };
   2921 
   2922 static void color_tree_init(ColorTree* tree)
   2923 {
   2924   int i;
   2925   for(i = 0; i < 16; i++) tree->children[i] = 0;
   2926   tree->index = -1;
   2927 }
   2928 
   2929 static void color_tree_cleanup(ColorTree* tree)
   2930 {
   2931   int i;
   2932   for(i = 0; i < 16; i++)
   2933   {
   2934     if(tree->children[i])
   2935     {
   2936       color_tree_cleanup(tree->children[i]);
   2937       lodepng_free(tree->children[i]);
   2938     }
   2939   }
   2940 }
   2941 
   2942 /*returns -1 if color not present, its index otherwise*/
   2943 static int color_tree_get(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
   2944 {
   2945   int bit = 0;
   2946   for(bit = 0; bit < 8; bit++)
   2947   {
   2948     int i = 8 * ((r >> bit) & 1) + 4 * ((g >> bit) & 1) + 2 * ((b >> bit) & 1) + 1 * ((a >> bit) & 1);
   2949     if(!tree->children[i]) return -1;
   2950     else tree = tree->children[i];
   2951   }
   2952   return tree ? tree->index : -1;
   2953 }
   2954 
   2955 #ifdef LODEPNG_COMPILE_ENCODER
   2956 static int color_tree_has(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
   2957 {
   2958   return color_tree_get(tree, r, g, b, a) >= 0;
   2959 }
   2960 #endif /*LODEPNG_COMPILE_ENCODER*/
   2961 
   2962 /*color is not allowed to already exist.
   2963 Index should be >= 0 (it's signed to be compatible with using -1 for "doesn't exist")*/
   2964 static void color_tree_add(ColorTree* tree,
   2965                            unsigned char r, unsigned char g, unsigned char b, unsigned char a, int index)
   2966 {
   2967   int bit;
   2968   for(bit = 0; bit < 8; bit++)
   2969   {
   2970     int i = 8 * ((r >> bit) & 1) + 4 * ((g >> bit) & 1) + 2 * ((b >> bit) & 1) + 1 * ((a >> bit) & 1);
   2971     if(!tree->children[i])
   2972     {
   2973       tree->children[i] = (ColorTree*)lodepng_malloc(sizeof(ColorTree));
   2974       color_tree_init(tree->children[i]);
   2975     }
   2976     tree = tree->children[i];
   2977   }
   2978   tree->index = index;
   2979 }
   2980 
   2981 /*put a pixel, given its RGBA color, into image of any color type*/
   2982 static unsigned rgba8ToPixel(unsigned char* out, size_t i,
   2983                              const LodePNGColorMode* mode, ColorTree* tree /*for palette*/,
   2984                              unsigned char r, unsigned char g, unsigned char b, unsigned char a)
   2985 {
   2986   if(mode->colortype == LCT_GREY)
   2987   {
   2988     unsigned char grey = r; /*((unsigned short)r + g + b) / 3*/;
   2989     if(mode->bitdepth == 8) out[i] = grey;
   2990     else if(mode->bitdepth == 16) out[i * 2 + 0] = out[i * 2 + 1] = grey;
   2991     else
   2992     {
   2993       /*take the most significant bits of grey*/
   2994       grey = (grey >> (8 - mode->bitdepth)) & ((1 << mode->bitdepth) - 1);
   2995       addColorBits(out, i, mode->bitdepth, grey);
   2996     }
   2997   }
   2998   else if(mode->colortype == LCT_RGB)
   2999   {
   3000     if(mode->bitdepth == 8)
   3001     {
   3002       out[i * 3 + 0] = r;
   3003       out[i * 3 + 1] = g;
   3004       out[i * 3 + 2] = b;
   3005     }
   3006     else
   3007     {
   3008       out[i * 6 + 0] = out[i * 6 + 1] = r;
   3009       out[i * 6 + 2] = out[i * 6 + 3] = g;
   3010       out[i * 6 + 4] = out[i * 6 + 5] = b;
   3011     }
   3012   }
   3013   else if(mode->colortype == LCT_PALETTE)
   3014   {
   3015     int index = color_tree_get(tree, r, g, b, a);
   3016     if(index < 0) return 82; /*color not in palette*/
   3017     if(mode->bitdepth == 8) out[i] = index;
   3018     else addColorBits(out, i, mode->bitdepth, index);
   3019   }
   3020   else if(mode->colortype == LCT_GREY_ALPHA)
   3021   {
   3022     unsigned char grey = r; /*((unsigned short)r + g + b) / 3*/;
   3023     if(mode->bitdepth == 8)
   3024     {
   3025       out[i * 2 + 0] = grey;
   3026       out[i * 2 + 1] = a;
   3027     }
   3028     else if(mode->bitdepth == 16)
   3029     {
   3030       out[i * 4 + 0] = out[i * 4 + 1] = grey;
   3031       out[i * 4 + 2] = out[i * 4 + 3] = a;
   3032     }
   3033   }
   3034   else if(mode->colortype == LCT_RGBA)
   3035   {
   3036     if(mode->bitdepth == 8)
   3037     {
   3038       out[i * 4 + 0] = r;
   3039       out[i * 4 + 1] = g;
   3040       out[i * 4 + 2] = b;
   3041       out[i * 4 + 3] = a;
   3042     }
   3043     else
   3044     {
   3045       out[i * 8 + 0] = out[i * 8 + 1] = r;
   3046       out[i * 8 + 2] = out[i * 8 + 3] = g;
   3047       out[i * 8 + 4] = out[i * 8 + 5] = b;
   3048       out[i * 8 + 6] = out[i * 8 + 7] = a;
   3049     }
   3050   }
   3051 
   3052   return 0; /*no error*/
   3053 }
   3054 
   3055 /*put a pixel, given its RGBA16 color, into image of any color 16-bitdepth type*/
   3056 static unsigned rgba16ToPixel(unsigned char* out, size_t i,
   3057                               const LodePNGColorMode* mode,
   3058                               unsigned short r, unsigned short g, unsigned short b, unsigned short a)
   3059 {
   3060   if(mode->bitdepth != 16) return 85; /*must be 16 for this function*/
   3061   if(mode->colortype == LCT_GREY)
   3062   {
   3063     unsigned short grey = r; /*((unsigned)r + g + b) / 3*/;
   3064     out[i * 2 + 0] = (grey >> 8) & 255;
   3065     out[i * 2 + 1] = grey & 255;
   3066   }
   3067   else if(mode->colortype == LCT_RGB)
   3068   {
   3069     out[i * 6 + 0] = (r >> 8) & 255;
   3070     out[i * 6 + 1] = r & 255;
   3071     out[i * 6 + 2] = (g >> 8) & 255;
   3072     out[i * 6 + 3] = g & 255;
   3073     out[i * 6 + 4] = (b >> 8) & 255;
   3074     out[i * 6 + 5] = b & 255;
   3075   }
   3076   else if(mode->colortype == LCT_GREY_ALPHA)
   3077   {
   3078     unsigned short grey = r; /*((unsigned)r + g + b) / 3*/;
   3079     out[i * 4 + 0] = (grey >> 8) & 255;
   3080     out[i * 4 + 1] = grey & 255;
   3081     out[i * 4 + 2] = (a >> 8) & 255;
   3082     out[i * 4 + 3] = a & 255;
   3083   }
   3084   else if(mode->colortype == LCT_RGBA)
   3085   {
   3086     out[i * 8 + 0] = (r >> 8) & 255;
   3087     out[i * 8 + 1] = r & 255;
   3088     out[i * 8 + 2] = (g >> 8) & 255;
   3089     out[i * 8 + 3] = g & 255;
   3090     out[i * 8 + 4] = (b >> 8) & 255;
   3091     out[i * 8 + 5] = b & 255;
   3092     out[i * 8 + 6] = (a >> 8) & 255;
   3093     out[i * 8 + 7] = a & 255;
   3094   }
   3095 
   3096   return 0; /*no error*/
   3097 }
   3098 
   3099 /*Get RGBA8 color of pixel with index i (y * width + x) from the raw image with given color type.*/
   3100 static unsigned getPixelColorRGBA8(unsigned char* r, unsigned char* g,
   3101                                    unsigned char* b, unsigned char* a,
   3102                                    const unsigned char* in, size_t i,
   3103                                    const LodePNGColorMode* mode,
   3104                                    unsigned fix_png)
   3105 {
   3106   if(mode->colortype == LCT_GREY)
   3107   {
   3108     if(mode->bitdepth == 8)
   3109     {
   3110       *r = *g = *b = in[i];
   3111       if(mode->key_defined && *r == mode->key_r) *a = 0;
   3112       else *a = 255;
   3113     }
   3114     else if(mode->bitdepth == 16)
   3115     {
   3116       *r = *g = *b = in[i * 2 + 0];
   3117       if(mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r) *a = 0;
   3118       else *a = 255;
   3119     }
   3120     else
   3121     {
   3122       unsigned highest = ((1U << mode->bitdepth) - 1U); /*highest possible value for this bit depth*/
   3123       size_t j = i * mode->bitdepth;
   3124       unsigned value = readBitsFromReversedStream(&j, in, mode->bitdepth);
   3125       *r = *g = *b = (value * 255) / highest;
   3126       if(mode->key_defined && value == mode->key_r) *a = 0;
   3127       else *a = 255;
   3128     }
   3129   }
   3130   else if(mode->colortype == LCT_RGB)
   3131   {
   3132     if(mode->bitdepth == 8)
   3133     {
   3134       *r = in[i * 3 + 0]; *g = in[i * 3 + 1]; *b = in[i * 3 + 2];
   3135       if(mode->key_defined && *r == mode->key_r && *g == mode->key_g && *b == mode->key_b) *a = 0;
   3136       else *a = 255;
   3137     }
   3138     else
   3139     {
   3140       *r = in[i * 6 + 0];
   3141       *g = in[i * 6 + 2];
   3142       *b = in[i * 6 + 4];
   3143       if(mode->key_defined && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
   3144          && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
   3145          && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b) *a = 0;
   3146       else *a = 255;
   3147     }
   3148   }
   3149   else if(mode->colortype == LCT_PALETTE)
   3150   {
   3151     unsigned index;
   3152     if(mode->bitdepth == 8) index = in[i];
   3153     else
   3154     {
   3155       size_t j = i * mode->bitdepth;
   3156       index = readBitsFromReversedStream(&j, in, mode->bitdepth);
   3157     }
   3158 
   3159     if(index >= mode->palettesize)
   3160     {
   3161       /*This is an error according to the PNG spec, but fix_png can ignore it*/
   3162       if(!fix_png) return (mode->bitdepth == 8 ? 46 : 47); /*index out of palette*/
   3163       *r = *g = *b = 0;
   3164       *a = 255;
   3165     }
   3166     else
   3167     {
   3168       *r = mode->palette[index * 4 + 0];
   3169       *g = mode->palette[index * 4 + 1];
   3170       *b = mode->palette[index * 4 + 2];
   3171       *a = mode->palette[index * 4 + 3];
   3172     }
   3173   }
   3174   else if(mode->colortype == LCT_GREY_ALPHA)
   3175   {
   3176     if(mode->bitdepth == 8)
   3177     {
   3178       *r = *g = *b = in[i * 2 + 0];
   3179       *a = in[i * 2 + 1];
   3180     }
   3181     else
   3182     {
   3183       *r = *g = *b = in[i * 4 + 0];
   3184       *a = in[i * 4 + 2];
   3185     }
   3186   }
   3187   else if(mode->colortype == LCT_RGBA)
   3188   {
   3189     if(mode->bitdepth == 8)
   3190     {
   3191       *r = in[i * 4 + 0];
   3192       *g = in[i * 4 + 1];
   3193       *b = in[i * 4 + 2];
   3194       *a = in[i * 4 + 3];
   3195     }
   3196     else
   3197     {
   3198       *r = in[i * 8 + 0];
   3199       *g = in[i * 8 + 2];
   3200       *b = in[i * 8 + 4];
   3201       *a = in[i * 8 + 6];
   3202     }
   3203   }
   3204 
   3205   return 0; /*no error*/
   3206 }
   3207 
   3208 /*Similar to getPixelColorRGBA8, but with all the for loops inside of the color
   3209 mode test cases, optimized to convert the colors much faster, when converting
   3210 to RGBA or RGB with 8 bit per cannel. buffer must be RGBA or RGB output with
   3211 enough memory, if has_alpha is true the output is RGBA. mode has the color mode
   3212 of the input buffer.*/
   3213 static unsigned getPixelColorsRGBA8(unsigned char* buffer, size_t numpixels,
   3214                                     unsigned has_alpha, const unsigned char* in,
   3215                                     const LodePNGColorMode* mode,
   3216                                     unsigned fix_png)
   3217 {
   3218   unsigned num_channels = has_alpha ? 4 : 3;
   3219   size_t i;
   3220   if(mode->colortype == LCT_GREY)
   3221   {
   3222     if(mode->bitdepth == 8)
   3223     {
   3224       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3225       {
   3226         buffer[0] = buffer[1] = buffer[2] = in[i];
   3227         if(has_alpha) buffer[3] = mode->key_defined && in[i] == mode->key_r ? 0 : 255;
   3228       }
   3229     }
   3230     else if(mode->bitdepth == 16)
   3231     {
   3232       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3233       {
   3234         buffer[0] = buffer[1] = buffer[2] = in[i * 2];
   3235         if(has_alpha) buffer[3] = mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r ? 0 : 255;
   3236       }
   3237     }
   3238     else
   3239     {
   3240       unsigned highest = ((1U << mode->bitdepth) - 1U); /*highest possible value for this bit depth*/
   3241       size_t j = 0;
   3242       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3243       {
   3244         unsigned value = readBitsFromReversedStream(&j, in, mode->bitdepth);
   3245         buffer[0] = buffer[1] = buffer[2] = (value * 255) / highest;
   3246         if(has_alpha) buffer[3] = mode->key_defined && value == mode->key_r ? 0 : 255;
   3247       }
   3248     }
   3249   }
   3250   else if(mode->colortype == LCT_RGB)
   3251   {
   3252     if(mode->bitdepth == 8)
   3253     {
   3254       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3255       {
   3256         buffer[0] = in[i * 3 + 0];
   3257         buffer[1] = in[i * 3 + 1];
   3258         buffer[2] = in[i * 3 + 2];
   3259         if(has_alpha) buffer[3] = mode->key_defined && buffer[0] == mode->key_r
   3260            && buffer[1]== mode->key_g && buffer[2] == mode->key_b ? 0 : 255;
   3261       }
   3262     }
   3263     else
   3264     {
   3265       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3266       {
   3267         buffer[0] = in[i * 6 + 0];
   3268         buffer[1] = in[i * 6 + 2];
   3269         buffer[2] = in[i * 6 + 4];
   3270         if(has_alpha) buffer[3] = mode->key_defined
   3271            && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
   3272            && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
   3273            && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b ? 0 : 255;
   3274       }
   3275     }
   3276   }
   3277   else if(mode->colortype == LCT_PALETTE)
   3278   {
   3279     unsigned index;
   3280     size_t j = 0;
   3281     for(i = 0; i < numpixels; i++, buffer += num_channels)
   3282     {
   3283       if(mode->bitdepth == 8) index = in[i];
   3284       else index = readBitsFromReversedStream(&j, in, mode->bitdepth);
   3285 
   3286       if(index >= mode->palettesize)
   3287       {
   3288         /*This is an error according to the PNG spec, but fix_png can ignore it*/
   3289         if(!fix_png) return (mode->bitdepth == 8 ? 46 : 47); /*index out of palette*/
   3290         buffer[0] = buffer[1] = buffer[2] = 0;
   3291         if(has_alpha) buffer[3] = 255;
   3292       }
   3293       else
   3294       {
   3295         buffer[0] = mode->palette[index * 4 + 0];
   3296         buffer[1] = mode->palette[index * 4 + 1];
   3297         buffer[2] = mode->palette[index * 4 + 2];
   3298         if(has_alpha) buffer[3] = mode->palette[index * 4 + 3];
   3299       }
   3300     }
   3301   }
   3302   else if(mode->colortype == LCT_GREY_ALPHA)
   3303   {
   3304     if(mode->bitdepth == 8)
   3305     {
   3306       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3307       {
   3308         buffer[0] = buffer[1] = buffer[2] = in[i * 2 + 0];
   3309         if(has_alpha) buffer[3] = in[i * 2 + 1];
   3310       }
   3311     }
   3312     else
   3313     {
   3314       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3315       {
   3316         buffer[0] = buffer[1] = buffer[2] = in[i * 4 + 0];
   3317         if(has_alpha) buffer[3] = in[i * 4 + 2];
   3318       }
   3319     }
   3320   }
   3321   else if(mode->colortype == LCT_RGBA)
   3322   {
   3323     if(mode->bitdepth == 8)
   3324     {
   3325       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3326       {
   3327         buffer[0] = in[i * 4 + 0];
   3328         buffer[1] = in[i * 4 + 1];
   3329         buffer[2] = in[i * 4 + 2];
   3330         if(has_alpha) buffer[3] = in[i * 4 + 3];
   3331       }
   3332     }
   3333     else
   3334     {
   3335       for(i = 0; i < numpixels; i++, buffer += num_channels)
   3336       {
   3337         buffer[0] = in[i * 8 + 0];
   3338         buffer[1] = in[i * 8 + 2];
   3339         buffer[2] = in[i * 8 + 4];
   3340         if(has_alpha) buffer[3] = in[i * 8 + 6];
   3341       }
   3342     }
   3343   }
   3344 
   3345   return 0; /*no error*/
   3346 }
   3347 
   3348 /*Get RGBA16 color of pixel with index i (y * width + x) from the raw image with
   3349 given color type, but the given color type must be 16-bit itself.*/
   3350 static unsigned getPixelColorRGBA16(unsigned short* r, unsigned short* g, unsigned short* b, unsigned short* a,
   3351                                     const unsigned char* in, size_t i, const LodePNGColorMode* mode)
   3352 {
   3353   if(mode->bitdepth != 16) return 85; /*error: this function only supports 16-bit input*/
   3354 
   3355   if(mode->colortype == LCT_GREY)
   3356   {
   3357     *r = *g = *b = 256 * in[i * 2 + 0] + in[i * 2 + 1];
   3358     if(mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r) *a = 0;
   3359     else *a = 65535;
   3360   }
   3361   else if(mode->colortype == LCT_RGB)
   3362   {
   3363     *r = 256 * in[i * 6 + 0] + in[i * 6 + 1];
   3364     *g = 256 * in[i * 6 + 2] + in[i * 6 + 3];
   3365     *b = 256 * in[i * 6 + 4] + in[i * 6 + 5];
   3366     if(mode->key_defined && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
   3367        && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
   3368        && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b) *a = 0;
   3369     else *a = 65535;
   3370   }
   3371   else if(mode->colortype == LCT_GREY_ALPHA)
   3372   {
   3373     *r = *g = *b = 256 * in[i * 4 + 0] + in[i * 4 + 1];
   3374     *a = 256 * in[i * 4 + 2] + in[i * 4 + 3];
   3375   }
   3376   else if(mode->colortype == LCT_RGBA)
   3377   {
   3378     *r = 256 * in[i * 8 + 0] + in[i * 8 + 1];
   3379     *g = 256 * in[i * 8 + 2] + in[i * 8 + 3];
   3380     *b = 256 * in[i * 8 + 4] + in[i * 8 + 5];
   3381     *a = 256 * in[i * 8 + 6] + in[i * 8 + 7];
   3382   }
   3383   else return 85; /*error: this function only supports 16-bit input, not palettes*/
   3384 
   3385   return 0; /*no error*/
   3386 }
   3387 
   3388 /*
   3389 converts from any color type to 24-bit or 32-bit (later maybe more supported). return value = LodePNG error code
   3390 the out buffer must have (w * h * bpp + 7) / 8 bytes, where bpp is the bits per pixel of the output color type
   3391 (lodepng_get_bpp) for < 8 bpp images, there may _not_ be padding bits at the end of scanlines.
   3392 */
   3393 unsigned lodepng_convert(unsigned char* out, const unsigned char* in,
   3394                          LodePNGColorMode* mode_out, const LodePNGColorMode* mode_in,
   3395                          unsigned w, unsigned h, unsigned fix_png)
   3396 {
   3397   unsigned error = 0;
   3398   size_t i;
   3399   ColorTree tree;
   3400   size_t numpixels = w * h;
   3401 
   3402   if(lodepng_color_mode_equal(mode_out, mode_in))
   3403   {
   3404     size_t numbytes = lodepng_get_raw_size(w, h, mode_in);
   3405     for(i = 0; i < numbytes; i++) out[i] = in[i];
   3406     return error;
   3407   }
   3408 
   3409   if(mode_out->colortype == LCT_PALETTE)
   3410   {
   3411     size_t palsize = 1 << mode_out->bitdepth;
   3412     if(mode_out->palettesize < palsize) palsize = mode_out->palettesize;
   3413     color_tree_init(&tree);
   3414     for(i = 0; i < palsize; i++)
   3415     {
   3416       unsigned char* p = &mode_out->palette[i * 4];
   3417       color_tree_add(&tree, p[0], p[1], p[2], p[3], i);
   3418     }
   3419   }
   3420 
   3421   if(mode_in->bitdepth == 16 && mode_out->bitdepth == 16)
   3422   {
   3423     for(i = 0; i < numpixels; i++)
   3424     {
   3425       unsigned short r = 0, g = 0, b = 0, a = 0;
   3426       error = getPixelColorRGBA16(&r, &g, &b, &a, in, i, mode_in);
   3427       if(error) break;
   3428       error = rgba16ToPixel(out, i, mode_out, r, g, b, a);
   3429       if(error) break;
   3430     }
   3431   }
   3432   else if(mode_out->bitdepth == 8 && mode_out->colortype == LCT_RGBA)
   3433   {
   3434     error = getPixelColorsRGBA8(out, numpixels, 1, in, mode_in, fix_png);
   3435   }
   3436   else if(mode_out->bitdepth == 8 && mode_out->colortype == LCT_RGB)
   3437   {
   3438     error = getPixelColorsRGBA8(out, numpixels, 0, in, mode_in, fix_png);
   3439   }
   3440   else
   3441   {
   3442     unsigned char r = 0, g = 0, b = 0, a = 0;
   3443     for(i = 0; i < numpixels; i++)
   3444     {
   3445       error = getPixelColorRGBA8(&r, &g, &b, &a, in, i, mode_in, fix_png);
   3446       if(error) break;
   3447       error = rgba8ToPixel(out, i, mode_out, &tree, r, g, b, a);
   3448       if(error) break;
   3449     }
   3450   }
   3451 
   3452   if(mode_out->colortype == LCT_PALETTE)
   3453   {
   3454     color_tree_cleanup(&tree);
   3455   }
   3456 
   3457   return error;
   3458 }
   3459 
   3460 #ifdef LODEPNG_COMPILE_ENCODER
   3461 
   3462 typedef struct ColorProfile
   3463 {
   3464   unsigned char sixteenbit; /*needs more than 8 bits per channel*/
   3465   unsigned char sixteenbit_done;
   3466 
   3467 
   3468   unsigned char colored; /*not greyscale*/
   3469   unsigned char colored_done;
   3470 
   3471   unsigned char key; /*a color key is required, or more*/
   3472   unsigned short key_r; /*these values are always in 16-bit bitdepth in the profile*/
   3473   unsigned short key_g;
   3474   unsigned short key_b;
   3475   unsigned char alpha; /*alpha channel, or alpha palette, required*/
   3476   unsigned char alpha_done;
   3477 
   3478   unsigned numcolors;
   3479   ColorTree tree; /*for listing the counted colors, up to 256*/
   3480   unsigned char* palette; /*size 1024. Remember up to the first 256 RGBA colors*/
   3481   unsigned maxnumcolors; /*if more than that amount counted*/
   3482   unsigned char numcolors_done;
   3483 
   3484   unsigned greybits; /*amount of bits required for greyscale (1, 2, 4, 8). Does not take 16 bit into account.*/
   3485   unsigned char greybits_done;
   3486 
   3487 } ColorProfile;
   3488 
   3489 static void color_profile_init(ColorProfile* profile, const LodePNGColorMode* mode)
   3490 {
   3491   profile->sixteenbit = 0;
   3492   profile->sixteenbit_done = mode->bitdepth == 16 ? 0 : 1;
   3493 
   3494   profile->colored = 0;
   3495   profile->colored_done = lodepng_is_greyscale_type(mode) ? 1 : 0;
   3496 
   3497   profile->key = 0;
   3498   profile->alpha = 0;
   3499   profile->alpha_done = lodepng_can_have_alpha(mode) ? 0 : 1;
   3500 
   3501   profile->numcolors = 0;
   3502   color_tree_init(&profile->tree);
   3503   profile->palette = (unsigned char*)lodepng_malloc(1024);
   3504   profile->maxnumcolors = 257;
   3505   if(lodepng_get_bpp(mode) <= 8)
   3506   {
   3507     int bpp = lodepng_get_bpp(mode);
   3508     profile->maxnumcolors = bpp == 1 ? 2 : (bpp == 2 ? 4 : (bpp == 4 ? 16 : 256));
   3509   }
   3510   profile->numcolors_done = 0;
   3511 
   3512   profile->greybits = 1;
   3513   profile->greybits_done = lodepng_get_bpp(mode) == 1 ? 1 : 0;
   3514 }
   3515 
   3516 static void color_profile_cleanup(ColorProfile* profile)
   3517 {
   3518   color_tree_cleanup(&profile->tree);
   3519   lodepng_free(profile->palette);
   3520 }
   3521 
   3522 /*function used for debug purposes with C++*/
   3523 /*void printColorProfile(ColorProfile* p)
   3524 {
   3525   std::cout << "sixteenbit: " << (int)p->sixteenbit << std::endl;
   3526   std::cout << "sixteenbit_done: " << (int)p->sixteenbit_done << std::endl;
   3527   std::cout << "colored: " << (int)p->colored << std::endl;
   3528   std::cout << "colored_done: " << (int)p->colored_done << std::endl;
   3529   std::cout << "key: " << (int)p->key << std::endl;
   3530   std::cout << "key_r: " << (int)p->key_r << std::endl;
   3531   std::cout << "key_g: " << (int)p->key_g << std::endl;
   3532   std::cout << "key_b: " << (int)p->key_b << std::endl;
   3533   std::cout << "alpha: " << (int)p->alpha << std::endl;
   3534   std::cout << "alpha_done: " << (int)p->alpha_done << std::endl;
   3535   std::cout << "numcolors: " << (int)p->numcolors << std::endl;
   3536   std::cout << "maxnumcolors: " << (int)p->maxnumcolors << std::endl;
   3537   std::cout << "numcolors_done: " << (int)p->numcolors_done << std::endl;
   3538   std::cout << "greybits: " << (int)p->greybits << std::endl;
   3539   std::cout << "greybits_done: " << (int)p->greybits_done << std::endl;
   3540 }*/
   3541 
   3542 /*Returns how many bits needed to represent given value (max 8 bit)*/
   3543 unsigned getValueRequiredBits(unsigned short value)
   3544 {
   3545   if(value == 0 || value == 255) return 1;
   3546   /*The scaling of 2-bit and 4-bit values uses multiples of 85 and 17*/
   3547   if(value % 17 == 0) return value % 85 == 0 ? 2 : 4;
   3548   return 8;
   3549 }
   3550 
   3551 /*profile must already have been inited with mode.
   3552 It's ok to set some parameters of profile to done already.*/
   3553 static unsigned get_color_profile(ColorProfile* profile,
   3554                                   const unsigned char* in,
   3555                                   size_t numpixels /*must be full image size, for certain filesize based choices*/,
   3556                                   const LodePNGColorMode* mode,
   3557                                   unsigned fix_png)
   3558 {
   3559   unsigned error = 0;
   3560   size_t i;
   3561 
   3562   if(mode->bitdepth == 16)
   3563   {
   3564     for(i = 0; i < numpixels; i++)
   3565     {
   3566       unsigned short r, g, b, a;
   3567       error = getPixelColorRGBA16(&r, &g, &b, &a, in, i, mode);
   3568       if(error) break;
   3569 
   3570       /*a color is considered good for 8-bit if the first byte and the second byte are equal,
   3571         (so if it's divisible through 257), NOT necessarily if the second byte is 0*/
   3572       if(!profile->sixteenbit_done
   3573           && (((r & 255) != ((r >> 8) & 255))
   3574            || ((g & 255) != ((g >> 8) & 255))
   3575            || ((b & 255) != ((b >> 8) & 255))))
   3576       {
   3577         profile->sixteenbit = 1;
   3578         profile->sixteenbit_done = 1;
   3579         profile->greybits_done = 1; /*greybits is not applicable anymore at 16-bit*/
   3580         profile->numcolors_done = 1; /*counting colors no longer useful, palette doesn't support 16-bit*/
   3581       }
   3582 
   3583       if(!profile->colored_done && (r != g || r != b))
   3584       {
   3585         profile->colored = 1;
   3586         profile->colored_done = 1;
   3587         profile->greybits_done = 1; /*greybits is not applicable anymore*/
   3588       }
   3589 
   3590       if(!profile->alpha_done && a != 65535)
   3591       {
   3592         /*only use color key if numpixels large enough to justify tRNS chunk size*/
   3593         if(a == 0 && numpixels > 16 && !(profile->key && (r != profile->key_r || g != profile->key_g || b != profile->key_b)))
   3594         {
   3595           if(!profile->alpha && !profile->key)
   3596           {
   3597             profile->key = 1;
   3598             profile->key_r = r;
   3599             profile->key_g = g;
   3600             profile->key_b = b;
   3601           }
   3602         }
   3603         else
   3604         {
   3605           profile->alpha = 1;
   3606           profile->alpha_done = 1;
   3607           profile->greybits_done = 1; /*greybits is not applicable anymore*/
   3608         }
   3609       }
   3610 
   3611       /* Color key cannot be used if an opaque pixel also has that RGB color. */
   3612       if(!profile->alpha_done && a == 65535 && profile->key
   3613           && r == profile->key_r && g == profile->key_g && b == profile->key_b)
   3614       {
   3615           profile->alpha = 1;
   3616           profile->alpha_done = 1;
   3617           profile->greybits_done = 1; /*greybits is not applicable anymore*/
   3618       }
   3619 
   3620       if(!profile->greybits_done)
   3621       {
   3622         /*assuming 8-bit r, this test does not care about 16-bit*/
   3623         unsigned bits = getValueRequiredBits(r);
   3624         if(bits > profile->greybits) profile->greybits = bits;
   3625         if(profile->greybits >= 8) profile->greybits_done = 1;
   3626       }
   3627 
   3628       if(!profile->numcolors_done)
   3629       {
   3630         /*assuming 8-bit rgba, this test does not care about 16-bit*/
   3631         if(!color_tree_has(&profile->tree, (unsigned char)r, (unsigned char)g, (unsigned char)b, (unsigned char)a))
   3632         {
   3633           color_tree_add(&profile->tree, (unsigned char)r, (unsigned char)g, (unsigned char)b, (unsigned char)a,
   3634             profile->numcolors);
   3635           if(profile->numcolors < 256)
   3636           {
   3637             unsigned char* p = profile->palette;
   3638             unsigned i = profile->numcolors;
   3639             p[i * 4 + 0] = (unsigned char)r;
   3640             p[i * 4 + 1] = (unsigned char)g;
   3641             p[i * 4 + 2] = (unsigned char)b;
   3642             p[i * 4 + 3] = (unsigned char)a;
   3643           }
   3644           profile->numcolors++;
   3645           if(profile->numcolors >= profile->maxnumcolors) profile->numcolors_done = 1;
   3646         }
   3647       }
   3648 
   3649       if(profile->alpha_done && profile->numcolors_done
   3650       && profile->colored_done && profile->sixteenbit_done && profile->greybits_done)
   3651       {
   3652         break;
   3653       }
   3654     };
   3655   }
   3656   else /* < 16-bit */
   3657   {
   3658     for(i = 0; i < numpixels; i++)
   3659     {
   3660       unsigned char r = 0, g = 0, b = 0, a = 0;
   3661       error = getPixelColorRGBA8(&r, &g, &b, &a, in, i, mode, fix_png);
   3662       if(error) break;
   3663 
   3664       if(!profile->colored_done && (r != g || r != b))
   3665       {
   3666         profile->colored = 1;
   3667         profile->colored_done = 1;
   3668         profile->greybits_done = 1; /*greybits is not applicable anymore*/
   3669       }
   3670 
   3671       if(!profile->alpha_done && a != 255)
   3672       {
   3673         if(a == 0 && !(profile->key && (r != profile->key_r || g != profile->key_g || b != profile->key_b)))
   3674         {
   3675           if(!profile->key)
   3676           {
   3677             profile->key = 1;
   3678             profile->key_r = r;
   3679             profile->key_g = g;
   3680             profile->key_b = b;
   3681           }
   3682         }
   3683         else
   3684         {
   3685           profile->alpha = 1;
   3686           profile->alpha_done = 1;
   3687           profile->greybits_done = 1; /*greybits is not applicable anymore*/
   3688         }
   3689       }
   3690 
   3691       /* Color key cannot be used if an opaque pixel also has that RGB color. */
   3692       if(!profile->alpha_done && a == 255 && profile->key
   3693           && r == profile->key_r && g == profile->key_g && b == profile->key_b)
   3694       {
   3695           profile->alpha = 1;
   3696           profile->alpha_done = 1;
   3697           profile->greybits_done = 1; /*greybits is not applicable anymore*/
   3698       }
   3699 
   3700       if(!profile->greybits_done)
   3701       {
   3702         unsigned bits = getValueRequiredBits(r);
   3703         if(bits > profile->greybits) profile->greybits = bits;
   3704         if(profile->greybits >= 8) profile->greybits_done = 1;
   3705       }
   3706 
   3707       if(!profile->numcolors_done)
   3708       {
   3709         if(!color_tree_has(&profile->tree, r, g, b, a))
   3710         {
   3711 
   3712           color_tree_add(&profile->tree, r, g, b, a, profile->numcolors);
   3713           if(profile->numcolors < 256)
   3714           {
   3715             unsigned char* p = profile->palette;
   3716             unsigned i = profile->numcolors;
   3717             p[i * 4 + 0] = r;
   3718             p[i * 4 + 1] = g;
   3719             p[i * 4 + 2] = b;
   3720             p[i * 4 + 3] = a;
   3721           }
   3722           profile->numcolors++;
   3723           if(profile->numcolors >= profile->maxnumcolors) profile->numcolors_done = 1;
   3724         }
   3725       }
   3726 
   3727       if(profile->alpha_done && profile->numcolors_done && profile->colored_done && profile->greybits_done)
   3728       {
   3729         break;
   3730       }
   3731     };
   3732   }
   3733 
   3734   /*make the profile's key always 16-bit for consistency*/
   3735   if(mode->bitdepth < 16)
   3736   {
   3737     /*repeat each byte twice*/
   3738     profile->key_r *= 257;
   3739     profile->key_g *= 257;
   3740     profile->key_b *= 257;
   3741   }
   3742 
   3743   return error;
   3744 }
   3745 
   3746 static void setColorKeyFrom16bit(LodePNGColorMode* mode_out, unsigned r, unsigned g, unsigned b, unsigned bitdepth)
   3747 {
   3748   unsigned mask = (1 << bitdepth) - 1;
   3749   mode_out->key_defined = 1;
   3750   mode_out->key_r = r & mask;
   3751   mode_out->key_g = g & mask;
   3752   mode_out->key_b = b & mask;
   3753 }
   3754 
   3755 /*updates values of mode with a potentially smaller color model. mode_out should
   3756 contain the user chosen color model, but will be overwritten with the new chosen one.*/
   3757 unsigned lodepng_auto_choose_color(LodePNGColorMode* mode_out,
   3758                                    const unsigned char* image, unsigned w, unsigned h,
   3759                                    const LodePNGColorMode* mode_in,
   3760                                    LodePNGAutoConvert auto_convert)
   3761 {
   3762   ColorProfile profile;
   3763   unsigned error = 0;
   3764   int no_nibbles = auto_convert == LAC_AUTO_NO_NIBBLES || auto_convert == LAC_AUTO_NO_NIBBLES_NO_PALETTE;
   3765   int no_palette = auto_convert == LAC_AUTO_NO_PALETTE || auto_convert == LAC_AUTO_NO_NIBBLES_NO_PALETTE;
   3766 
   3767   if(auto_convert == LAC_ALPHA)
   3768   {
   3769     if(mode_out->colortype != LCT_RGBA && mode_out->colortype != LCT_GREY_ALPHA) return 0;
   3770   }
   3771 
   3772   color_profile_init(&profile, mode_in);
   3773   if(auto_convert == LAC_ALPHA)
   3774   {
   3775     profile.colored_done = 1;
   3776     profile.greybits_done = 1;
   3777     profile.numcolors_done = 1;
   3778     profile.sixteenbit_done = 1;
   3779   }
   3780   error = get_color_profile(&profile, image, w * h, mode_in, 0 /*fix_png*/);
   3781   if(!error && auto_convert == LAC_ALPHA)
   3782   {
   3783     if(!profile.alpha)
   3784     {
   3785       mode_out->colortype = (mode_out->colortype == LCT_RGBA ? LCT_RGB : LCT_GREY);
   3786       if(profile.key) setColorKeyFrom16bit(mode_out, profile.key_r, profile.key_g, profile.key_b, mode_out->bitdepth);
   3787     }
   3788   }
   3789   else if(!error && auto_convert != LAC_ALPHA)
   3790   {
   3791     mode_out->key_defined = 0;
   3792 
   3793     if(profile.sixteenbit)
   3794     {
   3795       mode_out->bitdepth = 16;
   3796       if(profile.alpha)
   3797       {
   3798         mode_out->colortype = profile.colored ? LCT_RGBA : LCT_GREY_ALPHA;
   3799       }
   3800       else
   3801       {
   3802         mode_out->colortype = profile.colored ? LCT_RGB : LCT_GREY;
   3803         if(profile.key) setColorKeyFrom16bit(mode_out, profile.key_r, profile.key_g, profile.key_b, mode_out->bitdepth);
   3804       }
   3805     }
   3806     else /*less than 16 bits per channel*/
   3807     {
   3808       /*don't add palette overhead if image hasn't got a lot of pixels*/
   3809       unsigned n = profile.numcolors;
   3810       int palette_ok = !no_palette && n <= 256 && (n * 2 < w * h);
   3811       unsigned palettebits = n <= 2 ? 1 : (n <= 4 ? 2 : (n <= 16 ? 4 : 8));
   3812       int grey_ok = !profile.colored && !profile.alpha; /*grey without alpha, with potentially low bits*/
   3813       if(palette_ok || grey_ok)
   3814       {
   3815         if(!palette_ok || (grey_ok && profile.greybits <= palettebits))
   3816         {
   3817           unsigned grey = profile.key_r;
   3818           mode_out->colortype = LCT_GREY;
   3819           mode_out->bitdepth = profile.greybits;
   3820           if(profile.key) setColorKeyFrom16bit(mode_out, grey, grey, grey, mode_out->bitdepth);
   3821         }
   3822         else
   3823         {
   3824           /*fill in the palette*/
   3825           unsigned i;
   3826           unsigned char* p = profile.palette;
   3827           /*remove potential earlier palette*/
   3828           lodepng_palette_clear(mode_out);
   3829           for(i = 0; i < profile.numcolors; i++)
   3830           {
   3831             error = lodepng_palette_add(mode_out, p[i * 4 + 0], p[i * 4 + 1], p[i * 4 + 2], p[i * 4 + 3]);
   3832             if(error) break;
   3833           }
   3834 
   3835           mode_out->colortype = LCT_PALETTE;
   3836           mode_out->bitdepth = palettebits;
   3837         }
   3838       }
   3839       else /*8-bit per channel*/
   3840       {
   3841         mode_out->bitdepth = 8;
   3842         if(profile.alpha)
   3843         {
   3844           mode_out->colortype = profile.colored ? LCT_RGBA : LCT_GREY_ALPHA;
   3845         }
   3846         else
   3847         {
   3848           mode_out->colortype = profile.colored ? LCT_RGB : LCT_GREY /*LCT_GREY normally won't occur, already done earlier*/;
   3849           if(profile.key) setColorKeyFrom16bit(mode_out, profile.key_r, profile.key_g, profile.key_b, mode_out->bitdepth);
   3850         }
   3851       }
   3852     }
   3853   }
   3854 
   3855   color_profile_cleanup(&profile);
   3856 
   3857   if(mode_out->colortype == LCT_PALETTE && mode_in->palettesize == mode_out->palettesize)
   3858   {
   3859     /*In this case keep the palette order of the input, so that the user can choose an optimal one*/
   3860     size_t i;
   3861     for(i = 0; i < mode_in->palettesize * 4; i++)
   3862     {
   3863       mode_out->palette[i] = mode_in->palette[i];
   3864     }
   3865   }
   3866 
   3867   if(no_nibbles && mode_out->bitdepth < 8)
   3868   {
   3869     /*palette can keep its small amount of colors, as long as no indices use it*/
   3870     mode_out->bitdepth = 8;
   3871   }
   3872 
   3873   return error;
   3874 }
   3875 
   3876 #endif /* #ifdef LODEPNG_COMPILE_ENCODER */
   3877 
   3878 /*
   3879 Paeth predicter, used by PNG filter type 4
   3880 The parameters are of type short, but should come from unsigned chars, the shorts
   3881 are only needed to make the paeth calculation correct.
   3882 */
   3883 static unsigned char paethPredictor(short a, short b, short c)
   3884 {
   3885   short pa = abs(b - c);
   3886   short pb = abs(a - c);
   3887   short pc = abs(a + b - c - c);
   3888 
   3889   if(pc < pa && pc < pb) return (unsigned char)c;
   3890   else if(pb < pa) return (unsigned char)b;
   3891   else return (unsigned char)a;
   3892 }
   3893 
   3894 /*shared values used by multiple Adam7 related functions*/
   3895 
   3896 static const unsigned ADAM7_IX[7] = { 0, 4, 0, 2, 0, 1, 0 }; /*x start values*/
   3897 static const unsigned ADAM7_IY[7] = { 0, 0, 4, 0, 2, 0, 1 }; /*y start values*/
   3898 static const unsigned ADAM7_DX[7] = { 8, 8, 4, 4, 2, 2, 1 }; /*x delta values*/
   3899 static const unsigned ADAM7_DY[7] = { 8, 8, 8, 4, 4, 2, 2 }; /*y delta values*/
   3900 
   3901 /*
   3902 Outputs various dimensions and positions in the image related to the Adam7 reduced images.
   3903 passw: output containing the width of the 7 passes
   3904 passh: output containing the height of the 7 passes
   3905 filter_passstart: output containing the index of the start and end of each
   3906  reduced image with filter bytes
   3907 padded_passstart output containing the index of the start and end of each
   3908  reduced image when without filter bytes but with padded scanlines
   3909 passstart: output containing the index of the start and end of each reduced
   3910  image without padding between scanlines, but still padding between the images
   3911 w, h: width and height of non-interlaced image
   3912 bpp: bits per pixel
   3913 "padded" is only relevant if bpp is less than 8 and a scanline or image does not
   3914  end at a full byte
   3915 */
   3916 static void Adam7_getpassvalues(unsigned passw[7], unsigned passh[7], size_t filter_passstart[8],
   3917                                 size_t padded_passstart[8], size_t passstart[8], unsigned w, unsigned h, unsigned bpp)
   3918 {
   3919   /*the passstart values have 8 values: the 8th one indicates the byte after the end of the 7th (= last) pass*/
   3920   unsigned i;
   3921 
   3922   /*calculate width and height in pixels of each pass*/
   3923   for(i = 0; i < 7; i++)
   3924   {
   3925     passw[i] = (w + ADAM7_DX[i] - ADAM7_IX[i] - 1) / ADAM7_DX[i];
   3926     passh[i] = (h + ADAM7_DY[i] - ADAM7_IY[i] - 1) / ADAM7_DY[i];
   3927     if(passw[i] == 0) passh[i] = 0;
   3928     if(passh[i] == 0) passw[i] = 0;
   3929   }
   3930 
   3931   filter_passstart[0] = padded_passstart[0] = passstart[0] = 0;
   3932   for(i = 0; i < 7; i++)
   3933   {
   3934     /*if passw[i] is 0, it's 0 bytes, not 1 (no filtertype-byte)*/
   3935     filter_passstart[i + 1] = filter_passstart[i]
   3936                             + ((passw[i] && passh[i]) ? passh[i] * (1 + (passw[i] * bpp + 7) / 8) : 0);
   3937     /*bits padded if needed to fill full byte at end of each scanline*/
   3938     padded_passstart[i + 1] = padded_passstart[i] + passh[i] * ((passw[i] * bpp + 7) / 8);
   3939     /*only padded at end of reduced image*/
   3940     passstart[i + 1] = passstart[i] + (passh[i] * passw[i] * bpp + 7) / 8;
   3941   }
   3942 }
   3943 
   3944 #ifdef LODEPNG_COMPILE_DECODER
   3945 
   3946 /* ////////////////////////////////////////////////////////////////////////// */
   3947 /* / PNG Decoder                                                            / */
   3948 /* ////////////////////////////////////////////////////////////////////////// */
   3949 
   3950 /*read the information from the header and store it in the LodePNGInfo. return value is error*/
   3951 unsigned lodepng_inspect(unsigned* w, unsigned* h, LodePNGState* state,
   3952                          const unsigned char* in, size_t insize)
   3953 {
   3954   LodePNGInfo* info = &state->info_png;
   3955   if(insize == 0 || in == 0)
   3956   {
   3957     CERROR_RETURN_ERROR(state->error, 48); /*error: the given data is empty*/
   3958   }
   3959   if(insize < 29)
   3960   {
   3961     CERROR_RETURN_ERROR(state->error, 27); /*error: the data length is smaller than the length of a PNG header*/
   3962   }
   3963 
   3964   /*when decoding a new PNG image, make sure all parameters created after previous decoding are reset*/
   3965   lodepng_info_cleanup(info);
   3966   lodepng_info_init(info);
   3967 
   3968   if(in[0] != 137 || in[1] != 80 || in[2] != 78 || in[3] != 71
   3969      || in[4] != 13 || in[5] != 10 || in[6] != 26 || in[7] != 10)
   3970   {
   3971     CERROR_RETURN_ERROR(state->error, 28); /*error: the first 8 bytes are not the correct PNG signature*/
   3972   }
   3973   if(in[12] != 'I' || in[13] != 'H' || in[14] != 'D' || in[15] != 'R')
   3974   {
   3975     CERROR_RETURN_ERROR(state->error, 29); /*error: it doesn't start with a IHDR chunk!*/
   3976   }
   3977 
   3978   /*read the values given in the header*/
   3979   *w = lodepng_read32bitInt(&in[16]);
   3980   *h = lodepng_read32bitInt(&in[20]);
   3981   info->color.bitdepth = in[24];
   3982   info->color.colortype = (LodePNGColorType)in[25];
   3983   info->compression_method = in[26];
   3984   info->filter_method = in[27];
   3985   info->interlace_method = in[28];
   3986 
   3987   if(!state->decoder.ignore_crc)
   3988   {
   3989     unsigned CRC = lodepng_read32bitInt(&in[29]);
   3990     unsigned checksum = lodepng_crc32(&in[12], 17);
   3991     if(CRC != checksum)
   3992     {
   3993       CERROR_RETURN_ERROR(state->error, 57); /*invalid CRC*/
   3994     }
   3995   }
   3996 
   3997   /*error: only compression method 0 is allowed in the specification*/
   3998   if(info->compression_method != 0) CERROR_RETURN_ERROR(state->error, 32);
   3999   /*error: only filter method 0 is allowed in the specification*/
   4000   if(info->filter_method != 0) CERROR_RETURN_ERROR(state->error, 33);
   4001   /*error: only interlace methods 0 and 1 exist in the specification*/
   4002   if(info->interlace_method > 1) CERROR_RETURN_ERROR(state->error, 34);
   4003 
   4004   state->error = checkColorValidity(info->color.colortype, info->color.bitdepth);
   4005   return state->error;
   4006 }
   4007 
   4008 static unsigned unfilterScanline(unsigned char* recon, const unsigned char* scanline, const unsigned char* precon,
   4009                                  size_t bytewidth, unsigned char filterType, size_t length)
   4010 {
   4011   /*
   4012   For PNG filter method 0
   4013   unfilter a PNG image scanline by scanline. when the pixels are smaller than 1 byte,
   4014   the filter works byte per byte (bytewidth = 1)
   4015   precon is the previous unfiltered scanline, recon the result, scanline the current one
   4016   the incoming scanlines do NOT include the filtertype byte, that one is given in the parameter filterType instead
   4017   recon and scanline MAY be the same memory address! precon must be disjoint.
   4018   */
   4019 
   4020   size_t i;
   4021   switch(filterType)
   4022   {
   4023     case 0:
   4024       for(i = 0; i < length; i++) recon[i] = scanline[i];
   4025       break;
   4026     case 1:
   4027       for(i = 0; i < bytewidth; i++) recon[i] = scanline[i];
   4028       for(i = bytewidth; i < length; i++) recon[i] = scanline[i] + recon[i - bytewidth];
   4029       break;
   4030     case 2:
   4031       if(precon)
   4032       {
   4033         for(i = 0; i < length; i++) recon[i] = scanline[i] + precon[i];
   4034       }
   4035       else
   4036       {
   4037         for(i = 0; i < length; i++) recon[i] = scanline[i];
   4038       }
   4039       break;
   4040     case 3:
   4041       if(precon)
   4042       {
   4043         for(i = 0; i < bytewidth; i++) recon[i] = scanline[i] + precon[i] / 2;
   4044         for(i = bytewidth; i < length; i++) recon[i] = scanline[i] + ((recon[i - bytewidth] + precon[i]) / 2);
   4045       }
   4046       else
   4047       {
   4048         for(i = 0; i < bytewidth; i++) recon[i] = scanline[i];
   4049         for(i = bytewidth; i < length; i++) recon[i] = scanline[i] + recon[i - bytewidth] / 2;
   4050       }
   4051       break;
   4052     case 4:
   4053       if(precon)
   4054       {
   4055         for(i = 0; i < bytewidth; i++)
   4056         {
   4057           recon[i] = (scanline[i] + precon[i]); /*paethPredictor(0, precon[i], 0) is always precon[i]*/
   4058         }
   4059         for(i = bytewidth; i < length; i++)
   4060         {
   4061           recon[i] = (scanline[i] + paethPredictor(recon[i - bytewidth], precon[i], precon[i - bytewidth]));
   4062         }
   4063       }
   4064       else
   4065       {
   4066         for(i = 0; i < bytewidth; i++)
   4067         {
   4068           recon[i] = scanline[i];
   4069         }
   4070         for(i = bytewidth; i < length; i++)
   4071         {
   4072           /*paethPredictor(recon[i - bytewidth], 0, 0) is always recon[i - bytewidth]*/
   4073           recon[i] = (scanline[i] + recon[i - bytewidth]);
   4074         }
   4075       }
   4076       break;
   4077     default: return 36; /*error: unexisting filter type given*/
   4078   }
   4079   return 0;
   4080 }
   4081 
   4082 static unsigned unfilter(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
   4083 {
   4084   /*
   4085   For PNG filter method 0
   4086   this function unfilters a single image (e.g. without interlacing this is called once, with Adam7 seven times)
   4087   out must have enough bytes allocated already, in must have the scanlines + 1 filtertype byte per scanline
   4088   w and h are image dimensions or dimensions of reduced image, bpp is bits per pixel
   4089   in and out are allowed to be the same memory address (but aren't the same size since in has the extra filter bytes)
   4090   */
   4091 
   4092   unsigned y;
   4093   unsigned char* prevline = 0;
   4094 
   4095   /*bytewidth is used for filtering, is 1 when bpp < 8, number of bytes per pixel otherwise*/
   4096   size_t bytewidth = (bpp + 7) / 8;
   4097   size_t linebytes = (w * bpp + 7) / 8;
   4098 
   4099   for(y = 0; y < h; y++)
   4100   {
   4101     size_t outindex = linebytes * y;
   4102     size_t inindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
   4103     unsigned char filterType = in[inindex];
   4104 
   4105     CERROR_TRY_RETURN(unfilterScanline(&out[outindex], &in[inindex + 1], prevline, bytewidth, filterType, linebytes));
   4106 
   4107     prevline = &out[outindex];
   4108   }
   4109 
   4110   return 0;
   4111 }
   4112 
   4113 /*
   4114 in: Adam7 interlaced image, with no padding bits between scanlines, but between
   4115  reduced images so that each reduced image starts at a byte.
   4116 out: the same pixels, but re-ordered so that they're now a non-interlaced image with size w*h
   4117 bpp: bits per pixel
   4118 out has the following size in bits: w * h * bpp.
   4119 in is possibly bigger due to padding bits between reduced images.
   4120 out must be big enough AND must be 0 everywhere if bpp < 8 in the current implementation
   4121 (because that's likely a little bit faster)
   4122 NOTE: comments about padding bits are only relevant if bpp < 8
   4123 */
   4124 static void Adam7_deinterlace(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
   4125 {
   4126   unsigned passw[7], passh[7];
   4127   size_t filter_passstart[8], padded_passstart[8], passstart[8];
   4128   unsigned i;
   4129 
   4130   Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
   4131 
   4132   if(bpp >= 8)
   4133   {
   4134     for(i = 0; i < 7; i++)
   4135     {
   4136       unsigned x, y, b;
   4137       size_t bytewidth = bpp / 8;
   4138       for(y = 0; y < passh[i]; y++)
   4139       for(x = 0; x < passw[i]; x++)
   4140       {
   4141         size_t pixelinstart = passstart[i] + (y * passw[i] + x) * bytewidth;
   4142         size_t pixeloutstart = ((ADAM7_IY[i] + y * ADAM7_DY[i]) * w + ADAM7_IX[i] + x * ADAM7_DX[i]) * bytewidth;
   4143         for(b = 0; b < bytewidth; b++)
   4144         {
   4145           out[pixeloutstart + b] = in[pixelinstart + b];
   4146         }
   4147       }
   4148     }
   4149   }
   4150   else /*bpp < 8: Adam7 with pixels < 8 bit is a bit trickier: with bit pointers*/
   4151   {
   4152     for(i = 0; i < 7; i++)
   4153     {
   4154       unsigned x, y, b;
   4155       unsigned ilinebits = bpp * passw[i];
   4156       unsigned olinebits = bpp * w;
   4157       size_t obp, ibp; /*bit pointers (for out and in buffer)*/
   4158       for(y = 0; y < passh[i]; y++)
   4159       for(x = 0; x < passw[i]; x++)
   4160       {
   4161         ibp = (8 * passstart[i]) + (y * ilinebits + x * bpp);
   4162         obp = (ADAM7_IY[i] + y * ADAM7_DY[i]) * olinebits + (ADAM7_IX[i] + x * ADAM7_DX[i]) * bpp;
   4163         for(b = 0; b < bpp; b++)
   4164         {
   4165           unsigned char bit = readBitFromReversedStream(&ibp, in);
   4166           /*note that this function assumes the out buffer is completely 0, use setBitOfReversedStream otherwise*/
   4167           setBitOfReversedStream0(&obp, out, bit);
   4168         }
   4169       }
   4170     }
   4171   }
   4172 }
   4173 
   4174 static void removePaddingBits(unsigned char* out, const unsigned char* in,
   4175                               size_t olinebits, size_t ilinebits, unsigned h)
   4176 {
   4177   /*
   4178   After filtering there are still padding bits if scanlines have non multiple of 8 bit amounts. They need
   4179   to be removed (except at last scanline of (Adam7-reduced) image) before working with pure image buffers
   4180   for the Adam7 code, the color convert code and the output to the user.
   4181   in and out are allowed to be the same buffer, in may also be higher but still overlapping; in must
   4182   have >= ilinebits*h bits, out must have >= olinebits*h bits, olinebits must be <= ilinebits
   4183   also used to move bits after earlier such operations happened, e.g. in a sequence of reduced images from Adam7
   4184   only useful if (ilinebits - olinebits) is a value in the range 1..7
   4185   */
   4186   unsigned y;
   4187   size_t diff = ilinebits - olinebits;
   4188   size_t ibp = 0, obp = 0; /*input and output bit pointers*/
   4189   for(y = 0; y < h; y++)
   4190   {
   4191     size_t x;
   4192     for(x = 0; x < olinebits; x++)
   4193     {
   4194       unsigned char bit = readBitFromReversedStream(&ibp, in);
   4195       setBitOfReversedStream(&obp, out, bit);
   4196     }
   4197     ibp += diff;
   4198   }
   4199 }
   4200 
   4201 /*out must be buffer big enough to contain full image, and in must contain the full decompressed data from
   4202 the IDAT chunks (with filter index bytes and possible padding bits)
   4203 return value is error*/
   4204 static unsigned postProcessScanlines(unsigned char* out, unsigned char* in,
   4205                                      unsigned w, unsigned h, const LodePNGInfo* info_png)
   4206 {
   4207   /*
   4208   This function converts the filtered-padded-interlaced data into pure 2D image buffer with the PNG's colortype.
   4209   Steps:
   4210   *) if no Adam7: 1) unfilter 2) remove padding bits (= posible extra bits per scanline if bpp < 8)
   4211   *) if adam7: 1) 7x unfilter 2) 7x remove padding bits 3) Adam7_deinterlace
   4212   NOTE: the in buffer will be overwritten with intermediate data!
   4213   */
   4214   unsigned bpp = lodepng_get_bpp(&info_png->color);
   4215   if(bpp == 0) return 31; /*error: invalid colortype*/
   4216 
   4217   if(info_png->interlace_method == 0)
   4218   {
   4219     if(bpp < 8 && w * bpp != ((w * bpp + 7) / 8) * 8)
   4220     {
   4221       CERROR_TRY_RETURN(unfilter(in, in, w, h, bpp));
   4222       removePaddingBits(out, in, w * bpp, ((w * bpp + 7) / 8) * 8, h);
   4223     }
   4224     /*we can immediatly filter into the out buffer, no other steps needed*/
   4225     else CERROR_TRY_RETURN(unfilter(out, in, w, h, bpp));
   4226   }
   4227   else /*interlace_method is 1 (Adam7)*/
   4228   {
   4229     unsigned passw[7], passh[7]; size_t filter_passstart[8], padded_passstart[8], passstart[8];
   4230     unsigned i;
   4231 
   4232     Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
   4233 
   4234     for(i = 0; i < 7; i++)
   4235     {
   4236       CERROR_TRY_RETURN(unfilter(&in[padded_passstart[i]], &in[filter_passstart[i]], passw[i], passh[i], bpp));
   4237       /*TODO: possible efficiency improvement: if in this reduced image the bits fit nicely in 1 scanline,
   4238       move bytes instead of bits or move not at all*/
   4239       if(bpp < 8)
   4240       {
   4241         /*remove padding bits in scanlines; after this there still may be padding
   4242         bits between the different reduced images: each reduced image still starts nicely at a byte*/
   4243         removePaddingBits(&in[passstart[i]], &in[padded_passstart[i]], passw[i] * bpp,
   4244                           ((passw[i] * bpp + 7) / 8) * 8, passh[i]);
   4245       }
   4246     }
   4247 
   4248     Adam7_deinterlace(out, in, w, h, bpp);
   4249   }
   4250 
   4251   return 0;
   4252 }
   4253 
   4254 static unsigned readChunk_PLTE(LodePNGColorMode* color, const unsigned char* data, size_t chunkLength)
   4255 {
   4256   unsigned pos = 0, i;
   4257   if(color->palette) lodepng_free(color->palette);
   4258   color->palettesize = chunkLength / 3;
   4259   color->palette = (unsigned char*)lodepng_malloc(4 * color->palettesize);
   4260   if(!color->palette && color->palettesize)
   4261   {
   4262     color->palettesize = 0;
   4263     return 83; /*alloc fail*/
   4264   }
   4265   if(color->palettesize > 256) return 38; /*error: palette too big*/
   4266 
   4267   for(i = 0; i < color->palettesize; i++)
   4268   {
   4269     color->palette[4 * i + 0] = data[pos++]; /*R*/
   4270     color->palette[4 * i + 1] = data[pos++]; /*G*/
   4271     color->palette[4 * i + 2] = data[pos++]; /*B*/
   4272     color->palette[4 * i + 3] = 255; /*alpha*/
   4273   }
   4274 
   4275   return 0; /* OK */
   4276 }
   4277 
   4278 static unsigned readChunk_tRNS(LodePNGColorMode* color, const unsigned char* data, size_t chunkLength)
   4279 {
   4280   unsigned i;
   4281   if(color->colortype == LCT_PALETTE)
   4282   {
   4283     /*error: more alpha values given than there are palette entries*/
   4284     if(chunkLength > color->palettesize) return 38;
   4285 
   4286     for(i = 0; i < chunkLength; i++) color->palette[4 * i + 3] = data[i];
   4287   }
   4288   else if(color->colortype == LCT_GREY)
   4289   {
   4290     /*error: this chunk must be 2 bytes for greyscale image*/
   4291     if(chunkLength != 2) return 30;
   4292 
   4293     color->key_defined = 1;
   4294     color->key_r = color->key_g = color->key_b = 256 * data[0] + data[1];
   4295   }
   4296   else if(color->colortype == LCT_RGB)
   4297   {
   4298     /*error: this chunk must be 6 bytes for RGB image*/
   4299     if(chunkLength != 6) return 41;
   4300 
   4301     color->key_defined = 1;
   4302     color->key_r = 256 * data[0] + data[1];
   4303     color->key_g = 256 * data[2] + data[3];
   4304     color->key_b = 256 * data[4] + data[5];
   4305   }
   4306   else return 42; /*error: tRNS chunk not allowed for other color models*/
   4307 
   4308   return 0; /* OK */
   4309 }
   4310 
   4311 
   4312 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
   4313 /*background color chunk (bKGD)*/
   4314 static unsigned readChunk_bKGD(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
   4315 {
   4316   if(info->color.colortype == LCT_PALETTE)
   4317   {
   4318     /*error: this chunk must be 1 byte for indexed color image*/
   4319     if(chunkLength != 1) return 43;
   4320 
   4321     info->background_defined = 1;
   4322     info->background_r = info->background_g = info->background_b = data[0];
   4323   }
   4324   else if(info->color.colortype == LCT_GREY || info->color.colortype == LCT_GREY_ALPHA)
   4325   {
   4326     /*error: this chunk must be 2 bytes for greyscale image*/
   4327     if(chunkLength != 2) return 44;
   4328 
   4329     info->background_defined = 1;
   4330     info->background_r = info->background_g = info->background_b
   4331                                  = 256 * data[0] + data[1];
   4332   }
   4333   else if(info->color.colortype == LCT_RGB || info->color.colortype == LCT_RGBA)
   4334   {
   4335     /*error: this chunk must be 6 bytes for greyscale image*/
   4336     if(chunkLength != 6) return 45;
   4337 
   4338     info->background_defined = 1;
   4339     info->background_r = 256 * data[0] + data[1];
   4340     info->background_g = 256 * data[2] + data[3];
   4341     info->background_b = 256 * data[4] + data[5];
   4342   }
   4343 
   4344   return 0; /* OK */
   4345 }
   4346 
   4347 /*text chunk (tEXt)*/
   4348 static unsigned readChunk_tEXt(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
   4349 {
   4350   unsigned error = 0;
   4351   char *key = 0, *str = 0;
   4352   unsigned i;
   4353 
   4354   while(!error) /*not really a while loop, only used to break on error*/
   4355   {
   4356     unsigned length, string2_begin;
   4357 
   4358     length = 0;
   4359     while(length < chunkLength && data[length] != 0) length++;
   4360     /*even though it's not allowed by the standard, no error is thrown if
   4361     there's no null termination char, if the text is empty*/
   4362     if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
   4363 
   4364     key = (char*)lodepng_malloc(length + 1);
   4365     if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
   4366 
   4367     key[length] = 0;
   4368     for(i = 0; i < length; i++) key[i] = data[i];
   4369 
   4370     string2_begin = length + 1; /*skip keyword null terminator*/
   4371 
   4372     length = chunkLength < string2_begin ? 0 : chunkLength - string2_begin;
   4373     str = (char*)lodepng_malloc(length + 1);
   4374     if(!str) CERROR_BREAK(error, 83); /*alloc fail*/
   4375 
   4376     str[length] = 0;
   4377     for(i = 0; i < length; i++) str[i] = data[string2_begin + i];
   4378 
   4379     error = lodepng_add_text(info, key, str);
   4380 
   4381     break;
   4382   }
   4383 
   4384   lodepng_free(key);
   4385   lodepng_free(str);
   4386 
   4387   return error;
   4388 }
   4389 
   4390 /*compressed text chunk (zTXt)*/
   4391 static unsigned readChunk_zTXt(LodePNGInfo* info, const LodePNGDecompressSettings* zlibsettings,
   4392                                const unsigned char* data, size_t chunkLength)
   4393 {
   4394   unsigned error = 0;
   4395   unsigned i;
   4396 
   4397   unsigned length, string2_begin;
   4398   char *key = 0;
   4399   ucvector decoded;
   4400 
   4401   ucvector_init(&decoded);
   4402 
   4403   while(!error) /*not really a while loop, only used to break on error*/
   4404   {
   4405     for(length = 0; length < chunkLength && data[length] != 0; length++) ;
   4406     if(length + 2 >= chunkLength) CERROR_BREAK(error, 75); /*no null termination, corrupt?*/
   4407     if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
   4408 
   4409     key = (char*)lodepng_malloc(length + 1);
   4410     if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
   4411 
   4412     key[length] = 0;
   4413     for(i = 0; i < length; i++) key[i] = data[i];
   4414 
   4415     if(data[length + 1] != 0) CERROR_BREAK(error, 72); /*the 0 byte indicating compression must be 0*/
   4416 
   4417     string2_begin = length + 2;
   4418     if(string2_begin > chunkLength) CERROR_BREAK(error, 75); /*no null termination, corrupt?*/
   4419 
   4420     length = chunkLength - string2_begin;
   4421     /*will fail if zlib error, e.g. if length is too small*/
   4422     error = zlib_decompress(&decoded.data, &decoded.size,
   4423                             (unsigned char*)(&data[string2_begin]),
   4424                             length, zlibsettings);
   4425     if(error) break;
   4426     ucvector_push_back(&decoded, 0);
   4427 
   4428     error = lodepng_add_text(info, key, (char*)decoded.data);
   4429 
   4430     break;
   4431   }
   4432 
   4433   lodepng_free(key);
   4434   ucvector_cleanup(&decoded);
   4435 
   4436   return error;
   4437 }
   4438 
   4439 /*international text chunk (iTXt)*/
   4440 static unsigned readChunk_iTXt(LodePNGInfo* info, const LodePNGDecompressSettings* zlibsettings,
   4441                                const unsigned char* data, size_t chunkLength)
   4442 {
   4443   unsigned error = 0;
   4444   unsigned i;
   4445 
   4446   unsigned length, begin, compressed;
   4447   char *key = 0, *langtag = 0, *transkey = 0;
   4448   ucvector decoded;
   4449   ucvector_init(&decoded);
   4450 
   4451   while(!error) /*not really a while loop, only used to break on error*/
   4452   {
   4453     /*Quick check if the chunk length isn't too small. Even without check
   4454     it'd still fail with other error checks below if it's too short. This just gives a different error code.*/
   4455     if(chunkLength < 5) CERROR_BREAK(error, 30); /*iTXt chunk too short*/
   4456 
   4457     /*read the key*/
   4458     for(length = 0; length < chunkLength && data[length] != 0; length++) ;
   4459     if(length + 3 >= chunkLength) CERROR_BREAK(error, 75); /*no null termination char, corrupt?*/
   4460     if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
   4461 
   4462     key = (char*)lodepng_malloc(length + 1);
   4463     if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
   4464 
   4465     key[length] = 0;
   4466     for(i = 0; i < length; i++) key[i] = data[i];
   4467 
   4468     /*read the compression method*/
   4469     compressed = data[length + 1];
   4470     if(data[length + 2] != 0) CERROR_BREAK(error, 72); /*the 0 byte indicating compression must be 0*/
   4471 
   4472     /*even though it's not allowed by the standard, no error is thrown if
   4473     there's no null termination char, if the text is empty for the next 3 texts*/
   4474 
   4475     /*read the langtag*/
   4476     begin = length + 3;
   4477     length = 0;
   4478     for(i = begin; i < chunkLength && data[i] != 0; i++) length++;
   4479 
   4480     langtag = (char*)lodepng_malloc(length + 1);
   4481     if(!langtag) CERROR_BREAK(error, 83); /*alloc fail*/
   4482 
   4483     langtag[length] = 0;
   4484     for(i = 0; i < length; i++) langtag[i] = data[begin + i];
   4485 
   4486     /*read the transkey*/
   4487     begin += length + 1;
   4488     length = 0;
   4489     for(i = begin; i < chunkLength && data[i] != 0; i++) length++;
   4490 
   4491     transkey = (char*)lodepng_malloc(length + 1);
   4492     if(!transkey) CERROR_BREAK(error, 83); /*alloc fail*/
   4493 
   4494     transkey[length] = 0;
   4495     for(i = 0; i < length; i++) transkey[i] = data[begin + i];
   4496 
   4497     /*read the actual text*/
   4498     begin += length + 1;
   4499 
   4500     length = chunkLength < begin ? 0 : chunkLength - begin;
   4501 
   4502     if(compressed)
   4503     {
   4504       /*will fail if zlib error, e.g. if length is too small*/
   4505       error = zlib_decompress(&decoded.data, &decoded.size,
   4506                               (unsigned char*)(&data[begin]),
   4507                               length, zlibsettings);
   4508       if(error) break;
   4509       if(decoded.allocsize < decoded.size) decoded.allocsize = decoded.size;
   4510       ucvector_push_back(&decoded, 0);
   4511     }
   4512     else
   4513     {
   4514       if(!ucvector_resize(&decoded, length + 1)) CERROR_BREAK(error, 83 /*alloc fail*/);
   4515 
   4516       decoded.data[length] = 0;
   4517       for(i = 0; i < length; i++) decoded.data[i] = data[begin + i];
   4518     }
   4519 
   4520     error = lodepng_add_itext(info, key, langtag, transkey, (char*)decoded.data);
   4521 
   4522     break;
   4523   }
   4524 
   4525   lodepng_free(key);
   4526   lodepng_free(langtag);
   4527   lodepng_free(transkey);
   4528   ucvector_cleanup(&decoded);
   4529 
   4530   return error;
   4531 }
   4532 
   4533 static unsigned readChunk_tIME(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
   4534 {
   4535   if(chunkLength != 7) return 73; /*invalid tIME chunk size*/
   4536 
   4537   info->time_defined = 1;
   4538   info->time.year = 256 * data[0] + data[+ 1];
   4539   info->time.month = data[2];
   4540   info->time.day = data[3];
   4541   info->time.hour = data[4];
   4542   info->time.minute = data[5];
   4543   info->time.second = data[6];
   4544 
   4545   return 0; /* OK */
   4546 }
   4547 
   4548 static unsigned readChunk_pHYs(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
   4549 {
   4550   if(chunkLength != 9) return 74; /*invalid pHYs chunk size*/
   4551 
   4