Line data Source code
1 : /* Included by fd_bits.h */
2 : /* DO NOT INCLUDE DIRECTLY */
3 :
4 : /* fd_bits_tg.h provides type generic versions of the most of the
5 : functionality in fd_bits in that they infer the type from the
6 : argument). E.g. Unless otherwise explicitly noted, fd_foo( expr )
7 : will behave functionally and linguistically identical to fd_int_foo(
8 : expr ) if expr returns an int, fd_ulong_foo( expr ) if x returns a
9 : ulong and so forth. These macros are robust and should compile to to
10 : comparably fast O(1) assembly as the type explicit equivalents. */
11 :
12 : /* fd_tg_* are implement various bit and arithmetic operators that patch
13 : over various linguistic faults. These are meant for internal use to
14 : implement the actual bits tg functionality below.
15 :
16 : These are necessary because, as ranted about elsewhere, C and C++
17 : don't _meaningfully_ have char, short, uchar and ushort types.
18 : Operations on these are dubiously silently promoted to int. There is
19 : _almost_ a reasonable historical argument for this behavior for char
20 : and short. And this argument would be valid for uchar and ushort if
21 : those were promoted to uint. But, in a fit of complete utter
22 : linguistic insanity, uchar and ushort are promoted to a _signed_ int.
23 :
24 : This is a subtle underappreciated and all too common source of
25 : security bugs, data corruption and portability issues. As an
26 : example, this can cause great surprise and many a lost weekend
27 : debugging when things like ~(ulong)0 produce the ulong value
28 : ULONG_MAX and ~(uint)0 produce the uint value UINT_MAX but ~(uchar)0
29 : produces the 32-bit signed integer value -1.
30 :
31 : This (plus the lexical irregularities introduced by dubiously
32 : treating char's sign as implementation defined), makes writing robust
33 : code much harder than it should be and makes writing robust fast
34 : portable type generic code even more obtuse. Sigh ... */
35 :
36 : #define fd_tg_neg(x) ((__typeof__((x)))-(x) ) /* -x with type of x guaranteed */
37 : #define fd_tg_add(x,y) ((__typeof__((x)))((x) + (y))) /* x + y " */
38 : #define fd_tg_sub(x,y) ((__typeof__((x)))((x) - (y))) /* x - y " */
39 : #define fd_tg_not(x) ((__typeof__((x)))~(x) ) /* ~x " */
40 : #define fd_tg_and(x,y) ((__typeof__((x)))((x) & (y))) /* x & y " */
41 : #define fd_tg_or(x,y) ((__typeof__((x)))((x) | (y))) /* x | y " */
42 : #define fd_tg_xor(x,y) ((__typeof__((x)))((x) ^ (y))) /* x ^ y " */
43 :
44 : #define fd_tg_msb_idx(T) (8UL*sizeof(T)-1UL) /* Returns the index of the most significant bit for type T */
45 : #define fd_tg_is_unsigned_type(T) (((T)-(T)1)>(T)0) /* Returns 1 if T is an unsigned type, 0 otherwise */
46 :
47 : /* fd_tg_select will emit the expression e8, e16, e32, e64, or e128
48 : as appropriate for the width the integral type Tin (Tin can be a
49 : signed or unsigned type). The output will have the type Tout. This
50 : expression is selected at compile time (hopefully). This is to brute
51 : force cases where the low level language faults are just too great to
52 : workaround with the above.
53 :
54 : Two implementations are provided. One implementation uses the
55 : (widely supported) compiler extension __builtin_choose_expr. If we
56 : don't want to use a compiler extension (e.g. portability concerns /
57 : auditing tool chain support concerns / etc), there is a second
58 : implementation based on the ternary operator.
59 :
60 : In both implementations, the compiler will parse all the expressions
61 : before it selects the matching expression. Thus all the expressions
62 : have to be valid expressions for all x but only the matching
63 : expression has to be functionally correct for a particular x. (This
64 : is an inherent limitation for the ternary implementation.
65 : Unfortunately, this limitation also exists for the builtin
66 : implementation for current compilers.)
67 :
68 : That is, while this makes it possible to write truly type generic
69 : implementations for a much broader range of cases, we still need to
70 : jump through hoops. One hoop is that we only emit the 128-bit wide
71 : expression on targets with FD_HAS_INT128.
72 :
73 : Another hoop is due to the subtle difference between the builtin and
74 : the ternary operator: the builtin gives stronger guarantees that the
75 : selection will be done at compile time and it doesn't do type
76 : promotions of the individual expressions. So we cast the expressions
77 : to Tout to keep both implementations of fd_tg_select functionally
78 : identical. */
79 :
80 : #ifndef FD_BITS_TG_USE_BUILTIN
81 : #ifdef __cplusplus
82 : #define FD_BITS_TG_USE_BUILTIN 0
83 : #else
84 : #define FD_BITS_TG_USE_BUILTIN 1
85 : #endif
86 : #endif
87 :
88 : #if FD_BITS_TG_USE_BUILTIN
89 : #if FD_HAS_INT128
90 : #define fd_tg_select(Tin,Tout,e8,e16,e32,e64,e128) __builtin_choose_expr( sizeof(Tin)==1UL, (Tout)(e8), \
91 : __builtin_choose_expr( sizeof(Tin)==2UL, (Tout)(e16), \
92 : __builtin_choose_expr( sizeof(Tin)==4UL, (Tout)(e32), \
93 : __builtin_choose_expr( sizeof(Tin)==8UL, (Tout)(e64), \
94 : (Tout)(e128) ) ) ) )
95 : #else
96 : #define fd_tg_select(Tin,Tout,e8,e16,e32,e64,e128) __builtin_choose_expr( sizeof(Tin)==1UL, (Tout)(e8), \
97 : __builtin_choose_expr( sizeof(Tin)==2UL, (Tout)(e16), \
98 : __builtin_choose_expr( sizeof(Tin)==4UL, (Tout)(e32), \
99 : (Tout)(e64) ) ) )
100 : #endif
101 : #else
102 : #if FD_HAS_INT128
103 : #define fd_tg_select(Tin,Tout,e8,e16,e32,e64,e128) ( ((sizeof(Tin)==1UL) ? (Tout)(e8) : \
104 : ((sizeof(Tin)==2UL) ? (Tout)(e16) : \
105 : ((sizeof(Tin)==4UL) ? (Tout)(e32) : \
106 : ((sizeof(Tin)==8UL) ? (Tout)(e64) : \
107 : (Tout)(e128) ) ) ) ) )
108 : #else
109 : #define fd_tg_select(Tin,Tout,e8,e16,e32,e64,e128) ( ((sizeof(Tin)==1UL) ? (Tout)(e8) : \
110 : ((sizeof(Tin)==2UL) ? (Tout)(e16) : \
111 : ((sizeof(Tin)==4UL) ? (Tout)(e32) : \
112 : (Tout)(e64) ) ) ) )
113 : #endif
114 : #endif
115 :
116 : /* Actual type generic bits implementations. */
117 :
118 : #define fd_is_pow2( x ) (__extension__({ \
119 : __typeof__((x)) _fd_bits_x = (x); \
120 : ((!!_fd_bits_x) & !fd_tg_and( _fd_bits_x, fd_tg_sub( _fd_bits_x, (__typeof__((x)))1 ) )); \
121 : }))
122 :
123 : #define fd_pow2( T, b ) fd_shift_left( (T)1, (b) )
124 :
125 : #define fd_mask_bit( T, b ) fd_shift_left( (T)1, (b) )
126 : #define fd_clear_bit( x, b ) fd_tg_and( (x), fd_tg_not( fd_mask_bit( __typeof__((x)), (b) ) ) )
127 : #define fd_set_bit( x, b ) fd_tg_or ( (x), fd_mask_bit( __typeof__((x)), (b) ) )
128 : #define fd_flip_bit( x, b ) fd_tg_xor( (x), fd_mask_bit( __typeof__((x)), (b) ) )
129 : #define fd_extract_bit( x, b ) (((int)fd_shift_right( (x), (b) )) & 1)
130 : #define fd_insert_bit( x, b, y ) (__extension__({ \
131 : int _fd_bits_b = (b); \
132 : fd_tg_or( fd_clear_bit( (x), _fd_bits_b ), fd_shift_left( (__typeof__((x)))!!(y), _fd_bits_b ) ); \
133 : }))
134 :
135 : #define fd_mask_lsb( T, n ) fd_tg_sub( fd_shift_left( (T)1, (n) ), (T)1 )
136 : #define fd_clear_lsb( x, n ) fd_tg_and( (x), fd_tg_not( fd_mask_lsb( __typeof__((x)), (n) ) ) )
137 : #define fd_set_lsb( x, n ) fd_tg_or ( (x), fd_mask_lsb( __typeof__((x)), (n) ) )
138 : #define fd_flip_lsb( x, n ) fd_tg_xor( (x), fd_mask_lsb( __typeof__((x)), (n) ) )
139 : #define fd_extract_lsb( x, n ) fd_tg_and( (x), fd_mask_lsb( __typeof__((x)), (n) ) )
140 : #define fd_insert_lsb( x, n, y ) fd_tg_or ( fd_clear_lsb( (x), (n) ), (y) )
141 :
142 : #define fd_mask( T, l, h ) fd_tg_sub( fd_shift_left( (T)1, (h)+1 ), fd_shift_left( (T)1, (l) ) )
143 : #define fd_clear( x, l, h ) fd_tg_and( (x), fd_tg_not( fd_mask( __typeof__((x)), (l), (h) ) ) )
144 : #define fd_set( x, l, h ) fd_tg_or( (x), fd_mask( __typeof__((x)), (l), (h) ) )
145 : #define fd_flip( x, l, h ) fd_tg_xor( (x), fd_mask( __typeof__((x)), (l), (h) ) )
146 : #define fd_extract( x, l, h ) (__extension__({ \
147 : int _fd_bits_l = (l); \
148 : fd_tg_and( fd_shift_right( (x), _fd_bits_l ), fd_mask_lsb( __typeof__((x)), (h)-_fd_bits_l+1 ) ); \
149 : }))
150 : #define fd_insert( x, l, h, y ) (__extension__({ \
151 : int _fd_bits_l = (l); \
152 : fd_tg_or( fd_clear( (x), _fd_bits_l, (h) ), fd_shift_left( (y), _fd_bits_l ) ); \
153 : }))
154 :
155 : #define fd_lsb( x ) (__extension__({ \
156 : __typeof__((x)) _fd_bits_x = (x); \
157 : fd_tg_xor( _fd_bits_x, fd_tg_and( _fd_bits_x, fd_tg_sub( _fd_bits_x, (__typeof__((x)))1 ) ) ); \
158 : }))
159 :
160 : #define fd_pop_lsb( x ) (__extension__({ \
161 : __typeof__((x)) _fd_bits_x = (x); \
162 : fd_tg_and( _fd_bits_x, fd_tg_sub( _fd_bits_x, (__typeof__((x)))1 ) ); \
163 : }))
164 :
165 : #define fd_mask_align( T, a ) fd_tg_sub( (T)(a), (T)1 )
166 : #define fd_is_aligned( x, a ) (!fd_tg_and( (x), fd_mask_align( __typeof__((x)), (a) ) ))
167 : #define fd_alignment( x, a ) fd_tg_and( (x), fd_mask_align( __typeof__((x)), (a) ) )
168 : #define fd_align_dn( x, a ) fd_tg_and( (x), fd_tg_not( fd_mask_align( __typeof__((x)), (a) ) ) )
169 : #define fd_align_up( x, a ) (__extension__({ \
170 : __typeof__((x)) _fd_bits_m = fd_mask_align( __typeof__((x)), (a) ); \
171 : fd_tg_and( fd_tg_add( (x), _fd_bits_m ), fd_tg_not( _fd_bits_m ) ); \
172 : }))
173 :
174 : #define fd_blend( m, x, y ) (__extension__({ \
175 : __typeof__((x)) _fd_bits_m = (m); \
176 : fd_tg_or( fd_tg_and( _fd_bits_m, (x) ), fd_tg_and( fd_tg_not( _fd_bits_m ), (y) ) ); \
177 : }))
178 :
179 : #define fd_if(c,x,y) (__extension__({ \
180 : __typeof__((x)) _fd_bits_x = (x), _fd_bits_y = (y); /* Note: critical to eval first and then select */ \
181 : (c) ? _fd_bits_x : _fd_bits_y; /* cmov */ \
182 : }))
183 :
184 : #define fd_store_if(c,p,x) do { \
185 : __typeof__((x)) _fd_bits_dummy[1]; \
186 : *((c) ? (p) : _fd_bits_dummy) /* cmov */ = (x); \
187 : } while(0)
188 :
189 : /* Note: fd_int_abs has a return type of uint. This allows the edge
190 : case fd_int_abs(INT_MIN) to produce value of |INT_MIN| (which is not
191 : representable in an int but is in a uint). Similarly for the other
192 : signed integer types.
193 :
194 : For the type general implementation below, the return type is the
195 : same as the input type. As a result, the edge case has
196 : fd_abs(INT_MIN) == INT_MIN. But, if we cast the result to a uint, we
197 : have the desired (uint)fd_abs(INT_MIN) == |INT_MIN|.
198 :
199 : Unfortunately, compilers don't support constructs like "unsigned
200 : __typeof__((x))" to get this to output the unsigned version of the
201 : input type in a straightforward way. It would be possible to have
202 : fd_abs produce the correct unsigned variant of the input type by
203 : using __builtin_choose_expr. Unfortunately, this will not work with
204 : the ternary type promotion rules. Until we are willing to require
205 : toolchain support for __builtin_choose_expr, we stick with fd_abs
206 : returning the same type as the input. */
207 :
208 : #define fd_abs( x ) (__extension__({ \
209 : __typeof__((x)) _fd_bits_x = (x), _fd_bits_nx = fd_tg_neg( _fd_bits_x ); \
210 : (fd_tg_is_unsigned_type(__typeof__((x))) | (_fd_bits_x>((__typeof__(x))0))) ? _fd_bits_x : _fd_bits_nx; \
211 : }))
212 :
213 0 : #define fd_min(x,y) (__extension__({ \
214 0 : __typeof__((x)) _fd_bits_x = (x), _fd_bits_y = (y); \
215 0 : _fd_bits_x <= _fd_bits_y ? _fd_bits_x : _fd_bits_y; /* cmov */ \
216 0 : }))
217 :
218 0 : #define fd_max(x,y) (__extension__({ \
219 0 : __typeof__((x)) _fd_bits_x = (x), _fd_bits_y = (y); \
220 0 : _fd_bits_x >= _fd_bits_y ? _fd_bits_x : _fd_bits_y; /* cmov */ \
221 0 : }))
222 :
223 : /* Note: this implementation assumes zero padding left shift behavior on
224 : target. */
225 :
226 : #define fd_shift_left(x,n) (__extension__({ \
227 : int _fd_bits_m = (int)fd_tg_msb_idx( __typeof__((x)) ); /* compile time */ \
228 : int _fd_bits_n = (n); /* compile time (mostly) */ \
229 : int _fd_bits_c = _fd_bits_n>_fd_bits_m; /* compile time (mostly) */ \
230 : (__typeof__((x)))(((x) << (_fd_bits_c ? _fd_bits_m : _fd_bits_n)) << _fd_bits_c); /* compile time (mostly) */ \
231 : }))
232 :
233 : /* Note: assumes zero padding unsigned / sign extending signed right
234 : shift behavior on target. */
235 :
236 : #define fd_shift_right(x,n) (__extension__({ \
237 : int _fd_bits_m = (int)fd_tg_msb_idx( __typeof__((x)) ); /* compile time */ \
238 : int _fd_bits_n = (n); /* compile time (mostly) */ \
239 : int _fd_bits_c = _fd_bits_n>_fd_bits_m; /* compile time (mostly) */ \
240 : (__typeof__((x)))(((x) >> (_fd_bits_c ? _fd_bits_m : _fd_bits_n)) >> _fd_bits_c); /* compile time (mostly) */ \
241 : }))
242 :
243 : /* Note: rotates use fd_tg_select because the implementation requires
244 : a zero padding signed right shift when operating on a signed type.
245 : If we are willing to restrict rotates to unsigned types only, these
246 : can be implemented type generic without fd_tg_select. */
247 :
248 : #define fd_rotate_left(x,n) (__extension__({ \
249 : __typeof__((x)) _fd_bits_x = (x); \
250 : int _fd_bits_n = (n); \
251 : fd_tg_select( __typeof__((x)), __typeof__((x)), \
252 : (((uchar )_fd_bits_x) << (_fd_bits_n & 7)) | (((uchar )_fd_bits_x) >> ((-_fd_bits_n) & 7)), \
253 : (((ushort )_fd_bits_x) << (_fd_bits_n & 15)) | (((ushort )_fd_bits_x) >> ((-_fd_bits_n) & 15)), \
254 : (((uint )_fd_bits_x) << (_fd_bits_n & 31)) | (((uint )_fd_bits_x) >> ((-_fd_bits_n) & 31)), \
255 : (((ulong )_fd_bits_x) << (_fd_bits_n & 63)) | (((ulong )_fd_bits_x) >> ((-_fd_bits_n) & 63)), \
256 : (((uint128)_fd_bits_x) << (_fd_bits_n & 127)) | (((uint128)_fd_bits_x) >> ((-_fd_bits_n) & 127)) ); \
257 : }))
258 :
259 : #define fd_rotate_right(x,n) (__extension__({ \
260 : __typeof__((x)) _fd_bits_x = (x); \
261 : int _fd_bits_n = (n); \
262 : fd_tg_select( __typeof__((x)), __typeof__((x)), \
263 : (((uchar )_fd_bits_x) >> (_fd_bits_n & 7)) | (((uchar )_fd_bits_x) << ((-_fd_bits_n) & 7)), \
264 : (((ushort )_fd_bits_x) >> (_fd_bits_n & 15)) | (((ushort )_fd_bits_x) << ((-_fd_bits_n) & 15)), \
265 : (((uint )_fd_bits_x) >> (_fd_bits_n & 31)) | (((uint )_fd_bits_x) << ((-_fd_bits_n) & 31)), \
266 : (((ulong )_fd_bits_x) >> (_fd_bits_n & 63)) | (((ulong )_fd_bits_x) << ((-_fd_bits_n) & 63)), \
267 : (((uint128)_fd_bits_x) >> (_fd_bits_n & 127)) | (((uint128)_fd_bits_x) << ((-_fd_bits_n) & 127)) ); \
268 : }))
269 :
270 : /* Note: we use 4UL*sizeof(T) to avoid spurious compiler warnings of
271 : shifts wider than type when popcnt is used on narrower types. */
272 :
273 : #define fd_popcnt( x ) (__extension__({ \
274 : __typeof__((x)) _fd_bits_x = (x); \
275 : fd_tg_select( __typeof__((x)), int, \
276 : __builtin_popcount ( (uint)(uchar) _fd_bits_x ), \
277 : __builtin_popcount ( (uint)(ushort)_fd_bits_x ), \
278 : __builtin_popcount ( (uint) _fd_bits_x ), \
279 : __builtin_popcountl( (ulong) _fd_bits_x ), \
280 : __builtin_popcountl( (ulong)_fd_bits_x ) + __builtin_popcountl( (ulong)(_fd_bits_x >> (4UL*sizeof(__typeof__((x)))) ) ) ); \
281 : }))
282 :
283 : #define fd_find_lsb( x ) (__extension__({ \
284 : __typeof__((x)) _fd_bits_x = (x); \
285 : fd_tg_select( __typeof__((x)), int, \
286 : fd_uchar_find_lsb ( (uchar) _fd_bits_x ), \
287 : fd_ushort_find_lsb ( (ushort) _fd_bits_x ), \
288 : fd_uint_find_lsb ( (uint) _fd_bits_x ), \
289 : fd_ulong_find_lsb ( (ulong) _fd_bits_x ), \
290 : fd_uint128_find_lsb( (uint128)_fd_bits_x ) ); \
291 : }))
292 :
293 : #define fd_find_lsb_w_default( x, d ) (__extension__({ \
294 : __typeof__((x)) _fd_bits_x = (x); \
295 : int _fd_bits_d = (d); \
296 : fd_tg_select( __typeof__((x)), int, \
297 : fd_uchar_find_lsb_w_default ( (uchar) _fd_bits_x, _fd_bits_d ), \
298 : fd_ushort_find_lsb_w_default ( (ushort) _fd_bits_x, _fd_bits_d ), \
299 : fd_uint_find_lsb_w_default ( (uint) _fd_bits_x, _fd_bits_d ), \
300 : fd_ulong_find_lsb_w_default ( (ulong) _fd_bits_x, _fd_bits_d ), \
301 : fd_uint128_find_lsb_w_default( (uint128)_fd_bits_x, _fd_bits_d ) ); \
302 : }))
303 :
304 : #define fd_find_msb( x ) (__extension__({ \
305 : __typeof__((x)) _fd_bits_x = (x); \
306 : fd_tg_select( __typeof__((x)), int, \
307 : fd_uchar_find_msb ( (uchar) _fd_bits_x ), \
308 : fd_ushort_find_msb ( (ushort) _fd_bits_x ), \
309 : fd_uint_find_msb ( (uint) _fd_bits_x ), \
310 : fd_ulong_find_msb ( (ulong) _fd_bits_x ), \
311 : fd_uint128_find_msb( (uint128)_fd_bits_x ) ); \
312 : }))
313 :
314 : #define fd_find_msb_w_default( x, d ) (__extension__({ \
315 : __typeof__((x)) _fd_bits_x = (x); \
316 : int _fd_bits_d = (d); \
317 : fd_tg_select( __typeof__((x)), int, \
318 : fd_uchar_find_msb_w_default ( (uchar) _fd_bits_x, _fd_bits_d ), \
319 : fd_ushort_find_msb_w_default ( (ushort) _fd_bits_x, _fd_bits_d ), \
320 : fd_uint_find_msb_w_default ( (uint) _fd_bits_x, _fd_bits_d ), \
321 : fd_ulong_find_msb_w_default ( (ulong) _fd_bits_x, _fd_bits_d ), \
322 : fd_uint128_find_msb_w_default( (uint128)_fd_bits_x, _fd_bits_d ) ); \
323 : }))
324 :
325 : /* Note: defaults picked to match shift trick based implementation in
326 : edge cases. FIXME: Consider using shift trick implementation anyway
327 : so that these are "const" functions (e.g. not inline asm that can't
328 : be compile time evaluated with compiler time inputs). */
329 :
330 : #define fd_pow2_dn( x ) fd_shift_left( (__typeof__((x)))1, fd_find_msb_w_default( (x), 0 ) )
331 :
332 : #define fd_pow2_up( x ) fd_shift_left( (__typeof__((x)))1, fd_find_msb_w_default( fd_tg_sub( (x), (__typeof__((x)))1 ), -1 ) + 1 )
333 :
334 : /* Note: we use 4UL*sizeof(T) to avoid spurious compiler warnings of
335 : shifts wider than type when bswap is used on narrower types. */
336 :
337 : #define fd_bswap( x ) (__extension__({ \
338 : __typeof__((x)) _fd_bits_x = (x); \
339 : fd_tg_select( __typeof__((x)), __typeof__((x)), \
340 : /**/ _fd_bits_x, \
341 : __builtin_bswap16( (ushort)_fd_bits_x ), \
342 : __builtin_bswap32( (uint )_fd_bits_x ), \
343 : __builtin_bswap64( (ulong )_fd_bits_x ), \
344 : (((uint128)__builtin_bswap64( (ulong)_fd_bits_x )) << 64) | \
345 : ((uint128)__builtin_bswap64( (ulong)(_fd_bits_x >> (4UL*sizeof(__typeof__((x))))) )) ); \
346 : }))
347 :
348 : /* Note: Type generic versions of fd_zz_enc/fd_zz_dec have similar
349 : signed/unsigned input -> unsigned/signed output issues as fd_abs
350 : above. Unlike fd_abs though, the distinction is more fundamental
351 : than an edge case. So either we'd force a casting (which defeats the
352 : point of making a type generic implementation) or we require
353 : toolchain support for __builtin_choose_expr. Omitting for now. */
|
