// GIF decoder (GIF87a / GIF89a): LZW, global / local color tables,
// interlaced frames, transparency, and animation with frame disposal.
///|
priv struct GifReader {
data : Bytes
mut pos : Int32
}
///|
fn GifReader::u8(self : GifReader) -> Int32 raise DecodeError {
if self.pos >= self.data.length() {
raise CorruptData("unexpected end of GIF data")
}
let v = self.data[self.pos].to_int()
self.pos += 1
v
}
///|
fn GifReader::u16(self : GifReader) -> Int32 raise DecodeError {
let lo = self.u8()
lo | (self.u8() << 8)
}
///|
fn GifReader::color_table(
self : GifReader,
size : Int32,
) -> FixedArray[Byte] raise DecodeError {
if self.pos + size * 3 > self.data.length() {
raise CorruptData("GIF color table truncated")
}
let table = FixedArray::make(size * 3, b'\x00')
table.blit_from_bytes(0, self.data, self.pos, size * 3)
self.pos += size * 3
table
}
///|
/// Concatenate data sub-blocks up to (and including) the block terminator.
fn GifReader::sub_blocks(self : GifReader) -> Bytes raise DecodeError {
let buf = Buffer()
while true {
let n = self.u8()
if n == 0 {
break
}
if self.pos + n > self.data.length() {
raise CorruptData("GIF data sub-block truncated")
}
buf.write_bytesview(self.data[self.pos:self.pos + n])
self.pos += n
}
buf.to_bytes()
}
///|
fn GifReader::skip_sub_blocks(self : GifReader) -> Unit raise DecodeError {
while true {
let n = self.u8()
if n == 0 {
break
}
self.pos += n
}
}
///|
/// Decode GIF LZW data into exactly `count` color indices. Missing data
/// (truncated streams are common) leaves the remaining indices at 0.
fn gif_lzw_decode(
data : Bytes,
min_code_size : Int32,
count : Int32,
) -> FixedArray[Byte] raise DecodeError {
if min_code_size < 1 || min_code_size > 11 {
raise CorruptData("invalid GIF LZW minimum code size")
}
let out = FixedArray::make(count, b'\x00')
let clear = 1 << min_code_size
let eoi = clear + 1
let prefix = FixedArray::make(4096, 0)
let suffix = FixedArray::make(4096, b'\x00')
let length = FixedArray::make(4096, 0)
for i in 0.. Byte {
let len = length[code]
let mut c = code
let mut i = len - 1
while i >= 0 {
if written + i < count {
out[written + i] = suffix[c]
}
if i > 0 {
c = prefix[c]
}
i -= 1
}
written += len
suffix[c] // first byte of the string
}
while written < count {
while bit_count < code_size && pos < data.length() {
bit_buf = bit_buf | (data[pos].to_int() << bit_count)
bit_count += 8
pos += 1
}
if bit_count < code_size {
break // truncated
}
let code = bit_buf & ((1 << code_size) - 1)
bit_buf = bit_buf >> code_size
bit_count -= code_size
if code == clear {
code_size = min_code_size + 1
next_code = eoi + 1
prev = -1
continue
}
if code == eoi {
break
}
if prev < 0 {
if code >= clear {
raise CorruptData("invalid first GIF LZW code")
}
ignore(emit(code))
prev = code
continue
}
let first = if code < next_code {
emit(code)
} else if code == next_code {
// KwKwK: the new string is prev + first byte of prev.
let f = emit(prev)
if written < count {
out[written] = f
}
written += 1
f
} else {
raise CorruptData("invalid GIF LZW code")
}
if next_code < 4096 {
prefix[next_code] = prev
suffix[next_code] = first
length[next_code] = length[prev] + 1
next_code += 1
if next_code == 1 << code_size && code_size < 12 {
code_size += 1
}
}
prev = code
}
out
}
///|
fn gif_signature_ok(data : Bytes) -> Bool {
data.length() >= 6 &&
data[0] == b'G' &&
data[1] == b'I' &&
data[2] == b'F' &&
data[3] == b'8' &&
(data[4] == b'7' || data[4] == b'9') &&
data[5] == b'a'
}
///|
/// Decode frames, compositing them like browsers do: the canvas starts
/// transparent (the background color is ignored), each frame is drawn over
/// it with its transparent index skipped, and its disposal method is applied
/// before the next frame (2 = clear the frame rectangle, 3 = restore the
/// canvas from before the frame). `max_frames` stops early.
fn decode_gif_impl(
data : Bytes,
max_frames : Int32,
) -> Animation raise DecodeError {
if !gif_signature_ok(data) {
raise InvalidSignature("not a GIF file")
}
let r : GifReader = { data, pos: 6, }
let width = r.u16()
let height = r.u16()
let flags = r.u8()
ignore(r.u8()) // background color index
ignore(r.u8()) // pixel aspect ratio
check_decode_size(width, height)
let global_table = if (flags & 0x80) != 0 {
Some(r.color_table(1 << ((flags & 7) + 1)))
} else {
None
}
let canvas = FixedArray::make(width * height * 4, b'\x00')
let frames : Array[AnimationFrame] = []
let mut loop_count : Int32? = None
// Pending Graphics Control Extension for the next image.
let mut delay = 0
let mut disposal = 0
let mut transparent = -1
while r.pos < data.length() && frames.length() < max_frames {
match r.u8() {
0x3B => break // trailer
0x21 => {
let label = r.u8()
if label == 0xF9 {
// Graphics Control Extension
let block = r.sub_blocks()
if block.length() >= 4 {
let packed = block[0].to_int()
disposal = (packed >> 2) & 7
delay = block[1].to_int() | (block[2].to_int() << 8)
transparent = if (packed & 1) != 0 { block[3].to_int() } else { -1 }
}
} else if label == 0xFF {
// Application extension (NETSCAPE2.0 / ANIMEXTS1.0 loop count)
let block = r.sub_blocks()
if block.length() >= 14 &&
block[0:11].to_owned() == b"NETSCAPE2.0" &&
block[11] == b'\x01' {
loop_count = Some(block[12].to_int() | (block[13].to_int() << 8))
}
} else {
r.skip_sub_blocks()
}
}
0x2C => {
// Image descriptor
let fx = r.u16()
let fy = r.u16()
let fw = r.u16()
let fh = r.u16()
let fflags = r.u8()
let local_table = if (fflags & 0x80) != 0 {
Some(r.color_table(1 << ((fflags & 7) + 1)))
} else {
None
}
let interlaced = (fflags & 0x40) != 0
let table = match local_table {
Some(t) => t
None =>
match global_table {
Some(t) => t
None => raise CorruptData("GIF frame without a color table")
}
}
let entries = table.length() / 3
let min_code_size = r.u8()
let lzw = r.sub_blocks()
if fw > 0 && fh > 0 {
check_decode_size(fw, fh)
}
let indices = gif_lzw_decode(lzw, min_code_size, fw * fh)
let saved = if disposal == 3 { Some(canvas.copy()) } else { None }
// Draw
for row in 0..= height {
continue
}
for col in 0..= width {
continue
}
let idx = indices[row * fw + col].to_int()
if idx == transparent {
continue
}
let o = (y * width + x) * 4
if idx < entries {
canvas[o] = table[idx * 3]
canvas[o + 1] = table[idx * 3 + 1]
canvas[o + 2] = table[idx * 3 + 2]
} else {
canvas[o] = b'\x00'
canvas[o + 1] = b'\x00'
canvas[o + 2] = b'\x00'
}
canvas[o + 3] = b'\xFF'
}
}
frames.push({
image: { width, height, data: Bytes::from_array(canvas.copy()), },
delay_ms: delay * 10,
})
// Dispose
match (disposal, saved) {
(2, _) =>
for y in fy..<(fy + fh) {
if y >= height {
break
}
for x in fx..<(fx + fw) {
if x >= width {
break
}
let o = (y * width + x) * 4
for c in 0..<4 {
canvas[o + c] = b'\x00'
}
}
}
(3, Some(prev)) => prev.blit_to(canvas, len=prev.length())
_ => ()
}
delay = 0
disposal = 0
transparent = -1
}
b => raise CorruptData("unexpected GIF block 0x" + b.to_string(radix=16))
}
}
if frames.is_empty() {
raise MissingChunk("GIF image data")
}
// NETSCAPE loop count n repeats n more times (0 = forever); without the
// extension the animation plays once.
let plays = match loop_count {
None => 1
Some(0) => 0
Some(n) => n + 1
}
{ width, height, frames, plays, }
}
///|
/// Map the `row`-th stored row of an interlaced image to its y coordinate
/// (passes: every 8th row from 0, every 8th from 4, every 4th from 2,
/// every 2nd from 1).
fn gif_interlaced_row(row : Int32, height : Int32) -> Int32 {
let p1 = (height + 7) / 8
let p2 = (height + 3) / 8
let p3 = (height + 1) / 4
if row < p1 {
row * 8
} else if row < p1 + p2 {
(row - p1) * 8 + 4
} else if row < p1 + p2 + p3 {
(row - p1 - p2) * 4 + 2
} else {
(row - p1 - p2 - p3) * 2 + 1
}
}
///|
/// Decode the first frame of a GIF (composited on the logical screen).
pub fn decode_gif(data : Bytes) -> ImageData raise DecodeError {
decode_gif_impl(data, 1).frames[0].image
}
///|
/// Decode every frame of a (possibly animated) GIF. Each frame is the full
/// logical screen after compositing, with its delay.
pub fn decode_gif_frames(data : Bytes) -> Animation raise DecodeError {
decode_gif_impl(data, 0x7FFFFFFF)
}