int: Backport C23's bit utilities

2 files changed, 244 insertions, 0 deletions

diff --git a/src/int.h b/src/int.h
index 1cd455a..885933d 100644
--- a/src/int.h
+++ b/src/int.h
@@ -8,6 +8,7 @@
 #ifndef BFS_INT_H
 #define BFS_INT_H
 
+#include "config.h"
 #include <limits.h>
 #include <stdint.h>
 
@@ -165,4 +166,190 @@ static inline uint8_t bswap8(uint8_t n) {
 		uint32_t: bswap32, \
 		uint64_t: bswap64)(n)
 
+// Define an overload for each unsigned type
+#define UINT_OVERLOADS(macro) \
+	macro(unsigned char, _uc, UCHAR_WIDTH) \
+	macro(unsigned short, _us, USHRT_WIDTH) \
+	macro(unsigned int, _ui, UINT_WIDTH) \
+	macro(unsigned long, _ul, ULONG_WIDTH) \
+	macro(unsigned long long, _ull, ULLONG_WIDTH)
+
+// 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
+
+#if __STDC_VERSION__ >= 202311L
+#  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
+#  define trailing_ones stdc_trailing_ones
+#  define first_leading_zero stdc_first_leading_zero
+#  define first_leading_one stdc_first_leading_one
+#  define first_trailing_zero stdc_first_trailing_zero
+#  define first_trailing_one stdc_first_trailing_one
+#  define has_single_bit stdc_has_single_bit
+#  define bit_width stdc_bit_width
+#  define bit_ceil stdc_bit_ceil
+#  define bit_floor stdc_bit_floor
+#else
+
+#if __GNUC__
+
+// GCC provides builtins for unsigned {int,long,long long}, so promote char/short
+#define UINT_BUILTIN_uc(name) __builtin_##name
+#define UINT_BUILTIN_us(name) __builtin_##name
+#define UINT_BUILTIN_ui(name) __builtin_##name
+#define UINT_BUILTIN_ul(name) __builtin_##name##l
+#define UINT_BUILTIN_ull(name) __builtin_##name##ll
+#define UINT_BUILTIN(name, suffix) UINT_BUILTIN##suffix(name)
+
+#define BUILTIN_WIDTH_uc UINT_WIDTH
+#define BUILTIN_WIDTH_us UINT_WIDTH
+#define BUILTIN_WIDTH_ui UINT_WIDTH
+#define BUILTIN_WIDTH_ul ULONG_WIDTH
+#define BUILTIN_WIDTH_ull ULLONG_WIDTH
+#define BUILTIN_WIDTH(suffix) BUILTIN_WIDTH##suffix
+
+#define COUNT_ONES(type, suffix, width) \
+	static inline 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) { \
+	        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) { \
+		return n ? UINT_BUILTIN(ctz, suffix)(n) : width; \
+	}
+
+#define FIRST_TRAILING_ONE(type, suffix, width) \
+	static inline 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) { \
+		int ret; \
+		for (ret = 0; n; ++ret) { \
+			n &= n - 1; \
+		} \
+		return ret; \
+	}
+
+#define LEADING_ZEROS(type, suffix, width) \
+	static inline int leading_zeros##suffix(type n) { \
+		type bit = (type)1 << (width - 1); \
+		int ret; \
+		for (ret = 0; bit && !(n & bit); ++ret, bit >>= 1); \
+		return ret; \
+	}
+
+#define TRAILING_ZEROS(type, suffix, width) \
+	static inline int trailing_zeros##suffix(type n) { \
+		type bit = 1; \
+		int ret; \
+		for (ret = 0; bit && !(n & bit); ++ret, bit <<= 1); \
+		return ret; \
+	}
+
+#define FIRST_TRAILING_ONE(type, suffix, width) \
+	static inline int first_trailing_one##suffix(type n) { \
+		return n ? trailing_zeros##suffix(n) + 1 : 0; \
+	}
+
+#endif // !__GNUC__
+
+UINT_OVERLOADS(COUNT_ONES)
+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); \
+	}
+
+#define HAS_SINGLE_BIT(type, suffix, width) \
+	static inline bool has_single_bit##suffix(type n) { \
+		return n && !(n & (n - 1)); \
+	}
+
+UINT_OVERLOADS(ROTATE_LEFT)
+UINT_OVERLOADS(ROTATE_RIGHT)
+UINT_OVERLOADS(FIRST_LEADING_ONE)
+UINT_OVERLOADS(HAS_SINGLE_BIT)
+
+#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))
+
+#define trailing_zeros(n) UINT_SELECT(n, trailing_zeros)(n)
+#define trailing_ones(n) UINT_SELECT(n, trailing_zeros)(~(n))
+
+#define first_leading_one(n) UINT_SELECT(n, first_leading_one)(n)
+#define first_leading_zero(n) UINT_SELECT(n, first_leading_one)(~(n))
+
+#define first_trailing_one(n) UINT_SELECT(n, first_trailing_one)(n)
+#define first_trailing_zero(n) UINT_SELECT(n, first_trailing_one)(~(n))
+
+#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_CEIL(type, suffix, width) \
+	static inline type bit_ceil##suffix(type n) { \
+		return (type)1 << first_leading_one##suffix(n - !!n); \
+	}
+
+UINT_OVERLOADS(BIT_FLOOR)
+UINT_OVERLOADS(BIT_CEIL)
+
+#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)
+
+#endif // __STDC_VERSION__ < 202311L
+
 #endif // BFS_INT_H
diff --git a/tests/int.c b/tests/int.c
index 0039862..e59efde 100644
--- a/tests/int.c
+++ b/tests/int.c
@@ -60,5 +60,62 @@ int main(void) {
 	assert(bswap((uint32_t)0x12345678) == 0x78563412);
 	assert(bswap((uint64_t)0x1234567812345678) == 0x7856341278563412);
 
+	assert(count_ones(0x0) == 0);
+	assert(count_ones(0x1) == 1);
+	assert(count_ones(0x2) == 1);
+	assert(count_ones(0x3) == 2);
+	assert(count_ones(0x137F) == 10);
+
+	assert(count_zeros(0) == INT_WIDTH);
+	assert(count_zeros(0L) == LONG_WIDTH);
+	assert(count_zeros(0LL) == LLONG_WIDTH);
+	assert(count_zeros((uint8_t)0) == 8);
+	assert(count_zeros((uint16_t)0) == 16);
+	assert(count_zeros((uint32_t)0) == 32);
+	assert(count_zeros((uint64_t)0) == 64);
+
+	assert(rotate_left((uint8_t)0xA1, 4) == 0x1A);
+	assert(rotate_left((uint16_t)0x1234, 12) == 0x4123);
+	assert(rotate_left((uint32_t)0x12345678, 20) == 0x67812345);
+	assert(rotate_left((uint32_t)0x12345678, 0) == 0x12345678);
+
+	assert(rotate_right((uint8_t)0xA1, 4) == 0x1A);
+	assert(rotate_right((uint16_t)0x1234, 12) == 0x2341);
+	assert(rotate_right((uint32_t)0x12345678, 20) == 0x45678123);
+	assert(rotate_right((uint32_t)0x12345678, 0) == 0x12345678);
+
+	for (int i = 0; i < 16; ++i) {
+		uint16_t n = (uint16_t)1 << i;
+		for (int j = i; j < 16; ++j) {
+			uint16_t m = (uint16_t)1 << j;
+			uint16_t nm = n | m;
+			assert(count_ones(nm) == 1 + (n != m));
+			assert(count_zeros(nm) == 15 - (n != m));
+			assert(leading_zeros(nm) == 15 - j);
+			assert(trailing_zeros(nm) == i);
+			assert(first_leading_one(nm) == j + 1);
+			assert(first_trailing_one(nm) == i + 1);
+			assert(bit_width(nm) == j + 1);
+			assert(bit_floor(nm) == m);
+			if (n == m) {
+				assert(bit_ceil(nm) == m);
+				assert(has_single_bit(nm));
+			} else {
+				if (j < 15) {
+					assert(bit_ceil(nm) == (m << 1));
+				}
+				assert(!has_single_bit(nm));
+			}
+		}
+	}
+
+	assert(leading_zeros((uint16_t)0) == 16);
+	assert(trailing_zeros((uint16_t)0) == 16);
+	assert(first_leading_one(0) == 0);
+	assert(first_trailing_one(0) == 0);
+	assert(bit_width(0) == 0);
+	assert(bit_floor(0) == 0);
+	assert(bit_ceil(0) == 1);
+
 	return EXIT_SUCCESS;
 }