From 58c6e9393a794556bc3a192ce8227400d275d4e0 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Fri, 24 Sep 2021 19:42:42 +0100 Subject: lzw: Rework API for separate init for map/non-map decode functions. --- src/libnsgif.c | 26 +++--- src/lzw.c | 252 ++++++++++++++++++++++++++++++++------------------------- src/lzw.h | 94 ++++++++++++--------- 3 files changed, 214 insertions(+), 158 deletions(-) diff --git a/src/libnsgif.c b/src/libnsgif.c index 5fa9cb6..24dbf7d 100644 --- a/src/libnsgif.c +++ b/src/libnsgif.c @@ -554,6 +554,8 @@ static gif_result gif_error_from_lzw(lzw_result l_res) [LZW_BAD_ICODE] = GIF_FRAME_DATA_ERROR, [LZW_BAD_CODE] = GIF_FRAME_DATA_ERROR, }; + assert(l_res != LZW_BAD_PARAM); + assert(l_res != LZW_NO_COLOUR); return g_res[l_res]; } @@ -643,9 +645,8 @@ gif__decode_complex(gif_animation *gif, lzw_result res; /* Initialise the LZW decoding */ - res = lzw_decode_init(gif->lzw_ctx, gif->gif_data, - gif->buffer_size, gif->buffer_position, - minimum_code_size); + res = lzw_decode_init(gif->lzw_ctx, minimum_code_size, + gif->gif_data, gif->buffer_size, gif->buffer_position); if (res != LZW_OK) { return gif_error_from_lzw(res); } @@ -680,7 +681,7 @@ gif__decode_complex(gif_animation *gif, } break; } - res = lzw_decode_continuous(gif->lzw_ctx, + res = lzw_decode(gif->lzw_ctx, &uncompressed, &available); } @@ -715,23 +716,22 @@ gif__decode_simple(gif_animation *gif, gif_result ret = GIF_OK; lzw_result res; + transparency_index = gif->frames[frame].transparency ? + gif->frames[frame].transparency_index : + GIF_NO_TRANSPARENCY; + /* Initialise the LZW decoding */ - res = lzw_decode_init(gif->lzw_ctx, gif->gif_data, - gif->buffer_size, gif->buffer_position, - minimum_code_size); + res = lzw_decode_init_map(gif->lzw_ctx, + minimum_code_size, transparency_index, colour_table, + gif->gif_data, gif->buffer_size, gif->buffer_position); if (res != LZW_OK) { return gif_error_from_lzw(res); } - transparency_index = gif->frames[frame].transparency ? - gif->frames[frame].transparency_index : - GIF_NO_TRANSPARENCY; - frame_data += (offset_y * gif->width); while (pixels > 0) { - res = lzw_decode_map_continuous(gif->lzw_ctx, - transparency_index, colour_table, + res = lzw_decode_map(gif->lzw_ctx, frame_data, pixels, &written); pixels -= written; frame_data += written; diff --git a/src/lzw.c b/src/lzw.c index a243ddb..babe485 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -68,31 +68,32 @@ struct lzw_table_entry { struct lzw_ctx { struct lzw_read_ctx input; /**< Input reading context */ - uint32_t prev_code; /**< Code read from input previously. */ - uint32_t prev_code_first; /**< First value of previous code. */ - uint32_t prev_code_count; /**< Total values for previous code. */ + uint16_t prev_code; /**< Code read from input previously. */ + uint16_t prev_code_first; /**< First value of previous code. */ + uint16_t prev_code_count; /**< Total values for previous code. */ - uint32_t initial_code_size; /**< Starting LZW code size. */ + uint8_t initial_code_size; /**< Starting LZW code size. */ - uint32_t code_size; /**< Current LZW code size. */ - uint32_t code_max; /**< Max code value for current code size. */ + uint8_t code_size; /**< Current LZW code size. */ + uint16_t code_max; /**< Max code value for current code size. */ - uint32_t clear_code; /**< Special Clear code value */ - uint32_t eoi_code; /**< Special End of Information code value */ + uint16_t clear_code; /**< Special Clear code value */ + uint16_t eoi_code; /**< Special End of Information code value */ - uint32_t table_size; /**< Next position in table to fill. */ + uint16_t table_size; /**< Next position in table to fill. */ - uint32_t output_code; /**< Code that has been partially output. */ - uint32_t output_left; /**< Number of values left for output_code. */ + uint16_t output_code; /**< Code that has been partially output. */ + uint16_t output_left; /**< Number of values left for output_code. */ - uint32_t transparency_idx; /**< Index representing transparency. */ - uint32_t *restrict colour_map; /**< Index to pixel colour mapping */ - - /** Output value stack. */ - uint8_t stack_base[LZW_TABLE_ENTRY_MAX]; + bool has_transparency; /**< Whether the image is opaque. */ + uint8_t transparency_idx; /**< Index representing transparency. */ + const uint32_t *restrict colour_map; /**< Index to colour mapping. */ /** LZW code table. Generated during decode. */ struct lzw_table_entry table[LZW_TABLE_ENTRY_MAX]; + + /** Output value stack. */ + uint8_t stack_base[LZW_TABLE_ENTRY_MAX]; }; @@ -165,8 +166,8 @@ static lzw_result lzw__block_advance(struct lzw_read_ctx *restrict ctx) */ static inline lzw_result lzw__read_code( struct lzw_read_ctx *restrict ctx, - uint32_t code_size, - uint32_t *restrict code_out) + uint16_t code_size, + uint16_t *restrict code_out) { uint32_t code = 0; uint32_t current_bit = ctx->sb_bit & 0x7; @@ -232,9 +233,9 @@ static inline lzw_result lzw__read_code( */ static inline lzw_result lzw__handle_clear( struct lzw_ctx *ctx, - uint32_t *code_out) + uint16_t *code_out) { - uint32_t code; + uint16_t code; /* Reset table building context */ ctx->code_size = ctx->initial_code_size; @@ -259,27 +260,26 @@ static inline lzw_result lzw__handle_clear( 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 minimum_code_size) + uint8_t minimum_code_size, + const uint8_t *input_data, + uint32_t input_length, + uint32_t input_pos) { struct lzw_table_entry *table = ctx->table; lzw_result res; - uint32_t code; + uint16_t code; if (minimum_code_size >= LZW_CODE_MAX) { return LZW_BAD_ICODE; } /* 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.data = input_data; + ctx->input.data_len = input_length; + ctx->input.data_sb_next = input_pos; ctx->input.sb_bit = 0; ctx->input.sb_bit_count = 0; @@ -293,7 +293,7 @@ lzw_result lzw_decode_init( ctx->output_left = 0; /* Initialise the standard table entries */ - for (uint32_t i = 0; i < ctx->clear_code; ++i) { + for (uint16_t i = 0; i < ctx->clear_code; i++) { table[i].first = i; table[i].value = i; table[i].count = 1; @@ -313,6 +313,39 @@ lzw_result lzw_decode_init( ctx->output_code = code; ctx->output_left = 1; + ctx->has_transparency = false; + ctx->transparency_idx = 0; + ctx->colour_map = NULL; + + return LZW_OK; +} + +/* Exported function, documented in lzw.h */ +lzw_result lzw_decode_init_map( + struct lzw_ctx *ctx, + uint8_t minimum_code_size, + uint32_t transparency_idx, + const uint32_t *colour_table, + const uint8_t *input_data, + uint32_t input_length, + uint32_t input_pos) +{ + lzw_result res; + + if (colour_table == NULL) { + return LZW_BAD_PARAM; + } + + res = lzw_decode_init(ctx, minimum_code_size, + input_data, input_length, input_pos); + if (res != LZW_OK) { + return res; + } + + ctx->has_transparency = (transparency_idx <= 0xFF); + ctx->transparency_idx = transparency_idx; + ctx->colour_map = colour_table; + return LZW_OK; } @@ -324,7 +357,7 @@ lzw_result lzw_decode_init( */ static inline void lzw__table_add_entry( struct lzw_ctx *ctx, - uint32_t code) + uint16_t code) { struct lzw_table_entry *entry = &ctx->table[ctx->table_size]; @@ -338,30 +371,31 @@ static inline void lzw__table_add_entry( typedef uint32_t (*lzw_writer_fn)( struct lzw_ctx *ctx, - void *restrict output, - uint32_t length, - uint32_t used, - uint32_t code, - uint32_t left); + void *restrict output_data, + uint32_t output_length, + uint32_t output_pos, + uint16_t code, + uint16_t left); /** * Get the next LZW code and write its value(s) to output buffer. * - * \param[in] ctx LZW reading context, updated. - * \param[in] output Array to write output values into. - * \param[in] length Size of output array. - * \param[in] write_pixels Function for writing pixels to output. - * \param[in,out] used Number of values written. Updated on exit. + * \param[in] ctx LZW reading context, updated. + * \param[in] write_fn Function for writing pixels to output. + * \param[in] output_data Array to write output values into. + * \param[in] output_length Size of output array. + * \param[in,out] output_written Number of values written. Updated on exit. * \return LZW_OK on success, or appropriate error code otherwise. */ -static inline lzw_result lzw__decode(struct lzw_ctx *ctx, - void *restrict output, - uint32_t length, - lzw_writer_fn write_pixels, - uint32_t *restrict used) +static inline lzw_result lzw__decode( + struct lzw_ctx *ctx, + lzw_writer_fn write_fn, + void *restrict output_data, + uint32_t output_length, + uint32_t *restrict output_written) { lzw_result res; - uint32_t code; + uint16_t code; /* Get a new code from the input */ res = lzw__read_code(&ctx->input, ctx->code_size, &code); @@ -385,7 +419,7 @@ static inline lzw_result lzw__decode(struct lzw_ctx *ctx, } } else if (ctx->table_size < LZW_TABLE_ENTRY_MAX) { - uint32_t size = ctx->table_size; + uint16_t size = ctx->table_size; lzw__table_add_entry(ctx, (code < size) ? ctx->table[code].first : ctx->prev_code_first); @@ -397,8 +431,9 @@ static inline lzw_result lzw__decode(struct lzw_ctx *ctx, } } - *used += write_pixels(ctx, output, length, *used, code, - ctx->table[code].count); + *output_written += write_fn(ctx, + output_data, output_length, *output_written, + code, ctx->table[code].count); /* Store details of this code as "previous code" to the context. */ ctx->prev_code_first = ctx->table[code].first; @@ -416,25 +451,25 @@ static inline lzw_result lzw__decode(struct lzw_ctx *ctx, * this call, then there is more data for this code left to output. The code * is stored to the context as `ctx->output_code`. * - * \param[in] ctx LZW reading context, updated. - * \param[in] output Array to write output values into. - * \param[in] length Size of output array. - * \param[in] used Current position in output array. - * \param[in] code LZW code to output values for. - * \param[in] left Number of values remaining to output for this value. + * \param[in] ctx LZW reading context, updated. + * \param[in] output_data Array to write output values into. + * \param[in] output_length length Size of output array. + * \param[in] output_used Current position in output array. + * \param[in] code LZW code to output values for. + * \param[in] left Number of values remaining to output for this code. * \return Number of pixel values written. */ -static inline uint32_t lzw__write_pixels(struct lzw_ctx *ctx, - void *restrict output, - uint32_t length, - uint32_t used, - uint32_t code, - uint32_t left) +static inline uint32_t lzw__write_fn(struct lzw_ctx *ctx, + void *restrict output_data, + uint32_t output_length, + uint32_t output_used, + uint16_t code, + uint16_t left) { - uint8_t *restrict output_pos = (uint8_t *)output + used; + uint8_t *restrict output_pos = (uint8_t *)output_data + output_used; const struct lzw_table_entry * const table = ctx->table; - uint32_t space = length - used; - uint32_t count = left; + uint32_t space = output_length - output_used; + uint16_t count = left; if (count > space) { left = count - space; @@ -463,23 +498,24 @@ static inline uint32_t lzw__write_pixels(struct lzw_ctx *ctx, } /* Exported function, documented in lzw.h */ -lzw_result lzw_decode_continuous(struct lzw_ctx *ctx, - const uint8_t *restrict *const restrict data, - uint32_t *restrict used) +lzw_result lzw_decode(struct lzw_ctx *ctx, + const uint8_t *restrict *const restrict output_data, + uint32_t *restrict output_written) { - *used = 0; - *data = ctx->stack_base; + const uint32_t output_length = sizeof(ctx->stack_base); + + *output_written = 0; + *output_data = ctx->stack_base; if (ctx->output_left != 0) { - *used += lzw__write_pixels(ctx, - ctx->stack_base, sizeof(ctx->stack_base), *used, + *output_written += lzw__write_fn(ctx, + ctx->stack_base, output_length, *output_written, ctx->output_code, ctx->output_left); } - while (*used != sizeof(ctx->stack_base)) { - lzw_result res = lzw__decode(ctx, - ctx->stack_base, sizeof(ctx->stack_base), - lzw__write_pixels, used); + while (*output_written != output_length) { + lzw_result res = lzw__decode(ctx, lzw__write_fn, + ctx->stack_base, output_length, output_written); if (res != LZW_OK) { return res; } @@ -489,32 +525,32 @@ lzw_result lzw_decode_continuous(struct lzw_ctx *ctx, } /** - * Write colour mapped values for this code to the output stack. + * Write colour mapped values for this code to the output. * * If there isn't enough space in the output stack, this function will write * the as many as it can into the output. If `ctx->output_left > 0` after * this call, then there is more data for this code left to output. The code * is stored to the context as `ctx->output_code`. * - * \param[in] ctx LZW reading context, updated. - * \param[in] output Array to write output values into. - * \param[in] length Size of output array. - * \param[in] used Current position in output array. - * \param[in] code LZW code to output values for. - * \param[in] left Number of values remaining to output for this value. + * \param[in] ctx LZW reading context, updated. + * \param[in] output_data Array to write output values into. + * \param[in] output_length Size of output array. + * \param[in] output_used Current position in output array. + * \param[in] code LZW code to output values for. + * \param[in] left Number of values remaining to output for code. * \return Number of pixel values written. */ -static inline uint32_t lzw__write_pixels_map(struct lzw_ctx *ctx, - void *restrict buffer, - uint32_t length, - uint32_t used, - uint32_t code, - uint32_t left) +static inline uint32_t lzw__map_write_fn(struct lzw_ctx *ctx, + void *restrict output_data, + uint32_t output_length, + uint32_t output_used, + uint16_t code, + uint16_t left) { - uint32_t *restrict stack_pos = (uint32_t *)buffer + used; + uint32_t *restrict output_pos = (uint32_t *)output_data + output_used; const struct lzw_table_entry * const table = ctx->table; - uint32_t space = length - used; - uint32_t count = left; + uint32_t space = output_length - output_used; + uint16_t count = left; if (count > space) { left = count - space; @@ -531,12 +567,12 @@ static inline uint32_t lzw__write_pixels_map(struct lzw_ctx *ctx, code = entry->extends; } - stack_pos += count; + output_pos += count; for (unsigned i = count; i != 0; i--) { const struct lzw_table_entry *entry = table + code; - --stack_pos; + --output_pos; if (entry->value != ctx->transparency_idx) { - *stack_pos = ctx->colour_map[entry->value]; + *output_pos = ctx->colour_map[entry->value]; } code = entry->extends; } @@ -545,26 +581,26 @@ static inline uint32_t lzw__write_pixels_map(struct lzw_ctx *ctx, } /* Exported function, documented in lzw.h */ -lzw_result lzw_decode_map_continuous(struct lzw_ctx *ctx, - uint32_t transparency_idx, - uint32_t *restrict colour_map, - uint32_t *restrict data, - uint32_t length, - uint32_t *restrict used) +lzw_result lzw_decode_map(struct lzw_ctx *ctx, + uint32_t *restrict output_data, + uint32_t output_length, + uint32_t *restrict output_written) { - *used = 0; + *output_written = 0; - ctx->transparency_idx = transparency_idx; - ctx->colour_map = colour_map; + if (ctx->colour_map == NULL) { + return LZW_NO_COLOUR; + } if (ctx->output_left != 0) { - *used += lzw__write_pixels_map(ctx, data, length, *used, + *output_written += lzw__map_write_fn(ctx, + output_data, output_length, *output_written, ctx->output_code, ctx->output_left); } - while (*used != length) { - lzw_result res = lzw__decode(ctx, data, length, - lzw__write_pixels_map, used); + while (*output_written != output_length) { + lzw_result res = lzw__decode(ctx, lzw__map_write_fn, + output_data, output_length, output_written); if (res != LZW_OK) { return res; } diff --git a/src/lzw.h b/src/lzw.h index a227163..4549c60 100644 --- a/src/lzw.h +++ b/src/lzw.h @@ -16,7 +16,6 @@ * Decoder for GIF LZW data. */ - /** Maximum LZW code size in bits */ #define LZW_CODE_MAX 12 @@ -32,7 +31,9 @@ typedef enum lzw_result { LZW_NO_MEM, /**< Error: Out of memory */ LZW_NO_DATA, /**< Error: Out of data */ LZW_EOI_CODE, /**< Error: End of Information code */ + LZW_NO_COLOUR, /**< Error: No colour map provided. */ LZW_BAD_ICODE, /**< Error: Bad initial LZW code */ + LZW_BAD_PARAM, /**< Error: Bad function parameter. */ LZW_BAD_CODE, /**< Error: Bad LZW code */ } lzw_result; @@ -58,62 +59,81 @@ void lzw_context_destroy( /** * 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] minimum_code_size The LZW Minimum Code Size. - * \param[out] stack_base_out Returns base of decompressed data stack. + * \param[in] ctx The LZW decompression context to initialise. + * \param[in] minimum_code_size The LZW Minimum Code Size. + * \param[in] input_data The compressed data. + * \param[in] input_length Byte length of compressed data. + * \param[in] input_pos Start position in data. Must be position + * of a size byte at sub-block start. * \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 minimum_code_size); + uint8_t minimum_code_size, + const uint8_t *input_data, + uint32_t input_length, + uint32_t input_pos); /** - * Read input codes until end of lzw context owned output buffer. + * Read input codes until end of LZW context owned output buffer. * * Ensure anything in output is used before calling this, as anything - * on the there before this call will be trampled. + * there before this call will be trampled. * - * \param[in] ctx LZW reading context, updated. - * \param[out] data Returns pointer to array of output values. - * \param[out] used Returns the number of values written to data. + * \param[in] ctx LZW reading context, updated. + * \param[out] output_data Returns pointer to array of output values. + * \param[out] output_written Returns the number of values written to data. * \return LZW_OK on success, or appropriate error code otherwise. */ -lzw_result lzw_decode_continuous(struct lzw_ctx *ctx, - const uint8_t *restrict *const restrict data, - uint32_t *restrict used); +lzw_result lzw_decode(struct lzw_ctx *ctx, + const uint8_t *restrict *const restrict output_data, + uint32_t *restrict output_written); /** - * Read LZW codes into client buffer, mapping output to colours. - * - * Ensure anything in output is used before calling this, as anything - * on the there before this call will be trampled. + * Initialise an LZW decompression context for decoding to colour map values. * * For transparency to work correctly, the given client buffer must have * the values from the previous frame. The transparency_idx should be a value * of 256 or above, if the frame does not have transparency. * - * \param[in] ctx LZW reading context, updated. - * \param[in] transparency_idx Index representing transparency. - * \param[in] colour_map Index to pixel colour mapping - * \param[in] data Client buffer to fill with colour mapped values. - * \param[in] length Size of output array. - * \param[out] used Returns the number of values written to data. + * \param[in] ctx The LZW decompression context to initialise. + * \param[in] minimum_code_size The LZW Minimum Code Size. + * \param[in] transparency_idx Index representing transparency. + * \param[in] colour_table Index to pixel colour mapping. + * \param[in] input_data The compressed data. + * \param[in] input_length Byte length of compressed data. + * \param[in] input_pos Start position in data. Must be position + * of a size byte at sub-block start. * \return LZW_OK on success, or appropriate error code otherwise. */ -lzw_result lzw_decode_map_continuous(struct lzw_ctx *ctx, +lzw_result lzw_decode_init_map( + struct lzw_ctx *ctx, + uint8_t minimum_code_size, uint32_t transparency_idx, - uint32_t *restrict colour_table, - uint32_t *restrict data, - uint32_t length, - uint32_t *restrict used); + const uint32_t *colour_table, + const uint8_t *input_data, + uint32_t input_length, + uint32_t input_pos); + +/** + * Read LZW codes into client buffer, mapping output to colours. + * + * The context must have been initialised using \ref lzw_decode_init_map + * before calling this function, in order to provide the colour mapping table + * and any transparency index. + * + * Ensure anything in output is used before calling this, as anything + * there before this call will be trampled. + * + * \param[in] ctx LZW reading context, updated. + * \param[in] output_data Client buffer to fill with colour mapped values. + * \param[in] output_length Size of output array. + * \param[out] output_written Returns the number of values written to data. + * \return LZW_OK on success, or appropriate error code otherwise. + */ +lzw_result lzw_decode_map(struct lzw_ctx *ctx, + uint32_t *restrict output_data, + uint32_t output_length, + uint32_t *restrict output_written); #endif -- cgit v1.2.3