========================================================================== 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 colours each, using LZW compressed raster data to minimize file sizes. (Yes, it can hold more than 256 colours total, and yes, that's the patented compression) ========================================================================== Basic File Format Offset Name Size Description 0 Signature 3 bytes "GIF" 3 Version 3 bytes "87a" or "89a" GlobalDescriptor 7 bytes global descriptor, always present 6 Width 2 bytes width in pixels 8 Height 2 bytes height in pixels 10 Flags 1 byte global descriptor flags: GlobalColourMap bit 7 =1 if GlobalColourMap exists (should be true in almost all cases) =0 if default map is used, or if every image has a LocalColourMap ColourResolutionBits bits 6-4 +1 = significant number of bits per colour in GlobalColourMap reserved bit 3 =0 PixelBits bits 2-0 +1 = ColourDepth, NumberOfGlobalColours = 2^ColourDepth 11 BackgroundColour 1 byte background colour number (from GlobalColourMap or default map) 12 AspectRatio 1 byte usually =0 GlobalColourMap 3* NumberOfGlobalColours global colour table, present only when GlobalColourMap = 1 13 {Red 1 byte Red intensity (not necessarily 8 significant bits) Green 1 byte Green intensity (not necessarily 8 significant bits) Blue 1 byte Blue intensity (not necessarily 8 significant bits) } repeated NumberOfGlobalColours times From 13+3*NumberOfGlobalColours onwards are blocks marked by the leading byte. Extension Blocks ~~~~~~~~~~~~~~~~ ExtensionBlocks Optional, may be repeated any number of times. Read first byte to check its presence. 0 {Header 1 byte =$21 1 FunctionCode 1 byte there is a list of known function codes 2 Length 1 byte >0 3 Data Length 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 Raster Data ~~~~~~~~~~~ LocalDescriptor Local descriptor. Always present 0 Header 1 byte =$2C 1 PosX 2 bytes horizontal position of image in global image 3 PosY 2 bytes vertical position of image in global image 5 Width 2 bytes width of image 7 Height 2 bytes height of image 9 Flags 1 byte local descriptor Flags LocalColourMap bit 7 =1 if LocalColourMap exists =0 if GlobalColourMap (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 = ColourDepth, NumberOfLocalColours = 2^ColourDepth 10 LocalColourMap 3 * NumberOfLocalColours local colour table, present only when LocalColourMap = 1 {Red 1 byte Red intensity (not necessarily 8 significant bits) Green 1 byte Green intensity (not necessarily 8 significant bits) Blue 1 byte Blue intensity (not necessarily 8 significant bits) } repeated NumberOfLocalColours times 10+3*NumberOfLocalColours The pixel data +0 InitialCodeSize 1 byte usually = ColourDepth, except for black-and- white, where it is 2. +1 {Length 1 byte >0 Data Length 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 Extension Blocks ~~~~~~~~~~~~~~~~ ExtensionBlocks Optional, may be repeated any number of times. Read first byte to check its presence. Terminator ~~~~~~~~~~ Terminator 1 byte =$3B ========================================================================== Extension Block function codes 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 colour =0 no transparent colour Duration 2 bytes TransparentColour 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 (9-bit 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 .. NumberOfColours - 1 are mapped to their colour table entries 0 .. NumberOfColours - 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 NumberOfColours and NumberOfColours + 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 if (c + appended p) in string table? { Yes: c := c + appended p } else { 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 the 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 colour 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): colourdepth codesize overhead in bits approx. in bits 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 } if code in string table? { Yes: add to string table: (old + appended first pixel of c) c <- string table entry for code } else { 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 colour, 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 = 2CodeSize EndOfInformation = ClearCode + 1 counter = EndOfInformation + 1 { code <- next code from file increment counter if code < ClearCode: output a pixel of colour (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 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. 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 colours, 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 colour map is NOT the 216-colour CLUT of internet browsers! Default in terms of GIF means direct hardware mapping (i.e. HardwareColour := ColourIndex MOD NumberOfHardwarePaletteEntries) To use the default CLUT of internet browsers, get a copy of it and include it as a global colour map. A reader could use probably use anything as default colour 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 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. 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. ========================================================================== 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 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: * http://www.fastlane.net/~samiel/anim.shtmlGIF Animation Secrets * http://member.aol.com/royalef/gifanim.htm Royal Frazier's GIF Animation on the WWW * http://www.peritas.com/~abw/multigif.html MultiGIF GIF89a Animation Utility * http://www.iis.ee.ethz.ch/~kiwi/GIFMerge/ 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 this 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 to fileformats@daubnet.com.