GIF file format (Note: PNG computer_graphics_tools.html#png is a better graphics file format. see Dr. Tim Kientzle (email@example.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 (188.8.131.52) 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 (firstname.lastname@example.org), in Dr. Dobb's Journal, Feb. 1995. Associated source code should be available via anonymous FTP from the site ftp.mv.com (184.108.40.206) in the /pub/ddj/1995.02/ directory. ftp.ddj.com http://www.ddj.com/ftp/ /* was ftp.mv.com (220.127.116.11) */
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 ...
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
From: Tom Lane
Subject: Re: Gif compression question Date: 11 Dec 1999 00:00:00 GMT Sender: email@example.com Organization: Netcom Online Communications Services X-Server-Date: 11 Dec 1999 06:06:23 GMT Newsgroups: alt.comp.compression,comp.compression firstname.lastname@example.org (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