Basic Description

GIF was invented by Compuserve for their online service, but the specifications were made publicly available. GIFs can hold multiple bitmaps of up to 256 colors each, using LZW compressed raster data to minimize file sizes. (Yes, it can hold more than 256 colors total, and yes, that's the patented compression)

Basic File Format

Name			Size	Description
Signature			6 bytes	'GIF87a' or 'GIF89a'
GlobalDescriptor			7 bytes	global descriptor, always present
	Width		2 bytes	width in pixels
	Height		2 bytes	height in pixels
	Flags		1 byte	global descriptor flags
		GlobalColorMap	bit 7	=1 if GlobalColorMap exists (should be true in almost all cases) =0 if default map is used, or if every image has a LocalColorMap
		ColorResolutionBits	bits 6-4	+1 = significant bits per color in GlobalColorMap
		reserved	bit 3	=0
		PixelBits	bits 2-0	+1 = ColorDepth, NumberOfGlobalColors := 2ColorDepth
	BackgroundColor		1 byte	background color number (from GlobalColorMap or default map)
	AspectRatio		1 byte	usually =0
GlobalColorMap			NumberOfGlobalColors * 3	global color table, present only when GlobalDescriptor.Flags.GlobalColorMap = 1
		Red	1 byte	red intensity of color (not necessarily 8 significant bits)
		Green	1 byte	green intensity of color (not necessarily 8 significant bits)
		Blue	1 byte	blue intensity of color (not necessarily 8 significant bits)
	repeated NumberOfGlobalColors times
ExtensionBlocks			cannot be pre calculated	optional, may be repeated any number of times. read first byte to check its presence.
	Header		1 byte	=$21
	FunctionCode		1 byte	there is a list of known function codes below
		Length	1 byte	>0 !
		Data	Length bytes	interpretation of this data depends on its function code
	repeated any number of times. read first byte to check for terminator
	Terminator		1 byte	=0
LocalDescriptor			10 bytes	local descriptor. always present
	Header		1 bytes	=$2C
	PosX		2 bytes	horizontal position of image in global image
	PosY		2 bytes	vertical position of image in global image
	Width		2 bytes	width of image
	Height		2 bytes	height of image
	Flags		1 byte	local descriptor Flags
		LocalColorMap	bit 7	=1 if LocalColorMap exists =0 if GlobalColorMap (or default map) is used
		InterlacedImage	bit 6	=1 Interlaced ! =0 Non Interlaced
		Sorted	bit 5	usually =0
		reserved	bit 4-3	=0
		PixelBits	bit 2-0	+1 = ColorDepth, NumberOfLocalColors := 2ColorDepth
LocalColorMap			NumberOfLocalColors * 3	local color table, present only when LocalDescriptor.Flags.LocalColorMap = 1
		Red	1 byte	red intensity of color
		Green	1 byte	green intensity of color
		Blue	1 byte	blue intensity of color
	repeated NumberOfLocalColors times
Raster Data Block			cannot be pre calculated	always present
	InitialCodeSize		1 byte	usually = ColorDepth, except for black&white, where it is 2!
		Length	1 byte	>0
		Data	Length bytes	The pixel data bit stream. See decompression and compression schemes
	repeated any number of times. read first byte to check for terminator
	Terminator		1 byte	=0!
ExtensionBlocks			cannot be pre calculated	optional. read first byte to check its presence - format is identical to the ExtensionBlock above
Terminator			1 byte	=$3B

Extension Block function codes

Function Code	Name		Size	Description
1	PlaintextExtension		any	< incomplete >
249	LocalDescriptorExtension		4 bytes
	Flags		1 byte
		reserved ?	bits 7-5
		Undraw	bits 4-2	000 undefined (portability warning) 001 leave image for overwrite 010 restore background 011 restore previous 1xx undefined _
		User Input	bit 1
		Transparent	bit 0	=1 image has a transparent color =0 no transparent color
	Duration		2 bytes
	TransparentColor		1 byte
254	CommentExtension		any
255	ApplicationExtension		any

Raster Data encoding

Pixel data is stored in the data chunks of the Raster Data Blocks. It is a continuous stream of data (without line-wrap interruptions) top-down, left-to-right.

Since the LZW compression scheme used for GIFs produces codes of different bit length, codes are not stored in multiples of bytes, but as a bit stream instead. The size of codes starts with < InitialCodeSize > + 1, eventually increasing within the file. The least significant bit of the first byte in the data block is the least significant bit of the LZW code.

Example (9bit codes):

Code 3 Code 2 Code 1
================= ================= =================
0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
=============== =============== =============== ===============
Byte 4 Byte 3 Byte 2 Byte 1

When writing GIFs, codes are generated from the pixels by a LZW algorithm. When reading GIFs, codes are passed to another LZW algorithm to turn them into pixel values again. The string table used by both algorithms is initially this:
Entries 0 .. NumberOfColors - 1 are mapped to their color table entries 0 .. NumberOfColors - 1 respectively.
Entry 2InitialCodeSize + 1 = ClearCode
Entry 2InitialCodeSize + 1+1 = ClearCode + 1 = End-Of-Information
For GIFs with more than 1bit per pixel these entries are NumberOfColors and NumberOfColors + 1.

Sample GIF LZW-encoder / compressor

This is standard way of writing GIFs. If you use this, you will get small files, and you are using the Unisys patent.
(Pseudo code is a modified version from 'GIF explained' by Steve Blackstock)

c: string of pixels
p: single pixel

Initialize string table. (entries 0 .. End-Of-Information) codesize = InitialCodeSize + 1 c := empty output a ClearCode _
	p := next pixel
	is (c + appended p) in string table?
	Yes:	c := c + appended p
	No:	append (c + appended p) to string table output code for c to file c := p if code = max. for code size (code = 511 @ 9bits?) increase codesize by 1 if codesize = 13 reset string table, output a 12bit ClearCode and reset codesize to (InitialCodeSize + 1) (see portability warning)
repeat until no more pixels
if c <> empty output code for c output End-Of-Information

Sample GIF encoder without LZW

This is the non-standard way of writing GIFs. This code does not use Unisys' patent, but produces considerably larger files. All GIF decoders will still read these files.

codesize = InitialCodeSize + 1 ClearCode = 2^CodeSize EndOfInformation = ClearCode + 1 counter = EndOfInformation + 1 output a ClearCode
		p := next pixel c := p + added high order bit 0 output c increment counter if counter = max. for CodeSize - 1: write ClearCode and reset counter to EndOfInformation + 1
repeat until no more pixels
output End-Of-Information

Notice the following: There is no string table - if you have one, you are using LZW. CodeSize never changes - it could, since you simply have to count the codes you write to check whether it should, but this results in smaller files only with color depths <=2. There is no compression taking place, every pixel uses one more bit than necessary to store the data in, that bit is the highest order bit and is always zero.

The overhead to this system is the combined storage consumption of that additional zero bit and the ClearCode, which occurs every 2 Codesize - 1 - 3 pixels. (n = number of pixels, / is integer division):

colordepth in bits	codesize overhead in bits approx.	overhead %
8	9 n + 9n / 253	13%
7	8 n + 8n / 125	15%
6	7 n + 7n / 61	19%
5	6 n + 6n / 29	24%
4	5 n + 5n / 13	35%
3	4 n + 4n / 5	60%
2	3 n + 3n	200%
1	3 2n + 3n	500%
encoding schemes with increasing code lengths
2	3+4 1.66n + 4n / 8	191%
1	3+4 2.66n + 4n / 8	316%

Sample GIF LZW-decoder / decompressor

This is the standard way of reading GIFs. If you use this you can read all GIF files, and you are using the Unisys patent.
(Pseudo code is a modified version from 'GIF explained' by Steve Blackstock)

code: word
c: string of pixels
old: string of pixels

Initialize string table (entries 0 .. End-Of-Information) codesize = InitialCodeSize + 1 code <- first code from file c <- string table entry for code output c old <- c
	code <- next code from file if code = ClearCode: Reinitialize string table, and reset codesize to InitialCodeSize + 1 is code in string table?
	Yes:	add to string table: (old + appended first pixel of c) c <- string table entry for code
	No:	add to string table: (old + appended first pixel of old) c <- new string table entry
	output c old <- c if (added-table-entry# = max. for codesize) and (codesize < 12 ) (code = 511 @ 9bits?) increase codesize by 1
repeat until code = EndOfInformation

Sample GIF decoder without LZW

This is the non-standard way of reading GIFs. It does not use the Unisys patent, but it cannot cannot read all GIFs. Nevertheless, it can read the GIFs written with the non LZW encoder. There is a very small possibility for a GIF file written by a LZW encoder to actually look the same as with the non LZW version. An example would be an image with all pixels in a different color, where LZW produces the same output as the non LZW version. Those files can also be read by this. To check this, simply attempt to read the file. If you get to a code that is larger than EndOfInformation you would need the string table to decode it - which you don't have - and you'll have to quit reading. Do not make any attempt to try to decode it those files. If you do, make sure you understand that you are entering the field of LZW decompression again, and could simply use the LZW decoder above.

codesize = InitialCodeSize + 1 ClearCode = 2^CodeSize EndOfInformation = ClearCode + 1 counter = EndOfInformation + 1
		code <- next code from file increment counter if code < ClearCode: output a pixel of color (code) if code = ClearCode: counter = Endofinformation + 1, codesize = InitialCodeSize + 1 if (counter = max. for codesize) and (codesize < 12) increase codesize by 1
repeat until code >= EndOfInformation
if last code was not EndOfInformation: throw away image

Interlaced Images

Interlaced images change the order of lines as they are encoded in the Raster Data Blocks. As opposed to all lines being in a top to down order, they are intermixed by a specific four pass scheme:

Pass	Scheme	Lines	Number of Lines
1	Every 8th line, starting from line 0	0, 8, 16, 24, ...	(height+7) div 8
2	Every 8th line, starting from line 4	4, 12, 20, 28, ...	(height+3) div 8
3	Every 4th line, starting from line 2	2, 6, 10, 14, ...	(height+1) div 4
4	Every 2nd line, starting from line 1 (all odd lines)	1, 3, 5, 7, 9, ...	(height) div 2

Note: "div" is integer division. All passes can be empty.

Portability

The GIF format was created with portability in mind. There is almost no platform where it can't be viewed. The 16bit data is stored in 'Intel-' order, Least Significant Byte first. Most non Intel machines will have to swap bytes to get the actual data. Portable code should read data byte wise.

Portability Warning 1: The Undraw-Flag Problem

The use of the undraw-flag is inconsistent. Writers should use a standard of 01 - not 00. When using transparent colors, overwriting and replacing is not the same. Using 10 and 11 together with partial images will give strange results on different readers. Some viewers will restore the background/previous of the whole image, some will restore it only on the partial image that had been overwritten. Look at the Internet Explorer and Netscape Navigator to see the difference. Therefore an encoder should not use them in conjunction.

Portability Warning 2: The Deferred Clear Code Problem

The GIF specification is more flexible than the algorithm shown above, in that a encoder does not have to write a ClearCode when the string table is full. decide not to do so, in which case it should continue to use whatever is already in the string table, - and stick to a codesize of 12 bits. Unfortunately a lot of programs - including the Netscape Navigator - are unable to read these files. This problem has been addressed by the cover sheet of the GIF89a specifications, but for some reason quite a lot of people seem to have ignored it.

Portability Warning 3: Default Colors

The default color map is NOT the 216-color CLUT of internet browsers! Default in terms of GIF means direct hardware mapping (i.e. HardwareColor := ColorIndex MOD NumberOfHardwarePaletteEntries) To use the default CLUT of internet browsers, get a copy of it and include it as a global color map. A reader could use probably use anything as default color map.

Trademarks, Patents and Royalties

GIF and 'Graphics Interchange Format' are trademarks of CompuServe Inc. They have made the format publicly available without royalties or licensing restrictions.
The LZW compression is/was patented by Unisys. Unisys licenses the use of LZW to software manufacturers for money! They have a FAQ on their web site on this subject. Expect to pay $1000 in advance. Unisys does not own the rights to the GIF file format. The patent has expired, at least in most countries.

There has been a long discussion about the Unisys patent. When Unisys started collecting fees from programmers, some of them removed the GIF functionality from their products. Many of them put it back in due to customer demand. There also have been a number of approaches to get rid of GIF and its royalties by introducing a new file format (such as PNG).

There is a way of writing GIFs that does not make use of LZW, and therefore does not require a Unisys license. A general purpose reader on the other hand would have to use LZW to be able to read all GIFs. The other discussion that keeps going on is on the pronunciation of GIF, which has not jet been resolved, and it more or less shouldn't matter how you call it, if you know how to handle it.

(please read the disclaimer)

Cross-Checking Software

This section is for programmers, who wish to cross-check their implementation with others. This is an incomplete list of programs, which are available as freeware / shareware / try-before-buy etc.
The following software is able to decode GIFs:

Netscape Navigator
Microsoft Internet Explorer
JASC/Corel Paint Shop Pro (reads only the first image)

The following software is able to encode GIFs:

JASC Paint Shop Pro (writes single image GIFs only)
Microsoft GIF-Animator

Online Resources

The following suggestions are from the Graphics Fileformats FAQ:
Links specializing in GIF89a animations:
GIF Animation Secrets
Royal Frazier's GIF Animation on the WWW
MultiGIF GIF89a Animation Utility
GIFMerge Utility

Disclaimer

This is not the official format documentation. Although we're doing our best to keep this information as accurate as possible, there is no way of checking all of it under all possible circumstances. We're not taking any responsibility for the results of these information or lack thereof. The 'trademarks, patents and royalties' section is here just for your convenience, and is in no way complete. Please send us a note, if you find any incorrect of missing information.

GIF File Format