dymokomi/luce-compress
Source of release 0.9.1
0.9.1 / src / zstd / match.lucb
#==============================================================================================
#
# zstd/match - The encoder's match finders
#
# DESCRIPTION:
# A block's input becomes sequences: literals, then a match at an offset back. The
# finders keep hash tables of input positions (absolute, the frame being one
# input), so a match may reach into earlier blocks, up to the window.
#
# - `greedy` (levels 1 and 2): one table of 5-byte hashes; the first match found
# is taken, and over input that does not match the step grows.
# - `double` (levels 3 to 5): a table of 8-byte hashes beside the 5-byte one; a
# long match is preferred, and a short one is tried against a long one a byte
# later (as zstd's dfast strategy does).
# - `lazy` (levels 6 to 9, chain.lucb): hash chains searched to a depth, and a
# match deferred while the next position offers a better one.
#
# Each finder first tries the most recent offset a byte ahead, which costs the
# fewest bits to send.
#
#==============================================================================================
## A match found: its length (0 for none) and offset.
struct Found:
var length: usize
var offset: usize
## One sequence of a block: literals, then a match.
struct Sequence:
var literals: u32
var length: u32
var offset: u32
## The parameters of a level.
struct Level:
var strategy: u32
var window_log: u32
var hash_log: u32
var long_log: u32
var chain_log: u32
var depth: u32
var lazy: u32
let strategy_greedy: u32 = 0
let strategy_double: u32 = 1
let strategy_lazy: u32 = 2
## The parameters of `level` (levels past 9 are 9).
func level_parameters(level: i32) -> Level:
if level <= 1: return Level(strategy_greedy, 21, 15, 0, 0, 0, 0)
if level == 2: return Level(strategy_greedy, 21, 16, 0, 0, 0, 0)
if level == 3: return Level(strategy_double, 21, 16, 17, 0, 0, 0)
if level == 4: return Level(strategy_double, 22, 17, 18, 0, 0, 0)
if level == 5: return Level(strategy_double, 22, 18, 19, 0, 0, 0)
if level == 6: return Level(strategy_lazy, 22, 17, 0, 17, 8, 1)
if level == 7: return Level(strategy_lazy, 23, 18, 0, 18, 12, 1)
if level == 8: return Level(strategy_lazy, 23, 18, 0, 18, 16, 2)
return Level(strategy_lazy, 23, 19, 0, 19, 32, 2)
inline func hash5(value: u64, bits: u32) -> usize:
return (usize)(((value << 24) *% 889523592379) >> (u64)(64 - bits))
inline func hash8(value: u64, bits: u32) -> usize:
return (usize)((value *% 0xCF1BBCDCB7A56463) >> (u64)(64 - bits))
## How many bytes at `a` and `b` (b after a) agree, reading no further than `end`.
inline func count_match(base: const u8*, a: usize, b: usize, end: usize) -> usize:
var length: usize = 0
while b + length + 8 <= end:
let difference = memory.read[u64](base + a + length) ^ memory.read[u64](base + b + length)
if difference != 0:
var bits = difference
while bits & 255 == 0:
bits >>= 8
length += 1
return length
length += 8
while b + length < end and base[a + length] == base[b + length]:
length += 1
return length
extend Compressor:
## Note a sequence: the literals from `anchor` to `at`, then `found`.
inline func emit(anchor: usize, at: usize, found: Found):
let count = at - anchor
if count > 0: memory.copy(self.literals[self.literal_count..], self.input[anchor..<at], count)
self.literal_count += count
self.sequences[self.sequence_count] = Sequence((u32)count, (u32)found.length, (u32)found.offset)
self.sequence_count += 1
self.recent1 = self.recent0
self.recent0 = found.offset
## The most recent offset's match at `at`, at least 4 bytes, or none.
inline func repeat_at(at: usize, end: usize) -> Found:
var found: Found
let offset = self.recent0
if offset == 0 or offset > at: return found
let base = self.input.data
if memory.read[u32](base + at) != memory.read[u32](base + at - offset): return found
found.length = 4 + count_match(base, at - offset + 4, at + 4, end)
found.offset = offset
return found
## Whether `candidate` is a usable earlier position for `at`.
inline func reachable(candidate: usize, at: usize) -> bool:
return candidate < at and at - candidate <= self.window
## Sequences of the input `start..<end` by the greedy finder.
func find_greedy(start: usize, end: usize):
let base = self.input.data
let table = self.hashes.data
let bits = self.level.hash_log
var at = start
var anchor = start
while at + 8 <= end:
let repeat = self.repeat_at(at + 1, end)
if repeat.length > 0:
self.emit(anchor, at + 1, repeat)
at += 1 + repeat.length
anchor = at
continue
let slot = hash5(memory.read[u64](base + at), bits)
let candidate = (usize)table[slot]
table[slot] = (u32)at
if self.reachable(candidate, at) and memory.read[u32](base + candidate) == memory.read[u32](base + at):
var found = Found(4 + count_match(base, candidate + 4, at + 4, end), at - candidate)
# Extend backward over literals that also match.
var first = at
var source = candidate
while first > anchor and source > 0 and base[first - 1] == base[source - 1]:
first -= 1
source -= 1
found.length += 1
self.emit(anchor, first, found)
at = first + found.length
anchor = at
# Hash a position inside the match for the next search.
if at + 8 <= end: table[hash5(memory.read[u64](base + at - 2), bits)] = (u32)(at - 2)
continue
at += 1 + ((at - anchor) >> 6)
self.finish(anchor, end)
## Sequences of the input `start..<end` by the double-hash finder.
func find_double(start: usize, end: usize):
let base = self.input.data
let short = self.hashes.data
let long = self.long_hashes.data
let short_bits = self.level.hash_log
let long_bits = self.level.long_log
var at = start
var anchor = start
while at + 8 <= end:
let repeat = self.repeat_at(at + 1, end)
if repeat.length > 0:
self.emit(anchor, at + 1, repeat)
at += 1 + repeat.length
anchor = at
continue
let word = memory.read[u64](base + at)
let long_slot = hash8(word, long_bits)
let short_slot = hash5(word, short_bits)
let long_candidate = (usize)long[long_slot]
let short_candidate = (usize)short[short_slot]
long[long_slot] = (u32)at
short[short_slot] = (u32)at
var found: Found
var first = at
if self.reachable(long_candidate, at) and memory.read[u64](base + long_candidate) == word:
found = Found(8 + count_match(base, long_candidate + 8, at + 8, end), at - long_candidate)
elif self.reachable(short_candidate, at) and memory.read[u32](base + short_candidate) == (u32)word:
found = Found(4 + count_match(base, short_candidate + 4, at + 4, end), at - short_candidate)
# A long match a byte later wins over a short one here.
if at + 9 <= end:
let next_word = memory.read[u64](base + at + 1)
let next_slot = hash8(next_word, long_bits)
let next_candidate = (usize)long[next_slot]
long[next_slot] = (u32)(at + 1)
if self.reachable(next_candidate, at + 1) and memory.read[u64](base + next_candidate) == next_word:
let next_length = 8 + count_match(base, next_candidate + 8, at + 9, end)
if next_length > found.length:
found = Found(next_length, at + 1 - next_candidate)
first = at + 1
else:
at += 1 + ((at - anchor) >> 7)
continue
# Extend backward over literals that also match.
var source = first - found.offset
while first > anchor and source > 0 and base[first - 1] == base[source - 1]:
first -= 1
source -= 1
found.length += 1
self.emit(anchor, first, found)
at = first + found.length
anchor = at
# Hash positions inside the match for the next searches.
if at + 8 <= end:
let inside = at - 2
let value = memory.read[u64](base + inside)
long[hash8(value, long_bits)] = (u32)inside
short[hash5(value, short_bits)] = (u32)inside
self.finish(anchor, end)
## The literals from `anchor` to the block's end.
func finish(anchor: usize, end: usize):
let count = end - anchor
if count > 0: memory.copy(self.literals[self.literal_count..], self.input[anchor..<end], count)
self.literal_count += count