Editing GIF (section)

===Image coding===
The image pixel data, scanned horizontally from top left, are converted by [[Lempel–Ziv–Welch|LZW encoding]] to codes that are then mapped into bytes for storing in the file. The pixel codes typically don't match the 8-bit size of the bytes, so the codes are packed into bytes by a "little-Endian" scheme: the least significant bit of the first code is stored in the least significant bit of the first byte, higher order bits of the code into higher order bits of the byte, spilling over into the low order bits of the next byte as necessary. Each subsequent code is stored starting at the least significant bit not already used.

This byte stream is stored in the file as a series of "sub-blocks". Each sub-block has a maximum length 255 bytes and is prefixed with a byte indicating the number of data bytes in the sub-block. The series of sub-blocks is terminated by an empty sub-block (a single 0 byte, indicating a sub-block with 0 data bytes).

For the sample image above the reversible mapping between 9-bit codes and bytes is shown below.

{| class="wikitable" style="text-align:right;"
|+ Reversible mapping
! colspan=2 | 9-bit code
! colspan=2 | Byte
|-
! Hexadecimal !! Binary !! Binary !! Hexadecimal
|- style="font-family:monospace;"
| {{color|red|100}}   || {{color|red|1 00000000}}   || {{color|red|00000000}} || 00
|- style="font-family:monospace;"
| {{color|green|028}} || {{color|green|00 0101000}} || {{color|green|0101000}} {{color|red|1}} || 51
|- style="font-family:monospace;"
| {{color|blue|0FF}}  || {{color|blue|011 111111}}  || {{color|blue|111111}} {{color|green|00}} || FC
|- style="font-family:monospace;"
| {{color|red|103}}   || {{color|red|1000 00011}}   || {{color|red|00011}} {{color|blue|011}} || 1B
|- style="font-family:monospace;"
| {{color|green|102}} || {{color|green|10000 0010}} || {{color|green|0010}} {{color|red|1000}} || 28
|- style="font-family:monospace;"
| {{color|blue|103}}  || {{color|blue|100000 011}}  || {{color|blue|011}} {{color|green|10000}} || 70
|- style="font-family:monospace;"
| {{color|red|106}}   || {{color|red|1000001 10}}   || {{color|red|10}} {{color|blue|100000}} || A0
|- style="font-family:monospace;"
| {{color|green|107}} || {{color|green|10000011 1}} || {{color|green|1}} {{color|red|1000001}} || C1
|- style="font-family:monospace;"
|                     ||                            || {{color|green|10000011}} || 83
|- style="font-family:monospace;"
| {{color|blue|101}}  || {{color|blue|1 00000001}}  || {{color|blue|00000001}} || 01
|- style="font-family:monospace;"
|                     ||                            || {{color|black|0000000}} {{color|blue|1}} || 01
|}

A slight compression is evident: pixel colors defined initially by 15 bytes are exactly represented by 12 code bytes including control codes.
The encoding process that produces the 9-bit codes is shown below. A local string accumulates pixel color numbers from the palette, with no output action as long as the local string can be found in a code table. There is special treatment of the first two pixels that arrive before the table grows from its initial size by additions of strings. After each output code, the local string is initialized to the latest pixel color (that could not be included in the output code).

                           '''Table           9-bit'''
                      <u>'''string --> code      code    Action'''</u>
                           #0 | 000h               Initialize root table of 9-bit codes
                     palette  |  :
                      colors  |  :
                         #255 | 0FFh
                          clr | 100h
                          end | 101h
                              |            100h     Clear
 Pixel          Local         |
 color Palette  string        |
 BLACK  #40     28            |            028h     1st pixel always to output
 WHITE  #255    FF            |                     String found in table
                   28 FF      | 102h                Always add 1st string to table
                FF            |                     Initialize local string
 WHITE  #255    FF FF         |                     String not found in table
                              |            0FFh     - output code for previous string
                   FF FF      | 103h                - add latest string to table
                FF            |                     - initialize local string
 WHITE  #255    FF FF         |                     String found in table
 BLACK  #40     FF FF 28      |                     String not found in table
                              |            103h     - output code for previous string
                   FF FF 28   | 104h                - add latest string to table
                28            |                     - initialize local string
 WHITE  #255    28 FF         |                     String found in table
 WHITE  #255    28 FF FF      |                     String not found in table
                              |            102h     - output code for previous string
                   28 FF FF   | 105h                - add latest string to table
                FF            |                     - initialize local string
 WHITE  #255    FF FF         |                     String found in table
 WHITE  #255    FF FF FF      |                     String not found in table
                              |            103h     - output code for previous string
                   FF FF FF   | 106h                - add latest string to table
                FF            |                     - initialize local string
 WHITE  #255    FF FF         |                     String found in table
 WHITE  #255    FF FF FF      |                     String found in table
 WHITE  #255    FF FF FF FF   |                     String not found in table
                              |            106h     - output code for previous string
                   FF FF FF FF| 107h                - add latest string to table
                FF            |                     - initialize local string
 WHITE  #255    FF FF         |                     String found in table
 WHITE  #255    FF FF FF      |                     String found in table
 WHITE  #255    FF FF FF FF   |                     String found in table
                                                    No more pixels
                                           107h     - output code for last string
                                           101h     End

For clarity the table is shown above as being built of strings of increasing length. That scheme can function but the table consumes an unpredictable amount of memory. Memory can be saved in practice by noting that each new string to be stored consists of a previously stored string augmented by one character. It is economical to store at each address only two words: an existing address and one character.

The LZW algorithm requires a search of the table for each pixel. A linear search through up to 4096 addresses would make the coding slow. In practice the codes can be stored in order of numerical value; this allows each search to be done by a SAR (Successive Approximation Register, as used in some [[Successive approximation ADC|ADCs]]), with only 12 magnitude comparisons. For this efficiency an extra table is needed to convert between codes and actual memory addresses; the extra table upkeeping is needed only when a new code is stored which happens at much less than pixel rate.