From 3ab1f9e45455ea4406168da9a5837bd0ce176542 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Sat, 3 Apr 2021 17:35:55 +0100 Subject: lzw: Output values in picture order. --- src/libnsgif.c | 19 +++++++++---------- src/lzw.c | 50 ++++++++++++++++++++++++++------------------------ src/lzw.h | 21 ++++++--------------- 3 files changed, 41 insertions(+), 49 deletions(-) diff --git a/src/libnsgif.c b/src/libnsgif.c index ed394a2..3b070b3 100644 --- a/src/libnsgif.c +++ b/src/libnsgif.c @@ -637,17 +637,19 @@ gif__decode(gif_animation *gif, { const uint8_t *stack_base; const uint8_t *stack_pos; + 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, &stack_base, &stack_pos); + minimum_code_size, &stack_base); if (res != LZW_OK) { return gif_error_from_lzw(res); } + stack_pos = stack_base; for (unsigned int y = 0; y < height; y++) { unsigned int x; unsigned int decode_y; @@ -660,21 +662,18 @@ gif__decode(gif_animation *gif, } frame_scanline = frame_data + offset_x + (decode_y * gif->width); - /* Rather than decoding pixel by pixel, we try to burst - * out streams of data to remove the need for end-of - * data checks every pixel. - */ x = width; while (x > 0) { - unsigned int burst_bytes = (stack_pos - stack_base); - if (burst_bytes > 0) { + if (written > 0) { + unsigned burst_bytes = written; if (burst_bytes > x) { burst_bytes = x; } x -= burst_bytes; + written -= burst_bytes; while (burst_bytes-- > 0) { register unsigned char colour; - colour = *--stack_pos; + colour = *stack_pos++; if (((gif->frames[frame].transparency) && (colour != gif->frames[frame].transparency_index)) || (!gif->frames[frame].transparency)) { @@ -683,7 +682,7 @@ gif__decode(gif_animation *gif, frame_scanline++; } } else { - res = lzw_decode(gif->lzw_ctx, &stack_pos); + res = lzw_decode(gif->lzw_ctx, &written); if (res != LZW_OK) { /* Unexpected end of frame, try to recover */ if (res == LZW_OK_EOD) { @@ -693,10 +692,10 @@ gif__decode(gif_animation *gif, } break; } + stack_pos = stack_base; } } } - return ret; } diff --git a/src/lzw.c b/src/lzw.c index 7032501..518756c 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -83,6 +83,7 @@ struct lzw_ctx { uint32_t table_size; /**< Next position in table to fill. */ /** Output value stack. */ + uint32_t written; uint8_t stack_base[LZW_TABLE_ENTRY_MAX]; /** LZW code table. Generated during decode. */ @@ -223,15 +224,12 @@ static inline lzw_result lzw__read_code( * Clear LZW code table. * * \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) + struct lzw_ctx *ctx) { uint32_t code; - uint8_t *stack_pos; /* Reset table building context */ ctx->code_size = ctx->initial_code_size; @@ -258,10 +256,8 @@ static lzw_result lzw__clear_codes( ctx->prev_code_count = 1; /* Reset the stack, and add first non-clear code added as first item. */ - stack_pos = ctx->stack_base; - *stack_pos++ = code; + ctx->stack_base[ctx->written++] = code; - *stack_pos_out = stack_pos; return LZW_OK; } @@ -273,8 +269,7 @@ lzw_result lzw_decode_init( uint32_t compressed_data_len, uint32_t compressed_data_pos, uint8_t minimum_code_size, - const uint8_t ** const stack_base_out, - const uint8_t ** const stack_pos_out) + const uint8_t ** const stack_base_out) { struct lzw_table_entry *table = ctx->table; @@ -303,8 +298,10 @@ lzw_result lzw_decode_init( table[i].count = 1; } + ctx->written = 0; + *stack_base_out = ctx->stack_base; - return lzw__clear_codes(ctx, stack_pos_out); + return lzw__clear_codes(ctx); } /** @@ -332,32 +329,28 @@ static inline void lzw__table_add_entry( * * \param[in] ctx LZW reading context, updated. * \param[in] code LZW code to output values for. - * \param[out] stack_pos_out Returns current stack position. - * There are `stack_pos_out - ctx->stack_base` - * current stack entries. */ static inline void lzw__write_pixels(struct lzw_ctx *ctx, - uint32_t code, - const uint8_t ** const stack_pos_out) + uint32_t code) { - uint8_t *stack_pos = ctx->stack_base; - uint32_t clear_code = ctx->clear_code; + uint8_t *stack_pos = ctx->stack_base + ctx->written; struct lzw_table_entry * const table = ctx->table; + uint32_t count = table[code].count; - while (code > clear_code) { + stack_pos += count; + for (unsigned i = count; i != 0; i--) { struct lzw_table_entry *entry = table + code; - *stack_pos++ = entry->value; + *--stack_pos = entry->value; code = entry->extends; } - *stack_pos++ = table[code].value; - *stack_pos_out = stack_pos; + ctx->written += count; return; } /* Exported function, documented in lzw.h */ lzw_result lzw_decode(struct lzw_ctx *ctx, - const uint8_t ** const stack_pos_out) + uint32_t *written) { lzw_result res; uint32_t code; @@ -371,7 +364,12 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, /* Handle the new code */ if (code == ctx->clear_code) { /* Got Clear code */ - return lzw__clear_codes(ctx, stack_pos_out); + res = lzw__clear_codes(ctx); + if (res == LZW_OK) { + *written = ctx->written; + ctx->written = 0; + } + return res; } else if (code == ctx->eoi_code) { /* Got End of Information code */ @@ -400,6 +398,10 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, ctx->prev_code_count = ctx->table[code].count; ctx->prev_code = code; - lzw__write_pixels(ctx, code, stack_pos_out); + lzw__write_pixels(ctx, code); + + *written = ctx->written; + ctx->written = 0; + return LZW_OK; } diff --git a/src/lzw.h b/src/lzw.h index 888526e..a4a58fc 100644 --- a/src/lzw.h +++ b/src/lzw.h @@ -67,9 +67,6 @@ void lzw_context_destroy( * 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[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( @@ -78,8 +75,7 @@ lzw_result lzw_decode_init( uint32_t compressed_data_len, uint32_t compressed_data_pos, uint8_t minimum_code_size, - const uint8_t ** const stack_base_out, - const uint8_t ** const stack_pos_out); + const uint8_t ** const stack_base_out); /** * Fill the LZW stack with decompressed data @@ -87,19 +83,14 @@ lzw_result lzw_decode_init( * 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. + * \param[in] ctx LZW reading context, updated. + * \param[out] written Returns the number of values written. + * Use with `stack_base_out` value from previous + * lzw_decode_init() call. * \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); - + uint32_t *written); #endif -- cgit v1.2.3