summaryrefslogtreecommitdiffstats
path: root/src/bit.h
blob: c469305978bdcbfd185c9bc29ab3b982d912c807 (plain)
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
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
// Copyright © Tavian Barnes <tavianator@tavianator.com>
// SPDX-License-Identifier: 0BSD

/**
 * Bits & bytes.
 */

#ifndef BFS_BIT_H
#define BFS_BIT_H

#include "config.h"
#include <limits.h>
#include <stdint.h>

#if __STDC_VERSION__ >= C23
#  include <stdbit.h>
#endif

// C23 polyfill: _WIDTH macros

// The U*_MAX macros are of the form 2**n - 1, and we want to extract the n.
// One way would be *_WIDTH = popcount(*_MAX).  Alternatively, we can use
// Hallvard B. Furuseth's technique from [1], which is shorter.
//
// [1]: https://groups.google.com/g/comp.lang.c/c/NfedEFBFJ0k

// Let mask be of the form 2**m - 1, e.g. 0b111, and let n range over
// [0b0, 0b1, 0b11, 0b111, 0b1111, ...].  Then we have
//
//     n % 0b111
//         == [0b0, 0b1, 0b11, 0b0, 0b1, 0b11, ...]
//     n / (n % 0b111 + 1)
//         == [0b0 (x3), 0b111 (x3), 0b111111 (x3), ...]
//     n / (n % 0b111 + 1) / 0b111
//         == [0b0 (x3), 0b1 (x3), 0b1001 (x3), 0b1001001 (x3), ...]
//     n / (n % 0b111 + 1) / 0b111 % 0b111
//         == [0 (x3), 1 (x3), 2 (x3), ...]
//         == UMAX_CHUNK(n, 0b111)
#define UMAX_CHUNK(n, mask) (n / (n % mask + 1) / mask % mask)

// 8 * UMAX_CHUNK(n, 255) gives [0 (x8), 8 (x8), 16 (x8), ...].  To that we add
// [0, 1, 2, ..., 6, 7, 0, 1, ...], which we get from a linear interpolation on
// n % 255:
//
//     n % 255
//         == [0, 1, 3, 7, 15, 31, 63, 127, 0, ...]
//     86 / (n % 255 + 12)
//         == [7, 6, 5, 4, 3, 2, 1, 0, 7, ...]
#define UMAX_INTERP(n) (7 - 86 / (n % 255 + 12))

#define UMAX_WIDTH(n) (8 * UMAX_CHUNK(n, 255) + UMAX_INTERP(n))

#ifndef CHAR_WIDTH
#  define CHAR_WIDTH CHAR_BIT
#endif

// See https://gcc.gnu.org/onlinedocs/cpp/Common-Predefined-Macros.html

#ifndef USHRT_WIDTH
#  ifdef __SHRT_WIDTH__
#    define USHRT_WIDTH __SHRT_WIDTH__
#  else
#    define USHRT_WIDTH UMAX_WIDTH(USHRT_MAX)
#  endif
#endif

#ifndef UINT_WIDTH
#  ifdef __INT_WIDTH__
#    define UINT_WIDTH __INT_WIDTH__
#  else
#    define UINT_WIDTH UMAX_WIDTH(UINT_MAX)
#  endif
#endif

#ifndef ULONG_WIDTH
#  ifdef __LONG_WIDTH__
#    define ULONG_WIDTH __LONG_WIDTH__
#  else
#    define ULONG_WIDTH UMAX_WIDTH(ULONG_MAX)
#  endif
#endif

#ifndef ULLONG_WIDTH
#  ifdef __LONG_LONG_WIDTH__
#    define ULLONG_WIDTH __LONG_LONG_WIDTH__
#  elif defined(__LLONG_WIDTH__) // Clang
#    define ULLONG_WIDTH __LLONG_WIDTH__
#  else
#    define ULLONG_WIDTH UMAX_WIDTH(ULLONG_MAX)
#  endif
#endif

#ifndef SIZE_WIDTH
#  ifdef __SIZE_WIDTH__
#    define SIZE_WIDTH __SIZE_WIDTH__
#  else
#    define SIZE_WIDTH UMAX_WIDTH(SIZE_MAX)
#  endif
#endif

#ifndef PTRDIFF_WIDTH
#  ifdef __PTRDIFF_WIDTH__
#    define PTRDIFF_WIDTH __PTRDIFF_WIDTH__
#  else
#    define PTRDIFF_WIDTH UMAX_WIDTH(PTRDIFF_MAX)
#  endif
#endif

#ifndef UINTPTR_WIDTH
#  ifdef __INTPTR_WIDTH__
#    define UINTPTR_WIDTH __INTPTR_WIDTH__
#  else
#    define UINTPTR_WIDTH UMAX_WIDTH(UINTPTR_MAX)
#  endif
#endif

#ifndef UINTMAX_WIDTH
#  ifdef __INTMAX_WIDTH__
#    define UINTMAX_WIDTH __INTMAX_WIDTH__
#  else
#    define UINTMAX_WIDTH UMAX_WIDTH(UINTMAX_MAX)
#  endif
#endif

#ifndef UCHAR_WIDTH
#  define UCHAR_WIDTH CHAR_WIDTH
#endif
#ifndef SCHAR_WIDTH
#  define SCHAR_WIDTH CHAR_WIDTH
#endif
#ifndef SHRT_WIDTH
#  define SHRT_WIDTH USHRT_WIDTH
#endif
#ifndef INT_WIDTH
#  define INT_WIDTH UINT_WIDTH
#endif
#ifndef LONG_WIDTH
#  define LONG_WIDTH ULONG_WIDTH
#endif
#ifndef LLONG_WIDTH
#  define LLONG_WIDTH ULLONG_WIDTH
#endif
#ifndef INTPTR_WIDTH
#  define INTPTR_WIDTH UINTPTR_WIDTH
#endif
#ifndef INTMAX_WIDTH
#  define INTMAX_WIDTH UINTMAX_WIDTH
#endif

// C23 polyfill: byte order

#ifdef __STDC_ENDIAN_LITTLE__
#  define ENDIAN_LITTLE __STDC_ENDIAN_LITTLE__
#elif defined(__ORDER_LITTLE_ENDIAN__)
#  define ENDIAN_LITTLE __ORDER_LITTLE_ENDIAN__
#else
#  define ENDIAN_LITTLE 1234
#endif

#ifdef __STDC_ENDIAN_BIG__
#  define ENDIAN_BIG __STDC_ENDIAN_BIG__
#elif defined(__ORDER_BIG_ENDIAN__)
#  define ENDIAN_BIG __ORDER_BIG_ENDIAN__
#else
#  define ENDIAN_BIG 4321
#endif

#ifdef __STDC_ENDIAN_NATIVE__
#  define ENDIAN_NATIVE __STDC_ENDIAN_NATIVE__
#elif defined(__ORDER_NATIVE_ENDIAN__)
#  define ENDIAN_NATIVE __ORDER_NATIVE_ENDIAN__
#else
#  define ENDIAN_NATIVE 0
#endif

#if __STDC_VERSION__ >= C23
#  define bswap_u16 stdc_memreverse8u16
#  define bswap_u32 stdc_memreverse8u32
#  define bswap_u64 stdc_memreverse8u64
#elif __GNUC__
#  define bswap_u16 __builtin_bswap16
#  define bswap_u32 __builtin_bswap32
#  define bswap_u64 __builtin_bswap64
#else

static inline uint16_t bswap_u16(uint16_t n) {
	return (n << 8) | (n >> 8);
}

static inline uint32_t bswap_u32(uint32_t n) {
	return ((uint32_t)bswap_u16(n) << 16) | bswap_u16(n >> 16);
}

static inline uint64_t bswap_u64(uint64_t n) {
	return ((uint64_t)bswap_u32(n) << 32) | bswap_u32(n >> 32);
}

#endif

static inline uint8_t bswap_u8(uint8_t n) {
	return n;
}

/**
 * Reverse the byte order of an integer.
 */
#define bswap(n) \
	_Generic((n), \
		uint8_t: bswap_u8, \
		uint16_t: bswap_u16, \
		uint32_t: bswap_u32, \
		uint64_t: bswap_u64)(n)

// Define an overload for each unsigned type
#define UINT_OVERLOADS(macro) \
	macro(unsigned char, _uc, UCHAR_WIDTH) \
	macro(unsigned short, _us, USHRT_WIDTH) \
	macro(unsigned int, _ui, UINT_WIDTH) \
	macro(unsigned long, _ul, ULONG_WIDTH) \
	macro(unsigned long long, _ull, ULLONG_WIDTH)

// Select an overload based on an unsigned integer type
#define UINT_SELECT(n, name) \
	_Generic((n), \
		char:               name##_uc, \
		signed char:        name##_uc, \
		unsigned char:      name##_uc, \
		signed short:       name##_us, \
		unsigned short:     name##_us, \
		signed int:         name##_ui, \
		unsigned int:       name##_ui, \
		signed long:        name##_ul, \
		unsigned long:      name##_ul, \
		signed long long:   name##_ull, \
		unsigned long long: name##_ull)

// C23 polyfill: bit utilities

#if __STDC_VERSION__ >= C23
#  define count_ones stdc_count_ones
#  define count_zeros stdc_count_zeros
#  define rotate_left stdc_rotate_left
#  define rotate_right stdc_rotate_right
#  define leading_zeros stdc_leading_zeros
#  define leading_ones stdc_leading_ones
#  define trailing_zeros stdc_trailing_zeros
#  define trailing_ones stdc_trailing_ones
#  define first_leading_zero stdc_first_leading_zero
#  define first_leading_one stdc_first_leading_one
#  define first_trailing_zero stdc_first_trailing_zero
#  define first_trailing_one stdc_first_trailing_one
#  define has_single_bit stdc_has_single_bit
#  define bit_width stdc_bit_width
#  define bit_ceil stdc_bit_ceil
#  define bit_floor stdc_bit_floor
#else

#if __GNUC__

// GCC provides builtins for unsigned {int,long,long long}, so promote char/short
#define UINT_BUILTIN_uc(name) __builtin_##name
#define UINT_BUILTIN_us(name) __builtin_##name
#define UINT_BUILTIN_ui(name) __builtin_##name
#define UINT_BUILTIN_ul(name) __builtin_##name##l
#define UINT_BUILTIN_ull(name) __builtin_##name##ll
#define UINT_BUILTIN(name, suffix) UINT_BUILTIN##suffix(name)

#define BUILTIN_WIDTH_uc UINT_WIDTH
#define BUILTIN_WIDTH_us UINT_WIDTH
#define BUILTIN_WIDTH_ui UINT_WIDTH
#define BUILTIN_WIDTH_ul ULONG_WIDTH
#define BUILTIN_WIDTH_ull ULLONG_WIDTH
#define BUILTIN_WIDTH(suffix) BUILTIN_WIDTH##suffix

#define COUNT_ONES(type, suffix, width) \
	static inline int count_ones##suffix(type n) { \
		return UINT_BUILTIN(popcount, suffix)(n); \
	}

#define LEADING_ZEROS(type, suffix, width) \
	static inline int leading_zeros##suffix(type n) { \
	        return n \
			? UINT_BUILTIN(clz, suffix)(n) - (BUILTIN_WIDTH(suffix) - width) \
			: width; \
	}

#define TRAILING_ZEROS(type, suffix, width) \
	static inline int trailing_zeros##suffix(type n) { \
		return n ? UINT_BUILTIN(ctz, suffix)(n) : (int)width; \
	}

#define FIRST_TRAILING_ONE(type, suffix, width) \
	static inline int first_trailing_one##suffix(type n) { \
		return UINT_BUILTIN(ffs, suffix)(n); \
	}

#else // !__GNUC__

#define COUNT_ONES(type, suffix, width) \
	static inline int count_ones##suffix(type n) { \
		int ret; \
		for (ret = 0; n; ++ret) { \
			n &= n - 1; \
		} \
		return ret; \
	}

#define LEADING_ZEROS(type, suffix, width) \
	static inline int leading_zeros##suffix(type n) { \
		type bit = (type)1 << (width - 1); \
		int ret; \
		for (ret = 0; bit && !(n & bit); ++ret, bit >>= 1); \
		return ret; \
	}

#define TRAILING_ZEROS(type, suffix, width) \
	static inline int trailing_zeros##suffix(type n) { \
		type bit = 1; \
		int ret; \
		for (ret = 0; bit && !(n & bit); ++ret, bit <<= 1); \
		return ret; \
	}

#define FIRST_TRAILING_ONE(type, suffix, width) \
	static inline int first_trailing_one##suffix(type n) { \
		return n ? trailing_zeros##suffix(n) + 1 : 0; \
	}

#endif // !__GNUC__

UINT_OVERLOADS(COUNT_ONES)
UINT_OVERLOADS(LEADING_ZEROS)
UINT_OVERLOADS(TRAILING_ZEROS)
UINT_OVERLOADS(FIRST_TRAILING_ONE)

#define ROTATE_LEFT(type, suffix, width) \
	static inline type rotate_left##suffix(type n, int c) { \
		return (n << c) | (n >> ((width - c) % width)); \
	}

#define ROTATE_RIGHT(type, suffix, width) \
	static inline type rotate_right##suffix(type n, int c) { \
		return (n >> c) | (n << ((width - c) % width)); \
	}

#define FIRST_LEADING_ONE(type, suffix, width) \
	static inline int first_leading_one##suffix(type n) { \
		return width - leading_zeros##suffix(n); \
	}

#define HAS_SINGLE_BIT(type, suffix, width) \
	static inline bool has_single_bit##suffix(type n) { \
		/** Branchless n && !(n & (n - 1)) */ \
		return n - 1 < (n ^ (n - 1)); \
	}

UINT_OVERLOADS(ROTATE_LEFT)
UINT_OVERLOADS(ROTATE_RIGHT)
UINT_OVERLOADS(FIRST_LEADING_ONE)
UINT_OVERLOADS(HAS_SINGLE_BIT)

#define count_ones(n) UINT_SELECT(n, count_ones)(n)
#define count_zeros(n) UINT_SELECT(n, count_ones)(~(n))

#define rotate_left(n, c) UINT_SELECT(n, rotate_left)(n, c)
#define rotate_right(n, c) UINT_SELECT(n, rotate_right)(n, c)

#define leading_zeros(n) UINT_SELECT(n, leading_zeros)(n)
#define leading_ones(n) UINT_SELECT(n, leading_zeros)(~(n))

#define trailing_zeros(n) UINT_SELECT(n, trailing_zeros)(n)
#define trailing_ones(n) UINT_SELECT(n, trailing_zeros)(~(n))

#define first_leading_one(n) UINT_SELECT(n, first_leading_one)(n)
#define first_leading_zero(n) UINT_SELECT(n, first_leading_one)(~(n))

#define first_trailing_one(n) UINT_SELECT(n, first_trailing_one)(n)
#define first_trailing_zero(n) UINT_SELECT(n, first_trailing_one)(~(n))

#define has_single_bit(n) UINT_SELECT(n, has_single_bit)(n)

#define BIT_FLOOR(type, suffix, width) \
	static inline type bit_floor##suffix(type n) { \
		return n ? (type)1 << (first_leading_one##suffix(n) - 1) : 0; \
	}

#define BIT_CEIL(type, suffix, width) \
	static inline type bit_ceil##suffix(type n) { \
		return (type)1 << first_leading_one##suffix(n - !!n); \
	}

UINT_OVERLOADS(BIT_FLOOR)
UINT_OVERLOADS(BIT_CEIL)

#define bit_width(n) first_leading_one(n)
#define bit_floor(n) UINT_SELECT(n, bit_floor)(n)
#define bit_ceil(n) UINT_SELECT(n, bit_ceil)(n)

#endif // __STDC_VERSION__ < C23

#endif // BFS_BIT_H