Add algorithm for Residual Echo Detector.

webrtc/modules/audio_processing/echo_detector/echo_detector.cc

Index: webrtc/modules/audio_processing/echo_detector/echo_detector.cc
diff --git a/webrtc/modules/audio_processing/echo_detector/echo_detector.cc b/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
index 842be9e2db3a5a999de4dd07c02c40ec41c879db..ca8acb225770e5178417fd84d8aabbad73811a8d 100644
--- a/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
+++ b/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
@@ -10,21 +10,109 @@
 
 #include "webrtc/modules/audio_processing/echo_detector/echo_detector.h"
 
+#include <algorithm>
+#include <numeric>
+
+namespace {
+
+float Power(rtc::ArrayView<const float> input) {
+  return std::inner_product(input.begin(), input.end(), input.begin(), 0.f);
+}
+
+constexpr size_t kLookbackFrames = 650;
+// TODO(ivoc): Verify the size of this buffer.
+constexpr size_t kRenderBufferSize = 30;
+
+}  // namespace
+
 namespace webrtc {
 
-void EchoDetector::BufferFarend(const rtc::ArrayView<const float>& /*farend*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+EchoDetector::EchoDetector()
+    : render_buffer_(kRenderBufferSize),
+      render_power_(kLookbackFrames),
+      render_power_mean_(kLookbackFrames),
+      render_power_std_dev_(kLookbackFrames),
+      covariances_(kLookbackFrames){};
+
+EchoDetector::~EchoDetector() = default;
+
+void EchoDetector::BufferRender(rtc::ArrayView<const float> render) {
+  if (render_buffer_.Size() == 0) {
+    frames_since_zero_buffer_size_ = 0;
+  } else if (frames_since_zero_buffer_size_ >= kRenderBufferSize) {
+    // This can happen in a few cases: at the start of a call, due to a glitch
+    // or due to clock drift. The excess capture value will be ignored.
+    // TODO(ivoc): Include how often this happens in APM stats.
+    render_buffer_.Pop();
+    frames_since_zero_buffer_size_ = 0;

[hlundin-webrtc, 2016/10/24 00:42:14]

I don't understand the logic of frames_since_zero_buffer_size_. No matter what,
it will always come out as 1 when this method returns, and it is neither read
nor written anywhere else. Confused.

[ivoc, 2016/10/24 15:25:19]

The idea is to count how long ago it was since the buffer was zero. The
reasoning is that in the case of clockdrift, this buffer will never return to
zero (it will slowly fill up), so we can use this as a signal to detect that. 

I don't think it will come out as 1 no matter what: if
frames_since_zero_buffer_size_ is < kRenderBufferSize and the buffer is not
zero, neither the if nor the else-if will be run, and it will simply be
incremented below.

[hlundin-webrtc, 2016/10/27 13:05:48]

Oh, it was an if--elseif statement. I read it as if-else. Mea culpa.

You may want to reconsider the name of the state variable, or comment more in
detail what it is actually counting.

[ivoc, 2016/10/27 13:55:29]

Added more comments in the header, because naming stuff is hard.

+  }
+  ++frames_since_zero_buffer_size_;
+  float power = Power(render);
+  render_buffer_.Push(power);
 }
 
-void EchoDetector::Process(const rtc::ArrayView<const float>& /*nearend*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+void EchoDetector::Process(rtc::ArrayView<const float> capture) {
+  if (first_process_call_) {
+    // On the first process call (so the start of a call), we must flush the
+    // render buffer, otherwise the render data will be delayed.
+    render_buffer_.Clear();
+    first_process_call_ = false;
+  }
+
+  // Get the next render value.
+  const rtc::Optional<float> buffered_render_power = render_buffer_.Pop();
+  if (!buffered_render_power) {
+    // This can happen in a few cases: at the start of a call, due to a glitch
+    // or due to clock drift. The excess capture value will be ignored.
+    // TODO(ivoc): Include how often this happens in APM stats.
+    return;
+  }
+  // Update the render statistics, and store the statistics in circular buffers.
+  render_statistics_.Update(*buffered_render_power);
+  RTC_DCHECK_LT(next_insertion_index_, kLookbackFrames);
+  render_power_[next_insertion_index_] = *buffered_render_power;
+  render_power_mean_[next_insertion_index_] = render_statistics_.mean();
+  render_power_std_dev_[next_insertion_index_] =
+      render_statistics_.std_deviation();
+
+  // Get the next capture value, update capture statistics and add the relevant
+  // values to the buffers.
+  const float capture_power = Power(capture);
+  capture_statistics_.Update(capture_power);
+  const float capture_mean = capture_statistics_.mean();
+  const float capture_std_deviation = capture_statistics_.std_deviation();
+
+  // Update the covariance values and determine the new echo likelihood.
+  echo_likelihood_ = 0.f;
+  for (size_t delay = 0; delay < covariances_.size(); ++delay) {
+    const size_t read_index =
+        (kLookbackFrames + next_insertion_index_ - delay) % kLookbackFrames;
+    RTC_DCHECK_LT(read_index, render_power_.size());
+    covariances_[delay].Update(capture_power, capture_mean,
+                               capture_std_deviation, render_power_[read_index],
+                               render_power_mean_[read_index],
+                               render_power_std_dev_[read_index]);
+    echo_likelihood_ = std::max(
+        echo_likelihood_, covariances_[delay].normalized_cross_correlation());
+  }
+
+  // Update the next insertion index.
+  ++next_insertion_index_;
+  next_insertion_index_ %= kLookbackFrames;
 }
 
-void EchoDetector::Initialize(int /*sample_rate_hz*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+void EchoDetector::Initialize() {
+  render_buffer_.Clear();
+  std::fill(render_power_.begin(), render_power_.end(), 0.f);
+  std::fill(render_power_mean_.begin(), render_power_mean_.end(), 0.f);
+  std::fill(render_power_std_dev_.begin(), render_power_std_dev_.end(), 0.f);
+  render_statistics_.Clear();
+  capture_statistics_.Clear();
+  for (auto& cov : covariances_) {
+    cov.Clear();
+  }
+  echo_likelihood_ = 0.f;
+  next_insertion_index_ = 0;
 }
 
 }  // namespace webrtc