123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246 |
- /*
- * Copyright 2016-present Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- #include <folly/Math.h>
- #include <algorithm>
- #include <type_traits>
- #include <utility>
- #include <vector>
- #include <glog/logging.h>
- #include <folly/Portability.h>
- #include <folly/portability/GTest.h>
- using namespace folly;
- using namespace folly::detail;
- namespace {
- // Workaround for https://llvm.org/bugs/show_bug.cgi?id=16404,
- // issues with __int128 multiplication and UBSAN
- template <typename T>
- T mul(T lhs, T rhs) {
- if (rhs < 0) {
- rhs = -rhs;
- lhs = -lhs;
- }
- T accum = 0;
- while (rhs != 0) {
- if ((rhs & 1) != 0) {
- accum += lhs;
- }
- lhs += lhs;
- rhs >>= 1;
- }
- return accum;
- }
- template <typename T, typename B>
- T referenceDivFloor(T numer, T denom) {
- // rv = largest integral value <= numer / denom
- B n = numer;
- B d = denom;
- if (d < 0) {
- d = -d;
- n = -n;
- }
- B r = n / d;
- while (mul(r, d) > n) {
- --r;
- }
- while (mul(r + 1, d) <= n) {
- ++r;
- }
- T rv = static_cast<T>(r);
- assert(static_cast<B>(rv) == r);
- return rv;
- }
- template <typename T, typename B>
- T referenceDivCeil(T numer, T denom) {
- // rv = smallest integral value >= numer / denom
- B n = numer;
- B d = denom;
- if (d < 0) {
- d = -d;
- n = -n;
- }
- B r = n / d;
- while (mul(r, d) < n) {
- ++r;
- }
- while (mul(r - 1, d) >= n) {
- --r;
- }
- T rv = static_cast<T>(r);
- assert(static_cast<B>(rv) == r);
- return rv;
- }
- template <typename T, typename B>
- T referenceDivRoundAway(T numer, T denom) {
- if ((numer < 0) != (denom < 0)) {
- return referenceDivFloor<T, B>(numer, denom);
- } else {
- return referenceDivCeil<T, B>(numer, denom);
- }
- }
- template <typename T>
- std::vector<T> cornerValues() {
- std::vector<T> rv;
- for (T i = 1; i < 24; ++i) {
- rv.push_back(i);
- rv.push_back(T(std::numeric_limits<T>::max() / i));
- rv.push_back(T(std::numeric_limits<T>::max() - i));
- rv.push_back(T(std::numeric_limits<T>::max() / T(2) - i));
- if (std::is_signed<T>::value) {
- rv.push_back(-i);
- rv.push_back(T(std::numeric_limits<T>::min() / i));
- rv.push_back(T(std::numeric_limits<T>::min() + i));
- rv.push_back(T(std::numeric_limits<T>::min() / T(2) + i));
- }
- }
- return rv;
- }
- template <typename A, typename B, typename C>
- void runDivTests() {
- using T = decltype(static_cast<A>(1) / static_cast<B>(1));
- auto numers = cornerValues<A>();
- numers.push_back(0);
- auto denoms = cornerValues<B>();
- for (A n : numers) {
- for (B d : denoms) {
- if (std::is_signed<T>::value && n == std::numeric_limits<T>::min() &&
- d == static_cast<T>(-1)) {
- // n / d overflows in two's complement
- continue;
- }
- EXPECT_EQ(divCeil(n, d), (referenceDivCeil<T, C>(n, d))) << n << "/" << d;
- EXPECT_EQ(divFloor(n, d), (referenceDivFloor<T, C>(n, d)))
- << n << "/" << d;
- EXPECT_EQ(divTrunc(n, d), n / d) << n << "/" << d;
- EXPECT_EQ(divRoundAway(n, d), (referenceDivRoundAway<T, C>(n, d)))
- << n << "/" << d;
- T nn = n;
- T dd = d;
- EXPECT_EQ(divCeilBranchless(nn, dd), divCeilBranchful(nn, dd));
- EXPECT_EQ(divFloorBranchless(nn, dd), divFloorBranchful(nn, dd));
- EXPECT_EQ(divRoundAwayBranchless(nn, dd), divRoundAwayBranchful(nn, dd));
- }
- }
- }
- } // namespace
- TEST(Bits, divTestInt8) {
- runDivTests<int8_t, int8_t, int64_t>();
- runDivTests<int8_t, uint8_t, int64_t>();
- runDivTests<int8_t, int16_t, int64_t>();
- runDivTests<int8_t, uint16_t, int64_t>();
- runDivTests<int8_t, int32_t, int64_t>();
- runDivTests<int8_t, uint32_t, int64_t>();
- #if FOLLY_HAVE_INT128_T
- runDivTests<int8_t, int64_t, __int128>();
- runDivTests<int8_t, uint64_t, __int128>();
- #endif
- }
- TEST(Bits, divTestInt16) {
- runDivTests<int16_t, int8_t, int64_t>();
- runDivTests<int16_t, uint8_t, int64_t>();
- runDivTests<int16_t, int16_t, int64_t>();
- runDivTests<int16_t, uint16_t, int64_t>();
- runDivTests<int16_t, int32_t, int64_t>();
- runDivTests<int16_t, uint32_t, int64_t>();
- #if FOLLY_HAVE_INT128_T
- runDivTests<int16_t, int64_t, __int128>();
- runDivTests<int16_t, uint64_t, __int128>();
- #endif
- }
- TEST(Bits, divTestInt32) {
- runDivTests<int32_t, int8_t, int64_t>();
- runDivTests<int32_t, uint8_t, int64_t>();
- runDivTests<int32_t, int16_t, int64_t>();
- runDivTests<int32_t, uint16_t, int64_t>();
- runDivTests<int32_t, int32_t, int64_t>();
- runDivTests<int32_t, uint32_t, int64_t>();
- #if FOLLY_HAVE_INT128_T
- runDivTests<int32_t, int64_t, __int128>();
- runDivTests<int32_t, uint64_t, __int128>();
- #endif
- }
- #if FOLLY_HAVE_INT128_T
- TEST(Bits, divTestInt64) {
- runDivTests<int64_t, int8_t, __int128>();
- runDivTests<int64_t, uint8_t, __int128>();
- runDivTests<int64_t, int16_t, __int128>();
- runDivTests<int64_t, uint16_t, __int128>();
- runDivTests<int64_t, int32_t, __int128>();
- runDivTests<int64_t, uint32_t, __int128>();
- runDivTests<int64_t, int64_t, __int128>();
- runDivTests<int64_t, uint64_t, __int128>();
- }
- #endif
- TEST(Bits, divTestUint8) {
- runDivTests<uint8_t, int8_t, int64_t>();
- runDivTests<uint8_t, uint8_t, int64_t>();
- runDivTests<uint8_t, int16_t, int64_t>();
- runDivTests<uint8_t, uint16_t, int64_t>();
- runDivTests<uint8_t, int32_t, int64_t>();
- runDivTests<uint8_t, uint32_t, int64_t>();
- #if FOLLY_HAVE_INT128_T
- runDivTests<uint8_t, int64_t, __int128>();
- runDivTests<uint8_t, uint64_t, __int128>();
- #endif
- }
- TEST(Bits, divTestUint16) {
- runDivTests<uint16_t, int8_t, int64_t>();
- runDivTests<uint16_t, uint8_t, int64_t>();
- runDivTests<uint16_t, int16_t, int64_t>();
- runDivTests<uint16_t, uint16_t, int64_t>();
- runDivTests<uint16_t, int32_t, int64_t>();
- runDivTests<uint16_t, uint32_t, int64_t>();
- #if FOLLY_HAVE_INT128_T
- runDivTests<uint16_t, int64_t, __int128>();
- runDivTests<uint16_t, uint64_t, __int128>();
- #endif
- }
- TEST(Bits, divTestUint32) {
- runDivTests<uint32_t, int8_t, int64_t>();
- runDivTests<uint32_t, uint8_t, int64_t>();
- runDivTests<uint32_t, int16_t, int64_t>();
- runDivTests<uint32_t, uint16_t, int64_t>();
- runDivTests<uint32_t, int32_t, int64_t>();
- runDivTests<uint32_t, uint32_t, int64_t>();
- #if FOLLY_HAVE_INT128_T
- runDivTests<uint32_t, int64_t, __int128>();
- runDivTests<uint32_t, uint64_t, __int128>();
- #endif
- }
- #if FOLLY_HAVE_INT128_T
- TEST(Bits, divTestUint64) {
- runDivTests<uint64_t, int8_t, __int128>();
- runDivTests<uint64_t, uint8_t, __int128>();
- runDivTests<uint64_t, int16_t, __int128>();
- runDivTests<uint64_t, uint16_t, __int128>();
- runDivTests<uint64_t, int32_t, __int128>();
- runDivTests<uint64_t, uint32_t, __int128>();
- runDivTests<uint64_t, int64_t, __int128>();
- runDivTests<uint64_t, uint64_t, __int128>();
- }
- #endif
|