1 /* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
2
3 /**
4 * @brief Bit twiddling operations
5 *
6 * Bit twiddling shortcuts for various
7 * operations; see http://graphics.stanford.edu/%7Eseander/bithacks.html
8 * for details.
9 */
10 #ifndef _BITOPS_H
11 #define _BITOPS_H
12
13 /**
14 * @brief Next power of 2
15 * @param x The number to be rounded
16 * @return the rounded number
17 *
18 * Rounds an unsigned integer up to the
19 * next power of 2; i.e. 2, 4, 8, 16, etc.
20 */
next_power_of_2(unsigned int x)21 static inline unsigned int next_power_of_2(unsigned int x)
22 {
23 #ifdef __GNUC__
24 return 1 << (sizeof(unsigned int) * 8 - __builtin_clz(--x));
25 #else
26 x--;
27 x |= (x >> 1);
28 x |= (x >> 2);
29 x |= (x >> 4);
30 x |= (x >> 8);
31 x |= (x >> 16);
32 return ++x;
33 #endif
34 }
35
36 /**
37 * @brief Count bits set
38 * @param w Number in which to count bits
39 * @return The number of bits set
40 *
41 * Counts the number of bits in an unsigned int
42 * that are set to 1. So, for example, in the
43 * number 5, which is 101 in binary, there are
44 * two bits set to 1.
45 */
count_bits_set(unsigned int w)46 static inline unsigned int count_bits_set(unsigned int w)
47 {
48 #ifdef __GNUC__
49 return __builtin_popcount(w);
50 #else
51 const int S[] = {1, 2, 4, 8, 16};
52 const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
53 int c = w;
54 c = ((c >> S[0]) & B[0]) + (c & B[0]);
55 c = ((c >> S[1]) & B[1]) + (c & B[1]);
56 c = ((c >> S[2]) & B[2]) + (c & B[2]);
57 c = ((c >> S[3]) & B[3]) + (c & B[3]);
58 c = ((c >> S[4]) & B[4]) + (c & B[4]);
59 return c;
60 #endif
61 }
62
63 /**
64 * quote from GCC doc "Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero."
65 */
bits_ffs(unsigned int x)66 static inline unsigned bits_ffs(unsigned int x)
67 {
68 #ifdef __GNUC__
69 return __builtin_ffs(x);
70 #else
71 if (x == 0) return 0;
72 unsigned i = 1;
73 while (!(x & 0x1)) {
74 x = x >> 1;
75 ++i;
76 }
77 return i;
78 #endif
79 }
80
81
82
83 /**
84 * @brief Make even number macro
85 * @param n Number to make even
86 *
87 * Quick macro to make a number even, by
88 * forcing the rightmost bit to 0.
89 */
90 #define make_even_number(n) ((n) += ((n) & 0x1)?1:0) //! ~ceil()
91 //#define make_even_number(n) ((x) &= ~0x1) //! ~floor()
92
93 /**
94 * @brief Conditionally set flag macro
95 * @param number to set or unset flag in
96 * @param mask bitmask to be set or unset
97 * @param condition whether to set or unset the flag
98 *
99 * According to a condition, this macro will set or unset a
100 * particular flag in a number. It's a quick way of doing
101 * this:
102 * if (condition) number |= mask; else number &= ~mask;
103 */
104 #define conditionally_set_flag(number, mask, condition) ((number) ^= (-(condition) ^ (number)) & (mask))
105
106 #endif /* _BITOPS_H */
107