3 #ifndef __CDS_DETAILS_BITOP_GENERIC_H
4 #define __CDS_DETAILS_BITOP_GENERIC_H
6 #include <stdlib.h> // rand()
8 namespace bitop { namespace platform {
9 // Return true if x = 2 ** k, k >= 0
10 #ifndef cds_bitop_isPow2_32_DEFINED
11 static inline bool isPow2_32( uint32_t x )
13 return (x & ( x - 1 )) == 0 && x;
17 #ifndef cds_bitop_isPow2_64_DEFINED
18 static inline bool isPow2_64( atomic64_unaligned x )
20 return (x & ( x - 1 )) == 0 && x;
24 //***************************************************
25 // Most significant bit number (1..N)
28 #ifndef cds_bitop_msb32_DEFINED
29 // Return number (1..32) of most significant bit
31 // Source: Linux kernel
32 static inline int msb32( uint32_t x )
38 if (!(x & 0xffff0000u)) {
42 if (!(x & 0xff000000u)) {
46 if (!(x & 0xf0000000u)) {
50 if (!(x & 0xc0000000u)) {
54 if (!(x & 0x80000000u)) {
62 #ifndef cds_bitop_msb32nz_DEFINED
63 static inline int msb32nz( uint32_t x )
65 return msb32( x ) - 1;
69 #ifndef cds_bitop_msb64_DEFINED
70 static inline int msb64( atomic64u_unaligned x )
72 uint32_t h = (uint32_t) (x >> 32);
74 return msb32( h ) + 32;
75 return msb32( (uint32_t) x );
79 #ifndef cds_bitop_msb64nz_DEFINED
80 static inline int msb64nz( atomic64u_unaligned x )
82 return msb64( x ) - 1;
86 //***************************************************
87 // Least significant bit number (1..N)
90 #ifndef cds_bitop_lsb32_DEFINED
91 // Return number (1..32) of least significant bit
93 // Source: Linux kernel
94 static inline int lsb32( uint32_t x )
124 #ifndef cds_bitop_lsb32nz_DEFINED
125 static inline int lsb32nz( uint32_t x )
127 return lsb32( x ) - 1;
131 #ifndef cds_bitop_lsb64_DEFINED
132 static inline int lsb64( atomic64u_unaligned x )
136 if ( x & 0xffffffffu )
137 return lsb32( (uint32_t) x );
138 return lsb32( (uint32_t) (x >> 32) ) + 32;
142 #ifndef cds_bitop_lsb64nz_DEFINED
143 static inline int lsb64nz( atomic64u_unaligned x )
145 return lsb64( x ) - 1;
149 //******************************************************
151 //******************************************************
152 #ifndef cds_bitop_rbo32_DEFINED
153 static inline uint32_t rbo32( uint32_t x )
155 // swap odd and even bits
156 x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
157 // swap consecutive pairs
158 x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
160 x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
162 x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
163 // swap 2-byte long pairs
164 return ( x >> 16 ) | ( x << 16 );
168 #ifndef cds_bitop_rbo64_DEFINED
169 static inline atomic64u_t rbo64( atomic64u_unaligned x )
171 // Low 32bit Hight 32bit
172 return ( ((atomic64u_t) rbo32( (uint32_t) x )) << 32 ) | ((atomic64u_t) rbo32( (uint32_t) (x >> 32) ));
176 //******************************************************
177 // Set bit count. Return count of non-zero bits in word
178 //******************************************************
179 #ifndef cds_bitop_sbc32_DEFINED
180 static inline int sbc32( uint32_t x )
182 # ifdef cds_beans_zbc32_DEFINED
183 return 32 - zbc32( x );
185 // Algorithm from Sean Eron Anderson's great collection
186 x = x - ((x >> 1) & 0x55555555);
187 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
188 return (((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
193 #ifndef cds_bitop_sbc64_DEFINED
194 static inline int sbc64( atomic64u_unaligned x )
196 # ifdef cds_beans_zbc64_DEFINED
197 return 64 - zbc64( x );
199 return sbc32( (uint32_t) (x >> 32) ) + sbc32( (uint32_t) x );
204 //******************************************************
205 // Zero bit count. Return count of zero bits in word
206 //******************************************************
207 #ifndef cds_bitop_zbc32_DEFINED
208 static inline int zbc32( uint32_t x )
210 return 32 - sbc32( x );
214 #ifndef cds_bitop_zbc64_DEFINED
215 static inline int zbc64( atomic64u_unaligned x )
217 return 64 - sbc64( x );
222 #ifndef cds_bitop_complement32_DEFINED
223 static inline bool complement32( uint32_t * pArg, unsigned int nBit )
226 uint32_t nVal = *pArg & (1 << nBit);
232 #ifndef cds_bitop_complement64_DEFINED
233 static inline bool complement64( atomic64u_t * pArg, unsigned int nBit )
236 atomic64u_t nVal = *pArg & (atomic64u_t(1) << nBit);
237 *pArg ^= atomic64u_t(1) << nBit;
243 Simple random number generator
245 [2003] George Marsaglia "Xorshift RNGs"
247 static inline uint32_t RandXorShift32(uint32_t x)
249 //static uint32_t xRandom = 2463534242UL ; //rand() | 0x0100 ; // must be nonzero
250 //uint32_t x = xRandom;
252 x = ((rand() + 1) << 16) + rand() + 1;
258 static inline uint64_t RandXorShift64(uint64_t x)
260 //static atomic64u_t xRandom = 88172645463325252LL;
261 //atomic64u_t x = xRandom;
263 x = 88172645463325252LL;
268 }} // namespace bitop::platform
271 #endif // __CDS_DETAILS_BITOP_GENERIC_H