GIF file format (Note: PNG computer_graphics_tools.html#png is a better graphics file format. see Dr. Tim Kientzle (kientzle@netcom.com), in ÒPNG: Son of GIF But No RelationÓ article in _PC Techniques_ June 1995. Associated source code should be available via anonymous FTP from the site ftp.mv.com (192.80.84.3) in the /pub/ddj/1995.06/ directory. )

FIXME: move to http://en.wikipedia.org/wiki/Gif

See data_compression.html for links to explanations of the LZW compression algorithm used by GIF.

quotes from "Reading GIF Files" by Wilson MacGyver Liaw (macgyver@cis.ohio-state.edu), in Dr. Dobb's Journal, Feb. 1995. Associated source code should be available via anonymous FTP from the site ftp.mv.com (192.80.84.3) in the /pub/ddj/1995.02/ directory. ftp.ddj.com http://www.ddj.com/ftp/ /* was ftp.mv.com (192.80.84.1) */

There is a pointer to the Graphics Interchange Format (GIF) developed by CompuServe, version 89a. http://wwwhost.ots.utexas.edu/mac/pub-mac-graphics.html

"For information on writing and otherwise manipulating GIF files, I recommend _Bitmapped Graphics Programming in C++_ by Marv Luse (Addison Wesley, 1993), or _Programming for Gaphics Files in C and C++_ by John Levine (John Wiley and Sons, 1994)."

6 bytes: header: "GIF87a" or "GIF89a".
7 bytes: logical screen-descriptor block:
	2 bytes: logical screen width
	2 bytes: logical screen height
	1 byte: packed field:
		x80: global color-table flag
		x70: 3 bits of color resolution:
			number of bits per primary color available, minus 1.
			(0 == 1 bit; 1 == 2 bits; max of 7 == 8 bits).
		x08: sort flag (1 == table sorted in order of decreasing importance).
		x07: 3 bits: size of Global Color Table = (1<<(value+1)).
			(max of 7 = 256 colors; min of 0 = 2 colors).
	1 byte: Background-color index
		(index into global color table for background color)
	1 byte: "pixel aspect ratio":
		true aspect ratio is approximately ("pixel aspect ratio" +15)/64,
		ranges from 4:1 for widest pixel, to 1:4 for the tallest pixel.

"If the 1-bit global color-table flag is set to 1, the global color table will follow the logical screen-descriptor block." each entry of the color table is 3 bytes (a red, green, and blue byte).

Every image starts with the image descriptor block, followed by an optional local color table, and the LZW-compressed image data.

10 bytes:image descriptor block:
	1 byte: Image Separator: 0x2C
	2 bytes: Image Left position
	2 bytes: Image top position
	2 bytes: Image Width
	2 bytes: Image height
	1 byte: packed:
		x80: Local color-table flag
			if 1, the local color table
			(in same triple format as global color table)
			is read and used instead of the global color table
			for this image only.
		x40: Interlace flag (1==interlaced)
		x20: sort flag(1 == table sorted in order of decreasing importance).
		x18: Reserved 2 bits
		x07: (3 bits) Size of local color table  = (1<<(value+1)).

compressed image data: 1st byte: LZW minimum code size. .... compressed image data .... terminated with an end-of-information code. initial number of bits used for the compression codes is set by the "LZW minimum code size" ... when the number of patterns detected by the encoder exceeds the maximum number of patterns allowed by the current code size, the number of bits per code is increased by one. GIF allows up to 12 bits per code, thus the maxumum of 4096 codes. ... 2 special codes ...

• the clear code: (1<<minimum code size). If the minimum code size is 2, then the clear code would be 4. The clear code resets and initializes the table back to the startup state. [see below]
• end-of-information code ... defined as (clear code + 1)... marks the end of the LZW-compressed image data.

Interlace format:
Row	1st group	2nd group	3rd group	4th group
0	x
1							x
2					x
3							x
4			x
5							x
6					x
7							x
8	x
9							x
10					x
11							x
12			x

GIF89a introduces extension blocks ... many types ... all start with a byte called the "extension introducer" which always contains the value 0x21.... terminated with a block terminator ... the value 0x00 ... allows the reader to skip the extension block ...

comment extension block:
	(bytes)
	1: extension introducer: 0x21
	1: comment label: 0xFE
	x: comment data: 7-bit ASCII chars
	1: extension terminator: 0x00

information on other extension blocks is in the file "Graphics Interchange Format Version 89a" on the CompuServe Grphics Support Forum, library 17.

All GIF files end with the 1 byte trailer block, 1 byte: 0x3B.

Listing One (p. 103, Dr. Dobb's Journal, Feb. 1995) contains C code that deals with the GIF-variant LZW algorithm. http://www.ddj.com/

end of Wilson MacGyver Liaw article.

see also GIFPICT.CPP; should also be avail at DDJ site.

From: AIIGH! <morrisom at rintintin.Colorado.EDU>
Message-Id: <199508141640.KAA11594@benji.Colorado.EDU>
Subject: Re: More GIF help pleeeeeeeze....
To: cary at agora.rdrop.com (David Cary)
Date: Mon, 14 Aug 1995 10:40:05 -0600 (MDT)
X-Mailer: ELM [version 2.4 PL22]

Thanks for the GIF help.  Actually, I finally solved it all, and it turned
out to be something else.  I was assuming that, if my initial codes were
nine bits, that the clear code was nine bits regardless of where it
was in the data stream.  It turns out that it's the same number of bits as
are currently in the code (say 12).  That, and I wasn't packing the bytes
like I thought I was.  Oh well, live and learn.  Let me know if you need
help with whatever your project is.

 - Mark (morrisom at benji.colorado.edu)

From: AIIGH! <morrisom at rintintin.Colorado.EDU>
Subject: Re: GIF stuff
To: cary at agora.rdrop.com (David Cary)
Date: Wed, 9 Aug 1995 11:44:22 -0600 (MDT)

Thanks for the help.  In the file you included, you asked about how a
code size of 2 could produce a clear code of 4.  I actually think I
understand this part, so here goes:

The initial code size that precedes the GIF image is just the number of bits
per pixel.  The clear code, according to the GIF specs, is 2 raised to this
power.  So, if the initial code size is 2, the clear code is 2*2 or 4.  For
an 8-bit image, the clear code is 256.  It doesn't matter what the current
code size is, because the clear code (and the end-of-information code) is
reserved from the start based on the initial code size.

Anyways, hope that answers your question.  Thanks again for helping me
with mine.

 - Mark








	

	
	http://www.ccil.org/~esr/esr-freeware.html
	
	giflibCode to generate, slice, dice, puree, and chop GIF images.
	Includes both library routines callable from C and lots of useful
	utilities. Supports UNIX and DOS.


	

	one reason for not using GIF
	
	http://www.href.com/delphi/isapi.dll?HUBAPP:PGPNG:3883580
	

	

	more reasons not to use GIF
	
	http://www.gnu.org/philosophy/gif.html
	
	(use
	PNG
	
	computer_graphics_tools.html#png
	
	instead).

	

	If you're writing a decoder, please handle the
	"dictionary full" condition properly --
	-- continue use the current dictionary,
	just don't add more items.
	
	
From: Tom Lane 
Subject: Re: Gif compression question
Date: 11 Dec 1999 00:00:00 GMT
Sender: tgl@netcom7.netcom.com
Organization: Netcom Online Communications Services
X-Server-Date: 11 Dec 1999 06:06:23 GMT
Newsgroups: alt.comp.compression,comp.compression

mrd708@anu.edu.au (Matthew Doulgeris) writes:
> [ excellent explanation of LZW compression snipped ]

I just have a minor correction on this point:

> We could continue on to thirteen bits and up, but most compressors
> limit the size of the dictionary to 4096 elements. When the dictionary
> hits this point (or sometimes earlier as dictated by the compressor) a
> "reset" token is transmitted and the dictionary is restored to its
> initial state.

All LZW compressors that I know of have a definite upper limit on the
size of the dictionary and therefore also on the maximum code length.
However, it's not necessary to "reset" immediately when the dictionary
is full: one can simply continue to transmit data using the current
dictionary, without adding new items to the dictionary anymore.

In fact, if the statistics of the input data are unvarying, the
*optimal* thing to do is to continue using the filled dictionary,
rather than resetting and starting from scratch.  The only reason
to reset and start a new dictionary is to adapt to new input data
with different statistics.

The very first widely used implementation of LZW, the Unix "compress"
program, had quite a sophisticated method for exploiting this point.
The compressor measured the compression ratio it was getting on-the-
fly, and would stick with the filled dictionary until the ratio dropped
noticeably, indicating that the input data's statistics had shifted.
Then it'd issue a CLEAR code and start building a fresh dictionary.

Indeed, there'd be no need of a CLEAR code if the algorithm were always
to clear the dictionary the moment it fills --- the decoder could track
that change just as it tracks the addition of codes to the dictionary.
The whole point of having a CLEAR code is to let the encoder make some
kind of heuristic, not-hard-wired decision about when the dictionary
is no longer reflective of the input data.

Some years after Unix "compress", there were half-baked GIF-writing
programs that didn't do any such measurement, but just always issued
CLEAR instantly when their dictionaries filled.  Not long thereafter,
there were even-less-than-half-baked GIF-reading programs that would
actually crash *hard* if fed a GIF that didn't include an instant
CLEAR at every dictionary fill, because they'd keep filling dictionary
locations without bothering to notice if their arrays were full :-(.
Evidently the authors of these readers only tested them against the
output of the aforesaid half-baked writers.  And a while after that,
we find people saying that this brain damage is part of the definition
of the LZW algorithm.  It's not, it's only a symptom of incompetent
implementation.  The writer should be able to postpone CLEAR as long
as it likes.

                        regards, tom lane







the entire
	
	GIF87a specification
	ftp://ftp.ncsa.uiuc.edu/misc/file.formats/graphics.formats/gif87a.doc
	


end
gif.html