src/lodepng.cpp

   1 /*
   2 LodePNG version 20080927
   3
   4 Copyright (c) 2005-2008 Lode Vandevenne
   5
   6 This software is provided 'as-is', without any express or implied
   7 warranty. In no event will the authors be held liable for any damages
   8 arising from the use of this software.
   9
  10 Permission is granted to anyone to use this software for any purpose,
  11 including commercial applications, and to alter it and redistribute it
  12 freely, subject to the following restrictions:
  13
  14     1. The origin of this software must not be misrepresented; you must not
  15     claim that you wrote the original software. If you use this software
  16     in a product, an acknowledgment in the product documentation would be
  17     appreciated but is not required.
  18
  19     2. Altered source versions must be plainly marked as such, and must not be
  20     misrepresented as being the original software.
  21
  22     3. This notice may not be removed or altered from any source
  23     distribution.
  24 */
  25
  26 /*
  27 The manual and changelog can be found in the header file "lodepng.h"
  28 You are free to name this file lodepng.cpp or lodepng.c depending on your usage.
  29 */
  30
  31 #include "lodepng.h"
  32 #include "portable.h"
  33
  34 #define USE_BRUTE_FORCE_ENCODING 1
  35
  36 #define VERSION_STRING "20080927"
  37
  38 /* ////////////////////////////////////////////////////////////////////////// */
  39 /* / Tools For C                                                            / */
  40 /* ////////////////////////////////////////////////////////////////////////// */
  41
  42 /*
  43 About these tools (vector, uivector, ucvector and string):
  44 -LodePNG was originally written in C++. The vectors replace the std::vectors that were used in the C++ version.
  45 -The string tools are made to avoid problems with compilers that declare things like strncat as deprecated.
  46 -They're not used in the interface, only internally in this file, so all their functions are made static.
  47 */
  48
  49 #ifdef LODEPNG_COMPILE_ZLIB
  50 #ifdef LODEPNG_COMPILE_ENCODER
  51
  52 typedef struct vector /*this one is used only by the deflate compressor*/
  53 {
  54   void* data;
  55   size_t size; /*in groups of bytes depending on type*/
  56   size_t allocsize; /*in bytes*/
  57   unsigned typesize; /*sizeof the type you store in data*/
  58 } vector;
  59
  60 static unsigned vector_resize(vector* p, size_t size) /*returns 1 if success, 0 if failure ==> nothing done*/
  61 {
  62   if(size * p->typesize > p->allocsize)
  63   {
  64     size_t newsize = size * p->typesize * 2;
  65     void* data = realloc(p->data, newsize);
  66     if(data)
  67     {
  68       p->allocsize = newsize;
  69       p->data = data;
  70       p->size = size;
  71     }
  72     else return 0;
  73   }
  74   else p->size = size;
  75   return 1;
  76 }
  77
  78 static unsigned vector_resized(vector* p, size_t size, void dtor(void*)) /*resize and use destructor on elements if it gets smaller*/
  79 {
  80   size_t i;
  81   if(size < p->size) for(i = size; i < p->size; i++) dtor(&((char*)(p->data))[i * p->typesize]);
  82   return vector_resize(p, size);
  83 }
  84
  85 static void vector_cleanup(void* p)
  86 {
  87   ((vector*)p)->size = ((vector*)p)->allocsize = 0;
  88   free(((vector*)p)->data);
  89   ((vector*)p)->data = NULL;
  90 }
  91
  92 static void vector_cleanupd(vector* p, void dtor(void*)) /*clear and use destructor on elements*/
  93 {
  94   vector_resized(p, 0, dtor);
  95   vector_cleanup(p);
  96 }
  97
  98 static void vector_init(vector* p, unsigned typesize)
  99 {
 100   p->data = NULL;
 101   p->size = p->allocsize = 0;
 102   p->typesize = typesize;
 103 }
 104
 105 static void vector_swap(vector* p, vector* q) /*they're supposed to have the same typesize*/
 106 {
 107   size_t tmp;
 108   void* tmpp;
 109   tmp = p->size; p->size = q->size; q->size = tmp;
 110   tmp = p->allocsize; p->allocsize = q->allocsize; q->allocsize = tmp;
 111   tmpp = p->data; p->data = q->data; q->data = tmpp;
 112 }
 113
 114 static void* vector_get(vector* p, size_t index)
 115 {
 116   return &((char*)p->data)[index * p->typesize];
 117 }
 118 #endif /*LODEPNG_COMPILE_ENCODER*/
 119 #endif /*LODEPNG_COMPILE_ZLIB*/
 120
 121 /* /////////////////////////////////////////////////////////////////////////// */
 122
 123 #ifdef LODEPNG_COMPILE_ZLIB
 124 typedef struct uivector
 125 {
 126   unsigned* data;
 127   size_t size; /*size in number of unsigned longs*/
 128   size_t allocsize; /*allocated size in bytes*/
 129 } uivector;
 130
 131 static void uivector_cleanup(void* p)
 132 {
 133   ((uivector*)p)->size = ((uivector*)p)->allocsize = 0;
 134   free(((uivector*)p)->data);
 135   ((uivector*)p)->data = NULL;
 136 }
 137
 138 static unsigned uivector_resize(uivector* p, size_t size) /*returns 1 if success, 0 if failure ==> nothing done*/
 139 {
 140   if(size * sizeof(unsigned) > p->allocsize)
 141   {
 142     size_t newsize = size * sizeof(unsigned) * 2;
 143     void* data = realloc(p->data, newsize);
 144     if(data)
 145     {
 146       p->allocsize = newsize;
 147       p->data = (unsigned*)data;
 148       p->size = size;
 149     }
 150     else return 0;
 151   }
 152   else p->size = size;
 153   return 1;
 154 }
 155
 156 static unsigned uivector_resizev(uivector* p, size_t size, unsigned value) /*resize and give all new elements the value*/
 157 {
 158   size_t oldsize = p->size, i;
 159   if(!uivector_resize(p, size)) return 0;
 160   for(i = oldsize; i < size; i++) p->data[i] = value;
 161   return 1;
 162 }
 163
 164 static void uivector_init(uivector* p)
 165 {
 166   p->data = NULL;
 167   p->size = p->allocsize = 0;
 168 }
 169
 170 #ifdef LODEPNG_COMPILE_ENCODER
 171 static unsigned uivector_push_back(uivector* p, unsigned c) /*returns 1 if success, 0 if failure ==> nothing done*/
 172 {
 173   if(!uivector_resize(p, p->size + 1)) return 0;
 174   p->data[p->size - 1] = c;
 175   return 1;
 176 }
 177
 178 static unsigned uivector_copy(uivector* p, const uivector* q) /*copy q to p, returns 1 if success, 0 if failure ==> nothing done*/
 179 {
 180   size_t i;
 181   if(!uivector_resize(p, q->size)) return 0;
 182   for(i = 0; i < q->size; i++) p->data[i] = q->data[i];
 183   return 1;
 184 }
 185
 186 static void uivector_swap(uivector* p, uivector* q)
 187 {
 188   size_t tmp;
 189   unsigned* tmpp;
 190   tmp = p->size; p->size = q->size; q->size = tmp;
 191   tmp = p->allocsize; p->allocsize = q->allocsize; q->allocsize = tmp;
 192   tmpp = p->data; p->data = q->data; q->data = tmpp;
 193 }
 194 #endif /*LODEPNG_COMPILE_ENCODER*/
 195 #endif /*LODEPNG_COMPILE_ZLIB*/
 196
 197 /* /////////////////////////////////////////////////////////////////////////// */
 198
 199 typedef struct ucvector
 200 {
 201   unsigned char* data;
 202   size_t size; /*used size*/
 203   size_t allocsize; /*allocated size*/
 204 } ucvector;
 205
 206 static void ucvector_cleanup(void* p)
 207 {
 208   ((ucvector*)p)->size = ((ucvector*)p)->allocsize = 0;
 209   free(((ucvector*)p)->data);
 210   ((ucvector*)p)->data = NULL;
 211 }
 212
 213 static unsigned ucvector_resize(ucvector* p, size_t size) /*returns 1 if success, 0 if failure ==> nothing done*/
 214 {
 215   if(size * sizeof(unsigned) > p->allocsize)
 216   {
 217     size_t newsize = size * sizeof(unsigned) * 2;
 218     void* data = realloc(p->data, newsize);
 219     if(data)
 220     {
 221       p->allocsize = newsize;
 222       p->data = (unsigned char*)data;
 223       p->size = size;
 224     }
 225     else return 0; /*error: not enough memory*/
 226   }
 227   else p->size = size;
 228   return 1;
 229 }
 230
 231 #ifdef LODEPNG_COMPILE_DECODER
 232 #ifdef LODEPNG_COMPILE_PNG
 233 static unsigned ucvector_resizev(ucvector* p, size_t size, unsigned char value) /*resize and give all new elements the value*/
 234 {
 235   size_t oldsize = p->size, i;
 236   if(!ucvector_resize(p, size)) return 0;
 237   for(i = oldsize; i < size; i++) p->data[i] = value;
 238   return 1;
 239 }
 240 #endif /*LODEPNG_COMPILE_PNG*/
 241 #endif /*LODEPNG_COMPILE_DECODER*/
 242
 243 static void ucvector_init(ucvector* p)
 244 {
 245   p->data = NULL;
 246   p->size = p->allocsize = 0;
 247 }
 248
 249 #ifdef LODEPNG_COMPILE_ZLIB
 250 /*you can both convert from vector to buffer&size and vica versa*/
 251 static void ucvector_init_buffer(ucvector* p, unsigned char* buffer, size_t size)
 252 {
 253   p->data = buffer;
 254   p->allocsize = p->size = size;
 255 }
 256 #endif /*LODEPNG_COMPILE_ZLIB*/
 257
 258 static unsigned ucvector_push_back(ucvector* p, unsigned char c) /*returns 1 if success, 0 if failure ==> nothing done*/
 259 {
 260   if(!ucvector_resize(p, p->size + 1)) return 0;
 261   p->data[p->size - 1] = c;
 262   return 1;
 263 }
 264
 265 /* /////////////////////////////////////////////////////////////////////////// */
 266
 267 #ifdef LODEPNG_COMPILE_PNG
 268 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
 269 static unsigned string_resize(char** out, size_t size) /*returns 1 if success, 0 if failure ==> nothing done*/
 270 {
 271   char* data = (char*)realloc(*out, size + 1);
 272   if(data)
 273   {
 274     data[size] = 0; /*null termination char*/
 275     *out = data;
 276   }
 277   return data != 0;
 278 }
 279
 280 static void string_init(char** out) /*init a {char*, size_t} pair for use as string*/
 281 {
 282   *out = NULL;
 283   string_resize(out, 0);
 284 }
 285
 286 static void string_cleanup(char** out) /*free the above pair again*/
 287 {
 288   free(*out);
 289   *out = NULL;
 290 }
 291
 292 static void string_set(char** out, const char* in)
 293 {
 294   size_t insize = strlen(in), i = 0;
 295   if(string_resize(out, insize)) for(i = 0; i < insize; i++) (*out)[i] = in[i];
 296 }
 297 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
 298 #endif /*LODEPNG_COMPILE_PNG*/
 299
 300 #ifdef LODEPNG_COMPILE_ZLIB
 301
 302 /* ////////////////////////////////////////////////////////////////////////// */
 303 /* / Reading and writing single bits and bytes from/to stream for Deflate   / */
 304 /* ////////////////////////////////////////////////////////////////////////// */
 305
 306 #ifdef LODEPNG_COMPILE_ENCODER
 307 static void addBitToStream(size_t* bitpointer, ucvector* bitstream, unsigned char bit)
 308 {
 309   if((*bitpointer) % 8 == 0) ucvector_push_back(bitstream, 0); /*add a new byte at the end*/
 310   (bitstream->data[bitstream->size - 1]) |= (bit << ((*bitpointer) & 0x7)); /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/
 311   (*bitpointer)++;
 312 }
 313
 314 static void addBitsToStream(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
 315 {
 316   size_t i;
 317   for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> i) & 1));
 318 }
 319
 320 static void addBitsToStreamReversed(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
 321 {
 322   size_t i;
 323   for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> (nbits - 1 - i)) & 1));
 324 }
 325 #endif /*LODEPNG_COMPILE_ENCODER*/
 326
 327 #ifdef LODEPNG_COMPILE_DECODER
 328 static unsigned char readBitFromStream(size_t* bitpointer, const unsigned char* bitstream)
 329 {
 330   unsigned char result = (unsigned char)((bitstream[(*bitpointer) >> 3] >> ((*bitpointer) & 0x7)) & 1);
 331   (*bitpointer)++;
 332   return result;
 333 }
 334
 335 static unsigned readBitsFromStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
 336 {
 337   unsigned result = 0, i;
 338   for(i = 0; i < nbits; i++) result += ((unsigned)readBitFromStream(bitpointer, bitstream)) << i;
 339   return result;
 340 }
 341 #endif /*LODEPNG_COMPILE_DECODER*/
 342
 343 /* ////////////////////////////////////////////////////////////////////////// */
 344 /* / Deflate - Huffman                                                      / */
 345 /* ////////////////////////////////////////////////////////////////////////// */
 346
 347 #define FIRST_LENGTH_CODE_INDEX 257
 348 #define LAST_LENGTH_CODE_INDEX 285
 349 #define NUM_DEFLATE_CODE_SYMBOLS 288 /*256 literals, the end code, some length codes, and 2 unused codes*/
 350 #define NUM_DISTANCE_SYMBOLS 32 /*the distance codes have their own symbols, 30 used, 2 unused*/
 351 #define NUM_CODE_LENGTH_CODES 19 /*the code length codes. 0-15: code lengths, 16: copy previous 3-6 times, 17: 3-10 zeros, 18: 11-138 zeros*/
 352
 353 static const unsigned LENGTHBASE[29] /*the base lengths represented by codes 257-285*/
 354   = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
 355 static const unsigned LENGTHEXTRA[29] /*the extra bits used by codes 257-285 (added to base length)*/
 356   = {0, 0, 0, 0, 0, 0, 0,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,   4,   5,   5,   5,   5,   0};
 357 static const unsigned DISTANCEBASE[30] /*the base backwards distances (the bits of distance codes appear after length codes and use their own huffman tree)*/
 358   = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
 359 static const unsigned DISTANCEEXTRA[30] /*the extra bits of backwards distances (added to base)*/
 360   = {0, 0, 0, 0, 1, 1, 2,  2,  3,  3,  4,  4,  5,  5,   6,   6,   7,   7,   8,   8,    9,    9,   10,   10,   11,   11,   12,    12,    13,    13};
 361 static const unsigned CLCL[NUM_CODE_LENGTH_CODES] /*the order in which "code length alphabet code lengths" are stored, out of this the huffman tree of the dynamic huffman tree lengths is generated*/
 362   = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
 363
 364 /* /////////////////////////////////////////////////////////////////////////// */
 365
 366 #ifdef LODEPNG_COMPILE_ENCODER
 367 /*terminology used for the package-merge algorithm and the coin collector's problem*/
 368 typedef struct Coin /*a coin can be multiple coins (when they're merged)*/
 369 {
 370   uivector symbols;
 371   float weight; /*the sum of all weights in this coin*/
 372 } Coin;
 373
 374 static void Coin_init(Coin* c)
 375 {
 376   uivector_init(&c->symbols);
 377 }
 378
 379 static void Coin_cleanup(void* c) /*void* so that this dtor can be given as function pointer to the vector resize function*/
 380 {
 381   uivector_cleanup(&((Coin*)c)->symbols);
 382 }
 383
 384 static void Coin_copy(Coin* c1, const Coin* c2)
 385 {
 386   c1->weight = c2->weight;
 387   uivector_copy(&c1->symbols, &c2->symbols);
 388 }
 389
 390 static void addCoins(Coin* c1, const Coin* c2)
 391 {
 392   unsigned i;
 393   for(i = 0; i < c2->symbols.size; i++) uivector_push_back(&c1->symbols, c2->symbols.data[i]);
 394   c1->weight += c2->weight;
 395 }
 396
 397 static void Coin_sort(Coin* data, size_t amount) /*combsort*/
 398 {
 399   size_t gap = amount;
 400   unsigned char swapped = 0;
 401   while(gap > 1 || swapped)
 402   {
 403     size_t i;
 404     gap = (gap * 10) / 13; /*shrink factor 1.3*/
 405     if(gap == 9 || gap == 10) gap = 11; /*combsort11*/
 406     if(gap < 1) gap = 1;
 407     swapped = 0;
 408     for(i = 0; i < amount - gap; i++)
 409     {
 410       size_t j = i + gap;
 411       if(data[j].weight < data[i].weight)
 412       {
 413         float temp = data[j].weight; data[j].weight = data[i].weight; data[i].weight = temp;
 414         uivector_swap(&data[i].symbols, &data[j].symbols);
 415         swapped = 1;
 416       }
 417     }
 418   }
 419 }
 420 #endif /*LODEPNG_COMPILE_ENCODER*/
 421
 422 typedef struct HuffmanTree
 423 {
 424   uivector tree2d;
 425   uivector tree1d;
 426   uivector lengths; /*the lengths of the codes of the 1d-tree*/
 427   unsigned maxbitlen; /*maximum number of bits a single code can get*/
 428   unsigned numcodes; /*number of symbols in the alphabet = number of codes*/
 429 } HuffmanTree;
 430
 431 /*function used for debug purposes*/
 432 /*#include <iostream>
 433 static void HuffmanTree_draw(HuffmanTree* tree)
 434 {
 435   std::cout << "tree. length: " << tree->numcodes << " maxbitlen: " << tree->maxbitlen << std::endl;
 436   for(size_t i = 0; i < tree->tree1d.size; i++)
 437   {
 438     if(tree->lengths.data[i])
 439       std::cout << i << " " << tree->tree1d.data[i] << " " << tree->lengths.data[i] << std::endl;
 440   }
 441   std::cout << std::endl;
 442 }*/
 443
 444 static void HuffmanTree_init(HuffmanTree* tree)
 445 {
 446   uivector_init(&tree->tree2d);
 447   uivector_init(&tree->tree1d);
 448   uivector_init(&tree->lengths);
 449 }
 450
 451 static void HuffmanTree_cleanup(HuffmanTree* tree)
 452 {
 453   uivector_cleanup(&tree->tree2d);
 454   uivector_cleanup(&tree->tree1d);
 455   uivector_cleanup(&tree->lengths);
 456 }
 457
 458 /*the tree representation used by the decoder. return value is error*/
 459 static unsigned HuffmanTree_make2DTree(HuffmanTree* tree)
 460 {
 461   unsigned nodefilled = 0; /*up to which node it is filled*/
 462   unsigned treepos = 0; /*position in the tree (1 of the numcodes columns)*/
 463   unsigned n, i;
 464
 465   if(!uivector_resize(&tree->tree2d, tree->numcodes * 2)) return 9901; /*if failed return not enough memory error*/
 466   /*convert tree1d[] to tree2d[][]. In the 2D array, a value of 32767 means uninited, a value >= numcodes is an address to another bit, a value < numcodes is a code. The 2 rows are the 2 possible bit values (0 or 1), there are as many columns as codes - 1
 467   a good huffmann tree has N * 2 - 1 nodes, of which N - 1 are internal nodes. Here, the internal nodes are stored (what their 0 and 1 option point to). There is only memory for such good tree currently, if there are more nodes (due to too long length codes), error 55 will happen*/
 468   for(n = 0;  n < tree->numcodes * 2; n++) tree->tree2d.data[n] = 32767; /*32767 here means the tree2d isn't filled there yet*/
 469
 470   for(n = 0; n < tree->numcodes; n++) /*the codes*/
 471   for(i = 0; i < tree->lengths.data[n]; i++) /*the bits for this code*/
 472   {
 473     unsigned char bit = (unsigned char)((tree->tree1d.data[n] >> (tree->lengths.data[n] - i - 1)) & 1);
 474     if(treepos > tree->numcodes - 2) return 55; /*error 55: oversubscribed; see description in header*/
 475     if(tree->tree2d.data[2 * treepos + bit] == 32767) /*not yet filled in*/
 476     {
 477       if(i + 1 == tree->lengths.data[n]) /*last bit*/
 478       {
 479         tree->tree2d.data[2 * treepos + bit] = n; /*put the current code in it*/
 480         treepos = 0;
 481       }
 482       else /*put address of the next step in here, first that address has to be found of course (it's just nodefilled + 1)...*/
 483       {
 484         nodefilled++;
 485         tree->tree2d.data[2 * treepos + bit] = nodefilled + tree->numcodes; /*addresses encoded with numcodes added to it*/
 486         treepos = nodefilled;
 487       }
 488     }
 489     else treepos = tree->tree2d.data[2 * treepos + bit] - tree->numcodes;
 490   }
 491   for(n = 0;  n < tree->numcodes * 2; n++) if(tree->tree2d.data[n] == 32767) tree->tree2d.data[n] = 0; /*remove possible remaining 32767's*/
 492
 493   return 0;
 494 }
 495
 496 static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree) /*given that numcodes, lengths and maxbitlen are already filled in correctly. return value is error.*/
 497 {
 498   uivector blcount;
 499   uivector nextcode;
 500   unsigned bits, n, error = 0;
 501
 502   uivector_init(&blcount);
 503   uivector_init(&nextcode);
 504   if(!uivector_resize(&tree->tree1d, tree->numcodes)
 505   || !uivector_resizev(&blcount, tree->maxbitlen + 1, 0)
 506   || !uivector_resizev(&nextcode, tree->maxbitlen + 1, 0))
 507     error = 9902;
 508
 509   if(!error)
 510   {
 511     /*step 1: count number of instances of each code length*/
 512     for(bits = 0; bits < tree->numcodes; bits++) blcount.data[tree->lengths.data[bits]]++;
 513     /*step 2: generate the nextcode values*/
 514     for(bits = 1; bits <= tree->maxbitlen; bits++) nextcode.data[bits] = (nextcode.data[bits - 1] + blcount.data[bits - 1]) << 1;
 515     /*step 3: generate all the codes*/
 516     for(n = 0; n < tree->numcodes; n++) if(tree->lengths.data[n] != 0) tree->tree1d.data[n] = nextcode.data[tree->lengths.data[n]]++;
 517   }
 518
 519   uivector_cleanup(&blcount);
 520   uivector_cleanup(&nextcode);
 521
 522   if(!error) return HuffmanTree_make2DTree(tree);
 523   else return error;
 524 }
 525
 526 /*given the code lengths (as stored in the PNG file), generate the tree as defined by Deflate. maxbitlen is the maximum bits that a code in the tree can have. return value is error.*/
 527 static unsigned HuffmanTree_makeFromLengths(HuffmanTree* tree, const unsigned* bitlen, size_t numcodes, unsigned maxbitlen)
 528 {
 529   unsigned i;
 530   if(!uivector_resize(&tree->lengths, numcodes)) return 9903;
 531   for(i = 0; i < numcodes; i++) tree->lengths.data[i] = bitlen[i];
 532   tree->numcodes = (unsigned)numcodes; /*number of symbols*/
 533   tree->maxbitlen = maxbitlen;
 534   return HuffmanTree_makeFromLengths2(tree);
 535 }
 536
 537 #ifdef LODEPNG_COMPILE_ENCODER
 538 static unsigned HuffmanTree_fillInCoins(vector* coins, const unsigned* frequencies, unsigned numcodes, size_t sum)
 539 {
 540   unsigned i;
 541   for(i = 0; i < numcodes; i++)
 542   {
 543     Coin* coin;
 544     if(frequencies[i] == 0) continue; /*it's important to exclude symbols that aren't present*/
 545     if(!vector_resize(coins, coins->size + 1)) { vector_cleanup(coins); return 9904; }
 546     coin = (Coin*)(vector_get(coins, coins->size - 1));
 547     Coin_init(coin);
 548     coin->weight = frequencies[i] / (float)sum;
 549     uivector_push_back(&coin->symbols, i);
 550   }
 551   if(coins->size) Coin_sort((Coin*)coins->data, coins->size);
 552   return 0;
 553 }
 554
 555 static unsigned HuffmanTree_makeFromFrequencies(HuffmanTree* tree, const unsigned* frequencies, size_t numcodes, unsigned maxbitlen)
 556 {
 557   unsigned i, j;
 558   size_t sum = 0, numpresent = 0;
 559   unsigned error = 0;
 560
 561   vector prev_row; /*type Coin, the previous row of coins*/
 562   vector coins; /*type Coin, the coins of the currently calculated row*/
 563
 564   tree->maxbitlen = maxbitlen;
 565
 566   for(i = 0; i < numcodes; i++)
 567   {
 568     if(frequencies[i] > 0)
 569     {
 570       numpresent++;
 571       sum += frequencies[i];
 572     }
 573   }
 574
 575   if(numcodes == 0) return 80; /*error: a tree of 0 symbols is not supposed to be made*/
 576   tree->numcodes = (unsigned)numcodes; /*number of symbols*/
 577   uivector_resize(&tree->lengths, 0);
 578   if(!uivector_resizev(&tree->lengths, tree->numcodes, 0)) return 9905;
 579
 580   if(numpresent == 0) /*there are no symbols at all, in that case add one symbol of value 0 to the tree (see RFC 1951 section 3.2.7) */
 581   {
 582     tree->lengths.data[0] = 1;
 583     return HuffmanTree_makeFromLengths2(tree);
 584   }
 585   else if(numpresent == 1) /*the package merge algorithm gives wrong results if there's only one symbol (theoretically 0 bits would then suffice, but we need a proper symbol for zlib)*/
 586   {
 587     for(i = 0; i < numcodes; i++) if(frequencies[i]) tree->lengths.data[i] = 1;
 588     return HuffmanTree_makeFromLengths2(tree);
 589   }
 590
 591   vector_init(&coins, sizeof(Coin));
 592   vector_init(&prev_row, sizeof(Coin));
 593
 594   /*Package-Merge algorithm represented by coin collector's problem
 595   For every symbol, maxbitlen coins will be created*/
 596
 597   /*first row, lowest denominator*/
 598   error = HuffmanTree_fillInCoins(&coins, frequencies, tree->numcodes, sum);
 599   if(!error)
 600   {
 601     for(j = 1; j <= maxbitlen && !error; j++) /*each of the remaining rows*/
 602     {
 603       vector_swap(&coins, &prev_row); /*swap instead of copying*/
 604       if(!vector_resized(&coins, 0, Coin_cleanup)) { error = 9906; break; }
 605
 606       for(i = 0; i + 1 < prev_row.size; i += 2)
 607       {
 608         if(!vector_resize(&coins, coins.size + 1)) { error = 9907; break; }
 609         Coin_init((Coin*)vector_get(&coins, coins.size - 1));
 610         Coin_copy((Coin*)vector_get(&coins, coins.size - 1), (Coin*)vector_get(&prev_row, i));
 611         addCoins((Coin*)vector_get(&coins, coins.size - 1), (Coin*)vector_get(&prev_row, i + 1)); /*merge the coins into packages*/
 612       }
 613       if(j < maxbitlen)
 614       {
 615         error = HuffmanTree_fillInCoins(&coins, frequencies, tree->numcodes, sum);
 616       }
 617     }
 618   }
 619
 620   if(!error)
 621   {
 622     /*keep the coins with lowest weight, so that they add up to the amount of symbols - 1*/
 623     vector_resized(&coins, numpresent - 1, Coin_cleanup);
 624
 625     /*calculate the lenghts of each symbol, as the amount of times a coin of each symbol is used*/
 626     for(i = 0; i < coins.size; i++)
 627     {
 628       Coin* coin = (Coin*)vector_get(&coins, i);
 629       for(j = 0; j < coin->symbols.size; j++) tree->lengths.data[coin->symbols.data[j]]++;
 630     }
 631
 632     error = HuffmanTree_makeFromLengths2(tree);
 633   }
 634
 635   vector_cleanupd(&coins, Coin_cleanup);
 636   vector_cleanupd(&prev_row, Coin_cleanup);
 637
 638   return error;
 639 }
 640
 641 static unsigned HuffmanTree_getCode(const HuffmanTree* tree, unsigned index) { return tree->tree1d.data[index]; }
 642 static unsigned HuffmanTree_getLength(const HuffmanTree* tree, unsigned index) { return tree->lengths.data[index]; }
 643 #endif /*LODEPNG_COMPILE_ENCODER*/
 644
 645 /*get the tree of a deflated block with fixed tree, as specified in the deflate specification*/
 646 static unsigned generateFixedTree(HuffmanTree* tree)
 647 {
 648   unsigned i, error = 0;
 649   uivector bitlen;
 650   uivector_init(&bitlen);
 651   if(!uivector_resize(&bitlen, NUM_DEFLATE_CODE_SYMBOLS)) error = 9909;
 652
 653   if(!error)
 654   {
 655     /*288 possible codes: 0-255=literals, 256=endcode, 257-285=lengthcodes, 286-287=unused*/
 656     for(i =   0; i <= 143; i++) bitlen.data[i] = 8;
 657     for(i = 144; i <= 255; i++) bitlen.data[i] = 9;
 658     for(i = 256; i <= 279; i++) bitlen.data[i] = 7;
 659     for(i = 280; i <= 287; i++) bitlen.data[i] = 8;
 660
 661     error = HuffmanTree_makeFromLengths(tree, bitlen.data, NUM_DEFLATE_CODE_SYMBOLS, 15);
 662   }
 663
 664   uivector_cleanup(&bitlen);
 665   return error;
 666 }
 667
 668 static unsigned generateDistanceTree(HuffmanTree* tree)
 669 {
 670   unsigned i, error = 0;
 671   uivector bitlen;
 672   uivector_init(&bitlen);
 673   if(!uivector_resize(&bitlen, NUM_DISTANCE_SYMBOLS)) error = 9910;
 674
 675   /*there are 32 distance codes, but 30-31 are unused*/
 676   if(!error)
 677   {
 678     for(i = 0; i < NUM_DISTANCE_SYMBOLS; i++) bitlen.data[i] = 5;
 679     error = HuffmanTree_makeFromLengths(tree, bitlen.data, NUM_DISTANCE_SYMBOLS, 15);
 680   }
 681   uivector_cleanup(&bitlen);
 682   return error;
 683 }
 684
 685 #ifdef LODEPNG_COMPILE_DECODER
 686 /*Decodes a symbol from the tree
 687 if decoded is true, then result contains the symbol, otherwise it contains something unspecified (because the symbol isn't fully decoded yet)
 688 bit is the bit that was just read from the stream
 689 you have to decode a full symbol (let the decode function return true) before you can try to decode another one, otherwise the state isn't reset
 690 return value is error.*/
 691 static unsigned HuffmanTree_decode(const HuffmanTree* tree, unsigned* decoded, unsigned* result, unsigned* treepos, unsigned char bit)
 692 {
 693   if((*treepos) >= tree->numcodes) return 11; /*error: it appeared outside the codetree*/
 694
 695   (*result) = tree->tree2d.data[2 * (*treepos) + bit];
 696   (*decoded) = ((*result) < tree->numcodes);
 697
 698   if(*decoded) (*treepos) = 0;
 699   else (*treepos) = (*result) - tree->numcodes;
 700
 701   return 0;
 702 }
 703
 704 static unsigned huffmanDecodeSymbol(unsigned int* error, const unsigned char* in, size_t* bp, const HuffmanTree* codetree, size_t inlength)
 705 {
 706   unsigned treepos = 0, decoded, ct;
 707   for(;;)
 708   {
 709     unsigned char bit;
 710     if(((*bp) & 0x07) == 0 && ((*bp) >> 3) > inlength) { *error = 10; return 0; } /*error: end of input memory reached without endcode*/
 711     bit = readBitFromStream(bp, in);
 712     *error = HuffmanTree_decode(codetree, &decoded, &ct, &treepos, bit);
 713     if(*error) return 0; /*stop, an error happened*/
 714     if(decoded) return ct;
 715   }
 716 }
 717 #endif /*LODEPNG_COMPILE_DECODER*/
 718
 719 #ifdef LODEPNG_COMPILE_DECODER
 720
 721 /* ////////////////////////////////////////////////////////////////////////// */
 722 /* / Inflator                                                               / */
 723 /* ////////////////////////////////////////////////////////////////////////// */
 724
 725 /*get the tree of a deflated block with fixed tree, as specified in the deflate specification*/
 726 static void getTreeInflateFixed(HuffmanTree* tree, HuffmanTree* treeD)
 727 {
 728   /*error checking not done, this is fixed stuff, it works, it doesn't depend on the image*/
 729   generateFixedTree(tree);
 730   generateDistanceTree(treeD);
 731 }
 732
 733 /*get the tree of a deflated block with dynamic tree, the tree itself is also Huffman compressed with a known tree*/
 734 static unsigned getTreeInflateDynamic(HuffmanTree* codetree, HuffmanTree* codetreeD, HuffmanTree* codelengthcodetree,
 735                                       const unsigned char* in, size_t* bp, size_t inlength)
 736 {
 737   /*make sure that length values that aren't filled in will be 0, or a wrong tree will be generated*/
 738   /*C-code note: use no "return" between ctor and dtor of an uivector!*/
 739   unsigned error = 0;
 740   unsigned n, HLIT, HDIST, HCLEN, i;
 741   uivector bitlen;
 742   uivector bitlenD;
 743   uivector codelengthcode;
 744
 745   if((*bp) >> 3 >= inlength - 2) { return 49; } /*the bit pointer is or will go past the memory*/
 746
 747   HLIT =  readBitsFromStream(bp, in, 5) + 257; /*number of literal/length codes + 257. Unlike the spec, the value 257 is added to it here already*/
 748   HDIST = readBitsFromStream(bp, in, 5) + 1; /*number of distance codes. Unlike the spec, the value 1 is added to it here already*/
 749   HCLEN = readBitsFromStream(bp, in, 4) + 4; /*number of code length codes. Unlike the spec, the value 4 is added to it here already*/
 750
 751   /*read the code length codes out of 3 * (amount of code length codes) bits*/
 752   uivector_init(&codelengthcode);
 753   if(!uivector_resize(&codelengthcode, NUM_CODE_LENGTH_CODES)) error = 9911;
 754
 755   if(!error)
 756   {
 757     for(i = 0; i < NUM_CODE_LENGTH_CODES; i++)
 758     {
 759       if(i < HCLEN) codelengthcode.data[CLCL[i]] = readBitsFromStream(bp, in, 3);
 760       else codelengthcode.data[CLCL[i]] = 0; /*if not, it must stay 0*/
 761     }
 762
 763     error = HuffmanTree_makeFromLengths(codelengthcodetree, codelengthcode.data, codelengthcode.size, 7);
 764   }
 765
 766   uivector_cleanup(&codelengthcode);
 767   if(error) return error;
 768
 769   /*now we can use this tree to read the lengths for the tree that this function will return*/
 770   uivector_init(&bitlen);
 771   uivector_resizev(&bitlen, NUM_DEFLATE_CODE_SYMBOLS, 0);
 772   uivector_init(&bitlenD);
 773   uivector_resizev(&bitlenD, NUM_DISTANCE_SYMBOLS, 0);
 774   i = 0;
 775   if(!bitlen.data || !bitlenD.data) error = 9912;
 776   else while(i < HLIT + HDIST) /*i is the current symbol we're reading in the part that contains the code lengths of lit/len codes and dist codes*/
 777   {
 778     unsigned code = huffmanDecodeSymbol(&error, in, bp, codelengthcodetree, inlength);
 779     if(error) break;
 780
 781     if(code <= 15) /*a length code*/
 782     {
 783       if(i < HLIT) bitlen.data[i] = code;
 784       else bitlenD.data[i - HLIT] = code;
 785       i++;
 786     }
 787     else if(code == 16) /*repeat previous*/
 788     {
 789       unsigned replength = 3; /*read in the 2 bits that indicate repeat length (3-6)*/
 790       unsigned value; /*set value to the previous code*/
 791
 792       if((*bp) >> 3 >= inlength) { error = 50; break; } /*error, bit pointer jumps past memory*/
 793
 794       replength += readBitsFromStream(bp, in, 2);
 795
 796       if((i - 1) < HLIT) value = bitlen.data[i - 1];
 797       else value = bitlenD.data[i - HLIT - 1];
 798       /*repeat this value in the next lengths*/
 799       for(n = 0; n < replength; n++)
 800       {
 801         if(i >= HLIT + HDIST) { error = 13; break; } /*error: i is larger than the amount of codes*/
 802         if(i < HLIT) bitlen.data[i] = value;
 803         else bitlenD.data[i - HLIT] = value;
 804         i++;
 805       }
 806     }
 807     else if(code == 17) /*repeat "0" 3-10 times*/
 808     {
 809       unsigned replength = 3; /*read in the bits that indicate repeat length*/
 810       if((*bp) >> 3 >= inlength) { error = 50; break; } /*error, bit pointer jumps past memory*/
 811
 812       replength += readBitsFromStream(bp, in, 3);
 813
 814       /*repeat this value in the next lengths*/
 815       for(n = 0; n < replength; n++)
 816       {
 817         if(i >= HLIT + HDIST) { error = 14; break; } /*error: i is larger than the amount of codes*/
 818         if(i < HLIT) bitlen.data[i] = 0;
 819         else bitlenD.data[i - HLIT] = 0;
 820         i++;
 821       }
 822     }
 823     else if(code == 18) /*repeat "0" 11-138 times*/
 824     {
 825       unsigned replength = 11; /*read in the bits that indicate repeat length*/
 826       if((*bp) >> 3 >= inlength) { error = 50; break; } /*error, bit pointer jumps past memory*/
 827       replength += readBitsFromStream(bp, in, 7);
 828
 829       /*repeat this value in the next lengths*/
 830       for(n = 0; n < replength; n++)
 831       {
 832         if(i >= HLIT + HDIST) { error = 15; break; } /*error: i is larger than the amount of codes*/
 833         if(i < HLIT) bitlen.data[i] = 0;
 834         else bitlenD.data[i - HLIT] = 0;
 835         i++;
 836       }
 837     }
 838     else { error = 16; break; } /*error: somehow an unexisting code appeared. This can never happen.*/
 839   }
 840
 841   if(!error && bitlen.data[256] == 0) { error = 64; } /*the length of the end code 256 must be larger than 0*/
 842
 843   /*now we've finally got HLIT and HDIST, so generate the code trees, and the function is done*/
 844   if(!error) error = HuffmanTree_makeFromLengths(codetree, &bitlen.data[0], bitlen.size, 15);
 845   if(!error) error = HuffmanTree_makeFromLengths(codetreeD, &bitlenD.data[0], bitlenD.size, 15);
 846
 847   uivector_cleanup(&bitlen);
 848   uivector_cleanup(&bitlenD);
 849
 850   return error;
 851 }
 852
 853 /*inflate a block with dynamic of fixed Huffman tree*/
 854 static unsigned inflateHuffmanBlock(ucvector* out, const unsigned char* in, size_t* bp, size_t* pos, size_t inlength, unsigned btype)
 855 {
 856   unsigned endreached = 0, error = 0;
 857   HuffmanTree codetree; /*287, the code tree for Huffman codes*/
 858   HuffmanTree codetreeD; /*31, the code tree for distance codes*/
 859
 860   HuffmanTree_init(&codetree);
 861   HuffmanTree_init(&codetreeD);
 862
 863   if(btype == 1) getTreeInflateFixed(&codetree, &codetreeD);
 864   else if(btype == 2)
 865   {
 866     HuffmanTree codelengthcodetree; /*18, the code tree for code length codes*/
 867     HuffmanTree_init(&codelengthcodetree);
 868     error = getTreeInflateDynamic(&codetree, &codetreeD, &codelengthcodetree, in, bp, inlength);
 869     HuffmanTree_cleanup(&codelengthcodetree);
 870   }
 871
 872   while(!endreached && !error)
 873   {
 874     unsigned code = huffmanDecodeSymbol(&error, in, bp, &codetree, inlength);
 875     if(error) break; /*some error happened in the above function*/
 876     if(code == 256) endreached = 1; /*end code*/
 877     else if(code <= 255) /*literal symbol*/
 878     {
 879       if((*pos) >= out->size) ucvector_resize(out, ((*pos) + 1) * 2); /*reserve more room at once*/
 880       if((*pos) >= out->size) { error = 9913; break; } /*not enough memory*/
 881       out->data[(*pos)] = (unsigned char)(code);
 882       (*pos)++;
 883     }
 884     else if(code >= FIRST_LENGTH_CODE_INDEX && code <= LAST_LENGTH_CODE_INDEX) /*length code*/
 885     {
 886       /*part 1: get length base*/
 887       size_t length = LENGTHBASE[code - FIRST_LENGTH_CODE_INDEX];
 888       unsigned codeD, distance, numextrabitsD;
 889       size_t start, forward, backward, numextrabits;
 890
 891       /*part 2: get extra bits and add the value of that to length*/
 892       numextrabits = LENGTHEXTRA[code - FIRST_LENGTH_CODE_INDEX];
 893       if(((*bp) >> 3) >= inlength) { error = 51; break; } /*error, bit pointer will jump past memory*/
 894       length += readBitsFromStream(bp, in, numextrabits);
 895
 896       /*part 3: get distance code*/
 897       codeD = huffmanDecodeSymbol(&error, in, bp, &codetreeD, inlength);
 898       if(error) break;
 899       if(codeD > 29) { error = 18; break; } /*error: invalid distance code (30-31 are never used)*/
 900       distance = DISTANCEBASE[codeD];
 901
 902       /*part 4: get extra bits from distance*/
 903       numextrabitsD = DISTANCEEXTRA[codeD];
 904       if(((*bp) >> 3) >= inlength) { error = 51; break; } /*error, bit pointer will jump past memory*/
 905       distance += readBitsFromStream(bp, in, numextrabitsD);
 906
 907       /*part 5: fill in all the out[n] values based on the length and dist*/
 908       start = (*pos);
 909       backward = start - distance;
 910       if((*pos) + length >= out->size) ucvector_resize(out, ((*pos) + length) * 2); /*reserve more room at once*/
 911       if((*pos) + length >= out->size) { error = 9914; break; } /*not enough memory*/
 912
 913       for(forward = 0; forward < length; forward++)
 914       {
 915         out->data[(*pos)] = out->data[backward];
 916         (*pos)++;
 917         backward++;
 918         if(backward >= start) backward = start - distance;
 919       }
 920     }
 921   }
 922
 923   HuffmanTree_cleanup(&codetree);
 924   HuffmanTree_cleanup(&codetreeD);
 925
 926   return error;
 927 }
 928
 929 static unsigned inflateNoCompression(ucvector* out, const unsigned char* in, size_t* bp, size_t* pos, size_t inlength)
 930 {
 931   /*go to first boundary of byte*/
 932   size_t p;
 933   unsigned LEN, NLEN, n, error = 0;
 934   while(((*bp) & 0x7) != 0) (*bp)++;
 935   p = (*bp) / 8; /*byte position*/
 936
 937   /*read LEN (2 bytes) and NLEN (2 bytes)*/
 938   if(p >= inlength - 4) return 52; /*error, bit pointer will jump past memory*/
 939   LEN = in[p] + 256 * in[p + 1]; p += 2;
 940   NLEN = in[p] + 256 * in[p + 1]; p += 2;
 941
 942   /*check if 16-bit NLEN is really the one's complement of LEN*/
 943   if(LEN + NLEN != 65535) return 21; /*error: NLEN is not one's complement of LEN*/
 944
 945   if((*pos) + LEN >= out->size) { if(!ucvector_resize(out, (*pos) + LEN)) return 9915; }
 946
 947   /*read the literal data: LEN bytes are now stored in the out buffer*/
 948   if(p + LEN > inlength) return 23; /*error: reading outside of in buffer*/
 949   for(n = 0; n < LEN; n++) out->data[(*pos)++] = in[p++];
 950
 951   (*bp) = p * 8;
 952
 953   return error;
 954 }
 955
 956 /*inflate the deflated data (cfr. deflate spec); return value is the error*/
 957 unsigned LodeFlate_inflate(ucvector* out, const unsigned char* in, size_t insize, size_t inpos)
 958 {
 959   size_t bp = 0; /*bit pointer in the "in" data, current byte is bp >> 3, current bit is bp & 0x7 (from lsb to msb of the byte)*/
 960   unsigned BFINAL = 0;
 961   size_t pos = 0; /*byte position in the out buffer*/
 962
 963   unsigned error = 0;
 964
 965   while(!BFINAL)
 966   {
 967     unsigned BTYPE;
 968     if((bp >> 3) >= insize) return 52; /*error, bit pointer will jump past memory*/
 969     BFINAL = readBitFromStream(&bp, &in[inpos]);
 970     BTYPE = 1 * readBitFromStream(&bp, &in[inpos]); BTYPE += 2 * readBitFromStream(&bp, &in[inpos]);
 971
 972     if(BTYPE == 3) return 20; /*error: invalid BTYPE*/
 973     else if(BTYPE == 0) error = inflateNoCompression(out, &in[inpos], &bp, &pos, insize); /*no compression*/
 974     else error = inflateHuffmanBlock(out, &in[inpos], &bp, &pos, insize, BTYPE); /*compression, BTYPE 01 or 10*/
 975     if(error) return error;
 976   }
 977
 978   if(!ucvector_resize(out, pos)) error = 9916; /*Only now we know the true size of out, resize it to that*/
 979
 980   return error;
 981 }
 982
 983 #endif /*LODEPNG_COMPILE_DECODER*/
 984
 985 #ifdef LODEPNG_COMPILE_ENCODER
 986
 987 /* ////////////////////////////////////////////////////////////////////////// */
 988 /* / Deflator                                                               / */
 989 /* ////////////////////////////////////////////////////////////////////////// */
 990
 991 static const size_t MAX_SUPPORTED_DEFLATE_LENGTH = 258;
 992
 993 /*bitlen is the size in bits of the code*/
 994 static void addHuffmanSymbol(size_t* bp, ucvector* compressed, unsigned code, unsigned bitlen)
 995 {
 996   addBitsToStreamReversed(bp, compressed, code, bitlen);
 997 }
 998
 999 /*search the index in the array, that has the largest value smaller than or equal to the given value, given array must be sorted (if no value is smaller, it returns the size of the given array)*/
1000 static size_t searchCodeIndex(const unsigned* array, size_t array_size, size_t value)
1001 {
1002   /*linear search implementation*/
1003   /*for(size_t i = 1; i < array_size; i++) if(array[i] > value) return i - 1;
1004   return array_size - 1;*/
1005
1006   /*binary search implementation (not that much faster) (precondition: array_size > 0)*/
1007   size_t left  = 1;
1008   size_t right = array_size - 1;
1009   while(left <= right)
1010   {
1011     size_t mid = (left + right) / 2;
1012     if(array[mid] <= value) left = mid + 1; /*the value to find is more to the right*/
1013     else if(array[mid - 1] > value) right = mid - 1; /*the value to find is more to the left*/
1014     else return mid - 1;
1015   }
1016   return array_size - 1;
1017 }
1018
1019 static void addLengthDistance(uivector* values, size_t length, size_t distance)
1020 {
1021   /*values in encoded vector are those used by deflate:
1022   0-255: literal bytes
1023   256: end
1024   257-285: length/distance pair (length code, followed by extra length bits, distance code, extra distance bits)
1025   286-287: invalid*/
1026
1027   unsigned length_code = (unsigned)searchCodeIndex(LENGTHBASE, 29, length);
1028   unsigned extra_length = (unsigned)(length - LENGTHBASE[length_code]);
1029   unsigned dist_code = (unsigned)searchCodeIndex(DISTANCEBASE, 30, distance);
1030   unsigned extra_distance = (unsigned)(distance - DISTANCEBASE[dist_code]);
1031
1032   uivector_push_back(values, length_code + FIRST_LENGTH_CODE_INDEX);
1033   uivector_push_back(values, extra_length);
1034   uivector_push_back(values, dist_code);
1035   uivector_push_back(values, extra_distance);
1036 }
1037
1038 #if USE_BRUTE_FORCE_ENCODING
1039 #define encodeLZ77 encodeLZ77_brute
1040 /*the "brute force" version of the encodeLZ7 algorithm, not used anymore, kept here for reference*/
1041 static unsigned encodeLZ77_brute(uivector* out, const unsigned char* in, size_t size, unsigned windowSize)
1042 {
1043   size_t pos;
1044   /*using pointer instead of vector for input makes it faster when NOT using optimization when compiling; no influence if optimization is used*/
1045   for(pos = 0; pos < size; pos++)
1046   {
1047     /*Phase 1: doxygen images often have long runs of the same color, try to find them*/
1048     const int minLength = 4; // Minimum length for a run to make sense
1049
1050     if(pos < size - minLength * 4)
1051     {
1052       size_t p, fp;
1053       size_t current_length;
1054
1055       /*RGBA pixel run?*/
1056       p  = pos;
1057       fp = pos + 4;
1058       current_length = 0;
1059
1060       while(fp < size && in[p] == in[fp] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH)
1061       {
1062         ++p;
1063         ++fp;
1064         ++current_length;
1065       }
1066
1067       if (current_length > (minLength - 1 ) * 4) /*worth using?*/
1068       {
1069         uivector_push_back(out, in[pos    ]);
1070         uivector_push_back(out, in[pos + 1]);
1071         uivector_push_back(out, in[pos + 2]);
1072         uivector_push_back(out, in[pos + 3]);
1073         addLengthDistance(out, current_length, 4);
1074
1075         pos += current_length + 4 - 1; /*-1 for loop's pos++*/
1076         continue;
1077       }
1078
1079       /*RGB pixel run?*/
1080       p  = pos;
1081       fp = pos + 3;
1082       current_length = 0;
1083
1084       while(fp < size && in[p] == in[fp] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH)
1085       {
1086         ++p;
1087         ++fp;
1088         ++current_length;
1089       }
1090
1091       if (current_length > (minLength - 1 ) * 3) /*worth using?*/
1092       {
1093         uivector_push_back(out, in[pos    ]);
1094         uivector_push_back(out, in[pos + 1]);
1095         uivector_push_back(out, in[pos + 2]);
1096         addLengthDistance(out, current_length, 3);
1097
1098         pos += current_length + 3 - 1; /*-1 for loop's pos++*/
1099         continue;
1100       }
1101     }
1102
1103     size_t length = 0, offset = 0; /*the length and offset found for the current position*/
1104     size_t max_offset = pos < windowSize ? pos : windowSize; /*how far back to test*/
1105     size_t current_offset;
1106
1107     /**search for the longest string**/
1108     for(current_offset = 1; current_offset < max_offset; current_offset++) /*search backwards through all possible distances (=offsets)*/
1109     {
1110       size_t backpos = pos - current_offset;
1111       if(in[backpos] == in[pos])
1112       {
1113         /*test the next characters*/
1114         size_t current_length = 1;
1115         size_t backtest = backpos + 1;
1116         size_t foretest = pos + 1;
1117         while(foretest < size && in[backtest] == in[foretest] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH) /*maximum supporte length by deflate is max length*/
1118         {
1119           if(backpos >= pos) backpos -= current_offset; /*continue as if we work on the decoded bytes after pos by jumping back before pos*/
1120           current_length++;
1121           backtest++;
1122           foretest++;
1123         }
1124         if(current_length > length)
1125         {
1126           length = current_length; /*the longest length*/
1127           offset = current_offset; /*the offset that is related to this longest length*/
1128           if(current_length == MAX_SUPPORTED_DEFLATE_LENGTH) break; /*you can jump out of this for loop once a length of max length is found (gives significant speed gain)*/
1129         }
1130       }
1131     }
1132
1133     /**encode it as length/distance pair or literal value**/
1134     if(length < 3) /*only lengths of 3 or higher are supported as length/distance pair*/
1135     {
1136       uivector_push_back(out, in[pos]);
1137     }
1138     else
1139     {
1140       addLengthDistance(out, length, offset);
1141       pos += (length - 1);
1142     }
1143   } /*end of the loop through each character of input*/
1144
1145   return 0;
1146 }
1147 #endif
1148
1149 static const unsigned HASH_NUM_VALUES = 65536;
1150 static const unsigned HASH_NUM_CHARACTERS = 6;
1151 static const unsigned HASH_SHIFT = 2;
1152 /*
1153 Good and fast values: HASH_NUM_VALUES=65536, HASH_NUM_CHARACTERS=6, HASH_SHIFT=2
1154 making HASH_NUM_CHARACTERS larger (like 8), makes the file size larger but is a bit faster
1155 making HASH_NUM_CHARACTERS smaller (like 3), makes the file size smaller but is slower
1156 */
1157
1158 #if !defined(USE_BRUTE_FORCE_ENCODING)
1159 static unsigned getHash(const unsigned char* data, size_t size, size_t pos)
1160 {
1161   unsigned result = 0;
1162   size_t amount, i;
1163   if(pos >= size) return 0;
1164   amount = HASH_NUM_CHARACTERS; if(pos + amount >= size) amount = size - pos;
1165   for(i = 0; i < amount; i++) result ^= (data[pos + i] << (i * HASH_SHIFT));
1166   return result % HASH_NUM_VALUES;
1167 }
1168
1169 /*LZ77-encode the data using a hash table technique to let it encode faster. Return value is error code*/
1170 static unsigned encodeLZ77(uivector* out, const unsigned char* in, size_t size, unsigned windowSize)
1171 {
1172   /**generate hash table**/
1173   vector table; /*HASH_NUM_VALUES uivectors; this represents what would be an std::vector<std::vector<unsigned> > in C++*/
1174   uivector tablepos1, tablepos2;
1175   unsigned pos, i, error = 0;
1176
1177   vector_init(&table, sizeof(uivector));
1178   if(!vector_resize(&table, HASH_NUM_VALUES)) return 9917;
1179   for(i = 0; i < HASH_NUM_VALUES; i++)
1180   {
1181     uivector* v = (uivector*)vector_get(&table, i);
1182     uivector_init(v);
1183   }
1184
1185   /*remember start and end positions in the tables to searching in*/
1186   uivector_init(&tablepos1);
1187   uivector_init(&tablepos2);
1188   if(!uivector_resizev(&tablepos1, HASH_NUM_VALUES, 0)) error = 9918;
1189   if(!uivector_resizev(&tablepos2, HASH_NUM_VALUES, 0)) error = 9919;
1190
1191   if(!error)
1192   {
1193     for(pos = 0; pos < size; pos++)
1194     {
1195       unsigned length = 0, offset = 0; /*the length and offset found for the current position*/
1196       unsigned max_offset = pos < windowSize ? pos : windowSize; /*how far back to test*/
1197       unsigned tablepos;
1198
1199       /*/search for the longest string*/
1200       /*first find out where in the table to start (the first value that is in the range from "pos - max_offset" to "pos")*/
1201       unsigned hash = getHash(in, size, pos);
1202       if(!uivector_push_back((uivector*)vector_get(&table, hash), pos))  { error = 9920; break; }
1203
1204       while(((uivector*)vector_get(&table, hash))->data[tablepos1.data[hash]] < pos - max_offset) tablepos1.data[hash]++; /*it now points to the first value in the table for which the index is larger than or equal to pos - max_offset*/
1205       while(((uivector*)vector_get(&table, hash))->data[tablepos2.data[hash]] < pos) tablepos2.data[hash]++; /*it now points to the first value in the table for which the index is larger than or equal to pos*/
1206
1207       for(tablepos = tablepos2.data[hash] - 1; tablepos >= tablepos1.data[hash] && tablepos < tablepos2.data[hash]; tablepos--)
1208       {
1209         unsigned backpos = ((uivector*)vector_get(&table, hash))->data[tablepos];
1210         unsigned current_offset = pos - backpos;
1211
1212         /*test the next characters*/
1213         unsigned current_length = 0;
1214         unsigned backtest = backpos;
1215         unsigned foretest = pos;
1216         while(foretest < size && in[backtest] == in[foretest] && current_length < MAX_SUPPORTED_DEFLATE_LENGTH) /*maximum supporte length by deflate is max length*/
1217         {
1218           if(backpos >= pos) backpos -= current_offset; /*continue as if we work on the decoded bytes after pos by jumping back before pos*/
1219           current_length++;
1220           backtest++;
1221           foretest++;
1222         }
1223         if(current_length > length)
1224         {
1225           length = current_length; /*the longest length*/
1226           offset = current_offset; /*the offset that is related to this longest length*/
1227           if(current_length == MAX_SUPPORTED_DEFLATE_LENGTH) break; /*you can jump out of this for loop once a length of max length is found (gives significant speed gain)*/
1228         }
1229       }
1230
1231       /**encode it as length/distance pair or literal value**/
1232       if(length < 3) /*only lengths of 3 or higher are supported as length/distance pair*/
1233       {
1234         if(!uivector_push_back(out, in[pos])) { error = 9921; break; }
1235       }
1236       else
1237       {
1238         unsigned j;
1239         addLengthDistance(out, length, offset);
1240         for(j = 0; j < length - 1; j++)
1241         {
1242           pos++;
1243           if(!uivector_push_back((uivector*)vector_get(&table, getHash(in, size, pos)), pos)) { error = 9922; break; }
1244         }
1245       }
1246     } /*end of the loop through each character of input*/
1247   } /*end of "if(!error)"*/
1248
1249   /*cleanup*/
1250   for(i = 0; i < table.size; i++)
1251   {
1252     uivector* v = (uivector*)vector_get(&table, i);
1253     uivector_cleanup(v);
1254   }
1255   vector_cleanup(&table);
1256   uivector_cleanup(&tablepos1);
1257   uivector_cleanup(&tablepos2);
1258   return error;
1259 }
1260 #endif
1261
1262 /* /////////////////////////////////////////////////////////////////////////// */
1263
1264 static unsigned deflateNoCompression(ucvector* out, const unsigned char* data, size_t datasize)
1265 {
1266   /*non compressed deflate block data: 1 bit BFINAL,2 bits BTYPE,(5 bits): it jumps to start of next byte, 2 bytes LEN, 2 bytes NLEN, LEN bytes literal DATA*/
1267
1268   size_t i, j, numdeflateblocks = datasize / 65536 + 1;
1269   unsigned datapos = 0;
1270   for(i = 0; i < numdeflateblocks; i++)
1271   {
1272     unsigned BFINAL, BTYPE, LEN, NLEN;
1273     unsigned char firstbyte;
1274
1275     BFINAL = (i == numdeflateblocks - 1);
1276     BTYPE = 0;
1277
1278     firstbyte = (unsigned char)(BFINAL + ((BTYPE & 1) << 1) + ((BTYPE & 2) << 1));
1279     ucvector_push_back(out, firstbyte);
1280
1281     LEN = 65535;
1282     if(datasize - datapos < 65535) LEN = (unsigned)datasize - datapos;
1283     NLEN = 65535 - LEN;
1284
1285     ucvector_push_back(out, (unsigned char)(LEN % 256));
1286     ucvector_push_back(out, (unsigned char)(LEN / 256));
1287     ucvector_push_back(out, (unsigned char)(NLEN % 256));
1288     ucvector_push_back(out, (unsigned char)(NLEN / 256));
1289
1290     /*Decompressed data*/
1291     for(j = 0; j < 65535 && datapos < datasize; j++)
1292     {
1293       ucvector_push_back(out, data[datapos++]);
1294     }
1295   }
1296
1297   return 0;
1298 }
1299
1300 /*write the encoded data, using lit/len as well as distance codes*/
1301 static void writeLZ77data(size_t* bp, ucvector* out, const uivector* lz77_encoded, const HuffmanTree* codes, const HuffmanTree* codesD)
1302 {
1303   size_t i = 0;
1304   for(i = 0; i < lz77_encoded->size; i++)
1305   {
1306     unsigned val = lz77_encoded->data[i];
1307     addHuffmanSymbol(bp, out, HuffmanTree_getCode(codes, val), HuffmanTree_getLength(codes, val));
1308     if(val > 256) /*for a length code, 3 more things have to be added*/
1309     {
1310       unsigned length_index = val - FIRST_LENGTH_CODE_INDEX;
1311       unsigned n_length_extra_bits = LENGTHEXTRA[length_index];
1312       unsigned length_extra_bits = lz77_encoded->data[++i];
1313
1314       unsigned distance_code = lz77_encoded->data[++i];
1315
1316       unsigned distance_index = distance_code;
1317       unsigned n_distance_extra_bits = DISTANCEEXTRA[distance_index];
1318       unsigned distance_extra_bits = lz77_encoded->data[++i];
1319
1320       addBitsToStream(bp, out, length_extra_bits, n_length_extra_bits);
1321       addHuffmanSymbol(bp, out, HuffmanTree_getCode(codesD, distance_code), HuffmanTree_getLength(codesD, distance_code));
1322       addBitsToStream(bp, out, distance_extra_bits, n_distance_extra_bits);
1323     }
1324   }
1325 }
1326
1327 static unsigned deflateDynamic(ucvector* out, const unsigned char* data, size_t datasize, const LodeZlib_DeflateSettings* settings)
1328 {
1329   /*
1330   after the BFINAL and BTYPE, the dynamic block consists out of the following:
1331   - 5 bits HLIT, 5 bits HDIST, 4 bits HCLEN
1332   - (HCLEN+4)*3 bits code lengths of code length alphabet
1333   - HLIT + 257 code lenghts of lit/length alphabet (encoded using the code length alphabet, + possible repetition codes 16, 17, 18)
1334   - HDIST + 1 code lengths of distance alphabet (encoded using the code length alphabet, + possible repetition codes 16, 17, 18)
1335   - compressed data
1336   - 256 (end code)
1337   */
1338
1339   unsigned error = 0;
1340
1341   uivector lz77_encoded;
1342   HuffmanTree codes; /*tree for literal values and length codes*/
1343   HuffmanTree codesD; /*tree for distance codes*/
1344   HuffmanTree codelengthcodes;
1345   uivector frequencies;
1346   uivector frequenciesD;
1347   uivector amounts; /*the amounts in the "normal" order*/
1348   uivector lldl;
1349   uivector lldll; /*lit/len & dist code lenghts*/
1350   uivector clcls;
1351
1352   unsigned BFINAL = 1; /*make only one block... the first and final one*/
1353   size_t numcodes, numcodesD, i, bp = 0; /*the bit pointer*/
1354   unsigned HLIT, HDIST, HCLEN;
1355
1356   uivector_init(&lz77_encoded);
1357   HuffmanTree_init(&codes);
1358   HuffmanTree_init(&codesD);
1359   HuffmanTree_init(&codelengthcodes);
1360   uivector_init(&frequencies);
1361   uivector_init(&frequenciesD);
1362   uivector_init(&amounts);
1363   uivector_init(&lldl);
1364   uivector_init(&lldll);
1365   uivector_init(&clcls);
1366
1367   while(!error) /*the goto-avoiding while construct: break out to go to the cleanup phase, a break at the end makes sure the while is never repeated*/
1368   {
1369     if(settings->useLZ77)
1370     {
1371       error = encodeLZ77(&lz77_encoded, data, datasize, settings->windowSize); /*LZ77 encoded*/
1372       if(error) break;
1373     }
1374     else
1375     {
1376       if(!uivector_resize(&lz77_encoded, datasize)) { error = 9923; break; }
1377       for(i = 0; i < datasize; i++) lz77_encoded.data[i] = data[i]; /*no LZ77, but still will be Huffman compressed*/
1378     }
1379
1380     if(!uivector_resizev(&frequencies, 286, 0)) { error = 9924; break; }
1381     if(!uivector_resizev(&frequenciesD, 30, 0)) { error = 9925; break; }
1382     for(i = 0; i < lz77_encoded.size; i++)
1383     {
1384       unsigned symbol = lz77_encoded.data[i];
1385       frequencies.data[symbol]++;
1386       if(symbol > 256)
1387       {
1388         unsigned dist = lz77_encoded.data[i + 2];
1389         frequenciesD.data[dist]++;
1390         i += 3;
1391       }
1392     }
1393     frequencies.data[256] = 1; /*there will be exactly 1 end code, at the end of the block*/
1394
1395     error = HuffmanTree_makeFromFrequencies(&codes, frequencies.data, frequencies.size, 15);
1396     if(error) break;
1397     error = HuffmanTree_makeFromFrequencies(&codesD, frequenciesD.data, frequenciesD.size, 15);
1398     if(error) break;
1399
1400     addBitToStream(&bp, out, BFINAL);
1401     addBitToStream(&bp, out, 0); /*first bit of BTYPE "dynamic"*/
1402     addBitToStream(&bp, out, 1); /*second bit of BTYPE "dynamic"*/
1403
1404     numcodes = codes.numcodes; if(numcodes > 286) numcodes = 286;
1405     numcodesD = codesD.numcodes; if(numcodesD > 30) numcodesD = 30;
1406     for(i = 0; i < numcodes; i++) uivector_push_back(&lldll, HuffmanTree_getLength(&codes, (unsigned)i));
1407     for(i = 0; i < numcodesD; i++) uivector_push_back(&lldll, HuffmanTree_getLength(&codesD, (unsigned)i));
1408
1409     /*make lldl smaller by using repeat codes 16 (copy length 3-6 times), 17 (3-10 zeroes), 18 (11-138 zeroes)*/
1410     for(i = 0; i < (unsigned)lldll.size; i++)
1411     {
1412       unsigned j = 0;
1413       while(i + j + 1 < (unsigned)lldll.size && lldll.data[i + j + 1] == lldll.data[i]) j++;
1414
1415       if(lldll.data[i] == 0 && j >= 2)
1416       {
1417         j++; /*include the first zero*/
1418         if(j <= 10) { uivector_push_back(&lldl, 17); uivector_push_back(&lldl, j - 3); }
1419         else
1420         {
1421           if(j > 138) j = 138;
1422           uivector_push_back(&lldl, 18); uivector_push_back(&lldl, j - 11);
1423         }
1424         i += (j - 1);
1425       }
1426       else if(j >= 3)
1427       {
1428         size_t k;
1429         unsigned num = j / 6, rest = j % 6;
1430         uivector_push_back(&lldl, lldll.data[i]);
1431         for(k = 0; k < num; k++) { uivector_push_back(&lldl, 16); uivector_push_back(&lldl,    6 - 3); }
1432         if(rest >= 3)            { uivector_push_back(&lldl, 16); uivector_push_back(&lldl, rest - 3); }
1433         else j -= rest;
1434         i += j;
1435       }
1436       else uivector_push_back(&lldl, lldll.data[i]);
1437     }
1438
1439     /*generate huffmantree for the length codes of lit/len and dist codes*/
1440     if(!uivector_resizev(&amounts, 19, 0)) { error = 9926; break; } /*16 possible lengths (0-15) and 3 repeat codes (16, 17 and 18)*/
1441     for(i = 0; i < lldl.size; i++)
1442     {
1443       amounts.data[lldl.data[i]]++;
1444       if(lldl.data[i] >= 16) i++; /*after a repeat code come the bits that specify the amount, those don't need to be in the amounts calculation*/
1445     }
1446
1447     error = HuffmanTree_makeFromFrequencies(&codelengthcodes, amounts.data, amounts.size, 7);
1448     if(error) break;
1449
1450     if(!uivector_resize(&clcls, 19)) { error = 9927; break; }
1451     for(i = 0; i < 19; i++) clcls.data[i] = HuffmanTree_getLength(&codelengthcodes, CLCL[i]); /*lenghts of code length tree is in the order as specified by deflate*/
1452     while(clcls.data[clcls.size - 1] == 0 && clcls.size > 4)
1453     {
1454       if(!uivector_resize(&clcls, clcls.size - 1)) { error = 9928; break; } /*remove zeros at the end, but minimum size must be 4*/
1455     }
1456     if(error) break;
1457
1458     /*write the HLIT, HDIST and HCLEN values*/
1459     HLIT = (unsigned)(numcodes - 257);
1460     HDIST = (unsigned)(numcodesD - 1);
1461     HCLEN = (unsigned)clcls.size - 4;
1462     addBitsToStream(&bp, out, HLIT, 5);
1463     addBitsToStream(&bp, out, HDIST, 5);
1464     addBitsToStream(&bp, out, HCLEN, 4);
1465
1466     /*write the code lenghts of the code length alphabet*/
1467     for(i = 0; i < HCLEN + 4; i++) addBitsToStream(&bp, out, clcls.data[i], 3);
1468
1469     /*write the lenghts of the lit/len AND the dist alphabet*/
1470     for(i = 0; i < lldl.size; i++)
1471     {
1472       addHuffmanSymbol(&bp, out, HuffmanTree_getCode(&codelengthcodes, lldl.data[i]), HuffmanTree_getLength(&codelengthcodes, lldl.data[i]));
1473       /*extra bits of repeat codes*/
1474       if(lldl.data[i] == 16) addBitsToStream(&bp, out, lldl.data[++i], 2);
1475       else if(lldl.data[i] == 17) addBitsToStream(&bp, out, lldl.data[++i], 3);
1476       else if(lldl.data[i] == 18) addBitsToStream(&bp, out, lldl.data[++i], 7);
1477     }
1478
1479     /*write the compressed data symbols*/
1480     writeLZ77data(&bp, out, &lz77_encoded, &codes, &codesD);
1481     if(HuffmanTree_getLength(&codes, 256) == 0) { error = 64; break; } /*the length of the end code 256 must be larger than 0*/
1482     addHuffmanSymbol(&bp, out, HuffmanTree_getCode(&codes, 256), HuffmanTree_getLength(&codes, 256)); /*end code*/
1483
1484     break; /*end of error-while*/
1485   }
1486
1487   /*cleanup*/
1488   uivector_cleanup(&lz77_encoded);
1489   HuffmanTree_cleanup(&codes);
1490   HuffmanTree_cleanup(&codesD);
1491   HuffmanTree_cleanup(&codelengthcodes);
1492   uivector_cleanup(&frequencies);
1493   uivector_cleanup(&frequenciesD);
1494   uivector_cleanup(&amounts);
1495   uivector_cleanup(&lldl);
1496   uivector_cleanup(&lldll);
1497   uivector_cleanup(&clcls);
1498
1499   return error;
1500 }
1501
1502 static unsigned deflateFixed(ucvector* out, const unsigned char* data, size_t datasize, const LodeZlib_DeflateSettings* settings)
1503 {
1504   HuffmanTree codes; /*tree for literal values and length codes*/
1505   HuffmanTree codesD; /*tree for distance codes*/
1506
1507   unsigned BFINAL = 1; /*make only one block... the first and final one*/
1508   unsigned error = 0;
1509   size_t i, bp = 0; /*the bit pointer*/
1510
1511   HuffmanTree_init(&codes);
1512   HuffmanTree_init(&codesD);
1513
1514   generateFixedTree(&codes);
1515   generateDistanceTree(&codesD);
1516
1517   addBitToStream(&bp, out, BFINAL);
1518   addBitToStream(&bp, out, 1); /*first bit of BTYPE*/
1519   addBitToStream(&bp, out, 0); /*second bit of BTYPE*/
1520
1521   if(settings->useLZ77) /*LZ77 encoded*/
1522   {
1523     uivector lz77_encoded;
1524     uivector_init(&lz77_encoded);
1525     error = encodeLZ77(&lz77_encoded, data, datasize, settings->windowSize);
1526     if(!error) writeLZ77data(&bp, out, &lz77_encoded, &codes, &codesD);
1527     uivector_cleanup(&lz77_encoded);
1528   }
1529   else /*no LZ77, but still will be Huffman compressed*/
1530   {
1531     for(i = 0; i < datasize; i++) addHuffmanSymbol(&bp, out, HuffmanTree_getCode(&codes, data[i]), HuffmanTree_getLength(&codes, data[i]));
1532   }
1533   if(!error) addHuffmanSymbol(&bp, out, HuffmanTree_getCode(&codes, 256), HuffmanTree_getLength(&codes, 256)); /*"end" code*/
1534
1535   /*cleanup*/
1536   HuffmanTree_cleanup(&codes);
1537   HuffmanTree_cleanup(&codesD);
1538
1539   return error;
1540 }
1541
1542 unsigned LodeFlate_deflate(ucvector* out, const unsigned char* data, size_t datasize, const LodeZlib_DeflateSettings* settings)
1543 {
1544   unsigned error = 0;
1545   if(settings->btype == 0) error = deflateNoCompression(out, data, datasize);
1546   else if(settings->btype == 1) error = deflateFixed(out, data, datasize, settings);
1547   else if(settings->btype == 2) error = deflateDynamic(out, data, datasize, settings);
1548   else error = 61;
1549   return error;
1550 }
1551
1552 #endif /*LODEPNG_COMPILE_DECODER*/
1553
1554 /* ////////////////////////////////////////////////////////////////////////// */
1555 /* / Adler32                                                                  */
1556 /* ////////////////////////////////////////////////////////////////////////// */
1557
1558 static unsigned update_adler32(unsigned adler, const unsigned char* data, unsigned len)
1559 {
1560    unsigned s1 = adler & 0xffff;
1561    unsigned s2 = (adler >> 16) & 0xffff;
1562
1563   while(len > 0)
1564   {
1565     /*at least 5550 sums can be done before the sums overflow, saving us from a lot of module divisions*/
1566     unsigned amount = len > 5550 ? 5550 : len;
1567     len -= amount;
1568     while(amount > 0)
1569     {
1570       s1 = (s1 + *data++);
1571       s2 = (s2 + s1);
1572       amount--;
1573     }
1574     s1 %= 65521;
1575     s2 %= 65521;
1576   }
1577
1578   return (s2 << 16) | s1;
1579 }
1580
1581 /*Return the adler32 of the bytes data[0..len-1]*/
1582 static unsigned adler32(const unsigned char* data, unsigned len)
1583 {
1584   return update_adler32(1L, data, len);
1585 }
1586
1587 /* ////////////////////////////////////////////////////////////////////////// */
1588 /* / Reading and writing single bits and bytes from/to stream for Zlib      / */
1589 /* ////////////////////////////////////////////////////////////////////////// */
1590
1591 #ifdef LODEPNG_COMPILE_ENCODER
1592 void LodeZlib_add32bitInt(ucvector* buffer, unsigned value)
1593 {
1594   ucvector_push_back(buffer, (unsigned char)((value >> 24) & 0xff));
1595   ucvector_push_back(buffer, (unsigned char)((value >> 16) & 0xff));
1596   ucvector_push_back(buffer, (unsigned char)((value >>  8) & 0xff));
1597   ucvector_push_back(buffer, (unsigned char)((value      ) & 0xff));
1598 }
1599 #endif /*LODEPNG_COMPILE_ENCODER*/
1600
1601 unsigned LodeZlib_read32bitInt(const unsigned char* buffer)
1602 {
1603   return (buffer[0] << 24) | (buffer[1] << 16) | (buffer[2] << 8) | buffer[3];
1604 }
1605
1606 /* ////////////////////////////////////////////////////////////////////////// */
1607 /* / Zlib                                                                   / */
1608 /* ////////////////////////////////////////////////////////////////////////// */
1609
1610 #ifdef LODEPNG_COMPILE_DECODER
1611
1612 unsigned LodeZlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in, size_t insize, const LodeZlib_DecompressSettings* settings)
1613 {
1614   unsigned error = 0;
1615   unsigned CM, CINFO, FDICT;
1616   ucvector outv;
1617
1618   if(insize < 2) { error = 53; return error; } /*error, size of zlib data too small*/
1619   /*read information from zlib header*/
1620   if((in[0] * 256 + in[1]) % 31 != 0) { error = 24; return error; } /*error: 256 * in[0] + in[1] must be a multiple of 31, the FCHECK value is supposed to be made that way*/
1621
1622   CM = in[0] & 15;
1623   CINFO = (in[0] >> 4) & 15;
1624   /*FCHECK = in[1] & 31; //FCHECK is already tested above*/
1625   FDICT = (in[1] >> 5) & 1;
1626   /*FLEVEL = (in[1] >> 6) & 3; //not really important, all it does it to give a compiler warning about unused variable, we don't care what encoding setting the encoder used*/
1627
1628   if(CM != 8 || CINFO > 7) { error = 25; return error; } /*error: only compression method 8: inflate with sliding window of 32k is supported by the PNG spec*/
1629   if(FDICT != 0) { error = 26; return error; } /*error: the specification of PNG says about the zlib stream: "The additional flags shall not specify a preset dictionary."*/
1630
1631   ucvector_init_buffer(&outv, *out, *outsize); /*ucvector-controlled version of the output buffer, for dynamic array*/
1632   error = LodeFlate_inflate(&outv, in, insize, 2);
1633   *out = outv.data;
1634   *outsize = outv.size;
1635   if(error) return error;
1636
1637   if(!settings->ignoreAdler32)
1638   {
1639     unsigned ADLER32 = LodeZlib_read32bitInt(&in[insize - 4]);
1640     unsigned checksum = adler32(outv.data, (unsigned)outv.size);
1641     if(checksum != ADLER32) { error = 58; return error; }
1642   }
1643
1644   return error;
1645 }
1646
1647 #endif /*LODEPNG_COMPILE_DECODER*/
1648
1649 #ifdef LODEPNG_COMPILE_ENCODER
1650
1651 unsigned LodeZlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in, size_t insize, const LodeZlib_DeflateSettings* settings)
1652 {
1653   /*initially, *out must be NULL and outsize 0, if you just give some random *out that's pointing to a non allocated buffer, this'll crash*/
1654   ucvector deflatedata, outv;
1655   size_t i;
1656   unsigned error;
1657
1658   unsigned ADLER32;
1659   /*zlib data: 1 byte CMF (CM+CINFO), 1 byte FLG, deflate data, 4 byte ADLER32 checksum of the Decompressed data*/
1660   unsigned CMF = 120; /*0b01111000: CM 8, CINFO 7. With CINFO 7, any window size up to 32768 can be used.*/
1661   unsigned FLEVEL = 0;
1662   unsigned FDICT = 0;
1663   unsigned CMFFLG = 256 * CMF + FDICT * 32 + FLEVEL * 64;
1664   unsigned FCHECK = 31 - CMFFLG % 31;
1665   CMFFLG += FCHECK;
1666
1667   ucvector_init_buffer(&outv, *out, *outsize); /*ucvector-controlled version of the output buffer, for dynamic array*/
1668
1669   ucvector_push_back(&outv, (unsigned char)(CMFFLG / 256));
1670   ucvector_push_back(&outv, (unsigned char)(CMFFLG % 256));
1671
1672   ucvector_init(&deflatedata);
1673   error = LodeFlate_deflate(&deflatedata, in, insize, settings);
1674
1675   if(!error)
1676   {
1677     ADLER32 = adler32(in, (unsigned)insize);
1678     for(i = 0; i < deflatedata.size; i++) ucvector_push_back(&outv, deflatedata.data[i]);
1679     ucvector_cleanup(&deflatedata);
1680     LodeZlib_add32bitInt(&outv, ADLER32);
1681   }
1682
1683   *out = outv.data;
1684   *outsize = outv.size;
1685
1686   return error;
1687 }
1688
1689 #endif /*LODEPNG_COMPILE_ENCODER*/
1690
1691 #endif /*LODEPNG_COMPILE_ZLIB*/
1692
1693 /* ////////////////////////////////////////////////////////////////////////// */
1694
1695 #ifdef LODEPNG_COMPILE_ENCODER
1696
1697 void LodeZlib_DeflateSettings_init(LodeZlib_DeflateSettings* settings)
1698 {
1699   settings->btype = 2; /*compress with dynamic huffman tree (not in the mathematical sense, just not the predefined one)*/
1700   settings->useLZ77 = 1;
1701   settings->windowSize = 2048; /*this is a good tradeoff between speed and compression ratio*/
1702 }
1703
1704 const LodeZlib_DeflateSettings LodeZlib_defaultDeflateSettings = {2, 1, 2048};
1705
1706 #endif /*LODEPNG_COMPILE_ENCODER*/
1707
1708 #ifdef LODEPNG_COMPILE_DECODER
1709
1710 void LodeZlib_DecompressSettings_init(LodeZlib_DecompressSettings* settings)
1711 {
1712   settings->ignoreAdler32 = 0;
1713 }
1714
1715 const LodeZlib_DecompressSettings LodeZlib_defaultDecompressSettings = {0};
1716
1717 #endif /*LODEPNG_COMPILE_DECODER*/
1718
1719 /* ////////////////////////////////////////////////////////////////////////// */
1720 /* ////////////////////////////////////////////////////////////////////////// */
1721 /* ////////////////////////////////////////////////////////////////////////// */
1722 /* ////////////////////////////////////////////////////////////////////////// */
1723 /* ////////////////////////////////////////////////////////////////////////// */
1724 /* // End of Zlib related code, now comes the PNG related code that uses it// */
1725 /* ////////////////////////////////////////////////////////////////////////// */
1726 /* ////////////////////////////////////////////////////////////////////////// */
1727 /* ////////////////////////////////////////////////////////////////////////// */
1728 /* ////////////////////////////////////////////////////////////////////////// */
1729 /* ////////////////////////////////////////////////////////////////////////// */
1730
1731 #ifdef LODEPNG_COMPILE_PNG
1732
1733 /*
1734 The two functions below (LodePNG_decompress and LodePNG_compress) directly call the
1735 LodeZlib_decompress and LodeZlib_compress functions. The only purpose of the functions
1736 below, is to provide the ability to let LodePNG use a different Zlib encoder by only
1737 changing the two functions below, instead of changing it inside the vareous places
1738 in the other LodePNG functions.
1739
1740 *out must be NULL and *outsize must be 0 initially, and after the function is done,
1741 *out must point to the decompressed data, *outsize must be the size of it, and must
1742 be the size of the useful data in bytes, not the alloc size.
1743 */
1744
1745 #ifdef LODEPNG_COMPILE_DECODER
1746 static unsigned LodePNG_decompress(unsigned char** out, size_t* outsize, const unsigned char* in, size_t insize, const LodeZlib_DecompressSettings* settings)
1747 {
1748   return LodeZlib_decompress(out, outsize, in, insize, settings);
1749 }
1750 #endif /*LODEPNG_COMPILE_DECODER*/
1751 #ifdef LODEPNG_COMPILE_ENCODER
1752 static unsigned LodePNG_compress(unsigned char** out, size_t* outsize, const unsigned char* in, size_t insize, const LodeZlib_DeflateSettings* settings)
1753 {
1754   return LodeZlib_compress(out, outsize, in, insize, settings);
1755 }
1756 #endif /*LODEPNG_COMPILE_ENCODER*/
1757
1758 /* ////////////////////////////////////////////////////////////////////////// */
1759 /* / CRC32                                                                  / */
1760 /* ////////////////////////////////////////////////////////////////////////// */
1761
1762 static unsigned Crc32_crc_table_computed = 0;
1763 static unsigned Crc32_crc_table[256];
1764
1765 /*Make the table for a fast CRC.*/
1766 static void Crc32_make_crc_table(void)
1767 {
1768   unsigned c, k, n;
1769   for(n = 0; n < 256; n++)
1770   {
1771     c = n;
1772     for(k = 0; k < 8; k++)
1773     {
1774       if(c & 1) c = 0xedb88320L ^ (c >> 1);
1775       else c = c >> 1;
1776     }
1777     Crc32_crc_table[n] = c;
1778   }
1779   Crc32_crc_table_computed = 1;
1780 }
1781
1782 /*Update a running CRC with the bytes buf[0..len-1]--the CRC should be
1783 initialized to all 1's, and the transmitted value is the 1's complement of the
1784 final running CRC (see the crc() routine below).*/
1785 static unsigned Crc32_update_crc(const unsigned char* buf, unsigned crc, size_t len)
1786 {
1787   unsigned c = crc;
1788   size_t n;
1789
1790   if(!Crc32_crc_table_computed) Crc32_make_crc_table();
1791   for(n = 0; n < len; n++)
1792   {
1793     c = Crc32_crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
1794   }
1795   return c;
1796 }
1797
1798 /*Return the CRC of the bytes buf[0..len-1].*/
1799 static unsigned Crc32_crc(const unsigned char* buf, size_t len)
1800 {
1801   return Crc32_update_crc(buf, 0xffffffffL, len) ^ 0xffffffffL;
1802 }
1803
1804 /* ////////////////////////////////////////////////////////////////////////// */
1805 /* / Reading and writing single bits and bytes from/to stream for LodePNG   / */
1806 /* ////////////////////////////////////////////////////////////////////////// */
1807
1808 static unsigned char readBitFromReversedStream(size_t* bitpointer, const unsigned char* bitstream)
1809 {
1810   unsigned char result = (unsigned char)((bitstream[(*bitpointer) >> 3] >> (7 - ((*bitpointer) & 0x7))) & 1);
1811   (*bitpointer)++;
1812   return result;
1813 }
1814
1815 static unsigned readBitsFromReversedStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
1816 {
1817   unsigned result = 0;
1818   size_t i;
1819   for(i = nbits - 1; i < nbits; i--) result += (unsigned)readBitFromReversedStream(bitpointer, bitstream) << i;
1820   return result;
1821 }
1822
1823 #ifdef LODEPNG_COMPILE_DECODER
1824 static void setBitOfReversedStream0(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
1825 {
1826   /*the current bit in bitstream must be 0 for this to work*/
1827   if(bit) bitstream[(*bitpointer) >> 3] |=  (bit << (7 - ((*bitpointer) & 0x7))); /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/
1828   (*bitpointer)++;
1829 }
1830 #endif /*LODEPNG_COMPILE_DECODER*/
1831
1832 static void setBitOfReversedStream(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
1833 {
1834   /*the current bit in bitstream may be 0 or 1 for this to work*/
1835   if(bit == 0) bitstream[(*bitpointer) >> 3] &=  (unsigned char)(~(1 << (7 - ((*bitpointer) & 0x7))));
1836   else bitstream[(*bitpointer) >> 3] |=  (1 << (7 - ((*bitpointer) & 0x7)));
1837   (*bitpointer)++;
1838 }
1839
1840 static unsigned LodePNG_read32bitInt(const unsigned char* buffer)
1841 {
1842   return (buffer[0] << 24) | (buffer[1] << 16) | (buffer[2] << 8) | buffer[3];
1843 }
1844
1845 static void LodePNG_set32bitInt(unsigned char* buffer, unsigned value) /*buffer must have at least 4 allocated bytes available*/
1846 {
1847   buffer[0] = (unsigned char)((value >> 24) & 0xff);
1848   buffer[1] = (unsigned char)((value >> 16) & 0xff);
1849   buffer[2] = (unsigned char)((value >>  8) & 0xff);
1850   buffer[3] = (unsigned char)((value      ) & 0xff);
1851 }
1852
1853 #ifdef LODEPNG_COMPILE_ENCODER
1854 static void LodePNG_add32bitInt(ucvector* buffer, unsigned value)
1855 {
1856   ucvector_resize(buffer, buffer->size + 4);
1857   LodePNG_set32bitInt(&buffer->data[buffer->size - 4], value);
1858 }
1859 #endif /*LODEPNG_COMPILE_ENCODER*/
1860
1861 /* ////////////////////////////////////////////////////////////////////////// */
1862 /* / PNG chunks                                                             / */
1863 /* ////////////////////////////////////////////////////////////////////////// */
1864
1865 unsigned LodePNG_chunk_length(const unsigned char* chunk) /*get the length of the data of the chunk. Total chunk length has 12 bytes more.*/
1866 {
1867   return LodePNG_read32bitInt(&chunk[0]);
1868 }
1869
1870 void LodePNG_chunk_type(char type[5], const unsigned char* chunk) /*puts the 4-byte type in null terminated string*/
1871 {
1872   unsigned i;
1873   for(i = 0; i < 4; i++) type[i] = chunk[4 + i];
1874   type[4] = 0; /*null termination char*/
1875 }
1876
1877 unsigned char LodePNG_chunk_type_equals(const unsigned char* chunk, const char* type) /*check if the type is the given type*/
1878 {
1879   if(strlen(type) != 4) return 0;
1880   return (chunk[4] == type[0] && chunk[5] == type[1] && chunk[6] == type[2] && chunk[7] == type[3]);
1881 }
1882
1883 /*properties of PNG chunks gotten from capitalization of chunk type name, as defined by the standard*/
1884 unsigned char LodePNG_chunk_critical(const unsigned char* chunk) /*0: ancillary chunk, 1: it's one of the critical chunk types*/
1885 {
1886   return((chunk[4] & 32) == 0);
1887 }
1888
1889 unsigned char LodePNG_chunk_private(const unsigned char* chunk) /*0: public, 1: private*/
1890 {
1891   return((chunk[6] & 32) != 0);
1892 }
1893
1894 unsigned char LodePNG_chunk_safetocopy(const unsigned char* chunk) /*0: the chunk is unsafe to copy, 1: the chunk is safe to copy*/
1895 {
1896   return((chunk[7] & 32) != 0);
1897 }
1898
1899 unsigned char* LodePNG_chunk_data(unsigned char* chunk) /*get pointer to the data of the chunk*/
1900 {
1901   return &chunk[8];
1902 }
1903
1904 const unsigned char* LodePNG_chunk_data_const(const unsigned char* chunk) /*get pointer to the data of the chunk*/
1905 {
1906   return &chunk[8];
1907 }
1908
1909 unsigned LodePNG_chunk_check_crc(const unsigned char* chunk) /*returns 0 if the crc is correct, error code if it's incorrect*/
1910 {
1911   unsigned length = LodePNG_chunk_length(chunk);
1912   unsigned CRC = LodePNG_read32bitInt(&chunk[length + 8]);
1913   unsigned checksum = Crc32_crc(&chunk[4], length + 4); /*the CRC is taken of the data and the 4 chunk type letters, not the length*/
1914   if(CRC != checksum) return 1;
1915   else return 0;
1916 }
1917
1918 void LodePNG_chunk_generate_crc(unsigned char* chunk) /*generates the correct CRC from the data and puts it in the last 4 bytes of the chunk*/
1919 {
1920   unsigned length = LodePNG_chunk_length(chunk);
1921   unsigned CRC = Crc32_crc(&chunk[4], length + 4);
1922   LodePNG_set32bitInt(chunk + 8 + length, CRC);
1923 }
1924
1925 unsigned char* LodePNG_chunk_next(unsigned char* chunk) /*don't use on IEND chunk, as there is no next chunk then*/
1926 {
1927   unsigned total_chunk_length = LodePNG_chunk_length(chunk) + 12;
1928   return &chunk[total_chunk_length];
1929 }
1930
1931 const unsigned char* LodePNG_chunk_next_const(const unsigned char* chunk) /*don't use on IEND chunk, as there is no next chunk then*/
1932 {
1933   unsigned total_chunk_length = LodePNG_chunk_length(chunk) + 12;
1934   return &chunk[total_chunk_length];
1935 }
1936
1937 unsigned LodePNG_append_chunk(unsigned char** out, size_t* outlength, const unsigned char* chunk) /*appends chunk that was already created, to the data. Returns error code.*/
1938 {
1939   unsigned i;
1940   unsigned total_chunk_length = LodePNG_chunk_length(chunk) + 12;
1941   unsigned char *chunk_start, *new_buffer;
1942   size_t new_length = (*outlength) + total_chunk_length;
1943   if(new_length < total_chunk_length || new_length < (*outlength)) return 77; /*integer overflow happened*/
1944
1945   new_buffer = (unsigned char*)realloc(*out, new_length);
1946   if(!new_buffer) return 9929;
1947   (*out) = new_buffer;
1948   (*outlength) = new_length;
1949   chunk_start = &(*out)[new_length - total_chunk_length];
1950
1951   for(i = 0; i < total_chunk_length; i++) chunk_start[i] = chunk[i];
1952
1953   return 0;
1954 }
1955
1956 unsigned LodePNG_create_chunk(unsigned char** out, size_t* outlength, unsigned length, const char* type, const unsigned char* data) /*appends new chunk to out. Returns error code; may change memory address of out buffer*/
1957 {
1958   unsigned i;
1959   unsigned char *chunk, *new_buffer;
1960   size_t new_length = (*outlength) + length + 12;
1961   if(new_length < length + 12 || new_length < (*outlength)) return 77; /*integer overflow happened*/
1962   new_buffer = (unsigned char*)realloc(*out, new_length);
1963   if(!new_buffer) return 9930;
1964   (*out) = new_buffer;
1965   (*outlength) = new_length;
1966   chunk = &(*out)[(*outlength) - length - 12];
1967
1968   /*1: length*/
1969   LodePNG_set32bitInt(chunk, (unsigned)length);
1970
1971   /*2: chunk name (4 letters)*/
1972   chunk[4] = type[0];
1973   chunk[5] = type[1];
1974   chunk[6] = type[2];
1975   chunk[7] = type[3];
1976
1977   /*3: the data*/
1978   for(i = 0; i < length; i++) chunk[8 + i] = data[i];
1979
1980   /*4: CRC (of the chunkname characters and the data)*/
1981   LodePNG_chunk_generate_crc(chunk);
1982
1983   return 0;
1984 }
1985
1986 /* ////////////////////////////////////////////////////////////////////////// */
1987 /* / Color types and such                                                   / */
1988 /* ////////////////////////////////////////////////////////////////////////// */
1989
1990 /*return type is a LodePNG error code*/
1991 static unsigned checkColorValidity(unsigned colorType, unsigned bd) /*bd = bitDepth*/
1992 {
1993   switch(colorType)
1994   {
1995     case 0: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8 || bd == 16)) return 37; break; /*grey*/
1996     case 2: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*RGB*/
1997     case 3: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8            )) return 37; break; /*palette*/
1998     case 4: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*grey + alpha*/
1999     case 6: if(!(                                 bd == 8 || bd == 16)) return 37; break; /*RGBA*/
2000     default: return 31;
2001   }
2002   return 0; /*allowed color type / bits combination*/
2003 }
2004
2005 static unsigned getNumColorChannels(unsigned colorType)
2006 {
2007   switch(colorType)
2008   {
2009     case 0: return 1; /*grey*/
2010     case 2: return 3; /*RGB*/
2011     case 3: return 1; /*palette*/
2012     case 4: return 2; /*grey + alpha*/
2013     case 6: return 4; /*RGBA*/
2014   }
2015   return 0; /*unexisting color type*/
2016 }
2017
2018 static unsigned getBpp(unsigned colorType, unsigned bitDepth)
2019 {
2020   return getNumColorChannels(colorType) * bitDepth; /*bits per pixel is amount of channels * bits per channel*/
2021 }
2022
2023 /* ////////////////////////////////////////////////////////////////////////// */
2024
2025 void LodePNG_InfoColor_init(LodePNG_InfoColor* info)
2026 {
2027   info->key_defined = 0;
2028   info->key_r = info->key_g = info->key_b = 0;
2029   info->colorType = 6;
2030   info->bitDepth = 8;
2031   info->palette = 0;
2032   info->palettesize = 0;
2033 }
2034
2035 void LodePNG_InfoColor_cleanup(LodePNG_InfoColor* info)
2036 {
2037   LodePNG_InfoColor_clearPalette(info);
2038 }
2039
2040 void LodePNG_InfoColor_clearPalette(LodePNG_InfoColor* info)
2041 {
2042   if(info->palette) free(info->palette);
2043   info->palettesize = 0;
2044 }
2045
2046 unsigned LodePNG_InfoColor_addPalette(LodePNG_InfoColor* info, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
2047 {
2048   unsigned char* data;
2049   /*the same resize technique as C++ std::vectors is used, and here it's made so that for a palette with the max of 256 colors, it'll have the exact alloc size*/
2050   if(!(info->palettesize & (info->palettesize - 1))) /*if palettesize is 0 or a power of two*/
2051   {
2052     /*allocated data must be at least 4* palettesize (for 4 color bytes)*/
2053     size_t alloc_size = info->palettesize == 0 ? 4 : info->palettesize * 4 * 2;
2054     data = (unsigned char*)realloc(info->palette, alloc_size);
2055     if(!data) return 9931;
2056     else info->palette = data;
2057   }
2058   info->palette[4 * info->palettesize + 0] = r;
2059   info->palette[4 * info->palettesize + 1] = g;
2060   info->palette[4 * info->palettesize + 2] = b;
2061   info->palette[4 * info->palettesize + 3] = a;
2062   info->palettesize++;
2063   return 0;
2064 }
2065
2066 unsigned LodePNG_InfoColor_getBpp(const LodePNG_InfoColor* info) { return getBpp(info->colorType, info->bitDepth); } /*calculate bits per pixel out of colorType and bitDepth*/
2067 unsigned LodePNG_InfoColor_getChannels(const LodePNG_InfoColor* info) { return getNumColorChannels(info->colorType); }
2068 unsigned LodePNG_InfoColor_isGreyscaleType(const LodePNG_InfoColor* info) { return info->colorType == 0 || info->colorType == 4; }
2069 unsigned LodePNG_InfoColor_isAlphaType(const LodePNG_InfoColor* info) { return (info->colorType & 4) != 0; }
2070
2071 unsigned LodePNG_InfoColor_equal(const LodePNG_InfoColor* info1, const LodePNG_InfoColor* info2)
2072 {
2073   return info1->colorType == info2->colorType
2074       && info1->bitDepth  == info2->bitDepth; /*palette and color key not compared*/
2075 }
2076
2077 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
2078
2079 void LodePNG_UnknownChunks_init(LodePNG_UnknownChunks* chunks)
2080 {
2081   unsigned i;
2082   for(i = 0; i < 3; i++) chunks->data[i] = 0;
2083   for(i = 0; i < 3; i++) chunks->datasize[i] = 0;
2084 }
2085
2086 void LodePNG_UnknownChunks_cleanup(LodePNG_UnknownChunks* chunks)
2087 {
2088   unsigned i;
2089   for(i = 0; i < 3; i++) free(chunks->data[i]);
2090 }
2091
2092 unsigned LodePNG_UnknownChunks_copy(LodePNG_UnknownChunks* dest, const LodePNG_UnknownChunks* src)
2093 {
2094   unsigned i;
2095
2096   LodePNG_UnknownChunks_cleanup(dest);
2097
2098   for(i = 0; i < 3; i++)
2099   {
2100     size_t j;
2101     dest->datasize[i] = src->datasize[i];
2102     dest->data[i] = (unsigned char*)malloc(src->datasize[i]);
2103     if(!dest->data[i] && dest->datasize[i]) return 9932;
2104     for(j = 0; j < src->datasize[i]; j++) dest->data[i][j] = src->data[i][j];
2105   }
2106
2107   return 0;
2108 }
2109
2110 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
2111
2112 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2113
2114 void LodePNG_Text_init(LodePNG_Text* text)
2115 {
2116   text->num = 0;
2117   text->keys = NULL;
2118   text->strings = NULL;
2119 }
2120
2121 void LodePNG_Text_cleanup(LodePNG_Text* text)
2122 {
2123   LodePNG_Text_clear(text);
2124 }
2125
2126 unsigned LodePNG_Text_copy(LodePNG_Text* dest, const LodePNG_Text* source)
2127 {
2128   size_t i = 0;
2129   dest->keys = 0;
2130   dest->strings = 0;
2131   dest->num = 0;
2132   for(i = 0; i < source->num; i++)
2133   {
2134     unsigned error = LodePNG_Text_add(dest, source->keys[i], source->strings[i]);
2135     if(error) return error;
2136   }
2137   return 0;
2138 }
2139
2140 void LodePNG_Text_clear(LodePNG_Text* text)
2141 {
2142   size_t i;
2143   for(i = 0; i < text->num; i++)
2144     {
2145     string_cleanup(&text->keys[i]);
2146     string_cleanup(&text->strings[i]);
2147     }
2148   free(text->keys);
2149   free(text->strings);
2150 }
2151
2152 unsigned LodePNG_Text_add(LodePNG_Text* text, const char* key, const char* str)
2153 {
2154   char** new_keys = (char**)(realloc(text->keys, sizeof(char*) * (text->num + 1)));
2155   char** new_strings = (char**)(realloc(text->strings, sizeof(char*) * (text->num + 1)));
2156   if(!new_keys || !new_strings)
2157   {
2158     free(new_keys);
2159     free(new_strings);
2160     return 9933;
2161   }
2162
2163   text->num++;
2164   text->keys = new_keys;
2165   text->strings = new_strings;
2166
2167   string_init(&text->keys[text->num - 1]);
2168   string_set(&text->keys[text->num - 1], key);
2169
2170   string_init(&text->strings[text->num - 1]);
2171   string_set(&text->strings[text->num - 1], str);
2172
2173   return 0;
2174 }
2175
2176 /******************************************************************************/
2177
2178 void LodePNG_IText_init(LodePNG_IText* text)
2179 {
2180   text->num = 0;
2181   text->keys = NULL;
2182   text->langtags = NULL;
2183   text->transkeys = NULL;
2184   text->strings = NULL;
2185 }
2186
2187 void LodePNG_IText_cleanup(LodePNG_IText* text)
2188 {
2189   LodePNG_IText_clear(text);
2190 }
2191
2192 unsigned LodePNG_IText_copy(LodePNG_IText* dest, const LodePNG_IText* source)
2193 {
2194   size_t i = 0;
2195   dest->keys = 0;
2196   dest->langtags = 0;
2197   dest->transkeys = 0;
2198   dest->strings = 0;
2199   dest->num = 0;
2200   for(i = 0; i < source->num; i++)
2201   {
2202     unsigned error = LodePNG_IText_add(dest, source->keys[i], source->langtags[i], source->transkeys[i], source->strings[i]);
2203     if(error) return error;
2204   }
2205   return 0;
2206 }
2207
2208 void LodePNG_IText_clear(LodePNG_IText* text)
2209 {
2210   size_t i;
2211   for(i = 0; i < text->num; i++)
2212     {
2213     string_cleanup(&text->keys[i]);
2214     string_cleanup(&text->langtags[i]);
2215     string_cleanup(&text->transkeys[i]);
2216     string_cleanup(&text->strings[i]);
2217     }
2218   free(text->keys);
2219   free(text->langtags);
2220   free(text->transkeys);
2221   free(text->strings);
2222 }
2223
2224 unsigned LodePNG_IText_add(LodePNG_IText* text, const char* key, const char* langtag, const char* transkey, const char* str)
2225 {
2226   char** new_keys = (char**)(realloc(text->keys, sizeof(char*) * (text->num + 1)));
2227   char** new_langtags = (char**)(realloc(text->langtags, sizeof(char*) * (text->num + 1)));
2228   char** new_transkeys = (char**)(realloc(text->transkeys, sizeof(char*) * (text->num + 1)));
2229   char** new_strings = (char**)(realloc(text->strings, sizeof(char*) * (text->num + 1)));
2230   if(!new_keys || !new_langtags || !new_transkeys || !new_strings)
2231   {
2232     free(new_keys);
2233     free(new_langtags);
2234     free(new_transkeys);
2235     free(new_strings);
2236     return 9934;
2237   }
2238
2239   text->num++;
2240   text->keys = new_keys;
2241   text->langtags = new_langtags;
2242   text->transkeys = new_transkeys;
2243   text->strings = new_strings;
2244
2245   string_init(&text->keys[text->num - 1]);
2246   string_set(&text->keys[text->num - 1], key);
2247
2248   string_init(&text->langtags[text->num - 1]);
2249   string_set(&text->langtags[text->num - 1], langtag);
2250
2251   string_init(&text->transkeys[text->num - 1]);
2252   string_set(&text->transkeys[text->num - 1], transkey);
2253
2254   string_init(&text->strings[text->num - 1]);
2255   string_set(&text->strings[text->num - 1], str);
2256
2257   return 0;
2258 }
2259
2260 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
2261
2262 void LodePNG_InfoPng_init(LodePNG_InfoPng* info)
2263 {
2264   info->width = info->height = 0;
2265   LodePNG_InfoColor_init(&info->color);
2266   info->interlaceMethod = 0;
2267   info->compressionMethod = 0;
2268   info->filterMethod = 0;
2269 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2270   info->background_defined = 0;
2271   info->background_r = info->background_g = info->background_b = 0;
2272
2273   LodePNG_Text_init(&info->text);
2274   LodePNG_IText_init(&info->itext);
2275
2276   info->time_defined = 0;
2277   info->phys_defined = 0;
2278 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
2279 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
2280   LodePNG_UnknownChunks_init(&info->unknown_chunks);
2281 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
2282 }
2283
2284 void LodePNG_InfoPng_cleanup(LodePNG_InfoPng* info)
2285 {
2286   LodePNG_InfoColor_cleanup(&info->color);
2287 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2288   LodePNG_Text_cleanup(&info->text);
2289   LodePNG_IText_cleanup(&info->itext);
2290 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
2291 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
2292   LodePNG_UnknownChunks_cleanup(&info->unknown_chunks);
2293 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
2294 }
2295
2296 unsigned LodePNG_InfoPng_copy(LodePNG_InfoPng* dest, const LodePNG_InfoPng* source)
2297 {
2298   unsigned error = 0;
2299   LodePNG_InfoPng_cleanup(dest);
2300   *dest = *source;
2301   LodePNG_InfoColor_init(&dest->color);
2302   error = LodePNG_InfoColor_copy(&dest->color, &source->color); if(error) return error;
2303
2304 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2305   error = LodePNG_Text_copy(&dest->text, &source->text); if(error) return error;
2306   error = LodePNG_IText_copy(&dest->itext, &source->itext); if(error) return error;
2307 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
2308
2309 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
2310   LodePNG_UnknownChunks_init(&dest->unknown_chunks);
2311   error = LodePNG_UnknownChunks_copy(&dest->unknown_chunks, &source->unknown_chunks); if(error) return error;
2312 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
2313   return error;
2314 }
2315
2316 void LodePNG_InfoPng_swap(LodePNG_InfoPng* a, LodePNG_InfoPng* b)
2317 {
2318   LodePNG_InfoPng temp = *a;
2319   *a = *b;
2320   *b = temp;
2321 }
2322
2323 unsigned LodePNG_InfoColor_copy(LodePNG_InfoColor* dest, const LodePNG_InfoColor* source)
2324 {
2325   size_t i;
2326   LodePNG_InfoColor_cleanup(dest);
2327   *dest = *source;
2328   dest->palette = (unsigned char*)malloc(source->palettesize * 4);
2329   if(!dest->palette && source->palettesize) return 9935;
2330   for(i = 0; i < source->palettesize * 4; i++) dest->palette[i] = source->palette[i];
2331   return 0;
2332 }
2333
2334 void LodePNG_InfoRaw_init(LodePNG_InfoRaw* info)
2335 {
2336   LodePNG_InfoColor_init(&info->color);
2337 }
2338
2339 void LodePNG_InfoRaw_cleanup(LodePNG_InfoRaw* info)
2340 {
2341   LodePNG_InfoColor_cleanup(&info->color);
2342 }
2343
2344 unsigned LodePNG_InfoRaw_copy(LodePNG_InfoRaw* dest, const LodePNG_InfoRaw* source)
2345 {
2346   unsigned error = 0;
2347   LodePNG_InfoRaw_cleanup(dest);
2348   *dest = *source;
2349   LodePNG_InfoColor_init(&dest->color);
2350   error = LodePNG_InfoColor_copy(&dest->color, &source->color); if(error) return error;
2351   return error;
2352 }
2353
2354 /* ////////////////////////////////////////////////////////////////////////// */
2355
2356 /*
2357 converts from any color type to 24-bit or 32-bit (later maybe more supported). return value = LodePNG error code
2358 the out buffer must have (w * h * bpp + 7) / 8 bytes, where bpp is the bits per pixel of the output color type (LodePNG_InfoColor_getBpp)
2359 for < 8 bpp images, there may _not_ be padding bits at the end of scanlines.
2360 */
2361 unsigned LodePNG_convert(unsigned char* out, const unsigned char* in, LodePNG_InfoColor* infoOut, LodePNG_InfoColor* infoIn, unsigned w, unsigned h)
2362 {
2363   const size_t numpixels = w * h; /*amount of pixels*/
2364   const unsigned OUT_BYTES = LodePNG_InfoColor_getBpp(infoOut) / 8; /*bytes per pixel in the output image*/
2365   const unsigned OUT_ALPHA = LodePNG_InfoColor_isAlphaType(infoOut); /*use 8-bit alpha channel*/
2366   size_t i, c, bp = 0; /*bitpointer, used by less-than-8-bit color types*/
2367
2368   /*cases where in and out already have the same format*/
2369   if(LodePNG_InfoColor_equal(infoIn, infoOut))
2370   {
2371     size_t i, size = (w * h * LodePNG_InfoColor_getBpp(infoIn) + 7) / 8;
2372     for(i = 0; i < size; i++) out[i] = in[i];
2373     return 0;
2374   }
2375
2376   if((infoOut->colorType == 2 || infoOut->colorType == 6) && infoOut->bitDepth == 8)
2377   {
2378     if(infoIn->bitDepth == 8)
2379     {
2380       switch(infoIn->colorType)
2381       {
2382         case 0: /*greyscale color*/
2383           for(i = 0; i < numpixels; i++)
2384           {
2385             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = 255;
2386             out[OUT_BYTES * i + 0] = out[OUT_BYTES * i + 1] = out[OUT_BYTES * i + 2] = in[i];
2387             if(OUT_ALPHA && infoIn->key_defined && in[i] == infoIn->key_r) out[OUT_BYTES * i + 3] = 0;
2388           }
2389         break;
2390         case 2: /*RGB color*/
2391           for(i = 0; i < numpixels; i++)
2392           {
2393             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = 255;
2394             for(c = 0; c < 3; c++) out[OUT_BYTES * i + c] = in[3 * i + c];
2395             if(OUT_ALPHA && infoIn->key_defined == 1 && in[3 * i + 0] == infoIn->key_r && in[3 * i + 1] == infoIn->key_g && in[3 * i + 2] == infoIn->key_b) out[OUT_BYTES * i + 3] = 0;
2396           }
2397         break;
2398         case 3: /*indexed color (palette)*/
2399           for(i = 0; i < numpixels; i++)
2400           {
2401             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = 255;
2402             if(in[i] >= infoIn->palettesize) return 46;
2403             for(c = 0; c < OUT_BYTES; c++) out[OUT_BYTES * i + c] = infoIn->palette[4 * in[i] + c]; /*get rgb colors from the palette*/
2404           }
2405         break;
2406         case 4: /*greyscale with alpha*/
2407           for(i = 0; i < numpixels; i++)
2408           {
2409             out[OUT_BYTES * i + 0] = out[OUT_BYTES * i + 1] = out[OUT_BYTES * i + 2] = in[2 * i + 0];
2410             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = in[2 * i + 1];
2411           }
2412         break;
2413         case 6: /*RGB with alpha*/
2414           for(i = 0; i < numpixels; i++)
2415           {
2416             for(c = 0; c < OUT_BYTES; c++) out[OUT_BYTES * i + c] = in[4 * i + c];
2417           }
2418         break;
2419         default: break;
2420       }
2421     }
2422     else if(infoIn->bitDepth == 16)
2423     {
2424       switch(infoIn->colorType)
2425       {
2426         case 0: /*greyscale color*/
2427           for(i = 0; i < numpixels; i++)
2428           {
2429             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = 255;
2430             out[OUT_BYTES * i + 0] = out[OUT_BYTES * i + 1] = out[OUT_BYTES * i + 2] = in[2 * i];
2431             if(OUT_ALPHA && infoIn->key_defined && 256U * in[i] + in[i + 1] == infoIn->key_r) out[OUT_BYTES * i + 3] = 0;
2432           }
2433         break;
2434         case 2: /*RGB color*/
2435           for(i = 0; i < numpixels; i++)
2436           {
2437             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = 255;
2438             for(c = 0; c < 3; c++) out[OUT_BYTES * i + c] = in[6 * i + 2 * c];
2439             if(OUT_ALPHA && infoIn->key_defined && 256U * in[6 * i + 0] + in[6 * i + 1] == infoIn->key_r && 256U * in[6 * i + 2] + in[6 * i + 3] == infoIn->key_g && 256U * in[6 * i + 4] + in[6 * i + 5] == infoIn->key_b) out[OUT_BYTES * i + 3] = 0;
2440           }
2441         break;
2442         case 4: /*greyscale with alpha*/
2443           for(i = 0; i < numpixels; i++)
2444           {
2445             out[OUT_BYTES * i + 0] = out[OUT_BYTES * i + 1] = out[OUT_BYTES * i + 2] = in[4 * i]; /*most significant byte*/
2446             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = in[4 * i + 2];
2447           }
2448         break;
2449         case 6: /*RGB with alpha*/
2450           for(i = 0; i < numpixels; i++)
2451           {
2452             for(c = 0; c < OUT_BYTES; c++) out[OUT_BYTES * i + c] = in[8 * i + 2 * c];
2453           }
2454           break;
2455         default: break;
2456       }
2457     }
2458     else /*infoIn->bitDepth is less than 8 bit per channel*/
2459     {
2460       switch(infoIn->colorType)
2461       {
2462         case 0: /*greyscale color*/
2463           for(i = 0; i < numpixels; i++)
2464           {
2465             unsigned value = readBitsFromReversedStream(&bp, in, infoIn->bitDepth);
2466             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = 255;
2467             if(OUT_ALPHA && infoIn->key_defined && value && ((1U << infoIn->bitDepth) - 1U) == infoIn->key_r && ((1U << infoIn->bitDepth) - 1U)) out[OUT_BYTES * i + 3] = 0;
2468             value = (value * 255) / ((1 << infoIn->bitDepth) - 1); /*scale value from 0 to 255*/
2469             out[OUT_BYTES * i + 0] = out[OUT_BYTES * i + 1] = out[OUT_BYTES * i + 2] = (unsigned char)(value);
2470           }
2471         break;
2472         case 3: /*indexed color (palette)*/
2473           for(i = 0; i < numpixels; i++)
2474           {
2475             unsigned value = readBitsFromReversedStream(&bp, in, infoIn->bitDepth);
2476             if(OUT_ALPHA) out[OUT_BYTES * i + 3] = 255;
2477             if(value >= infoIn->palettesize) return 47;
2478             for(c = 0; c < OUT_BYTES; c++) out[OUT_BYTES * i + c] = infoIn->palette[4 * value + c]; /*get rgb colors from the palette*/
2479           }
2480         break;
2481         default: break;
2482       }
2483     }
2484   }
2485   else if(LodePNG_InfoColor_isGreyscaleType(infoOut) && infoOut->bitDepth == 8) /*conversion from greyscale to greyscale*/
2486   {
2487     if(!LodePNG_InfoColor_isGreyscaleType(infoIn)) return 62;
2488     if(infoIn->bitDepth == 8)
2489     {
2490       switch(infoIn->colorType)
2491       {
2492         case 0: /*greyscale color*/
2493           for(i = 0; i < numpixels; i++)
2494           {
2495             if(OUT_ALPHA) out[OUT_BYTES * i + 1] = 255;
2496             out[OUT_BYTES * i] = in[i];
2497             if(OUT_ALPHA && infoIn->key_defined && in[i] == infoIn->key_r) out[OUT_BYTES * i + 1] = 0;
2498           }
2499         break;
2500         case 4: /*greyscale with alpha*/
2501           for(i = 0; i < numpixels; i++)
2502           {
2503             out[OUT_BYTES * i + 0] = in[2 * i + 0];
2504             if(OUT_ALPHA) out[OUT_BYTES * i + 1] = in[2 * i + 1];
2505           }
2506         break;
2507         default: return 31;
2508       }
2509     }
2510     else if(infoIn->bitDepth == 16)
2511     {
2512       switch(infoIn->colorType)
2513       {
2514         case 0: /*greyscale color*/
2515           for(i = 0; i < numpixels; i++)
2516           {
2517             if(OUT_ALPHA) out[OUT_BYTES * i + 1] = 255;
2518             out[OUT_BYTES * i] = in[2 * i];
2519             if(OUT_ALPHA && infoIn->key_defined && 256U * in[i] + in[i + 1] == infoIn->key_r) out[OUT_BYTES * i + 1] = 0;
2520           }
2521         break;
2522         case 4: /*greyscale with alpha*/
2523           for(i = 0; i < numpixels; i++)
2524           {
2525             out[OUT_BYTES * i] = in[4 * i]; /*most significant byte*/
2526             if(OUT_ALPHA) out[OUT_BYTES * i + 1] = in[4 * i + 2]; /*most significant byte*/
2527           }
2528         break;
2529         default: return 31;
2530       }
2531     }
2532     else /*infoIn->bitDepth is less than 8 bit per channel*/
2533     {
2534       if(infoIn->colorType != 0) return 31; /*colorType 0 is the only greyscale type with < 8 bits per channel*/
2535       for(i = 0; i < numpixels; i++)
2536       {
2537         unsigned value = readBitsFromReversedStream(&bp, in, infoIn->bitDepth);
2538         if(OUT_ALPHA) out[OUT_BYTES * i + 1] = 255;
2539         if(OUT_ALPHA && infoIn->key_defined && value && ((1U << infoIn->bitDepth) - 1U) == infoIn->key_r && ((1U << infoIn->bitDepth) - 1U)) out[OUT_BYTES * i + 1] = 0;
2540         value = (value * 255) / ((1 << infoIn->bitDepth) - 1); /*scale value from 0 to 255*/
2541         out[OUT_BYTES * i] = (unsigned char)(value);
2542       }
2543     }
2544   }
2545   else return 59;
2546
2547   return 0;
2548 }
2549
2550 /*Paeth predicter, used by PNG filter type 4*/
2551 static int paethPredictor(int a, int b, int c)
2552 {
2553   int p = a + b - c;
2554   int pa = p > a ? p - a : a - p;
2555   int pb = p > b ? p - b : b - p;
2556   int pc = p > c ? p - c : c - p;
2557
2558   if(pa <= pb && pa <= pc) return a;
2559   else if(pb <= pc) return b;
2560   else return c;
2561 }
2562
2563 /*shared values used by multiple Adam7 related functions*/
2564
2565 static const unsigned ADAM7_IX[7] = { 0, 4, 0, 2, 0, 1, 0 }; /*x start values*/
2566 static const unsigned ADAM7_IY[7] = { 0, 0, 4, 0, 2, 0, 1 }; /*y start values*/
2567 static const unsigned ADAM7_DX[7] = { 8, 8, 4, 4, 2, 2, 1 }; /*x delta values*/
2568 static const unsigned ADAM7_DY[7] = { 8, 8, 8, 4, 4, 2, 2 }; /*y delta values*/
2569
2570 static void Adam7_getpassvalues(unsigned passw[7], unsigned passh[7], size_t filter_passstart[8], size_t padded_passstart[8], size_t passstart[8], unsigned w, unsigned h, unsigned bpp)
2571 {
2572   /*the passstart values have 8 values: the 8th one actually indicates the byte after the end of the 7th (= last) pass*/
2573   unsigned i;
2574
2575   /*calculate width and height in pixels of each pass*/
2576   for(i = 0; i < 7; i++)
2577   {
2578     passw[i] = (w + ADAM7_DX[i] - ADAM7_IX[i] - 1) / ADAM7_DX[i];
2579     passh[i] = (h + ADAM7_DY[i] - ADAM7_IY[i] - 1) / ADAM7_DY[i];
2580     if(passw[i] == 0) passh[i] = 0;
2581     if(passh[i] == 0) passw[i] = 0;
2582   }
2583
2584   filter_passstart[0] = padded_passstart[0] = passstart[0] = 0;
2585   for(i = 0; i < 7; i++)
2586   {
2587     filter_passstart[i + 1] = filter_passstart[i] + ((passw[i] && passh[i]) ? passh[i] * (1 + (passw[i] * bpp + 7) / 8) : 0); /*if passw[i] is 0, it's 0 bytes, not 1 (no filtertype-byte)*/
2588     padded_passstart[i + 1] = padded_passstart[i] + passh[i] * ((passw[i] * bpp + 7) / 8); /*bits padded if needed to fill full byte at end of each scanline*/
2589     passstart[i + 1] = passstart[i] + (passh[i] * passw[i] * bpp + 7) / 8; /*only padded at end of reduced image*/
2590   }
2591 }
2592
2593 #ifdef LODEPNG_COMPILE_DECODER
2594
2595 /* ////////////////////////////////////////////////////////////////////////// */
2596 /* / PNG Decoder                                                            / */
2597 /* ////////////////////////////////////////////////////////////////////////// */
2598
2599 /*read the information from the header and store it in the LodePNG_Info. return value is error*/
2600 void LodePNG_inspect(LodePNG_Decoder* decoder, const unsigned char* in, size_t inlength)
2601 {
2602   if(inlength == 0 || in == 0) { decoder->error = 48; return; } /*the given data is empty*/
2603   if(inlength < 29) { decoder->error = 27; return; } /*error: the data length is smaller than the length of the header*/
2604
2605   /*when decoding a new PNG image, make sure all parameters created after previous decoding are reset*/
2606   LodePNG_InfoPng_cleanup(&decoder->infoPng);
2607   LodePNG_InfoPng_init(&decoder->infoPng);
2608   decoder->error = 0;
2609
2610   if(in[0] != 137 || in[1] != 80 || in[2] != 78 || in[3] != 71 || in[4] != 13 || in[5] != 10 || in[6] != 26 || in[7] != 10) { decoder->error = 28; return; } /*error: the first 8 bytes are not the correct PNG signature*/
2611   if(in[12] != 'I' || in[13] != 'H' || in[14] != 'D' || in[15] != 'R') { decoder->error = 29; return; } /*error: it doesn't start with a IHDR chunk!*/
2612
2613   /*read the values given in the header*/
2614   decoder->infoPng.width = LodePNG_read32bitInt(&in[16]);
2615   decoder->infoPng.height = LodePNG_read32bitInt(&in[20]);
2616   decoder->infoPng.color.bitDepth = in[24];
2617   decoder->infoPng.color.colorType = in[25];
2618   decoder->infoPng.compressionMethod = in[26];
2619   decoder->infoPng.filterMethod = in[27];
2620   decoder->infoPng.interlaceMethod = in[28];
2621
2622   if(!decoder->settings.ignoreCrc)
2623   {
2624     unsigned CRC = LodePNG_read32bitInt(&in[29]);
2625     unsigned checksum = Crc32_crc(&in[12], 17);
2626     if(CRC != checksum) { decoder->error = 57; return; }
2627   }
2628
2629   if(decoder->infoPng.compressionMethod != 0) { decoder->error = 32; return; } /*error: only compression method 0 is allowed in the specification*/
2630   if(decoder->infoPng.filterMethod != 0)      { decoder->error = 33; return; } /*error: only filter method 0 is allowed in the specification*/
2631   if(decoder->infoPng.interlaceMethod > 1)    { decoder->error = 34; return; } /*error: only interlace methods 0 and 1 exist in the specification*/
2632
2633   decoder->error = checkColorValidity(decoder->infoPng.color.colorType, decoder->infoPng.color.bitDepth);
2634 }
2635
2636 static unsigned unfilterScanline(unsigned char* recon, const unsigned char* scanline, const unsigned char* precon, size_t bytewidth, unsigned char filterType, size_t length)
2637 {
2638   /*
2639   For PNG filter method 0
2640   unfilter a PNG image scanline by scanline. when the pixels are smaller than 1 byte, the filter works byte per byte (bytewidth = 1)
2641   precon is the previous unfiltered scanline, recon the result, scanline the current one
2642   the incoming scanlines do NOT include the filtertype byte, that one is given in the parameter filterType instead
2643   recon and scanline MAY be the same memory address! precon must be disjoint.
2644   */
2645
2646   size_t i;
2647   switch(filterType)
2648   {
2649     case 0:
2650       for(i = 0; i < length; i++) recon[i] = scanline[i];
2651       break;
2652     case 1:
2653       for(i =         0; i < bytewidth; i++) recon[i] = scanline[i];
2654       for(i = bytewidth; i <    length; i++) recon[i] = scanline[i] + recon[i - bytewidth];
2655       break;
2656     case 2:
2657       if(precon) for(i = 0; i < length; i++) recon[i] = scanline[i] + precon[i];
2658       else       for(i = 0; i < length; i++) recon[i] = scanline[i];
2659       break;
2660     case 3:
2661       if(precon)
2662       {
2663         for(i =         0; i < bytewidth; i++) recon[i] = scanline[i] + precon[i] / 2;
2664         for(i = bytewidth; i <    length; i++) recon[i] = scanline[i] + ((recon[i - bytewidth] + precon[i]) / 2);
2665       }
2666       else
2667       {
2668         for(i =         0; i < bytewidth; i++) recon[i] = scanline[i];
2669         for(i = bytewidth; i <    length; i++) recon[i] = scanline[i] + recon[i - bytewidth] / 2;
2670       }
2671       break;
2672     case 4:
2673       if(precon)
2674       {
2675         for(i =         0; i < bytewidth; i++) recon[i] = (unsigned char)(scanline[i] + paethPredictor(0, precon[i], 0));
2676         for(i = bytewidth; i <    length; i++) recon[i] = (unsigned char)(scanline[i] + paethPredictor(recon[i - bytewidth], precon[i], precon[i - bytewidth]));
2677       }
2678       else
2679       {
2680         for(i =         0; i < bytewidth; i++) recon[i] = scanline[i];
2681         for(i = bytewidth; i <    length; i++) recon[i] = (unsigned char)(scanline[i] + paethPredictor(recon[i - bytewidth], 0, 0));
2682       }
2683       break;
2684     default: return 36; /*error: unexisting filter type given*/
2685   }
2686   return 0;
2687 }
2688
2689 static unsigned unfilter(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
2690 {
2691   /*
2692   For PNG filter method 0
2693   this function unfilters a single image (e.g. without interlacing this is called once, with Adam7 it's called 7 times)
2694   out must have enough bytes allocated already, in must have the scanlines + 1 filtertype byte per scanline
2695   w and h are image dimensions or dimensions of reduced image, bpp is bits per pixel
2696   in and out are allowed to be the same memory address!
2697   */
2698
2699   unsigned y;
2700   unsigned char* prevline = 0;
2701
2702   size_t bytewidth = (bpp + 7) / 8; /*bytewidth is used for filtering, is 1 when bpp < 8, number of bytes per pixel otherwise*/
2703   size_t linebytes = (w * bpp + 7) / 8;
2704
2705   for(y = 0; y < h; y++)
2706   {
2707     size_t outindex = linebytes * y;
2708     size_t inindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
2709     unsigned char filterType = in[inindex];
2710
2711     unsigned error = unfilterScanline(&out[outindex], &in[inindex + 1], prevline, bytewidth, filterType, linebytes);
2712     if(error) return error;
2713
2714     prevline = &out[outindex];
2715   }
2716
2717   return 0;
2718 }
2719
2720 static void Adam7_deinterlace(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
2721 {
2722   /*Note: this function works on image buffers WITHOUT padding bits at end of scanlines with non-multiple-of-8 bit amounts, only between reduced images is padding
2723   out must be big enough AND must be 0 everywhere if bpp < 8 in the current implementation (because that's likely a little bit faster)*/
2724   unsigned passw[7], passh[7]; size_t filter_passstart[8], padded_passstart[8], passstart[8];
2725   unsigned i;
2726
2727   Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
2728
2729   if(bpp >= 8)
2730   {
2731     for(i = 0; i < 7; i++)
2732     {
2733       unsigned x, y, b;
2734       size_t bytewidth = bpp / 8;
2735       for(y = 0; y < passh[i]; y++)
2736       for(x = 0; x < passw[i]; x++)
2737       {
2738         size_t pixelinstart = passstart[i] + (y * passw[i] + x) * bytewidth;
2739         size_t pixeloutstart = ((ADAM7_IY[i] + y * ADAM7_DY[i]) * w + ADAM7_IX[i] + x * ADAM7_DX[i]) * bytewidth;
2740         for(b = 0; b < bytewidth; b++)
2741         {
2742           out[pixeloutstart + b] = in[pixelinstart + b];
2743         }
2744       }
2745     }
2746   }
2747   else /*bpp < 8: Adam7 with pixels < 8 bit is a bit trickier: with bit pointers*/
2748   {
2749     for(i = 0; i < 7; i++)
2750     {
2751       unsigned x, y, b;
2752       unsigned ilinebits = bpp * passw[i];
2753       unsigned olinebits = bpp * w;
2754       size_t obp, ibp; /*bit pointers (for out and in buffer)*/
2755       for(y = 0; y < passh[i]; y++)
2756       for(x = 0; x < passw[i]; x++)
2757       {
2758         ibp = (8 * passstart[i]) + (y * ilinebits + x * bpp);
2759         obp = (ADAM7_IY[i] + y * ADAM7_DY[i]) * olinebits + (ADAM7_IX[i] + x * ADAM7_DX[i]) * bpp;
2760         for(b = 0; b < bpp; b++)
2761         {
2762           unsigned char bit = readBitFromReversedStream(&ibp, in);
2763           setBitOfReversedStream0(&obp, out, bit); /*note that this function assumes the out buffer is completely 0, use setBitOfReversedStream otherwise*/
2764         }
2765       }
2766     }
2767   }
2768 }
2769
2770 static void removePaddingBits(unsigned char* out, const unsigned char* in, size_t olinebits, size_t ilinebits, unsigned h)
2771 {
2772   /*
2773   After filtering there are still padding bits if scanlines have non multiple of 8 bit amounts. They need to be removed (except at last scanline of (Adam7-reduced) image) before working with pure image buffers for the Adam7 code, the color convert code and the output to the user.
2774   in and out are allowed to be the same buffer, in may also be higher but still overlapping; in must have >= ilinebits*h bits, out must have >= olinebits*h bits, olinebits must be <= ilinebits
2775   also used to move bits after earlier such operations happened, e.g. in a sequence of reduced images from Adam7
2776   only useful if (ilinebits - olinebits) is a value in the range 1..7
2777   */
2778   unsigned y;
2779   size_t diff = ilinebits - olinebits;
2780   size_t obp = 0, ibp = 0; /*bit pointers*/
2781   for(y = 0; y < h; y++)
2782   {
2783     size_t x;
2784     for(x = 0; x < olinebits; x++)
2785     {
2786       unsigned char bit = readBitFromReversedStream(&ibp, in);
2787       setBitOfReversedStream(&obp, out, bit);
2788     }
2789     ibp += diff;
2790   }
2791 }
2792
2793 /*out must be buffer big enough to contain full image, and in must contain the full decompressed data from the IDAT chunks*/
2794 static unsigned postProcessScanlines(unsigned char* out, unsigned char* in, const LodePNG_InfoPng* infoPng) /*return value is error*/
2795 {
2796   /*
2797   This function converts the filtered-padded-interlaced data into pure 2D image buffer with the PNG's colortype. Steps:
2798   *) if no Adam7: 1) unfilter 2) remove padding bits (= posible extra bits per scanline if bpp < 8)
2799   *) if adam7: 1) 7x unfilter 2) 7x remove padding bits 3) Adam7_deinterlace
2800   NOTE: the in buffer will be overwritten with intermediate data!
2801   */
2802   unsigned bpp = LodePNG_InfoColor_getBpp(&infoPng->color);
2803   unsigned w = infoPng->width;
2804   unsigned h = infoPng->height;
2805   unsigned error = 0;
2806   if(bpp == 0) return 31; /*error: invalid colortype*/
2807
2808   if(infoPng->interlaceMethod == 0)
2809   {
2810     if(bpp < 8 && w * bpp != ((w * bpp + 7) / 8) * 8)
2811     {
2812       error = unfilter(in, in, w, h, bpp);
2813       if(error) return error;
2814       removePaddingBits(out, in, w * bpp, ((w * bpp + 7) / 8) * 8, h);
2815     }
2816     else error = unfilter(out, in, w, h, bpp); /*we can immediatly filter into the out buffer, no other steps needed*/
2817   }
2818   else /*interlaceMethod is 1 (Adam7)*/
2819   {
2820     unsigned passw[7], passh[7]; size_t filter_passstart[8], padded_passstart[8], passstart[8];
2821     unsigned i;
2822
2823     Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
2824
2825     for(i = 0; i < 7; i++)
2826     {
2827       error = unfilter(&in[padded_passstart[i]], &in[filter_passstart[i]], passw[i], passh[i], bpp);
2828       if(error) return error;
2829       if(bpp < 8) /*TODO: possible efficiency improvement: if in this reduced image the bits fit nicely in 1 scanline, move bytes instead of bits or move not at all*/
2830       {
2831         /*remove padding bits in scanlines; after this there still may be padding bits between the different reduced images: each reduced image still starts nicely at a byte*/
2832         removePaddingBits(&in[passstart[i]], &in[padded_passstart[i]], passw[i] * bpp, ((passw[i] * bpp + 7) / 8) * 8, passh[i]);
2833       }
2834     }
2835
2836     Adam7_deinterlace(out, in, w, h, bpp);
2837   }
2838
2839   return error;
2840 }
2841
2842 /*read a PNG, the result will be in the same color type as the PNG (hence "generic")*/
2843 static void decodeGeneric(LodePNG_Decoder* decoder, unsigned char** out, size_t* outsize, const unsigned char* in, size_t size)
2844 {
2845   unsigned char IEND = 0;
2846   const unsigned char* chunk;
2847   size_t i;
2848   ucvector idat; /*the data from idat chunks*/
2849
2850   /*for unknown chunk order*/
2851   unsigned unknown = 0;
2852   unsigned critical_pos = 1; /*1 = after IHDR, 2 = after PLTE, 3 = after IDAT*/
2853
2854   /*provide some proper output values if error will happen*/
2855   *out = 0;
2856   *outsize = 0;
2857
2858   if(size == 0 || in == 0) { decoder->error = 48; return; } /*the given data is empty*/
2859
2860   LodePNG_inspect(decoder, in, size); /*reads header and resets other parameters in decoder->infoPng*/
2861   if(decoder->error) return;
2862
2863   ucvector_init(&idat);
2864
2865   chunk = &in[33]; /*first byte of the first chunk after the header*/
2866
2867   while(!IEND) /*loop through the chunks, ignoring unknown chunks and stopping at IEND chunk. IDAT data is put at the start of the in buffer*/
2868   {
2869     unsigned chunkLength;
2870     const unsigned char* data; /*the data in the chunk*/
2871
2872     if((size_t)((chunk - in) + 12) > size || chunk < in) { decoder->error = 30; break; } /*error: size of the in buffer too small to contain next chunk*/
2873     chunkLength = LodePNG_chunk_length(chunk); /*length of the data of the chunk, excluding the length bytes, chunk type and CRC bytes*/
2874     if(chunkLength > 2147483647) { decoder->error = 63; break; }
2875     if((size_t)((chunk - in) + chunkLength + 12) > size || (chunk + chunkLength + 12) < in) { decoder->error = 35; break; } /*error: size of the in buffer too small to contain next chunk*/
2876     data = LodePNG_chunk_data_const(chunk);
2877
2878     /*IDAT chunk, containing compressed image data*/
2879     if(LodePNG_chunk_type_equals(chunk, "IDAT"))
2880     {
2881       size_t oldsize = idat.size;
2882       if(!ucvector_resize(&idat, oldsize + chunkLength)) { decoder->error = 9936; break; }
2883       for(i = 0; i < chunkLength; i++) idat.data[oldsize + i] = data[i];
2884       critical_pos = 3;
2885     }
2886     /*IEND chunk*/
2887     else if(LodePNG_chunk_type_equals(chunk, "IEND"))
2888     {
2889       IEND = 1;
2890     }
2891     /*palette chunk (PLTE)*/
2892     else if(LodePNG_chunk_type_equals(chunk, "PLTE"))
2893     {
2894       unsigned pos = 0;
2895       if(decoder->infoPng.color.palette) free(decoder->infoPng.color.palette);
2896       decoder->infoPng.color.palettesize = chunkLength / 3;
2897       decoder->infoPng.color.palette = (unsigned char*)malloc(4 * decoder->infoPng.color.palettesize);
2898       if(!decoder->infoPng.color.palette && decoder->infoPng.color.palettesize) { decoder->error = 9937; break; }
2899       if(!decoder->infoPng.color.palette) decoder->infoPng.color.palettesize = 0; /*malloc failed...*/
2900       if(decoder->infoPng.color.palettesize > 256) { decoder->error = 38; break; } /*error: palette too big*/
2901       for(i = 0; i < decoder->infoPng.color.palettesize; i++)
2902       {
2903         decoder->infoPng.color.palette[4 * i + 0] = data[pos++]; /*R*/
2904         decoder->infoPng.color.palette[4 * i + 1] = data[pos++]; /*G*/
2905         decoder->infoPng.color.palette[4 * i + 2] = data[pos++]; /*B*/
2906         decoder->infoPng.color.palette[4 * i + 3] = 255; /*alpha*/
2907       }
2908       critical_pos = 2;
2909     }
2910     /*palette transparency chunk (tRNS)*/
2911     else if(LodePNG_chunk_type_equals(chunk, "tRNS"))
2912     {
2913       if(decoder->infoPng.color.colorType == 3)
2914       {
2915         if(chunkLength > decoder->infoPng.color.palettesize) { decoder->error = 39; break; } /*error: more alpha values given than there are palette entries*/
2916         for(i = 0; i < chunkLength; i++) decoder->infoPng.color.palette[4 * i + 3] = data[i];
2917       }
2918       else if(decoder->infoPng.color.colorType == 0)
2919       {
2920         if(chunkLength != 2) { decoder->error = 40; break; } /*error: this chunk must be 2 bytes for greyscale image*/
2921         decoder->infoPng.color.key_defined = 1;
2922         decoder->infoPng.color.key_r = decoder->infoPng.color.key_g = decoder->infoPng.color.key_b = 256 * data[0] + data[1];
2923       }
2924       else if(decoder->infoPng.color.colorType == 2)
2925       {
2926         if(chunkLength != 6) { decoder->error = 41; break; } /*error: this chunk must be 6 bytes for RGB image*/
2927         decoder->infoPng.color.key_defined = 1;
2928         decoder->infoPng.color.key_r = 256 * data[0] + data[1];
2929         decoder->infoPng.color.key_g = 256 * data[2] + data[3];
2930         decoder->infoPng.color.key_b = 256 * data[4] + data[5];
2931       }
2932       else { decoder->error = 42; break; } /*error: tRNS chunk not allowed for other color models*/
2933     }
2934 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2935     /*background color chunk (bKGD)*/
2936     else if(LodePNG_chunk_type_equals(chunk, "bKGD"))
2937     {
2938       if(decoder->infoPng.color.colorType == 3)
2939       {
2940         if(chunkLength != 1) { decoder->error = 43; break; } /*error: this chunk must be 1 byte for indexed color image*/
2941         decoder->infoPng.background_defined = 1;
2942         decoder->infoPng.background_r = decoder->infoPng.background_g = decoder->infoPng.background_g = data[0];
2943       }
2944       else if(decoder->infoPng.color.colorType == 0 || decoder->infoPng.color.colorType == 4)
2945       {
2946         if(chunkLength != 2) { decoder->error = 44; break; } /*error: this chunk must be 2 bytes for greyscale image*/
2947         decoder->infoPng.background_defined = 1;
2948         decoder->infoPng.background_r = decoder->infoPng.background_g = decoder->infoPng.background_b = 256 * data[0] + data[1];
2949       }
2950       else if(decoder->infoPng.color.colorType == 2 || decoder->infoPng.color.colorType == 6)
2951       {
2952         if(chunkLength != 6) { decoder->error = 45; break; } /*error: this chunk must be 6 bytes for greyscale image*/
2953         decoder->infoPng.background_defined = 1;
2954         decoder->infoPng.background_r = 256 * data[0] + data[1];
2955         decoder->infoPng.background_g = 256 * data[2] + data[3];
2956         decoder->infoPng.background_b = 256 * data[4] + data[5];
2957       }
2958     }
2959     /*text chunk (tEXt)*/
2960     else if(LodePNG_chunk_type_equals(chunk, "tEXt"))
2961     {
2962       if(decoder->settings.readTextChunks)
2963       {
2964         char *key = 0, *str = 0;
2965
2966         while(!decoder->error) /*not really a while loop, only used to break on error*/
2967         {
2968           unsigned length, string2_begin;
2969
2970           for(length = 0; length < chunkLength && data[length] != 0; length++) ;
2971           if(length + 1 >= chunkLength) { decoder->error = 75; break; }
2972           key = (char*)malloc(length + 1);
2973           if(!key) { decoder->error = 9938; break; }
2974           key[length] = 0;
2975           for(i = 0; i < length; i++) key[i] = data[i];
2976
2977           string2_begin = length + 1;
2978           if(string2_begin > chunkLength)  { decoder->error = 75; break; }
2979           length = chunkLength - string2_begin;
2980           str = (char*)malloc(length + 1);
2981           if(!str) { decoder->error = 9939; break; }
2982           str[length] = 0;
2983           for(i = 0; i < length; i++) str[i] = data[string2_begin + i];
2984
2985           decoder->error = LodePNG_Text_add(&decoder->infoPng.text, key, str);
2986
2987           break;
2988         }
2989
2990         free(key);
2991         free(str);
2992       }
2993     }
2994     /*compressed text chunk (zTXt)*/
2995     else if(LodePNG_chunk_type_equals(chunk, "zTXt"))
2996     {
2997       if(decoder->settings.readTextChunks)
2998       {
2999         unsigned length, string2_begin;
3000         char *key = 0;
3001         ucvector decoded;
3002
3003         ucvector_init(&decoded);
3004
3005         while(!decoder->error) /*not really a while loop, only used to break on error*/
3006         {
3007           for(length = 0; length < chunkLength && data[length] != 0; length++) ;
3008           if(length + 2 >= chunkLength) { decoder->error = 75; break; }
3009           key = (char*)malloc(length + 1);
3010           if(!key) { decoder->error = 9940; break; }
3011           key[length] = 0;
3012           for(i = 0; i < length; i++) key[i] = data[i];
3013
3014           if(data[length + 1] != 0) { decoder->error = 72; break; } /*the 0 byte indicating compression must be 0*/
3015
3016           string2_begin = length + 2;
3017           if(string2_begin > chunkLength)  { decoder->error = 75; break; }
3018           length = chunkLength - string2_begin;
3019           decoder->error = LodePNG_decompress(&decoded.data, &decoded.size, (unsigned char*)(&data[string2_begin]), length, &decoder->settings.zlibsettings);
3020           if(decoder->error) break;
3021           ucvector_push_back(&decoded, 0);
3022
3023           decoder->error = LodePNG_Text_add(&decoder->infoPng.text, key, (char*)decoded.data);
3024
3025           break;
3026         }
3027
3028         free(key);
3029         ucvector_cleanup(&decoded);
3030         if(decoder->error) break;
3031       }
3032     }
3033     /*international text chunk (iTXt)*/
3034     else if(LodePNG_chunk_type_equals(chunk, "iTXt"))
3035     {
3036       if(decoder->settings.readTextChunks)
3037       {
3038         unsigned length, begin, compressed;
3039         char *key = 0, *langtag = 0, *transkey = 0;
3040         ucvector decoded;
3041         ucvector_init(&decoded);
3042
3043         while(!decoder->error) /*not really a while loop, only used to break on error*/
3044         {
3045           if(chunkLength < 5) { decoder->error = 76; break; }
3046           for(length = 0; length < chunkLength && data[length] != 0; length++) ;
3047           if(length + 2 >= chunkLength) { decoder->error = 75; break; }
3048           key = (char*)malloc(length + 1);
3049           if(!key) { decoder->error = 9941; break; }
3050           key[length] = 0;
3051           for(i = 0; i < length; i++) key[i] = data[i];
3052
3053           compressed = data[length + 1];
3054           if(data[length + 2] != 0) { decoder->error = 72; break; } /*the 0 byte indicating compression must be 0*/
3055
3056           begin = length + 3;
3057           length = 0;
3058           for(i = begin; i < chunkLength && data[i] != 0; i++) length++;
3059           if(begin + length + 1 >= chunkLength) { decoder->error = 75; break; }
3060           langtag = (char*)malloc(length + 1);
3061           if(!langtag) { decoder->error = 9942; break; }
3062           langtag[length] = 0;
3063           for(i = 0; i < length; i++) langtag[i] = data[begin + i];
3064
3065           begin += length + 1;
3066           length = 0;
3067           for(i = begin; i < chunkLength && data[i] != 0; i++) length++;
3068           if(begin + length + 1 >= chunkLength) { decoder->error = 75; break; }
3069           transkey = (char*)malloc(length + 1);
3070           if(!transkey) { decoder->error = 9943; break; }
3071           transkey[length] = 0;
3072           for(i = 0; i < length; i++) transkey[i] = data[begin + i];
3073
3074           begin += length + 1;
3075           if(begin > chunkLength)  { decoder->error = 75; break; }
3076           length = chunkLength - begin;
3077
3078           if(compressed)
3079           {
3080             decoder->error = LodePNG_decompress(&decoded.data, &decoded.size, (unsigned char*)(&data[begin]), length, &decoder->settings.zlibsettings);
3081             if(decoder->error) break;
3082             ucvector_push_back(&decoded, 0);
3083           }
3084           else
3085           {
3086             if(!ucvector_resize(&decoded, length + 1)) { decoder->error = 9944; break; }
3087             decoded.data[length] = 0;
3088             for(i = 0; i < length; i++) decoded.data[i] = data[begin + i];
3089           }
3090
3091           decoder->error = LodePNG_IText_add(&decoder->infoPng.itext, key, langtag, transkey, (char*)decoded.data);
3092
3093           break;
3094         }
3095
3096         free(key);
3097         free(langtag);
3098         free(transkey);
3099         ucvector_cleanup(&decoded);
3100         if(decoder->error) break;
3101       }
3102     }
3103     else if(LodePNG_chunk_type_equals(chunk, "tIME"))
3104     {
3105       if(chunkLength != 7) { decoder->error = 73; break; }
3106       decoder->infoPng.time_defined = 1;
3107       decoder->infoPng.time.year = 256 * data[0] + data[+ 1];
3108       decoder->infoPng.time.month = data[2];
3109       decoder->infoPng.time.day = data[3];
3110       decoder->infoPng.time.hour = data[4];
3111       decoder->infoPng.time.minute = data[5];
3112       decoder->infoPng.time.second = data[6];
3113     }
3114     else if(LodePNG_chunk_type_equals(chunk, "pHYs"))
3115     {
3116       if(chunkLength != 9) { decoder->error = 74; break; }
3117       decoder->infoPng.phys_defined = 1;
3118       decoder->infoPng.phys_x = 16777216 * data[0] + 65536 * data[1] + 256 * data[2] + data[3];
3119       decoder->infoPng.phys_y = 16777216 * data[4] + 65536 * data[5] + 256 * data[6] + data[7];
3120       decoder->infoPng.phys_unit = data[8];
3121     }
3122 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
3123     else /*it's not an implemented chunk type, so ignore it: skip over the data*/
3124     {
3125       if(LodePNG_chunk_critical(chunk)) { decoder->error = 69; break; } /*error: unknown critical chunk (5th bit of first byte of chunk type is 0)*/
3126       unknown = 1;
3127 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
3128       if(decoder->settings.rememberUnknownChunks)
3129       {
3130         LodePNG_UnknownChunks* unknown = &decoder->infoPng.unknown_chunks;
3131         decoder->error = LodePNG_append_chunk(&unknown->data[critical_pos - 1], &unknown->datasize[critical_pos - 1], chunk);
3132         if(decoder->error) break;
3133       }
3134 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
3135     }
3136
3137     if(!decoder->settings.ignoreCrc && !unknown) /*check CRC if wanted, only on known chunk types*/
3138     {
3139       if(LodePNG_chunk_check_crc(chunk)) { decoder->error = 57; break; }
3140     }
3141
3142     if(!IEND) chunk = LodePNG_chunk_next_const(chunk);
3143   }
3144
3145   if(!decoder->error)
3146   {
3147     ucvector scanlines;
3148     ucvector_init(&scanlines);
3149     if(!ucvector_resize(&scanlines, ((decoder->infoPng.width * (decoder->infoPng.height * LodePNG_InfoColor_getBpp(&decoder->infoPng.color) + 7)) / 8) + decoder->infoPng.height)) decoder->error = 9945; /*maximum final image length is already reserved in the vector's length - this is not really necessary*/
3150     if(!decoder->error) decoder->error = LodePNG_decompress(&scanlines.data, &scanlines.size, idat.data, idat.size, &decoder->settings.zlibsettings); /*decompress with the Zlib decompressor*/
3151
3152     if(!decoder->error)
3153     {
3154       ucvector outv;
3155       ucvector_init(&outv);
3156       if(!ucvector_resizev(&outv, (decoder->infoPng.height * decoder->infoPng.width * LodePNG_InfoColor_getBpp(&decoder->infoPng.color) + 7) / 8, 0)) decoder->error = 9946;
3157       if(!decoder->error) decoder->error = postProcessScanlines(outv.data, scanlines.data, &decoder->infoPng);
3158       *out = outv.data;
3159       *outsize = outv.size;
3160     }
3161     ucvector_cleanup(&scanlines);
3162   }
3163
3164   ucvector_cleanup(&idat);
3165 }
3166
3167 void LodePNG_decode(LodePNG_Decoder* decoder, unsigned char** out, size_t* outsize, const unsigned char* in, size_t insize)
3168 {
3169   *out = 0;
3170   *outsize = 0;
3171   decodeGeneric(decoder, out, outsize, in, insize);
3172   if(decoder->error) return;
3173   if(!decoder->settings.color_convert || LodePNG_InfoColor_equal(&decoder->infoRaw.color, &decoder->infoPng.color))
3174   {
3175     /*same color type, no copying or converting of data needed*/
3176     /*store the infoPng color settings on the infoRaw so that the infoRaw still reflects what colorType
3177     the raw image has to the end user*/
3178     if(!decoder->settings.color_convert)
3179     {
3180       decoder->error = LodePNG_InfoColor_copy(&decoder->infoRaw.color, &decoder->infoPng.color);
3181       if(decoder->error) return;
3182     }
3183   }
3184   else
3185   {
3186     /*color conversion needed; sort of copy of the data*/
3187     unsigned char* data = *out;
3188
3189     /*TODO: check if this works according to the statement in the documentation: "The converter can convert from greyscale input color type, to 8-bit greyscale or greyscale with alpha"*/
3190     if(!(decoder->infoRaw.color.colorType == 2 || decoder->infoRaw.color.colorType == 6) && !(decoder->infoRaw.color.bitDepth == 8)) { decoder->error = 56; return; }
3191
3192     *outsize = (decoder->infoPng.width * decoder->infoPng.height * LodePNG_InfoColor_getBpp(&decoder->infoRaw.color) + 7) / 8;
3193     *out = (unsigned char*)malloc(*outsize);
3194     if(!(*out))
3195     {
3196       decoder->error = 9947;
3197       *outsize = 0;
3198     }
3199     else decoder->error = LodePNG_convert(*out, data, &decoder->infoRaw.color, &decoder->infoPng.color, decoder->infoPng.width, decoder->infoPng.height);
3200     free(data);
3201   }
3202 }
3203
3204 unsigned LodePNG_decode32(unsigned char** out, unsigned* w, unsigned* h, const unsigned char* in, size_t insize)
3205 {
3206   unsigned error;
3207   size_t dummy_size;
3208   LodePNG_Decoder decoder;
3209   LodePNG_Decoder_init(&decoder);
3210   LodePNG_decode(&decoder, out, &dummy_size, in, insize);
3211   error = decoder.error;
3212   *w = decoder.infoPng.width;
3213   *h = decoder.infoPng.height;
3214   LodePNG_Decoder_cleanup(&decoder);
3215   return error;
3216 }
3217
3218 #ifdef LODEPNG_COMPILE_DISK
3219 unsigned LodePNG_decode32f(unsigned char** out, unsigned* w, unsigned* h, const char* filename)
3220 {
3221   unsigned char* buffer;
3222   size_t buffersize;
3223   unsigned error;
3224   error = LodePNG_loadFile(&buffer, &buffersize, filename);
3225   if(!error) error = LodePNG_decode32(out, w, h, buffer, buffersize);
3226   free(buffer);
3227   return error;
3228 }
3229 #endif /*LODEPNG_COMPILE_DISK*/
3230
3231 void LodePNG_DecodeSettings_init(LodePNG_DecodeSettings* settings)
3232 {
3233   settings->color_convert = 1;
3234 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
3235   settings->readTextChunks = 1;
3236 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
3237   settings->ignoreCrc = 0;
3238 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
3239   settings->rememberUnknownChunks = 0;
3240 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
3241   LodeZlib_DecompressSettings_init(&settings->zlibsettings);
3242 }
3243
3244 void LodePNG_Decoder_init(LodePNG_Decoder* decoder)
3245 {
3246   LodePNG_DecodeSettings_init(&decoder->settings);
3247   LodePNG_InfoRaw_init(&decoder->infoRaw);
3248   LodePNG_InfoPng_init(&decoder->infoPng);
3249   decoder->error = 1;
3250 }
3251
3252 void LodePNG_Decoder_cleanup(LodePNG_Decoder* decoder)
3253 {
3254   LodePNG_InfoRaw_cleanup(&decoder->infoRaw);
3255   LodePNG_InfoPng_cleanup(&decoder->infoPng);
3256 }
3257
3258 void LodePNG_Decoder_copy(LodePNG_Decoder* dest, const LodePNG_Decoder* source)
3259 {
3260   LodePNG_Decoder_cleanup(dest);
3261   *dest = *source;
3262   LodePNG_InfoRaw_init(&dest->infoRaw);
3263   LodePNG_InfoPng_init(&dest->infoPng);
3264   dest->error = LodePNG_InfoRaw_copy(&dest->infoRaw, &source->infoRaw); if(dest->error) return;
3265   dest->error = LodePNG_InfoPng_copy(&dest->infoPng, &source->infoPng); if(dest->error) return;
3266 }
3267
3268 #endif /*LODEPNG_COMPILE_DECODER*/
3269
3270 #ifdef LODEPNG_COMPILE_ENCODER
3271
3272 /* ////////////////////////////////////////////////////////////////////////// */
3273 /* / PNG Encoder                                                            / */
3274 /* ////////////////////////////////////////////////////////////////////////// */
3275
3276 /*chunkName must be string of 4 characters*/
3277 static unsigned addChunk(ucvector* out, const char* chunkName, const unsigned char* data, size_t length)
3278 {
3279   unsigned error = LodePNG_create_chunk(&out->data, &out->size, (unsigned)length, chunkName, data);
3280   if(error) return error;
3281   out->allocsize = out->size; /*fix the allocsize again*/
3282   return 0;
3283 }
3284
3285 static void writeSignature(ucvector* out)
3286 {
3287   /*8 bytes PNG signature*/
3288   ucvector_push_back(out, 137);
3289   ucvector_push_back(out, 80);
3290   ucvector_push_back(out, 78);
3291   ucvector_push_back(out, 71);
3292   ucvector_push_back(out, 13);
3293   ucvector_push_back(out, 10);
3294   ucvector_push_back(out, 26);
3295   ucvector_push_back(out, 10);
3296 }
3297
3298 static unsigned addChunk_IHDR(ucvector* out, unsigned w, unsigned h, unsigned bitDepth, unsigned colorType, unsigned interlaceMethod)
3299 {
3300   unsigned error = 0;
3301   ucvector header;
3302   ucvector_init(&header);
3303
3304   LodePNG_add32bitInt(&header, w); /*width*/
3305   LodePNG_add32bitInt(&header, h); /*height*/
3306   ucvector_push_back(&header, (unsigned char)bitDepth); /*bit depth*/
3307   ucvector_push_back(&header, (unsigned char)colorType); /*color type*/
3308   ucvector_push_back(&header, 0); /*compression method*/
3309   ucvector_push_back(&header, 0); /*filter method*/
3310   ucvector_push_back(&header, interlaceMethod); /*interlace method*/
3311
3312   error = addChunk(out, "IHDR", header.data, header.size);
3313   ucvector_cleanup(&header);
3314
3315   return error;
3316 }
3317
3318 static unsigned addChunk_PLTE(ucvector* out, const LodePNG_InfoColor* info)
3319 {
3320   unsigned error = 0;
3321   size_t i;
3322   ucvector PLTE;
3323   ucvector_init(&PLTE);
3324   for(i = 0; i < info->palettesize * 4; i++) if(i % 4 != 3) ucvector_push_back(&PLTE, info->palette[i]); /*add all channels except alpha channel*/
3325   error = addChunk(out, "PLTE", PLTE.data, PLTE.size);
3326   ucvector_cleanup(&PLTE);
3327
3328   return error;
3329 }
3330
3331 static unsigned addChunk_tRNS(ucvector* out, const LodePNG_InfoColor* info)
3332 {
3333   unsigned error = 0;
3334   size_t i;
3335   ucvector tRNS;
3336   ucvector_init(&tRNS);
3337   if(info->colorType == 3)
3338   {
3339     for(i = 0; i < info->palettesize; i++) ucvector_push_back(&tRNS, info->palette[4 * i + 3]); /*add only alpha channel*/
3340   }
3341   else if(info->colorType == 0)
3342   {
3343     if(info->key_defined)
3344     {
3345       ucvector_push_back(&tRNS, (unsigned char)(info->key_r / 256));
3346       ucvector_push_back(&tRNS, (unsigned char)(info->key_r % 256));
3347     }
3348   }
3349   else if(info->colorType == 2)
3350   {
3351     if(info->key_defined)
3352     {
3353       ucvector_push_back(&tRNS, (unsigned char)(info->key_r / 256));
3354       ucvector_push_back(&tRNS, (unsigned char)(info->key_r % 256));
3355       ucvector_push_back(&tRNS, (unsigned char)(info->key_g / 256));
3356       ucvector_push_back(&tRNS, (unsigned char)(info->key_g % 256));
3357       ucvector_push_back(&tRNS, (unsigned char)(info->key_b / 256));
3358       ucvector_push_back(&tRNS, (unsigned char)(info->key_b % 256));
3359     }
3360   }
3361
3362   error = addChunk(out, "tRNS", tRNS.data, tRNS.size);
3363   ucvector_cleanup(&tRNS);
3364
3365   return error;
3366 }
3367
3368 static unsigned addChunk_IDAT(ucvector* out, const unsigned char* data, size_t datasize, LodeZlib_DeflateSettings* zlibsettings)
3369 {
3370   ucvector zlibdata;
3371   unsigned error = 0;
3372
3373   /*compress with the Zlib compressor*/
3374   ucvector_init(&zlibdata);
3375   error = LodePNG_compress(&zlibdata.data, &zlibdata.size, data, datasize, zlibsettings);
3376   if(!error) error = addChunk(out, "IDAT", zlibdata.data, zlibdata.size);
3377   ucvector_cleanup(&zlibdata);
3378
3379   return error;
3380 }
3381
3382 static unsigned addChunk_IEND(ucvector* out)
3383 {
3384   unsigned error = 0;
3385   error = addChunk(out, "IEND", 0, 0);
3386   return error;
3387 }
3388
3389 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
3390
3391 static unsigned addChunk_tEXt(ucvector* out, const char* keyword, const char* textstring) /*add text chunk*/
3392 {
3393   unsigned error = 0;
3394   size_t i;
3395   ucvector text;
3396   ucvector_init(&text);
3397   for(i = 0; keyword[i] != 0; i++) ucvector_push_back(&text, (unsigned char)keyword[i]);
3398   ucvector_push_back(&text, 0);
3399   for(i = 0; textstring[i] != 0; i++) ucvector_push_back(&text, (unsigned char)textstring[i]);
3400   error = addChunk(out, "tEXt", text.data, text.size);
3401   ucvector_cleanup(&text);
3402
3403   return error;
3404 }
3405
3406 static unsigned addChunk_zTXt(ucvector* out, const char* keyword, const char* textstring, LodeZlib_DeflateSettings* zlibsettings)
3407 {
3408   unsigned error = 0;
3409   ucvector data, compressed;
3410   size_t i, textsize = strlen(textstring);
3411
3412   ucvector_init(&data);
3413   ucvector_init(&compressed);
3414   for(i = 0; keyword[i] != 0; i++) ucvector_push_back(&data, (unsigned char)keyword[i]);
3415   ucvector_push_back(&data, 0); /* 0 termination char*/
3416   ucvector_push_back(&data, 0); /*compression method: 0*/
3417
3418   error = LodePNG_compress(&compressed.data, &compressed.size, (unsigned char*)textstring, textsize, zlibsettings);
3419   if(!error)
3420   {
3421     for(i = 0; i < compressed.size; i++) ucvector_push_back(&data, compressed.data[i]);
3422     error = addChunk(out, "zTXt", data.data, data.size);
3423   }
3424
3425   ucvector_cleanup(&compressed);
3426   ucvector_cleanup(&data);
3427   return error;
3428 }
3429
3430 static unsigned addChunk_iTXt(ucvector* out, unsigned compressed, const char* keyword, const char* langtag, const char* transkey, const char* textstring, LodeZlib_DeflateSettings* zlibsettings)
3431 {
3432   unsigned error = 0;
3433   ucvector data, compressed_data;
3434   size_t i, textsize = strlen(textstring);
3435
3436   ucvector_init(&data);
3437
3438   for(i = 0; keyword[i] != 0; i++) ucvector_push_back(&data, (unsigned char)keyword[i]);
3439   ucvector_push_back(&data, 0); /*null termination char*/
3440   ucvector_push_back(&data, compressed ? 1 : 0); /*compression flag*/
3441   ucvector_push_back(&data, 0); /*compression method*/
3442   for(i = 0; langtag[i] != 0; i++) ucvector_push_back(&data, (unsigned char)langtag[i]);
3443   ucvector_push_back(&data, 0); /*null termination char*/
3444   for(i = 0; transkey[i] != 0; i++) ucvector_push_back(&data, (unsigned char)transkey[i]);
3445   ucvector_push_back(&data, 0); /*null termination char*/
3446
3447   if(compressed)
3448   {
3449     ucvector_init(&compressed_data);
3450     error = LodePNG_compress(&compressed_data.data, &compressed_data.size, (unsigned char*)textstring, textsize, zlibsettings);
3451     if(!error)
3452     {
3453       for(i = 0; i < compressed_data.size; i++) ucvector_push_back(&data, compressed_data.data[i]);
3454       for(i = 0; textstring[i] != 0; i++) ucvector_push_back(&data, (unsigned char)textstring[i]);
3455     }
3456   }
3457   else /*not compressed*/
3458   {
3459     for(i = 0; textstring[i] != 0; i++) ucvector_push_back(&data, (unsigned char)textstring[i]);
3460   }
3461
3462   if(!error) error = addChunk(out, "iTXt", data.data, data.size);
3463   ucvector_cleanup(&data);
3464   return error;
3465 }
3466
3467 static unsigned addChunk_bKGD(ucvector* out, const LodePNG_InfoPng* info)
3468 {
3469   unsigned error = 0;
3470   ucvector bKGD;
3471   ucvector_init(&bKGD);
3472   if(info->color.colorType == 0 || info->color.colorType == 4)
3473   {
3474     ucvector_push_back(&bKGD, (unsigned char)(info->background_r / 256));
3475     ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256));
3476   }
3477   else if(info->color.colorType == 2 || info->color.colorType == 6)
3478   {
3479     ucvector_push_back(&bKGD, (unsigned char)(info->background_r / 256));
3480     ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256));
3481     ucvector_push_back(&bKGD, (unsigned char)(info->background_g / 256));
3482     ucvector_push_back(&bKGD, (unsigned char)(info->background_g % 256));
3483     ucvector_push_back(&bKGD, (unsigned char)(info->background_b / 256));
3484     ucvector_push_back(&bKGD, (unsigned char)(info->background_b % 256));
3485   }
3486   else if(info->color.colorType == 3)
3487   {
3488     ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256)); /*palette index*/
3489   }
3490
3491   error = addChunk(out, "bKGD", bKGD.data, bKGD.size);
3492   ucvector_cleanup(&bKGD);
3493
3494   return error;
3495 }
3496
3497 static unsigned addChunk_tIME(ucvector* out, const LodePNG_Time* time)
3498 {
3499   unsigned error = 0;
3500   unsigned char* data = (unsigned char*)malloc(7);
3501   if(!data) return 9948;
3502   data[0] = (unsigned char)(time->year / 256);
3503   data[1] = (unsigned char)(time->year % 256);
3504   data[2] = time->month;
3505   data[3] = time->day;
3506   data[4] = time->hour;
3507   data[5] = time->minute;
3508   data[6] = time->second;
3509   error = addChunk(out, "tIME", data, 7);
3510   free(data);
3511   return error;
3512 }
3513
3514 static unsigned addChunk_pHYs(ucvector* out, const LodePNG_InfoPng* info)
3515 {
3516   unsigned error = 0;
3517   ucvector data;
3518   ucvector_init(&data);
3519
3520   LodePNG_add32bitInt(&data, info->phys_x);
3521   LodePNG_add32bitInt(&data, info->phys_y);
3522   ucvector_push_back(&data, info->phys_unit);
3523
3524   error = addChunk(out, "pHYs", data.data, data.size);
3525   ucvector_cleanup(&data);
3526
3527   return error;
3528 }
3529
3530 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
3531
3532 static void filterScanline(unsigned char* out, const unsigned char* scanline, const unsigned char* prevline, size_t length, size_t bytewidth, unsigned char filterType)
3533 {
3534   size_t i;
3535   switch(filterType)
3536   {
3537     case 0:
3538       if(prevline) for(i = 0; i < length; i++) out[i] = scanline[i];
3539       else         for(i = 0; i < length; i++) out[i] = scanline[i];
3540       break;
3541     case 1:
3542       if(prevline)
3543       {
3544         for(i =         0; i < bytewidth; i++) out[i] = scanline[i];
3545         for(i = bytewidth; i < length   ; i++) out[i] = scanline[i] - scanline[i - bytewidth];
3546       }
3547       else
3548       {
3549         for(i =         0; i < bytewidth; i++) out[i] = scanline[i];
3550         for(i = bytewidth; i <    length; i++) out[i] = scanline[i] - scanline[i - bytewidth];
3551       }
3552       break;
3553     case 2:
3554       if(prevline) for(i = 0; i < length; i++) out[i] = scanline[i] - prevline[i];
3555       else         for(i = 0; i < length; i++) out[i] = scanline[i];
3556       break;
3557     case 3:
3558       if(prevline)
3559       {
3560         for(i =         0; i < bytewidth; i++) out[i] = scanline[i] - prevline[i] / 2;
3561         for(i = bytewidth; i <    length; i++) out[i] = scanline[i] - ((scanline[i - bytewidth] + prevline[i]) / 2);
3562       }
3563       else
3564       {
3565         for(i =         0; i < length; i++) out[i] = scanline[i];
3566         for(i = bytewidth; i < length; i++) out[i] = scanline[i] - scanline[i - bytewidth] / 2;
3567       }
3568       break;
3569     case 4:
3570       if(prevline)
3571       {
3572         for(i =         0; i < bytewidth; i++) out[i] = (unsigned char)(scanline[i] - paethPredictor(0, prevline[i], 0));
3573         for(i = bytewidth; i <    length; i++) out[i] = (unsigned char)(scanline[i] - paethPredictor(scanline[i - bytewidth], prevline[i], prevline[i - bytewidth]));
3574       }
3575       else
3576       {
3577         for(i =         0; i < bytewidth; i++) out[i] = scanline[i];
3578         for(i = bytewidth; i <    length; i++) out[i] = (unsigned char)(scanline[i] - paethPredictor(scanline[i - bytewidth], 0, 0));
3579       }
3580       break;
3581   default: return; /*unexisting filter type given*/
3582   }
3583 }
3584
3585 static unsigned filter(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, const LodePNG_InfoColor* info)
3586 {
3587   /*
3588   For PNG filter method 0
3589   out must be a buffer with as size: h + (w * h * bpp + 7) / 8, because there are the scanlines with 1 extra byte per scanline
3590
3591   There is a nice heuristic described here: http://www.cs.toronto.edu/~cosmin/pngtech/optipng.html. It says:
3592    *  If the image type is Palette, or the bit depth is smaller than 8, then do not filter the image (i.e. use fixed filtering, with the filter None).
3593    * (The other case) If the image type is Grayscale or RGB (with or without Alpha), and the bit depth is not smaller than 8, then use adaptive filtering heuristic as follows: independently for each row, apply all five filters and select the filter that produces the smallest sum of absolute values per row.
3594
3595   Here the above method is used mostly. Note though that it appears to be better to use the adaptive filtering on the plasma 8-bit palette example, but that image isn't the best reference for palette images in general.
3596   */
3597
3598   unsigned bpp = LodePNG_InfoColor_getBpp(info);
3599   size_t linebytes = (w * bpp + 7) / 8; /*the width of a scanline in bytes, not including the filter type*/
3600   size_t bytewidth = (bpp + 7) / 8; /*bytewidth is used for filtering, is 1 when bpp < 8, number of bytes per pixel otherwise*/
3601   const unsigned char* prevline = 0;
3602   unsigned x, y;
3603   unsigned heuristic;
3604   unsigned error = 0;
3605
3606   if(bpp == 0) return 31; /*invalid color type*/
3607
3608   /*choose heuristic as described above*/
3609   if(info->colorType == 3 || info->bitDepth < 8) heuristic = 0;
3610   else heuristic = 1;
3611
3612   if(heuristic == 0) /*None filtertype for everything*/
3613   {
3614     for(y = 0; y < h; y++)
3615     {
3616       size_t outindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
3617       size_t inindex = linebytes * y;
3618       const unsigned TYPE = 0;
3619       out[outindex] = TYPE; /*filter type byte*/
3620       filterScanline(&out[outindex + 1], &in[inindex], prevline, linebytes, bytewidth, TYPE);
3621       prevline = &in[inindex];
3622     }
3623   }
3624   else if(heuristic == 1) /*adaptive filtering*/
3625   {
3626     size_t sum[5];
3627     ucvector attempt[5]; /*five filtering attempts, one for each filter type*/
3628     size_t smallest = 0;
3629     unsigned type, bestType = 0;
3630
3631     for(type = 0; type < 5; type++) ucvector_init(&attempt[type]);
3632     for(type = 0; type < 5; type++)
3633     {
3634       if(!ucvector_resize(&attempt[type], linebytes)) { error = 9949; break; }
3635     }
3636
3637     if(!error)
3638     {
3639       for(y = 0; y < h; y++)
3640       {
3641         /*try the 5 filter types*/
3642         for(type = 0; type < 5; type++)
3643         {
3644           filterScanline(attempt[type].data, &in[y * linebytes], prevline, linebytes, bytewidth, type);
3645
3646           /*calculate the sum of the result*/
3647           sum[type] = 0;
3648           for(x = 0; x < attempt[type].size; x+=3) sum[type] += attempt[type].data[x]; /*note that not all pixels are checked to speed this up while still having probably the best choice*/
3649
3650           /*check if this is smallest sum (or if type == 0 it's the first case so always store the values)*/
3651           if(type == 0 || sum[type] < smallest)
3652           {
3653             bestType = type;
3654             smallest = sum[type];
3655           }
3656         }
3657
3658         prevline = &in[y * linebytes];
3659
3660         /*now fill the out values*/
3661         out[y * (linebytes + 1)] = bestType; /*the first byte of a scanline will be the filter type*/
3662         for(x = 0; x < linebytes; x++) out[y * (linebytes + 1) + 1 + x] = attempt[bestType].data[x];
3663       }
3664     }
3665
3666     for(type = 0; type < 5; type++) ucvector_cleanup(&attempt[type]);
3667   }
3668   #if 0 /*deflate the scanline with a fixed tree after every filter attempt to see which one deflates best. This is slow, and _does not work as expected_: the heuristic gives smaller result!*/
3669   else if(heuristic == 2) /*adaptive filtering by using deflate*/
3670   {
3671     size_t size[5];
3672     ucvector attempt[5]; /*five filtering attempts, one for each filter type*/
3673     size_t smallest;
3674     unsigned type = 0, bestType = 0;
3675     unsigned char* dummy;
3676     LodeZlib_DeflateSettings deflatesettings = LodeZlib_defaultDeflateSettings;
3677     deflatesettings.btype = 1; /*use fixed tree on the attempts so that the tree is not adapted to the filtertype on purpose, to simulate the true case where the tree is the same for the whole image*/
3678     for(type = 0; type < 5; type++) { ucvector_init(&attempt[type]); ucvector_resize(&attempt[type], linebytes); }
3679     for(y = 0; y < h; y++) /*try the 5 filter types*/
3680     {
3681       for(type = 0; type < 5; type++)
3682       {
3683         filterScanline(attempt[type].data, &in[y * linebytes], prevline, linebytes, bytewidth, type);
3684         size[type] = 0; dummy = 0;
3685         LodePNG_compress(&dummy, &size[type], attempt[type].data, attempt[type].size, &deflatesettings);
3686         free(dummy);
3687         /*check if this is smallest size (or if type == 0 it's the first case so always store the values)*/
3688         if(type == 0 || size[type] < smallest) { bestType = type; smallest = size[type]; }
3689       }
3690       prevline = &in[y * linebytes];
3691       out[y * (linebytes + 1)] = bestType; /*the first byte of a scanline will be the filter type*/
3692       for(x = 0; x < linebytes; x++) out[y * (linebytes + 1) + 1 + x] = attempt[bestType].data[x];
3693     }
3694     for(type = 0; type < 5; type++) ucvector_cleanup(&attempt[type]);
3695   }
3696   #endif
3697
3698   return error;
3699 }
3700
3701 static void addPaddingBits(unsigned char* out, const unsigned char* in, size_t olinebits, size_t ilinebits, unsigned h)
3702 {
3703   /*The opposite of the removePaddingBits function
3704   olinebits must be >= ilinebits*/
3705   unsigned y;
3706   size_t diff = olinebits - ilinebits;
3707   size_t obp = 0, ibp = 0; /*bit pointers*/
3708   for(y = 0; y < h; y++)
3709   {
3710     size_t x;
3711     for(x = 0; x < ilinebits; x++)
3712     {
3713       unsigned char bit = readBitFromReversedStream(&ibp, in);
3714       setBitOfReversedStream(&obp, out, bit);
3715     }
3716     /*obp += diff; --> no, fill in some value in the padding bits too, to avoid "Use of uninitialised value of size ###" warning from valgrind*/
3717     for(x = 0; x < diff; x++) setBitOfReversedStream(&obp, out, 0);
3718   }
3719 }
3720
3721 static void Adam7_interlace(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
3722 {
3723   /*Note: this function works on image buffers WITHOUT padding bits at end of scanlines with non-multiple-of-8 bit amounts, only between reduced images is padding*/
3724   unsigned passw[7], passh[7]; size_t filter_passstart[8], padded_passstart[8], passstart[8];
3725   unsigned i;
3726
3727   Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
3728
3729   if(bpp >= 8)
3730   {
3731     for(i = 0; i < 7; i++)
3732     {
3733       unsigned x, y, b;
3734       size_t bytewidth = bpp / 8;
3735       for(y = 0; y < passh[i]; y++)
3736       for(x = 0; x < passw[i]; x++)
3737       {
3738         size_t pixelinstart = ((ADAM7_IY[i] + y * ADAM7_DY[i]) * w + ADAM7_IX[i] + x * ADAM7_DX[i]) * bytewidth;
3739         size_t pixeloutstart = passstart[i] + (y * passw[i] + x) * bytewidth;
3740         for(b = 0; b < bytewidth; b++)
3741         {
3742           out[pixeloutstart + b] = in[pixelinstart + b];
3743         }
3744       }
3745     }
3746   }
3747   else /*bpp < 8: Adam7 with pixels < 8 bit is a bit trickier: with bit pointers*/
3748   {
3749     for(i = 0; i < 7; i++)
3750     {
3751       unsigned x, y, b;
3752       unsigned ilinebits = bpp * passw[i];
3753       unsigned olinebits = bpp * w;
3754       size_t obp, ibp; /*bit pointers (for out and in buffer)*/
3755       for(y = 0; y < passh[i]; y++)
3756       for(x = 0; x < passw[i]; x++)
3757       {
3758         ibp = (ADAM7_IY[i] + y * ADAM7_DY[i]) * olinebits + (ADAM7_IX[i] + x * ADAM7_DX[i]) * bpp;
3759         obp = (8 * passstart[i]) + (y * ilinebits + x * bpp);
3760         for(b = 0; b < bpp; b++)
3761         {
3762           unsigned char bit = readBitFromReversedStream(&ibp, in);
3763           setBitOfReversedStream(&obp, out, bit);
3764         }
3765       }
3766     }
3767   }
3768 }
3769
3770 /*out must be buffer big enough to contain uncompressed IDAT chunk data, and in must contain the full image*/
3771 static unsigned preProcessScanlines(unsigned char** out, size_t* outsize, const unsigned char* in, const LodePNG_InfoPng* infoPng) /*return value is error*/
3772 {
3773   /*
3774   This function converts the pure 2D image with the PNG's colortype, into filtered-padded-interlaced data. Steps:
3775   *) if no Adam7: 1) add padding bits (= posible extra bits per scanline if bpp < 8) 2) filter
3776   *) if adam7: 1) Adam7_interlace 2) 7x add padding bits 3) 7x filter
3777   */
3778   unsigned bpp = LodePNG_InfoColor_getBpp(&infoPng->color);
3779   unsigned w = infoPng->width;
3780   unsigned h = infoPng->height;
3781   unsigned error = 0;
3782
3783   if(infoPng->interlaceMethod == 0)
3784   {
3785     *outsize = h + (h * ((w * bpp + 7) / 8)); /*image size plus an extra byte per scanline + possible padding bits*/
3786     *out = (unsigned char*)malloc(*outsize);
3787     if(!(*out) && (*outsize)) error = 9950;
3788
3789     if(!error)
3790     {
3791       if(bpp < 8 && w * bpp != ((w * bpp + 7) / 8) * 8) /*non multiple of 8 bits per scanline, padding bits needed per scanline*/
3792       {
3793         ucvector padded;
3794         ucvector_init(&padded);
3795         if(!ucvector_resize(&padded, h * ((w * bpp + 7) / 8))) error = 9951;
3796         if(!error)
3797         {
3798           addPaddingBits(padded.data, in, ((w * bpp + 7) / 8) * 8, w * bpp, h);
3799           error = filter(*out, padded.data, w, h, &infoPng->color);
3800         }
3801         ucvector_cleanup(&padded);
3802       }
3803       else error = filter(*out, in, w, h, &infoPng->color); /*we can immediatly filter into the out buffer, no other steps needed*/
3804     }
3805   }
3806   else /*interlaceMethod is 1 (Adam7)*/
3807   {
3808     unsigned char* adam7 = (unsigned char*)malloc((h * w * bpp + 7) / 8);
3809     if(!adam7 && ((h * w * bpp + 7) / 8)) error = 9952; /*malloc failed*/
3810
3811     while(!error) /*not a real while loop, used to break out to cleanup to avoid a goto*/
3812     {
3813       unsigned passw[7], passh[7]; size_t filter_passstart[8], padded_passstart[8], passstart[8];
3814       unsigned i;
3815
3816       Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
3817
3818       *outsize = filter_passstart[7]; /*image size plus an extra byte per scanline + possible padding bits*/
3819       *out = (unsigned char*)malloc(*outsize);
3820       if(!(*out) && (*outsize)) { error = 9953; break; }
3821
3822       Adam7_interlace(adam7, in, w, h, bpp);
3823
3824       for(i = 0; i < 7; i++)
3825       {
3826         if(bpp < 8)
3827         {
3828           ucvector padded;
3829           ucvector_init(&padded);
3830           if(!ucvector_resize(&padded, h * ((w * bpp + 7) / 8))) error = 9954;
3831           if(!error)
3832           {
3833             addPaddingBits(&padded.data[padded_passstart[i]], &adam7[passstart[i]], ((passw[i] * bpp + 7) / 8) * 8, passw[i] * bpp, passh[i]);
3834             error = filter(&(*out)[filter_passstart[i]], &padded.data[padded_passstart[i]], passw[i], passh[i], &infoPng->color);
3835           }
3836
3837           ucvector_cleanup(&padded);
3838         }
3839         else
3840         {
3841           error = filter(&(*out)[filter_passstart[i]], &adam7[padded_passstart[i]], passw[i], passh[i], &infoPng->color);
3842         }
3843       }
3844
3845       break;
3846     }
3847
3848     free(adam7);
3849   }
3850
3851   return error;
3852 }
3853
3854 /*palette must have 4 * palettesize bytes allocated*/
3855 static unsigned isPaletteFullyOpaque(const unsigned char* palette, size_t palettesize) /*palette given in format RGBARGBARGBARGBA...*/
3856 {
3857   size_t i;
3858   for(i = 0; i < palettesize; i++)
3859   {
3860     if(palette[4 * i + 3] != 255) return 0;
3861   }
3862   return 1;
3863 }
3864
3865 /*this function checks if the input image given by the user has no transparent pixels*/
3866 static unsigned isFullyOpaque(const unsigned char* image, unsigned w, unsigned h, const LodePNG_InfoColor* info)
3867 {
3868   /*TODO: When the user specified a color key for the input image, then this function must also check for pixels that are the same as the color key and treat those as transparent.*/
3869
3870   unsigned i, numpixels = w * h;
3871   if(info->colorType == 6)
3872   {
3873     if(info->bitDepth == 8)
3874     {
3875       for(i = 0; i < numpixels; i++) if(image[i * 4 + 3] != 255) return 0;
3876     }
3877     else
3878     {
3879       for(i = 0; i < numpixels; i++) if(image[i * 8 + 6] != 255 || image[i * 8 + 7] != 255) return 0;
3880     }
3881     return 1; /*no single pixel with alpha channel other than 255 found*/
3882   }
3883   else if(info->colorType == 4)
3884   {
3885     if(info->bitDepth == 8)
3886     {
3887       for(i = 0; i < numpixels; i++) if(image[i * 2 + 1] != 255) return 0;
3888     }
3889     else
3890     {
3891       for(i = 0; i < numpixels; i++) if(image[i * 4 + 2] != 255 || image[i * 4 + 3] != 255) return 0;
3892     }
3893     return 1; /*no single pixel with alpha channel other than 255 found*/
3894   }
3895   else if(info->colorType == 3)
3896   {
3897     /*when there's a palette, we could check every pixel for translucency, but much quicker is to just check the palette*/
3898     return(isPaletteFullyOpaque(info->palette, info->palettesize));
3899   }
3900
3901   return 0; /*color type that isn't supported by this function yet, so assume there is transparency to be safe*/
3902 }
3903
3904 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
3905 static unsigned addUnknownChunks(ucvector* out, unsigned char* data, size_t datasize)
3906 {
3907   unsigned char* inchunk = data;
3908   while((size_t)(inchunk - data) < datasize)
3909   {
3910     unsigned error = LodePNG_append_chunk(&out->data, &out->size, inchunk);
3911     if(error) return error; /*error: not enough memory*/
3912     out->allocsize = out->size; /*fix the allocsize again*/
3913     inchunk = LodePNG_chunk_next(inchunk);
3914   }
3915   return 0;
3916 }
3917 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
3918
3919 void LodePNG_encode(LodePNG_Encoder* encoder, unsigned char** out, size_t* outsize, const unsigned char* image, unsigned w, unsigned h)
3920 {
3921   LodePNG_InfoPng info;
3922   ucvector outv;
3923   unsigned char* data = 0; /*uncompressed version of the IDAT chunk data*/
3924   size_t datasize = 0;
3925
3926   /*provide some proper output values if error will happen*/
3927   *out = 0;
3928   *outsize = 0;
3929   encoder->error = 0;
3930
3931   info = encoder->infoPng; /*UNSAFE copy to avoid having to cleanup! but we will only change primitive parameters, and not invoke the cleanup function nor touch the palette's buffer so we use it safely*/
3932   info.width = w;
3933   info.height = h;
3934
3935   if(encoder->settings.autoLeaveOutAlphaChannel && isFullyOpaque(image, w, h, &encoder->infoRaw.color))
3936   {
3937     /*go to a color type without alpha channel*/
3938     if(info.color.colorType == 6) info.color.colorType = 2;
3939     else if(info.color.colorType == 4) info.color.colorType = 0;
3940   }
3941
3942   if(encoder->settings.zlibsettings.windowSize > 32768) { encoder->error = 60; return; } /*error: windowsize larger than allowed*/
3943   if(encoder->settings.zlibsettings.btype > 2) { encoder->error = 61; return; } /*error: unexisting btype*/
3944   if(encoder->infoPng.interlaceMethod > 1) { encoder->error = 71; return; } /*error: unexisting interlace mode*/
3945   if((encoder->error = checkColorValidity(info.color.colorType, info.color.bitDepth))) return; /*error: unexisting color type given*/
3946   if((encoder->error = checkColorValidity(encoder->infoRaw.color.colorType, encoder->infoRaw.color.bitDepth))) return; /*error: unexisting color type given*/
3947
3948   if(!LodePNG_InfoColor_equal(&encoder->infoRaw.color, &info.color))
3949   {
3950     unsigned char* converted;
3951     size_t size = (w * h * LodePNG_InfoColor_getBpp(&info.color) + 7) / 8;
3952
3953     if((info.color.colorType != 6 && info.color.colorType != 2) || (info.color.bitDepth != 8)) { encoder->error = 59; return; } /*for the output image, only these types are supported*/
3954     converted = (unsigned char*)malloc(size);
3955     if(!converted && size) encoder->error = 9955; /*error: malloc failed*/
3956     if(!encoder->error) encoder->error = LodePNG_convert(converted, image, &info.color, &encoder->infoRaw.color, w, h);
3957     if(!encoder->error) preProcessScanlines(&data, &datasize, converted, &info);/*filter(data.data, converted.data, w, h, LodePNG_InfoColor_getBpp(&info.color));*/
3958     free(converted);
3959   }
3960   else preProcessScanlines(&data, &datasize, image, &info);/*filter(data.data, image, w, h, LodePNG_InfoColor_getBpp(&info.color));*/
3961
3962   ucvector_init(&outv);
3963   while(!encoder->error) /*not really a while loop, this is only used to break out if an error happens to avoid goto's to do the ucvector cleanup*/
3964   {
3965 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
3966     size_t i;
3967 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
3968     /*write signature and chunks*/
3969     writeSignature(&outv);
3970     /*IHDR*/
3971     addChunk_IHDR(&outv, w, h, info.color.bitDepth, info.color.colorType, info.interlaceMethod);
3972 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
3973     /*unknown chunks between IHDR and PLTE*/
3974     if(info.unknown_chunks.data[0]) { encoder->error = addUnknownChunks(&outv, info.unknown_chunks.data[0], info.unknown_chunks.datasize[0]); if(encoder->error) break; }
3975 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
3976     /*PLTE*/
3977     if(info.color.colorType == 3)
3978     {
3979       if(info.color.palettesize == 0 || info.color.palettesize > 256) { encoder->error = 68; break; }
3980       addChunk_PLTE(&outv, &info.color);
3981     }
3982     if(encoder->settings.force_palette && (info.color.colorType == 2 || info.color.colorType == 6))
3983     {
3984       if(info.color.palettesize == 0 || info.color.palettesize > 256) { encoder->error = 68; break; }
3985       addChunk_PLTE(&outv, &info.color);
3986     }
3987     /*tRNS*/
3988     if(info.color.colorType == 3 && !isPaletteFullyOpaque(info.color.palette, info.color.palettesize)) addChunk_tRNS(&outv, &info.color);
3989     if((info.color.colorType == 0 || info.color.colorType == 2) && info.color.key_defined) addChunk_tRNS(&outv, &info.color);
3990 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
3991     /*bKGD (must come between PLTE and the IDAt chunks*/
3992     if(info.background_defined) addChunk_bKGD(&outv, &info);
3993     /*pHYs (must come before the IDAT chunks)*/
3994     if(info.phys_defined) addChunk_pHYs(&outv, &info);
3995 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
3996 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
3997     /*unknown chunks between PLTE and IDAT*/
3998     if(info.unknown_chunks.data[1]) { encoder->error = addUnknownChunks(&outv, info.unknown_chunks.data[1], info.unknown_chunks.datasize[1]); if(encoder->error) break; }
3999 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
4000     /*IDAT (multiple IDAT chunks must be consecutive)*/
4001     encoder->error = addChunk_IDAT(&outv, data, datasize, &encoder->settings.zlibsettings);
4002     if(encoder->error) break;
4003 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4004     /*tIME*/
4005     if(info.time_defined) addChunk_tIME(&outv, &info.time);
4006     /*tEXt and/or zTXt*/
4007     for(i = 0; i < info.text.num; i++)
4008     {
4009       if(strlen(info.text.keys[i]) > 79) { encoder->error = 66; break; }
4010       if(strlen(info.text.keys[i]) < 1) { encoder->error = 67; break; }
4011       if(encoder->settings.text_compression)
4012         addChunk_zTXt(&outv, info.text.keys[i], info.text.strings[i], &encoder->settings.zlibsettings);
4013       else
4014         addChunk_tEXt(&outv, info.text.keys[i], info.text.strings[i]);
4015     }
4016     /*LodePNG version id in text chunk*/
4017     if(encoder->settings.add_id)
4018     {
4019       unsigned alread_added_id_text = 0;
4020       for(i = 0; i < info.text.num; i++)
4021         if(!strcmp(info.text.keys[i], "LodePNG")) { alread_added_id_text = 1; break; }
4022       if(alread_added_id_text == 0)
4023         addChunk_tEXt(&outv, "LodePNG", VERSION_STRING); /*it's shorter as tEXt than as zTXt chunk*/
4024     }
4025     /*iTXt*/
4026     for(i = 0; i < info.itext.num; i++)
4027     {
4028       if(strlen(info.itext.keys[i]) > 79) { encoder->error = 66; break; }
4029       if(strlen(info.itext.keys[i]) < 1) { encoder->error = 67; break; }
4030       addChunk_iTXt(&outv, encoder->settings.text_compression,
4031                     info.itext.keys[i], info.itext.langtags[i], info.itext.transkeys[i], info.itext.strings[i],
4032                     &encoder->settings.zlibsettings);
4033     }
4034 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4035 #ifdef LODEPNG_COMPILE_UNKNOWN_CHUNKS
4036     /*unknown chunks between IDAT and IEND*/
4037     if(info.unknown_chunks.data[2]) { encoder->error = addUnknownChunks(&outv, info.unknown_chunks.data[2], info.unknown_chunks.datasize[2]); if(encoder->error) break; }
4038 #endif /*LODEPNG_COMPILE_UNKNOWN_CHUNKS*/
4039     /*IEND*/
4040     addChunk_IEND(&outv);
4041
4042     break; /*this isn't really a while loop; no error happened so break out now!*/
4043   }
4044
4045   free(data);
4046   /*instead of cleaning the vector up, give it to the output*/
4047   *out = outv.data;
4048   *outsize = outv.size;
4049 }
4050
4051 unsigned LodePNG_encode32(unsigned char** out, size_t* outsize, const unsigned char* image, unsigned w, unsigned h)
4052 {
4053   unsigned error;
4054   LodePNG_Encoder encoder;
4055   LodePNG_Encoder_init(&encoder);
4056   LodePNG_encode(&encoder, out, outsize, image, w, h);
4057   error = encoder.error;
4058   LodePNG_Encoder_cleanup(&encoder);
4059   return error;
4060 }
4061
4062 #ifdef LODEPNG_COMPILE_DISK
4063 unsigned LodePNG_encode32f(const char* filename, const unsigned char* image, unsigned w, unsigned h)
4064 {
4065   unsigned char* buffer;
4066   size_t buffersize;
4067   unsigned error = LodePNG_encode32(&buffer, &buffersize, image, w, h);
4068   LodePNG_saveFile(buffer, buffersize, filename);
4069   free(buffer);
4070   return error;
4071 }
4072 #endif /*LODEPNG_COMPILE_DISK*/
4073
4074 void LodePNG_EncodeSettings_init(LodePNG_EncodeSettings* settings)
4075 {
4076   LodeZlib_DeflateSettings_init(&settings->zlibsettings);
4077   settings->autoLeaveOutAlphaChannel = 1;
4078   settings->force_palette = 0;
4079 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4080   settings->add_id = 1;
4081   settings->text_compression = 0;
4082 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4083 }
4084
4085 void LodePNG_Encoder_init(LodePNG_Encoder* encoder)
4086 {
4087   LodePNG_EncodeSettings_init(&encoder->settings);
4088   LodePNG_InfoPng_init(&encoder->infoPng);
4089   LodePNG_InfoRaw_init(&encoder->infoRaw);
4090   encoder->error = 1;
4091 }
4092
4093 void LodePNG_Encoder_cleanup(LodePNG_Encoder* encoder)
4094 {
4095   LodePNG_InfoPng_cleanup(&encoder->infoPng);
4096   LodePNG_InfoRaw_cleanup(&encoder->infoRaw);
4097 }
4098
4099 void LodePNG_Encoder_copy(LodePNG_Encoder* dest, const LodePNG_Encoder* source)
4100 {
4101   LodePNG_Encoder_cleanup(dest);
4102   *dest = *source;
4103   LodePNG_InfoPng_init(&dest->infoPng);
4104   LodePNG_InfoRaw_init(&dest->infoRaw);
4105   dest->error = LodePNG_InfoPng_copy(&dest->infoPng, &source->infoPng); if(dest->error) return;
4106   dest->error = LodePNG_InfoRaw_copy(&dest->infoRaw, &source->infoRaw); if(dest->error) return;
4107 }
4108
4109 #endif /*LODEPNG_COMPILE_ENCODER*/
4110
4111 #endif /*LODEPNG_COMPILE_PNG*/
4112
4113 /* ////////////////////////////////////////////////////////////////////////// */
4114 /* / File IO                                                                / */
4115 /* ////////////////////////////////////////////////////////////////////////// */
4116
4117 #ifdef LODEPNG_COMPILE_DISK
4118
4119 unsigned LodePNG_loadFile(unsigned char** out, size_t* outsize, const char* filename) /*designed for loading files from hard disk in a dynamically allocated buffer*/
4120 {
4121   FILE* file;
4122   long size;
4123
4124   /*provide some proper output values if error will happen*/
4125   *out = 0;
4126   *outsize = 0;
4127
4128   file = portable_fopen(filename, "rb");
4129   if(!file) return 78;
4130
4131   /*get filesize:*/
4132   fseek(file , 0 , SEEK_END);
4133   size = ftell(file);
4134   rewind(file);
4135
4136   /*read contents of the file into the vector*/
4137   *outsize = 0;
4138   *out = (unsigned char*)malloc((size_t)size);
4139   if(size && (*out)) (*outsize) = fread(*out, 1, (size_t)size, file);
4140
4141   fclose(file);
4142   if(!(*out) && size) return 80; /*the above malloc failed*/
4143   return 0;
4144 }
4145
4146 /*write given buffer to the file, overwriting the file, it doesn't append to it.*/
4147 unsigned LodePNG_saveFile(const unsigned char* buffer, size_t buffersize, const char* filename)
4148 {
4149   FILE* file;
4150   file = portable_fopen(filename, "wb" );
4151   if(!file) return 79;
4152   fwrite((char*)buffer , 1 , buffersize, file);
4153   fclose(file);
4154   return 0;
4155 }
4156
4157 #endif /*LODEPNG_COMPILE_DISK*/
4158