GIF Frame Extractor — Go source

// Package gifdecode is the Go twin of CosmoDev's src/lib/gif-decode.ts
// (dual source: the web lib is TypeScript, the CLI lib is Go — kept in
// lock-step). Pure GIF87a/89a decoder: parses the byte stream and
// LZW-decodes every frame to indexed pixels. Deterministic and
// side-effect free; truncated or malformed input returns nil instead of
// panicking.
//
// The table-driven tests in gif-frame-extractor_test.go share vectors
// with src/lib/gif-decode.test.ts so the two implementations are held to
// the same contract.
package gifdecode

// GifFrame mirrors the TS GifFrame interface.
type GifFrame struct {
	X, Y, Width, Height int
	// Palette is the RGB-triplet override for this frame; nil = use GlobalPalette.
	Palette []byte
	// Indices holds the pixel indices in natural row order (de-interlaced).
	Indices []byte
	// DelayMs is the frame delay in milliseconds.
	DelayMs int
	// TransparentIndex is the transparent palette index, or -1.
	TransparentIndex int
	// Disposal is the disposal method 0-7 (0/1 = keep, 2 = restore bg, 3 = restore previous).
	Disposal int
}

// GifResult mirrors the TS GifResult interface.
type GifResult struct {
	Width, Height int
	Frames        []GifFrame
	// GlobalPalette is the global color table (RGB triplets); nil when absent.
	GlobalPalette []byte
	// LoopCount mirrors the TS loopCount: 0 means loop forever. The TS lib
	// uses Infinity when the NETSCAPE extension is absent (play-once
	// semantics differ per consumer); Go has no integer Infinity, so absence
	// is represented by LoopCountAbsent.
	LoopCount int
}

// LoopCountAbsent marks a GIF with no NETSCAPE loop-count extension (TS: Infinity).
const LoopCountAbsent = -1

// LzwDecode is GIF LZW decompression — minCodeSize 2-8, clear-code resets,
// growing code width, and the KwKwK case (code one ahead of the dictionary).
// Mirrors lzwDecode() in src/lib/gif-decode.ts exactly.
func LzwDecode(minCodeSize int, data []byte) []byte {
	clearCode := 1 << minCodeSize
	eoiCode := clearCode + 1
	codeSize := minCodeSize + 1
	nextCode := eoiCode + 1

	// Dictionary as (prefix, suffix, first-byte) triples — reset per clear code.
	var prefix [4096]int32
	var suffix, first [4096]byte
	resetDict := func() {
		for i := 0; i < clearCode; i++ {
			prefix[i] = -1
			suffix[i] = byte(i)
			first[i] = byte(i)
		}
		nextCode = eoiCode + 1
		codeSize = minCodeSize + 1
	}
	resetDict()

	out := make([]byte, 0, len(data)*2)
	var stack []byte
	// emit writes a code's chain and returns the chain's FIRST byte (for KwKwK).
	emit := func(code int) byte {
		stack = stack[:0]
		for c := int32(code); c >= 0; c = prefix[c] {
			stack = append(stack, suffix[c])
		}
		// The stack was collected last→first; reverse it into the output.
		for i := len(stack) - 1; i >= 0; i-- {
			out = append(out, stack[i])
		}
		return stack[len(stack)-1]
	}

	bitPos := 0
	readCode := func() int {
		if (bitPos+codeSize)>>3 > len(data) {
			return eoiCode
		}
		code := 0
		for i := 0; i < codeSize; i++ {
			byteIdx := (bitPos + i) >> 3
			if byteIdx >= len(data) {
				return eoiCode
			}
			bit := (data[byteIdx] >> ((bitPos + i) & 7)) & 1
			code |= int(bit) << i
		}
		bitPos += codeSize
		return code
	}

	prev := -1
	for {
		code := readCode()
		if code == eoiCode {
			break
		}
		if code == clearCode {
			resetDict()
			prev = -1
			continue
		}
		if prev == -1 {
			if code >= clearCode {
				break // First code after clear must be a literal.
			}
			emit(code)
			prev = code
			continue
		}
		if code > nextCode {
			break // Invalid — stop like browsers do.
		}
		// KwKwK: code one ahead of the dictionary decodes to prev + first(prev).
		var emittedFirst byte
		if code == nextCode {
			emit(prev)
			out = append(out, first[prev])
			emittedFirst = first[prev]
		} else {
			emittedFirst = emit(code)
		}
		prefix[nextCode] = int32(prev)
		suffix[nextCode] = emittedFirst
		first[nextCode] = first[prev]
		nextCode++
		prev = code
		if nextCode == 1<<codeSize && codeSize < 12 {
			codeSize++
		}
	}
	return out
}

// DeInterlace reorders interlaced rows into natural order. It is the
// identity for progressive rows (height < 4 or zero width — the input
// slice is returned unchanged, like the TS lib).
// Mirrors deInterlace() in src/lib/gif-decode.ts exactly.
func DeInterlace(indices []byte, width, height int) []byte {
	if height < 4 || width == 0 {
		return indices
	}
	out := make([]byte, len(indices))
	passes := []struct{ start, step int }{
		{0, 8},
		{4, 8},
		{2, 4},
		{1, 2},
	}
	src := 0
	for _, pass := range passes {
		for row := pass.start; row < height; row += pass.step {
			end := src + width
			if end > len(indices) {
				end = len(indices) // clamp: LZW output may be short (treated as EOI)
			}
			copy(out[row*width:], indices[src:end])
			src += width
			if src > len(indices) {
				return out // no stored rows left
			}
		}
	}
	return out
}

// DecodeGif parses a GIF87a/89a byte stream. It returns nil for
// truncated or malformed input (the TS lib returns null).
// Mirrors decodeGif() in src/lib/gif-decode.ts exactly: header/LSD/GCT
// parse, sub-block concatenation, NETSCAPE loop count (sub-block id 1
// after the 11-byte name), GCE (delay x10 ms, transparency flag/index,
// disposal), image descriptors with local color tables, LZW + 4-pass
// de-interlace.
func DecodeGif(bytes []byte) *GifResult {
	if len(bytes) < 13 {
		return nil
	}
	magic := string(bytes[0:6])
	if magic != "GIF87a" && magic != "GIF89a" {
		return nil
	}

	pos := 6
	width := int(bytes[pos]) | int(bytes[pos+1])<<8
	height := int(bytes[pos+2]) | int(bytes[pos+3])<<8
	packed := bytes[pos+4]
	pos += 7

	var globalPalette []byte
	if packed&0x80 != 0 {
		entries := 2 << (packed & 7)
		if pos+entries*3 > len(bytes) {
			return nil
		}
		globalPalette = append([]byte(nil), bytes[pos:pos+entries*3]...)
		pos += entries * 3
	}

	res := &GifResult{
		Width:          width,
		Height:         height,
		GlobalPalette:  globalPalette,
		LoopCount:      LoopCountAbsent,
	}
	delayMs := 0
	transparentIndex := -1
	disposal := 0

	// readSubBlocks concatenates data sub-blocks until the 0x00 terminator.
	// It returns nil when the stream ends mid-block (truncation).
	readSubBlocks := func() []byte {
		var chunks [][]byte
		for {
			if pos >= len(bytes) {
				return nil
			}
			size := int(bytes[pos])
			pos++
			if size == 0 {
				break
			}
			if pos+size > len(bytes) {
				return nil
			}
			chunks = append(chunks, bytes[pos:pos+size])
			pos += size
		}
		total := 0
		for _, c := range chunks {
			total += len(c)
		}
		out := make([]byte, 0, total)
		for _, c := range chunks {
			out = append(out, c...)
		}
		return out
	}

loop:
	for {
		if pos >= len(bytes) {
			return nil
		}
		block := bytes[pos]
		pos++

		switch block {
		case 0x3b: // trailer
			break loop

		case 0x21: // Extension
			if pos >= len(bytes) {
				return nil
			}
			label := bytes[pos]
			pos++
			switch label {
			case 0xf9: // Graphic control extension
				gce := readSubBlocks()
				if len(gce) < 4 {
					return nil
				}
				disposal = int(gce[0]>>2) & 7
				delayMs = (int(gce[1]) | int(gce[2])<<8) * 10
				if gce[0]&1 == 1 {
					transparentIndex = int(gce[3])
				} else {
					transparentIndex = -1
				}
			case 0xff: // Application extension
				app := readSubBlocks()
				// Sub-block contents concatenated: the 11-byte name, then id 1 + loop lo/hi.
				if len(app) >= 14 && string(app[0:11]) == "NETSCAPE2.0" && app[11] == 1 {
					res.LoopCount = int(app[12]) | int(app[13])<<8
				}
			default: // Comment / plain text / unknown — skip the sub-blocks.
				if readSubBlocks() == nil {
					return nil
				}
			}

		case 0x2c: // Image descriptor
			if pos+9 > len(bytes) {
				return nil
			}
			x := int(bytes[pos]) | int(bytes[pos+1])<<8
			y := int(bytes[pos+2]) | int(bytes[pos+3])<<8
			w := int(bytes[pos+4]) | int(bytes[pos+5])<<8
			h := int(bytes[pos+6]) | int(bytes[pos+7])<<8
			ip := bytes[pos+8]
			pos += 9
			var palette []byte
			if ip&0x80 != 0 {
				entries := 2 << (ip & 7)
				if pos+entries*3 > len(bytes) {
					return nil
				}
				palette = append([]byte(nil), bytes[pos:pos+entries*3]...)
				pos += entries * 3
			}
			if pos >= len(bytes) {
				return nil
			}
			minCodeSize := int(bytes[pos])
			pos++
			data := readSubBlocks()
			if data == nil {
				return nil
			}
			indices := LzwDecode(minCodeSize, data)
			final := indices
			if ip&0x40 != 0 {
				final = DeInterlace(indices, w, h)
			}
			res.Frames = append(res.Frames, GifFrame{
				X:                x,
				Y:                y,
				Width:            w,
				Height:           h,
				Palette:          palette,
				Indices:          final,
				DelayMs:          delayMs,
				TransparentIndex: transparentIndex,
				Disposal:         disposal,
			})
			delayMs = 0
			transparentIndex = -1
			disposal = 0

		default:
			return nil // Unknown block type — bail.
		}
	}

	return res
}