Changeset View
Changeset View
Standalone View
Standalone View
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 */ |