From b88f1ce91a610a4e491a4ad6352183791e78afac Mon Sep 17 00:00:00 2001 From: Robert Ancell Date: Fri, 7 Dec 2018 23:41:59 +1300 Subject: gif: Replace old LZW decoder with a stand-alone decoder --- gdk-pixbuf/io-gif.c | 312 +++++-------------------------------------------- gdk-pixbuf/lzw.c | 226 +++++++++++++++++++++++++++++++++++ gdk-pixbuf/lzw.h | 40 +++++++ gdk-pixbuf/meson.build | 2 +- 4 files changed, 299 insertions(+), 281 deletions(-) create mode 100644 gdk-pixbuf/lzw.c create mode 100644 gdk-pixbuf/lzw.h (limited to 'gdk-pixbuf') 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 #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 . + */ + +#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 . + */ + +#ifndef GDK_PIXBUF_LZW_H +#define GDK_PIXBUF_LZW_H + +#include + +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') ], -- cgit v1.2.1