Bitcoin Core  27.99.0
P2P Digital Currency
util.h
Go to the documentation of this file.
1 /***********************************************************************
2  * Copyright (c) 2013, 2014 Pieter Wuille *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
5  ***********************************************************************/
6 
7 #ifndef SECP256K1_UTIL_H
8 #define SECP256K1_UTIL_H
9 
10 #include "../include/secp256k1.h"
11 
12 #include <stdlib.h>
13 #include <stdint.h>
14 #include <stdio.h>
15 #include <limits.h>
16 
17 #define STR_(x) #x
18 #define STR(x) STR_(x)
19 #define DEBUG_CONFIG_MSG(x) "DEBUG_CONFIG: " x
20 #define DEBUG_CONFIG_DEF(x) DEBUG_CONFIG_MSG(#x "=" STR(x))
21 
22 /* Debug helper for printing arrays of unsigned char. */
23 #define PRINT_BUF(buf, len) do { \
24  printf("%s[%lu] = ", #buf, (unsigned long)len); \
25  print_buf_plain(buf, len); \
26 } while(0)
27 
28 static void print_buf_plain(const unsigned char *buf, size_t len) {
29  size_t i;
30  printf("{");
31  for (i = 0; i < len; i++) {
32  if (i % 8 == 0) {
33  printf("\n ");
34  } else {
35  printf(" ");
36  }
37  printf("0x%02X,", buf[i]);
38  }
39  printf("\n}\n");
40 }
41 
42 # if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) )
43 # if SECP256K1_GNUC_PREREQ(2,7)
44 # define SECP256K1_INLINE __inline__
45 # elif (defined(_MSC_VER))
46 # define SECP256K1_INLINE __inline
47 # else
48 # define SECP256K1_INLINE
49 # endif
50 # else
51 # define SECP256K1_INLINE inline
52 # endif
53 
58 #define ASSERT_INT_CONST_AND_DO(expr, stmt) do { \
59  switch(42) { \
60  case /* ERROR: integer argument is not constant */ expr: \
61  break; \
62  default: ; \
63  } \
64  stmt; \
65 } while(0)
66 
67 typedef struct {
68  void (*fn)(const char *text, void* data);
69  const void* data;
71 
72 static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback * const cb, const char * const text) {
73  cb->fn(text, (void*)cb->data);
74 }
75 
76 #ifndef USE_EXTERNAL_DEFAULT_CALLBACKS
77 static void secp256k1_default_illegal_callback_fn(const char* str, void* data) {
78  (void)data;
79  fprintf(stderr, "[libsecp256k1] illegal argument: %s\n", str);
80  abort();
81 }
82 static void secp256k1_default_error_callback_fn(const char* str, void* data) {
83  (void)data;
84  fprintf(stderr, "[libsecp256k1] internal consistency check failed: %s\n", str);
85  abort();
86 }
87 #else
88 void secp256k1_default_illegal_callback_fn(const char* str, void* data);
89 void secp256k1_default_error_callback_fn(const char* str, void* data);
90 #endif
91 
94  NULL
95 };
96 
99  NULL
100 };
101 
102 
103 #ifdef DETERMINISTIC
104 #define TEST_FAILURE(msg) do { \
105  fprintf(stderr, "%s\n", msg); \
106  abort(); \
107 } while(0);
108 #else
109 #define TEST_FAILURE(msg) do { \
110  fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, msg); \
111  abort(); \
112 } while(0)
113 #endif
114 
115 #if SECP256K1_GNUC_PREREQ(3, 0)
116 #define EXPECT(x,c) __builtin_expect((x),(c))
117 #else
118 #define EXPECT(x,c) (x)
119 #endif
120 
121 #ifdef DETERMINISTIC
122 #define CHECK(cond) do { \
123  if (EXPECT(!(cond), 0)) { \
124  TEST_FAILURE("test condition failed"); \
125  } \
126 } while(0)
127 #else
128 #define CHECK(cond) do { \
129  if (EXPECT(!(cond), 0)) { \
130  TEST_FAILURE("test condition failed: " #cond); \
131  } \
132 } while(0)
133 #endif
134 
135 /* Like assert(), but when VERIFY is defined. */
136 #if defined(VERIFY)
137 #define VERIFY_CHECK CHECK
138 #else
139 #define VERIFY_CHECK(cond)
140 #endif
141 
142 static SECP256K1_INLINE void *checked_malloc(const secp256k1_callback* cb, size_t size) {
143  void *ret = malloc(size);
144  if (ret == NULL) {
145  secp256k1_callback_call(cb, "Out of memory");
146  }
147  return ret;
148 }
149 
150 #if defined(__BIGGEST_ALIGNMENT__)
151 #define ALIGNMENT __BIGGEST_ALIGNMENT__
152 #else
153 /* Using 16 bytes alignment because common architectures never have alignment
154  * requirements above 8 for any of the types we care about. In addition we
155  * leave some room because currently we don't care about a few bytes. */
156 #define ALIGNMENT 16
157 #endif
158 
159 #define ROUND_TO_ALIGN(size) ((((size) + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT)
160 
161 /* Macro for restrict, when available and not in a VERIFY build. */
162 #if defined(SECP256K1_BUILD) && defined(VERIFY)
163 # define SECP256K1_RESTRICT
164 #else
165 # if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) )
166 # if SECP256K1_GNUC_PREREQ(3,0)
167 # define SECP256K1_RESTRICT __restrict__
168 # elif (defined(_MSC_VER) && _MSC_VER >= 1400)
169 # define SECP256K1_RESTRICT __restrict
170 # else
171 # define SECP256K1_RESTRICT
172 # endif
173 # else
174 # define SECP256K1_RESTRICT restrict
175 # endif
176 #endif
177 
178 #if defined(_WIN32)
179 # define I64FORMAT "I64d"
180 # define I64uFORMAT "I64u"
181 #else
182 # define I64FORMAT "lld"
183 # define I64uFORMAT "llu"
184 #endif
185 
186 #if defined(__GNUC__)
187 # define SECP256K1_GNUC_EXT __extension__
188 #else
189 # define SECP256K1_GNUC_EXT
190 #endif
191 
192 /* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */
193 static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag) {
194  unsigned char *p = (unsigned char *)s;
195  /* Access flag with a volatile-qualified lvalue.
196  This prevents clang from figuring out (after inlining) that flag can
197  take only be 0 or 1, which leads to variable time code. */
198  volatile int vflag = flag;
199  unsigned char mask = -(unsigned char) vflag;
200  while (len) {
201  *p &= ~mask;
202  p++;
203  len--;
204  }
205 }
206 
212 static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n) {
213  const unsigned char *p1 = s1, *p2 = s2;
214  size_t i;
215 
216  for (i = 0; i < n; i++) {
217  int diff = p1[i] - p2[i];
218  if (diff != 0) {
219  return diff;
220  }
221  }
222  return 0;
223 }
224 
226 static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
227  unsigned int mask0, mask1, r_masked, a_masked;
228  /* Access flag with a volatile-qualified lvalue.
229  This prevents clang from figuring out (after inlining) that flag can
230  take only be 0 or 1, which leads to variable time code. */
231  volatile int vflag = flag;
232 
233  /* Casting a negative int to unsigned and back to int is implementation defined behavior */
234  VERIFY_CHECK(*r >= 0 && *a >= 0);
235 
236  mask0 = (unsigned int)vflag + ~0u;
237  mask1 = ~mask0;
238  r_masked = ((unsigned int)*r & mask0);
239  a_masked = ((unsigned int)*a & mask1);
240 
241  *r = (int)(r_masked | a_masked);
242 }
243 
244 #if defined(USE_FORCE_WIDEMUL_INT128_STRUCT)
245 /* If USE_FORCE_WIDEMUL_INT128_STRUCT is set, use int128_struct. */
246 # define SECP256K1_WIDEMUL_INT128 1
247 # define SECP256K1_INT128_STRUCT 1
248 #elif defined(USE_FORCE_WIDEMUL_INT128)
249 /* If USE_FORCE_WIDEMUL_INT128 is set, use int128. */
250 # define SECP256K1_WIDEMUL_INT128 1
251 # define SECP256K1_INT128_NATIVE 1
252 #elif defined(USE_FORCE_WIDEMUL_INT64)
253 /* If USE_FORCE_WIDEMUL_INT64 is set, use int64. */
254 # define SECP256K1_WIDEMUL_INT64 1
255 #elif defined(UINT128_MAX) || defined(__SIZEOF_INT128__)
256 /* If a native 128-bit integer type exists, use int128. */
257 # define SECP256K1_WIDEMUL_INT128 1
258 # define SECP256K1_INT128_NATIVE 1
259 #elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64))
260 /* On 64-bit MSVC targets (x86_64 and arm64), use int128_struct
261  * (which has special logic to implement using intrinsics on those systems). */
262 # define SECP256K1_WIDEMUL_INT128 1
263 # define SECP256K1_INT128_STRUCT 1
264 #elif SIZE_MAX > 0xffffffff
265 /* Systems with 64-bit pointers (and thus registers) very likely benefit from
266  * using 64-bit based arithmetic (even if we need to fall back to 32x32->64 based
267  * multiplication logic). */
268 # define SECP256K1_WIDEMUL_INT128 1
269 # define SECP256K1_INT128_STRUCT 1
270 #else
271 /* Lastly, fall back to int64 based arithmetic. */
272 # define SECP256K1_WIDEMUL_INT64 1
273 #endif
274 
275 #ifndef __has_builtin
276 #define __has_builtin(x) 0
277 #endif
278 
279 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x.
280  * This function is only intended to be used as fallback for
281  * secp256k1_ctz32_var, but permits it to be tested separately. */
283  static const uint8_t debruijn[32] = {
284  0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A,
285  0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B,
286  0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B
287  };
288  return debruijn[(uint32_t)((x & -x) * 0x04D7651FU) >> 27];
289 }
290 
291 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x.
292  * This function is only intended to be used as fallback for
293  * secp256k1_ctz64_var, but permits it to be tested separately. */
295  static const uint8_t debruijn[64] = {
296  0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
297  62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
298  63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
299  51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
300  };
301  return debruijn[(uint64_t)((x & -x) * 0x022FDD63CC95386DU) >> 58];
302 }
303 
304 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x. */
305 static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x) {
306  VERIFY_CHECK(x != 0);
307 #if (__has_builtin(__builtin_ctz) || SECP256K1_GNUC_PREREQ(3,4))
308  /* If the unsigned type is sufficient to represent the largest uint32_t, consider __builtin_ctz. */
309  if (((unsigned)UINT32_MAX) == UINT32_MAX) {
310  return __builtin_ctz(x);
311  }
312 #endif
313 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
314  /* Otherwise consider __builtin_ctzl (the unsigned long type is always at least 32 bits). */
315  return __builtin_ctzl(x);
316 #else
317  /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
319 #endif
320 }
321 
322 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x. */
323 static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x) {
324  VERIFY_CHECK(x != 0);
325 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
326  /* If the unsigned long type is sufficient to represent the largest uint64_t, consider __builtin_ctzl. */
327  if (((unsigned long)UINT64_MAX) == UINT64_MAX) {
328  return __builtin_ctzl(x);
329  }
330 #endif
331 #if (__has_builtin(__builtin_ctzll) || SECP256K1_GNUC_PREREQ(3,4))
332  /* Otherwise consider __builtin_ctzll (the unsigned long long type is always at least 64 bits). */
333  return __builtin_ctzll(x);
334 #else
335  /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
337 #endif
338 }
339 
340 /* Read a uint32_t in big endian */
341 SECP256K1_INLINE static uint32_t secp256k1_read_be32(const unsigned char* p) {
342  return (uint32_t)p[0] << 24 |
343  (uint32_t)p[1] << 16 |
344  (uint32_t)p[2] << 8 |
345  (uint32_t)p[3];
346 }
347 
348 /* Write a uint32_t in big endian */
349 SECP256K1_INLINE static void secp256k1_write_be32(unsigned char* p, uint32_t x) {
350  p[3] = x;
351  p[2] = x >> 8;
352  p[1] = x >> 16;
353  p[0] = x >> 24;
354 }
355 
356 /* Read a uint64_t in big endian */
357 SECP256K1_INLINE static uint64_t secp256k1_read_be64(const unsigned char* p) {
358  return (uint64_t)p[0] << 56 |
359  (uint64_t)p[1] << 48 |
360  (uint64_t)p[2] << 40 |
361  (uint64_t)p[3] << 32 |
362  (uint64_t)p[4] << 24 |
363  (uint64_t)p[5] << 16 |
364  (uint64_t)p[6] << 8 |
365  (uint64_t)p[7];
366 }
367 
368 /* Write a uint64_t in big endian */
369 SECP256K1_INLINE static void secp256k1_write_be64(unsigned char* p, uint64_t x) {
370  p[7] = x;
371  p[6] = x >> 8;
372  p[5] = x >> 16;
373  p[4] = x >> 24;
374  p[3] = x >> 32;
375  p[2] = x >> 40;
376  p[1] = x >> 48;
377  p[0] = x >> 56;
378 }
379 
380 #endif /* SECP256K1_UTIL_H */
int ret
void printf(const char *fmt, const Args &... args)
Format list of arguments to std::cout, according to the given format string.
Definition: tinyformat.h:1077
static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x)
Definition: util.h:323
static SECP256K1_INLINE void * checked_malloc(const secp256k1_callback *cb, size_t size)
Definition: util.h:142
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition: util.h:212
static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag)
If flag is true, set *r equal to *a; otherwise leave it.
Definition: util.h:226
static void secp256k1_default_error_callback_fn(const char *str, void *data)
Definition: util.h:82
static const secp256k1_callback default_error_callback
Definition: util.h:97
static SECP256K1_INLINE uint32_t secp256k1_read_be32(const unsigned char *p)
Definition: util.h:341
#define SECP256K1_INLINE
Definition: util.h:48
static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x)
Definition: util.h:305
static SECP256K1_INLINE void secp256k1_write_be32(unsigned char *p, uint32_t x)
Definition: util.h:349
static SECP256K1_INLINE void secp256k1_write_be64(unsigned char *p, uint64_t x)
Definition: util.h:369
static void secp256k1_default_illegal_callback_fn(const char *str, void *data)
Definition: util.h:77
static SECP256K1_INLINE int secp256k1_ctz64_var_debruijn(uint64_t x)
Definition: util.h:294
static void print_buf_plain(const unsigned char *buf, size_t len)
Definition: util.h:28
#define VERIFY_CHECK(cond)
Definition: util.h:139
static SECP256K1_INLINE int secp256k1_ctz32_var_debruijn(uint32_t x)
Definition: util.h:282
static SECP256K1_INLINE uint64_t secp256k1_read_be64(const unsigned char *p)
Definition: util.h:357
static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag)
Definition: util.h:193
static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback *const cb, const char *const text)
Definition: util.h:72
static const secp256k1_callback default_illegal_callback
Definition: util.h:92
void(* fn)(const char *text, void *data)
Definition: util.h:68
const void * data
Definition: util.h:69