GIF Frame Extractor — Ruby source

# GIF Frame Extractor — decode a GIF byte stream into indexed frames.
#
# Language: Ruby (3.x), 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 nil (same contract as the TS reference). Bytes
# travel as binary Strings — indexing yields code points, not characters.

module GifFrameExtractor
  Frame = Struct.new(:x, :y, :width, :height,
                     :palette,    # RGB-triplet binary String; nil = global.
                     :indices,    # Pixel indices in natural row order.
                     :delay_ms, :transparent_index, :disposal)
  Result = Struct.new(:width, :height,   # Logical screen size.
                      :frames, :global_palette,
                      :loop_count)      # 0 = forever, nil when absent.

  module_function

  # -- GIF LZW decompression ----------------------------------------------

  # minCodeSize 2-8, clear-code resets, growing codes — same contract as TS.
  def lzw_decode(min_code_size, data)
    clear_code = 1 << min_code_size
    eoi_code = clear_code + 1
    code_size = min_code_size + 1
    next_code = eoi_code + 1
    # Dictionary as (prefix, suffix, first-byte) triples, reset per clear.
    prefix = Array.new(4096, -1)
    suffix = Array.new(4096) { |i| i < clear_code ? i : 0 }
    first = prefix.dup
    clear_code.times { |i| prefix[i] = -1; suffix[i] = i; first[i] = i }
    out = []
    bit_pos = 0
    prev = -1

    # Read one code LSB-first; returns EOI on truncation, like the TS decoder.
    read_code = lambda do
      return eoi_code if ((bit_pos + code_size) >> 3) > data.bytesize
      code = 0
      code_size.times do |i|
        byte_idx = (bit_pos + i) >> 3
        return eoi_code if byte_idx >= data.bytesize
        code |= ((data.getbyte(byte_idx) >> ((bit_pos + i) & 7)) & 1) << i
      end
      bit_pos += code_size
      code
    end

    # Emit a code's chain; returns the chain's FIRST byte (needed for KwKwK).
    emit = lambda do |code|
      stack = []
      c = code
      while c >= 0
        stack << suffix[c]
        c = prefix[c]
      end
      out.concat(stack.reverse)
      stack.last
    end

    loop do
      code = read_code.call
      break if code == eoi_code

      if code == clear_code
        next_code = eoi_code + 1
        code_size = min_code_size + 1
        clear_code.times { |i| prefix[i] = -1; suffix[i] = i; first[i] = i }
        prev = -1
        next
      end
      if prev == -1
        break if code >= clear_code # First code after clear must be a literal.

        emit.call(code)
        prev = code
        next
      end
      break if code > next_code # Invalid — stop like browsers do.

      # KwKwK: a code one ahead of the dictionary is prev + first(prev).
      emitted_first =
        if code == next_code
          emit.call(prev)
          out << first[prev]
          first[prev]
        else
          emit.call(code)
        end
      if next_code < 4096 # Table full: TS silently no-ops this write.
        prefix[next_code] = prev
        suffix[next_code] = emitted_first
        first[next_code] = first[prev]
        next_code += 1
        code_size += 1 if next_code == (1 << code_size) && code_size < 12
      end
      prev = code
    end
    out.pack('C*')
  end

  # -- Interlace -------------------------------------------------------------

  # Reorder interlaced rows into natural order; identity for short frames.
  def de_interlace(indices, width, height)
    return indices if height < 4 || width.zero?

    idx = indices.unpack('C*')
    out = Array.new(idx.length)
    src = 0 # Stored pass-by-pass: four passes, starts/steps below.
    [[0, 8], [4, 8], [2, 4], [1, 2]].each do |start, step|
      (start...height).step(step) do |row|
        out[row * width, width] = idx[src, width]
        src += width
      end
    end
    out.pack('C*')
  end

  # -- Whole-GIF parse -------------------------------------------------------

  # Concatenate a sub-block chain; nil on truncation.
  def read_sub_blocks(bytes, pos)
    chunks = []
    loop do
      return nil if pos >= bytes.bytesize

      size = bytes.getbyte(pos)
      pos += 1
      break if size.zero? # Terminator ends the chain.
      return nil if pos + size > bytes.bytesize

      chunks << bytes.byteslice(pos, size)
      pos += size
    end
    chunks.join
  end

  # Parse signature, screen descriptor, extensions, and all frames.
  def decode_gif(bytes)
    return nil if bytes.bytesize < 13
    return nil unless bytes.byteslice(0, 6) == 'GIF87a' || bytes.byteslice(0, 6) == 'GIF89a'

    # Logical screen descriptor: canvas size, flags, optional global palette.
    pos = 6
    width = bytes.getbyte(pos) | (bytes.getbyte(pos + 1) << 8)
    height = bytes.getbyte(pos + 2) | (bytes.getbyte(pos + 3) << 8)
    packed = bytes.getbyte(pos + 4)
    pos += 7 # Skip bg color + aspect ratio.
    global_palette = nil
    if packed & 0x80 != 0
      n = (2 << (packed & 7)) * 3
      return nil if pos + n > bytes.bytesize

      global_palette = bytes.byteslice(pos, n)
      pos += n
    end

    frames = []
    loop_count = nil # Absent until a NETSCAPE block says otherwise.
    delay_ms = 0
    transparent_index = -1
    disposal = 0

    loop do
      return nil if pos >= bytes.bytesize

      block = bytes.getbyte(pos)
      pos += 1
      break if block == 0x3b # trailer

      if block == 0x21 # Extension: graphic control / NETSCAPE / skip.
        return nil if pos >= bytes.bytesize

        label = bytes.getbyte(pos)
        pos += 1
        if label == 0xf9
          gce = read_sub_blocks(bytes, pos)
          return nil if gce.nil? || gce.bytesize < 4

          disposal = (gce.getbyte(0) >> 2) & 7
          delay_ms = (gce.getbyte(1) | (gce.getbyte(2) << 8)) * 10
          transparent_index = gce.getbyte(0) & 1 != 0 ? gce.getbyte(3) : -1
        elsif label == 0xff
          app = read_sub_blocks(bytes, pos)
          # Concatenated: 11-byte name, then id 1 + loop lo/hi.
          loop_count = app.getbyte(12) | (app.getbyte(13) << 8) if app &&
            app.bytesize >= 14 && app.byteslice(0, 11) == 'NETSCAPE2.0' &&
            app.getbyte(11) == 1
        elsif read_sub_blocks(bytes, pos).nil?
          return nil
        end
        next
      end

      if block == 0x2c # Image descriptor: rect, local palette, LZW data.
        return nil if pos + 9 > bytes.bytesize

        x = bytes.getbyte(pos) | (bytes.getbyte(pos + 1) << 8)
        y = bytes.getbyte(pos + 2) | (bytes.getbyte(pos + 3) << 8)
        w = bytes.getbyte(pos + 4) | (bytes.getbyte(pos + 5) << 8)
        h = bytes.getbyte(pos + 6) | (bytes.getbyte(pos + 7) << 8)
        ip = bytes.getbyte(pos + 8)
        pos += 9 # Descriptor is 9 bytes: x, y, w, h, packed flags.
        palette = nil
        if ip & 0x80 != 0
          n = (2 << (ip & 7)) * 3
          return nil if pos + n > bytes.bytesize

          palette = bytes.byteslice(pos, n)
          pos += n
        end
        return nil if pos >= bytes.bytesize

        min_code_size = bytes.getbyte(pos)
        pos += 1
        data = read_sub_blocks(bytes, pos) # Must be a complete sub-block chain.
        return nil if data.nil?

        indices = lzw_decode(min_code_size, data)
        indices = de_interlace(indices, w, h) if ip & 0x40 != 0
        frames << Frame.new(x, y, w, h, palette, indices,
                            delay_ms, transparent_index, disposal)
        delay_ms = 0
        transparent_index = -1
        disposal = 0
        next
      end

      return nil # Unknown block type — bail.
    end
    Result.new(width, height, frames, global_palette, loop_count)
  end
end

# 2×1 GIF89a: 2-color global palette (red, blue), one frame, pixels [0,1].
gif = [
  'GIF89a', "\x02\x00\x01\x00\x80\x00\x00",
  "\xff\x00\x00", "\x00\x00\xff",
  "\x2c", "\x00\x00\x00\x00\x02\x00\x01\x00\x00",
  "\x02", "\x02\x44\x0a", "\x00", "\x3b"
].join.force_encoding('ASCII-8BIT')
res = GifFrameExtractor.decode_gif(gif)
abort 'malformed GIF' if res.nil?
puts "#{res.width}x#{res.height}, #{res.frames.length} frame(s), loop=#{res.loop_count}"
res.frames.each_with_index do |f, i|
  idx = f.indices.unpack('C*').join(', ')
  puts "frame #{i}: #{f.width}x#{f.height} at (#{f.x},#{f.y}), " \
       "delay #{f.delay_ms}ms, indices [#{idx}]"
end