mirror of
https://github.com/ddidderr/wuffs.git
synced 2026-11-17 16:32:11 +01:00
Encoder (output stays byte-exact with libbrotlienc v1.2.1): - H58/H68 (q5-6): match the tags 8 at a time (SWAR, like GetMatchingTagMask's non-SSE2 code) and visit the matches with a de Bruijn ctz; inline the bucket entry check into the H5/H6 and H58/H68 loops, caching the 4 bytes compared at best_len; a dedicated H58/H68 store and hash. - find_last_distances caches the current byte at best_len. - ctz64 and a branch-free log2_floor_non_zero (de Bruijn tables), and find_match_length_with_limit uses ctz. - load32le, load64le, peek_u16, poke_u16 and poke_u32 use one bounds check each. Decoder (same output and statuses): - The literal fast path keeps pos and the counts in local variables. - Copies of at most 16 bytes, with a distance of at least 16, copy 16 bytes (like the C code; the window gap keeps the extra bytes unread). script/manual-test-brotli-float.c also checks log2_floor_non_zero (every u32) and ctz64. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01UZ978BikvkegL2JUkqoB1e
126 lines
4.3 KiB
Plaintext
126 lines
4.3 KiB
Plaintext
// Copyright 2026 The Wuffs Authors.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
|
|
// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
|
|
// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
|
|
// option. This file may not be copied, modified, or distributed
|
|
// except according to those terms.
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 OR MIT
|
|
|
|
// --------
|
|
|
|
// This file holds small helpers for the quality 2 (and above) code paths,
|
|
// which keep most of their state (the ring buffer, the hash tables, the
|
|
// commands, the output storage and the metablock split) in the workbuf. Like
|
|
// the C code's uint16_t and uint32_t arrays, multi-byte values in the workbuf
|
|
// are little-endian. The C code never reads or writes out of bounds, so the
|
|
// out of bounds branches here (which do nothing, or return 0) should never be
|
|
// taken.
|
|
|
|
// CTZ64_DEBRUIJN maps ((x & -x) * 0x03F7_9D71_B4CB_0A89) >> 58 to the
|
|
// number of trailing zero bits of the non-zero x.
|
|
pri const CTZ64_DEBRUIJN : roarray[64] base.u8[..= 63] = [
|
|
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,
|
|
]
|
|
|
|
// ctz64 returns the number of trailing zero bits of x, which must be
|
|
// non-zero (for x == 0 it returns 0).
|
|
pri func encoder.ctz64(x: base.u64) base.u64[..= 63] {
|
|
return CTZ64_DEBRUIJN[((args.x & (0 ~mod- args.x)) ~mod* 0x03F7_9D71_B4CB_0A89) >> 58] as base.u64
|
|
}
|
|
|
|
// byte_at returns s[i], or 0 if i is out of bounds.
|
|
pri func encoder.byte_at(s: roslice base.u8, i: base.u64) base.u8 {
|
|
if args.i < args.s.length() {
|
|
return args.s[args.i]
|
|
}
|
|
return 0
|
|
}
|
|
|
|
// peek_u16 returns the 2 bytes (little-endian) of s starting at i.
|
|
pri func encoder.peek_u16(s: roslice base.u8, i: base.u64) base.u16 {
|
|
if args.i < 0xFFFF_FFFF_FFFF_0000 {
|
|
if (args.i + 2) <= args.s.length() {
|
|
assert args.i <= (args.i + 2) via "a <= (a + b): 0 <= b"(b: 2)
|
|
return args.s[args.i .. args.i + 2].peek_u16le()
|
|
}
|
|
}
|
|
return 0
|
|
}
|
|
|
|
// poke_u16 sets the 2 bytes (little-endian) of s starting at i.
|
|
pri func encoder.poke_u16!(s: slice base.u8, i: base.u64, v: base.u16) {
|
|
if args.i < 0xFFFF_FFFF_FFFF_0000 {
|
|
if (args.i + 2) <= args.s.length() {
|
|
assert args.i <= (args.i + 2) via "a <= (a + b): 0 <= b"(b: 2)
|
|
args.s[args.i .. args.i + 2].poke_u16le!(a: args.v)
|
|
}
|
|
}
|
|
}
|
|
|
|
// poke_u32 sets the 4 bytes (little-endian) of s starting at i.
|
|
pri func encoder.poke_u32!(s: slice base.u8, i: base.u64, v: base.u32) {
|
|
if args.i < 0xFFFF_FFFF_FFFF_0000 {
|
|
if (args.i + 4) <= args.s.length() {
|
|
assert args.i <= (args.i + 4) via "a <= (a + b): 0 <= b"(b: 4)
|
|
args.s[args.i .. args.i + 4].poke_u32le!(a: args.v)
|
|
}
|
|
}
|
|
}
|
|
|
|
// set_byte sets s[i] to v, if i is in bounds.
|
|
pri func encoder.set_byte!(s: slice base.u8, i: base.u64, v: base.u8) {
|
|
if args.i < args.s.length() {
|
|
args.s[args.i] = args.v
|
|
}
|
|
}
|
|
|
|
// fill_bytes sets s[i .. i + n] to v (as far as it is in bounds).
|
|
pri func encoder.fill_bytes!(s: slice base.u8, i: base.u64, n: base.u64, v: base.u8) {
|
|
var q : slice base.u8
|
|
var n : base.u64
|
|
|
|
if args.i <= args.s.length() {
|
|
q = args.s[args.i ..]
|
|
if args.n <= q.length() {
|
|
q[.. args.n].bulk_memset!(byte_value: args.v)
|
|
} else {
|
|
n = q.length()
|
|
assert n <= q.length() via "a <= b: a == b"()
|
|
q[.. n].bulk_memset!(byte_value: args.v)
|
|
}
|
|
}
|
|
}
|
|
|
|
// dist_cache_u64 returns the C code's (size_t)dist_cache[i]: the int value,
|
|
// sign-extended to 64 bits.
|
|
pri func encoder.dist_cache_u64(i: base.u32) base.u64 {
|
|
var v : base.u32
|
|
|
|
v = this.dist_cache[args.i & 15]
|
|
if v >= 0x8000_0000 {
|
|
return (v as base.u64) | 0xFFFF_FFFF_0000_0000
|
|
}
|
|
return v as base.u64
|
|
}
|
|
|
|
// min64 returns the smaller of a and b.
|
|
pri func encoder.min64(a: base.u64, b: base.u64) base.u64 {
|
|
if args.a < args.b {
|
|
return args.a
|
|
}
|
|
return args.b
|
|
}
|
|
|
|
// max64 returns the larger of a and b.
|
|
pri func encoder.max64(a: base.u64, b: base.u64) base.u64 {
|
|
if args.a > args.b {
|
|
return args.a
|
|
}
|
|
return args.b
|
|
}
|