lodepng.cpp

00001 /*
00002 LodePNG version 20131222
00003 
00004 Copyright (c) 2005-2013 Lode Vandevenne
00005 
00006 This software is provided 'as-is', without any express or implied
00007 warranty. In no event will the authors be held liable for any damages
00008 arising from the use of this software.
00009 
00010 Permission is granted to anyone to use this software for any purpose,
00011 including commercial applications, and to alter it and redistribute it
00012 freely, subject to the following restrictions:
00013 
00014     1. The origin of this software must not be misrepresented; you must not
00015     claim that you wrote the original software. If you use this software
00016     in a product, an acknowledgment in the product documentation would be
00017     appreciated but is not required.
00018 
00019     2. Altered source versions must be plainly marked as such, and must not be
00020     misrepresented as being the original software.
00021 
00022     3. This notice may not be removed or altered from any source
00023     distribution.
00024 */
00025 
00026 /*
00027 The manual and changelog are in the header file "lodepng.h"
00028 Rename this file to lodepng.cpp to use it for C++, or to lodepng.c to use it for C.
00029 */
00030 
00031 #include "lodepng.h"
00032 
00033 #include <stdio.h>
00034 #include <stdlib.h>
00035 
00036 #ifdef LODEPNG_COMPILE_CPP
00037 #include <fstream>
00038 #endif /*LODEPNG_COMPILE_CPP*/
00039 
00040 #define VERSION_STRING "20131222"
00041 
00042 /*
00043 This source file is built up in the following large parts. The code sections
00044 with the "LODEPNG_COMPILE_" #defines divide this up further in an intermixed way.
00045 -Tools for C and common code for PNG and Zlib
00046 -C Code for Zlib (huffman, deflate, ...)
00047 -C Code for PNG (file format chunks, adam7, PNG filters, color conversions, ...)
00048 -The C++ wrapper around all of the above
00049 */
00050 
00051 /*The malloc, realloc and free functions defined here with "lodepng_" in front
00052 of the name, so that you can easily change them to others related to your
00053 platform if needed. Everything else in the code calls these. Pass
00054 -DLODEPNG_NO_COMPILE_ALLOCATORS to the compiler, or comment out
00055 #define LODEPNG_COMPILE_ALLOCATORS in the header, to disable the ones here and
00056 define them in your own project's source files without needing to change
00057 lodepng source code. Don't forget to remove "static" if you copypaste them
00058 from here.*/
00059 
00060 #ifdef LODEPNG_COMPILE_ALLOCATORS
00061 static void* lodepng_malloc(size_t size)
00062 {
00063   return malloc(size);
00064 }
00065 
00066 static void* lodepng_realloc(void* ptr, size_t new_size)
00067 {
00068   return realloc(ptr, new_size);
00069 }
00070 
00071 static void lodepng_free(void* ptr)
00072 {
00073   free(ptr);
00074 }
00075 #else /*LODEPNG_COMPILE_ALLOCATORS*/
00076 void* lodepng_malloc(size_t size);
00077 void* lodepng_realloc(void* ptr, size_t new_size);
00078 void lodepng_free(void* ptr);
00079 #endif /*LODEPNG_COMPILE_ALLOCATORS*/
00080 
00081 /* ////////////////////////////////////////////////////////////////////////// */
00082 /* ////////////////////////////////////////////////////////////////////////// */
00083 /* // Tools for C, and common code for PNG and Zlib.                       // */
00084 /* ////////////////////////////////////////////////////////////////////////// */
00085 /* ////////////////////////////////////////////////////////////////////////// */
00086 
00087 /*
00088 Often in case of an error a value is assigned to a variable and then it breaks
00089 out of a loop (to go to the cleanup phase of a function). This macro does that.
00090 It makes the error handling code shorter and more readable.
00091 
00092 Example: if(!uivector_resizev(&frequencies_ll, 286, 0)) ERROR_BREAK(83);
00093 */
00094 #define CERROR_BREAK(errorvar, code)\
00095 {\
00096   errorvar = code;\
00097   break;\
00098 }
00099 
00100 /*version of CERROR_BREAK that assumes the common case where the error variable is named "error"*/
00101 #define ERROR_BREAK(code) CERROR_BREAK(error, code)
00102 
00103 /*Set error var to the error code, and return it.*/
00104 #define CERROR_RETURN_ERROR(errorvar, code)\
00105 {\
00106   errorvar = code;\
00107   return code;\
00108 }
00109 
00110 /*Try the code, if it returns error, also return the error.*/
00111 #define CERROR_TRY_RETURN(call)\
00112 {\
00113   unsigned error = call;\
00114   if(error) return error;\
00115 }
00116 
00117 /*
00118 About uivector, ucvector and string:
00119 -All of them wrap dynamic arrays or text strings in a similar way.
00120 -LodePNG was originally written in C++. The vectors replace the std::vectors that were used in the C++ version.
00121 -The string tools are made to avoid problems with compilers that declare things like strncat as deprecated.
00122 -They're not used in the interface, only internally in this file as static functions.
00123 -As with many other structs in this file, the init and cleanup functions serve as ctor and dtor.
00124 */
00125 
00126 #ifdef LODEPNG_COMPILE_ZLIB
00127 /*dynamic vector of unsigned ints*/
00128 typedef struct uivector
00129 {
00130   unsigned* data;
00131   size_t size; /*size in number of unsigned longs*/
00132   size_t allocsize; /*allocated size in bytes*/
00133 } uivector;
00134 
00135 static void uivector_cleanup(void* p)
00136 {
00137   ((uivector*)p)->size = ((uivector*)p)->allocsize = 0;
00138   lodepng_free(((uivector*)p)->data);
00139   ((uivector*)p)->data = NULL;
00140 }
00141 
00142 /*returns 1 if success, 0 if failure ==> nothing done*/
00143 static unsigned uivector_resize(uivector* p, size_t size)
00144 {
00145   if(size * sizeof(unsigned) > p->allocsize)
00146   {
00147     size_t newsize = size * sizeof(unsigned) * 2;
00148     void* data = lodepng_realloc(p->data, newsize);
00149     if(data)
00150     {
00151       p->allocsize = newsize;
00152       p->data = (unsigned*)data;
00153       p->size = size;
00154     }
00155     else return 0;
00156   }
00157   else p->size = size;
00158   return 1;
00159 }
00160 
00161 /*resize and give all new elements the value*/
00162 static unsigned uivector_resizev(uivector* p, size_t size, unsigned value)
00163 {
00164   size_t oldsize = p->size, i;
00165   if(!uivector_resize(p, size)) return 0;
00166   for(i = oldsize; i < size; i++) p->data[i] = value;
00167   return 1;
00168 }
00169 
00170 static void uivector_init(uivector* p)
00171 {
00172   p->data = NULL;
00173   p->size = p->allocsize = 0;
00174 }
00175 
00176 #ifdef LODEPNG_COMPILE_ENCODER
00177 /*returns 1 if success, 0 if failure ==> nothing done*/
00178 static unsigned uivector_push_back(uivector* p, unsigned c)
00179 {
00180   if(!uivector_resize(p, p->size + 1)) return 0;
00181   p->data[p->size - 1] = c;
00182   return 1;
00183 }
00184 
00185 /*copy q to p, returns 1 if success, 0 if failure ==> nothing done*/
00186 static unsigned uivector_copy(uivector* p, const uivector* q)
00187 {
00188   size_t i;
00189   if(!uivector_resize(p, q->size)) return 0;
00190   for(i = 0; i < q->size; i++) p->data[i] = q->data[i];
00191   return 1;
00192 }
00193 #endif /*LODEPNG_COMPILE_ENCODER*/
00194 #endif /*LODEPNG_COMPILE_ZLIB*/
00195 
00196 /* /////////////////////////////////////////////////////////////////////////// */
00197 
00198 /*dynamic vector of unsigned chars*/
00199 typedef struct ucvector
00200 {
00201   unsigned char* data;
00202   size_t size; /*used size*/
00203   size_t allocsize; /*allocated size*/
00204 } ucvector;
00205 
00206 /*returns 1 if success, 0 if failure ==> nothing done*/
00207 static unsigned ucvector_resize(ucvector* p, size_t size)
00208 {
00209   if(size * sizeof(unsigned char) > p->allocsize)
00210   {
00211     size_t newsize = size * sizeof(unsigned char) * 2;
00212     void* data = lodepng_realloc(p->data, newsize);
00213     if(data)
00214     {
00215       p->allocsize = newsize;
00216       p->data = (unsigned char*)data;
00217       p->size = size;
00218     }
00219     else return 0; /*error: not enough memory*/
00220   }
00221   else p->size = size;
00222   return 1;
00223 }
00224 
00225 #ifdef LODEPNG_COMPILE_PNG
00226 
00227 static void ucvector_cleanup(void* p)
00228 {
00229   ((ucvector*)p)->size = ((ucvector*)p)->allocsize = 0;
00230   lodepng_free(((ucvector*)p)->data);
00231   ((ucvector*)p)->data = NULL;
00232 }
00233 
00234 static void ucvector_init(ucvector* p)
00235 {
00236   p->data = NULL;
00237   p->size = p->allocsize = 0;
00238 }
00239 
00240 #ifdef LODEPNG_COMPILE_DECODER
00241 /*resize and give all new elements the value*/
00242 static unsigned ucvector_resizev(ucvector* p, size_t size, unsigned char value)
00243 {
00244   size_t oldsize = p->size, i;
00245   if(!ucvector_resize(p, size)) return 0;
00246   for(i = oldsize; i < size; i++) p->data[i] = value;
00247   return 1;
00248 }
00249 #endif /*LODEPNG_COMPILE_DECODER*/
00250 #endif /*LODEPNG_COMPILE_PNG*/
00251 
00252 #ifdef LODEPNG_COMPILE_ZLIB
00253 /*you can both convert from vector to buffer&size and vica versa. If you use
00254 init_buffer to take over a buffer and size, it is not needed to use cleanup*/
00255 static void ucvector_init_buffer(ucvector* p, unsigned char* buffer, size_t size)
00256 {
00257   p->data = buffer;
00258   p->allocsize = p->size = size;
00259 }
00260 #endif /*LODEPNG_COMPILE_ZLIB*/
00261 
00262 #if (defined(LODEPNG_COMPILE_PNG) && defined(LODEPNG_COMPILE_ANCILLARY_CHUNKS)) || defined(LODEPNG_COMPILE_ENCODER)
00263 /*returns 1 if success, 0 if failure ==> nothing done*/
00264 static unsigned ucvector_push_back(ucvector* p, unsigned char c)
00265 {
00266   if(!ucvector_resize(p, p->size + 1)) return 0;
00267   p->data[p->size - 1] = c;
00268   return 1;
00269 }
00270 #endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
00271 
00272 
00273 /* ////////////////////////////////////////////////////////////////////////// */
00274 
00275 #ifdef LODEPNG_COMPILE_PNG
00276 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
00277 /*returns 1 if success, 0 if failure ==> nothing done*/
00278 static unsigned string_resize(char** out, size_t size)
00279 {
00280   char* data = (char*)lodepng_realloc(*out, size + 1);
00281   if(data)
00282   {
00283     data[size] = 0; /*null termination char*/
00284     *out = data;
00285   }
00286   return data != 0;
00287 }
00288 
00289 /*init a {char*, size_t} pair for use as string*/
00290 static void string_init(char** out)
00291 {
00292   *out = NULL;
00293   string_resize(out, 0);
00294 }
00295 
00296 /*free the above pair again*/
00297 static void string_cleanup(char** out)
00298 {
00299   lodepng_free(*out);
00300   *out = NULL;
00301 }
00302 
00303 static void string_set(char** out, const char* in)
00304 {
00305   size_t insize = strlen(in), i = 0;
00306   if(string_resize(out, insize))
00307   {
00308     for(i = 0; i < insize; i++)
00309     {
00310       (*out)[i] = in[i];
00311     }
00312   }
00313 }
00314 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
00315 #endif /*LODEPNG_COMPILE_PNG*/
00316 
00317 /* ////////////////////////////////////////////////////////////////////////// */
00318 
00319 unsigned lodepng_read32bitInt(const unsigned char* buffer)
00320 {
00321   return (buffer[0] << 24) | (buffer[1] << 16) | (buffer[2] << 8) | buffer[3];
00322 }
00323 
00324 #if defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)
00325 /*buffer must have at least 4 allocated bytes available*/
00326 static void lodepng_set32bitInt(unsigned char* buffer, unsigned value)
00327 {
00328   buffer[0] = (unsigned char)((value >> 24) & 0xff);
00329   buffer[1] = (unsigned char)((value >> 16) & 0xff);
00330   buffer[2] = (unsigned char)((value >>  8) & 0xff);
00331   buffer[3] = (unsigned char)((value      ) & 0xff);
00332 }
00333 #endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
00334 
00335 #ifdef LODEPNG_COMPILE_ENCODER
00336 static void lodepng_add32bitInt(ucvector* buffer, unsigned value)
00337 {
00338   ucvector_resize(buffer, buffer->size + 4); /*todo: give error if resize failed*/
00339   lodepng_set32bitInt(&buffer->data[buffer->size - 4], value);
00340 }
00341 #endif /*LODEPNG_COMPILE_ENCODER*/
00342 
00343 /* ////////////////////////////////////////////////////////////////////////// */
00344 /* / File IO                                                                / */
00345 /* ////////////////////////////////////////////////////////////////////////// */
00346 
00347 #ifdef LODEPNG_COMPILE_DISK
00348 
00349 unsigned lodepng_load_file(unsigned char** out, size_t* outsize, const char* filename)
00350 {
00351   FILE* file;
00352   long size;
00353 
00354   /*provide some proper output values if error will happen*/
00355   *out = 0;
00356   *outsize = 0;
00357 
00358   file = fopen(filename, "rb");
00359   if(!file) return 78;
00360 
00361   /*get filesize:*/
00362   fseek(file , 0 , SEEK_END);
00363   size = ftell(file);
00364   rewind(file);
00365 
00366   /*read contents of the file into the vector*/
00367   *outsize = 0;
00368   *out = (unsigned char*)lodepng_malloc((size_t)size);
00369   if(size && (*out)) (*outsize) = fread(*out, 1, (size_t)size, file);
00370 
00371   fclose(file);
00372   if(!(*out) && size) return 83; /*the above malloc failed*/
00373   return 0;
00374 }
00375 
00376 /*write given buffer to the file, overwriting the file, it doesn't append to it.*/
00377 unsigned lodepng_save_file(const unsigned char* buffer, size_t buffersize, const char* filename)
00378 {
00379   FILE* file;
00380   file = fopen(filename, "wb" );
00381   if(!file) return 79;
00382   fwrite((char*)buffer , 1 , buffersize, file);
00383   fclose(file);
00384   return 0;
00385 }
00386 
00387 #endif /*LODEPNG_COMPILE_DISK*/
00388 
00389 /* ////////////////////////////////////////////////////////////////////////// */
00390 /* ////////////////////////////////////////////////////////////////////////// */
00391 /* // End of common code and tools. Begin of Zlib related code.            // */
00392 /* ////////////////////////////////////////////////////////////////////////// */
00393 /* ////////////////////////////////////////////////////////////////////////// */
00394 
00395 #ifdef LODEPNG_COMPILE_ZLIB
00396 #ifdef LODEPNG_COMPILE_ENCODER
00397 /*TODO: this ignores potential out of memory errors*/
00398 #define addBitToStream(/*size_t**/ bitpointer, /*ucvector**/ bitstream, /*unsigned char*/ bit)\
00399 {\
00400   /*add a new byte at the end*/\
00401   if(((*bitpointer) & 7) == 0) ucvector_push_back(bitstream, (unsigned char)0);\
00402   /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/\
00403   (bitstream->data[bitstream->size - 1]) |= (bit << ((*bitpointer) & 0x7));\
00404   (*bitpointer)++;\
00405 }
00406 
00407 static void addBitsToStream(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
00408 {
00409   size_t i;
00410   for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> i) & 1));
00411 }
00412 
00413 static void addBitsToStreamReversed(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
00414 {
00415   size_t i;
00416   for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> (nbits - 1 - i)) & 1));
00417 }
00418 #endif /*LODEPNG_COMPILE_ENCODER*/
00419 
00420 #ifdef LODEPNG_COMPILE_DECODER
00421 
00422 #define READBIT(bitpointer, bitstream) ((bitstream[bitpointer >> 3] >> (bitpointer & 0x7)) & (unsigned char)1)
00423 
00424 static unsigned char readBitFromStream(size_t* bitpointer, const unsigned char* bitstream)
00425 {
00426   unsigned char result = (unsigned char)(READBIT(*bitpointer, bitstream));
00427   (*bitpointer)++;
00428   return result;
00429 }
00430 
00431 static unsigned readBitsFromStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
00432 {
00433   unsigned result = 0, i;
00434   for(i = 0; i < nbits; i++)
00435   {
00436     result += ((unsigned)READBIT(*bitpointer, bitstream)) << i;
00437     (*bitpointer)++;
00438   }
00439   return result;
00440 }
00441 #endif /*LODEPNG_COMPILE_DECODER*/
00442 
00443 /* ////////////////////////////////////////////////////////////////////////// */
00444 /* / Deflate - Huffman                                                      / */
00445 /* ////////////////////////////////////////////////////////////////////////// */
00446 
00447 #define FIRST_LENGTH_CODE_INDEX 257
00448 #define LAST_LENGTH_CODE_INDEX 285
00449 /*256 literals, the end code, some length codes, and 2 unused codes*/
00450 #define NUM_DEFLATE_CODE_SYMBOLS 288
00451 /*the distance codes have their own symbols, 30 used, 2 unused*/
00452 #define NUM_DISTANCE_SYMBOLS 32
00453 /*the code length codes. 0-15: code lengths, 16: copy previous 3-6 times, 17: 3-10 zeros, 18: 11-138 zeros*/
00454 #define NUM_CODE_LENGTH_CODES 19
00455 
00456 /*the base lengths represented by codes 257-285*/
00457 static const unsigned LENGTHBASE[29]
00458   = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
00459      67, 83, 99, 115, 131, 163, 195, 227, 258};
00460 
00461 /*the extra bits used by codes 257-285 (added to base length)*/
00462 static const unsigned LENGTHEXTRA[29]
00463   = {0, 0, 0, 0, 0, 0, 0,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,
00464       4,  4,  4,   4,   5,   5,   5,   5,   0};
00465 
00466 /*the base backwards distances (the bits of distance codes appear after length codes and use their own huffman tree)*/
00467 static const unsigned DISTANCEBASE[30]
00468   = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
00469      769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
00470 
00471 /*the extra bits of backwards distances (added to base)*/
00472 static const unsigned DISTANCEEXTRA[30]
00473   = {0, 0, 0, 0, 1, 1, 2,  2,  3,  3,  4,  4,  5,  5,   6,   6,   7,   7,   8,
00474        8,    9,    9,   10,   10,   11,   11,   12,    12,    13,    13};
00475 
00476 /*the order in which "code length alphabet code lengths" are stored, out of this
00477 the huffman tree of the dynamic huffman tree lengths is generated*/
00478 static const unsigned CLCL_ORDER[NUM_CODE_LENGTH_CODES]
00479   = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
00480 
00481 /* ////////////////////////////////////////////////////////////////////////// */
00482 
00483 /*
00484 Huffman tree struct, containing multiple representations of the tree
00485 */
00486 typedef struct HuffmanTree
00487 {
00488   unsigned* tree2d;
00489   unsigned* tree1d;
00490   unsigned* lengths; /*the lengths of the codes of the 1d-tree*/
00491   unsigned maxbitlen; /*maximum number of bits a single code can get*/
00492   unsigned numcodes; /*number of symbols in the alphabet = number of codes*/
00493 } HuffmanTree;
00494 
00495 /*function used for debug purposes to draw the tree in ascii art with C++*/
00496 /*
00497 static void HuffmanTree_draw(HuffmanTree* tree)
00498 {
00499   std::cout << "tree. length: " << tree->numcodes << " maxbitlen: " << tree->maxbitlen << std::endl;
00500   for(size_t i = 0; i < tree->tree1d.size; i++)
00501   {
00502     if(tree->lengths.data[i])
00503       std::cout << i << " " << tree->tree1d.data[i] << " " << tree->lengths.data[i] << std::endl;
00504   }
00505   std::cout << std::endl;
00506 }*/
00507 
00508 static void HuffmanTree_init(HuffmanTree* tree)
00509 {
00510   tree->tree2d = 0;
00511   tree->tree1d = 0;
00512   tree->lengths = 0;
00513 }
00514 
00515 static void HuffmanTree_cleanup(HuffmanTree* tree)
00516 {
00517   lodepng_free(tree->tree2d);
00518   lodepng_free(tree->tree1d);
00519   lodepng_free(tree->lengths);
00520 }
00521 
00522 /*the tree representation used by the decoder. return value is error*/
00523 static unsigned HuffmanTree_make2DTree(HuffmanTree* tree)
00524 {
00525   unsigned nodefilled = 0; /*up to which node it is filled*/
00526   unsigned treepos = 0; /*position in the tree (1 of the numcodes columns)*/
00527   unsigned n, i;
00528 
00529   tree->tree2d = (unsigned*)lodepng_malloc(tree->numcodes * 2 * sizeof(unsigned));
00530   if(!tree->tree2d) return 83; /*alloc fail*/
00531 
00532   /*
00533   convert tree1d[] to tree2d[][]. In the 2D array, a value of 32767 means
00534   uninited, a value >= numcodes is an address to another bit, a value < numcodes
00535   is a code. The 2 rows are the 2 possible bit values (0 or 1), there are as
00536   many columns as codes - 1.
00537   A good huffmann tree has N * 2 - 1 nodes, of which N - 1 are internal nodes.
00538   Here, the internal nodes are stored (what their 0 and 1 option point to).
00539   There is only memory for such good tree currently, if there are more nodes
00540   (due to too long length codes), error 55 will happen
00541   */
00542   for(n = 0; n < tree->numcodes * 2; n++)
00543   {
00544     tree->tree2d[n] = 32767; /*32767 here means the tree2d isn't filled there yet*/
00545   }
00546 
00547   for(n = 0; n < tree->numcodes; n++) /*the codes*/
00548   {
00549     for(i = 0; i < tree->lengths[n]; i++) /*the bits for this code*/
00550     {
00551       unsigned char bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1);
00552       if(treepos > tree->numcodes - 2) return 55; /*oversubscribed, see comment in lodepng_error_text*/
00553       if(tree->tree2d[2 * treepos + bit] == 32767) /*not yet filled in*/
00554       {
00555         if(i + 1 == tree->lengths[n]) /*last bit*/
00556         {
00557           tree->tree2d[2 * treepos + bit] = n; /*put the current code in it*/
00558           treepos = 0;
00559         }
00560         else
00561         {
00562           /*put address of the next step in here, first that address has to be found of course
00563           (it's just nodefilled + 1)...*/
00564           nodefilled++;
00565           /*addresses encoded with numcodes added to it*/
00566           tree->tree2d[2 * treepos + bit] = nodefilled + tree->numcodes;
00567           treepos = nodefilled;
00568         }
00569       }
00570       else treepos = tree->tree2d[2 * treepos + bit] - tree->numcodes;
00571     }
00572   }
00573 
00574   for(n = 0; n < tree->numcodes * 2; n++)
00575   {
00576     if(tree->tree2d[n] == 32767) tree->tree2d[n] = 0; /*remove possible remaining 32767's*/
00577   }
00578 
00579   return 0;
00580 }
00581 
00582 /*
00583 Second step for the ...makeFromLengths and ...makeFromFrequencies functions.
00584 numcodes, lengths and maxbitlen must already be filled in correctly. return
00585 value is error.
00586 */
00587 static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree)
00588 {
00589   uivector blcount;
00590   uivector nextcode;
00591   unsigned bits, n, error = 0;
00592 
00593   uivector_init(&blcount);
00594   uivector_init(&nextcode);
00595 
00596   tree->tree1d = (unsigned*)lodepng_malloc(tree->numcodes * sizeof(unsigned));
00597   if(!tree->tree1d) error = 83; /*alloc fail*/
00598 
00599   if(!uivector_resizev(&blcount, tree->maxbitlen + 1, 0)
00600   || !uivector_resizev(&nextcode, tree->maxbitlen + 1, 0))
00601     error = 83; /*alloc fail*/
00602 
00603   if(!error)
00604   {
00605     /*step 1: count number of instances of each code length*/
00606     for(bits = 0; bits < tree->numcodes; bits++) blcount.data[tree->lengths[bits]]++;
00607     /*step 2: generate the nextcode values*/
00608     for(bits = 1; bits <= tree->maxbitlen; bits++)
00609     {
00610       nextcode.data[bits] = (nextcode.data[bits - 1] + blcount.data[bits - 1]) << 1;
00611     }
00612     /*step 3: generate all the codes*/
00613     for(n = 0; n < tree->numcodes; n++)
00614     {
00615       if(tree->lengths[n] != 0) tree->tree1d[n] = nextcode.data[tree->lengths[n]]++;
00616     }
00617   }
00618 
00619   uivector_cleanup(&blcount);
00620   uivector_cleanup(&nextcode);
00621 
00622   if(!error) return HuffmanTree_make2DTree(tree);
00623   else return error;
00624 }
00625 
00626 /*
00627 given the code lengths (as stored in the PNG file), generate the tree as defined
00628 by Deflate. maxbitlen is the maximum bits that a code in the tree can have.
00629 return value is error.
00630 */
00631 static unsigned HuffmanTree_makeFromLengths(HuffmanTree* tree, const unsigned* bitlen,
00632                                             size_t numcodes, unsigned maxbitlen)
00633 {
00634   unsigned i;
00635   tree->lengths = (unsigned*)lodepng_malloc(numcodes * sizeof(unsigned));
00636   if(!tree->lengths) return 83; /*alloc fail*/
00637   for(i = 0; i < numcodes; i++) tree->lengths[i] = bitlen[i];
00638   tree->numcodes = (unsigned)numcodes; /*number of symbols*/
00639   tree->maxbitlen = maxbitlen;
00640   return HuffmanTree_makeFromLengths2(tree);
00641 }
00642 
00643 #ifdef LODEPNG_COMPILE_ENCODER
00644 
00645 /*
00646 A coin, this is the terminology used for the package-merge algorithm and the
00647 coin collector's problem. This is used to generate the huffman tree.
00648 A coin can be multiple coins (when they're merged)
00649 */
00650 typedef struct Coin
00651 {
00652   uivector symbols;
00653   float weight; /*the sum of all weights in this coin*/
00654 } Coin;
00655 
00656 static void coin_init(Coin* c)
00657 {
00658   uivector_init(&c->symbols);
00659 }
00660 
00661 /*argument c is void* so that this dtor can be given as function pointer to the vector resize function*/
00662 static void coin_cleanup(void* c)
00663 {
00664   uivector_cleanup(&((Coin*)c)->symbols);
00665 }
00666 
00667 static void coin_copy(Coin* c1, const Coin* c2)
00668 {
00669   c1->weight = c2->weight;
00670   uivector_copy(&c1->symbols, &c2->symbols);
00671 }
00672 
00673 static void add_coins(Coin* c1, const Coin* c2)
00674 {
00675   size_t i;
00676   for(i = 0; i < c2->symbols.size; i++) uivector_push_back(&c1->symbols, c2->symbols.data[i]);
00677   c1->weight += c2->weight;
00678 }
00679 
00680 static void init_coins(Coin* coins, size_t num)
00681 {
00682   size_t i;
00683   for(i = 0; i < num; i++) coin_init(&coins[i]);
00684 }
00685 
00686 static void cleanup_coins(Coin* coins, size_t num)
00687 {
00688   size_t i;
00689   for(i = 0; i < num; i++) coin_cleanup(&coins[i]);
00690 }
00691 
00692 static int coin_compare(const void* a, const void* b) {
00693   float wa = ((const Coin*)a)->weight;
00694   float wb = ((const Coin*)b)->weight;
00695   return wa > wb ? 1 : wa < wb ? -1 : 0;
00696 }
00697 
00698 static unsigned append_symbol_coins(Coin* coins, const unsigned* frequencies, unsigned numcodes, size_t sum)
00699 {
00700   unsigned i;
00701   unsigned j = 0; /*index of present symbols*/
00702   for(i = 0; i < numcodes; i++)
00703   {
00704     if(frequencies[i] != 0) /*only include symbols that are present*/
00705     {
00706       coins[j].weight = frequencies[i] / (float)sum;
00707       uivector_push_back(&coins[j].symbols, i);
00708       j++;
00709     }
00710   }
00711   return 0;
00712 }
00713 
00714 unsigned lodepng_huffman_code_lengths(unsigned* lengths, const unsigned* frequencies,
00715                                       size_t numcodes, unsigned maxbitlen)
00716 {
00717   unsigned i, j;
00718   size_t sum = 0, numpresent = 0;
00719   unsigned error = 0;
00720   Coin* coins; /*the coins of the currently calculated row*/
00721   Coin* prev_row; /*the previous row of coins*/
00722   unsigned numcoins;
00723   unsigned coinmem;
00724 
00725   if(numcodes == 0) return 80; /*error: a tree of 0 symbols is not supposed to be made*/
00726 
00727   for(i = 0; i < numcodes; i++)
00728   {
00729     if(frequencies[i] > 0)
00730     {
00731       numpresent++;
00732       sum += frequencies[i];
00733     }
00734   }
00735 
00736   for(i = 0; i < numcodes; i++) lengths[i] = 0;
00737 
00738   /*ensure at least two present symbols. There should be at least one symbol
00739   according to RFC 1951 section 3.2.7. To decoders incorrectly require two. To
00740   make these work as well ensure there are at least two symbols. The
00741   Package-Merge code below also doesn't work correctly if there's only one
00742   symbol, it'd give it the theoritical 0 bits but in practice zlib wants 1 bit*/
00743   if(numpresent == 0)
00744   {
00745     lengths[0] = lengths[1] = 1; /*note that for RFC 1951 section 3.2.7, only lengths[0] = 1 is needed*/
00746   }
00747   else if(numpresent == 1)
00748   {
00749     for(i = 0; i < numcodes; i++)
00750     {
00751       if(frequencies[i])
00752       {
00753         lengths[i] = 1;
00754         lengths[i == 0 ? 1 : 0] = 1;
00755         break;
00756       }
00757     }
00758   }
00759   else
00760   {
00761     /*Package-Merge algorithm represented by coin collector's problem
00762     For every symbol, maxbitlen coins will be created*/
00763 
00764     coinmem = numpresent * 2; /*max amount of coins needed with the current algo*/
00765     coins = (Coin*)lodepng_malloc(sizeof(Coin) * coinmem);
00766     prev_row = (Coin*)lodepng_malloc(sizeof(Coin) * coinmem);
00767     if(!coins || !prev_row)
00768     {
00769       lodepng_free(coins);
00770       lodepng_free(prev_row);
00771       return 83; /*alloc fail*/
00772     }
00773     init_coins(coins, coinmem);
00774     init_coins(prev_row, coinmem);
00775 
00776     /*first row, lowest denominator*/
00777     error = append_symbol_coins(coins, frequencies, numcodes, sum);
00778     numcoins = numpresent;
00779     qsort(coins, numcoins, sizeof(Coin), coin_compare);
00780     if(!error)
00781     {
00782       unsigned numprev = 0;
00783       for(j = 1; j <= maxbitlen && !error; j++) /*each of the remaining rows*/
00784       {
00785         unsigned tempnum;
00786         Coin* tempcoins;
00787         /*swap prev_row and coins, and their amounts*/
00788         tempcoins = prev_row; prev_row = coins; coins = tempcoins;
00789         tempnum = numprev; numprev = numcoins; numcoins = tempnum;
00790 
00791         cleanup_coins(coins, numcoins);
00792         init_coins(coins, numcoins);
00793 
00794         numcoins = 0;
00795 
00796         /*fill in the merged coins of the previous row*/
00797         for(i = 0; i + 1 < numprev; i += 2)
00798         {
00799           /*merge prev_row[i] and prev_row[i + 1] into new coin*/
00800           Coin* coin = &coins[numcoins++];
00801           coin_copy(coin, &prev_row[i]);
00802           add_coins(coin, &prev_row[i + 1]);
00803         }
00804         /*fill in all the original symbols again*/
00805         if(j < maxbitlen)
00806         {
00807           error = append_symbol_coins(coins + numcoins, frequencies, numcodes, sum);
00808           numcoins += numpresent;
00809         }
00810         qsort(coins, numcoins, sizeof(Coin), coin_compare);
00811       }
00812     }
00813 
00814     if(!error)
00815     {
00816       /*calculate the lenghts of each symbol, as the amount of times a coin of each symbol is used*/
00817       for(i = 0; i < numpresent - 1; i++)
00818       {
00819         Coin* coin = &coins[i];
00820         for(j = 0; j < coin->symbols.size; j++) lengths[coin->symbols.data[j]]++;
00821       }
00822     }
00823 
00824     cleanup_coins(coins, coinmem);
00825     lodepng_free(coins);
00826     cleanup_coins(prev_row, coinmem);
00827     lodepng_free(prev_row);
00828   }
00829 
00830   return error;
00831 }
00832 
00833 /*Create the Huffman tree given the symbol frequencies*/
00834 static unsigned HuffmanTree_makeFromFrequencies(HuffmanTree* tree, const unsigned* frequencies,
00835                                                 size_t mincodes, size_t numcodes, unsigned maxbitlen)
00836 {
00837   unsigned error = 0;
00838   while(!frequencies[numcodes - 1] && numcodes > mincodes) numcodes--; /*trim zeroes*/
00839   tree->maxbitlen = maxbitlen;
00840   tree->numcodes = (unsigned)numcodes; /*number of symbols*/
00841   tree->lengths = (unsigned*)lodepng_realloc(tree->lengths, numcodes * sizeof(unsigned));
00842   if(!tree->lengths) return 83; /*alloc fail*/
00843   /*initialize all lengths to 0*/
00844   memset(tree->lengths, 0, numcodes * sizeof(unsigned));
00845 
00846   error = lodepng_huffman_code_lengths(tree->lengths, frequencies, numcodes, maxbitlen);
00847   if(!error) error = HuffmanTree_makeFromLengths2(tree);
00848   return error;
00849 }
00850 
00851 static unsigned HuffmanTree_getCode(const HuffmanTree* tree, unsigned index)
00852 {
00853   return tree->tree1d[index];
00854 }
00855 
00856 static unsigned HuffmanTree_getLength(const HuffmanTree* tree, unsigned index)
00857 {
00858   return tree->lengths[index];
00859 }
00860 #endif /*LODEPNG_COMPILE_ENCODER*/
00861 
00862 /*get the literal and length code tree of a deflated block with fixed tree, as per the deflate specification*/
00863 static unsigned generateFixedLitLenTree(HuffmanTree* tree)
00864 {
00865   unsigned i, error = 0;
00866   unsigned* bitlen = (unsigned*)lodepng_malloc(NUM_DEFLATE_CODE_SYMBOLS * sizeof(unsigned));
00867   if(!bitlen) return 83; /*alloc fail*/
00868 
00869   /*288 possible codes: 0-255=literals, 256=endcode, 257-285=lengthcodes, 286-287=unused*/
00870   for(i =   0; i <= 143; i++) bitlen[i] = 8;
00871   for(i = 144; i <= 255; i++) bitlen[i] = 9;
00872   for(i = 256; i <= 279; i++) bitlen[i] = 7;
00873   for(i = 280; i <= 287; i++) bitlen[i] = 8;
00874 
00875   error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DEFLATE_CODE_SYMBOLS, 15);
00876 
00877   lodepng_free(bitlen);
00878   return error;
00879 }
00880 
00881 /*get the distance code tree of a deflated block with fixed tree, as specified in the deflate specification*/
00882 static unsigned generateFixedDistanceTree(HuffmanTree* tree)
00883 {
00884   unsigned i, error = 0;
00885   unsigned* bitlen = (unsigned*)lodepng_malloc(NUM_DISTANCE_SYMBOLS * sizeof(unsigned));
00886   if(!bitlen) return 83; /*alloc fail*/
00887 
00888   /*there are 32 distance codes, but 30-31 are unused*/
00889   for(i = 0; i < NUM_DISTANCE_SYMBOLS; i++) bitlen[i] = 5;
00890   error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DISTANCE_SYMBOLS, 15);
00891 
00892   lodepng_free(bitlen);
00893   return error;
00894 }
00895 
00896 #ifdef LODEPNG_COMPILE_DECODER
00897 
00898 /*
00899 returns the code, or (unsigned)(-1) if error happened
00900 inbitlength is the length of the complete buffer, in bits (so its byte length times 8)
00901 */
00902 static unsigned huffmanDecodeSymbol(const unsigned char* in, size_t* bp,
00903                                     const HuffmanTree* codetree, size_t inbitlength)
00904 {
00905   unsigned treepos = 0, ct;
00906   for(;;)
00907   {
00908     if(*bp >= inbitlength) return (unsigned)(-1); /*error: end of input memory reached without endcode*/
00909     /*
00910     decode the symbol from the tree. The "readBitFromStream" code is inlined in
00911     the expression below because this is the biggest bottleneck while decoding
00912     */
00913     ct = codetree->tree2d[(treepos << 1) + READBIT(*bp, in)];
00914     (*bp)++;
00915     if(ct < codetree->numcodes) return ct; /*the symbol is decoded, return it*/
00916     else treepos = ct - codetree->numcodes; /*symbol not yet decoded, instead move tree position*/
00917 
00918     if(treepos >= codetree->numcodes) return (unsigned)(-1); /*error: it appeared outside the codetree*/
00919   }
00920 }
00921 #endif /*LODEPNG_COMPILE_DECODER*/
00922 
00923 #ifdef LODEPNG_COMPILE_DECODER
00924 
00925 /* ////////////////////////////////////////////////////////////////////////// */
00926 /* / Inflator (Decompressor)                                                / */
00927 /* ////////////////////////////////////////////////////////////////////////// */
00928 
00929 /*get the tree of a deflated block with fixed tree, as specified in the deflate specification*/
00930 static void getTreeInflateFixed(HuffmanTree* tree_ll, HuffmanTree* tree_d)
00931 {
00932   /*TODO: check for out of memory errors*/
00933   generateFixedLitLenTree(tree_ll);
00934   generateFixedDistanceTree(tree_d);
00935 }
00936 
00937 /*get the tree of a deflated block with dynamic tree, the tree itself is also Huffman compressed with a known tree*/
00938 static unsigned getTreeInflateDynamic(HuffmanTree* tree_ll, HuffmanTree* tree_d,
00939                                       const unsigned char* in, size_t* bp, size_t inlength)
00940 {
00941   /*make sure that length values that aren't filled in will be 0, or a wrong tree will be generated*/
00942   unsigned error = 0;
00943   unsigned n, HLIT, HDIST, HCLEN, i;
00944   size_t inbitlength = inlength * 8;
00945 
00946   /*see comments in deflateDynamic for explanation of the context and these variables, it is analogous*/
00947   unsigned* bitlen_ll = 0; /*lit,len code lengths*/
00948   unsigned* bitlen_d = 0; /*dist code lengths*/
00949   /*code length code lengths ("clcl"), the bit lengths of the huffman tree used to compress bitlen_ll and bitlen_d*/
00950   unsigned* bitlen_cl = 0;
00951   HuffmanTree tree_cl; /*the code tree for code length codes (the huffman tree for compressed huffman trees)*/
00952 
00953   if((*bp) >> 3 >= inlength - 2) return 49; /*error: the bit pointer is or will go past the memory*/
00954 
00955   /*number of literal/length codes + 257. Unlike the spec, the value 257 is added to it here already*/
00956   HLIT =  readBitsFromStream(bp, in, 5) + 257;
00957   /*number of distance codes. Unlike the spec, the value 1 is added to it here already*/
00958   HDIST = readBitsFromStream(bp, in, 5) + 1;
00959   /*number of code length codes. Unlike the spec, the value 4 is added to it here already*/
00960   HCLEN = readBitsFromStream(bp, in, 4) + 4;
00961 
00962   HuffmanTree_init(&tree_cl);
00963 
00964   while(!error)
00965   {
00966     /*read the code length codes out of 3 * (amount of code length codes) bits*/
00967 
00968     bitlen_cl = (unsigned*)lodepng_malloc(NUM_CODE_LENGTH_CODES * sizeof(unsigned));
00969     if(!bitlen_cl) ERROR_BREAK(83 /*alloc fail*/);
00970 
00971     for(i = 0; i < NUM_CODE_LENGTH_CODES; i++)
00972     {
00973       if(i < HCLEN) bitlen_cl[CLCL_ORDER[i]] = readBitsFromStream(bp, in, 3);
00974       else bitlen_cl[CLCL_ORDER[i]] = 0; /*if not, it must stay 0*/
00975     }
00976 
00977     error = HuffmanTree_makeFromLengths(&tree_cl, bitlen_cl, NUM_CODE_LENGTH_CODES, 7);
00978     if(error) break;
00979 
00980     /*now we can use this tree to read the lengths for the tree that this function will return*/
00981     bitlen_ll = (unsigned*)lodepng_malloc(NUM_DEFLATE_CODE_SYMBOLS * sizeof(unsigned));
00982     bitlen_d = (unsigned*)lodepng_malloc(NUM_DISTANCE_SYMBOLS * sizeof(unsigned));
00983     if(!bitlen_ll || !bitlen_d) ERROR_BREAK(83 /*alloc fail*/);
00984     for(i = 0; i < NUM_DEFLATE_CODE_SYMBOLS; i++) bitlen_ll[i] = 0;
00985     for(i = 0; i < NUM_DISTANCE_SYMBOLS; i++) bitlen_d[i] = 0;
00986 
00987     /*i is the current symbol we're reading in the part that contains the code lengths of lit/len and dist codes*/
00988     i = 0;
00989     while(i < HLIT + HDIST)
00990     {
00991       unsigned code = huffmanDecodeSymbol(in, bp, &tree_cl, inbitlength);
00992       if(code <= 15) /*a length code*/
00993       {
00994         if(i < HLIT) bitlen_ll[i] = code;
00995         else bitlen_d[i - HLIT] = code;
00996         i++;
00997       }
00998       else if(code == 16) /*repeat previous*/
00999       {
01000         unsigned replength = 3; /*read in the 2 bits that indicate repeat length (3-6)*/
01001         unsigned value; /*set value to the previous code*/
01002 
01003         if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
01004         if (i == 0) ERROR_BREAK(54); /*can't repeat previous if i is 0*/
01005 
01006         replength += readBitsFromStream(bp, in, 2);
01007 
01008         if(i < HLIT + 1) value = bitlen_ll[i - 1];
01009         else value = bitlen_d[i - HLIT - 1];
01010         /*repeat this value in the next lengths*/
01011         for(n = 0; n < replength; n++)
01012         {
01013           if(i >= HLIT + HDIST) ERROR_BREAK(13); /*error: i is larger than the amount of codes*/
01014           if(i < HLIT) bitlen_ll[i] = value;
01015           else bitlen_d[i - HLIT] = value;
01016           i++;
01017         }
01018       }
01019       else if(code == 17) /*repeat "0" 3-10 times*/
01020       {
01021         unsigned replength = 3; /*read in the bits that indicate repeat length*/
01022         if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
01023 
01024         replength += readBitsFromStream(bp, in, 3);
01025 
01026         /*repeat this value in the next lengths*/
01027         for(n = 0; n < replength; n++)
01028         {
01029           if(i >= HLIT + HDIST) ERROR_BREAK(14); /*error: i is larger than the amount of codes*/
01030 
01031           if(i < HLIT) bitlen_ll[i] = 0;
01032           else bitlen_d[i - HLIT] = 0;
01033           i++;
01034         }
01035       }
01036       else if(code == 18) /*repeat "0" 11-138 times*/
01037       {
01038         unsigned replength = 11; /*read in the bits that indicate repeat length*/
01039         if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
01040 
01041         replength += readBitsFromStream(bp, in, 7);
01042 
01043         /*repeat this value in the next lengths*/
01044         for(n = 0; n < replength; n++)
01045         {
01046           if(i >= HLIT + HDIST) ERROR_BREAK(15); /*error: i is larger than the amount of codes*/
01047 
01048           if(i < HLIT) bitlen_ll[i] = 0;
01049           else bitlen_d[i - HLIT] = 0;
01050           i++;
01051         }
01052       }
01053       else /*if(code == (unsigned)(-1))*/ /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
01054       {
01055         if(code == (unsigned)(-1))
01056         {
01057           /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
01058           (10=no endcode, 11=wrong jump outside of tree)*/
01059           error = (*bp) > inbitlength ? 10 : 11;
01060         }
01061         else error = 16; /*unexisting code, this can never happen*/
01062         break;
01063       }
01064     }
01065     if(error) break;
01066 
01067     if(bitlen_ll[256] == 0) ERROR_BREAK(64); /*the length of the end code 256 must be larger than 0*/
01068 
01069     /*now we've finally got HLIT and HDIST, so generate the code trees, and the function is done*/
01070     error = HuffmanTree_makeFromLengths(tree_ll, bitlen_ll, NUM_DEFLATE_CODE_SYMBOLS, 15);
01071     if(error) break;
01072     error = HuffmanTree_makeFromLengths(tree_d, bitlen_d, NUM_DISTANCE_SYMBOLS, 15);
01073 
01074     break; /*end of error-while*/
01075   }
01076 
01077   lodepng_free(bitlen_cl);
01078   lodepng_free(bitlen_ll);
01079   lodepng_free(bitlen_d);
01080   HuffmanTree_cleanup(&tree_cl);
01081 
01082   return error;
01083 }
01084 
01085 /*inflate a block with dynamic of fixed Huffman tree*/
01086 static unsigned inflateHuffmanBlock(ucvector* out, const unsigned char* in, size_t* bp,
01087                                     size_t* pos, size_t inlength, unsigned btype)
01088 {
01089   unsigned error = 0;
01090   HuffmanTree tree_ll; /*the huffman tree for literal and length codes*/
01091   HuffmanTree tree_d; /*the huffman tree for distance codes*/
01092   size_t inbitlength = inlength * 8;
01093 
01094   HuffmanTree_init(&tree_ll);
01095   HuffmanTree_init(&tree_d);
01096 
01097   if(btype == 1) getTreeInflateFixed(&tree_ll, &tree_d);
01098   else if(btype == 2) error = getTreeInflateDynamic(&tree_ll, &tree_d, in, bp, inlength);
01099 
01100   while(!error) /*decode all symbols until end reached, breaks at end code*/
01101   {
01102     /*code_ll is literal, length or end code*/
01103     unsigned code_ll = huffmanDecodeSymbol(in, bp, &tree_ll, inbitlength);
01104     if(code_ll <= 255) /*literal symbol*/
01105     {
01106       if((*pos) >= out->size)
01107       {
01108         /*reserve more room at once*/
01109         if(!ucvector_resize(out, ((*pos) + 1) * 2)) ERROR_BREAK(83 /*alloc fail*/);
01110       }
01111       out->data[(*pos)] = (unsigned char)(code_ll);
01112       (*pos)++;
01113     }
01114     else if(code_ll >= FIRST_LENGTH_CODE_INDEX && code_ll <= LAST_LENGTH_CODE_INDEX) /*length code*/
01115     {
01116       unsigned code_d, distance;
01117       unsigned numextrabits_l, numextrabits_d; /*extra bits for length and distance*/
01118       size_t start, forward, backward, length;
01119 
01120       /*part 1: get length base*/
01121       length = LENGTHBASE[code_ll - FIRST_LENGTH_CODE_INDEX];
01122 
01123       /*part 2: get extra bits and add the value of that to length*/
01124       numextrabits_l = LENGTHEXTRA[code_ll - FIRST_LENGTH_CODE_INDEX];
01125       if(*bp >= inbitlength) ERROR_BREAK(51); /*error, bit pointer will jump past memory*/
01126       length += readBitsFromStream(bp, in, numextrabits_l);
01127 
01128       /*part 3: get distance code*/
01129       code_d = huffmanDecodeSymbol(in, bp, &tree_d, inbitlength);
01130       if(code_d > 29)
01131       {
01132         if(code_ll == (unsigned)(-1)) /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
01133         {
01134           /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
01135           (10=no endcode, 11=wrong jump outside of tree)*/
01136           error = (*bp) > inlength * 8 ? 10 : 11;
01137         }
01138         else error = 18; /*error: invalid distance code (30-31 are never used)*/
01139         break;
01140       }
01141       distance = DISTANCEBASE[code_d];
01142 
01143       /*part 4: get extra bits from distance*/
01144       numextrabits_d = DISTANCEEXTRA[code_d];
01145       if(*bp >= inbitlength) ERROR_BREAK(51); /*error, bit pointer will jump past memory*/
01146 
01147       distance += readBitsFromStream(bp, in, numextrabits_d);
01148 
01149       /*part 5: fill in all the out[n] values based on the length and dist*/
01150       start = (*pos);
01151       if(distance > start) ERROR_BREAK(52); /*too long backward distance*/
01152       backward = start - distance;
01153       if((*pos) + length >= out->size)
01154       {
01155         /*reserve more room at once*/
01156         if(!ucvector_resize(out, ((*pos) + length) * 2)) ERROR_BREAK(83 /*alloc fail*/);
01157       }
01158 
01159       for(forward = 0; forward < length; forward++)
01160       {
01161         out->data[(*pos)] = out->data[backward];
01162         (*pos)++;
01163         backward++;
01164         if(backward >= start) backward = start - distance;
01165       }
01166     }
01167     else if(code_ll == 256)
01168     {
01169       break; /*end code, break the loop*/
01170     }
01171     else /*if(code == (unsigned)(-1))*/ /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
01172     {
01173       /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
01174       (10=no endcode, 11=wrong jump outside of tree)*/
01175       error = (*bp) > inlength * 8 ? 10 : 11;
01176       break;
01177     }
01178   }
01179 
01180   HuffmanTree_cleanup(&tree_ll);
01181   HuffmanTree_cleanup(&tree_d);
01182 
01183   return error;
01184 }
01185 
01186 static unsigned inflateNoCompression(ucvector* out, const unsigned char* in, size_t* bp, size_t* pos, size_t inlength)
01187 {
01188   /*go to first boundary of byte*/
01189   size_t p;
01190   unsigned LEN, NLEN, n, error = 0;
01191   while(((*bp) & 0x7) != 0) (*bp)++;
01192   p = (*bp) / 8; /*byte position*/
01193 
01194   /*read LEN (2 bytes) and NLEN (2 bytes)*/
01195   if(p >= inlength - 4) return 52; /*error, bit pointer will jump past memory*/
01196   LEN = in[p] + 256 * in[p + 1]; p += 2;
01197   NLEN = in[p] + 256 * in[p + 1]; p += 2;
01198 
01199   /*check if 16-bit NLEN is really the one's complement of LEN*/
01200   if(LEN + NLEN != 65535) return 21; /*error: NLEN is not one's complement of LEN*/
01201 
01202   if((*pos) + LEN >= out->size)
01203   {
01204     if(!ucvector_resize(out, (*pos) + LEN)) return 83; /*alloc fail*/
01205   }
01206 
01207   /*read the literal data: LEN bytes are now stored in the out buffer*/
01208   if(p + LEN > inlength) return 23; /*error: reading outside of in buffer*/
01209   for(n = 0; n < LEN; n++) out->data[(*pos)++] = in[p++];
01210 
01211   (*bp) = p * 8;
01212 
01213   return error;
01214 }
01215 
01216 static unsigned lodepng_inflatev(ucvector* out,
01217                                  const unsigned char* in, size_t insize,
01218                                  const LodePNGDecompressSettings* settings)
01219 {
01220   /*bit pointer in the "in" data, current byte is bp >> 3, current bit is bp & 0x7 (from lsb to msb of the byte)*/
01221   size_t bp = 0;
01222   unsigned BFINAL = 0;
01223   size_t pos = 0; /*byte position in the out buffer*/
01224 
01225   unsigned error = 0;
01226 
01227   (void)settings;
01228 
01229   while(!BFINAL)
01230   {
01231     unsigned BTYPE;
01232     if(bp + 2 >= insize * 8) return 52; /*error, bit pointer will jump past memory*/
01233     BFINAL = readBitFromStream(&bp, in);
01234     BTYPE = 1 * readBitFromStream(&bp, in);
01235     BTYPE += 2 * readBitFromStream(&bp, in);
01236 
01237     if(BTYPE == 3) return 20; /*error: invalid BTYPE*/
01238     else if(BTYPE == 0) error = inflateNoCompression(out, in, &bp, &pos, insize); /*no compression*/
01239     else error = inflateHuffmanBlock(out, in, &bp, &pos, insize, BTYPE); /*compression, BTYPE 01 or 10*/
01240 
01241     if(error) return error;
01242   }
01243 
01244   /*Only now we know the true size of out, resize it to that*/
01245   if(!ucvector_resize(out, pos)) error = 83; /*alloc fail*/
01246 
01247   return error;
01248 }
01249 
01250 unsigned lodepng_inflate(unsigned char** out, size_t* outsize,
01251                          const unsigned char* in, size_t insize,
01252                          const LodePNGDecompressSettings* settings)
01253 {
01254   unsigned error;
01255   ucvector v;
01256   ucvector_init_buffer(&v, *out, *outsize);
01257   error = lodepng_inflatev(&v, in, insize, settings);
01258   *out = v.data;
01259   *outsize = v.size;
01260   return error;
01261 }
01262 
01263 static unsigned inflate(unsigned char** out, size_t* outsize,
01264                         const unsigned char* in, size_t insize,
01265                         const LodePNGDecompressSettings* settings)
01266 {
01267   if(settings->custom_inflate)
01268   {
01269     return settings->custom_inflate(out, outsize, in, insize, settings);
01270   }
01271   else
01272   {
01273     return lodepng_inflate(out, outsize, in, insize, settings);
01274   }
01275 }
01276 
01277 #endif /*LODEPNG_COMPILE_DECODER*/
01278 
01279 #ifdef LODEPNG_COMPILE_ENCODER
01280 
01281 /* ////////////////////////////////////////////////////////////////////////// */
01282 /* / Deflator (Compressor)                                                  / */
01283 /* ////////////////////////////////////////////////////////////////////////// */
01284 
01285 static const size_t MAX_SUPPORTED_DEFLATE_LENGTH = 258;
01286 
01287 /*bitlen is the size in bits of the code*/
01288 static void addHuffmanSymbol(size_t* bp, ucvector* compressed, unsigned code, unsigned bitlen)
01289 {
01290   addBitsToStreamReversed(bp, compressed, code, bitlen);
01291 }
01292 
01293 /*search the index in the array, that has the largest value smaller than or equal to the given value,
01294 given array must be sorted (if no value is smaller, it returns the size of the given array)*/
01295 static size_t searchCodeIndex(const unsigned* array, size_t array_size, size_t value)
01296 {
01297   /*linear search implementation*/
01298   /*for(size_t i = 1; i < array_size; i++) if(array[i] > value) return i - 1;
01299   return array_size - 1;*/
01300 
01301   /*binary search implementation (not that much faster) (precondition: array_size > 0)*/
01302   size_t left  = 1;
01303   size_t right = array_size - 1;
01304   while(left <= right)
01305   {
01306     size_t mid = (left + right) / 2;
01307     if(array[mid] <= value) left = mid + 1; /*the value to find is more to the right*/
01308     else if(array[mid - 1] > value) right = mid - 1; /*the value to find is more to the left*/
01309     else return mid - 1;
01310   }
01311   return array_size - 1;
01312 }
01313 
01314 static void addLengthDistance(uivector* values, size_t length, size_t distance)
01315 {
01316   /*values in encoded vector are those used by deflate:
01317   0-255: literal bytes
01318   256: end
01319   257-285: length/distance pair (length code, followed by extra length bits, distance code, extra distance bits)
01320   286-287: invalid*/
01321 
01322   unsigned length_code = (unsigned)searchCodeIndex(LENGTHBASE, 29, length);
01323   unsigned extra_length = (unsigned)(length - LENGTHBASE[length_code]);
01324   unsigned dist_code = (unsigned)searchCodeIndex(DISTANCEBASE, 30, distance);
01325   unsigned extra_distance = (unsigned)(distance - DISTANCEBASE[dist_code]);
01326 
01327   uivector_push_back(values, length_code + FIRST_LENGTH_CODE_INDEX);
01328   uivector_push_back(values, extra_length);
01329   uivector_push_back(values, dist_code);
01330   uivector_push_back(values, extra_distance);
01331 }
01332 
01333 static const unsigned HASH_BIT_MASK = 65535;
01334 static const unsigned HASH_NUM_VALUES = 65536;
01335 static const unsigned HASH_NUM_CHARACTERS = 3;
01336 static const unsigned HASH_SHIFT = 2;
01337 /*
01338 The HASH_NUM_CHARACTERS value is used to make encoding faster by using longer
01339 sequences to generate a hash value from the stream bytes. Setting it to 3
01340 gives exactly the same compression as the brute force method, since deflate's
01341 run length encoding starts with lengths of 3. Setting it to higher values,
01342 like 6, can make the encoding faster (not always though!), but will cause the
01343 encoding to miss any length between 3 and this value, so that the compression
01344 may be worse (but this can vary too depending on the image, sometimes it is
01345 even a bit better instead).
01346 The HASH_NUM_VALUES is the amount of unique possible hash values that
01347 combinations of bytes can give, the higher it is the more memory is needed, but
01348 if it's too low the advantage of hashing is gone.
01349 */
01350 
01351 typedef struct Hash
01352 {
01353   int* head; /*hash value to head circular pos*/
01354   int* val; /*circular pos to hash value*/
01355   /*circular pos to prev circular pos*/
01356   unsigned short* chain;
01357   unsigned short* zeros;
01358 } Hash;
01359 
01360 static unsigned hash_init(Hash* hash, unsigned windowsize)
01361 {
01362   unsigned i;
01363   hash->head = (int*)lodepng_malloc(sizeof(int) * HASH_NUM_VALUES);
01364   hash->val = (int*)lodepng_malloc(sizeof(int) * windowsize);
01365   hash->chain = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
01366   hash->zeros = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
01367 
01368   if(!hash->head || !hash->val || !hash->chain || !hash->zeros) return 83; /*alloc fail*/
01369 
01370   /*initialize hash table*/
01371   for(i = 0; i < HASH_NUM_VALUES; i++) hash->head[i] = -1;
01372   for(i = 0; i < windowsize; i++) hash->val[i] = -1;
01373   for(i = 0; i < windowsize; i++) hash->chain[i] = i; /*same value as index indicates uninitialized*/
01374 
01375   return 0;
01376 }
01377 
01378 static void hash_cleanup(Hash* hash)
01379 {
01380   lodepng_free(hash->head);
01381   lodepng_free(hash->val);
01382   lodepng_free(hash->chain);
01383   lodepng_free(hash->zeros);
01384 }
01385 
01386 static unsigned getHash(const unsigned char* data, size_t size, size_t pos)
01387 {
01388   unsigned result = 0;
01389   if (HASH_NUM_CHARACTERS == 3 && pos + 2 < size) {
01390     result ^= (data[pos + 0] << (0 * HASH_SHIFT));
01391     result ^= (data[pos + 1] << (1 * HASH_SHIFT));
01392     result ^= (data[pos + 2] << (2 * HASH_SHIFT));
01393   } else {
01394     size_t amount, i;
01395     if(pos >= size) return 0;
01396     amount = HASH_NUM_CHARACTERS;
01397     if(pos + amount >= size) amount = size - pos;
01398     for(i = 0; i < amount; i++) result ^= (data[pos + i] << (i * HASH_SHIFT));
01399   }
01400   return result & HASH_BIT_MASK;
01401 }
01402 
01403 static unsigned countZeros(const unsigned char* data, size_t size, size_t pos)
01404 {
01405   const unsigned char* start = data + pos;
01406   const unsigned char* end = start + MAX_SUPPORTED_DEFLATE_LENGTH;
01407   if(end > data + size) end = data + size;
01408   data = start;
01409   while (data != end && *data == 0) data++;
01410   /*subtracting two addresses returned as 32-bit number (max value is MAX_SUPPORTED_DEFLATE_LENGTH)*/
01411   return (unsigned)(data - start);
01412 }
01413 
01414 /*wpos = pos & (windowsize - 1)*/
01415 static void updateHashChain(Hash* hash, size_t wpos, int hashval)
01416 {
01417   hash->val[wpos] = hashval;
01418   if(hash->head[hashval] != -1) hash->chain[wpos] = hash->head[hashval];
01419   hash->head[hashval] = wpos;
01420 }
01421 
01422 /*
01423 LZ77-encode the data. Return value is error code. The input are raw bytes, the output
01424 is in the form of unsigned integers with codes representing for example literal bytes, or
01425 length/distance pairs.
01426 It uses a hash table technique to let it encode faster. When doing LZ77 encoding, a
01427 sliding window (of windowsize) is used, and all past bytes in that window can be used as
01428 the "dictionary". A brute force search through all possible distances would be slow, and
01429 this hash technique is one out of several ways to speed this up.
01430 */
01431 static unsigned encodeLZ77(uivector* out, Hash* hash,
01432                            const unsigned char* in, size_t inpos, size_t insize, unsigned windowsize,
01433                            unsigned minmatch, unsigned nicematch, unsigned lazymatching)
01434 {
01435   unsigned pos, i, error = 0;
01436   /*for large window lengths, assume the user wants no compression loss. Otherwise, max hash chain length speedup.*/
01437   unsigned maxchainlength = windowsize >= 8192 ? windowsize : windowsize / 8;
01438   unsigned maxlazymatch = windowsize >= 8192 ? MAX_SUPPORTED_DEFLATE_LENGTH : 64;
01439 
01440   unsigned usezeros = 1; /*not sure if setting it to false for windowsize < 8192 is better or worse*/
01441   unsigned numzeros = 0;
01442 
01443   unsigned offset; /*the offset represents the distance in LZ77 terminology*/
01444   unsigned length;
01445   unsigned lazy = 0;
01446   unsigned lazylength = 0, lazyoffset = 0;
01447   unsigned hashval;
01448   unsigned current_offset, current_length;
01449   const unsigned char *lastptr, *foreptr, *backptr;
01450   unsigned hashpos, prevpos;
01451 
01452   if(windowsize <= 0 || windowsize > 32768) return 60; /*error: windowsize smaller/larger than allowed*/
01453   if((windowsize & (windowsize - 1)) != 0) return 90; /*error: must be power of two*/
01454 
01455   if(nicematch > MAX_SUPPORTED_DEFLATE_LENGTH) nicematch = MAX_SUPPORTED_DEFLATE_LENGTH;
01456 
01457   for(pos = inpos; pos < insize; pos++)
01458   {
01459     size_t wpos = pos & (windowsize - 1); /*position for in 'circular' hash buffers*/
01460     unsigned chainlength = 0;
01461 
01462     hashval = getHash(in, insize, pos);
01463     updateHashChain(hash, wpos, hashval);
01464 
01465     if(usezeros && hashval == 0)
01466     {
01467       if (numzeros == 0) numzeros = countZeros(in, insize, pos);
01468       else if (pos + numzeros >= insize || in[pos + numzeros - 1] != 0) numzeros--;
01469       hash->zeros[wpos] = numzeros;
01470     }
01471     else
01472     {
01473       numzeros = 0;
01474     }
01475 
01476     /*the length and offset found for the current position*/
01477     length = 0;
01478     offset = 0;
01479 
01480     prevpos = hash->head[hashval];
01481     hashpos = hash->chain[prevpos];
01482 
01483     lastptr = &in[insize < pos + MAX_SUPPORTED_DEFLATE_LENGTH ? insize : pos + MAX_SUPPORTED_DEFLATE_LENGTH];
01484 
01485     /*search for the longest string*/
01486     for(;;)
01487     {
01488       /*stop when went completely around the circular buffer*/
01489       if(prevpos < wpos && hashpos > prevpos && hashpos <= wpos) break;
01490       if(prevpos > wpos && (hashpos <= wpos || hashpos > prevpos)) break;
01491       if(chainlength++ >= maxchainlength) break;
01492 
01493       current_offset = hashpos <= wpos ? wpos - hashpos : wpos - hashpos + windowsize;
01494       if(current_offset > 0)
01495       {
01496         /*test the next characters*/
01497         foreptr = &in[pos];
01498         backptr = &in[pos - current_offset];
01499 
01500         /*common case in PNGs is lots of zeros. Quickly skip over them as a speedup*/
01501         if(usezeros && hashval == 0 && hash->val[hashpos] == 0 /*hashval[hashpos] may be out of date*/)
01502         {
01503           unsigned skip = hash->zeros[hashpos];
01504           if(skip > numzeros) skip = numzeros;
01505           backptr += skip;
01506           foreptr += skip;
01507         }
01508 
01509         while(foreptr != lastptr && *backptr == *foreptr) /*maximum supported length by deflate is max length*/
01510         {
01511           ++backptr;
01512           ++foreptr;
01513         }
01514         current_length = (unsigned)(foreptr - &in[pos]);
01515 
01516         if(current_length > length)
01517         {
01518           length = current_length; /*the longest length*/
01519           offset = current_offset; /*the offset that is related to this longest length*/
01520           /*jump out once a length of max length is found (speed gain). This also jumps
01521           out if length is MAX_SUPPORTED_DEFLATE_LENGTH*/
01522           if(current_length >= nicematch) break;
01523         }
01524       }
01525 
01526       if(hashpos == hash->chain[hashpos]) break;
01527 
01528       prevpos = hashpos;
01529       hashpos = hash->chain[hashpos];
01530     }
01531 
01532     if(lazymatching)
01533     {
01534       if(!lazy && length >= 3 && length <= maxlazymatch && length < MAX_SUPPORTED_DEFLATE_LENGTH)
01535       {
01536         lazy = 1;
01537         lazylength = length;
01538         lazyoffset = offset;
01539         continue; /*try the next byte*/
01540       }
01541       if(lazy)
01542       {
01543         lazy = 0;
01544         if(pos == 0) ERROR_BREAK(81);
01545         if(length > lazylength + 1)
01546         {
01547           /*push the previous character as literal*/
01548           if(!uivector_push_back(out, in[pos - 1])) ERROR_BREAK(83 /*alloc fail*/);
01549         }
01550         else
01551         {
01552           length = lazylength;
01553           offset = lazyoffset;
01554           hash->head[hashval] = -1; /*the same hashchain update will be done, this ensures no wrong alteration*/
01555           pos--;
01556         }
01557       }
01558     }
01559     if(length >= 3 && offset > windowsize) ERROR_BREAK(86 /*too big (or overflown negative) offset*/);
01560 
01561     /*encode it as length/distance pair or literal value*/
01562     if(length < 3) /*only lengths of 3 or higher are supported as length/distance pair*/
01563     {
01564       if(!uivector_push_back(out, in[pos])) ERROR_BREAK(83 /*alloc fail*/);
01565     }
01566     else if(length < minmatch || (length == 3 && offset > 4096))
01567     {
01568       /*compensate for the fact that longer offsets have more extra bits, a
01569       length of only 3 may be not worth it then*/
01570       if(!uivector_push_back(out, in[pos])) ERROR_BREAK(83 /*alloc fail*/);
01571     }
01572     else
01573     {
01574       addLengthDistance(out, length, offset);
01575       for(i = 1; i < length; i++)
01576       {
01577         pos++;
01578         wpos = pos & (windowsize - 1);
01579         hashval = getHash(in, insize, pos);
01580         updateHashChain(hash, wpos, hashval);
01581         if(usezeros && hashval == 0)
01582         {
01583           if (numzeros == 0) numzeros = countZeros(in, insize, pos);
01584           else if (pos + numzeros >= insize || in[pos + numzeros - 1] != 0) numzeros--;
01585           hash->zeros[wpos] = numzeros;
01586         }
01587         else
01588         {
01589           numzeros = 0;
01590         }
01591       }
01592     }
01593   } /*end of the loop through each character of input*/
01594 
01595   return error;
01596 }
01597 
01598 /* /////////////////////////////////////////////////////////////////////////// */
01599 
01600 static unsigned deflateNoCompression(ucvector* out, const unsigned char* data, size_t datasize)
01601 {
01602   /*non compressed deflate block data: 1 bit BFINAL,2 bits BTYPE,(5 bits): it jumps to start of next byte,
01603   2 bytes LEN, 2 bytes NLEN, LEN bytes literal DATA*/
01604 
01605   size_t i, j, numdeflateblocks = (datasize + 65534) / 65535;
01606   unsigned datapos = 0;
01607   for(i = 0; i < numdeflateblocks; i++)
01608   {
01609     unsigned BFINAL, BTYPE, LEN, NLEN;
01610     unsigned char firstbyte;
01611 
01612     BFINAL = (i == numdeflateblocks - 1);
01613     BTYPE = 0;
01614 
01615     firstbyte = (unsigned char)(BFINAL + ((BTYPE & 1) << 1) + ((BTYPE & 2) << 1));
01616     ucvector_push_back(out, firstbyte);
01617 
01618     LEN = 65535;
01619     if(datasize - datapos < 65535) LEN = (unsigned)datasize - datapos;
01620     NLEN = 65535 - LEN;
01621 
01622     ucvector_push_back(out, (unsigned char)(LEN % 256));
01623     ucvector_push_back(out, (unsigned char)(LEN / 256));
01624     ucvector_push_back(out, (unsigned char)(NLEN % 256));
01625     ucvector_push_back(out, (unsigned char)(NLEN / 256));
01626 
01627     /*Decompressed data*/
01628     for(j = 0; j < 65535 && datapos < datasize; j++)
01629     {
01630       ucvector_push_back(out, data[datapos++]);
01631     }
01632   }
01633 
01634   return 0;
01635 }
01636 
01637 /*
01638 write the lz77-encoded data, which has lit, len and dist codes, to compressed stream using huffman trees.
01639 tree_ll: the tree for lit and len codes.
01640 tree_d: the tree for distance codes.
01641 */
01642 static void writeLZ77data(size_t* bp, ucvector* out, const uivector* lz77_encoded,
01643                           const HuffmanTree* tree_ll, const HuffmanTree* tree_d)
01644 {
01645   size_t i = 0;
01646   for(i = 0; i < lz77_encoded->size; i++)
01647   {
01648     unsigned val = lz77_encoded->data[i];
01649     addHuffmanSymbol(bp, out, HuffmanTree_getCode(tree_ll, val), HuffmanTree_getLength(tree_ll, val));
01650     if(val > 256) /*for a length code, 3 more things have to be added*/
01651     {
01652       unsigned length_index = val - FIRST_LENGTH_CODE_INDEX;
01653       unsigned n_length_extra_bits = LENGTHEXTRA[length_index];
01654       unsigned length_extra_bits = lz77_encoded->data[++i];
01655 
01656       unsigned distance_code = lz77_encoded->data[++i];
01657 
01658       unsigned distance_index = distance_code;
01659       unsigned n_distance_extra_bits = DISTANCEEXTRA[distance_index];
01660       unsigned distance_extra_bits = lz77_encoded->data[++i];
01661 
01662       addBitsToStream(bp, out, length_extra_bits, n_length_extra_bits);
01663       addHuffmanSymbol(bp, out, HuffmanTree_getCode(tree_d, distance_code),
01664                        HuffmanTree_getLength(tree_d, distance_code));
01665       addBitsToStream(bp, out, distance_extra_bits, n_distance_extra_bits);
01666     }
01667   }
01668 }
01669 
01670 /*Deflate for a block of type "dynamic", that is, with freely, optimally, created huffman trees*/
01671 static unsigned deflateDynamic(ucvector* out, size_t* bp, Hash* hash,
01672                                const unsigned char* data, size_t datapos, size_t dataend,
01673                                const LodePNGCompressSettings* settings, int final)
01674 {
01675   unsigned error = 0;
01676 
01677   /*
01678   A block is compressed as follows: The PNG data is lz77 encoded, resulting in
01679   literal bytes and length/distance pairs. This is then huffman compressed with
01680   two huffman trees. One huffman tree is used for the lit and len values ("ll"),
01681   another huffman tree is used for the dist values ("d"). These two trees are
01682   stored using their code lengths, and to compress even more these code lengths
01683   are also run-length encoded and huffman compressed. This gives a huffman tree
01684   of code lengths "cl". The code lenghts used to describe this third tree are
01685   the code length code lengths ("clcl").
01686   */
01687 
01688   /*The lz77 encoded data, represented with integers since there will also be length and distance codes in it*/
01689   uivector lz77_encoded;
01690   HuffmanTree tree_ll; /*tree for lit,len values*/
01691   HuffmanTree tree_d; /*tree for distance codes*/
01692   HuffmanTree tree_cl; /*tree for encoding the code lengths representing tree_ll and tree_d*/
01693   uivector frequencies_ll; /*frequency of lit,len codes*/
01694   uivector frequencies_d; /*frequency of dist codes*/
01695   uivector frequencies_cl; /*frequency of code length codes*/
01696   uivector bitlen_lld; /*lit,len,dist code lenghts (int bits), literally (without repeat codes).*/
01697   uivector bitlen_lld_e; /*bitlen_lld encoded with repeat codes (this is a rudemtary run length compression)*/
01698   /*bitlen_cl is the code length code lengths ("clcl"). The bit lengths of codes to represent tree_cl
01699   (these are written as is in the file, it would be crazy to compress these using yet another huffman
01700   tree that needs to be represented by yet another set of code lengths)*/
01701   uivector bitlen_cl;
01702   size_t datasize = dataend - datapos;
01703 
01704   /*
01705   Due to the huffman compression of huffman tree representations ("two levels"), there are some anologies:
01706   bitlen_lld is to tree_cl what data is to tree_ll and tree_d.
01707   bitlen_lld_e is to bitlen_lld what lz77_encoded is to data.
01708   bitlen_cl is to bitlen_lld_e what bitlen_lld is to lz77_encoded.
01709   */
01710 
01711   unsigned BFINAL = final;
01712   size_t numcodes_ll, numcodes_d, i;
01713   unsigned HLIT, HDIST, HCLEN;
01714 
01715   uivector_init(&lz77_encoded);
01716   HuffmanTree_init(&tree_ll);
01717   HuffmanTree_init(&tree_d);
01718   HuffmanTree_init(&tree_cl);
01719   uivector_init(&frequencies_ll);
01720   uivector_init(&frequencies_d);
01721   uivector_init(&frequencies_cl);
01722   uivector_init(&bitlen_lld);
01723   uivector_init(&bitlen_lld_e);
01724   uivector_init(&bitlen_cl);
01725 
01726   /*This while loop never loops due to a break at the end, it is here to
01727   allow breaking out of it to the cleanup phase on error conditions.*/
01728   while(!error)
01729   {
01730     if(settings->use_lz77)
01731     {
01732       error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize,
01733                          settings->minmatch, settings->nicematch, settings->lazymatching);
01734       if(error) break;
01735     }
01736     else
01737     {
01738       if(!uivector_resize(&lz77_encoded, datasize)) ERROR_BREAK(83 /*alloc fail*/);
01739       for(i = datapos; i < dataend; i++) lz77_encoded.data[i] = data[i]; /*no LZ77, but still will be Huffman compressed*/
01740     }
01741 
01742     if(!uivector_resizev(&frequencies_ll, 286, 0)) ERROR_BREAK(83 /*alloc fail*/);
01743     if(!uivector_resizev(&frequencies_d, 30, 0)) ERROR_BREAK(83 /*alloc fail*/);
01744 
01745     /*Count the frequencies of lit, len and dist codes*/
01746     for(i = 0; i < lz77_encoded.size; i++)
01747     {
01748       unsigned symbol = lz77_encoded.data[i];
01749       frequencies_ll.data[symbol]++;
01750       if(symbol > 256)
01751       {
01752         unsigned dist = lz77_encoded.data[i + 2];
01753         frequencies_d.data[dist]++;
01754         i += 3;
01755       }
01756     }
01757     frequencies_ll.data[256] = 1; /*there will be exactly 1 end code, at the end of the block*/
01758 
01759     /*Make both huffman trees, one for the lit and len codes, one for the dist codes*/
01760     error = HuffmanTree_makeFromFrequencies(&tree_ll, frequencies_ll.data, 257, frequencies_ll.size, 15);
01761     if(error) break;
01762     /*2, not 1, is chosen for mincodes: some buggy PNG decoders require at least 2 symbols in the dist tree*/
01763     error = HuffmanTree_makeFromFrequencies(&tree_d, frequencies_d.data, 2, frequencies_d.size, 15);
01764     if(error) break;
01765 
01766     numcodes_ll = tree_ll.numcodes; if(numcodes_ll > 286) numcodes_ll = 286;
01767     numcodes_d = tree_d.numcodes; if(numcodes_d > 30) numcodes_d = 30;
01768     /*store the code lengths of both generated trees in bitlen_lld*/
01769     for(i = 0; i < numcodes_ll; i++) uivector_push_back(&bitlen_lld, HuffmanTree_getLength(&tree_ll, (unsigned)i));
01770     for(i = 0; i < numcodes_d; i++) uivector_push_back(&bitlen_lld, HuffmanTree_getLength(&tree_d, (unsigned)i));
01771 
01772     /*run-length compress bitlen_ldd into bitlen_lld_e by using repeat codes 16 (copy length 3-6 times),
01773     17 (3-10 zeroes), 18 (11-138 zeroes)*/
01774     for(i = 0; i < (unsigned)bitlen_lld.size; i++)
01775     {
01776       unsigned j = 0; /*amount of repititions*/
01777       while(i + j + 1 < (unsigned)bitlen_lld.size && bitlen_lld.data[i + j + 1] == bitlen_lld.data[i]) j++;
01778 
01779       if(bitlen_lld.data[i] == 0 && j >= 2) /*repeat code for zeroes*/
01780       {
01781         j++; /*include the first zero*/
01782         if(j <= 10) /*repeat code 17 supports max 10 zeroes*/
01783         {
01784           uivector_push_back(&bitlen_lld_e, 17);
01785           uivector_push_back(&bitlen_lld_e, j - 3);
01786         }
01787         else /*repeat code 18 supports max 138 zeroes*/
01788         {
01789           if(j > 138) j = 138;
01790           uivector_push_back(&bitlen_lld_e, 18);
01791           uivector_push_back(&bitlen_lld_e, j - 11);
01792         }
01793         i += (j - 1);
01794       }
01795       else if(j >= 3) /*repeat code for value other than zero*/
01796       {
01797         size_t k;
01798         unsigned num = j / 6, rest = j % 6;
01799         uivector_push_back(&bitlen_lld_e, bitlen_lld.data[i]);
01800         for(k = 0; k < num; k++)
01801         {
01802           uivector_push_back(&bitlen_lld_e, 16);
01803           uivector_push_back(&bitlen_lld_e, 6 - 3);
01804         }
01805         if(rest >= 3)
01806         {
01807           uivector_push_back(&bitlen_lld_e, 16);
01808           uivector_push_back(&bitlen_lld_e, rest - 3);
01809         }
01810         else j -= rest;
01811         i += j;
01812       }
01813       else /*too short to benefit from repeat code*/
01814       {
01815         uivector_push_back(&bitlen_lld_e, bitlen_lld.data[i]);
01816       }
01817     }
01818 
01819     /*generate tree_cl, the huffmantree of huffmantrees*/
01820 
01821     if(!uivector_resizev(&frequencies_cl, NUM_CODE_LENGTH_CODES, 0)) ERROR_BREAK(83 /*alloc fail*/);
01822     for(i = 0; i < bitlen_lld_e.size; i++)
01823     {
01824       frequencies_cl.data[bitlen_lld_e.data[i]]++;
01825       /*after a repeat code come the bits that specify the number of repetitions,
01826       those don't need to be in the frequencies_cl calculation*/
01827       if(bitlen_lld_e.data[i] >= 16) i++;
01828     }
01829 
01830     error = HuffmanTree_makeFromFrequencies(&tree_cl, frequencies_cl.data,
01831                                             frequencies_cl.size, frequencies_cl.size, 7);
01832     if(error) break;
01833 
01834     if(!uivector_resize(&bitlen_cl, tree_cl.numcodes)) ERROR_BREAK(83 /*alloc fail*/);
01835     for(i = 0; i < tree_cl.numcodes; i++)
01836     {
01837       /*lenghts of code length tree is in the order as specified by deflate*/
01838       bitlen_cl.data[i] = HuffmanTree_getLength(&tree_cl, CLCL_ORDER[i]);
01839     }
01840     while(bitlen_cl.data[bitlen_cl.size - 1] == 0 && bitlen_cl.size > 4)
01841     {
01842       /*remove zeros at the end, but minimum size must be 4*/
01843       if(!uivector_resize(&bitlen_cl, bitlen_cl.size - 1)) ERROR_BREAK(83 /*alloc fail*/);
01844     }
01845     if(error) break;
01846 
01847     /*
01848     Write everything into the output
01849 
01850     After the BFINAL and BTYPE, the dynamic block consists out of the following:
01851     - 5 bits HLIT, 5 bits HDIST, 4 bits HCLEN
01852     - (HCLEN+4)*3 bits code lengths of code length alphabet
01853     - HLIT + 257 code lenghts of lit/length alphabet (encoded using the code length
01854       alphabet, + possible repetition codes 16, 17, 18)
01855     - HDIST + 1 code lengths of distance alphabet (encoded using the code length
01856       alphabet, + possible repetition codes 16, 17, 18)
01857     - compressed data
01858     - 256 (end code)
01859     */
01860 
01861     /*Write block type*/
01862     addBitToStream(bp, out, BFINAL);
01863     addBitToStream(bp, out, 0); /*first bit of BTYPE "dynamic"*/
01864     addBitToStream(bp, out, 1); /*second bit of BTYPE "dynamic"*/
01865 
01866     /*write the HLIT, HDIST and HCLEN values*/
01867     HLIT = (unsigned)(numcodes_ll - 257);
01868     HDIST = (unsigned)(numcodes_d - 1);
01869     HCLEN = (unsigned)bitlen_cl.size - 4;
01870     /*trim zeroes for HCLEN. HLIT and HDIST were already trimmed at tree creation*/
01871     while(!bitlen_cl.data[HCLEN + 4 - 1] && HCLEN > 0) HCLEN--;
01872     addBitsToStream(bp, out, HLIT, 5);
01873     addBitsToStream(bp, out, HDIST, 5);
01874     addBitsToStream(bp, out, HCLEN, 4);
01875 
01876     /*write the code lenghts of the code length alphabet*/
01877     for(i = 0; i < HCLEN + 4; i++) addBitsToStream(bp, out, bitlen_cl.data[i], 3);
01878 
01879     /*write the lenghts of the lit/len AND the dist alphabet*/
01880     for(i = 0; i < bitlen_lld_e.size; i++)
01881     {
01882       addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_cl, bitlen_lld_e.data[i]),
01883                        HuffmanTree_getLength(&tree_cl, bitlen_lld_e.data[i]));
01884       /*extra bits of repeat codes*/
01885       if(bitlen_lld_e.data[i] == 16) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 2);
01886       else if(bitlen_lld_e.data[i] == 17) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 3);
01887       else if(bitlen_lld_e.data[i] == 18) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 7);
01888     }
01889 
01890     /*write the compressed data symbols*/
01891     writeLZ77data(bp, out, &lz77_encoded, &tree_ll, &tree_d);
01892     /*error: the length of the end code 256 must be larger than 0*/
01893     if(HuffmanTree_getLength(&tree_ll, 256) == 0) ERROR_BREAK(64);
01894 
01895     /*write the end code*/
01896     addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, 256), HuffmanTree_getLength(&tree_ll, 256));
01897 
01898     break; /*end of error-while*/
01899   }
01900 
01901   /*cleanup*/
01902   uivector_cleanup(&lz77_encoded);
01903   HuffmanTree_cleanup(&tree_ll);
01904   HuffmanTree_cleanup(&tree_d);
01905   HuffmanTree_cleanup(&tree_cl);
01906   uivector_cleanup(&frequencies_ll);
01907   uivector_cleanup(&frequencies_d);
01908   uivector_cleanup(&frequencies_cl);
01909   uivector_cleanup(&bitlen_lld_e);
01910   uivector_cleanup(&bitlen_lld);
01911   uivector_cleanup(&bitlen_cl);
01912 
01913   return error;
01914 }
01915 
01916 static unsigned deflateFixed(ucvector* out, size_t* bp, Hash* hash,
01917                              const unsigned char* data,
01918                              size_t datapos, size_t dataend,
01919                              const LodePNGCompressSettings* settings, int final)
01920 {
01921   HuffmanTree tree_ll; /*tree for literal values and length codes*/
01922   HuffmanTree tree_d; /*tree for distance codes*/
01923 
01924   unsigned BFINAL = final;
01925   unsigned error = 0;
01926   size_t i;
01927 
01928   HuffmanTree_init(&tree_ll);
01929   HuffmanTree_init(&tree_d);
01930 
01931   generateFixedLitLenTree(&tree_ll);
01932   generateFixedDistanceTree(&tree_d);
01933 
01934   addBitToStream(bp, out, BFINAL);
01935   addBitToStream(bp, out, 1); /*first bit of BTYPE*/
01936   addBitToStream(bp, out, 0); /*second bit of BTYPE*/
01937 
01938   if(settings->use_lz77) /*LZ77 encoded*/
01939   {
01940     uivector lz77_encoded;
01941     uivector_init(&lz77_encoded);
01942     error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize,
01943                        settings->minmatch, settings->nicematch, settings->lazymatching);
01944     if(!error) writeLZ77data(bp, out, &lz77_encoded, &tree_ll, &tree_d);
01945     uivector_cleanup(&lz77_encoded);
01946   }
01947   else /*no LZ77, but still will be Huffman compressed*/
01948   {
01949     for(i = datapos; i < dataend; i++)
01950     {
01951       addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, data[i]), HuffmanTree_getLength(&tree_ll, data[i]));
01952     }
01953   }
01954   /*add END code*/
01955   if(!error) addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, 256), HuffmanTree_getLength(&tree_ll, 256));
01956 
01957   /*cleanup*/
01958   HuffmanTree_cleanup(&tree_ll);
01959   HuffmanTree_cleanup(&tree_d);
01960 
01961   return error;
01962 }
01963 
01964 static unsigned lodepng_deflatev(ucvector* out, const unsigned char* in, size_t insize,
01965                                  const LodePNGCompressSettings* settings)
01966 {
01967   unsigned error = 0;
01968   size_t i, blocksize, numdeflateblocks;
01969   size_t bp = 0; /*the bit pointer*/
01970   Hash hash;
01971 
01972   if(settings->btype > 2) return 61;
01973   else if(settings->btype == 0) return deflateNoCompression(out, in, insize);
01974   else if(settings->btype == 1) blocksize = insize;
01975   else /*if(settings->btype == 2)*/
01976   {
01977     blocksize = insize / 8 + 8;
01978     if(blocksize < 65535) blocksize = 65535;
01979   }
01980 
01981   numdeflateblocks = (insize + blocksize - 1) / blocksize;
01982   if(numdeflateblocks == 0) numdeflateblocks = 1;
01983 
01984   error = hash_init(&hash, settings->windowsize);
01985   if(error) return error;
01986 
01987   for(i = 0; i < numdeflateblocks && !error; i++)
01988   {
01989     int final = i == numdeflateblocks - 1;
01990     size_t start = i * blocksize;
01991     size_t end = start + blocksize;
01992     if(end > insize) end = insize;
01993 
01994     if(settings->btype == 1) error = deflateFixed(out, &bp, &hash, in, start, end, settings, final);
01995     else if(settings->btype == 2) error = deflateDynamic(out, &bp, &hash, in, start, end, settings, final);
01996   }
01997 
01998   hash_cleanup(&hash);
01999 
02000   return error;
02001 }
02002 
02003 unsigned lodepng_deflate(unsigned char** out, size_t* outsize,
02004                          const unsigned char* in, size_t insize,
02005                          const LodePNGCompressSettings* settings)
02006 {
02007   unsigned error;
02008   ucvector v;
02009   ucvector_init_buffer(&v, *out, *outsize);
02010   error = lodepng_deflatev(&v, in, insize, settings);
02011   *out = v.data;
02012   *outsize = v.size;
02013   return error;
02014 }
02015 
02016 static unsigned deflate(unsigned char** out, size_t* outsize,
02017                         const unsigned char* in, size_t insize,
02018                         const LodePNGCompressSettings* settings)
02019 {
02020   if(settings->custom_deflate)
02021   {
02022     return settings->custom_deflate(out, outsize, in, insize, settings);
02023   }
02024   else
02025   {
02026     return lodepng_deflate(out, outsize, in, insize, settings);
02027   }
02028 }
02029 
02030 #endif /*LODEPNG_COMPILE_DECODER*/
02031 
02032 /* ////////////////////////////////////////////////////////////////////////// */
02033 /* / Adler32                                                                  */
02034 /* ////////////////////////////////////////////////////////////////////////// */
02035 
02036 static unsigned update_adler32(unsigned adler, const unsigned char* data, unsigned len)
02037 {
02038    unsigned s1 = adler & 0xffff;
02039    unsigned s2 = (adler >> 16) & 0xffff;
02040 
02041   while(len > 0)
02042   {
02043     /*at least 5550 sums can be done before the sums overflow, saving a lot of module divisions*/
02044     unsigned amount = len > 5550 ? 5550 : len;
02045     len -= amount;
02046     while(amount > 0)
02047     {
02048       s1 += (*data++);
02049       s2 += s1;
02050       amount--;
02051     }
02052     s1 %= 65521;
02053     s2 %= 65521;
02054   }
02055 
02056   return (s2 << 16) | s1;
02057 }
02058 
02059 /*Return the adler32 of the bytes data[0..len-1]*/
02060 static unsigned adler32(const unsigned char* data, unsigned len)
02061 {
02062   return update_adler32(1L, data, len);
02063 }
02064 
02065 /* ////////////////////////////////////////////////////////////////////////// */
02066 /* / Zlib                                                                   / */
02067 /* ////////////////////////////////////////////////////////////////////////// */
02068 
02069 #ifdef LODEPNG_COMPILE_DECODER
02070 
02071 unsigned lodepng_zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
02072                                  size_t insize, const LodePNGDecompressSettings* settings)
02073 {
02074   unsigned error = 0;
02075   unsigned CM, CINFO, FDICT;
02076 
02077   if(insize < 2) return 53; /*error, size of zlib data too small*/
02078   /*read information from zlib header*/
02079   if((in[0] * 256 + in[1]) % 31 != 0)
02080   {
02081     /*error: 256 * in[0] + in[1] must be a multiple of 31, the FCHECK value is supposed to be made that way*/
02082     return 24;
02083   }
02084 
02085   CM = in[0] & 15;
02086   CINFO = (in[0] >> 4) & 15;
02087   /*FCHECK = in[1] & 31;*/ /*FCHECK is already tested above*/
02088   FDICT = (in[1] >> 5) & 1;
02089   /*FLEVEL = (in[1] >> 6) & 3;*/ /*FLEVEL is not used here*/
02090 
02091   if(CM != 8 || CINFO > 7)
02092   {
02093     /*error: only compression method 8: inflate with sliding window of 32k is supported by the PNG spec*/
02094     return 25;
02095   }
02096   if(FDICT != 0)
02097   {
02098     /*error: the specification of PNG says about the zlib stream:
02099       "The additional flags shall not specify a preset dictionary."*/
02100     return 26;
02101   }
02102 
02103   error = inflate(out, outsize, in + 2, insize - 2, settings);
02104   if(error) return error;
02105 
02106   if(!settings->ignore_adler32)
02107   {
02108     unsigned ADLER32 = lodepng_read32bitInt(&in[insize - 4]);
02109     unsigned checksum = adler32(*out, (unsigned)(*outsize));
02110     if(checksum != ADLER32) return 58; /*error, adler checksum not correct, data must be corrupted*/
02111   }
02112 
02113   return 0; /*no error*/
02114 }
02115 
02116 static unsigned zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
02117                                 size_t insize, const LodePNGDecompressSettings* settings)
02118 {
02119   if(settings->custom_zlib)
02120   {
02121     return settings->custom_zlib(out, outsize, in, insize, settings);
02122   }
02123   else
02124   {
02125     return lodepng_zlib_decompress(out, outsize, in, insize, settings);
02126   }
02127 }
02128 
02129 #endif /*LODEPNG_COMPILE_DECODER*/
02130 
02131 #ifdef LODEPNG_COMPILE_ENCODER
02132 
02133 unsigned lodepng_zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
02134                                size_t insize, const LodePNGCompressSettings* settings)
02135 {
02136   /*initially, *out must be NULL and outsize 0, if you just give some random *out
02137   that's pointing to a non allocated buffer, this'll crash*/
02138   ucvector outv;
02139   size_t i;
02140   unsigned error;
02141   unsigned char* deflatedata = 0;
02142   size_t deflatesize = 0;
02143 
02144   unsigned ADLER32;
02145   /*zlib data: 1 byte CMF (CM+CINFO), 1 byte FLG, deflate data, 4 byte ADLER32 checksum of the Decompressed data*/
02146   unsigned CMF = 120; /*0b01111000: CM 8, CINFO 7. With CINFO 7, any window size up to 32768 can be used.*/
02147   unsigned FLEVEL = 0;
02148   unsigned FDICT = 0;
02149   unsigned CMFFLG = 256 * CMF + FDICT * 32 + FLEVEL * 64;
02150   unsigned FCHECK = 31 - CMFFLG % 31;
02151   CMFFLG += FCHECK;
02152 
02153   /*ucvector-controlled version of the output buffer, for dynamic array*/
02154   ucvector_init_buffer(&outv, *out, *outsize);
02155 
02156   ucvector_push_back(&outv, (unsigned char)(CMFFLG / 256));
02157   ucvector_push_back(&outv, (unsigned char)(CMFFLG % 256));
02158 
02159   error = deflate(&deflatedata, &deflatesize, in, insize, settings);
02160 
02161   if(!error)
02162   {
02163     ADLER32 = adler32(in, (unsigned)insize);
02164     for(i = 0; i < deflatesize; i++) ucvector_push_back(&outv, deflatedata[i]);
02165     lodepng_free(deflatedata);
02166     lodepng_add32bitInt(&outv, ADLER32);
02167   }
02168 
02169   *out = outv.data;
02170   *outsize = outv.size;
02171 
02172   return error;
02173 }
02174 
02175 /* compress using the default or custom zlib function */
02176 static unsigned zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
02177                               size_t insize, const LodePNGCompressSettings* settings)
02178 {
02179   if(settings->custom_zlib)
02180   {
02181     return settings->custom_zlib(out, outsize, in, insize, settings);
02182   }
02183   else
02184   {
02185     return lodepng_zlib_compress(out, outsize, in, insize, settings);
02186   }
02187 }
02188 
02189 #endif /*LODEPNG_COMPILE_ENCODER*/
02190 
02191 #else /*no LODEPNG_COMPILE_ZLIB*/
02192 
02193 #ifdef LODEPNG_COMPILE_DECODER
02194 static unsigned zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
02195                                 size_t insize, const LodePNGDecompressSettings* settings)
02196 {
02197   if (!settings->custom_zlib) return 87; /*no custom zlib function provided */
02198   return settings->custom_zlib(out, outsize, in, insize, settings);
02199 }
02200 #endif /*LODEPNG_COMPILE_DECODER*/
02201 #ifdef LODEPNG_COMPILE_ENCODER
02202 static unsigned zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
02203                               size_t insize, const LodePNGCompressSettings* settings)
02204 {
02205   if (!settings->custom_zlib) return 87; /*no custom zlib function provided */
02206   return settings->custom_zlib(out, outsize, in, insize, settings);
02207 }
02208 #endif /*LODEPNG_COMPILE_ENCODER*/
02209 
02210 #endif /*LODEPNG_COMPILE_ZLIB*/
02211 
02212 /* ////////////////////////////////////////////////////////////////////////// */
02213 
02214 #ifdef LODEPNG_COMPILE_ENCODER
02215 
02216 /*this is a good tradeoff between speed and compression ratio*/
02217 #define DEFAULT_WINDOWSIZE 2048
02218 
02219 void lodepng_compress_settings_init(LodePNGCompressSettings* settings)
02220 {
02221   /*compress with dynamic huffman tree (not in the mathematical sense, just not the predefined one)*/
02222   settings->btype = 2;
02223   settings->use_lz77 = 1;
02224   settings->windowsize = DEFAULT_WINDOWSIZE;
02225   settings->minmatch = 3;
02226   settings->nicematch = 128;
02227   settings->lazymatching = 1;
02228 
02229   settings->custom_zlib = 0;
02230   settings->custom_deflate = 0;
02231   settings->custom_context = 0;
02232 }
02233 
02234 const LodePNGCompressSettings lodepng_default_compress_settings = {2, 1, DEFAULT_WINDOWSIZE, 3, 128, 1, 0, 0, 0};
02235 
02236 
02237 #endif /*LODEPNG_COMPILE_ENCODER*/
02238 
02239 #ifdef LODEPNG_COMPILE_DECODER
02240 
02241 void lodepng_decompress_settings_init(LodePNGDecompressSettings* settings)
02242 {
02243   settings->ignore_adler32 = 0;
02244 
02245   settings->custom_zlib = 0;
02246   settings->custom_inflate = 0;
02247   settings->custom_context = 0;
02248 }
02249 
02250 const LodePNGDecompressSettings lodepng_default_decompress_settings = {0, 0, 0, 0};
02251 
02252 #endif /*LODEPNG_COMPILE_DECODER*/
02253 
02254 /* ////////////////////////////////////////////////////////////////////////// */
02255 /* ////////////////////////////////////////////////////////////////////////// */
02256 /* // End of Zlib related code. Begin of PNG related code.                 // */
02257 /* ////////////////////////////////////////////////////////////////////////// */
02258 /* ////////////////////////////////////////////////////////////////////////// */
02259 
02260 #ifdef LODEPNG_COMPILE_PNG
02261 
02262 /* ////////////////////////////////////////////////////////////////////////// */
02263 /* / CRC32                                                                  / */
02264 /* ////////////////////////////////////////////////////////////////////////// */
02265 
02266 /* CRC polynomial: 0xedb88320 */
02267 static unsigned lodepng_crc32_table[256] = {
02268            0u, 1996959894u, 3993919788u, 2567524794u,  124634137u, 1886057615u, 3915621685u, 2657392035u,
02269    249268274u, 2044508324u, 3772115230u, 2547177864u,  162941995u, 2125561021u, 3887607047u, 2428444049u,
02270    498536548u, 1789927666u, 4089016648u, 2227061214u,  450548861u, 1843258603u, 4107580753u, 2211677639u,
02271    325883990u, 1684777152u, 4251122042u, 2321926636u,  335633487u, 1661365465u, 4195302755u, 2366115317u,
02272    997073096u, 1281953886u, 3579855332u, 2724688242u, 1006888145u, 1258607687u, 3524101629u, 2768942443u,
02273    901097722u, 1119000684u, 3686517206u, 2898065728u,  853044451u, 1172266101u, 3705015759u, 2882616665u,
02274    651767980u, 1373503546u, 3369554304u, 3218104598u,  565507253u, 1454621731u, 3485111705u, 3099436303u,
02275    671266974u, 1594198024u, 3322730930u, 2970347812u,  795835527u, 1483230225u, 3244367275u, 3060149565u,
02276   1994146192u,   31158534u, 2563907772u, 4023717930u, 1907459465u,  112637215u, 2680153253u, 3904427059u,
02277   2013776290u,  251722036u, 2517215374u, 3775830040u, 2137656763u,  141376813u, 2439277719u, 3865271297u,
02278   1802195444u,  476864866u, 2238001368u, 4066508878u, 1812370925u,  453092731u, 2181625025u, 4111451223u,
02279   1706088902u,  314042704u, 2344532202u, 4240017532u, 1658658271u,  366619977u, 2362670323u, 4224994405u,
02280   1303535960u,  984961486u, 2747007092u, 3569037538u, 1256170817u, 1037604311u, 2765210733u, 3554079995u,
02281   1131014506u,  879679996u, 2909243462u, 3663771856u, 1141124467u,  855842277u, 2852801631u, 3708648649u,
02282   1342533948u,  654459306u, 3188396048u, 3373015174u, 1466479909u,  544179635u, 3110523913u, 3462522015u,
02283   1591671054u,  702138776u, 2966460450u, 3352799412u, 1504918807u,  783551873u, 3082640443u, 3233442989u,
02284   3988292384u, 2596254646u,   62317068u, 1957810842u, 3939845945u, 2647816111u,   81470997u, 1943803523u,
02285   3814918930u, 2489596804u,  225274430u, 2053790376u, 3826175755u, 2466906013u,  167816743u, 2097651377u,
02286   4027552580u, 2265490386u,  503444072u, 1762050814u, 4150417245u, 2154129355u,  426522225u, 1852507879u,
02287   4275313526u, 2312317920u,  282753626u, 1742555852u, 4189708143u, 2394877945u,  397917763u, 1622183637u,
02288   3604390888u, 2714866558u,  953729732u, 1340076626u, 3518719985u, 2797360999u, 1068828381u, 1219638859u,
02289   3624741850u, 2936675148u,  906185462u, 1090812512u, 3747672003u, 2825379669u,  829329135u, 1181335161u,
02290   3412177804u, 3160834842u,  628085408u, 1382605366u, 3423369109u, 3138078467u,  570562233u, 1426400815u,
02291   3317316542u, 2998733608u,  733239954u, 1555261956u, 3268935591u, 3050360625u,  752459403u, 1541320221u,
02292   2607071920u, 3965973030u, 1969922972u,   40735498u, 2617837225u, 3943577151u, 1913087877u,   83908371u,
02293   2512341634u, 3803740692u, 2075208622u,  213261112u, 2463272603u, 3855990285u, 2094854071u,  198958881u,
02294   2262029012u, 4057260610u, 1759359992u,  534414190u, 2176718541u, 4139329115u, 1873836001u,  414664567u,
02295   2282248934u, 4279200368u, 1711684554u,  285281116u, 2405801727u, 4167216745u, 1634467795u,  376229701u,
02296   2685067896u, 3608007406u, 1308918612u,  956543938u, 2808555105u, 3495958263u, 1231636301u, 1047427035u,
02297   2932959818u, 3654703836u, 1088359270u,  936918000u, 2847714899u, 3736837829u, 1202900863u,  817233897u,
02298   3183342108u, 3401237130u, 1404277552u,  615818150u, 3134207493u, 3453421203u, 1423857449u,  601450431u,
02299   3009837614u, 3294710456u, 1567103746u,  711928724u, 3020668471u, 3272380065u, 1510334235u,  755167117u
02300 };
02301 
02302 /*Return the CRC of the bytes buf[0..len-1].*/
02303 unsigned lodepng_crc32(const unsigned char* buf, size_t len)
02304 {
02305   unsigned c = 0xffffffffL;
02306   size_t n;
02307 
02308   for(n = 0; n < len; n++)
02309   {
02310     c = lodepng_crc32_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
02311   }
02312   return c ^ 0xffffffffL;
02313 }
02314 
02315 /* ////////////////////////////////////////////////////////////////////////// */
02316 /* / Reading and writing single bits and bytes from/to stream for LodePNG   / */
02317 /* ////////////////////////////////////////////////////////////////////////// */
02318 
02319 static unsigned char readBitFromReversedStream(size_t* bitpointer, const unsigned char* bitstream)
02320 {
02321   unsigned char result = (unsigned char)((bitstream[(*bitpointer) >> 3] >> (7 - ((*bitpointer) & 0x7))) & 1);
02322   (*bitpointer)++;
02323   return result;
02324 }
02325 
02326 static unsigned readBitsFromReversedStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
02327 {
02328   unsigned result = 0;
02329   size_t i;
02330   for(i = nbits - 1; i < nbits; i--)
02331   {
02332     result += (unsigned)readBitFromReversedStream(bitpointer, bitstream) << i;
02333   }
02334   return result;
02335 }
02336 
02337 #ifdef LODEPNG_COMPILE_DECODER
02338 static void setBitOfReversedStream0(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
02339 {
02340   /*the current bit in bitstream must be 0 for this to work*/
02341   if(bit)
02342   {
02343     /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/
02344     bitstream[(*bitpointer) >> 3] |= (bit << (7 - ((*bitpointer) & 0x7)));
02345   }
02346   (*bitpointer)++;
02347 }
02348 #endif /*LODEPNG_COMPILE_DECODER*/
02349 
02350 static void setBitOfReversedStream(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
02351 {
02352   /*the current bit in bitstream may be 0 or 1 for this to work*/
02353   if(bit == 0) bitstream[(*bitpointer) >> 3] &=  (unsigned char)(~(1 << (7 - ((*bitpointer) & 0x7))));
02354   else         bitstream[(*bitpointer) >> 3] |=  (1 << (7 - ((*bitpointer) & 0x7)));
02355   (*bitpointer)++;
02356 }
02357 
02358 /* ////////////////////////////////////////////////////////////////////////// */
02359 /* / PNG chunks                                                             / */
02360 /* ////////////////////////////////////////////////////////////////////////// */
02361 
02362 unsigned lodepng_chunk_length(const unsigned char* chunk)
02363 {
02364   return lodepng_read32bitInt(&chunk[0]);
02365 }
02366 
02367 void lodepng_chunk_type(char type[5], const unsigned char* chunk)
02368 {
02369   unsigned i;
02370   for(i = 0; i < 4; i++) type[i] = chunk[4 + i];
02371   type[4] = 0; /*null termination char*/
02372 }
02373 
02374 unsigned char lodepng_chunk_type_equals(const unsigned char* chunk, const char* type)
02375 {
02376   if(strlen(type) != 4) return 0;
02377   return (chunk[4] == type[0] && chunk[5] == type[1] && chunk[6] == type[2] && chunk[7] == type[3]);
02378 }
02379 
02380 unsigned char lodepng_chunk_ancillary(const unsigned char* chunk)
02381 {
02382   return((chunk[4] & 32) != 0);
02383 }
02384 
02385 unsigned char lodepng_chunk_private(const unsigned char* chunk)
02386 {
02387   return((chunk[6] & 32) != 0);
02388 }
02389 
02390 unsigned char lodepng_chunk_safetocopy(const unsigned char* chunk)
02391 {
02392   return((chunk[7] & 32) != 0);
02393 }
02394 
02395 unsigned char* lodepng_chunk_data(unsigned char* chunk)
02396 {
02397   return &chunk[8];
02398 }
02399 
02400 const unsigned char* lodepng_chunk_data_const(const unsigned char* chunk)
02401 {
02402   return &chunk[8];
02403 }
02404 
02405 unsigned lodepng_chunk_check_crc(const unsigned char* chunk)
02406 {
02407   unsigned length = lodepng_chunk_length(chunk);
02408   unsigned CRC = lodepng_read32bitInt(&chunk[length + 8]);
02409   /*the CRC is taken of the data and the 4 chunk type letters, not the length*/
02410   unsigned checksum = lodepng_crc32(&chunk[4], length + 4);
02411   if(CRC != checksum) return 1;
02412   else return 0;
02413 }
02414 
02415 void lodepng_chunk_generate_crc(unsigned char* chunk)
02416 {
02417   unsigned length = lodepng_chunk_length(chunk);
02418   unsigned CRC = lodepng_crc32(&chunk[4], length + 4);
02419   lodepng_set32bitInt(chunk + 8 + length, CRC);
02420 }
02421 
02422 unsigned char* lodepng_chunk_next(unsigned char* chunk)
02423 {
02424   unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
02425   return &chunk[total_chunk_length];
02426 }
02427 
02428 const unsigned char* lodepng_chunk_next_const(const unsigned char* chunk)
02429 {
02430   unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
02431   return &chunk[total_chunk_length];
02432 }
02433 
02434 unsigned lodepng_chunk_append(unsigned char** out, size_t* outlength, const unsigned char* chunk)
02435 {
02436   unsigned i;
02437   unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
02438   unsigned char *chunk_start, *new_buffer;
02439   size_t new_length = (*outlength) + total_chunk_length;
02440   if(new_length < total_chunk_length || new_length < (*outlength)) return 77; /*integer overflow happened*/
02441 
02442   new_buffer = (unsigned char*)lodepng_realloc(*out, new_length);
02443   if(!new_buffer) return 83; /*alloc fail*/
02444   (*out) = new_buffer;
02445   (*outlength) = new_length;
02446   chunk_start = &(*out)[new_length - total_chunk_length];
02447 
02448   for(i = 0; i < total_chunk_length; i++) chunk_start[i] = chunk[i];
02449 
02450   return 0;
02451 }
02452 
02453 unsigned lodepng_chunk_create(unsigned char** out, size_t* outlength, unsigned length,
02454                               const char* type, const unsigned char* data)
02455 {
02456   unsigned i;
02457   unsigned char *chunk, *new_buffer;
02458   size_t new_length = (*outlength) + length + 12;
02459   if(new_length < length + 12 || new_length < (*outlength)) return 77; /*integer overflow happened*/
02460   new_buffer = (unsigned char*)lodepng_realloc(*out, new_length);
02461   if(!new_buffer) return 83; /*alloc fail*/
02462   (*out) = new_buffer;
02463   (*outlength) = new_length;
02464   chunk = &(*out)[(*outlength) - length - 12];
02465 
02466   /*1: length*/
02467   lodepng_set32bitInt(chunk, (unsigned)length);
02468 
02469   /*2: chunk name (4 letters)*/
02470   chunk[4] = type[0];
02471   chunk[5] = type[1];
02472   chunk[6] = type[2];
02473   chunk[7] = type[3];
02474 
02475   /*3: the data*/
02476   for(i = 0; i < length; i++) chunk[8 + i] = data[i];
02477 
02478   /*4: CRC (of the chunkname characters and the data)*/
02479   lodepng_chunk_generate_crc(chunk);
02480 
02481   return 0;
02482 }
02483 
02484 /* ////////////////////////////////////////////////////////////////////////// */
02485 /* / Color types and such                                                   / */
02486 /* ////////////////////////////////////////////////////////////////////////// */
02487 
02488 /*return type is a LodePNG error code*/
02489 static unsigned checkColorValidity(LodePNGColorType colortype, unsigned bd) /*bd = bitdepth*/
02490 {
02491   switch(colortype)
02492   {
02493     case 0: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8 || bd == 16)) return 37; break; /*grey*/
02494     case 2: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*RGB*/
02495     case 3: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8            )) return 37; break; /*palette*/
02496     case 4: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*grey + alpha*/
02497     case 6: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*RGBA*/
02498     default: return 31;
02499   }
02500   return 0; /*allowed color type / bits combination*/
02501 }
02502 
02503 static unsigned getNumColorChannels(LodePNGColorType colortype)
02504 {
02505   switch(colortype)
02506   {
02507     case 0: return 1; /*grey*/
02508     case 2: return 3; /*RGB*/
02509     case 3: return 1; /*palette*/
02510     case 4: return 2; /*grey + alpha*/
02511     case 6: return 4; /*RGBA*/
02512   }
02513   return 0; /*unexisting color type*/
02514 }
02515 
02516 static unsigned lodepng_get_bpp_lct(LodePNGColorType colortype, unsigned bitdepth)
02517 {
02518   /*bits per pixel is amount of channels * bits per channel*/
02519   return getNumColorChannels(colortype) * bitdepth;
02520 }
02521 
02522 /* ////////////////////////////////////////////////////////////////////////// */
02523 
02524 void lodepng_color_mode_init(LodePNGColorMode* info)
02525 {
02526   info->key_defined = 0;
02527   info->key_r = info->key_g = info->key_b = 0;
02528   info->colortype = LCT_RGBA;
02529   info->bitdepth = 8;
02530   info->palette = 0;
02531   info->palettesize = 0;
02532 }
02533 
02534 void lodepng_color_mode_cleanup(LodePNGColorMode* info)
02535 {
02536   lodepng_palette_clear(info);
02537 }
02538 
02539 unsigned lodepng_color_mode_copy(LodePNGColorMode* dest, const LodePNGColorMode* source)
02540 {
02541   size_t i;
02542   lodepng_color_mode_cleanup(dest);
02543   *dest = *source;
02544   if(source->palette)
02545   {
02546     dest->palette = (unsigned char*)lodepng_malloc(1024);
02547     if(!dest->palette && source->palettesize) return 83; /*alloc fail*/
02548     for(i = 0; i < source->palettesize * 4; i++) dest->palette[i] = source->palette[i];
02549   }
02550   return 0;
02551 }
02552 
02553 static int lodepng_color_mode_equal(const LodePNGColorMode* a, const LodePNGColorMode* b)
02554 {
02555   size_t i;
02556   if(a->colortype != b->colortype) return 0;
02557   if(a->bitdepth != b->bitdepth) return 0;
02558   if(a->key_defined != b->key_defined) return 0;
02559   if(a->key_defined)
02560   {
02561     if(a->key_r != b->key_r) return 0;
02562     if(a->key_g != b->key_g) return 0;
02563     if(a->key_b != b->key_b) return 0;
02564   }
02565   if(a->palettesize != b->palettesize) return 0;
02566   for(i = 0; i < a->palettesize * 4; i++)
02567   {
02568     if(a->palette[i] != b->palette[i]) return 0;
02569   }
02570   return 1;
02571 }
02572 
02573 void lodepng_palette_clear(LodePNGColorMode* info)
02574 {
02575   if(info->palette) lodepng_free(info->palette);
02576   info->palette = 0;
02577   info->palettesize = 0;
02578 }
02579 
02580 unsigned lodepng_palette_add(LodePNGColorMode* info,
02581                              unsigned char r, unsigned char g, unsigned char b, unsigned char a)
02582 {
02583   unsigned char* data;
02584   /*the same resize technique as C++ std::vectors is used, and here it's made so that for a palette with
02585   the max of 256 colors, it'll have the exact alloc size*/
02586   if(!info->palette) /*allocate palette if empty*/
02587   {
02588     /*room for 256 colors with 4 bytes each*/
02589     data = (unsigned char*)lodepng_realloc(info->palette, 1024);
02590     if(!data) return 83; /*alloc fail*/
02591     else info->palette = data;
02592   }
02593   info->palette[4 * info->palettesize + 0] = r;
02594   info->palette[4 * info->palettesize + 1] = g;
02595   info->palette[4 * info->palettesize + 2] = b;
02596   info->palette[4 * info->palettesize + 3] = a;
02597   info->palettesize++;
02598   return 0;
02599 }
02600 
02601 unsigned lodepng_get_bpp(const LodePNGColorMode* info)
02602 {
02603   /*calculate bits per pixel out of colortype and bitdepth*/
02604   return lodepng_get_bpp_lct(info->colortype, info->bitdepth);
02605 }
02606 
02607 unsigned lodepng_get_channels(const LodePNGColorMode* info)
02608 {
02609   return getNumColorChannels(info->colortype);
02610 }
02611 
02612 unsigned lodepng_is_greyscale_type(const LodePNGColorMode* info)
02613 {
02614   return info->colortype == LCT_GREY || info->colortype == LCT_GREY_ALPHA;
02615 }
02616 
02617 unsigned lodepng_is_alpha_type(const LodePNGColorMode* info)
02618 {
02619   return (info->colortype & 4) != 0; /*4 or 6*/
02620 }
02621 
02622 unsigned lodepng_is_palette_type(const LodePNGColorMode* info)
02623 {
02624   return info->colortype == LCT_PALETTE;
02625 }
02626 
02627 unsigned lodepng_has_palette_alpha(const LodePNGColorMode* info)
02628 {
02629   size_t i;
02630   for(i = 0; i < info->palettesize; i++)
02631   {
02632     if(info->palette[i * 4 + 3] < 255) return 1;
02633   }
02634   return 0;
02635 }
02636 
02637 unsigned lodepng_can_have_alpha(const LodePNGColorMode* info)
02638 {
02639   return info->key_defined
02640       || lodepng_is_alpha_type(info)
02641       || lodepng_has_palette_alpha(info);
02642 }
02643 
02644 size_t lodepng_get_raw_size(unsigned w, unsigned h, const LodePNGColorMode* color)
02645 {
02646   return (w * h * lodepng_get_bpp(color) + 7) / 8;
02647 }
02648 
02649 size_t lodepng_get_raw_size_lct(unsigned w, unsigned h, LodePNGColorType colortype, unsigned bitdepth)
02650 {
02651   return (w * h * lodepng_get_bpp_lct(colortype, bitdepth) + 7) / 8;
02652 }
02653 
02654 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
02655 
02656 static void LodePNGUnknownChunks_init(LodePNGInfo* info)
02657 {
02658   unsigned i;
02659   for(i = 0; i < 3; i++) info->unknown_chunks_data[i] = 0;
02660   for(i = 0; i < 3; i++) info->unknown_chunks_size[i] = 0;
02661 }
02662 
02663 static void LodePNGUnknownChunks_cleanup(LodePNGInfo* info)
02664 {
02665   unsigned i;
02666   for(i = 0; i < 3; i++) lodepng_free(info->unknown_chunks_data[i]);
02667 }
02668 
02669 static unsigned LodePNGUnknownChunks_copy(LodePNGInfo* dest, const LodePNGInfo* src)
02670 {
02671   unsigned i;
02672 
02673   LodePNGUnknownChunks_cleanup(dest);
02674 
02675   for(i = 0; i < 3; i++)
02676   {
02677     size_t j;
02678     dest->unknown_chunks_size[i] = src->unknown_chunks_size[i];
02679     dest->unknown_chunks_data[i] = (unsigned char*)lodepng_malloc(src->unknown_chunks_size[i]);
02680     if(!dest->unknown_chunks_data[i] && dest->unknown_chunks_size[i]) return 83; /*alloc fail*/
02681     for(j = 0; j < src->unknown_chunks_size[i]; j++)
02682     {
02683       dest->unknown_chunks_data[i][j] = src->unknown_chunks_data[i][j];
02684     }
02685   }
02686 
02687   return 0;
02688 }
02689 
02690 /******************************************************************************/
02691 
02692 static void LodePNGText_init(LodePNGInfo* info)
02693 {
02694   info->text_num = 0;
02695   info->text_keys = NULL;
02696   info->text_strings = NULL;
02697 }
02698 
02699 static void LodePNGText_cleanup(LodePNGInfo* info)
02700 {
02701   size_t i;
02702   for(i = 0; i < info->text_num; i++)
02703   {
02704     string_cleanup(&info->text_keys[i]);
02705     string_cleanup(&info->text_strings[i]);
02706   }
02707   lodepng_free(info->text_keys);
02708   lodepng_free(info->text_strings);
02709 }
02710 
02711 static unsigned LodePNGText_copy(LodePNGInfo* dest, const LodePNGInfo* source)
02712 {
02713   size_t i = 0;
02714   dest->text_keys = 0;
02715   dest->text_strings = 0;
02716   dest->text_num = 0;
02717   for(i = 0; i < source->text_num; i++)
02718   {
02719     CERROR_TRY_RETURN(lodepng_add_text(dest, source->text_keys[i], source->text_strings[i]));
02720   }
02721   return 0;
02722 }
02723 
02724 void lodepng_clear_text(LodePNGInfo* info)
02725 {
02726   LodePNGText_cleanup(info);
02727 }
02728 
02729 unsigned lodepng_add_text(LodePNGInfo* info, const char* key, const char* str)
02730 {
02731   char** new_keys = (char**)(lodepng_realloc(info->text_keys, sizeof(char*) * (info->text_num + 1)));
02732   char** new_strings = (char**)(lodepng_realloc(info->text_strings, sizeof(char*) * (info->text_num + 1)));
02733   if(!new_keys || !new_strings)
02734   {
02735     lodepng_free(new_keys);
02736     lodepng_free(new_strings);
02737     return 83; /*alloc fail*/
02738   }
02739 
02740   info->text_num++;
02741   info->text_keys = new_keys;
02742   info->text_strings = new_strings;
02743 
02744   string_init(&info->text_keys[info->text_num - 1]);
02745   string_set(&info->text_keys[info->text_num - 1], key);
02746 
02747   string_init(&info->text_strings[info->text_num - 1]);
02748   string_set(&info->text_strings[info->text_num - 1], str);
02749 
02750   return 0;
02751 }
02752 
02753 /******************************************************************************/
02754 
02755 static void LodePNGIText_init(LodePNGInfo* info)
02756 {
02757   info->itext_num = 0;
02758   info->itext_keys = NULL;
02759   info->itext_langtags = NULL;
02760   info->itext_transkeys = NULL;
02761   info->itext_strings = NULL;
02762 }
02763 
02764 static void LodePNGIText_cleanup(LodePNGInfo* info)
02765 {
02766   size_t i;
02767   for(i = 0; i < info->itext_num; i++)
02768   {
02769     string_cleanup(&info->itext_keys[i]);
02770     string_cleanup(&info->itext_langtags[i]);
02771     string_cleanup(&info->itext_transkeys[i]);
02772     string_cleanup(&info->itext_strings[i]);
02773   }
02774   lodepng_free(info->itext_keys);
02775   lodepng_free(info->itext_langtags);
02776   lodepng_free(info->itext_transkeys);
02777   lodepng_free(info->itext_strings);
02778 }
02779 
02780 static unsigned LodePNGIText_copy(LodePNGInfo* dest, const LodePNGInfo* source)
02781 {
02782   size_t i = 0;
02783   dest->itext_keys = 0;
02784   dest->itext_langtags = 0;
02785   dest->itext_transkeys = 0;
02786   dest->itext_strings = 0;
02787   dest->itext_num = 0;
02788   for(i = 0; i < source->itext_num; i++)
02789   {
02790     CERROR_TRY_RETURN(lodepng_add_itext(dest, source->itext_keys[i], source->itext_langtags[i],
02791                                         source->itext_transkeys[i], source->itext_strings[i]));
02792   }
02793   return 0;
02794 }
02795 
02796 void lodepng_clear_itext(LodePNGInfo* info)
02797 {
02798   LodePNGIText_cleanup(info);
02799 }
02800 
02801 unsigned lodepng_add_itext(LodePNGInfo* info, const char* key, const char* langtag,
02802                            const char* transkey, const char* str)
02803 {
02804   char** new_keys = (char**)(lodepng_realloc(info->itext_keys, sizeof(char*) * (info->itext_num + 1)));
02805   char** new_langtags = (char**)(lodepng_realloc(info->itext_langtags, sizeof(char*) * (info->itext_num + 1)));
02806   char** new_transkeys = (char**)(lodepng_realloc(info->itext_transkeys, sizeof(char*) * (info->itext_num + 1)));
02807   char** new_strings = (char**)(lodepng_realloc(info->itext_strings, sizeof(char*) * (info->itext_num + 1)));
02808   if(!new_keys || !new_langtags || !new_transkeys || !new_strings)
02809   {
02810     lodepng_free(new_keys);
02811     lodepng_free(new_langtags);
02812     lodepng_free(new_transkeys);
02813     lodepng_free(new_strings);
02814     return 83; /*alloc fail*/
02815   }
02816 
02817   info->itext_num++;
02818   info->itext_keys = new_keys;
02819   info->itext_langtags = new_langtags;
02820   info->itext_transkeys = new_transkeys;
02821   info->itext_strings = new_strings;
02822 
02823   string_init(&info->itext_keys[info->itext_num - 1]);
02824   string_set(&info->itext_keys[info->itext_num - 1], key);
02825 
02826   string_init(&info->itext_langtags[info->itext_num - 1]);
02827   string_set(&info->itext_langtags[info->itext_num - 1], langtag);
02828 
02829   string_init(&info->itext_transkeys[info->itext_num - 1]);
02830   string_set(&info->itext_transkeys[info->itext_num - 1], transkey);
02831 
02832   string_init(&info->itext_strings[info->itext_num - 1]);
02833   string_set(&info->itext_strings[info->itext_num - 1], str);
02834 
02835   return 0;
02836 }
02837 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
02838 
02839 void lodepng_info_init(LodePNGInfo* info)
02840 {
02841   lodepng_color_mode_init(&info->color);
02842   info->interlace_method = 0;
02843   info->compression_method = 0;
02844   info->filter_method = 0;
02845 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
02846   info->background_defined = 0;
02847   info->background_r = info->background_g = info->background_b = 0;
02848 
02849   LodePNGText_init(info);
02850   LodePNGIText_init(info);
02851 
02852   info->time_defined = 0;
02853   info->phys_defined = 0;
02854 
02855   LodePNGUnknownChunks_init(info);
02856 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
02857 }
02858 
02859 void lodepng_info_cleanup(LodePNGInfo* info)
02860 {
02861   lodepng_color_mode_cleanup(&info->color);
02862 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
02863   LodePNGText_cleanup(info);
02864   LodePNGIText_cleanup(info);
02865 
02866   LodePNGUnknownChunks_cleanup(info);
02867 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
02868 }
02869 
02870 unsigned lodepng_info_copy(LodePNGInfo* dest, const LodePNGInfo* source)
02871 {
02872   lodepng_info_cleanup(dest);
02873   *dest = *source;
02874   lodepng_color_mode_init(&dest->color);
02875   CERROR_TRY_RETURN(lodepng_color_mode_copy(&dest->color, &source->color));
02876 
02877 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
02878   CERROR_TRY_RETURN(LodePNGText_copy(dest, source));
02879   CERROR_TRY_RETURN(LodePNGIText_copy(dest, source));
02880 
02881   LodePNGUnknownChunks_init(dest);
02882   CERROR_TRY_RETURN(LodePNGUnknownChunks_copy(dest, source));
02883 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
02884   return 0;
02885 }
02886 
02887 void lodepng_info_swap(LodePNGInfo* a, LodePNGInfo* b)
02888 {
02889   LodePNGInfo temp = *a;
02890   *a = *b;
02891   *b = temp;
02892 }
02893 
02894 /* ////////////////////////////////////////////////////////////////////////// */
02895 
02896 /*index: bitgroup index, bits: bitgroup size(1, 2 or 4), in: bitgroup value, out: octet array to add bits to*/
02897 static void addColorBits(unsigned char* out, size_t index, unsigned bits, unsigned in)
02898 {
02899   unsigned m = bits == 1 ? 7 : bits == 2 ? 3 : 1; /*8 / bits - 1*/
02900   /*p = the partial index in the byte, e.g. with 4 palettebits it is 0 for first half or 1 for second half*/
02901   unsigned p = index & m;
02902   in &= (1 << bits) - 1; /*filter out any other bits of the input value*/
02903   in = in << (bits * (m - p));
02904   if(p == 0) out[index * bits / 8] = in;
02905   else out[index * bits / 8] |= in;
02906 }
02907 
02908 typedef struct ColorTree ColorTree;
02909 
02910 /*
02911 One node of a color tree
02912 This is the data structure used to count the number of unique colors and to get a palette
02913 index for a color. It's like an octree, but because the alpha channel is used too, each
02914 node has 16 instead of 8 children.
02915 */
02916 struct ColorTree
02917 {
02918   ColorTree* children[16]; /*up to 16 pointers to ColorTree of next level*/
02919   int index; /*the payload. Only has a meaningful value if this is in the last level*/
02920 };
02921 
02922 static void color_tree_init(ColorTree* tree)
02923 {
02924   int i;
02925   for(i = 0; i < 16; i++) tree->children[i] = 0;
02926   tree->index = -1;
02927 }
02928 
02929 static void color_tree_cleanup(ColorTree* tree)
02930 {
02931   int i;
02932   for(i = 0; i < 16; i++)
02933   {
02934     if(tree->children[i])
02935     {
02936       color_tree_cleanup(tree->children[i]);
02937       lodepng_free(tree->children[i]);
02938     }
02939   }
02940 }
02941 
02942 /*returns -1 if color not present, its index otherwise*/
02943 static int color_tree_get(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
02944 {
02945   int bit = 0;
02946   for(bit = 0; bit < 8; bit++)
02947   {
02948     int i = 8 * ((r >> bit) & 1) + 4 * ((g >> bit) & 1) + 2 * ((b >> bit) & 1) + 1 * ((a >> bit) & 1);
02949     if(!tree->children[i]) return -1;
02950     else tree = tree->children[i];
02951   }
02952   return tree ? tree->index : -1;
02953 }
02954 
02955 #ifdef LODEPNG_COMPILE_ENCODER
02956 static int color_tree_has(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
02957 {
02958   return color_tree_get(tree, r, g, b, a) >= 0;
02959 }
02960 #endif /*LODEPNG_COMPILE_ENCODER*/
02961 
02962 /*color is not allowed to already exist.
02963 Index should be >= 0 (it's signed to be compatible with using -1 for "doesn't exist")*/
02964 static void color_tree_add(ColorTree* tree,
02965                            unsigned char r, unsigned char g, unsigned char b, unsigned char a, int index)
02966 {
02967   int bit;
02968   for(bit = 0; bit < 8; bit++)
02969   {
02970     int i = 8 * ((r >> bit) & 1) + 4 * ((g >> bit) & 1) + 2 * ((b >> bit) & 1) + 1 * ((a >> bit) & 1);
02971     if(!tree->children[i])
02972     {
02973       tree->children[i] = (ColorTree*)lodepng_malloc(sizeof(ColorTree));
02974       color_tree_init(tree->children[i]);
02975     }
02976     tree = tree->children[i];
02977   }
02978   tree->index = index;
02979 }
02980 
02981 /*put a pixel, given its RGBA color, into image of any color type*/
02982 static unsigned rgba8ToPixel(unsigned char* out, size_t i,
02983                              const LodePNGColorMode* mode, ColorTree* tree /*for palette*/,
02984                              unsigned char r, unsigned char g, unsigned char b, unsigned char a)
02985 {
02986   if(mode->colortype == LCT_GREY)
02987   {
02988     unsigned char grey = r; /*((unsigned short)r + g + b) / 3*/;
02989     if(mode->bitdepth == 8) out[i] = grey;
02990     else if(mode->bitdepth == 16) out[i * 2 + 0] = out[i * 2 + 1] = grey;
02991     else
02992     {
02993       /*take the most significant bits of grey*/
02994       grey = (grey >> (8 - mode->bitdepth)) & ((1 << mode->bitdepth) - 1);
02995       addColorBits(out, i, mode->bitdepth, grey);
02996     }
02997   }
02998   else if(mode->colortype == LCT_RGB)
02999   {
03000     if(mode->bitdepth == 8)
03001     {
03002       out[i * 3 + 0] = r;
03003       out[i * 3 + 1] = g;
03004       out[i * 3 + 2] = b;
03005     }
03006     else
03007     {
03008       out[i * 6 + 0] = out[i * 6 + 1] = r;
03009       out[i * 6 + 2] = out[i * 6 + 3] = g;
03010       out[i * 6 + 4] = out[i * 6 + 5] = b;
03011     }
03012   }
03013   else if(mode->colortype == LCT_PALETTE)
03014   {
03015     int index = color_tree_get(tree, r, g, b, a);
03016     if(index < 0) return 82; /*color not in palette*/
03017     if(mode->bitdepth == 8) out[i] = index;
03018     else addColorBits(out, i, mode->bitdepth, index);
03019   }
03020   else if(mode->colortype == LCT_GREY_ALPHA)
03021   {
03022     unsigned char grey = r; /*((unsigned short)r + g + b) / 3*/;
03023     if(mode->bitdepth == 8)
03024     {
03025       out[i * 2 + 0] = grey;
03026       out[i * 2 + 1] = a;
03027     }
03028     else if(mode->bitdepth == 16)
03029     {
03030       out[i * 4 + 0] = out[i * 4 + 1] = grey;
03031       out[i * 4 + 2] = out[i * 4 + 3] = a;
03032     }
03033   }
03034   else if(mode->colortype == LCT_RGBA)
03035   {
03036     if(mode->bitdepth == 8)
03037     {
03038       out[i * 4 + 0] = r;
03039       out[i * 4 + 1] = g;
03040       out[i * 4 + 2] = b;
03041       out[i * 4 + 3] = a;
03042     }
03043     else
03044     {
03045       out[i * 8 + 0] = out[i * 8 + 1] = r;
03046       out[i * 8 + 2] = out[i * 8 + 3] = g;
03047       out[i * 8 + 4] = out[i * 8 + 5] = b;
03048       out[i * 8 + 6] = out[i * 8 + 7] = a;
03049     }
03050   }
03051 
03052   return 0; /*no error*/
03053 }
03054 
03055 /*put a pixel, given its RGBA16 color, into image of any color 16-bitdepth type*/
03056 static unsigned rgba16ToPixel(unsigned char* out, size_t i,
03057                               const LodePNGColorMode* mode,
03058                               unsigned short r, unsigned short g, unsigned short b, unsigned short a)
03059 {
03060   if(mode->bitdepth != 16) return 85; /*must be 16 for this function*/
03061   if(mode->colortype == LCT_GREY)
03062   {
03063     unsigned short grey = r; /*((unsigned)r + g + b) / 3*/;
03064     out[i * 2 + 0] = (grey >> 8) & 255;
03065     out[i * 2 + 1] = grey & 255;
03066   }
03067   else if(mode->colortype == LCT_RGB)
03068   {
03069     out[i * 6 + 0] = (r >> 8) & 255;
03070     out[i * 6 + 1] = r & 255;
03071     out[i * 6 + 2] = (g >> 8) & 255;
03072     out[i * 6 + 3] = g & 255;
03073     out[i * 6 + 4] = (b >> 8) & 255;
03074     out[i * 6 + 5] = b & 255;
03075   }
03076   else if(mode->colortype == LCT_GREY_ALPHA)
03077   {
03078     unsigned short grey = r; /*((unsigned)r + g + b) / 3*/;
03079     out[i * 4 + 0] = (grey >> 8) & 255;
03080     out[i * 4 + 1] = grey & 255;
03081     out[i * 4 + 2] = (a >> 8) & 255;
03082     out[i * 4 + 3] = a & 255;
03083   }
03084   else if(mode->colortype == LCT_RGBA)
03085   {
03086     out[i * 8 + 0] = (r >> 8) & 255;
03087     out[i * 8 + 1] = r & 255;
03088     out[i * 8 + 2] = (g >> 8) & 255;
03089     out[i * 8 + 3] = g & 255;
03090     out[i * 8 + 4] = (b >> 8) & 255;
03091     out[i * 8 + 5] = b & 255;
03092     out[i * 8 + 6] = (a >> 8) & 255;
03093     out[i * 8 + 7] = a & 255;
03094   }
03095 
03096   return 0; /*no error*/
03097 }
03098 
03099 /*Get RGBA8 color of pixel with index i (y * width + x) from the raw image with given color type.*/
03100 static unsigned getPixelColorRGBA8(unsigned char* r, unsigned char* g,
03101                                    unsigned char* b, unsigned char* a,
03102                                    const unsigned char* in, size_t i,
03103                                    const LodePNGColorMode* mode,
03104                                    unsigned fix_png)
03105 {
03106   if(mode->colortype == LCT_GREY)
03107   {
03108     if(mode->bitdepth == 8)
03109     {
03110       *r = *g = *b = in[i];
03111       if(mode->key_defined && *r == mode->key_r) *a = 0;
03112       else *a = 255;
03113     }
03114     else if(mode->bitdepth == 16)
03115     {
03116       *r = *g = *b = in[i * 2 + 0];
03117       if(mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r) *a = 0;
03118       else *a = 255;
03119     }
03120     else
03121     {
03122       unsigned highest = ((1U << mode->bitdepth) - 1U); /*highest possible value for this bit depth*/
03123       size_t j = i * mode->bitdepth;
03124       unsigned value = readBitsFromReversedStream(&j, in, mode->bitdepth);
03125       *r = *g = *b = (value * 255) / highest;
03126       if(mode->key_defined && value == mode->key_r) *a = 0;
03127       else *a = 255;
03128     }
03129   }
03130   else if(mode->colortype == LCT_RGB)
03131   {
03132     if(mode->bitdepth == 8)
03133     {
03134       *r = in[i * 3 + 0]; *g = in[i * 3 + 1]; *b = in[i * 3 + 2];
03135       if(mode->key_defined && *r == mode->key_r && *g == mode->key_g && *b == mode->key_b) *a = 0;
03136       else *a = 255;
03137     }
03138     else
03139     {
03140       *r = in[i * 6 + 0];
03141       *g = in[i * 6 + 2];
03142       *b = in[i * 6 + 4];
03143       if(mode->key_defined && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
03144          && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
03145          && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b) *a = 0;
03146       else *a = 255;
03147     }
03148   }
03149   else if(mode->colortype == LCT_PALETTE)
03150   {
03151     unsigned index;
03152     if(mode->bitdepth == 8) index = in[i];
03153     else
03154     {
03155       size_t j = i * mode->bitdepth;
03156       index = readBitsFromReversedStream(&j, in, mode->bitdepth);
03157     }
03158 
03159     if(index >= mode->palettesize)
03160     {
03161       /*This is an error according to the PNG spec, but fix_png can ignore it*/
03162       if(!fix_png) return (mode->bitdepth == 8 ? 46 : 47); /*index out of palette*/
03163       *r = *g = *b = 0;
03164       *a = 255;
03165     }
03166     else
03167     {
03168       *r = mode->palette[index * 4 + 0];
03169       *g = mode->palette[index * 4 + 1];
03170       *b = mode->palette[index * 4 + 2];
03171       *a = mode->palette[index * 4 + 3];
03172     }
03173   }
03174   else if(mode->colortype == LCT_GREY_ALPHA)
03175   {
03176     if(mode->bitdepth == 8)
03177     {
03178       *r = *g = *b = in[i * 2 + 0];
03179       *a = in[i * 2 + 1];
03180     }
03181     else
03182     {
03183       *r = *g = *b = in[i * 4 + 0];
03184       *a = in[i * 4 + 2];
03185     }
03186   }
03187   else if(mode->colortype == LCT_RGBA)
03188   {
03189     if(mode->bitdepth == 8)
03190     {
03191       *r = in[i * 4 + 0];
03192       *g = in[i * 4 + 1];
03193       *b = in[i * 4 + 2];
03194       *a = in[i * 4 + 3];
03195     }
03196     else
03197     {
03198       *r = in[i * 8 + 0];
03199       *g = in[i * 8 + 2];
03200       *b = in[i * 8 + 4];
03201       *a = in[i * 8 + 6];
03202     }
03203   }
03204 
03205   return 0; /*no error*/
03206 }
03207 
03208 /*Similar to getPixelColorRGBA8, but with all the for loops inside of the color
03209 mode test cases, optimized to convert the colors much faster, when converting
03210 to RGBA or RGB with 8 bit per cannel. buffer must be RGBA or RGB output with
03211 enough memory, if has_alpha is true the output is RGBA. mode has the color mode
03212 of the input buffer.*/
03213 static unsigned getPixelColorsRGBA8(unsigned char* buffer, size_t numpixels,
03214                                     unsigned has_alpha, const unsigned char* in,
03215                                     const LodePNGColorMode* mode,
03216                                     unsigned fix_png)
03217 {
03218   unsigned num_channels = has_alpha ? 4 : 3;
03219   size_t i;
03220   if(mode->colortype == LCT_GREY)
03221   {
03222     if(mode->bitdepth == 8)
03223     {
03224       for(i = 0; i < numpixels; i++, buffer += num_channels)
03225       {
03226         buffer[0] = buffer[1] = buffer[2] = in[i];
03227         if(has_alpha) buffer[3] = mode->key_defined && in[i] == mode->key_r ? 0 : 255;
03228       }
03229     }
03230     else if(mode->bitdepth == 16)
03231     {
03232       for(i = 0; i < numpixels; i++, buffer += num_channels)
03233       {
03234         buffer[0] = buffer[1] = buffer[2] = in[i * 2];
03235         if(has_alpha) buffer[3] = mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r ? 0 : 255;
03236       }
03237     }
03238     else
03239     {
03240       unsigned highest = ((1U << mode->bitdepth) - 1U); /*highest possible value for this bit depth*/
03241       size_t j = 0;
03242       for(i = 0; i < numpixels; i++, buffer += num_channels)
03243       {
03244         unsigned value = readBitsFromReversedStream(&j, in, mode->bitdepth);
03245         buffer[0] = buffer[1] = buffer[2] = (value * 255) / highest;
03246         if(has_alpha) buffer[3] = mode->key_defined && value == mode->key_r ? 0 : 255;
03247       }
03248     }
03249   }
03250   else if(mode->colortype == LCT_RGB)
03251   {
03252     if(mode->bitdepth == 8)
03253     {
03254       for(i = 0; i < numpixels; i++, buffer += num_channels)
03255       {
03256         buffer[0] = in[i * 3 + 0];
03257         buffer[1] = in[i * 3 + 1];
03258         buffer[2] = in[i * 3 + 2];
03259         if(has_alpha) buffer[3] = mode->key_defined && buffer[0] == mode->key_r
03260            && buffer[1]== mode->key_g && buffer[2] == mode->key_b ? 0 : 255;
03261       }
03262     }
03263     else
03264     {
03265       for(i = 0; i < numpixels; i++, buffer += num_channels)
03266       {
03267         buffer[0] = in[i * 6 + 0];
03268         buffer[1] = in[i * 6 + 2];
03269         buffer[2] = in[i * 6 + 4];
03270         if(has_alpha) buffer[3] = mode->key_defined
03271            && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
03272            && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
03273            && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b ? 0 : 255;
03274       }
03275     }
03276   }
03277   else if(mode->colortype == LCT_PALETTE)
03278   {
03279     unsigned index;
03280     size_t j = 0;
03281     for(i = 0; i < numpixels; i++, buffer += num_channels)
03282     {
03283       if(mode->bitdepth == 8) index = in[i];
03284       else index = readBitsFromReversedStream(&j, in, mode->bitdepth);
03285 
03286       if(index >= mode->palettesize)
03287       {
03288         /*This is an error according to the PNG spec, but fix_png can ignore it*/
03289         if(!fix_png) return (mode->bitdepth == 8 ? 46 : 47); /*index out of palette*/
03290         buffer[0] = buffer[1] = buffer[2] = 0;
03291         if(has_alpha) buffer[3] = 255;
03292       }
03293       else
03294       {
03295         buffer[0] = mode->palette[index * 4 + 0];
03296         buffer[1] = mode->palette[index * 4 + 1];
03297         buffer[2] = mode->palette[index * 4 + 2];
03298         if(has_alpha) buffer[3] = mode->palette[index * 4 + 3];
03299       }
03300     }
03301   }
03302   else if(mode->colortype == LCT_GREY_ALPHA)
03303   {
03304     if(mode->bitdepth == 8)
03305     {
03306       for(i = 0; i < numpixels; i++, buffer += num_channels)
03307       {
03308         buffer[0] = buffer[1] = buffer[2] = in[i * 2 + 0];
03309         if(has_alpha) buffer[3] = in[i * 2 + 1];
03310       }
03311     }
03312     else
03313     {
03314       for(i = 0; i < numpixels; i++, buffer += num_channels)
03315       {
03316         buffer[0] = buffer[1] = buffer[2] = in[i * 4 + 0];
03317         if(has_alpha) buffer[3] = in[i * 4 + 2];
03318       }
03319     }
03320   }
03321   else if(mode->colortype == LCT_RGBA)
03322   {
03323     if(mode->bitdepth == 8)
03324     {
03325       for(i = 0; i < numpixels; i++, buffer += num_channels)
03326       {
03327         buffer[0] = in[i * 4 + 0];
03328         buffer[1] = in[i * 4 + 1];
03329         buffer[2] = in[i * 4 + 2];
03330         if(has_alpha) buffer[3] = in[i * 4 + 3];
03331       }
03332     }
03333     else
03334     {
03335       for(i = 0; i < numpixels; i++, buffer += num_channels)
03336       {
03337         buffer[0] = in[i * 8 + 0];
03338         buffer[1] = in[i * 8 + 2];
03339         buffer[2] = in[i * 8 + 4];
03340         if(has_alpha) buffer[3] = in[i * 8 + 6];
03341       }
03342     }
03343   }
03344 
03345   return 0; /*no error*/
03346 }
03347 
03348 /*Get RGBA16 color of pixel with index i (y * width + x) from the raw image with
03349 given color type, but the given color type must be 16-bit itself.*/
03350 static unsigned getPixelColorRGBA16(unsigned short* r, unsigned short* g, unsigned short* b, unsigned short* a,
03351                                     const unsigned char* in, size_t i, const LodePNGColorMode* mode)
03352 {
03353   if(mode->bitdepth != 16) return 85; /*error: this function only supports 16-bit input*/
03354 
03355   if(mode->colortype == LCT_GREY)
03356   {
03357     *r = *g = *b = 256 * in[i * 2 + 0] + in[i * 2 + 1];
03358     if(mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r) *a = 0;
03359     else *a = 65535;
03360   }
03361   else if(mode->colortype == LCT_RGB)
03362   {
03363     *r = 256 * in[i * 6 + 0] + in[i * 6 + 1];
03364     *g = 256 * in[i * 6 + 2] + in[i * 6 + 3];
03365     *b = 256 * in[i * 6 + 4] + in[i * 6 + 5];
03366     if(mode->key_defined && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
03367        && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
03368        && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b) *a = 0;
03369     else *a = 65535;
03370   }
03371   else if(mode->colortype == LCT_GREY_ALPHA)
03372   {
03373     *r = *g = *b = 256 * in[i * 4 + 0] + in[i * 4 + 1];
03374     *a = 256 * in[i * 4 + 2] + in[i * 4 + 3];
03375   }
03376   else if(mode->colortype == LCT_RGBA)
03377   {
03378     *r = 256 * in[i * 8 + 0] + in[i * 8 + 1];
03379     *g = 256 * in[i * 8 + 2] + in[i * 8 + 3];
03380     *b = 256 * in[i * 8 + 4] + in[i * 8 + 5];
03381     *a = 256 * in[i * 8 + 6] + in[i * 8 + 7];
03382   }
03383   else return 85; /*error: this function only supports 16-bit input, not palettes*/
03384 
03385   return 0; /*no error*/
03386 }
03387 
03388 /*
03389 converts from any color type to 24-bit or 32-bit (later maybe more supported). return value = LodePNG error code
03390 the out buffer must have (w * h * bpp + 7) / 8 bytes, where bpp is the bits per pixel of the output color type
03391 (lodepng_get_bpp) for < 8 bpp images, there may _not_ be padding bits at the end of scanlines.
03392 */
03393 unsigned lodepng_convert(unsigned char* out, const unsigned char* in,
03394                          LodePNGColorMode* mode_out, const LodePNGColorMode* mode_in,
03395                          unsigned w, unsigned h, unsigned fix_png)
03396 {
03397   unsigned error = 0;
03398   size_t i;
03399   ColorTree tree;
03400   size_t numpixels = w * h;
03401 
03402   if(lodepng_color_mode_equal(mode_out, mode_in))
03403   {
03404     size_t numbytes = lodepng_get_raw_size(w, h, mode_in);
03405     for(i = 0; i < numbytes; i++) out[i] = in[i];
03406     return error;
03407   }
03408 
03409   if(mode_out->colortype == LCT_PALETTE)
03410   {
03411     size_t palsize = 1 << mode_out->bitdepth;
03412     if(mode_out->palettesize < palsize) palsize = mode_out->palettesize;
03413     color_tree_init(&tree);
03414     for(i = 0; i < palsize; i++)
03415     {
03416       unsigned char* p = &mode_out->palette[i * 4];
03417       color_tree_add(&tree, p[0], p[1], p[2], p[3], i);
03418     }
03419   }
03420 
03421   if(mode_in->bitdepth == 16 && mode_out->bitdepth == 16)
03422   {
03423     for(i = 0; i < numpixels; i++)
03424     {
03425       unsigned short r = 0, g = 0, b = 0, a = 0;
03426       error = getPixelColorRGBA16(&r, &g, &b, &a, in, i, mode_in);
03427       if(error) break;
03428       error = rgba16ToPixel(out, i, mode_out, r, g, b, a);
03429       if(error) break;
03430     }
03431   }
03432   else if(mode_out->bitdepth == 8 && mode_out->colortype == LCT_RGBA)
03433   {
03434     error = getPixelColorsRGBA8(out, numpixels, 1, in, mode_in, fix_png);
03435   }
03436   else if(mode_out->bitdepth == 8 && mode_out->colortype == LCT_RGB)
03437   {
03438     error = getPixelColorsRGBA8(out, numpixels, 0, in, mode_in, fix_png);
03439   }
03440   else
03441   {
03442     unsigned char r = 0, g = 0, b = 0, a = 0;
03443     for(i = 0; i < numpixels; i++)
03444     {
03445       error = getPixelColorRGBA8(&r, &g, &b, &a, in, i, mode_in, fix_png);
03446       if(error) break;
03447       error = rgba8ToPixel(out, i, mode_out, &tree, r, g, b, a);
03448       if(error) break;
03449     }
03450   }
03451 
03452   if(mode_out->colortype == LCT_PALETTE)
03453   {
03454     color_tree_cleanup(&tree);
03455   }
03456 
03457   return error;
03458 }
03459 
03460 #ifdef LODEPNG_COMPILE_ENCODER
03461 
03462 typedef struct ColorProfile
03463 {
03464   unsigned char sixteenbit; /*needs more than 8 bits per channel*/
03465   unsigned char sixteenbit_done;
03466 
03467 
03468   unsigned char colored; /*not greyscale*/
03469   unsigned char colored_done;
03470 
03471   unsigned char key; /*a color key is required, or more*/
03472   unsigned short key_r; /*these values are always in 16-bit bitdepth in the profile*/
03473   unsigned short key_g;
03474   unsigned short key_b;
03475   unsigned char alpha; /*alpha channel, or alpha palette, required*/
03476   unsigned char alpha_done;
03477 
03478   unsigned numcolors;
03479   ColorTree tree; /*for listing the counted colors, up to 256*/
03480   unsigned char* palette; /*size 1024. Remember up to the first 256 RGBA colors*/
03481   unsigned maxnumcolors; /*if more than that amount counted*/
03482   unsigned char numcolors_done;
03483 
03484   unsigned greybits; /*amount of bits required for greyscale (1, 2, 4, 8). Does not take 16 bit into account.*/
03485   unsigned char greybits_done;
03486 
03487 } ColorProfile;
03488 
03489 static void color_profile_init(ColorProfile* profile, const LodePNGColorMode* mode)
03490 {
03491   profile->sixteenbit = 0;
03492   profile->sixteenbit_done = mode->bitdepth == 16 ? 0 : 1;
03493 
03494   profile->colored = 0;
03495   profile->colored_done = lodepng_is_greyscale_type(mode) ? 1 : 0;
03496 
03497   profile->key = 0;
03498   profile->alpha = 0;
03499   profile->alpha_done = lodepng_can_have_alpha(mode) ? 0 : 1;
03500 
03501   profile->numcolors = 0;
03502   color_tree_init(&profile->tree);
03503   profile->palette = (unsigned char*)lodepng_malloc(1024);
03504   profile->maxnumcolors = 257;
03505   if(lodepng_get_bpp(mode) <= 8)
03506   {
03507     int bpp = lodepng_get_bpp(mode);
03508     profile->maxnumcolors = bpp == 1 ? 2 : (bpp == 2 ? 4 : (bpp == 4 ? 16 : 256));
03509   }
03510   profile->numcolors_done = 0;
03511 
03512   profile->greybits = 1;
03513   profile->greybits_done = lodepng_get_bpp(mode) == 1 ? 1 : 0;
03514 }
03515 
03516 static void color_profile_cleanup(ColorProfile* profile)
03517 {
03518   color_tree_cleanup(&profile->tree);
03519   lodepng_free(profile->palette);
03520 }
03521 
03522 /*function used for debug purposes with C++*/
03523 /*void printColorProfile(ColorProfile* p)
03524 {
03525   std::cout << "sixteenbit: " << (int)p->sixteenbit << std::endl;
03526   std::cout << "sixteenbit_done: " << (int)p->sixteenbit_done << std::endl;
03527   std::cout << "colored: " << (int)p->colored << std::endl;
03528   std::cout << "colored_done: " << (int)p->colored_done << std::endl;
03529   std::cout << "key: " << (int)p->key << std::endl;
03530   std::cout << "key_r: " << (int)p->key_r << std::endl;
03531   std::cout << "key_g: " << (int)p->key_g << std::endl;
03532   std::cout << "key_b: " << (int)p->key_b << std::endl;
03533   std::cout << "alpha: " << (int)p->alpha << std::endl;
03534   std::cout << "alpha_done: " << (int)p->alpha_done << std::endl;
03535   std::cout << "numcolors: " << (int)p->numcolors << std::endl;
03536   std::cout << "maxnumcolors: " << (int)p->maxnumcolors << std::endl;
03537   std::cout << "numcolors_done: " << (int)p->numcolors_done << std::endl;
03538   std::cout << "greybits: " << (int)p->greybits << std::endl;
03539   std::cout << "greybits_done: " << (int)p->greybits_done << std::endl;
03540 }*/
03541 
03542 /*Returns how many bits needed to represent given value (max 8 bit)*/
03543 unsigned getValueRequiredBits(unsigned short value)
03544 {
03545   if(value == 0 || value == 255) return 1;
03546   /*The scaling of 2-bit and 4-bit values uses multiples of 85 and 17*/
03547   if(value % 17 == 0) return value % 85 == 0 ? 2 : 4;
03548   return 8;
03549 }
03550 
03551 /*profile must already have been inited with mode.
03552 It's ok to set some parameters of profile to done already.*/
03553 static unsigned get_color_profile(ColorProfile* profile,
03554                                   const unsigned char* in,
03555                                   size_t numpixels /*must be full image size, for certain filesize based choices*/,
03556                                   const LodePNGColorMode* mode,
03557                                   unsigned fix_png)
03558 {
03559   unsigned error = 0;
03560   size_t i;
03561 
03562   if(mode->bitdepth == 16)
03563   {
03564     for(i = 0; i < numpixels; i++)
03565     {
03566       unsigned short r, g, b, a;
03567       error = getPixelColorRGBA16(&r, &g, &b, &a, in, i, mode);
03568       if(error) break;
03569 
03570       /*a color is considered good for 8-bit if the first byte and the second byte are equal,
03571         (so if it's divisible through 257), NOT necessarily if the second byte is 0*/
03572       if(!profile->sixteenbit_done
03573           && (((r & 255) != ((r >> 8) & 255))
03574            || ((g & 255) != ((g >> 8) & 255))
03575            || ((b & 255) != ((b >> 8) & 255))))
03576       {
03577         profile->sixteenbit = 1;
03578         profile->sixteenbit_done = 1;
03579         profile->greybits_done = 1; /*greybits is not applicable anymore at 16-bit*/
03580         profile->numcolors_done = 1; /*counting colors no longer useful, palette doesn't support 16-bit*/
03581       }
03582 
03583       if(!profile->colored_done && (r != g || r != b))
03584       {
03585         profile->colored = 1;
03586         profile->colored_done = 1;
03587         profile->greybits_done = 1; /*greybits is not applicable anymore*/
03588       }
03589 
03590       if(!profile->alpha_done && a != 65535)
03591       {
03592         /*only use color key if numpixels large enough to justify tRNS chunk size*/
03593         if(a == 0 && numpixels > 16 && !(profile->key && (r != profile->key_r || g != profile->key_g || b != profile->key_b)))
03594         {
03595           if(!profile->alpha && !profile->key)
03596           {
03597             profile->key = 1;
03598             profile->key_r = r;
03599             profile->key_g = g;
03600             profile->key_b = b;
03601           }
03602         }
03603         else
03604         {
03605           profile->alpha = 1;
03606           profile->alpha_done = 1;
03607           profile->greybits_done = 1; /*greybits is not applicable anymore*/
03608         }
03609       }
03610 
03611       /* Color key cannot be used if an opaque pixel also has that RGB color. */
03612       if(!profile->alpha_done && a == 65535 && profile->key
03613           && r == profile->key_r && g == profile->key_g && b == profile->key_b)
03614       {
03615           profile->alpha = 1;
03616           profile->alpha_done = 1;
03617           profile->greybits_done = 1; /*greybits is not applicable anymore*/
03618       }
03619 
03620       if(!profile->greybits_done)
03621       {
03622         /*assuming 8-bit r, this test does not care about 16-bit*/
03623         unsigned bits = getValueRequiredBits(r);
03624         if(bits > profile->greybits) profile->greybits = bits;
03625         if(profile->greybits >= 8) profile->greybits_done = 1;
03626       }
03627 
03628       if(!profile->numcolors_done)
03629       {
03630         /*assuming 8-bit rgba, this test does not care about 16-bit*/
03631         if(!color_tree_has(&profile->tree, (unsigned char)r, (unsigned char)g, (unsigned char)b, (unsigned char)a))
03632         {
03633           color_tree_add(&profile->tree, (unsigned char)r, (unsigned char)g, (unsigned char)b, (unsigned char)a,
03634             profile->numcolors);
03635           if(profile->numcolors < 256)
03636           {
03637             unsigned char* p = profile->palette;
03638             unsigned i = profile->numcolors;
03639             p[i * 4 + 0] = (unsigned char)r;
03640             p[i * 4 + 1] = (unsigned char)g;
03641             p[i * 4 + 2] = (unsigned char)b;
03642             p[i * 4 + 3] = (unsigned char)a;
03643           }
03644           profile->numcolors++;
03645           if(profile->numcolors >= profile->maxnumcolors) profile->numcolors_done = 1;
03646         }
03647       }
03648 
03649       if(profile->alpha_done && profile->numcolors_done
03650       && profile->colored_done && profile->sixteenbit_done && profile->greybits_done)
03651       {
03652         break;
03653       }
03654     };
03655   }
03656   else /* < 16-bit */
03657   {
03658     for(i = 0; i < numpixels; i++)
03659     {
03660       unsigned char r = 0, g = 0, b = 0, a = 0;
03661       error = getPixelColorRGBA8(&r, &g, &b, &a, in, i, mode, fix_png);
03662       if(error) break;
03663 
03664       if(!profile->colored_done && (r != g || r != b))
03665       {
03666         profile->colored = 1;
03667         profile->colored_done = 1;
03668         profile->greybits_done = 1; /*greybits is not applicable anymore*/
03669       }
03670 
03671       if(!profile->alpha_done && a != 255)
03672       {
03673         if(a == 0 && !(profile->key && (r != profile->key_r || g != profile->key_g || b != profile->key_b)))
03674         {
03675           if(!profile->key)
03676           {
03677             profile->key = 1;
03678             profile->key_r = r;
03679             profile->key_g = g;
03680             profile->key_b = b;
03681           }
03682         }
03683         else
03684         {
03685           profile->alpha = 1;
03686           profile->alpha_done = 1;
03687           profile->greybits_done = 1; /*greybits is not applicable anymore*/
03688         }
03689       }
03690 
03691       /* Color key cannot be used if an opaque pixel also has that RGB color. */
03692       if(!profile->alpha_done && a == 255 && profile->key
03693           && r == profile->key_r && g == profile->key_g && b == profile->key_b)
03694       {
03695           profile->alpha = 1;
03696           profile->alpha_done = 1;
03697           profile->greybits_done = 1; /*greybits is not applicable anymore*/
03698       }
03699 
03700       if(!profile->greybits_done)
03701       {
03702         unsigned bits = getValueRequiredBits(r);
03703         if(bits > profile->greybits) profile->greybits = bits;
03704         if(profile->greybits >= 8) profile->greybits_done = 1;
03705       }
03706 
03707       if(!profile->numcolors_done)
03708       {
03709         if(!color_tree_has(&profile->tree, r, g, b, a))
03710         {
03711 
03712           color_tree_add(&profile->tree, r, g, b, a, profile->numcolors);
03713           if(profile->numcolors < 256)
03714           {
03715             unsigned char* p = profile->palette;
03716             unsigned i = profile->numcolors;
03717             p[i * 4 + 0] = r;
03718             p[i * 4 + 1] = g;
03719             p[i * 4 + 2] = b;
03720             p[i * 4 + 3] = a;
03721           }
03722           profile->numcolors++;
03723           if(profile->numcolors >= profile->maxnumcolors) profile->numcolors_done = 1;
03724         }
03725       }
03726 
03727       if(profile->alpha_done && profile->numcolors_done && profile->colored_done && profile->greybits_done)
03728       {
03729         break;
03730       }
03731     };
03732   }
03733 
03734   /*make the profile's key always 16-bit for consistency*/
03735   if(mode->bitdepth < 16)
03736   {
03737     /*repeat each byte twice*/
03738     profile->key_r *= 257;
03739     profile->key_g *= 257;
03740     profile->key_b *= 257;
03741   }
03742 
03743   return error;
03744 }
03745 
03746 static void setColorKeyFrom16bit(LodePNGColorMode* mode_out, unsigned r, unsigned g, unsigned b, unsigned bitdepth)
03747 {
03748   unsigned mask = (1 << bitdepth) - 1;
03749   mode_out->key_defined = 1;
03750   mode_out->key_r = r & mask;
03751   mode_out->key_g = g & mask;
03752   mode_out->key_b = b & mask;
03753 }
03754 
03755 /*updates values of mode with a potentially smaller color model. mode_out should
03756 contain the user chosen color model, but will be overwritten with the new chosen one.*/
03757 unsigned lodepng_auto_choose_color(LodePNGColorMode* mode_out,
03758                                    const unsigned char* image, unsigned w, unsigned h,
03759                                    const LodePNGColorMode* mode_in,
03760                                    LodePNGAutoConvert auto_convert)
03761 {
03762   ColorProfile profile;
03763   unsigned error = 0;
03764   int no_nibbles = auto_convert == LAC_AUTO_NO_NIBBLES || auto_convert == LAC_AUTO_NO_NIBBLES_NO_PALETTE;
03765   int no_palette = auto_convert == LAC_AUTO_NO_PALETTE || auto_convert == LAC_AUTO_NO_NIBBLES_NO_PALETTE;
03766 
03767   if(auto_convert == LAC_ALPHA)
03768   {
03769     if(mode_out->colortype != LCT_RGBA && mode_out->colortype != LCT_GREY_ALPHA) return 0;
03770   }
03771 
03772   color_profile_init(&profile, mode_in);
03773   if(auto_convert == LAC_ALPHA)
03774   {
03775     profile.colored_done = 1;
03776     profile.greybits_done = 1;
03777     profile.numcolors_done = 1;
03778     profile.sixteenbit_done = 1;
03779   }
03780   error = get_color_profile(&profile, image, w * h, mode_in, 0 /*fix_png*/);
03781   if(!error && auto_convert == LAC_ALPHA)
03782   {
03783     if(!profile.alpha)
03784     {
03785       mode_out->colortype = (mode_out->colortype == LCT_RGBA ? LCT_RGB : LCT_GREY);
03786       if(profile.key) setColorKeyFrom16bit(mode_out, profile.key_r, profile.key_g, profile.key_b, mode_out->bitdepth);
03787     }
03788   }
03789   else if(!error && auto_convert != LAC_ALPHA)
03790   {
03791     mode_out->key_defined = 0;
03792 
03793     if(profile.sixteenbit)
03794     {
03795       mode_out->bitdepth = 16;
03796       if(profile.alpha)
03797       {
03798         mode_out->colortype = profile.colored ? LCT_RGBA : LCT_GREY_ALPHA;
03799       }
03800       else
03801       {
03802         mode_out->colortype = profile.colored ? LCT_RGB : LCT_GREY;
03803         if(profile.key) setColorKeyFrom16bit(mode_out, profile.key_r, profile.key_g, profile.key_b, mode_out->bitdepth);
03804       }
03805     }
03806     else /*less than 16 bits per channel*/
03807     {
03808       /*don't add palette overhead if image hasn't got a lot of pixels*/
03809       unsigned n = profile.numcolors;
03810       int palette_ok = !no_palette && n <= 256 && (n * 2 < w * h);
03811       unsigned palettebits = n <= 2 ? 1 : (n <= 4 ? 2 : (n <= 16 ? 4 : 8));
03812       int grey_ok = !profile.colored && !profile.alpha; /*grey without alpha, with potentially low bits*/
03813       if(palette_ok || grey_ok)
03814       {
03815         if(!palette_ok || (grey_ok && profile.greybits <= palettebits))
03816         {
03817           unsigned grey = profile.key_r;
03818           mode_out->colortype = LCT_GREY;
03819           mode_out->bitdepth = profile.greybits;
03820           if(profile.key) setColorKeyFrom16bit(mode_out, grey, grey, grey, mode_out->bitdepth);
03821         }
03822         else
03823         {
03824           /*fill in the palette*/
03825           unsigned i;
03826           unsigned char* p = profile.palette;
03827           /*remove potential earlier palette*/
03828           lodepng_palette_clear(mode_out);
03829           for(i = 0; i < profile.numcolors; i++)
03830           {
03831             error = lodepng_palette_add(mode_out, p[i * 4 + 0], p[i * 4 + 1], p[i * 4 + 2], p[i * 4 + 3]);
03832             if(error) break;
03833           }
03834 
03835           mode_out->colortype = LCT_PALETTE;
03836           mode_out->bitdepth = palettebits;
03837         }
03838       }
03839       else /*8-bit per channel*/
03840       {
03841         mode_out->bitdepth = 8;
03842         if(profile.alpha)
03843         {
03844           mode_out->colortype = profile.colored ? LCT_RGBA : LCT_GREY_ALPHA;
03845         }
03846         else
03847         {
03848           mode_out->colortype = profile.colored ? LCT_RGB : LCT_GREY /*LCT_GREY normally won't occur, already done earlier*/;
03849           if(profile.key) setColorKeyFrom16bit(mode_out, profile.key_r, profile.key_g, profile.key_b, mode_out->bitdepth);
03850         }
03851       }
03852     }
03853   }
03854 
03855   color_profile_cleanup(&profile);
03856 
03857   if(mode_out->colortype == LCT_PALETTE && mode_in->palettesize == mode_out->palettesize)
03858   {
03859     /*In this case keep the palette order of the input, so that the user can choose an optimal one*/
03860     size_t i;
03861     for(i = 0; i < mode_in->palettesize * 4; i++)
03862     {
03863       mode_out->palette[i] = mode_in->palette[i];
03864     }
03865   }
03866 
03867   if(no_nibbles && mode_out->bitdepth < 8)
03868   {
03869     /*palette can keep its small amount of colors, as long as no indices use it*/
03870     mode_out->bitdepth = 8;
03871   }
03872 
03873   return error;
03874 }
03875 
03876 #endif /* #ifdef LODEPNG_COMPILE_ENCODER */
03877 
03878 /*
03879 Paeth predicter, used by PNG filter type 4
03880 The parameters are of type short, but should come from unsigned chars, the shorts
03881 are only needed to make the paeth calculation correct.
03882 */
03883 static unsigned char paethPredictor(short a, short b, short c)
03884 {
03885   short pa = abs(b - c);
03886   short pb = abs(a - c);
03887   short pc = abs(a + b - c - c);
03888 
03889   if(pc < pa && pc < pb) return (unsigned char)c;
03890   else if(pb < pa) return (unsigned char)b;
03891   else return (unsigned char)a;
03892 }
03893 
03894 /*shared values used by multiple Adam7 related functions*/
03895 
03896 static const unsigned ADAM7_IX[7] = { 0, 4, 0, 2, 0, 1, 0 }; /*x start values*/
03897 static const unsigned ADAM7_IY[7] = { 0, 0, 4, 0, 2, 0, 1 }; /*y start values*/
03898 static const unsigned ADAM7_DX[7] = { 8, 8, 4, 4, 2, 2, 1 }; /*x delta values*/
03899 static const unsigned ADAM7_DY[7] = { 8, 8, 8, 4, 4, 2, 2 }; /*y delta values*/
03900 
03901 /*
03902 Outputs various dimensions and positions in the image related to the Adam7 reduced images.
03903 passw: output containing the width of the 7 passes
03904 passh: output containing the height of the 7 passes
03905 filter_passstart: output containing the index of the start and end of each
03906  reduced image with filter bytes
03907 padded_passstart output containing the index of the start and end of each
03908  reduced image when without filter bytes but with padded scanlines
03909 passstart: output containing the index of the start and end of each reduced
03910  image without padding between scanlines, but still padding between the images
03911 w, h: width and height of non-interlaced image
03912 bpp: bits per pixel
03913 "padded" is only relevant if bpp is less than 8 and a scanline or image does not
03914  end at a full byte
03915 */
03916 static void Adam7_getpassvalues(unsigned passw[7], unsigned passh[7], size_t filter_passstart[8],
03917                                 size_t padded_passstart[8], size_t passstart[8], unsigned w, unsigned h, unsigned bpp)
03918 {
03919   /*the passstart values have 8 values: the 8th one indicates the byte after the end of the 7th (= last) pass*/
03920   unsigned i;
03921 
03922   /*calculate width and height in pixels of each pass*/
03923   for(i = 0; i < 7; i++)
03924   {
03925     passw[i] = (w + ADAM7_DX[i] - ADAM7_IX[i] - 1) / ADAM7_DX[i];
03926     passh[i] = (h + ADAM7_DY[i] - ADAM7_IY[i] - 1) / ADAM7_DY[i];
03927     if(passw[i] == 0) passh[i] = 0;
03928     if(passh[i] == 0) passw[i] = 0;
03929   }
03930 
03931   filter_passstart[0] = padded_passstart[0] = passstart[0] = 0;
03932   for(i = 0; i < 7; i++)
03933   {
03934     /*if passw[i] is 0, it's 0 bytes, not 1 (no filtertype-byte)*/
03935     filter_passstart[i + 1] = filter_passstart[i]
03936                             + ((passw[i] && passh[i]) ? passh[i] * (1 + (passw[i] * bpp + 7) / 8) : 0);
03937     /*bits padded if needed to fill full byte at end of each scanline*/
03938     padded_passstart[i + 1] = padded_passstart[i] + passh[i] * ((passw[i] * bpp + 7) / 8);
03939     /*only padded at end of reduced image*/
03940     passstart[i + 1] = passstart[i] + (passh[i] * passw[i] * bpp + 7) / 8;
03941   }
03942 }
03943 
03944 #ifdef LODEPNG_COMPILE_DECODER
03945 
03946 /* ////////////////////////////////////////////////////////////////////////// */
03947 /* / PNG Decoder                                                            / */
03948 /* ////////////////////////////////////////////////////////////////////////// */
03949 
03950 /*read the information from the header and store it in the LodePNGInfo. return value is error*/
03951 unsigned lodepng_inspect(unsigned* w, unsigned* h, LodePNGState* state,
03952                          const unsigned char* in, size_t insize)
03953 {
03954   LodePNGInfo* info = &state->info_png;
03955   if(insize == 0 || in == 0)
03956   {
03957     CERROR_RETURN_ERROR(state->error, 48); /*error: the given data is empty*/
03958   }
03959   if(insize < 29)
03960   {
03961     CERROR_RETURN_ERROR(state->error, 27); /*error: the data length is smaller than the length of a PNG header*/
03962   }
03963 
03964   /*when decoding a new PNG image, make sure all parameters created after previous decoding are reset*/
03965   lodepng_info_cleanup(info);
03966   lodepng_info_init(info);
03967 
03968   if(in[0] != 137 || in[1] != 80 || in[2] != 78 || in[3] != 71
03969      || in[4] != 13 || in[5] != 10 || in[6] != 26 || in[7] != 10)
03970   {
03971     CERROR_RETURN_ERROR(state->error, 28); /*error: the first 8 bytes are not the correct PNG signature*/
03972   }
03973   if(in[12] != 'I' || in[13] != 'H' || in[14] != 'D' || in[15] != 'R')
03974   {
03975     CERROR_RETURN_ERROR(state->error, 29); /*error: it doesn't start with a IHDR chunk!*/
03976   }
03977 
03978   /*read the values given in the header*/
03979   *w = lodepng_read32bitInt(&in[16]);
03980   *h = lodepng_read32bitInt(&in[20]);
03981   info->color.bitdepth = in[24];
03982   info->color.colortype = (LodePNGColorType)in[25];
03983   info->compression_method = in[26];
03984   info->filter_method = in[27];
03985   info->interlace_method = in[28];
03986 
03987   if(!state->decoder.ignore_crc)
03988   {
03989     unsigned CRC = lodepng_read32bitInt(&in[29]);
03990     unsigned checksum = lodepng_crc32(&in[12], 17);
03991     if(CRC != checksum)
03992     {
03993       CERROR_RETURN_ERROR(state->error, 57); /*invalid CRC*/
03994     }
03995   }
03996 
03997   /*error: only compression method 0 is allowed in the specification*/
03998   if(info->compression_method != 0) CERROR_RETURN_ERROR(state->error, 32);
03999   /*error: only filter method 0 is allowed in the specification*/
04000   if(info->filter_method != 0) CERROR_RETURN_ERROR(state->error, 33);
04001   /*error: only interlace methods 0 and 1 exist in the specification*/
04002   if(info->interlace_method > 1) CERROR_RETURN_ERROR(state->error, 34);
04003 
04004   state->error = checkColorValidity(info->color.colortype, info->color.bitdepth);
04005   return state->error;
04006 }
04007 
04008 static unsigned unfilterScanline(unsigned char* recon, const unsigned char* scanline, const unsigned char* precon,
04009                                  size_t bytewidth, unsigned char filterType, size_t length)
04010 {
04011   /*
04012   For PNG filter method 0
04013   unfilter a PNG image scanline by scanline. when the pixels are smaller than 1 byte,
04014   the filter works byte per byte (bytewidth = 1)
04015   precon is the previous unfiltered scanline, recon the result, scanline the current one
04016   the incoming scanlines do NOT include the filtertype byte, that one is given in the parameter filterType instead
04017   recon and scanline MAY be the same memory address! precon must be disjoint.
04018   */
04019 
04020   size_t i;
04021   switch(filterType)
04022   {
04023     case 0:
04024       for(i = 0; i < length; i++) recon[i] = scanline[i];
04025       break;
04026     case 1:
04027       for(i = 0; i < bytewidth; i++) recon[i] = scanline[i];
04028       for(i = bytewidth; i < length; i++) recon[i] = scanline[i] + recon[i - bytewidth];
04029       break;
04030     case 2:
04031       if(precon)
04032       {
04033         for(i = 0; i < length; i++) recon[i] = scanline[i] + precon[i];
04034       }
04035       else
04036       {
04037         for(i = 0; i < length; i++) recon[i] = scanline[i];
04038       }
04039       break;
04040     case 3:
04041       if(precon)
04042       {
04043         for(i = 0; i < bytewidth; i++) recon[i] = scanline[i] + precon[i] / 2;
04044         for(i = bytewidth; i < length; i++) recon[i] = scanline[i] + ((recon[i - bytewidth] + precon[i]) / 2);
04045       }
04046       else
04047       {
04048         for(i = 0; i < bytewidth; i++) recon[i] = scanline[i];
04049         for(i = bytewidth; i < length; i++) recon[i] = scanline[i] + recon[i - bytewidth] / 2;
04050       }
04051       break;
04052     case 4:
04053       if(precon)
04054       {
04055         for(i = 0; i < bytewidth; i++)
04056         {
04057           recon[i] = (scanline[i] + precon[i]); /*paethPredictor(0, precon[i], 0) is always precon[i]*/
04058         }
04059         for(i = bytewidth; i < length; i++)
04060         {
04061           recon[i] = (scanline[i] + paethPredictor(recon[i - bytewidth], precon[i], precon[i - bytewidth]));
04062         }
04063       }
04064       else
04065       {
04066         for(i = 0; i < bytewidth; i++)
04067         {
04068           recon[i] = scanline[i];
04069         }
04070         for(i = bytewidth; i < length; i++)
04071         {
04072           /*paethPredictor(recon[i - bytewidth], 0, 0) is always recon[i - bytewidth]*/
04073           recon[i] = (scanline[i] + recon[i - bytewidth]);
04074         }
04075       }
04076       break;
04077     default: return 36; /*error: unexisting filter type given*/
04078   }
04079   return 0;
04080 }
04081 
04082 static unsigned unfilter(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
04083 {
04084   /*
04085   For PNG filter method 0
04086   this function unfilters a single image (e.g. without interlacing this is called once, with Adam7 seven times)
04087   out must have enough bytes allocated already, in must have the scanlines + 1 filtertype byte per scanline
04088   w and h are image dimensions or dimensions of reduced image, bpp is bits per pixel
04089   in and out are allowed to be the same memory address (but aren't the same size since in has the extra filter bytes)
04090   */
04091 
04092   unsigned y;
04093   unsigned char* prevline = 0;
04094 
04095   /*bytewidth is used for filtering, is 1 when bpp < 8, number of bytes per pixel otherwise*/
04096   size_t bytewidth = (bpp + 7) / 8;
04097   size_t linebytes = (w * bpp + 7) / 8;
04098 
04099   for(y = 0; y < h; y++)
04100   {
04101     size_t outindex = linebytes * y;
04102     size_t inindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
04103     unsigned char filterType = in[inindex];
04104 
04105     CERROR_TRY_RETURN(unfilterScanline(&out[outindex], &in[inindex + 1], prevline, bytewidth, filterType, linebytes));
04106 
04107     prevline = &out[outindex];
04108   }
04109 
04110   return 0;
04111 }
04112 
04113 /*
04114 in: Adam7 interlaced image, with no padding bits between scanlines, but between
04115  reduced images so that each reduced image starts at a byte.
04116 out: the same pixels, but re-ordered so that they're now a non-interlaced image with size w*h
04117 bpp: bits per pixel
04118 out has the following size in bits: w * h * bpp.
04119 in is possibly bigger due to padding bits between reduced images.
04120 out must be big enough AND must be 0 everywhere if bpp < 8 in the current implementation
04121 (because that's likely a little bit faster)
04122 NOTE: comments about padding bits are only relevant if bpp < 8
04123 */
04124 static void Adam7_deinterlace(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
04125 {
04126   unsigned passw[7], passh[7];
04127   size_t filter_passstart[8], padded_passstart[8], passstart[8];
04128   unsigned i;
04129 
04130   Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
04131 
04132   if(bpp >= 8)
04133   {
04134     for(i = 0; i < 7; i++)
04135     {
04136       unsigned x, y, b;
04137       size_t bytewidth = bpp / 8;
04138       for(y = 0; y < passh[i]; y++)
04139       for(x = 0; x < passw[i]; x++)
04140       {
04141         size_t pixelinstart = passstart[i] + (y * passw[i] + x) * bytewidth;
04142         size_t pixeloutstart = ((ADAM7_IY[i] + y * ADAM7_DY[i]) * w + ADAM7_IX[i] + x * ADAM7_DX[i]) * bytewidth;
04143         for(b = 0; b < bytewidth; b++)
04144         {
04145           out[pixeloutstart + b] = in[pixelinstart + b];
04146         }
04147       }
04148     }
04149   }
04150   else /*bpp < 8: Adam7 with pixels < 8 bit is a bit trickier: with bit pointers*/
04151   {
04152     for(i = 0; i < 7; i++)
04153     {
04154       unsigned x, y, b;
04155       unsigned ilinebits = bpp * passw[i];
04156       unsigned olinebits = bpp * w;
04157       size_t obp, ibp; /*bit pointers (for out and in buffer)*/
04158       for(y = 0; y < passh[i]; y++)
04159       for(x = 0; x < passw[i]; x++)
04160       {
04161         ibp = (8 * passstart[i]) + (y * ilinebits + x * bpp);
04162         obp = (ADAM7_IY[i] + y * ADAM7_DY[i]) * olinebits + (ADAM7_IX[i] + x * ADAM7_DX[i]) * bpp;
04163         for(b = 0; b < bpp; b++)
04164         {
04165           unsigned char bit = readBitFromReversedStream(&ibp, in);
04166           /*note that this function assumes the out buffer is completely 0, use setBitOfReversedStream otherwise*/
04167           setBitOfReversedStream0(&obp, out, bit);
04168         }
04169       }
04170     }
04171   }
04172 }
04173 
04174 static void removePaddingBits(unsigned char* out, const unsigned char* in,
04175                               size_t olinebits, size_t ilinebits, unsigned h)
04176 {
04177   /*
04178   After filtering there are still padding bits if scanlines have non multiple of 8 bit amounts. They need
04179   to be removed (except at last scanline of (Adam7-reduced) image) before working with pure image buffers
04180   for the Adam7 code, the color convert code and the output to the user.
04181   in and out are allowed to be the same buffer, in may also be higher but still overlapping; in must
04182   have >= ilinebits*h bits, out must have >= olinebits*h bits, olinebits must be <= ilinebits
04183   also used to move bits after earlier such operations happened, e.g. in a sequence of reduced images from Adam7
04184   only useful if (ilinebits - olinebits) is a value in the range 1..7
04185   */
04186   unsigned y;
04187   size_t diff = ilinebits - olinebits;
04188   size_t ibp = 0, obp = 0; /*input and output bit pointers*/
04189   for(y = 0; y < h; y++)
04190   {
04191     size_t x;
04192     for(x = 0; x < olinebits; x++)
04193     {
04194       unsigned char bit = readBitFromReversedStream(&ibp, in);
04195       setBitOfReversedStream(&obp, out, bit);
04196     }
04197     ibp += diff;
04198   }
04199 }
04200 
04201 /*out must be buffer big enough to contain full image, and in must contain the full decompressed data from
04202 the IDAT chunks (with filter index bytes and possible padding bits)
04203 return value is error*/
04204 static unsigned postProcessScanlines(unsigned char* out, unsigned char* in,
04205                                      unsigned w, unsigned h, const LodePNGInfo* info_png)
04206 {
04207   /*
04208   This function converts the filtered-padded-interlaced data into pure 2D image buffer with the PNG's colortype.
04209   Steps:
04210   *) if no Adam7: 1) unfilter 2) remove padding bits (= posible extra bits per scanline if bpp < 8)
04211   *) if adam7: 1) 7x unfilter 2) 7x remove padding bits 3) Adam7_deinterlace
04212   NOTE: the in buffer will be overwritten with intermediate data!
04213   */
04214   unsigned bpp = lodepng_get_bpp(&info_png->color);
04215   if(bpp == 0) return 31; /*error: invalid colortype*/
04216 
04217   if(info_png->interlace_method == 0)
04218   {
04219     if(bpp < 8 && w * bpp != ((w * bpp + 7) / 8) * 8)
04220     {
04221       CERROR_TRY_RETURN(unfilter(in, in, w, h, bpp));
04222       removePaddingBits(out, in, w * bpp, ((w * bpp + 7) / 8) * 8, h);
04223     }
04224     /*we can immediatly filter into the out buffer, no other steps needed*/
04225     else CERROR_TRY_RETURN(unfilter(out, in, w, h, bpp));
04226   }
04227   else /*interlace_method is 1 (Adam7)*/
04228   {
04229     unsigned passw[7], passh[7]; size_t filter_passstart[8], padded_passstart[8], passstart[8];
04230     unsigned i;
04231 
04232     Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
04233 
04234     for(i = 0; i < 7; i++)
04235     {
04236       CERROR_TRY_RETURN(unfilter(&in[padded_passstart[i]], &in[filter_passstart[i]], passw[i], passh[i], bpp));
04237       /*TODO: possible efficiency improvement: if in this reduced image the bits fit nicely in 1 scanline,
04238       move bytes instead of bits or move not at all*/
04239       if(bpp < 8)
04240       {
04241         /*remove padding bits in scanlines; after this there still may be padding
04242         bits between the different reduced images: each reduced image still starts nicely at a byte*/
04243         removePaddingBits(&in[passstart[i]], &in[padded_passstart[i]], passw[i] * bpp,
04244                           ((passw[i] * bpp + 7) / 8) * 8, passh[i]);
04245       }
04246     }
04247 
04248     Adam7_deinterlace(out, in, w, h, bpp);
04249   }
04250 
04251   return 0;
04252 }
04253 
04254 static unsigned readChunk_PLTE(LodePNGColorMode* color, const unsigned char* data, size_t chunkLength)
04255 {
04256   unsigned pos = 0, i;
04257   if(color->palette) lodepng_free(color->palette);
04258   color->palettesize = chunkLength / 3;
04259   color->palette = (unsigned char*)lodepng_malloc(4 * color->palettesize);
04260   if(!color->palette && color->palettesize)
04261   {
04262     color->palettesize = 0;
04263     return 83; /*alloc fail*/
04264   }
04265   if(color->palettesize > 256) return 38; /*error: palette too big*/
04266 
04267   for(i = 0; i < color->palettesize; i++)
04268   {
04269     color->palette[4 * i + 0] = data[pos++]; /*R*/
04270     color->palette[4 * i + 1] = data[pos++]; /*G*/
04271     color->palette[4 * i + 2] = data[pos++]; /*B*/
04272     color->palette[4 * i + 3] = 255; /*alpha*/
04273   }
04274 
04275   return 0; /* OK */
04276 }
04277 
04278 static unsigned readChunk_tRNS(LodePNGColorMode* color, const unsigned char* data, size_t chunkLength)
04279 {
04280   unsigned i;
04281   if(color->colortype == LCT_PALETTE)
04282   {
04283     /*error: more alpha values given than there are palette entries*/
04284     if(chunkLength > color->palettesize) return 38;
04285 
04286     for(i = 0; i < chunkLength; i++) color->palette[4 * i + 3] = data[i];
04287   }
04288   else if(color->colortype == LCT_GREY)
04289   {
04290     /*error: this chunk must be 2 bytes for greyscale image*/
04291     if(chunkLength != 2) return 30;
04292 
04293     color->key_defined = 1;
04294     color->key_r = color->key_g = color->key_b = 256 * data[0] + data[1];
04295   }
04296   else if(color->colortype == LCT_RGB)
04297   {
04298     /*error: this chunk must be 6 bytes for RGB image*/
04299     if(chunkLength != 6) return 41;
04300 
04301     color->key_defined = 1;
04302     color->key_r = 256 * data[0] + data[1];
04303     color->key_g = 256 * data[2] + data[3];
04304     color->key_b = 256 * data[4] + data[5];
04305   }
04306   else return 42; /*error: tRNS chunk not allowed for other color models*/
04307 
04308   return 0; /* OK */
04309 }
04310 
04311 
04312 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
04313 /*background color chunk (bKGD)*/
04314 static unsigned readChunk_bKGD(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
04315 {
04316   if(info->color.colortype == LCT_PALETTE)
04317   {
04318     /*error: this chunk must be 1 byte for indexed color image*/
04319     if(chunkLength != 1) return 43;
04320 
04321     info->background_defined = 1;
04322     info->background_r = info->background_g = info->background_b = data[0];
04323   }
04324   else if(info->color.colortype == LCT_GREY || info->color.colortype == LCT_GREY_ALPHA)
04325   {
04326     /*error: this chunk must be 2 bytes for greyscale image*/
04327     if(chunkLength != 2) return 44;
04328 
04329     info->background_defined = 1;
04330     info->background_r = info->background_g = info->background_b
04331                                  = 256 * data[0] + data[1];
04332   }
04333   else if(info->color.colortype == LCT_RGB || info->color.colortype == LCT_RGBA)
04334   {
04335     /*error: this chunk must be 6 bytes for greyscale image*/
04336     if(chunkLength != 6) return 45;
04337 
04338     info->background_defined = 1;
04339     info->background_r = 256 * data[0] + data[1];
04340     info->background_g = 256 * data[2] + data[3];
04341     info->background_b = 256 * data[4] + data[5];
04342   }
04343 
04344   return 0; /* OK */
04345 }
04346 
04347 /*text chunk (tEXt)*/
04348 static unsigned readChunk_tEXt(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
04349 {
04350   unsigned error = 0;
04351   char *key = 0, *str = 0;
04352   unsigned i;
04353 
04354   while(!error) /*not really a while loop, only used to break on error*/
04355   {
04356     unsigned length, string2_begin;
04357 
04358     length = 0;
04359     while(length < chunkLength && data[length] != 0) length++;
04360     /*even though it's not allowed by the standard, no error is thrown if
04361     there's no null termination char, if the text is empty*/
04362     if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
04363 
04364     key = (char*)lodepng_malloc(length + 1);
04365     if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
04366 
04367     key[length] = 0;
04368     for(i = 0; i < length; i++) key[i] = data[i];
04369 
04370     string2_begin = length + 1; /*skip keyword null terminator*/
04371 
04372     length = chunkLength < string2_begin ? 0 : chunkLength - string2_begin;
04373     str = (char*)lodepng_malloc(length + 1);
04374     if(!str) CERROR_BREAK(error, 83); /*alloc fail*/
04375 
04376     str[length] = 0;
04377     for(i = 0; i < length; i++) str[i] = data[string2_begin + i];
04378 
04379     error = lodepng_add_text(info, key, str);
04380 
04381     break;
04382   }
04383 
04384   lodepng_free(key);
04385   lodepng_free(str);
04386 
04387   return error;
04388 }
04389 
04390 /*compressed text chunk (zTXt)*/
04391 static unsigned readChunk_zTXt(LodePNGInfo* info, const LodePNGDecompressSettings* zlibsettings,
04392                                const unsigned char* data, size_t chunkLength)
04393 {
04394   unsigned error = 0;
04395   unsigned i;
04396 
04397   unsigned length, string2_begin;
04398   char *key = 0;
04399   ucvector decoded;
04400 
04401   ucvector_init(&decoded);
04402 
04403   while(!error) /*not really a while loop, only used to break on error*/
04404   {
04405     for(length = 0; length < chunkLength && data[length] != 0; length++) ;
04406     if(length + 2 >= chunkLength) CERROR_BREAK(error, 75); /*no null termination, corrupt?*/
04407     if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
04408 
04409     key = (char*)lodepng_malloc(length + 1);
04410     if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
04411 
04412     key[length] = 0;
04413     for(i = 0; i < length; i++) key[i] = data[i];
04414 
04415     if(data[length + 1] != 0) CERROR_BREAK(error, 72); /*the 0 byte indicating compression must be 0*/
04416 
04417     string2_begin = length + 2;
04418     if(string2_begin > chunkLength) CERROR_BREAK(error, 75); /*no null termination, corrupt?*/
04419 
04420     length = chunkLength - string2_begin;
04421     /*will fail if zlib error, e.g. if length is too small*/
04422     error = zlib_decompress(&decoded.data, &decoded.size,
04423                             (unsigned char*)(&data[string2_begin]),
04424                             length, zlibsettings);
04425     if(error) break;
04426     ucvector_push_back(&decoded, 0);
04427 
04428     error = lodepng_add_text(info, key, (char*)decoded.data);
04429 
04430     break;
04431   }
04432 
04433   lodepng_free(key);
04434   ucvector_cleanup(&decoded);
04435 
04436   return error;
04437 }
04438 
04439 /*international text chunk (iTXt)*/
04440 static unsigned readChunk_iTXt(LodePNGInfo* info, const LodePNGDecompressSettings* zlibsettings,
04441                                const unsigned char* data, size_t chunkLength)
04442 {
04443   unsigned error = 0;
04444   unsigned i;
04445 
04446   unsigned length, begin, compressed;
04447   char *key = 0, *langtag = 0, *transkey = 0;
04448   ucvector decoded;
04449   ucvector_init(&decoded);
04450 
04451   while(!error) /*not really a while loop, only used to break on error*/
04452   {
04453     /*Quick check if the chunk length isn't too small. Even without check
04454     it'd still fail with other error checks below if it's too short. This just gives a different error code.*/
04455     if(chunkLength < 5) CERROR_BREAK(error, 30); /*iTXt chunk too short*/
04456 
04457     /*read the key*/
04458     for(length = 0; length < chunkLength && data[length] != 0; length++) ;
04459     if(length + 3 >= chunkLength) CERROR_BREAK(error, 75); /*no null termination char, corrupt?*/
04460     if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
04461 
04462     key = (char*)lodepng_malloc(length + 1);
04463     if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
04464 
04465     key[length] = 0;
04466     for(i = 0; i < length; i++) key[i] = data[i];
04467 
04468     /*read the compression method*/
04469     compressed = data[length + 1];
04470     if(data[length + 2] != 0) CERROR_BREAK(error, 72); /*the 0 byte indicating compression must be 0*/
04471 
04472     /*even though it's not allowed by the standard, no error is thrown if
04473     there's no null termination char, if the text is empty for the next 3 texts*/
04474 
04475     /*read the langtag*/
04476     begin = length + 3;
04477     length = 0;
04478     for(i = begin; i < chunkLength && data[i] != 0; i++) length++;
04479 
04480     langtag = (char*)lodepng_malloc(length + 1);
04481     if(!langtag) CERROR_BREAK(error, 83); /*alloc fail*/
04482 
04483     langtag[length] = 0;
04484     for(i = 0; i < length; i++) langtag[i] = data[begin + i];
04485 
04486     /*read the transkey*/
04487     begin += length + 1;
04488     length = 0;
04489     for(i = begin; i < chunkLength && data[i] != 0; i++) length++;
04490 
04491     transkey = (char*)lodepng_malloc(length + 1);
04492     if(!transkey) CERROR_BREAK(error, 83); /*alloc fail*/
04493 
04494     transkey[length] = 0;
04495     for(i = 0; i < length; i++) transkey[i] = data[begin + i];
04496 
04497     /*read the actual text*/
04498     begin += length + 1;
04499 
04500     length = chunkLength < begin ? 0 : chunkLength - begin;
04501 
04502     if(compressed)
04503     {
04504       /*will fail if zlib error, e.g. if length is too small*/
04505       error = zlib_decompress(&decoded.data, &decoded.size,
04506                               (unsigned char*)(&data[begin]),
04507                               length, zlibsettings);
04508       if(error) break;
04509       if(decoded.allocsize < decoded.size) decoded.allocsize = decoded.size;
04510       ucvector_push_back(&decoded, 0);
04511     }
04512     else
04513     {
04514       if(!ucvector_resize(&decoded, length + 1)) CERROR_BREAK(error, 83 /*alloc fail*/);
04515 
04516       decoded.data[length] = 0;
04517       for(i = 0; i < length; i++) decoded.data[i] = data[begin + i];
04518     }
04519 
04520     error = lodepng_add_itext(info, key, langtag, transkey, (char*)decoded.data);
04521 
04522     break;
04523   }
04524 
04525   lodepng_free(key);
04526   lodepng_free(langtag);
04527   lodepng_free(transkey);
04528   ucvector_cleanup(&decoded);
04529 
04530   return error;
04531 }
04532 
04533 static unsigned readChunk_tIME(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
04534 {
04535   if(chunkLength != 7) return 73; /*invalid tIME chunk size*/
04536 
04537   info->time_defined = 1;
04538   info->time.year = 256 * data[0] + data[+ 1];
04539   info->time.month = data[2];
04540   info->time.day = data[3];
04541   info->time.hour = data[4];
04542   info->time.minute = data[5];
04543   info->time.second = data[6];
04544 
04545   return 0; /* OK */
04546 }
04547 
04548 static unsigned readChunk_pHYs(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
04549 {
04550   if(chunkLength != 9) return 74; /*invalid pHYs chunk size*/
04551 
04552   info->phys_defined = 1;
04553   info->phys_x = 16777216 * data[0] + 65536 * data[1] + 256 * data[2] + data[3];
04554   info->phys_y = 16777216 * data[4] + 65536 * data[5] + 256 * data[6] + data[7];
04555   info->phys_unit = data[8];
04556 
04557   return 0; /* OK */
04558 }
04559 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
04560 
04561 /*read a PNG, the result will be in the same color type as the PNG (hence "generic")*/
04562 static void decodeGeneric(unsigned char** out, unsigned* w, unsigned* h,
04563                           LodePNGState* state,
04564                           const unsigned char* in, size_t insize)
04565 {
04566   unsigned char IEND = 0;
04567   const unsigned char* chunk;
04568   size_t i;
04569   ucvector idat; /*the data from idat chunks*/
04570   ucvector scanlines;
04571 
04572   /*for unknown chunk order*/
04573   unsigned unknown = 0;
04574 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
04575   unsigned critical_pos = 1; /*1 = after IHDR, 2 = after PLTE, 3 = after IDAT*/
04576 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
04577 
04578   /*provide some proper output values if error will happen*/
04579   *out = 0;
04580 
04581   state->error = lodepng_inspect(w, h, state, in, insize); /*reads header and resets other parameters in state->info_png*/
04582   if(state->error) return;
04583 
04584   ucvector_init(&idat);
04585   chunk = &in[33]; /*first byte of the first chunk after the header*/
04586 
04587   /*loop through the chunks, ignoring unknown chunks and stopping at IEND chunk.
04588   IDAT data is put at the start of the in buffer*/
04589   while(!IEND && !state->error)
04590   {
04591     unsigned chunkLength;
04592     const unsigned char* data; /*the data in the chunk*/
04593 
04594     /*error: size of the in buffer too small to contain next chunk*/
04595     if((size_t)((chunk - in) + 12) > insize || chunk < in) CERROR_BREAK(state->error, 30);
04596 
04597     /*length of the data of the chunk, excluding the length bytes, chunk type and CRC bytes*/
04598     chunkLength = lodepng_chunk_length(chunk);
04599     /*error: chunk length larger than the max PNG chunk size*/
04600     if(chunkLength > 2147483647) CERROR_BREAK(state->error, 63);
04601 
04602     if((size_t)((chunk - in) + chunkLength + 12) > insize || (chunk + chunkLength + 12) < in)
04603     {
04604       CERROR_BREAK(state->error, 64); /*error: size of the in buffer too small to contain next chunk*/
04605     }
04606 
04607     data = lodepng_chunk_data_const(chunk);
04608 
04609     /*IDAT chunk, containing compressed image data*/
04610     if(lodepng_chunk_type_equals(chunk, "IDAT"))
04611     {
04612       size_t oldsize = idat.size;
04613       if(!ucvector_resize(&idat, oldsize + chunkLength)) CERROR_BREAK(state->error, 83 /*alloc fail*/);
04614       for(i = 0; i < chunkLength; i++) idat.data[oldsize + i] = data[i];
04615 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
04616       critical_pos = 3;
04617 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
04618     }
04619     /*IEND chunk*/
04620     else if(lodepng_chunk_type_equals(chunk, "IEND"))
04621     {
04622       IEND = 1;
04623     }
04624     /*palette chunk (PLTE)*/
04625     else if(lodepng_chunk_type_equals(chunk, "PLTE"))
04626     {
04627       state->error = readChunk_PLTE(&state->info_png.color, data, chunkLength);
04628       if(state->error) break;
04629 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
04630       critical_pos = 2;
04631 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
04632     }
04633     /*palette transparency chunk (tRNS)*/
04634     else if(lodepng_chunk_type_equals(chunk, "tRNS"))
04635     {
04636       state->error = readChunk_tRNS(&state->info_png.color, data, chunkLength);
04637       if(state->error) break;
04638     }
04639 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
04640     /*background color chunk (bKGD)*/
04641     else if(lodepng_chunk_type_equals(chunk, "bKGD"))
04642     {
04643       state->error = readChunk_bKGD(&state->info_png, data, chunkLength);
04644       if(state->error) break;
04645     }
04646     /*text chunk (tEXt)*/
04647     else if(lodepng_chunk_type_equals(chunk, "tEXt"))
04648     {
04649       if(state->decoder.read_text_chunks)
04650       {
04651         state->error = readChunk_tEXt(&state->info_png, data, chunkLength);
04652         if(state->error) break;
04653       }
04654     }
04655     /*compressed text chunk (zTXt)*/
04656     else if(lodepng_chunk_type_equals(chunk, "zTXt"))
04657     {
04658       if(state->decoder.read_text_chunks)
04659       {
04660         state->error = readChunk_zTXt(&state->info_png, &state->decoder.zlibsettings, data, chunkLength);
04661         if(state->error) break;
04662       }
04663     }
04664     /*international text chunk (iTXt)*/
04665     else if(lodepng_chunk_type_equals(chunk, "iTXt"))
04666     {
04667       if(state->decoder.read_text_chunks)
04668       {
04669         state->error = readChunk_iTXt(&state->info_png, &state->decoder.zlibsettings, data, chunkLength);
04670         if(state->error) break;
04671       }
04672     }
04673     else if(lodepng_chunk_type_equals(chunk, "tIME"))
04674     {
04675       state->error = readChunk_tIME(&state->info_png, data, chunkLength);
04676       if(state->error) break;
04677     }
04678     else if(lodepng_chunk_type_equals(chunk, "pHYs"))
04679     {
04680       state->error = readChunk_pHYs(&state->info_png, data, chunkLength);
04681       if(state->error) break;
04682     }
04683 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
04684     else /*it's not an implemented chunk type, so ignore it: skip over the data*/
04685     {
04686       /*error: unknown critical chunk (5th bit of first byte of chunk type is 0)*/
04687       if(!lodepng_chunk_ancillary(chunk)) CERROR_BREAK(state->error, 69);
04688 
04689       unknown = 1;
04690 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
04691       if(state->decoder.remember_unknown_chunks)
04692       {
04693         state->error = lodepng_chunk_append(&state->info_png.unknown_chunks_data[critical_pos - 1],
04694                                             &state->info_png.unknown_chunks_size[critical_pos - 1], chunk);
04695         if(state->error) break;
04696       }
04697 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
04698     }
04699 
04700     if(!state->decoder.ignore_crc && !unknown) /*check CRC if wanted, only on known chunk types*/
04701     {
04702       if(lodepng_chunk_check_crc(chunk)) CERROR_BREAK(state->error, 57); /*invalid CRC*/
04703     }
04704 
04705     if(!IEND) chunk = lodepng_chunk_next_const(chunk);
04706   }
04707 
04708   ucvector_init(&scanlines);
04709   if(!state->error)
04710   {
04711     /*maximum final image length is already reserved in the vector's length - this is not really necessary*/
04712     if(!ucvector_resize(&scanlines, lodepng_get_raw_size(*w, *h, &state->info_png.color) + *h))
04713     {
04714       state->error = 83; /*alloc fail*/
04715     }
04716   }
04717   if(!state->error)
04718   {
04719     /*decompress with the Zlib decompressor*/
04720     state->error = zlib_decompress(&scanlines.data, &scanlines.size, idat.data,
04721                                    idat.size, &state->decoder.zlibsettings);
04722   }
04723   ucvector_cleanup(&idat);
04724 
04725   if(!state->error)
04726   {
04727     ucvector outv;
04728     ucvector_init(&outv);
04729     if(!ucvector_resizev(&outv,
04730         lodepng_get_raw_size(*w, *h, &state->info_png.color), 0)) state->error = 83; /*alloc fail*/
04731     if(!state->error) state->error = postProcessScanlines(outv.data, scanlines.data, *w, *h, &state->info_png);
04732     *out = outv.data;
04733   }
04734   ucvector_cleanup(&scanlines);
04735 }
04736 
04737 unsigned lodepng_decode(unsigned char** out, unsigned* w, unsigned* h,
04738                         LodePNGState* state,
04739                         const unsigned char* in, size_t insize)
04740 {
04741   *out = 0;
04742   decodeGeneric(out, w, h, state, in, insize);
04743   if(state->error) return state->error;
04744   if(!state->decoder.color_convert || lodepng_color_mode_equal(&state->info_raw, &state->info_png.color))
04745   {
04746     /*same color type, no copying or converting of data needed*/
04747     /*store the info_png color settings on the info_raw so that the info_raw still reflects what colortype
04748     the raw image has to the end user*/
04749     if(!state->decoder.color_convert)
04750     {
04751       state->error = lodepng_color_mode_copy(&state->info_raw, &state->info_png.color);
04752       if(state->error) return state->error;
04753     }
04754   }
04755   else
04756   {
04757     /*color conversion needed; sort of copy of the data*/
04758     unsigned char* data = *out;
04759     size_t outsize;
04760 
04761     /*TODO: check if this works according to the statement in the documentation: "The converter can convert
04762     from greyscale input color type, to 8-bit greyscale or greyscale with alpha"*/
04763     if(!(state->info_raw.colortype == LCT_RGB || state->info_raw.colortype == LCT_RGBA)
04764        && !(state->info_raw.bitdepth == 8))
04765     {
04766       return 56; /*unsupported color mode conversion*/
04767     }
04768 
04769     outsize = lodepng_get_raw_size(*w, *h, &state->info_raw);
04770     *out = (unsigned char*)lodepng_malloc(outsize);
04771     if(!(*out))
04772     {
04773       state->error = 83; /*alloc fail*/
04774     }
04775     else state->error = lodepng_convert(*out, data, &state->info_raw, &state->info_png.color, *w, *h, state->decoder.fix_png);
04776     lodepng_free(data);
04777   }
04778   return state->error;
04779 }
04780 
04781 unsigned lodepng_decode_memory(unsigned char** out, unsigned* w, unsigned* h, const unsigned char* in,
04782                                size_t insize, LodePNGColorType colortype, unsigned bitdepth)
04783 {
04784   unsigned error;
04785   LodePNGState state;
04786   lodepng_state_init(&state);
04787   state.info_raw.colortype = colortype;
04788   state.info_raw.bitdepth = bitdepth;
04789   error = lodepng_decode(out, w, h, &state, in, insize);
04790   lodepng_state_cleanup(&state);
04791   return error;
04792 }
04793 
04794 unsigned lodepng_decode32(unsigned char** out, unsigned* w, unsigned* h, const unsigned char* in, size_t insize)
04795 {
04796   return lodepng_decode_memory(out, w, h, in, insize, LCT_RGBA, 8);
04797 }
04798 
04799 unsigned lodepng_decode24(unsigned char** out, unsigned* w, unsigned* h, const unsigned char* in, size_t insize)
04800 {
04801   return lodepng_decode_memory(out, w, h, in, insize, LCT_RGB, 8);
04802 }
04803 
04804 #ifdef LODEPNG_COMPILE_DISK
04805 unsigned lodepng_decode_file(unsigned char** out, unsigned* w, unsigned* h, const char* filename,
04806                              LodePNGColorType colortype, unsigned bitdepth)
04807 {
04808   unsigned char* buffer;
04809   size_t buffersize;
04810   unsigned error;
04811   error = lodepng_load_file(&buffer, &buffersize, filename);
04812   if(!error) error = lodepng_decode_memory(out, w, h, buffer, buffersize, colortype, bitdepth);
04813   lodepng_free(buffer);
04814   return error;
04815 }
04816 
04817 unsigned lodepng_decode32_file(unsigned char** out, unsigned* w, unsigned* h, const char* filename)
04818 {
04819   return lodepng_decode_file(out, w, h, filename, LCT_RGBA, 8);
04820 }
04821 
04822 unsigned lodepng_decode24_file(unsigned char** out, unsigned* w, unsigned* h, const char* filename)
04823 {
04824   return lodepng_decode_file(out, w, h, filename, LCT_RGB, 8);
04825 }
04826 #endif /*LODEPNG_COMPILE_DISK*/
04827 
04828 void lodepng_decoder_settings_init(LodePNGDecoderSettings* settings)
04829 {
04830   settings->color_convert = 1;
04831 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
04832   settings->read_text_chunks = 1;
04833   settings->remember_unknown_chunks = 0;
04834 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
04835   settings->ignore_crc = 0;
04836   settings->fix_png = 0;
04837   lodepng_decompress_settings_init(&settings->zlibsettings);
04838 }
04839 
04840 #endif /*LODEPNG_COMPILE_DECODER*/
04841 
04842 #if defined(LODEPNG_COMPILE_DECODER) || defined(LODEPNG_COMPILE_ENCODER)
04843 
04844 void lodepng_state_init(LodePNGState* state)
04845 {
04846 #ifdef LODEPNG_COMPILE_DECODER
04847   lodepng_decoder_settings_init(&state->decoder);
04848 #endif /*LODEPNG_COMPILE_DECODER*/
04849 #ifdef LODEPNG_COMPILE_ENCODER
04850   lodepng_encoder_settings_init(&state->encoder);
04851 #endif /*LODEPNG_COMPILE_ENCODER*/
04852   lodepng_color_mode_init(&state->info_raw);
04853   lodepng_info_init(&state->info_png);
04854   state->error = 1;
04855 }
04856 
04857 void lodepng_state_cleanup(LodePNGState* state)
04858 {
04859   lodepng_color_mode_cleanup(&state->info_raw);
04860   lodepng_info_cleanup(&state->info_png);
04861 }
04862 
04863 void lodepng_state_copy(LodePNGState* dest, const LodePNGState* source)
04864 {
04865   lodepng_state_cleanup(dest);
04866   *dest = *source;
04867   lodepng_color_mode_init(&dest->info_raw);
04868   lodepng_info_init(&dest->info_png);
04869   dest->error = lodepng_color_mode_copy(&dest->info_raw, &source->info_raw); if(dest->error) return;
04870   dest->error = lodepng_info_copy(&dest->info_png, &source->info_png); if(dest->error) return;
04871 }
04872 
04873 #endif /* defined(LODEPNG_COMPILE_DECODER) || defined(LODEPNG_COMPILE_ENCODER) */
04874 
04875 #ifdef LODEPNG_COMPILE_ENCODER
04876 
04877 /* ////////////////////////////////////////////////////////////////////////// */
04878 /* / PNG Encoder                                                            / */
04879 /* ////////////////////////////////////////////////////////////////////////// */
04880 
04881 /*chunkName must be string of 4 characters*/
04882 static unsigned addChunk(ucvector* out, const char* chunkName, const unsigned char* data, size_t length)
04883 {
04884   CERROR_TRY_RETURN(lodepng_chunk_create(&out->data, &out->size, (unsigned)length, chunkName, data));
04885   out->allocsize = out->size; /*fix the allocsize again*/
04886   return 0;
04887 }
04888 
04889 static void writeSignature(ucvector* out)
04890 {
04891   /*8 bytes PNG signature, aka the magic bytes*/
04892   ucvector_push_back(out, 137);
04893   ucvector_push_back(out, 80);
04894   ucvector_push_back(out, 78);
04895   ucvector_push_back(out, 71);
04896   ucvector_push_back(out, 13);
04897   ucvector_push_back(out, 10);
04898   ucvector_push_back(out, 26);
04899   ucvector_push_back(out, 10);
04900 }
04901 
04902 static unsigned addChunk_IHDR(ucvector* out, unsigned w, unsigned h,
04903                               LodePNGColorType colortype, unsigned bitdepth, unsigned interlace_method)
04904 {
04905   unsigned error = 0;
04906   ucvector header;
04907   ucvector_init(&header);
04908 
04909   lodepng_add32bitInt(&header, w); /*width*/
04910   lodepng_add32bitInt(&header, h); /*height*/
04911   ucvector_push_back(&header, (unsigned char)bitdepth); /*bit depth*/
04912   ucvector_push_back(&header, (unsigned char)colortype); /*color type*/
04913   ucvector_push_back(&header, 0); /*compression method*/
04914   ucvector_push_back(&header, 0); /*filter method*/
04915   ucvector_push_back(&header, interlace_method); /*interlace method*/
04916 
04917   error = addChunk(out, "IHDR", header.data, header.size);
04918   ucvector_cleanup(&header);
04919 
04920   return error;
04921 }
04922 
04923 static unsigned addChunk_PLTE(ucvector* out, const LodePNGColorMode* info)
04924 {
04925   unsigned error = 0;
04926   size_t i;
04927   ucvector PLTE;
04928   ucvector_init(&PLTE);
04929   for(i = 0; i < info->palettesize * 4; i++)
04930   {
04931     /*add all channels except alpha channel*/
04932     if(i % 4 != 3) ucvector_push_back(&PLTE, info->palette[i]);
04933   }
04934   error = addChunk(out, "PLTE", PLTE.data, PLTE.size);
04935   ucvector_cleanup(&PLTE);
04936 
04937   return error;
04938 }
04939 
04940 static unsigned addChunk_tRNS(ucvector* out, const LodePNGColorMode* info)
04941 {
04942   unsigned error = 0;
04943   size_t i;
04944   ucvector tRNS;
04945   ucvector_init(&tRNS);
04946   if(info->colortype == LCT_PALETTE)
04947   {
04948     size_t amount = info->palettesize;
04949     /*the tail of palette values that all have 255 as alpha, does not have to be encoded*/
04950     for(i = info->palettesize; i > 0; i--)
04951     {
04952       if(info->palette[4 * (i - 1) + 3] == 255) amount--;
04953       else break;
04954     }
04955     /*add only alpha channel*/
04956     for(i = 0; i < amount; i++) ucvector_push_back(&tRNS, info->palette[4 * i + 3]);
04957   }
04958   else if(info->colortype == LCT_GREY)
04959   {
04960     if(info->key_defined)
04961     {
04962       ucvector_push_back(&tRNS, (unsigned char)(info->key_r / 256));
04963       ucvector_push_back(&tRNS, (unsigned char)(info->key_r % 256));
04964     }
04965   }
04966   else if(info->colortype == LCT_RGB)
04967   {
04968     if(info->key_defined)
04969     {
04970       ucvector_push_back(&tRNS, (unsigned char)(info->key_r / 256));
04971       ucvector_push_back(&tRNS, (unsigned char)(info->key_r % 256));
04972       ucvector_push_back(&tRNS, (unsigned char)(info->key_g / 256));
04973       ucvector_push_back(&tRNS, (unsigned char)(info->key_g % 256));
04974       ucvector_push_back(&tRNS, (unsigned char)(info->key_b / 256));
04975       ucvector_push_back(&tRNS, (unsigned char)(info->key_b % 256));
04976     }
04977   }
04978 
04979   error = addChunk(out, "tRNS", tRNS.data, tRNS.size);
04980   ucvector_cleanup(&tRNS);
04981 
04982   return error;
04983 }
04984 
04985 static unsigned addChunk_IDAT(ucvector* out, const unsigned char* data, size_t datasize,
04986                               LodePNGCompressSettings* zlibsettings)
04987 {
04988   ucvector zlibdata;
04989   unsigned error = 0;
04990 
04991   /*compress with the Zlib compressor*/
04992   ucvector_init(&zlibdata);
04993   error = zlib_compress(&zlibdata.data, &zlibdata.size, data, datasize, zlibsettings);
04994   if(!error) error = addChunk(out, "IDAT", zlibdata.data, zlibdata.size);
04995   ucvector_cleanup(&zlibdata);
04996 
04997   return error;
04998 }
04999 
05000 static unsigned addChunk_IEND(ucvector* out)
05001 {
05002   unsigned error = 0;
05003   error = addChunk(out, "IEND", 0, 0);
05004   return error;
05005 }
05006 
05007 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
05008 
05009 static unsigned addChunk_tEXt(ucvector* out, const char* keyword, const char* textstring)
05010 {
05011   unsigned error = 0;
05012   size_t i;
05013   ucvector text;
05014   ucvector_init(&text);
05015   for(i = 0; keyword[i] != 0; i++) ucvector_push_back(&text, (unsigned char)keyword[i]);
05016   if(i < 1 || i > 79) return 89; /*error: invalid keyword size*/
05017   ucvector_push_back(&text, 0); /*0 termination char*/
05018   for(i = 0; textstring[i] != 0; i++) ucvector_push_back(&text, (unsigned char)textstring[i]);
05019   error = addChunk(out, "tEXt", text.data, text.size);
05020   ucvector_cleanup(&text);
05021 
05022   return error;
05023 }
05024 
05025 static unsigned addChunk_zTXt(ucvector* out, const char* keyword, const char* textstring,
05026                               LodePNGCompressSettings* zlibsettings)
05027 {
05028   unsigned error = 0;
05029   ucvector data, compressed;
05030   size_t i, textsize = strlen(textstring);
05031 
05032   ucvector_init(&data);
05033   ucvector_init(&compressed);
05034   for(i = 0; keyword[i] != 0; i++) ucvector_push_back(&data, (unsigned char)keyword[i]);
05035   if(i < 1 || i > 79) return 89; /*error: invalid keyword size*/
05036   ucvector_push_back(&data, 0); /*0 termination char*/
05037   ucvector_push_back(&data, 0); /*compression method: 0*/
05038 
05039   error = zlib_compress(&compressed.data, &compressed.size,
05040                         (unsigned char*)textstring, textsize, zlibsettings);
05041   if(!error)
05042   {
05043     for(i = 0; i < compressed.size; i++) ucvector_push_back(&data, compressed.data[i]);
05044     error = addChunk(out, "zTXt", data.data, data.size);
05045   }
05046 
05047   ucvector_cleanup(&compressed);
05048   ucvector_cleanup(&data);
05049   return error;
05050 }
05051 
05052 static unsigned addChunk_iTXt(ucvector* out, unsigned compressed, const char* keyword, const char* langtag,
05053                               const char* transkey, const char* textstring, LodePNGCompressSettings* zlibsettings)
05054 {
05055   unsigned error = 0;
05056   ucvector data;
05057   size_t i, textsize = strlen(textstring);
05058 
05059   ucvector_init(&data);
05060 
05061   for(i = 0; keyword[i] != 0; i++) ucvector_push_back(&data, (unsigned char)keyword[i]);
05062   if(i < 1 || i > 79) return 89; /*error: invalid keyword size*/
05063   ucvector_push_back(&data, 0); /*null termination char*/
05064   ucvector_push_back(&data, compressed ? 1 : 0); /*compression flag*/
05065   ucvector_push_back(&data, 0); /*compression method*/
05066   for(i = 0; langtag[i] != 0; i++) ucvector_push_back(&data, (unsigned char)langtag[i]);
05067   ucvector_push_back(&data, 0); /*null termination char*/
05068   for(i = 0; transkey[i] != 0; i++) ucvector_push_back(&data, (unsigned char)transkey[i]);
05069   ucvector_push_back(&data, 0); /*null termination char*/
05070 
05071   if(compressed)
05072   {
05073     ucvector compressed_data;
05074     ucvector_init(&compressed_data);
05075     error = zlib_compress(&compressed_data.data, &compressed_data.size,
05076                           (unsigned char*)textstring, textsize, zlibsettings);
05077     if(!error)
05078     {
05079       for(i = 0; i < compressed_data.size; i++) ucvector_push_back(&data, compressed_data.data[i]);
05080     }
05081     ucvector_cleanup(&compressed_data);
05082   }
05083   else /*not compressed*/
05084   {
05085     for(i = 0; textstring[i] != 0; i++) ucvector_push_back(&data, (unsigned char)textstring[i]);
05086   }
05087 
05088   if(!error) error = addChunk(out, "iTXt", data.data, data.size);
05089   ucvector_cleanup(&data);
05090   return error;
05091 }
05092 
05093 static unsigned addChunk_bKGD(ucvector* out, const LodePNGInfo* info)
05094 {
05095   unsigned error = 0;
05096   ucvector bKGD;
05097   ucvector_init(&bKGD);
05098   if(info->color.colortype == LCT_GREY || info->color.colortype == LCT_GREY_ALPHA)
05099   {
05100     ucvector_push_back(&bKGD, (unsigned char)(info->background_r / 256));
05101     ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256));
05102   }
05103   else if(info->color.colortype == LCT_RGB || info->color.colortype == LCT_RGBA)
05104   {
05105     ucvector_push_back(&bKGD, (unsigned char)(info->background_r / 256));
05106     ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256));
05107     ucvector_push_back(&bKGD, (unsigned char)(info->background_g / 256));
05108     ucvector_push_back(&bKGD, (unsigned char)(info->background_g % 256));
05109     ucvector_push_back(&bKGD, (unsigned char)(info->background_b / 256));
05110     ucvector_push_back(&bKGD, (unsigned char)(info->background_b % 256));
05111   }
05112   else if(info->color.colortype == LCT_PALETTE)
05113   {
05114     ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256)); /*palette index*/
05115   }
05116 
05117   error = addChunk(out, "bKGD", bKGD.data, bKGD.size);
05118   ucvector_cleanup(&bKGD);
05119 
05120   return error;
05121 }
05122 
05123 static unsigned addChunk_tIME(ucvector* out, const LodePNGTime* time)
05124 {
05125   unsigned error = 0;
05126   unsigned char* data = (unsigned char*)lodepng_malloc(7);
05127   if(!data) return 83; /*alloc fail*/
05128   data[0] = (unsigned char)(time->year / 256);
05129   data[1] = (unsigned char)(time->year % 256);
05130   data[2] = time->month;
05131   data[3] = time->day;
05132   data[4] = time->hour;
05133   data[5] = time->minute;
05134   data[6] = time->second;
05135   error = addChunk(out, "tIME", data, 7);
05136   lodepng_free(data);
05137   return error;
05138 }
05139 
05140 static unsigned addChunk_pHYs(ucvector* out, const LodePNGInfo* info)
05141 {
05142   unsigned error = 0;
05143   ucvector data;
05144   ucvector_init(&data);
05145 
05146   lodepng_add32bitInt(&data, info->phys_x);
05147   lodepng_add32bitInt(&data, info->phys_y);
05148   ucvector_push_back(&data, info->phys_unit);
05149 
05150   error = addChunk(out, "pHYs", data.data, data.size);
05151   ucvector_cleanup(&data);
05152 
05153   return error;
05154 }
05155 
05156 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
05157 
05158 static void filterScanline(unsigned char* out, const unsigned char* scanline, const unsigned char* prevline,
05159                            size_t length, size_t bytewidth, unsigned char filterType)
05160 {
05161   size_t i;
05162   switch(filterType)
05163   {
05164     case 0: /*None*/
05165       for(i = 0; i < length; i++) out[i] = scanline[i];
05166       break;
05167     case 1: /*Sub*/
05168       if(prevline)
05169       {
05170         for(i = 0; i < bytewidth; i++) out[i] = scanline[i];
05171         for(i = bytewidth; i < length; i++) out[i] = scanline[i] - scanline[i - bytewidth];
05172       }
05173       else
05174       {
05175         for(i = 0; i < bytewidth; i++) out[i] = scanline[i];
05176         for(i = bytewidth; i < length; i++) out[i] = scanline[i] - scanline[i - bytewidth];
05177       }
05178       break;
05179     case 2: /*Up*/
05180       if(prevline)
05181       {
05182         for(i = 0; i < length; i++) out[i] = scanline[i] - prevline[i];
05183       }
05184       else
05185       {
05186         for(i = 0; i < length; i++) out[i] = scanline[i];
05187       }
05188       break;
05189     case 3: /*Average*/
05190       if(prevline)
05191       {
05192         for(i = 0; i < bytewidth; i++) out[i] = scanline[i] - prevline[i] / 2;
05193         for(i = bytewidth; i < length; i++) out[i] = scanline[i] - ((scanline[i - bytewidth] + prevline[i]) / 2);
05194       }
05195       else
05196       {
05197         for(i = 0; i < bytewidth; i++) out[i] = scanline[i];
05198         for(i = bytewidth; i < length; i++) out[i] = scanline[i] - scanline[i - bytewidth] / 2;
05199       }
05200       break;
05201     case 4: /*Paeth*/
05202       if(prevline)
05203       {
05204         /*paethPredictor(0, prevline[i], 0) is always prevline[i]*/
05205         for(i = 0; i < bytewidth; i++) out[i] = (scanline[i] - prevline[i]);
05206         for(i = bytewidth; i < length; i++)
05207         {
05208           out[i] = (scanline[i] - paethPredictor(scanline[i - bytewidth], prevline[i], prevline[i - bytewidth]));
05209         }
05210       }
05211       else
05212       {
05213         for(i = 0; i < bytewidth; i++) out[i] = scanline[i];
05214         /*paethPredictor(scanline[i - bytewidth], 0, 0) is always scanline[i - bytewidth]*/
05215         for(i = bytewidth; i < length; i++) out[i] = (scanline[i] - scanline[i - bytewidth]);
05216       }
05217       break;
05218     default: return; /*unexisting filter type given*/
05219   }
05220 }
05221 
05222 /* log2 approximation. A slight bit faster than std::log. */
05223 static float flog2(float f)
05224 {
05225   float result = 0;
05226   while(f > 32) { result += 4; f /= 16; }
05227   while(f > 2) { result++; f /= 2; }
05228   return result + 1.442695f * (f * f * f / 3 - 3 * f * f / 2 + 3 * f - 1.83333f);
05229 }
05230 
05231 static unsigned filter(unsigned char* out, const unsigned char* in, unsigned w, unsigned h,
05232                        const LodePNGColorMode* info, const LodePNGEncoderSettings* settings)
05233 {
05234   /*
05235   For PNG filter method 0
05236   out must be a buffer with as size: h + (w * h * bpp + 7) / 8, because there are
05237   the scanlines with 1 extra byte per scanline
05238   */
05239 
05240   unsigned bpp = lodepng_get_bpp(info);
05241   /*the width of a scanline in bytes, not including the filter type*/
05242   size_t linebytes = (w * bpp + 7) / 8;
05243   /*bytewidth is used for filtering, is 1 when bpp < 8, number of bytes per pixel otherwise*/
05244   size_t bytewidth = (bpp + 7) / 8;
05245   const unsigned char* prevline = 0;
05246   unsigned x, y;
05247   unsigned error = 0;
05248   LodePNGFilterStrategy strategy = settings->filter_strategy;
05249 
05250   /*
05251   There is a heuristic called the minimum sum of absolute differences heuristic, suggested by the PNG standard:
05252    *  If the image type is Palette, or the bit depth is smaller than 8, then do not filter the image (i.e.
05253       use fixed filtering, with the filter None).
05254    * (The other case) If the image type is Grayscale or RGB (with or without Alpha), and the bit depth is
05255      not smaller than 8, then use adaptive filtering heuristic as follows: independently for each row, apply
05256      all five filters and select the filter that produces the smallest sum of absolute values per row.
05257   This heuristic is used if filter strategy is LFS_MINSUM and filter_palette_zero is true.
05258 
05259   If filter_palette_zero is true and filter_strategy is not LFS_MINSUM, the above heuristic is followed,
05260   but for "the other case", whatever strategy filter_strategy is set to instead of the minimum sum
05261   heuristic is used.
05262   */
05263   if(settings->filter_palette_zero &&
05264      (info->colortype == LCT_PALETTE || info->bitdepth < 8)) strategy = LFS_ZERO;
05265 
05266   if(bpp == 0) return 31; /*error: invalid color type*/
05267 
05268   if(strategy == LFS_ZERO)
05269   {
05270     for(y = 0; y < h; y++)
05271     {
05272       size_t outindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
05273       size_t inindex = linebytes * y;
05274       out[outindex] = 0; /*filter type byte*/
05275       filterScanline(&out[outindex + 1], &in[inindex], prevline, linebytes, bytewidth, 0);
05276       prevline = &in[inindex];
05277     }
05278   }
05279   else if(strategy == LFS_MINSUM)
05280   {
05281     /*adaptive filtering*/
05282     size_t sum[5];
05283     ucvector attempt[5]; /*five filtering attempts, one for each filter type*/
05284     size_t smallest = 0;
05285     unsigned type, bestType = 0;
05286 
05287     for(type = 0; type < 5; type++)
05288     {
05289       ucvector_init(&attempt[type]);
05290       if(!ucvector_resize(&attempt[type], linebytes)) return 83; /*alloc fail*/
05291     }
05292 
05293     if(!error)
05294     {
05295       for(y = 0; y < h; y++)
05296       {
05297         /*try the 5 filter types*/
05298         for(type = 0; type < 5; type++)
05299         {
05300           filterScanline(attempt[type].data, &in[y * linebytes], prevline, linebytes, bytewidth, type);
05301 
05302           /*calculate the sum of the result*/
05303           sum[type] = 0;
05304           if(type == 0)
05305           {
05306             for(x = 0; x < linebytes; x++) sum[type] += (unsigned char)(attempt[type].data[x]);
05307           }
05308           else
05309           {
05310             for(x = 0; x < linebytes; x++)
05311             {
05312               /*For differences, each byte should be treated as signed, values above 127 are negative
05313               (converted to signed char). Filtertype 0 isn't a difference though, so use unsigned there.
05314               This means filtertype 0 is almost never chosen, but that is justified.*/
05315               signed char s = (signed char)(attempt[type].data[x]);
05316               sum[type] += s < 0 ? -s : s;
05317             }
05318           }
05319 
05320           /*check if this is smallest sum (or if type == 0 it's the first case so always store the values)*/
05321           if(type == 0 || sum[type] < smallest)
05322           {
05323             bestType = type;
05324             smallest = sum[type];
05325           }
05326         }
05327 
05328         prevline = &in[y * linebytes];
05329 
05330         /*now fill the out values*/
05331         out[y * (linebytes + 1)] = bestType; /*the first byte of a scanline will be the filter type*/
05332         for(x = 0; x < linebytes; x++) out[y * (linebytes + 1) + 1 + x] = attempt[bestType].data[x];
05333       }
05334     }
05335 
05336     for(type = 0; type < 5; type++) ucvector_cleanup(&attempt[type]);
05337   }
05338   else if(strategy == LFS_ENTROPY)
05339   {
05340     float sum[5];
05341     ucvector attempt[5]; /*five filtering attempts, one for each filter type*/
05342     float smallest = 0;
05343     unsigned type, bestType = 0;
05344     unsigned count[256];
05345 
05346     for(type = 0; type < 5; type++)
05347     {
05348       ucvector_init(&attempt[type]);
05349       if(!ucvector_resize(&attempt[type], linebytes)) return 83; /*alloc fail*/
05350     }
05351 
05352     for(y = 0; y < h; y++)
05353     {
05354       /*try the 5 filter types*/
05355       for(type = 0; type < 5; type++)
05356       {
05357         filterScanline(attempt[type].data, &in[y * linebytes], prevline, linebytes, bytewidth, type);
05358         for(x = 0; x < 256; x++) count[x] = 0;
05359         for(x = 0; x < linebytes; x++) count[attempt[type].data[x]]++;
05360         count[type]++; /*the filter type itself is part of the scanline*/
05361         sum[type] = 0;
05362         for(x = 0; x < 256; x++)
05363         {
05364           float p = count[x] / (float)(linebytes + 1);
05365           sum[type] += count[x] == 0 ? 0 : flog2(1 / p) * p;
05366         }
05367         /*check if this is smallest sum (or if type == 0 it's the first case so always store the values)*/
05368         if(type == 0 || sum[type] < smallest)
05369         {
05370           bestType = type;
05371           smallest = sum[type];
05372         }
05373       }
05374 
05375       prevline = &in[y * linebytes];
05376 
05377       /*now fill the out values*/
05378       out[y * (linebytes + 1)] = bestType; /*the first byte of a scanline will be the filter type*/
05379       for(x = 0; x < linebytes; x++) out[y * (linebytes + 1) + 1 + x] = attempt[bestType].data[x];
05380     }
05381 
05382     for(type = 0; type < 5; type++) ucvector_cleanup(&attempt[type]);
05383   }
05384   else if(strategy == LFS_PREDEFINED)
05385   {
05386     for(y = 0; y < h; y++)
05387     {
05388       size_t outindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
05389       size_t inindex = linebytes * y;
05390       unsigned type = settings->predefined_filters[y];
05391       out[outindex] = type; /*filter type byte*/
05392       filterScanline(&out[outindex + 1], &in[inindex], prevline, linebytes, bytewidth, type);
05393       prevline = &in[inindex];
05394     }
05395   }
05396   else if(strategy == LFS_BRUTE_FORCE)
05397   {
05398     /*brute force filter chooser.
05399     deflate the scanline after every filter attempt to see which one deflates best.
05400     This is very slow and gives only slightly smaller, sometimes even larger, result*/
05401     size_t size[5];
05402     ucvector attempt[5]; /*five filtering attempts, one for each filter type*/
05403     size_t smallest = 0;
05404     unsigned type = 0, bestType = 0;
05405     unsigned char* dummy;
05406     LodePNGCompressSettings zlibsettings = settings->zlibsettings;
05407     /*use fixed tree on the attempts so that the tree is not adapted to the filtertype on purpose,
05408     to simulate the true case where the tree is the same for the whole image. Sometimes it gives
05409     better result with dynamic tree anyway. Using the fixed tree sometimes gives worse, but in rare
05410     cases better compression. It does make this a bit less slow, so it's worth doing this.*/
05411     zlibsettings.btype = 1;
05412     /*a custom encoder likely doesn't read the btype setting and is optimized for complete PNG
05413     images only, so disable it*/
05414     zlibsettings.custom_zlib = 0;
05415     zlibsettings.custom_deflate = 0;
05416     for(type = 0; type < 5; type++)
05417     {
05418       ucvector_init(&attempt[type]);
05419       ucvector_resize(&attempt[type], linebytes); /*todo: give error if resize failed*/
05420     }
05421     for(y = 0; y < h; y++) /*try the 5 filter types*/
05422     {
05423       for(type = 0; type < 5; type++)
05424       {
05425         unsigned testsize = attempt[type].size;
05426         /*if(testsize > 8) testsize /= 8;*/ /*it already works good enough by testing a part of the row*/
05427 
05428         filterScanline(attempt[type].data, &in[y * linebytes], prevline, linebytes, bytewidth, type);
05429         size[type] = 0;
05430         dummy = 0;
05431         zlib_compress(&dummy, &size[type], attempt[type].data, testsize, &zlibsettings);
05432         lodepng_free(dummy);
05433         /*check if this is smallest size (or if type == 0 it's the first case so always store the values)*/
05434         if(type == 0 || size[type] < smallest)
05435         {
05436           bestType = type;
05437           smallest = size[type];
05438         }
05439       }
05440       prevline = &in[y * linebytes];
05441       out[y * (linebytes + 1)] = bestType; /*the first byte of a scanline will be the filter type*/
05442       for(x = 0; x < linebytes; x++) out[y * (linebytes + 1) + 1 + x] = attempt[bestType].data[x];
05443     }
05444     for(type = 0; type < 5; type++) ucvector_cleanup(&attempt[type]);
05445   }
05446   else return 88; /* unknown filter strategy */
05447 
05448   return error;
05449 }
05450 
05451 static void addPaddingBits(unsigned char* out, const unsigned char* in,
05452                            size_t olinebits, size_t ilinebits, unsigned h)
05453 {
05454   /*The opposite of the removePaddingBits function
05455   olinebits must be >= ilinebits*/
05456   unsigned y;
05457   size_t diff = olinebits - ilinebits;
05458   size_t obp = 0, ibp = 0; /*bit pointers*/
05459   for(y = 0; y < h; y++)
05460   {
05461     size_t x;
05462     for(x = 0; x < ilinebits; x++)
05463     {
05464       unsigned char bit = readBitFromReversedStream(&ibp, in);
05465       setBitOfReversedStream(&obp, out, bit);
05466     }
05467     /*obp += diff; --> no, fill in some value in the padding bits too, to avoid
05468     "Use of uninitialised value of size ###" warning from valgrind*/
05469     for(x = 0; x < diff; x++) setBitOfReversedStream(&obp, out, 0);
05470   }
05471 }
05472 
05473 /*
05474 in: non-interlaced image with size w*h
05475 out: the same pixels, but re-ordered according to PNG's Adam7 interlacing, with
05476  no padding bits between scanlines, but between reduced images so that each
05477  reduced image starts at a byte.
05478 bpp: bits per pixel
05479 there are no padding bits, not between scanlines, not between reduced images
05480 in has the following size in bits: w * h * bpp.
05481 out is possibly bigger due to padding bits between reduced images
05482 NOTE: comments about padding bits are only relevant if bpp < 8
05483 */
05484 static void Adam7_interlace(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
05485 {
05486   unsigned passw[7], passh[7];
05487   size_t filter_passstart[8], padded_passstart[8], passstart[8];
05488   unsigned i;
05489 
05490   Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
05491 
05492   if(bpp >= 8)
05493   {
05494     for(i = 0; i < 7; i++)
05495     {
05496       unsigned x, y, b;
05497       size_t bytewidth = bpp / 8;
05498       for(y = 0; y < passh[i]; y++)
05499       for(x = 0; x < passw[i]; x++)
05500       {
05501         size_t pixelinstart = ((ADAM7_IY[i] + y * ADAM7_DY[i]) * w + ADAM7_IX[i] + x * ADAM7_DX[i]) * bytewidth;
05502         size_t pixeloutstart = passstart[i] + (y * passw[i] + x) * bytewidth;
05503         for(b = 0; b < bytewidth; b++)
05504         {
05505           out[pixeloutstart + b] = in[pixelinstart + b];
05506         }
05507       }
05508     }
05509   }
05510   else /*bpp < 8: Adam7 with pixels < 8 bit is a bit trickier: with bit pointers*/
05511   {
05512     for(i = 0; i < 7; i++)
05513     {
05514       unsigned x, y, b;
05515       unsigned ilinebits = bpp * passw[i];
05516       unsigned olinebits = bpp * w;
05517       size_t obp, ibp; /*bit pointers (for out and in buffer)*/
05518       for(y = 0; y < passh[i]; y++)
05519       for(x = 0; x < passw[i]; x++)
05520       {
05521         ibp = (ADAM7_IY[i] + y * ADAM7_DY[i]) * olinebits + (ADAM7_IX[i] + x * ADAM7_DX[i]) * bpp;
05522         obp = (8 * passstart[i]) + (y * ilinebits + x * bpp);
05523         for(b = 0; b < bpp; b++)
05524         {
05525           unsigned char bit = readBitFromReversedStream(&ibp, in);
05526           setBitOfReversedStream(&obp, out, bit);
05527         }
05528       }
05529     }
05530   }
05531 }
05532 
05533 /*out must be buffer big enough to contain uncompressed IDAT chunk data, and in must contain the full image.
05534 return value is error**/
05535 static unsigned preProcessScanlines(unsigned char** out, size_t* outsize, const unsigned char* in,
05536                                     unsigned w, unsigned h,
05537                                     const LodePNGInfo* info_png, const LodePNGEncoderSettings* settings)
05538 {
05539   /*
05540   This function converts the pure 2D image with the PNG's colortype, into filtered-padded-interlaced data. Steps:
05541   *) if no Adam7: 1) add padding bits (= posible extra bits per scanline if bpp < 8) 2) filter
05542   *) if adam7: 1) Adam7_interlace 2) 7x add padding bits 3) 7x filter
05543   */
05544   unsigned bpp = lodepng_get_bpp(&info_png->color);
05545   unsigned error = 0;
05546 
05547   if(info_png->interlace_method == 0)
05548   {
05549     *outsize = h + (h * ((w * bpp + 7) / 8)); /*image size plus an extra byte per scanline + possible padding bits*/
05550     *out = (unsigned char*)lodepng_malloc(*outsize);
05551     if(!(*out) && (*outsize)) error = 83; /*alloc fail*/
05552 
05553     if(!error)
05554     {
05555       /*non multiple of 8 bits per scanline, padding bits needed per scanline*/
05556       if(bpp < 8 && w * bpp != ((w * bpp + 7) / 8) * 8)
05557       {
05558         unsigned char* padded = (unsigned char*)lodepng_malloc(h * ((w * bpp + 7) / 8));
05559         if(!padded) error = 83; /*alloc fail*/
05560         if(!error)
05561         {
05562           addPaddingBits(padded, in, ((w * bpp + 7) / 8) * 8, w * bpp, h);
05563           error = filter(*out, padded, w, h, &info_png->color, settings);
05564         }
05565         lodepng_free(padded);
05566       }
05567       else
05568       {
05569         /*we can immediatly filter into the out buffer, no other steps needed*/
05570         error = filter(*out, in, w, h, &info_png->color, settings);
05571       }
05572     }
05573   }
05574   else /*interlace_method is 1 (Adam7)*/
05575   {
05576     unsigned passw[7], passh[7];
05577     size_t filter_passstart[8], padded_passstart[8], passstart[8];
05578     unsigned char* adam7;
05579 
05580     Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
05581 
05582     *outsize = filter_passstart[7]; /*image size plus an extra byte per scanline + possible padding bits*/
05583     *out = (unsigned char*)lodepng_malloc(*outsize);
05584     if(!(*out)) error = 83; /*alloc fail*/
05585 
05586     adam7 = (unsigned char*)lodepng_malloc(passstart[7]);
05587     if(!adam7 && passstart[7]) error = 83; /*alloc fail*/
05588 
05589     if(!error)
05590     {
05591       unsigned i;
05592 
05593       Adam7_interlace(adam7, in, w, h, bpp);
05594       for(i = 0; i < 7; i++)
05595       {
05596         if(bpp < 8)
05597         {
05598           unsigned char* padded = (unsigned char*)lodepng_malloc(padded_passstart[i + 1] - padded_passstart[i]);
05599           if(!padded) ERROR_BREAK(83); /*alloc fail*/
05600           addPaddingBits(padded, &adam7[passstart[i]],
05601                          ((passw[i] * bpp + 7) / 8) * 8, passw[i] * bpp, passh[i]);
05602           error = filter(&(*out)[filter_passstart[i]], padded,
05603                          passw[i], passh[i], &info_png->color, settings);
05604           lodepng_free(padded);
05605         }
05606         else
05607         {
05608           error = filter(&(*out)[filter_passstart[i]], &adam7[padded_passstart[i]],
05609                          passw[i], passh[i], &info_png->color, settings);
05610         }
05611 
05612         if(error) break;
05613       }
05614     }
05615 
05616     lodepng_free(adam7);
05617   }
05618 
05619   return error;
05620 }
05621 
05622 /*
05623 palette must have 4 * palettesize bytes allocated, and given in format RGBARGBARGBARGBA...
05624 returns 0 if the palette is opaque,
05625 returns 1 if the palette has a single color with alpha 0 ==> color key
05626 returns 2 if the palette is semi-translucent.
05627 */
05628 static unsigned getPaletteTranslucency(const unsigned char* palette, size_t palettesize)
05629 {
05630   size_t i, key = 0;
05631   unsigned r = 0, g = 0, b = 0; /*the value of the color with alpha 0, so long as color keying is possible*/
05632   for(i = 0; i < palettesize; i++)
05633   {
05634     if(!key && palette[4 * i + 3] == 0)
05635     {
05636       r = palette[4 * i + 0]; g = palette[4 * i + 1]; b = palette[4 * i + 2];
05637       key = 1;
05638       i = (size_t)(-1); /*restart from beginning, to detect earlier opaque colors with key's value*/
05639     }
05640     else if(palette[4 * i + 3] != 255) return 2;
05641     /*when key, no opaque RGB may have key's RGB*/
05642     else if(key && r == palette[i * 4 + 0] && g == palette[i * 4 + 1] && b == palette[i * 4 + 2]) return 2;
05643   }
05644   return key;
05645 }
05646 
05647 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
05648 static unsigned addUnknownChunks(ucvector* out, unsigned char* data, size_t datasize)
05649 {
05650   unsigned char* inchunk = data;
05651   while((size_t)(inchunk - data) < datasize)
05652   {
05653     CERROR_TRY_RETURN(lodepng_chunk_append(&out->data, &out->size, inchunk));
05654     out->allocsize = out->size; /*fix the allocsize again*/
05655     inchunk = lodepng_chunk_next(inchunk);
05656   }
05657   return 0;
05658 }
05659 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
05660 
05661 unsigned lodepng_encode(unsigned char** out, size_t* outsize,
05662                         const unsigned char* image, unsigned w, unsigned h,
05663                         LodePNGState* state)
05664 {
05665   LodePNGInfo info;
05666   ucvector outv;
05667   unsigned char* data = 0; /*uncompressed version of the IDAT chunk data*/
05668   size_t datasize = 0;
05669 
05670   /*provide some proper output values if error will happen*/
05671   *out = 0;
05672   *outsize = 0;
05673   state->error = 0;
05674 
05675   lodepng_info_init(&info);
05676   lodepng_info_copy(&info, &state->info_png);
05677 
05678   if((info.color.colortype == LCT_PALETTE || state->encoder.force_palette)
05679       && (info.color.palettesize == 0 || info.color.palettesize > 256))
05680   {
05681     state->error = 68; /*invalid palette size, it is only allowed to be 1-256*/
05682     return state->error;
05683   }
05684 
05685   if(state->encoder.auto_convert != LAC_NO)
05686   {
05687     state->error = lodepng_auto_choose_color(&info.color, image, w, h, &state->info_raw,
05688                                              state->encoder.auto_convert);
05689   }
05690   if(state->error) return state->error;
05691 
05692   if(state->encoder.zlibsettings.btype > 2)
05693   {
05694     CERROR_RETURN_ERROR(state->error, 61); /*error: unexisting btype*/
05695   }
05696   if(state->info_png.interlace_method > 1)
05697   {
05698     CERROR_RETURN_ERROR(state->error, 71); /*error: unexisting interlace mode*/
05699   }
05700 
05701   state->error = checkColorValidity(info.color.colortype, info.color.bitdepth);
05702   if(state->error) return state->error; /*error: unexisting color type given*/
05703   state->error = checkColorValidity(state->info_raw.colortype, state->info_raw.bitdepth);
05704   if(state->error) return state->error; /*error: unexisting color type given*/
05705 
05706   if(!lodepng_color_mode_equal(&state->info_raw, &info.color))
05707   {
05708     unsigned char* converted;
05709     size_t size = (w * h * lodepng_get_bpp(&info.color) + 7) / 8;
05710 
05711     converted = (unsigned char*)lodepng_malloc(size);
05712     if(!converted && size) state->error = 83; /*alloc fail*/
05713     if(!state->error)
05714     {
05715       state->error = lodepng_convert(converted, image, &info.color, &state->info_raw, w, h, 0 /*fix_png*/);
05716     }
05717     if(!state->error) preProcessScanlines(&data, &datasize, converted, w, h, &info, &state->encoder);
05718     lodepng_free(converted);
05719   }
05720   else preProcessScanlines(&data, &datasize, image, w, h, &info, &state->encoder);
05721 
05722   ucvector_init(&outv);
05723   while(!state->error) /*while only executed once, to break on error*/
05724   {
05725 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
05726     size_t i;
05727 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
05728     /*write signature and chunks*/
05729     writeSignature(&outv);
05730     /*IHDR*/
05731     addChunk_IHDR(&outv, w, h, info.color.colortype, info.color.bitdepth, info.interlace_method);
05732 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
05733     /*unknown chunks between IHDR and PLTE*/
05734     if(info.unknown_chunks_data[0])
05735     {
05736       state->error = addUnknownChunks(&outv, info.unknown_chunks_data[0], info.unknown_chunks_size[0]);
05737       if(state->error) break;
05738     }
05739 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
05740     /*PLTE*/
05741     if(info.color.colortype == LCT_PALETTE)
05742     {
05743       addChunk_PLTE(&outv, &info.color);
05744     }
05745     if(state->encoder.force_palette && (info.color.colortype == LCT_RGB || info.color.colortype == LCT_RGBA))
05746     {
05747       addChunk_PLTE(&outv, &info.color);
05748     }
05749     /*tRNS*/
05750     if(info.color.colortype == LCT_PALETTE && getPaletteTranslucency(info.color.palette, info.color.palettesize) != 0)
05751     {
05752       addChunk_tRNS(&outv, &info.color);
05753     }
05754     if((info.color.colortype == LCT_GREY || info.color.colortype == LCT_RGB) && info.color.key_defined)
05755     {
05756       addChunk_tRNS(&outv, &info.color);
05757     }
05758 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
05759     /*bKGD (must come between PLTE and the IDAt chunks*/
05760     if(info.background_defined) addChunk_bKGD(&outv, &info);
05761     /*pHYs (must come before the IDAT chunks)*/
05762     if(info.phys_defined) addChunk_pHYs(&outv, &info);
05763 
05764     /*unknown chunks between PLTE and IDAT*/
05765     if(info.unknown_chunks_data[1])
05766     {
05767       state->error = addUnknownChunks(&outv, info.unknown_chunks_data[1], info.unknown_chunks_size[1]);
05768       if(state->error) break;
05769     }
05770 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
05771     /*IDAT (multiple IDAT chunks must be consecutive)*/
05772     state->error = addChunk_IDAT(&outv, data, datasize, &state->encoder.zlibsettings);
05773     if(state->error) break;
05774 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
05775     /*tIME*/
05776     if(info.time_defined) addChunk_tIME(&outv, &info.time);
05777     /*tEXt and/or zTXt*/
05778     for(i = 0; i < info.text_num; i++)
05779     {
05780       if(strlen(info.text_keys[i]) > 79)
05781       {
05782         state->error = 66; /*text chunk too large*/
05783         break;
05784       }
05785       if(strlen(info.text_keys[i]) < 1)
05786       {
05787         state->error = 67; /*text chunk too small*/
05788         break;
05789       }
05790       if(state->encoder.text_compression)
05791       {
05792         addChunk_zTXt(&outv, info.text_keys[i], info.text_strings[i], &state->encoder.zlibsettings);
05793       }
05794       else
05795       {
05796         addChunk_tEXt(&outv, info.text_keys[i], info.text_strings[i]);
05797       }
05798     }
05799     /*LodePNG version id in text chunk*/
05800     if(state->encoder.add_id)
05801     {
05802       unsigned alread_added_id_text = 0;
05803       for(i = 0; i < info.text_num; i++)
05804       {
05805         if(!strcmp(info.text_keys[i], "LodePNG"))
05806         {
05807           alread_added_id_text = 1;
05808           break;
05809         }
05810       }
05811       if(alread_added_id_text == 0)
05812       {
05813         addChunk_tEXt(&outv, "LodePNG", VERSION_STRING); /*it's shorter as tEXt than as zTXt chunk*/
05814       }
05815     }
05816     /*iTXt*/
05817     for(i = 0; i < info.itext_num; i++)
05818     {
05819       if(strlen(info.itext_keys[i]) > 79)
05820       {
05821         state->error = 66; /*text chunk too large*/
05822         break;
05823       }
05824       if(strlen(info.itext_keys[i]) < 1)
05825       {
05826         state->error = 67; /*text chunk too small*/
05827         break;
05828       }
05829       addChunk_iTXt(&outv, state->encoder.text_compression,
05830                     info.itext_keys[i], info.itext_langtags[i], info.itext_transkeys[i], info.itext_strings[i],
05831                     &state->encoder.zlibsettings);
05832     }
05833 
05834     /*unknown chunks between IDAT and IEND*/
05835     if(info.unknown_chunks_data[2])
05836     {
05837       state->error = addUnknownChunks(&outv, info.unknown_chunks_data[2], info.unknown_chunks_size[2]);
05838       if(state->error) break;
05839     }
05840 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
05841     addChunk_IEND(&outv);
05842 
05843     break; /*this isn't really a while loop; no error happened so break out now!*/
05844   }
05845 
05846   lodepng_info_cleanup(&info);
05847   lodepng_free(data);
05848   /*instead of cleaning the vector up, give it to the output*/
05849   *out = outv.data;
05850   *outsize = outv.size;
05851 
05852   return state->error;
05853 }
05854 
05855 unsigned lodepng_encode_memory(unsigned char** out, size_t* outsize, const unsigned char* image,
05856                                unsigned w, unsigned h, LodePNGColorType colortype, unsigned bitdepth)
05857 {
05858   unsigned error;
05859   LodePNGState state;
05860   lodepng_state_init(&state);
05861   state.info_raw.colortype = colortype;
05862   state.info_raw.bitdepth = bitdepth;
05863   state.info_png.color.colortype = colortype;
05864   state.info_png.color.bitdepth = bitdepth;
05865   lodepng_encode(out, outsize, image, w, h, &state);
05866   error = state.error;
05867   lodepng_state_cleanup(&state);
05868   return error;
05869 }
05870 
05871 unsigned lodepng_encode32(unsigned char** out, size_t* outsize, const unsigned char* image, unsigned w, unsigned h)
05872 {
05873   return lodepng_encode_memory(out, outsize, image, w, h, LCT_RGBA, 8);
05874 }
05875 
05876 unsigned lodepng_encode24(unsigned char** out, size_t* outsize, const unsigned char* image, unsigned w, unsigned h)
05877 {
05878   return lodepng_encode_memory(out, outsize, image, w, h, LCT_RGB, 8);
05879 }
05880 
05881 #ifdef LODEPNG_COMPILE_DISK
05882 unsigned lodepng_encode_file(const char* filename, const unsigned char* image, unsigned w, unsigned h,
05883                              LodePNGColorType colortype, unsigned bitdepth)
05884 {
05885   unsigned char* buffer;
05886   size_t buffersize;
05887   unsigned error = lodepng_encode_memory(&buffer, &buffersize, image, w, h, colortype, bitdepth);
05888   if(!error) error = lodepng_save_file(buffer, buffersize, filename);
05889   lodepng_free(buffer);
05890   return error;
05891 }
05892 
05893 unsigned lodepng_encode32_file(const char* filename, const unsigned char* image, unsigned w, unsigned h)
05894 {
05895   return lodepng_encode_file(filename, image, w, h, LCT_RGBA, 8);
05896 }
05897 
05898 unsigned lodepng_encode24_file(const char* filename, const unsigned char* image, unsigned w, unsigned h)
05899 {
05900   return lodepng_encode_file(filename, image, w, h, LCT_RGB, 8);
05901 }
05902 #endif /*LODEPNG_COMPILE_DISK*/
05903 
05904 void lodepng_encoder_settings_init(LodePNGEncoderSettings* settings)
05905 {
05906   lodepng_compress_settings_init(&settings->zlibsettings);
05907   settings->filter_palette_zero = 1;
05908   settings->filter_strategy = LFS_MINSUM;
05909   settings->auto_convert = LAC_AUTO;
05910   settings->force_palette = 0;
05911   settings->predefined_filters = 0;
05912 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
05913   settings->add_id = 0;
05914   settings->text_compression = 1;
05915 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
05916 }
05917 
05918 #endif /*LODEPNG_COMPILE_ENCODER*/
05919 #endif /*LODEPNG_COMPILE_PNG*/
05920 
05921 #ifdef LODEPNG_COMPILE_ERROR_TEXT
05922 /*
05923 This returns the description of a numerical error code in English. This is also
05924 the documentation of all the error codes.
05925 */
05926 const char* lodepng_error_text(unsigned code)
05927 {
05928   switch(code)
05929   {
05930     case 0: return "no error, everything went ok";
05931     case 1: return "nothing done yet"; /*the Encoder/Decoder has done nothing yet, error checking makes no sense yet*/
05932     case 10: return "end of input memory reached without huffman end code"; /*while huffman decoding*/
05933     case 11: return "error in code tree made it jump outside of huffman tree"; /*while huffman decoding*/
05934     case 13: return "problem while processing dynamic deflate block";
05935     case 14: return "problem while processing dynamic deflate block";
05936     case 15: return "problem while processing dynamic deflate block";
05937     case 16: return "unexisting code while processing dynamic deflate block";
05938     case 17: return "end of out buffer memory reached while inflating";
05939     case 18: return "invalid distance code while inflating";
05940     case 19: return "end of out buffer memory reached while inflating";
05941     case 20: return "invalid deflate block BTYPE encountered while decoding";
05942     case 21: return "NLEN is not ones complement of LEN in a deflate block";
05943      /*end of out buffer memory reached while inflating:
05944      This can happen if the inflated deflate data is longer than the amount of bytes required to fill up
05945      all the pixels of the image, given the color depth and image dimensions. Something that doesn't
05946      happen in a normal, well encoded, PNG image.*/
05947     case 22: return "end of out buffer memory reached while inflating";
05948     case 23: return "end of in buffer memory reached while inflating";
05949     case 24: return "invalid FCHECK in zlib header";
05950     case 25: return "invalid compression method in zlib header";
05951     case 26: return "FDICT encountered in zlib header while it's not used for PNG";
05952     case 27: return "PNG file is smaller than a PNG header";
05953     /*Checks the magic file header, the first 8 bytes of the PNG file*/
05954     case 28: return "incorrect PNG signature, it's no PNG or corrupted";
05955     case 29: return "first chunk is not the header chunk";
05956     case 30: return "chunk length too large, chunk broken off at end of file";
05957     case 31: return "illegal PNG color type or bpp";
05958     case 32: return "illegal PNG compression method";
05959     case 33: return "illegal PNG filter method";
05960     case 34: return "illegal PNG interlace method";
05961     case 35: return "chunk length of a chunk is too large or the chunk too small";
05962     case 36: return "illegal PNG filter type encountered";
05963     case 37: return "illegal bit depth for this color type given";
05964     case 38: return "the palette is too big"; /*more than 256 colors*/
05965     case 39: return "more palette alpha values given in tRNS chunk than there are colors in the palette";
05966     case 40: return "tRNS chunk has wrong size for greyscale image";
05967     case 41: return "tRNS chunk has wrong size for RGB image";
05968     case 42: return "tRNS chunk appeared while it was not allowed for this color type";
05969     case 43: return "bKGD chunk has wrong size for palette image";
05970     case 44: return "bKGD chunk has wrong size for greyscale image";
05971     case 45: return "bKGD chunk has wrong size for RGB image";
05972     /*Is the palette too small?*/
05973     case 46: return "a value in indexed image is larger than the palette size (bitdepth = 8)";
05974     /*Is the palette too small?*/
05975     case 47: return "a value in indexed image is larger than the palette size (bitdepth < 8)";
05976     /*the input data is empty, maybe a PNG file doesn't exist or is in the wrong path*/
05977     case 48: return "empty input or file doesn't exist";
05978     case 49: return "jumped past memory while generating dynamic huffman tree";
05979     case 50: return "jumped past memory while generating dynamic huffman tree";
05980     case 51: return "jumped past memory while inflating huffman block";
05981     case 52: return "jumped past memory while inflating";
05982     case 53: return "size of zlib data too small";
05983     case 54: return "repeat symbol in tree while there was no value symbol yet";
05984     /*jumped past tree while generating huffman tree, this could be when the
05985     tree will have more leaves than symbols after generating it out of the
05986     given lenghts. They call this an oversubscribed dynamic bit lengths tree in zlib.*/
05987     case 55: return "jumped past tree while generating huffman tree";
05988     case 56: return "given output image colortype or bitdepth not supported for color conversion";
05989     case 57: return "invalid CRC encountered (checking CRC can be disabled)";
05990     case 58: return "invalid ADLER32 encountered (checking ADLER32 can be disabled)";
05991     case 59: return "requested color conversion not supported";
05992     case 60: return "invalid window size given in the settings of the encoder (must be 0-32768)";
05993     case 61: return "invalid BTYPE given in the settings of the encoder (only 0, 1 and 2 are allowed)";
05994     /*LodePNG leaves the choice of RGB to greyscale conversion formula to the user.*/
05995     case 62: return "conversion from color to greyscale not supported";
05996     case 63: return "length of a chunk too long, max allowed for PNG is 2147483647 bytes per chunk"; /*(2^31-1)*/
05997     /*this would result in the inability of a deflated block to ever contain an end code. It must be at least 1.*/
05998     case 64: return "the length of the END symbol 256 in the Huffman tree is 0";
05999     case 66: return "the length of a text chunk keyword given to the encoder is longer than the maximum of 79 bytes";
06000     case 67: return "the length of a text chunk keyword given to the encoder is smaller than the minimum of 1 byte";
06001     case 68: return "tried to encode a PLTE chunk with a palette that has less than 1 or more than 256 colors";
06002     case 69: return "unknown chunk type with 'critical' flag encountered by the decoder";
06003     case 71: return "unexisting interlace mode given to encoder (must be 0 or 1)";
06004     case 72: return "while decoding, unexisting compression method encountering in zTXt or iTXt chunk (it must be 0)";
06005     case 73: return "invalid tIME chunk size";
06006     case 74: return "invalid pHYs chunk size";
06007     /*length could be wrong, or data chopped off*/
06008     case 75: return "no null termination char found while decoding text chunk";
06009     case 76: return "iTXt chunk too short to contain required bytes";
06010     case 77: return "integer overflow in buffer size";
06011     case 78: return "failed to open file for reading"; /*file doesn't exist or couldn't be opened for reading*/
06012     case 79: return "failed to open file for writing";
06013     case 80: return "tried creating a tree of 0 symbols";
06014     case 81: return "lazy matching at pos 0 is impossible";
06015     case 82: return "color conversion to palette requested while a color isn't in palette";
06016     case 83: return "memory allocation failed";
06017     case 84: return "given image too small to contain all pixels to be encoded";
06018     case 85: return "internal color conversion bug";
06019     case 86: return "impossible offset in lz77 encoding (internal bug)";
06020     case 87: return "must provide custom zlib function pointer if LODEPNG_COMPILE_ZLIB is not defined";
06021     case 88: return "invalid filter strategy given for LodePNGEncoderSettings.filter_strategy";
06022     case 89: return "text chunk keyword too short or long: must have size 1-79";
06023     /*the windowsize in the LodePNGCompressSettings. Requiring POT(==> & instead of %) makes encoding 12% faster.*/
06024     case 90: return "windowsize must be a power of two";
06025   }
06026   return "unknown error code";
06027 }
06028 #endif /*LODEPNG_COMPILE_ERROR_TEXT*/
06029 
06030 /* ////////////////////////////////////////////////////////////////////////// */
06031 /* ////////////////////////////////////////////////////////////////////////// */
06032 /* // C++ Wrapper                                                          // */
06033 /* ////////////////////////////////////////////////////////////////////////// */
06034 /* ////////////////////////////////////////////////////////////////////////// */
06035 
06036 #ifdef LODEPNG_COMPILE_CPP
06037 namespace lodepng
06038 {
06039 
06040 #ifdef LODEPNG_COMPILE_DISK
06041 void load_file(std::vector<unsigned char>& buffer, const std::string& filename)
06042 {
06043   std::ifstream file(filename.c_str(), std::ios::in|std::ios::binary|std::ios::ate);
06044 
06045   /*get filesize*/
06046   std::streamsize size = 0;
06047   if(file.seekg(0, std::ios::end).good()) size = file.tellg();
06048   if(file.seekg(0, std::ios::beg).good()) size -= file.tellg();
06049 
06050   /*read contents of the file into the vector*/
06051   buffer.resize(size_t(size));
06052   if(size > 0) file.read((char*)(&buffer[0]), size);
06053 }
06054 
06055 /*write given buffer to the file, overwriting the file, it doesn't append to it.*/
06056 void save_file(const std::vector<unsigned char>& buffer, const std::string& filename)
06057 {
06058   std::ofstream file(filename.c_str(), std::ios::out|std::ios::binary);
06059   file.write(buffer.empty() ? 0 : (char*)&buffer[0], std::streamsize(buffer.size()));
06060 }
06061 #endif //LODEPNG_COMPILE_DISK
06062 
06063 #ifdef LODEPNG_COMPILE_ZLIB
06064 #ifdef LODEPNG_COMPILE_DECODER
06065 unsigned decompress(std::vector<unsigned char>& out, const unsigned char* in, size_t insize,
06066                     const LodePNGDecompressSettings& settings)
06067 {
06068   unsigned char* buffer = 0;
06069   size_t buffersize = 0;
06070   unsigned error = zlib_decompress(&buffer, &buffersize, in, insize, &settings);
06071   if(buffer)
06072   {
06073     out.insert(out.end(), &buffer[0], &buffer[buffersize]);
06074     lodepng_free(buffer);
06075   }
06076   return error;
06077 }
06078 
06079 unsigned decompress(std::vector<unsigned char>& out, const std::vector<unsigned char>& in,
06080                     const LodePNGDecompressSettings& settings)
06081 {
06082   return decompress(out, in.empty() ? 0 : &in[0], in.size(), settings);
06083 }
06084 #endif //LODEPNG_COMPILE_DECODER
06085 
06086 #ifdef LODEPNG_COMPILE_ENCODER
06087 unsigned compress(std::vector<unsigned char>& out, const unsigned char* in, size_t insize,
06088                   const LodePNGCompressSettings& settings)
06089 {
06090   unsigned char* buffer = 0;
06091   size_t buffersize = 0;
06092   unsigned error = zlib_compress(&buffer, &buffersize, in, insize, &settings);
06093   if(buffer)
06094   {
06095     out.insert(out.end(), &buffer[0], &buffer[buffersize]);
06096     lodepng_free(buffer);
06097   }
06098   return error;
06099 }
06100 
06101 unsigned compress(std::vector<unsigned char>& out, const std::vector<unsigned char>& in,
06102                   const LodePNGCompressSettings& settings)
06103 {
06104   return compress(out, in.empty() ? 0 : &in[0], in.size(), settings);
06105 }
06106 #endif //LODEPNG_COMPILE_ENCODER
06107 #endif //LODEPNG_COMPILE_ZLIB
06108 
06109 
06110 #ifdef LODEPNG_COMPILE_PNG
06111 
06112 State::State()
06113 {
06114   lodepng_state_init(this);
06115 }
06116 
06117 State::State(const State& other)
06118 {
06119   lodepng_state_init(this);
06120   lodepng_state_copy(this, &other);
06121 }
06122 
06123 State::~State()
06124 {
06125   lodepng_state_cleanup(this);
06126 }
06127 
06128 State& State::operator=(const State& other)
06129 {
06130   lodepng_state_copy(this, &other);
06131   return *this;
06132 }
06133 
06134 #ifdef LODEPNG_COMPILE_DECODER
06135 
06136 unsigned decode(std::vector<unsigned char>& out, unsigned& w, unsigned& h, const unsigned char* in,
06137                 size_t insize, LodePNGColorType colortype, unsigned bitdepth)
06138 {
06139   unsigned char* buffer;
06140   unsigned error = lodepng_decode_memory(&buffer, &w, &h, in, insize, colortype, bitdepth);
06141   if(buffer && !error)
06142   {
06143     State state;
06144     state.info_raw.colortype = colortype;
06145     state.info_raw.bitdepth = bitdepth;
06146     size_t buffersize = lodepng_get_raw_size(w, h, &state.info_raw);
06147     out.insert(out.end(), &buffer[0], &buffer[buffersize]);
06148     lodepng_free(buffer);
06149   }
06150   return error;
06151 }
06152 
06153 unsigned decode(std::vector<unsigned char>& out, unsigned& w, unsigned& h,
06154                 const std::vector<unsigned char>& in, LodePNGColorType colortype, unsigned bitdepth)
06155 {
06156   return decode(out, w, h, in.empty() ? 0 : &in[0], (unsigned)in.size(), colortype, bitdepth);
06157 }
06158 
06159 unsigned decode(std::vector<unsigned char>& out, unsigned& w, unsigned& h,
06160                 State& state,
06161                 const unsigned char* in, size_t insize)
06162 {
06163   unsigned char* buffer = NULL;
06164   unsigned error = lodepng_decode(&buffer, &w, &h, &state, in, insize);
06165   if(buffer && !error)
06166   {
06167     size_t buffersize = lodepng_get_raw_size(w, h, &state.info_raw);
06168     out.insert(out.end(), &buffer[0], &buffer[buffersize]);
06169   }
06170   lodepng_free(buffer);
06171   return error;
06172 }
06173 
06174 unsigned decode(std::vector<unsigned char>& out, unsigned& w, unsigned& h,
06175                 State& state,
06176                 const std::vector<unsigned char>& in)
06177 {
06178   return decode(out, w, h, state, in.empty() ? 0 : &in[0], in.size());
06179 }
06180 
06181 #ifdef LODEPNG_COMPILE_DISK
06182 unsigned decode(std::vector<unsigned char>& out, unsigned& w, unsigned& h, const std::string& filename,
06183                 LodePNGColorType colortype, unsigned bitdepth)
06184 {
06185   std::vector<unsigned char> buffer;
06186   load_file(buffer, filename);
06187   return decode(out, w, h, buffer, colortype, bitdepth);
06188 }
06189 #endif //LODEPNG_COMPILE_DECODER
06190 #endif //LODEPNG_COMPILE_DISK
06191 
06192 #ifdef LODEPNG_COMPILE_ENCODER
06193 unsigned encode(std::vector<unsigned char>& out, const unsigned char* in, unsigned w, unsigned h,
06194                 LodePNGColorType colortype, unsigned bitdepth)
06195 {
06196   unsigned char* buffer;
06197   size_t buffersize;
06198   unsigned error = lodepng_encode_memory(&buffer, &buffersize, in, w, h, colortype, bitdepth);
06199   if(buffer)
06200   {
06201     out.insert(out.end(), &buffer[0], &buffer[buffersize]);
06202     lodepng_free(buffer);
06203   }
06204   return error;
06205 }
06206 
06207 unsigned encode(std::vector<unsigned char>& out,
06208                 const std::vector<unsigned char>& in, unsigned w, unsigned h,
06209                 LodePNGColorType colortype, unsigned bitdepth)
06210 {
06211   if(lodepng_get_raw_size_lct(w, h, colortype, bitdepth) > in.size()) return 84;
06212   return encode(out, in.empty() ? 0 : &in[0], w, h, colortype, bitdepth);
06213 }
06214 
06215 unsigned encode(std::vector<unsigned char>& out,
06216                 const unsigned char* in, unsigned w, unsigned h,
06217                 State& state)
06218 {
06219   unsigned char* buffer;
06220   size_t buffersize;
06221   unsigned error = lodepng_encode(&buffer, &buffersize, in, w, h, &state);
06222   if(buffer)
06223   {
06224     out.insert(out.end(), &buffer[0], &buffer[buffersize]);
06225     lodepng_free(buffer);
06226   }
06227   return error;
06228 }
06229 
06230 unsigned encode(std::vector<unsigned char>& out,
06231                 const std::vector<unsigned char>& in, unsigned w, unsigned h,
06232                 State& state)
06233 {
06234   if(lodepng_get_raw_size(w, h, &state.info_raw) > in.size()) return 84;
06235   return encode(out, in.empty() ? 0 : &in[0], w, h, state);
06236 }
06237 
06238 #ifdef LODEPNG_COMPILE_DISK
06239 unsigned encode(const std::string& filename,
06240                 const unsigned char* in, unsigned w, unsigned h,
06241                 LodePNGColorType colortype, unsigned bitdepth)
06242 {
06243   std::vector<unsigned char> buffer;
06244   unsigned error = encode(buffer, in, w, h, colortype, bitdepth);
06245   if(!error) save_file(buffer, filename);
06246   return error;
06247 }
06248 
06249 unsigned encode(const std::string& filename,
06250                 const std::vector<unsigned char>& in, unsigned w, unsigned h,
06251                 LodePNGColorType colortype, unsigned bitdepth)
06252 {
06253   if(lodepng_get_raw_size_lct(w, h, colortype, bitdepth) > in.size()) return 84;
06254   return encode(filename, in.empty() ? 0 : &in[0], w, h, colortype, bitdepth);
06255 }
06256 #endif //LODEPNG_COMPILE_DISK
06257 #endif //LODEPNG_COMPILE_ENCODER
06258 #endif //LODEPNG_COMPILE_PNG
06259 } //namespace lodepng
06260 #endif /*LODEPNG_COMPILE_CPP*/
06261