cds/details/bitop_generic.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_DETAILS_BITOP_GENERIC_H
  32 #define CDSLIB_DETAILS_BITOP_GENERIC_H
  33
  34 #include <stdlib.h>     // rand()
  35 namespace cds {
  36     namespace bitop { namespace platform {
  37         // Return true if x = 2 ** k, k >= 0
  38 #ifndef cds_bitop_isPow2_32_DEFINED
  39         static inline bool isPow2_32( uint32_t x )
  40         {
  41             return (x & ( x - 1 )) == 0    && x;
  42         }
  43 #endif
  44
  45 #ifndef cds_bitop_isPow2_64_DEFINED
  46         static inline bool isPow2_64( uint64_t x )
  47         {
  48             return (x & ( x - 1 )) == 0 && x;
  49         }
  50 #endif
  51
  52         //***************************************************
  53         // Most significant bit number (1..N)
  54         // Return 0 if x == 0
  55         //
  56 #ifndef cds_bitop_msb32_DEFINED
  57         // Return number (1..32) of most significant bit
  58         // Return 0 if x == 0
  59         // Source: Linux kernel
  60         static inline int msb32( uint32_t x )
  61         {
  62             int r = 32;
  63
  64             if (!x)
  65                 return 0;
  66             if (!(x & 0xffff0000u)) {
  67                 x <<= 16;
  68                 r -= 16;
  69             }
  70             if (!(x & 0xff000000u)) {
  71                 x <<= 8;
  72                 r -= 8;
  73             }
  74             if (!(x & 0xf0000000u)) {
  75                 x <<= 4;
  76                 r -= 4;
  77             }
  78             if (!(x & 0xc0000000u)) {
  79                 x <<= 2;
  80                 r -= 2;
  81             }
  82             if (!(x & 0x80000000u)) {
  83                 x <<= 1;
  84                 r -= 1;
  85             }
  86             return r;
  87         }
  88 #endif
  89
  90 #ifndef cds_bitop_msb32nz_DEFINED
  91         static inline int msb32nz( uint32_t x )
  92         {
  93             return msb32( x ) - 1;
  94         }
  95 #endif
  96
  97 #ifndef cds_bitop_msb64_DEFINED
  98         static inline int msb64( uint64_t x )
  99         {
 100             uint32_t h = (uint32_t) (x >> 32);
 101             if ( h )
 102                 return msb32( h ) + 32;
 103             return msb32( (uint32_t) x );
 104         }
 105 #endif
 106
 107 #ifndef cds_bitop_msb64nz_DEFINED
 108         static inline int msb64nz( uint64_t x )
 109         {
 110             return msb64( x ) - 1;
 111         }
 112 #endif
 113
 114         //***************************************************
 115         // Least significant bit number (1..N)
 116         // Return 0 if x == 0
 117         //
 118 #ifndef cds_bitop_lsb32_DEFINED
 119         // Return number (1..32) of least significant bit
 120         // Return 0 if x == 0
 121         // Source: Linux kernel
 122         static inline int lsb32( uint32_t x )
 123         {
 124             int r = 1;
 125
 126             if (!x)
 127                 return 0;
 128             if (!(x & 0xffff)) {
 129                 x >>= 16;
 130                 r += 16;
 131             }
 132             if (!(x & 0xff)) {
 133                 x >>= 8;
 134                 r += 8;
 135             }
 136             if (!(x & 0xf)) {
 137                 x >>= 4;
 138                 r += 4;
 139             }
 140             if (!(x & 3)) {
 141                 x >>= 2;
 142                 r += 2;
 143             }
 144             if (!(x & 1)) {
 145                 x >>= 1;
 146                 r += 1;
 147             }
 148             return r;
 149         }
 150 #endif
 151
 152 #ifndef cds_bitop_lsb32nz_DEFINED
 153         static inline int lsb32nz( uint32_t x )
 154         {
 155             return lsb32( x ) - 1;
 156         }
 157 #endif
 158
 159 #ifndef cds_bitop_lsb64_DEFINED
 160         static inline int lsb64( uint64_t x )
 161         {
 162             if ( !x )
 163                 return 0;
 164             if ( x & 0xffffffffu )
 165                 return lsb32( (uint32_t) x );
 166             return lsb32( (uint32_t) (x >> 32) ) + 32;
 167         }
 168 #endif
 169
 170 #ifndef cds_bitop_lsb64nz_DEFINED
 171         static inline int lsb64nz( uint64_t x )
 172         {
 173             return lsb64( x ) - 1;
 174         }
 175 #endif
 176
 177         //******************************************************
 178         // Reverse bit order
 179         //******************************************************
 180 #ifndef cds_bitop_rbo32_DEFINED
 181         static inline uint32_t rbo32( uint32_t x )
 182         {
 183             // swap odd and even bits
 184             x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
 185             // swap consecutive pairs
 186             x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
 187             // swap nibbles ...
 188             x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
 189             // swap bytes
 190             x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
 191             // swap 2-byte long pairs
 192             return ( x >> 16 ) | ( x << 16 );
 193         }
 194 #endif
 195
 196 #ifndef cds_bitop_rbo64_DEFINED
 197         static inline uint64_t rbo64( uint64_t x )
 198         {
 199             //                      Low 32bit                                          Hight 32bit
 200             return ( static_cast<uint64_t>(rbo32( (uint32_t) x )) << 32 ) | ( static_cast<uint64_t>( rbo32( (uint32_t) (x >> 32) )));
 201         }
 202 #endif
 203
 204         //******************************************************
 205         // Set bit count. Return count of non-zero bits in word
 206         //******************************************************
 207 #ifndef cds_bitop_sbc32_DEFINED
 208         static inline int sbc32( uint32_t x )
 209         {
 210 #        ifdef cds_beans_zbc32_DEFINED
 211             return 32 - zbc32( x );
 212 #        else
 213             // Algorithm from Sean Eron Anderson's great collection
 214             x = x - ((x >> 1) & 0x55555555);
 215             x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 216             return (((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
 217 #        endif
 218         }
 219 #endif
 220
 221 #ifndef cds_bitop_sbc64_DEFINED
 222         static inline int sbc64( uint64_t x )
 223         {
 224 #        ifdef cds_beans_zbc64_DEFINED
 225             return 64 - zbc64( x );
 226 #        else
 227             return sbc32( (uint32_t) (x >> 32) ) + sbc32( (uint32_t) x );
 228 #        endif
 229         }
 230 #endif
 231
 232         //******************************************************
 233         // Zero bit count. Return count of zero bits in word
 234         //******************************************************
 235 #ifndef cds_bitop_zbc32_DEFINED
 236         static inline int zbc32( uint32_t x )
 237         {
 238             return 32 - sbc32( x );
 239         }
 240 #endif
 241
 242 #ifndef cds_bitop_zbc64_DEFINED
 243         static inline int zbc64( uint64_t x )
 244         {
 245             return 64 - sbc64( x );
 246         }
 247 #endif
 248
 249         // Bit complement
 250 #ifndef cds_bitop_complement32_DEFINED
 251         static inline bool complement32( uint32_t * pArg, unsigned int nBit )
 252         {
 253             assert( pArg );
 254             uint32_t nVal = *pArg & (1 << nBit);
 255             *pArg ^= 1 << nBit;
 256             return nVal != 0;
 257         }
 258 #endif
 259
 260 #ifndef cds_bitop_complement64_DEFINED
 261         static inline bool complement64( uint64_t * pArg, unsigned int nBit )
 262         {
 263             assert( pArg );
 264             uint64_t nVal = *pArg & (uint64_t(1) << nBit);
 265             *pArg ^= uint64_t(1) << nBit;
 266             return nVal != 0;
 267         }
 268 #endif
 269
 270         /*
 271             Simple random number generator
 272             Source:
 273                 [2003] George Marsaglia "Xorshift RNGs"
 274         */
 275         static inline uint32_t RandXorShift32(uint32_t x)
 276         {
 277             //static uint32_t xRandom = 2463534242UL    ;    //rand() | 0x0100    ;    // must be nonzero
 278             //uint32_t x = xRandom;
 279             if ( !x )
 280                 x = ((rand() + 1) << 16) + rand() + 1;
 281             x ^= x << 13;
 282             x ^= x >> 15;
 283             return x ^= x << 5;
 284         }
 285
 286         static inline uint64_t RandXorShift64(uint64_t x)
 287         {
 288             //static uint64_t xRandom = 88172645463325252LL;
 289             //uint64_t x = xRandom;
 290             if ( !x )
 291                 x = 88172645463325252LL;
 292             x ^= x << 13;
 293             x ^= x >> 7;
 294             return x ^= x << 17;
 295         }
 296     }}    // namespace bitop::platform
 297 } // namespace cds
 298
 299 #endif    // CDSLIB_DETAILS_BITOP_GENERIC_H