reactos/dll/win32/windowscodecs/ungif.c

   1 /*
   2  * Gif extracting routines - derived from libungif
   3  *
   4  * Portions Copyright 2006 Mike McCormack
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  */
  20
  21 /*
  22  * Original copyright notice:
  23  *
  24  * The GIFLIB distribution is Copyright (c) 1997  Eric S. Raymond
  25  *
  26  * Permission is hereby granted, free of charge, to any person obtaining a copy
  27  * of this software and associated documentation files (the "Software"), to deal
  28  * in the Software without restriction, including without limitation the rights
  29  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  30  * copies of the Software, and to permit persons to whom the Software is
  31  * furnished to do so, subject to the following conditions:
  32  *
  33  * The above copyright notice and this permission notice shall be included in
  34  * all copies or substantial portions of the Software.
  35  */
  36
  37
  38 /******************************************************************************
  39  *   "Gif-Lib" - Yet another gif library.
  40  *
  41  * Written by:  Gershon Elber            IBM PC Ver 1.1,    Aug. 1990
  42  ******************************************************************************
  43  * The kernel of the GIF Decoding process can be found here.
  44  ******************************************************************************
  45  * History:
  46  * 16 Jun 89 - Version 1.0 by Gershon Elber.
  47  *  3 Sep 90 - Version 1.1 by Gershon Elber (Support for Gif89, Unique names).
  48  *****************************************************************************/
  49
  50 #include "wincodecs_private.h"
  51
  52 #include "ungif.h"
  53
  54 static void *ungif_alloc( size_t sz )
  55 {
  56     return HeapAlloc( GetProcessHeap(), 0, sz );
  57 }
  58
  59 static void *ungif_calloc( size_t num, size_t sz )
  60 {
  61     return HeapAlloc( GetProcessHeap(), HEAP_ZERO_MEMORY, num*sz );
  62 }
  63
  64 static void *ungif_realloc( void *ptr, size_t sz )
  65 {
  66     return HeapReAlloc( GetProcessHeap(), 0, ptr, sz );
  67 }
  68
  69 static void ungif_free( void *ptr )
  70 {
  71     HeapFree( GetProcessHeap(), 0, ptr );
  72 }
  73
  74 #define LZ_MAX_CODE         4095    /* Biggest code possible in 12 bits. */
  75 #define LZ_BITS             12
  76
  77 #define NO_SUCH_CODE        4098    /* Impossible code, to signal empty. */
  78
  79 typedef struct GifFilePrivateType {
  80     GifWord BitsPerPixel,     /* Bits per pixel (Codes uses at least this + 1). */
  81       ClearCode,   /* The CLEAR LZ code. */
  82       EOFCode,     /* The EOF LZ code. */
  83       RunningCode, /* The next code algorithm can generate. */
  84       RunningBits, /* The number of bits required to represent RunningCode. */
  85       MaxCode1,    /* 1 bigger than max. possible code, in RunningBits bits. */
  86       LastCode,    /* The code before the current code. */
  87       CrntCode,    /* Current algorithm code. */
  88       StackPtr,    /* For character stack (see below). */
  89       CrntShiftState;    /* Number of bits in CrntShiftDWord. */
  90     unsigned long CrntShiftDWord;   /* For bytes decomposition into codes. */
  91     unsigned long PixelCount;   /* Number of pixels in image. */
  92     InputFunc Read;     /* function to read gif input (TVT) */
  93     GifByteType Buf[256];   /* Compressed input is buffered here. */
  94     GifByteType Stack[LZ_MAX_CODE]; /* Decoded pixels are stacked here. */
  95     GifByteType Suffix[LZ_MAX_CODE + 1];    /* So we can trace the codes. */
  96     GifPrefixType Prefix[LZ_MAX_CODE + 1];
  97 } GifFilePrivateType;
  98
  99 /* avoid extra function call in case we use fread (TVT) */
 100 #define READ(_gif,_buf,_len) \
 101     ((GifFilePrivateType*)_gif->Private)->Read(_gif,_buf,_len)
 102
 103 static int DGifGetWord(GifFileType *GifFile, GifWord *Word);
 104 static int DGifSetupDecompress(GifFileType *GifFile);
 105 static int DGifDecompressLine(GifFileType *GifFile, GifPixelType *Line, int LineLen);
 106 static int DGifGetPrefixChar(const GifPrefixType *Prefix, int Code, int ClearCode);
 107 static int DGifDecompressInput(GifFileType *GifFile, int *Code);
 108 static int DGifBufferedInput(GifFileType *GifFile, GifByteType *Buf,
 109                              GifByteType *NextByte);
 110
 111 static int DGifGetExtensionNext(GifFileType * GifFile, GifByteType ** GifExtension);
 112 static int DGifGetCodeNext(GifFileType * GifFile, GifByteType ** GifCodeBlock);
 113
 114 /******************************************************************************
 115  * Miscellaneous utility functions
 116  *****************************************************************************/
 117
 118 /* return smallest bitfield size n will fit in */
 119 static int
 120 BitSize(int n) {
 121
 122     register int i;
 123
 124     for (i = 1; i <= 8; i++)
 125         if ((1 << i) >= n)
 126             break;
 127     return (i);
 128 }
 129
 130 /******************************************************************************
 131  * Color map object functions
 132  *****************************************************************************/
 133
 134 /*
 135  * Allocate a color map of given size; initialize with contents of
 136  * ColorMap if that pointer is non-NULL.
 137  */
 138 static ColorMapObject *
 139 MakeMapObject(int ColorCount,
 140               const GifColorType * ColorMap) {
 141
 142     ColorMapObject *Object;
 143
 144     /*** FIXME: Our ColorCount has to be a power of two.  Is it necessary to
 145      * make the user know that or should we automatically round up instead? */
 146     if (ColorCount != (1 << BitSize(ColorCount))) {
 147         return NULL;
 148     }
 149
 150     Object = ungif_alloc(sizeof(ColorMapObject));
 151     if (Object == NULL) {
 152         return NULL;
 153     }
 154
 155     Object->Colors = ungif_calloc(ColorCount, sizeof(GifColorType));
 156     if (Object->Colors == NULL) {
 157         ungif_free(Object);
 158         return NULL;
 159     }
 160
 161     Object->ColorCount = ColorCount;
 162     Object->BitsPerPixel = BitSize(ColorCount);
 163
 164     if (ColorMap) {
 165         memcpy(Object->Colors, ColorMap, ColorCount * sizeof(GifColorType));
 166     }
 167
 168     return (Object);
 169 }
 170
 171 /*
 172  * Free a color map object
 173  */
 174 static void
 175 FreeMapObject(ColorMapObject * Object) {
 176
 177     if (Object != NULL) {
 178         ungif_free(Object->Colors);
 179         ungif_free(Object);
 180         /*** FIXME:
 181          * When we are willing to break API we need to make this function
 182          * FreeMapObject(ColorMapObject **Object)
 183          * and do this assignment to NULL here:
 184          * *Object = NULL;
 185          */
 186     }
 187 }
 188
 189 static int
 190 AddExtensionBlock(Extensions *New,
 191                   int Len,
 192                   const unsigned char ExtData[]) {
 193
 194     ExtensionBlock *ep;
 195
 196     if (New->ExtensionBlocks == NULL)
 197         New->ExtensionBlocks = ungif_alloc(sizeof(ExtensionBlock));
 198     else
 199         New->ExtensionBlocks = ungif_realloc(New->ExtensionBlocks,
 200                                       sizeof(ExtensionBlock) *
 201                                       (New->ExtensionBlockCount + 1));
 202
 203     if (New->ExtensionBlocks == NULL)
 204         return (GIF_ERROR);
 205
 206     ep = &New->ExtensionBlocks[New->ExtensionBlockCount++];
 207
 208     ep->ByteCount=Len + 3;
 209     ep->Bytes = ungif_alloc(ep->ByteCount + 3);
 210     if (ep->Bytes == NULL)
 211         return (GIF_ERROR);
 212
 213     /* Extension Header */
 214     ep->Bytes[0] = 0x21;
 215     ep->Bytes[1] = New->Function;
 216     ep->Bytes[2] = Len;
 217
 218     if (ExtData) {
 219         memcpy(ep->Bytes + 3, ExtData, Len);
 220         ep->Function = New->Function;
 221     }
 222
 223     return (GIF_OK);
 224 }
 225
 226 static int
 227 AppendExtensionBlock(Extensions *New,
 228                      int Len,
 229                      const unsigned char ExtData[])
 230 {
 231     ExtensionBlock *ep;
 232
 233     if (New->ExtensionBlocks == NULL)
 234         return (GIF_ERROR);
 235
 236     ep = &New->ExtensionBlocks[New->ExtensionBlockCount - 1];
 237
 238     ep->Bytes = ungif_realloc(ep->Bytes, ep->ByteCount + Len + 1);
 239     if (ep->Bytes == NULL)
 240         return (GIF_ERROR);
 241
 242     ep->Bytes[ep->ByteCount] = Len;
 243
 244     if (ExtData)
 245         memcpy(ep->Bytes + ep->ByteCount + 1, ExtData, Len);
 246
 247     ep->ByteCount += Len + 1;
 248
 249     return (GIF_OK);
 250 }
 251
 252 static void
 253 FreeExtension(Extensions *Extensions)
 254 {
 255     ExtensionBlock *ep;
 256
 257     if ((Extensions == NULL) || (Extensions->ExtensionBlocks == NULL)) {
 258         return;
 259     }
 260     for (ep = Extensions->ExtensionBlocks;
 261          ep < (Extensions->ExtensionBlocks + Extensions->ExtensionBlockCount); ep++)
 262         ungif_free(ep->Bytes);
 263     ungif_free(Extensions->ExtensionBlocks);
 264     Extensions->ExtensionBlocks = NULL;
 265 }
 266
 267 /******************************************************************************
 268  * Image block allocation functions
 269 ******************************************************************************/
 270
 271 static void
 272 FreeSavedImages(GifFileType * GifFile) {
 273
 274     SavedImage *sp;
 275
 276     if ((GifFile == NULL) || (GifFile->SavedImages == NULL)) {
 277         return;
 278     }
 279     for (sp = GifFile->SavedImages;
 280          sp < GifFile->SavedImages + GifFile->ImageCount; sp++) {
 281         if (sp->ImageDesc.ColorMap) {
 282             FreeMapObject(sp->ImageDesc.ColorMap);
 283             sp->ImageDesc.ColorMap = NULL;
 284         }
 285
 286         ungif_free(sp->RasterBits);
 287
 288         if (sp->Extensions.ExtensionBlocks)
 289             FreeExtension(&sp->Extensions);
 290     }
 291     ungif_free(GifFile->SavedImages);
 292     GifFile->SavedImages=NULL;
 293 }
 294
 295 /******************************************************************************
 296  * This routine should be called before any other DGif calls. Note that
 297  * this routine is called automatically from DGif file open routines.
 298  *****************************************************************************/
 299 static int
 300 DGifGetScreenDesc(GifFileType * GifFile) {
 301
 302     int i, BitsPerPixel, SortFlag;
 303     GifByteType Buf[3];
 304
 305     /* Put the screen descriptor into the file: */
 306     if (DGifGetWord(GifFile, &GifFile->SWidth) == GIF_ERROR ||
 307         DGifGetWord(GifFile, &GifFile->SHeight) == GIF_ERROR)
 308         return GIF_ERROR;
 309
 310     if (READ(GifFile, Buf, 3) != 3) {
 311         return GIF_ERROR;
 312     }
 313     GifFile->SColorResolution = (((Buf[0] & 0x70) + 1) >> 4) + 1;
 314     SortFlag = (Buf[0] & 0x08) != 0;
 315     BitsPerPixel = (Buf[0] & 0x07) + 1;
 316     GifFile->SBackGroundColor = Buf[1];
 317     GifFile->SAspectRatio = Buf[2];
 318     if (Buf[0] & 0x80) {    /* Do we have global color map? */
 319
 320         GifFile->SColorMap = MakeMapObject(1 << BitsPerPixel, NULL);
 321         if (GifFile->SColorMap == NULL) {
 322             return GIF_ERROR;
 323         }
 324
 325         /* Get the global color map: */
 326         GifFile->SColorMap->SortFlag = SortFlag;
 327         for (i = 0; i < GifFile->SColorMap->ColorCount; i++) {
 328             if (READ(GifFile, Buf, 3) != 3) {
 329                 FreeMapObject(GifFile->SColorMap);
 330                 GifFile->SColorMap = NULL;
 331                 return GIF_ERROR;
 332             }
 333             GifFile->SColorMap->Colors[i].Red = Buf[0];
 334             GifFile->SColorMap->Colors[i].Green = Buf[1];
 335             GifFile->SColorMap->Colors[i].Blue = Buf[2];
 336         }
 337     } else {
 338         GifFile->SColorMap = NULL;
 339     }
 340
 341     return GIF_OK;
 342 }
 343
 344 /******************************************************************************
 345  * This routine should be called before any attempt to read an image.
 346  *****************************************************************************/
 347 static int
 348 DGifGetRecordType(GifFileType * GifFile,
 349                   GifRecordType * Type) {
 350
 351     GifByteType Buf;
 352
 353     if (READ(GifFile, &Buf, 1) != 1) {
 354         /* Wine-specific behavior: Native accepts broken GIF files that have no
 355          * terminator, so we match this by treating EOF as a terminator. */
 356         *Type = TERMINATE_RECORD_TYPE;
 357         return GIF_OK;
 358     }
 359
 360     switch (Buf) {
 361       case ',':
 362           *Type = IMAGE_DESC_RECORD_TYPE;
 363           break;
 364       case '!':
 365           *Type = EXTENSION_RECORD_TYPE;
 366           break;
 367       case ';':
 368           *Type = TERMINATE_RECORD_TYPE;
 369           break;
 370       default:
 371           *Type = UNDEFINED_RECORD_TYPE;
 372           return GIF_ERROR;
 373     }
 374
 375     return GIF_OK;
 376 }
 377
 378 /******************************************************************************
 379  * This routine should be called before any attempt to read an image.
 380  * Note it is assumed the Image desc. header (',') has been read.
 381  *****************************************************************************/
 382 static int
 383 DGifGetImageDesc(GifFileType * GifFile) {
 384
 385     int i, BitsPerPixel, SortFlag;
 386     GifByteType Buf[3];
 387     GifFilePrivateType *Private = GifFile->Private;
 388     SavedImage *sp;
 389
 390     if (DGifGetWord(GifFile, &GifFile->Image.Left) == GIF_ERROR ||
 391         DGifGetWord(GifFile, &GifFile->Image.Top) == GIF_ERROR ||
 392         DGifGetWord(GifFile, &GifFile->Image.Width) == GIF_ERROR ||
 393         DGifGetWord(GifFile, &GifFile->Image.Height) == GIF_ERROR)
 394         return GIF_ERROR;
 395     if (READ(GifFile, Buf, 1) != 1) {
 396         return GIF_ERROR;
 397     }
 398     BitsPerPixel = (Buf[0] & 0x07) + 1;
 399     SortFlag = (Buf[0] & 0x20) != 0;
 400     GifFile->Image.Interlace = (Buf[0] & 0x40);
 401     if (Buf[0] & 0x80) {    /* Does this image have local color map? */
 402
 403         FreeMapObject(GifFile->Image.ColorMap);
 404
 405         GifFile->Image.ColorMap = MakeMapObject(1 << BitsPerPixel, NULL);
 406         if (GifFile->Image.ColorMap == NULL) {
 407             return GIF_ERROR;
 408         }
 409
 410         /* Get the image local color map: */
 411         GifFile->Image.ColorMap->SortFlag = SortFlag;
 412         for (i = 0; i < GifFile->Image.ColorMap->ColorCount; i++) {
 413             if (READ(GifFile, Buf, 3) != 3) {
 414                 FreeMapObject(GifFile->Image.ColorMap);
 415                 GifFile->Image.ColorMap = NULL;
 416                 return GIF_ERROR;
 417             }
 418             GifFile->Image.ColorMap->Colors[i].Red = Buf[0];
 419             GifFile->Image.ColorMap->Colors[i].Green = Buf[1];
 420             GifFile->Image.ColorMap->Colors[i].Blue = Buf[2];
 421         }
 422     } else if (GifFile->Image.ColorMap) {
 423         FreeMapObject(GifFile->Image.ColorMap);
 424         GifFile->Image.ColorMap = NULL;
 425     }
 426
 427     if (GifFile->SavedImages) {
 428         if ((GifFile->SavedImages = ungif_realloc(GifFile->SavedImages,
 429                                       sizeof(SavedImage) *
 430                                       (GifFile->ImageCount + 1))) == NULL) {
 431             return GIF_ERROR;
 432         }
 433     } else {
 434         if ((GifFile->SavedImages = ungif_alloc(sizeof(SavedImage))) == NULL) {
 435             return GIF_ERROR;
 436         }
 437     }
 438
 439     sp = &GifFile->SavedImages[GifFile->ImageCount];
 440     sp->ImageDesc = GifFile->Image;
 441     if (GifFile->Image.ColorMap != NULL) {
 442         sp->ImageDesc.ColorMap = MakeMapObject(
 443                                  GifFile->Image.ColorMap->ColorCount,
 444                                  GifFile->Image.ColorMap->Colors);
 445         if (sp->ImageDesc.ColorMap == NULL) {
 446             return GIF_ERROR;
 447         }
 448         sp->ImageDesc.ColorMap->SortFlag = GifFile->Image.ColorMap->SortFlag;
 449     }
 450     sp->RasterBits = NULL;
 451     sp->Extensions.ExtensionBlockCount = 0;
 452     sp->Extensions.ExtensionBlocks = NULL;
 453
 454     GifFile->ImageCount++;
 455
 456     Private->PixelCount = (long)GifFile->Image.Width *
 457        (long)GifFile->Image.Height;
 458
 459     DGifSetupDecompress(GifFile);  /* Reset decompress algorithm parameters. */
 460
 461     return GIF_OK;
 462 }
 463
 464 /******************************************************************************
 465  * Get one full scanned line (Line) of length LineLen from GIF file.
 466  *****************************************************************************/
 467 static int
 468 DGifGetLine(GifFileType * GifFile,
 469             GifPixelType * Line,
 470             int LineLen) {
 471
 472     GifByteType *Dummy;
 473     GifFilePrivateType *Private = GifFile->Private;
 474
 475     if (!LineLen)
 476         LineLen = GifFile->Image.Width;
 477
 478     if ((Private->PixelCount -= LineLen) > 0xffff0000UL) {
 479         return GIF_ERROR;
 480     }
 481
 482     if (DGifDecompressLine(GifFile, Line, LineLen) == GIF_OK) {
 483         if (Private->PixelCount == 0) {
 484             /* We probably would not be called any more, so lets clean
 485              * everything before we return: need to flush out all rest of
 486              * image until empty block (size 0) detected. We use GetCodeNext. */
 487             do
 488                 if (DGifGetCodeNext(GifFile, &Dummy) == GIF_ERROR)
 489                 {
 490                     WARN("GIF is not properly terminated\n");
 491                     break;
 492                 }
 493             while (Dummy != NULL) ;
 494         }
 495         return GIF_OK;
 496     } else
 497         return GIF_ERROR;
 498 }
 499
 500 /******************************************************************************
 501  * Get an extension block (see GIF manual) from gif file. This routine only
 502  * returns the first data block, and DGifGetExtensionNext should be called
 503  * after this one until NULL extension is returned.
 504  * The Extension should NOT be freed by the user (not dynamically allocated).
 505  * Note it is assumed the Extension desc. header ('!') has been read.
 506  *****************************************************************************/
 507 static int
 508 DGifGetExtension(GifFileType * GifFile,
 509                  int *ExtCode,
 510                  GifByteType ** Extension) {
 511
 512     GifByteType Buf;
 513
 514     if (READ(GifFile, &Buf, 1) != 1) {
 515         return GIF_ERROR;
 516     }
 517     *ExtCode = Buf;
 518
 519     return DGifGetExtensionNext(GifFile, Extension);
 520 }
 521
 522 /******************************************************************************
 523  * Get a following extension block (see GIF manual) from gif file. This
 524  * routine should be called until NULL Extension is returned.
 525  * The Extension should NOT be freed by the user (not dynamically allocated).
 526  *****************************************************************************/
 527 static int
 528 DGifGetExtensionNext(GifFileType * GifFile,
 529                      GifByteType ** Extension) {
 530
 531     GifByteType Buf;
 532     GifFilePrivateType *Private = GifFile->Private;
 533
 534     if (READ(GifFile, &Buf, 1) != 1) {
 535         return GIF_ERROR;
 536     }
 537     if (Buf > 0) {
 538         *Extension = Private->Buf;    /* Use private unused buffer. */
 539         (*Extension)[0] = Buf;  /* Pascal strings notation (pos. 0 is len.). */
 540         if (READ(GifFile, &((*Extension)[1]), Buf) != Buf) {
 541             return GIF_ERROR;
 542         }
 543     } else
 544         *Extension = NULL;
 545
 546     return GIF_OK;
 547 }
 548
 549 /******************************************************************************
 550  * Get 2 bytes (word) from the given file:
 551  *****************************************************************************/
 552 static int
 553 DGifGetWord(GifFileType * GifFile,
 554             GifWord *Word) {
 555
 556     unsigned char c[2];
 557
 558     if (READ(GifFile, c, 2) != 2) {
 559         return GIF_ERROR;
 560     }
 561
 562     *Word = (((unsigned int)c[1]) << 8) + c[0];
 563     return GIF_OK;
 564 }
 565
 566 /******************************************************************************
 567  * Continue to get the image code in compressed form. This routine should be
 568  * called until NULL block is returned.
 569  * The block should NOT be freed by the user (not dynamically allocated).
 570  *****************************************************************************/
 571 static int
 572 DGifGetCodeNext(GifFileType * GifFile,
 573                 GifByteType ** CodeBlock) {
 574
 575     GifByteType Buf;
 576     GifFilePrivateType *Private = GifFile->Private;
 577
 578     if (READ(GifFile, &Buf, 1) != 1) {
 579         return GIF_ERROR;
 580     }
 581
 582     if (Buf > 0) {
 583         *CodeBlock = Private->Buf;    /* Use private unused buffer. */
 584         (*CodeBlock)[0] = Buf;  /* Pascal strings notation (pos. 0 is len.). */
 585         if (READ(GifFile, &((*CodeBlock)[1]), Buf) != Buf) {
 586             return GIF_ERROR;
 587         }
 588     } else {
 589         *CodeBlock = NULL;
 590         Private->Buf[0] = 0;    /* Make sure the buffer is empty! */
 591         Private->PixelCount = 0;    /* And local info. indicate image read. */
 592     }
 593
 594     return GIF_OK;
 595 }
 596
 597 /******************************************************************************
 598  * Setup the LZ decompression for this image:
 599  *****************************************************************************/
 600 static int
 601 DGifSetupDecompress(GifFileType * GifFile) {
 602
 603     int i, BitsPerPixel;
 604     GifByteType CodeSize;
 605     GifPrefixType *Prefix;
 606     GifFilePrivateType *Private = GifFile->Private;
 607
 608     READ(GifFile, &CodeSize, 1);    /* Read Code size from file. */
 609     BitsPerPixel = CodeSize;
 610
 611     Private->Buf[0] = 0;    /* Input Buffer empty. */
 612     Private->BitsPerPixel = BitsPerPixel;
 613     Private->ClearCode = (1 << BitsPerPixel);
 614     Private->EOFCode = Private->ClearCode + 1;
 615     Private->RunningCode = Private->EOFCode + 1;
 616     Private->RunningBits = BitsPerPixel + 1;    /* Number of bits per code. */
 617     Private->MaxCode1 = 1 << Private->RunningBits;    /* Max. code + 1. */
 618     Private->StackPtr = 0;    /* No pixels on the pixel stack. */
 619     Private->LastCode = NO_SUCH_CODE;
 620     Private->CrntShiftState = 0;    /* No information in CrntShiftDWord. */
 621     Private->CrntShiftDWord = 0;
 622
 623     Prefix = Private->Prefix;
 624     for (i = 0; i <= LZ_MAX_CODE; i++)
 625         Prefix[i] = NO_SUCH_CODE;
 626
 627     return GIF_OK;
 628 }
 629
 630 /******************************************************************************
 631  * The LZ decompression routine:
 632  * This version decompress the given gif file into Line of length LineLen.
 633  * This routine can be called few times (one per scan line, for example), in
 634  * order the complete the whole image.
 635  *****************************************************************************/
 636 static int
 637 DGifDecompressLine(GifFileType * GifFile,
 638                    GifPixelType * Line,
 639                    int LineLen) {
 640
 641     int i = 0;
 642     int j, CrntCode, EOFCode, ClearCode, CrntPrefix, LastCode, StackPtr;
 643     GifByteType *Stack, *Suffix;
 644     GifPrefixType *Prefix;
 645     GifFilePrivateType *Private = GifFile->Private;
 646
 647     StackPtr = Private->StackPtr;
 648     Prefix = Private->Prefix;
 649     Suffix = Private->Suffix;
 650     Stack = Private->Stack;
 651     EOFCode = Private->EOFCode;
 652     ClearCode = Private->ClearCode;
 653     LastCode = Private->LastCode;
 654
 655     if (StackPtr != 0) {
 656         /* Let pop the stack off before continuing to read the gif file: */
 657         while (StackPtr != 0 && i < LineLen)
 658             Line[i++] = Stack[--StackPtr];
 659     }
 660
 661     while (i < LineLen) {    /* Decode LineLen items. */
 662         if (DGifDecompressInput(GifFile, &CrntCode) == GIF_ERROR)
 663             return GIF_ERROR;
 664
 665         if (CrntCode == EOFCode) {
 666             /* Note, however, that usually we will not be here as we will stop
 667              * decoding as soon as we got all the pixel, or EOF code will
 668              * not be read at all, and DGifGetLine/Pixel clean everything.  */
 669             if (i != LineLen - 1 || Private->PixelCount != 0) {
 670                 return GIF_ERROR;
 671             }
 672             i++;
 673         } else if (CrntCode == ClearCode) {
 674             /* We need to start over again: */
 675             for (j = 0; j <= LZ_MAX_CODE; j++)
 676                 Prefix[j] = NO_SUCH_CODE;
 677             Private->RunningCode = Private->EOFCode + 1;
 678             Private->RunningBits = Private->BitsPerPixel + 1;
 679             Private->MaxCode1 = 1 << Private->RunningBits;
 680             LastCode = Private->LastCode = NO_SUCH_CODE;
 681         } else {
 682             /* It's a regular code - if in pixel range simply add it to output
 683              * stream, otherwise trace to codes linked list until the prefix
 684              * is in pixel range: */
 685             if (CrntCode < ClearCode) {
 686                 /* This is simple - its pixel scalar, so add it to output: */
 687                 Line[i++] = CrntCode;
 688             } else {
 689                 /* It's a code to be traced: trace the linked list
 690                  * until the prefix is a pixel, while pushing the suffix
 691                  * pixels on our stack. If we done, pop the stack in reverse
 692                  * order (that's what stack is good for!) for output.  */
 693                 if (Prefix[CrntCode] == NO_SUCH_CODE) {
 694                     /* Only allowed if CrntCode is exactly the running code:
 695                      * In that case CrntCode = XXXCode, CrntCode or the
 696                      * prefix code is last code and the suffix char is
 697                      * exactly the prefix of last code! */
 698                     if (CrntCode == Private->RunningCode - 2) {
 699                         CrntPrefix = LastCode;
 700                         Suffix[Private->RunningCode - 2] =
 701                            Stack[StackPtr++] = DGifGetPrefixChar(Prefix,
 702                                                                  LastCode,
 703                                                                  ClearCode);
 704                     } else {
 705                         return GIF_ERROR;
 706                     }
 707                 } else
 708                     CrntPrefix = CrntCode;
 709
 710                 /* Now (if image is O.K.) we should not get a NO_SUCH_CODE
 711                  * during the trace. As we might loop forever, in case of
 712                  * defective image, we count the number of loops we trace
 713                  * and stop if we got LZ_MAX_CODE. Obviously we cannot
 714                  * loop more than that.  */
 715                 j = 0;
 716                 while (j++ <= LZ_MAX_CODE &&
 717                        CrntPrefix > ClearCode && CrntPrefix <= LZ_MAX_CODE) {
 718                     Stack[StackPtr++] = Suffix[CrntPrefix];
 719                     CrntPrefix = Prefix[CrntPrefix];
 720                 }
 721                 if (j >= LZ_MAX_CODE || CrntPrefix > LZ_MAX_CODE) {
 722                     return GIF_ERROR;
 723                 }
 724                 /* Push the last character on stack: */
 725                 Stack[StackPtr++] = CrntPrefix;
 726
 727                 /* Now lets pop all the stack into output: */
 728                 while (StackPtr != 0 && i < LineLen)
 729                     Line[i++] = Stack[--StackPtr];
 730             }
 731             if (LastCode != NO_SUCH_CODE) {
 732                 Prefix[Private->RunningCode - 2] = LastCode;
 733
 734                 if (CrntCode == Private->RunningCode - 2) {
 735                     /* Only allowed if CrntCode is exactly the running code:
 736                      * In that case CrntCode = XXXCode, CrntCode or the
 737                      * prefix code is last code and the suffix char is
 738                      * exactly the prefix of last code! */
 739                     Suffix[Private->RunningCode - 2] =
 740                        DGifGetPrefixChar(Prefix, LastCode, ClearCode);
 741                 } else {
 742                     Suffix[Private->RunningCode - 2] =
 743                        DGifGetPrefixChar(Prefix, CrntCode, ClearCode);
 744                 }
 745             }
 746             LastCode = CrntCode;
 747         }
 748     }
 749
 750     Private->LastCode = LastCode;
 751     Private->StackPtr = StackPtr;
 752
 753     return GIF_OK;
 754 }
 755
 756 /******************************************************************************
 757  * Routine to trace the Prefixes linked list until we get a prefix which is
 758  * not code, but a pixel value (less than ClearCode). Returns that pixel value.
 759  * If image is defective, we might loop here forever, so we limit the loops to
 760  * the maximum possible if image O.k. - LZ_MAX_CODE times.
 761  *****************************************************************************/
 762 static int
 763 DGifGetPrefixChar(const GifPrefixType *Prefix,
 764                   int Code,
 765                   int ClearCode) {
 766
 767     int i = 0;
 768
 769     while (Code > ClearCode && i++ <= LZ_MAX_CODE)
 770         Code = Prefix[Code];
 771     return Code;
 772 }
 773
 774 /******************************************************************************
 775  * The LZ decompression input routine:
 776  * This routine is responsible for the decompression of the bit stream from
 777  * 8 bits (bytes) packets, into the real codes.
 778  * Returns GIF_OK if read successfully.
 779  *****************************************************************************/
 780 static int
 781 DGifDecompressInput(GifFileType * GifFile,
 782                     int *Code) {
 783
 784     GifFilePrivateType *Private = GifFile->Private;
 785
 786     GifByteType NextByte;
 787     static const unsigned short CodeMasks[] = {
 788         0x0000, 0x0001, 0x0003, 0x0007,
 789         0x000f, 0x001f, 0x003f, 0x007f,
 790         0x00ff, 0x01ff, 0x03ff, 0x07ff,
 791         0x0fff
 792     };
 793     /* The image can't contain more than LZ_BITS per code. */
 794     if (Private->RunningBits > LZ_BITS) {
 795         return GIF_ERROR;
 796     }
 797
 798     while (Private->CrntShiftState < Private->RunningBits) {
 799         /* Needs to get more bytes from input stream for next code: */
 800         if (DGifBufferedInput(GifFile, Private->Buf, &NextByte) == GIF_ERROR) {
 801             return GIF_ERROR;
 802         }
 803         Private->CrntShiftDWord |=
 804            ((unsigned long)NextByte) << Private->CrntShiftState;
 805         Private->CrntShiftState += 8;
 806     }
 807     *Code = Private->CrntShiftDWord & CodeMasks[Private->RunningBits];
 808
 809     Private->CrntShiftDWord >>= Private->RunningBits;
 810     Private->CrntShiftState -= Private->RunningBits;
 811
 812     /* If code cannot fit into RunningBits bits, must raise its size. Note
 813      * however that codes above 4095 are used for special signaling.
 814      * If we're using LZ_BITS bits already and we're at the max code, just
 815      * keep using the table as it is, don't increment Private->RunningCode.
 816      */
 817     if (Private->RunningCode < LZ_MAX_CODE + 2 &&
 818             ++Private->RunningCode > Private->MaxCode1 &&
 819             Private->RunningBits < LZ_BITS) {
 820         Private->MaxCode1 <<= 1;
 821         Private->RunningBits++;
 822     }
 823     return GIF_OK;
 824 }
 825
 826 /******************************************************************************
 827  * This routines read one gif data block at a time and buffers it internally
 828  * so that the decompression routine could access it.
 829  * The routine returns the next byte from its internal buffer (or read next
 830  * block in if buffer empty) and returns GIF_OK if successful.
 831  *****************************************************************************/
 832 static int
 833 DGifBufferedInput(GifFileType * GifFile,
 834                   GifByteType * Buf,
 835                   GifByteType * NextByte) {
 836
 837     if (Buf[0] == 0) {
 838         /* Needs to read the next buffer - this one is empty: */
 839         if (READ(GifFile, Buf, 1) != 1) {
 840             return GIF_ERROR;
 841         }
 842         /* There shouldn't be any empty data blocks here as the LZW spec
 843          * says the LZW termination code should come first.  Therefore we
 844          * shouldn't be inside this routine at that point.
 845          */
 846         if (Buf[0] == 0) {
 847             return GIF_ERROR;
 848         }
 849         if (READ(GifFile, &Buf[1], Buf[0]) != Buf[0]) {
 850             return GIF_ERROR;
 851         }
 852         *NextByte = Buf[1];
 853         Buf[1] = 2;    /* We use now the second place as last char read! */
 854         Buf[0]--;
 855     } else {
 856         *NextByte = Buf[Buf[1]++];
 857         Buf[0]--;
 858     }
 859
 860     return GIF_OK;
 861 }
 862
 863 /******************************************************************************
 864  * This routine reads an entire GIF into core, hanging all its state info off
 865  * the GifFileType pointer.  Call DGifOpenFileName() or DGifOpenFileHandle()
 866  * first to initialize I/O.  Its inverse is EGifSpew().
 867  ******************************************************************************/
 868 int
 869 DGifSlurp(GifFileType * GifFile) {
 870
 871     int ImageSize;
 872     GifRecordType RecordType;
 873     SavedImage *sp;
 874     GifByteType *ExtData;
 875     Extensions temp_save;
 876
 877     temp_save.ExtensionBlocks = NULL;
 878     temp_save.ExtensionBlockCount = 0;
 879
 880     do {
 881         if (DGifGetRecordType(GifFile, &RecordType) == GIF_ERROR)
 882             return (GIF_ERROR);
 883
 884         switch (RecordType) {
 885           case IMAGE_DESC_RECORD_TYPE:
 886               if (DGifGetImageDesc(GifFile) == GIF_ERROR)
 887                   return (GIF_ERROR);
 888
 889               sp = &GifFile->SavedImages[GifFile->ImageCount - 1];
 890               ImageSize = sp->ImageDesc.Width * sp->ImageDesc.Height;
 891
 892               sp->RasterBits = ungif_alloc(ImageSize * sizeof(GifPixelType));
 893               if (sp->RasterBits == NULL) {
 894                   return GIF_ERROR;
 895               }
 896               if (DGifGetLine(GifFile, sp->RasterBits, ImageSize) ==
 897                   GIF_ERROR)
 898                   return (GIF_ERROR);
 899               if (temp_save.ExtensionBlocks) {
 900                   sp->Extensions.ExtensionBlocks = temp_save.ExtensionBlocks;
 901                   sp->Extensions.ExtensionBlockCount = temp_save.ExtensionBlockCount;
 902
 903                   temp_save.ExtensionBlocks = NULL;
 904                   temp_save.ExtensionBlockCount = 0;
 905
 906                   /* FIXME: The following is wrong.  It is left in only for
 907                    * backwards compatibility.  Someday it should go away. Use
 908                    * the sp->ExtensionBlocks->Function variable instead. */
 909                   sp->Extensions.Function = sp->Extensions.ExtensionBlocks[0].Function;
 910               }
 911               break;
 912
 913           case EXTENSION_RECORD_TYPE:
 914           {
 915               int Function;
 916               Extensions *Extensions;
 917
 918               if (DGifGetExtension(GifFile, &Function, &ExtData) == GIF_ERROR)
 919                   return (GIF_ERROR);
 920
 921               if (GifFile->ImageCount || Function == GRAPHICS_EXT_FUNC_CODE)
 922                   Extensions = &temp_save;
 923               else
 924                   Extensions = &GifFile->Extensions;
 925
 926               Extensions->Function = Function;
 927
 928               if (ExtData)
 929               {
 930                   /* Create an extension block with our data */
 931                   if (AddExtensionBlock(Extensions, ExtData[0], &ExtData[1]) == GIF_ERROR)
 932                       return (GIF_ERROR);
 933               }
 934               else /* Empty extension block */
 935               {
 936                   if (AddExtensionBlock(Extensions, 0, NULL) == GIF_ERROR)
 937                       return (GIF_ERROR);
 938               }
 939
 940               while (ExtData != NULL) {
 941                   int Len;
 942                   GifByteType *Data;
 943
 944                   if (DGifGetExtensionNext(GifFile, &ExtData) == GIF_ERROR)
 945                       return (GIF_ERROR);
 946
 947                   if (ExtData)
 948                   {
 949                       Len = ExtData[0];
 950                       Data = &ExtData[1];
 951                   }
 952                   else
 953                   {
 954                       Len = 0;
 955                       Data = NULL;
 956                   }
 957
 958                   if (AppendExtensionBlock(Extensions, Len, Data) == GIF_ERROR)
 959                       return (GIF_ERROR);
 960               }
 961               break;
 962           }
 963
 964           case TERMINATE_RECORD_TYPE:
 965               break;
 966
 967           default:    /* Should be trapped by DGifGetRecordType */
 968               break;
 969         }
 970     } while (RecordType != TERMINATE_RECORD_TYPE);
 971
 972     /* Just in case the Gif has an extension block without an associated
 973      * image... (Should we save this into a savefile structure with no image
 974      * instead? Have to check if the present writing code can handle that as
 975      * well.... */
 976     if (temp_save.ExtensionBlocks)
 977         FreeExtension(&temp_save);
 978
 979     return (GIF_OK);
 980 }
 981
 982 /******************************************************************************
 983  * GifFileType constructor with user supplied input function (TVT)
 984  *****************************************************************************/
 985 GifFileType *
 986 DGifOpen(void *userData,
 987          InputFunc readFunc) {
 988
 989     unsigned char Buf[GIF_STAMP_LEN + 1];
 990     GifFileType *GifFile;
 991     GifFilePrivateType *Private;
 992
 993     GifFile = ungif_alloc(sizeof(GifFileType));
 994     if (GifFile == NULL) {
 995         return NULL;
 996     }
 997
 998     memset(GifFile, '\0', sizeof(GifFileType));
 999
1000     Private = ungif_alloc(sizeof(GifFilePrivateType));
1001     if (!Private) {
1002         ungif_free(GifFile);
1003         return NULL;
1004     }
1005
1006     GifFile->Private = (void*)Private;
1007
1008     Private->Read = readFunc;    /* TVT */
1009     GifFile->UserData = userData;    /* TVT */
1010
1011     /* Lets see if this is a GIF file: */
1012     if (READ(GifFile, Buf, GIF_STAMP_LEN) != GIF_STAMP_LEN) {
1013         ungif_free(Private);
1014         ungif_free(GifFile);
1015         return NULL;
1016     }
1017
1018     /* The GIF Version number is ignored at this time. Maybe we should do
1019      * something more useful with it. */
1020     Buf[GIF_STAMP_LEN] = 0;
1021     if (memcmp(GIF_STAMP, Buf, GIF_VERSION_POS) != 0) {
1022         ungif_free(Private);
1023         ungif_free(GifFile);
1024         return NULL;
1025     }
1026
1027     if (DGifGetScreenDesc(GifFile) == GIF_ERROR) {
1028         ungif_free(Private);
1029         ungif_free(GifFile);
1030         return NULL;
1031     }
1032
1033     return GifFile;
1034 }
1035
1036 /******************************************************************************
1037  * This routine should be called last, to close the GIF file.
1038  *****************************************************************************/
1039 int
1040 DGifCloseFile(GifFileType * GifFile) {
1041
1042     GifFilePrivateType *Private;
1043
1044     if (GifFile == NULL)
1045         return GIF_ERROR;
1046
1047     Private = GifFile->Private;
1048
1049     if (GifFile->Image.ColorMap) {
1050         FreeMapObject(GifFile->Image.ColorMap);
1051         GifFile->Image.ColorMap = NULL;
1052     }
1053
1054     if (GifFile->SColorMap) {
1055         FreeMapObject(GifFile->SColorMap);
1056         GifFile->SColorMap = NULL;
1057     }
1058
1059     ungif_free(Private);
1060     Private = NULL;
1061
1062     if (GifFile->SavedImages) {
1063         FreeSavedImages(GifFile);
1064         GifFile->SavedImages = NULL;
1065     }
1066
1067     FreeExtension(&GifFile->Extensions);
1068
1069     ungif_free(GifFile);
1070
1071     return GIF_OK;
1072 }