* Brotli
* etc.
+Links:
+
+* <https://gist.github.com/kirlf/2eb242f225f9bfed4ecbfc8e1e2f5f71>
+* <https://en.m.wikipedia.org/wiki/Huffman_coding>
+* <https://bugs.libre-soc.org/show_bug.cgi?id=933>
+
# Prefix-code decode description
-`pcdec RT,RA,RB,RC,imm`
+`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 `RA` like so:
+The binary code tree is encoded in `RB` like so:
```
-t[i] = (RA >> i) & 0x1
+t[i] = (RB >> i) & 0x1
|
+-----------+-----------+
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 RB 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 >6-bits, so SO/OV/OV32 are set, and decoding stops.
-
-# [DRAFT] Prefix-code decode
-
-sorta-VA-Form
-
-* pcdec RT,RA,RB,RC,imm
-
-Pseudo-code:
-
- tree[0:63] <- (RA)
- in_bits[0:63] <- (RB)
- in_pos <- (RC)
- decoded_in_pos <- in_pos
- output <- [0] * 64
- out_byte <- 0
- decoded[0:7] <- 1
- overflow <- 0
- do while in_pos <u 64
- # walk the binary tree in `tree` from parent to the selected child
- decoded <- decoded * 2 + bitstream[63 - in_pos]
- in_pos <- in_pos + 1
- if decoded >=u 64 then
- overflow <- 1
- break
- if tree[63 - decoded] then
- decoded_in_pos <- in_pos
- output[56 - 8 * out_byte:63 - 8 * out_byte] <- decoded
- decoded <- 1
- out_byte <- out_byte + 1
- if one | (out_byte >=u 8) then
- break
- RT <- output
- RS <- decoded_in_pos
-
-Special Registers Altered:
-
- SO OV OV32
+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.
+
+[[!inline pages="openpower/isa/prefix_codes" quick="yes" raw="yes" ]]
# [DRAFT] Prefix-code encode
-TODO
\ No newline at end of file
+TODO