src/SquidMath.h

   1 /*
   2  * Copyright (C) 1996-2023 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 #ifndef SQUID_SRC_SQUIDMATH_H
  10 #define SQUID_SRC_SQUIDMATH_H
  11
  12 #include "base/forward.h"
  13 #include "base/TypeTraits.h"
  14
  15 #include <limits>
  16 #include <optional>
  17
  18 // TODO: Move to src/base/Math.h and drop the Math namespace
  19
  20 /* Math functions we define locally for Squid */
  21 namespace Math
  22 {
  23
  24 int intPercent(const int a, const int b);
  25 int64_t int64Percent(const int64_t a, const int64_t b);
  26 double doublePercent(const double, const double);
  27 int intAverage(const int, const int, int, const int);
  28 double doubleAverage(const double, const double, int, const int);
  29
  30 } // namespace Math
  31
  32 // If Sum() performance becomes important, consider using GCC and clang
  33 // built-ins like __builtin_add_overflow() instead of manual overflow checks.
  34
  35 /// detects a pair of unsigned types
  36 /// reduces code duplication in declarations further below
  37 template <typename T, typename U>
  38 using AllUnsigned = typename std::conditional<
  39                     std::is_unsigned<T>::value && std::is_unsigned<U>::value,
  40                     std::true_type,
  41                     std::false_type
  42                     >::type;
  43
  44 // TODO: Replace with std::cmp_less() after migrating to C++20.
  45 /// whether integer a is less than integer b, with correct overflow handling
  46 template <typename A, typename B>
  47 constexpr bool
  48 Less(const A a, const B b) {
  49     // The casts below make standard C++ integer conversions explicit. They
  50     // quell compiler warnings about signed/unsigned comparison. The first two
  51     // lines exclude different-sign a and b, making the casts/comparison safe.
  52     using AB = typename std::common_type<A, B>::type;
  53     return
  54         (a >= 0 && b < 0) ? false :
  55         (a < 0 && b >= 0) ? true :
  56         /* (a >= 0) == (b >= 0) */ static_cast<AB>(a) < static_cast<AB>(b);
  57 }
  58
  59 /// ensure that T is supported by NaturalSum() and friends
  60 template<typename T>
  61 constexpr void
  62 AssertNaturalType()
  63 {
  64     static_assert(std::numeric_limits<T>::is_bounded, "std::numeric_limits<T>::max() is meaningful");
  65     static_assert(std::numeric_limits<T>::is_exact, "no silent loss of precision");
  66     static_assert(!std::is_enum<T>::value, "no silent creation of non-enumerated values");
  67 }
  68
  69 // TODO: Investigate whether this optimization can be expanded to [signed] types
  70 // A and B when std::numeric_limits<decltype(A(0)+B(0))>::is_modulo is true.
  71 /// This IncreaseSumInternal() overload is optimized for speed.
  72 /// \returns a non-overflowing sum of the two unsigned arguments (or nothing)
  73 /// \prec both argument types are unsigned
  74 template <typename S, typename A, typename B, std::enable_if_t<AllUnsigned<A,B>::value, int> = 0>
  75 std::optional<S>
  76 IncreaseSumInternal(const A a, const B b) {
  77     // paranoid: AllUnsigned<A,B> precondition established that already
  78     static_assert(std::is_unsigned<A>::value, "AllUnsigned dispatch worked for A");
  79     static_assert(std::is_unsigned<B>::value, "AllUnsigned dispatch worked for B");
  80
  81     AssertNaturalType<S>();
  82     AssertNaturalType<A>();
  83     AssertNaturalType<B>();
  84
  85     // we should only be called by IncreaseSum(); it forces integer promotion
  86     static_assert(std::is_same<A, decltype(+a)>::value, "a will not be promoted");
  87     static_assert(std::is_same<B, decltype(+b)>::value, "b will not be promoted");
  88     // and without integer promotions, a sum of unsigned integers is unsigned
  89     static_assert(std::is_unsigned<decltype(a+b)>::value, "a+b is unsigned");
  90
  91     // with integer promotions ruled out, a or b can only undergo integer
  92     // conversion to the higher rank type (A or B, we do not know which)
  93     using AB = typename std::common_type<A, B>::type;
  94     static_assert(std::is_same<AB, A>::value || std::is_same<AB, B>::value, "no unexpected conversions");
  95     static_assert(std::is_same<AB, decltype(a+b)>::value, "lossless assignment");
  96     const AB sum = a + b;
  97
  98     static_assert(std::numeric_limits<AB>::is_modulo, "we can detect overflows");
  99     // 1. modulo math: overflowed sum is smaller than any of its operands
 100     // 2. the sum may overflow S (i.e. the return base type)
 101     // We do not need Less() here because we compare promoted unsigned types.
 102     return (sum >= a && sum <= std::numeric_limits<S>::max()) ?
 103            std::optional<S>(sum) : std::optional<S>();
 104 }
 105
 106 /// This IncreaseSumInternal() overload supports a larger variety of types.
 107 /// \returns a non-overflowing sum of the two arguments (or nothing)
 108 /// \returns nothing if at least one of the arguments is negative
 109 /// \prec at least one of the argument types is signed
 110 template <typename S, typename A, typename B, std::enable_if_t<!AllUnsigned<A,B>::value, int> = 0>
 111 std::optional<S> constexpr
 112 IncreaseSumInternal(const A a, const B b) {
 113     AssertNaturalType<S>();
 114     AssertNaturalType<A>();
 115     AssertNaturalType<B>();
 116
 117     // we should only be called by IncreaseSum() that does integer promotion
 118     static_assert(std::is_same<A, decltype(+a)>::value, "a will not be promoted");
 119     static_assert(std::is_same<B, decltype(+b)>::value, "b will not be promoted");
 120
 121     return
 122         // We could support a non-under/overflowing sum of negative numbers, but
 123         // our callers use negative values specially (e.g., for do-not-use or
 124         // do-not-limit settings) and are not supposed to do math with them.
 125         (a < 0 || b < 0) ? std::optional<S>() :
 126         // To avoid undefined behavior of signed overflow, we must not compute
 127         // the raw a+b sum if it may overflow. When A is not B, a or b undergoes
 128         // (safe for non-negatives) integer conversion in these expressions, so
 129         // we do not know the resulting a+b type AB and its maximum. We must
 130         // also detect subsequent casting-to-S overflows.
 131         // Overflow condition: (a + b > maxAB) or (a + b > maxS).
 132         // A is an integer promotion of S, so maxS <= maxA <= maxAB.
 133         // Since maxS <= maxAB, it is sufficient to just check: a + b > maxS,
 134         // which is the same as the overflow-safe condition here: maxS - a < b.
 135         // Finally, (maxS - a) cannot overflow because a is not negative and
 136         // cannot underflow because a is a promotion of s: 0 <= a <= maxS.
 137         Less(std::numeric_limits<S>::max() - a, b) ? std::optional<S>() :
 138         std::optional<S>(a + b);
 139 }
 140
 141 /// argument pack expansion termination for IncreaseSum<S, T, Args...>()
 142 template <typename S, typename T>
 143 std::optional<S>
 144 IncreaseSum(const S s, const T t)
 145 {
 146     // Force (always safe) integer promotions now, to give std::enable_if_t<>
 147     // promoted types instead of entering IncreaseSumInternal<AllUnsigned>(s,t)
 148     // but getting a _signed_ promoted value of s or t in s + t.
 149     return IncreaseSumInternal<S>(+s, +t);
 150 }
 151
 152 /// \returns a non-overflowing sum of the arguments (or nothing)
 153 template <typename S, typename T, typename... Args>
 154 std::optional<S>
 155 IncreaseSum(const S sum, const T t, const Args... args) {
 156     if (const auto head = IncreaseSum(sum, t)) {
 157         return IncreaseSum(head.value(), args...);
 158     } else {
 159         // std::optional<S>() triggers bogus -Wmaybe-uninitialized warnings in GCC v10.3
 160         return std::nullopt;
 161     }
 162 }
 163
 164 /// \returns an exact, non-overflowing sum of the arguments (or nothing)
 165 template <typename SummationType, typename... Args>
 166 std::optional<SummationType>
 167 NaturalSum(const Args... args) {
 168     return IncreaseSum<SummationType>(0, args...);
 169 }
 170
 171 /// Safely resets the given variable to NaturalSum() of the given arguments.
 172 /// If the sum overflows, resets to variable's maximum possible value.
 173 /// \returns the new variable value (like an assignment operator would)
 174 template <typename S, typename... Args>
 175 S
 176 SetToNaturalSumOrMax(S &var, const Args... args)
 177 {
 178     var = NaturalSum<S>(args...).value_or(std::numeric_limits<S>::max());
 179     return var;
 180 }
 181
 182 /// converts a given non-negative integer into an integer of a given type
 183 /// without loss of information or undefined behavior
 184 template <typename Result, typename Source>
 185 Result
 186 NaturalCast(const Source s)
 187 {
 188     return NaturalSum<Result>(s).value();
 189 }
 190
 191 #endif /* SQUID_SRC_SQUIDMATH_H */
 192