Factor out std/bzip2/decode_block_slow.wuffs
diff --git a/release/c/wuffs-unsupported-snapshot.c b/release/c/wuffs-unsupported-snapshot.c
index b42735c..c31dcc1 100644
--- a/release/c/wuffs-unsupported-snapshot.c
+++ b/release/c/wuffs-unsupported-snapshot.c
@@ -6944,10 +6944,10 @@
uint32_t f_num_sections;
uint32_t f_code_lengths_bitmask;
+ uint32_t p_decode_block_slow[1];
uint32_t p_transform_io[1];
uint32_t p_prepare_block[1];
uint32_t p_read_code_lengths[1];
- uint32_t p_execute_block[1];
uint32_t p_flush_block[1];
} private_impl;
@@ -6961,6 +6961,14 @@
uint32_t f_bwt[1048576];
struct {
+ uint8_t v_which;
+ uint32_t v_ticks;
+ uint32_t v_section;
+ uint32_t v_bs;
+ uint32_t v_node_index;
+ uint32_t v_run_shift;
+ } s_decode_block_slow[1];
+ struct {
uint32_t v_i;
uint64_t v_tag;
uint32_t v_final_checksum_want;
@@ -6974,14 +6982,6 @@
uint32_t v_code_length;
} s_read_code_lengths[1];
struct {
- uint8_t v_which;
- uint32_t v_ticks;
- uint32_t v_section;
- uint32_t v_bs;
- uint32_t v_node_index;
- uint32_t v_run_shift;
- } s_execute_block[1];
- struct {
uint32_t v_i;
uint32_t v_n;
uint32_t v_repeat_count;
@@ -24913,6 +24913,11 @@
// ---------------- Private Function Prototypes
static wuffs_base__status
+wuffs_bzip2__decoder__decode_block_slow(
+ wuffs_bzip2__decoder* self,
+ wuffs_base__io_buffer* a_src);
+
+static wuffs_base__status
wuffs_bzip2__decoder__prepare_block(
wuffs_bzip2__decoder* self,
wuffs_base__io_buffer* a_src);
@@ -24927,11 +24932,6 @@
wuffs_bzip2__decoder* self,
uint32_t a_which);
-static wuffs_base__status
-wuffs_bzip2__decoder__execute_block(
- wuffs_bzip2__decoder* self,
- wuffs_base__io_buffer* a_src);
-
static wuffs_base__empty_struct
wuffs_bzip2__decoder__invert_bwt(
wuffs_bzip2__decoder* self);
@@ -25026,6 +25026,171 @@
// ---------------- Function Implementations
+// -------- func bzip2.decoder.decode_block_slow
+
+static wuffs_base__status
+wuffs_bzip2__decoder__decode_block_slow(
+ wuffs_bzip2__decoder* self,
+ wuffs_base__io_buffer* a_src) {
+ wuffs_base__status status = wuffs_base__make_status(NULL);
+
+ uint8_t v_which = 0;
+ uint8_t v_c = 0;
+ uint16_t v_child = 0;
+ uint32_t v_child_ff = 0;
+ uint32_t v_i = 0;
+ uint32_t v_j = 0;
+ uint32_t v_ticks = 0;
+ uint32_t v_section = 0;
+ uint32_t v_bs = 0;
+ uint32_t v_output = 0;
+ uint32_t v_node_index = 0;
+ uint32_t v_run_shift = 0;
+ uint32_t v_run = 0;
+ uint32_t v_mtft0 = 0;
+
+ const uint8_t* iop_a_src = NULL;
+ const uint8_t* io0_a_src WUFFS_BASE__POTENTIALLY_UNUSED = NULL;
+ const uint8_t* io1_a_src WUFFS_BASE__POTENTIALLY_UNUSED = NULL;
+ const uint8_t* io2_a_src WUFFS_BASE__POTENTIALLY_UNUSED = NULL;
+ if (a_src) {
+ io0_a_src = a_src->data.ptr;
+ io1_a_src = io0_a_src + a_src->meta.ri;
+ iop_a_src = io1_a_src;
+ io2_a_src = io0_a_src + a_src->meta.wi;
+ }
+
+ uint32_t coro_susp_point = self->private_impl.p_decode_block_slow[0];
+ if (coro_susp_point) {
+ v_which = self->private_data.s_decode_block_slow[0].v_which;
+ v_ticks = self->private_data.s_decode_block_slow[0].v_ticks;
+ v_section = self->private_data.s_decode_block_slow[0].v_section;
+ v_bs = self->private_data.s_decode_block_slow[0].v_bs;
+ v_node_index = self->private_data.s_decode_block_slow[0].v_node_index;
+ v_run_shift = self->private_data.s_decode_block_slow[0].v_run_shift;
+ }
+ switch (coro_susp_point) {
+ WUFFS_BASE__COROUTINE_SUSPENSION_POINT_0;
+
+ v_which = WUFFS_BZIP2__CLAMP_TO_5[(self->private_data.f_huffman_selectors[0] & 7)];
+ v_section = 1;
+ v_i = 0;
+ v_j = 0;
+ while (v_i < 256) {
+ if (self->private_data.f_presence[v_i] != 0) {
+ self->private_data.f_mtft[(v_j & 255)] = ((uint8_t)(v_i));
+ v_j += 1;
+ }
+ v_i += 1;
+ }
+ v_i = 0;
+ while (v_i < 256) {
+ self->private_data.f_letter_counts[v_i] = 0;
+ v_i += 1;
+ }
+ v_ticks = 50;
+ while (true) {
+ if (v_ticks > 0) {
+ v_ticks -= 1;
+ } else {
+ v_ticks = 49;
+ v_which = WUFFS_BZIP2__CLAMP_TO_5[(self->private_data.f_huffman_selectors[(v_section & 32767)] & 7)];
+ v_section += 1;
+ }
+ v_node_index = 0;
+ label__0__continue:;
+ while (true) {
+ if (self->private_impl.f_n_bits <= 0) {
+ {
+ WUFFS_BASE__COROUTINE_SUSPENSION_POINT(1);
+ if (WUFFS_BASE__UNLIKELY(iop_a_src == io2_a_src)) {
+ status = wuffs_base__make_status(wuffs_base__suspension__short_read);
+ goto suspend;
+ }
+ uint8_t t_0 = *iop_a_src++;
+ v_c = t_0;
+ }
+ self->private_impl.f_bits = (((uint32_t)(v_c)) << 24);
+ self->private_impl.f_n_bits = 8;
+ }
+ v_child = self->private_data.f_huffman_trees[v_which][v_node_index][(self->private_impl.f_bits >> 31)];
+ self->private_impl.f_bits <<= 1;
+ self->private_impl.f_n_bits -= 1;
+ if (v_child < 1024) {
+ v_node_index = ((uint32_t)(v_child));
+ goto label__0__continue;
+ } else if (v_child < 1280) {
+ v_child_ff = ((uint32_t)((v_child & 255)));
+ v_output = ((uint32_t)(self->private_data.f_mtft[v_child_ff]));
+ wuffs_base__slice_u8__copy_from_slice(wuffs_base__make_slice_u8_ij(self->private_data.f_mtft, 1, (1 + v_child_ff)), wuffs_base__make_slice_u8(self->private_data.f_mtft, v_child_ff));
+ self->private_data.f_mtft[0] = ((uint8_t)(v_output));
+ self->private_data.f_letter_counts[v_output] += 1;
+ self->private_data.f_bwt[v_bs] = v_output;
+ if (v_bs >= self->private_impl.f_max_incl_block_size) {
+ status = wuffs_base__make_status(wuffs_bzip2__error__bad_block_length);
+ goto exit;
+ }
+ v_bs += 1;
+ v_run_shift = 0;
+ goto label__0__break;
+ } else if (v_child > 1281) {
+ goto label__outer__break;
+ }
+ if (v_run_shift >= 23) {
+ status = wuffs_base__make_status(wuffs_bzip2__error__bad_block_length);
+ goto exit;
+ }
+ v_run = (((uint32_t)((v_child - 1279))) << v_run_shift);
+ v_run_shift += 1;
+ v_i = v_bs;
+ v_j = (v_run + v_bs);
+ if (v_j > self->private_impl.f_max_incl_block_size) {
+ status = wuffs_base__make_status(wuffs_bzip2__error__bad_block_length);
+ goto exit;
+ }
+ v_bs = v_j;
+ v_mtft0 = ((uint32_t)(self->private_data.f_mtft[0]));
+ self->private_data.f_letter_counts[v_mtft0] += v_run;
+ while (v_i < v_j) {
+ self->private_data.f_bwt[v_i] = v_mtft0;
+ v_i += 1;
+ }
+ goto label__0__break;
+ }
+ label__0__break:;
+ }
+ label__outer__break:;
+ if (v_bs > self->private_impl.f_max_incl_block_size) {
+ status = wuffs_base__make_status(wuffs_bzip2__error__bad_block_length);
+ goto exit;
+ }
+ self->private_impl.f_block_size = v_bs;
+
+ goto ok;
+ ok:
+ self->private_impl.p_decode_block_slow[0] = 0;
+ goto exit;
+ }
+
+ goto suspend;
+ suspend:
+ self->private_impl.p_decode_block_slow[0] = wuffs_base__status__is_suspension(&status) ? coro_susp_point : 0;
+ self->private_data.s_decode_block_slow[0].v_which = v_which;
+ self->private_data.s_decode_block_slow[0].v_ticks = v_ticks;
+ self->private_data.s_decode_block_slow[0].v_section = v_section;
+ self->private_data.s_decode_block_slow[0].v_bs = v_bs;
+ self->private_data.s_decode_block_slow[0].v_node_index = v_node_index;
+ self->private_data.s_decode_block_slow[0].v_run_shift = v_run_shift;
+
+ goto exit;
+ exit:
+ if (a_src) {
+ a_src->meta.ri = ((size_t)(iop_a_src - a_src->data.ptr));
+ }
+
+ return status;
+}
+
// -------- func bzip2.decoder.set_quirk_enabled
WUFFS_BASE__MAYBE_STATIC wuffs_base__empty_struct
@@ -25203,7 +25368,7 @@
a_src->meta.ri = ((size_t)(iop_a_src - a_src->data.ptr));
}
WUFFS_BASE__COROUTINE_SUSPENSION_POINT(7);
- status = wuffs_bzip2__decoder__execute_block(self, a_src);
+ status = wuffs_bzip2__decoder__decode_block_slow(self, a_src);
if (a_src) {
iop_a_src = a_src->data.ptr + a_src->meta.ri;
}
@@ -25791,171 +25956,6 @@
return wuffs_base__make_status(NULL);
}
-// -------- func bzip2.decoder.execute_block
-
-static wuffs_base__status
-wuffs_bzip2__decoder__execute_block(
- wuffs_bzip2__decoder* self,
- wuffs_base__io_buffer* a_src) {
- wuffs_base__status status = wuffs_base__make_status(NULL);
-
- uint8_t v_which = 0;
- uint8_t v_c = 0;
- uint16_t v_child = 0;
- uint32_t v_child_ff = 0;
- uint32_t v_i = 0;
- uint32_t v_j = 0;
- uint32_t v_ticks = 0;
- uint32_t v_section = 0;
- uint32_t v_bs = 0;
- uint32_t v_output = 0;
- uint32_t v_node_index = 0;
- uint32_t v_run_shift = 0;
- uint32_t v_run = 0;
- uint32_t v_mtft0 = 0;
-
- const uint8_t* iop_a_src = NULL;
- const uint8_t* io0_a_src WUFFS_BASE__POTENTIALLY_UNUSED = NULL;
- const uint8_t* io1_a_src WUFFS_BASE__POTENTIALLY_UNUSED = NULL;
- const uint8_t* io2_a_src WUFFS_BASE__POTENTIALLY_UNUSED = NULL;
- if (a_src) {
- io0_a_src = a_src->data.ptr;
- io1_a_src = io0_a_src + a_src->meta.ri;
- iop_a_src = io1_a_src;
- io2_a_src = io0_a_src + a_src->meta.wi;
- }
-
- uint32_t coro_susp_point = self->private_impl.p_execute_block[0];
- if (coro_susp_point) {
- v_which = self->private_data.s_execute_block[0].v_which;
- v_ticks = self->private_data.s_execute_block[0].v_ticks;
- v_section = self->private_data.s_execute_block[0].v_section;
- v_bs = self->private_data.s_execute_block[0].v_bs;
- v_node_index = self->private_data.s_execute_block[0].v_node_index;
- v_run_shift = self->private_data.s_execute_block[0].v_run_shift;
- }
- switch (coro_susp_point) {
- WUFFS_BASE__COROUTINE_SUSPENSION_POINT_0;
-
- v_which = WUFFS_BZIP2__CLAMP_TO_5[(self->private_data.f_huffman_selectors[0] & 7)];
- v_section = 1;
- v_i = 0;
- v_j = 0;
- while (v_i < 256) {
- if (self->private_data.f_presence[v_i] != 0) {
- self->private_data.f_mtft[(v_j & 255)] = ((uint8_t)(v_i));
- v_j += 1;
- }
- v_i += 1;
- }
- v_i = 0;
- while (v_i < 256) {
- self->private_data.f_letter_counts[v_i] = 0;
- v_i += 1;
- }
- v_ticks = 50;
- while (true) {
- if (v_ticks > 0) {
- v_ticks -= 1;
- } else {
- v_ticks = 49;
- v_which = WUFFS_BZIP2__CLAMP_TO_5[(self->private_data.f_huffman_selectors[(v_section & 32767)] & 7)];
- v_section += 1;
- }
- v_node_index = 0;
- label__0__continue:;
- while (true) {
- if (self->private_impl.f_n_bits <= 0) {
- {
- WUFFS_BASE__COROUTINE_SUSPENSION_POINT(1);
- if (WUFFS_BASE__UNLIKELY(iop_a_src == io2_a_src)) {
- status = wuffs_base__make_status(wuffs_base__suspension__short_read);
- goto suspend;
- }
- uint8_t t_0 = *iop_a_src++;
- v_c = t_0;
- }
- self->private_impl.f_bits = (((uint32_t)(v_c)) << 24);
- self->private_impl.f_n_bits = 8;
- }
- v_child = self->private_data.f_huffman_trees[v_which][v_node_index][(self->private_impl.f_bits >> 31)];
- self->private_impl.f_bits <<= 1;
- self->private_impl.f_n_bits -= 1;
- if (v_child < 1024) {
- v_node_index = ((uint32_t)(v_child));
- goto label__0__continue;
- } else if (v_child < 1280) {
- v_child_ff = ((uint32_t)((v_child & 255)));
- v_output = ((uint32_t)(self->private_data.f_mtft[v_child_ff]));
- wuffs_base__slice_u8__copy_from_slice(wuffs_base__make_slice_u8_ij(self->private_data.f_mtft, 1, (1 + v_child_ff)), wuffs_base__make_slice_u8(self->private_data.f_mtft, v_child_ff));
- self->private_data.f_mtft[0] = ((uint8_t)(v_output));
- self->private_data.f_letter_counts[v_output] += 1;
- self->private_data.f_bwt[v_bs] = v_output;
- if (v_bs >= self->private_impl.f_max_incl_block_size) {
- status = wuffs_base__make_status(wuffs_bzip2__error__bad_block_length);
- goto exit;
- }
- v_bs += 1;
- v_run_shift = 0;
- goto label__0__break;
- } else if (v_child > 1281) {
- goto label__outer__break;
- }
- if (v_run_shift >= 23) {
- status = wuffs_base__make_status(wuffs_bzip2__error__bad_block_length);
- goto exit;
- }
- v_run = (((uint32_t)((v_child - 1279))) << v_run_shift);
- v_run_shift += 1;
- v_i = v_bs;
- v_j = (v_run + v_bs);
- if (v_j > self->private_impl.f_max_incl_block_size) {
- status = wuffs_base__make_status(wuffs_bzip2__error__bad_block_length);
- goto exit;
- }
- v_bs = v_j;
- v_mtft0 = ((uint32_t)(self->private_data.f_mtft[0]));
- self->private_data.f_letter_counts[v_mtft0] += v_run;
- while (v_i < v_j) {
- self->private_data.f_bwt[v_i] = v_mtft0;
- v_i += 1;
- }
- goto label__0__break;
- }
- label__0__break:;
- }
- label__outer__break:;
- if (v_bs > self->private_impl.f_max_incl_block_size) {
- status = wuffs_base__make_status(wuffs_bzip2__error__bad_block_length);
- goto exit;
- }
- self->private_impl.f_block_size = v_bs;
-
- goto ok;
- ok:
- self->private_impl.p_execute_block[0] = 0;
- goto exit;
- }
-
- goto suspend;
- suspend:
- self->private_impl.p_execute_block[0] = wuffs_base__status__is_suspension(&status) ? coro_susp_point : 0;
- self->private_data.s_execute_block[0].v_which = v_which;
- self->private_data.s_execute_block[0].v_ticks = v_ticks;
- self->private_data.s_execute_block[0].v_section = v_section;
- self->private_data.s_execute_block[0].v_bs = v_bs;
- self->private_data.s_execute_block[0].v_node_index = v_node_index;
- self->private_data.s_execute_block[0].v_run_shift = v_run_shift;
-
- goto exit;
- exit:
- if (a_src) {
- a_src->meta.ri = ((size_t)(iop_a_src - a_src->data.ptr));
- }
-
- return status;
-}
-
// -------- func bzip2.decoder.invert_bwt
static wuffs_base__empty_struct
diff --git a/std/bzip2/decode_block_slow.wuffs b/std/bzip2/decode_block_slow.wuffs
new file mode 100644
index 0000000..fe65baa
--- /dev/null
+++ b/std/bzip2/decode_block_slow.wuffs
@@ -0,0 +1,132 @@
+// 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
+}
diff --git a/std/bzip2/decode_bzip2.wuffs b/std/bzip2/decode_bzip2.wuffs
index 8052827..6f86876 100644
--- a/std/bzip2/decode_bzip2.wuffs
+++ b/std/bzip2/decode_bzip2.wuffs
@@ -27,6 +27,8 @@
pub const DECODER_WORKBUF_LEN_MAX_INCL_WORST_CASE : base.u64 = 0
+pri const CLAMP_TO_5 : array[8] base.u8[..= 5] = [0, 1, 2, 3, 4, 5, 5, 5]
+
pub struct decoder? implements base.io_transformer(
bits : base.u32,
n_bits : base.u32[..= 31],
@@ -136,7 +138,7 @@
}
this.prepare_block?(src: args.src)
- this.execute_block?(src: args.src)
+ this.decode_block_slow?(src: args.src)
this.invert_bwt!()
this.flush_block?(dst: args.dst)
} endwhile
@@ -588,127 +590,6 @@
return ok
}
-pri const CLAMP_TO_5 : array[8] base.u8[..= 5] = [0, 1, 2, 3, 4, 5, 5, 5]
-
-pri func decoder.execute_block?(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
-}
-
// invert_bwt performs "two passes over the data, and one pass over the
// alphabet", per the BWT technical report, except that the first data pass
// (accumulating this.letter_counts) is integrated into execute_block.
