From 6afd007c188894b123c6f8360be1fb292f59b0e4 Mon Sep 17 00:00:00 2001
From: Jacob Lifshay <programmerjake@gmail.com>
Date: Wed, 21 Sep 2022 13:43:23 -0700
Subject: [PATCH] add initial draft of prefix-code (like huffman code) dec/enc
 instructions

---
 openpower.mdwn              |  1 +
 openpower/prefix_codes.mdwn | 55 +++++++++++++++++++++++++++++++++++++
 openpower/sv.mdwn           |  1 +
 3 files changed, 57 insertions(+)
 create mode 100644 openpower/prefix_codes.mdwn

diff --git a/openpower.mdwn b/openpower.mdwn
index 38e10eb2d..da186f35b 100644
--- a/openpower.mdwn
+++ b/openpower.mdwn
@@ -30,6 +30,7 @@ EULA released! looks good.
 * [[openpower/isa]] - pseudo-code extracted from POWER V3.0B PDF spec
 * [[openpower/gem5]]
 * [[openpower/sv]]
+* [[openpower/prefix_codes]] Decode/encode prefix-codes, used by JPEG, DEFLATE, etc.
 * [[openpower/opcode_regs_deduped]]
 * [[openpower/simd_vsx]]
 * [[openpower/ISA_WG]] - OpenPOWER ISA Working Group
diff --git a/openpower/prefix_codes.mdwn b/openpower/prefix_codes.mdwn
new file mode 100644
index 000000000..3158de09a
--- /dev/null
+++ b/openpower/prefix_codes.mdwn
@@ -0,0 +1,55 @@
+# 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
+* etc.
+
+# Prefix-code decode description
+
+`pcdec RT,RA,RB,RC,imm`
+
+if `imm` is 1 TODO FIXME
+
+# [DRAFT] Prefix-code decode
+
+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
+
+# [DRAFT] Prefix-code encode
+
+TODO
\ No newline at end of file
diff --git a/openpower/sv.mdwn b/openpower/sv.mdwn
index 71e73cd6f..6fc55599f 100644
--- a/openpower/sv.mdwn
+++ b/openpower/sv.mdwn
@@ -243,6 +243,7 @@ Stand-alone Scalar Instructions:
 * [[sv/fclass]] detect class of FP numbers
 * [[sv/int_fp_mv]] Move and convert GPR <-> FPR, needed for !VSX
 * [[sv/av_opcodes]] scalar opcodes for Audio/Video
+* [[prefix_codes]] Decode/encode prefix-codes, used by JPEG, DEFLATE, etc.
 * TODO: OpenPOWER adaptation [[openpower/transcendentals]]
 
 Twin targetted instructions (two registers out, one implicit, just like
-- 
2.30.2