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 16 ffs_llu(unsigned long long bitmap) { 17 return JEMALLOC_INTERNAL_FFSLL(bitmap); 18 } 19 20 BIT_UTIL_INLINE unsigned 21 ffs_lu(unsigned long bitmap) { 22 return JEMALLOC_INTERNAL_FFSL(bitmap); 23 } 24 25 BIT_UTIL_INLINE unsigned 26 ffs_u(unsigned bitmap) { 27 return JEMALLOC_INTERNAL_FFS(bitmap); 28 } 29 30 BIT_UTIL_INLINE unsigned 31 ffs_zu(size_t bitmap) { 32 #if LG_SIZEOF_PTR == LG_SIZEOF_INT 33 return ffs_u(bitmap); 34 #elif LG_SIZEOF_PTR == LG_SIZEOF_LONG 35 return ffs_lu(bitmap); 36 #elif LG_SIZEOF_PTR == LG_SIZEOF_LONG_LONG 37 return ffs_llu(bitmap); 38 #else 39 #error No implementation for size_t ffs() 40 #endif 41 } 42 43 BIT_UTIL_INLINE unsigned 44 ffs_u64(uint64_t bitmap) { 45 #if LG_SIZEOF_LONG == 3 46 return ffs_lu(bitmap); 47 #elif LG_SIZEOF_LONG_LONG == 3 48 return ffs_llu(bitmap); 49 #else 50 #error No implementation for 64-bit ffs() 51 #endif 52 } 53 54 BIT_UTIL_INLINE unsigned 55 ffs_u32(uint32_t bitmap) { 56 #if LG_SIZEOF_INT == 2 57 return ffs_u(bitmap); 58 #else 59 #error No implementation for 32-bit ffs() 60 #endif 61 return ffs_u(bitmap); 62 } 63 64 BIT_UTIL_INLINE uint64_t 65 pow2_ceil_u64(uint64_t x) { 66 x--; 67 x |= x >> 1; 68 x |= x >> 2; 69 x |= x >> 4; 70 x |= x >> 8; 71 x |= x >> 16; 72 x |= x >> 32; 73 x++; 74 return x; 75 } 76 77 BIT_UTIL_INLINE uint32_t 78 pow2_ceil_u32(uint32_t x) { 79 x--; 80 x |= x >> 1; 81 x |= x >> 2; 82 x |= x >> 4; 83 x |= x >> 8; 84 x |= x >> 16; 85 x++; 86 return x; 87 } 88 89 /* Compute the smallest power of 2 that is >= x. */ 90 BIT_UTIL_INLINE size_t 91 pow2_ceil_zu(size_t x) { 92 #if (LG_SIZEOF_PTR == 3) 93 return pow2_ceil_u64(x); 94 #else 95 return pow2_ceil_u32(x); 96 #endif 97 } 98 99 #if (defined(__i386__) || defined(__amd64__) || defined(__x86_64__)) 100 BIT_UTIL_INLINE unsigned 101 lg_floor(size_t x) { 102 size_t ret; 103 assert(x != 0); 104 105 asm ("bsr %1, %0" 106 : "=r"(ret) // Outputs. 107 : "r"(x) // Inputs. 108 ); 109 assert(ret < UINT_MAX); 110 return (unsigned)ret; 111 } 112 #elif (defined(_MSC_VER)) 113 BIT_UTIL_INLINE unsigned 114 lg_floor(size_t x) { 115 unsigned long ret; 116 117 assert(x != 0); 118 119 #if (LG_SIZEOF_PTR == 3) 120 _BitScanReverse64(&ret, x); 121 #elif (LG_SIZEOF_PTR == 2) 122 _BitScanReverse(&ret, x); 123 #else 124 # error "Unsupported type size for lg_floor()" 125 #endif 126 assert(ret < UINT_MAX); 127 return (unsigned)ret; 128 } 129 #elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ)) 130 BIT_UTIL_INLINE unsigned 131 lg_floor(size_t x) { 132 assert(x != 0); 133 134 #if (LG_SIZEOF_PTR == LG_SIZEOF_INT) 135 return ((8 << LG_SIZEOF_PTR) - 1) - __builtin_clz(x); 136 #elif (LG_SIZEOF_PTR == LG_SIZEOF_LONG) 137 return ((8 << LG_SIZEOF_PTR) - 1) - __builtin_clzl(x); 138 #else 139 # error "Unsupported type size for lg_floor()" 140 #endif 141 } 142 #else 143 BIT_UTIL_INLINE unsigned 144 lg_floor(size_t x) { 145 assert(x != 0); 146 147 x |= (x >> 1); 148 x |= (x >> 2); 149 x |= (x >> 4); 150 x |= (x >> 8); 151 x |= (x >> 16); 152 #if (LG_SIZEOF_PTR == 3) 153 x |= (x >> 32); 154 #endif 155 if (x == SIZE_T_MAX) { 156 return (8 << LG_SIZEOF_PTR) - 1; 157 } 158 x++; 159 return ffs_zu(x) - 2; 160 } 161 #endif 162 163 #undef BIT_UTIL_INLINE 164 165 #endif /* JEMALLOC_INTERNAL_BIT_UTIL_H */ 166