summaryrefslogtreecommitdiffstats
path: root/src/int.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/int.h')
-rw-r--r--src/int.h355
1 files changed, 0 insertions, 355 deletions
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