lzw: Output values in picture order.

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