src/port/pg_bitutils.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * pg_bitutils.c
   4  *        Miscellaneous functions for bit-wise operations.
   5  *
   6  * Copyright (c) 2019-2021, PostgreSQL Global Development Group
   7  *
   8  * IDENTIFICATION
   9  *        src/port/pg_bitutils.c
  10  *
  11  *-------------------------------------------------------------------------
  12  */
  13 #include "c.h"
  14
  15 #ifdef HAVE__GET_CPUID
  16 #include <cpuid.h>
  17 #endif
  18 #ifdef HAVE__CPUID
  19 #include <intrin.h>
  20 #endif
  21
  22 #include "port/pg_bitutils.h"
  23
  24
  25 /*
  26  * Array giving the position of the left-most set bit for each possible
  27  * byte value.  We count the right-most position as the 0th bit, and the
  28  * left-most the 7th bit.  The 0th entry of the array should not be used.
  29  *
  30  * Note: this is not used by the functions in pg_bitutils.h when
  31  * HAVE__BUILTIN_CLZ is defined, but we provide it anyway, so that
  32  * extensions possibly compiled with a different compiler can use it.
  33  */
  34 const uint8 pg_leftmost_one_pos[256] = {
  35         0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
  36         4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  37         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  38         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  39         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  40         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  41         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  42         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  43         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  44         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  45         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  46         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  47         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  48         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  49         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  50         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
  51 };
  52
  53 /*
  54  * Array giving the position of the right-most set bit for each possible
  55  * byte value.  We count the right-most position as the 0th bit, and the
  56  * left-most the 7th bit.  The 0th entry of the array should not be used.
  57  *
  58  * Note: this is not used by the functions in pg_bitutils.h when
  59  * HAVE__BUILTIN_CTZ is defined, but we provide it anyway, so that
  60  * extensions possibly compiled with a different compiler can use it.
  61  */
  62 const uint8 pg_rightmost_one_pos[256] = {
  63         0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  64         4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  65         5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  66         4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  67         6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  68         4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  69         5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  70         4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  71         7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  72         4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  73         5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  74         4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  75         6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  76         4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  77         5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  78         4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  79 };
  80
  81 /*
  82  * Array giving the number of 1-bits in each possible byte value.
  83  *
  84  * Note: we export this for use by functions in which explicit use
  85  * of the popcount functions seems unlikely to be a win.
  86  */
  87 const uint8 pg_number_of_ones[256] = {
  88         0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  89         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  90         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  91         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  92         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  93         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  94         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  95         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  96         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  97         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  98         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  99         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 100         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 101         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 102         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 103         4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
 104 };
 105
 106 static int      pg_popcount32_slow(uint32 word);
 107 static int      pg_popcount64_slow(uint64 word);
 108
 109 #ifdef TRY_POPCNT_FAST
 110 static bool pg_popcount_available(void);
 111 static int      pg_popcount32_choose(uint32 word);
 112 static int      pg_popcount64_choose(uint64 word);
 113 static int      pg_popcount32_fast(uint32 word);
 114 static int      pg_popcount64_fast(uint64 word);
 115
 116 int                     (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
 117 int                     (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
 118 #endif                                                  /* TRY_POPCNT_FAST */
 119
 120 #ifdef TRY_POPCNT_FAST
 121
 122 /*
 123  * Return true if CPUID indicates that the POPCNT instruction is available.
 124  */
 125 static bool
 126 pg_popcount_available(void)
 127 {
 128         unsigned int exx[4] = {0, 0, 0, 0};
 129
 130 #if defined(HAVE__GET_CPUID)
 131         __get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
 132 #elif defined(HAVE__CPUID)
 133         __cpuid(exx, 1);
 134 #else
 135 #error cpuid instruction not available
 136 #endif
 137
 138         return (exx[2] & (1 << 23)) != 0;       /* POPCNT */
 139 }
 140
 141 /*
 142  * These functions get called on the first call to pg_popcount32 etc.
 143  * They detect whether we can use the asm implementations, and replace
 144  * the function pointers so that subsequent calls are routed directly to
 145  * the chosen implementation.
 146  */
 147 static int
 148 pg_popcount32_choose(uint32 word)
 149 {
 150         if (pg_popcount_available())
 151         {
 152                 pg_popcount32 = pg_popcount32_fast;
 153                 pg_popcount64 = pg_popcount64_fast;
 154         }
 155         else
 156         {
 157                 pg_popcount32 = pg_popcount32_slow;
 158                 pg_popcount64 = pg_popcount64_slow;
 159         }
 160
 161         return pg_popcount32(word);
 162 }
 163
 164 static int
 165 pg_popcount64_choose(uint64 word)
 166 {
 167         if (pg_popcount_available())
 168         {
 169                 pg_popcount32 = pg_popcount32_fast;
 170                 pg_popcount64 = pg_popcount64_fast;
 171         }
 172         else
 173         {
 174                 pg_popcount32 = pg_popcount32_slow;
 175                 pg_popcount64 = pg_popcount64_slow;
 176         }
 177
 178         return pg_popcount64(word);
 179 }
 180
 181 /*
 182  * pg_popcount32_fast
 183  *              Return the number of 1 bits set in word
 184  */
 185 static int
 186 pg_popcount32_fast(uint32 word)
 187 {
 188 #ifdef _MSC_VER
 189         return __popcnt(word);
 190 #else
 191         uint32          res;
 192
 193 __asm__ __volatile__(" popcntl %1,%0\n":"=q"(res):"rm"(word):"cc");
 194         return (int) res;
 195 #endif
 196 }
 197
 198 /*
 199  * pg_popcount64_fast
 200  *              Return the number of 1 bits set in word
 201  */
 202 static int
 203 pg_popcount64_fast(uint64 word)
 204 {
 205 #ifdef _MSC_VER
 206         return __popcnt64(word);
 207 #else
 208         uint64          res;
 209
 210 __asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
 211         return (int) res;
 212 #endif
 213 }
 214
 215 #endif                                                  /* TRY_POPCNT_FAST */
 216
 217
 218 /*
 219  * pg_popcount32_slow
 220  *              Return the number of 1 bits set in word
 221  */
 222 static int
 223 pg_popcount32_slow(uint32 word)
 224 {
 225 #ifdef HAVE__BUILTIN_POPCOUNT
 226         return __builtin_popcount(word);
 227 #else                                                   /* !HAVE__BUILTIN_POPCOUNT */
 228         int                     result = 0;
 229
 230         while (word != 0)
 231         {
 232                 result += pg_number_of_ones[word & 255];
 233                 word >>= 8;
 234         }
 235
 236         return result;
 237 #endif                                                  /* HAVE__BUILTIN_POPCOUNT */
 238 }
 239
 240 /*
 241  * pg_popcount64_slow
 242  *              Return the number of 1 bits set in word
 243  */
 244 static int
 245 pg_popcount64_slow(uint64 word)
 246 {
 247 #ifdef HAVE__BUILTIN_POPCOUNT
 248 #if defined(HAVE_LONG_INT_64)
 249         return __builtin_popcountl(word);
 250 #elif defined(HAVE_LONG_LONG_INT_64)
 251         return __builtin_popcountll(word);
 252 #else
 253 #error must have a working 64-bit integer datatype
 254 #endif
 255 #else                                                   /* !HAVE__BUILTIN_POPCOUNT */
 256         int                     result = 0;
 257
 258         while (word != 0)
 259         {
 260                 result += pg_number_of_ones[word & 255];
 261                 word >>= 8;
 262         }
 263
 264         return result;
 265 #endif                                                  /* HAVE__BUILTIN_POPCOUNT */
 266 }
 267
 268 #ifndef TRY_POPCNT_FAST
 269
 270 /*
 271  * When the POPCNT instruction is not available, there's no point in using
 272  * function pointers to vary the implementation between the fast and slow
 273  * method.  We instead just make these actual external functions when
 274  * TRY_POPCNT_FAST is not defined.  The compiler should be able to inline
 275  * the slow versions here.
 276  */
 277 int
 278 pg_popcount32(uint32 word)
 279 {
 280         return pg_popcount32_slow(word);
 281 }
 282
 283 int
 284 pg_popcount64(uint64 word)
 285 {
 286         return pg_popcount64_slow(word);
 287 }
 288
 289 #endif                                                  /* !TRY_POPCNT_FAST */
 290
 291 /*
 292  * pg_popcount
 293  *              Returns the number of 1-bits in buf
 294  */
 295 uint64
 296 pg_popcount(const char *buf, int bytes)
 297 {
 298         uint64          popcnt = 0;
 299
 300 #if SIZEOF_VOID_P >= 8
 301         /* Process in 64-bit chunks if the buffer is aligned. */
 302         if (buf == (const char *) TYPEALIGN(8, buf))
 303         {
 304                 const uint64 *words = (const uint64 *) buf;
 305
 306                 while (bytes >= 8)
 307                 {
 308                         popcnt += pg_popcount64(*words++);
 309                         bytes -= 8;
 310                 }
 311
 312                 buf = (const char *) words;
 313         }
 314 #else
 315         /* Process in 32-bit chunks if the buffer is aligned. */
 316         if (buf == (const char *) TYPEALIGN(4, buf))
 317         {
 318                 const uint32 *words = (const uint32 *) buf;
 319
 320                 while (bytes >= 4)
 321                 {
 322                         popcnt += pg_popcount32(*words++);
 323                         bytes -= 4;
 324                 }
 325
 326                 buf = (const char *) words;
 327         }
 328 #endif
 329
 330         /* Process any remaining bytes */
 331         while (bytes--)
 332                 popcnt += pg_number_of_ones[(unsigned char) *buf++];
 333
 334         return popcnt;
 335 }