1 /* Jitter: general-purpose integer arithmetic macro header. 2 3 Copyright (C) 2019, 2020, 2021 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_ARITHMETIC_H_ 23 #define JITTER_ARITHMETIC_H_ 24 25 #include <stdint.h> 26 27 #include <jitter/jitter.h> 28 #include <jitter/jitter-bitwise.h> 29 30 31 /* This header assumes two's complement arithmetic. 32 * ************************************************************************** */ 33 34 /* This all assumes two's complement arithmetic, in the meaning of the values 35 which are computed and in many cases also for the purpose of the computation 36 itself. */ 37 38 39 40 41 /* Constants related to the representation of integers. 42 * ************************************************************************** */ 43 44 /* Expand to an expression whose result is an uint64_t bitmask, holding a single 45 1 bit at the position of the sign bit and 0 elsewhere, assuming a two's 46 complement representation in the given number of bits. If the expression 47 given for the number of bit is a constant expression then the expansion is a 48 constant expression as well. The number of bits may be any natural number up 49 to 64 included. */ 50 #define JITTER_SIGN_BIT_FOR_BITS(bit_no) \ 51 ((uint64_t) 1 << ((bit_no) - 1)) 52 53 /* Expand to a constant expression, like the expansion of 54 JITTER_SIGN_BIT_FOR_BITS , for the number of bits in a Jitter word. */ 55 #define JITTER_SIGN_BIT \ 56 JITTER_SIGN_BIT_FOR_BITS (JITTER_BITS_PER_WORD) 57 58 59 60 61 /* Integer representation limits. 62 * ************************************************************************** */ 63 64 /* Expand to a constant int64_t expression whose value is the most negative 65 number representable with the given number of bits in two's complement. The 66 given number of bits must not be greater than 64. */ 67 #define JITTER_MOST_NEGATIVE_SIGNED_IN_BITS(bit_no) \ 68 ((int64_t) - (((uint64_t) 1) << ((bit_no) - 1))) 69 70 /* Expand to a constant int64_t expression whose value is the most positive 71 number representable with the given number of bits in two's complement. The 72 given number of bits must not be greater than 64. */ 73 #define JITTER_MOST_POSITIVE_SIGNED_IN_BITS(bit_no) \ 74 ((int64_t) ((((uint64_t) 1) << ((bit_no) - 1)) - 1)) 75 76 /* Expand to a constant uint64_t expression whose value is the largest number 77 representable, unsigned, with the given number of bits. The given number of 78 bits must not be greater than 64. */ 79 #define JITTER_MAXIMUM_UNSIGNED_IN_BITS(bit_no) \ 80 ((((uint64_t) 1) << (bit_no)) - 1) 81 82 /* The values of JITTER_MOST_NEGATIVE_SIGNED_IN_BITS, 83 JITTER_MOST_POSITIVE_SIGNED_IN_BITS and JITTER_MAXIMUM_UNSIGNED_IN_BITS for 84 word-sized types. */ 85 #define JITTER_MOST_NEGATIVE_SIGNED \ 86 ((jitter_int) \ 87 JITTER_MOST_NEGATIVE_SIGNED_IN_BITS (JITTER_BITS_PER_WORD)) 88 #define JITTER_MOST_POSTITIVE_SIGNED \ 89 ((jitter_int) \ 90 JITTER_MOST_POSTITIVE_SIGNED_IN_BITS (JITTER_BITS_PER_WORD)) 91 #define JITTER_MAXIMUM_UNSIGNED \ 92 ((jitter_uint) \ 93 JITTER_MAXIMUM_UNSIGNED_IN_BITS (JITTER_BITS_PER_WORD)) 94 95 /* Expand to an expression evaluating to a Boolean. The result will be 96 non-false iff the given argument, taken as a word-sized unsigned integer, 97 fits within the specified number of bits. For example 0, 4, 45 or 255 fit in 98 8 bits, but 256 does not. The number of bits does not need to be a power of 99 two and can even be greater than 63 -- in which case the result will evaluate 100 to non-false, since any given number will be exactly representable in 64 or 101 more bits. 102 The expansion will be a constant expression if the arguments are constant 103 expressions; however the arguments may be evaluated multiple times. */ 104 #define JITTER_FITS_IN_BITS_ZERO_EXTENDED(word, bit_no) \ 105 (((bit_no) >= 64) \ 106 || (((uint64_t) (word)) \ 107 <= JITTER_MAXIMUM_UNSIGNED_IN_BITS (bit_no))) 108 109 /* Like JITTER_FITS_IN_BITS_ZERO_EXTENDED, but use sign extension rather than 110 zero extension. */ 111 #define JITTER_FITS_IN_BITS_SIGN_EXTENDED(word, bit_no) \ 112 (((bit_no) >= 64) \ 113 || ((((int64_t) (uint64_t) (word)) \ 114 >= JITTER_MOST_NEGATIVE_SIGNED_IN_BITS (bit_no)) \ 115 && (((int64_t) (uint64_t) (word)) \ 116 <= JITTER_MOST_POSITIVE_SIGNED_IN_BITS (bit_no)))) 117 118 119 120 121 /* Integer division rounding up. 122 * ************************************************************************** */ 123 124 /* Given two expressions of some unsigned integer type expand to an expression 125 of the same type evaluating to the ceiling of the quotient of the arguments. 126 This may evaluate the arguments multiple times, but expands to a constant 127 expression if the arguments are constant expressions. */ 128 #define JITTER_QUOTIENT_CEILING(ua, ub) \ 129 /* Bruno Haible suggested the alternative (ua + ub - 1) / ub which is \ 130 useful in some contexts, but unfortunately can overflow. */ \ 131 ((ua) != 0 \ 132 ? (((ua) - 1) / (ub) + 1) \ 133 : 0) 134 135 136 137 138 /* Integer overflow checking. 139 * ************************************************************************** */ 140 141 /* This functionality provides ways of checking for overflow on signed integers 142 before actually attempting an operation which would result in undefined 143 behavior in C. 144 145 At this time only signed integer operations are supported. */ 146 147 /* Given a C integer type in its unsigned and signed variants, expressions a and 148 b evaluating to integers of the given signed type and a number of significant 149 bits (which a and b must fit in), expand to a Boolean expression, non-false 150 iff the sum of a and b would overflow the same given number of bits. 151 Arguments may be evaluated multiple times; bit_no should be a constant 152 expression for an efficient expansion. 153 The implementation will use GCC's overflow-checking primitives if available 154 and if supported in the given number of bits. */ 155 #ifdef JITTER_HAVE_GCC_OVERFLOW_CHECKING 156 # define JITTER_WOULD_PLUS_OVERFLOW(__jitter_unsigned_type, \ 157 __jitter_signed_type, \ 158 a, b, bit_no) \ 159 (((bit_no) == 64) \ 160 ? JITTER_WOULD_PLUS_OVERFLOW_GCC (int64_t, (a), (b)) \ 161 : (((bit_no) == 32) \ 162 ? JITTER_WOULD_PLUS_OVERFLOW_GCC (int32_t, (a), (b)) \ 163 : (((bit_no) == 16) \ 164 ? JITTER_WOULD_PLUS_OVERFLOW_GCC (int16_t, (a), (b)) \ 165 : (((bit_no) == 8) \ 166 ? JITTER_WOULD_PLUS_OVERFLOW_GCC (int8_t, (a), (b)) \ 167 : JITTER_WOULD_PLUS_OVERFLOW_NON_GCC (__jitter_unsigned_type, \ 168 __jitter_signed_type, \ 169 (a), (b), (bit_no)))))) 170 #else // The GCC builtin is not available in this configuration. 171 # define JITTER_WOULD_PLUS_OVERFLOW(__jitter_unsigned_type, \ 172 __jitter_signed_type, \ 173 a, b, bit_no) \ 174 JITTER_WOULD_PLUS_OVERFLOW_NON_GCC (__jitter_unsigned_type, \ 175 __jitter_signed_type, \ 176 (a), (b), (bit_no)) 177 #endif // #ifdef JITTER_HAVE_GCC_OVERFLOW_CHECKING 178 179 /* A halper macro in the implementation of JITTER_WOULD_PLUS_OVERFLOW for the 180 generic non-builtin case. This does not evaluate to a Boolean, but to a 181 signed word: the sum operation overflows iff the result of the expansion is 182 negative. 183 This is intended for use in a conditional fast branch checking the sign. */ 184 #define JITTER_WOULD_PLUS_OVERFLOW_SIGNED_WORD(__jitter_unsigned_type, \ 185 __jitter_signed_type, \ 186 a, b, bit_no) \ 187 /* The formula, like others below in this file, is a generalization \ 188 to an arbitrary number of bits of an idea in Hacker's Delight, \ 189 §2. */ \ 190 ((__jitter_signed_type) \ 191 (~ ((__jitter_unsigned_type) (a) \ 192 ^ (__jitter_unsigned_type) (b)) \ 193 & (((__jitter_unsigned_type) (a)) \ 194 ^ (((__jitter_unsigned_type) (a) \ 195 + (__jitter_unsigned_type) (b)))))) 196 197 /* The generic non-builtin implementation of JITTER_WOULD_PLUS_OVERFLOW, with 198 the same API. This is not intended for the user to call directly. */ 199 #define JITTER_WOULD_PLUS_OVERFLOW_NON_GCC(__jitter_unsigned_type, \ 200 __jitter_signed_type, \ 201 a, b, bit_no) \ 202 (JITTER_WOULD_PLUS_OVERFLOW_SIGNED_WORD (__jitter_unsigned_type, \ 203 __jitter_signed_type, \ 204 (a), (b), (bit_no)) \ 205 & JITTER_SIGN_BIT_FOR_BITS(bit_no)) 206 207 /* The GCC implementation of JITTER_WOULD_PLUS_OVERFLOW. This is not intended 208 for the user to call directly, and in fact is only correct when the given 209 integer type matches the result width. Again, not for the user. */ 210 #define JITTER_WOULD_PLUS_OVERFLOW_GCC(__jitter_signed_type, a, b) \ 211 (__builtin_add_overflow_p ((__jitter_signed_type) (a), \ 212 (__jitter_signed_type) (b), \ 213 (__jitter_signed_type) -1)) 214 215 /* Like JITTER_WOULD_PLUS_OVERFLOW, but checking overflow for subtraction; the 216 sign-bit idea is the same. */ 217 #ifdef JITTER_HAVE_GCC_OVERFLOW_CHECKING 218 # define JITTER_WOULD_MINUS_OVERFLOW(__jitter_unsigned_type, \ 219 __jitter_signed_type, \ 220 a, b, bit_no) \ 221 (((bit_no) == 64) \ 222 ? JITTER_WOULD_MINUS_OVERFLOW_GCC (int64_t, (a), (b)) \ 223 : (((bit_no) == 32) \ 224 ? JITTER_WOULD_MINUS_OVERFLOW_GCC (int32_t, (a), (b)) \ 225 : (((bit_no) == 16) \ 226 ? JITTER_WOULD_MINUS_OVERFLOW_GCC (int16_t, (a), (b)) \ 227 : (((bit_no) == 8) \ 228 ? JITTER_WOULD_MINUS_OVERFLOW_GCC (int8_t, (a), (b)) \ 229 : JITTER_WOULD_MINUS_OVERFLOW_NON_GCC (__jitter_unsigned_type, \ 230 __jitter_signed_type, \ 231 (a), (b), (bit_no)))))) 232 #else // No GCC builtin available. 233 # define JITTER_WOULD_MINUS_OVERFLOW(__jitter_unsigned_type, \ 234 __jitter_signed_type, \ 235 a, b, bit_no) \ 236 JITTER_WOULD_MINUS_OVERFLOW_NON_GCC (__jitter_unsigned_type, \ 237 __jitter_signed_type, \ 238 (a), (b), (bit_no)) 239 #endif // #ifdef JITTER_HAVE_GCC_OVERFLOW_CHECKING 240 #define JITTER_WOULD_MINUS_OVERFLOW_SIGNED_WORD(__jitter_unsigned_type, \ 241 __jitter_signed_type, \ 242 a, b, bit_no) \ 243 /* This formula comes from Hacker's Delight §2, again. */ \ 244 ((__jitter_signed_type) \ 245 ((((__jitter_unsigned_type) (a) - (__jitter_unsigned_type) (b)) \ 246 ^ (__jitter_unsigned_type) (a)) \ 247 & (((__jitter_unsigned_type) (a) - (__jitter_unsigned_type) (b)) \ 248 ^ ~ (__jitter_unsigned_type) (b)))) 249 #define JITTER_WOULD_MINUS_OVERFLOW_NON_GCC(__jitter_unsigned_type, \ 250 __jitter_signed_type, \ 251 a, b, bit_no) \ 252 (JITTER_WOULD_MINUS_OVERFLOW_SIGNED_WORD (__jitter_unsigned_type, \ 253 __jitter_signed_type, \ 254 (a), (b), (bit_no)) \ 255 & JITTER_SIGN_BIT_FOR_BITS(bit_no)) 256 #define JITTER_WOULD_MINUS_OVERFLOW_GCC(__jitter_signed_type, a, b) \ 257 (__builtin_sub_overflow_p ((__jitter_signed_type) (a), \ 258 (__jitter_signed_type) (b), \ 259 (__jitter_signed_type) -1)) 260 261 /* Like JITTER_WOULD_PLUS_OVERFLOW and JITTER_WOULD_MINUS_OVERFLOW, but checking 262 overflow for multiplication; unfortunately the fallback non-builtin case for 263 multiplication is less pretty and the idea of the sign bit does not apply. 264 Apart from this the logic is the same as for sum and subtraction. */ 265 #ifdef JITTER_HAVE_GCC_OVERFLOW_CHECKING 266 # define JITTER_WOULD_TIMES_OVERFLOW(__jitter_unsigned_type, \ 267 __jitter_signed_type, \ 268 a, b, bit_no) \ 269 (((bit_no) == 64) \ 270 ? JITTER_WOULD_TIMES_OVERFLOW_GCC (int64_t, (a), (b)) \ 271 : (((bit_no) == 32) \ 272 ? JITTER_WOULD_TIMES_OVERFLOW_GCC (int32_t, (a), (b)) \ 273 : (((bit_no) == 16) \ 274 ? JITTER_WOULD_TIMES_OVERFLOW_GCC (int16_t, (a), (b)) \ 275 : (((bit_no) == 8) \ 276 ? JITTER_WOULD_TIMES_OVERFLOW_GCC (int8_t, (a), (b)) \ 277 : JITTER_WOULD_TIMES_OVERFLOW_NON_GCC (__jitter_unsigned_type, \ 278 __jitter_signed_type, \ 279 (a), (b), (bit_no)))))) 280 #else // No GCC builtin available. 281 # define JITTER_WOULD_TIMES_OVERFLOW(__jitter_unsigned_type, \ 282 __jitter_signed_type, \ 283 a, b, bit_no) \ 284 JITTER_WOULD_TIMES_OVERFLOW_NON_GCC (__jitter_unsigned_type, \ 285 __jitter_signed_type, \ 286 (a), (b), (bit_no)) 287 #endif // #ifdef JITTER_HAVE_GCC_OVERFLOW_CHECKING 288 #define JITTER_WOULD_TIMES_OVERFLOW_NON_GCC(__jitter_unsigned_type, \ 289 __jitter_signed_type, \ 290 a, b, bit_no) \ 291 /* This formula comes from Hacker's Delight §2, once more. Notice \ 292 that, differently from the cases for sum and subtraction, this \ 293 works by case analysis and the result is a Boolean. This will \ 294 certainly be inefficient. */ \ 295 (((a) > 0) \ 296 ? (((b) > 0) \ 297 ? ((a) > ((__jitter_signed_type) \ 298 JITTER_MOST_POSITIVE_SIGNED_IN_BITS (bit_no) \ 299 / (b))) \ 300 : ((b) < ((__jitter_signed_type) \ 301 JITTER_MOST_NEGATIVE_SIGNED_IN_BITS (bit_no) \ 302 / (a)))) \ 303 : (((b) > 0) \ 304 ? ((a) < ((__jitter_signed_type) \ 305 JITTER_MOST_NEGATIVE_SIGNED_IN_BITS (bit_no) \ 306 / (b))) \ 307 : ((a) != 0 \ 308 && (b) < ((__jitter_signed_type) \ 309 JITTER_MOST_POSITIVE_SIGNED_IN_BITS (bit_no) \ 310 / (a))))) 311 #define JITTER_WOULD_TIMES_OVERFLOW_GCC(__jitter_signed_type, a, b) \ 312 (__builtin_mul_overflow_p ((__jitter_signed_type) (a), \ 313 (__jitter_signed_type) (b), \ 314 (__jitter_signed_type) -1)) 315 316 /* Like the previous operations, checking overflow for division. GCC has no 317 builtin for this case. */ 318 #define JITTER_WOULD_DIVIDED_OVERFLOW(__jitter_unsigned_type, \ 319 __jitter_signed_type, \ 320 a, b, bit_no) \ 321 /* The cast on the result seems gratuitous, but the size of \ 322 the result (not really the sign) may be important as \ 323 this macro may occur in inline asm operands. */ \ 324 ((__jitter_unsigned_type) \ 325 ((b) == 0 \ 326 || ((__jitter_signed_type) (a) \ 327 == ((__jitter_signed_type) \ 328 JITTER_MOST_NEGATIVE_SIGNED_IN_BITS (bit_no)) \ 329 && (__jitter_signed_type) (b) == -1))) 330 331 /* Like the previous operations, checking overflow for remainder. */ 332 #define JITTER_WOULD_REMAINDER_OVERFLOW(__jitter_unsigned_type, \ 333 __jitter_signed_type, \ 334 a, b, bit_no) \ 335 ((b) == 0) 336 337 /* The non-overflow remainder condition. See the "negative condition" comments 338 in generate-fast-branches.in.m4sh for the rationale. */ 339 #define JITTER_WOULD_REMAINDER_NOT_OVERFLOW(__jitter_unsigned_type, \ 340 __jitter_signed_type, \ 341 a, b, bit_no) \ 342 (b) 343 344 345 346 347 /* Integer overflow checking and constant expressions. 348 * ************************************************************************** */ 349 350 /* The code for checking overflow and for overflow-checking operations often 351 benefits from optimizations, consisting in not generating conditionals in 352 inline asm when the condition of overflow or non-overflow is known at 353 compile time. The logic for this optimization is in 354 jitter/jitter-fast-branch-machine-generated.h 355 , which is machine-generated by the script obtained from preprocessing 356 scripts/generate-fast-branches.in.m4sh 357 . 358 359 The GCC builtin __builtin_constant_p fails to return true in several common 360 cases which could be resolved at compile time, particularly with arguments 361 including GCC's own overflow-checking builtins. Instead of just using 362 __builtin_constant_p on a Boolean expression involving overflow-checking 363 builtins to check if a C condition can be resolved at compile time we 364 can use the macros here, which are designed to evaluate to constants more 365 easily. 366 367 The expressions given as arguments must have no side effects. The expansion 368 (of non-side-effecting arguments) will always be a constant expression, even 369 if the arguments are non-constant expressions. 370 371 This will not of course catch every possible case where the property is 372 known, as that would not even be computable, but should be both a correct 373 conservative approximation, and good enough to optimize away many redundant 374 overflow checks. I have never seen a case where GCC is not able to generate 375 straight-line code after one of these macros determined that the condition 376 was constant. Still, even if that happened, it would be just a matter of 377 suboptimal performance, and not of correctness. 378 379 The macros in this section are only used for advanced dispatches, which rely 380 on GCC anyway. No other compiler is supported. */ 381 382 /* The following helper macros are all used internally in the rest of this 383 section. 384 Given a non-side-effecting expression, constant or not, expand to a constant 385 expression evaluating to a Boolean telling, respectively, whether the 386 expression is known to evaluate to the given value or known not to, whether 387 an expression is known to evaluate to the same result as another, known to 388 evaluate to a different result, known to evaluate to a positive or to a 389 non-negative result. */ 390 #define JITTER_KNOWN_TO_BE(expression, value) \ 391 (__builtin_constant_p (expression) \ 392 && (expression) == (value)) 393 #define JITTER_KNOWN_NOT_TO_BE(expression, value) \ 394 (__builtin_constant_p (expression) \ 395 && (expression) != (value)) 396 #define JITTER_KNOWN_TO_BE_EQUAL(expression_a, expression_b) \ 397 (__builtin_constant_p ((expression_a) == (expression_b)) \ 398 && (expression_a) == (expression_b)) 399 #define JITTER_KNOWN_TO_BE_DIFFERENT(expression_a, expression_b) \ 400 (__builtin_constant_p ((expression_a) != (expression_b)) \ 401 && (expression_a) != (expression_b)) 402 #define JITTER_KNOWN_TO_BE_POSITIVE(expression_a) \ 403 (__builtin_constant_p ((expression_a) >= 0) \ 404 && (expression_a) > 0) 405 #define JITTER_KNOWN_TO_BE_NONNEGATIVE(expression_a) \ 406 (__builtin_constant_p ((expression_a) >= 0) \ 407 && (expression_a) >= 0) 408 409 /* Given two non-side-effecting expressions, constant or not, evaluating to 410 jitter_int, expand to a Boolean constant expression evaluating to true iff 411 the overflow status of a plus operation between the results of the two 412 expression is known at compile time. In case the result is true the 413 operations is either known to definietely overflow, or to definitely not 414 overflow; which case it is can be checked from the other macros above. 415 416 Implementation note: the expansion, even if complex, consists in a 417 disjunction of predicates, the simplest of which are near the beginning. */ 418 #define JITTER_PLUS_OVERFLOWS_KNOWN_CONSTANT_GCC(a, b) \ 419 ((/* Both operands are known constants: the operation might \ 420 overflow, and if so we know it at compile time. */ \ 421 __builtin_constant_p (a) \ 422 && __builtin_constant_p (b)) \ 423 || (/* For every b: 0 + b does not overflow. */ \ 424 JITTER_KNOWN_TO_BE ((a), 0)) \ 425 || (/* For every a: a + 0 does not overflow. */ \ 426 JITTER_KNOWN_TO_BE ((b), 0)) \ 427 || (/* We may know whether a + b overflows, from the macro here. */ \ 428 __builtin_constant_p \ 429 (JITTER_WOULD_PLUS_OVERFLOW_NON_GCC (jitter_uint, \ 430 jitter_int, \ 431 (a), \ 432 (b), \ 433 JITTER_BITS_PER_WORD)))) 434 435 /* Like JITTER_PLUS_OVERFLOWS_KNOWN_CONSTANT_GCC, for the minus operation. */ 436 #define JITTER_MINUS_OVERFLOWS_KNOWN_CONSTANT_GCC(a, b) \ 437 ((/* Both operands are known constants: the operation might \ 438 overflow, and if so we know it at compile time. */ \ 439 __builtin_constant_p (a) \ 440 && __builtin_constant_p (b)) \ 441 || (/* For every a: a - 0 = a does not overflow. Notice that \ 442 we cannot say the same for the left operand, since \ 443 in two's complement negatives have a wider range. */ \ 444 JITTER_KNOWN_TO_BE ((b), 0)) \ 445 || (/* For every a: a - a = 0 does not overflow. */ \ 446 JITTER_KNOWN_TO_BE_EQUAL ((a), (b))) \ 447 || (/* We may know whether a - b overflows, from the macro here. */ \ 448 __builtin_constant_p \ 449 (JITTER_WOULD_MINUS_OVERFLOW_NON_GCC (jitter_uint, \ 450 jitter_int, \ 451 (a), \ 452 (b), \ 453 JITTER_BITS_PER_WORD)))) 454 455 /* Like JITTER_PLUS_OVERFLOWS_KNOWN_CONSTANT_GCC, for the times operation. */ 456 #define JITTER_TIMES_OVERFLOWS_KNOWN_CONSTANT_GCC(a, b) \ 457 ((/* Both operands are known constants: the operation might \ 458 overflow, and if so we know it at compile time. */ \ 459 __builtin_constant_p (a) \ 460 && __builtin_constant_p (b)) \ 461 || (/* For every b: 0 * b = 0 does not overflow. */ \ 462 JITTER_KNOWN_TO_BE ((a), 0)) \ 463 || (/* For every a: a * 0 = 0 does not overflow. */ \ 464 JITTER_KNOWN_TO_BE ((b), 0)) \ 465 || (/* For every b: 1 * b = b does not overflow. */ \ 466 JITTER_KNOWN_TO_BE ((a), 1)) \ 467 || (/* For every a: 1 * a = a does not overflow. */ \ 468 JITTER_KNOWN_TO_BE ((b), 1)) \ 469 || (/* For every b: -1 * b does not overflow, as long \ 470 as b is non-negaive. */ \ 471 JITTER_KNOWN_TO_BE ((a), -1) \ 472 && JITTER_KNOWN_TO_BE_NONNEGATIVE (b)) \ 473 || (/* For every a: a * -1 does not overflow, as long \ 474 as a is non-negative. */ \ 475 JITTER_KNOWN_TO_BE ((b), -1) \ 476 && JITTER_KNOWN_TO_BE_NONNEGATIVE (a)) \ 477 || (/* We may know whether a * b overflows, from the macro here. */ \ 478 __builtin_constant_p \ 479 (JITTER_WOULD_TIMES_OVERFLOW_NON_GCC (jitter_uint, \ 480 jitter_int, \ 481 (a), \ 482 (b), \ 483 JITTER_BITS_PER_WORD)))) 484 485 /* Like JITTER_PLUS_OVERFLOWS_KNOWN_CONSTANT_GCC, for the divided operation. */ 486 #define JITTER_DIVIDED_OVERFLOWS_KNOWN_CONSTANT_GCC(a, b) \ 487 ((/* Both operands are known constants: the operation might \ 488 overflow, and if so we know it at compile time. */ \ 489 __builtin_constant_p (a) \ 490 && __builtin_constant_p (b)) \ 491 || (/* For every a: a / 0 overflows. */ \ 492 JITTER_KNOWN_TO_BE ((b), 0)) \ 493 || (/* For every a, b: a / b does not overflow when b > 0. */ \ 494 JITTER_KNOWN_TO_BE_POSITIVE (b)) \ 495 || (/* For every a, b: a / b overflows when a = MIN and b = -1. */ \ 496 JITTER_KNOWN_TO_BE ((a), JITTER_MOST_NEGATIVE_SIGNED) \ 497 && JITTER_KNOWN_TO_BE ((b), -1)) \ 498 || (/* For every a, b: a / b does not overflow when a != MIN and b != 0. */ \ 499 JITTER_KNOWN_NOT_TO_BE ((a), JITTER_MOST_NEGATIVE_SIGNED) \ 500 && JITTER_KNOWN_NOT_TO_BE ((b), 0)) \ 501 || (/* For every a, b: a / b does not overflow when b != -1 and b != 0. */ \ 502 JITTER_KNOWN_NOT_TO_BE ((b), -1) \ 503 && JITTER_KNOWN_TO_BE ((b), 0)) \ 504 || (/* We may know whether a / b overflows, from the macro here. */ \ 505 __builtin_constant_p \ 506 (JITTER_WOULD_DIVIDED_OVERFLOW (jitter_uint, \ 507 jitter_int, \ 508 (a), \ 509 (b), \ 510 JITTER_BITS_PER_WORD)))) 511 512 /* Like JITTER_PLUS_OVERFLOWS_KNOWN_CONSTANT_GCC, for the remainder (%) 513 operation. */ 514 #define JITTER_REMAINDER_OVERFLOWS_KNOWN_CONSTANT_GCC(a, b) \ 515 JITTER_DIVIDED_OVERFLOWS_KNOWN_CONSTANT_GCC((a), (b)) 516 517 518 519 520 /* Sign function, as a macro. 521 * ************************************************************************** */ 522 523 /* Given an expression a, expand to a signed integer expression holding the sign 524 of the result of the evaluation of a: one of -1, 0, +1. 525 The argument may be evaluated more than once. If the argument is a constant 526 expression then the expansion is constant as well. 527 This is also correct for floating-point arguments. */ 528 #define JITTER_SIGN(n) \ 529 /* The idea is from Hacker's Delight §2-8, which also presents an \ 530 alternative equivalent to, in my notation, \ 531 (!! ((n) >= 0) - !! ((n) <= 0)) \ 532 . In C, ever since K&R, (! expression) is guaranteed to always \ 533 yield either 0 or 1; therefore (!! expression) is a portable \ 534 way of normalizing a Boolean. */ \ 535 (!! ((n) > 0) - !! ((n) < 0)) 536 537 538 539 540 /* Boolean operations. 541 * ************************************************************************** */ 542 543 /* I might want to move this section to some other header. */ 544 545 /* Expand to an expression evaluating to the logical (not bitwise) xor of the 546 result of the evaluation of the two given Boolean expressions. This is 547 useful for comparing possibly non-normalized Booleans for inequality, 548 obtaining a non-false value when the two arguments are (logically) 549 different. */ 550 #define JITTER_XOR(a, b) \ 551 /* Implementation note: this normalization using ! is correct and \ 552 portable, as (! exp) is guaranteed to evaluate to either 0 or 1. \ 553 This has been the case forever, since even before the time of \ 554 ANSI C. */ \ 555 (! (a) != ! (b)) 556 557 /* Similar to JITTER_XOR, but here the expansion evaluates to the logical 558 negation of the logical xor of the results. This is a convenient way of 559 comparing two possibly non-normalized Booleans for Boolean equality. */ 560 #define JITTER_NXOR(a, b) \ 561 /* See the implementation comment in JITTER_XOR. */ \ 562 (! (a) == ! (b)) 563 564 565 566 567 /* Number of digits of an integer. 568 * ************************************************************************** */ 569 570 /* The functionality in this section could be implemented with macros, at the 571 cost of only a little pain. Right now this API is not used in 572 performance-critical code or from VM instructions, and therefore relies on 573 functions. */ 574 575 /* Return the number of characters required to represent the given signed 576 integer number, including the minus sign only if the argument is negative, in 577 the given radix. */ 578 int 579 jitter_digit_no (jitter_int number, unsigned radix); 580 581 /* Same as jitter_digit_no, for an unsigned integer. */ 582 int 583 jitter_digit_no_unsigned (jitter_uint number, unsigned radix); 584 585 /* Same as jitter_digit_no and jitter_digit_no_unsigned, for radix 10. */ 586 int 587 jitter_digit_no_radix_10 (jitter_int number); 588 int 589 jitter_digit_no_unsigned_radix_10 (jitter_uint number); 590 591 #endif // #ifndef JITTER_ARITHMETIC_H_ 592