From 26ac7e36c0710284d18d95eb0e58e21178396ffd Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Wed, 29 May 2024 11:12:21 -0400 Subject: bit: Update to match C23 Based on the latest C23 draft (N3220): - Argument types to generic bit functions should be unsigned - Bit functions return unsigned int - Byte-swapping functions (stdc_memreverse8*()) weren't added - stdc_rotate_{left,right}() weren't added - first_leading_*() counts from the *left* --- src/bit.h | 96 +++++++++++++++++++++++++++++-------------------------------- tests/bit.c | 36 +++++++++++------------ 2 files changed, 63 insertions(+), 69 deletions(-) diff --git a/src/bit.h b/src/bit.h index 17cfbcf..880ccd6 100644 --- a/src/bit.h +++ b/src/bit.h @@ -173,11 +173,7 @@ # define ENDIAN_NATIVE 0 #endif -#if __STDC_VERSION__ >= C23 -# define bswap_u16 stdc_memreverse8u16 -# define bswap_u32 stdc_memreverse8u32 -# define bswap_u64 stdc_memreverse8u64 -#elif __GNUC__ +#if __GNUC__ # define bswap_u16 __builtin_bswap16 # define bswap_u32 __builtin_bswap32 # define bswap_u64 __builtin_bswap64 @@ -222,16 +218,10 @@ static inline uint8_t bswap_u8(uint8_t n) { // Select an overload based on an unsigned integer type #define UINT_SELECT(n, name) \ _Generic((n), \ - char: name##_uc, \ - signed char: name##_uc, \ unsigned char: name##_uc, \ - signed short: name##_us, \ unsigned short: name##_us, \ - signed int: name##_ui, \ unsigned int: name##_ui, \ - signed long: name##_ul, \ unsigned long: name##_ul, \ - signed long long: name##_ull, \ unsigned long long: name##_ull) // C23 polyfill: bit utilities @@ -239,8 +229,6 @@ static inline uint8_t bswap_u8(uint8_t n) { #if __STDC_VERSION__ >= C23 # define count_ones stdc_count_ones # define count_zeros stdc_count_zeros -# define rotate_left stdc_rotate_left -# define rotate_right stdc_rotate_right # define leading_zeros stdc_leading_zeros # define leading_ones stdc_leading_ones # define trailing_zeros stdc_trailing_zeros @@ -273,31 +261,31 @@ static inline uint8_t bswap_u8(uint8_t n) { #define BUILTIN_WIDTH(suffix) BUILTIN_WIDTH##suffix #define COUNT_ONES(type, suffix, width) \ - static inline int count_ones##suffix(type n) { \ + static inline unsigned int count_ones##suffix(type n) { \ return UINT_BUILTIN(popcount, suffix)(n); \ } #define LEADING_ZEROS(type, suffix, width) \ - static inline int leading_zeros##suffix(type n) { \ + static inline unsigned int leading_zeros##suffix(type n) { \ return n \ ? UINT_BUILTIN(clz, suffix)(n) - (BUILTIN_WIDTH(suffix) - width) \ : width; \ } #define TRAILING_ZEROS(type, suffix, width) \ - static inline int trailing_zeros##suffix(type n) { \ + static inline unsigned int trailing_zeros##suffix(type n) { \ return n ? UINT_BUILTIN(ctz, suffix)(n) : (int)width; \ } #define FIRST_TRAILING_ONE(type, suffix, width) \ - static inline int first_trailing_one##suffix(type n) { \ + static inline unsigned int first_trailing_one##suffix(type n) { \ return UINT_BUILTIN(ffs, suffix)(n); \ } #else // !__GNUC__ #define COUNT_ONES(type, suffix, width) \ - static inline int count_ones##suffix(type n) { \ + static inline unsigned int count_ones##suffix(type n) { \ int ret; \ for (ret = 0; n; ++ret) { \ n &= n - 1; \ @@ -306,7 +294,7 @@ static inline uint8_t bswap_u8(uint8_t n) { } #define LEADING_ZEROS(type, suffix, width) \ - static inline int leading_zeros##suffix(type n) { \ + static inline unsigned int leading_zeros##suffix(type n) { \ type bit = (type)1 << (width - 1); \ int ret; \ for (ret = 0; bit && !(n & bit); ++ret, bit >>= 1); \ @@ -314,7 +302,7 @@ static inline uint8_t bswap_u8(uint8_t n) { } #define TRAILING_ZEROS(type, suffix, width) \ - static inline int trailing_zeros##suffix(type n) { \ + static inline unsigned int trailing_zeros##suffix(type n) { \ type bit = 1; \ int ret; \ for (ret = 0; bit && !(n & bit); ++ret, bit <<= 1); \ @@ -322,7 +310,7 @@ static inline uint8_t bswap_u8(uint8_t n) { } #define FIRST_TRAILING_ONE(type, suffix, width) \ - static inline int first_trailing_one##suffix(type n) { \ + static inline unsigned int first_trailing_one##suffix(type n) { \ return n ? trailing_zeros##suffix(n) + 1 : 0; \ } @@ -333,19 +321,9 @@ UINT_OVERLOADS(LEADING_ZEROS) UINT_OVERLOADS(TRAILING_ZEROS) UINT_OVERLOADS(FIRST_TRAILING_ONE) -#define ROTATE_LEFT(type, suffix, width) \ - static inline type rotate_left##suffix(type n, int c) { \ - return (n << c) | (n >> ((width - c) % width)); \ - } - -#define ROTATE_RIGHT(type, suffix, width) \ - static inline type rotate_right##suffix(type n, int c) { \ - return (n >> c) | (n << ((width - c) % width)); \ - } - #define FIRST_LEADING_ONE(type, suffix, width) \ - static inline int first_leading_one##suffix(type n) { \ - return width - leading_zeros##suffix(n); \ + static inline unsigned int first_leading_one##suffix(type n) { \ + return n ? leading_zeros##suffix(n) + 1 : 0; \ } #define HAS_SINGLE_BIT(type, suffix, width) \ @@ -354,17 +332,30 @@ UINT_OVERLOADS(FIRST_TRAILING_ONE) return n - 1 < (n ^ (n - 1)); \ } -UINT_OVERLOADS(ROTATE_LEFT) -UINT_OVERLOADS(ROTATE_RIGHT) +#define BIT_WIDTH(type, suffix, width) \ + static inline unsigned int bit_width##suffix(type n) { \ + return width - leading_zeros##suffix(n); \ + } + +#define BIT_FLOOR(type, suffix, width) \ + static inline type bit_floor##suffix(type n) { \ + return n ? (type)1 << (bit_width##suffix(n) - 1) : 0; \ + } + +#define BIT_CEIL(type, suffix, width) \ + static inline type bit_ceil##suffix(type n) { \ + return (type)1 << bit_width##suffix(n - !!n); \ + } + UINT_OVERLOADS(FIRST_LEADING_ONE) UINT_OVERLOADS(HAS_SINGLE_BIT) +UINT_OVERLOADS(BIT_WIDTH) +UINT_OVERLOADS(BIT_FLOOR) +UINT_OVERLOADS(BIT_CEIL) #define count_ones(n) UINT_SELECT(n, count_ones)(n) #define count_zeros(n) UINT_SELECT(n, count_ones)(~(n)) -#define rotate_left(n, c) UINT_SELECT(n, rotate_left)(n, c) -#define rotate_right(n, c) UINT_SELECT(n, rotate_right)(n, c) - #define leading_zeros(n) UINT_SELECT(n, leading_zeros)(n) #define leading_ones(n) UINT_SELECT(n, leading_zeros)(~(n)) @@ -379,23 +370,26 @@ UINT_OVERLOADS(HAS_SINGLE_BIT) #define has_single_bit(n) UINT_SELECT(n, has_single_bit)(n) -#define BIT_FLOOR(type, suffix, width) \ - static inline type bit_floor##suffix(type n) { \ - return n ? (type)1 << (first_leading_one##suffix(n) - 1) : 0; \ - } +#define bit_width(n) UINT_SELECT(n, bit_width)(n) +#define bit_floor(n) UINT_SELECT(n, bit_floor)(n) +#define bit_ceil(n) UINT_SELECT(n, bit_ceil)(n) -#define BIT_CEIL(type, suffix, width) \ - static inline type bit_ceil##suffix(type n) { \ - return (type)1 << first_leading_one##suffix(n - !!n); \ +#endif // __STDC_VERSION__ < C23 + +#define ROTATE_LEFT(type, suffix, width) \ + static inline type rotate_left##suffix(type n, int c) { \ + return (n << c) | (n >> ((width - c) % width)); \ } -UINT_OVERLOADS(BIT_FLOOR) -UINT_OVERLOADS(BIT_CEIL) +#define ROTATE_RIGHT(type, suffix, width) \ + static inline type rotate_right##suffix(type n, int c) { \ + return (n >> c) | (n << ((width - c) % width)); \ + } -#define bit_width(n) first_leading_one(n) -#define bit_floor(n) UINT_SELECT(n, bit_floor)(n) -#define bit_ceil(n) UINT_SELECT(n, bit_ceil)(n) +UINT_OVERLOADS(ROTATE_LEFT) +UINT_OVERLOADS(ROTATE_RIGHT) -#endif // __STDC_VERSION__ < C23 +#define rotate_left(n, c) UINT_SELECT(n, rotate_left)(n, c) +#define rotate_right(n, c) UINT_SELECT(n, rotate_right)(n, c) #endif // BFS_BIT_H diff --git a/tests/bit.c b/tests/bit.c index 674d1b2..49e167d 100644 --- a/tests/bit.c +++ b/tests/bit.c @@ -76,15 +76,15 @@ bool check_bit(void) { ret &= check_eq(bswap((uint32_t)0x12345678), 0x78563412); ret &= check_eq(bswap((uint64_t)0x1234567812345678), 0x7856341278563412); - ret &= check_eq(count_ones(0x0), 0); - ret &= check_eq(count_ones(0x1), 1); - ret &= check_eq(count_ones(0x2), 1); - ret &= check_eq(count_ones(0x3), 2); - ret &= check_eq(count_ones(0x137F), 10); - - ret &= check_eq(count_zeros(0), INT_WIDTH); - ret &= check_eq(count_zeros(0L), LONG_WIDTH); - ret &= check_eq(count_zeros(0LL), LLONG_WIDTH); + ret &= check_eq(count_ones(0x0U), 0); + ret &= check_eq(count_ones(0x1U), 1); + ret &= check_eq(count_ones(0x2U), 1); + ret &= check_eq(count_ones(0x3U), 2); + ret &= check_eq(count_ones(0x137FU), 10); + + ret &= check_eq(count_zeros(0U), UINT_WIDTH); + ret &= check_eq(count_zeros(0UL), ULONG_WIDTH); + ret &= check_eq(count_zeros(0ULL), ULLONG_WIDTH); ret &= check_eq(count_zeros((uint8_t)0), 8); ret &= check_eq(count_zeros((uint16_t)0), 16); ret &= check_eq(count_zeros((uint32_t)0), 32); @@ -100,16 +100,16 @@ bool check_bit(void) { ret &= check_eq(rotate_right((uint32_t)0x12345678, 20), 0x45678123); ret &= check_eq(rotate_right((uint32_t)0x12345678, 0), 0x12345678); - for (int i = 0; i < 16; ++i) { + for (unsigned int i = 0; i < 16; ++i) { uint16_t n = (uint16_t)1 << i; - for (int j = i; j < 16; ++j) { + for (unsigned int j = i; j < 16; ++j) { uint16_t m = (uint16_t)1 << j; uint16_t nm = n | m; ret &= check_eq(count_ones(nm), 1 + (n != m)); ret &= check_eq(count_zeros(nm), 15 - (n != m)); ret &= check_eq(leading_zeros(nm), 15 - j); ret &= check_eq(trailing_zeros(nm), i); - ret &= check_eq(first_leading_one(nm), j + 1); + ret &= check_eq(first_leading_one(nm), 16 - j); ret &= check_eq(first_trailing_one(nm), i + 1); ret &= check_eq(bit_width(nm), j + 1); ret &= check_eq(bit_floor(nm), m); @@ -127,13 +127,13 @@ bool check_bit(void) { ret &= check_eq(leading_zeros((uint16_t)0), 16); ret &= check_eq(trailing_zeros((uint16_t)0), 16); - ret &= check_eq(first_leading_one(0), 0); - ret &= check_eq(first_trailing_one(0), 0); - ret &= check_eq(bit_width(0), 0); - ret &= check_eq(bit_floor(0), 0); - ret &= check_eq(bit_ceil(0), 1); + ret &= check_eq(first_leading_one(0U), 0); + ret &= check_eq(first_trailing_one(0U), 0); + ret &= check_eq(bit_width(0U), 0); + ret &= check_eq(bit_floor(0U), 0); + ret &= check_eq(bit_ceil(0U), 1); - ret &= bfs_check(!has_single_bit(0)); + ret &= bfs_check(!has_single_bit(0U)); ret &= bfs_check(!has_single_bit(UINT32_MAX)); ret &= bfs_check(has_single_bit((uint32_t)1 << (UINT_WIDTH - 1))); -- cgit v1.2.3