util.h
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 34 static 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 60 /** Assert statically that expr is true. 61 * 62 * This is a statement-like macro and can only be used inside functions. 63 */ 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 73 /** Assert statically that expr is an integer constant expression, and run stmt. 74 * 75 * Useful for example to enforce that magnitude arguments are constant. 76 */ 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 87 typedef struct { 88 void (*fn)(const char *text, void* data); 89 const void* data; 90 } secp256k1_callback; 91 92 static 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 97 static 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 } 102 static 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 108 void secp256k1_default_illegal_callback_fn(const char* str, void* data); 109 void secp256k1_default_error_callback_fn(const char* str, void* data); 110 #endif 111 112 static const secp256k1_callback default_illegal_callback = { 113 secp256k1_default_illegal_callback_fn, 114 NULL 115 }; 116 117 static const secp256k1_callback default_error_callback = { 118 secp256k1_default_error_callback_fn, 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 162 static 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 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) 185 186 /* Macro for restrict, when available and not in a VERIFY build. */ 187 #if defined(SECP256K1_BUILD) && defined(VERIFY) 188 # define SECP256K1_RESTRICT 189 #else 190 # if (!defined(__STDC_VERSION__) || (__STDC_VERSION__ < 199901L) ) 191 # if SECP256K1_GNUC_PREREQ(3,0) 192 # define SECP256K1_RESTRICT __restrict__ 193 # elif (defined(_MSC_VER) && _MSC_VER >= 1400) 194 # define SECP256K1_RESTRICT __restrict 195 # else 196 # define SECP256K1_RESTRICT 197 # endif 198 # else 199 # define SECP256K1_RESTRICT restrict 200 # endif 201 #endif 202 203 #if defined(__GNUC__) 204 # define SECP256K1_GNUC_EXT __extension__ 205 #else 206 # define SECP256K1_GNUC_EXT 207 #endif 208 209 /* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */ 210 static SECP256K1_INLINE void secp256k1_memczero(void *s, size_t len, int flag) { 211 unsigned char *p = (unsigned char *)s; 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 unsigned char mask = -(unsigned char) vflag; 217 VERIFY_CHECK(flag == 0 || flag == 1); 218 while (len) { 219 *p &= ~mask; 220 p++; 221 len--; 222 } 223 } 224 225 /* Zeroes memory to prevent leaking sensitive info. Won't be optimized out. */ 226 static SECP256K1_INLINE void secp256k1_memzero_explicit(void *ptr, size_t len) { 227 #if defined(_MSC_VER) 228 /* SecureZeroMemory is guaranteed not to be optimized out by MSVC. */ 229 SecureZeroMemory(ptr, len); 230 #elif defined(__GNUC__) 231 /* We use a memory barrier that scares the compiler away from optimizing out the memset. 232 * 233 * Quoting Adam Langley <agl@google.com> in commit ad1907fe73334d6c696c8539646c21b11178f20f 234 * in BoringSSL (ISC License): 235 * As best as we can tell, this is sufficient to break any optimisations that 236 * might try to eliminate "superfluous" memsets. 237 * This method is used in memzero_explicit() the Linux kernel, too. Its advantage is that it 238 * is pretty efficient, because the compiler can still implement the memset() efficiently, 239 * just not remove it entirely. See "Dead Store Elimination (Still) Considered Harmful" by 240 * Yang et al. (USENIX Security 2017) for more background. 241 */ 242 memset(ptr, 0, len); 243 __asm__ __volatile__("" : : "r"(ptr) : "memory"); 244 #else 245 void *(*volatile const volatile_memset)(void *, int, size_t) = memset; 246 volatile_memset(ptr, 0, len); 247 #endif 248 } 249 250 /* Cleanses memory to prevent leaking sensitive info. Won't be optimized out. 251 * The state of the memory after this call is unspecified so callers must not 252 * make any assumptions about its contents. 253 * 254 * In VERIFY builds, it has the side effect of marking the memory as undefined. 255 * This helps to detect use-after-clear bugs where code incorrectly reads from 256 * cleansed memory during testing. 257 */ 258 static SECP256K1_INLINE void secp256k1_memclear_explicit(void *ptr, size_t len) { 259 /* The current implementation zeroes, but callers must not rely on this */ 260 secp256k1_memzero_explicit(ptr, len); 261 #ifdef VERIFY 262 SECP256K1_CHECKMEM_UNDEFINE(ptr, len); 263 #endif 264 } 265 266 /** Semantics like memcmp. Variable-time. 267 * 268 * We use this to avoid possible compiler bugs with memcmp, e.g. 269 * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189 270 */ 271 static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n) { 272 const unsigned char *p1 = s1, *p2 = s2; 273 size_t i; 274 275 for (i = 0; i < n; i++) { 276 int diff = p1[i] - p2[i]; 277 if (diff != 0) { 278 return diff; 279 } 280 } 281 return 0; 282 } 283 284 /* Return 1 if all elements of array s are 0 and otherwise return 0. 285 * Constant-time. */ 286 static SECP256K1_INLINE int secp256k1_is_zero_array(const unsigned char *s, size_t len) { 287 unsigned char acc = 0; 288 int ret; 289 size_t i; 290 291 for (i = 0; i < len; i++) { 292 acc |= s[i]; 293 } 294 ret = (acc == 0); 295 /* acc may contain secret values. Try to explicitly clear it. */ 296 secp256k1_memclear_explicit(&acc, sizeof(acc)); 297 return ret; 298 } 299 300 /** If flag is 1, set *r equal to *a; if flag is 0, leave it. Constant-time. 301 * Both *r and *a must be initialized and non-negative. Flag must be 0 or 1. */ 302 static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) { 303 unsigned int mask0, mask1, r_masked, a_masked; 304 /* Access flag with a volatile-qualified lvalue. 305 This prevents clang from figuring out (after inlining) that flag can 306 take only be 0 or 1, which leads to variable time code. */ 307 volatile int vflag = flag; 308 309 VERIFY_CHECK(flag == 0 || flag == 1); 310 /* Casting a negative int to unsigned and back to int is implementation defined behavior */ 311 VERIFY_CHECK(*r >= 0 && *a >= 0); 312 313 mask0 = (unsigned int)vflag + ~0u; 314 mask1 = ~mask0; 315 r_masked = ((unsigned int)*r & mask0); 316 a_masked = ((unsigned int)*a & mask1); 317 318 *r = (int)(r_masked | a_masked); 319 } 320 321 #if defined(USE_FORCE_WIDEMUL_INT128_STRUCT) 322 /* If USE_FORCE_WIDEMUL_INT128_STRUCT is set, use int128_struct. */ 323 # define SECP256K1_WIDEMUL_INT128 1 324 # define SECP256K1_INT128_STRUCT 1 325 #elif defined(USE_FORCE_WIDEMUL_INT128) 326 /* If USE_FORCE_WIDEMUL_INT128 is set, use int128. */ 327 # define SECP256K1_WIDEMUL_INT128 1 328 # define SECP256K1_INT128_NATIVE 1 329 #elif defined(USE_FORCE_WIDEMUL_INT64) 330 /* If USE_FORCE_WIDEMUL_INT64 is set, use int64. */ 331 # define SECP256K1_WIDEMUL_INT64 1 332 #elif defined(UINT128_MAX) || defined(__SIZEOF_INT128__) 333 /* If a native 128-bit integer type exists, use int128. */ 334 # define SECP256K1_WIDEMUL_INT128 1 335 # define SECP256K1_INT128_NATIVE 1 336 #elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64)) 337 /* On 64-bit MSVC targets (x86_64 and arm64), use int128_struct 338 * (which has special logic to implement using intrinsics on those systems). */ 339 # define SECP256K1_WIDEMUL_INT128 1 340 # define SECP256K1_INT128_STRUCT 1 341 #elif SIZE_MAX > 0xffffffff 342 /* Systems with 64-bit pointers (and thus registers) very likely benefit from 343 * using 64-bit based arithmetic (even if we need to fall back to 32x32->64 based 344 * multiplication logic). */ 345 # define SECP256K1_WIDEMUL_INT128 1 346 # define SECP256K1_INT128_STRUCT 1 347 #else 348 /* Lastly, fall back to int64 based arithmetic. */ 349 # define SECP256K1_WIDEMUL_INT64 1 350 #endif 351 352 #ifndef __has_builtin 353 #define __has_builtin(x) 0 354 #endif 355 356 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x. 357 * This function is only intended to be used as fallback for 358 * secp256k1_ctz32_var, but permits it to be tested separately. */ 359 static SECP256K1_INLINE int secp256k1_ctz32_var_debruijn(uint32_t x) { 360 static const uint8_t debruijn[32] = { 361 0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A, 362 0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B, 363 0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B 364 }; 365 return debruijn[(uint32_t)((x & -x) * 0x04D7651FU) >> 27]; 366 } 367 368 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x. 369 * This function is only intended to be used as fallback for 370 * secp256k1_ctz64_var, but permits it to be tested separately. */ 371 static SECP256K1_INLINE int secp256k1_ctz64_var_debruijn(uint64_t x) { 372 static const uint8_t debruijn[64] = { 373 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, 374 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, 375 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, 376 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12 377 }; 378 return debruijn[(uint64_t)((x & -x) * 0x022FDD63CC95386DU) >> 58]; 379 } 380 381 /* Determine the number of trailing zero bits in a (non-zero) 32-bit x. */ 382 static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x) { 383 VERIFY_CHECK(x != 0); 384 #if (__has_builtin(__builtin_ctz) || SECP256K1_GNUC_PREREQ(3,4)) 385 /* If the unsigned type is sufficient to represent the largest uint32_t, consider __builtin_ctz. */ 386 if (((unsigned)UINT32_MAX) == UINT32_MAX) { 387 return __builtin_ctz(x); 388 } 389 #endif 390 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4)) 391 /* Otherwise consider __builtin_ctzl (the unsigned long type is always at least 32 bits). */ 392 return __builtin_ctzl(x); 393 #else 394 /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */ 395 return secp256k1_ctz32_var_debruijn(x); 396 #endif 397 } 398 399 /* Determine the number of trailing zero bits in a (non-zero) 64-bit x. */ 400 static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x) { 401 VERIFY_CHECK(x != 0); 402 #if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4)) 403 /* If the unsigned long type is sufficient to represent the largest uint64_t, consider __builtin_ctzl. */ 404 if (((unsigned long)UINT64_MAX) == UINT64_MAX) { 405 return __builtin_ctzl(x); 406 } 407 #endif 408 #if (__has_builtin(__builtin_ctzll) || SECP256K1_GNUC_PREREQ(3,4)) 409 /* Otherwise consider __builtin_ctzll (the unsigned long long type is always at least 64 bits). */ 410 return __builtin_ctzll(x); 411 #else 412 /* If no suitable CTZ builtin is available, use a (variable time) software emulation. */ 413 return secp256k1_ctz64_var_debruijn(x); 414 #endif 415 } 416 417 /* Read a uint32_t in big endian */ 418 SECP256K1_INLINE static uint32_t secp256k1_read_be32(const unsigned char* p) { 419 return (uint32_t)p[0] << 24 | 420 (uint32_t)p[1] << 16 | 421 (uint32_t)p[2] << 8 | 422 (uint32_t)p[3]; 423 } 424 425 /* Write a uint32_t in big endian */ 426 SECP256K1_INLINE static void secp256k1_write_be32(unsigned char* p, uint32_t x) { 427 p[3] = x; 428 p[2] = x >> 8; 429 p[1] = x >> 16; 430 p[0] = x >> 24; 431 } 432 433 /* Read a uint64_t in big endian */ 434 SECP256K1_INLINE static uint64_t secp256k1_read_be64(const unsigned char* p) { 435 return (uint64_t)p[0] << 56 | 436 (uint64_t)p[1] << 48 | 437 (uint64_t)p[2] << 40 | 438 (uint64_t)p[3] << 32 | 439 (uint64_t)p[4] << 24 | 440 (uint64_t)p[5] << 16 | 441 (uint64_t)p[6] << 8 | 442 (uint64_t)p[7]; 443 } 444 445 /* Write a uint64_t in big endian */ 446 SECP256K1_INLINE static void secp256k1_write_be64(unsigned char* p, uint64_t x) { 447 p[7] = x; 448 p[6] = x >> 8; 449 p[5] = x >> 16; 450 p[4] = x >> 24; 451 p[3] = x >> 32; 452 p[2] = x >> 40; 453 p[1] = x >> 48; 454 p[0] = x >> 56; 455 } 456 457 /* Rotate a uint32_t to the right. */ 458 SECP256K1_INLINE static uint32_t secp256k1_rotr32(const uint32_t x, const unsigned int by) { 459 #if defined(_MSC_VER) 460 return _rotr(x, by); /* needs <stdlib.h> */ 461 #else 462 /* Reduce rotation amount to avoid UB when shifting. */ 463 const unsigned int mask = CHAR_BIT * sizeof(x) - 1; 464 /* Turned into a rot instruction by GCC and clang. */ 465 return (x >> (by & mask)) | (x << ((-by) & mask)); 466 #endif 467 } 468 469 #endif /* SECP256K1_UTIL_H */