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_ULL(nr) (1ULL << (nr)) 24 #define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) 25 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 26 #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) 27 28 #define MAKE_64BIT_MASK(shift, length) \ 29 (((~0ULL) >> (64 - (length))) << (shift)) 30 31 /** 32 * set_bit - Set a bit in memory 33 * @nr: the bit to set 34 * @addr: the address to start counting from 35 */ 36 static inline void set_bit(long nr, unsigned long *addr) 37 { 38 unsigned long mask = BIT_MASK(nr); 39 unsigned long *p = addr + BIT_WORD(nr); 40 41 *p |= mask; 42 } 43 44 /** 45 * set_bit_atomic - Set a bit in memory atomically 46 * @nr: the bit to set 47 * @addr: the address to start counting from 48 */ 49 static inline void set_bit_atomic(long nr, unsigned long *addr) 50 { 51 unsigned long mask = BIT_MASK(nr); 52 unsigned long *p = addr + BIT_WORD(nr); 53 54 qatomic_or(p, mask); 55 } 56 57 /** 58 * clear_bit - Clears a bit in memory 59 * @nr: Bit to clear 60 * @addr: Address to start counting from 61 */ 62 static inline void clear_bit(long nr, unsigned long *addr) 63 { 64 unsigned long mask = BIT_MASK(nr); 65 unsigned long *p = addr + BIT_WORD(nr); 66 67 *p &= ~mask; 68 } 69 70 /** 71 * change_bit - Toggle a bit in memory 72 * @nr: Bit to change 73 * @addr: Address to start counting from 74 */ 75 static inline void change_bit(long nr, unsigned long *addr) 76 { 77 unsigned long mask = BIT_MASK(nr); 78 unsigned long *p = addr + BIT_WORD(nr); 79 80 *p ^= mask; 81 } 82 83 /** 84 * test_and_set_bit - Set a bit and return its old value 85 * @nr: Bit to set 86 * @addr: Address to count from 87 */ 88 static inline int test_and_set_bit(long nr, unsigned long *addr) 89 { 90 unsigned long mask = BIT_MASK(nr); 91 unsigned long *p = addr + BIT_WORD(nr); 92 unsigned long old = *p; 93 94 *p = old | mask; 95 return (old & mask) != 0; 96 } 97 98 /** 99 * test_and_clear_bit - Clear a bit and return its old value 100 * @nr: Bit to clear 101 * @addr: Address to count from 102 */ 103 static inline int test_and_clear_bit(long nr, unsigned long *addr) 104 { 105 unsigned long mask = BIT_MASK(nr); 106 unsigned long *p = addr + BIT_WORD(nr); 107 unsigned long old = *p; 108 109 *p = old & ~mask; 110 return (old & mask) != 0; 111 } 112 113 /** 114 * test_and_change_bit - Change a bit and return its old value 115 * @nr: Bit to change 116 * @addr: Address to count from 117 */ 118 static inline int test_and_change_bit(long nr, unsigned long *addr) 119 { 120 unsigned long mask = BIT_MASK(nr); 121 unsigned long *p = addr + BIT_WORD(nr); 122 unsigned long old = *p; 123 124 *p = old ^ mask; 125 return (old & mask) != 0; 126 } 127 128 /** 129 * test_bit - Determine whether a bit is set 130 * @nr: bit number to test 131 * @addr: Address to start counting from 132 */ 133 static inline int test_bit(long nr, const unsigned long *addr) 134 { 135 return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); 136 } 137 138 /** 139 * find_last_bit - find the last set bit in a memory region 140 * @addr: The address to start the search at 141 * @size: The maximum size to search 142 * 143 * Returns the bit number of the last set bit, 144 * or @size if there is no set bit in the bitmap. 145 */ 146 unsigned long find_last_bit(const unsigned long *addr, 147 unsigned long size); 148 149 /** 150 * find_next_bit - find the next set bit in a memory region 151 * @addr: The address to base the search on 152 * @offset: The bitnumber to start searching at 153 * @size: The bitmap size in bits 154 * 155 * Returns the bit number of the next set bit, 156 * or @size if there are no further set bits in the bitmap. 157 */ 158 unsigned long find_next_bit(const unsigned long *addr, 159 unsigned long size, 160 unsigned long offset); 161 162 /** 163 * find_next_zero_bit - find the next cleared bit in a memory region 164 * @addr: The address to base the search on 165 * @offset: The bitnumber to start searching at 166 * @size: The bitmap size in bits 167 * 168 * Returns the bit number of the next cleared bit, 169 * or @size if there are no further clear bits in the bitmap. 170 */ 171 172 unsigned long find_next_zero_bit(const unsigned long *addr, 173 unsigned long size, 174 unsigned long offset); 175 176 /** 177 * find_first_bit - find the first set bit in a memory region 178 * @addr: The address to start the search at 179 * @size: The maximum size to search 180 * 181 * Returns the bit number of the first set bit, 182 * or @size if there is no set bit in the bitmap. 183 */ 184 static inline unsigned long find_first_bit(const unsigned long *addr, 185 unsigned long size) 186 { 187 unsigned long result, tmp; 188 189 for (result = 0; result < size; result += BITS_PER_LONG) { 190 tmp = *addr++; 191 if (tmp) { 192 result += ctzl(tmp); 193 return result < size ? result : size; 194 } 195 } 196 /* Not found */ 197 return size; 198 } 199 200 /** 201 * find_first_zero_bit - find the first cleared bit in a memory region 202 * @addr: The address to start the search at 203 * @size: The maximum size to search 204 * 205 * Returns the bit number of the first cleared bit, 206 * or @size if there is no clear bit in the bitmap. 207 */ 208 static inline unsigned long find_first_zero_bit(const unsigned long *addr, 209 unsigned long size) 210 { 211 return find_next_zero_bit(addr, size, 0); 212 } 213 214 /** 215 * rol8 - rotate an 8-bit value left 216 * @word: value to rotate 217 * @shift: bits to roll 218 */ 219 static inline uint8_t rol8(uint8_t word, unsigned int shift) 220 { 221 return (word << shift) | (word >> ((8 - shift) & 7)); 222 } 223 224 /** 225 * ror8 - rotate an 8-bit value right 226 * @word: value to rotate 227 * @shift: bits to roll 228 */ 229 static inline uint8_t ror8(uint8_t word, unsigned int shift) 230 { 231 return (word >> shift) | (word << ((8 - shift) & 7)); 232 } 233 234 /** 235 * rol16 - rotate a 16-bit value left 236 * @word: value to rotate 237 * @shift: bits to roll 238 */ 239 static inline uint16_t rol16(uint16_t word, unsigned int shift) 240 { 241 return (word << shift) | (word >> ((16 - shift) & 15)); 242 } 243 244 /** 245 * ror16 - rotate a 16-bit value right 246 * @word: value to rotate 247 * @shift: bits to roll 248 */ 249 static inline uint16_t ror16(uint16_t word, unsigned int shift) 250 { 251 return (word >> shift) | (word << ((16 - shift) & 15)); 252 } 253 254 /** 255 * rol32 - rotate a 32-bit value left 256 * @word: value to rotate 257 * @shift: bits to roll 258 */ 259 static inline uint32_t rol32(uint32_t word, unsigned int shift) 260 { 261 return (word << shift) | (word >> ((32 - shift) & 31)); 262 } 263 264 /** 265 * ror32 - rotate a 32-bit value right 266 * @word: value to rotate 267 * @shift: bits to roll 268 */ 269 static inline uint32_t ror32(uint32_t word, unsigned int shift) 270 { 271 return (word >> shift) | (word << ((32 - shift) & 31)); 272 } 273 274 /** 275 * rol64 - rotate a 64-bit value left 276 * @word: value to rotate 277 * @shift: bits to roll 278 */ 279 static inline uint64_t rol64(uint64_t word, unsigned int shift) 280 { 281 return (word << shift) | (word >> ((64 - shift) & 63)); 282 } 283 284 /** 285 * ror64 - rotate a 64-bit value right 286 * @word: value to rotate 287 * @shift: bits to roll 288 */ 289 static inline uint64_t ror64(uint64_t word, unsigned int shift) 290 { 291 return (word >> shift) | (word << ((64 - shift) & 63)); 292 } 293 294 /** 295 * extract32: 296 * @value: the value to extract the bit field from 297 * @start: the lowest bit in the bit field (numbered from 0) 298 * @length: the length of the bit field 299 * 300 * Extract from the 32 bit input @value the bit field specified by the 301 * @start and @length parameters, and return it. The bit field must 302 * lie entirely within the 32 bit word. It is valid to request that 303 * all 32 bits are returned (ie @length 32 and @start 0). 304 * 305 * Returns: the value of the bit field extracted from the input value. 306 */ 307 static inline uint32_t extract32(uint32_t value, int start, int length) 308 { 309 assert(start >= 0 && length > 0 && length <= 32 - start); 310 return (value >> start) & (~0U >> (32 - length)); 311 } 312 313 /** 314 * extract8: 315 * @value: the value to extract the bit field from 316 * @start: the lowest bit in the bit field (numbered from 0) 317 * @length: the length of the bit field 318 * 319 * Extract from the 8 bit input @value the bit field specified by the 320 * @start and @length parameters, and return it. The bit field must 321 * lie entirely within the 8 bit word. It is valid to request that 322 * all 8 bits are returned (ie @length 8 and @start 0). 323 * 324 * Returns: the value of the bit field extracted from the input value. 325 */ 326 static inline uint8_t extract8(uint8_t value, int start, int length) 327 { 328 assert(start >= 0 && length > 0 && length <= 8 - start); 329 return extract32(value, start, length); 330 } 331 332 /** 333 * extract16: 334 * @value: the value to extract the bit field from 335 * @start: the lowest bit in the bit field (numbered from 0) 336 * @length: the length of the bit field 337 * 338 * Extract from the 16 bit input @value the bit field specified by the 339 * @start and @length parameters, and return it. The bit field must 340 * lie entirely within the 16 bit word. It is valid to request that 341 * all 16 bits are returned (ie @length 16 and @start 0). 342 * 343 * Returns: the value of the bit field extracted from the input value. 344 */ 345 static inline uint16_t extract16(uint16_t value, int start, int length) 346 { 347 assert(start >= 0 && length > 0 && length <= 16 - start); 348 return extract32(value, start, length); 349 } 350 351 /** 352 * extract64: 353 * @value: the value to extract the bit field from 354 * @start: the lowest bit in the bit field (numbered from 0) 355 * @length: the length of the bit field 356 * 357 * Extract from the 64 bit input @value the bit field specified by the 358 * @start and @length parameters, and return it. The bit field must 359 * lie entirely within the 64 bit word. It is valid to request that 360 * all 64 bits are returned (ie @length 64 and @start 0). 361 * 362 * Returns: the value of the bit field extracted from the input value. 363 */ 364 static inline uint64_t extract64(uint64_t value, int start, int length) 365 { 366 assert(start >= 0 && length > 0 && length <= 64 - start); 367 return (value >> start) & (~0ULL >> (64 - length)); 368 } 369 370 /** 371 * sextract32: 372 * @value: the value to extract the bit field from 373 * @start: the lowest bit in the bit field (numbered from 0) 374 * @length: the length of the bit field 375 * 376 * Extract from the 32 bit input @value the bit field specified by the 377 * @start and @length parameters, and return it, sign extended to 378 * an int32_t (ie with the most significant bit of the field propagated 379 * to all the upper bits of the return value). The bit field must lie 380 * entirely within the 32 bit word. It is valid to request that 381 * all 32 bits are returned (ie @length 32 and @start 0). 382 * 383 * Returns: the sign extended value of the bit field extracted from the 384 * input value. 385 */ 386 static inline int32_t sextract32(uint32_t value, int start, int length) 387 { 388 assert(start >= 0 && length > 0 && length <= 32 - start); 389 /* Note that this implementation relies on right shift of signed 390 * integers being an arithmetic shift. 391 */ 392 return ((int32_t)(value << (32 - length - start))) >> (32 - length); 393 } 394 395 /** 396 * sextract64: 397 * @value: the value to extract the bit field from 398 * @start: the lowest bit in the bit field (numbered from 0) 399 * @length: the length of the bit field 400 * 401 * Extract from the 64 bit input @value the bit field specified by the 402 * @start and @length parameters, and return it, sign extended to 403 * an int64_t (ie with the most significant bit of the field propagated 404 * to all the upper bits of the return value). The bit field must lie 405 * entirely within the 64 bit word. It is valid to request that 406 * all 64 bits are returned (ie @length 64 and @start 0). 407 * 408 * Returns: the sign extended value of the bit field extracted from the 409 * input value. 410 */ 411 static inline int64_t sextract64(uint64_t value, int start, int length) 412 { 413 assert(start >= 0 && length > 0 && length <= 64 - start); 414 /* Note that this implementation relies on right shift of signed 415 * integers being an arithmetic shift. 416 */ 417 return ((int64_t)(value << (64 - length - start))) >> (64 - length); 418 } 419 420 /** 421 * deposit32: 422 * @value: initial value to insert bit field into 423 * @start: the lowest bit in the bit field (numbered from 0) 424 * @length: the length of the bit field 425 * @fieldval: the value to insert into the bit field 426 * 427 * Deposit @fieldval into the 32 bit @value at the bit field specified 428 * by the @start and @length parameters, and return the modified 429 * @value. Bits of @value outside the bit field are not modified. 430 * Bits of @fieldval above the least significant @length bits are 431 * ignored. The bit field must lie entirely within the 32 bit word. 432 * It is valid to request that all 32 bits are modified (ie @length 433 * 32 and @start 0). 434 * 435 * Returns: the modified @value. 436 */ 437 static inline uint32_t deposit32(uint32_t value, int start, int length, 438 uint32_t fieldval) 439 { 440 uint32_t mask; 441 assert(start >= 0 && length > 0 && length <= 32 - start); 442 mask = (~0U >> (32 - length)) << start; 443 return (value & ~mask) | ((fieldval << start) & mask); 444 } 445 446 /** 447 * deposit64: 448 * @value: initial value to insert bit field into 449 * @start: the lowest bit in the bit field (numbered from 0) 450 * @length: the length of the bit field 451 * @fieldval: the value to insert into the bit field 452 * 453 * Deposit @fieldval into the 64 bit @value at the bit field specified 454 * by the @start and @length parameters, and return the modified 455 * @value. Bits of @value outside the bit field are not modified. 456 * Bits of @fieldval above the least significant @length bits are 457 * ignored. The bit field must lie entirely within the 64 bit word. 458 * It is valid to request that all 64 bits are modified (ie @length 459 * 64 and @start 0). 460 * 461 * Returns: the modified @value. 462 */ 463 static inline uint64_t deposit64(uint64_t value, int start, int length, 464 uint64_t fieldval) 465 { 466 uint64_t mask; 467 assert(start >= 0 && length > 0 && length <= 64 - start); 468 mask = (~0ULL >> (64 - length)) << start; 469 return (value & ~mask) | ((fieldval << start) & mask); 470 } 471 472 /** 473 * half_shuffle32: 474 * @x: 32-bit value (of which only the bottom 16 bits are of interest) 475 * 476 * Given an input value:: 477 * 478 * xxxx xxxx xxxx xxxx ABCD EFGH IJKL MNOP 479 * 480 * return the value where the bottom 16 bits are spread out into 481 * the odd bits in the word, and the even bits are zeroed:: 482 * 483 * 0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N 0O0P 484 * 485 * Any bits set in the top half of the input are ignored. 486 * 487 * Returns: the shuffled bits. 488 */ 489 static inline uint32_t half_shuffle32(uint32_t x) 490 { 491 /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits". 492 * It ignores any bits set in the top half of the input. 493 */ 494 x = ((x & 0xFF00) << 8) | (x & 0x00FF); 495 x = ((x << 4) | x) & 0x0F0F0F0F; 496 x = ((x << 2) | x) & 0x33333333; 497 x = ((x << 1) | x) & 0x55555555; 498 return x; 499 } 500 501 /** 502 * half_shuffle64: 503 * @x: 64-bit value (of which only the bottom 32 bits are of interest) 504 * 505 * Given an input value:: 506 * 507 * xxxx xxxx xxxx .... xxxx xxxx ABCD EFGH IJKL MNOP QRST UVWX YZab cdef 508 * 509 * return the value where the bottom 32 bits are spread out into 510 * the odd bits in the word, and the even bits are zeroed:: 511 * 512 * 0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N .... 0U0V 0W0X 0Y0Z 0a0b 0c0d 0e0f 513 * 514 * Any bits set in the top half of the input are ignored. 515 * 516 * Returns: the shuffled bits. 517 */ 518 static inline uint64_t half_shuffle64(uint64_t x) 519 { 520 /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits". 521 * It ignores any bits set in the top half of the input. 522 */ 523 x = ((x & 0xFFFF0000ULL) << 16) | (x & 0xFFFF); 524 x = ((x << 8) | x) & 0x00FF00FF00FF00FFULL; 525 x = ((x << 4) | x) & 0x0F0F0F0F0F0F0F0FULL; 526 x = ((x << 2) | x) & 0x3333333333333333ULL; 527 x = ((x << 1) | x) & 0x5555555555555555ULL; 528 return x; 529 } 530 531 /** 532 * half_unshuffle32: 533 * @x: 32-bit value (of which only the odd bits are of interest) 534 * 535 * Given an input value:: 536 * 537 * xAxB xCxD xExF xGxH xIxJ xKxL xMxN xOxP 538 * 539 * return the value where all the odd bits are compressed down 540 * into the low half of the word, and the high half is zeroed:: 541 * 542 * 0000 0000 0000 0000 ABCD EFGH IJKL MNOP 543 * 544 * Any even bits set in the input are ignored. 545 * 546 * Returns: the unshuffled bits. 547 */ 548 static inline uint32_t half_unshuffle32(uint32_t x) 549 { 550 /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits". 551 * where it is called an inverse half shuffle. 552 */ 553 x &= 0x55555555; 554 x = ((x >> 1) | x) & 0x33333333; 555 x = ((x >> 2) | x) & 0x0F0F0F0F; 556 x = ((x >> 4) | x) & 0x00FF00FF; 557 x = ((x >> 8) | x) & 0x0000FFFF; 558 return x; 559 } 560 561 /** 562 * half_unshuffle64: 563 * @x: 64-bit value (of which only the odd bits are of interest) 564 * 565 * Given an input value:: 566 * 567 * xAxB xCxD xExF xGxH xIxJ xKxL xMxN .... xUxV xWxX xYxZ xaxb xcxd xexf 568 * 569 * return the value where all the odd bits are compressed down 570 * into the low half of the word, and the high half is zeroed:: 571 * 572 * 0000 0000 0000 .... 0000 0000 ABCD EFGH IJKL MNOP QRST UVWX YZab cdef 573 * 574 * Any even bits set in the input are ignored. 575 * 576 * Returns: the unshuffled bits. 577 */ 578 static inline uint64_t half_unshuffle64(uint64_t x) 579 { 580 /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits". 581 * where it is called an inverse half shuffle. 582 */ 583 x &= 0x5555555555555555ULL; 584 x = ((x >> 1) | x) & 0x3333333333333333ULL; 585 x = ((x >> 2) | x) & 0x0F0F0F0F0F0F0F0FULL; 586 x = ((x >> 4) | x) & 0x00FF00FF00FF00FFULL; 587 x = ((x >> 8) | x) & 0x0000FFFF0000FFFFULL; 588 x = ((x >> 16) | x) & 0x00000000FFFFFFFFULL; 589 return x; 590 } 591 592 #endif 593