// 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 // -------- // Mirrors the BROTLI_STATE_HUFFMAN_CODE_0 through // BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY states of // BrotliDecoderDecompressStream in decode.c, followed by ProcessCommands. pri func decoder.decode_compressed_metablock?(src: base.io_reader, workbuf: slice base.u8, dictbuf: roslice base.u8) { var t : base.u32 var n : base.u32[..= 256] var n0 : base.u32[..= 256] var n2 : base.u32[..= 256] var bits : base.u32 var npostfix : base.u32[..= 3] var ndirect : base.u32[..= 120] var alphabet_max : base.u32[..= 1128] var alphabet : base.u32[..= 544] var i : base.u32 var k : base.u32 // BROTLI_STATE_HUFFMAN_CODE_0 ..= BROTLI_STATE_HUFFMAN_CODE_3. t = 0 while t < 3 { this.decode_var_len_uint8?(src: args.src) n = (this.bits_value & 0xFF) + 1 this.num_block_types[t] = n if n >= 2 { this.read_huffman_code?(src: args.src, alphabet_size_max: n + 2, alphabet_size_limit: n + 2, hoff: BLOCK_TYPE_HUFFS_BASE + (t * BLOCK_TYPE_HUFFS_STRIDE), table_size_max: BLOCK_TYPE_HUFFS_STRIDE) this.read_huffman_code?(src: args.src, alphabet_size_max: 26, alphabet_size_limit: 26, hoff: BLOCK_LEN_HUFFS_BASE + (t * BLOCK_LEN_HUFFS_STRIDE), table_size_max: BLOCK_LEN_HUFFS_STRIDE) this.read_block_length?(src: args.src, t: t) this.block_length[t] = this.bits_value } t += 1 } // BROTLI_STATE_METABLOCK_HEADER_2. this.read_bits?(src: args.src, n: 6) bits = this.bits_value npostfix = bits & 3 ndirect = ((bits >> 2) & 15) << npostfix this.distance_postfix_bits = npostfix this.num_direct_distance_codes = ndirect // BROTLI_STATE_CONTEXT_MODES. Mirrors ReadContextModes. n0 = this.num_block_types[0] i = 0 while i < n0 { assert i < 256 via "a < b: a < c; c <= b"(c: n0) this.read_bits?(src: args.src, n: 2) this.context_modes[i] = (this.bits_value & 3) as base.u8 i += 1 } // BROTLI_STATE_CONTEXT_MAP_1. this.decode_context_map?(src: args.src, size: n0 << 6, offset: 0) this.num_literal_htrees = this.bits_value.min(no_more_than: 256) // BROTLI_STATE_CONTEXT_MAP_2. n2 = this.num_block_types[2] this.decode_context_map?(src: args.src, size: n2 << 2, offset: DIST_CONTEXT_MAP_BASE) this.num_dist_htrees = this.bits_value.min(no_more_than: 256) if this.large_window { // BROTLI_DISTANCE_ALPHABET_SIZE(npostfix, ndirect, // BROTLI_LARGE_MAX_DISTANCE_BITS) and the max_alphabet_size of // BrotliCalculateDistanceCodeLimit(BROTLI_MAX_ALLOWED_DISTANCE, // npostfix, ndirect). alphabet_max = 16 + ndirect + ((62 as base.u32) << (npostfix + 1)) alphabet = this.calculate_distance_code_limit(npostfix: npostfix, ndirect: ndirect) } else { // BROTLI_DISTANCE_ALPHABET_SIZE(npostfix, ndirect, // BROTLI_MAX_DISTANCE_BITS). alphabet = 16 + ndirect + ((24 as base.u32) << (npostfix + 1)) alphabet_max = alphabet } this.distance_alphabet_size = alphabet // BROTLI_STATE_TREE_GROUP. Mirrors HuffmanTreeGroupDecode, three times. k = 0 while k < this.num_literal_htrees { assert k < 256 via "a < b: a < c; c <= b"(c: this.num_literal_htrees) this.read_huffman_code?(src: args.src, alphabet_size_max: 256, alphabet_size_limit: 256, hoff: LIT_HUFFS_BASE + (k * LIT_HUFFS_STRIDE), table_size_max: LIT_HUFFS_STRIDE) k += 1 } k = 0 while k < this.num_block_types[1] { assert k < 256 via "a < b: a < c; c <= b"(c: this.num_block_types[1]) this.read_huffman_code?(src: args.src, alphabet_size_max: 704, alphabet_size_limit: 704, hoff: CMD_HUFFS_BASE + (k * CMD_HUFFS_STRIDE), table_size_max: CMD_HUFFS_STRIDE) k += 1 } k = 0 while k < this.num_dist_htrees { assert k < 256 via "a < b: a < c; c <= b"(c: this.num_dist_htrees) this.read_huffman_code?(src: args.src, alphabet_size_max: alphabet_max, alphabet_size_limit: alphabet, hoff: DIST_HUFFS_BASE + (k * DIST_HUFFS_STRIDE), table_size_max: DIST_HUFFS_STRIDE) k += 1 } // BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY. this.prepare_literal_decoding!() this.dist_context_map_slice = 0 this.htree_command = 0 this.calculate_distance_lut!() this.process_commands?(src: args.src, workbuf: args.workbuf, dictbuf: args.dictbuf) } // Mirrors BrotliCalculateDistanceCodeLimit in constants.h, with a // max_distance of BROTLI_MAX_ALLOWED_DISTANCE (0x7FFF_FFFC). It returns the // max_alphabet_size, which is at most 544. pri func decoder.calculate_distance_code_limit(npostfix: base.u32[..= 3], ndirect: base.u32[..= 120]) base.u32[..= 544] { var offset : base.u32 var ndistbits : base.u32 var tmp : base.u32 var half : base.u32[..= 1] var group : base.u32 var postfix : base.u32[..= 7] var ret : base.u32 // The max_distance <= ndirect case cannot happen. // // offset is (forbidden_distance - ndirect - 1), where forbidden_distance // is (max_distance + 1), after removing the postfix and "head-start". offset = ((0x7FFF_FFFC - args.ndirect) >> args.npostfix) + 4 postfix = ((1 as base.u32) << args.npostfix) - 1 // Calculate the number of distance bits (a poor man's log2floor). tmp = offset / 2 ndistbits = 0 while (tmp <> 0) and (ndistbits < 32) { ndistbits += 1 tmp >>= 1 } // One bit is covered with subrange addressing ("half"). ndistbits ~mod-= 1 // Find the subrange. half = (offset >> (ndistbits & 31)) & 1 // Calculate the "group" part of the dcode. group = ((ndistbits ~mod- 1) ~mod<< 1) | half if group == 0 { return args.ndirect + 16 } // Decrement "group", so it is the last permitted "group". group -= 1 ret = (((group ~mod<< args.npostfix) | postfix) ~mod+ args.ndirect) ~mod+ 17 if ret > 544 { return 544 } return ret } // Mirrors DecodeContextMap in decode.c. The context map is written to // this.context_maps[args.offset .. args.offset + args.size] and the number // of Huffman trees (in [1 ..= 256]) is stored in this.bits_value. pri func decoder.decode_context_map?(src: base.io_reader, size: base.u32[..= 16384], offset: base.u32[..= 16384]) { var size : base.u32[..= 16384] var offset : base.u32[..= 16384] var num_htrees : base.u32[..= 256] var max_rle : base.u32[..= 16] var alphabet : base.u32[..= 272] var ci : base.u32 var code : base.u32 var reps : base.u32 var i : base.u32 size = args.size offset = args.offset this.decode_var_len_uint8?(src: args.src) num_htrees = (this.bits_value & 0xFF) + 1 if num_htrees <= 1 { ci = 0 while ci < size, inv num_htrees <= 1, { i = offset ~mod+ ci if i >= 17408 { return "#internal error: inconsistent ring buffer" } this.context_maps[i] = 0 ci ~mod+= 1 } this.bits_value = num_htrees return ok } // BROTLI_STATE_CONTEXT_MAP_READ_PREFIX. max_rle = 0 this.read_bits?(src: args.src, n: 1) if this.bits_value <> 0 { this.read_bits?(src: args.src, n: 4) max_rle = (this.bits_value & 15) + 1 } // BROTLI_STATE_CONTEXT_MAP_HUFFMAN. alphabet = num_htrees + max_rle this.read_huffman_code?(src: args.src, alphabet_size_max: alphabet, alphabet_size_limit: alphabet, hoff: CONTEXT_MAP_HUFFS_BASE, table_size_max: 646) // BROTLI_STATE_CONTEXT_MAP_DECODE. ci = 0 while ci < size { this.read_symbol?(src: args.src, hoff: CONTEXT_MAP_HUFFS_BASE) code = this.symbol if (code == 0) or (code > max_rle) { i = offset ~mod+ ci if i >= 17408 { return "#internal error: inconsistent ring buffer" } if code == 0 { this.context_maps[i] = 0 } else { this.context_maps[i] = ((code ~mod- max_rle) & 0xFF) as base.u8 } ci ~mod+= 1 continue } // RLE sub-stage. code is in [1 ..= max_rle] and max_rle <= 16. this.read_bits?(src: args.src, n: code.min(no_more_than: 16)) reps = this.bits_value ~mod+ ((1 as base.u32) << code.min(no_more_than: 16)) if reps > (size ~mod- ci) { return "#bad context map repeat" } while reps > 0 { i = offset ~mod+ ci if i >= 17408 { return "#internal error: inconsistent ring buffer" } this.context_maps[i] = 0 ci ~mod+= 1 reps -= 1 } } // BROTLI_STATE_CONTEXT_MAP_TRANSFORM. this.read_bits?(src: args.src, n: 1) if this.bits_value <> 0 { this.inverse_move_to_front_transform!(offset: offset, size: size) } this.bits_value = num_htrees } // Mirrors InverseMoveToFrontTransform in decode.c. That C function // re-initializes only part of its move-to-front list, but that's an // optimization: it's equivalent to re-initializing all of it. pri func decoder.inverse_move_to_front_transform!(offset: base.u32[..= 16384], size: base.u32[..= 16384]) { var i : base.u32 var j : base.u32 var index : base.u32[..= 0xFF] var value : base.u8 i = 0 while i < 256 { this.mtf[i] = (i & 0xFF) as base.u8 i += 1 } i = 0 while i < args.size { j = args.offset ~mod+ i if j >= 17408 { return nothing } index = this.context_maps[j] as base.u32 value = this.mtf[index] this.context_maps[j] = value while index > 0 { this.mtf[index] = this.mtf[index - 1] index -= 1 } this.mtf[0] = value i ~mod+= 1 } } // read_block_length reads a block length, using the args.t'th block length // prefix code, and stores it in this.bits_value. Mirrors SafeReadBlockLength // in decode.c. pri func decoder.read_block_length?(src: base.io_reader, t: base.u32[..= 2]) { var code : base.u32[..= 25] this.read_symbol?(src: args.src, hoff: BLOCK_LEN_HUFFS_BASE + (args.t * BLOCK_LEN_HUFFS_STRIDE)) if this.symbol >= 26 { return "#internal error: inconsistent Huffman table" } code = this.symbol.min(no_more_than: 25) this.read_bits?(src: args.src, n: BLOCK_LENGTH_NBITS[code]) this.bits_value = BLOCK_LENGTH_OFFSETS[code] ~mod+ this.bits_value } // Mirrors DecodeBlockTypeAndLength in decode.c. pri func decoder.decode_block_switch?(src: base.io_reader, t: base.u32[..= 2]) { var t : base.u32[..= 2] var max_block_type : base.u32 var block_type : base.u32 t = args.t if this.num_block_types[t] <= 1 { return "#bad block switch" } this.read_symbol?(src: args.src, hoff: BLOCK_TYPE_HUFFS_BASE + (t * BLOCK_TYPE_HUFFS_STRIDE)) block_type = this.symbol this.read_block_length?(src: args.src, t: t) this.block_length[t] = this.bits_value max_block_type = this.num_block_types[t] if block_type == 1 { block_type = this.block_type_rb[(2 * t) + 1] ~mod+ 1 } else if block_type == 0 { block_type = this.block_type_rb[2 * t] } else { block_type ~mod-= 2 } if block_type >= max_block_type { block_type -= max_block_type } this.block_type_rb[2 * t] = this.block_type_rb[(2 * t) + 1] this.block_type_rb[(2 * t) + 1] = block_type } // Mirrors PrepareLiteralDecoding in decode.c. pri func decoder.prepare_literal_decoding!() { var block_type : base.u32[..= 0xFF] block_type = this.block_type_rb[1] & 0xFF this.context_map_slice = block_type << 6 this.context_mode = (this.context_modes[block_type] & 3) as base.u32 } // Mirrors CalculateDistanceLut in decode.c. pri func decoder.calculate_distance_lut!() { var npostfix : base.u32[..= 3] var ndirect : base.u32[..= 120] var limit : base.u32[..= 544] var postfix : base.u32[..= 8] var i : base.u32 var j : base.u32 var bits : base.u32 var half : base.u32 var dbase : base.u32 npostfix = this.distance_postfix_bits ndirect = this.num_direct_distance_codes limit = this.distance_alphabet_size postfix = (1 as base.u32) << npostfix // Skip short codes. i = 16 // Fill direct codes. j = 0 while j < ndirect { if i >= 1128 { return nothing } this.dist_extra_bits[i] = 0 this.dist_offset[i] = j ~mod+ 1 i ~mod+= 1 j ~mod+= 1 } // Fill regular distance codes. bits = 1 half = 0 while i < limit { dbase = (((2 ~mod+ half) ~mod<< (bits & 31)) ~mod- 4) ~mod<< npostfix dbase = (ndirect ~mod+ dbase) ~mod+ 1 // Always fill the complete group. j = 0 while j < postfix { if i >= 1128 { return nothing } this.dist_extra_bits[i] = (bits & 0xFF) as base.u8 this.dist_offset[i] = dbase ~mod+ j i ~mod+= 1 j ~mod+= 1 } bits = bits ~mod+ half half = half ^ 1 } } // Mirrors ProcessCommandsInternal in decode.c. pri func decoder.process_commands?(src: base.io_reader, workbuf: slice base.u8, dictbuf: roslice base.u8) { var cmd_code : base.u32[..= 703] var p1 : base.u32[..= 0xFF] var p2 : base.u32[..= 0xFF] var mode_offset : base.u32[..= 0x600] var ctx : base.u32[..= 63] var tree : base.u32[..= 0xFF] var max_distance : base.u32 var distance : base.u32 var i : base.u32 var n : base.u32 var k : base.u32 var b : base.u8 var compound_size : base.u32 var address : base.u32 var chunk : base.u32[..= 14] var j : base.u64 var fr : base.u32 var dst_i : base.u64 var src_i : base.u64 var k64 : base.u64 var n64 : base.u64 var dlo : base.u64 var dhi : base.u64 var slo : base.u64 var shi : base.u64 var fs : base.status while true { if (this.cmd_state == 0) and (args.src.length() >= 16) { fs = this.process_commands_fast!(src: args.src, workbuf: args.workbuf) if not fs.is_ok() { return fs } else if this.cmd_state == 4 { this.cmd_state = 0 return ok } } if this.cmd_state == 0 { // CommandBegin. if this.block_length[1] == 0 { // Mirrors DecodeCommandBlockSwitch. this.decode_block_switch?(src: args.src, t: 1) this.htree_command = this.block_type_rb[3] & 0xFF continue } // Mirrors ReadCommandInternal. fr = this.read_symbol_fast!(src: args.src, hoff: CMD_HUFFS_BASE + (this.htree_command * CMD_HUFFS_STRIDE)) if fr <> 0 { this.read_symbol?(src: args.src, hoff: CMD_HUFFS_BASE + (this.htree_command * CMD_HUFFS_STRIDE)) } if this.symbol >= 704 { return "#internal error: inconsistent Huffman table" } cmd_code = this.symbol.min(no_more_than: 703) this.implicit_zero_distance = CMD_IMPLICIT_ZERO_DISTANCE[cmd_code] <> 0 this.distance_context = CMD_DISTANCE_CONTEXT[cmd_code] as base.u32 this.update_dist_htree_index!() fr = this.read_bits_fast!(src: args.src, n: CMD_INSERT_LEN_EXTRA_BITS[cmd_code] as base.u32) if fr <> 0 { this.read_bits?(src: args.src, n: CMD_INSERT_LEN_EXTRA_BITS[cmd_code] as base.u32) } this.insert_length = CMD_INSERT_LEN_OFFSET[cmd_code] ~mod+ this.bits_value fr = this.read_bits_fast!(src: args.src, n: CMD_COPY_LEN_EXTRA_BITS[cmd_code] as base.u32) if fr <> 0 { this.read_bits?(src: args.src, n: CMD_COPY_LEN_EXTRA_BITS[cmd_code] as base.u32) } this.copy_length = CMD_COPY_LEN_OFFSET[cmd_code] ~mod+ this.bits_value this.block_length[1] ~mod-= 1 if this.insert_length > 0 { this.mb_remaining ~mod-= this.insert_length this.cmd_state = 1 } else { this.cmd_state = 2 } } if this.cmd_state == 1 { // CommandInner. Read the literals in the command. while this.insert_length > 0 { if this.block_length[0] == 0 { // Mirrors DecodeLiteralBlockSwitch. this.decode_block_switch?(src: args.src, t: 0) this.prepare_literal_decoding!() continue } p1 = this.get_byte(workbuf: args.workbuf, distance: 1) as base.u32 p2 = this.get_byte(workbuf: args.workbuf, distance: 2) as base.u32 mode_offset = this.context_mode << 9 // BROTLI_CONTEXT(p1, p2, s->context_lookup). ctx = (CONTEXT_LOOKUP[mode_offset | p1] | CONTEXT_LOOKUP[mode_offset | 0x100 | p2]) as base.u32 tree = this.context_maps[this.context_map_slice + ctx] as base.u32 fr = this.read_symbol_fast!(src: args.src, hoff: LIT_HUFFS_BASE + (tree * LIT_HUFFS_STRIDE)) if fr <> 0 { this.read_symbol?(src: args.src, hoff: LIT_HUFFS_BASE + (tree * LIT_HUFFS_STRIDE)) } this.put_byte!(workbuf: args.workbuf, b: (this.symbol & 0xFF) as base.u8) this.block_length[0] ~mod-= 1 this.insert_length ~mod-= 1 if this.pos == this.rb_size { this.ring_event?() } } this.cmd_state = 2 if (this.mb_remaining == 0) or (this.mb_remaining >= 0x8000_0000) { // BROTLI_STATE_METABLOCK_DONE. this.cmd_state = 0 return ok } } if this.cmd_state == 2 { // CommandPostDecodeLiterals. if this.implicit_zero_distance { // Implicit distance case. this.distance_context = 1 this.dist_rb_idx ~mod-= 1 this.distance_code = this.dist_rb[this.dist_rb_idx & 3] } else { // Read distance code in the command, unless it was implicitly // zero. if this.block_length[2] == 0 { // Mirrors DecodeDistanceBlockSwitch. this.decode_block_switch?(src: args.src, t: 2) this.dist_context_map_slice = (this.block_type_rb[5] & 0xFF) << 2 this.update_dist_htree_index!() } this.read_distance?(src: args.src) } this.cmd_state = 3 } // this.cmd_state == 3. if this.max_distance <> this.max_backward_distance { this.max_distance = this.pos.min(no_more_than: this.max_backward_distance) } max_distance = this.max_distance i = this.copy_length distance = this.distance_code if distance > max_distance { // Apply a compound dictionary or static dictionary reference, // since the distance is larger than the max LZ77 distance. // // The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE. if distance > 0x7FFF_FFFC { return "#bad distance" } compound_size = this.chunk_offsets[this.num_chunks] address = (distance - max_distance) - 1 if address < compound_size { // Mirrors InitializeCompoundDictionaryCopy and // CopyFromCompoundDictionary in decode.c. This address is the // C code's (compound_dictionary_size - (s->distance_code - // s->max_distance)). address = compound_size ~mod- (address + 1) if ((address as base.u64) + (i as base.u64)) > (compound_size as base.u64) { return "#bad compound dictionary" } // Update the recent distances cache. this.dist_rb[this.dist_rb_idx & 3] = distance this.dist_rb_idx ~mod+= 1 this.mb_remaining ~mod-= i chunk = 0 while i > 0 { while chunk < 14 { if address < this.chunk_offsets[chunk + 1] { break } chunk += 1 } j = (this.chunk_starts[chunk] as base.u64) + ((address ~mod- this.chunk_offsets[chunk]) as base.u64) b = 0 if j < args.dictbuf.length() { b = args.dictbuf[j] } this.put_byte!(workbuf: args.workbuf, b: b) address ~mod+= 1 i ~mod-= 1 if this.pos == this.rb_size { this.ring_event?() } } } else if (4 <= i) and (i <= 31) { // SHARED_BROTLI_MIN_DICTIONARY_WORD_LENGTH and // SHARED_BROTLI_MAX_DICTIONARY_WORD_LENGTH. p1 = this.get_byte(workbuf: args.workbuf, distance: 1) as base.u32 p2 = this.get_byte(workbuf: args.workbuf, distance: 2) as base.u32 mode_offset = this.context_mode << 9 ctx = (CONTEXT_LOOKUP[mode_offset | p1] | CONTEXT_LOOKUP[mode_offset | 0x100 | p2]) as base.u32 // Compensate double distance-ring-buffer roll. this.dist_rb_idx ~mod+= this.distance_context n = this.copy_dictionary_word!(dictbuf: args.dictbuf, address: address ~mod- compound_size, len: i.min(no_more_than: 31), ctx: ctx) if n == 0xFFFF_FFFE { return "#bad dictionary" } else if n == 0xFFFF_FFFF { return "#bad transform" } else if (n == 0) and (distance <= 120) { return "#bad transform" } this.mb_remaining ~mod-= n k = 0 while k < n { this.put_byte!(workbuf: args.workbuf, b: this.transformed_word[k & 1023]) k ~mod+= 1 if this.pos == this.rb_size { this.ring_event?() } } } else { return "#bad dictionary" } } else { // Apply an LZ77 copy. Update the recent distances cache. this.dist_rb[this.dist_rb_idx & 3] = distance this.dist_rb_idx ~mod+= 1 this.mb_remaining ~mod-= i // Fast path: when the copy neither wraps around the physical ring // buffer (at either end) nor makes this.pos reach this.rb_size, // copy the bytes in chunks of at most distance bytes. Each chunk's // source bytes are final (and do not overlap the chunk's // destination), so this matches the byte by byte loop below. dst_i = this.pos as base.u64 src_i = ((this.pos ~mod- distance) & (this.window_size ~mod- 1)) as base.u64 if ((dst_i + (i as base.u64)) < (this.rb_size as base.u64)) and ((src_i + (i as base.u64)) <= (this.window_size as base.u64)) and ((this.window_size as base.u64) <= args.workbuf.length()) and (distance > 0) { k64 = 0 while k64 < (i as base.u64) { n64 = (i as base.u64) ~mod- k64 n64 = n64.min(no_more_than: distance as base.u64) dlo = dst_i ~mod+ k64 dhi = dlo ~mod+ n64 slo = src_i ~mod+ k64 shi = slo ~mod+ n64 if (n64 == 0) or (dlo > dhi) or (dhi > args.workbuf.length()) or (slo > shi) or (shi > args.workbuf.length()) { break } args.workbuf[dlo .. dhi].copy_from_slice!(s: args.workbuf[slo .. shi]) k64 ~mod+= n64 } // k64 == i, unless the (unreachable) break above was taken, // in which case the loop below copies the remaining bytes. this.pos ~mod+= (k64 & 0xFFFF_FFFF) as base.u32 i ~mod-= (k64 & 0xFFFF_FFFF) as base.u32 } while i > 0 { b = this.get_byte(workbuf: args.workbuf, distance: distance) this.put_byte!(workbuf: args.workbuf, b: b) i -= 1 if this.pos == this.rb_size { this.ring_event?() } } } this.cmd_state = 0 if (this.mb_remaining == 0) or (this.mb_remaining >= 0x8000_0000) { // BROTLI_STATE_METABLOCK_DONE. return ok } } } // process_commands_fast is a fast path for process_commands. It is not a // coroutine. It handles commands, or parts of commands (see // decoder.cmd_state), for as long as args.src holds enough bytes and the work // needs no block switch, ring buffer event or dictionary reference. Then it // returns, and process_commands picks up where it left off. // // It reads ahead, up to 8 bytes at a time, into a 64-bit bit buffer. When it // returns, it gives back (undoes) the whole bytes left in that buffer. The // coroutines read_symbol and read_bits read an input byte only when they // need more bits, so that between reads, fewer than 8 bits are buffered. // Giving back the whole bytes restores that state exactly, so this function // reads the same bits and leaves the decoder in the same state as // process_commands would, and it writes the same bytes and returns the same // errors. It sets this.cmd_state to 4 when the metablock is done. pri func decoder.process_commands_fast!(src: base.io_reader, workbuf: slice base.u8) base.status { var ret : base.status var bits : base.u64 var n_bits : base.u32[..= 63] var i : base.u32 var e : base.u32 var e_bits : base.u32[..= 23] var cmd_code : base.u32[..= 703] var nb : base.u32[..= 24] var p1 : base.u32[..= 0xFF] var p2 : base.u32[..= 0xFF] var mode_offset : base.u32[..= 0x600] var ctx : base.u32[..= 63] var tree : base.u32[..= 0xFF] var code : base.u32 var nbits : base.u32[..= 32] var lo : base.u32 var max_distance : base.u32 var distance : base.u32 var n : base.u32 var dst_i : base.u64 var src_i : base.u64 var k64 : base.u64 var n64 : base.u64 var dlo : base.u64 var dhi : base.u64 var slo : base.u64 var shi : base.u64 var cm_slice : base.u32[..= 16320] var wmask : base.u32 var pos : base.u32 var lit_n : base.u32 var lit_i : base.u32 var wi : base.u64 var copied16 : base.bool if this.n_bits >= 8 { return ok } n_bits = this.n_bits & 7 bits = (this.bits as base.u64) & (((1 as base.u64) << n_bits) - 1) while.outer true { if this.cmd_state == 0 { // Two refills, of at most 8 bytes each. if (this.block_length[1] == 0) or (args.src.length() < 16) { break.outer } bits |= args.src.peek_u64le() ~mod<< n_bits args.src.skip_u32_fast!(actual: (63 - n_bits) >> 3, worst_case: 8) n_bits |= 56 // Mirrors ReadCommandInternal. i = (CMD_HUFFS_BASE + (this.htree_command * CMD_HUFFS_STRIDE)) ~mod+ ((bits & 0xFF) as base.u32) if i >= HUFFS_LEN { ret = "#internal error: inconsistent Huffman table" break.outer } e = this.huffs[i] as base.u32 e_bits = e & 15 if e_bits > 8 { i = ((CMD_HUFFS_BASE + (this.htree_command * CMD_HUFFS_STRIDE)) ~mod+ (e >> 4)) ~mod+ ((((bits >> 8) & 0x7FFF) as base.u32) & (((1 as base.u32) << (e_bits - 8)) - 1)) if i >= HUFFS_LEN { ret = "#internal error: inconsistent Huffman table" break.outer } e = this.huffs[i] as base.u32 e_bits = (e & 15) + 8 } if n_bits < e_bits { ret = "#internal error: inconsistent bit reader" break.outer } bits >>= e_bits n_bits -= e_bits if (e >> 4) >= 704 { ret = "#internal error: inconsistent Huffman table" break.outer } this.symbol = e >> 4 cmd_code = this.symbol.min(no_more_than: 703) this.implicit_zero_distance = CMD_IMPLICIT_ZERO_DISTANCE[cmd_code] <> 0 this.distance_context = CMD_DISTANCE_CONTEXT[cmd_code] as base.u32 this.update_dist_htree_index!() nb = CMD_INSERT_LEN_EXTRA_BITS[cmd_code] as base.u32 if n_bits < nb { ret = "#internal error: inconsistent bit reader" break.outer } this.bits_value = ((bits & (((1 as base.u64) << nb) - 1)) & 0xFFFF_FFFF) as base.u32 bits >>= nb n_bits -= nb this.insert_length = CMD_INSERT_LEN_OFFSET[cmd_code] ~mod+ this.bits_value if args.src.length() < 8 { ret = "#internal error: inconsistent bit reader" break.outer } bits |= args.src.peek_u64le() ~mod<< n_bits args.src.skip_u32_fast!(actual: (63 - n_bits) >> 3, worst_case: 8) n_bits |= 56 nb = CMD_COPY_LEN_EXTRA_BITS[cmd_code] as base.u32 if n_bits < nb { ret = "#internal error: inconsistent bit reader" break.outer } this.bits_value = ((bits & (((1 as base.u64) << nb) - 1)) & 0xFFFF_FFFF) as base.u32 bits >>= nb n_bits -= nb this.copy_length = CMD_COPY_LEN_OFFSET[cmd_code] ~mod+ this.bits_value this.block_length[1] ~mod-= 1 if this.insert_length > 0 { this.mb_remaining ~mod-= this.insert_length this.cmd_state = 1 } else { this.cmd_state = 2 } } if this.cmd_state == 1 { // CommandInner. Read the literals in the command. p1 and p2 are // the last two bytes written to the ring buffer (put_byte always // writes when the physical ring buffer fits in args.workbuf). if (this.window_size as base.u64) > args.workbuf.length() { break.outer } p1 = this.get_byte(workbuf: args.workbuf, distance: 1) as base.u32 p2 = this.get_byte(workbuf: args.workbuf, distance: 2) as base.u32 mode_offset = this.context_mode << 9 cm_slice = this.context_map_slice wmask = this.window_size ~mod- 1 pos = this.pos // lit_n is how many literals the loop below decodes before this // command's literals, this block's literals or the ring buffer // (before the next ring_event) run out. The loop keeps pos, the // counts and the symbol in local variables, and writes them back // to this.etc fields before every break. lit_n = this.insert_length.min(no_more_than: this.block_length[0]) if (pos ~mod+ 1) >= this.rb_size { lit_n = 0 } else { lit_n = lit_n.min(no_more_than: (this.rb_size ~mod- pos) ~mod- 1) } lit_i = 0 while lit_i < lit_n { if n_bits < 24 { if args.src.length() < 8 { break } bits |= args.src.peek_u64le() ~mod<< n_bits args.src.skip_u32_fast!(actual: (63 - n_bits) >> 3, worst_case: 8) n_bits |= 56 } ctx = (CONTEXT_LOOKUP[mode_offset | p1] | CONTEXT_LOOKUP[mode_offset | 0x100 | p2]) as base.u32 tree = this.context_maps[cm_slice + ctx] as base.u32 i = (LIT_HUFFS_BASE + (tree * LIT_HUFFS_STRIDE)) ~mod+ ((bits & 0xFF) as base.u32) if i >= HUFFS_LEN { ret = "#internal error: inconsistent Huffman table" break } e = this.huffs[i] as base.u32 e_bits = e & 15 if e_bits > 8 { i = ((LIT_HUFFS_BASE + (tree * LIT_HUFFS_STRIDE)) ~mod+ (e >> 4)) ~mod+ ((((bits >> 8) & 0x7FFF) as base.u32) & (((1 as base.u32) << (e_bits - 8)) - 1)) if i >= HUFFS_LEN { ret = "#internal error: inconsistent Huffman table" break } e = this.huffs[i] as base.u32 e_bits = (e & 15) + 8 } if n_bits < e_bits { ret = "#internal error: inconsistent bit reader" break } bits >>= e_bits n_bits -= e_bits p2 = p1 p1 = (e >> 4) & 0xFF wi = (pos & wmask) as base.u64 if wi < args.workbuf.length() { args.workbuf[wi] = p1 as base.u8 } pos ~mod+= 1 lit_i ~mod+= 1 } if lit_i > 0 { this.symbol = p1 this.pos = pos this.block_length[0] ~mod-= lit_i this.insert_length ~mod-= lit_i } if (ret.is_error()) or (this.insert_length > 0) { break.outer } this.cmd_state = 2 if (this.mb_remaining == 0) or (this.mb_remaining >= 0x8000_0000) { this.cmd_state = 4 break.outer } } if this.cmd_state == 2 { // CommandPostDecodeLiterals. if this.implicit_zero_distance { this.distance_context = 1 this.dist_rb_idx ~mod-= 1 this.distance_code = this.dist_rb[this.dist_rb_idx & 3] } else { // One refill: 56 bits suffice for a symbol and 32 extra bits. if (this.block_length[2] == 0) or (args.src.length() < 8) { break.outer } bits |= args.src.peek_u64le() ~mod<< n_bits args.src.skip_u32_fast!(actual: (63 - n_bits) >> 3, worst_case: 8) n_bits |= 56 // Mirrors read_distance. i = (DIST_HUFFS_BASE + (this.dist_htree_index * DIST_HUFFS_STRIDE)) ~mod+ ((bits & 0xFF) as base.u32) if i >= HUFFS_LEN { ret = "#internal error: inconsistent Huffman table" break.outer } e = this.huffs[i] as base.u32 e_bits = e & 15 if e_bits > 8 { i = ((DIST_HUFFS_BASE + (this.dist_htree_index * DIST_HUFFS_STRIDE)) ~mod+ (e >> 4)) ~mod+ ((((bits >> 8) & 0x7FFF) as base.u32) & (((1 as base.u32) << (e_bits - 8)) - 1)) if i >= HUFFS_LEN { ret = "#internal error: inconsistent Huffman table" break.outer } e = this.huffs[i] as base.u32 e_bits = (e & 15) + 8 } if n_bits < e_bits { ret = "#internal error: inconsistent bit reader" break.outer } bits >>= e_bits n_bits -= e_bits this.symbol = e >> 4 code = this.symbol this.block_length[2] ~mod-= 1 this.distance_context = 0 if code < 16 { this.take_distance_from_ring_buffer!(code: code) } else { if (code >= this.distance_alphabet_size) or (code >= 1128) { ret = "#internal error: inconsistent Huffman table" break.outer } nbits = this.dist_extra_bits[code].min(no_more_than: 32) as base.u32 if n_bits < nbits { ret = "#internal error: inconsistent bit reader" break.outer } // Like read_bits32, this is (lo | (hi << 16)) when nbits // is more than 24. lo = ((bits & (((1 as base.u64) << nbits) - 1)) & 0xFFFF_FFFF) as base.u32 this.bits_value = lo bits >>= nbits n_bits -= nbits this.distance_code = (((this.dist_offset[code] as base.u64) ~mod+ ((this.bits_value as base.u64) ~mod<< this.distance_postfix_bits)) & 0xFFFF_FFFF) as base.u32 } } this.cmd_state = 3 } // this.cmd_state == 3. Only handle LZ77 copies that need no ring // buffer event and do not wrap around the physical ring buffer. max_distance = this.max_distance if max_distance <> this.max_backward_distance { max_distance = this.pos.min(no_more_than: this.max_backward_distance) } distance = this.distance_code n = this.copy_length if (distance > max_distance) or (distance == 0) { break.outer } dst_i = this.pos as base.u64 src_i = ((this.pos ~mod- distance) & (this.window_size ~mod- 1)) as base.u64 if ((dst_i + (n as base.u64)) >= (this.rb_size as base.u64)) or ((src_i + (n as base.u64)) > (this.window_size as base.u64)) or ((this.window_size as base.u64) > args.workbuf.length()) { break.outer } this.max_distance = max_distance this.dist_rb[this.dist_rb_idx & 3] = distance this.dist_rb_idx ~mod+= 1 this.mb_remaining ~mod-= n // Copy in chunks of at most distance bytes, like process_commands. k64 = 0 if (n <= 16) and (distance >= 16) and ((dst_i ~mod+ 16) <= (this.rb_size as base.u64)) and ((src_i ~mod+ 16) <= (this.window_size as base.u64)) { // Like the C code, copy 16 bytes, overwriting up to 16 - n bytes // after the copy's end. Those bytes are more than the maximum // backward distance (BROTLI_WINDOW_GAP is 16) away from any later // position, so they are never read before being rewritten. copied16 = this.copy16!(workbuf: args.workbuf, d: dst_i, s: src_i) if copied16 { k64 = n as base.u64 } } while k64 < (n as base.u64) { n64 = (n as base.u64) ~mod- k64 n64 = n64.min(no_more_than: distance as base.u64) dlo = dst_i ~mod+ k64 dhi = dlo ~mod+ n64 slo = src_i ~mod+ k64 shi = slo ~mod+ n64 if (n64 == 0) or (dlo > dhi) or (dhi > args.workbuf.length()) or (slo > shi) or (shi > args.workbuf.length()) { break } args.workbuf[dlo .. dhi].copy_from_slice!(s: args.workbuf[slo .. shi]) k64 ~mod+= n64 } this.pos ~mod+= (k64 & 0xFFFF_FFFF) as base.u32 n ~mod-= (k64 & 0xFFFF_FFFF) as base.u32 // n == 0, unless the (unreachable) break above was taken. This.pos // stays below this.rb_size, so there is no ring buffer event. while n > 0 { this.put_byte!(workbuf: args.workbuf, b: this.get_byte(workbuf: args.workbuf, distance: distance)) n -= 1 } this.cmd_state = 0 if (this.mb_remaining == 0) or (this.mb_remaining >= 0x8000_0000) { this.cmd_state = 4 break.outer } }.outer // Give back the whole bytes left in the bit buffer. while n_bits >= 8 { if not args.src.can_undo_byte() { return "#internal error: inconsistent bit reader" } args.src.undo_byte!() n_bits -= 8 } this.bits = ((bits & (((1 as base.u64) << n_bits) - 1)) & 0xFFFF_FFFF) as base.u32 this.n_bits = n_bits return ret } // update_dist_htree_index sets this.dist_htree_index from the distance // context map. Mirrors part of ReadCommandInternal and // DecodeDistanceBlockSwitch in decode.c. pri func decoder.update_dist_htree_index!() { this.dist_htree_index = this.context_maps[ DIST_CONTEXT_MAP_BASE + this.dist_context_map_slice + this.distance_context] as base.u32 } // Mirrors ReadDistanceInternal in decode.c. pri func decoder.read_distance?(src: base.io_reader) { var code : base.u32 var fr : base.u32 var nbits : base.u32[..= 32] fr = this.read_symbol_fast!(src: args.src, hoff: DIST_HUFFS_BASE + (this.dist_htree_index * DIST_HUFFS_STRIDE)) if fr <> 0 { this.read_symbol?(src: args.src, hoff: DIST_HUFFS_BASE + (this.dist_htree_index * DIST_HUFFS_STRIDE)) } code = this.symbol this.block_length[2] ~mod-= 1 // Convert the distance code to the actual distance by possibly looking up // past distances from the this.dist_rb. this.distance_context = 0 if code < 16 { this.take_distance_from_ring_buffer!(code: code) return ok } if (code >= this.distance_alphabet_size) or (code >= 1128) { return "#internal error: inconsistent Huffman table" } // The C code uses BrotliSafeReadBits32, as large-window brotli can have // more than 24 extra bits. nbits = this.dist_extra_bits[code].min(no_more_than: 32) as base.u32 fr = 1 if nbits <= 24 { fr = this.read_bits_fast!(src: args.src, n: nbits) } if fr <> 0 { this.read_bits32?(src: args.src, n: nbits) } if code >= 1128 { return "#internal error: inconsistent Huffman table" } // The C code calculates this with brotli_reg_t (64-bit) arithmetic and // then casts to int. BrotliCalculateDistanceCodeLimit means that the // result is less than BROTLI_MAX_ALLOWED_DISTANCE. this.distance_code = (((this.dist_offset[code] as base.u64) ~mod+ ((this.bits_value as base.u64) ~mod<< this.distance_postfix_bits)) & 0xFFFF_FFFF) as base.u32 } // Mirrors TakeDistanceFromRingBuffer in decode.c. pri func decoder.take_distance_from_ring_buffer!(code: base.u32[..= 15]) { var index_delta : base.u32[..= 3] var nibble : base.u32[..= 5] var v : base.u32 if args.code <= 3 { // Compensate double distance-ring-buffer roll for dictionary items. this.distance_context = 0 if args.code == 0 { this.distance_context = 1 } this.distance_code = this.dist_rb[((this.dist_rb_idx ~mod+ 3) ~mod- args.code) & 3] this.dist_rb_idx ~mod-= this.distance_context return nothing } index_delta = 3 if args.code < 10 { nibble = args.code - 4 } else { nibble = args.code - 10 index_delta = 2 } // Unpack one of six 4-bit values, and subtract 3. v = this.dist_rb[(this.dist_rb_idx ~mod+ index_delta) & 3] ~mod+ (((0x60_5142 as base.u32) >> (4 * nibble)) & 15) if v <= 3 { // A huge distance will cause a "#bad distance" soon. this.distance_code = 0x7FFF_FFFF } else { this.distance_code = v - 3 } } // copy16 copies the 16 bytes at workbuf[s ..] to workbuf[d ..], if both are // in bounds (and returns whether it did). The two ranges must not overlap. pri func decoder.copy16!(workbuf: slice base.u8, d: base.u64, s: base.u64) base.bool { var lo : base.u64 var hi : base.u64 var q : slice base.u8 var r : slice base.u8 if (args.s > args.workbuf.length()) or (args.d > args.workbuf.length()) { return false } q = args.workbuf[args.s ..] if q.length() >= 16 { lo = q.peek_u64le() q = q[8 ..] if q.length() >= 8 { hi = q.peek_u64le() q = args.workbuf[args.d ..] if q.length() >= 16 { r = q[8 ..] q.poke_u64le!(a: lo) if r.length() >= 8 { r.poke_u64le!(a: hi) return true } } } } return false }