Add algorithm for Residual Echo Detector.

webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc

Index: webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc
diff --git a/webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc b/webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..178f4c40145cc52dd3dd8681dedcf8c287ddacc4
--- /dev/null
+++ b/webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc
@@ -0,0 +1,119 @@
+/*
+ *  Copyright (c) 2016 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 <vector>
+
+#include "webrtc/modules/audio_processing/echo_detector/echo_detector.h"
+#include "webrtc/test/gtest.h"
+
+namespace webrtc {
+
+TEST(EchoDetectorTests, Echo) {
+  EchoDetector echo_detector;
+  std::vector<float> ones(160, 1.f);
+  std::vector<float> zeros(160, 0.f);
+
+  // In this test the capture signal has a delay of 10 frames w.r.t. the render
+  // signal, but is otherwise identical. Both signals are periodic with a 20
+  // frame interval.
+  for (int i = 0; i < 1000; i++) {
+    if (i % 20 == 0) {
+      echo_detector.BufferRender(ones);
+      echo_detector.Process(zeros);
+    } else if (i % 20 == 10) {
+      echo_detector.BufferRender(zeros);
+      echo_detector.Process(ones);
+    } else {
+      echo_detector.BufferRender(zeros);
+      echo_detector.Process(zeros);
+    }
+  }
+  // We expect to detect echo with near certain likelihood.
+  EXPECT_NEAR(1.f, echo_detector.echo_likelihood(), 0.01f);
+}
+
+TEST(EchoDetectorTests, NoEcho) {
+  EchoDetector echo_detector;
+  std::vector<float> ones(160, 1.f);
+  std::vector<float> zeros(160, 0.f);
+
+  // In this test the capture signal is always zero, so no echo should be
+  // detected.
+  for (int i = 0; i < 1000; i++) {
+    if (i % 20 == 0) {
+      echo_detector.BufferRender(ones);
+    } else {
+      echo_detector.BufferRender(zeros);
+    }
+    echo_detector.Process(zeros);
+  }
+  // We expect to not detect any echo.
+  EXPECT_NEAR(0.f, echo_detector.echo_likelihood(), 0.01f);
+}
+
+TEST(EchoDetectorTests, EchoWithRenderClockDrift) {
+  EchoDetector echo_detector;
+  std::vector<float> ones(160, 1.f);
+  std::vector<float> zeros(160, 0.f);
+
+  // In this test the capture signal has a delay of 10 frames w.r.t. the render
+  // signal, but is otherwise identical. Both signals are periodic with a 20
+  // frame interval. There is a simulated clock drift of 1% in this test, with
+  // the render side producing data slightly faster.
+  for (int i = 0; i < 1000; i++) {

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

What if you ran this for much longer? Would it still pass? Probably not a good
idea for the committed test, but you can test it locally.

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

I tried this with 100000 loop iterations locally, and the test still passes with
the same likelihood (but it takes 5.7s, which indicates that the RED takes about
57ns per iteration in debug mode on my machine).

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

Acknowledged.

+    if (i % 20 == 0) {
+      echo_detector.BufferRender(ones);
+      echo_detector.Process(zeros);
+    } else if (i % 20 == 10) {
+      echo_detector.BufferRender(zeros);
+      echo_detector.Process(ones);
+    } else {
+      echo_detector.BufferRender(zeros);
+      echo_detector.Process(zeros);
+    }
+    if (i % 100 == 0) {
+      // This is causing the simulated clock drift.
+      echo_detector.BufferRender(zeros);
+    }
+  }
+  // We expect to detect echo with high likelihood.
+  EXPECT_GT(echo_detector.echo_likelihood(), 0.8f);

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

Out of curiosity, why does this test flag echo with "only" 80% certainty, while
the one below is 99%?

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

Clock drift is harder to correct for on the render side, this due to the fact
that calls to BufferRender() and Process() can be jittery, so they don't
necessarily alternate nicely. To deal with this, the BufferRender() function
stores the value in a queue, and processing is only done on the Process()
function, which takes a single value from the queue. For clockdrift on the other
side, the situation is simple, because the render buffer will be empty when
Process() is called too often, so we know immediately that this is clockdrift
and we can just ignore the excess call. The problem on the render side is that
excess calls can be either due to jitter (in which case it should just be
buffered) or due to clockdrift (in which case we want to discard it). To deal
with this we now count how long it has been until the render buffer was empty,
it should be empty within a reasonable amount of time, otherwise it indicates
clockdrift. This means that there is a larger delay before clockdrift is
detected and corrected on this side than on the other side, which leads to worse
performance.

I guess this could be corrected for by introducing a sufficiently long delay on
both sides, but I'm not sure if that's desirable.

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

OK. Sounds good. You may want to put some of this information (preferably
condensed) into a comment here.

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

Done.

+}
+
+TEST(EchoDetectorTests, EchoWithCaptureClockDrift) {
+  EchoDetector echo_detector;
+  std::vector<float> ones(160, 1.f);
+  std::vector<float> zeros(160, 0.f);
+
+  // In this test the capture signal has a delay of 10 frames w.r.t. the render
+  // signal, but is otherwise identical. Both signals are periodic with a 20
+  // frame interval. There is a simulated clock drift of 1% in this test, with
+  // the capture side producing data slightly faster.
+  for (int i = 0; i < 1000; i++) {

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

Same question as above about much longer test.

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

Also tried with 100000 iterations, same result.

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

Acknowledged.

+    if (i % 20 == 0) {
+      echo_detector.BufferRender(ones);
+      echo_detector.Process(zeros);
+    } else if (i % 20 == 10) {
+      echo_detector.BufferRender(zeros);
+      echo_detector.Process(ones);
+    } else {
+      echo_detector.BufferRender(zeros);
+      echo_detector.Process(zeros);
+    }
+    if (i % 100 == 0) {
+      // This is causing the simulated clock drift.
+      echo_detector.Process(zeros);
+    }
+  }
+  // We expect to detect echo with near certain likelihood.
+  EXPECT_NEAR(1.f, echo_detector.echo_likelihood(), 0.01f);
+}
+
+}  // namespace webrtc