LCOV - code coverage report
Current view: top level - src/include/port - pg_bitutils.h (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 23 24 95.8 %
Date: 2020-06-01 09:07:10 Functions: 8 8 100.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-2020, 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    10585228 : pg_leftmost_one_pos32(uint32 word)
      33             : {
      34             : #ifdef HAVE__BUILTIN_CLZ
      35             :     Assert(word != 0);
      36             : 
      37    10585228 :     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     1970082 : 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     1970082 :     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             : pg_rightmost_one_pos32(uint32 word)
      86             : {
      87             : #ifdef HAVE__BUILTIN_CTZ
      88             :     Assert(word != 0);
      89             : 
      90             :     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     8003032 : 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     8003032 :     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 highest power of 2 of '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    78776270 : 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    78776270 :     if ((num & (num - 1)) == 0)
     156    74800672 :         return num;             /* already power 2 */
     157             : 
     158     3975598 :     return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
     159             : }
     160             : 
     161             : /*
     162             :  * pg_nextpower2_64
     163             :  *      Returns the next highest power of 2 of '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        8466 : 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        8466 :     if ((num & (num - 1)) == 0)
     179        1158 :         return num;             /* already power 2 */
     180             : 
     181        7308 :     return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
     182             : }
     183             : 
     184             : /*
     185             :  * pg_ceil_log2_32
     186             :  *      Returns equivalent of ceil(log2(num))
     187             :  */
     188             : static inline uint32
     189      450870 : pg_ceil_log2_32(uint32 num)
     190             : {
     191      450870 :     if (num < 2)
     192           0 :         return 0;
     193             :     else
     194      450870 :         return pg_leftmost_one_pos32(num - 1) + 1;
     195             : }
     196             : 
     197             : /*
     198             :  * pg_ceil_log2_64
     199             :  *      Returns equivalent of ceil(log2(num))
     200             :  */
     201             : static inline uint64
     202     2030642 : pg_ceil_log2_64(uint64 num)
     203             : {
     204     2030642 :     if (num < 2)
     205      239556 :         return 0;
     206             :     else
     207     1791086 :         return pg_leftmost_one_pos64(num - 1) + 1;
     208             : }
     209             : 
     210             : /* Count the number of one-bits in a uint32 or uint64 */
     211             : extern int  (*pg_popcount32) (uint32 word);
     212             : extern int  (*pg_popcount64) (uint64 word);
     213             : 
     214             : /* Count the number of one-bits in a byte array */
     215             : extern uint64 pg_popcount(const char *buf, int bytes);
     216             : 
     217             : /*
     218             :  * Rotate the bits of "word" to the right by n bits.
     219             :  */
     220             : static inline uint32
     221     8678040 : pg_rotate_right32(uint32 word, int n)
     222             : {
     223     8678040 :     return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
     224             : }
     225             : 
     226             : #endif                          /* PG_BITUTILS_H */

Generated by: LCOV version 1.13