Video to GIF Converter — Go source

// Package gifencode is the Go twin of CosmoDev's src/lib/gif-encode.ts
// (dual source: the web lib is TypeScript, the CLI lib is Go — kept in
// lock-step). Pure + deterministic, never panics. The tests in
// video-to-gif_test.go share vectors with src/lib/gif-encode.test.ts so the
// two implementations are held to the same contract.
//
// Assembly mirrors the TS lib exactly: one shared palette quantized by
// median-cut (inlined from src/lib/palette-extract.ts, the same way the
// palette twin ports it — no cross-package import) over a strided sample of
// every frame → GCT padded to a power of two → NETSCAPE2.0 loop-forever →
// per frame a GCE with centisecond delays and an LZW image block, sub-blocked
// at 255 bytes.
package gifencode

import (
	"math"
	"sort"
)

// FrameInput is one RGBA frame to encode (mirrors GifFrameInput).
type FrameInput struct {
	Width   int
	Height  int
	Rgba    []byte // 4 bytes per pixel, top-left origin
	DelayMs int    // stored as centiseconds
}

// defaultMaxColors mirrors the TS default (opts.maxColors ?? 128).
const defaultMaxColors = 128

// ---------------------------------------------------------------------------
// LZW compression (GIF variant)
// ---------------------------------------------------------------------------

// LzwEncode GIF-LZW-compresses index bytes (mirrors lzwEncode in
// gif-encode.ts): codes packed LSB-first at the current width. The encoder's
// dictionary runs one entry AHEAD of the decoder's (its add for (w,c) is only
// constructible on the decoder's NEXT read), so the code width grows one entry
// later — right after adding code 2^codeSize. At 4096 codes the dictionary
// resets mid-stream with a clear code, like other encoders do.
func LzwEncode(minCodeSize int, indices []byte) []byte {
	clearCode := 1 << minCodeSize
	eoiCode := clearCode + 1
	codeSize := minCodeSize + 1
	nextCode := eoiCode + 1

	// Dictionary: (prefixCode, byte) -> code, keyed numerically.
	dict := make(map[int]int)
	resetDict := func() {
		dict = make(map[int]int)
		nextCode = eoiCode + 1
		codeSize = minCodeSize + 1
	}
	resetDict()

	out := make([]byte, 0, len(indices)/2+8)
	var bitBuffer uint32
	var bitCount int
	emit := func(code int) {
		bitBuffer |= uint32(code) << uint(bitCount)
		bitCount += codeSize
		for bitCount >= 8 {
			out = append(out, byte(bitBuffer&0xff))
			bitBuffer >>= 8
			bitCount -= 8
		}
	}
	growIfDue := func() {
		// Grow AFTER adding code 2^codeSize — one entry later than the decoder.
		if nextCode-1 == 1<<codeSize && codeSize < 12 {
			codeSize++
		}
	}

	emit(clearCode)
	if len(indices) == 0 {
		emit(eoiCode)
		if bitCount > 0 {
			out = append(out, byte(bitBuffer&0xff))
		}
		return out
	}

	w := int(indices[0])
	for i := 1; i < len(indices); i++ {
		c := int(indices[i])
		key := (w << 8) | c
		if found, ok := dict[key]; ok {
			w = found
			continue
		}
		emit(w)
		dict[key] = nextCode
		nextCode++
		growIfDue()
		w = c
		if nextCode >= 4096 {
			// Dictionary full — reset like encoders do.
			emit(clearCode)
			resetDict()
			w = c
		}
	}
	emit(w)
	emit(eoiCode)
	if bitCount > 0 {
		out = append(out, byte(bitBuffer&0xff))
	}
	return out
}

// ---------------------------------------------------------------------------
// Palette extraction (median-cut, inlined from src/lib/palette-extract.ts)
// ---------------------------------------------------------------------------

// swatch mirrors palette-extract.ts Swatch.
type swatch struct {
	r, g, b    int
	population int
}

type rgbPixel struct{ r, g, b int }

// paletteMaxSamples mirrors MAX_SAMPLES: down-sample so large inputs
// quantize in bounded time.
const paletteMaxSamples = 16384

// extractPalette is median-cut quantization: split the widest-range bucket at
// the median of that channel, repeat. Stable ordering only — deterministic.
func extractPalette(rgba []byte, maxColors int) []swatch {
	total := len(rgba) / 4
	if total == 0 {
		return nil
	}

	pixels := make([]rgbPixel, 0, total)
	stride := max(total/paletteMaxSamples, 1)
	for i := 0; i < total; i += stride {
		o := i * 4
		if rgba[o+3] == 0 {
			continue // fully transparent samples are skipped
		}
		pixels = append(pixels, rgbPixel{int(rgba[o]), int(rgba[o+1]), int(rgba[o+2])})
	}
	if len(pixels) == 0 {
		return nil
	}

	buckets := [][]rgbPixel{pixels}
	for len(buckets) < maxColors {
		// Widest-range bucket with more than one distinct value wins the split.
		bestIdx := -1
		bestRange := 1 // Range 1 (exact duplicates only) never splits further.
		for i := range buckets {
			if rng := channelRange(buckets[i]); rng > bestRange {
				bestRange = rng
				bestIdx = i
			}
		}
		if bestIdx == -1 {
			break
		}
		bucket := buckets[bestIdx]
		buckets = append(buckets[:bestIdx], buckets[bestIdx+1:]...)
		left, right := splitBucket(bucket)
		buckets = append(buckets, left, right)
	}

	out := make([]swatch, 0, len(buckets))
	for _, bucket := range buckets {
		if len(bucket) == 0 {
			continue
		}
		var sr, sg, sb int
		for _, p := range bucket {
			sr += p.r
			sg += p.g
			sb += p.b
		}
		// Math.round of a non-negative mean, in integer arithmetic.
		n := len(bucket)
		out = append(out, swatch{
			r:          (sr + n/2) / n,
			g:          (sg + n/2) / n,
			b:          (sb + n/2) / n,
			population: n,
		})
	}
	// Population-descending, stable (ties keep bucket order) — like the TS
	// stable sort.
	sort.SliceStable(out, func(i, j int) bool { return out[i].population > out[j].population })
	return out
}

func channelRange(bucket []rgbPixel) int {
	minR, maxR := 255, 0
	minG, maxG := 255, 0
	minB, maxB := 255, 0
	for _, p := range bucket {
		if p.r < minR {
			minR = p.r
		}
		if p.r > maxR {
			maxR = p.r
		}
		if p.g < minG {
			minG = p.g
		}
		if p.g > maxG {
			maxG = p.g
		}
		if p.b < minB {
			minB = p.b
		}
		if p.b > maxB {
			maxB = p.b
		}
	}
	return max(max(maxR-minR, maxG-minG), maxB-minB)
}

func splitBucket(bucket []rgbPixel) (left, right []rgbPixel) {
	minR, maxR := 255, 0
	minG, maxG := 255, 0
	minB, maxB := 255, 0
	for _, p := range bucket {
		if p.r < minR {
			minR = p.r
		}
		if p.r > maxR {
			maxR = p.r
		}
		if p.g < minG {
			minG = p.g
		}
		if p.g > maxG {
			maxG = p.g
		}
		if p.b < minB {
			minB = p.b
		}
		if p.b > maxB {
			maxB = p.b
		}
	}
	// Channel with the widest range; r wins ties, then g (strict >, TS order).
	ch := 0 // 0=r 1=g 2=b
	best := maxR - minR
	if maxG-minG > best {
		ch = 1
		best = maxG - minG
	}
	if maxB-minB > best {
		ch = 2
	}

	sorted := make([]rgbPixel, len(bucket))
	copy(sorted, bucket)
	sort.SliceStable(sorted, func(i, j int) bool {
		switch ch {
		case 1:
			return sorted[i].g < sorted[j].g
		case 2:
			return sorted[i].b < sorted[j].b
		default:
			return sorted[i].r < sorted[j].r
		}
	})
	mid := len(sorted) / 2
	return sorted[:mid], sorted[mid:]
}

// ---------------------------------------------------------------------------
// Palette mapping
// ---------------------------------------------------------------------------

// mapToPalette maps RGBA to palette indices via an exact-color cache plus
// nearest RGB squared distance (mirrors mapToPalette in gif-encode.ts).
func mapToPalette(rgba []byte, palette []swatch) []byte {
	indices := make([]byte, len(rgba)/4)
	cache := make(map[int]int, 256)
	for i := range indices {
		o := i * 4
		key := int(rgba[o])<<16 | int(rgba[o+1])<<8 | int(rgba[o+2])
		idx, ok := cache[key]
		if !ok {
			best := 0
			bestDist := int(^uint(0) >> 1) // max int
			for p := range palette {
				dr := int(rgba[o]) - palette[p].r
				dg := int(rgba[o+1]) - palette[p].g
				db := int(rgba[o+2]) - palette[p].b
				dist := dr*dr + dg*dg + db*db
				if dist < bestDist {
					bestDist = dist
					best = p
				}
			}
			idx = best
			cache[key] = idx
		}
		indices[i] = byte(idx)
	}
	return indices
}

// ---------------------------------------------------------------------------
// Byte assembly
// ---------------------------------------------------------------------------

func appendU16LE(out []byte, n int) []byte {
	return append(out, byte(n&0xff), byte((n>>8)&0xff))
}

// EncodeGif quantizes frames onto one shared palette and assembles the GIF89a
// byte stream (mirrors encodeGif in gif-encode.ts). maxColors <= 0 means the
// default 128; values above 256 clamp to 256. No frames or no quantizable
// pixels (e.g. a zero-pixel frame) yield an empty result.
func EncodeGif(frames []FrameInput, maxColors int) []byte {
	if maxColors <= 0 {
		maxColors = defaultMaxColors
	}
	if maxColors > 256 {
		maxColors = 256
	}
	if len(frames) == 0 {
		return []byte{}
	}

	// One shared palette, quantized from a down-sampled mix of all frames.
	mixed := make([]byte, 0, 64)
	for _, f := range frames {
		total := len(f.Rgba) / 4
		stride := max(total/4096, 1)
		for i := 0; i < total; i += stride {
			o := i * 4
			mixed = append(mixed, f.Rgba[o], f.Rgba[o+1], f.Rgba[o+2], f.Rgba[o+3])
		}
	}
	palette := extractPalette(mixed, maxColors)
	if len(palette) == 0 {
		return []byte{}
	}

	// Palette table padded to a power of two (min 2 entries).
	tableBits := 1
	for 1<<tableBits < len(palette) {
		tableBits++
	}
	tableSize := 1 << tableBits

	out := make([]byte, 0, 1024)
	out = append(out, "GIF89a"...)
	out = appendU16LE(out, frames[0].Width)
	out = appendU16LE(out, frames[0].Height)
	out = append(out, byte(0x80|(tableBits-1)), 0, 0) // GCT flag + size; bg; aspect
	for i := range tableSize {
		if i < len(palette) {
			out = append(out, byte(palette[i].r), byte(palette[i].g), byte(palette[i].b))
		} else {
			out = append(out, 0, 0, 0)
		}
	}

	// NETSCAPE loop forever.
	out = append(out, 0x21, 0xff, 0x0b)
	out = append(out, "NETSCAPE2.0"...)
	out = append(out, 0x03, 0x01, 0x00, 0x00, 0x00)

	minCodeSize := max(tableBits, 2)
	for _, frame := range frames {
		// Graphic control extension: delay in centiseconds, no transparency.
		cs := min(max(int(math.Round(float64(frame.DelayMs)/10)), 0), 0xffff)
		out = append(out, 0x21, 0xf9, 0x04, 0x00)
		out = appendU16LE(out, cs)
		out = append(out, 0x00, 0x00)

		out = append(out, 0x2c)
		out = appendU16LE(out, 0)
		out = appendU16LE(out, 0)
		out = appendU16LE(out, frame.Width)
		out = appendU16LE(out, frame.Height)
		out = append(out, 0x00) // no LCT, no interlace

		indices := mapToPalette(frame.Rgba, palette)
		data := LzwEncode(minCodeSize, indices)
		out = append(out, byte(minCodeSize))
		for i := 0; i < len(data); i += 255 {
			end := min(i+255, len(data))
			chunk := data[i:end]
			out = append(out, byte(len(chunk)))
			out = append(out, chunk...)
		}
		out = append(out, 0x00) // block terminator
	}

	out = append(out, 0x3b) // trailer
	return out
}