CGIF, A fast and lightweight GIF encoder that can create GIF animations and images

Hi Daniel,

I'm researching permissively-licenced open source GIF encoding libraries to add as a possible dependency of libvips and am very happy to discover this repo, including the huge bonus that it has tests :tada:

I realise this code is less than a month old but it already seems to be well-written and fully-featured, which is a very good sign, thank you.

I have a few questions after briefly reading and testing the code. I suspect these are things you've already thought of but not got round to yet so I can break these out into separate enhancement issues if that's easier.

• Should constants/structs exposed by the header file be "namespaced" with a consistent CGIF prefix, e.g. CGIFFrameConfig, CGIF_FRAME_ATTR_... etc.?
• Would allowing for output other than the filesystem e.g. to memory or pipe/stream be something of interest, perhaps by adding a configurable write function pointer to the GIFConfig (CGIFConfig?) struct?
• I notice there are comments about the endianess of converting 16-bit integers to byte arrays. Are big endian systems something you'd like to support?
• An initial valgrind report suggests there may be cases where uninitialised memory is being used, where e.g. the use of calloc would be safer than malloc, but this is still something I need to test properly (all_optim appears to segfault randomly).
• To make things easier for me locally, I've created a small meson configuration file for this repo as it removes most of the pain of (cross-)compilation/testing, as libvips supports many platforms, should that be of interest to you.

I'd be happy to use some of our Open Collective donations to help fund this work, and/or submit PRs where appropriate too.

Guten Tag, I've taken the approach as suggested in #4, ensuring the relevant disposal method is set, plus added a unit test.

I've also tested this using a botched together libvips+cgif integration and the obligatory dancing banana.

It's common for GIF images to include transparent pixels as part of a frame (often as a single frame "animated" image) and typically this would be the first entry/index in the palette.

I've had a quick go at hacking this into cgif via a FRAME_ATTR_HAS_TRANSPARENCY flag and it seems to work.

diff --git a/cgif.c b/cgif.c
index 81567c0..4154dd1 100644
--- a/cgif.c
+++ b/cgif.c
@@ -556,7 +556,7 @@ int cgif_addframe(GIF* pGIF, FrameConfig* pConfig) {
     pFrame->aGraphicExt[1] = 0xF9;
     pFrame->aGraphicExt[2] = 0x04;
     pFrame->aGraphicExt[3] = 0x04;
-    if(pFrame->config.genFlags & FRAME_GEN_USE_TRANSPARENCY) {
+    if((pFrame->config.genFlags & FRAME_GEN_USE_TRANSPARENCY) || (pConfig->attrFlags & FRAME_ATTR_HAS_TRANSPARENCY)) {
       pFrame->aGraphicExt[3] |= 0x01;
     }
     pFrame->aGraphicExt[6] = pFrame->transIndex;
diff --git a/cgif.h b/cgif.h
index 80e617c..8fb0603 100644
--- a/cgif.h
+++ b/cgif.h
@@ -10,6 +10,7 @@
 #define GIF_ATTR_IS_ANIMATED          (1uL << 1)       // make an animated GIF (default is non-animated GIF)
 #define GIF_ATTR_NO_GLOBAL_TABLE      (1uL << 2)       // disable global color table (global color table is default)
 #define FRAME_ATTR_USE_LOCAL_TABLE    (1uL << 0)       // use a local color table for a frame (local color table is not used by default)
+#define FRAME_ATTR_HAS_TRANSPARENCY   (1uL << 1)       // palette contains transparency at index 0
 // flags to decrease GIF-size
 #define FRAME_GEN_USE_TRANSPARENCY    (1uL << 0)       // use transparency optimization (setting pixels identical to previous frame transparent)
 #define FRAME_GEN_USE_DIFF_WINDOW     (1uL << 1)       // do encoding just for the sub-window that has changed from previous frame

It's quite likely there's a better/cleaner way to do this.

I'm happy to submit a PR but would welcome any thoughts/improvements on the approach/API.

Hi, as discussed in #1 this PR adds a meson build script to allow all the major Linux distributions, macOS Homebrew etc. to start to build, package and distribute this library.

The tests have been updated so they write to their "own" file to allow these to be run in parallel.

It adds GitHub Actions CI configuration, including running the tests via valgrind.

https://github.com/lovell/cgif/actions/runs/1067901844

I'm trying to encode an animated GIF file that only plays once and then stops. However, when I set CGIF_Config->numLoops to 1, it plays twice, and when I set it to 0, it results in an infinite loop, making it impossible to do so. Example GIF:

I re-encoded the GIF with ImageMagick to have a proper loop count, here's what it's supposed to look like:

After comparing the two GIFs above in a hex editor, I can see that the one that properly loops doesn't have a NETSCAPE2.0 application extension. Perhaps there could be a way to specify that it's not needed?

There appears to be a small memory leak when cgif_close is called without first adding a frame by calling cgif_addframe. It appears cgif_close will skip some cleanups when pGIF->CurResult is != CGIF_OK. In this case, it’s CGIF_PENDING and so pGIF doesn’t get freed within cgif_raw_close. I appreciate this isn’t the most typical use case for cgif, but it is possible for it to happen in my application if it has to close down before having had chance to add a frame. Thanks for a great library.

Most time of encoding is spent in the LZW routines. Increase LZW encoding speed by improving cache affinity. The memory usage has been decreased as well.

ToDo:

• [x] Do benchmarks to verify the speed improvement
• [x] Extend tests and add tests that fully utilize the pTreeMap (backup LZW mapping tree)

Resolve potential unaligned accesses which caused issues on sparc64. This issue has been reported by the Debian Build-System: https://buildd.debian.org/status/package.php?p=cgif

• [x] Set up sparc64 VM and test this fix
• [x] Backport PR to V0.0 branch and release V0.0.4

As of now, in case the user specifies a color table with 1 or 2 entries, the size of the resulting color table in the GIF is chosen two entries too large (2^2 instead of 2^1). Resolve this by properly calculating the needed size. This behavior can be reproduced with the min_color_table_test.c test.

It seems that this can be implemented as log2(n - 1) + 2, though that will give different results for n < 3 || n > 256, but perhaps that's fine.

This PR was initiated as a draft to discuss this further.

#include <stdio.h>
#include <stdint.h>

static uint8_t calcInitCodeLen(uint16_t numEntries) {
	if (numEntries > (1uL << 7)) {
		return 9;
	}
	if (numEntries > (1uL << 6)) {
		return 8;
	}
	if (numEntries > (1uL << 5)) {
		return 7;
	}
	if (numEntries > (1uL << 4)) {
		return 6;
	}
	if (numEntries > (1uL << 3)) {
		return 5;
	}
	if (numEntries > (1uL << 2)) {
		return 4;
	}
	return 3;
}

static uint8_t calcInitCodeLen2(uint16_t numEntries) {
	return 31 - __builtin_clz(numEntries - 1) + 2; // log2(n - 1) + 2
}

int main() {
	uint16_t i;

	for (i = 1; i < (1 << 10); i <<= 1 /*i++*/) {
		printf("i = %d\n", i);
		printf("%d ", calcInitCodeLen(i));
		printf("%d\n", calcInitCodeLen2(i));
	}
}

Slight optimization to: cgif_addframe

cgif_addframe now drops sequential frames that are identical to the previous frame and sums the frames' delay. This trick means we are encoding fewer bytes in the final GIF.

It should bring a slight improvement to decoders when decoding GIFs with sequential, duplicate frames as there is now fewer total frames to decode.

As of now, cgif requires more memory for writing interlaced GIFs.

For more details: https://github.com/dloebl/cgif/blob/b05de324c4413558bea330fb350ad4fd13396529/src/cgif_raw.c#L526

The file size of a frame after LZW encoding could be reduced further by using so-called clear codes. A clear code resets the LZW dictionary. Afterwards, the encoding is continued with a fresh LZW dictionary and the initial minimum code size. As of now, cgif always issues a clear code once the dictionary is full (4096 entries). However, it can be beneficial regarding the file size to reset it earlier or later. This is an optimization problem. We would need to find an adequate heuristic to find an approximate optimum here.

Add public cgif_rgb API with the following features:

• Allows passing RGB(A) image data to cgif.
• cgif takes care of quantization/dithering and creates the color palette(s).
• Avoids the size explosion (libvips/libvips#2576) by keeping transparent areas transparent during quantization/dithering.

ToDo:

• [ ] add lossy transparency selection ("low-pass filter") to improve the size further
• [ ] merge some local color palette(s) to a global palette (if the quality is not affected)
• [ ] cleanup/refactor cgif_rgb module
• [ ] add documentation to Wiki/README
• [x] add examples
• [ ] add coverage tests for cgif_rgb module

As of now our tests only check whether the resulting file is a valid GIF image. However, we should add tests that check whether the input image data matches the output image data. To achieve this, we would need to pass the GIF image created to an actual GIF decoder.

Steps:

1. Find a common, well-tested decoder (e.g. ImageMagick might be an option)
2. Add a compare routine to all current tests (Note: multi-frame / transparent GIFs might be tricky)