Gitweb links: ...log http://git.netsurf-browser.org/libnsgif.git/shortlog/0aeb0afe342d035ab32b... ...commit http://git.netsurf-browser.org/libnsgif.git/commit/0aeb0afe342d035ab32bac... ...tree http://git.netsurf-browser.org/libnsgif.git/tree/0aeb0afe342d035ab32bac1d... The branch, master has been updated via 0aeb0afe342d035ab32bac1d89b185f25d7acf32 (commit) via 2cff6fc0dc2f57816a73a37501e017cd252457f8 (commit) via 6dc2f20b0a836750b98b0abba9dad6e54571ecad (commit) via e2c52950885bf50271a990511ba7954736080735 (commit) via decfeceb211697b18b2525ec533a95ed03418e1d (commit) via db49e5b61beb1759469f3e6bd53850c6bc0a38ac (commit) via 9dd7f040b1dffbe94b833aeede412054544709e8 (commit) via 1abac9abe5a3f4a0f1b892b9aa2e036f5871b37d (commit) via 39519291052243d5ab678be3da5ae12787941016 (commit) via 45c0d2812d13d110b151e4b60787275572c65e69 (commit) via c2074de22a8d77ff8e688a3f22132f6d0ee44c20 (commit) via 602dcec85a1fc6f932bd32b49008354016c29bec (commit) via f434088537e3c8a4bde836fcea3c159b44fe8983 (commit) via 3ab1f9e45455ea4406168da9a5837bd0ce176542 (commit) via 79d5d80a4dbe33d9e446aa637d7b905fac072f88 (commit) via 270155287a0f2e7788253a38178efefb608ffdd5 (commit) via def4cda3550f2f3e661fecf897447e0409e3ca15 (commit) via b5b9d0524b2159278be8ebb18812b82872704c5d (commit) via bf63b51e89777cccbc3e94e3c4ca082f5f82def2 (commit) via c06164add4d44baad937ee9abcd110a46b7944ba (commit) via f1e0c5c5bbb01ab9747b9bd0113e6598bcc5025a (commit) via 87f9e081593d4ca373997f4a19578f13066e1941 (commit) via 29f3d0fb22f9cdbd603e9561c9c8e000a2d6d5ef (commit) via d8e8d3cceef907f798276014ebdfed7c370fb866 (commit) from bba28df0cc0c75338a63645c6a55aebfebe91c74 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commitdiff http://git.netsurf-browser.org/libnsgif.git/commit/?id=0aeb0afe342d035ab3... commit 0aeb0afe342d035ab32bac1d89b185f25d7acf32 Author: Michael Drake <tlsa(a)netsurf-browser.org&gt; Commit: Michael Drake <tlsa(a)netsurf-browser.org&gt; lzw: Always read three bytes on fast path to avoid swtich. diff --git a/src/lzw.c b/src/lzw.c index a3034f8..4b521b6 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -41,7 +41,7 @@ struct lzw_read_ctx { 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 */ + size_t sb_bit; /**< Current bit offset in sub-block */ uint32_t sb_bit_count; /**< Bit count in sub-block */ }; @@ -165,29 +165,25 @@ 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, - uint8_t code_size, + uint32_t code_size, uint32_t *restrict code_out) { uint32_t code = 0; - uint8_t current_bit = ctx->sb_bit & 0x7; - uint8_t byte_advance = (current_bit + code_size) >> 3; + uint32_t current_bit = ctx->sb_bit & 0x7; - assert(byte_advance <= 2); - - if (ctx->sb_bit + code_size <= ctx->sb_bit_count) { - /* Fast path: code fully inside this sub-block */ + if (ctx->sb_bit + 24 <= ctx->sb_bit_count) { + /* Fast path: read three bytes from this sub-block */ const uint8_t *data = ctx->sb_data + (ctx->sb_bit >> 3); - switch (byte_advance) { - case 2: code |= data[2] << 16; /* Fall through */ - case 1: code |= data[1] << 8; /* Fall through */ - case 0: code |= data[0] << 0; - } + code |= *data++ << 0; + code |= *data++ << 8; + code |= *data << 16; ctx->sb_bit += code_size; } else { /* Slow path: code spans sub-blocks */ + uint8_t byte_advance = (current_bit + code_size) >> 3; uint8_t byte = 0; - uint8_t bits_remaining_0 = (code_size < (8 - current_bit)) ? - code_size : (8 - current_bit); + uint8_t bits_remaining_0 = (code_size < (8u - current_bit)) ? + code_size : (8u - current_bit); uint8_t bits_remaining_1 = code_size - bits_remaining_0; uint8_t bits_used[3] = { [0] = bits_remaining_0, @@ -195,6 +191,8 @@ static inline lzw_result lzw__read_code( [2] = bits_remaining_1 - 8, }; + assert(byte_advance <= 2); + while (true) { const uint8_t *data = ctx->sb_data; lzw_result res; commitdiff http://git.netsurf-browser.org/libnsgif.git/commit/?id=2cff6fc0dc2f57816a... commit 2cff6fc0dc2f57816a73a37501e017cd252457f8 Author: Michael Drake <tlsa(a)netsurf-browser.org&gt; Commit: Michael Drake <tlsa(a)netsurf-browser.org&gt; lzw: Restrict pointers through code reader. diff --git a/src/lzw.c b/src/lzw.c index 4c4e09c..a3034f8 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -36,7 +36,7 @@ * 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 */ + const uint8_t *restrict data; /**< Pointer to start of input data */ uint32_t data_len; /**< Input data length */ uint32_t data_sb_next; /**< Offset to sub-block size */ @@ -122,7 +122,7 @@ void lzw_context_destroy(struct lzw_ctx *ctx) * \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) +static lzw_result lzw__block_advance(struct lzw_read_ctx *restrict ctx) { uint32_t block_size; uint32_t next_block_pos = ctx->data_sb_next; @@ -164,9 +164,9 @@ static lzw_result lzw__block_advance(struct lzw_read_ctx *ctx) * \return LZW_OK or LZW_OK_EOD on success, appropriate error otherwise. */ static inline lzw_result lzw__read_code( - struct lzw_read_ctx *ctx, + struct lzw_read_ctx *restrict ctx, uint8_t code_size, - uint32_t *code_out) + uint32_t *restrict code_out) { uint32_t code = 0; uint8_t current_bit = ctx->sb_bit & 0x7; commitdiff http://git.netsurf-browser.org/libnsgif.git/commit/?id=6dc2f20b0a836750b9... commit 6dc2f20b0a836750b98b0abba9dad6e54571ecad Author: Michael Drake <tlsa(a)netsurf-browser.org&gt; Commit: Michael Drake <tlsa(a)netsurf-browser.org&gt; lzw: Constify table pointers in writer functions. diff --git a/src/lzw.c b/src/lzw.c index ece06e7..4c4e09c 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -400,7 +400,7 @@ static inline uint32_t lzw__write_pixels(struct lzw_ctx *ctx, uint32_t left) { uint8_t *restrict output_pos = (uint8_t *)output + used; - struct lzw_table_entry * const table = ctx->table; + const struct lzw_table_entry * const table = ctx->table; uint32_t space = length - used; uint32_t count = left; @@ -416,13 +416,13 @@ static inline uint32_t lzw__write_pixels(struct lzw_ctx *ctx, /* Skip over any values we don't have space for. */ for (unsigned i = left; i != 0; i--) { - struct lzw_table_entry *entry = table + code; + const struct lzw_table_entry *entry = table + code; code = entry->extends; } output_pos += count; for (unsigned i = count; i != 0; i--) { - struct lzw_table_entry *entry = table + code; + const struct lzw_table_entry *entry = table + code; *--output_pos = entry->value; code = entry->extends; } @@ -491,7 +491,7 @@ static inline uint32_t lzw__write_pixels_map(struct lzw_ctx *ctx, uint32_t left) { uint32_t *restrict stack_pos = (uint32_t *)buffer + used; - struct lzw_table_entry * const table = ctx->table; + const struct lzw_table_entry * const table = ctx->table; uint32_t space = length - used; uint32_t count = left; @@ -506,13 +506,13 @@ static inline uint32_t lzw__write_pixels_map(struct lzw_ctx *ctx, ctx->output_left = left; for (unsigned i = left; i != 0; i--) { - struct lzw_table_entry *entry = table + code; + const 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; + const struct lzw_table_entry *entry = table + code; --stack_pos; if (entry->value != ctx->transparency_idx) { *stack_pos = ctx->colour_map[entry->value]; commitdiff http://git.netsurf-browser.org/libnsgif.git/commit/?id=e2c52950885bf50271... commit e2c52950885bf50271a990511ba7954736080735 Author: Michael Drake <tlsa(a)netsurf-browser.org&gt; Commit: Michael Drake <tlsa(a)netsurf-browser.org&gt; gif: Switch complex decoder over to continuous lzw API. diff --git a/src/libnsgif.c b/src/libnsgif.c index 3c49218..6d78dc2 100644 --- a/src/libnsgif.c +++ b/src/libnsgif.c @@ -681,7 +681,7 @@ gif__decode_complex(gif_animation *gif, } break; } - res = lzw_decode(gif->lzw_ctx, + res = lzw_decode_continuous(gif->lzw_ctx, &uncompressed, &available); } commitdiff http://git.netsurf-browser.org/libnsgif.git/commit/?id=decfeceb211697b18b... commit decfeceb211697b18b2525ec533a95ed03418e1d Author: Michael Drake <tlsa(a)netsurf-browser.org&gt; Commit: Michael Drake <tlsa(a)netsurf-browser.org&gt; 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. 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 commitdiff http://git.netsurf-browser.org/libnsgif.git/commit/?id=db49e5b61beb175946... commit db49e5b61beb1759469f3e6bd53850c6bc0a38ac Author: Michael Drake <tlsa(a)netsurf-browser.org&gt; Commit: Michael Drake <tlsa(a)netsurf-browser.org&gt; gif: Handle any uncompressed output before exiting due to error. diff --git a/src/libnsgif.c b/src/libnsgif.c index e0d97c0..752f8c2 100644 --- a/src/libnsgif.c +++ b/src/libnsgif.c @@ -672,8 +672,6 @@ gif__decode(gif_animation *gif, const uint8_t *uncompressed; unsigned row_available; if (available == 0) { - res = lzw_decode(gif->lzw_ctx, - &uncompressed, &available); if (res != LZW_OK) { /* Unexpected end of frame, try to recover */ if (res == LZW_OK_EOD) { @@ -683,6 +681,8 @@ gif__decode(gif_animation *gif, } break; } + res = lzw_decode(gif->lzw_ctx, + &uncompressed, &available); } row_available = x < available ? x : available; commitdiff http://git.netsurf-browser.org/libnsgif.git/commit/?id=9dd7f040b1dffbe94b... commit 9dd7f040b1dffbe94b833aeede412054544709e8 Author: Michael Drake <tlsa(a)netsurf-browser.org&gt; Commit: Michael Drake <tlsa(a)netsurf-browser.org&gt; lzw: Add function for decoding multiple LZW codes at a time. diff --git a/src/lzw.c b/src/lzw.c index 5308ff4..88ee060 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -437,3 +437,29 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, return lzw__decode(ctx, ctx->stack_base, sizeof(ctx->stack_base), lzw__write_pixels, used); } + +/* Exported function, documented in lzw.h */ +lzw_result lzw_decode_continuous(struct lzw_ctx *ctx, + const uint8_t ** const data, + uint32_t *restrict used) +{ + *used = 0; + *data = ctx->stack_base; + + if (ctx->output_left != 0) { + *used += lzw__write_pixels(ctx, + ctx->stack_base, sizeof(ctx->stack_base), *used, + 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); + if (res != LZW_OK) { + return res; + } + } + + return LZW_OK; +} diff --git a/src/lzw.h b/src/lzw.h index dd0191e..9f8f979 100644 --- a/src/lzw.h +++ b/src/lzw.h @@ -91,4 +91,19 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, const uint8_t *restrict *const restrict data, uint32_t *restrict used); +/** + * 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. + * + * \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. + * \return LZW_OK on success, or appropriate error code otherwise. + */ +lzw_result lzw_decode_continuous(struct lzw_ctx *ctx, + const uint8_t ** const data, + uint32_t *restrict used); + #endif commitdiff http://git.netsurf-browser.org/libnsgif.git/commit/?id=1abac9abe5a3f4a0f1... commit 1abac9abe5a3f4a0f1b892b9aa2e036f5871b37d Author: Michael Drake <tlsa(a)netsurf-browser.org&gt; Commit: Michael Drake <tlsa(a)netsurf-browser.org&gt; lzw: Add support for resumable output of a single code. This allows handling of insufficient output buffer space. diff --git a/src/lzw.c b/src/lzw.c index 035882d..5308ff4 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -82,6 +82,9 @@ struct lzw_ctx { uint32_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. */ + /** Output value stack. */ uint8_t stack_base[LZW_TABLE_ENTRY_MAX]; @@ -263,6 +266,8 @@ lzw_result lzw_decode_init( ctx->clear_code = (1 << minimum_code_size) + 0; ctx->eoi_code = (1 << minimum_code_size) + 1; + ctx->output_left = 0; + /* Initialise the standard table entries */ for (uint32_t i = 0; i < ctx->clear_code; ++i) { table[i].first = i; @@ -296,47 +301,28 @@ static inline void lzw__table_add_entry( ctx->table_size++; } -/** - * Write values for this code to the output stack. - * - * \param[in] ctx LZW reading context, updated. - * \param[in] output Array to write output values into. - * \param[in] code LZW code to output values for. - * \return Number of pixel values written. - */ -static inline uint32_t lzw__write_pixels(struct lzw_ctx *ctx, +typedef uint32_t (*lzw_writer_fn)( + struct lzw_ctx *ctx, void *restrict output, - uint32_t code) -{ - uint8_t *restrict output_pos = (uint8_t *)output; - struct lzw_table_entry * const table = ctx->table; - uint32_t count = table[code].count; - - output_pos += count; - for (unsigned i = count; i != 0; i--) { - struct lzw_table_entry *entry = table + code; - *--output_pos = entry->value; - code = entry->extends; - } - - return count; -} + uint32_t length, + uint32_t used, + uint32_t code, + uint32_t left); /** - * Fill the LZW stack with decompressed data + * Get the next LZW code and write its value(s) to output buffer. * - * Ensure anything in output is used before calling this, as anything - * on the there before this call will be trampled. - * - * \param[in] ctx LZW reading context, updated. - * \param[in] output Array to write output values into. - * \param[out] used Returns the number of values written. - * Use with `stack_base_out` value from previous - * lzw_decode_init() call. + * \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. * \return LZW_OK on success, or appropriate error code otherwise. */ static inline lzw_result lzw__decode(struct lzw_ctx *ctx, uint8_t *restrict output, + uint32_t length, + lzw_writer_fn write_pixels, uint32_t *restrict used) { lzw_result res; @@ -375,7 +361,8 @@ static inline lzw_result lzw__decode(struct lzw_ctx *ctx, } } - *used += lzw__write_pixels(ctx, output, code); + *used += write_pixels(ctx, output, length, *used, code, + ctx->table[code].count); } /* Store details of this code as "previous code" to the context. */ @@ -386,6 +373,60 @@ static inline lzw_result lzw__decode(struct lzw_ctx *ctx, return LZW_OK; } +/** + * Write 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(struct lzw_ctx *ctx, + void *restrict output, + uint32_t length, + uint32_t used, + uint32_t code, + uint32_t left) +{ + uint8_t *restrict output_pos = (uint8_t *)output + 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; + + /* Skip over any values we don't have space for. */ + for (unsigned i = left; i != 0; i--) { + struct lzw_table_entry *entry = table + code; + code = entry->extends; + } + + output_pos += count; + for (unsigned i = count; i != 0; i--) { + struct lzw_table_entry *entry = table + code; + *--output_pos = entry->value; + code = entry->extends; + } + + return count; +} + /* Exported function, documented in lzw.h */ lzw_result lzw_decode(struct lzw_ctx *ctx, const uint8_t *restrict* const restrict data, @@ -393,5 +434,6 @@ lzw_result lzw_decode(struct lzw_ctx *ctx, { *used = 0; *data = ctx->stack_base; - return lzw__decode(ctx, ctx->stack_base, used); + return lzw__decode(ctx, ctx->stack_base, sizeof(ctx->stack_base), + lzw__write_pixels, used); } ----------------------------------------------------------------------- Summary of changes: src/libnsgif.c | 221 +++++++++++++++++++-------- src/lzw.c | 456 ++++++++++++++++++++++++++++++++++++++------------------ src/lzw.h | 69 ++++++--- 3 files changed, 524 insertions(+), 222 deletions(-) diff --git a/src/libnsgif.c b/src/libnsgif.c index 512ebfe..6d78dc2 100644 --- a/src/libnsgif.c +++ b/src/libnsgif.c @@ -42,6 +42,9 @@ /** Transparent colour */ #define GIF_TRANSPARENT_COLOUR 0x00 +/** No transparency */ +#define GIF_NO_TRANSPARENCY (0xFFFFFFFFu) + /* GIF Flags */ #define GIF_FRAME_COMBINE 1 #define GIF_FRAME_CLEAR 2 @@ -623,6 +626,160 @@ static gif_result gif__recover_previous_frame(const gif_animation *gif) return GIF_OK; } +static gif_result +gif__decode_complex(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) +{ + unsigned int transparency_index; + uint32_t available = 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; + + for (unsigned int y = 0; y < height; y++) { + unsigned int x; + unsigned int decode_y; + unsigned int *frame_scanline; + + if (interlace) { + decode_y = gif_interlaced_line(height, y) + offset_y; + } else { + decode_y = y + offset_y; + } + frame_scanline = frame_data + offset_x + (decode_y * gif->width); + + x = width; + while (x > 0) { + const uint8_t *uncompressed; + unsigned row_available; + if (available == 0) { + 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; + } + res = lzw_decode_continuous(gif->lzw_ctx, + &uncompressed, &available); + } + + row_available = x < available ? x : available; + x -= row_available; + available -= row_available; + while (row_available-- > 0) { + register unsigned int colour; + colour = *uncompressed++; + if (colour != transparency_index) { + *frame_scanline = colour_table[colour]; + } + frame_scanline++; + } + } + } + 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 * @@ -643,11 +800,8 @@ gif_internal_decode_frame(gif_animation *gif, unsigned int flags, colour_table_size, interlace; unsigned int *colour_table; unsigned int *frame_data = 0; // Set to 0 for no warnings - unsigned int *frame_scanline; unsigned int save_buffer_position; unsigned int return_value = 0; - unsigned int x, y, decode_y, burst_bytes; - register unsigned char colour; /* Ensure this frame is supposed to be decoded */ if (gif->frames[frame].display == false) { @@ -801,10 +955,6 @@ 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 */ @@ -868,62 +1018,15 @@ gif_internal_decode_frame(gif_animation *gif, gif->decoded_frame = frame; gif->buffer_position = (gif_data - gif->gif_data) + 1; - /* Initialise the LZW decoding */ - 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 */ - for (y = 0; y < height; y++) { - if (interlace) { - decode_y = gif_interlaced_line(height, y) + offset_y; - } else { - decode_y = y + offset_y; - } - 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) { - 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 = *--stack_pos; - if (((gif->frames[frame].transparency) && - (colour != gif->frames[frame].transparency_index)) || - (!gif->frames[frame].transparency)) { - *frame_scanline = colour_table[colour]; - } - frame_scanline++; - } - } else { - res = lzw_decode(gif->lzw_ctx, &stack_pos); - if (res != LZW_OK) { - /* Unexpected end of frame, try to recover */ - if (res == LZW_OK_EOD) { - return_value = GIF_OK; - } else { - return_value = gif_error_from_lzw(res); - } - goto gif_decode_frame_exit; - } - } - } - } + return_value = gif__decode(gif, frame, width, height, + offset_x, offset_y, interlace, gif_data[0], + frame_data, colour_table); } else { /* Clear our frame */ if (gif->frames[frame].disposal_method == GIF_FRAME_CLEAR) { + unsigned int y; for (y = 0; y < height; y++) { + unsigned int *frame_scanline; frame_scanline = frame_data + offset_x + ((offset_y + y) * gif->width); if (gif->frames[frame].transparency) { memset(frame_scanline, diff --git a/src/lzw.c b/src/lzw.c index 1f85496..4b521b6 100644 --- a/src/lzw.c +++ b/src/lzw.c @@ -4,6 +4,7 @@ * http://www.opensource.org/licenses/mit-license.php * * Copyright 2017 Michael Drake <michael.drake(a)codethink.co.uk&gt; + * Copyright 2021 Michael Drake <tlsa(a)netsurf-browser.org&gt; */ #include <assert.h> @@ -20,6 +21,8 @@ * Decoder for GIF LZW data. */ +/** Maximum number of lzw table entries. */ +#define LZW_TABLE_ENTRY_MAX (1u << LZW_CODE_MAX) /** * Context for reading LZW data. @@ -33,55 +36,63 @@ * 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 */ + const uint8_t *restrict 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 */ + size_t sb_bit; /**< Current bit offset in sub-block */ uint32_t sb_bit_count; /**< Bit count in sub-block */ }; /** - * LZW dictionary entry. + * LZW table entry. * - * Records in the dictionary are composed of 1 or more entries. - * Entries point to previous entries which can be followed to compose + * Records in the table are composed of 1 or more entries. + * Entries refer to the entry they extend 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 + * the `value` from each entry, and move to the entry it extends. + * If the extended entries 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. */ +struct lzw_table_entry { + uint8_t value; /**< Last value for record ending at entry. */ + uint8_t first; /**< First value in entry's entire record. */ + uint16_t count; /**< Count of values in this entry's record. */ + uint16_t extends; /**< Offset in table to previous entry. */ }; /** * LZW decompression context. */ struct lzw_ctx { - /** Input reading context */ - struct lzw_read_ctx input; + struct lzw_read_ctx input; /**< Input reading context */ - uint32_t previous_code; /**< Code read from input previously. */ - uint32_t previous_code_first; /**< First value of previous code. */ + 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. */ - 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 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. */ 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. */ + uint32_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. */ + + uint32_t transparency_idx; /**< Index representing transparency. */ + uint32_t *restrict colour_map; /**< Index to pixel colour mapping */ /** Output value stack. */ - uint8_t stack_base[1 << LZW_CODE_MAX]; + uint8_t stack_base[LZW_TABLE_ENTRY_MAX]; - /** LZW decode dictionary. Generated during decode. */ - struct lzw_dictionary_entry table[1 << LZW_CODE_MAX]; + /** LZW code table. Generated during decode. */ + struct lzw_table_entry table[LZW_TABLE_ENTRY_MAX]; }; @@ -111,7 +122,7 @@ void lzw_context_destroy(struct lzw_ctx *ctx) * \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) +static lzw_result lzw__block_advance(struct lzw_read_ctx *restrict ctx) { uint32_t block_size; uint32_t next_block_pos = ctx->data_sb_next; @@ -152,31 +163,27 @@ static lzw_result lzw__block_advance(struct lzw_read_ctx *ctx) * \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) +static inline lzw_result lzw__read_code( + struct lzw_read_ctx *restrict ctx, + uint32_t code_size, + uint32_t *restrict code_out) { uint32_t code = 0; - uint8_t current_bit = ctx->sb_bit & 0x7; - uint8_t byte_advance = (current_bit + code_size) >> 3; - - assert(byte_advance <= 2); + uint32_t current_bit = ctx->sb_bit & 0x7; - if (ctx->sb_bit + code_size <= ctx->sb_bit_count) { - /* Fast path: code fully inside this sub-block */ + if (ctx->sb_bit + 24 <= ctx->sb_bit_count) { + /* Fast path: read three bytes from this sub-block */ const uint8_t *data = ctx->sb_data + (ctx->sb_bit >> 3); - switch (byte_advance) { - case 2: code |= data[2] << 16; /* Fall through */ - case 1: code |= data[1] << 8; /* Fall through */ - case 0: code |= data[0] << 0; - } + code |= *data++ << 0; + code |= *data++ << 8; + code |= *data << 16; ctx->sb_bit += code_size; } else { /* Slow path: code spans sub-blocks */ + uint8_t byte_advance = (current_bit + code_size) >> 3; uint8_t byte = 0; - uint8_t bits_remaining_0 = (code_size < (8 - current_bit)) ? - code_size : (8 - current_bit); + uint8_t bits_remaining_0 = (code_size < (8u - current_bit)) ? + code_size : (8u - current_bit); uint8_t bits_remaining_1 = code_size - bits_remaining_0; uint8_t bits_used[3] = { [0] = bits_remaining_0, @@ -184,6 +191,8 @@ static inline lzw_result lzw__next_code( [2] = bits_remaining_1 - 8, }; + assert(byte_advance <= 2); + while (true) { const uint8_t *data = ctx->sb_data; lzw_result res; @@ -215,48 +224,18 @@ static inline lzw_result lzw__next_code( /** - * Clear LZW code dictionary. + * Clear LZW code table. * - * \param[in] ctx LZW reading context, updated. - * \param[out] stack_pos_out Returns current stack position. + * \param[in] ctx LZW reading context, updated. * \return LZW_OK or error code. */ -static lzw_result lzw__clear_codes( - struct lzw_ctx *ctx, - const uint8_t ** const stack_pos_out) +static inline void lzw__clear_table( + struct lzw_ctx *ctx) { - 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; + /* Reset table building context */ + ctx->code_size = ctx->initial_code_size; + ctx->code_max = (1 << ctx->initial_code_size) - 1; + ctx->table_size = ctx->eoi_code + 1; } @@ -266,13 +245,11 @@ lzw_result lzw_decode_init( 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) + uint8_t minimum_code_size) { - struct lzw_dictionary_entry *table = ctx->table; + struct lzw_table_entry *table = ctx->table; - if (code_size >= LZW_CODE_MAX) { + if (minimum_code_size >= LZW_CODE_MAX) { return LZW_BAD_ICODE; } @@ -284,98 +261,291 @@ lzw_result lzw_decode_init( ctx->input.sb_bit = 0; ctx->input.sb_bit_count = 0; - /* Initialise the dictionary building context */ - ctx->initial_code_size = code_size; + /* Initialise the table building context */ + ctx->initial_code_size = minimum_code_size + 1; - ctx->clear_code = (1 << code_size) + 0; - ctx->eoi_code = (1 << code_size) + 1; + ctx->clear_code = (1 << minimum_code_size) + 0; + ctx->eoi_code = (1 << minimum_code_size) + 1; - /* Initialise the standard dictionary entries */ + ctx->output_left = 0; + + /* Initialise the standard table entries */ for (uint32_t i = 0; i < ctx->clear_code; ++i) { - table[i].first_value = i; - table[i].last_value = i; + table[i].first = i; + table[i].value = i; + table[i].count = 1; } - *stack_base_out = ctx->stack_base; - return lzw__clear_codes(ctx, stack_pos_out); + lzw__clear_table(ctx); + ctx->prev_code = ctx->clear_code; + + return LZW_OK; } +/** + * Create new table entry. + * + * \param[in] ctx LZW reading context, updated. + * \param[in] code Last value code for new table entry. + */ +static inline void lzw__table_add_entry( + struct lzw_ctx *ctx, + uint32_t code) +{ + struct lzw_table_entry *entry = &ctx->table[ctx->table_size]; -/* Exported function, documented in lzw.h */ -lzw_result lzw_decode(struct lzw_ctx *ctx, - const uint8_t ** const stack_pos_out) + entry->value = code; + entry->first = ctx->prev_code_first; + entry->count = ctx->prev_code_count + 1; + entry->extends = ctx->prev_code; + + ctx->table_size++; +} + +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); + +/** + * 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. + * \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) { lzw_result res; - uint32_t code_new; - uint32_t code_out; - 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; - struct lzw_dictionary_entry * const table = ctx->table; + uint32_t code; /* Get a new code from the input */ - res = lzw__next_code(&ctx->input, ctx->current_code_size, &code_new); + res = lzw__read_code(&ctx->input, ctx->code_size, &code); if (res != LZW_OK) { return res; } /* Handle the new code */ - if (code_new == clear_code) { - /* Got Clear code */ - return lzw__clear_codes(ctx, stack_pos_out); - - } else if (code_new == ctx->eoi_code) { + if (code == ctx->eoi_code) { /* Got End of Information code */ return LZW_EOI_CODE; - } else if (code_new > current_entry) { + } else if (code > ctx->table_size) { /* Code is invalid */ return LZW_BAD_CODE; - } else if (code_new < current_entry) { - /* Code is in table */ - code_out = code_new; - last_value = table[code_new].first_value; + } else if (code == ctx->clear_code) { + lzw__clear_table(ctx); + } else { + if (ctx->prev_code != ctx->clear_code && + ctx->table_size < LZW_TABLE_ENTRY_MAX) { + uint32_t size = ctx->table_size; + lzw__table_add_entry(ctx, (code < size) ? + ctx->table[code].first : + ctx->prev_code_first); + + /* Ensure code size is increased, if needed. */ + if (size == ctx->code_max && + ctx->code_size < LZW_CODE_MAX) { + ctx->code_size++; + ctx->code_max = (1 << ctx->code_size) - 1; + } + } + + *used += write_pixels(ctx, output, length, *used, code, + ctx->table[code].count); + } + + /* Store details of this code as "previous code" to the context. */ + ctx->prev_code_first = ctx->table[code].first; + ctx->prev_code_count = ctx->table[code].count; + ctx->prev_code = code; + + return LZW_OK; +} + +/** + * Write 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(struct lzw_ctx *ctx, + void *restrict output, + uint32_t length, + uint32_t used, + uint32_t code, + uint32_t left) +{ + uint8_t *restrict output_pos = (uint8_t *)output + used; + const 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 { - /* Code not in table */ - *stack_pos++ = ctx->previous_code_first; - code_out = ctx->previous_code; - last_value = ctx->previous_code_first; + left = 0; } - /* 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++; + ctx->output_code = code; + ctx->output_left = left; + + /* Skip over any values we don't have space for. */ + for (unsigned i = left; i != 0; i--) { + const struct lzw_table_entry *entry = table + code; + code = entry->extends; + } + + output_pos += count; + for (unsigned i = count; i != 0; i--) { + const struct lzw_table_entry *entry = table + code; + *--output_pos = entry->value; + code = entry->extends; + } + + return count; +} + +/* Exported function, documented in lzw.h */ +lzw_result lzw_decode(struct lzw_ctx *ctx, + const uint8_t *restrict* const restrict data, + uint32_t *restrict used) +{ + *used = 0; + *data = ctx->stack_base; + return lzw__decode(ctx, ctx->stack_base, sizeof(ctx->stack_base), + lzw__write_pixels, used); +} + +/* Exported function, documented in lzw.h */ +lzw_result lzw_decode_continuous(struct lzw_ctx *ctx, + const uint8_t ** const data, + uint32_t *restrict used) +{ + *used = 0; + *data = ctx->stack_base; + + if (ctx->output_left != 0) { + *used += lzw__write_pixels(ctx, + ctx->stack_base, sizeof(ctx->stack_base), *used, + ctx->output_code, ctx->output_left); } - /* 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; + while (*used != sizeof(ctx->stack_base)) { + lzw_result res = lzw__decode(ctx, + ctx->stack_base, sizeof(ctx->stack_base), + lzw__write_pixels, used); + if (res != LZW_OK) { + return res; } } - /* Store details of this code as "previous code" to the context. */ - 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) { - struct lzw_dictionary_entry *entry = table + code_out; - *stack_pos++ = entry->last_value; - code_out = entry->previous_entry; + 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; + const 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--) { + const struct lzw_table_entry *entry = table + code; + code = entry->extends; + } + + stack_pos += count; + for (unsigned i = count; i != 0; i--) { + const 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; + } } - *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 385b425..c442cff 100644 --- a/src/lzw.h +++ b/src/lzw.h @@ -65,11 +65,8 @@ void lzw_context_destroy( * \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[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( @@ -77,29 +74,61 @@ lzw_result lzw_decode_init( 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); + uint8_t minimum_code_size); /** - * Fill the LZW stack with decompressed data + * Read a single LZW code and write into lzw context owned output buffer. * - * Ensure anything on the stack is used before calling this, as anything - * on the stack before this call will be trampled. + * Ensure anything in output is used before calling this, as anything + * on the there before this call will be trampled. * - * Caller does not own `stack_pos_out`. + * \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. + * \return LZW_OK on success, or appropriate error code otherwise. + */ +lzw_result lzw_decode(struct lzw_ctx *ctx, + const uint8_t *restrict *const restrict data, + uint32_t *restrict used); + +/** + * 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. * - * \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] data Returns pointer to array of output values. + * \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( - struct lzw_ctx *ctx, - const uint8_t ** const stack_pos_out); +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 -- NetSurf GIF Decoder