[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 #35 from Jacob Lifshay <programmerjake at gmail.com> ---
After writing code to generate the lookup tables needed for JPEG decoding from
the huffman tables in the JPEG, I realized that those tables are huge and
mostly zeros, so I'm altering pcdec.'s definition to optionally compress the
output index (explained below).

the least-significant 2 bits of the `tree` input are unused, so I crammed a
2-bit mode in there instead of having a `once` immediate (should be fine
because `tree` values are only rarely created), allowing selecting a few
different modes that output compressed/uncompressed indexes and optionally read
6-bits into the output when nothing matches in the `tree` input (allowing
processing 6-bits at a time of input instead of 5 for long prefix codes).

compressed output indexes:
basically if `tree` is:
 0b1100000001000100
(codes for "0", "10", "110", and "111")
then:
decoded input    uncompressed index    compressed index
"0"              0b1_0                 0
"10"             0b1_10                1
"110"            0b1_110               2
"111"            0b1_111               3

the compressed index can be calculated by calculating the number of 1-bits that
are less-significant than the bit 1<<uncompressed_index, ignoring the two LSB
`tree` bits (since they're used for `mode` instead)

this compressed index encoding actually largely matches how JPEG stores huffman
codes' corresponding values.

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