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 3 : #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 66216 : #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 251658240 : #define fd_tg_msb_idx(T) (8UL*sizeof(T)-1UL) /* Returns the index of the most significant bit for type T */
45 3 : #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 > (__typeof__((x)))0) & \
121 : !fd_tg_and( _fd_bits_x, fd_tg_sub( _fd_bits_x, (__typeof__((x)))1 ) )); \
122 : }))
123 :
124 0 : #define fd_pow2( T, b ) fd_shift_left( (T)1, (b) )
125 :
126 : #define fd_mask_bit( T, b ) fd_shift_left( (T)1, (b) )
127 : #define fd_clear_bit( x, b ) fd_tg_and( (x), fd_tg_not( fd_mask_bit( __typeof__((x)), (b) ) ) )
128 : #define fd_set_bit( x, b ) fd_tg_or ( (x), fd_mask_bit( __typeof__((x)), (b) ) )
129 : #define fd_flip_bit( x, b ) fd_tg_xor( (x), fd_mask_bit( __typeof__((x)), (b) ) )
130 251658240 : #define fd_extract_bit( x, b ) (((int)fd_shift_right( (x), (b) )) & 1)
131 : #define fd_insert_bit( x, b, y ) (__extension__({ \
132 : int _fd_bits_b = (b); \
133 : fd_tg_or( fd_clear_bit( (x), _fd_bits_b ), fd_shift_left( (__typeof__((x)))!!(y), _fd_bits_b ) ); \
134 : }))
135 :
136 33108 : #define fd_mask_lsb( T, n ) fd_tg_sub( fd_shift_left( (T)1, (n) ), (T)1 )
137 : #define fd_clear_lsb( x, n ) fd_tg_and( (x), fd_tg_not( fd_mask_lsb( __typeof__((x)), (n) ) ) )
138 : #define fd_set_lsb( x, n ) fd_tg_or ( (x), fd_mask_lsb( __typeof__((x)), (n) ) )
139 : #define fd_flip_lsb( x, n ) fd_tg_xor( (x), fd_mask_lsb( __typeof__((x)), (n) ) )
140 : #define fd_extract_lsb( x, n ) fd_tg_and( (x), fd_mask_lsb( __typeof__((x)), (n) ) )
141 : #define fd_insert_lsb( x, n, y ) fd_tg_or ( fd_clear_lsb( (x), (n) ), (y) )
142 :
143 : #define fd_mask( T, l, h ) fd_tg_sub( fd_shift_left( (T)1, (h)+1 ), fd_shift_left( (T)1, (l) ) )
144 : #define fd_clear( x, l, h ) fd_tg_and( (x), fd_tg_not( fd_mask( __typeof__((x)), (l), (h) ) ) )
145 : #define fd_set( x, l, h ) fd_tg_or( (x), fd_mask( __typeof__((x)), (l), (h) ) )
146 : #define fd_flip( x, l, h ) fd_tg_xor( (x), fd_mask( __typeof__((x)), (l), (h) ) )
147 : #define fd_extract( x, l, h ) (__extension__({ \
148 : int _fd_bits_l = (l); \
149 : fd_tg_and( fd_shift_right( (x), _fd_bits_l ), fd_mask_lsb( __typeof__((x)), (h)-_fd_bits_l+1 ) ); \
150 : }))
151 : #define fd_insert( x, l, h, y ) (__extension__({ \
152 : int _fd_bits_l = (l); \
153 : fd_tg_or( fd_clear( (x), _fd_bits_l, (h) ), fd_shift_left( (y), _fd_bits_l ) ); \
154 : }))
155 :
156 : #define fd_lsb( x ) (__extension__({ \
157 : __typeof__((x)) _fd_bits_x = (x); \
158 : fd_tg_xor( _fd_bits_x, fd_tg_and( _fd_bits_x, fd_tg_sub( _fd_bits_x, (__typeof__((x)))1 ) ) ); \
159 : }))
160 :
161 : #define fd_pop_lsb( x ) (__extension__({ \
162 : __typeof__((x)) _fd_bits_x = (x); \
163 : fd_tg_and( _fd_bits_x, fd_tg_sub( _fd_bits_x, (__typeof__((x)))1 ) ); \
164 : }))
165 :
166 : #define fd_mask_align( T, a ) fd_tg_sub( (T)(a), (T)1 )
167 : #define fd_is_aligned( x, a ) (!fd_tg_and( (x), fd_mask_align( __typeof__((x)), (a) ) ))
168 : #define fd_alignment( x, a ) fd_tg_and( (x), fd_mask_align( __typeof__((x)), (a) ) )
169 : #define fd_align_dn( x, a ) fd_tg_and( (x), fd_tg_not( fd_mask_align( __typeof__((x)), (a) ) ) )
170 : #define fd_align_up( x, a ) (__extension__({ \
171 : __typeof__((x)) _fd_bits_m = fd_mask_align( __typeof__((x)), (a) ); \
172 : fd_tg_and( fd_tg_add( (x), _fd_bits_m ), fd_tg_not( _fd_bits_m ) ); \
173 : }))
174 :
175 : #define fd_blend( m, x, y ) (__extension__({ \
176 : __typeof__((x)) _fd_bits_m = (m); \
177 : fd_tg_or( fd_tg_and( _fd_bits_m, (x) ), fd_tg_and( fd_tg_not( _fd_bits_m ), (y) ) ); \
178 : }))
179 :
180 : #define fd_if(c,x,y) (__extension__({ \
181 : __typeof__((x)) _fd_bits_x = (x), _fd_bits_y = (y); /* Note: critical to eval first and then select */ \
182 : (c) ? _fd_bits_x : _fd_bits_y; /* cmov */ \
183 : }))
184 :
185 553648128 : #define fd_store_if(c,p,x) do { \
186 553648128 : __typeof__((x)) _fd_bits_dummy[1]; \
187 553648128 : *((c) ? (p) : _fd_bits_dummy) /* cmov */ = (x); \
188 553648128 : } while(0)
189 :
190 : /* Note: fd_int_abs has a return type of uint. This allows the edge
191 : case fd_int_abs(INT_MIN) to produce value of |INT_MIN| (which is not
192 : representable in an int but is in a uint). Similarly for the other
193 : signed integer types.
194 :
195 : For the type general implementation below, the return type is the
196 : same as the input type. As a result, the edge case has
197 : fd_abs(INT_MIN) == INT_MIN. But, if we cast the result to a uint, we
198 : have the desired (uint)fd_abs(INT_MIN) == |INT_MIN|.
199 :
200 : Unfortunately, compilers don't support constructs like "unsigned
201 : __typeof__((x))" to get this to output the unsigned version of the
202 : input type in a straightforward way. It would be possible to have
203 : fd_abs produce the correct unsigned variant of the input type by
204 : using __builtin_choose_expr. Unfortunately, this will not work with
205 : the ternary type promotion rules. Until we are willing to require
206 : toolchain support for __builtin_choose_expr, we stick with fd_abs
207 : returning the same type as the input. */
208 :
209 3 : #define fd_abs( x ) (__extension__({ \
210 3 : __typeof__((x)) _fd_bits_x = (x), _fd_bits_nx = fd_tg_neg( _fd_bits_x ); \
211 3 : (fd_tg_is_unsigned_type(__typeof__((x))) | (_fd_bits_x>((__typeof__(x))0))) ? _fd_bits_x : _fd_bits_nx; \
212 3 : }))
213 :
214 0 : #define fd_min(x,y) (__extension__({ \
215 0 : __typeof__((x)) _fd_bits_x = (x), _fd_bits_y = (y); \
216 0 : _fd_bits_x <= _fd_bits_y ? _fd_bits_x : _fd_bits_y; /* cmov */ \
217 0 : }))
218 :
219 0 : #define fd_max(x,y) (__extension__({ \
220 0 : __typeof__((x)) _fd_bits_x = (x), _fd_bits_y = (y); \
221 0 : _fd_bits_x >= _fd_bits_y ? _fd_bits_x : _fd_bits_y; /* cmov */ \
222 0 : }))
223 :
224 : /* Note: this implementation assumes zero padding left shift behavior on
225 : target. */
226 :
227 0 : #define fd_shift_left(x,n) (__extension__({ \
228 0 : int _fd_bits_m = (int)fd_tg_msb_idx( __typeof__((x)) ); /* compile time */ \
229 0 : int _fd_bits_n = (n); /* compile time (mostly) */ \
230 0 : int _fd_bits_c = _fd_bits_n>_fd_bits_m; /* compile time (mostly) */ \
231 0 : (__typeof__((x)))(((x) << (_fd_bits_c ? _fd_bits_m : _fd_bits_n)) << _fd_bits_c); /* compile time (mostly) */ \
232 0 : }))
233 :
234 : /* Note: assumes zero padding unsigned / sign extending signed right
235 : shift behavior on target. */
236 :
237 251658240 : #define fd_shift_right(x,n) (__extension__({ \
238 251658240 : int _fd_bits_m = (int)fd_tg_msb_idx( __typeof__((x)) ); /* compile time */ \
239 251658240 : int _fd_bits_n = (n); /* compile time (mostly) */ \
240 251658240 : int _fd_bits_c = _fd_bits_n>_fd_bits_m; /* compile time (mostly) */ \
241 251658240 : (__typeof__((x)))(((x) >> (_fd_bits_c ? _fd_bits_m : _fd_bits_n)) >> _fd_bits_c); /* compile time (mostly) */ \
242 251658240 : }))
243 :
244 : /* Note: rotates use fd_tg_select because the implementation requires
245 : a zero padding signed right shift when operating on a signed type.
246 : If we are willing to restrict rotates to unsigned types only, these
247 : can be implemented type generic without fd_tg_select. */
248 :
249 : #define fd_rotate_left(x,n) (__extension__({ \
250 : __typeof__((x)) _fd_bits_x = (x); \
251 : int _fd_bits_n = (n); \
252 : fd_tg_select( __typeof__((x)), __typeof__((x)), \
253 : (((uchar )_fd_bits_x) << (_fd_bits_n & 7)) | (((uchar )_fd_bits_x) >> ((-_fd_bits_n) & 7)), \
254 : (((ushort )_fd_bits_x) << (_fd_bits_n & 15)) | (((ushort )_fd_bits_x) >> ((-_fd_bits_n) & 15)), \
255 : (((uint )_fd_bits_x) << (_fd_bits_n & 31)) | (((uint )_fd_bits_x) >> ((-_fd_bits_n) & 31)), \
256 : (((ulong )_fd_bits_x) << (_fd_bits_n & 63)) | (((ulong )_fd_bits_x) >> ((-_fd_bits_n) & 63)), \
257 : (((uint128)_fd_bits_x) << (_fd_bits_n & 127)) | (((uint128)_fd_bits_x) >> ((-_fd_bits_n) & 127)) ); \
258 : }))
259 :
260 : #define fd_rotate_right(x,n) (__extension__({ \
261 : __typeof__((x)) _fd_bits_x = (x); \
262 : int _fd_bits_n = (n); \
263 : fd_tg_select( __typeof__((x)), __typeof__((x)), \
264 : (((uchar )_fd_bits_x) >> (_fd_bits_n & 7)) | (((uchar )_fd_bits_x) << ((-_fd_bits_n) & 7)), \
265 : (((ushort )_fd_bits_x) >> (_fd_bits_n & 15)) | (((ushort )_fd_bits_x) << ((-_fd_bits_n) & 15)), \
266 : (((uint )_fd_bits_x) >> (_fd_bits_n & 31)) | (((uint )_fd_bits_x) << ((-_fd_bits_n) & 31)), \
267 : (((ulong )_fd_bits_x) >> (_fd_bits_n & 63)) | (((ulong )_fd_bits_x) << ((-_fd_bits_n) & 63)), \
268 : (((uint128)_fd_bits_x) >> (_fd_bits_n & 127)) | (((uint128)_fd_bits_x) << ((-_fd_bits_n) & 127)) ); \
269 : }))
270 :
271 : /* Note: we use 4UL*sizeof(T) to avoid spurious compiler warnings of
272 : shifts wider than type when popcnt is used on narrower types. */
273 :
274 : #define fd_popcnt( x ) (__extension__({ \
275 : __typeof__((x)) _fd_bits_x = (x); \
276 : fd_tg_select( __typeof__((x)), int, \
277 : __builtin_popcount ( (uint)(uchar) _fd_bits_x ), \
278 : __builtin_popcount ( (uint)(ushort)_fd_bits_x ), \
279 : __builtin_popcount ( (uint) _fd_bits_x ), \
280 : __builtin_popcountl( (ulong) _fd_bits_x ), \
281 : __builtin_popcountl( (ulong)_fd_bits_x ) + __builtin_popcountl( (ulong)(_fd_bits_x >> (4UL*sizeof(__typeof__((x)))) ) ) ); \
282 : }))
283 :
284 : #define fd_find_lsb( x ) (__extension__({ \
285 : __typeof__((x)) _fd_bits_x = (x); \
286 : fd_tg_select( __typeof__((x)), int, \
287 : fd_uchar_find_lsb ( (uchar) _fd_bits_x ), \
288 : fd_ushort_find_lsb ( (ushort) _fd_bits_x ), \
289 : fd_uint_find_lsb ( (uint) _fd_bits_x ), \
290 : fd_ulong_find_lsb ( (ulong) _fd_bits_x ), \
291 : fd_uint128_find_lsb( (uint128)_fd_bits_x ) ); \
292 : }))
293 :
294 : #define fd_find_lsb_w_default( x, d ) (__extension__({ \
295 : __typeof__((x)) _fd_bits_x = (x); \
296 : int _fd_bits_d = (d); \
297 : fd_tg_select( __typeof__((x)), int, \
298 : fd_uchar_find_lsb_w_default ( (uchar) _fd_bits_x, _fd_bits_d ), \
299 : fd_ushort_find_lsb_w_default ( (ushort) _fd_bits_x, _fd_bits_d ), \
300 : fd_uint_find_lsb_w_default ( (uint) _fd_bits_x, _fd_bits_d ), \
301 : fd_ulong_find_lsb_w_default ( (ulong) _fd_bits_x, _fd_bits_d ), \
302 : fd_uint128_find_lsb_w_default( (uint128)_fd_bits_x, _fd_bits_d ) ); \
303 : }))
304 :
305 : #define fd_find_msb( x ) (__extension__({ \
306 : __typeof__((x)) _fd_bits_x = (x); \
307 : fd_tg_select( __typeof__((x)), int, \
308 : fd_uchar_find_msb ( (uchar) _fd_bits_x ), \
309 : fd_ushort_find_msb ( (ushort) _fd_bits_x ), \
310 : fd_uint_find_msb ( (uint) _fd_bits_x ), \
311 : fd_ulong_find_msb ( (ulong) _fd_bits_x ), \
312 : fd_uint128_find_msb( (uint128)_fd_bits_x ) ); \
313 : }))
314 :
315 : #define fd_find_msb_w_default( x, d ) (__extension__({ \
316 : __typeof__((x)) _fd_bits_x = (x); \
317 : int _fd_bits_d = (d); \
318 : fd_tg_select( __typeof__((x)), int, \
319 : fd_uchar_find_msb_w_default ( (uchar) _fd_bits_x, _fd_bits_d ), \
320 : fd_ushort_find_msb_w_default ( (ushort) _fd_bits_x, _fd_bits_d ), \
321 : fd_uint_find_msb_w_default ( (uint) _fd_bits_x, _fd_bits_d ), \
322 : fd_ulong_find_msb_w_default ( (ulong) _fd_bits_x, _fd_bits_d ), \
323 : fd_uint128_find_msb_w_default( (uint128)_fd_bits_x, _fd_bits_d ) ); \
324 : }))
325 :
326 : /* Note: defaults picked to match shift trick based implementation in
327 : edge cases. FIXME: Consider using shift trick implementation anyway
328 : so that these are "const" functions (e.g. not inline asm that can't
329 : be compile time evaluated with compiler time inputs). */
330 :
331 : #define fd_pow2_dn( x ) fd_shift_left( (__typeof__((x)))1, fd_find_msb_w_default( (x), 0 ) )
332 :
333 : #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 )
334 :
335 : /* Note: we use 4UL*sizeof(T) to avoid spurious compiler warnings of
336 : shifts wider than type when bswap is used on narrower types. */
337 :
338 : #define fd_bswap( x ) (__extension__({ \
339 : __typeof__((x)) _fd_bits_x = (x); \
340 : fd_tg_select( __typeof__((x)), __typeof__((x)), \
341 : /**/ _fd_bits_x, \
342 : __builtin_bswap16( (ushort)_fd_bits_x ), \
343 : __builtin_bswap32( (uint )_fd_bits_x ), \
344 : __builtin_bswap64( (ulong )_fd_bits_x ), \
345 : (((uint128)__builtin_bswap64( (ulong)_fd_bits_x )) << 64) | \
346 : ((uint128)__builtin_bswap64( (ulong)(_fd_bits_x >> (4UL*sizeof(__typeof__((x))))) )) ); \
347 : }))
348 :
349 : /* Note: Type generic versions of fd_zz_enc/fd_zz_dec have similar
350 : signed/unsigned input -> unsigned/signed output issues as fd_abs
351 : above. Unlike fd_abs though, the distinction is more fundamental
352 : than an edge case. So either we'd force a casting (which defeats the
353 : point of making a type generic implementation) or we require
354 : toolchain support for __builtin_choose_expr. Omitting for now. */
|
