gif.c

嵌入式浏览器Dillo源码

/*
 * The GIF decoder for dillo. It is responsible for decoding GIF data
 * and transferring it to the dicache.
 *
 * Adapted by Raph Levien from giftopnm.c as found in the
 * netpbm-1mar1994 release. The copyright notice for giftopnm.c
 * follows:
 */

/* +-------------------------------------------------------------------+ */
/* | Copyright 1990, 1991, 1993, David Koblas.  ([e-mail])    | */
/* |   Permission to use, copy, modify, and distribute this software   | */
/* |   and its documentation for any purpose and without fee is hereby | */
/* |   granted, provided that the above copyright notice appear in all | */
/* |   copies and that both that copyright notice and this permission  | */
/* |   notice appear in supporting documentation.  This software is    | */
/* |   provided "as is" without express or implied warranty.           | */
/* +-------------------------------------------------------------------+ */


/* Notes 13 Oct 1997 --RLL
 *
 * Today, just for the hell of it, I implemented a new decoder from
 * scratch. It's oriented around pushing bytes, while the old decoder
 * was based around reads which may suspend. There were basically
 * three motivations.
 *
 * 1. To increase the speed.
 *
 * 2. To fix some bugs I had seen, most likely due to suspension.
 *
 * 3. To make sure that the code had no buffer overruns or the like.
 *
 * 4. So that the code could be released under a freer license.
 *
 * Let's see how we did on speed. I used a large image for testing
 * (fvwm95-2.gif).
 *
 * The old decoder spent a total of about 1.04 seconds decoding the
 * image. Another .58 seconds went into Image_line, almost
 * entirely conversion from colormap to RGB.
 *
 * The new decoder spent a total of 0.46 seconds decoding the image.
 * However, the time for Image_line went up to 1.01 seconds.
 * Thus, even though the decoder seems to be about twice as fast,
 * the net gain is pretty minimal. Could this be because of cache
 * effects?
 *
 * Lessons learned: The first, which I keep learning over and over, is
 * not to try to optimize too much. It doesn't work. Just keep things
 * simple.
 *
 * Second, it seems that the colormap to RGB conversion is really a
 * significant part of the overall time. It's possible that going
 * directly to 16 bits would help, but that's optimization again :)
 */

/* todo:
 * + Make sure to handle error cases gracefully (including aborting the
 * connection, if necessary).
 */

#undef VERBOSE

#include <stdio.h>              /* for sprintf */
#include <string.h>             /* for memcpy and memmove */

#include <gtk/gtk.h>
#include "image.h"
#include "web.h"
#include "cache.h"
#include "dicache.h"
#include "prefs.h"

#define INTERLACE      0x40
#define LOCALCOLORMAP  0x80

#define LM_to_uint(a,b)   ((((guchar)b)<<8)|((guchar)a))

#define        MAXCOLORMAPSIZE         256
#define        MAX_LWZ_BITS            12


typedef struct _DilloGif {
   DilloImage *Image;
   DilloUrl *url;
   gint version;

   gint state;
   size_t Start_Ofs;
   guint Flags;

   guchar input_code_size;
   guchar *linebuf;
   gint pass;

   guint y;

   /* state for lwz_read_byte */
   gint code_size;

   /* The original GifScreen from giftopnm */
   guint Width;
   guint Height;
   size_t ColorMap_ofs;
   guint ColorResolution;
   guint NumColors;
   gint Background;
   guint spill_line_index;
#if 0
   guint AspectRatio;    /* AspectRatio (not used) */
#endif

   /* Gif89 extensions */
   gint transparent;
#if 0
   /* None are used: */
   gint delayTime;
   gint inputFlag;
   gint disposal;
#endif

   /* state for the new push-oriented decoder */
   gint packet_size;       /* The amount of the data block left to process */
   guint window;
   gint bits_in_window;
   guint last_code;        /* Last "compressed" code in the look up table */
   guint line_index;
   guchar **spill_lines;
   gint num_spill_lines_max;
   gint length[(1 << MAX_LWZ_BITS) + 1];
   gint code_and_byte[(1 << MAX_LWZ_BITS) + 1];
} DilloGif;

/* Some invariants:
 *
 * last_code <= code_mask
 *
 * code_and_byte is stored packed: (code << 8) | byte
 */


/*
 * Forward declarations
 */
static void Gif_write(DilloGif *gif, void *Buf, gint BufSize);
static void Gif_close(DilloGif *gif, CacheClient_t *Client);
static size_t Gif_process_bytes(DilloGif *gif, const guchar *buf,
                                size_t bufsize, void *Buf);
static DilloGif *Gif_new(DilloImage *Image, DilloUrl *url, gint version);
static void Gif_callback(int Op, CacheClient_t *Client);


/*
 * MIME handler for "image/gif" type
 * (Sets Gif_callback as cache-client)
 */
DwWidget *a_Gif_image(const char *Type, void *Ptr, CA_Callback_t *Call,
                      void **Data)
{
   DilloWeb *web = Ptr;
   DICacheEntry *DicEntry;

   if ( !web->Image )
      web->Image = a_Image_new(0, 0, NULL, prefs.bg_color);
      /* todo: get the backgound color from the parent widget -- Livio. */

   /* Add an extra reference to the Image (for dicache usage) */
   a_Image_ref(web->Image);

   DicEntry = a_Dicache_get_entry(web->url);
   if ( !DicEntry ) {
      /* Let's create an entry for this image... */
      DicEntry = a_Dicache_add_entry(web->url);

      /* ... and let the decoder feed it! */
      *Data = Gif_new(web->Image, DicEntry->url, DicEntry->version);
      *Call = (CA_Callback_t) Gif_callback;
   } else {
      /* Let's feed our client from the dicache */
      a_Dicache_ref(DicEntry->url, DicEntry->version);
      *Data = web->Image;
      *Call = (CA_Callback_t) a_Dicache_callback;
   }
   return DW_WIDGET (web->Image->dw);
}

/*
 * Create a new gif structure for decoding a gif into a RGB buffer
 */
static DilloGif *Gif_new(DilloImage *Image, DilloUrl *url, gint version)
{
   DilloGif *gif = g_malloc(sizeof(DilloGif));

   gif->Image = Image;
   gif->url = url;
   gif->version = version;

   gif->Flags = 0;
   gif->state = 0;
   gif->Start_Ofs = 0;
   gif->linebuf = NULL;
   gif->Background = -1;
   gif->transparent = -1;
   gif->num_spill_lines_max = 0;
   gif->spill_lines = NULL;
   gif->window = 0;
   gif->packet_size = 0;
   gif->ColorMap_ofs = 0;

   return gif;
}

/*
 * This function is a cache client, it receives data from the cache
 * and dispatches it to the appropriate gif-processing functions
 */
static void Gif_callback(int Op, CacheClient_t *Client)
{
   if ( Op )
      Gif_close(Client->CbData, Client);
   else
      Gif_write(Client->CbData, Client->Buf, Client->BufSize);
}

/*
 * Receive and process new chunks of GIF image data
 */
static void Gif_write(DilloGif *gif, void *Buf, gint BufSize)
{
   guchar *buf;
   ssize_t bufsize, bytes_consumed;

   /* Sanity checks */
   if (!Buf || !gif->Image || BufSize <= 0)
      return;

   buf = ((guchar *) Buf) + gif->Start_Ofs;
   bufsize = BufSize - gif->Start_Ofs;

#ifdef VERBOSE
   g_print("Gif_write: %d bytes\n", BufSize);
#endif

   /* Process the bytes in the input buffer. */
   bytes_consumed = Gif_process_bytes(gif, buf, bufsize, Buf);

   if (bytes_consumed < 1)
      return;
   gif->Start_Ofs += bytes_consumed;

#ifdef VERBOSE
   g_print("exit Gif_write, bufsize=%d\n", bufsize);
#endif
}

/*
 * Finish the decoding process (and free the memory)
 */
static void Gif_close(DilloGif *gif, CacheClient_t *Client)
{
   gint i;

#ifdef VERBOSE
   g_print("destroy gif %x\n", gif);
#endif

   a_Dicache_close(gif->url, gif->version, Client);

   if (gif->linebuf != NULL)
      g_free(gif->linebuf);

   if (gif->spill_lines != NULL) {
      for (i = 0; i < gif->num_spill_lines_max; i++)
         g_free(gif->spill_lines[i]);
      g_free(gif->spill_lines);
   }
   g_free(gif);
}


/* --- GIF Extensions ----------------------------------------------------- */

/*
 * This reads a sequence of GIF data blocks.. and ignores them!
 * Buf points to the first data block.
 *
 * Return Value
 * 0 = There wasn't enough bytes read yet to read the whole datablock
 * otherwise the size of the data blocks
 */
static inline size_t Gif_data_blocks(const guchar *Buf, size_t BSize)
{
   size_t Size = 0;

   if (BSize < 1)
      return 0;
   while (Buf[0]) {
      if (BSize <= (size_t)(Buf[0] + 1))
         return 0;
      Size += Buf[0] + 1;
      BSize -= Buf[0] + 1;
      Buf += Buf[0] + 1;
   }
   return Size + 1;
}

/*
 * This is a GIF extension.  We ignore it with this routine.
 * Buffer points to just after the extension label.
 *
 * Return Value
 * 0 -- block not processed
 * otherwise the size of the extension label.
 */
static inline size_t Gif_do_generic_ext(const guchar *Buf, size_t BSize)
{
   size_t Size = Buf[0] + 1, DSize;

   /* The Block size (the first byte) is supposed to be a specific size
    * for each extension... we don't check.
    */

   if (Buf[0] > BSize)
      return 0;
   DSize = Gif_data_blocks(Buf + Size, BSize - Size);
   if (!DSize)
      return 0;
   Size += DSize;
   return Size <= BSize ? Size : 0;
}

/*
 * ?
 */
static inline size_t
 Gif_do_gc_ext(DilloGif *gif, const guchar *Buf, size_t BSize)
{
   /* Graphic Control Extension */
   size_t Size = Buf[0] + 2;
   guint Flags;

   if (Size > BSize)
      return 0;
   Buf++;
   Flags = Buf[0];

   /* The packed fields */
#if 0
   gif->disposal = (Buf[0] >> 2) & 0x7;
   gif->inputFlag = (Buf[0] >> 1) & 0x1;

   /* Delay time */
   gif->delayTime = LM_to_uint(Buf[1], Buf[2]);
#endif

   /* Transparent color index, may not be valid  (unless flag is set) */
   if ((Flags & 0x1)) {
      gif->transparent = Buf[3];
   }
   return Size;
}

#define App_Ext  (0xff)
#define Cmt_Ext  (0xfe)
#define GC_Ext   (0xf9)
#define Txt_Ext  (0x01)

/*
 * ?
 * Return value:
 *    TRUE when the extension is over
 */
static size_t Gif_do_extension(DilloGif *gif, guchar Label,
                               const guchar *buf,
                               size_t BSize)
{
   switch (Label) {
   case GC_Ext:         /* Graphics extension */
      return Gif_do_gc_ext(gif, buf, BSize);

   case Cmt_Ext:                /* Comment extension */
      return Gif_data_blocks(buf, BSize);

   case Txt_Ext:                /* Plain text Extension */
      /* This extension allows (rcm thinks) the image to be rendered as text.
       */
   case App_Ext:                /* Application Extension */
   default:
      return Gif_do_generic_ext(buf, BSize);    /*Ignore Extension */
   }
}

/* --- General Image Decoder ----------------------------------------------- */
/* Here begins the new push-oriented decoder. It should be quite a bit
 * faster than the old code, which was adapted to be asynchronous from
 * David Koblas's original giftopnm code.
 */

/*
 * ?
 */
static void Gif_lwz_init(DilloGif *gif)
{
   gif->num_spill_lines_max = 1;
   gif->spill_lines = g_malloc(sizeof(guchar *) * gif->num_spill_lines_max);

   gif->spill_lines[0] = g_malloc(gif->Width);
   gif->bits_in_window = 0;

   /* First code in table = clear_code +1
    * Last code in table = first code in table
    * clear_code = (1<< input code size)
    */
   gif->last_code = (1 << gif->input_code_size) + 1;
   memset(gif->code_and_byte, 0,
          (1 + gif->last_code) * sizeof(gif->code_and_byte[0]));
   gif->code_size = gif->input_code_size + 1;
   gif->line_index = 0;
}

/*
 * Send the image line to the dicache, also handling the interlacing.
 */
static void Gif_emit_line(DilloGif *gif, const guchar *linebuf)
{
   a_Dicache_write(gif->Image, gif->url, gif->version, linebuf, 0, gif->y);
   if (gif->Flags & INTERLACE) {
      switch (gif->pass) {
      case 0:
      case 1:
         gif->y += 8;
         break;
      case 2:
         gif->y += 4;
         break;
      case 3:
         gif->y += 2;
         break;
      }
      if (gif->y >= gif->Height) {
         gif->pass++;
         switch (gif->pass) {
         case 1:
            gif->y = 4;
            break;
         case 2:
            gif->y = 2;
            break;
         case 3:
            gif->y = 1;
            break;
         default:
            /* arriving here is an error in the input image. */
            gif->y = 0;
            break;
         }
      }
   } else {
      if (gif->y < gif->Height)
         gif->y++;
   }
}

/*
 * I apologize for the large size of this routine and the goto error
 * construct - I almost _never_ do that. I offer the excuse of
 * optimizing for speed.
 *
 * RCM -- busted these down into smaller subroutines... still very hard to
 * read.
 */


/*
 * Decode the packetized lwz bytes
 */
static void Gif_literal(DilloGif *gif, guint code)
{
   gif->linebuf[gif->line_index++] = code;
   if (gif->line_index >= gif->Width) {
      Gif_emit_line(gif, gif->linebuf);
      gif->line_index = 0;
   }
   gif->length[gif->last_code + 1] = 2;
   gif->code_and_byte[gif->last_code + 1] = (code << 8);
   gif->code_and_byte[gif->last_code] |= code;
}

/*
 * ?
 */
/* Profiling reveals over half the GIF time is spent here: */
static void Gif_sequence(DilloGif *gif, guint code)
{
   guint o_index, o_size, orig_code;
   guchar *obuf = NULL;
   guint sequence_length = gif->length[code];
   guint line_index = gif->line_index;
   gint num_spill_lines;
   gint spill_line_index = gif->spill_line_index;
   guchar *last_byte_ptr;

   gif->length[gif->last_code + 1] = sequence_length + 1;
   gif->code_and_byte[gif->last_code + 1] = (code << 8);

   /* We're going to traverse the sequence backwards. Thus,
    * we need to allocate spill lines if the sequence won't
    * fit entirely within the present scan line. */
   if (line_index + sequence_length <= gif->Width) {
      num_spill_lines = 0;
      obuf = gif->linebuf;
      o_index = line_index + sequence_length;
      o_size = sequence_length - 1;
   } else {
      num_spill_lines = (line_index + sequence_length - 1) /
          gif->Width;
      o_index = (line_index + sequence_length - 1) % gif->Width + 1;
      if (num_spill_lines > gif->num_spill_lines_max) {
         /* Allocate more spill lines. */
         spill_line_index = gif->num_spill_lines_max;
         gif->num_spill_lines_max = num_spill_lines << 1;
         gif->spill_lines = g_realloc(gif->spill_lines,
                                      gif->num_spill_lines_max *
                                      sizeof(guchar *));

         for (; spill_line_index < gif->num_spill_lines_max;
              spill_line_index++)
            gif->spill_lines[spill_line_index] =
                g_malloc(gif->Width);
      }
      spill_line_index = num_spill_lines - 1;
      obuf = gif->spill_lines[spill_line_index];
      o_size = o_index;
   }
   gif->line_index = o_index;   /* for afterwards */