Bitcoin Core  22.99.0
P2P Digital Currency
int_utils.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_INT_UTILS_H_
8 #define _MINISKETCH_INT_UTILS_H_
9 
10 #include <stdlib.h>
11 
12 #include <limits>
13 #include <algorithm>
14 #include <type_traits>
15 
16 #ifdef _MSC_VER
17 # include <intrin.h>
18 #endif
19 
20 template<int bits>
21 static constexpr inline uint64_t Rot(uint64_t x) { return (x << bits) | (x >> (64 - bits)); }
22 
23 static inline void SipHashRound(uint64_t& v0, uint64_t& v1, uint64_t& v2, uint64_t& v3) {
24  v0 += v1; v1 = Rot<13>(v1); v1 ^= v0;
25  v0 = Rot<32>(v0);
26  v2 += v3; v3 = Rot<16>(v3); v3 ^= v2;
27  v0 += v3; v3 = Rot<21>(v3); v3 ^= v0;
28  v2 += v1; v1 = Rot<17>(v1); v1 ^= v2;
29  v2 = Rot<32>(v2);
30 }
31 
32 inline uint64_t SipHash(uint64_t k0, uint64_t k1, uint64_t data) {
33  uint64_t v0 = 0x736f6d6570736575ULL ^ k0;
34  uint64_t v1 = 0x646f72616e646f6dULL ^ k1;
35  uint64_t v2 = 0x6c7967656e657261ULL ^ k0;
36  uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ data;
37  SipHashRound(v0, v1, v2, v3);
38  SipHashRound(v0, v1, v2, v3);
39  v0 ^= data;
40  v3 ^= 0x800000000000000ULL;
41  SipHashRound(v0, v1, v2, v3);
42  SipHashRound(v0, v1, v2, v3);
43  v0 ^= 0x800000000000000ULL;
44  v2 ^= 0xFF;
45  SipHashRound(v0, v1, v2, v3);
46  SipHashRound(v0, v1, v2, v3);
47  SipHashRound(v0, v1, v2, v3);
48  SipHashRound(v0, v1, v2, v3);
49  return v0 ^ v1 ^ v2 ^ v3;
50 }
51 
52 class BitWriter {
53  unsigned char state = 0;
54  int offset = 0;
55  unsigned char* out;
56 
57 public:
58  BitWriter(unsigned char* output) : out(output) {}
59 
60  template<int BITS, typename I>
61  inline void Write(I val) {
62  int bits = BITS;
63  if (bits + offset >= 8) {
64  state |= ((val & ((I(1) << (8 - offset)) - 1)) << offset);
65  *(out++) = state;
66  val >>= (8 - offset);
67  bits -= 8 - offset;
68  offset = 0;
69  state = 0;
70  }
71  while (bits >= 8) {
72  *(out++) = val & 255;
73  val >>= 8;
74  bits -= 8;
75  }
76  state |= ((val & ((I(1) << bits) - 1)) << offset);
77  offset += bits;
78  }
79 
80  inline void Flush() {
81  if (offset) {
82  *(out++) = state;
83  state = 0;
84  offset = 0;
85  }
86  }
87 };
88 
89 class BitReader {
90  unsigned char state = 0;
91  int offset = 0;
92  const unsigned char* in;
93 
94 public:
95  BitReader(const unsigned char* input) : in(input) {}
96 
97  template<int BITS, typename I>
98  inline I Read() {
99  int bits = BITS;
100  if (offset >= bits) {
101  I ret = state & ((1 << bits) - 1);
102  state >>= bits;
103  offset -= bits;
104  return ret;
105  }
106  I val = state;
107  int out = offset;
108  while (out + 8 <= bits) {
109  val |= ((I(*(in++))) << out);
110  out += 8;
111  }
112  if (out < bits) {
113  unsigned char c = *(in++);
114  val |= (c & ((I(1) << (bits - out)) - 1)) << out;
115  state = c >> (bits - out);
116  offset = 8 - (bits - out);
117  } else {
118  state = 0;
119  offset = 0;
120  }
121  return val;
122  }
123 };
124 
126 template<int BITS, typename I>
127 constexpr inline I Mask() { return ((I((I(-1)) << (std::numeric_limits<I>::digits - BITS))) >> (std::numeric_limits<I>::digits - BITS)); }
128 
130 template<typename I>
131 static inline int CountBits(I val, int max) {
132 #ifdef HAVE_CLZ
133  (void)max;
134  if (val == 0) return 0;
135  if (std::numeric_limits<unsigned>::digits >= std::numeric_limits<I>::digits) {
136  return std::numeric_limits<unsigned>::digits - __builtin_clz(val);
137  } else if (std::numeric_limits<unsigned long>::digits >= std::numeric_limits<I>::digits) {
138  return std::numeric_limits<unsigned long>::digits - __builtin_clzl(val);
139  } else {
140  return std::numeric_limits<unsigned long long>::digits - __builtin_clzll(val);
141  }
142 #elif _MSC_VER
143  (void)max;
144  unsigned long index;
145  unsigned char ret;
146  if (std::numeric_limits<I>::digits <= 32) {
147  ret = _BitScanReverse(&index, val);
148  } else {
149  ret = _BitScanReverse64(&index, val);
150  }
151  if (!ret) return 0;
152  return index;
153 #else
154  while (max && (val >> (max - 1) == 0)) --max;
155  return max;
156 #endif
157 }
158 
159 template<typename I, int BITS>
160 class BitsInt {
161 private:
162  static_assert(std::is_integral<I>::value && std::is_unsigned<I>::value, "BitsInt requires an unsigned integer type");
163  static_assert(BITS > 0 && BITS <= std::numeric_limits<I>::digits, "BitsInt requires 1 <= Bits <= representation type size");
164 
165  static constexpr I MASK = Mask<BITS, I>();
166 
167 public:
168 
169  typedef I Repr;
170 
171  static constexpr int SIZE = BITS;
172 
173  static void inline Swap(I& a, I& b) {
174  std::swap(a, b);
175  }
176 
177  static constexpr inline bool IsZero(I a) { return a == 0; }
178  static constexpr inline I Mask(I val) { return val & MASK; }
179  static constexpr inline I Shift(I val, int bits) { return ((val << bits) & MASK); }
180  static constexpr inline I UnsafeShift(I val, int bits) { return (val << bits); }
181 
182  template<int Offset, int Count>
183  static constexpr inline int MidBits(I val) {
184  static_assert(Count > 0, "BITSInt::MidBits needs Count > 0");
185  static_assert(Count + Offset <= BITS, "BitsInt::MidBits overflow of Count+Offset");
186  return (val >> Offset) & ((I(1) << Count) - 1);
187  }
188 
189  template<int Count>
190  static constexpr inline int TopBits(I val) {
191  static_assert(Count > 0, "BitsInt::TopBits needs Count > 0");
192  static_assert(Count <= BITS, "BitsInt::TopBits needs Offset <= BITS");
193  return val >> (BITS - Count);
194  }
195 
196  static inline constexpr I CondXorWith(I val, bool cond, I v) {
197  return val ^ (-I(cond) & v);
198  }
199 
200  template<I MOD>
201  static inline constexpr I CondXorWith(I val, bool cond) {
202  return val ^ (-I(cond) & MOD);
203  }
204 
205  static inline int Bits(I val, int max) { return CountBits<I>(val, max); }
206 };
207 
209 template<typename F, uint32_t MOD>
210 struct LFSR {
211  typedef typename F::Repr I;
213  static inline constexpr I Call(const I& a) {
214  return F::template CondXorWith<MOD>(F::Shift(a, 1), F::template TopBits<1>(a));
215  }
216 };
217 
219 template<typename I, int N, typename L, typename F, int K> struct GFMulHelper;
220 template<typename I, int N, typename L, typename F> struct GFMulHelper<I, N, L, F, 0>
221 {
222  static inline constexpr I Run(const I& a, const I& b) { return I(0); }
223 };
224 template<typename I, int N, typename L, typename F, int K> struct GFMulHelper
225 {
226  static inline constexpr I Run(const I& a, const I& b) { return F::CondXorWith(GFMulHelper<I, N, L, F, K - 1>::Run(L::Call(a), b), F::template MidBits<N - K, 1>(b), a); }
227 };
228 
230 template<typename I, int N, typename L, typename F> inline constexpr I GFMul(const I& a, const I& b) { return GFMulHelper<I, N, L, F, N>::Run(a, b); }
231 
233 template<typename I, typename F, int BITS, uint32_t MOD>
234 inline I InvExtGCD(I x)
235 {
236  if (F::IsZero(x)) return x;
237  I t(0), newt(1);
238  I r(MOD), newr = x;
239  int rlen = BITS + 1, newrlen = F::Bits(newr, BITS);
240  while (newr) {
241  int q = rlen - newrlen;
242  r ^= F::Shift(newr, q);
243  t ^= F::UnsafeShift(newt, q);
244  rlen = F::Bits(r, rlen - 1);
245  if (r < newr) {
246  F::Swap(t, newt);
247  F::Swap(r, newr);
248  std::swap(rlen, newrlen);
249  }
250  }
251  return t;
252 }
253 
259 template<typename I, typename F, int BITS, I (*MUL)(I, I), I (*SQR)(I), I (*SQR2)(I), I(*SQR4)(I), I(*SQR8)(I), I(*SQR16)(I)>
260 inline I InvLadder(I x1)
261 {
262  static constexpr int INV_EXP = BITS - 1;
263  I x2 = (INV_EXP >= 2) ? MUL(SQR(x1), x1) : I();
264  I x4 = (INV_EXP >= 4) ? MUL(SQR2(x2), x2) : I();
265  I x8 = (INV_EXP >= 8) ? MUL(SQR4(x4), x4) : I();
266  I x16 = (INV_EXP >= 16) ? MUL(SQR8(x8), x8) : I();
267  I x32 = (INV_EXP >= 32) ? MUL(SQR16(x16), x16) : I();
268  I r;
269  if (INV_EXP >= 32) {
270  r = x32;
271  } else if (INV_EXP >= 16) {
272  r = x16;
273  } else if (INV_EXP >= 8) {
274  r = x8;
275  } else if (INV_EXP >= 4) {
276  r = x4;
277  } else if (INV_EXP >= 2) {
278  r = x2;
279  } else {
280  r = x1;
281  }
282  if (INV_EXP >= 32 && (INV_EXP & 16)) r = MUL(SQR16(r), x16);
283  if (INV_EXP >= 16 && (INV_EXP & 8)) r = MUL(SQR8(r), x8);
284  if (INV_EXP >= 8 && (INV_EXP & 4)) r = MUL(SQR4(r), x4);
285  if (INV_EXP >= 4 && (INV_EXP & 2)) r = MUL(SQR2(r), x2);
286  if (INV_EXP >= 2 && (INV_EXP & 1)) r = MUL(SQR(r), x1);
287  return SQR(r);
288 }
289 
290 #endif
BitsInt::Bits
static int Bits(I val, int max)
Definition: int_utils.h:205
CountBits
static int CountBits(I val, int max)
Compute the smallest power of two that is larger than val.
Definition: int_utils.h:131
SipHashRound
static void SipHashRound(uint64_t &v0, uint64_t &v1, uint64_t &v2, uint64_t &v3)
Definition: int_utils.h:23
BitsInt::MASK
static constexpr I MASK
Definition: int_utils.h:165
BitReader
Definition: int_utils.h:89
BitsInt::Mask
static constexpr I Mask(I val)
Definition: int_utils.h:178
InvLadder
I InvLadder(I x1)
Compute the inverse of x1 using an exponentiation ladder.
Definition: int_utils.h:260
BitsInt::TopBits
static constexpr int TopBits(I val)
Definition: int_utils.h:190
GFMulHelper::Run
static constexpr I Run(const I &a, const I &b)
Definition: int_utils.h:226
BitsInt::MidBits
static constexpr int MidBits(I val)
Definition: int_utils.h:183
SipHash
uint64_t SipHash(uint64_t k0, uint64_t k1, uint64_t data)
Definition: int_utils.h:32
BitWriter
Definition: int_utils.h:52
LFSR
Class which implements a stateless LFSR for generic moduli.
Definition: int_utils.h:210
BitsInt::IsZero
static constexpr bool IsZero(I a)
Definition: int_utils.h:177
GFMulHelper
Helper class for carryless multiplications.
Definition: int_utils.h:219
BitsInt::CondXorWith
static constexpr I CondXorWith(I val, bool cond)
Definition: int_utils.h:201
BitWriter::Flush
void Flush()
Definition: int_utils.h:80
BitReader::offset
int offset
Definition: int_utils.h:91
BitReader::in
const unsigned char * in
Definition: int_utils.h:92
BitReader::BitReader
BitReader(const unsigned char *input)
Definition: int_utils.h:95
BitReader::state
unsigned char state
Definition: int_utils.h:90
Mask
constexpr I Mask()
Return a value of type I with its bits lowest bits set (bits must be > 0).
Definition: int_utils.h:127
BitWriter::out
unsigned char * out
Definition: int_utils.h:55
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:213
BitWriter::offset
int offset
Definition: int_utils.h:54
BitsInt::Repr
I Repr
Definition: int_utils.h:169
GFMul
constexpr I GFMul(const I &a, const I &b)
Compute the carry-less multiplication of a and b, with N bits, using L as LFSR type.
Definition: int_utils.h:230
BitsInt::SIZE
static constexpr int SIZE
Definition: int_utils.h:171
BitWriter::BitWriter
BitWriter(unsigned char *output)
Definition: int_utils.h:58
BitWriter::Write
void Write(I val)
Definition: int_utils.h:61
BitsInt::CondXorWith
static constexpr I CondXorWith(I val, bool cond, I v)
Definition: int_utils.h:196
BitsInt::UnsafeShift
static constexpr I UnsafeShift(I val, int bits)
Definition: int_utils.h:180
Rot
static constexpr uint64_t Rot(uint64_t x)
Definition: int_utils.h:21
LFSR::I
F::Repr I
Definition: int_utils.h:211
BitsInt::Swap
static void Swap(I &a, I &b)
Definition: int_utils.h:173
GFMulHelper< I, N, L, F, 0 >::Run
static constexpr I Run(const I &a, const I &b)
Definition: int_utils.h:222
InvExtGCD
I InvExtGCD(I x)
Compute the inverse of x using an extgcd algorithm.
Definition: int_utils.h:234
BitWriter::state
unsigned char state
Definition: int_utils.h:53
k1
static const unsigned char k1[32]
Definition: chacha_poly_aead.cpp:19
BitsInt::Shift
static constexpr I Shift(I val, int bits)
Definition: int_utils.h:179
BitsInt
Definition: int_utils.h:160
ByteUnit::t
@ t
BitReader::Read
I Read()
Definition: int_utils.h:98