Back to index

tetex-bin  3.0
gd_gif_out.c
Go to the documentation of this file.
00001 #include <stdio.h>
00002 #include <math.h>
00003 #include <string.h>
00004 #include <stdlib.h>
00005 #include "gd.h"
00006 #include "gdhelpers.h"
00007 
00008 /* Code drawn from ppmtogif.c, from the pbmplus package
00009 **
00010 ** Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>. A
00011 ** Lempel-Zim compression based on "compress".
00012 **
00013 ** Modified by Marcel Wijkstra <wijkstra@fwi.uva.nl>
00014 **
00015 ** Copyright (C) 1989 by Jef Poskanzer.
00016 **
00017 ** Permission to use, copy, modify, and distribute this software and its
00018 ** documentation for any purpose and without fee is hereby granted, provided
00019 ** that the above copyright notice appear in all copies and that both that
00020 ** copyright notice and this permission notice appear in supporting
00021 ** documentation.  This software is provided "as is" without express or
00022 ** implied warranty.
00023 **
00024 ** The Graphics Interchange Format(c) is the Copyright property of
00025 ** CompuServe Incorporated.  GIF(sm) is a Service Mark property of
00026 ** CompuServe Incorporated.
00027 */
00028 
00029 /*
00030  * a code_int must be able to hold 2**GIFBITS values of type int, and also -1
00031  */
00032 typedef int             code_int;
00033 
00034 #ifdef SIGNED_COMPARE_SLOW
00035 typedef unsigned long int count_int;
00036 typedef unsigned short int count_short;
00037 #else /*SIGNED_COMPARE_SLOW*/
00038 typedef long int          count_int;
00039 #endif /*SIGNED_COMPARE_SLOW*/
00040 
00041 /* 2.0.28: threadsafe */
00042 
00043 #define maxbits GIFBITS
00044 
00045 /* should NEVER generate this code */
00046 #define maxmaxcode ((code_int)1 << GIFBITS)
00047 
00048 #define HSIZE  5003            /* 80% occupancy */
00049 #define hsize HSIZE            /* Apparently invariant, left over from 
00050                                    compress */
00051 
00052 typedef struct {
00053        int Width, Height;
00054        int curx, cury;
00055        long CountDown;
00056        int Pass;
00057        int Interlace;
00058         int n_bits;                        /* number of bits/code */
00059         code_int maxcode;                  /* maximum code, given n_bits */
00060         count_int htab [HSIZE];
00061         unsigned short codetab [HSIZE];
00062        code_int free_ent;                  /* first unused entry */
00063        /*
00064         * block compression parameters -- after all codes are used up,
00065         * and compression rate changes, start over.
00066         */
00067        int clear_flg;
00068        int offset;
00069        long int in_count;            /* length of input */
00070        long int out_count;           /* # of codes output (for debugging) */
00071 
00072        int g_init_bits;
00073        gdIOCtx * g_outfile;
00074 
00075        int ClearCode;
00076        int EOFCode;
00077        unsigned long cur_accum;
00078        int cur_bits;
00079         /*
00080          * Number of characters so far in this 'packet'
00081          */
00082         int a_count;
00083         /*
00084          * Define the storage for the packet accumulator
00085          */
00086         char accum[ 256 ];
00087 } GifCtx;
00088 
00089 static int gifPutWord(int w, gdIOCtx *out);
00090 static int colorstobpp(int colors);
00091 static void BumpPixel (GifCtx *ctx);
00092 static int GIFNextPixel (gdImagePtr im, GifCtx *ctx);
00093 static void GIFEncode (gdIOCtxPtr fp, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im);
00094 static void GIFAnimEncode (gdIOCtxPtr fp, int IWidth, int IHeight, int LeftOfs, int TopOfs, int GInterlace, int Transparent, int Delay, int Disposal, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im);
00095 static void compress (int init_bits, gdIOCtx *outfile, gdImagePtr im, GifCtx *ctx);
00096 static void output (code_int code, GifCtx *ctx);
00097 static void cl_block (GifCtx *ctx);
00098 static void cl_hash (register count_int chsize, GifCtx *ctx);
00099 static void char_init (GifCtx *ctx);
00100 static void char_out (int c, GifCtx *ctx);
00101 static void flush_char (GifCtx *ctx);
00102 BGD_DECLARE(void *) gdImageGifPtr (gdImagePtr im, int *size)
00103 {
00104   void *rv;
00105   gdIOCtx *out = gdNewDynamicCtx (2048, NULL);
00106   gdImageGifCtx (im, out);
00107   rv = gdDPExtractData (out, size);
00108   out->gd_free (out);
00109   return rv;
00110 }
00111 
00112 BGD_DECLARE(void) gdImageGif (gdImagePtr im, FILE * outFile)
00113 {
00114   gdIOCtx *out = gdNewFileCtx (outFile);
00115   gdImageGifCtx (im, out);
00116   out->gd_free (out);
00117 }
00118 
00119 BGD_DECLARE(void) gdImageGifCtx(gdImagePtr im, gdIOCtxPtr out)
00120 {
00121        gdImagePtr pim = 0, tim = im;
00122        int interlace, transparent, BitsPerPixel;
00123        interlace = im->interlace;
00124        transparent = im->transparent;
00125        if (im->trueColor) {
00126               /* Expensive, but the only way that produces an
00127                      acceptable result: mix down to a palette
00128                      based temporary image. */
00129               pim = gdImageCreatePaletteFromTrueColor(im, 1, 256);
00130               if (!pim) {
00131                      return;
00132               }
00133               tim = pim; 
00134        }
00135        BitsPerPixel = colorstobpp(tim->colorsTotal);
00136        /* All set, let's do it. */
00137        GIFEncode(
00138               out, tim->sx, tim->sy, interlace, 0, transparent, BitsPerPixel,
00139               tim->red, tim->green, tim->blue, tim);
00140        if (pim) {
00141               /* Destroy palette based temporary image. */
00142               gdImageDestroy(      pim);
00143        }
00144 }
00145 
00146 BGD_DECLARE(void *) gdImageGifAnimBeginPtr (gdImagePtr im, int *size, int GlobalCM, int Loops)
00147 {
00148   void *rv;
00149   gdIOCtx *out = gdNewDynamicCtx (2048, NULL);
00150   gdImageGifAnimBeginCtx(im, out, GlobalCM, Loops);
00151   rv = gdDPExtractData (out, size);
00152   out->gd_free (out);
00153   return rv;
00154 }
00155 
00156 BGD_DECLARE(void) gdImageGifAnimBegin (gdImagePtr im, FILE *outFile, int GlobalCM, int Loops)
00157 {
00158   gdIOCtx *out = gdNewFileCtx (outFile);
00159   gdImageGifAnimBeginCtx (im, out, GlobalCM, Loops);
00160   out->gd_free (out);
00161 }
00162 
00163 BGD_DECLARE(void) gdImageGifAnimBeginCtx(gdImagePtr im, gdIOCtxPtr out, int GlobalCM, int Loops)
00164 {
00165        int B;
00166        int RWidth, RHeight;
00167        int Resolution;
00168        int ColorMapSize;
00169        int BitsPerPixel;
00170        int Background = 0;
00171        int i;
00172 
00173        /* Default is to use global color map */
00174        if (GlobalCM < 0) GlobalCM = 1;
00175 
00176        BitsPerPixel = colorstobpp(im->colorsTotal);
00177         ColorMapSize = 1 << BitsPerPixel;
00178 
00179         RWidth = im->sx;
00180         RHeight = im->sy;
00181 
00182         Resolution = BitsPerPixel;
00183 
00184         /*
00185          * Write the Magic header
00186          */
00187         gdPutBuf("GIF89a", 6, out );
00188 
00189         /*
00190          * Write out the screen width and height
00191          */
00192         gifPutWord( RWidth, out );
00193         gifPutWord( RHeight, out );
00194 
00195         /*
00196          * Indicate that there is a global colour map
00197          */
00198         B = GlobalCM ? 0x80 : 0;
00199 
00200         /*
00201          * OR in the resolution
00202          */
00203         B |= (Resolution - 1) << 5;
00204 
00205         /*
00206          * OR in the Bits per Pixel
00207          */
00208         B |= (BitsPerPixel - 1);
00209 
00210         /*
00211          * Write it out
00212          */
00213         gdPutC( B, out );
00214 
00215         /*
00216          * Write out the Background colour
00217          */
00218         gdPutC( Background, out );
00219 
00220         /*
00221          * Byte of 0's (future expansion)
00222          */
00223         gdPutC( 0, out );
00224 
00225         /*
00226          * Write out the Global Colour Map
00227          */
00228        if (GlobalCM)
00229               for( i=0; i<ColorMapSize; ++i ) {
00230                      gdPutC( im->red[i], out );
00231                      gdPutC( im->green[i], out );
00232                      gdPutC( im->blue[i], out );
00233               }
00234 
00235        if (Loops >= 0) {
00236               gdPutBuf( "!\377\13NETSCAPE2.0\3\1", 16, out );
00237               gifPutWord( Loops, out );
00238               gdPutC( 0, out );
00239        }
00240 }
00241 
00242 BGD_DECLARE(void *) gdImageGifAnimAddPtr (gdImagePtr im, int *size, int LocalCM, int LeftOfs, int TopOfs, int Delay, int Disposal, gdImagePtr previm)
00243 {
00244   void *rv;
00245   gdIOCtx *out = gdNewDynamicCtx (2048, NULL);
00246   gdImageGifAnimAddCtx(im, out, LocalCM, LeftOfs, TopOfs, Delay, Disposal, previm);
00247   rv = gdDPExtractData (out, size);
00248   out->gd_free (out);
00249   return rv;
00250 }
00251 
00252 BGD_DECLARE(void) gdImageGifAnimAdd (gdImagePtr im, FILE * outFile, int LocalCM, int LeftOfs, int TopOfs, int Delay, int Disposal, gdImagePtr previm)
00253 {
00254   gdIOCtx *out = gdNewFileCtx (outFile);
00255   gdImageGifAnimAddCtx (im, out, LocalCM, LeftOfs, TopOfs, Delay, Disposal, previm);
00256   out->gd_free (out);
00257 }
00258 
00259 static int
00260 comparewithmap (gdImagePtr im1, gdImagePtr im2, int c1, int c2, int *colorMap)
00261 {
00262        if (!colorMap)
00263               return c1 == c2;
00264        if (-2 != colorMap[c1])
00265               return colorMap[c1] == c2;
00266        return (colorMap[c1] = gdImageColorExactAlpha (im2, im1->red[c1], im1->green[c1], im1->blue[c1], im1->alpha[c1]))
00267               == c2;
00268 }
00269 
00270 BGD_DECLARE(void) gdImageGifAnimAddCtx(gdImagePtr im, gdIOCtxPtr out, int LocalCM, int LeftOfs, int TopOfs, int Delay, int Disposal, gdImagePtr previm)
00271 {
00272        gdImagePtr pim = 0, tim = im;
00273        int interlace, transparent, BitsPerPixel;
00274        interlace = im->interlace;
00275        transparent = im->transparent;
00276 
00277        /* Default is no local color map */
00278        if (LocalCM < 0) LocalCM = 0;
00279        if (im->trueColor) {
00280               /* Expensive, but the only way that produces an
00281                      acceptable result: mix down to a palette
00282                      based temporary image. */
00283               pim = gdImageCreatePaletteFromTrueColor(im, 1, 256);
00284               if (!pim) {
00285                      return;
00286               }
00287               tim = pim; 
00288        }
00289        if (previm) {
00290               /* create optimized animation.  Compare this image to
00291                  the previous image and crop the temporary copy of
00292                  current image to include only changed rectangular
00293                  area.  Also replace unchanged pixels inside this
00294                  area with transparent color.  Transparent color
00295                  needs to be already allocated!
00296                  Preconditions:
00297                  TopOfs, LeftOfs are assumed 0
00298 
00299                  Images should be of same size.  If not, a temporary
00300                  copy is made with the same size as previous image.
00301                  
00302               */
00303               gdImagePtr prev_pim = 0, prev_tim = previm;
00304               int x, y;
00305               int min_x = 0;
00306               int min_y = tim->sy;
00307               int max_x = 0;
00308               int max_y = 0;
00309               int colorMap[256];
00310 
00311               if (previm->trueColor) {
00312                      prev_pim = gdImageCreatePaletteFromTrueColor(previm, 1, 256);
00313                      if (!prev_pim) {
00314                             return;
00315                      }
00316                      prev_tim = prev_pim; 
00317               }
00318               for (x = 0; x < 256; ++x)
00319                      colorMap[x] = -2;
00320 
00321               /* First find bounding box of changed areas. */
00322               /* first find the top changed row */
00323               for (y = 0; y < tim->sy; ++y)
00324                      for (x = 0; x < tim->sx; ++x)
00325                             if (!comparewithmap(prev_tim, tim,
00326                                               prev_tim->pixels[y][x],
00327                                               tim->pixels[y][x],
00328                                               colorMap)) {
00329                                    min_y = max_y = y;
00330                                    min_x = max_x = x;
00331                                    goto break_top;
00332                             }
00333        break_top:
00334               if (tim->sy == min_y) {
00335                      /* No changes in this frame!! Encode empty image. */
00336                      transparent = 0;
00337                      min_x = min_y = 1;
00338                      max_x = max_y = 0;
00339               } else {
00340                      /* Then the bottom row */
00341                      for (y = tim->sy - 1; y > min_y; --y)
00342                             for (x = 0; x < tim->sx; ++x)
00343                                    if (!comparewithmap
00344                                        (prev_tim, tim,
00345                                         prev_tim->pixels[y][x],
00346                                         tim->pixels[y][x],
00347                                         colorMap)) {
00348                                           max_y = y;
00349                                           if (x < min_x) min_x = x;
00350                                           if (x > max_x) max_x = x;
00351                                           goto break_bot;
00352                                    }
00353               break_bot:
00354                      /* left side */
00355                      for (x = 0; x < min_x; ++x)
00356                             for (y = min_y; y <= max_y; ++y)
00357                                    if (!comparewithmap
00358                                        (prev_tim, tim,
00359                                         prev_tim->pixels[y][x],
00360                                         tim->pixels[y][x],
00361                                         colorMap)) {
00362                                           min_x = x;
00363                                           goto break_left;
00364                                    }
00365               break_left:
00366                      /* right side */
00367                      for (x = tim->sx-1; x > max_x; --x)
00368                             for (y = min_y; y <= max_y; ++y)
00369                                    if (!comparewithmap
00370                                        (prev_tim, tim,
00371                                         prev_tim->pixels[y][x],
00372                                         tim->pixels[y][x],
00373                                         colorMap)) {
00374                                           max_x = x;
00375                                           goto break_right;
00376                                    }
00377               break_right:
00378                      ;
00379               }
00380 
00381               LeftOfs = min_x;
00382               TopOfs = min_y;
00383               Disposal = 1;
00384 
00385               /* Make a copy of the image with the new offsets.
00386                  But only if necessary. */
00387               if (min_x != 0 || max_x != tim->sx-1
00388                   || min_y != 0 || max_y != tim->sy-1
00389                   || transparent >= 0) {
00390                      gdImagePtr pim2
00391                             = gdImageCreate(max_x-min_x+1, max_y-min_y+1);
00392                      if (!pim2) {
00393                             if (prev_pim)
00394                                    gdImageDestroy (prev_pim);
00395                             goto fail_end;
00396                      }
00397                      gdImagePaletteCopy (pim2, LocalCM ? tim : prev_tim);
00398                      gdImageCopy (pim2, tim, 0, 0, min_x, min_y,
00399                                  max_x-min_x+1, max_y-min_y+1);
00400                      if (pim)
00401                             gdImageDestroy (pim);
00402                      tim = pim = pim2;
00403               }
00404 
00405               /* now let's compare pixels for transparent
00406                  optimization.  But only if transparent is set. */
00407               if (transparent >= 0) {
00408                      for (y = 0; y < tim->sy; ++y)
00409                             for (x = 0; x < tim->sx; ++x)
00410                                    if (comparewithmap
00411                                        (prev_tim, tim,
00412                                         prev_tim->pixels[min_y+y][min_x+x],
00413                                         tim->pixels[y][x], 0)) {
00414                                           gdImageSetPixel (tim, x, y,
00415                                                          transparent);
00416                                           break;
00417                                    }
00418               }
00419               if (prev_pim)
00420                      gdImageDestroy (prev_pim);
00421        }
00422        BitsPerPixel = colorstobpp(tim->colorsTotal);
00423        /* All set, let's do it. */
00424        GIFAnimEncode(
00425               out, tim->sx, tim->sy, LeftOfs, TopOfs, interlace, transparent,
00426               Delay, Disposal, BitsPerPixel,
00427               LocalCM ? tim->red : 0, tim->green, tim->blue, tim);
00428  fail_end:
00429        if (pim) {
00430               /* Destroy palette based temporary image. */
00431               gdImageDestroy(      pim);
00432        }
00433 }
00434 
00435 BGD_DECLARE(void) gdImageGifAnimEnd(FILE *outFile)
00436 {
00437 #if 1
00438   putc (';', outFile);
00439 #else
00440   gdIOCtx *out = gdNewFileCtx (outFile);
00441   gdImageGifAnimEndCtx (out);
00442   out->gd_free (out);
00443 #endif
00444 }
00445 
00446 BGD_DECLARE(void *) gdImageGifAnimEndPtr (int *size)
00447 {
00448   char *rv = (char *) gdMalloc (1);
00449   *rv = ';';
00450   *size = 1;
00451   return (void *)rv;
00452 }
00453 
00454 BGD_DECLARE(void) gdImageGifAnimEndCtx(gdIOCtx *out)
00455 {
00456        /*
00457         * Write the GIF file terminator
00458         */
00459        gdPutC( ';', out );
00460 }
00461 
00462 static int
00463 colorstobpp(int colors)
00464 {
00465     int bpp = 0;
00466 
00467     if ( colors <= 2 )
00468         bpp = 1;
00469     else if ( colors <= 4 )
00470         bpp = 2;
00471     else if ( colors <= 8 )
00472         bpp = 3;
00473     else if ( colors <= 16 )
00474         bpp = 4;
00475     else if ( colors <= 32 )
00476         bpp = 5;
00477     else if ( colors <= 64 )
00478         bpp = 6;
00479     else if ( colors <= 128 )
00480         bpp = 7;
00481     else if ( colors <= 256 )
00482         bpp = 8;
00483     return bpp;
00484     }
00485 
00486 /*****************************************************************************
00487  *
00488  * GIFENCODE.C    - GIF Image compression interface
00489  *
00490  * GIFEncode( FName, GHeight, GWidth, GInterlace, Background, Transparent,
00491  *            BitsPerPixel, Red, Green, Blue, gdImagePtr )
00492  *
00493  *****************************************************************************/
00494 
00495 #define TRUE 1
00496 #define FALSE 0
00497 /*
00498  * Bump the 'curx' and 'cury' to point to the next pixel
00499  */
00500 static void
00501 BumpPixel(GifCtx *ctx)
00502 {
00503         /*
00504          * Bump the current X position
00505          */
00506         ++(ctx->curx);
00507 
00508         /*
00509          * If we are at the end of a scan line, set curx back to the beginning
00510          * If we are interlaced, bump the cury to the appropriate spot,
00511          * otherwise, just increment it.
00512          */
00513         if( ctx->curx == ctx->Width ) {
00514                 ctx->curx = 0;
00515 
00516                 if( !ctx->Interlace )
00517                         ++(ctx->cury);
00518                 else {
00519                      switch( ctx->Pass ) {
00520 
00521                        case 0:
00522                           ctx->cury += 8;
00523                           if( ctx->cury >= ctx->Height ) {
00524                                 ++(ctx->Pass);
00525                                 ctx->cury = 4;
00526                           }
00527                           break;
00528 
00529                        case 1:
00530                           ctx->cury += 8;
00531                           if( ctx->cury >= ctx->Height ) {
00532                                 ++(ctx->Pass);
00533                                 ctx->cury = 2;
00534                           }
00535                           break;
00536 
00537                        case 2:
00538                           ctx->cury += 4;
00539                           if( ctx->cury >= ctx->Height ) {
00540                              ++(ctx->Pass);
00541                              ctx->cury = 1;
00542                           }
00543                           break;
00544 
00545                        case 3:
00546                           ctx->cury += 2;
00547                           break;
00548                         }
00549                 }
00550         }
00551 }
00552 
00553 /*
00554  * Return the next pixel from the image
00555  */
00556 static int
00557 GIFNextPixel(gdImagePtr im, GifCtx *ctx)
00558 {
00559         int r;
00560 
00561         if( ctx->CountDown == 0 )
00562                 return EOF;
00563 
00564         --(ctx->CountDown);
00565 
00566         r = gdImageGetPixel(im, ctx->curx, ctx->cury);
00567 
00568         BumpPixel(ctx);
00569 
00570         return r;
00571 }
00572 
00573 /* public */
00574 
00575 static void
00576 GIFEncode(gdIOCtxPtr fp, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im)
00577 {
00578         int B;
00579         int RWidth, RHeight;
00580         int LeftOfs, TopOfs;
00581         int Resolution;
00582         int ColorMapSize;
00583         int InitCodeSize;
00584         int i;
00585        GifCtx ctx;
00586         ctx.Interlace = GInterlace;
00587        ctx.in_count = 1;
00588        memset(&ctx, 0, sizeof(ctx));
00589         ColorMapSize = 1 << BitsPerPixel;
00590 
00591         RWidth = ctx.Width = GWidth;
00592         RHeight = ctx.Height = GHeight;
00593         LeftOfs = TopOfs = 0;
00594 
00595         Resolution = BitsPerPixel;
00596 
00597         /*
00598          * Calculate number of bits we are expecting
00599          */
00600         ctx.CountDown = (long)ctx.Width * (long)ctx.Height;
00601 
00602         /*
00603          * Indicate which pass we are on (if interlace)
00604          */
00605         ctx.Pass = 0;
00606 
00607         /*
00608          * The initial code size
00609          */
00610         if( BitsPerPixel <= 1 )
00611                 InitCodeSize = 2;
00612         else
00613                 InitCodeSize = BitsPerPixel;
00614 
00615         /*
00616          * Set up the current x and y position
00617          */
00618         ctx.curx = ctx.cury = 0;
00619 
00620         /*
00621          * Write the Magic header
00622          */
00623         gdPutBuf(Transparent < 0 ? "GIF87a" : "GIF89a", 6, fp );
00624 
00625         /*
00626          * Write out the screen width and height
00627          */
00628         gifPutWord( RWidth, fp );
00629         gifPutWord( RHeight, fp );
00630 
00631         /*
00632          * Indicate that there is a global colour map
00633          */
00634         B = 0x80;       /* Yes, there is a color map */
00635 
00636         /*
00637          * OR in the resolution
00638          */
00639         B |= (Resolution - 1) << 5;
00640 
00641         /*
00642          * OR in the Bits per Pixel
00643          */
00644         B |= (BitsPerPixel - 1);
00645 
00646         /*
00647          * Write it out
00648          */
00649         gdPutC( B, fp );
00650 
00651         /*
00652          * Write out the Background colour
00653          */
00654         gdPutC( Background, fp );
00655 
00656         /*
00657          * Byte of 0's (future expansion)
00658          */
00659         gdPutC( 0, fp );
00660 
00661         /*
00662          * Write out the Global Colour Map
00663          */
00664         for( i=0; i<ColorMapSize; ++i ) {
00665                 gdPutC( Red[i], fp );
00666                 gdPutC( Green[i], fp );
00667                 gdPutC( Blue[i], fp );
00668         }
00669 
00670        /*
00671         * Write out extension for transparent colour index, if necessary.
00672         */
00673        if ( Transparent >= 0 ) {
00674            gdPutC( '!', fp );
00675            gdPutC( 0xf9, fp );
00676            gdPutC( 4, fp );
00677            gdPutC( 1, fp );
00678            gdPutC( 0, fp );
00679            gdPutC( 0, fp );
00680            gdPutC( (unsigned char) Transparent, fp );
00681            gdPutC( 0, fp );
00682        }
00683 
00684         /*
00685          * Write an Image separator
00686          */
00687         gdPutC( ',', fp );
00688 
00689         /*
00690          * Write the Image header
00691          */
00692 
00693         gifPutWord( LeftOfs, fp );
00694         gifPutWord( TopOfs, fp );
00695         gifPutWord( ctx.Width, fp );
00696         gifPutWord( ctx.Height, fp );
00697 
00698         /*
00699          * Write out whether or not the image is interlaced
00700          */
00701         if( ctx.Interlace )
00702                 gdPutC( 0x40, fp );
00703         else
00704                 gdPutC( 0x00, fp );
00705 
00706         /*
00707          * Write out the initial code size
00708          */
00709         gdPutC( InitCodeSize, fp );
00710 
00711         /*
00712          * Go and actually compress the data
00713          */
00714         compress( InitCodeSize+1, fp, im, &ctx );
00715 
00716         /*
00717          * Write out a Zero-length packet (to end the series)
00718          */
00719         gdPutC( 0, fp );
00720 
00721         /*
00722          * Write the GIF file terminator
00723          */
00724         gdPutC( ';', fp );
00725 }
00726 
00727 static void
00728 GIFAnimEncode(gdIOCtxPtr fp, int IWidth, int IHeight, int LeftOfs, int TopOfs, int GInterlace, int Transparent, int Delay, int Disposal, int BitsPerPixel, int *Red, int *Green, int *Blue, gdImagePtr im)
00729 {
00730        int B;
00731         int ColorMapSize;
00732         int InitCodeSize;
00733         int i;
00734        GifCtx ctx;
00735         ctx.Interlace = GInterlace;
00736        ctx.in_count = 1;
00737        memset(&ctx, 0, sizeof(ctx));
00738         ColorMapSize = 1 << BitsPerPixel;
00739 
00740        if (LeftOfs < 0) LeftOfs = 0;
00741        if (TopOfs < 0) TopOfs = 0;
00742        if (Delay < 0) Delay = 100;
00743        if (Disposal < 0) Disposal = 1;
00744 
00745        ctx.Width = IWidth;
00746         ctx.Height = IHeight;
00747 
00748         /*
00749          * Calculate number of bits we are expecting
00750          */
00751         ctx.CountDown = (long)ctx.Width * (long)ctx.Height;
00752 
00753         /*
00754          * Indicate which pass we are on (if interlace)
00755          */
00756         ctx.Pass = 0;
00757 
00758         /*
00759          * The initial code size
00760          */
00761         if( BitsPerPixel <= 1 )
00762                 InitCodeSize = 2;
00763         else
00764                 InitCodeSize = BitsPerPixel;
00765 
00766         /*
00767          * Set up the current x and y position
00768          */
00769         ctx.curx = ctx.cury = 0;
00770 
00771        /*
00772         * Write out extension for image animation and looping
00773         */
00774        gdPutC( '!', fp );
00775        gdPutC( 0xf9, fp );
00776        gdPutC( 4, fp );
00777        gdPutC( (Transparent >= 0 ? 1 : 0)
00778               | (Disposal << 2), fp );
00779        gdPutC( (unsigned char)(Delay & 255), fp );
00780        gdPutC( (unsigned char)((Delay >> 8) & 255), fp );
00781        gdPutC( (unsigned char) Transparent, fp );
00782        gdPutC( 0, fp );
00783 
00784        /*
00785         * Write an Image separator
00786         */
00787        gdPutC( ',', fp );
00788 
00789         /*
00790          * Write out the Image header
00791          */
00792         gifPutWord( LeftOfs, fp );
00793         gifPutWord( TopOfs, fp );
00794         gifPutWord( ctx.Width, fp );
00795         gifPutWord( ctx.Height, fp );
00796 
00797         /*
00798          * Indicate that there is a local colour map
00799          */
00800         B = (Red && Green && Blue) ? 0x80 : 0;
00801 
00802         /*
00803          * OR in the interlacing
00804          */
00805         B |= ctx.Interlace ? 0x40 : 0;
00806 
00807         /*
00808          * OR in the Bits per Pixel
00809          */
00810         B |= (Red && Green && Blue) ? (BitsPerPixel - 1) : 0;
00811 
00812         /*
00813          * Write it out
00814          */
00815         gdPutC( B, fp );
00816 
00817        /*
00818         * Write out the Local Colour Map
00819         */
00820        if (Red && Green && Blue)
00821               for( i=0; i<ColorMapSize; ++i ) {
00822                      gdPutC( Red[i], fp );
00823                      gdPutC( Green[i], fp );
00824                      gdPutC( Blue[i], fp );
00825               }
00826 
00827         /*
00828          * Write out the initial code size
00829          */
00830         gdPutC( InitCodeSize, fp );
00831 
00832         /*
00833          * Go and actually compress the data
00834          */
00835         compress( InitCodeSize+1, fp, im, &ctx );
00836 
00837         /*
00838          * Write out a Zero-length packet (to end the series)
00839          */
00840         gdPutC( 0, fp );
00841 }
00842 
00843 /***************************************************************************
00844  *
00845  *  GIFCOMPR.C       - GIF Image compression routines
00846  *
00847  *  Lempel-Ziv compression based on 'compress'.  GIF modifications by
00848  *  David Rowley (mgardi@watdcsu.waterloo.edu)
00849  *
00850  ***************************************************************************/
00851 
00852 /*
00853  * General DEFINEs
00854  */
00855 
00856 #define GIFBITS    12
00857 
00858 #ifdef NO_UCHAR
00859  typedef char   char_type;
00860 #else /*NO_UCHAR*/
00861  typedef        unsigned char   char_type;
00862 #endif /*NO_UCHAR*/
00863 
00864 /*
00865  *
00866  * GIF Image compression - modified 'compress'
00867  *
00868  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
00869  *
00870  * By Authors:  Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
00871  *              Jim McKie               (decvax!mcvax!jim)
00872  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
00873  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
00874  *              James A. Woods          (decvax!ihnp4!ames!jaw)
00875  *              Joe Orost               (decvax!vax135!petsd!joe)
00876  *
00877  */
00878 #include <ctype.h>
00879 
00880 #define ARGVAL() (*++(*argv) || (--argc && *++argv))
00881 
00882 #ifdef COMPATIBLE               /* But wrong! */
00883 # define MAXCODE(n_bits)        ((code_int) 1 << (n_bits) - 1)
00884 #else /*COMPATIBLE*/
00885 # define MAXCODE(n_bits)        (((code_int) 1 << (n_bits)) - 1)
00886 #endif /*COMPATIBLE*/
00887 
00888 #define HashTabOf(i)       ctx->htab[i]
00889 #define CodeTabOf(i)    ctx->codetab[i]
00890 
00891 
00892 /*
00893  * To save much memory, we overlay the table used by compress() with those
00894  * used by decompress().  The tab_prefix table is the same size and type
00895  * as the codetab.  The tab_suffix table needs 2**GIFBITS characters.  We
00896  * get this from the beginning of htab.  The output stack uses the rest
00897  * of htab, and contains characters.  There is plenty of room for any
00898  * possible stack (stack used to be 8000 characters).
00899  */
00900 
00901 #define tab_prefixof(i) CodeTabOf(i)
00902 #define tab_suffixof(i)        ((char_type*)(htab))[i]
00903 #define de_stack               ((char_type*)&tab_suffixof((code_int)1<<GIFBITS))
00904 
00905 /*
00906  * compress stdin to stdout
00907  *
00908  * Algorithm:  use open addressing double hashing (no chaining) on the
00909  * prefix code / next character combination.  We do a variant of Knuth's
00910  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
00911  * secondary probe.  Here, the modular division first probe is gives way
00912  * to a faster exclusive-or manipulation.  Also do block compression with
00913  * an adaptive reset, whereby the code table is cleared when the compression
00914  * ratio decreases, but after the table fills.  The variable-length output
00915  * codes are re-sized at this point, and a special CLEAR code is generated
00916  * for the decompressor.  Late addition:  construct the table according to
00917  * file size for noticeable speed improvement on small files.  Please direct
00918  * questions about this implementation to ames!jaw.
00919  */
00920 
00921 static void
00922 output(code_int code, GifCtx *ctx);
00923 
00924 static void
00925 compress(int init_bits, gdIOCtxPtr outfile, gdImagePtr im, GifCtx *ctx)
00926 {
00927     register long fcode;
00928     register code_int i /* = 0 */;
00929     register int c;
00930     register code_int ent;
00931     register code_int disp;
00932     register code_int hsize_reg;
00933     register int hshift;
00934 
00935     /*
00936      * Set up the globals:  g_init_bits - initial number of bits
00937      *                      g_outfile   - pointer to output file
00938      */
00939     ctx->g_init_bits = init_bits;
00940     ctx->g_outfile = outfile;
00941 
00942     /*
00943      * Set up the necessary values
00944      */
00945     ctx->offset = 0;
00946     ctx->out_count = 0;
00947     ctx->clear_flg = 0;
00948     ctx->in_count = 1;
00949     ctx->maxcode = MAXCODE(ctx->n_bits = ctx->g_init_bits);
00950 
00951     ctx->ClearCode = (1 << (init_bits - 1));
00952     ctx->EOFCode = ctx->ClearCode + 1;
00953     ctx->free_ent = ctx->ClearCode + 2;
00954 
00955     char_init(ctx);
00956 
00957     ent = GIFNextPixel( im, ctx );
00958 
00959     hshift = 0;
00960     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
00961         ++hshift;
00962     hshift = 8 - hshift;                /* set hash code range bound */
00963 
00964     hsize_reg = hsize;
00965     cl_hash( (count_int) hsize_reg, ctx );            /* clear hash table */
00966 
00967     output( (code_int)ctx->ClearCode, ctx );
00968 
00969 #ifdef SIGNED_COMPARE_SLOW
00970     while ( (c = GIFNextPixel( im )) != (unsigned) EOF ) {
00971 #else /*SIGNED_COMPARE_SLOW*/
00972     while ( (c = GIFNextPixel( im, ctx )) != EOF ) {  /* } */
00973 #endif /*SIGNED_COMPARE_SLOW*/
00974 
00975         ++(ctx->in_count);
00976 
00977         fcode = (long) (((long) c << maxbits) + ent);
00978         i = (((code_int)c << hshift) ^ ent);    /* xor hashing */
00979 
00980         if ( HashTabOf (i) == fcode ) {
00981             ent = CodeTabOf (i);
00982             continue;
00983         } else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
00984             goto nomatch;
00985         disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
00986         if ( i == 0 )
00987             disp = 1;
00988 probe:
00989         if ( (i -= disp) < 0 )
00990             i += hsize_reg;
00991 
00992         if ( HashTabOf (i) == fcode ) {
00993             ent = CodeTabOf (i);
00994             continue;
00995         }
00996         if ( (long)HashTabOf (i) > 0 )
00997             goto probe;
00998 nomatch:
00999         output ( (code_int) ent, ctx );
01000         ++(ctx->out_count);
01001         ent = c;
01002 #ifdef SIGNED_COMPARE_SLOW
01003         if ( (unsigned) ctx->free_ent < (unsigned) maxmaxcode) {
01004 #else /*SIGNED_COMPARE_SLOW*/
01005         if ( ctx->free_ent < maxmaxcode ) {  /* } */
01006 #endif /*SIGNED_COMPARE_SLOW*/
01007             CodeTabOf (i) = ctx->free_ent++; /* code -> hashtable */
01008             HashTabOf (i) = fcode;
01009         } else
01010                 cl_block(ctx);
01011     }
01012     /*
01013      * Put out the final code.
01014      */
01015     output( (code_int)ent, ctx );
01016     ++(ctx->out_count);
01017     output( (code_int) ctx->EOFCode, ctx );
01018 }
01019 
01020 /*****************************************************************
01021  * TAG( output )
01022  *
01023  * Output the given code.
01024  * Inputs:
01025  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
01026  *              that n_bits =< (long)wordsize - 1.
01027  * Outputs:
01028  *      Outputs code to the file.
01029  * Assumptions:
01030  *      Chars are 8 bits long.
01031  * Algorithm:
01032  *      Maintain a GIFBITS character long buffer (so that 8 codes will
01033  * fit in it exactly).  Use the VAX insv instruction to insert each
01034  * code in turn.  When the buffer fills up empty it and start over.
01035  */
01036 
01037 static unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
01038                                   0x001F, 0x003F, 0x007F, 0x00FF,
01039                                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
01040                                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
01041 
01042 static void
01043 output(code_int code, GifCtx *ctx)
01044 {
01045     ctx->cur_accum &= masks[ ctx->cur_bits ];
01046 
01047     if( ctx->cur_bits > 0 )
01048         ctx->cur_accum |= ((long)code << ctx->cur_bits);
01049     else
01050         ctx->cur_accum = code;
01051 
01052     ctx->cur_bits += ctx->n_bits;
01053 
01054     while( ctx->cur_bits >= 8 ) {
01055         char_out( (unsigned int)(ctx->cur_accum & 0xff), ctx );
01056         ctx->cur_accum >>= 8;
01057         ctx->cur_bits -= 8;
01058     }
01059 
01060     /*
01061      * If the next entry is going to be too big for the code size,
01062      * then increase it, if possible.
01063      */
01064    if ( ctx->free_ent > ctx->maxcode || ctx->clear_flg ) {
01065 
01066             if( ctx->clear_flg ) {
01067 
01068                 ctx->maxcode = MAXCODE (ctx->n_bits = ctx->g_init_bits);
01069                 ctx->clear_flg = 0;
01070 
01071             } else {
01072 
01073                 ++(ctx->n_bits);
01074                 if ( ctx->n_bits == maxbits )
01075                     ctx->maxcode = maxmaxcode;
01076                 else
01077                     ctx->maxcode = MAXCODE(ctx->n_bits);
01078             }
01079         }
01080 
01081     if( code == ctx->EOFCode ) {
01082         /*
01083          * At EOF, write the rest of the buffer.
01084          */
01085         while( ctx->cur_bits > 0 ) {
01086                 char_out( (unsigned int)(ctx->cur_accum & 0xff), ctx);
01087                 ctx->cur_accum >>= 8;
01088                 ctx->cur_bits -= 8;
01089         }
01090 
01091         flush_char(ctx);
01092 
01093     }
01094 }
01095 
01096 /*
01097  * Clear out the hash table
01098  */
01099 static void
01100 cl_block (GifCtx *ctx)             /* table clear for block compress */
01101 {
01102 
01103         cl_hash ( (count_int) hsize, ctx );
01104         ctx->free_ent = ctx->ClearCode + 2;
01105         ctx->clear_flg = 1;
01106 
01107         output( (code_int)ctx->ClearCode, ctx);
01108 }
01109 
01110 static void
01111 cl_hash(register count_int chsize, GifCtx *ctx)          /* reset code table */
01112                          
01113 {
01114 
01115         register count_int *htab_p = ctx->htab+chsize;
01116 
01117         register long i;
01118         register long m1 = -1;
01119 
01120         i = chsize - 16;
01121         do {                            /* might use Sys V memset(3) here */
01122                 *(htab_p-16) = m1;
01123                 *(htab_p-15) = m1;
01124                 *(htab_p-14) = m1;
01125                 *(htab_p-13) = m1;
01126                 *(htab_p-12) = m1;
01127                 *(htab_p-11) = m1;
01128                 *(htab_p-10) = m1;
01129                 *(htab_p-9) = m1;
01130                 *(htab_p-8) = m1;
01131                 *(htab_p-7) = m1;
01132                 *(htab_p-6) = m1;
01133                 *(htab_p-5) = m1;
01134                 *(htab_p-4) = m1;
01135                 *(htab_p-3) = m1;
01136                 *(htab_p-2) = m1;
01137                 *(htab_p-1) = m1;
01138                 htab_p -= 16;
01139         } while ((i -= 16) >= 0);
01140 
01141         for ( i += 16; i > 0; --i )
01142                 *--htab_p = m1;
01143 }
01144 
01145 /******************************************************************************
01146  *
01147  * GIF Specific routines
01148  *
01149  ******************************************************************************/
01150 
01151 /*
01152  * Set up the 'byte output' routine
01153  */
01154 static void
01155 char_init(GifCtx *ctx)
01156 {
01157         ctx->a_count = 0;
01158 }
01159 
01160 /*
01161  * Add a character to the end of the current packet, and if it is 254
01162  * characters, flush the packet to disk.
01163  */
01164 static void
01165 char_out(int c, GifCtx *ctx)
01166 {
01167         ctx->accum[ ctx->a_count++ ] = c;
01168         if( ctx->a_count >= 254 )
01169                 flush_char(ctx);
01170 }
01171 
01172 /*
01173  * Flush the packet to disk, and reset the accumulator
01174  */
01175 static void
01176 flush_char(GifCtx *ctx)
01177 {
01178         if( ctx->a_count > 0 ) {
01179                 gdPutC( ctx->a_count, ctx->g_outfile );
01180                 gdPutBuf( ctx->accum, ctx->a_count, ctx->g_outfile );
01181                 ctx->a_count = 0;
01182         }
01183 }
01184 
01185 static int gifPutWord(int w, gdIOCtx *out)
01186 {
01187        /* Byte order is little-endian */
01188        gdPutC(w & 0xFF, out);
01189        gdPutC((w >> 8) & 0xFF, out);
01190        return 0;
01191 }
01192 
01193