/* uPNG -- derived from LodePNG version 20100808 Copyright (c) 2005-2010 Lode Vandevenne Copyright (c) 2010 Sean Middleditch Copyright (c) 2020 Marvin Borner This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software. Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions: 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 3. This notice may not be removed or altered from any source distribution. */ #include #include #include #include #include #define MAKE_BYTE(b) ((b)&0xFF) #define MAKE_DWORD(a, b, c, d) \ ((MAKE_BYTE(a) << 24) | (MAKE_BYTE(b) << 16) | (MAKE_BYTE(c) << 8) | MAKE_BYTE(d)) #define MAKE_DWORD_PTR(p) MAKE_DWORD((p)[0], (p)[1], (p)[2], (p)[3]) #define CHUNK_IHDR MAKE_DWORD('I', 'H', 'D', 'R') #define CHUNK_IDAT MAKE_DWORD('I', 'D', 'A', 'T') #define CHUNK_IEND MAKE_DWORD('I', 'E', 'N', 'D') #define FIRST_LENGTH_CODE_INDEX 257 #define LAST_LENGTH_CODE_INDEX 285 #define NUM_DEFLATE_CODE_SYMBOLS \ 288 // 256 literals, the end code, some length codes, and 2 unused codes #define NUM_DISTANCE_SYMBOLS 32 // The distance codes have their own symbols, 30 used, 2 unused #define NUM_CODE_LENGTH_CODES \ 19 // The code length codes. 0-15: code lengths, 16: copy previous 3-6 times, 17: 3-10 zeros, 18: 11-138 zeros #define MAX_SYMBOLS 288 // Largest number of symbols used by any tree type #define DEFLATE_CODE_BITLEN 15 #define DISTANCE_BITLEN 15 #define CODE_LENGTH_BITLEN 7 #define MAX_BIT_LENGTH 15 // Largest bitlen used by any tree type #define DEFLATE_CODE_BUFFER_SIZE (NUM_DEFLATE_CODE_SYMBOLS * 2) #define DISTANCE_BUFFER_SIZE (NUM_DISTANCE_SYMBOLS * 2) #define CODE_LENGTH_BUFFER_SIZE (NUM_DISTANCE_SYMBOLS * 2) #define SET_ERROR(png, code) \ do { \ (png)->error = (code); \ (png)->error_line = __LINE__; \ } while (0) #define png_chunk_length(chunk) MAKE_DWORD_PTR(chunk) #define png_chunk_type(chunk) MAKE_DWORD_PTR((chunk) + 4) #define png_chunk_critical(chunk) (((chunk)[4] & 32) == 0) struct huffman_tree { u32 *tree2d; u32 maxbitlen; // Maximum number of bits a single code can get u32 numcodes; // Number of symbols in the alphabet = number of codes }; // The base lengths represented by codes 257-285 static const u32 LENGTH_BASE[29] = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 }; // The extra bits used by codes 257-285 (added to base length) static const u32 LENGTH_EXTRA[29] = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 }; // The base backwards distances (the bits of distance codes appear after length codes and use their own huffman tree) static const u32 DISTANCE_BASE[30] = { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 }; // The extra bits of backwards distances (added to base) static const u32 DISTANCE_EXTRA[30] = { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 }; // The order in which "code length alphabet code lengths" are stored, out of this the huffman tree of the dynamic huffman tree lengths is generated static const u32 CLCL[NUM_CODE_LENGTH_CODES] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; static const u32 FIXED_DEFLATE_CODE_TREE[NUM_DEFLATE_CODE_SYMBOLS * 2] = { 289, 370, 290, 307, 546, 291, 561, 292, 293, 300, 294, 297, 295, 296, 0, 1, 2, 3, 298, 299, 4, 5, 6, 7, 301, 304, 302, 303, 8, 9, 10, 11, 305, 306, 12, 13, 14, 15, 308, 339, 309, 324, 310, 317, 311, 314, 312, 313, 16, 17, 18, 19, 315, 316, 20, 21, 22, 23, 318, 321, 319, 320, 24, 25, 26, 27, 322, 323, 28, 29, 30, 31, 325, 332, 326, 329, 327, 328, 32, 33, 34, 35, 330, 331, 36, 37, 38, 39, 333, 336, 334, 335, 40, 41, 42, 43, 337, 338, 44, 45, 46, 47, 340, 355, 341, 348, 342, 345, 343, 344, 48, 49, 50, 51, 346, 347, 52, 53, 54, 55, 349, 352, 350, 351, 56, 57, 58, 59, 353, 354, 60, 61, 62, 63, 356, 363, 357, 360, 358, 359, 64, 65, 66, 67, 361, 362, 68, 69, 70, 71, 364, 367, 365, 366, 72, 73, 74, 75, 368, 369, 76, 77, 78, 79, 371, 434, 372, 403, 373, 388, 374, 381, 375, 378, 376, 377, 80, 81, 82, 83, 379, 380, 84, 85, 86, 87, 382, 385, 383, 384, 88, 89, 90, 91, 386, 387, 92, 93, 94, 95, 389, 396, 390, 393, 391, 392, 96, 97, 98, 99, 394, 395, 100, 101, 102, 103, 397, 400, 398, 399, 104, 105, 106, 107, 401, 402, 108, 109, 110, 111, 404, 419, 405, 412, 406, 409, 407, 408, 112, 113, 114, 115, 410, 411, 116, 117, 118, 119, 413, 416, 414, 415, 120, 121, 122, 123, 417, 418, 124, 125, 126, 127, 420, 427, 421, 424, 422, 423, 128, 129, 130, 131, 425, 426, 132, 133, 134, 135, 428, 431, 429, 430, 136, 137, 138, 139, 432, 433, 140, 141, 142, 143, 435, 483, 436, 452, 568, 437, 438, 445, 439, 442, 440, 441, 144, 145, 146, 147, 443, 444, 148, 149, 150, 151, 446, 449, 447, 448, 152, 153, 154, 155, 450, 451, 156, 157, 158, 159, 453, 468, 454, 461, 455, 458, 456, 457, 160, 161, 162, 163, 459, 460, 164, 165, 166, 167, 462, 465, 463, 464, 168, 169, 170, 171, 466, 467, 172, 173, 174, 175, 469, 476, 470, 473, 471, 472, 176, 177, 178, 179, 474, 475, 180, 181, 182, 183, 477, 480, 478, 479, 184, 185, 186, 187, 481, 482, 188, 189, 190, 191, 484, 515, 485, 500, 486, 493, 487, 490, 488, 489, 192, 193, 194, 195, 491, 492, 196, 197, 198, 199, 494, 497, 495, 496, 200, 201, 202, 203, 498, 499, 204, 205, 206, 207, 501, 508, 502, 505, 503, 504, 208, 209, 210, 211, 506, 507, 212, 213, 214, 215, 509, 512, 510, 511, 216, 217, 218, 219, 513, 514, 220, 221, 222, 223, 516, 531, 517, 524, 518, 521, 519, 520, 224, 225, 226, 227, 522, 523, 228, 229, 230, 231, 525, 528, 526, 527, 232, 233, 234, 235, 529, 530, 236, 237, 238, 239, 532, 539, 533, 536, 534, 535, 240, 241, 242, 243, 537, 538, 244, 245, 246, 247, 540, 543, 541, 542, 248, 249, 250, 251, 544, 545, 252, 253, 254, 255, 547, 554, 548, 551, 549, 550, 256, 257, 258, 259, 552, 553, 260, 261, 262, 263, 555, 558, 556, 557, 264, 265, 266, 267, 559, 560, 268, 269, 270, 271, 562, 565, 563, 564, 272, 273, 274, 275, 566, 567, 276, 277, 278, 279, 569, 572, 570, 571, 280, 281, 282, 283, 573, 574, 284, 285, 286, 287, 0, 0 }; static const u32 FIXED_DISTANCE_TREE[NUM_DISTANCE_SYMBOLS * 2] = { 33, 48, 34, 41, 35, 38, 36, 37, 0, 1, 2, 3, 39, 40, 4, 5, 6, 7, 42, 45, 43, 44, 8, 9, 10, 11, 46, 47, 12, 13, 14, 15, 49, 56, 50, 53, 51, 52, 16, 17, 18, 19, 54, 55, 20, 21, 22, 23, 57, 60, 58, 59, 24, 25, 26, 27, 61, 62, 28, 29, 30, 31, 0, 0 }; static u8 read_bit(u32 *bitpointer, const u8 *bitstream) { u8 result = (u8)((bitstream[(*bitpointer) >> 3] >> ((*bitpointer) & 0x7)) & 1); (*bitpointer)++; return result; } static u32 read_bits(u32 *bitpointer, const u8 *bitstream, u32 nbits) { u32 result = 0, i; for (i = 0; i < nbits; i++) result |= ((u32)read_bit(bitpointer, bitstream)) << i; return result; } // The buffer must be numcodes*2 in size! static void huffman_tree_init(struct huffman_tree *tree, u32 *buffer, u32 numcodes, u32 maxbitlen) { tree->tree2d = buffer; tree->numcodes = numcodes; tree->maxbitlen = maxbitlen; } // Given the code lengths (as stored in the PNG file), generate the tree as defined by deflate. maxbitlen is the maximum bits that a code in the tree can have static void huffman_tree_create_lengths(struct png *png, struct huffman_tree *tree, const u32 *bitlen) { u32 tree1d[MAX_SYMBOLS]; u32 blcount[MAX_BIT_LENGTH]; u32 nextcode[MAX_BIT_LENGTH + 1]; u32 bits, n, i; u32 nodefilled = 0; // Up to which node it is filled u32 treepos = 0; // Position in the tree (1 of the numcodes columns) // Initialize local vectors memset(blcount, 0, sizeof(blcount)); memset(nextcode, 0, sizeof(nextcode)); // Step 1: Count number of instances of each code length for (bits = 0; bits < tree->numcodes; bits++) { blcount[bitlen[bits]]++; } // Step 2: Generate the nextcode values for (bits = 1; bits <= tree->maxbitlen; bits++) { nextcode[bits] = (nextcode[bits - 1] + blcount[bits - 1]) << 1; } // Step 3: Generate all the codes for (n = 0; n < tree->numcodes; n++) { if (bitlen[n] != 0) { tree1d[n] = nextcode[bitlen[n]]++; } } /* Convert tree1d[] to tree2d[][]. In the 2D array, a value of 32767 means uninited, a value >= numcodes is an address to another bit, a value < numcodes is a code. The 2 rows are the 2 possible bit values (0 or 1), there are as many columns as codes - 1. A good huffmann tree has N * 2 - 1 nodes, of which N - 1 are internal nodes. Here, the internal nodes are stored (what their 0 and 1 option point to). There is only memory for such good tree currently, if there are more nodes (due to too long length codes), error 55 will happen */ for (n = 0; n < tree->numcodes * 2; n++) { tree->tree2d[n] = 32767; // 32767 here means the tree2d isn't filled there yet } for (n = 0; n < tree->numcodes; n++) { // The codes for (i = 0; i < bitlen[n]; i++) { // The bits for this code u8 bit = (u8)((tree1d[n] >> (bitlen[n] - i - 1)) & 1); // Check if oversubscribed if (treepos > tree->numcodes - 2) { SET_ERROR(png, PNG_EMALFORMED); return; } if (tree->tree2d[2 * treepos + bit] == 32767) { // Not yet filled in if (i + 1 == bitlen[n]) { // Last bit // Put the current code in it tree->tree2d[2 * treepos + bit] = n; treepos = 0; } else { // Put address of the next step in here, first that address has to be found of course (it's just nodefilled + 1)... nodefilled++; tree->tree2d[2 * treepos + bit] = nodefilled + tree->numcodes; // Addresses encoded with numcodes added to it treepos = nodefilled; } } else { treepos = tree->tree2d[2 * treepos + bit] - tree->numcodes; } } } for (n = 0; n < tree->numcodes * 2; n++) { if (tree->tree2d[n] == 32767) { tree->tree2d[n] = 0; // Remove possible remaining 32767's } } } static u32 huffman_decode_symbol(struct png *png, const u8 *in, u32 *bp, const struct huffman_tree *codetree, u32 inlength) { u32 treepos = 0, ct; u8 bit; for (;;) { // Error: end of input memory reached without endcode if (((*bp) & 0x07) == 0 && ((*bp) >> 3) > inlength) { SET_ERROR(png, PNG_EMALFORMED); return 0; } bit = read_bit(bp, in); ct = codetree->tree2d[(treepos << 1) | bit]; if (ct < codetree->numcodes) { return ct; } treepos = ct - codetree->numcodes; if (treepos >= codetree->numcodes) { SET_ERROR(png, PNG_EMALFORMED); return 0; } } } // Get the tree of a deflated block with dynamic tree, the tree itself is also Huffman compressed with a known tree static void get_tree_inflate_dynamic(struct png *png, struct huffman_tree *codetree, struct huffman_tree *codetreeD, struct huffman_tree *codelengthcodetree, const u8 *in, u32 *bp, u32 inlength) { u32 codelengthcode[NUM_CODE_LENGTH_CODES]; u32 bitlen[NUM_DEFLATE_CODE_SYMBOLS]; u32 bitlenD[NUM_DISTANCE_SYMBOLS]; u32 n, hlit, hdist, hclen, i; // Make sure that length values that aren't filled in will be 0, or a wrong tree will be generated if ((*bp) >> 3 >= inlength - 2) { SET_ERROR(png, PNG_EMALFORMED); return; } // Clear bitlen arrays memset(bitlen, 0, sizeof(bitlen)); memset(bitlenD, 0, sizeof(bitlenD)); // Number of literal/length codes + 257. Unlike the spec, the value 257 is added to it here already hlit = read_bits(bp, in, 5) + 257; // Number of distance codes. Unlike the spec, the value 1 is added to it here already hdist = read_bits(bp, in, 5) + 1; // Number of code length codes. Unlike the spec, the value 4 is added to it here already hclen = read_bits(bp, in, 4) + 4; for (i = 0; i < NUM_CODE_LENGTH_CODES; i++) { if (i < hclen) { codelengthcode[CLCL[i]] = read_bits(bp, in, 3); } else { codelengthcode[CLCL[i]] = 0; } } huffman_tree_create_lengths(png, codelengthcodetree, codelengthcode); if (png->error != PNG_EOK) return; // Use this tree to read the lengths for the tree that this function will return i = 0; while (i < hlit + hdist) { u32 code = huffman_decode_symbol(png, in, bp, codelengthcodetree, inlength); if (png->error != PNG_EOK) { break; } if (code <= 15) { // Length code if (i < hlit) { bitlen[i] = code; } else { bitlenD[i - hlit] = code; } i++; } else if (code == 16) { // Repeat previous u32 replength = 3; // Read in the 2 bits that indicate repeat length (3-6) u32 value; // Set value to the previous code if ((*bp) >> 3 >= inlength) { SET_ERROR(png, PNG_EMALFORMED); break; } // Error, bit pointer jumps past memory replength += read_bits(bp, in, 2); if ((i - 1) < hlit) { value = bitlen[i - 1]; } else { value = bitlenD[i - hlit - 1]; } // Repeat this value in the next lengths for (n = 0; n < replength; n++) { // i is larger than the amount of codes if (i >= hlit + hdist) { SET_ERROR(png, PNG_EMALFORMED); break; } if (i < hlit) { bitlen[i] = value; } else { bitlenD[i - hlit] = value; } i++; } } else if (code == 17) { // Repeat "0" 3-10 times u32 replength = 3; // Read in the bits that indicate repeat length if ((*bp) >> 3 >= inlength) { SET_ERROR(png, PNG_EMALFORMED); break; } // Error, bit pointer jumps past memory replength += read_bits(bp, in, 3); // Repeat this value in the next lengths for (n = 0; n < replength; n++) { // Error: i is larger than the amount of codes if (i >= hlit + hdist) { SET_ERROR(png, PNG_EMALFORMED); break; } if (i < hlit) { bitlen[i] = 0; } else { bitlenD[i - hlit] = 0; } i++; } } else if (code == 18) { // Repeat "0" 11-138 times u32 replength = 11; // Read in the bits that indicate repeat length // Error, bit pointer jumps past memory if ((*bp) >> 3 >= inlength) { SET_ERROR(png, PNG_EMALFORMED); break; } replength += read_bits(bp, in, 7); // Repeat this value in the next lengths for (n = 0; n < replength; n++) { // i is larger than the amount of codes if (i >= hlit + hdist) { SET_ERROR(png, PNG_EMALFORMED); break; } if (i < hlit) bitlen[i] = 0; else bitlenD[i - hlit] = 0; i++; } } else { // Somehow an unexisting code appeared SET_ERROR(png, PNG_EMALFORMED); break; } } if (png->error == PNG_EOK && bitlen[256] == 0) { SET_ERROR(png, PNG_EMALFORMED); } // Generate code trees if (png->error == PNG_EOK) { huffman_tree_create_lengths(png, codetree, bitlen); } if (png->error == PNG_EOK) { huffman_tree_create_lengths(png, codetreeD, bitlenD); } } // Inflate a block with dynamic of fixed Huffman tree static void inflate_huffman(struct png *png, u8 *out, u32 outsize, const u8 *in, u32 *bp, u32 *pos, u32 inlength, u32 btype) { u32 codetree_buffer[DEFLATE_CODE_BUFFER_SIZE]; u32 codetreeD_buffer[DISTANCE_BUFFER_SIZE]; u32 done = 0; struct huffman_tree codetree; struct huffman_tree codetreeD; if (btype == 1) { // Fixed trees huffman_tree_init(&codetree, (u32 *)FIXED_DEFLATE_CODE_TREE, NUM_DEFLATE_CODE_SYMBOLS, DEFLATE_CODE_BITLEN); huffman_tree_init(&codetreeD, (u32 *)FIXED_DISTANCE_TREE, NUM_DISTANCE_SYMBOLS, DISTANCE_BITLEN); } else if (btype == 2) { // Dynamic trees u32 codelengthcodetree_buffer[CODE_LENGTH_BUFFER_SIZE]; struct huffman_tree codelengthcodetree; huffman_tree_init(&codetree, codetree_buffer, NUM_DEFLATE_CODE_SYMBOLS, DEFLATE_CODE_BITLEN); huffman_tree_init(&codetreeD, codetreeD_buffer, NUM_DISTANCE_SYMBOLS, DISTANCE_BITLEN); huffman_tree_init(&codelengthcodetree, codelengthcodetree_buffer, NUM_CODE_LENGTH_CODES, CODE_LENGTH_BITLEN); get_tree_inflate_dynamic(png, &codetree, &codetreeD, &codelengthcodetree, in, bp, inlength); } while (done == 0) { u32 code = huffman_decode_symbol(png, in, bp, &codetree, inlength); if (png->error != PNG_EOK) { return; } if (code == 256) { // End code done = 1; } else if (code <= 255) { // Literal symbol if ((*pos) >= outsize) { SET_ERROR(png, PNG_EMALFORMED); return; } // Store output out[(*pos)++] = (u8)(code); } else if (code >= FIRST_LENGTH_CODE_INDEX && code <= LAST_LENGTH_CODE_INDEX) { // Part 1: Get length base u32 length = LENGTH_BASE[code - FIRST_LENGTH_CODE_INDEX]; u32 codeD, distance, numextrabitsD; u32 start, forward, backward, numextrabits; // Part 2: Get extra bits and add the value of that to length numextrabits = LENGTH_EXTRA[code - FIRST_LENGTH_CODE_INDEX]; // Error, bit pointer will jump past memory if (((*bp) >> 3) >= inlength) { SET_ERROR(png, PNG_EMALFORMED); return; } length += read_bits(bp, in, numextrabits); // Part 3: Get distance code codeD = huffman_decode_symbol(png, in, bp, &codetreeD, inlength); if (png->error != PNG_EOK) { return; } // Invalid distance code (30-31 are never used) if (codeD > 29) { SET_ERROR(png, PNG_EMALFORMED); return; } distance = DISTANCE_BASE[codeD]; // Part 4: Get extra bits from distance numextrabitsD = DISTANCE_EXTRA[codeD]; // Error, bit pointer will jump past memory if (((*bp) >> 3) >= inlength) { SET_ERROR(png, PNG_EMALFORMED); return; } distance += read_bits(bp, in, numextrabitsD); // Part 5: Fill in all the out[n] values based on the length and dist start = (*pos); backward = start - distance; if ((*pos) + length >= outsize) { SET_ERROR(png, PNG_EMALFORMED); return; } for (forward = 0; forward < length; forward++) { out[(*pos)++] = out[backward]; backward++; if (backward >= start) { backward = start - distance; } } } } } static void inflate_uncompressed(struct png *png, u8 *out, u32 outsize, const u8 *in, u32 *bp, u32 *pos, u32 inlength) { u32 p; u32 len, nlen, n; // Go to first boundary of byte while (((*bp) & 0x7) != 0) { (*bp)++; } p = (*bp) / 8; //byte position // Read len (2 bytes) and nlen (2 bytes) if (p >= inlength - 4) { SET_ERROR(png, PNG_EMALFORMED); return; } len = in[p] + 256 * in[p + 1]; p += 2; nlen = in[p] + 256 * in[p + 1]; p += 2; // Check if 16-bit nlen is really the one's complement of len if (len + nlen != 65535) { SET_ERROR(png, PNG_EMALFORMED); return; } if ((*pos) + len >= outsize) { SET_ERROR(png, PNG_EMALFORMED); return; } // Read the literal data: len bytes are now stored in the out buffer if (p + len > inlength) { SET_ERROR(png, PNG_EMALFORMED); return; } for (n = 0; n < len; n++) { out[(*pos)++] = in[p++]; } (*bp) = p * 8; } // Inflate the deflated data (cfr. deflate spec) static enum png_error uz_inflate_data(struct png *png, u8 *out, u32 outsize, const u8 *in, u32 insize, u32 inpos) { u32 bp = 0; // Bit pointer in the in buffer u32 pos = 0; // Byte position in the out buffer u32 done = 0; while (done == 0) { u32 btype; // Ensure next bit doesn't point past the end of the buffer if ((bp >> 3) >= insize) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Read block control bits done = read_bit(&bp, &in[inpos]); btype = read_bit(&bp, &in[inpos]) | (read_bit(&bp, &in[inpos]) << 1); // Process control type appropriately if (btype == 3) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } else if (btype == 0) { // No compression inflate_uncompressed(png, out, outsize, &in[inpos], &bp, &pos, insize); } else { // Compression, btype 01 or 10 inflate_huffman(png, out, outsize, &in[inpos], &bp, &pos, insize, btype); } // Stop if an error has occured if (png->error != PNG_EOK) { return png->error; } } return png->error; } static enum png_error uz_inflate(struct png *png, u8 *out, u32 outsize, const u8 *in, u32 insize) { // Two bytes for the zlib data header if (insize < 2) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // 256 * in[0] + in[1] must be a multiple of 31, the FCHECK value is supposed to be made that way if ((in[0] * 256 + in[1]) % 31 != 0) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Error: Only compression method 8: Inflate with sliding window of 32k is supported by the PNG spec if ((in[0] & 15) != 8 || ((in[0] >> 4) & 15) > 7) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // The specification of PNG says about the zlib stream: "The additional flags shall not specify a preset dictionary." if (((in[1] >> 5) & 1) != 0) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Create output buffer uz_inflate_data(png, out, outsize, in, insize, 2); return png->error; } // Paeth predictor, used by PNG filter type 4 static int paeth_predictor(int a, int b, int c) { int p = a + b - c; int pa = p > a ? p - a : a - p; int pb = p > b ? p - b : b - p; int pc = p > c ? p - c : c - p; if (pa <= pb && pa <= pc) return a; else if (pb <= pc) return b; else return c; } static void unfilter_scanline(struct png *png, u8 *recon, const u8 *scanline, const u8 *precon, u32 bytewidth, u8 filterType, u32 length) { /* For PNG filter method 0 Unfilter a PNG image scanline by scanline. when the pixels are smaller than 1 byte, the filter works byte per byte (bytewidth = 1) precon is the previous unfiltered scanline, recon the result, scanline the current one The incoming scanlines do NOT include the filtertype byte, that one is given in the parameter filterType instead recon and scanline MAY be the same memory address! precon must be disjoint. */ u32 i; switch (filterType) { case 0: for (i = 0; i < length; i++) recon[i] = scanline[i]; break; case 1: for (i = 0; i < bytewidth; i++) recon[i] = scanline[i]; for (i = bytewidth; i < length; i++) recon[i] = scanline[i] + recon[i - bytewidth]; break; case 2: if (precon) for (i = 0; i < length; i++) recon[i] = scanline[i] + precon[i]; else for (i = 0; i < length; i++) recon[i] = scanline[i]; break; case 3: if (precon) { for (i = 0; i < bytewidth; i++) recon[i] = scanline[i] + precon[i] / 2; for (i = bytewidth; i < length; i++) recon[i] = scanline[i] + ((recon[i - bytewidth] + precon[i]) / 2); } else { for (i = 0; i < bytewidth; i++) recon[i] = scanline[i]; for (i = bytewidth; i < length; i++) recon[i] = scanline[i] + recon[i - bytewidth] / 2; } break; case 4: if (precon) { for (i = 0; i < bytewidth; i++) recon[i] = (u8)(scanline[i] + paeth_predictor(0, precon[i], 0)); for (i = bytewidth; i < length; i++) recon[i] = (u8)(scanline[i] + paeth_predictor(recon[i - bytewidth], precon[i], precon[i - bytewidth])); } else { for (i = 0; i < bytewidth; i++) recon[i] = scanline[i]; for (i = bytewidth; i < length; i++) recon[i] = (u8)(scanline[i] + paeth_predictor(recon[i - bytewidth], 0, 0)); } break; default: SET_ERROR(png, PNG_EMALFORMED); break; } } static void unfilter(struct png *png, u8 *out, const u8 *in, u32 w, u32 h, u32 bpp) { /* For PNG filter method 0 This function unfilters a single image (e.g. without interlacing this is called once, with Adam7 it's called 7 times) out must have enough bytes allocated already, in must have the scanlines + 1 filtertype byte per scanline w and h are image dimensions or dimensions of reduced image, bpp is bpp per pixel in and out are allowed to be the same memory address! */ u32 y; u8 *prevline = 0; // bytewidth is used for filtering, is 1 when bpp < 8, number of bytes per pixel otherwise u32 bytewidth = (bpp + 7) / 8; u32 linebytes = (w * bpp + 7) / 8; for (y = 0; y < h; y++) { u32 outindex = linebytes * y; u32 inindex = (1 + linebytes) * y; u8 filterType = in[inindex]; unfilter_scanline(png, &out[outindex], &in[inindex + 1], prevline, bytewidth, filterType, linebytes); if (png->error != PNG_EOK) { return; } prevline = &out[outindex]; } } static void remove_padding_bits(u8 *out, const u8 *in, u32 olinebits, u32 ilinebits, u32 h) { /* After filtering there are still padding bpp if scanlines have non multiple of 8 bit amounts. They need to be removed (except at last scanline of (Adam7-reduced) image) before working with pure image buffers for the Adam7 code, the color convert code and the output to the user. in and out are allowed to be the same buffer, in may also be higher but still overlapping; in must have >= ilinebits*h bpp, out must have >= olinebits*h bpp, olinebits must be <= ilinebits Also used to move bpp after earlier such operations happened, e.g. in a sequence of reduced images from Adam7 Only useful if (ilinebits - olinebits) is a value in the range 1..7 */ u32 y; u32 diff = ilinebits - olinebits; u32 obp = 0, ibp = 0; // Bit pointers for (y = 0; y < h; y++) { u32 x; for (x = 0; x < olinebits; x++) { u8 bit = (u8)((in[(ibp) >> 3] >> (7 - ((ibp)&0x7))) & 1); ibp++; if (bit == 0) out[(obp) >> 3] &= (u8)(~(1 << (7 - ((obp)&0x7)))); else out[(obp) >> 3] |= (1 << (7 - ((obp)&0x7))); ++obp; } ibp += diff; } } // out buffer must be big enough to contain full image, and it must contain the full decompressed data from the IDAT chunks static void post_process_scanlines(struct png *png, u8 *out, u8 *in, const struct png *info_png) { u32 bpp = png_get_bpp(info_png); u32 w = info_png->width; u32 h = info_png->height; if (bpp == 0) { SET_ERROR(png, PNG_EMALFORMED); return; } if (bpp < 8 && w * bpp != ((w * bpp + 7) / 8) * 8) { unfilter(png, in, in, w, h, bpp); if (png->error != PNG_EOK) { return; } remove_padding_bits(out, in, w * bpp, ((w * bpp + 7) / 8) * 8, h); } else { unfilter(png, out, in, w, h, bpp); } } static enum png_format determine_format(struct png *png) { switch (png->color_type) { case PNG_LUM: switch (png->color_depth) { case 1: return PNG_LUMINANCE1; case 2: return PNG_LUMINANCE2; case 4: return PNG_LUMINANCE4; case 8: return PNG_LUMINANCE8; default: return PNG_BADFORMAT; } case PNG_RGB: switch (png->color_depth) { case 8: return PNG_RGB8; case 16: return PNG_RGB16; default: return PNG_BADFORMAT; } case PNG_LUMA: switch (png->color_depth) { case 1: return PNG_LUMINANCE_ALPHA1; case 2: return PNG_LUMINANCE_ALPHA2; case 4: return PNG_LUMINANCE_ALPHA4; case 8: return PNG_LUMINANCE_ALPHA8; default: return PNG_BADFORMAT; } case PNG_RGBA: switch (png->color_depth) { case 8: return PNG_RGBA8; case 16: return PNG_RGBA16; default: return PNG_BADFORMAT; } default: return PNG_BADFORMAT; } } static void png_free_source(struct png *png) { if (png->source.owning != 0) { free((void *)png->source.buffer); } png->source.buffer = NULL; png->source.size = 0; png->source.owning = 0; } // Read the information from the header and store it in the png_info enum png_error png_header(struct png *png) { if (png->error != PNG_EOK) { return png->error; } if (png->state != PNG_NEW) { return png->error; } // Minimum length of a valid PNG file is 29 bytes // FIXME: Verify this against the specification, or against the actual code below if (png->source.size < 29) { SET_ERROR(png, PNG_ENOTPNG); return png->error; } // Check that PNG header matches expected value if (png->source.buffer[0] != 137 || png->source.buffer[1] != 80 || png->source.buffer[2] != 78 || png->source.buffer[3] != 71 || png->source.buffer[4] != 13 || png->source.buffer[5] != 10 || png->source.buffer[6] != 26 || png->source.buffer[7] != 10) { SET_ERROR(png, PNG_ENOTPNG); return png->error; } // Check that the first chunk is the IHDR chunk if (MAKE_DWORD_PTR(png->source.buffer + 12) != CHUNK_IHDR) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Read the values given in the header png->width = MAKE_DWORD_PTR(png->source.buffer + 16); png->height = MAKE_DWORD_PTR(png->source.buffer + 20); png->color_depth = png->source.buffer[24]; png->color_type = (enum png_color)png->source.buffer[25]; // Determine the color format png->format = determine_format(png); if (png->format == PNG_BADFORMAT) { SET_ERROR(png, PNG_EUNFORMAT); return png->error; } // Check that the compression method (byte 27) is 0 (only allowed value in spec) if (png->source.buffer[26] != 0) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Check that the compression method (byte 27) is 0 (only allowed value in spec) if (png->source.buffer[27] != 0) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Check that the compression method (byte 27) is 0 (spec allows 1, but png does not support it) if (png->source.buffer[28] != 0) { SET_ERROR(png, PNG_EUNINTERLACED); return png->error; } png->state = PNG_HEADER; return png->error; } // Read a PNG, the result will be in the same color type as the PNG (hence "generic") enum png_error png_decode(struct png *png) { const u8 *chunk; u8 *compressed; u8 *inflated; u32 compressed_size = 0, compressed_index = 0; u32 inflated_size; enum png_error error; if (png->error != PNG_EOK) { return png->error; } // Parse the main header, if necessary png_header(png); if (png->error != PNG_EOK) { return png->error; } // Not a PNG header -> crash if (png->state != PNG_HEADER) { return png->error; } // Release old result, if any if (png->buffer != 0) { free(png->buffer); png->buffer = 0; png->size = 0; } // First byte of the first chunk after the header chunk = png->source.buffer + 33; // Scan through the chunks, finding the size of all IDAT chunks, and also verify general compliance while (chunk < png->source.buffer + png->source.size) { u32 length; // Make sure chunk header is not larger than the total compressed if ((u32)(chunk - png->source.buffer + 12) > png->source.size) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Get length; sanity check it length = png_chunk_length(chunk); if (length > S32_MAX) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Make sure chunk header+paylaod is not larger than the total compressed if ((u32)(chunk - png->source.buffer + length + 12) > png->source.size) { SET_ERROR(png, PNG_EMALFORMED); return png->error; } // Parse chunks if (png_chunk_type(chunk) == CHUNK_IDAT) { compressed_size += length; } else if (png_chunk_type(chunk) == CHUNK_IEND) { break; } else if (png_chunk_critical(chunk)) { SET_ERROR(png, PNG_EUNSUPPORTED); return png->error; } chunk += png_chunk_length(chunk) + 12; } // Allocate enough space for the (compressed and filtered) image data compressed = (u8 *)malloc(compressed_size); if (compressed == NULL) { SET_ERROR(png, PNG_ENOMEM); return png->error; } // Scan through the chunks again, this time copying the values into the compressed buffer.There's no reason to validate anything a second time chunk = png->source.buffer + 33; while (chunk < png->source.buffer + png->source.size) { u32 length; const u8 *data; // The data in the chunk length = png_chunk_length(chunk); data = chunk + 8; // Parse chunks if (png_chunk_type(chunk) == CHUNK_IDAT) { memcpy(compressed + compressed_index, data, length); compressed_index += length; } else if (png_chunk_type(chunk) == CHUNK_IEND) { break; } chunk += png_chunk_length(chunk) + 12; } // Allocate space to store inflated (but still filtered) data inflated_size = ((png->width * (png->height * png_get_bpp(png) + 7)) / 8) + png->height; inflated = (u8 *)malloc(inflated_size); if (inflated == NULL) { free(compressed); SET_ERROR(png, PNG_ENOMEM); return png->error; } // Decompress image data error = uz_inflate(png, inflated, inflated_size, compressed, compressed_size); if (error != PNG_EOK) { free(compressed); free(inflated); return png->error; } // Free the compressed compressed data free(compressed); // Allocate final image buffer png->size = (png->height * png->width * png_get_bpp(png) + 7) / 8; png->buffer = (u8 *)malloc(png->size); if (png->buffer == NULL) { free(inflated); png->size = 0; SET_ERROR(png, PNG_ENOMEM); return png->error; } // Unfilter scanlines post_process_scanlines(png, png->buffer, inflated, png); free(inflated); if (png->error != PNG_EOK) { free(png->buffer); png->buffer = NULL; png->size = 0; } else { png->state = PNG_DECODED; } // Done! png_free_source(png); return png->error; } static struct png *png_new(void) { struct png *png; png = (struct png *)malloc(sizeof(struct png)); if (png == NULL) { return NULL; } png->buffer = NULL; png->size = 0; png->width = png->height = 0; png->color_type = PNG_RGBA; png->color_depth = 8; png->format = PNG_RGBA8; png->state = PNG_NEW; png->error = PNG_EOK; png->error_line = 0; png->source.buffer = NULL; png->source.size = 0; png->source.owning = 0; return png; } void png_free(struct png *png) { // Deallocate image buffer if (png->buffer) free(png->buffer); // Deallocate source buffer, if necessary png_free_source(png); // Deallocate struct itself free(png); } u32 png_get_bpp(const struct png *png) { int depth = 0; switch (png->color_type) { case PNG_LUM: depth = 1; break; case PNG_RGB: depth = 3; break; case PNG_LUMA: depth = 2; break; case PNG_RGBA: depth = 4; break; default: depth = 0; break; } return png->color_depth * depth; } struct bmp *png_load(const char *path) { struct png *png = png_new(); if (!png) return NULL; void *buf = sread(path); if (!buf) { SET_ERROR(png, PNG_ENOTFOUND); png_free(png); return NULL; } struct stat s = { 0 }; stat(path, &s); png->source.buffer = buf; png->source.size = s.size; png->source.owning = 1; png_decode(png); assert(png->error == PNG_EOK); struct bmp *bmp = malloc(sizeof(*bmp)); bmp->width = png->width; bmp->height = png->height; bmp->data = png->buffer; bmp->bpp = png_get_bpp(png); bmp->pitch = png->width * (bmp->bpp >> 3); png_free(png); return bmp; }