GIF Frame Extractor — Kotlin source

// GIF Frame Extractor — decode a GIF byte stream into indexed frames.
//
// Language: Kotlin (JVM), standard library only
// CosmoDev polyglot showcase port of the `gif-frame-extractor` tool.
// Ported from src/lib/gif-decode.ts — display source, part of CosmoDev's
// polyglot tool pages.
//
// A from-scratch GIF87a/89a parser: signature + logical screen descriptor
// (canvas size, global color table), extension blocks (frame delay,
// transparency, NETSCAPE loop count), and LZW image data decompressed to
// palette indices — interlaced frames reordered to natural row order.
// Malformed input returns null (same contract as the TS reference).

// --- Result types ----------------------------------------------------------

/** One decoded image: a rect on the canvas plus palette-index data. */
class GifFrame(
    val x: Int, val y: Int, val width: Int, val height: Int,
    /** RGB triplets; null = use the global color table. */
    val palette: ByteArray?,
    /** Pixel indices in natural row order. */
    val indices: ByteArray,
    val delayMs: Int,
    val transparentIndex: Int, // -1 = opaque (no transparent palette entry).
    val disposal: Int,
)

/** Whole-file result: screen size, frames, palettes, loop count. */
class GifResult(
    val width: Int, val height: Int, // Logical screen size.
    val frames: List<GifFrame>,
    val globalPalette: ByteArray?,
    /** NETSCAPE loop; 0 = forever, null when absent. */
    val loopCount: Int?,
)

// --- GIF LZW decompression -------------------------------------------------

/** Read one code LSB-first; returns EOI on truncation, like the TS decoder. */
private fun readCode(data: ByteArray, bitPos: IntArray, codeSize: Int, eoiCode: Int): Int {
    if ((bitPos[0] + codeSize) ushr 3 > data.size) return eoiCode
    var code = 0
    for (i in 0 until codeSize) {
        val byteIdx = (bitPos[0] + i) ushr 3
        if (byteIdx >= data.size) return eoiCode
        code = code or (((data[byteIdx].toInt() ushr ((bitPos[0] + i) and 7)) and 1) shl i)
    }
    bitPos[0] += codeSize
    return code
}

/** Emit a code's chain; returns the chain's FIRST byte (needed for KwKwK). */
private fun emitChain(
    code: Int, prefix: IntArray, suffix: IntArray, out: MutableList<Int>,
): Int {
    val stack = IntArray(4096)
    var n = 0
    var c = code
    while (c >= 0) { stack[n++] = suffix[c]; c = prefix[c] }
    for (i in n - 1 downTo 0) out.add(stack[i])
    return stack[n - 1]
}

/** minCodeSize 2-8, clear-code resets, growing codes — same contract as TS. */
fun lzwDecode(minCodeSize: Int, data: ByteArray): ByteArray {
    val clearCode = 1 shl minCodeSize
    val eoiCode = clearCode + 1
    var codeSize = minCodeSize + 1
    var nextCode = eoiCode + 1
    // Dictionary as (prefix, suffix, first-byte) triples, reset per clear.
    val prefix = IntArray(4096)
    val suffix = IntArray(4096)
    val first = IntArray(4096)
    val out = mutableListOf<Int>()
    val bitPos = intArrayOf(0) // One-slot array — the TS closure's mutable pos.
    var prev = -1
    while (true) {
        val code = readCode(data, bitPos, codeSize, eoiCode)
        if (code == eoiCode) break
        if (code == clearCode) {
            for (i in 0 until clearCode) { prefix[i] = -1; suffix[i] = i; first[i] = i }
            nextCode = eoiCode + 1; codeSize = minCodeSize + 1
            prev = -1
            continue
        }
        if (prev == -1) {
            if (code >= clearCode) break // First code after clear is a literal.
            emitChain(code, prefix, suffix, out)
            prev = code
            continue
        }
        if (code > nextCode) break // Invalid — stop like browsers do.
        // KwKwK: a code one ahead of the dictionary is prev + first(prev).
        val emittedFirst =
            if (code == nextCode) {
                emitChain(prev, prefix, suffix, out)
                out.add(first[prev])
                first[prev]
            } else {
                emitChain(code, prefix, suffix, out)
            }
        if (nextCode < 4096) { // Table full: TS silently no-ops this write.
            prefix[nextCode] = prev
            suffix[nextCode] = emittedFirst
            first[nextCode] = first[prev]
            nextCode++
            if (nextCode == (1 shl codeSize) && codeSize < 12) codeSize++
        }
        prev = code
    }
    return ByteArray(out.size) { out[it].toByte() }
}

// --- Interlace -------------------------------------------------------------

/** Reorder interlaced rows into natural order; identity for short frames. */
fun deInterlace(indices: ByteArray, width: Int, height: Int): ByteArray {
    if (height < 4 || width == 0) return indices
    val out = ByteArray(indices.size)
    var src = 0 // Stored pass-by-pass: four passes, starts/steps below.
    for ((start, step) in listOf(0 to 8, 4 to 8, 2 to 4, 1 to 2)) {
        var row = start
        while (row < height) {
            System.arraycopy(indices, src, out, row * width, width)
            src += width
            row += step
        }
    }
    return out
}

// --- Whole-GIF parse ---------------------------------------------------------

private fun le16(b: ByteArray, p: Int) = (b[p].toInt() and 0xff) or ((b[p + 1].toInt() and 0xff) shl 8)

/** Concatenate a sub-block chain; null on truncation. pos[0] advances. */
private fun readSubBlocks(b: ByteArray, pos: IntArray): ByteArray? {
    val chunks = ArrayList<ByteArray>()
    var total = 0
    while (true) {
        if (pos[0] >= b.size) return null
        val size = b[pos[0]++].toInt() and 0xff
        if (size == 0) break // Terminator ends the chain.
        if (pos[0] + size > b.size) return null
        chunks.add(b.copyOfRange(pos[0], pos[0] + size))
        total += size
        pos[0] += size
    }
    val out = ByteArray(total)
    var offset = 0
    for (c in chunks) { System.arraycopy(c, 0, out, offset, c.size); offset += c.size }
    return out
}

/** Parse signature, screen descriptor, extensions, and all frames. */
fun decodeGif(bytes: ByteArray): GifResult? {
    if (bytes.size < 13) return null
    val magic = String(bytes, 0, 6, Charsets.US_ASCII)
    if (magic != "GIF87a" && magic != "GIF89a") return null
    // Logical screen descriptor: canvas size, flags, optional global palette.
    val pos = intArrayOf(6)
    val width = le16(bytes, pos[0])
    val height = le16(bytes, pos[0] + 2)
    val packed = bytes[pos[0] + 4].toInt() and 0xff
    pos[0] += 7 // Skip bg color + aspect ratio.
    var globalPalette: ByteArray? = null
    if (packed and 0x80 != 0) {
        val n = (2 shl (packed and 7)) * 3
        if (pos[0] + n > bytes.size) return null
        globalPalette = bytes.copyOfRange(pos[0], pos[0] + n)
        pos[0] += n
    }
    val frames = ArrayList<GifFrame>()
    var loopCount: Int? = null // Absent until a NETSCAPE block says otherwise.
    var delayMs = 0
    var transparentIndex = -1
    var disposal = 0

    while (true) {
        if (pos[0] >= bytes.size) return null
        val block = bytes[pos[0]++].toInt() and 0xff
        if (block == 0x3b) break // trailer
        if (block == 0x21) { // Extension: graphic control / NETSCAPE / skip.
            if (pos[0] >= bytes.size) return null
            when (val label = bytes[pos[0]++].toInt() and 0xff) {
                0xf9 -> {
                    val gce = readSubBlocks(bytes, pos) ?: return null
                    if (gce.size < 4) return null
                    disposal = (gce[0].toInt() ushr 2) and 7
                    delayMs = le16(gce, 1) * 10
                    transparentIndex = if (gce[0].toInt() and 1 != 0) gce[3].toInt() and 0xff else -1
                }
                0xff -> {
                    val app = readSubBlocks(bytes, pos)
                    // Concatenated: 11-byte name, then id 1 + loop lo/hi.
                    if (app != null && app.size >= 14 && app[11].toInt() == 1 &&
                        String(app, 0, 11, Charsets.US_ASCII) == "NETSCAPE2.0"
                    ) {
                        loopCount = le16(app, 12)
                    }
                }
                else -> if (readSubBlocks(bytes, pos) == null) return null
            }
            continue
        }
        if (block == 0x2c) { // Image descriptor: rect, local palette, LZW data.
            if (pos[0] + 9 > bytes.size) return null
            val x = le16(bytes, pos[0])
            val y = le16(bytes, pos[0] + 2)
            val w = le16(bytes, pos[0] + 4)
            val h = le16(bytes, pos[0] + 6)
            val ip = bytes[pos[0] + 8].toInt() and 0xff
            pos[0] += 9 // Descriptor is 9 bytes: x, y, w, h, packed flags.
            var palette: ByteArray? = null
            if (ip and 0x80 != 0) {
                val n = (2 shl (ip and 7)) * 3
                if (pos[0] + n > bytes.size) return null
                palette = bytes.copyOfRange(pos[0], pos[0] + n)
                pos[0] += n
            }
            if (pos[0] >= bytes.size) return null
            val minCodeSize = bytes[pos[0]++].toInt() and 0xff
            // LZW payload must be a complete sub-block chain.
            val data = readSubBlocks(bytes, pos) ?: return null
            var indices = lzwDecode(minCodeSize, data)
            if (ip and 0x40 != 0) indices = deInterlace(indices, w, h)
            frames.add(GifFrame(x, y, w, h, palette, indices, delayMs, transparentIndex, disposal))
            delayMs = 0; transparentIndex = -1; disposal = 0
            continue
        }
        return null // Unknown block type — bail.
    }
    return GifResult(width, height, frames, globalPalette, loopCount)
}

// 2×1 GIF89a: 2-color global palette (red, blue), one frame, pixels [0,1].
fun main() {
    val gif = byteArrayOf(
        'G'.code.toByte(), 'I'.code.toByte(), 'F'.code.toByte(),
        '8'.code.toByte(), '9'.code.toByte(), 'a'.code.toByte(),
        0x02, 0x00, 0x01, 0x00, 0x80.toByte(), 0x00, 0x00, // LSD: 2×1, GCT
        0xff.toByte(), 0x00, 0x00, 0x00, 0x00, 0xff.toByte(), // GCT: red, blue
        0x2c,                                               // image descriptor
        0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x01, 0x00, 0x00,
        0x02,                                               // LZW min code size
        0x02, 0x44, 0x0a, 0x00,                             // sub-block + term.
        0x3b                                                // trailer
    )
    val res = decodeGif(gif) ?: run {
        System.err.println("malformed GIF")
        return
    }
    println("${res.width}x${res.height}, ${res.frames.size} frame(s), loop=${res.loopCount ?: "∞"}")
    res.frames.forEachIndexed { i, f ->
        val idx = f.indices.joinToString(", ") { (it.toInt() and 0xff).toString() }
        println("frame $i: ${f.width}x${f.height} at (${f.x},${f.y}), delay ${f.delayMs}ms, indices [$idx]")
    }
}