Enthusiasms

Enthusiasms is an edited stream of consciousness, by Simen.

GIF: A Technical History

From a technical standpoint, the success of the lowly GIF is a mystery. Both as an image format and as a video/animation format, it’s vastly inferior to the alternatives. It only supports 256 colors; its compression is inefficient; it doesn’t support sound; the last specification was published more than twenty years ago. Yet it’s still thriving. The reason, of course, is convenience: on the web, the GIF, and especially the animated GIF, is the only video format that runs everywhere, runs automatically, and loops. These characteristics serve to make the GIF a potent vector for memes. But the story of how we got here is really the story of the internet growing up, and for that reason, it’s worth spending a few words on. Maybe even a lot of words, more words than most file formats deserve.

I’m going to attempt the impossible: to tell an engaging story accessible to relative laymen using a hex editor (a program for manually editing binary files). The above is the binary content of a very simple test GIF I made in order to better understand the GIF specification. Here it is, if you want to play along at home: . I’ll walk you through each part of the file, and explain each part as it pertains to the history of the GIF.

GIF89a

The Graphics Interchange Format (GIF) was invented by CompuServe in 1987. The eighties were really the wild west days of the internet. The web had yet to be invented, and the internet had yet to go mainstream. At the start of the decade, there was no such thing as a single internet. Instead, there were a bunch of different computer networks that gradually grew together to form one. CompuServe ran one of these networks.

CompuServe was founded in 1969. These were the days when computers were so large and expensive that regular companies couldn’t afford one, so they rented computing time from a timesharing company. Compuserve was one such company, and they built a dial-up network to support their business. In 1979, they became the first to provide an online service to regular consumers. This was not the internet: it was a self-contained network, unconnected to the various other computer networks at the time. Downloading files from this network—which would be connected to the general internet in the late 80s—was the purpose GIF was designed for. The first GIF standard was released in 1987, and the second in July, 1989. The GIF file format has remained unchanged since then. The web hadn’t been invented yet.

GIF files weren’t intended to store animations. Unlike other image formats, however, GIF files were designed to hold more than one image. This had more to do with eliminating redundant information that was shared across files than with sequences of moving images. Online connections weren’t fast in 1987. Here’s what the 1989 standard has to say:

A GIF Data Stream is a sequence of protocol blocks and sub-blocks representing a collection of graphics. In general, the graphics in a Data Stream are assumed to be related to some degree, and to share some control information; it is recommended that encoders attempt to group together related graphics in order to minimize hardware changes during processing and to minimize control information overhead.

The updated standard published in 1989 introduced two crucial features on the way to the animated GIF we all know and love. One was delays between one image and the next. There was no explicit mention of animation in the standard:

Delay Time - If not 0, this field specifies the number of hundredths (1/100) of a second to wait before continuing with the processing of the Data Stream.

The other new feature was Application Extension Blocks, which allow for information to be encoded into GIF files that tells a specific application to process the file in a specific way. (Other applications will ignore this info.) Note that the standard actually discourages developers from using Application Extension Blocks, and instead recommends that they embed the GIF format in their own file formats:

As an embedded protocol, GIF may be part of larger application protocols, within which GIF is used to render graphics. (…) This approach is recommended in favor of using Application Extensions, which become overhead for all other applications that do not process them.

04 00 04 00

This part defines the size of what the GIF standard calls the “Logical Screen”. This is the overall size of the image (here 4x4 pixels, each dimension stored as a 16-bit integer). Note, however, that each image in the file need not have the same dimensions as the “logical screen”. As long as the image fits within the logical screen, it can be smaller, and indeed, each image within a GIF file must specify an offset of the logical screen. (If you have a GIF where the content is surrounded on all sides by one solid color, you can use this feature to optimize the file.)

FF FF FF 00 00 00

After some flags, we come to another well-known feature of GIFs: the color table. As you probably know, GIFs can only store 256 different colors. This makes it ill-suited for true-color photographs. These 256 colors, however, can be chosen from a palette of millions. It’s just that out of those millions of colors, each image in the GIF can only use 256. The color table stores the color values for each of these 256 colors, and then the rest of the file simply specifies where in the table each pixel’s color is located. This GIF file has the simplest possible palette: only two colors, pure white (FF FF FF) and pure black (00 00 00). GIF was an improvement over CompuServe’s older file format, which only supported black and white.

!NETSCAPE2.0

This is where things start to get interesting. In 1991, Tim Berners-Lee opened the web to the public. Although there were others, the first great web browser was called Mosaic. Mosaic evolved into the second great browser, and the one that went head-to-head with Internet Explorer during the Browser Wars of the nineties: Netscape Navigator. (The Netscape codebase later evolved into Mozilla Firefox. Netscape lost the war with Internet Explorer, but IE lost the war to Firefox. The Mosaic line won in the end. But I digress.)

In the early days, there was no way to embed an image into an HTML page. While working on Mosaic, Marc Andreessen came up with the <img> tag. You can read more about this here. When Andreessen announced the <img> tag in February, 1993, his was far from the only proposed way to embed images into web pages. Many people disagreed with his proposal. Some proposed alternative tags. Others wanted a general solution to embedding other media into web pages. Why create a dedicated image tag, when this would surely lead to dedicated video tags, audio tags, and so on? Why not create a general solution that could embed all sorts of media, including images, video, audio, and novel future media?

This was another important moment that led to the ubiquity of animated GIFs. Andreessen and the other pioneers could have devised a way to embed general media into web pages in 1993. If they had, then we wouldn’t have had to wait so long for non-GIF video formats to work everywhere. But Andreessen’s proposal won out, and so the GIF, the video file format that masquerades as still image, became the only way to display moving images on the web everywhere you can display stills. Why did Andreessen win? Because he happened to be the developer of a popular web browser, and he shipped code that worked. Once <img> worked in Mosaic, it soon spread and became ubiquitous. The img tag started showing up in HTML standards after the web browsers had standardized on it.

Then, finally, we get to Netscape 2.0. Peek inside a GIF file sometime: every animated GIF contains a reference to Netscape Navigator 2.0, a browser that has been obsolete for fifteen years. Netscape 2 introduced a slew of new features: embedded Java, JavaScript, frames. And animated GIFs. Netscape 2.0, you see, defined one of those Application Extension Blocks. What the Extension Block does is basically say that the browser should loop through each image within the GIF file. Although other people had come up with the idea of using the multi-image feature of GIF to make animations, interest in animated GIFs didn’t explode until Netscape made the feature available to website owners everywhere.

Remember this little fellow, one of the first animated GIFs to truly go viral?

21 F9 04 04 64 00 00 00 2C

Finally, we’re closing in on the actual image in my sample GIF. The sequence that starts with an exclamation point (0x21 in hex) is a control block that has metadata for the image data to come.

The highlighted section in the screenshot says that the browser should wait one-hundred 1/00ths of a second (i.e., one whole second) after rendering the first frame before rendering the next. After the comma comes the first image frame.

02 04 8C 8F 19 05 00

The tiny bits here are the actual pixel data. Everything else is metadata. Of course, I deliberately made this file very small in order for it to be instructive. In a real file, which would be much larger than 4x4 pixels, data will outweigh metadata. The pixel data, as mentioned, consists of a series of bytes, each of which represents one pixel by telling a decoder where in the color table to look for the right color value. Only, it’s not so simple. As you can see, there are only seven bytes to describe sixteen pixels, and each pixel is supposed to be described by one byte. This is because the lossless Lempel-Ziv-Welch compression algorithm is used to reduce file sizes.

When CompuServe developed GIF in 1987, LZW compression was a commonly used technique, and CompuServe found it natural to use it for GIF. Unbeknownst to CompuServe, however, a patent on the LZW technique had been already been granted to Unisys. For years, Unisys chose to ignore people using it in software, rather staking their claim against manufacturers implementing the algorithm in hardware. In late 1994, Unisys suddenly decided to start pursuing software implementations, and CompuServe in particular. Predictably, there was outrage. The whole debacle ended with a deal where people who wrote software that processed GIF files would have to pay royalties to UniSys, while end users were free to use GIF as they pleased. In order to develop a completely free and open alternative to GIF, a working group sat down and eventually came up with PNG.

The LZW patents expired in 2004, and since then, GIF has been completely free.

3B, or ;

The semicolon indicates the end of a GIF file, and the end of this discussion. I said that I find this story interesting and instructive, and I stand by that. I fully understand that some may consider this too long and too technical, but the technical aspects tie in to many of the most important events and trends in internet history.

Here’s an interesting graph. I don’t know of any way to reliably quantify the public interest in GIFs, but we can make an estimate using Google trend data. Although it feels like GIFs (especially the animated variety) are everywhere, people certainly are googling less for them than they were before. I suspect that while meme gifs are common on blogs and forums, the many other uses for the file format are slowly being phased out. The GIF is really only suitable for small pictures with a very limited color palette. Due to historical accident, it has seen more widely use than its technical qualities would indicate. Now, finally, twenty-plus years after the GIF was invented, we’re seeing widespread support and adoption of alternatives. PNGs, JPEGs and HTML5’s <video> are making the old uses for the GIF obsolete. What we are left with is the GIF as a lowest common denominator. Not unlike the memes it’s being paired with.

If you’re technically inclined, and if the above mass of words wasn’t enough for you, you might want to read the GIF specification. Be prepared to muck around alt-tabbing between binary files and your browser window for a while before it starts making sense. The specification also details other, little-used (and little-supported) features of the file format, such as waiting for user input before proceeding with an animation, and rendering plain text stored in the file (not in the rasterized image data).

Feb 3, 2012