3 inline cell log2(cell x) {
5 #if defined(FACTOR_X86)
7 _BitScanReverse((unsigned long*)&n, x);
9 asm("bsr %1, %0;" : "=r"(n) : "r"(x));
12 #elif defined(FACTOR_AMD64)
15 _BitScanReverse64((unsigned long*)&n, x);
17 asm("bsr %1, %0;" : "=r"(n) : "r"(x));
20 #elif defined(FACTOR_ARM)
22 _BitScanReverse((unsigned long*)&n, x);
24 n = (31 - __builtin_clz(x));
27 #elif defined(FACTOR_ARM64)
30 _BitScanReverse64((unsigned long*)&n, x);
32 n = (63 - __builtin_clzll(x));
35 #elif defined(FACTOR_PPC32)
37 n = (31 - __builtin_clz(x));
39 #error Unsupported compiler
42 #elif defined(FACTOR_PPC64)
44 n = (63 - __builtin_clzll(x));
46 #error Unsupported compiler
50 #error Unsupported CPU
55 inline cell rightmost_clear_bit(cell x) { return log2(~x & (x + 1)); }
57 inline cell rightmost_set_bit(cell x) { return log2(x & (~x + 1)); }
59 inline cell popcount(cell x) {
62 return __builtin_popcountll(x);
64 return __builtin_popcount(x);
68 uint64_t k1 = 0x5555555555555555ll;
69 uint64_t k2 = 0x3333333333333333ll;
70 uint64_t k4 = 0x0f0f0f0f0f0f0f0fll;
71 uint64_t kf = 0x0101010101010101ll;
74 uint32_t k1 = 0x55555555;
75 uint32_t k2 = 0x33333333;
76 uint32_t k4 = 0xf0f0f0f;
77 uint32_t kf = 0x1010101;
81 x = x - ((x >> 1) & k1); // put count of each 2 bits into those 2 bits
82 x = (x & k2) + ((x >> 2) & k2); // put count of each 4 bits into those 4 bits
83 x = (x + (x >> 4)) & k4; // put count of each 8 bits into those 8 bits
84 x = (x * kf) >> ks; // returns 8 most significant bits of x + (x<<8) +
85 // (x<<16) + (x<<24) + ...
91 inline bool bitmap_p(uint8_t* bitmap, cell index) {
92 cell byte = index >> 3;
94 return (bitmap[byte] & (1 << bit)) != 0;