mirror of
https://github.com/ddidderr/wuffs.git
synced 2026-11-17 16:32:11 +01:00
build_and_store_huffman_tree_fast_generic indexed the 704-entry ZERO_REPS and NON_ZERO_REPS tables with reps & 511, so a run of more than 511 equal code lengths (e.g. unused command codes between 75 and 688 in a quality 2 metablock of more than 128 commands) was written wrongly and the stream did not decode. Found by the differential fuzzer (quality 2, lgwin 10).
1185 lines
46 KiB
Plaintext
1185 lines
46 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 the parts of brotli_bit_stream.c (and block_encoder_inc.h)
|
|
// that qualities 2 to 9 use: storing compressed metablocks (with and without
|
|
// block splits and context maps) and uncompressed metablocks.
|
|
//
|
|
// The storage (the C code's uint8_t* storage) is the s argument. The input
|
|
// (the ring buffer) and the commands are in the wb (workbuf) argument. The
|
|
// generic Huffman code builder (build_and_store_huffman_tree) works on
|
|
// this.huff_histo, this.huff_depth and this.huff_bits: its callers copy their
|
|
// histogram in and the resulting depths and bits out.
|
|
|
|
// rb_byte returns the ring buffer's byte at position pos (masked).
|
|
pri func encoder.rb_byte(wb: roslice base.u8, pos: base.u64) base.u8 {
|
|
return this.byte_at(s: args.wb, i: this.rb_buf_off ~mod+ (args.pos & (this.rb_mask as base.u64)))
|
|
}
|
|
|
|
// Mirrors JumpToByteBoundary in brotli_bit_stream.c.
|
|
pri func encoder.jump_to_byte_boundary!(s: slice base.u8) {
|
|
this.bw_ix = (this.bw_ix ~mod+ 7) & 0xFFFF_FFFF_FFFF_FFF8
|
|
this.set_byte!(s: args.s, i: this.bw_ix >> 3, v: 0)
|
|
}
|
|
|
|
// Mirrors BrotliEncodeMlen and StoreCompressedMetaBlockHeader in
|
|
// brotli_bit_stream.c.
|
|
pri func encoder.store_compressed_meta_block_header!(is_final_block: base.bool, length: base.u64, s: slice base.u8) {
|
|
var lg : base.u32[..= 32]
|
|
var mnibbles : base.u32
|
|
|
|
// Write ISLAST bit.
|
|
if args.is_final_block {
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s)
|
|
// Write ISEMPTY bit.
|
|
this.write_bits!(n_bits: 1, bits: 0, s: args.s)
|
|
} else {
|
|
this.write_bits!(n_bits: 1, bits: 0, s: args.s)
|
|
}
|
|
lg = 1
|
|
if args.length > 1 {
|
|
lg = this.log2_floor_non_zero(n: args.length ~mod- 1) + 1
|
|
}
|
|
mnibbles = 4
|
|
if lg >= 16 {
|
|
mnibbles = (lg + 3) / 4
|
|
}
|
|
this.write_bits!(n_bits: 2, bits: (mnibbles ~mod- 4) as base.u64, s: args.s)
|
|
this.write_bits!(n_bits: mnibbles ~mod* 4, bits: args.length ~mod- 1, s: args.s)
|
|
if not args.is_final_block {
|
|
// Write ISUNCOMPRESSED bit.
|
|
this.write_bits!(n_bits: 1, bits: 0, s: args.s)
|
|
}
|
|
}
|
|
|
|
// Mirrors BrotliStoreUncompressedMetaBlockHeader and
|
|
// BrotliStoreUncompressedMetaBlock in brotli_bit_stream.c.
|
|
pri func encoder.store_uncompressed_meta_block!(is_final_block: base.bool, wb: roslice base.u8, position: base.u64, len: base.u64, s: slice base.u8) {
|
|
var lg : base.u32[..= 32]
|
|
var mnibbles : base.u32
|
|
var masked_pos : base.u64
|
|
var len : base.u64
|
|
var len1 : base.u64
|
|
var mask : base.u64
|
|
|
|
mask = this.rb_mask as base.u64
|
|
masked_pos = args.position & mask
|
|
len = args.len
|
|
|
|
// Write ISLAST bit. Uncompressed block cannot be the last one, so set to
|
|
// 0.
|
|
this.write_bits!(n_bits: 1, bits: 0, s: args.s)
|
|
lg = 1
|
|
if len > 1 {
|
|
lg = this.log2_floor_non_zero(n: len ~mod- 1) + 1
|
|
}
|
|
mnibbles = 4
|
|
if lg >= 16 {
|
|
mnibbles = (lg + 3) / 4
|
|
}
|
|
this.write_bits!(n_bits: 2, bits: (mnibbles ~mod- 4) as base.u64, s: args.s)
|
|
this.write_bits!(n_bits: mnibbles ~mod* 4, bits: len ~mod- 1, s: args.s)
|
|
// Write ISUNCOMPRESSED bit.
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s)
|
|
this.jump_to_byte_boundary!(s: args.s)
|
|
|
|
if (masked_pos ~mod+ len) > (mask ~mod+ 1) {
|
|
len1 = (mask ~mod+ 1) ~mod- masked_pos
|
|
this.copy_rb_to_storage!(wb: args.wb, from: masked_pos, n: len1, s: args.s)
|
|
len ~mod-= len1
|
|
masked_pos = 0
|
|
}
|
|
this.copy_rb_to_storage!(wb: args.wb, from: masked_pos, n: len, s: args.s)
|
|
|
|
// We need to clear the next 4 bytes to continue to be compatible with
|
|
// BrotliWriteBits.
|
|
this.set_byte!(s: args.s, i: this.bw_ix >> 3, v: 0)
|
|
|
|
// Since the uncompressed block itself may not be the final block, add an
|
|
// empty one after this.
|
|
if args.is_final_block {
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s) // islast
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s) // isempty
|
|
this.jump_to_byte_boundary!(s: args.s)
|
|
}
|
|
}
|
|
|
|
// copy_rb_to_storage copies n bytes of the ring buffer, starting at its
|
|
// (masked) position from, to the storage at the (byte aligned) bit position
|
|
// this.bw_ix, and advances this.bw_ix.
|
|
pri func encoder.copy_rb_to_storage!(wb: roslice base.u8, from: base.u64, n: base.u64, s: slice base.u8) {
|
|
var src : roslice base.u8
|
|
var dst : slice base.u8
|
|
var a : base.u64
|
|
var b : base.u64
|
|
|
|
a = this.rb_buf_off ~mod+ args.from
|
|
b = this.bw_ix >> 3
|
|
if (a <= args.wb.length()) and (b <= args.s.length()) {
|
|
src = args.wb[a ..]
|
|
dst = args.s[b ..]
|
|
if (args.n <= src.length()) and (args.n <= dst.length()) {
|
|
dst.copy_from_slice!(s: src[.. args.n])
|
|
}
|
|
}
|
|
this.bw_ix ~mod+= args.n ~mod<< 3
|
|
}
|
|
|
|
// Mirrors StoreCommandExtra in brotli_bit_stream.c.
|
|
pri func encoder.store_command_extra!(wb: roslice base.u8, i: base.u64, s: slice base.u8) {
|
|
var copylen_code : base.u32
|
|
var insert_len : base.u32
|
|
var inscode : base.u32
|
|
var copycode : base.u32
|
|
var insnumextra : base.u32
|
|
var insextraval : base.u64
|
|
var copyextraval : base.u64
|
|
|
|
copylen_code = this.cmd_copy_len_code(wb: args.wb, i: args.i)
|
|
insert_len = this.cmd_insert_len(wb: args.wb, i: args.i)
|
|
inscode = this.get_insert_length_code(insertlen: insert_len as base.u64)
|
|
copycode = this.get_copy_length_code(copylen: copylen_code as base.u64)
|
|
insnumextra = INS_EXTRA[inscode.min(no_more_than: 23)]
|
|
insextraval = (insert_len ~mod- INS_BASE[inscode.min(no_more_than: 23)]) as base.u64
|
|
copyextraval = (copylen_code ~mod- COPY_BASE[copycode.min(no_more_than: 23)]) as base.u64
|
|
this.write_bits!(
|
|
n_bits: insnumextra + COPY_EXTRA[copycode.min(no_more_than: 23)],
|
|
bits: (copyextraval ~mod<< insnumextra) | insextraval,
|
|
s: args.s)
|
|
}
|
|
|
|
// Mirrors StoreVarLenUint8 in brotli_bit_stream.c.
|
|
pri func encoder.store_var_len_uint8!(n: base.u64, s: slice base.u8) {
|
|
var nbits : base.u32[..= 31]
|
|
|
|
if args.n == 0 {
|
|
this.write_bits!(n_bits: 1, bits: 0, s: args.s)
|
|
} else {
|
|
nbits = this.log2_floor_non_zero(n: args.n)
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s)
|
|
this.write_bits!(n_bits: 3, bits: nbits as base.u64, s: args.s)
|
|
this.write_bits!(n_bits: nbits, bits: args.n ~mod- ((1 as base.u64) << nbits), s: args.s)
|
|
}
|
|
}
|
|
|
|
// Mirrors StoreSimpleHuffmanTree in brotli_bit_stream.c, with
|
|
// this.huff_depth as depths.
|
|
pri func encoder.store_simple_huffman_tree!(symbols: array[4] base.u32, num_symbols: base.u32, max_bits: base.u32, s: slice base.u8) {
|
|
var symbols : array[4] base.u32
|
|
var i : base.u32
|
|
var j : base.u32
|
|
var tmp : base.u32
|
|
|
|
symbols = args.symbols
|
|
// Value of 1 indicates a simple Huffman code.
|
|
this.write_bits!(n_bits: 2, bits: 1, s: args.s)
|
|
this.write_bits!(n_bits: 2, bits: (args.num_symbols ~mod- 1) as base.u64, s: args.s) // NSYM - 1.
|
|
|
|
// Sort.
|
|
i = 0
|
|
while i < args.num_symbols {
|
|
j = i ~mod+ 1
|
|
while j < args.num_symbols {
|
|
if this.huff_depth[symbols[j & 3] & 1023] < this.huff_depth[symbols[i & 3] & 1023] {
|
|
tmp = symbols[j & 3]
|
|
symbols[j & 3] = symbols[i & 3]
|
|
symbols[i & 3] = tmp
|
|
}
|
|
j ~mod+= 1
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[0] as base.u64, s: args.s)
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[1] as base.u64, s: args.s)
|
|
if args.num_symbols >= 3 {
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[2] as base.u64, s: args.s)
|
|
}
|
|
if args.num_symbols >= 4 {
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[3] as base.u64, s: args.s)
|
|
// Tree-select.
|
|
if this.huff_depth[symbols[0] & 1023] == 1 {
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s)
|
|
} else {
|
|
this.write_bits!(n_bits: 1, bits: 0, s: args.s)
|
|
}
|
|
}
|
|
}
|
|
|
|
// Mirrors BuildAndStoreHuffmanTree in brotli_bit_stream.c, with
|
|
// this.huff_histo, this.huff_depth and this.huff_bits as the histogram, depth
|
|
// and bits arguments.
|
|
pri func encoder.build_and_store_huffman_tree!(histogram_length: base.u32, alphabet_size: base.u32, s: slice base.u8) {
|
|
var count : base.u32
|
|
var s4 : array[4] base.u32
|
|
var i : base.u32
|
|
var max_bits : base.u32
|
|
var max_bits_counter : base.u32
|
|
|
|
i = 0
|
|
while i < args.histogram_length {
|
|
if this.huff_histo[i & 1023] <> 0 {
|
|
if count < 4 {
|
|
s4[count] = i
|
|
} else if count > 4 {
|
|
break
|
|
}
|
|
count ~mod+= 1
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
|
|
max_bits_counter = args.alphabet_size ~mod- 1
|
|
while max_bits_counter > 0 {
|
|
max_bits_counter >>= 1
|
|
max_bits ~mod+= 1
|
|
}
|
|
|
|
if count <= 1 {
|
|
this.write_bits!(n_bits: 4, bits: 1, s: args.s)
|
|
this.write_bits!(n_bits: max_bits, bits: s4[0] as base.u64, s: args.s)
|
|
this.huff_depth[s4[0] & 1023] = 0
|
|
this.huff_bits[s4[0] & 1023] = 0
|
|
return nothing
|
|
}
|
|
|
|
i = 0
|
|
while i < args.histogram_length {
|
|
this.huff_depth[i & 1023] = 0
|
|
i ~mod+= 1
|
|
}
|
|
this.create_huffman_tree!(src: 2, off: 0, length: args.histogram_length, tree_limit: 15, depth: this.huff_depth[..])
|
|
this.convert_bit_depths_to_symbols!(depth: this.huff_depth[..], len: args.histogram_length, dst: 4)
|
|
|
|
if count <= 4 {
|
|
this.store_simple_huffman_tree!(symbols: s4, num_symbols: count, max_bits: max_bits, s: args.s)
|
|
} else {
|
|
this.store_huffman_tree!(depths: this.huff_depth[..], num: args.histogram_length, s: args.s)
|
|
}
|
|
}
|
|
|
|
// Mirrors BrotliBuildAndStoreHuffmanTreeFast in brotli_bit_stream.c, with
|
|
// this.huff_histo, this.huff_depth and this.huff_bits as the histogram, depth
|
|
// and bits arguments.
|
|
pri func encoder.build_and_store_huffman_tree_fast_generic!(histogram_total: base.u64, max_bits: base.u32, s: slice base.u8) {
|
|
var count : base.u32
|
|
var symbols : array[4] base.u32
|
|
var length : base.u32
|
|
var total : base.u64
|
|
var count_limit : base.u32
|
|
var n : base.u32
|
|
var l : base.u32
|
|
var h : base.u32
|
|
var i : base.u32
|
|
var j : base.u32
|
|
var tmp : base.u32
|
|
var depth_ok : base.bool
|
|
var value : base.u32
|
|
var prev_value : base.u32
|
|
var reps : base.u32
|
|
var k : base.u32
|
|
|
|
total = args.histogram_total
|
|
while (total <> 0) and (length < 1024) {
|
|
h = this.huff_histo[length]
|
|
if h <> 0 {
|
|
if count < 4 {
|
|
symbols[count] = length
|
|
}
|
|
count ~mod+= 1
|
|
total ~mod-= h as base.u64
|
|
}
|
|
length ~mod+= 1
|
|
}
|
|
|
|
if count <= 1 {
|
|
this.write_bits!(n_bits: 4, bits: 1, s: args.s)
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[0] as base.u64, s: args.s)
|
|
this.huff_depth[symbols[0] & 1023] = 0
|
|
this.huff_bits[symbols[0] & 1023] = 0
|
|
return nothing
|
|
}
|
|
|
|
i = 0
|
|
while i < length {
|
|
this.huff_depth[i & 1023] = 0
|
|
i ~mod+= 1
|
|
}
|
|
|
|
count_limit = 1
|
|
while true {
|
|
n = 0
|
|
l = length
|
|
while l > 0 {
|
|
l -= 1
|
|
h = this.huff_histo[l & 1023]
|
|
if h <> 0 {
|
|
if h >= count_limit {
|
|
this.tree_count[n & 2047] = h
|
|
} else {
|
|
this.tree_count[n & 2047] = count_limit
|
|
}
|
|
this.tree_left[n & 2047] = TREE_NONE
|
|
this.tree_right[n & 2047] = (l & 0xFFFF) as base.u16
|
|
n ~mod+= 1
|
|
}
|
|
}
|
|
this.sort_huffman_tree_items!(n: n, tie_break: false)
|
|
this.merge_huffman_nodes!(n: n)
|
|
depth_ok = this.set_depth!(p0: (n ~mod* 2) ~mod- 1, depth: this.huff_depth[..], max_depth: 14)
|
|
if depth_ok {
|
|
break
|
|
}
|
|
count_limit ~mod*= 2
|
|
}
|
|
this.convert_bit_depths_to_symbols!(depth: this.huff_depth[..], len: length, dst: 4)
|
|
|
|
if count <= 4 {
|
|
// Value of 1 indicates a simple Huffman code.
|
|
this.write_bits!(n_bits: 2, bits: 1, s: args.s)
|
|
this.write_bits!(n_bits: 2, bits: (count ~mod- 1) as base.u64, s: args.s) // NSYM - 1.
|
|
|
|
// Sort.
|
|
i = 0
|
|
while i < count {
|
|
j = i ~mod+ 1
|
|
while j < count {
|
|
if this.huff_depth[symbols[j & 3] & 1023] < this.huff_depth[symbols[i & 3] & 1023] {
|
|
tmp = symbols[j & 3]
|
|
symbols[j & 3] = symbols[i & 3]
|
|
symbols[i & 3] = tmp
|
|
}
|
|
j ~mod+= 1
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[0] as base.u64, s: args.s)
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[1] as base.u64, s: args.s)
|
|
if count >= 3 {
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[2] as base.u64, s: args.s)
|
|
}
|
|
if count >= 4 {
|
|
this.write_bits!(n_bits: args.max_bits, bits: symbols[3] as base.u64, s: args.s)
|
|
// Tree-select.
|
|
if this.huff_depth[symbols[0] & 1023] == 1 {
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s)
|
|
} else {
|
|
this.write_bits!(n_bits: 1, bits: 0, s: args.s)
|
|
}
|
|
}
|
|
|
|
} else {
|
|
// Complex Huffman Tree.
|
|
this.write_bits!(n_bits: 40, bits: STATIC_CODE_LENGTH_CODE, s: args.s)
|
|
|
|
// Actual RLE coding.
|
|
prev_value = 8
|
|
i = 0
|
|
while i < length {
|
|
value = this.huff_depth[i & 1023] as base.u32
|
|
reps = 1
|
|
k = i ~mod+ 1
|
|
while k < length {
|
|
if (this.huff_depth[k & 1023] as base.u32) <> value {
|
|
break
|
|
}
|
|
reps ~mod+= 1
|
|
k ~mod+= 1
|
|
}
|
|
i ~mod+= reps
|
|
// Mirrors BrotliBuildAndStoreHuffmanTreeFast's kZeroRepsDepth[reps]
|
|
// and kNonZeroRepsDepth[reps] (704 entries each): a run can be
|
|
// longer than 511, e.g. the zeros between command codes 75 and
|
|
// 688.
|
|
if value == 0 {
|
|
this.write_bits!(n_bits: ZERO_REPS_DEPTH[reps.min(no_more_than: 703)], bits: ZERO_REPS_BITS[reps.min(no_more_than: 703)], s: args.s)
|
|
} else {
|
|
if prev_value <> value {
|
|
this.write_bits!(n_bits: CODE_LENGTH_DEPTH[value & 15], bits: CODE_LENGTH_BITS[value & 15], s: args.s)
|
|
reps ~mod-= 1
|
|
}
|
|
if reps < 3 {
|
|
while reps <> 0 {
|
|
reps -= 1
|
|
this.write_bits!(n_bits: CODE_LENGTH_DEPTH[value & 15], bits: CODE_LENGTH_BITS[value & 15], s: args.s)
|
|
}
|
|
} else {
|
|
reps -= 3
|
|
this.write_bits!(n_bits: NON_ZERO_REPS_DEPTH[reps.min(no_more_than: 703)], bits: NON_ZERO_REPS_BITS[reps.min(no_more_than: 703)], s: args.s)
|
|
}
|
|
prev_value = value
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// copy_huff_to_mb copies this.huff_depth[.. n] and this.huff_bits[.. n] to
|
|
// this.mb_lit_depth and this.mb_lit_bits (when cat is 0), this.mb_cmd_depth
|
|
// and this.mb_cmd_bits (when cat is 1) or this.mb_dist_depth and
|
|
// this.mb_dist_bits (when cat is 2).
|
|
pri func encoder.copy_huff_to_mb!(cat: base.u32, n: base.u32) {
|
|
var i : base.u32
|
|
|
|
i = 0
|
|
while i < args.n {
|
|
if args.cat == 0 {
|
|
this.mb_lit_depth[i & 255] = this.huff_depth[i & 1023]
|
|
this.mb_lit_bits[i & 255] = this.huff_bits[i & 1023]
|
|
} else if args.cat == 1 {
|
|
this.mb_cmd_depth[i & 1023] = this.huff_depth[i & 1023]
|
|
this.mb_cmd_bits[i & 1023] = this.huff_bits[i & 1023]
|
|
} else {
|
|
this.mb_dist_depth[i & 1023] = this.huff_depth[i & 1023]
|
|
this.mb_dist_bits[i & 1023] = this.huff_bits[i & 1023]
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
}
|
|
|
|
// load_huff_histo copies the first n elements of this.hist_lit (when cat is
|
|
// 0), this.hist_cmd (when cat is 1) or this.hist_dist (when cat is 2) to
|
|
// this.huff_histo.
|
|
pri func encoder.load_huff_histo!(cat: base.u32, n: base.u32) {
|
|
var i : base.u32
|
|
|
|
i = 0
|
|
while i < args.n {
|
|
if args.cat == 0 {
|
|
this.huff_histo[i & 1023] = this.hist_lit[i & 255]
|
|
} else if args.cat == 1 {
|
|
this.huff_histo[i & 1023] = this.hist_cmd[i & 1023]
|
|
} else {
|
|
this.huff_histo[i & 1023] = this.hist_dist[i & 1023]
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
}
|
|
|
|
// Mirrors BuildHistograms in brotli_bit_stream.c, into this.hist_lit,
|
|
// this.hist_cmd and this.hist_dist (with the C code's total_count_ values in
|
|
// this.hist_lit_total, etc).
|
|
pri func encoder.build_histograms!(wb: roslice base.u8, start_pos: base.u64, n_commands: base.u64) {
|
|
var pos : base.u64
|
|
var i : base.u64
|
|
var j : base.u32
|
|
var cmd_prefix : base.u16
|
|
var copy_len : base.u32
|
|
|
|
i = 0
|
|
while i < 1024 {
|
|
this.hist_cmd[i] = 0
|
|
this.hist_dist[i] = 0
|
|
if i < 256 {
|
|
this.hist_lit[i] = 0
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
this.hist_lit_total = 0
|
|
this.hist_cmd_total = 0
|
|
this.hist_dist_total = 0
|
|
|
|
pos = args.start_pos
|
|
i = 0
|
|
while i < args.n_commands {
|
|
cmd_prefix = this.cmd_cmd_prefix(wb: args.wb, i: i)
|
|
this.hist_cmd[cmd_prefix & 1023] ~mod+= 1
|
|
this.hist_cmd_total ~mod+= 1
|
|
j = this.cmd_insert_len(wb: args.wb, i: i)
|
|
while j > 0 {
|
|
this.hist_lit[this.rb_byte(wb: args.wb, pos: pos)] ~mod+= 1
|
|
this.hist_lit_total ~mod+= 1
|
|
pos ~mod+= 1
|
|
j -= 1
|
|
}
|
|
copy_len = this.cmd_copy_len(wb: args.wb, i: i)
|
|
pos ~mod+= copy_len as base.u64
|
|
if (copy_len <> 0) and (cmd_prefix >= 128) {
|
|
this.hist_dist[this.cmd_dist_prefix(wb: args.wb, i: i) & 0x3FF] ~mod+= 1
|
|
this.hist_dist_total ~mod+= 1
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
}
|
|
|
|
// Mirrors StoreDataWithHuffmanCodes in brotli_bit_stream.c. The depths and
|
|
// bits are this.mb_lit_depth and this.mb_lit_bits (etc) or, for the command
|
|
// and distance codes when static_codes is true, the C code's
|
|
// kStaticCommandCodeDepth (etc) tables.
|
|
pri func encoder.store_data_with_huffman_codes!(wb: roslice base.u8, start_pos: base.u64, n_commands: base.u64, static_codes: base.bool, s: slice base.u8) {
|
|
var pos : base.u64
|
|
var i : base.u64
|
|
var j : base.u32
|
|
var cmd_code : base.u32
|
|
var literal : base.u8
|
|
var copy_len : base.u32
|
|
var dist_prefix : base.u32
|
|
var dist_code : base.u32
|
|
|
|
pos = args.start_pos
|
|
i = 0
|
|
while i < args.n_commands {
|
|
cmd_code = (this.cmd_cmd_prefix(wb: args.wb, i: i) as base.u32) & 1023
|
|
if args.static_codes {
|
|
this.write_bits!(
|
|
n_bits: STATIC_COMMAND_CODE_DEPTH[cmd_code.min(no_more_than: 703)] as base.u32,
|
|
bits: STATIC_COMMAND_CODE_BITS[cmd_code.min(no_more_than: 703)] as base.u64,
|
|
s: args.s)
|
|
} else {
|
|
this.write_bits!(
|
|
n_bits: this.mb_cmd_depth[cmd_code] as base.u32,
|
|
bits: this.mb_cmd_bits[cmd_code] as base.u64,
|
|
s: args.s)
|
|
}
|
|
this.store_command_extra!(wb: args.wb, i: i, s: args.s)
|
|
j = this.cmd_insert_len(wb: args.wb, i: i)
|
|
while j > 0 {
|
|
literal = this.rb_byte(wb: args.wb, pos: pos)
|
|
this.write_bits!(
|
|
n_bits: this.mb_lit_depth[literal] as base.u32,
|
|
bits: this.mb_lit_bits[literal] as base.u64,
|
|
s: args.s)
|
|
pos ~mod+= 1
|
|
j -= 1
|
|
}
|
|
copy_len = this.cmd_copy_len(wb: args.wb, i: i)
|
|
pos ~mod+= copy_len as base.u64
|
|
if (copy_len <> 0) and (cmd_code >= 128) {
|
|
dist_prefix = this.cmd_dist_prefix(wb: args.wb, i: i) as base.u32
|
|
dist_code = dist_prefix & 0x3FF
|
|
if args.static_codes {
|
|
this.write_bits!(
|
|
n_bits: STATIC_DISTANCE_CODE_DEPTH[dist_code & 63] as base.u32,
|
|
bits: STATIC_DISTANCE_CODE_BITS[dist_code & 63] as base.u64,
|
|
s: args.s)
|
|
} else {
|
|
this.write_bits!(
|
|
n_bits: this.mb_dist_depth[dist_code] as base.u32,
|
|
bits: this.mb_dist_bits[dist_code] as base.u64,
|
|
s: args.s)
|
|
}
|
|
this.write_bits!(
|
|
n_bits: dist_prefix >> 10,
|
|
bits: this.cmd_dist_extra(wb: args.wb, i: i) as base.u64,
|
|
s: args.s)
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
}
|
|
|
|
// Mirrors BrotliStoreMetaBlockTrivial in brotli_bit_stream.c.
|
|
pri func encoder.store_meta_block_trivial!(wb: roslice base.u8, start_pos: base.u64, length: base.u64, is_last: base.bool, n_commands: base.u64, s: slice base.u8) {
|
|
this.store_compressed_meta_block_header!(is_final_block: args.is_last, length: args.length, s: args.s)
|
|
this.build_histograms!(wb: args.wb, start_pos: args.start_pos, n_commands: args.n_commands)
|
|
this.write_bits!(n_bits: 13, bits: 0, s: args.s)
|
|
|
|
this.load_huff_histo!(cat: 0, n: 256)
|
|
this.build_and_store_huffman_tree!(histogram_length: 256, alphabet_size: 256, s: args.s)
|
|
this.copy_huff_to_mb!(cat: 0, n: 256)
|
|
this.load_huff_histo!(cat: 1, n: 704)
|
|
this.build_and_store_huffman_tree!(histogram_length: 704, alphabet_size: 704, s: args.s)
|
|
this.copy_huff_to_mb!(cat: 1, n: 704)
|
|
// MAX_SIMPLE_DISTANCE_ALPHABET_SIZE is 140.
|
|
this.load_huff_histo!(cat: 2, n: 140)
|
|
this.build_and_store_huffman_tree!(histogram_length: 140, alphabet_size: this.dist_alphabet_size_max, s: args.s)
|
|
this.copy_huff_to_mb!(cat: 2, n: 140)
|
|
|
|
this.store_data_with_huffman_codes!(wb: args.wb, start_pos: args.start_pos, n_commands: args.n_commands, static_codes: false, s: args.s)
|
|
if args.is_last {
|
|
this.jump_to_byte_boundary!(s: args.s)
|
|
}
|
|
}
|
|
|
|
// Mirrors BrotliStoreMetaBlockFast in brotli_bit_stream.c.
|
|
pri func encoder.store_meta_block_fast!(wb: roslice base.u8, start_pos: base.u64, length: base.u64, is_last: base.bool, n_commands: base.u64, s: slice base.u8) {
|
|
var distance_alphabet_bits : base.u32
|
|
var pos : base.u64
|
|
var num_literals : base.u64
|
|
var i : base.u64
|
|
var j : base.u32
|
|
|
|
distance_alphabet_bits = this.log2_floor_non_zero(n: (this.dist_alphabet_size_max ~mod- 1) as base.u64) + 1
|
|
|
|
this.store_compressed_meta_block_header!(is_final_block: args.is_last, length: args.length, s: args.s)
|
|
this.write_bits!(n_bits: 13, bits: 0, s: args.s)
|
|
|
|
if args.n_commands <= 128 {
|
|
i = 0
|
|
while i < 1024 {
|
|
this.huff_histo[i] = 0
|
|
i ~mod+= 1
|
|
}
|
|
pos = args.start_pos
|
|
i = 0
|
|
while i < args.n_commands {
|
|
j = this.cmd_insert_len(wb: args.wb, i: i)
|
|
num_literals ~mod+= j as base.u64
|
|
while j > 0 {
|
|
this.huff_histo[this.rb_byte(wb: args.wb, pos: pos)] ~mod+= 1
|
|
pos ~mod+= 1
|
|
j -= 1
|
|
}
|
|
pos ~mod+= this.cmd_copy_len(wb: args.wb, i: i) as base.u64
|
|
i ~mod+= 1
|
|
}
|
|
this.build_and_store_huffman_tree_fast_generic!(histogram_total: num_literals, max_bits: 8, s: args.s)
|
|
this.copy_huff_to_mb!(cat: 0, n: 256)
|
|
// StoreStaticCommandHuffmanTree.
|
|
this.write_bits!(n_bits: 56, bits: STATIC_COMMAND_TREE_BITS, s: args.s)
|
|
this.write_bits!(n_bits: STATIC_COMMAND_TREE_NUM_BITS_2, bits: STATIC_COMMAND_TREE_BITS_2, s: args.s)
|
|
// StoreStaticDistanceHuffmanTree.
|
|
this.write_bits!(n_bits: STATIC_DISTANCE_TREE_NUM_BITS, bits: STATIC_DISTANCE_TREE_BITS, s: args.s)
|
|
this.store_data_with_huffman_codes!(wb: args.wb, start_pos: args.start_pos, n_commands: args.n_commands, static_codes: true, s: args.s)
|
|
} else {
|
|
this.build_histograms!(wb: args.wb, start_pos: args.start_pos, n_commands: args.n_commands)
|
|
this.load_huff_histo!(cat: 0, n: 256)
|
|
this.build_and_store_huffman_tree_fast_generic!(histogram_total: this.hist_lit_total, max_bits: 8, s: args.s)
|
|
this.copy_huff_to_mb!(cat: 0, n: 256)
|
|
this.load_huff_histo!(cat: 1, n: 704)
|
|
this.build_and_store_huffman_tree_fast_generic!(histogram_total: this.hist_cmd_total, max_bits: 10, s: args.s)
|
|
this.copy_huff_to_mb!(cat: 1, n: 704)
|
|
this.load_huff_histo!(cat: 2, n: 544)
|
|
this.build_and_store_huffman_tree_fast_generic!(histogram_total: this.hist_dist_total, max_bits: distance_alphabet_bits, s: args.s)
|
|
this.copy_huff_to_mb!(cat: 2, n: 544)
|
|
this.store_data_with_huffman_codes!(wb: args.wb, start_pos: args.start_pos, n_commands: args.n_commands, static_codes: false, s: args.s)
|
|
}
|
|
|
|
if args.is_last {
|
|
this.jump_to_byte_boundary!(s: args.s)
|
|
}
|
|
}
|
|
|
|
// Mirrors BlockLengthPrefixCode in brotli_bit_stream.c.
|
|
pri func encoder.block_length_prefix_code(len: base.u32) base.u32[..= 25] {
|
|
var code : base.u32[..= 25]
|
|
|
|
code = 0
|
|
if args.len >= 177 {
|
|
code = 14
|
|
if args.len >= 753 {
|
|
code = 20
|
|
}
|
|
} else if args.len >= 41 {
|
|
code = 7
|
|
}
|
|
while code < 25 {
|
|
if args.len < BLOCK_LENGTH_OFFSETS[code + 1] {
|
|
break
|
|
}
|
|
code += 1
|
|
}
|
|
return code
|
|
}
|
|
|
|
// Mirrors NextBlockTypeCode in brotli_bit_stream.c, for category c's block
|
|
// encoder's calculator (when c is 0, 1 or 2) or for a local calculator (when
|
|
// c is 3).
|
|
pri func encoder.next_block_type_code!(c: base.u32[..= 3], block_type: base.u32) base.u32 {
|
|
var type_code : base.u32
|
|
|
|
if args.block_type == (this.be_last_type[args.c] ~mod+ 1) {
|
|
type_code = 1
|
|
} else if args.block_type == this.be_second_last_type[args.c] {
|
|
type_code = 0
|
|
} else {
|
|
type_code = args.block_type ~mod+ 2
|
|
}
|
|
this.be_second_last_type[args.c] = this.be_last_type[args.c]
|
|
this.be_last_type[args.c] = args.block_type
|
|
return type_code
|
|
}
|
|
|
|
// Mirrors StoreBlockSwitch in brotli_bit_stream.c, for category c's block
|
|
// encoder.
|
|
pri func encoder.store_block_switch!(c: base.u32[..= 3], block_len: base.u32, block_type: base.u32, is_first_block: base.bool, s: slice base.u8) {
|
|
var typecode : base.u32
|
|
var lencode : base.u32[..= 25]
|
|
|
|
typecode = this.next_block_type_code!(c: args.c, block_type: args.block_type)
|
|
if not args.is_first_block {
|
|
this.write_bits!(
|
|
n_bits: this.be_type_depth[(args.c << 9) | (typecode & 511)] as base.u32,
|
|
bits: this.be_type_bits[(args.c << 9) | (typecode & 511)] as base.u64,
|
|
s: args.s)
|
|
}
|
|
lencode = this.block_length_prefix_code(len: args.block_len)
|
|
this.write_bits!(
|
|
n_bits: this.be_length_depth[(args.c << 5) | lencode] as base.u32,
|
|
bits: this.be_length_bits[(args.c << 5) | lencode] as base.u64,
|
|
s: args.s)
|
|
this.write_bits!(
|
|
n_bits: BLOCK_LENGTH_NBITS[lencode],
|
|
bits: (args.block_len ~mod- BLOCK_LENGTH_OFFSETS[lencode]) as base.u64,
|
|
s: args.s)
|
|
}
|
|
|
|
// Mirrors BuildAndStoreBlockSplitCode in brotli_bit_stream.c (via
|
|
// BuildAndStoreBlockSwitchEntropyCodes), for category c's block encoder.
|
|
pri func encoder.build_and_store_block_split_code!(wb: roslice base.u8, c: base.u32[..= 3], s: slice base.u8) {
|
|
var num_types : base.u32[..= 256]
|
|
var num_blocks : base.u64
|
|
var i : base.u64
|
|
var j : base.u32
|
|
var type_code : base.u32
|
|
var lencode : base.u32[..= 25]
|
|
|
|
num_types = this.be_num_block_types[args.c].min(no_more_than: 256)
|
|
num_blocks = this.be_num_blocks[args.c]
|
|
|
|
// type_histo (num_types + 2 elements) is this.huff_histo[0 .. 258] and
|
|
// length_histo (26 elements) is this.huff_histo[512 .. 538].
|
|
j = 0
|
|
while j < 538 {
|
|
this.huff_histo[j] = 0
|
|
j ~mod+= 1
|
|
}
|
|
this.be_last_type[3] = 1
|
|
this.be_second_last_type[3] = 0
|
|
i = 0
|
|
while i < num_blocks {
|
|
type_code = this.next_block_type_code!(c: 3,
|
|
block_type: this.byte_at(s: args.wb, i: this.gbs_types_off[args.c] ~mod+ i) as base.u32)
|
|
if i <> 0 {
|
|
this.huff_histo[type_code & 511] ~mod+= 1
|
|
}
|
|
lencode = this.block_length_prefix_code(
|
|
len: this.load32le(s: args.wb, i: this.gbs_lengths_off[args.c] ~mod+ (i ~mod* 4)))
|
|
this.huff_histo[512 + lencode] ~mod+= 1
|
|
i ~mod+= 1
|
|
}
|
|
this.store_var_len_uint8!(n: (num_types ~mod- 1) as base.u64, s: args.s)
|
|
if num_types > 1 {
|
|
this.build_and_store_huffman_tree!(histogram_length: num_types + 2, alphabet_size: num_types + 2, s: args.s)
|
|
j = 0
|
|
while j < (num_types + 2) {
|
|
this.be_type_depth[(args.c << 9) | (j & 511)] = this.huff_depth[j & 1023]
|
|
this.be_type_bits[(args.c << 9) | (j & 511)] = this.huff_bits[j & 1023]
|
|
j ~mod+= 1
|
|
}
|
|
j = 0
|
|
while j < 26 {
|
|
this.huff_histo[j] = this.huff_histo[512 + j]
|
|
j ~mod+= 1
|
|
}
|
|
this.build_and_store_huffman_tree!(histogram_length: 26, alphabet_size: 26, s: args.s)
|
|
j = 0
|
|
while j < 26 {
|
|
this.be_length_depth[(args.c << 5) | j] = this.huff_depth[j]
|
|
this.be_length_bits[(args.c << 5) | j] = this.huff_bits[j]
|
|
j ~mod+= 1
|
|
}
|
|
this.store_block_switch!(c: args.c,
|
|
block_len: this.load32le(s: args.wb, i: this.gbs_lengths_off[args.c]),
|
|
block_type: this.byte_at(s: args.wb, i: this.gbs_types_off[args.c]) as base.u32,
|
|
is_first_block: true,
|
|
s: args.s)
|
|
}
|
|
}
|
|
|
|
// Mirrors StoreTrivialContextMap in brotli_bit_stream.c.
|
|
pri func encoder.store_trivial_context_map!(num_types: base.u64, context_bits: base.u32[..= 6], s: slice base.u8) {
|
|
var repeat_code : base.u32
|
|
var repeat_bits : base.u64
|
|
var alphabet_size : base.u32
|
|
var i : base.u32
|
|
var code : base.u32
|
|
|
|
this.store_var_len_uint8!(n: args.num_types ~mod- 1, s: args.s)
|
|
if args.num_types > 1 {
|
|
repeat_code = args.context_bits ~mod- 1
|
|
repeat_bits = ((1 as base.u64) << (repeat_code & 31)) ~mod- 1
|
|
alphabet_size = ((args.num_types & 0x3FF) as base.u32) ~mod+ repeat_code
|
|
i = 0
|
|
while i < alphabet_size {
|
|
this.huff_histo[i & 1023] = 0
|
|
i ~mod+= 1
|
|
}
|
|
// Write RLEMAX.
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s)
|
|
this.write_bits!(n_bits: 4, bits: (repeat_code ~mod- 1) as base.u64, s: args.s)
|
|
this.huff_histo[repeat_code & 1023] = (args.num_types & 0xFFFF_FFFF) as base.u32
|
|
this.huff_histo[0] = 1
|
|
i = args.context_bits
|
|
while i < alphabet_size {
|
|
this.huff_histo[i & 1023] = 1
|
|
i ~mod+= 1
|
|
}
|
|
this.build_and_store_huffman_tree!(histogram_length: alphabet_size, alphabet_size: alphabet_size, s: args.s)
|
|
i = 0
|
|
while (i as base.u64) < args.num_types {
|
|
code = 0
|
|
if i <> 0 {
|
|
code = (i ~mod+ args.context_bits) ~mod- 1
|
|
}
|
|
this.write_bits!(
|
|
n_bits: this.huff_depth[code & 1023] as base.u32,
|
|
bits: this.huff_bits[code & 1023] as base.u64,
|
|
s: args.s)
|
|
this.write_bits!(
|
|
n_bits: this.huff_depth[repeat_code & 1023] as base.u32,
|
|
bits: this.huff_bits[repeat_code & 1023] as base.u64,
|
|
s: args.s)
|
|
this.write_bits!(n_bits: repeat_code, bits: repeat_bits, s: args.s)
|
|
i ~mod+= 1
|
|
}
|
|
// Write IMTF (inverse-move-to-front) bit.
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s)
|
|
}
|
|
}
|
|
|
|
// Mirrors EncodeContextMap in brotli_bit_stream.c (with MoveToFrontTransform
|
|
// and RunLengthCodeZeros), for the literal context map: this.mb_cmap_size u8
|
|
// values at the this.mb_cmap_off workbuf offset. The C code's rle_symbols
|
|
// are u32le values at the this.mb_rle_off workbuf offset.
|
|
pri func encoder.encode_context_map!(wb: slice base.u8, num_clusters: base.u64, s: slice base.u8) {
|
|
var size : base.u64
|
|
var i : base.u64
|
|
var k : base.u64
|
|
var max_value : base.u32[..= 255]
|
|
var v : base.u32
|
|
var vb : base.u32[..= 255]
|
|
var index : base.u32
|
|
var mtf_size : base.u32[..= 256]
|
|
var max_reps : base.u32
|
|
var reps : base.u32
|
|
var max_prefix : base.u32
|
|
var max_run_length_prefix : base.u32[..= 6]
|
|
var out_size : base.u64
|
|
var run_length_prefix : base.u32
|
|
var extra_bits : base.u32
|
|
var rle_symbol : base.u32
|
|
var j : base.u32
|
|
|
|
this.store_var_len_uint8!(n: args.num_clusters ~mod- 1, s: args.s)
|
|
if args.num_clusters == 1 {
|
|
return nothing
|
|
}
|
|
size = this.mb_cmap_size
|
|
|
|
// MoveToFrontTransform.
|
|
if size <> 0 {
|
|
max_value = 0
|
|
i = 0
|
|
while i < size {
|
|
vb = this.byte_at(s: args.wb, i: this.mb_cmap_off ~mod+ i) as base.u32
|
|
if vb > max_value {
|
|
max_value = vb
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
j = 0
|
|
while j <= max_value {
|
|
this.mtf[j & 255] = (j & 0xFF) as base.u8
|
|
j ~mod+= 1
|
|
}
|
|
mtf_size = max_value + 1
|
|
i = 0
|
|
while i < size {
|
|
v = this.byte_at(s: args.wb, i: this.mb_cmap_off ~mod+ i) as base.u32
|
|
index = 0
|
|
while index < mtf_size {
|
|
if (this.mtf[index & 255] as base.u32) == v {
|
|
break
|
|
}
|
|
index ~mod+= 1
|
|
}
|
|
this.poke_u32!(s: args.wb, i: this.mb_rle_off ~mod+ (i ~mod* 4), v: index)
|
|
// MoveToFront.
|
|
j = index
|
|
while j > 0 {
|
|
this.mtf[j & 255] = this.mtf[(j - 1) & 255]
|
|
j -= 1
|
|
}
|
|
this.mtf[0] = (v & 0xFF) as base.u8
|
|
i ~mod+= 1
|
|
}
|
|
}
|
|
|
|
// RunLengthCodeZeros.
|
|
i = 0
|
|
while i < size {
|
|
reps = 0
|
|
while (i < size) and (this.rle_sym(wb: args.wb, i: i) <> 0) {
|
|
i ~mod+= 1
|
|
}
|
|
while (i < size) and (this.rle_sym(wb: args.wb, i: i) == 0) {
|
|
reps ~mod+= 1
|
|
i ~mod+= 1
|
|
}
|
|
max_reps = max_reps.max(no_less_than: reps)
|
|
}
|
|
max_prefix = 0
|
|
if max_reps > 0 {
|
|
max_prefix = this.log2_floor_non_zero(n: max_reps as base.u64)
|
|
}
|
|
max_run_length_prefix = max_prefix.min(no_more_than: 6)
|
|
max_prefix = max_run_length_prefix
|
|
out_size = 0
|
|
i = 0
|
|
while i < size {
|
|
v = this.rle_sym(wb: args.wb, i: i)
|
|
if v <> 0 {
|
|
this.poke_u32!(s: args.wb, i: this.mb_rle_off ~mod+ (out_size ~mod* 4), v: v ~mod+ max_run_length_prefix)
|
|
i ~mod+= 1
|
|
out_size ~mod+= 1
|
|
} else {
|
|
reps = 1
|
|
k = i ~mod+ 1
|
|
while (k < size) and (this.rle_sym(wb: args.wb, i: k) == 0) {
|
|
reps ~mod+= 1
|
|
k ~mod+= 1
|
|
}
|
|
i ~mod+= reps as base.u64
|
|
while reps <> 0 {
|
|
if reps < ((2 as base.u32) << (max_prefix & 7)) {
|
|
run_length_prefix = this.log2_floor_non_zero(n: reps as base.u64)
|
|
extra_bits = reps ~mod- ((1 as base.u32) << run_length_prefix)
|
|
this.poke_u32!(s: args.wb, i: this.mb_rle_off ~mod+ (out_size ~mod* 4),
|
|
v: run_length_prefix ~mod+ (extra_bits ~mod<< 9))
|
|
out_size ~mod+= 1
|
|
break
|
|
} else {
|
|
extra_bits = ((1 as base.u32) << (max_prefix & 7)) ~mod- 1
|
|
this.poke_u32!(s: args.wb, i: this.mb_rle_off ~mod+ (out_size ~mod* 4),
|
|
v: max_prefix ~mod+ (extra_bits ~mod<< 9))
|
|
reps ~mod-= ((2 as base.u32) << (max_prefix & 7)) ~mod- 1
|
|
out_size ~mod+= 1
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
j = 0
|
|
while j < 272 {
|
|
this.huff_histo[j] = 0
|
|
j ~mod+= 1
|
|
}
|
|
i = 0
|
|
while i < out_size {
|
|
this.huff_histo[this.rle_sym(wb: args.wb, i: i) & 511] ~mod+= 1
|
|
i ~mod+= 1
|
|
}
|
|
if max_run_length_prefix > 0 {
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s)
|
|
this.write_bits!(n_bits: 4, bits: (max_run_length_prefix - 1) as base.u64, s: args.s)
|
|
} else {
|
|
this.write_bits!(n_bits: 1, bits: 0, s: args.s)
|
|
}
|
|
this.build_and_store_huffman_tree!(
|
|
histogram_length: ((args.num_clusters & 0x3FF) as base.u32) + max_run_length_prefix,
|
|
alphabet_size: ((args.num_clusters & 0x3FF) as base.u32) + max_run_length_prefix,
|
|
s: args.s)
|
|
i = 0
|
|
while i < out_size {
|
|
v = this.rle_sym(wb: args.wb, i: i)
|
|
rle_symbol = v & 511
|
|
this.write_bits!(
|
|
n_bits: this.huff_depth[rle_symbol] as base.u32,
|
|
bits: this.huff_bits[rle_symbol] as base.u64,
|
|
s: args.s)
|
|
if (rle_symbol > 0) and (rle_symbol <= max_run_length_prefix) {
|
|
this.write_bits!(n_bits: rle_symbol, bits: (v >> 9) as base.u64, s: args.s)
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
this.write_bits!(n_bits: 1, bits: 1, s: args.s) // use move-to-front
|
|
}
|
|
|
|
// rle_sym returns rle_symbols[i], the u32le at the this.mb_rle_off workbuf
|
|
// offset (plus 4 * i).
|
|
pri func encoder.rle_sym(wb: roslice base.u8, i: base.u64) base.u32 {
|
|
return this.load32le(s: args.wb, i: this.mb_rle_off ~mod+ (args.i ~mod* 4))
|
|
}
|
|
|
|
// Mirrors InitBlockEncoder in brotli_bit_stream.c, for category c, whose
|
|
// split is the greedy block splitter's.
|
|
pri func encoder.init_block_encoder!(wb: roslice base.u8, c: base.u32[..= 3], histogram_length: base.u32) {
|
|
this.be_histogram_length[args.c] = args.histogram_length
|
|
this.be_num_block_types[args.c] = this.gbs_num_types[args.c]
|
|
this.be_num_blocks[args.c] = this.gbs_split_num_blocks[args.c]
|
|
this.be_last_type[args.c] = 1
|
|
this.be_second_last_type[args.c] = 0
|
|
this.be_block_ix[args.c] = 0
|
|
this.be_block_len[args.c] = 0
|
|
if this.be_num_blocks[args.c] <> 0 {
|
|
this.be_block_len[args.c] = this.load32le(s: args.wb, i: this.gbs_lengths_off[args.c])
|
|
}
|
|
this.be_entropy_ix[args.c] = 0
|
|
}
|
|
|
|
// Mirrors FN(BuildAndStoreEntropyCodes) in block_encoder_inc.h, for category
|
|
// c: building and storing a Huffman code for each of its histograms, into
|
|
// the block encoder's depths_ and bits_ tables (at the this.be_depth_off[c]
|
|
// and this.be_bits_off[c] workbuf offsets, as u8 and u16le values).
|
|
pri func encoder.build_and_store_entropy_codes!(wb: slice base.u8, c: base.u32[..= 3], alphabet_size: base.u32, s: slice base.u8) {
|
|
var hlen : base.u32
|
|
var i : base.u64
|
|
var j : base.u32
|
|
var ix : base.u64
|
|
var hoff : base.u64
|
|
|
|
hlen = this.be_histogram_length[args.c].min(no_more_than: 1024)
|
|
i = 0
|
|
while i < this.gbs_histograms_size[args.c] {
|
|
hoff = this.gbs_histo_off(c: args.c, ix: i)
|
|
j = 0
|
|
while j < hlen {
|
|
this.huff_histo[j & 1023] = this.load32le(s: args.wb, i: hoff ~mod+ ((j as base.u64) * 4))
|
|
j ~mod+= 1
|
|
}
|
|
this.build_and_store_huffman_tree!(histogram_length: hlen, alphabet_size: args.alphabet_size, s: args.s)
|
|
ix = i ~mod* (hlen as base.u64)
|
|
j = 0
|
|
while j < hlen {
|
|
this.set_byte!(s: args.wb, i: (this.be_depth_off[args.c] ~mod+ ix) ~mod+ (j as base.u64), v: this.huff_depth[j & 1023])
|
|
this.poke_u16!(s: args.wb, i: this.be_bits_off[args.c] ~mod+ ((ix ~mod+ (j as base.u64)) ~mod* 2), v: this.huff_bits[j & 1023])
|
|
j ~mod+= 1
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
}
|
|
|
|
// Mirrors StoreSymbol and StoreSymbolWithContext in brotli_bit_stream.c. For
|
|
// StoreSymbolWithContext (with_context is true), the context map is the
|
|
// literal context map (the only context map below quality 10) and the
|
|
// context bits are 6.
|
|
pri func encoder.store_symbol!(wb: roslice base.u8, c: base.u32[..= 3], symbol: base.u64, with_context: base.bool, context: base.u64, s: slice base.u8) {
|
|
var block_ix : base.u64
|
|
var block_len : base.u32
|
|
var block_type : base.u32
|
|
var histo_ix : base.u64
|
|
var ix : base.u64
|
|
|
|
if this.be_block_len[args.c] == 0 {
|
|
block_ix = this.be_block_ix[args.c] ~mod+ 1
|
|
this.be_block_ix[args.c] = block_ix
|
|
block_len = this.load32le(s: args.wb, i: this.gbs_lengths_off[args.c] ~mod+ (block_ix ~mod* 4))
|
|
block_type = this.byte_at(s: args.wb, i: this.gbs_types_off[args.c] ~mod+ block_ix) as base.u32
|
|
this.be_block_len[args.c] = block_len
|
|
if args.with_context {
|
|
this.be_entropy_ix[args.c] = (block_type as base.u64) << 6
|
|
} else {
|
|
this.be_entropy_ix[args.c] = (block_type as base.u64) * (this.be_histogram_length[args.c] as base.u64)
|
|
}
|
|
this.store_block_switch!(c: args.c, block_len: block_len, block_type: block_type, is_first_block: false, s: args.s)
|
|
}
|
|
this.be_block_len[args.c] ~mod-= 1
|
|
if args.with_context {
|
|
histo_ix = this.byte_at(s: args.wb, i: (this.mb_cmap_off ~mod+ this.be_entropy_ix[args.c]) ~mod+ args.context) as base.u64
|
|
ix = (histo_ix * (this.be_histogram_length[args.c] as base.u64)) ~mod+ args.symbol
|
|
} else {
|
|
ix = this.be_entropy_ix[args.c] ~mod+ args.symbol
|
|
}
|
|
this.write_bits!(
|
|
n_bits: this.byte_at(s: args.wb, i: this.be_depth_off[args.c] ~mod+ ix) as base.u32,
|
|
bits: this.peek_u16(s: args.wb, i: this.be_bits_off[args.c] ~mod+ (ix ~mod* 2)) as base.u64,
|
|
s: args.s)
|
|
}
|
|
|
|
// Mirrors BrotliStoreMetaBlock in brotli_bit_stream.c, for the metablock
|
|
// split made by build_meta_block_greedy (whose distance context map is
|
|
// always empty) and a CONTEXT_UTF8 literal context mode.
|
|
pri func encoder.store_meta_block!(wb: slice base.u8, start_pos: base.u64, length: base.u64, prev_byte: base.u8, prev_byte2: base.u8,
|
|
is_last: base.bool, n_commands: base.u64, s: slice base.u8) {
|
|
var pos : base.u64
|
|
var prev_byte : base.u8
|
|
var prev_byte2 : base.u8
|
|
var i : base.u64
|
|
var j : base.u32
|
|
var cmd_prefix : base.u16
|
|
var copy_len : base.u32
|
|
var literal : base.u8
|
|
var context : base.u32
|
|
var dist_prefix : base.u32
|
|
|
|
pos = args.start_pos
|
|
prev_byte = args.prev_byte
|
|
prev_byte2 = args.prev_byte2
|
|
|
|
this.store_compressed_meta_block_header!(is_final_block: args.is_last, length: args.length, s: args.s)
|
|
|
|
this.init_block_encoder!(wb: args.wb, c: 0, histogram_length: 256)
|
|
this.init_block_encoder!(wb: args.wb, c: 1, histogram_length: 704)
|
|
this.init_block_encoder!(wb: args.wb, c: 2, histogram_length: this.dist_alphabet_size_limit)
|
|
|
|
this.build_and_store_block_split_code!(wb: args.wb, c: 0, s: args.s)
|
|
this.build_and_store_block_split_code!(wb: args.wb, c: 1, s: args.s)
|
|
this.build_and_store_block_split_code!(wb: args.wb, c: 2, s: args.s)
|
|
|
|
this.write_bits!(n_bits: 2, bits: this.distance_postfix_bits as base.u64, s: args.s)
|
|
this.write_bits!(n_bits: 4, bits: (this.num_direct_distance_codes >> (this.distance_postfix_bits & 3)) as base.u64, s: args.s)
|
|
j = 0
|
|
while j < this.gbs_num_types[0] {
|
|
// CONTEXT_UTF8 is 2.
|
|
this.write_bits!(n_bits: 2, bits: 2, s: args.s)
|
|
j ~mod+= 1
|
|
}
|
|
|
|
if this.mb_cmap_size == 0 {
|
|
this.store_trivial_context_map!(num_types: this.gbs_histograms_size[0], context_bits: 6, s: args.s)
|
|
} else {
|
|
this.encode_context_map!(wb: args.wb, num_clusters: this.gbs_histograms_size[0], s: args.s)
|
|
}
|
|
this.store_trivial_context_map!(num_types: this.gbs_histograms_size[2], context_bits: 2, s: args.s)
|
|
|
|
this.build_and_store_entropy_codes!(wb: args.wb, c: 0, alphabet_size: 256, s: args.s)
|
|
this.build_and_store_entropy_codes!(wb: args.wb, c: 1, alphabet_size: 704, s: args.s)
|
|
this.build_and_store_entropy_codes!(wb: args.wb, c: 2, alphabet_size: this.dist_alphabet_size_max, s: args.s)
|
|
|
|
i = 0
|
|
while i < args.n_commands {
|
|
cmd_prefix = this.cmd_cmd_prefix(wb: args.wb, i: i)
|
|
this.store_symbol!(wb: args.wb, c: 1, symbol: cmd_prefix as base.u64, with_context: false, context: 0, s: args.s)
|
|
this.store_command_extra!(wb: args.wb, i: i, s: args.s)
|
|
j = this.cmd_insert_len(wb: args.wb, i: i)
|
|
if this.mb_cmap_size == 0 {
|
|
while j > 0 {
|
|
this.store_symbol!(wb: args.wb, c: 0, symbol: this.rb_byte(wb: args.wb, pos: pos) as base.u64,
|
|
with_context: false, context: 0, s: args.s)
|
|
pos ~mod+= 1
|
|
j -= 1
|
|
}
|
|
} else {
|
|
while j > 0 {
|
|
context = (CONTEXT_LOOKUP[1024 + (prev_byte as base.u32)] |
|
|
CONTEXT_LOOKUP[1280 + (prev_byte2 as base.u32)]) as base.u32
|
|
literal = this.rb_byte(wb: args.wb, pos: pos)
|
|
this.store_symbol!(wb: args.wb, c: 0, symbol: literal as base.u64,
|
|
with_context: true, context: context as base.u64, s: args.s)
|
|
prev_byte2 = prev_byte
|
|
prev_byte = literal
|
|
pos ~mod+= 1
|
|
j -= 1
|
|
}
|
|
}
|
|
copy_len = this.cmd_copy_len(wb: args.wb, i: i)
|
|
pos ~mod+= copy_len as base.u64
|
|
if copy_len <> 0 {
|
|
prev_byte2 = this.rb_byte(wb: args.wb, pos: pos ~mod- 2)
|
|
prev_byte = this.rb_byte(wb: args.wb, pos: pos ~mod- 1)
|
|
if cmd_prefix >= 128 {
|
|
dist_prefix = this.cmd_dist_prefix(wb: args.wb, i: i) as base.u32
|
|
this.store_symbol!(wb: args.wb, c: 2, symbol: (dist_prefix & 0x3FF) as base.u64,
|
|
with_context: false, context: 0, s: args.s)
|
|
this.write_bits!(
|
|
n_bits: dist_prefix >> 10,
|
|
bits: this.cmd_dist_extra(wb: args.wb, i: i) as base.u64,
|
|
s: args.s)
|
|
}
|
|
}
|
|
i ~mod+= 1
|
|
}
|
|
if args.is_last {
|
|
this.jump_to_byte_boundary!(s: args.s)
|
|
}
|
|
}
|