From 4505819c576fc93f21d73e1bf85550250cdb72a2 Mon Sep 17 00:00:00 2001 From: Tavian Barnes 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 +// SPDX-License-Identifier: 0BSD + +/** + * Bits & bytes. + */ + +#ifndef BFS_BIT_H +#define BFS_BIT_H + +#include "config.h" +#include +#include + +#if __STDC_VERSION__ >= 202311L +# include +#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 -// SPDX-License-Identifier: 0BSD - -/** - * Bits & bytes. - */ - -#ifndef BFS_INT_H -#define BFS_INT_H - -#include "config.h" -#include -#include - -#if __STDC_VERSION__ >= 202311L -# include -#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 #include 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 +// SPDX-License-Identifier: 0BSD + +#undef NDEBUG + +#include "../src/bit.h" +#include "../src/diag.h" +#include +#include +#include +#include + +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 -// SPDX-License-Identifier: 0BSD - -#undef NDEBUG - -#include "../src/int.h" -#include "../src/diag.h" -#include -#include -#include -#include - -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