dymokomi/luce-raw
Source of release 0.8.2
#==============================================================================================
#
# raw/bits - Bit readers and canonical Huffman tables
#
# DESCRIPTION:
# Most raw codings read their bits most significant first. Bits keeps up to 64
# of them buffered; JPEG streams additionally drop the zero byte stuffed after
# each 0xFF and stop at a marker. Past the data the reader supplies zero bits,
# but consuming them is an error, so a truncated stream fails instead of
# decoding garbage. Huffman is the lookup table form of a canonical code: one
# entry per `bits`-bit prefix holding the code length and its symbol.
#
#==============================================================================================
## A most-significant-first bit reader over `data` from `position`.
struct Bits:
var data: const u8[]
var position: usize
var buffer: u64
var count: u32
var padding: u32
var stuffed: bool
var marker: bool
# Set by decoders that report a corrupt stream once per line rather than
# per code (fuji_compressed.lucb); they check it and fail.
var fault: bool
## Top the buffer up to at least 57 bits, with zero padding past the data or
## at a JPEG marker: eight bytes at once where no 0xFF hides among them,
## byte by byte otherwise.
func fill():
if self.count <= 56 and not self.marker and self.position + 8 <= self.data.length:
let p = self.data.data + self.position
let word = ((u64)p[0] << 56) | ((u64)p[1] << 48) | ((u64)p[2] << 40) | ((u64)p[3] << 32) | ((u64)p[4] << 24) | ((u64)p[5] << 16) | ((u64)p[6] << 8) | (u64)p[7]
let inverse = ~word
if not self.stuffed or ((inverse -% 0x0101010101010101) & ~inverse & 0x8080808080808080) == 0:
let take = (64 - self.count) >> 3
let bits = take * 8
self.buffer |= (word >> (64 - bits)) << (64 - self.count - bits)
self.position += (usize)take
self.count += bits
return
while self.count <= 56:
var byte: u64 = 0
if not self.marker and self.position < self.data.length:
byte = (u64)self.data[self.position]
if self.stuffed and byte == 255:
if self.position + 1 < self.data.length and self.data[self.position + 1] == 0:
self.position += 2
else:
self.marker = true
byte = 0
self.padding += 8
else:
self.position += 1
else:
self.padding += 8
self.buffer |= byte << (56 - self.count)
self.count += 8
## The next `n` bits (at most 32) without consuming them.
func peek(n: u32) -> u32:
if self.count < n:
self.fill()
if n == 0:
return 0
return (u32)(self.buffer >> (64 - n))
## Consume `n` bits already peeked; an error when they run past the data.
func skip(n: u32) -> !:
if self.count < n:
self.fill()
self.buffer = self.buffer << n if n < 64 else 0
self.count -= n
if self.count < self.padding:
error(corrupt, "raw bit stream is truncated")
## Read `n` bits (at most 32).
func read(n: u32) -> u32!:
let value = self.peek(n)
try self.skip(n)
return value
## Skip to just past the next JPEG restart marker and start afresh there, as
## each restart interval begins on a byte boundary. The marker stops `fill`,
## so no buffered byte lies beyond it.
func restart() -> !:
var at = self.position
while at + 1 < self.data.length and not (self.data[at] == 255 and self.data[at + 1] >= 0xd0 and self.data[at + 1] <= 0xd7):
at += 1
if at + 1 >= self.data.length:
error(corrupt, "JPEG restart marker missing")
self.position = at + 2
self.buffer = 0
self.count = 0
self.padding = 0
self.marker = false
## A canonical Huffman code as a table indexed by the next `bits` bits: each
## entry is the code's length shifted left eight, or'd with its symbol; zero
## marks a prefix no code begins.
struct Huffman:
var table: u16[]
var bits: u32
## The code with `counts[n]` codes of length n + 1 and the symbols in order.
static func build(counts: const u8[], symbols: const u8[]) -> Huffman!:
if counts.length != 16:
error(corrupt, "Huffman table needs sixteen counts")
var longest: u32 = 0
var total: usize = 0
for n: usize in 0..<16:
if counts[n] != 0:
longest = (u32)n + 1
total += (usize)counts[n]
if longest == 0 or total > symbols.length or total > 256:
error(corrupt, "invalid Huffman table")
let table = try new u16[(usize)1 << longest] in memory.heap
var code: usize = 0
var index: usize = 0
for length in 1..=(usize)longest:
for i in 0..<(usize)counts[length - 1]:
let span = (usize)1 << ((usize)longest - length)
if code + span > table.length:
free(table) in memory.heap
error(corrupt, "Huffman code lengths overflow")
for j in 0..<span:
table[code + j] = (u16)(length << 8) | (u16)symbols[index]
code += span
index += 1
return Huffman(table = table, bits = longest)
## A code given as a ready table, as some raw formats describe theirs.
static func custom(bits: u32, entries: const u16[]) -> Huffman!:
if bits == 0 or bits > 16 or entries.length != (usize)1 << bits:
error(corrupt, "invalid Huffman lookup table")
let table = try new u16[entries.length] in memory.heap
memory.copy(table, entries, entries.length)
return Huffman(table = table, bits = bits)
## The next symbol of `reader`.
func decode(reader: Bits*) -> u32!:
let entry = self.table[(usize)reader.peek(self.bits)]
if entry == 0:
error(corrupt, "invalid Huffman code in raw data")
try reader.skip((u32)(entry >> 8))
return (u32)(entry & 255)
func close():
if self.table.length > 0:
free(self.table) in memory.heap
self = Huffman()
## The next Huffman-coded JPEG difference: a magnitude category from `table`,
## then that many bits of value, read with one buffer refill.
inline func difference(reader: Bits*, table: const Huffman*) -> i32!:
if reader.count < 32:
reader.fill()
let entry = table.table[(usize)(reader.buffer >> (64 - table.bits))]
if entry == 0:
error(corrupt, "invalid Huffman code in raw data")
let length = (u32)(entry >> 8)
let category = (u32)(entry & 255)
if category > 16:
error(corrupt, "raw difference too long")
let bits = length + (category if category < 16 else 0)
let value = (i32)((reader.buffer << length) >> (64 - category)) if category > 0 and category < 16 else 0
reader.buffer = reader.buffer << bits
reader.count -= bits
if reader.count < reader.padding:
error(corrupt, "raw bit stream is truncated")
if category == 0:
return 0
if category == 16:
return -32768
if (value & ((i32)1 << (category - 1))) == 0:
return value - ((i32)1 << category) + 1
return value