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