1 /* 2 * Bitops Module 3 * 4 * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> 5 * 6 * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h 7 * 8 * This work is licensed under the terms of the GNU LGPL, version 2.1 or later. 9 * See the COPYING.LIB file in the top-level directory. 10 */ 11 12 #ifndef BITOPS_H 13 #define BITOPS_H 14 15 16 #include "host-utils.h" 17 #include "atomic.h" 18 19 #define BITS_PER_BYTE CHAR_BIT 20 #define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) 21 22 #define BIT(nr) (1UL << (nr)) 23 #define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) 24 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 25 #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) 26 27 /** 28 * set_bit - Set a bit in memory 29 * @nr: the bit to set 30 * @addr: the address to start counting from 31 */ 32 static inline void set_bit(long nr, unsigned long *addr) 33 { 34 unsigned long mask = BIT_MASK(nr); 35 unsigned long *p = addr + BIT_WORD(nr); 36 37 *p |= mask; 38 } 39 40 /** 41 * set_bit_atomic - Set a bit in memory atomically 42 * @nr: the bit to set 43 * @addr: the address to start counting from 44 */ 45 static inline void set_bit_atomic(long nr, unsigned long *addr) 46 { 47 unsigned long mask = BIT_MASK(nr); 48 unsigned long *p = addr + BIT_WORD(nr); 49 50 atomic_or(p, mask); 51 } 52 53 /** 54 * clear_bit - Clears a bit in memory 55 * @nr: Bit to clear 56 * @addr: Address to start counting from 57 */ 58 static inline void clear_bit(long nr, unsigned long *addr) 59 { 60 unsigned long mask = BIT_MASK(nr); 61 unsigned long *p = addr + BIT_WORD(nr); 62 63 *p &= ~mask; 64 } 65 66 /** 67 * change_bit - Toggle a bit in memory 68 * @nr: Bit to change 69 * @addr: Address to start counting from 70 */ 71 static inline void change_bit(long nr, unsigned long *addr) 72 { 73 unsigned long mask = BIT_MASK(nr); 74 unsigned long *p = addr + BIT_WORD(nr); 75 76 *p ^= mask; 77 } 78 79 /** 80 * test_and_set_bit - Set a bit and return its old value 81 * @nr: Bit to set 82 * @addr: Address to count from 83 */ 84 static inline int test_and_set_bit(long nr, unsigned long *addr) 85 { 86 unsigned long mask = BIT_MASK(nr); 87 unsigned long *p = addr + BIT_WORD(nr); 88 unsigned long old = *p; 89 90 *p = old | mask; 91 return (old & mask) != 0; 92 } 93 94 /** 95 * test_and_clear_bit - Clear a bit and return its old value 96 * @nr: Bit to clear 97 * @addr: Address to count from 98 */ 99 static inline int test_and_clear_bit(long nr, unsigned long *addr) 100 { 101 unsigned long mask = BIT_MASK(nr); 102 unsigned long *p = addr + BIT_WORD(nr); 103 unsigned long old = *p; 104 105 *p = old & ~mask; 106 return (old & mask) != 0; 107 } 108 109 /** 110 * test_and_change_bit - Change a bit and return its old value 111 * @nr: Bit to change 112 * @addr: Address to count from 113 */ 114 static inline int test_and_change_bit(long nr, unsigned long *addr) 115 { 116 unsigned long mask = BIT_MASK(nr); 117 unsigned long *p = addr + BIT_WORD(nr); 118 unsigned long old = *p; 119 120 *p = old ^ mask; 121 return (old & mask) != 0; 122 } 123 124 /** 125 * test_bit - Determine whether a bit is set 126 * @nr: bit number to test 127 * @addr: Address to start counting from 128 */ 129 static inline int test_bit(long nr, const unsigned long *addr) 130 { 131 return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); 132 } 133 134 /** 135 * find_last_bit - find the last set bit in a memory region 136 * @addr: The address to start the search at 137 * @size: The maximum size to search 138 * 139 * Returns the bit number of the first set bit, or size. 140 */ 141 unsigned long find_last_bit(const unsigned long *addr, 142 unsigned long size); 143 144 /** 145 * find_next_bit - find the next set bit in a memory region 146 * @addr: The address to base the search on 147 * @offset: The bitnumber to start searching at 148 * @size: The bitmap size in bits 149 */ 150 unsigned long find_next_bit(const unsigned long *addr, 151 unsigned long size, 152 unsigned long offset); 153 154 /** 155 * find_next_zero_bit - find the next cleared bit in a memory region 156 * @addr: The address to base the search on 157 * @offset: The bitnumber to start searching at 158 * @size: The bitmap size in bits 159 */ 160 161 unsigned long find_next_zero_bit(const unsigned long *addr, 162 unsigned long size, 163 unsigned long offset); 164 165 /** 166 * find_first_bit - find the first set bit in a memory region 167 * @addr: The address to start the search at 168 * @size: The maximum size to search 169 * 170 * Returns the bit number of the first set bit. 171 */ 172 static inline unsigned long find_first_bit(const unsigned long *addr, 173 unsigned long size) 174 { 175 unsigned long result, tmp; 176 177 for (result = 0; result < size; result += BITS_PER_LONG) { 178 tmp = *addr++; 179 if (tmp) { 180 result += ctzl(tmp); 181 return result < size ? result : size; 182 } 183 } 184 /* Not found */ 185 return size; 186 } 187 188 /** 189 * find_first_zero_bit - find the first cleared bit in a memory region 190 * @addr: The address to start the search at 191 * @size: The maximum size to search 192 * 193 * Returns the bit number of the first cleared bit. 194 */ 195 static inline unsigned long find_first_zero_bit(const unsigned long *addr, 196 unsigned long size) 197 { 198 return find_next_zero_bit(addr, size, 0); 199 } 200 201 static inline unsigned long hweight_long(unsigned long w) 202 { 203 unsigned long count; 204 205 for (count = 0; w; w >>= 1) { 206 count += w & 1; 207 } 208 return count; 209 } 210 211 /** 212 * rol8 - rotate an 8-bit value left 213 * @word: value to rotate 214 * @shift: bits to roll 215 */ 216 static inline uint8_t rol8(uint8_t word, unsigned int shift) 217 { 218 return (word << shift) | (word >> (8 - shift)); 219 } 220 221 /** 222 * ror8 - rotate an 8-bit value right 223 * @word: value to rotate 224 * @shift: bits to roll 225 */ 226 static inline uint8_t ror8(uint8_t word, unsigned int shift) 227 { 228 return (word >> shift) | (word << (8 - shift)); 229 } 230 231 /** 232 * rol16 - rotate a 16-bit value left 233 * @word: value to rotate 234 * @shift: bits to roll 235 */ 236 static inline uint16_t rol16(uint16_t word, unsigned int shift) 237 { 238 return (word << shift) | (word >> (16 - shift)); 239 } 240 241 /** 242 * ror16 - rotate a 16-bit value right 243 * @word: value to rotate 244 * @shift: bits to roll 245 */ 246 static inline uint16_t ror16(uint16_t word, unsigned int shift) 247 { 248 return (word >> shift) | (word << (16 - shift)); 249 } 250 251 /** 252 * rol32 - rotate a 32-bit value left 253 * @word: value to rotate 254 * @shift: bits to roll 255 */ 256 static inline uint32_t rol32(uint32_t word, unsigned int shift) 257 { 258 return (word << shift) | (word >> (32 - shift)); 259 } 260 261 /** 262 * ror32 - rotate a 32-bit value right 263 * @word: value to rotate 264 * @shift: bits to roll 265 */ 266 static inline uint32_t ror32(uint32_t word, unsigned int shift) 267 { 268 return (word >> shift) | (word << (32 - shift)); 269 } 270 271 /** 272 * rol64 - rotate a 64-bit value left 273 * @word: value to rotate 274 * @shift: bits to roll 275 */ 276 static inline uint64_t rol64(uint64_t word, unsigned int shift) 277 { 278 return (word << shift) | (word >> (64 - shift)); 279 } 280 281 /** 282 * ror64 - rotate a 64-bit value right 283 * @word: value to rotate 284 * @shift: bits to roll 285 */ 286 static inline uint64_t ror64(uint64_t word, unsigned int shift) 287 { 288 return (word >> shift) | (word << (64 - shift)); 289 } 290 291 /** 292 * extract32: 293 * @value: the value to extract the bit field from 294 * @start: the lowest bit in the bit field (numbered from 0) 295 * @length: the length of the bit field 296 * 297 * Extract from the 32 bit input @value the bit field specified by the 298 * @start and @length parameters, and return it. The bit field must 299 * lie entirely within the 32 bit word. It is valid to request that 300 * all 32 bits are returned (ie @length 32 and @start 0). 301 * 302 * Returns: the value of the bit field extracted from the input value. 303 */ 304 static inline uint32_t extract32(uint32_t value, int start, int length) 305 { 306 assert(start >= 0 && length > 0 && length <= 32 - start); 307 return (value >> start) & (~0U >> (32 - length)); 308 } 309 310 /** 311 * extract64: 312 * @value: the value to extract the bit field from 313 * @start: the lowest bit in the bit field (numbered from 0) 314 * @length: the length of the bit field 315 * 316 * Extract from the 64 bit input @value the bit field specified by the 317 * @start and @length parameters, and return it. The bit field must 318 * lie entirely within the 64 bit word. It is valid to request that 319 * all 64 bits are returned (ie @length 64 and @start 0). 320 * 321 * Returns: the value of the bit field extracted from the input value. 322 */ 323 static inline uint64_t extract64(uint64_t value, int start, int length) 324 { 325 assert(start >= 0 && length > 0 && length <= 64 - start); 326 return (value >> start) & (~0ULL >> (64 - length)); 327 } 328 329 /** 330 * sextract32: 331 * @value: the value to extract the bit field from 332 * @start: the lowest bit in the bit field (numbered from 0) 333 * @length: the length of the bit field 334 * 335 * Extract from the 32 bit input @value the bit field specified by the 336 * @start and @length parameters, and return it, sign extended to 337 * an int32_t (ie with the most significant bit of the field propagated 338 * to all the upper bits of the return value). The bit field must lie 339 * entirely within the 32 bit word. It is valid to request that 340 * all 32 bits are returned (ie @length 32 and @start 0). 341 * 342 * Returns: the sign extended value of the bit field extracted from the 343 * input value. 344 */ 345 static inline int32_t sextract32(uint32_t value, int start, int length) 346 { 347 assert(start >= 0 && length > 0 && length <= 32 - start); 348 /* Note that this implementation relies on right shift of signed 349 * integers being an arithmetic shift. 350 */ 351 return ((int32_t)(value << (32 - length - start))) >> (32 - length); 352 } 353 354 /** 355 * sextract64: 356 * @value: the value to extract the bit field from 357 * @start: the lowest bit in the bit field (numbered from 0) 358 * @length: the length of the bit field 359 * 360 * Extract from the 64 bit input @value the bit field specified by the 361 * @start and @length parameters, and return it, sign extended to 362 * an int64_t (ie with the most significant bit of the field propagated 363 * to all the upper bits of the return value). The bit field must lie 364 * entirely within the 64 bit word. It is valid to request that 365 * all 64 bits are returned (ie @length 64 and @start 0). 366 * 367 * Returns: the sign extended value of the bit field extracted from the 368 * input value. 369 */ 370 static inline int64_t sextract64(uint64_t value, int start, int length) 371 { 372 assert(start >= 0 && length > 0 && length <= 64 - start); 373 /* Note that this implementation relies on right shift of signed 374 * integers being an arithmetic shift. 375 */ 376 return ((int64_t)(value << (64 - length - start))) >> (64 - length); 377 } 378 379 /** 380 * deposit32: 381 * @value: initial value to insert bit field into 382 * @start: the lowest bit in the bit field (numbered from 0) 383 * @length: the length of the bit field 384 * @fieldval: the value to insert into the bit field 385 * 386 * Deposit @fieldval into the 32 bit @value at the bit field specified 387 * by the @start and @length parameters, and return the modified 388 * @value. Bits of @value outside the bit field are not modified. 389 * Bits of @fieldval above the least significant @length bits are 390 * ignored. The bit field must lie entirely within the 32 bit word. 391 * It is valid to request that all 32 bits are modified (ie @length 392 * 32 and @start 0). 393 * 394 * Returns: the modified @value. 395 */ 396 static inline uint32_t deposit32(uint32_t value, int start, int length, 397 uint32_t fieldval) 398 { 399 uint32_t mask; 400 assert(start >= 0 && length > 0 && length <= 32 - start); 401 mask = (~0U >> (32 - length)) << start; 402 return (value & ~mask) | ((fieldval << start) & mask); 403 } 404 405 /** 406 * deposit64: 407 * @value: initial value to insert bit field into 408 * @start: the lowest bit in the bit field (numbered from 0) 409 * @length: the length of the bit field 410 * @fieldval: the value to insert into the bit field 411 * 412 * Deposit @fieldval into the 64 bit @value at the bit field specified 413 * by the @start and @length parameters, and return the modified 414 * @value. Bits of @value outside the bit field are not modified. 415 * Bits of @fieldval above the least significant @length bits are 416 * ignored. The bit field must lie entirely within the 64 bit word. 417 * It is valid to request that all 64 bits are modified (ie @length 418 * 64 and @start 0). 419 * 420 * Returns: the modified @value. 421 */ 422 static inline uint64_t deposit64(uint64_t value, int start, int length, 423 uint64_t fieldval) 424 { 425 uint64_t mask; 426 assert(start >= 0 && length > 0 && length <= 64 - start); 427 mask = (~0ULL >> (64 - length)) << start; 428 return (value & ~mask) | ((fieldval << start) & mask); 429 } 430 431 #endif 432