Bitcoin Core  24.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 /* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */
177 static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag) {
178  unsigned char *p = (unsigned char *)s;
179  /* Access flag with a volatile-qualified lvalue.
180  This prevents clang from figuring out (after inlining) that flag can
181  take only be 0 or 1, which leads to variable time code. */
182  volatile int vflag = flag;
183  unsigned char mask = -(unsigned char) vflag;
184  while (len) {
185  *p &= ~mask;
186  p++;
187  len--;
188  }
189 }
190 
196 static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n) {
197  const unsigned char *p1 = s1, *p2 = s2;
198  size_t i;
199 
200  for (i = 0; i < n; i++) {
201  int diff = p1[i] - p2[i];
202  if (diff != 0) {
203  return diff;
204  }
205  }
206  return 0;
207 }
208 
210 static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
211  unsigned int mask0, mask1, r_masked, a_masked;
212  /* Access flag with a volatile-qualified lvalue.
213  This prevents clang from figuring out (after inlining) that flag can
214  take only be 0 or 1, which leads to variable time code. */
215  volatile int vflag = flag;
216 
217  /* Casting a negative int to unsigned and back to int is implementation defined behavior */
218  VERIFY_CHECK(*r >= 0 && *a >= 0);
219 
220  mask0 = (unsigned int)vflag + ~0u;
221  mask1 = ~mask0;
222  r_masked = ((unsigned int)*r & mask0);
223  a_masked = ((unsigned int)*a & mask1);
224 
225  *r = (int)(r_masked | a_masked);
226 }
227 
228 /* If USE_FORCE_WIDEMUL_{INT128,INT64} is set, use that wide multiplication implementation.
229  * Otherwise use the presence of __SIZEOF_INT128__ to decide.
230  */
231 #if defined(USE_FORCE_WIDEMUL_INT128)
232 # define SECP256K1_WIDEMUL_INT128 1
233 #elif defined(USE_FORCE_WIDEMUL_INT64)
234 # define SECP256K1_WIDEMUL_INT64 1
235 #elif defined(UINT128_MAX) || defined(__SIZEOF_INT128__)
236 # define SECP256K1_WIDEMUL_INT128 1
237 #else
238 # define SECP256K1_WIDEMUL_INT64 1
239 #endif
240 #if defined(SECP256K1_WIDEMUL_INT128)
241 # if !defined(UINT128_MAX) && defined(__SIZEOF_INT128__)
242 SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_t;
243 SECP256K1_GNUC_EXT typedef __int128 int128_t;
244 #define UINT128_MAX ((uint128_t)(-1))
245 #define INT128_MAX ((int128_t)(UINT128_MAX >> 1))
246 #define INT128_MIN (-INT128_MAX - 1)
247 /* No (U)INT128_C macros because compilers providing __int128 do not support 128-bit literals. */
248 # endif
249 #endif
250 
251 #ifndef __has_builtin
252 #define __has_builtin(x) 0
253 #endif
254 
255 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x.
256  * This function is only intended to be used as fallback for
257  * secp256k1_ctz32_var, but permits it to be tested separately. */
259  static const uint8_t debruijn[32] = {
260  0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A,
261  0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B,
262  0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B
263  };
264  return debruijn[((x & -x) * 0x04D7651F) >> 27];
265 }
266 
267 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x.
268  * This function is only intended to be used as fallback for
269  * secp256k1_ctz64_var, but permits it to be tested separately. */
271  static const uint8_t debruijn[64] = {
272  0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
273  62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
274  63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
275  51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
276  };
277  return debruijn[((x & -x) * 0x022FDD63CC95386D) >> 58];
278 }
279 
280 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x. */
281 static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x) {
282  VERIFY_CHECK(x != 0);
283 #if (__has_builtin(__builtin_ctz) || SECP256K1_GNUC_PREREQ(3,4))
284  /* If the unsigned type is sufficient to represent the largest uint32_t, consider __builtin_ctz. */
285  if (((unsigned)UINT32_MAX) == UINT32_MAX) {
286  return __builtin_ctz(x);
287  }
288 #endif
289 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
290  /* Otherwise consider __builtin_ctzl (the unsigned long type is always at least 32 bits). */
291  return __builtin_ctzl(x);
292 #else
293  /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
295 #endif
296 }
297 
298 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x. */
299 static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x) {
300  VERIFY_CHECK(x != 0);
301 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
302  /* If the unsigned long type is sufficient to represent the largest uint64_t, consider __builtin_ctzl. */
303  if (((unsigned long)UINT64_MAX) == UINT64_MAX) {
304  return __builtin_ctzl(x);
305  }
306 #endif
307 #if (__has_builtin(__builtin_ctzll) || SECP256K1_GNUC_PREREQ(3,4))
308  /* Otherwise consider __builtin_ctzll (the unsigned long long type is always at least 64 bits). */
309  return __builtin_ctzll(x);
310 #else
311  /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
313 #endif
314 }
315 
316 /* Read a uint32_t in big endian */
317 SECP256K1_INLINE static uint32_t secp256k1_read_be32(const unsigned char* p) {
318  return (uint32_t)p[0] << 24 |
319  (uint32_t)p[1] << 16 |
320  (uint32_t)p[2] << 8 |
321  (uint32_t)p[3];
322 }
323 
324 /* Write a uint32_t in big endian */
325 SECP256K1_INLINE static void secp256k1_write_be32(unsigned char* p, uint32_t x) {
326  p[3] = x;
327  p[2] = x >> 8;
328  p[1] = x >> 16;
329  p[0] = x >> 24;
330 }
331 
332 #endif /* SECP256K1_UTIL_H */
int ret
static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x)
Definition: util.h:299
static SECP256K1_INLINE void * checked_realloc(const secp256k1_callback *cb, void *ptr, size_t size)
Definition: util.h:126
static SECP256K1_INLINE void * checked_malloc(const secp256k1_callback *cb, size_t size)
Definition: util.h:118
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition: util.h:196
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:210
static void secp256k1_default_error_callback_fn(const char *str, void *data)
Definition: util.h:34
#define SECP256K1_GNUC_EXT
Definition: util.h:173
static const secp256k1_callback default_error_callback
Definition: util.h:49
static SECP256K1_INLINE uint32_t secp256k1_read_be32(const unsigned char *p)
Definition: util.h:317
static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x)
Definition: util.h:281
static SECP256K1_INLINE void secp256k1_write_be32(unsigned char *p, uint32_t x)
Definition: util.h:325
static void secp256k1_default_illegal_callback_fn(const char *str, void *data)
Definition: util.h:29
static SECP256K1_INLINE int secp256k1_ctz64_var_debruijn(uint64_t x)
Definition: util.h:270
#define VERIFY_CHECK(cond)
Definition: util.h:95
static SECP256K1_INLINE int secp256k1_ctz32_var_debruijn(uint32_t x)
Definition: util.h:258
static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag)
Definition: util.h:177
static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback *const cb, const char *const text)
Definition: util.h:24
static const secp256k1_callback default_illegal_callback
Definition: util.h:44
#define SECP256K1_INLINE
Definition: secp256k1.h:127
void(* fn)(const char *text, void *data)
Definition: util.h:20
const void * data
Definition: util.h:21