SquidMath.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2022 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/Optional.h"
14 
15 #include <limits>
16 #include <type_traits>
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 
37 template <bool B, class T = void>
39 
42 template <typename T, typename U>
43 using AllUnsigned = typename std::conditional<
44  std::is_unsigned<T>::value && std::is_unsigned<U>::value,
45  std::true_type,
46  std::false_type
47  >::type;
48 
49 // TODO: Replace with std::cmp_less() after migrating to C++20.
51 template <typename A, typename B>
52 constexpr bool
53 Less(const A a, const B b) {
54  // The casts below make standard C++ integer conversions explicit. They
55  // quell compiler warnings about signed/unsigned comparison. The first two
56  // lines exclude different-sign a and b, making the casts/comparison safe.
57  using AB = typename std::common_type<A, B>::type;
58  return
59  (a >= 0 && b < 0) ? false :
60  (a < 0 && b >= 0) ? true :
61  /* (a >= 0) == (b >= 0) */ static_cast<AB>(a) < static_cast<AB>(b);
62 }
63 
65 template<typename T>
66 constexpr bool
68 {
69  static_assert(std::numeric_limits<T>::is_bounded, "std::numeric_limits<T>::max() is meaningful");
70  static_assert(std::numeric_limits<T>::is_exact, "no silent loss of precision");
71  static_assert(!std::is_enum<T>::value, "no silent creation of non-enumerated values");
72  return true; // for static_assert convenience in C++11 constexpr callers
73 }
74 
75 // TODO: Investigate whether this optimization can be expanded to [signed] types
76 // A and B when std::numeric_limits<decltype(A(0)+B(0))>::is_modulo is true.
80 template <typename S, typename A, typename B, EnableIfType<AllUnsigned<A,B>::value, int> = 0>
82 IncreaseSumInternal(const A a, const B b) {
83  // paranoid: AllUnsigned<A,B> precondition established that already
84  static_assert(std::is_unsigned<A>::value, "AllUnsigned dispatch worked for A");
85  static_assert(std::is_unsigned<B>::value, "AllUnsigned dispatch worked for B");
86 
87  // TODO: Just call AssertNaturalType() after upgrading to C++14.
88  static_assert(AssertNaturalType<S>(), "S is a supported type");
89  static_assert(AssertNaturalType<A>(), "A is a supported type");
90  static_assert(AssertNaturalType<B>(), "B is a supported type");
91 
92  // we should only be called by IncreaseSum(); it forces integer promotion
93  static_assert(std::is_same<A, decltype(+a)>::value, "a will not be promoted");
94  static_assert(std::is_same<B, decltype(+b)>::value, "b will not be promoted");
95  // and without integer promotions, a sum of unsigned integers is unsigned
96  static_assert(std::is_unsigned<decltype(a+b)>::value, "a+b is unsigned");
97 
98  // with integer promotions ruled out, a or b can only undergo integer
99  // conversion to the higher rank type (A or B, we do not know which)
100  using AB = typename std::common_type<A, B>::type;
101  static_assert(std::is_same<AB, A>::value || std::is_same<AB, B>::value, "no unexpected conversions");
102  static_assert(std::is_same<AB, decltype(a+b)>::value, "lossless assignment");
103  const AB sum = a + b;
104 
105  static_assert(std::numeric_limits<AB>::is_modulo, "we can detect overflows");
106  // 1. modulo math: overflowed sum is smaller than any of its operands
107  // 2. the sum may overflow S (i.e. the return base type)
108  // We do not need Less() here because we compare promoted unsigned types.
109  return (sum >= a && sum <= std::numeric_limits<S>::max()) ?
110  Optional<S>(sum) : Optional<S>();
111 }
112 
117 template <typename S, typename A, typename B, EnableIfType<!AllUnsigned<A,B>::value, int> = 0>
118 Optional<S> constexpr
119 IncreaseSumInternal(const A a, const B b) {
120  static_assert(AssertNaturalType<S>(), "S is a supported type");
121  static_assert(AssertNaturalType<A>(), "A is a supported type");
122  static_assert(AssertNaturalType<B>(), "B is a supported type");
123 
124  // we should only be called by IncreaseSum() that does integer promotion
125  static_assert(std::is_same<A, decltype(+a)>::value, "a will not be promoted");
126  static_assert(std::is_same<B, decltype(+b)>::value, "b will not be promoted");
127 
128  return
129  // We could support a non-under/overflowing sum of negative numbers, but
130  // our callers use negative values specially (e.g., for do-not-use or
131  // do-not-limit settings) and are not supposed to do math with them.
132  (a < 0 || b < 0) ? Optional<S>() :
133  // To avoid undefined behavior of signed overflow, we must not compute
134  // the raw a+b sum if it may overflow. When A is not B, a or b undergoes
135  // (safe for non-negatives) integer conversion in these expressions, so
136  // we do not know the resulting a+b type AB and its maximum. We must
137  // also detect subsequent casting-to-S overflows.
138  // Overflow condition: (a + b > maxAB) or (a + b > maxS).
139  // A is an integer promotion of S, so maxS <= maxA <= maxAB.
140  // Since maxS <= maxAB, it is sufficient to just check: a + b > maxS,
141  // which is the same as the overflow-safe condition here: maxS - a < b.
142  // Finally, (maxS - a) cannot overflow because a is not negative and
143  // cannot underflow because a is a promotion of s: 0 <= a <= maxS.
145  Optional<S>(a + b);
146 }
147 
149 template <typename S, typename T>
151 IncreaseSum(const S s, const T t)
152 {
153  // Force (always safe) integer promotions now, to give EnableIfType<>
154  // promoted types instead of entering IncreaseSumInternal<AllUnsigned>(s,t)
155  // but getting a _signed_ promoted value of s or t in s + t.
156  return IncreaseSumInternal<S>(+s, +t);
157 }
158 
160 template <typename S, typename T, typename... Args>
162 IncreaseSum(const S sum, const T t, const Args... args) {
163  if (const auto head = IncreaseSum(sum, t)) {
164  return IncreaseSum(head.value(), args...);
165  } else {
166  return Optional<S>();
167  }
168 }
169 
171 template <typename SummationType, typename... Args>
173 NaturalSum(const Args... args) {
174  return IncreaseSum<SummationType>(0, args...);
175 }
176 
180 template <typename S, typename... Args>
181 S
182 SetToNaturalSumOrMax(S &var, const Args... args)
183 {
184  var = NaturalSum<S>(args...).value_or(std::numeric_limits<S>::max());
185  return var;
186 }
187 
188 #endif /* _SQUID_SRC_SQUIDMATH_H */
189 
Optional< SummationType > NaturalSum(const Args... args)
Definition: SquidMath.h:173
Optional< S > IncreaseSum(const S s, const T t)
argument pack expansion termination for IncreaseSum<S, T, Args...>()
Definition: SquidMath.h:151
Optional< S > IncreaseSumInternal(const A a, const B b)
Definition: SquidMath.h:82
int intPercent(const int a, const int b)
Definition: SquidMath.cc:13
Definition: SquidMath.h:22
int type
Definition: errorpage.cc:152
int intAverage(const int, const int, int, const int)
Definition: SquidMath.cc:40
(limited) std::optional replacement (until we upgrade to C++17)
Definition: Optional.h:29
A const & max(A const &lhs, A const &rhs)
double doublePercent(const double, const double)
Definition: SquidMath.cc:25
typename std::conditional< std::is_unsigned< T >::value &&std::is_unsigned< U >::value, std::true_type, std::false_type >::type AllUnsigned
Definition: SquidMath.h:47
constexpr bool AssertNaturalType()
ensure that T is supported by NaturalSum() and friends
Definition: SquidMath.h:67
static uint32 A
Definition: md4.c:43
typename std::enable_if< B, T >::type EnableIfType
Definition: SquidMath.h:38
S SetToNaturalSumOrMax(S &var, const Args... args)
Definition: SquidMath.h:182
int64_t int64Percent(const int64_t a, const int64_t b)
Definition: SquidMath.cc:19
double doubleAverage(const double, const double, int, const int)
Definition: SquidMath.cc:31
squidaio_request_t * head
Definition: aiops.cc:126
static uint32 B
Definition: md4.c:43
constexpr bool Less(const A a, const B b)
whether integer a is less than integer b, with correct overflow handling
Definition: SquidMath.h:53
#define false
Definition: GnuRegex.c:233

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors