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 */
21namespace Math
22{
23
24int intPercent(const int a, const int b);
25int64_t int64Percent(const int64_t a, const int64_t b);
26double doublePercent(const double, const double);
27int intAverage(const int, const int, int, const int);
28double 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
37template <bool B, class T = void>
39
42template <typename T, typename U>
43using 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.
51template <typename A, typename B>
52constexpr bool
53Less(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
65template<typename T>
66constexpr 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.
80template <typename S, typename A, typename B, EnableIfType<AllUnsigned<A,B>::value, int> = 0>
82IncreaseSumInternal(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
117template <typename S, typename A, typename B, EnableIfType<!AllUnsigned<A,B>::value, int> = 0>
118Optional<S> constexpr
119IncreaseSumInternal(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
149template <typename S, typename T>
151IncreaseSum(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
160template <typename S, typename T, typename... Args>
162IncreaseSum(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
171template <typename SummationType, typename... Args>
173NaturalSum(const Args... args) {
174 return IncreaseSum<SummationType>(0, args...);
175}
176
180template <typename S, typename... Args>
181S
182SetToNaturalSumOrMax(S &var, const Args... args)
183{
184 var = NaturalSum<S>(args...).value_or(std::numeric_limits<S>::max());
185 return var;
186}
187
190template <typename Result, typename Source>
191Result
192NaturalCast(const Source s)
193{
194 return NaturalSum<Result>(s).value();
195}
196
197#endif /* _SQUID_SRC_SQUIDMATH_H */
198
#define false
Definition: GnuRegex.c:240
typename std::enable_if< B, T >::type EnableIfType
Definition: SquidMath.h:38
Result NaturalCast(const Source s)
Definition: SquidMath.h:192
S SetToNaturalSumOrMax(S &var, const Args... args)
Definition: SquidMath.h:182
Optional< SummationType > NaturalSum(const Args... args)
Definition: SquidMath.h:173
Optional< S > IncreaseSumInternal(const A a, const B b)
Definition: SquidMath.h:82
constexpr bool AssertNaturalType()
ensure that T is supported by NaturalSum() and friends
Definition: SquidMath.h:67
Optional< S > IncreaseSum(const S s, const T t)
argument pack expansion termination for IncreaseSum<S, T, Args...>()
Definition: SquidMath.h:151
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 Less(const A a, const B b)
whether integer a is less than integer b, with correct overflow handling
Definition: SquidMath.h:53
squidaio_request_t * head
Definition: aiops.cc:126
(limited) std::optional replacement (until we upgrade to C++17)
Definition: Optional.h:30
A const & max(A const &lhs, A const &rhs)
int type
Definition: errorpage.cc:152
static uint32 A
Definition: md4.c:43
static uint32 B
Definition: md4.c:43
Definition: SquidMath.h:22
int intPercent(const int a, const int b)
Definition: SquidMath.cc:13
double doubleAverage(const double, const double, int, const int)
Definition: SquidMath.cc:31
double doublePercent(const double, const double)
Definition: SquidMath.cc:25
int64_t int64Percent(const int64_t a, const int64_t b)
Definition: SquidMath.cc:19
int intAverage(const int, const int, int, const int)
Definition: SquidMath.cc:40

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors