Xemu [doxygen]  hyppo 0a42be3a057156924bc1b626a687bd6e27349c45 @ Sat 19 Mar 02:15:11 CET 2022
lodepng.c
Go to the documentation of this file.
1 /*
2 LodePNG version 20150418
3 
4 Copyright (c) 2005-2015 Lode Vandevenne
5 
6 !! XEMU WARNING: this is not the original distribution of LodePNG,
7 !! some lighter modifications have been done! - LGB
8 
9 This software is provided 'as-is', without any express or implied
10 warranty. In no event will the authors be held liable for any damages
11 arising from the use of this software.
12 
13 Permission is granted to anyone to use this software for any purpose,
14 including commercial applications, and to alter it and redistribute it
15 freely, subject to the following restrictions:
16 
17  1. The origin of this software must not be misrepresented; you must not
18  claim that you wrote the original software. If you use this software
19  in a product, an acknowledgment in the product documentation would be
20  appreciated but is not required.
21 
22  2. Altered source versions must be plainly marked as such, and must not be
23  misrepresented as being the original software.
24 
25  3. This notice may not be removed or altered from any source
26  distribution.
27 */
28 
29 /*
30 The manual and changelog are in the header file "lodepng.h"
31 */
32 
33 
34 #ifdef XEMU_USE_LODEPNG
35 
36 #include "xemu/lodepng.h"
37 
38 #include <stdio.h>
39 #include <stdlib.h>
40 
41 #if defined(_MSC_VER) && (_MSC_VER >= 1310) /*Visual Studio: A few warning types are not desired here.*/
42 #pragma warning( disable : 4244 ) /*implicit conversions: not warned by gcc -Wall -Wextra and requires too much casts*/
43 #pragma warning( disable : 4996 ) /*VS does not like fopen, but fopen_s is not standard C so unusable here*/
44 #endif /*_MSC_VER */
45 
46 const char* LODEPNG_VERSION_STRING = "20150418";
47 
48 /*
49 This source file is built up in the following large parts. The code sections
50 with the "LODEPNG_COMPILE_" #defines divide this up further in an intermixed way.
51 -Tools for C and common code for PNG and Zlib
52 -C Code for Zlib (huffman, deflate, ...)
53 -C Code for PNG (file format chunks, adam7, PNG filters, color conversions, ...)
54 -The C++ wrapper around all of the above
55 */
56 
57 /*The malloc, realloc and free functions defined here with "lodepng_" in front
58 of the name, so that you can easily change them to others related to your
59 platform if needed. Everything else in the code calls these. Pass
60 -DLODEPNG_NO_COMPILE_ALLOCATORS to the compiler, or comment out
61 #define LODEPNG_COMPILE_ALLOCATORS in the header, to disable the ones here and
62 define them in your own project's source files without needing to change
63 lodepng source code. Don't forget to remove "static" if you copypaste them
64 from here.*/
65 
66 #ifdef LODEPNG_COMPILE_ALLOCATORS
67 static void* lodepng_malloc(size_t size)
68 {
69  return malloc(size);
70 }
71 
72 static void* lodepng_realloc(void* ptr, size_t new_size)
73 {
74  return realloc(ptr, new_size);
75 }
76 
77 static void lodepng_free(void* ptr)
78 {
79  free(ptr);
80 }
81 #else /*LODEPNG_COMPILE_ALLOCATORS*/
82 void* lodepng_malloc(size_t size);
83 void* lodepng_realloc(void* ptr, size_t new_size);
84 void lodepng_free(void* ptr);
85 #endif /*LODEPNG_COMPILE_ALLOCATORS*/
86 
87 /* ////////////////////////////////////////////////////////////////////////// */
88 /* ////////////////////////////////////////////////////////////////////////// */
89 /* // Tools for C, and common code for PNG and Zlib. // */
90 /* ////////////////////////////////////////////////////////////////////////// */
91 /* ////////////////////////////////////////////////////////////////////////// */
92 
93 /*
94 Often in case of an error a value is assigned to a variable and then it breaks
95 out of a loop (to go to the cleanup phase of a function). This macro does that.
96 It makes the error handling code shorter and more readable.
97 
98 Example: if(!uivector_resizev(&frequencies_ll, 286, 0)) ERROR_BREAK(83);
99 */
100 #define CERROR_BREAK(errorvar, code)\
101 {\
102  errorvar = code;\
103  break;\
104 }
105 
106 /*version of CERROR_BREAK that assumes the common case where the error variable is named "error"*/
107 #define ERROR_BREAK(code) CERROR_BREAK(error, code)
108 
109 /*Set error var to the error code, and return it.*/
110 #define CERROR_RETURN_ERROR(errorvar, code)\
111 {\
112  errorvar = code;\
113  return code;\
114 }
115 
116 /*Try the code, if it returns error, also return the error.*/
117 #define CERROR_TRY_RETURN(call)\
118 {\
119  unsigned error = call;\
120  if(error) return error;\
121 }
122 
123 /*Set error var to the error code, and return from the void function.*/
124 #define CERROR_RETURN(errorvar, code)\
125 {\
126  errorvar = code;\
127  return;\
128 }
129 
130 /*
131 About uivector, ucvector and string:
132 -All of them wrap dynamic arrays or text strings in a similar way.
133 -LodePNG was originally written in C++. The vectors replace the std::vectors that were used in the C++ version.
134 -The string tools are made to avoid problems with compilers that declare things like strncat as deprecated.
135 -They're not used in the interface, only internally in this file as static functions.
136 -As with many other structs in this file, the init and cleanup functions serve as ctor and dtor.
137 */
138 
139 #ifdef LODEPNG_COMPILE_ZLIB
140 /*dynamic vector of unsigned ints*/
141 typedef struct uivector
142 {
143  unsigned* data;
144  size_t size; /*size in number of unsigned longs*/
145  size_t allocsize; /*allocated size in bytes*/
146 } uivector;
147 
148 static void uivector_cleanup(void* p)
149 {
150  ((uivector*)p)->size = ((uivector*)p)->allocsize = 0;
151  lodepng_free(((uivector*)p)->data);
152  ((uivector*)p)->data = NULL;
153 }
154 
155 /*returns 1 if success, 0 if failure ==> nothing done*/
156 static unsigned uivector_reserve(uivector* p, size_t allocsize)
157 {
158  if(allocsize > p->allocsize)
159  {
160  size_t newsize = (allocsize > p->allocsize * 2) ? allocsize : (allocsize * 3 / 2);
161  void* data = lodepng_realloc(p->data, newsize);
162  if(data)
163  {
164  p->allocsize = newsize;
165  p->data = (unsigned*)data;
166  }
167  else return 0; /*error: not enough memory*/
168  }
169  return 1;
170 }
171 
172 /*returns 1 if success, 0 if failure ==> nothing done*/
173 static unsigned uivector_resize(uivector* p, size_t size)
174 {
175  if(!uivector_reserve(p, size * sizeof(unsigned))) return 0;
176  p->size = size;
177  return 1; /*success*/
178 }
179 
180 /*resize and give all new elements the value*/
181 static unsigned uivector_resizev(uivector* p, size_t size, unsigned value)
182 {
183  size_t oldsize = p->size, i;
184  if(!uivector_resize(p, size)) return 0;
185  for(i = oldsize; i < size; ++i) p->data[i] = value;
186  return 1;
187 }
188 
189 static void uivector_init(uivector* p)
190 {
191  p->data = NULL;
192  p->size = p->allocsize = 0;
193 }
194 
195 #ifdef LODEPNG_COMPILE_ENCODER
196 /*returns 1 if success, 0 if failure ==> nothing done*/
197 static unsigned uivector_push_back(uivector* p, unsigned c)
198 {
199  if(!uivector_resize(p, p->size + 1)) return 0;
200  p->data[p->size - 1] = c;
201  return 1;
202 }
203 #endif /*LODEPNG_COMPILE_ENCODER*/
204 #endif /*LODEPNG_COMPILE_ZLIB*/
205 
206 /* /////////////////////////////////////////////////////////////////////////// */
207 
208 /*dynamic vector of unsigned chars*/
209 typedef struct ucvector
210 {
211  unsigned char* data;
212  size_t size; /*used size*/
213  size_t allocsize; /*allocated size*/
214 } ucvector;
215 
216 /*returns 1 if success, 0 if failure ==> nothing done*/
217 static unsigned ucvector_reserve(ucvector* p, size_t allocsize)
218 {
219  if(allocsize > p->allocsize)
220  {
221  size_t newsize = (allocsize > p->allocsize * 2) ? allocsize : (allocsize * 3 / 2);
222  void* data = lodepng_realloc(p->data, newsize);
223  if(data)
224  {
225  p->allocsize = newsize;
226  p->data = (unsigned char*)data;
227  }
228  else return 0; /*error: not enough memory*/
229  }
230  return 1;
231 }
232 
233 /*returns 1 if success, 0 if failure ==> nothing done*/
234 static unsigned ucvector_resize(ucvector* p, size_t size)
235 {
236  if(!ucvector_reserve(p, size * sizeof(unsigned char))) return 0;
237  p->size = size;
238  return 1; /*success*/
239 }
240 
241 #ifdef LODEPNG_COMPILE_PNG
242 
243 static void ucvector_cleanup(void* p)
244 {
245  ((ucvector*)p)->size = ((ucvector*)p)->allocsize = 0;
246  lodepng_free(((ucvector*)p)->data);
247  ((ucvector*)p)->data = NULL;
248 }
249 
250 static void ucvector_init(ucvector* p)
251 {
252  p->data = NULL;
253  p->size = p->allocsize = 0;
254 }
255 
256 #ifdef LODEPNG_COMPILE_DECODER
257 /*resize and give all new elements the value*/
258 static unsigned ucvector_resizev(ucvector* p, size_t size, unsigned char value)
259 {
260  size_t oldsize = p->size, i;
261  if(!ucvector_resize(p, size)) return 0;
262  for(i = oldsize; i < size; ++i) p->data[i] = value;
263  return 1;
264 }
265 #endif /*LODEPNG_COMPILE_DECODER*/
266 #endif /*LODEPNG_COMPILE_PNG*/
267 
268 #ifdef LODEPNG_COMPILE_ZLIB
269 /*you can both convert from vector to buffer&size and vica versa. If you use
270 init_buffer to take over a buffer and size, it is not needed to use cleanup*/
271 static void ucvector_init_buffer(ucvector* p, unsigned char* buffer, size_t size)
272 {
273  p->data = buffer;
274  p->allocsize = p->size = size;
275 }
276 #endif /*LODEPNG_COMPILE_ZLIB*/
277 
278 #if (defined(LODEPNG_COMPILE_PNG) && defined(LODEPNG_COMPILE_ANCILLARY_CHUNKS)) || defined(LODEPNG_COMPILE_ENCODER)
279 /*returns 1 if success, 0 if failure ==> nothing done*/
280 static unsigned ucvector_push_back(ucvector* p, unsigned char c)
281 {
282  if(!ucvector_resize(p, p->size + 1)) return 0;
283  p->data[p->size - 1] = c;
284  return 1;
285 }
286 #endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
287 
288 
289 /* ////////////////////////////////////////////////////////////////////////// */
290 
291 #ifdef LODEPNG_COMPILE_PNG
292 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
293 /*returns 1 if success, 0 if failure ==> nothing done*/
294 static unsigned string_resize(char** out, size_t size)
295 {
296  char* data = (char*)lodepng_realloc(*out, size + 1);
297  if(data)
298  {
299  data[size] = 0; /*null termination char*/
300  *out = data;
301  }
302  return data != 0;
303 }
304 
305 /*init a {char*, size_t} pair for use as string*/
306 static void string_init(char** out)
307 {
308  *out = NULL;
309  string_resize(out, 0);
310 }
311 
312 /*free the above pair again*/
313 static void string_cleanup(char** out)
314 {
315  lodepng_free(*out);
316  *out = NULL;
317 }
318 
319 static void string_set(char** out, const char* in)
320 {
321  size_t insize = strlen(in), i;
322  if(string_resize(out, insize))
323  {
324  for(i = 0; i != insize; ++i)
325  {
326  (*out)[i] = in[i];
327  }
328  }
329 }
330 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
331 #endif /*LODEPNG_COMPILE_PNG*/
332 
333 /* ////////////////////////////////////////////////////////////////////////// */
334 
335 unsigned lodepng_read32bitInt(const unsigned char* buffer)
336 {
337  return (unsigned)((buffer[0] << 24) | (buffer[1] << 16) | (buffer[2] << 8) | buffer[3]);
338 }
339 
340 #if defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)
341 /*buffer must have at least 4 allocated bytes available*/
342 static void lodepng_set32bitInt(unsigned char* buffer, unsigned value)
343 {
344  buffer[0] = (unsigned char)((value >> 24) & 0xff);
345  buffer[1] = (unsigned char)((value >> 16) & 0xff);
346  buffer[2] = (unsigned char)((value >> 8) & 0xff);
347  buffer[3] = (unsigned char)((value ) & 0xff);
348 }
349 #endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
350 
351 #ifdef LODEPNG_COMPILE_ENCODER
352 static void lodepng_add32bitInt(ucvector* buffer, unsigned value)
353 {
354  ucvector_resize(buffer, buffer->size + 4); /*todo: give error if resize failed*/
355  lodepng_set32bitInt(&buffer->data[buffer->size - 4], value);
356 }
357 #endif /*LODEPNG_COMPILE_ENCODER*/
358 
359 /* ////////////////////////////////////////////////////////////////////////// */
360 /* / File IO / */
361 /* ////////////////////////////////////////////////////////////////////////// */
362 
363 #ifdef LODEPNG_COMPILE_DISK
364 
365 unsigned lodepng_load_file(unsigned char** out, size_t* outsize, const char* filename)
366 {
367  FILE* file;
368  long size;
369 
370  /*provide some proper output values if error will happen*/
371  *out = 0;
372  *outsize = 0;
373 
374  file = fopen(filename, "rb");
375  if(!file) return 78;
376 
377  /*get filesize:*/
378  fseek(file , 0 , SEEK_END);
379  size = ftell(file);
380  rewind(file);
381 
382  /*read contents of the file into the vector*/
383  *outsize = 0;
384  *out = (unsigned char*)lodepng_malloc((size_t)size);
385  if(size && (*out)) (*outsize) = fread(*out, 1, (size_t)size, file);
386 
387  fclose(file);
388  if(!(*out) && size) return 83; /*the above malloc failed*/
389  return 0;
390 }
391 
392 /*write given buffer to the file, overwriting the file, it doesn't append to it.*/
393 unsigned lodepng_save_file(const unsigned char* buffer, size_t buffersize, const char* filename)
394 {
395  FILE* file;
396  file = fopen(filename, "wb" );
397  if(!file) return 79;
398  fwrite((char*)buffer , 1 , buffersize, file);
399  fclose(file);
400  return 0;
401 }
402 
403 #endif /*LODEPNG_COMPILE_DISK*/
404 
405 /* ////////////////////////////////////////////////////////////////////////// */
406 /* ////////////////////////////////////////////////////////////////////////// */
407 /* // End of common code and tools. Begin of Zlib related code. // */
408 /* ////////////////////////////////////////////////////////////////////////// */
409 /* ////////////////////////////////////////////////////////////////////////// */
410 
411 #ifdef LODEPNG_COMPILE_ZLIB
412 #ifdef LODEPNG_COMPILE_ENCODER
413 /*TODO: this ignores potential out of memory errors*/
414 #define addBitToStream(/*size_t**/ bitpointer, /*ucvector**/ bitstream, /*unsigned char*/ bit)\
415 {\
416  /*add a new byte at the end*/\
417  if(((*bitpointer) & 7) == 0) ucvector_push_back(bitstream, (unsigned char)0);\
418  /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/\
419  (bitstream->data[bitstream->size - 1]) |= (bit << ((*bitpointer) & 0x7));\
420  ++(*bitpointer);\
421 }
422 
423 static void addBitsToStream(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
424 {
425  size_t i;
426  for(i = 0; i != nbits; ++i) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> i) & 1));
427 }
428 
429 static void addBitsToStreamReversed(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
430 {
431  size_t i;
432  for(i = 0; i != nbits; ++i) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> (nbits - 1 - i)) & 1));
433 }
434 #endif /*LODEPNG_COMPILE_ENCODER*/
435 
436 #ifdef LODEPNG_COMPILE_DECODER
437 
438 #define READBIT(bitpointer, bitstream) ((bitstream[bitpointer >> 3] >> (bitpointer & 0x7)) & (unsigned char)1)
439 
440 static unsigned char readBitFromStream(size_t* bitpointer, const unsigned char* bitstream)
441 {
442  unsigned char result = (unsigned char)(READBIT(*bitpointer, bitstream));
443  ++(*bitpointer);
444  return result;
445 }
446 
447 static unsigned readBitsFromStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
448 {
449  unsigned result = 0, i;
450  for(i = 0; i != nbits; ++i)
451  {
452  result += ((unsigned)READBIT(*bitpointer, bitstream)) << i;
453  ++(*bitpointer);
454  }
455  return result;
456 }
457 #endif /*LODEPNG_COMPILE_DECODER*/
458 
459 /* ////////////////////////////////////////////////////////////////////////// */
460 /* / Deflate - Huffman / */
461 /* ////////////////////////////////////////////////////////////////////////// */
462 
463 #define FIRST_LENGTH_CODE_INDEX 257
464 #define LAST_LENGTH_CODE_INDEX 285
465 /*256 literals, the end code, some length codes, and 2 unused codes*/
466 #define NUM_DEFLATE_CODE_SYMBOLS 288
467 /*the distance codes have their own symbols, 30 used, 2 unused*/
468 #define NUM_DISTANCE_SYMBOLS 32
469 /*the code length codes. 0-15: code lengths, 16: copy previous 3-6 times, 17: 3-10 zeros, 18: 11-138 zeros*/
470 #define NUM_CODE_LENGTH_CODES 19
471 
472 /*the base lengths represented by codes 257-285*/
473 static const unsigned LENGTHBASE[29]
474  = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
475  67, 83, 99, 115, 131, 163, 195, 227, 258};
476 
477 /*the extra bits used by codes 257-285 (added to base length)*/
478 static const unsigned LENGTHEXTRA[29]
479  = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
480  4, 4, 4, 4, 5, 5, 5, 5, 0};
481 
482 /*the base backwards distances (the bits of distance codes appear after length codes and use their own huffman tree)*/
483 static const unsigned DISTANCEBASE[30]
484  = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
485  769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
486 
487 /*the extra bits of backwards distances (added to base)*/
488 static const unsigned DISTANCEEXTRA[30]
489  = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8,
490  8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13};
491 
492 /*the order in which "code length alphabet code lengths" are stored, out of this
493 the huffman tree of the dynamic huffman tree lengths is generated*/
494 static const unsigned CLCL_ORDER[NUM_CODE_LENGTH_CODES]
495  = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
496 
497 /* ////////////////////////////////////////////////////////////////////////// */
498 
499 /*
500 Huffman tree struct, containing multiple representations of the tree
501 */
502 typedef struct HuffmanTree
503 {
504  unsigned* tree2d;
505  unsigned* tree1d;
506  unsigned* lengths; /*the lengths of the codes of the 1d-tree*/
507  unsigned maxbitlen; /*maximum number of bits a single code can get*/
508  unsigned numcodes; /*number of symbols in the alphabet = number of codes*/
509 } HuffmanTree;
510 
511 /*function used for debug purposes to draw the tree in ascii art with C++*/
512 /*
513 static void HuffmanTree_draw(HuffmanTree* tree)
514 {
515  std::cout << "tree. length: " << tree->numcodes << " maxbitlen: " << tree->maxbitlen << std::endl;
516  for(size_t i = 0; i != tree->tree1d.size; ++i)
517  {
518  if(tree->lengths.data[i])
519  std::cout << i << " " << tree->tree1d.data[i] << " " << tree->lengths.data[i] << std::endl;
520  }
521  std::cout << std::endl;
522 }*/
523 
524 static void HuffmanTree_init(HuffmanTree* tree)
525 {
526  tree->tree2d = 0;
527  tree->tree1d = 0;
528  tree->lengths = 0;
529 }
530 
531 static void HuffmanTree_cleanup(HuffmanTree* tree)
532 {
533  lodepng_free(tree->tree2d);
534  lodepng_free(tree->tree1d);
535  lodepng_free(tree->lengths);
536 }
537 
538 /*the tree representation used by the decoder. return value is error*/
539 static unsigned HuffmanTree_make2DTree(HuffmanTree* tree)
540 {
541  unsigned nodefilled = 0; /*up to which node it is filled*/
542  unsigned treepos = 0; /*position in the tree (1 of the numcodes columns)*/
543  unsigned n, i;
544 
545  tree->tree2d = (unsigned*)lodepng_malloc(tree->numcodes * 2 * sizeof(unsigned));
546  if(!tree->tree2d) return 83; /*alloc fail*/
547 
548  /*
549  convert tree1d[] to tree2d[][]. In the 2D array, a value of 32767 means
550  uninited, a value >= numcodes is an address to another bit, a value < numcodes
551  is a code. The 2 rows are the 2 possible bit values (0 or 1), there are as
552  many columns as codes - 1.
553  A good huffmann tree has N * 2 - 1 nodes, of which N - 1 are internal nodes.
554  Here, the internal nodes are stored (what their 0 and 1 option point to).
555  There is only memory for such good tree currently, if there are more nodes
556  (due to too long length codes), error 55 will happen
557  */
558  for(n = 0; n < tree->numcodes * 2; ++n)
559  {
560  tree->tree2d[n] = 32767; /*32767 here means the tree2d isn't filled there yet*/
561  }
562 
563  for(n = 0; n < tree->numcodes; ++n) /*the codes*/
564  {
565  for(i = 0; i != tree->lengths[n]; ++i) /*the bits for this code*/
566  {
567  unsigned char bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1);
568  /*oversubscribed, see comment in lodepng_error_text*/
569  if(treepos > 2147483647 || treepos + 2 > tree->numcodes) return 55;
570  if(tree->tree2d[2 * treepos + bit] == 32767) /*not yet filled in*/
571  {
572  if(i + 1 == tree->lengths[n]) /*last bit*/
573  {
574  tree->tree2d[2 * treepos + bit] = n; /*put the current code in it*/
575  treepos = 0;
576  }
577  else
578  {
579  /*put address of the next step in here, first that address has to be found of course
580  (it's just nodefilled + 1)...*/
581  ++nodefilled;
582  /*addresses encoded with numcodes added to it*/
583  tree->tree2d[2 * treepos + bit] = nodefilled + tree->numcodes;
584  treepos = nodefilled;
585  }
586  }
587  else treepos = tree->tree2d[2 * treepos + bit] - tree->numcodes;
588  }
589  }
590 
591  for(n = 0; n < tree->numcodes * 2; ++n)
592  {
593  if(tree->tree2d[n] == 32767) tree->tree2d[n] = 0; /*remove possible remaining 32767's*/
594  }
595 
596  return 0;
597 }
598 
599 /*
600 Second step for the ...makeFromLengths and ...makeFromFrequencies functions.
601 numcodes, lengths and maxbitlen must already be filled in correctly. return
602 value is error.
603 */
604 static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree)
605 {
606  uivector blcount;
607  uivector nextcode;
608  unsigned error = 0;
609  unsigned bits, n;
610 
611  uivector_init(&blcount);
612  uivector_init(&nextcode);
613 
614  tree->tree1d = (unsigned*)lodepng_malloc(tree->numcodes * sizeof(unsigned));
615  if(!tree->tree1d) error = 83; /*alloc fail*/
616 
617  if(!uivector_resizev(&blcount, tree->maxbitlen + 1, 0)
618  || !uivector_resizev(&nextcode, tree->maxbitlen + 1, 0))
619  error = 83; /*alloc fail*/
620 
621  if(!error)
622  {
623  /*step 1: count number of instances of each code length*/
624  for(bits = 0; bits != tree->numcodes; ++bits) ++blcount.data[tree->lengths[bits]];
625  /*step 2: generate the nextcode values*/
626  for(bits = 1; bits <= tree->maxbitlen; ++bits)
627  {
628  nextcode.data[bits] = (nextcode.data[bits - 1] + blcount.data[bits - 1]) << 1;
629  }
630  /*step 3: generate all the codes*/
631  for(n = 0; n != tree->numcodes; ++n)
632  {
633  if(tree->lengths[n] != 0) tree->tree1d[n] = nextcode.data[tree->lengths[n]]++;
634  }
635  }
636 
637  uivector_cleanup(&blcount);
638  uivector_cleanup(&nextcode);
639 
640  if(!error) return HuffmanTree_make2DTree(tree);
641  else return error;
642 }
643 
644 /*
645 given the code lengths (as stored in the PNG file), generate the tree as defined
646 by Deflate. maxbitlen is the maximum bits that a code in the tree can have.
647 return value is error.
648 */
649 static unsigned HuffmanTree_makeFromLengths(HuffmanTree* tree, const unsigned* bitlen,
650  size_t numcodes, unsigned maxbitlen)
651 {
652  unsigned i;
653  tree->lengths = (unsigned*)lodepng_malloc(numcodes * sizeof(unsigned));
654  if(!tree->lengths) return 83; /*alloc fail*/
655  for(i = 0; i != numcodes; ++i) tree->lengths[i] = bitlen[i];
656  tree->numcodes = (unsigned)numcodes; /*number of symbols*/
657  tree->maxbitlen = maxbitlen;
658  return HuffmanTree_makeFromLengths2(tree);
659 }
660 
661 #ifdef LODEPNG_COMPILE_ENCODER
662 
663 /*BPM: Boundary Package Merge, see "A Fast and Space-Economical Algorithm for Length-Limited Coding",
664 Jyrki Katajainen, Alistair Moffat, Andrew Turpin, 1995.*/
665 
666 /*chain node for boundary package merge*/
667 typedef struct BPMNode
668 {
669  int weight; /*the sum of all weights in this chain*/
670  unsigned index; /*index of this leaf node (called "count" in the paper)*/
671  struct BPMNode* tail; /*the next nodes in this chain (null if last)*/
672  int in_use;
673 } BPMNode;
674 
675 /*lists of chains*/
676 typedef struct BPMLists
677 {
678  /*memory pool*/
679  unsigned memsize;
680  BPMNode* memory;
681  unsigned numfree;
682  unsigned nextfree;
683  BPMNode** freelist;
684  /*two heads of lookahead chains per list*/
685  unsigned listsize;
686  BPMNode** chains0;
687  BPMNode** chains1;
688 } BPMLists;
689 
690 /*creates a new chain node with the given parameters, from the memory in the lists */
691 static BPMNode* bpmnode_create(BPMLists* lists, int weight, unsigned index, BPMNode* tail)
692 {
693  unsigned i;
694  BPMNode* result;
695 
696  /*memory full, so garbage collect*/
697  if(lists->nextfree >= lists->numfree)
698  {
699  /*mark only those that are in use*/
700  for(i = 0; i != lists->memsize; ++i) lists->memory[i].in_use = 0;
701  for(i = 0; i != lists->listsize; ++i)
702  {
703  BPMNode* node;
704  for(node = lists->chains0[i]; node != 0; node = node->tail) node->in_use = 1;
705  for(node = lists->chains1[i]; node != 0; node = node->tail) node->in_use = 1;
706  }
707  /*collect those that are free*/
708  lists->numfree = 0;
709  for(i = 0; i != lists->memsize; ++i)
710  {
711  if(!lists->memory[i].in_use) lists->freelist[lists->numfree++] = &lists->memory[i];
712  }
713  lists->nextfree = 0;
714  }
715 
716  result = lists->freelist[lists->nextfree++];
717  result->weight = weight;
718  result->index = index;
719  result->tail = tail;
720  return result;
721 }
722 
723 static int bpmnode_compare(const void* a, const void* b)
724 {
725  int wa = ((const BPMNode*)a)->weight;
726  int wb = ((const BPMNode*)b)->weight;
727  if(wa < wb) return -1;
728  if(wa > wb) return 1;
729  /*make the qsort a stable sort*/
730  return ((const BPMNode*)a)->index < ((const BPMNode*)b)->index ? 1 : -1;
731 }
732 
733 /*Boundary Package Merge step, numpresent is the amount of leaves, and c is the current chain.*/
734 static void boundaryPM(BPMLists* lists, BPMNode* leaves, size_t numpresent, int c, int num)
735 {
736  unsigned lastindex = lists->chains1[c]->index;
737 
738  if(c == 0)
739  {
740  if(lastindex >= numpresent) return;
741  lists->chains0[c] = lists->chains1[c];
742  lists->chains1[c] = bpmnode_create(lists, leaves[lastindex].weight, lastindex + 1, 0);
743  }
744  else
745  {
746  /*sum of the weights of the head nodes of the previous lookahead chains.*/
747  int sum = lists->chains0[c - 1]->weight + lists->chains1[c - 1]->weight;
748  lists->chains0[c] = lists->chains1[c];
749  if(lastindex < numpresent && sum > leaves[lastindex].weight)
750  {
751  lists->chains1[c] = bpmnode_create(lists, leaves[lastindex].weight, lastindex + 1, lists->chains1[c]->tail);
752  return;
753  }
754  lists->chains1[c] = bpmnode_create(lists, sum, lastindex, lists->chains1[c - 1]);
755  /*in the end we are only interested in the chain of the last list, so no
756  need to recurse if we're at the last one (this gives measurable speedup)*/
757  if(num + 1 < (int)(2 * numpresent - 2))
758  {
759  boundaryPM(lists, leaves, numpresent, c - 1, num);
760  boundaryPM(lists, leaves, numpresent, c - 1, num);
761  }
762  }
763 }
764 
765 unsigned lodepng_huffman_code_lengths(unsigned* lengths, const unsigned* frequencies,
766  size_t numcodes, unsigned maxbitlen)
767 {
768  unsigned error = 0;
769  unsigned i;
770  size_t numpresent = 0; /*number of symbols with non-zero frequency*/
771  BPMNode* leaves; /*the symbols, only those with > 0 frequency*/
772 
773  if(numcodes == 0) return 80; /*error: a tree of 0 symbols is not supposed to be made*/
774  if((1u << maxbitlen) < numcodes) return 80; /*error: represent all symbols*/
775 
776  leaves = (BPMNode*)lodepng_malloc(numcodes * sizeof(*leaves));
777  if(!leaves) return 83; /*alloc fail*/
778 
779  for(i = 0; i != numcodes; ++i)
780  {
781  if(frequencies[i] > 0)
782  {
783  leaves[numpresent].weight = frequencies[i];
784  leaves[numpresent].index = i;
785  ++numpresent;
786  }
787  }
788 
789  for(i = 0; i != numcodes; ++i) lengths[i] = 0;
790 
791  /*ensure at least two present symbols. There should be at least one symbol
792  according to RFC 1951 section 3.2.7. Some decoders incorrectly require two. To
793  make these work as well ensure there are at least two symbols. The
794  Package-Merge code below also doesn't work correctly if there's only one
795  symbol, it'd give it the theoritical 0 bits but in practice zlib wants 1 bit*/
796  if(numpresent == 0)
797  {
798  lengths[0] = lengths[1] = 1; /*note that for RFC 1951 section 3.2.7, only lengths[0] = 1 is needed*/
799  }
800  else if(numpresent == 1)
801  {
802  lengths[leaves[0].index] = 1;
803  lengths[leaves[0].index == 0 ? 1 : 0] = 1;
804  }
805  else
806  {
807  BPMLists lists;
808  BPMNode* node;
809 
810  qsort(leaves, numpresent, sizeof(BPMNode), bpmnode_compare);
811 
812  lists.listsize = maxbitlen;
813  lists.memsize = 2 * maxbitlen * (maxbitlen + 1);
814  lists.nextfree = 0;
815  lists.numfree = lists.memsize;
816  lists.memory = (BPMNode*)lodepng_malloc(lists.memsize * sizeof(*lists.memory));
817  lists.freelist = (BPMNode**)lodepng_malloc(lists.memsize * sizeof(BPMNode*));
818  lists.chains0 = (BPMNode**)lodepng_malloc(lists.listsize * sizeof(BPMNode*));
819  lists.chains1 = (BPMNode**)lodepng_malloc(lists.listsize * sizeof(BPMNode*));
820  if(!lists.memory || !lists.freelist || !lists.chains0 || !lists.chains1) error = 83; /*alloc fail*/
821 
822  if(!error)
823  {
824  for(i = 0; i != lists.memsize; ++i) lists.freelist[i] = &lists.memory[i];
825 
826  bpmnode_create(&lists, leaves[0].weight, 1, 0);
827  bpmnode_create(&lists, leaves[1].weight, 2, 0);
828 
829  for(i = 0; i != lists.listsize; ++i)
830  {
831  lists.chains0[i] = &lists.memory[0];
832  lists.chains1[i] = &lists.memory[1];
833  }
834 
835  /*each boundaryPM call adds one chain to the last list, and we need 2 * numpresent - 2 chains.*/
836  for(i = 2; i != 2 * numpresent - 2; ++i) boundaryPM(&lists, leaves, numpresent, maxbitlen - 1, i);
837 
838  for(node = lists.chains1[maxbitlen - 1]; node; node = node->tail)
839  {
840  for(i = 0; i != node->index; ++i) ++lengths[leaves[i].index];
841  }
842  }
843 
844  lodepng_free(lists.memory);
845  lodepng_free(lists.freelist);
846  lodepng_free(lists.chains0);
847  lodepng_free(lists.chains1);
848  }
849 
850  lodepng_free(leaves);
851  return error;
852 }
853 
854 /*Create the Huffman tree given the symbol frequencies*/
855 static unsigned HuffmanTree_makeFromFrequencies(HuffmanTree* tree, const unsigned* frequencies,
856  size_t mincodes, size_t numcodes, unsigned maxbitlen)
857 {
858  unsigned error = 0;
859  while(!frequencies[numcodes - 1] && numcodes > mincodes) --numcodes; /*trim zeroes*/
860  tree->maxbitlen = maxbitlen;
861  tree->numcodes = (unsigned)numcodes; /*number of symbols*/
862  tree->lengths = (unsigned*)lodepng_realloc(tree->lengths, numcodes * sizeof(unsigned));
863  if(!tree->lengths) return 83; /*alloc fail*/
864  /*initialize all lengths to 0*/
865  memset(tree->lengths, 0, numcodes * sizeof(unsigned));
866 
867  error = lodepng_huffman_code_lengths(tree->lengths, frequencies, numcodes, maxbitlen);
868  if(!error) error = HuffmanTree_makeFromLengths2(tree);
869  return error;
870 }
871 
872 static unsigned HuffmanTree_getCode(const HuffmanTree* tree, unsigned index)
873 {
874  return tree->tree1d[index];
875 }
876 
877 static unsigned HuffmanTree_getLength(const HuffmanTree* tree, unsigned index)
878 {
879  return tree->lengths[index];
880 }
881 #endif /*LODEPNG_COMPILE_ENCODER*/
882 
883 /*get the literal and length code tree of a deflated block with fixed tree, as per the deflate specification*/
884 static unsigned generateFixedLitLenTree(HuffmanTree* tree)
885 {
886  unsigned i, error = 0;
887  unsigned* bitlen = (unsigned*)lodepng_malloc(NUM_DEFLATE_CODE_SYMBOLS * sizeof(unsigned));
888  if(!bitlen) return 83; /*alloc fail*/
889 
890  /*288 possible codes: 0-255=literals, 256=endcode, 257-285=lengthcodes, 286-287=unused*/
891  for(i = 0; i <= 143; ++i) bitlen[i] = 8;
892  for(i = 144; i <= 255; ++i) bitlen[i] = 9;
893  for(i = 256; i <= 279; ++i) bitlen[i] = 7;
894  for(i = 280; i <= 287; ++i) bitlen[i] = 8;
895 
896  error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DEFLATE_CODE_SYMBOLS, 15);
897 
898  lodepng_free(bitlen);
899  return error;
900 }
901 
902 /*get the distance code tree of a deflated block with fixed tree, as specified in the deflate specification*/
903 static unsigned generateFixedDistanceTree(HuffmanTree* tree)
904 {
905  unsigned i, error = 0;
906  unsigned* bitlen = (unsigned*)lodepng_malloc(NUM_DISTANCE_SYMBOLS * sizeof(unsigned));
907  if(!bitlen) return 83; /*alloc fail*/
908 
909  /*there are 32 distance codes, but 30-31 are unused*/
910  for(i = 0; i != NUM_DISTANCE_SYMBOLS; ++i) bitlen[i] = 5;
911  error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DISTANCE_SYMBOLS, 15);
912 
913  lodepng_free(bitlen);
914  return error;
915 }
916 
917 #ifdef LODEPNG_COMPILE_DECODER
918 
919 /*
920 returns the code, or (unsigned)(-1) if error happened
921 inbitlength is the length of the complete buffer, in bits (so its byte length times 8)
922 */
923 static unsigned huffmanDecodeSymbol(const unsigned char* in, size_t* bp,
924  const HuffmanTree* codetree, size_t inbitlength)
925 {
926  unsigned treepos = 0, ct;
927  for(;;)
928  {
929  if(*bp >= inbitlength) return (unsigned)(-1); /*error: end of input memory reached without endcode*/
930  /*
931  decode the symbol from the tree. The "readBitFromStream" code is inlined in
932  the expression below because this is the biggest bottleneck while decoding
933  */
934  ct = codetree->tree2d[(treepos << 1) + READBIT(*bp, in)];
935  ++(*bp);
936  if(ct < codetree->numcodes) return ct; /*the symbol is decoded, return it*/
937  else treepos = ct - codetree->numcodes; /*symbol not yet decoded, instead move tree position*/
938 
939  if(treepos >= codetree->numcodes) return (unsigned)(-1); /*error: it appeared outside the codetree*/
940  }
941 }
942 #endif /*LODEPNG_COMPILE_DECODER*/
943 
944 #ifdef LODEPNG_COMPILE_DECODER
945 
946 /* ////////////////////////////////////////////////////////////////////////// */
947 /* / Inflator (Decompressor) / */
948 /* ////////////////////////////////////////////////////////////////////////// */
949 
950 /*get the tree of a deflated block with fixed tree, as specified in the deflate specification*/
951 static void getTreeInflateFixed(HuffmanTree* tree_ll, HuffmanTree* tree_d)
952 {
953  /*TODO: check for out of memory errors*/
954  generateFixedLitLenTree(tree_ll);
955  generateFixedDistanceTree(tree_d);
956 }
957 
958 /*get the tree of a deflated block with dynamic tree, the tree itself is also Huffman compressed with a known tree*/
959 static unsigned getTreeInflateDynamic(HuffmanTree* tree_ll, HuffmanTree* tree_d,
960  const unsigned char* in, size_t* bp, size_t inlength)
961 {
962  /*make sure that length values that aren't filled in will be 0, or a wrong tree will be generated*/
963  unsigned error = 0;
964  unsigned n, HLIT, HDIST, HCLEN, i;
965  size_t inbitlength = inlength * 8;
966 
967  /*see comments in deflateDynamic for explanation of the context and these variables, it is analogous*/
968  unsigned* bitlen_ll = 0; /*lit,len code lengths*/
969  unsigned* bitlen_d = 0; /*dist code lengths*/
970  /*code length code lengths ("clcl"), the bit lengths of the huffman tree used to compress bitlen_ll and bitlen_d*/
971  unsigned* bitlen_cl = 0;
972  HuffmanTree tree_cl; /*the code tree for code length codes (the huffman tree for compressed huffman trees)*/
973 
974  if((*bp) + 14 > (inlength << 3)) return 49; /*error: the bit pointer is or will go past the memory*/
975 
976  /*number of literal/length codes + 257. Unlike the spec, the value 257 is added to it here already*/
977  HLIT = readBitsFromStream(bp, in, 5) + 257;
978  /*number of distance codes. Unlike the spec, the value 1 is added to it here already*/
979  HDIST = readBitsFromStream(bp, in, 5) + 1;
980  /*number of code length codes. Unlike the spec, the value 4 is added to it here already*/
981  HCLEN = readBitsFromStream(bp, in, 4) + 4;
982 
983  if((*bp) + HCLEN * 3 > (inlength << 3)) return 50; /*error: the bit pointer is or will go past the memory*/
984 
985  HuffmanTree_init(&tree_cl);
986 
987  while(!error)
988  {
989  /*read the code length codes out of 3 * (amount of code length codes) bits*/
990 
991  bitlen_cl = (unsigned*)lodepng_malloc(NUM_CODE_LENGTH_CODES * sizeof(unsigned));
992  if(!bitlen_cl) ERROR_BREAK(83 /*alloc fail*/);
993 
994  for(i = 0; i != NUM_CODE_LENGTH_CODES; ++i)
995  {
996  if(i < HCLEN) bitlen_cl[CLCL_ORDER[i]] = readBitsFromStream(bp, in, 3);
997  else bitlen_cl[CLCL_ORDER[i]] = 0; /*if not, it must stay 0*/
998  }
999 
1000  error = HuffmanTree_makeFromLengths(&tree_cl, bitlen_cl, NUM_CODE_LENGTH_CODES, 7);
1001  if(error) break;
1002 
1003  /*now we can use this tree to read the lengths for the tree that this function will return*/
1004  bitlen_ll = (unsigned*)lodepng_malloc(NUM_DEFLATE_CODE_SYMBOLS * sizeof(unsigned));
1005  bitlen_d = (unsigned*)lodepng_malloc(NUM_DISTANCE_SYMBOLS * sizeof(unsigned));
1006  if(!bitlen_ll || !bitlen_d) ERROR_BREAK(83 /*alloc fail*/);
1007  for(i = 0; i != NUM_DEFLATE_CODE_SYMBOLS; ++i) bitlen_ll[i] = 0;
1008  for(i = 0; i != NUM_DISTANCE_SYMBOLS; ++i) bitlen_d[i] = 0;
1009 
1010  /*i is the current symbol we're reading in the part that contains the code lengths of lit/len and dist codes*/
1011  i = 0;
1012  while(i < HLIT + HDIST)
1013  {
1014  unsigned code = huffmanDecodeSymbol(in, bp, &tree_cl, inbitlength);
1015  if(code <= 15) /*a length code*/
1016  {
1017  if(i < HLIT) bitlen_ll[i] = code;
1018  else bitlen_d[i - HLIT] = code;
1019  ++i;
1020  }
1021  else if(code == 16) /*repeat previous*/
1022  {
1023  unsigned replength = 3; /*read in the 2 bits that indicate repeat length (3-6)*/
1024  unsigned value; /*set value to the previous code*/
1025 
1026  if(i == 0) ERROR_BREAK(54); /*can't repeat previous if i is 0*/
1027 
1028  if((*bp + 2) > inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
1029  replength += readBitsFromStream(bp, in, 2);
1030 
1031  if(i < HLIT + 1) value = bitlen_ll[i - 1];
1032  else value = bitlen_d[i - HLIT - 1];
1033  /*repeat this value in the next lengths*/
1034  for(n = 0; n < replength; ++n)
1035  {
1036  if(i >= HLIT + HDIST) ERROR_BREAK(13); /*error: i is larger than the amount of codes*/
1037  if(i < HLIT) bitlen_ll[i] = value;
1038  else bitlen_d[i - HLIT] = value;
1039  ++i;
1040  }
1041  }
1042  else if(code == 17) /*repeat "0" 3-10 times*/
1043  {
1044  unsigned replength = 3; /*read in the bits that indicate repeat length*/
1045  if((*bp + 3) > inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
1046  replength += readBitsFromStream(bp, in, 3);
1047 
1048  /*repeat this value in the next lengths*/
1049  for(n = 0; n < replength; ++n)
1050  {
1051  if(i >= HLIT + HDIST) ERROR_BREAK(14); /*error: i is larger than the amount of codes*/
1052 
1053  if(i < HLIT) bitlen_ll[i] = 0;
1054  else bitlen_d[i - HLIT] = 0;
1055  ++i;
1056  }
1057  }
1058  else if(code == 18) /*repeat "0" 11-138 times*/
1059  {
1060  unsigned replength = 11; /*read in the bits that indicate repeat length*/
1061  if((*bp + 7) > inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
1062  replength += readBitsFromStream(bp, in, 7);
1063 
1064  /*repeat this value in the next lengths*/
1065  for(n = 0; n < replength; ++n)
1066  {
1067  if(i >= HLIT + HDIST) ERROR_BREAK(15); /*error: i is larger than the amount of codes*/
1068 
1069  if(i < HLIT) bitlen_ll[i] = 0;
1070  else bitlen_d[i - HLIT] = 0;
1071  ++i;
1072  }
1073  }
1074  else /*if(code == (unsigned)(-1))*/ /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
1075  {
1076  if(code == (unsigned)(-1))
1077  {
1078  /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
1079  (10=no endcode, 11=wrong jump outside of tree)*/
1080  error = (*bp) > inbitlength ? 10 : 11;
1081  }
1082  else error = 16; /*unexisting code, this can never happen*/
1083  break;
1084  }
1085  }
1086  if(error) break;
1087 
1088  if(bitlen_ll[256] == 0) ERROR_BREAK(64); /*the length of the end code 256 must be larger than 0*/
1089 
1090  /*now we've finally got HLIT and HDIST, so generate the code trees, and the function is done*/
1091  error = HuffmanTree_makeFromLengths(tree_ll, bitlen_ll, NUM_DEFLATE_CODE_SYMBOLS, 15);
1092  if(error) break;
1093  error = HuffmanTree_makeFromLengths(tree_d, bitlen_d, NUM_DISTANCE_SYMBOLS, 15);
1094 
1095  break; /*end of error-while*/
1096  }
1097 
1098  lodepng_free(bitlen_cl);
1099  lodepng_free(bitlen_ll);
1100  lodepng_free(bitlen_d);
1101  HuffmanTree_cleanup(&tree_cl);
1102 
1103  return error;
1104 }
1105 
1106 /*inflate a block with dynamic of fixed Huffman tree*/
1107 static unsigned inflateHuffmanBlock(ucvector* out, const unsigned char* in, size_t* bp,
1108  size_t* pos, size_t inlength, unsigned btype)
1109 {
1110  unsigned error = 0;
1111  HuffmanTree tree_ll; /*the huffman tree for literal and length codes*/
1112  HuffmanTree tree_d; /*the huffman tree for distance codes*/
1113  size_t inbitlength = inlength * 8;
1114 
1115  HuffmanTree_init(&tree_ll);
1116  HuffmanTree_init(&tree_d);
1117 
1118  if(btype == 1) getTreeInflateFixed(&tree_ll, &tree_d);
1119  else if(btype == 2) error = getTreeInflateDynamic(&tree_ll, &tree_d, in, bp, inlength);
1120 
1121  while(!error) /*decode all symbols until end reached, breaks at end code*/
1122  {
1123  /*code_ll is literal, length or end code*/
1124  unsigned code_ll = huffmanDecodeSymbol(in, bp, &tree_ll, inbitlength);
1125  if(code_ll <= 255) /*literal symbol*/
1126  {
1127  /*ucvector_push_back would do the same, but for some reason the two lines below run 10% faster*/
1128  if(!ucvector_resize(out, (*pos) + 1)) ERROR_BREAK(83 /*alloc fail*/);
1129  out->data[*pos] = (unsigned char)code_ll;
1130  ++(*pos);
1131  }
1132  else if(code_ll >= FIRST_LENGTH_CODE_INDEX && code_ll <= LAST_LENGTH_CODE_INDEX) /*length code*/
1133  {
1134  unsigned code_d, distance;
1135  unsigned numextrabits_l, numextrabits_d; /*extra bits for length and distance*/
1136  size_t start, forward, backward, length;
1137 
1138  /*part 1: get length base*/
1139  length = LENGTHBASE[code_ll - FIRST_LENGTH_CODE_INDEX];
1140 
1141  /*part 2: get extra bits and add the value of that to length*/
1142  numextrabits_l = LENGTHEXTRA[code_ll - FIRST_LENGTH_CODE_INDEX];
1143  if((*bp + numextrabits_l) > inbitlength) ERROR_BREAK(51); /*error, bit pointer will jump past memory*/
1144  length += readBitsFromStream(bp, in, numextrabits_l);
1145 
1146  /*part 3: get distance code*/
1147  code_d = huffmanDecodeSymbol(in, bp, &tree_d, inbitlength);
1148  if(code_d > 29)
1149  {
1150  if(code_ll == (unsigned)(-1)) /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
1151  {
1152  /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
1153  (10=no endcode, 11=wrong jump outside of tree)*/
1154  error = (*bp) > inlength * 8 ? 10 : 11;
1155  }
1156  else error = 18; /*error: invalid distance code (30-31 are never used)*/
1157  break;
1158  }
1159  distance = DISTANCEBASE[code_d];
1160 
1161  /*part 4: get extra bits from distance*/
1162  numextrabits_d = DISTANCEEXTRA[code_d];
1163  if((*bp + numextrabits_d) > inbitlength) ERROR_BREAK(51); /*error, bit pointer will jump past memory*/
1164  distance += readBitsFromStream(bp, in, numextrabits_d);
1165 
1166  /*part 5: fill in all the out[n] values based on the length and dist*/
1167  start = (*pos);
1168  if(distance > start) ERROR_BREAK(52); /*too long backward distance*/
1169  backward = start - distance;
1170 
1171  if(!ucvector_resize(out, (*pos) + length)) ERROR_BREAK(83 /*alloc fail*/);
1172  if (distance < length) {
1173  for(forward = 0; forward < length; ++forward)
1174  {
1175  out->data[(*pos)++] = out->data[backward++];
1176  }
1177  } else {
1178  memcpy(out->data + *pos, out->data + backward, length);
1179  *pos += length;
1180  }
1181  }
1182  else if(code_ll == 256)
1183  {
1184  break; /*end code, break the loop*/
1185  }
1186  else /*if(code == (unsigned)(-1))*/ /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
1187  {
1188  /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
1189  (10=no endcode, 11=wrong jump outside of tree)*/
1190  error = ((*bp) > inlength * 8) ? 10 : 11;
1191  break;
1192  }
1193  }
1194 
1195  HuffmanTree_cleanup(&tree_ll);
1196  HuffmanTree_cleanup(&tree_d);
1197 
1198  return error;
1199 }
1200 
1201 static unsigned inflateNoCompression(ucvector* out, const unsigned char* in, size_t* bp, size_t* pos, size_t inlength)
1202 {
1203  size_t p;
1204  unsigned LEN, NLEN, n, error = 0;
1205 
1206  /*go to first boundary of byte*/
1207  while(((*bp) & 0x7) != 0) ++(*bp);
1208  p = (*bp) / 8; /*byte position*/
1209 
1210  /*read LEN (2 bytes) and NLEN (2 bytes)*/
1211  if(p + 4 >= inlength) return 52; /*error, bit pointer will jump past memory*/
1212  LEN = in[p] + 256u * in[p + 1]; p += 2;
1213  NLEN = in[p] + 256u * in[p + 1]; p += 2;
1214 
1215  /*check if 16-bit NLEN is really the one's complement of LEN*/
1216  if(LEN + NLEN != 65535) return 21; /*error: NLEN is not one's complement of LEN*/
1217 
1218  if(!ucvector_resize(out, (*pos) + LEN)) return 83; /*alloc fail*/
1219 
1220  /*read the literal data: LEN bytes are now stored in the out buffer*/
1221  if(p + LEN > inlength) return 23; /*error: reading outside of in buffer*/
1222  for(n = 0; n < LEN; ++n) out->data[(*pos)++] = in[p++];
1223 
1224  (*bp) = p * 8;
1225 
1226  return error;
1227 }
1228 
1229 static unsigned lodepng_inflatev(ucvector* out,
1230  const unsigned char* in, size_t insize,
1231  const LodePNGDecompressSettings* settings)
1232 {
1233  /*bit pointer in the "in" data, current byte is bp >> 3, current bit is bp & 0x7 (from lsb to msb of the byte)*/
1234  size_t bp = 0;
1235  unsigned BFINAL = 0;
1236  size_t pos = 0; /*byte position in the out buffer*/
1237  unsigned error = 0;
1238 
1239  (void)settings;
1240 
1241  while(!BFINAL)
1242  {
1243  unsigned BTYPE;
1244  if(bp + 2 >= insize * 8) return 52; /*error, bit pointer will jump past memory*/
1245  BFINAL = readBitFromStream(&bp, in);
1246  BTYPE = 1u * readBitFromStream(&bp, in);
1247  BTYPE += 2u * readBitFromStream(&bp, in);
1248 
1249  if(BTYPE == 3) return 20; /*error: invalid BTYPE*/
1250  else if(BTYPE == 0) error = inflateNoCompression(out, in, &bp, &pos, insize); /*no compression*/
1251  else error = inflateHuffmanBlock(out, in, &bp, &pos, insize, BTYPE); /*compression, BTYPE 01 or 10*/
1252 
1253  if(error) return error;
1254  }
1255 
1256  return error;
1257 }
1258 
1259 unsigned lodepng_inflate(unsigned char** out, size_t* outsize,
1260  const unsigned char* in, size_t insize,
1261  const LodePNGDecompressSettings* settings)
1262 {
1263  unsigned error;
1264  ucvector v;
1265  ucvector_init_buffer(&v, *out, *outsize);
1266  error = lodepng_inflatev(&v, in, insize, settings);
1267  *out = v.data;
1268  *outsize = v.size;
1269  return error;
1270 }
1271 
1272 static unsigned inflate(unsigned char** out, size_t* outsize,
1273  const unsigned char* in, size_t insize,
1274  const LodePNGDecompressSettings* settings)
1275 {
1276  if(settings->custom_inflate)
1277  {
1278  return settings->custom_inflate(out, outsize, in, insize, settings);
1279  }
1280  else
1281  {
1282  return lodepng_inflate(out, outsize, in, insize, settings);
1283  }
1284 }
1285 
1286 #endif /*LODEPNG_COMPILE_DECODER*/
1287 
1288 #ifdef LODEPNG_COMPILE_ENCODER
1289 
1290 /* ////////////////////////////////////////////////////////////////////////// */
1291 /* / Deflator (Compressor) / */
1292 /* ////////////////////////////////////////////////////////////////////////// */
1293 
1294 static const size_t MAX_SUPPORTED_DEFLATE_LENGTH = 258;
1295 
1296 /*bitlen is the size in bits of the code*/
1297 static void addHuffmanSymbol(size_t* bp, ucvector* compressed, unsigned code, unsigned bitlen)
1298 {
1299  addBitsToStreamReversed(bp, compressed, code, bitlen);
1300 }
1301 
1302 /*search the index in the array, that has the largest value smaller than or equal to the given value,
1303 given array must be sorted (if no value is smaller, it returns the size of the given array)*/
1304 static size_t searchCodeIndex(const unsigned* array, size_t array_size, size_t value)
1305 {
1306  /*linear search implementation*/
1307  /*for(size_t i = 1; i < array_size; ++i) if(array[i] > value) return i - 1;
1308  return array_size - 1;*/
1309 
1310  /*binary search implementation (not that much faster) (precondition: array_size > 0)*/
1311  size_t left = 1;
1312  size_t right = array_size - 1;
1313  while(left <= right)
1314  {
1315  size_t mid = (left + right) / 2;
1316  if(array[mid] <= value) left = mid + 1; /*the value to find is more to the right*/
1317  else if(array[mid - 1] > value) right = mid - 1; /*the value to find is more to the left*/
1318  else return mid - 1;
1319  }
1320  return array_size - 1;
1321 }
1322 
1323 static void addLengthDistance(uivector* values, size_t length, size_t distance)
1324 {
1325  /*values in encoded vector are those used by deflate:
1326  0-255: literal bytes
1327  256: end
1328  257-285: length/distance pair (length code, followed by extra length bits, distance code, extra distance bits)
1329  286-287: invalid*/
1330 
1331  unsigned length_code = (unsigned)searchCodeIndex(LENGTHBASE, 29, length);
1332  unsigned extra_length = (unsigned)(length - LENGTHBASE[length_code]);
1333  unsigned dist_code = (unsigned)searchCodeIndex(DISTANCEBASE, 30, distance);
1334  unsigned extra_distance = (unsigned)(distance - DISTANCEBASE[dist_code]);
1335 
1336  uivector_push_back(values, length_code + FIRST_LENGTH_CODE_INDEX);
1337  uivector_push_back(values, extra_length);
1338  uivector_push_back(values, dist_code);
1339  uivector_push_back(values, extra_distance);
1340 }
1341 
1342 /*3 bytes of data get encoded into two bytes. The hash cannot use more than 3
1343 bytes as input because 3 is the minimum match length for deflate*/
1344 static const unsigned HASH_NUM_VALUES = 65536;
1345 static const unsigned HASH_BIT_MASK = 65535; /*HASH_NUM_VALUES - 1, but C90 does not like that as initializer*/
1346 
1347 typedef struct Hash
1348 {
1349  int* head; /*hash value to head circular pos - can be outdated if went around window*/
1350  /*circular pos to prev circular pos*/
1351  unsigned short* chain;
1352  int* val; /*circular pos to hash value*/
1353 
1354  /*TODO: do this not only for zeros but for any repeated byte. However for PNG
1355  it's always going to be the zeros that dominate, so not important for PNG*/
1356  int* headz; /*similar to head, but for chainz*/
1357  unsigned short* chainz; /*those with same amount of zeros*/
1358  unsigned short* zeros; /*length of zeros streak, used as a second hash chain*/
1359 } Hash;
1360 
1361 static unsigned hash_init(Hash* hash, unsigned windowsize)
1362 {
1363  unsigned i;
1364  hash->head = (int*)lodepng_malloc(sizeof(int) * HASH_NUM_VALUES);
1365  hash->val = (int*)lodepng_malloc(sizeof(int) * windowsize);
1366  hash->chain = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
1367 
1368  hash->zeros = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
1369  hash->headz = (int*)lodepng_malloc(sizeof(int) * (MAX_SUPPORTED_DEFLATE_LENGTH + 1));
1370  hash->chainz = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
1371 
1372  if(!hash->head || !hash->chain || !hash->val || !hash->headz|| !hash->chainz || !hash->zeros)
1373  {
1374  return 83; /*alloc fail*/
1375  }
1376 
1377  /*initialize hash table*/
1378  for(i = 0; i != HASH_NUM_VALUES; ++i) hash->head[i] = -1;
1379  for(i = 0; i != windowsize; ++i) hash->val[i] = -1;
1380  for(i = 0; i != windowsize; ++i) hash->chain[i] = i; /*same value as index indicates uninitialized*/
1381 
1382  for(i = 0; i <= MAX_SUPPORTED_DEFLATE_LENGTH; ++i) hash->headz[i] = -1;
1383  for(i = 0; i != windowsize; ++i) hash->chainz[i] = i; /*same value as index indicates uninitialized*/
1384 
1385  return 0;
1386 }
1387 
1388 static void hash_cleanup(Hash* hash)
1389 {
1390  lodepng_free(hash->head);
1391  lodepng_free(hash->val);
1392  lodepng_free(hash->chain);
1393 
1394  lodepng_free(hash->zeros);
1395  lodepng_free(hash->headz);
1396  lodepng_free(hash->chainz);
1397 }
1398 
1399 
1400 
1401 static unsigned getHash(const unsigned char* data, size_t size, size_t pos)
1402 {
1403  unsigned result = 0;
1404  if(pos + 2 < size)
1405  {
1406  /*A simple shift and xor hash is used. Since the data of PNGs is dominated
1407  by zeroes due to the filters, a better hash does not have a significant
1408  effect on speed in traversing the chain, and causes more time spend on
1409  calculating the hash.*/
1410  result ^= (unsigned)(data[pos + 0] << 0u);
1411  result ^= (unsigned)(data[pos + 1] << 4u);
1412  result ^= (unsigned)(data[pos + 2] << 8u);
1413  } else {
1414  size_t amount, i;
1415  if(pos >= size) return 0;
1416  amount = size - pos;
1417  for(i = 0; i != amount; ++i) result ^= (unsigned)(data[pos + i] << (i * 8u));
1418  }
1419  return result & HASH_BIT_MASK;
1420 }
1421 
1422 static unsigned countZeros(const unsigned char* data, size_t size, size_t pos)
1423 {
1424  const unsigned char* start = data + pos;
1425  const unsigned char* end = start + MAX_SUPPORTED_DEFLATE_LENGTH;
1426  if(end > data + size) end = data + size;
1427  data = start;
1428  while(data != end && *data == 0) ++data;
1429  /*subtracting two addresses returned as 32-bit number (max value is MAX_SUPPORTED_DEFLATE_LENGTH)*/
1430  return (unsigned)(data - start);
1431 }
1432 
1433 /*wpos = pos & (windowsize - 1)*/
1434 static void updateHashChain(Hash* hash, size_t wpos, unsigned hashval, unsigned short numzeros)
1435 {
1436  hash->val[wpos] = (int)hashval;
1437  if(hash->head[hashval] != -1) hash->chain[wpos] = hash->head[hashval];
1438  hash->head[hashval] = wpos;
1439 
1440  hash->zeros[wpos] = numzeros;
1441  if(hash->headz[numzeros] != -1) hash->chainz[wpos] = hash->headz[numzeros];
1442  hash->headz[numzeros] = wpos;
1443 }
1444 
1445 /*
1446 LZ77-encode the data. Return value is error code. The input are raw bytes, the output
1447 is in the form of unsigned integers with codes representing for example literal bytes, or
1448 length/distance pairs.
1449 It uses a hash table technique to let it encode faster. When doing LZ77 encoding, a
1450 sliding window (of windowsize) is used, and all past bytes in that window can be used as
1451 the "dictionary". A brute force search through all possible distances would be slow, and
1452 this hash technique is one out of several ways to speed this up.
1453 */
1454 static unsigned encodeLZ77(uivector* out, Hash* hash,
1455  const unsigned char* in, size_t inpos, size_t insize, unsigned windowsize,
1456  unsigned minmatch, unsigned nicematch, unsigned lazymatching)
1457 {
1458  size_t pos;
1459  unsigned i, error = 0;
1460  /*for large window lengths, assume the user wants no compression loss. Otherwise, max hash chain length speedup.*/
1461  unsigned maxchainlength = windowsize >= 8192 ? windowsize : windowsize / 8;
1462  unsigned maxlazymatch = windowsize >= 8192 ? MAX_SUPPORTED_DEFLATE_LENGTH : 64;
1463 
1464  unsigned usezeros = 1; /*not sure if setting it to false for windowsize < 8192 is better or worse*/
1465  unsigned numzeros = 0;
1466 
1467  unsigned offset; /*the offset represents the distance in LZ77 terminology*/
1468  unsigned length;
1469  unsigned lazy = 0;
1470  unsigned lazylength = 0, lazyoffset = 0;
1471  unsigned hashval;
1472  unsigned current_offset, current_length;
1473  unsigned prev_offset;
1474  const unsigned char *lastptr, *foreptr, *backptr;
1475  unsigned hashpos;
1476 
1477  if(windowsize == 0 || windowsize > 32768) return 60; /*error: windowsize smaller/larger than allowed*/
1478  if((windowsize & (windowsize - 1)) != 0) return 90; /*error: must be power of two*/
1479 
1480  if(nicematch > MAX_SUPPORTED_DEFLATE_LENGTH) nicematch = MAX_SUPPORTED_DEFLATE_LENGTH;
1481 
1482  for(pos = inpos; pos < insize; ++pos)
1483  {
1484  size_t wpos = pos & (windowsize - 1); /*position for in 'circular' hash buffers*/
1485  unsigned chainlength = 0;
1486 
1487  hashval = getHash(in, insize, pos);
1488 
1489  if(usezeros && hashval == 0)
1490  {
1491  if(numzeros == 0) numzeros = countZeros(in, insize, pos);
1492  else if(pos + numzeros > insize || in[pos + numzeros - 1] != 0) --numzeros;
1493  }
1494  else
1495  {
1496  numzeros = 0;
1497  }
1498 
1499  updateHashChain(hash, wpos, hashval, numzeros);
1500 
1501  /*the length and offset found for the current position*/
1502  length = 0;
1503  offset = 0;
1504 
1505  hashpos = hash->chain[wpos];
1506 
1507  lastptr = &in[insize < pos + MAX_SUPPORTED_DEFLATE_LENGTH ? insize : pos + MAX_SUPPORTED_DEFLATE_LENGTH];
1508 
1509  /*search for the longest string*/
1510  prev_offset = 0;
1511  for(;;)
1512  {
1513  if(chainlength++ >= maxchainlength) break;
1514  current_offset = hashpos <= wpos ? wpos - hashpos : wpos - hashpos + windowsize;
1515 
1516  if(current_offset < prev_offset) break; /*stop when went completely around the circular buffer*/
1517  prev_offset = current_offset;
1518  if(current_offset > 0)
1519  {
1520  /*test the next characters*/
1521  foreptr = &in[pos];
1522  backptr = &in[pos - current_offset];
1523 
1524  /*common case in PNGs is lots of zeros. Quickly skip over them as a speedup*/
1525  if(numzeros >= 3)
1526  {
1527  unsigned skip = hash->zeros[hashpos];
1528  if(skip > numzeros) skip = numzeros;
1529  backptr += skip;
1530  foreptr += skip;
1531  }
1532 
1533  while(foreptr != lastptr && *backptr == *foreptr) /*maximum supported length by deflate is max length*/
1534  {
1535  ++backptr;
1536  ++foreptr;
1537  }
1538  current_length = (unsigned)(foreptr - &in[pos]);
1539 
1540  if(current_length > length)
1541  {
1542  length = current_length; /*the longest length*/
1543  offset = current_offset; /*the offset that is related to this longest length*/
1544  /*jump out once a length of max length is found (speed gain). This also jumps
1545  out if length is MAX_SUPPORTED_DEFLATE_LENGTH*/
1546  if(current_length >= nicematch) break;
1547  }
1548  }
1549 
1550  if(hashpos == hash->chain[hashpos]) break;
1551 
1552  if(numzeros >= 3 && length > numzeros)
1553  {
1554  hashpos = hash->chainz[hashpos];
1555  if(hash->zeros[hashpos] != numzeros) break;
1556  }
1557  else
1558  {
1559  hashpos = hash->chain[hashpos];
1560  /*outdated hash value, happens if particular value was not encountered in whole last window*/
1561  if(hash->val[hashpos] != (int)hashval) break;
1562  }
1563  }
1564 
1565  if(lazymatching)
1566  {
1567  if(!lazy && length >= 3 && length <= maxlazymatch && length < MAX_SUPPORTED_DEFLATE_LENGTH)
1568  {
1569  lazy = 1;
1570  lazylength = length;
1571  lazyoffset = offset;
1572  continue; /*try the next byte*/
1573  }
1574  if(lazy)
1575  {
1576  lazy = 0;
1577  if(pos == 0) ERROR_BREAK(81);
1578  if(length > lazylength + 1)
1579  {
1580  /*push the previous character as literal*/
1581  if(!uivector_push_back(out, in[pos - 1])) ERROR_BREAK(83 /*alloc fail*/);
1582  }
1583  else
1584  {
1585  length = lazylength;
1586  offset = lazyoffset;
1587  hash->head[hashval] = -1; /*the same hashchain update will be done, this ensures no wrong alteration*/
1588  hash->headz[numzeros] = -1; /*idem*/
1589  --pos;
1590  }
1591  }
1592  }
1593  if(length >= 3 && offset > windowsize) ERROR_BREAK(86 /*too big (or overflown negative) offset*/);
1594 
1595  /*encode it as length/distance pair or literal value*/
1596  if(length < 3) /*only lengths of 3 or higher are supported as length/distance pair*/
1597  {
1598  if(!uivector_push_back(out, in[pos])) ERROR_BREAK(83 /*alloc fail*/);
1599  }
1600  else if(length < minmatch || (length == 3 && offset > 4096))
1601  {
1602  /*compensate for the fact that longer offsets have more extra bits, a
1603  length of only 3 may be not worth it then*/
1604  if(!uivector_push_back(out, in[pos])) ERROR_BREAK(83 /*alloc fail*/);
1605  }
1606  else
1607  {
1608  addLengthDistance(out, length, offset);
1609  for(i = 1; i < length; ++i)
1610  {
1611  ++pos;
1612  wpos = pos & (windowsize - 1);
1613  hashval = getHash(in, insize, pos);
1614  if(usezeros && hashval == 0)
1615  {
1616  if(numzeros == 0) numzeros = countZeros(in, insize, pos);
1617  else if(pos + numzeros > insize || in[pos + numzeros - 1] != 0) --numzeros;
1618  }
1619  else
1620  {
1621  numzeros = 0;
1622  }
1623  updateHashChain(hash, wpos, hashval, numzeros);
1624  }
1625  }
1626  } /*end of the loop through each character of input*/
1627 
1628  return error;
1629 }
1630 
1631 /* /////////////////////////////////////////////////////////////////////////// */
1632 
1633 static unsigned deflateNoCompression(ucvector* out, const unsigned char* data, size_t datasize)
1634 {
1635  /*non compressed deflate block data: 1 bit BFINAL,2 bits BTYPE,(5 bits): it jumps to start of next byte,
1636  2 bytes LEN, 2 bytes NLEN, LEN bytes literal DATA*/
1637 
1638  size_t i, j, numdeflateblocks = (datasize + 65534) / 65535;
1639  unsigned datapos = 0;
1640  for(i = 0; i != numdeflateblocks; ++i)
1641  {
1642  unsigned BFINAL, BTYPE, LEN, NLEN;
1643  unsigned char firstbyte;
1644 
1645  BFINAL = (i == numdeflateblocks - 1);
1646  BTYPE = 0;
1647 
1648  firstbyte = (unsigned char)(BFINAL + ((BTYPE & 1) << 1) + ((BTYPE & 2) << 1));
1649  ucvector_push_back(out, firstbyte);
1650 
1651  LEN = 65535;
1652  if(datasize - datapos < 65535) LEN = (unsigned)datasize - datapos;
1653  NLEN = 65535 - LEN;
1654 
1655  ucvector_push_back(out, (unsigned char)(LEN % 256));
1656  ucvector_push_back(out, (unsigned char)(LEN / 256));
1657  ucvector_push_back(out, (unsigned char)(NLEN % 256));
1658  ucvector_push_back(out, (unsigned char)(NLEN / 256));
1659 
1660  /*Decompressed data*/
1661  for(j = 0; j < 65535 && datapos < datasize; ++j)
1662  {
1663  ucvector_push_back(out, data[datapos++]);
1664  }
1665  }
1666 
1667  return 0;
1668 }
1669 
1670 /*
1671 write the lz77-encoded data, which has lit, len and dist codes, to compressed stream using huffman trees.
1672 tree_ll: the tree for lit and len codes.
1673 tree_d: the tree for distance codes.
1674 */
1675 static void writeLZ77data(size_t* bp, ucvector* out, const uivector* lz77_encoded,
1676  const HuffmanTree* tree_ll, const HuffmanTree* tree_d)
1677 {
1678  size_t i = 0;
1679  for(i = 0; i != lz77_encoded->size; ++i)
1680  {
1681  unsigned val = lz77_encoded->data[i];
1682  addHuffmanSymbol(bp, out, HuffmanTree_getCode(tree_ll, val), HuffmanTree_getLength(tree_ll, val));
1683  if(val > 256) /*for a length code, 3 more things have to be added*/
1684  {
1685  unsigned length_index = val - FIRST_LENGTH_CODE_INDEX;
1686  unsigned n_length_extra_bits = LENGTHEXTRA[length_index];
1687  unsigned length_extra_bits = lz77_encoded->data[++i];
1688 
1689  unsigned distance_code = lz77_encoded->data[++i];
1690 
1691  unsigned distance_index = distance_code;
1692  unsigned n_distance_extra_bits = DISTANCEEXTRA[distance_index];
1693  unsigned distance_extra_bits = lz77_encoded->data[++i];
1694 
1695  addBitsToStream(bp, out, length_extra_bits, n_length_extra_bits);
1696  addHuffmanSymbol(bp, out, HuffmanTree_getCode(tree_d, distance_code),
1697  HuffmanTree_getLength(tree_d, distance_code));
1698  addBitsToStream(bp, out, distance_extra_bits, n_distance_extra_bits);
1699  }
1700  }
1701 }
1702 
1703 /*Deflate for a block of type "dynamic", that is, with freely, optimally, created huffman trees*/
1704 static unsigned deflateDynamic(ucvector* out, size_t* bp, Hash* hash,
1705  const unsigned char* data, size_t datapos, size_t dataend,
1706  const LodePNGCompressSettings* settings, unsigned final)
1707 {
1708  unsigned error = 0;
1709 
1710  /*
1711  A block is compressed as follows: The PNG data is lz77 encoded, resulting in
1712  literal bytes and length/distance pairs. This is then huffman compressed with
1713  two huffman trees. One huffman tree is used for the lit and len values ("ll"),
1714  another huffman tree is used for the dist values ("d"). These two trees are
1715  stored using their code lengths, and to compress even more these code lengths
1716  are also run-length encoded and huffman compressed. This gives a huffman tree
1717  of code lengths "cl". The code lenghts used to describe this third tree are
1718  the code length code lengths ("clcl").
1719  */
1720 
1721  /*The lz77 encoded data, represented with integers since there will also be length and distance codes in it*/
1722  uivector lz77_encoded;
1723  HuffmanTree tree_ll; /*tree for lit,len values*/
1724  HuffmanTree tree_d; /*tree for distance codes*/
1725  HuffmanTree tree_cl; /*tree for encoding the code lengths representing tree_ll and tree_d*/
1726  uivector frequencies_ll; /*frequency of lit,len codes*/
1727  uivector frequencies_d; /*frequency of dist codes*/
1728  uivector frequencies_cl; /*frequency of code length codes*/
1729  uivector bitlen_lld; /*lit,len,dist code lenghts (int bits), literally (without repeat codes).*/
1730  uivector bitlen_lld_e; /*bitlen_lld encoded with repeat codes (this is a rudemtary run length compression)*/
1731  /*bitlen_cl is the code length code lengths ("clcl"). The bit lengths of codes to represent tree_cl
1732  (these are written as is in the file, it would be crazy to compress these using yet another huffman
1733  tree that needs to be represented by yet another set of code lengths)*/
1734  uivector bitlen_cl;
1735  size_t datasize = dataend - datapos;
1736 
1737  /*
1738  Due to the huffman compression of huffman tree representations ("two levels"), there are some anologies:
1739  bitlen_lld is to tree_cl what data is to tree_ll and tree_d.
1740  bitlen_lld_e is to bitlen_lld what lz77_encoded is to data.
1741  bitlen_cl is to bitlen_lld_e what bitlen_lld is to lz77_encoded.
1742  */
1743 
1744  unsigned BFINAL = final;
1745  size_t numcodes_ll, numcodes_d, i;
1746  unsigned HLIT, HDIST, HCLEN;
1747 
1748  uivector_init(&lz77_encoded);
1749  HuffmanTree_init(&tree_ll);
1750  HuffmanTree_init(&tree_d);
1751  HuffmanTree_init(&tree_cl);
1752  uivector_init(&frequencies_ll);
1753  uivector_init(&frequencies_d);
1754  uivector_init(&frequencies_cl);
1755  uivector_init(&bitlen_lld);
1756  uivector_init(&bitlen_lld_e);
1757  uivector_init(&bitlen_cl);
1758 
1759  /*This while loop never loops due to a break at the end, it is here to
1760  allow breaking out of it to the cleanup phase on error conditions.*/
1761  while(!error)
1762  {
1763  if(settings->use_lz77)
1764  {
1765  error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize,
1766  settings->minmatch, settings->nicematch, settings->lazymatching);
1767  if(error) break;
1768  }
1769  else
1770  {
1771  if(!uivector_resize(&lz77_encoded, datasize)) ERROR_BREAK(83 /*alloc fail*/);
1772  for(i = datapos; i < dataend; ++i) lz77_encoded.data[i] = data[i]; /*no LZ77, but still will be Huffman compressed*/
1773  }
1774 
1775  if(!uivector_resizev(&frequencies_ll, 286, 0)) ERROR_BREAK(83 /*alloc fail*/);
1776  if(!uivector_resizev(&frequencies_d, 30, 0)) ERROR_BREAK(83 /*alloc fail*/);
1777 
1778  /*Count the frequencies of lit, len and dist codes*/
1779  for(i = 0; i != lz77_encoded.size; ++i)
1780  {
1781  unsigned symbol = lz77_encoded.data[i];
1782  ++frequencies_ll.data[symbol];
1783  if(symbol > 256)
1784  {
1785  unsigned dist = lz77_encoded.data[i + 2];
1786  ++frequencies_d.data[dist];
1787  i += 3;
1788  }
1789  }
1790  frequencies_ll.data[256] = 1; /*there will be exactly 1 end code, at the end of the block*/
1791 
1792  /*Make both huffman trees, one for the lit and len codes, one for the dist codes*/
1793  error = HuffmanTree_makeFromFrequencies(&tree_ll, frequencies_ll.data, 257, frequencies_ll.size, 15);
1794  if(error) break;
1795  /*2, not 1, is chosen for mincodes: some buggy PNG decoders require at least 2 symbols in the dist tree*/
1796  error = HuffmanTree_makeFromFrequencies(&tree_d, frequencies_d.data, 2, frequencies_d.size, 15);
1797  if(error) break;
1798 
1799  numcodes_ll = tree_ll.numcodes; if(numcodes_ll > 286) numcodes_ll = 286;
1800  numcodes_d = tree_d.numcodes; if(numcodes_d > 30) numcodes_d = 30;
1801  /*store the code lengths of both generated trees in bitlen_lld*/
1802  for(i = 0; i != numcodes_ll; ++i) uivector_push_back(&bitlen_lld, HuffmanTree_getLength(&tree_ll, (unsigned)i));
1803  for(i = 0; i != numcodes_d; ++i) uivector_push_back(&bitlen_lld, HuffmanTree_getLength(&tree_d, (unsigned)i));
1804 
1805  /*run-length compress bitlen_ldd into bitlen_lld_e by using repeat codes 16 (copy length 3-6 times),
1806  17 (3-10 zeroes), 18 (11-138 zeroes)*/
1807  for(i = 0; i != (unsigned)bitlen_lld.size; ++i)
1808  {
1809  unsigned j = 0; /*amount of repititions*/
1810  while(i + j + 1 < (unsigned)bitlen_lld.size && bitlen_lld.data[i + j + 1] == bitlen_lld.data[i]) ++j;
1811 
1812  if(bitlen_lld.data[i] == 0 && j >= 2) /*repeat code for zeroes*/
1813  {
1814  ++j; /*include the first zero*/
1815  if(j <= 10) /*repeat code 17 supports max 10 zeroes*/
1816  {
1817  uivector_push_back(&bitlen_lld_e, 17);
1818  uivector_push_back(&bitlen_lld_e, j - 3);
1819  }
1820  else /*repeat code 18 supports max 138 zeroes*/
1821  {
1822  if(j > 138) j = 138;
1823  uivector_push_back(&bitlen_lld_e, 18);
1824  uivector_push_back(&bitlen_lld_e, j - 11);
1825  }
1826  i += (j - 1);
1827  }
1828  else if(j >= 3) /*repeat code for value other than zero*/
1829  {
1830  size_t k;
1831  unsigned num = j / 6, rest = j % 6;
1832  uivector_push_back(&bitlen_lld_e, bitlen_lld.data[i]);
1833  for(k = 0; k < num; ++k)
1834  {
1835  uivector_push_back(&bitlen_lld_e, 16);
1836  uivector_push_back(&bitlen_lld_e, 6 - 3);
1837  }
1838  if(rest >= 3)
1839  {
1840  uivector_push_back(&bitlen_lld_e, 16);
1841  uivector_push_back(&bitlen_lld_e, rest - 3);
1842  }
1843  else j -= rest;
1844  i += j;
1845  }
1846  else /*too short to benefit from repeat code*/
1847  {
1848  uivector_push_back(&bitlen_lld_e, bitlen_lld.data[i]);
1849  }
1850  }
1851 
1852  /*generate tree_cl, the huffmantree of huffmantrees*/
1853 
1854  if(!uivector_resizev(&frequencies_cl, NUM_CODE_LENGTH_CODES, 0)) ERROR_BREAK(83 /*alloc fail*/);
1855  for(i = 0; i != bitlen_lld_e.size; ++i)
1856  {
1857  ++frequencies_cl.data[bitlen_lld_e.data[i]];
1858  /*after a repeat code come the bits that specify the number of repetitions,
1859  those don't need to be in the frequencies_cl calculation*/
1860  if(bitlen_lld_e.data[i] >= 16) ++i;
1861  }
1862 
1863  error = HuffmanTree_makeFromFrequencies(&tree_cl, frequencies_cl.data,
1864  frequencies_cl.size, frequencies_cl.size, 7);
1865  if(error) break;
1866 
1867  if(!uivector_resize(&bitlen_cl, tree_cl.numcodes)) ERROR_BREAK(83 /*alloc fail*/);
1868  for(i = 0; i != tree_cl.numcodes; ++i)
1869  {
1870  /*lenghts of code length tree is in the order as specified by deflate*/
1871  bitlen_cl.data[i] = HuffmanTree_getLength(&tree_cl, CLCL_ORDER[i]);
1872  }
1873  while(bitlen_cl.data[bitlen_cl.size - 1] == 0 && bitlen_cl.size > 4)
1874  {
1875  /*remove zeros at the end, but minimum size must be 4*/
1876  if(!uivector_resize(&bitlen_cl, bitlen_cl.size - 1)) ERROR_BREAK(83 /*alloc fail*/);
1877  }
1878  if(error) break;
1879 
1880  /*
1881  Write everything into the output
1882 
1883  After the BFINAL and BTYPE, the dynamic block consists out of the following:
1884  - 5 bits HLIT, 5 bits HDIST, 4 bits HCLEN
1885  - (HCLEN+4)*3 bits code lengths of code length alphabet
1886  - HLIT + 257 code lenghts of lit/length alphabet (encoded using the code length
1887  alphabet, + possible repetition codes 16, 17, 18)
1888  - HDIST + 1 code lengths of distance alphabet (encoded using the code length
1889  alphabet, + possible repetition codes 16, 17, 18)
1890  - compressed data
1891  - 256 (end code)
1892  */
1893 
1894  /*Write block type*/
1895  addBitToStream(bp, out, BFINAL);
1896  addBitToStream(bp, out, 0); /*first bit of BTYPE "dynamic"*/
1897  addBitToStream(bp, out, 1); /*second bit of BTYPE "dynamic"*/
1898 
1899  /*write the HLIT, HDIST and HCLEN values*/
1900  HLIT = (unsigned)(numcodes_ll - 257);
1901  HDIST = (unsigned)(numcodes_d - 1);
1902  HCLEN = (unsigned)bitlen_cl.size - 4;
1903  /*trim zeroes for HCLEN. HLIT and HDIST were already trimmed at tree creation*/
1904  while(!bitlen_cl.data[HCLEN + 4 - 1] && HCLEN > 0) --HCLEN;
1905  addBitsToStream(bp, out, HLIT, 5);
1906  addBitsToStream(bp, out, HDIST, 5);
1907  addBitsToStream(bp, out, HCLEN, 4);
1908 
1909  /*write the code lenghts of the code length alphabet*/
1910  for(i = 0; i != HCLEN + 4; ++i) addBitsToStream(bp, out, bitlen_cl.data[i], 3);
1911 
1912  /*write the lenghts of the lit/len AND the dist alphabet*/
1913  for(i = 0; i != bitlen_lld_e.size; ++i)
1914  {
1915  addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_cl, bitlen_lld_e.data[i]),
1916  HuffmanTree_getLength(&tree_cl, bitlen_lld_e.data[i]));
1917  /*extra bits of repeat codes*/
1918  if(bitlen_lld_e.data[i] == 16) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 2);
1919  else if(bitlen_lld_e.data[i] == 17) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 3);
1920  else if(bitlen_lld_e.data[i] == 18) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 7);
1921  }
1922 
1923  /*write the compressed data symbols*/
1924  writeLZ77data(bp, out, &lz77_encoded, &tree_ll, &tree_d);
1925  /*error: the length of the end code 256 must be larger than 0*/
1926  if(HuffmanTree_getLength(&tree_ll, 256) == 0) ERROR_BREAK(64);
1927 
1928  /*write the end code*/
1929  addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, 256), HuffmanTree_getLength(&tree_ll, 256));
1930 
1931  break; /*end of error-while*/
1932  }
1933 
1934  /*cleanup*/
1935  uivector_cleanup(&lz77_encoded);
1936  HuffmanTree_cleanup(&tree_ll);
1937  HuffmanTree_cleanup(&tree_d);
1938  HuffmanTree_cleanup(&tree_cl);
1939  uivector_cleanup(&frequencies_ll);
1940  uivector_cleanup(&frequencies_d);
1941  uivector_cleanup(&frequencies_cl);
1942  uivector_cleanup(&bitlen_lld_e);
1943  uivector_cleanup(&bitlen_lld);
1944  uivector_cleanup(&bitlen_cl);
1945 
1946  return error;
1947 }
1948 
1949 static unsigned deflateFixed(ucvector* out, size_t* bp, Hash* hash,
1950  const unsigned char* data,
1951  size_t datapos, size_t dataend,
1952  const LodePNGCompressSettings* settings, unsigned final)
1953 {
1954  HuffmanTree tree_ll; /*tree for literal values and length codes*/
1955  HuffmanTree tree_d; /*tree for distance codes*/
1956 
1957  unsigned BFINAL = final;
1958  unsigned error = 0;
1959  size_t i;
1960 
1961  HuffmanTree_init(&tree_ll);
1962  HuffmanTree_init(&tree_d);
1963 
1964  generateFixedLitLenTree(&tree_ll);
1965  generateFixedDistanceTree(&tree_d);
1966 
1967  addBitToStream(bp, out, BFINAL);
1968  addBitToStream(bp, out, 1); /*first bit of BTYPE*/
1969  addBitToStream(bp, out, 0); /*second bit of BTYPE*/
1970 
1971  if(settings->use_lz77) /*LZ77 encoded*/
1972  {
1973  uivector lz77_encoded;
1974  uivector_init(&lz77_encoded);
1975  error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize,
1976  settings->minmatch, settings->nicematch, settings->lazymatching);
1977  if(!error) writeLZ77data(bp, out, &lz77_encoded, &tree_ll, &tree_d);
1978  uivector_cleanup(&lz77_encoded);
1979  }
1980  else /*no LZ77, but still will be Huffman compressed*/
1981  {
1982  for(i = datapos; i < dataend; ++i)
1983  {
1984  addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, data[i]), HuffmanTree_getLength(&tree_ll, data[i]));
1985  }
1986  }
1987  /*add END code*/
1988  if(!error) addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, 256), HuffmanTree_getLength(&tree_ll, 256));
1989 
1990  /*cleanup*/
1991  HuffmanTree_cleanup(&tree_ll);
1992  HuffmanTree_cleanup(&tree_d);
1993 
1994  return error;
1995 }
1996 
1997 static unsigned lodepng_deflatev(ucvector* out, const unsigned char* in, size_t insize,
1998  const LodePNGCompressSettings* settings)
1999 {
2000  unsigned error = 0;
2001  size_t i, blocksize, numdeflateblocks;
2002  size_t bp = 0; /*the bit pointer*/
2003  Hash hash;
2004 
2005  if(settings->btype > 2) return 61;
2006  else if(settings->btype == 0) return deflateNoCompression(out, in, insize);
2007  else if(settings->btype == 1) blocksize = insize;
2008  else /*if(settings->btype == 2)*/
2009  {
2010  /*on PNGs, deflate blocks of 65-262k seem to give most dense encoding*/
2011  blocksize = insize / 8 + 8;
2012  if(blocksize < 65536) blocksize = 65536;
2013  if(blocksize > 262144) blocksize = 262144;
2014  }
2015 
2016  numdeflateblocks = (insize + blocksize - 1) / blocksize;
2017  if(numdeflateblocks == 0) numdeflateblocks = 1;
2018 
2019  error = hash_init(&hash, settings->windowsize);
2020  if(error) return error;
2021 
2022  for(i = 0; i != numdeflateblocks && !error; ++i)
2023  {
2024  unsigned final = (i == numdeflateblocks - 1);
2025  size_t start = i * blocksize;
2026  size_t end = start + blocksize;
2027  if(end > insize) end = insize;
2028 
2029  if(settings->btype == 1) error = deflateFixed(out, &bp, &hash, in, start, end, settings, final);
2030  else if(settings->btype == 2) error = deflateDynamic(out, &bp, &hash, in, start, end, settings, final);
2031  }
2032 
2033  hash_cleanup(&hash);
2034 
2035  return error;
2036 }
2037 
2038 unsigned lodepng_deflate(unsigned char** out, size_t* outsize,
2039  const unsigned char* in, size_t insize,
2040  const LodePNGCompressSettings* settings)
2041 {
2042  unsigned error;
2043  ucvector v;
2044  ucvector_init_buffer(&v, *out, *outsize);
2045  error = lodepng_deflatev(&v, in, insize, settings);
2046  *out = v.data;
2047  *outsize = v.size;
2048  return error;
2049 }
2050 
2051 static unsigned deflate(unsigned char** out, size_t* outsize,
2052  const unsigned char* in, size_t insize,
2053  const LodePNGCompressSettings* settings)
2054 {
2055  if(settings->custom_deflate)
2056  {
2057  return settings->custom_deflate(out, outsize, in, insize, settings);
2058  }
2059  else
2060  {
2061  return lodepng_deflate(out, outsize, in, insize, settings);
2062  }
2063 }
2064 
2065 #endif /*LODEPNG_COMPILE_DECODER*/
2066 
2067 /* ////////////////////////////////////////////////////////////////////////// */
2068 /* / Adler32 */
2069 /* ////////////////////////////////////////////////////////////////////////// */
2070 
2071 static unsigned update_adler32(unsigned adler, const unsigned char* data, unsigned len)
2072 {
2073  unsigned s1 = adler & 0xffff;
2074  unsigned s2 = (adler >> 16) & 0xffff;
2075 
2076  while(len > 0)
2077  {
2078  /*at least 5550 sums can be done before the sums overflow, saving a lot of module divisions*/
2079  unsigned amount = len > 5550 ? 5550 : len;
2080  len -= amount;
2081  while(amount > 0)
2082  {
2083  s1 += (*data++);
2084  s2 += s1;
2085  --amount;
2086  }
2087  s1 %= 65521;
2088  s2 %= 65521;
2089  }
2090 
2091  return (s2 << 16) | s1;
2092 }
2093 
2094 /*Return the adler32 of the bytes data[0..len-1]*/
2095 static unsigned adler32(const unsigned char* data, unsigned len)
2096 {
2097  return update_adler32(1L, data, len);
2098 }
2099 
2100 /* ////////////////////////////////////////////////////////////////////////// */
2101 /* / Zlib / */
2102 /* ////////////////////////////////////////////////////////////////////////// */
2103 
2104 #ifdef LODEPNG_COMPILE_DECODER
2105 
2106 unsigned lodepng_zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
2107  size_t insize, const LodePNGDecompressSettings* settings)
2108 {
2109  unsigned error = 0;
2110  unsigned CM, CINFO, FDICT;
2111 
2112  if(insize < 2) return 53; /*error, size of zlib data too small*/
2113  /*read information from zlib header*/
2114  if((in[0] * 256 + in[1]) % 31 != 0)
2115  {
2116  /*error: 256 * in[0] + in[1] must be a multiple of 31, the FCHECK value is supposed to be made that way*/
2117  return 24;
2118  }
2119 
2120  CM = in[0] & 15;
2121  CINFO = (in[0] >> 4) & 15;
2122  /*FCHECK = in[1] & 31;*/ /*FCHECK is already tested above*/
2123  FDICT = (in[1] >> 5) & 1;
2124  /*FLEVEL = (in[1] >> 6) & 3;*/ /*FLEVEL is not used here*/
2125 
2126  if(CM != 8 || CINFO > 7)
2127  {
2128  /*error: only compression method 8: inflate with sliding window of 32k is supported by the PNG spec*/
2129  return 25;
2130  }
2131  if(FDICT != 0)
2132  {
2133  /*error: the specification of PNG says about the zlib stream:
2134  "The additional flags shall not specify a preset dictionary."*/
2135  return 26;
2136  }
2137 
2138  error = inflate(out, outsize, in + 2, insize - 2, settings);
2139  if(error) return error;
2140 
2141  if(!settings->ignore_adler32)
2142  {
2143  unsigned ADLER32 = lodepng_read32bitInt(&in[insize - 4]);
2144  unsigned checksum = adler32(*out, (unsigned)(*outsize));
2145  if(checksum != ADLER32) return 58; /*error, adler checksum not correct, data must be corrupted*/
2146  }
2147 
2148  return 0; /*no error*/
2149 }
2150 
2151 static unsigned zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
2152  size_t insize, const LodePNGDecompressSettings* settings)
2153 {
2154  if(settings->custom_zlib)
2155  {
2156  return settings->custom_zlib(out, outsize, in, insize, settings);
2157  }
2158  else
2159  {
2160  return lodepng_zlib_decompress(out, outsize, in, insize, settings);
2161  }
2162 }
2163 
2164 #endif /*LODEPNG_COMPILE_DECODER*/
2165 
2166 #ifdef LODEPNG_COMPILE_ENCODER
2167 
2168 unsigned lodepng_zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
2169  size_t insize, const LodePNGCompressSettings* settings)
2170 {
2171  /*initially, *out must be NULL and outsize 0, if you just give some random *out
2172  that's pointing to a non allocated buffer, this'll crash*/
2173  ucvector outv;
2174  size_t i;
2175  unsigned error;
2176  unsigned char* deflatedata = 0;
2177  size_t deflatesize = 0;
2178 
2179  /*zlib data: 1 byte CMF (CM+CINFO), 1 byte FLG, deflate data, 4 byte ADLER32 checksum of the Decompressed data*/
2180  unsigned CMF = 120; /*0b01111000: CM 8, CINFO 7. With CINFO 7, any window size up to 32768 can be used.*/
2181  unsigned FLEVEL = 0;
2182  unsigned FDICT = 0;
2183  unsigned CMFFLG = 256 * CMF + FDICT * 32 + FLEVEL * 64;
2184  unsigned FCHECK = 31 - CMFFLG % 31;
2185  CMFFLG += FCHECK;
2186 
2187  /*ucvector-controlled version of the output buffer, for dynamic array*/
2188  ucvector_init_buffer(&outv, *out, *outsize);
2189 
2190  ucvector_push_back(&outv, (unsigned char)(CMFFLG / 256));
2191  ucvector_push_back(&outv, (unsigned char)(CMFFLG % 256));
2192 
2193  error = deflate(&deflatedata, &deflatesize, in, insize, settings);
2194 
2195  if(!error)
2196  {
2197  unsigned ADLER32 = adler32(in, (unsigned)insize);
2198  for(i = 0; i != deflatesize; ++i) ucvector_push_back(&outv, deflatedata[i]);
2199  lodepng_free(deflatedata);
2200  lodepng_add32bitInt(&outv, ADLER32);
2201  }
2202 
2203  *out = outv.data;
2204  *outsize = outv.size;
2205 
2206  return error;
2207 }
2208 
2209 /* compress using the default or custom zlib function */
2210 static unsigned zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
2211  size_t insize, const LodePNGCompressSettings* settings)
2212 {
2213  if(settings->custom_zlib)
2214  {
2215  return settings->custom_zlib(out, outsize, in, insize, settings);
2216  }
2217  else
2218  {
2219  return lodepng_zlib_compress(out, outsize, in, insize, settings);
2220  }
2221 }
2222 
2223 #endif /*LODEPNG_COMPILE_ENCODER*/
2224 
2225 #else /*no LODEPNG_COMPILE_ZLIB*/
2226 
2227 #ifdef LODEPNG_COMPILE_DECODER
2228 static unsigned zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
2229  size_t insize, const LodePNGDecompressSettings* settings)
2230 {
2231  if(!settings->custom_zlib) return 87; /*no custom zlib function provided */
2232  return settings->custom_zlib(out, outsize, in, insize, settings);
2233 }
2234 #endif /*LODEPNG_COMPILE_DECODER*/
2235 #ifdef LODEPNG_COMPILE_ENCODER
2236 static unsigned zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
2237  size_t insize, const LodePNGCompressSettings* settings)
2238 {
2239  if(!settings->custom_zlib) return 87; /*no custom zlib function provided */
2240  return settings->custom_zlib(out, outsize, in, insize, settings);
2241 }
2242 #endif /*LODEPNG_COMPILE_ENCODER*/
2243 
2244 #endif /*LODEPNG_COMPILE_ZLIB*/
2245 
2246 /* ////////////////////////////////////////////////////////////////////////// */
2247 
2248 #ifdef LODEPNG_COMPILE_ENCODER
2249 
2250 /*this is a good tradeoff between speed and compression ratio*/
2251 #define DEFAULT_WINDOWSIZE 2048
2252 
2253 void lodepng_compress_settings_init(LodePNGCompressSettings* settings)
2254 {
2255  /*compress with dynamic huffman tree (not in the mathematical sense, just not the predefined one)*/
2256  settings->btype = 2;
2257  settings->use_lz77 = 1;
2258  settings->windowsize = DEFAULT_WINDOWSIZE;
2259  settings->minmatch = 3;
2260  settings->nicematch = 128;
2261  settings->lazymatching = 1;
2262 
2263  settings->custom_zlib = 0;
2264  settings->custom_deflate = 0;
2265  settings->custom_context = 0;
2266 }
2267 
2268 const LodePNGCompressSettings lodepng_default_compress_settings = {2, 1, DEFAULT_WINDOWSIZE, 3, 128, 1, 0, 0, 0};
2269 
2270 
2271 #endif /*LODEPNG_COMPILE_ENCODER*/
2272 
2273 #ifdef LODEPNG_COMPILE_DECODER
2274 
2275 void lodepng_decompress_settings_init(LodePNGDecompressSettings* settings)
2276 {
2277  settings->ignore_adler32 = 0;
2278 
2279  settings->custom_zlib = 0;
2280  settings->custom_inflate = 0;
2281  settings->custom_context = 0;
2282 }
2283 
2284 const LodePNGDecompressSettings lodepng_default_decompress_settings = {0, 0, 0, 0};
2285 
2286 #endif /*LODEPNG_COMPILE_DECODER*/
2287 
2288 /* ////////////////////////////////////////////////////////////////////////// */
2289 /* ////////////////////////////////////////////////////////////////////////// */
2290 /* // End of Zlib related code. Begin of PNG related code. // */
2291 /* ////////////////////////////////////////////////////////////////////////// */
2292 /* ////////////////////////////////////////////////////////////////////////// */
2293 
2294 #ifdef LODEPNG_COMPILE_PNG
2295 
2296 /* ////////////////////////////////////////////////////////////////////////// */
2297 /* / CRC32 / */
2298 /* ////////////////////////////////////////////////////////////////////////// */
2299 
2300 /* CRC polynomial: 0xedb88320 */
2301 static unsigned lodepng_crc32_table[256] = {
2302  0u, 1996959894u, 3993919788u, 2567524794u, 124634137u, 1886057615u, 3915621685u, 2657392035u,
2303  249268274u, 2044508324u, 3772115230u, 2547177864u, 162941995u, 2125561021u, 3887607047u, 2428444049u,
2304  498536548u, 1789927666u, 4089016648u, 2227061214u, 450548861u, 1843258603u, 4107580753u, 2211677639u,
2305  325883990u, 1684777152u, 4251122042u, 2321926636u, 335633487u, 1661365465u, 4195302755u, 2366115317u,
2306  997073096u, 1281953886u, 3579855332u, 2724688242u, 1006888145u, 1258607687u, 3524101629u, 2768942443u,
2307  901097722u, 1119000684u, 3686517206u, 2898065728u, 853044451u, 1172266101u, 3705015759u, 2882616665u,
2308  651767980u, 1373503546u, 3369554304u, 3218104598u, 565507253u, 1454621731u, 3485111705u, 3099436303u,
2309  671266974u, 1594198024u, 3322730930u, 2970347812u, 795835527u, 1483230225u, 3244367275u, 3060149565u,
2310  1994146192u, 31158534u, 2563907772u, 4023717930u, 1907459465u, 112637215u, 2680153253u, 3904427059u,
2311  2013776290u, 251722036u, 2517215374u, 3775830040u, 2137656763u, 141376813u, 2439277719u, 3865271297u,
2312  1802195444u, 476864866u, 2238001368u, 4066508878u, 1812370925u, 453092731u, 2181625025u, 4111451223u,
2313  1706088902u, 314042704u, 2344532202u, 4240017532u, 1658658271u, 366619977u, 2362670323u, 4224994405u,
2314  1303535960u, 984961486u, 2747007092u, 3569037538u, 1256170817u, 1037604311u, 2765210733u, 3554079995u,
2315  1131014506u, 879679996u, 2909243462u, 3663771856u, 1141124467u, 855842277u, 2852801631u, 3708648649u,
2316  1342533948u, 654459306u, 3188396048u, 3373015174u, 1466479909u, 544179635u, 3110523913u, 3462522015u,
2317  1591671054u, 702138776u, 2966460450u, 3352799412u, 1504918807u, 783551873u, 3082640443u, 3233442989u,
2318  3988292384u, 2596254646u, 62317068u, 1957810842u, 3939845945u, 2647816111u, 81470997u, 1943803523u,
2319  3814918930u, 2489596804u, 225274430u, 2053790376u, 3826175755u, 2466906013u, 167816743u, 2097651377u,
2320  4027552580u, 2265490386u, 503444072u, 1762050814u, 4150417245u, 2154129355u, 426522225u, 1852507879u,
2321  4275313526u, 2312317920u, 282753626u, 1742555852u, 4189708143u, 2394877945u, 397917763u, 1622183637u,
2322  3604390888u, 2714866558u, 953729732u, 1340076626u, 3518719985u, 2797360999u, 1068828381u, 1219638859u,
2323  3624741850u, 2936675148u, 906185462u, 1090812512u, 3747672003u, 2825379669u, 829329135u, 1181335161u,
2324  3412177804u, 3160834842u, 628085408u, 1382605366u, 3423369109u, 3138078467u, 570562233u, 1426400815u,
2325  3317316542u, 2998733608u, 733239954u, 1555261956u, 3268935591u, 3050360625u, 752459403u, 1541320221u,
2326  2607071920u, 3965973030u, 1969922972u, 40735498u, 2617837225u, 3943577151u, 1913087877u, 83908371u,
2327  2512341634u, 3803740692u, 2075208622u, 213261112u, 2463272603u, 3855990285u, 2094854071u, 198958881u,
2328  2262029012u, 4057260610u, 1759359992u, 534414190u, 2176718541u, 4139329115u, 1873836001u, 414664567u,
2329  2282248934u, 4279200368u, 1711684554u, 285281116u, 2405801727u, 4167216745u, 1634467795u, 376229701u,
2330  2685067896u, 3608007406u, 1308918612u, 956543938u, 2808555105u, 3495958263u, 1231636301u, 1047427035u,
2331  2932959818u, 3654703836u, 1088359270u, 936918000u, 2847714899u, 3736837829u, 1202900863u, 817233897u,
2332  3183342108u, 3401237130u, 1404277552u, 615818150u, 3134207493u, 3453421203u, 1423857449u, 601450431u,
2333  3009837614u, 3294710456u, 1567103746u, 711928724u, 3020668471u, 3272380065u, 1510334235u, 755167117u
2334 };
2335 
2336 /*Return the CRC of the bytes buf[0..len-1].*/
2337 unsigned lodepng_crc32(const unsigned char* buf, size_t len)
2338 {
2339  unsigned c = 0xffffffffL;
2340  size_t n;
2341 
2342  for(n = 0; n < len; ++n)
2343  {
2344  c = lodepng_crc32_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
2345  }
2346  return c ^ 0xffffffffL;
2347 }
2348 
2349 /* ////////////////////////////////////////////////////////////////////////// */
2350 /* / Reading and writing single bits and bytes from/to stream for LodePNG / */
2351 /* ////////////////////////////////////////////////////////////////////////// */
2352 
2353 static unsigned char readBitFromReversedStream(size_t* bitpointer, const unsigned char* bitstream)
2354 {
2355  unsigned char result = (unsigned char)((bitstream[(*bitpointer) >> 3] >> (7 - ((*bitpointer) & 0x7))) & 1);
2356  ++(*bitpointer);
2357  return result;
2358 }
2359 
2360 static unsigned readBitsFromReversedStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
2361 {
2362  unsigned result = 0;
2363  size_t i;
2364  for(i = nbits - 1; i < nbits; --i)
2365  {
2366  result += (unsigned)readBitFromReversedStream(bitpointer, bitstream) << i;
2367  }
2368  return result;
2369 }
2370 
2371 #ifdef LODEPNG_COMPILE_DECODER
2372 static void setBitOfReversedStream0(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
2373 {
2374  /*the current bit in bitstream must be 0 for this to work*/
2375  if(bit)
2376  {
2377  /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/
2378  bitstream[(*bitpointer) >> 3] |= (bit << (7 - ((*bitpointer) & 0x7)));
2379  }
2380  ++(*bitpointer);
2381 }
2382 #endif /*LODEPNG_COMPILE_DECODER*/
2383 
2384 static void setBitOfReversedStream(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
2385 {
2386  /*the current bit in bitstream may be 0 or 1 for this to work*/
2387  if(bit == 0) bitstream[(*bitpointer) >> 3] &= (unsigned char)(~(1 << (7 - ((*bitpointer) & 0x7))));
2388  else bitstream[(*bitpointer) >> 3] |= (1 << (7 - ((*bitpointer) & 0x7)));
2389  ++(*bitpointer);
2390 }
2391 
2392 /* ////////////////////////////////////////////////////////////////////////// */
2393 /* / PNG chunks / */
2394 /* ////////////////////////////////////////////////////////////////////////// */
2395 
2396 unsigned lodepng_chunk_length(const unsigned char* chunk)
2397 {
2398  return lodepng_read32bitInt(&chunk[0]);
2399 }
2400 
2401 void lodepng_chunk_type(char type[5], const unsigned char* chunk)
2402 {
2403  unsigned i;
2404  for(i = 0; i != 4; ++i) type[i] = (char)chunk[4 + i];
2405  type[4] = 0; /*null termination char*/
2406 }
2407 
2408 unsigned char lodepng_chunk_type_equals(const unsigned char* chunk, const char* type)
2409 {
2410  if(strlen(type) != 4) return 0;
2411  return (chunk[4] == type[0] && chunk[5] == type[1] && chunk[6] == type[2] && chunk[7] == type[3]);
2412 }
2413 
2414 unsigned char lodepng_chunk_ancillary(const unsigned char* chunk)
2415 {
2416  return((chunk[4] & 32) != 0);
2417 }
2418 
2419 unsigned char lodepng_chunk_private(const unsigned char* chunk)
2420 {
2421  return((chunk[6] & 32) != 0);
2422 }
2423 
2424 unsigned char lodepng_chunk_safetocopy(const unsigned char* chunk)
2425 {
2426  return((chunk[7] & 32) != 0);
2427 }
2428 
2429 unsigned char* lodepng_chunk_data(unsigned char* chunk)
2430 {
2431  return &chunk[8];
2432 }
2433 
2434 const unsigned char* lodepng_chunk_data_const(const unsigned char* chunk)
2435 {
2436  return &chunk[8];
2437 }
2438 
2439 unsigned lodepng_chunk_check_crc(const unsigned char* chunk)
2440 {
2441  unsigned length = lodepng_chunk_length(chunk);
2442  unsigned CRC = lodepng_read32bitInt(&chunk[length + 8]);
2443  /*the CRC is taken of the data and the 4 chunk type letters, not the length*/
2444  unsigned checksum = lodepng_crc32(&chunk[4], length + 4);
2445  if(CRC != checksum) return 1;
2446  else return 0;
2447 }
2448 
2449 void lodepng_chunk_generate_crc(unsigned char* chunk)
2450 {
2451  unsigned length = lodepng_chunk_length(chunk);
2452  unsigned CRC = lodepng_crc32(&chunk[4], length + 4);
2453  lodepng_set32bitInt(chunk + 8 + length, CRC);
2454 }
2455 
2456 unsigned char* lodepng_chunk_next(unsigned char* chunk)
2457 {
2458  unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
2459  return &chunk[total_chunk_length];
2460 }
2461 
2462 const unsigned char* lodepng_chunk_next_const(const unsigned char* chunk)
2463 {
2464  unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
2465  return &chunk[total_chunk_length];
2466 }
2467 
2468 unsigned lodepng_chunk_append(unsigned char** out, size_t* outlength, const unsigned char* chunk)
2469 {
2470  unsigned i;
2471  unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
2472  unsigned char *chunk_start, *new_buffer;
2473  size_t new_length = (*outlength) + total_chunk_length;
2474  if(new_length < total_chunk_length || new_length < (*outlength)) return 77; /*integer overflow happened*/
2475 
2476  new_buffer = (unsigned char*)lodepng_realloc(*out, new_length);
2477  if(!new_buffer) return 83; /*alloc fail*/
2478  (*out) = new_buffer;
2479  (*outlength) = new_length;
2480  chunk_start = &(*out)[new_length - total_chunk_length];
2481 
2482  for(i = 0; i != total_chunk_length; ++i) chunk_start[i] = chunk[i];
2483 
2484  return 0;
2485 }
2486 
2487 unsigned lodepng_chunk_create(unsigned char** out, size_t* outlength, unsigned length,
2488  const char* type, const unsigned char* data)
2489 {
2490  unsigned i;
2491  unsigned char *chunk, *new_buffer;
2492  size_t new_length = (*outlength) + length + 12;
2493  if(new_length < length + 12 || new_length < (*outlength)) return 77; /*integer overflow happened*/
2494  new_buffer = (unsigned char*)lodepng_realloc(*out, new_length);
2495  if(!new_buffer) return 83; /*alloc fail*/
2496  (*out) = new_buffer;
2497  (*outlength) = new_length;
2498  chunk = &(*out)[(*outlength) - length - 12];
2499 
2500  /*1: length*/
2501  lodepng_set32bitInt(chunk, (unsigned)length);
2502 
2503  /*2: chunk name (4 letters)*/
2504  chunk[4] = (unsigned char)type[0];
2505  chunk[5] = (unsigned char)type[1];
2506  chunk[6] = (unsigned char)type[2];
2507  chunk[7] = (unsigned char)type[3];
2508 
2509  /*3: the data*/
2510  for(i = 0; i != length; ++i) chunk[8 + i] = data[i];
2511 
2512  /*4: CRC (of the chunkname characters and the data)*/
2513  lodepng_chunk_generate_crc(chunk);
2514 
2515  return 0;
2516 }
2517 
2518 /* ////////////////////////////////////////////////////////////////////////// */
2519 /* / Color types and such / */
2520 /* ////////////////////////////////////////////////////////////////////////// */
2521 
2522 /*return type is a LodePNG error code*/
2523 static unsigned checkColorValidity(LodePNGColorType colortype, unsigned bd) /*bd = bitdepth*/
2524 {
2525  switch(colortype)
2526  {
2527  case 0: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8 || bd == 16)) return 37; break; /*grey*/
2528  case 2: if(!( bd == 8 || bd == 16)) return 37; break; /*RGB*/
2529  case 3: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8 )) return 37; break; /*palette*/
2530  case 4: if(!( bd == 8 || bd == 16)) return 37; break; /*grey + alpha*/
2531  case 6: if(!( bd == 8 || bd == 16)) return 37; break; /*RGBA*/
2532  default: return 31;
2533  }
2534  return 0; /*allowed color type / bits combination*/
2535 }
2536 
2537 static unsigned getNumColorChannels(LodePNGColorType colortype)
2538 {
2539  switch(colortype)
2540  {
2541  case 0: return 1; /*grey*/
2542  case 2: return 3; /*RGB*/
2543  case 3: return 1; /*palette*/
2544  case 4: return 2; /*grey + alpha*/
2545  case 6: return 4; /*RGBA*/
2546  }
2547  return 0; /*unexisting color type*/
2548 }
2549 
2550 static unsigned lodepng_get_bpp_lct(LodePNGColorType colortype, unsigned bitdepth)
2551 {
2552  /*bits per pixel is amount of channels * bits per channel*/
2553  return getNumColorChannels(colortype) * bitdepth;
2554 }
2555 
2556 /* ////////////////////////////////////////////////////////////////////////// */
2557 
2558 void lodepng_color_mode_init(LodePNGColorMode* info)
2559 {
2560  info->key_defined = 0;
2561  info->key_r = info->key_g = info->key_b = 0;
2562  info->colortype = LCT_RGBA;
2563  info->bitdepth = 8;
2564  info->palette = 0;
2565  info->palettesize = 0;
2566 }
2567 
2568 void lodepng_color_mode_cleanup(LodePNGColorMode* info)
2569 {
2570  lodepng_palette_clear(info);
2571 }
2572 
2573 unsigned lodepng_color_mode_copy(LodePNGColorMode* dest, const LodePNGColorMode* source)
2574 {
2575  size_t i;
2576  lodepng_color_mode_cleanup(dest);
2577  *dest = *source;
2578  if(source->palette)
2579  {
2580  dest->palette = (unsigned char*)lodepng_malloc(1024);
2581  if(!dest->palette && source->palettesize) return 83; /*alloc fail*/
2582  for(i = 0; i != source->palettesize * 4; ++i) dest->palette[i] = source->palette[i];
2583  }
2584  return 0;
2585 }
2586 
2587 static int lodepng_color_mode_equal(const LodePNGColorMode* a, const LodePNGColorMode* b)
2588 {
2589  size_t i;
2590  if(a->colortype != b->colortype) return 0;
2591  if(a->bitdepth != b->bitdepth) return 0;
2592  if(a->key_defined != b->key_defined) return 0;
2593  if(a->key_defined)
2594  {
2595  if(a->key_r != b->key_r) return 0;
2596  if(a->key_g != b->key_g) return 0;
2597  if(a->key_b != b->key_b) return 0;
2598  }
2599  if(a->palettesize != b->palettesize) return 0;
2600  for(i = 0; i != a->palettesize * 4; ++i)
2601  {
2602  if(a->palette[i] != b->palette[i]) return 0;
2603  }
2604  return 1;
2605 }
2606 
2607 void lodepng_palette_clear(LodePNGColorMode* info)
2608 {
2609  if(info->palette) lodepng_free(info->palette);
2610  info->palette = 0;
2611  info->palettesize = 0;
2612 }
2613 
2614 unsigned lodepng_palette_add(LodePNGColorMode* info,
2615  unsigned char r, unsigned char g, unsigned char b, unsigned char a)
2616 {
2617  unsigned char* data;
2618  /*the same resize technique as C++ std::vectors is used, and here it's made so that for a palette with
2619  the max of 256 colors, it'll have the exact alloc size*/
2620  if(!info->palette) /*allocate palette if empty*/
2621  {
2622  /*room for 256 colors with 4 bytes each*/
2623  data = (unsigned char*)lodepng_realloc(info->palette, 1024);
2624  if(!data) return 83; /*alloc fail*/
2625  else info->palette = data;
2626  }
2627  info->palette[4 * info->palettesize + 0] = r;
2628  info->palette[4 * info->palettesize + 1] = g;
2629  info->palette[4 * info->palettesize + 2] = b;
2630  info->palette[4 * info->palettesize + 3] = a;
2631  ++info->palettesize;
2632  return 0;
2633 }
2634 
2635 unsigned lodepng_get_bpp(const LodePNGColorMode* info)
2636 {
2637  /*calculate bits per pixel out of colortype and bitdepth*/
2638  return lodepng_get_bpp_lct(info->colortype, info->bitdepth);
2639 }
2640 
2641 unsigned lodepng_get_channels(const LodePNGColorMode* info)
2642 {
2643  return getNumColorChannels(info->colortype);
2644 }
2645 
2646 unsigned lodepng_is_greyscale_type(const LodePNGColorMode* info)
2647 {
2648  return info->colortype == LCT_GREY || info->colortype == LCT_GREY_ALPHA;
2649 }
2650 
2651 unsigned lodepng_is_alpha_type(const LodePNGColorMode* info)
2652 {
2653  return (info->colortype & 4) != 0; /*4 or 6*/
2654 }
2655 
2656 unsigned lodepng_is_palette_type(const LodePNGColorMode* info)
2657 {
2658  return info->colortype == LCT_PALETTE;
2659 }
2660 
2661 unsigned lodepng_has_palette_alpha(const LodePNGColorMode* info)
2662 {
2663  size_t i;
2664  for(i = 0; i != info->palettesize; ++i)
2665  {
2666  if(info->palette[i * 4 + 3] < 255) return 1;
2667  }
2668  return 0;
2669 }
2670 
2671 unsigned lodepng_can_have_alpha(const LodePNGColorMode* info)
2672 {
2673  return info->key_defined
2674  || lodepng_is_alpha_type(info)
2675  || lodepng_has_palette_alpha(info);
2676 }
2677 
2678 size_t lodepng_get_raw_size(unsigned w, unsigned h, const LodePNGColorMode* color)
2679 {
2680  return (w * h * lodepng_get_bpp(color) + 7) / 8;
2681 }
2682 
2683 size_t lodepng_get_raw_size_lct(unsigned w, unsigned h, LodePNGColorType colortype, unsigned bitdepth)
2684 {
2685  return (w * h * lodepng_get_bpp_lct(colortype, bitdepth) + 7) / 8;
2686 }
2687 
2688 
2689 #ifdef LODEPNG_COMPILE_PNG
2690 #ifdef LODEPNG_COMPILE_DECODER
2691 /*in an idat chunk, each scanline is a multiple of 8 bits, unlike the lodepng output buffer*/
2692 static size_t lodepng_get_raw_size_idat(unsigned w, unsigned h, const LodePNGColorMode* color)
2693 {
2694  return h * ((w * lodepng_get_bpp(color) + 7) / 8);
2695 }
2696 #endif /*LODEPNG_COMPILE_DECODER*/
2697 #endif /*LODEPNG_COMPILE_PNG*/
2698 
2699 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2700 
2701 static void LodePNGUnknownChunks_init(LodePNGInfo* info)
2702 {
2703  unsigned i;
2704  for(i = 0; i != 3; ++i) info->unknown_chunks_data[i] = 0;
2705  for(i = 0; i != 3; ++i) info->unknown_chunks_size[i] = 0;
2706 }
2707 
2708 static void LodePNGUnknownChunks_cleanup(LodePNGInfo* info)
2709 {
2710  unsigned i;
2711  for(i = 0; i != 3; ++i) lodepng_free(info->unknown_chunks_data[i]);
2712 }
2713 
2714 static unsigned LodePNGUnknownChunks_copy(LodePNGInfo* dest, const LodePNGInfo* src)
2715 {
2716  unsigned i;
2717 
2718  LodePNGUnknownChunks_cleanup(dest);
2719 
2720  for(i = 0; i != 3; ++i)
2721  {
2722  size_t j;
2723  dest->unknown_chunks_size[i] = src->unknown_chunks_size[i];
2724  dest->unknown_chunks_data[i] = (unsigned char*)lodepng_malloc(src->unknown_chunks_size[i]);
2725  if(!dest->unknown_chunks_data[i] && dest->unknown_chunks_size[i]) return 83; /*alloc fail*/
2726  for(j = 0; j < src->unknown_chunks_size[i]; ++j)
2727  {
2728  dest->unknown_chunks_data[i][j] = src->unknown_chunks_data[i][j];
2729  }
2730  }
2731 
2732  return 0;
2733 }
2734 
2735 /******************************************************************************/
2736 
2737 static void LodePNGText_init(LodePNGInfo* info)
2738 {
2739  info->text_num = 0;
2740  info->text_keys = NULL;
2741  info->text_strings = NULL;
2742 }
2743 
2744 static void LodePNGText_cleanup(LodePNGInfo* info)
2745 {
2746  size_t i;
2747  for(i = 0; i != info->text_num; ++i)
2748  {
2749  string_cleanup(&info->text_keys[i]);
2750  string_cleanup(&info->text_strings[i]);
2751  }
2752  lodepng_free(info->text_keys);
2753  lodepng_free(info->text_strings);
2754 }
2755 
2756 static unsigned LodePNGText_copy(LodePNGInfo* dest, const LodePNGInfo* source)
2757 {
2758  size_t i = 0;
2759  dest->text_keys = 0;
2760  dest->text_strings = 0;
2761  dest->text_num = 0;
2762  for(i = 0; i != source->text_num; ++i)
2763  {
2764  CERROR_TRY_RETURN(lodepng_add_text(dest, source->text_keys[i], source->text_strings[i]));
2765  }
2766  return 0;
2767 }
2768 
2769 void lodepng_clear_text(LodePNGInfo* info)
2770 {
2771  LodePNGText_cleanup(info);
2772 }
2773 
2774 unsigned lodepng_add_text(LodePNGInfo* info, const char* key, const char* str)
2775 {
2776  char** new_keys = (char**)(lodepng_realloc(info->text_keys, sizeof(char*) * (info->text_num + 1)));
2777  char** new_strings = (char**)(lodepng_realloc(info->text_strings, sizeof(char*) * (info->text_num + 1)));
2778  if(!new_keys || !new_strings)
2779  {
2780  lodepng_free(new_keys);
2781  lodepng_free(new_strings);
2782  return 83; /*alloc fail*/
2783  }
2784 
2785  ++info->text_num;
2786  info->text_keys = new_keys;
2787  info->text_strings = new_strings;
2788 
2789  string_init(&info->text_keys[info->text_num - 1]);
2790  string_set(&info->text_keys[info->text_num - 1], key);
2791 
2792  string_init(&info->text_strings[info->text_num - 1]);
2793  string_set(&info->text_strings[info->text_num - 1], str);
2794 
2795  return 0;
2796 }
2797 
2798 /******************************************************************************/
2799 
2800 static void LodePNGIText_init(LodePNGInfo* info)
2801 {
2802  info->itext_num = 0;
2803  info->itext_keys = NULL;
2804  info->itext_langtags = NULL;
2805  info->itext_transkeys = NULL;
2806  info->itext_strings = NULL;
2807 }
2808 
2809 static void LodePNGIText_cleanup(LodePNGInfo* info)
2810 {
2811  size_t i;
2812  for(i = 0; i != info->itext_num; ++i)
2813  {
2814  string_cleanup(&info->itext_keys[i]);
2815  string_cleanup(&info->itext_langtags[i]);
2816  string_cleanup(&info->itext_transkeys[i]);
2817  string_cleanup(&info->itext_strings[i]);
2818  }
2819  lodepng_free(info->itext_keys);
2820  lodepng_free(info->itext_langtags);
2821  lodepng_free(info->itext_transkeys);
2822  lodepng_free(info->itext_strings);
2823 }
2824 
2825 static unsigned LodePNGIText_copy(LodePNGInfo* dest, const LodePNGInfo* source)
2826 {
2827  size_t i = 0;
2828  dest->itext_keys = 0;
2829  dest->itext_langtags = 0;
2830  dest->itext_transkeys = 0;
2831  dest->itext_strings = 0;
2832  dest->itext_num = 0;
2833  for(i = 0; i != source->itext_num; ++i)
2834  {
2835  CERROR_TRY_RETURN(lodepng_add_itext(dest, source->itext_keys[i], source->itext_langtags[i],
2836  source->itext_transkeys[i], source->itext_strings[i]));
2837  }
2838  return 0;
2839 }
2840 
2841 void lodepng_clear_itext(LodePNGInfo* info)
2842 {
2843  LodePNGIText_cleanup(info);
2844 }
2845 
2846 unsigned lodepng_add_itext(LodePNGInfo* info, const char* key, const char* langtag,
2847  const char* transkey, const char* str)
2848 {
2849  char** new_keys = (char**)(lodepng_realloc(info->itext_keys, sizeof(char*) * (info->itext_num + 1)));
2850  char** new_langtags = (char**)(lodepng_realloc(info->itext_langtags, sizeof(char*) * (info->itext_num + 1)));
2851  char** new_transkeys = (char**)(lodepng_realloc(info->itext_transkeys, sizeof(char*) * (info->itext_num + 1)));
2852  char** new_strings = (char**)(lodepng_realloc(info->itext_strings, sizeof(char*) * (info->itext_num + 1)));
2853  if(!new_keys || !new_langtags || !new_transkeys || !new_strings)
2854  {
2855  lodepng_free(new_keys);
2856  lodepng_free(new_langtags);
2857  lodepng_free(new_transkeys);
2858  lodepng_free(new_strings);
2859  return 83; /*alloc fail*/
2860  }
2861 
2862  ++info->itext_num;
2863  info->itext_keys = new_keys;
2864  info->itext_langtags = new_langtags;
2865  info->itext_transkeys = new_transkeys;
2866  info->itext_strings = new_strings;
2867 
2868  string_init(&info->itext_keys[info->itext_num - 1]);
2869  string_set(&info->itext_keys[info->itext_num - 1], key);
2870 
2871  string_init(&info->itext_langtags[info->itext_num - 1]);
2872  string_set(&info->itext_langtags[info->itext_num - 1], langtag);
2873 
2874  string_init(&info->itext_transkeys[info->itext_num - 1]);
2875  string_set(&info->itext_transkeys[info->itext_num - 1], transkey);
2876 
2877  string_init(&info->itext_strings[info->itext_num - 1]);
2878  string_set(&info->itext_strings[info->itext_num - 1], str);
2879 
2880  return 0;
2881 }
2882 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
2883 
2884 void lodepng_info_init(LodePNGInfo* info)
2885 {
2886  lodepng_color_mode_init(&info->color);
2887  info->interlace_method = 0;
2888  info->compression_method = 0;
2889  info->filter_method = 0;
2890 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2891  info->background_defined = 0;
2892  info->background_r = info->background_g = info->background_b = 0;
2893 
2894  LodePNGText_init(info);
2895  LodePNGIText_init(info);
2896 
2897  info->time_defined = 0;
2898  info->phys_defined = 0;
2899 
2900  LodePNGUnknownChunks_init(info);
2901 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
2902 }
2903 
2904 void lodepng_info_cleanup(LodePNGInfo* info)
2905 {
2906  lodepng_color_mode_cleanup(&info->color);
2907 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2908  LodePNGText_cleanup(info);
2909  LodePNGIText_cleanup(info);
2910 
2911  LodePNGUnknownChunks_cleanup(info);
2912 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
2913 }
2914 
2915 unsigned lodepng_info_copy(LodePNGInfo* dest, const LodePNGInfo* source)
2916 {
2917  lodepng_info_cleanup(dest);
2918  *dest = *source;
2919  lodepng_color_mode_init(&dest->color);
2920  CERROR_TRY_RETURN(lodepng_color_mode_copy(&dest->color, &source->color));
2921 
2922 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
2923  CERROR_TRY_RETURN(LodePNGText_copy(dest, source));
2924  CERROR_TRY_RETURN(LodePNGIText_copy(dest, source));
2925 
2926  LodePNGUnknownChunks_init(dest);
2927  CERROR_TRY_RETURN(LodePNGUnknownChunks_copy(dest, source));
2928 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
2929  return 0;
2930 }
2931 
2932 void lodepng_info_swap(LodePNGInfo* a, LodePNGInfo* b)
2933 {
2934  LodePNGInfo temp = *a;
2935  *a = *b;
2936  *b = temp;
2937 }
2938 
2939 /* ////////////////////////////////////////////////////////////////////////// */
2940 
2941 /*index: bitgroup index, bits: bitgroup size(1, 2 or 4), in: bitgroup value, out: octet array to add bits to*/
2942 static void addColorBits(unsigned char* out, size_t index, unsigned bits, unsigned in)
2943 {
2944  unsigned m = bits == 1 ? 7 : bits == 2 ? 3 : 1; /*8 / bits - 1*/
2945  /*p = the partial index in the byte, e.g. with 4 palettebits it is 0 for first half or 1 for second half*/
2946  unsigned p = index & m;
2947  in &= (1u << bits) - 1u; /*filter out any other bits of the input value*/
2948  in = in << (bits * (m - p));
2949  if(p == 0) out[index * bits / 8] = in;
2950  else out[index * bits / 8] |= in;
2951 }
2952 
2953 typedef struct ColorTree ColorTree;
2954 
2955 /*
2956 One node of a color tree
2957 This is the data structure used to count the number of unique colors and to get a palette
2958 index for a color. It's like an octree, but because the alpha channel is used too, each
2959 node has 16 instead of 8 children.
2960 */
2961 struct ColorTree
2962 {
2963  ColorTree* children[16]; /*up to 16 pointers to ColorTree of next level*/
2964  int index; /*the payload. Only has a meaningful value if this is in the last level*/
2965 };
2966 
2967 static void color_tree_init(ColorTree* tree)
2968 {
2969  int i;
2970  for(i = 0; i != 16; ++i) tree->children[i] = 0;
2971  tree->index = -1;
2972 }
2973 
2974 static void color_tree_cleanup(ColorTree* tree)
2975 {
2976  int i;
2977  for(i = 0; i != 16; ++i)
2978  {
2979  if(tree->children[i])
2980  {
2981  color_tree_cleanup(tree->children[i]);
2982  lodepng_free(tree->children[i]);
2983  }
2984  }
2985 }
2986 
2987 /*returns -1 if color not present, its index otherwise*/
2988 static int color_tree_get(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
2989 {
2990  int bit = 0;
2991  for(bit = 0; bit < 8; ++bit)
2992  {
2993  int i = 8 * ((r >> bit) & 1) + 4 * ((g >> bit) & 1) + 2 * ((b >> bit) & 1) + 1 * ((a >> bit) & 1);
2994  if(!tree->children[i]) return -1;
2995  else tree = tree->children[i];
2996  }
2997  return tree ? tree->index : -1;
2998 }
2999 
3000 #ifdef LODEPNG_COMPILE_ENCODER
3001 static int color_tree_has(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
3002 {
3003  return color_tree_get(tree, r, g, b, a) >= 0;
3004 }
3005 #endif /*LODEPNG_COMPILE_ENCODER*/
3006 
3007 /*color is not allowed to already exist.
3008 Index should be >= 0 (it's signed to be compatible with using -1 for "doesn't exist")*/
3009 static void color_tree_add(ColorTree* tree,
3010  unsigned char r, unsigned char g, unsigned char b, unsigned char a, unsigned index)
3011 {
3012  int bit;
3013  for(bit = 0; bit < 8; ++bit)
3014  {
3015  int i = 8 * ((r >> bit) & 1) + 4 * ((g >> bit) & 1) + 2 * ((b >> bit) & 1) + 1 * ((a >> bit) & 1);
3016  if(!tree->children[i])
3017  {
3018  tree->children[i] = (ColorTree*)lodepng_malloc(sizeof(ColorTree));
3019  color_tree_init(tree->children[i]);
3020  }
3021  tree = tree->children[i];
3022  }
3023  tree->index = (int)index;
3024 }
3025 
3026 /*put a pixel, given its RGBA color, into image of any color type*/
3027 static unsigned rgba8ToPixel(unsigned char* out, size_t i,
3028  const LodePNGColorMode* mode, ColorTree* tree /*for palette*/,
3029  unsigned char r, unsigned char g, unsigned char b, unsigned char a)
3030 {
3031  if(mode->colortype == LCT_GREY)
3032  {
3033  unsigned char grey = r; /*((unsigned short)r + g + b) / 3*/;
3034  if(mode->bitdepth == 8) out[i] = grey;
3035  else if(mode->bitdepth == 16) out[i * 2 + 0] = out[i * 2 + 1] = grey;
3036  else
3037  {
3038  /*take the most significant bits of grey*/
3039  grey = (grey >> (8 - mode->bitdepth)) & ((1 << mode->bitdepth) - 1);
3040  addColorBits(out, i, mode->bitdepth, grey);
3041  }
3042  }
3043  else if(mode->colortype == LCT_RGB)
3044  {
3045  if(mode->bitdepth == 8)
3046  {
3047  out[i * 3 + 0] = r;
3048  out[i * 3 + 1] = g;
3049  out[i * 3 + 2] = b;
3050  }
3051  else
3052  {
3053  out[i * 6 + 0] = out[i * 6 + 1] = r;
3054  out[i * 6 + 2] = out[i * 6 + 3] = g;
3055  out[i * 6 + 4] = out[i * 6 + 5] = b;
3056  }
3057  }
3058  else if(mode->colortype == LCT_PALETTE)
3059  {
3060  int index = color_tree_get(tree, r, g, b, a);
3061  if(index < 0) return 82; /*color not in palette*/
3062  if(mode->bitdepth == 8) out[i] = index;
3063  else addColorBits(out, i, mode->bitdepth, (unsigned)index);
3064  }
3065  else if(mode->colortype == LCT_GREY_ALPHA)
3066  {
3067  unsigned char grey = r; /*((unsigned short)r + g + b) / 3*/;
3068  if(mode->bitdepth == 8)
3069  {
3070  out[i * 2 + 0] = grey;
3071  out[i * 2 + 1] = a;
3072  }
3073  else if(mode->bitdepth == 16)
3074  {
3075  out[i * 4 + 0] = out[i * 4 + 1] = grey;
3076  out[i * 4 + 2] = out[i * 4 + 3] = a;
3077  }
3078  }
3079  else if(mode->colortype == LCT_RGBA)
3080  {
3081  if(mode->bitdepth == 8)
3082  {
3083  out[i * 4 + 0] = r;
3084  out[i * 4 + 1] = g;
3085  out[i * 4 + 2] = b;
3086  out[i * 4 + 3] = a;
3087  }
3088  else
3089  {
3090  out[i * 8 + 0] = out[i * 8 + 1] = r;
3091  out[i * 8 + 2] = out[i * 8 + 3] = g;
3092  out[i * 8 + 4] = out[i * 8 + 5] = b;
3093  out[i * 8 + 6] = out[i * 8 + 7] = a;
3094  }
3095  }
3096 
3097  return 0; /*no error*/
3098 }
3099 
3100 /*put a pixel, given its RGBA16 color, into image of any color 16-bitdepth type*/
3101 static void rgba16ToPixel(unsigned char* out, size_t i,
3102  const LodePNGColorMode* mode,
3103  unsigned short r, unsigned short g, unsigned short b, unsigned short a)
3104 {
3105  if(mode->colortype == LCT_GREY)
3106  {
3107  unsigned short grey = r; /*((unsigned)r + g + b) / 3*/;
3108  out[i * 2 + 0] = (grey >> 8) & 255;
3109  out[i * 2 + 1] = grey & 255;
3110  }
3111  else if(mode->colortype == LCT_RGB)
3112  {
3113  out[i * 6 + 0] = (r >> 8) & 255;
3114  out[i * 6 + 1] = r & 255;
3115  out[i * 6 + 2] = (g >> 8) & 255;
3116  out[i * 6 + 3] = g & 255;
3117  out[i * 6 + 4] = (b >> 8) & 255;
3118  out[i * 6 + 5] = b & 255;
3119  }
3120  else if(mode->colortype == LCT_GREY_ALPHA)
3121  {
3122  unsigned short grey = r; /*((unsigned)r + g + b) / 3*/;
3123  out[i * 4 + 0] = (grey >> 8) & 255;
3124  out[i * 4 + 1] = grey & 255;
3125  out[i * 4 + 2] = (a >> 8) & 255;
3126  out[i * 4 + 3] = a & 255;
3127  }
3128  else if(mode->colortype == LCT_RGBA)
3129  {
3130  out[i * 8 + 0] = (r >> 8) & 255;
3131  out[i * 8 + 1] = r & 255;
3132  out[i * 8 + 2] = (g >> 8) & 255;
3133  out[i * 8 + 3] = g & 255;
3134  out[i * 8 + 4] = (b >> 8) & 255;
3135  out[i * 8 + 5] = b & 255;
3136  out[i * 8 + 6] = (a >> 8) & 255;
3137  out[i * 8 + 7] = a & 255;
3138  }
3139 }
3140 
3141 /*Get RGBA8 color of pixel with index i (y * width + x) from the raw image with given color type.*/
3142 static void getPixelColorRGBA8(unsigned char* r, unsigned char* g,
3143  unsigned char* b, unsigned char* a,
3144  const unsigned char* in, size_t i,
3145  const LodePNGColorMode* mode)
3146 {
3147  if(mode->colortype == LCT_GREY)
3148  {
3149  if(mode->bitdepth == 8)
3150  {
3151  *r = *g = *b = in[i];
3152  if(mode->key_defined && *r == mode->key_r) *a = 0;
3153  else *a = 255;
3154  }
3155  else if(mode->bitdepth == 16)
3156  {
3157  *r = *g = *b = in[i * 2 + 0];
3158  if(mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r) *a = 0;
3159  else *a = 255;
3160  }
3161  else
3162  {
3163  unsigned highest = ((1U << mode->bitdepth) - 1U); /*highest possible value for this bit depth*/
3164  size_t j = i * mode->bitdepth;
3165  unsigned value = readBitsFromReversedStream(&j, in, mode->bitdepth);
3166  *r = *g = *b = (value * 255) / highest;
3167  if(mode->key_defined && value == mode->key_r) *a = 0;
3168  else *a = 255;
3169  }
3170  }
3171  else if(mode->colortype == LCT_RGB)
3172  {
3173  if(mode->bitdepth == 8)
3174  {
3175  *r = in[i * 3 + 0]; *g = in[i * 3 + 1]; *b = in[i * 3 + 2];
3176  if(mode->key_defined && *r == mode->key_r && *g == mode->key_g && *b == mode->key_b) *a = 0;
3177  else *a = 255;
3178  }
3179  else
3180  {
3181  *r = in[i * 6 + 0];
3182  *g = in[i * 6 + 2];
3183  *b = in[i * 6 + 4];
3184  if(mode->key_defined && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
3185  && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
3186  && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b) *a = 0;
3187  else *a = 255;
3188  }
3189  }
3190  else if(mode->colortype == LCT_PALETTE)
3191  {
3192  unsigned index;
3193  if(mode->bitdepth == 8) index = in[i];
3194  else
3195  {
3196  size_t j = i * mode->bitdepth;
3197  index = readBitsFromReversedStream(&j, in, mode->bitdepth);
3198  }
3199 
3200  if(index >= mode->palettesize)
3201  {
3202  /*This is an error according to the PNG spec, but common PNG decoders make it black instead.
3203  Done here too, slightly faster due to no error handling needed.*/
3204  *r = *g = *b = 0;
3205  *a = 255;
3206  }
3207  else
3208  {
3209  *r = mode->palette[index * 4 + 0];
3210  *g = mode->palette[index * 4 + 1];
3211  *b = mode->palette[index * 4 + 2];
3212  *a = mode->palette[index * 4 + 3];
3213  }
3214  }
3215  else if(mode->colortype == LCT_GREY_ALPHA)
3216  {
3217  if(mode->bitdepth == 8)
3218  {
3219  *r = *g = *b = in[i * 2 + 0];
3220  *a = in[i * 2 + 1];
3221  }
3222  else
3223  {
3224  *r = *g = *b = in[i * 4 + 0];
3225  *a = in[i * 4 + 2];
3226  }
3227  }
3228  else if(mode->colortype == LCT_RGBA)
3229  {
3230  if(mode->bitdepth == 8)
3231  {
3232  *r = in[i * 4 + 0];
3233  *g = in[i * 4 + 1];
3234  *b = in[i * 4 + 2];
3235  *a = in[i * 4 + 3];
3236  }
3237  else
3238  {
3239  *r = in[i * 8 + 0];
3240  *g = in[i * 8 + 2];
3241  *b = in[i * 8 + 4];
3242  *a = in[i * 8 + 6];
3243  }
3244  }
3245 }
3246 
3247 /*Similar to getPixelColorRGBA8, but with all the for loops inside of the color
3248 mode test cases, optimized to convert the colors much faster, when converting
3249 to RGBA or RGB with 8 bit per cannel. buffer must be RGBA or RGB output with
3250 enough memory, if has_alpha is true the output is RGBA. mode has the color mode
3251 of the input buffer.*/
3252 static void getPixelColorsRGBA8(unsigned char* buffer, size_t numpixels,
3253  unsigned has_alpha, const unsigned char* in,
3254  const LodePNGColorMode* mode)
3255 {
3256  unsigned num_channels = has_alpha ? 4 : 3;
3257  size_t i;
3258  if(mode->colortype == LCT_GREY)
3259  {
3260  if(mode->bitdepth == 8)
3261  {
3262  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3263  {
3264  buffer[0] = buffer[1] = buffer[2] = in[i];
3265  if(has_alpha) buffer[3] = mode->key_defined && in[i] == mode->key_r ? 0 : 255;
3266  }
3267  }
3268  else if(mode->bitdepth == 16)
3269  {
3270  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3271  {
3272  buffer[0] = buffer[1] = buffer[2] = in[i * 2];
3273  if(has_alpha) buffer[3] = mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r ? 0 : 255;
3274  }
3275  }
3276  else
3277  {
3278  unsigned highest = ((1U << mode->bitdepth) - 1U); /*highest possible value for this bit depth*/
3279  size_t j = 0;
3280  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3281  {
3282  unsigned value = readBitsFromReversedStream(&j, in, mode->bitdepth);
3283  buffer[0] = buffer[1] = buffer[2] = (value * 255) / highest;
3284  if(has_alpha) buffer[3] = mode->key_defined && value == mode->key_r ? 0 : 255;
3285  }
3286  }
3287  }
3288  else if(mode->colortype == LCT_RGB)
3289  {
3290  if(mode->bitdepth == 8)
3291  {
3292  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3293  {
3294  buffer[0] = in[i * 3 + 0];
3295  buffer[1] = in[i * 3 + 1];
3296  buffer[2] = in[i * 3 + 2];
3297  if(has_alpha) buffer[3] = mode->key_defined && buffer[0] == mode->key_r
3298  && buffer[1]== mode->key_g && buffer[2] == mode->key_b ? 0 : 255;
3299  }
3300  }
3301  else
3302  {
3303  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3304  {
3305  buffer[0] = in[i * 6 + 0];
3306  buffer[1] = in[i * 6 + 2];
3307  buffer[2] = in[i * 6 + 4];
3308  if(has_alpha) buffer[3] = mode->key_defined
3309  && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
3310  && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
3311  && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b ? 0 : 255;
3312  }
3313  }
3314  }
3315  else if(mode->colortype == LCT_PALETTE)
3316  {
3317  unsigned index;
3318  size_t j = 0;
3319  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3320  {
3321  if(mode->bitdepth == 8) index = in[i];
3322  else index = readBitsFromReversedStream(&j, in, mode->bitdepth);
3323 
3324  if(index >= mode->palettesize)
3325  {
3326  /*This is an error according to the PNG spec, but most PNG decoders make it black instead.
3327  Done here too, slightly faster due to no error handling needed.*/
3328  buffer[0] = buffer[1] = buffer[2] = 0;
3329  if(has_alpha) buffer[3] = 255;
3330  }
3331  else
3332  {
3333  buffer[0] = mode->palette[index * 4 + 0];
3334  buffer[1] = mode->palette[index * 4 + 1];
3335  buffer[2] = mode->palette[index * 4 + 2];
3336  if(has_alpha) buffer[3] = mode->palette[index * 4 + 3];
3337  }
3338  }
3339  }
3340  else if(mode->colortype == LCT_GREY_ALPHA)
3341  {
3342  if(mode->bitdepth == 8)
3343  {
3344  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3345  {
3346  buffer[0] = buffer[1] = buffer[2] = in[i * 2 + 0];
3347  if(has_alpha) buffer[3] = in[i * 2 + 1];
3348  }
3349  }
3350  else
3351  {
3352  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3353  {
3354  buffer[0] = buffer[1] = buffer[2] = in[i * 4 + 0];
3355  if(has_alpha) buffer[3] = in[i * 4 + 2];
3356  }
3357  }
3358  }
3359  else if(mode->colortype == LCT_RGBA)
3360  {
3361  if(mode->bitdepth == 8)
3362  {
3363  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3364  {
3365  buffer[0] = in[i * 4 + 0];
3366  buffer[1] = in[i * 4 + 1];
3367  buffer[2] = in[i * 4 + 2];
3368  if(has_alpha) buffer[3] = in[i * 4 + 3];
3369  }
3370  }
3371  else
3372  {
3373  for(i = 0; i != numpixels; ++i, buffer += num_channels)
3374  {
3375  buffer[0] = in[i * 8 + 0];
3376  buffer[1] = in[i * 8 + 2];
3377  buffer[2] = in[i * 8 + 4];
3378  if(has_alpha) buffer[3] = in[i * 8 + 6];
3379  }
3380  }
3381  }
3382 }
3383 
3384 /*Get RGBA16 color of pixel with index i (y * width + x) from the raw image with
3385 given color type, but the given color type must be 16-bit itself.*/
3386 static void getPixelColorRGBA16(unsigned short* r, unsigned short* g, unsigned short* b, unsigned short* a,
3387  const unsigned char* in, size_t i, const LodePNGColorMode* mode)
3388 {
3389  if(mode->colortype == LCT_GREY)
3390  {
3391  *r = *g = *b = 256 * in[i * 2 + 0] + in[i * 2 + 1];
3392  if(mode->key_defined && 256U * in[i * 2 + 0] + in[i * 2 + 1] == mode->key_r) *a = 0;
3393  else *a = 65535;
3394  }
3395  else if(mode->colortype == LCT_RGB)
3396  {
3397  *r = 256 * in[i * 6 + 0] + in[i * 6 + 1];
3398  *g = 256 * in[i * 6 + 2] + in[i * 6 + 3];
3399  *b = 256 * in[i * 6 + 4] + in[i * 6 + 5];
3400  if(mode->key_defined && 256U * in[i * 6 + 0] + in[i * 6 + 1] == mode->key_r
3401  && 256U * in[i * 6 + 2] + in[i * 6 + 3] == mode->key_g
3402  && 256U * in[i * 6 + 4] + in[i * 6 + 5] == mode->key_b) *a = 0;
3403  else *a = 65535;
3404  }
3405  else if(mode->colortype == LCT_GREY_ALPHA)
3406  {
3407  *r = *g = *b = 256 * in[i * 4 + 0] + in[i * 4 + 1];
3408  *a = 256 * in[i * 4 + 2] + in[i * 4 + 3];
3409  }
3410  else if(mode->colortype == LCT_RGBA)
3411  {
3412  *r = 256 * in[i * 8 + 0] + in[i * 8 + 1];
3413  *g = 256 * in[i * 8 + 2] + in[i * 8 + 3];
3414  *b = 256 * in[i * 8 + 4] + in[i * 8 + 5];
3415  *a = 256 * in[i * 8 + 6] + in[i * 8 + 7];
3416  }
3417 }
3418 
3419 unsigned lodepng_convert(unsigned char* out, const unsigned char* in,
3420  LodePNGColorMode* mode_out, const LodePNGColorMode* mode_in,
3421  unsigned w, unsigned h)
3422 {
3423  size_t i;
3424  ColorTree tree;
3425  size_t numpixels = w * h;
3426 
3427  if(lodepng_color_mode_equal(mode_out, mode_in))
3428  {
3429  size_t numbytes = lodepng_get_raw_size(w, h, mode_in);
3430  for(i = 0; i != numbytes; ++i) out[i] = in[i];
3431  return 0;
3432  }
3433 
3434  if(mode_out->colortype == LCT_PALETTE)
3435  {
3436  size_t palsize = 1u << mode_out->bitdepth;
3437  if(mode_out->palettesize < palsize) palsize = mode_out->palettesize;
3438  color_tree_init(&tree);
3439  for(i = 0; i != palsize; ++i)
3440  {
3441  unsigned char* p = &mode_out->palette[i * 4];
3442  color_tree_add(&tree, p[0], p[1], p[2], p[3], i);
3443  }
3444  }
3445 
3446  if(mode_in->bitdepth == 16 && mode_out->bitdepth == 16)
3447  {
3448  for(i = 0; i != numpixels; ++i)
3449  {
3450  unsigned short r = 0, g = 0, b = 0, a = 0;
3451  getPixelColorRGBA16(&r, &g, &b, &a, in, i, mode_in);
3452  rgba16ToPixel(out, i, mode_out, r, g, b, a);
3453  }
3454  }
3455  else if(mode_out->bitdepth == 8 && mode_out->colortype == LCT_RGBA)
3456  {
3457  getPixelColorsRGBA8(out, numpixels, 1, in, mode_in);
3458  }
3459  else if(mode_out->bitdepth == 8 && mode_out->colortype == LCT_RGB)
3460  {
3461  getPixelColorsRGBA8(out, numpixels, 0, in, mode_in);
3462  }
3463  else
3464  {
3465  unsigned char r = 0, g = 0, b = 0, a = 0;
3466  for(i = 0; i != numpixels; ++i)
3467  {
3468  getPixelColorRGBA8(&r, &g, &b, &a, in, i, mode_in);
3469  rgba8ToPixel(out, i, mode_out, &tree, r, g, b, a);
3470  }
3471  }
3472 
3473  if(mode_out->colortype == LCT_PALETTE)
3474  {
3475  color_tree_cleanup(&tree);
3476  }
3477 
3478  return 0; /*no error (this function currently never has one, but maybe OOM detection added later.)*/
3479 }
3480 
3481 #ifdef LODEPNG_COMPILE_ENCODER
3482 
3483 void lodepng_color_profile_init(LodePNGColorProfile* profile)
3484 {
3485  profile->colored = 0;
3486  profile->key = 0;
3487  profile->alpha = 0;
3488  profile->key_r = profile->key_g = profile->key_b = 0;
3489  profile->numcolors = 0;
3490  profile->bits = 1;
3491 }
3492 
3493 /*function used for debug purposes with C++*/
3494 /*void printColorProfile(LodePNGColorProfile* p)
3495 {
3496  std::cout << "colored: " << (int)p->colored << ", ";
3497  std::cout << "key: " << (int)p->key << ", ";
3498  std::cout << "key_r: " << (int)p->key_r << ", ";
3499  std::cout << "key_g: " << (int)p->key_g << ", ";
3500  std::cout << "key_b: " << (int)p->key_b << ", ";
3501  std::cout << "alpha: " << (int)p->alpha << ", ";
3502  std::cout << "numcolors: " << (int)p->numcolors << ", ";
3503  std::cout << "bits: " << (int)p->bits << std::endl;
3504 }*/
3505 
3506 /*Returns how many bits needed to represent given value (max 8 bit)*/
3507 static unsigned getValueRequiredBits(unsigned char value)
3508 {
3509  if(value == 0 || value == 255) return 1;
3510  /*The scaling of 2-bit and 4-bit values uses multiples of 85 and 17*/
3511  if(value % 17 == 0) return value % 85 == 0 ? 2 : 4;
3512  return 8;
3513 }
3514 
3515 /*profile must already have been inited with mode.
3516 It's ok to set some parameters of profile to done already.*/
3517 unsigned lodepng_get_color_profile(LodePNGColorProfile* profile,
3518  const unsigned char* in, unsigned w, unsigned h,
3519  const LodePNGColorMode* mode)
3520 {
3521  unsigned error = 0;
3522  size_t i;
3523  ColorTree tree;
3524  size_t numpixels = w * h;
3525 
3526  unsigned colored_done = lodepng_is_greyscale_type(mode) ? 1 : 0;
3527  unsigned alpha_done = lodepng_can_have_alpha(mode) ? 0 : 1;
3528  unsigned numcolors_done = 0;
3529  unsigned bpp = lodepng_get_bpp(mode);
3530  unsigned bits_done = bpp == 1 ? 1 : 0;
3531  unsigned maxnumcolors = 257;
3532  unsigned sixteen = 0;
3533  if(bpp <= 8) maxnumcolors = bpp == 1 ? 2 : (bpp == 2 ? 4 : (bpp == 4 ? 16 : 256));
3534 
3535  color_tree_init(&tree);
3536 
3537  /*Check if the 16-bit input is truly 16-bit*/
3538  if(mode->bitdepth == 16)
3539  {
3540  unsigned short r, g, b, a;
3541  for(i = 0; i != numpixels; ++i)
3542  {
3543  getPixelColorRGBA16(&r, &g, &b, &a, in, i, mode);
3544  if((r & 255) != ((r >> 8) & 255) || (g & 255) != ((g >> 8) & 255) ||
3545  (b & 255) != ((b >> 8) & 255) || (a & 255) != ((a >> 8) & 255)) /*first and second byte differ*/
3546  {
3547  sixteen = 1;
3548  break;
3549  }
3550  }
3551  }
3552 
3553  if(sixteen)
3554  {
3555  unsigned short r = 0, g = 0, b = 0, a = 0;
3556  profile->bits = 16;
3557  bits_done = numcolors_done = 1; /*counting colors no longer useful, palette doesn't support 16-bit*/
3558 
3559  for(i = 0; i != numpixels; ++i)
3560  {
3561  getPixelColorRGBA16(&r, &g, &b, &a, in, i, mode);
3562 
3563  if(!colored_done && (r != g || r != b))
3564  {
3565  profile->colored = 1;
3566  colored_done = 1;
3567  }
3568 
3569  if(!alpha_done)
3570  {
3571  unsigned matchkey = (r == profile->key_r && g == profile->key_g && b == profile->key_b);
3572  if(a != 65535 && (a != 0 || (profile->key && !matchkey)))
3573  {
3574  profile->alpha = 1;
3575  alpha_done = 1;
3576  if(profile->bits < 8) profile->bits = 8; /*PNG has no alphachannel modes with less than 8-bit per channel*/
3577  }
3578  else if(a == 0 && !profile->alpha && !profile->key)
3579  {
3580  profile->key = 1;
3581  profile->key_r = r;
3582  profile->key_g = g;
3583  profile->key_b = b;
3584  }
3585  else if(a == 65535 && profile->key && matchkey)
3586  {
3587  /* Color key cannot be used if an opaque pixel also has that RGB color. */
3588  profile->alpha = 1;
3589  alpha_done = 1;
3590  }
3591  }
3592 
3593  if(alpha_done && numcolors_done && colored_done && bits_done) break;
3594  }
3595  }
3596  else /* < 16-bit */
3597  {
3598  for(i = 0; i != numpixels; ++i)
3599  {
3600  unsigned char r = 0, g = 0, b = 0, a = 0;
3601  getPixelColorRGBA8(&r, &g, &b, &a, in, i, mode);
3602 
3603  if(!bits_done && profile->bits < 8)
3604  {
3605  /*only r is checked, < 8 bits is only relevant for greyscale*/
3606  unsigned bits = getValueRequiredBits(r);
3607  if(bits > profile->bits) profile->bits = bits;
3608  }
3609  bits_done = (profile->bits >= bpp);
3610 
3611  if(!colored_done && (r != g || r != b))
3612  {
3613  profile->colored = 1;
3614  colored_done = 1;
3615  if(profile->bits < 8) profile->bits = 8; /*PNG has no colored modes with less than 8-bit per channel*/
3616  }
3617 
3618  if(!alpha_done)
3619  {
3620  unsigned matchkey = (r == profile->key_r && g == profile->key_g && b == profile->key_b);
3621  if(a != 255 && (a != 0 || (profile->key && !matchkey)))
3622  {
3623  profile->alpha = 1;
3624  alpha_done = 1;
3625  if(profile->bits < 8) profile->bits = 8; /*PNG has no alphachannel modes with less than 8-bit per channel*/
3626  }
3627  else if(a == 0 && !profile->alpha && !profile->key)
3628  {
3629  profile->key = 1;
3630  profile->key_r = r;
3631  profile->key_g = g;
3632  profile->key_b = b;
3633  }
3634  else if(a == 255 && profile->key && matchkey)
3635  {
3636  /* Color key cannot be used if an opaque pixel also has that RGB color. */
3637  profile->alpha = 1;
3638  alpha_done = 1;
3639  if(profile->bits < 8) profile->bits = 8; /*PNG has no alphachannel modes with less than 8-bit per channel*/
3640  }
3641  }
3642 
3643  if(!numcolors_done)
3644  {
3645  if(!color_tree_has(&tree, r, g, b, a))
3646  {
3647  color_tree_add(&tree, r, g, b, a, profile->numcolors);
3648  if(profile->numcolors < 256)
3649  {
3650  unsigned char* p = profile->palette;
3651  unsigned n = profile->numcolors;
3652  p[n * 4 + 0] = r;
3653  p[n * 4 + 1] = g;
3654  p[n * 4 + 2] = b;
3655  p[n * 4 + 3] = a;
3656  }
3657  ++profile->numcolors;
3658  numcolors_done = profile->numcolors >= maxnumcolors;
3659  }
3660  }
3661 
3662  if(alpha_done && numcolors_done && colored_done && bits_done) break;
3663  }
3664 
3665  /*make the profile's key always 16-bit for consistency - repeat each byte twice*/
3666  profile->key_r += (profile->key_r << 8);
3667  profile->key_g += (profile->key_g << 8);
3668  profile->key_b += (profile->key_b << 8);
3669  }
3670 
3671  color_tree_cleanup(&tree);
3672  return error;
3673 }
3674 
3675 /*Automatically chooses color type that gives smallest amount of bits in the
3676 output image, e.g. grey if there are only greyscale pixels, palette if there
3677 are less than 256 colors, ...
3678 Updates values of mode with a potentially smaller color model. mode_out should
3679 contain the user chosen color model, but will be overwritten with the new chosen one.*/
3680 unsigned lodepng_auto_choose_color(LodePNGColorMode* mode_out,
3681  const unsigned char* image, unsigned w, unsigned h,
3682  const LodePNGColorMode* mode_in)
3683 {
3684  LodePNGColorProfile prof;
3685  unsigned error = 0;
3686  unsigned i, n, palettebits, grey_ok, palette_ok;
3687 
3688  lodepng_color_profile_init(&prof);
3689  error = lodepng_get_color_profile(&prof, image, w, h, mode_in);
3690  if(error) return error;
3691  mode_out->key_defined = 0;
3692 
3693  if(prof.key && w * h <= 16)
3694  {
3695  prof.alpha = 1; /*too few pixels to justify tRNS chunk overhead*/
3696  if(prof.bits < 8) prof.bits = 8; /*PNG has no alphachannel modes with less than 8-bit per channel*/
3697  }
3698  grey_ok = !prof.colored && !prof.alpha; /*grey without alpha, with potentially low bits*/
3699  n = prof.numcolors;
3700  palettebits = n <= 2 ? 1 : (n <= 4 ? 2 : (n <= 16 ? 4 : 8));
3701  palette_ok = n <= 256 && (n * 2 < w * h) && prof.bits <= 8;
3702  if(w * h < n * 2) palette_ok = 0; /*don't add palette overhead if image has only a few pixels*/
3703  if(grey_ok && prof.bits <= palettebits) palette_ok = 0; /*grey is less overhead*/
3704 
3705  if(palette_ok)
3706  {
3707  unsigned char* p = prof.palette;
3708  lodepng_palette_clear(mode_out); /*remove potential earlier palette*/
3709  for(i = 0; i != prof.numcolors; ++i)
3710  {
3711  error = lodepng_palette_add(mode_out, p[i * 4 + 0], p[i * 4 + 1], p[i * 4 + 2], p[i * 4 + 3]);
3712  if(error) break;
3713  }
3714 
3715  mode_out->colortype = LCT_PALETTE;
3716  mode_out->bitdepth = palettebits;
3717 
3718  if(mode_in->colortype == LCT_PALETTE && mode_in->palettesize >= mode_out->palettesize
3719  && mode_in->bitdepth == mode_out->bitdepth)
3720  {
3721  /*If input should have same palette colors, keep original to preserve its order and prevent conversion*/
3722  lodepng_color_mode_cleanup(mode_out);
3723  lodepng_color_mode_copy(mode_out, mode_in);
3724  }
3725  }
3726  else /*8-bit or 16-bit per channel*/
3727  {
3728  mode_out->bitdepth = prof.bits;
3729  mode_out->colortype = prof.alpha ? (prof.colored ? LCT_RGBA : LCT_GREY_ALPHA)
3730  : (prof.colored ? LCT_RGB : LCT_GREY);
3731 
3732  if(prof.key && !prof.alpha)
3733  {
3734  unsigned mask = (1u << mode_out->bitdepth) - 1u; /*profile always uses 16-bit, mask converts it*/
3735  mode_out->key_r = prof.key_r & mask;
3736  mode_out->key_g = prof.key_g & mask;
3737  mode_out->key_b = prof.key_b & mask;
3738  mode_out->key_defined = 1;
3739  }
3740  }
3741 
3742  return error;
3743 }
3744 
3745 #endif /* #ifdef LODEPNG_COMPILE_ENCODER */
3746 
3747 /*
3748 Paeth predicter, used by PNG filter type 4
3749 The parameters are of type short, but should come from unsigned chars, the shorts
3750 are only needed to make the paeth calculation correct.
3751 */
3752 static unsigned char paethPredictor(short a, short b, short c)
3753 {
3754  short pa = abs(b - c);
3755  short pb = abs(a - c);
3756  short pc = abs(a + b - c - c);
3757 
3758  if(pc < pa && pc < pb) return (unsigned char)c;
3759  else if(pb < pa) return (unsigned char)b;
3760  else return (unsigned char)a;
3761 }
3762 
3763 /*shared values used by multiple Adam7 related functions*/
3764 
3765 static const unsigned ADAM7_IX[7] = { 0, 4, 0, 2, 0, 1, 0 }; /*x start values*/
3766 static const unsigned ADAM7_IY[7] = { 0, 0, 4, 0, 2, 0, 1 }; /*y start values*/
3767 static const unsigned ADAM7_DX[7] = { 8, 8, 4, 4, 2, 2, 1 }; /*x delta values*/
3768 static const unsigned ADAM7_DY[7] = { 8, 8, 8, 4, 4, 2, 2 }; /*y delta values*/
3769 
3770 /*
3771 Outputs various dimensions and positions in the image related to the Adam7 reduced images.
3772 passw: output containing the width of the 7 passes
3773 passh: output containing the height of the 7 passes
3774 filter_passstart: output containing the index of the start and end of each
3775  reduced image with filter bytes
3776 padded_passstart output containing the index of the start and end of each
3777  reduced image when without filter bytes but with padded scanlines
3778 passstart: output containing the index of the start and end of each reduced
3779  image without padding between scanlines, but still padding between the images
3780 w, h: width and height of non-interlaced image
3781 bpp: bits per pixel
3782 "padded" is only relevant if bpp is less than 8 and a scanline or image does not
3783  end at a full byte
3784 */
3785 static void Adam7_getpassvalues(unsigned passw[7], unsigned passh[7], size_t filter_passstart[8],
3786  size_t padded_passstart[8], size_t passstart[8], unsigned w, unsigned h, unsigned bpp)
3787 {
3788  /*the passstart values have 8 values: the 8th one indicates the byte after the end of the 7th (= last) pass*/
3789  unsigned i;
3790 
3791  /*calculate width and height in pixels of each pass*/
3792  for(i = 0; i != 7; ++i)
3793  {
3794  passw[i] = (w + ADAM7_DX[i] - ADAM7_IX[i] - 1) / ADAM7_DX[i];
3795  passh[i] = (h + ADAM7_DY[i] - ADAM7_IY[i] - 1) / ADAM7_DY[i];
3796  if(passw[i] == 0) passh[i] = 0;
3797  if(passh[i] == 0) passw[i] = 0;
3798  }
3799 
3800  filter_passstart[0] = padded_passstart[0] = passstart[0] = 0;
3801  for(i = 0; i != 7; ++i)
3802  {
3803  /*if passw[i] is 0, it's 0 bytes, not 1 (no filtertype-byte)*/
3804  filter_passstart[i + 1] = filter_passstart[i]
3805  + ((passw[i] && passh[i]) ? passh[i] * (1 + (passw[i] * bpp + 7) / 8) : 0);
3806  /*bits padded if needed to fill full byte at end of each scanline*/
3807  padded_passstart[i + 1] = padded_passstart[i] + passh[i] * ((passw[i] * bpp + 7) / 8);
3808  /*only padded at end of reduced image*/
3809  passstart[i + 1] = passstart[i] + (passh[i] * passw[i] * bpp + 7) / 8;
3810  }
3811 }
3812 
3813 #ifdef LODEPNG_COMPILE_DECODER
3814 
3815 /* ////////////////////////////////////////////////////////////////////////// */
3816 /* / PNG Decoder / */
3817 /* ////////////////////////////////////////////////////////////////////////// */
3818 
3819 /*read the information from the header and store it in the LodePNGInfo. return value is error*/
3820 unsigned lodepng_inspect(unsigned* w, unsigned* h, LodePNGState* state,
3821  const unsigned char* in, size_t insize)
3822 {
3823  LodePNGInfo* info = &state->info_png;
3824  if(insize == 0 || in == 0)
3825  {
3826  CERROR_RETURN_ERROR(state->error, 48); /*error: the given data is empty*/
3827  }
3828  if(insize < 33)
3829  {
3830  CERROR_RETURN_ERROR(state->error, 27); /*error: the data length is smaller than the length of a PNG header*/
3831  }
3832 
3833  /*when decoding a new PNG image, make sure all parameters created after previous decoding are reset*/
3834  lodepng_info_cleanup(info);
3835  lodepng_info_init(info);
3836 
3837  if(in[0] != 137 || in[1] != 80 || in[2] != 78 || in[3] != 71
3838  || in[4] != 13 || in[5] != 10 || in[6] != 26 || in[7] != 10)
3839  {
3840  CERROR_RETURN_ERROR(state->error, 28); /*error: the first 8 bytes are not the correct PNG signature*/
3841  }
3842  if(in[12] != 'I' || in[13] != 'H' || in[14] != 'D' || in[15] != 'R')
3843  {
3844  CERROR_RETURN_ERROR(state->error, 29); /*error: it doesn't start with a IHDR chunk!*/
3845  }
3846 
3847  /*read the values given in the header*/
3848  *w = lodepng_read32bitInt(&in[16]);
3849  *h = lodepng_read32bitInt(&in[20]);
3850  info->color.bitdepth = in[24];
3851  info->color.colortype = (LodePNGColorType)in[25];
3852  info->compression_method = in[26];
3853  info->filter_method = in[27];
3854  info->interlace_method = in[28];
3855 
3856  if(*w == 0 || *h == 0)
3857  {
3858  CERROR_RETURN_ERROR(state->error, 93);
3859  }
3860 
3861  if(!state->decoder.ignore_crc)
3862  {
3863  unsigned CRC = lodepng_read32bitInt(&in[29]);
3864  unsigned checksum = lodepng_crc32(&in[12], 17);
3865  if(CRC != checksum)
3866  {
3867  CERROR_RETURN_ERROR(state->error, 57); /*invalid CRC*/
3868  }
3869  }
3870 
3871  /*error: only compression method 0 is allowed in the specification*/
3872  if(info->compression_method != 0) CERROR_RETURN_ERROR(state->error, 32);
3873  /*error: only filter method 0 is allowed in the specification*/
3874  if(info->filter_method != 0) CERROR_RETURN_ERROR(state->error, 33);
3875  /*error: only interlace methods 0 and 1 exist in the specification*/
3876  if(info->interlace_method > 1) CERROR_RETURN_ERROR(state->error, 34);
3877 
3878  state->error = checkColorValidity(info->color.colortype, info->color.bitdepth);
3879  return state->error;
3880 }
3881 
3882 static unsigned unfilterScanline(unsigned char* recon, const unsigned char* scanline, const unsigned char* precon,
3883  size_t bytewidth, unsigned char filterType, size_t length)
3884 {
3885  /*
3886  For PNG filter method 0
3887  unfilter a PNG image scanline by scanline. when the pixels are smaller than 1 byte,
3888  the filter works byte per byte (bytewidth = 1)
3889  precon is the previous unfiltered scanline, recon the result, scanline the current one
3890  the incoming scanlines do NOT include the filtertype byte, that one is given in the parameter filterType instead
3891  recon and scanline MAY be the same memory address! precon must be disjoint.
3892  */
3893 
3894  size_t i;
3895  switch(filterType)
3896  {
3897  case 0:
3898  for(i = 0; i != length; ++i) recon[i] = scanline[i];
3899  break;
3900  case 1:
3901  for(i = 0; i != bytewidth; ++i) recon[i] = scanline[i];
3902  for(i = bytewidth; i < length; ++i) recon[i] = scanline[i] + recon[i - bytewidth];
3903  break;
3904  case 2:
3905  if(precon)
3906  {
3907  for(i = 0; i != length; ++i) recon[i] = scanline[i] + precon[i];
3908  }
3909  else
3910  {
3911  for(i = 0; i != length; ++i) recon[i] = scanline[i];
3912  }
3913  break;
3914  case 3:
3915  if(precon)
3916  {
3917  for(i = 0; i != bytewidth; ++i) recon[i] = scanline[i] + precon[i] / 2;
3918  for(i = bytewidth; i < length; ++i) recon[i] = scanline[i] + ((recon[i - bytewidth] + precon[i]) / 2);
3919  }
3920  else
3921  {
3922  for(i = 0; i != bytewidth; ++i) recon[i] = scanline[i];
3923  for(i = bytewidth; i < length; ++i) recon[i] = scanline[i] + recon[i - bytewidth] / 2;
3924  }
3925  break;
3926  case 4:
3927  if(precon)
3928  {
3929  for(i = 0; i != bytewidth; ++i)
3930  {
3931  recon[i] = (scanline[i] + precon[i]); /*paethPredictor(0, precon[i], 0) is always precon[i]*/
3932  }
3933  for(i = bytewidth; i < length; ++i)
3934  {
3935  recon[i] = (scanline[i] + paethPredictor(recon[i - bytewidth], precon[i], precon[i - bytewidth]));
3936  }
3937  }
3938  else
3939  {
3940  for(i = 0; i != bytewidth; ++i)
3941  {
3942  recon[i] = scanline[i];
3943  }
3944  for(i = bytewidth; i < length; ++i)
3945  {
3946  /*paethPredictor(recon[i - bytewidth], 0, 0) is always recon[i - bytewidth]*/
3947  recon[i] = (scanline[i] + recon[i - bytewidth]);
3948  }
3949  }
3950  break;
3951  default: return 36; /*error: unexisting filter type given*/
3952  }
3953  return 0;
3954 }
3955 
3956 static unsigned unfilter(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
3957 {
3958  /*
3959  For PNG filter method 0
3960  this function unfilters a single image (e.g. without interlacing this is called once, with Adam7 seven times)
3961  out must have enough bytes allocated already, in must have the scanlines + 1 filtertype byte per scanline
3962  w and h are image dimensions or dimensions of reduced image, bpp is bits per pixel
3963  in and out are allowed to be the same memory address (but aren't the same size since in has the extra filter bytes)
3964  */
3965 
3966  unsigned y;
3967  unsigned char* prevline = 0;
3968 
3969  /*bytewidth is used for filtering, is 1 when bpp < 8, number of bytes per pixel otherwise*/
3970  size_t bytewidth = (bpp + 7) / 8;
3971  size_t linebytes = (w * bpp + 7) / 8;
3972 
3973  for(y = 0; y < h; ++y)
3974  {
3975  size_t outindex = linebytes * y;
3976  size_t inindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
3977  unsigned char filterType = in[inindex];
3978 
3979  CERROR_TRY_RETURN(unfilterScanline(&out[outindex], &in[inindex + 1], prevline, bytewidth, filterType, linebytes));
3980 
3981  prevline = &out[outindex];
3982  }
3983 
3984  return 0;
3985 }
3986 
3987 /*
3988 in: Adam7 interlaced image, with no padding bits between scanlines, but between
3989  reduced images so that each reduced image starts at a byte.
3990 out: the same pixels, but re-ordered so that they're now a non-interlaced image with size w*h
3991 bpp: bits per pixel
3992 out has the following size in bits: w * h * bpp.
3993 in is possibly bigger due to padding bits between reduced images.
3994 out must be big enough AND must be 0 everywhere if bpp < 8 in the current implementation
3995 (because that's likely a little bit faster)
3996 NOTE: comments about padding bits are only relevant if bpp < 8
3997 */
3998 static void Adam7_deinterlace(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
3999 {
4000  unsigned passw[7], passh[7];
4001  size_t filter_passstart[8], padded_passstart[8], passstart[8];
4002  unsigned i;
4003 
4004  Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
4005 
4006  if(bpp >= 8)
4007  {
4008  for(i = 0; i != 7; ++i)
4009  {
4010  unsigned x, y, b;
4011  size_t bytewidth = bpp / 8;
4012  for(y = 0; y < passh[i]; ++y)
4013  for(x = 0; x < passw[i]; ++x)
4014  {
4015  size_t pixelinstart = passstart[i] + (y * passw[i] + x) * bytewidth;
4016  size_t pixeloutstart = ((ADAM7_IY[i] + y * ADAM7_DY[i]) * w + ADAM7_IX[i] + x * ADAM7_DX[i]) * bytewidth;
4017  for(b = 0; b < bytewidth; ++b)
4018  {
4019  out[pixeloutstart + b] = in[pixelinstart + b];
4020  }
4021  }
4022  }
4023  }
4024  else /*bpp < 8: Adam7 with pixels < 8 bit is a bit trickier: with bit pointers*/
4025  {
4026  for(i = 0; i != 7; ++i)
4027  {
4028  unsigned x, y, b;
4029  unsigned ilinebits = bpp * passw[i];
4030  unsigned olinebits = bpp * w;
4031  size_t obp, ibp; /*bit pointers (for out and in buffer)*/
4032  for(y = 0; y < passh[i]; ++y)
4033  for(x = 0; x < passw[i]; ++x)
4034  {
4035  ibp = (8 * passstart[i]) + (y * ilinebits + x * bpp);
4036  obp = (ADAM7_IY[i] + y * ADAM7_DY[i]) * olinebits + (ADAM7_IX[i] + x * ADAM7_DX[i]) * bpp;
4037  for(b = 0; b < bpp; ++b)
4038  {
4039  unsigned char bit = readBitFromReversedStream(&ibp, in);
4040  /*note that this function assumes the out buffer is completely 0, use setBitOfReversedStream otherwise*/
4041  setBitOfReversedStream0(&obp, out, bit);
4042  }
4043  }
4044  }
4045  }
4046 }
4047 
4048 static void removePaddingBits(unsigned char* out, const unsigned char* in,
4049  size_t olinebits, size_t ilinebits, unsigned h)
4050 {
4051  /*
4052  After filtering there are still padding bits if scanlines have non multiple of 8 bit amounts. They need
4053  to be removed (except at last scanline of (Adam7-reduced) image) before working with pure image buffers
4054  for the Adam7 code, the color convert code and the output to the user.
4055  in and out are allowed to be the same buffer, in may also be higher but still overlapping; in must
4056  have >= ilinebits*h bits, out must have >= olinebits*h bits, olinebits must be <= ilinebits
4057  also used to move bits after earlier such operations happened, e.g. in a sequence of reduced images from Adam7
4058  only useful if (ilinebits - olinebits) is a value in the range 1..7
4059  */
4060  unsigned y;
4061  size_t diff = ilinebits - olinebits;
4062  size_t ibp = 0, obp = 0; /*input and output bit pointers*/
4063  for(y = 0; y < h; ++y)
4064  {
4065  size_t x;
4066  for(x = 0; x < olinebits; ++x)
4067  {
4068  unsigned char bit = readBitFromReversedStream(&ibp, in);
4069  setBitOfReversedStream(&obp, out, bit);
4070  }
4071  ibp += diff;
4072  }
4073 }
4074 
4075 /*out must be buffer big enough to contain full image, and in must contain the full decompressed data from
4076 the IDAT chunks (with filter index bytes and possible padding bits)
4077 return value is error*/
4078 static unsigned postProcessScanlines(unsigned char* out, unsigned char* in,
4079  unsigned w, unsigned h, const LodePNGInfo* info_png)
4080 {
4081  /*
4082  This function converts the filtered-padded-interlaced data into pure 2D image buffer with the PNG's colortype.
4083  Steps:
4084  *) if no Adam7: 1) unfilter 2) remove padding bits (= posible extra bits per scanline if bpp < 8)
4085  *) if adam7: 1) 7x unfilter 2) 7x remove padding bits 3) Adam7_deinterlace
4086  NOTE: the in buffer will be overwritten with intermediate data!
4087  */
4088  unsigned bpp = lodepng_get_bpp(&info_png->color);
4089  if(bpp == 0) return 31; /*error: invalid colortype*/
4090 
4091  if(info_png->interlace_method == 0)
4092  {
4093  if(bpp < 8 && w * bpp != ((w * bpp + 7) / 8) * 8)
4094  {
4095  CERROR_TRY_RETURN(unfilter(in, in, w, h, bpp));
4096  removePaddingBits(out, in, w * bpp, ((w * bpp + 7) / 8) * 8, h);
4097  }
4098  /*we can immediatly filter into the out buffer, no other steps needed*/
4099  else CERROR_TRY_RETURN(unfilter(out, in, w, h, bpp));
4100  }
4101  else /*interlace_method is 1 (Adam7)*/
4102  {
4103  unsigned passw[7], passh[7]; size_t filter_passstart[8], padded_passstart[8], passstart[8];
4104  unsigned i;
4105 
4106  Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
4107 
4108  for(i = 0; i != 7; ++i)
4109  {
4110  CERROR_TRY_RETURN(unfilter(&in[padded_passstart[i]], &in[filter_passstart[i]], passw[i], passh[i], bpp));
4111  /*TODO: possible efficiency improvement: if in this reduced image the bits fit nicely in 1 scanline,
4112  move bytes instead of bits or move not at all*/
4113  if(bpp < 8)
4114  {
4115  /*remove padding bits in scanlines; after this there still may be padding
4116  bits between the different reduced images: each reduced image still starts nicely at a byte*/
4117  removePaddingBits(&in[passstart[i]], &in[padded_passstart[i]], passw[i] * bpp,
4118  ((passw[i] * bpp + 7) / 8) * 8, passh[i]);
4119  }
4120  }
4121 
4122  Adam7_deinterlace(out, in, w, h, bpp);
4123  }
4124 
4125  return 0;
4126 }
4127 
4128 static unsigned readChunk_PLTE(LodePNGColorMode* color, const unsigned char* data, size_t chunkLength)
4129 {
4130  unsigned pos = 0, i;
4131  if(color->palette) lodepng_free(color->palette);
4132  color->palettesize = chunkLength / 3;
4133  color->palette = (unsigned char*)lodepng_malloc(4 * color->palettesize);
4134  if(!color->palette && color->palettesize)
4135  {
4136  color->palettesize = 0;
4137  return 83; /*alloc fail*/
4138  }
4139  if(color->palettesize > 256) return 38; /*error: palette too big*/
4140 
4141  for(i = 0; i != color->palettesize; ++i)
4142  {
4143  color->palette[4 * i + 0] = data[pos++]; /*R*/
4144  color->palette[4 * i + 1] = data[pos++]; /*G*/
4145  color->palette[4 * i + 2] = data[pos++]; /*B*/
4146  color->palette[4 * i + 3] = 255; /*alpha*/
4147  }
4148 
4149  return 0; /* OK */
4150 }
4151 
4152 static unsigned readChunk_tRNS(LodePNGColorMode* color, const unsigned char* data, size_t chunkLength)
4153 {
4154  unsigned i;
4155  if(color->colortype == LCT_PALETTE)
4156  {
4157  /*error: more alpha values given than there are palette entries*/
4158  if(chunkLength > color->palettesize) return 38;
4159 
4160  for(i = 0; i != chunkLength; ++i) color->palette[4 * i + 3] = data[i];
4161  }
4162  else if(color->colortype == LCT_GREY)
4163  {
4164  /*error: this chunk must be 2 bytes for greyscale image*/
4165  if(chunkLength != 2) return 30;
4166 
4167  color->key_defined = 1;
4168  color->key_r = color->key_g = color->key_b = 256u * data[0] + data[1];
4169  }
4170  else if(color->colortype == LCT_RGB)
4171  {
4172  /*error: this chunk must be 6 bytes for RGB image*/
4173  if(chunkLength != 6) return 41;
4174 
4175  color->key_defined = 1;
4176  color->key_r = 256u * data[0] + data[1];
4177  color->key_g = 256u * data[2] + data[3];
4178  color->key_b = 256u * data[4] + data[5];
4179  }
4180  else return 42; /*error: tRNS chunk not allowed for other color models*/
4181 
4182  return 0; /* OK */
4183 }
4184 
4185 
4186 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4187 /*background color chunk (bKGD)*/
4188 static unsigned readChunk_bKGD(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
4189 {
4190  if(info->color.colortype == LCT_PALETTE)
4191  {
4192  /*error: this chunk must be 1 byte for indexed color image*/
4193  if(chunkLength != 1) return 43;
4194 
4195  info->background_defined = 1;
4196  info->background_r = info->background_g = info->background_b = data[0];
4197  }
4198  else if(info->color.colortype == LCT_GREY || info->color.colortype == LCT_GREY_ALPHA)
4199  {
4200  /*error: this chunk must be 2 bytes for greyscale image*/
4201  if(chunkLength != 2) return 44;
4202 
4203  info->background_defined = 1;
4204  info->background_r = info->background_g = info->background_b = 256u * data[0] + data[1];
4205  }
4206  else if(info->color.colortype == LCT_RGB || info->color.colortype == LCT_RGBA)
4207  {
4208  /*error: this chunk must be 6 bytes for greyscale image*/
4209  if(chunkLength != 6) return 45;
4210 
4211  info->background_defined = 1;
4212  info->background_r = 256u * data[0] + data[1];
4213  info->background_g = 256u * data[2] + data[3];
4214  info->background_b = 256u * data[4] + data[5];
4215  }
4216 
4217  return 0; /* OK */
4218 }
4219 
4220 /*text chunk (tEXt)*/
4221 static unsigned readChunk_tEXt(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
4222 {
4223  unsigned error = 0;
4224  char *key = 0, *str = 0;
4225  unsigned i;
4226 
4227  while(!error) /*not really a while loop, only used to break on error*/
4228  {
4229  unsigned length, string2_begin;
4230 
4231  length = 0;
4232  while(length < chunkLength && data[length] != 0) ++length;
4233  /*even though it's not allowed by the standard, no error is thrown if
4234  there's no null termination char, if the text is empty*/
4235  if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
4236 
4237  key = (char*)lodepng_malloc(length + 1);
4238  if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
4239 
4240  key[length] = 0;
4241  for(i = 0; i != length; ++i) key[i] = (char)data[i];
4242 
4243  string2_begin = length + 1; /*skip keyword null terminator*/
4244 
4245  length = chunkLength < string2_begin ? 0 : chunkLength - string2_begin;
4246  str = (char*)lodepng_malloc(length + 1);
4247  if(!str) CERROR_BREAK(error, 83); /*alloc fail*/
4248 
4249  str[length] = 0;
4250  for(i = 0; i != length; ++i) str[i] = (char)data[string2_begin + i];
4251 
4252  error = lodepng_add_text(info, key, str);
4253 
4254  break;
4255  }
4256 
4257  lodepng_free(key);
4258  lodepng_free(str);
4259 
4260  return error;
4261 }
4262 
4263 /*compressed text chunk (zTXt)*/
4264 static unsigned readChunk_zTXt(LodePNGInfo* info, const LodePNGDecompressSettings* zlibsettings,
4265  const unsigned char* data, size_t chunkLength)
4266 {
4267  unsigned error = 0;
4268  unsigned i;
4269 
4270  unsigned length, string2_begin;
4271  char *key = 0;
4272  ucvector decoded;
4273 
4274  ucvector_init(&decoded);
4275 
4276  while(!error) /*not really a while loop, only used to break on error*/
4277  {
4278  for(length = 0; length < chunkLength && data[length] != 0; ++length) ;
4279  if(length + 2 >= chunkLength) CERROR_BREAK(error, 75); /*no null termination, corrupt?*/
4280  if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
4281 
4282  key = (char*)lodepng_malloc(length + 1);
4283  if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
4284 
4285  key[length] = 0;
4286  for(i = 0; i != length; ++i) key[i] = (char)data[i];
4287 
4288  if(data[length + 1] != 0) CERROR_BREAK(error, 72); /*the 0 byte indicating compression must be 0*/
4289 
4290  string2_begin = length + 2;
4291  if(string2_begin > chunkLength) CERROR_BREAK(error, 75); /*no null termination, corrupt?*/
4292 
4293  length = chunkLength - string2_begin;
4294  /*will fail if zlib error, e.g. if length is too small*/
4295  error = zlib_decompress(&decoded.data, &decoded.size,
4296  (unsigned char*)(&data[string2_begin]),
4297  length, zlibsettings);
4298  if(error) break;
4299  ucvector_push_back(&decoded, 0);
4300 
4301  error = lodepng_add_text(info, key, (char*)decoded.data);
4302 
4303  break;
4304  }
4305 
4306  lodepng_free(key);
4307  ucvector_cleanup(&decoded);
4308 
4309  return error;
4310 }
4311 
4312 /*international text chunk (iTXt)*/
4313 static unsigned readChunk_iTXt(LodePNGInfo* info, const LodePNGDecompressSettings* zlibsettings,
4314  const unsigned char* data, size_t chunkLength)
4315 {
4316  unsigned error = 0;
4317  unsigned i;
4318 
4319  unsigned length, begin, compressed;
4320  char *key = 0, *langtag = 0, *transkey = 0;
4321  ucvector decoded;
4322  ucvector_init(&decoded);
4323 
4324  while(!error) /*not really a while loop, only used to break on error*/
4325  {
4326  /*Quick check if the chunk length isn't too small. Even without check
4327  it'd still fail with other error checks below if it's too short. This just gives a different error code.*/
4328  if(chunkLength < 5) CERROR_BREAK(error, 30); /*iTXt chunk too short*/
4329 
4330  /*read the key*/
4331  for(length = 0; length < chunkLength && data[length] != 0; ++length) ;
4332  if(length + 3 >= chunkLength) CERROR_BREAK(error, 75); /*no null termination char, corrupt?*/
4333  if(length < 1 || length > 79) CERROR_BREAK(error, 89); /*keyword too short or long*/
4334 
4335  key = (char*)lodepng_malloc(length + 1);
4336  if(!key) CERROR_BREAK(error, 83); /*alloc fail*/
4337 
4338  key[length] = 0;
4339  for(i = 0; i != length; ++i) key[i] = (char)data[i];
4340 
4341  /*read the compression method*/
4342  compressed = data[length + 1];
4343  if(data[length + 2] != 0) CERROR_BREAK(error, 72); /*the 0 byte indicating compression must be 0*/
4344 
4345  /*even though it's not allowed by the standard, no error is thrown if
4346  there's no null termination char, if the text is empty for the next 3 texts*/
4347 
4348  /*read the langtag*/
4349  begin = length + 3;
4350  length = 0;
4351  for(i = begin; i < chunkLength && data[i] != 0; ++i) ++length;
4352 
4353  langtag = (char*)lodepng_malloc(length + 1);
4354  if(!langtag) CERROR_BREAK(error, 83); /*alloc fail*/
4355 
4356  langtag[length] = 0;
4357  for(i = 0; i != length; ++i) langtag[i] = (char)data[begin + i];
4358 
4359  /*read the transkey*/
4360  begin += length + 1;
4361  length = 0;
4362  for(i = begin; i < chunkLength && data[i] != 0; ++i) ++length;
4363 
4364  transkey = (char*)lodepng_malloc(length + 1);
4365  if(!transkey) CERROR_BREAK(error, 83); /*alloc fail*/
4366 
4367  transkey[length] = 0;
4368  for(i = 0; i != length; ++i) transkey[i] = (char)data[begin + i];
4369 
4370  /*read the actual text*/
4371  begin += length + 1;
4372 
4373  length = chunkLength < begin ? 0 : chunkLength - begin;
4374 
4375  if(compressed)
4376  {
4377  /*will fail if zlib error, e.g. if length is too small*/
4378  error = zlib_decompress(&decoded.data, &decoded.size,
4379  (unsigned char*)(&data[begin]),
4380  length, zlibsettings);
4381  if(error) break;
4382  if(decoded.allocsize < decoded.size) decoded.allocsize = decoded.size;
4383  ucvector_push_back(&decoded, 0);
4384  }
4385  else
4386  {
4387  if(!ucvector_resize(&decoded, length + 1)) CERROR_BREAK(error, 83 /*alloc fail*/);
4388 
4389  decoded.data[length] = 0;
4390  for(i = 0; i != length; ++i) decoded.data[i] = data[begin + i];
4391  }
4392 
4393  error = lodepng_add_itext(info, key, langtag, transkey, (char*)decoded.data);
4394 
4395  break;
4396  }
4397 
4398  lodepng_free(key);
4399  lodepng_free(langtag);
4400  lodepng_free(transkey);
4401  ucvector_cleanup(&decoded);
4402 
4403  return error;
4404 }
4405 
4406 static unsigned readChunk_tIME(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
4407 {
4408  if(chunkLength != 7) return 73; /*invalid tIME chunk size*/
4409 
4410  info->time_defined = 1;
4411  info->time.year = 256u * data[0] + data[1];
4412  info->time.month = data[2];
4413  info->time.day = data[3];
4414  info->time.hour = data[4];
4415  info->time.minute = data[5];
4416  info->time.second = data[6];
4417 
4418  return 0; /* OK */
4419 }
4420 
4421 static unsigned readChunk_pHYs(LodePNGInfo* info, const unsigned char* data, size_t chunkLength)
4422 {
4423  if(chunkLength != 9) return 74; /*invalid pHYs chunk size*/
4424 
4425  info->phys_defined = 1;
4426  info->phys_x = 16777216u * data[0] + 65536u * data[1] + 256u * data[2] + data[3];
4427  info->phys_y = 16777216u * data[4] + 65536u * data[5] + 256u * data[6] + data[7];
4428  info->phys_unit = data[8];
4429 
4430  return 0; /* OK */
4431 }
4432 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4433 
4434 /*read a PNG, the result will be in the same color type as the PNG (hence "generic")*/
4435 static void decodeGeneric(unsigned char** out, unsigned* w, unsigned* h,
4436  LodePNGState* state,
4437  const unsigned char* in, size_t insize)
4438 {
4439  unsigned char IEND = 0;
4440  const unsigned char* chunk;
4441  size_t i;
4442  ucvector idat; /*the data from idat chunks*/
4443  ucvector scanlines;
4444  size_t predict;
4445  size_t numpixels;
4446 
4447  /*for unknown chunk order*/
4448  unsigned unknown = 0;
4449 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4450  unsigned critical_pos = 1; /*1 = after IHDR, 2 = after PLTE, 3 = after IDAT*/
4451 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4452 
4453  /*provide some proper output values if error will happen*/
4454  *out = 0;
4455 
4456  state->error = lodepng_inspect(w, h, state, in, insize); /*reads header and resets other parameters in state->info_png*/
4457  if(state->error) return;
4458 
4459  numpixels = *w * *h;
4460 
4461  /*multiplication overflow*/
4462  if(*h != 0 && numpixels / *h != *w) CERROR_RETURN(state->error, 92);
4463  /*multiplication overflow possible further below. Allows up to 2^31-1 pixel
4464  bytes with 16-bit RGBA, the rest is room for filter bytes.*/
4465  if(numpixels > 268435455) CERROR_RETURN(state->error, 92);
4466 
4467  ucvector_init(&idat);
4468  chunk = &in[33]; /*first byte of the first chunk after the header*/
4469 
4470  /*loop through the chunks, ignoring unknown chunks and stopping at IEND chunk.
4471  IDAT data is put at the start of the in buffer*/
4472  while(!IEND && !state->error)
4473  {
4474  unsigned chunkLength;
4475  const unsigned char* data; /*the data in the chunk*/
4476 
4477  /*error: size of the in buffer too small to contain next chunk*/
4478  if((size_t)((chunk - in) + 12) > insize || chunk < in) CERROR_BREAK(state->error, 30);
4479 
4480  /*length of the data of the chunk, excluding the length bytes, chunk type and CRC bytes*/
4481  chunkLength = lodepng_chunk_length(chunk);
4482  /*error: chunk length larger than the max PNG chunk size*/
4483  if(chunkLength > 2147483647) CERROR_BREAK(state->error, 63);
4484 
4485  if((size_t)((chunk - in) + chunkLength + 12) > insize || (chunk + chunkLength + 12) < in)
4486  {
4487  CERROR_BREAK(state->error, 64); /*error: size of the in buffer too small to contain next chunk*/
4488  }
4489 
4490  data = lodepng_chunk_data_const(chunk);
4491 
4492  /*IDAT chunk, containing compressed image data*/
4493  if(lodepng_chunk_type_equals(chunk, "IDAT"))
4494  {
4495  size_t oldsize = idat.size;
4496  if(!ucvector_resize(&idat, oldsize + chunkLength)) CERROR_BREAK(state->error, 83 /*alloc fail*/);
4497  for(i = 0; i != chunkLength; ++i) idat.data[oldsize + i] = data[i];
4498 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4499  critical_pos = 3;
4500 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4501  }
4502  /*IEND chunk*/
4503  else if(lodepng_chunk_type_equals(chunk, "IEND"))
4504  {
4505  IEND = 1;
4506  }
4507  /*palette chunk (PLTE)*/
4508  else if(lodepng_chunk_type_equals(chunk, "PLTE"))
4509  {
4510  state->error = readChunk_PLTE(&state->info_png.color, data, chunkLength);
4511  if(state->error) break;
4512 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4513  critical_pos = 2;
4514 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4515  }
4516  /*palette transparency chunk (tRNS)*/
4517  else if(lodepng_chunk_type_equals(chunk, "tRNS"))
4518  {
4519  state->error = readChunk_tRNS(&state->info_png.color, data, chunkLength);
4520  if(state->error) break;
4521  }
4522 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4523  /*background color chunk (bKGD)*/
4524  else if(lodepng_chunk_type_equals(chunk, "bKGD"))
4525  {
4526  state->error = readChunk_bKGD(&state->info_png, data, chunkLength);
4527  if(state->error) break;
4528  }
4529  /*text chunk (tEXt)*/
4530  else if(lodepng_chunk_type_equals(chunk, "tEXt"))
4531  {
4532  if(state->decoder.read_text_chunks)
4533  {
4534  state->error = readChunk_tEXt(&state->info_png, data, chunkLength);
4535  if(state->error) break;
4536  }
4537  }
4538  /*compressed text chunk (zTXt)*/
4539  else if(lodepng_chunk_type_equals(chunk, "zTXt"))
4540  {
4541  if(state->decoder.read_text_chunks)
4542  {
4543  state->error = readChunk_zTXt(&state->info_png, &state->decoder.zlibsettings, data, chunkLength);
4544  if(state->error) break;
4545  }
4546  }
4547  /*international text chunk (iTXt)*/
4548  else if(lodepng_chunk_type_equals(chunk, "iTXt"))
4549  {
4550  if(state->decoder.read_text_chunks)
4551  {
4552  state->error = readChunk_iTXt(&state->info_png, &state->decoder.zlibsettings, data, chunkLength);
4553  if(state->error) break;
4554  }
4555  }
4556  else if(lodepng_chunk_type_equals(chunk, "tIME"))
4557  {
4558  state->error = readChunk_tIME(&state->info_png, data, chunkLength);
4559  if(state->error) break;
4560  }
4561  else if(lodepng_chunk_type_equals(chunk, "pHYs"))
4562  {
4563  state->error = readChunk_pHYs(&state->info_png, data, chunkLength);
4564  if(state->error) break;
4565  }
4566 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4567  else /*it's not an implemented chunk type, so ignore it: skip over the data*/
4568  {
4569  /*error: unknown critical chunk (5th bit of first byte of chunk type is 0)*/
4570  if(!lodepng_chunk_ancillary(chunk)) CERROR_BREAK(state->error, 69);
4571 
4572  unknown = 1;
4573 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4574  if(state->decoder.remember_unknown_chunks)
4575  {
4576  state->error = lodepng_chunk_append(&state->info_png.unknown_chunks_data[critical_pos - 1],
4577  &state->info_png.unknown_chunks_size[critical_pos - 1], chunk);
4578  if(state->error) break;
4579  }
4580 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4581  }
4582 
4583  if(!state->decoder.ignore_crc && !unknown) /*check CRC if wanted, only on known chunk types*/
4584  {
4585  if(lodepng_chunk_check_crc(chunk)) CERROR_BREAK(state->error, 57); /*invalid CRC*/
4586  }
4587 
4588  if(!IEND) chunk = lodepng_chunk_next_const(chunk);
4589  }
4590 
4591  ucvector_init(&scanlines);
4592  /*predict output size, to allocate exact size for output buffer to avoid more dynamic allocation.
4593  If the decompressed size does not match the prediction, the image must be corrupt.*/
4594  if(state->info_png.interlace_method == 0)
4595  {
4596  /*The extra *h is added because this are the filter bytes every scanline starts with*/
4597  predict = lodepng_get_raw_size_idat(*w, *h, &state->info_png.color) + *h;
4598  }
4599  else
4600  {
4601  /*Adam-7 interlaced: predicted size is the sum of the 7 sub-images sizes*/
4602  const LodePNGColorMode* color = &state->info_png.color;
4603  predict = 0;
4604  predict += lodepng_get_raw_size_idat((*w + 7) / 8, (*h + 7) / 8, color) + (*h + 7) / 8;
4605  if(*w > 4) predict += lodepng_get_raw_size_idat((*w + 3) / 8, (*h + 7) / 8, color) + (*h + 7) / 8;
4606  predict += lodepng_get_raw_size_idat((*w + 3) / 4, (*h + 3) / 8, color) + (*h + 3) / 8;
4607  if(*w > 2) predict += lodepng_get_raw_size_idat((*w + 1) / 4, (*h + 3) / 4, color) + (*h + 3) / 4;
4608  predict += lodepng_get_raw_size_idat((*w + 1) / 2, (*h + 1) / 4, color) + (*h + 1) / 4;
4609  if(*w > 1) predict += lodepng_get_raw_size_idat((*w + 0) / 2, (*h + 1) / 2, color) + (*h + 1) / 2;
4610  predict += lodepng_get_raw_size_idat((*w + 0) / 1, (*h + 0) / 2, color) + (*h + 0) / 2;
4611  }
4612  if(!state->error && !ucvector_reserve(&scanlines, predict)) state->error = 83; /*alloc fail*/
4613  if(!state->error)
4614  {
4615  state->error = zlib_decompress(&scanlines.data, &scanlines.size, idat.data,
4616  idat.size, &state->decoder.zlibsettings);
4617  if(!state->error && scanlines.size != predict) state->error = 91; /*decompressed size doesn't match prediction*/
4618  }
4619  ucvector_cleanup(&idat);
4620 
4621  if(!state->error)
4622  {
4623  size_t outsize = lodepng_get_raw_size(*w, *h, &state->info_png.color);
4624  ucvector outv;
4625  ucvector_init(&outv);
4626  if(!ucvector_resizev(&outv, outsize, 0)) state->error = 83; /*alloc fail*/
4627  if(!state->error) state->error = postProcessScanlines(outv.data, scanlines.data, *w, *h, &state->info_png);
4628  *out = outv.data;
4629  }
4630  ucvector_cleanup(&scanlines);
4631 }
4632 
4633 unsigned lodepng_decode(unsigned char** out, unsigned* w, unsigned* h,
4634  LodePNGState* state,
4635  const unsigned char* in, size_t insize)
4636 {
4637  *out = 0;
4638  decodeGeneric(out, w, h, state, in, insize);
4639  if(state->error) return state->error;
4640  if(!state->decoder.color_convert || lodepng_color_mode_equal(&state->info_raw, &state->info_png.color))
4641  {
4642  /*same color type, no copying or converting of data needed*/
4643  /*store the info_png color settings on the info_raw so that the info_raw still reflects what colortype
4644  the raw image has to the end user*/
4645  if(!state->decoder.color_convert)
4646  {
4647  state->error = lodepng_color_mode_copy(&state->info_raw, &state->info_png.color);
4648  if(state->error) return state->error;
4649  }
4650  }
4651  else
4652  {
4653  /*color conversion needed; sort of copy of the data*/
4654  unsigned char* data = *out;
4655  size_t outsize;
4656 
4657  /*TODO: check if this works according to the statement in the documentation: "The converter can convert
4658  from greyscale input color type, to 8-bit greyscale or greyscale with alpha"*/
4659  if(!(state->info_raw.colortype == LCT_RGB || state->info_raw.colortype == LCT_RGBA)
4660  && !(state->info_raw.bitdepth == 8))
4661  {
4662  return 56; /*unsupported color mode conversion*/
4663  }
4664 
4665  outsize = lodepng_get_raw_size(*w, *h, &state->info_raw);
4666  *out = (unsigned char*)lodepng_malloc(outsize);
4667  if(!(*out))
4668  {
4669  state->error = 83; /*alloc fail*/
4670  }
4671  else state->error = lodepng_convert(*out, data, &state->info_raw,
4672  &state->info_png.color, *w, *h);
4673  lodepng_free(data);
4674  }
4675  return state->error;
4676 }
4677 
4678 unsigned lodepng_decode_memory(unsigned char** out, unsigned* w, unsigned* h, const unsigned char* in,
4679  size_t insize, LodePNGColorType colortype, unsigned bitdepth)
4680 {
4681  unsigned error;
4682  LodePNGState state;
4683  lodepng_state_init(&state);
4684  state.info_raw.colortype = colortype;
4685  state.info_raw.bitdepth = bitdepth;
4686  error = lodepng_decode(out, w, h, &state, in, insize);
4687  lodepng_state_cleanup(&state);
4688  return error;
4689 }
4690 
4691 unsigned lodepng_decode32(unsigned char** out, unsigned* w, unsigned* h, const unsigned char* in, size_t insize)
4692 {
4693  return lodepng_decode_memory(out, w, h, in, insize, LCT_RGBA, 8);
4694 }
4695 
4696 unsigned lodepng_decode24(unsigned char** out, unsigned* w, unsigned* h, const unsigned char* in, size_t insize)
4697 {
4698  return lodepng_decode_memory(out, w, h, in, insize, LCT_RGB, 8);
4699 }
4700 
4701 #ifdef LODEPNG_COMPILE_DISK
4702 unsigned lodepng_decode_file(unsigned char** out, unsigned* w, unsigned* h, const char* filename,
4703  LodePNGColorType colortype, unsigned bitdepth)
4704 {
4705  unsigned char* buffer;
4706  size_t buffersize;
4707  unsigned error;
4708  error = lodepng_load_file(&buffer, &buffersize, filename);
4709  if(!error) error = lodepng_decode_memory(out, w, h, buffer, buffersize, colortype, bitdepth);
4710  lodepng_free(buffer);
4711  return error;
4712 }
4713 
4714 unsigned lodepng_decode32_file(unsigned char** out, unsigned* w, unsigned* h, const char* filename)
4715 {
4716  return lodepng_decode_file(out, w, h, filename, LCT_RGBA, 8);
4717 }
4718 
4719 unsigned lodepng_decode24_file(unsigned char** out, unsigned* w, unsigned* h, const char* filename)
4720 {
4721  return lodepng_decode_file(out, w, h, filename, LCT_RGB, 8);
4722 }
4723 #endif /*LODEPNG_COMPILE_DISK*/
4724 
4725 void lodepng_decoder_settings_init(LodePNGDecoderSettings* settings)
4726 {
4727  settings->color_convert = 1;
4728 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4729  settings->read_text_chunks = 1;
4730  settings->remember_unknown_chunks = 0;
4731 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
4732  settings->ignore_crc = 0;
4733  lodepng_decompress_settings_init(&settings->zlibsettings);
4734 }
4735 
4736 #endif /*LODEPNG_COMPILE_DECODER*/
4737 
4738 #if defined(LODEPNG_COMPILE_DECODER) || defined(LODEPNG_COMPILE_ENCODER)
4739 
4740 void lodepng_state_init(LodePNGState* state)
4741 {
4742 #ifdef LODEPNG_COMPILE_DECODER
4743  lodepng_decoder_settings_init(&state->decoder);
4744 #endif /*LODEPNG_COMPILE_DECODER*/
4745 #ifdef LODEPNG_COMPILE_ENCODER
4746  lodepng_encoder_settings_init(&state->encoder);
4747 #endif /*LODEPNG_COMPILE_ENCODER*/
4748  lodepng_color_mode_init(&state->info_raw);
4749  lodepng_info_init(&state->info_png);
4750  state->error = 1;
4751 }
4752 
4753 void lodepng_state_cleanup(LodePNGState* state)
4754 {
4755  lodepng_color_mode_cleanup(&state->info_raw);
4756  lodepng_info_cleanup(&state->info_png);
4757 }
4758 
4759 void lodepng_state_copy(LodePNGState* dest, const LodePNGState* source)
4760 {
4761  lodepng_state_cleanup(dest);
4762  *dest = *source;
4763  lodepng_color_mode_init(&dest->info_raw);
4764  lodepng_info_init(&dest->info_png);
4765  dest->error = lodepng_color_mode_copy(&dest->info_raw, &source->info_raw); if(dest->error) return;
4766  dest->error = lodepng_info_copy(&dest->info_png, &source->info_png); if(dest->error) return;
4767 }
4768 
4769 #endif /* defined(LODEPNG_COMPILE_DECODER) || defined(LODEPNG_COMPILE_ENCODER) */
4770 
4771 #ifdef LODEPNG_COMPILE_ENCODER
4772 
4773 /* ////////////////////////////////////////////////////////////////////////// */
4774 /* / PNG Encoder / */
4775 /* ////////////////////////////////////////////////////////////////////////// */
4776 
4777 /*chunkName must be string of 4 characters*/
4778 static unsigned addChunk(ucvector* out, const char* chunkName, const unsigned char* data, size_t length)
4779 {
4780  CERROR_TRY_RETURN(lodepng_chunk_create(&out->data, &out->size, (unsigned)length, chunkName, data));
4781  out->allocsize = out->size; /*fix the allocsize again*/
4782  return 0;
4783 }
4784 
4785 static void writeSignature(ucvector* out)
4786 {
4787  /*8 bytes PNG signature, aka the magic bytes*/
4788  ucvector_push_back(out, 137);
4789  ucvector_push_back(out, 80);
4790  ucvector_push_back(out, 78);
4791  ucvector_push_back(out, 71);
4792  ucvector_push_back(out, 13);
4793  ucvector_push_back(out, 10);
4794  ucvector_push_back(out, 26);
4795  ucvector_push_back(out, 10);
4796 }
4797 
4798 static unsigned addChunk_IHDR(ucvector* out, unsigned w, unsigned h,
4799  LodePNGColorType colortype, unsigned bitdepth, unsigned interlace_method)
4800 {
4801  unsigned error = 0;
4802  ucvector header;
4803  ucvector_init(&header);
4804 
4805  lodepng_add32bitInt(&header, w); /*width*/
4806  lodepng_add32bitInt(&header, h); /*height*/
4807  ucvector_push_back(&header, (unsigned char)bitdepth); /*bit depth*/
4808  ucvector_push_back(&header, (unsigned char)colortype); /*color type*/
4809  ucvector_push_back(&header, 0); /*compression method*/
4810  ucvector_push_back(&header, 0); /*filter method*/
4811  ucvector_push_back(&header, interlace_method); /*interlace method*/
4812 
4813  error = addChunk(out, "IHDR", header.data, header.size);
4814  ucvector_cleanup(&header);
4815 
4816  return error;
4817 }
4818 
4819 static unsigned addChunk_PLTE(ucvector* out, const LodePNGColorMode* info)
4820 {
4821  unsigned error = 0;
4822  size_t i;
4823  ucvector PLTE;
4824  ucvector_init(&PLTE);
4825  for(i = 0; i != info->palettesize * 4; ++i)
4826  {
4827  /*add all channels except alpha channel*/
4828  if(i % 4 != 3) ucvector_push_back(&PLTE, info->palette[i]);
4829  }
4830  error = addChunk(out, "PLTE", PLTE.data, PLTE.size);
4831  ucvector_cleanup(&PLTE);
4832 
4833  return error;
4834 }
4835 
4836 static unsigned addChunk_tRNS(ucvector* out, const LodePNGColorMode* info)
4837 {
4838  unsigned error = 0;
4839  size_t i;
4840  ucvector tRNS;
4841  ucvector_init(&tRNS);
4842  if(info->colortype == LCT_PALETTE)
4843  {
4844  size_t amount = info->palettesize;
4845  /*the tail of palette values that all have 255 as alpha, does not have to be encoded*/
4846  for(i = info->palettesize; i != 0; --i)
4847  {
4848  if(info->palette[4 * (i - 1) + 3] == 255) --amount;
4849  else break;
4850  }
4851  /*add only alpha channel*/
4852  for(i = 0; i != amount; ++i) ucvector_push_back(&tRNS, info->palette[4 * i + 3]);
4853  }
4854  else if(info->colortype == LCT_GREY)
4855  {
4856  if(info->key_defined)
4857  {
4858  ucvector_push_back(&tRNS, (unsigned char)(info->key_r / 256));
4859  ucvector_push_back(&tRNS, (unsigned char)(info->key_r % 256));
4860  }
4861  }
4862  else if(info->colortype == LCT_RGB)
4863  {
4864  if(info->key_defined)
4865  {
4866  ucvector_push_back(&tRNS, (unsigned char)(info->key_r / 256));
4867  ucvector_push_back(&tRNS, (unsigned char)(info->key_r % 256));
4868  ucvector_push_back(&tRNS, (unsigned char)(info->key_g / 256));
4869  ucvector_push_back(&tRNS, (unsigned char)(info->key_g % 256));
4870  ucvector_push_back(&tRNS, (unsigned char)(info->key_b / 256));
4871  ucvector_push_back(&tRNS, (unsigned char)(info->key_b % 256));
4872  }
4873  }
4874 
4875  error = addChunk(out, "tRNS", tRNS.data, tRNS.size);
4876  ucvector_cleanup(&tRNS);
4877 
4878  return error;
4879 }
4880 
4881 static unsigned addChunk_IDAT(ucvector* out, const unsigned char* data, size_t datasize,
4882  LodePNGCompressSettings* zlibsettings)
4883 {
4884  ucvector zlibdata;
4885  unsigned error = 0;
4886 
4887  /*compress with the Zlib compressor*/
4888  ucvector_init(&zlibdata);
4889  error = zlib_compress(&zlibdata.data, &zlibdata.size, data, datasize, zlibsettings);
4890  if(!error) error = addChunk(out, "IDAT", zlibdata.data, zlibdata.size);
4891  ucvector_cleanup(&zlibdata);
4892 
4893  return error;
4894 }
4895 
4896 static unsigned addChunk_IEND(ucvector* out)
4897 {
4898  unsigned error = 0;
4899  error = addChunk(out, "IEND", 0, 0);
4900  return error;
4901 }
4902 
4903 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
4904 
4905 static unsigned addChunk_tEXt(ucvector* out, const char* keyword, const char* textstring)
4906 {
4907  unsigned error = 0;
4908  size_t i;
4909  ucvector text;
4910  ucvector_init(&text);
4911  for(i = 0; keyword[i] != 0; ++i) ucvector_push_back(&text, (unsigned char)keyword[i]);
4912  if(i < 1 || i > 79) return 89; /*error: invalid keyword size*/
4913  ucvector_push_back(&text, 0); /*0 termination char*/
4914  for(i = 0; textstring[i] != 0; ++i) ucvector_push_back(&text, (unsigned char)textstring[i]);
4915  error = addChunk(out, "tEXt", text.data, text.size);
4916  ucvector_cleanup(&text);
4917 
4918  return error;
4919 }
4920 
4921 static unsigned addChunk_zTXt(ucvector* out, const char* keyword, const char* textstring,
4922  LodePNGCompressSettings* zlibsettings)
4923 {
4924  unsigned error = 0;
4925  ucvector data, compressed;
4926  size_t i, textsize = strlen(textstring);
4927 
4928  ucvector_init(&data);
4929  ucvector_init(&compressed);
4930  for(i = 0; keyword[i] != 0; ++i) ucvector_push_back(&data, (unsigned char)keyword[i]);
4931  if(i < 1 || i > 79) return 89; /*error: invalid keyword size*/
4932  ucvector_push_back(&data, 0); /*0 termination char*/
4933  ucvector_push_back(&data, 0); /*compression method: 0*/
4934 
4935  error = zlib_compress(&compressed.data, &compressed.size,
4936  (unsigned char*)textstring, textsize, zlibsettings);
4937  if(!error)
4938  {
4939  for(i = 0; i != compressed.size; ++i) ucvector_push_back(&data, compressed.data[i]);
4940  error = addChunk(out, "zTXt", data.data, data.size);
4941  }
4942 
4943  ucvector_cleanup(&compressed);
4944  ucvector_cleanup(&data);
4945  return error;
4946 }
4947 
4948 static unsigned addChunk_iTXt(ucvector* out, unsigned compressed, const char* keyword, const char* langtag,
4949  const char* transkey, const char* textstring, LodePNGCompressSettings* zlibsettings)
4950 {
4951  unsigned error = 0;
4952  ucvector data;
4953  size_t i, textsize = strlen(textstring);
4954 
4955  ucvector_init(&data);
4956 
4957  for(i = 0; keyword[i] != 0; ++i) ucvector_push_back(&data, (unsigned char)keyword[i]);
4958  if(i < 1 || i > 79) return 89; /*error: invalid keyword size*/
4959  ucvector_push_back(&data, 0); /*null termination char*/
4960  ucvector_push_back(&data, compressed ? 1 : 0); /*compression flag*/
4961  ucvector_push_back(&data, 0); /*compression method*/
4962  for(i = 0; langtag[i] != 0; ++i) ucvector_push_back(&data, (unsigned char)langtag[i]);
4963  ucvector_push_back(&data, 0); /*null termination char*/
4964  for(i = 0; transkey[i] != 0; ++i) ucvector_push_back(&data, (unsigned char)transkey[i]);
4965  ucvector_push_back(&data, 0); /*null termination char*/
4966 
4967  if(compressed)
4968  {
4969  ucvector compressed_data;
4970  ucvector_init(&compressed_data);
4971  error = zlib_compress(&compressed_data.data, &compressed_data.size,
4972  (unsigned char*)textstring, textsize, zlibsettings);
4973  if(!error)
4974  {
4975  for(i = 0; i != compressed_data.size; ++i) ucvector_push_back(&data, compressed_data.data[i]);
4976  }
4977  ucvector_cleanup(&compressed_data);
4978  }
4979  else /*not compressed*/
4980  {
4981  for(i = 0; textstring[i] != 0; ++i) ucvector_push_back(&data, (unsigned char)textstring[i]);
4982  }
4983 
4984  if(!error) error = addChunk(out, "iTXt", data.data, data.size);
4985  ucvector_cleanup(&data);
4986  return error;
4987 }
4988 
4989 static unsigned addChunk_bKGD(ucvector* out, const LodePNGInfo* info)
4990 {
4991  unsigned error = 0;
4992  ucvector bKGD;
4993  ucvector_init(&bKGD);
4994  if(info->color.colortype == LCT_GREY || info->color.colortype == LCT_GREY_ALPHA)
4995  {
4996  ucvector_push_back(&bKGD, (unsigned char)(info->background_r / 256));
4997  ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256));
4998  }
4999  else if(info->color.colortype == LCT_RGB || info->color.colortype == LCT_RGBA)
5000  {
5001  ucvector_push_back(&bKGD, (unsigned char)(info->background_r / 256));
5002  ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256));
5003  ucvector_push_back(&bKGD, (unsigned char)(info->background_g / 256));
5004  ucvector_push_back(&bKGD, (unsigned char)(info->background_g % 256));
5005  ucvector_push_back(&bKGD, (unsigned char)(info->background_b / 256));
5006  ucvector_push_back(&bKGD, (unsigned char)(info->background_b % 256));
5007  }
5008  else if(info->color.colortype == LCT_PALETTE)
5009  {
5010  ucvector_push_back(&bKGD, (unsigned char)(info->background_r % 256)); /*palette index*/
5011  }
5012 
5013  error = addChunk(out, "bKGD", bKGD.data, bKGD.size);
5014  ucvector_cleanup(&bKGD);
5015 
5016  return error;
5017 }
5018 
5019 static unsigned addChunk_tIME(ucvector* out, const LodePNGTime* time)
5020 {
5021  unsigned error = 0;
5022  unsigned char* data = (unsigned char*)lodepng_malloc(7);
5023  if(!data) return 83; /*alloc fail*/
5024  data[0] = (unsigned char)(time->year / 256);
5025  data[1] = (unsigned char)(time->year % 256);
5026  data[2] = (unsigned char)time->month;
5027  data[3] = (unsigned char)time->day;
5028  data[4] = (unsigned char)time->hour;
5029  data[5] = (unsigned char)time->minute;
5030  data[6] = (unsigned char)time->second;
5031  error = addChunk(out, "tIME", data, 7);
5032  lodepng_free(data);
5033  return error;
5034 }
5035 
5036 static unsigned addChunk_pHYs(ucvector* out, const LodePNGInfo* info)
5037 {
5038  unsigned error = 0;
5039  ucvector data;
5040  ucvector_init(&data);
5041 
5042  lodepng_add32bitInt(&data, info->phys_x);
5043  lodepng_add32bitInt(&data, info->phys_y);
5044  ucvector_push_back(&data, info->phys_unit);
5045 
5046  error = addChunk(out, "pHYs", data.data, data.size);
5047  ucvector_cleanup(&data);
5048 
5049  return error;
5050 }
5051 
5052 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
5053 
5054 static void filterScanline(unsigned char* out, const unsigned char* scanline, const unsigned char* prevline,
5055  size_t length, size_t bytewidth, unsigned char filterType)
5056 {
5057  size_t i;
5058  switch(filterType)
5059  {
5060  case 0: /*None*/
5061  for(i = 0; i != length; ++i) out[i] = scanline[i];
5062  break;
5063  case 1: /*Sub*/
5064  for(i = 0; i != bytewidth; ++i) out[i] = scanline[i];
5065  for(i = bytewidth; i < length; ++i) out[i] = scanline[i] - scanline[i - bytewidth];
5066  break;
5067  case 2: /*Up*/
5068  if(prevline)
5069  {
5070  for(i = 0; i != length; ++i) out[i] = scanline[i] - prevline[i];
5071  }
5072  else
5073  {
5074  for(i = 0; i != length; ++i) out[i] = scanline[i];
5075  }
5076  break;
5077  case 3: /*Average*/
5078  if(prevline)
5079  {
5080  for(i = 0; i != bytewidth; ++i) out[i] = scanline[i] - prevline[i] / 2;
5081  for(i = bytewidth; i < length; ++i) out[i] = scanline[i] - ((scanline[i - bytewidth] + prevline[i]) / 2);
5082  }
5083  else
5084  {
5085  for(i = 0; i != bytewidth; ++i) out[i] = scanline[i];
5086  for(i = bytewidth; i < length; ++i) out[i] = scanline[i] - scanline[i - bytewidth] / 2;
5087  }
5088  break;
5089  case 4: /*Paeth*/
5090  if(prevline)
5091  {
5092  /*paethPredictor(0, prevline[i], 0) is always prevline[i]*/
5093  for(i = 0; i != bytewidth; ++i) out[i] = (scanline[i] - prevline[i]);
5094  for(i = bytewidth; i < length; ++i)
5095  {
5096  out[i] = (scanline[i] - paethPredictor(scanline[i - bytewidth], prevline[i], prevline[i - bytewidth]));
5097  }
5098  }
5099  else
5100  {
5101  for(i = 0; i != bytewidth; ++i) out[i] = scanline[i];
5102  /*paethPredictor(scanline[i - bytewidth], 0, 0) is always scanline[i - bytewidth]*/
5103  for(i = bytewidth; i < length; ++i) out[i] = (scanline[i] - scanline[i - bytewidth]);
5104  }
5105  break;
5106  default: return; /*unexisting filter type given*/
5107  }
5108 }
5109 
5110 /* log2 approximation. A slight bit faster than std::log. */
5111 static float flog2(float f)
5112 {
5113  float result = 0;
5114  while(f > 32) { result += 4; f /= 16; }
5115  while(f > 2) { ++result; f /= 2; }
5116  return result + 1.442695f * (f * f * f / 3 - 3 * f * f / 2 + 3 * f - 1.83333f);
5117 }
5118 
5119 static unsigned filter(unsigned char* out, const unsigned char* in, unsigned w, unsigned h,
5120  const LodePNGColorMode* info, const LodePNGEncoderSettings* settings)
5121 {
5122  /*
5123  For PNG filter method 0
5124  out must be a buffer with as size: h + (w * h * bpp + 7) / 8, because there are
5125  the scanlines with 1 extra byte per scanline
5126  */
5127 
5128  unsigned bpp = lodepng_get_bpp(info);
5129  /*the width of a scanline in bytes, not including the filter type*/
5130  size_t linebytes = (w * bpp + 7) / 8;
5131  /*bytewidth is used for filtering, is 1 when bpp < 8, number of bytes per pixel otherwise*/
5132  size_t bytewidth = (bpp + 7) / 8;
5133  const unsigned char* prevline = 0;
5134  unsigned x, y;
5135  unsigned error = 0;
5136  LodePNGFilterStrategy strategy = settings->filter_strategy;
5137 
5138  /*
5139  There is a heuristic called the minimum sum of absolute differences heuristic, suggested by the PNG standard:
5140  * If the image type is Palette, or the bit depth is smaller than 8, then do not filter the image (i.e.
5141  use fixed filtering, with the filter None).
5142  * (The other case) If the image type is Grayscale or RGB (with or without Alpha), and the bit depth is
5143  not smaller than 8, then use adaptive filtering heuristic as follows: independently for each row, apply
5144  all five filters and select the filter that produces the smallest sum of absolute values per row.
5145  This heuristic is used if filter strategy is LFS_MINSUM and filter_palette_zero is true.
5146 
5147  If filter_palette_zero is true and filter_strategy is not LFS_MINSUM, the above heuristic is followed,
5148  but for "the other case", whatever strategy filter_strategy is set to instead of the minimum sum
5149  heuristic is used.
5150  */
5151  if(settings->filter_palette_zero &&
5152  (info->colortype == LCT_PALETTE || info->bitdepth < 8)) strategy = LFS_ZERO;
5153 
5154  if(bpp == 0) return 31; /*error: invalid color type*/
5155 
5156  if(strategy == LFS_ZERO)
5157  {
5158  for(y = 0; y != h; ++y)
5159  {
5160  size_t outindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
5161  size_t inindex = linebytes * y;
5162  out[outindex] = 0; /*filter type byte*/
5163  filterScanline(&out[outindex + 1], &in[inindex], prevline, linebytes, bytewidth, 0);
5164  prevline = &in[inindex];
5165  }
5166  }
5167  else if(strategy == LFS_MINSUM)
5168  {
5169  /*adaptive filtering*/
5170  size_t sum[5];
5171  ucvector attempt[5]; /*five filtering attempts, one for each filter type*/
5172  size_t smallest = 0;
5173  unsigned char type, bestType = 0;
5174 
5175  for(type = 0; type != 5; ++type)
5176  {
5177  ucvector_init(&attempt[type]);
5178  if(!ucvector_resize(&attempt[type], linebytes)) return 83; /*alloc fail*/
5179  }
5180 
5181  if(!error)
5182  {
5183  for(y = 0; y != h; ++y)
5184  {
5185  /*try the 5 filter types*/
5186  for(type = 0; type != 5; ++type)
5187  {
5188  filterScanline(attempt[type].data, &in[y * linebytes], prevline, linebytes, bytewidth, type);
5189 
5190  /*calculate the sum of the result*/
5191  sum[type] = 0;
5192  if(type == 0)
5193  {
5194  for(x = 0; x != linebytes; ++x) sum[type] += (unsigned char)(attempt[type].data[x]);
5195  }
5196  else
5197  {
5198  for(x = 0; x != linebytes; ++x)
5199  {
5200  /*For differences, each byte should be treated as signed, values above 127 are negative
5201  (converted to signed char). Filtertype 0 isn't a difference though, so use unsigned there.
5202  This means filtertype 0 is almost never chosen, but that is justified.*/
5203  unsigned char s = attempt[type].data[x];
5204  sum[type] += s < 128 ? s : (255U - s);
5205  }
5206  }
5207 
5208  /*check if this is smallest sum (or if type == 0 it's the first case so always store the values)*/
5209  if(type == 0 || sum[type] < smallest)
5210  {
5211  bestType = type;
5212  smallest = sum[type];
5213  }
5214  }
5215 
5216  prevline = &in[y * linebytes];
5217 
5218  /*now fill the out values*/
5219  out[y * (linebytes + 1)] = bestType; /*the first byte of a scanline will be the filter type*/
5220  for(x = 0; x != linebytes; ++x) out[y * (linebytes + 1) + 1 + x] = attempt[bestType].data[x];
5221  }
5222  }
5223 
5224  for(type = 0; type != 5; ++type) ucvector_cleanup(&attempt[type]);
5225  }
5226  else if(strategy == LFS_ENTROPY)
5227  {
5228  float sum[5];
5229  ucvector attempt[5]; /*five filtering attempts, one for each filter type*/
5230  float smallest = 0;
5231  unsigned type, bestType = 0;
5232  unsigned count[256];
5233 
5234  for(type = 0; type != 5; ++type)
5235  {
5236  ucvector_init(&attempt[type]);
5237  if(!ucvector_resize(&attempt[type], linebytes)) return 83; /*alloc fail*/
5238  }
5239 
5240  for(y = 0; y != h; ++y)
5241  {
5242  /*try the 5 filter types*/
5243  for(type = 0; type != 5; ++type)
5244  {
5245  filterScanline(attempt[type].data, &in[y * linebytes], prevline, linebytes, bytewidth, type);
5246  for(x = 0; x != 256; ++x) count[x] = 0;
5247  for(x = 0; x != linebytes; ++x) ++count[attempt[type].data[x]];
5248  ++count[type]; /*the filter type itself is part of the scanline*/
5249  sum[type] = 0;
5250  for(x = 0; x != 256; ++x)
5251  {
5252  float p = count[x] / (float)(linebytes + 1);
5253  sum[type] += count[x] == 0 ? 0 : flog2(1 / p) * p;
5254  }
5255  /*check if this is smallest sum (or if type == 0 it's the first case so always store the values)*/
5256  if(type == 0 || sum[type] < smallest)
5257  {
5258  bestType = type;
5259  smallest = sum[type];
5260  }
5261  }
5262 
5263  prevline = &in[y * linebytes];
5264 
5265  /*now fill the out values*/
5266  out[y * (linebytes + 1)] = bestType; /*the first byte of a scanline will be the filter type*/
5267  for(x = 0; x != linebytes; ++x) out[y * (linebytes + 1) + 1 + x] = attempt[bestType].data[x];
5268  }
5269 
5270  for(type = 0; type != 5; ++type) ucvector_cleanup(&attempt[type]);
5271  }
5272  else if(strategy == LFS_PREDEFINED)
5273  {
5274  for(y = 0; y != h; ++y)
5275  {
5276  size_t outindex = (1 + linebytes) * y; /*the extra filterbyte added to each row*/
5277  size_t inindex = linebytes * y;
5278  unsigned char type = settings->predefined_filters[y];
5279  out[outindex] = type; /*filter type byte*/
5280  filterScanline(&out[outindex + 1], &in[inindex], prevline, linebytes, bytewidth, type);
5281  prevline = &in[inindex];
5282  }
5283  }
5284  else if(strategy == LFS_BRUTE_FORCE)
5285  {
5286  /*brute force filter chooser.
5287  deflate the scanline after every filter attempt to see which one deflates best.
5288  This is very slow and gives only slightly smaller, sometimes even larger, result*/
5289  size_t size[5];
5290  ucvector attempt[5]; /*five filtering attempts, one for each filter type*/
5291  size_t smallest = 0;
5292  unsigned type = 0, bestType = 0;
5293  unsigned char* dummy;
5294  LodePNGCompressSettings zlibsettings = settings->zlibsettings;
5295  /*use fixed tree on the attempts so that the tree is not adapted to the filtertype on purpose,
5296  to simulate the true case where the tree is the same for the whole image. Sometimes it gives
5297  better result with dynamic tree anyway. Using the fixed tree sometimes gives worse, but in rare
5298  cases better compression. It does make this a bit less slow, so it's worth doing this.*/
5299  zlibsettings.btype = 1;
5300  /*a custom encoder likely doesn't read the btype setting and is optimized for complete PNG
5301  images only, so disable it*/
5302  zlibsettings.custom_zlib = 0;
5303  zlibsettings.custom_deflate = 0;
5304  for(type = 0; type != 5; ++type)
5305  {
5306  ucvector_init(&attempt[type]);
5307  ucvector_resize(&attempt[type], linebytes); /*todo: give error if resize failed*/
5308  }
5309  for(y = 0; y != h; ++y) /*try the 5 filter types*/
5310  {
5311  for(type = 0; type != 5; ++type)
5312  {
5313  unsigned testsize = attempt[type].size;
5314  /*if(testsize > 8) testsize /= 8;*/ /*it already works good enough by testing a part of the row*/
5315 
5316  filterScanline(attempt[type].data, &in[y * linebytes], prevline, linebytes, bytewidth, type);
5317  size[type] = 0;
5318  dummy = 0;
5319  zlib_compress(&dummy, &size[type], attempt[type].data, testsize, &zlibsettings);
5320  lodepng_free(dummy);
5321  /*check if this is smallest size (or if type == 0 it's the first case so always store the values)*/
5322  if(type == 0 || size[type] < smallest)
5323  {
5324  bestType = type;
5325  smallest = size[type];
5326  }
5327  }
5328  prevline = &in[y * linebytes];
5329  out[y * (linebytes + 1)] = bestType; /*the first byte of a scanline will be the filter type*/
5330  for(x = 0; x != linebytes; ++x) out[y * (linebytes + 1) + 1 + x] = attempt[bestType].data[x];
5331  }
5332  for(type = 0; type != 5; ++type) ucvector_cleanup(&attempt[type]);
5333  }
5334  else return 88; /* unknown filter strategy */
5335 
5336  return error;
5337 }
5338 
5339 static void addPaddingBits(unsigned char* out, const unsigned char* in,
5340  size_t olinebits, size_t ilinebits, unsigned h)
5341 {
5342  /*The opposite of the removePaddingBits function
5343  olinebits must be >= ilinebits*/
5344  unsigned y;
5345  size_t diff = olinebits - ilinebits;
5346  size_t obp = 0, ibp = 0; /*bit pointers*/
5347  for(y = 0; y != h; ++y)
5348  {
5349  size_t x;
5350  for(x = 0; x < ilinebits; ++x)
5351  {
5352  unsigned char bit = readBitFromReversedStream(&ibp, in);
5353  setBitOfReversedStream(&obp, out, bit);
5354  }
5355  /*obp += diff; --> no, fill in some value in the padding bits too, to avoid
5356  "Use of uninitialised value of size ###" warning from valgrind*/
5357  for(x = 0; x != diff; ++x) setBitOfReversedStream(&obp, out, 0);
5358  }
5359 }
5360 
5361 /*
5362 in: non-interlaced image with size w*h
5363 out: the same pixels, but re-ordered according to PNG's Adam7 interlacing, with
5364  no padding bits between scanlines, but between reduced images so that each
5365  reduced image starts at a byte.
5366 bpp: bits per pixel
5367 there are no padding bits, not between scanlines, not between reduced images
5368 in has the following size in bits: w * h * bpp.
5369 out is possibly bigger due to padding bits between reduced images
5370 NOTE: comments about padding bits are only relevant if bpp < 8
5371 */
5372 static void Adam7_interlace(unsigned char* out, const unsigned char* in, unsigned w, unsigned h, unsigned bpp)
5373 {
5374  unsigned passw[7], passh[7];
5375  size_t filter_passstart[8], padded_passstart[8], passstart[8];
5376  unsigned i;
5377 
5378  Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
5379 
5380  if(bpp >= 8)
5381  {
5382  for(i = 0; i != 7; ++i)
5383  {
5384  unsigned x, y, b;
5385  size_t bytewidth = bpp / 8;
5386  for(y = 0; y < passh[i]; ++y)
5387  for(x = 0; x < passw[i]; ++x)
5388  {
5389  size_t pixelinstart = ((ADAM7_IY[i] + y * ADAM7_DY[i]) * w + ADAM7_IX[i] + x * ADAM7_DX[i]) * bytewidth;
5390  size_t pixeloutstart = passstart[i] + (y * passw[i] + x) * bytewidth;
5391  for(b = 0; b < bytewidth; ++b)
5392  {
5393  out[pixeloutstart + b] = in[pixelinstart + b];
5394  }
5395  }
5396  }
5397  }
5398  else /*bpp < 8: Adam7 with pixels < 8 bit is a bit trickier: with bit pointers*/
5399  {
5400  for(i = 0; i != 7; ++i)
5401  {
5402  unsigned x, y, b;
5403  unsigned ilinebits = bpp * passw[i];
5404  unsigned olinebits = bpp * w;
5405  size_t obp, ibp; /*bit pointers (for out and in buffer)*/
5406  for(y = 0; y < passh[i]; ++y)
5407  for(x = 0; x < passw[i]; ++x)
5408  {
5409  ibp = (ADAM7_IY[i] + y * ADAM7_DY[i]) * olinebits + (ADAM7_IX[i] + x * ADAM7_DX[i]) * bpp;
5410  obp = (8 * passstart[i]) + (y * ilinebits + x * bpp);
5411  for(b = 0; b < bpp; ++b)
5412  {
5413  unsigned char bit = readBitFromReversedStream(&ibp, in);
5414  setBitOfReversedStream(&obp, out, bit);
5415  }
5416  }
5417  }
5418  }
5419 }
5420 
5421 /*out must be buffer big enough to contain uncompressed IDAT chunk data, and in must contain the full image.
5422 return value is error**/
5423 static unsigned preProcessScanlines(unsigned char** out, size_t* outsize, const unsigned char* in,
5424  unsigned w, unsigned h,
5425  const LodePNGInfo* info_png, const LodePNGEncoderSettings* settings)
5426 {
5427  /*
5428  This function converts the pure 2D image with the PNG's colortype, into filtered-padded-interlaced data. Steps:
5429  *) if no Adam7: 1) add padding bits (= posible extra bits per scanline if bpp < 8) 2) filter
5430  *) if adam7: 1) Adam7_interlace 2) 7x add padding bits 3) 7x filter
5431  */
5432  unsigned bpp = lodepng_get_bpp(&info_png->color);
5433  unsigned error = 0;
5434 
5435  if(info_png->interlace_method == 0)
5436  {
5437  *outsize = h + (h * ((w * bpp + 7) / 8)); /*image size plus an extra byte per scanline + possible padding bits*/
5438  *out = (unsigned char*)lodepng_malloc(*outsize);
5439  if(!(*out) && (*outsize)) error = 83; /*alloc fail*/
5440 
5441  if(!error)
5442  {
5443  /*non multiple of 8 bits per scanline, padding bits needed per scanline*/
5444  if(bpp < 8 && w * bpp != ((w * bpp + 7) / 8) * 8)
5445  {
5446  unsigned char* padded = (unsigned char*)lodepng_malloc(h * ((w * bpp + 7) / 8));
5447  if(!padded) error = 83; /*alloc fail*/
5448  if(!error)
5449  {
5450  addPaddingBits(padded, in, ((w * bpp + 7) / 8) * 8, w * bpp, h);
5451  error = filter(*out, padded, w, h, &info_png->color, settings);
5452  }
5453  lodepng_free(padded);
5454  }
5455  else
5456  {
5457  /*we can immediatly filter into the out buffer, no other steps needed*/
5458  error = filter(*out, in, w, h, &info_png->color, settings);
5459  }
5460  }
5461  }
5462  else /*interlace_method is 1 (Adam7)*/
5463  {
5464  unsigned passw[7], passh[7];
5465  size_t filter_passstart[8], padded_passstart[8], passstart[8];
5466  unsigned char* adam7;
5467 
5468  Adam7_getpassvalues(passw, passh, filter_passstart, padded_passstart, passstart, w, h, bpp);
5469 
5470  *outsize = filter_passstart[7]; /*image size plus an extra byte per scanline + possible padding bits*/
5471  *out = (unsigned char*)lodepng_malloc(*outsize);
5472  if(!(*out)) error = 83; /*alloc fail*/
5473 
5474  adam7 = (unsigned char*)lodepng_malloc(passstart[7]);
5475  if(!adam7 && passstart[7]) error = 83; /*alloc fail*/
5476 
5477  if(!error)
5478  {
5479  unsigned i;
5480 
5481  Adam7_interlace(adam7, in, w, h, bpp);
5482  for(i = 0; i != 7; ++i)
5483  {
5484  if(bpp < 8)
5485  {
5486  unsigned char* padded = (unsigned char*)lodepng_malloc(padded_passstart[i + 1] - padded_passstart[i]);
5487  if(!padded) ERROR_BREAK(83); /*alloc fail*/
5488  addPaddingBits(padded, &adam7[passstart[i]],
5489  ((passw[i] * bpp + 7) / 8) * 8, passw[i] * bpp, passh[i]);
5490  error = filter(&(*out)[filter_passstart[i]], padded,
5491  passw[i], passh[i], &info_png->color, settings);
5492  lodepng_free(padded);
5493  }
5494  else
5495  {
5496  error = filter(&(*out)[filter_passstart[i]], &adam7[padded_passstart[i]],
5497  passw[i], passh[i], &info_png->color, settings);
5498  }
5499 
5500  if(error) break;
5501  }
5502  }
5503 
5504  lodepng_free(adam7);
5505  }
5506 
5507  return error;
5508 }
5509 
5510 /*
5511 palette must have 4 * palettesize bytes allocated, and given in format RGBARGBARGBARGBA...
5512 returns 0 if the palette is opaque,
5513 returns 1 if the palette has a single color with alpha 0 ==> color key
5514 returns 2 if the palette is semi-translucent.
5515 */
5516 static unsigned getPaletteTranslucency(const unsigned char* palette, size_t palettesize)
5517 {
5518  size_t i;
5519  unsigned key = 0;
5520  unsigned r = 0, g = 0, b = 0; /*the value of the color with alpha 0, so long as color keying is possible*/
5521  for(i = 0; i != palettesize; ++i)
5522  {
5523  if(!key && palette[4 * i + 3] == 0)
5524  {
5525  r = palette[4 * i + 0]; g = palette[4 * i + 1]; b = palette[4 * i + 2];
5526  key = 1;
5527  i = (size_t)(-1); /*restart from beginning, to detect earlier opaque colors with key's value*/
5528  }
5529  else if(palette[4 * i + 3] != 255) return 2;
5530  /*when key, no opaque RGB may have key's RGB*/
5531  else if(key && r == palette[i * 4 + 0] && g == palette[i * 4 + 1] && b == palette[i * 4 + 2]) return 2;
5532  }
5533  return key;
5534 }
5535 
5536 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
5537 static unsigned addUnknownChunks(ucvector* out, unsigned char* data, size_t datasize)
5538 {
5539  unsigned char* inchunk = data;
5540  while((size_t)(inchunk - data) < datasize)
5541  {
5542  CERROR_TRY_RETURN(lodepng_chunk_append(&out->data, &out->size, inchunk));
5543  out->allocsize = out->size; /*fix the allocsize again*/
5544  inchunk = lodepng_chunk_next(inchunk);
5545  }
5546  return 0;
5547 }
5548 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
5549 
5550 unsigned lodepng_encode(unsigned char** out, size_t* outsize,
5551  const unsigned char* image, unsigned w, unsigned h,
5552  LodePNGState* state)
5553 {
5554  LodePNGInfo info;
5555  ucvector outv;
5556  unsigned char* data = 0; /*uncompressed version of the IDAT chunk data*/
5557  size_t datasize = 0;
5558 
5559  /*provide some proper output values if error will happen*/
5560  *out = 0;
5561  *outsize = 0;
5562  state->error = 0;
5563 
5564  lodepng_info_init(&info);
5565  lodepng_info_copy(&info, &state->info_png);
5566 
5567  if((info.color.colortype == LCT_PALETTE || state->encoder.force_palette)
5568  && (info.color.palettesize == 0 || info.color.palettesize > 256))
5569  {
5570  state->error = 68; /*invalid palette size, it is only allowed to be 1-256*/
5571  return state->error;
5572  }
5573 
5574  if(state->encoder.auto_convert)
5575  {
5576  state->error = lodepng_auto_choose_color(&info.color, image, w, h, &state->info_raw);
5577  }
5578  if(state->error) return state->error;
5579 
5580  if(state->encoder.zlibsettings.btype > 2)
5581  {
5582  CERROR_RETURN_ERROR(state->error, 61); /*error: unexisting btype*/
5583  }
5584  if(state->info_png.interlace_method > 1)
5585  {
5586  CERROR_RETURN_ERROR(state->error, 71); /*error: unexisting interlace mode*/
5587  }
5588 
5589  state->error = checkColorValidity(info.color.colortype, info.color.bitdepth);
5590  if(state->error) return state->error; /*error: unexisting color type given*/
5591  state->error = checkColorValidity(state->info_raw.colortype, state->info_raw.bitdepth);
5592  if(state->error) return state->error; /*error: unexisting color type given*/
5593 
5594  if(!lodepng_color_mode_equal(&state->info_raw, &info.color))
5595  {
5596  unsigned char* converted;
5597  size_t size = (w * h * lodepng_get_bpp(&info.color) + 7) / 8;
5598 
5599  converted = (unsigned char*)lodepng_malloc(size);
5600  if(!converted && size) state->error = 83; /*alloc fail*/
5601  if(!state->error)
5602  {
5603  state->error = lodepng_convert(converted, image, &info.color, &state->info_raw, w, h);
5604  }
5605  if(!state->error) preProcessScanlines(&data, &datasize, converted, w, h, &info, &state->encoder);
5606  lodepng_free(converted);
5607  }
5608  else preProcessScanlines(&data, &datasize, image, w, h, &info, &state->encoder);
5609 
5610  ucvector_init(&outv);
5611  while(!state->error) /*while only executed once, to break on error*/
5612  {
5613 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
5614  size_t i;
5615 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
5616  /*write signature and chunks*/
5617  writeSignature(&outv);
5618  /*IHDR*/
5619  addChunk_IHDR(&outv, w, h, info.color.colortype, info.color.bitdepth, info.interlace_method);
5620 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
5621  /*unknown chunks between IHDR and PLTE*/
5622  if(info.unknown_chunks_data[0])
5623  {
5624  state->error = addUnknownChunks(&outv, info.unknown_chunks_data[0], info.unknown_chunks_size[0]);
5625  if(state->error) break;
5626  }
5627 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
5628  /*PLTE*/
5629  if(info.color.colortype == LCT_PALETTE)
5630  {
5631  addChunk_PLTE(&outv, &info.color);
5632  }
5633  if(state->encoder.force_palette && (info.color.colortype == LCT_RGB || info.color.colortype == LCT_RGBA))
5634  {
5635  addChunk_PLTE(&outv, &info.color);
5636  }
5637  /*tRNS*/
5638  if(info.color.colortype == LCT_PALETTE && getPaletteTranslucency(info.color.palette, info.color.palettesize) != 0)
5639  {
5640  addChunk_tRNS(&outv, &info.color);
5641  }
5642  if((info.color.colortype == LCT_GREY || info.color.colortype == LCT_RGB) && info.color.key_defined)
5643  {
5644  addChunk_tRNS(&outv, &info.color);
5645  }
5646 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
5647  /*bKGD (must come between PLTE and the IDAt chunks*/
5648  if(info.background_defined) addChunk_bKGD(&outv, &info);
5649  /*pHYs (must come before the IDAT chunks)*/
5650  if(info.phys_defined) addChunk_pHYs(&outv, &info);
5651 
5652  /*unknown chunks between PLTE and IDAT*/
5653  if(info.unknown_chunks_data[1])
5654  {
5655  state->error = addUnknownChunks(&outv, info.unknown_chunks_data[1], info.unknown_chunks_size[1]);
5656  if(state->error) break;
5657  }
5658 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
5659  /*IDAT (multiple IDAT chunks must be consecutive)*/
5660  state->error = addChunk_IDAT(&outv, data, datasize, &state->encoder.zlibsettings);
5661  if(state->error) break;
5662 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
5663  /*tIME*/
5664  if(info.time_defined) addChunk_tIME(&outv, &info.time);
5665  /*tEXt and/or zTXt*/
5666  for(i = 0; i != info.text_num; ++i)
5667  {
5668  if(strlen(info.text_keys[i]) > 79)
5669  {
5670  state->error = 66; /*text chunk too large*/
5671  break;
5672  }
5673  if(strlen(info.text_keys[i]) < 1)
5674  {
5675  state->error = 67; /*text chunk too small*/
5676  break;
5677  }
5678  if(state->encoder.text_compression)
5679  {
5680  addChunk_zTXt(&outv, info.text_keys[i], info.text_strings[i], &state->encoder.zlibsettings);
5681  }
5682  else
5683  {
5684  addChunk_tEXt(&outv, info.text_keys[i], info.text_strings[i]);
5685  }
5686  }
5687  /*LodePNG version id in text chunk*/
5688  if(state->encoder.add_id)
5689  {
5690  unsigned alread_added_id_text = 0;
5691  for(i = 0; i != info.text_num; ++i)
5692  {
5693  if(!strcmp(info.text_keys[i], "LodePNG"))
5694  {
5695  alread_added_id_text = 1;
5696  break;
5697  }
5698  }
5699  if(alread_added_id_text == 0)
5700  {
5701  addChunk_tEXt(&outv, "LodePNG", LODEPNG_VERSION_STRING); /*it's shorter as tEXt than as zTXt chunk*/
5702  }
5703  }
5704  /*iTXt*/
5705  for(i = 0; i != info.itext_num; ++i)
5706  {
5707  if(strlen(info.itext_keys[i]) > 79)
5708  {
5709  state->error = 66; /*text chunk too large*/
5710  break;
5711  }
5712  if(strlen(info.itext_keys[i]) < 1)
5713  {
5714  state->error = 67; /*text chunk too small*/
5715  break;
5716  }
5717  addChunk_iTXt(&outv, state->encoder.text_compression,
5718  info.itext_keys[i], info.itext_langtags[i], info.itext_transkeys[i], info.itext_strings[i],
5719  &state->encoder.zlibsettings);
5720  }
5721 
5722  /*unknown chunks between IDAT and IEND*/
5723  if(info.unknown_chunks_data[2])
5724  {
5725  state->error = addUnknownChunks(&outv, info.unknown_chunks_data[2], info.unknown_chunks_size[2]);
5726  if(state->error) break;
5727  }
5728 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
5729  addChunk_IEND(&outv);
5730 
5731  break; /*this isn't really a while loop; no error happened so break out now!*/
5732  }
5733 
5734  lodepng_info_cleanup(&info);
5735  lodepng_free(data);
5736  /*instead of cleaning the vector up, give it to the output*/
5737  *out = outv.data;
5738  *outsize = outv.size;
5739 
5740  return state->error;
5741 }
5742 
5743 unsigned lodepng_encode_memory(unsigned char** out, size_t* outsize, const unsigned char* image,
5744  unsigned w, unsigned h, LodePNGColorType colortype, unsigned bitdepth)
5745 {
5746  unsigned error;
5747  LodePNGState state;
5748  lodepng_state_init(&state);
5749  state.info_raw.colortype = colortype;
5750  state.info_raw.bitdepth = bitdepth;
5751  state.info_png.color.colortype = colortype;
5752  state.info_png.color.bitdepth = bitdepth;
5753  lodepng_encode(out, outsize, image, w, h, &state);
5754  error = state.error;
5755  lodepng_state_cleanup(&state);
5756  return error;
5757 }
5758 
5759 unsigned lodepng_encode32(unsigned char** out, size_t* outsize, const unsigned char* image, unsigned w, unsigned h)
5760 {
5761  return lodepng_encode_memory(out, outsize, image, w, h, LCT_RGBA, 8);
5762 }
5763 
5764 unsigned lodepng_encode24(unsigned char** out, size_t* outsize, const unsigned char* image, unsigned w, unsigned h)
5765 {
5766  return lodepng_encode_memory(out, outsize, image, w, h, LCT_RGB, 8);
5767 }
5768 
5769 #ifdef LODEPNG_COMPILE_DISK
5770 unsigned lodepng_encode_file(const char* filename, const unsigned char* image, unsigned w, unsigned h,
5771  LodePNGColorType colortype, unsigned bitdepth)
5772 {
5773  unsigned char* buffer;
5774  size_t buffersize;
5775  unsigned error = lodepng_encode_memory(&buffer, &buffersize, image, w, h, colortype, bitdepth);
5776  if(!error) error = lodepng_save_file(buffer, buffersize, filename);
5777  lodepng_free(buffer);
5778  return error;
5779 }
5780 
5781 unsigned lodepng_encode32_file(const char* filename, const unsigned char* image, unsigned w, unsigned h)
5782 {
5783  return lodepng_encode_file(filename, image, w, h, LCT_RGBA, 8);
5784 }
5785 
5786 unsigned lodepng_encode24_file(const char* filename, const unsigned char* image, unsigned w, unsigned h)
5787 {
5788  return lodepng_encode_file(filename, image, w, h, LCT_RGB, 8);
5789 }
5790 #endif /*LODEPNG_COMPILE_DISK*/
5791 
5792 void lodepng_encoder_settings_init(LodePNGEncoderSettings* settings)
5793 {
5794  lodepng_compress_settings_init(&settings->zlibsettings);
5795  settings->filter_palette_zero = 1;
5796  settings->filter_strategy = LFS_MINSUM;
5797  settings->auto_convert = 1;
5798  settings->force_palette = 0;
5799  settings->predefined_filters = 0;
5800 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
5801  settings->add_id = 0;
5802  settings->text_compression = 1;
5803 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
5804 }
5805 
5806 #endif /*LODEPNG_COMPILE_ENCODER*/
5807 #endif /*LODEPNG_COMPILE_PNG*/
5808 
5809 #ifdef LODEPNG_COMPILE_ERROR_TEXT
5810 /*
5811 This returns the description of a numerical error code in English. This is also
5812 the documentation of all the error codes.
5813 */
5814 const char* lodepng_error_text(unsigned code)
5815 {
5816  switch(code)
5817  {
5818  case 0: return "no error, everything went ok";
5819  case 1: return "nothing done yet"; /*the Encoder/Decoder has done nothing yet, error checking makes no sense yet*/
5820  case 10: return "end of input memory reached without huffman end code"; /*while huffman decoding*/
5821  case 11: return "error in code tree made it jump outside of huffman tree"; /*while huffman decoding*/
5822  case 13: return "problem while processing dynamic deflate block";
5823  case 14: return "problem while processing dynamic deflate block";
5824  case 15: return "problem while processing dynamic deflate block";
5825  case 16: return "unexisting code while processing dynamic deflate block";
5826  case 17: return "end of out buffer memory reached while inflating";
5827  case 18: return "invalid distance code while inflating";
5828  case 19: return "end of out buffer memory reached while inflating";
5829  case 20: return "invalid deflate block BTYPE encountered while decoding";
5830  case 21: return "NLEN is not ones complement of LEN in a deflate block";
5831  /*end of out buffer memory reached while inflating:
5832  This can happen if the inflated deflate data is longer than the amount of bytes required to fill up
5833  all the pixels of the image, given the color depth and image dimensions. Something that doesn't
5834  happen in a normal, well encoded, PNG image.*/
5835  case 22: return "end of out buffer memory reached while inflating";
5836  case 23: return "end of in buffer memory reached while inflating";
5837  case 24: return "invalid FCHECK in zlib header";
5838  case 25: return "invalid compression method in zlib header";
5839  case 26: return "FDICT encountered in zlib header while it's not used for PNG";
5840  case 27: return "PNG file is smaller than a PNG header";
5841  /*Checks the magic file header, the first 8 bytes of the PNG file*/
5842  case 28: return "incorrect PNG signature, it's no PNG or corrupted";
5843  case 29: return "first chunk is not the header chunk";
5844  case 30: return "chunk length too large, chunk broken off at end of file";
5845  case 31: return "illegal PNG color type or bpp";
5846  case 32: return "illegal PNG compression method";
5847  case 33: return "illegal PNG filter method";
5848  case 34: return "illegal PNG interlace method";
5849  case 35: return "chunk length of a chunk is too large or the chunk too small";
5850  case 36: return "illegal PNG filter type encountered";
5851  case 37: return "illegal bit depth for this color type given";
5852  case 38: return "the palette is too big"; /*more than 256 colors*/
5853  case 39: return "more palette alpha values given in tRNS chunk than there are colors in the palette";
5854  case 40: return "tRNS chunk has wrong size for greyscale image";
5855  case 41: return "tRNS chunk has wrong size for RGB image";
5856  case 42: return "tRNS chunk appeared while it was not allowed for this color type";
5857  case 43: return "bKGD chunk has wrong size for palette image";
5858  case 44: return "bKGD chunk has wrong size for greyscale image";
5859  case 45: return "bKGD chunk has wrong size for RGB image";
5860  /*the input data is empty, maybe a PNG file doesn't exist or is in the wrong path*/
5861  case 48: return "empty input or file doesn't exist";
5862  case 49: return "jumped past memory while generating dynamic huffman tree";
5863  case 50: return "jumped past memory while generating dynamic huffman tree";
5864  case 51: return "jumped past memory while inflating huffman block";
5865  case 52: return "jumped past memory while inflating";
5866  case 53: return "size of zlib data too small";
5867  case 54: return "repeat symbol in tree while there was no value symbol yet";
5868  /*jumped past tree while generating huffman tree, this could be when the
5869  tree will have more leaves than symbols after generating it out of the
5870  given lenghts. They call this an oversubscribed dynamic bit lengths tree in zlib.*/
5871  case 55: return "jumped past tree while generating huffman tree";
5872  case 56: return "given output image colortype or bitdepth not supported for color conversion";
5873  case 57: return "invalid CRC encountered (checking CRC can be disabled)";
5874  case 58: return "invalid ADLER32 encountered (checking ADLER32 can be disabled)";
5875  case 59: return "requested color conversion not supported";
5876  case 60: return "invalid window size given in the settings of the encoder (must be 0-32768)";
5877  case 61: return "invalid BTYPE given in the settings of the encoder (only 0, 1 and 2 are allowed)";
5878  /*LodePNG leaves the choice of RGB to greyscale conversion formula to the user.*/
5879  case 62: return "conversion from color to greyscale not supported";
5880  case 63: return "length of a chunk too long, max allowed for PNG is 2147483647 bytes per chunk"; /*(2^31-1)*/
5881  /*this would result in the inability of a deflated block to ever contain an end code. It must be at least 1.*/
5882  case 64: return "the length of the END symbol 256 in the Huffman tree is 0";
5883  case 66: return "the length of a text chunk keyword given to the encoder is longer than the maximum of 79 bytes";
5884  case 67: return "the length of a text chunk keyword given to the encoder is smaller than the minimum of 1 byte";
5885  case 68: return "tried to encode a PLTE chunk with a palette that has less than 1 or more than 256 colors";
5886  case 69: return "unknown chunk type with 'critical' flag encountered by the decoder";
5887  case 71: return "unexisting interlace mode given to encoder (must be 0 or 1)";
5888  case 72: return "while decoding, unexisting compression method encountering in zTXt or iTXt chunk (it must be 0)";
5889  case 73: return "invalid tIME chunk size";
5890  case 74: return "invalid pHYs chunk size";
5891  /*length could be wrong, or data chopped off*/
5892  case 75: return "no null termination char found while decoding text chunk";
5893  case 76: return "iTXt chunk too short to contain required bytes";
5894  case 77: return "integer overflow in buffer size";
5895  case 78: return "failed to open file for reading"; /*file doesn't exist or couldn't be opened for reading*/
5896  case 79: return "failed to open file for writing";
5897  case 80: return "tried creating a tree of 0 symbols";
5898  case 81: return "lazy matching at pos 0 is impossible";
5899  case 82: return "color conversion to palette requested while a color isn't in palette";
5900  case 83: return "memory allocation failed";
5901  case 84: return "given image too small to contain all pixels to be encoded";
5902  case 86: return "impossible offset in lz77 encoding (internal bug)";
5903  case 87: return "must provide custom zlib function pointer if LODEPNG_COMPILE_ZLIB is not defined";
5904  case 88: return "invalid filter strategy given for LodePNGEncoderSettings.filter_strategy";
5905  case 89: return "text chunk keyword too short or long: must have size 1-79";
5906  /*the windowsize in the LodePNGCompressSettings. Requiring POT(==> & instead of %) makes encoding 12% faster.*/
5907  case 90: return "windowsize must be a power of two";
5908  case 91: return "invalid decompressed idat size";
5909  case 92: return "too many pixels, not supported";
5910  case 93: return "zero width or height is invalid";
5911  }
5912  return "unknown error code";
5913 }
5914 #endif /*LODEPNG_COMPILE_ERROR_TEXT*/
5915 
5916 
5917 #endif
index
int index
Definition: vera.c:66
lodepng.h
text
const char * text
Definition: basic_text.c:391
pc
Uint16 pc
Definition: z8k1.c:127
m65-memcontent-generator.data
data
Definition: m65-memcontent-generator.py:119
palette
Uint32 * palette
Definition: vic4_palette.c:33
x
int x
Definition: console.c:27
mode
int mode
Definition: vera.c:61
compress_sd_image.r
def r
Definition: compress_sd_image.py:76
memory
Uint8 memory[0x100000]
Definition: commodore_65.c:43
size
int size
Definition: inject.c:37
L
#define L
Definition: macros.h:30
checksum
Uint8 checksum[0x10]
Definition: cpmfs.c:52
y
int y
Definition: console.c:27
mask
int mask
Definition: dma65.c:83
value
int value
Definition: dma65.c:90
scanline
int scanline
Definition: vic6561.c:52
buf
Uint8 buf[512]
Definition: fat32.c:155