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

VA-Form

  • pcdec. RT,RA,RB,RC

Pseudo-code:

tree[0:63] <- (RB)
mode <- tree[62:63]
tree[62:63] <- 0
ra_used <- 0b0
in_bits[0:63] <- (RC|0)
if in_bits = 0 then
    in_bits[0:63] <- 1
orig_in_bits <- in_bits
tree_index <- 1
found <- 0b0
hit_end <- 0b0
do bit_length = 1 to 6
    in_bit <- in_bits[63]
    if in_bits = 1 then
        if ra_used | (_RA = 0) then
            hit_end <- 0b1
            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
    tree_index <- tree_index * 2
    if in_bit = 1 then
        tree_index <- tree_index + 1
    if tree_index < 64 then
        if tree[63 - tree_index] then
            found <- 0b1
            leave
compressed_index <- 0
do i = 0 to 127
    possible <- 1
    j <- i
    do while j >= 4
        j <- j / 2
        if tree[63 - j] then
            possible <- 0
            leave
    if i = tree_index then
        leave
    else if i >= 64 then
        compressed_index <- compressed_index + possible
    else if tree[63 - i] = 1 then
        compressed_index <- compressed_index + possible
switch(mode)
    case(0):
        RT[0:63] <- tree_index
        if ¬found then
            in_bits <- orig_in_bits
            ra_used <- 0b0
    case(1):
        RT[0:63] <- tree_index
        if hit_end then
            in_bits <- orig_in_bits
            ra_used <- 0b0
    case(2):
        RT[0:63] <- compressed_index
        if ¬found then
            in_bits <- orig_in_bits
            ra_used <- 0b0
            RT[0:63] <- tree_index
    default:
        RT[0:63] <- compressed_index
        if hit_end then
            in_bits <- orig_in_bits
            ra_used <- 0b0
RS <- in_bits
CR0 <- ra_used || (tree_index >= 64) || found || hit_end

Special Registers Altered:

CR0

[DRAFT] Prefix-code encode

TODO