src/util.h

   1 /**********************************************************************
   2  * Copyright (c) 2013, 2014 Pieter Wuille                             *
   3  * Distributed under the MIT software license, see the accompanying   *
   4  * file COPYING or http://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
  19 typedef struct {
  20     void (*fn)(const char *text, void* data);
  21     const void* data;
  22 } secp256k1_callback;
  23
  24 static 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
  91 static 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
  99 static 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  */
 134 static 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;
 137     VERIFY_CHECK(prealloc_ptr != NULL);
 138     VERIFY_CHECK(*prealloc_ptr != NULL);
 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     *((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. */
 205 static 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
 219 /** Semantics like memcmp. Variable-time.
 220  *
 221  * We use this to avoid possible compiler bugs with memcmp, e.g.
 222  * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189
 223  */
 224 static 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
 237 /** If flag is true, set *r equal to *a; otherwise leave it. Constant-time.  Both *r and *a must be initialized and non-negative.*/
 238 static 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__)
 270 SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_t;
 271 SECP256K1_GNUC_EXT typedef __int128 int128_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 #endif /* SECP256K1_UTIL_H */