xapian-core/common/popcount.h

   1 /** @file
   2  * @brief Count the number of set bits in an integer type
   3  */
   4 /* Copyright (C) 2014-2020 Olly Betts
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  19  */
  20
  21 #ifndef XAPIAN_INCLUDED_POPCOUNT_H
  22 #define XAPIAN_INCLUDED_POPCOUNT_H
  23
  24 #ifndef PACKAGE
  25 # error config.h must be included first in each C++ source file
  26 #endif
  27
  28 #if !HAVE_DECL___BUILTIN_POPCOUNT
  29 // Only include <intrin.h> if we have to as it can result in warnings about
  30 // duplicate declarations of builtin functions under mingw.
  31 # if HAVE_DECL___POPCNT || HAVE_DECL___POPCNT64
  32 #  include <intrin.h>
  33 # endif
  34 #endif
  35
  36 /// Add the number of set bits in value to accumulator.
  37 template<typename A, typename V>
  38 static inline void
  39 add_popcount(A& accumulator, V value)
  40 {
  41     if (false) {
  42 #if HAVE_DECL___BUILTIN_POPCOUNT
  43     } else if constexpr(sizeof(V) == sizeof(unsigned)) {
  44         accumulator += __builtin_popcount(value);
  45 #elif HAVE_DECL___POPCNT
  46     } else if constexpr(sizeof(V) == sizeof(unsigned)) {
  47         accumulator += static_cast<A>(__popcnt(value));
  48 #endif
  49 #if HAVE_DECL___BUILTIN_POPCOUNTL
  50     } else if constexpr(sizeof(V) == sizeof(unsigned long)) {
  51         accumulator += __builtin_popcountl(value);
  52 #endif
  53 #if HAVE_DECL___BUILTIN_POPCOUNTLL
  54     } else if constexpr(sizeof(V) == sizeof(unsigned long long)) {
  55         accumulator += __builtin_popcountll(value);
  56 #elif HAVE_DECL___POPCNT64
  57     } else if constexpr(sizeof(V) == sizeof(unsigned long long)) {
  58         accumulator += static_cast<A>(__popcnt64(value));
  59 #endif
  60     } else {
  61         auto u = static_cast<std::make_unsigned_t<V>>(value);
  62         while (u) {
  63             ++accumulator;
  64             // Bit twiddling trick to unset the lowest set bit of u.
  65             u &= u - 1;
  66         }
  67     }
  68 }
  69
  70 #endif // XAPIAN_INCLUDED_POPCOUNT_H