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