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 |
102 | RGIFDEF bool GifBegin(const char *filename, unsigned int width, unsigned int height, unsigned int delay, unsigned int bitDepth, bool dither); |
103 | RGIFDEF bool GifWriteFrame(const unsigned char *image, unsigned int width, unsigned int height, unsigned int delay, int bitDepth, bool dither); |
104 | RGIFDEF 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 |
142 | typedef 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 |
159 | typedef 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 |
169 | typedef struct GifLzwNode { |
170 | unsigned short m_next[256]; |
171 | } GifLzwNode; |
172 | |
173 | //---------------------------------------------------------------------------------- |
174 | // Global Variables Definition |
175 | //---------------------------------------------------------------------------------- |
176 | const int gifTransparentIndex = 0; // Transparent color index |
177 | |
178 | static FILE *gifFile = NULL; |
179 | unsigned char *gifFrame; |
180 | |
181 | //---------------------------------------------------------------------------------- |
182 | // Module specific Functions Declaration |
183 | //---------------------------------------------------------------------------------- |
184 | static void GifGetClosestPaletteColor(GifPalette *pPal, int r, int g, int b, int *bestInd, int *bestDiff, int treeRoot); |
185 | static void GifSwapPixels(unsigned char *image, int pixA, int pixB); |
186 | static int GifPartition(unsigned char *image, const int left, const int right, const int elt, int pivotIndex); |
187 | static void GifPartitionByMedian(unsigned char *image, int left, int right, int com, int neededCenter); |
188 | static void GifSplitPalette(unsigned char *image, int numPixels, int firstElt, int lastElt, int splitElt, int splitDist, int treeNode, bool buildForDither, GifPalette *pal); |
189 | static int GifPickChangedPixels(const unsigned char *lastFrame, unsigned char *frame, int numPixels); |
190 | static void GifMakePalette(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned int width, unsigned int height, int bitDepth, bool buildForDither, GifPalette *pPal); |
191 | static void GifDitherImage(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned char *outFrame, unsigned int width, unsigned int height, GifPalette *pPal); |
192 | static void GifThresholdImage(const unsigned char *lastFrame, const unsigned char *nextFrame, unsigned char *outFrame, unsigned int width, unsigned int height, GifPalette *pPal); |
193 | static void GifWriteBit(GifBitStatus *stat, unsigned int bit); |
194 | |
195 | static void GifWriteChunk(FILE *f, GifBitStatus *stat); |
196 | static void GifWritePalette(FILE *f, const GifPalette *pPal); |
197 | static void GifWriteCode(FILE *f, GifBitStatus *stat, unsigned int code, unsigned int length); |
198 | static 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. |
207 | RGIFDEF 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. |
269 | RGIFDEF 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. |
289 | RGIFDEF 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. |
311 | static 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 | |
361 | static 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 |
385 | static 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 |
414 | static 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 |
432 | static 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. |
552 | static 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 |
578 | static 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 |
608 | static 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 |
717 | static 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 |
756 | static 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 |
774 | static 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 | |
784 | static 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 |
799 | static 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 |
818 | static 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 | |