std/bzip2/decode_block_slow.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_block_slow?(src: base.io_reader) {
	var which      : base.u8[..= 5]
	var c          : base.u8
	var child      : base.u16
	var child_ff   : base.u32[..= 255]
	var i          : base.u32
	var j          : base.u32
	var ticks      : base.u32[..= 50]
	var section    : base.u32
	var bs         : base.u32[..= 1_048575]  // 1_048575 = ((1 << 20) - 1)
	var output     : base.u32[..= 255]
	var node_index : base.u32[..= 1023]
	var run_shift  : base.u32[..= 23]
	var run        : base.u32[..= 16_777216]  // 16_777216 = (2 << 23)
	var mtft0      : base.u32[..= 255]

	which = CLAMP_TO_5[this.huffman_selectors[0] & 7]
	section = 1

	// Initialize the MTFT state.
	i = 0
	j = 0
	while i < 256 {
		if this.presence[i] <> 0 {
			this.mtft[j & 0xFF] = i as base.u8
			j ~mod+= 1
		}
		i += 1
	} endwhile

	i = 0
	while i < 256 {
		this.letter_counts[i] = 0
		i += 1
	} endwhile

	// Apply the Huffman trees.
	ticks = 50
	while.outer true {
		if ticks > 0 {
			ticks -= 1
		} else {
			ticks = 49
			which = CLAMP_TO_5[this.huffman_selectors[section & 32767] & 7]
			section ~mod+= 1
		}

		node_index = 0
		while true {
			if this.n_bits <= 0 {
				c = args.src.read_u8?()
				this.bits = (c as base.u32) << 24
				this.n_bits = 8
				assert this.n_bits > 0
			}
			child = this.huffman_trees[which][node_index][this.bits >> 31]
			this.bits ~mod<<= 1
			this.n_bits -= 1

			if child < 1024 {  // Branch node.
				node_index = child as base.u32
				continue

			} else if child < 1280 {  // 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[bs] = output
				if bs >= this.max_incl_block_size {
					return "#bad block length"
				}
				assert bs < 900000 via "a < b: a < c; c <= b"(c: this.max_incl_block_size)
				bs += 1
				run_shift = 0
				break

			} else if child > 1281 {  // EOB symbol.
				break.outer
			}

			// RUNA or RUNB symbol.
			if run_shift >= 23 {
				return "#bad block length"
			}
			run = ((child - 1279) as base.u32) << run_shift
			run_shift += 1
			i = bs
			j = run + bs
			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)
			bs = 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
			break
		} endwhile
	} endwhile.outer

	if bs > this.max_incl_block_size {
		return "#bad block length"
	}
	assert bs <= 900000 via "a <= b: a <= c; c <= b"(c: this.max_incl_block_size)
	this.block_size = bs
}