Refactor DelayManager into separate Histogram class and make it injectable for testing purposes.
Change-Id: I98aa3f992169e598fc1a3dd850400183395fe1fe
Bug: webrtc:10333
Reviewed-on: https://webrtc-review.googlesource.com/c/123445
Commit-Queue: Jakob Ivarsson‎ <jakobi@webrtc.org>
Reviewed-by: Minyue Li <minyue@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#26797}diff --git a/modules/audio_coding/BUILD.gn b/modules/audio_coding/BUILD.gn
index 7999cc5..693fa65 100644
--- a/modules/audio_coding/BUILD.gn
+++ b/modules/audio_coding/BUILD.gn
@@ -943,6 +943,8 @@
"neteq/expand.h",
"neteq/expand_uma_logger.cc",
"neteq/expand_uma_logger.h",
+ "neteq/histogram.cc",
+ "neteq/histogram.h",
"neteq/include/neteq.h",
"neteq/merge.cc",
"neteq/merge.h",
@@ -999,6 +1001,7 @@
"../../rtc_base/system:fallthrough",
"../../system_wrappers:field_trial",
"../../system_wrappers:metrics",
+ "//third_party/abseil-cpp/absl/memory",
"//third_party/abseil-cpp/absl/strings",
"//third_party/abseil-cpp/absl/types:optional",
]
@@ -1969,6 +1972,7 @@
"neteq/dtmf_buffer_unittest.cc",
"neteq/dtmf_tone_generator_unittest.cc",
"neteq/expand_unittest.cc",
+ "neteq/histogram_unittest.cc",
"neteq/merge_unittest.cc",
"neteq/mock/mock_buffer_level_filter.h",
"neteq/mock/mock_decoder_database.h",
@@ -1977,6 +1981,7 @@
"neteq/mock/mock_dtmf_buffer.h",
"neteq/mock/mock_dtmf_tone_generator.h",
"neteq/mock/mock_expand.h",
+ "neteq/mock/mock_histogram.h",
"neteq/mock/mock_packet_buffer.h",
"neteq/mock/mock_red_payload_splitter.h",
"neteq/mock/mock_statistics_calculator.h",
diff --git a/modules/audio_coding/neteq/decision_logic_unittest.cc b/modules/audio_coding/neteq/decision_logic_unittest.cc
index ebc24d4..2e9b923 100644
--- a/modules/audio_coding/neteq/decision_logic_unittest.cc
+++ b/modules/audio_coding/neteq/decision_logic_unittest.cc
@@ -31,11 +31,12 @@
TickTimer tick_timer;
PacketBuffer packet_buffer(10, &tick_timer);
DelayPeakDetector delay_peak_detector(&tick_timer, false);
- DelayManager delay_manager(240, 0, false, &delay_peak_detector, &tick_timer);
+ auto delay_manager =
+ DelayManager::Create(240, 0, false, &delay_peak_detector, &tick_timer);
BufferLevelFilter buffer_level_filter;
DecisionLogic* logic = DecisionLogic::Create(
fs_hz, output_size_samples, false, &decoder_database, packet_buffer,
- &delay_manager, &buffer_level_filter, &tick_timer);
+ delay_manager.get(), &buffer_level_filter, &tick_timer);
delete logic;
}
@@ -48,14 +49,15 @@
TickTimer tick_timer;
PacketBuffer packet_buffer(10, &tick_timer);
DelayPeakDetector delay_peak_detector(&tick_timer, false);
- DelayManager delay_manager(240, 0, false, &delay_peak_detector, &tick_timer);
+ auto delay_manager =
+ DelayManager::Create(240, 0, false, &delay_peak_detector, &tick_timer);
BufferLevelFilter buffer_level_filter;
{
test::ScopedFieldTrials field_trial(
"WebRTC-Audio-NetEqPostponeDecodingAfterExpand/Enabled/");
DecisionLogic logic(kFsHz, kOutputSizeSamples, false, &decoder_database,
- packet_buffer, &delay_manager, &buffer_level_filter,
- &tick_timer);
+ packet_buffer, delay_manager.get(),
+ &buffer_level_filter, &tick_timer);
EXPECT_EQ(kDefaultPostponeDecodingLevel,
logic.postpone_decoding_level_for_test());
}
@@ -63,24 +65,24 @@
test::ScopedFieldTrials field_trial(
"WebRTC-Audio-NetEqPostponeDecodingAfterExpand/Enabled-65/");
DecisionLogic logic(kFsHz, kOutputSizeSamples, false, &decoder_database,
- packet_buffer, &delay_manager, &buffer_level_filter,
- &tick_timer);
+ packet_buffer, delay_manager.get(),
+ &buffer_level_filter, &tick_timer);
EXPECT_EQ(65, logic.postpone_decoding_level_for_test());
}
{
test::ScopedFieldTrials field_trial(
"WebRTC-Audio-NetEqPostponeDecodingAfterExpand/Disabled/");
DecisionLogic logic(kFsHz, kOutputSizeSamples, false, &decoder_database,
- packet_buffer, &delay_manager, &buffer_level_filter,
- &tick_timer);
+ packet_buffer, delay_manager.get(),
+ &buffer_level_filter, &tick_timer);
EXPECT_EQ(0, logic.postpone_decoding_level_for_test());
}
{
test::ScopedFieldTrials field_trial(
"WebRTC-Audio-NetEqPostponeDecodingAfterExpand/Enabled--1/");
DecisionLogic logic(kFsHz, kOutputSizeSamples, false, &decoder_database,
- packet_buffer, &delay_manager, &buffer_level_filter,
- &tick_timer);
+ packet_buffer, delay_manager.get(),
+ &buffer_level_filter, &tick_timer);
EXPECT_EQ(kDefaultPostponeDecodingLevel,
logic.postpone_decoding_level_for_test());
}
@@ -88,8 +90,8 @@
test::ScopedFieldTrials field_trial(
"WebRTC-Audio-NetEqPostponeDecodingAfterExpand/Enabled-101/");
DecisionLogic logic(kFsHz, kOutputSizeSamples, false, &decoder_database,
- packet_buffer, &delay_manager, &buffer_level_filter,
- &tick_timer);
+ packet_buffer, delay_manager.get(),
+ &buffer_level_filter, &tick_timer);
EXPECT_EQ(kDefaultPostponeDecodingLevel,
logic.postpone_decoding_level_for_test());
}
diff --git a/modules/audio_coding/neteq/delay_manager.cc b/modules/audio_coding/neteq/delay_manager.cc
index d2dd85d..e22a408 100644
--- a/modules/audio_coding/neteq/delay_manager.cc
+++ b/modules/audio_coding/neteq/delay_manager.cc
@@ -17,6 +17,7 @@
#include <numeric>
#include <string>
+#include "absl/memory/memory.h"
#include "modules/audio_coding/neteq/delay_peak_detector.h"
#include "modules/include/module_common_types_public.h"
#include "rtc_base/checks.h"
@@ -27,16 +28,15 @@
namespace {
-constexpr int kLimitProbability = 53687091; // 1/20 in Q30.
-constexpr int kLimitProbabilityStreaming = 536871; // 1/2000 in Q30.
-constexpr int kMaxStreamingPeakPeriodMs = 600000; // 10 minutes in ms.
+constexpr int kLimitProbability = 1020054733; // 19/20 in Q30.
+constexpr int kLimitProbabilityStreaming = 1073204953; // 1999/2000 in Q30.
+constexpr int kMaxStreamingPeakPeriodMs = 600000; // 10 minutes in ms.
constexpr int kCumulativeSumDrift = 2; // Drift term for cumulative sum
// |iat_cumulative_sum_|.
constexpr int kMinBaseMinimumDelayMs = 0;
constexpr int kMaxBaseMinimumDelayMs = 10000;
-// Steady-state forgetting factor for |iat_vector_|, 0.9993 in Q15.
-constexpr int kIatFactor_ = 32745;
-constexpr int kMaxIat = 64; // Max inter-arrival time to register.
+constexpr int kIatFactor = 32745; // 0.9993 in Q15.
+constexpr int kMaxIat = 64; // Max inter-arrival time to register.
constexpr int kMaxReorderedPackets =
10; // Max number of consecutive reordered packets.
@@ -51,8 +51,8 @@
double percentile = -1.0;
if (sscanf(field_trial_string.c_str(), "Enabled-%lf", &percentile) == 1 &&
percentile >= 0.0 && percentile <= 100.0) {
- return absl::make_optional<int>(static_cast<int>(
- (1 << 30) * (100.0 - percentile) / 100.0 + 0.5)); // in Q30.
+ return absl::make_optional<int>(
+ static_cast<int>((1 << 30) * percentile / 100.0 + 0.5)); // in Q30.
} else {
RTC_LOG(LS_WARNING) << "Invalid parameter for "
<< kForceTargetDelayPercentileFieldTrial
@@ -70,11 +70,11 @@
int base_minimum_delay_ms,
bool enable_rtx_handling,
DelayPeakDetector* peak_detector,
- const TickTimer* tick_timer)
+ const TickTimer* tick_timer,
+ std::unique_ptr<Histogram> iat_histogram)
: first_packet_received_(false),
max_packets_in_buffer_(max_packets_in_buffer),
- iat_vector_(kMaxIat + 1, 0),
- iat_factor_(0),
+ iat_histogram_(std::move(iat_histogram)),
tick_timer_(tick_timer),
base_minimum_delay_ms_(base_minimum_delay_ms),
effective_minimum_delay_ms_(base_minimum_delay_ms),
@@ -95,33 +95,26 @@
forced_limit_probability_(GetForcedLimitProbability()),
enable_rtx_handling_(enable_rtx_handling) {
assert(peak_detector); // Should never be NULL.
+ RTC_CHECK(iat_histogram_);
RTC_DCHECK_GE(base_minimum_delay_ms_, 0);
Reset();
}
+std::unique_ptr<DelayManager> DelayManager::Create(
+ size_t max_packets_in_buffer,
+ int base_minimum_delay_ms,
+ bool enable_rtx_handling,
+ DelayPeakDetector* peak_detector,
+ const TickTimer* tick_timer) {
+ return absl::make_unique<DelayManager>(
+ max_packets_in_buffer, base_minimum_delay_ms, enable_rtx_handling,
+ peak_detector, tick_timer,
+ absl::make_unique<Histogram>(kMaxIat + 1, kIatFactor));
+}
+
DelayManager::~DelayManager() {}
-const DelayManager::IATVector& DelayManager::iat_vector() const {
- return iat_vector_;
-}
-
-// Set the histogram vector to an exponentially decaying distribution
-// iat_vector_[i] = 0.5^(i+1), i = 0, 1, 2, ...
-// iat_vector_ is in Q30.
-void DelayManager::ResetHistogram() {
- // Set temp_prob to (slightly more than) 1 in Q14. This ensures that the sum
- // of iat_vector_ is 1.
- uint16_t temp_prob = 0x4002; // 16384 + 2 = 100000000000010 binary.
- IATVector::iterator it = iat_vector_.begin();
- for (; it < iat_vector_.end(); it++) {
- temp_prob >>= 1;
- (*it) = temp_prob << 16;
- }
- base_target_level_ = 4;
- target_level_ = base_target_level_ << 8;
-}
-
int DelayManager::Update(uint16_t sequence_number,
uint32_t timestamp,
int sample_rate_hz) {
@@ -157,8 +150,8 @@
if (packet_len_ms > 0) {
// Cannot update statistics unless |packet_len_ms| is valid.
// Calculate inter-arrival time (IAT) in integer "packet times"
- // (rounding down). This is the value used as index to the histogram
- // vector |iat_vector_|.
+ // (rounding down). This is the value added to the inter-arrival time
+ // histogram.
int iat_packets = packet_iat_stopwatch_->ElapsedMs() / packet_len_ms;
if (streaming_mode_) {
@@ -178,9 +171,8 @@
}
// Saturate IAT at maximum value.
- const int max_iat = kMaxIat;
- iat_packets = std::min(iat_packets, max_iat);
- UpdateHistogram(iat_packets);
+ iat_packets = std::min(iat_packets, iat_histogram_->NumBuckets() - 1);
+ iat_histogram_->Add(iat_packets);
// Calculate new |target_level_| based on updated statistics.
target_level_ = CalculateTargetLevel(iat_packets, reordered);
if (streaming_mode_) {
@@ -229,57 +221,6 @@
}
}
-// Each element in the vector is first multiplied by the forgetting factor
-// |iat_factor_|. Then the vector element indicated by |iat_packets| is then
-// increased (additive) by 1 - |iat_factor_|. This way, the probability of
-// |iat_packets| is slightly increased, while the sum of the histogram remains
-// constant (=1).
-// Due to inaccuracies in the fixed-point arithmetic, the histogram may no
-// longer sum up to 1 (in Q30) after the update. To correct this, a correction
-// term is added or subtracted from the first element (or elements) of the
-// vector.
-// The forgetting factor |iat_factor_| is also updated. When the DelayManager
-// is reset, the factor is set to 0 to facilitate rapid convergence in the
-// beginning. With each update of the histogram, the factor is increased towards
-// the steady-state value |kIatFactor_|.
-void DelayManager::UpdateHistogram(size_t iat_packets) {
- assert(iat_packets < iat_vector_.size());
- int vector_sum = 0; // Sum up the vector elements as they are processed.
- // Multiply each element in |iat_vector_| with |iat_factor_|.
- for (IATVector::iterator it = iat_vector_.begin(); it != iat_vector_.end();
- ++it) {
- *it = (static_cast<int64_t>(*it) * iat_factor_) >> 15;
- vector_sum += *it;
- }
-
- // Increase the probability for the currently observed inter-arrival time
- // by 1 - |iat_factor_|. The factor is in Q15, |iat_vector_| in Q30.
- // Thus, left-shift 15 steps to obtain result in Q30.
- iat_vector_[iat_packets] += (32768 - iat_factor_) << 15;
- vector_sum += (32768 - iat_factor_) << 15; // Add to vector sum.
-
- // |iat_vector_| should sum up to 1 (in Q30), but it may not due to
- // fixed-point rounding errors.
- vector_sum -= 1 << 30; // Should be zero. Compensate if not.
- if (vector_sum != 0) {
- // Modify a few values early in |iat_vector_|.
- int flip_sign = vector_sum > 0 ? -1 : 1;
- IATVector::iterator it = iat_vector_.begin();
- while (it != iat_vector_.end() && abs(vector_sum) > 0) {
- // Add/subtract 1/16 of the element, but not more than |vector_sum|.
- int correction = flip_sign * std::min(abs(vector_sum), (*it) >> 4);
- *it += correction;
- vector_sum += correction;
- ++it;
- }
- }
- assert(vector_sum == 0); // Verify that the above is correct.
-
- // Update |iat_factor_| (changes only during the first seconds after a reset).
- // The factor converges to |kIatFactor_|.
- iat_factor_ += (kIatFactor_ - iat_factor_ + 3) >> 2;
-}
-
// Enforces upper and lower limits for |target_level_|. The upper limit is
// chosen to be minimum of i) 75% of |max_packets_in_buffer_|, to leave some
// headroom for natural fluctuations around the target, and ii) equivalent of
@@ -317,28 +258,9 @@
}
// Calculate target buffer level from inter-arrival time histogram.
- // Find the |iat_index| for which the probability of observing an
- // inter-arrival time larger than or equal to |iat_index| is less than or
- // equal to |limit_probability|. The sought probability is estimated using
- // the histogram as the reverse cumulant PDF, i.e., the sum of elements from
- // the end up until |iat_index|. Now, since the sum of all elements is 1
- // (in Q30) by definition, and since the solution is often a low value for
- // |iat_index|, it is more efficient to start with |sum| = 1 and subtract
- // elements from the start of the histogram.
- size_t index = 0; // Start from the beginning of |iat_vector_|.
- int sum = 1 << 30; // Assign to 1 in Q30.
- sum -= iat_vector_[index]; // Ensure that target level is >= 1.
-
- do {
- // Subtract the probabilities one by one until the sum is no longer greater
- // than limit_probability.
- ++index;
- sum -= iat_vector_[index];
- } while ((sum > limit_probability) && (index < iat_vector_.size() - 1));
-
// This is the base value for the target buffer level.
- int target_level = static_cast<int>(index);
- base_target_level_ = static_cast<int>(index);
+ int target_level = iat_histogram_->Quantile(limit_probability);
+ base_target_level_ = target_level;
// Update detector for delay peaks.
bool delay_peak_found =
@@ -359,8 +281,9 @@
RTC_LOG_F(LS_ERROR) << "length_ms = " << length_ms;
return -1;
}
- if (frame_length_change_experiment_ && packet_len_ms_ != length_ms) {
- iat_vector_ = ScaleHistogram(iat_vector_, packet_len_ms_, length_ms);
+ if (frame_length_change_experiment_ && packet_len_ms_ != length_ms &&
+ packet_len_ms_ > 0) {
+ iat_histogram_->Scale(packet_len_ms_, length_ms);
}
packet_len_ms_ = length_ms;
@@ -374,8 +297,9 @@
packet_len_ms_ = 0; // Packet size unknown.
streaming_mode_ = false;
peak_detector_.Reset();
- ResetHistogram(); // Resets target levels too.
- iat_factor_ = 0; // Adapt the histogram faster for the first few packets.
+ iat_histogram_->Reset();
+ base_target_level_ = 4;
+ target_level_ = base_target_level_ << 8;
packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
max_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
iat_cumulative_sum_ = 0;
@@ -385,12 +309,14 @@
double DelayManager::EstimatedClockDriftPpm() const {
double sum = 0.0;
- // Calculate the expected value based on the probabilities in |iat_vector_|.
- for (size_t i = 0; i < iat_vector_.size(); ++i) {
- sum += static_cast<double>(iat_vector_[i]) * i;
+ // Calculate the expected value based on the probabilities in
+ // |iat_histogram_|.
+ auto buckets = iat_histogram_->buckets();
+ for (size_t i = 0; i < buckets.size(); ++i) {
+ sum += static_cast<double>(buckets[i]) * i;
}
- // The probabilities in |iat_vector_| are in Q30. Divide by 1 << 30 to convert
- // to Q0; subtract the nominal inter-arrival time (1) to make a zero
+ // The probabilities in |iat_histogram_| are in Q30. Divide by 1 << 30 to
+ // convert to Q0; subtract the nominal inter-arrival time (1) to make a zero
// clockdrift represent as 0; mulitply by 1000000 to produce parts-per-million
// (ppm).
return (sum / (1 << 30) - 1) * 1e6;
@@ -442,60 +368,6 @@
++last_seq_no_;
}
-DelayManager::IATVector DelayManager::ScaleHistogram(const IATVector& histogram,
- int old_packet_length,
- int new_packet_length) {
- if (old_packet_length == 0) {
- // If we don't know the previous frame length, don't make any changes to the
- // histogram.
- return histogram;
- }
- RTC_DCHECK_GT(new_packet_length, 0);
- RTC_DCHECK_EQ(old_packet_length % 10, 0);
- RTC_DCHECK_EQ(new_packet_length % 10, 0);
- IATVector new_histogram(histogram.size(), 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 int64_t scaled_acc = acc * new_packet_length / time_counter;
- int64_t actually_used_acc = 0;
- while (time_counter >= new_packet_length) {
- 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;
- }
- // Only subtract the part that was succesfully written to the new histogram.
- acc -= actually_used_acc;
- }
- // If there is anything left in acc (due to rounding errors), add it to the
- // 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());
- 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;
-}
-
bool DelayManager::IsValidMinimumDelay(int delay_ms) const {
return 0 <= delay_ms && delay_ms <= MinimumDelayUpperBound();
}
diff --git a/modules/audio_coding/neteq/delay_manager.h b/modules/audio_coding/neteq/delay_manager.h
index 59f9d37..4f2cb85 100644
--- a/modules/audio_coding/neteq/delay_manager.h
+++ b/modules/audio_coding/neteq/delay_manager.h
@@ -17,6 +17,7 @@
#include <vector>
#include "absl/types/optional.h"
+#include "modules/audio_coding/neteq/histogram.h"
#include "modules/audio_coding/neteq/tick_timer.h"
#include "rtc_base/constructor_magic.h"
@@ -27,24 +28,26 @@
class DelayManager {
public:
- typedef std::vector<int> IATVector;
+ DelayManager(size_t max_packets_in_buffer,
+ int base_minimum_delay_ms,
+ bool enable_rtx_handling,
+ DelayPeakDetector* peak_detector,
+ const TickTimer* tick_timer,
+ std::unique_ptr<Histogram> iat_histogram);
// Create a DelayManager object. Notify the delay manager that the packet
// buffer can hold no more than |max_packets_in_buffer| packets (i.e., this
// is the number of packet slots in the buffer) and that the target delay
// should be greater than or equal to |base_minimum_delay_ms|. Supply a
// PeakDetector object to the DelayManager.
- DelayManager(size_t max_packets_in_buffer,
- int base_minimum_delay_ms,
- bool enable_rtx_handling,
- DelayPeakDetector* peak_detector,
- const TickTimer* tick_timer);
+ static std::unique_ptr<DelayManager> Create(size_t max_packets_in_buffer,
+ int base_minimum_delay_ms,
+ bool enable_rtx_handling,
+ DelayPeakDetector* peak_detector,
+ const TickTimer* tick_timer);
virtual ~DelayManager();
- // Read the inter-arrival time histogram. Mainly for testing purposes.
- virtual const IATVector& iat_vector() const;
-
// Updates the delay manager with a new incoming packet, with
// |sequence_number| and |timestamp| from the RTP header. This updates the
// inter-arrival time histogram and other statistics, as well as the
@@ -102,13 +105,6 @@
// packet will shift the sequence numbers for the following packets.
virtual void RegisterEmptyPacket();
- // Apply compression or stretching to the IAT histogram, for a change in frame
- // size. This returns an updated histogram. This function is public for
- // testability.
- static IATVector ScaleHistogram(const IATVector& histogram,
- int old_packet_length,
- int new_packet_length);
-
// Accessors and mutators.
// Assuming |delay| is in valid range.
virtual bool SetMinimumDelay(int delay_ms);
@@ -138,10 +134,6 @@
// Provides 75% of currently possible maximum buffer size in milliseconds.
int MaxBufferTimeQ75() const;
- // Sets |iat_vector_| to the default start distribution and sets the
- // |base_target_level_| and |target_level_| to the corresponding values.
- void ResetHistogram();
-
// Updates |iat_cumulative_sum_| and |max_iat_cumulative_sum_|. (These are
// used by the streaming mode.) This method is called by Update().
void UpdateCumulativeSums(int packet_len_ms, uint16_t sequence_number);
@@ -151,11 +143,6 @@
// and buffer size.
void UpdateEffectiveMinimumDelay();
- // Updates the histogram |iat_vector_|. The probability for inter-arrival time
- // equal to |iat_packets| (in integer packets) is increased slightly, while
- // all other entries are decreased. This method is called by Update().
- void UpdateHistogram(size_t iat_packets);
-
// Makes sure that |target_level_| is not too large, taking
// |max_packets_in_buffer_| and |extra_delay_ms_| into account. This method is
// called by Update().
@@ -170,8 +157,7 @@
bool first_packet_received_;
const size_t max_packets_in_buffer_; // Capacity of the packet buffer.
- IATVector iat_vector_; // Histogram of inter-arrival times.
- int iat_factor_; // Forgetting factor for updating the IAT histogram (Q15).
+ std::unique_ptr<Histogram> iat_histogram_;
const TickTimer* tick_timer_;
int base_minimum_delay_ms_;
// Provides delay which is used by LimitTargetLevel as lower bound on target
diff --git a/modules/audio_coding/neteq/delay_manager_unittest.cc b/modules/audio_coding/neteq/delay_manager_unittest.cc
index 19b99af..b3797e2 100644
--- a/modules/audio_coding/neteq/delay_manager_unittest.cc
+++ b/modules/audio_coding/neteq/delay_manager_unittest.cc
@@ -14,7 +14,10 @@
#include <math.h>
+#include "absl/memory/memory.h"
+#include "modules/audio_coding/neteq/histogram.h"
#include "modules/audio_coding/neteq/mock/mock_delay_peak_detector.h"
+#include "modules/audio_coding/neteq/mock/mock_histogram.h"
#include "rtc_base/checks.h"
#include "test/field_trial.h"
#include "test/gmock.h"
@@ -46,6 +49,8 @@
std::unique_ptr<DelayManager> dm_;
TickTimer tick_timer_;
MockDelayPeakDetector detector_;
+ bool use_mock_histogram_ = false;
+ MockHistogram* mock_histogram_;
uint16_t seq_no_;
uint32_t ts_;
bool enable_rtx_handling_ = false;
@@ -63,8 +68,18 @@
void DelayManagerTest::RecreateDelayManager() {
EXPECT_CALL(detector_, Reset()).Times(1);
+ std::unique_ptr<Histogram> histogram;
+ static const int kMaxIat = 64;
+ static const int kForgetFactor = 32745;
+ if (use_mock_histogram_) {
+ mock_histogram_ = new MockHistogram(kMaxIat, kForgetFactor);
+ histogram.reset(mock_histogram_);
+ } else {
+ histogram = absl::make_unique<Histogram>(kMaxIat, kForgetFactor);
+ }
dm_.reset(new DelayManager(kMaxNumberOfPackets, kMinDelayMs,
- enable_rtx_handling_, &detector_, &tick_timer_));
+ enable_rtx_handling_, &detector_, &tick_timer_,
+ std::move(histogram)));
}
void DelayManagerTest::SetPacketAudioLength(int lengt_ms) {
@@ -92,17 +107,6 @@
// object.
}
-TEST_F(DelayManagerTest, VectorInitialization) {
- const DelayManager::IATVector& vec = dm_->iat_vector();
- double sum = 0.0;
- for (size_t i = 0; i < vec.size(); i++) {
- EXPECT_NEAR(ldexp(pow(0.5, static_cast<int>(i + 1)), 30), vec[i], 65537);
- // Tolerance 65537 in Q30 corresponds to a delta of approximately 0.00006.
- sum += vec[i];
- }
- EXPECT_EQ(1 << 30, static_cast<int>(sum)); // Should be 1 in Q30.
-}
-
TEST_F(DelayManagerTest, SetPacketAudioLength) {
const int kLengthMs = 30;
// Expect DelayManager to pass on the new length to the detector object.
@@ -477,26 +481,26 @@
TEST_F(DelayManagerTest, EnableRtxHandling) {
enable_rtx_handling_ = true;
+ use_mock_histogram_ = true;
RecreateDelayManager();
+ EXPECT_TRUE(mock_histogram_);
// Insert first packet.
SetPacketAudioLength(kFrameSizeMs);
InsertNextPacket();
// Insert reordered packet.
- // TODO(jakobi): Test estimated inter-arrival time by mocking the histogram
- // instead of checking the call to the peak detector.
- EXPECT_CALL(detector_, Update(3, true, _));
+ EXPECT_CALL(*mock_histogram_, Add(3));
EXPECT_EQ(0, dm_->Update(seq_no_ - 3, ts_ - 3 * kFrameSizeMs, kFs));
// Insert another reordered packet.
- EXPECT_CALL(detector_, Update(2, true, _));
+ EXPECT_CALL(*mock_histogram_, Add(2));
EXPECT_EQ(0, dm_->Update(seq_no_ - 2, ts_ - 2 * kFrameSizeMs, kFs));
// Insert the next packet in order and verify that the inter-arrival time is
// estimated correctly.
IncreaseTime(kFrameSizeMs);
- EXPECT_CALL(detector_, Update(1, false, _));
+ EXPECT_CALL(*mock_histogram_, Add(1));
InsertNextPacket();
}
@@ -573,7 +577,7 @@
test::ScopedFieldTrials field_trial(
"WebRTC-Audio-NetEqForceTargetDelayPercentile/Enabled-0/");
RecreateDelayManager();
- EXPECT_EQ(absl::make_optional<int>(1 << 30),
+ EXPECT_EQ(absl::make_optional<int>(0),
dm_->forced_limit_probability_for_test());
SetPacketAudioLength(kFrameSizeMs);
@@ -595,14 +599,14 @@
test::ScopedFieldTrials field_trial(
"WebRTC-Audio-NetEqForceTargetDelayPercentile/Enabled-95/");
RecreateDelayManager();
- EXPECT_EQ(absl::make_optional<int>(53687091),
+ EXPECT_EQ(absl::make_optional<int>(1020054733),
dm_->forced_limit_probability_for_test()); // 1/20 in Q30
}
{
test::ScopedFieldTrials field_trial(
"WebRTC-Audio-NetEqForceTargetDelayPercentile/Enabled-99.95/");
RecreateDelayManager();
- EXPECT_EQ(absl::make_optional<int>(536871),
+ EXPECT_EQ(absl::make_optional<int>(1073204953),
dm_->forced_limit_probability_for_test()); // 1/2000 in Q30
}
{
@@ -624,116 +628,4 @@
}
}
-// Test if the histogram is stretched correctly if the packet size is decreased.
-TEST(DelayManagerIATScalingTest, StretchTest) {
- using IATVector = DelayManager::IATVector;
- // Test a straightforward 60ms to 20ms change.
- IATVector iat = {12, 0, 0, 0, 0, 0};
- IATVector expected_result = {4, 4, 4, 0, 0, 0};
- IATVector stretched_iat = DelayManager::ScaleHistogram(iat, 60, 20);
- EXPECT_EQ(stretched_iat, expected_result);
-
- // Test an example where the last bin in the stretched histogram should
- // contain the sum of the elements that don't fit into the new histogram.
- iat = {18, 15, 12, 9, 6, 3, 0};
- expected_result = {6, 6, 6, 5, 5, 5, 30};
- stretched_iat = DelayManager::ScaleHistogram(iat, 60, 20);
- EXPECT_EQ(stretched_iat, expected_result);
-
- // Test a 120ms to 60ms change.
- iat = {18, 16, 14, 4, 0};
- expected_result = {9, 9, 8, 8, 18};
- stretched_iat = DelayManager::ScaleHistogram(iat, 120, 60);
- EXPECT_EQ(stretched_iat, expected_result);
-
- // Test a 120ms to 20ms change.
- iat = {19, 12, 0, 0, 0, 0, 0, 0};
- expected_result = {3, 3, 3, 3, 3, 3, 2, 11};
- stretched_iat = DelayManager::ScaleHistogram(iat, 120, 20);
- EXPECT_EQ(stretched_iat, expected_result);
-
- // Test a 70ms to 40ms change.
- iat = {13, 7, 5, 3, 1, 5, 12, 11, 3, 0, 0, 0};
- expected_result = {7, 5, 5, 3, 3, 2, 2, 1, 2, 2, 6, 22};
- stretched_iat = DelayManager::ScaleHistogram(iat, 70, 40);
- EXPECT_EQ(stretched_iat, expected_result);
-
- // Test a 30ms to 20ms change.
- iat = {13, 7, 5, 3, 1, 5, 12, 11, 3, 0, 0, 0};
- expected_result = {8, 6, 6, 3, 2, 2, 1, 3, 3, 8, 7, 11};
- stretched_iat = DelayManager::ScaleHistogram(iat, 30, 20);
- EXPECT_EQ(stretched_iat, expected_result);
-}
-
-// Test if the histogram is compressed correctly if the packet size is
-// increased.
-TEST(DelayManagerIATScalingTest, CompressionTest) {
- using IATVector = DelayManager::IATVector;
- // Test a 20 to 60 ms change.
- IATVector iat = {12, 11, 10, 3, 2, 1};
- IATVector expected_result = {33, 6, 0, 0, 0, 0};
- IATVector compressed_iat = DelayManager::ScaleHistogram(iat, 20, 60);
- EXPECT_EQ(compressed_iat, expected_result);
-
- // Test a 60ms to 120ms change.
- iat = {18, 16, 14, 4, 1};
- expected_result = {34, 18, 1, 0, 0};
- compressed_iat = DelayManager::ScaleHistogram(iat, 60, 120);
- EXPECT_EQ(compressed_iat, expected_result);
-
- // Test a 20ms to 120ms change.
- iat = {18, 12, 5, 4, 4, 3, 5, 1};
- expected_result = {46, 6, 0, 0, 0, 0, 0, 0};
- compressed_iat = DelayManager::ScaleHistogram(iat, 20, 120);
- EXPECT_EQ(compressed_iat, expected_result);
-
- // Test a 70ms to 80ms change.
- iat = {13, 7, 5, 3, 1, 5, 12, 11, 3};
- expected_result = {11, 8, 6, 2, 5, 12, 13, 3, 0};
- compressed_iat = DelayManager::ScaleHistogram(iat, 70, 80);
- EXPECT_EQ(compressed_iat, expected_result);
-
- // Test a 50ms to 110ms change.
- iat = {13, 7, 5, 3, 1, 5, 12, 11, 3};
- expected_result = {18, 8, 16, 16, 2, 0, 0, 0, 0};
- compressed_iat = DelayManager::ScaleHistogram(iat, 50, 110);
- 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
diff --git a/modules/audio_coding/neteq/histogram.cc b/modules/audio_coding/neteq/histogram.cc
new file mode 100644
index 0000000..b8e4e52
--- /dev/null
+++ b/modules/audio_coding/neteq/histogram.cc
@@ -0,0 +1,174 @@
+/*
+ * Copyright (c) 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 <algorithm>
+#include <numeric>
+
+#include "modules/audio_coding/neteq/histogram.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/numerics/safe_conversions.h"
+
+namespace webrtc {
+
+Histogram::Histogram(size_t num_buckets, int forget_factor)
+ : buckets_(num_buckets, 0),
+ forget_factor_(0),
+ base_forget_factor_(forget_factor) {}
+
+Histogram::~Histogram() {}
+
+// Each element in the vector is first multiplied by the forgetting factor
+// |forget_factor_|. Then the vector element indicated by |iat_packets| is then
+// increased (additive) by 1 - |forget_factor_|. This way, the probability of
+// |iat_packets| is slightly increased, while the sum of the histogram remains
+// constant (=1).
+// Due to inaccuracies in the fixed-point arithmetic, the histogram may no
+// longer sum up to 1 (in Q30) after the update. To correct this, a correction
+// term is added or subtracted from the first element (or elements) of the
+// vector.
+// The forgetting factor |forget_factor_| is also updated. When the DelayManager
+// is reset, the factor is set to 0 to facilitate rapid convergence in the
+// beginning. With each update of the histogram, the factor is increased towards
+// the steady-state value |kIatFactor_|.
+void Histogram::Add(int value) {
+ RTC_DCHECK(value >= 0);
+ RTC_DCHECK(value < static_cast<int>(buckets_.size()));
+ int vector_sum = 0; // Sum up the vector elements as they are processed.
+ // Multiply each element in |buckets_| with |forget_factor_|.
+ for (int& bucket : buckets_) {
+ bucket = (static_cast<int64_t>(bucket) * forget_factor_) >> 15;
+ vector_sum += bucket;
+ }
+
+ // Increase the probability for the currently observed inter-arrival time
+ // by 1 - |forget_factor_|. The factor is in Q15, |buckets_| in Q30.
+ // Thus, left-shift 15 steps to obtain result in Q30.
+ buckets_[value] += (32768 - forget_factor_) << 15;
+ vector_sum += (32768 - forget_factor_) << 15; // Add to vector sum.
+
+ // |buckets_| should sum up to 1 (in Q30), but it may not due to
+ // fixed-point rounding errors.
+ vector_sum -= 1 << 30; // Should be zero. Compensate if not.
+ if (vector_sum != 0) {
+ // Modify a few values early in |buckets_|.
+ int flip_sign = vector_sum > 0 ? -1 : 1;
+ for (int& bucket : buckets_) {
+ // Add/subtract 1/16 of the element, but not more than |vector_sum|.
+ int correction = flip_sign * std::min(abs(vector_sum), bucket >> 4);
+ bucket += correction;
+ vector_sum += correction;
+ if (abs(vector_sum) == 0) {
+ break;
+ }
+ }
+ }
+ RTC_DCHECK(vector_sum == 0); // Verify that the above is correct.
+
+ // Update |forget_factor_| (changes only during the first seconds after a
+ // reset). The factor converges to |base_forget_factor_|.
+ forget_factor_ += (base_forget_factor_ - forget_factor_ + 3) >> 2;
+}
+
+int Histogram::Quantile(int probability) {
+ // Find the bucket for which the probability of observing an
+ // inter-arrival time larger than or equal to |index| is larger than or
+ // equal to |probability|. The sought probability is estimated using
+ // the histogram as the reverse cumulant PDF, i.e., the sum of elements from
+ // the end up until |index|. Now, since the sum of all elements is 1
+ // (in Q30) by definition, and since the solution is often a low value for
+ // |iat_index|, it is more efficient to start with |sum| = 1 and subtract
+ // elements from the start of the histogram.
+ int inverse_probability = (1 << 30) - probability;
+ size_t index = 0; // Start from the beginning of |buckets_|.
+ int sum = 1 << 30; // Assign to 1 in Q30.
+ sum -= buckets_[index]; // Ensure that target level is >= 1.
+
+ do {
+ // Subtract the probabilities one by one until the sum is no longer greater
+ // than |inverse_probability|.
+ ++index;
+ sum -= buckets_[index];
+ } while ((sum > inverse_probability) && (index < buckets_.size() - 1));
+ return static_cast<int>(index);
+}
+
+// Set the histogram vector to an exponentially decaying distribution
+// buckets_[i] = 0.5^(i+1), i = 0, 1, 2, ...
+// buckets_ is in Q30.
+void Histogram::Reset() {
+ // Set temp_prob to (slightly more than) 1 in Q14. This ensures that the sum
+ // of buckets_ is 1.
+ uint16_t temp_prob = 0x4002; // 16384 + 2 = 100000000000010 binary.
+ for (int& bucket : buckets_) {
+ temp_prob >>= 1;
+ bucket = temp_prob << 16;
+ }
+ forget_factor_ = 0; // Adapt the histogram faster for the first few packets.
+}
+
+int Histogram::NumBuckets() const {
+ return buckets_.size();
+}
+
+void Histogram::Scale(int old_bucket_width, int new_bucket_width) {
+ buckets_ = ScaleBuckets(buckets_, old_bucket_width, new_bucket_width);
+}
+
+std::vector<int> Histogram::ScaleBuckets(const std::vector<int>& buckets,
+ int old_bucket_width,
+ int new_bucket_width) {
+ RTC_DCHECK_GT(old_bucket_width, 0);
+ RTC_DCHECK_GT(new_bucket_width, 0);
+ RTC_DCHECK_EQ(old_bucket_width % 10, 0);
+ RTC_DCHECK_EQ(new_bucket_width % 10, 0);
+ std::vector<int> new_histogram(buckets.size(), 0);
+ int64_t acc = 0;
+ int time_counter = 0;
+ size_t new_histogram_idx = 0;
+ for (size_t i = 0; i < buckets.size(); i++) {
+ acc += buckets[i];
+ time_counter += old_bucket_width;
+ // The bins should be scaled, to ensure the histogram still sums to one.
+ const int64_t scaled_acc = acc * new_bucket_width / time_counter;
+ int64_t actually_used_acc = 0;
+ while (time_counter >= new_bucket_width) {
+ 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_bucket_width;
+ }
+ // Only subtract the part that was succesfully written to the new histogram.
+ acc -= actually_used_acc;
+ }
+ // If there is anything left in acc (due to rounding errors), add it to the
+ // 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(buckets.size(), new_histogram.size());
+ 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(buckets.begin(), buckets.end(), 0ll),
+ accumulate(new_histogram.begin(), new_histogram.end(), 0ll));
+ }
+ return new_histogram;
+}
+
+} // namespace webrtc
diff --git a/modules/audio_coding/neteq/histogram.h b/modules/audio_coding/neteq/histogram.h
new file mode 100644
index 0000000..66b4fe9
--- /dev/null
+++ b/modules/audio_coding/neteq/histogram.h
@@ -0,0 +1,59 @@
+/*
+ * Copyright (c) 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 MODULES_AUDIO_CODING_NETEQ_HISTOGRAM_H_
+#define MODULES_AUDIO_CODING_NETEQ_HISTOGRAM_H_
+
+#include <string.h> // Provide access to size_t.
+
+#include <vector>
+
+namespace webrtc {
+
+class Histogram {
+ public:
+ // Creates histogram with capacity |num_buckets| and |forget_factor| in Q15.
+ Histogram(size_t num_buckets, int forget_factor);
+
+ virtual ~Histogram();
+
+ // Resets the histogram to the default start distribution.
+ virtual void Reset();
+
+ // Add entry in bucket |index|.
+ virtual void Add(int index);
+
+ // Calculates the quantile at |probability| (in Q30) of the histogram
+ // distribution.
+ virtual int Quantile(int probability);
+
+ // Apply compression or stretching to the histogram.
+ virtual void Scale(int old_bucket_width, int new_bucket_width);
+
+ // Returns the number of buckets in the histogram.
+ virtual int NumBuckets() const;
+
+ // Returns the probability for each bucket in Q30.
+ std::vector<int> buckets() const { return buckets_; }
+
+ // Made public for testing.
+ static std::vector<int> ScaleBuckets(const std::vector<int>& buckets,
+ int old_bucket_width,
+ int new_bucket_width);
+
+ private:
+ std::vector<int> buckets_;
+ int forget_factor_; // Q15
+ const int base_forget_factor_;
+};
+
+} // namespace webrtc
+
+#endif // MODULES_AUDIO_CODING_NETEQ_HISTOGRAM_H_
diff --git a/modules/audio_coding/neteq/histogram_unittest.cc b/modules/audio_coding/neteq/histogram_unittest.cc
new file mode 100644
index 0000000..7a887c8
--- /dev/null
+++ b/modules/audio_coding/neteq/histogram_unittest.cc
@@ -0,0 +1,171 @@
+/*
+ * Copyright (c) 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 <cmath>
+
+#include "modules/audio_coding/neteq/histogram.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+
+TEST(HistogramTest, Initialization) {
+ Histogram histogram(65, 32440);
+ histogram.Reset();
+ const auto& buckets = histogram.buckets();
+ double sum = 0.0;
+ for (size_t i = 0; i < buckets.size(); i++) {
+ EXPECT_NEAR(ldexp(std::pow(0.5, static_cast<int>(i + 1)), 30), buckets[i],
+ 65537);
+ // Tolerance 65537 in Q30 corresponds to a delta of approximately 0.00006.
+ sum += buckets[i];
+ }
+ EXPECT_EQ(1 << 30, static_cast<int>(sum)); // Should be 1 in Q30.
+}
+
+TEST(HistogramTest, Add) {
+ Histogram histogram(10, 32440);
+ histogram.Reset();
+ const std::vector<int> before = histogram.buckets();
+ const int index = 5;
+ histogram.Add(index);
+ const std::vector<int> after = histogram.buckets();
+ EXPECT_GT(after[index], before[index]);
+ int sum = 0;
+ for (int bucket : after) {
+ sum += bucket;
+ }
+ EXPECT_EQ(1 << 30, sum);
+}
+
+TEST(HistogramTest, ForgetFactor) {
+ Histogram histogram(10, 32440);
+ histogram.Reset();
+ const std::vector<int> before = histogram.buckets();
+ const int index = 4;
+ histogram.Add(index);
+ const std::vector<int> after = histogram.buckets();
+ for (int i = 0; i < histogram.NumBuckets(); ++i) {
+ if (i != index) {
+ EXPECT_LT(after[i], before[i]);
+ }
+ }
+}
+
+// Test if the histogram is scaled correctly if the bucket width is decreased.
+TEST(HistogramTest, DownScale) {
+ // Test a straightforward 60 to 20 change.
+ std::vector<int> buckets = {12, 0, 0, 0, 0, 0};
+ std::vector<int> expected_result = {4, 4, 4, 0, 0, 0};
+ std::vector<int> stretched_buckets = Histogram::ScaleBuckets(buckets, 60, 20);
+ EXPECT_EQ(stretched_buckets, expected_result);
+
+ // Test an example where the last bin in the stretched histogram should
+ // contain the sum of the elements that don't fit into the new histogram.
+ buckets = {18, 15, 12, 9, 6, 3, 0};
+ expected_result = {6, 6, 6, 5, 5, 5, 30};
+ stretched_buckets = Histogram::ScaleBuckets(buckets, 60, 20);
+ EXPECT_EQ(stretched_buckets, expected_result);
+
+ // Test a 120 to 60 change.
+ buckets = {18, 16, 14, 4, 0};
+ expected_result = {9, 9, 8, 8, 18};
+ stretched_buckets = Histogram::ScaleBuckets(buckets, 120, 60);
+ EXPECT_EQ(stretched_buckets, expected_result);
+
+ // Test a 120 to 20 change.
+ buckets = {19, 12, 0, 0, 0, 0, 0, 0};
+ expected_result = {3, 3, 3, 3, 3, 3, 2, 11};
+ stretched_buckets = Histogram::ScaleBuckets(buckets, 120, 20);
+ EXPECT_EQ(stretched_buckets, expected_result);
+
+ // Test a 70 to 40 change.
+ buckets = {13, 7, 5, 3, 1, 5, 12, 11, 3, 0, 0, 0};
+ expected_result = {7, 5, 5, 3, 3, 2, 2, 1, 2, 2, 6, 22};
+ stretched_buckets = Histogram::ScaleBuckets(buckets, 70, 40);
+ EXPECT_EQ(stretched_buckets, expected_result);
+
+ // Test a 30 to 20 change.
+ buckets = {13, 7, 5, 3, 1, 5, 12, 11, 3, 0, 0, 0};
+ expected_result = {8, 6, 6, 3, 2, 2, 1, 3, 3, 8, 7, 11};
+ stretched_buckets = Histogram::ScaleBuckets(buckets, 30, 20);
+ EXPECT_EQ(stretched_buckets, expected_result);
+}
+
+// Test if the histogram is scaled correctly if the bucket width is increased.
+TEST(HistogramTest, UpScale) {
+ // Test a 20 to 60 change.
+ std::vector<int> buckets = {12, 11, 10, 3, 2, 1};
+ std::vector<int> expected_result = {33, 6, 0, 0, 0, 0};
+ std::vector<int> compressed_buckets =
+ Histogram::ScaleBuckets(buckets, 20, 60);
+ EXPECT_EQ(compressed_buckets, expected_result);
+
+ // Test a 60 to 120 change.
+ buckets = {18, 16, 14, 4, 1};
+ expected_result = {34, 18, 1, 0, 0};
+ compressed_buckets = Histogram::ScaleBuckets(buckets, 60, 120);
+ EXPECT_EQ(compressed_buckets, expected_result);
+
+ // Test a 20 to 120 change.
+ buckets = {18, 12, 5, 4, 4, 3, 5, 1};
+ expected_result = {46, 6, 0, 0, 0, 0, 0, 0};
+ compressed_buckets = Histogram::ScaleBuckets(buckets, 20, 120);
+ EXPECT_EQ(compressed_buckets, expected_result);
+
+ // Test a 70 to 80 change.
+ buckets = {13, 7, 5, 3, 1, 5, 12, 11, 3};
+ expected_result = {11, 8, 6, 2, 5, 12, 13, 3, 0};
+ compressed_buckets = Histogram::ScaleBuckets(buckets, 70, 80);
+ EXPECT_EQ(compressed_buckets, expected_result);
+
+ // Test a 50 to 110 change.
+ buckets = {13, 7, 5, 3, 1, 5, 12, 11, 3};
+ expected_result = {18, 8, 16, 16, 2, 0, 0, 0, 0};
+ compressed_buckets = Histogram::ScaleBuckets(buckets, 50, 110);
+ EXPECT_EQ(compressed_buckets, expected_result);
+}
+
+// Test if the histogram scaling function handles overflows correctly.
+TEST(HistogramTest, OverflowTest) {
+ // Test a upscale operation that can cause overflow.
+ std::vector<int> buckets = {733544448, 0, 0, 0, 0, 0, 0,
+ 340197376, 0, 0, 0, 0, 0, 0};
+ std::vector<int> expected_result = {733544448, 340197376, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0};
+ std::vector<int> scaled_buckets = Histogram::ScaleBuckets(buckets, 10, 60);
+ EXPECT_EQ(scaled_buckets, expected_result);
+
+ buckets = {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_buckets = Histogram::ScaleBuckets(buckets, 20, 60);
+ EXPECT_EQ(scaled_buckets, 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.
+ buckets = {2000000000, 2000000000, 2000000000,
+ 2000000000, 2000000000, 2000000000};
+ expected_result = {666666666, 666666666, 666666666,
+ 666666667, 666666667, 2147483647};
+ scaled_buckets = Histogram::ScaleBuckets(buckets, 60, 20);
+ EXPECT_EQ(scaled_buckets, 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.
+ buckets = {2000000000, 2000000000, 2000000000,
+ 2000000000, 2000000000, 2000000000};
+ expected_result = {2147483647, 2147483647, 2147483647,
+ 2147483647, 2147483647, 1262581765};
+ scaled_buckets = Histogram::ScaleBuckets(buckets, 20, 60);
+ EXPECT_EQ(scaled_buckets, expected_result);
+}
+
+} // namespace webrtc
diff --git a/modules/audio_coding/neteq/mock/mock_delay_manager.h b/modules/audio_coding/neteq/mock/mock_delay_manager.h
index 67c7a8a..fa07e20 100644
--- a/modules/audio_coding/neteq/mock/mock_delay_manager.h
+++ b/modules/audio_coding/neteq/mock/mock_delay_manager.h
@@ -11,8 +11,10 @@
#ifndef MODULES_AUDIO_CODING_NETEQ_MOCK_MOCK_DELAY_MANAGER_H_
#define MODULES_AUDIO_CODING_NETEQ_MOCK_MOCK_DELAY_MANAGER_H_
-#include "modules/audio_coding/neteq/delay_manager.h"
+#include <algorithm>
+#include "modules/audio_coding/neteq/delay_manager.h"
+#include "modules/audio_coding/neteq/histogram.h"
#include "test/gmock.h"
namespace webrtc {
@@ -23,15 +25,16 @@
int base_min_target_delay_ms,
bool enable_rtx_handling,
DelayPeakDetector* peak_detector,
- const TickTimer* tick_timer)
+ const TickTimer* tick_timer,
+ std::unique_ptr<Histogram> histogram)
: DelayManager(max_packets_in_buffer,
base_min_target_delay_ms,
enable_rtx_handling,
peak_detector,
- tick_timer) {}
+ tick_timer,
+ std::move(histogram)) {}
virtual ~MockDelayManager() { Die(); }
MOCK_METHOD0(Die, void());
- MOCK_CONST_METHOD0(iat_vector, const IATVector&());
MOCK_METHOD3(Update,
int(uint16_t sequence_number,
uint32_t timestamp,
diff --git a/modules/audio_coding/neteq/mock/mock_histogram.h b/modules/audio_coding/neteq/mock/mock_histogram.h
new file mode 100644
index 0000000..09b1b89
--- /dev/null
+++ b/modules/audio_coding/neteq/mock/mock_histogram.h
@@ -0,0 +1,31 @@
+/*
+ * Copyright (c) 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 MODULES_AUDIO_CODING_NETEQ_MOCK_MOCK_HISTOGRAM_H_
+#define MODULES_AUDIO_CODING_NETEQ_MOCK_MOCK_HISTOGRAM_H_
+
+#include "modules/audio_coding/neteq/histogram.h"
+
+#include "test/gmock.h"
+
+namespace webrtc {
+
+class MockHistogram : public Histogram {
+ public:
+ MockHistogram(size_t num_buckets, int forget_factor)
+ : Histogram(num_buckets, forget_factor) {}
+ virtual ~MockHistogram() {}
+
+ MOCK_METHOD1(Add, void(int));
+ MOCK_METHOD1(Quantile, int(int));
+};
+
+} // namespace webrtc
+#endif // MODULES_AUDIO_CODING_NETEQ_MOCK_MOCK_HISTOGRAM_H_
diff --git a/modules/audio_coding/neteq/neteq_impl.cc b/modules/audio_coding/neteq/neteq_impl.cc
index 8115135..9daf296 100644
--- a/modules/audio_coding/neteq/neteq_impl.cc
+++ b/modules/audio_coding/neteq/neteq_impl.cc
@@ -63,11 +63,11 @@
new DecoderDatabase(decoder_factory, config.codec_pair_id)),
delay_peak_detector(
new DelayPeakDetector(tick_timer.get(), config.enable_rtx_handling)),
- delay_manager(new DelayManager(config.max_packets_in_buffer,
- config.min_delay_ms,
- config.enable_rtx_handling,
- delay_peak_detector.get(),
- tick_timer.get())),
+ delay_manager(DelayManager::Create(config.max_packets_in_buffer,
+ config.min_delay_ms,
+ config.enable_rtx_handling,
+ delay_peak_detector.get(),
+ tick_timer.get())),
dtmf_buffer(new DtmfBuffer(config.sample_rate_hz)),
dtmf_tone_generator(new DtmfToneGenerator),
packet_buffer(
diff --git a/modules/audio_coding/neteq/neteq_impl_unittest.cc b/modules/audio_coding/neteq/neteq_impl_unittest.cc
index cf627d9..e7552c1 100644
--- a/modules/audio_coding/neteq/neteq_impl_unittest.cc
+++ b/modules/audio_coding/neteq/neteq_impl_unittest.cc
@@ -14,6 +14,7 @@
#include "api/audio_codecs/builtin_audio_decoder_factory.h"
#include "modules/audio_coding/neteq/accelerate.h"
#include "modules/audio_coding/neteq/expand.h"
+#include "modules/audio_coding/neteq/histogram.h"
#include "modules/audio_coding/neteq/include/neteq.h"
#include "modules/audio_coding/neteq/mock/mock_buffer_level_filter.h"
#include "modules/audio_coding/neteq/mock/mock_decoder_database.h"
@@ -97,7 +98,8 @@
if (use_mock_delay_manager_) {
std::unique_ptr<MockDelayManager> mock(new MockDelayManager(
config_.max_packets_in_buffer, config_.min_delay_ms,
- config_.enable_rtx_handling, delay_peak_detector_, tick_timer_));
+ config_.enable_rtx_handling, delay_peak_detector_, tick_timer_,
+ absl::make_unique<Histogram>(50, 32745)));
mock_delay_manager_ = mock.get();
EXPECT_CALL(*mock_delay_manager_, set_streaming_mode(false)).Times(1);
deps.delay_manager = std::move(mock);