• Basic Description
• Basic File Format
• Extension Block Function Codes
• Raster Data Encoding 
• Sample GIF LZW-encoder / compressor
• Sample GIF encoder without LZW
• Sample GIF LZW-decoder / decompressor
• Sample GIF decoder without LZW
• Interlaced Images
•  Portability
•  Trademarks, Patents and Royalties
•  Cross Checking Software
•  Resources 
•  Online
•  Paper
•  Disclaimer

Basic Description

Basic File Format

Extension Block function codes

Raster Data encoding

             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 2^{InitialCodeSize + 1}      = ClearCode 
Entry 2^{InitialCodeSize + 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

(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) portability
repeat until no more pixels
if c <> empty output code for c
output End-Of-Information

Sample GIF encoder without LZW

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

(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

Interlaced Images

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

Portability

Warnings

• 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.
• 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. 
• 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

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). None of them have succeeded yet in terms of wide cross platform availability. 

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

The following software is able to decode GIFs: 

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

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

Online Resources