google / google/highway

Adding additional finite field and carryless multiplication ops

Open
#2,801 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
5.8k
Forks
471
Avg merge
1d 6h
Merged PRs (30d)
81

Description

There are some additional finite field and carryless multiplication ops that have actual use cases, including cryptography (including SM4, Camellia, Grain128-AEADv2, and post-quantum crytography), hashing (including Groestl hash, Toeplitz hash, and CRC checksums), and Reed-Solomon error correction.

Here are the proposed additional finite field and carryless multiplication ops:
- VU8 **CLMul**(VU8 a, VU8 b) - does carryless multiplication of `a[i]` and `b[i]`, returning the lower 8 bits without any modular reduction, equivalent to NEON `vmul_p8` or SVE2 `svpmul_u8`
- VU16 **WidenCLMul**(DU16, VU8 a, VU8 b) - does carryless multiplication of `a[i]` and `b[i]`, returned as a U16, equivalent to NEON `vmull_p8`
- VU8 **CLMulHigh**(VU8 a, VU8 b) - does carryless multiplication of `a[i]` and `b[i]`, returning the upper 8 bits, equivalent to `DemoteTo(du8, ShiftRight<8>(WidenCLMulLower(du16, a, b)))`
- VU8 **GF2P8Mul**(VU8 a, VU8 b) - does carryless multiplication of `a[i]` and `b[i]` followed by finite field modular reduction by x8 + x4+ x3 + x + 1, equivalent to GFNI `_mm_gf2p8mul_epi8`
- VU16 **CLMulEven**(DU16, VU8 a, VU8 b) - does carryless multiplication of `a[2*i]` and `b[2*i]` - equivalent to SVE2 `svpmullb_u16`
- VU16 **CLMulOdd**(DU16, VU8 a, VU8 b) - does carryless multiplication of `a[2*i+1]` and `b[2*i+1]` - equivalent to SVE2 `svpmullt_u16`
- VU16 **CLWidenMulPairwiseAdd**(DU16, VU8 a, VU8 b) - equivalent to `Xor(CLMulEven(du16, a, b), CLMulOdd(du16, a, b))` or PPC8 `vec_pmsum_be(a, b)`
- VU8 **GF2P8MulInverse**(VU8 v) - computes the GF(2^8) multiplicative inverse of `v[i]` (modulo x8 + x4+ x3 + x + 1) - equivalent to GFNI `_mm_gf2p8affineinv_epi64_epi8(v, _mm_set1_epi64x(0x0102040810204080), 0x00)`
- VU8 **GaloisAffine**<uint64_k kMatrix, uint8_t kXorMask>(VU8 v) - applies affine transform `kMatrix` to `v[i]` - equivalent to GFNI `_mm_gf2p8affine_epi64_epi8(v, _mm_set1_epi64x(static_cast(kMatrix)), kXorMask)`
- VU8 **GaloisAffineInv**<uint64_k kMatrix, uint8_t kXorMask>(VU8 v) - equivalent to `GaloisAffine(GF2P8MulInverse(v))` or GFNI `_mm_gf2p8affineinv_epi64_epi8(v, _mm_set1_epi64x(static_cast(kMatrix)), kXorMask)`

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.