util.h (13110B)
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 12 #include <stdlib.h> 13 #include <stdint.h> 14 #include <stdio.h> 15 #include <limits.h> 16 17 #define STR_(x) #x 18 #define STR(x) STR_(x) 19 #define DEBUG_CONFIG_MSG(x) "DEBUG_CONFIG: " x 20 #define DEBUG_CONFIG_DEF(x) DEBUG_CONFIG_MSG(#x "=" STR(x)) 21 22 /* Debug helper for printing arrays of unsigned char. */ 23 #define PRINT_BUF(buf, len) do { \ 24 printf("%s[%lu] = ", #buf, (unsigned long)len); \ 25 print_buf_plain(buf, len); \ 26 } while(0) 27 28 static void print_buf_plain(const unsigned char *buf, size_t len) { 29 size_t i; 30 printf("{"); 31 for (i = 0; i < len; i++) { 32 if (i % 8 == 0) { 33 printf("\n "); 34 } else { 35 printf(" "); 36 } 37 printf("0x%02X,", buf[i]); 38 } 39 printf("\n}\n"); 40 } 41 42 # if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) ) 43 # if SECP256K1_GNUC_PREREQ(2,7) 44 # define SECP256K1_INLINE __inline__ 45 # elif (defined(_MSC_VER)) 46 # define SECP256K1_INLINE __inline 47 # else 48 # define SECP256K1_INLINE 49 # endif 50 # else 51 # define SECP256K1_INLINE inline 52 # endif 53 54 /** Assert statically that expr is true. 55 * 56 * This is a statement-like macro and can only be used inside functions. 57 */ 58 #define STATIC_ASSERT(expr) do { \ 59 switch(0) { \ 60 case 0: \ 61 /* If expr evaluates to 0, we have two case labels "0", which is illegal. */ \ 62 case /* ERROR: static assertion failed */ (expr): \ 63 ; \ 64 } \ 65 } while(0) 66 67 /** Assert statically that expr is an integer constant expression, and run stmt. 68 * 69 * Useful for example to enforce that magnitude arguments are constant. 70 */ 71 #define ASSERT_INT_CONST_AND_DO(expr, stmt) do { \ 72 switch(42) { \ 73 /* C allows only integer constant expressions as case labels. */ \ 74 case /* ERROR: integer argument is not constant */ (expr): \ 75 break; \ 76 default: ; \ 77 } \ 78 stmt; \ 79 } while(0) 80 81 typedef struct { 82 void (*fn)(const char *text, void* data); 83 const void* data; 84 } haskellsecp256k1_v0_1_0_callback; 85 86 static SECP256K1_INLINE void haskellsecp256k1_v0_1_0_callback_call(const haskellsecp256k1_v0_1_0_callback * const cb, const char * const text) { 87 cb->fn(text, (void*)cb->data); 88 } 89 90 #ifndef USE_EXTERNAL_DEFAULT_CALLBACKS 91 static void haskellsecp256k1_v0_1_0_default_illegal_callback_fn(const char* str, void* data) { 92 (void)data; 93 fprintf(stderr, "[libsecp256k1] illegal argument: %s\n", str); 94 abort(); 95 } 96 static void haskellsecp256k1_v0_1_0_default_error_callback_fn(const char* str, void* data) { 97 (void)data; 98 fprintf(stderr, "[libsecp256k1] internal consistency check failed: %s\n", str); 99 abort(); 100 } 101 #else 102 void haskellsecp256k1_v0_1_0_default_illegal_callback_fn(const char* str, void* data); 103 void haskellsecp256k1_v0_1_0_default_error_callback_fn(const char* str, void* data); 104 #endif 105 106 static const haskellsecp256k1_v0_1_0_callback default_illegal_callback = { 107 haskellsecp256k1_v0_1_0_default_illegal_callback_fn, 108 NULL 109 }; 110 111 static const haskellsecp256k1_v0_1_0_callback default_error_callback = { 112 haskellsecp256k1_v0_1_0_default_error_callback_fn, 113 NULL 114 }; 115 116 117 #ifdef DETERMINISTIC 118 #define TEST_FAILURE(msg) do { \ 119 fprintf(stderr, "%s\n", msg); \ 120 abort(); \ 121 } while(0); 122 #else 123 #define TEST_FAILURE(msg) do { \ 124 fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, msg); \ 125 abort(); \ 126 } while(0) 127 #endif 128 129 #if SECP256K1_GNUC_PREREQ(3, 0) 130 #define EXPECT(x,c) __builtin_expect((x),(c)) 131 #else 132 #define EXPECT(x,c) (x) 133 #endif 134 135 #ifdef DETERMINISTIC 136 #define CHECK(cond) do { \ 137 if (EXPECT(!(cond), 0)) { \ 138 TEST_FAILURE("test condition failed"); \ 139 } \ 140 } while(0) 141 #else 142 #define CHECK(cond) do { \ 143 if (EXPECT(!(cond), 0)) { \ 144 TEST_FAILURE("test condition failed: " #cond); \ 145 } \ 146 } while(0) 147 #endif 148 149 /* Like assert(), but when VERIFY is defined. */ 150 #if defined(VERIFY) 151 #define VERIFY_CHECK CHECK 152 #else 153 #define VERIFY_CHECK(cond) 154 #endif 155 156 static SECP256K1_INLINE void *checked_malloc(const haskellsecp256k1_v0_1_0_callback* cb, size_t size) { 157 void *ret = malloc(size); 158 if (ret == NULL) { 159 haskellsecp256k1_v0_1_0_callback_call(cb, "Out of memory"); 160 } 161 return ret; 162 } 163 164 #if defined(__BIGGEST_ALIGNMENT__) 165 #define ALIGNMENT __BIGGEST_ALIGNMENT__ 166 #else 167 /* Using 16 bytes alignment because common architectures never have alignment 168 * requirements above 8 for any of the types we care about. In addition we 169 * leave some room because currently we don't care about a few bytes. */ 170 #define ALIGNMENT 16 171 #endif 172 173 #define ROUND_TO_ALIGN(size) ((((size) + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT) 174 175 /* Macro for restrict, when available and not in a VERIFY build. */ 176 #if defined(SECP256K1_BUILD) && defined(VERIFY) 177 # define SECP256K1_RESTRICT 178 #else 179 # if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) ) 180 # if SECP256K1_GNUC_PREREQ(3,0) 181 # define SECP256K1_RESTRICT __restrict__ 182 # elif (defined(_MSC_VER) && _MSC_VER >= 1400) 183 # define SECP256K1_RESTRICT __restrict 184 # else 185 # define SECP256K1_RESTRICT 186 # endif 187 # else 188 # define SECP256K1_RESTRICT restrict 189 # endif 190 #endif 191 192 #if defined(_WIN32) 193 # define I64FORMAT "I64d" 194 # define I64uFORMAT "I64u" 195 #else 196 # define I64FORMAT "lld" 197 # define I64uFORMAT "llu" 198 #endif 199 200 #if defined(__GNUC__) 201 # define SECP256K1_GNUC_EXT __extension__ 202 #else 203 # define SECP256K1_GNUC_EXT 204 #endif 205 206 /* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */ 207 static SECP256K1_INLINE void haskellsecp256k1_v0_1_0_memczero(void *s, size_t len, int flag) { 208 unsigned char *p = (unsigned char *)s; 209 /* Access flag with a volatile-qualified lvalue. 210 This prevents clang from figuring out (after inlining) that flag can 211 take only be 0 or 1, which leads to variable time code. */ 212 volatile int vflag = flag; 213 unsigned char mask = -(unsigned char) vflag; 214 while (len) { 215 *p &= ~mask; 216 p++; 217 len--; 218 } 219 } 220 221 /** Semantics like memcmp. Variable-time. 222 * 223 * We use this to avoid possible compiler bugs with memcmp, e.g. 224 * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189 225 */ 226 static SECP256K1_INLINE int haskellsecp256k1_v0_1_0_memcmp_var(const void *s1, const void *s2, size_t n) { 227 const unsigned char *p1 = s1, *p2 = s2; 228 size_t i; 229 230 for (i = 0; i < n; i++) { 231 int diff = p1[i] - p2[i]; 232 if (diff != 0) { 233 return diff; 234 } 235 } 236 return 0; 237 } 238 239 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized and non-negative.*/ 240 static SECP256K1_INLINE void haskellsecp256k1_v0_1_0_int_cmov(int *r, const int *a, int flag) { 241 unsigned int mask0, mask1, r_masked, a_masked; 242 /* Access flag with a volatile-qualified lvalue. 243 This prevents clang from figuring out (after inlining) that flag can 244 take only be 0 or 1, which leads to variable time code. */ 245 volatile int vflag = flag; 246 247 /* Casting a negative int to unsigned and back to int is implementation defined behavior */ 248 VERIFY_CHECK(*r >= 0 && *a >= 0); 249 250 mask0 = (unsigned int)vflag + ~0u; 251 mask1 = ~mask0; 252 r_masked = ((unsigned int)*r & mask0); 253 a_masked = ((unsigned int)*a & mask1); 254 255 *r = (int)(r_masked | a_masked); 256 } 257 258 #if defined(USE_FORCE_WIDEMUL_INT128_STRUCT) 259 /* If USE_FORCE_WIDEMUL_INT128_STRUCT is set, use int128_struct. */ 260 # define SECP256K1_WIDEMUL_INT128 1 261 # define SECP256K1_INT128_STRUCT 1 262 #elif defined(USE_FORCE_WIDEMUL_INT128) 263 /* If USE_FORCE_WIDEMUL_INT128 is set, use int128. */ 264 # define SECP256K1_WIDEMUL_INT128 1 265 # define SECP256K1_INT128_NATIVE 1 266 #elif defined(USE_FORCE_WIDEMUL_INT64) 267 /* If USE_FORCE_WIDEMUL_INT64 is set, use int64. */ 268 # define SECP256K1_WIDEMUL_INT64 1 269 #elif defined(UINT128_MAX) || defined(__SIZEOF_INT128__) 270 /* If a native 128-bit integer type exists, use int128. */ 271 # define SECP256K1_WIDEMUL_INT128 1 272 # define SECP256K1_INT128_NATIVE 1 273 #elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64)) 274 /* On 64-bit MSVC targets (x86_64 and arm64), use int128_struct 275 * (which has special logic to implement using intrinsics on those systems). */ 276 # define SECP256K1_WIDEMUL_INT128 1 277 # define SECP256K1_INT128_STRUCT 1 278 #elif SIZE_MAX > 0xffffffff 279 /* Systems with 64-bit pointers (and thus registers) very likely benefit from 280 * using 64-bit based arithmetic (even if we need to fall back to 32x32->64 based 281 * multiplication logic). */ 282 # define SECP256K1_WIDEMUL_INT128 1 283 # define SECP256K1_INT128_STRUCT 1 284 #else 285 /* Lastly, fall back to int64 based arithmetic. */ 286 # define SECP256K1_WIDEMUL_INT64 1 287 #endif 288 289 #ifndef __has_builtin 290 #define __has_builtin(x) 0 291 #endif 292 293 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x. 294 * This function is only intended to be used as fallback for 295 * haskellsecp256k1_v0_1_0_ctz32_var, but permits it to be tested separately. */ 296 static SECP256K1_INLINE int haskellsecp256k1_v0_1_0_ctz32_var_debruijn(uint32_t x) { 297 static const uint8_t debruijn[32] = { 298 0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A, 299 0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B, 300 0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B 301 }; 302 return debruijn[(uint32_t)((x & -x) * 0x04D7651FU) >> 27]; 303 } 304 305 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x. 306 * This function is only intended to be used as fallback for 307 * haskellsecp256k1_v0_1_0_ctz64_var, but permits it to be tested separately. */ 308 static SECP256K1_INLINE int haskellsecp256k1_v0_1_0_ctz64_var_debruijn(uint64_t x) { 309 static const uint8_t debruijn[64] = { 310 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, 311 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, 312 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, 313 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12 314 }; 315 return debruijn[(uint64_t)((x & -x) * 0x022FDD63CC95386DU) >> 58]; 316 } 317 318 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x. */ 319 static SECP256K1_INLINE int haskellsecp256k1_v0_1_0_ctz32_var(uint32_t x) { 320 VERIFY_CHECK(x != 0); 321 #if (__has_builtin(__builtin_ctz) || SECP256K1_GNUC_PREREQ(3,4)) 322 /* If the unsigned type is sufficient to represent the largest uint32_t, consider __builtin_ctz. */ 323 if (((unsigned)UINT32_MAX) == UINT32_MAX) { 324 return __builtin_ctz(x); 325 } 326 #endif 327 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4)) 328 /* Otherwise consider __builtin_ctzl (the unsigned long type is always at least 32 bits). */ 329 return __builtin_ctzl(x); 330 #else 331 /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */ 332 return haskellsecp256k1_v0_1_0_ctz32_var_debruijn(x); 333 #endif 334 } 335 336 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x. */ 337 static SECP256K1_INLINE int haskellsecp256k1_v0_1_0_ctz64_var(uint64_t x) { 338 VERIFY_CHECK(x != 0); 339 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4)) 340 /* If the unsigned long type is sufficient to represent the largest uint64_t, consider __builtin_ctzl. */ 341 if (((unsigned long)UINT64_MAX) == UINT64_MAX) { 342 return __builtin_ctzl(x); 343 } 344 #endif 345 #if (__has_builtin(__builtin_ctzll) || SECP256K1_GNUC_PREREQ(3,4)) 346 /* Otherwise consider __builtin_ctzll (the unsigned long long type is always at least 64 bits). */ 347 return __builtin_ctzll(x); 348 #else 349 /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */ 350 return haskellsecp256k1_v0_1_0_ctz64_var_debruijn(x); 351 #endif 352 } 353 354 /* Read a uint32_t in big endian */ 355 SECP256K1_INLINE static uint32_t haskellsecp256k1_v0_1_0_read_be32(const unsigned char* p) { 356 return (uint32_t)p[0] << 24 | 357 (uint32_t)p[1] << 16 | 358 (uint32_t)p[2] << 8 | 359 (uint32_t)p[3]; 360 } 361 362 /* Write a uint32_t in big endian */ 363 SECP256K1_INLINE static void haskellsecp256k1_v0_1_0_write_be32(unsigned char* p, uint32_t x) { 364 p[3] = x; 365 p[2] = x >> 8; 366 p[1] = x >> 16; 367 p[0] = x >> 24; 368 } 369 370 /* Read a uint64_t in big endian */ 371 SECP256K1_INLINE static uint64_t haskellsecp256k1_v0_1_0_read_be64(const unsigned char* p) { 372 return (uint64_t)p[0] << 56 | 373 (uint64_t)p[1] << 48 | 374 (uint64_t)p[2] << 40 | 375 (uint64_t)p[3] << 32 | 376 (uint64_t)p[4] << 24 | 377 (uint64_t)p[5] << 16 | 378 (uint64_t)p[6] << 8 | 379 (uint64_t)p[7]; 380 } 381 382 /* Write a uint64_t in big endian */ 383 SECP256K1_INLINE static void haskellsecp256k1_v0_1_0_write_be64(unsigned char* p, uint64_t x) { 384 p[7] = x; 385 p[6] = x >> 8; 386 p[5] = x >> 16; 387 p[4] = x >> 24; 388 p[3] = x >> 32; 389 p[2] = x >> 40; 390 p[1] = x >> 48; 391 p[0] = x >> 56; 392 } 393 394 #endif /* SECP256K1_UTIL_H */