Video to GIF Converter — Kotlin source

// Video to GIF Converter — a pure GIF89a encoder core.
//
// Language: Kotlin 1.9+ (JVM), standard library only.
// Source:   CosmoDev polyglot showcase port of the `video-to-gif` tool —
//           the same encoder ships as the Go CLI twin. Ported from
//           src/lib/gif-encode.ts (the canonical TypeScript implementation).
// License:  display source — part of CosmoDev's polyglot tool pages.
//
// One shared palette is median-cut quantized from a down-sampled mix of all
// frames, every frame is mapped onto it (exact-match cache, else nearest
// RGB), and the index stream is LZW-compressed with the GIF variant of the
// algorithm — codes packed LSB-first, width growing one step behind the
// dictionary. The bit accumulator uses a Long: JS gets away with a number
// there because its doubles hold 53 bits, but Kotlin Int would silently
// truncate at 32 and corrupt wide codes.
//
// Run: kotlinc kotlin.kt -include-runtime -d gif.jar && java -jar gif.jar

/** One frame: raw RGBA pixels plus its delay. */
data class GifFrameInput(
    val width: Int,
    val height: Int,
    val rgba: ByteArray, // RGBA, 4 bytes/pixel, top-left origin
    val delayMs: Int,    // stored in the file as centiseconds
)

/** One dominant color: averaged RGB plus the pixel count it represents. */
data class Swatch(val r: Int, val g: Int, val b: Int, val population: Int)

private class Pixel(val r: Int, val g: Int, val b: Int)

/** Per-channel spread of a pixel bucket. */
private class Bounds(val r: Int, val g: Int, val b: Int)

private fun bounds(bucket: List<Pixel>): Bounds {
    var minR = 255; var maxR = 0; var minG = 255; var maxG = 0; var minB = 255; var maxB = 0
    for (p in 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 Bounds(maxR - minR, maxG - minG, maxB - minB)
}

/** Split a bucket at the median of its widest channel (stable, deterministic). */
private fun splitBucket(bucket: List<Pixel>): Pair<List<Pixel>, List<Pixel>> {
    val b = bounds(bucket)
    val channel = when {
        b.g > b.r && b.g >= b.b -> 1
        b.b > b.r && b.b > b.g -> 2
        else -> 0
    }
    val sorted = bucket.sortedBy { when (channel) { 0 -> it.r; 1 -> it.g; else -> it.b } }
    val mid = sorted.size / 2
    return sorted.subList(0, mid).toList() to sorted.subList(mid, sorted.size).toList()
}

private fun avg(bucket: List<Pixel>, c: (Pixel) -> Int): Int =
    Math.round(bucket.sumOf(c).toDouble() / bucket.size).toInt()

/** Median-cut quantization: split the widest-range bucket until maxColors. */
fun extractPalette(rgba: ByteArray, maxColors: Int = 8): List<Swatch> {
    val total = rgba.size / 4
    val pixels = ArrayList<Pixel>(total)
    val stride = maxOf(1, total / 16384) // bounded samples
    var i = 0
    while (i < total) {
        val o = i * 4
        // Trap: JVM bytes are signed — 0xff alpha is -1, so mask before compare.
        if ((rgba[o + 3].toInt() and 0xff) > 0) { // skip transparent
            pixels.add(Pixel(rgba[o].toInt() and 0xff, rgba[o + 1].toInt() and 0xff, rgba[o + 2].toInt() and 0xff))
        }
        i += stride
    }
    if (pixels.isEmpty()) return emptyList()

    val buckets = ArrayList<List<Pixel>>(maxColors)
    buckets.add(pixels)
    while (buckets.size < maxColors) {
        var bestIdx = -1
        var bestRange = 1 // range 1 (duplicates only) never splits
        for (idx in buckets.indices) {
            val b = bounds(buckets[idx])
            val range = maxOf(b.r, b.g, b.b)
            if (range > bestRange) { bestRange = range; bestIdx = idx }
        }
        if (bestIdx == -1) break
        val (low, high) = splitBucket(buckets.removeAt(bestIdx))
        buckets.add(low)
        buckets.add(high)
    }

    return buckets
        .filter { it.isNotEmpty() }
        .map { b -> Swatch(avg(b) { it.r }, avg(b) { it.g }, avg(b) { it.b }, b.size) }
        .sortedByDescending { it.population } // populous colors get low indices
}

/** Map RGBA pixels to palette indices: exact-match cache, else nearest RGB. */
fun mapToPalette(rgba: ByteArray, palette: List<Swatch>): ByteArray {
    val cache = HashMap<Int, Int>()
    val indices = ByteArray(rgba.size / 4)
    for (i in indices.indices) {
        val o = i * 4
        val r = rgba[o].toInt() and 0xff
        val g = rgba[o + 1].toInt() and 0xff
        val b = rgba[o + 2].toInt() and 0xff
        val key = (r shl 16) or (g shl 8) or b
        val cached = cache[key]
        if (cached != null) { indices[i] = cached.toByte(); continue }
        var best = 0
        var bestDist = Int.MAX_VALUE
        for (p in palette.indices) {
            val dr = r - palette[p].r; val dg = g - palette[p].g; val db = b - palette[p].b
            val dist = dr * dr + dg * dg + db * db
            if (dist < bestDist) { bestDist = dist; best = p }
        }
        cache[key] = best
        indices[i] = best.toByte()
    }
    return indices
}

/** LZW compression (GIF variant): pack codes LSB-first at the current width. */
fun lzwEncode(minCodeSize: Int, indices: ByteArray): ByteArray {
    val clearCode = 1 shl minCodeSize
    val eoiCode = clearCode + 1
    var codeSize = minCodeSize + 1
    var nextCode = eoiCode + 1
    var dict = HashMap<Long, Int>() // (prefixCode shl 8) or byte -> code

    val out = ByteArrayList()
    var bitBuffer = 0L
    var bitCount = 0
    fun emit(code: Int) {
        bitBuffer = bitBuffer or (code.toLong() shl bitCount)
        bitCount += codeSize
        while (bitCount >= 8) { out.add((bitBuffer and 0xff).toInt().toByte()); bitBuffer = bitBuffer ushr 8; bitCount -= 8 }
    }

    emit(clearCode)
    if (indices.isEmpty()) { emit(eoiCode); if (bitCount > 0) out.add((bitBuffer and 0xff).toInt().toByte()); return out.toByteArray() }

    var w = indices[0].toInt() and 0xff
    for (i in 1 until indices.size) {
        val c = indices[i].toInt() and 0xff
        val key = (w.toLong() shl 8) or c.toLong()
        val found = dict[key]
        if (found != null) { w = found; continue }
        emit(w)
        dict[key] = nextCode++
        // Width lags one entry behind the dictionary: grow after adding 2^codeSize.
        if (nextCode - 1 == 1 shl codeSize && codeSize < 12) codeSize++
        w = c
        if (nextCode >= 4096) { emit(clearCode); dict = HashMap(); nextCode = eoiCode + 1; codeSize = minCodeSize + 1 } // full — reset
    }
    emit(w); emit(eoiCode)
    if (bitCount > 0) out.add((bitBuffer and 0xff).toInt().toByte())
    return out.toByteArray()
}

/** Tiny growable byte sink — java.io.ByteArrayOutputStream would also do. */
private class ByteArrayList {
    private var data = ByteArray(256)
    private var len = 0
    fun add(b: Byte) {
        if (len == data.size) data = data.copyOf(data.size * 2)
        data[len++] = b
    }
    fun toByteArray() = data.copyOf(len)
}

private fun pushAscii(out: ByteArrayList, text: String) {
    for (ch in text) out.add(ch.code.toByte())
}

private fun u16le(n: Int): ByteArray = byteArrayOf((n and 0xff).toByte(), ((n shr 8) and 0xff).toByte())

fun encodeGif(frames: List<GifFrameInput>, maxColors: Int = 128): ByteArray {
    if (frames.isEmpty()) return ByteArray(0)

    // One shared palette, quantized from a down-sampled mix of all frames.
    val mixed = ArrayList<Byte>(frames.size * 4096 * 4)
    for (f in frames) {
        val total = f.rgba.size / 4
        val stride = maxOf(1, total / 4096)
        var i = 0
        while (i < total) {
            val o = i * 4
            mixed.add(f.rgba[o]); mixed.add(f.rgba[o + 1]); mixed.add(f.rgba[o + 2]); mixed.add(f.rgba[o + 3])
            i += stride
        }
    }
    val palette = extractPalette(mixed.toByteArray(), minOf(maxColors, 256))
    if (palette.isEmpty()) return ByteArray(0)

    // Palette table padded to a power of two (min 2 entries).
    var tableBits = 1
    while (1 shl tableBits < palette.size) tableBits++

    val out = ByteArrayList()
    pushAscii(out, "GIF89a")
    for (b in u16le(frames[0].width)) out.add(b)
    for (b in u16le(frames[0].height)) out.add(b)
    out.add(((0x80 or (tableBits - 1)).toByte())); out.add(0); out.add(0) // GCT flag + size; bg; aspect
    for (i in 0 until (1 shl tableBits)) {
        val s = palette.getOrNull(i)
        out.add((s?.r ?: 0).toByte()); out.add((s?.g ?: 0).toByte()); out.add((s?.b ?: 0).toByte())
    }
    out.add(0x21); out.add(0xff.toByte()); out.add(0x0b) // NETSCAPE loop-forever extension
    pushAscii(out, "NETSCAPE2.0")
    out.add(0x03); out.add(0x01); out.add(0); out.add(0); out.add(0)

    val minCodeSize = maxOf(2, tableBits)
    for (frame in frames) {
        val cs = (Math.round(frame.delayMs / 10.0).toInt()).coerceIn(0, 0xffff) // centiseconds
        out.add(0x21); out.add(0xf9.toByte()); out.add(0x04); out.add(0) // graphic control ext
        for (b in u16le(cs)) out.add(b)
        out.add(0); out.add(0)
        out.add(0x2c)
        for (b in u16le(0)) out.add(b)
        for (b in u16le(0)) out.add(b)
        for (b in u16le(frame.width)) out.add(b)
        for (b in u16le(frame.height)) out.add(b)
        out.add(0) // no local color table, no interlace
        val data = lzwEncode(minCodeSize, mapToPalette(frame.rgba, palette))
        out.add(minCodeSize.toByte())
        var i = 0
        while (i < data.size) { // sub-blocked every 255 bytes
            val chunk = if (i + 255 <= data.size) data.copyOfRange(i, i + 255) else data.copyOfRange(i, data.size)
            out.add(chunk.size.toByte())
            for (b in chunk) out.add(b)
            i += 255
        }
        out.add(0) // block terminator
    }
    out.add(0x3b) // trailer
    return out.toByteArray()
}

// Usage: encodeGif(frames) -> GIF89a bytes — one shared palette, one image block per frame.