1 /*-------------------------------------------------------------------------
2  *
3  * pg_bitutils.h
4  *	  Miscellaneous functions for bit-wise operations.
5  *
6  *
7  * Copyright (c) 2019, 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 extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
17 extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
18 extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
19 
20 /*
21  * pg_leftmost_one_pos32
22  *		Returns the position of the most significant set bit in "word",
23  *		measured from the least significant bit.  word must not be 0.
24  */
25 static inline int
pg_leftmost_one_pos32(uint32 word)26 pg_leftmost_one_pos32(uint32 word)
27 {
28 #ifdef HAVE__BUILTIN_CLZ
29 	Assert(word != 0);
30 
31 	return 31 - __builtin_clz(word);
32 #else
33 	int			shift = 32 - 8;
34 
35 	Assert(word != 0);
36 
37 	while ((word >> shift) == 0)
38 		shift -= 8;
39 
40 	return shift + pg_leftmost_one_pos[(word >> shift) & 255];
41 #endif							/* HAVE__BUILTIN_CLZ */
42 }
43 
44 /*
45  * pg_leftmost_one_pos64
46  *		As above, but for a 64-bit word.
47  */
48 static inline int
pg_leftmost_one_pos64(uint64 word)49 pg_leftmost_one_pos64(uint64 word)
50 {
51 #ifdef HAVE__BUILTIN_CLZ
52 	Assert(word != 0);
53 
54 #if defined(HAVE_LONG_INT_64)
55 	return 63 - __builtin_clzl(word);
56 #elif defined(HAVE_LONG_LONG_INT_64)
57 	return 63 - __builtin_clzll(word);
58 #else
59 #error must have a working 64-bit integer datatype
60 #endif
61 #else							/* !HAVE__BUILTIN_CLZ */
62 	int			shift = 64 - 8;
63 
64 	Assert(word != 0);
65 
66 	while ((word >> shift) == 0)
67 		shift -= 8;
68 
69 	return shift + pg_leftmost_one_pos[(word >> shift) & 255];
70 #endif							/* HAVE__BUILTIN_CLZ */
71 }
72 
73 /*
74  * pg_rightmost_one_pos32
75  *		Returns the position of the least significant set bit in "word",
76  *		measured from the least significant bit.  word must not be 0.
77  */
78 static inline int
pg_rightmost_one_pos32(uint32 word)79 pg_rightmost_one_pos32(uint32 word)
80 {
81 #ifdef HAVE__BUILTIN_CTZ
82 	Assert(word != 0);
83 
84 	return __builtin_ctz(word);
85 #else
86 	int			result = 0;
87 
88 	Assert(word != 0);
89 
90 	while ((word & 255) == 0)
91 	{
92 		word >>= 8;
93 		result += 8;
94 	}
95 	result += pg_rightmost_one_pos[word & 255];
96 	return result;
97 #endif							/* HAVE__BUILTIN_CTZ */
98 }
99 
100 /*
101  * pg_rightmost_one_pos64
102  *		As above, but for a 64-bit word.
103  */
104 static inline int
pg_rightmost_one_pos64(uint64 word)105 pg_rightmost_one_pos64(uint64 word)
106 {
107 #ifdef HAVE__BUILTIN_CTZ
108 	Assert(word != 0);
109 
110 #if defined(HAVE_LONG_INT_64)
111 	return __builtin_ctzl(word);
112 #elif defined(HAVE_LONG_LONG_INT_64)
113 	return __builtin_ctzll(word);
114 #else
115 #error must have a working 64-bit integer datatype
116 #endif
117 #else							/* !HAVE__BUILTIN_CTZ */
118 	int			result = 0;
119 
120 	Assert(word != 0);
121 
122 	while ((word & 255) == 0)
123 	{
124 		word >>= 8;
125 		result += 8;
126 	}
127 	result += pg_rightmost_one_pos[word & 255];
128 	return result;
129 #endif							/* HAVE__BUILTIN_CTZ */
130 }
131 
132 /* Count the number of one-bits in a uint32 or uint64 */
133 extern int	(*pg_popcount32) (uint32 word);
134 extern int	(*pg_popcount64) (uint64 word);
135 
136 /* Count the number of one-bits in a byte array */
137 extern uint64 pg_popcount(const char *buf, int bytes);
138 
139 /*
140  * Rotate the bits of "word" to the right by n bits.
141  */
142 static inline uint32
pg_rotate_right32(uint32 word,int n)143 pg_rotate_right32(uint32 word, int n)
144 {
145 	return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
146 }
147 
148 #endif							/* PG_BITUTILS_H */
149