Fix for overflow bug in histogram scaling function in NetEq.
The experimental function that scales the histogram of inter-arrival times in NetEq suffered from an overflow bug. This caused unexpected increases in the calculated target level.
Bug: webrtc:8381
Change-Id: I2af4d22119fdc684b3cac838c9b317959af17a1f
Reviewed-on: https://webrtc-review.googlesource.com/30261
Commit-Queue: Ivo Creusen <ivoc@webrtc.org>
Reviewed-by: Henrik Lundin <henrik.lundin@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#21213}diff --git a/modules/audio_coding/neteq/delay_manager.cc b/modules/audio_coding/neteq/delay_manager.cc
index dc854c7..b70131d 100644
--- a/modules/audio_coding/neteq/delay_manager.cc
+++ b/modules/audio_coding/neteq/delay_manager.cc
@@ -398,18 +398,20 @@
RTC_DCHECK_EQ(old_packet_length % 10, 0);
RTC_DCHECK_EQ(new_packet_length % 10, 0);
IATVector new_histogram(histogram.size(), 0);
- int acc = 0;
+ int64_t acc = 0;
int time_counter = 0;
size_t new_histogram_idx = 0;
for (size_t i = 0; i < histogram.size(); i++) {
acc += histogram[i];
time_counter += old_packet_length;
// The bins should be scaled, to ensure the histogram still sums to one.
- const int scaled_acc = acc * new_packet_length / time_counter;
- int actually_used_acc = 0;
+ const int64_t scaled_acc = acc * new_packet_length / time_counter;
+ int64_t actually_used_acc = 0;
while (time_counter >= new_packet_length) {
- actually_used_acc += scaled_acc;
- new_histogram[new_histogram_idx] += scaled_acc;
+ const int64_t old_histogram_val = new_histogram[new_histogram_idx];
+ new_histogram[new_histogram_idx] =
+ rtc::saturated_cast<int>(old_histogram_val + scaled_acc);
+ actually_used_acc += new_histogram[new_histogram_idx] - old_histogram_val;
new_histogram_idx =
std::min(new_histogram_idx + 1, new_histogram.size() - 1);
time_counter -= new_packet_length;
@@ -418,11 +420,23 @@
acc -= actually_used_acc;
}
// If there is anything left in acc (due to rounding errors), add it to the
- // last bin.
- new_histogram[new_histogram_idx] += acc;
+ // last bin. If we cannot add everything to the last bin we need to add as
+ // much as possible to the bins after the last bin (this is only possible
+ // when compressing a histogram).
+ while (acc > 0 && new_histogram_idx < new_histogram.size()) {
+ const int64_t old_histogram_val = new_histogram[new_histogram_idx];
+ new_histogram[new_histogram_idx] =
+ rtc::saturated_cast<int>(old_histogram_val + acc);
+ acc -= new_histogram[new_histogram_idx] - old_histogram_val;
+ new_histogram_idx++;
+ }
RTC_DCHECK_EQ(histogram.size(), new_histogram.size());
- RTC_DCHECK_EQ(accumulate(histogram.begin(), histogram.end(), 0),
- accumulate(new_histogram.begin(), new_histogram.end(), 0));
+ if (acc == 0) {
+ // If acc is non-zero, we were not able to add everything to the new
+ // histogram, so this check will not hold.
+ RTC_DCHECK_EQ(accumulate(histogram.begin(), histogram.end(), 0ll),
+ accumulate(new_histogram.begin(), new_histogram.end(), 0ll));
+ }
return new_histogram;
}
diff --git a/modules/audio_coding/neteq/delay_manager_unittest.cc b/modules/audio_coding/neteq/delay_manager_unittest.cc
index 6dad4db..953bc6b 100644
--- a/modules/audio_coding/neteq/delay_manager_unittest.cc
+++ b/modules/audio_coding/neteq/delay_manager_unittest.cc
@@ -411,4 +411,39 @@
EXPECT_EQ(compressed_iat, expected_result);
}
+// Test if the histogram scaling function handles overflows correctly.
+TEST(DelayManagerIATScalingTest, OverflowTest) {
+ using IATVector = DelayManager::IATVector;
+ // Test a compression operation that can cause overflow.
+ IATVector iat = {733544448, 0, 0, 0, 0, 0, 0, 340197376, 0, 0, 0, 0, 0, 0};
+ IATVector expected_result = {733544448, 340197376, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0};
+ IATVector scaled_iat = DelayManager::ScaleHistogram(iat, 10, 60);
+ EXPECT_EQ(scaled_iat, expected_result);
+
+ iat = {655591163, 39962288, 360736736, 1930514, 4003853, 1782764,
+ 114119, 2072996, 0, 2149354, 0};
+ expected_result = {1056290187, 7717131, 2187115, 2149354, 0, 0,
+ 0, 0, 0, 0, 0};
+ scaled_iat = DelayManager::ScaleHistogram(iat, 20, 60);
+ EXPECT_EQ(scaled_iat, expected_result);
+
+ // In this test case we will not be able to add everything to the final bin in
+ // the scaled histogram. Check that the last bin doesn't overflow.
+ iat = {2000000000, 2000000000, 2000000000,
+ 2000000000, 2000000000, 2000000000};
+ expected_result = {666666666, 666666666, 666666666,
+ 666666667, 666666667, 2147483647};
+ scaled_iat = DelayManager::ScaleHistogram(iat, 60, 20);
+ EXPECT_EQ(scaled_iat, expected_result);
+
+ // In this test case we will not be able to add enough to each of the bins,
+ // so the values should be smeared out past the end of the normal range.
+ iat = {2000000000, 2000000000, 2000000000,
+ 2000000000, 2000000000, 2000000000};
+ expected_result = {2147483647, 2147483647, 2147483647,
+ 2147483647, 2147483647, 1262581765};
+ scaled_iat = DelayManager::ScaleHistogram(iat, 20, 60);
+ EXPECT_EQ(scaled_iat, expected_result);
+}
} // namespace webrtc