[Libre-soc-isa] [Bug 933] prefix-code (like huffman code) decode/encode instructions

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=933

--- Comment #33 from Jacob Lifshay <programmerjake at gmail.com> ---
I have an idea for better fallback decoding: use pcdec. once=1 multiple times,
looking up the `tree` value in a table, this allows reading up to 5 bits each
time, which is small enough to be a reasonable in-memory table size.

basically (taking into account RA/RB now swapped):
fallback_table = [...]
tree = 0xFFFF_FFFF_0000_0000
bits = 1  # u64
while True:
    pcdec. addr, next_input, tree, leftover_bits, 1
    leftover_bits = RS
    if used_RA:
        next_input = *input++
    if addr = 0:
        error("invalid code")
    bit_count = floor_log2(bits)  # 63 - count_leading_zeros(bits)
    bits &= ~(1 << bit_count)
    bits |= addr << bit_count
    if addr < 32 or fallback_table is None:
        break  # done
    # now 32 <= addr < 64, so fallback_table needs 32 entries
    tree, fallback_table = fallback_table[addr - 32]
# decoded code is in bits

-- 
You are receiving this mail because:
You are on the CC list for the bug.