Something went wrong. Try again.
A breadth-first version of the UNIX find command tavianator.com/projects/bfs.html
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474// Copyright © Tavian Barnes <tavianator@tavianator.com>// SPDX-License-Identifier: 0BSD
/** * Bits & bytes. */
#ifndef BFS_BIT_H#define BFS_BIT_H
#include "bfs.h"
#include <limits.h>#include <stdint.h>
#if __has_include(<stdbit.h>)# 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
// See https://gcc.gnu.org/onlinedocs/cpp/Common-Predefined-Macros.html
#ifndef USHRT_WIDTH# ifdef __SHRT_WIDTH__# define USHRT_WIDTH __SHRT_WIDTH__# else# define USHRT_WIDTH UMAX_WIDTH(USHRT_MAX)# endif#endif
#ifndef UINT_WIDTH# ifdef __INT_WIDTH__# define UINT_WIDTH __INT_WIDTH__# else# define UINT_WIDTH UMAX_WIDTH(UINT_MAX)# endif#endif
#ifndef ULONG_WIDTH# ifdef __LONG_WIDTH__# define ULONG_WIDTH __LONG_WIDTH__# else# define ULONG_WIDTH UMAX_WIDTH(ULONG_MAX)# endif#endif
#ifndef ULLONG_WIDTH# ifdef __LONG_LONG_WIDTH__# define ULLONG_WIDTH __LONG_LONG_WIDTH__# elif defined(__LLONG_WIDTH__) // Clang# define ULLONG_WIDTH __LLONG_WIDTH__# else# define ULLONG_WIDTH UMAX_WIDTH(ULLONG_MAX)# endif#endif
#ifndef SIZE_WIDTH# ifdef __SIZE_WIDTH__# define SIZE_WIDTH __SIZE_WIDTH__# else# define SIZE_WIDTH UMAX_WIDTH(SIZE_MAX)# endif#endif
#ifndef PTRDIFF_WIDTH# ifdef __PTRDIFF_WIDTH__# define PTRDIFF_WIDTH __PTRDIFF_WIDTH__# else# define PTRDIFF_WIDTH UMAX_WIDTH(PTRDIFF_MAX)# endif#endif
#ifndef UINTPTR_WIDTH# ifdef __INTPTR_WIDTH__# define UINTPTR_WIDTH __INTPTR_WIDTH__# else# define UINTPTR_WIDTH UMAX_WIDTH(UINTPTR_MAX)# endif#endif
#ifndef UINTMAX_WIDTH# ifdef __INTMAX_WIDTH__# define UINTMAX_WIDTH __INTMAX_WIDTH__# else# define UINTMAX_WIDTH UMAX_WIDTH(UINTMAX_MAX)# endif#endif
#ifndef UCHAR_WIDTH# define UCHAR_WIDTH CHAR_WIDTH#endif#ifndef SCHAR_WIDTH# define SCHAR_WIDTH CHAR_WIDTH#endif#ifndef SHRT_WIDTH# define SHRT_WIDTH USHRT_WIDTH#endif#ifndef INT_WIDTH# define INT_WIDTH UINT_WIDTH#endif#ifndef LONG_WIDTH# define LONG_WIDTH ULONG_WIDTH#endif#ifndef LLONG_WIDTH# define LLONG_WIDTH ULLONG_WIDTH#endif#ifndef INTPTR_WIDTH# define INTPTR_WIDTH UINTPTR_WIDTH#endif#ifndef INTMAX_WIDTH# define INTMAX_WIDTH UINTMAX_WIDTH#endif
// N3022 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(__BYTE_ORDER__)# define ENDIAN_NATIVE __BYTE_ORDER__#else# define ENDIAN_NATIVE 0#endif
#if __GNUC__# define bswap_u16 __builtin_bswap16# define bswap_u32 __builtin_bswap32# define bswap_u64 __builtin_bswap64#else
static inline uint16_t bswap_u16(uint16_t n) { return (n << 8) | (n >> 8);}
static inline uint32_t bswap_u32(uint32_t n) { return ((uint32_t)bswap_u16(n) << 16) | bswap_u16(n >> 16);}
static inline uint64_t bswap_u64(uint64_t n) { return ((uint64_t)bswap_u32(n) << 32) | bswap_u32(n >> 32);}
#endif
static inline uint8_t bswap_u8(uint8_t n) { return n;}
#if UCHAR_WIDTH == 8# define bswap_uc bswap_u8#endif
#if USHRT_WIDTH == 16# define bswap_us bswap_u16#elif USHRT_WIDTH == 32# define bswap_us bswap_u32#elif USHRT_WIDTH == 64# define bswap_us bswap_u64#endif
#if UINT_WIDTH == 16# define bswap_ui bswap_u16#elif UINT_WIDTH == 32# define bswap_ui bswap_u32#elif UINT_WIDTH == 64# define bswap_ui bswap_u64#endif
#if ULONG_WIDTH == 32# define bswap_ul bswap_u32#elif ULONG_WIDTH == 64# define bswap_ul bswap_u64#endif
#if ULLONG_WIDTH == 64# define bswap_ull bswap_u64#endif
// 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), \ unsigned char: name##_uc, \ unsigned short: name##_us, \ unsigned int: name##_ui, \ unsigned long: name##_ul, \ unsigned long long: name##_ull)
/** * Reverse the byte order of an integer. */#define bswap(n) UINT_SELECT(n, bswap)(n)
#define LOAD8_LEU8(ptr, i, n) ((uint##n##_t)((const unsigned char *)ptr)[(i) / 8] << (i))#define LOAD8_BEU8(ptr, i, n) ((uint##n##_t)((const unsigned char *)ptr)[(i) / 8] << (n - (i) - 8))
/** Load a little-endian 8-bit word. */static inline uint8_t load8_leu8(const void *ptr) { return LOAD8_LEU8(ptr, 0, 8);}
/** Load a big-endian 8-bit word. */static inline uint8_t load8_beu8(const void *ptr) { return LOAD8_BEU8(ptr, 0, 8);}
#define LOAD8_LEU16(ptr, i, n) (LOAD8_LEU8(ptr, i, n) | LOAD8_LEU8(ptr, i + 8, n))#define LOAD8_BEU16(ptr, i, n) (LOAD8_BEU8(ptr, i, n) | LOAD8_BEU8(ptr, i + 8, n))
/** Load a little-endian 16-bit word. */static inline uint16_t load8_leu16(const void *ptr) { return LOAD8_LEU16(ptr, 0, 16);}
/** Load a big-endian 16-bit word. */static inline uint16_t load8_beu16(const void *ptr) { return LOAD8_BEU16(ptr, 0, 16);}
#define LOAD8_LEU32(ptr, i, n) (LOAD8_LEU16(ptr, i, n) | LOAD8_LEU16(ptr, i + 16, n))#define LOAD8_BEU32(ptr, i, n) (LOAD8_BEU16(ptr, i, n) | LOAD8_BEU16(ptr, i + 16, n))
/** Load a little-endian 32-bit word. */static inline uint32_t load8_leu32(const void *ptr) { return LOAD8_LEU32(ptr, 0, 32);}
/** Load a big-endian 32-bit word. */static inline uint32_t load8_beu32(const void *ptr) { return LOAD8_BEU32(ptr, 0, 32);}
#define LOAD8_LEU64(ptr, i, n) (LOAD8_LEU32(ptr, i, n) | LOAD8_LEU32(ptr, i + 32, n))#define LOAD8_BEU64(ptr, i, n) (LOAD8_BEU32(ptr, i, n) | LOAD8_BEU32(ptr, i + 32, n))
/** Load a little-endian 64-bit word. */static inline uint64_t load8_leu64(const void *ptr) { return LOAD8_LEU64(ptr, 0, 64);}
/** Load a big-endian 64-bit word. */static inline uint64_t load8_beu64(const void *ptr) { return LOAD8_BEU64(ptr, 0, 64);}
// C23 polyfill: bit utilities
#if __STDC_VERSION_STDBIT_H__ >= C23# define count_ones stdc_count_ones# define count_zeros stdc_count_zeros# 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 unsigned int count_ones##suffix(type n) { \ return UINT_BUILTIN(popcount, suffix)(n); \ }
#define LEADING_ZEROS(type, suffix, width) \ static inline unsigned 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 unsigned int trailing_zeros##suffix(type n) { \ return n ? UINT_BUILTIN(ctz, suffix)(n) : (int)width; \ }
#define FIRST_TRAILING_ONE(type, suffix, width) \ static inline unsigned int first_trailing_one##suffix(type n) { \ return UINT_BUILTIN(ffs, suffix)(n); \ }
#else // !__GNUC__
#define COUNT_ONES(type, suffix, width) \ static inline unsigned 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 unsigned 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 unsigned 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 unsigned 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 FIRST_LEADING_ONE(type, suffix, width) \ static inline unsigned int first_leading_one##suffix(type n) { \ return n ? leading_zeros##suffix(n) + 1 : 0; \ }
#define HAS_SINGLE_BIT(type, suffix, width) \ static inline bool has_single_bit##suffix(type n) { \ /** Branchless n && !(n & (n - 1)) */ \ return n - 1 < (n ^ (n - 1)); \ }
#define BIT_WIDTH(type, suffix, width) \ static inline unsigned int bit_width##suffix(type n) { \ return width - leading_zeros##suffix(n); \ }
#define BIT_FLOOR(type, suffix, width) \ static inline type bit_floor##suffix(type n) { \ return n ? (type)1 << (bit_width##suffix(n) - 1) : 0; \ }
#define BIT_CEIL(type, suffix, width) \ static inline type bit_ceil##suffix(type n) { \ return (type)1 << bit_width##suffix(n - !!n); \ }
UINT_OVERLOADS(FIRST_LEADING_ONE)UINT_OVERLOADS(HAS_SINGLE_BIT)UINT_OVERLOADS(BIT_WIDTH)UINT_OVERLOADS(BIT_FLOOR)UINT_OVERLOADS(BIT_CEIL)
#define count_ones(n) UINT_SELECT(n, count_ones)(n)#define count_zeros(n) UINT_SELECT(n, count_ones)(~(n))
#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_width(n) UINT_SELECT(n, bit_width)(n)#define bit_floor(n) UINT_SELECT(n, bit_floor)(n)#define bit_ceil(n) UINT_SELECT(n, bit_ceil)(n)
#endif // __STDC_VERSION_STDBIT_H__ < C23
#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)); \ }
UINT_OVERLOADS(ROTATE_LEFT)UINT_OVERLOADS(ROTATE_RIGHT)
#define rotate_left(n, c) UINT_SELECT(n, rotate_left)(n, c)#define rotate_right(n, c) UINT_SELECT(n, rotate_right)(n, c)
#endif // BFS_BIT_H