1#ifndef JEMALLOC_INTERNAL_BIT_UTIL_H
2#define JEMALLOC_INTERNAL_BIT_UTIL_H
3
4#include "jemalloc/internal/assert.h"
5
6#define BIT_UTIL_INLINE static inline
7
8/* Sanity check. */
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
12#endif
13
14
15BIT_UTIL_INLINE unsigned
16ffs_llu(unsigned long long bitmap) {
17	return JEMALLOC_INTERNAL_FFSLL(bitmap);
18}
19
20BIT_UTIL_INLINE unsigned
21ffs_lu(unsigned long bitmap) {
22	return JEMALLOC_INTERNAL_FFSL(bitmap);
23}
24
25BIT_UTIL_INLINE unsigned
26ffs_u(unsigned bitmap) {
27	return JEMALLOC_INTERNAL_FFS(bitmap);
28}
29
30#ifdef JEMALLOC_INTERNAL_POPCOUNTL
31BIT_UTIL_INLINE unsigned
32popcount_lu(unsigned long bitmap) {
33  return JEMALLOC_INTERNAL_POPCOUNTL(bitmap);
34}
35#endif
36
37/*
38 * Clears first unset bit in bitmap, and returns
39 * place of bit.  bitmap *must not* be 0.
40 */
41
42BIT_UTIL_INLINE size_t
43cfs_lu(unsigned long* bitmap) {
44	size_t bit = ffs_lu(*bitmap) - 1;
45	*bitmap ^= ZU(1) << bit;
46	return bit;
47}
48
49BIT_UTIL_INLINE unsigned
50ffs_zu(size_t bitmap) {
51#if LG_SIZEOF_PTR == LG_SIZEOF_INT
52	return ffs_u(bitmap);
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);
57#else
58#error No implementation for size_t ffs()
59#endif
60}
61
62BIT_UTIL_INLINE unsigned
63ffs_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);
68#else
69#error No implementation for 64-bit ffs()
70#endif
71}
72
73BIT_UTIL_INLINE unsigned
74ffs_u32(uint32_t bitmap) {
75#if LG_SIZEOF_INT == 2
76	return ffs_u(bitmap);
77#else
78#error No implementation for 32-bit ffs()
79#endif
80	return ffs_u(bitmap);
81}
82
83BIT_UTIL_INLINE uint64_t
84pow2_ceil_u64(uint64_t x) {
85#if (defined(__amd64__) || defined(__x86_64__) || defined(JEMALLOC_HAVE_BUILTIN_CLZ))
86	if(unlikely(x <= 1)) {
87		return x;
88	}
89	size_t msb_on_index;
90#if (defined(__amd64__) || defined(__x86_64__))
91	asm ("bsrq %1, %0"
92			: "=r"(msb_on_index) // Outputs.
93			: "r"(x-1)           // Inputs.
94		);
95#elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ))
96	msb_on_index = (63 ^ __builtin_clzll(x - 1));
97#endif
98	assert(msb_on_index < 63);
99	return 1ULL << (msb_on_index + 1);
100#else
101	x--;
102	x |= x >> 1;
103	x |= x >> 2;
104	x |= x >> 4;
105	x |= x >> 8;
106	x |= x >> 16;
107	x |= x >> 32;
108	x++;
109	return x;
110#endif
111}
112
113BIT_UTIL_INLINE uint32_t
114pow2_ceil_u32(uint32_t x) {
115#if ((defined(__i386__) || defined(JEMALLOC_HAVE_BUILTIN_CLZ)) && (!defined(__s390__)))
116	if(unlikely(x <= 1)) {
117		return x;
118	}
119	size_t msb_on_index;
120#if (defined(__i386__))
121	asm ("bsr %1, %0"
122			: "=r"(msb_on_index) // Outputs.
123			: "r"(x-1)           // Inputs.
124		);
125#elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ))
126	msb_on_index = (31 ^ __builtin_clz(x - 1));
127#endif
128	assert(msb_on_index < 31);
129	return 1U << (msb_on_index + 1);
130#else
131	x--;
132	x |= x >> 1;
133	x |= x >> 2;
134	x |= x >> 4;
135	x |= x >> 8;
136	x |= x >> 16;
137	x++;
138	return x;
139#endif
140}
141
142/* Compute the smallest power of 2 that is >= x. */
143BIT_UTIL_INLINE size_t
144pow2_ceil_zu(size_t x) {
145#if (LG_SIZEOF_PTR == 3)
146	return pow2_ceil_u64(x);
147#else
148	return pow2_ceil_u32(x);
149#endif
150}
151
152#if (defined(__i386__) || defined(__amd64__) || defined(__x86_64__))
153BIT_UTIL_INLINE unsigned
154lg_floor(size_t x) {
155	size_t ret;
156	assert(x != 0);
157
158	asm ("bsr %1, %0"
159	    : "=r"(ret) // Outputs.
160	    : "r"(x)    // Inputs.
161	    );
162	assert(ret < UINT_MAX);
163	return (unsigned)ret;
164}
165#elif (defined(_MSC_VER))
166BIT_UTIL_INLINE unsigned
167lg_floor(size_t x) {
168	unsigned long ret;
169
170	assert(x != 0);
171
172#if (LG_SIZEOF_PTR == 3)
173	_BitScanReverse64(&ret, x);
174#elif (LG_SIZEOF_PTR == 2)
175	_BitScanReverse(&ret, x);
176#else
177#  error "Unsupported type size for lg_floor()"
178#endif
179	assert(ret < UINT_MAX);
180	return (unsigned)ret;
181}
182#elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ))
183BIT_UTIL_INLINE unsigned
184lg_floor(size_t x) {
185	assert(x != 0);
186
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);
191#else
192#  error "Unsupported type size for lg_floor()"
193#endif
194}
195#else
196BIT_UTIL_INLINE unsigned
197lg_floor(size_t x) {
198	assert(x != 0);
199
200	x |= (x >> 1);
201	x |= (x >> 2);
202	x |= (x >> 4);
203	x |= (x >> 8);
204	x |= (x >> 16);
205#if (LG_SIZEOF_PTR == 3)
206	x |= (x >> 32);
207#endif
208	if (x == SIZE_T_MAX) {
209		return (8 << LG_SIZEOF_PTR) - 1;
210	}
211	x++;
212	return ffs_zu(x) - 2;
213}
214#endif
215
216BIT_UTIL_INLINE unsigned
217lg_ceil(size_t x) {
218	return lg_floor(x) + ((x & (x - 1)) == 0 ? 0 : 1);
219}
220
221#undef BIT_UTIL_INLINE
222
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))
233#else
234#  define LG_FLOOR(x) LG_FLOOR_64((x))
235#endif
236
237#define LG_CEIL(x) (LG_FLOOR(x) + (((x) & ((x) - 1)) == 0 ? 0 : 1))
238
239#endif /* JEMALLOC_INTERNAL_BIT_UTIL_H */
240