Page MenuHomePhabricator
Differential D9401 Diff 28154 src/secp256k1/src/util.h

Changeset View

Standalone View

View Options

src/secp256k1/src/util.h

Show First 20 Lines • Show All 270 Lines • ▼ Show 20 Lines
SECP256K1_GNUC_EXT typedef __int128 int128_t; SECP256K1_GNUC_EXT typedef __int128 int128_t;
#define UINT128_MAX ((uint128_t)(-1)) #define UINT128_MAX ((uint128_t)(-1))
#define INT128_MAX ((int128_t)(UINT128_MAX >> 1)) #define INT128_MAX ((int128_t)(UINT128_MAX >> 1))
#define INT128_MIN (-INT128_MAX - 1) #define INT128_MIN (-INT128_MAX - 1)
/* No (U)INT128_C macros because compilers providing __int128 do not support 128-bit literals. */ /* No (U)INT128_C macros because compilers providing __int128 do not support 128-bit literals. */
# endif # endif
#endif #endif
#ifndef __has_builtin
#define __has_builtin(x) 0
#endif
/* Determine the number of trailing zero bits in a (non-zero) 32-bit x.
* This function is only intended to be used as fallback for
* secp256k1_ctz32_var, but permits it to be tested separately. */
static SECP256K1_INLINE int secp256k1_ctz32_var_debruijn(uint32_t x) {
static const uint8_t debruijn[32] = {
0x00, 0x01, 0x02, 0x18, 0x03, 0x13, 0x06, 0x19, 0x16, 0x04, 0x14, 0x0A,
0x10, 0x07, 0x0C, 0x1A, 0x1F, 0x17, 0x12, 0x05, 0x15, 0x09, 0x0F, 0x0B,
0x1E, 0x11, 0x08, 0x0E, 0x1D, 0x0D, 0x1C, 0x1B
};
return debruijn[((x & -x) * 0x04D7651F) >> 27];
}
/* Determine the number of trailing zero bits in a (non-zero) 64-bit x.
* This function is only intended to be used as fallback for
* secp256k1_ctz64_var, but permits it to be tested separately. */
static SECP256K1_INLINE int secp256k1_ctz64_var_debruijn(uint64_t x) {
static const uint8_t debruijn[64] = {
0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
};
return debruijn[((x & -x) * 0x022FDD63CC95386D) >> 58];
}
/* Determine the number of trailing zero bits in a (non-zero) 32-bit x. */
static SECP256K1_INLINE int secp256k1_ctz32_var(uint32_t x) {
VERIFY_CHECK(x != 0);
#if (__has_builtin(__builtin_ctz) || SECP256K1_GNUC_PREREQ(3,4))
/* If the unsigned type is sufficient to represent the largest uint32_t, consider __builtin_ctz. */
if (((unsigned)UINT32_MAX) == UINT32_MAX) {
return __builtin_ctz(x);
}
#endif
#if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
/* Otherwise consider __builtin_ctzl (the unsigned long type is always at least 32 bits). */
return __builtin_ctzl(x);
#else
/* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
return secp256k1_ctz32_var_debruijn(x);
#endif
}
/* Determine the number of trailing zero bits in a (non-zero) 64-bit x. */
static SECP256K1_INLINE int secp256k1_ctz64_var(uint64_t x) {
VERIFY_CHECK(x != 0);
#if (__has_builtin(__builtin_ctzl) || SECP256K1_GNUC_PREREQ(3,4))
/* If the unsigned long type is sufficient to represent the largest uint64_t, consider __builtin_ctzl. */
if (((unsigned long)UINT64_MAX) == UINT64_MAX) {
return __builtin_ctzl(x);
}
#endif
#if (__has_builtin(__builtin_ctzll) || SECP256K1_GNUC_PREREQ(3,4))
/* Otherwise consider __builtin_ctzll (the unsigned long long type is always at least 64 bits). */
return __builtin_ctzll(x);
#else
/* If no suitable CTZ builtin is available, use a (variable time) software emulation. */
return secp256k1_ctz64_var_debruijn(x);
#endif
}
#endif /* SECP256K1_UTIL_H */ #endif /* SECP256K1_UTIL_H */