Bitcoin Core 31.99.0
P2P Digital Currency
clmul_common_impl.h
Go to the documentation of this file.
1/**********************************************************************
2 * Copyright (c) 2018 Pieter Wuille, Greg Maxwell, Gleb Naumenko *
3 * Distributed under the MIT software license, see the accompanying *
4 * file LICENSE or http://www.opensource.org/licenses/mit-license.php.*
5 **********************************************************************/
6
7#ifndef _MINISKETCH_FIELDS_CLMUL_COMMON_IMPL_H_
8#define _MINISKETCH_FIELDS_CLMUL_COMMON_IMPL_H_ 1
9
10#include <stdint.h>
11#include <immintrin.h>
12
13#include "../int_utils.h"
14#include "../lintrans.h"
15#include "../util.h"
16
17namespace {
18
19// The memory sanitizer in clang < 11 cannot reason through _mm_clmulepi64_si128 calls.
20// Disable memory sanitization in the functions using them for those compilers.
21#if defined(__clang__) && (__clang_major__ < 11)
22# if defined(__has_feature)
23# if __has_feature(memory_sanitizer)
24# define NO_SANITIZE_MEMORY __attribute__((no_sanitize("memory")))
25# endif
26# endif
27#endif
28#ifndef NO_SANITIZE_MEMORY
29# define NO_SANITIZE_MEMORY
30#endif
31
32template<typename I, int BITS, I MOD> NO_SANITIZE_MEMORY MAYBE_UNUSED I MulWithClMulReduce(I a, I b)
33{
34 static constexpr I MASK = Mask<BITS, I>();
35
36 const __m128i MOD128 = _mm_cvtsi64_si128(MOD);
37 __m128i product = _mm_clmulepi64_si128(_mm_cvtsi64_si128((uint64_t)a), _mm_cvtsi64_si128((uint64_t)b), 0x00);
38 if (BITS <= 32) {
39 __m128i high1 = _mm_srli_epi64(product, BITS);
40 __m128i red1 = _mm_clmulepi64_si128(high1, MOD128, 0x00);
41 __m128i high2 = _mm_srli_epi64(red1, BITS);
42 __m128i red2 = _mm_clmulepi64_si128(high2, MOD128, 0x00);
43 return _mm_cvtsi128_si64(_mm_xor_si128(_mm_xor_si128(product, red1), red2)) & MASK;
44 } else if (BITS == 64) {
45 __m128i red1 = _mm_clmulepi64_si128(product, MOD128, 0x01);
46 __m128i red2 = _mm_clmulepi64_si128(red1, MOD128, 0x01);
47 return _mm_cvtsi128_si64(_mm_xor_si128(_mm_xor_si128(product, red1), red2));
48 } else if ((BITS % 8) == 0) {
49 __m128i high1 = _mm_srli_si128(product, BITS / 8);
50 __m128i red1 = _mm_clmulepi64_si128(high1, MOD128, 0x00);
51 __m128i high2 = _mm_srli_si128(red1, BITS / 8);
52 __m128i red2 = _mm_clmulepi64_si128(high2, MOD128, 0x00);
53 return _mm_cvtsi128_si64(_mm_xor_si128(_mm_xor_si128(product, red1), red2)) & MASK;
54 } else {
55 __m128i high1 = _mm_or_si128(_mm_srli_epi64(product, BITS), _mm_srli_si128(_mm_slli_epi64(product, 64 - BITS), 8));
56 __m128i red1 = _mm_clmulepi64_si128(high1, MOD128, 0x00);
57 if ((uint64_t(MOD) >> (66 - BITS)) == 0) {
58 __m128i high2 = _mm_srli_epi64(red1, BITS);
59 __m128i red2 = _mm_clmulepi64_si128(high2, MOD128, 0x00);
60 return _mm_cvtsi128_si64(_mm_xor_si128(_mm_xor_si128(product, red1), red2)) & MASK;
61 } else {
62 __m128i high2 = _mm_or_si128(_mm_srli_epi64(red1, BITS), _mm_srli_si128(_mm_slli_epi64(red1, 64 - BITS), 8));
63 __m128i red2 = _mm_clmulepi64_si128(high2, MOD128, 0x00);
64 return _mm_cvtsi128_si64(_mm_xor_si128(_mm_xor_si128(product, red1), red2)) & MASK;
65 }
66 }
67}
68
69template<typename I, int BITS, int POS> NO_SANITIZE_MEMORY MAYBE_UNUSED I MulTrinomial(I a, I b)
70{
71 static constexpr I MASK = Mask<BITS, I>();
72
73 __m128i product = _mm_clmulepi64_si128(_mm_cvtsi64_si128((uint64_t)a), _mm_cvtsi64_si128((uint64_t)b), 0x00);
74 if (BITS <= 32) {
75 __m128i high1 = _mm_srli_epi64(product, BITS);
76 __m128i red1 = _mm_xor_si128(high1, _mm_slli_epi64(high1, POS));
77 if (POS == 1) {
78 return _mm_cvtsi128_si64(_mm_xor_si128(product, red1)) & MASK;
79 } else {
80 __m128i high2 = _mm_srli_epi64(red1, BITS);
81 __m128i red2 = _mm_xor_si128(high2, _mm_slli_epi64(high2, POS));
82 return _mm_cvtsi128_si64(_mm_xor_si128(_mm_xor_si128(product, red1), red2)) & MASK;
83 }
84 } else {
85 __m128i high1 = _mm_or_si128(_mm_srli_epi64(product, BITS), _mm_srli_si128(_mm_slli_epi64(product, 64 - BITS), 8));
86 if (BITS + POS <= 66) {
87 __m128i red1 = _mm_xor_si128(high1, _mm_slli_epi64(high1, POS));
88 if (POS == 1) {
89 return _mm_cvtsi128_si64(_mm_xor_si128(product, red1)) & MASK;
90 } else if (BITS + POS <= 66) {
91 __m128i high2 = _mm_srli_epi64(red1, BITS);
92 __m128i red2 = _mm_xor_si128(high2, _mm_slli_epi64(high2, POS));
93 return _mm_cvtsi128_si64(_mm_xor_si128(_mm_xor_si128(product, red1), red2)) & MASK;
94 }
95 } else {
96 const __m128i MOD128 = _mm_cvtsi64_si128(1 + (((uint64_t)1) << POS));
97 __m128i red1 = _mm_clmulepi64_si128(high1, MOD128, 0x00);
98 __m128i high2 = _mm_or_si128(_mm_srli_epi64(red1, BITS), _mm_srli_si128(_mm_slli_epi64(red1, 64 - BITS), 8));
99 __m128i red2 = _mm_xor_si128(high2, _mm_slli_epi64(high2, POS));
100 return _mm_cvtsi128_si64(_mm_xor_si128(_mm_xor_si128(product, red1), red2)) & MASK;
101 }
102 }
103}
104
106template<typename I, int B, I MOD, I (*MUL)(I, I), typename F, const F* SQR, const F* SQR2, const F* SQR4, const F* SQR8, const F* SQR16, const F* QRT, typename T, const T* LOAD, const T* SAVE> struct GenField
107{
108 typedef BitsInt<I, B> O;
109 typedef LFSR<O, MOD> L;
110
111 static inline constexpr I Sqr1(I a) { return SQR->template Map<O>(a); }
112 static inline constexpr I Sqr2(I a) { return SQR2->template Map<O>(a); }
113 static inline constexpr I Sqr4(I a) { return SQR4->template Map<O>(a); }
114 static inline constexpr I Sqr8(I a) { return SQR8->template Map<O>(a); }
115 static inline constexpr I Sqr16(I a) { return SQR16->template Map<O>(a); }
116
117public:
118 typedef I Elem;
119
120 inline constexpr int Bits() const { return B; }
121
122 inline constexpr Elem Mul2(Elem val) const { return L::Call(val); }
123
124 inline Elem Mul(Elem a, Elem b) const { return MUL(a, b); }
125
126 class Multiplier
127 {
128 Elem m_val;
129 public:
130 inline constexpr explicit Multiplier(const GenField&, Elem a) : m_val(a) {}
131 constexpr Elem operator()(Elem a) const { return MUL(m_val, a); }
132 };
133
135 inline constexpr Elem Sqr(Elem val) const { return SQR->template Map<O>(val); }
136
138 inline constexpr Elem Qrt(Elem val) const { return QRT->template Map<O>(val); }
139
141 inline Elem Inv(Elem val) const { return InvLadder<I, O, B, MUL, Sqr1, Sqr2, Sqr4, Sqr8, Sqr16>(val); }
142
144 Elem FromSeed(uint64_t seed) const {
145 uint64_t k0 = 0x434c4d554c466c64ull; // "CLMULFld"
146 uint64_t k1 = seed;
147 uint64_t count = ((uint64_t)B) << 32;
148 I ret;
149 do {
150 ret = O::Mask(I(SipHash(k0, k1, count++)));
151 } while(ret == 0);
152 return LOAD->template Map<O>(ret);
153 }
154
155 Elem Deserialize(BitReader& in) const { return LOAD->template Map<O>(in.Read<B, I>()); }
156
157 void Serialize(BitWriter& out, Elem val) const { out.Write<B, I>(SAVE->template Map<O>(val)); }
158
159 constexpr Elem FromUint64(uint64_t x) const { return LOAD->template Map<O>(O::Mask(I(x))); }
160 constexpr uint64_t ToUint64(Elem val) const { return uint64_t(SAVE->template Map<O>(val)); }
161};
162
163template<typename I, int B, I MOD, typename F, const F* SQR, const F* SQR2, const F* SQR4, const F* SQR8, const F* SQR16, const F* QRT, typename T, const T* LOAD, const T* SAVE>
164using Field = GenField<I, B, MOD, MulWithClMulReduce<I, B, MOD>, F, SQR, SQR2, SQR4, SQR8, SQR16, QRT, T, LOAD, SAVE>;
165
166template<typename I, int B, int POS, typename F, const F* SQR, const F* SQR2, const F* SQR4, const F* SQR8, const F* SQR16, const F* QRT, typename T, const T* LOAD, const T* SAVE>
167using FieldTri = GenField<I, B, I(1) + (I(1) << POS), MulTrinomial<I, B, POS>, F, SQR, SQR2, SQR4, SQR8, SQR16, QRT, T, LOAD, SAVE>;
168
169}
170
171#endif
ret
int ret
Definition: bitcoin-cli.cpp:1691
BitReader::Read
I Read()
Definition: int_utils.h:113
BitsInt::Mask
static constexpr I Mask(I val)
Definition: int_utils.h:198
NO_SANITIZE_MEMORY
#define NO_SANITIZE_MEMORY
Definition: clmul_common_impl.h:29
T
#define T(expected, seed, data)
SipHash
uint64_t SipHash(uint64_t k0, uint64_t k1, uint64_t data)
Definition: int_utils.h:35
MAYBE_UNUSED
#define MAYBE_UNUSED
Definition: util.h:39
tests_wycheproof_generate_ecdsa.out
string out
Definition: tests_wycheproof_generate_ecdsa.py:24
Serialize
void Serialize(Stream &, V)=delete
Sqr
void Sqr(std::vector< typename F::Elem > &poly, const F &field)
Square a polynomial.
Definition: sketch_impl.h:92
Field
Definition: gen.cpp:130
LFSR
Class which implements a stateless LFSR for generic moduli.
Definition: int_utils.h:230
LFSR::Call
static constexpr I Call(const I &a)
Shift a value a up once, treating it as an N-bit LFSR, with pattern MOD.
Definition: int_utils.h:233
count
static int count
Definition: tests_exhaustive.c:39
B
#define B
Definition: util_tests.cpp:565
Generated on Mon Aug 17 2026 20:00:43 for Bitcoin Core by doxygen 1.9.4