Use LZW encoding when saving GIF images

[raygard]

Fixes #5278 .

Changes proposed in this pull request:

• Modify Gif.h and GifEncode.c to use LZW encoding

After this has been done and the Tests/images/hopper_resized.gif file has been recreated with LZW encoding (per 72a098b mod to test_image_resize.py by @radarhere), that same test can be used to validate against regression, "making this an appropriate test to ensure that we don't break your code in the future." (quoting @radarhere)

I have tested this extensively. The best test I can provide now is this: test_giflzw.py . As described in the doc comment there, you need a build with the current (older) GifEncode.c named PIL and another with the new version named PIL_giflzw. You then run the program on image files (GIFs, but some other types will also work). It will open and save each file using both the old and the new encoders, to in-memory io.BytesIO buffers and optionally to actual files. It then re-opens them and retrieves the unencoded pixel bytes using .tobytes() and compares. I've never had a compare fail to match.

The new encoder is a little slower than the old, but typically yields GIF files about 70% the size of the old encoder.

If anyone is equipped to run a static or dynamic checker against my code (e.g. valgrind or anything else), I would welcome that. It currently compiles clean on both Windows and Linux.

The whole modules can be found in https://github.com/raygard/Pillow/blob/giflzw/src/libImaging/Gif.h and https://github.com/raygard/Pillow/blob/giflzw/src/libImaging/GifEncode.c .

[wiredfool]

If you can rebase on current master, there's now a Valgrind github action.

[radarhere]

Suggested change

	if (st->code_bits_left)
	goto check_buf_bits;
	if (st->code_bits_left) {
	goto check_buf_bits;
	}

Just a style change, see #4492

[raygard]

Done. Thanks for catching that. I tried to conform to the current Pillow style but missed that one.

[wiredfool]

LGTM.

One more thing that I'd ask -- can you link any references for the LZW format that you used (as comments), so if we do have to dig into this, we have a reference to what you were trying to do at the time? We'll also need to note something in the release notes. (#5287)

I'd like to get this into the 8.2.0 release, I think it's looking good enough at this point.

[raygard]

I have added a comment referencing the original GIF LZW spec from Compuserve. I hope that's what you wanted.

[hugovk]

@raygard Please could you also add this to the release notes?

https://github.com/python-pillow/Pillow/blob/master/docs/releasenotes/8.2.0.rst

[raygard]

@hugovk Not sure if I did this correctly, as I just copied the latest release notes into my own giflzw branch before adding this, under "Other Changes":

GIF writer uses LZW encoding
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

GIF files are now written using LZW encoding, which will generate smaller files,
typically about 70% of the size generated by the older encoder.

The pixel data is encoded using the format specified in the [Compuserve GIF
standard](https://www.w3.org/Graphics/GIF/spec-gif89a.txt). The older encoder
used a variant of run-length encoding that was compatible but less efficient.

I see that git/github says it has conflicts to be resolved, but it looks to me like a simple insertion of a few lines. I don't understand git enough to see why it causes a conflict.

[hugovk]

Ah yes, Git can be a bit tricky when the same lines are changed in a PR and then later in master, it doesn't always know the correct thing to do. I've resolved the conflict.

I'll merge this a bit later.

Thanks!

[raygard]

@hugovk I don't know why the link does not render correctly when I view the release notes at https://github.com/python-pillow/Pillow/blob/master/docs/releasenotes/8.2.0.rst.

I see literally:

[Compuserve GIF standard](https://www.w3.org/Graphics/GIF/spec-gif89a.txt).

Instead of Compuserve GIF standard.

No big deal, but wonder why.

[hugovk]

Oh yeah, it's because it's reStructuredText not Markdown, so has a different syntax:

https://docutils.sourceforge.io/docs/user/rst/quickref.html#hyperlink-targets

I'll fix it. Thanks for checking!

[raygard]

That’s on me for not noticing it’s .rst not .md. I’ve written a lot more .rst than .md and should have noticed! Thank you for fixing it. 

BTW there is some code and documentation at https://github.com/raygard/giflzw and https://raygard.github.io/giflzw/ regarding the development of this LZW encoder. In particular, there is an explanation and justification for the Duff's-device-like structure at https://raygard.github.io/giflzw/pages/about_the_code.html .