src/SquidMath.h

   1 /*
   2  * Copyright (C) 1996-2020 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
  14 #include <limits>
  15 #include <type_traits>
  16
  17 // TODO: Move to src/base/Math.h and drop the Math namespace
  18
  19 /* Math functions we define locally for Squid */
  20 namespace Math
  21 {
  22
  23 int intPercent(const int a, const int b);
  24 int64_t int64Percent(const int64_t a, const int64_t b);
  25 double doublePercent(const double, const double);
  26 int intAverage(const int, const int, int, const int);
  27 double doubleAverage(const double, const double, int, const int);
  28
  29 } // namespace Math
  30
  31 // If Sum() performance becomes important, consider using GCC and clang
  32 // built-ins like __builtin_add_overflow() instead of manual overflow checks.
  33
  34 /// std::enable_if_t replacement until C++14
  35 /// simplifies Sum() declarations below
  36 template <bool B, class T = void>
  37 using EnableIfType = typename std::enable_if<B,T>::type;
  38
  39 /// detects a pair of unsigned types
  40 /// reduces code duplication in Sum() declarations below
  41 template <typename T, typename U>
  42 using AllUnsigned = typename std::conditional<
  43                     std::is_unsigned<T>::value && std::is_unsigned<U>::value,
  44                     std::true_type,
  45                     std::false_type
  46                     >::type;
  47
  48 /// \returns a non-overflowing sum of the two unsigned arguments (or nothing)
  49 template <typename T, typename U, EnableIfType<AllUnsigned<T,U>::value, int> = 0>
  50 Optional<T>
  51 Sum(const T a, const U b) {
  52     // Instead of computing the largest type dynamically, we simply go by T and
  53     // reject cases like Sum(0, ULLONG_MAX) that would overflow on return.
  54     // TODO: Consider using std::common_type<T, U> in the return type instead.
  55     static_assert(sizeof(T) >= sizeof(U), "Sum() return type can fit its (unsigned) result");
  56
  57     // this optimized implementation relies on unsigned overflows
  58     static_assert(std::is_unsigned<T>::value, "the first Sum(a,b) argument is unsigned");
  59     static_assert(std::is_unsigned<U>::value, "the second Sum(a,b) argument is unsigned");
  60     const auto sum = a + b;
  61     // when a+b overflows, the result becomes smaller than any operand
  62     return (sum < a) ? Optional<T>() : Optional<T>(sum);
  63 }
  64
  65 /// \returns a non-overflowing sum of the two signed arguments (or nothing)
  66 template <typename T, typename U, EnableIfType<!AllUnsigned<T,U>::value, int> = 0>
  67 Optional<T> constexpr
  68 Sum(const T a, const U b) {
  69     // Instead of computing the largest type dynamically, we simply go by T and
  70     // reject cases like Sum(0, LLONG_MAX) that would overflow on return.
  71     static_assert(sizeof(T) >= sizeof(U), "Sum() return type can fit its (signed) result");
  72
  73     // tests below avoid undefined behavior of signed under/overflows
  74     return b >= 0 ?
  75            ((a > std::numeric_limits<U>::max() - b) ? Optional<T>() : Optional<T>(a + b)):
  76            ((a < std::numeric_limits<U>::min() - b) ? Optional<T>() : Optional<T>(a + b));
  77 }
  78
  79 /// \returns a non-overflowing sum of the arguments (or nothing)
  80 template <typename T, typename... Args>
  81 Optional<T>
  82 Sum(const T first, Args... args) {
  83     if (const auto others = Sum(args...)) {
  84         return Sum(first, others.value());
  85     } else {
  86         return Optional<T>();
  87     }
  88 }
  89
  90 #endif /* _SQUID_SRC_SQUIDMATH_H */
  91