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 } 62 63 BIT_UTIL_INLINE uint64_t 64 pow2_ceil_u64(uint64_t x) { 65 x--; 66 x |= x >> 1; 67 x |= x >> 2; 68 x |= x >> 4; 69 x |= x >> 8; 70 x |= x >> 16; 71 x |= x >> 32; 72 x++; 73 return x; 74 } 75 76 BIT_UTIL_INLINE uint32_t 77 pow2_ceil_u32(uint32_t x) { 78 x--; 79 x |= x >> 1; 80 x |= x >> 2; 81 x |= x >> 4; 82 x |= x >> 8; 83 x |= x >> 16; 84 x++; 85 return x; 86 } 87 88 /* Compute the smallest power of 2 that is >= x. */ 89 BIT_UTIL_INLINE size_t 90 pow2_ceil_zu(size_t x) { 91 #if (LG_SIZEOF_PTR == 3) 92 return pow2_ceil_u64(x); 93 #else 94 return pow2_ceil_u32(x); 95 #endif 96 } 97 98 #if (defined(__i386__) || defined(__amd64__) || defined(__x86_64__)) 99 BIT_UTIL_INLINE unsigned 100 lg_floor(size_t x) { 101 size_t ret; 102 assert(x != 0); 103 104 asm ("bsr %1, %0" 105 : "=r"(ret) // Outputs. 106 : "r"(x) // Inputs. 107 ); 108 assert(ret < UINT_MAX); 109 return (unsigned)ret; 110 } 111 #elif (defined(_MSC_VER)) 112 BIT_UTIL_INLINE unsigned 113 lg_floor(size_t x) { 114 unsigned long ret; 115 116 assert(x != 0); 117 118 #if (LG_SIZEOF_PTR == 3) 119 _BitScanReverse64(&ret, x); 120 #elif (LG_SIZEOF_PTR == 2) 121 _BitScanReverse(&ret, x); 122 #else 123 # error "Unsupported type size for lg_floor()" 124 #endif 125 assert(ret < UINT_MAX); 126 return (unsigned)ret; 127 } 128 #elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ)) 129 BIT_UTIL_INLINE unsigned 130 lg_floor(size_t x) { 131 assert(x != 0); 132 133 #if (LG_SIZEOF_PTR == LG_SIZEOF_INT) 134 return ((8 << LG_SIZEOF_PTR) - 1) - __builtin_clz(x); 135 #elif (LG_SIZEOF_PTR == LG_SIZEOF_LONG) 136 return ((8 << LG_SIZEOF_PTR) - 1) - __builtin_clzl(x); 137 #else 138 # error "Unsupported type size for lg_floor()" 139 #endif 140 } 141 #else 142 BIT_UTIL_INLINE unsigned 143 lg_floor(size_t x) { 144 assert(x != 0); 145 146 x |= (x >> 1); 147 x |= (x >> 2); 148 x |= (x >> 4); 149 x |= (x >> 8); 150 x |= (x >> 16); 151 #if (LG_SIZEOF_PTR == 3) 152 x |= (x >> 32); 153 #endif 154 if (x == SIZE_T_MAX) { 155 return (8 << LG_SIZEOF_PTR) - 1; 156 } 157 x++; 158 return ffs_zu(x) - 2; 159 } 160 #endif 161 162 #undef BIT_UTIL_INLINE 163 164 #endif /* JEMALLOC_INTERNAL_BIT_UTIL_H */ 165