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 15 BIT_UTIL_INLINE unsigned ffs_llu(unsigned long long bitmap)16ffs_llu(unsigned long long bitmap) { 17 return JEMALLOC_INTERNAL_FFSLL(bitmap); 18 } 19 20 BIT_UTIL_INLINE unsigned ffs_lu(unsigned long bitmap)21ffs_lu(unsigned long bitmap) { 22 return JEMALLOC_INTERNAL_FFSL(bitmap); 23 } 24 25 BIT_UTIL_INLINE unsigned ffs_u(unsigned bitmap)26ffs_u(unsigned bitmap) { 27 return JEMALLOC_INTERNAL_FFS(bitmap); 28 } 29 30 #ifdef JEMALLOC_INTERNAL_POPCOUNTL 31 BIT_UTIL_INLINE unsigned popcount_lu(unsigned long bitmap)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 42 BIT_UTIL_INLINE size_t cfs_lu(unsigned long * bitmap)43cfs_lu(unsigned long* bitmap) { 44 size_t bit = ffs_lu(*bitmap) - 1; 45 *bitmap ^= ZU(1) << bit; 46 return bit; 47 } 48 49 BIT_UTIL_INLINE unsigned ffs_zu(size_t bitmap)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 62 BIT_UTIL_INLINE unsigned ffs_u64(uint64_t bitmap)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 73 BIT_UTIL_INLINE unsigned ffs_u32(uint32_t bitmap)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 83 BIT_UTIL_INLINE uint64_t pow2_ceil_u64(uint64_t x)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 113 BIT_UTIL_INLINE uint32_t pow2_ceil_u32(uint32_t x)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. */ 143 BIT_UTIL_INLINE size_t pow2_ceil_zu(size_t x)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__)) 153 BIT_UTIL_INLINE unsigned lg_floor(size_t x)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)) 166 BIT_UTIL_INLINE unsigned lg_floor(size_t x)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)) 183 BIT_UTIL_INLINE unsigned lg_floor(size_t x)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 196 BIT_UTIL_INLINE unsigned lg_floor(size_t x)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 216 BIT_UTIL_INLINE unsigned lg_ceil(size_t x)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