1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2020 Arm Limited 3 * Copyright(c) 2010-2019 Intel Corporation 4 * Copyright(c) 2023 Microsoft Corporation 5 */ 6 7 #ifndef _RTE_BITOPS_H_ 8 #define _RTE_BITOPS_H_ 9 10 /** 11 * @file 12 * Bit Operations 13 * 14 * This file defines a family of APIs for bit operations 15 * without enforcing memory ordering. 16 */ 17 18 #include <stdint.h> 19 20 #include <rte_debug.h> 21 22 #ifdef __cplusplus 23 extern "C" { 24 #endif 25 26 /** 27 * Get the uint64_t value for a specified bit set. 28 * 29 * @param nr 30 * The bit number in range of 0 to 63. 31 */ 32 #define RTE_BIT64(nr) (UINT64_C(1) << (nr)) 33 34 /** 35 * Get the uint32_t value for a specified bit set. 36 * 37 * @param nr 38 * The bit number in range of 0 to 31. 39 */ 40 #define RTE_BIT32(nr) (UINT32_C(1) << (nr)) 41 42 /** 43 * Get the uint32_t shifted value. 44 * 45 * @param val 46 * The value to be shifted. 47 * @param nr 48 * The shift number in range of 0 to (32 - width of val). 49 */ 50 #define RTE_SHIFT_VAL32(val, nr) (UINT32_C(val) << (nr)) 51 52 /** 53 * Get the uint64_t shifted value. 54 * 55 * @param val 56 * The value to be shifted. 57 * @param nr 58 * The shift number in range of 0 to (64 - width of val). 59 */ 60 #define RTE_SHIFT_VAL64(val, nr) (UINT64_C(val) << (nr)) 61 62 /** 63 * Generate a contiguous 32-bit mask 64 * starting at bit position low and ending at position high. 65 * 66 * @param high 67 * High bit position. 68 * @param low 69 * Low bit position. 70 */ 71 #define RTE_GENMASK32(high, low) \ 72 (((~UINT32_C(0)) << (low)) & (~UINT32_C(0) >> (31u - (high)))) 73 74 /** 75 * Generate a contiguous 64-bit mask 76 * starting at bit position low and ending at position high. 77 * 78 * @param high 79 * High bit position. 80 * @param low 81 * Low bit position. 82 */ 83 #define RTE_GENMASK64(high, low) \ 84 (((~UINT64_C(0)) << (low)) & (~UINT64_C(0) >> (63u - (high)))) 85 86 /** 87 * Extract a 32-bit field element. 88 * 89 * @param mask 90 * Shifted mask. 91 * @param reg 92 * Value of entire bitfield. 93 */ 94 #define RTE_FIELD_GET32(mask, reg) \ 95 ((typeof(mask))(((reg) & (mask)) >> rte_ctz32(mask))) 96 97 /** 98 * Extract a 64-bit field element. 99 * 100 * @param mask 101 * Shifted mask. 102 * @param reg 103 * Value of entire bitfield. 104 */ 105 #define RTE_FIELD_GET64(mask, reg) \ 106 ((typeof(mask))(((reg) & (mask)) >> rte_ctz64(mask))) 107 108 /*------------------------ 32-bit relaxed operations ------------------------*/ 109 110 /** 111 * Get the target bit from a 32-bit value without memory ordering. 112 * 113 * @param nr 114 * The target bit to get. 115 * @param addr 116 * The address holding the bit. 117 * @return 118 * The target bit. 119 */ 120 static inline uint32_t 121 rte_bit_relaxed_get32(unsigned int nr, volatile uint32_t *addr) 122 { 123 RTE_ASSERT(nr < 32); 124 125 uint32_t mask = UINT32_C(1) << nr; 126 return (*addr) & mask; 127 } 128 129 /** 130 * Set the target bit in a 32-bit value to 1 without memory ordering. 131 * 132 * @param nr 133 * The target bit to set. 134 * @param addr 135 * The address holding the bit. 136 */ 137 static inline void 138 rte_bit_relaxed_set32(unsigned int nr, volatile uint32_t *addr) 139 { 140 RTE_ASSERT(nr < 32); 141 142 uint32_t mask = RTE_BIT32(nr); 143 *addr = (*addr) | mask; 144 } 145 146 /** 147 * Clear the target bit in a 32-bit value to 0 without memory ordering. 148 * 149 * @param nr 150 * The target bit to clear. 151 * @param addr 152 * The address holding the bit. 153 */ 154 static inline void 155 rte_bit_relaxed_clear32(unsigned int nr, volatile uint32_t *addr) 156 { 157 RTE_ASSERT(nr < 32); 158 159 uint32_t mask = RTE_BIT32(nr); 160 *addr = (*addr) & (~mask); 161 } 162 163 /** 164 * Return the original bit from a 32-bit value, then set it to 1 without 165 * memory ordering. 166 * 167 * @param nr 168 * The target bit to get and set. 169 * @param addr 170 * The address holding the bit. 171 * @return 172 * The original bit. 173 */ 174 static inline uint32_t 175 rte_bit_relaxed_test_and_set32(unsigned int nr, volatile uint32_t *addr) 176 { 177 RTE_ASSERT(nr < 32); 178 179 uint32_t mask = RTE_BIT32(nr); 180 uint32_t val = *addr; 181 *addr = val | mask; 182 return val & mask; 183 } 184 185 /** 186 * Return the original bit from a 32-bit value, then clear it to 0 without 187 * memory ordering. 188 * 189 * @param nr 190 * The target bit to get and clear. 191 * @param addr 192 * The address holding the bit. 193 * @return 194 * The original bit. 195 */ 196 static inline uint32_t 197 rte_bit_relaxed_test_and_clear32(unsigned int nr, volatile uint32_t *addr) 198 { 199 RTE_ASSERT(nr < 32); 200 201 uint32_t mask = RTE_BIT32(nr); 202 uint32_t val = *addr; 203 *addr = val & (~mask); 204 return val & mask; 205 } 206 207 /*------------------------ 64-bit relaxed operations ------------------------*/ 208 209 /** 210 * Get the target bit from a 64-bit value without memory ordering. 211 * 212 * @param nr 213 * The target bit to get. 214 * @param addr 215 * The address holding the bit. 216 * @return 217 * The target bit. 218 */ 219 static inline uint64_t 220 rte_bit_relaxed_get64(unsigned int nr, volatile uint64_t *addr) 221 { 222 RTE_ASSERT(nr < 64); 223 224 uint64_t mask = RTE_BIT64(nr); 225 return (*addr) & mask; 226 } 227 228 /** 229 * Set the target bit in a 64-bit value to 1 without memory ordering. 230 * 231 * @param nr 232 * The target bit to set. 233 * @param addr 234 * The address holding the bit. 235 */ 236 static inline void 237 rte_bit_relaxed_set64(unsigned int nr, volatile uint64_t *addr) 238 { 239 RTE_ASSERT(nr < 64); 240 241 uint64_t mask = RTE_BIT64(nr); 242 (*addr) = (*addr) | mask; 243 } 244 245 /** 246 * Clear the target bit in a 64-bit value to 0 without memory ordering. 247 * 248 * @param nr 249 * The target bit to clear. 250 * @param addr 251 * The address holding the bit. 252 */ 253 static inline void 254 rte_bit_relaxed_clear64(unsigned int nr, volatile uint64_t *addr) 255 { 256 RTE_ASSERT(nr < 64); 257 258 uint64_t mask = RTE_BIT64(nr); 259 *addr = (*addr) & (~mask); 260 } 261 262 /** 263 * Return the original bit from a 64-bit value, then set it to 1 without 264 * memory ordering. 265 * 266 * @param nr 267 * The target bit to get and set. 268 * @param addr 269 * The address holding the bit. 270 * @return 271 * The original bit. 272 */ 273 static inline uint64_t 274 rte_bit_relaxed_test_and_set64(unsigned int nr, volatile uint64_t *addr) 275 { 276 RTE_ASSERT(nr < 64); 277 278 uint64_t mask = RTE_BIT64(nr); 279 uint64_t val = *addr; 280 *addr = val | mask; 281 return val; 282 } 283 284 /** 285 * Return the original bit from a 64-bit value, then clear it to 0 without 286 * memory ordering. 287 * 288 * @param nr 289 * The target bit to get and clear. 290 * @param addr 291 * The address holding the bit. 292 * @return 293 * The original bit. 294 */ 295 static inline uint64_t 296 rte_bit_relaxed_test_and_clear64(unsigned int nr, volatile uint64_t *addr) 297 { 298 RTE_ASSERT(nr < 64); 299 300 uint64_t mask = RTE_BIT64(nr); 301 uint64_t val = *addr; 302 *addr = val & (~mask); 303 return val & mask; 304 } 305 306 #ifdef RTE_TOOLCHAIN_MSVC 307 308 /** 309 * Get the count of leading 0-bits in v. 310 * 311 * @param v 312 * The value. 313 * @return 314 * The count of leading zero bits. 315 */ 316 static inline unsigned int 317 rte_clz32(uint32_t v) 318 { 319 unsigned long rv; 320 321 (void)_BitScanReverse(&rv, v); 322 323 return (unsigned int)(sizeof(v) * CHAR_BIT - 1 - rv); 324 } 325 326 /** 327 * Get the count of leading 0-bits in v. 328 * 329 * @param v 330 * The value. 331 * @return 332 * The count of leading zero bits. 333 */ 334 static inline unsigned int 335 rte_clz64(uint64_t v) 336 { 337 unsigned long rv; 338 339 (void)_BitScanReverse64(&rv, v); 340 341 return (unsigned int)(sizeof(v) * CHAR_BIT - 1 - rv); 342 } 343 344 /** 345 * Get the count of trailing 0-bits in v. 346 * 347 * @param v 348 * The value. 349 * @return 350 * The count of trailing zero bits. 351 */ 352 static inline unsigned int 353 rte_ctz32(uint32_t v) 354 { 355 unsigned long rv; 356 357 (void)_BitScanForward(&rv, v); 358 359 return (unsigned int)rv; 360 } 361 362 /** 363 * Get the count of trailing 0-bits in v. 364 * 365 * @param v 366 * The value. 367 * @return 368 * The count of trailing zero bits. 369 */ 370 static inline unsigned int 371 rte_ctz64(uint64_t v) 372 { 373 unsigned long rv; 374 375 (void)_BitScanForward64(&rv, v); 376 377 return (unsigned int)rv; 378 } 379 380 /** 381 * Get the count of 1-bits in v. 382 * 383 * @param v 384 * The value. 385 * @return 386 * The count of 1-bits. 387 */ 388 static inline unsigned int 389 rte_popcount32(uint32_t v) 390 { 391 return (unsigned int)__popcnt(v); 392 } 393 394 /** 395 * Get the count of 1-bits in v. 396 * 397 * @param v 398 * The value. 399 * @return 400 * The count of 1-bits. 401 */ 402 static inline unsigned int 403 rte_popcount64(uint64_t v) 404 { 405 return (unsigned int)__popcnt64(v); 406 } 407 408 #else 409 410 /** 411 * Get the count of leading 0-bits in v. 412 * 413 * @param v 414 * The value. 415 * @return 416 * The count of leading zero bits. 417 */ 418 static inline unsigned int 419 rte_clz32(uint32_t v) 420 { 421 return (unsigned int)__builtin_clz(v); 422 } 423 424 /** 425 * Get the count of leading 0-bits in v. 426 * 427 * @param v 428 * The value. 429 * @return 430 * The count of leading zero bits. 431 */ 432 static inline unsigned int 433 rte_clz64(uint64_t v) 434 { 435 return (unsigned int)__builtin_clzll(v); 436 } 437 438 /** 439 * Get the count of trailing 0-bits in v. 440 * 441 * @param v 442 * The value. 443 * @return 444 * The count of trailing zero bits. 445 */ 446 static inline unsigned int 447 rte_ctz32(uint32_t v) 448 { 449 return (unsigned int)__builtin_ctz(v); 450 } 451 452 /** 453 * Get the count of trailing 0-bits in v. 454 * 455 * @param v 456 * The value. 457 * @return 458 * The count of trailing zero bits. 459 */ 460 static inline unsigned int 461 rte_ctz64(uint64_t v) 462 { 463 return (unsigned int)__builtin_ctzll(v); 464 } 465 466 /** 467 * Get the count of 1-bits in v. 468 * 469 * @param v 470 * The value. 471 * @return 472 * The count of 1-bits. 473 */ 474 static inline unsigned int 475 rte_popcount32(uint32_t v) 476 { 477 return (unsigned int)__builtin_popcount(v); 478 } 479 480 /** 481 * Get the count of 1-bits in v. 482 * 483 * @param v 484 * The value. 485 * @return 486 * The count of 1-bits. 487 */ 488 static inline unsigned int 489 rte_popcount64(uint64_t v) 490 { 491 return (unsigned int)__builtin_popcountll(v); 492 } 493 494 #endif 495 496 /** 497 * Combines 32b inputs most significant set bits into the least 498 * significant bits to construct a value with the same MSBs as x 499 * but all 1's under it. 500 * 501 * @param x 502 * The integer whose MSBs need to be combined with its LSBs 503 * @return 504 * The combined value. 505 */ 506 static inline uint32_t 507 rte_combine32ms1b(uint32_t x) 508 { 509 x |= x >> 1; 510 x |= x >> 2; 511 x |= x >> 4; 512 x |= x >> 8; 513 x |= x >> 16; 514 515 return x; 516 } 517 518 /** 519 * Combines 64b inputs most significant set bits into the least 520 * significant bits to construct a value with the same MSBs as x 521 * but all 1's under it. 522 * 523 * @param v 524 * The integer whose MSBs need to be combined with its LSBs 525 * @return 526 * The combined value. 527 */ 528 static inline uint64_t 529 rte_combine64ms1b(uint64_t v) 530 { 531 v |= v >> 1; 532 v |= v >> 2; 533 v |= v >> 4; 534 v |= v >> 8; 535 v |= v >> 16; 536 v |= v >> 32; 537 538 return v; 539 } 540 541 /** 542 * Searches the input parameter for the least significant set bit 543 * (starting from zero). 544 * If a least significant 1 bit is found, its bit index is returned. 545 * If the content of the input parameter is zero, then the content of the return 546 * value is undefined. 547 * @param v 548 * input parameter, should not be zero. 549 * @return 550 * least significant set bit in the input parameter. 551 */ 552 static inline uint32_t 553 rte_bsf32(uint32_t v) 554 { 555 return (uint32_t)rte_ctz32(v); 556 } 557 558 /** 559 * Searches the input parameter for the least significant set bit 560 * (starting from zero). Safe version (checks for input parameter being zero). 561 * 562 * @warning ``pos`` must be a valid pointer. It is not checked! 563 * 564 * @param v 565 * The input parameter. 566 * @param pos 567 * If ``v`` was not 0, this value will contain position of least significant 568 * bit within the input parameter. 569 * @return 570 * Returns 0 if ``v`` was 0, otherwise returns 1. 571 */ 572 static inline int 573 rte_bsf32_safe(uint32_t v, uint32_t *pos) 574 { 575 if (v == 0) 576 return 0; 577 578 *pos = rte_bsf32(v); 579 return 1; 580 } 581 582 /** 583 * Searches the input parameter for the least significant set bit 584 * (starting from zero). 585 * If a least significant 1 bit is found, its bit index is returned. 586 * If the content of the input parameter is zero, then the content of the return 587 * value is undefined. 588 * @param v 589 * input parameter, should not be zero. 590 * @return 591 * least significant set bit in the input parameter. 592 */ 593 static inline uint32_t 594 rte_bsf64(uint64_t v) 595 { 596 return (uint32_t)rte_ctz64(v); 597 } 598 599 /** 600 * Searches the input parameter for the least significant set bit 601 * (starting from zero). Safe version (checks for input parameter being zero). 602 * 603 * @warning ``pos`` must be a valid pointer. It is not checked! 604 * 605 * @param v 606 * The input parameter. 607 * @param pos 608 * If ``v`` was not 0, this value will contain position of least significant 609 * bit within the input parameter. 610 * @return 611 * Returns 0 if ``v`` was 0, otherwise returns 1. 612 */ 613 static inline int 614 rte_bsf64_safe(uint64_t v, uint32_t *pos) 615 { 616 if (v == 0) 617 return 0; 618 619 *pos = rte_bsf64(v); 620 return 1; 621 } 622 623 /** 624 * Return the last (most-significant) bit set. 625 * 626 * @note The last (most significant) bit is at position 32. 627 * @note rte_fls_u32(0) = 0, rte_fls_u32(1) = 1, rte_fls_u32(0x80000000) = 32 628 * 629 * @param x 630 * The input parameter. 631 * @return 632 * The last (most-significant) bit set, or 0 if the input is 0. 633 */ 634 static inline uint32_t 635 rte_fls_u32(uint32_t x) 636 { 637 return (x == 0) ? 0 : 32 - rte_clz32(x); 638 } 639 640 /** 641 * Return the last (most-significant) bit set. 642 * 643 * @note The last (most significant) bit is at position 64. 644 * @note rte_fls_u64(0) = 0, rte_fls_u64(1) = 1, 645 * rte_fls_u64(0x8000000000000000) = 64 646 * 647 * @param x 648 * The input parameter. 649 * @return 650 * The last (most-significant) bit set, or 0 if the input is 0. 651 */ 652 static inline uint32_t 653 rte_fls_u64(uint64_t x) 654 { 655 return (x == 0) ? 0 : 64 - rte_clz64(x); 656 } 657 658 /*********** Macros to work with powers of 2 ********/ 659 660 /** 661 * Macro to return 1 if n is a power of 2, 0 otherwise 662 */ 663 #define RTE_IS_POWER_OF_2(n) ((n) && !(((n) - 1) & (n))) 664 665 /** 666 * Returns true if n is a power of 2 667 * @param n 668 * Number to check 669 * @return 1 if true, 0 otherwise 670 */ 671 static inline int 672 rte_is_power_of_2(uint32_t n) 673 { 674 return n && !(n & (n - 1)); 675 } 676 677 /** 678 * Aligns input parameter to the next power of 2 679 * 680 * @param x 681 * The integer value to align 682 * 683 * @return 684 * Input parameter aligned to the next power of 2 685 */ 686 static inline uint32_t 687 rte_align32pow2(uint32_t x) 688 { 689 x--; 690 x = rte_combine32ms1b(x); 691 692 return x + 1; 693 } 694 695 /** 696 * Aligns input parameter to the previous power of 2 697 * 698 * @param x 699 * The integer value to align 700 * 701 * @return 702 * Input parameter aligned to the previous power of 2 703 */ 704 static inline uint32_t 705 rte_align32prevpow2(uint32_t x) 706 { 707 x = rte_combine32ms1b(x); 708 709 return x - (x >> 1); 710 } 711 712 /** 713 * Aligns 64b input parameter to the next power of 2 714 * 715 * @param v 716 * The 64b value to align 717 * 718 * @return 719 * Input parameter aligned to the next power of 2 720 */ 721 static inline uint64_t 722 rte_align64pow2(uint64_t v) 723 { 724 v--; 725 v = rte_combine64ms1b(v); 726 727 return v + 1; 728 } 729 730 /** 731 * Aligns 64b input parameter to the previous power of 2 732 * 733 * @param v 734 * The 64b value to align 735 * 736 * @return 737 * Input parameter aligned to the previous power of 2 738 */ 739 static inline uint64_t 740 rte_align64prevpow2(uint64_t v) 741 { 742 v = rte_combine64ms1b(v); 743 744 return v - (v >> 1); 745 } 746 747 /** 748 * Return the rounded-up log2 of a integer. 749 * 750 * @note Contrary to the logarithm mathematical operation, 751 * rte_log2_u32(0) == 0 and not -inf. 752 * 753 * @param v 754 * The input parameter. 755 * @return 756 * The rounded-up log2 of the input, or 0 if the input is 0. 757 */ 758 static inline uint32_t 759 rte_log2_u32(uint32_t v) 760 { 761 if (v == 0) 762 return 0; 763 v = rte_align32pow2(v); 764 return rte_bsf32(v); 765 } 766 767 /** 768 * Return the rounded-up log2 of a 64-bit integer. 769 * 770 * @note Contrary to the logarithm mathematical operation, 771 * rte_log2_u64(0) == 0 and not -inf. 772 * 773 * @param v 774 * The input parameter. 775 * @return 776 * The rounded-up log2 of the input, or 0 if the input is 0. 777 */ 778 static inline uint32_t 779 rte_log2_u64(uint64_t v) 780 { 781 if (v == 0) 782 return 0; 783 v = rte_align64pow2(v); 784 /* we checked for v being 0 already, so no undefined behavior */ 785 return rte_bsf64(v); 786 } 787 788 #ifdef __cplusplus 789 } 790 #endif 791 792 #endif /* _RTE_BITOPS_H_ */ 793