Prefix-code encode/decode acceleration

This is useful for Huffman codes, and other prefix-codes, which are used a lot in common formats:

  • DEFLATE (zip, png, gzip, etc.)
  • JPEG
  • MP3
  • MPEG-2/H.262 (DVD video)
  • zstd
  • Brotli
  • etc.

Links:

Prefix-code decode description

pcdec. RT,RA,RB,RC,imm

|0   |6   |11  |16  |21  |26  |31   |
| PO | RT | RA | RB | RC | XO | imm |

if imm is 1, at most one code-word is decoded -- useful for things like DEFLATE that alternate code words with other bits, or use multiple binary code trees. if imm is 0, it decodes multiple code-words

The binary code tree is encoded in RB like so:

t[i] = (RB >> i) & 0x1

                       |
           +-----------+-----------+
           |                       |
           0                       1
           |                       |
     +---t[2]----+           +---t[3]----+
     |           |           |           |
     0           1           0           1
     |           |           |           |
  +t[4]-+     +t[5]-+     +t[6]-+     +t[7]-+
  |     |     |     |     |     |     |     |
  0     1     0     1     0     1     0     1
  |     |     |     |     |     |     |     |
t[8]  t[9]  t[10] t[11] t[12] t[13] t[14] t[15]

and so on for t[16..]

Decoding a code word works by walking on the tree from the root to the children, matching each passed 0 or 1 to the next read input bit in RA in LSB to MSB order. When t[i] is set, then a valid code word was read and i is written to the next byte of output in RT in LSB to MSB order. When no set t[i] is encountered, and there are still input bits left, then the code word is >5-bits, so SO/OV/OV32 are set, and decoding stops.

[DRAFT] Prefix-code decode

VA2-Form

  • pcdec. RT,RA,RB,RC,once

Pseudo-code:

tree[0:63] <- (RB)
ra_used <- 0b0
in_bits[0:63] <- (RC|0)
if in_bits = 0 then
    in_bits[0:63] <- 1
final_in_bits <- in_bits
final_ra_used <- ra_used
output <- [0] * 64
out_byte <- 0
decoded[0:7] <- 1
so_bit <- 0b0
do while out_byte < 8
    in_bit <- in_bits[63]
    if in_bits = 1 then
        if ra_used | (_RA = 0) then
            leave
        ra_used <- 0b1
        in_bit <- (RA)[63]
        in_bits <- 0b1 || (RA)[0:62]
    else
        in_bits <- 0b0 || in_bits[0:62]
    # walk the binary tree in `tree` from parent to the selected child
    decoded <- decoded[1:7] || in_bit
    if decoded <u 64 then
        if tree[63 - decoded] then
            final_in_bits <- in_bits
            final_ra_used <- ra_used
            output[56 - 8 * out_byte:63 - 8 * out_byte] <- decoded
            decoded[0:7] <- 1
            out_byte <- out_byte + 1
            if once then
                leave
    else
        so_bit <- 0b1
        leave
RT <- output
RS <- final_in_bits
CR0 <- final_ra_used || 0b0 || (output = 0) || so_bit

Special Registers Altered:

CR0

[DRAFT] Prefix-code encode

TODO