diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | src/int.h | 100 | ||||
| -rw-r--r-- | tests/int.c | 54 |
3 files changed, 155 insertions, 1 deletions
@@ -240,7 +240,7 @@ LIBBFS := \ $(BIN)/bfs: $(OBJ)/src/main.o $(LIBBFS) # Standalone unit tests -UNITS := bfstd trie xtimegm +UNITS := bfstd int trie xtimegm UNIT_TESTS := $(UNITS:%=$(BIN)/tests/%) UNIT_CHECKS := $(UNITS:%=check-%) diff --git a/src/int.h b/src/int.h new file mode 100644 index 0000000..56fabee --- /dev/null +++ b/src/int.h @@ -0,0 +1,100 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +/** + * Bits & bytes. + */ + +#ifndef BFS_INT_H +#define BFS_INT_H + +#include <limits.h> +#include <stdint.h> + +// 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 + +#endif // BFS_INT_H diff --git a/tests/int.c b/tests/int.c new file mode 100644 index 0000000..db59e90 --- /dev/null +++ b/tests/int.c @@ -0,0 +1,54 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +#include "../src/int.h" +#include "../src/diag.h" +#include <limits.h> +#include <stdint.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) { +} |