Graphical demo for the LPC4088 Experiment Base Board with one of the Display Expansion Kits. This program decodes decodes and shows two png images.

Dependencies:   EALib mbed

Committer:
embeddedartists
Date:
Fri Oct 03 13:30:09 2014 +0000
Revision:
0:b567d56a59d7
First version

Who changed what in which revision?

UserRevisionLine numberNew contents of line
embeddedartists 0:b567d56a59d7 1 /*
embeddedartists 0:b567d56a59d7 2 LodePNG version 20131222
embeddedartists 0:b567d56a59d7 3
embeddedartists 0:b567d56a59d7 4 Copyright (c) 2005-2013 Lode Vandevenne
embeddedartists 0:b567d56a59d7 5
embeddedartists 0:b567d56a59d7 6 This software is provided 'as-is', without any express or implied
embeddedartists 0:b567d56a59d7 7 warranty. In no event will the authors be held liable for any damages
embeddedartists 0:b567d56a59d7 8 arising from the use of this software.
embeddedartists 0:b567d56a59d7 9
embeddedartists 0:b567d56a59d7 10 Permission is granted to anyone to use this software for any purpose,
embeddedartists 0:b567d56a59d7 11 including commercial applications, and to alter it and redistribute it
embeddedartists 0:b567d56a59d7 12 freely, subject to the following restrictions:
embeddedartists 0:b567d56a59d7 13
embeddedartists 0:b567d56a59d7 14 1. The origin of this software must not be misrepresented; you must not
embeddedartists 0:b567d56a59d7 15 claim that you wrote the original software. If you use this software
embeddedartists 0:b567d56a59d7 16 in a product, an acknowledgment in the product documentation would be
embeddedartists 0:b567d56a59d7 17 appreciated but is not required.
embeddedartists 0:b567d56a59d7 18
embeddedartists 0:b567d56a59d7 19 2. Altered source versions must be plainly marked as such, and must not be
embeddedartists 0:b567d56a59d7 20 misrepresented as being the original software.
embeddedartists 0:b567d56a59d7 21
embeddedartists 0:b567d56a59d7 22 3. This notice may not be removed or altered from any source
embeddedartists 0:b567d56a59d7 23 distribution.
embeddedartists 0:b567d56a59d7 24 */
embeddedartists 0:b567d56a59d7 25
embeddedartists 0:b567d56a59d7 26 /*
embeddedartists 0:b567d56a59d7 27 The manual and changelog are in the header file "lodepng.h"
embeddedartists 0:b567d56a59d7 28 Rename this file to lodepng.cpp to use it for C++, or to lodepng.c to use it for C.
embeddedartists 0:b567d56a59d7 29 */
embeddedartists 0:b567d56a59d7 30
embeddedartists 0:b567d56a59d7 31 #include "lodepng.h"
embeddedartists 0:b567d56a59d7 32
embeddedartists 0:b567d56a59d7 33 #include <stdio.h>
embeddedartists 0:b567d56a59d7 34 #include <stdlib.h>
embeddedartists 0:b567d56a59d7 35
embeddedartists 0:b567d56a59d7 36 #ifdef LODEPNG_COMPILE_CPP
embeddedartists 0:b567d56a59d7 37 #include <fstream>
embeddedartists 0:b567d56a59d7 38 #endif /*LODEPNG_COMPILE_CPP*/
embeddedartists 0:b567d56a59d7 39
embeddedartists 0:b567d56a59d7 40 #define VERSION_STRING "20131222"
embeddedartists 0:b567d56a59d7 41
embeddedartists 0:b567d56a59d7 42 /*
embeddedartists 0:b567d56a59d7 43 This source file is built up in the following large parts. The code sections
embeddedartists 0:b567d56a59d7 44 with the "LODEPNG_COMPILE_" #defines divide this up further in an intermixed way.
embeddedartists 0:b567d56a59d7 45 -Tools for C and common code for PNG and Zlib
embeddedartists 0:b567d56a59d7 46 -C Code for Zlib (huffman, deflate, ...)
embeddedartists 0:b567d56a59d7 47 -C Code for PNG (file format chunks, adam7, PNG filters, color conversions, ...)
embeddedartists 0:b567d56a59d7 48 -The C++ wrapper around all of the above
embeddedartists 0:b567d56a59d7 49 */
embeddedartists 0:b567d56a59d7 50
embeddedartists 0:b567d56a59d7 51 /*The malloc, realloc and free functions defined here with "lodepng_" in front
embeddedartists 0:b567d56a59d7 52 of the name, so that you can easily change them to others related to your
embeddedartists 0:b567d56a59d7 53 platform if needed. Everything else in the code calls these. Pass
embeddedartists 0:b567d56a59d7 54 -DLODEPNG_NO_COMPILE_ALLOCATORS to the compiler, or comment out
embeddedartists 0:b567d56a59d7 55 #define LODEPNG_COMPILE_ALLOCATORS in the header, to disable the ones here and
embeddedartists 0:b567d56a59d7 56 define them in your own project's source files without needing to change
embeddedartists 0:b567d56a59d7 57 lodepng source code. Don't forget to remove "static" if you copypaste them
embeddedartists 0:b567d56a59d7 58 from here.*/
embeddedartists 0:b567d56a59d7 59
embeddedartists 0:b567d56a59d7 60 #ifdef LODEPNG_COMPILE_ALLOCATORS
embeddedartists 0:b567d56a59d7 61 static void* lodepng_malloc(size_t size)
embeddedartists 0:b567d56a59d7 62 {
embeddedartists 0:b567d56a59d7 63 return malloc(size);
embeddedartists 0:b567d56a59d7 64 }
embeddedartists 0:b567d56a59d7 65
embeddedartists 0:b567d56a59d7 66 static void* lodepng_realloc(void* ptr, size_t new_size)
embeddedartists 0:b567d56a59d7 67 {
embeddedartists 0:b567d56a59d7 68 return realloc(ptr, new_size);
embeddedartists 0:b567d56a59d7 69 }
embeddedartists 0:b567d56a59d7 70
embeddedartists 0:b567d56a59d7 71 static void lodepng_free(void* ptr)
embeddedartists 0:b567d56a59d7 72 {
embeddedartists 0:b567d56a59d7 73 free(ptr);
embeddedartists 0:b567d56a59d7 74 }
embeddedartists 0:b567d56a59d7 75 #else /*LODEPNG_COMPILE_ALLOCATORS*/
embeddedartists 0:b567d56a59d7 76 void* lodepng_malloc(size_t size);
embeddedartists 0:b567d56a59d7 77 void* lodepng_realloc(void* ptr, size_t new_size);
embeddedartists 0:b567d56a59d7 78 void lodepng_free(void* ptr);
embeddedartists 0:b567d56a59d7 79 #endif /*LODEPNG_COMPILE_ALLOCATORS*/
embeddedartists 0:b567d56a59d7 80
embeddedartists 0:b567d56a59d7 81 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 82 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 83 /* // Tools for C, and common code for PNG and Zlib. // */
embeddedartists 0:b567d56a59d7 84 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 85 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 86
embeddedartists 0:b567d56a59d7 87 /*
embeddedartists 0:b567d56a59d7 88 Often in case of an error a value is assigned to a variable and then it breaks
embeddedartists 0:b567d56a59d7 89 out of a loop (to go to the cleanup phase of a function). This macro does that.
embeddedartists 0:b567d56a59d7 90 It makes the error handling code shorter and more readable.
embeddedartists 0:b567d56a59d7 91
embeddedartists 0:b567d56a59d7 92 Example: if(!uivector_resizev(&frequencies_ll, 286, 0)) ERROR_BREAK(83);
embeddedartists 0:b567d56a59d7 93 */
embeddedartists 0:b567d56a59d7 94 #define CERROR_BREAK(errorvar, code)\
embeddedartists 0:b567d56a59d7 95 {\
embeddedartists 0:b567d56a59d7 96 errorvar = code;\
embeddedartists 0:b567d56a59d7 97 break;\
embeddedartists 0:b567d56a59d7 98 }
embeddedartists 0:b567d56a59d7 99
embeddedartists 0:b567d56a59d7 100 /*version of CERROR_BREAK that assumes the common case where the error variable is named "error"*/
embeddedartists 0:b567d56a59d7 101 #define ERROR_BREAK(code) CERROR_BREAK(error, code)
embeddedartists 0:b567d56a59d7 102
embeddedartists 0:b567d56a59d7 103 /*Set error var to the error code, and return it.*/
embeddedartists 0:b567d56a59d7 104 #define CERROR_RETURN_ERROR(errorvar, code)\
embeddedartists 0:b567d56a59d7 105 {\
embeddedartists 0:b567d56a59d7 106 errorvar = code;\
embeddedartists 0:b567d56a59d7 107 return code;\
embeddedartists 0:b567d56a59d7 108 }
embeddedartists 0:b567d56a59d7 109
embeddedartists 0:b567d56a59d7 110 /*Try the code, if it returns error, also return the error.*/
embeddedartists 0:b567d56a59d7 111 #define CERROR_TRY_RETURN(call)\
embeddedartists 0:b567d56a59d7 112 {\
embeddedartists 0:b567d56a59d7 113 unsigned error = call;\
embeddedartists 0:b567d56a59d7 114 if(error) return error;\
embeddedartists 0:b567d56a59d7 115 }
embeddedartists 0:b567d56a59d7 116
embeddedartists 0:b567d56a59d7 117 /*
embeddedartists 0:b567d56a59d7 118 About uivector, ucvector and string:
embeddedartists 0:b567d56a59d7 119 -All of them wrap dynamic arrays or text strings in a similar way.
embeddedartists 0:b567d56a59d7 120 -LodePNG was originally written in C++. The vectors replace the std::vectors that were used in the C++ version.
embeddedartists 0:b567d56a59d7 121 -The string tools are made to avoid problems with compilers that declare things like strncat as deprecated.
embeddedartists 0:b567d56a59d7 122 -They're not used in the interface, only internally in this file as static functions.
embeddedartists 0:b567d56a59d7 123 -As with many other structs in this file, the init and cleanup functions serve as ctor and dtor.
embeddedartists 0:b567d56a59d7 124 */
embeddedartists 0:b567d56a59d7 125
embeddedartists 0:b567d56a59d7 126 #ifdef LODEPNG_COMPILE_ZLIB
embeddedartists 0:b567d56a59d7 127 /*dynamic vector of unsigned ints*/
embeddedartists 0:b567d56a59d7 128 typedef struct uivector
embeddedartists 0:b567d56a59d7 129 {
embeddedartists 0:b567d56a59d7 130 unsigned* data;
embeddedartists 0:b567d56a59d7 131 size_t size; /*size in number of unsigned longs*/
embeddedartists 0:b567d56a59d7 132 size_t allocsize; /*allocated size in bytes*/
embeddedartists 0:b567d56a59d7 133 } uivector;
embeddedartists 0:b567d56a59d7 134
embeddedartists 0:b567d56a59d7 135 static void uivector_cleanup(void* p)
embeddedartists 0:b567d56a59d7 136 {
embeddedartists 0:b567d56a59d7 137 ((uivector*)p)->size = ((uivector*)p)->allocsize = 0;
embeddedartists 0:b567d56a59d7 138 lodepng_free(((uivector*)p)->data);
embeddedartists 0:b567d56a59d7 139 ((uivector*)p)->data = NULL;
embeddedartists 0:b567d56a59d7 140 }
embeddedartists 0:b567d56a59d7 141
embeddedartists 0:b567d56a59d7 142 /*returns 1 if success, 0 if failure ==> nothing done*/
embeddedartists 0:b567d56a59d7 143 static unsigned uivector_resize(uivector* p, size_t size)
embeddedartists 0:b567d56a59d7 144 {
embeddedartists 0:b567d56a59d7 145 if(size * sizeof(unsigned) > p->allocsize)
embeddedartists 0:b567d56a59d7 146 {
embeddedartists 0:b567d56a59d7 147 size_t newsize = size * sizeof(unsigned) * 2;
embeddedartists 0:b567d56a59d7 148 void* data = lodepng_realloc(p->data, newsize);
embeddedartists 0:b567d56a59d7 149 if(data)
embeddedartists 0:b567d56a59d7 150 {
embeddedartists 0:b567d56a59d7 151 p->allocsize = newsize;
embeddedartists 0:b567d56a59d7 152 p->data = (unsigned*)data;
embeddedartists 0:b567d56a59d7 153 p->size = size;
embeddedartists 0:b567d56a59d7 154 }
embeddedartists 0:b567d56a59d7 155 else return 0;
embeddedartists 0:b567d56a59d7 156 }
embeddedartists 0:b567d56a59d7 157 else p->size = size;
embeddedartists 0:b567d56a59d7 158 return 1;
embeddedartists 0:b567d56a59d7 159 }
embeddedartists 0:b567d56a59d7 160
embeddedartists 0:b567d56a59d7 161 /*resize and give all new elements the value*/
embeddedartists 0:b567d56a59d7 162 static unsigned uivector_resizev(uivector* p, size_t size, unsigned value)
embeddedartists 0:b567d56a59d7 163 {
embeddedartists 0:b567d56a59d7 164 size_t oldsize = p->size, i;
embeddedartists 0:b567d56a59d7 165 if(!uivector_resize(p, size)) return 0;
embeddedartists 0:b567d56a59d7 166 for(i = oldsize; i < size; i++) p->data[i] = value;
embeddedartists 0:b567d56a59d7 167 return 1;
embeddedartists 0:b567d56a59d7 168 }
embeddedartists 0:b567d56a59d7 169
embeddedartists 0:b567d56a59d7 170 static void uivector_init(uivector* p)
embeddedartists 0:b567d56a59d7 171 {
embeddedartists 0:b567d56a59d7 172 p->data = NULL;
embeddedartists 0:b567d56a59d7 173 p->size = p->allocsize = 0;
embeddedartists 0:b567d56a59d7 174 }
embeddedartists 0:b567d56a59d7 175
embeddedartists 0:b567d56a59d7 176 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 177 /*returns 1 if success, 0 if failure ==> nothing done*/
embeddedartists 0:b567d56a59d7 178 static unsigned uivector_push_back(uivector* p, unsigned c)
embeddedartists 0:b567d56a59d7 179 {
embeddedartists 0:b567d56a59d7 180 if(!uivector_resize(p, p->size + 1)) return 0;
embeddedartists 0:b567d56a59d7 181 p->data[p->size - 1] = c;
embeddedartists 0:b567d56a59d7 182 return 1;
embeddedartists 0:b567d56a59d7 183 }
embeddedartists 0:b567d56a59d7 184
embeddedartists 0:b567d56a59d7 185 /*copy q to p, returns 1 if success, 0 if failure ==> nothing done*/
embeddedartists 0:b567d56a59d7 186 static unsigned uivector_copy(uivector* p, const uivector* q)
embeddedartists 0:b567d56a59d7 187 {
embeddedartists 0:b567d56a59d7 188 size_t i;
embeddedartists 0:b567d56a59d7 189 if(!uivector_resize(p, q->size)) return 0;
embeddedartists 0:b567d56a59d7 190 for(i = 0; i < q->size; i++) p->data[i] = q->data[i];
embeddedartists 0:b567d56a59d7 191 return 1;
embeddedartists 0:b567d56a59d7 192 }
embeddedartists 0:b567d56a59d7 193 #endif /*LODEPNG_COMPILE_ENCODER*/
embeddedartists 0:b567d56a59d7 194 #endif /*LODEPNG_COMPILE_ZLIB*/
embeddedartists 0:b567d56a59d7 195
embeddedartists 0:b567d56a59d7 196 /* /////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 197
embeddedartists 0:b567d56a59d7 198 /*dynamic vector of unsigned chars*/
embeddedartists 0:b567d56a59d7 199 typedef struct ucvector
embeddedartists 0:b567d56a59d7 200 {
embeddedartists 0:b567d56a59d7 201 unsigned char* data;
embeddedartists 0:b567d56a59d7 202 size_t size; /*used size*/
embeddedartists 0:b567d56a59d7 203 size_t allocsize; /*allocated size*/
embeddedartists 0:b567d56a59d7 204 } ucvector;
embeddedartists 0:b567d56a59d7 205
embeddedartists 0:b567d56a59d7 206 /*returns 1 if success, 0 if failure ==> nothing done*/
embeddedartists 0:b567d56a59d7 207 static unsigned ucvector_resize(ucvector* p, size_t size)
embeddedartists 0:b567d56a59d7 208 {
embeddedartists 0:b567d56a59d7 209 if(size * sizeof(unsigned char) > p->allocsize)
embeddedartists 0:b567d56a59d7 210 {
embeddedartists 0:b567d56a59d7 211 size_t newsize = size * sizeof(unsigned char) * 2;
embeddedartists 0:b567d56a59d7 212 void* data = lodepng_realloc(p->data, newsize);
embeddedartists 0:b567d56a59d7 213 if(data)
embeddedartists 0:b567d56a59d7 214 {
embeddedartists 0:b567d56a59d7 215 p->allocsize = newsize;
embeddedartists 0:b567d56a59d7 216 p->data = (unsigned char*)data;
embeddedartists 0:b567d56a59d7 217 p->size = size;
embeddedartists 0:b567d56a59d7 218 }
embeddedartists 0:b567d56a59d7 219 else return 0; /*error: not enough memory*/
embeddedartists 0:b567d56a59d7 220 }
embeddedartists 0:b567d56a59d7 221 else p->size = size;
embeddedartists 0:b567d56a59d7 222 return 1;
embeddedartists 0:b567d56a59d7 223 }
embeddedartists 0:b567d56a59d7 224
embeddedartists 0:b567d56a59d7 225 #ifdef LODEPNG_COMPILE_PNG
embeddedartists 0:b567d56a59d7 226
embeddedartists 0:b567d56a59d7 227 static void ucvector_cleanup(void* p)
embeddedartists 0:b567d56a59d7 228 {
embeddedartists 0:b567d56a59d7 229 ((ucvector*)p)->size = ((ucvector*)p)->allocsize = 0;
embeddedartists 0:b567d56a59d7 230 lodepng_free(((ucvector*)p)->data);
embeddedartists 0:b567d56a59d7 231 ((ucvector*)p)->data = NULL;
embeddedartists 0:b567d56a59d7 232 }
embeddedartists 0:b567d56a59d7 233
embeddedartists 0:b567d56a59d7 234 static void ucvector_init(ucvector* p)
embeddedartists 0:b567d56a59d7 235 {
embeddedartists 0:b567d56a59d7 236 p->data = NULL;
embeddedartists 0:b567d56a59d7 237 p->size = p->allocsize = 0;
embeddedartists 0:b567d56a59d7 238 }
embeddedartists 0:b567d56a59d7 239
embeddedartists 0:b567d56a59d7 240 #ifdef LODEPNG_COMPILE_DECODER
embeddedartists 0:b567d56a59d7 241 /*resize and give all new elements the value*/
embeddedartists 0:b567d56a59d7 242 static unsigned ucvector_resizev(ucvector* p, size_t size, unsigned char value)
embeddedartists 0:b567d56a59d7 243 {
embeddedartists 0:b567d56a59d7 244 size_t oldsize = p->size, i;
embeddedartists 0:b567d56a59d7 245 if(!ucvector_resize(p, size)) return 0;
embeddedartists 0:b567d56a59d7 246 for(i = oldsize; i < size; i++) p->data[i] = value;
embeddedartists 0:b567d56a59d7 247 return 1;
embeddedartists 0:b567d56a59d7 248 }
embeddedartists 0:b567d56a59d7 249 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 250 #endif /*LODEPNG_COMPILE_PNG*/
embeddedartists 0:b567d56a59d7 251
embeddedartists 0:b567d56a59d7 252 #ifdef LODEPNG_COMPILE_ZLIB
embeddedartists 0:b567d56a59d7 253 /*you can both convert from vector to buffer&size and vica versa. If you use
embeddedartists 0:b567d56a59d7 254 init_buffer to take over a buffer and size, it is not needed to use cleanup*/
embeddedartists 0:b567d56a59d7 255 static void ucvector_init_buffer(ucvector* p, unsigned char* buffer, size_t size)
embeddedartists 0:b567d56a59d7 256 {
embeddedartists 0:b567d56a59d7 257 p->data = buffer;
embeddedartists 0:b567d56a59d7 258 p->allocsize = p->size = size;
embeddedartists 0:b567d56a59d7 259 }
embeddedartists 0:b567d56a59d7 260 #endif /*LODEPNG_COMPILE_ZLIB*/
embeddedartists 0:b567d56a59d7 261
embeddedartists 0:b567d56a59d7 262 #if (defined(LODEPNG_COMPILE_PNG) && defined(LODEPNG_COMPILE_ANCILLARY_CHUNKS)) || defined(LODEPNG_COMPILE_ENCODER)
embeddedartists 0:b567d56a59d7 263 /*returns 1 if success, 0 if failure ==> nothing done*/
embeddedartists 0:b567d56a59d7 264 static unsigned ucvector_push_back(ucvector* p, unsigned char c)
embeddedartists 0:b567d56a59d7 265 {
embeddedartists 0:b567d56a59d7 266 if(!ucvector_resize(p, p->size + 1)) return 0;
embeddedartists 0:b567d56a59d7 267 p->data[p->size - 1] = c;
embeddedartists 0:b567d56a59d7 268 return 1;
embeddedartists 0:b567d56a59d7 269 }
embeddedartists 0:b567d56a59d7 270 #endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
embeddedartists 0:b567d56a59d7 271
embeddedartists 0:b567d56a59d7 272
embeddedartists 0:b567d56a59d7 273 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 274
embeddedartists 0:b567d56a59d7 275 #ifdef LODEPNG_COMPILE_PNG
embeddedartists 0:b567d56a59d7 276 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
embeddedartists 0:b567d56a59d7 277 /*returns 1 if success, 0 if failure ==> nothing done*/
embeddedartists 0:b567d56a59d7 278 static unsigned string_resize(char** out, size_t size)
embeddedartists 0:b567d56a59d7 279 {
embeddedartists 0:b567d56a59d7 280 char* data = (char*)lodepng_realloc(*out, size + 1);
embeddedartists 0:b567d56a59d7 281 if(data)
embeddedartists 0:b567d56a59d7 282 {
embeddedartists 0:b567d56a59d7 283 data[size] = 0; /*null termination char*/
embeddedartists 0:b567d56a59d7 284 *out = data;
embeddedartists 0:b567d56a59d7 285 }
embeddedartists 0:b567d56a59d7 286 return data != 0;
embeddedartists 0:b567d56a59d7 287 }
embeddedartists 0:b567d56a59d7 288
embeddedartists 0:b567d56a59d7 289 /*init a {char*, size_t} pair for use as string*/
embeddedartists 0:b567d56a59d7 290 static void string_init(char** out)
embeddedartists 0:b567d56a59d7 291 {
embeddedartists 0:b567d56a59d7 292 *out = NULL;
embeddedartists 0:b567d56a59d7 293 string_resize(out, 0);
embeddedartists 0:b567d56a59d7 294 }
embeddedartists 0:b567d56a59d7 295
embeddedartists 0:b567d56a59d7 296 /*free the above pair again*/
embeddedartists 0:b567d56a59d7 297 static void string_cleanup(char** out)
embeddedartists 0:b567d56a59d7 298 {
embeddedartists 0:b567d56a59d7 299 lodepng_free(*out);
embeddedartists 0:b567d56a59d7 300 *out = NULL;
embeddedartists 0:b567d56a59d7 301 }
embeddedartists 0:b567d56a59d7 302
embeddedartists 0:b567d56a59d7 303 static void string_set(char** out, const char* in)
embeddedartists 0:b567d56a59d7 304 {
embeddedartists 0:b567d56a59d7 305 size_t insize = strlen(in), i = 0;
embeddedartists 0:b567d56a59d7 306 if(string_resize(out, insize))
embeddedartists 0:b567d56a59d7 307 {
embeddedartists 0:b567d56a59d7 308 for(i = 0; i < insize; i++)
embeddedartists 0:b567d56a59d7 309 {
embeddedartists 0:b567d56a59d7 310 (*out)[i] = in[i];
embeddedartists 0:b567d56a59d7 311 }
embeddedartists 0:b567d56a59d7 312 }
embeddedartists 0:b567d56a59d7 313 }
embeddedartists 0:b567d56a59d7 314 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
embeddedartists 0:b567d56a59d7 315 #endif /*LODEPNG_COMPILE_PNG*/
embeddedartists 0:b567d56a59d7 316
embeddedartists 0:b567d56a59d7 317 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 318
embeddedartists 0:b567d56a59d7 319 unsigned lodepng_read32bitInt(const unsigned char* buffer)
embeddedartists 0:b567d56a59d7 320 {
embeddedartists 0:b567d56a59d7 321 return (buffer[0] << 24) | (buffer[1] << 16) | (buffer[2] << 8) | buffer[3];
embeddedartists 0:b567d56a59d7 322 }
embeddedartists 0:b567d56a59d7 323
embeddedartists 0:b567d56a59d7 324 #if defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)
embeddedartists 0:b567d56a59d7 325 /*buffer must have at least 4 allocated bytes available*/
embeddedartists 0:b567d56a59d7 326 static void lodepng_set32bitInt(unsigned char* buffer, unsigned value)
embeddedartists 0:b567d56a59d7 327 {
embeddedartists 0:b567d56a59d7 328 buffer[0] = (unsigned char)((value >> 24) & 0xff);
embeddedartists 0:b567d56a59d7 329 buffer[1] = (unsigned char)((value >> 16) & 0xff);
embeddedartists 0:b567d56a59d7 330 buffer[2] = (unsigned char)((value >> 8) & 0xff);
embeddedartists 0:b567d56a59d7 331 buffer[3] = (unsigned char)((value ) & 0xff);
embeddedartists 0:b567d56a59d7 332 }
embeddedartists 0:b567d56a59d7 333 #endif /*defined(LODEPNG_COMPILE_PNG) || defined(LODEPNG_COMPILE_ENCODER)*/
embeddedartists 0:b567d56a59d7 334
embeddedartists 0:b567d56a59d7 335 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 336 static void lodepng_add32bitInt(ucvector* buffer, unsigned value)
embeddedartists 0:b567d56a59d7 337 {
embeddedartists 0:b567d56a59d7 338 ucvector_resize(buffer, buffer->size + 4); /*todo: give error if resize failed*/
embeddedartists 0:b567d56a59d7 339 lodepng_set32bitInt(&buffer->data[buffer->size - 4], value);
embeddedartists 0:b567d56a59d7 340 }
embeddedartists 0:b567d56a59d7 341 #endif /*LODEPNG_COMPILE_ENCODER*/
embeddedartists 0:b567d56a59d7 342
embeddedartists 0:b567d56a59d7 343 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 344 /* / File IO / */
embeddedartists 0:b567d56a59d7 345 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 346
embeddedartists 0:b567d56a59d7 347 #ifdef LODEPNG_COMPILE_DISK
embeddedartists 0:b567d56a59d7 348
embeddedartists 0:b567d56a59d7 349 unsigned lodepng_load_file(unsigned char** out, size_t* outsize, const char* filename)
embeddedartists 0:b567d56a59d7 350 {
embeddedartists 0:b567d56a59d7 351 FILE* file;
embeddedartists 0:b567d56a59d7 352 long size;
embeddedartists 0:b567d56a59d7 353
embeddedartists 0:b567d56a59d7 354 /*provide some proper output values if error will happen*/
embeddedartists 0:b567d56a59d7 355 *out = 0;
embeddedartists 0:b567d56a59d7 356 *outsize = 0;
embeddedartists 0:b567d56a59d7 357
embeddedartists 0:b567d56a59d7 358 file = fopen(filename, "rb");
embeddedartists 0:b567d56a59d7 359 if(!file) return 78;
embeddedartists 0:b567d56a59d7 360
embeddedartists 0:b567d56a59d7 361 /*get filesize:*/
embeddedartists 0:b567d56a59d7 362 fseek(file , 0 , SEEK_END);
embeddedartists 0:b567d56a59d7 363 size = ftell(file);
embeddedartists 0:b567d56a59d7 364 rewind(file);
embeddedartists 0:b567d56a59d7 365
embeddedartists 0:b567d56a59d7 366 /*read contents of the file into the vector*/
embeddedartists 0:b567d56a59d7 367 *outsize = 0;
embeddedartists 0:b567d56a59d7 368 *out = (unsigned char*)lodepng_malloc((size_t)size);
embeddedartists 0:b567d56a59d7 369 if(size && (*out)) (*outsize) = fread(*out, 1, (size_t)size, file);
embeddedartists 0:b567d56a59d7 370
embeddedartists 0:b567d56a59d7 371 fclose(file);
embeddedartists 0:b567d56a59d7 372 if(!(*out) && size) return 83; /*the above malloc failed*/
embeddedartists 0:b567d56a59d7 373 return 0;
embeddedartists 0:b567d56a59d7 374 }
embeddedartists 0:b567d56a59d7 375
embeddedartists 0:b567d56a59d7 376 /*write given buffer to the file, overwriting the file, it doesn't append to it.*/
embeddedartists 0:b567d56a59d7 377 unsigned lodepng_save_file(const unsigned char* buffer, size_t buffersize, const char* filename)
embeddedartists 0:b567d56a59d7 378 {
embeddedartists 0:b567d56a59d7 379 FILE* file;
embeddedartists 0:b567d56a59d7 380 file = fopen(filename, "wb" );
embeddedartists 0:b567d56a59d7 381 if(!file) return 79;
embeddedartists 0:b567d56a59d7 382 fwrite((char*)buffer , 1 , buffersize, file);
embeddedartists 0:b567d56a59d7 383 fclose(file);
embeddedartists 0:b567d56a59d7 384 return 0;
embeddedartists 0:b567d56a59d7 385 }
embeddedartists 0:b567d56a59d7 386
embeddedartists 0:b567d56a59d7 387 #endif /*LODEPNG_COMPILE_DISK*/
embeddedartists 0:b567d56a59d7 388
embeddedartists 0:b567d56a59d7 389 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 390 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 391 /* // End of common code and tools. Begin of Zlib related code. // */
embeddedartists 0:b567d56a59d7 392 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 393 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 394
embeddedartists 0:b567d56a59d7 395 #ifdef LODEPNG_COMPILE_ZLIB
embeddedartists 0:b567d56a59d7 396 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 397 /*TODO: this ignores potential out of memory errors*/
embeddedartists 0:b567d56a59d7 398 #define addBitToStream(/*size_t**/ bitpointer, /*ucvector**/ bitstream, /*unsigned char*/ bit)\
embeddedartists 0:b567d56a59d7 399 {\
embeddedartists 0:b567d56a59d7 400 /*add a new byte at the end*/\
embeddedartists 0:b567d56a59d7 401 if(((*bitpointer) & 7) == 0) ucvector_push_back(bitstream, (unsigned char)0);\
embeddedartists 0:b567d56a59d7 402 /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/\
embeddedartists 0:b567d56a59d7 403 (bitstream->data[bitstream->size - 1]) |= (bit << ((*bitpointer) & 0x7));\
embeddedartists 0:b567d56a59d7 404 (*bitpointer)++;\
embeddedartists 0:b567d56a59d7 405 }
embeddedartists 0:b567d56a59d7 406
embeddedartists 0:b567d56a59d7 407 static void addBitsToStream(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
embeddedartists 0:b567d56a59d7 408 {
embeddedartists 0:b567d56a59d7 409 size_t i;
embeddedartists 0:b567d56a59d7 410 for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> i) & 1));
embeddedartists 0:b567d56a59d7 411 }
embeddedartists 0:b567d56a59d7 412
embeddedartists 0:b567d56a59d7 413 static void addBitsToStreamReversed(size_t* bitpointer, ucvector* bitstream, unsigned value, size_t nbits)
embeddedartists 0:b567d56a59d7 414 {
embeddedartists 0:b567d56a59d7 415 size_t i;
embeddedartists 0:b567d56a59d7 416 for(i = 0; i < nbits; i++) addBitToStream(bitpointer, bitstream, (unsigned char)((value >> (nbits - 1 - i)) & 1));
embeddedartists 0:b567d56a59d7 417 }
embeddedartists 0:b567d56a59d7 418 #endif /*LODEPNG_COMPILE_ENCODER*/
embeddedartists 0:b567d56a59d7 419
embeddedartists 0:b567d56a59d7 420 #ifdef LODEPNG_COMPILE_DECODER
embeddedartists 0:b567d56a59d7 421
embeddedartists 0:b567d56a59d7 422 #define READBIT(bitpointer, bitstream) ((bitstream[bitpointer >> 3] >> (bitpointer & 0x7)) & (unsigned char)1)
embeddedartists 0:b567d56a59d7 423
embeddedartists 0:b567d56a59d7 424 static unsigned char readBitFromStream(size_t* bitpointer, const unsigned char* bitstream)
embeddedartists 0:b567d56a59d7 425 {
embeddedartists 0:b567d56a59d7 426 unsigned char result = (unsigned char)(READBIT(*bitpointer, bitstream));
embeddedartists 0:b567d56a59d7 427 (*bitpointer)++;
embeddedartists 0:b567d56a59d7 428 return result;
embeddedartists 0:b567d56a59d7 429 }
embeddedartists 0:b567d56a59d7 430
embeddedartists 0:b567d56a59d7 431 static unsigned readBitsFromStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
embeddedartists 0:b567d56a59d7 432 {
embeddedartists 0:b567d56a59d7 433 unsigned result = 0, i;
embeddedartists 0:b567d56a59d7 434 for(i = 0; i < nbits; i++)
embeddedartists 0:b567d56a59d7 435 {
embeddedartists 0:b567d56a59d7 436 result += ((unsigned)READBIT(*bitpointer, bitstream)) << i;
embeddedartists 0:b567d56a59d7 437 (*bitpointer)++;
embeddedartists 0:b567d56a59d7 438 }
embeddedartists 0:b567d56a59d7 439 return result;
embeddedartists 0:b567d56a59d7 440 }
embeddedartists 0:b567d56a59d7 441 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 442
embeddedartists 0:b567d56a59d7 443 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 444 /* / Deflate - Huffman / */
embeddedartists 0:b567d56a59d7 445 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 446
embeddedartists 0:b567d56a59d7 447 #define FIRST_LENGTH_CODE_INDEX 257
embeddedartists 0:b567d56a59d7 448 #define LAST_LENGTH_CODE_INDEX 285
embeddedartists 0:b567d56a59d7 449 /*256 literals, the end code, some length codes, and 2 unused codes*/
embeddedartists 0:b567d56a59d7 450 #define NUM_DEFLATE_CODE_SYMBOLS 288
embeddedartists 0:b567d56a59d7 451 /*the distance codes have their own symbols, 30 used, 2 unused*/
embeddedartists 0:b567d56a59d7 452 #define NUM_DISTANCE_SYMBOLS 32
embeddedartists 0:b567d56a59d7 453 /*the code length codes. 0-15: code lengths, 16: copy previous 3-6 times, 17: 3-10 zeros, 18: 11-138 zeros*/
embeddedartists 0:b567d56a59d7 454 #define NUM_CODE_LENGTH_CODES 19
embeddedartists 0:b567d56a59d7 455
embeddedartists 0:b567d56a59d7 456 /*the base lengths represented by codes 257-285*/
embeddedartists 0:b567d56a59d7 457 static const unsigned LENGTHBASE[29]
embeddedartists 0:b567d56a59d7 458 = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
embeddedartists 0:b567d56a59d7 459 67, 83, 99, 115, 131, 163, 195, 227, 258};
embeddedartists 0:b567d56a59d7 460
embeddedartists 0:b567d56a59d7 461 /*the extra bits used by codes 257-285 (added to base length)*/
embeddedartists 0:b567d56a59d7 462 static const unsigned LENGTHEXTRA[29]
embeddedartists 0:b567d56a59d7 463 = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
embeddedartists 0:b567d56a59d7 464 4, 4, 4, 4, 5, 5, 5, 5, 0};
embeddedartists 0:b567d56a59d7 465
embeddedartists 0:b567d56a59d7 466 /*the base backwards distances (the bits of distance codes appear after length codes and use their own huffman tree)*/
embeddedartists 0:b567d56a59d7 467 static const unsigned DISTANCEBASE[30]
embeddedartists 0:b567d56a59d7 468 = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
embeddedartists 0:b567d56a59d7 469 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
embeddedartists 0:b567d56a59d7 470
embeddedartists 0:b567d56a59d7 471 /*the extra bits of backwards distances (added to base)*/
embeddedartists 0:b567d56a59d7 472 static const unsigned DISTANCEEXTRA[30]
embeddedartists 0:b567d56a59d7 473 = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8,
embeddedartists 0:b567d56a59d7 474 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13};
embeddedartists 0:b567d56a59d7 475
embeddedartists 0:b567d56a59d7 476 /*the order in which "code length alphabet code lengths" are stored, out of this
embeddedartists 0:b567d56a59d7 477 the huffman tree of the dynamic huffman tree lengths is generated*/
embeddedartists 0:b567d56a59d7 478 static const unsigned CLCL_ORDER[NUM_CODE_LENGTH_CODES]
embeddedartists 0:b567d56a59d7 479 = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
embeddedartists 0:b567d56a59d7 480
embeddedartists 0:b567d56a59d7 481 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 482
embeddedartists 0:b567d56a59d7 483 /*
embeddedartists 0:b567d56a59d7 484 Huffman tree struct, containing multiple representations of the tree
embeddedartists 0:b567d56a59d7 485 */
embeddedartists 0:b567d56a59d7 486 typedef struct HuffmanTree
embeddedartists 0:b567d56a59d7 487 {
embeddedartists 0:b567d56a59d7 488 unsigned* tree2d;
embeddedartists 0:b567d56a59d7 489 unsigned* tree1d;
embeddedartists 0:b567d56a59d7 490 unsigned* lengths; /*the lengths of the codes of the 1d-tree*/
embeddedartists 0:b567d56a59d7 491 unsigned maxbitlen; /*maximum number of bits a single code can get*/
embeddedartists 0:b567d56a59d7 492 unsigned numcodes; /*number of symbols in the alphabet = number of codes*/
embeddedartists 0:b567d56a59d7 493 } HuffmanTree;
embeddedartists 0:b567d56a59d7 494
embeddedartists 0:b567d56a59d7 495 /*function used for debug purposes to draw the tree in ascii art with C++*/
embeddedartists 0:b567d56a59d7 496 /*
embeddedartists 0:b567d56a59d7 497 static void HuffmanTree_draw(HuffmanTree* tree)
embeddedartists 0:b567d56a59d7 498 {
embeddedartists 0:b567d56a59d7 499 std::cout << "tree. length: " << tree->numcodes << " maxbitlen: " << tree->maxbitlen << std::endl;
embeddedartists 0:b567d56a59d7 500 for(size_t i = 0; i < tree->tree1d.size; i++)
embeddedartists 0:b567d56a59d7 501 {
embeddedartists 0:b567d56a59d7 502 if(tree->lengths.data[i])
embeddedartists 0:b567d56a59d7 503 std::cout << i << " " << tree->tree1d.data[i] << " " << tree->lengths.data[i] << std::endl;
embeddedartists 0:b567d56a59d7 504 }
embeddedartists 0:b567d56a59d7 505 std::cout << std::endl;
embeddedartists 0:b567d56a59d7 506 }*/
embeddedartists 0:b567d56a59d7 507
embeddedartists 0:b567d56a59d7 508 static void HuffmanTree_init(HuffmanTree* tree)
embeddedartists 0:b567d56a59d7 509 {
embeddedartists 0:b567d56a59d7 510 tree->tree2d = 0;
embeddedartists 0:b567d56a59d7 511 tree->tree1d = 0;
embeddedartists 0:b567d56a59d7 512 tree->lengths = 0;
embeddedartists 0:b567d56a59d7 513 }
embeddedartists 0:b567d56a59d7 514
embeddedartists 0:b567d56a59d7 515 static void HuffmanTree_cleanup(HuffmanTree* tree)
embeddedartists 0:b567d56a59d7 516 {
embeddedartists 0:b567d56a59d7 517 lodepng_free(tree->tree2d);
embeddedartists 0:b567d56a59d7 518 lodepng_free(tree->tree1d);
embeddedartists 0:b567d56a59d7 519 lodepng_free(tree->lengths);
embeddedartists 0:b567d56a59d7 520 }
embeddedartists 0:b567d56a59d7 521
embeddedartists 0:b567d56a59d7 522 /*the tree representation used by the decoder. return value is error*/
embeddedartists 0:b567d56a59d7 523 static unsigned HuffmanTree_make2DTree(HuffmanTree* tree)
embeddedartists 0:b567d56a59d7 524 {
embeddedartists 0:b567d56a59d7 525 unsigned nodefilled = 0; /*up to which node it is filled*/
embeddedartists 0:b567d56a59d7 526 unsigned treepos = 0; /*position in the tree (1 of the numcodes columns)*/
embeddedartists 0:b567d56a59d7 527 unsigned n, i;
embeddedartists 0:b567d56a59d7 528
embeddedartists 0:b567d56a59d7 529 tree->tree2d = (unsigned*)lodepng_malloc(tree->numcodes * 2 * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 530 if(!tree->tree2d) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 531
embeddedartists 0:b567d56a59d7 532 /*
embeddedartists 0:b567d56a59d7 533 convert tree1d[] to tree2d[][]. In the 2D array, a value of 32767 means
embeddedartists 0:b567d56a59d7 534 uninited, a value >= numcodes is an address to another bit, a value < numcodes
embeddedartists 0:b567d56a59d7 535 is a code. The 2 rows are the 2 possible bit values (0 or 1), there are as
embeddedartists 0:b567d56a59d7 536 many columns as codes - 1.
embeddedartists 0:b567d56a59d7 537 A good huffmann tree has N * 2 - 1 nodes, of which N - 1 are internal nodes.
embeddedartists 0:b567d56a59d7 538 Here, the internal nodes are stored (what their 0 and 1 option point to).
embeddedartists 0:b567d56a59d7 539 There is only memory for such good tree currently, if there are more nodes
embeddedartists 0:b567d56a59d7 540 (due to too long length codes), error 55 will happen
embeddedartists 0:b567d56a59d7 541 */
embeddedartists 0:b567d56a59d7 542 for(n = 0; n < tree->numcodes * 2; n++)
embeddedartists 0:b567d56a59d7 543 {
embeddedartists 0:b567d56a59d7 544 tree->tree2d[n] = 32767; /*32767 here means the tree2d isn't filled there yet*/
embeddedartists 0:b567d56a59d7 545 }
embeddedartists 0:b567d56a59d7 546
embeddedartists 0:b567d56a59d7 547 for(n = 0; n < tree->numcodes; n++) /*the codes*/
embeddedartists 0:b567d56a59d7 548 {
embeddedartists 0:b567d56a59d7 549 for(i = 0; i < tree->lengths[n]; i++) /*the bits for this code*/
embeddedartists 0:b567d56a59d7 550 {
embeddedartists 0:b567d56a59d7 551 unsigned char bit = (unsigned char)((tree->tree1d[n] >> (tree->lengths[n] - i - 1)) & 1);
embeddedartists 0:b567d56a59d7 552 if(treepos > tree->numcodes - 2) return 55; /*oversubscribed, see comment in lodepng_error_text*/
embeddedartists 0:b567d56a59d7 553 if(tree->tree2d[2 * treepos + bit] == 32767) /*not yet filled in*/
embeddedartists 0:b567d56a59d7 554 {
embeddedartists 0:b567d56a59d7 555 if(i + 1 == tree->lengths[n]) /*last bit*/
embeddedartists 0:b567d56a59d7 556 {
embeddedartists 0:b567d56a59d7 557 tree->tree2d[2 * treepos + bit] = n; /*put the current code in it*/
embeddedartists 0:b567d56a59d7 558 treepos = 0;
embeddedartists 0:b567d56a59d7 559 }
embeddedartists 0:b567d56a59d7 560 else
embeddedartists 0:b567d56a59d7 561 {
embeddedartists 0:b567d56a59d7 562 /*put address of the next step in here, first that address has to be found of course
embeddedartists 0:b567d56a59d7 563 (it's just nodefilled + 1)...*/
embeddedartists 0:b567d56a59d7 564 nodefilled++;
embeddedartists 0:b567d56a59d7 565 /*addresses encoded with numcodes added to it*/
embeddedartists 0:b567d56a59d7 566 tree->tree2d[2 * treepos + bit] = nodefilled + tree->numcodes;
embeddedartists 0:b567d56a59d7 567 treepos = nodefilled;
embeddedartists 0:b567d56a59d7 568 }
embeddedartists 0:b567d56a59d7 569 }
embeddedartists 0:b567d56a59d7 570 else treepos = tree->tree2d[2 * treepos + bit] - tree->numcodes;
embeddedartists 0:b567d56a59d7 571 }
embeddedartists 0:b567d56a59d7 572 }
embeddedartists 0:b567d56a59d7 573
embeddedartists 0:b567d56a59d7 574 for(n = 0; n < tree->numcodes * 2; n++)
embeddedartists 0:b567d56a59d7 575 {
embeddedartists 0:b567d56a59d7 576 if(tree->tree2d[n] == 32767) tree->tree2d[n] = 0; /*remove possible remaining 32767's*/
embeddedartists 0:b567d56a59d7 577 }
embeddedartists 0:b567d56a59d7 578
embeddedartists 0:b567d56a59d7 579 return 0;
embeddedartists 0:b567d56a59d7 580 }
embeddedartists 0:b567d56a59d7 581
embeddedartists 0:b567d56a59d7 582 /*
embeddedartists 0:b567d56a59d7 583 Second step for the ...makeFromLengths and ...makeFromFrequencies functions.
embeddedartists 0:b567d56a59d7 584 numcodes, lengths and maxbitlen must already be filled in correctly. return
embeddedartists 0:b567d56a59d7 585 value is error.
embeddedartists 0:b567d56a59d7 586 */
embeddedartists 0:b567d56a59d7 587 static unsigned HuffmanTree_makeFromLengths2(HuffmanTree* tree)
embeddedartists 0:b567d56a59d7 588 {
embeddedartists 0:b567d56a59d7 589 uivector blcount;
embeddedartists 0:b567d56a59d7 590 uivector nextcode;
embeddedartists 0:b567d56a59d7 591 unsigned bits, n, error = 0;
embeddedartists 0:b567d56a59d7 592
embeddedartists 0:b567d56a59d7 593 uivector_init(&blcount);
embeddedartists 0:b567d56a59d7 594 uivector_init(&nextcode);
embeddedartists 0:b567d56a59d7 595
embeddedartists 0:b567d56a59d7 596 tree->tree1d = (unsigned*)lodepng_malloc(tree->numcodes * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 597 if(!tree->tree1d) error = 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 598
embeddedartists 0:b567d56a59d7 599 if(!uivector_resizev(&blcount, tree->maxbitlen + 1, 0)
embeddedartists 0:b567d56a59d7 600 || !uivector_resizev(&nextcode, tree->maxbitlen + 1, 0))
embeddedartists 0:b567d56a59d7 601 error = 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 602
embeddedartists 0:b567d56a59d7 603 if(!error)
embeddedartists 0:b567d56a59d7 604 {
embeddedartists 0:b567d56a59d7 605 /*step 1: count number of instances of each code length*/
embeddedartists 0:b567d56a59d7 606 for(bits = 0; bits < tree->numcodes; bits++) blcount.data[tree->lengths[bits]]++;
embeddedartists 0:b567d56a59d7 607 /*step 2: generate the nextcode values*/
embeddedartists 0:b567d56a59d7 608 for(bits = 1; bits <= tree->maxbitlen; bits++)
embeddedartists 0:b567d56a59d7 609 {
embeddedartists 0:b567d56a59d7 610 nextcode.data[bits] = (nextcode.data[bits - 1] + blcount.data[bits - 1]) << 1;
embeddedartists 0:b567d56a59d7 611 }
embeddedartists 0:b567d56a59d7 612 /*step 3: generate all the codes*/
embeddedartists 0:b567d56a59d7 613 for(n = 0; n < tree->numcodes; n++)
embeddedartists 0:b567d56a59d7 614 {
embeddedartists 0:b567d56a59d7 615 if(tree->lengths[n] != 0) tree->tree1d[n] = nextcode.data[tree->lengths[n]]++;
embeddedartists 0:b567d56a59d7 616 }
embeddedartists 0:b567d56a59d7 617 }
embeddedartists 0:b567d56a59d7 618
embeddedartists 0:b567d56a59d7 619 uivector_cleanup(&blcount);
embeddedartists 0:b567d56a59d7 620 uivector_cleanup(&nextcode);
embeddedartists 0:b567d56a59d7 621
embeddedartists 0:b567d56a59d7 622 if(!error) return HuffmanTree_make2DTree(tree);
embeddedartists 0:b567d56a59d7 623 else return error;
embeddedartists 0:b567d56a59d7 624 }
embeddedartists 0:b567d56a59d7 625
embeddedartists 0:b567d56a59d7 626 /*
embeddedartists 0:b567d56a59d7 627 given the code lengths (as stored in the PNG file), generate the tree as defined
embeddedartists 0:b567d56a59d7 628 by Deflate. maxbitlen is the maximum bits that a code in the tree can have.
embeddedartists 0:b567d56a59d7 629 return value is error.
embeddedartists 0:b567d56a59d7 630 */
embeddedartists 0:b567d56a59d7 631 static unsigned HuffmanTree_makeFromLengths(HuffmanTree* tree, const unsigned* bitlen,
embeddedartists 0:b567d56a59d7 632 size_t numcodes, unsigned maxbitlen)
embeddedartists 0:b567d56a59d7 633 {
embeddedartists 0:b567d56a59d7 634 unsigned i;
embeddedartists 0:b567d56a59d7 635 tree->lengths = (unsigned*)lodepng_malloc(numcodes * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 636 if(!tree->lengths) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 637 for(i = 0; i < numcodes; i++) tree->lengths[i] = bitlen[i];
embeddedartists 0:b567d56a59d7 638 tree->numcodes = (unsigned)numcodes; /*number of symbols*/
embeddedartists 0:b567d56a59d7 639 tree->maxbitlen = maxbitlen;
embeddedartists 0:b567d56a59d7 640 return HuffmanTree_makeFromLengths2(tree);
embeddedartists 0:b567d56a59d7 641 }
embeddedartists 0:b567d56a59d7 642
embeddedartists 0:b567d56a59d7 643 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 644
embeddedartists 0:b567d56a59d7 645 /*
embeddedartists 0:b567d56a59d7 646 A coin, this is the terminology used for the package-merge algorithm and the
embeddedartists 0:b567d56a59d7 647 coin collector's problem. This is used to generate the huffman tree.
embeddedartists 0:b567d56a59d7 648 A coin can be multiple coins (when they're merged)
embeddedartists 0:b567d56a59d7 649 */
embeddedartists 0:b567d56a59d7 650 typedef struct Coin
embeddedartists 0:b567d56a59d7 651 {
embeddedartists 0:b567d56a59d7 652 uivector symbols;
embeddedartists 0:b567d56a59d7 653 float weight; /*the sum of all weights in this coin*/
embeddedartists 0:b567d56a59d7 654 } Coin;
embeddedartists 0:b567d56a59d7 655
embeddedartists 0:b567d56a59d7 656 static void coin_init(Coin* c)
embeddedartists 0:b567d56a59d7 657 {
embeddedartists 0:b567d56a59d7 658 uivector_init(&c->symbols);
embeddedartists 0:b567d56a59d7 659 }
embeddedartists 0:b567d56a59d7 660
embeddedartists 0:b567d56a59d7 661 /*argument c is void* so that this dtor can be given as function pointer to the vector resize function*/
embeddedartists 0:b567d56a59d7 662 static void coin_cleanup(void* c)
embeddedartists 0:b567d56a59d7 663 {
embeddedartists 0:b567d56a59d7 664 uivector_cleanup(&((Coin*)c)->symbols);
embeddedartists 0:b567d56a59d7 665 }
embeddedartists 0:b567d56a59d7 666
embeddedartists 0:b567d56a59d7 667 static void coin_copy(Coin* c1, const Coin* c2)
embeddedartists 0:b567d56a59d7 668 {
embeddedartists 0:b567d56a59d7 669 c1->weight = c2->weight;
embeddedartists 0:b567d56a59d7 670 uivector_copy(&c1->symbols, &c2->symbols);
embeddedartists 0:b567d56a59d7 671 }
embeddedartists 0:b567d56a59d7 672
embeddedartists 0:b567d56a59d7 673 static void add_coins(Coin* c1, const Coin* c2)
embeddedartists 0:b567d56a59d7 674 {
embeddedartists 0:b567d56a59d7 675 size_t i;
embeddedartists 0:b567d56a59d7 676 for(i = 0; i < c2->symbols.size; i++) uivector_push_back(&c1->symbols, c2->symbols.data[i]);
embeddedartists 0:b567d56a59d7 677 c1->weight += c2->weight;
embeddedartists 0:b567d56a59d7 678 }
embeddedartists 0:b567d56a59d7 679
embeddedartists 0:b567d56a59d7 680 static void init_coins(Coin* coins, size_t num)
embeddedartists 0:b567d56a59d7 681 {
embeddedartists 0:b567d56a59d7 682 size_t i;
embeddedartists 0:b567d56a59d7 683 for(i = 0; i < num; i++) coin_init(&coins[i]);
embeddedartists 0:b567d56a59d7 684 }
embeddedartists 0:b567d56a59d7 685
embeddedartists 0:b567d56a59d7 686 static void cleanup_coins(Coin* coins, size_t num)
embeddedartists 0:b567d56a59d7 687 {
embeddedartists 0:b567d56a59d7 688 size_t i;
embeddedartists 0:b567d56a59d7 689 for(i = 0; i < num; i++) coin_cleanup(&coins[i]);
embeddedartists 0:b567d56a59d7 690 }
embeddedartists 0:b567d56a59d7 691
embeddedartists 0:b567d56a59d7 692 static int coin_compare(const void* a, const void* b) {
embeddedartists 0:b567d56a59d7 693 float wa = ((const Coin*)a)->weight;
embeddedartists 0:b567d56a59d7 694 float wb = ((const Coin*)b)->weight;
embeddedartists 0:b567d56a59d7 695 return wa > wb ? 1 : wa < wb ? -1 : 0;
embeddedartists 0:b567d56a59d7 696 }
embeddedartists 0:b567d56a59d7 697
embeddedartists 0:b567d56a59d7 698 static unsigned append_symbol_coins(Coin* coins, const unsigned* frequencies, unsigned numcodes, size_t sum)
embeddedartists 0:b567d56a59d7 699 {
embeddedartists 0:b567d56a59d7 700 unsigned i;
embeddedartists 0:b567d56a59d7 701 unsigned j = 0; /*index of present symbols*/
embeddedartists 0:b567d56a59d7 702 for(i = 0; i < numcodes; i++)
embeddedartists 0:b567d56a59d7 703 {
embeddedartists 0:b567d56a59d7 704 if(frequencies[i] != 0) /*only include symbols that are present*/
embeddedartists 0:b567d56a59d7 705 {
embeddedartists 0:b567d56a59d7 706 coins[j].weight = frequencies[i] / (float)sum;
embeddedartists 0:b567d56a59d7 707 uivector_push_back(&coins[j].symbols, i);
embeddedartists 0:b567d56a59d7 708 j++;
embeddedartists 0:b567d56a59d7 709 }
embeddedartists 0:b567d56a59d7 710 }
embeddedartists 0:b567d56a59d7 711 return 0;
embeddedartists 0:b567d56a59d7 712 }
embeddedartists 0:b567d56a59d7 713
embeddedartists 0:b567d56a59d7 714 unsigned lodepng_huffman_code_lengths(unsigned* lengths, const unsigned* frequencies,
embeddedartists 0:b567d56a59d7 715 size_t numcodes, unsigned maxbitlen)
embeddedartists 0:b567d56a59d7 716 {
embeddedartists 0:b567d56a59d7 717 unsigned i, j;
embeddedartists 0:b567d56a59d7 718 size_t sum = 0, numpresent = 0;
embeddedartists 0:b567d56a59d7 719 unsigned error = 0;
embeddedartists 0:b567d56a59d7 720 Coin* coins; /*the coins of the currently calculated row*/
embeddedartists 0:b567d56a59d7 721 Coin* prev_row; /*the previous row of coins*/
embeddedartists 0:b567d56a59d7 722 unsigned numcoins;
embeddedartists 0:b567d56a59d7 723 unsigned coinmem;
embeddedartists 0:b567d56a59d7 724
embeddedartists 0:b567d56a59d7 725 if(numcodes == 0) return 80; /*error: a tree of 0 symbols is not supposed to be made*/
embeddedartists 0:b567d56a59d7 726
embeddedartists 0:b567d56a59d7 727 for(i = 0; i < numcodes; i++)
embeddedartists 0:b567d56a59d7 728 {
embeddedartists 0:b567d56a59d7 729 if(frequencies[i] > 0)
embeddedartists 0:b567d56a59d7 730 {
embeddedartists 0:b567d56a59d7 731 numpresent++;
embeddedartists 0:b567d56a59d7 732 sum += frequencies[i];
embeddedartists 0:b567d56a59d7 733 }
embeddedartists 0:b567d56a59d7 734 }
embeddedartists 0:b567d56a59d7 735
embeddedartists 0:b567d56a59d7 736 for(i = 0; i < numcodes; i++) lengths[i] = 0;
embeddedartists 0:b567d56a59d7 737
embeddedartists 0:b567d56a59d7 738 /*ensure at least two present symbols. There should be at least one symbol
embeddedartists 0:b567d56a59d7 739 according to RFC 1951 section 3.2.7. To decoders incorrectly require two. To
embeddedartists 0:b567d56a59d7 740 make these work as well ensure there are at least two symbols. The
embeddedartists 0:b567d56a59d7 741 Package-Merge code below also doesn't work correctly if there's only one
embeddedartists 0:b567d56a59d7 742 symbol, it'd give it the theoritical 0 bits but in practice zlib wants 1 bit*/
embeddedartists 0:b567d56a59d7 743 if(numpresent == 0)
embeddedartists 0:b567d56a59d7 744 {
embeddedartists 0:b567d56a59d7 745 lengths[0] = lengths[1] = 1; /*note that for RFC 1951 section 3.2.7, only lengths[0] = 1 is needed*/
embeddedartists 0:b567d56a59d7 746 }
embeddedartists 0:b567d56a59d7 747 else if(numpresent == 1)
embeddedartists 0:b567d56a59d7 748 {
embeddedartists 0:b567d56a59d7 749 for(i = 0; i < numcodes; i++)
embeddedartists 0:b567d56a59d7 750 {
embeddedartists 0:b567d56a59d7 751 if(frequencies[i])
embeddedartists 0:b567d56a59d7 752 {
embeddedartists 0:b567d56a59d7 753 lengths[i] = 1;
embeddedartists 0:b567d56a59d7 754 lengths[i == 0 ? 1 : 0] = 1;
embeddedartists 0:b567d56a59d7 755 break;
embeddedartists 0:b567d56a59d7 756 }
embeddedartists 0:b567d56a59d7 757 }
embeddedartists 0:b567d56a59d7 758 }
embeddedartists 0:b567d56a59d7 759 else
embeddedartists 0:b567d56a59d7 760 {
embeddedartists 0:b567d56a59d7 761 /*Package-Merge algorithm represented by coin collector's problem
embeddedartists 0:b567d56a59d7 762 For every symbol, maxbitlen coins will be created*/
embeddedartists 0:b567d56a59d7 763
embeddedartists 0:b567d56a59d7 764 coinmem = numpresent * 2; /*max amount of coins needed with the current algo*/
embeddedartists 0:b567d56a59d7 765 coins = (Coin*)lodepng_malloc(sizeof(Coin) * coinmem);
embeddedartists 0:b567d56a59d7 766 prev_row = (Coin*)lodepng_malloc(sizeof(Coin) * coinmem);
embeddedartists 0:b567d56a59d7 767 if(!coins || !prev_row)
embeddedartists 0:b567d56a59d7 768 {
embeddedartists 0:b567d56a59d7 769 lodepng_free(coins);
embeddedartists 0:b567d56a59d7 770 lodepng_free(prev_row);
embeddedartists 0:b567d56a59d7 771 return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 772 }
embeddedartists 0:b567d56a59d7 773 init_coins(coins, coinmem);
embeddedartists 0:b567d56a59d7 774 init_coins(prev_row, coinmem);
embeddedartists 0:b567d56a59d7 775
embeddedartists 0:b567d56a59d7 776 /*first row, lowest denominator*/
embeddedartists 0:b567d56a59d7 777 error = append_symbol_coins(coins, frequencies, numcodes, sum);
embeddedartists 0:b567d56a59d7 778 numcoins = numpresent;
embeddedartists 0:b567d56a59d7 779 qsort(coins, numcoins, sizeof(Coin), coin_compare);
embeddedartists 0:b567d56a59d7 780 if(!error)
embeddedartists 0:b567d56a59d7 781 {
embeddedartists 0:b567d56a59d7 782 unsigned numprev = 0;
embeddedartists 0:b567d56a59d7 783 for(j = 1; j <= maxbitlen && !error; j++) /*each of the remaining rows*/
embeddedartists 0:b567d56a59d7 784 {
embeddedartists 0:b567d56a59d7 785 unsigned tempnum;
embeddedartists 0:b567d56a59d7 786 Coin* tempcoins;
embeddedartists 0:b567d56a59d7 787 /*swap prev_row and coins, and their amounts*/
embeddedartists 0:b567d56a59d7 788 tempcoins = prev_row; prev_row = coins; coins = tempcoins;
embeddedartists 0:b567d56a59d7 789 tempnum = numprev; numprev = numcoins; numcoins = tempnum;
embeddedartists 0:b567d56a59d7 790
embeddedartists 0:b567d56a59d7 791 cleanup_coins(coins, numcoins);
embeddedartists 0:b567d56a59d7 792 init_coins(coins, numcoins);
embeddedartists 0:b567d56a59d7 793
embeddedartists 0:b567d56a59d7 794 numcoins = 0;
embeddedartists 0:b567d56a59d7 795
embeddedartists 0:b567d56a59d7 796 /*fill in the merged coins of the previous row*/
embeddedartists 0:b567d56a59d7 797 for(i = 0; i + 1 < numprev; i += 2)
embeddedartists 0:b567d56a59d7 798 {
embeddedartists 0:b567d56a59d7 799 /*merge prev_row[i] and prev_row[i + 1] into new coin*/
embeddedartists 0:b567d56a59d7 800 Coin* coin = &coins[numcoins++];
embeddedartists 0:b567d56a59d7 801 coin_copy(coin, &prev_row[i]);
embeddedartists 0:b567d56a59d7 802 add_coins(coin, &prev_row[i + 1]);
embeddedartists 0:b567d56a59d7 803 }
embeddedartists 0:b567d56a59d7 804 /*fill in all the original symbols again*/
embeddedartists 0:b567d56a59d7 805 if(j < maxbitlen)
embeddedartists 0:b567d56a59d7 806 {
embeddedartists 0:b567d56a59d7 807 error = append_symbol_coins(coins + numcoins, frequencies, numcodes, sum);
embeddedartists 0:b567d56a59d7 808 numcoins += numpresent;
embeddedartists 0:b567d56a59d7 809 }
embeddedartists 0:b567d56a59d7 810 qsort(coins, numcoins, sizeof(Coin), coin_compare);
embeddedartists 0:b567d56a59d7 811 }
embeddedartists 0:b567d56a59d7 812 }
embeddedartists 0:b567d56a59d7 813
embeddedartists 0:b567d56a59d7 814 if(!error)
embeddedartists 0:b567d56a59d7 815 {
embeddedartists 0:b567d56a59d7 816 /*calculate the lenghts of each symbol, as the amount of times a coin of each symbol is used*/
embeddedartists 0:b567d56a59d7 817 for(i = 0; i < numpresent - 1; i++)
embeddedartists 0:b567d56a59d7 818 {
embeddedartists 0:b567d56a59d7 819 Coin* coin = &coins[i];
embeddedartists 0:b567d56a59d7 820 for(j = 0; j < coin->symbols.size; j++) lengths[coin->symbols.data[j]]++;
embeddedartists 0:b567d56a59d7 821 }
embeddedartists 0:b567d56a59d7 822 }
embeddedartists 0:b567d56a59d7 823
embeddedartists 0:b567d56a59d7 824 cleanup_coins(coins, coinmem);
embeddedartists 0:b567d56a59d7 825 lodepng_free(coins);
embeddedartists 0:b567d56a59d7 826 cleanup_coins(prev_row, coinmem);
embeddedartists 0:b567d56a59d7 827 lodepng_free(prev_row);
embeddedartists 0:b567d56a59d7 828 }
embeddedartists 0:b567d56a59d7 829
embeddedartists 0:b567d56a59d7 830 return error;
embeddedartists 0:b567d56a59d7 831 }
embeddedartists 0:b567d56a59d7 832
embeddedartists 0:b567d56a59d7 833 /*Create the Huffman tree given the symbol frequencies*/
embeddedartists 0:b567d56a59d7 834 static unsigned HuffmanTree_makeFromFrequencies(HuffmanTree* tree, const unsigned* frequencies,
embeddedartists 0:b567d56a59d7 835 size_t mincodes, size_t numcodes, unsigned maxbitlen)
embeddedartists 0:b567d56a59d7 836 {
embeddedartists 0:b567d56a59d7 837 unsigned error = 0;
embeddedartists 0:b567d56a59d7 838 while(!frequencies[numcodes - 1] && numcodes > mincodes) numcodes--; /*trim zeroes*/
embeddedartists 0:b567d56a59d7 839 tree->maxbitlen = maxbitlen;
embeddedartists 0:b567d56a59d7 840 tree->numcodes = (unsigned)numcodes; /*number of symbols*/
embeddedartists 0:b567d56a59d7 841 tree->lengths = (unsigned*)lodepng_realloc(tree->lengths, numcodes * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 842 if(!tree->lengths) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 843 /*initialize all lengths to 0*/
embeddedartists 0:b567d56a59d7 844 memset(tree->lengths, 0, numcodes * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 845
embeddedartists 0:b567d56a59d7 846 error = lodepng_huffman_code_lengths(tree->lengths, frequencies, numcodes, maxbitlen);
embeddedartists 0:b567d56a59d7 847 if(!error) error = HuffmanTree_makeFromLengths2(tree);
embeddedartists 0:b567d56a59d7 848 return error;
embeddedartists 0:b567d56a59d7 849 }
embeddedartists 0:b567d56a59d7 850
embeddedartists 0:b567d56a59d7 851 static unsigned HuffmanTree_getCode(const HuffmanTree* tree, unsigned index)
embeddedartists 0:b567d56a59d7 852 {
embeddedartists 0:b567d56a59d7 853 return tree->tree1d[index];
embeddedartists 0:b567d56a59d7 854 }
embeddedartists 0:b567d56a59d7 855
embeddedartists 0:b567d56a59d7 856 static unsigned HuffmanTree_getLength(const HuffmanTree* tree, unsigned index)
embeddedartists 0:b567d56a59d7 857 {
embeddedartists 0:b567d56a59d7 858 return tree->lengths[index];
embeddedartists 0:b567d56a59d7 859 }
embeddedartists 0:b567d56a59d7 860 #endif /*LODEPNG_COMPILE_ENCODER*/
embeddedartists 0:b567d56a59d7 861
embeddedartists 0:b567d56a59d7 862 /*get the literal and length code tree of a deflated block with fixed tree, as per the deflate specification*/
embeddedartists 0:b567d56a59d7 863 static unsigned generateFixedLitLenTree(HuffmanTree* tree)
embeddedartists 0:b567d56a59d7 864 {
embeddedartists 0:b567d56a59d7 865 unsigned i, error = 0;
embeddedartists 0:b567d56a59d7 866 unsigned* bitlen = (unsigned*)lodepng_malloc(NUM_DEFLATE_CODE_SYMBOLS * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 867 if(!bitlen) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 868
embeddedartists 0:b567d56a59d7 869 /*288 possible codes: 0-255=literals, 256=endcode, 257-285=lengthcodes, 286-287=unused*/
embeddedartists 0:b567d56a59d7 870 for(i = 0; i <= 143; i++) bitlen[i] = 8;
embeddedartists 0:b567d56a59d7 871 for(i = 144; i <= 255; i++) bitlen[i] = 9;
embeddedartists 0:b567d56a59d7 872 for(i = 256; i <= 279; i++) bitlen[i] = 7;
embeddedartists 0:b567d56a59d7 873 for(i = 280; i <= 287; i++) bitlen[i] = 8;
embeddedartists 0:b567d56a59d7 874
embeddedartists 0:b567d56a59d7 875 error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DEFLATE_CODE_SYMBOLS, 15);
embeddedartists 0:b567d56a59d7 876
embeddedartists 0:b567d56a59d7 877 lodepng_free(bitlen);
embeddedartists 0:b567d56a59d7 878 return error;
embeddedartists 0:b567d56a59d7 879 }
embeddedartists 0:b567d56a59d7 880
embeddedartists 0:b567d56a59d7 881 /*get the distance code tree of a deflated block with fixed tree, as specified in the deflate specification*/
embeddedartists 0:b567d56a59d7 882 static unsigned generateFixedDistanceTree(HuffmanTree* tree)
embeddedartists 0:b567d56a59d7 883 {
embeddedartists 0:b567d56a59d7 884 unsigned i, error = 0;
embeddedartists 0:b567d56a59d7 885 unsigned* bitlen = (unsigned*)lodepng_malloc(NUM_DISTANCE_SYMBOLS * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 886 if(!bitlen) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 887
embeddedartists 0:b567d56a59d7 888 /*there are 32 distance codes, but 30-31 are unused*/
embeddedartists 0:b567d56a59d7 889 for(i = 0; i < NUM_DISTANCE_SYMBOLS; i++) bitlen[i] = 5;
embeddedartists 0:b567d56a59d7 890 error = HuffmanTree_makeFromLengths(tree, bitlen, NUM_DISTANCE_SYMBOLS, 15);
embeddedartists 0:b567d56a59d7 891
embeddedartists 0:b567d56a59d7 892 lodepng_free(bitlen);
embeddedartists 0:b567d56a59d7 893 return error;
embeddedartists 0:b567d56a59d7 894 }
embeddedartists 0:b567d56a59d7 895
embeddedartists 0:b567d56a59d7 896 #ifdef LODEPNG_COMPILE_DECODER
embeddedartists 0:b567d56a59d7 897
embeddedartists 0:b567d56a59d7 898 /*
embeddedartists 0:b567d56a59d7 899 returns the code, or (unsigned)(-1) if error happened
embeddedartists 0:b567d56a59d7 900 inbitlength is the length of the complete buffer, in bits (so its byte length times 8)
embeddedartists 0:b567d56a59d7 901 */
embeddedartists 0:b567d56a59d7 902 static unsigned huffmanDecodeSymbol(const unsigned char* in, size_t* bp,
embeddedartists 0:b567d56a59d7 903 const HuffmanTree* codetree, size_t inbitlength)
embeddedartists 0:b567d56a59d7 904 {
embeddedartists 0:b567d56a59d7 905 unsigned treepos = 0, ct;
embeddedartists 0:b567d56a59d7 906 for(;;)
embeddedartists 0:b567d56a59d7 907 {
embeddedartists 0:b567d56a59d7 908 if(*bp >= inbitlength) return (unsigned)(-1); /*error: end of input memory reached without endcode*/
embeddedartists 0:b567d56a59d7 909 /*
embeddedartists 0:b567d56a59d7 910 decode the symbol from the tree. The "readBitFromStream" code is inlined in
embeddedartists 0:b567d56a59d7 911 the expression below because this is the biggest bottleneck while decoding
embeddedartists 0:b567d56a59d7 912 */
embeddedartists 0:b567d56a59d7 913 ct = codetree->tree2d[(treepos << 1) + READBIT(*bp, in)];
embeddedartists 0:b567d56a59d7 914 (*bp)++;
embeddedartists 0:b567d56a59d7 915 if(ct < codetree->numcodes) return ct; /*the symbol is decoded, return it*/
embeddedartists 0:b567d56a59d7 916 else treepos = ct - codetree->numcodes; /*symbol not yet decoded, instead move tree position*/
embeddedartists 0:b567d56a59d7 917
embeddedartists 0:b567d56a59d7 918 if(treepos >= codetree->numcodes) return (unsigned)(-1); /*error: it appeared outside the codetree*/
embeddedartists 0:b567d56a59d7 919 }
embeddedartists 0:b567d56a59d7 920 }
embeddedartists 0:b567d56a59d7 921 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 922
embeddedartists 0:b567d56a59d7 923 #ifdef LODEPNG_COMPILE_DECODER
embeddedartists 0:b567d56a59d7 924
embeddedartists 0:b567d56a59d7 925 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 926 /* / Inflator (Decompressor) / */
embeddedartists 0:b567d56a59d7 927 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 928
embeddedartists 0:b567d56a59d7 929 /*get the tree of a deflated block with fixed tree, as specified in the deflate specification*/
embeddedartists 0:b567d56a59d7 930 static void getTreeInflateFixed(HuffmanTree* tree_ll, HuffmanTree* tree_d)
embeddedartists 0:b567d56a59d7 931 {
embeddedartists 0:b567d56a59d7 932 /*TODO: check for out of memory errors*/
embeddedartists 0:b567d56a59d7 933 generateFixedLitLenTree(tree_ll);
embeddedartists 0:b567d56a59d7 934 generateFixedDistanceTree(tree_d);
embeddedartists 0:b567d56a59d7 935 }
embeddedartists 0:b567d56a59d7 936
embeddedartists 0:b567d56a59d7 937 /*get the tree of a deflated block with dynamic tree, the tree itself is also Huffman compressed with a known tree*/
embeddedartists 0:b567d56a59d7 938 static unsigned getTreeInflateDynamic(HuffmanTree* tree_ll, HuffmanTree* tree_d,
embeddedartists 0:b567d56a59d7 939 const unsigned char* in, size_t* bp, size_t inlength)
embeddedartists 0:b567d56a59d7 940 {
embeddedartists 0:b567d56a59d7 941 /*make sure that length values that aren't filled in will be 0, or a wrong tree will be generated*/
embeddedartists 0:b567d56a59d7 942 unsigned error = 0;
embeddedartists 0:b567d56a59d7 943 unsigned n, HLIT, HDIST, HCLEN, i;
embeddedartists 0:b567d56a59d7 944 size_t inbitlength = inlength * 8;
embeddedartists 0:b567d56a59d7 945
embeddedartists 0:b567d56a59d7 946 /*see comments in deflateDynamic for explanation of the context and these variables, it is analogous*/
embeddedartists 0:b567d56a59d7 947 unsigned* bitlen_ll = 0; /*lit,len code lengths*/
embeddedartists 0:b567d56a59d7 948 unsigned* bitlen_d = 0; /*dist code lengths*/
embeddedartists 0:b567d56a59d7 949 /*code length code lengths ("clcl"), the bit lengths of the huffman tree used to compress bitlen_ll and bitlen_d*/
embeddedartists 0:b567d56a59d7 950 unsigned* bitlen_cl = 0;
embeddedartists 0:b567d56a59d7 951 HuffmanTree tree_cl; /*the code tree for code length codes (the huffman tree for compressed huffman trees)*/
embeddedartists 0:b567d56a59d7 952
embeddedartists 0:b567d56a59d7 953 if((*bp) >> 3 >= inlength - 2) return 49; /*error: the bit pointer is or will go past the memory*/
embeddedartists 0:b567d56a59d7 954
embeddedartists 0:b567d56a59d7 955 /*number of literal/length codes + 257. Unlike the spec, the value 257 is added to it here already*/
embeddedartists 0:b567d56a59d7 956 HLIT = readBitsFromStream(bp, in, 5) + 257;
embeddedartists 0:b567d56a59d7 957 /*number of distance codes. Unlike the spec, the value 1 is added to it here already*/
embeddedartists 0:b567d56a59d7 958 HDIST = readBitsFromStream(bp, in, 5) + 1;
embeddedartists 0:b567d56a59d7 959 /*number of code length codes. Unlike the spec, the value 4 is added to it here already*/
embeddedartists 0:b567d56a59d7 960 HCLEN = readBitsFromStream(bp, in, 4) + 4;
embeddedartists 0:b567d56a59d7 961
embeddedartists 0:b567d56a59d7 962 HuffmanTree_init(&tree_cl);
embeddedartists 0:b567d56a59d7 963
embeddedartists 0:b567d56a59d7 964 while(!error)
embeddedartists 0:b567d56a59d7 965 {
embeddedartists 0:b567d56a59d7 966 /*read the code length codes out of 3 * (amount of code length codes) bits*/
embeddedartists 0:b567d56a59d7 967
embeddedartists 0:b567d56a59d7 968 bitlen_cl = (unsigned*)lodepng_malloc(NUM_CODE_LENGTH_CODES * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 969 if(!bitlen_cl) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 970
embeddedartists 0:b567d56a59d7 971 for(i = 0; i < NUM_CODE_LENGTH_CODES; i++)
embeddedartists 0:b567d56a59d7 972 {
embeddedartists 0:b567d56a59d7 973 if(i < HCLEN) bitlen_cl[CLCL_ORDER[i]] = readBitsFromStream(bp, in, 3);
embeddedartists 0:b567d56a59d7 974 else bitlen_cl[CLCL_ORDER[i]] = 0; /*if not, it must stay 0*/
embeddedartists 0:b567d56a59d7 975 }
embeddedartists 0:b567d56a59d7 976
embeddedartists 0:b567d56a59d7 977 error = HuffmanTree_makeFromLengths(&tree_cl, bitlen_cl, NUM_CODE_LENGTH_CODES, 7);
embeddedartists 0:b567d56a59d7 978 if(error) break;
embeddedartists 0:b567d56a59d7 979
embeddedartists 0:b567d56a59d7 980 /*now we can use this tree to read the lengths for the tree that this function will return*/
embeddedartists 0:b567d56a59d7 981 bitlen_ll = (unsigned*)lodepng_malloc(NUM_DEFLATE_CODE_SYMBOLS * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 982 bitlen_d = (unsigned*)lodepng_malloc(NUM_DISTANCE_SYMBOLS * sizeof(unsigned));
embeddedartists 0:b567d56a59d7 983 if(!bitlen_ll || !bitlen_d) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 984 for(i = 0; i < NUM_DEFLATE_CODE_SYMBOLS; i++) bitlen_ll[i] = 0;
embeddedartists 0:b567d56a59d7 985 for(i = 0; i < NUM_DISTANCE_SYMBOLS; i++) bitlen_d[i] = 0;
embeddedartists 0:b567d56a59d7 986
embeddedartists 0:b567d56a59d7 987 /*i is the current symbol we're reading in the part that contains the code lengths of lit/len and dist codes*/
embeddedartists 0:b567d56a59d7 988 i = 0;
embeddedartists 0:b567d56a59d7 989 while(i < HLIT + HDIST)
embeddedartists 0:b567d56a59d7 990 {
embeddedartists 0:b567d56a59d7 991 unsigned code = huffmanDecodeSymbol(in, bp, &tree_cl, inbitlength);
embeddedartists 0:b567d56a59d7 992 if(code <= 15) /*a length code*/
embeddedartists 0:b567d56a59d7 993 {
embeddedartists 0:b567d56a59d7 994 if(i < HLIT) bitlen_ll[i] = code;
embeddedartists 0:b567d56a59d7 995 else bitlen_d[i - HLIT] = code;
embeddedartists 0:b567d56a59d7 996 i++;
embeddedartists 0:b567d56a59d7 997 }
embeddedartists 0:b567d56a59d7 998 else if(code == 16) /*repeat previous*/
embeddedartists 0:b567d56a59d7 999 {
embeddedartists 0:b567d56a59d7 1000 unsigned replength = 3; /*read in the 2 bits that indicate repeat length (3-6)*/
embeddedartists 0:b567d56a59d7 1001 unsigned value; /*set value to the previous code*/
embeddedartists 0:b567d56a59d7 1002
embeddedartists 0:b567d56a59d7 1003 if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
embeddedartists 0:b567d56a59d7 1004 if (i == 0) ERROR_BREAK(54); /*can't repeat previous if i is 0*/
embeddedartists 0:b567d56a59d7 1005
embeddedartists 0:b567d56a59d7 1006 replength += readBitsFromStream(bp, in, 2);
embeddedartists 0:b567d56a59d7 1007
embeddedartists 0:b567d56a59d7 1008 if(i < HLIT + 1) value = bitlen_ll[i - 1];
embeddedartists 0:b567d56a59d7 1009 else value = bitlen_d[i - HLIT - 1];
embeddedartists 0:b567d56a59d7 1010 /*repeat this value in the next lengths*/
embeddedartists 0:b567d56a59d7 1011 for(n = 0; n < replength; n++)
embeddedartists 0:b567d56a59d7 1012 {
embeddedartists 0:b567d56a59d7 1013 if(i >= HLIT + HDIST) ERROR_BREAK(13); /*error: i is larger than the amount of codes*/
embeddedartists 0:b567d56a59d7 1014 if(i < HLIT) bitlen_ll[i] = value;
embeddedartists 0:b567d56a59d7 1015 else bitlen_d[i - HLIT] = value;
embeddedartists 0:b567d56a59d7 1016 i++;
embeddedartists 0:b567d56a59d7 1017 }
embeddedartists 0:b567d56a59d7 1018 }
embeddedartists 0:b567d56a59d7 1019 else if(code == 17) /*repeat "0" 3-10 times*/
embeddedartists 0:b567d56a59d7 1020 {
embeddedartists 0:b567d56a59d7 1021 unsigned replength = 3; /*read in the bits that indicate repeat length*/
embeddedartists 0:b567d56a59d7 1022 if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
embeddedartists 0:b567d56a59d7 1023
embeddedartists 0:b567d56a59d7 1024 replength += readBitsFromStream(bp, in, 3);
embeddedartists 0:b567d56a59d7 1025
embeddedartists 0:b567d56a59d7 1026 /*repeat this value in the next lengths*/
embeddedartists 0:b567d56a59d7 1027 for(n = 0; n < replength; n++)
embeddedartists 0:b567d56a59d7 1028 {
embeddedartists 0:b567d56a59d7 1029 if(i >= HLIT + HDIST) ERROR_BREAK(14); /*error: i is larger than the amount of codes*/
embeddedartists 0:b567d56a59d7 1030
embeddedartists 0:b567d56a59d7 1031 if(i < HLIT) bitlen_ll[i] = 0;
embeddedartists 0:b567d56a59d7 1032 else bitlen_d[i - HLIT] = 0;
embeddedartists 0:b567d56a59d7 1033 i++;
embeddedartists 0:b567d56a59d7 1034 }
embeddedartists 0:b567d56a59d7 1035 }
embeddedartists 0:b567d56a59d7 1036 else if(code == 18) /*repeat "0" 11-138 times*/
embeddedartists 0:b567d56a59d7 1037 {
embeddedartists 0:b567d56a59d7 1038 unsigned replength = 11; /*read in the bits that indicate repeat length*/
embeddedartists 0:b567d56a59d7 1039 if(*bp >= inbitlength) ERROR_BREAK(50); /*error, bit pointer jumps past memory*/
embeddedartists 0:b567d56a59d7 1040
embeddedartists 0:b567d56a59d7 1041 replength += readBitsFromStream(bp, in, 7);
embeddedartists 0:b567d56a59d7 1042
embeddedartists 0:b567d56a59d7 1043 /*repeat this value in the next lengths*/
embeddedartists 0:b567d56a59d7 1044 for(n = 0; n < replength; n++)
embeddedartists 0:b567d56a59d7 1045 {
embeddedartists 0:b567d56a59d7 1046 if(i >= HLIT + HDIST) ERROR_BREAK(15); /*error: i is larger than the amount of codes*/
embeddedartists 0:b567d56a59d7 1047
embeddedartists 0:b567d56a59d7 1048 if(i < HLIT) bitlen_ll[i] = 0;
embeddedartists 0:b567d56a59d7 1049 else bitlen_d[i - HLIT] = 0;
embeddedartists 0:b567d56a59d7 1050 i++;
embeddedartists 0:b567d56a59d7 1051 }
embeddedartists 0:b567d56a59d7 1052 }
embeddedartists 0:b567d56a59d7 1053 else /*if(code == (unsigned)(-1))*/ /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
embeddedartists 0:b567d56a59d7 1054 {
embeddedartists 0:b567d56a59d7 1055 if(code == (unsigned)(-1))
embeddedartists 0:b567d56a59d7 1056 {
embeddedartists 0:b567d56a59d7 1057 /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
embeddedartists 0:b567d56a59d7 1058 (10=no endcode, 11=wrong jump outside of tree)*/
embeddedartists 0:b567d56a59d7 1059 error = (*bp) > inbitlength ? 10 : 11;
embeddedartists 0:b567d56a59d7 1060 }
embeddedartists 0:b567d56a59d7 1061 else error = 16; /*unexisting code, this can never happen*/
embeddedartists 0:b567d56a59d7 1062 break;
embeddedartists 0:b567d56a59d7 1063 }
embeddedartists 0:b567d56a59d7 1064 }
embeddedartists 0:b567d56a59d7 1065 if(error) break;
embeddedartists 0:b567d56a59d7 1066
embeddedartists 0:b567d56a59d7 1067 if(bitlen_ll[256] == 0) ERROR_BREAK(64); /*the length of the end code 256 must be larger than 0*/
embeddedartists 0:b567d56a59d7 1068
embeddedartists 0:b567d56a59d7 1069 /*now we've finally got HLIT and HDIST, so generate the code trees, and the function is done*/
embeddedartists 0:b567d56a59d7 1070 error = HuffmanTree_makeFromLengths(tree_ll, bitlen_ll, NUM_DEFLATE_CODE_SYMBOLS, 15);
embeddedartists 0:b567d56a59d7 1071 if(error) break;
embeddedartists 0:b567d56a59d7 1072 error = HuffmanTree_makeFromLengths(tree_d, bitlen_d, NUM_DISTANCE_SYMBOLS, 15);
embeddedartists 0:b567d56a59d7 1073
embeddedartists 0:b567d56a59d7 1074 break; /*end of error-while*/
embeddedartists 0:b567d56a59d7 1075 }
embeddedartists 0:b567d56a59d7 1076
embeddedartists 0:b567d56a59d7 1077 lodepng_free(bitlen_cl);
embeddedartists 0:b567d56a59d7 1078 lodepng_free(bitlen_ll);
embeddedartists 0:b567d56a59d7 1079 lodepng_free(bitlen_d);
embeddedartists 0:b567d56a59d7 1080 HuffmanTree_cleanup(&tree_cl);
embeddedartists 0:b567d56a59d7 1081
embeddedartists 0:b567d56a59d7 1082 return error;
embeddedartists 0:b567d56a59d7 1083 }
embeddedartists 0:b567d56a59d7 1084
embeddedartists 0:b567d56a59d7 1085 /*inflate a block with dynamic of fixed Huffman tree*/
embeddedartists 0:b567d56a59d7 1086 static unsigned inflateHuffmanBlock(ucvector* out, const unsigned char* in, size_t* bp,
embeddedartists 0:b567d56a59d7 1087 size_t* pos, size_t inlength, unsigned btype)
embeddedartists 0:b567d56a59d7 1088 {
embeddedartists 0:b567d56a59d7 1089 unsigned error = 0;
embeddedartists 0:b567d56a59d7 1090 HuffmanTree tree_ll; /*the huffman tree for literal and length codes*/
embeddedartists 0:b567d56a59d7 1091 HuffmanTree tree_d; /*the huffman tree for distance codes*/
embeddedartists 0:b567d56a59d7 1092 size_t inbitlength = inlength * 8;
embeddedartists 0:b567d56a59d7 1093
embeddedartists 0:b567d56a59d7 1094 HuffmanTree_init(&tree_ll);
embeddedartists 0:b567d56a59d7 1095 HuffmanTree_init(&tree_d);
embeddedartists 0:b567d56a59d7 1096
embeddedartists 0:b567d56a59d7 1097 if(btype == 1) getTreeInflateFixed(&tree_ll, &tree_d);
embeddedartists 0:b567d56a59d7 1098 else if(btype == 2) error = getTreeInflateDynamic(&tree_ll, &tree_d, in, bp, inlength);
embeddedartists 0:b567d56a59d7 1099
embeddedartists 0:b567d56a59d7 1100 while(!error) /*decode all symbols until end reached, breaks at end code*/
embeddedartists 0:b567d56a59d7 1101 {
embeddedartists 0:b567d56a59d7 1102 /*code_ll is literal, length or end code*/
embeddedartists 0:b567d56a59d7 1103 unsigned code_ll = huffmanDecodeSymbol(in, bp, &tree_ll, inbitlength);
embeddedartists 0:b567d56a59d7 1104 if(code_ll <= 255) /*literal symbol*/
embeddedartists 0:b567d56a59d7 1105 {
embeddedartists 0:b567d56a59d7 1106 if((*pos) >= out->size)
embeddedartists 0:b567d56a59d7 1107 {
embeddedartists 0:b567d56a59d7 1108 /*reserve more room at once*/
embeddedartists 0:b567d56a59d7 1109 if(!ucvector_resize(out, ((*pos) + 1) * 2)) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1110 }
embeddedartists 0:b567d56a59d7 1111 out->data[(*pos)] = (unsigned char)(code_ll);
embeddedartists 0:b567d56a59d7 1112 (*pos)++;
embeddedartists 0:b567d56a59d7 1113 }
embeddedartists 0:b567d56a59d7 1114 else if(code_ll >= FIRST_LENGTH_CODE_INDEX && code_ll <= LAST_LENGTH_CODE_INDEX) /*length code*/
embeddedartists 0:b567d56a59d7 1115 {
embeddedartists 0:b567d56a59d7 1116 unsigned code_d, distance;
embeddedartists 0:b567d56a59d7 1117 unsigned numextrabits_l, numextrabits_d; /*extra bits for length and distance*/
embeddedartists 0:b567d56a59d7 1118 size_t start, forward, backward, length;
embeddedartists 0:b567d56a59d7 1119
embeddedartists 0:b567d56a59d7 1120 /*part 1: get length base*/
embeddedartists 0:b567d56a59d7 1121 length = LENGTHBASE[code_ll - FIRST_LENGTH_CODE_INDEX];
embeddedartists 0:b567d56a59d7 1122
embeddedartists 0:b567d56a59d7 1123 /*part 2: get extra bits and add the value of that to length*/
embeddedartists 0:b567d56a59d7 1124 numextrabits_l = LENGTHEXTRA[code_ll - FIRST_LENGTH_CODE_INDEX];
embeddedartists 0:b567d56a59d7 1125 if(*bp >= inbitlength) ERROR_BREAK(51); /*error, bit pointer will jump past memory*/
embeddedartists 0:b567d56a59d7 1126 length += readBitsFromStream(bp, in, numextrabits_l);
embeddedartists 0:b567d56a59d7 1127
embeddedartists 0:b567d56a59d7 1128 /*part 3: get distance code*/
embeddedartists 0:b567d56a59d7 1129 code_d = huffmanDecodeSymbol(in, bp, &tree_d, inbitlength);
embeddedartists 0:b567d56a59d7 1130 if(code_d > 29)
embeddedartists 0:b567d56a59d7 1131 {
embeddedartists 0:b567d56a59d7 1132 if(code_ll == (unsigned)(-1)) /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
embeddedartists 0:b567d56a59d7 1133 {
embeddedartists 0:b567d56a59d7 1134 /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
embeddedartists 0:b567d56a59d7 1135 (10=no endcode, 11=wrong jump outside of tree)*/
embeddedartists 0:b567d56a59d7 1136 error = (*bp) > inlength * 8 ? 10 : 11;
embeddedartists 0:b567d56a59d7 1137 }
embeddedartists 0:b567d56a59d7 1138 else error = 18; /*error: invalid distance code (30-31 are never used)*/
embeddedartists 0:b567d56a59d7 1139 break;
embeddedartists 0:b567d56a59d7 1140 }
embeddedartists 0:b567d56a59d7 1141 distance = DISTANCEBASE[code_d];
embeddedartists 0:b567d56a59d7 1142
embeddedartists 0:b567d56a59d7 1143 /*part 4: get extra bits from distance*/
embeddedartists 0:b567d56a59d7 1144 numextrabits_d = DISTANCEEXTRA[code_d];
embeddedartists 0:b567d56a59d7 1145 if(*bp >= inbitlength) ERROR_BREAK(51); /*error, bit pointer will jump past memory*/
embeddedartists 0:b567d56a59d7 1146
embeddedartists 0:b567d56a59d7 1147 distance += readBitsFromStream(bp, in, numextrabits_d);
embeddedartists 0:b567d56a59d7 1148
embeddedartists 0:b567d56a59d7 1149 /*part 5: fill in all the out[n] values based on the length and dist*/
embeddedartists 0:b567d56a59d7 1150 start = (*pos);
embeddedartists 0:b567d56a59d7 1151 if(distance > start) ERROR_BREAK(52); /*too long backward distance*/
embeddedartists 0:b567d56a59d7 1152 backward = start - distance;
embeddedartists 0:b567d56a59d7 1153 if((*pos) + length >= out->size)
embeddedartists 0:b567d56a59d7 1154 {
embeddedartists 0:b567d56a59d7 1155 /*reserve more room at once*/
embeddedartists 0:b567d56a59d7 1156 if(!ucvector_resize(out, ((*pos) + length) * 2)) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1157 }
embeddedartists 0:b567d56a59d7 1158
embeddedartists 0:b567d56a59d7 1159 for(forward = 0; forward < length; forward++)
embeddedartists 0:b567d56a59d7 1160 {
embeddedartists 0:b567d56a59d7 1161 out->data[(*pos)] = out->data[backward];
embeddedartists 0:b567d56a59d7 1162 (*pos)++;
embeddedartists 0:b567d56a59d7 1163 backward++;
embeddedartists 0:b567d56a59d7 1164 if(backward >= start) backward = start - distance;
embeddedartists 0:b567d56a59d7 1165 }
embeddedartists 0:b567d56a59d7 1166 }
embeddedartists 0:b567d56a59d7 1167 else if(code_ll == 256)
embeddedartists 0:b567d56a59d7 1168 {
embeddedartists 0:b567d56a59d7 1169 break; /*end code, break the loop*/
embeddedartists 0:b567d56a59d7 1170 }
embeddedartists 0:b567d56a59d7 1171 else /*if(code == (unsigned)(-1))*/ /*huffmanDecodeSymbol returns (unsigned)(-1) in case of error*/
embeddedartists 0:b567d56a59d7 1172 {
embeddedartists 0:b567d56a59d7 1173 /*return error code 10 or 11 depending on the situation that happened in huffmanDecodeSymbol
embeddedartists 0:b567d56a59d7 1174 (10=no endcode, 11=wrong jump outside of tree)*/
embeddedartists 0:b567d56a59d7 1175 error = (*bp) > inlength * 8 ? 10 : 11;
embeddedartists 0:b567d56a59d7 1176 break;
embeddedartists 0:b567d56a59d7 1177 }
embeddedartists 0:b567d56a59d7 1178 }
embeddedartists 0:b567d56a59d7 1179
embeddedartists 0:b567d56a59d7 1180 HuffmanTree_cleanup(&tree_ll);
embeddedartists 0:b567d56a59d7 1181 HuffmanTree_cleanup(&tree_d);
embeddedartists 0:b567d56a59d7 1182
embeddedartists 0:b567d56a59d7 1183 return error;
embeddedartists 0:b567d56a59d7 1184 }
embeddedartists 0:b567d56a59d7 1185
embeddedartists 0:b567d56a59d7 1186 static unsigned inflateNoCompression(ucvector* out, const unsigned char* in, size_t* bp, size_t* pos, size_t inlength)
embeddedartists 0:b567d56a59d7 1187 {
embeddedartists 0:b567d56a59d7 1188 /*go to first boundary of byte*/
embeddedartists 0:b567d56a59d7 1189 size_t p;
embeddedartists 0:b567d56a59d7 1190 unsigned LEN, NLEN, n, error = 0;
embeddedartists 0:b567d56a59d7 1191 while(((*bp) & 0x7) != 0) (*bp)++;
embeddedartists 0:b567d56a59d7 1192 p = (*bp) / 8; /*byte position*/
embeddedartists 0:b567d56a59d7 1193
embeddedartists 0:b567d56a59d7 1194 /*read LEN (2 bytes) and NLEN (2 bytes)*/
embeddedartists 0:b567d56a59d7 1195 if(p >= inlength - 4) return 52; /*error, bit pointer will jump past memory*/
embeddedartists 0:b567d56a59d7 1196 LEN = in[p] + 256 * in[p + 1]; p += 2;
embeddedartists 0:b567d56a59d7 1197 NLEN = in[p] + 256 * in[p + 1]; p += 2;
embeddedartists 0:b567d56a59d7 1198
embeddedartists 0:b567d56a59d7 1199 /*check if 16-bit NLEN is really the one's complement of LEN*/
embeddedartists 0:b567d56a59d7 1200 if(LEN + NLEN != 65535) return 21; /*error: NLEN is not one's complement of LEN*/
embeddedartists 0:b567d56a59d7 1201
embeddedartists 0:b567d56a59d7 1202 if((*pos) + LEN >= out->size)
embeddedartists 0:b567d56a59d7 1203 {
embeddedartists 0:b567d56a59d7 1204 if(!ucvector_resize(out, (*pos) + LEN)) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 1205 }
embeddedartists 0:b567d56a59d7 1206
embeddedartists 0:b567d56a59d7 1207 /*read the literal data: LEN bytes are now stored in the out buffer*/
embeddedartists 0:b567d56a59d7 1208 if(p + LEN > inlength) return 23; /*error: reading outside of in buffer*/
embeddedartists 0:b567d56a59d7 1209 for(n = 0; n < LEN; n++) out->data[(*pos)++] = in[p++];
embeddedartists 0:b567d56a59d7 1210
embeddedartists 0:b567d56a59d7 1211 (*bp) = p * 8;
embeddedartists 0:b567d56a59d7 1212
embeddedartists 0:b567d56a59d7 1213 return error;
embeddedartists 0:b567d56a59d7 1214 }
embeddedartists 0:b567d56a59d7 1215
embeddedartists 0:b567d56a59d7 1216 static unsigned lodepng_inflatev(ucvector* out,
embeddedartists 0:b567d56a59d7 1217 const unsigned char* in, size_t insize,
embeddedartists 0:b567d56a59d7 1218 const LodePNGDecompressSettings* settings)
embeddedartists 0:b567d56a59d7 1219 {
embeddedartists 0:b567d56a59d7 1220 /*bit pointer in the "in" data, current byte is bp >> 3, current bit is bp & 0x7 (from lsb to msb of the byte)*/
embeddedartists 0:b567d56a59d7 1221 size_t bp = 0;
embeddedartists 0:b567d56a59d7 1222 unsigned BFINAL = 0;
embeddedartists 0:b567d56a59d7 1223 size_t pos = 0; /*byte position in the out buffer*/
embeddedartists 0:b567d56a59d7 1224
embeddedartists 0:b567d56a59d7 1225 unsigned error = 0;
embeddedartists 0:b567d56a59d7 1226
embeddedartists 0:b567d56a59d7 1227 (void)settings;
embeddedartists 0:b567d56a59d7 1228
embeddedartists 0:b567d56a59d7 1229 while(!BFINAL)
embeddedartists 0:b567d56a59d7 1230 {
embeddedartists 0:b567d56a59d7 1231 unsigned BTYPE;
embeddedartists 0:b567d56a59d7 1232 if(bp + 2 >= insize * 8) return 52; /*error, bit pointer will jump past memory*/
embeddedartists 0:b567d56a59d7 1233 BFINAL = readBitFromStream(&bp, in);
embeddedartists 0:b567d56a59d7 1234 BTYPE = 1 * readBitFromStream(&bp, in);
embeddedartists 0:b567d56a59d7 1235 BTYPE += 2 * readBitFromStream(&bp, in);
embeddedartists 0:b567d56a59d7 1236
embeddedartists 0:b567d56a59d7 1237 if(BTYPE == 3) return 20; /*error: invalid BTYPE*/
embeddedartists 0:b567d56a59d7 1238 else if(BTYPE == 0) error = inflateNoCompression(out, in, &bp, &pos, insize); /*no compression*/
embeddedartists 0:b567d56a59d7 1239 else error = inflateHuffmanBlock(out, in, &bp, &pos, insize, BTYPE); /*compression, BTYPE 01 or 10*/
embeddedartists 0:b567d56a59d7 1240
embeddedartists 0:b567d56a59d7 1241 if(error) return error;
embeddedartists 0:b567d56a59d7 1242 }
embeddedartists 0:b567d56a59d7 1243
embeddedartists 0:b567d56a59d7 1244 /*Only now we know the true size of out, resize it to that*/
embeddedartists 0:b567d56a59d7 1245 if(!ucvector_resize(out, pos)) error = 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 1246
embeddedartists 0:b567d56a59d7 1247 return error;
embeddedartists 0:b567d56a59d7 1248 }
embeddedartists 0:b567d56a59d7 1249
embeddedartists 0:b567d56a59d7 1250 unsigned lodepng_inflate(unsigned char** out, size_t* outsize,
embeddedartists 0:b567d56a59d7 1251 const unsigned char* in, size_t insize,
embeddedartists 0:b567d56a59d7 1252 const LodePNGDecompressSettings* settings)
embeddedartists 0:b567d56a59d7 1253 {
embeddedartists 0:b567d56a59d7 1254 unsigned error;
embeddedartists 0:b567d56a59d7 1255 ucvector v;
embeddedartists 0:b567d56a59d7 1256 ucvector_init_buffer(&v, *out, *outsize);
embeddedartists 0:b567d56a59d7 1257 error = lodepng_inflatev(&v, in, insize, settings);
embeddedartists 0:b567d56a59d7 1258 *out = v.data;
embeddedartists 0:b567d56a59d7 1259 *outsize = v.size;
embeddedartists 0:b567d56a59d7 1260 return error;
embeddedartists 0:b567d56a59d7 1261 }
embeddedartists 0:b567d56a59d7 1262
embeddedartists 0:b567d56a59d7 1263 static unsigned inflate(unsigned char** out, size_t* outsize,
embeddedartists 0:b567d56a59d7 1264 const unsigned char* in, size_t insize,
embeddedartists 0:b567d56a59d7 1265 const LodePNGDecompressSettings* settings)
embeddedartists 0:b567d56a59d7 1266 {
embeddedartists 0:b567d56a59d7 1267 if(settings->custom_inflate)
embeddedartists 0:b567d56a59d7 1268 {
embeddedartists 0:b567d56a59d7 1269 return settings->custom_inflate(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 1270 }
embeddedartists 0:b567d56a59d7 1271 else
embeddedartists 0:b567d56a59d7 1272 {
embeddedartists 0:b567d56a59d7 1273 return lodepng_inflate(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 1274 }
embeddedartists 0:b567d56a59d7 1275 }
embeddedartists 0:b567d56a59d7 1276
embeddedartists 0:b567d56a59d7 1277 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 1278
embeddedartists 0:b567d56a59d7 1279 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 1280
embeddedartists 0:b567d56a59d7 1281 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 1282 /* / Deflator (Compressor) / */
embeddedartists 0:b567d56a59d7 1283 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 1284
embeddedartists 0:b567d56a59d7 1285 static const size_t MAX_SUPPORTED_DEFLATE_LENGTH = 258;
embeddedartists 0:b567d56a59d7 1286
embeddedartists 0:b567d56a59d7 1287 /*bitlen is the size in bits of the code*/
embeddedartists 0:b567d56a59d7 1288 static void addHuffmanSymbol(size_t* bp, ucvector* compressed, unsigned code, unsigned bitlen)
embeddedartists 0:b567d56a59d7 1289 {
embeddedartists 0:b567d56a59d7 1290 addBitsToStreamReversed(bp, compressed, code, bitlen);
embeddedartists 0:b567d56a59d7 1291 }
embeddedartists 0:b567d56a59d7 1292
embeddedartists 0:b567d56a59d7 1293 /*search the index in the array, that has the largest value smaller than or equal to the given value,
embeddedartists 0:b567d56a59d7 1294 given array must be sorted (if no value is smaller, it returns the size of the given array)*/
embeddedartists 0:b567d56a59d7 1295 static size_t searchCodeIndex(const unsigned* array, size_t array_size, size_t value)
embeddedartists 0:b567d56a59d7 1296 {
embeddedartists 0:b567d56a59d7 1297 /*linear search implementation*/
embeddedartists 0:b567d56a59d7 1298 /*for(size_t i = 1; i < array_size; i++) if(array[i] > value) return i - 1;
embeddedartists 0:b567d56a59d7 1299 return array_size - 1;*/
embeddedartists 0:b567d56a59d7 1300
embeddedartists 0:b567d56a59d7 1301 /*binary search implementation (not that much faster) (precondition: array_size > 0)*/
embeddedartists 0:b567d56a59d7 1302 size_t left = 1;
embeddedartists 0:b567d56a59d7 1303 size_t right = array_size - 1;
embeddedartists 0:b567d56a59d7 1304 while(left <= right)
embeddedartists 0:b567d56a59d7 1305 {
embeddedartists 0:b567d56a59d7 1306 size_t mid = (left + right) / 2;
embeddedartists 0:b567d56a59d7 1307 if(array[mid] <= value) left = mid + 1; /*the value to find is more to the right*/
embeddedartists 0:b567d56a59d7 1308 else if(array[mid - 1] > value) right = mid - 1; /*the value to find is more to the left*/
embeddedartists 0:b567d56a59d7 1309 else return mid - 1;
embeddedartists 0:b567d56a59d7 1310 }
embeddedartists 0:b567d56a59d7 1311 return array_size - 1;
embeddedartists 0:b567d56a59d7 1312 }
embeddedartists 0:b567d56a59d7 1313
embeddedartists 0:b567d56a59d7 1314 static void addLengthDistance(uivector* values, size_t length, size_t distance)
embeddedartists 0:b567d56a59d7 1315 {
embeddedartists 0:b567d56a59d7 1316 /*values in encoded vector are those used by deflate:
embeddedartists 0:b567d56a59d7 1317 0-255: literal bytes
embeddedartists 0:b567d56a59d7 1318 256: end
embeddedartists 0:b567d56a59d7 1319 257-285: length/distance pair (length code, followed by extra length bits, distance code, extra distance bits)
embeddedartists 0:b567d56a59d7 1320 286-287: invalid*/
embeddedartists 0:b567d56a59d7 1321
embeddedartists 0:b567d56a59d7 1322 unsigned length_code = (unsigned)searchCodeIndex(LENGTHBASE, 29, length);
embeddedartists 0:b567d56a59d7 1323 unsigned extra_length = (unsigned)(length - LENGTHBASE[length_code]);
embeddedartists 0:b567d56a59d7 1324 unsigned dist_code = (unsigned)searchCodeIndex(DISTANCEBASE, 30, distance);
embeddedartists 0:b567d56a59d7 1325 unsigned extra_distance = (unsigned)(distance - DISTANCEBASE[dist_code]);
embeddedartists 0:b567d56a59d7 1326
embeddedartists 0:b567d56a59d7 1327 uivector_push_back(values, length_code + FIRST_LENGTH_CODE_INDEX);
embeddedartists 0:b567d56a59d7 1328 uivector_push_back(values, extra_length);
embeddedartists 0:b567d56a59d7 1329 uivector_push_back(values, dist_code);
embeddedartists 0:b567d56a59d7 1330 uivector_push_back(values, extra_distance);
embeddedartists 0:b567d56a59d7 1331 }
embeddedartists 0:b567d56a59d7 1332
embeddedartists 0:b567d56a59d7 1333 static const unsigned HASH_BIT_MASK = 65535;
embeddedartists 0:b567d56a59d7 1334 static const unsigned HASH_NUM_VALUES = 65536;
embeddedartists 0:b567d56a59d7 1335 static const unsigned HASH_NUM_CHARACTERS = 3;
embeddedartists 0:b567d56a59d7 1336 static const unsigned HASH_SHIFT = 2;
embeddedartists 0:b567d56a59d7 1337 /*
embeddedartists 0:b567d56a59d7 1338 The HASH_NUM_CHARACTERS value is used to make encoding faster by using longer
embeddedartists 0:b567d56a59d7 1339 sequences to generate a hash value from the stream bytes. Setting it to 3
embeddedartists 0:b567d56a59d7 1340 gives exactly the same compression as the brute force method, since deflate's
embeddedartists 0:b567d56a59d7 1341 run length encoding starts with lengths of 3. Setting it to higher values,
embeddedartists 0:b567d56a59d7 1342 like 6, can make the encoding faster (not always though!), but will cause the
embeddedartists 0:b567d56a59d7 1343 encoding to miss any length between 3 and this value, so that the compression
embeddedartists 0:b567d56a59d7 1344 may be worse (but this can vary too depending on the image, sometimes it is
embeddedartists 0:b567d56a59d7 1345 even a bit better instead).
embeddedartists 0:b567d56a59d7 1346 The HASH_NUM_VALUES is the amount of unique possible hash values that
embeddedartists 0:b567d56a59d7 1347 combinations of bytes can give, the higher it is the more memory is needed, but
embeddedartists 0:b567d56a59d7 1348 if it's too low the advantage of hashing is gone.
embeddedartists 0:b567d56a59d7 1349 */
embeddedartists 0:b567d56a59d7 1350
embeddedartists 0:b567d56a59d7 1351 typedef struct Hash
embeddedartists 0:b567d56a59d7 1352 {
embeddedartists 0:b567d56a59d7 1353 int* head; /*hash value to head circular pos*/
embeddedartists 0:b567d56a59d7 1354 int* val; /*circular pos to hash value*/
embeddedartists 0:b567d56a59d7 1355 /*circular pos to prev circular pos*/
embeddedartists 0:b567d56a59d7 1356 unsigned short* chain;
embeddedartists 0:b567d56a59d7 1357 unsigned short* zeros;
embeddedartists 0:b567d56a59d7 1358 } Hash;
embeddedartists 0:b567d56a59d7 1359
embeddedartists 0:b567d56a59d7 1360 static unsigned hash_init(Hash* hash, unsigned windowsize)
embeddedartists 0:b567d56a59d7 1361 {
embeddedartists 0:b567d56a59d7 1362 unsigned i;
embeddedartists 0:b567d56a59d7 1363 hash->head = (int*)lodepng_malloc(sizeof(int) * HASH_NUM_VALUES);
embeddedartists 0:b567d56a59d7 1364 hash->val = (int*)lodepng_malloc(sizeof(int) * windowsize);
embeddedartists 0:b567d56a59d7 1365 hash->chain = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
embeddedartists 0:b567d56a59d7 1366 hash->zeros = (unsigned short*)lodepng_malloc(sizeof(unsigned short) * windowsize);
embeddedartists 0:b567d56a59d7 1367
embeddedartists 0:b567d56a59d7 1368 if(!hash->head || !hash->val || !hash->chain || !hash->zeros) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 1369
embeddedartists 0:b567d56a59d7 1370 /*initialize hash table*/
embeddedartists 0:b567d56a59d7 1371 for(i = 0; i < HASH_NUM_VALUES; i++) hash->head[i] = -1;
embeddedartists 0:b567d56a59d7 1372 for(i = 0; i < windowsize; i++) hash->val[i] = -1;
embeddedartists 0:b567d56a59d7 1373 for(i = 0; i < windowsize; i++) hash->chain[i] = i; /*same value as index indicates uninitialized*/
embeddedartists 0:b567d56a59d7 1374
embeddedartists 0:b567d56a59d7 1375 return 0;
embeddedartists 0:b567d56a59d7 1376 }
embeddedartists 0:b567d56a59d7 1377
embeddedartists 0:b567d56a59d7 1378 static void hash_cleanup(Hash* hash)
embeddedartists 0:b567d56a59d7 1379 {
embeddedartists 0:b567d56a59d7 1380 lodepng_free(hash->head);
embeddedartists 0:b567d56a59d7 1381 lodepng_free(hash->val);
embeddedartists 0:b567d56a59d7 1382 lodepng_free(hash->chain);
embeddedartists 0:b567d56a59d7 1383 lodepng_free(hash->zeros);
embeddedartists 0:b567d56a59d7 1384 }
embeddedartists 0:b567d56a59d7 1385
embeddedartists 0:b567d56a59d7 1386 static unsigned getHash(const unsigned char* data, size_t size, size_t pos)
embeddedartists 0:b567d56a59d7 1387 {
embeddedartists 0:b567d56a59d7 1388 unsigned result = 0;
embeddedartists 0:b567d56a59d7 1389 if (HASH_NUM_CHARACTERS == 3 && pos + 2 < size) {
embeddedartists 0:b567d56a59d7 1390 result ^= (data[pos + 0] << (0 * HASH_SHIFT));
embeddedartists 0:b567d56a59d7 1391 result ^= (data[pos + 1] << (1 * HASH_SHIFT));
embeddedartists 0:b567d56a59d7 1392 result ^= (data[pos + 2] << (2 * HASH_SHIFT));
embeddedartists 0:b567d56a59d7 1393 } else {
embeddedartists 0:b567d56a59d7 1394 size_t amount, i;
embeddedartists 0:b567d56a59d7 1395 if(pos >= size) return 0;
embeddedartists 0:b567d56a59d7 1396 amount = HASH_NUM_CHARACTERS;
embeddedartists 0:b567d56a59d7 1397 if(pos + amount >= size) amount = size - pos;
embeddedartists 0:b567d56a59d7 1398 for(i = 0; i < amount; i++) result ^= (data[pos + i] << (i * HASH_SHIFT));
embeddedartists 0:b567d56a59d7 1399 }
embeddedartists 0:b567d56a59d7 1400 return result & HASH_BIT_MASK;
embeddedartists 0:b567d56a59d7 1401 }
embeddedartists 0:b567d56a59d7 1402
embeddedartists 0:b567d56a59d7 1403 static unsigned countZeros(const unsigned char* data, size_t size, size_t pos)
embeddedartists 0:b567d56a59d7 1404 {
embeddedartists 0:b567d56a59d7 1405 const unsigned char* start = data + pos;
embeddedartists 0:b567d56a59d7 1406 const unsigned char* end = start + MAX_SUPPORTED_DEFLATE_LENGTH;
embeddedartists 0:b567d56a59d7 1407 if(end > data + size) end = data + size;
embeddedartists 0:b567d56a59d7 1408 data = start;
embeddedartists 0:b567d56a59d7 1409 while (data != end && *data == 0) data++;
embeddedartists 0:b567d56a59d7 1410 /*subtracting two addresses returned as 32-bit number (max value is MAX_SUPPORTED_DEFLATE_LENGTH)*/
embeddedartists 0:b567d56a59d7 1411 return (unsigned)(data - start);
embeddedartists 0:b567d56a59d7 1412 }
embeddedartists 0:b567d56a59d7 1413
embeddedartists 0:b567d56a59d7 1414 /*wpos = pos & (windowsize - 1)*/
embeddedartists 0:b567d56a59d7 1415 static void updateHashChain(Hash* hash, size_t wpos, int hashval)
embeddedartists 0:b567d56a59d7 1416 {
embeddedartists 0:b567d56a59d7 1417 hash->val[wpos] = hashval;
embeddedartists 0:b567d56a59d7 1418 if(hash->head[hashval] != -1) hash->chain[wpos] = hash->head[hashval];
embeddedartists 0:b567d56a59d7 1419 hash->head[hashval] = wpos;
embeddedartists 0:b567d56a59d7 1420 }
embeddedartists 0:b567d56a59d7 1421
embeddedartists 0:b567d56a59d7 1422 /*
embeddedartists 0:b567d56a59d7 1423 LZ77-encode the data. Return value is error code. The input are raw bytes, the output
embeddedartists 0:b567d56a59d7 1424 is in the form of unsigned integers with codes representing for example literal bytes, or
embeddedartists 0:b567d56a59d7 1425 length/distance pairs.
embeddedartists 0:b567d56a59d7 1426 It uses a hash table technique to let it encode faster. When doing LZ77 encoding, a
embeddedartists 0:b567d56a59d7 1427 sliding window (of windowsize) is used, and all past bytes in that window can be used as
embeddedartists 0:b567d56a59d7 1428 the "dictionary". A brute force search through all possible distances would be slow, and
embeddedartists 0:b567d56a59d7 1429 this hash technique is one out of several ways to speed this up.
embeddedartists 0:b567d56a59d7 1430 */
embeddedartists 0:b567d56a59d7 1431 static unsigned encodeLZ77(uivector* out, Hash* hash,
embeddedartists 0:b567d56a59d7 1432 const unsigned char* in, size_t inpos, size_t insize, unsigned windowsize,
embeddedartists 0:b567d56a59d7 1433 unsigned minmatch, unsigned nicematch, unsigned lazymatching)
embeddedartists 0:b567d56a59d7 1434 {
embeddedartists 0:b567d56a59d7 1435 unsigned pos, i, error = 0;
embeddedartists 0:b567d56a59d7 1436 /*for large window lengths, assume the user wants no compression loss. Otherwise, max hash chain length speedup.*/
embeddedartists 0:b567d56a59d7 1437 unsigned maxchainlength = windowsize >= 8192 ? windowsize : windowsize / 8;
embeddedartists 0:b567d56a59d7 1438 unsigned maxlazymatch = windowsize >= 8192 ? MAX_SUPPORTED_DEFLATE_LENGTH : 64;
embeddedartists 0:b567d56a59d7 1439
embeddedartists 0:b567d56a59d7 1440 unsigned usezeros = 1; /*not sure if setting it to false for windowsize < 8192 is better or worse*/
embeddedartists 0:b567d56a59d7 1441 unsigned numzeros = 0;
embeddedartists 0:b567d56a59d7 1442
embeddedartists 0:b567d56a59d7 1443 unsigned offset; /*the offset represents the distance in LZ77 terminology*/
embeddedartists 0:b567d56a59d7 1444 unsigned length;
embeddedartists 0:b567d56a59d7 1445 unsigned lazy = 0;
embeddedartists 0:b567d56a59d7 1446 unsigned lazylength = 0, lazyoffset = 0;
embeddedartists 0:b567d56a59d7 1447 unsigned hashval;
embeddedartists 0:b567d56a59d7 1448 unsigned current_offset, current_length;
embeddedartists 0:b567d56a59d7 1449 const unsigned char *lastptr, *foreptr, *backptr;
embeddedartists 0:b567d56a59d7 1450 unsigned hashpos, prevpos;
embeddedartists 0:b567d56a59d7 1451
embeddedartists 0:b567d56a59d7 1452 if(windowsize <= 0 || windowsize > 32768) return 60; /*error: windowsize smaller/larger than allowed*/
embeddedartists 0:b567d56a59d7 1453 if((windowsize & (windowsize - 1)) != 0) return 90; /*error: must be power of two*/
embeddedartists 0:b567d56a59d7 1454
embeddedartists 0:b567d56a59d7 1455 if(nicematch > MAX_SUPPORTED_DEFLATE_LENGTH) nicematch = MAX_SUPPORTED_DEFLATE_LENGTH;
embeddedartists 0:b567d56a59d7 1456
embeddedartists 0:b567d56a59d7 1457 for(pos = inpos; pos < insize; pos++)
embeddedartists 0:b567d56a59d7 1458 {
embeddedartists 0:b567d56a59d7 1459 size_t wpos = pos & (windowsize - 1); /*position for in 'circular' hash buffers*/
embeddedartists 0:b567d56a59d7 1460 unsigned chainlength = 0;
embeddedartists 0:b567d56a59d7 1461
embeddedartists 0:b567d56a59d7 1462 hashval = getHash(in, insize, pos);
embeddedartists 0:b567d56a59d7 1463 updateHashChain(hash, wpos, hashval);
embeddedartists 0:b567d56a59d7 1464
embeddedartists 0:b567d56a59d7 1465 if(usezeros && hashval == 0)
embeddedartists 0:b567d56a59d7 1466 {
embeddedartists 0:b567d56a59d7 1467 if (numzeros == 0) numzeros = countZeros(in, insize, pos);
embeddedartists 0:b567d56a59d7 1468 else if (pos + numzeros >= insize || in[pos + numzeros - 1] != 0) numzeros--;
embeddedartists 0:b567d56a59d7 1469 hash->zeros[wpos] = numzeros;
embeddedartists 0:b567d56a59d7 1470 }
embeddedartists 0:b567d56a59d7 1471 else
embeddedartists 0:b567d56a59d7 1472 {
embeddedartists 0:b567d56a59d7 1473 numzeros = 0;
embeddedartists 0:b567d56a59d7 1474 }
embeddedartists 0:b567d56a59d7 1475
embeddedartists 0:b567d56a59d7 1476 /*the length and offset found for the current position*/
embeddedartists 0:b567d56a59d7 1477 length = 0;
embeddedartists 0:b567d56a59d7 1478 offset = 0;
embeddedartists 0:b567d56a59d7 1479
embeddedartists 0:b567d56a59d7 1480 prevpos = hash->head[hashval];
embeddedartists 0:b567d56a59d7 1481 hashpos = hash->chain[prevpos];
embeddedartists 0:b567d56a59d7 1482
embeddedartists 0:b567d56a59d7 1483 lastptr = &in[insize < pos + MAX_SUPPORTED_DEFLATE_LENGTH ? insize : pos + MAX_SUPPORTED_DEFLATE_LENGTH];
embeddedartists 0:b567d56a59d7 1484
embeddedartists 0:b567d56a59d7 1485 /*search for the longest string*/
embeddedartists 0:b567d56a59d7 1486 for(;;)
embeddedartists 0:b567d56a59d7 1487 {
embeddedartists 0:b567d56a59d7 1488 /*stop when went completely around the circular buffer*/
embeddedartists 0:b567d56a59d7 1489 if(prevpos < wpos && hashpos > prevpos && hashpos <= wpos) break;
embeddedartists 0:b567d56a59d7 1490 if(prevpos > wpos && (hashpos <= wpos || hashpos > prevpos)) break;
embeddedartists 0:b567d56a59d7 1491 if(chainlength++ >= maxchainlength) break;
embeddedartists 0:b567d56a59d7 1492
embeddedartists 0:b567d56a59d7 1493 current_offset = hashpos <= wpos ? wpos - hashpos : wpos - hashpos + windowsize;
embeddedartists 0:b567d56a59d7 1494 if(current_offset > 0)
embeddedartists 0:b567d56a59d7 1495 {
embeddedartists 0:b567d56a59d7 1496 /*test the next characters*/
embeddedartists 0:b567d56a59d7 1497 foreptr = &in[pos];
embeddedartists 0:b567d56a59d7 1498 backptr = &in[pos - current_offset];
embeddedartists 0:b567d56a59d7 1499
embeddedartists 0:b567d56a59d7 1500 /*common case in PNGs is lots of zeros. Quickly skip over them as a speedup*/
embeddedartists 0:b567d56a59d7 1501 if(usezeros && hashval == 0 && hash->val[hashpos] == 0 /*hashval[hashpos] may be out of date*/)
embeddedartists 0:b567d56a59d7 1502 {
embeddedartists 0:b567d56a59d7 1503 unsigned skip = hash->zeros[hashpos];
embeddedartists 0:b567d56a59d7 1504 if(skip > numzeros) skip = numzeros;
embeddedartists 0:b567d56a59d7 1505 backptr += skip;
embeddedartists 0:b567d56a59d7 1506 foreptr += skip;
embeddedartists 0:b567d56a59d7 1507 }
embeddedartists 0:b567d56a59d7 1508
embeddedartists 0:b567d56a59d7 1509 while(foreptr != lastptr && *backptr == *foreptr) /*maximum supported length by deflate is max length*/
embeddedartists 0:b567d56a59d7 1510 {
embeddedartists 0:b567d56a59d7 1511 ++backptr;
embeddedartists 0:b567d56a59d7 1512 ++foreptr;
embeddedartists 0:b567d56a59d7 1513 }
embeddedartists 0:b567d56a59d7 1514 current_length = (unsigned)(foreptr - &in[pos]);
embeddedartists 0:b567d56a59d7 1515
embeddedartists 0:b567d56a59d7 1516 if(current_length > length)
embeddedartists 0:b567d56a59d7 1517 {
embeddedartists 0:b567d56a59d7 1518 length = current_length; /*the longest length*/
embeddedartists 0:b567d56a59d7 1519 offset = current_offset; /*the offset that is related to this longest length*/
embeddedartists 0:b567d56a59d7 1520 /*jump out once a length of max length is found (speed gain). This also jumps
embeddedartists 0:b567d56a59d7 1521 out if length is MAX_SUPPORTED_DEFLATE_LENGTH*/
embeddedartists 0:b567d56a59d7 1522 if(current_length >= nicematch) break;
embeddedartists 0:b567d56a59d7 1523 }
embeddedartists 0:b567d56a59d7 1524 }
embeddedartists 0:b567d56a59d7 1525
embeddedartists 0:b567d56a59d7 1526 if(hashpos == hash->chain[hashpos]) break;
embeddedartists 0:b567d56a59d7 1527
embeddedartists 0:b567d56a59d7 1528 prevpos = hashpos;
embeddedartists 0:b567d56a59d7 1529 hashpos = hash->chain[hashpos];
embeddedartists 0:b567d56a59d7 1530 }
embeddedartists 0:b567d56a59d7 1531
embeddedartists 0:b567d56a59d7 1532 if(lazymatching)
embeddedartists 0:b567d56a59d7 1533 {
embeddedartists 0:b567d56a59d7 1534 if(!lazy && length >= 3 && length <= maxlazymatch && length < MAX_SUPPORTED_DEFLATE_LENGTH)
embeddedartists 0:b567d56a59d7 1535 {
embeddedartists 0:b567d56a59d7 1536 lazy = 1;
embeddedartists 0:b567d56a59d7 1537 lazylength = length;
embeddedartists 0:b567d56a59d7 1538 lazyoffset = offset;
embeddedartists 0:b567d56a59d7 1539 continue; /*try the next byte*/
embeddedartists 0:b567d56a59d7 1540 }
embeddedartists 0:b567d56a59d7 1541 if(lazy)
embeddedartists 0:b567d56a59d7 1542 {
embeddedartists 0:b567d56a59d7 1543 lazy = 0;
embeddedartists 0:b567d56a59d7 1544 if(pos == 0) ERROR_BREAK(81);
embeddedartists 0:b567d56a59d7 1545 if(length > lazylength + 1)
embeddedartists 0:b567d56a59d7 1546 {
embeddedartists 0:b567d56a59d7 1547 /*push the previous character as literal*/
embeddedartists 0:b567d56a59d7 1548 if(!uivector_push_back(out, in[pos - 1])) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1549 }
embeddedartists 0:b567d56a59d7 1550 else
embeddedartists 0:b567d56a59d7 1551 {
embeddedartists 0:b567d56a59d7 1552 length = lazylength;
embeddedartists 0:b567d56a59d7 1553 offset = lazyoffset;
embeddedartists 0:b567d56a59d7 1554 hash->head[hashval] = -1; /*the same hashchain update will be done, this ensures no wrong alteration*/
embeddedartists 0:b567d56a59d7 1555 pos--;
embeddedartists 0:b567d56a59d7 1556 }
embeddedartists 0:b567d56a59d7 1557 }
embeddedartists 0:b567d56a59d7 1558 }
embeddedartists 0:b567d56a59d7 1559 if(length >= 3 && offset > windowsize) ERROR_BREAK(86 /*too big (or overflown negative) offset*/);
embeddedartists 0:b567d56a59d7 1560
embeddedartists 0:b567d56a59d7 1561 /*encode it as length/distance pair or literal value*/
embeddedartists 0:b567d56a59d7 1562 if(length < 3) /*only lengths of 3 or higher are supported as length/distance pair*/
embeddedartists 0:b567d56a59d7 1563 {
embeddedartists 0:b567d56a59d7 1564 if(!uivector_push_back(out, in[pos])) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1565 }
embeddedartists 0:b567d56a59d7 1566 else if(length < minmatch || (length == 3 && offset > 4096))
embeddedartists 0:b567d56a59d7 1567 {
embeddedartists 0:b567d56a59d7 1568 /*compensate for the fact that longer offsets have more extra bits, a
embeddedartists 0:b567d56a59d7 1569 length of only 3 may be not worth it then*/
embeddedartists 0:b567d56a59d7 1570 if(!uivector_push_back(out, in[pos])) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1571 }
embeddedartists 0:b567d56a59d7 1572 else
embeddedartists 0:b567d56a59d7 1573 {
embeddedartists 0:b567d56a59d7 1574 addLengthDistance(out, length, offset);
embeddedartists 0:b567d56a59d7 1575 for(i = 1; i < length; i++)
embeddedartists 0:b567d56a59d7 1576 {
embeddedartists 0:b567d56a59d7 1577 pos++;
embeddedartists 0:b567d56a59d7 1578 wpos = pos & (windowsize - 1);
embeddedartists 0:b567d56a59d7 1579 hashval = getHash(in, insize, pos);
embeddedartists 0:b567d56a59d7 1580 updateHashChain(hash, wpos, hashval);
embeddedartists 0:b567d56a59d7 1581 if(usezeros && hashval == 0)
embeddedartists 0:b567d56a59d7 1582 {
embeddedartists 0:b567d56a59d7 1583 if (numzeros == 0) numzeros = countZeros(in, insize, pos);
embeddedartists 0:b567d56a59d7 1584 else if (pos + numzeros >= insize || in[pos + numzeros - 1] != 0) numzeros--;
embeddedartists 0:b567d56a59d7 1585 hash->zeros[wpos] = numzeros;
embeddedartists 0:b567d56a59d7 1586 }
embeddedartists 0:b567d56a59d7 1587 else
embeddedartists 0:b567d56a59d7 1588 {
embeddedartists 0:b567d56a59d7 1589 numzeros = 0;
embeddedartists 0:b567d56a59d7 1590 }
embeddedartists 0:b567d56a59d7 1591 }
embeddedartists 0:b567d56a59d7 1592 }
embeddedartists 0:b567d56a59d7 1593 } /*end of the loop through each character of input*/
embeddedartists 0:b567d56a59d7 1594
embeddedartists 0:b567d56a59d7 1595 return error;
embeddedartists 0:b567d56a59d7 1596 }
embeddedartists 0:b567d56a59d7 1597
embeddedartists 0:b567d56a59d7 1598 /* /////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 1599
embeddedartists 0:b567d56a59d7 1600 static unsigned deflateNoCompression(ucvector* out, const unsigned char* data, size_t datasize)
embeddedartists 0:b567d56a59d7 1601 {
embeddedartists 0:b567d56a59d7 1602 /*non compressed deflate block data: 1 bit BFINAL,2 bits BTYPE,(5 bits): it jumps to start of next byte,
embeddedartists 0:b567d56a59d7 1603 2 bytes LEN, 2 bytes NLEN, LEN bytes literal DATA*/
embeddedartists 0:b567d56a59d7 1604
embeddedartists 0:b567d56a59d7 1605 size_t i, j, numdeflateblocks = (datasize + 65534) / 65535;
embeddedartists 0:b567d56a59d7 1606 unsigned datapos = 0;
embeddedartists 0:b567d56a59d7 1607 for(i = 0; i < numdeflateblocks; i++)
embeddedartists 0:b567d56a59d7 1608 {
embeddedartists 0:b567d56a59d7 1609 unsigned BFINAL, BTYPE, LEN, NLEN;
embeddedartists 0:b567d56a59d7 1610 unsigned char firstbyte;
embeddedartists 0:b567d56a59d7 1611
embeddedartists 0:b567d56a59d7 1612 BFINAL = (i == numdeflateblocks - 1);
embeddedartists 0:b567d56a59d7 1613 BTYPE = 0;
embeddedartists 0:b567d56a59d7 1614
embeddedartists 0:b567d56a59d7 1615 firstbyte = (unsigned char)(BFINAL + ((BTYPE & 1) << 1) + ((BTYPE & 2) << 1));
embeddedartists 0:b567d56a59d7 1616 ucvector_push_back(out, firstbyte);
embeddedartists 0:b567d56a59d7 1617
embeddedartists 0:b567d56a59d7 1618 LEN = 65535;
embeddedartists 0:b567d56a59d7 1619 if(datasize - datapos < 65535) LEN = (unsigned)datasize - datapos;
embeddedartists 0:b567d56a59d7 1620 NLEN = 65535 - LEN;
embeddedartists 0:b567d56a59d7 1621
embeddedartists 0:b567d56a59d7 1622 ucvector_push_back(out, (unsigned char)(LEN % 256));
embeddedartists 0:b567d56a59d7 1623 ucvector_push_back(out, (unsigned char)(LEN / 256));
embeddedartists 0:b567d56a59d7 1624 ucvector_push_back(out, (unsigned char)(NLEN % 256));
embeddedartists 0:b567d56a59d7 1625 ucvector_push_back(out, (unsigned char)(NLEN / 256));
embeddedartists 0:b567d56a59d7 1626
embeddedartists 0:b567d56a59d7 1627 /*Decompressed data*/
embeddedartists 0:b567d56a59d7 1628 for(j = 0; j < 65535 && datapos < datasize; j++)
embeddedartists 0:b567d56a59d7 1629 {
embeddedartists 0:b567d56a59d7 1630 ucvector_push_back(out, data[datapos++]);
embeddedartists 0:b567d56a59d7 1631 }
embeddedartists 0:b567d56a59d7 1632 }
embeddedartists 0:b567d56a59d7 1633
embeddedartists 0:b567d56a59d7 1634 return 0;
embeddedartists 0:b567d56a59d7 1635 }
embeddedartists 0:b567d56a59d7 1636
embeddedartists 0:b567d56a59d7 1637 /*
embeddedartists 0:b567d56a59d7 1638 write the lz77-encoded data, which has lit, len and dist codes, to compressed stream using huffman trees.
embeddedartists 0:b567d56a59d7 1639 tree_ll: the tree for lit and len codes.
embeddedartists 0:b567d56a59d7 1640 tree_d: the tree for distance codes.
embeddedartists 0:b567d56a59d7 1641 */
embeddedartists 0:b567d56a59d7 1642 static void writeLZ77data(size_t* bp, ucvector* out, const uivector* lz77_encoded,
embeddedartists 0:b567d56a59d7 1643 const HuffmanTree* tree_ll, const HuffmanTree* tree_d)
embeddedartists 0:b567d56a59d7 1644 {
embeddedartists 0:b567d56a59d7 1645 size_t i = 0;
embeddedartists 0:b567d56a59d7 1646 for(i = 0; i < lz77_encoded->size; i++)
embeddedartists 0:b567d56a59d7 1647 {
embeddedartists 0:b567d56a59d7 1648 unsigned val = lz77_encoded->data[i];
embeddedartists 0:b567d56a59d7 1649 addHuffmanSymbol(bp, out, HuffmanTree_getCode(tree_ll, val), HuffmanTree_getLength(tree_ll, val));
embeddedartists 0:b567d56a59d7 1650 if(val > 256) /*for a length code, 3 more things have to be added*/
embeddedartists 0:b567d56a59d7 1651 {
embeddedartists 0:b567d56a59d7 1652 unsigned length_index = val - FIRST_LENGTH_CODE_INDEX;
embeddedartists 0:b567d56a59d7 1653 unsigned n_length_extra_bits = LENGTHEXTRA[length_index];
embeddedartists 0:b567d56a59d7 1654 unsigned length_extra_bits = lz77_encoded->data[++i];
embeddedartists 0:b567d56a59d7 1655
embeddedartists 0:b567d56a59d7 1656 unsigned distance_code = lz77_encoded->data[++i];
embeddedartists 0:b567d56a59d7 1657
embeddedartists 0:b567d56a59d7 1658 unsigned distance_index = distance_code;
embeddedartists 0:b567d56a59d7 1659 unsigned n_distance_extra_bits = DISTANCEEXTRA[distance_index];
embeddedartists 0:b567d56a59d7 1660 unsigned distance_extra_bits = lz77_encoded->data[++i];
embeddedartists 0:b567d56a59d7 1661
embeddedartists 0:b567d56a59d7 1662 addBitsToStream(bp, out, length_extra_bits, n_length_extra_bits);
embeddedartists 0:b567d56a59d7 1663 addHuffmanSymbol(bp, out, HuffmanTree_getCode(tree_d, distance_code),
embeddedartists 0:b567d56a59d7 1664 HuffmanTree_getLength(tree_d, distance_code));
embeddedartists 0:b567d56a59d7 1665 addBitsToStream(bp, out, distance_extra_bits, n_distance_extra_bits);
embeddedartists 0:b567d56a59d7 1666 }
embeddedartists 0:b567d56a59d7 1667 }
embeddedartists 0:b567d56a59d7 1668 }
embeddedartists 0:b567d56a59d7 1669
embeddedartists 0:b567d56a59d7 1670 /*Deflate for a block of type "dynamic", that is, with freely, optimally, created huffman trees*/
embeddedartists 0:b567d56a59d7 1671 static unsigned deflateDynamic(ucvector* out, size_t* bp, Hash* hash,
embeddedartists 0:b567d56a59d7 1672 const unsigned char* data, size_t datapos, size_t dataend,
embeddedartists 0:b567d56a59d7 1673 const LodePNGCompressSettings* settings, int final)
embeddedartists 0:b567d56a59d7 1674 {
embeddedartists 0:b567d56a59d7 1675 unsigned error = 0;
embeddedartists 0:b567d56a59d7 1676
embeddedartists 0:b567d56a59d7 1677 /*
embeddedartists 0:b567d56a59d7 1678 A block is compressed as follows: The PNG data is lz77 encoded, resulting in
embeddedartists 0:b567d56a59d7 1679 literal bytes and length/distance pairs. This is then huffman compressed with
embeddedartists 0:b567d56a59d7 1680 two huffman trees. One huffman tree is used for the lit and len values ("ll"),
embeddedartists 0:b567d56a59d7 1681 another huffman tree is used for the dist values ("d"). These two trees are
embeddedartists 0:b567d56a59d7 1682 stored using their code lengths, and to compress even more these code lengths
embeddedartists 0:b567d56a59d7 1683 are also run-length encoded and huffman compressed. This gives a huffman tree
embeddedartists 0:b567d56a59d7 1684 of code lengths "cl". The code lenghts used to describe this third tree are
embeddedartists 0:b567d56a59d7 1685 the code length code lengths ("clcl").
embeddedartists 0:b567d56a59d7 1686 */
embeddedartists 0:b567d56a59d7 1687
embeddedartists 0:b567d56a59d7 1688 /*The lz77 encoded data, represented with integers since there will also be length and distance codes in it*/
embeddedartists 0:b567d56a59d7 1689 uivector lz77_encoded;
embeddedartists 0:b567d56a59d7 1690 HuffmanTree tree_ll; /*tree for lit,len values*/
embeddedartists 0:b567d56a59d7 1691 HuffmanTree tree_d; /*tree for distance codes*/
embeddedartists 0:b567d56a59d7 1692 HuffmanTree tree_cl; /*tree for encoding the code lengths representing tree_ll and tree_d*/
embeddedartists 0:b567d56a59d7 1693 uivector frequencies_ll; /*frequency of lit,len codes*/
embeddedartists 0:b567d56a59d7 1694 uivector frequencies_d; /*frequency of dist codes*/
embeddedartists 0:b567d56a59d7 1695 uivector frequencies_cl; /*frequency of code length codes*/
embeddedartists 0:b567d56a59d7 1696 uivector bitlen_lld; /*lit,len,dist code lenghts (int bits), literally (without repeat codes).*/
embeddedartists 0:b567d56a59d7 1697 uivector bitlen_lld_e; /*bitlen_lld encoded with repeat codes (this is a rudemtary run length compression)*/
embeddedartists 0:b567d56a59d7 1698 /*bitlen_cl is the code length code lengths ("clcl"). The bit lengths of codes to represent tree_cl
embeddedartists 0:b567d56a59d7 1699 (these are written as is in the file, it would be crazy to compress these using yet another huffman
embeddedartists 0:b567d56a59d7 1700 tree that needs to be represented by yet another set of code lengths)*/
embeddedartists 0:b567d56a59d7 1701 uivector bitlen_cl;
embeddedartists 0:b567d56a59d7 1702 size_t datasize = dataend - datapos;
embeddedartists 0:b567d56a59d7 1703
embeddedartists 0:b567d56a59d7 1704 /*
embeddedartists 0:b567d56a59d7 1705 Due to the huffman compression of huffman tree representations ("two levels"), there are some anologies:
embeddedartists 0:b567d56a59d7 1706 bitlen_lld is to tree_cl what data is to tree_ll and tree_d.
embeddedartists 0:b567d56a59d7 1707 bitlen_lld_e is to bitlen_lld what lz77_encoded is to data.
embeddedartists 0:b567d56a59d7 1708 bitlen_cl is to bitlen_lld_e what bitlen_lld is to lz77_encoded.
embeddedartists 0:b567d56a59d7 1709 */
embeddedartists 0:b567d56a59d7 1710
embeddedartists 0:b567d56a59d7 1711 unsigned BFINAL = final;
embeddedartists 0:b567d56a59d7 1712 size_t numcodes_ll, numcodes_d, i;
embeddedartists 0:b567d56a59d7 1713 unsigned HLIT, HDIST, HCLEN;
embeddedartists 0:b567d56a59d7 1714
embeddedartists 0:b567d56a59d7 1715 uivector_init(&lz77_encoded);
embeddedartists 0:b567d56a59d7 1716 HuffmanTree_init(&tree_ll);
embeddedartists 0:b567d56a59d7 1717 HuffmanTree_init(&tree_d);
embeddedartists 0:b567d56a59d7 1718 HuffmanTree_init(&tree_cl);
embeddedartists 0:b567d56a59d7 1719 uivector_init(&frequencies_ll);
embeddedartists 0:b567d56a59d7 1720 uivector_init(&frequencies_d);
embeddedartists 0:b567d56a59d7 1721 uivector_init(&frequencies_cl);
embeddedartists 0:b567d56a59d7 1722 uivector_init(&bitlen_lld);
embeddedartists 0:b567d56a59d7 1723 uivector_init(&bitlen_lld_e);
embeddedartists 0:b567d56a59d7 1724 uivector_init(&bitlen_cl);
embeddedartists 0:b567d56a59d7 1725
embeddedartists 0:b567d56a59d7 1726 /*This while loop never loops due to a break at the end, it is here to
embeddedartists 0:b567d56a59d7 1727 allow breaking out of it to the cleanup phase on error conditions.*/
embeddedartists 0:b567d56a59d7 1728 while(!error)
embeddedartists 0:b567d56a59d7 1729 {
embeddedartists 0:b567d56a59d7 1730 if(settings->use_lz77)
embeddedartists 0:b567d56a59d7 1731 {
embeddedartists 0:b567d56a59d7 1732 error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize,
embeddedartists 0:b567d56a59d7 1733 settings->minmatch, settings->nicematch, settings->lazymatching);
embeddedartists 0:b567d56a59d7 1734 if(error) break;
embeddedartists 0:b567d56a59d7 1735 }
embeddedartists 0:b567d56a59d7 1736 else
embeddedartists 0:b567d56a59d7 1737 {
embeddedartists 0:b567d56a59d7 1738 if(!uivector_resize(&lz77_encoded, datasize)) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1739 for(i = datapos; i < dataend; i++) lz77_encoded.data[i] = data[i]; /*no LZ77, but still will be Huffman compressed*/
embeddedartists 0:b567d56a59d7 1740 }
embeddedartists 0:b567d56a59d7 1741
embeddedartists 0:b567d56a59d7 1742 if(!uivector_resizev(&frequencies_ll, 286, 0)) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1743 if(!uivector_resizev(&frequencies_d, 30, 0)) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1744
embeddedartists 0:b567d56a59d7 1745 /*Count the frequencies of lit, len and dist codes*/
embeddedartists 0:b567d56a59d7 1746 for(i = 0; i < lz77_encoded.size; i++)
embeddedartists 0:b567d56a59d7 1747 {
embeddedartists 0:b567d56a59d7 1748 unsigned symbol = lz77_encoded.data[i];
embeddedartists 0:b567d56a59d7 1749 frequencies_ll.data[symbol]++;
embeddedartists 0:b567d56a59d7 1750 if(symbol > 256)
embeddedartists 0:b567d56a59d7 1751 {
embeddedartists 0:b567d56a59d7 1752 unsigned dist = lz77_encoded.data[i + 2];
embeddedartists 0:b567d56a59d7 1753 frequencies_d.data[dist]++;
embeddedartists 0:b567d56a59d7 1754 i += 3;
embeddedartists 0:b567d56a59d7 1755 }
embeddedartists 0:b567d56a59d7 1756 }
embeddedartists 0:b567d56a59d7 1757 frequencies_ll.data[256] = 1; /*there will be exactly 1 end code, at the end of the block*/
embeddedartists 0:b567d56a59d7 1758
embeddedartists 0:b567d56a59d7 1759 /*Make both huffman trees, one for the lit and len codes, one for the dist codes*/
embeddedartists 0:b567d56a59d7 1760 error = HuffmanTree_makeFromFrequencies(&tree_ll, frequencies_ll.data, 257, frequencies_ll.size, 15);
embeddedartists 0:b567d56a59d7 1761 if(error) break;
embeddedartists 0:b567d56a59d7 1762 /*2, not 1, is chosen for mincodes: some buggy PNG decoders require at least 2 symbols in the dist tree*/
embeddedartists 0:b567d56a59d7 1763 error = HuffmanTree_makeFromFrequencies(&tree_d, frequencies_d.data, 2, frequencies_d.size, 15);
embeddedartists 0:b567d56a59d7 1764 if(error) break;
embeddedartists 0:b567d56a59d7 1765
embeddedartists 0:b567d56a59d7 1766 numcodes_ll = tree_ll.numcodes; if(numcodes_ll > 286) numcodes_ll = 286;
embeddedartists 0:b567d56a59d7 1767 numcodes_d = tree_d.numcodes; if(numcodes_d > 30) numcodes_d = 30;
embeddedartists 0:b567d56a59d7 1768 /*store the code lengths of both generated trees in bitlen_lld*/
embeddedartists 0:b567d56a59d7 1769 for(i = 0; i < numcodes_ll; i++) uivector_push_back(&bitlen_lld, HuffmanTree_getLength(&tree_ll, (unsigned)i));
embeddedartists 0:b567d56a59d7 1770 for(i = 0; i < numcodes_d; i++) uivector_push_back(&bitlen_lld, HuffmanTree_getLength(&tree_d, (unsigned)i));
embeddedartists 0:b567d56a59d7 1771
embeddedartists 0:b567d56a59d7 1772 /*run-length compress bitlen_ldd into bitlen_lld_e by using repeat codes 16 (copy length 3-6 times),
embeddedartists 0:b567d56a59d7 1773 17 (3-10 zeroes), 18 (11-138 zeroes)*/
embeddedartists 0:b567d56a59d7 1774 for(i = 0; i < (unsigned)bitlen_lld.size; i++)
embeddedartists 0:b567d56a59d7 1775 {
embeddedartists 0:b567d56a59d7 1776 unsigned j = 0; /*amount of repititions*/
embeddedartists 0:b567d56a59d7 1777 while(i + j + 1 < (unsigned)bitlen_lld.size && bitlen_lld.data[i + j + 1] == bitlen_lld.data[i]) j++;
embeddedartists 0:b567d56a59d7 1778
embeddedartists 0:b567d56a59d7 1779 if(bitlen_lld.data[i] == 0 && j >= 2) /*repeat code for zeroes*/
embeddedartists 0:b567d56a59d7 1780 {
embeddedartists 0:b567d56a59d7 1781 j++; /*include the first zero*/
embeddedartists 0:b567d56a59d7 1782 if(j <= 10) /*repeat code 17 supports max 10 zeroes*/
embeddedartists 0:b567d56a59d7 1783 {
embeddedartists 0:b567d56a59d7 1784 uivector_push_back(&bitlen_lld_e, 17);
embeddedartists 0:b567d56a59d7 1785 uivector_push_back(&bitlen_lld_e, j - 3);
embeddedartists 0:b567d56a59d7 1786 }
embeddedartists 0:b567d56a59d7 1787 else /*repeat code 18 supports max 138 zeroes*/
embeddedartists 0:b567d56a59d7 1788 {
embeddedartists 0:b567d56a59d7 1789 if(j > 138) j = 138;
embeddedartists 0:b567d56a59d7 1790 uivector_push_back(&bitlen_lld_e, 18);
embeddedartists 0:b567d56a59d7 1791 uivector_push_back(&bitlen_lld_e, j - 11);
embeddedartists 0:b567d56a59d7 1792 }
embeddedartists 0:b567d56a59d7 1793 i += (j - 1);
embeddedartists 0:b567d56a59d7 1794 }
embeddedartists 0:b567d56a59d7 1795 else if(j >= 3) /*repeat code for value other than zero*/
embeddedartists 0:b567d56a59d7 1796 {
embeddedartists 0:b567d56a59d7 1797 size_t k;
embeddedartists 0:b567d56a59d7 1798 unsigned num = j / 6, rest = j % 6;
embeddedartists 0:b567d56a59d7 1799 uivector_push_back(&bitlen_lld_e, bitlen_lld.data[i]);
embeddedartists 0:b567d56a59d7 1800 for(k = 0; k < num; k++)
embeddedartists 0:b567d56a59d7 1801 {
embeddedartists 0:b567d56a59d7 1802 uivector_push_back(&bitlen_lld_e, 16);
embeddedartists 0:b567d56a59d7 1803 uivector_push_back(&bitlen_lld_e, 6 - 3);
embeddedartists 0:b567d56a59d7 1804 }
embeddedartists 0:b567d56a59d7 1805 if(rest >= 3)
embeddedartists 0:b567d56a59d7 1806 {
embeddedartists 0:b567d56a59d7 1807 uivector_push_back(&bitlen_lld_e, 16);
embeddedartists 0:b567d56a59d7 1808 uivector_push_back(&bitlen_lld_e, rest - 3);
embeddedartists 0:b567d56a59d7 1809 }
embeddedartists 0:b567d56a59d7 1810 else j -= rest;
embeddedartists 0:b567d56a59d7 1811 i += j;
embeddedartists 0:b567d56a59d7 1812 }
embeddedartists 0:b567d56a59d7 1813 else /*too short to benefit from repeat code*/
embeddedartists 0:b567d56a59d7 1814 {
embeddedartists 0:b567d56a59d7 1815 uivector_push_back(&bitlen_lld_e, bitlen_lld.data[i]);
embeddedartists 0:b567d56a59d7 1816 }
embeddedartists 0:b567d56a59d7 1817 }
embeddedartists 0:b567d56a59d7 1818
embeddedartists 0:b567d56a59d7 1819 /*generate tree_cl, the huffmantree of huffmantrees*/
embeddedartists 0:b567d56a59d7 1820
embeddedartists 0:b567d56a59d7 1821 if(!uivector_resizev(&frequencies_cl, NUM_CODE_LENGTH_CODES, 0)) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1822 for(i = 0; i < bitlen_lld_e.size; i++)
embeddedartists 0:b567d56a59d7 1823 {
embeddedartists 0:b567d56a59d7 1824 frequencies_cl.data[bitlen_lld_e.data[i]]++;
embeddedartists 0:b567d56a59d7 1825 /*after a repeat code come the bits that specify the number of repetitions,
embeddedartists 0:b567d56a59d7 1826 those don't need to be in the frequencies_cl calculation*/
embeddedartists 0:b567d56a59d7 1827 if(bitlen_lld_e.data[i] >= 16) i++;
embeddedartists 0:b567d56a59d7 1828 }
embeddedartists 0:b567d56a59d7 1829
embeddedartists 0:b567d56a59d7 1830 error = HuffmanTree_makeFromFrequencies(&tree_cl, frequencies_cl.data,
embeddedartists 0:b567d56a59d7 1831 frequencies_cl.size, frequencies_cl.size, 7);
embeddedartists 0:b567d56a59d7 1832 if(error) break;
embeddedartists 0:b567d56a59d7 1833
embeddedartists 0:b567d56a59d7 1834 if(!uivector_resize(&bitlen_cl, tree_cl.numcodes)) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1835 for(i = 0; i < tree_cl.numcodes; i++)
embeddedartists 0:b567d56a59d7 1836 {
embeddedartists 0:b567d56a59d7 1837 /*lenghts of code length tree is in the order as specified by deflate*/
embeddedartists 0:b567d56a59d7 1838 bitlen_cl.data[i] = HuffmanTree_getLength(&tree_cl, CLCL_ORDER[i]);
embeddedartists 0:b567d56a59d7 1839 }
embeddedartists 0:b567d56a59d7 1840 while(bitlen_cl.data[bitlen_cl.size - 1] == 0 && bitlen_cl.size > 4)
embeddedartists 0:b567d56a59d7 1841 {
embeddedartists 0:b567d56a59d7 1842 /*remove zeros at the end, but minimum size must be 4*/
embeddedartists 0:b567d56a59d7 1843 if(!uivector_resize(&bitlen_cl, bitlen_cl.size - 1)) ERROR_BREAK(83 /*alloc fail*/);
embeddedartists 0:b567d56a59d7 1844 }
embeddedartists 0:b567d56a59d7 1845 if(error) break;
embeddedartists 0:b567d56a59d7 1846
embeddedartists 0:b567d56a59d7 1847 /*
embeddedartists 0:b567d56a59d7 1848 Write everything into the output
embeddedartists 0:b567d56a59d7 1849
embeddedartists 0:b567d56a59d7 1850 After the BFINAL and BTYPE, the dynamic block consists out of the following:
embeddedartists 0:b567d56a59d7 1851 - 5 bits HLIT, 5 bits HDIST, 4 bits HCLEN
embeddedartists 0:b567d56a59d7 1852 - (HCLEN+4)*3 bits code lengths of code length alphabet
embeddedartists 0:b567d56a59d7 1853 - HLIT + 257 code lenghts of lit/length alphabet (encoded using the code length
embeddedartists 0:b567d56a59d7 1854 alphabet, + possible repetition codes 16, 17, 18)
embeddedartists 0:b567d56a59d7 1855 - HDIST + 1 code lengths of distance alphabet (encoded using the code length
embeddedartists 0:b567d56a59d7 1856 alphabet, + possible repetition codes 16, 17, 18)
embeddedartists 0:b567d56a59d7 1857 - compressed data
embeddedartists 0:b567d56a59d7 1858 - 256 (end code)
embeddedartists 0:b567d56a59d7 1859 */
embeddedartists 0:b567d56a59d7 1860
embeddedartists 0:b567d56a59d7 1861 /*Write block type*/
embeddedartists 0:b567d56a59d7 1862 addBitToStream(bp, out, BFINAL);
embeddedartists 0:b567d56a59d7 1863 addBitToStream(bp, out, 0); /*first bit of BTYPE "dynamic"*/
embeddedartists 0:b567d56a59d7 1864 addBitToStream(bp, out, 1); /*second bit of BTYPE "dynamic"*/
embeddedartists 0:b567d56a59d7 1865
embeddedartists 0:b567d56a59d7 1866 /*write the HLIT, HDIST and HCLEN values*/
embeddedartists 0:b567d56a59d7 1867 HLIT = (unsigned)(numcodes_ll - 257);
embeddedartists 0:b567d56a59d7 1868 HDIST = (unsigned)(numcodes_d - 1);
embeddedartists 0:b567d56a59d7 1869 HCLEN = (unsigned)bitlen_cl.size - 4;
embeddedartists 0:b567d56a59d7 1870 /*trim zeroes for HCLEN. HLIT and HDIST were already trimmed at tree creation*/
embeddedartists 0:b567d56a59d7 1871 while(!bitlen_cl.data[HCLEN + 4 - 1] && HCLEN > 0) HCLEN--;
embeddedartists 0:b567d56a59d7 1872 addBitsToStream(bp, out, HLIT, 5);
embeddedartists 0:b567d56a59d7 1873 addBitsToStream(bp, out, HDIST, 5);
embeddedartists 0:b567d56a59d7 1874 addBitsToStream(bp, out, HCLEN, 4);
embeddedartists 0:b567d56a59d7 1875
embeddedartists 0:b567d56a59d7 1876 /*write the code lenghts of the code length alphabet*/
embeddedartists 0:b567d56a59d7 1877 for(i = 0; i < HCLEN + 4; i++) addBitsToStream(bp, out, bitlen_cl.data[i], 3);
embeddedartists 0:b567d56a59d7 1878
embeddedartists 0:b567d56a59d7 1879 /*write the lenghts of the lit/len AND the dist alphabet*/
embeddedartists 0:b567d56a59d7 1880 for(i = 0; i < bitlen_lld_e.size; i++)
embeddedartists 0:b567d56a59d7 1881 {
embeddedartists 0:b567d56a59d7 1882 addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_cl, bitlen_lld_e.data[i]),
embeddedartists 0:b567d56a59d7 1883 HuffmanTree_getLength(&tree_cl, bitlen_lld_e.data[i]));
embeddedartists 0:b567d56a59d7 1884 /*extra bits of repeat codes*/
embeddedartists 0:b567d56a59d7 1885 if(bitlen_lld_e.data[i] == 16) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 2);
embeddedartists 0:b567d56a59d7 1886 else if(bitlen_lld_e.data[i] == 17) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 3);
embeddedartists 0:b567d56a59d7 1887 else if(bitlen_lld_e.data[i] == 18) addBitsToStream(bp, out, bitlen_lld_e.data[++i], 7);
embeddedartists 0:b567d56a59d7 1888 }
embeddedartists 0:b567d56a59d7 1889
embeddedartists 0:b567d56a59d7 1890 /*write the compressed data symbols*/
embeddedartists 0:b567d56a59d7 1891 writeLZ77data(bp, out, &lz77_encoded, &tree_ll, &tree_d);
embeddedartists 0:b567d56a59d7 1892 /*error: the length of the end code 256 must be larger than 0*/
embeddedartists 0:b567d56a59d7 1893 if(HuffmanTree_getLength(&tree_ll, 256) == 0) ERROR_BREAK(64);
embeddedartists 0:b567d56a59d7 1894
embeddedartists 0:b567d56a59d7 1895 /*write the end code*/
embeddedartists 0:b567d56a59d7 1896 addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, 256), HuffmanTree_getLength(&tree_ll, 256));
embeddedartists 0:b567d56a59d7 1897
embeddedartists 0:b567d56a59d7 1898 break; /*end of error-while*/
embeddedartists 0:b567d56a59d7 1899 }
embeddedartists 0:b567d56a59d7 1900
embeddedartists 0:b567d56a59d7 1901 /*cleanup*/
embeddedartists 0:b567d56a59d7 1902 uivector_cleanup(&lz77_encoded);
embeddedartists 0:b567d56a59d7 1903 HuffmanTree_cleanup(&tree_ll);
embeddedartists 0:b567d56a59d7 1904 HuffmanTree_cleanup(&tree_d);
embeddedartists 0:b567d56a59d7 1905 HuffmanTree_cleanup(&tree_cl);
embeddedartists 0:b567d56a59d7 1906 uivector_cleanup(&frequencies_ll);
embeddedartists 0:b567d56a59d7 1907 uivector_cleanup(&frequencies_d);
embeddedartists 0:b567d56a59d7 1908 uivector_cleanup(&frequencies_cl);
embeddedartists 0:b567d56a59d7 1909 uivector_cleanup(&bitlen_lld_e);
embeddedartists 0:b567d56a59d7 1910 uivector_cleanup(&bitlen_lld);
embeddedartists 0:b567d56a59d7 1911 uivector_cleanup(&bitlen_cl);
embeddedartists 0:b567d56a59d7 1912
embeddedartists 0:b567d56a59d7 1913 return error;
embeddedartists 0:b567d56a59d7 1914 }
embeddedartists 0:b567d56a59d7 1915
embeddedartists 0:b567d56a59d7 1916 static unsigned deflateFixed(ucvector* out, size_t* bp, Hash* hash,
embeddedartists 0:b567d56a59d7 1917 const unsigned char* data,
embeddedartists 0:b567d56a59d7 1918 size_t datapos, size_t dataend,
embeddedartists 0:b567d56a59d7 1919 const LodePNGCompressSettings* settings, int final)
embeddedartists 0:b567d56a59d7 1920 {
embeddedartists 0:b567d56a59d7 1921 HuffmanTree tree_ll; /*tree for literal values and length codes*/
embeddedartists 0:b567d56a59d7 1922 HuffmanTree tree_d; /*tree for distance codes*/
embeddedartists 0:b567d56a59d7 1923
embeddedartists 0:b567d56a59d7 1924 unsigned BFINAL = final;
embeddedartists 0:b567d56a59d7 1925 unsigned error = 0;
embeddedartists 0:b567d56a59d7 1926 size_t i;
embeddedartists 0:b567d56a59d7 1927
embeddedartists 0:b567d56a59d7 1928 HuffmanTree_init(&tree_ll);
embeddedartists 0:b567d56a59d7 1929 HuffmanTree_init(&tree_d);
embeddedartists 0:b567d56a59d7 1930
embeddedartists 0:b567d56a59d7 1931 generateFixedLitLenTree(&tree_ll);
embeddedartists 0:b567d56a59d7 1932 generateFixedDistanceTree(&tree_d);
embeddedartists 0:b567d56a59d7 1933
embeddedartists 0:b567d56a59d7 1934 addBitToStream(bp, out, BFINAL);
embeddedartists 0:b567d56a59d7 1935 addBitToStream(bp, out, 1); /*first bit of BTYPE*/
embeddedartists 0:b567d56a59d7 1936 addBitToStream(bp, out, 0); /*second bit of BTYPE*/
embeddedartists 0:b567d56a59d7 1937
embeddedartists 0:b567d56a59d7 1938 if(settings->use_lz77) /*LZ77 encoded*/
embeddedartists 0:b567d56a59d7 1939 {
embeddedartists 0:b567d56a59d7 1940 uivector lz77_encoded;
embeddedartists 0:b567d56a59d7 1941 uivector_init(&lz77_encoded);
embeddedartists 0:b567d56a59d7 1942 error = encodeLZ77(&lz77_encoded, hash, data, datapos, dataend, settings->windowsize,
embeddedartists 0:b567d56a59d7 1943 settings->minmatch, settings->nicematch, settings->lazymatching);
embeddedartists 0:b567d56a59d7 1944 if(!error) writeLZ77data(bp, out, &lz77_encoded, &tree_ll, &tree_d);
embeddedartists 0:b567d56a59d7 1945 uivector_cleanup(&lz77_encoded);
embeddedartists 0:b567d56a59d7 1946 }
embeddedartists 0:b567d56a59d7 1947 else /*no LZ77, but still will be Huffman compressed*/
embeddedartists 0:b567d56a59d7 1948 {
embeddedartists 0:b567d56a59d7 1949 for(i = datapos; i < dataend; i++)
embeddedartists 0:b567d56a59d7 1950 {
embeddedartists 0:b567d56a59d7 1951 addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, data[i]), HuffmanTree_getLength(&tree_ll, data[i]));
embeddedartists 0:b567d56a59d7 1952 }
embeddedartists 0:b567d56a59d7 1953 }
embeddedartists 0:b567d56a59d7 1954 /*add END code*/
embeddedartists 0:b567d56a59d7 1955 if(!error) addHuffmanSymbol(bp, out, HuffmanTree_getCode(&tree_ll, 256), HuffmanTree_getLength(&tree_ll, 256));
embeddedartists 0:b567d56a59d7 1956
embeddedartists 0:b567d56a59d7 1957 /*cleanup*/
embeddedartists 0:b567d56a59d7 1958 HuffmanTree_cleanup(&tree_ll);
embeddedartists 0:b567d56a59d7 1959 HuffmanTree_cleanup(&tree_d);
embeddedartists 0:b567d56a59d7 1960
embeddedartists 0:b567d56a59d7 1961 return error;
embeddedartists 0:b567d56a59d7 1962 }
embeddedartists 0:b567d56a59d7 1963
embeddedartists 0:b567d56a59d7 1964 static unsigned lodepng_deflatev(ucvector* out, const unsigned char* in, size_t insize,
embeddedartists 0:b567d56a59d7 1965 const LodePNGCompressSettings* settings)
embeddedartists 0:b567d56a59d7 1966 {
embeddedartists 0:b567d56a59d7 1967 unsigned error = 0;
embeddedartists 0:b567d56a59d7 1968 size_t i, blocksize, numdeflateblocks;
embeddedartists 0:b567d56a59d7 1969 size_t bp = 0; /*the bit pointer*/
embeddedartists 0:b567d56a59d7 1970 Hash hash;
embeddedartists 0:b567d56a59d7 1971
embeddedartists 0:b567d56a59d7 1972 if(settings->btype > 2) return 61;
embeddedartists 0:b567d56a59d7 1973 else if(settings->btype == 0) return deflateNoCompression(out, in, insize);
embeddedartists 0:b567d56a59d7 1974 else if(settings->btype == 1) blocksize = insize;
embeddedartists 0:b567d56a59d7 1975 else /*if(settings->btype == 2)*/
embeddedartists 0:b567d56a59d7 1976 {
embeddedartists 0:b567d56a59d7 1977 blocksize = insize / 8 + 8;
embeddedartists 0:b567d56a59d7 1978 if(blocksize < 65535) blocksize = 65535;
embeddedartists 0:b567d56a59d7 1979 }
embeddedartists 0:b567d56a59d7 1980
embeddedartists 0:b567d56a59d7 1981 numdeflateblocks = (insize + blocksize - 1) / blocksize;
embeddedartists 0:b567d56a59d7 1982 if(numdeflateblocks == 0) numdeflateblocks = 1;
embeddedartists 0:b567d56a59d7 1983
embeddedartists 0:b567d56a59d7 1984 error = hash_init(&hash, settings->windowsize);
embeddedartists 0:b567d56a59d7 1985 if(error) return error;
embeddedartists 0:b567d56a59d7 1986
embeddedartists 0:b567d56a59d7 1987 for(i = 0; i < numdeflateblocks && !error; i++)
embeddedartists 0:b567d56a59d7 1988 {
embeddedartists 0:b567d56a59d7 1989 int final = i == numdeflateblocks - 1;
embeddedartists 0:b567d56a59d7 1990 size_t start = i * blocksize;
embeddedartists 0:b567d56a59d7 1991 size_t end = start + blocksize;
embeddedartists 0:b567d56a59d7 1992 if(end > insize) end = insize;
embeddedartists 0:b567d56a59d7 1993
embeddedartists 0:b567d56a59d7 1994 if(settings->btype == 1) error = deflateFixed(out, &bp, &hash, in, start, end, settings, final);
embeddedartists 0:b567d56a59d7 1995 else if(settings->btype == 2) error = deflateDynamic(out, &bp, &hash, in, start, end, settings, final);
embeddedartists 0:b567d56a59d7 1996 }
embeddedartists 0:b567d56a59d7 1997
embeddedartists 0:b567d56a59d7 1998 hash_cleanup(&hash);
embeddedartists 0:b567d56a59d7 1999
embeddedartists 0:b567d56a59d7 2000 return error;
embeddedartists 0:b567d56a59d7 2001 }
embeddedartists 0:b567d56a59d7 2002
embeddedartists 0:b567d56a59d7 2003 unsigned lodepng_deflate(unsigned char** out, size_t* outsize,
embeddedartists 0:b567d56a59d7 2004 const unsigned char* in, size_t insize,
embeddedartists 0:b567d56a59d7 2005 const LodePNGCompressSettings* settings)
embeddedartists 0:b567d56a59d7 2006 {
embeddedartists 0:b567d56a59d7 2007 unsigned error;
embeddedartists 0:b567d56a59d7 2008 ucvector v;
embeddedartists 0:b567d56a59d7 2009 ucvector_init_buffer(&v, *out, *outsize);
embeddedartists 0:b567d56a59d7 2010 error = lodepng_deflatev(&v, in, insize, settings);
embeddedartists 0:b567d56a59d7 2011 *out = v.data;
embeddedartists 0:b567d56a59d7 2012 *outsize = v.size;
embeddedartists 0:b567d56a59d7 2013 return error;
embeddedartists 0:b567d56a59d7 2014 }
embeddedartists 0:b567d56a59d7 2015
embeddedartists 0:b567d56a59d7 2016 static unsigned deflate(unsigned char** out, size_t* outsize,
embeddedartists 0:b567d56a59d7 2017 const unsigned char* in, size_t insize,
embeddedartists 0:b567d56a59d7 2018 const LodePNGCompressSettings* settings)
embeddedartists 0:b567d56a59d7 2019 {
embeddedartists 0:b567d56a59d7 2020 if(settings->custom_deflate)
embeddedartists 0:b567d56a59d7 2021 {
embeddedartists 0:b567d56a59d7 2022 return settings->custom_deflate(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2023 }
embeddedartists 0:b567d56a59d7 2024 else
embeddedartists 0:b567d56a59d7 2025 {
embeddedartists 0:b567d56a59d7 2026 return lodepng_deflate(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2027 }
embeddedartists 0:b567d56a59d7 2028 }
embeddedartists 0:b567d56a59d7 2029
embeddedartists 0:b567d56a59d7 2030 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 2031
embeddedartists 0:b567d56a59d7 2032 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2033 /* / Adler32 */
embeddedartists 0:b567d56a59d7 2034 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2035
embeddedartists 0:b567d56a59d7 2036 static unsigned update_adler32(unsigned adler, const unsigned char* data, unsigned len)
embeddedartists 0:b567d56a59d7 2037 {
embeddedartists 0:b567d56a59d7 2038 unsigned s1 = adler & 0xffff;
embeddedartists 0:b567d56a59d7 2039 unsigned s2 = (adler >> 16) & 0xffff;
embeddedartists 0:b567d56a59d7 2040
embeddedartists 0:b567d56a59d7 2041 while(len > 0)
embeddedartists 0:b567d56a59d7 2042 {
embeddedartists 0:b567d56a59d7 2043 /*at least 5550 sums can be done before the sums overflow, saving a lot of module divisions*/
embeddedartists 0:b567d56a59d7 2044 unsigned amount = len > 5550 ? 5550 : len;
embeddedartists 0:b567d56a59d7 2045 len -= amount;
embeddedartists 0:b567d56a59d7 2046 while(amount > 0)
embeddedartists 0:b567d56a59d7 2047 {
embeddedartists 0:b567d56a59d7 2048 s1 += (*data++);
embeddedartists 0:b567d56a59d7 2049 s2 += s1;
embeddedartists 0:b567d56a59d7 2050 amount--;
embeddedartists 0:b567d56a59d7 2051 }
embeddedartists 0:b567d56a59d7 2052 s1 %= 65521;
embeddedartists 0:b567d56a59d7 2053 s2 %= 65521;
embeddedartists 0:b567d56a59d7 2054 }
embeddedartists 0:b567d56a59d7 2055
embeddedartists 0:b567d56a59d7 2056 return (s2 << 16) | s1;
embeddedartists 0:b567d56a59d7 2057 }
embeddedartists 0:b567d56a59d7 2058
embeddedartists 0:b567d56a59d7 2059 /*Return the adler32 of the bytes data[0..len-1]*/
embeddedartists 0:b567d56a59d7 2060 static unsigned adler32(const unsigned char* data, unsigned len)
embeddedartists 0:b567d56a59d7 2061 {
embeddedartists 0:b567d56a59d7 2062 return update_adler32(1L, data, len);
embeddedartists 0:b567d56a59d7 2063 }
embeddedartists 0:b567d56a59d7 2064
embeddedartists 0:b567d56a59d7 2065 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2066 /* / Zlib / */
embeddedartists 0:b567d56a59d7 2067 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2068
embeddedartists 0:b567d56a59d7 2069 #ifdef LODEPNG_COMPILE_DECODER
embeddedartists 0:b567d56a59d7 2070
embeddedartists 0:b567d56a59d7 2071 unsigned lodepng_zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
embeddedartists 0:b567d56a59d7 2072 size_t insize, const LodePNGDecompressSettings* settings)
embeddedartists 0:b567d56a59d7 2073 {
embeddedartists 0:b567d56a59d7 2074 unsigned error = 0;
embeddedartists 0:b567d56a59d7 2075 unsigned CM, CINFO, FDICT;
embeddedartists 0:b567d56a59d7 2076
embeddedartists 0:b567d56a59d7 2077 if(insize < 2) return 53; /*error, size of zlib data too small*/
embeddedartists 0:b567d56a59d7 2078 /*read information from zlib header*/
embeddedartists 0:b567d56a59d7 2079 if((in[0] * 256 + in[1]) % 31 != 0)
embeddedartists 0:b567d56a59d7 2080 {
embeddedartists 0:b567d56a59d7 2081 /*error: 256 * in[0] + in[1] must be a multiple of 31, the FCHECK value is supposed to be made that way*/
embeddedartists 0:b567d56a59d7 2082 return 24;
embeddedartists 0:b567d56a59d7 2083 }
embeddedartists 0:b567d56a59d7 2084
embeddedartists 0:b567d56a59d7 2085 CM = in[0] & 15;
embeddedartists 0:b567d56a59d7 2086 CINFO = (in[0] >> 4) & 15;
embeddedartists 0:b567d56a59d7 2087 /*FCHECK = in[1] & 31;*/ /*FCHECK is already tested above*/
embeddedartists 0:b567d56a59d7 2088 FDICT = (in[1] >> 5) & 1;
embeddedartists 0:b567d56a59d7 2089 /*FLEVEL = (in[1] >> 6) & 3;*/ /*FLEVEL is not used here*/
embeddedartists 0:b567d56a59d7 2090
embeddedartists 0:b567d56a59d7 2091 if(CM != 8 || CINFO > 7)
embeddedartists 0:b567d56a59d7 2092 {
embeddedartists 0:b567d56a59d7 2093 /*error: only compression method 8: inflate with sliding window of 32k is supported by the PNG spec*/
embeddedartists 0:b567d56a59d7 2094 return 25;
embeddedartists 0:b567d56a59d7 2095 }
embeddedartists 0:b567d56a59d7 2096 if(FDICT != 0)
embeddedartists 0:b567d56a59d7 2097 {
embeddedartists 0:b567d56a59d7 2098 /*error: the specification of PNG says about the zlib stream:
embeddedartists 0:b567d56a59d7 2099 "The additional flags shall not specify a preset dictionary."*/
embeddedartists 0:b567d56a59d7 2100 return 26;
embeddedartists 0:b567d56a59d7 2101 }
embeddedartists 0:b567d56a59d7 2102
embeddedartists 0:b567d56a59d7 2103 error = inflate(out, outsize, in + 2, insize - 2, settings);
embeddedartists 0:b567d56a59d7 2104 if(error) return error;
embeddedartists 0:b567d56a59d7 2105
embeddedartists 0:b567d56a59d7 2106 if(!settings->ignore_adler32)
embeddedartists 0:b567d56a59d7 2107 {
embeddedartists 0:b567d56a59d7 2108 unsigned ADLER32 = lodepng_read32bitInt(&in[insize - 4]);
embeddedartists 0:b567d56a59d7 2109 unsigned checksum = adler32(*out, (unsigned)(*outsize));
embeddedartists 0:b567d56a59d7 2110 if(checksum != ADLER32) return 58; /*error, adler checksum not correct, data must be corrupted*/
embeddedartists 0:b567d56a59d7 2111 }
embeddedartists 0:b567d56a59d7 2112
embeddedartists 0:b567d56a59d7 2113 return 0; /*no error*/
embeddedartists 0:b567d56a59d7 2114 }
embeddedartists 0:b567d56a59d7 2115
embeddedartists 0:b567d56a59d7 2116 static unsigned zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
embeddedartists 0:b567d56a59d7 2117 size_t insize, const LodePNGDecompressSettings* settings)
embeddedartists 0:b567d56a59d7 2118 {
embeddedartists 0:b567d56a59d7 2119 if(settings->custom_zlib)
embeddedartists 0:b567d56a59d7 2120 {
embeddedartists 0:b567d56a59d7 2121 return settings->custom_zlib(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2122 }
embeddedartists 0:b567d56a59d7 2123 else
embeddedartists 0:b567d56a59d7 2124 {
embeddedartists 0:b567d56a59d7 2125 return lodepng_zlib_decompress(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2126 }
embeddedartists 0:b567d56a59d7 2127 }
embeddedartists 0:b567d56a59d7 2128
embeddedartists 0:b567d56a59d7 2129 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 2130
embeddedartists 0:b567d56a59d7 2131 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 2132
embeddedartists 0:b567d56a59d7 2133 unsigned lodepng_zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
embeddedartists 0:b567d56a59d7 2134 size_t insize, const LodePNGCompressSettings* settings)
embeddedartists 0:b567d56a59d7 2135 {
embeddedartists 0:b567d56a59d7 2136 /*initially, *out must be NULL and outsize 0, if you just give some random *out
embeddedartists 0:b567d56a59d7 2137 that's pointing to a non allocated buffer, this'll crash*/
embeddedartists 0:b567d56a59d7 2138 ucvector outv;
embeddedartists 0:b567d56a59d7 2139 size_t i;
embeddedartists 0:b567d56a59d7 2140 unsigned error;
embeddedartists 0:b567d56a59d7 2141 unsigned char* deflatedata = 0;
embeddedartists 0:b567d56a59d7 2142 size_t deflatesize = 0;
embeddedartists 0:b567d56a59d7 2143
embeddedartists 0:b567d56a59d7 2144 unsigned ADLER32;
embeddedartists 0:b567d56a59d7 2145 /*zlib data: 1 byte CMF (CM+CINFO), 1 byte FLG, deflate data, 4 byte ADLER32 checksum of the Decompressed data*/
embeddedartists 0:b567d56a59d7 2146 unsigned CMF = 120; /*0b01111000: CM 8, CINFO 7. With CINFO 7, any window size up to 32768 can be used.*/
embeddedartists 0:b567d56a59d7 2147 unsigned FLEVEL = 0;
embeddedartists 0:b567d56a59d7 2148 unsigned FDICT = 0;
embeddedartists 0:b567d56a59d7 2149 unsigned CMFFLG = 256 * CMF + FDICT * 32 + FLEVEL * 64;
embeddedartists 0:b567d56a59d7 2150 unsigned FCHECK = 31 - CMFFLG % 31;
embeddedartists 0:b567d56a59d7 2151 CMFFLG += FCHECK;
embeddedartists 0:b567d56a59d7 2152
embeddedartists 0:b567d56a59d7 2153 /*ucvector-controlled version of the output buffer, for dynamic array*/
embeddedartists 0:b567d56a59d7 2154 ucvector_init_buffer(&outv, *out, *outsize);
embeddedartists 0:b567d56a59d7 2155
embeddedartists 0:b567d56a59d7 2156 ucvector_push_back(&outv, (unsigned char)(CMFFLG / 256));
embeddedartists 0:b567d56a59d7 2157 ucvector_push_back(&outv, (unsigned char)(CMFFLG % 256));
embeddedartists 0:b567d56a59d7 2158
embeddedartists 0:b567d56a59d7 2159 error = deflate(&deflatedata, &deflatesize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2160
embeddedartists 0:b567d56a59d7 2161 if(!error)
embeddedartists 0:b567d56a59d7 2162 {
embeddedartists 0:b567d56a59d7 2163 ADLER32 = adler32(in, (unsigned)insize);
embeddedartists 0:b567d56a59d7 2164 for(i = 0; i < deflatesize; i++) ucvector_push_back(&outv, deflatedata[i]);
embeddedartists 0:b567d56a59d7 2165 lodepng_free(deflatedata);
embeddedartists 0:b567d56a59d7 2166 lodepng_add32bitInt(&outv, ADLER32);
embeddedartists 0:b567d56a59d7 2167 }
embeddedartists 0:b567d56a59d7 2168
embeddedartists 0:b567d56a59d7 2169 *out = outv.data;
embeddedartists 0:b567d56a59d7 2170 *outsize = outv.size;
embeddedartists 0:b567d56a59d7 2171
embeddedartists 0:b567d56a59d7 2172 return error;
embeddedartists 0:b567d56a59d7 2173 }
embeddedartists 0:b567d56a59d7 2174
embeddedartists 0:b567d56a59d7 2175 /* compress using the default or custom zlib function */
embeddedartists 0:b567d56a59d7 2176 static unsigned zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
embeddedartists 0:b567d56a59d7 2177 size_t insize, const LodePNGCompressSettings* settings)
embeddedartists 0:b567d56a59d7 2178 {
embeddedartists 0:b567d56a59d7 2179 if(settings->custom_zlib)
embeddedartists 0:b567d56a59d7 2180 {
embeddedartists 0:b567d56a59d7 2181 return settings->custom_zlib(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2182 }
embeddedartists 0:b567d56a59d7 2183 else
embeddedartists 0:b567d56a59d7 2184 {
embeddedartists 0:b567d56a59d7 2185 return lodepng_zlib_compress(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2186 }
embeddedartists 0:b567d56a59d7 2187 }
embeddedartists 0:b567d56a59d7 2188
embeddedartists 0:b567d56a59d7 2189 #endif /*LODEPNG_COMPILE_ENCODER*/
embeddedartists 0:b567d56a59d7 2190
embeddedartists 0:b567d56a59d7 2191 #else /*no LODEPNG_COMPILE_ZLIB*/
embeddedartists 0:b567d56a59d7 2192
embeddedartists 0:b567d56a59d7 2193 #ifdef LODEPNG_COMPILE_DECODER
embeddedartists 0:b567d56a59d7 2194 static unsigned zlib_decompress(unsigned char** out, size_t* outsize, const unsigned char* in,
embeddedartists 0:b567d56a59d7 2195 size_t insize, const LodePNGDecompressSettings* settings)
embeddedartists 0:b567d56a59d7 2196 {
embeddedartists 0:b567d56a59d7 2197 if (!settings->custom_zlib) return 87; /*no custom zlib function provided */
embeddedartists 0:b567d56a59d7 2198 return settings->custom_zlib(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2199 }
embeddedartists 0:b567d56a59d7 2200 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 2201 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 2202 static unsigned zlib_compress(unsigned char** out, size_t* outsize, const unsigned char* in,
embeddedartists 0:b567d56a59d7 2203 size_t insize, const LodePNGCompressSettings* settings)
embeddedartists 0:b567d56a59d7 2204 {
embeddedartists 0:b567d56a59d7 2205 if (!settings->custom_zlib) return 87; /*no custom zlib function provided */
embeddedartists 0:b567d56a59d7 2206 return settings->custom_zlib(out, outsize, in, insize, settings);
embeddedartists 0:b567d56a59d7 2207 }
embeddedartists 0:b567d56a59d7 2208 #endif /*LODEPNG_COMPILE_ENCODER*/
embeddedartists 0:b567d56a59d7 2209
embeddedartists 0:b567d56a59d7 2210 #endif /*LODEPNG_COMPILE_ZLIB*/
embeddedartists 0:b567d56a59d7 2211
embeddedartists 0:b567d56a59d7 2212 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2213
embeddedartists 0:b567d56a59d7 2214 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 2215
embeddedartists 0:b567d56a59d7 2216 /*this is a good tradeoff between speed and compression ratio*/
embeddedartists 0:b567d56a59d7 2217 #define DEFAULT_WINDOWSIZE 2048
embeddedartists 0:b567d56a59d7 2218
embeddedartists 0:b567d56a59d7 2219 void lodepng_compress_settings_init(LodePNGCompressSettings* settings)
embeddedartists 0:b567d56a59d7 2220 {
embeddedartists 0:b567d56a59d7 2221 /*compress with dynamic huffman tree (not in the mathematical sense, just not the predefined one)*/
embeddedartists 0:b567d56a59d7 2222 settings->btype = 2;
embeddedartists 0:b567d56a59d7 2223 settings->use_lz77 = 1;
embeddedartists 0:b567d56a59d7 2224 settings->windowsize = DEFAULT_WINDOWSIZE;
embeddedartists 0:b567d56a59d7 2225 settings->minmatch = 3;
embeddedartists 0:b567d56a59d7 2226 settings->nicematch = 128;
embeddedartists 0:b567d56a59d7 2227 settings->lazymatching = 1;
embeddedartists 0:b567d56a59d7 2228
embeddedartists 0:b567d56a59d7 2229 settings->custom_zlib = 0;
embeddedartists 0:b567d56a59d7 2230 settings->custom_deflate = 0;
embeddedartists 0:b567d56a59d7 2231 settings->custom_context = 0;
embeddedartists 0:b567d56a59d7 2232 }
embeddedartists 0:b567d56a59d7 2233
embeddedartists 0:b567d56a59d7 2234 const LodePNGCompressSettings lodepng_default_compress_settings = {2, 1, DEFAULT_WINDOWSIZE, 3, 128, 1, 0, 0, 0};
embeddedartists 0:b567d56a59d7 2235
embeddedartists 0:b567d56a59d7 2236
embeddedartists 0:b567d56a59d7 2237 #endif /*LODEPNG_COMPILE_ENCODER*/
embeddedartists 0:b567d56a59d7 2238
embeddedartists 0:b567d56a59d7 2239 #ifdef LODEPNG_COMPILE_DECODER
embeddedartists 0:b567d56a59d7 2240
embeddedartists 0:b567d56a59d7 2241 void lodepng_decompress_settings_init(LodePNGDecompressSettings* settings)
embeddedartists 0:b567d56a59d7 2242 {
embeddedartists 0:b567d56a59d7 2243 settings->ignore_adler32 = 0;
embeddedartists 0:b567d56a59d7 2244
embeddedartists 0:b567d56a59d7 2245 settings->custom_zlib = 0;
embeddedartists 0:b567d56a59d7 2246 settings->custom_inflate = 0;
embeddedartists 0:b567d56a59d7 2247 settings->custom_context = 0;
embeddedartists 0:b567d56a59d7 2248 }
embeddedartists 0:b567d56a59d7 2249
embeddedartists 0:b567d56a59d7 2250 const LodePNGDecompressSettings lodepng_default_decompress_settings = {0, 0, 0, 0};
embeddedartists 0:b567d56a59d7 2251
embeddedartists 0:b567d56a59d7 2252 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 2253
embeddedartists 0:b567d56a59d7 2254 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2255 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2256 /* // End of Zlib related code. Begin of PNG related code. // */
embeddedartists 0:b567d56a59d7 2257 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2258 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2259
embeddedartists 0:b567d56a59d7 2260 #ifdef LODEPNG_COMPILE_PNG
embeddedartists 0:b567d56a59d7 2261
embeddedartists 0:b567d56a59d7 2262 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2263 /* / CRC32 / */
embeddedartists 0:b567d56a59d7 2264 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2265
embeddedartists 0:b567d56a59d7 2266 /* CRC polynomial: 0xedb88320 */
embeddedartists 0:b567d56a59d7 2267 static unsigned lodepng_crc32_table[256] = {
embeddedartists 0:b567d56a59d7 2268 0u, 1996959894u, 3993919788u, 2567524794u, 124634137u, 1886057615u, 3915621685u, 2657392035u,
embeddedartists 0:b567d56a59d7 2269 249268274u, 2044508324u, 3772115230u, 2547177864u, 162941995u, 2125561021u, 3887607047u, 2428444049u,
embeddedartists 0:b567d56a59d7 2270 498536548u, 1789927666u, 4089016648u, 2227061214u, 450548861u, 1843258603u, 4107580753u, 2211677639u,
embeddedartists 0:b567d56a59d7 2271 325883990u, 1684777152u, 4251122042u, 2321926636u, 335633487u, 1661365465u, 4195302755u, 2366115317u,
embeddedartists 0:b567d56a59d7 2272 997073096u, 1281953886u, 3579855332u, 2724688242u, 1006888145u, 1258607687u, 3524101629u, 2768942443u,
embeddedartists 0:b567d56a59d7 2273 901097722u, 1119000684u, 3686517206u, 2898065728u, 853044451u, 1172266101u, 3705015759u, 2882616665u,
embeddedartists 0:b567d56a59d7 2274 651767980u, 1373503546u, 3369554304u, 3218104598u, 565507253u, 1454621731u, 3485111705u, 3099436303u,
embeddedartists 0:b567d56a59d7 2275 671266974u, 1594198024u, 3322730930u, 2970347812u, 795835527u, 1483230225u, 3244367275u, 3060149565u,
embeddedartists 0:b567d56a59d7 2276 1994146192u, 31158534u, 2563907772u, 4023717930u, 1907459465u, 112637215u, 2680153253u, 3904427059u,
embeddedartists 0:b567d56a59d7 2277 2013776290u, 251722036u, 2517215374u, 3775830040u, 2137656763u, 141376813u, 2439277719u, 3865271297u,
embeddedartists 0:b567d56a59d7 2278 1802195444u, 476864866u, 2238001368u, 4066508878u, 1812370925u, 453092731u, 2181625025u, 4111451223u,
embeddedartists 0:b567d56a59d7 2279 1706088902u, 314042704u, 2344532202u, 4240017532u, 1658658271u, 366619977u, 2362670323u, 4224994405u,
embeddedartists 0:b567d56a59d7 2280 1303535960u, 984961486u, 2747007092u, 3569037538u, 1256170817u, 1037604311u, 2765210733u, 3554079995u,
embeddedartists 0:b567d56a59d7 2281 1131014506u, 879679996u, 2909243462u, 3663771856u, 1141124467u, 855842277u, 2852801631u, 3708648649u,
embeddedartists 0:b567d56a59d7 2282 1342533948u, 654459306u, 3188396048u, 3373015174u, 1466479909u, 544179635u, 3110523913u, 3462522015u,
embeddedartists 0:b567d56a59d7 2283 1591671054u, 702138776u, 2966460450u, 3352799412u, 1504918807u, 783551873u, 3082640443u, 3233442989u,
embeddedartists 0:b567d56a59d7 2284 3988292384u, 2596254646u, 62317068u, 1957810842u, 3939845945u, 2647816111u, 81470997u, 1943803523u,
embeddedartists 0:b567d56a59d7 2285 3814918930u, 2489596804u, 225274430u, 2053790376u, 3826175755u, 2466906013u, 167816743u, 2097651377u,
embeddedartists 0:b567d56a59d7 2286 4027552580u, 2265490386u, 503444072u, 1762050814u, 4150417245u, 2154129355u, 426522225u, 1852507879u,
embeddedartists 0:b567d56a59d7 2287 4275313526u, 2312317920u, 282753626u, 1742555852u, 4189708143u, 2394877945u, 397917763u, 1622183637u,
embeddedartists 0:b567d56a59d7 2288 3604390888u, 2714866558u, 953729732u, 1340076626u, 3518719985u, 2797360999u, 1068828381u, 1219638859u,
embeddedartists 0:b567d56a59d7 2289 3624741850u, 2936675148u, 906185462u, 1090812512u, 3747672003u, 2825379669u, 829329135u, 1181335161u,
embeddedartists 0:b567d56a59d7 2290 3412177804u, 3160834842u, 628085408u, 1382605366u, 3423369109u, 3138078467u, 570562233u, 1426400815u,
embeddedartists 0:b567d56a59d7 2291 3317316542u, 2998733608u, 733239954u, 1555261956u, 3268935591u, 3050360625u, 752459403u, 1541320221u,
embeddedartists 0:b567d56a59d7 2292 2607071920u, 3965973030u, 1969922972u, 40735498u, 2617837225u, 3943577151u, 1913087877u, 83908371u,
embeddedartists 0:b567d56a59d7 2293 2512341634u, 3803740692u, 2075208622u, 213261112u, 2463272603u, 3855990285u, 2094854071u, 198958881u,
embeddedartists 0:b567d56a59d7 2294 2262029012u, 4057260610u, 1759359992u, 534414190u, 2176718541u, 4139329115u, 1873836001u, 414664567u,
embeddedartists 0:b567d56a59d7 2295 2282248934u, 4279200368u, 1711684554u, 285281116u, 2405801727u, 4167216745u, 1634467795u, 376229701u,
embeddedartists 0:b567d56a59d7 2296 2685067896u, 3608007406u, 1308918612u, 956543938u, 2808555105u, 3495958263u, 1231636301u, 1047427035u,
embeddedartists 0:b567d56a59d7 2297 2932959818u, 3654703836u, 1088359270u, 936918000u, 2847714899u, 3736837829u, 1202900863u, 817233897u,
embeddedartists 0:b567d56a59d7 2298 3183342108u, 3401237130u, 1404277552u, 615818150u, 3134207493u, 3453421203u, 1423857449u, 601450431u,
embeddedartists 0:b567d56a59d7 2299 3009837614u, 3294710456u, 1567103746u, 711928724u, 3020668471u, 3272380065u, 1510334235u, 755167117u
embeddedartists 0:b567d56a59d7 2300 };
embeddedartists 0:b567d56a59d7 2301
embeddedartists 0:b567d56a59d7 2302 /*Return the CRC of the bytes buf[0..len-1].*/
embeddedartists 0:b567d56a59d7 2303 unsigned lodepng_crc32(const unsigned char* buf, size_t len)
embeddedartists 0:b567d56a59d7 2304 {
embeddedartists 0:b567d56a59d7 2305 unsigned c = 0xffffffffL;
embeddedartists 0:b567d56a59d7 2306 size_t n;
embeddedartists 0:b567d56a59d7 2307
embeddedartists 0:b567d56a59d7 2308 for(n = 0; n < len; n++)
embeddedartists 0:b567d56a59d7 2309 {
embeddedartists 0:b567d56a59d7 2310 c = lodepng_crc32_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
embeddedartists 0:b567d56a59d7 2311 }
embeddedartists 0:b567d56a59d7 2312 return c ^ 0xffffffffL;
embeddedartists 0:b567d56a59d7 2313 }
embeddedartists 0:b567d56a59d7 2314
embeddedartists 0:b567d56a59d7 2315 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2316 /* / Reading and writing single bits and bytes from/to stream for LodePNG / */
embeddedartists 0:b567d56a59d7 2317 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2318
embeddedartists 0:b567d56a59d7 2319 static unsigned char readBitFromReversedStream(size_t* bitpointer, const unsigned char* bitstream)
embeddedartists 0:b567d56a59d7 2320 {
embeddedartists 0:b567d56a59d7 2321 unsigned char result = (unsigned char)((bitstream[(*bitpointer) >> 3] >> (7 - ((*bitpointer) & 0x7))) & 1);
embeddedartists 0:b567d56a59d7 2322 (*bitpointer)++;
embeddedartists 0:b567d56a59d7 2323 return result;
embeddedartists 0:b567d56a59d7 2324 }
embeddedartists 0:b567d56a59d7 2325
embeddedartists 0:b567d56a59d7 2326 static unsigned readBitsFromReversedStream(size_t* bitpointer, const unsigned char* bitstream, size_t nbits)
embeddedartists 0:b567d56a59d7 2327 {
embeddedartists 0:b567d56a59d7 2328 unsigned result = 0;
embeddedartists 0:b567d56a59d7 2329 size_t i;
embeddedartists 0:b567d56a59d7 2330 for(i = nbits - 1; i < nbits; i--)
embeddedartists 0:b567d56a59d7 2331 {
embeddedartists 0:b567d56a59d7 2332 result += (unsigned)readBitFromReversedStream(bitpointer, bitstream) << i;
embeddedartists 0:b567d56a59d7 2333 }
embeddedartists 0:b567d56a59d7 2334 return result;
embeddedartists 0:b567d56a59d7 2335 }
embeddedartists 0:b567d56a59d7 2336
embeddedartists 0:b567d56a59d7 2337 #ifdef LODEPNG_COMPILE_DECODER
embeddedartists 0:b567d56a59d7 2338 static void setBitOfReversedStream0(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
embeddedartists 0:b567d56a59d7 2339 {
embeddedartists 0:b567d56a59d7 2340 /*the current bit in bitstream must be 0 for this to work*/
embeddedartists 0:b567d56a59d7 2341 if(bit)
embeddedartists 0:b567d56a59d7 2342 {
embeddedartists 0:b567d56a59d7 2343 /*earlier bit of huffman code is in a lesser significant bit of an earlier byte*/
embeddedartists 0:b567d56a59d7 2344 bitstream[(*bitpointer) >> 3] |= (bit << (7 - ((*bitpointer) & 0x7)));
embeddedartists 0:b567d56a59d7 2345 }
embeddedartists 0:b567d56a59d7 2346 (*bitpointer)++;
embeddedartists 0:b567d56a59d7 2347 }
embeddedartists 0:b567d56a59d7 2348 #endif /*LODEPNG_COMPILE_DECODER*/
embeddedartists 0:b567d56a59d7 2349
embeddedartists 0:b567d56a59d7 2350 static void setBitOfReversedStream(size_t* bitpointer, unsigned char* bitstream, unsigned char bit)
embeddedartists 0:b567d56a59d7 2351 {
embeddedartists 0:b567d56a59d7 2352 /*the current bit in bitstream may be 0 or 1 for this to work*/
embeddedartists 0:b567d56a59d7 2353 if(bit == 0) bitstream[(*bitpointer) >> 3] &= (unsigned char)(~(1 << (7 - ((*bitpointer) & 0x7))));
embeddedartists 0:b567d56a59d7 2354 else bitstream[(*bitpointer) >> 3] |= (1 << (7 - ((*bitpointer) & 0x7)));
embeddedartists 0:b567d56a59d7 2355 (*bitpointer)++;
embeddedartists 0:b567d56a59d7 2356 }
embeddedartists 0:b567d56a59d7 2357
embeddedartists 0:b567d56a59d7 2358 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2359 /* / PNG chunks / */
embeddedartists 0:b567d56a59d7 2360 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2361
embeddedartists 0:b567d56a59d7 2362 unsigned lodepng_chunk_length(const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2363 {
embeddedartists 0:b567d56a59d7 2364 return lodepng_read32bitInt(&chunk[0]);
embeddedartists 0:b567d56a59d7 2365 }
embeddedartists 0:b567d56a59d7 2366
embeddedartists 0:b567d56a59d7 2367 void lodepng_chunk_type(char type[5], const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2368 {
embeddedartists 0:b567d56a59d7 2369 unsigned i;
embeddedartists 0:b567d56a59d7 2370 for(i = 0; i < 4; i++) type[i] = chunk[4 + i];
embeddedartists 0:b567d56a59d7 2371 type[4] = 0; /*null termination char*/
embeddedartists 0:b567d56a59d7 2372 }
embeddedartists 0:b567d56a59d7 2373
embeddedartists 0:b567d56a59d7 2374 unsigned char lodepng_chunk_type_equals(const unsigned char* chunk, const char* type)
embeddedartists 0:b567d56a59d7 2375 {
embeddedartists 0:b567d56a59d7 2376 if(strlen(type) != 4) return 0;
embeddedartists 0:b567d56a59d7 2377 return (chunk[4] == type[0] && chunk[5] == type[1] && chunk[6] == type[2] && chunk[7] == type[3]);
embeddedartists 0:b567d56a59d7 2378 }
embeddedartists 0:b567d56a59d7 2379
embeddedartists 0:b567d56a59d7 2380 unsigned char lodepng_chunk_ancillary(const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2381 {
embeddedartists 0:b567d56a59d7 2382 return((chunk[4] & 32) != 0);
embeddedartists 0:b567d56a59d7 2383 }
embeddedartists 0:b567d56a59d7 2384
embeddedartists 0:b567d56a59d7 2385 unsigned char lodepng_chunk_private(const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2386 {
embeddedartists 0:b567d56a59d7 2387 return((chunk[6] & 32) != 0);
embeddedartists 0:b567d56a59d7 2388 }
embeddedartists 0:b567d56a59d7 2389
embeddedartists 0:b567d56a59d7 2390 unsigned char lodepng_chunk_safetocopy(const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2391 {
embeddedartists 0:b567d56a59d7 2392 return((chunk[7] & 32) != 0);
embeddedartists 0:b567d56a59d7 2393 }
embeddedartists 0:b567d56a59d7 2394
embeddedartists 0:b567d56a59d7 2395 unsigned char* lodepng_chunk_data(unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2396 {
embeddedartists 0:b567d56a59d7 2397 return &chunk[8];
embeddedartists 0:b567d56a59d7 2398 }
embeddedartists 0:b567d56a59d7 2399
embeddedartists 0:b567d56a59d7 2400 const unsigned char* lodepng_chunk_data_const(const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2401 {
embeddedartists 0:b567d56a59d7 2402 return &chunk[8];
embeddedartists 0:b567d56a59d7 2403 }
embeddedartists 0:b567d56a59d7 2404
embeddedartists 0:b567d56a59d7 2405 unsigned lodepng_chunk_check_crc(const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2406 {
embeddedartists 0:b567d56a59d7 2407 unsigned length = lodepng_chunk_length(chunk);
embeddedartists 0:b567d56a59d7 2408 unsigned CRC = lodepng_read32bitInt(&chunk[length + 8]);
embeddedartists 0:b567d56a59d7 2409 /*the CRC is taken of the data and the 4 chunk type letters, not the length*/
embeddedartists 0:b567d56a59d7 2410 unsigned checksum = lodepng_crc32(&chunk[4], length + 4);
embeddedartists 0:b567d56a59d7 2411 if(CRC != checksum) return 1;
embeddedartists 0:b567d56a59d7 2412 else return 0;
embeddedartists 0:b567d56a59d7 2413 }
embeddedartists 0:b567d56a59d7 2414
embeddedartists 0:b567d56a59d7 2415 void lodepng_chunk_generate_crc(unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2416 {
embeddedartists 0:b567d56a59d7 2417 unsigned length = lodepng_chunk_length(chunk);
embeddedartists 0:b567d56a59d7 2418 unsigned CRC = lodepng_crc32(&chunk[4], length + 4);
embeddedartists 0:b567d56a59d7 2419 lodepng_set32bitInt(chunk + 8 + length, CRC);
embeddedartists 0:b567d56a59d7 2420 }
embeddedartists 0:b567d56a59d7 2421
embeddedartists 0:b567d56a59d7 2422 unsigned char* lodepng_chunk_next(unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2423 {
embeddedartists 0:b567d56a59d7 2424 unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
embeddedartists 0:b567d56a59d7 2425 return &chunk[total_chunk_length];
embeddedartists 0:b567d56a59d7 2426 }
embeddedartists 0:b567d56a59d7 2427
embeddedartists 0:b567d56a59d7 2428 const unsigned char* lodepng_chunk_next_const(const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2429 {
embeddedartists 0:b567d56a59d7 2430 unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
embeddedartists 0:b567d56a59d7 2431 return &chunk[total_chunk_length];
embeddedartists 0:b567d56a59d7 2432 }
embeddedartists 0:b567d56a59d7 2433
embeddedartists 0:b567d56a59d7 2434 unsigned lodepng_chunk_append(unsigned char** out, size_t* outlength, const unsigned char* chunk)
embeddedartists 0:b567d56a59d7 2435 {
embeddedartists 0:b567d56a59d7 2436 unsigned i;
embeddedartists 0:b567d56a59d7 2437 unsigned total_chunk_length = lodepng_chunk_length(chunk) + 12;
embeddedartists 0:b567d56a59d7 2438 unsigned char *chunk_start, *new_buffer;
embeddedartists 0:b567d56a59d7 2439 size_t new_length = (*outlength) + total_chunk_length;
embeddedartists 0:b567d56a59d7 2440 if(new_length < total_chunk_length || new_length < (*outlength)) return 77; /*integer overflow happened*/
embeddedartists 0:b567d56a59d7 2441
embeddedartists 0:b567d56a59d7 2442 new_buffer = (unsigned char*)lodepng_realloc(*out, new_length);
embeddedartists 0:b567d56a59d7 2443 if(!new_buffer) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 2444 (*out) = new_buffer;
embeddedartists 0:b567d56a59d7 2445 (*outlength) = new_length;
embeddedartists 0:b567d56a59d7 2446 chunk_start = &(*out)[new_length - total_chunk_length];
embeddedartists 0:b567d56a59d7 2447
embeddedartists 0:b567d56a59d7 2448 for(i = 0; i < total_chunk_length; i++) chunk_start[i] = chunk[i];
embeddedartists 0:b567d56a59d7 2449
embeddedartists 0:b567d56a59d7 2450 return 0;
embeddedartists 0:b567d56a59d7 2451 }
embeddedartists 0:b567d56a59d7 2452
embeddedartists 0:b567d56a59d7 2453 unsigned lodepng_chunk_create(unsigned char** out, size_t* outlength, unsigned length,
embeddedartists 0:b567d56a59d7 2454 const char* type, const unsigned char* data)
embeddedartists 0:b567d56a59d7 2455 {
embeddedartists 0:b567d56a59d7 2456 unsigned i;
embeddedartists 0:b567d56a59d7 2457 unsigned char *chunk, *new_buffer;
embeddedartists 0:b567d56a59d7 2458 size_t new_length = (*outlength) + length + 12;
embeddedartists 0:b567d56a59d7 2459 if(new_length < length + 12 || new_length < (*outlength)) return 77; /*integer overflow happened*/
embeddedartists 0:b567d56a59d7 2460 new_buffer = (unsigned char*)lodepng_realloc(*out, new_length);
embeddedartists 0:b567d56a59d7 2461 if(!new_buffer) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 2462 (*out) = new_buffer;
embeddedartists 0:b567d56a59d7 2463 (*outlength) = new_length;
embeddedartists 0:b567d56a59d7 2464 chunk = &(*out)[(*outlength) - length - 12];
embeddedartists 0:b567d56a59d7 2465
embeddedartists 0:b567d56a59d7 2466 /*1: length*/
embeddedartists 0:b567d56a59d7 2467 lodepng_set32bitInt(chunk, (unsigned)length);
embeddedartists 0:b567d56a59d7 2468
embeddedartists 0:b567d56a59d7 2469 /*2: chunk name (4 letters)*/
embeddedartists 0:b567d56a59d7 2470 chunk[4] = type[0];
embeddedartists 0:b567d56a59d7 2471 chunk[5] = type[1];
embeddedartists 0:b567d56a59d7 2472 chunk[6] = type[2];
embeddedartists 0:b567d56a59d7 2473 chunk[7] = type[3];
embeddedartists 0:b567d56a59d7 2474
embeddedartists 0:b567d56a59d7 2475 /*3: the data*/
embeddedartists 0:b567d56a59d7 2476 for(i = 0; i < length; i++) chunk[8 + i] = data[i];
embeddedartists 0:b567d56a59d7 2477
embeddedartists 0:b567d56a59d7 2478 /*4: CRC (of the chunkname characters and the data)*/
embeddedartists 0:b567d56a59d7 2479 lodepng_chunk_generate_crc(chunk);
embeddedartists 0:b567d56a59d7 2480
embeddedartists 0:b567d56a59d7 2481 return 0;
embeddedartists 0:b567d56a59d7 2482 }
embeddedartists 0:b567d56a59d7 2483
embeddedartists 0:b567d56a59d7 2484 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2485 /* / Color types and such / */
embeddedartists 0:b567d56a59d7 2486 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2487
embeddedartists 0:b567d56a59d7 2488 /*return type is a LodePNG error code*/
embeddedartists 0:b567d56a59d7 2489 static unsigned checkColorValidity(LodePNGColorType colortype, unsigned bd) /*bd = bitdepth*/
embeddedartists 0:b567d56a59d7 2490 {
embeddedartists 0:b567d56a59d7 2491 switch(colortype)
embeddedartists 0:b567d56a59d7 2492 {
embeddedartists 0:b567d56a59d7 2493 case 0: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8 || bd == 16)) return 37; break; /*grey*/
embeddedartists 0:b567d56a59d7 2494 case 2: if(!( bd == 8 || bd == 16)) return 37; break; /*RGB*/
embeddedartists 0:b567d56a59d7 2495 case 3: if(!(bd == 1 || bd == 2 || bd == 4 || bd == 8 )) return 37; break; /*palette*/
embeddedartists 0:b567d56a59d7 2496 case 4: if(!( bd == 8 || bd == 16)) return 37; break; /*grey + alpha*/
embeddedartists 0:b567d56a59d7 2497 case 6: if(!( bd == 8 || bd == 16)) return 37; break; /*RGBA*/
embeddedartists 0:b567d56a59d7 2498 default: return 31;
embeddedartists 0:b567d56a59d7 2499 }
embeddedartists 0:b567d56a59d7 2500 return 0; /*allowed color type / bits combination*/
embeddedartists 0:b567d56a59d7 2501 }
embeddedartists 0:b567d56a59d7 2502
embeddedartists 0:b567d56a59d7 2503 static unsigned getNumColorChannels(LodePNGColorType colortype)
embeddedartists 0:b567d56a59d7 2504 {
embeddedartists 0:b567d56a59d7 2505 switch(colortype)
embeddedartists 0:b567d56a59d7 2506 {
embeddedartists 0:b567d56a59d7 2507 case 0: return 1; /*grey*/
embeddedartists 0:b567d56a59d7 2508 case 2: return 3; /*RGB*/
embeddedartists 0:b567d56a59d7 2509 case 3: return 1; /*palette*/
embeddedartists 0:b567d56a59d7 2510 case 4: return 2; /*grey + alpha*/
embeddedartists 0:b567d56a59d7 2511 case 6: return 4; /*RGBA*/
embeddedartists 0:b567d56a59d7 2512 }
embeddedartists 0:b567d56a59d7 2513 return 0; /*unexisting color type*/
embeddedartists 0:b567d56a59d7 2514 }
embeddedartists 0:b567d56a59d7 2515
embeddedartists 0:b567d56a59d7 2516 static unsigned lodepng_get_bpp_lct(LodePNGColorType colortype, unsigned bitdepth)
embeddedartists 0:b567d56a59d7 2517 {
embeddedartists 0:b567d56a59d7 2518 /*bits per pixel is amount of channels * bits per channel*/
embeddedartists 0:b567d56a59d7 2519 return getNumColorChannels(colortype) * bitdepth;
embeddedartists 0:b567d56a59d7 2520 }
embeddedartists 0:b567d56a59d7 2521
embeddedartists 0:b567d56a59d7 2522 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2523
embeddedartists 0:b567d56a59d7 2524 void lodepng_color_mode_init(LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2525 {
embeddedartists 0:b567d56a59d7 2526 info->key_defined = 0;
embeddedartists 0:b567d56a59d7 2527 info->key_r = info->key_g = info->key_b = 0;
embeddedartists 0:b567d56a59d7 2528 info->colortype = LCT_RGBA;
embeddedartists 0:b567d56a59d7 2529 info->bitdepth = 8;
embeddedartists 0:b567d56a59d7 2530 info->palette = 0;
embeddedartists 0:b567d56a59d7 2531 info->palettesize = 0;
embeddedartists 0:b567d56a59d7 2532 }
embeddedartists 0:b567d56a59d7 2533
embeddedartists 0:b567d56a59d7 2534 void lodepng_color_mode_cleanup(LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2535 {
embeddedartists 0:b567d56a59d7 2536 lodepng_palette_clear(info);
embeddedartists 0:b567d56a59d7 2537 }
embeddedartists 0:b567d56a59d7 2538
embeddedartists 0:b567d56a59d7 2539 unsigned lodepng_color_mode_copy(LodePNGColorMode* dest, const LodePNGColorMode* source)
embeddedartists 0:b567d56a59d7 2540 {
embeddedartists 0:b567d56a59d7 2541 size_t i;
embeddedartists 0:b567d56a59d7 2542 lodepng_color_mode_cleanup(dest);
embeddedartists 0:b567d56a59d7 2543 *dest = *source;
embeddedartists 0:b567d56a59d7 2544 if(source->palette)
embeddedartists 0:b567d56a59d7 2545 {
embeddedartists 0:b567d56a59d7 2546 dest->palette = (unsigned char*)lodepng_malloc(1024);
embeddedartists 0:b567d56a59d7 2547 if(!dest->palette && source->palettesize) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 2548 for(i = 0; i < source->palettesize * 4; i++) dest->palette[i] = source->palette[i];
embeddedartists 0:b567d56a59d7 2549 }
embeddedartists 0:b567d56a59d7 2550 return 0;
embeddedartists 0:b567d56a59d7 2551 }
embeddedartists 0:b567d56a59d7 2552
embeddedartists 0:b567d56a59d7 2553 static int lodepng_color_mode_equal(const LodePNGColorMode* a, const LodePNGColorMode* b)
embeddedartists 0:b567d56a59d7 2554 {
embeddedartists 0:b567d56a59d7 2555 size_t i;
embeddedartists 0:b567d56a59d7 2556 if(a->colortype != b->colortype) return 0;
embeddedartists 0:b567d56a59d7 2557 if(a->bitdepth != b->bitdepth) return 0;
embeddedartists 0:b567d56a59d7 2558 if(a->key_defined != b->key_defined) return 0;
embeddedartists 0:b567d56a59d7 2559 if(a->key_defined)
embeddedartists 0:b567d56a59d7 2560 {
embeddedartists 0:b567d56a59d7 2561 if(a->key_r != b->key_r) return 0;
embeddedartists 0:b567d56a59d7 2562 if(a->key_g != b->key_g) return 0;
embeddedartists 0:b567d56a59d7 2563 if(a->key_b != b->key_b) return 0;
embeddedartists 0:b567d56a59d7 2564 }
embeddedartists 0:b567d56a59d7 2565 if(a->palettesize != b->palettesize) return 0;
embeddedartists 0:b567d56a59d7 2566 for(i = 0; i < a->palettesize * 4; i++)
embeddedartists 0:b567d56a59d7 2567 {
embeddedartists 0:b567d56a59d7 2568 if(a->palette[i] != b->palette[i]) return 0;
embeddedartists 0:b567d56a59d7 2569 }
embeddedartists 0:b567d56a59d7 2570 return 1;
embeddedartists 0:b567d56a59d7 2571 }
embeddedartists 0:b567d56a59d7 2572
embeddedartists 0:b567d56a59d7 2573 void lodepng_palette_clear(LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2574 {
embeddedartists 0:b567d56a59d7 2575 if(info->palette) lodepng_free(info->palette);
embeddedartists 0:b567d56a59d7 2576 info->palette = 0;
embeddedartists 0:b567d56a59d7 2577 info->palettesize = 0;
embeddedartists 0:b567d56a59d7 2578 }
embeddedartists 0:b567d56a59d7 2579
embeddedartists 0:b567d56a59d7 2580 unsigned lodepng_palette_add(LodePNGColorMode* info,
embeddedartists 0:b567d56a59d7 2581 unsigned char r, unsigned char g, unsigned char b, unsigned char a)
embeddedartists 0:b567d56a59d7 2582 {
embeddedartists 0:b567d56a59d7 2583 unsigned char* data;
embeddedartists 0:b567d56a59d7 2584 /*the same resize technique as C++ std::vectors is used, and here it's made so that for a palette with
embeddedartists 0:b567d56a59d7 2585 the max of 256 colors, it'll have the exact alloc size*/
embeddedartists 0:b567d56a59d7 2586 if(!info->palette) /*allocate palette if empty*/
embeddedartists 0:b567d56a59d7 2587 {
embeddedartists 0:b567d56a59d7 2588 /*room for 256 colors with 4 bytes each*/
embeddedartists 0:b567d56a59d7 2589 data = (unsigned char*)lodepng_realloc(info->palette, 1024);
embeddedartists 0:b567d56a59d7 2590 if(!data) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 2591 else info->palette = data;
embeddedartists 0:b567d56a59d7 2592 }
embeddedartists 0:b567d56a59d7 2593 info->palette[4 * info->palettesize + 0] = r;
embeddedartists 0:b567d56a59d7 2594 info->palette[4 * info->palettesize + 1] = g;
embeddedartists 0:b567d56a59d7 2595 info->palette[4 * info->palettesize + 2] = b;
embeddedartists 0:b567d56a59d7 2596 info->palette[4 * info->palettesize + 3] = a;
embeddedartists 0:b567d56a59d7 2597 info->palettesize++;
embeddedartists 0:b567d56a59d7 2598 return 0;
embeddedartists 0:b567d56a59d7 2599 }
embeddedartists 0:b567d56a59d7 2600
embeddedartists 0:b567d56a59d7 2601 unsigned lodepng_get_bpp(const LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2602 {
embeddedartists 0:b567d56a59d7 2603 /*calculate bits per pixel out of colortype and bitdepth*/
embeddedartists 0:b567d56a59d7 2604 return lodepng_get_bpp_lct(info->colortype, info->bitdepth);
embeddedartists 0:b567d56a59d7 2605 }
embeddedartists 0:b567d56a59d7 2606
embeddedartists 0:b567d56a59d7 2607 unsigned lodepng_get_channels(const LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2608 {
embeddedartists 0:b567d56a59d7 2609 return getNumColorChannels(info->colortype);
embeddedartists 0:b567d56a59d7 2610 }
embeddedartists 0:b567d56a59d7 2611
embeddedartists 0:b567d56a59d7 2612 unsigned lodepng_is_greyscale_type(const LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2613 {
embeddedartists 0:b567d56a59d7 2614 return info->colortype == LCT_GREY || info->colortype == LCT_GREY_ALPHA;
embeddedartists 0:b567d56a59d7 2615 }
embeddedartists 0:b567d56a59d7 2616
embeddedartists 0:b567d56a59d7 2617 unsigned lodepng_is_alpha_type(const LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2618 {
embeddedartists 0:b567d56a59d7 2619 return (info->colortype & 4) != 0; /*4 or 6*/
embeddedartists 0:b567d56a59d7 2620 }
embeddedartists 0:b567d56a59d7 2621
embeddedartists 0:b567d56a59d7 2622 unsigned lodepng_is_palette_type(const LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2623 {
embeddedartists 0:b567d56a59d7 2624 return info->colortype == LCT_PALETTE;
embeddedartists 0:b567d56a59d7 2625 }
embeddedartists 0:b567d56a59d7 2626
embeddedartists 0:b567d56a59d7 2627 unsigned lodepng_has_palette_alpha(const LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2628 {
embeddedartists 0:b567d56a59d7 2629 size_t i;
embeddedartists 0:b567d56a59d7 2630 for(i = 0; i < info->palettesize; i++)
embeddedartists 0:b567d56a59d7 2631 {
embeddedartists 0:b567d56a59d7 2632 if(info->palette[i * 4 + 3] < 255) return 1;
embeddedartists 0:b567d56a59d7 2633 }
embeddedartists 0:b567d56a59d7 2634 return 0;
embeddedartists 0:b567d56a59d7 2635 }
embeddedartists 0:b567d56a59d7 2636
embeddedartists 0:b567d56a59d7 2637 unsigned lodepng_can_have_alpha(const LodePNGColorMode* info)
embeddedartists 0:b567d56a59d7 2638 {
embeddedartists 0:b567d56a59d7 2639 return info->key_defined
embeddedartists 0:b567d56a59d7 2640 || lodepng_is_alpha_type(info)
embeddedartists 0:b567d56a59d7 2641 || lodepng_has_palette_alpha(info);
embeddedartists 0:b567d56a59d7 2642 }
embeddedartists 0:b567d56a59d7 2643
embeddedartists 0:b567d56a59d7 2644 size_t lodepng_get_raw_size(unsigned w, unsigned h, const LodePNGColorMode* color)
embeddedartists 0:b567d56a59d7 2645 {
embeddedartists 0:b567d56a59d7 2646 return (w * h * lodepng_get_bpp(color) + 7) / 8;
embeddedartists 0:b567d56a59d7 2647 }
embeddedartists 0:b567d56a59d7 2648
embeddedartists 0:b567d56a59d7 2649 size_t lodepng_get_raw_size_lct(unsigned w, unsigned h, LodePNGColorType colortype, unsigned bitdepth)
embeddedartists 0:b567d56a59d7 2650 {
embeddedartists 0:b567d56a59d7 2651 return (w * h * lodepng_get_bpp_lct(colortype, bitdepth) + 7) / 8;
embeddedartists 0:b567d56a59d7 2652 }
embeddedartists 0:b567d56a59d7 2653
embeddedartists 0:b567d56a59d7 2654 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
embeddedartists 0:b567d56a59d7 2655
embeddedartists 0:b567d56a59d7 2656 static void LodePNGUnknownChunks_init(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2657 {
embeddedartists 0:b567d56a59d7 2658 unsigned i;
embeddedartists 0:b567d56a59d7 2659 for(i = 0; i < 3; i++) info->unknown_chunks_data[i] = 0;
embeddedartists 0:b567d56a59d7 2660 for(i = 0; i < 3; i++) info->unknown_chunks_size[i] = 0;
embeddedartists 0:b567d56a59d7 2661 }
embeddedartists 0:b567d56a59d7 2662
embeddedartists 0:b567d56a59d7 2663 static void LodePNGUnknownChunks_cleanup(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2664 {
embeddedartists 0:b567d56a59d7 2665 unsigned i;
embeddedartists 0:b567d56a59d7 2666 for(i = 0; i < 3; i++) lodepng_free(info->unknown_chunks_data[i]);
embeddedartists 0:b567d56a59d7 2667 }
embeddedartists 0:b567d56a59d7 2668
embeddedartists 0:b567d56a59d7 2669 static unsigned LodePNGUnknownChunks_copy(LodePNGInfo* dest, const LodePNGInfo* src)
embeddedartists 0:b567d56a59d7 2670 {
embeddedartists 0:b567d56a59d7 2671 unsigned i;
embeddedartists 0:b567d56a59d7 2672
embeddedartists 0:b567d56a59d7 2673 LodePNGUnknownChunks_cleanup(dest);
embeddedartists 0:b567d56a59d7 2674
embeddedartists 0:b567d56a59d7 2675 for(i = 0; i < 3; i++)
embeddedartists 0:b567d56a59d7 2676 {
embeddedartists 0:b567d56a59d7 2677 size_t j;
embeddedartists 0:b567d56a59d7 2678 dest->unknown_chunks_size[i] = src->unknown_chunks_size[i];
embeddedartists 0:b567d56a59d7 2679 dest->unknown_chunks_data[i] = (unsigned char*)lodepng_malloc(src->unknown_chunks_size[i]);
embeddedartists 0:b567d56a59d7 2680 if(!dest->unknown_chunks_data[i] && dest->unknown_chunks_size[i]) return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 2681 for(j = 0; j < src->unknown_chunks_size[i]; j++)
embeddedartists 0:b567d56a59d7 2682 {
embeddedartists 0:b567d56a59d7 2683 dest->unknown_chunks_data[i][j] = src->unknown_chunks_data[i][j];
embeddedartists 0:b567d56a59d7 2684 }
embeddedartists 0:b567d56a59d7 2685 }
embeddedartists 0:b567d56a59d7 2686
embeddedartists 0:b567d56a59d7 2687 return 0;
embeddedartists 0:b567d56a59d7 2688 }
embeddedartists 0:b567d56a59d7 2689
embeddedartists 0:b567d56a59d7 2690 /******************************************************************************/
embeddedartists 0:b567d56a59d7 2691
embeddedartists 0:b567d56a59d7 2692 static void LodePNGText_init(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2693 {
embeddedartists 0:b567d56a59d7 2694 info->text_num = 0;
embeddedartists 0:b567d56a59d7 2695 info->text_keys = NULL;
embeddedartists 0:b567d56a59d7 2696 info->text_strings = NULL;
embeddedartists 0:b567d56a59d7 2697 }
embeddedartists 0:b567d56a59d7 2698
embeddedartists 0:b567d56a59d7 2699 static void LodePNGText_cleanup(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2700 {
embeddedartists 0:b567d56a59d7 2701 size_t i;
embeddedartists 0:b567d56a59d7 2702 for(i = 0; i < info->text_num; i++)
embeddedartists 0:b567d56a59d7 2703 {
embeddedartists 0:b567d56a59d7 2704 string_cleanup(&info->text_keys[i]);
embeddedartists 0:b567d56a59d7 2705 string_cleanup(&info->text_strings[i]);
embeddedartists 0:b567d56a59d7 2706 }
embeddedartists 0:b567d56a59d7 2707 lodepng_free(info->text_keys);
embeddedartists 0:b567d56a59d7 2708 lodepng_free(info->text_strings);
embeddedartists 0:b567d56a59d7 2709 }
embeddedartists 0:b567d56a59d7 2710
embeddedartists 0:b567d56a59d7 2711 static unsigned LodePNGText_copy(LodePNGInfo* dest, const LodePNGInfo* source)
embeddedartists 0:b567d56a59d7 2712 {
embeddedartists 0:b567d56a59d7 2713 size_t i = 0;
embeddedartists 0:b567d56a59d7 2714 dest->text_keys = 0;
embeddedartists 0:b567d56a59d7 2715 dest->text_strings = 0;
embeddedartists 0:b567d56a59d7 2716 dest->text_num = 0;
embeddedartists 0:b567d56a59d7 2717 for(i = 0; i < source->text_num; i++)
embeddedartists 0:b567d56a59d7 2718 {
embeddedartists 0:b567d56a59d7 2719 CERROR_TRY_RETURN(lodepng_add_text(dest, source->text_keys[i], source->text_strings[i]));
embeddedartists 0:b567d56a59d7 2720 }
embeddedartists 0:b567d56a59d7 2721 return 0;
embeddedartists 0:b567d56a59d7 2722 }
embeddedartists 0:b567d56a59d7 2723
embeddedartists 0:b567d56a59d7 2724 void lodepng_clear_text(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2725 {
embeddedartists 0:b567d56a59d7 2726 LodePNGText_cleanup(info);
embeddedartists 0:b567d56a59d7 2727 }
embeddedartists 0:b567d56a59d7 2728
embeddedartists 0:b567d56a59d7 2729 unsigned lodepng_add_text(LodePNGInfo* info, const char* key, const char* str)
embeddedartists 0:b567d56a59d7 2730 {
embeddedartists 0:b567d56a59d7 2731 char** new_keys = (char**)(lodepng_realloc(info->text_keys, sizeof(char*) * (info->text_num + 1)));
embeddedartists 0:b567d56a59d7 2732 char** new_strings = (char**)(lodepng_realloc(info->text_strings, sizeof(char*) * (info->text_num + 1)));
embeddedartists 0:b567d56a59d7 2733 if(!new_keys || !new_strings)
embeddedartists 0:b567d56a59d7 2734 {
embeddedartists 0:b567d56a59d7 2735 lodepng_free(new_keys);
embeddedartists 0:b567d56a59d7 2736 lodepng_free(new_strings);
embeddedartists 0:b567d56a59d7 2737 return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 2738 }
embeddedartists 0:b567d56a59d7 2739
embeddedartists 0:b567d56a59d7 2740 info->text_num++;
embeddedartists 0:b567d56a59d7 2741 info->text_keys = new_keys;
embeddedartists 0:b567d56a59d7 2742 info->text_strings = new_strings;
embeddedartists 0:b567d56a59d7 2743
embeddedartists 0:b567d56a59d7 2744 string_init(&info->text_keys[info->text_num - 1]);
embeddedartists 0:b567d56a59d7 2745 string_set(&info->text_keys[info->text_num - 1], key);
embeddedartists 0:b567d56a59d7 2746
embeddedartists 0:b567d56a59d7 2747 string_init(&info->text_strings[info->text_num - 1]);
embeddedartists 0:b567d56a59d7 2748 string_set(&info->text_strings[info->text_num - 1], str);
embeddedartists 0:b567d56a59d7 2749
embeddedartists 0:b567d56a59d7 2750 return 0;
embeddedartists 0:b567d56a59d7 2751 }
embeddedartists 0:b567d56a59d7 2752
embeddedartists 0:b567d56a59d7 2753 /******************************************************************************/
embeddedartists 0:b567d56a59d7 2754
embeddedartists 0:b567d56a59d7 2755 static void LodePNGIText_init(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2756 {
embeddedartists 0:b567d56a59d7 2757 info->itext_num = 0;
embeddedartists 0:b567d56a59d7 2758 info->itext_keys = NULL;
embeddedartists 0:b567d56a59d7 2759 info->itext_langtags = NULL;
embeddedartists 0:b567d56a59d7 2760 info->itext_transkeys = NULL;
embeddedartists 0:b567d56a59d7 2761 info->itext_strings = NULL;
embeddedartists 0:b567d56a59d7 2762 }
embeddedartists 0:b567d56a59d7 2763
embeddedartists 0:b567d56a59d7 2764 static void LodePNGIText_cleanup(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2765 {
embeddedartists 0:b567d56a59d7 2766 size_t i;
embeddedartists 0:b567d56a59d7 2767 for(i = 0; i < info->itext_num; i++)
embeddedartists 0:b567d56a59d7 2768 {
embeddedartists 0:b567d56a59d7 2769 string_cleanup(&info->itext_keys[i]);
embeddedartists 0:b567d56a59d7 2770 string_cleanup(&info->itext_langtags[i]);
embeddedartists 0:b567d56a59d7 2771 string_cleanup(&info->itext_transkeys[i]);
embeddedartists 0:b567d56a59d7 2772 string_cleanup(&info->itext_strings[i]);
embeddedartists 0:b567d56a59d7 2773 }
embeddedartists 0:b567d56a59d7 2774 lodepng_free(info->itext_keys);
embeddedartists 0:b567d56a59d7 2775 lodepng_free(info->itext_langtags);
embeddedartists 0:b567d56a59d7 2776 lodepng_free(info->itext_transkeys);
embeddedartists 0:b567d56a59d7 2777 lodepng_free(info->itext_strings);
embeddedartists 0:b567d56a59d7 2778 }
embeddedartists 0:b567d56a59d7 2779
embeddedartists 0:b567d56a59d7 2780 static unsigned LodePNGIText_copy(LodePNGInfo* dest, const LodePNGInfo* source)
embeddedartists 0:b567d56a59d7 2781 {
embeddedartists 0:b567d56a59d7 2782 size_t i = 0;
embeddedartists 0:b567d56a59d7 2783 dest->itext_keys = 0;
embeddedartists 0:b567d56a59d7 2784 dest->itext_langtags = 0;
embeddedartists 0:b567d56a59d7 2785 dest->itext_transkeys = 0;
embeddedartists 0:b567d56a59d7 2786 dest->itext_strings = 0;
embeddedartists 0:b567d56a59d7 2787 dest->itext_num = 0;
embeddedartists 0:b567d56a59d7 2788 for(i = 0; i < source->itext_num; i++)
embeddedartists 0:b567d56a59d7 2789 {
embeddedartists 0:b567d56a59d7 2790 CERROR_TRY_RETURN(lodepng_add_itext(dest, source->itext_keys[i], source->itext_langtags[i],
embeddedartists 0:b567d56a59d7 2791 source->itext_transkeys[i], source->itext_strings[i]));
embeddedartists 0:b567d56a59d7 2792 }
embeddedartists 0:b567d56a59d7 2793 return 0;
embeddedartists 0:b567d56a59d7 2794 }
embeddedartists 0:b567d56a59d7 2795
embeddedartists 0:b567d56a59d7 2796 void lodepng_clear_itext(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2797 {
embeddedartists 0:b567d56a59d7 2798 LodePNGIText_cleanup(info);
embeddedartists 0:b567d56a59d7 2799 }
embeddedartists 0:b567d56a59d7 2800
embeddedartists 0:b567d56a59d7 2801 unsigned lodepng_add_itext(LodePNGInfo* info, const char* key, const char* langtag,
embeddedartists 0:b567d56a59d7 2802 const char* transkey, const char* str)
embeddedartists 0:b567d56a59d7 2803 {
embeddedartists 0:b567d56a59d7 2804 char** new_keys = (char**)(lodepng_realloc(info->itext_keys, sizeof(char*) * (info->itext_num + 1)));
embeddedartists 0:b567d56a59d7 2805 char** new_langtags = (char**)(lodepng_realloc(info->itext_langtags, sizeof(char*) * (info->itext_num + 1)));
embeddedartists 0:b567d56a59d7 2806 char** new_transkeys = (char**)(lodepng_realloc(info->itext_transkeys, sizeof(char*) * (info->itext_num + 1)));
embeddedartists 0:b567d56a59d7 2807 char** new_strings = (char**)(lodepng_realloc(info->itext_strings, sizeof(char*) * (info->itext_num + 1)));
embeddedartists 0:b567d56a59d7 2808 if(!new_keys || !new_langtags || !new_transkeys || !new_strings)
embeddedartists 0:b567d56a59d7 2809 {
embeddedartists 0:b567d56a59d7 2810 lodepng_free(new_keys);
embeddedartists 0:b567d56a59d7 2811 lodepng_free(new_langtags);
embeddedartists 0:b567d56a59d7 2812 lodepng_free(new_transkeys);
embeddedartists 0:b567d56a59d7 2813 lodepng_free(new_strings);
embeddedartists 0:b567d56a59d7 2814 return 83; /*alloc fail*/
embeddedartists 0:b567d56a59d7 2815 }
embeddedartists 0:b567d56a59d7 2816
embeddedartists 0:b567d56a59d7 2817 info->itext_num++;
embeddedartists 0:b567d56a59d7 2818 info->itext_keys = new_keys;
embeddedartists 0:b567d56a59d7 2819 info->itext_langtags = new_langtags;
embeddedartists 0:b567d56a59d7 2820 info->itext_transkeys = new_transkeys;
embeddedartists 0:b567d56a59d7 2821 info->itext_strings = new_strings;
embeddedartists 0:b567d56a59d7 2822
embeddedartists 0:b567d56a59d7 2823 string_init(&info->itext_keys[info->itext_num - 1]);
embeddedartists 0:b567d56a59d7 2824 string_set(&info->itext_keys[info->itext_num - 1], key);
embeddedartists 0:b567d56a59d7 2825
embeddedartists 0:b567d56a59d7 2826 string_init(&info->itext_langtags[info->itext_num - 1]);
embeddedartists 0:b567d56a59d7 2827 string_set(&info->itext_langtags[info->itext_num - 1], langtag);
embeddedartists 0:b567d56a59d7 2828
embeddedartists 0:b567d56a59d7 2829 string_init(&info->itext_transkeys[info->itext_num - 1]);
embeddedartists 0:b567d56a59d7 2830 string_set(&info->itext_transkeys[info->itext_num - 1], transkey);
embeddedartists 0:b567d56a59d7 2831
embeddedartists 0:b567d56a59d7 2832 string_init(&info->itext_strings[info->itext_num - 1]);
embeddedartists 0:b567d56a59d7 2833 string_set(&info->itext_strings[info->itext_num - 1], str);
embeddedartists 0:b567d56a59d7 2834
embeddedartists 0:b567d56a59d7 2835 return 0;
embeddedartists 0:b567d56a59d7 2836 }
embeddedartists 0:b567d56a59d7 2837 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
embeddedartists 0:b567d56a59d7 2838
embeddedartists 0:b567d56a59d7 2839 void lodepng_info_init(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2840 {
embeddedartists 0:b567d56a59d7 2841 lodepng_color_mode_init(&info->color);
embeddedartists 0:b567d56a59d7 2842 info->interlace_method = 0;
embeddedartists 0:b567d56a59d7 2843 info->compression_method = 0;
embeddedartists 0:b567d56a59d7 2844 info->filter_method = 0;
embeddedartists 0:b567d56a59d7 2845 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
embeddedartists 0:b567d56a59d7 2846 info->background_defined = 0;
embeddedartists 0:b567d56a59d7 2847 info->background_r = info->background_g = info->background_b = 0;
embeddedartists 0:b567d56a59d7 2848
embeddedartists 0:b567d56a59d7 2849 LodePNGText_init(info);
embeddedartists 0:b567d56a59d7 2850 LodePNGIText_init(info);
embeddedartists 0:b567d56a59d7 2851
embeddedartists 0:b567d56a59d7 2852 info->time_defined = 0;
embeddedartists 0:b567d56a59d7 2853 info->phys_defined = 0;
embeddedartists 0:b567d56a59d7 2854
embeddedartists 0:b567d56a59d7 2855 LodePNGUnknownChunks_init(info);
embeddedartists 0:b567d56a59d7 2856 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
embeddedartists 0:b567d56a59d7 2857 }
embeddedartists 0:b567d56a59d7 2858
embeddedartists 0:b567d56a59d7 2859 void lodepng_info_cleanup(LodePNGInfo* info)
embeddedartists 0:b567d56a59d7 2860 {
embeddedartists 0:b567d56a59d7 2861 lodepng_color_mode_cleanup(&info->color);
embeddedartists 0:b567d56a59d7 2862 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
embeddedartists 0:b567d56a59d7 2863 LodePNGText_cleanup(info);
embeddedartists 0:b567d56a59d7 2864 LodePNGIText_cleanup(info);
embeddedartists 0:b567d56a59d7 2865
embeddedartists 0:b567d56a59d7 2866 LodePNGUnknownChunks_cleanup(info);
embeddedartists 0:b567d56a59d7 2867 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
embeddedartists 0:b567d56a59d7 2868 }
embeddedartists 0:b567d56a59d7 2869
embeddedartists 0:b567d56a59d7 2870 unsigned lodepng_info_copy(LodePNGInfo* dest, const LodePNGInfo* source)
embeddedartists 0:b567d56a59d7 2871 {
embeddedartists 0:b567d56a59d7 2872 lodepng_info_cleanup(dest);
embeddedartists 0:b567d56a59d7 2873 *dest = *source;
embeddedartists 0:b567d56a59d7 2874 lodepng_color_mode_init(&dest->color);
embeddedartists 0:b567d56a59d7 2875 CERROR_TRY_RETURN(lodepng_color_mode_copy(&dest->color, &source->color));
embeddedartists 0:b567d56a59d7 2876
embeddedartists 0:b567d56a59d7 2877 #ifdef LODEPNG_COMPILE_ANCILLARY_CHUNKS
embeddedartists 0:b567d56a59d7 2878 CERROR_TRY_RETURN(LodePNGText_copy(dest, source));
embeddedartists 0:b567d56a59d7 2879 CERROR_TRY_RETURN(LodePNGIText_copy(dest, source));
embeddedartists 0:b567d56a59d7 2880
embeddedartists 0:b567d56a59d7 2881 LodePNGUnknownChunks_init(dest);
embeddedartists 0:b567d56a59d7 2882 CERROR_TRY_RETURN(LodePNGUnknownChunks_copy(dest, source));
embeddedartists 0:b567d56a59d7 2883 #endif /*LODEPNG_COMPILE_ANCILLARY_CHUNKS*/
embeddedartists 0:b567d56a59d7 2884 return 0;
embeddedartists 0:b567d56a59d7 2885 }
embeddedartists 0:b567d56a59d7 2886
embeddedartists 0:b567d56a59d7 2887 void lodepng_info_swap(LodePNGInfo* a, LodePNGInfo* b)
embeddedartists 0:b567d56a59d7 2888 {
embeddedartists 0:b567d56a59d7 2889 LodePNGInfo temp = *a;
embeddedartists 0:b567d56a59d7 2890 *a = *b;
embeddedartists 0:b567d56a59d7 2891 *b = temp;
embeddedartists 0:b567d56a59d7 2892 }
embeddedartists 0:b567d56a59d7 2893
embeddedartists 0:b567d56a59d7 2894 /* ////////////////////////////////////////////////////////////////////////// */
embeddedartists 0:b567d56a59d7 2895
embeddedartists 0:b567d56a59d7 2896 /*index: bitgroup index, bits: bitgroup size(1, 2 or 4), in: bitgroup value, out: octet array to add bits to*/
embeddedartists 0:b567d56a59d7 2897 static void addColorBits(unsigned char* out, size_t index, unsigned bits, unsigned in)
embeddedartists 0:b567d56a59d7 2898 {
embeddedartists 0:b567d56a59d7 2899 unsigned m = bits == 1 ? 7 : bits == 2 ? 3 : 1; /*8 / bits - 1*/
embeddedartists 0:b567d56a59d7 2900 /*p = the partial index in the byte, e.g. with 4 palettebits it is 0 for first half or 1 for second half*/
embeddedartists 0:b567d56a59d7 2901 unsigned p = index & m;
embeddedartists 0:b567d56a59d7 2902 in &= (1 << bits) - 1; /*filter out any other bits of the input value*/
embeddedartists 0:b567d56a59d7 2903 in = in << (bits * (m - p));
embeddedartists 0:b567d56a59d7 2904 if(p == 0) out[index * bits / 8] = in;
embeddedartists 0:b567d56a59d7 2905 else out[index * bits / 8] |= in;
embeddedartists 0:b567d56a59d7 2906 }
embeddedartists 0:b567d56a59d7 2907
embeddedartists 0:b567d56a59d7 2908 typedef struct ColorTree ColorTree;
embeddedartists 0:b567d56a59d7 2909
embeddedartists 0:b567d56a59d7 2910 /*
embeddedartists 0:b567d56a59d7 2911 One node of a color tree
embeddedartists 0:b567d56a59d7 2912 This is the data structure used to count the number of unique colors and to get a palette
embeddedartists 0:b567d56a59d7 2913 index for a color. It's like an octree, but because the alpha channel is used too, each
embeddedartists 0:b567d56a59d7 2914 node has 16 instead of 8 children.
embeddedartists 0:b567d56a59d7 2915 */
embeddedartists 0:b567d56a59d7 2916 struct ColorTree
embeddedartists 0:b567d56a59d7 2917 {
embeddedartists 0:b567d56a59d7 2918 ColorTree* children[16]; /*up to 16 pointers to ColorTree of next level*/
embeddedartists 0:b567d56a59d7 2919 int index; /*the payload. Only has a meaningful value if this is in the last level*/
embeddedartists 0:b567d56a59d7 2920 };
embeddedartists 0:b567d56a59d7 2921
embeddedartists 0:b567d56a59d7 2922 static void color_tree_init(ColorTree* tree)
embeddedartists 0:b567d56a59d7 2923 {
embeddedartists 0:b567d56a59d7 2924 int i;
embeddedartists 0:b567d56a59d7 2925 for(i = 0; i < 16; i++) tree->children[i] = 0;
embeddedartists 0:b567d56a59d7 2926 tree->index = -1;
embeddedartists 0:b567d56a59d7 2927 }
embeddedartists 0:b567d56a59d7 2928
embeddedartists 0:b567d56a59d7 2929 static void color_tree_cleanup(ColorTree* tree)
embeddedartists 0:b567d56a59d7 2930 {
embeddedartists 0:b567d56a59d7 2931 int i;
embeddedartists 0:b567d56a59d7 2932 for(i = 0; i < 16; i++)
embeddedartists 0:b567d56a59d7 2933 {
embeddedartists 0:b567d56a59d7 2934 if(tree->children[i])
embeddedartists 0:b567d56a59d7 2935 {
embeddedartists 0:b567d56a59d7 2936 color_tree_cleanup(tree->children[i]);
embeddedartists 0:b567d56a59d7 2937 lodepng_free(tree->children[i]);
embeddedartists 0:b567d56a59d7 2938 }
embeddedartists 0:b567d56a59d7 2939 }
embeddedartists 0:b567d56a59d7 2940 }
embeddedartists 0:b567d56a59d7 2941
embeddedartists 0:b567d56a59d7 2942 /*returns -1 if color not present, its index otherwise*/
embeddedartists 0:b567d56a59d7 2943 static int color_tree_get(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
embeddedartists 0:b567d56a59d7 2944 {
embeddedartists 0:b567d56a59d7 2945 int bit = 0;
embeddedartists 0:b567d56a59d7 2946 for(bit = 0; bit < 8; bit++)
embeddedartists 0:b567d56a59d7 2947 {
embeddedartists 0:b567d56a59d7 2948 int i = 8 * ((r >> bit) & 1) + 4 * ((g >> bit) & 1) + 2 * ((b >> bit) & 1) + 1 * ((a >> bit) & 1);
embeddedartists 0:b567d56a59d7 2949 if(!tree->children[i]) return -1;
embeddedartists 0:b567d56a59d7 2950 else tree = tree->children[i];
embeddedartists 0:b567d56a59d7 2951 }
embeddedartists 0:b567d56a59d7 2952 return tree ? tree->index : -1;
embeddedartists 0:b567d56a59d7 2953 }
embeddedartists 0:b567d56a59d7 2954
embeddedartists 0:b567d56a59d7 2955 #ifdef LODEPNG_COMPILE_ENCODER
embeddedartists 0:b567d56a59d7 2956 static int color_tree_has(ColorTree* tree, unsigned char r, unsigned char g, unsigned char b, unsigned char a)
embeddedartists 0:b567d56a59d7 2957 {
embeddedartists 0:b567d56a59d7 2958 return color_tree_get(tree, r, g, b, a) >= 0;
embeddedartists 0:b567d56a59d7 2959 }
embeddedartists 0:b567d56a59d7 2960 #endif /*LODEPNG_COMPILE_ENCODER*/
embeddedartists 0:b567d56a59d7 2961
embeddedartists 0:b567d56a59d7 2962 /*color is not allowed to already exist.
embeddedartists 0:b567d56a59d7 2963 Index should be >= 0 (it's signed to be compatible with using -1 for "doesn't exist")*/
embeddedartists 0:b567d56a59d7 2964 static void color_tree_add(ColorTree* tree,
embeddedartists 0:b567d56a59d7 2965 unsigned char r, unsigned char g, unsigned char b, unsigned char a, int index)
embeddedartists 0:b567d56a59d7 2966 {
embeddedartists 0:b567d56a59d7 2967 int bit;
embeddedartists 0:b567d56a59d7 2968 for(bit = 0; bit < 8; bit++)
embeddedartists 0:b567d56a59d7 2969 {
embeddedartists 0:b567d56a59d7 2970 int i = 8 * ((r >> bit) & 1) + 4 * ((g >> bit) & 1) + 2 * ((b >> bit) & 1) + 1 * ((a >> bit) & 1);
embeddedartists 0:b567d56a59d7 2971 if(!tree->children[i])
embeddedartists 0:b567d56a59d7 2972 {
embeddedartists 0:b567d56a59d7 2973 tree->children[i] = (ColorTree*)lodepng_malloc(sizeof(ColorTree));
embeddedartists 0:b567d56a59d7 2974 color_tree_init(tree->children[i]);
embeddedartists 0:b567d56a59d7 2975 }
embeddedartists 0:b567d56a59d7 2976 tree = tree->children[i];
embeddedartists 0:b567d56a59d7 2977 }
embeddedartists 0:b567d56a59d7 2978 tree->index = index;
embeddedartists 0:b567d56a59d7 2979 }
embeddedartists 0:b567d56a59d7 2980
embeddedartists 0:b567d56a59d7 2981 /*put a pixel, given its RGBA color, into image of any color type*/
embeddedartists 0:b567d56a59d7 2982 static unsigned rgba8ToPixel(unsigned char* out, size_t i,
embeddedartists 0:b567d56a59d7 2983 const LodePNGColorMode* mode, ColorTree* tree /*for palette*/,
embeddedartists 0:b567d56a59d7 2984 unsigned char r, unsigned char g, unsigned char b, unsigned char a)
embeddedartists 0:b567d56a59d7 2985 {
embeddedartists 0:b567d56a59d7 2986 if(mode->colortype == LCT_GREY)
embeddedartists 0:b567d56a59d7 2987 {
embeddedartists 0:b567d56a59d7 2988 unsigned char grey = r; /*((unsigned short)r + g + b) / 3*/;
embeddedartists 0:b567d56a59d7 2989 if(mode->bitdepth == 8) out[i] = grey;
embeddedartists 0:b567d56a59d7 2990 else if(mode->bitdepth == 16) out[i * 2 + 0] = out[i * 2 + 1] = grey;
embeddedartists 0:b567d56a59d7 2991 else
embeddedartists 0:b567d56a59d7 2992 {
embeddedartists 0:b567d56a59d7 2993 /*take the most significant bits of grey*/
embeddedartists 0:b567d56a59d7 2994 grey = (grey >> (8 - mode->bitdepth)) & ((1 << mode->bitdepth) - 1);
embeddedartists 0:b567d56a59d7 2995 addColorBits(out, i, mode->bitdepth, grey);
embeddedartists 0:b567d56a59d7 2996 }
embeddedartists 0:b567d56a59d7 2997 }
embeddedartists 0:b567d56a59d7 2998 else if(mode->colortype == LCT_RGB)
embeddedartists 0:b567d56a59d7 2999 {
embeddedartists 0:b567d56a59d7 3000 if(mode->bitdepth == 8)
embeddedartists 0:b567d56a59d7 3001 {
embeddedartists 0:b567d56a59d7 3002 out[i * 3 + 0] = r;
embeddedartists 0:b567d56a59d7 3003 out[i * 3 + 1] = g;
embeddedartists 0:b567d56a59d7 3004 out[i * 3 + 2] = b;
embeddedartists 0:b567d56a59d7 3005 }
embeddedartists 0:b567d56a59d7 3006 else
embeddedartists 0:b567d56a59d7 3007 {
embeddedartists 0:b567d56a59d7 3008 out[i * 6 + 0] = out[i * 6 + 1] = r;
embeddedartists 0:b567d56a59d7 3009 out[i * 6 + 2] = out[i * 6 + 3] = g;
embeddedartists 0:b567d56a59d7 3010 out[i * 6 + 4] = out[i * 6 + 5] = b;
embeddedartists 0:b567d56a59d7 3011 }
embeddedartists 0:b567d56a59d7 3012 }
embeddedartists 0:b567d56a59d7 3013 else if(mode->colortype == LCT_PALETTE)
embeddedartists 0:b567d56a59d7 3014 {
embeddedartists 0:b567d56a59d7 3015 int index = color_tree_get(tree, r, g, b, a);
embeddedartists 0:b567d56a59d7 3016 if(index < 0) return 82; /*color not in palette*/
embeddedartists 0:b567d56a59d7 3017 if(mode->bitdepth == 8) out[i] = index;
embeddedartists 0:b567d56a59d7 3018 else addColorBits(out, i, mode->bitdepth, index);
embeddedartists 0:b567d56a59d7 3019 }
embeddedartists 0:b567d56a59d7 3020 else if(mode->colortype == LCT_GREY_ALPHA)
embeddedartists 0:b567d56a59d7 3021 {
embeddedartists 0:b567d56a59d7 3022 unsigned char grey = r; /*((unsigned short)r + g + b) / 3*/;
embeddedartists 0:b567d56a59d7 3023 if(mode->bitdepth == 8)
embeddedartists 0:b567d56a59d7 3024 {
embeddedartists 0:b567d56a59d7 3025 out[i * 2 + 0] = grey;
embeddedartists 0:b567d56a59d7 3026 out[i * 2 + 1] = a;
embeddedartists 0:b567d56a59d7 3027 }
embeddedartists 0:b567d56a59d7 3028 else if(mode->bitdepth == 16)
embeddedartists 0:b567d56a59d7 3029 {
embeddedartists 0:b567d56a59d7 3030 out[i * 4 + 0] = out[i * 4 + 1] = grey;
embeddedartists 0:b567d56a59d7 3031 out[i * 4 + 2] = out[i * 4 + 3] = a;
embeddedartists 0:b567d56a59d7 3032 }
embeddedartists 0:b567d56a59d7 3033 }
embeddedartists 0:b567d56a59d7 3034 else if(mode->colortype == LCT_RGBA)
embeddedartists 0:b567d56a59d7 3035 {
embeddedartists 0:b567d56a59d7 3036 if(mode->bitdepth == 8)
embeddedartists 0:b567d56a59d7 3037 {
embeddedartists 0:b567d56a59d7 3038 out[i * 4 + 0] = r;
embeddedartists 0:b567d56a59d7 3039 out[i * 4 + 1] = g;
embeddedartists 0:b567d56a59d7 3040 out[i * 4 + 2] = b;
embeddedartists 0:b567d56a59d7 3041 out[i * 4 + 3] = a;
embeddedartists 0:b567d56a59d7 3042 }
embeddedartists 0:b567d56a59d7 3043 else
embeddedartists 0:b567d56a59d7 3044 {
embeddedartists 0:b567d56a59d7 3045 out[i * 8 + 0] = out[i * 8 + 1] = r;