mirror of
https://github.com/ddidderr/wuffs.git
synced 2026-11-17 16:32:11 +01:00
Mirror BrotliEncoderPrepareDictionary (BROTLI_SHARED_DICTIONARY_RAW), CreatePreparedDictionary and BrotliEncoderAttachPreparedDictionary as encoder.add_dictionary, with the prepared hash tables (slot offsets, heads and items) in the workbuf after the dictionary bytes, and the compound dictionary search (FindCompoundDictionaryMatch and LookupCompoundDictionaryMatch) for the hashers whose CreateBackwardReferences variant enables it, the compound dictionary gap for static dictionary distances and the compound branch of ExtendLastCommand. Extend the encoder parity script with a -dict grid that also checks round trips through libbrotlidec and the Wuffs decoder.
407 lines
18 KiB
Plaintext
407 lines
18 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 mirrors command.h, prefix.h and backward_references.c (and
|
|
// backward_references_inc.h): turning the ring buffer's bytes into commands.
|
|
//
|
|
// Commands are stored in the workbuf, starting at the this.cmds_off offset,
|
|
// as 16 little-endian bytes each, in the C code's Command struct order:
|
|
// insert_len_ (u32), copy_len_ (u32: the copy length in the low 25 bits and
|
|
// copy_code - copy_len in the high 7 bits), dist_extra_ (u32), cmd_prefix_
|
|
// (u16) and dist_prefix_ (u16).
|
|
|
|
// Mirrors BROTLI_NUM_DISTANCE_SHORT_CODES in constants.h.
|
|
pri const NUM_DISTANCE_SHORT_CODES : base.u32 = 16
|
|
|
|
// cmd_insert_len returns the i'th command's insert_len_.
|
|
pri func encoder.cmd_insert_len(wb: roslice base.u8, i: base.u64) base.u32 {
|
|
return this.load32le(s: args.wb, i: this.cmds_off ~mod+ (args.i ~mod* 16))
|
|
}
|
|
|
|
// cmd_copy_len_raw returns the i'th command's copy_len_.
|
|
pri func encoder.cmd_copy_len_raw(wb: roslice base.u8, i: base.u64) base.u32 {
|
|
return this.load32le(s: args.wb, i: (this.cmds_off ~mod+ (args.i ~mod* 16)) ~mod+ 4)
|
|
}
|
|
|
|
// cmd_dist_extra returns the i'th command's dist_extra_.
|
|
pri func encoder.cmd_dist_extra(wb: roslice base.u8, i: base.u64) base.u32 {
|
|
return this.load32le(s: args.wb, i: (this.cmds_off ~mod+ (args.i ~mod* 16)) ~mod+ 8)
|
|
}
|
|
|
|
// cmd_cmd_prefix returns the i'th command's cmd_prefix_.
|
|
pri func encoder.cmd_cmd_prefix(wb: roslice base.u8, i: base.u64) base.u16 {
|
|
return this.peek_u16(s: args.wb, i: (this.cmds_off ~mod+ (args.i ~mod* 16)) ~mod+ 12)
|
|
}
|
|
|
|
// cmd_dist_prefix returns the i'th command's dist_prefix_.
|
|
pri func encoder.cmd_dist_prefix(wb: roslice base.u8, i: base.u64) base.u16 {
|
|
return this.peek_u16(s: args.wb, i: (this.cmds_off ~mod+ (args.i ~mod* 16)) ~mod+ 14)
|
|
}
|
|
|
|
// set_cmd sets all of the i'th command's fields.
|
|
pri func encoder.set_cmd!(wb: slice base.u8, i: base.u64, insert_len: base.u32, copy_len: base.u32, dist_extra: base.u32, cmd_prefix: base.u16, dist_prefix: base.u16) {
|
|
var off : base.u64
|
|
|
|
off = this.cmds_off ~mod+ (args.i ~mod* 16)
|
|
this.poke_u32!(s: args.wb, i: off, v: args.insert_len)
|
|
this.poke_u32!(s: args.wb, i: off ~mod+ 4, v: args.copy_len)
|
|
this.poke_u32!(s: args.wb, i: off ~mod+ 8, v: args.dist_extra)
|
|
this.poke_u16!(s: args.wb, i: off ~mod+ 12, v: args.cmd_prefix)
|
|
this.poke_u16!(s: args.wb, i: off ~mod+ 14, v: args.dist_prefix)
|
|
}
|
|
|
|
// Mirrors CommandCopyLen in command.h.
|
|
pri func encoder.cmd_copy_len(wb: roslice base.u8, i: base.u64) base.u32 {
|
|
return this.cmd_copy_len_raw(wb: args.wb, i: args.i) & 0x1FF_FFFF
|
|
}
|
|
|
|
// Mirrors CommandCopyLenCode in command.h.
|
|
pri func encoder.cmd_copy_len_code(wb: roslice base.u8, i: base.u64) base.u32 {
|
|
var raw : base.u32
|
|
var modifier : base.u32
|
|
var delta : base.u32
|
|
|
|
raw = this.cmd_copy_len_raw(wb: args.wb, i: args.i)
|
|
modifier = raw >> 25
|
|
// (int8_t)((uint8_t)(modifier | ((modifier & 0x40) << 1))), as a two's
|
|
// complement u32.
|
|
delta = modifier | ((modifier & 0x40) << 1)
|
|
if delta >= 0x80 {
|
|
delta |= 0xFFFF_FF00
|
|
}
|
|
return (raw & 0x1FF_FFFF) ~mod+ delta
|
|
}
|
|
|
|
// Mirrors CommandDistanceContext in command.h.
|
|
pri func encoder.cmd_distance_context(cmd_prefix: base.u16) base.u32 {
|
|
var r : base.u32
|
|
var c : base.u32
|
|
|
|
r = (args.cmd_prefix >> 6) as base.u32
|
|
c = (args.cmd_prefix & 7) as base.u32
|
|
if ((r == 0) or (r == 2) or (r == 4) or (r == 7)) and (c <= 2) {
|
|
return c
|
|
}
|
|
return 3
|
|
}
|
|
|
|
// Mirrors GetInsertLengthCode in command.h.
|
|
pri func encoder.get_insert_length_code(insertlen: base.u64) base.u32 {
|
|
var nbits : base.u32
|
|
|
|
if args.insertlen < 6 {
|
|
return args.insertlen as base.u32
|
|
} else if args.insertlen < 130 {
|
|
nbits = this.log2_floor_non_zero(n: args.insertlen - 2) ~mod- 1
|
|
return ((nbits ~mod<< 1) ~mod+ (((args.insertlen - 2) >> (nbits & 63)) as base.u32)) ~mod+ 2
|
|
} else if args.insertlen < 2114 {
|
|
return this.log2_floor_non_zero(n: args.insertlen - 66) ~mod+ 10
|
|
} else if args.insertlen < 6210 {
|
|
return 21
|
|
} else if args.insertlen < 22594 {
|
|
return 22
|
|
}
|
|
return 23
|
|
}
|
|
|
|
// Mirrors GetCopyLengthCode in command.h.
|
|
pri func encoder.get_copy_length_code(copylen: base.u64) base.u32 {
|
|
var nbits : base.u32
|
|
|
|
if args.copylen < 10 {
|
|
return ((args.copylen ~mod- 2) & 0xFF) as base.u32
|
|
} else if args.copylen < 134 {
|
|
nbits = this.log2_floor_non_zero(n: args.copylen - 6) ~mod- 1
|
|
return ((nbits ~mod<< 1) ~mod+ (((args.copylen - 6) >> (nbits & 63)) as base.u32)) ~mod+ 4
|
|
} else if args.copylen < 2118 {
|
|
return this.log2_floor_non_zero(n: args.copylen - 70) ~mod+ 12
|
|
}
|
|
return 23
|
|
}
|
|
|
|
// Mirrors CombineLengthCodes in command.h.
|
|
pri func encoder.combine_length_codes(inscode: base.u32, copycode: base.u32, use_last_distance: base.bool) base.u16 {
|
|
var bits64 : base.u32
|
|
var offset : base.u32
|
|
|
|
bits64 = (args.copycode & 7) | ((args.inscode & 7) << 3)
|
|
if args.use_last_distance and (args.inscode < 8) and (args.copycode < 16) {
|
|
if args.copycode < 8 {
|
|
return (bits64 & 0xFFFF) as base.u16
|
|
}
|
|
return ((bits64 | 64) & 0xFFFF) as base.u16
|
|
}
|
|
offset = 2 ~mod* ((args.copycode >> 3) ~mod+ (3 ~mod* (args.inscode >> 3)))
|
|
offset = ((offset ~mod<< 5) ~mod+ 0x40) ~mod+ (((0x52_0D40 as base.u32) >> (offset & 31)) & 0xC0)
|
|
return ((offset | bits64) & 0xFFFF) as base.u16
|
|
}
|
|
|
|
// Mirrors GetLengthCode in command.h.
|
|
pri func encoder.get_length_code(insertlen: base.u64, copylen: base.u64, use_last_distance: base.bool) base.u16 {
|
|
return this.combine_length_codes(
|
|
inscode: this.get_insert_length_code(insertlen: args.insertlen),
|
|
copycode: this.get_copy_length_code(copylen: args.copylen),
|
|
use_last_distance: args.use_last_distance)
|
|
}
|
|
|
|
// Mirrors InitCommand in command.h, storing the n'th command.
|
|
pri func encoder.init_command!(wb: slice base.u8, n: base.u64, insertlen: base.u64, copylen: base.u64, copylen_code_delta: base.u64, distance_code: base.u64) {
|
|
var delta : base.u32
|
|
var pe : base.u64
|
|
var dist_prefix : base.u16
|
|
var cmd_prefix : base.u16
|
|
|
|
delta = (args.copylen_code_delta & 0xFF) as base.u32
|
|
pe = this.mb.prefix_encode_copy_distance(
|
|
distance_code: args.distance_code,
|
|
num_direct_codes: this.num_direct_distance_codes as base.u64,
|
|
postfix_bits: this.distance_postfix_bits)
|
|
dist_prefix = (pe & 0xFFFF) as base.u16
|
|
cmd_prefix = this.get_length_code(
|
|
insertlen: args.insertlen,
|
|
copylen: args.copylen ~mod+ args.copylen_code_delta,
|
|
use_last_distance: (dist_prefix & 0x3FF) == 0)
|
|
this.set_cmd!(wb: args.wb, i: args.n,
|
|
insert_len: (args.insertlen & 0xFFFF_FFFF) as base.u32,
|
|
copy_len: ((args.copylen & 0xFFFF_FFFF) as base.u32) | (delta ~mod<< 25),
|
|
dist_extra: (pe >> 32) as base.u32,
|
|
cmd_prefix: cmd_prefix,
|
|
dist_prefix: dist_prefix)
|
|
}
|
|
|
|
// Mirrors InitInsertCommand in command.h, storing the n'th command.
|
|
pri func encoder.init_insert_command!(wb: slice base.u8, n: base.u64, insertlen: base.u64) {
|
|
this.set_cmd!(wb: args.wb, i: args.n,
|
|
insert_len: (args.insertlen & 0xFFFF_FFFF) as base.u32,
|
|
copy_len: 4 << 25,
|
|
dist_extra: 0,
|
|
cmd_prefix: this.get_length_code(insertlen: args.insertlen, copylen: 4, use_last_distance: false),
|
|
dist_prefix: 16)
|
|
}
|
|
|
|
// Mirrors CommandRestoreDistanceCode in command.h, for the i'th command.
|
|
pri func encoder.cmd_restore_distance_code(wb: roslice base.u8, i: base.u64) base.u32 {
|
|
return this.mb.command_restore_distance_code(wb: args.wb,
|
|
c: this.cmds_off ~mod+ (args.i ~mod* 16),
|
|
npostfix: this.distance_postfix_bits,
|
|
ndirect: this.num_direct_distance_codes)
|
|
}
|
|
|
|
// Mirrors ComputeDistanceCode in backward_references.c.
|
|
pri func encoder.compute_distance_code(distance: base.u64, max_distance: base.u64) base.u64 {
|
|
var distance_plus_3 : base.u64
|
|
var offset0 : base.u64
|
|
var offset1 : base.u64
|
|
|
|
if args.distance <= args.max_distance {
|
|
distance_plus_3 = args.distance ~mod+ 3
|
|
offset0 = distance_plus_3 ~mod- this.dist_cache_u64(i: 0)
|
|
offset1 = distance_plus_3 ~mod- this.dist_cache_u64(i: 1)
|
|
if args.distance == this.dist_cache_u64(i: 0) {
|
|
return 0
|
|
} else if args.distance == this.dist_cache_u64(i: 1) {
|
|
return 1
|
|
} else if offset0 < 7 {
|
|
return ((0x975_0468 as base.u64) >> (4 * offset0)) & 0xF
|
|
} else if offset1 < 7 {
|
|
return ((0xFDB_1ACE as base.u64) >> (4 * offset1)) & 0xF
|
|
} else if args.distance == this.dist_cache_u64(i: 2) {
|
|
return 2
|
|
} else if args.distance == this.dist_cache_u64(i: 3) {
|
|
return 3
|
|
}
|
|
}
|
|
return args.distance ~mod+ 15
|
|
}
|
|
|
|
// Mirrors CreateBackwardReferences in backward_references_inc.h (via
|
|
// BrotliCreateBackwardReferences in backward_references.c), with the
|
|
// built-in static dictionary. Its ENABLE_COMPOUND_DICTIONARY variant (see
|
|
// compound_dictionary_enabled) searches the attached dictionaries (in
|
|
// args.dwb). New commands are appended at this.num_cmds.
|
|
pri func encoder.create_backward_references!(wb: slice base.u8, dwb: roslice base.u8, num_bytes: base.u64, position: base.u64) base.status {
|
|
var position : base.u64
|
|
var max_backward_limit : base.u64
|
|
var position_offset : base.u64
|
|
var insert_length : base.u64
|
|
var pos_end : base.u64
|
|
var store_end : base.u64
|
|
var htl : base.u64
|
|
var random_heuristics_window_size : base.u64
|
|
var apply_random_heuristics : base.u64
|
|
var max_length : base.u64
|
|
var max_distance : base.u64
|
|
var dictionary_start : base.u64
|
|
var delayed_backward_references : base.u32
|
|
var sr_len : base.u64
|
|
var sr_distance : base.u64
|
|
var sr_score : base.u64
|
|
var sr_len_code_delta : base.u64
|
|
var distance_code : base.u64
|
|
var range_start : base.u64
|
|
var range_end : base.u64
|
|
var k_margin : base.u64
|
|
var pos_jump : base.u64
|
|
var gap : base.u64
|
|
var use_compound : base.bool
|
|
var data : roslice base.u8
|
|
|
|
position = args.position
|
|
max_backward_limit = ((1 as base.u64) << this.lgwin) ~mod- 16
|
|
position_offset = this.stream_offset as base.u64
|
|
insert_length = this.last_insert_len
|
|
pos_end = position ~mod+ args.num_bytes
|
|
htl = this.hasher_type_length()
|
|
store_end = position
|
|
if args.num_bytes >= htl {
|
|
store_end = ((position ~mod+ args.num_bytes) ~mod- htl) ~mod+ 1
|
|
}
|
|
random_heuristics_window_size = 64
|
|
if this.quality >= 9 {
|
|
random_heuristics_window_size = 512
|
|
}
|
|
apply_random_heuristics = position ~mod+ random_heuristics_window_size
|
|
gap = this.dict_total_size
|
|
use_compound = this.compound_dictionary_enabled()
|
|
if this.rb_buf_off <= args.wb.length() {
|
|
data = args.wb[this.rb_buf_off ..]
|
|
}
|
|
|
|
this.prepare_distance_cache!()
|
|
|
|
while (position ~mod+ htl) < pos_end {
|
|
max_length = pos_end ~mod- position
|
|
max_distance = position.min(no_more_than: max_backward_limit)
|
|
dictionary_start = this.min64(a: position ~mod+ position_offset, b: max_backward_limit)
|
|
this.sr_len = 0
|
|
this.sr_len_code_delta = 0
|
|
this.sr_distance = 0
|
|
this.sr_score = SCORE_BASE + 100
|
|
this.find_longest_match!(wb: args.wb, cur_ix: position, max_length: max_length,
|
|
max_backward: max_distance, dictionary_distance: dictionary_start ~mod+ gap,
|
|
max_distance: this.dist_max_distance)
|
|
if use_compound {
|
|
this.lookup_compound_dictionary_match!(data: data, dwb: args.dwb,
|
|
cur_ix: position, max_length: max_length,
|
|
max_ring_buffer_distance: dictionary_start, max_distance: this.dist_max_distance)
|
|
}
|
|
if this.sr_score > (SCORE_BASE + 100) {
|
|
// Found a match. Let's look for something even better ahead.
|
|
delayed_backward_references = 0
|
|
max_length ~mod-= 1
|
|
while true {
|
|
sr_len = this.sr_len
|
|
sr_distance = this.sr_distance
|
|
sr_score = this.sr_score
|
|
sr_len_code_delta = this.sr_len_code_delta
|
|
this.sr_len = 0
|
|
if this.quality < 5 {
|
|
this.sr_len = this.min64(a: sr_len ~mod- 1, b: max_length)
|
|
}
|
|
this.sr_len_code_delta = 0
|
|
this.sr_distance = 0
|
|
this.sr_score = SCORE_BASE + 100
|
|
max_distance = this.min64(a: position ~mod+ 1, b: max_backward_limit)
|
|
dictionary_start = this.min64(a: (position ~mod+ 1) ~mod+ position_offset, b: max_backward_limit)
|
|
this.find_longest_match!(wb: args.wb, cur_ix: position ~mod+ 1, max_length: max_length,
|
|
max_backward: max_distance, dictionary_distance: dictionary_start ~mod+ gap,
|
|
max_distance: this.dist_max_distance)
|
|
if use_compound {
|
|
this.lookup_compound_dictionary_match!(data: data, dwb: args.dwb,
|
|
cur_ix: position ~mod+ 1, max_length: max_length,
|
|
max_ring_buffer_distance: dictionary_start, max_distance: this.dist_max_distance)
|
|
}
|
|
if this.sr_score >= (sr_score ~mod+ 175) {
|
|
// Ok, let's just write one byte for now and start a match
|
|
// from the next byte.
|
|
position ~mod+= 1
|
|
insert_length ~mod+= 1
|
|
delayed_backward_references ~mod+= 1
|
|
if (delayed_backward_references < 4) and ((position ~mod+ htl) < pos_end) {
|
|
max_length ~mod-= 1
|
|
continue
|
|
}
|
|
break
|
|
}
|
|
// Keep the old sr.
|
|
this.sr_len = sr_len
|
|
this.sr_distance = sr_distance
|
|
this.sr_score = sr_score
|
|
this.sr_len_code_delta = sr_len_code_delta
|
|
break
|
|
}
|
|
apply_random_heuristics = (position ~mod+ (2 ~mod* this.sr_len)) ~mod+ random_heuristics_window_size
|
|
dictionary_start = this.min64(a: position ~mod+ position_offset, b: max_backward_limit)
|
|
// The first 16 codes are special short-codes, and the minimum
|
|
// offset is 1.
|
|
distance_code = this.compute_distance_code(distance: this.sr_distance, max_distance: dictionary_start ~mod+ gap)
|
|
if (this.sr_distance <= (dictionary_start ~mod+ gap)) and (distance_code > 0) {
|
|
this.dist_cache[3] = this.dist_cache[2]
|
|
this.dist_cache[2] = this.dist_cache[1]
|
|
this.dist_cache[1] = this.dist_cache[0]
|
|
this.dist_cache[0] = (this.sr_distance & 0xFFFF_FFFF) as base.u32
|
|
this.prepare_distance_cache!()
|
|
}
|
|
if this.num_cmds >= this.cmds_cap {
|
|
return "#internal error: inconsistent encoder state"
|
|
}
|
|
this.init_command!(wb: args.wb, n: this.num_cmds, insertlen: insert_length, copylen: this.sr_len,
|
|
copylen_code_delta: this.sr_len_code_delta, distance_code: distance_code)
|
|
this.num_cmds ~mod+= 1
|
|
this.num_lits ~mod+= insert_length
|
|
insert_length = 0
|
|
// Put the hash keys into the table, if there are enough bytes
|
|
// left. Depending on the hasher implementation, it can push all
|
|
// positions in the given range or only a subset of them. Avoid
|
|
// hash poisoning with RLE data.
|
|
range_start = position ~mod+ 2
|
|
range_end = this.min64(a: position ~mod+ this.sr_len, b: store_end)
|
|
if this.sr_distance < (this.sr_len >> 2) {
|
|
range_start = range_end.min(no_more_than: range_start.max(no_less_than:
|
|
(position ~mod+ this.sr_len) ~mod- (this.sr_distance ~mod<< 2)))
|
|
}
|
|
this.hasher_store_range!(wb: args.wb, ix_start: range_start, ix_end: range_end)
|
|
position ~mod+= this.sr_len
|
|
} else {
|
|
insert_length ~mod+= 1
|
|
position ~mod+= 1
|
|
// If we have not seen matches for a long time, we can skip some
|
|
// match lookups. Unsuccessful match lookups are very very
|
|
// expensive and this kind of a heuristic speeds up compression
|
|
// quite a lot.
|
|
if position > apply_random_heuristics {
|
|
// Going through uncompressible data, jump.
|
|
if position > (apply_random_heuristics ~mod+ (4 ~mod* random_heuristics_window_size)) {
|
|
k_margin = this.max64(a: htl ~mod- 1, b: 4)
|
|
pos_jump = this.min64(a: position ~mod+ 16, b: pos_end ~mod- k_margin)
|
|
while position < pos_jump {
|
|
this.hasher_store!(wb: args.wb, ix: position)
|
|
insert_length ~mod+= 4
|
|
position ~mod+= 4
|
|
}
|
|
} else {
|
|
k_margin = this.max64(a: htl ~mod- 1, b: 2)
|
|
pos_jump = this.min64(a: position ~mod+ 8, b: pos_end ~mod- k_margin)
|
|
while position < pos_jump {
|
|
this.hasher_store!(wb: args.wb, ix: position)
|
|
insert_length ~mod+= 2
|
|
position ~mod+= 2
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
insert_length ~mod+= pos_end ~mod- position
|
|
this.last_insert_len = insert_length
|
|
return ok
|
|
}
|