* grev <https://bugs.libre-soc.org/show_bug.cgi?id=755>
* remove Rc=1 from ternlog due to conflicts in encoding as well
as saving space <https://bugs.libre-soc.org/show_bug.cgi?id=753#c5>
+* GF2^M <https://bugs.libre-soc.org/show_bug.cgi?id=782>
# bitmanipulation
**DRAFT STATUS**
+pseudocode: <https://libre-soc.org/openpower/isa/bitmanip/>
+
this extension amalgamates bitmanipulation primitives from many sources, including RISC-V bitmanip, Packed SIMD, AVX-512 and OpenPOWER VSX. Vectorisation and SIMD are removed: these are straight scalar (element) operations making them suitable for embedded applications.
Vectorisation Context is provided by [[openpower/sv]].
ternlogv is experimental and is the only operation that may be considered a "Packed SIMD". It is added as a variant of the already well-justified ternlog operation (done in AVX512 as an immediate only) "because it looks fun". As it is based on the LUT4 concept it will allow accelerated emulation of FPGAs. Other vendors of ISAs are buying FPGA companies to achieve similar objectives.
-general-purpose Galois Field operations are added so as to avoid huge custom opcode proliferation across many areas of Computer Science. however for convenience and also to avoid setup costs, some of the more common operations (clmul, crc32) are also added. The expectation is that these operations would all be covered by the same pipeline.
+general-purpose Galois Field 2^M operations are added so as to avoid huge custom opcode proliferation across many areas of Computer Science. however for convenience and also to avoid setup costs, some of the more common operations (clmul, crc32) are also added. The expectation is that these operations would all be covered by the same pipeline.
note that there are brownfield spaces below that could incorporate some of the set-before-first and other scalar operations listed in [[sv/vector_ops]], and
the [[sv/av_opcodes]] as well as [[sv/setvl]]
minor opcode allocation
- | 28.30 |31| name |
- | ------ |--| --------- |
- | 00 |0 | ternlogi |
- | 000 |1 | ternlog |
- | 100 |1 | grevlog |
- | 010 |Rc| bitmask |
- | 011 |Rc| gf* |
- | 101 |1 | ternlogv |
- | 101 |0 | ternlogcr |
- | 110 |Rc| 1/2-op |
- | 111 |Rc| 3-op |
+| 28.30 |31| name |
+| ------ |--| --------- |
+| -00 |0 | ternlogi |
+| -00 |1 | grevlog |
+| -01 | | grevlogi |
+| 010 |Rc| bitmask |
+| 011 |0 | gfbmadd* |
+| 011 |1 | clmadd* |
+| 110 |Rc| 1/2-op |
+| 111 |1 | ternlogv |
+| 111 |0 | ternlogcr |
1-op and variants
| RT | RA | RB | type | minmax |
| RT | RA | RB | | av abs avgadd |
| RT | RA | RB | type | vmask ops |
-| RT | RA | RB | | |
+| RT | RA | RB | | |
3 ops
-* bitmask set/extract
+* grevlog
* ternlog bitops
-* GF
+* GF mul-add
+* bitmask-reverse
TODO: convert all instructions to use RT and not RS
-| 0.5|6.10|11.15|16.20 |21..25 | 26....30 |31| name |
-| -- | -- | --- | --- | ----- | -------- |--| ------ |
-| NN | RT | RA | RB | RC | mode 000 |1 | ternlog |
-| NN | RT | RA | RB | im0-4 | im5-7 00 |0 | ternlogi |
-| NN | RT | RA | RB | / im0-3 | 00 100 |1 | grevlog |
-| NN | RT | RA | s0-5 | s6 im0-3| 01 100 |1 | grevlogi |
-| NN | RT | RA | | | 1- 100 |1 | rsvd |
-| NN | RS | RA | RB | RC | 00 011 |Rc| gfmul |
-| NN | RS | RA | RB | RC | 01 011 |Rc| gfadd |
-| NN | RT | RA | RB | deg | 10 011 |Rc| gfinv |
-| NN | RS | RA | RB | deg | 11 011 |Rc| gfmuli |
-| NN | RS | RA | RB | deg | 11 111 |Rc| gfaddi |
+| 0.5|6.10|11.15|16.20 |21..25 | 26....30 |31| name |
+| -- | -- | --- | --- | ----- | -------- |--| ------ |
+| NN | RT | RA | RB | im0-4 | im5-7 00 |0 | ternlogi |
+| NN | RT | RA | RB | im0-4 | im5-7 00 |1 | grevlog |
+| NN | RT | RA | s0-4 | im0-4 | im5-7 01 |s5| grevlogi |
+| NN | RS | RA | RB | RC | 00 011 |0 | gfbmadd |
+| NN | RS | RA | RB | RC | 10 011 |0 | gfbmaddsub |
+| NN | RS | RA | RB | RC | 00 011 |1 | clmadd |
+| NN | RS | RA | RB | RC | 10 011 |1 | clmaddsub |
+| NN | RT | RA | RB | sh0-4 | sh5 1 011 |Rc| bmrevi |
| 0.5|6.10|11.15| 16.23 |24.27 | 28.30 |31| name |
| -- | -- | --- | ----- | ---- | ----- |--| ------ |
-| NN | RT | RA | imm | mask | 101 |1 | ternlogv |
+| NN | RT | RA | imm | mask | 111 |1 | ternlogv |
| 0.5|6.8 | 9.11|12.14|15|16.23|24.27 | 28.30|31| name |
| -- | -- | --- | --- |- |-----|----- | -----|--| -------|
-| NN | BA | BB | BC |0 |imm | mask | 101 |0 | ternlogcr |
+| NN | BA | BB | BC |0 |imm | mask | 111 |0 | ternlogcr |
ops (note that av avg and abs as well as vec scalar mask
are included here)
| NN | RA | RB | | 1 | 11 | 0100 110 |Rc| rsvd |
| NN | RA | RB | sh | SH | itype | 1000 110 |Rc| bmopsi |
| NN | RA | RB | | | | 1100 110 |Rc| rsvd |
-| NN | RA | RB | | 1 | | 0001 110 |Rc| rsvd |
+| NN | RT | RA | RB | 1 | 00 | 0001 110 |Rc| cldiv |
+| NN | RT | RA | RB | 1 | 01 | 0001 110 |Rc| clmod |
+| NN | RT | RA | RB | 1 | 10 | 0001 110 |Rc| |
+| NN | RT | RB | RB | 1 | 11 | 0001 110 |Rc| clinv |
| NN | RA | RB | RC | 0 | 00 | 0001 110 |Rc| vec sbfm |
| NN | RA | RB | RC | 0 | 01 | 0001 110 |Rc| vec sofm |
| NN | RA | RB | RC | 0 | 10 | 0001 110 |Rc| vec sifm |
| NN | RA | RB | RC | 0 | 10 | 0010 110 |Rc| shfl |
| NN | RA | RB | sh | SH | 10 | 1010 110 |Rc| shfli |
| NN | RA | RB | RC | 0 | 10 | 0110 110 |Rc| shflw |
-| NN | RA | RB | RC | | 10 | 1110 110 |Rc| rsvd |
+| NN | RA | RB | RC | | 10 | 1110 110 |Rc| rsvd |
| NN | RA | RB | RC | 0 | 11 | 1110 110 |Rc| clmulr |
| NN | RA | RB | RC | 1 | 11 | 1110 110 |Rc| clmulh |
| NN | | | | | | --11 110 |Rc| setvl |
| 0.5|6.10|11.15| 16.23 |24.27 | 28.30 |31|
| -- | -- | --- | ----- | ---- | ----- |--|
-| NN | RT | RA | imm | mask | 101 |1 |
+| NN | RT | RA | imm | mask | 111 |1 |
for i in range(8):
idx = RA.x[i] << 2 | RA.y[i] << 1 | RA.z[i]
| 0.5|6.8 | 9.11|12.14|15|16.23|24.27 | 28.30|31|
| -- | -- | --- | --- |- |-----|----- | -----|--|
-| NN | BA | BB | BC |0 |imm | mask | 101 |0 |
+| NN | BA | BB | BC |0 |imm | mask | 111 |0 |
for i in range(4):
if not mask[i] continue
| 0.5|6.10|11.15|16.20|21.25| 26..30 |31| name |
| -- | -- | --- | --- | --- | ------- |--| ----- |
| NN | RT | RA | RB | RC | mode 010 |Rc| bm* |
-| NN | RT | RA | RB | RC | 0 1 111 |Rc| bmrev |
```
| 0.5|6.10|11.15|16.20|21.26| 27..30 |31| name |
| -- | -- | --- | --- | --- | ------- |--| ------ |
-| NN | RT | RA | RB | sh | 0 111 |Rc| bmrevi |
+| NN | RT | RA | RB | sh | 1 011 |Rc| bmrevi |
# grevlut
-generalised reverse combined with a LUT2 and allowing
+generalised reverse combined with a pair of LUT2s and allowing
zero when RA=0 provides a wide range of instructions
and a means to set regular 64 bit patterns in one
32 bit instruction.
+the two LUT2s are applied left-half (when not swapping)
+and right-half (when swapping) so as to allow a wider
+range of options
+
+<img src="/openpower/sv/grevlut2x2.jpg" width=700 />
+
```
lut2(imm, a, b):
idx = b << 1 | a
return imm[idx] # idx by LSB0 order
-dorow(imm, step_i, chunksize):
+dorow(imm8, step_i, chunksize):
for j in 0 to 63:
+ if (j&chunk_size) == 0
+ imm = imm8[0..3]
+ else
+ imm = imm8[4..7]
step_o[j] = lut2(imm, step_i[j], step_i[j ^ chunk_size])
return step_o
-uint64_t grevlut64(uint64_t RA, uint64_t RB, uint8 lut2)
+uint64_t grevlut64(uint64_t RA, uint64_t RB, uint8 imm)
{
uint64_t x = RA;
int shamt = RB & 63;
- int imm = lut2 & 0b1111;
for i in 0 to 6
step = 1<<i
if (shamt & step) x = dorow(imm, x, step)
```
-# Galois Field
+# Galois Field 2^M
-see <https://courses.csail.mit.edu/6.857/2016/files/ffield.py>
+see:
-## Multiply
+* <https://courses.csail.mit.edu/6.857/2016/files/ffield.py>
+* <https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture7.pdf>
+* <https://foss.heptapod.net/math/libgf2/-/blob/branch/default/src/libgf2/gf2.py>
+
+## SPRs to set modulo and degree
+
+to save registers and make operations orthogonal with standard
+arithmetic the modulo is to be set in an SPR
+
+## Twin Butterfly (Tukey-Cooley) Mul-add-sub
+
+used in combination with SV FFT REMAP to perform
+a full NTT in-place. possible by having 3-in 2-out,
+to avoid the need for a temp register. RS is written
+to as well as RT.
-this requires 3 parameters and a "degree"
+ gffmadd RT,RA,RC,RB (Rc=0)
+ gffmadd. RT,RA,RC,RB (Rc=1)
- RT = GFMUL(RA, RB, gfdegree, modulo=RC)
+Pseudo-code:
-realistically with the degree also needing to be an immediate it should be brought down to an overwrite version:
+ RT <- GFADD(GFMUL(RA, RC), RB))
+ RS <- GFADD(GFMUL(RA, RC), RB))
- RS = GFMUL(RS, RA, gfdegree, modulo=RC)
- RS = GFMUL(RS, RA, gfdegree=RB, modulo=RC)
-| 0.5|6.10|11.15|16.20|21.25| 26..30 |31|
-| -- | -- | --- | --- | --- | ------- |--|
-| NN | RS | RA | deg | RC | 00 011 |Rc|
-| NN | RS | RA | RB | RC | 11 011 |Rc|
+## Multiply
+
+with the modulo and degree being in an SPR, multiply can be identical
+equivalent to standard integer add
-where the SimpleV variant may override RS-as-src differently from RS-as-dest
+ RS = GFMUL(RA, RB)
+
+| 0.5|6.10|11.15|16.20|21.25| 26..30 |31|
+| -- | -- | --- | --- | --- | ------ |--|
+| NN | RT | RA | RB |11000| 01110 |Rc|
```
from functools import reduce
+def gf_degree(a) :
+ res = 0
+ a >>= 1
+ while (a != 0) :
+ a >>= 1;
+ res += 1;
+ return res
+
# constants used in the multGF2 function
mask1 = mask2 = polyred = None
-def setGF2(degree, irPoly):
+def setGF2(irPoly):
"""Define parameters of binary finite field GF(2^m)/g(x)
- - degree: extension degree of binary field
- irPoly: coefficients of irreducible polynomial g(x)
"""
+ # degree: extension degree of binary field
+ degree = gf_degree(irPoly)
+
def i2P(sInt):
"""Convert an integer into a polynomial"""
return [(sInt >> i) & 1
"""Multiply two polynomials in GF(2^m)/g(x)"""
p = 0
while p2:
+ # standard long-multiplication: check LSB and add
if p2 & 1:
p ^= p1
p1 <<= 1
+ # standard modulo: check MSB and add polynomial
if p1 & mask1:
p1 ^= polyred
p2 >>= 1
if __name__ == "__main__":
# Define binary field GF(2^3)/x^3 + x + 1
- setGF2(3, 0b1011)
+ setGF2(0b1011) # degree 3
# Evaluate the product (x^2 + x + 1)(x^2 + 1)
print("{:02x}".format(multGF2(0b111, 0b101)))
# Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
# (used in the Advanced Encryption Standard-AES)
- setGF2(8, 0b100011011)
+ setGF2(0b100011011) # degree 8
# Evaluate the product (x^7)(x^7 + x + 1)
print("{:02x}".format(multGF2(0b10000000, 0b10000011)))
```
-## GF add
- RS = GFADDI(RS, RA|0, gfdegree, modulo=RC)
- RS = GFADD(RS, RA|0, gfdegree=RB, modulo=RC)
+## GF(2^M) Inverse
-| 0.5|6.10|11.15|16.20|21.25| 26..30 |31| name |
-| -- | -- | --- | --- | --- | ------- |--| ----- |
-| NN | RS | RA | deg | RC | 0 1 011 |Rc| gfaddi |
-| NN | RS | RA | RB | RC | 1 1 111 |Rc| gfadd |
+```
+# https://bugs.libre-soc.org/show_bug.cgi?id=782#c33
+# https://ftp.libre-soc.org/ARITH18_Kobayashi.pdf
+def gf_invert(a) :
+
+ s = getGF2() # get the full polynomial (including the MSB)
+ r = a
+ v = 0
+ u = 1
+ j = 0
-GFMOD is a pseudo-op where RA=0
+ for i in range(1, 2*degree+1):
+ # could use count-trailing-1s here to skip ahead
+ if r & mask1: # test MSB of r
+ if s & mask1: # test MSB of s
+ s ^= r
+ v ^= u
+ s <<= 1 # shift left 1
+ if j == 0:
+ r, s = s, r # swap r,s
+ u, v = v<<1, u # shift v and swap
+ j = 1
+ else:
+ u >>= 1 # right shift left
+ j -= 1
+ else:
+ r <<= 1 # shift left 1
+ u <<= 1 # shift left 1
+ j += 1
-## gf invert
+ return u
+```
+
+# GF2 (Carryless)
+
+## GF2 (carryless) div and mod
```
def gf_degree(a) :
res += 1;
return res
-def gf_invert(a, mod=0x1B) :
- v = mod
- g1 = 1
- g2 = 0
- j = gf_degree(a) - 8
-
- while (a != 1) :
- if (j < 0) :
- a, v = v, a
- g1, g2 = g2, g1
- j = -j
+def FullDivision(self, f, v):
+ """
+ Takes two arguments, f, v
+ fDegree and vDegree are the degrees of the field elements
+ f and v represented as a polynomials.
+ This method returns the field elements a and b such that
- a ^= v << j
- g1 ^= g2 << j
+ f(x) = a(x) * v(x) + b(x).
- a %= 256 # Emulating 8-bit overflow
- g1 %= 256 # Emulating 8-bit overflow
+ That is, a is the divisor and b is the remainder, or in
+ other words a is like floor(f/v) and b is like f modulo v.
+ """
- j = gf_degree(a) - gf_degree(v)
-
- return g1
+ fDegree, vDegree = gf_degree(f), gf_degree(v)
+ res, rem = 0, f
+ for i in reversed(range(vDegree, fDegree+1):
+ if ((rem >> i) & 1): # check bit
+ res ^= (1 << (i - vDegree))
+ rem ^= ( v << (i - vDegree)))
+ return (res, rem)
```
-## carryless mul
+| 0.5|6.10|11.15|16.20| 21 | 22.23 | 24....30 |31| name |
+| -- | -- | --- | --- | -- | ----- | -------- |--| ---- |
+| NN | RT | RA | RB | 1 | 00 | 0001 110 |Rc| cldiv |
+| NN | RT | RA | RB | 1 | 01 | 0001 110 |Rc| clmod |
+
+## GF2 carryless mul
based on RV bitmanip
-see https://en.wikipedia.org/wiki/CLMUL_instruction_set
+see <https://en.wikipedia.org/wiki/CLMUL_instruction_set> and
+<https://www.felixcloutier.com/x86/pclmulqdq> and
+<https://en.m.wikipedia.org/wiki/Carry-less_product>
these are GF2 operations with the modulo set to 2^degree.
they are worth adding as their own non-overwrite operations
projects / libreriscv.git / blobdiff