| /* |
| * Copyright 2021-2022 The OpenSSL Project Authors. All Rights Reserved. |
| * |
| * Licensed under the Apache License 2.0 (the "License"). You may not use |
| * this file except in compliance with the License. You can obtain a copy |
| * in the file LICENSE in the source distribution or at |
| * https://www.openssl.org/source/license.html |
| */ |
| |
| #ifndef OSSL_INTERNAL_SAFE_MATH_H |
| # define OSSL_INTERNAL_SAFE_MATH_H |
| # pragma once |
| |
| # include <openssl/e_os2.h> /* For 'ossl_inline' */ |
| |
| # ifndef OPENSSL_NO_BUILTIN_OVERFLOW_CHECKING |
| # ifdef __has_builtin |
| # define has(func) __has_builtin(func) |
| # elif __GNUC__ > 5 |
| # define has(func) 1 |
| # endif |
| # endif /* OPENSSL_NO_BUILTIN_OVERFLOW_CHECKING */ |
| |
| # ifndef has |
| # define has(func) 0 |
| # endif |
| |
| /* |
| * Safe addition helpers |
| */ |
| # if has(__builtin_add_overflow) |
| # define OSSL_SAFE_MATH_ADDS(type_name, type, min, max) \ |
| static ossl_inline ossl_unused type safe_add_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| type r; \ |
| \ |
| if (!__builtin_add_overflow(a, b, &r)) \ |
| return r; \ |
| *err |= 1; \ |
| return a < 0 ? min : max; \ |
| } |
| |
| # define OSSL_SAFE_MATH_ADDU(type_name, type, max) \ |
| static ossl_inline ossl_unused type safe_add_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| type r; \ |
| \ |
| if (!__builtin_add_overflow(a, b, &r)) \ |
| return r; \ |
| *err |= 1; \ |
| return a + b; \ |
| } |
| |
| # else /* has(__builtin_add_overflow) */ |
| # define OSSL_SAFE_MATH_ADDS(type_name, type, min, max) \ |
| static ossl_inline ossl_unused type safe_add_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if ((a < 0) ^ (b < 0) \ |
| || (a > 0 && b <= max - a) \ |
| || (a < 0 && b >= min - a) \ |
| || a == 0) \ |
| return a + b; \ |
| *err |= 1; \ |
| return a < 0 ? min : max; \ |
| } |
| |
| # define OSSL_SAFE_MATH_ADDU(type_name, type, max) \ |
| static ossl_inline ossl_unused type safe_add_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (b > max - a) \ |
| *err |= 1; \ |
| return a + b; \ |
| } |
| # endif /* has(__builtin_add_overflow) */ |
| |
| /* |
| * Safe subtraction helpers |
| */ |
| # if has(__builtin_sub_overflow) |
| # define OSSL_SAFE_MATH_SUBS(type_name, type, min, max) \ |
| static ossl_inline ossl_unused type safe_sub_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| type r; \ |
| \ |
| if (!__builtin_sub_overflow(a, b, &r)) \ |
| return r; \ |
| *err |= 1; \ |
| return a < 0 ? min : max; \ |
| } |
| |
| # else /* has(__builtin_sub_overflow) */ |
| # define OSSL_SAFE_MATH_SUBS(type_name, type, min, max) \ |
| static ossl_inline ossl_unused type safe_sub_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (!((a < 0) ^ (b < 0)) \ |
| || (b > 0 && a >= min + b) \ |
| || (b < 0 && a <= max + b) \ |
| || b == 0) \ |
| return a - b; \ |
| *err |= 1; \ |
| return a < 0 ? min : max; \ |
| } |
| |
| # endif /* has(__builtin_sub_overflow) */ |
| |
| # define OSSL_SAFE_MATH_SUBU(type_name, type) \ |
| static ossl_inline ossl_unused type safe_sub_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (b > a) \ |
| *err |= 1; \ |
| return a - b; \ |
| } |
| |
| /* |
| * Safe multiplication helpers |
| */ |
| # if has(__builtin_mul_overflow) |
| # define OSSL_SAFE_MATH_MULS(type_name, type, min, max) \ |
| static ossl_inline ossl_unused type safe_mul_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| type r; \ |
| \ |
| if (!__builtin_mul_overflow(a, b, &r)) \ |
| return r; \ |
| *err |= 1; \ |
| return (a < 0) ^ (b < 0) ? min : max; \ |
| } |
| |
| # define OSSL_SAFE_MATH_MULU(type_name, type, max) \ |
| static ossl_inline ossl_unused type safe_mul_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| type r; \ |
| \ |
| if (!__builtin_mul_overflow(a, b, &r)) \ |
| return r; \ |
| *err |= 1; \ |
| return a * b; \ |
| } |
| |
| # else /* has(__builtin_mul_overflow) */ |
| # define OSSL_SAFE_MATH_MULS(type_name, type, min, max) \ |
| static ossl_inline ossl_unused type safe_mul_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (a == 0 || b == 0) \ |
| return 0; \ |
| if (a == 1) \ |
| return b; \ |
| if (b == 1) \ |
| return a; \ |
| if (a != min && b != min) { \ |
| const type x = a < 0 ? -a : a; \ |
| const type y = b < 0 ? -b : b; \ |
| \ |
| if (x <= max / y) \ |
| return a * b; \ |
| } \ |
| *err |= 1; \ |
| return (a < 0) ^ (b < 0) ? min : max; \ |
| } |
| |
| # define OSSL_SAFE_MATH_MULU(type_name, type, max) \ |
| static ossl_inline ossl_unused type safe_mul_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (a > max / b) \ |
| *err |= 1; \ |
| return a * b; \ |
| } |
| # endif /* has(__builtin_mul_overflow) */ |
| |
| /* |
| * Safe division helpers |
| */ |
| # define OSSL_SAFE_MATH_DIVS(type_name, type, min, max) \ |
| static ossl_inline ossl_unused type safe_div_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (b == 0) { \ |
| *err |= 1; \ |
| return a < 0 ? min : max; \ |
| } \ |
| if (b == -1 && a == min) { \ |
| *err |= 1; \ |
| return max; \ |
| } \ |
| return a / b; \ |
| } |
| |
| # define OSSL_SAFE_MATH_DIVU(type_name, type, max) \ |
| static ossl_inline ossl_unused type safe_div_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (b != 0) \ |
| return a / b; \ |
| *err |= 1; \ |
| return max; \ |
| } |
| |
| /* |
| * Safe modulus helpers |
| */ |
| # define OSSL_SAFE_MATH_MODS(type_name, type, min, max) \ |
| static ossl_inline ossl_unused type safe_mod_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (b == 0) { \ |
| *err |= 1; \ |
| return 0; \ |
| } \ |
| if (b == -1 && a == min) { \ |
| *err |= 1; \ |
| return max; \ |
| } \ |
| return a % b; \ |
| } |
| |
| # define OSSL_SAFE_MATH_MODU(type_name, type) \ |
| static ossl_inline ossl_unused type safe_mod_ ## type_name(type a, \ |
| type b, \ |
| int *err) \ |
| { \ |
| if (b != 0) \ |
| return a % b; \ |
| *err |= 1; \ |
| return 0; \ |
| } |
| |
| /* |
| * Safe negation helpers |
| */ |
| # define OSSL_SAFE_MATH_NEGS(type_name, type, min) \ |
| static ossl_inline ossl_unused type safe_neg_ ## type_name(type a, \ |
| int *err) \ |
| { \ |
| if (a != min) \ |
| return -a; \ |
| *err |= 1; \ |
| return min; \ |
| } |
| |
| # define OSSL_SAFE_MATH_NEGU(type_name, type) \ |
| static ossl_inline ossl_unused type safe_neg_ ## type_name(type a, \ |
| int *err) \ |
| { \ |
| if (a == 0) \ |
| return a; \ |
| *err |= 1; \ |
| return 1 + ~a; \ |
| } |
| |
| /* |
| * Safe absolute value helpers |
| */ |
| # define OSSL_SAFE_MATH_ABSS(type_name, type, min) \ |
| static ossl_inline ossl_unused type safe_abs_ ## type_name(type a, \ |
| int *err) \ |
| { \ |
| if (a != min) \ |
| return a < 0 ? -a : a; \ |
| *err |= 1; \ |
| return min; \ |
| } |
| |
| # define OSSL_SAFE_MATH_ABSU(type_name, type) \ |
| static ossl_inline ossl_unused type safe_abs_ ## type_name(type a, \ |
| int *err) \ |
| { \ |
| return a; \ |
| } |
| |
| /* |
| * Safe fused multiply divide helpers |
| * |
| * These are a bit obscure: |
| * . They begin by checking the denominator for zero and getting rid of this |
| * corner case. |
| * |
| * . Second is an attempt to do the multiplication directly, if it doesn't |
| * overflow, the quotient is returned (for signed values there is a |
| * potential problem here which isn't present for unsigned). |
| * |
| * . Finally, the multiplication/division is transformed so that the larger |
| * of the numerators is divided first. This requires a remainder |
| * correction: |
| * |
| * a b / c = (a / c) b + (a mod c) b / c, where a > b |
| * |
| * The individual operations need to be overflow checked (again signed |
| * being more problematic). |
| * |
| * The algorithm used is not perfect but it should be "good enough". |
| */ |
| # define OSSL_SAFE_MATH_MULDIVS(type_name, type, max) \ |
| static ossl_inline ossl_unused type safe_muldiv_ ## type_name(type a, \ |
| type b, \ |
| type c, \ |
| int *err) \ |
| { \ |
| int e2 = 0; \ |
| type q, r, x, y; \ |
| \ |
| if (c == 0) { \ |
| *err |= 1; \ |
| return a == 0 || b == 0 ? 0 : max; \ |
| } \ |
| x = safe_mul_ ## type_name(a, b, &e2); \ |
| if (!e2) \ |
| return safe_div_ ## type_name(x, c, err); \ |
| if (b > a) { \ |
| x = b; \ |
| b = a; \ |
| a = x; \ |
| } \ |
| q = safe_div_ ## type_name(a, c, err); \ |
| r = safe_mod_ ## type_name(a, c, err); \ |
| x = safe_mul_ ## type_name(r, b, err); \ |
| y = safe_mul_ ## type_name(q, b, err); \ |
| q = safe_div_ ## type_name(x, c, err); \ |
| return safe_add_ ## type_name(y, q, err); \ |
| } |
| |
| # define OSSL_SAFE_MATH_MULDIVU(type_name, type, max) \ |
| static ossl_inline ossl_unused type safe_muldiv_ ## type_name(type a, \ |
| type b, \ |
| type c, \ |
| int *err) \ |
| { \ |
| int e2 = 0; \ |
| type x, y; \ |
| \ |
| if (c == 0) { \ |
| *err |= 1; \ |
| return a == 0 || b == 0 ? 0 : max; \ |
| } \ |
| x = safe_mul_ ## type_name(a, b, &e2); \ |
| if (!e2) \ |
| return x / c; \ |
| if (b > a) { \ |
| x = b; \ |
| b = a; \ |
| a = x; \ |
| } \ |
| x = safe_mul_ ## type_name(a % c, b, err); \ |
| y = safe_mul_ ## type_name(a / c, b, err); \ |
| return safe_add_ ## type_name(y, x / c, err); \ |
| } |
| |
| /* |
| * Calculate a / b rounding up: |
| * i.e. a / b + (a % b != 0) |
| * Which is usually (less safely) converted to (a + b - 1) / b |
| * If you *know* that b != 0, then it's safe to ignore err. |
| */ |
| #define OSSL_SAFE_MATH_DIV_ROUND_UP(type_name, type, max) \ |
| static ossl_inline ossl_unused type safe_div_round_up_ ## type_name \ |
| (type a, type b, int *errp) \ |
| { \ |
| type x; \ |
| int *err, err_local = 0; \ |
| \ |
| /* Allow errors to be ignored by callers */ \ |
| err = errp != NULL ? errp : &err_local; \ |
| /* Fast path, both positive */ \ |
| if (b > 0 && a > 0) { \ |
| /* Faster path: no overflow concerns */ \ |
| if (a < max - b) \ |
| return (a + b - 1) / b; \ |
| return a / b + (a % b != 0); \ |
| } \ |
| if (b == 0) { \ |
| *err |= 1; \ |
| return a == 0 ? 0 : max; \ |
| } \ |
| if (a == 0) \ |
| return 0; \ |
| /* Rather slow path because there are negatives involved */ \ |
| x = safe_mod_ ## type_name(a, b, err); \ |
| return safe_add_ ## type_name(safe_div_ ## type_name(a, b, err), \ |
| x != 0, err); \ |
| } |
| |
| /* Calculate ranges of types */ |
| # define OSSL_SAFE_MATH_MINS(type) ((type)1 << (sizeof(type) * 8 - 1)) |
| # define OSSL_SAFE_MATH_MAXS(type) (~OSSL_SAFE_MATH_MINS(type)) |
| # define OSSL_SAFE_MATH_MAXU(type) (~(type)0) |
| |
| /* |
| * Wrapper macros to create all the functions of a given type |
| */ |
| # define OSSL_SAFE_MATH_SIGNED(type_name, type) \ |
| OSSL_SAFE_MATH_ADDS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ |
| OSSL_SAFE_MATH_MAXS(type)) \ |
| OSSL_SAFE_MATH_SUBS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ |
| OSSL_SAFE_MATH_MAXS(type)) \ |
| OSSL_SAFE_MATH_MULS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ |
| OSSL_SAFE_MATH_MAXS(type)) \ |
| OSSL_SAFE_MATH_DIVS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ |
| OSSL_SAFE_MATH_MAXS(type)) \ |
| OSSL_SAFE_MATH_MODS(type_name, type, OSSL_SAFE_MATH_MINS(type), \ |
| OSSL_SAFE_MATH_MAXS(type)) \ |
| OSSL_SAFE_MATH_DIV_ROUND_UP(type_name, type, \ |
| OSSL_SAFE_MATH_MAXS(type)) \ |
| OSSL_SAFE_MATH_MULDIVS(type_name, type, OSSL_SAFE_MATH_MAXS(type)) \ |
| OSSL_SAFE_MATH_NEGS(type_name, type, OSSL_SAFE_MATH_MINS(type)) \ |
| OSSL_SAFE_MATH_ABSS(type_name, type, OSSL_SAFE_MATH_MINS(type)) |
| |
| # define OSSL_SAFE_MATH_UNSIGNED(type_name, type) \ |
| OSSL_SAFE_MATH_ADDU(type_name, type, OSSL_SAFE_MATH_MAXU(type)) \ |
| OSSL_SAFE_MATH_SUBU(type_name, type) \ |
| OSSL_SAFE_MATH_MULU(type_name, type, OSSL_SAFE_MATH_MAXU(type)) \ |
| OSSL_SAFE_MATH_DIVU(type_name, type, OSSL_SAFE_MATH_MAXU(type)) \ |
| OSSL_SAFE_MATH_MODU(type_name, type) \ |
| OSSL_SAFE_MATH_DIV_ROUND_UP(type_name, type, \ |
| OSSL_SAFE_MATH_MAXU(type)) \ |
| OSSL_SAFE_MATH_MULDIVU(type_name, type, OSSL_SAFE_MATH_MAXU(type)) \ |
| OSSL_SAFE_MATH_NEGU(type_name, type) \ |
| OSSL_SAFE_MATH_ABSU(type_name, type) |
| |
| #endif /* OSSL_INTERNAL_SAFE_MATH_H */ |
