std/gif/decode_lzw.puffs

// Use of this source code is governed by a BSD-style license that can be found
// in the LICENSE file.

// TODO: some mechanism for fixing the error code's value, such as a trailing
// "= 100", to maintain API stability.
pub error "LZW code is out of range"
pub error "LZW prefix chain is cyclical"

pub struct lzw_decoder?(
	literal_width u32[2..8] = 8,
	stack[4096] u8,
	suffixes[4096] u8,
	prefixes[4096] u16[..4095],
)

pub func lzw_decoder.set_literal_width(lw u32[2..8] = 8)() {
	this.literal_width = in.lw
}

pub func lzw_decoder.decode?(dst ptr buf1, src ptr buf1, src_final bool)() {
	// These variables don't change over the lifetime of this func.
	var clear_code u32[4..256] = (1 as u32) << this.literal_width
	var end_code u32[5..257] = clear_code + 1

	// These variables do change.
	var use_save_code bool
	var save_code u32[..4095] = end_code
	var prev_code u32[..4095]
	var width u32[..12] = this.literal_width + 1

	// These variables yield src's bits in Least Significant Bits order.
	var bits u32
	var n_bits u32

	while true,
		pre n_bits < 8,
	{
		assert n_bits < (width + 8) via "a < (b + c): a < c; 0 <= b"()
		while n_bits < width,
			inv n_bits < (width + 8),
			post n_bits >= width,
		{
			assert n_bits < 12 via "a < b: a < c; c <= b"(c:width)
			bits |= (in.src.read_u8?() as u32) << n_bits  // TODO: read_u8 should take src_final.
			n_bits += 8
		}
		var code u32[..4095] = bits.low_bits(n:width)
		bits >>= width
		n_bits -= width

		if code < clear_code {
			assert code < 256 via "a < b: a < c; c <= b"(c:clear_code)
			in.dst.write_u8?(x:code as u8)
			if use_save_code {
				this.suffixes[save_code] = code as u8
				this.prefixes[save_code] = prev_code as u16
			}

		} else if code == clear_code {
			use_save_code = false
			save_code = end_code
			prev_code = 0
			width = this.literal_width + 1
			continue

		} else if code == end_code {
			return

		} else if code <= save_code {
			var s u32[..4095] = 4095
			var c u32[..4095] = code

			if (code == save_code) and use_save_code {
				s -= 1
				c = prev_code
			}

			while c >= clear_code,
				inv n_bits < 8,
				post c < 256 via "a < b: a < c; c <= b"(c:clear_code),
			{
				this.stack[s] = this.suffixes[c]
				if s == 0 {
					return error "LZW prefix chain is cyclical"
				}
				s -= 1
				c = this.prefixes[c] as u32
			}
			this.stack[s] = c as u8

			if (code == save_code) and use_save_code {
				this.stack[4095] = c as u8
			}

			// TODO: the "x:s" arg is a placeholder, and should be something
			// like (this.stack[s:]), which means defining a slice type (and
			// type checking, bounds checking and code generation for it).
			in.dst.write?(x:s)

			if use_save_code {
				this.suffixes[save_code] = c as u8
				this.prefixes[save_code] = prev_code as u16
			}

		} else {
			return error "LZW code is out of range"
		}

		use_save_code = save_code < 4095
		if use_save_code {
			save_code += 1
			if (save_code == ((1 as u32) << width)) and (width < 12) {
				width += 1
			}
		}
		prev_code = code
	}
}