Video to GIF Converter — Ruby source

# Video to GIF Converter — Ruby (3.1+), standard library only.
#
# Pure GIF89a encoder core, ported from the canonical TypeScript lib
# src/lib/gif-encode.ts (same contract as the c.c port in this directory):
# 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 arrays (4 bytes/pixel, top-left
# origin). Deterministic. Display source — part of CosmoDev's polyglot pages.

Swatch = Struct.new(:r, :g, :b, :population)

# One input frame. +delay_ms+ is stored in the stream as centiseconds.
GifFrame = Struct.new(:width, :height, :rgba, :delay_ms)

MAX_SAMPLES = 16_384  # palette down-sample ceiling (TS: palette-extract)

# ---------------------------------------------------------------------------
# Median-cut palette extraction (mirrors src/lib/palette-extract.ts)
# ---------------------------------------------------------------------------

def channel_range(bucket)
  mins = [255, 255, 255]
  maxs = [0, 0, 0]
  bucket.each do |px|
    3.times do |c|
      mins[c] = px[c] if px[c] < mins[c]
      maxs[c] = px[c] if px[c] > maxs[c]
    end
  end
  spreads = 3.times.map { |c| maxs[c] - mins[c] }
  best = spreads.each_with_index.max_by { |(range, _c)| range }
  best[0] == 0 ? nil : best
end

def extract_palette(rgba, max_colors)
  total = rgba.length / 4
  return [] if total.zero?

  pixels = []
  stride = [1, total / MAX_SAMPLES].max
  (0...total).step(stride) do |i|
    o = i * 4
    next if rgba[o + 3].zero?  # fully transparent — skip

    pixels << [rgba[o], rgba[o + 1], rgba[o + 2]]
  end
  return [] if pixels.empty?

  buckets = [pixels]
  while buckets.length < max_colors
    best_idx = nil
    best_range = 1  # range 1 (exact duplicates) never splits
    buckets.each_with_index do |bucket, i|
      range, = channel_range(bucket)
      if range && range > best_range
        best_range = range
        best_idx = i
      end
    end
    break unless best_idx  # every bucket is uniform — done

    bucket = buckets.delete_at(best_idx)
    _, channel = channel_range(bucket)
    # sort_by is stable in Ruby, as TS sort() is with a tie-free comparator.
    sorted = bucket.sort_by { |px| px[channel] }
    mid = sorted.length / 2
    buckets << sorted[0, mid]
    buckets << sorted[mid..]
  end

  buckets.filter_map do |b|
    next if b.empty?

    n = b.length
    avg = 3.times.map { |c| (b.sum { |px| px[c] } + n / 2) / n }
    Swatch.new(avg[0], avg[1], avg[2], n)
  end.sort_by { |s| -s.population }  # populous colors get low indices
end

# ---------------------------------------------------------------------------
# Palette mapping — exact-match cache, else nearest RGB (squared distance)
# ---------------------------------------------------------------------------

def map_to_palette(rgba, palette)
  total = rgba.length / 4
  indices = Array.new(total)
  cache = {}
  total.times do |i|
    o = i * 4
    key = (rgba[o] << 16) | (rgba[o + 1] << 8) | rgba[o + 2]
    idx = cache[key]
    unless idx
      best = 0
      best_dist = nil
      palette.each_with_index do |sw, p|
        dr = rgba[o] - sw.r
        dg = rgba[o + 1] - sw.g
        db = rgba[o + 2] - sw.b
        dist = dr * dr + dg * dg + db * db
        if best_dist.nil? || dist < best_dist
          best_dist = dist
          best = p
        end
      end
      idx = cache[key] = best
    end
    indices[i] = idx
  end
  indices
end

# ---------------------------------------------------------------------------
# LZW compression (GIF variant) — codes packed LSB-first, sub-blocked later
# ---------------------------------------------------------------------------

def lzw_encode(min_code_size, indices)
  clear_code = 1 << min_code_size
  eoi_code = clear_code + 1
  code_size = min_code_size + 1
  next_code = eoi_code + 1

  # Dictionary: (prefixCode, byte) -> code, keyed numerically (TS: Map).
  dict = {}
  reset_dict = -> {
    dict.clear
    next_code = eoi_code + 1
    code_size = min_code_size + 1
  }

  out = []
  bit_buffer = 0
  bit_count = 0
  emit = ->(code) {
    bit_buffer |= code << bit_count
    bit_count += code_size
    while bit_count >= 8
      out << (bit_buffer & 0xff)
      bit_buffer >>= 8
      bit_count -= 8
    end
  }
  # The encoder's dictionary runs one entry AHEAD of the decoder's, so the
  # width grows one entry later: right after adding code 2^code_size.
  grow_if_due = -> {
    code_size += 1 if next_code - 1 == (1 << code_size) && code_size < 12
  }

  emit.call(clear_code)
  return out if indices.empty?

  w = indices[0]
  (1...indices.length).each do |i|
    c = indices[i]
    key = (w << 8) | c
    found = dict[key]
    if found
      w = found
      next
    end
    emit.call(w)
    dict[key] = next_code
    next_code += 1
    grow_if_due.call
    w = c
    next if next_code < 4096

    # Dictionary full — reset like encoders do (clear BEFORE continuing).
    emit.call(clear_code)
    reset_dict.call
    w = c
  end
  emit.call(w)
  emit.call(eoi_code)
  out << (bit_buffer & 0xff) if bit_count.positive?
  out
end

# ---------------------------------------------------------------------------
# Byte assembly
# ---------------------------------------------------------------------------

def u16le(n) = [n & 0xff, (n >> 8) & 0xff]

# Returns the GIF89a byte stream as a binary String. Empty input -> "".
def encode_gif(frames, max_colors: 128)
  return +'' if frames.empty?

  # One shared palette, quantized from a down-sampled mix of all frames.
  mixed = []
  frames.each do |f|
    total = f.rgba.length / 4
    stride = [1, total / 4096].max
    (0...total).step(stride) do |i|
      o = i * 4
      mixed.concat(f.rgba[o, 4])
    end
  end
  palette = extract_palette(mixed, [max_colors, 256].min)
  return +'' if palette.empty?

  # 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.
  table_bits = 1
  table_bits += 1 while (1 << table_bits) < palette.length

  out = []
  out.concat('GIF89a'.bytes)
  width = frames.first.width
  height = frames.first.height
  out.concat(u16le(width), u16le(height))
  out << (0x80 | (table_bits - 1)) << 0 << 0  # GCT flag + size; bg; aspect
  (1 << table_bits).times do |i|
    sw = palette[i]
    out << (sw ? sw.r : 0) << (sw ? sw.g : 0) << (sw ? sw.b : 0)
  end

  # NETSCAPE loop forever.
  out.concat([0x21, 0xff, 0x0b])
  out.concat('NETSCAPE2.0'.bytes)
  out.concat([0x03, 0x01, 0x00, 0x00, 0x00])

  min_code_size = [table_bits, 2].max  # GIF spec floor: 2
  frames.each do |frame|
    # Graphic control extension: delay in centiseconds, no transparency.
    cs = (frame.delay_ms / 10.0).round.clamp(0, 0xffff)
    out.concat([0x21, 0xf9, 0x04, 0x00])
    out.concat(u16le(cs))
    out.concat([0x00, 0x00])

    out << 0x2c
    out.concat(u16le(0), u16le(0), u16le(frame.width), u16le(frame.height))
    out << 0x00  # no local color table, no interlace

    indices = map_to_palette(frame.rgba, palette)
    data = lzw_encode(min_code_size, indices)
    out << min_code_size
    data.each_slice(255) { |chunk| out << chunk.length; out.concat(chunk) }
    out << 0x00  # block terminator
  end

  out << 0x3b  # trailer
  out.pack('C*')
end

if __FILE__ == $PROGRAM_NAME
  # Smoke: two frames of a red/blue gradient — decode header fields, sizes.
  frame = ->(delay) {
    rgba = []
    4.times { |y| 4.times { |x| rgba.concat(y < 2 ? [200, 40, 40, 255] : [30, 40, 210, 255]) } }
    GifFrame.new(4, 4, rgba, delay)
  }
  gif = encode_gif([frame.call(100), frame.call(250)])
  bytes = gif.bytes
  puts "encoded #{bytes.length} bytes"
  puts "header: #{gif[0, 6]}  trailer: 0x%02X" % bytes.last
  puts "logical screen: %dx%d" % [bytes[6] | (bytes[7] << 8), bytes[8] | (bytes[9] << 8)]
end