GCC Code Coverage Report


Directory: ./
File: submodules/raylib/src/external/msf_gif.h
Date: 2023-09-29 04:53:15
Exec Total Coverage
Lines: 0 203 0.0%
Branches: 0 94 0.0%

Line Branch Exec Source
1 /*
2 HOW TO USE:
3
4 In exactly one translation unit (.c or .cpp file), #define MSF_GIF_IMPL before including the header, like so:
5
6 #define MSF_GIF_IMPL
7 #include "msf_gif.h"
8
9 Everywhere else, just include the header like normal.
10
11
12 USAGE EXAMPLE:
13
14 int width = 480, height = 320, centisecondsPerFrame = 5, bitDepth = 16;
15 MsfGifState gifState = {};
16 // msf_gif_bgra_flag = true; //optionally, set this flag if your pixels are in BGRA format instead of RGBA
17 // msf_gif_alpha_threshold = 128; //optionally, enable transparency (see function documentation below for details)
18 msf_gif_begin(&gifState, width, height);
19 msf_gif_frame(&gifState, ..., centisecondsPerFrame, bitDepth, width * 4); //frame 1
20 msf_gif_frame(&gifState, ..., centisecondsPerFrame, bitDepth, width * 4); //frame 2
21 msf_gif_frame(&gifState, ..., centisecondsPerFrame, bitDepth, width * 4); //frame 3, etc...
22 MsfGifResult result = msf_gif_end(&gifState);
23 if (result.data) {
24 FILE * fp = fopen("MyGif.gif", "wb");
25 fwrite(result.data, result.dataSize, 1, fp);
26 fclose(fp);
27 }
28 msf_gif_free(result);
29
30 Detailed function documentation can be found in the header section below.
31
32
33 ERROR HANDLING:
34
35 If memory allocation fails, the functions will signal the error via their return values.
36 If one function call fails, the library will free all of its allocations,
37 and all subsequent calls will safely no-op and return 0 until the next call to `msf_gif_begin()`.
38 Therefore, it's safe to check only the return value of `msf_gif_end()`.
39
40
41 REPLACING MALLOC:
42
43 This library uses malloc+realloc+free internally for memory allocation.
44 To facilitate integration with custom memory allocators, these calls go through macros, which can be redefined.
45 The expected function signature equivalents of the macros are as follows:
46
47 void * MSF_GIF_MALLOC(void * context, size_t newSize)
48 void * MSF_GIF_REALLOC(void * context, void * oldMemory, size_t oldSize, size_t newSize)
49 void MSF_GIF_FREE(void * context, void * oldMemory, size_t oldSize)
50
51 If your allocator needs a context pointer, you can set the `customAllocatorContext` field of the MsfGifState struct
52 before calling msf_gif_begin(), and it will be passed to all subsequent allocator macro calls.
53
54 The maximum number of bytes the library will allocate to encode a single gif is bounded by the following formula:
55 `(2 * 1024 * 1024) + (width * height * 8) + ((1024 + width * height * 1.5) * 3 * frameCount)`
56 The peak heap memory usage in bytes, if using a general-purpose heap allocator, is bounded by the following formula:
57 `(2 * 1024 * 1024) + (width * height * 9.5) + 1024 + (16 * frameCount) + (2 * sizeOfResultingGif)
58
59
60 See end of file for license information.
61 */
62
63 //version 2.2
64
65 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
66 /// HEADER ///
67 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
68
69 #ifndef MSF_GIF_H
70 #define MSF_GIF_H
71
72 #include <stdint.h>
73 #include <stddef.h>
74
75 typedef struct {
76 void * data;
77 size_t dataSize;
78
79 size_t allocSize; //internal use
80 void * contextPointer; //internal use
81 } MsfGifResult;
82
83 typedef struct { //internal use
84 uint32_t * pixels;
85 int depth, count, rbits, gbits, bbits;
86 } MsfCookedFrame;
87
88 typedef struct MsfGifBuffer {
89 struct MsfGifBuffer * next;
90 size_t size;
91 uint8_t data[1];
92 } MsfGifBuffer;
93
94 typedef size_t (* MsfGifFileWriteFunc) (const void * buffer, size_t size, size_t count, void * stream);
95 typedef struct {
96 MsfGifFileWriteFunc fileWriteFunc;
97 void * fileWriteData;
98 MsfCookedFrame previousFrame;
99 MsfCookedFrame currentFrame;
100 int16_t * lzwMem;
101 MsfGifBuffer * listHead;
102 MsfGifBuffer * listTail;
103 int width, height;
104 void * customAllocatorContext;
105 int framesSubmitted; //needed for transparency to work correctly (because we reach into the previous frame)
106 } MsfGifState;
107
108 #ifdef __cplusplus
109 extern "C" {
110 #endif //__cplusplus
111
112 /**
113 * @param width Image width in pixels.
114 * @param height Image height in pixels.
115 * @return Non-zero on success, 0 on error.
116 */
117 int msf_gif_begin(MsfGifState * handle, int width, int height);
118
119 /**
120 * @param pixelData Pointer to raw framebuffer data. Rows must be contiguous in memory, in RGBA8 format
121 * (or BGRA8 if you have set `msf_gif_bgra_flag = true`).
122 * Note: This function does NOT free `pixelData`. You must free it yourself afterwards.
123 * @param centiSecondsPerFrame How many hundredths of a second this frame should be displayed for.
124 * Note: This being specified in centiseconds is a limitation of the GIF format.
125 * @param maxBitDepth Limits how many bits per pixel can be used when quantizing the gif.
126 * The actual bit depth chosen for a given frame will be less than or equal to
127 * the supplied maximum, depending on the variety of colors used in the frame.
128 * `maxBitDepth` will be clamped between 1 and 16. The recommended default is 16.
129 * Lowering this value can result in faster exports and smaller gifs,
130 * but the quality may suffer.
131 * Please experiment with this value to find what works best for your application.
132 * @param pitchInBytes The number of bytes from the beginning of one row of pixels to the beginning of the next.
133 * If you want to flip the image, just pass in a negative pitch.
134 * @return Non-zero on success, 0 on error.
135 */
136 int msf_gif_frame(MsfGifState * handle, uint8_t * pixelData, int centiSecondsPerFame, int maxBitDepth, int pitchInBytes);
137
138 /**
139 * @return A block of memory containing the gif file data, or NULL on error.
140 * You are responsible for freeing this via `msf_gif_free()`.
141 */
142 MsfGifResult msf_gif_end(MsfGifState * handle);
143
144 /**
145 * @param result The MsfGifResult struct, verbatim as it was returned from `msf_gif_end()`.
146 */
147 void msf_gif_free(MsfGifResult result);
148
149 //The gif format only supports 1-bit transparency, meaning a pixel will either be fully transparent or fully opaque.
150 //Pixels with an alpha value less than the alpha threshold will be treated as transparent.
151 //To enable exporting transparent gifs, set it to a value between 1 and 255 (inclusive) before calling msf_gif_frame().
152 //Setting it to 0 causes the alpha channel to be ignored. Its initial value is 0.
153 extern int msf_gif_alpha_threshold;
154
155 //Set `msf_gif_bgra_flag = true` before calling `msf_gif_frame()` if your pixels are in BGRA byte order instead of RBGA.
156 extern int msf_gif_bgra_flag;
157
158
159
160 //TO-FILE FUNCTIONS
161 //These functions are equivalent to the ones above, but they write results to a file incrementally,
162 //instead of building a buffer in memory. This can result in lower memory usage when saving large gifs,
163 //because memory usage is bounded by only the size of a single frame, and is not dependent on the number of frames.
164 //There is currently no reason to use these unless you are on a memory-constrained platform.
165 //If in doubt about which API to use, for now you should use the normal (non-file) functions above.
166 //The signature of MsfGifFileWriteFunc matches fwrite for convenience, so that you can use the C file API like so:
167 // FILE * fp = fopen("MyGif.gif", "wb");
168 // msf_gif_begin_to_file(&handle, width, height, (MsfGifFileWriteFunc) fwrite, (void *) fp);
169 // msf_gif_frame_to_file(...)
170 // msf_gif_end_to_file(&handle);
171 // fclose(fp);
172 //If you use a custom file write function, you must take care to return the same values that fwrite() would return.
173 //Note that all three functions will potentially write to the file.
174 int msf_gif_begin_to_file(MsfGifState * handle, int width, int height, MsfGifFileWriteFunc func, void * filePointer);
175 int msf_gif_frame_to_file(MsfGifState * handle, uint8_t * pixelData, int centiSecondsPerFame, int maxBitDepth, int pitchInBytes);
176 int msf_gif_end_to_file(MsfGifState * handle); //returns 0 on error and non-zero on success
177
178 #ifdef __cplusplus
179 }
180 #endif //__cplusplus
181
182 #endif //MSF_GIF_H
183
184 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
185 /// IMPLEMENTATION ///
186 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
187
188 #ifdef MSF_GIF_IMPL
189 #ifndef MSF_GIF_ALREADY_IMPLEMENTED_IN_THIS_TRANSLATION_UNIT
190 #define MSF_GIF_ALREADY_IMPLEMENTED_IN_THIS_TRANSLATION_UNIT
191
192 //ensure the library user has either defined all of malloc/realloc/free, or none
193 #if defined(MSF_GIF_MALLOC) && defined(MSF_GIF_REALLOC) && defined(MSF_GIF_FREE) //ok
194 #elif !defined(MSF_GIF_MALLOC) && !defined(MSF_GIF_REALLOC) && !defined(MSF_GIF_FREE) //ok
195 #else
196 #error "You must either define all of MSF_GIF_MALLOC, MSF_GIF_REALLOC, and MSF_GIF_FREE, or define none of them"
197 #endif
198
199 //provide default allocator definitions that redirect to the standard global allocator
200 #if !defined(MSF_GIF_MALLOC)
201 #include <stdlib.h> //malloc, etc.
202 #define MSF_GIF_MALLOC(contextPointer, newSize) malloc(newSize)
203 #define MSF_GIF_REALLOC(contextPointer, oldMemory, oldSize, newSize) realloc(oldMemory, newSize)
204 #define MSF_GIF_FREE(contextPointer, oldMemory, oldSize) free(oldMemory)
205 #endif
206
207 //instrumentation for capturing profiling traces (useless for the library user, but useful for the library author)
208 #ifdef MSF_GIF_ENABLE_TRACING
209 #define MsfTimeFunc TimeFunc
210 #define MsfTimeLoop TimeLoop
211 #define msf_init_profiling_thread init_profiling_thread
212 #else
213 #define MsfTimeFunc
214 #define MsfTimeLoop(name)
215 #define msf_init_profiling_thread()
216 #endif //MSF_GIF_ENABLE_TRACING
217
218 #include <string.h> //memcpy
219
220 //TODO: use compiler-specific notation to force-inline functions currently marked inline
221 #if defined(__GNUC__) //gcc, clang
222 static inline int msf_bit_log(int i) { return 32 - __builtin_clz(i); }
223 #elif defined(_MSC_VER) //msvc
224 #include <intrin.h>
225 static inline int msf_bit_log(int i) { unsigned long idx; _BitScanReverse(&idx, i); return idx + 1; }
226 #else //fallback implementation for other compilers
227 //from https://stackoverflow.com/a/31718095/3064745 - thanks!
228 static inline int msf_bit_log(int i) {
229 static const int MultiplyDeBruijnBitPosition[32] = {
230 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
231 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31,
232 };
233 i |= i >> 1;
234 i |= i >> 2;
235 i |= i >> 4;
236 i |= i >> 8;
237 i |= i >> 16;
238 return MultiplyDeBruijnBitPosition[(uint32_t)(i * 0x07C4ACDDU) >> 27] + 1;
239 }
240 #endif
241 static inline int msf_imin(int a, int b) { return a < b? a : b; }
242 static inline int msf_imax(int a, int b) { return b < a? a : b; }
243
244 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
245 /// Frame Cooking ///
246 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
247
248 #if (defined (__SSE2__) || defined (_M_X64) || _M_IX86_FP == 2) && !defined(MSF_GIF_NO_SSE2)
249 #include <emmintrin.h>
250 #endif
251
252 int msf_gif_alpha_threshold = 0;
253 int msf_gif_bgra_flag = 0;
254
255 static void msf_cook_frame(MsfCookedFrame * frame, uint8_t * raw, uint8_t * used,
256 int width, int height, int pitch, int depth)
257 { MsfTimeFunc
258 //bit depth for each channel
259 const static int rdepthsArray[17] = { 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5 };
260 const static int gdepthsArray[17] = { 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6 };
261 const static int bdepthsArray[17] = { 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5 };
262 //this extra level of indirection looks unnecessary but we need to explicitly decay the arrays to pointers
263 //in order to be able to swap them because of C's annoying not-quite-pointers, not-quite-value-types stack arrays.
264 const int * rdepths = msf_gif_bgra_flag? bdepthsArray : rdepthsArray;
265 const int * gdepths = gdepthsArray;
266 const int * bdepths = msf_gif_bgra_flag? rdepthsArray : bdepthsArray;
267
268 const static int ditherKernel[16] = {
269 0 << 12, 8 << 12, 2 << 12, 10 << 12,
270 12 << 12, 4 << 12, 14 << 12, 6 << 12,
271 3 << 12, 11 << 12, 1 << 12, 9 << 12,
272 15 << 12, 7 << 12, 13 << 12, 5 << 12,
273 };
274
275 uint32_t * cooked = frame->pixels;
276 int count = 0;
277 MsfTimeLoop("do") do {
278 int rbits = rdepths[depth], gbits = gdepths[depth], bbits = bdepths[depth];
279 int paletteSize = (1 << (rbits + gbits + bbits)) + 1;
280 memset(used, 0, paletteSize * sizeof(uint8_t));
281
282 //TODO: document what this math does and why it's correct
283 int rdiff = (1 << (8 - rbits)) - 1;
284 int gdiff = (1 << (8 - gbits)) - 1;
285 int bdiff = (1 << (8 - bbits)) - 1;
286 short rmul = (short) ((255.0f - rdiff) / 255.0f * 257);
287 short gmul = (short) ((255.0f - gdiff) / 255.0f * 257);
288 short bmul = (short) ((255.0f - bdiff) / 255.0f * 257);
289
290 int gmask = ((1 << gbits) - 1) << rbits;
291 int bmask = ((1 << bbits) - 1) << rbits << gbits;
292
293 MsfTimeLoop("cook") for (int y = 0; y < height; ++y) {
294 int x = 0;
295
296 #if (defined (__SSE2__) || defined (_M_X64) || _M_IX86_FP == 2) && !defined(MSF_GIF_NO_SSE2)
297 __m128i k = _mm_loadu_si128((__m128i *) &ditherKernel[(y & 3) * 4]);
298 __m128i k2 = _mm_or_si128(_mm_srli_epi32(k, rbits), _mm_slli_epi32(_mm_srli_epi32(k, bbits), 16));
299 for (; x < width - 3; x += 4) {
300 uint8_t * pixels = &raw[y * pitch + x * 4];
301 __m128i p = _mm_loadu_si128((__m128i *) pixels);
302
303 __m128i rb = _mm_and_si128(p, _mm_set1_epi32(0x00FF00FF));
304 __m128i rb1 = _mm_mullo_epi16(rb, _mm_set_epi16(bmul, rmul, bmul, rmul, bmul, rmul, bmul, rmul));
305 __m128i rb2 = _mm_adds_epu16(rb1, k2);
306 __m128i r3 = _mm_srli_epi32(_mm_and_si128(rb2, _mm_set1_epi32(0x0000FFFF)), 16 - rbits);
307 __m128i b3 = _mm_and_si128(_mm_srli_epi32(rb2, 32 - rbits - gbits - bbits), _mm_set1_epi32(bmask));
308
309 __m128i g = _mm_and_si128(_mm_srli_epi32(p, 8), _mm_set1_epi32(0x000000FF));
310 __m128i g1 = _mm_mullo_epi16(g, _mm_set1_epi32(gmul));
311 __m128i g2 = _mm_adds_epu16(g1, _mm_srli_epi32(k, gbits));
312 __m128i g3 = _mm_and_si128(_mm_srli_epi32(g2, 16 - rbits - gbits), _mm_set1_epi32(gmask));
313
314 __m128i out = _mm_or_si128(_mm_or_si128(r3, g3), b3);
315
316 //mask in transparency based on threshold
317 //NOTE: we can theoretically do a sub instead of srli by doing an unsigned compare via bias
318 // to maybe save a TINY amount of throughput? but lol who cares maybe I'll do it later -m
319 __m128i invAlphaMask = _mm_cmplt_epi32(_mm_srli_epi32(p, 24), _mm_set1_epi32(msf_gif_alpha_threshold));
320 out = _mm_or_si128(_mm_and_si128(invAlphaMask, _mm_set1_epi32(paletteSize - 1)), _mm_andnot_si128(invAlphaMask, out));
321
322 //TODO: does storing this as a __m128i then reading it back as a uint32_t violate strict aliasing?
323 uint32_t * c = &cooked[y * width + x];
324 _mm_storeu_si128((__m128i *) c, out);
325 }
326 #endif
327
328 //scalar cleanup loop
329 for (; x < width; ++x) {
330 uint8_t * p = &raw[y * pitch + x * 4];
331
332 //transparent pixel if alpha is low
333 if (p[3] < msf_gif_alpha_threshold) {
334 cooked[y * width + x] = paletteSize - 1;
335 continue;
336 }
337
338 int dx = x & 3, dy = y & 3;
339 int k = ditherKernel[dy * 4 + dx];
340 cooked[y * width + x] =
341 (msf_imin(65535, p[2] * bmul + (k >> bbits)) >> (16 - rbits - gbits - bbits) & bmask) |
342 (msf_imin(65535, p[1] * gmul + (k >> gbits)) >> (16 - rbits - gbits ) & gmask) |
343 msf_imin(65535, p[0] * rmul + (k >> rbits)) >> (16 - rbits );
344 }
345 }
346
347 count = 0;
348 MsfTimeLoop("mark") for (int i = 0; i < width * height; ++i) {
349 used[cooked[i]] = 1;
350 }
351
352 //count used colors, transparent is ignored
353 MsfTimeLoop("count") for (int j = 0; j < paletteSize - 1; ++j) {
354 count += used[j];
355 }
356 } while (count >= 256 && --depth);
357
358 MsfCookedFrame ret = { cooked, depth, count, rdepths[depth], gdepths[depth], bdepths[depth] };
359 *frame = ret;
360 }
361
362 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
363 /// Frame Compression ///
364 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
365
366 static inline void msf_put_code(uint8_t * * writeHead, uint32_t * blockBits, int len, uint32_t code) {
367 //insert new code into block buffer
368 int idx = *blockBits / 8;
369 int bit = *blockBits % 8;
370 (*writeHead)[idx + 0] |= code << bit ;
371 (*writeHead)[idx + 1] |= code >> ( 8 - bit);
372 (*writeHead)[idx + 2] |= code >> (16 - bit);
373 *blockBits += len;
374
375 //prep the next block buffer if the current one is full
376 if (*blockBits >= 256 * 8) {
377 *blockBits -= 255 * 8;
378 (*writeHead) += 256;
379 (*writeHead)[2] = (*writeHead)[1];
380 (*writeHead)[1] = (*writeHead)[0];
381 (*writeHead)[0] = 255;
382 memset((*writeHead) + 4, 0, 256);
383 }
384 }
385
386 typedef struct {
387 int16_t * data;
388 int len;
389 int stride;
390 } MsfStridedList;
391
392 static inline void msf_lzw_reset(MsfStridedList * lzw, int tableSize, int stride) { MsfTimeFunc
393 memset(lzw->data, 0xFF, 4096 * stride * sizeof(int16_t));
394 lzw->len = tableSize + 2;
395 lzw->stride = stride;
396 }
397
398 static MsfGifBuffer * msf_compress_frame(void * allocContext, int width, int height, int centiSeconds,
399 MsfCookedFrame frame, MsfGifState * handle, uint8_t * used, int16_t * lzwMem)
400 { MsfTimeFunc
401 //NOTE: we reserve enough memory for theoretical the worst case upfront because it's a reasonable amount,
402 // and prevents us from ever having to check size or realloc during compression
403 int maxBufSize = offsetof(MsfGifBuffer, data) + 32 + 256 * 3 + width * height * 3 / 2; //headers + color table + data
404 MsfGifBuffer * buffer = (MsfGifBuffer *) MSF_GIF_MALLOC(allocContext, maxBufSize);
405 if (!buffer) { return NULL; }
406 uint8_t * writeHead = buffer->data;
407 MsfStridedList lzw = { lzwMem };
408
409 //allocate tlb
410 int totalBits = frame.rbits + frame.gbits + frame.bbits;
411 int tlbSize = (1 << totalBits) + 1;
412 uint8_t tlb[(1 << 16) + 1]; //only 64k, so stack allocating is fine
413
414 //generate palette
415 typedef struct { uint8_t r, g, b; } Color3;
416 Color3 table[256] = { {0} };
417 int tableIdx = 1; //we start counting at 1 because 0 is the transparent color
418 //transparent is always last in the table
419 tlb[tlbSize-1] = 0;
420 MsfTimeLoop("table") for (int i = 0; i < tlbSize-1; ++i) {
421 if (used[i]) {
422 tlb[i] = tableIdx;
423 int rmask = (1 << frame.rbits) - 1;
424 int gmask = (1 << frame.gbits) - 1;
425 //isolate components
426 int r = i & rmask;
427 int g = i >> frame.rbits & gmask;
428 int b = i >> (frame.rbits + frame.gbits);
429 //shift into highest bits
430 r <<= 8 - frame.rbits;
431 g <<= 8 - frame.gbits;
432 b <<= 8 - frame.bbits;
433 table[tableIdx].r = r | r >> frame.rbits | r >> (frame.rbits * 2) | r >> (frame.rbits * 3);
434 table[tableIdx].g = g | g >> frame.gbits | g >> (frame.gbits * 2) | g >> (frame.gbits * 3);
435 table[tableIdx].b = b | b >> frame.bbits | b >> (frame.bbits * 2) | b >> (frame.bbits * 3);
436 if (msf_gif_bgra_flag) {
437 uint8_t temp = table[tableIdx].r;
438 table[tableIdx].r = table[tableIdx].b;
439 table[tableIdx].b = temp;
440 }
441 ++tableIdx;
442 }
443 }
444 int hasTransparentPixels = used[tlbSize-1];
445
446 //SPEC: "Because of some algorithmic constraints however, black & white images which have one color bit
447 // must be indicated as having a code size of 2."
448 int tableBits = msf_imax(2, msf_bit_log(tableIdx - 1));
449 int tableSize = 1 << tableBits;
450 //NOTE: we don't just compare `depth` field here because it will be wrong for the first frame and we will segfault
451 MsfCookedFrame previous = handle->previousFrame;
452 int hasSamePal = frame.rbits == previous.rbits && frame.gbits == previous.gbits && frame.bbits == previous.bbits;
453 int framesCompatible = hasSamePal && !hasTransparentPixels;
454
455 //NOTE: because __attribute__((__packed__)) is annoyingly compiler-specific, we do this unreadable weirdness
456 char headerBytes[19] = "\x21\xF9\x04\x05\0\0\0\0" "\x2C\0\0\0\0\0\0\0\0\x80";
457 //NOTE: we need to check the frame number because if we reach into the buffer prior to the first frame,
458 // we'll just clobber the file header instead, which is a bug
459 if (hasTransparentPixels && handle->framesSubmitted > 0) {
460 handle->listTail->data[3] = 0x09; //set the previous frame's disposal to background, so transparency is possible
461 }
462 memcpy(&headerBytes[4], &centiSeconds, 2);
463 memcpy(&headerBytes[13], &width, 2);
464 memcpy(&headerBytes[15], &height, 2);
465 headerBytes[17] |= tableBits - 1;
466 memcpy(writeHead, headerBytes, 18);
467 writeHead += 18;
468
469 //local color table
470 memcpy(writeHead, table, tableSize * sizeof(Color3));
471 writeHead += tableSize * sizeof(Color3);
472 *writeHead++ = tableBits;
473
474 //prep block
475 memset(writeHead, 0, 260);
476 writeHead[0] = 255;
477 uint32_t blockBits = 8; //relative to block.head
478
479 //SPEC: "Encoders should output a Clear code as the first code of each image data stream."
480 msf_lzw_reset(&lzw, tableSize, tableIdx);
481 msf_put_code(&writeHead, &blockBits, msf_bit_log(lzw.len - 1), tableSize);
482
483 int lastCode = framesCompatible && frame.pixels[0] == previous.pixels[0]? 0 : tlb[frame.pixels[0]];
484 MsfTimeLoop("compress") for (int i = 1; i < width * height; ++i) {
485 //PERF: branching vs. branchless version of this line is observed to have no discernable impact on speed
486 int color = framesCompatible && frame.pixels[i] == previous.pixels[i]? 0 : tlb[frame.pixels[i]];
487 int code = (&lzw.data[lastCode * lzw.stride])[color];
488 if (code < 0) {
489 //write to code stream
490 int codeBits = msf_bit_log(lzw.len - 1);
491 msf_put_code(&writeHead, &blockBits, codeBits, lastCode);
492
493 if (lzw.len > 4095) {
494 //reset buffer code table
495 msf_put_code(&writeHead, &blockBits, codeBits, tableSize);
496 msf_lzw_reset(&lzw, tableSize, tableIdx);
497 } else {
498 (&lzw.data[lastCode * lzw.stride])[color] = lzw.len;
499 ++lzw.len;
500 }
501
502 lastCode = color;
503 } else {
504 lastCode = code;
505 }
506 }
507
508 //write code for leftover index buffer contents, then the end code
509 msf_put_code(&writeHead, &blockBits, msf_imin(12, msf_bit_log(lzw.len - 1)), lastCode);
510 msf_put_code(&writeHead, &blockBits, msf_imin(12, msf_bit_log(lzw.len)), tableSize + 1);
511
512 //flush remaining data
513 if (blockBits > 8) {
514 int bytes = (blockBits + 7) / 8; //round up
515 writeHead[0] = bytes - 1;
516 writeHead += bytes;
517 }
518 *writeHead++ = 0; //terminating block
519
520 //fill in buffer header and shrink buffer to fit data
521 buffer->next = NULL;
522 buffer->size = writeHead - buffer->data;
523 MsfGifBuffer * moved =
524 (MsfGifBuffer *) MSF_GIF_REALLOC(allocContext, buffer, maxBufSize, offsetof(MsfGifBuffer, data) + buffer->size);
525 if (!moved) { MSF_GIF_FREE(allocContext, buffer, maxBufSize); return NULL; }
526 return moved;
527 }
528
529 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
530 /// To-memory API ///
531 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
532
533 static const int lzwAllocSize = 4096 * 256 * sizeof(int16_t);
534
535 //NOTE: by C standard library conventions, freeing NULL should be a no-op,
536 // but just in case the user's custom free doesn't follow that rule, we do null checks on our end as well.
537 static void msf_free_gif_state(MsfGifState * handle) {
538 if (handle->previousFrame.pixels) MSF_GIF_FREE(handle->customAllocatorContext, handle->previousFrame.pixels,
539 handle->width * handle->height * sizeof(uint32_t));
540 if (handle->currentFrame.pixels) MSF_GIF_FREE(handle->customAllocatorContext, handle->currentFrame.pixels,
541 handle->width * handle->height * sizeof(uint32_t));
542 if (handle->lzwMem) MSF_GIF_FREE(handle->customAllocatorContext, handle->lzwMem, lzwAllocSize);
543 for (MsfGifBuffer * node = handle->listHead; node;) {
544 MsfGifBuffer * next = node->next; //NOTE: we have to copy the `next` pointer BEFORE freeing the node holding it
545 MSF_GIF_FREE(handle->customAllocatorContext, node, offsetof(MsfGifBuffer, data) + node->size);
546 node = next;
547 }
548 handle->listHead = NULL; //this implicitly marks the handle as invalid until the next msf_gif_begin() call
549 }
550
551 int msf_gif_begin(MsfGifState * handle, int width, int height) { MsfTimeFunc
552 //NOTE: we cannot stomp the entire struct to zero because we must preserve `customAllocatorContext`.
553 MsfCookedFrame empty = {0}; //god I hate MSVC...
554 handle->previousFrame = empty;
555 handle->currentFrame = empty;
556 handle->width = width;
557 handle->height = height;
558 handle->framesSubmitted = 0;
559
560 //allocate memory for LZW buffer
561 //NOTE: Unfortunately we can't just use stack memory for the LZW table because it's 2MB,
562 // which is more stack space than most operating systems give by default,
563 // and we can't realistically expect users to be willing to override that just to use our library,
564 // so we have to allocate this on the heap.
565 handle->lzwMem = (int16_t *) MSF_GIF_MALLOC(handle->customAllocatorContext, lzwAllocSize);
566 handle->previousFrame.pixels =
567 (uint32_t *) MSF_GIF_MALLOC(handle->customAllocatorContext, handle->width * handle->height * sizeof(uint32_t));
568 handle->currentFrame.pixels =
569 (uint32_t *) MSF_GIF_MALLOC(handle->customAllocatorContext, handle->width * handle->height * sizeof(uint32_t));
570
571 //setup header buffer header (lol)
572 handle->listHead = (MsfGifBuffer *) MSF_GIF_MALLOC(handle->customAllocatorContext, offsetof(MsfGifBuffer, data) + 32);
573 if (!handle->listHead || !handle->lzwMem || !handle->previousFrame.pixels || !handle->currentFrame.pixels) {
574 msf_free_gif_state(handle);
575 return 0;
576 }
577 handle->listTail = handle->listHead;
578 handle->listHead->next = NULL;
579 handle->listHead->size = 32;
580
581 //NOTE: because __attribute__((__packed__)) is annoyingly compiler-specific, we do this unreadable weirdness
582 char headerBytes[33] = "GIF89a\0\0\0\0\x70\0\0" "\x21\xFF\x0BNETSCAPE2.0\x03\x01\0\0\0";
583 memcpy(&headerBytes[6], &width, 2);
584 memcpy(&headerBytes[8], &height, 2);
585 memcpy(handle->listHead->data, headerBytes, 32);
586 return 1;
587 }
588
589 int msf_gif_frame(MsfGifState * handle, uint8_t * pixelData, int centiSecondsPerFame, int maxBitDepth, int pitchInBytes)
590 { MsfTimeFunc
591 if (!handle->listHead) { return 0; }
592
593 maxBitDepth = msf_imax(1, msf_imin(16, maxBitDepth));
594 if (pitchInBytes == 0) pitchInBytes = handle->width * 4;
595 if (pitchInBytes < 0) pixelData -= pitchInBytes * (handle->height - 1);
596
597 uint8_t used[(1 << 16) + 1]; //only 64k, so stack allocating is fine
598 msf_cook_frame(&handle->currentFrame, pixelData, used, handle->width, handle->height, pitchInBytes,
599 msf_imin(maxBitDepth, handle->previousFrame.depth + 160 / msf_imax(1, handle->previousFrame.count)));
600
601 MsfGifBuffer * buffer = msf_compress_frame(handle->customAllocatorContext, handle->width, handle->height,
602 centiSecondsPerFame, handle->currentFrame, handle, used, handle->lzwMem);
603 if (!buffer) { msf_free_gif_state(handle); return 0; }
604 handle->listTail->next = buffer;
605 handle->listTail = buffer;
606
607 //swap current and previous frames
608 MsfCookedFrame tmp = handle->previousFrame;
609 handle->previousFrame = handle->currentFrame;
610 handle->currentFrame = tmp;
611
612 handle->framesSubmitted += 1;
613 return 1;
614 }
615
616 MsfGifResult msf_gif_end(MsfGifState * handle) { MsfTimeFunc
617 if (!handle->listHead) { MsfGifResult empty = {0}; return empty; }
618
619 //first pass: determine total size
620 size_t total = 1; //1 byte for trailing marker
621 for (MsfGifBuffer * node = handle->listHead; node; node = node->next) { total += node->size; }
622
623 //second pass: write data
624 uint8_t * buffer = (uint8_t *) MSF_GIF_MALLOC(handle->customAllocatorContext, total);
625 if (buffer) {
626 uint8_t * writeHead = buffer;
627 for (MsfGifBuffer * node = handle->listHead; node; node = node->next) {
628 memcpy(writeHead, node->data, node->size);
629 writeHead += node->size;
630 }
631 *writeHead++ = 0x3B;
632 }
633
634 //third pass: free buffers
635 msf_free_gif_state(handle);
636
637 MsfGifResult ret = { buffer, total, total, handle->customAllocatorContext };
638 return ret;
639 }
640
641 void msf_gif_free(MsfGifResult result) { MsfTimeFunc
642 if (result.data) { MSF_GIF_FREE(result.contextPointer, result.data, result.allocSize); }
643 }
644
645 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
646 /// To-file API ///
647 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
648
649 int msf_gif_begin_to_file(MsfGifState * handle, int width, int height, MsfGifFileWriteFunc func, void * filePointer) {
650 handle->fileWriteFunc = func;
651 handle->fileWriteData = filePointer;
652 return msf_gif_begin(handle, width, height);
653 }
654
655 int msf_gif_frame_to_file(MsfGifState * handle, uint8_t * pixelData, int centiSecondsPerFame, int maxBitDepth, int pitchInBytes) {
656 if (!msf_gif_frame(handle, pixelData, centiSecondsPerFame, maxBitDepth, pitchInBytes)) { return 0; }
657
658 //NOTE: this is a somewhat hacky implementation which is not perfectly efficient, but it's good enough for now
659 MsfGifBuffer * head = handle->listHead;
660 if (!handle->fileWriteFunc(head->data, head->size, 1, handle->fileWriteData)) { msf_free_gif_state(handle); return 0; }
661 handle->listHead = head->next;
662 MSF_GIF_FREE(handle->customAllocatorContext, head, offsetof(MsfGifBuffer, data) + head->size);
663 return 1;
664 }
665
666 int msf_gif_end_to_file(MsfGifState * handle) {
667 //NOTE: this is a somewhat hacky implementation which is not perfectly efficient, but it's good enough for now
668 MsfGifResult result = msf_gif_end(handle);
669 int ret = (int) handle->fileWriteFunc(result.data, result.dataSize, 1, handle->fileWriteData);
670 msf_gif_free(result);
671 return ret;
672 }
673
674 #endif //MSF_GIF_ALREADY_IMPLEMENTED_IN_THIS_TRANSLATION_UNIT
675 #endif //MSF_GIF_IMPL
676
677 /*
678 ------------------------------------------------------------------------------
679 This software is available under 2 licenses -- choose whichever you prefer.
680 ------------------------------------------------------------------------------
681 ALTERNATIVE A - MIT License
682 Copyright (c) 2021 Miles Fogle
683 Permission is hereby granted, free of charge, to any person obtaining a copy of
684 this software and associated documentation files (the "Software"), to deal in
685 the Software without restriction, including without limitation the rights to
686 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
687 of the Software, and to permit persons to whom the Software is furnished to do
688 so, subject to the following conditions:
689 The above copyright notice and this permission notice shall be included in all
690 copies or substantial portions of the Software.
691 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
692 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
693 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
694 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
695 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
696 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
697 SOFTWARE.
698 ------------------------------------------------------------------------------
699 ALTERNATIVE B - Public Domain (www.unlicense.org)
700 This is free and unencumbered software released into the public domain.
701 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
702 software, either in source code form or as a compiled binary, for any purpose,
703 commercial or non-commercial, and by any means.
704 In jurisdictions that recognize copyright laws, the author or authors of this
705 software dedicate any and all copyright interest in the software to the public
706 domain. We make this dedication for the benefit of the public at large and to
707 the detriment of our heirs and successors. We intend this dedication to be an
708 overt act of relinquishment in perpetuity of all present and future rights to
709 this software under copyright law.
710 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
711 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
712 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
713 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
714 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
715 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
716 ------------------------------------------------------------------------------
717 */
718