openpower/sv/bitmanip.mdwn

   1 [[!tag standards]]
   2
   3 # bitmanipulation
   4
   5 **DRAFT STATUS**
   6
   7 this extension amalgamates bitnanipulation 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.  Vectorisation Context is provided by [[openpower/sv]].
   8
   9 ternaryv 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 ternary 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 a similar objective.
  10
  11 general-purpose Galois Field operations are added so as to avoid huge 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.
  12
  13 # summary
  14
  15 minor opcode allocation
  16
  17     |  28.30 |31| name      |
  18     | ------ |--| --------- |
  19     |   00   |Rc| ternaryi  |
  20     |  001   |Rc| ternary   |
  21     |  010   |Rc| bitmask   |
  22     |  011   |Rc| gf*       |
  23     |  101   |1 | ternaryv  |
  24     |  101   |0 | ternarycr |
  25     |  110   |Rc| 1/2-op    |
  26     |  111   |Rc| bitmaski  |
  27
  28 1-op and variants
  29
  30 | dest | src1 | subop | op       |
  31 | ---- | ---- | ----- | -------- |
  32 | RT   | RA   | ..    | bmatflip |
  33
  34 2-op and variants
  35
  36 | dest | src1 | src2 | subop | op       |
  37 | ---- | ---- | ---- | ----- | -------- |
  38 | RT   | RA   | RB   | or    | bmatflip |
  39 | RT   | RA   | RB   | xor   | bmatflip |
  40 | RT   | RA   | RB   | bdep  | dep/ext  |
  41 | RT   | RA   | RB   | bext  | dep/ext  |
  42 | RT   | RA   | RB   |       | grev  |
  43 | RT   | RA   | RB   |       | clmul*  |
  44 | RT   | RA   | RB   |       | gorc |
  45 | RT   | RA   | RB   | shuf  | shuffle |
  46 | RT   | RA   | RB   | unshuf| shuffle |
  47 | RT   | RA   | RB   | width | xperm  |
  48 | RT   | RA   | RB   | type | minmax |
  49 | RT   | RA   | RB   |  |  |
  50 | RT   | RA   | RB   |  |  |
  51 | RT   | RA   | RB   |  |  |
  52
  53 3 ops
  54
  55 * bitmask set/extract
  56 * ternary bitops
  57 * GF
  58
  59 | 0.5|6.10|11.15|16.20|21..25 | 26....30 |31| name |
  60 | -- | -- | --- | --- | ----- | -------- |--| ------ |
  61 | NN | RT | RA  | RB  | RC    | mode 001 |Rc| ternary |
  62 | NN | RT | RA  | RB  | im0-4 | im5-7 00 |Rc| ternaryi |
  63 | NN | RS | RA  | RB  | RC    | 00  011  |Rc| gfmul |
  64 | NN | RS | RA  | RB  | deg   | 01  011  |Rc| gfadd |
  65 | NN | RT | RA  | RB  | deg   | 10  011  |Rc| gfinv |
  66 | NN | RS | RA  | RB  | deg   | 11  011  |Rc| gfmuli |
  67
  68 | 0.5|6.10|11.15| 16.23 |24.27 | 28.30 |31| name |
  69 | -- | -- | --- | ----- | ---- | ----- |--| ------ |
  70 | NN | RT | RA  | imm   | mask | 101   |1 | ternaryv |
  71
  72 | 0.5|6.8 | 9.11|12.14|15|16.23|24.27 | 28.30|31| name |
  73 | -- | -- | --- | --- |- |-----|----- | -----|--| -------|
  74 | NN | BA | BB  | BC  |0 |imm  | mask | 101  |0 | ternarycr |
  75
  76 ops
  77
  78 | 0.5|6.10|11.15|16.20| 21.22 | 23 | 24....30 |31| name |
  79 | -- | -- | --- | --- | ----- | -- | -------- |--| ---- |
  80 | NN | RA | RB  |     |       | 0  | 0000 110 |Rc| rsvd   |
  81 | NN | RA | RB  | RC  | itype | 1  | 0000 110 |Rc| xperm |
  82 | NN | RA | RB  | RC  | itype | 0  | 0100 110 |Rc| minmax |
  83 | NN | RA | RB  |     |       | 1  | 0100 110 |Rc| rsvd |
  84 | NN | RA | RB  | sh  | itype | SH | 1000 110 |Rc| bmopsi |
  85 | NN | RA | RB  |     |       |    | 1100 110 |Rc| rsvd |
  86 | NN | RA | RB  |     |       |    | 1100 110 |Rc| rsvd |
  87 | NN | RA | RB  |     |       |    | 1100 110 |Rc| rsvd |
  88 | NN | RA | RB  |     |       |    | 1100 110 |Rc| rsvd |
  89 | NN | RA | RB  |     |       | 0  | 0001 110 |Rc| rsvd |
  90 | NN | RA | RB  |     |       | 0  | 0101 110 |Rc| rsvd |
  91 | NN | RA | RB  | RC  | 00    | 0  | 0010 110 |Rc| gorc |
  92 | NN | RA | RB  | sh  | 00    | SH | 1010 110 |Rc| gorci |
  93 | NN | RA | RB  | RC  | 00    | 0  | 0110 110 |Rc| gorcw |
  94 | NN | RA | RB  | sh  | 00    | 0  | 1110 110 |Rc| gorcwi |
  95 | NN | RA | RB  | RC  | 00    | 1  | 1110 110 |Rc| bmator  |
  96 | NN | RA | RB  | RC  | 01    | 0  | 0010 110 |Rc| grev |
  97 | NN | RA | RB  | RC  | 01    | 1  | 0010 110 |Rc| clmul |
  98 | NN | RA | RB  | sh  | 01    | SH | 1010 110 |Rc| grevi |
  99 | NN | RA | RB  | RC  | 01    | 0  | 0110 110 |Rc| grevw |
 100 | NN | RA | RB  | sh  | 01    | 0  | 1110 110 |Rc| grevwi |
 101 | NN | RA | RB  | RC  | 01    | 1  | 1110 110 |Rc| bmatxor   |
 102 | NN | RA | RB  | RC  | 10    | 0  | 0010 110 |Rc| shfl |
 103 | NN | RA | RB  | sh  | 10    | SH | 1010 110 |Rc| shfli |
 104 | NN | RA | RB  | RC  | 10    | 0  | 0110 110 |Rc| shflw |
 105 | NN | RA | RB  | RC  | 10    | 0  | 1110 110 |Rc| bdep   |
 106 | NN | RA | RB  | RC  | 10    | 1  | 1110 110 |Rc| bext  |
 107 | NN | RA | RB  | RC  | 11    | 0  | 1110 110 |Rc| clmulr  |
 108 | NN | RA | RB  | RC  | 11    | 1  | 1110 110 |Rc| clmulh  |
 109 | NN | RA | RB  |     |       |    | NN11 110 |Rc| rsvd  |
 110
 111 # bit to byte permute
 112
 113 similar to matrix permute in RV bitmanip, which has XOR and OR variants
 114
 115     do j = 0 to 7
 116       do k = 0 to 7
 117          b = VSR[VRB+32].dword[i].byte[k].bit[j]
 118          VSR[VRT+32].dword[i].byte[j].bit[k] = b
 119
 120 # vector bit deposit
 121
 122 vpdepd VRT,VRA,VRB, identical to RV bitmamip bdep
 123
 124     do while(m < 64)
 125        if VSR[VRB+32].dword[i].bit[63-m]=1 then do
 126           result = VSR[VRA+32].dword[i].bit[63-k]
 127           VSR[VRT+32].dword[i].bit[63-m] = result
 128           k = k + 1
 129        m = m + 1
 130
 131 ```
 132
 133 uint_xlen_t bdep(uint_xlen_t RA, uint_xlen_t RB)
 134 {
 135     uint_xlen_t r = 0;
 136     for (int i = 0, j = 0; i < XLEN; i++)
 137         if ((RB >> i) & 1) {
 138             if ((RA >> j) & 1)
 139                 r |= uint_xlen_t(1) << i;
 140             j++;
 141         }
 142     return r;
 143 }
 144
 145 ```
 146
 147 # vector bit extract
 148
 149 other way round: identical to RV bext
 150
 151 ```
 152 uint_xlen_t bext(uint_xlen_t RA, uint_xlen_t RB)
 153 {
 154     uint_xlen_t r = 0;
 155     for (int i = 0, j = 0; i < XLEN; i++)
 156         if ((RB >> i) & 1) {
 157             if ((RA >> i) & 1)
 158                 r |= uint_xlen_t(1) << j;
 159             j++;
 160         }
 161     return r;
 162 }
 163 ```
 164
 165 # int min/max
 166
 167 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).
 168
 169 signed/unsigned min/max gives more flexibility.
 170
 171 ```
 172 uint_xlen_t min(uint_xlen_t rs1, uint_xlen_t rs2)
 173 { return (int_xlen_t)rs1 < (int_xlen_t)rs2 ? rs1 : rs2;
 174 }
 175 uint_xlen_t max(uint_xlen_t rs1, uint_xlen_t rs2)
 176 { return (int_xlen_t)rs1 > (int_xlen_t)rs2 ? rs1 : rs2;
 177 }
 178 uint_xlen_t minu(uint_xlen_t rs1, uint_xlen_t rs2)
 179 { return rs1 < rs2 ? rs1 : rs2;
 180 }
 181 uint_xlen_t maxu(uint_xlen_t rs1, uint_xlen_t rs2)
 182 { return rs1 > rs2 ? rs1 : rs2;
 183 }
 184 ```
 185
 186
 187 # ternary bitops
 188
 189 Similar to FPGA LUTs: for every bit perform a lookup into a table using an 8bit immediate, or in another register
 190
 191 | 0.5|6.10|11.15|16.20| 21..25| 26..30   |31|
 192 | -- | -- | --- | --- | ----- | -------- |--|
 193 | NN | RT | RA  | RB  | im0-4 | im5-7 00 |Rc|
 194
 195     for i in range(64):
 196         idx = RT[i] << 2 | RA[i] << 1 | RB[i]
 197         RT[i] = (imm & (1<<idx)) != 0
 198
 199 bits 21..22 may be used to specify a mode, such as treating the whole integer zero/nonzero and putting 1/0 in the result, rather than bitwise test.
 200
 201 a 4 operand variant which becomes more along the lines of an FPGA:
 202
 203 | 0.5|6.10|11.15|16.20|21.25| 26...30  |31|
 204 | -- | -- | --- | --- | --- | -------- |--|
 205 | NN | RT | RA  | RB  | RC  | mode 001 |Rc|
 206
 207     for i in range(64):
 208         idx = RT[i] << 2 | RA[i] << 1 | RB[i]
 209         RT[i] = (RC & (1<<idx)) != 0
 210
 211 mode (2 bit) may be used to do inversion of ordering, similar to carryless mul,
 212 3 modes.
 213
 214 also, another possible variant involving swizzle and vec4:
 215
 216 | 0.5|6.10|11.15| 16.23 |24.27 | 28.30 |31|
 217 | -- | -- | --- | ----- | ---- | ----- |--|
 218 | NN | RT | RA  | imm   | mask | 101   |1 |
 219
 220     for i in range(8):
 221         idx = RA.x[i] << 2 | RA.y[i] << 1 | RA.z[i]
 222         res = (imm & (1<<idx)) != 0
 223         for j in range(3):
 224              if mask[j]: RT[i+j*8] = res
 225
 226 another mode selection would be CRs not Ints.
 227
 228 | 0.5|6.8 | 9.11|12.14|15|16.23|24.27 | 28.30|31|
 229 | -- | -- | --- | --- |- |-----|----- | -----|--|
 230 | NN | BA | BB  | BC  |0 |imm  | mask | 101  |0 |
 231
 232     for i in range(4):
 233         if not mask[i] continue
 234         idx = crregs[BA][i] << 2 |
 235               crregs[BB][i] << 1 |
 236               crregs[BC][i]
 237         crregs[BA][i] = (imm & (1<<idx)) != 0
 238
 239 # bitmask set
 240
 241 based on RV bitmanip singlebit set, instruction format similar to shift
 242 [[isa/fixedshift]].  bmext is actually covered already (shift-with-mask rldicl but only immediate version).
 243 however bitmask-invert is not, and set/clr are not covered, although they can use the same Shift ALU.
 244
 245 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.
 246 bmrev however there is no direct equivalent and consequently a bmrevi is required.
 247
 248 | 0.5|6.10|11.15|16.20|21.25| 26..30  |31| name  |
 249 | -- | -- | --- | --- | --- | ------- |--| ----- |
 250 | NN | RT | RA  | RB  | RC  | mode 010 |Rc| bm*   |
 251 | NN | RT | RA  | RB  | RC  | 0 1  111 |Rc| bmrev |
 252
 253
 254 ```
 255 uint_xlen_t bmset(RA, RB, sh)
 256 {
 257     int shamt = RB & (XLEN - 1);
 258     mask = (2<<sh)-1;
 259     return RA | (mask << shamt);
 260 }
 261
 262 uint_xlen_t bmclr(RA, RB, sh)
 263 {
 264     int shamt = RB & (XLEN - 1);
 265     mask = (2<<sh)-1;
 266     return RA & ~(mask << shamt);
 267 }
 268
 269 uint_xlen_t bminv(RA, RB, sh)
 270 {
 271     int shamt = RB & (XLEN - 1);
 272     mask = (2<<sh)-1;
 273     return RA ^ (mask << shamt);
 274 }
 275
 276 uint_xlen_t bmext(RA, RB, sh)
 277 {
 278     int shamt = RB & (XLEN - 1);
 279     mask = (2<<sh)-1;
 280     return mask & (RA >> shamt);
 281 }
 282 ```
 283
 284 bitmask extract with reverse.  can be done by bitinverting all of RA and getting bits of RA from the opposite end.
 285
 286 ```
 287 msb = rb[5:0];
 288 rev[0:msb] = ra[msb:0];
 289 rt = ZE(rev[msb:0]);
 290
 291 uint_xlen_t bmextrev(RA, RB, sh)
 292 {
 293     int shamt = (RB & (XLEN - 1));
 294     shamt = (XLEN-1)-shamt;  # shift other end
 295     bra = bitreverse(RA)     # swap LSB-MSB
 296     mask = (2<<sh)-1;
 297     return mask & (bra >> shamt);
 298 }
 299 ```
 300
 301 | 0.5|6.10|11.15|16.20|21.26| 27..30  |31| name   |
 302 | -- | -- | --- | --- | --- | ------- |--| ------ |
 303 | NN | RT | RA  | RB  | sh  | 0   111 |Rc| bmrevi |
 304
 305
 306
 307 # grev
 308
 309 based on RV bitmanip
 310
 311 ```
 312 uint64_t grev64(uint64_t RA, uint64_t RB)
 313 {
 314     uint64_t x = RA;
 315     int shamt = RB & 63;
 316     if (shamt & 1) x = ((x &  0x5555555555555555LL) <<  1) |
 317                         ((x & 0xAAAAAAAAAAAAAAAALL) >>  1);
 318     if (shamt & 2) x = ((x &  0x3333333333333333LL) <<  2) |
 319                         ((x & 0xCCCCCCCCCCCCCCCCLL) >>  2);
 320     if (shamt & 4) x = ((x &  0x0F0F0F0F0F0F0F0FLL) <<  4) |
 321                         ((x & 0xF0F0F0F0F0F0F0F0LL) >>  4);
 322     if (shamt & 8) x = ((x &  0x00FF00FF00FF00FFLL) <<  8) |
 323                         ((x & 0xFF00FF00FF00FF00LL) >>  8);
 324     if (shamt & 16) x = ((x & 0x0000FFFF0000FFFFLL) << 16) |
 325                         ((x & 0xFFFF0000FFFF0000LL) >> 16);
 326     if (shamt & 32) x = ((x & 0x00000000FFFFFFFFLL) << 32) |
 327                         ((x & 0xFFFFFFFF00000000LL) >> 32);
 328     return x;
 329 }
 330
 331 ```
 332
 333 # shuffle / unshuffle
 334
 335 based on RV bitmanip
 336
 337 ```
 338 uint32_t shfl32(uint32_t RA, uint32_t RB)
 339 {
 340     uint32_t x = RA;
 341     int shamt = RB & 15;
 342     if (shamt & 8) x  = shuffle32_stage(x, 0x00ff0000, 0x0000ff00, 8);
 343     if (shamt & 4) x  = shuffle32_stage(x, 0x0f000f00, 0x00f000f0, 4);
 344     if (shamt & 2) x  = shuffle32_stage(x, 0x30303030, 0x0c0c0c0c, 2);
 345     if (shamt & 1) x  = shuffle32_stage(x, 0x44444444, 0x22222222, 1);
 346     return x;
 347 }
 348 uint32_t unshfl32(uint32_t RA, uint32_t RB)
 349 {
 350     uint32_t x = RA;
 351     int shamt = RB & 15;
 352     if (shamt & 1) x  = shuffle32_stage(x, 0x44444444, 0x22222222, 1);
 353     if (shamt & 2) x  = shuffle32_stage(x, 0x30303030, 0x0c0c0c0c, 2);
 354     if (shamt & 4) x  = shuffle32_stage(x, 0x0f000f00, 0x00f000f0, 4);
 355     if (shamt & 8) x  = shuffle32_stage(x, 0x00ff0000, 0x0000ff00, 8);
 356     return x;
 357 }
 358
 359 uint64_t shuffle64_stage(uint64_t src, uint64_t maskL, uint64_t maskR, int N)
 360 {
 361     uint64_t x = src & ~(maskL | maskR);
 362     x |= ((src << N) & maskL) | ((src >> N) & maskR);
 363     return x;
 364 }
 365 uint64_t shfl64(uint64_t RA, uint64_t RB)
 366 {
 367     uint64_t x = RA;
 368     int shamt = RB & 31;
 369     if (shamt & 16) x = shuffle64_stage(x, 0x0000ffff00000000LL,
 370                                            0x00000000ffff0000LL, 16);
 371     if (shamt & 8) x = shuffle64_stage(x, 0x00ff000000ff0000LL,
 372                                            0x0000ff000000ff00LL, 8);
 373     if (shamt & 4) x = shuffle64_stage(x, 0x0f000f000f000f00LL,
 374                                            0x00f000f000f000f0LL, 4);
 375     if (shamt & 2) x = shuffle64_stage(x, 0x3030303030303030LL,
 376                                            0x0c0c0c0c0c0c0c0cLL, 2);
 377     if (shamt & 1) x = shuffle64_stage(x, 0x4444444444444444LL,
 378                                            0x2222222222222222LL, 1);
 379     return x;
 380 }
 381 uint64_t unshfl64(uint64_t RA, uint64_t RB)
 382 {
 383     uint64_t x = RA;
 384     int shamt = RB & 31;
 385     if (shamt &  1) x = shuffle64_stage(x, 0x4444444444444444LL,
 386                                            0x2222222222222222LL, 1);
 387     if (shamt &  2) x = shuffle64_stage(x, 0x3030303030303030LL,
 388                                            0x0c0c0c0c0c0c0c0cLL, 2);
 389     if (shamt &  4) x = shuffle64_stage(x, 0x0f000f000f000f00LL,
 390                                            0x00f000f000f000f0LL, 4);
 391     if (shamt &  8) x = shuffle64_stage(x, 0x00ff000000ff0000LL,
 392                                            0x0000ff000000ff00LL, 8);
 393     if (shamt & 16) x = shuffle64_stage(x, 0x0000ffff00000000LL,
 394                                            0x00000000ffff0000LL, 16);
 395     return x;
 396 }
 397 ```
 398
 399 # xperm
 400
 401 based on RV bitmanip
 402
 403 ```
 404 uint_xlen_t xperm(uint_xlen_t RA, uint_xlen_t RB, int sz_log2)
 405 {
 406     uint_xlen_t r = 0;
 407     uint_xlen_t sz = 1LL << sz_log2;
 408     uint_xlen_t mask = (1LL << sz) - 1;
 409     for (int i = 0; i < XLEN; i += sz) {
 410         uint_xlen_t pos = ((RB >> i) & mask) << sz_log2;
 411         if (pos < XLEN)
 412             r |= ((RA >> pos) & mask) << i;
 413     }
 414     return r;
 415 }
 416 uint_xlen_t xperm_n (uint_xlen_t RA, uint_xlen_t RB)
 417 {  return xperm(RA, RB, 2); }
 418 uint_xlen_t xperm_b (uint_xlen_t RA, uint_xlen_t RB)
 419 {  return xperm(RA, RB, 3); }
 420 uint_xlen_t xperm_h (uint_xlen_t RA, uint_xlen_t RB)
 421 {  return xperm(RA, RB, 4); }
 422 uint_xlen_t xperm_w (uint_xlen_t RA, uint_xlen_t RB)
 423 {  return xperm(RA, RB, 5); }
 424 ```
 425
 426 # gorc
 427
 428 based on RV bitmanip
 429
 430 ```
 431 uint32_t gorc32(uint32_t RA, uint32_t RB)
 432 {
 433     uint32_t x = RA;
 434     int shamt = RB & 31;
 435     if (shamt & 1) x |= ((x & 0x55555555) << 1)   |  ((x &  0xAAAAAAAA) >> 1);
 436     if (shamt & 2) x |= ((x & 0x33333333) << 2)   |  ((x &  0xCCCCCCCC) >> 2);
 437     if (shamt & 4) x |= ((x & 0x0F0F0F0F) << 4)   |  ((x &  0xF0F0F0F0) >> 4);
 438     if (shamt & 8) x |= ((x & 0x00FF00FF) << 8)   |  ((x &  0xFF00FF00) >> 8);
 439     if (shamt & 16) x |= ((x & 0x0000FFFF) << 16) |  ((x &  0xFFFF0000) >> 16);
 440     return x;
 441 }
 442 uint64_t gorc64(uint64_t RA, uint64_t RB)
 443 {
 444     uint64_t x = RA;
 445     int shamt = RB & 63;
 446     if (shamt & 1) x |= ((x & 0x5555555555555555LL)   <<   1) |
 447                          ((x & 0xAAAAAAAAAAAAAAAALL)  >>  1);
 448     if (shamt & 2) x |= ((x & 0x3333333333333333LL)   <<   2) |
 449                          ((x & 0xCCCCCCCCCCCCCCCCLL)  >>  2);
 450     if (shamt & 4) x |= ((x & 0x0F0F0F0F0F0F0F0FLL)   <<   4) |
 451                          ((x & 0xF0F0F0F0F0F0F0F0LL)  >>  4);
 452     if (shamt & 8) x |= ((x & 0x00FF00FF00FF00FFLL)   <<   8) |
 453                          ((x & 0xFF00FF00FF00FF00LL)  >>  8);
 454     if (shamt & 16) x |= ((x & 0x0000FFFF0000FFFFLL)  << 16) |
 455                          ((x & 0xFFFF0000FFFF0000LL)  >> 16);
 456     if (shamt & 32) x |= ((x & 0x00000000FFFFFFFFLL)  << 32) |
 457                          ((x & 0xFFFFFFFF00000000LL)  >> 32);
 458     return x;
 459 }
 460
 461 ```
 462
 463 # cmix
 464
 465 based on RV bitmanip, covered by ternary bitops
 466
 467 ```
 468 uint_xlen_t cmix(uint_xlen_t RA, uint_xlen_t RB, uint_xlen_t RC) {
 469     return (RA & RB) | (RC & ~RB);
 470 }
 471 ```
 472
 473 # carryless mul
 474
 475 based on RV bitmanip
 476 see https://en.wikipedia.org/wiki/CLMUL_instruction_set
 477
 478 ```
 479 uint_xlen_t clmul(uint_xlen_t RA, uint_xlen_t RB)
 480 {
 481     uint_xlen_t x = 0;
 482     for (int i = 0; i < XLEN; i++)
 483         if ((RB >> i) & 1)
 484             x ^= RA << i;
 485     return x;
 486 }
 487 uint_xlen_t clmulh(uint_xlen_t RA, uint_xlen_t RB)
 488 {
 489     uint_xlen_t x = 0;
 490     for (int i = 1; i < XLEN; i++)
 491         if ((RB >> i) & 1)
 492             x ^= RA >> (XLEN-i);
 493     return x;
 494 }
 495 uint_xlen_t clmulr(uint_xlen_t RA, uint_xlen_t RB)
 496 {
 497     uint_xlen_t x = 0;
 498     for (int i = 0; i < XLEN; i++)
 499         if ((RB >> i) & 1)
 500             x ^= RA >> (XLEN-i-1);
 501     return x;
 502 }
 503 ```
 504 # Galois Field
 505
 506 see <https://courses.csail.mit.edu/6.857/2016/files/ffield.py>
 507
 508 ## Multiply
 509
 510 this requires 3 parameters and a "degree"
 511
 512     RT = GFMUL(RA, RB, gfdegree, modulo=RC)
 513
 514 realistically with the degree also needing to be an immediate it should be brought down to an overwrite version:
 515
 516     RS = GFMUL(RS, RA, gfdegree, modulo=RB)
 517     RS = GFMUL(RS, RA, gfdegree=RC, modulo=RB)
 518
 519 | 0.5|6.10|11.15|16.20|21.25| 26..30  |31|
 520 | -- | -- | --- | --- | --- | ------- |--|
 521 | NN | RS | RA  | RB  | deg | 00  011 |Rc|
 522 | NN | RS | RA  | RB  | RC  | 11  011 |Rc|
 523
 524 where the SimpleV variant may override RS-as-src differently from RS-as-dest
 525
 526
 527
 528 ```
 529 from functools import reduce
 530
 531 # constants used in the multGF2 function
 532 mask1 = mask2 = polyred = None
 533
 534 def setGF2(degree, irPoly):
 535     """Define parameters of binary finite field GF(2^m)/g(x)
 536        - degree: extension degree of binary field
 537        - irPoly: coefficients of irreducible polynomial g(x)
 538     """
 539     def i2P(sInt):
 540         """Convert an integer into a polynomial"""
 541         return [(sInt >> i) & 1
 542                 for i in reversed(range(sInt.bit_length()))]
 543
 544     global mask1, mask2, polyred
 545     mask1 = mask2 = 1 << degree
 546     mask2 -= 1
 547     polyred = reduce(lambda x, y: (x << 1) + y, i2P(irPoly)[1:])
 548
 549 def multGF2(p1, p2):
 550     """Multiply two polynomials in GF(2^m)/g(x)"""
 551     p = 0
 552     while p2:
 553         if p2 & 1:
 554             p ^= p1
 555         p1 <<= 1
 556         if p1 & mask1:
 557             p1 ^= polyred
 558         p2 >>= 1
 559     return p & mask2
 560
 561 if __name__ == "__main__":
 562
 563     # Define binary field GF(2^3)/x^3 + x + 1
 564     setGF2(3, 0b1011)
 565
 566     # Evaluate the product (x^2 + x + 1)(x^2 + 1)
 567     print("{:02x}".format(multGF2(0b111, 0b101)))
 568
 569     # Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
 570     # (used in the Advanced Encryption Standard-AES)
 571     setGF2(8, 0b100011011)
 572
 573     # Evaluate the product (x^7)(x^7 + x + 1)
 574     print("{:02x}".format(multGF2(0b10000000, 0b10000011)))
 575 ```
 576 ## GF add
 577
 578     RS = GFADD(RS, RA|0, gfdegree, modulo=RB)
 579     RS = GFADDI(RS, RA|0, gfdegree=RC, modulo=RB)
 580
 581 | 0.5|6.10|11.15|16.20|21.25| 26..30  |31| name  |
 582 | -- | -- | --- | --- | --- | ------- |--| ----- |
 583 | NN | RS | RA  | RB  | RC  | 0 1  011 |Rc| gfadd |
 584 | NN | RS | RA  | RB  | RC  | 1 1  111 |Rc| gfaddi |
 585
 586 GFMOD is a pseudo-op where RA=0
 587
 588 ## gf invert
 589
 590 ```
 591 def gf_degree(a) :
 592   res = 0
 593   a >>= 1
 594   while (a != 0) :
 595     a >>= 1;
 596     res += 1;
 597   return res
 598
 599 def gf_invert(a, mod=0x1B) :
 600   v = mod
 601   g1 = 1
 602   g2 = 0
 603   j = gf_degree(a) - 8
 604
 605   while (a != 1) :
 606     if (j < 0) :
 607       a, v = v, a
 608       g1, g2 = g2, g1
 609       j = -j
 610
 611     a ^= v << j
 612     g1 ^= g2 << j
 613
 614     a %= 256  # Emulating 8-bit overflow
 615     g1 %= 256 # Emulating 8-bit overflow
 616
 617     j = gf_degree(a) - gf_degree(v)
 618
 619   return g1
 620 ```
 621
 622 # bitmatrix
 623
 624 ```
 625 uint64_t bmatflip(uint64_t RA)
 626 {
 627     uint64_t x = RA;
 628     x = shfl64(x, 31);
 629     x = shfl64(x, 31);
 630     x = shfl64(x, 31);
 631     return x;
 632 }
 633 uint64_t bmatxor(uint64_t RA, uint64_t RB)
 634 {
 635     // transpose of RB
 636     uint64_t RBt = bmatflip(RB);
 637     uint8_t u[8]; // rows of RA
 638     uint8_t v[8]; // cols of RB
 639     for (int i = 0; i < 8; i++) {
 640         u[i] = RA >> (i*8);
 641         v[i] = RBt >> (i*8);
 642     }
 643     uint64_t x = 0;
 644     for (int i = 0; i < 64; i++) {
 645         if (pcnt(u[i / 8] & v[i % 8]) & 1)
 646             x |= 1LL << i;
 647     }
 648     return x;
 649 }
 650 uint64_t bmator(uint64_t RA, uint64_t RB)
 651 {
 652     // transpose of RB
 653     uint64_t RBt = bmatflip(RB);
 654     uint8_t u[8]; // rows of RA
 655     uint8_t v[8]; // cols of RB
 656     for (int i = 0; i < 8; i++) {
 657         u[i] = RA >> (i*8);
 658         v[i] = RBt >> (i*8);
 659     }
 660     uint64_t x = 0;
 661     for (int i = 0; i < 64; i++) {
 662         if ((u[i / 8] & v[i % 8]) != 0)
 663             x |= 1LL << i;
 664     }
 665     return x;
 666 }
 667
 668 ```