granicus.if.org Git - imagemagick/blob - coders/gif.c

   1 /*
   2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   3 %                                                                             %
   4 %                                                                             %
   5 %                                                                             %
   6 %                             GGGG  IIIII  FFFFF                              %
   7 %                            G        I    F                                  %
   8 %                            G  GG    I    FFF                                %
   9 %                            G   G    I    F                                  %
  10 %                             GGG   IIIII  F                                  %
  11 %                                                                             %
  12 %                                                                             %
  13 %            Read/Write Compuserv Graphics Interchange Format                 %
  14 %                                                                             %
  15 %                              Software Design                                %
  16 %                                John Cristy                                  %
  17 %                                 July 1992                                   %
  18 %                                                                             %
  19 %                                                                             %
  20 %  Copyright 1999-2011 ImageMagick Studio LLC, a non-profit organization      %
  21 %  dedicated to making software imaging solutions freely available.           %
  22 %                                                                             %
  23 %  You may not use this file except in compliance with the License.  You may  %
  24 %  obtain a copy of the License at                                            %
  25 %                                                                             %
  26 %    http://www.imagemagick.org/script/license.php                            %
  27 %                                                                             %
  28 %  Unless required by applicable law or agreed to in writing, software        %
  29 %  distributed under the License is distributed on an "AS IS" BASIS,          %
  30 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
  31 %  See the License for the specific language governing permissions and        %
  32 %  limitations under the License.                                             %
  33 %                                                                             %
  34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  35 %
  36 %
  37 */
  38 \f
  39 /*
  40   Include declarations.
  41 */
  42 #include "MagickCore/studio.h"
  43 #include "MagickCore/attribute.h"
  44 #include "MagickCore/blob.h"
  45 #include "MagickCore/blob-private.h"
  46 #include "MagickCore/cache.h"
  47 #include "MagickCore/color.h"
  48 #include "MagickCore/color-private.h"
  49 #include "MagickCore/colormap.h"
  50 #include "MagickCore/colormap-private.h"
  51 #include "MagickCore/colorspace.h"
  52 #include "MagickCore/exception.h"
  53 #include "MagickCore/exception-private.h"
  54 #include "MagickCore/image.h"
  55 #include "MagickCore/image-private.h"
  56 #include "MagickCore/list.h"
  57 #include "MagickCore/profile.h"
  58 #include "MagickCore/magick.h"
  59 #include "MagickCore/memory_.h"
  60 #include "MagickCore/monitor.h"
  61 #include "MagickCore/monitor-private.h"
  62 #include "MagickCore/option.h"
  63 #include "MagickCore/pixel.h"
  64 #include "MagickCore/pixel-accessor.h"
  65 #include "MagickCore/property.h"
  66 #include "MagickCore/quantize.h"
  67 #include "MagickCore/quantum-private.h"
  68 #include "MagickCore/static.h"
  69 #include "MagickCore/string_.h"
  70 #include "MagickCore/module.h"
  71 \f
  72 /*
  73   Define declarations.
  74 */
  75 #define MaximumLZWBits  12
  76 #define MaximumLZWCode  (1UL << MaximumLZWBits)
  77 \f
  78 /*
  79   Typdef declarations.
  80 */
  81 typedef struct _LZWCodeInfo
  82 {
  83   unsigned char
  84     buffer[280];
  85
  86   size_t
  87     count,
  88     bit;
  89
  90   MagickBooleanType
  91     eof;
  92 } LZWCodeInfo;
  93
  94 typedef struct _LZWStack
  95 {
  96   size_t
  97     *codes,
  98     *index,
  99     *top;
 100 } LZWStack;
 101
 102 typedef struct _LZWInfo
 103 {
 104   Image
 105     *image;
 106
 107   LZWStack
 108     *stack;
 109
 110   MagickBooleanType
 111     genesis;
 112
 113   size_t
 114     data_size,
 115     maximum_data_value,
 116     clear_code,
 117     end_code,
 118     bits,
 119     first_code,
 120     last_code,
 121     maximum_code,
 122     slot,
 123     *table[2];
 124
 125   LZWCodeInfo
 126     code_info;
 127 } LZWInfo;
 128 \f
 129 /*
 130   Forward declarations.
 131 */
 132 static inline int
 133   GetNextLZWCode(LZWInfo *,const size_t);
 134
 135 static MagickBooleanType
 136   WriteGIFImage(const ImageInfo *,Image *);
 137
 138 static ssize_t
 139   ReadBlobBlock(Image *,unsigned char *);
 140 \f
 141 /*
 142 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 143 %                                                                             %
 144 %                                                                             %
 145 %                                                                             %
 146 %   D e c o d e I m a g e                                                     %
 147 %                                                                             %
 148 %                                                                             %
 149 %                                                                             %
 150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 151 %
 152 %  DecodeImage uncompresses an image via GIF-coding.
 153 %
 154 %  The format of the DecodeImage method is:
 155 %
 156 %      MagickBooleanType DecodeImage(Image *image,const ssize_t opacity)
 157 %
 158 %  A description of each parameter follows:
 159 %
 160 %    o image: the address of a structure of type Image.
 161 %
 162 %    o opacity:  The colormap index associated with the transparent color.
 163 %
 164 */
 165
 166 static LZWInfo *RelinquishLZWInfo(LZWInfo *lzw_info)
 167 {
 168   if (lzw_info->table[0] != (size_t *) NULL)
 169     lzw_info->table[0]=(size_t *) RelinquishMagickMemory(
 170       lzw_info->table[0]);
 171   if (lzw_info->table[1] != (size_t *) NULL)
 172     lzw_info->table[1]=(size_t *) RelinquishMagickMemory(
 173       lzw_info->table[1]);
 174   if (lzw_info->stack != (LZWStack *) NULL)
 175     {
 176       if (lzw_info->stack->codes != (size_t *) NULL)
 177         lzw_info->stack->codes=(size_t *) RelinquishMagickMemory(
 178           lzw_info->stack->codes);
 179       lzw_info->stack=(LZWStack *) RelinquishMagickMemory(lzw_info->stack);
 180     }
 181   lzw_info=(LZWInfo *) RelinquishMagickMemory(lzw_info);
 182   return((LZWInfo *) NULL);
 183 }
 184
 185 static inline void ResetLZWInfo(LZWInfo *lzw_info)
 186 {
 187   size_t
 188     one;
 189
 190   lzw_info->bits=lzw_info->data_size+1;
 191   one=1;
 192   lzw_info->maximum_code=one << lzw_info->bits;
 193   lzw_info->slot=lzw_info->maximum_data_value+3;
 194   lzw_info->genesis=MagickTrue;
 195 }
 196
 197 static LZWInfo *AcquireLZWInfo(Image *image,const size_t data_size)
 198 {
 199   LZWInfo
 200     *lzw_info;
 201
 202   register ssize_t
 203     i;
 204
 205   size_t
 206     one;
 207
 208   lzw_info=(LZWInfo *) AcquireMagickMemory(sizeof(*lzw_info));
 209   if (lzw_info == (LZWInfo *) NULL)
 210     return((LZWInfo *) NULL);
 211   (void) ResetMagickMemory(lzw_info,0,sizeof(*lzw_info));
 212   lzw_info->image=image;
 213   lzw_info->data_size=data_size;
 214   one=1;
 215   lzw_info->maximum_data_value=(one << data_size)-1;
 216   lzw_info->clear_code=lzw_info->maximum_data_value+1;
 217   lzw_info->end_code=lzw_info->maximum_data_value+2;
 218   lzw_info->table[0]=(size_t *) AcquireQuantumMemory(MaximumLZWCode,
 219     sizeof(*lzw_info->table));
 220   lzw_info->table[1]=(size_t *) AcquireQuantumMemory(MaximumLZWCode,
 221     sizeof(*lzw_info->table));
 222   if ((lzw_info->table[0] == (size_t *) NULL) ||
 223       (lzw_info->table[1] == (size_t *) NULL))
 224     {
 225       lzw_info=RelinquishLZWInfo(lzw_info);
 226       return((LZWInfo *) NULL);
 227     }
 228   for (i=0; i <= (ssize_t) lzw_info->maximum_data_value; i++)
 229   {
 230     lzw_info->table[0][i]=0;
 231     lzw_info->table[1][i]=(size_t) i;
 232   }
 233   ResetLZWInfo(lzw_info);
 234   lzw_info->code_info.buffer[0]='\0';
 235   lzw_info->code_info.buffer[1]='\0';
 236   lzw_info->code_info.count=2;
 237   lzw_info->code_info.bit=8*lzw_info->code_info.count;
 238   lzw_info->code_info.eof=MagickFalse;
 239   lzw_info->genesis=MagickTrue;
 240   lzw_info->stack=(LZWStack *) AcquireMagickMemory(sizeof(*lzw_info->stack));
 241   if (lzw_info->stack == (LZWStack *) NULL)
 242     {
 243       lzw_info=RelinquishLZWInfo(lzw_info);
 244       return((LZWInfo *) NULL);
 245     }
 246   lzw_info->stack->codes=(size_t *) AcquireQuantumMemory(2UL*
 247     MaximumLZWCode,sizeof(*lzw_info->stack->codes));
 248   if (lzw_info->stack->codes == (size_t *) NULL)
 249     {
 250       lzw_info=RelinquishLZWInfo(lzw_info);
 251       return((LZWInfo *) NULL);
 252     }
 253   lzw_info->stack->index=lzw_info->stack->codes;
 254   lzw_info->stack->top=lzw_info->stack->codes+2*MaximumLZWCode;
 255   return(lzw_info);
 256 }
 257
 258 static inline int GetNextLZWCode(LZWInfo *lzw_info,const size_t bits)
 259 {
 260   int
 261     code;
 262
 263   register ssize_t
 264     i;
 265
 266   size_t
 267     one;
 268
 269   while (((lzw_info->code_info.bit+bits) > (8*lzw_info->code_info.count)) &&
 270          (lzw_info->code_info.eof == MagickFalse))
 271   {
 272     ssize_t
 273       count;
 274
 275     lzw_info->code_info.buffer[0]=lzw_info->code_info.buffer[
 276       lzw_info->code_info.count-2];
 277     lzw_info->code_info.buffer[1]=lzw_info->code_info.buffer[
 278       lzw_info->code_info.count-1];
 279     lzw_info->code_info.bit-=8*(lzw_info->code_info.count-2);
 280     lzw_info->code_info.count=2;
 281     count=ReadBlobBlock(lzw_info->image,&lzw_info->code_info.buffer[
 282       lzw_info->code_info.count]);
 283     if (count > 0)
 284       lzw_info->code_info.count+=count;
 285     else
 286       lzw_info->code_info.eof=MagickTrue;
 287   }
 288   if ((lzw_info->code_info.bit+bits) > (8*lzw_info->code_info.count))
 289     return(-1);
 290   code=0;
 291   one=1;
 292   for (i=0; i < (ssize_t) bits; i++)
 293   {
 294     code|=((lzw_info->code_info.buffer[lzw_info->code_info.bit/8] &
 295       (one << (lzw_info->code_info.bit % 8))) != 0) << i;
 296     lzw_info->code_info.bit++;
 297   }
 298   return(code);
 299 }
 300
 301 static inline int PopLZWStack(LZWStack *stack_info)
 302 {
 303   if (stack_info->index <= stack_info->codes)
 304     return(-1);
 305   stack_info->index--;
 306   return((int) *stack_info->index);
 307 }
 308
 309 static inline void PushLZWStack(LZWStack *stack_info,const size_t value)
 310 {
 311   if (stack_info->index >= stack_info->top)
 312     return;
 313   *stack_info->index=value;
 314   stack_info->index++;
 315 }
 316
 317 static int ReadBlobLZWByte(LZWInfo *lzw_info)
 318 {
 319   int
 320     code;
 321
 322   ssize_t
 323     count;
 324
 325   size_t
 326     one,
 327     value;
 328
 329   if (lzw_info->stack->index != lzw_info->stack->codes)
 330     return(PopLZWStack(lzw_info->stack));
 331   if (lzw_info->genesis != MagickFalse)
 332     {
 333       lzw_info->genesis=MagickFalse;
 334       do
 335       {
 336         lzw_info->first_code=(size_t) GetNextLZWCode(lzw_info,
 337           lzw_info->bits);
 338         lzw_info->last_code=lzw_info->first_code;
 339       } while (lzw_info->first_code == lzw_info->clear_code);
 340       return((int) lzw_info->first_code);
 341     }
 342   code=GetNextLZWCode(lzw_info,lzw_info->bits);
 343   if (code < 0)
 344     return(code);
 345   if ((size_t) code == lzw_info->clear_code)
 346     {
 347       ResetLZWInfo(lzw_info);
 348       return(ReadBlobLZWByte(lzw_info));
 349     }
 350   if ((size_t) code == lzw_info->end_code)
 351     return(-1);
 352   if ((size_t) code < lzw_info->slot)
 353     value=(size_t) code;
 354   else
 355     {
 356       PushLZWStack(lzw_info->stack,lzw_info->first_code);
 357       value=lzw_info->last_code;
 358     }
 359   count=0;
 360   while (value > lzw_info->maximum_data_value)
 361   {
 362     if ((size_t) count > MaximumLZWCode)
 363       return(-1);
 364     count++;
 365     if ((size_t) value > MaximumLZWCode)
 366       return(-1);
 367     PushLZWStack(lzw_info->stack,lzw_info->table[1][value]);
 368     value=lzw_info->table[0][value];
 369   }
 370   lzw_info->first_code=lzw_info->table[1][value];
 371   PushLZWStack(lzw_info->stack,lzw_info->first_code);
 372   one=1;
 373   if (lzw_info->slot < MaximumLZWCode)
 374     {
 375       lzw_info->table[0][lzw_info->slot]=lzw_info->last_code;
 376       lzw_info->table[1][lzw_info->slot]=lzw_info->first_code;
 377       lzw_info->slot++;
 378       if ((lzw_info->slot >= lzw_info->maximum_code) &&
 379           (lzw_info->bits < MaximumLZWBits))
 380         {
 381           lzw_info->bits++;
 382           lzw_info->maximum_code=one << lzw_info->bits;
 383         }
 384     }
 385   lzw_info->last_code=(size_t) code;
 386   return(PopLZWStack(lzw_info->stack));
 387 }
 388
 389 static MagickBooleanType DecodeImage(Image *image,const ssize_t opacity)
 390 {
 391   ExceptionInfo
 392     *exception;
 393
 394   int
 395     c;
 396
 397   LZWInfo
 398     *lzw_info;
 399
 400   Quantum
 401     index;
 402
 403   size_t
 404     pass;
 405
 406   ssize_t
 407     offset,
 408     y;
 409
 410   unsigned char
 411     data_size;
 412
 413   /*
 414     Allocate decoder tables.
 415   */
 416   assert(image != (Image *) NULL);
 417   assert(image->signature == MagickSignature);
 418   if (image->debug != MagickFalse)
 419     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 420   data_size=(unsigned char) ReadBlobByte(image);
 421   if (data_size > MaximumLZWBits)
 422     ThrowBinaryException(CorruptImageError,"CorruptImage",image->filename);
 423   lzw_info=AcquireLZWInfo(image,data_size);
 424   if (lzw_info == (LZWInfo *) NULL)
 425     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
 426       image->filename);
 427   exception=(&image->exception);
 428   pass=0;
 429   offset=0;
 430   for (y=0; y < (ssize_t) image->rows; y++)
 431   {
 432     register ssize_t
 433       x;
 434
 435     register Quantum
 436       *restrict q;
 437
 438     q=GetAuthenticPixels(image,0,offset,image->columns,1,exception);
 439     if (q == (const Quantum *) NULL)
 440       break;
 441     for (x=0; x < (ssize_t) image->columns; )
 442     {
 443       c=ReadBlobLZWByte(lzw_info);
 444       if (c < 0)
 445         break;
 446       index=ConstrainColormapIndex(image,(size_t) c);
 447       SetPixelIndex(image,index,q);
 448       SetPixelPacket(image,image->colormap+(ssize_t) index,q);
 449       SetPixelAlpha(image,(ssize_t) index == opacity ? TransparentAlpha :
 450         OpaqueAlpha,q);
 451       x++;
 452       q+=GetPixelChannels(image);
 453     }
 454     if (x < (ssize_t) image->columns)
 455       break;
 456     if (image->interlace == NoInterlace)
 457       offset++;
 458     else
 459       switch (pass)
 460       {
 461         case 0:
 462         default:
 463         {
 464           offset+=8;
 465           if (offset >= (ssize_t) image->rows)
 466             {
 467               pass++;
 468               offset=4;
 469             }
 470           break;
 471         }
 472         case 1:
 473         {
 474           offset+=8;
 475           if (offset >= (ssize_t) image->rows)
 476             {
 477               pass++;
 478               offset=2;
 479             }
 480           break;
 481         }
 482         case 2:
 483         {
 484           offset+=4;
 485           if (offset >= (ssize_t) image->rows)
 486             {
 487               pass++;
 488               offset=1;
 489             }
 490           break;
 491         }
 492         case 3:
 493         {
 494           offset+=2;
 495           break;
 496         }
 497       }
 498     if (SyncAuthenticPixels(image,exception) == MagickFalse)
 499       break;
 500   }
 501   lzw_info=RelinquishLZWInfo(lzw_info);
 502   if (y < (ssize_t) image->rows)
 503     ThrowBinaryException(CorruptImageError,"CorruptImage",image->filename);
 504   return(MagickTrue);
 505 }
 506 \f
 507 /*
 508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 509 %                                                                             %
 510 %                                                                             %
 511 %                                                                             %
 512 %   E n c o d e I m a g e                                                     %
 513 %                                                                             %
 514 %                                                                             %
 515 %                                                                             %
 516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 517 %
 518 %  EncodeImage compresses an image via GIF-coding.
 519 %
 520 %  The format of the EncodeImage method is:
 521 %
 522 %      MagickBooleanType EncodeImage(const ImageInfo *image_info,Image *image,
 523 %        const size_t data_size)
 524 %
 525 %  A description of each parameter follows:
 526 %
 527 %    o image_info: the image info.
 528 %
 529 %    o image: the address of a structure of type Image.
 530 %
 531 %    o data_size:  The number of bits in the compressed packet.
 532 %
 533 */
 534 static MagickBooleanType EncodeImage(const ImageInfo *image_info,Image *image,
 535   const size_t data_size)
 536 {
 537 #define MaxCode(number_bits)  ((one << (number_bits))-1)
 538 #define MaxHashTable  5003
 539 #define MaxGIFBits  12UL
 540 #define MaxGIFTable  (1UL << MaxGIFBits)
 541 #define GIFOutputCode(code) \
 542 { \
 543   /*  \
 544     Emit a code. \
 545   */ \
 546   if (bits > 0) \
 547     datum|=(code) << bits; \
 548   else \
 549     datum=code; \
 550   bits+=number_bits; \
 551   while (bits >= 8) \
 552   { \
 553     /*  \
 554       Add a character to current packet. \
 555     */ \
 556     packet[length++]=(unsigned char) (datum & 0xff); \
 557     if (length >= 254) \
 558       { \
 559         (void) WriteBlobByte(image,(unsigned char) length); \
 560         (void) WriteBlob(image,length,packet); \
 561         length=0; \
 562       } \
 563     datum>>=8; \
 564     bits-=8; \
 565   } \
 566   if (free_code > max_code)  \
 567     { \
 568       number_bits++; \
 569       if (number_bits == MaxGIFBits) \
 570         max_code=MaxGIFTable; \
 571       else \
 572         max_code=MaxCode(number_bits); \
 573     } \
 574 }
 575
 576   Quantum
 577     index;
 578
 579   register ssize_t
 580     i;
 581
 582   short
 583     *hash_code,
 584     *hash_prefix,
 585     waiting_code;
 586
 587   size_t
 588     bits,
 589     clear_code,
 590     datum,
 591     end_of_information_code,
 592     free_code,
 593     length,
 594     max_code,
 595     next_pixel,
 596     number_bits,
 597     one,
 598     pass;
 599
 600   ssize_t
 601     displacement,
 602     offset,
 603     k,
 604     y;
 605
 606   unsigned char
 607     *packet,
 608     *hash_suffix;
 609
 610   /*
 611     Allocate encoder tables.
 612   */
 613   assert(image != (Image *) NULL);
 614   one=1;
 615   packet=(unsigned char *) AcquireQuantumMemory(256,sizeof(*packet));
 616   hash_code=(short *) AcquireQuantumMemory(MaxHashTable,sizeof(*hash_code));
 617   hash_prefix=(short *) AcquireQuantumMemory(MaxHashTable,sizeof(*hash_prefix));
 618   hash_suffix=(unsigned char *) AcquireQuantumMemory(MaxHashTable,
 619     sizeof(*hash_suffix));
 620   if ((packet == (unsigned char *) NULL) || (hash_code == (short *) NULL) ||
 621       (hash_prefix == (short *) NULL) ||
 622       (hash_suffix == (unsigned char *) NULL))
 623     {
 624       if (packet != (unsigned char *) NULL)
 625         packet=(unsigned char *) RelinquishMagickMemory(packet);
 626       if (hash_code != (short *) NULL)
 627         hash_code=(short *) RelinquishMagickMemory(hash_code);
 628       if (hash_prefix != (short *) NULL)
 629         hash_prefix=(short *) RelinquishMagickMemory(hash_prefix);
 630       if (hash_suffix != (unsigned char *) NULL)
 631         hash_suffix=(unsigned char *) RelinquishMagickMemory(hash_suffix);
 632       return(MagickFalse);
 633     }
 634   /*
 635     Initialize GIF encoder.
 636   */
 637   number_bits=data_size;
 638   max_code=MaxCode(number_bits);
 639   clear_code=((short) one << (data_size-1));
 640   end_of_information_code=clear_code+1;
 641   free_code=clear_code+2;
 642   length=0;
 643   datum=0;
 644   bits=0;
 645   for (i=0; i < MaxHashTable; i++)
 646     hash_code[i]=0;
 647   GIFOutputCode(clear_code);
 648   /*
 649     Encode pixels.
 650   */
 651   offset=0;
 652   pass=0;
 653   waiting_code=0;
 654   for (y=0; y < (ssize_t) image->rows; y++)
 655   {
 656     register const Quantum
 657       *restrict p;
 658
 659     register ssize_t
 660       x;
 661
 662     p=GetVirtualPixels(image,0,offset,image->columns,1,&image->exception);
 663     if (p == (const Quantum *) NULL)
 664       break;
 665     if (y == 0)
 666       {
 667         waiting_code=(short) GetPixelIndex(image,p);
 668         p+=GetPixelChannels(image);
 669       }
 670     for (x=(ssize_t) (y == 0 ? 1 : 0); x < (ssize_t) image->columns; x++)
 671     {
 672       /*
 673         Probe hash table.
 674       */
 675       index=(Quantum) ((size_t) GetPixelIndex(image,p) & 0xff);
 676       p+=GetPixelChannels(image);
 677       k=(ssize_t) (((size_t) index << (MaxGIFBits-8))+waiting_code);
 678       if (k >= MaxHashTable)
 679         k-=MaxHashTable;
 680       next_pixel=MagickFalse;
 681       displacement=1;
 682       if (hash_code[k] > 0)
 683         {
 684           if ((hash_prefix[k] == waiting_code) &&
 685               (hash_suffix[k] == (unsigned char) index))
 686             {
 687               waiting_code=hash_code[k];
 688               continue;
 689             }
 690           if (k != 0)
 691             displacement=MaxHashTable-k;
 692           for ( ; ; )
 693           {
 694             k-=displacement;
 695             if (k < 0)
 696               k+=MaxHashTable;
 697             if (hash_code[k] == 0)
 698               break;
 699             if ((hash_prefix[k] == waiting_code) &&
 700                 (hash_suffix[k] == (unsigned char) index))
 701               {
 702                 waiting_code=hash_code[k];
 703                 next_pixel=MagickTrue;
 704                 break;
 705               }
 706           }
 707           if (next_pixel == MagickTrue)
 708             continue;
 709         }
 710       GIFOutputCode((size_t) waiting_code);
 711       if (free_code < MaxGIFTable)
 712         {
 713           hash_code[k]=(short) free_code++;
 714           hash_prefix[k]=waiting_code;
 715           hash_suffix[k]=(unsigned char) index;
 716         }
 717       else
 718         {
 719           /*
 720             Fill the hash table with empty entries.
 721           */
 722           for (k=0; k < MaxHashTable; k++)
 723             hash_code[k]=0;
 724           /*
 725             Reset compressor and issue a clear code.
 726           */
 727           free_code=clear_code+2;
 728           GIFOutputCode(clear_code);
 729           number_bits=data_size;
 730           max_code=MaxCode(number_bits);
 731         }
 732       waiting_code=(short) index;
 733     }
 734     if (image_info->interlace == NoInterlace)
 735       offset++;
 736     else
 737       switch (pass)
 738       {
 739         case 0:
 740         default:
 741         {
 742           offset+=8;
 743           if (offset >= (ssize_t) image->rows)
 744             {
 745               pass++;
 746               offset=4;
 747             }
 748           break;
 749         }
 750         case 1:
 751         {
 752           offset+=8;
 753           if (offset >= (ssize_t) image->rows)
 754             {
 755               pass++;
 756               offset=2;
 757             }
 758           break;
 759         }
 760         case 2:
 761         {
 762           offset+=4;
 763           if (offset >= (ssize_t) image->rows)
 764             {
 765               pass++;
 766               offset=1;
 767             }
 768           break;
 769         }
 770         case 3:
 771         {
 772           offset+=2;
 773           break;
 774         }
 775       }
 776   }
 777   /*
 778     Flush out the buffered code.
 779   */
 780   GIFOutputCode((size_t) waiting_code);
 781   GIFOutputCode(end_of_information_code);
 782   if (bits > 0)
 783     {
 784       /*
 785         Add a character to current packet.
 786       */
 787       packet[length++]=(unsigned char) (datum & 0xff);
 788       if (length >= 254)
 789         {
 790           (void) WriteBlobByte(image,(unsigned char) length);
 791           (void) WriteBlob(image,length,packet);
 792           length=0;
 793         }
 794     }
 795   /*
 796     Flush accumulated data.
 797   */
 798   if (length > 0)
 799     {
 800       (void) WriteBlobByte(image,(unsigned char) length);
 801       (void) WriteBlob(image,length,packet);
 802     }
 803   /*
 804     Free encoder memory.
 805   */
 806   hash_suffix=(unsigned char *) RelinquishMagickMemory(hash_suffix);
 807   hash_prefix=(short *) RelinquishMagickMemory(hash_prefix);
 808   hash_code=(short *) RelinquishMagickMemory(hash_code);
 809   packet=(unsigned char *) RelinquishMagickMemory(packet);
 810   return(MagickTrue);
 811 }
 812 \f
 813 /*
 814 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 815 %                                                                             %
 816 %                                                                             %
 817 %                                                                             %
 818 %   I s G I F                                                                 %
 819 %                                                                             %
 820 %                                                                             %
 821 %                                                                             %
 822 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 823 %
 824 %  IsGIF() returns MagickTrue if the image format type, identified by the
 825 %  magick string, is GIF.
 826 %
 827 %  The format of the IsGIF method is:
 828 %
 829 %      MagickBooleanType IsGIF(const unsigned char *magick,const size_t length)
 830 %
 831 %  A description of each parameter follows:
 832 %
 833 %    o magick: compare image format pattern against these bytes.
 834 %
 835 %    o length: Specifies the length of the magick string.
 836 %
 837 */
 838 static MagickBooleanType IsGIF(const unsigned char *magick,const size_t length)
 839 {
 840   if (length < 4)
 841     return(MagickFalse);
 842   if (LocaleNCompare((char *) magick,"GIF8",4) == 0)
 843     return(MagickTrue);
 844   return(MagickFalse);
 845 }
 846 \f
 847 /*
 848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 849 %                                                                             %
 850 %                                                                             %
 851 %                                                                             %
 852 +  R e a d B l o b B l o c k                                                  %
 853 %                                                                             %
 854 %                                                                             %
 855 %                                                                             %
 856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 857 %
 858 %  ReadBlobBlock() reads data from the image file and returns it.  The
 859 %  amount of data is determined by first reading a count byte.  The number
 860 %  of bytes read is returned.
 861 %
 862 %  The format of the ReadBlobBlock method is:
 863 %
 864 %      size_t ReadBlobBlock(Image *image,unsigned char *data)
 865 %
 866 %  A description of each parameter follows:
 867 %
 868 %    o image: the image.
 869 %
 870 %    o data:  Specifies an area to place the information requested from
 871 %      the file.
 872 %
 873 */
 874 static ssize_t ReadBlobBlock(Image *image,unsigned char *data)
 875 {
 876   ssize_t
 877     count;
 878
 879   unsigned char
 880     block_count;
 881
 882   assert(image != (Image *) NULL);
 883   assert(image->signature == MagickSignature);
 884   assert(data != (unsigned char *) NULL);
 885   count=ReadBlob(image,1,&block_count);
 886   if (count != 1)
 887     return(0);
 888   return(ReadBlob(image,(size_t) block_count,data));
 889 }
 890 \f
 891 /*
 892 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 893 %                                                                             %
 894 %                                                                             %
 895 %                                                                             %
 896 %   R e a d G I F I m a g e                                                   %
 897 %                                                                             %
 898 %                                                                             %
 899 %                                                                             %
 900 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 901 %
 902 %  ReadGIFImage() reads a Compuserve Graphics image file and returns it.
 903 %  It allocates the memory necessary for the new Image structure and returns a
 904 %  pointer to the new image.
 905 %
 906 %  The format of the ReadGIFImage method is:
 907 %
 908 %      Image *ReadGIFImage(const ImageInfo *image_info,ExceptionInfo *exception)
 909 %
 910 %  A description of each parameter follows:
 911 %
 912 %    o image_info: the image info.
 913 %
 914 %    o exception: return any errors or warnings in this structure.
 915 %
 916 */
 917
 918 static inline size_t MagickMax(const size_t x,const size_t y)
 919 {
 920   if (x > y)
 921     return(x);
 922   return(y);
 923 }
 924
 925 static inline size_t MagickMin(const size_t x,const size_t y)
 926 {
 927   if (x < y)
 928     return(x);
 929   return(y);
 930 }
 931
 932 static MagickBooleanType PingGIFImage(Image *image)
 933 {
 934   unsigned char
 935     buffer[256],
 936     length,
 937     data_size;
 938
 939   assert(image != (Image *) NULL);
 940   assert(image->signature == MagickSignature);
 941   if (image->debug != MagickFalse)
 942     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 943   if (ReadBlob(image,1,&data_size) != 1)
 944     ThrowBinaryException(CorruptImageError,"CorruptImage",image->filename);
 945   if (data_size > MaximumLZWBits)
 946     ThrowBinaryException(CorruptImageError,"CorruptImage",image->filename);
 947   if (ReadBlob(image,1,&length) != 1)
 948     ThrowBinaryException(CorruptImageError,"CorruptImage",image->filename);
 949   while (length != 0)
 950   {
 951     if (ReadBlob(image,length,buffer) != (ssize_t) length)
 952       ThrowBinaryException(CorruptImageError,"CorruptImage",image->filename);
 953     if (ReadBlob(image,1,&length) != 1)
 954       ThrowBinaryException(CorruptImageError,"CorruptImage",image->filename);
 955   }
 956   return(MagickTrue);
 957 }
 958
 959 static Image *ReadGIFImage(const ImageInfo *image_info,ExceptionInfo *exception)
 960 {
 961 #define BitSet(byte,bit)  (((byte) & (bit)) == (bit))
 962 #define LSBFirstOrder(x,y)  (((y) << 8) | (x))
 963
 964   Image
 965     *image;
 966
 967   int
 968     number_extensionss=0;
 969
 970   MagickBooleanType
 971     status;
 972
 973   RectangleInfo
 974     page;
 975
 976   register ssize_t
 977     i;
 978
 979   register unsigned char
 980     *p;
 981
 982   size_t
 983     delay,
 984     dispose,
 985     global_colors,
 986     image_count,
 987     iterations,
 988     one;
 989
 990   ssize_t
 991     count,
 992     opacity;
 993
 994   unsigned char
 995     background,
 996     c,
 997     flag,
 998     *global_colormap,
 999     header[MaxTextExtent],
1000     magick[12];
1001
1002   /*
1003     Open image file.
1004   */
1005   assert(image_info != (const ImageInfo *) NULL);
1006   assert(image_info->signature == MagickSignature);
1007   if (image_info->debug != MagickFalse)
1008     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",
1009       image_info->filename);
1010   assert(exception != (ExceptionInfo *) NULL);
1011   assert(exception->signature == MagickSignature);
1012   image=AcquireImage(image_info);
1013   status=OpenBlob(image_info,image,ReadBinaryBlobMode,exception);
1014   if (status == MagickFalse)
1015     {
1016       image=DestroyImageList(image);
1017       return((Image *) NULL);
1018     }
1019   /*
1020     Determine if this a GIF file.
1021   */
1022   count=ReadBlob(image,6,magick);
1023   if ((count != 6) || ((LocaleNCompare((char *) magick,"GIF87",5) != 0) &&
1024       (LocaleNCompare((char *) magick,"GIF89",5) != 0)))
1025     ThrowReaderException(CorruptImageError,"ImproperImageHeader");
1026   page.width=ReadBlobLSBShort(image);
1027   page.height=ReadBlobLSBShort(image);
1028   flag=(unsigned char) ReadBlobByte(image);
1029   background=(unsigned char) ReadBlobByte(image);
1030   c=(unsigned char) ReadBlobByte(image);  /* reserved */
1031   one=1;
1032   global_colors=one << (((size_t) flag & 0x07)+1);
1033   global_colormap=(unsigned char *) AcquireQuantumMemory((size_t)
1034     MagickMax(global_colors,256),3UL*sizeof(*global_colormap));
1035   if (global_colormap == (unsigned char *) NULL)
1036     ThrowReaderException(ResourceLimitError,"MemoryAllocationFailed");
1037   if (BitSet((int) flag,0x80) != 0)
1038     count=ReadBlob(image,(size_t) (3*global_colors),global_colormap);
1039   delay=0;
1040   dispose=0;
1041   iterations=1;
1042   opacity=(-1);
1043   image_count=0;
1044   for ( ; ; )
1045   {
1046     count=ReadBlob(image,1,&c);
1047     if (count != 1)
1048       break;
1049     if (c == (unsigned char) ';')
1050       break;  /* terminator */
1051     if (c == (unsigned char) '!')
1052       {
1053         /*
1054           GIF Extension block.
1055         */
1056
1057         count=ReadBlob(image,1,&c);
1058         if (count != 1)
1059           {
1060             global_colormap=(unsigned char *) RelinquishMagickMemory(
1061               global_colormap);
1062             ThrowReaderException(CorruptImageError,
1063               "UnableToReadExtensionBlock");
1064           }
1065         switch (c)
1066         {
1067           case 0xf9:
1068           {
1069             /*
1070               Read graphics control extension.
1071             */
1072             while (ReadBlobBlock(image,header) != 0) ;
1073             dispose=(size_t) (header[0] >> 2);
1074             delay=(size_t) ((header[2] << 8) | header[1]);
1075             if ((ssize_t) (header[0] & 0x01) == 0x01)
1076               opacity=(ssize_t) header[3];
1077             break;
1078           }
1079           case 0xfe:
1080           {
1081             char
1082               *comments;
1083
1084             /*
1085               Read comment extension.
1086             */
1087             comments=AcquireString((char *) NULL);
1088             for ( ; ; )
1089             {
1090               count=(ssize_t) ReadBlobBlock(image,header);
1091               if (count == 0)
1092                 break;
1093               header[count]='\0';
1094               (void) ConcatenateString(&comments,(const char *) header);
1095             }
1096             (void) SetImageProperty(image,"comment",comments);
1097             comments=DestroyString(comments);
1098             break;
1099           }
1100           case 0xff:
1101           {
1102             /* Read GIF application extension */
1103
1104             MagickBooleanType
1105               loop;
1106
1107             /*
1108               Read Netscape Loop extension.
1109             */
1110             loop=MagickFalse;
1111             if (ReadBlobBlock(image,header) != 0)
1112               loop=LocaleNCompare((char *) header,"NETSCAPE2.0",11) == 0 ?
1113                 MagickTrue : MagickFalse;
1114             if (loop != MagickFalse)
1115               {
1116                 while (ReadBlobBlock(image,header) != 0)
1117                   iterations=(size_t) ((header[2] << 8) | header[1]);
1118                 break;
1119               }
1120             else
1121               {
1122                 char
1123                   name[MaxTextExtent];
1124
1125                 int
1126                   block_length,
1127                   info_length,
1128                   reserved_length;
1129
1130                 MagickBooleanType
1131                   i8bim,
1132                   icc,
1133                   iptc;
1134
1135                 StringInfo
1136                   *profile;
1137
1138                 unsigned char
1139                   *info;
1140
1141                 /*
1142                   Store GIF application extension as a generic profile.
1143                 */
1144                 i8bim=LocaleNCompare((char *) header,"MGK8BIM0000",11) == 0 ?
1145                   MagickTrue : MagickFalse;
1146                 icc=LocaleNCompare((char *) header,"ICCRGBG1012",11) == 0 ?
1147                   MagickTrue : MagickFalse;
1148                 iptc=LocaleNCompare((char *) header,"MGKIPTC0000",11) == 0 ?
1149                   MagickTrue : MagickFalse;
1150                 number_extensionss++;
1151                 (void) LogMagickEvent(CoderEvent,GetMagickModule(),
1152                   "    Reading GIF application extension");
1153                 info=(unsigned char *) AcquireQuantumMemory(255UL,
1154                   sizeof(*info));
1155                 reserved_length=255;
1156                 for (info_length=0; ; )
1157                 {
1158                   block_length=(int) ReadBlobBlock(image,&info[info_length]);
1159                   if (block_length == 0)
1160                     break;
1161                   info_length+=block_length;
1162                   if (info_length > (reserved_length-255))
1163                     {
1164                        reserved_length+=4096;
1165                        info=(unsigned char *) ResizeQuantumMemory(info,
1166                          (size_t) reserved_length,sizeof(*info));
1167                     }
1168                 }
1169                 info=(unsigned char *) ResizeQuantumMemory(info,(size_t)
1170                   (info_length+1),sizeof(*info));
1171                 profile=AcquireStringInfo((size_t) info_length);
1172                 SetStringInfoDatum(profile,(const unsigned char *) info);
1173                 if (i8bim == MagickTrue)
1174                   (void) CopyMagickString(name,"8bim",sizeof(name));
1175                 else if (icc == MagickTrue)
1176                   (void) CopyMagickString(name,"icc",sizeof(name));
1177                 else if (iptc == MagickTrue)
1178                   (void) CopyMagickString(name,"iptc",sizeof(name));
1179                 else
1180                   (void) FormatLocaleString(name,sizeof(name),"gif:%.11s",
1181                     header);
1182                 (void) SetImageProfile(image,name,profile);
1183                 info=(unsigned char *) RelinquishMagickMemory(info);
1184                 profile=DestroyStringInfo(profile);
1185                 (void) LogMagickEvent(CoderEvent,GetMagickModule(),
1186                   "      profile name=%s",name);
1187               }
1188             break;
1189           }
1190           default:
1191           {
1192             while (ReadBlobBlock(image,header) != 0) ;
1193             break;
1194           }
1195         }
1196       }
1197     if (c != (unsigned char) ',')
1198       continue;
1199     if (image_count != 0)
1200       {
1201         /*
1202           Allocate next image structure.
1203         */
1204         AcquireNextImage(image_info,image);
1205         if (GetNextImageInList(image) == (Image *) NULL)
1206           {
1207             image=DestroyImageList(image);
1208             global_colormap=(unsigned char *) RelinquishMagickMemory(
1209               global_colormap);
1210             return((Image *) NULL);
1211           }
1212         image=SyncNextImageInList(image);
1213       }
1214     image_count++;
1215     /*
1216       Read image attributes.
1217     */
1218     image->storage_class=PseudoClass;
1219     image->compression=LZWCompression;
1220     page.x=(ssize_t) ReadBlobLSBShort(image);
1221     page.y=(ssize_t) ReadBlobLSBShort(image);
1222     image->columns=ReadBlobLSBShort(image);
1223     image->rows=ReadBlobLSBShort(image);
1224     image->depth=8;
1225     flag=(unsigned char) ReadBlobByte(image);
1226     image->interlace=BitSet((int) flag,0x40) != 0 ? GIFInterlace :
1227       NoInterlace;
1228     image->colors=BitSet((int) flag,0x80) == 0 ? global_colors :
1229       one << ((size_t) (flag & 0x07)+1);
1230     if (opacity >= (ssize_t) image->colors)
1231       opacity=(-1);
1232     image->page.width=page.width;
1233     image->page.height=page.height;
1234     image->page.y=page.y;
1235     image->page.x=page.x;
1236     image->delay=delay;
1237     image->ticks_per_second=100;
1238     image->dispose=(DisposeType) dispose;
1239     image->iterations=iterations;
1240     image->matte=opacity >= 0 ? MagickTrue : MagickFalse;
1241     delay=0;
1242     dispose=0;
1243     iterations=1;
1244     if ((image->columns == 0) || (image->rows == 0))
1245       {
1246         global_colormap=(unsigned char *) RelinquishMagickMemory(
1247           global_colormap);
1248         ThrowReaderException(CorruptImageError,"NegativeOrZeroImageSize");
1249       }
1250     /*
1251       Inititialize colormap.
1252     */
1253     if (AcquireImageColormap(image,image->colors) == MagickFalse)
1254       {
1255         global_colormap=(unsigned char *) RelinquishMagickMemory(
1256           global_colormap);
1257         ThrowReaderException(ResourceLimitError,"MemoryAllocationFailed");
1258       }
1259     if (BitSet((int) flag,0x80) == 0)
1260       {
1261         /*
1262           Use global colormap.
1263         */
1264         p=global_colormap;
1265         for (i=0; i < (ssize_t) image->colors; i++)
1266         {
1267           image->colormap[i].red=ScaleCharToQuantum(*p++);
1268           image->colormap[i].green=ScaleCharToQuantum(*p++);
1269           image->colormap[i].blue=ScaleCharToQuantum(*p++);
1270           if (i == opacity)
1271             {
1272               image->colormap[i].alpha=(Quantum) TransparentAlpha;
1273               image->transparent_color=image->colormap[opacity];
1274             }
1275         }
1276         image->background_color=image->colormap[MagickMin(background,
1277           image->colors-1)];
1278       }
1279     else
1280       {
1281         unsigned char
1282           *colormap;
1283
1284         /*
1285           Read local colormap.
1286         */
1287         colormap=(unsigned char *) AcquireQuantumMemory(image->colors,
1288           3*sizeof(*colormap));
1289         if (colormap == (unsigned char *) NULL)
1290           {
1291             global_colormap=(unsigned char *) RelinquishMagickMemory(
1292               global_colormap);
1293             ThrowReaderException(ResourceLimitError,"MemoryAllocationFailed");
1294           }
1295         count=ReadBlob(image,(3*image->colors)*sizeof(*colormap),colormap);
1296         if (count != (ssize_t) (3*image->colors))
1297           {
1298             global_colormap=(unsigned char *) RelinquishMagickMemory(
1299               global_colormap);
1300             colormap=(unsigned char *) RelinquishMagickMemory(colormap);
1301             ThrowReaderException(CorruptImageError,
1302               "InsufficientImageDataInFile");
1303           }
1304         p=colormap;
1305         for (i=0; i < (ssize_t) image->colors; i++)
1306         {
1307           image->colormap[i].red=ScaleCharToQuantum(*p++);
1308           image->colormap[i].green=ScaleCharToQuantum(*p++);
1309           image->colormap[i].blue=ScaleCharToQuantum(*p++);
1310           if (i == opacity)
1311             image->colormap[i].alpha=(Quantum) TransparentAlpha;
1312         }
1313         colormap=(unsigned char *) RelinquishMagickMemory(colormap);
1314       }
1315     if ((image_info->ping != MagickFalse) && (image_info->number_scenes != 0))
1316       if (image->scene >= (image_info->scene+image_info->number_scenes-1))
1317         break;
1318     /*
1319       Decode image.
1320     */
1321     if (image_info->ping != MagickFalse)
1322       status=PingGIFImage(image);
1323     else
1324       status=DecodeImage(image,opacity);
1325     if ((image_info->ping == MagickFalse) && (status == MagickFalse))
1326       {
1327         global_colormap=(unsigned char *) RelinquishMagickMemory(
1328           global_colormap);
1329         ThrowReaderException(CorruptImageError,"CorruptImage");
1330       }
1331     if (image_info->number_scenes != 0)
1332       if (image->scene >= (image_info->scene+image_info->number_scenes-1))
1333         break;
1334     opacity=(-1);
1335     status=SetImageProgress(image,LoadImageTag,(MagickOffsetType) image->scene-
1336       1,image->scene);
1337     if (status == MagickFalse)
1338       break;
1339   }
1340   global_colormap=(unsigned char *) RelinquishMagickMemory(global_colormap);
1341   if ((image->columns == 0) || (image->rows == 0))
1342     ThrowReaderException(CorruptImageError,"NegativeOrZeroImageSize");
1343   (void) CloseBlob(image);
1344   return(GetFirstImageInList(image));
1345 }
1346 \f
1347 /*
1348 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1349 %                                                                             %
1350 %                                                                             %
1351 %                                                                             %
1352 %   R e g i s t e r G I F I m a g e                                           %
1353 %                                                                             %
1354 %                                                                             %
1355 %                                                                             %
1356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1357 %
1358 %  RegisterGIFImage() adds properties for the GIF image format to
1359 %  the list of supported formats.  The properties include the image format
1360 %  tag, a method to read and/or write the format, whether the format
1361 %  supports the saving of more than one frame to the same file or blob,
1362 %  whether the format supports native in-memory I/O, and a brief
1363 %  description of the format.
1364 %
1365 %  The format of the RegisterGIFImage method is:
1366 %
1367 %      size_t RegisterGIFImage(void)
1368 %
1369 */
1370 ModuleExport size_t RegisterGIFImage(void)
1371 {
1372   MagickInfo
1373     *entry;
1374
1375   entry=SetMagickInfo("GIF");
1376   entry->decoder=(DecodeImageHandler *) ReadGIFImage;
1377   entry->encoder=(EncodeImageHandler *) WriteGIFImage;
1378   entry->magick=(IsImageFormatHandler *) IsGIF;
1379   entry->description=ConstantString("CompuServe graphics interchange format");
1380   entry->module=ConstantString("GIF");
1381   (void) RegisterMagickInfo(entry);
1382   entry=SetMagickInfo("GIF87");
1383   entry->decoder=(DecodeImageHandler *) ReadGIFImage;
1384   entry->encoder=(EncodeImageHandler *) WriteGIFImage;
1385   entry->magick=(IsImageFormatHandler *) IsGIF;
1386   entry->adjoin=MagickFalse;
1387   entry->description=ConstantString("CompuServe graphics interchange format");
1388   entry->version=ConstantString("version 87a");
1389   entry->module=ConstantString("GIF");
1390   (void) RegisterMagickInfo(entry);
1391   return(MagickImageCoderSignature);
1392 }
1393 \f
1394 /*
1395 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1396 %                                                                             %
1397 %                                                                             %
1398 %                                                                             %
1399 %   U n r e g i s t e r G I F I m a g e                                       %
1400 %                                                                             %
1401 %                                                                             %
1402 %                                                                             %
1403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1404 %
1405 %  UnregisterGIFImage() removes format registrations made by the
1406 %  GIF module from the list of supported formats.
1407 %
1408 %  The format of the UnregisterGIFImage method is:
1409 %
1410 %      UnregisterGIFImage(void)
1411 %
1412 */
1413 ModuleExport void UnregisterGIFImage(void)
1414 {
1415   (void) UnregisterMagickInfo("GIF");
1416   (void) UnregisterMagickInfo("GIF87");
1417 }
1418 \f
1419 /*
1420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1421 %                                                                             %
1422 %                                                                             %
1423 %                                                                             %
1424 %   W r i t e G I F I m a g e                                                 %
1425 %                                                                             %
1426 %                                                                             %
1427 %                                                                             %
1428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1429 %
1430 %  WriteGIFImage() writes an image to a file in the Compuserve Graphics
1431 %  image format.
1432 %
1433 %  The format of the WriteGIFImage method is:
1434 %
1435 %      MagickBooleanType WriteGIFImage(const ImageInfo *image_info,Image *image)
1436 %
1437 %  A description of each parameter follows.
1438 %
1439 %    o image_info: the image info.
1440 %
1441 %    o image:  The image.
1442 %
1443 */
1444 static MagickBooleanType WriteGIFImage(const ImageInfo *image_info,Image *image)
1445 {
1446   Image
1447     *next_image;
1448
1449   int
1450     c;
1451
1452   ImageInfo
1453     *write_info;
1454
1455   InterlaceType
1456     interlace;
1457
1458   MagickBooleanType
1459     status;
1460
1461   MagickOffsetType
1462     scene;
1463
1464   RectangleInfo
1465     page;
1466
1467   register ssize_t
1468     i;
1469
1470   register unsigned char
1471     *q;
1472
1473   size_t
1474     bits_per_pixel,
1475     delay,
1476     length,
1477     one;
1478
1479   ssize_t
1480     j,
1481     opacity;
1482
1483   unsigned char
1484     *colormap,
1485     *global_colormap;
1486
1487   /*
1488     Open output image file.
1489   */
1490   assert(image_info != (const ImageInfo *) NULL);
1491   assert(image_info->signature == MagickSignature);
1492   assert(image != (Image *) NULL);
1493   assert(image->signature == MagickSignature);
1494   if (image->debug != MagickFalse)
1495     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1496   status=OpenBlob(image_info,image,WriteBinaryBlobMode,&image->exception);
1497   if (status == MagickFalse)
1498     return(status);
1499   /*
1500     Allocate colormap.
1501   */
1502   global_colormap=(unsigned char *) AcquireQuantumMemory(768UL,
1503     sizeof(*global_colormap));
1504   colormap=(unsigned char *) AcquireQuantumMemory(768UL,sizeof(*colormap));
1505   if ((global_colormap == (unsigned char *) NULL) ||
1506       (colormap == (unsigned char *) NULL))
1507     ThrowWriterException(ResourceLimitError,"MemoryAllocationFailed");
1508   for (i=0; i < 768; i++)
1509     colormap[i]=(unsigned char) 0;
1510   /*
1511     Write GIF header.
1512   */
1513   write_info=CloneImageInfo(image_info);
1514   if (LocaleCompare(write_info->magick,"GIF87") != 0)
1515     (void) WriteBlob(image,6,(unsigned char *) "GIF89a");
1516   else
1517     {
1518       (void) WriteBlob(image,6,(unsigned char *) "GIF87a");
1519       write_info->adjoin=MagickFalse;
1520     }
1521   /*
1522     Determine image bounding box.
1523   */
1524   page.width=image->columns;
1525   page.height=image->rows;
1526   page.x=0;
1527   page.y=0;
1528   if (write_info->adjoin != MagickFalse)
1529     for (next_image=image; next_image != (Image *) NULL; )
1530     {
1531       page.x=next_image->page.x;
1532       page.y=next_image->page.y;
1533       if ((next_image->page.width+page.x) > page.width)
1534         page.width=next_image->page.width+page.x;
1535       if ((next_image->page.height+page.y) > page.height)
1536         page.height=next_image->page.height+page.y;
1537       next_image=GetNextImageInList(next_image);
1538     }
1539   page.x=image->page.x;
1540   page.y=image->page.y;
1541   if ((image->page.width != 0) && (image->page.height != 0))
1542     page=image->page;
1543   (void) WriteBlobLSBShort(image,(unsigned short) page.width);
1544   (void) WriteBlobLSBShort(image,(unsigned short) page.height);
1545   /*
1546     Write images to file.
1547   */
1548   interlace=write_info->interlace;
1549   if ((write_info->adjoin != MagickFalse) &&
1550       (GetNextImageInList(image) != (Image *) NULL))
1551     interlace=NoInterlace;
1552   scene=0;
1553   one=1;
1554   do
1555   {
1556     if (image->colorspace != RGBColorspace)
1557       (void) TransformImageColorspace(image,RGBColorspace);
1558     opacity=(-1);
1559     if (IsImageOpaque(image,&image->exception) != MagickFalse)
1560       {
1561         if ((image->storage_class == DirectClass) || (image->colors > 256))
1562           (void) SetImageType(image,PaletteType);
1563       }
1564     else
1565       {
1566         MagickRealType
1567           alpha,
1568           beta;
1569
1570         /*
1571           Identify transparent colormap index.
1572         */
1573         if ((image->storage_class == DirectClass) || (image->colors > 256))
1574           (void) SetImageType(image,PaletteBilevelMatteType);
1575         for (i=0; i < (ssize_t) image->colors; i++)
1576           if (image->colormap[i].alpha != OpaqueAlpha)
1577             {
1578               if (opacity < 0)
1579                 {
1580                   opacity=i;
1581                   continue;
1582                 }
1583               alpha=(MagickRealType) TransparentAlpha-(MagickRealType)
1584                 image->colormap[i].alpha;
1585               beta=(MagickRealType) TransparentAlpha-(MagickRealType)
1586                 image->colormap[opacity].alpha;
1587               if (alpha < beta)
1588                 opacity=i;
1589             }
1590         if (opacity == -1)
1591           {
1592             (void) SetImageType(image,PaletteBilevelMatteType);
1593             for (i=0; i < (ssize_t) image->colors; i++)
1594               if (image->colormap[i].alpha != OpaqueAlpha)
1595                 {
1596                   if (opacity < 0)
1597                     {
1598                       opacity=i;
1599                       continue;
1600                     }
1601                   alpha=(Quantum) TransparentAlpha-(MagickRealType)
1602                     image->colormap[i].alpha;
1603                   beta=(Quantum) TransparentAlpha-(MagickRealType)
1604                     image->colormap[opacity].alpha;
1605                   if (alpha < beta)
1606                     opacity=i;
1607                 }
1608           }
1609         if (opacity >= 0)
1610           {
1611             image->colormap[opacity].red=image->transparent_color.red;
1612             image->colormap[opacity].green=image->transparent_color.green;
1613             image->colormap[opacity].blue=image->transparent_color.blue;
1614           }
1615       }
1616     if ((image->storage_class == DirectClass) || (image->colors > 256))
1617       ThrowWriterException(ResourceLimitError,"MemoryAllocationFailed");
1618     for (bits_per_pixel=1; bits_per_pixel < 8; bits_per_pixel++)
1619       if ((one << bits_per_pixel) >= image->colors)
1620         break;
1621     q=colormap;
1622     for (i=0; i < (ssize_t) image->colors; i++)
1623     {
1624       *q++=ScaleQuantumToChar(image->colormap[i].red);
1625       *q++=ScaleQuantumToChar(image->colormap[i].green);
1626       *q++=ScaleQuantumToChar(image->colormap[i].blue);
1627     }
1628     for ( ; i < (ssize_t) (one << bits_per_pixel); i++)
1629     {
1630       *q++=(unsigned char) 0x0;
1631       *q++=(unsigned char) 0x0;
1632       *q++=(unsigned char) 0x0;
1633     }
1634     if ((GetPreviousImageInList(image) == (Image *) NULL) ||
1635         (write_info->adjoin == MagickFalse))
1636       {
1637         /*
1638           Write global colormap.
1639         */
1640         c=0x80;
1641         c|=(8-1) << 4;  /* color resolution */
1642         c|=(bits_per_pixel-1);   /* size of global colormap */
1643         (void) WriteBlobByte(image,(unsigned char) c);
1644         for (j=0; j < (ssize_t) image->colors; j++)
1645           if (IsPixelPacketEquivalent(&image->background_color,image->colormap+j))
1646             break;
1647         (void) WriteBlobByte(image,(unsigned char)
1648           (j == (ssize_t) image->colors ? 0 : j));  /* background color */
1649         (void) WriteBlobByte(image,(unsigned char) 0x00);  /* reserved */
1650         length=(size_t) (3*(one << bits_per_pixel));
1651         (void) WriteBlob(image,length,colormap);
1652         for (j=0; j < 768; j++)
1653           global_colormap[j]=colormap[j];
1654       }
1655     if (LocaleCompare(write_info->magick,"GIF87") != 0)
1656       {
1657         /*
1658           Write graphics control extension.
1659         */
1660         (void) WriteBlobByte(image,(unsigned char) 0x21);
1661         (void) WriteBlobByte(image,(unsigned char) 0xf9);
1662         (void) WriteBlobByte(image,(unsigned char) 0x04);
1663         c=image->dispose << 2;
1664         if (opacity >= 0)
1665           c|=0x01;
1666         (void) WriteBlobByte(image,(unsigned char) c);
1667         delay=(size_t) (100*image->delay/MagickMax((size_t)
1668           image->ticks_per_second,1));
1669         (void) WriteBlobLSBShort(image,(unsigned short) delay);
1670         (void) WriteBlobByte(image,(unsigned char) (opacity >= 0 ? opacity :
1671           0));
1672         (void) WriteBlobByte(image,(unsigned char) 0x00);
1673         if ((LocaleCompare(write_info->magick,"GIF87") != 0) &&
1674             (GetImageProperty(image,"comment") != (const char *) NULL))
1675           {
1676             const char
1677               *value;
1678
1679             register const char
1680               *p;
1681
1682             size_t
1683               count;
1684
1685             /*
1686               Write Comment extension.
1687             */
1688             (void) WriteBlobByte(image,(unsigned char) 0x21);
1689             (void) WriteBlobByte(image,(unsigned char) 0xfe);
1690             value=GetImageProperty(image,"comment");
1691             p=value;
1692             while (strlen(p) != 0)
1693             {
1694               count=MagickMin(strlen(p),255);
1695               (void) WriteBlobByte(image,(unsigned char) count);
1696               for (i=0; i < (ssize_t) count; i++)
1697                 (void) WriteBlobByte(image,(unsigned char) *p++);
1698             }
1699             (void) WriteBlobByte(image,(unsigned char) 0x00);
1700           }
1701         if ((GetPreviousImageInList(image) == (Image *) NULL) &&
1702             (GetNextImageInList(image) != (Image *) NULL) &&
1703             (image->iterations != 1))
1704           {
1705             /*
1706               Write Netscape Loop extension.
1707             */
1708             (void) LogMagickEvent(CoderEvent,GetMagickModule(),
1709                "  Writing GIF Extension %s","NETSCAPE2.0");
1710             (void) WriteBlobByte(image,(unsigned char) 0x21);
1711             (void) WriteBlobByte(image,(unsigned char) 0xff);
1712             (void) WriteBlobByte(image,(unsigned char) 0x0b);
1713             (void) WriteBlob(image,11,(unsigned char *) "NETSCAPE2.0");
1714             (void) WriteBlobByte(image,(unsigned char) 0x03);
1715             (void) WriteBlobByte(image,(unsigned char) 0x01);
1716             (void) WriteBlobLSBShort(image,(unsigned short) image->iterations);
1717             (void) WriteBlobByte(image,(unsigned char) 0x00);
1718           }
1719         ResetImageProfileIterator(image);
1720         for ( ; ; )
1721         {
1722           char
1723             *name;
1724
1725           const StringInfo
1726             *profile;
1727
1728           name=GetNextImageProfile(image);
1729           if (name == (const char *) NULL)
1730             break;
1731           profile=GetImageProfile(image,name);
1732           if (profile != (StringInfo *) NULL)
1733           {
1734             if ((LocaleCompare(name,"ICC") == 0) ||
1735                 (LocaleCompare(name,"ICM") == 0) ||
1736                 (LocaleCompare(name,"IPTC") == 0) ||
1737                 (LocaleCompare(name,"8BIM") == 0) ||
1738                 (LocaleNCompare(name,"gif:",4) == 0))
1739             {
1740                size_t
1741                  length;
1742
1743                ssize_t
1744                  offset;
1745
1746                unsigned char
1747                  *datum;
1748
1749                datum=GetStringInfoDatum(profile);
1750                length=GetStringInfoLength(profile);
1751                (void) WriteBlobByte(image,(unsigned char) 0x21);
1752                (void) WriteBlobByte(image,(unsigned char) 0xff);
1753                (void) WriteBlobByte(image,(unsigned char) 0x0b);
1754                if ((LocaleCompare(name,"ICC") == 0) ||
1755                    (LocaleCompare(name,"ICM") == 0))
1756                  {
1757                    /*
1758                      Write ICC extension.
1759                    */
1760                    (void) WriteBlob(image,11,(unsigned char *)"ICCRGBG1012");
1761                    (void) LogMagickEvent(CoderEvent,GetMagickModule(),
1762                        "  Writing GIF Extension %s","ICCRGBG1012");
1763                  }
1764                else
1765                  if ((LocaleCompare(name,"IPTC") == 0))
1766                    {
1767                      /*
1768                        write IPTC extension.
1769                      */
1770                      (void) WriteBlob(image,11,(unsigned char *)"MGKIPTC0000");
1771                      (void) LogMagickEvent(CoderEvent,GetMagickModule(),
1772                          "  Writing GIF Extension %s","MGKIPTC0000");
1773                    }
1774                  else
1775                    if ((LocaleCompare(name,"8BIM") == 0))
1776                      {
1777                        /*
1778                          Write 8BIM extension>
1779                        */
1780                         (void) WriteBlob(image,11,(unsigned char *)
1781                           "MGK8BIM0000");
1782                         (void) LogMagickEvent(CoderEvent,GetMagickModule(),
1783                           "  Writing GIF Extension %s","MGK8BIM0000");
1784                      }
1785                    else
1786                      {
1787                        char
1788                          extension[MaxTextExtent];
1789
1790                        /* write generic extension */
1791                        (void) CopyMagickString(extension,name+4,
1792                          sizeof(extension));
1793                        (void) WriteBlob(image,11,(unsigned char *) extension);
1794                        (void) LogMagickEvent(CoderEvent,GetMagickModule(),
1795                           "  Writing GIF Extension %s",name);
1796                      }
1797                offset=0;
1798                while ((ssize_t) length > offset)
1799                {
1800                  size_t
1801                    block_length;
1802
1803                  if ((length-offset) < 255)
1804                    block_length=length-offset;
1805                  else
1806                    block_length=255;
1807                  (void) WriteBlobByte(image,(unsigned char) block_length);
1808                  (void) WriteBlob(image,(size_t) block_length,datum+offset);
1809                  offset+=(ssize_t) block_length;
1810                }
1811                (void) WriteBlobByte(image,(unsigned char) 0x00);
1812             }
1813           }
1814         }
1815       }
1816     (void) WriteBlobByte(image,',');  /* image separator */
1817     /*
1818       Write the image header.
1819     */
1820     page.x=image->page.x;
1821     page.y=image->page.y;
1822     if ((image->page.width != 0) && (image->page.height != 0))
1823       page=image->page;
1824     (void) WriteBlobLSBShort(image,(unsigned short) (page.x < 0 ? 0 : page.x));
1825     (void) WriteBlobLSBShort(image,(unsigned short) (page.y < 0 ? 0 : page.y));
1826     (void) WriteBlobLSBShort(image,(unsigned short) image->columns);
1827     (void) WriteBlobLSBShort(image,(unsigned short) image->rows);
1828     c=0x00;
1829     if (interlace != NoInterlace)
1830       c|=0x40;  /* pixel data is interlaced */
1831     for (j=0; j < (ssize_t) (3*image->colors); j++)
1832       if (colormap[j] != global_colormap[j])
1833         break;
1834     if (j == (ssize_t) (3*image->colors))
1835       (void) WriteBlobByte(image,(unsigned char) c);
1836     else
1837       {
1838         c|=0x80;
1839         c|=(bits_per_pixel-1);   /* size of local colormap */
1840         (void) WriteBlobByte(image,(unsigned char) c);
1841         length=(size_t) (3*(one << bits_per_pixel));
1842         (void) WriteBlob(image,length,colormap);
1843       }
1844     /*
1845       Write the image data.
1846     */
1847     c=(int) MagickMax(bits_per_pixel,2);
1848     (void) WriteBlobByte(image,(unsigned char) c);
1849     status=EncodeImage(write_info,image,(size_t) MagickMax(bits_per_pixel,2)+1);
1850     if (status == MagickFalse)
1851       {
1852         global_colormap=(unsigned char *) RelinquishMagickMemory(
1853           global_colormap);
1854         colormap=(unsigned char *) RelinquishMagickMemory(colormap);
1855         write_info=DestroyImageInfo(write_info);
1856         ThrowWriterException(ResourceLimitError,"MemoryAllocationFailed");
1857       }
1858     (void) WriteBlobByte(image,(unsigned char) 0x00);
1859     if (GetNextImageInList(image) == (Image *) NULL)
1860       break;
1861     image=SyncNextImageInList(image);
1862     scene++;
1863     status=SetImageProgress(image,SaveImagesTag,scene,
1864       GetImageListLength(image));
1865     if (status == MagickFalse)
1866       break;
1867   } while (write_info->adjoin != MagickFalse);
1868   (void) WriteBlobByte(image,';'); /* terminator */
1869   global_colormap=(unsigned char *) RelinquishMagickMemory(global_colormap);
1870   colormap=(unsigned char *) RelinquishMagickMemory(colormap);
1871   write_info=DestroyImageInfo(write_info);
1872   (void) CloseBlob(image);
1873   return(MagickTrue);
1874 }