From decfeceb211697b18b2525ec533a95ed03418e1d Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Sun, 4 Apr 2021 23:40:01 +0100 Subject: lzw: Direct output into frame data, avoiding stack. If the frame is non-interlaced, and has the same rowstride as the full image, then we can decode lzw directly into the output image. --- src/libnsgif.c | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++-- src/lzw.c | 90 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++- src/lzw.h | 25 ++++++++++++++++ 3 files changed, 195 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/libnsgif.c b/src/libnsgif.c index 752f8c2..3c49218 100644 --- a/src/libnsgif.c +++ b/src/libnsgif.c @@ -626,8 +626,8 @@ static gif_result gif__recover_previous_frame(const gif_animation *gif) return GIF_OK; } -static inline gif_result -gif__decode(gif_animation *gif, +static gif_result +gif__decode_complex(gif_animation *gif, unsigned int frame, unsigned int width, unsigned int height, @@ -701,6 +701,85 @@ gif__decode(gif_animation *gif, return ret; } +static gif_result +gif__decode_simple(gif_animation *gif, + unsigned int frame, + unsigned int height, + unsigned int offset_y, + uint8_t minimum_code_size, + unsigned int *restrict frame_data, + unsigned int *restrict colour_table) +{ + unsigned int transparency_index; + uint32_t pixels = gif->width * height; + uint32_t written = 0; + gif_result ret = GIF_OK; + 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); + 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, + frame_data, pixels, &written); + pixels -= written; + frame_data += written; + if (res != LZW_OK) { + /* Unexpected end of frame, try to recover */ + if (res == LZW_OK_EOD) { + ret = GIF_OK; + } else { + ret = gif_error_from_lzw(res); + } + break; + } + } + + if (pixels == 0) { + ret = GIF_OK; + } + + return ret; +} + +static inline gif_result +gif__decode(gif_animation *gif, + unsigned int frame, + unsigned int width, + unsigned int height, + unsigned int offset_x, + unsigned int offset_y, + unsigned int interlace, + uint8_t minimum_code_size, + unsigned int *restrict frame_data, + unsigned int *restrict colour_table) +{ + gif_result ret; + + if (interlace == false && width == gif->width && offset_x == 0) { + ret = gif__decode_simple(gif, frame, height, offset_y, + minimum_code_size, frame_data, colour_table); + } else { + ret = gif__decode_complex(gif, frame, width, height, + offset_x, offset_y, interlace, + minimum_code_size, frame_data, colour_table); + } + + return ret; +} + /** * decode a gif frame * diff --git a/src/lzw.c b/src/lzw.c index 88ee060..ece06e7 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -85,6 +85,9 @@ struct lzw_ctx { uint32_t output_code; /**< Code that has been partially output. */ uint32_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]; @@ -320,7 +323,7 @@ typedef uint32_t (*lzw_writer_fn)( * \return LZW_OK on success, or appropriate error code otherwise. */ static inline lzw_result lzw__decode(struct lzw_ctx *ctx, - uint8_t *restrict output, + void *restrict output, uint32_t length, lzw_writer_fn write_pixels, uint32_t *restrict used) @@ -463,3 +466,88 @@ lzw_result lzw_decode_continuous(struct lzw_ctx *ctx, return LZW_OK; } + +/** + * Write colour mapped values for this code to the output stack. + * + * 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. + * \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) +{ + uint32_t *restrict stack_pos = (uint32_t *)buffer + used; + struct lzw_table_entry * const table = ctx->table; + uint32_t space = length - used; + uint32_t count = left; + + if (count > space) { + left = count - space; + count = space; + } else { + left = 0; + } + + ctx->output_code = code; + ctx->output_left = left; + + for (unsigned i = left; i != 0; i--) { + struct lzw_table_entry *entry = table + code; + code = entry->extends; + } + + stack_pos += count; + for (unsigned i = count; i != 0; i--) { + struct lzw_table_entry *entry = table + code; + --stack_pos; + if (entry->value != ctx->transparency_idx) { + *stack_pos = ctx->colour_map[entry->value]; + } + code = entry->extends; + } + + return count; +} + +/* 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) +{ + *used = 0; + + ctx->transparency_idx = transparency_idx; + ctx->colour_map = colour_map; + + if (ctx->output_left != 0) { + *used += lzw__write_pixels_map(ctx, data, length, *used, + ctx->output_code, ctx->output_left); + } + + while (*used != sizeof(ctx->stack_base)) { + lzw_result res = lzw__decode(ctx, data, length, + lzw__write_pixels_map, used); + if (res != LZW_OK) { + return res; + } + } + + return LZW_OK; +} diff --git a/src/lzw.h b/src/lzw.h index 9f8f979..c442cff 100644 --- a/src/lzw.h +++ b/src/lzw.h @@ -106,4 +106,29 @@ lzw_result lzw_decode_continuous(struct lzw_ctx *ctx, const uint8_t ** const data, uint32_t *restrict used); +/** + * 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. + * + * 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. + * \return LZW_OK on success, or appropriate error code otherwise. + */ +lzw_result lzw_decode_map_continuous(struct lzw_ctx *ctx, + uint32_t transparency_idx, + uint32_t *restrict colour_table, + uint32_t *restrict data, + uint32_t length, + uint32_t *restrict used); + #endif -- cgit v1.2.3