5 * ternlogi <https://bugs.libre-soc.org/show_bug.cgi?id=745>
6 * grev <https://bugs.libre-soc.org/show_bug.cgi?id=755>
7 * GF2^M <https://bugs.libre-soc.org/show_bug.cgi?id=782>
13 pseudocode: <https://libre-soc.org/openpower/isa/bitmanip/>
15 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.
16 Vectorisation Context is provided by [[openpower/sv]].
18 When combined with SV, scalar variants of bitmanip operations found in VSX are added so that VSX may be retired as "legacy" in the far future (10 to 20 years). Also, VSX is hundreds of opcodes, requires 128 bit pathways, and is wholly unsuited to low power or embedded scenarios.
20 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.
22 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.
24 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
25 the [[sv/av_opcodes]] as well as [[sv/setvl]]
29 * <https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders>
30 * <https://maths-people.anu.edu.au/~brent/pd/rpb232tr.pdf>
34 two major opcodes are needed
36 ternlog has its own major opcode
39 | ------ |--| --------- |
44 2nd major opcode for other bitmanip: minor opcode allocation
47 | ------ |--| --------- |
52 | 011 | | gf/cl madd* |
59 | dest | src1 | subop | op |
60 | ---- | ---- | ----- | -------- |
61 | RT | RA | .. | bmatflip |
65 | dest | src1 | src2 | subop | op |
66 | ---- | ---- | ---- | ----- | -------- |
67 | RT | RA | RB | or | bmatflip |
68 | RT | RA | RB | xor | bmatflip |
69 | RT | RA | RB | | grev |
70 | RT | RA | RB | | clmul* |
71 | RT | RA | RB | | gorc |
72 | RT | RA | RB | shuf | shuffle |
73 | RT | RA | RB | unshuf| shuffle |
74 | RT | RA | RB | width | xperm |
75 | RT | RA | RB | type | minmax |
76 | RT | RA | RB | | av abs avgadd |
77 | RT | RA | RB | type | vmask ops |
86 TODO: convert all instructions to use RT and not RS
88 | 0.5|6.8 | 9.11|12.14|15.17|18.20|21.28 | 29.30|31|name|
89 | -- | -- | --- | --- | --- |-----|----- | -----|--|----|
90 | NN | BT | BA | BB | BC |m0-2 | imm | 10 |m3|crternlog|
92 | 0.5|6.10|11.15|16.20 |21..25 | 26....30 |31| name |
93 | -- | -- | --- | --- | ----- | -------- |--| ------ |
94 | NN | RT | RA |itype/| im0-4 | im5-7 00 |0 | xpermi |
95 | NN | RT | RA | RB | im0-4 | im5-7 00 |1 | grevlog |
96 | NN | | | | | ..... 01 |0 | crternlog |
97 | NN | RT | RA | RB | RC | mode 010 |Rc| bitmask* |
98 | NN | RS | RA | RB | RC | 00 011 |0 | gfbmadd |
99 | NN | RS | RA | RB | RC | 00 011 |1 | gfbmaddsub |
100 | NN | RS | RA | RB | RC | 01 011 |0 | clmadd |
101 | NN | RS | RA | RB | RC | 01 011 |1 | clmaddsub |
102 | NN | RS | RA | RB | RC | 10 011 |0 | gfpmadd |
103 | NN | RS | RA | RB | RC | 10 011 |1 | gfpmaddsub |
104 | NN | RS | RA | RB | RC | 11 011 | | rsvd |
105 | NN | RT | RA | RB | sh0-4 | sh5 1 111 |Rc| bmrevi |
107 ops (note that av avg and abs as well as vec scalar mask
108 are included here [[sv/vector_ops]], and
109 the [[sv/av_opcodes]])
111 TODO: convert from RA, RB, and RC to correct field names of RT, RA, and RB, and
112 double check that instructions didn't need 3 inputs.
114 | 0.5|6.10|11.15|16.20| 21 | 22.23 | 24....30 |31| name |
115 | -- | -- | --- | --- | -- | ----- | -------- |--| ---- |
116 | NN | RS | me | sh | SH | ME 0 | nn00 110 |Rc| bmopsi |
117 | NN | RS | RB | sh | SH | / 1 | nn00 110 |Rc| bmopsi |
118 | NN | RT | RA | RB | 1 | 00 | 0001 110 |Rc| cldiv |
119 | NN | RT | RA | RB | 1 | 01 | 0001 110 |Rc| clmod |
120 | NN | RT | RA | RB | 1 | 10 | 0001 110 |Rc| |
121 | NN | RT | RB | RB | 1 | 11 | 0001 110 |Rc| clinv |
122 | NN | RA | RB | RC | 0 | 00 | 0001 110 |Rc| vec sbfm |
123 | NN | RA | RB | RC | 0 | 01 | 0001 110 |Rc| vec sofm |
124 | NN | RA | RB | RC | 0 | 10 | 0001 110 |Rc| vec sifm |
125 | NN | RA | RB | RC | 0 | 11 | 0001 110 |Rc| vec cprop |
126 | NN | RT | RA | RB | 1 | itype | 0101 110 |Rc| xperm |
127 | NN | RA | RB | RC | 0 | itype | 0101 110 |Rc| minmax |
128 | NN | RA | RB | RC | 1 | 00 | 0101 110 |Rc| av abss |
129 | NN | RA | RB | RC | 1 | 01 | 0101 110 |Rc| av absu|
130 | NN | RA | RB | | 1 | 10 | 0101 110 |Rc| avg add |
131 | NN | RA | RB | | 1 | 11 | 0101 110 |Rc| rsvd |
132 | NN | RA | RB | | | | 1001 110 |Rc| rsvd |
133 | NN | RA | RB | | | | 1101 110 |Rc| rsvd |
134 | NN | RA | RB | RC | 0 | 00 | 0010 110 |Rc| gorc |
135 | NN | RA | RB | sh | SH | 00 | 1010 110 |Rc| gorci |
136 | NN | RA | RB | RC | 0 | 00 | 0110 110 |Rc| gorcw |
137 | NN | RA | RB | sh | 0 | 00 | 1110 110 |Rc| gorcwi |
138 | NN | RA | RB | RC | 1 | 00 | 1110 110 |Rc| bmator |
139 | NN | RA | RB | RC | 0 | 01 | 0010 110 |Rc| grev |
140 | NN | RA | RB | RC | 1 | 01 | 0010 110 |Rc| clmul |
141 | NN | RA | RB | sh | SH | 01 | 1010 110 |Rc| grevi |
142 | NN | RA | RB | RC | 0 | 01 | 0110 110 |Rc| grevw |
143 | NN | RA | RB | sh | 0 | 01 | 1110 110 |Rc| grevwi |
144 | NN | RA | RB | RC | 1 | 01 | 1110 110 |Rc| bmatxor |
145 | NN | RA | RB | RC | | 10 | --10 110 |Rc| rsvd |
146 | NN | RA | RB | RC | 0 | 11 | 1110 110 |Rc| clmulr |
147 | NN | RA | RB | RC | 1 | 11 | 1110 110 |Rc| clmulh |
148 | NN | | | | | | --11 110 |Rc| setvl |
152 Similar to FPGA LUTs: for every bit perform a lookup into a table using an 8bit immediate, or in another register.
154 Like the x86 AVX512F [vpternlogd/vpternlogq](https://www.felixcloutier.com/x86/vpternlogd:vpternlogq) instructions.
158 | 0.5|6.10|11.15|16.20| 21..28|29.30|31|
159 | -- | -- | --- | --- | ----- | --- |--|
160 | NN | RT | RA | RB | im0-7 | 00 |Rc|
163 idx = c << 2 | b << 1 | a
164 return imm[idx] # idx by LSB0 order
167 RT[i] = lut3(imm, RB[i], RA[i], RT[i])
171 also, another possible variant involving swizzle-like selection
172 and masking, this only requires 3 64 bit registers (RA, RS, RB) and
175 Note however that unless XLEN matches sz, this instruction
176 is a Read-Modify-Write: RS must be read as a second operand
177 and all unmodified bits preserved. SVP64 may provide limited
178 alternative destination for RS from RS-as-source, but again
179 all unmodified bits must still be copied.
181 | 0.5|6.10|11.15|16.20|21.28 | 29.30 |31|
182 | -- | -- | --- | --- | ---- | ----- |--|
183 | NN | RS | RA | RB |idx0-3| 01 |sz|
185 SZ = (1+sz) * 8 # 8 or 16
186 raoff = MIN(XLEN, idx0 * SZ)
187 rboff = MIN(XLEN, idx1 * SZ)
188 rcoff = MIN(XLEN, idx2 * SZ)
189 rsoff = MIN(XLEN, idx3 * SZ)
191 for i in range(MIN(XLEN, SZ)):
195 res = lut3(imm, ra, rb, rc)
200 another mode selection would be CRs not Ints.
202 | 0.5|6.8 | 9.11|12.14|15.17|18.20|21.28 | 29.30|31|
203 | -- | -- | --- | --- | --- |-----|----- | -----|--|
204 | NN | BT | BA | BB | BC |m0-2 | imm | 10 |m3|
208 if not mask[i] continue
209 crregs[BT][i] = lut3(imm,
217 signed and unsigned min/max for integer. this is sort-of partly synthesiseable in [[sv/svp64]] with pred-result as long as the dest reg is one of the sources, but not both signed and unsigned. when the dest is also one of the srces and the mv fails due to the CR bittest failing this will only overwrite the dest where the src is greater (or less).
219 signed/unsigned min/max gives more flexibility.
222 uint_xlen_t min(uint_xlen_t rs1, uint_xlen_t rs2)
223 { return (int_xlen_t)rs1 < (int_xlen_t)rs2 ? rs1 : rs2;
225 uint_xlen_t max(uint_xlen_t rs1, uint_xlen_t rs2)
226 { return (int_xlen_t)rs1 > (int_xlen_t)rs2 ? rs1 : rs2;
228 uint_xlen_t minu(uint_xlen_t rs1, uint_xlen_t rs2)
229 { return rs1 < rs2 ? rs1 : rs2;
231 uint_xlen_t maxu(uint_xlen_t rs1, uint_xlen_t rs2)
232 { return rs1 > rs2 ? rs1 : rs2;
239 based on RV bitmanip, covered by ternlog bitops
242 uint_xlen_t cmix(uint_xlen_t RA, uint_xlen_t RB, uint_xlen_t RC) {
243 return (RA & RB) | (RC & ~RB);
250 based on RV bitmanip singlebit set, instruction format similar to shift
251 [[isa/fixedshift]]. bmext is actually covered already (shift-with-mask rldicl but only immediate version).
252 however bitmask-invert is not, and set/clr are not covered, although they can use the same Shift ALU.
254 bmext (RB) version is not the same as rldicl because bmext is a right shift by RC, where rldicl is a left rotate. for the immediate version this does not matter, so a bmexti is not required.
255 bmrev however there is no direct equivalent and consequently a bmrevi is required.
257 bmset (register for mask amount) is particularly useful for creating
258 predicate masks where the length is a dynamic runtime quantity.
259 bmset(RA=0, RB=0, RC=mask) will produce a run of ones of length "mask" in a single instruction without needing to initialise or depend on any other registers.
261 | 0.5|6.10|11.15|16.20|21.25| 26..30 |31| name |
262 | -- | -- | --- | --- | --- | ------- |--| ----- |
263 | NN | RS | RA | RB | RC | mode 010 |Rc| bm* |
265 Immediate-variant is an overwrite form:
267 | 0.5|6.10|11.15|16.20| 21 | 22.23 | 24....30 |31| name |
268 | -- | -- | --- | --- | -- | ----- | -------- |--| ---- |
269 | NN | RS | RB | sh | SH | itype | 1000 110 |Rc| bm*i |
275 mask_a = ((1 << x) - 1) & ((1 << 64) - 1)
276 mask_b = ((1 << y) - 1) & ((1 << 64) - 1)
281 mask_a = ((1 << x) - 1) & ((1 << 64) - 1)
282 mask_b = (~((1 << y) - 1)) & ((1 << 64) - 1)
283 return mask_a ^ mask_b
286 uint_xlen_t bmset(RS, RB, sh)
288 int shamt = RB & (XLEN - 1);
290 return RS | (mask << shamt);
293 uint_xlen_t bmclr(RS, RB, sh)
295 int shamt = RB & (XLEN - 1);
297 return RS & ~(mask << shamt);
300 uint_xlen_t bminv(RS, RB, sh)
302 int shamt = RB & (XLEN - 1);
304 return RS ^ (mask << shamt);
307 uint_xlen_t bmext(RS, RB, sh)
309 int shamt = RB & (XLEN - 1);
311 return mask & (RS >> shamt);
315 bitmask extract with reverse. can be done by bit-order-inverting all of RB and getting bits of RB from the opposite end.
317 when RA is zero, no shift occurs. this makes bmextrev useful for
318 simply reversing all bits of a register.
322 rev[0:msb] = rb[msb:0];
325 uint_xlen_t bmextrev(RA, RB, sh)
328 if (RA != 0) shamt = (GPR(RA) & (XLEN - 1));
329 shamt = (XLEN-1)-shamt; # shift other end
330 bra = bitreverse(RB) # swap LSB-MSB
332 return mask & (bra >> shamt);
336 | 0.5|6.10|11.15|16.20|21.26| 27..30 |31| name |
337 | -- | -- | --- | --- | --- | ------- |--| ------ |
338 | NN | RT | RA | RB | sh | 1 011 |Rc| bmrevi |
343 generalised reverse combined with a pair of LUT2s and allowing
344 a constant `0b0101...0101` when RA=0, and an option to invert
345 (including when RA=0, giving a constant 0b1010...1010 as the
346 initial value) provides a wide range of instructions
347 and a means to set regular 64 bit patterns in one
350 the two LUT2s are applied left-half (when not swapping)
351 and right-half (when swapping) so as to allow a wider
354 <img src="/openpower/sv/grevlut2x2.jpg" width=700 />
356 * A value of `0b11001010` for the immediate provides
357 the functionality of a standard "grev".
358 * `0b11101110` provides gorc
360 grevlut should be arranged so as to produce the constants
361 needed to put into bext (bitextract) so as in turn to
362 be able to emulate x86 pmovmask instructions <https://www.felixcloutier.com/x86/pmovmskb>.
363 This only requires 2 instructions (grevlut, bext).
365 Note that if the mask is required to be placed
366 directly into CR Fields (for use as CR Predicate
367 masks rather than a integer mask) then sv.ori
368 may be used instead, bearing in mind that sv.ori
369 is a 64-bit instruction, and `VL` must have been
370 set to the required length:
372 sv.ori./elwid=8 r10.v, r10.v, 0
374 The following settings provide the required mask constants:
376 | RA | RB | imm | iv | result |
377 | ------- | ------- | ---------- | -- | ---------- |
378 | 0x555.. | 0b10 | 0b01101100 | 0 | 0x111111... |
379 | 0x555.. | 0b110 | 0b01101100 | 0 | 0x010101... |
380 | 0x555.. | 0b1110 | 0b01101100 | 0 | 0x00010001... |
381 | 0x555.. | 0b10 | 0b11000110 | 1 | 0x88888... |
382 | 0x555.. | 0b110 | 0b11000110 | 1 | 0x808080... |
383 | 0x555.. | 0b1110 | 0b11000110 | 1 | 0x80008000... |
385 Better diagram showing the correct ordering of shamt (RB). A LUT2
386 is applied to all locations marked in red using the first 4
387 bits of the immediate, and a separate LUT2 applied to all
388 locations in green using the upper 4 bits of the immediate.
390 <img src="/openpower/sv/grevlut.png" width=700 />
392 demo code [[openpower/sv/grevlut.py]]
397 return imm[idx] # idx by LSB0 order
399 dorow(imm8, step_i, chunksize):
401 if (j&chunk_size) == 0
405 step_o[j] = lut2(imm, step_i[j], step_i[j ^ chunk_size])
408 uint64_t grevlut64(uint64_t RA, uint64_t RB, uint8 imm, bool iv)
410 uint64_t x = 0x5555_5555_5555_5555;
411 if (RA != 0) x = GPR(RA);
416 if (shamt & step) x = dorow(imm, x, step)
422 | 0.5|6.10|11.15|16.20 |21..25 | 26....30 |31| name |
423 | -- | -- | --- | --- | ----- | -------- |--| ------ |
424 | NN | RT | RA | s0-4 | im0-4 | im5-7 1 iv |s5| grevlogi |
425 | NN | RT | RA | RB | im0-4 | im5-7 00 |1 | grevlog |
430 based on RV bitmanip, this is also known as a butterfly network. however
431 where a butterfly network allows setting of every crossbar setting in
432 every row and every column, generalised-reverse (grev) only allows
433 a per-row decision: every entry in the same row must either switch or
436 <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/8/8c/Butterfly_Network.jpg/474px-Butterfly_Network.jpg" />
439 uint64_t grev64(uint64_t RA, uint64_t RB)
443 if (shamt & 1) x = ((x & 0x5555555555555555LL) << 1) |
444 ((x & 0xAAAAAAAAAAAAAAAALL) >> 1);
445 if (shamt & 2) x = ((x & 0x3333333333333333LL) << 2) |
446 ((x & 0xCCCCCCCCCCCCCCCCLL) >> 2);
447 if (shamt & 4) x = ((x & 0x0F0F0F0F0F0F0F0FLL) << 4) |
448 ((x & 0xF0F0F0F0F0F0F0F0LL) >> 4);
449 if (shamt & 8) x = ((x & 0x00FF00FF00FF00FFLL) << 8) |
450 ((x & 0xFF00FF00FF00FF00LL) >> 8);
451 if (shamt & 16) x = ((x & 0x0000FFFF0000FFFFLL) << 16) |
452 ((x & 0xFFFF0000FFFF0000LL) >> 16);
453 if (shamt & 32) x = ((x & 0x00000000FFFFFFFFLL) << 32) |
454 ((x & 0xFFFFFFFF00000000LL) >> 32);
462 based on RV bitmanip.
464 RA contains a vector of indices to select parts of RB to be
465 copied to RT. The immediate-variant allows up to an 8 bit
466 pattern (repeated) to be targetted at different parts of RT
469 uint_xlen_t xpermi(uint8_t imm8, uint_xlen_t RB, int sz_log2)
472 uint_xlen_t sz = 1LL << sz_log2;
473 uint_xlen_t mask = (1LL << sz) - 1;
474 uint_xlen_t RA = imm8 | imm8<<8 | ... | imm8<<56;
475 for (int i = 0; i < XLEN; i += sz) {
476 uint_xlen_t pos = ((RA >> i) & mask) << sz_log2;
478 r |= ((RB >> pos) & mask) << i;
482 uint_xlen_t xperm(uint_xlen_t RA, uint_xlen_t RB, int sz_log2)
485 uint_xlen_t sz = 1LL << sz_log2;
486 uint_xlen_t mask = (1LL << sz) - 1;
487 for (int i = 0; i < XLEN; i += sz) {
488 uint_xlen_t pos = ((RA >> i) & mask) << sz_log2;
490 r |= ((RB >> pos) & mask) << i;
494 uint_xlen_t xperm_n (uint_xlen_t RA, uint_xlen_t RB)
495 { return xperm(RA, RB, 2); }
496 uint_xlen_t xperm_b (uint_xlen_t RA, uint_xlen_t RB)
497 { return xperm(RA, RB, 3); }
498 uint_xlen_t xperm_h (uint_xlen_t RA, uint_xlen_t RB)
499 { return xperm(RA, RB, 4); }
500 uint_xlen_t xperm_w (uint_xlen_t RA, uint_xlen_t RB)
501 { return xperm(RA, RB, 5); }
509 uint32_t gorc32(uint32_t RA, uint32_t RB)
513 if (shamt & 1) x |= ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
514 if (shamt & 2) x |= ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
515 if (shamt & 4) x |= ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
516 if (shamt & 8) x |= ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
517 if (shamt & 16) x |= ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
520 uint64_t gorc64(uint64_t RA, uint64_t RB)
524 if (shamt & 1) x |= ((x & 0x5555555555555555LL) << 1) |
525 ((x & 0xAAAAAAAAAAAAAAAALL) >> 1);
526 if (shamt & 2) x |= ((x & 0x3333333333333333LL) << 2) |
527 ((x & 0xCCCCCCCCCCCCCCCCLL) >> 2);
528 if (shamt & 4) x |= ((x & 0x0F0F0F0F0F0F0F0FLL) << 4) |
529 ((x & 0xF0F0F0F0F0F0F0F0LL) >> 4);
530 if (shamt & 8) x |= ((x & 0x00FF00FF00FF00FFLL) << 8) |
531 ((x & 0xFF00FF00FF00FF00LL) >> 8);
532 if (shamt & 16) x |= ((x & 0x0000FFFF0000FFFFLL) << 16) |
533 ((x & 0xFFFF0000FFFF0000LL) >> 16);
534 if (shamt & 32) x |= ((x & 0x00000000FFFFFFFFLL) << 32) |
535 ((x & 0xFFFFFFFF00000000LL) >> 32);
541 # Instructions for Carry-less Operations aka. Polynomials with coefficients in `GF(2)`
543 Carry-less addition/subtraction is simply XOR, so a `cladd`
544 instruction is not provided since the `xor[i]` instruction can be used instead.
546 These are operations on polynomials with coefficients in `GF(2)`, with the
547 polynomial's coefficients packed into integers with the following algorithm:
549 [[!inline pagenames="openpower/sv/bitmanip/pack_poly.py" raw="true" feeds="no" actions="yes"]]
551 ## Carry-less Multiply Instructions
554 see <https://en.wikipedia.org/wiki/CLMUL_instruction_set> and
555 <https://www.felixcloutier.com/x86/pclmulqdq> and
556 <https://en.m.wikipedia.org/wiki/Carry-less_product>
558 They are worth adding as their own non-overwrite operations
559 (in the same pipeline).
561 ### `clmul` Carry-less Multiply
563 [[!inline pagenames="openpower/sv/bitmanip/clmul.py" raw="true" feeds="no" actions="yes"]]
565 ### `clmulh` Carry-less Multiply High
567 [[!inline pagenames="openpower/sv/bitmanip/clmulh.py" raw="true" feeds="no" actions="yes"]]
569 ### `clmulr` Carry-less Multiply (Reversed)
571 Useful for CRCs. Equivalent to bit-reversing the result of `clmul` on
574 [[!inline pagenames="openpower/sv/bitmanip/clmulr.py" raw="true" feeds="no" actions="yes"]]
576 ## `clmadd` Carry-less Multiply-Add
579 clmadd RT, RA, RB, RC
583 (RT) = clmul((RA), (RB)) ^ (RC)
586 ## `cltmadd` Twin Carry-less Multiply-Add (for FFTs)
589 cltmadd RT, RA, RB, RC
592 TODO: add link to explanation for where `RS` comes from.
595 (RT) = RC ^ clmul((RA), (RB))
599 ## `cldivrem` Carry-less Division and Remainder
601 `cldivrem` isn't an actual instruction, but is just used in the pseudo-code
602 for other instructions.
604 [[!inline pagenames="openpower/sv/bitmanip/cldivrem.py" raw="true" feeds="no" actions="yes"]]
606 ## `cldiv` Carry-less Division
615 q, r = cldivrem(n, d, width=XLEN)
619 ## `clrem` Carry-less Remainder
628 q, r = cldivrem(n, d, width=XLEN)
632 # Instructions for Binary Galois Fields `GF(2^m)`
636 * <https://courses.csail.mit.edu/6.857/2016/files/ffield.py>
637 * <https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture7.pdf>
638 * <https://foss.heptapod.net/math/libgf2/-/blob/branch/default/src/libgf2/gf2.py>
640 Binary Galois Field addition/subtraction is simply XOR, so a `gfbadd`
641 instruction is not provided since the `xor[i]` instruction can be used instead.
643 ## `GFBREDPOLY` SPR -- Reducing Polynomial
645 In order to save registers and to make operations orthogonal with standard
646 arithmetic, the reducing polynomial is stored in a dedicated SPR `GFBREDPOLY`.
647 This also allows hardware to pre-compute useful parameters (such as the
648 degree, or look-up tables) based on the reducing polynomial, and store them
649 alongside the SPR in hidden registers, only recomputing them whenever the SPR
650 is written to, rather than having to recompute those values for every
653 Because Galois Fields require the reducing polynomial to be an irreducible
654 polynomial, that guarantees that any polynomial of `degree > 1` must have
655 the LSB set, since otherwise it would be divisible by the polynomial `x`,
656 making it reducible, making whatever we're working on no longer a Field.
657 Therefore, we can reuse the LSB to indicate `degree == XLEN`.
659 [[!inline pagenames="openpower/sv/bitmanip/decode_reducing_polynomial.py" raw="true" feeds="no" actions="yes"]]
661 ## `gfbredpoly` -- Set the Reducing Polynomial SPR `GFBREDPOLY`
663 unless this is an immediate op, `mtspr` is completely sufficient.
665 [[!inline pagenames="openpower/sv/bitmanip/gfbredpoly.py" raw="true" feeds="no" actions="yes"]]
667 ## `gfbmul` -- Binary Galois Field `GF(2^m)` Multiplication
673 [[!inline pagenames="openpower/sv/bitmanip/gfbmul.py" raw="true" feeds="no" actions="yes"]]
675 ## `gfbmadd` -- Binary Galois Field `GF(2^m)` Multiply-Add
678 gfbmadd RT, RA, RB, RC
681 [[!inline pagenames="openpower/sv/bitmanip/gfbmadd.py" raw="true" feeds="no" actions="yes"]]
683 ## `gfbtmadd` -- Binary Galois Field `GF(2^m)` Twin Multiply-Add (for FFT)
686 gfbtmadd RT, RA, RB, RC
689 TODO: add link to explanation for where `RS` comes from.
692 (RT) = gfbmadd((RA), (RB), (RC))
696 ## `gfbinv` -- Binary Galois Field `GF(2^m)` Inverse
702 [[!inline pagenames="openpower/sv/bitmanip/gfbinv.py" raw="true" feeds="no" actions="yes"]]
704 # Instructions for Prime Galois Fields `GF(p)`
709 def int_to_gfp(int_value, prime):
710 return int_value % prime # follows Python remainder semantics
713 ## `GFPRIME` SPR -- Prime Modulus For `gfp*` Instructions
715 ## `gfpadd` Prime Galois Field `GF(p)` Addition
722 (RT) = int_to_gfp((RA) + (RB), GFPRIME)
725 the addition happens on infinite-precision integers
727 ## `gfpsub` Prime Galois Field `GF(p)` Subtraction
734 (RT) = int_to_gfp((RA) - (RB), GFPRIME)
737 the subtraction happens on infinite-precision integers
739 ## `gfpmul` Prime Galois Field `GF(p)` Multiplication
746 (RT) = int_to_gfp((RA) * (RB), GFPRIME)
749 the multiplication happens on infinite-precision integers
751 ## `gfpinv` Prime Galois Field `GF(p)` Invert
757 Some potential hardware implementations are found in:
758 <https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.5233&rep=rep1&type=pdf>
761 (RT) = gfpinv((RA), GFPRIME)
764 the multiplication happens on infinite-precision integers
766 ## `gfpmadd` Prime Galois Field `GF(p)` Multiply-Add
769 gfpmadd RT, RA, RB, RC
773 (RT) = int_to_gfp((RA) * (RB) + (RC), GFPRIME)
776 the multiplication and addition happens on infinite-precision integers
778 ## `gfpmsub` Prime Galois Field `GF(p)` Multiply-Subtract
781 gfpmsub RT, RA, RB, RC
785 (RT) = int_to_gfp((RA) * (RB) - (RC), GFPRIME)
788 the multiplication and subtraction happens on infinite-precision integers
790 ## `gfpmsubr` Prime Galois Field `GF(p)` Multiply-Subtract-Reversed
793 gfpmsubr RT, RA, RB, RC
797 (RT) = int_to_gfp((RC) - (RA) * (RB), GFPRIME)
800 the multiplication and subtraction happens on infinite-precision integers
802 ## `gfpmaddsubr` Prime Galois Field `GF(p)` Multiply-Add and Multiply-Sub-Reversed (for FFT)
805 gfpmaddsubr RT, RA, RB, RC
808 TODO: add link to explanation for where `RS` comes from.
811 product = (RA) * (RB)
813 (RT) = int_to_gfp(product + term, GFPRIME)
814 (RS) = int_to_gfp(term - product, GFPRIME)
817 the multiplication, addition, and subtraction happens on infinite-precision integers
819 ## Twin Butterfly (Tukey-Cooley) Mul-add-sub
821 used in combination with SV FFT REMAP to perform
822 a full NTT in-place. possible by having 3-in 2-out,
823 to avoid the need for a temp register. RS is written
826 gffmadd RT,RA,RC,RB (Rc=0)
827 gffmadd. RT,RA,RC,RB (Rc=1)
831 RT <- GFADD(GFMUL(RA, RC), RB))
832 RS <- GFADD(GFMUL(RA, RC), RB))
837 with the modulo and degree being in an SPR, multiply can be identical
838 equivalent to standard integer add
842 | 0.5|6.10|11.15|16.20|21.25| 26..30 |31|
843 | -- | -- | --- | --- | --- | ------ |--|
844 | NN | RT | RA | RB |11000| 01110 |Rc|
849 from functools import reduce
859 # constants used in the multGF2 function
860 mask1 = mask2 = polyred = None
863 """Define parameters of binary finite field GF(2^m)/g(x)
864 - irPoly: coefficients of irreducible polynomial g(x)
866 # degree: extension degree of binary field
867 degree = gf_degree(irPoly)
870 """Convert an integer into a polynomial"""
871 return [(sInt >> i) & 1
872 for i in reversed(range(sInt.bit_length()))]
874 global mask1, mask2, polyred
875 mask1 = mask2 = 1 << degree
877 polyred = reduce(lambda x, y: (x << 1) + y, i2P(irPoly)[1:])
880 """Multiply two polynomials in GF(2^m)/g(x)"""
883 # standard long-multiplication: check LSB and add
887 # standard modulo: check MSB and add polynomial
893 if __name__ == "__main__":
895 # Define binary field GF(2^3)/x^3 + x + 1
896 setGF2(0b1011) # degree 3
898 # Evaluate the product (x^2 + x + 1)(x^2 + 1)
899 print("{:02x}".format(multGF2(0b111, 0b101)))
901 # Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
902 # (used in the Advanced Encryption Standard-AES)
903 setGF2(0b100011011) # degree 8
905 # Evaluate the product (x^7)(x^7 + x + 1)
906 print("{:02x}".format(multGF2(0b10000000, 0b10000011)))
909 ## carryless Twin Butterfly (Tukey-Cooley) Mul-add-sub
911 used in combination with SV FFT REMAP to perform
912 a full NTT in-place. possible by having 3-in 2-out,
913 to avoid the need for a temp register. RS is written
916 clfmadd RT,RA,RC,RB (Rc=0)
917 clfmadd. RT,RA,RC,RB (Rc=1)
921 RT <- CLMUL(RA, RC) ^ RB
922 RS <- CLMUL(RA, RC) ^ RB
928 uint64_t bmatflip(uint64_t RA)
936 uint64_t bmatxor(uint64_t RA, uint64_t RB)
939 uint64_t RBt = bmatflip(RB);
940 uint8_t u[8]; // rows of RA
941 uint8_t v[8]; // cols of RB
942 for (int i = 0; i < 8; i++) {
947 for (int i = 0; i < 64; i++) {
948 if (pcnt(u[i / 8] & v[i % 8]) & 1)
953 uint64_t bmator(uint64_t RA, uint64_t RB)
956 uint64_t RBt = bmatflip(RB);
957 uint8_t u[8]; // rows of RA
958 uint8_t v[8]; // cols of RB
959 for (int i = 0; i < 8; i++) {
964 for (int i = 0; i < 64; i++) {
965 if ((u[i / 8] & v[i % 8]) != 0)
973 # Already in POWER ISA
975 ## count leading/trailing zeros with mask
981 do i = 0 to 63 if((RB)i=1) then do
982 if((RS)i=1) then break end end count ← count + 1
988 vpdepd VRT,VRA,VRB, identical to RV bitmamip bdep, found already in v3.1 p106
991 if VSR[VRB+32].dword[i].bit[63-m]=1 then do
992 result = VSR[VRA+32].dword[i].bit[63-k]
993 VSR[VRT+32].dword[i].bit[63-m] = result
999 uint_xlen_t bdep(uint_xlen_t RA, uint_xlen_t RB)
1002 for (int i = 0, j = 0; i < XLEN; i++)
1003 if ((RB >> i) & 1) {
1005 r |= uint_xlen_t(1) << i;
1015 other way round: identical to RV bext, found in v3.1 p196
1018 uint_xlen_t bext(uint_xlen_t RA, uint_xlen_t RB)
1021 for (int i = 0, j = 0; i < XLEN; i++)
1022 if ((RB >> i) & 1) {
1024 r |= uint_xlen_t(1) << j;
1033 found in v3.1 p106 so not to be added here
1043 if((RB)63-i==1) then do
1044 result63-ptr1 = (RS)63-i
1050 # bit to byte permute
1052 similar to matrix permute in RV bitmanip, which has XOR and OR variants,
1053 these perform a transpose.
1057 b = VSR[VRB+32].dword[i].byte[k].bit[j]
1058 VSR[VRT+32].dword[i].byte[j].bit[k] = b