-
Notifications
You must be signed in to change notification settings - Fork 426
/
lodepng.cpp
7009 lines (6167 loc) · 296 KB
/
lodepng.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
LodePNG version 20241015
Copyright (c) 2005-2024 Lode Vandevenne
This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
3. This notice may not be removed or altered from any source
distribution.
*/
/*
The manual and changelog are in the header file "lodepng.h"
Rename this file to lodepng.cpp to use it for C++, or to lodepng.c to use it for C.
*/
#include "lodepng.h"
#ifdef LODEPNG_COMPILE_DISK
#include <limits.h> /* LONG_MAX */
#include <stdio.h> /* file handling */
#endif /* LODEPNG_COMPILE_DISK */
#ifdef LODEPNG_COMPILE_ALLOCATORS
#include <stdlib.h> /* allocations */
#endif /* LODEPNG_COMPILE_ALLOCATORS */
#if defined(_MSC_VER) && (_MSC_VER >= 1310) /*Visual Studio: A few warning types are not desired here.*/
#pragma warning( disable : 4244 ) /*implicit conversions: not warned by gcc -Wall -Wextra and requires too much casts*/
#pragma warning( disable : 4996 ) /*VS does not like fopen, but fopen_s is not standard C so unusable here*/
#endif /*_MSC_VER */
const char* LODEPNG_VERSION_STRING = "20241015";
/*
This source file is divided into the following large parts. The code sections
with the "LODEPNG_COMPILE_" #defines divide this up further in an intermixed way.
-Tools for C and common code for PNG and Zlib
-C Code for Zlib (huffman, deflate, ...)
-C Code for PNG (file format chunks, adam7, PNG filters, color conversions, ...)
-The C++ wrapper around all of the above
*/
/* ////////////////////////////////////////////////////////////////////////// */
/* ////////////////////////////////////////////////////////////////////////// */
/* // Tools for C, and common code for PNG and Zlib. // */
/* ////////////////////////////////////////////////////////////////////////// */
/* ////////////////////////////////////////////////////////////////////////// */
/*The malloc, realloc and free functions defined here with "lodepng_" in front
of the name, so that you can easily change them to others related to your
platform if needed. Everything else in the code calls these. Pass
-DLODEPNG_NO_COMPILE_ALLOCATORS to the compiler, or comment out
#define LODEPNG_COMPILE_ALLOCATORS in the header, to disable the ones here and
define them in your own project's source files without needing to change
lodepng source code. Don't forget to remove "static" if you copypaste them
from here.*/
#ifdef LODEPNG_COMPILE_ALLOCATORS
static void* lodepng_malloc(size_t size) {
#ifdef LODEPNG_MAX_ALLOC
if(size > LODEPNG_MAX_ALLOC) return 0;
#endif
return malloc(size);
}
/* NOTE: when realloc returns NULL, it leaves the original memory untouched */
static void* lodepng_realloc(void* ptr, size_t new_size) {
#ifdef LODEPNG_MAX_ALLOC
if(new_size > LODEPNG_MAX_ALLOC) return 0;
#endif
return realloc(ptr, new_size);
}
static void lodepng_free(void* ptr) {
free(ptr);
}
#else /*LODEPNG_COMPILE_ALLOCATORS*/
/* TODO: support giving additional void* payload to the custom allocators */
void* lodepng_malloc(size_t size);
void* lodepng_realloc(void* ptr, size_t new_size);
void lodepng_free(void* ptr);
#endif /*LODEPNG_COMPILE_ALLOCATORS*/
/* convince the compiler to inline a function, for use when this measurably improves performance */
/* inline is not available in C90, but use it when supported by the compiler */
#if (defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined(__cplusplus) && (__cplusplus >= 199711L))
#define LODEPNG_INLINE inline
#else
#define LODEPNG_INLINE /* not available */
#endif
/* restrict is not available in C90, but use it when supported by the compiler */
#if (defined(__GNUC__) && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 1))) ||\
(defined(_MSC_VER) && (_MSC_VER >= 1400)) || \
(defined(__WATCOMC__) && (__WATCOMC__ >= 1250) && !defined(__cplusplus))
#define LODEPNG_RESTRICT __restrict
#else
#define LODEPNG_RESTRICT /* not available */
#endif
/* Replacements for C library functions such as memcpy and strlen, to support platforms
where a full C library is not available. The compiler can recognize them and compile
to something as fast. */
static void lodepng_memcpy(void* LODEPNG_RESTRICT dst,
const void* LODEPNG_RESTRICT src, size_t size) {
size_t i;
for(i = 0; i < size; i++) ((char*)dst)[i] = ((const char*)src)[i];
}
static void lodepng_memset(void* LODEPNG_RESTRICT dst,
int value, size_t num) {
size_t i;
for(i = 0; i < num; i++) ((char*)dst)[i] = (char)value;
}
/* does not check memory out of bounds, do not use on untrusted data */
static size_t lodepng_strlen(const char* a) {
const char* orig = a;
/* avoid warning about unused function in case of disabled COMPILE... macros */
(void)(&lodepng_strlen);
while(*a) a++;
return (size_t)(a - orig);
}
#define LODEPNG_MAX(a, b) (((a) > (b)) ? (a) : (b))
#define LODEPNG_MIN(a, b) (((a) < (b)) ? (a) : (b))
#if defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_DECODER)
/* Safely check if adding two integers will overflow (no undefined
behavior, compiler removing the code, etc...) and output result. */
static int lodepng_addofl(size_t a, size_t b, size_t* result) {
*result = a + b; /* Unsigned addition is well defined and safe in C90 */
return *result < a;
}
#endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_DECODER)*/
#ifdef LODEPNG_COMPILE_DECODER
/* Safely check if multiplying two integers will overflow (no undefined
behavior, compiler removing the code, etc...) and output result. */
static int lodepng_mulofl(size_t a, size_t b, size_t* result) {
*result = a * b; /* Unsigned multiplication is well defined and safe in C90 */
return (a != 0 && *result / a != b);
}
#ifdef LODEPNG_COMPILE_ZLIB
/* Safely check if a + b > c, even if overflow could happen. */
static int lodepng_gtofl(size_t a, size_t b, size_t c) {
size_t d;
if(lodepng_addofl(a, b, &d)) return 1;
return d > c;
}
#endif /*LODEPNG_COMPILE_ZLIB*/
#endif /*LODEPNG_COMPILE_DECODER*/
/*
Often in case of an error a value is assigned to a variable and then it breaks
out of a loop (to go to the cleanup phase of a function). This macro does that.
It makes the error handling code shorter and more readable.
Example: if(!uivector_resize(&lz77_encoded, datasize)) ERROR_BREAK(83);
*/
#define CERROR_BREAK(errorvar, code){\
errorvar = code;\
break;\
}
/*version of CERROR_BREAK that assumes the common case where the error variable is named "error"*/
#define ERROR_BREAK(code) CERROR_BREAK(error, code)
/*Set error var to the error code, and return it.*/
#define CERROR_RETURN_ERROR(errorvar, code){\
errorvar = code;\
return code;\
}
/*Try the code, if it returns error, also return the error.*/
#define CERROR_TRY_RETURN(call){\
unsigned error = call;\
if(error) return error;\
}
/*Set error var to the error code, and return from the void function.*/
#define CERROR_RETURN(errorvar, code){\
errorvar = code;\
return;\
}
/*
About uivector, ucvector and string:
-All of them wrap dynamic arrays or text strings in a similar way.
-LodePNG was originally written in C++. The vectors replace the std::vectors that were used in the C++ version.
-The string tools are made to avoid problems with compilers that declare things like strncat as deprecated.
-They're not used in the interface, only internally in this file as static functions.
-As with many other structs in this file, the init and cleanup functions serve as ctor and dtor.
*/
#ifdef LODEPNG_COMPILE_ZLIB
#ifdef LODEPNG_COMPILE_ENCODER
/*dynamic vector of unsigned ints*/
typedef struct uivector {
unsigned* data;
size_t size; /*size in number of unsigned longs*/
size_t allocsize; /*allocated size in bytes*/
} uivector;
static void uivector_cleanup(void* p) {
((uivector*)p)->size = ((uivector*)p)->allocsize = 0;
lodepng_free(((uivector*)p)->data);
((uivector*)p)->data = NULL;
}
/*returns 1 if success, 0 if failure ==> nothing done*/
static unsigned uivector_resize(uivector* p, size_t size) {
size_t allocsize = size * sizeof(unsigned);
if(allocsize > p->allocsize) {
size_t newsize = allocsize + (p->allocsize >> 1u);
void* data = lodepng_realloc(p->data, newsize);
if(data) {
p->allocsize = newsize;
p->data = (unsigned*)data;
}
else return 0; /*error: not enough memory*/
}
p->size = size;
return 1; /*success*/
}
static void uivector_init(uivector* p) {
p->data = NULL;
p->size = p->allocsize = 0;
}
/*returns 1 if success, 0 if failure ==> nothing done*/
static unsigned uivector_push_back(uivector* p, unsigned c) {
if(!uivector_resize(p, p->size + 1)) return 0;
p->data[p->size - 1] = c;
return 1;
}
#endif /*LODEPNG_COMPILE_ENCODER*/
#endif /*LODEPNG_COMPILE_ZLIB*/
/* /////////////////////////////////////////////////////////////////////////// */
/*dynamic vector of unsigned chars*/
typedef struct ucvector {
unsigned char* data;
size_t size; /*used size*/
size_t allocsize; /*allocated size*/
} ucvector;
/*returns 1 if success, 0 if failure ==> nothing done*/
static unsigned ucvector_reserve(ucvector* p, size_t size) {
if(size > p->allocsize) {
size_t newsize = size + (p->allocsize >> 1u);
void* data = lodepng_realloc(p->data, newsize);
if(data) {
p->allocsize = newsize;
p->data = (unsigned char*)data;
}
else return 0; /*error: not enough memory*/
}
return 1; /*success*/
}
/*returns 1 if success, 0 if failure ==> nothing done*/
static unsigned ucvector_resize(ucvector* p, size_t size) {
p->size = size;
return ucvector_reserve(p, size);
}
static ucvector ucvector_init(unsigned char* buffer, size_t size) {
ucvector v;
v.data = buffer;
v.allocsize = v.size = size;
return v;
}
/* ////////////////////////////////////////////////////////////////////////// */
#ifdef LODEPNG_COMPILE_PNG
#ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
/*free string pointer and set it to NULL*/
static void string_cleanup(char** out) {
lodepng_free(*out);
*out = NULL;
}
/*also appends null termination character*/
static char* alloc_string_sized(const char* in, size_t insize) {
char* out = (char*)lodepng_malloc(insize + 1);
if(out) {
lodepng_memcpy(out, in, insize);
out[insize] = 0;
}
return out;
}
/* dynamically allocates a new string with a copy of the null terminated input text */
static char* alloc_string(const char* in) {
return alloc_string_sized(in, lodepng_strlen(in));
}
#endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
#endif /*LODEPNG_COMPILE_PNG*/
/* ////////////////////////////////////////////////////////////////////////// */
#if defined(LODEPNG_COMPILE_DECODER) || defined(LODEPNG_COMPILE_PNG)
static unsigned lodepng_read32bitInt(const unsigned char* buffer) {
return (((unsigned)buffer[0] << 24u) | ((unsigned)buffer[1] << 16u) |
((unsigned)buffer[2] << 8u) | (unsigned)buffer[3]);
}
#endif /*defined(LODEPNG_COMPILE_DECODER) || defined(LODEPNG_COMPILE_PNG)*/
#if defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)
/*buffer must have at least 4 allocated bytes available*/
static void lodepng_set32bitInt(unsigned char* buffer, unsigned value) {
buffer[0] = (unsigned char)((value >> 24) & 0xff);
buffer[1] = (unsigned char)((value >> 16) & 0xff);
buffer[2] = (unsigned char)((value >> 8) & 0xff);
buffer[3] = (unsigned char)((value ) & 0xff);
}
#endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
/* ////////////////////////////////////////////////////////////////////////// */
/* / File IO / */
/* ////////////////////////////////////////////////////////////////////////// */
#ifdef LODEPNG_COMPILE_DISK
/* returns negative value on error. This should be pure C compatible, so no fstat. */
static long lodepng_filesize(const char* filename) {
FILE* file;
long size;
file = fopen(filename, "rb");
if(!file) return -1;
if(fseek(file, 0, SEEK_END) != 0) {
fclose(file);
return -1;
}
size = ftell(file);
/* It may give LONG_MAX as directory size, this is invalid for us. */
if(size == LONG_MAX) size = -1;
fclose(file);
return size;
}
/* load file into buffer that already has the correct allocated size. Returns error code.*/
static unsigned lodepng_buffer_file(unsigned char* out, size_t size, const char* filename) {
FILE* file;
size_t readsize;
file = fopen(filename, "rb");
if(!file) return 78;
readsize = fread(out, 1, size, file);
fclose(file);
if(readsize != size) return 78;
return 0;
}
unsigned lodepng_load_file(unsigned char** out, size_t* outsize, const char* filename) {
long size = lodepng_filesize(filename);
if(size < 0) return 78;
*outsize = (size_t)size;
*out = (unsigned char*)lodepng_malloc((size_t)size);
if(!(*out) && size > 0) return 83; /*the above malloc failed*/
return lodepng_buffer_file(*out, (size_t)size, filename);
}
/*write given buffer to the file, overwriting the file, it doesn't append to it.*/
unsigned lodepng_save_file(const unsigned char* buffer, size_t buffersize, const char* filename) {
FILE* file;
file = fopen(filename, "wb" );
if(!file) return 79;
fwrite(buffer, 1, buffersize, file);
fclose(file);
return 0;
}
#endif /*LODEPNG_COMPILE_DISK*/
/* ////////////////////////////////////////////////////////////////////////// */
/* ////////////////////////////////////////////////////////////////////////// */
/* // End of common code and tools. Begin of Zlib related code. // */
/* ////////////////////////////////////////////////////////////////////////// */
/* ////////////////////////////////////////////////////////////////////////// */
#ifdef LODEPNG_COMPILE_ZLIB
#ifdef LODEPNG_COMPILE_ENCODER
typedef struct {
ucvector* data;
unsigned char bp; /*ok to overflow, indicates bit pos inside byte*/
} LodePNGBitWriter;
static void LodePNGBitWriter_init(LodePNGBitWriter* writer, ucvector* data) {
writer->data = data;
writer->bp = 0;
}
/*TODO: this ignores potential out of memory errors*/
#define WRITEBIT(writer, bit){\
/* append new byte */\
if(((writer->bp) & 7u) == 0) {\
if(!ucvector_resize(writer->data, writer->data->size + 1)) return;\
writer->data->data[writer->data->size - 1] = 0;\
}\
(writer->data->data[writer->data->size - 1]) |= (bit << ((writer->bp) & 7u));\
++writer->bp;\
}
/* LSB of value is written first, and LSB of bytes is used first */
static void writeBits(LodePNGBitWriter* writer, unsigned value, size_t nbits) {
if(nbits == 1) { /* compiler should statically compile this case if nbits == 1 */
WRITEBIT(writer, value);
} else {
/* TODO: increase output size only once here rather than in each WRITEBIT */
size_t i;
for(i = 0; i != nbits; ++i) {
WRITEBIT(writer, (unsigned char)((value >> i) & 1));
}
}
}
/* This one is to use for adding huffman symbol, the value bits are written MSB first */
static void writeBitsReversed(LodePNGBitWriter* writer, unsigned value, size_t nbits) {
size_t i;
for(i = 0; i != nbits; ++i) {
/* TODO: increase output size only once here rather than in each WRITEBIT */
WRITEBIT(writer, (unsigned char)((value >> (nbits - 1u - i)) & 1u));
}
}
#endif /*LODEPNG_COMPILE_ENCODER*/
#ifdef LODEPNG_COMPILE_DECODER
typedef struct {
const unsigned char* data;
size_t size; /*size of data in bytes*/
size_t bitsize; /*size of data in bits, end of valid bp values, should be 8*size*/
size_t bp;
unsigned buffer; /*buffer for reading bits. NOTE: 'unsigned' must support at least 32 bits*/
} LodePNGBitReader;
/* data size argument is in bytes. Returns error if size too large causing overflow */
static unsigned LodePNGBitReader_init(LodePNGBitReader* reader, const unsigned char* data, size_t size) {
size_t temp;
reader->data = data;
reader->size = size;
/* size in bits, return error if overflow (if size_t is 32 bit this supports up to 500MB) */
if(lodepng_mulofl(size, 8u, &reader->bitsize)) return 105;
/*ensure incremented bp can be compared to bitsize without overflow even when it would be incremented 32 too much and
trying to ensure 32 more bits*/
if(lodepng_addofl(reader->bitsize, 64u, &temp)) return 105;
reader->bp = 0;
reader->buffer = 0;
return 0; /*ok*/
}
/*
ensureBits functions:
Ensures the reader can at least read nbits bits in one or more readBits calls,
safely even if not enough bits are available.
The nbits parameter is unused but is given for documentation purposes, error
checking for amount of bits must be done beforehand.
*/
/*See ensureBits documentation above. This one ensures up to 9 bits */
static LODEPNG_INLINE void ensureBits9(LodePNGBitReader* reader, size_t nbits) {
size_t start = reader->bp >> 3u;
size_t size = reader->size;
if(start + 1u < size) {
reader->buffer = (unsigned)reader->data[start + 0] | ((unsigned)reader->data[start + 1] << 8u);
reader->buffer >>= (reader->bp & 7u);
} else {
reader->buffer = 0;
if(start + 0u < size) reader->buffer = reader->data[start + 0];
reader->buffer >>= (reader->bp & 7u);
}
(void)nbits;
}
/*See ensureBits documentation above. This one ensures up to 17 bits */
static LODEPNG_INLINE void ensureBits17(LodePNGBitReader* reader, size_t nbits) {
size_t start = reader->bp >> 3u;
size_t size = reader->size;
if(start + 2u < size) {
reader->buffer = (unsigned)reader->data[start + 0] | ((unsigned)reader->data[start + 1] << 8u) |
((unsigned)reader->data[start + 2] << 16u);
reader->buffer >>= (reader->bp & 7u);
} else {
reader->buffer = 0;
if(start + 0u < size) reader->buffer |= reader->data[start + 0];
if(start + 1u < size) reader->buffer |= ((unsigned)reader->data[start + 1] << 8u);
reader->buffer >>= (reader->bp & 7u);
}
(void)nbits;
}
/*See ensureBits documentation above. This one ensures up to 25 bits */
static LODEPNG_INLINE void ensureBits25(LodePNGBitReader* reader, size_t nbits) {
size_t start = reader->bp >> 3u;
size_t size = reader->size;
if(start + 3u < size) {
reader->buffer = (unsigned)reader->data[start + 0] | ((unsigned)reader->data[start + 1] << 8u) |
((unsigned)reader->data[start + 2] << 16u) | ((unsigned)reader->data[start + 3] << 24u);
reader->buffer >>= (reader->bp & 7u);
} else {
reader->buffer = 0;
if(start + 0u < size) reader->buffer |= reader->data[start + 0];
if(start + 1u < size) reader->buffer |= ((unsigned)reader->data[start + 1] << 8u);
if(start + 2u < size) reader->buffer |= ((unsigned)reader->data[start + 2] << 16u);
reader->buffer >>= (reader->bp & 7u);
}
(void)nbits;
}
/*See ensureBits documentation above. This one ensures up to 32 bits */
static LODEPNG_INLINE void ensureBits32(LodePNGBitReader* reader, size_t nbits) {
size_t start = reader->bp >> 3u;
size_t size = reader->size;
if(start + 4u < size) {
reader->buffer = (unsigned)reader->data[start + 0] | ((unsigned)reader->data[start + 1] << 8u) |
((unsigned)reader->data[start + 2] << 16u) | ((unsigned)reader->data[start + 3] << 24u);
reader->buffer >>= (reader->bp & 7u);
reader->buffer |= (((unsigned)reader->data[start + 4] << 24u) << (8u - (reader->bp & 7u)));
} else {
reader->buffer = 0;
if(start + 0u < size) reader->buffer |= reader->data[start + 0];
if(start + 1u < size) reader->buffer |= ((unsigned)reader->data[start + 1] << 8u);
if(start + 2u < size) reader->buffer |= ((unsigned)reader->data[start + 2] << 16u);
if(start + 3u < size) reader->buffer |= ((unsigned)reader->data[start + 3] << 24u);
reader->buffer >>= (reader->bp & 7u);
}
(void)nbits;
}
/* Get bits without advancing the bit pointer. Must have enough bits available with ensureBits. Max nbits is 31. */
static LODEPNG_INLINE unsigned peekBits(LodePNGBitReader* reader, size_t nbits) {
/* The shift allows nbits to be only up to 31. */
return reader->buffer & ((1u << nbits) - 1u);
}
/* Must have enough bits available with ensureBits */
static LODEPNG_INLINE void advanceBits(LodePNGBitReader* reader, size_t nbits) {
reader->buffer >>= nbits;
reader->bp += nbits;
}
/* Must have enough bits available with ensureBits */
static LODEPNG_INLINE unsigned readBits(LodePNGBitReader* reader, size_t nbits) {
unsigned result = peekBits(reader, nbits);
advanceBits(reader, nbits);
return result;
}
#endif /*LODEPNG_COMPILE_DECODER*/
static unsigned reverseBits(unsigned bits, unsigned num) {
/*TODO: implement faster lookup table based version when needed*/
unsigned i, result = 0;
for(i = 0; i < num; i++) result |= ((bits >> (num - i - 1u)) & 1u) << i;
return result;
}
/* ////////////////////////////////////////////////////////////////////////// */
/* / Deflate - Huffman / */
/* ////////////////////////////////////////////////////////////////////////// */
#define FIRST_LENGTH_CODE_INDEX 257
#define LAST_LENGTH_CODE_INDEX 285
/*256 literals, the end code, some length codes, and 2 unused codes*/
#define NUM_DEFLATE_CODE_SYMBOLS 288
/*the distance codes have their own symbols, 30 used, 2 unused*/
#define NUM_DISTANCE_SYMBOLS 32
/*the code length codes. 0-15: code lengths, 16: copy previous 3-6 times, 17: 3-10 zeros, 18: 11-138 zeros*/
#define NUM_CODE_LENGTH_CODES 19
/*the base lengths represented by codes 257-285*/
static const unsigned LENGTHBASE[29]
= {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};
/*the extra bits used by codes 257-285 (added to base length)*/
static const unsigned LENGTHEXTRA[29]
= {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};
/*the base backwards distances (the bits of distance codes appear after length codes and use their own huffman tree)*/
static const unsigned DISTANCEBASE[30]
= {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};
/*the extra bits of backwards distances (added to base)*/
static const unsigned DISTANCEEXTRA[30]
= {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};
/*the order in which "code length alphabet code lengths" are stored as specified by deflate, out of this the huffman
tree of the dynamic huffman tree lengths is generated*/
static const unsigned CLCL_ORDER[NUM_CODE_LENGTH_CODES]
= {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
/* ////////////////////////////////////////////////////////////////////////// */
/*
Huffman tree struct, containing multiple representations of the tree
*/
typedef struct HuffmanTree {
unsigned* codes; /*the huffman codes (bit patterns representing the symbols)*/
unsigned* lengths; /*the lengths of the huffman codes*/
unsigned maxbitlen; /*maximum number of bits a single code can get*/
unsigned numcodes; /*number of symbols in the alphabet = number of codes*/
/* for reading only */
unsigned char* table_len; /*length of symbol from lookup table, or max length if secondary lookup needed*/
unsigned short* table_value; /*value of symbol from lookup table, or pointer to secondary table if needed*/
} HuffmanTree;
static void HuffmanTree_init(HuffmanTree* tree) {
tree->codes = 0;
tree->lengths = 0;
tree->table_len = 0;
tree->table_value = 0;
}
static void HuffmanTree_cleanup(HuffmanTree* tree) {
lodepng_free(tree->codes);
lodepng_free(tree->lengths);
lodepng_free(tree->table_len);
lodepng_free(tree->table_value);
}
/* amount of bits for first huffman table lookup (aka root bits), see HuffmanTree_makeTable and huffmanDecodeSymbol.*/
/* values 8u and 9u work the fastest */
#define FIRSTBITS 9u
/* a symbol value too big to represent any valid symbol, to indicate reading disallowed huffman bits combination,
which is possible in case of only 0 or 1 present symbols. */
#define INVALIDSYMBOL 65535u
/* make table for huffman decoding */
static unsigned HuffmanTree_makeTable(HuffmanTree* tree) {
static const unsigned headsize = 1u << FIRSTBITS; /*size of the first table*/
static const unsigned mask = (1u << FIRSTBITS) /*headsize*/ - 1u;
size_t i, numpresent, pointer, size; /*total table size*/
unsigned* maxlens = (unsigned*)lodepng_malloc(headsize * sizeof(unsigned));
if(!maxlens) return 83; /*alloc fail*/
/* compute maxlens: max total bit length of symbols sharing prefix in the first table*/
lodepng_memset(maxlens, 0, headsize * sizeof(*maxlens));
for(i = 0; i < tree->numcodes; i++) {
unsigned symbol = tree->codes[i];
unsigned l = tree->lengths[i];
unsigned index;
if(l <= FIRSTBITS) continue; /*symbols that fit in first table don't increase secondary table size*/
/*get the FIRSTBITS MSBs, the MSBs of the symbol are encoded first. See later comment about the reversing*/
index = reverseBits(symbol >> (l - FIRSTBITS), FIRSTBITS);
maxlens[index] = LODEPNG_MAX(maxlens[index], l);
}
/* compute total table size: size of first table plus all secondary tables for symbols longer than FIRSTBITS */
size = headsize;
for(i = 0; i < headsize; ++i) {
unsigned l = maxlens[i];
if(l > FIRSTBITS) size += (((size_t)1) << (l - FIRSTBITS));
}
tree->table_len = (unsigned char*)lodepng_malloc(size * sizeof(*tree->table_len));
tree->table_value = (unsigned short*)lodepng_malloc(size * sizeof(*tree->table_value));
if(!tree->table_len || !tree->table_value) {
lodepng_free(maxlens);
/* freeing tree->table values is done at a higher scope */
return 83; /*alloc fail*/
}
/*initialize with an invalid length to indicate unused entries*/
for(i = 0; i < size; ++i) tree->table_len[i] = 16;
/*fill in the first table for long symbols: max prefix size and pointer to secondary tables*/
pointer = headsize;
for(i = 0; i < headsize; ++i) {
unsigned l = maxlens[i];
if(l <= FIRSTBITS) continue;
tree->table_len[i] = l;
tree->table_value[i] = (unsigned short)pointer;
pointer += (((size_t)1) << (l - FIRSTBITS));
}
lodepng_free(maxlens);
/*fill in the first table for short symbols, or secondary table for long symbols*/
numpresent = 0;
for(i = 0; i < tree->numcodes; ++i) {
unsigned l = tree->lengths[i];
unsigned symbol, reverse;
if(l == 0) continue;
symbol = tree->codes[i]; /*the huffman bit pattern. i itself is the value.*/
/*reverse bits, because the huffman bits are given in MSB first order but the bit reader reads LSB first*/
reverse = reverseBits(symbol, l);
numpresent++;
if(l <= FIRSTBITS) {
/*short symbol, fully in first table, replicated num times if l < FIRSTBITS*/
unsigned num = 1u << (FIRSTBITS - l);
unsigned j;
for(j = 0; j < num; ++j) {
/*bit reader will read the l bits of symbol first, the remaining FIRSTBITS - l bits go to the MSB's*/
unsigned index = reverse | (j << l);
if(tree->table_len[index] != 16) return 55; /*invalid tree: long symbol shares prefix with short symbol*/
tree->table_len[index] = l;
tree->table_value[index] = (unsigned short)i;
}
} else {
/*long symbol, shares prefix with other long symbols in first lookup table, needs second lookup*/
/*the FIRSTBITS MSBs of the symbol are the first table index*/
unsigned index = reverse & mask;
unsigned maxlen = tree->table_len[index];
/*log2 of secondary table length, should be >= l - FIRSTBITS*/
unsigned tablelen = maxlen - FIRSTBITS;
unsigned start = tree->table_value[index]; /*starting index in secondary table*/
unsigned num = 1u << (tablelen - (l - FIRSTBITS)); /*amount of entries of this symbol in secondary table*/
unsigned j;
if(maxlen < l) return 55; /*invalid tree: long symbol shares prefix with short symbol*/
for(j = 0; j < num; ++j) {
unsigned reverse2 = reverse >> FIRSTBITS; /* l - FIRSTBITS bits */
unsigned index2 = start + (reverse2 | (j << (l - FIRSTBITS)));
tree->table_len[index2] = l;
tree->table_value[index2] = (unsigned short)i;
}
}
}
if(numpresent < 2) {
/* In case of exactly 1 symbol, in theory the huffman symbol needs 0 bits,
but deflate uses 1 bit instead. In case of 0 symbols, no symbols can
appear at all, but such huffman tree could still exist (e.g. if distance
codes are never used). In both cases, not all symbols of the table will be
filled in. Fill them in with an invalid symbol value so returning them from
huffmanDecodeSymbol will cause error. */
for(i = 0; i < size; ++i) {
if(tree->table_len[i] == 16) {
/* As length, use a value smaller than FIRSTBITS for the head table,
and a value larger than FIRSTBITS for the secondary table, to ensure
valid behavior for advanceBits when reading this symbol. */
tree->table_len[i] = (i < headsize) ? 1 : (FIRSTBITS + 1);
tree->table_value[i] = INVALIDSYMBOL;
}
}
} else {
/* A good huffman tree has N * 2 - 1 nodes, of which N - 1 are internal nodes.
If that is not the case (due to too long length codes), the table will not
have been fully used, and this is an error (not all bit combinations can be
decoded): an oversubscribed huffman tree, indicated by error 55. */
for(i = 0; i < size; ++i) {
if(tree->table_len[i] == 16) return 55;
}
}
return 0;
}
/*
Second step for the ...makeFromLengths and ...makeFromFrequencies functions.
numcodes, lengths and maxbitlen must already be filled in correctly. return
value is error.
*/
static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree) {
unsigned* blcount;
unsigned* nextcode;
unsigned error = 0;
unsigned bits, n;
tree->codes = (unsigned*)lodepng_malloc(tree->numcodes * sizeof(unsigned));
blcount = (unsigned*)lodepng_malloc((tree->maxbitlen + 1) * sizeof(unsigned));
nextcode = (unsigned*)lodepng_malloc((tree->maxbitlen + 1) * sizeof(unsigned));
if(!tree->codes || !blcount || !nextcode) error = 83; /*alloc fail*/
if(!error) {
for(n = 0; n != tree->maxbitlen + 1; n++) blcount[n] = nextcode[n] = 0;
/*step 1: count number of instances of each code length*/
for(bits = 0; bits != tree->numcodes; ++bits) ++blcount[tree->lengths[bits]];
/*step 2: generate the nextcode values*/
for(bits = 1; bits <= tree->maxbitlen; ++bits) {
nextcode[bits] = (nextcode[bits - 1] + blcount[bits - 1]) << 1u;
}
/*step 3: generate all the codes*/
for(n = 0; n != tree->numcodes; ++n) {
if(tree->lengths[n] != 0) {
tree->codes[n] = nextcode[tree->lengths[n]]++;
/*remove superfluous bits from the code*/
tree->codes[n] &= ((1u << tree->lengths[n]) - 1u);
}
}
}
lodepng_free(blcount);
lodepng_free(nextcode);
if(!error) error = HuffmanTree_makeTable(tree);
return error;
}
/*
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.
*/
static unsigned HuffmanTree_makeFromLengths(HuffmanTree* tree, const unsigned* bitlen,
size_t numcodes, unsigned maxbitlen) {
unsigned i;
tree->lengths = (unsigned*)lodepng_malloc(numcodes * sizeof(unsigned));
if(!tree->lengths) return 83; /*alloc fail*/
for(i = 0; i != numcodes; ++i) tree->lengths[i] = bitlen[i];
tree->numcodes = (unsigned)numcodes; /*number of symbols*/
tree->maxbitlen = maxbitlen;
return HuffmanTree_makeFromLengths2(tree);
}
#ifdef LODEPNG_COMPILE_ENCODER
/*BPM: Boundary Package Merge, see "A Fast and Space-Economical Algorithm for Length-Limited Coding",
Jyrki Katajainen, Alistair Moffat, Andrew Turpin, 1995.*/
/*chain node for boundary package merge*/
typedef struct BPMNode {
int weight; /*the sum of all weights in this chain*/
unsigned index; /*index of this leaf node (called "count" in the paper)*/
struct BPMNode* tail; /*the next nodes in this chain (null if last)*/
int in_use;
} BPMNode;
/*lists of chains*/
typedef struct BPMLists {
/*memory pool*/
unsigned memsize;
BPMNode* memory;
unsigned numfree;
unsigned nextfree;
BPMNode** freelist;
/*two heads of lookahead chains per list*/
unsigned listsize;
BPMNode** chains0;
BPMNode** chains1;
} BPMLists;
/*creates a new chain node with the given parameters, from the memory in the lists */
static BPMNode* bpmnode_create(BPMLists* lists, int weight, unsigned index, BPMNode* tail) {
unsigned i;
BPMNode* result;
/*memory full, so garbage collect*/
if(lists->nextfree >= lists->numfree) {
/*mark only those that are in use*/
for(i = 0; i != lists->memsize; ++i) lists->memory[i].in_use = 0;
for(i = 0; i != lists->listsize; ++i) {
BPMNode* node;
for(node = lists->chains0[i]; node != 0; node = node->tail) node->in_use = 1;
for(node = lists->chains1[i]; node != 0; node = node->tail) node->in_use = 1;
}
/*collect those that are free*/
lists->numfree = 0;
for(i = 0; i != lists->memsize; ++i) {
if(!lists->memory[i].in_use) lists->freelist[lists->numfree++] = &lists->memory[i];
}
lists->nextfree = 0;
}
result = lists->freelist[lists->nextfree++];
result->weight = weight;
result->index = index;
result->tail = tail;
return result;
}
/*sort the leaves with stable mergesort*/
static void bpmnode_sort(BPMNode* leaves, size_t num) {
BPMNode* mem = (BPMNode*)lodepng_malloc(sizeof(*leaves) * num);
size_t width, counter = 0;
for(width = 1; width < num; width *= 2) {
BPMNode* a = (counter & 1) ? mem : leaves;
BPMNode* b = (counter & 1) ? leaves : mem;
size_t p;
for(p = 0; p < num; p += 2 * width) {
size_t q = (p + width > num) ? num : (p + width);
size_t r = (p + 2 * width > num) ? num : (p + 2 * width);
size_t i = p, j = q, k;
for(k = p; k < r; k++) {
if(i < q && (j >= r || a[i].weight <= a[j].weight)) b[k] = a[i++];
else b[k] = a[j++];
}
}
counter++;
}
if(counter & 1) lodepng_memcpy(leaves, mem, sizeof(*leaves) * num);
lodepng_free(mem);
}
/*Boundary Package Merge step, numpresent is the amount of leaves, and c is the current chain.*/
static void boundaryPM(BPMLists* lists, BPMNode* leaves, size_t numpresent, int c, int num) {
unsigned lastindex = lists->chains1[c]->index;
if(c == 0) {
if(lastindex >= numpresent) return;
lists->chains0[c] = lists->chains1[c];
lists->chains1[c] = bpmnode_create(lists, leaves[lastindex].weight, lastindex + 1, 0);
} else {
/*sum of the weights of the head nodes of the previous lookahead chains.*/
int sum = lists->chains0[c - 1]->weight + lists->chains1[c - 1]->weight;
lists->chains0[c] = lists->chains1[c];
if(lastindex < numpresent && sum > leaves[lastindex].weight) {
lists->chains1[c] = bpmnode_create(lists, leaves[lastindex].weight, lastindex + 1, lists->chains1[c]->tail);
return;
}
lists->chains1[c] = bpmnode_create(lists, sum, lastindex, lists->chains1[c - 1]);
/*in the end we are only interested in the chain of the last list, so no
need to recurse if we're at the last one (this gives measurable speedup)*/
if(num + 1 < (int)(2 * numpresent - 2)) {
boundaryPM(lists, leaves, numpresent, c - 1, num);
boundaryPM(lists, leaves, numpresent, c - 1, num);
}
}
}
unsigned lodepng_huffman_code_lengths(unsigned* lengths, const unsigned* frequencies,
size_t numcodes, unsigned maxbitlen) {
unsigned error = 0;
unsigned i;
size_t numpresent = 0; /*number of symbols with non-zero frequency*/
BPMNode* leaves; /*the symbols, only those with > 0 frequency*/
if(numcodes == 0) return 80; /*error: a tree of 0 symbols is not supposed to be made*/
if((1u << maxbitlen) < (unsigned)numcodes) return 80; /*error: represent all symbols*/
leaves = (BPMNode*)lodepng_malloc(numcodes * sizeof(*leaves));
if(!leaves) return 83; /*alloc fail*/
for(i = 0; i != numcodes; ++i) {
if(frequencies[i] > 0) {
leaves[numpresent].weight = (int)frequencies[i];
leaves[numpresent].index = i;
++numpresent;
}
}
lodepng_memset(lengths, 0, numcodes * sizeof(*lengths));
/*ensure at least two present symbols. There should be at least one symbol
according to RFC 1951 section 3.2.7. Some decoders incorrectly require two. To
make these work as well ensure there are at least two symbols. The
Package-Merge code below also doesn't work correctly if there's only one
symbol, it'd give it the theoretical 0 bits but in practice zlib wants 1 bit*/
if(numpresent == 0) {
lengths[0] = lengths[1] = 1; /*note that for RFC 1951 section 3.2.7, only lengths[0] = 1 is needed*/
} else if(numpresent == 1) {
lengths[leaves[0].index] = 1;
lengths[leaves[0].index == 0 ? 1 : 0] = 1;
} else {
BPMLists lists;
BPMNode* node;
bpmnode_sort(leaves, numpresent);
lists.listsize = maxbitlen;
lists.memsize = 2 * maxbitlen * (maxbitlen + 1);
lists.nextfree = 0;
lists.numfree = lists.memsize;
lists.memory = (BPMNode*)lodepng_malloc(lists.memsize * sizeof(*lists.memory));
lists.freelist = (BPMNode**)lodepng_malloc(lists.memsize * sizeof(BPMNode*));
lists.chains0 = (BPMNode**)lodepng_malloc(lists.listsize * sizeof(BPMNode*));
lists.chains1 = (BPMNode**)lodepng_malloc(lists.listsize * sizeof(BPMNode*));
if(!lists.memory || !lists.freelist || !lists.chains0 || !lists.chains1) error = 83; /*alloc fail*/
if(!error) {
for(i = 0; i != lists.memsize; ++i) lists.freelist[i] = &lists.memory[i];
bpmnode_create(&lists, leaves[0].weight, 1, 0);
bpmnode_create(&lists, leaves[1].weight, 2, 0);
for(i = 0; i != lists.listsize; ++i) {
lists.chains0[i] = &lists.memory[0];
lists.chains1[i] = &lists.memory[1];
}