Bitcoin ABC 0.26.3
P2P Digital Currency
Loading...
Searching...
No Matches
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
19typedef struct {
20 void (*fn)(const char *text, void* data);
21 const void* data;
23
24static 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
91static 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
99static 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 */
134static 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;
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. */
205static 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
224static 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
238static 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__)
270SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_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. */
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. */
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 */
T GetRand(T nMax=std::numeric_limits< T >::max()) noexcept
Generate a uniform random integer of type T in the range [0..nMax) nMax defaults to std::numeric_limi...
Definition random.h:85
static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x)
Definition util.h:327
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition util.h:224
static SECP256K1_INLINE void * manual_alloc(void **prealloc_ptr, size_t alloc_size, void *base, size_t max_size)
Definition util.h:134
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
#define ALIGNMENT
Definition util.h:113
#define SECP256K1_GNUC_EXT
Definition util.h:176
#define ROUND_TO_ALIGN(size)
Definition util.h:116
static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x)
Definition util.h:309
static SECP256K1_INLINE int secp256k1_ctz64_var_debruijn(uint64_t x)
Definition util.h:298
static SECP256K1_INLINE void * checked_realloc(const secp256k1_callback *cb, void *ptr, size_t size)
Definition util.h:99
#define VERIFY_CHECK(cond)
Definition util.h:68
static SECP256K1_INLINE int secp256k1_ctz32_var_debruijn(uint32_t x)
Definition util.h:286
static SECP256K1_INLINE void * checked_malloc(const secp256k1_callback *cb, size_t size)
Definition util.h:91
static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag)
Definition util.h:205
static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback *const cb, const char *const text)
Definition util.h:24
#define SECP256K1_INLINE
Definition secp256k1.h:124
void(* fn)(const char *text, void *data)
Definition util.h:20
const void * data
Definition util.h:21