Video to GIF Converter — Swift source

// Video to GIF Converter — Swift (5.9+, standard library only) port of the
// video-to-gif tool: a pure GIF89a encoder core.
// Ported from src/lib/gif-encode.ts (the canonical TypeScript implementation),
// with the palette step inlined from src/lib/palette-extract.ts.
// display source — part of CosmoDev's polyglot tool pages.
//
// Same contract as the TS reference: one palette quantized from a down-sampled
// mix of ALL frames (median cut), nearest-color mapping with an exact-match
// cache, and GIF-variant LZW. No video decode — frames arrive as RGBA buffers.

struct GifFrameInput {
  let width: Int
  let height: Int
  /// RGBA, 4 bytes per pixel, top-left origin.
  let rgba: [UInt8]
  /// Frame delay in milliseconds (stored as centiseconds).
  let delayMs: Int
}

struct Swatch {
  let r: Int, g: Int, b: Int
  let population: Int
}

struct Pixel {
  let r: Int, g: Int, b: Int
}

// ---------------------------------------------------------------------------
// Median-cut palette (inlined port of src/lib/palette-extract.ts)
// ---------------------------------------------------------------------------

/// Down-sample so large frames quantize in bounded time (TS: MAX_SAMPLES).
let maxSamples = 16_384

/// Median-cut quantization: split the widest channel at the median, repeat.
func extractPalette(_ rgba: [UInt8], maxColors: Int = 8) -> [Swatch] {
  let total = rgba.count / 4
  if total == 0 { return [] }

  var pixels: [Pixel] = []
  let stride = max(1, total / maxSamples)
  var i = 0
  while i < total {
    let o = i * 4
    if rgba[o + 3] > 0 { // skip transparent
      pixels.append(Pixel(r: Int(rgba[o]), g: Int(rgba[o + 1]), b: Int(rgba[o + 2])))
    }
    i += stride
  }
  if pixels.isEmpty { return [] }

  var buckets: [[Pixel]] = [pixels]
  while buckets.count < maxColors {
    // Widest-range bucket with more than one distinct value wins the split.
    var bestIdx = -1
    var bestRange = 1 // range 1 (exact duplicates only) never splits further
    for (i, bucket) in buckets.enumerated() {
      let range = channelRange(bucket)
      if range > bestRange {
        bestRange = range
        bestIdx = i
      }
    }
    if bestIdx == -1 { break }
    let halves = splitBucket(buckets.remove(at: bestIdx))
    buckets.append(contentsOf: halves)
  }

  return buckets
    .filter { !$0.isEmpty }
    .map { bucket in
      let n = Double(bucket.count)
      return Swatch(
        r: Int((Double(bucket.reduce(0) { $0 + $1.r }) / n).rounded()),
        g: Int((Double(bucket.reduce(0) { $0 + $1.g }) / n).rounded()),
        b: Int((Double(bucket.reduce(0) { $0 + $1.b }) / n).rounded()),
        population: bucket.count)
    }
    .sorted { $0.population > $1.population } // populous colors get low indices
}

private func channelRange(_ bucket: [Pixel]) -> Int {
  var minR = 255, maxR = 0, minG = 255, maxG = 0, minB = 255, maxB = 0
  for p in bucket {
    minR = min(minR, p.r); maxR = max(maxR, p.r)
    minG = min(minG, p.g); maxG = max(maxG, p.g)
    minB = min(minB, p.b); maxB = max(maxB, p.b)
  }
  return max(maxR - minR, maxG - minG, maxB - minB)
}

private func splitBucket(_ bucket: [Pixel]) -> [[Pixel]] {
  var minR = 255, maxR = 0, minG = 255, maxG = 0, minB = 255, maxB = 0
  for p in bucket {
    minR = min(minR, p.r); maxR = max(maxR, p.r)
    minG = min(minG, p.g); maxG = max(maxG, p.g)
    minB = min(minB, p.b); maxB = max(maxB, p.b)
  }
  var range = maxR - minR, channel = 0
  if maxG - minG > range { range = maxG - minG; channel = 1 }
  if maxB - minB > range { range = maxB - minB; channel = 2 }

  // enumerated().sorted keeps the split deterministic, matching the TS lib's
  // stable sort on ties.
  let sorted = bucket.enumerated()
    .sorted { a, b in
      let av = channel == 0 ? a.element.r : (channel == 1 ? a.element.g : a.element.b)
      let bv = channel == 0 ? b.element.r : (channel == 1 ? b.element.g : b.element.b)
      return av == bv ? a.offset < b.offset : av < bv
    }
    .map(\.element)
  let mid = sorted.count / 2
  return [Array(sorted[..<mid]), Array(sorted[mid...])]
}

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

/// Pack codes LSB-first at the current width, sub-blocked every 255 bytes.
func lzwEncode(_ minCodeSize: Int, _ indices: [UInt8]) -> [UInt8] {
  let clearCode = 1 << minCodeSize
  let eoiCode = clearCode + 1
  var codeSize = minCodeSize + 1
  var nextCode = eoiCode + 1

  // Dictionary: (prefixCode, byte) -> code, keyed numerically.
  var dict: [Int: Int] = [:]
  func resetDict() {
    dict.removeAll(keepingCapacity: true)
    nextCode = eoiCode + 1
    codeSize = minCodeSize + 1
  }
  resetDict()

  var out: [UInt8] = []
  var bitBuffer = 0
  var bitCount = 0
  func emit(_ code: Int) {
    // GIF packs codes LSB-first — the opposite bit order from PNG's deflate.
    bitBuffer |= code << bitCount
    bitCount += codeSize
    while bitCount >= 8 {
      out.append(UInt8(bitBuffer & 0xff))
      bitBuffer >>= 8
      bitCount -= 8
    }
  }
  func flush() {
    if bitCount > 0 { out.append(UInt8(bitBuffer & 0xff)) }
  }
  func growIfDue() {
    // 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
    // width grows one entry later: right after adding code 2^codeSize.
    if nextCode - 1 == 1 << codeSize && codeSize < 12 { codeSize += 1 }
  }

  emit(clearCode)
  if indices.isEmpty {
    emit(eoiCode)
    flush()
    return out
  }

  var w = Int(indices[0])
  for i in 1..<indices.count {
    let c = Int(indices[i])
    let key = (w << 8) | c
    if let found = dict[key] {
      w = found
      continue
    }
    emit(w)
    dict[key] = nextCode
    nextCode += 1
    growIfDue()
    w = c
    if nextCode >= 4096 {
      // Dictionary full — reset like encoders do.
      emit(clearCode)
      resetDict()
      w = c
    }
  }
  emit(w)
  emit(eoiCode)
  flush()
  return out
}

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

/// Map RGBA to palette indices via exact cache + nearest RGB distance.
private func mapToPalette(_ rgba: [UInt8], _ palette: [Swatch]) -> [UInt8] {
  let count = rgba.count / 4
  var indices = [UInt8](repeating: 0, count: count)
  var cache: [Int: UInt8] = [:] // 24-bit packed RGB key
  for i in 0..<count {
    let o = i * 4
    let key = (Int(rgba[o]) << 16) | (Int(rgba[o + 1]) << 8) | Int(rgba[o + 2])
    if let idx = cache[key] {
      indices[i] = idx
      continue
    }
    var best = 0
    var bestDist = Int.max
    for (p, sw) in palette.enumerated() {
      let dr = Int(rgba[o]) - sw.r
      let dg = Int(rgba[o + 1]) - sw.g
      let db = Int(rgba[o + 2]) - sw.b
      let dist = dr * dr + dg * dg + db * db
      if dist < bestDist {
        bestDist = dist
        best = p
      }
    }
    cache[key] = UInt8(best)
    indices[i] = UInt8(best)
  }
  return indices
}

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

func encodeGif(_ frames: [GifFrameInput], maxColors: Int = 128) -> [UInt8] {
  let maxColors = min(maxColors, 256)
  if frames.isEmpty { return [] }

  // One shared palette, quantized from a down-sampled mix of all frames.
  var mixed: [UInt8] = []
  for f in frames {
    let total = f.rgba.count / 4
    let stride = max(1, total / 4096)
    var i = 0
    while i < total {
      mixed.append(f.rgba[i * 4])
      mixed.append(f.rgba[i * 4 + 1])
      mixed.append(f.rgba[i * 4 + 2])
      mixed.append(f.rgba[i * 4 + 3])
      i += stride
    }
  }
  let palette = extractPalette(mixed, maxColors: maxColors)
  if palette.isEmpty { return [] }

  // Palette table padded to a power of two (min 2 entries); the GCT size
  // field stores bits-1, so a 2-color table is written as 0.
  var tableBits = 1
  while (1 << tableBits) < palette.count { tableBits += 1 }
  let tableSize = 1 << tableBits

  var out: [UInt8] = []
  func u16le(_ n: Int) {
    out.append(UInt8(n & 0xff))
    out.append(UInt8((n >> 8) & 0xff))
  }

  out.append(contentsOf: Array("GIF89a".utf8))
  u16le(frames[0].width)
  u16le(frames[0].height)
  out.append(UInt8(0x80 | (tableBits - 1))); out.append(0); out.append(0) // GCT flag + size; bg; aspect
  for i in 0..<tableSize {
    let sw = i < palette.count ? palette[i] : nil
    out.append(UInt8(sw?.r ?? 0)); out.append(UInt8(sw?.g ?? 0)); out.append(UInt8(sw?.b ?? 0))
  }

  // NETSCAPE loop forever.
  out.append(0x21); out.append(0xff); out.append(0x0b)
  out.append(contentsOf: Array("NETSCAPE2.0".utf8))
  out.append(0x03); out.append(0x01); out.append(0x00); out.append(0x00); out.append(0x00)

  let minCodeSize = max(2, tableBits) // GIF spec floor: 2
  for frame in frames {
    // Graphic control extension: delay in centiseconds, no transparency.
    var cs = Int((Double(frame.delayMs) / 10).rounded())
    cs = max(0, min(0xffff, cs))
    out.append(0x21); out.append(0xf9); out.append(0x04); out.append(0x00)
    u16le(cs)
    out.append(0x00); out.append(0x00)

    out.append(0x2c)
    u16le(0); u16le(0); u16le(frame.width); u16le(frame.height)
    out.append(0x00) // no local color table, no interlace

    let indices = mapToPalette(frame.rgba, palette)
    let data = lzwEncode(minCodeSize, indices)
    out.append(UInt8(minCodeSize))
    var i = 0
    while i < data.count { // sub-blocked every 255 bytes
      let chunkEnd = min(i + 255, data.count)
      out.append(UInt8(chunkEnd - i))
      out.append(contentsOf: data[i..<chunkEnd])
      i = chunkEnd
    }
    out.append(0x00) // block terminator
  }

  out.append(0x3b) // trailer
  return out
}

// Smoke: a 4×2 two-frame animation — red then blue — encodes to a valid
// GIF89a header + trailer.
let red = GifFrameInput(width: 4, height: 2,
                        rgba: (0..<8).flatMap { _ in [200, 40, 40, 255] },
                        delayMs: 100)
let blue = GifFrameInput(width: 4, height: 2,
                        rgba: (0..<8).flatMap { _ in [40, 60, 200, 255] },
                        delayMs: 100)
let gif = encodeGif([red, blue], maxColors: 4)
let hex = gif.prefix(6).map { String($0, radix: 16, uppercase: true) }.joined(separator: " ")
print("encoded \(gif.count) bytes: \(hex)") // expect "47 49 46 38 39 61" — "GIF89a"