1 #ifndef _LINUX_BITOPS_H 2 #define _LINUX_BITOPS_H 3 4 #include <ntifs.h> 5 #include <linux/types.h> 6 7 #ifdef __KERNEL__ 8 #define BIT(nr) (1 << (nr)) 9 #define BIT_MASK(nr) (1 << ((nr) % BITS_PER_LONG)) 10 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 11 #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_LONG) 12 #define BITS_PER_BYTE 8 13 #endif 14 15 /* 16 * Include this here because some architectures need generic_ffs/fls in 17 * scope 18 */ 19 20 /** 21 * find_first_zero_bit - find the first zero bit in a memory region 22 * @addr: The address to start the search at 23 * @size: The maximum size to search 24 * 25 * Returns the bit number of the first zero bit, not the number of the byte 26 * containing a bit. 27 */ 28 #define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0) 29 30 /** 31 * find_next_zero_bit - find the first zero bit in a memory region 32 * @addr: The address to base the search on 33 * @offset: The bit number to start searching at 34 * @size: The maximum size to search 35 */ 36 int find_next_zero_bit(const unsigned long *addr, int size, int offset); 37 38 /** 39 * __ffs - find first bit in word. 40 * @word: The word to search 41 * 42 * Undefined if no bit exists, so code should check against 0 first. 43 */ 44 static inline unsigned long __ffs(unsigned long word) 45 { 46 int num = 0; 47 48 #if BITS_PER_LONG == 64 49 if ((word & 0xffffffff) == 0) { 50 num += 32; 51 word >>= 32; 52 } 53 #endif 54 if ((word & 0xffff) == 0) { 55 num += 16; 56 word >>= 16; 57 } 58 if ((word & 0xff) == 0) { 59 num += 8; 60 word >>= 8; 61 } 62 if ((word & 0xf) == 0) { 63 num += 4; 64 word >>= 4; 65 } 66 if ((word & 0x3) == 0) { 67 num += 2; 68 word >>= 2; 69 } 70 if ((word & 0x1) == 0) 71 num += 1; 72 return num; 73 } 74 75 /** 76 * find_first_bit - find the first set bit in a memory region 77 * @addr: The address to start the search at 78 * @size: The maximum size to search 79 * 80 * Returns the bit number of the first set bit, not the number of the byte 81 * containing a bit. 82 */ 83 static inline unsigned find_first_bit(const unsigned long *addr, unsigned size) 84 { 85 unsigned x = 0; 86 87 while (x < size) { 88 unsigned long val = *addr++; 89 if (val) 90 return __ffs(val) + x; 91 x += (sizeof(*addr)<<3); 92 } 93 return x; 94 } 95 96 /** 97 * find_next_bit - find the next set bit in a memory region 98 * @addr: The address to base the search on 99 * @offset: The bitnumber to start searching at 100 * @size: The maximum size to search 101 */ 102 103 /* 104 * ffz - find first zero in word. 105 * @word: The word to search 106 * 107 * Undefined if no zero exists, so code should check against ~0UL first. 108 */ 109 #define ffz(x) __ffs(~(x)) 110 111 112 /** 113 * ffs - find first bit set 114 * @x: the word to search 115 * 116 * This is defined the same way as 117 * the libc and compiler builtin ffs routines, therefore 118 * differs in spirit from the above ffz (man ffs). 119 */ 120 static inline int ffs(int x) 121 { 122 int r = 1; 123 124 if (!x) 125 return 0; 126 if (!(x & 0xffff)) { 127 x >>= 16; 128 r += 16; 129 } 130 if (!(x & 0xff)) { 131 x >>= 8; 132 r += 8; 133 } 134 if (!(x & 0xf)) { 135 x >>= 4; 136 r += 4; 137 } 138 if (!(x & 3)) { 139 x >>= 2; 140 r += 2; 141 } 142 if (!(x & 1)) { 143 x >>= 1; 144 r += 1; 145 } 146 return r; 147 } 148 149 /** 150 * fls - find last (most-significant) bit set 151 * @x: the word to search 152 * 153 * This is defined the same way as ffs. 154 * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. 155 */ 156 157 static inline int fls(int x) 158 { 159 int r = 32; 160 161 if (!x) 162 return 0; 163 if (!(x & 0xffff0000u)) { 164 x <<= 16; 165 r -= 16; 166 } 167 if (!(x & 0xff000000u)) { 168 x <<= 8; 169 r -= 8; 170 } 171 if (!(x & 0xf0000000u)) { 172 x <<= 4; 173 r -= 4; 174 } 175 if (!(x & 0xc0000000u)) { 176 x <<= 2; 177 r -= 2; 178 } 179 if (!(x & 0x80000000u)) { 180 x <<= 1; 181 r -= 1; 182 } 183 return r; 184 } 185 186 static inline int fls64(__u64 x) 187 { 188 __u32 h = (__u32) (x >> 32); 189 if (h) 190 return fls(h) + 32; 191 return fls((int)x); 192 } 193 194 #define for_each_bit(bit, addr, size) \ 195 for ((bit) = find_first_bit((addr), (size)); \ 196 (bit) < (size); \ 197 (bit) = find_next_bit((addr), (size), (bit) + 1)) 198 199 200 static __inline int get_bitmask_order(unsigned int count) 201 { 202 int order; 203 204 order = fls(count); 205 return order; /* We could be slightly more clever with -1 here... */ 206 } 207 208 static __inline int get_count_order(unsigned int count) 209 { 210 int order; 211 212 order = fls(count) - 1; 213 if (count & (count - 1)) 214 order++; 215 return order; 216 } 217 218 219 /** 220 * rol32 - rotate a 32-bit value left 221 * @word: value to rotate 222 * @shift: bits to roll 223 */ 224 static inline __u32 rol32(__u32 word, unsigned int shift) 225 { 226 return (word << shift) | (word >> (32 - shift)); 227 } 228 229 /** 230 * ror32 - rotate a 32-bit value right 231 * @word: value to rotate 232 * @shift: bits to roll 233 */ 234 static inline __u32 ror32(__u32 word, unsigned int shift) 235 { 236 return (word >> shift) | (word << (32 - shift)); 237 } 238 239 static inline unsigned fls_long(unsigned long l) 240 { 241 if (sizeof(l) == 4) 242 return fls(l); 243 return fls64(l); 244 } 245 246 /* 247 * hweightN: returns the hamming weight (i.e. the number 248 * of bits set) of a N-bit word 249 */ 250 251 static inline unsigned long hweight32(unsigned long w) 252 { 253 unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555); 254 res = (res & 0x33333333) + ((res >> 2) & 0x33333333); 255 res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F); 256 res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF); 257 return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF); 258 } 259 260 static inline unsigned long hweight64(__u64 w) 261 { 262 #if BITS_PER_LONG < 64 263 return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w); 264 #else 265 u64 res; 266 res = (w & 0x5555555555555555U) + ((w >> 1) & 0x5555555555555555U); 267 res = (res & 0x3333333333333333U) + ((res >> 2) & 0x3333333333333333U); 268 res = (res & 0x0F0F0F0F0F0F0F0FU) + ((res >> 4) & 0x0F0F0F0F0F0F0F0FU); 269 res = (res & 0x00FF00FF00FF00FFU) + ((res >> 8) & 0x00FF00FF00FF00FFU); 270 res = (res & 0x0000FFFF0000FFFFU) + ((res >> 16) & 0x0000FFFF0000FFFFU); 271 return (res & 0x00000000FFFFFFFFU) + ((res >> 32) & 0x00000000FFFFFFFFU); 272 #endif 273 } 274 275 static inline unsigned long hweight_long(unsigned long w) 276 { 277 return sizeof(w) == 4 ? hweight32(w) : hweight64(w); 278 } 279 280 #endif 281