dymokomi/luce-compress
Source of release 0.9.0
0.9.0 / src / flate / deflate.lucb
#==============================================================================================
#
# flate/deflate - The matcher and segment compressor
#
# DESCRIPTION:
# libdeflate's level table: 4-byte hash chains over a 32 KiB window, searched
# `depth` deep and stopped at a `nice` length, and greedy matching at every level
# (level 1 has its own chainless parser, fastest.lucb). Lazy matching, which helps
# text by a few percent, made filtered image rows larger as well as slower (a
# photo's noise makes the literal it spends dear), and images are what this
# module is for; general data goes through `compress`. Matches compare eight bytes at a
# time. Blocks close every 16383 symbols. The chains live in a ring of one window's
# positions (libdeflate's layout), so a chain walk stays in cache however large
# the segment is.
#
#==============================================================================================
## How many chain entries a search visits, and the length that ends it at once:
## libdeflate's levels, with 5 between its 4 and 6 (its 5 is 4's search, lazily).
let level_depth: u16[10] = [0, 4, 6, 12, 16, 24, 35, 100, 300, 600]
let level_nice: u16[10] = [0, 32, 10, 14, 30, 48, 65, 130, 258, 258]
let window: usize = 32768
let window_mask: usize = 32767
## Hash table size: 2^17 heads keep chains to true matches rather than collisions.
let hash_bits: u32 = 16
let block_symbols: usize = 16383
## The most a segment of `n` bytes can take compressed (stored, with its headers).
pub func deflate_bound(n: usize) -> usize:
return n + n // 2048 + 64
## Compress `input` as one DEFLATE segment with a fresh window into `output` (at
## least `deflate_bound` bytes) at `level` 0..9; the bytes written. The segment
## ends in a final block when `last`, else in a sync flush (an empty stored block),
## so segments concatenate into one stream.
pub func deflate_raw(input: const u8[], level: i32, output: u8[], last: bool) -> usize!:
if level < 0 or level > 9:
error(invalid, "deflate level must be 0 through 9")
let n = input.length
if output.length < deflate_bound(n):
error(limit, "deflate output is smaller than deflate_bound")
var c = Compressor(symbols = Symbols.make(), w = Writer(out = output.data, pos = 0, acc = 0, bits = 0))
defer c.close()
try c.open(n, level)
let data = input.data
if level == 0:
write_stored(&c.w, data, 0, n, last)
elif level == 1:
try compress_fastest(&c, data, n, last)
else:
try c.greedy(data, n, last)
if not last:
c.w.put(0, 3)
c.w.align()
for byte in [0, 0, 255, 255]:
c.w.out[c.w.pos] = (u8)byte
c.w.pos += 1
c.w.align()
return c.w.pos
## A zlib stream of `input` at `level` into `output` (at least `deflate_bound`
## plus 6 bytes): header, one segment and the Adler-32; the bytes written.
pub func deflate_zlib(input: const u8[], level: i32, output: u8[]) -> usize!:
if output.length < deflate_bound(input.length) + 6:
error(limit, "deflate output is smaller than deflate_bound")
let header = zlib_header(level)
output[0] = header[0]
output[1] = header[1]
let used = 2 + try deflate_raw(input, level, output[2..], true)
let adler = adler32(input)
output[used] = (u8)(adler >> 24)
output[used + 1] = (u8)(adler >> 16)
output[used + 2] = (u8)(adler >> 8)
output[used + 3] = (u8)adler
return used + 4
## A zlib stream's payload inflated into exactly `output`, header and Adler-32
## checked; the bytes of `data` it used.
pub func inflate_zlib(data: const u8[], output: u8[]) -> usize!:
if data.length < 6 or (data[0] & 15) != 8 or data[0] >> 4 > 7 or (((u32)data[0] << 8) | (u32)data[1]) % 31 != 0:
error(corrupt, "invalid zlib header")
if (data[1] & 32) != 0:
error(corrupt, "preset zlib dictionaries are not supported")
let used = try inflate_raw(data[2..], output)
let at = 2 + used
if data.length - at < 4:
error(corrupt, "truncated zlib stream")
let stored = ((u32)data[at] << 24) | ((u32)data[at + 1] << 16) | ((u32)data[at + 2] << 8) | (u32)data[at + 3]
if stored != adler32(output):
error(corrupt, "zlib Adler checksum mismatch")
return at + 4
## A zlib stream of unknown length inflated through a 256 KiB window: each
## run of output goes to `deliver` (valid during the call), at most
## `maximum` bytes in all; the header and Adler-32 are checked. The bytes of
## `data` it used.
pub func inflate_zlib_streamed(data: const u8[], maximum: usize, deliver: Deliver, context: void*?) -> usize!:
if data.length < 6 or (data[0] & 15) != 8 or data[0] >> 4 > 7 or (((u32)data[0] << 8) | (u32)data[1]) % 31 != 0:
error(corrupt, "invalid zlib header")
if (data[1] & 32) != 0:
error(corrupt, "preset zlib dictionaries are not supported")
let through = try new u8[262144] --- in memory.heap
defer free(through) in memory.heap
var check = Checked(deliver = deliver, context = context, adler = 1)
var slide = Slide(deliver = checked_deliver, context = (void*)&check, base = 0, total = maximum, start = 0, open = true)
let used = try inflate_through(data[2..], none, through, &slide, none, none)
let at = 2 + used
if data.length - at < 4:
error(corrupt, "truncated zlib stream")
let stored = ((u32)data[at] << 24) | ((u32)data[at + 1] << 16) | ((u32)data[at + 2] << 8) | (u32)data[at + 3]
if stored != check.adler:
error(corrupt, "zlib Adler checksum mismatch")
return at + 4
## A raw DEFLATE stream of unknown length inflated through a 256 KiB window, as
## `inflate_zlib_streamed` does for zlib: each run of output goes to `deliver` (valid
## during the call), at most `maximum` bytes in all. It ends after the final block (or
## a block that ends `data`); the bytes of `data` it used, so a caller framing several
## streams (gzip members) knows where the next begins.
pub func inflate_raw_streamed(data: const u8[], maximum: usize, deliver: Deliver, context: void*?) -> usize!:
let through = try new u8[262144] --- in memory.heap
defer free(through) in memory.heap
var slide = Slide(deliver = deliver, context = context, base = 0, total = maximum, start = 0, open = true)
return try inflate_through(data, none, through, &slide, none, none)
## A streamed inflate's receiver: the caller's, and the Adler-32 so far.
struct Checked:
var deliver: Deliver
var context: void*?
var adler: u32
func checked_deliver(context: void*?, bytes: const u8[]) -> !:
let check = (Checked*)(context else return)
check.adler = adler32(bytes, check.adler)
try check.deliver(check.context, bytes)
struct Compressor:
var symbols: Symbols
var head: i32[]
var prev: i32[]
var block: Block
var w: Writer
var level: usize
var depth: usize
var nice: usize
## Input the current block starts at.
var block_start: usize
func open(n: usize, level: i32) -> !:
self.level = (usize)level
self.depth = (usize)level_depth[self.level]
self.nice = (usize)level_nice[self.level]
# A parser checks the count before each symbol, so one slot past the
# count at which a block closes is enough.
self.block.litlen = try new u16[block_symbols + 1] --- in memory.heap
self.block.distance = try new u16[block_symbols + 1] --- in memory.heap
self.block.clear()
if level > 0:
self.head = try new i32[(usize)1 << hash_bits] --- in memory.heap
# -1 in every head: all bytes 0xFF.
memory.set(u8[]((u8*)self.head.data, self.head.length * 4), 255)
# Each position's predecessor, at its place in the window's ring; a walk
# stops before a position the ring has since reused.
self.prev = try new i32[window] --- in memory.heap
func close():
if self.head.length > 0:
free(self.head) in memory.heap
if self.prev.length > 0:
free(self.prev) in memory.heap
if self.block.litlen.length > 0:
free(self.block.litlen) in memory.heap
if self.block.distance.length > 0:
free(self.block.distance) in memory.heap
## Write the block of symbols so far, covering input up to `end`.
func flush(data: const u8*, start: usize, end: usize, final_block: bool) -> !:
write_block(&self.w, &self.block, &self.symbols, data, start, end, final_block)
self.block.clear()
self.block_start = end
## Record a literal. The block's arrays have room past `block_symbols` for
## every symbol a parser adds before it next checks the count, so the writes
## need no checks of their own.
func literal(value: u8):
let b = &self.block
let k = b.count
b.litlen.data[k] = (u16)value
b.distance.data[k] = 0
b.count = k +% 1
let freq = (u32*)&b.literal_freq[0]
freq[(usize)value] = freq[(usize)value] +% 1
## Record a match of 3..258 bytes at distance 1..32768.
func matched(length: usize, distance: usize):
let b = &self.block
let k = b.count
b.litlen.data[k] = (u16)length
b.distance.data[k] = (u16)distance
b.count = k +% 1
let freq = (u32*)&b.literal_freq[0]
let code = 257 +% (usize)((const u8*)&self.symbols.length_code[0])[length]
freq[code] = freq[code] +% 1
let dfreq = (u32*)&b.distance_freq[0]
let dcode = self.symbols.distance_code(distance)
dfreq[dcode] = dfreq[dcode] +% 1
## Enter position `p` (with four bytes ahead) in the hash chains; the previous
## position with the same hash, or -1. Four bytes, as zlib-ng hashes, make far
## shorter chains than three on image data for a sliver of compression.
func insert(data: const u8*, p: usize) -> i32:
let key = memory.read[u32](data + p)
let h = (usize)((key *% 2654435761) >> (32 - hash_bits))
let heads = self.head.data
let earlier = heads[h]
self.prev.data[p & window_mask] = earlier
heads[h] = (i32)p
return earlier
## The longest match at `p` among the chain from `candidate`, better than
## `best` (else 0); its distance. A candidate must share the four bytes
## ending at the best length so far, then the first four, before it is
## measured (libdeflate's order: the tail rejects most candidates). The hot
## loop uses wrapping arithmetic, whose values stay far from overflow.
func longest(data: const u8*, n: usize, p: usize, candidate: i32, best: usize, depth: usize) -> (usize, usize):
let most = n - p if n - p < 258 else 258
var length = best if best >= 3 else 3
if most < 4 or length >= most:
return (0, 0)
var distance: usize = 0
var chain = depth
var cur = candidate
let here = data + p
let head4 = memory.read[u32](here)
var tail = memory.read[u32](here + (length -% 3))
let prev = self.prev.data
let nice = self.nice
# No candidate below the window; -1 (no candidate) is below it too.
let lowest = (i32)(p - window if p > window else 0)
while true:
cur = walk(data, prev, cur, lowest, &chain, length -% 3, tail, head4)
if cur < 0:
break
let at = (usize)cur
let found = match_length(data + at + 4, here + 4, most -% 4) +% 4
if found > length:
length = found
distance = p -% at
if found >= nice:
break
if found >= most:
break
tail = memory.read[u32](here + (length -% 3))
cur = prev[at & window_mask]
return (length, distance) if distance > 0 else (0, 0)
## Enter positions `first..<stop` in the hash chains, as a match covers them
## (as `insert` does, with the tables in hand).
func skip(data: const u8*, n: usize, first: usize, stop: usize):
let end = stop if stop +% 4 <= n else (n - 3 if n > 3 else 0)
let heads = self.head.data
let prev = self.prev.data
var k = first
while k < end:
let h = (usize)((memory.read[u32](data + k) *% 2654435761) >> (32 - hash_bits))
prev[k & window_mask] = heads[h]
heads[h] = (i32)k
k = k +% 1
func greedy(data: const u8*, n: usize, last: bool) -> !:
var p: usize = 0
while p < n:
if self.block.count >= block_symbols:
try self.flush(data, self.block_start, p, false)
var length: usize = 0
var distance: usize = 0
if p + 4 <= n:
let candidate = self.insert(data, p)
let (found, d) = self.longest(data, n, p, candidate, 2, self.depth)
length = found
distance = d
if length < 3 or (length == 3 and distance > 8192):
self.literal(data[p])
p += 1
continue
self.matched(length, distance)
self.skip(data, n, p + 1, p + length)
p += length
try self.flush(data, self.block_start, n, last)
## Follow the chain from `cur` for at most `*steps` entries, not below `lowest`,
## to the first position whose four bytes at `offset` are `tail` and whose first
## four are `head4`; -1 when there is none. Kept apart from `longest` so the
## walk, where the search spends its time, holds few values.
func walk(data: const u8*, prev: const i32*, first: i32, lowest: i32, steps: usize*, offset: usize, tail: u32, head4: u32) -> i32:
var cur = first
var left = *steps
while left > 0:
if cur < lowest:
break
let there = data + (usize)cur
left = left -% 1
if memory.read[u32](there + offset) == tail:
if memory.read[u32](there) == head4:
*steps = left
return cur
cur = prev[(usize)cur & window_mask]
*steps = 0
return -1
## Bytes equal at the start of `a` and `b`, at most `most`: eight at a time,
## the first difference found from the lowest differing bit.
func match_length(a: const u8*, b: const u8*, most: usize) -> usize:
var n: usize = 0
while n +% 8 <= most:
let x = memory.read[u64](a + n) ^ memory.read[u64](b + n)
if x != 0:
return n +% (lowest_bit(x) >> 3)
n = n +% 8
while n < most:
if a[n] != b[n]:
return n
n = n +% 1
return n
## The index of the lowest set bit of a nonzero word (de Bruijn, whose index is
## below 64 by construction).
func lowest_bit(x: u64) -> usize:
let table = (const u8*)&debruijn[0]
return (usize)table[(usize)(((x & -%x) *% 0x03F79D71B4CB0A89) >> 58)]
let debruijn: u8[64] = [0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4, 62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5, 63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11, 46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6]