[[!tag standards]]
+[[!toc levels=1]]
+
# Implementation Log
* ternlogi <https://bugs.libre-soc.org/show_bug.cgi?id=745>
* grev <https://bugs.libre-soc.org/show_bug.cgi?id=755>
* GF2^M <https://bugs.libre-soc.org/show_bug.cgi?id=782>
+
# bitmanipulation
**DRAFT STATUS**
-pseudocode: <https://libre-soc.org/openpower/isa/bitmanip/>
+pseudocode: [[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]].
| NN | RT | RA | RB | im0-4 | im5-7 00 |1 | grevlog |
| NN | | | | | ..... 01 |0 | crternlog |
| NN | RT | RA | RB | RC | mode 010 |Rc| bitmask* |
-| NN | RS | RA | RB | RC | 00 011 |0 | gfbmadd |
-| NN | RS | RA | RB | RC | 00 011 |1 | gfbmaddsub |
-| NN | RS | RA | RB | RC | 01 011 |0 | clmadd |
-| NN | RS | RA | RB | RC | 01 011 |1 | clmaddsub |
-| NN | RS | RA | RB | RC | 10 011 |0 | gfpmadd |
-| NN | RS | RA | RB | RC | 10 011 |1 | gfpmaddsub |
-| NN | RS | RA | RB | RC | 11 011 | | rsvd |
+| NN | | | | | 00 011 | | rsvd |
+| NN | | | | | 01 011 | | rsvd |
+| NN | | | | | 10 011 | | rsvd |
+| NN | | | | | 11 011 |Rc| setvl |
| NN | RT | RA | RB | sh0-4 | sh5 1 111 |Rc| bmrevi |
ops (note that av avg and abs as well as vec scalar mask
| 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 | 11 | 0001 110 |Rc| vec cprop |
+| NN | RT | RA | RB | 0 | | 0101 110 |Rc| rsvd |
| NN | RT | RA | RB | 1 | itype | 0101 110 |Rc| xperm |
-| NN | RA | RB | RC | 0 | itype | 0101 110 |Rc| av minmax |
-| NN | RA | RB | RC | 1 | 00 | 0101 110 |Rc| av abss |
-| NN | RA | RB | RC | 1 | 01 | 0101 110 |Rc| av absu|
-| NN | RA | RB | | 1 | 10 | 0101 110 |Rc| av avgadd |
-| NN | RA | RB | | 1 | 11 | 0101 110 |Rc| rsvd |
-| NN | RA | RB | | | | 1001 110 |Rc| rsvd |
+| NN | RA | RB | RC | 0 | itype | 1001 110 |Rc| av minmax |
+| NN | RA | RB | RC | 1 | 00 | 1001 110 |Rc| av abss |
+| NN | RA | RB | RC | 1 | 01 | 1001 110 |Rc| av absu|
+| NN | RA | RB | | 1 | 10 | 1001 110 |Rc| av avgadd |
+| NN | RA | RB | | 1 | 11 | 1001 110 |Rc| rsvd |
| NN | RA | RB | | | | 1101 110 |Rc| rsvd |
| NN | RA | RB | RC | 0 | 00 | 0010 110 |Rc| gorc |
| NN | RA | RB | sh | SH | 00 | 1010 110 |Rc| gorci |
| NN | RA | RB | RC | | 10 | --10 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 |
+| NN | | | | | | --11 110 |Rc| rsvd |
# ternlog bitops
}
```
-# Introductory Explanation for Carry-less and Galois Field arithmetic
+# Introduction to Carry-less and GF arithmetic
+
+* obligatory xkcd <https://xkcd.com/2595/>
There are three completely separate types of Galois-Field-based
arithmetic that we implement which are not well explained even in introductory literature. A slightly oversimplified explanation
is followed by more accurate descriptions:
-* carry-less binary arithmetic. this is not actually a Galois Field,
+* `GF(2)` carry-less binary arithmetic. this is not actually a Galois Field,
but is accidentally referred to as GF(2) - see below as to why.
-* modulo arithmetic with a Prime number, these are "proper" Galois Fields
-* modulo arithmetic with two limits: a power-of-2 (2^N) and a second
- "reducing" polynomial (similar to a prime number)
+* `GF(p)` modulo arithmetic with a Prime number, these are "proper" Galois Fields
+* `GF(2^N)` carry-less binary arithmetic with two limits: modulo a power-of-2
+ (2^N) and a second "reducing" polynomial (similar to a prime number), these
+ are said to be GF(2^N) arithmetic.
further detailed and more precise explanations are provided below
-## Polynomials with coefficients in `GF(2)`
-
-(aka. Carry-less arithmetic -- the `cl*` instructions).
-
-This isn't actually a Galois Field, but its coefficients are. This is
-basically binary integer addition, subtraction, and multiplication like
-usual, except that carries aren't propagated at all, effectively turning
-both addition and subtraction into the bitwise xor operation. Division and
-remainder are defined to match how addition and multiplication works.
-
-## Galois Fields with a prime size
-
-aka. `GF(p)` or Prime Galois Fields (the `gfp*` instructions).
-This is basically just the integers mod `p`.
-
-## Galois Fields with a power-of-a-prime size
-
-aka. `GF(p^n)` or `GF(q)` where `q == p^n` for prime `p` and integer `n > 0`.
-
-We only implement these for `p == 2`, called Binary Galois Fields
-(`GF(2^n)` -- the `gfb*` instructions).
-For any prime `p`, `GF(p^n)` is implemented as polynomials with
-coefficients in `GF(p)` and degree `< n`, where the polynomials are the
-remainders of dividing by a specificly chosen polynomial in `GF(p)` called
-the Reducing Polynomial (we will denote that by `red_poly`). The Reducing
-Polynomial must be an irreducable polynomial (like primes, but for
-polynomials), as well as have degree `n`. All `GF(p^n)` for the same `p`
-and `n` are isomorphic to each other -- the choice of `red_poly` doesn't
-affect `GF(p^n)`'s mathematical shape, all that changes is the specific
-polynomials used to implement `GF(p^n)`.
+* **Polynomials with coefficients in `GF(2)`**
+ (aka. Carry-less arithmetic -- the `cl*` instructions).
+ This isn't actually a Galois Field, but its coefficients are. This is
+ basically binary integer addition, subtraction, and multiplication like
+ usual, except that carries aren't propagated at all, effectively turning
+ both addition and subtraction into the bitwise xor operation. Division and
+ remainder are defined to match how addition and multiplication works.
+* **Galois Fields with a prime size**
+ (aka. `GF(p)` or Prime Galois Fields -- the `gfp*` instructions).
+ This is basically just the integers mod `p`.
+* **Galois Fields with a power-of-a-prime size**
+ (aka. `GF(p^n)` or `GF(q)` where `q == p^n` for prime `p` and
+ integer `n > 0`).
+ We only implement these for `p == 2`, called Binary Galois Fields
+ (`GF(2^n)` -- the `gfb*` instructions).
+ For any prime `p`, `GF(p^n)` is implemented as polynomials with
+ coefficients in `GF(p)` and degree `< n`, where the polynomials are the
+ remainders of dividing by a specificly chosen polynomial in `GF(p)` called
+ the Reducing Polynomial (we will denote that by `red_poly`). The Reducing
+ Polynomial must be an irreducable polynomial (like primes, but for
+ polynomials), as well as have degree `n`. All `GF(p^n)` for the same `p`
+ and `n` are isomorphic to each other -- the choice of `red_poly` doesn't
+ affect `GF(p^n)`'s mathematical shape, all that changes is the specific
+ polynomials used to implement `GF(p^n)`.
+
+Many implementations and much of the literature do not make a clear
+distinction between these three categories, which makes it confusing
+to understand what their purpose and value is.
+
+* carry-less multiply is extremely common and is used for the ubiquitous
+ CRC32 algorithm. [TODO add many others, helps justify to ISA WG]
+* GF(2^N) forms the basis of Rijndael (the current AES standard) and
+ has significant uses throughout cryptography
+* GF(p) is the basis again of a significant quantity of algorithms
+ (TODO, list them, jacob knows what they are), even though the
+ modulo is limited to be below 64-bit (size of a scalar int)
# Instructions for Carry-less Operations
These are operations on polynomials with coefficients in `GF(2)`, with the
polynomial's coefficients packed into integers with the following algorithm:
-[[!inline pagenames="openpower/sv/bitmanip/pack_poly.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/pack_poly.py" raw="yes"]]
+```
## Carry-less Multiply Instructions
### `clmul` Carry-less Multiply
-[[!inline pagenames="openpower/sv/bitmanip/clmul.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/clmul.py" raw="yes"]]
+```
### `clmulh` Carry-less Multiply High
-[[!inline pagenames="openpower/sv/bitmanip/clmulh.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/clmulh.py" raw="yes"]]
+```
### `clmulr` Carry-less Multiply (Reversed)
Useful for CRCs. Equivalent to bit-reversing the result of `clmul` on
bit-reversed inputs.
-[[!inline pagenames="openpower/sv/bitmanip/clmulr.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/clmulr.py" raw="yes"]]
+```
## `clmadd` Carry-less Multiply-Add
`cldivrem` isn't an actual instruction, but is just used in the pseudo-code
for other instructions.
-[[!inline pagenames="openpower/sv/bitmanip/cldivrem.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/cldivrem.py" raw="yes"]]
+```
## `cldiv` Carry-less Division
making it reducible, making whatever we're working on no longer a Field.
Therefore, we can reuse the LSB to indicate `degree == XLEN`.
-[[!inline pagenames="openpower/sv/bitmanip/decode_reducing_polynomial.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/decode_reducing_polynomial.py" raw="yes"]]
+```
## `gfbredpoly` -- Set the Reducing Polynomial SPR `GFBREDPOLY`
unless this is an immediate op, `mtspr` is completely sufficient.
-[[!inline pagenames="openpower/sv/bitmanip/gfbredpoly.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfbredpoly.py" raw="yes"]]
+```
## `gfbmul` -- Binary Galois Field `GF(2^m)` Multiplication
gfbmul RT, RA, RB
```
-[[!inline pagenames="openpower/sv/bitmanip/gfbmul.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfbmul.py" raw="yes"]]
+```
## `gfbmadd` -- Binary Galois Field `GF(2^m)` Multiply-Add
gfbmadd RT, RA, RB, RC
```
-[[!inline pagenames="openpower/sv/bitmanip/gfbmadd.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfbmadd.py" raw="yes"]]
+```
## `gfbtmadd` -- Binary Galois Field `GF(2^m)` Twin Multiply-Add (for FFT)
gfbinv RT, RA
```
-[[!inline pagenames="openpower/sv/bitmanip/gfbinv.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfbinv.py" raw="yes"]]
+```
# Instructions for Prime Galois Fields `GF(p)`
gfpadd RT, RA, RB
```
-[[!inline pagenames="openpower/sv/bitmanip/gfpadd.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfpadd.py" raw="yes"]]
+```
the addition happens on infinite-precision integers
gfpsub RT, RA, RB
```
-[[!inline pagenames="openpower/sv/bitmanip/gfpsub.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfpsub.py" raw="yes"]]
+```
the subtraction happens on infinite-precision integers
gfpmul RT, RA, RB
```
-[[!inline pagenames="openpower/sv/bitmanip/gfpmul.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfpmul.py" raw="yes"]]
+```
the multiplication happens on infinite-precision integers
Some potential hardware implementations are found in:
<https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.5233&rep=rep1&type=pdf>
-[[!inline pagenames="openpower/sv/bitmanip/gfpinv.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfpinv.py" raw="yes"]]
+```
## `gfpmadd` Prime Galois Field `GF(p)` Multiply-Add
gfpmadd RT, RA, RB, RC
```
-[[!inline pagenames="openpower/sv/bitmanip/gfpmadd.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfpmadd.py" raw="yes"]]
+```
the multiplication and addition happens on infinite-precision integers
gfpmsub RT, RA, RB, RC
```
-[[!inline pagenames="openpower/sv/bitmanip/gfpmsub.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfpmsub.py" raw="yes"]]
+```
the multiplication and subtraction happens on infinite-precision integers
gfpmsubr RT, RA, RB, RC
```
-[[!inline pagenames="openpower/sv/bitmanip/gfpmsubr.py" raw="true" feeds="no" actions="yes"]]
+```python
+[[!inline pagenames="gf_reference/gfpmsubr.py" raw="yes"]]
+```
the multiplication and subtraction happens on infinite-precision integers
## bit deposit
-vpdepd VRT,VRA,VRB, identical to RV bitmamip bdep, found already in v3.1 p106
+pdepd VRT,VRA,VRB, identical to RV bitmamip bdep, found already in v3.1 p106
do while(m < 64)
if VSR[VRB+32].dword[i].bit[63-m]=1 then do
```
-# bit extract
+## bit extract
-other way round: identical to RV bext, found in v3.1 p196
+other way round: identical to RV bext: pextd, found in v3.1 p196
```
uint_xlen_t bext(uint_xlen_t RA, uint_xlen_t RB)
}
```
-# centrifuge
+## centrifuge
found in v3.1 p106 so not to be added here
RA = result
```
-# bit to byte permute
+## bit to byte permute
similar to matrix permute in RV bitmanip, which has XOR and OR variants,
-these perform a transpose.
+these perform a transpose. TODO this looks VSX is there a scalar variant
+in v3.0/1 already
do j = 0 to 7
do k = 0 to 7
b = VSR[VRB+32].dword[i].byte[k].bit[j]
VSR[VRT+32].dword[i].byte[j].bit[k] = b
+# Appendix
+
+see [[bitmanip/appendix]]
+
projects / libreriscv.git / blobdiff