dymokomi/luce-compress
Source of release 0.9.1
0.9.1 / src / flate / inflate.lucb
#==============================================================================================
#
# flate/inflate - The decoder
#
# DESCRIPTION:
# Symbols decode through a 12-bit table on the next bits of a 64-bit buffer,
# refilled eight bytes at a time; an entry holds the code length, the kind
# (literal, length or distance, end of block), the base value and its extra
# bits. Longer codes, rare in practice,, walk the canonical code. Matches copy
# eight bytes at a time when they are eight or more back.
#
#==============================================================================================
let length_base: u16[29] = [3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258]
let length_extra: u8[29] = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0]
let distance_base: u16[30] = [1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577]
let distance_extra: u8[30] = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13]
let code_order: usize[19] = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]
let literal_kind: u32 = 0
let match_kind: u32 = 1
let end_kind: u32 = 2
let invalid_kind: u32 = 3
## One alphabet's decoding table: (value << 16) | (extra << 8) | (kind << 4) | length
## by the next 12 bits (length 0: a longer code), and the canonical code for those.
struct Table:
var fast: u32[4096]
var counts: u16[16]
var symbols: u16[320]
## 0 literal/length, 1 distance, 2 code lengths.
var alphabet: u32
## The entry of `symbol`, the code length left out.
func entry(symbol: usize) -> u32:
if self.alphabet == 2:
return (u32)symbol << 16
if self.alphabet == 1:
if symbol >= 30:
return invalid_kind << 4
return ((u32)distance_base[symbol] << 16) | ((u32)distance_extra[symbol] << 8) | (match_kind << 4)
if symbol < 256:
return ((u32)symbol << 16) | (literal_kind << 4)
if symbol == 256:
return end_kind << 4
if symbol > 285:
return invalid_kind << 4
return ((u32)length_base[symbol - 257] << 16) | ((u32)length_extra[symbol - 257] << 8) | (match_kind << 4)
## Build from code lengths. Only the code-length alphabet must be complete; a
## lone one-bit code or no codes at all is accepted, as zlib does.
func build(lengths: const u8[], alphabet: u32) -> !:
self.alphabet = alphabet
memory.set(u8[]((u8*)&self.fast[0], 16384), 0)
for n in 0..<(usize)16:
self.counts[n] = 0
for length in lengths:
if length > 15:
error(corrupt, "invalid Huffman code length")
self.counts[(usize)length] += 1
self.counts[0] = 0
var left: i32 = 1
var offsets: u16[16]
var next: u32[16]
var code: u32 = 0
for n in 1..<(usize)16:
left = left * 2 - (i32)self.counts[n]
if left < 0:
error(corrupt, "oversubscribed Huffman tree")
code = (code + (u32)self.counts[n - 1]) << 1
next[n] = code
if n < 15:
offsets[n + 1] = offsets[n] + self.counts[n]
var present: u32 = 0
for n in 1..<(usize)16:
present += (u32)self.counts[n]
if left > 0 and (alphabet == 2 or (present > 0 and (present != 1 or self.counts[1] != 1))):
error(corrupt, "incomplete Huffman tree")
for i in 0..<lengths.length:
let length = (usize)lengths[i]
if length == 0:
continue
self.symbols[(usize)offsets[length]] = (u16)i
offsets[length] += 1
let c = next[length]
next[length] += 1
if length <= 12:
# The table is indexed by the code's bits in stream order: reversed.
var reversed: u32 = 0
for b in 0..<length:
reversed = (reversed << 1) | ((c >> (u32)b) & 1)
let e = self.entry(i) | (u32)length
var at = (usize)reversed
while at < 4096:
self.fast[at] = e
at += (usize)1 << length
## The entry for a code longer than 12 bits at the bottom of `acc`, with its
## length; length 0 when no code matches.
func slow(acc: u64) -> u32:
var code: i32 = 0
var first: i32 = 0
var index: i32 = 0
for length in 1..<(usize)16:
code |= (i32)((acc >> (u64)(length - 1)) & 1)
let count = (i32)self.counts[length]
if code - first < count:
return self.entry((usize)self.symbols[(usize)(index + code - first)]) | (u32)length
index += count
first = (first + count) << 1
code <<= 1
return 0
## Input bits, least significant first, read eight bytes ahead; past the end the
## buffer fills with zeros, counted in `padded`.
struct Stream:
var data: const u8*
var length: usize
var pos: usize
var acc: u64
var bits: u32
var padded: u32
## Where the input goes on once `data` is read, and the bytes read before it.
var more: More?
var context: void*?
var base: usize
func refill():
if self.pos + 8 <= self.length:
self.acc |= memory.read[u64](self.data + self.pos) << (u64)self.bits
self.pos += (usize)((63 - self.bits) >> 3)
self.bits |= 56
return
while self.bits <= 56:
if self.pos < self.length or self.next_piece():
self.acc |= (u64)self.data[self.pos] << (u64)self.bits
self.pos += 1
else:
self.padded += 8
self.bits += 8
func take(count: u32) -> u32:
if self.bits < count:
self.refill()
let value = (u32)(self.acc & (((u64)1 << (u64)count) - 1))
self.acc >>= (u64)count
self.bits -= count
return value
## Whether decoding read past the input.
func overrun() -> bool:
return self.bits < self.padded
## Input bytes consumed, over every piece: whole bytes still in the buffer go back.
func consumed() -> usize:
return self.base + self.pos - (usize)((self.bits - self.padded) >> 3) if self.bits >= self.padded else self.base + self.pos
## The next piece of input, if `more` has one.
func next_piece() -> bool:
let more = self.more else return false
let piece = more(self.context)
if piece.length == 0:
self.more = none
return false
self.base += self.length
self.data = piece.data
self.length = piece.length
self.pos = 0
return true
## Whether every byte of input has been read.
func ended() -> bool:
return self.more == none and self.consumed() >= self.base + self.length
## Inflate the raw DEFLATE stream in `data` into exactly `output`, returning the
## input bytes it used. It stops after a final block, or after a block that ends
## with the input (a segment ending in a sync flush). `progress`, when given, hears
## of every 256 KiB of output and of the end.
pub func inflate_raw(data: const u8[], output: u8[], progress: Progress? = none, context: void*? = none) -> usize!:
var slide = Slide(deliver = none, context = none, base = 0, total = output.length, start = 0)
return try inflate_through(data, none, output, &slide, progress, context)
## Inflate the raw DEFLATE stream in `data` into `output`, at most its
## length: the input bytes used and the output bytes made.
pub func inflate_raw_bounded(data: const u8[], output: u8[]) -> (usize, usize)!:
var slide = Slide(deliver = none, context = none, base = 0, total = output.length, start = 0, open = true)
let used = try inflate_through(data, none, output, &slide, none, none)
return (used, slide.produced)
## Inflate the raw DEFLATE stream in `data`, `total` bytes of output, through
## `through` rather than one buffer the size of it all: each time it
## fills, the bytes not yet handed on go to `deliver`, and the last 32 KiB (all a
## match can reach back) move to its start. The last bytes go at the end. So a
## decoder of a large stream holds a window, not the whole output. It
## takes at least 64 KiB; a few hundred KiB keeps the calls few. The input
## can come in pieces too: once `data` is read, `more` gives the next (empty
## at the end), as a PNG's IDAT chunks, without joining them. Returns the
## input bytes used, over every piece.
pub func inflate_raw_windowed(data: const u8[], through: u8[], total: usize, deliver: Deliver, context: void*?, more: More? = none) -> usize!:
if through.length < minimum_window:
error(invalid, "an inflate window takes at least 64 KiB")
var slide = Slide(deliver = deliver, context = context, base = 0, total = total, start = 0)
return try inflate_through(data, more, through, &slide, none, context)
## Gives a windowed inflate its next piece of input; an empty one at the end.
pub type More = func(void*?) -> const u8[]
## Hears of a windowed inflate's output: the context and bytes that are valid
## only during the call.
pub type Deliver = func(void*?, const u8[]) -> unit!
## The smallest window: the 32 KiB kept, and room past it for more than a match.
let minimum_window: usize = 65536 + 2 * slack
## Room a decode step may need past the check before it: two literals or a
## match of 258, with an 8-byte copy's overshoot.
let slack: usize = 274
## Where a windowed inflate's output goes; `deliver` none for one whole buffer.
struct Slide:
var deliver: Deliver?
var context: void*?
## Output bytes made before the window's start; the whole stream's output.
var base: usize
var total: usize
## The first byte in the window not yet delivered.
var start: usize
## `total` is a limit rather than the exact length.
var open: bool = false
## The whole stream's output, once finished.
var produced: usize = 0
## The window's end the decoder stops short of to slide it.
func edge(size: usize) -> usize:
return size if self.deliver == none else size - slack
## Hand on what is new in `through[..<o]` and keep its last 32 KiB at its
## start; the new output position.
func advance(through: u8[], o: usize) -> usize!:
let deliver = self.deliver else error(corrupt, "deflate stream is longer than its output")
try deliver(self.context, through[self.start..<o])
let keep = window if o > window else o
memory.copy(through, through[o - keep..<o], keep)
self.base += o - keep
self.start = keep
if self.base + keep > self.total:
error(corrupt, "deflate stream is longer than its output")
return keep
## The end: the rest handed on, and the output its promised length.
func finish(through: u8[], o: usize) -> !:
if self.base + o != self.total and not self.open:
error(corrupt, "deflate stream is shorter than its output")
self.produced = self.base + o
if let deliver = self.deliver:
try deliver(self.context, through[self.start..<o])
## Inflate into `output`, whole or as the window `slide` says.
func inflate_through(data: const u8[], more: More?, output: u8[], slide: Slide*, progress: Progress?, context: void*?) -> usize!:
let tables = try new Table[3] in memory.heap
defer free(tables) in memory.heap
var s = Stream(data = data.data, length = data.length, pos = 0, acc = 0, bits = 0, padded = 0, more = more, context = context, base = 0)
let edge = slide.edge(output.length)
var o: usize = 0
var next_report: usize = 262144
while true:
let final_block = s.take(1)
let kind = s.take(2)
if kind == 0:
# Stored: to a byte boundary, then LEN, NLEN and the bytes.
_ = s.take(s.bits & 7)
var count = (usize)s.take(16)
let check = (usize)s.take(16)
if s.overrun():
error(corrupt, "truncated deflate stream")
if check != (count ^ 65535):
error(corrupt, "invalid stored deflate block")
while count > 0:
if o >= edge:
o = try slide.advance(output, o)
let room = output.length - o
if room == 0:
error(corrupt, "stored deflate block overruns its buffers")
if s.bits > s.padded:
# Bytes the bit buffer read ahead come first.
output[o] = (u8)s.take(8)
o += 1
count -= 1
continue
if s.padded > 0 or (s.pos >= s.length and not s.next_piece()):
error(corrupt, "truncated deflate stream")
# The buffer is empty; what a refill read ahead past it is read again.
s.acc = 0
var part = count if count < room else room
part = part if part < s.length - s.pos else s.length - s.pos
memory.copy(output[o..], u8[]((u8*)(s.data + s.pos), part), part)
s.pos += part
o += part
count -= part
elif kind == 3:
error(corrupt, "reserved deflate block type")
else:
if kind == 1:
try fixed_tables(&tables[0], &tables[1])
else:
try dynamic_tables(&s, &tables[0], &tables[1], &tables[2])
o = try decode_block(&s, &tables[0], &tables[1], output, o, edge, slide, progress, context, &next_report)
if s.overrun():
error(corrupt, "truncated deflate stream")
if final_block == 1 or s.ended():
break
try slide.finish(output, o)
if let report = progress:
report(context, o)
return s.consumed()
func fixed_tables(literals: Table*, distances: Table*) -> !:
var lengths: u8[288]
for i in 0..<(usize)288:
lengths[i] = 8 if i < 144 else 9 if i < 256 else 7 if i < 280 else 8
try literals.build(lengths, 0)
# All 32 five-bit codes, though 30 and 31 never occur.
var short: u8[32]
for i in 0..<(usize)32:
short[i] = 5
try distances.build(short, 1)
func dynamic_tables(s: Stream*, literals: Table*, distances: Table*, codes: Table*) -> !:
let nlit = (usize)s.take(5) + 257
let ndist = (usize)s.take(5) + 1
let ncode = (usize)s.take(4) + 4
if nlit > 286 or ndist > 30:
error(corrupt, "too many deflate codes")
var code_lengths: u8[19]
for i in 0..<ncode:
code_lengths[code_order[i]] = (u8)s.take(3)
try codes.build(code_lengths, 2)
var lengths: u8[320]
var n: usize = 0
while n < nlit + ndist:
if s.bits < 16:
s.refill()
var e = codes.fast[(usize)(s.acc & 2047)]
if e & 15 == 0:
e = codes.slow(s.acc)
if e & 15 == 0:
error(corrupt, "invalid Huffman symbol")
s.acc >>= (u64)(e & 15)
s.bits -= e & 15
let symbol = e >> 16
if symbol < 16:
lengths[n] = (u8)symbol
n += 1
continue
if symbol == 16 and n == 0:
error(corrupt, "deflate repeat has no previous length")
let count = (usize)s.take(2 if symbol == 16 else 3 if symbol == 17 else 7) + (11 if symbol == 18 else 3)
if count > nlit + ndist - n:
error(corrupt, "deflate code repeat exceeds table")
let value = lengths[n - 1] if symbol == 16 else 0
for i in 0..<count:
lengths[n + i] = value
n += count
if lengths[256] == 0:
error(corrupt, "deflate tree lacks end marker")
try literals.build(lengths[..<nlit], 0)
try distances.build(lengths[nlit..<nlit + ndist], 1)
## Decode one Huffman block into `output` from `o`; the new output position.
## Past `edge` the window slides first (a whole buffer's limit is its end).
func decode_block(s: Stream*, literals: const Table*, distances: const Table*, output: u8[], start: usize, edge: usize, slide: Slide*, progress: Progress?, context: void*?, next_report: usize*) -> usize!:
let out = output.data
let size = output.length
let lit = &literals.fast[0]
let dist = &distances.fast[0]
var o = start
var acc = s.acc
var bits = s.bits
var input = s.data
var input_end = s.length
# The fast loop, while 16 bytes of input and a match's worth of output
# (before the slide's edge) are left: one branchless refill a symbol,
# no output checks, and copies free to run over by a word. Its
# arithmetic wraps and its shift counts are masked: the loop's bounds
# already keep every value in range, so no check is needed.
var pos = s.pos
let fast_end = (edge if edge < size else size) -| slack
let fast_input = input_end -| 16
while o < fast_end and pos <= fast_input:
acc |= memory.read[u64](input + pos) << (u64)(bits & 63)
pos = pos +% (usize)((63 -% bits) >> 3)
bits |= 56
var e = lit[(usize)(acc & 4095)]
if e & 15 == 0:
e = literals.slow(acc)
if e & 15 == 0:
error(corrupt, "invalid Huffman symbol")
acc >>= (u64)(e & 15)
bits = bits -% (e & 15)
let kind = (e >> 4) & 3
if kind == literal_kind:
out[o] = (u8)(e >> 16)
o = o +% 1
# Two more literals without refilling: at least 41 bits remain.
let second = lit[(usize)(acc & 4095)]
if second & 15 == 0 or (second >> 4) & 3 != literal_kind: continue
acc >>= (u64)(second & 15)
bits = bits -% (second & 15)
out[o] = (u8)(second >> 16)
o = o +% 1
let third = lit[(usize)(acc & 4095)]
if third & 15 == 0 or (third >> 4) & 3 != literal_kind: continue
acc >>= (u64)(third & 15)
bits = bits -% (third & 15)
out[o] = (u8)(third >> 16)
o = o +% 1
continue
if kind == end_kind:
s.acc = acc
s.bits = bits
s.pos = pos
return o
if kind == invalid_kind:
error(corrupt, "invalid deflate length symbol")
# A match: its extra bits, distance code and extra bits fit the 41 left.
let extra = (e >> 8) & 15
let length = (usize)(e >> 16) +% (usize)(acc & ((((u64)1) << (u64)extra) -% 1))
acc >>= (u64)extra
bits = bits -% extra
var d = dist[(usize)(acc & 4095)]
if d & 15 == 0:
d = distances.slow(acc)
if d & 15 == 0:
error(corrupt, "invalid Huffman symbol")
acc >>= (u64)(d & 15)
bits = bits -% (d & 15)
if (d >> 4) & 3 != match_kind:
error(corrupt, "invalid deflate distance symbol")
let dextra = (d >> 8) & 15
let distance = (usize)(d >> 16) +% (usize)(acc & ((((u64)1) << (u64)dextra) -% 1))
acc >>= (u64)dextra
bits = bits -% dextra
if distance > o or distance > 32768:
error(corrupt, "invalid deflate back reference")
let to = out + o
let back = out + (o -% distance)
if distance >= 8:
var n: usize = 0
while n < length:
memory.write[u64](to + n, memory.read[u64](back + n))
n = n +% 8
elif distance == 1:
memory.set(u8[](to, length), *back)
else:
# A short period: its first eight-or-more bytes one by one, then
# words from that far back (a multiple of the period).
let period = distance * ((8 + distance - 1) // distance)
var n: usize = 0
while n < period and n < length:
to[n] = back[n]
n = n +% 1
while n < length:
memory.write[u64](to + n, memory.read[u64](to + (n -% period)))
n = n +% 8
o = o +% length
if o >= *next_report:
if let report = progress:
report(context, o)
*next_report = o + 262144
s.pos = pos
while true:
# A symbol that read past the input (into the zeros a refill pads it with) ends
# the stream here, rather than its zeros decoding on to the output's limit.
if bits < s.padded:
error(corrupt, "truncated deflate stream")
if o > edge:
o = try slide.advance(output, o)
if bits < 48:
# Eight bytes at once while the input has them.
if s.pos + 8 <= input_end:
acc |= memory.read[u64](input + s.pos) << (u64)bits
s.pos += (usize)((63 - bits) >> 3)
bits |= 56
else:
s.acc = acc
s.bits = bits
s.refill()
acc = s.acc
bits = s.bits
# The refill may have gone on to the next piece of input.
input = s.data
input_end = s.length
var e = lit[(usize)(acc & 4095)]
if e & 15 == 0:
e = literals.slow(acc)
if e & 15 == 0:
error(corrupt, "invalid Huffman symbol")
acc >>= (u64)(e & 15)
bits = bits -% (e & 15)
let kind = (e >> 4) & 3
if kind == literal_kind:
if o >= size:
error(corrupt, "deflate stream is longer than its output")
out[o] = (u8)(e >> 16)
o += 1
# A second literal without refilling: at least 33 bits remain.
let next = lit[(usize)(acc & 4095)]
if next & 15 != 0 and (next >> 4) & 3 == literal_kind and o < size:
acc >>= (u64)(next & 15)
bits = bits -% (next & 15)
out[o] = (u8)(next >> 16)
o += 1
continue
if kind == end_kind:
break
if kind == invalid_kind:
error(corrupt, "invalid deflate length symbol")
let extra = (e >> 8) & 15
let length = (usize)(e >> 16) + (usize)(acc & (((u64)1 << (u64)extra) - 1))
acc >>= (u64)extra
bits -= extra
var d = dist[(usize)(acc & 4095)]
if d & 15 == 0:
d = distances.slow(acc)
if d & 15 == 0:
error(corrupt, "invalid Huffman symbol")
acc >>= (u64)(d & 15)
bits -= d & 15
if (d >> 4) & 3 != match_kind:
error(corrupt, "invalid deflate distance symbol")
let dextra = (d >> 8) & 15
let distance = (usize)(d >> 16) + (usize)(acc & (((u64)1 << (u64)dextra) - 1))
acc >>= (u64)dextra
bits -= dextra
if distance > o or distance > 32768:
error(corrupt, "invalid deflate back reference")
if length > size - o:
error(corrupt, "deflate stream is longer than its output")
let to = out + o
let back = out + (o - distance)
if distance >= 8 and o + length + 8 <= size:
var n: usize = 0
while n < length:
memory.write[u64](to + n, memory.read[u64](back + n))
n += 8
elif distance == 1:
memory.set(u8[](to, length), *back)
else:
for n in 0..<length:
to[n] = back[n]
o += length
if o >= *next_report:
if let report = progress:
report(context, o)
*next_report = o + 262144
s.acc = acc
s.bits = bits
return o