1*324bb76bSAndroid Build Coastguard Worker<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 2*324bb76bSAndroid Build Coastguard Worker 3*324bb76bSAndroid Build Coastguard Worker<html> 4*324bb76bSAndroid Build Coastguard Worker<head> 5*324bb76bSAndroid Build Coastguard Worker<title>What's In A GIF - LZW Image Data</title> 6*324bb76bSAndroid Build Coastguard Worker<style type="text/css"> 7*324bb76bSAndroid Build Coastguard Worker.byte {font-family: Courier, fixed; 8*324bb76bSAndroid Build Coastguard Worker padding: .2em} 9*324bb76bSAndroid Build Coastguard Worker.gif_header {background-color: #f9E89D} 10*324bb76bSAndroid Build Coastguard Worker.gif_screen {background-color: #C8DBD9} 11*324bb76bSAndroid Build Coastguard Worker.gif_color {background-color: #E1E1E1} 12*324bb76bSAndroid Build Coastguard Worker.gif_graphic {background-color: #F9EB9D} 13*324bb76bSAndroid Build Coastguard Worker.gif_imgdesc {background-color: #C2D1DC} 14*324bb76bSAndroid Build Coastguard Worker.gif_imgdata {background-color: #D0C4C4} 15*324bb76bSAndroid Build Coastguard Worker.gif_trailer {background-color: #f9E89D} 16*324bb76bSAndroid Build Coastguard Worker.gif_ext {background-color: #D0CFAE} 17*324bb76bSAndroid Build Coastguard Worker#global_color_size {margin-left: auto; margin-right:auto; border:1px solid black;} 18*324bb76bSAndroid Build Coastguard Worker#global_color_size th {border-bottom: 1px solid #666666} 19*324bb76bSAndroid Build Coastguard Worker#global_color_size td {text-align:center;} 20*324bb76bSAndroid Build Coastguard Worker.code_table {margin-left: auto; margin-right:auto; border:1px solid black;} 21*324bb76bSAndroid Build Coastguard Worker.code_table th {text-align: left; border-bottom: 1px solid #666666} 22*324bb76bSAndroid Build Coastguard Worker.alg_steps {margin: 0 auto; border: 1px solid black} 23*324bb76bSAndroid Build Coastguard Worker.alg_steps th, .alg_steps td {border: 1px solid black} 24*324bb76bSAndroid Build Coastguard Worker.alg_steps .index {padding: 0 .3em} 25*324bb76bSAndroid Build Coastguard Worker.alg_steps .processed {color: #CCC} 26*324bb76bSAndroid Build Coastguard Worker.alg_steps .buffer {background-color: #c0efc0; border-top: 1px solid #c0efc0; border-bottom: 1px solid #c0efc0;} 27*324bb76bSAndroid Build Coastguard Worker.alg_steps .current {background-color: #e0d0e0; border-top: 1px solid #e0d0e0; border-bottom: 1px solid #e0d0e0;} 28*324bb76bSAndroid Build Coastguard Worker</style> 29*324bb76bSAndroid Build Coastguard Worker</head> 30*324bb76bSAndroid Build Coastguard Worker<body> 31*324bb76bSAndroid Build Coastguard Worker<table width='100%' cellpadding='0' summary='Canned page header' bgcolor="#ddd"> 32*324bb76bSAndroid Build Coastguard Worker<tr> 33*324bb76bSAndroid Build Coastguard Worker<td><h2>What's In A GIF</h2></td> 34*324bb76bSAndroid Build Coastguard Worker<td align="center"><img src="../giflib-logo.gif"></td> 35*324bb76bSAndroid Build Coastguard Worker<td align="right">(LZW image data)</td> 36*324bb76bSAndroid Build Coastguard Worker</tr> 37*324bb76bSAndroid Build Coastguard Worker</table> 38*324bb76bSAndroid Build Coastguard Worker 39*324bb76bSAndroid Build Coastguard Worker<div id="body"> 40*324bb76bSAndroid Build Coastguard Worker<div style="text-align:center; margin-top: 10px; padding-top: 10px; border-top: #cecece 1px solid"> 41*324bb76bSAndroid Build Coastguard Worker<p><a href="index.html">Back to the GIF index page.</a></p> 42*324bb76bSAndroid Build Coastguard Worker</div> 43*324bb76bSAndroid Build Coastguard Worker 44*324bb76bSAndroid Build Coastguard Worker<p>Now let's look at exactly how we go about storing an image in a GIF 45*324bb76bSAndroid Build Coastguard Workerfile. The GIF format is a raster format, meaning it stores image data 46*324bb76bSAndroid Build Coastguard Workerby remembering the color of every pixel in the image. More 47*324bb76bSAndroid Build Coastguard Workerspecifically, GIF files remember the index of the color in a color 48*324bb76bSAndroid Build Coastguard Workertable for each pixel. To make that clearer, let's review the 49*324bb76bSAndroid Build Coastguard Workersample image we used in the <a href="bits_and_bytes.html">first 50*324bb76bSAndroid Build Coastguard Workersection</a>.</p> 51*324bb76bSAndroid Build Coastguard Worker 52*324bb76bSAndroid Build Coastguard Worker<table style="margin-left: auto; margin-right:auto;"> 53*324bb76bSAndroid Build Coastguard Worker<tr> 54*324bb76bSAndroid Build Coastguard Worker<td style="text-align:center; vertical-align: top; padding: 5px;width:30%"> 55*324bb76bSAndroid Build Coastguard Worker<h3>Actual Size</h3> 56*324bb76bSAndroid Build Coastguard Worker<img src="sample_1.gif" alt="sample gif, actual size" title="Actual Size" 57*324bb76bSAndroid Build Coastguard Workerwidth="10" height="10" style="padding: 20px" /><br/>(10x10)</td> 58*324bb76bSAndroid Build Coastguard Worker<td style="text-align:center; vertical-align: top; padding: 5px;; width:40%"> 59*324bb76bSAndroid Build Coastguard Worker<h3>Enlarged</h3> 60*324bb76bSAndroid Build Coastguard Worker<img src="sample_1_enlarged.gif" alt="sample gif, enlarged" 61*324bb76bSAndroid Build Coastguard Workertitle="Enlarged" width="100" height="100" /><br/>(100x100)</td> 62*324bb76bSAndroid Build Coastguard Worker<td style="vertical-align: top; padding: 5px; width:30%"> 63*324bb76bSAndroid Build Coastguard Worker<h3>Color Table</h3> 64*324bb76bSAndroid Build Coastguard Worker<table> 65*324bb76bSAndroid Build Coastguard Worker<tr><th>Index</th><th>Color</th></tr> 66*324bb76bSAndroid Build Coastguard Worker<tr><td>0</td><td><span style="color:#FFFFFF; background: #000000; font-weight: bold">White</span></td></tr> 67*324bb76bSAndroid Build Coastguard Worker<tr><td>1</td><td><span style="color:#FF0000; font-weight: bold">Red</span></td></tr> 68*324bb76bSAndroid Build Coastguard Worker<tr><td>2</td><td><span style="color:#0000FF; font-weight: bold">Blue</span></td></tr> 69*324bb76bSAndroid Build Coastguard Worker<tr><td>3</td><td><span style="font-weight: bold">Black</span></td></tr> 70*324bb76bSAndroid Build Coastguard Worker</table> 71*324bb76bSAndroid Build Coastguard Worker</td> 72*324bb76bSAndroid Build Coastguard Worker</tr></table> 73*324bb76bSAndroid Build Coastguard Worker 74*324bb76bSAndroid Build Coastguard Worker<p>The color table came from the global color table block. The colors 75*324bb76bSAndroid Build Coastguard Workerare listed in the order which they appear in the file. The first color 76*324bb76bSAndroid Build Coastguard Workeris given an index of zero. When we send the codes, we always start at 77*324bb76bSAndroid Build Coastguard Workerthe top left of the image and work our way right. When we get to the 78*324bb76bSAndroid Build Coastguard Workerend of the line, the very next code is the one that starts the next 79*324bb76bSAndroid Build Coastguard Workerline. (The decoder will "wrap" the image based on the image 80*324bb76bSAndroid Build Coastguard Workerdimensions.) We could encode our sample image in the following 81*324bb76bSAndroid Build Coastguard Workerway:</p> 82*324bb76bSAndroid Build Coastguard Worker 83*324bb76bSAndroid Build Coastguard Worker<blockquote><p>1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 84*324bb76bSAndroid Build Coastguard Worker1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 2, 2, 2, 1, 1, 1, 85*324bb76bSAndroid Build Coastguard Worker0, 0, 0, 0, 2, 2, 2, ...</p></blockquote> 86*324bb76bSAndroid Build Coastguard Worker 87*324bb76bSAndroid Build Coastguard Worker<p>The above listing shows the sequence required to render the first five 88*324bb76bSAndroid Build Coastguard Workerlines of the image. We could continue with this method until we've 89*324bb76bSAndroid Build Coastguard Workerspecified the color for every pixel; however, this can result in a 90*324bb76bSAndroid Build Coastguard Workerrather large file. Luckily for us, the GIF format allows us to take 91*324bb76bSAndroid Build Coastguard Workeradvantage of repetition in our output and to compress our data.</p> 92*324bb76bSAndroid Build Coastguard Worker 93*324bb76bSAndroid Build Coastguard Worker<p>Much of the following information came from John Barkaus's tutorial 94*324bb76bSAndroid Build Coastguard Worker<cite>LZW and GIF Explained</cite>, which seems to have fallen off the 95*324bb76bSAndroid Build Coastguard Workerweb. I've tried to provide more detailed samples as well 96*324bb76bSAndroid Build Coastguard Workeras illustrations to make the process even clearer</p> 97*324bb76bSAndroid Build Coastguard Worker 98*324bb76bSAndroid Build Coastguard Worker<h2><a name="lzw_compression">LZW Compression</a></h2> 99*324bb76bSAndroid Build Coastguard Worker 100*324bb76bSAndroid Build Coastguard Worker<p>The compression method GIF use is a variant of LZW 101*324bb76bSAndroid Build Coastguard Worker(Lempel-Ziv-Welch) compression. To start using this method, we need a 102*324bb76bSAndroid Build Coastguard Worker<strong>code table</strong>. This code table will allow us to use 103*324bb76bSAndroid Build Coastguard Workerspecial codes to indicate a sequence of colors rather than just one at 104*324bb76bSAndroid Build Coastguard Workera time. The first thing we do is to <em>initialize the code 105*324bb76bSAndroid Build Coastguard Workertable</em>. We start by adding a code for each of the colors in the 106*324bb76bSAndroid Build Coastguard Workercolor table. This would be a local color table if one was provided, or 107*324bb76bSAndroid Build Coastguard Workerthe global color table. (I will be starting all codes with 108*324bb76bSAndroid Build Coastguard Worker"#" to distinguish them from color indexes.)</p> 109*324bb76bSAndroid Build Coastguard Worker 110*324bb76bSAndroid Build Coastguard Worker<table class="code_table"> 111*324bb76bSAndroid Build Coastguard Worker<tr><th>Code</th><th>Color(s)</th></tr> 112*324bb76bSAndroid Build Coastguard Worker<tr><td>#0</td><td>0</td></tr> 113*324bb76bSAndroid Build Coastguard Worker<tr><td>#1</td><td>1</td></tr> 114*324bb76bSAndroid Build Coastguard Worker<tr><td>#2</td><td>2</td></tr> 115*324bb76bSAndroid Build Coastguard Worker<tr><td>#3</td><td>3</td></tr> 116*324bb76bSAndroid Build Coastguard Worker<tr><td>#4</td><td>Clear Code</td></tr> 117*324bb76bSAndroid Build Coastguard Worker<tr><td>#5</td><td>End Of Information Code</td></tr> 118*324bb76bSAndroid Build Coastguard Worker</table> 119*324bb76bSAndroid Build Coastguard Worker 120*324bb76bSAndroid Build Coastguard Worker<p>I added a code for each of the colors in the global color table of 121*324bb76bSAndroid Build Coastguard Workerour sample image. I also snuck in two special control codes. (These 122*324bb76bSAndroid Build Coastguard Workerspecial codes are only used in the GIF version of LZW, not in standard 123*324bb76bSAndroid Build Coastguard WorkerLZW compression.) Our code table is now considered initialized.</p> 124*324bb76bSAndroid Build Coastguard Worker 125*324bb76bSAndroid Build Coastguard Worker<p>Let me now explain what those special codes are for. The first new code 126*324bb76bSAndroid Build Coastguard Workeris the <em>clear code</em> (CC). Whenever you come across the clear code 127*324bb76bSAndroid Build Coastguard Workerin the image data, it's your cue to reinitialize the code table. (I'll 128*324bb76bSAndroid Build Coastguard Workerexplain why you might need to do this in a bit.) The second new code 129*324bb76bSAndroid Build Coastguard Workeris the <em>end of information code</em> (EOI). When you come across 130*324bb76bSAndroid Build Coastguard Workerthis code, this means you've reached the end of the image. Here I've placed 131*324bb76bSAndroid Build Coastguard Workerthe special codes right after the color codes, but actually the value of 132*324bb76bSAndroid Build Coastguard Workerthe special codes depends on the value of the LZW minimum code size 133*324bb76bSAndroid Build Coastguard Workerfrom the image data block. If the LZW minimum code size is the same as 134*324bb76bSAndroid Build Coastguard Workerthe color table size, then special codes immediatly follow the colors; however 135*324bb76bSAndroid Build Coastguard Workerit is possible to specify a larger LZW minimum code size which may leave 136*324bb76bSAndroid Build Coastguard Workera gap in the codes where no colors are assigned. This can be 137*324bb76bSAndroid Build Coastguard Workersummarizaed in the <a name="color_table_size">following table</a>.</p> 138*324bb76bSAndroid Build Coastguard Worker 139*324bb76bSAndroid Build Coastguard Worker<div style="text-align:center"> 140*324bb76bSAndroid Build Coastguard Worker<table id="global_color_size"> 141*324bb76bSAndroid Build Coastguard Worker<tr><th>LZW Min Code<br/>Size</th><th>Color<br/>Codes</th><th>Clear<br/>Code</th><th>EOI<br/>Code</th></tr> 142*324bb76bSAndroid Build Coastguard Worker<tr><td>2</td><td>#0-#3</td><td>#4</td><td>#5</td></tr> 143*324bb76bSAndroid Build Coastguard Worker<tr><td>3</td><td>#0-#7</td><td>#8</td><td>#9</td></tr> 144*324bb76bSAndroid Build Coastguard Worker<tr><td>4</td><td>#0-#15</td><td>#16</td><td>#17</td></tr> 145*324bb76bSAndroid Build Coastguard Worker<tr><td>5</td><td>#0-#31</td><td>#32</td><td>#33</td></tr> 146*324bb76bSAndroid Build Coastguard Worker<tr><td>6</td><td>#0-#63</td><td>#64</td><td>#65</td></tr> 147*324bb76bSAndroid Build Coastguard Worker<tr><td>7</td><td>#0-#127</td><td>#128</td><td>#129</td></tr> 148*324bb76bSAndroid Build Coastguard Worker<tr><td>8</td><td>#0-#255</td><td>#256</td><td>#257</td></tr> 149*324bb76bSAndroid Build Coastguard Worker</table> 150*324bb76bSAndroid Build Coastguard Worker</div> 151*324bb76bSAndroid Build Coastguard Worker 152*324bb76bSAndroid Build Coastguard Worker<p>Before we proceed, let me define two more terms. First the <strong>index 153*324bb76bSAndroid Build Coastguard Workerstream</strong> will be the list of indexes of the color for each of 154*324bb76bSAndroid Build Coastguard Workerthe pixels. This is the input we will be compressing. The <strong>code 155*324bb76bSAndroid Build Coastguard Workerstream</strong> will be the list of codes we generate as output. The 156*324bb76bSAndroid Build Coastguard Worker<strong>index buffer</strong> will be the list of color indexes 157*324bb76bSAndroid Build Coastguard Workerwe care "currently looking at." The index buffer will contain a list 158*324bb76bSAndroid Build Coastguard Workerof one or more color indexes. Now we can step though the LZW 159*324bb76bSAndroid Build Coastguard Workercompression algorithm. First, I'll just list the steps. After that 160*324bb76bSAndroid Build Coastguard WorkerI'll walk through the steps with our specific example.</p> 161*324bb76bSAndroid Build Coastguard Worker 162*324bb76bSAndroid Build Coastguard Worker<ul> 163*324bb76bSAndroid Build Coastguard Worker<li>Initialize code table</li> 164*324bb76bSAndroid Build Coastguard Worker<li>Always start by sending a clear code to the code stream.</li> 165*324bb76bSAndroid Build Coastguard Worker<li>Read first index from index stream. This value is now the value 166*324bb76bSAndroid Build Coastguard Workerfor the index buffer</li> 167*324bb76bSAndroid Build Coastguard Worker<li><LOOP POINT></li> 168*324bb76bSAndroid Build Coastguard Worker<li>Get the next index from the index stream to the index buffer. We will 169*324bb76bSAndroid Build Coastguard Workercall this index, K</li> 170*324bb76bSAndroid Build Coastguard Worker<li>Is index buffer + K in our code table?</li> 171*324bb76bSAndroid Build Coastguard Worker<li>Yes: 172*324bb76bSAndroid Build Coastguard Worker <ul> 173*324bb76bSAndroid Build Coastguard Worker <li>add K to the end of the index buffer</li> 174*324bb76bSAndroid Build Coastguard Worker <li>if there are more indexes, return to LOOP POINT</li> 175*324bb76bSAndroid Build Coastguard Worker </ul> 176*324bb76bSAndroid Build Coastguard Worker</li> 177*324bb76bSAndroid Build Coastguard Worker<li>No: 178*324bb76bSAndroid Build Coastguard Worker <ul> 179*324bb76bSAndroid Build Coastguard Worker <li>Add a row for index buffer + K into our code table with 180*324bb76bSAndroid Build Coastguard Worker the next smallest code</li> 181*324bb76bSAndroid Build Coastguard Worker <li>Output the code for just the index buffer to our code steam</li> 182*324bb76bSAndroid Build Coastguard Worker <li>Index buffer is set to K</li> 183*324bb76bSAndroid Build Coastguard Worker <li>K is set to nothing</li> 184*324bb76bSAndroid Build Coastguard Worker <li>if there are more indexes, return to LOOP POINT</li> 185*324bb76bSAndroid Build Coastguard Worker </ul> 186*324bb76bSAndroid Build Coastguard Worker</li> 187*324bb76bSAndroid Build Coastguard Worker<li>Output code for contents of index buffer</li> 188*324bb76bSAndroid Build Coastguard Worker<li>Output end-of-information code</li> 189*324bb76bSAndroid Build Coastguard Worker</ul> 190*324bb76bSAndroid Build Coastguard Worker 191*324bb76bSAndroid Build Coastguard Worker<p>Seems simple enough, right? It really isn't all that bad. Let's 192*324bb76bSAndroid Build Coastguard Workerwalk though our sample image to show you how this works. (The steps I 193*324bb76bSAndroid Build Coastguard Workerwill be describing are summarized in the following table. Numbers 194*324bb76bSAndroid Build Coastguard Workerhighlighted in green are in the index buffer; numbers in purple are 195*324bb76bSAndroid Build Coastguard Workerthe current K value.) We have already initialized our code table. We 196*324bb76bSAndroid Build Coastguard Workerstart by doing two things: we output our clear code (#4) to the code 197*324bb76bSAndroid Build Coastguard Workerstream, and we read the first color index from the index stream, 1, 198*324bb76bSAndroid Build Coastguard Workerinto our index buffer [Step 0].</p> 199*324bb76bSAndroid Build Coastguard Worker 200*324bb76bSAndroid Build Coastguard Worker<p>Now we enter the main loop of the algorithm. We read the next index 201*324bb76bSAndroid Build Coastguard Workerin the index stream, 1, into K [Step 1]. Next we see if we have a 202*324bb76bSAndroid Build Coastguard Workerrecord for the index buffer plus K in the code stream. In this case we 203*324bb76bSAndroid Build Coastguard Workerlooking for 1,1. Currently our code table only contains single colors 204*324bb76bSAndroid Build Coastguard Workerso this value is not in there. Now we will actually add a new row to 205*324bb76bSAndroid Build Coastguard Workerour code table that does contain this value. The next available code 206*324bb76bSAndroid Build Coastguard Workeris #6, we will let #6 be 1,1. Note that we do not actually send this 207*324bb76bSAndroid Build Coastguard Workercode to the code stream, instead we send just the code for the 208*324bb76bSAndroid Build Coastguard Workervalue(s) in the index buffer. The index buffer is just 1 and the code 209*324bb76bSAndroid Build Coastguard Workerfor 1 is #1. This is the code we output. We now reset the index buffer 210*324bb76bSAndroid Build Coastguard Workerto just the value in K and K becomes nothing. [Step 2].</p> 211*324bb76bSAndroid Build Coastguard Worker 212*324bb76bSAndroid Build Coastguard Worker<p>We continue by reading the next index into K. [Step 3]. Now K is 1 and the 213*324bb76bSAndroid Build Coastguard Workerindex buffer is 1. Again we look to see if there is a value in our code 214*324bb76bSAndroid Build Coastguard Workertable for the buffer plus K (1,1) and this time there is. (In fact we just 215*324bb76bSAndroid Build Coastguard Workeradded it.) Therefore we add K to the end of the index buffer and clear out 216*324bb76bSAndroid Build Coastguard WorkerK. Now our index buffer is 1,1. [Step 4].</p> 217*324bb76bSAndroid Build Coastguard Worker 218*324bb76bSAndroid Build Coastguard Worker<p>The next index in the index stream is yet another 1. This is our 219*324bb76bSAndroid Build Coastguard Workernew K [Step 5]. Now the index buffer plus K is 1,1,1 which we do not 220*324bb76bSAndroid Build Coastguard Workerhave a code for in our code table. As we did before, we define a new 221*324bb76bSAndroid Build Coastguard Workercode and add it to the code table. The next code would be #7; thus #7 222*324bb76bSAndroid Build Coastguard Worker= 1, 1, 1. Now we kick out the code for just the values in the index 223*324bb76bSAndroid Build Coastguard Workerbuffer (#6 = 1,1) to the code stream and set the index buffer to be 224*324bb76bSAndroid Build Coastguard WorkerK. [Step 6].</p> 225*324bb76bSAndroid Build Coastguard Worker 226*324bb76bSAndroid Build Coastguard Worker<table class="alg_steps" cellspacing="0"> 227*324bb76bSAndroid Build Coastguard Worker<thead> 228*324bb76bSAndroid Build Coastguard Worker<tr> 229*324bb76bSAndroid Build Coastguard Worker <th>Step</th> 230*324bb76bSAndroid Build Coastguard Worker <th>Action</th> 231*324bb76bSAndroid Build Coastguard Worker <th>Index Stream</th> 232*324bb76bSAndroid Build Coastguard Worker <th>New Code Table Row</th> 233*324bb76bSAndroid Build Coastguard Worker <th>Code Stream</th> 234*324bb76bSAndroid Build Coastguard Worker</tr> 235*324bb76bSAndroid Build Coastguard Worker</thead> 236*324bb76bSAndroid Build Coastguard Worker<tbody> 237*324bb76bSAndroid Build Coastguard Worker<tr> 238*324bb76bSAndroid Build Coastguard Worker <td>0</td> 239*324bb76bSAndroid Build Coastguard Worker <td>Init</td> 240*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"></span> 241*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span> 242*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 243*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 244*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 245*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 246*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 247*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 248*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 249*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 250*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 251*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 252*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 253*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 254*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 255*324bb76bSAndroid Build Coastguard Worker <td> </td> 256*324bb76bSAndroid Build Coastguard Worker <td>#4</td> 257*324bb76bSAndroid Build Coastguard Worker</tr> 258*324bb76bSAndroid Build Coastguard Worker 259*324bb76bSAndroid Build Coastguard Worker<tr> 260*324bb76bSAndroid Build Coastguard Worker <td>1</td> 261*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 262*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"></span> 263*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span> 264*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">1</span></span> 265*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 266*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 267*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 268*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 269*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 270*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 271*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 272*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 273*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 274*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 275*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 276*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 277*324bb76bSAndroid Build Coastguard Worker <td> </td> 278*324bb76bSAndroid Build Coastguard Worker <td>#4</td> 279*324bb76bSAndroid Build Coastguard Worker</tr> 280*324bb76bSAndroid Build Coastguard Worker 281*324bb76bSAndroid Build Coastguard Worker<tr> 282*324bb76bSAndroid Build Coastguard Worker <td>2</td> 283*324bb76bSAndroid Build Coastguard Worker <td>Not Found</td> 284*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span></span> 285*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span> 286*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 287*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 288*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 289*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 290*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 291*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 292*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 293*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 294*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 295*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 296*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 297*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 298*324bb76bSAndroid Build Coastguard Worker <td>#6 - 1, 1</td> 299*324bb76bSAndroid Build Coastguard Worker <td>#4 #1</td> 300*324bb76bSAndroid Build Coastguard Worker</tr> 301*324bb76bSAndroid Build Coastguard Worker 302*324bb76bSAndroid Build Coastguard Worker<tr> 303*324bb76bSAndroid Build Coastguard Worker <td>3</td> 304*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 305*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span></span> 306*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span> 307*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">1</span></span> 308*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 309*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 310*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 311*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 312*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 313*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 314*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 315*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 316*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 317*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 318*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 319*324bb76bSAndroid Build Coastguard Worker <td> </td> 320*324bb76bSAndroid Build Coastguard Worker <td>#4 #1</td> 321*324bb76bSAndroid Build Coastguard Worker</tr> 322*324bb76bSAndroid Build Coastguard Worker 323*324bb76bSAndroid Build Coastguard Worker<tr> 324*324bb76bSAndroid Build Coastguard Worker <td>4</td> 325*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 326*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span></span> 327*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span> 328*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 329*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 330*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 331*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 332*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 333*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 334*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 335*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 336*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 337*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 338*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 339*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 340*324bb76bSAndroid Build Coastguard Worker <td> </td> 341*324bb76bSAndroid Build Coastguard Worker <td>#4 #1</td> 342*324bb76bSAndroid Build Coastguard Worker</tr> 343*324bb76bSAndroid Build Coastguard Worker 344*324bb76bSAndroid Build Coastguard Worker<tr> 345*324bb76bSAndroid Build Coastguard Worker <td>5</td> 346*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 347*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span></span> 348*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span> 349*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 350*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">1</span></span> 351*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 352*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 353*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 354*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 355*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 356*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 357*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 358*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 359*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 360*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 361*324bb76bSAndroid Build Coastguard Worker <td> </td> 362*324bb76bSAndroid Build Coastguard Worker <td>#4 #1</td> 363*324bb76bSAndroid Build Coastguard Worker</tr> 364*324bb76bSAndroid Build Coastguard Worker 365*324bb76bSAndroid Build Coastguard Worker<tr> 366*324bb76bSAndroid Build Coastguard Worker <td>6</td> 367*324bb76bSAndroid Build Coastguard Worker <td>Not Found</td> 368*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 369*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 370*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 371*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span> 372*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 373*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 374*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 375*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 376*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 377*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 378*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 379*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 380*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 381*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 382*324bb76bSAndroid Build Coastguard Worker <td>#7 - 1, 1, 1</td> 383*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6</td> 384*324bb76bSAndroid Build Coastguard Worker</tr> 385*324bb76bSAndroid Build Coastguard Worker</tbody> 386*324bb76bSAndroid Build Coastguard Worker<tbody id="compress_more"> 387*324bb76bSAndroid Build Coastguard Worker 388*324bb76bSAndroid Build Coastguard Worker<tr> 389*324bb76bSAndroid Build Coastguard Worker <td>7</td> 390*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 391*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 392*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 393*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 394*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span> 395*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">1</span></span> 396*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 397*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 398*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 399*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 400*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 401*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 402*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 403*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 404*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 405*324bb76bSAndroid Build Coastguard Worker <td> </td> 406*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6</td> 407*324bb76bSAndroid Build Coastguard Worker</tr> 408*324bb76bSAndroid Build Coastguard Worker 409*324bb76bSAndroid Build Coastguard Worker<tr> 410*324bb76bSAndroid Build Coastguard Worker <td>8</td> 411*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 412*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 413*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 414*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 415*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span> 416*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 417*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 418*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 419*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 420*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 421*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 422*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 423*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 424*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 425*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 426*324bb76bSAndroid Build Coastguard Worker <td> </td> 427*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6</td> 428*324bb76bSAndroid Build Coastguard Worker</tr> 429*324bb76bSAndroid Build Coastguard Worker 430*324bb76bSAndroid Build Coastguard Worker<tr> 431*324bb76bSAndroid Build Coastguard Worker <td>9</td> 432*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 433*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 434*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 435*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 436*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span> 437*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 438*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">2</span></span> 439*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 440*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 441*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 442*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 443*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 444*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 445*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 446*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 447*324bb76bSAndroid Build Coastguard Worker <td> </td> 448*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6</td> 449*324bb76bSAndroid Build Coastguard Worker</tr> 450*324bb76bSAndroid Build Coastguard Worker 451*324bb76bSAndroid Build Coastguard Worker<tr> 452*324bb76bSAndroid Build Coastguard Worker <td>10</td> 453*324bb76bSAndroid Build Coastguard Worker <td>Not Found</td> 454*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 455*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 456*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 457*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 458*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 459*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span></span> 460*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 461*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 462*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 463*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 464*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 465*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 466*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 467*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 468*324bb76bSAndroid Build Coastguard Worker <td>#8 - 1, 1, 2</td> 469*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6</td> 470*324bb76bSAndroid Build Coastguard Worker</tr> 471*324bb76bSAndroid Build Coastguard Worker 472*324bb76bSAndroid Build Coastguard Worker<tr> 473*324bb76bSAndroid Build Coastguard Worker <td>11</td> 474*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 475*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 476*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 477*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 478*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 479*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 480*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span></span> 481*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">2</span></span> 482*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 483*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 484*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 485*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 486*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 487*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 488*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 489*324bb76bSAndroid Build Coastguard Worker <td> </td> 490*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6</td> 491*324bb76bSAndroid Build Coastguard Worker</tr> 492*324bb76bSAndroid Build Coastguard Worker 493*324bb76bSAndroid Build Coastguard Worker<tr> 494*324bb76bSAndroid Build Coastguard Worker <td>12</td> 495*324bb76bSAndroid Build Coastguard Worker <td>Not Found </td> 496*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 497*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 498*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 499*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 500*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 501*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 502*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span></span> 503*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 504*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 505*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 506*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 507*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 508*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 509*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 510*324bb76bSAndroid Build Coastguard Worker <td>#9 - 2, 2</td> 511*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2</td> 512*324bb76bSAndroid Build Coastguard Worker</tr> 513*324bb76bSAndroid Build Coastguard Worker 514*324bb76bSAndroid Build Coastguard Worker<tr> 515*324bb76bSAndroid Build Coastguard Worker <td>13</td> 516*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 517*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 518*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 519*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 520*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 521*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 522*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 523*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span></span> 524*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">2</span></span> 525*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 526*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 527*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 528*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 529*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 530*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 531*324bb76bSAndroid Build Coastguard Worker <td> </td> 532*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2</td> 533*324bb76bSAndroid Build Coastguard Worker</tr> 534*324bb76bSAndroid Build Coastguard Worker 535*324bb76bSAndroid Build Coastguard Worker<tr> 536*324bb76bSAndroid Build Coastguard Worker <td>14</td> 537*324bb76bSAndroid Build Coastguard Worker <td>Found </td> 538*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 539*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 540*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 541*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 542*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 543*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 544*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span> 545*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 546*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 547*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 548*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 549*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 550*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 551*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 552*324bb76bSAndroid Build Coastguard Worker <td> </td> 553*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2</td> 554*324bb76bSAndroid Build Coastguard Worker</tr> 555*324bb76bSAndroid Build Coastguard Worker 556*324bb76bSAndroid Build Coastguard Worker<tr> 557*324bb76bSAndroid Build Coastguard Worker <td>15</td> 558*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 559*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 560*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 561*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 562*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 563*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 564*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 565*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span> 566*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 567*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">2</span></span> 568*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 569*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 570*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 571*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 572*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 573*324bb76bSAndroid Build Coastguard Worker <td> </td> 574*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2</td> 575*324bb76bSAndroid Build Coastguard Worker</tr> 576*324bb76bSAndroid Build Coastguard Worker 577*324bb76bSAndroid Build Coastguard Worker<tr> 578*324bb76bSAndroid Build Coastguard Worker <td>16</td> 579*324bb76bSAndroid Build Coastguard Worker <td>Not Found</td> 580*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 581*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 582*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 583*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 584*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 585*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 586*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 587*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 588*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span></span> 589*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 590*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 591*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 592*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 593*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 594*324bb76bSAndroid Build Coastguard Worker <td>#10 - 2, 2, 2</td> 595*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9</td> 596*324bb76bSAndroid Build Coastguard Worker</tr> 597*324bb76bSAndroid Build Coastguard Worker 598*324bb76bSAndroid Build Coastguard Worker<tr> 599*324bb76bSAndroid Build Coastguard Worker <td>17</td> 600*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 601*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 602*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 603*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 604*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 605*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 606*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 607*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 608*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 609*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span></span> 610*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">2</span></span> 611*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 612*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 613*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 614*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 615*324bb76bSAndroid Build Coastguard Worker <td> </td> 616*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9</td> 617*324bb76bSAndroid Build Coastguard Worker</tr> 618*324bb76bSAndroid Build Coastguard Worker 619*324bb76bSAndroid Build Coastguard Worker<tr> 620*324bb76bSAndroid Build Coastguard Worker <td>18</td> 621*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 622*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 623*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 624*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 625*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 626*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 627*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 628*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 629*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 630*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span> 631*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 632*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 633*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 634*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 635*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 636*324bb76bSAndroid Build Coastguard Worker <td> </td> 637*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9</td> 638*324bb76bSAndroid Build Coastguard Worker</tr> 639*324bb76bSAndroid Build Coastguard Worker 640*324bb76bSAndroid Build Coastguard Worker<tr> 641*324bb76bSAndroid Build Coastguard Worker <td>19</td> 642*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 643*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 644*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 645*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 646*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 647*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 648*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 649*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 650*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 651*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">2</span> 652*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 653*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">1</span></span> 654*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 655*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 656*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 657*324bb76bSAndroid Build Coastguard Worker <td> </td> 658*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9</td> 659*324bb76bSAndroid Build Coastguard Worker</tr> 660*324bb76bSAndroid Build Coastguard Worker 661*324bb76bSAndroid Build Coastguard Worker<tr> 662*324bb76bSAndroid Build Coastguard Worker <td>20</td> 663*324bb76bSAndroid Build Coastguard Worker <td>Not Found</td> 664*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 665*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 666*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 667*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 668*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 669*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 670*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 671*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 672*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 673*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 674*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span> 675*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 676*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 677*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 678*324bb76bSAndroid Build Coastguard Worker <td>#11 - 2, 2, 1</td> 679*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9 #9</td> 680*324bb76bSAndroid Build Coastguard Worker</tr> 681*324bb76bSAndroid Build Coastguard Worker 682*324bb76bSAndroid Build Coastguard Worker<tr> 683*324bb76bSAndroid Build Coastguard Worker <td>21</td> 684*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 685*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 686*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 687*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 688*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 689*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 690*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 691*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 692*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 693*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 694*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 695*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span> 696*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">1</span></span> 697*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 698*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 699*324bb76bSAndroid Build Coastguard Worker <td> </td> 700*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9 #9</td> 701*324bb76bSAndroid Build Coastguard Worker</tr> 702*324bb76bSAndroid Build Coastguard Worker 703*324bb76bSAndroid Build Coastguard Worker<tr> 704*324bb76bSAndroid Build Coastguard Worker <td>22</td> 705*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 706*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 707*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 708*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 709*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 710*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 711*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 712*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 713*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 714*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 715*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 716*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span> 717*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 718*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 719*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 720*324bb76bSAndroid Build Coastguard Worker <td> </td> 721*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9 #9</td> 722*324bb76bSAndroid Build Coastguard Worker</tr> 723*324bb76bSAndroid Build Coastguard Worker 724*324bb76bSAndroid Build Coastguard Worker<tr> 725*324bb76bSAndroid Build Coastguard Worker <td>23</td> 726*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 727*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 728*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 729*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 730*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 731*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 732*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 733*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 734*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 735*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 736*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 737*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span> 738*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 739*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">1</span></span> 740*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 741*324bb76bSAndroid Build Coastguard Worker <td> </td> 742*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9 #9</td> 743*324bb76bSAndroid Build Coastguard Worker</tr> 744*324bb76bSAndroid Build Coastguard Worker 745*324bb76bSAndroid Build Coastguard Worker<tr> 746*324bb76bSAndroid Build Coastguard Worker <td>24</td> 747*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 748*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 749*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 750*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 751*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 752*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 753*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 754*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 755*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 756*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 757*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 758*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span> 759*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 760*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 761*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span>...</td> 762*324bb76bSAndroid Build Coastguard Worker <td> </td> 763*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9 #9</td> 764*324bb76bSAndroid Build Coastguard Worker</tr> 765*324bb76bSAndroid Build Coastguard Worker 766*324bb76bSAndroid Build Coastguard Worker<tr> 767*324bb76bSAndroid Build Coastguard Worker <td>25</td> 768*324bb76bSAndroid Build Coastguard Worker <td>Read</td> 769*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 770*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 771*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 772*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 773*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 774*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 775*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 776*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 777*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 778*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span></span> 779*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span> 780*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 781*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 782*324bb76bSAndroid Build Coastguard Worker <span class="current"><span class="index">1</span></span>...</td> 783*324bb76bSAndroid Build Coastguard Worker <td> </td> 784*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9 #9</td> 785*324bb76bSAndroid Build Coastguard Worker</tr> 786*324bb76bSAndroid Build Coastguard Worker 787*324bb76bSAndroid Build Coastguard Worker<tr> 788*324bb76bSAndroid Build Coastguard Worker <td>26</td> 789*324bb76bSAndroid Build Coastguard Worker <td>Not Found</td> 790*324bb76bSAndroid Build Coastguard Worker <td><span class="processed"><span class="index">1</span> 791*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 792*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 793*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 794*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 795*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 796*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 797*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 798*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 799*324bb76bSAndroid Build Coastguard Worker <span class="index">2</span> 800*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 801*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span> 802*324bb76bSAndroid Build Coastguard Worker <span class="index">1</span></span> 803*324bb76bSAndroid Build Coastguard Worker <span class="buffer"><span class="index">1</span></span>...</td> 804*324bb76bSAndroid Build Coastguard Worker <td>#12 - 1, 1, 1, 1</td> 805*324bb76bSAndroid Build Coastguard Worker <td>#4 #1 #6 #6 #2 #9 #9 #7</td> 806*324bb76bSAndroid Build Coastguard Worker</tr> 807*324bb76bSAndroid Build Coastguard Worker</tbody> 808*324bb76bSAndroid Build Coastguard Worker</table> 809*324bb76bSAndroid Build Coastguard Worker 810*324bb76bSAndroid Build Coastguard Worker<p>I've included a few more steps to help you see the pattern. You 811*324bb76bSAndroid Build Coastguard Workerkeep going until you run out of indexes in the index stream. When 812*324bb76bSAndroid Build Coastguard Workerthere is nothing new to read, you simply write out the code for 813*324bb76bSAndroid Build Coastguard Workerwhatever values you may have in your index buffer. Finally you should 814*324bb76bSAndroid Build Coastguard Workersend the end-of-information code to the code stream. In this example, 815*324bb76bSAndroid Build Coastguard Workerthat code is #5. (View the <a href="lzw_image_data_code_table.html"> 816*324bb76bSAndroid Build Coastguard Workercomplete code table</a>.)</p> 817*324bb76bSAndroid Build Coastguard Worker 818*324bb76bSAndroid Build Coastguard Worker<p>As you can see we dynamically built many new codes for our code 819*324bb76bSAndroid Build Coastguard Workertable as we compressed the data. For large files this can turn into a 820*324bb76bSAndroid Build Coastguard Workerlarge number of codes. It turns out that the GIF format specifies a 821*324bb76bSAndroid Build Coastguard Workermaximum code of #4095 (this happens to be the largest 12-bit 822*324bb76bSAndroid Build Coastguard Workernumber). If you want to use a new code, you have to clear out all of 823*324bb76bSAndroid Build Coastguard Workeryour old codes. You do this by sending the clear code (which for our 824*324bb76bSAndroid Build Coastguard Workersample was the #4). This tells the decoder that you are reinitializing 825*324bb76bSAndroid Build Coastguard Workeryour code table and it should too. Then you start building your own 826*324bb76bSAndroid Build Coastguard Workercodes again starting just after the value for your end-of-information 827*324bb76bSAndroid Build Coastguard Workercode (in our sample, we would start again at #6).</p> 828*324bb76bSAndroid Build Coastguard Worker 829*324bb76bSAndroid Build Coastguard Worker<p>The final code stream would look like this:</p> 830*324bb76bSAndroid Build Coastguard Worker 831*324bb76bSAndroid Build Coastguard Worker<blockquote><p>#4 #1 #6 #6 #2 #9 #9 #7 #8 #10 #2 #12 #1 #14 #15 #6 #0 #21 #0 #10 #7 #22 #23 832*324bb76bSAndroid Build Coastguard Worker#18 #26 #7 #10 #29 #13 #24 #12 #18 #16 #36 #12 #5</p></blockquote> 833*324bb76bSAndroid Build Coastguard Worker 834*324bb76bSAndroid Build Coastguard Worker<p>This is only 36 codes versus the 100 that would be required without compression.</p> 835*324bb76bSAndroid Build Coastguard Worker 836*324bb76bSAndroid Build Coastguard Worker<h2><a name="lzw_decompression">LZW Decompression</a></h2> 837*324bb76bSAndroid Build Coastguard Worker 838*324bb76bSAndroid Build Coastguard Worker<p> At some point we will need to turn this code stream back into 839*324bb76bSAndroid Build Coastguard Workera picture. To do this, we only need to know the values in the stream 840*324bb76bSAndroid Build Coastguard Workerand the size of the color table that was used. That's it. You remember that 841*324bb76bSAndroid Build Coastguard Workerbig code table we built during compression? We actually have enough information 842*324bb76bSAndroid Build Coastguard Workerin the code stream itself to be able to rebuild it.</p> 843*324bb76bSAndroid Build Coastguard Worker 844*324bb76bSAndroid Build Coastguard Worker<p>Again, i'll list the algorithm and then we will walk though an example. Let 845*324bb76bSAndroid Build Coastguard Workerme define a few terms i will be using. CODE will be current code we're working 846*324bb76bSAndroid Build Coastguard Workerwith. CODE-1 will be the code just before CODE in the code stream. {CODE} 847*324bb76bSAndroid Build Coastguard Workerwill be the value for CODE in the code table. For example, using the code 848*324bb76bSAndroid Build Coastguard Workertable we created during compression, if CODE=#7 then {CODE}=1,1,1. 849*324bb76bSAndroid Build Coastguard WorkerIn the same way, {CODE-1} would be the value in the code table for the 850*324bb76bSAndroid Build Coastguard Workercode that came before CODE. Looking at step 26 from the compression, 851*324bb76bSAndroid Build Coastguard Workerif CODE=#7, then {CODE-1} would be {#9}, not {#6}, which was 2,2.</p> 852*324bb76bSAndroid Build Coastguard Worker 853*324bb76bSAndroid Build Coastguard Worker<ul> 854*324bb76bSAndroid Build Coastguard Worker<li>Initialize code table</li> 855*324bb76bSAndroid Build Coastguard Worker<li>let CODE be the first code in the code stream</li> 856*324bb76bSAndroid Build Coastguard Worker<li>output {CODE} to index stream</li> 857*324bb76bSAndroid Build Coastguard Worker<li><LOOP POINT></li> 858*324bb76bSAndroid Build Coastguard Worker<li>let CODE be the next code in the code stream</li> 859*324bb76bSAndroid Build Coastguard Worker<li>is CODE in the code table?</li> 860*324bb76bSAndroid Build Coastguard Worker<li>Yes: 861*324bb76bSAndroid Build Coastguard Worker <ul> 862*324bb76bSAndroid Build Coastguard Worker <li>output {CODE} to index stream</li> 863*324bb76bSAndroid Build Coastguard Worker <li>let K be the first index in {CODE}</li> 864*324bb76bSAndroid Build Coastguard Worker <li>add {CODE-1}+K to the code table</li> 865*324bb76bSAndroid Build Coastguard Worker </ul> 866*324bb76bSAndroid Build Coastguard Worker</li> 867*324bb76bSAndroid Build Coastguard Worker<li>No: 868*324bb76bSAndroid Build Coastguard Worker <ul> 869*324bb76bSAndroid Build Coastguard Worker <li>let K be the first index of {CODE-1}</li> 870*324bb76bSAndroid Build Coastguard Worker <li>output {CODE-1}+K to index stream</li> 871*324bb76bSAndroid Build Coastguard Worker <li>add {CODE-1}+K to code table</li> 872*324bb76bSAndroid Build Coastguard Worker </ul> 873*324bb76bSAndroid Build Coastguard Worker</li> 874*324bb76bSAndroid Build Coastguard Worker<li>return to LOOP POINT</li> 875*324bb76bSAndroid Build Coastguard Worker</ul> 876*324bb76bSAndroid Build Coastguard Worker 877*324bb76bSAndroid Build Coastguard Worker<p>Let's start reading though the code stream we've created to show how to 878*324bb76bSAndroid Build Coastguard Workerturn it back into a list of color indexes. The first value in the code 879*324bb76bSAndroid Build Coastguard Workerstream should be a clear code. This means we should initialize our code 880*324bb76bSAndroid Build Coastguard Workertable. To do this we must know how many colors are in our color table. 881*324bb76bSAndroid Build Coastguard Worker(This information comes from the first byte in the image data block in 882*324bb76bSAndroid Build Coastguard Workerthe file. More on this later.) Again we will set up codes #0-#3 to be each 883*324bb76bSAndroid Build Coastguard Workerof the four colors and add in the clear code (#4) 884*324bb76bSAndroid Build Coastguard Workerand end of information code (#5).</p> 885*324bb76bSAndroid Build Coastguard Worker 886*324bb76bSAndroid Build Coastguard Worker<p>The next step is to read the first color code. In the following table you 887*324bb76bSAndroid Build Coastguard Workerwill see the values of CODE highlighted in purple, and the values for 888*324bb76bSAndroid Build Coastguard WorkerCODE-1 highlighted in green. Our first CODE value is #1. We then output 889*324bb76bSAndroid Build Coastguard Worker{#1}, or simply 1, to the index stream [Step 0].</p> 890*324bb76bSAndroid Build Coastguard Worker 891*324bb76bSAndroid Build Coastguard Worker<p>Now we enter the main loop of the algorithm. The next code gets assigned 892*324bb76bSAndroid Build Coastguard Workerto CODE which now makes that value #6. Next we check to see if this value 893*324bb76bSAndroid Build Coastguard Workeris in our code table. At this time, it is not. This means we must find the 894*324bb76bSAndroid Build Coastguard Workerfirst index in the value of {CODE-1} and call this K. Thus K = first index of 895*324bb76bSAndroid Build Coastguard Worker{CODE-1} = first index of {#1} = 1. Now we output {CODE-1} + K to the index 896*324bb76bSAndroid Build Coastguard Workerstream and add this value to our code table. The means we output 1,1 and 897*324bb76bSAndroid Build Coastguard Workergive this value a code of #6 [Step 1].</p> 898*324bb76bSAndroid Build Coastguard Worker 899*324bb76bSAndroid Build Coastguard Worker<table class="alg_steps" cellspacing="0"> 900*324bb76bSAndroid Build Coastguard Worker<tr> 901*324bb76bSAndroid Build Coastguard Worker <th>Step</th> 902*324bb76bSAndroid Build Coastguard Worker <th>Action</th> 903*324bb76bSAndroid Build Coastguard Worker <th>Code Stream</th> 904*324bb76bSAndroid Build Coastguard Worker <th>New Code Table Row</th> 905*324bb76bSAndroid Build Coastguard Worker <th>Index Stream</th> 906*324bb76bSAndroid Build Coastguard Worker</tr> 907*324bb76bSAndroid Build Coastguard Worker<tr> 908*324bb76bSAndroid Build Coastguard Worker <td>0</td> 909*324bb76bSAndroid Build Coastguard Worker <td>Init</td> 910*324bb76bSAndroid Build Coastguard Worker <td><span class="processed">#4</span> <span class="current">#1</span> #6 #6 #2 #9 #9 #7 ...</td> 911*324bb76bSAndroid Build Coastguard Worker <td> </td> 912*324bb76bSAndroid Build Coastguard Worker <td>1</td> 913*324bb76bSAndroid Build Coastguard Worker</tr> 914*324bb76bSAndroid Build Coastguard Worker<tr> 915*324bb76bSAndroid Build Coastguard Worker <td>1</td> 916*324bb76bSAndroid Build Coastguard Worker <td>Not Found</td> 917*324bb76bSAndroid Build Coastguard Worker <td><span class="processed">#4</span> <span class="buffer">#1</span> <span class="current">#6</span> #6 #2 #9 #9 #7 ...</td> 918*324bb76bSAndroid Build Coastguard Worker <td>#6 - 1, 1</td> 919*324bb76bSAndroid Build Coastguard Worker <td>1, 1, 1</td> 920*324bb76bSAndroid Build Coastguard Worker</tr> 921*324bb76bSAndroid Build Coastguard Worker<tr> 922*324bb76bSAndroid Build Coastguard Worker <td>2</td> 923*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 924*324bb76bSAndroid Build Coastguard Worker <td><span class="processed">#4 #1</span> <span class="buffer">#6</span> <span class="current">#6</span> #2 #9 #9 #7 ...</td> 925*324bb76bSAndroid Build Coastguard Worker <td>#7 - 1, 1, 1</td> 926*324bb76bSAndroid Build Coastguard Worker <td>1, 1, 1, 1, 1</td> 927*324bb76bSAndroid Build Coastguard Worker</tr> 928*324bb76bSAndroid Build Coastguard Worker<tr> 929*324bb76bSAndroid Build Coastguard Worker <td>3</td> 930*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 931*324bb76bSAndroid Build Coastguard Worker <td><span class="processed">#4 #1 #6</span> <span class="buffer">#6</span> <span class="current">#2</span> #9 #9 #7 ...</td> 932*324bb76bSAndroid Build Coastguard Worker <td>#8 - 1, 1, 2</td> 933*324bb76bSAndroid Build Coastguard Worker <td>1, 1, 1, 1, 1, 2</td> 934*324bb76bSAndroid Build Coastguard Worker</tr> 935*324bb76bSAndroid Build Coastguard Worker<tr> 936*324bb76bSAndroid Build Coastguard Worker <td>4</td> 937*324bb76bSAndroid Build Coastguard Worker <td>Not Found</td> 938*324bb76bSAndroid Build Coastguard Worker <td><span class="processed">#4 #1 #6 #6</span> <span class="buffer">#2</span> <span class="current">#9</span> #9 #7 ...</td> 939*324bb76bSAndroid Build Coastguard Worker <td>#9 - 2, 2</td> 940*324bb76bSAndroid Build Coastguard Worker <td>1, 1, 1, 1, 1, 2, 2, 2</td> 941*324bb76bSAndroid Build Coastguard Worker</tr> 942*324bb76bSAndroid Build Coastguard Worker<tr> 943*324bb76bSAndroid Build Coastguard Worker <td>5</td> 944*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 945*324bb76bSAndroid Build Coastguard Worker <td><span class="processed">#4 #1 #6 #6 #2</span> <span class="buffer">#9</span> <span class="current">#9</span> #7 ...</td> 946*324bb76bSAndroid Build Coastguard Worker <td>#10 - 2, 2, 2</td> 947*324bb76bSAndroid Build Coastguard Worker <td>1, 1, 1, 1, 1, 2, 2, 2, 2, 2</td> 948*324bb76bSAndroid Build Coastguard Worker</tr> 949*324bb76bSAndroid Build Coastguard Worker<tr> 950*324bb76bSAndroid Build Coastguard Worker <td>6</td> 951*324bb76bSAndroid Build Coastguard Worker <td>Found</td> 952*324bb76bSAndroid Build Coastguard Worker <td><span class="processed">#4 #1 #6 #6 #2 #9</span> <span class="buffer">#9</span> <span class="current">#7</span> ...</td> 953*324bb76bSAndroid Build Coastguard Worker <td>#11 - 2, 2, 1</td> 954*324bb76bSAndroid Build Coastguard Worker <td>1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1</td> 955*324bb76bSAndroid Build Coastguard Worker</tr> 956*324bb76bSAndroid Build Coastguard Worker</table> 957*324bb76bSAndroid Build Coastguard Worker 958*324bb76bSAndroid Build Coastguard Worker<p>We start the loop again by reading the next code. CODE now would be 959*324bb76bSAndroid Build Coastguard Worker#6 and this time we do have a record for this code in our code 960*324bb76bSAndroid Build Coastguard Workertable. Thus we dump {#6} to the index stream which would be 1,1. 961*324bb76bSAndroid Build Coastguard WorkerNow we take the first index in {#6} and call that K. Here, {#6} has 962*324bb76bSAndroid Build Coastguard Workertwo indexes, the first of which is 1; thus K = 1. Before moving 963*324bb76bSAndroid Build Coastguard Workeron, we add {CODE-1}+K to the code table. This #7 is now 1, 1, 1 [Step 2].</p> 964*324bb76bSAndroid Build Coastguard Worker 965*324bb76bSAndroid Build Coastguard Worker<p>I've included a few more steps so you can see the algorithm in action. While 966*324bb76bSAndroid Build Coastguard Workerthe explanation may sound complicated, you can see it's actually quite simple. 967*324bb76bSAndroid Build Coastguard WorkerYou'll also notice that you end up building the exact same 968*324bb76bSAndroid Build Coastguard Worker<a href="lzw_image_data_code_table.html">code table</a> 969*324bb76bSAndroid Build Coastguard Workeras the one that was created during compression. This is the reason that 970*324bb76bSAndroid Build Coastguard WorkerLZW is so great; we can just share the codes and not the table.</p> 971*324bb76bSAndroid Build Coastguard Worker 972*324bb76bSAndroid Build Coastguard Worker<h2><a name="lzw_bytes">Saving the Code Stream as Bytes</a></h2> 973*324bb76bSAndroid Build Coastguard Worker 974*324bb76bSAndroid Build Coastguard Worker<p>I've shown you how to go back and forth between index and code stream, but 975*324bb76bSAndroid Build Coastguard Workerhaven't told you what to do with them. The index stream is used to specify the 976*324bb76bSAndroid Build Coastguard Workercolor of each of the pixel of your image and really only shows up on screen. 977*324bb76bSAndroid Build Coastguard WorkerIt is the code stream that is actually saved in the GIF files on your computer 978*324bb76bSAndroid Build Coastguard Workeror transmitted over the internet. In order to save these code streams, we must 979*324bb76bSAndroid Build Coastguard Workerturn them into bytes. The first thought might be to store each of the codes 980*324bb76bSAndroid Build Coastguard Workeras its own byte; however this would limit the max code to just #255 and 981*324bb76bSAndroid Build Coastguard Workerresult in a lot of wasted bits for the small codes. To solve these problems, 982*324bb76bSAndroid Build Coastguard Workerthe GIF file format actually uses flexible <em>code sizes</em>.</p> 983*324bb76bSAndroid Build Coastguard Worker 984*324bb76bSAndroid Build Coastguard Worker<p>Flexible code sizes allow for further compression by limiting the bits 985*324bb76bSAndroid Build Coastguard Workerneeded to save the code stream as bytes. The <em>code size</em> is the number 986*324bb76bSAndroid Build Coastguard Workerof bits it takes to store the value of the code. When we talk about bits, 987*324bb76bSAndroid Build Coastguard Workerwe're referring to the 1's and 0's that make up a byte. The codes are 988*324bb76bSAndroid Build Coastguard Workerconverted to their binary values to come up with the bits. To specify 989*324bb76bSAndroid Build Coastguard Workerthe code for #4, you would look at this binary equivalent, which is 100, 990*324bb76bSAndroid Build Coastguard Workerand see that you would need three bits to store this value. The largest code 991*324bb76bSAndroid Build Coastguard Workervalue in our sample code stream is #36 (binary: 100100) which would 992*324bb76bSAndroid Build Coastguard Workertake 6 bits to encode. Note that the number of bits i've just given is 993*324bb76bSAndroid Build Coastguard Workerthe minimum number. You can make the number take up more bits by adding 994*324bb76bSAndroid Build Coastguard Workerzeros to the front.</p> 995*324bb76bSAndroid Build Coastguard Worker 996*324bb76bSAndroid Build Coastguard Worker<p style="text-align:center"><img src="image_data_block.gif" alt="GIF image data block layout" style="border: 1px solid black" /></p> 997*324bb76bSAndroid Build Coastguard Worker 998*324bb76bSAndroid Build Coastguard Worker<p>We need a way to know what size each of the codes are. Recall that the 999*324bb76bSAndroid Build Coastguard Workerimage data block begins with a single byte value called the 1000*324bb76bSAndroid Build Coastguard Worker<em>LZW minimum code size</em>. The GIF format allows sizes as small 1001*324bb76bSAndroid Build Coastguard Workeras 2 bits and as large as 12 bits. This minimum code size value is typically 1002*324bb76bSAndroid Build Coastguard Workerthe number of bits/pixel of the image. So if you have 32 colors in your image, 1003*324bb76bSAndroid Build Coastguard Workeryou will need 5 bits/pixel (for numbers 0-31 because 31 in binary is 11111). 1004*324bb76bSAndroid Build Coastguard WorkerThus, this will most likely be one more than the bit value for the size of the 1005*324bb76bSAndroid Build Coastguard Workercolor table you are using. (Even if you only have two colors, the minimum 1006*324bb76bSAndroid Build Coastguard Workercode size most be at least 2.) Refer to the <a href="#color_table_size"> 1007*324bb76bSAndroid Build Coastguard Workercode table above</a> to remind yourself how that works.</p> 1008*324bb76bSAndroid Build Coastguard Worker 1009*324bb76bSAndroid Build Coastguard Worker<p>Here's the funny thing: the value for minimum code size isn't 1010*324bb76bSAndroid Build Coastguard Workeractually the smallest code size that's used in the encoding 1011*324bb76bSAndroid Build Coastguard Workerprocess. Because the minimum code size tells you how many bits are 1012*324bb76bSAndroid Build Coastguard Workerneeded just for the different colors of the image, you still have to 1013*324bb76bSAndroid Build Coastguard Workeraccount for the two special codes that we always add to the code 1014*324bb76bSAndroid Build Coastguard Workertable. Therefore the actual smallest code size that will be used is 1015*324bb76bSAndroid Build Coastguard Workerone more than the value specified in the "minimum" code size 1016*324bb76bSAndroid Build Coastguard Workerbyte. I'll call this new value the <em>first code size</em>.</p> 1017*324bb76bSAndroid Build Coastguard Worker 1018*324bb76bSAndroid Build Coastguard Worker<p>We now know how many bytes the first code will be. This size will probably 1019*324bb76bSAndroid Build Coastguard Workerwork for the next few codes as well, but recall that the GIF format 1020*324bb76bSAndroid Build Coastguard Workerallows for flexible code sizes. As larger code values get added to your 1021*324bb76bSAndroid Build Coastguard Workercode table, you will soon realize that you need larger code sizes if you 1022*324bb76bSAndroid Build Coastguard Workerwere to output those values. When you are encoding the data, you increase 1023*324bb76bSAndroid Build Coastguard Workeryour code size as soon as your write out the code equal to 1024*324bb76bSAndroid Build Coastguard Worker2^(current code size)-1. If you are decoding from codes to indexes, 1025*324bb76bSAndroid Build Coastguard Workeryou need to increase your code size as soon as you add the code value that 1026*324bb76bSAndroid Build Coastguard Workeris equal to 2^(current code size)-1 to your code table. That is, the next 1027*324bb76bSAndroid Build Coastguard Workertime you grab the next section of bits, you grab one more.</p> 1028*324bb76bSAndroid Build Coastguard Worker 1029*324bb76bSAndroid Build Coastguard Worker<p>Note that the largest code size allowed is 12 bits. If you get to this 1030*324bb76bSAndroid Build Coastguard Workerlimit, the next code you encounter should be the <em>clear code</em> which 1031*324bb76bSAndroid Build Coastguard Workerwould tell you to reinitialize the code table. You then go back to using 1032*324bb76bSAndroid Build Coastguard Workerthe first code size and grow again when necessary.</p> 1033*324bb76bSAndroid Build Coastguard Worker 1034*324bb76bSAndroid Build Coastguard Worker<p>Jumping back to our sample image, we see that we have a minimum code 1035*324bb76bSAndroid Build Coastguard Workersize value of 2 which means out first code size will be 3 bits long. 1036*324bb76bSAndroid Build Coastguard WorkerOut first three codes, #1 #6 and #6, would be coded as 001 110 and 110. 1037*324bb76bSAndroid Build Coastguard WorkerIf you see at Step 6 of the encoding, we added a code of #7 to our code 1038*324bb76bSAndroid Build Coastguard Workertable. This is our clue to increase our code size because 7 is equal to 1039*324bb76bSAndroid Build Coastguard Worker2^3-1 (where 3 is our current code size). Thus, the next code we 1040*324bb76bSAndroid Build Coastguard Workerwrite out, #2, will use the new code size of 4 and therefore look 1041*324bb76bSAndroid Build Coastguard Workerlike 0010. In the decoding process, we again would increase our code 1042*324bb76bSAndroid Build Coastguard Workersize when we read the code for #7 and would read the next 4, rather than 1043*324bb76bSAndroid Build Coastguard Workerthe next 3 bits, to get the next code. In the sample table above this 1044*324bb76bSAndroid Build Coastguard Workeroccurs in Step 2.</p> 1045*324bb76bSAndroid Build Coastguard Worker 1046*324bb76bSAndroid Build Coastguard Worker<p>Finally we must turn all these bit values into bytes. The lowest bit of the 1047*324bb76bSAndroid Build Coastguard Workercode bit value gets placed in the lowest available bit of the byte. After 1048*324bb76bSAndroid Build Coastguard Workeryou've filled up the 8 bits in the byte, you take any left over bits and 1049*324bb76bSAndroid Build Coastguard Workerstart a new byte. Take a look at the following illustration to see 1050*324bb76bSAndroid Build Coastguard Workerhow that works with the codes from our sample image.</p> 1051*324bb76bSAndroid Build Coastguard Worker 1052*324bb76bSAndroid Build Coastguard Worker<p style="text-align:center"><img src="lzw_encoding_codes.gif" 1053*324bb76bSAndroid Build Coastguard Workeralt="Encoding LZW Codes" style="border: 1px solid black" / WIDTH="500" 1054*324bb76bSAndroid Build Coastguard WorkerHEIGHT="220"></p> 1055*324bb76bSAndroid Build Coastguard Worker 1056*324bb76bSAndroid Build Coastguard Worker<p>You can see in the first byte that was returned (<span 1057*324bb76bSAndroid Build Coastguard Workerclass="byte">8C</span>) that the lowest three bits (because that was 1058*324bb76bSAndroid Build Coastguard Workerour first code size) contain 010 which is the binary value of 6 so 1059*324bb76bSAndroid Build Coastguard Workerthat would be the clear code we started with, #4. In the three bits to 1060*324bb76bSAndroid Build Coastguard Workerthe left, you see 001 which out or first data code of #1. You can also 1061*324bb76bSAndroid Build Coastguard Workersee when we switched into code sizes of 4 bits in the second byte 1062*324bb76bSAndroid Build Coastguard Worker(<span class="byte">2D</span>).</p> 1063*324bb76bSAndroid Build Coastguard Worker 1064*324bb76bSAndroid Build Coastguard Worker<p>When you run out of codes but have filled less than 8 bits of the 1065*324bb76bSAndroid Build Coastguard Workerbyte, you should just fill the remaining bits with zeros. Recall that 1066*324bb76bSAndroid Build Coastguard Workerthe image data must be broken up onto <a 1067*324bb76bSAndroid Build Coastguard Workerhref="bits_and_bytes.html#image_data_block">data sub-blocks</a>. Each 1068*324bb76bSAndroid Build Coastguard Workerof the data sub-blocks begins with a byte that specifies how many 1069*324bb76bSAndroid Build Coastguard Workerbytes of data. The value will be between 1 and 255. After you read 1070*324bb76bSAndroid Build Coastguard Workerthose bytes, the next byte indicates again how many bytes of data 1071*324bb76bSAndroid Build Coastguard Workerfollow. You stop when you encounter a subblock that has a lenght of 1072*324bb76bSAndroid Build Coastguard Workerzero. That tells you when you've reached the end of the image data. In 1073*324bb76bSAndroid Build Coastguard Workerour sample the image the byte just after the LZW code size is <span 1074*324bb76bSAndroid Build Coastguard Workerclass="byte">16</span> which indicates that 22 bytes of data 1075*324bb76bSAndroid Build Coastguard Workerfollow. After we reach those, we see the next byte is <span 1076*324bb76bSAndroid Build Coastguard Workerclass="byte">00</span> which means we are all done.</p> 1077*324bb76bSAndroid Build Coastguard Worker 1078*324bb76bSAndroid Build Coastguard Worker<p>Return codes from bytes the basically just the same process in 1079*324bb76bSAndroid Build Coastguard Workerreverse. A sample illustration of the process follows which shows how 1080*324bb76bSAndroid Build Coastguard Workeryou would extract codes if the first code size were 5 bits.</p> 1081*324bb76bSAndroid Build Coastguard Worker 1082*324bb76bSAndroid Build Coastguard Worker<p style="text-align:center"><img src="lzw_decoding_bytes.gif" alt="Decoding LZW Bytes" style="border: 1px solid black" / WIDTH="500" HEIGHT="220"></p> 1083*324bb76bSAndroid Build Coastguard Worker 1084*324bb76bSAndroid Build Coastguard Worker<h2>Next: Animation and Transparency</h2> 1085*324bb76bSAndroid Build Coastguard Worker 1086*324bb76bSAndroid Build Coastguard Worker<p>That is pretty much everything you need to know to read or generate 1087*324bb76bSAndroid Build Coastguard Workera basic image file. One of the reasons the GIF becames such a popular 1088*324bb76bSAndroid Build Coastguard Workerformat was because it also allowed for "fancier" features. These 1089*324bb76bSAndroid Build Coastguard Workerfeatures include animation and transparency. Next we'll look 1090*324bb76bSAndroid Build Coastguard Workerat how those work.</p> 1091*324bb76bSAndroid Build Coastguard Worker 1092*324bb76bSAndroid Build Coastguard Worker<p><a href="animation_and_transparency.html">Continue...</a></p> 1093*324bb76bSAndroid Build Coastguard Worker</div> 1094*324bb76bSAndroid Build Coastguard Worker 1095*324bb76bSAndroid Build Coastguard Worker<div style="text-align:center; margin-top: 10px; padding-top: 10px; border-top: #cecece 1px solid"> 1096*324bb76bSAndroid Build Coastguard Worker<a href="../index.html">Back to GIFLIB documentation</a> 1097*324bb76bSAndroid Build Coastguard Worker</div> 1098*324bb76bSAndroid Build Coastguard Worker 1099*324bb76bSAndroid Build Coastguard Worker</body> 1100*324bb76bSAndroid Build Coastguard Worker 1101*324bb76bSAndroid Build Coastguard Worker</html> 1102
