GIF Frame Extractor — Swift source

// GIF Frame Extractor — decode a GIF byte stream into indexed frames.
//
// Language: Swift (5.9+), 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.
//
// Parses GIF87a/89a, LZW-decodes every frame to indexed pixels, and
// de-interlaces interlaced rows. Deterministic; truncated or malformed input
// returns nil instead of throwing — the TS lib's null-return convention.

struct GifFrame {
  let x: Int, y: Int, width: Int, height: Int
  /// Palette override for this frame (RGB triplets); nil = use global.
  let palette: [UInt8]?
  /// Pixel indices in natural row order (de-interlaced).
  let indices: [UInt8]
  let delayMs: Int
  /// Transparent palette index, or -1.
  let transparentIndex: Int
  /// Disposal method 0-7 (0/1 keep, 2 restore bg, 3 restore previous).
  let disposal: Int
}

struct Gif {
  let width: Int, height: Int
  let frames: [GifFrame]
  let globalPalette: [UInt8]?
  /// NETSCAPE loop count; nil when the extension is absent (play-once
  /// semantics differ per consumer — the TS lib surfaces Infinity there).
  let loopCount: Int?
}

/// GIF LZW decompression — minCodeSize 2-8, clear-code resets, growing codes.
/// Dictionary as (prefix, suffix) pairs; the KwKwK case re-emits the previous
/// chain's first byte, exactly like the TS emit().
func lzwDecode(minCodeSize: Int, data: [UInt8]) -> [UInt8]? {
  if minCodeSize < 2 || minCodeSize > 8 { return nil }
  let clearCode = 1 << minCodeSize
  let eoiCode = clearCode + 1

  var codeSize = minCodeSize + 1
  var nextCode = eoiCode + 1

  var prefix = [Int32](repeating: 0, count: 4096)
  var suffix = [UInt8](repeating: 0, count: 4096)

  func resetDict() {
    for i in 0..<clearCode {
      prefix[i] = -1
      suffix[i] = UInt8(i)
    }
    nextCode = eoiCode + 1
    codeSize = minCodeSize + 1
  }
  resetDict()

  var out: [UInt8] = []
  var bitPos = 0

  func readCode() -> Int {
    if (bitPos + codeSize) > data.count * 8 { return eoiCode }
    var code = 0
    for i in 0..<codeSize {
      let byteIdx = (bitPos + i) >> 3
      if byteIdx >= data.count { return eoiCode }
      let bit = (Int(data[byteIdx]) >> ((bitPos + i) & 7)) & 1
      code |= bit << i
    }
    bitPos += codeSize
    return code
  }

  func firstByte(of c: Int32) -> UInt8 {
    var cur = c
    while prefix[Int(cur)] >= 0 { cur = prefix[Int(cur)] }
    return suffix[Int(cur)]
  }

  var prev: Int32 = -1
  while true {
    let code = readCode()
    if code == eoiCode { break }
    if code == clearCode {
      resetDict()
      prev = -1
      continue
    }

    var stack: [UInt8] = []
    var chainFirst: UInt8
    if code >= nextCode {
      // KwKwK — code not yet defined: chain is prev + first(prev).
      if prev < 0 { return nil }
      chainFirst = firstByte(of: prev)
      var c: Int32 = prev
      while c >= 0 {
        stack.append(suffix[Int(c)])
        c = prefix[Int(c)]
      }
    } else {
      chainFirst = firstByte(of: Int32(code))
      var c: Int32 = Int32(code)
      while c >= 0 {
        stack.append(suffix[Int(c)])
        c = prefix[Int(c)]
      }
    }
    // Unwind in reverse = natural order.
    out.append(contentsOf: stack.reversed())

    // Add prev+first to the dictionary (the entry the KwKwK case used).
    if prev >= 0 && nextCode < 4096 {
      prefix[nextCode] = prev
      suffix[nextCode] = chainFirst
      nextCode += 1
    }
    prev = Int32(code)

    if nextCode == (1 << codeSize) && codeSize < 12 { codeSize += 1 }
  }
  return out
}

/// Decode a full GIF byte stream. Returns nil on bad signature or truncation.
func decodeGif(_ data: [UInt8]) -> Gif? {
  struct Reader {
    let data: [UInt8]
    var pos = 0
    mutating func u8() -> UInt8? {
      guard pos < data.count else { return nil }
      defer { pos += 1 }
      return data[pos]
    }
    mutating func u16le() -> Int? {
      guard let lo = u8(), let hi = u8() else { return nil }
      return Int(lo) | (Int(hi) << 8)
    }
    mutating func bytes(_ n: Int) -> [UInt8]? {
      guard pos + n <= data.count else { return nil }
      defer { pos += n }
      return Array(data[pos..<pos + n])
    }
  }

  var r = Reader(data: data)
  guard let sig = r.bytes(6), Array(sig[0..<3]) == Array("GIF".utf8) else { return nil }

  guard let width = r.u16le(), let height = r.u16le(),
        let flags = r.u8(), r.u8() != nil else { return nil }  // flags + bg index
  let gctSize = 2 << Int(flags & 0x07)

  var globalPalette: [UInt8]? = nil
  if flags & 0x80 != 0 {
    guard let raw = r.bytes(gctSize * 3) else { return nil }
    globalPalette = raw
  }

  var frames: [GifFrame] = []
  var loopCount: Int? = nil
  // Per-frame graphic-control state, applied to the NEXT image descriptor.
  var delayMs = 0
  var transparentIndex = -1
  var disposal = 0

  loop: while let b = r.u8() {
    switch b {
    case 0x3B:  // trailer
      break loop
    case 0x21:  // extension
      guard let label = r.u8() else { return nil }
      if label == 0xF9 {  // graphic control
        guard let len = r.u8(), let blk = r.bytes(Int(len)), blk.count >= 4 else { return nil }
        disposal = Int((blk[0] >> 2) & 0x07)
        delayMs = Int(blk[1]) | (Int(blk[2]) << 8)
        transparentIndex = blk[0] & 1 != 0 ? Int(blk[3]) : -1
      } else if label == 0xFF {  // application — NETSCAPE2.0 loop
        guard let len = r.u8(), let ident = r.bytes(Int(len)) else { return nil }
        if ident == Array("NETSCAPE2.0".utf8) {
          if let n = r.u8(), n == 3, r.u8() != nil, let lc = r.u16le() {
            loopCount = lc
          }
        }
      }
      // Skip any remaining sub-blocks of this extension.
      while let n = r.u8(), n > 0 {
        guard r.bytes(Int(n)) != nil else { return nil }
      }
    case 0x2C:  // image descriptor
      guard let ix = r.u16le(), let iy = r.u16le(),
            let iw = r.u16le(), let ih = r.u16le(),
            let iflags = r.u8() else { return nil }
      let lctSize = 2 << Int(iflags & 0x07)

      var palette: [UInt8]? = nil
      if iflags & 0x80 != 0 {
        guard let raw = r.bytes(lctSize * 3) else { return nil }
        palette = raw
      }

      guard let minCodeSize = r.u8() else { return nil }
      // Concatenate the data sub-blocks, then LZW-decode.
      var lzw: [UInt8] = []
      while let n = r.u8(), n > 0 {
        guard let chunk = r.bytes(Int(n)) else { return nil }
        lzw.append(contentsOf: chunk)
      }
      guard var indices = lzwDecode(minCodeSize: Int(minCodeSize), data: lzw) else { return nil }

      // De-interlace: rows arrive as passes 0,8 / 4,8 / 2,4 / 1,2.
      if iflags & 0x40 != 0 && iw > 0 && ih > 0 {
        var deint = [UInt8](repeating: 0, count: iw * ih)
        let strides = [(0, 8), (4, 8), (2, 4), (1, 2)]
        var srcRow = 0
        for (start, step) in strides {
          var y = start
          while y < ih {
            if srcRow < ih {
              let dst = y * iw
              let src = srcRow * iw
              let n = min(iw, max(0, indices.count - src))
              if n > 0 {
                for k in 0..<n { deint[dst + k] = indices[src + k] }
              }
            }
            srcRow += 1
            y += step
          }
        }
        indices = deint
      }

      frames.append(GifFrame(x: ix, y: iy, width: iw, height: ih, palette: palette,
          indices: indices, delayMs: delayMs, transparentIndex: transparentIndex,
          disposal: disposal))
      // Reset per-frame state (the TS lib applies it per descriptor).
      delayMs = 0
      transparentIndex = -1
      disposal = 0
    default:
      return nil  // bad block
    }
  }

  return Gif(width: width, height: height, frames: frames,
      globalPalette: globalPalette, loopCount: loopCount)
}

// Smoke: decode a 1×1 transparent GIF built by hand. Real vectors live in
// the TS test suite — this display port mirrors its structure.
let onePixelGif: [UInt8] = [
  0x47, 0x49, 0x46, 0x38, 0x39, 0x61,  // GIF89a
  0x01, 0x00, 0x01, 0x00, 0x80, 0x00, 0x00,  // 1x1, GCT flag, 2 entries
  0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00,  // white, black
  0x2C, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00,  // image 1x1 at 0,0
  0x02, 0x02, 0x44, 0x01, 0x00,  // LZW min 2, sub-block: 44 01, terminator
  0x3B,
]
if let gif = decodeGif(onePixelGif) {
  print("\(gif.width)x\(gif.height), \(gif.frames.count) frame(s), " +
        "first pixel index \(gif.frames[0].indices[0])")
}