cds/details/bitop_generic.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_DETAILS_BITOP_GENERIC_H
   4 #define CDSLIB_DETAILS_BITOP_GENERIC_H
   5
   6 #include <stdlib.h>     // rand()
   7 namespace cds {
   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 )
  12         {
  13             return (x & ( x - 1 )) == 0    && x;
  14         }
  15 #endif
  16
  17 #ifndef cds_bitop_isPow2_64_DEFINED
  18         static inline bool isPow2_64( atomic64_unaligned x )
  19         {
  20             return (x & ( x - 1 )) == 0 && x;
  21         }
  22 #endif
  23
  24         //***************************************************
  25         // Most significant bit number (1..N)
  26         // Return 0 if x == 0
  27         //
  28 #ifndef cds_bitop_msb32_DEFINED
  29         // Return number (1..32) of most significant bit
  30         // Return 0 if x == 0
  31         // Source: Linux kernel
  32         static inline int msb32( uint32_t x )
  33         {
  34             int r = 32;
  35
  36             if (!x)
  37                 return 0;
  38             if (!(x & 0xffff0000u)) {
  39                 x <<= 16;
  40                 r -= 16;
  41             }
  42             if (!(x & 0xff000000u)) {
  43                 x <<= 8;
  44                 r -= 8;
  45             }
  46             if (!(x & 0xf0000000u)) {
  47                 x <<= 4;
  48                 r -= 4;
  49             }
  50             if (!(x & 0xc0000000u)) {
  51                 x <<= 2;
  52                 r -= 2;
  53             }
  54             if (!(x & 0x80000000u)) {
  55                 x <<= 1;
  56                 r -= 1;
  57             }
  58             return r;
  59         }
  60 #endif
  61
  62 #ifndef cds_bitop_msb32nz_DEFINED
  63         static inline int msb32nz( uint32_t x )
  64         {
  65             return msb32( x ) - 1;
  66         }
  67 #endif
  68
  69 #ifndef cds_bitop_msb64_DEFINED
  70         static inline int msb64( atomic64u_unaligned x )
  71         {
  72             uint32_t h = (uint32_t) (x >> 32);
  73             if ( h )
  74                 return msb32( h ) + 32;
  75             return msb32( (uint32_t) x );
  76         }
  77 #endif
  78
  79 #ifndef cds_bitop_msb64nz_DEFINED
  80         static inline int msb64nz( atomic64u_unaligned x )
  81         {
  82             return msb64( x ) - 1;
  83         }
  84 #endif
  85
  86         //***************************************************
  87         // Least significant bit number (1..N)
  88         // Return 0 if x == 0
  89         //
  90 #ifndef cds_bitop_lsb32_DEFINED
  91         // Return number (1..32) of least significant bit
  92         // Return 0 if x == 0
  93         // Source: Linux kernel
  94         static inline int lsb32( uint32_t x )
  95         {
  96             int r = 1;
  97
  98             if (!x)
  99                 return 0;
 100             if (!(x & 0xffff)) {
 101                 x >>= 16;
 102                 r += 16;
 103             }
 104             if (!(x & 0xff)) {
 105                 x >>= 8;
 106                 r += 8;
 107             }
 108             if (!(x & 0xf)) {
 109                 x >>= 4;
 110                 r += 4;
 111             }
 112             if (!(x & 3)) {
 113                 x >>= 2;
 114                 r += 2;
 115             }
 116             if (!(x & 1)) {
 117                 x >>= 1;
 118                 r += 1;
 119             }
 120             return r;
 121         }
 122 #endif
 123
 124 #ifndef cds_bitop_lsb32nz_DEFINED
 125         static inline int lsb32nz( uint32_t x )
 126         {
 127             return lsb32( x ) - 1;
 128         }
 129 #endif
 130
 131 #ifndef cds_bitop_lsb64_DEFINED
 132         static inline int lsb64( atomic64u_unaligned x )
 133         {
 134             if ( !x )
 135                 return 0;
 136             if ( x & 0xffffffffu )
 137                 return lsb32( (uint32_t) x );
 138             return lsb32( (uint32_t) (x >> 32) ) + 32;
 139         }
 140 #endif
 141
 142 #ifndef cds_bitop_lsb64nz_DEFINED
 143         static inline int lsb64nz( atomic64u_unaligned x )
 144         {
 145             return lsb64( x ) - 1;
 146         }
 147 #endif
 148
 149         //******************************************************
 150         // Reverse bit order
 151         //******************************************************
 152 #ifndef cds_bitop_rbo32_DEFINED
 153         static inline uint32_t rbo32( uint32_t x )
 154         {
 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);
 159             // swap nibbles ...
 160             x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
 161             // swap bytes
 162             x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
 163             // swap 2-byte long pairs
 164             return ( x >> 16 ) | ( x << 16 );
 165         }
 166 #endif
 167
 168 #ifndef cds_bitop_rbo64_DEFINED
 169         static inline atomic64u_t rbo64( atomic64u_unaligned x )
 170         {
 171             //                      Low 32bit                                          Hight 32bit
 172             return ( ((atomic64u_t) rbo32( (uint32_t) x )) << 32 ) | ((atomic64u_t) rbo32( (uint32_t) (x >> 32) ));
 173         }
 174 #endif
 175
 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 )
 181         {
 182 #        ifdef cds_beans_zbc32_DEFINED
 183             return 32 - zbc32( x );
 184 #        else
 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;
 189 #        endif
 190         }
 191 #endif
 192
 193 #ifndef cds_bitop_sbc64_DEFINED
 194         static inline int sbc64( atomic64u_unaligned x )
 195         {
 196 #        ifdef cds_beans_zbc64_DEFINED
 197             return 64 - zbc64( x );
 198 #        else
 199             return sbc32( (uint32_t) (x >> 32) ) + sbc32( (uint32_t) x );
 200 #        endif
 201         }
 202 #endif
 203
 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 )
 209         {
 210             return 32 - sbc32( x );
 211         }
 212 #endif
 213
 214 #ifndef cds_bitop_zbc64_DEFINED
 215         static inline int zbc64( atomic64u_unaligned x )
 216         {
 217             return 64 - sbc64( x );
 218         }
 219 #endif
 220
 221         // Bit complement
 222 #ifndef cds_bitop_complement32_DEFINED
 223         static inline bool complement32( uint32_t * pArg, unsigned int nBit )
 224         {
 225             assert( pArg );
 226             uint32_t nVal = *pArg & (1 << nBit);
 227             *pArg ^= 1 << nBit;
 228             return nVal != 0;
 229         }
 230 #endif
 231
 232 #ifndef cds_bitop_complement64_DEFINED
 233         static inline bool complement64( atomic64u_t * pArg, unsigned int nBit )
 234         {
 235             assert( pArg );
 236             atomic64u_t nVal = *pArg & (atomic64u_t(1) << nBit);
 237             *pArg ^= atomic64u_t(1) << nBit;
 238             return nVal != 0;
 239         }
 240 #endif
 241
 242         /*
 243             Simple random number generator
 244             Source:
 245                 [2003] George Marsaglia "Xorshift RNGs"
 246         */
 247         static inline uint32_t RandXorShift32(uint32_t x)
 248         {
 249             //static uint32_t xRandom = 2463534242UL    ;    //rand() | 0x0100    ;    // must be nonzero
 250             //uint32_t x = xRandom;
 251             if ( !x )
 252                 x = ((rand() + 1) << 16) + rand() + 1;
 253             x ^= x << 13;
 254             x ^= x >> 15;
 255             return x ^= x << 5;
 256         }
 257
 258         static inline uint64_t RandXorShift64(uint64_t x)
 259         {
 260             //static atomic64u_t xRandom = 88172645463325252LL;
 261             //atomic64u_t x = xRandom;
 262             if ( !x )
 263                 x = 88172645463325252LL;
 264             x ^= x << 13;
 265             x ^= x >> 7;
 266             return x ^= x << 17;
 267         }
 268     }}    // namespace bitop::platform
 269 } // namespace cds
 270
 271 #endif    // CDSLIB_DETAILS_BITOP_GENERIC_H