Bitcoin Core  22.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 #if defined HAVE_CONFIG_H
11 #include "libsecp256k1-config.h"
12 #endif
13 
14 #include <stdlib.h>
15 #include <stdint.h>
16 #include <stdio.h>
17 #include <limits.h>
18 
19 typedef struct {
20  void (*fn)(const char *text, void* data);
21  const void* data;
23 
24 static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback * const cb, const char * const text) {
25  cb->fn(text, (void*)cb->data);
26 }
27 
28 #ifndef USE_EXTERNAL_DEFAULT_CALLBACKS
29 static void secp256k1_default_illegal_callback_fn(const char* str, void* data) {
30  (void)data;
31  fprintf(stderr, "[libsecp256k1] illegal argument: %s\n", str);
32  abort();
33 }
34 static void secp256k1_default_error_callback_fn(const char* str, void* data) {
35  (void)data;
36  fprintf(stderr, "[libsecp256k1] internal consistency check failed: %s\n", str);
37  abort();
38 }
39 #else
40 void secp256k1_default_illegal_callback_fn(const char* str, void* data);
41 void secp256k1_default_error_callback_fn(const char* str, void* data);
42 #endif
43 
46  NULL
47 };
48 
51  NULL
52 };
53 
54 
55 #ifdef DETERMINISTIC
56 #define TEST_FAILURE(msg) do { \
57  fprintf(stderr, "%s\n", msg); \
58  abort(); \
59 } while(0);
60 #else
61 #define TEST_FAILURE(msg) do { \
62  fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, msg); \
63  abort(); \
64 } while(0)
65 #endif
66 
67 #if SECP256K1_GNUC_PREREQ(3, 0)
68 #define EXPECT(x,c) __builtin_expect((x),(c))
69 #else
70 #define EXPECT(x,c) (x)
71 #endif
72 
73 #ifdef DETERMINISTIC
74 #define CHECK(cond) do { \
75  if (EXPECT(!(cond), 0)) { \
76  TEST_FAILURE("test condition failed"); \
77  } \
78 } while(0)
79 #else
80 #define CHECK(cond) do { \
81  if (EXPECT(!(cond), 0)) { \
82  TEST_FAILURE("test condition failed: " #cond); \
83  } \
84 } while(0)
85 #endif
86 
87 /* Like assert(), but when VERIFY is defined, and side-effect safe. */
88 #if defined(COVERAGE)
89 #define VERIFY_CHECK(check)
90 #define VERIFY_SETUP(stmt)
91 #elif defined(VERIFY)
92 #define VERIFY_CHECK CHECK
93 #define VERIFY_SETUP(stmt) do { stmt; } while(0)
94 #else
95 #define VERIFY_CHECK(cond) do { (void)(cond); } while(0)
96 #define VERIFY_SETUP(stmt)
97 #endif
98 
99 /* Define `VG_UNDEF` and `VG_CHECK` when VALGRIND is defined */
100 #if !defined(VG_CHECK)
101 # if defined(VALGRIND)
102 # include <valgrind/memcheck.h>
103 # define VG_UNDEF(x,y) VALGRIND_MAKE_MEM_UNDEFINED((x),(y))
104 # define VG_CHECK(x,y) VALGRIND_CHECK_MEM_IS_DEFINED((x),(y))
105 # else
106 # define VG_UNDEF(x,y)
107 # define VG_CHECK(x,y)
108 # endif
109 #endif
110 
111 /* Like `VG_CHECK` but on VERIFY only */
112 #if defined(VERIFY)
113 #define VG_CHECK_VERIFY(x,y) VG_CHECK((x), (y))
114 #else
115 #define VG_CHECK_VERIFY(x,y)
116 #endif
117 
118 static SECP256K1_INLINE void *checked_malloc(const secp256k1_callback* cb, size_t size) {
119  void *ret = malloc(size);
120  if (ret == NULL) {
121  secp256k1_callback_call(cb, "Out of memory");
122  }
123  return ret;
124 }
125 
126 static SECP256K1_INLINE void *checked_realloc(const secp256k1_callback* cb, void *ptr, size_t size) {
127  void *ret = realloc(ptr, size);
128  if (ret == NULL) {
129  secp256k1_callback_call(cb, "Out of memory");
130  }
131  return ret;
132 }
133 
134 #if defined(__BIGGEST_ALIGNMENT__)
135 #define ALIGNMENT __BIGGEST_ALIGNMENT__
136 #else
137 /* Using 16 bytes alignment because common architectures never have alignment
138  * requirements above 8 for any of the types we care about. In addition we
139  * leave some room because currently we don't care about a few bytes. */
140 #define ALIGNMENT 16
141 #endif
142 
143 #define ROUND_TO_ALIGN(size) ((((size) + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT)
144 
145 /* Macro for restrict, when available and not in a VERIFY build. */
146 #if defined(SECP256K1_BUILD) && defined(VERIFY)
147 # define SECP256K1_RESTRICT
148 #else
149 # if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) )
150 # if SECP256K1_GNUC_PREREQ(3,0)
151 # define SECP256K1_RESTRICT __restrict__
152 # elif (defined(_MSC_VER) && _MSC_VER >= 1400)
153 # define SECP256K1_RESTRICT __restrict
154 # else
155 # define SECP256K1_RESTRICT
156 # endif
157 # else
158 # define SECP256K1_RESTRICT restrict
159 # endif
160 #endif
161 
162 #if defined(_WIN32)
163 # define I64FORMAT "I64d"
164 # define I64uFORMAT "I64u"
165 #else
166 # define I64FORMAT "lld"
167 # define I64uFORMAT "llu"
168 #endif
169 
170 #if defined(__GNUC__)
171 # define SECP256K1_GNUC_EXT __extension__
172 #else
173 # define SECP256K1_GNUC_EXT
174 #endif
175 
176 /* If SECP256K1_{LITTLE,BIG}_ENDIAN is not explicitly provided, infer from various other system macros. */
177 #if !defined(SECP256K1_LITTLE_ENDIAN) && !defined(SECP256K1_BIG_ENDIAN)
178 /* Inspired by https://github.com/rofl0r/endianness.h/blob/9853923246b065a3b52d2c43835f3819a62c7199/endianness.h#L52L73 */
179 # if (defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) || \
180  defined(_X86_) || defined(__x86_64__) || defined(__i386__) || \
181  defined(__i486__) || defined(__i586__) || defined(__i686__) || \
182  defined(__MIPSEL) || defined(_MIPSEL) || defined(MIPSEL) || \
183  defined(__ARMEL__) || defined(__AARCH64EL__) || \
184  (defined(__LITTLE_ENDIAN__) && __LITTLE_ENDIAN__ == 1) || \
185  (defined(_LITTLE_ENDIAN) && _LITTLE_ENDIAN == 1) || \
186  defined(_M_IX86) || defined(_M_AMD64) || defined(_M_ARM) /* MSVC */
187 # define SECP256K1_LITTLE_ENDIAN
188 # endif
189 # if (defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) || \
190  defined(__MIPSEB) || defined(_MIPSEB) || defined(MIPSEB) || \
191  defined(__MICROBLAZEEB__) || defined(__ARMEB__) || defined(__AARCH64EB__) || \
192  (defined(__BIG_ENDIAN__) && __BIG_ENDIAN__ == 1) || \
193  (defined(_BIG_ENDIAN) && _BIG_ENDIAN == 1)
194 # define SECP256K1_BIG_ENDIAN
195 # endif
196 #endif
197 #if defined(SECP256K1_LITTLE_ENDIAN) == defined(SECP256K1_BIG_ENDIAN)
198 # error Please make sure that either SECP256K1_LITTLE_ENDIAN or SECP256K1_BIG_ENDIAN is set, see src/util.h.
199 #endif
200 
201 /* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */
202 static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag) {
203  unsigned char *p = (unsigned char *)s;
204  /* Access flag with a volatile-qualified lvalue.
205  This prevents clang from figuring out (after inlining) that flag can
206  take only be 0 or 1, which leads to variable time code. */
207  volatile int vflag = flag;
208  unsigned char mask = -(unsigned char) vflag;
209  while (len) {
210  *p &= ~mask;
211  p++;
212  len--;
213  }
214 }
215 
221 static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n) {
222  const unsigned char *p1 = s1, *p2 = s2;
223  size_t i;
224 
225  for (i = 0; i < n; i++) {
226  int diff = p1[i] - p2[i];
227  if (diff != 0) {
228  return diff;
229  }
230  }
231  return 0;
232 }
233 
235 static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
236  unsigned int mask0, mask1, r_masked, a_masked;
237  /* Access flag with a volatile-qualified lvalue.
238  This prevents clang from figuring out (after inlining) that flag can
239  take only be 0 or 1, which leads to variable time code. */
240  volatile int vflag = flag;
241 
242  /* Casting a negative int to unsigned and back to int is implementation defined behavior */
243  VERIFY_CHECK(*r >= 0 && *a >= 0);
244 
245  mask0 = (unsigned int)vflag + ~0u;
246  mask1 = ~mask0;
247  r_masked = ((unsigned int)*r & mask0);
248  a_masked = ((unsigned int)*a & mask1);
249 
250  *r = (int)(r_masked | a_masked);
251 }
252 
253 /* If USE_FORCE_WIDEMUL_{INT128,INT64} is set, use that wide multiplication implementation.
254  * Otherwise use the presence of __SIZEOF_INT128__ to decide.
255  */
256 #if defined(USE_FORCE_WIDEMUL_INT128)
257 # define SECP256K1_WIDEMUL_INT128 1
258 #elif defined(USE_FORCE_WIDEMUL_INT64)
259 # define SECP256K1_WIDEMUL_INT64 1
260 #elif defined(UINT128_MAX) || defined(__SIZEOF_INT128__)
261 # define SECP256K1_WIDEMUL_INT128 1
262 #else
263 # define SECP256K1_WIDEMUL_INT64 1
264 #endif
265 #if defined(SECP256K1_WIDEMUL_INT128)
266 # if !defined(UINT128_MAX) && defined(__SIZEOF_INT128__)
267 SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_t;
268 SECP256K1_GNUC_EXT typedef __int128 int128_t;
269 #define UINT128_MAX ((uint128_t)(-1))
270 #define INT128_MAX ((int128_t)(UINT128_MAX >> 1))
271 #define INT128_MIN (-INT128_MAX - 1)
272 /* No (U)INT128_C macros because compilers providing __int128 do not support 128-bit literals. */
273 # endif
274 #endif
275 
276 #ifndef __has_builtin
277 #define __has_builtin(x) 0
278 #endif
279 
280 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x.
281  * This function is only intended to be used as fallback for
282  * secp256k1_ctz32_var, but permits it to be tested separately. */
284  static const uint8_t debruijn[32] = {
285  0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A,
286  0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B,
287  0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B
288  };
289  return debruijn[((x & -x) * 0x04D7651F) >> 27];
290 }
291 
292 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x.
293  * This function is only intended to be used as fallback for
294  * secp256k1_ctz64_var, but permits it to be tested separately. */
296  static const uint8_t debruijn[64] = {
297  0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
298  62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
299  63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
300  51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
301  };
302  return debruijn[((x & -x) * 0x022FDD63CC95386D) >> 58];
303 }
304 
305 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x. */
306 static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x) {
307  VERIFY_CHECK(x != 0);
308 #if (__has_builtin(__builtin_ctz) || SECP256K1_GNUC_PREREQ(3,4))
309  /* If the unsigned type is sufficient to represent the largest uint32_t, consider __builtin_ctz. */
310  if (((unsigned)UINT32_MAX) == UINT32_MAX) {
311  return __builtin_ctz(x);
312  }
313 #endif
314 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
315  /* Otherwise consider __builtin_ctzl (the unsigned long type is always at least 32 bits). */
316  return __builtin_ctzl(x);
317 #else
318  /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
320 #endif
321 }
322 
323 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x. */
324 static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x) {
325  VERIFY_CHECK(x != 0);
326 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
327  /* If the unsigned long type is sufficient to represent the largest uint64_t, consider __builtin_ctzl. */
328  if (((unsigned long)UINT64_MAX) == UINT64_MAX) {
329  return __builtin_ctzl(x);
330  }
331 #endif
332 #if (__has_builtin(__builtin_ctzll) || SECP256K1_GNUC_PREREQ(3,4))
333  /* Otherwise consider __builtin_ctzll (the unsigned long long type is always at least 64 bits). */
334  return __builtin_ctzll(x);
335 #else
336  /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
338 #endif
339 }
340 
341 #endif /* SECP256K1_UTIL_H */
VERIFY_CHECK
#define VERIFY_CHECK(cond)
Definition: util.h:95
checked_realloc
static SECP256K1_INLINE void * checked_realloc(const secp256k1_callback *cb, void *ptr, size_t size)
Definition: util.h:126
secp256k1_memcmp_var
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition: util.h:221
secp256k1_ctz64_var
static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x)
Definition: util.h:324
secp256k1_ctz32_var
static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x)
Definition: util.h:306
SECP256K1_GNUC_EXT
#define SECP256K1_GNUC_EXT
Definition: util.h:173
secp256k1_callback::data
const void * data
Definition: util.h:25
checked_malloc
static SECP256K1_INLINE void * checked_malloc(const secp256k1_callback *cb, size_t size)
Definition: util.h:118
secp256k1_ctz32_var_debruijn
static SECP256K1_INLINE int secp256k1_ctz32_var_debruijn(uint32_t x)
Definition: util.h:283
secp256k1_ctz64_var_debruijn
static SECP256K1_INLINE int secp256k1_ctz64_var_debruijn(uint64_t x)
Definition: util.h:295
secp256k1_int_cmov
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:235
secp256k1_memczero
static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag)
Definition: util.h:202
libsecp256k1-config.h
secp256k1_callback::fn
void(* fn)(const char *text, void *data)
Definition: util.h:24
secp256k1_callback
Definition: util.h:19
secp256k1_default_illegal_callback_fn
static void secp256k1_default_illegal_callback_fn(const char *str, void *data)
Definition: util.h:29
SECP256K1_INLINE
#define SECP256K1_INLINE
Definition: secp256k1.h:127
default_illegal_callback
static const secp256k1_callback default_illegal_callback
Definition: util.h:44
secp256k1_default_error_callback_fn
static void secp256k1_default_error_callback_fn(const char *str, void *data)
Definition: util.h:34
default_error_callback
static const secp256k1_callback default_error_callback
Definition: util.h:49
secp256k1_callback_call
static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback *const cb, const char *const text)
Definition: util.h:24