Introduce integer division helpers with non-default rounding
There are multiple places in webrtc code where alternative than
default rounding is desired. Typically this rounding is inlined.
e.g. as (<x> + <y>/2) / <y> making code more clumpsy (<y> might be long expression)
and unsafe for large values of <x>
This change introduce small helpers to address both concerns.
Bug: None
Change-Id: Icd8dcee80a697b7c50ba0b2e50295087d2be8670
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/153354
Commit-Queue: Danil Chapovalov <danilchap@webrtc.org>
Reviewed-by: Karl Wiberg <kwiberg@webrtc.org>
Reviewed-by: Niels Moller <nisse@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#29222}
diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index 694823c..8f13b0a 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -339,6 +339,16 @@
]
}
+rtc_source_set("divide_round") {
+ sources = [
+ "numerics/divide_round.h",
+ ]
+ deps = [
+ ":checks",
+ ":safe_compare",
+ ]
+}
+
rtc_source_set("safe_compare") {
sources = [
"numerics/safe_compare.h",
@@ -1132,6 +1142,7 @@
"event_tracer_unittest.cc",
"event_unittest.cc",
"logging_unittest.cc",
+ "numerics/divide_round_unittest.cc",
"numerics/histogram_percentile_counter_unittest.cc",
"numerics/mod_ops_unittest.cc",
"numerics/moving_max_counter_unittest.cc",
@@ -1164,6 +1175,7 @@
}
deps = [
":checks",
+ ":divide_round",
":gunit_helpers",
":rate_limiter",
":rtc_base",
diff --git a/rtc_base/numerics/divide_round.h b/rtc_base/numerics/divide_round.h
new file mode 100644
index 0000000..77bc486
--- /dev/null
+++ b/rtc_base/numerics/divide_round.h
@@ -0,0 +1,48 @@
+/*
+ * Copyright 2019 The WebRTC Project Authors. All rights reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef RTC_BASE_NUMERICS_DIVIDE_ROUND_H_
+#define RTC_BASE_NUMERICS_DIVIDE_ROUND_H_
+
+#include <type_traits>
+
+#include "rtc_base/checks.h"
+#include "rtc_base/numerics/safe_compare.h"
+
+namespace webrtc {
+
+template <typename Dividend, typename Divisor>
+inline auto constexpr DivideRoundUp(Dividend dividend, Divisor divisor) {
+ static_assert(std::is_integral<Dividend>(), "");
+ static_assert(std::is_integral<Divisor>(), "");
+ RTC_DCHECK_GE(dividend, 0);
+ RTC_DCHECK_GT(divisor, 0);
+
+ auto quotient = dividend / divisor;
+ auto remainder = dividend % divisor;
+ return quotient + (remainder > 0 ? 1 : 0);
+}
+
+template <typename Dividend, typename Divisor>
+inline auto constexpr DivideRoundToNearest(Dividend dividend, Divisor divisor) {
+ static_assert(std::is_integral<Dividend>(), "");
+ static_assert(std::is_integral<Divisor>(), "");
+ RTC_DCHECK_GE(dividend, 0);
+ RTC_DCHECK_GT(divisor, 0);
+
+ auto half_of_divisor = (divisor - 1) / 2;
+ auto quotient = dividend / divisor;
+ auto remainder = dividend % divisor;
+ return quotient + (rtc::SafeGt(remainder, half_of_divisor) ? 1 : 0);
+}
+
+} // namespace webrtc
+
+#endif // RTC_BASE_NUMERICS_DIVIDE_ROUND_H_
diff --git a/rtc_base/numerics/divide_round_unittest.cc b/rtc_base/numerics/divide_round_unittest.cc
new file mode 100644
index 0000000..30ad494
--- /dev/null
+++ b/rtc_base/numerics/divide_round_unittest.cc
@@ -0,0 +1,161 @@
+/*
+ * Copyright 2019 The WebRTC Project Authors. All rights reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "rtc_base/numerics/divide_round.h"
+
+#include <limits>
+
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace {
+
+TEST(DivideRoundUpTest, CanBeUsedAsConstexpr) {
+ static_assert(DivideRoundUp(5, 1) == 5, "");
+ static_assert(DivideRoundUp(5, 2) == 3, "");
+}
+
+TEST(DivideRoundUpTest, ReturnsZeroForZeroDividend) {
+ EXPECT_EQ(DivideRoundUp(uint8_t{0}, 1), 0);
+ EXPECT_EQ(DivideRoundUp(uint8_t{0}, 3), 0);
+ EXPECT_EQ(DivideRoundUp(int{0}, 1), 0);
+ EXPECT_EQ(DivideRoundUp(int{0}, 3), 0);
+}
+
+TEST(DivideRoundUpTest, WorksForMaxDividend) {
+ EXPECT_EQ(DivideRoundUp(uint8_t{255}, 2), 128);
+ EXPECT_EQ(DivideRoundUp(std::numeric_limits<int>::max(), 2),
+ std::numeric_limits<int>::max() / 2 +
+ (std::numeric_limits<int>::max() % 2));
+}
+
+TEST(DivideRoundToNearestTest, CanBeUsedAsConstexpr) {
+ static constexpr int kOne = DivideRoundToNearest(5, 4);
+ static constexpr int kTwo = DivideRoundToNearest(7, 4);
+ static_assert(kOne == 1, "");
+ static_assert(kTwo == 2, "");
+}
+
+TEST(DivideRoundToNearestTest, DivideByOddNumber) {
+ EXPECT_EQ(DivideRoundToNearest(0, 3), 0);
+ EXPECT_EQ(DivideRoundToNearest(1, 3), 0);
+ EXPECT_EQ(DivideRoundToNearest(2, 3), 1);
+ EXPECT_EQ(DivideRoundToNearest(3, 3), 1);
+ EXPECT_EQ(DivideRoundToNearest(4, 3), 1);
+ EXPECT_EQ(DivideRoundToNearest(5, 3), 2);
+ EXPECT_EQ(DivideRoundToNearest(6, 3), 2);
+}
+
+TEST(DivideRoundToNearestTest, DivideByEvenNumberTieRoundsUp) {
+ EXPECT_EQ(DivideRoundToNearest(0, 4), 0);
+ EXPECT_EQ(DivideRoundToNearest(1, 4), 0);
+ EXPECT_EQ(DivideRoundToNearest(2, 4), 1);
+ EXPECT_EQ(DivideRoundToNearest(3, 4), 1);
+ EXPECT_EQ(DivideRoundToNearest(4, 4), 1);
+ EXPECT_EQ(DivideRoundToNearest(5, 4), 1);
+ EXPECT_EQ(DivideRoundToNearest(6, 4), 2);
+ EXPECT_EQ(DivideRoundToNearest(7, 4), 2);
+}
+
+TEST(DivideRoundToNearestTest, LargeDivisor) {
+ EXPECT_EQ(DivideRoundToNearest(std::numeric_limits<int>::max() - 1,
+ std::numeric_limits<int>::max()),
+ 1);
+}
+
+TEST(DivideRoundToNearestTest, DivideSmallTypeByLargeType) {
+ uint8_t small = 0xff;
+ uint16_t large = 0xffff;
+ EXPECT_EQ(DivideRoundToNearest(small, large), 0);
+}
+
+using IntegerTypes = ::testing::Types<int8_t,
+ int16_t,
+ int32_t,
+ int64_t,
+ uint8_t,
+ uint16_t,
+ uint32_t,
+ uint64_t>;
+template <typename T>
+class DivideRoundTypedTest : public ::testing::Test {};
+TYPED_TEST_SUITE(DivideRoundTypedTest, IntegerTypes);
+
+TYPED_TEST(DivideRoundTypedTest, RoundToNearestPreservesType) {
+ static_assert(
+ std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, int8_t{3})),
+ decltype(TypeParam{100} / int8_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, int16_t{3})),
+ decltype(TypeParam{100} / int16_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, int32_t{3})),
+ decltype(TypeParam{100} / int32_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, int64_t{3})),
+ decltype(TypeParam{100} / int64_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, uint8_t{3})),
+ decltype(TypeParam{100} / uint8_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, uint16_t{3})),
+ decltype(TypeParam{100} / uint16_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, uint32_t{3})),
+ decltype(TypeParam{100} / uint32_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, uint64_t{3})),
+ decltype(TypeParam{100} / uint64_t{3})>::value,
+ "");
+}
+
+TYPED_TEST(DivideRoundTypedTest, RoundUpPreservesType) {
+ static_assert(std::is_same<decltype(DivideRoundUp(TypeParam{100}, int8_t{3})),
+ decltype(TypeParam{100} / int8_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundUp(TypeParam{100}, int16_t{3})),
+ decltype(TypeParam{100} / int16_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundUp(TypeParam{100}, int32_t{3})),
+ decltype(TypeParam{100} / int32_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundUp(TypeParam{100}, int64_t{3})),
+ decltype(TypeParam{100} / int64_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundUp(TypeParam{100}, uint8_t{3})),
+ decltype(TypeParam{100} / uint8_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundUp(TypeParam{100}, uint16_t{3})),
+ decltype(TypeParam{100} / uint16_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundUp(TypeParam{100}, uint32_t{3})),
+ decltype(TypeParam{100} / uint32_t{3})>::value,
+ "");
+ static_assert(
+ std::is_same<decltype(DivideRoundUp(TypeParam{100}, uint64_t{3})),
+ decltype(TypeParam{100} / uint64_t{3})>::value,
+ "");
+}
+
+} // namespace
+} // namespace webrtc
