// Copyright 2026 The Wuffs Authors. // // Licensed under the Apache License, Version 2.0 or the MIT license // , 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) } }