1 #ifndef MARISA_GRIMOIRE_VECTOR_POP_COUNT_H_ 2 #define MARISA_GRIMOIRE_VECTOR_POP_COUNT_H_ 3 4 #include "marisa/grimoire/intrin.h" 5 6 namespace marisa { 7 namespace grimoire { 8 namespace vector { 9 10 #if MARISA_WORD_SIZE == 64 11 12 class PopCount { 13 public: PopCount(UInt64 x)14 explicit PopCount(UInt64 x) : value_() { 15 x = (x & 0x5555555555555555ULL) + ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1); 16 x = (x & 0x3333333333333333ULL) + ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2); 17 x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4); 18 x *= 0x0101010101010101ULL; 19 value_ = x; 20 } 21 lo8()22 std::size_t lo8() const { 23 return (std::size_t)(value_ & 0xFFU); 24 } lo16()25 std::size_t lo16() const { 26 return (std::size_t)((value_ >> 8) & 0xFFU); 27 } lo24()28 std::size_t lo24() const { 29 return (std::size_t)((value_ >> 16) & 0xFFU); 30 } lo32()31 std::size_t lo32() const { 32 return (std::size_t)((value_ >> 24) & 0xFFU); 33 } lo40()34 std::size_t lo40() const { 35 return (std::size_t)((value_ >> 32) & 0xFFU); 36 } lo48()37 std::size_t lo48() const { 38 return (std::size_t)((value_ >> 40) & 0xFFU); 39 } lo56()40 std::size_t lo56() const { 41 return (std::size_t)((value_ >> 48) & 0xFFU); 42 } lo64()43 std::size_t lo64() const { 44 return (std::size_t)((value_ >> 56) & 0xFFU); 45 } 46 count(UInt64 x)47 static std::size_t count(UInt64 x) { 48 #if defined(MARISA_X64) && defined(MARISA_USE_POPCNT) 49 #ifdef _MSC_VER 50 return __popcnt64(x); 51 #else // _MSC_VER 52 return static_cast<std::size_t>(_mm_popcnt_u64(x)); 53 #endif // _MSC_VER 54 #else // defined(MARISA_X64) && defined(MARISA_USE_POPCNT) 55 return PopCount(x).lo64(); 56 #endif // defined(MARISA_X64) && defined(MARISA_USE_POPCNT) 57 } 58 59 private: 60 UInt64 value_; 61 }; 62 63 #else // MARISA_WORD_SIZE == 64 64 65 class PopCount { 66 public: 67 explicit PopCount(UInt32 x) : value_() { 68 x = (x & 0x55555555U) + ((x & 0xAAAAAAAAU) >> 1); 69 x = (x & 0x33333333U) + ((x & 0xCCCCCCCCU) >> 2); 70 x = (x & 0x0F0F0F0FU) + ((x & 0xF0F0F0F0U) >> 4); 71 x *= 0x01010101U; 72 value_ = x; 73 } 74 75 std::size_t lo8() const { 76 return value_ & 0xFFU; 77 } 78 std::size_t lo16() const { 79 return (value_ >> 8) & 0xFFU; 80 } 81 std::size_t lo24() const { 82 return (value_ >> 16) & 0xFFU; 83 } 84 std::size_t lo32() const { 85 return (value_ >> 24) & 0xFFU; 86 } 87 88 static std::size_t count(UInt32 x) { 89 #ifdef MARISA_USE_POPCNT 90 #ifdef _MSC_VER 91 return __popcnt(x); 92 #else // _MSC_VER 93 return _mm_popcnt_u32(x); 94 #endif // _MSC_VER 95 #else // MARISA_USE_POPCNT 96 return PopCount(x).lo32(); 97 #endif // MARISA_USE_POPCNT 98 } 99 100 private: 101 UInt32 value_; 102 }; 103 104 #endif // MARISA_WORD_SIZE == 64 105 106 } // namespace vector 107 } // namespace grimoire 108 } // namespace marisa 109 110 #endif // MARISA_GRIMOIRE_VECTOR_POP_COUNT_H_ 111