diff options
Diffstat (limited to 'lisiblepng/src/lisiblepng')
| -rw-r--r-- | lisiblepng/src/lisiblepng/assert.h | 15 | ||||
| -rw-r--r-- | lisiblepng/src/lisiblepng/bitstream.c | 53 | ||||
| -rw-r--r-- | lisiblepng/src/lisiblepng/bitstream.h | 20 | ||||
| -rw-r--r-- | lisiblepng/src/lisiblepng/deflate.c | 419 | ||||
| -rw-r--r-- | lisiblepng/src/lisiblepng/deflate.h | 19 | ||||
| -rw-r--r-- | lisiblepng/src/lisiblepng/log.h | 23 |
6 files changed, 549 insertions, 0 deletions
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 <stdint.h> +#include <stdlib.h> + +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 <string.h> + +#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 <stdbool.h> +#include <stdint.h> +#include <stdlib.h> + +/// 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 <stdio.h> + +#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 |
