example/gif.h

   1 //
   2 // gif.h
   3 // by Charlie Tangora
   4 // Public domain.
   5 // Email me : ctangora -at- gmail -dot- com
   6 //
   7 // This file offers a simple, very limited way to create animated GIFs directly in code.
   8 //
   9 // Those looking for particular cleverness are likely to be disappointed; it's pretty
  10 // much a straight-ahead implementation of the GIF format with optional Floyd-Steinberg
  11 // dithering. (It does at least use delta encoding - only the changed portions of each
  12 // frame are saved.)
  13 //
  14 // So resulting files are often quite large. The hope is that it will be handy nonetheless
  15 // as a quick and easily-integrated way for programs to spit out animations.
  16 //
  17 // Only RGBA8 is currently supported as an input format. (The alpha is ignored.)
  18 //
  19 // If capturing a buffer with a bottom-left origin (such as OpenGL), define GIF_FLIP_VERT
  20 // to automatically flip the buffer data when writing the image (the buffer itself is
  21 // unchanged.
  22 //
  23 // USAGE:
  24 // Create a GifWriter struct. Pass it to GifBegin() to initialize and write the header.
  25 // Pass subsequent frames to GifWriteFrame().
  26 // Finally, call GifEnd() to close the file handle and free memory.
  27 //
  28
  29 #ifndef gif_h
  30 #define gif_h
  31
  32 #include <stdio.h>   // for FILE*
  33 #include <string.h>  // for memcpy and bzero
  34 #include <stdint.h>  // for integer typedefs
  35
  36 // Define these macros to hook into a custom memory allocator.
  37 // TEMP_MALLOC and TEMP_FREE will only be called in stack fashion - frees in the reverse order of mallocs
  38 // and any temp memory allocated by a function will be freed before it exits.
  39 // MALLOC and FREE are used only by GifBegin and GifEnd respectively (to allocate a buffer the size of the image, which
  40 // is used to find changed pixels for delta-encoding.)
  41
  42 #ifndef GIF_TEMP_MALLOC
  43 #include <stdlib.h>
  44 #define GIF_TEMP_MALLOC malloc
  45 #endif
  46
  47 #ifndef GIF_TEMP_FREE
  48 #include <stdlib.h>
  49 #define GIF_TEMP_FREE free
  50 #endif
  51
  52 #ifndef GIF_MALLOC
  53 #include <stdlib.h>
  54 #define GIF_MALLOC malloc
  55 #endif
  56
  57 #ifndef GIF_FREE
  58 #include <stdlib.h>
  59 #define GIF_FREE free
  60 #endif
  61
  62 const int kGifTransIndex = 0;
  63
  64 struct GifPalette
  65 {
  66     int bitDepth;
  67
  68     uint8_t r[256];
  69     uint8_t g[256];
  70     uint8_t b[256];
  71
  72     // k-d tree over RGB space, organized in heap fashion
  73     // i.e. left child of node i is node i*2, right child is node i*2+1
  74     // nodes 256-511 are implicitly the leaves, containing a color
  75     uint8_t treeSplitElt[255];
  76     uint8_t treeSplit[255];
  77 };
  78
  79 // max, min, and abs functions
  80 int GifIMax(int l, int r) { return l>r?l:r; }
  81 int GifIMin(int l, int r) { return l<r?l:r; }
  82 int GifIAbs(int i) { return i<0?-i:i; }
  83
  84 // walks the k-d tree to pick the palette entry for a desired color.
  85 // Takes as in/out parameters the current best color and its error -
  86 // only changes them if it finds a better color in its subtree.
  87 // this is the major hotspot in the code at the moment.
  88 void GifGetClosestPaletteColor(GifPalette* pPal, int r, int g, int b, int& bestInd, int& bestDiff, int treeRoot = 1)
  89 {
  90     // base case, reached the bottom of the tree
  91     if(treeRoot > (1<<pPal->bitDepth)-1)
  92     {
  93         int ind = treeRoot-(1<<pPal->bitDepth);
  94         if(ind == kGifTransIndex) return;
  95
  96         // check whether this color is better than the current winner
  97         int r_err = r - ((int32_t)pPal->r[ind]);
  98         int g_err = g - ((int32_t)pPal->g[ind]);
  99         int b_err = b - ((int32_t)pPal->b[ind]);
 100         int diff = GifIAbs(r_err)+GifIAbs(g_err)+GifIAbs(b_err);
 101
 102         if(diff < bestDiff)
 103         {
 104             bestInd = ind;
 105             bestDiff = diff;
 106         }
 107
 108         return;
 109     }
 110
 111     // take the appropriate color (r, g, or b) for this node of the k-d tree
 112     int comps[3]; comps[0] = r; comps[1] = g; comps[2] = b;
 113     int splitComp = comps[pPal->treeSplitElt[treeRoot]];
 114
 115     int splitPos = pPal->treeSplit[treeRoot];
 116     if(splitPos > splitComp)
 117     {
 118         // check the left subtree
 119         GifGetClosestPaletteColor(pPal, r, g, b, bestInd, bestDiff, treeRoot*2);
 120         if( bestDiff > splitPos - splitComp )
 121         {
 122             // cannot prove there's not a better value in the right subtree, check that too
 123             GifGetClosestPaletteColor(pPal, r, g, b, bestInd, bestDiff, treeRoot*2+1);
 124         }
 125     }
 126     else
 127     {
 128         GifGetClosestPaletteColor(pPal, r, g, b, bestInd, bestDiff, treeRoot*2+1);
 129         if( bestDiff > splitComp - splitPos )
 130         {
 131             GifGetClosestPaletteColor(pPal, r, g, b, bestInd, bestDiff, treeRoot*2);
 132         }
 133     }
 134 }
 135
 136 void GifSwapPixels(uint8_t* image, int pixA, int pixB)
 137 {
 138     uint8_t rA = image[pixA*4];
 139     uint8_t gA = image[pixA*4+1];
 140     uint8_t bA = image[pixA*4+2];
 141     uint8_t aA = image[pixA*4+3];
 142
 143     uint8_t rB = image[pixB*4];
 144     uint8_t gB = image[pixB*4+1];
 145     uint8_t bB = image[pixB*4+2];
 146     uint8_t aB = image[pixA*4+3];
 147
 148     image[pixA*4] = rB;
 149     image[pixA*4+1] = gB;
 150     image[pixA*4+2] = bB;
 151     image[pixA*4+3] = aB;
 152
 153     image[pixB*4] = rA;
 154     image[pixB*4+1] = gA;
 155     image[pixB*4+2] = bA;
 156     image[pixB*4+3] = aA;
 157 }
 158
 159 // just the partition operation from quicksort
 160 int GifPartition(uint8_t* image, const int left, const int right, const int elt, int pivotIndex)
 161 {
 162     const int pivotValue = image[(pivotIndex)*4+elt];
 163     GifSwapPixels(image, pivotIndex, right-1);
 164     int storeIndex = left;
 165     bool split = 0;
 166     for(int ii=left; ii<right-1; ++ii)
 167     {
 168         int arrayVal = image[ii*4+elt];
 169         if( arrayVal < pivotValue )
 170         {
 171             GifSwapPixels(image, ii, storeIndex);
 172             ++storeIndex;
 173         }
 174         else if( arrayVal == pivotValue )
 175         {
 176             if(split)
 177             {
 178                 GifSwapPixels(image, ii, storeIndex);
 179                 ++storeIndex;
 180             }
 181             split = !split;
 182         }
 183     }
 184     GifSwapPixels(image, storeIndex, right-1);
 185     return storeIndex;
 186 }
 187
 188 // Perform an incomplete sort, finding all elements above and below the desired median
 189 void GifPartitionByMedian(uint8_t* image, int left, int right, int com, int neededCenter)
 190 {
 191     if(left < right-1)
 192     {
 193         int pivotIndex = left + (right-left)/2;
 194
 195         pivotIndex = GifPartition(image, left, right, com, pivotIndex);
 196
 197         // Only "sort" the section of the array that contains the median
 198         if(pivotIndex > neededCenter)
 199             GifPartitionByMedian(image, left, pivotIndex, com, neededCenter);
 200
 201         if(pivotIndex < neededCenter)
 202             GifPartitionByMedian(image, pivotIndex+1, right, com, neededCenter);
 203     }
 204 }
 205
 206 // Builds a palette by creating a balanced k-d tree of all pixels in the image
 207 void GifSplitPalette(uint8_t* image, int numPixels, int firstElt, int lastElt, int splitElt, int splitDist, int treeNode, bool buildForDither, GifPalette* pal)
 208 {
 209     if(lastElt <= firstElt || numPixels == 0)
 210         return;
 211
 212     // base case, bottom of the tree
 213     if(lastElt == firstElt+1)
 214     {
 215         if(buildForDither)
 216         {
 217             // Dithering needs at least one color as dark as anything
 218             // in the image and at least one brightest color -
 219             // otherwise it builds up error and produces strange artifacts
 220             if( firstElt == 1 )
 221             {
 222                 // special case: the darkest color in the image
 223                 uint32_t r=255, g=255, b=255;
 224                 for(int ii=0; ii<numPixels; ++ii)
 225                 {
 226                     r = (uint32_t)GifIMin((int32_t)r, image[ii * 4 + 0]);
 227                     g = (uint32_t)GifIMin((int32_t)g, image[ii * 4 + 1]);
 228                     b = (uint32_t)GifIMin((int32_t)b, image[ii * 4 + 2]);
 229                 }
 230
 231                 pal->r[firstElt] = (uint8_t)r;
 232                 pal->g[firstElt] = (uint8_t)g;
 233                 pal->b[firstElt] = (uint8_t)b;
 234
 235                 return;
 236             }
 237
 238             if( firstElt == (1 << pal->bitDepth)-1 )
 239             {
 240                 // special case: the lightest color in the image
 241                 uint32_t r=0, g=0, b=0;
 242                 for(int ii=0; ii<numPixels; ++ii)
 243                 {
 244                     r = (uint32_t)GifIMax((int32_t)r, image[ii * 4 + 0]);
 245                     g = (uint32_t)GifIMax((int32_t)g, image[ii * 4 + 1]);
 246                     b = (uint32_t)GifIMax((int32_t)b, image[ii * 4 + 2]);
 247                 }
 248
 249                 pal->r[firstElt] = (uint8_t)r;
 250                 pal->g[firstElt] = (uint8_t)g;
 251                 pal->b[firstElt] = (uint8_t)b;
 252
 253                 return;
 254             }
 255         }
 256
 257         // otherwise, take the average of all colors in this subcube
 258         uint64_t r=0, g=0, b=0;
 259         for(int ii=0; ii<numPixels; ++ii)
 260         {
 261             r += image[ii*4+0];
 262             g += image[ii*4+1];
 263             b += image[ii*4+2];
 264         }
 265
 266         r += (uint64_t)numPixels / 2;  // round to nearest
 267         g += (uint64_t)numPixels / 2;
 268         b += (uint64_t)numPixels / 2;
 269
 270         r /= (uint64_t)numPixels;
 271         g /= (uint64_t)numPixels;
 272         b /= (uint64_t)numPixels;
 273
 274         pal->r[firstElt] = (uint8_t)r;
 275         pal->g[firstElt] = (uint8_t)g;
 276         pal->b[firstElt] = (uint8_t)b;
 277
 278         return;
 279     }
 280
 281     // Find the axis with the largest range
 282     int minR = 255, maxR = 0;
 283     int minG = 255, maxG = 0;
 284     int minB = 255, maxB = 0;
 285     for(int ii=0; ii<numPixels; ++ii)
 286     {
 287         int r = image[ii*4+0];
 288         int g = image[ii*4+1];
 289         int b = image[ii*4+2];
 290
 291         if(r > maxR) maxR = r;
 292         if(r < minR) minR = r;
 293
 294         if(g > maxG) maxG = g;
 295         if(g < minG) minG = g;
 296
 297         if(b > maxB) maxB = b;
 298         if(b < minB) minB = b;
 299     }
 300
 301     int rRange = maxR - minR;
 302     int gRange = maxG - minG;
 303     int bRange = maxB - minB;
 304
 305     // and split along that axis. (incidentally, this means this isn't a "proper" k-d tree but I don't know what else to call it)
 306     int splitCom = 1;
 307     if(bRange > gRange) splitCom = 2;
 308     if(rRange > bRange && rRange > gRange) splitCom = 0;
 309
 310     int subPixelsA = numPixels * (splitElt - firstElt) / (lastElt - firstElt);
 311     int subPixelsB = numPixels-subPixelsA;
 312
 313     GifPartitionByMedian(image, 0, numPixels, splitCom, subPixelsA);
 314
 315     pal->treeSplitElt[treeNode] = (uint8_t)splitCom;
 316     pal->treeSplit[treeNode] = image[subPixelsA*4+splitCom];
 317
 318     GifSplitPalette(image,              subPixelsA, firstElt, splitElt, splitElt-splitDist, splitDist/2, treeNode*2,   buildForDither, pal);
 319     GifSplitPalette(image+subPixelsA*4, subPixelsB, splitElt, lastElt,  splitElt+splitDist, splitDist/2, treeNode*2+1, buildForDither, pal);
 320 }
 321
 322 // Finds all pixels that have changed from the previous image and
 323 // moves them to the fromt of th buffer.
 324 // This allows us to build a palette optimized for the colors of the
 325 // changed pixels only.
 326 int GifPickChangedPixels( const uint8_t* lastFrame, uint8_t* frame, int numPixels )
 327 {
 328     int numChanged = 0;
 329     uint8_t* writeIter = frame;
 330
 331     for (int ii=0; ii<numPixels; ++ii)
 332     {
 333         if(lastFrame[0] != frame[0] ||
 334            lastFrame[1] != frame[1] ||
 335            lastFrame[2] != frame[2])
 336         {
 337             writeIter[0] = frame[0];
 338             writeIter[1] = frame[1];
 339             writeIter[2] = frame[2];
 340             ++numChanged;
 341             writeIter += 4;
 342         }
 343         lastFrame += 4;
 344         frame += 4;
 345     }
 346
 347     return numChanged;
 348 }
 349
 350 // Creates a palette by placing all the image pixels in a k-d tree and then averaging the blocks at the bottom.
 351 // This is known as the "modified median split" technique
 352 void GifMakePalette( const uint8_t* lastFrame, const uint8_t* nextFrame, uint32_t width, uint32_t height, int bitDepth, bool buildForDither, GifPalette* pPal )
 353 {
 354     pPal->bitDepth = bitDepth;
 355
 356     // SplitPalette is destructive (it sorts the pixels by color) so
 357     // we must create a copy of the image for it to destroy
 358     size_t imageSize = (size_t)(width * height * 4 * sizeof(uint8_t));
 359     uint8_t* destroyableImage = (uint8_t*)GIF_TEMP_MALLOC(imageSize);
 360     memcpy(destroyableImage, nextFrame, imageSize);
 361
 362     int numPixels = (int)(width * height);
 363     if(lastFrame)
 364         numPixels = GifPickChangedPixels(lastFrame, destroyableImage, numPixels);
 365
 366     const int lastElt = 1 << bitDepth;
 367     const int splitElt = lastElt/2;
 368     const int splitDist = splitElt/2;
 369
 370     GifSplitPalette(destroyableImage, numPixels, 1, lastElt, splitElt, splitDist, 1, buildForDither, pPal);
 371
 372     GIF_TEMP_FREE(destroyableImage);
 373
 374     // add the bottom node for the transparency index
 375     pPal->treeSplit[1 << (bitDepth-1)] = 0;
 376     pPal->treeSplitElt[1 << (bitDepth-1)] = 0;
 377
 378     pPal->r[0] = pPal->g[0] = pPal->b[0] = 0;
 379 }
 380
 381 // Implements Floyd-Steinberg dithering, writes palette value to alpha
 382 void GifDitherImage( const uint8_t* lastFrame, const uint8_t* nextFrame, uint8_t* outFrame, uint32_t width, uint32_t height, GifPalette* pPal )
 383 {
 384     int numPixels = (int)(width * height);
 385
 386     // quantPixels initially holds color*256 for all pixels
 387     // The extra 8 bits of precision allow for sub-single-color error values
 388     // to be propagated
 389     int32_t *quantPixels = (int32_t *)GIF_TEMP_MALLOC(sizeof(int32_t) * (size_t)numPixels * 4);
 390
 391     for( int ii=0; ii<numPixels*4; ++ii )
 392     {
 393         uint8_t pix = nextFrame[ii];
 394         int32_t pix16 = int32_t(pix) * 256;
 395         quantPixels[ii] = pix16;
 396     }
 397
 398     for( uint32_t yy=0; yy<height; ++yy )
 399     {
 400         for( uint32_t xx=0; xx<width; ++xx )
 401         {
 402             int32_t* nextPix = quantPixels + 4*(yy*width+xx);
 403             const uint8_t* lastPix = lastFrame? lastFrame + 4*(yy*width+xx) : NULL;
 404
 405             // Compute the colors we want (rounding to nearest)
 406             int32_t rr = (nextPix[0] + 127) / 256;
 407             int32_t gg = (nextPix[1] + 127) / 256;
 408             int32_t bb = (nextPix[2] + 127) / 256;
 409
 410             // if it happens that we want the color from last frame, then just write out
 411             // a transparent pixel
 412             if( lastFrame &&
 413                lastPix[0] == rr &&
 414                lastPix[1] == gg &&
 415                lastPix[2] == bb )
 416             {
 417                 nextPix[0] = rr;
 418                 nextPix[1] = gg;
 419                 nextPix[2] = bb;
 420                 nextPix[3] = kGifTransIndex;
 421                 continue;
 422             }
 423
 424             int32_t bestDiff = 1000000;
 425             int32_t bestInd = kGifTransIndex;
 426
 427             // Search the palete
 428             GifGetClosestPaletteColor(pPal, rr, gg, bb, bestInd, bestDiff);
 429
 430             // Write the result to the temp buffer
 431             int32_t r_err = nextPix[0] - int32_t(pPal->r[bestInd]) * 256;
 432             int32_t g_err = nextPix[1] - int32_t(pPal->g[bestInd]) * 256;
 433             int32_t b_err = nextPix[2] - int32_t(pPal->b[bestInd]) * 256;
 434
 435             nextPix[0] = pPal->r[bestInd];
 436             nextPix[1] = pPal->g[bestInd];
 437             nextPix[2] = pPal->b[bestInd];
 438             nextPix[3] = bestInd;
 439
 440             // Propagate the error to the four adjacent locations
 441             // that we haven't touched yet
 442             int quantloc_7 = (int)(yy * width + xx + 1);
 443             int quantloc_3 = (int)(yy * width + width + xx - 1);
 444             int quantloc_5 = (int)(yy * width + width + xx);
 445             int quantloc_1 = (int)(yy * width + width + xx + 1);
 446
 447             if(quantloc_7 < numPixels)
 448             {
 449                 int32_t* pix7 = quantPixels+4*quantloc_7;
 450                 pix7[0] += GifIMax( -pix7[0], r_err * 7 / 16 );
 451                 pix7[1] += GifIMax( -pix7[1], g_err * 7 / 16 );
 452                 pix7[2] += GifIMax( -pix7[2], b_err * 7 / 16 );
 453             }
 454
 455             if(quantloc_3 < numPixels)
 456             {
 457                 int32_t* pix3 = quantPixels+4*quantloc_3;
 458                 pix3[0] += GifIMax( -pix3[0], r_err * 3 / 16 );
 459                 pix3[1] += GifIMax( -pix3[1], g_err * 3 / 16 );
 460                 pix3[2] += GifIMax( -pix3[2], b_err * 3 / 16 );
 461             }
 462
 463             if(quantloc_5 < numPixels)
 464             {
 465                 int32_t* pix5 = quantPixels+4*quantloc_5;
 466                 pix5[0] += GifIMax( -pix5[0], r_err * 5 / 16 );
 467                 pix5[1] += GifIMax( -pix5[1], g_err * 5 / 16 );
 468                 pix5[2] += GifIMax( -pix5[2], b_err * 5 / 16 );
 469             }
 470
 471             if(quantloc_1 < numPixels)
 472             {
 473                 int32_t* pix1 = quantPixels+4*quantloc_1;
 474                 pix1[0] += GifIMax( -pix1[0], r_err / 16 );
 475                 pix1[1] += GifIMax( -pix1[1], g_err / 16 );
 476                 pix1[2] += GifIMax( -pix1[2], b_err / 16 );
 477             }
 478         }
 479     }
 480
 481     // Copy the palettized result to the output buffer
 482     for( int ii=0; ii<numPixels*4; ++ii )
 483     {
 484         outFrame[ii] = (uint8_t)quantPixels[ii];
 485     }
 486
 487     GIF_TEMP_FREE(quantPixels);
 488 }
 489
 490 // Picks palette colors for the image using simple thresholding, no dithering
 491 void GifThresholdImage( const uint8_t* lastFrame, const uint8_t* nextFrame, uint8_t* outFrame, uint32_t width, uint32_t height, GifPalette* pPal )
 492 {
 493     uint32_t numPixels = width*height;
 494     for( uint32_t ii=0; ii<numPixels; ++ii )
 495     {
 496         // if a previous color is available, and it matches the current color,
 497         // set the pixel to transparent
 498         if(lastFrame &&
 499            lastFrame[0] == nextFrame[0] &&
 500            lastFrame[1] == nextFrame[1] &&
 501            lastFrame[2] == nextFrame[2])
 502         {
 503             outFrame[0] = lastFrame[0];
 504             outFrame[1] = lastFrame[1];
 505             outFrame[2] = lastFrame[2];
 506             outFrame[3] = kGifTransIndex;
 507         }
 508         else
 509         {
 510             // palettize the pixel
 511             int32_t bestDiff = 1000000;
 512             int32_t bestInd = 1;
 513             GifGetClosestPaletteColor(pPal, nextFrame[0], nextFrame[1], nextFrame[2], bestInd, bestDiff);
 514
 515             // Write the resulting color to the output buffer
 516             outFrame[0] = pPal->r[bestInd];
 517             outFrame[1] = pPal->g[bestInd];
 518             outFrame[2] = pPal->b[bestInd];
 519             outFrame[3] = (uint8_t)bestInd;
 520         }
 521
 522         if(lastFrame) lastFrame += 4;
 523         outFrame += 4;
 524         nextFrame += 4;
 525     }
 526 }
 527
 528 // Simple structure to write out the LZW-compressed portion of the image
 529 // one bit at a time
 530 struct GifBitStatus
 531 {
 532     uint8_t bitIndex;  // how many bits in the partial byte written so far
 533     uint8_t byte;      // current partial byte
 534
 535     uint32_t chunkIndex;
 536     uint8_t chunk[256];   // bytes are written in here until we have 256 of them, then written to the file
 537 };
 538
 539 // insert a single bit
 540 void GifWriteBit( GifBitStatus& stat, uint32_t bit )
 541 {
 542     bit = bit & 1;
 543     bit = bit << stat.bitIndex;
 544     stat.byte |= bit;
 545
 546     ++stat.bitIndex;
 547     if( stat.bitIndex > 7 )
 548     {
 549         // move the newly-finished byte to the chunk buffer
 550         stat.chunk[stat.chunkIndex++] = stat.byte;
 551         // and start a new byte
 552         stat.bitIndex = 0;
 553         stat.byte = 0;
 554     }
 555 }
 556
 557 // write all bytes so far to the file
 558 void GifWriteChunk( FILE* f, GifBitStatus& stat )
 559 {
 560     fputc((int)stat.chunkIndex, f);
 561     fwrite(stat.chunk, 1, stat.chunkIndex, f);
 562
 563     stat.bitIndex = 0;
 564     stat.byte = 0;
 565     stat.chunkIndex = 0;
 566 }
 567
 568 void GifWriteCode( FILE* f, GifBitStatus& stat, uint32_t code, uint32_t length )
 569 {
 570     for( uint32_t ii=0; ii<length; ++ii )
 571     {
 572         GifWriteBit(stat, code);
 573         code = code >> 1;
 574
 575         if( stat.chunkIndex == 255 )
 576         {
 577             GifWriteChunk(f, stat);
 578         }
 579     }
 580 }
 581
 582 // The LZW dictionary is a 256-ary tree constructed as the file is encoded,
 583 // this is one node
 584 struct GifLzwNode
 585 {
 586     uint16_t m_next[256];
 587 };
 588
 589 // write a 256-color (8-bit) image palette to the file
 590 void GifWritePalette( const GifPalette* pPal, FILE* f )
 591 {
 592     fputc(0, f);  // first color: transparency
 593     fputc(0, f);
 594     fputc(0, f);
 595
 596     for(int ii=1; ii<(1 << pPal->bitDepth); ++ii)
 597     {
 598         uint32_t r = pPal->r[ii];
 599         uint32_t g = pPal->g[ii];
 600         uint32_t b = pPal->b[ii];
 601
 602         fputc((int)r, f);
 603         fputc((int)g, f);
 604         fputc((int)b, f);
 605     }
 606 }
 607
 608 // write the image header, LZW-compress and write out the image
 609 void GifWriteLzwImage(FILE* f, uint8_t* image, uint32_t left, uint32_t top,  uint32_t width, uint32_t height, uint32_t delay, GifPalette* pPal)
 610 {
 611     // graphics control extension
 612     fputc(0x21, f);
 613     fputc(0xf9, f);
 614     fputc(0x04, f);
 615     fputc(0x05, f); // leave prev frame in place, this frame has transparency
 616     fputc(delay & 0xff, f);
 617     fputc((delay >> 8) & 0xff, f);
 618     fputc(kGifTransIndex, f); // transparent color index
 619     fputc(0, f);
 620
 621     fputc(0x2c, f); // image descriptor block
 622
 623     fputc(left & 0xff, f);           // corner of image in canvas space
 624     fputc((left >> 8) & 0xff, f);
 625     fputc(top & 0xff, f);
 626     fputc((top >> 8) & 0xff, f);
 627
 628     fputc(width & 0xff, f);          // width and height of image
 629     fputc((width >> 8) & 0xff, f);
 630     fputc(height & 0xff, f);
 631     fputc((height >> 8) & 0xff, f);
 632
 633     //fputc(0, f); // no local color table, no transparency
 634     //fputc(0x80, f); // no local color table, but transparency
 635
 636     fputc(0x80 + pPal->bitDepth-1, f); // local color table present, 2 ^ bitDepth entries
 637     GifWritePalette(pPal, f);
 638
 639     const int minCodeSize = pPal->bitDepth;
 640     const uint32_t clearCode = 1 << pPal->bitDepth;
 641
 642     fputc(minCodeSize, f); // min code size 8 bits
 643
 644     GifLzwNode* codetree = (GifLzwNode*)GIF_TEMP_MALLOC(sizeof(GifLzwNode)*4096);
 645
 646     memset(codetree, 0, sizeof(GifLzwNode)*4096);
 647     int32_t curCode = -1;
 648     uint32_t codeSize = (uint32_t)minCodeSize + 1;
 649     uint32_t maxCode = clearCode+1;
 650
 651     GifBitStatus stat;
 652     stat.byte = 0;
 653     stat.bitIndex = 0;
 654     stat.chunkIndex = 0;
 655
 656     GifWriteCode(f, stat, clearCode, codeSize);  // start with a fresh LZW dictionary
 657
 658     for(uint32_t yy=0; yy<height; ++yy)
 659     {
 660         for(uint32_t xx=0; xx<width; ++xx)
 661         {
 662     #ifdef GIF_FLIP_VERT
 663             // bottom-left origin image (such as an OpenGL capture)
 664             uint8_t nextValue = image[((height-1-yy)*width+xx)*4+3];
 665     #else
 666             // top-left origin
 667             uint8_t nextValue = image[(yy*width+xx)*4+3];
 668     #endif
 669
 670             // "loser mode" - no compression, every single code is followed immediately by a clear
 671             //WriteCode( f, stat, nextValue, codeSize );
 672             //WriteCode( f, stat, 256, codeSize );
 673
 674             if( curCode < 0 )
 675             {
 676                 // first value in a new run
 677                 curCode = nextValue;
 678             }
 679             else if( codetree[curCode].m_next[nextValue] )
 680             {
 681                 // current run already in the dictionary
 682                 curCode = codetree[curCode].m_next[nextValue];
 683             }
 684             else
 685             {
 686                 // finish the current run, write a code
 687                 GifWriteCode(f, stat, (uint32_t)curCode, codeSize);
 688
 689                 // insert the new run into the dictionary
 690                 codetree[curCode].m_next[nextValue] = (uint16_t)++maxCode;
 691
 692                 if( maxCode >= (1ul << codeSize) )
 693                 {
 694                     // dictionary entry count has broken a size barrier,
 695                     // we need more bits for codes
 696                     codeSize++;
 697                 }
 698                 if( maxCode == 4095 )
 699                 {
 700                     // the dictionary is full, clear it out and begin anew
 701                     GifWriteCode(f, stat, clearCode, codeSize); // clear tree
 702
 703                     memset(codetree, 0, sizeof(GifLzwNode)*4096);
 704                     codeSize = (uint32_t)(minCodeSize + 1);
 705                     maxCode = clearCode+1;
 706                 }
 707
 708                 curCode = nextValue;
 709             }
 710         }
 711     }
 712
 713     // compression footer
 714     GifWriteCode(f, stat, (uint32_t)curCode, codeSize);
 715     GifWriteCode(f, stat, clearCode, codeSize);
 716     GifWriteCode(f, stat, clearCode + 1, (uint32_t)minCodeSize + 1);
 717
 718     // write out the last partial chunk
 719     while( stat.bitIndex ) GifWriteBit(stat, 0);
 720     if( stat.chunkIndex ) GifWriteChunk(f, stat);
 721
 722     fputc(0, f); // image block terminator
 723
 724     GIF_TEMP_FREE(codetree);
 725 }
 726
 727 struct GifWriter
 728 {
 729     FILE* f;
 730     uint8_t* oldImage;
 731     bool firstFrame;
 732 };
 733
 734 // Creates a gif file.
 735 // The input GIFWriter is assumed to be uninitialized.
 736 // The delay value is the time between frames in hundredths of a second - note that not all viewers pay much attention to this value.
 737 bool GifBegin( GifWriter* writer, const char* filename, uint32_t width, uint32_t height, uint32_t delay, int32_t bitDepth = 8, bool dither = false )
 738 {
 739     (void)bitDepth; (void)dither; // Mute "Unused argument" warnings
 740 #if defined(_MSC_VER) && (_MSC_VER >= 1400)
 741         writer->f = 0;
 742     fopen_s(&writer->f, filename, "wb");
 743 #else
 744     writer->f = fopen(filename, "wb");
 745 #endif
 746     if(!writer->f) return false;
 747
 748     writer->firstFrame = true;
 749
 750     // allocate
 751     writer->oldImage = (uint8_t*)GIF_MALLOC(width*height*4);
 752
 753     fputs("GIF89a", writer->f);
 754
 755     // screen descriptor
 756     fputc(width & 0xff, writer->f);
 757     fputc((width >> 8) & 0xff, writer->f);
 758     fputc(height & 0xff, writer->f);
 759     fputc((height >> 8) & 0xff, writer->f);
 760
 761     fputc(0xf0, writer->f);  // there is an unsorted global color table of 2 entries
 762     fputc(0, writer->f);     // background color
 763     fputc(0, writer->f);     // pixels are square (we need to specify this because it's 1989)
 764
 765     // now the "global" palette (really just a dummy palette)
 766     // color 0: black
 767     fputc(0, writer->f);
 768     fputc(0, writer->f);
 769     fputc(0, writer->f);
 770     // color 1: also black
 771     fputc(0, writer->f);
 772     fputc(0, writer->f);
 773     fputc(0, writer->f);
 774
 775     if( delay != 0 )
 776     {
 777         // animation header
 778         fputc(0x21, writer->f); // extension
 779         fputc(0xff, writer->f); // application specific
 780         fputc(11, writer->f); // length 11
 781         fputs("NETSCAPE2.0", writer->f); // yes, really
 782         fputc(3, writer->f); // 3 bytes of NETSCAPE2.0 data
 783
 784         fputc(1, writer->f); // JUST BECAUSE
 785         fputc(0, writer->f); // loop infinitely (byte 0)
 786         fputc(0, writer->f); // loop infinitely (byte 1)
 787
 788         fputc(0, writer->f); // block terminator
 789     }
 790
 791     return true;
 792 }
 793
 794 // Writes out a new frame to a GIF in progress.
 795 // The GIFWriter should have been created by GIFBegin.
 796 // AFAIK, it is legal to use different bit depths for different frames of an image -
 797 // this may be handy to save bits in animations that don't change much.
 798 bool GifWriteFrame( GifWriter* writer, const uint8_t* image, uint32_t width, uint32_t height, uint32_t delay, int bitDepth = 8, bool dither = false )
 799 {
 800     if(!writer->f) return false;
 801
 802     const uint8_t* oldImage = writer->firstFrame? NULL : writer->oldImage;
 803     writer->firstFrame = false;
 804
 805     GifPalette pal;
 806     GifMakePalette((dither? NULL : oldImage), image, width, height, bitDepth, dither, &pal);
 807
 808     if(dither)
 809         GifDitherImage(oldImage, image, writer->oldImage, width, height, &pal);
 810     else
 811         GifThresholdImage(oldImage, image, writer->oldImage, width, height, &pal);
 812
 813     GifWriteLzwImage(writer->f, writer->oldImage, 0, 0, width, height, delay, &pal);
 814
 815     return true;
 816 }
 817
 818 // Writes the EOF code, closes the file handle, and frees temp memory used by a GIF.
 819 // Many if not most viewers will still display a GIF properly if the EOF code is missing,
 820 // but it's still a good idea to write it out.
 821 bool GifEnd( GifWriter* writer )
 822 {
 823     if(!writer->f) return false;
 824
 825     fputc(0x3b, writer->f); // end of file
 826     fclose(writer->f);
 827     GIF_FREE(writer->oldImage);
 828
 829     writer->f = NULL;
 830     writer->oldImage = NULL;
 831
 832     return true;
 833 }
 834
 835 #endif