1 /* Jitter: general-purpose bitwise macro header. 2 3 Copyright (C) 2018, 2019, 2020 Luca Saiu 4 Written by Luca Saiu 5 6 This file is part of Jitter. 7 8 Jitter is free software: you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation, either version 3 of the License, or 11 (at your option) any later version. 12 13 Jitter is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with Jitter. If not, see <http://www.gnu.org/licenses/>. */ 20 21 22 #ifndef JITTER_BITWISE_H_ 23 #define JITTER_BITWISE_H_ 24 25 26 #include <limits.h> /* For CHAR_BIT . */ 27 28 #include <jitter/jitter.h> 29 30 31 /* Introduction. 32 * ************************************************************************** */ 33 34 /* This header contains some general-purpose macros for bitwise operations. */ 35 36 37 38 39 /* Powers of two. 40 * ************************************************************************** */ 41 42 /* Expand to an expression evaluating to nonzero if the given argument, assumed 43 to be nonzero, does *not* evaluate to a power of two. 44 This may evaluate the argument multiple times, but is otherwise efficient and 45 always branchless. */ 46 #define JITTER_ISNT_NONZERO_A_POWER_OF_TWO(x) \ 47 ((x) & ((x) - 1)) 48 49 /* Expand to an expression evaluating to nonzero if the given argument, assumed 50 to be nonzero, evaluates to a power of two. 51 This may evaluate the argument multiple times. */ 52 #define JITTER_IS_NONZERO_A_POWER_OF_TWO(x) \ 53 (! JITTER_ISNT_NONZERO_A_POWER_OF_TWO(x)) 54 55 /* Expand to an expression evaluating to nonzero if the given argument evaluates 56 to a power of two. 57 This may evaluate the argument multiple times. */ 58 #define JITTER_IS_A_POWER_OF_TWO(x) \ 59 (((x) != 0) && JITTER_IS_NONZERO_A_POWER_OF_TWO(x)) 60 61 /* Expand to an expression evaluating to nonzero if the given argument does 62 *not* evaluate to a power of two. 63 This may evaluate the argument multiple times. */ 64 #define JITTER_ISNT_A_POWER_OF_TWO(x) \ 65 (((x) == 0) || JITTER_ISNT_NONZERO_A_POWER_OF_TWO(x)) 66 67 /* Given a possibly integer x and a power of two p, expand to an expression 68 evaluating to the maximum integer less than or equal to x which is a multiple 69 of p. 70 The signed version relies on two's complement representation. 71 This assumes that p is a power of two and may evaluate both arguments 72 multiple times. However, if both arguments are constant expression, the 73 expansion is also a constant expression. */ 74 #define JITTER_PREVIOUS_MULTIPLE_OF_POWER_OF_TWO(x, p) \ 75 ((x) & ~ ((p) - 1)) 76 77 /* Given a possibly signed integer x and a power of two p, expand to an 78 expression evaluating to the minimum integer greater than or equal to x which 79 is a multiple of p. 80 81 This assumes that p is a power of two and may evaluate both arguments 82 multiple times. However, if both arguments are constant expression, the 83 expansion is also a constant expression. 84 85 I learned this technique from from Hacker's Delight, §3-1. 86 Let y be the smallest multiple of p greater than or equal to x, where p 87 is a power of two. Then: 88 y = (x + p - 1) & - p [1] 89 and also 90 y = x + (- x & (p - 1)) [2] 91 I am currently using [1]. [2] can be useful in other contexts, because 92 the second addend expresses a displacement from x to y. */ 93 #define JITTER_NEXT_MULTIPLE_OF_POWER_OF_TWO(x, p) \ 94 (((x) + ((p) - 1)) & ~ ((p) - 1)) 95 96 /* Given a positive integer a and a positive integer b, expand to a constant 97 expression evaluating to the smallest integer greater than or equal to a 98 which is a multiple of b. 99 This may evaluate both arguments multiple times. However, if both arguments 100 are constant expression, the expansion is also a constant expression. */ 101 #define JITTER_NEXT_MULTIPLE_OF_POSITIVE(a, b) \ 102 (((a) + (b) - 1) / (b) * (b)) 103 104 105 106 107 /* Type sizes in bits. 108 * ************************************************************************** */ 109 110 /* Given a type expand to a constant expression evaluating to the type size in 111 bits. This is useful for playing with bit masks. */ 112 #define JITTER_SIZEOF_IN_BITS(_jitter_type) \ 113 (sizeof (_jitter_type) * CHAR_BIT) 114 115 /* Jitter word size in bits. */ 116 #define JITTER_BITS_PER_WORD \ 117 JITTER_SIZEOF_IN_BITS (jitter_int) 118 119 120 121 122 /* Binary field extraction. 123 * ************************************************************************** */ 124 125 /* Expand to an expression evaluating to a field of the given word starting from 126 the given 0-based bit index until the given 0-based bit index, both ends 127 included. The 0th bit is considered to be the least significant. 128 The result is logically-right-shifted so that the least significant bit of 129 the field is the least significant bit of the result. 130 The expansion may evaluate the arguments multiple times. */ 131 #define JITTER_WORD_FIELD(word, from_bit_index, to_bit_index) \ 132 ((((uint64_t) (word)) >> (from_bit_index)) \ 133 & ((1UL << ((to_bit_index) - (from_bit_index) + 1)) - 1)) 134 135 136 137 138 /* Arithmetic right shifts. 139 * ************************************************************************** */ 140 141 /* Expand to an r-value evaluating to the given word arithmetically 142 right-shifted by _jitter_bit_nom , using the given types which must be 143 unsigned and signed integer types of the same width. 144 145 There are basically two separate implementations of this, one relying on >> 146 sign-extending on signed operands, like GCC does, and another generic but 147 slow solution. Which implementation is used depends on a constant expression 148 checking how >> behaves at compile time. I cannot think of any way of moving 149 this logic to configure, as the check would depend on run-time behavior and 150 would break under cross-compilation. 151 152 Notice that the seemingly obvious alternative of doing a signed division by 153 a power of two does not always compute the correct result with a negative 154 operand in two's complement: the rounding direction for signed division is 155 not what we need here. */ 156 #define JITTER_ARITHMETIC_SHIFT_RIGHT(_jitter_unsigned_type, \ 157 _jitter_signed_type, \ 158 _jitter_word, \ 159 _jitter_bit_no) \ 160 (JITTER_RIGHT_SHIFT_SIGN_EXTENDS (_jitter_unsigned_type, \ 161 _jitter_signed_type) \ 162 ? JITTER_ARITHMETIC_SHIFT_RIGHT_GCC (_jitter_unsigned_type, \ 163 _jitter_signed_type, \ 164 (_jitter_word), \ 165 (_jitter_bit_no)) \ 166 : JITTER_ARITHMETIC_SHIFT_RIGHT_GENERIC (_jitter_unsigned_type, \ 167 _jitter_signed_type, \ 168 (_jitter_word), \ 169 (_jitter_bit_no))) 170 171 /* Expand to a constant expression, nonzero iff >> sign-extends (at least on an 172 argument of size jitter_int , which is what we care about here). 173 This is used in the implementation of JITTER_ARITHMETIC_SHIFT_RIGHT . */ 174 #define JITTER_RIGHT_SHIFT_SIGN_EXTENDS(_jitter_unsigned_type, \ 175 _jitter_signed_type) \ 176 /* Just do on one simple test. Some ridiculous C compiler might in theory \ 177 behave in some different way than actually performing an arithmetic \ 178 shift and still give the expected result here, but I do not feel like \ 179 being overly pedantic. */ \ 180 ((((_jitter_signed_type) -56) >> 3) \ 181 == ((_jitter_signed_type) -7)) 182 183 /* One of the two implementations for JITTER_ARITHMETIC_SHIFT_RIGHT . This 184 definition is more efficient than the alternative but relies on >> 185 sign-extending on signed operands like GCC does; the C standards doesn't 186 define a behavior in this case. */ 187 #define JITTER_ARITHMETIC_SHIFT_RIGHT_GCC(_jitter_unsigned_type, \ 188 _jitter_signed_type, \ 189 _jitter_word, \ 190 _jitter_bit_no) \ 191 ((_jitter_unsigned_type) \ 192 (((_jitter_signed_type) (_jitter_word)) \ 193 >> (_jitter_bit_no))) 194 195 /* One of the two implementations for JITTER_ARITHMETIC_SHIFT_RIGHT . This 196 definition does not rely on implementation-defined behavior. */ 197 #define JITTER_ARITHMETIC_SHIFT_RIGHT_GENERIC(_jitter_unsigned_type, \ 198 _jitter_signed_type, \ 199 _jitter_word, \ 200 _jitter_bit_no) \ 201 /* The technique comes from from Hacker's Delight, §2. */ \ 202 ((_jitter_signed_type) \ 203 ((((_jitter_unsigned_type) (_jitter_word)) >> (_jitter_bit_no)) \ 204 | - (((_jitter_unsigned_type) \ 205 (((_jitter_unsigned_type) (_jitter_word)) \ 206 >> (JITTER_SIZEOF_IN_BITS (_jitter_unsigned_type) - 1))) \ 207 << (JITTER_SIZEOF_IN_BITS (_jitter_unsigned_type) - 1 \ 208 - (_jitter_bit_no))))) 209 210 211 212 213 /* Straight-line sign tests. 214 * ************************************************************************** */ 215 216 /* Expand to an expression which evalues the given word, which must have the given 217 signed type; the expansion result, of the given unsigned type, will evaluate to 218 either: 219 - the unsigned conversion of -1 (all bits set to 1), meaning true, when 220 _jitter_word is positive; 221 - the value 0, meaning false, when _jitter_word is negative. 222 223 Rationale: this is conceived to materialize a Boolean result, usually to be 224 further normalized with bitwise operations like in the macros below. 225 Of course using this macro as the conditional or guard in a test or loop in C 226 is not useful, as its entire point is to avoid branches. */ 227 #define JITTER_IS_NEGATIVE_ALL_ONES(_jitter_unsigned_type, \ 228 _jitter_signed_type, \ 229 _jitter_word) \ 230 ((_jitter_unsigned_type) \ 231 JITTER_ARITHMETIC_SHIFT_RIGHT \ 232 (_jitter_unsigned_type, \ 233 _jitter_signed_type, \ 234 (_jitter_word), \ 235 JITTER_SIZEOF_IN_BITS (_jitter_unsigned_type) - 1)) 236 237 /* Given an integer type in unsigned and singed version and three expressions 238 named discriminand, then and else, expand to an expression evaluating to 239 then if the discriminand is negative, and to else otherwise. 240 The the three expressions, which may be evaluated multiple times in the 241 expansion, must have the given type. The then and else expressions should 242 be constant expressions for good performance. 243 An important case use for this macro is a VM primitive returning a tagged 244 Boolean result, which needs to be materialized. 245 Define JITTER_CONDITIONAL_IF_NEGATIVE to use one of the two implementations 246 below. The API is identical and either implementation will work on every 247 platform, but performance may differ. On some machines (for example, 248 PowerPC) straight-line code is often a huge win; on others it is just a 249 modest improvement, and in a few cases (SH, and possibly x86_64) is 250 actually counterproductive. */ 251 #if defined (JITTER_HAVE_FAST_STRAIGHT_LINE_NEGATIVITY) 252 # define JITTER_CONDITIONAL_IF_NEGATIVE(_jitter_unsigned_type, \ 253 _jitter_signed_type, \ 254 _jitter_discriminand, \ 255 _jitter_then, \ 256 _jitter_else) \ 257 JITTER_CONDITIONAL_IF_NEGATIVE_STRAIGHT_LINE (_jitter_unsigned_type, \ 258 _jitter_signed_type, \ 259 (_jitter_discriminand), \ 260 (_jitter_then), \ 261 (_jitter_else)) 262 #else /* ! defined (JITTER_HAVE_FAST_STRAIGHT_LINE_NEGATIVITY) */ 263 # define JITTER_CONDITIONAL_IF_NEGATIVE(_jitter_unsigned_type, \ 264 _jitter_signed_type, \ 265 _jitter_discriminand, \ 266 _jitter_then, \ 267 _jitter_else) \ 268 JITTER_CONDITIONAL_IF_NEGATIVE_TRIVIAL (_jitter_unsigned_type, \ 269 _jitter_signed_type, \ 270 (_jitter_discriminand), \ 271 (_jitter_then), \ 272 (_jitter_else)) 273 #endif // #if defined (JITTER_HAVE_FAST_STRAIGHT_LINE_NEGATIVITY) 274 275 /* One of the two implementations of JITTER_CONDITIONAL_IF_NEGATIVE, in this 276 case expanding to straight-line code. 277 Implementation note: 278 The idea is rewriting 279 (discriminand < 0) ? then : else 280 to an expression of the following shape 281 (discriminand < 0) & X ^ Y 282 Now, (discriminand < 0) is either -1 or 0, as per 283 JITTER_IS_NEGATIVE_ALL_ONES; it follows that (discriminand < 0) & X will be 0 284 when discriminand >= 0. Since the result must be else when discriminand >= 0 285 we have that Y can only be else in order to have (0 ^ Y) = else. At this 286 point we can determine the right value for X: the xor operation with Y is 287 applied unconditionally, and has the effect of flipping every 1 bit from 288 else; but the only place where we can make the result be then is in X. X 289 must be such that xor-ing -1 & X with else gives then . So, X must set the 1 290 bits from then to the *opposite* configuration compared to what we aim for in 291 the result, except for the ones which will are 1 in else; the bits from then 292 will be flipped once, the ones from else will be flipped twice. 293 It is not difficult to see that the solution is: 294 * X = ~ (then ^ ~ else) 295 * Y = else . */ 296 #define JITTER_CONDITIONAL_IF_NEGATIVE_STRAIGHT_LINE(_jitter_unsigned_type, \ 297 _jitter_signed_type, \ 298 _jitter_discriminand, \ 299 _jitter_then, \ 300 _jitter_else) \ 301 ((/* This subexpression is discriminand < 0 ? -1 : 0 . */ \ 302 (_jitter_unsigned_type) \ 303 (JITTER_IS_NEGATIVE_ALL_ONES (_jitter_unsigned_type, \ 304 _jitter_signed_type, \ 305 (_jitter_discriminand))) \ 306 & (/* X = ~ (then ^ ~ else) . */ \ 307 ~ ((_jitter_unsigned_type) (_jitter_then) \ 308 ^ ~ (_jitter_unsigned_type) (_jitter_else)))) \ 309 ^ (/* Y = else . */ \ 310 (_jitter_unsigned_type) (_jitter_else))) 311 312 /* An alternative trivial implementation of JITTER_CONDITIONAL_IF_NEGATIVE , to 313 be used instead of JITTER_CONDITIONAL_IF_NEGATIVE_STRAIGHT_LINE on machines 314 where arbitrary shifts are expensive or take many instructions. */ 315 #define JITTER_CONDITIONAL_IF_NEGATIVE_TRIVIAL(_jitter_unsigned_type, \ 316 _jitter_signed_type, \ 317 _jitter_discriminand, \ 318 _jitter_then, \ 319 _jitter_else) \ 320 (((_jitter_signed_type) (_jitter_discriminand) < 0) \ 321 ? (_jitter_unsigned_type) (_jitter_then) \ 322 : (_jitter_unsigned_type) (_jitter_else)) 323 324 /* Like JITTER_CONDITIONAL_IF_NEGATIVE , but expanding to then if the 325 discriminand is non-negative. */ 326 #define JITTER_CONDITIONAL_IF_NONNEGATIVE(_jitter_unsigned_type, \ 327 _jitter_signed_type, \ 328 _jitter_discriminand, \ 329 _jitter_then, \ 330 _jitter_else) \ 331 JITTER_CONDITIONAL_IF_NEGATIVE (_jitter_unsigned_type, \ 332 _jitter_signed_type, \ 333 (_jitter_discriminand), \ 334 (_jitter_else), \ 335 (_jitter_then)) 336 337 /* Like JITTER_CONDITIONAL_IF_NEGATIVE , but expanding to then if the 338 discriminand is positive. */ 339 #define JITTER_CONDITIONAL_IF_POSITIVE(_jitter_unsigned_type, \ 340 _jitter_signed_type, \ 341 _jitter_discriminand, \ 342 _jitter_then, \ 343 _jitter_else) \ 344 /* This cannot be rewritten into a call to JITTER_CONDITIONAL_IF_NEGATIVE. \ 345 One could naïvely think of using the equivalence \ 346 d > 0 iff (- d) < 0 \ 347 , which would be correct except that the arithmetic negation overflows \ 348 when d is the most negative integer. \ 349 This alternative, more directly working on the sign bit, \ 350 d > 0 iff (~ d) < 0 \ 351 , fails when d is zero. \ 352 Hacker's Delight §2-12 "Comparison Predicates" gives formulas for x < y \ 353 which would be applicable to 0 < y, if they did both not involve an \ 354 arithmetic negation of y. \ 355 I cannot think of any clever way to optimize this. If some way exists \ 356 then it can be implemented here, in the place of this trivial version. */ \ 357 (((_jitter_signed_type) (_jitter_discriminand) > 0) \ 358 ? (_jitter_unsigned_type) (_jitter_then) \ 359 : (_jitter_unsigned_type) (_jitter_else)) 360 361 /* Like JITTER_CONDITIONAL_IF_NEGATIVE , but expanding to then if the 362 discriminand is non-positive. */ 363 #define JITTER_CONDITIONAL_IF_NONPOSITIVE(_jitter_unsigned_type, \ 364 _jitter_signed_type, \ 365 _jitter_discriminand, \ 366 _jitter_then, \ 367 _jitter_else) \ 368 JITTER_CONDITIONAL_IF_POSITIVE (_jitter_unsigned_type, \ 369 _jitter_signed_type, \ 370 (_jitter_discriminand), \ 371 (_jitter_else), \ 372 (_jitter_then)) 373 374 375 376 377 /* Pointers and misalignment. 378 * ************************************************************************** */ 379 380 /* A word-sized bitmask having 1 bits on the right, in the positions which would 381 make a pointer to a word-sized datum be misaligned. */ 382 #define JITTER_POINTER_MISALIGNMENT_BITS_MASK \ 383 ((((jitter_uint) 1) << JITTER_LG_BYTES_PER_WORD) - 1) 384 385 /* A bit mask which is just the one's complement of 386 JITTER_POINTER_MISALIGNMENT_BITS_MASK , having the low bits set to 1 instead 387 of the high bits. */ 388 #define JITTER_POINTER_NON_MISALIGNMENT_BITS_MASK \ 389 (~ JITTER_POINTER_MISALIGNMENT_BITS_MASK) 390 391 /* Given an expression evaluating to a pointer or a word-sized bitmask expand to 392 an expression evaluating to the given expression converted to a bitmask and 393 with the lowest bits masked off so as to form a correct bit configuration for 394 a pointer to an aligned word-sized datum. 395 If the argument is constant then the expansion is constant. 396 This definition is conditional and avoids actually performing the mask 397 operation if pointers are guaranteed to be always aligned by the machine 398 or the ABI. 399 See jitter/jitter-pointer-set.h for the reason why this bizarre macro is 400 in fact useful. */ 401 #if JITTER_ALIGNOF_VOID_P_P < JITTER_BYTES_PER_WORD 402 # define JITTER_UNMISALIGNED_BITMASK(_jitter_uint) \ 403 /* On this configuration there is the risk of actually having \ 404 misaligned pointers: mask off the low bits. */ \ 405 ((jitter_uint) (_jitter_uint) & \ 406 JITTER_POINTER_NON_MISALIGNMENT_BITS_MASK) 407 #else 408 # define JITTER_UNMISALIGNED_BITMASK(_jitter_uint) \ 409 /* On this configuration pointers are always aligned: do not \ 410 mask. */ \ 411 ((jitter_uint) (_jitter_uint)) 412 #endif 413 414 #endif // #ifndef JITTER_BITWISE_H_ 415