std/bzip2/decode_huffman_fast.wuffs

// Copyright 2022 The Wuffs Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

pri func decoder.decode_huffman_fast!(src: base.io_reader) base.status {
	var bits       : base.u32
	var n_bits     : base.u32[..= 31]
	var block_size : base.u32[..= 900000]
	var which      : base.u8[..= 5]
	var ticks      : base.u32[..= 50]
	var section    : base.u32
	var run_shift  : base.u32[..= 23]

	var table_entry : base.u16
	var child       : base.u16
	var child_ff    : base.u32[..= 255]
	var i           : base.u32
	var j           : base.u32
	var output      : base.u32[..= 255]
	var run         : base.u32[..= 12_582912]  // 12_582912 = (3 << 22)
	var mtft0       : base.u32[..= 255]

	bits = this.bits
	n_bits = this.n_bits
	block_size = this.block_size
	which = this.decode_huffman_which
	ticks = this.decode_huffman_ticks
	section = this.decode_huffman_section
	run_shift = this.decode_huffman_run_shift

	// Apply the Huffman trees.
	while.outer args.src.length() >= 4 {
		if ticks > 0 {
			ticks -= 1
		} else {
			ticks = 49
			section ~mod+= 1
			if section >= this.num_sections {
				return "#bad number of sections"
			}
			which = CLAMP_TO_5[this.huffman_selectors[section & 32767] & 7]
		}

		bits |= args.src.peek_u32be() >> n_bits
		args.src.skip_u32_fast!(actual: (31 - n_bits) >> 3, worst_case: 4)
		n_bits |= 24

		table_entry = this.huffman_tables[which][bits >> 24]
		bits ~mod<<= table_entry >> 12
		n_bits -= (table_entry >> 12) as base.u32
		child = table_entry & 0x3FF
		while child < 257 {
			child = this.huffman_trees[which][child][bits >> 31]
			bits ~mod<<= 1
			if n_bits <= 0 {
				return "#internal error: inconsistent Huffman decoder state"
			}
			n_bits -= 1
		} endwhile

		if child < 0x300 {  // mNN symbol.
			// Move to front.
			child_ff = (child & 0xFF) as base.u32
			output = this.mtft[child_ff] as base.u32
			this.mtft[1 .. 1 + child_ff].copy_from_slice!(
				s: this.mtft[.. child_ff])
			this.mtft[0] = output as base.u8

			this.letter_counts[output] ~mod+= 1
			this.bwt[block_size] = output
			if block_size >= this.max_incl_block_size {
				return "#bad block length"
			}
			assert block_size < 900000 via "a < b: a < c; c <= b"(c: this.max_incl_block_size)
			block_size += 1
			run_shift = 0
			continue.outer
		} else if child == 0x300 {  // EOB symbol.
			this.decode_huffman_finished = true
			break.outer
		}

		// RUNA or RUNB symbol.
		if run_shift >= 23 {
			return "#bad block length"
		}
		run = ((child as base.u32) & 3) << run_shift
		run_shift += 1
		i = block_size
		j = run + block_size
		if j > this.max_incl_block_size {
			return "#bad block length"
		}
		assert j <= 900000 via "a <= b: a <= c; c <= b"(c: this.max_incl_block_size)
		block_size = j

		mtft0 = this.mtft[0] as base.u32
		this.letter_counts[mtft0] ~mod+= run
		while i < j,
			pre j <= 900000,
		{
			assert i < 900000 via "a < b: a < c; c <= b"(c: j)
			this.bwt[i] = mtft0
			i += 1
		} endwhile
	} endwhile.outer

	this.bits = bits
	this.n_bits = n_bits
	this.block_size = block_size
	this.decode_huffman_which = which
	this.decode_huffman_ticks = ticks
	this.decode_huffman_section = section
	this.decode_huffman_run_shift = run_shift

	return ok
}