src/jitcs_int_bitfuncs.h

   1 //===-- src/jitcs_int_bitfuncs.h --------------------------------*- C++ -*-===//
   2 // Trailing-Zero/One-Count and population count.
   3 //
   4 // Copyright (C) 2013-2014 Dirk Steinke.
   5 // See copyright and license notice in COPYRIGHT or include/jitcs.h
   6 //
   7 // Trailing-Zero-Count is used to find bit positions in bitmasks, and
   8 // population count is probably used somewhere too.
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _JITCS_INT_ADT_BITFUNCS_H_
  12 #define _JITCS_INT_ADT_BITFUNCS_H_
  13
  14 #include "jitcs_base.h"
  15
  16 #ifdef _MSC_VER
  17 #include <intrin.h>
  18 #pragma intrinsic(_BitScanForward)
  19 #ifdef JITCS_64
  20 #pragma intrinsic(_BitScanForward64)
  21 #endif
  22 #endif
  23 #if __GNUC__
  24 #include "x86intrin.h"
  25 #endif
  26
  27 namespace jitcs {
  28
  29 inline uint t0cnt32nz_(u32 v, uint o) {
  30   assert(v != 0);
  31 #if __GNUC__
  32   int index = __bsfd(v);
  33 #endif
  34 #ifdef _MSC_VER
  35   unsigned long index;
  36   u8 ok = _BitScanForward(&index, v);
  37   assert(ok);
  38 #endif
  39   return index + o;
  40 }
  41 #ifdef JITCS_64
  42 inline uint t0cnt64nz_(u64 v, uint o) {
  43   assert(v != 0);
  44 #if __GNUC__
  45   int index = __bsfq(v);
  46 #endif
  47 #ifdef _MSC_VER
  48   unsigned long index;
  49   u8 ok = _BitScanForward64(&index, v);
  50   assert(ok);
  51 #endif
  52   return index + o;
  53 }
  54 #else
  55 inline uint t0cnt64nz_(u64 v, uint o) {
  56   assert(v != 0);
  57   return t0cnt32nz_(((u32)v) == 0 ? (u32)(v >> 32) : (u32)v,
  58                     o + (((u32)v) == 0 ? 32 : 0));
  59 }
  60 #endif
  61
  62 inline uint t0cnt32nz(u32 v, uint o = 0) { return t0cnt32nz_(v >> o, o); }
  63 inline uint t0cnt64nz(u64 v, uint o = 0) { return t0cnt64nz_(v >> o, o); }
  64
  65 inline uint t1cnt32nz(u32 v, uint o = 0) { return t0cnt32nz(~v, o); }
  66 inline uint t1cnt64nz(u64 v, uint o = 0) { return t0cnt64nz(~v, o); }
  67
  68 // --------------------------
  69
  70 inline uint popcnt32(u32 v) {
  71   enum {
  72     M01 = (~(u32)0) / 255,
  73     M55 = 0x55 * M01,
  74     M33 = 0x33 * M01,
  75     M0F = 0x0f * M01,
  76   };
  77   v = (v & M55) + ((v >> 1) & M55);
  78   v = (v & M33) + ((v >> 2) & M33);
  79   v = (v & M0F) + ((v >> 4) & M0F);
  80   return (v * M01) >> 24;
  81 }
  82 #ifdef JITCS_64
  83 inline uint popcnt64(u64 v) {
  84   enum {
  85     M01 = (~(u64)0) / 255,
  86     M55 = 0x55 * M01,
  87     M33 = 0x33 * M01,
  88     M0F = 0x0f * M01,
  89   };
  90   v = (v & M55) + ((v >> 1) & M55);
  91   v = (v & M33) + ((v >> 2) & M33);
  92   v = (v & M0F) + ((v >> 4) & M0F);
  93   return (v * M01) >> 24;
  94 }
  95 #else
  96 inline uint popcnt64(u64 v) {
  97   return popcnt32((u32)v) + popcnt32((u32)(v >> 32));
  98 }
  99 #endif
 100
 101 // --------------------------
 102
 103 inline uint t0cntnz(i32 v, uint o = 0) { return t0cnt32nz((u32)v, o); }
 104 inline uint t0cntnz(u32 v, uint o = 0) { return t0cnt32nz(v, o); }
 105 inline uint t0cntnz(u64 v, uint o = 0) { return t0cnt64nz(v, o); }
 106
 107 inline uint t1cntnz(i32 v, uint o = 0) { return t1cnt32nz((u32)v, o); }
 108 inline uint t1cntnz(u32 v, uint o = 0) { return t1cnt32nz(v, o); }
 109 inline uint t1cntnz(u64 v, uint o = 0) { return t1cnt64nz(v, o); }
 110
 111 inline uint popcnt(i32 v) { return popcnt32((u32)v); }
 112 inline uint popcnt(u32 v) { return popcnt32(v); }
 113 inline uint popcnt(u64 v) { return popcnt64(v); }
 114
 115 } // end of namespace evm
 116 #endif
 117 // _JITCS_INT_ADT_BITFUNCS_H_