Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/src/lodepng.cpp

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

Archive Download this file

Revision: 1322