Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / flate / fastest.lucb

#==============================================================================================
#
#   flate/fastest - Level 1: libdeflate's fastest parser
#
#   DESCRIPTION:
#       No hash chains: each 4-byte hash names a bucket of the two most recent positions
#       with it, and a position takes the longer of their matches (four bytes at least),
#       greedily. A match's covered positions still enter the buckets, so later text
#       finds them. About three times the speed of the chained greedy parser for a few
#       percent of size.
#
#==============================================================================================

## Bucket hash table size: 2^15 buckets of two positions.
let fastest_bits: u32 = 15
## A match this long ends the search at once.
let fastest_nice: usize = 32

## Compress `data[0..<n]` into `c`'s writer at level 1.
func compress_fastest(c: Compressor*, data: const u8*, n: usize, last: bool) -> !:
    let buckets = try new i32[(usize)2 << fastest_bits] --- in memory.heap
    defer free(buckets) in memory.heap
    memory.set(u8[]((u8*)buckets.data, buckets.length * 4), 255)
    let table = buckets.data
    var p: usize = 0
    while p < n:
        if c.block.count >= block_symbols:
            try c.flush(data, c.block_start, p, false)
        if p +% 5 > n:
            c.literal(data[p])
            p = p +% 1
            continue
        let here = data + p
        let seq = memory.read[u32](here)
        let h = (usize)((seq *% 2654435761) >> (32 - fastest_bits)) << 1
        let first = table[h]
        let second = table[h + 1]
        table[h] = (i32)p
        table[h + 1] = first
        let most = n - p if n - p < 258 else 258
        let lowest = (i32)(p - window if p > window else 0)
        var length: usize = 0
        var distance: usize = 0
        if first >= lowest and memory.read[u32](data + (usize)first) == seq:
            length = match_length(data + (usize)first + 4, here + 4, most -% 4) +% 4
            distance = p -% (usize)first
        if length < fastest_nice and second >= lowest and memory.read[u32](data + (usize)second) == seq:
            let other = match_length(data + (usize)second + 4, here + 4, most -% 4) +% 4
            if other > length:
                length = other
                distance = p -% (usize)second
        if length < 4:
            c.literal(data[p])
            p = p +% 1
            continue
        c.matched(length, distance)
        # The covered positions enter their buckets too.
        let end = p + length
        let stop = end if end +% 5 <= n else (n - 4 if n > 4 else 0)
        var k = p +% 1
        while k < stop:
            let kh = (usize)((memory.read[u32](data + k) *% 2654435761) >> (32 - fastest_bits)) << 1
            table[kh + 1] = table[kh]
            table[kh] = (i32)k
            k = k +% 1
        p = end
    try c.flush(data, c.block_start, n, last)