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.

3 files changed, 196 insertions, 3 deletions

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 1440b78..0d39882 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];
 
@@ -363,6 +366,63 @@ static inline uint32_t lzw__write_pixels(struct lzw_ctx *ctx,
 	return count;
 }
 
+
+/**
+ * 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;
+}
+
 /**
  * Get the next LZW code and write its value(s) to output buffer.
  *
@@ -374,7 +434,7 @@ static inline uint32_t lzw__write_pixels(struct lzw_ctx *ctx,
  * \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 +523,32 @@ lzw_result lzw_decode_continuous(struct lzw_ctx *ctx,
 
 	return LZW_OK;
 }
+
+/* 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 c130c24..3be97d0 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 *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