From fe2a38686946c708c2e52031459673a10db41dc8 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Mon, 3 Apr 2017 10:22:12 +0100 Subject: Test tool: Add option to disable output. --- test/decode_gif.c | 66 ++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 41 insertions(+), 25 deletions(-) diff --git a/test/decode_gif.c b/test/decode_gif.c index aafe7f6..0ce53c7 100644 --- a/test/decode_gif.c +++ b/test/decode_gif.c @@ -135,19 +135,22 @@ static void warning(const char *context, gif_result code) fprintf(stderr, "\n"); } -static void write_ppm(FILE* fh, const char *name, gif_animation *gif) +static void write_ppm(FILE* fh, const char *name, gif_animation *gif, + bool no_write) { unsigned int i; gif_result code; - fprintf(fh, "P3\n"); - fprintf(fh, "# %s\n", name); - fprintf(fh, "# width %u \n", gif->width); - fprintf(fh, "# height %u \n", gif->height); - fprintf(fh, "# frame_count %u \n", gif->frame_count); - fprintf(fh, "# frame_count_partial %u \n", gif->frame_count_partial); - fprintf(fh, "# loop_count %u \n", gif->loop_count); - fprintf(fh, "%u %u 256\n", gif->width, gif->height * gif->frame_count); + if (!no_write) { + fprintf(fh, "P3\n"); + fprintf(fh, "# %s\n", name); + fprintf(fh, "# width %u \n", gif->width); + fprintf(fh, "# height %u \n", gif->height); + fprintf(fh, "# frame_count %u \n", gif->frame_count); + fprintf(fh, "# frame_count_partial %u \n", gif->frame_count_partial); + fprintf(fh, "# loop_count %u \n", gif->loop_count); + fprintf(fh, "%u %u 256\n", gif->width, gif->height * gif->frame_count); + } /* decode the frames */ for (i = 0; i != gif->frame_count; i++) { @@ -158,17 +161,19 @@ static void write_ppm(FILE* fh, const char *name, gif_animation *gif) if (code != GIF_OK) warning("gif_decode_frame", code); - fprintf(fh, "# frame %u:\n", i); - image = (unsigned char *) gif->frame_image; - for (row = 0; row != gif->height; row++) { - for (col = 0; col != gif->width; col++) { - size_t z = (row * gif->width + col) * 4; - fprintf(fh, "%u %u %u ", - (unsigned char) image[z], - (unsigned char) image[z + 1], - (unsigned char) image[z + 2]); + if (!no_write) { + fprintf(fh, "# frame %u:\n", i); + image = (unsigned char *) gif->frame_image; + for (row = 0; row != gif->height; row++) { + for (col = 0; col != gif->width; col++) { + size_t z = (row * gif->width + col) * 4; + fprintf(fh, "%u %u %u ", + (unsigned char) image[z], + (unsigned char) image[z + 1], + (unsigned char) image[z + 2]); + } + fprintf(fh, "\n"); } - fprintf(fh, "\n"); } } @@ -189,17 +194,28 @@ int main(int argc, char *argv[]) gif_result code; unsigned char *data; FILE *outf = stdout; + bool no_write = false; if (argc < 2) { fprintf(stderr, "Usage: %s image.gif [out]\n", argv[0]); + fprintf(stderr, "\n"); + fprintf(stderr, "If [out] is NOWRITE, the gif will be docoded " + "but not output.\n"); + fprintf(stderr, "Otherwise [out] is an output filename.\n"); + fprintf(stderr, "When [out] is unset, output is to stdout.\n"); + return 1; } if (argc > 2) { - outf = fopen(argv[2], "w+"); - if (outf == NULL) { - fprintf(stderr, "Unable to open %s for writing\n", argv[2]); - return 2; + if (strcmp(argv[2], "NOWRITE") == 0) { + no_write = true; + } else { + outf = fopen(argv[2], "w+"); + if (outf == NULL) { + fprintf(stderr, "Unable to open %s for writing\n", argv[2]); + return 2; + } } } @@ -218,9 +234,9 @@ int main(int argc, char *argv[]) } } while (code != GIF_OK); - write_ppm(outf, argv[1], &gif); + write_ppm(outf, argv[1], &gif, no_write); - if (argc > 2) { + if (argc > 2 && !no_write) { fclose(outf); } -- cgit v1.2.3 From 8c42f9f934005ba40645ba326b74c8f8b0675df2 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Mon, 3 Apr 2017 10:03:18 +0100 Subject: New LZW decoder: Routine to extract LZW codes from GIF sub-block sequences. --- src/lzw.c | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lzw.h | 28 ++++++++++++ 2 files changed, 177 insertions(+) create mode 100644 src/lzw.c create mode 100644 src/lzw.h diff --git a/src/lzw.c b/src/lzw.c new file mode 100644 index 0000000..23c815e --- /dev/null +++ b/src/lzw.c @@ -0,0 +1,149 @@ +/* + * This file is part of NetSurf's LibNSGIF, http://www.netsurf-browser.org/ + * Licensed under the MIT License, + * http://www.opensource.org/licenses/mit-license.php + * + * Copyright 2017 Michael Drake + */ + +#include +#include +#include + +#include "lzw.h" + +/** + * \file + * \brief LZW decompression (implementation) + * + * Decoder for GIF LZW data. + */ + + +/** + * Context for reading LZW data. + * + * LZW data is split over multiple sub-blocks. Each sub-block has a + * byte at the start, which says the sub-block size, and then the data. + * Zero-size sub-blocks have no data, and the biggest sub-block size is + * 255, which means there are 255 bytes of data following the sub-block + * size entry. + * + * Note that an individual LZW code can be split over up to three sub-blocks. + */ +struct lzw_read_ctx { + const uint8_t *data; /**< Pointer to start of input data */ + uint32_t data_len; /**< Input data length */ + uint32_t data_sb_next; /**< Offset to sub-block size */ + + const uint8_t *sb_data; /**< Pointer to current sub-block in data */ + uint32_t sb_bit; /**< Current bit offset in sub-block */ + uint32_t sb_bit_count; /**< Bit count in sub-block */ +}; + + +/** + * Advance the context to the next sub-block in the input data. + * + * \param[in] ctx LZW reading context, updated on success. + * \return LZW_OK or LZW_OK_EOD on success, appropriate error otherwise. + */ +static lzw_result lzw__block_advance(struct lzw_read_ctx *ctx) +{ + uint32_t block_size; + uint32_t next_block_pos = ctx->data_sb_next; + const uint8_t *data_next = ctx->data + next_block_pos; + + if (next_block_pos >= ctx->data_len) { + return LZW_NO_DATA; + } + + block_size = *data_next; + + if ((next_block_pos + block_size) >= ctx->data_len) { + return LZW_NO_DATA; + } + + ctx->sb_bit = 0; + ctx->sb_bit_count = block_size * 8; + + if (block_size == 0) { + ctx->data_sb_next += 1; + return LZW_OK_EOD; + } + + ctx->sb_data = data_next + 1; + ctx->data_sb_next += block_size + 1; + + return LZW_OK; +} + + +/** + * Get the next LZW code of given size from the raw input data. + * + * Reads codes from the input data stream coping with GIF data sub-blocks. + * + * \param[in] ctx LZW reading context, updated. + * \param[in] code_size Size of LZW code to get from data. + * \param[out] code_out Returns an LZW code on success. + * \return LZW_OK or LZW_OK_EOD on success, appropriate error otherwise. + */ +static inline lzw_result lzw__next_code( + struct lzw_read_ctx *ctx, + uint8_t code_size, + uint32_t *code_out) +{ + uint32_t code = 0; + uint8_t current_bit = ctx->sb_bit & 0x7; + uint8_t byte_advance = (current_bit + code_size) >> 3; + + if (ctx->sb_bit + code_size < ctx->sb_bit_count) { + /* Fast path: code fully inside this sub-block */ + const uint8_t *data = ctx->sb_data + (ctx->sb_bit >> 3); + switch (byte_advance) { + case 2: code |= data[2] << 16; + case 1: code |= data[1] << 8; + case 0: code |= data[0] << 0; + } + ctx->sb_bit += code_size; + } else { + /* Slow path: code spans sub-blocks */ + uint8_t byte = 0; + uint8_t bits_remaining_0 = (code_size < (8 - current_bit)) ? + code_size : (8 - current_bit); + uint8_t bits_remaining_1 = code_size - bits_remaining_0; + uint8_t bits_used[3] = { + [0] = bits_remaining_0, + [1] = bits_remaining_1 < 8 ? bits_remaining_1 : 8, + [2] = bits_remaining_1 - 8, + }; + + while (true) { + const uint8_t *data = ctx->sb_data; + lzw_result res; + + /* Get any data from end of this sub-block */ + while (byte <= byte_advance && + ctx->sb_bit < ctx->sb_bit_count) { + code |= data[ctx->sb_bit >> 3] << (byte << 3); + ctx->sb_bit += bits_used[byte]; + byte++; + } + + /* Check if we have all we need */ + if (byte > byte_advance) { + break; + } + + /* Move to next sub-block */ + res = lzw__block_advance(ctx); + if (res != LZW_OK) { + return res; + } + } + } + + *code_out = (code >> current_bit) & ((1 << code_size) - 1); + return LZW_OK; +} diff --git a/src/lzw.h b/src/lzw.h new file mode 100644 index 0000000..0683ad0 --- /dev/null +++ b/src/lzw.h @@ -0,0 +1,28 @@ +/* + * This file is part of NetSurf's LibNSGIF, http://www.netsurf-browser.org/ + * Licensed under the MIT License, + * http://www.opensource.org/licenses/mit-license.php + * + * Copyright 2017 Michael Drake + */ + +#ifndef LZW_H_ +#define LZW_H_ + +/** + * \file + * \brief LZW decompression (interface) + * + * Decoder for GIF LZW data. + */ + + +/** LZW decoding response codes */ +typedef enum lzw_result { + LZW_OK, /**< Success */ + LZW_OK_EOD, /**< Success; reached zero-length sub-block */ + LZW_NO_DATA, /**< Error: Out of data */ +} lzw_result; + + +#endif -- cgit v1.2.3 From 960c3b6d2229dcc7cc4a4ef60838329b78880e66 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Mon, 3 Apr 2017 10:07:23 +0100 Subject: New LZW decoder: Add client calls to create/destroy LZW contexts. --- src/lzw.c | 28 ++++++++++++++++++++++++++++ src/lzw.h | 24 ++++++++++++++++++++++++ 2 files changed, 52 insertions(+) diff --git a/src/lzw.c b/src/lzw.c index 23c815e..4f7ff8f 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -41,6 +41,34 @@ struct lzw_read_ctx { uint32_t sb_bit_count; /**< Bit count in sub-block */ }; +/** + * LZW decompression context. + */ +struct lzw_ctx { + /** Input reading context */ + struct lzw_read_ctx input; +}; + + +/* Exported function, documented in lzw.h */ +lzw_result lzw_context_create(struct lzw_ctx **ctx) +{ + struct lzw_ctx *c = malloc(sizeof(*c)); + if (c == NULL) { + return LZW_NO_MEM; + } + + *ctx = c; + return LZW_OK; +} + + +/* Exported function, documented in lzw.h */ +void lzw_context_destroy(struct lzw_ctx *ctx) +{ + free(ctx); +} + /** * Advance the context to the next sub-block in the input data. diff --git a/src/lzw.h b/src/lzw.h index 0683ad0..a908414 100644 --- a/src/lzw.h +++ b/src/lzw.h @@ -17,12 +17,36 @@ */ +/* Declare lzw internal context structure */ +struct lzw_ctx; + + /** LZW decoding response codes */ typedef enum lzw_result { LZW_OK, /**< Success */ LZW_OK_EOD, /**< Success; reached zero-length sub-block */ + LZW_NO_MEM, /**< Error: Out of memory */ LZW_NO_DATA, /**< Error: Out of data */ } lzw_result; +/** + * Create an LZW decompression context. + * + * \param[out] ctx Returns an LZW decompression context. Caller owned, + * free with lzw_context_destroy(). + * \return LZW_OK on success, or appropriate error code otherwise. + */ +lzw_result lzw_context_create( + struct lzw_ctx **ctx); + +/** + * Destroy an LZW decompression context. + * + * \param[in] ctx The LZW decompression context to destroy. + */ +void lzw_context_destroy( + struct lzw_ctx *ctx); + + #endif -- cgit v1.2.3 From 86ebd63cc1e9570cf247da26635375e31fc57d40 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Mon, 3 Apr 2017 10:14:25 +0100 Subject: New LZW decoder: Add client calls to initialise LZW, and perform decode. --- src/lzw.c | 196 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lzw.h | 54 +++++++++++++++++ 2 files changed, 250 insertions(+) diff --git a/src/lzw.c b/src/lzw.c index 4f7ff8f..b161799 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -41,12 +41,46 @@ struct lzw_read_ctx { uint32_t sb_bit_count; /**< Bit count in sub-block */ }; +/** + * LZW dictionary entry. + * + * Records in the dictionary are composed of 1 or more entries. + * Entries point to previous entries which can be followed to compose + * the complete record. To compose the record in reverse order, take + * the `last_value` from each entry, and move to the previous entry. + * If the previous_entry's index is < the current clear_code, then it + * is the last entry in the record. + */ +struct lzw_dictionary_entry { + uint8_t last_value; /**< Last value for record ending at entry. */ + uint8_t first_value; /**< First value for entry's record. */ + uint16_t previous_entry; /**< Offset in dictionary to previous entry. */ +}; + /** * LZW decompression context. */ struct lzw_ctx { /** Input reading context */ struct lzw_read_ctx input; + + uint32_t previous_code; /**< Code read from input previously. */ + uint32_t previous_code_first; /**< First value of previous code. */ + + uint32_t initial_code_size; /**< Starting LZW code size. */ + uint32_t current_code_size; /**< Current LZW code size. */ + uint32_t current_code_size_max; /**< Max code value for current size. */ + + uint32_t clear_code; /**< Special Clear code value */ + uint32_t eoi_code; /**< Special End of Information code value */ + + uint32_t current_entry; /**< Next position in table to fill. */ + + /** Output value stack. */ + uint8_t stack_base[1 << LZW_CODE_MAX]; + + /** LZW decode dictionary. Generated during decode. */ + struct lzw_dictionary_entry table[1 << LZW_CODE_MAX]; }; @@ -175,3 +209,165 @@ static inline lzw_result lzw__next_code( *code_out = (code >> current_bit) & ((1 << code_size) - 1); return LZW_OK; } + + +/** + * Clear LZW code dictionary. + * + * \param[in] ctx LZW reading context, updated. + * \param[out] stack_pos_out Returns current stack position. + * \return LZW_OK or error code. + */ +static lzw_result lzw__clear_codes( + struct lzw_ctx *ctx, + const uint8_t ** const stack_pos_out) +{ + uint32_t code; + uint8_t *stack_pos; + + /* Reset dictionary building context */ + ctx->current_code_size = ctx->initial_code_size + 1; + ctx->current_code_size_max = (1 << ctx->current_code_size) - 1;; + ctx->current_entry = (1 << ctx->initial_code_size) + 2; + + /* There might be a sequence of clear codes, so process them all */ + do { + lzw_result res = lzw__next_code(&ctx->input, + ctx->current_code_size, &code); + if (res != LZW_OK) { + return res; + } + } while (code == ctx->clear_code); + + /* The initial code must be from the initial dictionary. */ + if (code > ctx->clear_code) { + return LZW_BAD_ICODE; + } + + /* Record this initial code as "previous" code, needed during decode. */ + ctx->previous_code = code; + ctx->previous_code_first = code; + + /* Reset the stack, and add first non-clear code added as first item. */ + stack_pos = ctx->stack_base; + *stack_pos++ = code; + + *stack_pos_out = stack_pos; + return LZW_OK; +} + + +/* Exported function, documented in lzw.h */ +lzw_result lzw_decode_init( + struct lzw_ctx *ctx, + const uint8_t *compressed_data, + uint32_t compressed_data_len, + uint32_t compressed_data_pos, + uint8_t code_size, + const uint8_t ** const stack_base_out, + const uint8_t ** const stack_pos_out) +{ + struct lzw_dictionary_entry *table = ctx->table; + + /* Initialise the input reading context */ + ctx->input.data = compressed_data; + ctx->input.data_len = compressed_data_len; + ctx->input.data_sb_next = compressed_data_pos; + + ctx->input.sb_bit = 0; + ctx->input.sb_bit_count = 0; + + /* Initialise the dictionary building context */ + ctx->initial_code_size = code_size; + + ctx->clear_code = (1 << code_size) + 0; + ctx->eoi_code = (1 << code_size) + 1; + + /* Initialise the standard dictionary entries */ + for (uint32_t i = 0; i < ctx->clear_code; ++i) { + table[i].first_value = i; + table[i].last_value = i; + } + + *stack_base_out = ctx->stack_base; + return lzw__clear_codes(ctx, stack_pos_out); +} + + +/* Exported function, documented in lzw.h */ +lzw_result lzw_decode(struct lzw_ctx *ctx, + const uint8_t ** const stack_pos_out) +{ + lzw_result res; + uint32_t code_new; + uint32_t code_out; + struct lzw_dictionary_entry *entry; + uint8_t *stack_pos = ctx->stack_base; + uint32_t clear_code = ctx->clear_code; + uint32_t current_entry = ctx->current_entry; + struct lzw_dictionary_entry * const table = ctx->table; + + /* Get a new code from the input */ + res = lzw__next_code(&ctx->input, ctx->current_code_size, &code_new); + if (res != LZW_OK) { + return res; + } + + if (code_new == clear_code) { + /* Got Clear code */ + return lzw__clear_codes(ctx, stack_pos_out); + + } else if (code_new == ctx->eoi_code) { + /* Got End of Information code */ + return LZW_EOI_CODE; + } + + if (current_entry >= (1 << LZW_CODE_MAX)) { + /* No space in table for new entries, only Clear and + * End of Information codes were allowed. */ + return LZW_BAD_DATA; + } + + entry = table + current_entry; + if (code_new > current_entry) { + /* Code is invalid */ + return LZW_BAD_CODE; + } else if (code_new < current_entry) { + /* Code is in table */ + code_out = code_new; + entry->last_value = table[code_new].first_value; + } else { + /* Code not in table */ + *stack_pos++ = ctx->previous_code_first; + code_out = ctx->previous_code; + entry->last_value = ctx->previous_code_first; + } + entry->first_value = ctx->previous_code_first; + entry->previous_entry = ctx->previous_code; + + /* Ensure code size is increased, if needed. */ + if (current_entry == ctx->current_code_size_max) { + if (ctx->current_code_size < LZW_CODE_MAX) { + ctx->current_code_size++; + ctx->current_code_size_max = + (1 << ctx->current_code_size) - 1; + } + } + ctx->current_entry++; + + ctx->previous_code_first = table[code_new].first_value; + ctx->previous_code = code_new; + + /* Put rest of data for this code on output stack. + * Note, in the case of "code not in table", the last entry of the + * current code has already been placed on the stack above. */ + while (code_out > clear_code) { + entry = table + code_out; + *stack_pos++ = entry->last_value; + code_out = entry->previous_entry; + } + *stack_pos++ = table[code_out].last_value; + + *stack_pos_out = stack_pos; + return LZW_OK; +} diff --git a/src/lzw.h b/src/lzw.h index a908414..5812c0d 100644 --- a/src/lzw.h +++ b/src/lzw.h @@ -17,6 +17,10 @@ */ +/** Maximum LZW code size in bits */ +#define LZW_CODE_MAX 12 + + /* Declare lzw internal context structure */ struct lzw_ctx; @@ -27,6 +31,10 @@ typedef enum lzw_result { LZW_OK_EOD, /**< Success; reached zero-length sub-block */ LZW_NO_MEM, /**< Error: Out of memory */ LZW_NO_DATA, /**< Error: Out of data */ + LZW_EOI_CODE, /**< Error: End of Information code */ + LZW_BAD_ICODE, /**< Error: Bad initial LZW code */ + LZW_BAD_CODE, /**< Error: Bad LZW code */ + LZW_BAD_DATA, /**< Error: Bad data */ } lzw_result; @@ -48,5 +56,51 @@ lzw_result lzw_context_create( void lzw_context_destroy( struct lzw_ctx *ctx); +/** + * Initialise an LZW decompression context for decoding. + * + * Caller owns neither `stack_base_out` or `stack_pos_out`. + * + * \param[in] ctx The LZW decompression context to initialise. + * \param[in] compressed_data The compressed data. + * \param[in] compressed_data_len Byte length of compressed data. + * \param[in] compressed_data_pos Start position in data. Must be position + * of a size byte at sub-block start. + * \param[in] code_size The initial LZW code size to use. + * \param[out] stack_base_out Returns base of decompressed data stack. + * \param[out] stack_pos_out Returns current stack position. + * There are `stack_pos_out - stack_base_out` + * current stack entries. + * \return LZW_OK on success, or appropriate error code otherwise. + */ +lzw_result lzw_decode_init( + struct lzw_ctx *ctx, + const uint8_t *compressed_data, + uint32_t compressed_data_len, + uint32_t compressed_data_pos, + uint8_t code_size, + const uint8_t ** const stack_base_out, + const uint8_t ** const stack_pos_out); + +/** + * Fill the LZW stack with decompressed data + * + * Ensure anything on the stack is used before calling this, as anything + * on the stack before this call will be trampled. + * + * Caller does not own `stack_pos_out`. + * + * \param[in] ctx LZW reading context, updated. + * \param[out] stack_pos_out Returns current stack position. + * Use with `stack_base_out` value from previous + * lzw_decode_init() call. + * There are `stack_pos_out - stack_base_out` + * current stack entries. + * \return LZW_OK on success, or appropriate error code otherwise. + */ +lzw_result lzw_decode( + struct lzw_ctx *ctx, + const uint8_t ** const stack_pos_out); + #endif -- cgit v1.2.3 From 34f3a9a81824dcda5a3e1944d14b0273298ec0c3 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Mon, 3 Apr 2017 10:23:18 +0100 Subject: GIF decoding: Remove old LZW decoder and port library to new implementation. --- include/libnsgif.h | 2 + src/Makefile | 2 +- src/libnsgif.c | 369 +++++++---------------------------------------------- 3 files changed, 47 insertions(+), 326 deletions(-) diff --git a/include/libnsgif.h b/include/libnsgif.h index fd92a0a..a819fec 100644 --- a/include/libnsgif.h +++ b/include/libnsgif.h @@ -93,6 +93,8 @@ typedef struct gif_bitmap_callback_vt { /** GIF animation data */ typedef struct gif_animation { + /** LZW decode context */ + void *lzw_ctx; /** callbacks for bitmap functions */ gif_bitmap_callback_vt bitmap_callbacks; /** pointer to GIF data */ diff --git a/src/Makefile b/src/Makefile index 0fa4dc6..cb5d31f 100644 --- a/src/Makefile +++ b/src/Makefile @@ -1,4 +1,4 @@ # Sources -DIR_SOURCES := libnsgif.c +DIR_SOURCES := libnsgif.c lzw.c include $(NSBUILD)/Makefile.subdir diff --git a/src/libnsgif.c b/src/libnsgif.c index 998f8d7..fffbd94 100644 --- a/src/libnsgif.c +++ b/src/libnsgif.c @@ -8,6 +8,7 @@ */ #include +#include #include #include #include @@ -15,6 +16,8 @@ #include "libnsgif.h" #include "utils/log.h" +#include "lzw.h" + /** * * \file @@ -36,9 +39,6 @@ /** Internal flag that a frame is invalid/unprocessed */ #define GIF_INVALID_FRAME -1 -/** Maximum LZW bits available */ -#define GIF_MAX_LZW 12 - /** Transparent colour */ #define GIF_TRANSPARENT_COLOUR 0x00 @@ -65,313 +65,6 @@ /** standard GIF header size */ #define GIF_STANDARD_HEADER_SIZE 13 -/** LZW parameters */ -struct lzw_s { - unsigned char buf[4]; - const unsigned char *direct; - int table[2][(1 << GIF_MAX_LZW)]; - unsigned char stack[(1 << GIF_MAX_LZW) * 2]; - unsigned char *stack_pointer; - - int code_size, set_code_size; - - int max_code, max_code_size; - - int clear_code, end_code; - - int curbit, lastbit, last_byte; - - int firstcode; - int oldcode; - - bool zero_data_block; - bool get_done; -}; - - -/* General LZW values. They are shared for all GIFs being decoded, and thus we - * can't handle progressive decoding efficiently without having the data for - * each image which would use an extra 10Kb or so per GIF. - */ -static struct lzw_s lzw_params = { - .zero_data_block = false, -}; - -static struct lzw_s *lzw = &lzw_params; - -/** - * get the next LZW code from the GIF - * - * reads codes from the input data stream coping with GIF data sub blocking - * - * \param[in] compressed_data LZW compressed data - * \param[in] compressed_data_len Byte size of compressed_data - * \param[in,out] compressed_data_pos Current position in compressed_data - * updated on exit. - * \param[in] code_size Number of bits in the current LZW code - * \return The next code to process or error return code - */ -static int gif_next_code( - const uint8_t *compressed_data, - uint32_t compressed_data_len, - uint32_t *compressed_data_pos, - int code_size) -{ - int i, j, end, count, ret; - uint32_t pos = *compressed_data_pos; - const unsigned char *b; - static const int maskTbl[16] = { - 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, - 0x00ff, 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff - }; - - end = lzw->curbit + code_size; - if (end >= lzw->lastbit) { - if (lzw->get_done) { - return GIF_END_OF_FRAME; - } - lzw->buf[0] = lzw->direct[lzw->last_byte - 2]; - lzw->buf[1] = lzw->direct[lzw->last_byte - 1]; - - /* get the next block */ - lzw->direct = compressed_data + pos; - if (pos >= compressed_data_len) { - return GIF_INSUFFICIENT_FRAME_DATA; - } - - count = lzw->direct[0]; - lzw->zero_data_block = (count == 0); - if ((pos + count) >= compressed_data_len) { - return GIF_INSUFFICIENT_FRAME_DATA; - } - - if (count == 0) { - lzw->get_done = true; - } else { - if (pos + 3 >= compressed_data_len) { - return GIF_INSUFFICIENT_FRAME_DATA; - } - lzw->direct -= 1; - lzw->buf[2] = lzw->direct[2]; - lzw->buf[3] = lzw->direct[3]; - } - pos += count + 1; - - /* update our variables */ - lzw->last_byte = 2 + count; - lzw->curbit = (lzw->curbit - lzw->lastbit) + 16; - lzw->lastbit = (2 + count) << 3; - end = lzw->curbit + code_size; - } - - i = lzw->curbit >> 3; - if (i < 2) { - b = lzw->buf; - } else { - b = lzw->direct; - } - - ret = b[i]; - j = (end >> 3) - 1; - if (i <= j) { - ret |= (b[i + 1] << 8); - if (i < j) { - ret |= (b[i + 2] << 16); - } - } - ret = (ret >> (lzw->curbit % 8)) & maskTbl[code_size]; - lzw->curbit += code_size; - - *compressed_data_pos = pos; - return ret; -} - - -/** - * Clear LZW code dictionary - * - * \param[in] compressed_data LZW compressed data - * \param[in] compressed_data_len Byte size of compressed_data - * \param[in,out] compressed_data_pos Current position in compressed_data - * updated on exit. - * \return GIF_OK or error code. - */ -static gif_result gif_clear_codes_LZW( - const uint8_t *compressed_data, - uint32_t compressed_data_len, - uint32_t *compressed_data_pos) -{ - int i; - int code; - - if (lzw->clear_code >= (1 << GIF_MAX_LZW)) { - lzw->stack_pointer = lzw->stack; - return GIF_FRAME_DATA_ERROR; - } - - /* initialise our table */ - memset(lzw->table, 0x00, (1 << GIF_MAX_LZW) * 8); - for (i = 0; i < lzw->clear_code; ++i) { - lzw->table[1][i] = i; - } - - /* reset LZW parameters */ - lzw->code_size = lzw->set_code_size + 1; - lzw->max_code_size = lzw->clear_code << 1; - lzw->max_code = lzw->clear_code + 2; - lzw->stack_pointer = lzw->stack; - - /* process repeated clear codes */ - do { - code = gif_next_code(compressed_data, compressed_data_len, - compressed_data_pos, lzw->code_size); - if (code < 0) { - return code; - } - } while (code == lzw->clear_code); - lzw->firstcode = lzw->oldcode = code; - - *lzw->stack_pointer++ = lzw->firstcode; - - return GIF_OK; -} - - -/** - * Initialise LZW - * - * This initialises a LZW context ready to commence decompression. - * - * \param[in] compressed_data LZW compressed data - * \param[in] compressed_data_len Byte size of compressed_data - * \param[in,out] compressed_data_pos Current position in compressed_data - * updated on exit. - * \param[in] initial_code_size Size of codes used on clearing of code dictionary - */ -static gif_result gif_initialise_LZW( - const uint8_t *compressed_data, - uint32_t compressed_data_len, - uint32_t *compressed_data_pos, - int initial_code_size) -{ - lzw->set_code_size = initial_code_size; - lzw->code_size = lzw->set_code_size + 1; - lzw->clear_code = (1 << lzw->set_code_size); - lzw->end_code = lzw->clear_code + 1; - lzw->max_code_size = lzw->clear_code << 1; - lzw->max_code = lzw->clear_code + 2; - lzw->curbit = lzw->lastbit = 0; - lzw->last_byte = 2; - lzw->get_done = false; - lzw->direct = lzw->buf; - - return gif_clear_codes_LZW(compressed_data, - compressed_data_len, - compressed_data_pos); -} - -/** - * fill the LZW stack with decompressed data - * - * \param[in] compressed_data LZW compressed data - * \param[in] compressed_data_len Byte size of compressed_data - * \param[in,out] compressed_data_pos Current position in compressed_data - * updated on exit. - * \return true on sucessful decode of the next LZW code else false. - */ -static gif_result gif_next_LZW( - const uint8_t *compressed_data, - uint32_t compressed_data_len, - uint32_t *compressed_data_pos) -{ - int code, incode; - int block_size; - int new_code; - - code = gif_next_code(compressed_data, compressed_data_len, - compressed_data_pos, lzw->code_size); - if (code < 0) { - return code; - } - - if (code == lzw->clear_code) { - return gif_clear_codes_LZW(compressed_data, - compressed_data_len, - compressed_data_pos); - } - - if (code == lzw->end_code) { - /* skip to the end of our data so multi-image GIFs work */ - if (lzw->zero_data_block) { - return GIF_FRAME_DATA_ERROR; - } - block_size = 0; - while (block_size != 1 && - *compressed_data_pos < compressed_data_len) { - block_size = compressed_data[*compressed_data_pos] + 1; - *compressed_data_pos += block_size; - } - return GIF_FRAME_DATA_ERROR; - } - - incode = code; - if (code >= lzw->max_code) { - if (lzw->stack_pointer >= lzw->stack + ((1 << GIF_MAX_LZW) * 2)) { - return GIF_FRAME_DATA_ERROR; - } - *lzw->stack_pointer++ = lzw->firstcode; - code = lzw->oldcode; - } - - /* The following loop is the most important in the GIF decoding cycle - * as every single pixel passes through it. - * - * Note: our stack is always big enough to hold a complete decompressed - * chunk. - */ - while (code >= lzw->clear_code) { - if (lzw->stack_pointer >= lzw->stack + ((1 << GIF_MAX_LZW) * 2) || - code >= (1 << GIF_MAX_LZW)) { - return GIF_FRAME_DATA_ERROR; - } - *lzw->stack_pointer++ = lzw->table[1][code]; - new_code = lzw->table[0][code]; - if (new_code < lzw->clear_code) { - code = new_code; - break; - } - - if (lzw->stack_pointer >= lzw->stack + ((1 << GIF_MAX_LZW) * 2) || - new_code >= (1 << GIF_MAX_LZW)) { - return GIF_FRAME_DATA_ERROR; - } - *lzw->stack_pointer++ = lzw->table[1][new_code]; - code = lzw->table[0][new_code]; - if (code == new_code) { - return GIF_FRAME_DATA_ERROR; - } - } - - if (lzw->stack_pointer >= lzw->stack + ((1 << GIF_MAX_LZW) * 2)) { - return GIF_FRAME_DATA_ERROR; - } - *lzw->stack_pointer++ = lzw->firstcode = lzw->table[1][code]; - - code = lzw->max_code; - if (code < (1 << GIF_MAX_LZW)) { - lzw->table[0][code] = lzw->oldcode; - lzw->table[1][code] = lzw->firstcode; - ++lzw->max_code; - if ((lzw->max_code >= lzw->max_code_size) && - (lzw->max_code_size < (1 << GIF_MAX_LZW))) { - lzw->max_code_size = lzw->max_code_size << 1; - ++lzw->code_size; - } - } - lzw->oldcode = incode; - return GIF_OK; -} - /** * Updates the sprite memory size @@ -725,7 +418,7 @@ static gif_result gif_initialise_frame(gif_animation *gif) if (gif_bytes < 1) { return GIF_INSUFFICIENT_FRAME_DATA; } - if (gif_data[0] > GIF_MAX_LZW) { + if (gif_data[0] > LZW_CODE_MAX) { return GIF_DATA_ERROR; } @@ -863,7 +556,20 @@ static unsigned int gif_interlaced_line(int height, int y) { } - +static gif_result gif_error_from_lzw(lzw_result l_res) +{ + static const gif_result g_res[] = { + [LZW_OK] = GIF_OK, + [LZW_OK_EOD] = GIF_END_OF_FRAME, + [LZW_NO_MEM] = GIF_INSUFFICIENT_MEMORY, + [LZW_NO_DATA] = GIF_INSUFFICIENT_FRAME_DATA, + [LZW_EOI_CODE] = GIF_FRAME_DATA_ERROR, + [LZW_BAD_ICODE] = GIF_FRAME_DATA_ERROR, + [LZW_BAD_CODE] = GIF_FRAME_DATA_ERROR, + [LZW_BAD_DATA] = GIF_FRAME_DATA_ERROR, + }; + return g_res[l_res]; +} /** @@ -878,7 +584,6 @@ gif_internal_decode_frame(gif_animation *gif, unsigned int frame, bool clear_image) { - gif_result res; unsigned int index = 0; unsigned char *gif_data, *gif_end; int gif_bytes; @@ -1038,6 +743,10 @@ gif_internal_decode_frame(gif_animation *gif, /* If we are clearing the image we just clear, if not decode */ if (!clear_image) { + lzw_result res; + const uint8_t *stack_base; + const uint8_t *stack_pos; + /* Ensure we have enough data for a 1-byte LZW code size + * 1-byte gif trailer */ @@ -1114,10 +823,11 @@ gif_internal_decode_frame(gif_animation *gif, gif->buffer_position = (gif_data - gif->gif_data) + 1; /* Initialise the LZW decoding */ - res = gif_initialise_LZW(gif->gif_data, gif->buffer_size, - &gif->buffer_position, gif_data[0]); - if (res != GIF_OK) { - return res; + res = lzw_decode_init(gif->lzw_ctx, gif->gif_data, + gif->buffer_size, gif->buffer_position, + gif_data[0], &stack_base, &stack_pos); + if (res != LZW_OK) { + return gif_error_from_lzw(res); } /* Decompress the data */ @@ -1135,14 +845,14 @@ gif_internal_decode_frame(gif_animation *gif, */ x = width; while (x > 0) { - burst_bytes = (lzw->stack_pointer - lzw->stack); + burst_bytes = (stack_pos - stack_base); if (burst_bytes > 0) { if (burst_bytes > x) { burst_bytes = x; } x -= burst_bytes; while (burst_bytes-- > 0) { - colour = *--lzw->stack_pointer; + colour = *--stack_pos; if (((gif->frames[frame].transparency) && (colour != gif->frames[frame].transparency_index)) || (!gif->frames[frame].transparency)) { @@ -1151,15 +861,13 @@ gif_internal_decode_frame(gif_animation *gif, frame_scanline++; } } else { - res = gif_next_LZW(gif->gif_data, - gif->buffer_size, - &gif->buffer_position); - if (res != GIF_OK) { + res = lzw_decode(gif->lzw_ctx, &stack_pos); + if (res != LZW_OK) { /* Unexpected end of frame, try to recover */ - if (res == GIF_END_OF_FRAME) { + if (res == LZW_OK_EOD) { return_value = GIF_OK; } else { - return_value = res; + return_value = gif_error_from_lzw(res); } goto gif_decode_frame_exit; } @@ -1230,6 +938,14 @@ gif_result gif_initialise(gif_animation *gif, size_t size, unsigned char *data) gif->buffer_size = size; gif->gif_data = data; + if (gif->lzw_ctx == NULL) { + lzw_result res = lzw_context_create( + (struct lzw_ctx **)&gif->lzw_ctx); + if (res != LZW_OK) { + return gif_error_from_lzw(res); + } + } + /* Check for sufficient data to be a GIF (6-byte header + 7-byte * logical screen descriptor) */ @@ -1448,4 +1164,7 @@ void gif_finalise(gif_animation *gif) gif->local_colour_table = NULL; free(gif->global_colour_table); gif->global_colour_table = NULL; + + lzw_context_destroy(gif->lzw_ctx); + gif->lzw_ctx = NULL; } -- cgit v1.2.3 From f9797e4ae82090808036b1e1ec4318d0f1bdc456 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Tue, 4 Apr 2017 13:53:51 +0100 Subject: New LZW decoder: Real-world fix; continue after dictionary is full. --- src/libnsgif.c | 1 - src/lzw.c | 27 +++++++++++++-------------- src/lzw.h | 1 - 3 files changed, 13 insertions(+), 16 deletions(-) diff --git a/src/libnsgif.c b/src/libnsgif.c index fffbd94..6bf9956 100644 --- a/src/libnsgif.c +++ b/src/libnsgif.c @@ -566,7 +566,6 @@ static gif_result gif_error_from_lzw(lzw_result l_res) [LZW_EOI_CODE] = GIF_FRAME_DATA_ERROR, [LZW_BAD_ICODE] = GIF_FRAME_DATA_ERROR, [LZW_BAD_CODE] = GIF_FRAME_DATA_ERROR, - [LZW_BAD_DATA] = GIF_FRAME_DATA_ERROR, }; return g_res[l_res]; } diff --git a/src/lzw.c b/src/lzw.c index b161799..6b7156e 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -301,7 +301,7 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, lzw_result res; uint32_t code_new; uint32_t code_out; - struct lzw_dictionary_entry *entry; + uint8_t last_value; uint8_t *stack_pos = ctx->stack_base; uint32_t clear_code = ctx->clear_code; uint32_t current_entry = ctx->current_entry; @@ -322,28 +322,28 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, return LZW_EOI_CODE; } - if (current_entry >= (1 << LZW_CODE_MAX)) { - /* No space in table for new entries, only Clear and - * End of Information codes were allowed. */ - return LZW_BAD_DATA; - } - - entry = table + current_entry; if (code_new > current_entry) { /* Code is invalid */ return LZW_BAD_CODE; } else if (code_new < current_entry) { /* Code is in table */ code_out = code_new; - entry->last_value = table[code_new].first_value; + last_value = table[code_new].first_value; } else { /* Code not in table */ *stack_pos++ = ctx->previous_code_first; code_out = ctx->previous_code; - entry->last_value = ctx->previous_code_first; + last_value = ctx->previous_code_first; + } + + /* Add to the dictionary, only if there's space */ + if (current_entry < (1 << LZW_CODE_MAX)) { + struct lzw_dictionary_entry *entry = table + current_entry; + entry->last_value = last_value; + entry->first_value = ctx->previous_code_first; + entry->previous_entry = ctx->previous_code; + ctx->current_entry++; } - entry->first_value = ctx->previous_code_first; - entry->previous_entry = ctx->previous_code; /* Ensure code size is increased, if needed. */ if (current_entry == ctx->current_code_size_max) { @@ -353,7 +353,6 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, (1 << ctx->current_code_size) - 1; } } - ctx->current_entry++; ctx->previous_code_first = table[code_new].first_value; ctx->previous_code = code_new; @@ -362,7 +361,7 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, * Note, in the case of "code not in table", the last entry of the * current code has already been placed on the stack above. */ while (code_out > clear_code) { - entry = table + code_out; + struct lzw_dictionary_entry *entry = table + code_out; *stack_pos++ = entry->last_value; code_out = entry->previous_entry; } diff --git a/src/lzw.h b/src/lzw.h index 5812c0d..385b425 100644 --- a/src/lzw.h +++ b/src/lzw.h @@ -34,7 +34,6 @@ typedef enum lzw_result { LZW_EOI_CODE, /**< Error: End of Information code */ LZW_BAD_ICODE, /**< Error: Bad initial LZW code */ LZW_BAD_CODE, /**< Error: Bad LZW code */ - LZW_BAD_DATA, /**< Error: Bad data */ } lzw_result; -- cgit v1.2.3