|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
<html>
|
|
Packit |
f1137c |
<head>
|
|
Packit |
f1137c |
<title>What's In A GIF - LZW Image Data</title>
|
|
Packit |
f1137c |
<style type="text/css">
|
|
Packit |
f1137c |
.byte {font-family: Courier, fixed;
|
|
Packit |
f1137c |
padding: .2em}
|
|
Packit |
f1137c |
.gif_header {background-color: #f9E89D}
|
|
Packit |
f1137c |
.gif_screen {background-color: #C8DBD9}
|
|
Packit |
f1137c |
.gif_color {background-color: #E1E1E1}
|
|
Packit |
f1137c |
.gif_graphic {background-color: #F9EB9D}
|
|
Packit |
f1137c |
.gif_imgdesc {background-color: #C2D1DC}
|
|
Packit |
f1137c |
.gif_imgdata {background-color: #D0C4C4}
|
|
Packit |
f1137c |
.gif_trailer {background-color: #f9E89D}
|
|
Packit |
f1137c |
.gif_ext {background-color: #D0CFAE}
|
|
Packit |
f1137c |
#global_color_size {margin-left: auto; margin-right:auto; border:1px solid black;}
|
|
Packit |
f1137c |
#global_color_size th {border-bottom: 1px solid #666666}
|
|
Packit |
f1137c |
#global_color_size td {text-align:center;}
|
|
Packit |
f1137c |
.code_table {margin-left: auto; margin-right:auto; border:1px solid black;}
|
|
Packit |
f1137c |
.code_table th {text-align: left; border-bottom: 1px solid #666666}
|
|
Packit |
f1137c |
.alg_steps {margin: 0 auto; border: 1px solid black}
|
|
Packit |
f1137c |
.alg_steps th, .alg_steps td {border: 1px solid black}
|
|
Packit |
f1137c |
.alg_steps .index {padding: 0 .3em}
|
|
Packit |
f1137c |
.alg_steps .processed {color: #CCC}
|
|
Packit |
f1137c |
.alg_steps .buffer {background: #C8DBD9 url(highlight_green.gif) repeat-x center left;
|
|
Packit |
f1137c |
border-top: 1px solid #AAA2A2; border-bottom: 1px solid #AAA2A2;}
|
|
Packit |
f1137c |
.alg_steps .current {background: #D0C4C4 url(highlight_purple.gif) repeat-x center left;
|
|
Packit |
f1137c |
border-top: 1px solid #98A5A4; border-bottom: 1px solid #98A5A4;}
|
|
Packit |
f1137c |
</style>
|
|
Packit |
f1137c |
</head>
|
|
Packit |
f1137c |
<body>
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
What's In A GIF
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
(LZW image data)
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Back to the GIF index page.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Now let's look at exactly how we go about storing an image in a GIF
|
|
Packit |
f1137c |
file. The GIF format is a raster format, meaning it stores image data
|
|
Packit |
f1137c |
by remembering the color of every pixel in the image. More
|
|
Packit |
f1137c |
specifically, GIF files remember the index of the color in a color
|
|
Packit |
f1137c |
table for each pixel. To make that clearer, let's review the
|
|
Packit |
f1137c |
sample image we used in the first
|
|
Packit |
f1137c |
section.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Actual Size
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
width="10" height="10" style="padding: 20px" />
(10x10)
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Enlarged
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
title="Enlarged" width="100" height="100" />
(100x100)
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Color Table
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
IndexColor
|
|
Packit |
f1137c |
0White
|
|
Packit |
f1137c |
1Red
|
|
Packit |
f1137c |
2Blue
|
|
Packit |
f1137c |
3Black
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
The color table came from the global color table block. The colors
|
|
Packit |
f1137c |
are listed in the order which they appear in the file. The first color
|
|
Packit |
f1137c |
is given an index of zero. When we send the codes, we always start at
|
|
Packit |
f1137c |
the top left of the image and work our way right. When we get to the
|
|
Packit |
f1137c |
end of the line, the very next code is the one that starts the next
|
|
Packit |
f1137c |
line. (The decoder will "wrap" the image based on the image
|
|
Packit |
f1137c |
dimensions.) We could encode our sample image in the following
|
|
Packit |
f1137c |
way:
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1,
|
|
Packit |
f1137c |
1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 2, 2, 2, 1, 1, 1,
|
|
Packit |
f1137c |
0, 0, 0, 0, 2, 2, 2, ...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
The above listing shows the sequence required to render the first five
|
|
Packit |
f1137c |
lines of the image. We could continue with this method until we've
|
|
Packit |
f1137c |
specified the color for every pixel; however, this can result in a
|
|
Packit |
f1137c |
rather large file. Luckily for us, the GIF format allows us to take
|
|
Packit |
f1137c |
advantage of repetition in our output and to compress our data.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Much of the following information came from John Barkaus's tutorial
|
|
Packit |
f1137c |
LZW and GIF Explained, which seems to have fallen off the
|
|
Packit |
f1137c |
web. I've tried to provide more detailed samples as well
|
|
Packit |
f1137c |
as illustrations to make the process even clearer
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
The compression method GIF use is a variant of LZW
|
|
Packit |
f1137c |
(Lempel-Ziv-Welch) compression. To start using this method, we need a
|
|
Packit |
f1137c |
code table. This code table will allow us to use
|
|
Packit |
f1137c |
special codes to indicate a sequence of colors rather than just one at
|
|
Packit |
f1137c |
a time. The first thing we do is to initialize the code
|
|
Packit |
f1137c |
table. We start by adding a code for each of the colors in the
|
|
Packit |
f1137c |
color table. This would be a local color table if one was provided, or
|
|
Packit |
f1137c |
the global color table. (I will be starting all codes with
|
|
Packit |
f1137c |
"#" to distinguish them from color indexes.)
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
CodeColor(s)
|
|
Packit |
f1137c |
#00
|
|
Packit |
f1137c |
#11
|
|
Packit |
f1137c |
#22
|
|
Packit |
f1137c |
#33
|
|
Packit |
f1137c |
#4Clear Code
|
|
Packit |
f1137c |
#5End Of Information Code
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
I added a code for each of the colors in the global color table of
|
|
Packit |
f1137c |
our sample image. I also snuck in two special control codes. (These
|
|
Packit |
f1137c |
special codes are only used in the GIF version of LZW, not in standard
|
|
Packit |
f1137c |
LZW compression.) Our code table is now considered initialized.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Let me now explain what those special codes are for. The first new code
|
|
Packit |
f1137c |
is the clear code (CC). Whenever you come across the clear code
|
|
Packit |
f1137c |
in the image data, it's your cue to reinitialize the code table. (I'll
|
|
Packit |
f1137c |
explain why you might need to do this in a bit.) The second new code
|
|
Packit |
f1137c |
is the end of information code (EOI). When you come across
|
|
Packit |
f1137c |
this code, this means you've reached the end of the image. Here I've placed
|
|
Packit |
f1137c |
the special codes right after the color codes, but actually the value of
|
|
Packit |
f1137c |
the special codes depends on the value of the LZW minimum code size
|
|
Packit |
f1137c |
from the image data block. If the LZW minimum code size is the same as
|
|
Packit |
f1137c |
the color table size, then special codes immediatly follow the colors; however
|
|
Packit |
f1137c |
it is possible to specify a larger LWZ minimum code size which may leave
|
|
Packit |
f1137c |
a gap in the codes where no colors are assigned. This can be
|
|
Packit |
f1137c |
summarizaed in the following table.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
LWZ Min Code
SizeColor
CodesClear
CodeEOI
Code
|
|
Packit |
f1137c |
2#0-#3#4#5
|
|
Packit |
f1137c |
3#0-#7#8#9
|
|
Packit |
f1137c |
4#0-#15#16#17
|
|
Packit |
f1137c |
5#0-#31#32#33
|
|
Packit |
f1137c |
6#0-#63#64#65
|
|
Packit |
f1137c |
7#0-#127#128#129
|
|
Packit |
f1137c |
8#0-#255#256#257
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Before we proceed, let me define two more terms. First the index
|
|
Packit |
f1137c |
stream will be the list of indexes of the color for each of
|
|
Packit |
f1137c |
the pixels. This is the input we will be compressing. The code
|
|
Packit |
f1137c |
stream will be the list of codes we generate as output. The
|
|
Packit |
f1137c |
index buffer will be the list of color indexes
|
|
Packit |
f1137c |
we care "currently looking at." The index buffer will contain a list
|
|
Packit |
f1137c |
of one or more color indexes. Now we can step though the LZW
|
|
Packit |
f1137c |
compression algorithm. First, I'll just list the steps. After that
|
|
Packit |
f1137c |
I'll walk through the steps with our specific example.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Initialize code table
|
|
Packit |
f1137c |
Always start by sending a clear code to the code stream.
|
|
Packit |
f1137c |
Read first index from index stream. This value is now the value
|
|
Packit |
f1137c |
for the index buffer
|
|
Packit |
f1137c |
<LOOP POINT>
|
|
Packit |
f1137c |
Get the next index from the index stream to the index buffer. We will
|
|
Packit |
f1137c |
call this index, K
|
|
Packit |
f1137c |
Is index buffer + K in our code table?
|
|
Packit |
f1137c |
Yes:
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
add K to the end of the index buffer
|
|
Packit |
f1137c |
if there are more indexes, return to LOOP POINT
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
No:
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Add a row for index buffer + K into our code table with
|
|
Packit |
f1137c |
the next smallest code
|
|
Packit |
f1137c |
Output the code for just the index buffer to our code steam
|
|
Packit |
f1137c |
Index buffer is set to K
|
|
Packit |
f1137c |
K is set to nothing
|
|
Packit |
f1137c |
if there are more indexes, return to LOOP POINT
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Output code for contents of index buffer
|
|
Packit |
f1137c |
Output end-of-information code
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Seems simple enough, right? It really isn't all that bad. Let's
|
|
Packit |
f1137c |
walk though our sample image to show you how this works. (The steps I
|
|
Packit |
f1137c |
will be describing are summarized in the following table. Numbers
|
|
Packit |
f1137c |
highlighted in green are in the index buffer; numbers in purple are
|
|
Packit |
f1137c |
the current K value.) We have already initialized our code table. We
|
|
Packit |
f1137c |
start by doing two things: we output our clear code (#4) to the code
|
|
Packit |
f1137c |
stream, and we read the first color index from the index stream, 1,
|
|
Packit |
f1137c |
into our index buffer [Step 0].
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Now we enter the main loop of the algorithm. We read the next index
|
|
Packit |
f1137c |
in the index stream, 1, into K [Step 1]. Next we see if we have a
|
|
Packit |
f1137c |
record for the index buffer plus K in the code stream. In this case we
|
|
Packit |
f1137c |
looking for 1,1. Currently our code table only contains single colors
|
|
Packit |
f1137c |
so this value is not in there. Now we will actually add a new row to
|
|
Packit |
f1137c |
our code table that does contain this value. The next available code
|
|
Packit |
f1137c |
is #6, we will let #6 be 1,1. Note that we do not actually send this
|
|
Packit |
f1137c |
code to the code stream, instead we send just the code for the
|
|
Packit |
f1137c |
value(s) in the index buffer. The index buffer is just 1 and the code
|
|
Packit |
f1137c |
for 1 is #1. This is the code we output. We now reset the index buffer
|
|
Packit |
f1137c |
to just the value in K and K becomes nothing. [Step 2].
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
We continue by reading the next index into K. [Step 3]. Now K is 1 and the
|
|
Packit |
f1137c |
index buffer is 1. Again we look to see if there is a value in our code
|
|
Packit |
f1137c |
table for the buffer plus K (1,1) and this time there is. (In fact we just
|
|
Packit |
f1137c |
added it.) Therefore we add K to the end of the index buffer and clear out
|
|
Packit |
f1137c |
K. Now our index buffer is 1,1. [Step 4].
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
The next index in the index stream is yet another 1. This is our
|
|
Packit |
f1137c |
new K [Step 5]. Now the index buffer plus K is 1,1,1 which we do not
|
|
Packit |
f1137c |
have a code for in our code table. As we did before, we define a new
|
|
Packit |
f1137c |
code and add it to the code table. The next code would be #7; thus #7
|
|
Packit |
f1137c |
= 1, 1, 1. Now we kick out the code for just the values in the index
|
|
Packit |
f1137c |
buffer (#6 = 1,1) to the code stream and set the index buffer to be
|
|
Packit |
f1137c |
K. [Step 6].
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Step
|
|
Packit |
f1137c |
Action
|
|
Packit |
f1137c |
Index Stream
|
|
Packit |
f1137c |
New Code Table Row
|
|
Packit |
f1137c |
Code Stream
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
0
|
|
Packit |
f1137c |
Init
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
#6 - 1, 1
|
|
Packit |
f1137c |
#4 #1
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
3
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
4
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
5
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
6
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
#7 - 1, 1, 1
|
|
Packit |
f1137c |
#4 #1 #6
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
7
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
8
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
9
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
10
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
#8 - 1, 1, 2
|
|
Packit |
f1137c |
#4 #1 #6 #6
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
11
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
12
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
#9 - 2, 2
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
13
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
14
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
15
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
16
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
#10 - 2, 2, 2
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
17
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
18
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
19
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
20
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
#11 - 2, 2, 1
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
21
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
22
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
23
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
24
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
25
|
|
Packit |
f1137c |
Read
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
26
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
1...
|
|
Packit |
f1137c |
#12 - 1, 1, 1, 1
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
I've included a few more steps to help you see the pattern. You
|
|
Packit |
f1137c |
keep going until you run out of indexes in the index stream. When
|
|
Packit |
f1137c |
there is nothing new to read, you simply write out the code for
|
|
Packit |
f1137c |
whatever values you may have in your index buffer. Finally you should
|
|
Packit |
f1137c |
send the end-of-information code to the code stream. In this example,
|
|
Packit |
f1137c |
that code is #5. (View the
|
|
Packit |
f1137c |
complete code table.)
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
As you can see we dynamically built many new codes for our code
|
|
Packit |
f1137c |
table as we compressed the data. For large files this can turn into a
|
|
Packit |
f1137c |
large number of codes. It turns out that the GIF format specifies a
|
|
Packit |
f1137c |
maximum code of #4095 (this happens to be the largest 12-bit
|
|
Packit |
f1137c |
number). If you want to use a new code, you have to clear out all of
|
|
Packit |
f1137c |
your old codes. You do this by sending the clear code (which for our
|
|
Packit |
f1137c |
sample was the #4). This tells the decoder that you are reinitializing
|
|
Packit |
f1137c |
your code table and it should too. Then you start building your own
|
|
Packit |
f1137c |
codes again starting just after the value for your end-of-information
|
|
Packit |
f1137c |
code (in our sample, we would start again at #6).
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
The final code stream would look like this:
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7 #8 #10 #2 #12 #1 #14 #15 #6 #0 #21 #0 #10 #7 #22 #23
|
|
Packit |
f1137c |
#18 #26 #7 #10 #29 #13 #24 #12 #18 #16 #36 #12 #5
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
This is only 36 codes versus the 100 that would be required without compression.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
At some point we will need to turn this code stream back into
|
|
Packit |
f1137c |
a picture. To do this, we only need to know the values in the stream
|
|
Packit |
f1137c |
and the size of the color table that was used. That's it. You remember that
|
|
Packit |
f1137c |
big code table we built during compression? We actually have enough information
|
|
Packit |
f1137c |
in the code stream itself to be able to rebuild it.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Again, i'll list the algorithm and then we will walk though an example. Let
|
|
Packit |
f1137c |
me define a few terms i will be using. CODE will be current code we're working
|
|
Packit |
f1137c |
with. CODE-1 will be the code just before CODE in the code stream. {CODE}
|
|
Packit |
f1137c |
will be the value for CODE in the code table. For example, using the code
|
|
Packit |
f1137c |
table we created during compression, if CODE=#7 then {CODE}=1,1,1.
|
|
Packit |
f1137c |
In the same way, {CODE-1} would be the value in the code table for the
|
|
Packit |
f1137c |
code that came before CODE. Looking at step 26 from the compression,
|
|
Packit |
f1137c |
if CODE=#7, then {CODE-1} would be {#9}, not {#6}, which was 2,2.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Initialize code table
|
|
Packit |
f1137c |
let CODE be the first code in the code stream
|
|
Packit |
f1137c |
output {CODE} to index stream
|
|
Packit |
f1137c |
<LOOP POINT>
|
|
Packit |
f1137c |
let CODE be the next code in the code stream
|
|
Packit |
f1137c |
is CODE in the code table?
|
|
Packit |
f1137c |
Yes:
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
output {CODE} to index stream
|
|
Packit |
f1137c |
let K be the first index in {CODE}
|
|
Packit |
f1137c |
add {CODE-1}+K to the code table
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
No:
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
let K be the first index of {CODE-1}
|
|
Packit |
f1137c |
output {CODE-1}+K to index stream
|
|
Packit |
f1137c |
add {CODE-1}+K to code table
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
return to LOOP POINT
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Let's start reading though the code stream we've created to show how to
|
|
Packit |
f1137c |
turn it back into a list of color indexes. The first value in the code
|
|
Packit |
f1137c |
stream should be a clear code. This means we should initialize our code
|
|
Packit |
f1137c |
table. To do this we must know how many colors are in our color table.
|
|
Packit |
f1137c |
(This information comes from the first byte in the image data block in
|
|
Packit |
f1137c |
the file. More on this later.) Again we will set up codes #0-#3 to be each
|
|
Packit |
f1137c |
of the four colors and add in the clear code (#4)
|
|
Packit |
f1137c |
and end of information code (#5).
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
The next step is to read the first color code. In the following table you
|
|
Packit |
f1137c |
will see the values of CODE highlighted in purple, and the values for
|
|
Packit |
f1137c |
CODE-1 highlighted in green. Our first CODE value is #1. We then output
|
|
Packit |
f1137c |
{#1}, or simply 1, to the index stream [Step 0].
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Now we enter the main loop of the algorithm. The next code gets assigned
|
|
Packit |
f1137c |
to CODE which now makes that value #6. Next we check to see if this value
|
|
Packit |
f1137c |
is in our code table. At this time, it is not. This means we must find the
|
|
Packit |
f1137c |
first index in the value of {CODE-1} and call this K. Thus K = first index of
|
|
Packit |
f1137c |
{CODE-1} = first index of {#1} = 1. Now we output {CODE-1} + K to the index
|
|
Packit |
f1137c |
stream and add this value to our code table. The means we output 1,1 and
|
|
Packit |
f1137c |
give this value a code of #6 [Step 1].
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Step
|
|
Packit |
f1137c |
Action
|
|
Packit |
f1137c |
Code Stream
|
|
Packit |
f1137c |
New Code Table Row
|
|
Packit |
f1137c |
Index Stream
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
0
|
|
Packit |
f1137c |
Init
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7 ...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
1
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7 ...
|
|
Packit |
f1137c |
#6 - 1, 1
|
|
Packit |
f1137c |
1, 1, 1
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
2
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7 ...
|
|
Packit |
f1137c |
#7 - 1, 1, 1
|
|
Packit |
f1137c |
1, 1, 1, 1, 1
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
3
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7 ...
|
|
Packit |
f1137c |
#8 - 1, 1, 2
|
|
Packit |
f1137c |
1, 1, 1, 1, 1, 2
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
4
|
|
Packit |
f1137c |
Not Found
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7 ...
|
|
Packit |
f1137c |
#9 - 2, 2
|
|
Packit |
f1137c |
1, 1, 1, 1, 1, 2, 2, 2
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
5
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7 ...
|
|
Packit |
f1137c |
#10 - 2, 2, 2
|
|
Packit |
f1137c |
1, 1, 1, 1, 1, 2, 2, 2, 2, 2
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
6
|
|
Packit |
f1137c |
Found
|
|
Packit |
f1137c |
#4 #1 #6 #6 #2 #9 #9 #7 ...
|
|
Packit |
f1137c |
#11 - 2, 2, 1
|
|
Packit |
f1137c |
1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
We start the loop again by reading the next code. CODE now would be
|
|
Packit |
f1137c |
#6 and this time we do have a record for this code in our code
|
|
Packit |
f1137c |
table. Thus we dump {#6} to the index stream which would be 1,1.
|
|
Packit |
f1137c |
Now we take the first index in {#6} and call that K. Here, {#6} has
|
|
Packit |
f1137c |
two indexes, the first of which is 1; thus K = 1. Before moving
|
|
Packit |
f1137c |
on, we add {CODE-1}+K to the code table. This #7 is now 1, 1, 1 [Step 2].
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
I've included a few more steps so you can see the algorithm in action. While
|
|
Packit |
f1137c |
the explanation may sound complicated, you can see it's actually quite simple.
|
|
Packit |
f1137c |
You'll also notice that you end up building the exact same
|
|
Packit |
f1137c |
code table
|
|
Packit |
f1137c |
as the one that was created during compression. This is the reason that
|
|
Packit |
f1137c |
LZW is so great; we can just share the codes and not the table.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
I've shown you how to go back and forth between index and code stream, but
|
|
Packit |
f1137c |
haven't told you what to do with them. The index stream is used to specify the
|
|
Packit |
f1137c |
color of each of the pixel of your image and really only shows up on screen.
|
|
Packit |
f1137c |
It is the code stream that is actually saved in the GIF files on your computer
|
|
Packit |
f1137c |
or transmitted over the internet. In order to save these code streams, we must
|
|
Packit |
f1137c |
turn them into bytes. The first thought might be to store each of the codes
|
|
Packit |
f1137c |
as its own byte; however this would limit the max code to just #255 and
|
|
Packit |
f1137c |
result in a lot of wasted bits for the small codes. To solve these problems,
|
|
Packit |
f1137c |
the GIF file format actually uses flexible code sizes.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Flexible code sizes allow for further compression by limiting the bits
|
|
Packit |
f1137c |
needed to save the code stream as bytes. The code size is the number
|
|
Packit |
f1137c |
of bits it takes to store the value of the code. When we talk about bits,
|
|
Packit |
f1137c |
we're referring to the 1's and 0's that make up a byte. The codes are
|
|
Packit |
f1137c |
converted to their binary values to come up with the bits. To specify
|
|
Packit |
f1137c |
the code for #4, you would look at this binary equivalent, which is 100,
|
|
Packit |
f1137c |
and see that you would need three bits to store this value. The largest code
|
|
Packit |
f1137c |
value in our sample code stream is #36 (binary: 100100) which would
|
|
Packit |
f1137c |
take 6 bits to encode. Note that the number of bits i've just given is
|
|
Packit |
f1137c |
the minimum number. You can make the number take up more bits by adding
|
|
Packit |
f1137c |
zeros to the front.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
We need a way to know what size each of the codes are. Recall that the
|
|
Packit |
f1137c |
image data block begins with a single byte value called the
|
|
Packit |
f1137c |
LZW minimum code size. The GIF format allows sizes as small
|
|
Packit |
f1137c |
as 2 bits and as large as 12 bits. This minimum code size value is typically
|
|
Packit |
f1137c |
the number of bits/pixel of the image. So if you have 32 colors in your image,
|
|
Packit |
f1137c |
you will need 5 bits/pixel (for numbers 0-31 because 31 in binary is 11111).
|
|
Packit |
f1137c |
Thus, this will most likely be one more than the bit value for the size of the
|
|
Packit |
f1137c |
color table you are using. (Even if you only have two colors, the minimum
|
|
Packit |
f1137c |
code size most be at least 2.) Refer to the
|
|
Packit |
f1137c |
code table above to remind yourself how that works.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Here's the funny thing: the value for minimum code size isn't
|
|
Packit |
f1137c |
actually the smallest code size that's used in the encoding
|
|
Packit |
f1137c |
process. Because the minimum code size tells you how many bits are
|
|
Packit |
f1137c |
needed just for the different colors of the image, you still have to
|
|
Packit |
f1137c |
account for the two special codes that we always add to the code
|
|
Packit |
f1137c |
table. Therefore the actual smallest code size that will be used is
|
|
Packit |
f1137c |
one more than the value specified in the "minimum" code size
|
|
Packit |
f1137c |
byte. I'll call this new value the first code size.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
We now know how many bytes the first code will be. This size will probably
|
|
Packit |
f1137c |
work for the next few codes as well, but recall that the GIF format
|
|
Packit |
f1137c |
allows for flexible code sizes. As larger code values get added to your
|
|
Packit |
f1137c |
code table, you will soon realize that you need larger code sizes if you
|
|
Packit |
f1137c |
were to output those values. When you are encoding the data, you increase
|
|
Packit |
f1137c |
your code size as soon as your write out the code equal to
|
|
Packit |
f1137c |
2^(current code size)-1. If you are decoding from codes to indexes,
|
|
Packit |
f1137c |
you need to increase your code size as soon as you add the code value that
|
|
Packit |
f1137c |
is equal to 2^(current code size)-1 to your code table. That is, the next
|
|
Packit |
f1137c |
time you grab the next section of bits, you grab one more.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Note that the largest code size allowed is 12 bits. If you get to this
|
|
Packit |
f1137c |
limit, the next code you encounter should be the clear code which
|
|
Packit |
f1137c |
would tell you to reinitialize the code table. You then go back to using
|
|
Packit |
f1137c |
the first code size and grow again when necessary.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Jumping back to our sample image, we see that we have a minimum code
|
|
Packit |
f1137c |
size value of 2 which means out first code size will be 3 bits long.
|
|
Packit |
f1137c |
Out first three codes, #1 #6 and #6, would be coded as 001 110 and 110.
|
|
Packit |
f1137c |
If you see at Step 6 of the encoding, we added a code of #7 to our code
|
|
Packit |
f1137c |
table. This is our clue to increase our code size because 7 is equal to
|
|
Packit |
f1137c |
2^3-1 (where 3 is our current code size). Thus, the next code we
|
|
Packit |
f1137c |
write out, #2, will use the new code size of 4 and therefore look
|
|
Packit |
f1137c |
like 0010. In the decoding process, we again would increase our code
|
|
Packit |
f1137c |
size when we read the code for #7 and would read the next 4, rather than
|
|
Packit |
f1137c |
the next 3 bits, to get the next code. In the sample table above this
|
|
Packit |
f1137c |
occurs in Step 2.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Finally we must turn all these bit values into bytes. The lowest bit of the
|
|
Packit |
f1137c |
code bit value gets placed in the lowest available bit of the byte. After
|
|
Packit |
f1137c |
you've filled up the 8 bits in the byte, you take any left over bits and
|
|
Packit |
f1137c |
start a new byte. Take a look at the following illustration to see
|
|
Packit |
f1137c |
how that works with the codes from our sample image.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
alt="Encoding LZW Codes" style="border: 1px solid black" / WIDTH="500"
|
|
Packit |
f1137c |
HEIGHT="220">
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
You can see in the first byte that was returned (
|
|
Packit |
f1137c |
class="byte">8C) that the lowest three bits (because that was
|
|
Packit |
f1137c |
our first code size) contain 110 which is the binary value of 4 so
|
|
Packit |
f1137c |
that would be the clear code we started with, #4. In the three bits to
|
|
Packit |
f1137c |
the left, you see 001 which out or first data code of #1. You can also
|
|
Packit |
f1137c |
see when we switched into code sizes of 4 bits in the second byte
|
|
Packit |
f1137c |
(2D).
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
When you run out of codes but have filled less than 8 bits of the
|
|
Packit |
f1137c |
byte, you should just fill the remaining bits with zeros. Recall that
|
|
Packit |
f1137c |
the image data must be broken up onto
|
|
Packit |
f1137c |
href="bits_and_bytes.html#image_data_block">data sub-blocks. Each
|
|
Packit |
f1137c |
of the data sub-blocks begins with a byte that specifies how many
|
|
Packit |
f1137c |
bytes of data. The value will be between 1 and 255. After you read
|
|
Packit |
f1137c |
those bytes, the next byte indicates again how many bytes of data
|
|
Packit |
f1137c |
follow. You stop when you encounter a subblock that has a lenght of
|
|
Packit |
f1137c |
zero. That tells you when you've reached the end of the image data. In
|
|
Packit |
f1137c |
our sample the image the byte just after the LZW code size is
|
|
Packit |
f1137c |
class="byte">16 which indicates that 22 bytes of data
|
|
Packit |
f1137c |
follow. After we reach those, we see the next byte is
|
|
Packit |
f1137c |
class="byte">00 which means we are all done.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Return codes from bytes the basically just the same process in
|
|
Packit |
f1137c |
reverse. A sample illustration of the process follows which shows how
|
|
Packit |
f1137c |
you would extract codes if the first code size were 5 bits.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Next: Animation and Transparency
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
That is pretty much everything you need to know to read or generate
|
|
Packit |
f1137c |
a basic image file. One of the reasons the GIF becames such a popular
|
|
Packit |
f1137c |
format was because it also allowed for "fancier" features. These
|
|
Packit |
f1137c |
features include animation and transparency. Next we'll look
|
|
Packit |
f1137c |
at how those work.
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Continue...
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
Back to GIFLIB documentation
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
</body>
|
|
Packit |
f1137c |
|
|
Packit |
f1137c |
</html>
|