Inside a GIF file: blocks, LZW and disposal
GIF is from 1987 and still the format people mean when they say “an animation”. It is small enough to read in an afternoon: a header, a palette, and a stream of blocks, with pixels compressed by LZW and animation done by drawing patches over the previous picture under a disposal rule. This is a tour of that format using the bytes of a real file, with the JavaScript to decode it. It also covers why reversing a GIF is harder than it looks, why two GIFs that look the same can share almost no bytes, and how to open a GIF of many gigabytes when nothing in it says where frame 10,000 starts.
Header and logical screen
These are the first bytes of the sample on OmniViewer, a 34-frame clip of a bamboo grove:
00000000: 47 49 46 38 39 61 f0 00 88 00 f7 ff 00 GIF89a ...........
└─ signature ────┘ width height pk bg aspect
00000013: 00 08 02 0f 09 02 13 0e 06 … 256 RGB triplets (768 bytes)Six bytes of signature (GIF87a or GIF89a), then the logical screen: width 0x00f0 = 240 and height 0x0088 = 136, little-endian. The packed byte 0xf7 says a global colour table follows (top bit), and its size is 2(7 + 1) = 256 entries of three bytes each. Every frame without a palette of its own uses this one. A GIF never has more than 256 colours in one frame. That is the format’s one hard limit, and every frame may bring its own table to work around it.
const width = u8[6] | u8[7] << 8;
const height = u8[8] | u8[9] << 8;
const packed = u8[10];
const gctSize = packed & 0x80 ? 2 << (packed & 7) : 0; // entries, 2..256
let pos = 13 + gctSize * 3; // the first blockBlocks and sub-blocks
After the palette, the file is a stream of blocks, each introduced by one byte:
0x21an extension: a label byte, then data;0x2Can image: a 10-byte descriptor, an optional local palette, then the compressed pixels;0x3Bthe trailer: the file is over.
Extension data and image data are both stored as a chain of sub-blocks. Each one is a length byte (1–255) followed by that many bytes, and a zero length ends the chain. That is the whole container. There is no size for a block as a whole and no table of contents. The only way to find where something ends is to follow its length bytes.
Walking a GIF
function skipChain(u8, p) { // p: the first length byte
for (;;) {
const n = u8[p];
p += 1 + n;
if (n === 0) return p; // just past the terminator
}
}
for (;;) {
const intro = u8[pos];
if (intro === 0x3b) break; // trailer
if (intro === 0x21) { // extension
pos = skipChain(u8, pos + 2); // skip label, then hop
} else if (intro === 0x2c) { // image
const p = u8[pos + 9];
const lct = p & 0x80 ? 2 << (p & 7) : 0;
const lzwMin = pos + 10 + lct * 3; // LZW minimum code size
pos = skipChain(u8, lzwMin + 1);
} else throw new Error(`no block starts with 0x${intro.toString(16)}`);
}That loop is the core of the BLOCKS tab. It reads one length byte in every 256 at most and never touches a pixel. OmniViewer’s version also records what it passes: each frame’s rectangle, timing and byte range, plus every comment, application block and anything odd, such as a missing trailer, bytes after it, or a frame that hangs off the canvas.
One frame: control + descriptor
Here is the first frame of the sample, at offset 0x320:
21 f9 04 04 3c 00 1f 00 graphic control extension
│ └delay┘ │
│ 60 cs transparent index (unused: flag bit 0 is off)
packed 0x04: disposal 1 (leave), no transparency
2c 00 00 00 00 f0 00 88 00 00 image descriptor: at (0,0), 240×136,
no local palette, not interlaced
08 LZW minimum code size
ff 00 6b ec 18 52 … sub-blocks of compressed pixelsThe graphic control extension (label 0xF9) applies to the image that follows it. It carries the delay in hundredths of a second, here 60, so 600 ms. It also carries an optional transparent colour index, whose pixels are not drawn so the canvas shows through, and the disposal method, which says what to do with this frame before the next one is drawn. Browsers treat a delay of 0 or 1 as 10 (100 ms), so a GIF cannot really play faster than 50 fps, and one that asks for 0 plays at 10.
The image descriptor places a rectangle on the canvas. In most animated GIFs that rectangle is smaller than the canvas, because only part of the picture changed.
LZW, decoded
The pixels are palette indices, compressed with LZW. The decoder builds the same dictionary the encoder built, one entry per code read, so the dictionary is never stored. Codes start one bit wider than the minimum code size and grow to at most 12 bits. Two codes are reserved: clear (2min) resets the dictionary, and end (clear + 1) stops.
function lzwDecode(data, minCode, pixels) { // data: sub-blocks already joined
const out = new Uint8Array(pixels);
const clear = 1 << minCode, end = clear + 1;
const prefix = new Int16Array(4096), suffix = new Uint8Array(4096), first = new Uint8Array(4096);
for (let i = 0; i < clear; i++) { prefix[i] = -1; suffix[i] = first[i] = i; }
let size = minCode + 1, next = end + 1, old = -1, acc = 0, bits = 0, ip = 0, op = 0;
const stack = new Uint8Array(4097);
while (op < pixels && ip <= data.length) {
while (bits < size) { acc |= data[ip++] << bits; bits += 8; } // LSB-first
const code = acc & ((1 << size) - 1); acc >>>= size; bits -= size;
if (code === clear) { size = minCode + 1; next = end + 1; old = -1; continue; }
if (code === end) break;
if (old === -1) { out[op++] = old = code; continue; }
let c = code, sp = 0;
if (code === next) { stack[sp++] = first[old]; c = old; } // the KwKwK case
while (c >= clear) { stack[sp++] = suffix[c]; c = prefix[c]; }
stack[sp++] = c;
while (sp) out[op++] = stack[--sp];
if (next < 4096) {
prefix[next] = old; suffix[next] = c; first[next] = first[old];
if (++next === 1 << size && size < 12) size++;
}
old = code;
}
return out;
}Two details catch people out. When the dictionary fills at 4096 entries, the encoder may keep emitting codes without a clear, and the decoder must simply stop adding entries. And a code that is not in the dictionary yet can only be the entry about to be made. That is the “KwKwK” case: the previous string plus its own first character. An interlaced frame then needs its rows put back in order. They arrive in four passes: every 8th row from 0, every 8th from 4, every 4th from 2, then every 2nd from 1.
This decoder, a compositor and the walk come to a few hundred lines with no library. OmniViewer’s matches ffmpeg’s GIF decoder pixel for pixel on every frame of the sample and of test files covering interlacing, local palettes and every disposal method.
Disposal: how frames stack
A GIF animation is one canvas. Each frame paints its rectangle onto it, skipping the transparent index. Then, before the next frame is drawn, the frame’s disposal method is applied:
- 0 / 1, leave it: the next frame draws on top.
- 2, restore to background: clear the rectangle. Every current browser clears it to transparent, not to the “background colour” the header names.
- 3, restore previous: put back what was under the rectangle before this frame was drawn. A decoder has to save that region first.
function draw(canvas, W, f, indices, pal) { // canvas: W×H RGBA
if (pending?.disposal === 2) clearRect(canvas, pending);
if (pending?.disposal === 3) restoreRect(canvas, pending, saved);
if (f.disposal === 3) saved = copyRect(canvas, f);
for (let y = 0; y < f.height; y++) for (let x = 0; x < f.width; x++) {
const k = indices[y * f.width + x];
if (k === f.transparent) continue; // the old picture shows through
const o = ((f.y + y) * W + f.x + x) * 4;
canvas[o] = pal[k * 3]; canvas[o + 1] = pal[k * 3 + 1]; canvas[o + 2] = pal[k * 3 + 2]; canvas[o + 3] = 255;
}
pending = f;
}Optimisers lean on this heavily. ffmpeg, which made the sample, marks every pixel that did not change since the previous frame as transparent, so LZW gets long runs of one index. The sample’s frames 2–34 all cover the full canvas, yet most of their pixels are see-through.
Why editing needs a compositor
Because of disposal, frame 12 of a GIF is not a picture on its own. It is a patch that only makes sense over frames 1–11. So you cannot reverse a GIF by reversing its frames, or rotate one by rotating each rectangle and keeping the transparency, or save “frame 12” by decoding frame 12 alone. OmniViewer’s TRANSFORM tab first composites every frame into the full picture a browser would show. Only then does it apply the edits (colour, rotation, size, order, speed) and write a new file. The re-encoded GIF gets a fresh palette per frame, with only the changed rectangle written. A frame that already fits in 256 colours keeps them exactly, so a GIF re-encoded without edits is pixel-identical to the original.
The same composited frames feed the conversions. As a lossless animated PNG they go to ffmpeg, compiled to WebAssembly, for MP4, WebM and animated WebP. That keeps every frame’s own duration, with one fix: ffmpeg times a frame by the next one’s timestamp, so without care the last frame of a variable-rate animation gets a guessed duration.
Comparing two GIFs
LZW is adaptive, so one changed pixel early in a frame changes the dictionary and every code after it. Two GIFs that look identical (the same animation saved by two programs, or saved twice) can share almost none of their bytes. A byte diff tells you nothing. OmniViewer’s DIFF tab decodes both files and compares what they show, frame by frame and pixel by pixel. It pairs frames by number, or by time when one file dropped frames, and also compares delays and loop counts. Side B can be a PNG, APNG or WebP as well, which is how you check that an export kept everything.
Comments, XMP and loops
Animation looping is not in the GIF spec at all. It is an application extension Netscape invented: 21 ff 0b "NETSCAPE2.0" 03 01 nn nn 00, where the 16-bit number counts repeats after the first play and 0 means forever. A file without it plays once. The same mechanism carries an XMP packet ("XMP DataXMP", written raw and followed by a 258-byte “magic trailer” that makes the raw bytes parse as sub-blocks) and ICC colour profiles. Comment extensions (0xFE) hold free text. A viewer shows none of them. The sample carries a comment and an XMP packet naming the place it was filmed, and the BLOCKS tab’s clean copy drops both while copying the frames byte for byte.
Opening a huge GIF
Nothing in a GIF records where a frame starts, and the image data has no length field, so the walk above is the only way in. OmniViewer runs it in a worker over 4 MB reads and hops sub-blocks synchronously inside each read. That is one await per megabyte rather than one per 256-byte sub-block. What it keeps is numbers, about twenty per frame.
- A 1 GB test GIF (the sample’s frames repeated, 37,978 frames, two hours long) indexed in about one second in Chromium, with a 23 MB page heap. The walk itself ran at 1.7 GB/s from cache.
- Frames are decoded one at a time when you look at them. A seek starts from the frame already on the canvas, a cached snapshot (capped at 192 MB) or a key frame: one that covers the whole canvas with no transparent index, so nothing before it can show through. On a 12,614-frame file of such frames, jumping to the end took 27 ms.
- The worst case is a file like the sample, where every frame after the first is transparency-optimised and nothing stands alone. The first jump to the end of the 1 GB file decoded all 37,978 frames in 29 seconds, with a progress line. After that, snapshots made seeks back into it take about 50 ms.
- Exports run frame by frame too, holding only the current canvas and the output, and the clean copy is byte ranges of the original file.
Where the spec lives
The format is the GIF89a specification (CompuServe, 1990). The NETSCAPE2.0 loop block and the browsers’ delay clamping are folklore, written down in browser source code rather than in any standard. None of it needs a library. The OmniViewer GIF toolkit is the code above plus a user interface, running in your browser.
