497 lines
13 KiB
C
497 lines
13 KiB
C
#ifndef VLIBC_STDBIT_H
|
|
#define VLIBC_STDBIT_H
|
|
|
|
/*
|
|
* vlibc — <stdbit.h>.
|
|
*
|
|
* Bit and byte manipulation (C23 7.18). Every per-width operation is a
|
|
* static inline function over the GCC counting builtins
|
|
* (__builtin_clz/clzl/clzll, __builtin_ctz/ctzl/ctzll,
|
|
* __builtin_popcount/popcountl/popcountll), so no call escapes into the
|
|
* library. The type-generic names (stdc_leading_zeros, ...) dispatch through
|
|
* _Generic to the per-width functions; signed arguments convert to the
|
|
* unsigned type of the same rank, which preserves the bit pattern exactly as
|
|
* C23 specifies. Widths match x86_64: int is 32-bit, long is 64-bit.
|
|
*
|
|
* This header is ISO C core and is present in every profile.
|
|
*/
|
|
|
|
#include <vlibc/features.h>
|
|
|
|
#include <limits.h>
|
|
|
|
/* stdc_leading_zeros: number of 0 bits before the first 1 bit, or the width. */
|
|
static inline unsigned int
|
|
stdc_leading_zeros_uc(unsigned char x)
|
|
{
|
|
return x == 0 ? 8u : (unsigned int)(__builtin_clz(x) - 24);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_leading_zeros_us(unsigned short x)
|
|
{
|
|
return x == 0 ? 16u : (unsigned int)(__builtin_clz(x) - 16);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_leading_zeros_ui(unsigned int x)
|
|
{
|
|
return x == 0 ? 32u : (unsigned int)__builtin_clz(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_leading_zeros_ul(unsigned long x)
|
|
{
|
|
return x == 0 ? 64u : (unsigned int)__builtin_clzl(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_leading_zeros_ull(unsigned long long x)
|
|
{
|
|
return x == 0 ? 64u : (unsigned int)__builtin_clzll(x);
|
|
}
|
|
|
|
/* stdc_leading_ones: number of 1 bits before the first 0 bit, or the width. */
|
|
static inline unsigned int
|
|
stdc_leading_ones_uc(unsigned char x)
|
|
{
|
|
return x == UCHAR_MAX ? 8u : (unsigned int)(__builtin_clz((unsigned char)~x) - 24);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_leading_ones_us(unsigned short x)
|
|
{
|
|
return x == USHRT_MAX ? 16u : (unsigned int)(__builtin_clz((unsigned short)~x) - 16);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_leading_ones_ui(unsigned int x)
|
|
{
|
|
return x == UINT_MAX ? 32u : (unsigned int)__builtin_clz(~x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_leading_ones_ul(unsigned long x)
|
|
{
|
|
return x == ULONG_MAX ? 64u : (unsigned int)__builtin_clzl(~x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_leading_ones_ull(unsigned long long x)
|
|
{
|
|
return x == ULLONG_MAX ? 64u : (unsigned int)__builtin_clzll(~x);
|
|
}
|
|
|
|
/* stdc_trailing_zeros: number of 0 bits after the last 1 bit, or the width. */
|
|
static inline unsigned int
|
|
stdc_trailing_zeros_uc(unsigned char x)
|
|
{
|
|
return x == 0 ? 8u : (unsigned int)__builtin_ctz(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_trailing_zeros_us(unsigned short x)
|
|
{
|
|
return x == 0 ? 16u : (unsigned int)__builtin_ctz(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_trailing_zeros_ui(unsigned int x)
|
|
{
|
|
return x == 0 ? 32u : (unsigned int)__builtin_ctz(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_trailing_zeros_ul(unsigned long x)
|
|
{
|
|
return x == 0 ? 64u : (unsigned int)__builtin_ctzl(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_trailing_zeros_ull(unsigned long long x)
|
|
{
|
|
return x == 0 ? 64u : (unsigned int)__builtin_ctzll(x);
|
|
}
|
|
|
|
/* stdc_trailing_ones: number of 1 bits after the last 0 bit, or the width. */
|
|
static inline unsigned int
|
|
stdc_trailing_ones_uc(unsigned char x)
|
|
{
|
|
return x == UCHAR_MAX ? 8u : (unsigned int)__builtin_ctz((unsigned char)~x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_trailing_ones_us(unsigned short x)
|
|
{
|
|
return x == USHRT_MAX ? 16u : (unsigned int)__builtin_ctz((unsigned short)~x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_trailing_ones_ui(unsigned int x)
|
|
{
|
|
return x == UINT_MAX ? 32u : (unsigned int)__builtin_ctz(~x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_trailing_ones_ul(unsigned long x)
|
|
{
|
|
return x == ULONG_MAX ? 64u : (unsigned int)__builtin_ctzl(~x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_trailing_ones_ull(unsigned long long x)
|
|
{
|
|
return x == ULLONG_MAX ? 64u : (unsigned int)__builtin_ctzll(~x);
|
|
}
|
|
|
|
/*
|
|
* stdc_first_*: index (from the most significant bit) of the first zero/one
|
|
* bit, or the width when no such bit exists. By construction, the index of
|
|
* the first zero from the top equals the count of leading ones, and so on.
|
|
*/
|
|
static inline unsigned int
|
|
stdc_first_leading_zero_uc(unsigned char x)
|
|
{
|
|
return stdc_leading_ones_uc(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_zero_us(unsigned short x)
|
|
{
|
|
return stdc_leading_ones_us(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_zero_ui(unsigned int x)
|
|
{
|
|
return stdc_leading_ones_ui(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_zero_ul(unsigned long x)
|
|
{
|
|
return stdc_leading_ones_ul(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_zero_ull(unsigned long long x)
|
|
{
|
|
return stdc_leading_ones_ull(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_one_uc(unsigned char x)
|
|
{
|
|
return stdc_leading_zeros_uc(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_one_us(unsigned short x)
|
|
{
|
|
return stdc_leading_zeros_us(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_one_ui(unsigned int x)
|
|
{
|
|
return stdc_leading_zeros_ui(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_one_ul(unsigned long x)
|
|
{
|
|
return stdc_leading_zeros_ul(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_leading_one_ull(unsigned long long x)
|
|
{
|
|
return stdc_leading_zeros_ull(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_zero_uc(unsigned char x)
|
|
{
|
|
return stdc_trailing_ones_uc(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_zero_us(unsigned short x)
|
|
{
|
|
return stdc_trailing_ones_us(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_zero_ui(unsigned int x)
|
|
{
|
|
return stdc_trailing_ones_ui(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_zero_ul(unsigned long x)
|
|
{
|
|
return stdc_trailing_ones_ul(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_zero_ull(unsigned long long x)
|
|
{
|
|
return stdc_trailing_ones_ull(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_one_uc(unsigned char x)
|
|
{
|
|
return stdc_trailing_zeros_uc(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_one_us(unsigned short x)
|
|
{
|
|
return stdc_trailing_zeros_us(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_one_ui(unsigned int x)
|
|
{
|
|
return stdc_trailing_zeros_ui(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_one_ul(unsigned long x)
|
|
{
|
|
return stdc_trailing_zeros_ul(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_first_trailing_one_ull(unsigned long long x)
|
|
{
|
|
return stdc_trailing_zeros_ull(x);
|
|
}
|
|
|
|
/* stdc_count_ones: number of 1 bits. */
|
|
static inline unsigned int
|
|
stdc_count_ones_uc(unsigned char x)
|
|
{
|
|
return (unsigned int)__builtin_popcount(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_count_ones_us(unsigned short x)
|
|
{
|
|
return (unsigned int)__builtin_popcount(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_count_ones_ui(unsigned int x)
|
|
{
|
|
return (unsigned int)__builtin_popcount(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_count_ones_ul(unsigned long x)
|
|
{
|
|
return (unsigned int)__builtin_popcountl(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_count_ones_ull(unsigned long long x)
|
|
{
|
|
return (unsigned int)__builtin_popcountll(x);
|
|
}
|
|
|
|
/* stdc_count_zeros: number of 0 bits. */
|
|
static inline unsigned int
|
|
stdc_count_zeros_uc(unsigned char x)
|
|
{
|
|
return 8u - stdc_count_ones_uc(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_count_zeros_us(unsigned short x)
|
|
{
|
|
return 16u - stdc_count_ones_us(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_count_zeros_ui(unsigned int x)
|
|
{
|
|
return 32u - stdc_count_ones_ui(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_count_zeros_ul(unsigned long x)
|
|
{
|
|
return 64u - stdc_count_ones_ul(x);
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_count_zeros_ull(unsigned long long x)
|
|
{
|
|
return 64u - stdc_count_ones_ull(x);
|
|
}
|
|
|
|
/* stdc_has_single_bit: true iff exactly one bit is set. */
|
|
static inline _Bool
|
|
stdc_has_single_bit_uc(unsigned char x)
|
|
{
|
|
return x != 0 && (x & (x - 1U)) == 0;
|
|
}
|
|
|
|
static inline _Bool
|
|
stdc_has_single_bit_us(unsigned short x)
|
|
{
|
|
return x != 0 && (x & (x - 1U)) == 0;
|
|
}
|
|
|
|
static inline _Bool
|
|
stdc_has_single_bit_ui(unsigned int x)
|
|
{
|
|
return x != 0 && (x & (x - 1U)) == 0;
|
|
}
|
|
|
|
static inline _Bool
|
|
stdc_has_single_bit_ul(unsigned long x)
|
|
{
|
|
return x != 0 && (x & (x - 1UL)) == 0;
|
|
}
|
|
|
|
static inline _Bool
|
|
stdc_has_single_bit_ull(unsigned long long x)
|
|
{
|
|
return x != 0 && (x & (x - 1ULL)) == 0;
|
|
}
|
|
|
|
/* stdc_bit_width: bits needed to represent x (0 for 0, 1 for 1). */
|
|
static inline unsigned int
|
|
stdc_bit_width_uc(unsigned char x)
|
|
{
|
|
return x == 0 ? 0u : (unsigned int)(32 - __builtin_clz(x));
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_bit_width_us(unsigned short x)
|
|
{
|
|
return x == 0 ? 0u : (unsigned int)(32 - __builtin_clz(x));
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_bit_width_ui(unsigned int x)
|
|
{
|
|
return x == 0 ? 0u : (unsigned int)(32 - __builtin_clz(x));
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_bit_width_ul(unsigned long x)
|
|
{
|
|
return x == 0 ? 0u : (unsigned int)(64 - __builtin_clzl(x));
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_bit_width_ull(unsigned long long x)
|
|
{
|
|
return x == 0 ? 0u : (unsigned int)(64 - __builtin_clzll(x));
|
|
}
|
|
|
|
/* stdc_bit_floor: largest power of 2 not greater than x (0 for 0). */
|
|
static inline unsigned char
|
|
stdc_bit_floor_uc(unsigned char x)
|
|
{
|
|
return (unsigned char)(x == 0 ? 0 : (1u << (32 - __builtin_clz(x) - 1)));
|
|
}
|
|
|
|
static inline unsigned short
|
|
stdc_bit_floor_us(unsigned short x)
|
|
{
|
|
return (unsigned short)(x == 0 ? 0 : (1u << (32 - __builtin_clz(x) - 1)));
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_bit_floor_ui(unsigned int x)
|
|
{
|
|
return x == 0 ? 0u : (1u << (32 - __builtin_clz(x) - 1));
|
|
}
|
|
|
|
static inline unsigned long
|
|
stdc_bit_floor_ul(unsigned long x)
|
|
{
|
|
return x == 0 ? 0ul : (1ul << (64 - __builtin_clzl(x) - 1));
|
|
}
|
|
|
|
static inline unsigned long long
|
|
stdc_bit_floor_ull(unsigned long long x)
|
|
{
|
|
return x == 0 ? 0ull : (1ull << (64 - __builtin_clzll(x) - 1));
|
|
}
|
|
|
|
/*
|
|
* stdc_bit_ceil: smallest power of 2 not less than x. The result is
|
|
* undefined when it is not representable in the type of x, per C23.
|
|
*/
|
|
static inline unsigned char
|
|
stdc_bit_ceil_uc(unsigned char x)
|
|
{
|
|
return (unsigned char)(x <= 1 ? 1 : (1u << (32 - __builtin_clz(x - 1))));
|
|
}
|
|
|
|
static inline unsigned short
|
|
stdc_bit_ceil_us(unsigned short x)
|
|
{
|
|
return (unsigned short)(x <= 1 ? 1 : (1u << (32 - __builtin_clz(x - 1))));
|
|
}
|
|
|
|
static inline unsigned int
|
|
stdc_bit_ceil_ui(unsigned int x)
|
|
{
|
|
return x <= 1 ? 1u : (1u << (32 - __builtin_clz(x - 1)));
|
|
}
|
|
|
|
static inline unsigned long
|
|
stdc_bit_ceil_ul(unsigned long x)
|
|
{
|
|
return x <= 1 ? 1ul : (1ul << (64 - __builtin_clzl(x - 1)));
|
|
}
|
|
|
|
static inline unsigned long long
|
|
stdc_bit_ceil_ull(unsigned long long x)
|
|
{
|
|
return x <= 1 ? 1ull : (1ull << (64 - __builtin_clzll(x - 1)));
|
|
}
|
|
|
|
/*
|
|
* Type-generic dispatch: map the (lvalue-converted) argument type to the
|
|
* per-width function. Signed types route to the unsigned function of the
|
|
* same rank, which preserves the bit pattern as C23 requires.
|
|
*/
|
|
#define VLIBC_STDBIT_DISPATCH(fn, x) \
|
|
_Generic((x), \
|
|
_Bool: fn##_uc, \
|
|
char: fn##_uc, \
|
|
signed char: fn##_uc, \
|
|
unsigned char: fn##_uc, \
|
|
short: fn##_us, \
|
|
unsigned short: fn##_us, \
|
|
int: fn##_ui, \
|
|
unsigned int: fn##_ui, \
|
|
long: fn##_ul, \
|
|
unsigned long: fn##_ul, \
|
|
long long: fn##_ull, \
|
|
unsigned long long: fn##_ull)(x)
|
|
|
|
#define stdc_leading_zeros(x) VLIBC_STDBIT_DISPATCH(stdc_leading_zeros, x)
|
|
#define stdc_leading_ones(x) VLIBC_STDBIT_DISPATCH(stdc_leading_ones, x)
|
|
#define stdc_trailing_zeros(x) VLIBC_STDBIT_DISPATCH(stdc_trailing_zeros, x)
|
|
#define stdc_trailing_ones(x) VLIBC_STDBIT_DISPATCH(stdc_trailing_ones, x)
|
|
#define stdc_first_leading_zero(x) VLIBC_STDBIT_DISPATCH(stdc_first_leading_zero, x)
|
|
#define stdc_first_leading_one(x) VLIBC_STDBIT_DISPATCH(stdc_first_leading_one, x)
|
|
#define stdc_first_trailing_zero(x) VLIBC_STDBIT_DISPATCH(stdc_first_trailing_zero, x)
|
|
#define stdc_first_trailing_one(x) VLIBC_STDBIT_DISPATCH(stdc_first_trailing_one, x)
|
|
#define stdc_count_zeros(x) VLIBC_STDBIT_DISPATCH(stdc_count_zeros, x)
|
|
#define stdc_count_ones(x) VLIBC_STDBIT_DISPATCH(stdc_count_ones, x)
|
|
#define stdc_has_single_bit(x) VLIBC_STDBIT_DISPATCH(stdc_has_single_bit, x)
|
|
#define stdc_bit_width(x) VLIBC_STDBIT_DISPATCH(stdc_bit_width, x)
|
|
#define stdc_bit_floor(x) VLIBC_STDBIT_DISPATCH(stdc_bit_floor, x)
|
|
#define stdc_bit_ceil(x) VLIBC_STDBIT_DISPATCH(stdc_bit_ceil, x)
|
|
|
|
#endif /* VLIBC_STDBIT_H */
|