1 #ifndef JEMALLOC_INTERNAL_BIT_UTIL_H
2 #define JEMALLOC_INTERNAL_BIT_UTIL_H
4 #include "jemalloc/internal/assert.h"
6 #define BIT_UTIL_INLINE static inline
9 #if !defined(JEMALLOC_INTERNAL_FFSLL) || !defined(JEMALLOC_INTERNAL_FFSL) \
10 || !defined(JEMALLOC_INTERNAL_FFS)
11 # error JEMALLOC_INTERNAL_FFS{,L,LL} should have been defined by configure
15 BIT_UTIL_INLINE unsigned
16 ffs_llu(unsigned long long bitmap) {
17 return JEMALLOC_INTERNAL_FFSLL(bitmap);
20 BIT_UTIL_INLINE unsigned
21 ffs_lu(unsigned long bitmap) {
22 return JEMALLOC_INTERNAL_FFSL(bitmap);
25 BIT_UTIL_INLINE unsigned
26 ffs_u(unsigned bitmap) {
27 return JEMALLOC_INTERNAL_FFS(bitmap);
30 #ifdef JEMALLOC_INTERNAL_POPCOUNTL
31 BIT_UTIL_INLINE unsigned
32 popcount_lu(unsigned long bitmap) {
33 return JEMALLOC_INTERNAL_POPCOUNTL(bitmap);
38 * Clears first unset bit in bitmap, and returns
39 * place of bit. bitmap *must not* be 0.
42 BIT_UTIL_INLINE size_t
43 cfs_lu(unsigned long* bitmap) {
44 size_t bit = ffs_lu(*bitmap) - 1;
45 *bitmap ^= ZU(1) << bit;
49 BIT_UTIL_INLINE unsigned
50 ffs_zu(size_t bitmap) {
51 #if LG_SIZEOF_PTR == LG_SIZEOF_INT
53 #elif LG_SIZEOF_PTR == LG_SIZEOF_LONG
54 return ffs_lu(bitmap);
55 #elif LG_SIZEOF_PTR == LG_SIZEOF_LONG_LONG
56 return ffs_llu(bitmap);
58 #error No implementation for size_t ffs()
62 BIT_UTIL_INLINE unsigned
63 ffs_u64(uint64_t bitmap) {
64 #if LG_SIZEOF_LONG == 3
65 return ffs_lu(bitmap);
66 #elif LG_SIZEOF_LONG_LONG == 3
67 return ffs_llu(bitmap);
69 #error No implementation for 64-bit ffs()
73 BIT_UTIL_INLINE unsigned
74 ffs_u32(uint32_t bitmap) {
75 #if LG_SIZEOF_INT == 2
78 #error No implementation for 32-bit ffs()
83 BIT_UTIL_INLINE uint64_t
84 pow2_ceil_u64(uint64_t x) {
85 #if (defined(__amd64__) || defined(__x86_64__) || defined(JEMALLOC_HAVE_BUILTIN_CLZ))
86 if(unlikely(x <= 1)) {
90 #if (defined(__amd64__) || defined(__x86_64__))
92 : "=r"(msb_on_index) // Outputs.
95 #elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ))
96 msb_on_index = (63 ^ __builtin_clzll(x - 1));
98 assert(msb_on_index < 63);
99 return 1ULL << (msb_on_index + 1);
113 BIT_UTIL_INLINE uint32_t
114 pow2_ceil_u32(uint32_t x) {
115 #if ((defined(__i386__) || defined(JEMALLOC_HAVE_BUILTIN_CLZ)) && (!defined(__s390__)))
116 if(unlikely(x <= 1)) {
120 #if (defined(__i386__))
122 : "=r"(msb_on_index) // Outputs.
123 : "r"(x-1) // Inputs.
125 #elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ))
126 msb_on_index = (31 ^ __builtin_clz(x - 1));
128 assert(msb_on_index < 31);
129 return 1U << (msb_on_index + 1);
142 /* Compute the smallest power of 2 that is >= x. */
143 BIT_UTIL_INLINE size_t
144 pow2_ceil_zu(size_t x) {
145 #if (LG_SIZEOF_PTR == 3)
146 return pow2_ceil_u64(x);
148 return pow2_ceil_u32(x);
152 #if (defined(__i386__) || defined(__amd64__) || defined(__x86_64__))
153 BIT_UTIL_INLINE unsigned
159 : "=r"(ret) // Outputs.
162 assert(ret < UINT_MAX);
163 return (unsigned)ret;
165 #elif (defined(_MSC_VER))
166 BIT_UTIL_INLINE unsigned
172 #if (LG_SIZEOF_PTR == 3)
173 _BitScanReverse64(&ret, x);
174 #elif (LG_SIZEOF_PTR == 2)
175 _BitScanReverse(&ret, x);
177 # error "Unsupported type size for lg_floor()"
179 assert(ret < UINT_MAX);
180 return (unsigned)ret;
182 #elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ))
183 BIT_UTIL_INLINE unsigned
187 #if (LG_SIZEOF_PTR == LG_SIZEOF_INT)
188 return ((8 << LG_SIZEOF_PTR) - 1) - __builtin_clz(x);
189 #elif (LG_SIZEOF_PTR == LG_SIZEOF_LONG)
190 return ((8 << LG_SIZEOF_PTR) - 1) - __builtin_clzl(x);
192 # error "Unsupported type size for lg_floor()"
196 BIT_UTIL_INLINE unsigned
205 #if (LG_SIZEOF_PTR == 3)
208 if (x == SIZE_T_MAX) {
209 return (8 << LG_SIZEOF_PTR) - 1;
212 return ffs_zu(x) - 2;
216 BIT_UTIL_INLINE unsigned
218 return lg_floor(x) + ((x & (x - 1)) == 0 ? 0 : 1);
221 #undef BIT_UTIL_INLINE
223 /* A compile-time version of lg_floor and lg_ceil. */
224 #define LG_FLOOR_1(x) 0
225 #define LG_FLOOR_2(x) (x < (1ULL << 1) ? LG_FLOOR_1(x) : 1 + LG_FLOOR_1(x >> 1))
226 #define LG_FLOOR_4(x) (x < (1ULL << 2) ? LG_FLOOR_2(x) : 2 + LG_FLOOR_2(x >> 2))
227 #define LG_FLOOR_8(x) (x < (1ULL << 4) ? LG_FLOOR_4(x) : 4 + LG_FLOOR_4(x >> 4))
228 #define LG_FLOOR_16(x) (x < (1ULL << 8) ? LG_FLOOR_8(x) : 8 + LG_FLOOR_8(x >> 8))
229 #define LG_FLOOR_32(x) (x < (1ULL << 16) ? LG_FLOOR_16(x) : 16 + LG_FLOOR_16(x >> 16))
230 #define LG_FLOOR_64(x) (x < (1ULL << 32) ? LG_FLOOR_32(x) : 32 + LG_FLOOR_32(x >> 32))
231 #if LG_SIZEOF_PTR == 2
232 # define LG_FLOOR(x) LG_FLOOR_32((x))
234 # define LG_FLOOR(x) LG_FLOOR_64((x))
237 #define LG_CEIL(x) (LG_FLOOR(x) + (((x) & ((x) - 1)) == 0 ? 0 : 1))
239 #endif /* JEMALLOC_INTERNAL_BIT_UTIL_H */