module bzip2

const bzip2_block_magic = u64(0x314159265359)
const bzip2_eos_magic = u64(0x177245385090)
const bzip2_runa = 0
const bzip2_runb = 1
const bzip2_max_groups = 6
const bzip2_max_alpha = 258
const bzip2_group_size = 50
const bzip2_max_code_len = 20
const bzip2_max_selectors = 18002

// vfmt off
const bzip2_crc32_table = [..]u32[
    0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,
    0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61, 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
    0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9, 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
    0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd,
    0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039, 0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,
    0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
    0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49, 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
    0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d,
    0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
    0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16, 0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,
    0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde, 0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02,
    0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
    0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692,
    0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6, 0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a,
    0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e, 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
    0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a,
    0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637, 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
    0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f, 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
    0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b,
    0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff, 0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,
    0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
    0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
    0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b,
    0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
    0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640, 0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,
    0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8, 0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24,
    0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
    0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654,
    0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0, 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c,
    0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18, 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
    0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c,
    0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
]
// vfmt on

@[params]
pub struct CompressParams {
pub:
    block_size int = 9 // Valid range is 1..9 (100k to 900k block size).
}

@[params]
pub struct DecompressParams {
pub:
    verify_crc bool = true
}

// compress compresses `src` into a bzip2 byte stream.
pub fn compress(src []u8, params CompressParams) ![]u8 {
    if params.block_size < 1 || params.block_size > 9 {
        return error('bzip2: block_size must be in 1..9')
    }
    mut w := BitWriter{
        out: []u8{}
    }

    w.write_byte(`B`)
    w.write_byte(`Z`)
    w.write_byte(`h`)
    w.write_byte(u8(`0`) + u8(params.block_size))

    max_block := params.block_size * 100000
    mut stream_crc := u32(0)
    if src.len > 0 {
        mut pos := 0
        for pos < src.len {
            end := find_rle1_block_end(src, pos, max_block)
            chunk := src[pos..end]
            block := encode_block(chunk)!
            w.write_bits(48, bzip2_block_magic)
            w.write_bits(32, u64(block.block_crc))
            w.write_bit(0) // randomized flag; unsupported legacy mode
            w.write_bits(24, u64(block.orig_ptr))
            write_in_use_map(mut w, block.in_use)
            w.write_bits(3, u64(block.n_groups))
            w.write_bits(15, u64(block.selectors.len))
            for sel in block.selector_mtf {
                for _ in 0 .. sel {
                    w.write_bit(1)
                }
                w.write_bit(0)
            }
            for g in 0 .. block.n_groups {
                write_code_lengths(mut w, block.code_lengths[g], block.alpha_size)
            }
            mut grp_idx := 0
            mut grp_pos := 0
            for sym in block.symbols {
                if grp_pos == 0 {
                    grp_idx = block.selectors[grp_idx]
                }
                code := block.codes[grp_idx][sym]
                len := block.code_lengths[grp_idx][sym]
                w.write_bits(len, u64(code))
                grp_pos++
                if grp_pos == bzip2_group_size {
                    grp_pos = 0
                    grp_idx++
                }
            }
            stream_crc = rotate_left_1(stream_crc) ^ block.block_crc
            pos = end
        }
    }
    w.write_bits(48, bzip2_eos_magic)
    w.write_bits(32, u64(stream_crc))
    return w.finish()
}

// decompress decompresses a bzip2 byte stream.
pub fn decompress(src []u8, params DecompressParams) ![]u8 {
    mut r := BitReader{
        data: src
    }
    if r.read_byte()! != `B` || r.read_byte()! != `Z` || r.read_byte()! != `h` {
        return error('bzip2: invalid header')
    }
    lvl := r.read_byte()!
    if lvl < `1` || lvl > `9` {
        return error('bzip2: invalid block size marker')
    }
    block_limit := int(lvl - `0`) * 100000
    mut out := []u8{}
    mut stream_crc := u32(0)
    for {
        magic := r.read_bits(48)!
        if magic == bzip2_eos_magic {
            stored_stream_crc := u32(r.read_bits(32)!)
            if params.verify_crc && stored_stream_crc != stream_crc {
                return error('bzip2: stream crc mismatch')
            }
            if !r.is_aligned_to_byte_zero_padding() {
                return error('bzip2: trailing non-zero bits')
            }
            return out
        }
        if magic != bzip2_block_magic {
            return error('bzip2: invalid block magic')
        }
        block_crc := u32(r.read_bits(32)!)
        randomized := r.read_bit()!
        if randomized != 0 {
            return error('bzip2: randomized blocks are not supported')
        }
        orig_ptr := int(r.read_bits(24)!)
        in_use := read_in_use_map(mut r)!
        mut seq_to_unseq := []u8{}
        for i, used in in_use {
            if used {
                seq_to_unseq << u8(i)
            }
        }
        n_in_use := seq_to_unseq.len
        alpha_size := n_in_use + 2
        if alpha_size < 2 || alpha_size > bzip2_max_alpha {
            return error('bzip2: invalid alphabet size')
        }
        n_groups := int(r.read_bits(3)!)
        if n_groups < 2 || n_groups > bzip2_max_groups {
            return error('bzip2: invalid huffman group count')
        }
        n_selectors := int(r.read_bits(15)!)
        if n_selectors < 1 || n_selectors > bzip2_max_selectors {
            return error('bzip2: invalid selector count')
        }
        mut selectors_mtf := []int{len: n_selectors}
        for i in 0 .. n_selectors {
            mut c := 0
            for {
                b := r.read_bit()!
                if b == 0 {
                    break
                }
                c++
                if c >= n_groups {
                    return error('bzip2: invalid selector mtf value')
                }
            }
            selectors_mtf[i] = c
        }
        selectors := decode_selector_mtf(selectors_mtf, n_groups)!

        mut code_lengths := [][]int{len: n_groups, init: []int{len: alpha_size}}
        for g in 0 .. n_groups {
            mut curr := int(r.read_bits(5)!)
            if curr < 1 || curr > bzip2_max_code_len {
                return error('bzip2: invalid initial huffman code length')
            }
            for i in 0 .. alpha_size {
                for {
                    flag := r.read_bit()!
                    if flag == 0 {
                        break
                    }
                    up_down := r.read_bit()!
                    if up_down == 0 {
                        curr++
                    } else {
                        curr--
                    }
                    if curr < 1 || curr > bzip2_max_code_len {
                        return error('bzip2: invalid huffman code length delta')
                    }
                }
                code_lengths[g][i] = curr
            }
        }

        mut tables := []DecodeTable{len: n_groups}
        for g in 0 .. n_groups {
            tables[g] = build_decode_table(code_lengths[g], alpha_size)!
        }

        eob := n_in_use + 1
        mut selector_index := 0
        mut group_pos := 0
        mut mtf := []int{len: n_in_use}
        for i in 0 .. n_in_use {
            mtf[i] = i
        }
        mut decoded_syms := []int{}
        mut next_sym := 0
        for {
            if group_pos == 0 {
                if selector_index >= selectors.len {
                    return error('bzip2: selectors exhausted')
                }
            }
            grp := selectors[selector_index]
            next_sym = tables[grp].decode(mut r)!
            group_pos++
            if group_pos == bzip2_group_size {
                group_pos = 0
                selector_index++
            }
            if next_sym == eob {
                break
            }
            if next_sym == bzip2_runa || next_sym == bzip2_runb {
                mut s := i64(-1)
                mut n := i64(1)
                remaining := block_limit - decoded_syms.len
                if remaining < 1 {
                    return error('bzip2: block output exceeds declared block size')
                }
                for {
                    if next_sym == bzip2_runa {
                        s += n
                    } else {
                        s += n * 2
                    }
                    if s + 1 > i64(remaining) {
                        return error('bzip2: block output exceeds declared block size')
                    }
                    n *= 2
                    if group_pos == 0 {
                        if selector_index >= selectors.len {
                            return error('bzip2: selectors exhausted in run')
                        }
                    }
                    grp2 := selectors[selector_index]
                    next_sym = tables[grp2].decode(mut r)!
                    group_pos++
                    if group_pos == bzip2_group_size {
                        group_pos = 0
                        selector_index++
                    }
                    if next_sym != bzip2_runa && next_sym != bzip2_runb {
                        break
                    }
                }
                run_len := int(s + 1)
                if run_len < 1 {
                    return error('bzip2: invalid run length')
                }
                if mtf.len == 0 {
                    return error('bzip2: invalid run with empty mtf table')
                }
                ensure_block_output_limit(decoded_syms.len, run_len, block_limit)!
                for _ in 0 .. run_len {
                    decoded_syms << mtf[0]
                }
                if next_sym == eob {
                    break
                }
            }
            if next_sym == eob {
                break
            }
            if next_sym < 2 || next_sym > eob {
                return error('bzip2: invalid symbol value')
            }
            pos := next_sym - 1
            if pos >= mtf.len {
                return error('bzip2: mtf index out of range')
            }
            sym := mtf[pos]
            move_to_front_int(mut mtf, pos)
            ensure_block_output_limit(decoded_syms.len, 1, block_limit)!
            decoded_syms << sym
        }

        mut bwt_bytes := []u8{cap: decoded_syms.len}
        for s in decoded_syms {
            if s < 0 || s >= seq_to_unseq.len {
                return error('bzip2: decoded symbol is out of sequence map range')
            }
            bwt_bytes << seq_to_unseq[s]
        }

        rle1 := inverse_bwt(bwt_bytes, orig_ptr)!
        plain := rle1_decode(rle1)!
        if params.verify_crc {
            calc := bzip2_crc32(plain)
            if calc != block_crc {
                return error('bzip2: block crc mismatch')
            }
        }
        stream_crc = rotate_left_1(stream_crc) ^ block_crc
        out << plain
    }
    return error('bzip2: unexpected end of stream')
}

struct EncodedBlock {
    block_crc    u32
    orig_ptr     int
    in_use       []bool
    alpha_size   int
    n_groups     int
    selectors    []int
    selector_mtf []int
    symbols      []int
    code_lengths [][]int
    codes        [][]u32
}

fn encode_block(src []u8) !EncodedBlock {
    block_crc := bzip2_crc32(src)
    rle1 := rle1_encode(src)
    if rle1.len == 0 {
        return error('bzip2: internal error, empty block after rle1')
    }
    bwt, orig_ptr := bwt_transform(rle1)
    mut in_use := []bool{len: 256}
    for b in bwt {
        in_use[int(b)] = true
    }
    mut seq_to_unseq := []u8{}
    for i, used in in_use {
        if used {
            seq_to_unseq << u8(i)
        }
    }
    mut unseq_to_seq := []int{len: 256, init: -1}
    for i, b in seq_to_unseq {
        unseq_to_seq[int(b)] = i
    }
    mtf_symbols, alpha_size := mtf_rle2_encode(bwt, unseq_to_seq, seq_to_unseq.len)
    if mtf_symbols.len == 0 {
        return error('bzip2: internal error, empty symbol stream')
    }
    n_groups := select_group_count(mtf_symbols.len)
    n_selectors := selector_count_from_symbol_count(mtf_symbols.len)!
    mut selectors := []int{len: n_selectors, init: 0}
    selector_mtf := encode_selector_mtf(selectors, n_groups)
    freq := symbol_freq(mtf_symbols, alpha_size)
    lens := make_huffman_lengths(freq, bzip2_max_code_len)
    codes := build_huffman_codes(lens)
    mut code_lengths := [][]int{len: n_groups}
    mut code_words := [][]u32{len: n_groups}
    for i in 0 .. n_groups {
        code_lengths[i] = lens.clone()
        code_words[i] = codes.clone()
    }
    return EncodedBlock{
        block_crc:    block_crc
        orig_ptr:     orig_ptr
        in_use:       in_use
        alpha_size:   alpha_size
        n_groups:     n_groups
        selectors:    selectors
        selector_mtf: selector_mtf
        symbols:      mtf_symbols
        code_lengths: code_lengths
        codes:        code_words
    }
}

fn select_group_count(n_syms int) int {
    if n_syms < 200 {
        return 2
    }
    if n_syms < 600 {
        return 3
    }
    if n_syms < 1200 {
        return 4
    }
    if n_syms < 2400 {
        return 5
    }
    return 6
}

fn selector_count_from_symbol_count(n_symbols int) !int {
    if n_symbols < 1 {
        return error('bzip2: invalid selector count')
    }
    n_selectors := (n_symbols + bzip2_group_size - 1) / bzip2_group_size
    if n_selectors < 1 || n_selectors > bzip2_max_selectors {
        return error('bzip2: invalid selector count')
    }
    return n_selectors
}

fn ensure_block_output_limit(decoded_len int, add_len int, block_limit int) ! {
    if decoded_len < 0 || add_len < 0 || block_limit < 0 {
        return error('bzip2: invalid block output state')
    }
    if decoded_len > block_limit || add_len > block_limit - decoded_len {
        return error('bzip2: block output exceeds declared block size')
    }
}

fn symbol_freq(symbols []int, alpha_size int) []int {
    mut freq := []int{len: alpha_size}
    for s in symbols {
        if s >= 0 && s < alpha_size {
            freq[s]++
        }
    }
    for i in 0 .. alpha_size {
        if freq[i] == 0 {
            freq[i] = 1
        }
    }
    return freq
}

fn write_in_use_map(mut w BitWriter, in_use []bool) {
    mut group_used := []bool{len: 16}
    for i in 0 .. 16 {
        for j in 0 .. 16 {
            if in_use[i * 16 + j] {
                group_used[i] = true
                break
            }
        }
    }
    for g in group_used {
        w.write_bit(if g { 1 } else { 0 })
    }
    for i in 0 .. 16 {
        if !group_used[i] {
            continue
        }
        for j in 0 .. 16 {
            w.write_bit(if in_use[i * 16 + j] { 1 } else { 0 })
        }
    }
}

fn read_in_use_map(mut r BitReader) ![]bool {
    mut group_used := []bool{len: 16}
    for i in 0 .. 16 {
        group_used[i] = r.read_bit()! == 1
    }
    mut in_use := []bool{len: 256}
    for i in 0 .. 16 {
        if !group_used[i] {
            continue
        }
        for j in 0 .. 16 {
            in_use[i * 16 + j] = r.read_bit()! == 1
        }
    }
    return in_use
}

fn write_code_lengths(mut w BitWriter, lengths []int, alpha_size int) {
    mut curr := lengths[0]
    w.write_bits(5, u64(curr))
    for i in 0 .. alpha_size {
        target := lengths[i]
        for curr < target {
            w.write_bit(1)
            w.write_bit(0)
            curr++
        }
        for curr > target {
            w.write_bit(1)
            w.write_bit(1)
            curr--
        }
        w.write_bit(0)
    }
}

fn decode_selector_mtf(vals []int, n_groups int) ![]int {
    mut pos := []int{len: n_groups}
    for i in 0 .. n_groups {
        pos[i] = i
    }
    mut out := []int{len: vals.len}
    for i, v in vals {
        if v < 0 || v >= n_groups {
            return error('bzip2: selector mtf value out of range')
        }
        sel := pos[v]
        for j := v; j > 0; j-- {
            pos[j] = pos[j - 1]
        }
        pos[0] = sel
        out[i] = sel
    }
    return out
}

fn encode_selector_mtf(selectors []int, n_groups int) []int {
    mut pos := []int{len: n_groups}
    for i in 0 .. n_groups {
        pos[i] = i
    }
    mut out := []int{len: selectors.len}
    for i, sel in selectors {
        mut idx := 0
        for idx < pos.len && pos[idx] != sel {
            idx++
        }
        if idx >= pos.len {
            out[i] = 0
            continue
        }
        out[i] = idx
        for j := idx; j > 0; j-- {
            pos[j] = pos[j - 1]
        }
        pos[0] = sel
    }
    return out
}

fn make_huffman_lengths(freq []int, max_len int) []int {
    mut scaled := freq.clone()
    for {
        lens := build_huffman_lengths_unbounded(scaled)
        mut max_seen := 0
        for l in lens {
            if l > max_seen {
                max_seen = l
            }
        }
        if max_seen <= max_len {
            return lens
        }
        for i in 0 .. scaled.len {
            scaled[i] = (scaled[i] >> 1) + 1
        }
    }
    return []int{}
}

fn build_huffman_lengths_unbounded(freq []int) []int {
    n := freq.len
    if n == 0 {
        return []int{}
    }
    mut weight := []int{cap: 2 * n}
    mut parent := []int{cap: 2 * n}
    for i in 0 .. n {
        w := if freq[i] > 0 { freq[i] } else { 1 }
        weight << w
        parent << -1
    }
    mut active := []int{len: n}
    for i in 0 .. n {
        active[i] = i
    }
    for active.len > 1 {
        mut m1 := 0
        mut m2 := 1
        if weight[active[m2]] < weight[active[m1]] {
            t := m1
            m1 = m2
            m2 = t
        }
        for i in 2 .. active.len {
            idx := active[i]
            if weight[idx] < weight[active[m1]] {
                m2 = m1
                m1 = i
            } else if weight[idx] < weight[active[m2]] {
                m2 = i
            }
        }
        a := active[m1]
        b := active[m2]
        new_idx := weight.len
        weight << (weight[a] + weight[b])
        parent << -1
        parent[a] = new_idx
        parent[b] = new_idx
        if m1 > m2 {
            active.delete(m1)
            active.delete(m2)
        } else {
            active.delete(m2)
            active.delete(m1)
        }
        active << new_idx
    }
    mut lengths := []int{len: n}
    for i in 0 .. n {
        mut l := 0
        mut p := parent[i]
        for p != -1 {
            l++
            p = parent[p]
        }
        if l == 0 {
            l = 1
        }
        lengths[i] = l
    }
    return lengths
}

fn build_huffman_codes(lengths []int) []u32 {
    mut max_len := 0
    for l in lengths {
        if l > max_len {
            max_len = l
        }
    }
    mut bl_count := []int{len: max_len + 1}
    for l in lengths {
        if l > 0 {
            bl_count[l]++
        }
    }
    mut next_code := []u32{len: max_len + 1}
    mut code := u32(0)
    for bits in 1 .. max_len + 1 {
        code = (code + u32(bl_count[bits - 1])) << 1
        next_code[bits] = code
    }
    mut out := []u32{len: lengths.len}
    for i, l in lengths {
        if l == 0 {
            continue
        }
        out[i] = next_code[l]
        next_code[l]++
    }
    return out
}

struct DecodeTable {
    min_len int
    max_len int
    base    []int
    limit   []int
    perm    []int
}

fn build_decode_table(lengths []int, alpha_size int) !DecodeTable {
    mut min_len := 999
    mut max_len := 0
    for i in 0 .. alpha_size {
        l := lengths[i]
        if l < 1 || l > bzip2_max_code_len {
            return error('bzip2: invalid huffman code length')
        }
        if l < min_len {
            min_len = l
        }
        if l > max_len {
            max_len = l
        }
    }
    mut perm := []int{}
    for l in min_len .. max_len + 1 {
        for i in 0 .. alpha_size {
            if lengths[i] == l {
                perm << i
            }
        }
    }
    mut base := []int{len: max_len + 2}
    mut limit := []int{len: max_len + 1}
    for i in 0 .. alpha_size {
        base[lengths[i] + 1]++
    }
    for i in 1 .. base.len {
        base[i] += base[i - 1]
    }
    mut vec := 0
    for l in min_len .. max_len + 1 {
        vec += base[l + 1] - base[l]
        limit[l] = vec - 1
        vec <<= 1
    }
    for l in min_len + 1 .. max_len + 1 {
        base[l] = ((limit[l - 1] + 1) * 2) - base[l]
    }
    return DecodeTable{
        min_len: min_len
        max_len: max_len
        base:    base
        limit:   limit
        perm:    perm
    }
}

fn (t DecodeTable) decode(mut r BitReader) !int {
    mut zn := t.min_len
    mut zvec := int(r.read_bits(zn)!)
    for zn <= t.max_len && zvec > t.limit[zn] {
        zn++
        bit := int(r.read_bits(1)!)
        zvec = (zvec * 2) | bit
    }
    if zn > t.max_len {
        return error('bzip2: invalid huffman code')
    }
    idx := zvec - t.base[zn]
    if idx < 0 || idx >= t.perm.len {
        return error('bzip2: invalid huffman decode index')
    }
    return t.perm[idx]
}

fn mtf_rle2_encode(data []u8, unseq_to_seq []int, n_in_use int) ([]int, int) {
    mut mtf := []int{len: n_in_use}
    for i in 0 .. n_in_use {
        mtf[i] = i
    }
    eob := n_in_use + 1
    mut out := []int{}
    mut zpend := 0
    for b in data {
        seq := unseq_to_seq[int(b)]
        mut pos := 0
        for pos < mtf.len && mtf[pos] != seq {
            pos++
        }
        if pos == 0 {
            zpend++
            continue
        }
        if zpend > 0 {
            emit_run_a_b(mut out, zpend)
            zpend = 0
        }
        out << (pos + 1)
        move_to_front_int(mut mtf, pos)
    }
    if zpend > 0 {
        emit_run_a_b(mut out, zpend)
    }
    out << eob
    return out, n_in_use + 2
}

fn emit_run_a_b(mut out []int, run_len int) {
    mut z := run_len - 1
    for {
        if (z & 1) == 0 {
            out << bzip2_runa
        } else {
            out << bzip2_runb
        }
        if z < 2 {
            break
        }
        z = (z - 2) >> 1
    }
}

fn move_to_front_int(mut arr []int, pos int) {
    if pos <= 0 {
        return
    }
    tmp := arr[pos]
    for i := pos; i > 0; i-- {
        arr[i] = arr[i - 1]
    }
    arr[0] = tmp
}

fn rle1_encode(src []u8) []u8 {
    if src.len == 0 {
        return []u8{}
    }
    mut out := []u8{cap: src.len + (src.len / 4) + 8}
    mut i := 0
    for i < src.len {
        b := src[i]
        mut run := 1
        for i + run < src.len && src[i + run] == b && run < max_i32 {
            run++
        }
        mut rem := run
        for rem > 0 {
            if rem <= 3 {
                for _ in 0 .. rem {
                    out << b
                }
                rem = 0
            } else {
                chunk := if rem > 259 { 259 } else { rem }
                for _ in 0 .. 4 {
                    out << b
                }
                out << u8(chunk - 4)
                rem -= chunk
            }
        }
        i += run
    }
    return out
}

fn find_rle1_block_end(src []u8, start int, block_limit int) int {
    if start >= src.len {
        return start
    }
    mut end := start
    mut encoded_len := 0
    for end < src.len {
        b := src[end]
        mut run_len := 1
        for end + run_len < src.len && src[end + run_len] == b {
            run_len++
        }
        run_encoded_len := rle1_encoded_run_len(run_len)
        if encoded_len + run_encoded_len <= block_limit {
            encoded_len += run_encoded_len
            end += run_len
            continue
        }
        available := block_limit - encoded_len
        if available <= 0 {
            break
        }
        take := max_run_prefix_for_rle1(run_len, available)
        if take <= 0 {
            break
        }
        end += take
        break
    }
    if end == start {
        return start + 1
    }
    return end
}

fn max_run_prefix_for_rle1(run_len int, encoded_limit int) int {
    if run_len <= 0 || encoded_limit <= 0 {
        return 0
    }
    mut lo := 1
    mut hi := run_len
    mut best := 0
    for lo <= hi {
        mid := lo + (hi - lo) / 2
        if rle1_encoded_run_len(mid) <= encoded_limit {
            best = mid
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return best
}

fn rle1_encoded_run_len(run_len int) int {
    if run_len <= 0 {
        return 0
    }
    if run_len <= 3 {
        return run_len
    }
    full_chunks := run_len / 259
    rem := run_len % 259
    mut out := full_chunks * 5
    if rem == 0 {
        return out
    }
    if rem <= 3 {
        out += rem
    } else {
        out += 5
    }
    return out
}

fn rle1_decode(src []u8) ![]u8 {
    mut out := []u8{cap: src.len}
    mut i := 0
    for i < src.len {
        if i + 4 < src.len && src[i] == src[i + 1] && src[i] == src[i + 2] && src[i] == src[i + 3] {
            run := int(src[i + 4]) + 4
            for _ in 0 .. run {
                out << src[i]
            }
            i += 5
        } else {
            out << src[i]
            i++
        }
    }
    return out
}

fn bwt_transform(data []u8) ([]u8, int) {
    n := data.len
    if n == 0 {
        return []u8{}, 0
    }
    mut sa := cyclic_suffix_array(data)
    mut out := []u8{len: n}
    mut orig_ptr := 0
    for i, s in sa {
        if s == 0 {
            orig_ptr = i
            out[i] = data[n - 1]
        } else {
            out[i] = data[s - 1]
        }
    }
    return out, orig_ptr
}

fn inverse_bwt(last_col []u8, orig_ptr int) ![]u8 {
    n := last_col.len
    if n == 0 {
        return []u8{}
    }
    if orig_ptr < 0 || orig_ptr >= n {
        return error('bzip2: invalid bwt origin pointer')
    }
    mut count := []int{len: 256}
    for b in last_col {
        count[int(b)]++
    }
    mut tots := []int{len: 256}
    mut sum := 0
    for i in 0 .. 256 {
        tots[i] = sum
        sum += count[i]
    }
    mut tt := []int{len: n}
    for i, b in last_col {
        idx := int(b)
        tt[tots[idx]] = i
        tots[idx]++
    }
    mut out := []u8{len: n}
    mut tpos := orig_ptr
    for i in 0 .. n {
        tpos = tt[tpos]
        out[i] = last_col[tpos]
    }
    return out
}

fn cyclic_suffix_array(data []u8) []int {
    n := data.len
    if n <= 1 {
        if n == 1 {
            return [0]
        }
        return []int{}
    }
    mut sa := []int{len: n}
    mut rank := []int{len: n}
    for i in 0 .. n {
        sa[i] = i
        rank[i] = int(data[i])
    }
    mut tmp_sa := []int{len: n}
    mut new_rank := []int{len: n}
    mut k := 1
    for k < n {
        radix_sort_cyclic(mut sa, mut tmp_sa, rank, k)
        new_rank[sa[0]] = 0
        mut classes := 1
        for i in 1 .. n {
            a := sa[i - 1]
            b := sa[i]
            if rank[a] != rank[b] || rank[(a + k) % n] != rank[(b + k) % n] {
                classes++
            }
            new_rank[b] = classes - 1
        }
        rank = new_rank.clone()
        if classes == n {
            break
        }
        k <<= 1
    }
    return sa
}

fn radix_sort_cyclic(mut sa []int, mut tmp []int, rank []int, k int) {
    n := sa.len
    m := if n > 256 { n } else { 256 }
    mut count := []int{len: m}
    for i in 0 .. n {
        key := rank[(sa[i] + k) % n]
        count[key]++
    }
    mut pos := []int{len: m}
    mut sum := 0
    for i in 0 .. m {
        pos[i] = sum
        sum += count[i]
    }
    for i in 0 .. n {
        v := sa[i]
        key := rank[(v + k) % n]
        tmp[pos[key]] = v
        pos[key]++
    }
    count = []int{len: m}
    for i in 0 .. n {
        key := rank[tmp[i]]
        count[key]++
    }
    sum = 0
    for i in 0 .. m {
        pos[i] = sum
        sum += count[i]
    }
    for i in 0 .. n {
        v := tmp[i]
        key := rank[v]
        sa[pos[key]] = v
        pos[key]++
    }
}

struct BitWriter {
mut:
    out       []u8
    bitbuf    u64
    bit_count int
}

fn (mut w BitWriter) write_byte(b u8) {
    w.out << b
}

fn (mut w BitWriter) write_bit(bit int) {
    w.write_bits(1, u64(bit & 1))
}

fn (mut w BitWriter) write_bits(n int, value u64) {
    if n <= 0 {
        return
    }
    for i := n - 1; i >= 0; i-- {
        b := (value >> u32(i)) & 1
        w.bitbuf = (w.bitbuf << 1) | b
        w.bit_count++
        if w.bit_count == 8 {
            w.out << u8(w.bitbuf & 0xff)
            w.bitbuf = 0
            w.bit_count = 0
        }
    }
}

fn (mut w BitWriter) finish() ![]u8 {
    if w.bit_count > 0 {
        w.bitbuf <<= u32(8 - w.bit_count)
        w.out << u8(w.bitbuf & 0xff)
        w.bitbuf = 0
        w.bit_count = 0
    }
    return w.out
}

struct BitReader {
    data []u8
mut:
    byte_pos int
    bit_pos  int
}

fn (mut r BitReader) read_byte() !u8 {
    if r.bit_pos != 0 {
        return error('bzip2: attempted byte read on non-byte boundary')
    }
    if r.byte_pos >= r.data.len {
        return error('bzip2: unexpected end of input')
    }
    b := r.data[r.byte_pos]
    r.byte_pos++
    return b
}

fn (mut r BitReader) read_bit() !int {
    return int(r.read_bits(1)!)
}

fn (mut r BitReader) read_bits(n int) !u64 {
    if n < 0 || n > 56 {
        return error('bzip2: invalid bit width')
    }
    mut out := u64(0)
    for _ in 0 .. n {
        if r.byte_pos >= r.data.len {
            return error('bzip2: unexpected end of input')
        }
        b := r.data[r.byte_pos]
        bit := (b >> u8(7 - r.bit_pos)) & u8(1)
        out = (out << 1) | u64(bit)
        r.bit_pos++
        if r.bit_pos == 8 {
            r.bit_pos = 0
            r.byte_pos++
        }
    }
    return out
}

fn (r &BitReader) is_aligned_to_byte_zero_padding() bool {
    if r.bit_pos == 0 {
        return r.byte_pos == r.data.len
    }
    if r.byte_pos >= r.data.len {
        return false
    }
    mask := u8((1 << u8(8 - r.bit_pos)) - 1)
    if (r.data[r.byte_pos] & mask) != 0 {
        return false
    }
    for i in r.byte_pos + 1 .. r.data.len {
        if r.data[i] != 0 {
            return false
        }
    }
    return true
}

fn rotate_left_1(v u32) u32 {
    return (v << 1) | (v >> 31)
}

fn bzip2_crc32(data []u8) u32 {
    mut crc := u32(0xffffffff)
    for b in data {
        table_idx := int(((crc >> 24) ^ u32(b)) & u32(0xff))
        crc = (crc << 8) ^ bzip2_crc32_table[table_idx]
    }
    return ~crc
}