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
16extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
17extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
18extern 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 */
25static inline int
26pg_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 */
48static inline int
49pg_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 */
78static inline int
79pg_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 */
104static inline int
105pg_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 */
133extern int (*pg_popcount32) (uint32 word);
134extern int (*pg_popcount64) (uint64 word);
135
136/* Count the number of one-bits in a byte array */
137extern uint64 pg_popcount(const char *buf, int bytes);
138
139#endif /* PG_BITUTILS_H */
140