| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef UTIL_ARITH_H | ||
| 2 | #define UTIL_ARITH_H | ||
| 3 | |||
| 4 | #include <stdbool.h> | ||
| 5 | #include <stddef.h> | ||
| 6 | #include <stdint.h> | ||
| 7 | #include "debug.h" | ||
| 8 | #include "macros.h" | ||
| 9 | |||
| 10 | // Calculate the maximum representable value for __typeof__(x), where x | ||
| 11 | // is an unsigned integer and sizeof(x) >= sizeof(int) | ||
| 12 | #define UNSIGNED_MAX_VALUE(x) (~((x) ^ (x))) | ||
| 13 | |||
| 14 | #if GNUC_AT_LEAST(5, 0) || HAS_BUILTIN(__builtin_mul_overflow) | ||
| 15 | #define CHECKED_ADD(a, b, res) return __builtin_add_overflow(a, b, res) | ||
| 16 | #define CHECKED_MUL(a, b, res) return __builtin_mul_overflow(a, b, res) | ||
| 17 | #elif __STDC_VERSION__ >= 202311L | ||
| 18 | #include <stdckdint.h> | ||
| 19 | #define CHECKED_ADD(a, b, res) return ckd_add(res, a, b) | ||
| 20 | #define CHECKED_MUL(a, b, res) return ckd_mul(res, a, b) | ||
| 21 | #else | ||
| 22 | #define CHECKED_ADD(a, b, res) \ | ||
| 23 | if (unlikely(b > UNSIGNED_MAX_VALUE(a) - a)) return true; else {*res = a + b; return false;} | ||
| 24 | #define CHECKED_MUL(a, b, res) \ | ||
| 25 | if (unlikely(a > 0 && b > UNSIGNED_MAX_VALUE(a) / a)) return true; else {*res = a * b; return false;} | ||
| 26 | #endif | ||
| 27 | |||
| 28 | 482 | static inline bool umax_multiply_overflows(uintmax_t a, uintmax_t b, uintmax_t *result) | |
| 29 | { | ||
| 30 | 482 | CHECKED_MUL(a, b, result); | |
| 31 | } | ||
| 32 | |||
| 33 | 15914 | static inline bool size_multiply_overflows(size_t a, size_t b, size_t *result) | |
| 34 | { | ||
| 35 | 15914 | CHECKED_MUL(a, b, result); | |
| 36 | } | ||
| 37 | |||
| 38 | 476 | static inline bool umax_add_overflows(uintmax_t a, uintmax_t b, uintmax_t *result) | |
| 39 | { | ||
| 40 | 476 | CHECKED_ADD(a, b, result); | |
| 41 | } | ||
| 42 | |||
| 43 | 241144 | static inline bool size_add_overflows(size_t a, size_t b, size_t *result) | |
| 44 | { | ||
| 45 | 241144 | CHECKED_ADD(a, b, result); | |
| 46 | } | ||
| 47 | |||
| 48 | // Return true if `nmemb * size` overflows and the compiler indicates a | ||
| 49 | // pre-C23 standards revision. The purpose of this is to check for integer | ||
| 50 | // overflow in the product of calloc() arguments, but only when the standard | ||
| 51 | // doesn't require the calloc() function itself to do so (see ยง7.24.3.2p3). | ||
| 52 | 4390 | static inline bool calloc_args_have_ub_overflow(size_t nmemb, size_t size) | |
| 53 | { | ||
| 54 | 4390 | bool pre_c23 = (__STDC_VERSION__ < 202311L); | |
| 55 | 4390 | size_t tmp; | |
| 56 | 4390 | return pre_c23 && size_multiply_overflows(nmemb, size, &tmp); | |
| 57 | } | ||
| 58 | |||
| 59 | // This is equivalent to `(x + 1) % modulus`, given the constraints | ||
| 60 | // imposed by BUG_ON(), but avoids expensive divisions by a non-constant | ||
| 61 | 65 | static inline size_t wrapping_increment(size_t x, size_t modulus) | |
| 62 | { | ||
| 63 | 65 | BUG_ON(modulus == 0); | |
| 64 | 65 | BUG_ON(x >= modulus); | |
| 65 |
2/2✓ Branch 0 (6→7) taken 49 times.
✓ Branch 1 (6→8) taken 16 times.
|
65 | return (x + 1 < modulus) ? x + 1 : 0; |
| 66 | } | ||
| 67 | |||
| 68 | // As above, but for decrementing `x` instead of incrementing it | ||
| 69 | 51 | static inline size_t wrapping_decrement(size_t x, size_t modulus) | |
| 70 | { | ||
| 71 | 51 | BUG_ON(modulus == 0); | |
| 72 | 51 | BUG_ON(x >= modulus); | |
| 73 |
2/2✓ Branch 0 (6→7) taken 37 times.
✓ Branch 1 (6→8) taken 14 times.
|
51 | return (x ? x : modulus) - 1; |
| 74 | } | ||
| 75 | |||
| 76 | 7 | static inline size_t saturating_increment(size_t x, size_t max) | |
| 77 | { | ||
| 78 | 7 | BUG_ON(x > max); | |
| 79 | 7 | return x + (x < max); | |
| 80 | } | ||
| 81 | |||
| 82 | 5 | static inline size_t saturating_decrement(size_t x) | |
| 83 | { | ||
| 84 | 5 | return x - (x > 0); | |
| 85 | } | ||
| 86 | |||
| 87 | 12 | static inline size_t saturating_subtract(size_t a, size_t b) | |
| 88 | { | ||
| 89 | 12 | return a - MIN(a, b); | |
| 90 | } | ||
| 91 | |||
| 92 | size_t xmul_(size_t a, size_t b); | ||
| 93 | size_t xadd(size_t a, size_t b); | ||
| 94 | |||
| 95 | // Equivalent to `a * b`, but calling fatal_error() for arithmetic overflow. | ||
| 96 | // Note that if either operand is 2, adding 1 to the result can never | ||
| 97 | // overflow (often useful when doubling a buffer plus 1 extra byte). Similar | ||
| 98 | // observations can be made when multiplying by other powers of 2 (except 1) | ||
| 99 | // due to the equivalence with left shifting. | ||
| 100 | 15892 | static inline size_t xmul(size_t a, size_t b) | |
| 101 | { | ||
| 102 | // If either argument is known at compile-time to be 1, the multiplication | ||
| 103 | // can't overflow and is thus safe to be inlined without checks | ||
| 104 |
2/8✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 15892 times.
✗ Branch 2 (3→4) not taken.
✗ Branch 3 (3→6) not taken.
✗ Branch 4 (4→5) not taken.
✓ Branch 5 (4→7) taken 15892 times.
✗ Branch 6 (5→6) not taken.
✗ Branch 7 (5→7) not taken.
|
15892 | if ((IS_CT_CONSTANT(a) && a <= 1) || (IS_CT_CONSTANT(b) && b <= 1)) { |
| 105 | − | return a * b; // GCOVR_EXCL_LINE | |
| 106 | } | ||
| 107 | // Otherwise, emit a call to the checked implementation | ||
| 108 | 15892 | return xmul_(a, b); | |
| 109 | } | ||
| 110 | |||
| 111 | 203 | static inline size_t xadd3(size_t a, size_t b, size_t c) | |
| 112 | { | ||
| 113 | 203 | return xadd(a, xadd(b, c)); | |
| 114 | } | ||
| 115 | |||
| 116 | #endif | ||
| 117 |