1/* @title: Bit Manipulation & Integer Powers of Two */
2#pragma once
3#include <compiler/core.h>
4#include <compiler/intrinsic.h>
5#include <compiler/wrapper.h>
6#include <enforce.h>
7#include <math/bit_api_internal.h>
8#include <stdbool.h>
9#include <stddef.h>
10#include <stdint.h>
11
12/* Must be a plain expression, not a statement,
13 * due to use in enums and whatnot */
14#define BIT(n) (1ull << (n))
15#define BITS_PER_BYTE (8)
16#define BIT_SIZEOF(t) (sizeof(t) * BITS_PER_BYTE)
17#define BIT_OFFSETOF(s, m) (offsetof(s, m) * BITS_PER_BYTE)
18#define BIT_ALIGNOF(s, m) (cc_alignof(s, m) * BITS_PER_BYTE)
19
20/* Verify that we aren't going OOB at runtime */
21#define __bit_index_ok(n, bits) \
22 ((__UINTMAX_TYPE__) (__INTMAX_TYPE__) (n) < (__UINTMAX_TYPE__) (bits))
23
24#define _BIT_CAPTURE(val, n) \
25 __auto_type __bit_v = (val); \
26 __auto_type __bit_n = (n); \
27 ct_typecheck_integer_as(__bit_v, val); \
28 ct_typecheck_integer_as(__bit_n, n); \
29 (void) enforce(__bit_index_ok(__bit_n, sizeof(__bit_v) * __CHAR_BIT__))
30
31#define BIT_SET(val, n) \
32 ({ \
33 _BIT_CAPTURE(val, n); \
34 (typeof(__bit_v)) ((uint64_t) __bit_v | (UINT64_C(1) << __bit_n)); \
35 })
36
37#define BIT_CLEAR(val, n) \
38 ({ \
39 _BIT_CAPTURE(val, n); \
40 (typeof(__bit_v)) ((uint64_t) __bit_v & ~(UINT64_C(1) << __bit_n)); \
41 })
42
43#define BIT_TOGGLE(val, n) \
44 ({ \
45 _BIT_CAPTURE(val, n); \
46 (typeof(__bit_v)) ((uint64_t) __bit_v ^ (UINT64_C(1) << __bit_n)); \
47 })
48
49#define BIT_TEST(val, n) \
50 ({ \
51 _BIT_CAPTURE(val, n); \
52 (bool) (((uint64_t) __bit_v >> __bit_n) & UINT64_C(1)); \
53 })
54
55/* Inclusive bit range as a uint64_t mask,
56 * with lo and hi evaluated and checked */
57#define BIT_MASK(lo, hi) \
58 ({ \
59 __auto_type __msk_lo = (lo); \
60 __auto_type __msk_hi = (hi); \
61 ct_typecheck_integer_as(__msk_lo, lo); \
62 ct_typecheck_integer_as(__msk_hi, hi); \
63 (void) enforce(__bit_index_ok(__msk_hi, 64) && \
64 (__UINTMAX_TYPE__) (__INTMAX_TYPE__) __msk_lo <= \
65 (__UINTMAX_TYPE__) (__INTMAX_TYPE__) __msk_hi); \
66 uint32_t __msk_l = (uint32_t) __msk_lo; \
67 uint32_t __msk_h = (uint32_t) __msk_hi; \
68 (~UINT64_C(0) >> (63u - (__msk_h - __msk_l))) << __msk_l; \
69 })
70
71#define BIT_GET_FIELD(val, lo, hi) \
72 ({ \
73 __auto_type __fld_v = (val); \
74 uint32_t __fld_l = (uint32_t) (lo); \
75 uint32_t __fld_h = (uint32_t) (hi); \
76 ct_typecheck_integer_as(__fld_v, val); \
77 (void) enforce(__fld_l <= __fld_h && \
78 __fld_h < (sizeof(__fld_v) * __CHAR_BIT__)); \
79 (typeof(__fld_v)) (((uint64_t) __fld_v >> __fld_l) & \
80 (~UINT64_C(0) >> (63u - (__fld_h - __fld_l)))); \
81 })
82
83#define BIT_SET_FIELD(val, field_val, lo, hi) \
84 ({ \
85 __auto_type __fld_v = (val); \
86 uint64_t __fld_fv = (uint64_t) (field_val); \
87 uint32_t __fld_l = (uint32_t) (lo); \
88 uint32_t __fld_h = (uint32_t) (hi); \
89 ct_typecheck_integer_as(__fld_v, val); \
90 (void) enforce(__fld_l <= __fld_h && \
91 __fld_h < (sizeof(__fld_v) * __CHAR_BIT__)); \
92 uint64_t __fld_mask = (~UINT64_C(0) >> (63u - (__fld_h - __fld_l))) \
93 << __fld_l; \
94 (typeof(__fld_v)) (((uint64_t) __fld_v & ~__fld_mask) | \
95 ((__fld_fv << __fld_l) & __fld_mask)); \
96 })
97
98#define SET_FIELD(val, field_val, lo, hi) BIT_SET_FIELD(val, field_val, lo, hi)
99
100#define BIT_RANGE(val, lo, hi) BIT_GET_FIELD(val, lo, hi)
101
102#define BIT_ANY(val, mask) \
103 ({ \
104 __auto_type __any_v = (val); \
105 __auto_type __any_m = (mask); \
106 typedef ct_common_type_2(__any_v, __any_m) __any_t; \
107 ct_typecheck_widenable_to((__any_t) 0, val); \
108 ct_typecheck_widenable_to((__any_t) 0, mask); \
109 (bool) (((__any_t) __any_v & (__any_t) __any_m) != 0); \
110 })
111
112#define BIT_ALL(val, mask) \
113 ({ \
114 __auto_type __all_v = (val); \
115 __auto_type __all_m = (mask); \
116 typedef ct_common_type_2(__all_v, __all_m) __all_t; \
117 ct_typecheck_widenable_to((__all_t) 0, val); \
118 ct_typecheck_widenable_to((__all_t) 0, mask); \
119 (bool) (((__all_t) __all_v & (__all_t) __all_m) == (__all_t) __all_m); \
120 })
121
122/* Count of bits in an inclusive range */
123#define BIT_WIDTH(lo, hi) \
124 ({ \
125 uint32_t __w_l = (uint32_t) (lo); \
126 uint32_t __w_h = (uint32_t) (hi); \
127 (void) enforce(__w_l <= __w_h); \
128 ((__w_h - __w_l) + 1u); \
129 })
130
131static inline cc_constfn size_t popcount(size_t n) {
132 return (size_t) cw_popcount((unsigned long long) n);
133}
134
135static inline cc_constfn uint8_t ilog2(uint64_t x) {
136 return x == 0 ? 0 : (uint8_t) (63 - ci_clzll(x));
137}
138
139static inline cc_constfn size_t pow2(size_t n) {
140 return 1ULL << n;
141}
142
143static inline cc_constfn size_t next_pow2(size_t x) {
144 size_t p = 1;
145 if (x == 0)
146 return 1;
147 while (p < x) {
148 if (p > (SIZE_MAX >> 1))
149 return p;
150 p <<= 1;
151 }
152 return p;
153}
154
155static inline cc_constfn size_t prev_pow2(size_t x) {
156 size_t p = 1;
157 if (x == 0)
158 return 1;
159 while (p <= x) {
160 if (p > (SIZE_MAX >> 1))
161 return p;
162 p <<= 1;
163 }
164 return p >> 1;
165}
166