
Lossy GIF compressor (kornel.ski)
152 points by tambourine_man on Mar 13, 2018 | hide | past | web | favorite | 72 comments

It's weird that this pull request was never accepted by gifsicle.


Also check out his other high-quality GIF encoder project https://gif.ski/

Older HN submission https://news.ycombinator.com/item?id=15730018

It's probably (in part) due to the last line of the article / post:

> App Store terms and conditions forbid distribution of Free Software that grants users freedom to use the program any way they want. You're not allowed to distribute this software with DRM applied to it.

Which is, of course, false.

Specific free software licenses have DRM distribution restrictions regardless of if source/non-DRM editions are available. Which of course goes against user freedom too (to have their applications the way they want).

That to me says that it's the licence that is the issue (or needs to be improved).

gifsicle and the lossy version are both GPL-licensed. That's a deal-breaker for Apple (by their own choosing), but not a problem for the gifsicle project.

I think the reason for change not being accepted upstream is that the amount of complexity added exceeds amount of free time the upstream maintainer has.

I like this part on the end


Basically the essence of the GPL in one short paragraph.

Is this actually correct? If I distribute my app on the App Store, and provide a GitHub link in the description of the the full source code of the app, then it should comply with the GPL.

The Free Software Foundation has some details on this[1]. This used to come up with the video player VLC, but they seem to have relicenced it, and it's now possible.[2]

I've heard one reason is that the App Store requires users to agree to additional usage restrictions, which the GPL forbids distributors (in this case Apple) from applying.

[1] https://www.fsf.org/blogs/licensing/more-about-the-app-store... [2] https://www.videolan.org/vlc/download-ios.html

If you own all the copyrights to the source of the app you are linking on Github, then you can release it on the Appstore effectively under a different license for that version. If you don't own all the code, then are possibly violating someone else's license.

Short answers: GPLv2, no; GPLv3, yes.

Apple's App Store is identical to the TiVoization problem that GPLv3 was written to combat: https://www.gnu.org/licenses/rms-why-gplv3

Tivoization provision of GPLv3 only applies to software distributed as with a hardware “ussr product” (in the same transaction in which possessory interest in the hardware is transferred), so while it would apply to core components of iOS (of they used GPLv3 upstream, which they won't), it wouldn't seem to apply to any third party software distributed through the App Store.

(The same concerns that motivated anti-tivoization may apply, but the actual license terms don't appear to.)

This is not to say that there aren't other incompatibilities, but anti-tivoization doesn't seem to be a problem.

There is no difference. Apple provides binaries (via the App Store), and the user is not allowed to install/run their own binaries, which is a requirement the GPLv3 added to prevent TiVoization.

It matters not whether the software is preinstalled or offered on the side, the effect is the same. If the user can't install their own versions of software, the environment is incompatible with the GPLv3.

Now, running GPLv3 software via Cydia/jailbroken-iPhones is probably OK, since the user has gone through the effort in order to run their own versions of software. I'm pretty sure the FSF would prefer running a free software version of Android instead, however. :-)

> There is no difference.

Whether or not there is a moral difference, there is a clear difference in terms of the license terms.


No, the requirement that the GPLv3 added is that “Installation Instructions” must be provided when a licensee conveys software “in, or with, or specifically for use in, a User Product, and the conveying occurs as part of a transaction in which the right of possession and use of the User Product is transferred to the recipient in perpetuity or for a fixed term (regardless of how the transaction is characterized)” [emphasis added] [0]; that is, for anti-tivoization to apply, the software must be for a “User Product” (which App Store Apps are) and it must be conveyed in the same transaction as possession of the “User Product” is transferred (which clearly does not happen in the normal case with App Store Apps.)

You seem to be confusing a fuzzy picture of the goal of the GPLv3 with the actual requirements of the license terms.

[0] see the third to last paragraph of Section 5 of the license, https://www.gnu.org/licenses/gpl-3.0.en.html


This has not been true for a few years. Nowadays anyone can freely upload apps from Xcode to iDevices (before it used to cost 99$)

You can freely upload apps from Xcode to iDevices if you own a Mac, and have an Apple developer account (not paid but you still need one), and compile the code yourself, and most crucially the code signing on apps deployed this way expires after a week. This is in no way a serious deployment method.

I suspect the "freely upload" requirement might be "free as in speech", not "free as in beer". Apple might make it free as in cost nothing. But are you required to agree to any terms of service? I suspect so.

No, Apple is doing something different. See rmc’s post. They are asserting things like “If you use the Apple Store at all, then you agree not to install any GPL software it contains on more than 5 devices”

What makes you say "GPLv2, yes"? The issue is not just tivoization (if that's even applicable at all) but that per GPLv2 "You may not impose any further restrictions on the recipients' exercise of the rights granted herein." The rights include copying, distributing and modifying the software. The app store terms of service impose additional restrictions.

GPL compliance requires that you can reproduce a binary from the source with no additional encumbrances. That's not possible on Apple platforms. It's not enough to just provide the source.

So no signed binaries? The signature portion will obviously not be reproducible by anyone but the original signer. I believe that is all the App Store process does, sign with a key issued by Apple, but it might be more complex.

> I use public key cryptography to sign my code to assure its authenticity. Is it true that GPLv3 forces me to release my private signing keys?I use public key cryptography to sign my code to assure its authenticity. Is it true that GPLv3 forces me to release my private signing keys?

> No. The only time you would be required to release signing keys is if you conveyed GPLed software inside a User Product, and its hardware checked the software for a valid cryptographic signature before it would function. In that specific case, you would be required to provide anyone who owned the device, on demand, with the key to sign and install modified software on the device so that it will run. If each instance of the device uses a different key, then you need only give each purchaser a key for that instance.


No, because the provision you cite only applies for software distributed as part of a qualified device or in the same transaction where possessory interest in the device is transferred. That wouldn't apply to iOS Apps outside of the stock bundled apps, as App Store apps are transferred in separate transactions from the device.

The GNU FAQ is very clear on this matter. Code signing is allowed. But, you're right that the bit of the license I quoted is irrelevant, so I've removed it.

And in the case of a Mac, so far you don't need keys to install software you compiled yourself. On iOS there are additional encumbrances, like the need for a dev account, a separate computing device (a Mac) to compile for the iOS device, and so on.

It’s getting harder and harder for kexts. You can’t readily compile those from source and install them yourself without a developer license , anymore.

You currently technically still can, I believe (restart in some safe mode and disable a protection mechanism of sorts, iirc), but the trend is not towards openness. Honestly I don’t doubt for a second they’re doing it purely for the sake of security, but that doesn’t really matter for the GPL as far as I’m aware ?

Are you referring to additional meta that Apple applies to apps in the app store or something else?

I'd say that it's possible on a Mac, but not on an iOS device. You can't develop iOS apps on an iOS device, for starters. Just that is an additional encumbrance. Last time I checked, you also need some dev account with Apple to upload apps to your iOS device. (Remember, these rules are subject to interpretation, in court in the extreme case.)

That's what I was thinking. Some home routers have source links for the free software they use.

But I'd venture a guess that this source code is GPLv2 licensed, not GPLv3 licensed. They could make their firmware GPLv3 compliant, but it would be quite a bit of extra work.

It's irrelevant what you do to comply. To distribute in the App Store, Apple requires you to sign an agreement in which you license the code to Apple under Apple's non-FOSS terms. If you don't have the right to license the code under Apple's terms, Apple won't take it.

Apple doesn't comply with GPL and they don't want to. On a few occasions I have formally asked them to comply with GPL terms and they took GPLed apps down instead.

It's correct that GPLv3 forbids it (I think v2 doesn't) which isn't a problem with the App Store - it's a problem with the (opinionated) GPLv3.

Plenty of other OSS licenses work fine on the app store.

It sounds like he wants to make it illegal on the AppStore:

> Permission is granted to copy, distribute, or alter Gifsicle, whole or in part, as long as source code copyright notices are kept intact, with the following restriction: Developers or distributors who plan to use Gifsicle code, whole or in part, in a product whose source code will not be made available to the end user -- more precisely, in a context which would violate the GPL -- MUST contact the author and obtain permission before doing so.

- https://github.com/kornelski/giflossy#copyrightlicense

The software is based on Gifsicle, itself a GPLv2 licensed piece of software, so there isn't much the author could legally do about it.

This comment section is filled with weird misconceptions about the software and about the compatibility between GPL and the Apple store terms of service. Somehow people think the software is GPLv3 even though a cursory glance will reveal that it isn't. People think that the author of the modification has a say in how it's licensed. It's based on GPLv2 software, he doesn't. Others are saying that while distributing GPLv2 licensed software on the Apple store is fine, GPLv3 isn't, when neither is OK. Sorry for soapboxing here, but it seems appropriate to address all these misconceptions in one place.

He made it illegal when he chose GPL(v3). The text above just points it out. That it's inconvenient for app store users has no bearing on legality. Of course, as the author, he could with a stroke of the hand give an app store excemption or change/add a license, but clearly, he doesn't want to.

Why not use the AGPL in this case though? GPLv3 still does not prevent you from putting it on a server and exposing it as a SAAS.

What makes you assume that's something he wants to prevent?

The tone. I assume that if the author does not want people to distribute the library in an application with DRM, regardless of the fact whether they publish the source code or not they would also not be happy if somebody just took it, modified it and sold it as service without publishing their code.

Let's maybe generously assume that the author is not dumb and would carefully choose a license based on his needs and preferences.

Then consider the facts: The work is based on GPLv2 licensed tool (gifsicle), thus subject to the same terms and conditions. Knowing that, one can read the note as a friendly reminder of how the ToS of the Apple store is incompatible with GPLv2. You may have read it as snark, but it's literally just stating a matter of fact regarding a matter the author of the fork can't legally do anything about.

And that's awesome and a boon to society!

The core idea here is really interesting; adapting a lossless compression system in a heuristic approximate mode. Instead of looking backwards for identical subsequences, look for approximate subsequences.

Unlike tools like pngquant, which use quantization to create palletized images, this directly hooks into the compression stage. I haven't looked at the source yet, but this is an idea that I've been thinking about recently, especially as regarding the somewhat obscure farbfeld [1] image format, which relies entirely on external compression.

Zlib in particular is "easy" to do this for, or at least an approach is clear, in which you can build up a big prefix tree and then "massage" it by combining subtrees. There are a number of different ways that you could approach this heuristically as well.

Bzip is a different beast -- the Burrows–Wheeler transform is sensitive to changes in the byte stream, so it's not easy to poke a byte to make it similar to another byte and then get the delta on the transform itself.

[1] https://tools.suckless.org/farbfeld/

Huh, I will have to play with this and see how it compares with the naive interframe optimizer I’ve been hacking on for years.

You can do something similar with ffmpeg’s palettegen/paletteuse or imagemagick’s fuzz option. Generally speaking, fuzz/IM does well for recompressing GIFs, especially high-noise or static background. If you still have the source video, nothing can beat ffmpeg though.

(Those options usually require a bit of tweaking though. I can’t compare these at work, might give it a go later.)

This is absolutely not similar to any ffmpeg/IM's options. This doesn't change the palette, and doesn't rely on static backgrounds.

Instead, it integrates very deeply into LZW compression to make dictionary matching visually approximate in a way that maximizes compression. The only other implementation of this that I'm aware of is in Photoshop.

Hi Pornel, thanks a lot for the amazing tool.

If you are doing the animation from scratch, which would be the preferred workflow for smallest size with as few artifacts as possible?

Photoshop Save for Web 256? Which dithering algorithm works best with giflossy?

Would exporting every frame as an individual GIF with its own pallet help?

Generating an MP4 first then run it through some other quantizer?


Lowering pixel resolution and frame rate will reduce file size the most.

Make the gif straight from the original lossless source if possible, since any JPEG-like video compression artifacts will inflate file size in gif.

If the input is a video already, use gif.ski

And then giflossy.

Of course ideally avoid the gif format entirely, since even the best possible compression in it is still horribly awful compared to H.26x and VP9.

Thanks, maybe a more specific question: how does it compare to Photoshop’s lossy option in Save for Web?

Which dither and color reduction algorithms would be better suited for giflossy?

That’s an (impressive) implementation detail. By similar, I mean the result is a smaller GIF.

Gif needs to be EOLd - there is no need to use it as most browsers support modern alternatives like mp4 with real video codecs. Even safari tech preview can now play these inlined.

mp4? That's not a video compression format. It's a stream container format. mp4 files might contain RealVideo (ugh) or MPEG1... or pretty much anything really.

Perhaps you meant h.264 or MPEG-4 (which should not be confused with mp4 container format!).

You can decode GIFs with a few hundred lines of code. Decoding different mp4 cases requires several orders of magnitude more code.

One big advantage of GIFs is simplicity. So perhaps you could come up with something that could be decoded with at most one or two orders of magnitude more code?

Do you suggest that the untold billions of both animated and static GIFs should be lossily transcoded to mp4 (which presumably also has a limited shelf life?) so that we can finally remove GIF support from web browsers because [reason here]?

Btw, mp4 is a container format.

There is also APNG, which might be better suited for this and supports transparency.

APNG is a strictly superior drop in replacement for GIF, has been around for ages, but never got adopted by anyone but firefox. I don't get it. Animated WebP also fills the same role but lacks support outside of Chrome.

The trend of converting gifs to h264 videos is kind of awful in terms of image quality but I'm sure it saves a lot of bandwidth for sites like imgur and twitter.

APNG works in both Chrome and Safari, haven't tested in IE/Edge.

h264 might have an advantage since it does consume less cpu due to hardware support though.

You're right, looks like Chrome added it last year, only 9 years after Firefox. h264 is efficient to decode but it's always lossy and gif->h264 conversions have the worst of both worlds qualities of h264 video compression artifacts and being limited to a 256 color palette.

most normal people consuming the content don’t care about it being lossy as PSNR good. That’s the reason why Giphy and others provide an mp4/264 alternate format. Reddit also seems to be embedding mp4/264 instead of gifs.

aPNG was never accepted by the PNG standards body, and tends to be as large or larger than GIF[1]. If we're going to go through the effort of converting, then WebP makes way more sense.

1. https://www.androidpolice.com/2017/05/01/animated-png-format...

It seems to me that WebP is more of a replacement for "animated" JPEG than PNG. http://littlesvr.ca/apng/gif_apng_webp5.html in these comparisons apng has the edge. Ideally we could have both. Sadly Apple is not willing to add webp/webm support to safari.

If you convert static GIF to static PNG, 99% of the time you'll get a smaller file. That was the original goal of PNG project, and it succeeded: static GIFs disappeared completely. Converting animated GIF to animated PNG leads to similar filesize savings.

Video formats like webp exploit temporal and spatial similarities to get efficiency. Gif/apng do not. This reduces bandwidth costs and file sizes very much.

Download a dozen random GIF cinemagraphs, and try gif2webp and gif2apng on them.

Try ffmpeg or vlc instead, you will get much better results. Ffmpeg has support for almost all video/audio formats ever invented.

I can not believe nobody mentioned:

APNG is (can be?) lossless. You have to lose a lot of quality in GIF to get reasonable filesizes. APNG gets you lossless quality with decent sizes.

Quality sticklers rejoice!

APNG's palette mode is much worse than GIF, and RGBA mode has 3-4 times more data to compress. Deflate is better than LZW, but not that much better, so APNG can only offer either worse quality or worse file size.

Lots of large GIFs used today were converted from H.264 (YouTube, etc.), so the crap quality of H.264 -> GIF -> H.264 is entirely the fault of GIF.

> APNG's palette mode is much worse than GIF

In terms of image quality, it's only slightly worse. But having the same palette for all frames helps to make inter-frame optimization much more efficient.

Post is talking about lossy gif->gif conversion. MP4/H264 do the same but get you 10x gains, while maintaining much better quality. One tradeoff is the loss of transparency.

Yes, I assumed everyone here knows about mp4/h264/etc. Nokia also released a more formal container spec using HEIF, that supports transparency (most folks will complain about patent encumbered issues). However it will be a while before browsers support it.

Browsers get the latest development, but you have to remember that the purpose of GIFs is to be shared, sometimes in applications that are not browsers. They still need to be viewable as intended on those platforms.

Personally as soon as I find a mp4 instead of a gif I curse the uploader for not providing a reasonable gif backup I can use and share around.

> tech preview

As it is not yet generally available as something the public will install, and given how long it can take for a wide userbase to upgrade, this support wouldn't mean being able to set gif's EoL to any date soon.

Unless you refuse to let Safari hold you back as IE6 did for so long (and to an extent newer IE versions still do depending on you target audience - in my day job I have no choice but to support IE 8 and 11 to this day). Though if that is the case then you've stopped actively supporting Safari already.

Will be out in 6 months. Chrome already supports it.

Consider mobile. A huge number of phones, ones you might consider mid tier and not low end, can only play 1 or 2 videos at a time. Hence, the need for a video format that can be rendered in only software.

Except h.264 videos have hw accel behind them (faster + less power draw) and use less data, making them doubly preferable on mobile as well.

Browsers need to be EOLd in favour of sandbox binary app launchers but that's not gonna happen any time soon.

With all the gif art that gets created, I would be really sad about this.

B-but my millenial retro posers
