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 | 463 | static inline bool umax_multiply_overflows(uintmax_t a, uintmax_t b, uintmax_t *result) | |
29 | { | ||
30 | 463 | CHECKED_MUL(a, b, result); | |
31 | } | ||
32 | |||
33 | 17883 | static inline bool size_multiply_overflows(size_t a, size_t b, size_t *result) | |
34 | { | ||
35 | 17883 | CHECKED_MUL(a, b, result); | |
36 | } | ||
37 | |||
38 | 457 | static inline bool umax_add_overflows(uintmax_t a, uintmax_t b, uintmax_t *result) | |
39 | { | ||
40 | 457 | CHECKED_ADD(a, b, result); | |
41 | } | ||
42 | |||
43 | 192943 | static inline bool size_add_overflows(size_t a, size_t b, size_t *result) | |
44 | { | ||
45 | 192943 | CHECKED_ADD(a, b, result); | |
46 | } | ||
47 | |||
48 | // Saturating subtract | ||
49 | 10 | static inline size_t size_ssub(size_t a, size_t b) | |
50 | { | ||
51 | 10 | size_t r = a - b; | |
52 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 6 times.
|
10 | return (r > a) ? 0 : r; |
53 | } | ||
54 | |||
55 | // Round x up to a multiple of r (which *must* be a power of 2) | ||
56 | 26874 | static inline size_t round_size_to_next_multiple(size_t x, size_t r) | |
57 | DIAGNOSE_IF(!IS_POWER_OF_2(r)) | ||
58 | { | ||
59 | 26874 | r--; | |
60 | 26874 | return (x + r) & ~r; | |
61 | } | ||
62 | |||
63 | // This is equivalent to `(x + 1) % modulus`, given the constraints | ||
64 | // imposed by BUG_ON(), but avoids expensive divisions by a non-constant | ||
65 | 65 | static inline size_t size_increment_wrapped(size_t x, size_t modulus) | |
66 | { | ||
67 | 65 | BUG_ON(modulus == 0); | |
68 | 65 | BUG_ON(x >= modulus); | |
69 |
2/2✓ Branch 0 taken 49 times.
✓ Branch 1 taken 16 times.
|
65 | return (x + 1 < modulus) ? x + 1 : 0; |
70 | } | ||
71 | |||
72 | // As above, but for decrementing `x` instead of incrementing it | ||
73 | 51 | static inline size_t size_decrement_wrapped(size_t x, size_t modulus) | |
74 | { | ||
75 | 51 | BUG_ON(modulus == 0); | |
76 | 51 | BUG_ON(x >= modulus); | |
77 |
2/2✓ Branch 0 taken 37 times.
✓ Branch 1 taken 14 times.
|
51 | return (x ? x : modulus) - 1; |
78 | } | ||
79 | |||
80 | #endif | ||
81 |