From bb6f08f3c79efc7bb7877aca97cebd3dab8b7838 Mon Sep 17 00:00:00 2001 From: Clement Sibille Date: Tue, 5 Mar 2024 16:02:17 +0900 Subject: Implement PNG decompression This patch adds PNG decompression for images without interlacing and without alpha channel. Only basic image data is supported. Background, transparency, gamma, paletted images are not supported. --- lisiblepng-bin/src/main.c | 5 +- lisiblepng/meson.build | 7 +- lisiblepng/src/assert.h | 15 -- lisiblepng/src/bitstream.c | 53 ----- lisiblepng/src/bitstream.h | 20 -- lisiblepng/src/deflate.c | 394 -------------------------------- lisiblepng/src/deflate.h | 15 -- lisiblepng/src/lisiblepng.c | 290 ++++++++++++++++++++--- lisiblepng/src/lisiblepng/assert.h | 15 ++ lisiblepng/src/lisiblepng/bitstream.c | 53 +++++ lisiblepng/src/lisiblepng/bitstream.h | 20 ++ lisiblepng/src/lisiblepng/deflate.c | 419 ++++++++++++++++++++++++++++++++++ lisiblepng/src/lisiblepng/deflate.h | 19 ++ lisiblepng/src/lisiblepng/log.h | 23 ++ lisiblepng/src/log.h | 9 - 15 files changed, 820 insertions(+), 537 deletions(-) delete mode 100644 lisiblepng/src/assert.h delete mode 100644 lisiblepng/src/bitstream.c delete mode 100644 lisiblepng/src/bitstream.h delete mode 100644 lisiblepng/src/deflate.c delete mode 100644 lisiblepng/src/deflate.h create mode 100644 lisiblepng/src/lisiblepng/assert.h create mode 100644 lisiblepng/src/lisiblepng/bitstream.c create mode 100644 lisiblepng/src/lisiblepng/bitstream.h create mode 100644 lisiblepng/src/lisiblepng/deflate.c create mode 100644 lisiblepng/src/lisiblepng/deflate.h create mode 100644 lisiblepng/src/lisiblepng/log.h delete mode 100644 lisiblepng/src/log.h diff --git a/lisiblepng-bin/src/main.c b/lisiblepng-bin/src/main.c index 7979326..62dea31 100644 --- a/lisiblepng-bin/src/main.c +++ b/lisiblepng-bin/src/main.c @@ -1,8 +1,11 @@ #include #include -#include +#include #include +#define LOG0(msg) fprintf(stderr, msg) +#define LOGN(fmt, ...) fprintf(stderr, fmt, __VA_ARGS__) + int main(int argc, char **argv) { if (argc != 2) { LOG0("Usage: lisiblepng "); diff --git a/lisiblepng/meson.build b/lisiblepng/meson.build index 224011a..22510fe 100644 --- a/lisiblepng/meson.build +++ b/lisiblepng/meson.build @@ -1,3 +1,6 @@ +cc = meson.get_compiler('c') +m_dep = cc.find_library('m', required: true) + lisiblepng_incdir = include_directories('src/') -lisiblepng_lib = library('lisiblepng', 'src/lisiblepng.c', 'src/deflate.c', 'src/bitstream.c') -lisiblepng_dep = declare_dependency(include_directories: lisiblepng_incdir, link_with: [lisiblepng_lib]) +lisiblepng_lib = library('lisiblepng', 'src/lisiblepng.c', 'src/lisiblepng/deflate.c', 'src/lisiblepng/bitstream.c', dependencies: [m_dep]) +lisiblepng_dep = declare_dependency(include_directories: lisiblepng_incdir, link_with: [lisiblepng_lib], dependencies: [m_dep]) diff --git a/lisiblepng/src/assert.h b/lisiblepng/src/assert.h deleted file mode 100644 index 7d41b57..0000000 --- a/lisiblepng/src/assert.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef LISIBLE_PNG_ASSET_H -#define LISIBLE_PNG_ASSET_H - -#include "log.h" - -#define ASSERT(predicate) \ - do { \ - if (!(predicate)) { \ - LOGN("Assertion failed in %s:%d:\n\t%s", __FILE__, __LINE__, \ - #predicate); \ - exit(1); \ - } \ - } while (0) - -#endif // LISIBLE_PNG_ASSET_H diff --git a/lisiblepng/src/bitstream.c b/lisiblepng/src/bitstream.c deleted file mode 100644 index e7ddb79..0000000 --- a/lisiblepng/src/bitstream.c +++ /dev/null @@ -1,53 +0,0 @@ -#include "bitstream.h" -#include "assert.h" - -#define MAX(x, y) (((x) > (y)) ? (x) : (y)) -#define MIN(x, y) (((x) < (y)) ? (x) : (y)) - -void Bitstream_init(Bitstream *bitstream, const uint8_t *data, - size_t data_size) { - ASSERT(bitstream != NULL); - ASSERT(data != NULL); - bitstream->data = data; - bitstream->data_size = data_size; - bitstream->current_byte_index = 0; - bitstream->current_bit_offset = 0; -} - -void bitstream_advance(Bitstream *bitstream, size_t bit_count) { - ASSERT(bitstream != NULL); - uint8_t current_bit = bitstream->current_bit_offset; - bitstream->current_byte_index = - bitstream->current_byte_index + (current_bit + bit_count) / 8; - bitstream->current_bit_offset = (current_bit + bit_count) % 8; -} - -void Bitstream_skip(Bitstream *bitstream, size_t bit_count) { - ASSERT(bitstream != NULL); - bitstream_advance(bitstream, bit_count); -} - -uint16_t Bitstream_next_bits(Bitstream *bitstream, int bit_count) { - ASSERT(bitstream != NULL); - ASSERT(bit_count <= 16); - ASSERT((bitstream->current_bit_offset + (size_t)bit_count) / 8 <= - bitstream->data_size); - - int bit_to_read = bit_count; - uint16_t val = bitstream->data[bitstream->current_byte_index] >> - bitstream->current_bit_offset; - - size_t bit_read = MIN(bit_count, 8 - bitstream->current_bit_offset); - bitstream_advance(bitstream, bit_read); - bit_to_read -= bit_read; - while (bit_to_read > 0) { - val |= (bitstream->data[bitstream->current_byte_index] >> - bitstream->current_bit_offset) - << bit_read; - bit_read = MIN(bit_to_read, 8 - bitstream->current_bit_offset); - bitstream_advance(bitstream, bit_read); - bit_to_read -= bit_read; - } - - return (val & ((1 << bit_count) - 1)); -} diff --git a/lisiblepng/src/bitstream.h b/lisiblepng/src/bitstream.h deleted file mode 100644 index 72d8295..0000000 --- a/lisiblepng/src/bitstream.h +++ /dev/null @@ -1,20 +0,0 @@ -#ifndef CUTTERENG_BITSTREAM_H -#define CUTTERENG_BITSTREAM_H - -#include -#include - -typedef struct { - const uint8_t *data; - size_t data_size; - - size_t current_byte_index; - uint8_t current_bit_offset; -} Bitstream; - -void Bitstream_init(Bitstream *bitstream, const uint8_t *data, - size_t data_size); -void Bitstream_skip(Bitstream *bitstream, size_t bit_count); -uint16_t Bitstream_next_bits(Bitstream *bitstream, int bit_count); - -#endif // CUTTERENG_BITSTREAM_H diff --git a/lisiblepng/src/deflate.c b/lisiblepng/src/deflate.c deleted file mode 100644 index d894a35..0000000 --- a/lisiblepng/src/deflate.c +++ /dev/null @@ -1,394 +0,0 @@ -#include "deflate.h" -#include "assert.h" -#include "bitstream.h" -#include - -#define CM_LENGTH_BITS 4 -#define CINFO_LENGTH_BITS 4 -#define FCHECK_LENGTH_BITS 5 -#define FDICT_LENGTH_BITS 1 -#define FLEVEL_LENGTH_BITS 2 - -#define BFINAL_LENGTH_BITS 1 -#define BTYPE_LENGTH_BITS 2 - -#define CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT 19 -#define MAX_HUFFMAN_CODE_LENGTH 15 -#define MAX_LENGTH_CODES 286 -#define MAX_DISTANCE_CODES 32 -#define FIXED_LENGTH_LITERAL_CODE_COUNT 288 - -typedef enum { - DeflateBlockType_NoCompression, - DeflateBlockType_FixedHuffman, - DeflateBlockType_DynamicHuffman, - DeflateBlockType_Error -} DeflateBlockType; - -typedef struct { - uint16_t counts[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT]; - uint16_t symbols[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT]; -} CodeLengthTable; - -typedef struct { - uint16_t counts[MAX_LENGTH_CODES]; - uint16_t symbols[MAX_LENGTH_CODES]; -} LengthLiteralTable; - -typedef struct { - uint16_t counts[MAX_DISTANCE_CODES]; - uint16_t symbols[MAX_DISTANCE_CODES]; -} DistanceTable; - -#define DEFLATE_OUTPUT_BUFFER_INITIAL_CAPACITY (1024 * 256) - -typedef struct { - char *buffer; - size_t len; - size_t cap; -} OutputBuffer; - -void OutputBuffer_init(OutputBuffer *output_buffer) { - ASSERT(output_buffer != NULL); - output_buffer->buffer = calloc(DEFLATE_OUTPUT_BUFFER_INITIAL_CAPACITY, 1); - if (!output_buffer->buffer) { - LOG0("Couldn't allocate deflate output buffer (out of memory?)"); - abort(); - } - output_buffer->cap = DEFLATE_OUTPUT_BUFFER_INITIAL_CAPACITY; - output_buffer->len = 0; -} - -void OutputBuffer_expand(OutputBuffer *output_buffer) { - ASSERT(output_buffer != NULL); - size_t new_cap = output_buffer->cap * 2; - output_buffer->buffer = realloc(output_buffer->buffer, new_cap); - if (!output_buffer->buffer) { - LOG0("Couldn't reallocate deflate output buffer (out of memory?)"); - abort(); - } - - output_buffer->cap = new_cap; -} - -void OutputBuffer_push(OutputBuffer *output_buffer, char byte) { - ASSERT(output_buffer != NULL); - if (output_buffer->len == output_buffer->cap) { - OutputBuffer_expand(output_buffer); - } - - output_buffer->buffer[output_buffer->len++] = byte; -} - -size_t OutputBuffer_length(const OutputBuffer *output_buffer) { - ASSERT(output_buffer != NULL); - return output_buffer->len; -} - -int huffman_table_decode(const uint16_t *symbols, const uint16_t *counts, - Bitstream *bitstream) { - ASSERT(symbols != NULL); - ASSERT(counts != NULL); - ASSERT(bitstream != NULL); - int code = 0; - int index = 0; - int first = 0; - for (int i = 1; i <= MAX_HUFFMAN_CODE_LENGTH; i++) { - code |= Bitstream_next_bits(bitstream, 1); - int count = counts[i]; - if (code - count < first) { - return symbols[index + (code - first)]; - } - - index += count; - first += count; - first <<= 1; - code <<= 1; - } - - return -1; -} - -void build_huffman_table_from_codelengths(uint16_t *symbols, uint16_t *counts, - const uint16_t *codelengths, - uint16_t codelength_count) { - ASSERT(symbols != NULL); - ASSERT(counts != NULL); - ASSERT(codelengths != NULL); - - for (int i = 0; i < codelength_count; i++) { - counts[codelengths[i]]++; - } - counts[0] = 0; - - uint16_t next_code[MAX_HUFFMAN_CODE_LENGTH + 1] = {0}; - for (int i = 1; i < MAX_HUFFMAN_CODE_LENGTH; i++) { - next_code[i + 1] = next_code[i] + counts[i]; - } - - for (int i = 0; i < codelength_count; i++) { - if (codelengths[i] == 0) { - continue; - } - - symbols[next_code[codelengths[i]]++] = i; - } -} -void CodeLengthTable_build_from_codelengths( - CodeLengthTable *table, - uint16_t codelength_codelengths[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT]) { - ASSERT(table != NULL); - ASSERT(codelength_codelengths != NULL); - static const uint8_t CODELENGTH_MAPPING[] = { - 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; - uint16_t mapped_codelengths[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT] = {0}; - for (int i = 0; i < CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT; i++) { - mapped_codelengths[CODELENGTH_MAPPING[i]] = codelength_codelengths[i]; - } - - build_huffman_table_from_codelengths(table->symbols, table->counts, - mapped_codelengths, - CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT); -} - -void build_codelength_table(CodeLengthTable *codelength_table, - Bitstream *bitstream, const uint8_t hclen) { - ASSERT(codelength_table != NULL); - ASSERT(bitstream != NULL); - - uint16_t codelengths_codelengths[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT] = {0}; - for (int i = 0; i < hclen; i++) { - codelengths_codelengths[i] = Bitstream_next_bits(bitstream, 3); - } - - CodeLengthTable_build_from_codelengths(codelength_table, - codelengths_codelengths); -} - -bool deflate_decompress_(Bitstream *bitstream, - const LengthLiteralTable *length_literal_table, - const DistanceTable *distance_table, - OutputBuffer *output) { - ASSERT(bitstream != NULL); - ASSERT(output != NULL); - ASSERT(length_literal_table != NULL); - ASSERT(distance_table != NULL); - static const uint16_t length_size_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}; - static const uint16_t length_extra_bits[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}; - static const uint16_t distance_offset_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}; - static const uint16_t distance_extra_bits[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}; - - int symbol = 0; - while (symbol != 256) { - symbol = huffman_table_decode(length_literal_table->symbols, - length_literal_table->counts, bitstream); - if (symbol < 0) { - LOG0("Unknown symbol decoded"); - return false; - } - if (symbol < 256) { - OutputBuffer_push(output, (char)symbol); - } else if (symbol > 256) { - symbol -= 257; - int length = length_size_base[symbol] + - Bitstream_next_bits(bitstream, length_extra_bits[symbol]); - symbol = huffman_table_decode(distance_table->symbols, - distance_table->counts, bitstream); - if (symbol < 0) { - return false; - } - - int distance = - distance_offset_base[symbol] + - Bitstream_next_bits(bitstream, distance_extra_bits[symbol]); - while (length > 0) { - size_t output_buffer_length = OutputBuffer_length(output); - OutputBuffer_push( - output, (char)output->buffer[output_buffer_length - distance]); - length--; - } - } - } - - return true; -} - -bool deflate_decompress(Bitstream *bitstream, OutputBuffer *output) { - ASSERT(bitstream != NULL); - ASSERT(output != NULL); - - uint8_t b_final = 0; - while (!b_final) { - LOG0("Parse deflate block"); - b_final = Bitstream_next_bits(bitstream, BFINAL_LENGTH_BITS); - const uint8_t b_type = Bitstream_next_bits(bitstream, BTYPE_LENGTH_BITS); - if (b_type == DeflateBlockType_NoCompression) { - LOG0("Uncompressed deflate blocks aren't supported"); - abort(); - } else { - if (b_type == DeflateBlockType_FixedHuffman) { - static bool are_tables_blank = true; - static LengthLiteralTable length_literal_table = {0}; - static DistanceTable distance_table = {0}; - - uint16_t lenlit_codelengths[FIXED_LENGTH_LITERAL_CODE_COUNT]; - - if (are_tables_blank) { - for (int symbol = 0; symbol < 144; symbol++) { - lenlit_codelengths[symbol] = 8; - } - - for (int symbol = 144; symbol < 256; symbol++) { - lenlit_codelengths[symbol] = 9; - } - - for (int symbol = 256; symbol < 280; symbol++) { - lenlit_codelengths[symbol] = 7; - } - - for (int symbol = 280; symbol < FIXED_LENGTH_LITERAL_CODE_COUNT; - symbol++) { - lenlit_codelengths[symbol] = 8; - } - - build_huffman_table_from_codelengths( - length_literal_table.symbols, length_literal_table.counts, - lenlit_codelengths, FIXED_LENGTH_LITERAL_CODE_COUNT); - - uint16_t distance_codelengths[MAX_DISTANCE_CODES] = {0}; - for (int symbol = 0; symbol < MAX_DISTANCE_CODES; symbol++) { - distance_codelengths[symbol] = 5; - } - - build_huffman_table_from_codelengths( - distance_table.symbols, distance_table.counts, - distance_codelengths, MAX_DISTANCE_CODES); - are_tables_blank = false; - } - deflate_decompress_(bitstream, &length_literal_table, &distance_table, - output); - } else { - LengthLiteralTable length_literal_table = {0}; - DistanceTable distance_table = {0}; - const uint16_t hlit = Bitstream_next_bits(bitstream, 5) + 257; - const uint8_t hdist = Bitstream_next_bits(bitstream, 5) + 1; - const uint8_t hclen = Bitstream_next_bits(bitstream, 4) + 4; - LOGN("Dynamic table:\n" - "hlit: %d\n" - "hdist: %d\n" - "hclen: %d", - hlit, hdist, hclen); - CodeLengthTable codelength_table = {0}; - build_codelength_table(&codelength_table, bitstream, hclen); - - uint16_t lenlit_dist_codelengths[MAX_LENGTH_CODES + - MAX_DISTANCE_CODES] = {0}; - int index = 0; - while (index < hlit + hdist) { - int symbol = huffman_table_decode(codelength_table.symbols, - codelength_table.counts, bitstream); - if (symbol < 0) { - LOG0("Unknown symbol decoded using huffman table"); - return false; - } else if (symbol < 16) { - lenlit_dist_codelengths[index++] = symbol; - } else { - int repeat = 0; - int codelength = 0; - if (symbol == 16) { - repeat = 3 + Bitstream_next_bits(bitstream, 2); - codelength = lenlit_dist_codelengths[index - 1]; - } else if (symbol == 17) { - repeat = 3 + Bitstream_next_bits(bitstream, 3); - } else { - repeat = 11 + Bitstream_next_bits(bitstream, 7); - } - - for (int i = 0; i < repeat; i++) { - lenlit_dist_codelengths[index++] = codelength; - } - } - } - - // The block must have an end - ASSERT(lenlit_dist_codelengths[256] > 0); - - build_huffman_table_from_codelengths(length_literal_table.symbols, - length_literal_table.counts, - lenlit_dist_codelengths, hlit); - build_huffman_table_from_codelengths( - distance_table.symbols, distance_table.counts, - lenlit_dist_codelengths + hlit, hdist); - deflate_decompress_(bitstream, &length_literal_table, &distance_table, - output); - } - } - } - return true; -} - -char *zlib_decompress(const uint8_t *compressed_data_buffer, - const size_t compressed_data_length) { - ASSERT(compressed_data_buffer != NULL); - - Bitstream bitstream; - Bitstream_init(&bitstream, compressed_data_buffer, compressed_data_length); - - uint16_t cm = Bitstream_next_bits(&bitstream, CM_LENGTH_BITS); - uint16_t cinfo = Bitstream_next_bits(&bitstream, CINFO_LENGTH_BITS); - uint16_t fcheck = Bitstream_next_bits(&bitstream, FCHECK_LENGTH_BITS); - uint16_t fdict = Bitstream_next_bits(&bitstream, FDICT_LENGTH_BITS); - uint16_t flevel = Bitstream_next_bits(&bitstream, FLEVEL_LENGTH_BITS); - - LOGN("zlib informations:\n" - "- CM (compression method): %d\n" - "- CINFO (compression info): %d\n" - "- FCHECK (check bits for CMF and FLG): %d\n" - "- FDICT (preset dictionary): %d\n" - "- FLEVEL (compression level): %d", - cm, cinfo, fcheck, fdict, flevel); - uint16_t cmf = bitstream.data[0]; - uint16_t flg = bitstream.data[1]; - if ((cmf * 256 + flg) % 31 != 0) { - LOG0("fcheck validation failed"); - return false; - } - - if (fdict != 0) { - LOG0("preset dictionnaries are unsupported"); - return NULL; - } - - OutputBuffer output; - OutputBuffer_init(&output); - if (!deflate_decompress(&bitstream, &output)) { - LOG0("deflate decompression failed"); - return NULL; - } - - int adler32 = bitstream.data[bitstream.current_byte_index + 4] + - (bitstream.data[bitstream.current_byte_index + 3] << 8) + - (bitstream.data[bitstream.current_byte_index + 2] << 16) + - (bitstream.data[bitstream.current_byte_index + 1] << 24); - LOGN("Adler32 checksum: %d", adler32); - - uint32_t a = 1; - uint32_t b = 0; - for (size_t i = 0; i < output.len; i++) { - a = (a + (unsigned char)output.buffer[i]) % 65521; - b = (b + a) % 65521; - } - int computed_adler32 = (b << 16) | a; - LOGN("Computed Adler32 checksum: %d", computed_adler32); - - return output.buffer; -} diff --git a/lisiblepng/src/deflate.h b/lisiblepng/src/deflate.h deleted file mode 100644 index 77100c6..0000000 --- a/lisiblepng/src/deflate.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef LISIBLE_PNG_DEFLATE_H -#define LISIBLE_PNG_DEFLATE_H - -#include -#include -#include - -/// Decompresses zlib compressed data as defined by RFC 1950 -/// -/// @return A pointer to the decompressed data, the caller is responsible to -/// deallocate it using free(). In case of error, NULL is returned. -char *zlib_decompress(const uint8_t *compressed_data_buffer, - const size_t compressed_data_length); - -#endif // LISIBLE_PNG_DEFLATE_H diff --git a/lisiblepng/src/lisiblepng.c b/lisiblepng/src/lisiblepng.c index 5ccd300..7a3818b 100644 --- a/lisiblepng/src/lisiblepng.c +++ b/lisiblepng/src/lisiblepng.c @@ -1,7 +1,7 @@ #include "lisiblepng.h" -#include "assert.h" -#include "deflate.h" -#include "log.h" +#include "lisiblepng/assert.h" +#include "lisiblepng/deflate.h" +#include "lisiblepng/log.h" #include #include #include @@ -61,8 +61,39 @@ const uint32_t CRC32_TABLE[256] = { 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D}; +typedef enum { + ColourType_Greyscale = 0, + ColourType_Truecolour = 2, + ColourType_IndexedColour = 3, + ColourType_GreyscaleWithAlpha = 4, + ColourType_TruecolourWithAlpha = 6, + ColourType_Unknown +} ColourType; + +uint8_t ColourType_sample_count(const ColourType colour_type) { + switch (colour_type) { + case ColourType_Greyscale: + return 1; + case ColourType_Truecolour: + return 3; + case ColourType_IndexedColour: + return 1; + case ColourType_GreyscaleWithAlpha: + return 2; + case ColourType_TruecolourWithAlpha: + return 4; + default: + LPNG_LOG_ERR0("Unknown colour type"); + abort(); + } +} + struct Png { - const uint8_t *data; + char *data; + size_t width; + size_t height; + ColourType colour_type; + uint8_t bits_per_sample; }; typedef struct { @@ -103,7 +134,7 @@ long ParsingContext_cursor_position(DeflateDecompressor *ctx) { bool ParsingContext_skip_bytes(DeflateDecompressor *ctx, size_t byte_count) { ASSERT(ctx != NULL); if (fseek(ctx->stream, byte_count, SEEK_CUR) != 0) { - LOGN("Couldn't skip bytes: %s", strerror(errno)); + LPNG_LOG_ERR("Couldn't skip bytes: %s", strerror(errno)); return false; } @@ -115,7 +146,7 @@ bool ParsingContext_parse_bytes(DeflateDecompressor *ctx, size_t byte_count, ASSERT(ctx != NULL); ASSERT(output_buffer != NULL); if (fread(output_buffer, 1, byte_count, ctx->stream) < byte_count) { - LOG0("Couldn't parse bytes, EOF reached"); + LPNG_LOG_ERR0("Couldn't parse bytes, EOF reached"); return false; } @@ -180,16 +211,17 @@ typedef struct { void ImageHeader_print_image_header(const ImageHeader *image_header) { ASSERT(image_header != NULL); - LOGN("Image header:\n" - "- dimensions: %dx%d\n" - "- bit depth: %d\n" - "- colour type: %d\n" - "- compression method: %d\n" - "- filter method: %d\n" - "- interlace method: %d", - image_header->width, image_header->height, image_header->bit_depth, - image_header->colour_type, image_header->compression_method, - image_header->filter_method, image_header->interlace_method); + LPNG_LOG_DBG("Image header:\n" + "- dimensions: %dx%d\n" + "- bit depth: %d\n" + "- colour type: %d\n" + "- compression method: %d\n" + "- filter method: %d\n" + "- interlace method: %d", + image_header->width, image_header->height, + image_header->bit_depth, image_header->colour_type, + image_header->compression_method, image_header->filter_method, + image_header->interlace_method); } bool ParsingContext_validate_crc_if_required(DeflateDecompressor *ctx) { @@ -198,7 +230,7 @@ bool ParsingContext_validate_crc_if_required(DeflateDecompressor *ctx) { uint32_t crc; PARSE_FIELD(uint32_t, crc); if (computed_crc != crc) { - LOG0("Invalid CRC checksum"); + LPNG_LOG_ERR0("Invalid CRC checksum"); return false; } #else @@ -208,6 +240,11 @@ bool ParsingContext_validate_crc_if_required(DeflateDecompressor *ctx) { return true; } +bool is_valid_bit_depth(uint8_t bit_depth) { + return bit_depth == 1 || bit_depth == 2 || bit_depth == 4 || bit_depth == 8 || + bit_depth == 16; +} + bool parse_IHDR_chunk(DeflateDecompressor *ctx, ImageHeader *image_header) { ASSERT(ctx != NULL); ASSERT(image_header != NULL); @@ -220,7 +257,7 @@ bool parse_IHDR_chunk(DeflateDecompressor *ctx, ImageHeader *image_header) { uint32_t type; PARSE_FIELD(uint32_t, type); if (type != IHDR_CHUNK_TYPE) { - LOG0("Expected IHDR chunk"); + LPNG_LOG_ERR0("Expected IHDR chunk"); return false; } @@ -228,6 +265,10 @@ bool parse_IHDR_chunk(DeflateDecompressor *ctx, ImageHeader *image_header) { PARSE_FIELD(uint32_t, image_header->width); PARSE_FIELD(uint32_t, image_header->height); PARSE_FIELD(uint8_t, image_header->bit_depth); + if (!is_valid_bit_depth(image_header->bit_depth)) { + LPNG_LOG_ERR("Invalid bitdepth: %d", image_header->bit_depth); + return false; + } PARSE_FIELD(uint8_t, image_header->colour_type); PARSE_FIELD(uint8_t, image_header->compression_method); PARSE_FIELD(uint8_t, image_header->filter_method); @@ -265,6 +306,119 @@ uint32_t uint32_t_to_le(uint32_t value) { (value_bytes[2] << 8) + value_bytes[3]; } +uint8_t none_reconstruction_function(uint8_t recon_a, uint8_t recon_b, + uint8_t recon_c, uint8_t x) { + (void)recon_a; + (void)recon_b; + (void)recon_c; + return x; +} +uint8_t sub_reconstruction_function(uint8_t recon_a, uint8_t recon_b, + uint8_t recon_c, uint8_t x) { + (void)recon_b; + (void)recon_c; + return x + recon_a; +} +uint8_t up_reconstruction_function(uint8_t recon_a, uint8_t recon_b, + uint8_t recon_c, uint8_t x) { + (void)recon_a; + (void)recon_c; + return x + recon_b; +} +uint8_t average_reconstruction_function(uint8_t recon_a, uint8_t recon_b, + uint8_t recon_c, uint8_t x) { + (void)recon_c; + uint16_t sum = (recon_a + recon_b) / 2u; + return x + sum; +} +uint8_t paeth_predictor(uint8_t a, uint8_t b, uint8_t c) { + int16_t p = a + b - c; + int16_t pa = abs(p - a); + int16_t pb = abs(p - b); + int16_t pc = abs(p - c); + uint8_t pr; + if (pa <= pb && pa <= pc) { + pr = a; + } else if (pb <= pc) { + pr = b; + } else { + pr = c; + } + + return pr; +} +uint8_t paeth_reconstruction_function(uint8_t recon_a, uint8_t recon_b, + uint8_t recon_c, uint8_t x) { + return x + paeth_predictor(recon_a, recon_b, recon_c); +} +typedef uint8_t (*ReconstructionFn)(uint8_t, uint8_t, uint8_t, uint8_t); +static const ReconstructionFn reconstruction_functions[] = { + none_reconstruction_function, sub_reconstruction_function, + up_reconstruction_function, average_reconstruction_function, + paeth_reconstruction_function}; + +void apply_reconstruction_functions_to_scanline( + char *output_scanline, const char *input_scanline, + const char *previous_output_scanline, size_t filter_type, + size_t scanline_size, size_t bytes_per_pixel) { + ASSERT(output_scanline != NULL); + ASSERT(input_scanline != NULL); + ASSERT(filter_type < + sizeof(reconstruction_functions) / sizeof(ReconstructionFn)); + + for (size_t i = 0; i < scanline_size / bytes_per_pixel; i++) { + for (size_t p = 0; p < bytes_per_pixel; p++) { + uint8_t a = 0; + if (i > 0) { + a = output_scanline[i * bytes_per_pixel - bytes_per_pixel + p]; + } + + uint8_t b = 0; + uint8_t c = 0; + if (previous_output_scanline != NULL) { + b = previous_output_scanline[i * bytes_per_pixel + p]; + if (i > 0) { + c = previous_output_scanline[i * bytes_per_pixel - bytes_per_pixel + + p]; + } + } + + uint8_t x = input_scanline[i * bytes_per_pixel + p]; + output_scanline[i * bytes_per_pixel + p] = + reconstruction_functions[filter_type](a, b, c, x); + } + } +} + +void apply_reconstruction_functions(Png *image, + const char *decompressed_data_buffer) { + ASSERT(image != NULL); + ASSERT(decompressed_data_buffer != NULL); + size_t sample_count = ColourType_sample_count(image->colour_type); + size_t bits_per_pixel = (image->bits_per_sample * sample_count); + size_t bytes_per_pixel = bits_per_pixel / 8; + if (image->bits_per_sample < 8) { + bytes_per_pixel = 1; + } + size_t scanline_size = image->width * bits_per_pixel / 8; + + for (size_t scanline = 0; scanline < image->height; scanline++) { + size_t output_scanline_start = scanline_size * scanline; + size_t input_scanline_start = (scanline_size + 1) * scanline; + uint8_t filter_type = decompressed_data_buffer[input_scanline_start]; + const char *previous_output_scanline = NULL; + if (scanline > 0) { + size_t previous_output_scanline_start = scanline_size * (scanline - 1); + previous_output_scanline = &image->data[previous_output_scanline_start]; + } + + apply_reconstruction_functions_to_scanline( + &image->data[output_scanline_start], + &decompressed_data_buffer[input_scanline_start + 1], + previous_output_scanline, filter_type, scanline_size, bytes_per_pixel); + } +} + Png *lis_Png_parse(FILE *stream) { Png *png = malloc(sizeof(Png)); DeflateDecompressor ctx; @@ -273,12 +427,12 @@ Png *lis_Png_parse(FILE *stream) { uint8_t parsed_png_signature[PNG_SIGNATURE_LENGTH]; if (!ParsingContext_parse_bytes(&ctx, PNG_SIGNATURE_LENGTH, parsed_png_signature)) { - LOG0("Couldn't parse signature"); + LPNG_LOG_ERR0("Couldn't parse signature"); goto err; } if (!matches_png_signature(parsed_png_signature)) { - LOG0("Invalid signature"); + LPNG_LOG_ERR0("Invalid signature"); goto err; } @@ -289,40 +443,64 @@ Png *lis_Png_parse(FILE *stream) { ImageHeader_print_image_header(&header); ImageData image_data = {0}; + size_t parsed_data_chunk_count = 0; bool end_reached = false; while (!end_reached) { uint32_t length; if (!ParsingContext_parse_uint32_t(&ctx, &length)) { - LOG0("Couldn't parse chunk length"); + LPNG_LOG_ERR0("Couldn't parse chunk length"); goto cleanup_data; } ParsingContext_crc_reset(&ctx); uint32_t type; if (!ParsingContext_parse_uint32_t(&ctx, &type)) { - LOG0("Couldn't parse chunk type"); + LPNG_LOG_ERR0("Couldn't parse chunk type"); goto cleanup_data; } +#ifdef LPNG_DEBUG_LOG uint32_t type_le = uint32_t_to_le(type); - LOGN("Parsing %.4s chunk", (char *)&type_le); + LPNG_LOG_DBG("Parsing %.4s chunk", (char *)&type_le); +#endif + switch (type) { case IDAT_CHUNK_TYPE: - parse_IDAT_chunk(&ctx, length, &image_data); + if (!parse_IDAT_chunk(&ctx, length, &image_data)) { + LPNG_LOG_ERR0("Couldn't parse IDAT chunk"); + goto cleanup_data; + } + parsed_data_chunk_count++; break; case IEND_CHUNK_TYPE: end_reached = true; ParsingContext_skip_bytes(&ctx, sizeof(uint32_t)); break; default: - LOG0("Unknown chunk type, skipping chunk..."); + LPNG_LOG_DBG0("Unknown chunk type, skipping chunk..."); ParsingContext_skip_bytes(&ctx, length + sizeof(uint32_t)); break; } } - LOGN("Data length: %zul", image_data.length); - zlib_decompress(image_data.data, image_data.length); + if (parsed_data_chunk_count == 0) { + LPNG_LOG_ERR0("No IDAT chunk found, at least one is required"); + goto cleanup_data; + } + + LPNG_LOG_DBG("Data length: %zu", image_data.length); + png->width = header.width; + png->height = header.height; + png->colour_type = header.colour_type; + png->bits_per_sample = header.bit_depth; + size_t output_length; + char *output_buffer = + zlib_decompress(image_data.data, image_data.length, &output_length); + png->data = output_buffer; + + apply_reconstruction_functions(png, output_buffer); + + free(image_data.data); return png; @@ -334,4 +512,60 @@ err: #undef PARSE_FIELD void lis_Png_destroy(Png *png) { free(png); } -void lis_Png_dump_ppm(const Png *png) { ASSERT(png != NULL); } +void lis_Png_dump_ppm(const Png *png) { + ASSERT(png != NULL); + printf("P3\n"); + printf("%zu %zu\n", png->width, png->height); + printf("%d\n", (1 << png->bits_per_sample) - 1); + size_t sample_count = ColourType_sample_count(png->colour_type); + size_t bits_per_pixel = png->bits_per_sample * sample_count; + size_t bytes_per_pixel = bits_per_pixel / 8; + if (png->bits_per_sample < 8) { + bytes_per_pixel = 1; + } + for (size_t pixel_index = 0; pixel_index < png->height * png->width; + pixel_index++) { + + if (png->colour_type == ColourType_Greyscale) { + if (bits_per_pixel == 16) { + uint8_t hi = png->data[pixel_index * bytes_per_pixel]; + uint8_t lo = png->data[pixel_index * bytes_per_pixel + 1]; + uint16_t grey = ((hi & 0xFFu) << 8) | (lo & 0xFFu); + printf("%u %u %u\n", grey, grey, grey); + } else { + size_t absolute_bit_offset = pixel_index * bits_per_pixel; + size_t byte_offset = absolute_bit_offset / 8; + size_t relative_bit_offset = absolute_bit_offset % 8; + unsigned char grey = + (png->data[byte_offset] >> + (7 - relative_bit_offset - (bits_per_pixel - 1))) & + ((1 << bits_per_pixel) - 1); + printf("%u %u %u\n", grey, grey, grey); + } + } else if (png->colour_type == ColourType_Truecolour) { + if (png->bits_per_sample == 16) { + uint8_t hi_r = png->data[pixel_index * bytes_per_pixel]; + uint8_t lo_r = png->data[pixel_index * bytes_per_pixel + 1]; + uint16_t r = ((hi_r & 0xFFu) << 8) | (lo_r & 0xFFu); + + uint8_t hi_g = png->data[pixel_index * bytes_per_pixel + 2]; + uint8_t lo_g = png->data[pixel_index * bytes_per_pixel + 3]; + uint16_t g = ((hi_g & 0xFFu) << 8) | (lo_g & 0xFFu); + + uint8_t hi_b = png->data[pixel_index * bytes_per_pixel + 4]; + uint8_t lo_b = png->data[pixel_index * bytes_per_pixel + 5]; + uint16_t b = ((hi_b & 0xFFu) << 8) | (lo_b & 0xFFu); + + printf("%u %u %u\n", r, g, b); + } else { + uint8_t r = png->data[pixel_index * bytes_per_pixel]; + uint8_t g = png->data[pixel_index * bytes_per_pixel + 1]; + uint8_t b = png->data[pixel_index * bytes_per_pixel + 2]; + printf("%u %u %u\n", r, g, b); + } + } else { + LPNG_LOG_ERR0("Unsupported colour type"); + exit(1); + } + } +} diff --git a/lisiblepng/src/lisiblepng/assert.h b/lisiblepng/src/lisiblepng/assert.h new file mode 100644 index 0000000..1de9c36 --- /dev/null +++ b/lisiblepng/src/lisiblepng/assert.h @@ -0,0 +1,15 @@ +#ifndef LISIBLE_PNG_ASSET_H +#define LISIBLE_PNG_ASSET_H + +#include "log.h" + +#define ASSERT(predicate) \ + do { \ + if (!(predicate)) { \ + LPNG_LOG_ERR("Assertion failed in %s:%d:\n\t%s", __FILE__, __LINE__, \ + #predicate); \ + exit(1); \ + } \ + } while (0) + +#endif // LISIBLE_PNG_ASSET_H diff --git a/lisiblepng/src/lisiblepng/bitstream.c b/lisiblepng/src/lisiblepng/bitstream.c new file mode 100644 index 0000000..e7ddb79 --- /dev/null +++ b/lisiblepng/src/lisiblepng/bitstream.c @@ -0,0 +1,53 @@ +#include "bitstream.h" +#include "assert.h" + +#define MAX(x, y) (((x) > (y)) ? (x) : (y)) +#define MIN(x, y) (((x) < (y)) ? (x) : (y)) + +void Bitstream_init(Bitstream *bitstream, const uint8_t *data, + size_t data_size) { + ASSERT(bitstream != NULL); + ASSERT(data != NULL); + bitstream->data = data; + bitstream->data_size = data_size; + bitstream->current_byte_index = 0; + bitstream->current_bit_offset = 0; +} + +void bitstream_advance(Bitstream *bitstream, size_t bit_count) { + ASSERT(bitstream != NULL); + uint8_t current_bit = bitstream->current_bit_offset; + bitstream->current_byte_index = + bitstream->current_byte_index + (current_bit + bit_count) / 8; + bitstream->current_bit_offset = (current_bit + bit_count) % 8; +} + +void Bitstream_skip(Bitstream *bitstream, size_t bit_count) { + ASSERT(bitstream != NULL); + bitstream_advance(bitstream, bit_count); +} + +uint16_t Bitstream_next_bits(Bitstream *bitstream, int bit_count) { + ASSERT(bitstream != NULL); + ASSERT(bit_count <= 16); + ASSERT((bitstream->current_bit_offset + (size_t)bit_count) / 8 <= + bitstream->data_size); + + int bit_to_read = bit_count; + uint16_t val = bitstream->data[bitstream->current_byte_index] >> + bitstream->current_bit_offset; + + size_t bit_read = MIN(bit_count, 8 - bitstream->current_bit_offset); + bitstream_advance(bitstream, bit_read); + bit_to_read -= bit_read; + while (bit_to_read > 0) { + val |= (bitstream->data[bitstream->current_byte_index] >> + bitstream->current_bit_offset) + << bit_read; + bit_read = MIN(bit_to_read, 8 - bitstream->current_bit_offset); + bitstream_advance(bitstream, bit_read); + bit_to_read -= bit_read; + } + + return (val & ((1 << bit_count) - 1)); +} diff --git a/lisiblepng/src/lisiblepng/bitstream.h b/lisiblepng/src/lisiblepng/bitstream.h new file mode 100644 index 0000000..72d8295 --- /dev/null +++ b/lisiblepng/src/lisiblepng/bitstream.h @@ -0,0 +1,20 @@ +#ifndef CUTTERENG_BITSTREAM_H +#define CUTTERENG_BITSTREAM_H + +#include +#include + +typedef struct { + const uint8_t *data; + size_t data_size; + + size_t current_byte_index; + uint8_t current_bit_offset; +} Bitstream; + +void Bitstream_init(Bitstream *bitstream, const uint8_t *data, + size_t data_size); +void Bitstream_skip(Bitstream *bitstream, size_t bit_count); +uint16_t Bitstream_next_bits(Bitstream *bitstream, int bit_count); + +#endif // CUTTERENG_BITSTREAM_H diff --git a/lisiblepng/src/lisiblepng/deflate.c b/lisiblepng/src/lisiblepng/deflate.c new file mode 100644 index 0000000..50f90e3 --- /dev/null +++ b/lisiblepng/src/lisiblepng/deflate.c @@ -0,0 +1,419 @@ +#include "deflate.h" +#include "assert.h" +#include "bitstream.h" +#include + +#define CM_LENGTH_BITS 4 +#define CINFO_LENGTH_BITS 4 +#define FCHECK_LENGTH_BITS 5 +#define FDICT_LENGTH_BITS 1 +#define FLEVEL_LENGTH_BITS 2 + +#define BFINAL_LENGTH_BITS 1 +#define BTYPE_LENGTH_BITS 2 + +#define CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT 19 +#define MAX_HUFFMAN_CODE_LENGTH 15 +#define MAX_LENGTH_CODES 288 +#define MAX_DISTANCE_CODES 32 +#define FIXED_LENGTH_LITERAL_CODE_COUNT 288 + +typedef enum { + DeflateBlockType_NoCompression, + DeflateBlockType_FixedHuffman, + DeflateBlockType_DynamicHuffman, + DeflateBlockType_Error +} DeflateBlockType; + +typedef struct { + uint16_t counts[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT]; + uint16_t symbols[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT]; +} CodeLengthTable; + +typedef struct { + uint16_t counts[MAX_LENGTH_CODES]; + uint16_t symbols[MAX_LENGTH_CODES]; +} LengthLiteralTable; + +typedef struct { + uint16_t counts[MAX_DISTANCE_CODES]; + uint16_t symbols[MAX_DISTANCE_CODES]; +} DistanceTable; + +#define DEFLATE_OUTPUT_BUFFER_INITIAL_CAPACITY (1024 * 256) + +typedef struct { + char *buffer; + size_t len; + size_t cap; +} OutputBuffer; + +void OutputBuffer_init(OutputBuffer *output_buffer) { + ASSERT(output_buffer != NULL); + output_buffer->buffer = calloc(DEFLATE_OUTPUT_BUFFER_INITIAL_CAPACITY, 1); + if (!output_buffer->buffer) { + LPNG_LOG_ERR0("Couldn't allocate deflate output buffer (out of memory?)"); + abort(); + } + output_buffer->cap = DEFLATE_OUTPUT_BUFFER_INITIAL_CAPACITY; + output_buffer->len = 0; +} + +void OutputBuffer_expand(OutputBuffer *output_buffer) { + ASSERT(output_buffer != NULL); + size_t new_cap = output_buffer->cap * 2; + output_buffer->buffer = realloc(output_buffer->buffer, new_cap); + if (!output_buffer->buffer) { + LPNG_LOG_ERR0("Couldn't reallocate deflate output buffer (out of memory?)"); + abort(); + } + + output_buffer->cap = new_cap; +} + +void OutputBuffer_push(OutputBuffer *output_buffer, char byte) { + ASSERT(output_buffer != NULL); + if (output_buffer->len == output_buffer->cap) { + OutputBuffer_expand(output_buffer); + } + + output_buffer->buffer[output_buffer->len++] = byte; +} + +size_t OutputBuffer_length(const OutputBuffer *output_buffer) { + ASSERT(output_buffer != NULL); + return output_buffer->len; +} + +int huffman_table_decode(const uint16_t *symbols, const uint16_t *counts, + Bitstream *bitstream) { + ASSERT(symbols != NULL); + ASSERT(counts != NULL); + ASSERT(bitstream != NULL); + int code = 0; + int index = 0; + int first = 0; + for (int i = 1; i <= MAX_HUFFMAN_CODE_LENGTH; i++) { + code |= Bitstream_next_bits(bitstream, 1); + int count = counts[i]; + if (code - count < first) { + return symbols[index + (code - first)]; + } + + index += count; + first += count; + first <<= 1; + code <<= 1; + } + + return -1; +} + +void build_huffman_table_from_codelengths(uint16_t *symbols, uint16_t *counts, + const uint16_t *codelengths, + uint16_t codelength_count) { + ASSERT(symbols != NULL); + ASSERT(counts != NULL); + ASSERT(codelengths != NULL); + + for (int i = 0; i < codelength_count; i++) { + counts[codelengths[i]]++; + } + counts[0] = 0; + + uint16_t next_code[MAX_HUFFMAN_CODE_LENGTH + 1] = {0}; + for (int i = 1; i < MAX_HUFFMAN_CODE_LENGTH; i++) { + next_code[i + 1] = next_code[i] + counts[i]; + } + + for (int i = 0; i < codelength_count; i++) { + if (codelengths[i] == 0) { + continue; + } + + symbols[next_code[codelengths[i]]++] = i; + } +} +void CodeLengthTable_build_from_codelengths( + CodeLengthTable *table, + uint16_t codelength_codelengths[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT]) { + ASSERT(table != NULL); + ASSERT(codelength_codelengths != NULL); + static const uint8_t CODELENGTH_MAPPING[] = { + 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; + uint16_t mapped_codelengths[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT] = {0}; + for (int i = 0; i < CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT; i++) { + mapped_codelengths[CODELENGTH_MAPPING[i]] = codelength_codelengths[i]; + } + + build_huffman_table_from_codelengths(table->symbols, table->counts, + mapped_codelengths, + CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT); +} + +void build_codelength_table(CodeLengthTable *codelength_table, + Bitstream *bitstream, const uint8_t hclen) { + ASSERT(codelength_table != NULL); + ASSERT(bitstream != NULL); + + uint16_t codelengths_codelengths[CODE_LENGTH_ALPHABET_MAX_SYMBOL_COUNT] = {0}; + for (int i = 0; i < hclen; i++) { + codelengths_codelengths[i] = Bitstream_next_bits(bitstream, 3); + } + + CodeLengthTable_build_from_codelengths(codelength_table, + codelengths_codelengths); +} + +bool deflate_decompress_(Bitstream *bitstream, + const LengthLiteralTable *length_literal_table, + const DistanceTable *distance_table, + OutputBuffer *output) { + ASSERT(bitstream != NULL); + ASSERT(output != NULL); + ASSERT(length_literal_table != NULL); + ASSERT(distance_table != NULL); + static const uint16_t length_size_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}; + static const uint16_t length_extra_bits[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}; + static const uint16_t distance_offset_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}; + static const uint16_t distance_extra_bits[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}; + + int symbol = 0; + while (symbol != 256) { + symbol = huffman_table_decode(length_literal_table->symbols, + length_literal_table->counts, bitstream); + if (symbol < 0) { + LPNG_LOG_ERR0("Unknown symbol decoded"); + return false; + } + if (symbol < 256) { + OutputBuffer_push(output, (char)symbol); + } else if (symbol > 256) { + symbol -= 257; + int length = length_size_base[symbol] + + Bitstream_next_bits(bitstream, length_extra_bits[symbol]); + symbol = huffman_table_decode(distance_table->symbols, + distance_table->counts, bitstream); + if (symbol < 0) { + return false; + } + + int distance = + distance_offset_base[symbol] + + Bitstream_next_bits(bitstream, distance_extra_bits[symbol]); + while (length > 0) { + size_t output_buffer_length = OutputBuffer_length(output); + OutputBuffer_push( + output, (char)output->buffer[output_buffer_length - distance]); + length--; + } + } + } + + return true; +} + +bool deflate_decompress(Bitstream *bitstream, OutputBuffer *output) { + ASSERT(bitstream != NULL); + ASSERT(output != NULL); + + uint8_t b_final = 0; + while (!b_final) { + LPNG_LOG_DBG0("Parse deflate block"); + b_final = Bitstream_next_bits(bitstream, BFINAL_LENGTH_BITS); + const uint8_t b_type = Bitstream_next_bits(bitstream, BTYPE_LENGTH_BITS); + if (b_type == DeflateBlockType_NoCompression) { + LPNG_LOG_ERR0("Uncompressed deflate blocks aren't supported"); + abort(); + } else { + if (b_type == DeflateBlockType_FixedHuffman) { + LPNG_LOG_ERR0("Static huffman table"); + static bool are_tables_blank = true; + static LengthLiteralTable length_literal_table = {0}; + static DistanceTable distance_table = {0}; + + uint16_t lenlit_codelengths[FIXED_LENGTH_LITERAL_CODE_COUNT]; + + if (are_tables_blank) { + LPNG_LOG_ERR0("Computing static huffman table"); + for (int symbol = 0; symbol < 144; symbol++) { + lenlit_codelengths[symbol] = 8; + } + + for (int symbol = 144; symbol < 256; symbol++) { + lenlit_codelengths[symbol] = 9; + } + + for (int symbol = 256; symbol < 280; symbol++) { + lenlit_codelengths[symbol] = 7; + } + + for (int symbol = 280; symbol < FIXED_LENGTH_LITERAL_CODE_COUNT; + symbol++) { + lenlit_codelengths[symbol] = 8; + } + + build_huffman_table_from_codelengths( + length_literal_table.symbols, length_literal_table.counts, + lenlit_codelengths, FIXED_LENGTH_LITERAL_CODE_COUNT); + + uint16_t distance_codelengths[MAX_DISTANCE_CODES] = {0}; + for (int symbol = 0; symbol < MAX_DISTANCE_CODES; symbol++) { + distance_codelengths[symbol] = 5; + } + + build_huffman_table_from_codelengths( + distance_table.symbols, distance_table.counts, + distance_codelengths, MAX_DISTANCE_CODES); + are_tables_blank = false; + } + deflate_decompress_(bitstream, &length_literal_table, &distance_table, + output); + } else { + LengthLiteralTable length_literal_table = {0}; + DistanceTable distance_table = {0}; + const uint16_t hlit = Bitstream_next_bits(bitstream, 5) + 257; + const uint8_t hdist = Bitstream_next_bits(bitstream, 5) + 1; + const uint8_t hclen = Bitstream_next_bits(bitstream, 4) + 4; + LPNG_LOG_DBG("Dynamic table:\n" + "hlit: %d\n" + "hdist: %d\n" + "hclen: %d", + hlit, hdist, hclen); + CodeLengthTable codelength_table = {0}; + build_codelength_table(&codelength_table, bitstream, hclen); + + uint16_t lenlit_dist_codelengths[MAX_LENGTH_CODES + + MAX_DISTANCE_CODES] = {0}; + int index = 0; + while (index < hlit + hdist) { + int symbol = huffman_table_decode(codelength_table.symbols, + codelength_table.counts, bitstream); + if (symbol < 0) { + LPNG_LOG_ERR0("Unknown symbol decoded using huffman table"); + return false; + } else if (symbol < 16) { + lenlit_dist_codelengths[index++] = symbol; + } else { + int repeat = 0; + int codelength = 0; + if (symbol == 16) { + repeat = 3 + Bitstream_next_bits(bitstream, 2); + codelength = lenlit_dist_codelengths[index - 1]; + } else if (symbol == 17) { + repeat = 3 + Bitstream_next_bits(bitstream, 3); + } else { + repeat = 11 + Bitstream_next_bits(bitstream, 7); + } + + for (int i = 0; i < repeat; i++) { + lenlit_dist_codelengths[index++] = codelength; + } + } + } + + // The block must have an end + ASSERT(lenlit_dist_codelengths[256] > 0); + + build_huffman_table_from_codelengths(length_literal_table.symbols, + length_literal_table.counts, + lenlit_dist_codelengths, hlit); + build_huffman_table_from_codelengths( + distance_table.symbols, distance_table.counts, + lenlit_dist_codelengths + hlit, hdist); + + deflate_decompress_(bitstream, &length_literal_table, &distance_table, + output); + } + } + } + return true; +} + +char *zlib_decompress(const uint8_t *compressed_data_buffer, + const size_t compressed_data_length, + size_t *output_length) { + ASSERT(compressed_data_buffer != NULL); + + Bitstream bitstream; + Bitstream_init(&bitstream, compressed_data_buffer, compressed_data_length); + + uint16_t cm = Bitstream_next_bits(&bitstream, CM_LENGTH_BITS); + uint16_t cinfo = Bitstream_next_bits(&bitstream, CINFO_LENGTH_BITS); + uint16_t fcheck = Bitstream_next_bits(&bitstream, FCHECK_LENGTH_BITS); + uint16_t fdict = Bitstream_next_bits(&bitstream, FDICT_LENGTH_BITS); + uint16_t flevel = Bitstream_next_bits(&bitstream, FLEVEL_LENGTH_BITS); + +#ifdef LPNG_DEBUG_LOG + LPNG_LOG_DBG("zlib informations:\n" + "- CM (compression method): %d\n" + "- CINFO (compression info): %d\n" + "- FCHECK (check bits for CMF and FLG): %d\n" + "- FDICT (preset dictionary): %d\n" + "- FLEVEL (compression level): %d", + cm, cinfo, fcheck, fdict, flevel); +#else + (void)cm; + (void)cinfo; + (void)fcheck; +#endif // LPNG_DEBUG_LOG + + uint16_t cmf = bitstream.data[0]; + uint16_t flg = bitstream.data[1]; + if ((cmf * 256 + flg) % 31 != 0) { + LPNG_LOG_ERR0("fcheck validation failed"); + return false; + } + + if (flevel > 9) { + LPNG_LOG_ERR0("Invalid compression level"); + return NULL; + } + + if (fdict != 0) { + LPNG_LOG_ERR0("preset dictionnaries are unsupported"); + return NULL; + } + + OutputBuffer output; + OutputBuffer_init(&output); + if (!deflate_decompress(&bitstream, &output)) { + LPNG_LOG_ERR0("deflate decompression failed"); + return NULL; + } + + size_t adler32_offset = bitstream.current_byte_index; + if (bitstream.current_bit_offset % 8 != 0) { + adler32_offset++; + } + + uint32_t adler32 = bitstream.data[adler32_offset + 3] + + (bitstream.data[adler32_offset + 2] << 8) + + (bitstream.data[adler32_offset + 1] << 16) + + (bitstream.data[adler32_offset] << 24); + LPNG_LOG_DBG("Adler32 checksum: %u", adler32); + uint32_t a = 1; + uint32_t b = 0; + for (size_t i = 0; i < output.len; i++) { + a = (a + (uint8_t)output.buffer[i]) % 65521; + b = (b + a) % 65521; + } + uint32_t computed_adler32 = (b << 16) | a; + LPNG_LOG_DBG("Computed Adler32 checksum: %u", computed_adler32); + if (adler32 != computed_adler32) { + LPNG_LOG_ERR0("Invalid checksum"); + exit(1); + } + + *output_length = output.len; + return output.buffer; +} diff --git a/lisiblepng/src/lisiblepng/deflate.h b/lisiblepng/src/lisiblepng/deflate.h new file mode 100644 index 0000000..88a3711 --- /dev/null +++ b/lisiblepng/src/lisiblepng/deflate.h @@ -0,0 +1,19 @@ +#ifndef LISIBLE_PNG_DEFLATE_H +#define LISIBLE_PNG_DEFLATE_H + +#include +#include +#include + +/// Decompresses zlib compressed data as defined by RFC 1950 +/// +/// @param compressed_data_buffer The compressed data +/// @param compressed_data_length The length in bytes of the compressed data +/// @param output_length The pointer to write the output length to +/// @return A pointer to the decompressed data, the caller is responsible to +/// deallocate it using free(). In case of error, NULL is returned. +char *zlib_decompress(const uint8_t *compressed_data_buffer, + const size_t compressed_data_length, + size_t *output_length); + +#endif // LISIBLE_PNG_DEFLATE_H diff --git a/lisiblepng/src/lisiblepng/log.h b/lisiblepng/src/lisiblepng/log.h new file mode 100644 index 0000000..720acd1 --- /dev/null +++ b/lisiblepng/src/lisiblepng/log.h @@ -0,0 +1,23 @@ +#ifndef LISIBLE_PNG_LOG_H +#define LISIBLE_PNG_LOG_H + +#include + +#define LPNG_LOG_PREFIX "LPNG: " +#define LPNG_DEBUG_LOG_PREFIX "%s:%d " LPNG_LOG_PREFIX +#define LPNG_LOG_ERR0(fmt) fprintf(stderr, LPNG_LOG_PREFIX fmt "\n") +#define LPNG_LOG_ERR(fmt, ...) \ + fprintf(stderr, LPNG_LOG_PREFIX fmt "\n", __VA_ARGS__) + +#ifdef LPNG_DEBUG_LOG +#define LPNG_LOG_DBG0(fmt) \ + fprintf(stderr, LPNG_DEBUG_LOG_PREFIX fmt "\n", __FILE__, __LINE__) +#define LPNG_LOG_DBG(fmt, ...) \ + fprintf(stderr, LPNG_DEBUG_LOG_PREFIX fmt "\n", __FILE__, __LINE__, \ + __VA_ARGS__) +#else +#define LPNG_LOG_DBG0(fmt) +#define LPNG_LOG_DBG(fmt, ...) +#endif // LPNG_DEBUG_LOG + +#endif // LISIBLE_PNG_LOG_H diff --git a/lisiblepng/src/log.h b/lisiblepng/src/log.h deleted file mode 100644 index fba6820..0000000 --- a/lisiblepng/src/log.h +++ /dev/null @@ -1,9 +0,0 @@ -#ifndef LISIBLE_PNG_LOG_H -#define LISIBLE_PNG_LOG_H - -#include - -#define LOG0(fmt) fprintf(stderr, fmt "\n") -#define LOGN(fmt, ...) fprintf(stderr, fmt "\n", __VA_ARGS__) - -#endif // LISIBLE_PNG_LOG_H -- cgit v1.2.3