Ruby 4.1.0dev (2026-11-16 revision 67814cf9b0f3a4bad6f7369b0c8e6fc69220de64)
bit.h
1#ifndef PRISM_INTERNAL_BIT_H
2#define PRISM_INTERNAL_BIT_H
3
5
6/*
7 * Count trailing zero bits in a 64-bit value, and find the index of the
8 * highest set bit in one (the result of the x86 bsr instruction). pm_ctzll is
9 * used by SWAR identifier scanning to find the first non-matching byte in a
10 * word, and pm_bsrll by integer parsing and printing to find the largest power
11 * of two below a count.
12 *
13 * Precondition: v must be nonzero. The results are undefined when v == 0
14 * (matching the behavior of __builtin_ctzll, __builtin_clzll,
15 * _BitScanForward64, and _BitScanReverse64).
16 */
17#if defined(__GNUC__) || defined(__clang__)
18#define pm_bsrll(v) (63 - (unsigned) __builtin_clzll(v))
19#define pm_ctzll(v) ((unsigned) __builtin_ctzll(v))
20#elif defined(_MSC_VER) && defined(_WIN64)
21#include <intrin.h>
22#include <stdint.h>
23
24static PRISM_INLINE unsigned
25pm_bsrll(uint64_t v) {
26 unsigned long index;
27 _BitScanReverse64(&index, v);
28 return (unsigned) index;
29}
30
31static PRISM_INLINE unsigned
32pm_ctzll(uint64_t v) {
33 unsigned long index;
34 _BitScanForward64(&index, v);
35 return (unsigned) index;
36}
37#else
38#include <stdint.h>
39
40static PRISM_INLINE unsigned
41pm_bsrll(uint64_t v) {
42 unsigned c = 0;
43 if (v & 0xFFFFFFFF00000000ULL) { c += 32; v >>= 32; }
44 if (v & 0x00000000FFFF0000ULL) { c += 16; v >>= 16; }
45 if (v & 0x000000000000FF00ULL) { c += 8; v >>= 8; }
46 if (v & 0x00000000000000F0ULL) { c += 4; v >>= 4; }
47 if (v & 0x000000000000000CULL) { c += 2; v >>= 2; }
48 if (v & 0x0000000000000002ULL) { c += 1; }
49 return c;
50}
51
52static PRISM_INLINE unsigned
53pm_ctzll(uint64_t v) {
54 unsigned c = 0;
55 v &= (uint64_t) (-(int64_t) v);
56 if (!(v & 0x00000000FFFFFFFFULL)) c += 32;
57 if (!(v & 0x0000FFFF0000FFFFULL)) c += 16;
58 if (!(v & 0x00FF00FF00FF00FFULL)) c += 8;
59 if (!(v & 0x0F0F0F0F0F0F0F0FULL)) c += 4;
60 if (!(v & 0x3333333333333333ULL)) c += 2;
61 if (!(v & 0x5555555555555555ULL)) c += 1;
62 return c;
63}
64#endif
65
66#endif
#define PRISM_INLINE
Old Visual Studio versions do not support the inline keyword, so we need to define it to be __inline.
Definition inline.h:12