src/bit.h

   1 // Copyright © Tavian Barnes <tavianator@tavianator.com>
   2 // SPDX-License-Identifier: 0BSD
   3
   4 /**
   5  * Bits & bytes.
   6  */
   7
   8 #ifndef BFS_BIT_H
   9 #define BFS_BIT_H
  10
  11 #include "config.h"
  12 #include <limits.h>
  13 #include <stdint.h>
  14
  15 #if __STDC_VERSION__ >= 202311L
  16 #  include <stdbit.h>
  17 #endif
  18
  19 // C23 polyfill: _WIDTH macros
  20
  21 // The U*_MAX macros are of the form 2**n - 1, and we want to extract the n.
  22 // One way would be *_WIDTH = popcount(*_MAX).  Alternatively, we can use
  23 // Hallvard B. Furuseth's technique from [1], which is shorter.
  24 //
  25 // [1]: https://groups.google.com/g/comp.lang.c/c/NfedEFBFJ0k
  26
  27 // Let mask be of the form 2**m - 1, e.g. 0b111, and let n range over
  28 // [0b0, 0b1, 0b11, 0b111, 0b1111, ...].  Then we have
  29 //
  30 //     n % 0b111
  31 //         == [0b0, 0b1, 0b11, 0b0, 0b1, 0b11, ...]
  32 //     n / (n % 0b111 + 1)
  33 //         == [0b0 (x3), 0b111 (x3), 0b111111 (x3), ...]
  34 //     n / (n % 0b111 + 1) / 0b111
  35 //         == [0b0 (x3), 0b1 (x3), 0b1001 (x3), 0b1001001 (x3), ...]
  36 //     n / (n % 0b111 + 1) / 0b111 % 0b111
  37 //         == [0 (x3), 1 (x3), 2 (x3), ...]
  38 //         == UMAX_CHUNK(n, 0b111)
  39 #define UMAX_CHUNK(n, mask) (n / (n % mask + 1) / mask % mask)
  40
  41 // 8 * UMAX_CHUNK(n, 255) gives [0 (x8), 8 (x8), 16 (x8), ...].  To that we add
  42 // [0, 1, 2, ..., 6, 7, 0, 1, ...], which we get from a linear interpolation on
  43 // n % 255:
  44 //
  45 //     n % 255
  46 //         == [0, 1, 3, 7, 15, 31, 63, 127, 0, ...]
  47 //     86 / (n % 255 + 12)
  48 //         == [7, 6, 5, 4, 3, 2, 1, 0, 7, ...]
  49 #define UMAX_INTERP(n) (7 - 86 / (n % 255 + 12))
  50
  51 #define UMAX_WIDTH(n) (8 * UMAX_CHUNK(n, 255) + UMAX_INTERP(n))
  52
  53 #ifndef CHAR_WIDTH
  54 #  define CHAR_WIDTH CHAR_BIT
  55 #endif
  56
  57 // See https://gcc.gnu.org/onlinedocs/cpp/Common-Predefined-Macros.html
  58
  59 #ifndef USHRT_WIDTH
  60 #  ifdef __SHRT_WIDTH__
  61 #    define USHRT_WIDTH __SHRT_WIDTH__
  62 #  else
  63 #    define USHRT_WIDTH UMAX_WIDTH(USHRT_MAX)
  64 #  endif
  65 #endif
  66
  67 #ifndef UINT_WIDTH
  68 #  ifdef __INT_WIDTH__
  69 #    define UINT_WIDTH __INT_WIDTH__
  70 #  else
  71 #    define UINT_WIDTH UMAX_WIDTH(UINT_MAX)
  72 #  endif
  73 #endif
  74
  75 #ifndef ULONG_WIDTH
  76 #  ifdef __LONG_WIDTH__
  77 #    define ULONG_WIDTH __LONG_WIDTH__
  78 #  else
  79 #    define ULONG_WIDTH UMAX_WIDTH(ULONG_MAX)
  80 #  endif
  81 #endif
  82
  83 #ifndef ULLONG_WIDTH
  84 #  ifdef __LONG_LONG_WIDTH__
  85 #    define ULLONG_WIDTH __LONG_LONG_WIDTH__
  86 #  elif defined(__LLONG_WIDTH__) // Clang
  87 #    define ULLONG_WIDTH __LLONG_WIDTH__
  88 #  else
  89 #    define ULLONG_WIDTH UMAX_WIDTH(ULLONG_MAX)
  90 #  endif
  91 #endif
  92
  93 #ifndef SIZE_WIDTH
  94 #  ifdef __SIZE_WIDTH__
  95 #    define SIZE_WIDTH __SIZE_WIDTH__
  96 #  else
  97 #    define SIZE_WIDTH UMAX_WIDTH(SIZE_MAX)
  98 #  endif
  99 #endif
 100
 101 #ifndef PTRDIFF_WIDTH
 102 #  ifdef __PTRDIFF_WIDTH__
 103 #    define PTRDIFF_WIDTH __PTRDIFF_WIDTH__
 104 #  else
 105 #    define PTRDIFF_WIDTH UMAX_WIDTH(PTRDIFF_MAX)
 106 #  endif
 107 #endif
 108
 109 #ifndef UINTPTR_WIDTH
 110 #  ifdef __INTPTR_WIDTH__
 111 #    define UINTPTR_WIDTH __INTPTR_WIDTH__
 112 #  else
 113 #    define UINTPTR_WIDTH UMAX_WIDTH(UINTPTR_MAX)
 114 #  endif
 115 #endif
 116
 117 #ifndef UINTMAX_WIDTH
 118 #  ifdef __INTMAX_WIDTH__
 119 #    define UINTMAX_WIDTH __INTMAX_WIDTH__
 120 #  else
 121 #    define UINTMAX_WIDTH UMAX_WIDTH(UINTMAX_MAX)
 122 #  endif
 123 #endif
 124
 125 #ifndef UCHAR_WIDTH
 126 #  define UCHAR_WIDTH CHAR_WIDTH
 127 #endif
 128 #ifndef SCHAR_WIDTH
 129 #  define SCHAR_WIDTH CHAR_WIDTH
 130 #endif
 131 #ifndef SHRT_WIDTH
 132 #  define SHRT_WIDTH USHRT_WIDTH
 133 #endif
 134 #ifndef INT_WIDTH
 135 #  define INT_WIDTH UINT_WIDTH
 136 #endif
 137 #ifndef LONG_WIDTH
 138 #  define LONG_WIDTH ULONG_WIDTH
 139 #endif
 140 #ifndef LLONG_WIDTH
 141 #  define LLONG_WIDTH ULLONG_WIDTH
 142 #endif
 143 #ifndef INTPTR_WIDTH
 144 #  define INTPTR_WIDTH UINTPTR_WIDTH
 145 #endif
 146 #ifndef INTMAX_WIDTH
 147 #  define INTMAX_WIDTH UINTMAX_WIDTH
 148 #endif
 149
 150 // C23 polyfill: byte order
 151
 152 #ifdef __STDC_ENDIAN_LITTLE__
 153 #  define ENDIAN_LITTLE __STDC_ENDIAN_LITTLE__
 154 #elif defined(__ORDER_LITTLE_ENDIAN__)
 155 #  define ENDIAN_LITTLE __ORDER_LITTLE_ENDIAN__
 156 #else
 157 #  define ENDIAN_LITTLE 1234
 158 #endif
 159
 160 #ifdef __STDC_ENDIAN_BIG__
 161 #  define ENDIAN_BIG __STDC_ENDIAN_BIG__
 162 #elif defined(__ORDER_BIG_ENDIAN__)
 163 #  define ENDIAN_BIG __ORDER_BIG_ENDIAN__
 164 #else
 165 #  define ENDIAN_BIG 4321
 166 #endif
 167
 168 #ifdef __STDC_ENDIAN_NATIVE__
 169 #  define ENDIAN_NATIVE __STDC_ENDIAN_NATIVE__
 170 #elif defined(__ORDER_NATIVE_ENDIAN__)
 171 #  define ENDIAN_NATIVE __ORDER_NATIVE_ENDIAN__
 172 #else
 173 #  define ENDIAN_NATIVE 0
 174 #endif
 175
 176 #if __STDC_VERSION__ >= 202311L
 177 #  define bswap16 stdc_memreverse8u16
 178 #  define bswap32 stdc_memreverse8u32
 179 #  define bswap64 stdc_memreverse8u64
 180 #elif __GNUC__
 181 #  define bswap16 __builtin_bswap16
 182 #  define bswap32 __builtin_bswap32
 183 #  define bswap64 __builtin_bswap64
 184 #else
 185
 186 static inline uint16_t bswap16(uint16_t n) {
 187         return (n << 8) | (n >> 8);
 188 }
 189
 190 static inline uint32_t bswap32(uint32_t n) {
 191         return ((uint32_t)bswap16(n) << 16) | bswap16(n >> 16);
 192 }
 193
 194 static inline uint64_t bswap64(uint64_t n) {
 195         return ((uint64_t)bswap32(n) << 32) | bswap32(n >> 32);
 196 }
 197
 198 #endif
 199
 200 static inline uint8_t bswap8(uint8_t n) {
 201         return n;
 202 }
 203
 204 /**
 205  * Reverse the byte order of an integer.
 206  */
 207 #define bswap(n) \
 208         _Generic((n), \
 209                 uint8_t: bswap8, \
 210                 uint16_t: bswap16, \
 211                 uint32_t: bswap32, \
 212                 uint64_t: bswap64)(n)
 213
 214 // Define an overload for each unsigned type
 215 #define UINT_OVERLOADS(macro) \
 216         macro(unsigned char, _uc, UCHAR_WIDTH) \
 217         macro(unsigned short, _us, USHRT_WIDTH) \
 218         macro(unsigned int, _ui, UINT_WIDTH) \
 219         macro(unsigned long, _ul, ULONG_WIDTH) \
 220         macro(unsigned long long, _ull, ULLONG_WIDTH)
 221
 222 // Select an overload based on an unsigned integer type
 223 #define UINT_SELECT(n, name) \
 224         _Generic((n), \
 225                 char:               name##_uc, \
 226                 signed char:        name##_uc, \
 227                 unsigned char:      name##_uc, \
 228                 signed short:       name##_us, \
 229                 unsigned short:     name##_us, \
 230                 signed int:         name##_ui, \
 231                 unsigned int:       name##_ui, \
 232                 signed long:        name##_ul, \
 233                 unsigned long:      name##_ul, \
 234                 signed long long:   name##_ull, \
 235                 unsigned long long: name##_ull)
 236
 237 // C23 polyfill: bit utilities
 238
 239 #if __STDC_VERSION__ >= 202311L
 240 #  define count_ones stdc_count_ones
 241 #  define count_zeros stdc_count_zeros
 242 #  define rotate_left stdc_rotate_left
 243 #  define rotate_right stdc_rotate_right
 244 #  define leading_zeros stdc_leading_zeros
 245 #  define leading_ones stdc_leading_ones
 246 #  define trailing_zeros stdc_trailing_zeros
 247 #  define trailing_ones stdc_trailing_ones
 248 #  define first_leading_zero stdc_first_leading_zero
 249 #  define first_leading_one stdc_first_leading_one
 250 #  define first_trailing_zero stdc_first_trailing_zero
 251 #  define first_trailing_one stdc_first_trailing_one
 252 #  define has_single_bit stdc_has_single_bit
 253 #  define bit_width stdc_bit_width
 254 #  define bit_ceil stdc_bit_ceil
 255 #  define bit_floor stdc_bit_floor
 256 #else
 257
 258 #if __GNUC__
 259
 260 // GCC provides builtins for unsigned {int,long,long long}, so promote char/short
 261 #define UINT_BUILTIN_uc(name) __builtin_##name
 262 #define UINT_BUILTIN_us(name) __builtin_##name
 263 #define UINT_BUILTIN_ui(name) __builtin_##name
 264 #define UINT_BUILTIN_ul(name) __builtin_##name##l
 265 #define UINT_BUILTIN_ull(name) __builtin_##name##ll
 266 #define UINT_BUILTIN(name, suffix) UINT_BUILTIN##suffix(name)
 267
 268 #define BUILTIN_WIDTH_uc UINT_WIDTH
 269 #define BUILTIN_WIDTH_us UINT_WIDTH
 270 #define BUILTIN_WIDTH_ui UINT_WIDTH
 271 #define BUILTIN_WIDTH_ul ULONG_WIDTH
 272 #define BUILTIN_WIDTH_ull ULLONG_WIDTH
 273 #define BUILTIN_WIDTH(suffix) BUILTIN_WIDTH##suffix
 274
 275 #define COUNT_ONES(type, suffix, width) \
 276         static inline int count_ones##suffix(type n) { \
 277                 return UINT_BUILTIN(popcount, suffix)(n); \
 278         }
 279
 280 #define LEADING_ZEROS(type, suffix, width) \
 281         static inline int leading_zeros##suffix(type n) { \
 282                 return n \
 283                         ? UINT_BUILTIN(clz, suffix)(n) - (BUILTIN_WIDTH(suffix) - width) \
 284                         : width; \
 285         }
 286
 287 #define TRAILING_ZEROS(type, suffix, width) \
 288         static inline int trailing_zeros##suffix(type n) { \
 289                 return n ? UINT_BUILTIN(ctz, suffix)(n) : (int)width; \
 290         }
 291
 292 #define FIRST_TRAILING_ONE(type, suffix, width) \
 293         static inline int first_trailing_one##suffix(type n) { \
 294                 return UINT_BUILTIN(ffs, suffix)(n); \
 295         }
 296
 297 #else // !__GNUC__
 298
 299 #define COUNT_ONES(type, suffix, width) \
 300         static inline int count_ones##suffix(type n) { \
 301                 int ret; \
 302                 for (ret = 0; n; ++ret) { \
 303                         n &= n - 1; \
 304                 } \
 305                 return ret; \
 306         }
 307
 308 #define LEADING_ZEROS(type, suffix, width) \
 309         static inline int leading_zeros##suffix(type n) { \
 310                 type bit = (type)1 << (width - 1); \
 311                 int ret; \
 312                 for (ret = 0; bit && !(n & bit); ++ret, bit >>= 1); \
 313                 return ret; \
 314         }
 315
 316 #define TRAILING_ZEROS(type, suffix, width) \
 317         static inline int trailing_zeros##suffix(type n) { \
 318                 type bit = 1; \
 319                 int ret; \
 320                 for (ret = 0; bit && !(n & bit); ++ret, bit <<= 1); \
 321                 return ret; \
 322         }
 323
 324 #define FIRST_TRAILING_ONE(type, suffix, width) \
 325         static inline int first_trailing_one##suffix(type n) { \
 326                 return n ? trailing_zeros##suffix(n) + 1 : 0; \
 327         }
 328
 329 #endif // !__GNUC__
 330
 331 UINT_OVERLOADS(COUNT_ONES)
 332 UINT_OVERLOADS(LEADING_ZEROS)
 333 UINT_OVERLOADS(TRAILING_ZEROS)
 334 UINT_OVERLOADS(FIRST_TRAILING_ONE)
 335
 336 #define ROTATE_LEFT(type, suffix, width) \
 337         static inline type rotate_left##suffix(type n, int c) { \
 338                 return (n << c) | (n >> ((width - c) % width)); \
 339         }
 340
 341 #define ROTATE_RIGHT(type, suffix, width) \
 342         static inline type rotate_right##suffix(type n, int c) { \
 343                 return (n >> c) | (n << ((width - c) % width)); \
 344         }
 345
 346 #define FIRST_LEADING_ONE(type, suffix, width) \
 347         static inline int first_leading_one##suffix(type n) { \
 348                 return width - leading_zeros##suffix(n); \
 349         }
 350
 351 #define HAS_SINGLE_BIT(type, suffix, width) \
 352         static inline bool has_single_bit##suffix(type n) { \
 353                 return n && !(n & (n - 1)); \
 354         }
 355
 356 UINT_OVERLOADS(ROTATE_LEFT)
 357 UINT_OVERLOADS(ROTATE_RIGHT)
 358 UINT_OVERLOADS(FIRST_LEADING_ONE)
 359 UINT_OVERLOADS(HAS_SINGLE_BIT)
 360
 361 #define count_ones(n) UINT_SELECT(n, count_ones)(n)
 362 #define count_zeros(n) UINT_SELECT(n, count_ones)(~(n))
 363
 364 #define rotate_left(n, c) UINT_SELECT(n, rotate_left)(n, c)
 365 #define rotate_right(n, c) UINT_SELECT(n, rotate_right)(n, c)
 366
 367 #define leading_zeros(n) UINT_SELECT(n, leading_zeros)(n)
 368 #define leading_ones(n) UINT_SELECT(n, leading_zeros)(~(n))
 369
 370 #define trailing_zeros(n) UINT_SELECT(n, trailing_zeros)(n)
 371 #define trailing_ones(n) UINT_SELECT(n, trailing_zeros)(~(n))
 372
 373 #define first_leading_one(n) UINT_SELECT(n, first_leading_one)(n)
 374 #define first_leading_zero(n) UINT_SELECT(n, first_leading_one)(~(n))
 375
 376 #define first_trailing_one(n) UINT_SELECT(n, first_trailing_one)(n)
 377 #define first_trailing_zero(n) UINT_SELECT(n, first_trailing_one)(~(n))
 378
 379 #define has_single_bit(n) UINT_SELECT(n, has_single_bit)(n)
 380
 381 #define BIT_FLOOR(type, suffix, width) \
 382         static inline type bit_floor##suffix(type n) { \
 383                 return n ? (type)1 << (first_leading_one##suffix(n) - 1) : 0; \
 384         }
 385
 386 #define BIT_CEIL(type, suffix, width) \
 387         static inline type bit_ceil##suffix(type n) { \
 388                 return (type)1 << first_leading_one##suffix(n - !!n); \
 389         }
 390
 391 UINT_OVERLOADS(BIT_FLOOR)
 392 UINT_OVERLOADS(BIT_CEIL)
 393
 394 #define bit_width(n) first_leading_one(n)
 395 #define bit_floor(n) UINT_SELECT(n, bit_floor)(n)
 396 #define bit_ceil(n) UINT_SELECT(n, bit_ceil)(n)
 397
 398 #endif // __STDC_VERSION__ < 202311L
 399
 400 #endif // BFS_BIT_H