Editing GIF (section)

==Example GIF file==
{| class="wikitable"
|-
|[[Microsoft Paint]] saves a small black-and-white image as the following GIF file (illustrated enlarged).<br/>Paint does not make optimal use of GIF; due to the unnecessarily large color table (storing a full 256 colors instead of the used 2) and symbol width, this GIF file is not an efficient representation of the 15-pixel image.<br/>Although the Graphic Control Extension block declares color index 16 (hexadecimal 10) to be transparent, that index is not used in the image. The only color indexes appearing in the image data are decimal 40 and 255, which the Global Color Table maps to black and white, respectively.
|[[File:gifSample.gif|center]]
{{small|Sample image (enlarged), actual size 3&nbsp;pixels&nbsp;wide by 5&nbsp;high}}
|}
The hex numbers in the following tables are in [[Endianness|little-endian]] byte order, as the format specification prescribes.

{| class="wikitable"
|+ Table of example GIF image values
! Byte # (hex) !! Hexadecimal !! Text or value !! colspan=2 | Meaning
|-
| 0 || 47 49 46 38 39 61 || GIF89a || colspan=2 | Header
|-
! colspan=5 | Logical Screen Descriptor
|-
| 6 || 03 00 || 3 || colspan=2 | Logical screen width
|-
| 8 || 05 00 || 5 || colspan=2 | Logical screen height
|-
| A || F7 || || colspan=2 | GCT follows for 256 colors with resolution 3{{resx}}8 bits/primary, the lowest 3 bits represent the bit depth minus 1, the highest true bit means that the GCT is present
|-
| B || 00 || 0 || colspan=2 | Background color: index #0; #000000 black
|-
| C || 00 || 0 || colspan=2 | Default pixel aspect ratio, 0:0
|-
! colspan=5 | Global Color Table
|- 
| D || 00 00 00 || 
{| class="wikitable"
! R (red) !! G (green) !! B (blue)
|-
| 0 || 0 || 0
|}
|| Global Color Table, color #0: #000000, black || rowspan=4 width=220px | [[File:GIFPAL.png|none|thumb|Bytes D<sub>h</sub> to 30C<sub>h</sub> in the example define a palette of 256 colors. The indexes used in the sample image for black and white are 28<sub>h</sub> and FF<sub>h</sub>.]]
|-
| 10 || 80 00 00 || 
{| class="wikitable"
! R (red) !! G (green) !! B (blue)
|-
| 128 || 0 || 0
|}
|| Global Color Table, color #1: transparent bit, not used in image
|-
| ... || ... || ... || Global Color Table extends to 30A
|-
| 30A || FF FF FF ||
{| class="wikitable"
! R (red) !! G (green) !! B (blue)
|-
| 255 || 255 || 255
|}
|| Global Color Table, color #255: #ffffff, white
|-
! colspan=5 | Graphic Control Extension
|-
| 30D || 21 || <code>'!'</code> || colspan="2" | An Extension Block (introduced by an ASCII exclamation point <code>'!'</code>)
|-
| 30E || F9 || || colspan="2" | A Graphic Control Extension
|-
| 30F || 04 || 4 || colspan=2 | Amount of GCE data, 4 bytes
|-
| 310 || 01 || || colspan=2 | Transparent background color; this is a bit field, the lowest bit signifies transparency
|-
| 311 || 00 00 || || colspan=2 | Delay for animation in hundredths of a second; '''not used'''
|-
| 313 || 10 || 16 || colspan=2 | Color number of transparent pixel in GCT
|-
| 314 || 00 || || colspan=2 | End of GCE block
|-
! colspan=5 | Image Descriptor
|-
| 315 || 2C || <code>','</code>|| colspan="2" | An Image Descriptor (introduced by 0x2C, an ASCII comma <code>','</code>)
|-
| 316 || 00 00 00 00 || (0, 0) || colspan=2 | North-west corner position of image in logical screen
|-
| 31A || 03 00 05 00 || (3, 5) || colspan=2 | Image width and height in pixels
|-
| 31E || 00 || 0 || colspan=2 | Local color table bit, 0 means none
|-
! colspan=5 | Image Data
|-
| 31F || 08 || 8 || colspan=2 | Start of image, LZW minimum code size
|-
| 320 || 0B || 11 || colspan=2 | Beginning of first data sub-block, specifying 11 bytes of encoded data to follow
|-
| 321 || 00 51 FC 1B 28 70 A0 C1 83 01 01 || <image data> || colspan=2 | 11 bytes of image data, see field 320
|-
| 32C || 00 || 0 || colspan=2 | Ending data sub-block, specifying no following data bytes (and the end of the image)
|-
! colspan=5 | Trailer
|-
| 32D || 3B || <code>';'</code> || colspan=2 | File termination block indicator (an ASCII semi-colon <code>';'</code>)
|}

===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.

===Image decoding===
Decoding begins by mapping the stored bytes back to 9-bit codes. These are decoded to recover the pixel colors as shown below. A table identical to the one used in the encoder is built by adding strings by this rule:
{| class="wikitable"
|+ Is incoming code found in table?
|  {{Yes}} || add string for local code followed by first byte of string for incoming code
|-
|  {{No}}  || add string for local code followed by copy of its own first byte
|}

       '''shift'''
 '''9-bit ----> Local      Table                 Pixel'''
 <u>'''code        code   code --> string   Palette color  Action'''</u>
 100h               000h  | #0                       Initialize root table of 9-bit codes
                     :    | palette
                     :    | colors
                    0FFh  | #255
                    100h  | clr
                    101h  | end
 028h                     |             #40   {{font color|WHITE|BLACK|BLACK}}  Decode 1st pixel
 0FFh        028h         |                           Incoming code found in table
                          |             #255  {{font color|BLACK|WHITE|WHITE}}   - output string from table
                    102h  | 28 FF                     - add to table
 103h        0FFh         |                           Incoming code not found in table
                    103h  | FF FF                     - add to table
                          |                           - output string from table
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
 102h        103h         |                           Incoming code found in table
                          |                           - output string from table
                          |             #40   {{font color|WHITE|BLACK|BLACK}}
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                    104h  | FF FF 28                  - add to table
 103h        102h         |                           Incoming code found in table
                          |                           - output string from table
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                    105h  | 28 FF FF                  - add to table
 106h        103h         |                           Incoming code not found in table
                    106h  | FF FF FF                  - add to table
                          |                           - output string from table
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
 107h        106h         |                           Incoming code not found in table
                    107h  | FF FF FF FF               - add to table
                          |                           - output string from table
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
                          |             #255  {{font color|BLACK|WHITE|WHITE}}
 101h                     |                           End

===LZW code lengths===
Shorter code lengths can be used for palettes smaller than the 256 colors in the example. If the palette is only 64 colors (so color indexes are 6 bits wide), the symbols can range from 0 to 63, and the symbol width can be taken to be 6 bits, with codes starting at 7 bits. In fact, the symbol width need not match the palette size: as long as the values decoded are always less than the number of colors in the palette, the symbols can be any width from 2 to 8, and the palette size any power of 2 from 2 to 256. For example, if only the first four colors (values 0 to 3) of the palette are used, the symbols can be taken to be 2 bits wide with codes starting at 3 bits.

Conversely, the symbol width could be set at 8, even if only values 0 and 1 are used; these data would only require a two-color table. Although there would be no point in encoding the file that way, something similar typically happens for bi-color images: the minimum symbol width is 2, even if only values 0 and 1 are used.

The code table initially contains codes that are one bit longer than the symbol size in order to accommodate the two special codes ''clr'' and ''end'' and codes for strings that are added during the process. When the table is full the code length increases to give space for more strings, up to a maximum code 4095 = FFF(hex). As the decoder builds its table it tracks these increases in code length and it is able to unpack incoming bytes accordingly.

===Uncompressed GIF ===
{| class="wikitable floatright" width=145px
|-
|[[File:Quilt design as 46x46 uncompressed GIF.gif|center]]
{{small|A 46×46 uncompressed GIF with 7-bit symbols (128 colors, 8-bit codes).<br/>Click on the image for an explanation of the code.}}
|}
The GIF encoding process can be modified to create a file without LZW compression that is still viewable as a GIF image. This technique was introduced originally as a way to avoid patent infringement. Uncompressed GIF can also be a useful intermediate format for a graphics programmer because individual pixels are accessible for reading or painting. An uncompressed GIF file can be converted to an ordinary GIF file simply by passing it through an image editor.

The modified encoding method ignores building the LZW table and emits only the root palette codes and the codes for CLEAR and STOP. This yields a simpler encoding (a 1-to-1 correspondence between code values and palette codes) but sacrifices all of the compression: each pixel in the image generates an output code indicating its color index. When processing an uncompressed GIF, a standard GIF decoder will not be prevented from writing strings to its dictionary table, but the code width must never increase since that triggers a different packing of bits to bytes.

If the symbol width is {{mvar|n}}, the codes of width {{math|''n''+1}} fall naturally into two blocks: the lower block of {{math|2{{sup|''n''}}}} codes for coding single symbols, and the upper block of {{math|2{{sup|''n''}}}} codes that will be used by the decoder for sequences of length greater than one. Of that upper block, the first two codes are already taken: {{math|2{{sup|''n''}}}} for CLEAR and {{math|2{{sup|''n''}} + 1}} for STOP. The decoder must also be prevented from using the last code in the upper block, {{math|2<sup>''n''+1</sup> − 1}}, because when the decoder fills that slot, it will increase the code width. Thus in the upper block there are {{math|2{{sup|''n''}} − 3}} codes available to the decoder that won't trigger an increase in code width. Because the decoder is always one step behind in maintaining the table, it does not generate a table entry upon receiving the first code from the encoder, but will generate one for each succeeding code. Thus the encoder can generate {{math|2{{sup|''n''}} − 2}} codes without triggering an increase in code width. Therefore, the encoder must emit extra CLEAR codes at intervals of {{math|2{{sup|''n''}} − 2}} codes or less to make the decoder reset the coding dictionary. The GIF standard allows such extra CLEAR codes to be inserted in the image data at any time. The composite data stream is partitioned into sub-blocks that each carry from 1 to 255 bytes.

For the sample 3×5 image above, the following 9-bit codes represent "clear" (100) followed by image pixels in scan order and "stop" (101).

 100 028 0FF 0FF 0FF 028 0FF 0FF 0FF 0FF 0FF 0FF 0FF 0FF 0FF 0FF 101

After the above codes are mapped to bytes, the uncompressed file differs from the compressed file thus:

{| class="wikitable"
! Byte # (hex) !! Hexadecimal !! Text or value !! Meaning 
|-
| 320 || 14 || 20 || 20 bytes uncompressed image data follow
|-
| 321 || 00 51 FC FB F7 0F C5 BF 7F FF FE FD FB F7 EF DF BF 7F 01 01 || ||
|-
| 335 || 00 || 0 || End of image data
|}