cds/algo/bitop.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_BITOP_H
   4 #define CDSLIB_BITOP_H
   5
   6 /*
   7     Different bit algorithms:
   8         LSB        get least significant bit number
   9         MSB        get most significant bit number
  10         bswap    swap byte order of word
  11         RBO        reverse bit order of word
  12
  13     Editions:
  14         2007.10.08    Maxim.Khiszinsky    Created
  15 */
  16
  17 #include <cds/details/defs.h>
  18 #include <cds/compiler/bitop.h>
  19
  20 namespace cds {
  21     /// Bit operations
  22     namespace bitop {
  23
  24         ///@cond none
  25         namespace details {
  26             template <int> struct BitOps;
  27
  28             // 32-bit bit ops
  29             template <> struct BitOps<4> {
  30                 typedef uint32_t        TUInt;
  31
  32                 static int      MSB( TUInt x )      { return bitop::platform::msb32( x );   }
  33                 static int      LSB( TUInt x )      { return bitop::platform::lsb32( x );   }
  34                 static int      MSBnz( TUInt x )    { return bitop::platform::msb32nz( x ); }
  35                 static int      LSBnz( TUInt x )    { return bitop::platform::lsb32nz( x ); }
  36                 static int      SBC( TUInt x )      { return bitop::platform::sbc32( x ) ;  }
  37                 static int      ZBC( TUInt x )      { return bitop::platform::zbc32( x ) ;  }
  38
  39                 static TUInt    RBO( TUInt x )      { return bitop::platform::rbo32( x );   }
  40                 static bool     complement( TUInt& x, int nBit ) { return bitop::platform::complement32( &x, nBit ); }
  41
  42                 static TUInt    RandXorShift(TUInt x) { return bitop::platform::RandXorShift32(x); }
  43             };
  44
  45             // 64-bit bit ops
  46             template <> struct BitOps<8> {
  47                 typedef atomic64u_unaligned        TUInt;
  48
  49                 static int      MSB( TUInt x )        { return bitop::platform::msb64( x );     }
  50                 static int      LSB( TUInt x )        { return bitop::platform::lsb64( x );     }
  51                 static int      MSBnz( TUInt x )      { return bitop::platform::msb64nz( x );   }
  52                 static int      LSBnz( TUInt x )      { return bitop::platform::lsb64nz( x );   }
  53                 static  int     SBC( TUInt x )        { return bitop::platform::sbc64( x ) ;    }
  54                 static  int     ZBC( TUInt x )        { return bitop::platform::zbc64( x ) ;    }
  55
  56                 static TUInt    RBO( TUInt x )        { return bitop::platform::rbo64( x );     }
  57                 static bool     complement( TUInt& x, int nBit ) { return bitop::platform::complement64( &x, nBit ); }
  58
  59                 static TUInt    RandXorShift(TUInt x) { return bitop::platform::RandXorShift64(x); }
  60             };
  61         }    // namespace details
  62         //@endcond
  63
  64
  65         /// Get least significant bit (LSB) number (1..32/64), 0 if nArg == 0
  66         template <typename T>
  67         static inline int LSB( T nArg )
  68         {
  69             return details::BitOps< sizeof(T) >::LSB( (typename details::BitOps<sizeof(T)>::TUInt) nArg );
  70         }
  71
  72         /// Get least significant bit (LSB) number (0..31/63)
  73         /**
  74             Precondition: nArg != 0
  75         */
  76         template <typename T>
  77         static inline int LSBnz( T nArg )
  78         {
  79             assert( nArg != 0 );
  80             return details::BitOps< sizeof(T) >::LSBnz( (typename details::BitOps<sizeof(T)>::TUInt) nArg );
  81         }
  82
  83         /// Get most significant bit (MSB) number (1..32/64), 0 if nArg == 0
  84         template <typename T>
  85         static inline int MSB( T nArg )
  86         {
  87             return details::BitOps< sizeof(T) >::MSB( (typename details::BitOps<sizeof(T)>::TUInt) nArg );
  88         }
  89
  90         /// Get most significant bit (MSB) number (0..31/63)
  91         /**
  92             Precondition: nArg != 0
  93         */
  94         template <typename T>
  95         static inline int MSBnz( T nArg )
  96         {
  97             assert( nArg != 0 );
  98             return details::BitOps< sizeof(T) >::MSBnz( (typename details::BitOps<sizeof(T)>::TUInt) nArg );
  99         }
 100
 101         /// Get non-zero bit count of a word
 102         template <typename T>
 103         static inline int SBC( T nArg )
 104         {
 105             return details::BitOps< sizeof(T) >::SBC( (typename details::BitOps<sizeof(T)>::TUInt) nArg );
 106         }
 107
 108         /// Get zero bit count of a word
 109         template <typename T>
 110         static inline int ZBC( T nArg )
 111         {
 112             return details::BitOps< sizeof(T) >::ZBC( (typename details::BitOps<sizeof(T)>::TUInt) nArg );
 113         }
 114
 115         /// Reverse bit order of \p nArg
 116         template <typename T>
 117         static inline T RBO( T nArg )
 118         {
 119             return (T) details::BitOps< sizeof(T) >::RBO( (typename details::BitOps<sizeof(T)>::TUInt) nArg );
 120         }
 121
 122         /// Complement bit \p nBit in \p nArg
 123         template <typename T>
 124         static inline bool complement( T& nArg, int nBit )
 125         {
 126             return details::BitOps< sizeof(T) >::complement( reinterpret_cast< typename details::BitOps<sizeof(T)>::TUInt& >( nArg ), nBit );
 127         }
 128
 129         /// Simple random number generator
 130         template <typename T>
 131         static inline T RandXorShift( T x)
 132         {
 133             return (T) details::BitOps< sizeof(T) >::RandXorShift(x);
 134         }
 135
 136     } // namespace bitop
 137 } //namespace cds
 138
 139 #endif    // #ifndef CDSLIB_BITOP_H
 140