Electroneum
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 <stdlib.h>
11 #include <stdint.h>
12 #include <stdio.h>
13 #include <limits.h>
14 
15 #define STR_(x) #x
16 #define STR(x) STR_(x)
17 #define DEBUG_CONFIG_MSG(x) "DEBUG_CONFIG: " x
18 #define DEBUG_CONFIG_DEF(x) DEBUG_CONFIG_MSG(#x "=" STR(x))
19 
20 typedef struct {
21  void (*fn)(const char *text, void* data);
22  const void* data;
24 
25 static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback * const cb, const char * const text) {
26  cb->fn(text, (void*)cb->data);
27 }
28 
29 #ifndef USE_EXTERNAL_DEFAULT_CALLBACKS
30 static void secp256k1_default_illegal_callback_fn(const char* str, void* data) {
31  (void)data;
32  fprintf(stderr, "[libsecp256k1] illegal argument: %s\n", str);
33  abort();
34 }
35 static void secp256k1_default_error_callback_fn(const char* str, void* data) {
36  (void)data;
37  fprintf(stderr, "[libsecp256k1] internal consistency check failed: %s\n", str);
38  abort();
39 }
40 #else
41 void secp256k1_default_illegal_callback_fn(const char* str, void* data);
42 void secp256k1_default_error_callback_fn(const char* str, void* data);
43 #endif
44 
45 static const secp256k1_callback default_illegal_callback = {
46  secp256k1_default_illegal_callback_fn,
47  NULL
48 };
49 
50 static const secp256k1_callback default_error_callback = {
51  secp256k1_default_error_callback_fn,
52  NULL
53 };
54 
55 
56 #ifdef DETERMINISTIC
57 #define TEST_FAILURE(msg) do { \
58  fprintf(stderr, "%s\n", msg); \
59  abort(); \
60 } while(0);
61 #else
62 #define TEST_FAILURE(msg) do { \
63  fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, msg); \
64  abort(); \
65 } while(0)
66 #endif
67 
68 #if SECP256K1_GNUC_PREREQ(3, 0)
69 #define EXPECT(x,c) __builtin_expect((x),(c))
70 #else
71 #define EXPECT(x,c) (x)
72 #endif
73 
74 #ifdef DETERMINISTIC
75 #define CHECK(cond) do { \
76  if (EXPECT(!(cond), 0)) { \
77  TEST_FAILURE("test condition failed"); \
78  } \
79 } while(0)
80 #else
81 #define CHECK(cond) do { \
82  if (EXPECT(!(cond), 0)) { \
83  TEST_FAILURE("test condition failed: " #cond); \
84  } \
85 } while(0)
86 #endif
87 
88 /* Like assert(), but when VERIFY is defined, and side-effect safe. */
89 #if defined(COVERAGE)
90 #define VERIFY_CHECK(check)
91 #define VERIFY_SETUP(stmt)
92 #elif defined(VERIFY)
93 #define VERIFY_CHECK CHECK
94 #define VERIFY_SETUP(stmt) do { stmt; } while(0)
95 #else
96 #define VERIFY_CHECK(cond) do { (void)(cond); } while(0)
97 #define VERIFY_SETUP(stmt)
98 #endif
99 
100 static SECP256K1_INLINE void *checked_malloc(const secp256k1_callback* cb, size_t size) {
101  void *ret = malloc(size);
102  if (ret == NULL) {
103  secp256k1_callback_call(cb, "Out of memory");
104  }
105  return ret;
106 }
107 
108 static SECP256K1_INLINE void *checked_realloc(const secp256k1_callback* cb, void *ptr, size_t size) {
109  void *ret = realloc(ptr, size);
110  if (ret == NULL) {
111  secp256k1_callback_call(cb, "Out of memory");
112  }
113  return ret;
114 }
115 
116 #if defined(__BIGGEST_ALIGNMENT__)
117 #define ALIGNMENT __BIGGEST_ALIGNMENT__
118 #else
119 /* Using 16 bytes alignment because common architectures never have alignment
120  * requirements above 8 for any of the types we care about. In addition we
121  * leave some room because currently we don't care about a few bytes. */
122 #define ALIGNMENT 16
123 #endif
124 
125 #define ROUND_TO_ALIGN(size) ((((size) + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT)
126 
127 /* Macro for restrict, when available and not in a VERIFY build. */
128 #if defined(SECP256K1_BUILD) && defined(VERIFY)
129 # define SECP256K1_RESTRICT
130 #else
131 # if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) )
132 # if SECP256K1_GNUC_PREREQ(3,0)
133 # define SECP256K1_RESTRICT __restrict__
134 # elif (defined(_MSC_VER) && _MSC_VER >= 1400)
135 # define SECP256K1_RESTRICT __restrict
136 # else
137 # define SECP256K1_RESTRICT
138 # endif
139 # else
140 # define SECP256K1_RESTRICT restrict
141 # endif
142 #endif
143 
144 #if defined(_WIN32)
145 # define I64FORMAT "I64d"
146 # define I64uFORMAT "I64u"
147 #else
148 # define I64FORMAT "lld"
149 # define I64uFORMAT "llu"
150 #endif
151 
152 #if defined(__GNUC__)
153 # define SECP256K1_GNUC_EXT __extension__
154 #else
155 # define SECP256K1_GNUC_EXT
156 #endif
157 
158 /* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */
159 static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag) {
160  unsigned char *p = (unsigned char *)s;
161  /* Access flag with a volatile-qualified lvalue.
162  This prevents clang from figuring out (after inlining) that flag can
163  take only be 0 or 1, which leads to variable time code. */
164  volatile int vflag = flag;
165  unsigned char mask = -(unsigned char) vflag;
166  while (len) {
167  *p &= ~mask;
168  p++;
169  len--;
170  }
171 }
172 
178 static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n) {
179  const unsigned char *p1 = s1, *p2 = s2;
180  size_t i;
181 
182  for (i = 0; i < n; i++) {
183  int diff = p1[i] - p2[i];
184  if (diff != 0) {
185  return diff;
186  }
187  }
188  return 0;
189 }
190 
192 static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
193  unsigned int mask0, mask1, r_masked, a_masked;
194  /* Access flag with a volatile-qualified lvalue.
195  This prevents clang from figuring out (after inlining) that flag can
196  take only be 0 or 1, which leads to variable time code. */
197  volatile int vflag = flag;
198 
199  /* Casting a negative int to unsigned and back to int is implementation defined behavior */
200  VERIFY_CHECK(*r >= 0 && *a >= 0);
201 
202  mask0 = (unsigned int)vflag + ~0u;
203  mask1 = ~mask0;
204  r_masked = ((unsigned int)*r & mask0);
205  a_masked = ((unsigned int)*a & mask1);
206 
207  *r = (int)(r_masked | a_masked);
208 }
209 
210 #if defined(USE_FORCE_WIDEMUL_INT128_STRUCT)
211 /* If USE_FORCE_WIDEMUL_INT128_STRUCT is set, use int128_struct. */
212 # define SECP256K1_WIDEMUL_INT128 1
213 # define SECP256K1_INT128_STRUCT 1
214 #elif defined(USE_FORCE_WIDEMUL_INT128)
215 /* If USE_FORCE_WIDEMUL_INT128 is set, use int128. */
216 # define SECP256K1_WIDEMUL_INT128 1
217 # define SECP256K1_INT128_NATIVE 1
218 #elif defined(USE_FORCE_WIDEMUL_INT64)
219 /* If USE_FORCE_WIDEMUL_INT64 is set, use int64. */
220 # define SECP256K1_WIDEMUL_INT64 1
221 #elif defined(UINT128_MAX) || defined(__SIZEOF_INT128__)
222 /* If a native 128-bit integer type exists, use int128. */
223 # define SECP256K1_WIDEMUL_INT128 1
224 # define SECP256K1_INT128_NATIVE 1
225 #elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64))
226 /* On 64-bit MSVC targets (x86_64 and arm64), use int128_struct
227  * (which has special logic to implement using intrinsics on those systems). */
228 # define SECP256K1_WIDEMUL_INT128 1
229 # define SECP256K1_INT128_STRUCT 1
230 #elif SIZE_MAX > 0xffffffff
231 /* Systems with 64-bit pointers (and thus registers) very likely benefit from
232  * using 64-bit based arithmetic (even if we need to fall back to 32x32->64 based
233  * multiplication logic). */
234 # define SECP256K1_WIDEMUL_INT128 1
235 # define SECP256K1_INT128_STRUCT 1
236 #else
237 /* Lastly, fall back to int64 based arithmetic. */
238 # define SECP256K1_WIDEMUL_INT64 1
239 #endif
240 
241 #ifndef __has_builtin
242 #define __has_builtin(x) 0
243 #endif
244 
245 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x.
246  * This function is only intended to be used as fallback for
247  * secp256k1_ctz32_var, but permits it to be tested separately. */
248 static SECP256K1_INLINE int secp256k1_ctz32_var_debruijn(uint32_t x) {
249  static const uint8_t debruijn[32] = {
250  0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A,
251  0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B,
252  0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B
253  };
254  return debruijn[((x & -x) * 0x04D7651F) >> 27];
255 }
256 
257 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x.
258  * This function is only intended to be used as fallback for
259  * secp256k1_ctz64_var, but permits it to be tested separately. */
260 static SECP256K1_INLINE int secp256k1_ctz64_var_debruijn(uint64_t x) {
261  static const uint8_t debruijn[64] = {
262  0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
263  62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
264  63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
265  51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
266  };
267  return debruijn[((x & -x) * 0x022FDD63CC95386D) >> 58];
268 }
269 
270 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x. */
271 static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x) {
272  VERIFY_CHECK(x != 0);
273 #if (__has_builtin(__builtin_ctz) || SECP256K1_GNUC_PREREQ(3,4))
274  /* If the unsigned type is sufficient to represent the largest uint32_t, consider __builtin_ctz. */
275  if (((unsigned)UINT32_MAX) == UINT32_MAX) {
276  return __builtin_ctz(x);
277  }
278 #endif
279 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
280  /* Otherwise consider __builtin_ctzl (the unsigned long type is always at least 32 bits). */
281  return __builtin_ctzl(x);
282 #else
283  /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
284  return secp256k1_ctz32_var_debruijn(x);
285 #endif
286 }
287 
288 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x. */
289 static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x) {
290  VERIFY_CHECK(x != 0);
291 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
292  /* If the unsigned long type is sufficient to represent the largest uint64_t, consider __builtin_ctzl. */
293  if (((unsigned long)UINT64_MAX) == UINT64_MAX) {
294  return __builtin_ctzl(x);
295  }
296 #endif
297 #if (__has_builtin(__builtin_ctzll) || SECP256K1_GNUC_PREREQ(3,4))
298  /* Otherwise consider __builtin_ctzll (the unsigned long long type is always at least 64 bits). */
299  return __builtin_ctzll(x);
300 #else
301  /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
302  return secp256k1_ctz64_var_debruijn(x);
303 #endif
304 }
305 
306 /* Read a uint32_t in big endian */
307 SECP256K1_INLINE static uint32_t secp256k1_read_be32(const unsigned char* p) {
308  return (uint32_t)p[0] << 24 |
309  (uint32_t)p[1] << 16 |
310  (uint32_t)p[2] << 8 |
311  (uint32_t)p[3];
312 }
313 
314 /* Write a uint32_t in big endian */
315 SECP256K1_INLINE static void secp256k1_write_be32(unsigned char* p, uint32_t x) {
316  p[3] = x;
317  p[2] = x >> 8;
318  p[1] = x >> 16;
319  p[0] = x >> 24;
320 }
321 
322 #endif /* SECP256K1_UTIL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:96
void(* fn)(const char *text, void *data)
Definition: util.h:21
unsigned char uint8_t
Definition: stdint.h:124
#define SECP256K1_INLINE
Definition: secp256k1.h:131
unsigned int uint32_t
Definition: stdint.h:126
unsigned __int64 uint64_t
Definition: stdint.h:136
#define UINT64_MAX
Definition: stdint.h:189
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
#define UINT32_MAX
Definition: stdint.h:188
const void * data
Definition: util.h:22