gif: Replace old LZW decoder with a stand-alone decoder

4 files changed, 299 insertions, 281 deletions

diff --git a/gdk-pixbuf/io-gif.c b/gdk-pixbuf/io-gif.c
index b3f1b4647..911499520 100644
--- a/gdk-pixbuf/io-gif.c
+++ b/gdk-pixbuf/io-gif.c
@@ -58,6 +58,7 @@
 #include <glib/gi18n-lib.h>
 #include "gdk-pixbuf-io.h"
 #include "io-gif-animation.h"
+#include "lzw.h"
 
 
 
@@ -65,7 +66,6 @@
 #undef IO_GIFDEBUG
 
 #define MAXCOLORMAPSIZE  256
-#define MAX_LZW_BITS     12
 
 #define INTERLACE          0x40
 #define LOCALCOLORMAP      0x80
@@ -85,7 +85,6 @@ enum {
 	GIF_GET_EXTENSION,
 	GIF_GET_COLORMAP2,
 	GIF_PREPARE_LZW,
-	GIF_LZW_FILL_BUFFER,
 	GIF_GET_LZW,
 	GIF_DONE
 };
@@ -155,26 +154,10 @@ struct _GifContext
 	guchar block_count;
 	guchar block_buf[280];
 
-	int old_state; /* used by lzw_fill buffer */
-	/* get_code context */
-	int code_curbit;
-	int code_lastbit;
-	int code_done;
-	int code_last_byte;
-
-	/* lzw context */
-	gint lzw_code_size;
 	guchar lzw_set_code_size;
-	gint lzw_max_code;
-	gint lzw_max_code_size;
-	gint lzw_firstcode;
-	gint lzw_oldcode;
-	gint lzw_clear_code;
-	gint lzw_end_code;
-	gint *lzw_sp;
-
-	gint lzw_table[2][(1 << MAX_LZW_BITS)];
-	gint lzw_stack[(1 << (MAX_LZW_BITS)) * 2 + 1];
+	LZWDecoder *lzw_decoder;
+	guint8 *index_buffer;
+	gsize index_buffer_length;
 
 	/* painting context */
 	gint draw_xpos;
@@ -185,9 +168,6 @@ struct _GifContext
         GError **error;
 };
 
-/* The buffer must be at least 255 bytes long. */
-static int GetDataBlock (GifContext *, unsigned char *);
-
 
 
 #ifdef IO_GIFDEBUG
@@ -446,225 +426,6 @@ gif_get_extension (GifContext *context)
 	return 0;
 }
 
-static int ZeroDataBlock = FALSE;
-
-/* @buf must be at least 255 bytes long. */
-static int
-GetDataBlock (GifContext *context,
-	      unsigned char *buf)
-{
-/*  	unsigned char count; */
-
-	if (!gif_read (context, &context->block_count, 1)) {
-		/*g_message (_("GIF: error in getting DataBlock size\n"));*/
-		return -1;
-	}
-
-	ZeroDataBlock = context->block_count == 0;
-
-	if ((context->block_count != 0) && (!gif_read (context, buf, context->block_count))) {
-		/*g_message (_("GIF: error in reading DataBlock\n"));*/
-		return -1;
-	}
-
-	return context->block_count;
-}
-
-
-static void
-gif_set_lzw_fill_buffer (GifContext *context)
-{
-	context->block_count = 0;
-	context->old_state = context->state;
-	context->state = GIF_LZW_FILL_BUFFER;
-}
-
-static int
-gif_lzw_fill_buffer (GifContext *context)
-{
-	gint retval;
-
-	if (context->code_done) {
-		if (context->code_curbit >= context->code_lastbit) {
-                        g_set_error_literal (context->error,
-                                             GDK_PIXBUF_ERROR,
-                                             GDK_PIXBUF_ERROR_CORRUPT_IMAGE,
-                                             _("GIF file was missing some data (perhaps it was truncated somehow?)"));
-
-			return -2;
-		}
-                /* Is this supposed to be an error or what? */
-		/* g_message ("trying to read more data after we've done stuff\n"); */
-                g_set_error (context->error,
-                             GDK_PIXBUF_ERROR,
-                             GDK_PIXBUF_ERROR_FAILED,
-                             _("Internal error in the GIF loader (%s)"),
-                             G_STRLOC);
-                
-		return -2;
-	}
-
-	if (context->code_last_byte < 2) {
-		g_set_error_literal (context->error,
-				     GDK_PIXBUF_ERROR,
-				     GDK_PIXBUF_ERROR_CORRUPT_IMAGE,
-				     _("Bad code encountered"));
-		return -2;
-	}
-
-	context->block_buf[0] = context->block_buf[context->code_last_byte - 2];
-	context->block_buf[1] = context->block_buf[context->code_last_byte - 1];
-
-	retval = get_data_block (context, &context->block_buf[2], NULL);
-
-	if (retval == -1)
-		return -1;
-
-	if (context->block_count == 0)
-		context->code_done = TRUE;
-
-	context->code_last_byte = 2 + context->block_count;
-	context->code_curbit = (context->code_curbit - context->code_lastbit) + 16;
-	context->code_lastbit = (2 + context->block_count) * 8;
-
-	context->state = context->old_state;
-	return 0;
-}
-
-static int
-get_code (GifContext *context,
-	  int   code_size)
-{
-	int i, j, ret;
-
-	if ((context->code_curbit + code_size) > context->code_lastbit){
-		gif_set_lzw_fill_buffer (context);
-		return -3;
-	}
-
-	ret = 0;
-	for (i = context->code_curbit, j = 0; j < code_size; ++i, ++j)
-		ret |= ((context->block_buf[i / 8] & (1 << (i % 8))) != 0) << j;
-
-	context->code_curbit += code_size;
-
-	return ret;
-}
-
-#define CHECK_LZW_SP() G_STMT_START {                                           \
-        if ((guchar *)context->lzw_sp >=                                        \
-            (guchar *)context->lzw_stack + sizeof (context->lzw_stack)) {       \
-                 g_set_error_literal (context->error,                           \
-                                      GDK_PIXBUF_ERROR,                         \
-                                      GDK_PIXBUF_ERROR_CORRUPT_IMAGE,           \
-                                      _("Stack overflow"));                     \
-                return -2;                                                      \
-        }                                                                       \
-} G_STMT_END
-
-static int
-lzw_read_byte (GifContext *context)
-{
-	int code, incode;
-	gint my_retval;
-	register int i;
-
-	if (context->lzw_sp > context->lzw_stack) {
-		my_retval = *--(context->lzw_sp);
-		return my_retval;
-	}
-
-	while ((code = get_code (context, context->lzw_code_size)) >= 0) {
-		if (code == context->lzw_clear_code) {
-			for (i = 0; i < context->lzw_clear_code; ++i) {
-				context->lzw_table[0][i] = 0;
-				context->lzw_table[1][i] = i;
-			}
-			for (; i < (1 << MAX_LZW_BITS); ++i)
-				context->lzw_table[0][i] = context->lzw_table[1][i] = 0;
-			context->lzw_code_size = context->lzw_set_code_size + 1;
-			context->lzw_max_code_size = 2 * context->lzw_clear_code;
-			context->lzw_max_code = context->lzw_clear_code + 2;
-			context->lzw_sp = context->lzw_stack;
-			context->lzw_oldcode = code;
-			return -3;
-		} else if (code == context->lzw_end_code) {
-			int count;
-			unsigned char buf[260];
-
-                        /*  FIXME - we should handle this case */
-                        g_set_error_literal (context->error,
-                                             GDK_PIXBUF_ERROR,
-                                             GDK_PIXBUF_ERROR_FAILED,
-                                             _("GIF image loader cannot understand this image."));
-                        return -2;
-                        
-			if (ZeroDataBlock) {
-				return -2;
-			}
-
-			while ((count = GetDataBlock (context, buf)) > 0)
-				;
-
-			if (count != 0) {
-				/*g_print (_("GIF: missing EOD in data stream (common occurence)"));*/
-				return -2;
-			}
-		}
-
-		incode = code;
-
-		if (code >= context->lzw_max_code) {
-                        CHECK_LZW_SP ();
-			*(context->lzw_sp)++ = context->lzw_firstcode;
-			code = context->lzw_oldcode;
-		}
-
-		while (code >= context->lzw_clear_code) {
-                        if (code >= (1 << MAX_LZW_BITS)) {
-                                g_set_error_literal (context->error,
-                                                     GDK_PIXBUF_ERROR,
-                                                     GDK_PIXBUF_ERROR_CORRUPT_IMAGE,
-                                                     _("Bad code encountered"));
-				return -2;
-                        }
-                        CHECK_LZW_SP ();
-			*(context->lzw_sp)++ = context->lzw_table[1][code];
-
-			if (code == context->lzw_table[0][code]) {
-                                g_set_error_literal (context->error,
-                                                     GDK_PIXBUF_ERROR,
-                                                     GDK_PIXBUF_ERROR_CORRUPT_IMAGE,
-                                                     _("Circular table entry in GIF file"));
-				return -2;
-			}
-			code = context->lzw_table[0][code];
-		}
-
-                CHECK_LZW_SP ();
-		*(context->lzw_sp)++ = context->lzw_firstcode = context->lzw_table[1][code];
-
-		if (context->lzw_oldcode != context->lzw_clear_code && (code = context->lzw_max_code) < (1 << MAX_LZW_BITS)) {
-			context->lzw_table[0][code] = context->lzw_oldcode;
-			context->lzw_table[1][code] = context->lzw_firstcode;
-			++context->lzw_max_code;
-			if ((context->lzw_max_code >= context->lzw_max_code_size) &&
-			    (context->lzw_max_code_size < (1 << MAX_LZW_BITS))) {
-				context->lzw_max_code_size *= 2;
-				++context->lzw_code_size;
-			}
-		}
-
-		context->lzw_oldcode = incode;
-
-		if (context->lzw_sp > context->lzw_stack) {
-			my_retval = *--(context->lzw_sp);
-			return my_retval;
-		}
-	}
-	return code;
-}
-
 static void
 gif_set_get_lzw (GifContext *context)
 {
@@ -955,20 +716,38 @@ gif_get_lzw (GifContext *context)
 
 	while (TRUE) {
                 guchar (*cmap)[MAXCOLORMAPSIZE];
+                guint8 block[255];
+                gint empty_block = FALSE;
+                gsize n_indexes, i;
 
                 if (context->frame_cmap_active)
                         cmap = context->frame_color_map;
                 else
                         cmap = context->global_color_map;
-                
-		v = lzw_read_byte (context);
+
+		v = get_data_block (context, block, &empty_block);
 		if (v < 0) {
 			goto finished_data;
 		}
+		if (empty_block) {
+			goto done;
+		}
+
 		bound_flag = TRUE;
 
                 g_assert (gdk_pixbuf_get_has_alpha (context->frame->pixbuf));
-                
+
+		if (context->lzw_decoder == NULL) {
+			context->lzw_decoder = lzw_decoder_new (context->lzw_set_code_size + 1);
+			context->index_buffer_length = context->frame_len * context->frame_height;
+			context->index_buffer = g_new (guint8, context->index_buffer_length);
+                }
+		n_indexes = lzw_decoder_feed (context->lzw_decoder, block, context->block_count, context->index_buffer, context->index_buffer_length);
+                context->block_count = 0;
+
+		for (i = 0; i < n_indexes; i++) {
+                v = context->index_buffer[i];
+
                 temp = dest + context->draw_ypos * gdk_pixbuf_get_rowstride (context->frame->pixbuf) + context->draw_xpos * 4;
                 *temp = cmap [0][(guchar) v];
                 *(temp+1) = cmap [1][(guchar) v];
@@ -1027,6 +806,7 @@ gif_get_lzw (GifContext *context)
 		}
 		if (context->draw_ypos >= context->frame_height)
 			break;
+		}
 	}
 
  done:
@@ -1070,6 +850,9 @@ gif_get_lzw (GifContext *context)
 	}
 
 	if (context->state == GIF_GET_NEXT_STEP) {
+		g_clear_object (&context->lzw_decoder);
+		g_clear_pointer (&context->index_buffer, g_free);
+
                 /* Will be freed with context->animation, we are just
                  * marking that we're done with it (no current frame)
                  */
@@ -1091,14 +874,12 @@ gif_set_prepare_lzw (GifContext *context)
 static int
 gif_prepare_lzw (GifContext *context)
 {
-	gint i;
-
 	if (!gif_read (context, &(context->lzw_set_code_size), 1)) {
 		/*g_message (_("GIF: EOF / read error on image data\n"));*/
 		return -1;
 	}
         
-        if (context->lzw_set_code_size > MAX_LZW_BITS) {
+        if (context->lzw_set_code_size > LZW_CODE_MAX) {
                 g_set_error_literal (context->error,
                                      GDK_PIXBUF_ERROR,
                                      GDK_PIXBUF_ERROR_CORRUPT_IMAGE,
@@ -1106,33 +887,9 @@ gif_prepare_lzw (GifContext *context)
                 return -2;
         }
 
-	context->lzw_code_size = context->lzw_set_code_size + 1;
-	context->lzw_clear_code = 1 << context->lzw_set_code_size;
-	context->lzw_end_code = context->lzw_clear_code + 1;
-	context->lzw_max_code_size = 2 * context->lzw_clear_code;
-	context->lzw_max_code = context->lzw_clear_code + 2;
-	context->lzw_oldcode = context->lzw_clear_code;
-	context->code_curbit = 0;
-	context->code_lastbit = 0;
-	/* During initialistion (in gif_lzw_fill_buffer) we substract 2 from
-	 * this value to peek into a buffer.
-	 * In order to not get a negative array index later, we set the value
-	 * to that magic 2 now.
-	 */
-	context->code_last_byte = 2;
-	context->code_done = FALSE;
-
-        g_assert (context->lzw_clear_code <= 
-                  G_N_ELEMENTS (context->lzw_table[0]));
-
-	for (i = 0; i < context->lzw_clear_code; ++i) {
-		context->lzw_table[0][i] = 0;
-		context->lzw_table[1][i] = i;
-	}
-	for (; i < (1 << MAX_LZW_BITS); ++i)
-		context->lzw_table[0][i] = context->lzw_table[1][0] = 0;
+	context->lzw_decoder = NULL;
+	context->index_buffer = NULL;
 
-	context->lzw_sp = context->lzw_stack;
 	gif_set_get_lzw (context);
 
 	return 0;
@@ -1393,11 +1150,6 @@ gif_main_loop (GifContext *context)
 			retval = gif_prepare_lzw (context);
 			break;
 
-		case GIF_LZW_FILL_BUFFER:
-                        LOG("fill_buffer\n");
-			retval = gif_lzw_fill_buffer (context);
-			break;
-
 		case GIF_GET_LZW:
                         LOG("get_lzw\n");
 			retval = gif_get_lzw (context);
diff --git a/gdk-pixbuf/lzw.c b/gdk-pixbuf/lzw.c
new file mode 100644
index 000000000..9e052a6f7
--- /dev/null
+++ b/gdk-pixbuf/lzw.c
@@ -0,0 +1,226 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 8 -*- */
+/*
+ * Copyright (C) 2018 Canonical Ltd.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "lzw.h"
+
+/* Maximum number of codes */
+#define MAX_CODES (1 << LZW_CODE_MAX)
+
+typedef struct
+{
+        /* Last index this code represents */
+        guint8 index;
+
+        /* Codeword of previous index or the EOI code if doesn't extend */
+        guint16 extends;
+} LZWCode;
+
+struct _LZWDecoder
+{
+        GObject parent_instance;
+
+        /* Initial code size */
+        int min_code_size;
+
+        /* Current code size */
+        int code_size;
+
+        /* Code table and special codes */
+        int clear_code;
+        int eoi_code;
+        LZWCode code_table[MAX_CODES];
+        int code_table_size;
+
+        /* Current code being assembled */
+        int code;
+        int code_bits;
+
+        /* Last code processed */
+        int last_code;
+};
+
+G_DEFINE_TYPE (LZWDecoder, lzw_decoder, G_TYPE_OBJECT)
+
+static void
+add_code (LZWDecoder *self,
+          int         code)
+{
+        /* Find the first index of the given code */
+        int c = code;
+        while (self->code_table[c].extends != self->eoi_code)
+                c = self->code_table[c].extends;
+
+        /* Make a new code that extends the previous code */
+        self->code_table[self->code_table_size].index = self->code_table[c].index;
+        self->code_table[self->code_table_size].extends = self->last_code;
+        self->code_table_size++;
+}
+
+static gsize
+write_indexes (LZWDecoder *self,
+               guint8     *output,
+               gsize       output_length)
+{
+        int c;
+        gsize index_count = 1, offset;
+
+        /* Ignore invalid codeword */
+        if (self->code >= self->code_table_size)
+                return 0;
+
+        /* Work out how many indexes this code represents... */
+        c = self->code;
+        while (self->code_table[c].extends != self->eoi_code) {
+                c = self->code_table[c].extends;
+                index_count++;
+        }
+
+        /* ...then write the indexes in backwards */
+        c = self->code;
+        offset = index_count - 1;
+        while (TRUE) {
+                if (offset < output_length)
+                        output[offset] = self->code_table[c].index;
+
+                if (self->code_table[c].extends == self->eoi_code)
+                        return index_count;
+
+                c = self->code_table[c].extends;
+                offset--;
+        }
+}
+
+void
+lzw_decoder_class_init (LZWDecoderClass *klass)
+{
+}
+
+void
+lzw_decoder_init (LZWDecoder *self)
+{
+}
+
+LZWDecoder *
+lzw_decoder_new (guint8 code_size)
+{
+        LZWDecoder *self;
+        int i;
+
+        self = g_object_new (lzw_decoder_get_type (), NULL);
+
+        self->min_code_size = code_size;
+        self->code_size = code_size;
+
+        /* Add special clear and end of information codes */
+        self->clear_code = 1 << (code_size - 1);
+        self->eoi_code = self->clear_code + 1;
+
+        for (i = 0; i <= self->eoi_code; i++) {
+                self->code_table[i].index = i;
+                self->code_table[i].extends = self->eoi_code;
+                self->code_table_size++;
+        }
+
+        /* Start with an empty codeword following an implicit clear codeword */
+        self->code = 0;
+        self->last_code = self->clear_code;
+
+        return self;
+}
+
+gsize
+lzw_decoder_feed (LZWDecoder *self,
+                  guint8     *input,
+                  gsize       input_length,
+                  guint8     *output,
+                  gsize       output_length)
+{
+        gsize i, n_written = 0;
+
+        g_return_val_if_fail (LZW_IS_DECODER (self), 0);
+
+        /* Ignore data after "end of information" codeword */
+        if (self->last_code == self->eoi_code)
+                return 0;
+
+        /* Processes each octet of input */
+        for (i = 0; i < input_length; i++) {
+                guint8 d = input[i];
+                int n_available;
+
+                /* Process the bits of the octet into codewords */
+                for (n_available = 8; n_available > 0; ) {
+                        int n_bits, new_bits;
+
+                        /* Extract up the the required number of bits from the octet */
+                        n_bits = MIN (self->code_size - self->code_bits, n_available);
+                        new_bits = d & ((1 << n_bits) - 1);
+                        d = d >> n_bits;
+                        n_available -= n_bits;
+
+                        /* Add the new bits to the code until we have a full codeword */
+                        self->code = new_bits << self->code_bits | self->code;
+                        self->code_bits += n_bits;
+                        if (self->code_bits < self->code_size)
+                                continue;
+
+                        /* Stop on "end of information" codeword */
+                        if (self->code == self->eoi_code) {
+                                self->last_code = self->code;
+                                return n_written;
+                        }
+
+                        /* Reset the code table on "clear" */
+                        if (self->code == self->clear_code) {
+                                self->code_table_size = self->eoi_code + 1;
+                                self->code_size = self->min_code_size;
+                        } else {
+                                /* Add a new code word if space.
+                                 * The first code after a clear is skipped */
+                                if (self->last_code != self->clear_code && self->code_table_size < MAX_CODES) {
+                                        if (self->code < self->code_table_size)
+                                                add_code (self, self->code);
+                                        else if (self->code == self->code_table_size)
+                                                add_code (self, self->last_code);
+                                        else {
+                                                /* Invalid code received - just stop here */
+                                                self->last_code = self->eoi_code;
+                                                return output_length;
+                                        }
+
+                                        /* When table is full increase code size */
+                                        if (self->code_table_size == (1 << self->code_size) && self->code_size < LZW_CODE_MAX)
+                                                self->code_size++;
+                                }
+
+                                /* Convert codeword into indexes */
+                                n_written += write_indexes (self, output + n_written, output_length - n_written);
+                        }
+
+                        self->last_code = self->code;
+                        self->code = 0;
+                        self->code_bits = 0;
+
+                        /* Out of space */
+                        if (n_written >= output_length)
+                                return output_length;
+                }
+        }
+
+        return n_written;
+}
diff --git a/gdk-pixbuf/lzw.h b/gdk-pixbuf/lzw.h
new file mode 100644
index 000000000..60e5df349
--- /dev/null
+++ b/gdk-pixbuf/lzw.h
@@ -0,0 +1,40 @@
+/*
+ * Copyright (C) 2018 Canonical Ltd.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef GDK_PIXBUF_LZW_H
+#define GDK_PIXBUF_LZW_H
+
+#include <glib-object.h>
+
+G_BEGIN_DECLS
+
+G_DECLARE_FINAL_TYPE (LZWDecoder, lzw_decoder, LZW, DECODER, GObject)
+
+/* Maximum code size in bits */
+#define LZW_CODE_MAX 12
+
+LZWDecoder *lzw_decoder_new  (guint8     code_size);
+
+gsize       lzw_decoder_feed (LZWDecoder *decoder,
+                              guint8     *input,
+                              gsize       input_length,
+                              guint8     *output,
+                              gsize       output_length);
+
+G_END_DECLS
+
+#endif
diff --git a/gdk-pixbuf/meson.build b/gdk-pixbuf/meson.build
index 7c58bef8f..8c944ba71 100644
--- a/gdk-pixbuf/meson.build
+++ b/gdk-pixbuf/meson.build
@@ -10,7 +10,7 @@ subdir('pixops')
 loaders = [
   [ 'png', [ 'io-png.c' ], enabled_loaders.contains('png') ],
   [ 'bmp', [ 'io-bmp.c' ], not native_windows_loaders ],
-  [ 'gif', [ 'io-gif.c', 'io-gif-animation.c' ], not native_windows_loaders ],
+  [ 'gif', [ 'io-gif.c', 'io-gif-animation.c', 'lzw.c' ], not native_windows_loaders ],
   [ 'ico', [ 'io-ico.c' ], not native_windows_loaders ],
   [ 'ani', [ 'io-ani.c', 'io-ani-animation.c' ] ],
   [ 'jpeg', [ 'io-jpeg.c' ], enabled_loaders.contains('jpeg') ],