1/**********************************************************************************************
2*
3* rgif.h v0.5
4*
5* Original implementation (gif.h) by Charlie Tangora [ctangora -at- gmail -dot- com]
6* adapted to C99, reformatted and renamed by Ramon Santamaria (@raysan5)
7*
8* This file offers a simple, very limited way to create animated GIFs directly in code.
9*
10* Those looking for particular cleverness are likely to be disappointed; it's pretty
11* much a straight-ahead implementation of the GIF format with optional Floyd-Steinberg
12* dithering. (It does at least use delta encoding - only the changed portions of each
13* frame are saved.)
14*
15* So resulting files are often quite large. The hope is that it will be handy nonetheless
16* as a quick and easily-integrated way for programs to spit out animations.
17*
18* Only RGBA8 is currently supported as an input format. (The alpha is ignored.)
19*
20* CONFIGURATION:
21*
22* #define RGIF_IMPLEMENTATION
23* Generates the implementation of the library into the included file.
24* If not defined, the library is in header only mode and can be included in other headers
25* or source files without problems. But only ONE file should hold the implementation.
26*
27* USAGE:
28* 1) Create a GifWriter struct. Pass it to GifBegin() to initialize and write the header.
29* 2) Pass subsequent frames to GifWriteFrame().
30* 3) Finally, call GifEnd() to close the file handle and free memory.
31*
32*
33* LICENSE: This software is available under 2 licenses -- choose whichever you prefer
34*
35* ALTERNATIVE A - MIT License
36*
37* Copyright (c) 2017-2019 Ramon Santamaria (@raysan5)
38*
39* Permission is hereby granted, free of charge, to any person obtaining a copy of
40* this software and associated documentation files (the "Software"), to deal in
41* the Software without restriction, including without limitation the rights to
42* use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
43* of the Software, and to permit persons to whom the Software is furnished to do
44* so, subject to the following conditions:
45*
46* The above copyright notice and this permission notice shall be included in all
47* copies or substantial portions of the Software.
48*
49* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
50* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
51* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
52* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
53* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
54* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
55*
56* ------------------------------------------------------------------------------
57*
58* ALTERNATIVE B - public domain (www.unlicense.org)
59*
60* This is free and unencumbered software released into the public domain.
61* Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
62* software, either in source code form or as a compiled binary, for any purpose,
63* commercial or non-commercial, and by any means.
64*
65* In jurisdictions that recognize copyright laws, the author or authors of this
66* software dedicate any and all copyright interest in the software to the public
67* domain. We make this dedication for the benefit of the public at large and to
68* the detriment of our heirs and successors. We intend this dedication to be an
69* overt act of relinquishment in perpetuity of all present and future rights to
70* this software under copyright law.
71*
72* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
73* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
74* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
75* AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
76* ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
77* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
78*
79**********************************************************************************************/
80
81#ifndef RGIF_H
82#define RGIF_H
83
84#include <stdio.h> // Required for: FILE
85
86//#define RGIF_STATIC
87#ifdef RGIF_STATIC
88 #define RGIFDEF static // Functions just visible to module including this file
89#else
90 #ifdef __cplusplus
91 #define RGIFDEF extern "C" // Functions visible from other files (no name mangling of functions in C++)
92 #else
93 #define RGIFDEF extern // Functions visible from other files
94 #endif
95#endif
96
97//----------------------------------------------------------------------------------
98// Module Functions Declaration
99//----------------------------------------------------------------------------------
100
101// NOTE: By default use bitDepth = 8, dither = false
102RGIFDEF bool GifBegin(const char *filename, unsigned int width, unsigned int height, unsigned int delay, unsigned int bitDepth, bool dither);
103RGIFDEF bool GifWriteFrame(const unsigned char *image, unsigned int width, unsigned int height, unsigned int delay, int bitDepth, bool dither);
104RGIFDEF bool GifEnd();
105
106#endif // RGIF_H
107
108
109/***********************************************************************************
110*
111 * GIF IMPLEMENTATION
112*
113************************************************************************************/
114
115#if defined(RGIF_IMPLEMENTATION)
116
117#include <stdio.h> // Required for: FILE, fopen(), fclose()
118#include <string.h> // Required for: memcpy()
119
120// Check if custom malloc/free functions defined, if not, using standard ones
121// RGIF_MALLOC and RGIF_FREE are used only by GifBegin and GifEnd respectively,
122// to allocate a buffer the size of the image, which is used to find changed pixels for delta-encoding.
123#if !defined(RGIF_MALLOC)
124 #include <stdlib.h> // Required for: malloc(), free()
125
126 #define RGIF_MALLOC(size) malloc(size)
127 #define RGIF_FREE(ptr) free(ptr)
128#endif
129
130//----------------------------------------------------------------------------------
131// Defines and Macros
132//----------------------------------------------------------------------------------
133#define GIFMIN(a, b) (((a)<(b))?(a):(b))
134#define GIFMAX(a, b) (((a)>(b))?(a):(b))
135#define GIFABS(x) ((x)<0?-(x):(x))
136
137//----------------------------------------------------------------------------------
138// Types and Structures Definition
139//----------------------------------------------------------------------------------
140
141// Gif palette structure
142typedef struct GifPalette {
143 int bitDepth;
144
145 unsigned char r[256];
146 unsigned char g[256];
147 unsigned char b[256];
148
149 // k-d tree over RGB space, organized in heap fashion
150 // i.e. left child of node i is node i*2, right child is node i*2 + 1
151 // nodes 256-511 are implicitly the leaves, containing a color
152 unsigned char treeSplitElt[255];
153 unsigned char treeSplit[255];
154} GifPalette;
155
156
157// Simple structure to write out the LZW-compressed
158// portion of the imageone bit at a time
159typedef struct GifBitStatus {
160 unsigned char bitIndex; // how many bits in the partial byte written so far
161 unsigned char byte; // current partial byte
162
163 unsigned int chunkIndex;
164 unsigned char chunk[256]; // bytes are written in here until we have 256 of them, then written to the file
165} GifBitStatus;
166
167// The LZW dictionary is a 256-ary tree constructed
168// as the file is encoded, this is one node
169typedef struct GifLzwNode {
170 unsigned short m_next[256];
171} GifLzwNode;
172
173//----------------------------------------------------------------------------------
174// Global Variables Definition
175//----------------------------------------------------------------------------------
176const int gifTransparentIndex = 0; // Transparent color index
177
178static FILE *gifFile = NULL;
179unsigned char *gifFrame;
180
181//----------------------------------------------------------------------------------
182// Module specific Functions Declaration
183//----------------------------------------------------------------------------------
184static void GifGetClosestPaletteColor(GifPalette *pPal, int r, int g, int b, int *bestInd, int *bestDiff, int treeRoot);
185static void GifSwapPixels(unsigned char *image, int pixA, int pixB);
186static int GifPartition(unsigned char *image, const int left, const int right, const int elt, int pivotIndex);
187static void GifPartitionByMedian(unsigned char *image, int left, int right, int com, int neededCenter);
188static void GifSplitPalette(unsigned char *image, int numPixels, int firstElt, int lastElt, int splitElt, int splitDist, int treeNode, bool buildForDither, GifPalette *pal);
189static int GifPickChangedPixels(const unsigned char *lastFrame, unsigned char *frame, int numPixels);
190static void GifMakePalette(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned int width, unsigned int height, int bitDepth, bool buildForDither, GifPalette *pPal);
191static void GifDitherImage(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned char *outFrame, unsigned int width, unsigned int height, GifPalette *pPal);
192static void GifThresholdImage(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned char *outFrame, unsigned int width, unsigned int height, GifPalette *pPal);
193static void GifWriteBit(GifBitStatus *stat, unsigned int bit);
194
195static void GifWriteChunk(FILE *f, GifBitStatus *stat);
196static void GifWritePalette(FILE *f, const GifPalette *pPal);
197static void GifWriteCode(FILE *f, GifBitStatus *stat, unsigned int code, unsigned int length);
198static void GifWriteLzwImage(FILE *f, unsigned char *image, unsigned int left, unsigned int top, unsigned int width, unsigned int height, unsigned int delay, GifPalette *pPal);
199
200//----------------------------------------------------------------------------------
201// Module Functions Definition
202//----------------------------------------------------------------------------------
203
204// Creates a gif file
205// NOTE: Initializes internal file pointer (only one gif recording at a time)
206// The delay value is the time between frames in hundredths of a second - note that not all viewers pay much attention to this value.
207RGIFDEF bool GifBegin(const char *filename, unsigned int width, unsigned int height, unsigned int delay, unsigned int bitDepth, bool dither)
208{
209#if _MSC_VER >= 1400
210 gifFile = 0;
211 fopen_s(&gifFile, filename, "wb");
212#else
213 gifFile = fopen(filename, "wb");
214#endif
215
216 if (!gifFile) return false;
217
218 // Allocate space for one gif frame
219 gifFrame = (unsigned char *)RGIF_MALLOC(width*height*4);
220
221 // GIF Header
222 fputs("GIF89a",gifFile);
223
224 // Reference: http://www.onicos.com/staff/iz/formats/gif.html
225
226 // GIF Screen Descriptor
227 fputc(width & 0xff, gifFile);
228 fputc((width >> 8) & 0xff, gifFile); // Screen width (2 byte)
229 fputc(height & 0xff, gifFile);
230 fputc((height >> 8) & 0xff, gifFile); // Screen height (2 byte)
231
232 fputc(0xf0, gifFile); // Color table flags: unsorted global color table of 2 entries (1 byte, bit-flags)
233 fputc(0, gifFile); // Background color index
234 fputc(0, gifFile); // Pixel Aspect Ratio (square, we need to specify this because it's 1989)
235
236 // GIF Global Color table (just a dummy palette)
237 // Color 0: black
238 fputc(0, gifFile);
239 fputc(0, gifFile);
240 fputc(0, gifFile);
241 // Color 1: also black
242 fputc(0, gifFile);
243 fputc(0, gifFile);
244 fputc(0, gifFile);
245
246 if (delay != 0)
247 {
248 // Application Extension Block (19 bytes long)
249 fputc(0x21, gifFile); // GIF Extension code
250 fputc(0xff, gifFile); // Application Extension Label
251 fputc(11, gifFile); // Length of Application Block (11 byte)
252 fputs("NETSCAPE2.0", gifFile); // Application Identifier (Netscape 2.0 block)
253
254 fputc(0x03, gifFile); // Length of Data Sub-Block (3 bytes)
255 fputc(0x01, gifFile); // 0x01
256 fputc(0x00, gifFile); // This specifies the number of times,
257 fputc(0x00, gifFile); // the loop should be executed (infinitely)
258
259 fputc(0x00, gifFile); // Data Sub-Block Terminator.
260 }
261
262 return true;
263}
264
265// Writes out a new frame to a GIF in progress.
266// NOTE: gifFile should have been initialized with GifBegin()
267// AFAIK, it is legal to use different bit depths for different frames of an image -
268// this may be handy to save bits in animations that don't change much.
269RGIFDEF bool GifWriteFrame(const unsigned char *image, unsigned int width, unsigned int height, unsigned int delay, int bitDepth, bool dither)
270{
271 if (!gifFile) return false;
272
273 const unsigned char *oldImage = gifFrame;
274
275 GifPalette pal;
276 GifMakePalette((dither ? NULL : oldImage), image, width, height, bitDepth, dither, &pal);
277
278 if (dither) GifDitherImage(oldImage, image, gifFrame, width, height, &pal);
279 else GifThresholdImage(oldImage, image, gifFrame, width, height, &pal);
280
281 GifWriteLzwImage(gifFile, gifFrame, 0, 0, width, height, delay, &pal);
282
283 return true;
284}
285
286// Writes the EOF code, closes the file handle, and frees temp memory used by a GIF.
287// Many if not most viewers will still display a GIF properly if the EOF code is missing,
288// but it's still a good idea to write it out.
289RGIFDEF bool GifEnd()
290{
291 if (!gifFile) return false;
292
293 fputc(0x3b, gifFile); // Trailer (end of file)
294 fclose(gifFile);
295
296 RGIF_FREE(gifFrame);
297
298 gifFile = NULL;
299 gifFrame = NULL;
300
301 return true;
302}
303
304//----------------------------------------------------------------------------------
305// Module specific Functions Definition
306//----------------------------------------------------------------------------------
307// walks the k-d tree to pick the palette entry for a desired color.
308// Takes as in/out parameters the current best color and its error -
309// only changes them if it finds a better color in its subtree.
310// this is the major hotspot in the code at the moment.
311static void GifGetClosestPaletteColor(GifPalette *pPal, int r, int g, int b, int *bestInd, int *bestDiff, int treeRoot)
312{
313 // base case, reached the bottom of the tree
314 if (treeRoot > (1<<pPal->bitDepth)-1)
315 {
316 int ind = treeRoot-(1<<pPal->bitDepth);
317 if (ind == gifTransparentIndex) return;
318
319 // check whether this color is better than the current winner
320 int r_err = r - ((int)pPal->r[ind]);
321 int g_err = g - ((int)pPal->g[ind]);
322 int b_err = b - ((int)pPal->b[ind]);
323 int diff = GIFABS(r_err)+GIFABS(g_err)+GIFABS(b_err);
324
325 if (diff < *bestDiff)
326 {
327 *bestInd = ind;
328 *bestDiff = diff;
329 }
330
331 return;
332 }
333
334 // take the appropriate color (r, g, or b) for this node of the k-d tree
335 int comps[3]; comps[0] = r; comps[1] = g; comps[2] = b;
336 int splitComp = comps[pPal->treeSplitElt[treeRoot]];
337
338 int splitPos = pPal->treeSplit[treeRoot];
339 if (splitPos > splitComp)
340 {
341 // check the left subtree
342 GifGetClosestPaletteColor(pPal, r, g, b, bestInd, bestDiff, treeRoot*2);
343
344 if (*bestDiff > (splitPos - splitComp))
345 {
346 // cannot prove there's not a better value in the right subtree, check that too
347 GifGetClosestPaletteColor(pPal, r, g, b, bestInd, bestDiff, treeRoot*2 + 1);
348 }
349 }
350 else
351 {
352 GifGetClosestPaletteColor(pPal, r, g, b, bestInd, bestDiff, treeRoot*2 + 1);
353
354 if (*bestDiff > splitComp - splitPos)
355 {
356 GifGetClosestPaletteColor(pPal, r, g, b, bestInd, bestDiff, treeRoot*2);
357 }
358 }
359}
360
361static void GifSwapPixels(unsigned char *image, int pixA, int pixB)
362{
363 unsigned char rA = image[pixA*4];
364 unsigned char gA = image[pixA*4 + 1];
365 unsigned char bA = image[pixA*4+2];
366 unsigned char aA = image[pixA*4+3];
367
368 unsigned char rB = image[pixB*4];
369 unsigned char gB = image[pixB*4 + 1];
370 unsigned char bB = image[pixB*4+2];
371 unsigned char aB = image[pixA*4+3];
372
373 image[pixA*4] = rB;
374 image[pixA*4 + 1] = gB;
375 image[pixA*4+2] = bB;
376 image[pixA*4+3] = aB;
377
378 image[pixB*4] = rA;
379 image[pixB*4 + 1] = gA;
380 image[pixB*4+2] = bA;
381 image[pixB*4+3] = aA;
382}
383
384// just the partition operation from quicksort
385static int GifPartition(unsigned char *image, const int left, const int right, const int elt, int pivotIndex)
386{
387 const int pivotValue = image[(pivotIndex)*4+elt];
388 GifSwapPixels(image, pivotIndex, right-1);
389 int storeIndex = left;
390 bool split = 0;
391 for (int ii=left; ii<right-1; ++ii)
392 {
393 int arrayVal = image[ii*4+elt];
394 if (arrayVal < pivotValue)
395 {
396 GifSwapPixels(image, ii, storeIndex);
397 ++storeIndex;
398 }
399 else if (arrayVal == pivotValue)
400 {
401 if (split)
402 {
403 GifSwapPixels(image, ii, storeIndex);
404 ++storeIndex;
405 }
406 split = !split;
407 }
408 }
409 GifSwapPixels(image, storeIndex, right-1);
410 return storeIndex;
411}
412
413// Perform an incomplete sort, finding all elements above and below the desired median
414static void GifPartitionByMedian(unsigned char *image, int left, int right, int com, int neededCenter)
415{
416 if (left < right-1)
417 {
418 int pivotIndex = left + (right-left)/2;
419
420 pivotIndex = GifPartition(image, left, right, com, pivotIndex);
421
422 // Only "sort" the section of the array that contains the median
423 if (pivotIndex > neededCenter)
424 GifPartitionByMedian(image, left, pivotIndex, com, neededCenter);
425
426 if (pivotIndex < neededCenter)
427 GifPartitionByMedian(image, pivotIndex + 1, right, com, neededCenter);
428 }
429}
430
431// Builds a palette by creating a balanced k-d tree of all pixels in the image
432static void GifSplitPalette(unsigned char *image, int numPixels, int firstElt, int lastElt, int splitElt, int splitDist,
433 int treeNode, bool buildForDither, GifPalette *pal)
434{
435 if (lastElt <= firstElt || numPixels == 0)
436 return;
437
438 // base case, bottom of the tree
439 if (lastElt == firstElt + 1)
440 {
441 if (buildForDither)
442 {
443 // Dithering needs at least one color as dark as anything
444 // in the image and at least one brightest color -
445 // otherwise it builds up error and produces strange artifacts
446 if (firstElt == 1)
447 {
448 // special case: the darkest color in the image
449 unsigned int r=255, g=255, b=255;
450 for (int ii=0; ii<numPixels; ++ii)
451 {
452 r = GIFMIN(r, image[ii*4+0]);
453 g = GIFMIN(g, image[ii*4 + 1]);
454 b = GIFMIN(b, image[ii*4+2]);
455 }
456
457 pal->r[firstElt] = r;
458 pal->g[firstElt] = g;
459 pal->b[firstElt] = b;
460
461 return;
462 }
463
464 if (firstElt == (1 << pal->bitDepth)-1)
465 {
466 // special case: the lightest color in the image
467 unsigned int r=0, g=0, b=0;
468 for (int ii=0; ii<numPixels; ++ii)
469 {
470 r = GIFMAX(r, image[ii*4+0]);
471 g = GIFMAX(g, image[ii*4 + 1]);
472 b = GIFMAX(b, image[ii*4+2]);
473 }
474
475 pal->r[firstElt] = r;
476 pal->g[firstElt] = g;
477 pal->b[firstElt] = b;
478
479 return;
480 }
481 }
482
483 // otherwise, take the average of all colors in this subcube
484 unsigned long long r=0, g=0, b=0;
485 for (int ii=0; ii<numPixels; ++ii)
486 {
487 r += image[ii*4+0];
488 g += image[ii*4 + 1];
489 b += image[ii*4+2];
490 }
491
492 r += numPixels / 2; // round to nearest
493 g += numPixels / 2;
494 b += numPixels / 2;
495
496 r /= numPixels;
497 g /= numPixels;
498 b /= numPixels;
499
500 pal->r[firstElt] = (unsigned char)r;
501 pal->g[firstElt] = (unsigned char)g;
502 pal->b[firstElt] = (unsigned char)b;
503
504 return;
505 }
506
507 // Find the axis with the largest range
508 int minR = 255, maxR = 0;
509 int minG = 255, maxG = 0;
510 int minB = 255, maxB = 0;
511 for (int ii=0; ii<numPixels; ++ii)
512 {
513 int r = image[ii*4+0];
514 int g = image[ii*4 + 1];
515 int b = image[ii*4+2];
516
517 if (r > maxR) maxR = r;
518 if (r < minR) minR = r;
519
520 if (g > maxG) maxG = g;
521 if (g < minG) minG = g;
522
523 if (b > maxB) maxB = b;
524 if (b < minB) minB = b;
525 }
526
527 int rRange = maxR - minR;
528 int gRange = maxG - minG;
529 int bRange = maxB - minB;
530
531 // 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)
532 int splitCom = 1;
533 if (bRange > gRange) splitCom = 2;
534 if (rRange > bRange && rRange > gRange) splitCom = 0;
535
536 int subPixelsA = numPixels *(splitElt - firstElt) / (lastElt - firstElt);
537 int subPixelsB = numPixels-subPixelsA;
538
539 GifPartitionByMedian(image, 0, numPixels, splitCom, subPixelsA);
540
541 pal->treeSplitElt[treeNode] = splitCom;
542 pal->treeSplit[treeNode] = image[subPixelsA*4+splitCom];
543
544 GifSplitPalette(image, subPixelsA, firstElt, splitElt, splitElt-splitDist, splitDist/2, treeNode*2, buildForDither, pal);
545 GifSplitPalette(image+subPixelsA*4, subPixelsB, splitElt, lastElt, splitElt+splitDist, splitDist/2, treeNode*2 + 1, buildForDither, pal);
546}
547
548// Finds all pixels that have changed from the previous image and
549// moves them to the fromt of th buffer.
550// This allows us to build a palette optimized for the colors of the
551// changed pixels only.
552static int GifPickChangedPixels(const unsigned char *lastFrame, unsigned char *frame, int numPixels)
553{
554 int numChanged = 0;
555 unsigned char *writeIter = frame;
556
557 for (int ii=0; ii<numPixels; ++ii)
558 {
559 if (lastFrame[0] != frame[0] ||
560 lastFrame[1] != frame[1] ||
561 lastFrame[2] != frame[2])
562 {
563 writeIter[0] = frame[0];
564 writeIter[1] = frame[1];
565 writeIter[2] = frame[2];
566 ++numChanged;
567 writeIter += 4;
568 }
569 lastFrame += 4;
570 frame += 4;
571 }
572
573 return numChanged;
574}
575
576// Creates a palette by placing all the image pixels in a k-d tree and then averaging the blocks at the bottom.
577// This is known as the "modified median split" technique
578static void GifMakePalette(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned int width, unsigned int height, int bitDepth, bool buildForDither, GifPalette *pPal)
579{
580 pPal->bitDepth = bitDepth;
581
582 // SplitPalette is destructive (it sorts the pixels by color) so
583 // we must create a copy of the image for it to destroy
584 int imageSize = width*height*4*sizeof(unsigned char);
585 unsigned char *destroyableImage = (unsigned char*)RGIF_MALLOC(imageSize);
586 memcpy(destroyableImage, nextFrame, imageSize);
587
588 int numPixels = width*height;
589 if (lastFrame)
590 numPixels = GifPickChangedPixels(lastFrame, destroyableImage, numPixels);
591
592 const int lastElt = 1 << bitDepth;
593 const int splitElt = lastElt/2;
594 const int splitDist = splitElt/2;
595
596 GifSplitPalette(destroyableImage, numPixels, 1, lastElt, splitElt, splitDist, 1, buildForDither, pPal);
597
598 RGIF_FREE(destroyableImage);
599
600 // add the bottom node for the transparency index
601 pPal->treeSplit[1 << (bitDepth-1)] = 0;
602 pPal->treeSplitElt[1 << (bitDepth-1)] = 0;
603
604 pPal->r[0] = pPal->g[0] = pPal->b[0] = 0;
605}
606
607// Implements Floyd-Steinberg dithering, writes palette value to alpha
608static void GifDitherImage(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned char *outFrame, unsigned int width, unsigned int height, GifPalette *pPal)
609{
610 int numPixels = width*height;
611
612 // quantPixels initially holds color*256 for all pixels
613 // The extra 8 bits of precision allow for sub-single-color error values
614 // to be propagated
615 int *quantPixels = (int*)RGIF_MALLOC(sizeof(int)*numPixels*4);
616
617 for (int ii=0; ii<numPixels*4; ++ii)
618 {
619 unsigned char pix = nextFrame[ii];
620 int pix16 = (int)pix*256;
621 quantPixels[ii] = pix16;
622 }
623
624 for (unsigned int yy=0; yy<height; ++yy)
625 {
626 for (unsigned int xx=0; xx<width; ++xx)
627 {
628 int *nextPix = quantPixels + 4*(yy*width+xx);
629 const unsigned char *lastPix = lastFrame? lastFrame + 4*(yy*width+xx) : NULL;
630
631 // Compute the colors we want (rounding to nearest)
632 int rr = (nextPix[0] + 127) / 256;
633 int gg = (nextPix[1] + 127) / 256;
634 int bb = (nextPix[2] + 127) / 256;
635
636 // if it happens that we want the color from last frame, then just write out
637 // a transparent pixel
638 if (lastFrame &&
639 lastPix[0] == rr &&
640 lastPix[1] == gg &&
641 lastPix[2] == bb)
642 {
643 nextPix[0] = rr;
644 nextPix[1] = gg;
645 nextPix[2] = bb;
646 nextPix[3] = gifTransparentIndex;
647 continue;
648 }
649
650 int bestDiff = 1000000;
651 int bestInd = gifTransparentIndex;
652
653 // Search the palete
654 GifGetClosestPaletteColor(pPal, rr, gg, bb, &bestInd, &bestDiff, 1);
655
656 // Write the result to the temp buffer
657 int r_err = nextPix[0] - (int)(pPal->r[bestInd])*256;
658 int g_err = nextPix[1] - (int)(pPal->g[bestInd])*256;
659 int b_err = nextPix[2] - (int)(pPal->b[bestInd])*256;
660
661 nextPix[0] = pPal->r[bestInd];
662 nextPix[1] = pPal->g[bestInd];
663 nextPix[2] = pPal->b[bestInd];
664 nextPix[3] = bestInd;
665
666 // Propagate the error to the four adjacent locations
667 // that we haven't touched yet
668 int quantloc_7 = (yy*width+xx + 1);
669 int quantloc_3 = (yy*width+width+xx-1);
670 int quantloc_5 = (yy*width+width+xx);
671 int quantloc_1 = (yy*width+width+xx + 1);
672
673 if (quantloc_7 < numPixels)
674 {
675 int *pix7 = quantPixels+4*quantloc_7;
676 pix7[0] += GIFMAX(-pix7[0], r_err*7 / 16);
677 pix7[1] += GIFMAX(-pix7[1], g_err*7 / 16);
678 pix7[2] += GIFMAX(-pix7[2], b_err*7 / 16);
679 }
680
681 if (quantloc_3 < numPixels)
682 {
683 int *pix3 = quantPixels+4*quantloc_3;
684 pix3[0] += GIFMAX(-pix3[0], r_err*3 / 16);
685 pix3[1] += GIFMAX(-pix3[1], g_err*3 / 16);
686 pix3[2] += GIFMAX(-pix3[2], b_err*3 / 16);
687 }
688
689 if (quantloc_5 < numPixels)
690 {
691 int *pix5 = quantPixels+4*quantloc_5;
692 pix5[0] += GIFMAX(-pix5[0], r_err*5 / 16);
693 pix5[1] += GIFMAX(-pix5[1], g_err*5 / 16);
694 pix5[2] += GIFMAX(-pix5[2], b_err*5 / 16);
695 }
696
697 if (quantloc_1 < numPixels)
698 {
699 int *pix1 = quantPixels+4*quantloc_1;
700 pix1[0] += GIFMAX(-pix1[0], r_err / 16);
701 pix1[1] += GIFMAX(-pix1[1], g_err / 16);
702 pix1[2] += GIFMAX(-pix1[2], b_err / 16);
703 }
704 }
705 }
706
707 // Copy the palettized result to the output buffer
708 for (int ii=0; ii<numPixels*4; ++ii)
709 {
710 outFrame[ii] = quantPixels[ii];
711 }
712
713 RGIF_FREE(quantPixels);
714}
715
716// Picks palette colors for the image using simple thresholding, no dithering
717static void GifThresholdImage(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned char *outFrame, unsigned int width, unsigned int height, GifPalette *pPal)
718{
719 unsigned int numPixels = width*height;
720 for (unsigned int ii=0; ii<numPixels; ++ii)
721 {
722 // if a previous color is available, and it matches the current color,
723 // set the pixel to transparent
724 if (lastFrame &&
725 lastFrame[0] == nextFrame[0] &&
726 lastFrame[1] == nextFrame[1] &&
727 lastFrame[2] == nextFrame[2])
728 {
729 outFrame[0] = lastFrame[0];
730 outFrame[1] = lastFrame[1];
731 outFrame[2] = lastFrame[2];
732 outFrame[3] = gifTransparentIndex;
733 }
734 else
735 {
736 // palettize the pixel
737 int bestDiff = 1000000;
738 int bestInd = 1;
739 GifGetClosestPaletteColor(pPal, nextFrame[0], nextFrame[1], nextFrame[2], &bestInd, &bestDiff, 1);
740
741 // Write the resulting color to the output buffer
742 outFrame[0] = pPal->r[bestInd];
743 outFrame[1] = pPal->g[bestInd];
744 outFrame[2] = pPal->b[bestInd];
745 outFrame[3] = bestInd;
746 }
747
748 if (lastFrame) lastFrame += 4;
749 outFrame += 4;
750 nextFrame += 4;
751 }
752}
753
754
755// insert a single bit
756static void GifWriteBit(GifBitStatus *stat, unsigned int bit)
757{
758 bit = bit & 1;
759 bit = bit << stat->bitIndex;
760 stat->byte |= bit;
761
762 ++stat->bitIndex;
763 if (stat->bitIndex > 7)
764 {
765 // move the newly-finished byte to the chunk buffer
766 stat->chunk[stat->chunkIndex++] = stat->byte;
767 // and start a new byte
768 stat->bitIndex = 0;
769 stat->byte = 0;
770 }
771}
772
773// write all bytes so far to the file
774static void GifWriteChunk(FILE *f, GifBitStatus *stat)
775{
776 fputc(stat->chunkIndex, f);
777 fwrite(stat->chunk, 1, stat->chunkIndex, f);
778
779 stat->bitIndex = 0;
780 stat->byte = 0;
781 stat->chunkIndex = 0;
782}
783
784static void GifWriteCode(FILE *f, GifBitStatus *stat, unsigned int code, unsigned int length)
785{
786 for (unsigned int ii=0; ii<length; ++ii)
787 {
788 GifWriteBit(stat, code);
789 code = code >> 1;
790
791 if (stat->chunkIndex == 255)
792 {
793 GifWriteChunk(f, stat);
794 }
795 }
796}
797
798// write a 256-color (8-bit) image palette to the file
799static void GifWritePalette(FILE *f, const GifPalette *pPal)
800{
801 fputc(0, f); // first color: transparency
802 fputc(0, f);
803 fputc(0, f);
804
805 for (int ii=1; ii<(1 << pPal->bitDepth); ++ii)
806 {
807 unsigned int r = pPal->r[ii];
808 unsigned int g = pPal->g[ii];
809 unsigned int b = pPal->b[ii];
810
811 fputc(r, f);
812 fputc(g, f);
813 fputc(b, f);
814 }
815}
816
817// write the image header, LZW-compress and write out the image
818static void GifWriteLzwImage(FILE *f, unsigned char *image, unsigned int left, unsigned int top, unsigned int width, unsigned int height, unsigned int delay, GifPalette *pPal)
819{
820 // graphics control extension
821 fputc(0x21, f);
822 fputc(0xf9, f);
823 fputc(0x04, f);
824 fputc(0x05, f); // leave prev frame in place, this frame has transparency
825 fputc(delay & 0xff, f);
826 fputc((delay >> 8) & 0xff, f);
827 fputc(gifTransparentIndex, f); // transparent color index
828 fputc(0, f);
829
830 fputc(0x2c, f); // image descriptor block
831
832 fputc(left & 0xff, f); // corner of image in canvas space
833 fputc((left >> 8) & 0xff, f);
834 fputc(top & 0xff, f);
835 fputc((top >> 8) & 0xff, f);
836
837 fputc(width & 0xff, f); // width and height of image
838 fputc((width >> 8) & 0xff, f);
839 fputc(height & 0xff, f);
840 fputc((height >> 8) & 0xff, f);
841
842 //fputc(0, f); // no local color table, no transparency
843 //fputc(0x80, f); // no local color table, but transparency
844
845 fputc(0x80 + pPal->bitDepth-1, f); // local color table present, 2 ^ bitDepth entries
846 GifWritePalette(f, pPal);
847
848 const int minCodeSize = pPal->bitDepth;
849 const unsigned int clearCode = 1 << pPal->bitDepth;
850
851 fputc(minCodeSize, f); // min code size 8 bits
852
853 GifLzwNode *codetree = (GifLzwNode *)RGIF_MALLOC(sizeof(GifLzwNode)*4096);
854
855 memset(codetree, 0, sizeof(GifLzwNode)*4096);
856 int curCode = -1;
857 unsigned int codeSize = minCodeSize + 1;
858 unsigned int maxCode = clearCode + 1;
859
860 GifBitStatus stat;
861 stat.byte = 0;
862 stat.bitIndex = 0;
863 stat.chunkIndex = 0;
864
865 GifWriteCode(f, &stat, clearCode, codeSize); // start with a fresh LZW dictionary
866
867 for (unsigned int yy=0; yy<height; ++yy)
868 {
869 for (unsigned int xx=0; xx<width; ++xx)
870 {
871 unsigned char nextValue = image[(yy*width+xx)*4+3];
872
873 // "loser mode" - no compression, every single code is followed immediately by a clear
874 //WriteCode(f, stat, nextValue, codeSize);
875 //WriteCode(f, stat, 256, codeSize);
876
877 if (curCode < 0)
878 {
879 // first value in a new run
880 curCode = nextValue;
881 }
882 else if (codetree[curCode].m_next[nextValue])
883 {
884 // current run already in the dictionary
885 curCode = codetree[curCode].m_next[nextValue];
886 }
887 else
888 {
889 // finish the current run, write a code
890 GifWriteCode(f, &stat, curCode, codeSize);
891
892 // insert the new run into the dictionary
893 codetree[curCode].m_next[nextValue] = ++maxCode;
894
895 if (maxCode >= (1ul << codeSize))
896 {
897 // dictionary entry count has broken a size barrier,
898 // we need more bits for codes
899 codeSize++;
900 }
901 if (maxCode == 4095)
902 {
903 // the dictionary is full, clear it out and begin anew
904 GifWriteCode(f, &stat, clearCode, codeSize); // clear tree
905
906 memset(codetree, 0, sizeof(GifLzwNode)*4096);
907 codeSize = minCodeSize + 1;
908 maxCode = clearCode + 1;
909 }
910
911 curCode = nextValue;
912 }
913 }
914 }
915
916 // compression footer
917 GifWriteCode(f, &stat, curCode, codeSize);
918 GifWriteCode(f, &stat, clearCode, codeSize);
919 GifWriteCode(f, &stat, clearCode + 1, minCodeSize + 1);
920
921 // write out the last partial chunk
922 while (stat.bitIndex) GifWriteBit(&stat, 0);
923 if (stat.chunkIndex) GifWriteChunk(f, &stat);
924
925 fputc(0, f); // image block terminator
926
927 RGIF_FREE(codetree);
928}
929
930#endif // RGIF_IMPLEMENTATION
931