1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
#ifndef BITS_H
#define BITS_H
#define UINT64_SUM_OVERFLOWS(a, b) \
(a > (uint64_t)-1 - b)
#define BIT(n) (1u << (n))
/* These expressions make it easy to ensure that bit test expressions
are boolean in order to satisfy the in-house -Wstrict-bool. */
/* ((val & bits) == 0) is very common */
#define HAS_NO_BITS(val,bits) (((val) & (bits)) == 0)
/* ((val & bits) != 0) is even more common */
/* Note - illogical behaviour if bits==0, fixing that requires potential
multiple evaluation, but it's a corner case that should never occur. */
#define HAS_ANY_BITS(val,bits) (((val) & (bits)) != 0)
/* ((val & bits) == bits) is uncommon */
#define HAS_ALL_BITS(val,bits) ((~(val) & (bits)) == 0)
/* negation implemented without using the subtraction operator
~(x - 1) = 1 + ~x these are equivalent by -(-x) == ~(~(x)) == x */
#define UNSIGNED_MINUS(x) (1 + ~(x))
/* Returns x, such that x is the smallest power of 2 >= num. */
size_t nearest_power(size_t num) ATTR_CONST;
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
/* Returns TRUE if 2^x=num, i.e. if num has only a single bit set to 1. */
static inline bool ATTR_CONST
bits_is_power_of_two(uint64_t num)
{
return __builtin_popcountll(num) == 1;
}
static inline unsigned int ATTR_CONST
bits_required32(uint32_t num)
{
return num == 0 ? 0 : 32 - __builtin_clz(num);
}
static inline unsigned int ATTR_CONST
bits_required8(uint8_t num) { return bits_required32(num); }
static inline unsigned int ATTR_CONST
bits_required16(uint16_t num) { return bits_required32(num); }
static inline unsigned int ATTR_CONST
bits_required64(uint64_t num)
{
return num == 0 ? 0 : 64 - __builtin_clzll(num);
}
#else
/* Returns TRUE if 2^x=num, i.e. if num has only a single bit set to 1. */
static inline bool ATTR_CONST
bits_is_power_of_two(uint64_t num)
{
return num != 0 && (num & (num + ~0ULL)) == 0;
}
unsigned int bits_required8(uint8_t num) ATTR_CONST;
static inline
unsigned int bits_required16(uint16_t num)
{
return (num <= 0xff) ? bits_required8(num)
: 8 + bits_required8(num >> 8);
}
static inline
unsigned int bits_required32(uint32_t num)
{
return (num <= 0xffff) ? bits_required16(num)
: 16 + bits_required16(num >> 16);
}
static inline
unsigned int bits_required64(uint64_t num)
{
return (num <= 0xffffffff) ? bits_required32(num)
: 32 + bits_required32(num >> 32);
}
#endif
static inline uint64_t ATTR_NO_SANITIZE_INTEGER
ATTR_NO_SANITIZE_IMPLICIT_CONVERSION
bits_rotl64(uint64_t num, unsigned int count)
{
const unsigned int mask = CHAR_BIT*sizeof(num) - 1;
count &= mask;
return (num << count) | (num >> (UNSIGNED_MINUS(count) & mask));
}
static inline uint32_t ATTR_NO_SANITIZE_INTEGER
ATTR_NO_SANITIZE_IMPLICIT_CONVERSION
bits_rotl32(uint32_t num, unsigned int count)
{
const unsigned int mask = CHAR_BIT*sizeof(num) - 1;
count &= mask;
return (num << count) | (num >> (UNSIGNED_MINUS(count) & mask));
}
static inline uint64_t ATTR_NO_SANITIZE_INTEGER
ATTR_NO_SANITIZE_IMPLICIT_CONVERSION
bits_rotr64(uint64_t num, unsigned int count)
{
const unsigned int mask = CHAR_BIT*sizeof(num) - 1;
count &= mask;
return (num >> count) | (num << (UNSIGNED_MINUS(count) & mask));
}
static inline uint32_t ATTR_NO_SANITIZE_INTEGER
ATTR_NO_SANITIZE_IMPLICIT_CONVERSION
bits_rotr32(uint32_t num, unsigned int count)
{
const unsigned int mask = CHAR_BIT*sizeof(num) - 1;
count &= mask;
return (num >> count) | (num << (UNSIGNED_MINUS(count) & mask));
}
/* These functions look too big to be inline, but in almost all expected
uses, 'fracbits' will be a compile-time constant, and most of the
expressions will simplify greatly.
*/
/* Perform a piecewise-linear approximation to a log2, with fracbits "fractional" bits.
Best explained with examples:
With 2 fractional bits splitting each power of 2 into 4 bands:
00, 01, 10, 11 -> 00, 01, 10, 11 (small corner cases)
100, 101, 110, 111 -> 100, 101, 110, 111 ([4-8) split into 4 bands)
1000, 1001, 1010, 1011 -> 1000, 1000, 1001, 1001 ([8-15) split ...
1100, 1101, 1110, 1111 -> 1010, 1010, 1011, 1011 ... into 4 bands)
[16..31) -> 11bb
[32..63) -> 100bb
[64..127) -> 101bb
[128..255) -> 110bb
e.g. 236 = 11101100 -> ((8-2)<<2 == 11000) + (111.....>> 5 == 111) - 100 == 11011
*/
static inline unsigned int ATTR_CONST
bits_fraclog(unsigned int val, unsigned int fracbits)
{
unsigned bits = bits_required32(val);
if (bits <= fracbits + 1)
return val;
unsigned int bandnum = bits - fracbits;
unsigned int bandstart = bandnum << fracbits;
unsigned int fracoffsbad = val >> (bandnum - 1); /* has leading 1 still */
unsigned int bucket = bandstart + fracoffsbad - BIT(fracbits);
return bucket;
}
static inline unsigned int ATTR_CONST
bits_fraclog_bucket_start(unsigned int bucket, unsigned int fracbits)
{
unsigned int bandnum = bucket >> fracbits;
if (bandnum <= 1)
return bucket;
if (fracbits == 0)
return BIT(bucket - 1);
unsigned int fracoffs = bucket & (BIT(fracbits)-1);
unsigned int fracoffs1 = BIT(fracbits) + fracoffs;
unsigned int bandstart = fracoffs1 << (bandnum - 1);
return bandstart;
}
static inline unsigned int ATTR_CONST ATTR_NO_SANITIZE_INTEGER
ATTR_NO_SANITIZE_IMPLICIT_CONVERSION
bits_fraclog_bucket_end(unsigned int bucket, unsigned int fracbits)
{
unsigned int bandnum = bucket >> fracbits;
if (bandnum <= 1)
return bucket;
if (fracbits == 0)
return BIT(bucket - 1) * 2 - 1;
unsigned int fracoffs = bucket & (BIT(fracbits)-1);
unsigned int nextfracoffs1 = 1 + BIT(fracbits) + fracoffs;
unsigned int nextbandstart = nextfracoffs1 << (bandnum - 1);
return nextbandstart - 1;
}
/* UNSAFE: multiple use of parameter (but expecting a constant in reality).
But a macro as it's most likely to be used to declare an array size.
*/
#define BITS_FRACLOG_BUCKETS(bits) ((33u - (bits)) << (bits))
#endif
|
