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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
|
#ifndef TERM_COMPAT_H
#define TERM_COMPAT_H
/*
* Compiler and libc differences, kept in one place. GCC and Clang use their
* builtins. MSVC uses its intrinsics. Any other compiler, and any build with
* TERM_NO_COMPILER_BUILTINS, uses plain C. Plain C gives the same results,
* only slower.
*/
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#if defined(__GNUC__) || defined(__clang__)
#define TERM_COMPILER_GNU 1
#elif defined(_MSC_VER)
#define TERM_COMPILER_MSVC 1
#include <intrin.h>
#endif
#if !defined(TERM_NO_COMPILER_BUILTINS) && defined(TERM_COMPILER_GNU)
#define TERM_HAVE_BUILTINS 1
#elif !defined(TERM_NO_COMPILER_BUILTINS) && defined(TERM_COMPILER_MSVC)
#define TERM_HAVE_MSVC_BITOPS 1
#endif
#if defined(TERM_COMPILER_GNU)
#define TERM_HOT __attribute__((hot))
#define TERM_NOINLINE __attribute__((noinline))
#define TERM_ALWAYS_INLINE __attribute__((always_inline))
#define TERM_MAYBE_UNUSED __attribute__((unused))
#elif defined(TERM_COMPILER_MSVC)
#define TERM_HOT
#define TERM_NOINLINE __declspec(noinline)
#define TERM_ALWAYS_INLINE __forceinline
#define TERM_MAYBE_UNUSED
#else
#define TERM_HOT
#define TERM_NOINLINE
#define TERM_ALWAYS_INLINE
#define TERM_MAYBE_UNUSED
#endif
#if defined(TERM_HAVE_BUILTINS)
#define TERM_EXPECT(x, v) __builtin_expect((x), (v))
#else
#define TERM_EXPECT(x, v) (x)
#endif
/* term_ctz32(0) is 32, term_clz32(0) is 32, term_ctz64(0) is 64, and
* term_clz64(0) is 64 on every path. */
#if defined(TERM_HAVE_BUILTINS)
static inline int term_ctz32(uint32_t x) { return x ? __builtin_ctz(x) : 32; }
static inline int term_clz32(uint32_t x) { return x ? __builtin_clz(x) : 32; }
static inline int term_popcount32(uint32_t x) { return __builtin_popcount(x); }
static inline int term_ctz64(uint64_t x) { return x ? __builtin_ctzll(x) : 64; }
static inline int term_clz64(uint64_t x) { return x ? __builtin_clzll(x) : 64; }
static inline int term_popcount64(uint64_t x) { return __builtin_popcountll(x); }
#else
#if defined(TERM_HAVE_MSVC_BITOPS)
static inline int term_ctz32(uint32_t x)
{
unsigned long i;
return _BitScanForward(&i, x) ? (int)i : 32;
}
static inline int term_clz32(uint32_t x)
{
unsigned long i;
return _BitScanReverse(&i, x) ? 31 - (int)i : 32;
}
static inline int term_popcount32(uint32_t x) { return (int)__popcnt(x); }
#else
static inline int term_ctz32(uint32_t x)
{
if (!x)
return 32;
static const uint8_t de_bruijn[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
return (int)de_bruijn[((uint32_t)((x & -x) * 0x077CB531U)) >> 27];
}
static inline int term_clz32(uint32_t x)
{
if (!x)
return 32;
int n = 0;
if (!(x & 0xffff0000u)) { n += 16; x <<= 16; }
if (!(x & 0xff000000u)) { n += 8; x <<= 8; }
if (!(x & 0xf0000000u)) { n += 4; x <<= 4; }
if (!(x & 0xc0000000u)) { n += 2; x <<= 2; }
if (!(x & 0x80000000u)) { n += 1; }
return n;
}
static inline int term_popcount32(uint32_t x)
{
x = x - ((x >> 1) & 0x55555555u);
x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
return (int)((((x + (x >> 4)) & 0x0F0F0F0Fu) * 0x01010101u) >> 24);
}
#endif
/* Without builtins, the 64-bit forms are built from the 32-bit ones. */
static inline int term_ctz64(uint64_t x)
{
uint32_t lo = (uint32_t)x;
return lo ? term_ctz32(lo) : 32 + term_ctz32((uint32_t)(x >> 32));
}
static inline int term_clz64(uint64_t x)
{
uint32_t hi = (uint32_t)(x >> 32);
return hi ? term_clz32(hi) : 32 + term_clz32((uint32_t)x);
}
static inline int term_popcount64(uint64_t x)
{
return term_popcount32((uint32_t)x) + term_popcount32((uint32_t)(x >> 32));
}
#endif
/* Smallest power of two >= x, branchlessly via CLZ. Returns UINT32_MAX on overflow. */
static inline uint32_t term_next_pow2_32(uint32_t x)
{
uint32_t v = x <= 1 ? 1 : x - 1;
int lz = term_clz32(v);
uint32_t res = UINT32_C(1) << ((32 - lz) & 31);
return (x <= 1) ? 1 : (lz == 0 ? UINT32_MAX : res);
}
/* Smallest power of two >= x, branchlessly via CLZ. Returns UINT64_MAX on overflow. */
static inline uint64_t term_next_pow2_64(uint64_t x)
{
uint64_t v = x <= 1 ? 1 : x - 1;
int lz = term_clz64(v);
uint64_t res = UINT64_C(1) << ((64 - lz) & 63);
return (x <= 1) ? 1 : (lz == 0 ? UINT64_MAX : res);
}
static inline size_t term_next_pow2(size_t x)
{
#if SIZE_MAX > UINT32_MAX
return (size_t)term_next_pow2_64(x);
#else
return (size_t)term_next_pow2_32((uint32_t)x);
#endif
}
/* Grows cap by doubling until >= need, branchlessly.
* If cap >= need, returns cap. Otherwise returns next power of two >= need. */
static inline uint32_t term_grow_cap32(uint32_t cap, uint32_t need)
{
return cap >= need ? cap : term_next_pow2_32(need);
}
static inline uint64_t term_grow_cap64(uint64_t cap, uint64_t need)
{
return cap >= need ? cap : term_next_pow2_64(need);
}
static inline size_t term_grow_cap(size_t cap, size_t need)
{
#if SIZE_MAX > UINT32_MAX
return (size_t)term_grow_cap64(cap, need);
#else
return (size_t)term_grow_cap32((uint32_t)cap, (uint32_t)need);
#endif
}
/* A spin-wait hint. Compilers without one get a no-op. */
static inline void term_cpu_relax(void)
{
#if defined(TERM_COMPILER_GNU)
#if defined(TERM_HAVE_BUILTINS) && defined(__x86_64__)
__builtin_ia32_pause();
#elif defined(__aarch64__)
__asm__ __volatile__("yield");
#endif
#elif defined(TERM_COMPILER_MSVC)
#if defined(_M_X64) || defined(_M_IX86)
_mm_pause();
#elif defined(_M_ARM64)
__yield();
#endif
#endif
}
/* strdup is POSIX, so the core copies strings itself. */
static inline char *term_strdup(const char *s)
{
size_t n = strlen(s) + 1;
char *copy = malloc(n);
if (copy)
memcpy(copy, s, n);
return copy;
}
/* ASCII-only prefix test, as strncasecmp() does in the C locale. */
static inline bool term_has_prefix_ci(const char *s, const char *prefix)
{
for (; *prefix; prefix++, s++) {
unsigned char a = (unsigned char)*s;
unsigned char b = (unsigned char)*prefix;
a |= ((unsigned)(a - 'A') < 26) ? 0x20 : 0;
b |= ((unsigned)(b - 'A') < 26) ? 0x20 : 0;
if (a != b)
return false;
}
return true;
}
/* Allocates size bytes that start on an align-byte boundary. align must be a
* power of two. The raw pointer is stored just before the block, so
* term_aligned_free() can release it. C11 aligned_alloc() and POSIX
* posix_memalign() are not on every toolchain. */
static inline void *term_aligned_alloc(size_t align, size_t size)
{
if (size > SIZE_MAX - align - sizeof(void *))
return NULL;
void *raw = malloc(size + align + sizeof(void *));
if (!raw)
return NULL;
uintptr_t p = ((uintptr_t)raw + sizeof(void *) + align - 1) & ~((uintptr_t)align - 1);
((void **)p)[-1] = raw;
return (void *)p;
}
static inline void term_aligned_free(void *p)
{
if (p)
free(((void **)p)[-1]);
}
#endif
|
