From 4505819c576fc93f21d73e1bf85550250cdb72a2 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Thu, 18 May 2023 11:25:14 -0400
Subject: bit: Rename int.h to bit.h

---
 Makefile    |   2 +-
 src/bit.h   | 355 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/int.h   | 355 ------------------------------------------------------------
 src/trie.c  |   2 +-
 tests/bit.c | 121 +++++++++++++++++++++
 tests/int.c | 121 ---------------------
 6 files changed, 478 insertions(+), 478 deletions(-)
 create mode 100644 src/bit.h
 delete mode 100644 src/int.h
 create mode 100644 tests/bit.c
 delete mode 100644 tests/int.c

diff --git a/Makefile b/Makefile
index 361f230..1d3bd20 100644
--- a/Makefile
+++ b/Makefile
@@ -240,7 +240,7 @@ LIBBFS := \
 $(BIN)/bfs: $(OBJ)/src/main.o $(LIBBFS)
 
 # Standalone unit tests
-UNITS := bfstd int trie xtimegm
+UNITS := bfstd bit trie xtimegm
 UNIT_TESTS := $(UNITS:%=$(BIN)/tests/%)
 UNIT_CHECKS := $(UNITS:%=check-%)
 
diff --git a/src/bit.h b/src/bit.h
new file mode 100644
index 0000000..efd7d27
--- /dev/null
+++ b/src/bit.h
@@ -0,0 +1,355 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+/**
+ * Bits & bytes.
+ */
+
+#ifndef BFS_BIT_H
+#define BFS_BIT_H
+
+#include "config.h"
+#include <limits.h>
+#include <stdint.h>
+
+#if __STDC_VERSION__ >= 202311L
+#  include <stdbit.h>
+#endif
+
+// C23 polyfill: _WIDTH macros
+
+// The U*_MAX macros are of the form 2**n - 1, and we want to extract the n.
+// One way would be *_WIDTH = popcount(*_MAX).  Alternatively, we can use
+// Hallvard B. Furuseth's technique from [1], which is shorter.
+//
+// [1]: https://groups.google.com/g/comp.lang.c/c/NfedEFBFJ0k
+
+// Let mask be of the form 2**m - 1, e.g. 0b111, and let n range over
+// [0b0, 0b1, 0b11, 0b111, 0b1111, ...].  Then we have
+//
+//     n % 0b111
+//         == [0b0, 0b1, 0b11, 0b0, 0b1, 0b11, ...]
+//     n / (n % 0b111 + 1)
+//         == [0b0 (x3), 0b111 (x3), 0b111111 (x3), ...]
+//     n / (n % 0b111 + 1) / 0b111
+//         == [0b0 (x3), 0b1 (x3), 0b1001 (x3), 0b1001001 (x3), ...]
+//     n / (n % 0b111 + 1) / 0b111 % 0b111
+//         == [0 (x3), 1 (x3), 2 (x3), ...]
+//         == UMAX_CHUNK(n, 0b111)
+#define UMAX_CHUNK(n, mask) (n / (n % mask + 1) / mask % mask)
+
+// 8 * UMAX_CHUNK(n, 255) gives [0 (x8), 8 (x8), 16 (x8), ...].  To that we add
+// [0, 1, 2, ..., 6, 7, 0, 1, ...], which we get from a linear interpolation on
+// n % 255:
+//
+//     n % 255
+//         == [0, 1, 3, 7, 15, 31, 63, 127, 0, ...]
+//     86 / (n % 255 + 12)
+//         == [7, 6, 5, 4, 3, 2, 1, 0, 7, ...]
+#define UMAX_INTERP(n) (7 - 86 / (n % 255 + 12))
+
+#define UMAX_WIDTH(n) (8 * UMAX_CHUNK(n, 255) + UMAX_INTERP(n))
+
+#ifndef CHAR_WIDTH
+#  define CHAR_WIDTH CHAR_BIT
+#endif
+#ifndef UCHAR_WIDTH
+#  define UCHAR_WIDTH CHAR_WIDTH
+#endif
+#ifndef SCHAR_WIDTH
+#  define SCHAR_WIDTH CHAR_WIDTH
+#endif
+#ifndef USHRT_WIDTH
+#  define USHRT_WIDTH UMAX_WIDTH(USHRT_MAX)
+#endif
+#ifndef SHRT_WIDTH
+#  define SHRT_WIDTH USHRT_WIDTH
+#endif
+#ifndef UINT_WIDTH
+#  define UINT_WIDTH UMAX_WIDTH(UINT_MAX)
+#endif
+#ifndef INT_WIDTH
+#  define INT_WIDTH UINT_WIDTH
+#endif
+#ifndef ULONG_WIDTH
+#  define ULONG_WIDTH UMAX_WIDTH(ULONG_MAX)
+#endif
+#ifndef LONG_WIDTH
+#  define LONG_WIDTH ULONG_WIDTH
+#endif
+#ifndef ULLONG_WIDTH
+#  define ULLONG_WIDTH UMAX_WIDTH(ULLONG_MAX)
+#endif
+#ifndef LLONG_WIDTH
+#  define LLONG_WIDTH ULLONG_WIDTH
+#endif
+#ifndef SIZE_WIDTH
+#  define SIZE_WIDTH UMAX_WIDTH(SIZE_MAX)
+#endif
+#ifndef PTRDIFF_WIDTH
+#  define PTRDIFF_WIDTH (UMAX_WIDTH(PTRDIFF_MAX) + 1)
+#endif
+#ifndef UINTPTR_WIDTH
+#  define UINTPTR_WIDTH UMAX_WIDTH(UINTPTR_MAX)
+#endif
+#ifndef INTPTR_WIDTH
+#  define INTPTR_WIDTH UINTPTR_WIDTH
+#endif
+#ifndef UINTMAX_WIDTH
+#  define UINTMAX_WIDTH UMAX_WIDTH(UINTMAX_MAX)
+#endif
+#ifndef INTMAX_WIDTH
+#  define INTMAX_WIDTH UINTMAX_WIDTH
+#endif
+
+// C23 polyfill: byte order
+
+#ifdef __STDC_ENDIAN_LITTLE__
+#  define ENDIAN_LITTLE __STDC_ENDIAN_LITTLE__
+#elif defined(__ORDER_LITTLE_ENDIAN__)
+#  define ENDIAN_LITTLE __ORDER_LITTLE_ENDIAN__
+#else
+#  define ENDIAN_LITTLE 1234
+#endif
+
+#ifdef __STDC_ENDIAN_BIG__
+#  define ENDIAN_BIG __STDC_ENDIAN_BIG__
+#elif defined(__ORDER_BIG_ENDIAN__)
+#  define ENDIAN_BIG __ORDER_BIG_ENDIAN__
+#else
+#  define ENDIAN_BIG 4321
+#endif
+
+#ifdef __STDC_ENDIAN_NATIVE__
+#  define ENDIAN_NATIVE __STDC_ENDIAN_NATIVE__
+#elif defined(__ORDER_NATIVE_ENDIAN__)
+#  define ENDIAN_NATIVE __ORDER_NATIVE_ENDIAN__
+#else
+#  define ENDIAN_NATIVE 0
+#endif
+
+#if __STDC_VERSION__ >= 202311L
+#  define bswap16 stdc_memreverse8u16
+#  define bswap32 stdc_memreverse8u32
+#  define bswap64 stdc_memreverse8u64
+#elif __GNUC__
+#  define bswap16 __builtin_bswap16
+#  define bswap32 __builtin_bswap32
+#  define bswap64 __builtin_bswap64
+#else
+
+static inline uint16_t bswap16(uint16_t n) {
+	return (n << 8) | (n >> 8);
+}
+
+static inline uint32_t bswap32(uint32_t n) {
+	return ((uint32_t)bswap16(n) << 16) | bswap16(n >> 16);
+}
+
+static inline uint64_t bswap64(uint64_t n) {
+	return ((uint64_t)bswap32(n) << 32) | bswap32(n >> 32);
+}
+
+#endif
+
+static inline uint8_t bswap8(uint8_t n) {
+	return n;
+}
+
+/**
+ * Reverse the byte order of an integer.
+ */
+#define bswap(n) \
+	_Generic((n), \
+		uint8_t: bswap8, \
+		uint16_t: bswap16, \
+		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_BIT_H
diff --git a/src/int.h b/src/int.h
deleted file mode 100644
index 885933d..0000000
--- a/src/int.h
+++ /dev/null
@@ -1,355 +0,0 @@
-// Copyright © Tavian Barnes <tavianator@tavianator.com>
-// SPDX-License-Identifier: 0BSD
-
-/**
- * Bits & bytes.
- */
-
-#ifndef BFS_INT_H
-#define BFS_INT_H
-
-#include "config.h"
-#include <limits.h>
-#include <stdint.h>
-
-#if __STDC_VERSION__ >= 202311L
-#  include <stdbit.h>
-#endif
-
-// C23 polyfill: _WIDTH macros
-
-// The U*_MAX macros are of the form 2**n - 1, and we want to extract the n.
-// One way would be *_WIDTH = popcount(*_MAX).  Alternatively, we can use
-// Hallvard B. Furuseth's technique from [1], which is shorter.
-//
-// [1]: https://groups.google.com/g/comp.lang.c/c/NfedEFBFJ0k
-
-// Let mask be of the form 2**m - 1, e.g. 0b111, and let n range over
-// [0b0, 0b1, 0b11, 0b111, 0b1111, ...].  Then we have
-//
-//     n % 0b111
-//         == [0b0, 0b1, 0b11, 0b0, 0b1, 0b11, ...]
-//     n / (n % 0b111 + 1)
-//         == [0b0 (x3), 0b111 (x3), 0b111111 (x3), ...]
-//     n / (n % 0b111 + 1) / 0b111
-//         == [0b0 (x3), 0b1 (x3), 0b1001 (x3), 0b1001001 (x3), ...]
-//     n / (n % 0b111 + 1) / 0b111 % 0b111
-//         == [0 (x3), 1 (x3), 2 (x3), ...]
-//         == UMAX_CHUNK(n, 0b111)
-#define UMAX_CHUNK(n, mask) (n / (n % mask + 1) / mask % mask)
-
-// 8 * UMAX_CHUNK(n, 255) gives [0 (x8), 8 (x8), 16 (x8), ...].  To that we add
-// [0, 1, 2, ..., 6, 7, 0, 1, ...], which we get from a linear interpolation on
-// n % 255:
-//
-//     n % 255
-//         == [0, 1, 3, 7, 15, 31, 63, 127, 0, ...]
-//     86 / (n % 255 + 12)
-//         == [7, 6, 5, 4, 3, 2, 1, 0, 7, ...]
-#define UMAX_INTERP(n) (7 - 86 / (n % 255 + 12))
-
-#define UMAX_WIDTH(n) (8 * UMAX_CHUNK(n, 255) + UMAX_INTERP(n))
-
-#ifndef CHAR_WIDTH
-#  define CHAR_WIDTH CHAR_BIT
-#endif
-#ifndef UCHAR_WIDTH
-#  define UCHAR_WIDTH CHAR_WIDTH
-#endif
-#ifndef SCHAR_WIDTH
-#  define SCHAR_WIDTH CHAR_WIDTH
-#endif
-#ifndef USHRT_WIDTH
-#  define USHRT_WIDTH UMAX_WIDTH(USHRT_MAX)
-#endif
-#ifndef SHRT_WIDTH
-#  define SHRT_WIDTH USHRT_WIDTH
-#endif
-#ifndef UINT_WIDTH
-#  define UINT_WIDTH UMAX_WIDTH(UINT_MAX)
-#endif
-#ifndef INT_WIDTH
-#  define INT_WIDTH UINT_WIDTH
-#endif
-#ifndef ULONG_WIDTH
-#  define ULONG_WIDTH UMAX_WIDTH(ULONG_MAX)
-#endif
-#ifndef LONG_WIDTH
-#  define LONG_WIDTH ULONG_WIDTH
-#endif
-#ifndef ULLONG_WIDTH
-#  define ULLONG_WIDTH UMAX_WIDTH(ULLONG_MAX)
-#endif
-#ifndef LLONG_WIDTH
-#  define LLONG_WIDTH ULLONG_WIDTH
-#endif
-#ifndef SIZE_WIDTH
-#  define SIZE_WIDTH UMAX_WIDTH(SIZE_MAX)
-#endif
-#ifndef PTRDIFF_WIDTH
-#  define PTRDIFF_WIDTH (UMAX_WIDTH(PTRDIFF_MAX) + 1)
-#endif
-#ifndef UINTPTR_WIDTH
-#  define UINTPTR_WIDTH UMAX_WIDTH(UINTPTR_MAX)
-#endif
-#ifndef INTPTR_WIDTH
-#  define INTPTR_WIDTH UINTPTR_WIDTH
-#endif
-#ifndef UINTMAX_WIDTH
-#  define UINTMAX_WIDTH UMAX_WIDTH(UINTMAX_MAX)
-#endif
-#ifndef INTMAX_WIDTH
-#  define INTMAX_WIDTH UINTMAX_WIDTH
-#endif
-
-// C23 polyfill: byte order
-
-#ifdef __STDC_ENDIAN_LITTLE__
-#  define ENDIAN_LITTLE __STDC_ENDIAN_LITTLE__
-#elif defined(__ORDER_LITTLE_ENDIAN__)
-#  define ENDIAN_LITTLE __ORDER_LITTLE_ENDIAN__
-#else
-#  define ENDIAN_LITTLE 1234
-#endif
-
-#ifdef __STDC_ENDIAN_BIG__
-#  define ENDIAN_BIG __STDC_ENDIAN_BIG__
-#elif defined(__ORDER_BIG_ENDIAN__)
-#  define ENDIAN_BIG __ORDER_BIG_ENDIAN__
-#else
-#  define ENDIAN_BIG 4321
-#endif
-
-#ifdef __STDC_ENDIAN_NATIVE__
-#  define ENDIAN_NATIVE __STDC_ENDIAN_NATIVE__
-#elif defined(__ORDER_NATIVE_ENDIAN__)
-#  define ENDIAN_NATIVE __ORDER_NATIVE_ENDIAN__
-#else
-#  define ENDIAN_NATIVE 0
-#endif
-
-#if __STDC_VERSION__ >= 202311L
-#  define bswap16 stdc_memreverse8u16
-#  define bswap32 stdc_memreverse8u32
-#  define bswap64 stdc_memreverse8u64
-#elif __GNUC__
-#  define bswap16 __builtin_bswap16
-#  define bswap32 __builtin_bswap32
-#  define bswap64 __builtin_bswap64
-#else
-
-static inline uint16_t bswap16(uint16_t n) {
-	return (n << 8) | (n >> 8);
-}
-
-static inline uint32_t bswap32(uint32_t n) {
-	return ((uint32_t)bswap16(n) << 16) | bswap16(n >> 16);
-}
-
-static inline uint64_t bswap64(uint64_t n) {
-	return ((uint64_t)bswap32(n) << 32) | bswap32(n >> 32);
-}
-
-#endif
-
-static inline uint8_t bswap8(uint8_t n) {
-	return n;
-}
-
-/**
- * Reverse the byte order of an integer.
- */
-#define bswap(n) \
-	_Generic((n), \
-		uint8_t: bswap8, \
-		uint16_t: bswap16, \
-		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/src/trie.c b/src/trie.c
index 2226890..7c2f65d 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -82,9 +82,9 @@
  */
 
 #include "trie.h"
+#include "bit.h"
 #include "config.h"
 #include "diag.h"
-#include "int.h"
 #include "list.h"
 #include <assert.h>
 #include <limits.h>
diff --git a/tests/bit.c b/tests/bit.c
new file mode 100644
index 0000000..7a7b0f3
--- /dev/null
+++ b/tests/bit.c
@@ -0,0 +1,121 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+#undef NDEBUG
+
+#include "../src/bit.h"
+#include "../src/diag.h"
+#include <assert.h>
+#include <limits.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+bfs_static_assert(UMAX_WIDTH(0x1) == 1);
+bfs_static_assert(UMAX_WIDTH(0x3) == 2);
+bfs_static_assert(UMAX_WIDTH(0x7) == 3);
+bfs_static_assert(UMAX_WIDTH(0xF) == 4);
+bfs_static_assert(UMAX_WIDTH(0xFF) == 8);
+bfs_static_assert(UMAX_WIDTH(0xFFF) == 12);
+bfs_static_assert(UMAX_WIDTH(0xFFFF) == 16);
+
+#define UWIDTH_MAX(n) (2 * ((UINTMAX_C(1) << ((n) - 1)) - 1) + 1)
+#define IWIDTH_MAX(n) UWIDTH_MAX((n) - 1)
+#define IWIDTH_MIN(n) (-(intmax_t)IWIDTH_MAX(n) - 1)
+
+bfs_static_assert(UCHAR_MAX == UWIDTH_MAX(UCHAR_WIDTH));
+bfs_static_assert(SCHAR_MIN == IWIDTH_MIN(SCHAR_WIDTH));
+bfs_static_assert(SCHAR_MAX == IWIDTH_MAX(SCHAR_WIDTH));
+
+bfs_static_assert(USHRT_MAX == UWIDTH_MAX(USHRT_WIDTH));
+bfs_static_assert(SHRT_MIN == IWIDTH_MIN(SHRT_WIDTH));
+bfs_static_assert(SHRT_MAX == IWIDTH_MAX(SHRT_WIDTH));
+
+bfs_static_assert(UINT_MAX == UWIDTH_MAX(UINT_WIDTH));
+bfs_static_assert(INT_MIN == IWIDTH_MIN(INT_WIDTH));
+bfs_static_assert(INT_MAX == IWIDTH_MAX(INT_WIDTH));
+
+bfs_static_assert(ULONG_MAX == UWIDTH_MAX(ULONG_WIDTH));
+bfs_static_assert(LONG_MIN == IWIDTH_MIN(LONG_WIDTH));
+bfs_static_assert(LONG_MAX == IWIDTH_MAX(LONG_WIDTH));
+
+bfs_static_assert(ULLONG_MAX == UWIDTH_MAX(ULLONG_WIDTH));
+bfs_static_assert(LLONG_MIN == IWIDTH_MIN(LLONG_WIDTH));
+bfs_static_assert(LLONG_MAX == IWIDTH_MAX(LLONG_WIDTH));
+
+bfs_static_assert(SIZE_MAX == UWIDTH_MAX(SIZE_WIDTH));
+bfs_static_assert(PTRDIFF_MIN == IWIDTH_MIN(PTRDIFF_WIDTH));
+bfs_static_assert(PTRDIFF_MAX == IWIDTH_MAX(PTRDIFF_WIDTH));
+
+bfs_static_assert(UINTPTR_MAX == UWIDTH_MAX(UINTPTR_WIDTH));
+bfs_static_assert(INTPTR_MIN == IWIDTH_MIN(INTPTR_WIDTH));
+bfs_static_assert(INTPTR_MAX == IWIDTH_MAX(INTPTR_WIDTH));
+
+bfs_static_assert(UINTMAX_MAX == UWIDTH_MAX(UINTMAX_WIDTH));
+bfs_static_assert(INTMAX_MIN == IWIDTH_MIN(INTMAX_WIDTH));
+bfs_static_assert(INTMAX_MAX == IWIDTH_MAX(INTMAX_WIDTH));
+
+int main(void) {
+	assert(bswap((uint8_t)0x12) == 0x12);
+	assert(bswap((uint16_t)0x1234) == 0x3412);
+	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;
+}
diff --git a/tests/int.c b/tests/int.c
deleted file mode 100644
index e59efde..0000000
--- a/tests/int.c
+++ /dev/null
@@ -1,121 +0,0 @@
-// Copyright © Tavian Barnes <tavianator@tavianator.com>
-// SPDX-License-Identifier: 0BSD
-
-#undef NDEBUG
-
-#include "../src/int.h"
-#include "../src/diag.h"
-#include <assert.h>
-#include <limits.h>
-#include <stdint.h>
-#include <stdlib.h>
-
-bfs_static_assert(UMAX_WIDTH(0x1) == 1);
-bfs_static_assert(UMAX_WIDTH(0x3) == 2);
-bfs_static_assert(UMAX_WIDTH(0x7) == 3);
-bfs_static_assert(UMAX_WIDTH(0xF) == 4);
-bfs_static_assert(UMAX_WIDTH(0xFF) == 8);
-bfs_static_assert(UMAX_WIDTH(0xFFF) == 12);
-bfs_static_assert(UMAX_WIDTH(0xFFFF) == 16);
-
-#define UWIDTH_MAX(n) (2 * ((UINTMAX_C(1) << ((n) - 1)) - 1) + 1)
-#define IWIDTH_MAX(n) UWIDTH_MAX((n) - 1)
-#define IWIDTH_MIN(n) (-(intmax_t)IWIDTH_MAX(n) - 1)
-
-bfs_static_assert(UCHAR_MAX == UWIDTH_MAX(UCHAR_WIDTH));
-bfs_static_assert(SCHAR_MIN == IWIDTH_MIN(SCHAR_WIDTH));
-bfs_static_assert(SCHAR_MAX == IWIDTH_MAX(SCHAR_WIDTH));
-
-bfs_static_assert(USHRT_MAX == UWIDTH_MAX(USHRT_WIDTH));
-bfs_static_assert(SHRT_MIN == IWIDTH_MIN(SHRT_WIDTH));
-bfs_static_assert(SHRT_MAX == IWIDTH_MAX(SHRT_WIDTH));
-
-bfs_static_assert(UINT_MAX == UWIDTH_MAX(UINT_WIDTH));
-bfs_static_assert(INT_MIN == IWIDTH_MIN(INT_WIDTH));
-bfs_static_assert(INT_MAX == IWIDTH_MAX(INT_WIDTH));
-
-bfs_static_assert(ULONG_MAX == UWIDTH_MAX(ULONG_WIDTH));
-bfs_static_assert(LONG_MIN == IWIDTH_MIN(LONG_WIDTH));
-bfs_static_assert(LONG_MAX == IWIDTH_MAX(LONG_WIDTH));
-
-bfs_static_assert(ULLONG_MAX == UWIDTH_MAX(ULLONG_WIDTH));
-bfs_static_assert(LLONG_MIN == IWIDTH_MIN(LLONG_WIDTH));
-bfs_static_assert(LLONG_MAX == IWIDTH_MAX(LLONG_WIDTH));
-
-bfs_static_assert(SIZE_MAX == UWIDTH_MAX(SIZE_WIDTH));
-bfs_static_assert(PTRDIFF_MIN == IWIDTH_MIN(PTRDIFF_WIDTH));
-bfs_static_assert(PTRDIFF_MAX == IWIDTH_MAX(PTRDIFF_WIDTH));
-
-bfs_static_assert(UINTPTR_MAX == UWIDTH_MAX(UINTPTR_WIDTH));
-bfs_static_assert(INTPTR_MIN == IWIDTH_MIN(INTPTR_WIDTH));
-bfs_static_assert(INTPTR_MAX == IWIDTH_MAX(INTPTR_WIDTH));
-
-bfs_static_assert(UINTMAX_MAX == UWIDTH_MAX(UINTMAX_WIDTH));
-bfs_static_assert(INTMAX_MIN == IWIDTH_MIN(INTMAX_WIDTH));
-bfs_static_assert(INTMAX_MAX == IWIDTH_MAX(INTMAX_WIDTH));
-
-int main(void) {
-	assert(bswap((uint8_t)0x12) == 0x12);
-	assert(bswap((uint16_t)0x1234) == 0x3412);
-	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;
-}
-- 
cgit v1.2.3