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