dymokomi/luce-webp
Source of release 0.1.0
0.1.0 / src / webp / vp8l_decode.lucb
#==============================================================================================
#
# webp/vp8l_decode - The lossless image streams
#
# DESCRIPTION:
# Port of dec/vp8l_dec.c, non-incremental. An image stream is its transforms (at
# the top level only), a color cache, its Huffman codes (with a meta Huffman image
# choosing the group of each tile, at the top level), then the pixels: literals,
# backward references (LZ77, distances through the 2D plane codes) and color cache
# hits. Sub-images (transform data, the Huffman image) are streams of their own.
# The top-level pixels are transformed back and handed on sixteen rows at a time:
# to RGBA, or for an ALPH chunk, their green as alpha (with a byte-per-pixel path
# for a palette-only alpha stream), unfiltered as they arrive.
#
#==============================================================================================
## Rows transformed and handed on at a time (NUM_ARGB_CACHE_ROWS).
let num_argb_cache_rows: usize = 16
## The 120 short distance codes of the 2D plane: (yoffset << 4) | (8 - xoffset).
let code_to_plane: u8[120] = [
0x18, 0x07, 0x17, 0x19, 0x28, 0x06, 0x27, 0x29, 0x16, 0x1a, 0x26, 0x2a, 0x38, 0x05, 0x37, 0x39, 0x15, 0x1b, 0x36, 0x3a, 0x25, 0x2b, 0x48, 0x04, 0x47, 0x49, 0x14, 0x1c, 0x35, 0x3b, 0x46, 0x4a, 0x24, 0x2c, 0x58, 0x45, 0x4b, 0x34, 0x3c, 0x03,
0x57, 0x59, 0x13, 0x1d, 0x56, 0x5a, 0x23, 0x2d, 0x44, 0x4c, 0x55, 0x5b, 0x33, 0x3d, 0x68, 0x02, 0x67, 0x69, 0x12, 0x1e, 0x66, 0x6a, 0x22, 0x2e, 0x54, 0x5c, 0x43, 0x4d, 0x65, 0x6b, 0x32, 0x3e, 0x78, 0x01, 0x77, 0x79, 0x53, 0x5d, 0x11, 0x1f,
0x64, 0x6c, 0x42, 0x4e, 0x76, 0x7a, 0x21, 0x2f, 0x75, 0x7b, 0x31, 0x3f, 0x63, 0x6d, 0x52, 0x5e, 0x00, 0x74, 0x7c, 0x41, 0x4f, 0x10, 0x20, 0x62, 0x6e, 0x30, 0x73, 0x7d, 0x51, 0x5f, 0x40, 0x72, 0x7e, 0x61, 0x6f, 0x50, 0x71, 0x7f, 0x60, 0x70]
let num_transforms: usize = 4
# mark: The decoder ===========================================================================
## Where the top-level rows go.
enum Sink:
## Nowhere: a sub-image, kept whole.
keep
## RGBA into the area.
rgba
## Their green, as alpha, into the plane.
alpha
## The codes and color cache of the stream being decoded (VP8LMetadata).
struct Metadata:
var color_cache_size: usize
var color_cache: u32[]
var hash_shift: u32
## The tile mask (all ones without a Huffman image), bits and width of the Huffman image.
var huffman_mask: usize
var huffman_subsample_bits: u32
var huffman_xsize: usize
var huffman_image: u32[]
var num_htree_groups: usize
var htree_groups: TreeGroup[]
var huffman_tables: HuffmanTables
## ClearMetadata.
func clear():
if self.color_cache.length > 0:
free(self.color_cache) in memory.heap
if self.huffman_image.length > 0:
free(self.huffman_image) in memory.heap
if self.htree_groups.length > 0:
free(self.htree_groups) in memory.heap
self.huffman_tables.release()
var cleared: Metadata
self = cleared
## A lossless decoder (VP8LDecoder).
struct Lossless:
var br: LosslessBits
## The size of the stream at hand (at the top level, after color indexing's bundling).
var width: usize
var height: usize
## The picture's size.
var io_width: usize
var io_height: usize
var hdr: Metadata
var transforms: Transform[4]
var next_transform: usize
var transforms_seen: u32
## The top-level pixels, then the row above the cache, then the cache of transformed
## rows (argb_cache).
var pixels: u32[]
var argb_cache: usize
var last_row: usize
var last_pixel: usize
var last_out_row: usize
var sink: Sink = Sink.keep
## The RGBA destination.
var area_pixels: u8[]
var area_stride: usize
## The alpha plane, its filter, and its last row (prev_line).
var plane: u8[]
var filter: u8
var prev_line: usize?
func release():
self.hdr.clear()
for i in 0..<self.next_transform:
if self.transforms[i].data.length > 0:
free(self.transforms[i].data) in memory.heap
if self.pixels.length > 0:
free(self.pixels) in memory.heap
# mark: Distances =============================================================================
## GetCopyDistance: a length or distance from its prefix symbol and extra bits.
inline func get_copy_distance(symbol: u32, br: LosslessBits*) -> usize:
if symbol < 4:
return (usize)symbol + 1
let extra_bits = (symbol - 2) >> 1
let offset = (2 + (symbol & 1)) << extra_bits
return (usize)(offset + br.read_bits(extra_bits)) + 1
## PlaneCodeToDistance: a distance code to a distance in pixels, the first 120 codes a
## neighbourhood in the 2D plane.
inline func plane_code_to_distance(xsize: usize, plane_code: usize) -> usize:
if plane_code > 120:
return plane_code - 120
let dist_code = (i64)code_to_plane[plane_code - 1]
let yoffset = dist_code >> 4
let xoffset = 8 - (dist_code & 0xf)
let distance = yoffset * (i64)xsize + xoffset
return (usize)distance if distance >= 1 else 1
## GetMetaIndex and GetHtreeGroupForPos: the group of the tile at (`x`, `y`).
inline func group_for_pos(hdr: const Metadata*, x: usize, y: usize) -> const TreeGroup*:
if hdr.huffman_subsample_bits == 0:
return &hdr.htree_groups[0]
let bits = hdr.huffman_subsample_bits
return &hdr.htree_groups[(usize)hdr.huffman_image[hdr.huffman_xsize * (y >> bits) + (x >> bits)]]
## ReadPackedSymbols: a whole literal pixel into `dst` (returning 0), or a non-literal
## green symbol.
inline func read_packed_symbols(group: const TreeGroup*, br: LosslessBits*, dst: u32*) -> u32:
let val = br.prefetch_bits() & 63
let code = (&group.packed_table[0])[(usize)val]
if code.bits < bits_special_marker:
br.bit_pos = br.bit_pos +% (u32)code.bits
dst[0] = code.value
return 0
br.bit_pos = br.bit_pos +% (u32)(code.bits -% bits_special_marker)
return code.value
## VP8LHashPix and VP8LColorCacheInsert.
inline func cache_insert(hdr: Metadata*, argb: u32):
hdr.color_cache.data[(usize)((argb *% 0x1e35a7bd) >> (hdr.hash_shift & 31))] = argb
## CopyBlock32b: `length` pixels from `dist` back, overlapping as a repeating pattern.
inline func copy_block32(dst: u32*, dist: usize, length: usize):
let src = dst - dist
if dist >= length:
memory.copy(u32[](dst, length), u32[]((u32*)src, length), length)
return
for i in 0..<length:
dst[i] = src[i]
# mark: Streams ===============================================================================
## ReadTransform: the next transform, and its data; color indexing narrows `xsize`.
func read_transform(dec: Lossless*, xsize: usize*, ysize: usize) -> !:
let kind = dec.br.read_bits(2)
# Each transform at most once.
if (dec.transforms_seen & ((u32)1 << kind)) != 0:
error(corrupt, "VP8L transform appears twice")
dec.transforms_seen |= (u32)1 << kind
let index = dec.next_transform
dec.transforms[index] = Transform(kind = kind, bits = 0, xsize = *xsize, ysize = ysize)
dec.next_transform += 1
if kind == predictor_transform or kind == cross_color_transform:
let bits = 2 + dec.br.read_bits(3)
dec.transforms[index].bits = bits
dec.transforms[index].data = try decode_image_stream(dec, sub_sample_size(*xsize, bits), sub_sample_size(ysize, bits), false)
elif kind == color_indexing_transform:
let num_colors = (usize)dec.br.read_bits(8) + 1
let bits: u32 = 0 if num_colors > 16 else 1 if num_colors > 4 else 2 if num_colors > 2 else 3
*xsize = sub_sample_size(dec.transforms[index].xsize, bits)
dec.transforms[index].bits = bits
let palette = try decode_image_stream(dec, num_colors, 1, false)
defer free(palette) in memory.heap
# ExpandColorMap: the palette is delta coded, and spans every bundled value.
let final_num_colors = (usize)1 << ((u32)8 >> bits)
let expanded = try new u32[final_num_colors] in memory.heap
let data = u8[]((u8*)palette.data, 4 * num_colors)
let new_data = u8[]((u8*)expanded.data, 4 * final_num_colors)
expanded[0] = palette[0]
for i in 4..<4 * num_colors:
new_data[i] = data[i] +% new_data[i - 4]
dec.transforms[index].data = expanded
## ReadHuffmanCodes: the codes of the stream, with the meta Huffman image where allowed.
func read_huffman_codes(dec: Lossless*, xsize: usize, ysize: usize, color_cache_bits: u32, allow_recursion: bool) -> !:
var num_htree_groups: usize = 1
var num_htree_groups_max: usize = 1
var mapping: i32[]
defer:
if mapping.length > 0:
free(mapping) in memory.heap
var huffman_image: u32[]
errdefer:
if huffman_image.length > 0:
free(huffman_image) in memory.heap
var subsample_bits: u32 = 0
if allow_recursion and dec.br.read_bits(1) != 0:
# Meta Huffman codes.
let huffman_precision = 2 + dec.br.read_bits(3)
let huffman_xsize = sub_sample_size(xsize, huffman_precision)
let huffman_ysize = sub_sample_size(ysize, huffman_precision)
let huffman_pixs = huffman_xsize * huffman_ysize
huffman_image = try decode_image_stream(dec, huffman_xsize, huffman_ysize, false)
subsample_bits = huffman_precision
for i in 0..<huffman_pixs:
# The group is in the red and green bytes.
let group = (huffman_image[i] >> 8) & 0xffff
huffman_image[i] = group
if (usize)group >= num_htree_groups_max:
num_htree_groups_max = (usize)group + 1
# Too many groups for the image: only the ones used are kept, mapped to
# 0..num_htree_groups.
if num_htree_groups_max > 1000 or num_htree_groups_max > xsize * ysize:
mapping = try new i32[num_htree_groups_max] in memory.heap
memory.set(u8[]((u8*)mapping.data, num_htree_groups_max * 4), 0xff)
num_htree_groups = 0
for i in 0..<huffman_pixs:
let mapped_group = &mapping[(usize)huffman_image[i]]
if *mapped_group == -1:
*mapped_group = (i32)num_htree_groups
num_htree_groups += 1
huffman_image[i] = (u32)*mapped_group
else:
num_htree_groups = num_htree_groups_max
if dec.br.eos:
error(corrupt, "VP8L data ends in the Huffman image")
let groups = try new TreeGroup[num_htree_groups] in memory.heap
errdefer free(groups) in memory.heap
read_huffman_codes_helper(&dec.br, color_cache_bits, num_htree_groups, num_htree_groups_max, mapping, &dec.hdr.huffman_tables, groups) catch failure:
dec.hdr.huffman_tables.release()
error(failure.code, failure.message)
dec.hdr.huffman_subsample_bits = subsample_bits
dec.hdr.huffman_image = huffman_image
dec.hdr.num_htree_groups = num_htree_groups
dec.hdr.htree_groups = groups
## DecodeImageStream: a stream of `xsize` by `ysize` pixels. At the top level it reads the
## transforms and codes and leaves the pixels to the caller (returning nothing); a
## sub-image is decoded whole and returned.
func decode_image_stream(dec: Lossless*, xsize: usize, ysize: usize, is_level0: bool) -> u32[]!:
var transform_xsize = xsize
let transform_ysize = ysize
errdefer dec.hdr.clear()
if is_level0:
while dec.br.read_bits(1) != 0:
if dec.next_transform >= num_transforms:
error(corrupt, "VP8L has too many transforms")
try read_transform(dec, &transform_xsize, transform_ysize)
# The color cache.
var color_cache_bits: u32 = 0
if dec.br.read_bits(1) != 0:
color_cache_bits = dec.br.read_bits(4)
if color_cache_bits < 1 or color_cache_bits > max_cache_bits:
error(corrupt, "VP8L color cache size is invalid")
try read_huffman_codes(dec, transform_xsize, transform_ysize, color_cache_bits, is_level0)
if color_cache_bits > 0:
dec.hdr.color_cache_size = (usize)1 << color_cache_bits
dec.hdr.color_cache = try new u32[dec.hdr.color_cache_size] in memory.heap
dec.hdr.hash_shift = 32 - color_cache_bits
else:
dec.hdr.color_cache_size = 0
# UpdateDecoder.
dec.width = transform_xsize
dec.height = transform_ysize
let num_bits = dec.hdr.huffman_subsample_bits
dec.hdr.huffman_xsize = sub_sample_size(transform_xsize, num_bits)
dec.hdr.huffman_mask = ~(usize)0 if num_bits == 0 else ((usize)1 << num_bits) - 1
var nothing: u32[]
if is_level0:
return nothing
let data = try new u32[transform_xsize * transform_ysize] --- in memory.heap
errdefer free(data) in memory.heap
try decode_image_data(dec, data.data, transform_xsize, transform_ysize, transform_ysize)
if dec.br.eos:
error(corrupt, "VP8L sub-image data ends early")
dec.last_pixel = 0
dec.hdr.clear()
return data
## DecodeImageData: pixels of the stream into `data` (`width` by `height`) up to row
## `last_row`, handing rows on to the sink every sixteen rows and at the end.
func decode_image_data(dec: Lossless*, data: u32*, width: usize, height: usize, last_row: usize) -> !:
var row = dec.last_pixel // width
var col = dec.last_pixel % width
let br = &dec.br
let hdr = &dec.hdr
var src = dec.last_pixel
var last_cached = src
let src_end = width * height
let src_last = width * last_row
let len_code_limit = num_literal_codes + num_length_codes
let color_cache_limit = len_code_limit + (u32)hdr.color_cache_size
let use_cache = hdr.color_cache_size > 0
let mask = hdr.huffman_mask
let codes = hdr.huffman_tables.codes.data
var group: const TreeGroup* = &hdr.htree_groups[0]
if src < src_last:
group = group_for_pos(hdr, col, row)
while src < src_last:
# Only when the tile changes.
if (col & mask) == 0:
group = group_for_pos(hdr, col, row)
if group.is_trivial_code:
data[src] = group.literal_arb
else:
br.fill_bit_window()
var code: u32 = 0
var have_symbol = true
if group.use_packed_table:
code = read_packed_symbols(group, br, data + src)
if br.is_end_of_stream():
break
# A whole literal pixel was written.
have_symbol = code != 0
else:
code = read_symbol(codes + group.htrees[huff_green], br)
if have_symbol:
if br.is_end_of_stream():
break
if code < num_literal_codes:
if group.is_trivial_literal:
data[src] = group.literal_arb | (code << 8)
else:
let red_symbol = read_symbol(codes + group.htrees[huff_red], br)
br.fill_bit_window()
let blue_symbol = read_symbol(codes + group.htrees[huff_blue], br)
let alpha_symbol = read_symbol(codes + group.htrees[huff_alpha], br)
if br.is_end_of_stream():
break
data[src] = (alpha_symbol << 24) | (red_symbol << 16) | (code << 8) | blue_symbol
elif code < len_code_limit:
# A backward reference.
let length = get_copy_distance(code - num_literal_codes, br)
let dist_symbol = read_symbol(codes + group.htrees[huff_dist], br)
br.fill_bit_window()
let dist_code = get_copy_distance(dist_symbol, br)
let distance = plane_code_to_distance(width, dist_code)
if br.is_end_of_stream():
break
if src < distance or src_end - src < length:
error(corrupt, "VP8L backward reference is out of range")
copy_block32(data + src, distance, length)
src += length
col += length
while col >= width:
col -= width
row += 1
if row <= last_row and row % num_argb_cache_rows == 0:
try process_rows(dec, row)
if (col & mask) != 0:
group = group_for_pos(hdr, col, row)
if use_cache:
while last_cached < src:
cache_insert(hdr, data[last_cached])
last_cached += 1
continue
elif code < color_cache_limit:
# A color cache hit.
let key = code - len_code_limit
while last_cached < src:
cache_insert(hdr, data[last_cached])
last_cached += 1
data[src] = hdr.color_cache[(usize)key]
else:
error(corrupt, "VP8L symbol is out of range")
# AdvanceByOne.
src += 1
col += 1
if col >= width:
col = 0
row += 1
if row <= last_row and row % num_argb_cache_rows == 0:
try process_rows(dec, row)
if use_cache:
while last_cached < src:
cache_insert(hdr, data[last_cached])
last_cached += 1
br.eos = br.is_end_of_stream()
if br.eos:
error(corrupt, "VP8L data ends early")
# The rows of the last batch.
try process_rows(dec, row if row < last_row else last_row)
dec.last_pixel = src