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