LCOV - code coverage report
Current view: top level - src/port - pg_bitutils.c (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 21 39 53.8 %
Date: 2021-12-04 22:09:09 Functions: 4 8 50.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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        2032 : pg_popcount_available(void)
     127             : {
     128        2032 :     unsigned int exx[4] = {0, 0, 0, 0};
     129             : 
     130             : #if defined(HAVE__GET_CPUID)
     131        2032 :     __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        2032 :     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           0 : pg_popcount32_choose(uint32 word)
     149             : {
     150           0 :     if (pg_popcount_available())
     151             :     {
     152           0 :         pg_popcount32 = pg_popcount32_fast;
     153           0 :         pg_popcount64 = pg_popcount64_fast;
     154             :     }
     155             :     else
     156             :     {
     157           0 :         pg_popcount32 = pg_popcount32_slow;
     158           0 :         pg_popcount64 = pg_popcount64_slow;
     159             :     }
     160             : 
     161           0 :     return pg_popcount32(word);
     162             : }
     163             : 
     164             : static int
     165        2032 : pg_popcount64_choose(uint64 word)
     166             : {
     167        2032 :     if (pg_popcount_available())
     168             :     {
     169        2032 :         pg_popcount32 = pg_popcount32_fast;
     170        2032 :         pg_popcount64 = pg_popcount64_fast;
     171             :     }
     172             :     else
     173             :     {
     174           0 :         pg_popcount32 = pg_popcount32_slow;
     175           0 :         pg_popcount64 = pg_popcount64_slow;
     176             :     }
     177             : 
     178        2032 :     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           0 : pg_popcount32_fast(uint32 word)
     187             : {
     188             : #ifdef _MSC_VER
     189             :     return __popcnt(word);
     190             : #else
     191             :     uint32      res;
     192             : 
     193           0 : __asm__ __volatile__(" popcntl %1,%0\n":"=q"(res):"rm"(word):"cc");
     194           0 :     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    29037750 : pg_popcount64_fast(uint64 word)
     204             : {
     205             : #ifdef _MSC_VER
     206             :     return __popcnt64(word);
     207             : #else
     208             :     uint64      res;
     209             : 
     210    29037750 : __asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
     211    29037750 :     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           0 : pg_popcount32_slow(uint32 word)
     224             : {
     225             : #ifdef HAVE__BUILTIN_POPCOUNT
     226           0 :     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           0 : pg_popcount64_slow(uint64 word)
     246             : {
     247             : #ifdef HAVE__BUILTIN_POPCOUNT
     248             : #if defined(HAVE_LONG_INT_64)
     249           0 :     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        7192 : pg_popcount(const char *buf, int bytes)
     297             : {
     298        7192 :     uint64      popcnt = 0;
     299             : 
     300             : #if SIZEOF_VOID_P >= 8
     301             :     /* Process in 64-bit chunks if the buffer is aligned. */
     302        7192 :     if (buf == (const char *) TYPEALIGN(8, buf))
     303             :     {
     304        7088 :         const uint64 *words = (const uint64 *) buf;
     305             : 
     306        7088 :         while (bytes >= 8)
     307             :         {
     308           0 :             popcnt += pg_popcount64(*words++);
     309           0 :             bytes -= 8;
     310             :         }
     311             : 
     312        7088 :         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       14444 :     while (bytes--)
     332        7252 :         popcnt += pg_number_of_ones[(unsigned char) *buf++];
     333             : 
     334        7192 :     return popcnt;
     335             : }

Generated by: LCOV version 1.14