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