lib/count-one-bits.h

   1 /* count-one-bits.h -- counts the number of 1-bits in a word.
   2    Copyright (C) 2007-2020 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Ben Pfaff.  */
  18
  19 #ifndef COUNT_ONE_BITS_H
  20 #define COUNT_ONE_BITS_H 1
  21
  22 #include <limits.h>
  23 #include <stdlib.h>
  24
  25 #ifndef _GL_INLINE_HEADER_BEGIN
  26  #error "Please include config.h first."
  27 #endif
  28 _GL_INLINE_HEADER_BEGIN
  29 #ifndef COUNT_ONE_BITS_INLINE
  30 # define COUNT_ONE_BITS_INLINE _GL_INLINE
  31 #endif
  32
  33 #ifdef __cplusplus
  34 extern "C" {
  35 #endif
  36
  37 /* Assuming the GCC builtin is GCC_BUILTIN and the MSC builtin is MSC_BUILTIN,
  38    expand to code that computes the number of 1-bits of the local
  39    variable 'x' of type TYPE (an unsigned integer type) and return it
  40    from the current function.  */
  41 #if (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) \
  42     || (__clang_major__ >= 4)
  43 # define COUNT_ONE_BITS(GCC_BUILTIN, MSC_BUILTIN, TYPE) \
  44     return GCC_BUILTIN (x)
  45 #else
  46
  47 /* Compute and return the number of 1-bits set in the least
  48    significant 32 bits of X. */
  49 COUNT_ONE_BITS_INLINE int
  50 count_one_bits_32 (unsigned int x)
  51 {
  52   x = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U);
  53   x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U);
  54   x = (x >> 16) + (x & 0xffff);
  55   x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f);
  56   return (x >> 8) + (x & 0x00ff);
  57 }
  58
  59 /* Expand to code that computes the number of 1-bits of the local
  60    variable 'x' of type TYPE (an unsigned integer type) and return it
  61    from the current function.  */
  62 # define COUNT_ONE_BITS_GENERIC(TYPE)                                   \
  63     do                                                                  \
  64       {                                                                 \
  65         int count = 0;                                                  \
  66         int bits;                                                       \
  67         for (bits = 0; bits < sizeof (TYPE) * CHAR_BIT; bits += 32)     \
  68           {                                                             \
  69             count += count_one_bits_32 (x);                             \
  70             x = x >> 31 >> 1;                                           \
  71           }                                                             \
  72         return count;                                                   \
  73       }                                                                 \
  74     while (0)
  75
  76 # if 1500 <= _MSC_VER && (defined _M_IX86 || defined _M_X64)
  77
  78 /* While gcc falls back to its own generic code if the machine
  79    on which it's running doesn't support popcount, with Microsoft's
  80    compiler we need to detect and fallback ourselves.  */
  81
  82 #  if 0
  83 #   include <intrin.h>
  84 #  else
  85     /* Don't pollute the namespace with too many MSVC intrinsics.  */
  86 #   pragma intrinsic (__cpuid)
  87 #   pragma intrinsic (__popcnt)
  88 #   if defined _M_X64
  89 #    pragma intrinsic (__popcnt64)
  90 #   endif
  91 #  endif
  92
  93 #  if !defined _M_X64
  94 static inline __popcnt64 (unsigned long long x)
  95 {
  96   return __popcnt ((unsigned int) (x >> 32)) + __popcnt ((unsigned int) x);
  97 }
  98 #  endif
  99
 100 /* Return nonzero if popcount is supported.  */
 101
 102 /* 1 if supported, 0 if not supported, -1 if unknown.  */
 103 extern int popcount_support;
 104
 105 COUNT_ONE_BITS_INLINE int
 106 popcount_supported (void)
 107 {
 108   if (popcount_support < 0)
 109     {
 110       /* Do as described in
 111          <https://docs.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64> */
 112       int cpu_info[4];
 113       __cpuid (cpu_info, 1);
 114       popcount_support = (cpu_info[2] >> 23) & 1;
 115     }
 116   return popcount_support;
 117 }
 118
 119 #  define COUNT_ONE_BITS(GCC_BUILTIN, MSC_BUILTIN, TYPE) \
 120      do                                                  \
 121        {                                                 \
 122          if (popcount_supported ())                      \
 123            return MSC_BUILTIN (x);                       \
 124          else                                            \
 125            COUNT_ONE_BITS_GENERIC (TYPE);                \
 126        }                                                 \
 127      while (0)
 128
 129 # else
 130
 131 #  define COUNT_ONE_BITS(GCC_BUILTIN, MSC_BUILTIN, TYPE) \
 132      COUNT_ONE_BITS_GENERIC (TYPE)
 133
 134 # endif
 135 #endif
 136
 137 /* Compute and return the number of 1-bits set in X. */
 138 COUNT_ONE_BITS_INLINE int
 139 count_one_bits (unsigned int x)
 140 {
 141   COUNT_ONE_BITS (__builtin_popcount, __popcnt, unsigned int);
 142 }
 143
 144 /* Compute and return the number of 1-bits set in X. */
 145 COUNT_ONE_BITS_INLINE int
 146 count_one_bits_l (unsigned long int x)
 147 {
 148   COUNT_ONE_BITS (__builtin_popcountl, __popcnt, unsigned long int);
 149 }
 150
 151 /* Compute and return the number of 1-bits set in X. */
 152 COUNT_ONE_BITS_INLINE int
 153 count_one_bits_ll (unsigned long long int x)
 154 {
 155   COUNT_ONE_BITS (__builtin_popcountll, __popcnt64, unsigned long long int);
 156 }
 157
 158 #ifdef __cplusplus
 159 }
 160 #endif
 161
 162 _GL_INLINE_HEADER_END
 163
 164 #endif /* COUNT_ONE_BITS_H */