22#ifndef LELY_UTIL_BITS_H_
23#define LELY_UTIL_BITS_H_
34#ifndef LELY_UTIL_BITS_INLINE
35#define LELY_UTIL_BITS_INLINE static inline
46LELY_UTIL_BITS_INLINE uint_least16_t
bswap16(uint_least16_t x);
52LELY_UTIL_BITS_INLINE uint_least32_t
bswap32(uint_least32_t x);
58LELY_UTIL_BITS_INLINE uint_least64_t
bswap64(uint_least64_t x);
62LELY_UTIL_BITS_INLINE
int cls8(uint_least8_t x);
68#if defined(_MSC_VER) || defined(__GNUC__) || __has_builtin(__builtin_clz)
69LELY_UTIL_BITS_INLINE
int clz8(uint_least8_t x);
71int clz8(uint_least8_t x);
78LELY_UTIL_BITS_INLINE
int cls16(uint_least16_t x);
84LELY_UTIL_BITS_INLINE
int clz16(uint_least16_t x);
90LELY_UTIL_BITS_INLINE
int cls32(uint_least32_t x);
96LELY_UTIL_BITS_INLINE
int clz32(uint_least32_t x);
102LELY_UTIL_BITS_INLINE
int cls64(uint_least64_t x);
108LELY_UTIL_BITS_INLINE
int clz64(uint_least64_t x);
114LELY_UTIL_BITS_INLINE
int cts8(uint_least8_t x);
120#if defined(_MSC_VER) || defined(__GNUC__) || __has_builtin(__builtin_ctz)
121LELY_UTIL_BITS_INLINE
int ctz8(uint_least8_t x);
123int ctz8(uint_least8_t x);
130LELY_UTIL_BITS_INLINE
int cts16(uint_least16_t x);
136LELY_UTIL_BITS_INLINE
int ctz16(uint_least16_t x);
142LELY_UTIL_BITS_INLINE
int cts32(uint_least32_t x);
148LELY_UTIL_BITS_INLINE
int ctz32(uint_least32_t x);
154LELY_UTIL_BITS_INLINE
int cts64(uint_least64_t x);
160LELY_UTIL_BITS_INLINE
int ctz64(uint_least64_t x);
166#if defined(_MSC_VER) || defined(__GNUC__) || __has_builtin(__builtin_ffs)
167LELY_UTIL_BITS_INLINE
int ffs8(uint_least8_t x);
169int ffs8(uint_least8_t x);
176LELY_UTIL_BITS_INLINE
int ffz8(uint_least8_t x);
182LELY_UTIL_BITS_INLINE
int ffs16(uint_least16_t x);
188LELY_UTIL_BITS_INLINE
int ffz16(uint_least16_t x);
194LELY_UTIL_BITS_INLINE
int ffs32(uint_least32_t x);
200LELY_UTIL_BITS_INLINE
int ffz32(uint_least32_t x);
206LELY_UTIL_BITS_INLINE
int ffs64(uint_least64_t x);
212LELY_UTIL_BITS_INLINE
int ffz64(uint_least64_t x);
215#if defined(__GNUC__) || __has_builtin(__builtin_parity)
216LELY_UTIL_BITS_INLINE
int parity8(uint_least8_t x);
222LELY_UTIL_BITS_INLINE
int parity16(uint_least16_t x);
225LELY_UTIL_BITS_INLINE
int parity32(uint_least32_t x);
228LELY_UTIL_BITS_INLINE
int parity64(uint_least64_t x);
234#if defined(__GNUC__) || __has_builtin(__builtin_popcount)
235LELY_UTIL_BITS_INLINE
int popcount8(uint_least8_t x);
244LELY_UTIL_BITS_INLINE
int popcount16(uint_least16_t x);
250LELY_UTIL_BITS_INLINE
int popcount32(uint_least32_t x);
256LELY_UTIL_BITS_INLINE
int popcount64(uint_least64_t x);
259LELY_UTIL_BITS_INLINE uint_least8_t
rol8(uint_least8_t x,
unsigned int n);
262LELY_UTIL_BITS_INLINE uint_least8_t
ror8(uint_least8_t x,
unsigned int n);
265LELY_UTIL_BITS_INLINE uint_least16_t
rol16(uint_least16_t x,
unsigned int n);
268LELY_UTIL_BITS_INLINE uint_least16_t
ror16(uint_least16_t x,
unsigned int n);
271LELY_UTIL_BITS_INLINE uint_least32_t
rol32(uint_least32_t x,
unsigned int n);
274LELY_UTIL_BITS_INLINE uint_least32_t
ror32(uint_least32_t x,
unsigned int n);
277LELY_UTIL_BITS_INLINE uint_least64_t
rol64(uint_least64_t x,
unsigned int n);
280LELY_UTIL_BITS_INLINE uint_least64_t
ror64(uint_least64_t x,
unsigned int n);
282LELY_UTIL_BITS_INLINE uint_least16_t
286 return _byteswap_ushort(x);
287#elif GNUC_PREREQ(4, 8) || __has_builtin(__builtin_bswap16)
288 return __builtin_bswap16(x);
290 return ((x & 0xff) << 8) | ((x >> 8) & 0xff);
294LELY_UTIL_BITS_INLINE uint_least32_t
298 return _byteswap_ulong(x);
299#elif GNUC_PREREQ(4, 3) || __has_builtin(__builtin_bswap32)
300 return __builtin_bswap32(x);
302 return ((x & 0xff) << 24) | ((x & 0xff00u) << 8) | ((x >> 8) & 0xff00u)
303 | ((x >> 24) & 0xff);
307LELY_UTIL_BITS_INLINE uint_least64_t
311 return _byteswap_uint64(x);
312#elif GNUC_PREREQ(4, 3) || __has_builtin(__builtin_bswap64)
313 return __builtin_bswap64(x);
315 return ((x & 0xff) << 56) | ((x & 0xff00u) << 40)
316 | ((x & 0xff0000ul) << 24) | ((x & 0xff000000ul) << 8)
317 | ((x >> 8) & 0xff000000ul) | ((x >> 24) & 0xff0000ul)
318 | ((x >> 40) & 0xff00u) | ((x >> 56) & 0xff);
322LELY_UTIL_BITS_INLINE
int
328#if defined(_MSC_VER) || defined(__GNUC__) || __has_builtin(__builtin_clz)
329LELY_UTIL_BITS_INLINE
int
335 return _BitScanReverse(&Index, x) ? (7 - Index) : 8;
336#elif defined(__GNUC__) || __has_builtin(__builtin_clz)
337 return (x != 0) ? (__builtin_clz(x) - 24) : 8;
342LELY_UTIL_BITS_INLINE
int
348LELY_UTIL_BITS_INLINE
int
351 x &= UINT16_C(0xffff);
354 return _BitScanReverse(&Index, x) ? (15 - Index) : 16;
355#elif defined(__GNUC__) || __has_builtin(__builtin_clz)
356 return (x != 0) ? (__builtin_clz(x) - 16) : 16;
358 return ((x >> 8) != 0) ?
clz8(x >> 8) : (
clz8((uint_least8_t)x) + 8);
362LELY_UTIL_BITS_INLINE
int
368LELY_UTIL_BITS_INLINE
int
371 x &= UINT32_C(0xffffffff);
374 return _BitScanReverse(&Index, x) ? 31 - Index : 32;
375#elif (defined(__GNUC__) || __has_builtin(__builtin_clz)) && __WORDSIZE == 64
376 return (x != 0) ? __builtin_clz(x) : 32;
377#elif defined(__GNUC__) || __has_builtin(__builtin_clzl)
378 return (x != 0) ? __builtin_clzl(x) : 32;
380 return ((x >> 16) != 0) ?
clz16(x >> 16)
381 : (
clz16((uint_least16_t)x) + 16);
385LELY_UTIL_BITS_INLINE
int
391LELY_UTIL_BITS_INLINE
int
394 x &= UINT64_C(0xffffffffffffffff);
395#if defined(_MSC_VER) && _WIN64
397 return _BitScanReverse64(&Index, x) ? (63 - Index) : 64;
398#elif (defined(__GNUC__) || __has_builtin(__builtin_clzl)) && LONG_BIT == 64
399 return (x != 0) ? __builtin_clzl(x) : 64;
400#elif defined(__GNUC__) || __has_builtin(__builtin_clzll)
401 return (x != 0) ? __builtin_clzll(x) : 64;
403 return ((x >> 32) != 0) ?
clz32(x >> 32)
404 : (
clz32((uint_least32_t)x) + 32);
408LELY_UTIL_BITS_INLINE
int
414#if defined(_MSC_VER) || defined(__GNUC__) || __has_builtin(__builtin_ctz)
415LELY_UTIL_BITS_INLINE
int
421 return _BitScanForward(&Index, x) ? Index : 8;
422#elif defined(__GNUC__) || __has_builtin(__builtin_ctz)
423 return (x != 0) ? __builtin_ctz(x) : 8;
428LELY_UTIL_BITS_INLINE
int
434LELY_UTIL_BITS_INLINE
int
437 x &= UINT16_C(0xffff);
440 return _BitScanForward(&Index, x) ? Index : 16;
441#elif defined(__GNUC__) || __has_builtin(__builtin_ctz)
442 return (x != 0) ? __builtin_ctz(x) : 16;
444 return ((x & UINT8_C(0xff)) != 0) ?
ctz8((uint_least8_t)x)
449LELY_UTIL_BITS_INLINE
int
455LELY_UTIL_BITS_INLINE
int
458 x &= UINT32_C(0xffffffff);
461 return _BitScanForward(&Index, x) ? Index : 32;
462#elif (defined(__GNUC__) || __has_builtin(__builtin_ctz)) && __WORDSIZE == 64
463 return (x != 0) ? __builtin_ctz(x) : 32;
464#elif defined(__GNUC__) || __has_builtin(__builtin_ctzl)
465 return (x != 0) ? __builtin_ctzl(x) : 32;
468 return (x & UINT16_C(0xffff))
469 ?
ctz16((uint_least16_t)x) :
ctz16(x >> 16) + 16;
474LELY_UTIL_BITS_INLINE
int
480LELY_UTIL_BITS_INLINE
int
483 x &= UINT64_C(0xffffffffffffffff);
484#if (defined(__GNUC__) || __has_builtin(__builtin_ctzl)) && LONG_BIT == 64
485 return (x != 0) ? __builtin_ctzl(x) : 64;
486#elif defined(__GNUC__) || __has_builtin(__builtin_ctzll)
487 return (x != 0) ? __builtin_ctzll(x) : 64;
490 return (x & UINT32_C(0xffffffff))
491 ?
ctz32((uint_least32_t)x) :
ctz32(x >> 32) + 32;
496#if defined(_MSC_VER) || defined(__GNUC__) || __has_builtin(__builtin_ffs)
497LELY_UTIL_BITS_INLINE
int
503 return _BitScanForward(&Index, x) ? Index + 1 : 0;
504#elif defined(__GNUC__) || __has_builtin(__builtin_ffs)
505 return __builtin_ffs(x);
510LELY_UTIL_BITS_INLINE
int
516LELY_UTIL_BITS_INLINE
int
519 x &= UINT16_C(0xffff);
522 return _BitScanForward(&Index, x) ? Index + 1 : 0;
523#elif defined(__GNUC__) || __has_builtin(__builtin_ffs)
524 return __builtin_ffs(x);
527 return (x != 0) ? ((x & UINT8_C(0xff))
528 ?
ffs8((uint_least8_t)x) :
ffs8(x >> 8) + 8) : 0;
533LELY_UTIL_BITS_INLINE
int
539LELY_UTIL_BITS_INLINE
int
542 x &= UINT32_C(0xffffffff);
545 return _BitScanForward(&Index, x) ? Index + 1 : 0;
546#elif (defined(__GNUC__) || __has_builtin(__builtin_ffs)) && __WORDSIZE == 64
547 return __builtin_ffs(x);
548#elif defined(__GNUC__) || __has_builtin(__builtin_ffsl)
549 return __builtin_ffsl(x);
552 return (x != 0) ? ((x & UINT16_C(0xffff))
553 ?
ffs16((uint_least16_t)x) :
ffs16(x >> 16) + 16) : 0;
558LELY_UTIL_BITS_INLINE
int
564LELY_UTIL_BITS_INLINE
int
567 x &= UINT64_C(0xffffffffffffffff);
568#if defined(_MSC_VER) && _WIN64
570 return _BitScanForward64(&Index, x) ? Index + 1 : 0;
571#elif (defined(__GNUC__) || __has_builtin(__builtin_ffsl)) && LONG_BIT == 64
572 return __builtin_ffsl(x);
573#elif defined(__GNUC__) || __has_builtin(__builtin_ffsll)
574 return __builtin_ffsll(x);
577 return (x != 0) ? ((x & UINT32_C(0xffffffff))
578 ?
ffs32((uint_least32_t)x) :
ffs32(x >> 32) + 32) : 0;
583LELY_UTIL_BITS_INLINE
int
589#if defined(__GNUC__) || __has_builtin(__builtin_parity)
590LELY_UTIL_BITS_INLINE
int
594 return __builtin_parity(x);
598LELY_UTIL_BITS_INLINE
int
601 x &= UINT16_C(0xffff);
602#if defined(__GNUC__) || __has_builtin(__builtin_parity)
603 return __builtin_parity(x);
609LELY_UTIL_BITS_INLINE
int
612 x &= UINT32_C(0xffffffff);
613#if (defined(__GNUC__) || __has_builtin(__builtin_parity)) && __WORDSIZE == 64
614 return __builtin_parity(x);
615#elif defined(__GNUC__) || __has_builtin(__builtin_parityl)
616 return __builtin_parityl(x);
622LELY_UTIL_BITS_INLINE
int
625 x &= UINT64_C(0xffffffffffffffff);
626#if (defined(__GNUC__) || __has_builtin(__builtin_parityl)) && LONG_BIT == 64
627 return __builtin_parityl(x);
628#elif defined(__GNUC__) || __has_builtin(__builtin_parityll)
629 return __builtin_parityll(x);
635#if defined(__GNUC__) || __has_builtin(__builtin_popcount)
636LELY_UTIL_BITS_INLINE
int
640 return __builtin_popcount(x);
644LELY_UTIL_BITS_INLINE
int
647 x &= UINT16_C(0xffff);
648#if defined(__GNUC__) || __has_builtin(__builtin_popcount)
649 return __builtin_popcount(x);
655LELY_UTIL_BITS_INLINE
int
658 x &= UINT32_C(0xffffffff);
659#if (defined(__GNUC__) || __has_builtin(__builtin_popcount)) && __WORDSIZE == 64
660 return __builtin_popcount(x);
661#elif defined(__GNUC__) || __has_builtin(__builtin_popcountl)
662 return __builtin_popcountl(x);
668LELY_UTIL_BITS_INLINE
int
671 x &= UINT64_C(0xffffffffffffffff);
672#if (defined(__GNUC__) || __has_builtin(__builtin_popcountl)) && LONG_BIT == 64
673 return __builtin_popcountl(x);
674#elif defined(__GNUC__) || __has_builtin(__builtin_popcountll)
675 return __builtin_popcountll(x);
681LELY_UTIL_BITS_INLINE uint_least8_t
682rol8(uint_least8_t x,
unsigned int n)
689 return (n != 0) ? (uint_least8_t)((x << n) | (x >> (8U - n))) : x;
693LELY_UTIL_BITS_INLINE uint_least8_t
694ror8(uint_least8_t x,
unsigned int n)
701 return (n != 0) ? (uint_least8_t)((x >> n) | (x << (8U - n))) : x;
705LELY_UTIL_BITS_INLINE uint_least16_t
706rol16(uint_least16_t x,
unsigned int n)
708 x &= UINT16_C(0xffff);
711 return _rotl16(x, n);
713 return (n != 0) ? (uint_least16_t)((x << n) | (x >> (16U - n))) : x;
717LELY_UTIL_BITS_INLINE uint_least16_t
718ror16(uint_least16_t x,
unsigned int n)
720 x &= UINT16_C(0xffff);
723 return _rotr16(x, n);
725 return (n != 0) ? (uint_least16_t)((x >> n) | (x << (16U - n))) : x;
729LELY_UTIL_BITS_INLINE uint_least32_t
730rol32(uint_least32_t x,
unsigned int n)
732 x &= UINT32_C(0xffffffff);
737 return (n != 0) ? (uint_least32_t)((x << n) | (x >> (32U - n))) : x;
741LELY_UTIL_BITS_INLINE uint_least32_t
742ror32(uint_least32_t x,
unsigned int n)
744 x &= UINT32_C(0xffffffff);
749 return (n != 0) ? (uint_least32_t)((x >> n) | (x << (32U - n))) : x;
753LELY_UTIL_BITS_INLINE uint_least64_t
754rol64(uint_least64_t x,
unsigned int n)
756 x &= UINT64_C(0xffffffffffffffff);
759 return _rotl64(x, n);
761 return (n != 0) ? (uint_least64_t)((x << n) | (x >> (64U - n))) : x;
765LELY_UTIL_BITS_INLINE uint_least64_t
766ror64(uint_least64_t x,
unsigned int n)
768 x &= UINT64_C(0xffffffffffffffff);
771 return _rotr64(x, n);
773 return (n != 0) ? (uint_least64_t)((x >> n) | (x << (64U - n))) : x;
int cts64(uint_least64_t x)
Counts the number of trailing set bits in the unsigned 64-bit integer x.
uint_least32_t ror32(uint_least32_t x, unsigned int n)
Rotates the 32-bit unsigned integer x right by n bits.
uint_least16_t ror16(uint_least16_t x, unsigned int n)
Rotates the 16-bit unsigned integer x right by n bits.
uint_least64_t bswap64(uint_least64_t x)
Reverses the byte order of the 64-bit unsigned integer x.
int ffs16(uint_least16_t x)
Returns the index (starting from one) of the first set bit in the unsigned 16-bit integer x,...
int ffz64(uint_least64_t x)
Returns the index (starting from one) of the first zero bit in the unsigned 64-bit integer x,...
int cts8(uint_least8_t x)
Counts the number of trailing set bits in the unsigned 8-bit integer x.
int parity16(uint_least16_t x)
Returns the parity of the unsigned 16-bit integer x.
int ffs8(uint_least8_t x)
Returns the index (starting from one) of the first set bit in the unsigned 8-bit integer x,...
uint_least64_t ror64(uint_least64_t x, unsigned int n)
Rotates the 64-bit unsigned integer x right by n bits.
int ctz32(uint_least32_t x)
Counts the number of trailing zero bits in the unsigned 32-bit integer x.
int cls16(uint_least16_t x)
Counts the number of leading set bits in the unsigned 16-bit integer x.
int ffs64(uint_least64_t x)
Returns the index (starting from one) of the first set bit in the unsigned 64-bit integer x,...
uint_least8_t ror8(uint_least8_t x, unsigned int n)
Rotates the 8-bit unsigned integer x right by n bits.
int cts32(uint_least32_t x)
Counts the number of trailing set bits in the unsigned 32-bit integer x.
int clz8(uint_least8_t x)
Counts the number of leading zero bits in the unsigned 8-bit integer x.
int ctz64(uint_least64_t x)
Counts the number of trailing zero bits in the unsigned 64-bit integer x.
int popcount32(uint_least32_t x)
Returns the population count (the number of set bits) in the unsigned 32-bit integer x.
int cts16(uint_least16_t x)
Counts the number of trailing set bits in the unsigned 16-bit integer x.
int cls64(uint_least64_t x)
Counts the number of leading set bits in the unsigned 64-bit integer x.
uint_least16_t bswap16(uint_least16_t x)
Reverses the byte order of the 16-bit unsigned integer x.
int parity8(uint_least8_t x)
Returns the parity of the unsigned 8-bit integer x.
uint_least32_t rol32(uint_least32_t x, unsigned int n)
Rotates the 32-bit unsigned integer x left by n bits.
uint_least8_t rol8(uint_least8_t x, unsigned int n)
Rotates the 8-bit unsigned integer x left by n bits.
int clz64(uint_least64_t x)
Counts the number of leading zero bits in the unsigned 64-bit integer x.
int ffz8(uint_least8_t x)
Returns the index (starting from one) of the first zero bit in the unsigned 8-bit integer x,...
int ffs32(uint_least32_t x)
Returns the index (starting from one) of the first set bit in the unsigned 32-bit integer x,...
int clz32(uint_least32_t x)
Counts the number of leading zero bits in the unsigned 32-bit integer x.
int parity32(uint_least32_t x)
Returns the parity of the unsigned 32-bit integer x.
int clz16(uint_least16_t x)
Counts the number of leading zero bits in the unsigned 16-bit integer x.
int ffz32(uint_least32_t x)
Returns the index (starting from one) of the first zero bit in the unsigned 32-bit integer x,...
int ffz16(uint_least16_t x)
Returns the index (starting from one) of the first zero bit in the unsigned 16-bit integer x,...
int cls32(uint_least32_t x)
Counts the number of leading set bits in the unsigned 32-bit integer x.
int popcount64(uint_least64_t x)
Returns the population count (the number of set bits) in the unsigned 64-bit integer x.
uint_least16_t rol16(uint_least16_t x, unsigned int n)
Rotates the 16-bit unsigned integer x left by n bits.
int parity64(uint_least64_t x)
Returns the parity of the unsigned 64-bit integer x.
uint_least64_t rol64(uint_least64_t x, unsigned int n)
Rotates the 64-bit unsigned integer x left by n bits.
int ctz16(uint_least16_t x)
Counts the number of trailing zero bits in the unsigned 16-bit integer x.
int ctz8(uint_least8_t x)
Counts the number of trailing zero bits in the unsigned 8-bit integer x.
int cls8(uint_least8_t x)
Counts the number of leading set bits in the unsigned 8-bit integer x.
uint_least32_t bswap32(uint_least32_t x)
Reverses the byte order of the 32-bit unsigned integer x.
int popcount16(uint_least16_t x)
Returns the population count (the number of set bits) in the unsigned 16-bit integer x.
int popcount8(uint_least8_t x)
Returns the population count (the number of set bits) in the unsigned 8-bit integer x.
This header file is part of the Lely libraries; it contains the compiler feature definitions.
This header file is part of the C11 and POSIX compatibility library; it includes <stdint....
This header file is part of the C11 and POSIX compatibility library; it includes <stdlib....