openpower/prefix_codes.mdwn

   1 # Prefix-code encode/decode acceleration
   2
   3 This is useful for Huffman codes, and other prefix-codes, which are used a lot in common formats:
   4
   5 * DEFLATE (zip, png, gzip, etc.)
   6 * JPEG
   7 * MP3
   8 * etc.
   9
  10 # Prefix-code decode description
  11
  12 `pcdec RT,RA,RB,RC,imm`
  13
  14     |0   |6   |11  |16  |21  |26  |31   |
  15     | PO | RT | RA | RB | RC | XO | imm |
  16
  17 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
  18
  19 The binary code tree is encoded in `RA` like so:
  20
  21 ```
  22 t[i] = (RA >> i) & 0x1
  23
  24                        |
  25            +-----------+-----------+
  26            |                       |
  27            0                       1
  28            |                       |
  29      +---t[2]----+           +---t[3]----+
  30      |           |           |           |
  31      0           1           0           1
  32      |           |           |           |
  33   +t[4]-+     +t[5]-+     +t[6]-+     +t[7]-+
  34   |     |     |     |     |     |     |     |
  35   0     1     0     1     0     1     0     1
  36   |     |     |     |     |     |     |     |
  37 t[8]  t[9]  t[10] t[11] t[12] t[13] t[14] t[15]
  38
  39 and so on for t[16..]
  40 ```
  41
  42 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.
  43
  44 # [DRAFT] Prefix-code decode
  45
  46 sorta-VA-Form
  47
  48 * pcdec RT,RA,RB,RC,imm
  49
  50 Pseudo-code:
  51
  52     tree[0:63] <- (RA)
  53     in_bits[0:63] <- (RB)
  54     in_pos <- (RC)
  55     decoded_in_pos <- in_pos
  56     output <- [0] * 64
  57     out_byte <- 0
  58     decoded[0:7] <- 1
  59     overflow <- 0
  60     do while in_pos <u 64
  61         # walk the binary tree in `tree` from parent to the selected child
  62         decoded <- decoded * 2 + bitstream[63 - in_pos]
  63         in_pos <- in_pos + 1
  64         if decoded >=u 64 then
  65             overflow <- 1
  66             break
  67         if tree[63 - decoded] then
  68             decoded_in_pos <- in_pos
  69             output[56 - 8 * out_byte:63 - 8 * out_byte] <- decoded
  70             decoded <- 1
  71             out_byte <- out_byte + 1
  72             if one | (out_byte >=u 8) then
  73                 break
  74     RT <- output
  75     RS <- decoded_in_pos
  76
  77 Special Registers Altered:
  78
  79     SO OV OV32
  80
  81 # [DRAFT] Prefix-code encode
  82
  83 TODO