LCOV - code coverage report
Current view: top level - src/include/port - pg_bitutils.h (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 25 28 89.3 %
Date: 2021-11-29 05:09:10 Functions: 9 10 90.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * pg_bitutils.h
       4             :  *    Miscellaneous functions for bit-wise operations.
       5             :  *
       6             :  *
       7             :  * Copyright (c) 2019-2021, PostgreSQL Global Development Group
       8             :  *
       9             :  * src/include/port/pg_bitutils.h
      10             :  *
      11             :  *-------------------------------------------------------------------------
      12             :  */
      13             : #ifndef PG_BITUTILS_H
      14             : #define PG_BITUTILS_H
      15             : 
      16             : #ifndef FRONTEND
      17             : extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
      18             : extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
      19             : extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
      20             : #else
      21             : extern const uint8 pg_leftmost_one_pos[256];
      22             : extern const uint8 pg_rightmost_one_pos[256];
      23             : extern const uint8 pg_number_of_ones[256];
      24             : #endif
      25             : 
      26             : /*
      27             :  * pg_leftmost_one_pos32
      28             :  *      Returns the position of the most significant set bit in "word",
      29             :  *      measured from the least significant bit.  word must not be 0.
      30             :  */
      31             : static inline int
      32    23027872 : pg_leftmost_one_pos32(uint32 word)
      33             : {
      34             : #ifdef HAVE__BUILTIN_CLZ
      35             :     Assert(word != 0);
      36             : 
      37    23027872 :     return 31 - __builtin_clz(word);
      38             : #else
      39             :     int         shift = 32 - 8;
      40             : 
      41             :     Assert(word != 0);
      42             : 
      43             :     while ((word >> shift) == 0)
      44             :         shift -= 8;
      45             : 
      46             :     return shift + pg_leftmost_one_pos[(word >> shift) & 255];
      47             : #endif                          /* HAVE__BUILTIN_CLZ */
      48             : }
      49             : 
      50             : /*
      51             :  * pg_leftmost_one_pos64
      52             :  *      As above, but for a 64-bit word.
      53             :  */
      54             : static inline int
      55     4473296 : pg_leftmost_one_pos64(uint64 word)
      56             : {
      57             : #ifdef HAVE__BUILTIN_CLZ
      58             :     Assert(word != 0);
      59             : 
      60             : #if defined(HAVE_LONG_INT_64)
      61     4473296 :     return 63 - __builtin_clzl(word);
      62             : #elif defined(HAVE_LONG_LONG_INT_64)
      63             :     return 63 - __builtin_clzll(word);
      64             : #else
      65             : #error must have a working 64-bit integer datatype
      66             : #endif
      67             : #else                           /* !HAVE__BUILTIN_CLZ */
      68             :     int         shift = 64 - 8;
      69             : 
      70             :     Assert(word != 0);
      71             : 
      72             :     while ((word >> shift) == 0)
      73             :         shift -= 8;
      74             : 
      75             :     return shift + pg_leftmost_one_pos[(word >> shift) & 255];
      76             : #endif                          /* HAVE__BUILTIN_CLZ */
      77             : }
      78             : 
      79             : /*
      80             :  * pg_rightmost_one_pos32
      81             :  *      Returns the position of the least significant set bit in "word",
      82             :  *      measured from the least significant bit.  word must not be 0.
      83             :  */
      84             : static inline int
      85           0 : pg_rightmost_one_pos32(uint32 word)
      86             : {
      87             : #ifdef HAVE__BUILTIN_CTZ
      88             :     Assert(word != 0);
      89             : 
      90           0 :     return __builtin_ctz(word);
      91             : #else
      92             :     int         result = 0;
      93             : 
      94             :     Assert(word != 0);
      95             : 
      96             :     while ((word & 255) == 0)
      97             :     {
      98             :         word >>= 8;
      99             :         result += 8;
     100             :     }
     101             :     result += pg_rightmost_one_pos[word & 255];
     102             :     return result;
     103             : #endif                          /* HAVE__BUILTIN_CTZ */
     104             : }
     105             : 
     106             : /*
     107             :  * pg_rightmost_one_pos64
     108             :  *      As above, but for a 64-bit word.
     109             :  */
     110             : static inline int
     111    16830698 : pg_rightmost_one_pos64(uint64 word)
     112             : {
     113             : #ifdef HAVE__BUILTIN_CTZ
     114             :     Assert(word != 0);
     115             : 
     116             : #if defined(HAVE_LONG_INT_64)
     117    16830698 :     return __builtin_ctzl(word);
     118             : #elif defined(HAVE_LONG_LONG_INT_64)
     119             :     return __builtin_ctzll(word);
     120             : #else
     121             : #error must have a working 64-bit integer datatype
     122             : #endif
     123             : #else                           /* !HAVE__BUILTIN_CTZ */
     124             :     int         result = 0;
     125             : 
     126             :     Assert(word != 0);
     127             : 
     128             :     while ((word & 255) == 0)
     129             :     {
     130             :         word >>= 8;
     131             :         result += 8;
     132             :     }
     133             :     result += pg_rightmost_one_pos[word & 255];
     134             :     return result;
     135             : #endif                          /* HAVE__BUILTIN_CTZ */
     136             : }
     137             : 
     138             : /*
     139             :  * pg_nextpower2_32
     140             :  *      Returns the next higher power of 2 above 'num', or 'num' if it's
     141             :  *      already a power of 2.
     142             :  *
     143             :  * 'num' mustn't be 0 or be above PG_UINT32_MAX / 2 + 1.
     144             :  */
     145             : static inline uint32
     146   139937888 : pg_nextpower2_32(uint32 num)
     147             : {
     148             :     Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);
     149             : 
     150             :     /*
     151             :      * A power 2 number has only 1 bit set.  Subtracting 1 from such a number
     152             :      * will turn on all previous bits resulting in no common bits being set
     153             :      * between num and num-1.
     154             :      */
     155   139937888 :     if ((num & (num - 1)) == 0)
     156   131403280 :         return num;             /* already power 2 */
     157             : 
     158     8534608 :     return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
     159             : }
     160             : 
     161             : /*
     162             :  * pg_nextpower2_64
     163             :  *      Returns the next higher power of 2 above 'num', or 'num' if it's
     164             :  *      already a power of 2.
     165             :  *
     166             :  * 'num' mustn't be 0 or be above PG_UINT64_MAX / 2  + 1.
     167             :  */
     168             : static inline uint64
     169       19302 : pg_nextpower2_64(uint64 num)
     170             : {
     171             :     Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);
     172             : 
     173             :     /*
     174             :      * A power 2 number has only 1 bit set.  Subtracting 1 from such a number
     175             :      * will turn on all previous bits resulting in no common bits being set
     176             :      * between num and num-1.
     177             :      */
     178       19302 :     if ((num & (num - 1)) == 0)
     179        3922 :         return num;             /* already power 2 */
     180             : 
     181       15380 :     return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
     182             : }
     183             : 
     184             : /*
     185             :  * pg_nextpower2_size_t
     186             :  *      Returns the next higher power of 2 above 'num', for a size_t input.
     187             :  */
     188             : #if SIZEOF_SIZE_T == 4
     189             : #define pg_nextpower2_size_t(num) pg_nextpower2_32(num)
     190             : #else
     191             : #define pg_nextpower2_size_t(num) pg_nextpower2_64(num)
     192             : #endif
     193             : 
     194             : /*
     195             :  * pg_prevpower2_32
     196             :  *      Returns the next lower power of 2 below 'num', or 'num' if it's
     197             :  *      already a power of 2.
     198             :  *
     199             :  * 'num' mustn't be 0.
     200             :  */
     201             : static inline uint32
     202             : pg_prevpower2_32(uint32 num)
     203             : {
     204             :     return ((uint32) 1) << pg_leftmost_one_pos32(num);
     205             : }
     206             : 
     207             : /*
     208             :  * pg_prevpower2_64
     209             :  *      Returns the next lower power of 2 below 'num', or 'num' if it's
     210             :  *      already a power of 2.
     211             :  *
     212             :  * 'num' mustn't be 0.
     213             :  */
     214             : static inline uint64
     215     1338740 : pg_prevpower2_64(uint64 num)
     216             : {
     217     1338740 :     return ((uint64) 1) << pg_leftmost_one_pos64(num);
     218             : }
     219             : 
     220             : /*
     221             :  * pg_prevpower2_size_t
     222             :  *      Returns the next lower power of 2 below 'num', for a size_t input.
     223             :  */
     224             : #if SIZEOF_SIZE_T == 4
     225             : #define pg_prevpower2_size_t(num) pg_prevpower2_32(num)
     226             : #else
     227             : #define pg_prevpower2_size_t(num) pg_prevpower2_64(num)
     228             : #endif
     229             : 
     230             : /*
     231             :  * pg_ceil_log2_32
     232             :  *      Returns equivalent of ceil(log2(num))
     233             :  */
     234             : static inline uint32
     235      451202 : pg_ceil_log2_32(uint32 num)
     236             : {
     237      451202 :     if (num < 2)
     238           0 :         return 0;
     239             :     else
     240      451202 :         return pg_leftmost_one_pos32(num - 1) + 1;
     241             : }
     242             : 
     243             : /*
     244             :  * pg_ceil_log2_64
     245             :  *      Returns equivalent of ceil(log2(num))
     246             :  */
     247             : static inline uint64
     248     1274268 : pg_ceil_log2_64(uint64 num)
     249             : {
     250     1274268 :     if (num < 2)
     251      353420 :         return 0;
     252             :     else
     253      920848 :         return pg_leftmost_one_pos64(num - 1) + 1;
     254             : }
     255             : 
     256             : /*
     257             :  * With MSVC on x86_64 builds, try using native popcnt instructions via the
     258             :  * __popcnt and __popcnt64 intrinsics.  These don't work the same as GCC's
     259             :  * __builtin_popcount* intrinsic functions as they always emit popcnt
     260             :  * instructions.
     261             :  */
     262             : #if defined(_MSC_VER) && defined(_M_AMD64)
     263             : #define HAVE_X86_64_POPCNTQ
     264             : #endif
     265             : 
     266             : /*
     267             :  * On x86_64, we can use the hardware popcount instruction, but only if
     268             :  * we can verify that the CPU supports it via the cpuid instruction.
     269             :  *
     270             :  * Otherwise, we fall back to a hand-rolled implementation.
     271             :  */
     272             : #ifdef HAVE_X86_64_POPCNTQ
     273             : #if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
     274             : #define TRY_POPCNT_FAST 1
     275             : #endif
     276             : #endif
     277             : 
     278             : #ifdef TRY_POPCNT_FAST
     279             : /* Attempt to use the POPCNT instruction, but perform a runtime check first */
     280             : extern int  (*pg_popcount32) (uint32 word);
     281             : extern int  (*pg_popcount64) (uint64 word);
     282             : 
     283             : #else
     284             : /* Use a portable implementation -- no need for a function pointer. */
     285             : extern int  pg_popcount32(uint32 word);
     286             : extern int  pg_popcount64(uint64 word);
     287             : 
     288             : #endif                          /* TRY_POPCNT_FAST */
     289             : 
     290             : /* Count the number of one-bits in a byte array */
     291             : extern uint64 pg_popcount(const char *buf, int bytes);
     292             : 
     293             : /*
     294             :  * Rotate the bits of "word" to the right by n bits.
     295             :  */
     296             : static inline uint32
     297     8372020 : pg_rotate_right32(uint32 word, int n)
     298             : {
     299     8372020 :     return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
     300             : }
     301             : 
     302             : #endif                          /* PG_BITUTILS_H */

Generated by: LCOV version 1.14