Luce packages
LuceLuce BaseLuciaOS

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]