Bitcoin Core 30.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#include "checkmem.h"
12
13#include <string.h>
14#include <stdlib.h>
15#include <stdint.h>
16#include <stdio.h>
17#include <limits.h>
18#if defined(_MSC_VER)
19/* For SecureZeroMemory */
20#include <Windows.h>
21#endif
22
23#define STR_(x) #x
24#define STR(x) STR_(x)
25#define DEBUG_CONFIG_MSG(x) "DEBUG_CONFIG: " x
26#define DEBUG_CONFIG_DEF(x) DEBUG_CONFIG_MSG(#x "=" STR(x))
27
28/* Debug helper for printing arrays of unsigned char. */
29#define PRINT_BUF(buf, len) do { \
30 printf("%s[%lu] = ", #buf, (unsigned long)len); \
31 print_buf_plain(buf, len); \
32} while(0)
33
34static void print_buf_plain(const unsigned char *buf, size_t len) {
35 size_t i;
36 printf("{");
37 for (i = 0; i < len; i++) {
38 if (i % 8 == 0) {
39 printf("\n ");
40 } else {
41 printf(" ");
42 }
43 printf("0x%02X,", buf[i]);
44 }
45 printf("\n}\n");
46}
47
48# if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) )
49# if SECP256K1_GNUC_PREREQ(2,7)
50# define SECP256K1_INLINE __inline__
51# elif (defined(_MSC_VER))
52# define SECP256K1_INLINE __inline
53# else
54# define SECP256K1_INLINE
55# endif
56# else
57# define SECP256K1_INLINE inline
58# endif
59
64#define STATIC_ASSERT(expr) do { \
65 switch(0) { \
66 case 0: \
67 /* If expr evaluates to 0, we have two case labels "0", which is illegal. */ \
68 case /* ERROR: static assertion failed */ (expr): \
69 ; \
70 } \
71} while(0)
72
77#define ASSERT_INT_CONST_AND_DO(expr, stmt) do { \
78 switch(42) { \
79 /* C allows only integer constant expressions as case labels. */ \
80 case /* ERROR: integer argument is not constant */ (expr): \
81 break; \
82 default: ; \
83 } \
84 stmt; \
85} while(0)
86
87typedef struct {
88 void (*fn)(const char *text, void* data);
89 const void* data;
91
92static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback * const cb, const char * const text) {
93 cb->fn(text, (void*)cb->data);
94}
95
96#ifndef USE_EXTERNAL_DEFAULT_CALLBACKS
97static void secp256k1_default_illegal_callback_fn(const char* str, void* data) {
98 (void)data;
99 fprintf(stderr, "[libsecp256k1] illegal argument: %s\n", str);
100 abort();
101}
102static void secp256k1_default_error_callback_fn(const char* str, void* data) {
103 (void)data;
104 fprintf(stderr, "[libsecp256k1] internal consistency check failed: %s\n", str);
105 abort();
106}
107#else
108void secp256k1_default_illegal_callback_fn(const char* str, void* data);
109void secp256k1_default_error_callback_fn(const char* str, void* data);
110#endif
111
114 NULL
115};
116
119 NULL
120};
121
122
123#ifdef DETERMINISTIC
124#define TEST_FAILURE(msg) do { \
125 fprintf(stderr, "%s\n", msg); \
126 abort(); \
127} while(0);
128#else
129#define TEST_FAILURE(msg) do { \
130 fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, msg); \
131 abort(); \
132} while(0)
133#endif
134
135#if SECP256K1_GNUC_PREREQ(3, 0)
136#define EXPECT(x,c) __builtin_expect((x),(c))
137#else
138#define EXPECT(x,c) (x)
139#endif
140
141#ifdef DETERMINISTIC
142#define CHECK(cond) do { \
143 if (EXPECT(!(cond), 0)) { \
144 TEST_FAILURE("test condition failed"); \
145 } \
146} while(0)
147#else
148#define CHECK(cond) do { \
149 if (EXPECT(!(cond), 0)) { \
150 TEST_FAILURE("test condition failed: " #cond); \
151 } \
152} while(0)
153#endif
154
155/* Like assert(), but when VERIFY is defined. */
156#if defined(VERIFY)
157#define VERIFY_CHECK CHECK
158#else
159#define VERIFY_CHECK(cond)
160#endif
161
162static SECP256K1_INLINE void *checked_malloc(const secp256k1_callback* cb, size_t size) {
163 void *ret = malloc(size);
164 if (ret == NULL) {
165 secp256k1_callback_call(cb, "Out of memory");
166 }
167 return ret;
168}
169
170#if defined(__BIGGEST_ALIGNMENT__)
171#define ALIGNMENT __BIGGEST_ALIGNMENT__
172#else
173/* Using 16 bytes alignment because common architectures never have alignment
174 * requirements above 8 for any of the types we care about. In addition we
175 * leave some room because currently we don't care about a few bytes. */
176#define ALIGNMENT 16
177#endif
178
179/* ceil(x/y) for integers x > 0 and y > 0. Here, / denotes rational division. */
180#define CEIL_DIV(x, y) (1 + ((x) - 1) / (y))
181
182#define ROUND_TO_ALIGN(size) (CEIL_DIV(size, ALIGNMENT) * ALIGNMENT)
183
184/* Macro for restrict, when available and not in a VERIFY build. */
185#if defined(SECP256K1_BUILD) && defined(VERIFY)
186# define SECP256K1_RESTRICT
187#else
188# if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) )
189# if SECP256K1_GNUC_PREREQ(3,0)
190# define SECP256K1_RESTRICT __restrict__
191# elif (defined(_MSC_VER) && _MSC_VER >= 1400)
192# define SECP256K1_RESTRICT __restrict
193# else
194# define SECP256K1_RESTRICT
195# endif
196# else
197# define SECP256K1_RESTRICT restrict
198# endif
199#endif
200
201#if defined(__GNUC__)
202# define SECP256K1_GNUC_EXT __extension__
203#else
204# define SECP256K1_GNUC_EXT
205#endif
206
207/* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */
208static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag) {
209 unsigned char *p = (unsigned char *)s;
210 /* Access flag with a volatile-qualified lvalue.
211 This prevents clang from figuring out (after inlining) that flag can
212 take only be 0 or 1, which leads to variable time code. */
213 volatile int vflag = flag;
214 unsigned char mask = -(unsigned char) vflag;
215 while (len) {
216 *p &= ~mask;
217 p++;
218 len--;
219 }
220}
221
222/* Zeroes memory to prevent leaking sensitive info. Won't be optimized out. */
223static SECP256K1_INLINE void secp256k1_memzero_explicit(void *ptr, size_t len) {
224#if defined(_MSC_VER)
225 /* SecureZeroMemory is guaranteed not to be optimized out by MSVC. */
226 SecureZeroMemory(ptr, len);
227#elif defined(__GNUC__)
228 /* We use a memory barrier that scares the compiler away from optimizing out the memset.
229 *
230 * Quoting Adam Langley <agl@google.com> in commit ad1907fe73334d6c696c8539646c21b11178f20f
231 * in BoringSSL (ISC License):
232 * As best as we can tell, this is sufficient to break any optimisations that
233 * might try to eliminate "superfluous" memsets.
234 * This method is used in memzero_explicit() the Linux kernel, too. Its advantage is that it
235 * is pretty efficient, because the compiler can still implement the memset() efficiently,
236 * just not remove it entirely. See "Dead Store Elimination (Still) Considered Harmful" by
237 * Yang et al. (USENIX Security 2017) for more background.
238 */
239 memset(ptr, 0, len);
240 __asm__ __volatile__("" : : "r"(ptr) : "memory");
241#else
242 void *(*volatile const volatile_memset)(void *, int, size_t) = memset;
243 volatile_memset(ptr, 0, len);
244#endif
245}
246
247/* Cleanses memory to prevent leaking sensitive info. Won't be optimized out.
248 * The state of the memory after this call is unspecified so callers must not
249 * make any assumptions about its contents.
250 *
251 * In VERIFY builds, it has the side effect of marking the memory as undefined.
252 * This helps to detect use-after-clear bugs where code incorrectly reads from
253 * cleansed memory during testing.
254 */
255static SECP256K1_INLINE void secp256k1_memclear_explicit(void *ptr, size_t len) {
256 /* The current implementation zeroes, but callers must not rely on this */
258#ifdef VERIFY
260#endif
261}
262
268static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n) {
269 const unsigned char *p1 = s1, *p2 = s2;
270 size_t i;
271
272 for (i = 0; i < n; i++) {
273 int diff = p1[i] - p2[i];
274 if (diff != 0) {
275 return diff;
276 }
277 }
278 return 0;
279}
280
281/* Return 1 if all elements of array s are 0 and otherwise return 0.
282 * Constant-time. */
283static SECP256K1_INLINE int secp256k1_is_zero_array(const unsigned char *s, size_t len) {
284 unsigned char acc = 0;
285 int ret;
286 size_t i;
287
288 for (i = 0; i < len; i++) {
289 acc |= s[i];
290 }
291 ret = (acc == 0);
292 /* acc may contain secret values. Try to explicitly clear it. */
293 secp256k1_memclear_explicit(&acc, sizeof(acc));
294 return ret;
295}
296
298static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
299 unsigned int mask0, mask1, r_masked, a_masked;
300 /* Access flag with a volatile-qualified lvalue.
301 This prevents clang from figuring out (after inlining) that flag can
302 take only be 0 or 1, which leads to variable time code. */
303 volatile int vflag = flag;
304
305 /* Casting a negative int to unsigned and back to int is implementation defined behavior */
306 VERIFY_CHECK(*r >= 0 && *a >= 0);
307
308 mask0 = (unsigned int)vflag + ~0u;
309 mask1 = ~mask0;
310 r_masked = ((unsigned int)*r & mask0);
311 a_masked = ((unsigned int)*a & mask1);
312
313 *r = (int)(r_masked | a_masked);
314}
315
316#if defined(USE_FORCE_WIDEMUL_INT128_STRUCT)
317/* If USE_FORCE_WIDEMUL_INT128_STRUCT is set, use int128_struct. */
318# define SECP256K1_WIDEMUL_INT128 1
319# define SECP256K1_INT128_STRUCT 1
320#elif defined(USE_FORCE_WIDEMUL_INT128)
321/* If USE_FORCE_WIDEMUL_INT128 is set, use int128. */
322# define SECP256K1_WIDEMUL_INT128 1
323# define SECP256K1_INT128_NATIVE 1
324#elif defined(USE_FORCE_WIDEMUL_INT64)
325/* If USE_FORCE_WIDEMUL_INT64 is set, use int64. */
326# define SECP256K1_WIDEMUL_INT64 1
327#elif defined(UINT128_MAX) || defined(__SIZEOF_INT128__)
328/* If a native 128-bit integer type exists, use int128. */
329# define SECP256K1_WIDEMUL_INT128 1
330# define SECP256K1_INT128_NATIVE 1
331#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64))
332/* On 64-bit MSVC targets (x86_64 and arm64), use int128_struct
333 * (which has special logic to implement using intrinsics on those systems). */
334# define SECP256K1_WIDEMUL_INT128 1
335# define SECP256K1_INT128_STRUCT 1
336#elif SIZE_MAX > 0xffffffff
337/* Systems with 64-bit pointers (and thus registers) very likely benefit from
338 * using 64-bit based arithmetic (even if we need to fall back to 32x32->64 based
339 * multiplication logic). */
340# define SECP256K1_WIDEMUL_INT128 1
341# define SECP256K1_INT128_STRUCT 1
342#else
343/* Lastly, fall back to int64 based arithmetic. */
344# define SECP256K1_WIDEMUL_INT64 1
345#endif
346
347#ifndef __has_builtin
348#define __has_builtin(x) 0
349#endif
350
351/* Determine the number of trailing zero bits in a (non-zero) 32-bit x.
352 * This function is only intended to be used as fallback for
353 * secp256k1_ctz32_var, but permits it to be tested separately. */
355 static const uint8_t debruijn[32] = {
356 0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A,
357 0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B,
358 0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B
359 };
360 return debruijn[(uint32_t)((x & -x) * 0x04D7651FU) >> 27];
361}
362
363/* Determine the number of trailing zero bits in a (non-zero) 64-bit x.
364 * This function is only intended to be used as fallback for
365 * secp256k1_ctz64_var, but permits it to be tested separately. */
367 static const uint8_t debruijn[64] = {
368 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
369 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
370 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
371 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
372 };
373 return debruijn[(uint64_t)((x & -x) * 0x022FDD63CC95386DU) >> 58];
374}
375
376/* Determine the number of trailing zero bits in a (non-zero) 32-bit x. */
377static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x) {
378 VERIFY_CHECK(x != 0);
379#if (__has_builtin(__builtin_ctz) || SECP256K1_GNUC_PREREQ(3,4))
380 /* If the unsigned type is sufficient to represent the largest uint32_t, consider __builtin_ctz. */
381 if (((unsigned)UINT32_MAX) == UINT32_MAX) {
382 return __builtin_ctz(x);
383 }
384#endif
385#if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
386 /* Otherwise consider __builtin_ctzl (the unsigned long type is always at least 32 bits). */
387 return __builtin_ctzl(x);
388#else
389 /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
391#endif
392}
393
394/* Determine the number of trailing zero bits in a (non-zero) 64-bit x. */
395static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x) {
396 VERIFY_CHECK(x != 0);
397#if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
398 /* If the unsigned long type is sufficient to represent the largest uint64_t, consider __builtin_ctzl. */
399 if (((unsigned long)UINT64_MAX) == UINT64_MAX) {
400 return __builtin_ctzl(x);
401 }
402#endif
403#if (__has_builtin(__builtin_ctzll) || SECP256K1_GNUC_PREREQ(3,4))
404 /* Otherwise consider __builtin_ctzll (the unsigned long long type is always at least 64 bits). */
405 return __builtin_ctzll(x);
406#else
407 /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
409#endif
410}
411
412/* Read a uint32_t in big endian */
413SECP256K1_INLINE static uint32_t secp256k1_read_be32(const unsigned char* p) {
414 return (uint32_t)p[0] << 24 |
415 (uint32_t)p[1] << 16 |
416 (uint32_t)p[2] << 8 |
417 (uint32_t)p[3];
418}
419
420/* Write a uint32_t in big endian */
421SECP256K1_INLINE static void secp256k1_write_be32(unsigned char* p, uint32_t x) {
422 p[3] = x;
423 p[2] = x >> 8;
424 p[1] = x >> 16;
425 p[0] = x >> 24;
426}
427
428/* Read a uint64_t in big endian */
429SECP256K1_INLINE static uint64_t secp256k1_read_be64(const unsigned char* p) {
430 return (uint64_t)p[0] << 56 |
431 (uint64_t)p[1] << 48 |
432 (uint64_t)p[2] << 40 |
433 (uint64_t)p[3] << 32 |
434 (uint64_t)p[4] << 24 |
435 (uint64_t)p[5] << 16 |
436 (uint64_t)p[6] << 8 |
437 (uint64_t)p[7];
438}
439
440/* Write a uint64_t in big endian */
441SECP256K1_INLINE static void secp256k1_write_be64(unsigned char* p, uint64_t x) {
442 p[7] = x;
443 p[6] = x >> 8;
444 p[5] = x >> 16;
445 p[4] = x >> 24;
446 p[3] = x >> 32;
447 p[2] = x >> 40;
448 p[1] = x >> 48;
449 p[0] = x >> 56;
450}
451
452/* Rotate a uint32_t to the right. */
453SECP256K1_INLINE static uint32_t secp256k1_rotr32(const uint32_t x, const unsigned int by) {
454#if defined(_MSC_VER)
455 return _rotr(x, by); /* needs <stdlib.h> */
456#else
457 /* Reduce rotation amount to avoid UB when shifting. */
458 const unsigned int mask = CHAR_BIT * sizeof(x) - 1;
459 /* Turned into a rot instruction by GCC and clang. */
460 return (x >> (by & mask)) | (x << ((-by) & mask));
461#endif
462}
463
464#endif /* SECP256K1_UTIL_H */
int ret
#define SECP256K1_CHECKMEM_UNDEFINE(p, len)
Definition: checkmem.h:100
void printf(FormatStringCheck< sizeof...(Args)> fmt, const Args &... args)
Format list of arguments to std::cout, according to the given format string.
Definition: tinyformat.h:1096
static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x)
Definition: util.h:395
static SECP256K1_INLINE void secp256k1_memclear_explicit(void *ptr, size_t len)
Definition: util.h:255
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition: util.h:268
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:298
static SECP256K1_INLINE void secp256k1_memzero_explicit(void *ptr, size_t len)
Definition: util.h:223
static void secp256k1_default_error_callback_fn(const char *str, void *data)
Definition: util.h:102
static SECP256K1_INLINE int secp256k1_is_zero_array(const unsigned char *s, size_t len)
Definition: util.h:283
static const secp256k1_callback default_error_callback
Definition: util.h:117
static SECP256K1_INLINE uint32_t secp256k1_read_be32(const unsigned char *p)
Definition: util.h:413
#define SECP256K1_INLINE
Definition: util.h:54
static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x)
Definition: util.h:377
static SECP256K1_INLINE void secp256k1_write_be32(unsigned char *p, uint32_t x)
Definition: util.h:421
static SECP256K1_INLINE void secp256k1_write_be64(unsigned char *p, uint64_t x)
Definition: util.h:441
static SECP256K1_INLINE uint32_t secp256k1_rotr32(const uint32_t x, const unsigned int by)
Definition: util.h:453
static void secp256k1_default_illegal_callback_fn(const char *str, void *data)
Definition: util.h:97
static SECP256K1_INLINE int secp256k1_ctz64_var_debruijn(uint64_t x)
Definition: util.h:366
static void print_buf_plain(const unsigned char *buf, size_t len)
Definition: util.h:34
#define VERIFY_CHECK(cond)
Definition: util.h:159
static SECP256K1_INLINE int secp256k1_ctz32_var_debruijn(uint32_t x)
Definition: util.h:354
static SECP256K1_INLINE uint64_t secp256k1_read_be64(const unsigned char *p)
Definition: util.h:429
static SECP256K1_INLINE void * checked_malloc(const secp256k1_callback *cb, size_t size)
Definition: util.h:162
static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag)
Definition: util.h:208
static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback *const cb, const char *const text)
Definition: util.h:92
static const secp256k1_callback default_illegal_callback
Definition: util.h:112
void(* fn)(const char *text, void *data)
Definition: util.h:88
const void * data
Definition: util.h:89