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