</p>
<b>3c.Example</b>
<p>Let抯 do a brief explanation of what happens when we run Cat256tInTheHatAnd263eR257 through our little decompressor:
<ol>
<li>1. C is read and outputted, First_code = 'C'</li>
<li>2. Next_Code = 'a', 'a' is in table so it is outputted, and "Ca", 256 is added to the table. First_code = 'a'</li>
<li>3. Next_Code = 't', 't' is in table so it is outputted, and "at", 257 is added to the table. First_Code = 't'</li>
<li>4. Next_Code = 256, '256' is in table, so "Ca" is outputted, "tC" , 258 is added to string table, and First_code = 256.</li>
</ol>
The rest should come really easy. And the check if it the code is not in the table is not used in this example, try entering Data like:<br>

AndAndAndAndAndAndAndAndAndAndAndAndAndAndAndAndAndAndAndAnd<br>

"And" see what happens, to keep this tutorial simple we won抰 focus on it to much, if you need to learn more about it have a look at the source and other tutorials in the references section.

And that concluded the decompression stage, whoa; you now know how to use LZW compression!
</p>
<a name = "gif"><b>The GIF</b></a>
<hr><br>
<b>4a.What is it?</b>
<p>
Okay now well go a cover the GIF format. Briefly to summarize what GIF is, GIF stands for the Graphics Interchange Format and is one of the widely accepted methods of transferring images over the net. However it has begun to show its age (supporting only a maximum of 8 bit or 256 colour images) and is gradually being replaced. So we might as well discuss it while it's not extinct like the dinosaurs.

Okay, now obviously we can't just run our decompressor over the image and hope for it to work, the GIF format makes some subtle differences to the code were used too. First there is a header, which looks like so:
</p>
<b>4b. The GIF Format</b>
<p>
<pre>
GIF HEADER
6 Bytes		Signature
2 Bytes		ScreenWidth
2 Bytes		ScreenHeight
1 Byte		Depth
1 Byte		Background
1 Byte		Reserved(87a) or Pixel Aspect Ratio
</pre>
<b>Descriptions:<br><br></b>
<b>Signature</b> - Is either GIF87a or GIF89a, each version has a few changes but most are not to important, the most noticeable being the fact GIF89a supports animated images<br>
<b>ScreenWidth</b> - The maximum size of an image in a GIF, if this is an animated GIF, images can be smaller or equal to this size<br>
<b>ScreenHeight</b> - See above<br>
<b>Depth</b> - This is divided into several bits, as follows:<br>
<b>-----------------Packed Fields-----------<br></b>
<b>Bit 0-2</b>: In 87a these hold the value of pixel, which is the number of bits -1 per pixel in the image. In 89a it抯 the size of the palette ((pixel+1)^2).<br>
<b>Bit 3</b> - Reserved in 87a, in 89a its a sort flag telling you that colours in the colour table are listed in decreasing order of important, but its not big deal now(unless your running a 256 colours desktop).<br>
<b>Bit 4-6</b>: These are cs, cs+1 is the colour resolution of the image. <br>
<b>Bit 7</b> - If set we have a global palette, meaning only one palette in total, if not we have a local palette which means you'll find a palette before each image. (If there are multiple images)<br>
<b>-----------------Packed Fields--------------------<br></b>
<b>Background</b> - The background colour, only important if you have an animated GIF, and some of the "ScreenWidth or Height" is not full.<br>
<b>Reserved/Aspect Ratio</b>: This really isn't important, but uh, if you really need to know more read the GIF89a from wotsit (see references).<br>

Now the <b>Palette</b>, If there is a global palette (Meaning Bit 7 in depth is set) you read this RIGHT after the header, if not after the image identifier, the palette looks like so:<br>
<pre>
1 Byte - red intensity, 0-255-----| Repeat for every color<br>
1 Byte - green intensity, 0-255   | in colour table, usually<br>
1 Byte - blue intensity, 0-255----| (cs+1)^2<br>
</pre>
Remember that the colour map starts with colour 0 and works up!
Now these values are right shifted twice (many 8 bit palette handlers use 6 bit channels, or 0-63 colours per channel) so you may need to left shift twice or divide by 4(unless you抮e dealing with win32api, which wants 0-255 palette entries). However, it really depends on your palette routines so check your documentation on it. Allegro uses 6 bits, and that's why I brought it up.

Now after that, you want to look for the Image Descriptor, which looks like so:
<pre>
IMAGE DESCRIPTER
1 Byte - 	ID
2 Bytes - 	ImageLeft
2 Bytes - 	ImageTop
2 Bytes - 	Width
2 Bytes -	Height
1 Byte - 	Depth
</pre>
<b>ID</b> - This is the ',' char or 0x2C in hex.<br>
<b>ImageLeft</b> - How many pixels from the left of the Screenwidth the image starts<br>
<b>ImageTop</b> - Same as above except below top<br>
<b>Width</b> - Width of image in pixels<br>
<b>Height</b> - Height of image in pixels<br>
<b>Depth</b> - Okay this is another packed bit, and is rather different in 89a and 87a. Remember if Bit 7 is not set, you only need to worry about Bit 6 as the others are relevant to Bit 7<br>
<b>-----------------Packed Fields--------------------<br></b>
<b>Bit 0-2</b>: Pixel, in 87a this is bits per pixel-1, in 89a this is the size of the colour table (pixel+1)^2.<br>
<b>Bit 3-4</b>: Reserved both in 87a and 89a<br>
<b>Bit 5</b>: 87a unused, 89a tells that palette is in order of decreasing importance<br>
<b>Bit 6</b>: Image is interlaced, more on interlaced later<br>
<b>Bit 7</b>: if set means has a local palette (animated GIF) meaning the palette starts, then the image otherwise is false meaning image starts right after.<br>
<b>-----------------Packed Fields--------------------<br></b>
It is very important to realize that the image descriptor does NOT HAVE TO START AFTER THE HEADER, keep reading through the GIF until you find the ',' character, then you read the image, otherwise your loader may experience problems with certain GIFs.<br>

After that there is the image which looks like so
<pre>
1 Byte	 		CodeSize
1 Byte 			BufferSize -------|Repeat until
BufferSize Bytes	Buffer     -------|EOI is found
</pre>
Okay, now <b>CodeSize</b> is equal to the bpp +1. This is because the LZW compression of GIF works intelligently. GIF can compress with a maximum of 12 bits per code, however it starts of using only bpp+1 bits per code, and then when the last code used is equal to codeSize^2 then it increases CodeSize by one. This goes on to a maximum of 12 bits, this allows the GIF to compress small images as well as large images.<br>

Now <b>Buffersize</b> is essentially a number from 0-255 that tells how many bytes you're to read and then you repeat it, pretty pointless if you ask me but remember if you read 0 remember to stop reading the image!<br>

Now onto the GIF <b>buffer</b>, this is the same as the lzw compression we just cover with a few differences. They are:<br>
<ul>
<li>a) Variable compression, we already covered this, basically if only 9 bits (any code less then 511) is needed then 9 is used, when code 511 is read, then the compression switches to 10 bits. This goes up until 12, were the maximum is then reached<</li>

<li>b) Now the other variation is the clear code, this bpp ^2 (so if the image has 256 colors, or 8 bit, it would be 256). This can be found anywhere in the buffer, and when it is found, you must clear the tables and codes, and start decompressing with clear tables</li>

<li>c) The final reserved code is bpp^2+1, which is EOI, when this is found the image is finished and you can stop reading.</li>

Okay now that you've loaded an image, you can keep reading until you find the ';', or 0x3B found after you've loaded an image, if you find a ',' before it(89a), that means it is an animated GIF, and you'll have to load more images!
</ul>
Now that's it, you can load a GIF, Hopefully I've explained it really clearly, if not, here is a little present, more pseudo code!

</p>
<b>4c. GIF Pseudo Code</b>
<p>
<pre>
Load Header
Load Image Descriptor after ID has been found
Clear LZW tables
get First_Code
get Code_Size
DO
 get Next_Code
 If Codeword = Clear Code (CC)
  Clear LZW Table
	get FirstCode
Elseif CodeWord = EOI
   BREAK LOOP 
Else
     if Next_Code is NOT in the string table
		String_Buffer = translated First_code + 
    first byte of First_Code
	else
		String_Buffer = Translation of Next_Code
	add translated First_code + first byte of 
First_Code to the table
	First_Code = Next_Code
	display String_Buffer

  If Code_Used = COdesize ^2 -1  AND CodeSize > 12    
     CodeSize = Codesize +1
LOOP  
</pre>
Make sure to check for the CC(clear code) and EOI(end of image), and the MINUTE your last code used is the CodeSize ^2-1 (So if it was a CodeSize of 9, 511), then increase your CodeSize. The rest is the same as your standard LZW loading, so ill leave actually writing the whole thing an exercise to you, however, you may look at the sources that come with the tutorial, ported to a couple of languages so take a look at which ever one you prefer!
</p>

<b>4d.Advanced GIF topics</b>
<p>
Okay there are a few things of the GIF I have not covered yet:
First:
Interlaced GIFs, as promised, here is the info I was holding out: 

Interlaced GIFs are similar to normal GIFs, except they are designed to be able to display parts of the image before the image has been downloaded. They do that by encoding not top to bottom, but every 8th line, starting with line 0, then every 8th row, starting with row 4, then every 4th row starting with 2 and then finally, you draw every 2nd line, starting with line 1. Confused well, here is a quick drawing:
</p>
<pre>
Row Number          Drawn on pass
0			1
1			   4
2			  3
3			   4
4			 2
5			   4
6			  3
7			   4
8			1
9			   4
10			  3
11			   4
12			 2
13			   4
14			  3
15			   4
16			1
</pre>
This way, an image is gradually formed, rather then being drawn top to bottom, it made sense when 56k modems were common, but now it doesn't really have many benefits. Nothing else is different, the only difference is the way the pixels are drawn and compressed.

<br><b>GIF 89a Extensions</b><br>
GIF 89a adds many new features to the GIF format, some of which have already been discussed, and Ill briefly mention the names of the additions and how to read them
<ul>
<li>The GIF 89a additions begin with the symbol 0x21; this is found before an image descriptor. After the identifier, another identifier is used to determine which extension is used. The extensions are, with a brief summary:</li>

<li>Graphics Control Extension - used mainly for transparency, as well as having a few other flags. Extension identifier is 0xF9.</li>

<li>Comment Extension - adds user comments to an image, extension identifier is 0xFE.</li>

<li>Plain text extension - Used to draw the image in text. Really it抯 not terribly important, identifier is 0x01.</li>

<li>Application Extension - I'm not sure what use this has, identifier is 0xFF. (It doesn't help load the image so don't worry about it).</li>
</ul>
For more information on these extensions please consult the official GIF 89a documentation, it can be found in the references section.
</p>
<a name = "code"><b>Source Code</b></a>
<hr>

<b>5a. The Source Code contains 2 ports</b>
<p>
The C code is 100% C, and works in both MSVC and Mingw, and I'm positive will work in any ANSII c compatible compiler (if not tell me which one and ill see what I can do). The GIF Loading section requires Allegro, I used version 4 but older and newer versions (within reason) should be compatible (I didn't exactly push it to the limits). They were not tested under LINUX, however
GifAllegS is uses the same code base and it works under Linux, so this code should too, hopefully.<br><br>

The Java code was written for the JVM 1.4.2, but likewise I didn't do anything special, older/newer versions within reason should be compatible. Because Java has built in support for
Gifs, I did not port the GIF code over, but you are welcome to do so.<br><br>

Both ports were written for clarity, and I tried my best to write legible, clear code. The code is not optimized for speed and I wouldn't be surprised if the speed can be easily increased (You should have no trouble speeding things up). Global variables in C were avoided, in fact, none are used. Neither are static variables. Code is meant to be modified, feel free to do so, be sure to give credit, the code is freeware, but on the understanding that credit will be given where it is due. Be sure to thank some people from the reference section if you have room as well, I would never have been able to write this without them.<br>
<br>
I didn't do a C++ port, although I admit it would be really cool to use constructors and other stuff, but the Java code is close enough, and easily ported. And besides, the C code works well enough in C++. Though I won't hide the fact that I think the C++ version would come out really nice and be totally awesome to use, especially with the ability for vector tables and other stuff... the Java code is a port, and I didn抰 use any of its really neat features unfortunately.<br>
</p>
<b>5b. Notes on Source Code</b>
<p>
Okay, first off if you find a bug 
please report it to me, and better yet, if you know how to fix it send that too, it'll help greatly. Also you can drop by the http://starsdev.cjb.net/developer/ website and see if any new tutorials ever come up. There
you can also find my Allegro GIF library.<br><br>

GIF interlaced is not supported; neither are local colourmaps or animated GIFs. These are easy to write however, and check the references for any more information you may need. Consider it an exercise. If you look at the source code you'll notice that it loads the entire buffer chunk at once, which is faster then reading each byte, but does waste memory. You can read a byte at a time instead if you wanted to, try doing so as an exercise, you'll find it very simple to do!
(Although, most computers do have 256 MB of ram)<br><br>