Calculating Stride for Interlaced GIF Decoding

Decoding an interlaced GIF requires calculating the memory stride to correctly place pixel data into a linear display buffer as rows arrive out of sequential order. This article explains how decoders determine memory stride from canvas dimensions and pixel depth, and how that stride is applied across the four interlacing passes to calculate precise destination buffer offsets.

Canvas Dimensions and Base Stride

The stride—often referred to as pitch—represents the byte length of a single horizontal row of pixels in memory. A decoder does not base its destination stride on the dimensions of the individual GIF image frame alone, but on the dimensions of the entire logical canvas and the target pixel format.

The standard calculation for the base stride is:

\[\text{Stride} = \text{Canvas Width} \times \text{Bytes Per Pixel}\]

If the rendering environment requires rows to align with specific memory boundaries (such as 4-byte or 32-byte alignment for hardware acceleration or SIMD operations), the decoder rounds the stride up:

\[\text{Aligned Stride} = \left( \text{Stride} + \text{Alignment} - 1 \right) \ \& \ \sim(\text{Alignment} - 1)\]

The Role of Interlacing

A non-interlaced GIF unpacks sequentially from row \(0\) to row \(H-1\). In contrast, an interlaced GIF splits the vertical rows into four distinct passes:

• Pass 1: Starts at row 0, steps by 8 rows (rows 0, 8, 16, ...)
• Pass 2: Starts at row 4, steps by 8 rows (rows 4, 12, 20, ...)
• Pass 3: Starts at row 2, steps by 4 rows (rows 2, 6, 10, ...)
• Pass 4: Starts at row 1, steps by 2 rows (rows 1, 3, 5, ...)

The interlacing scheme changes the row traversal order, but it does not alter the underlying horizontal memory stride. The decoder processes LZW-decompressed pixels one full scanline at a time, where each decoded line matches the sub-frame's width, and uses the stride to project that line into the correct vertical slot in memory.

Calculating Row Offsets in Memory

A sub-frame inside a GIF can be smaller than the logical canvas and positioned with horizontal (Image Left) and vertical (Image Top) offsets. To write a decoded interlaced line into the canvas buffer, the decoder calculates the memory pointer for the start of the target row:

\[\text{Row Address} = \text{Base Pointer} + \left( (\text{Image Top} + \text{Current Row}) \times \text{Stride} \right) + (\text{Image Left} \times \text{Bytes Per Pixel})\]

As the LZW decompressor outputs pixels for a line:

1. The decoder fills a temporary line buffer or writes directly to the calculated Row Address.
2. The Current Row counter increments by the current pass step value (8, 4, or 2).
3. If Current Row meets or exceeds the sub-frame height, the decoder advances to the next pass and resets Current Row to that pass's starting index.

By treating the stride as a fixed multiplier and updating the row index according to the interlacing pass schedule, the decoder unpacks the interlaced stream directly into a single coherent canvas buffer without secondary reorganization passes.