Adding audio RepetitionDetector in AudioProcessingModule.

webrtc/modules/audio_processing/repetition_detector.cc

Index: webrtc/modules/audio_processing/repetition_detector.cc
diff --git a/webrtc/modules/audio_processing/repetition_detector.cc b/webrtc/modules/audio_processing/repetition_detector.cc
new file mode 100644
index 0000000000000000000000000000000000000000..90a173a22161ccc95483a273527d11688092e4bc
--- /dev/null
+++ b/webrtc/modules/audio_processing/repetition_detector.cc
@@ -0,0 +1,155 @@
+/*
+ *  Copyright (c) 2015 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 "webrtc/modules/audio_processing/repetition_detector.h"
+
+#include <string.h>  // memset
+
+#include "webrtc/base/checks.h"
+
+namespace webrtc {
+
+namespace {
+static const RepetitionDetector::Pattern kRepetitionPatterns[] = {
+    // {id_, look_back_, look_back_range_, length_, length_range_}

[minyue-webrtc, 2015/08/28 14:27:00]

Comment here should be updated, I forgot.

[minyue-webrtc, 2015/09/03 13:23:58]

Done.

+    {0, 10, 10},
+    {1, 100, 100}
+};
+}
+
+RepetitionDetector::State::State(int id, int look_back_ms, int min_length_ms)
+    : id_(id),
+      look_back_ms_(look_back_ms),
+      min_length_ms_(min_length_ms) {
+  Reset();
+}
+
+void RepetitionDetector::State::Increment(bool zero) {
+  if (0 == count_samples_ && zero) {

[hlundin-webrtc, 2015/08/31 13:46:46]

You do not need this if statement.

[minyue-webrtc, 2015/09/03 13:23:58]

I know that this is redundant if Reset was called properly, well, it helps to
make this function more complete.

If to reduce redundancy, I'd rather remove all_zero_ = true; in Reset()

[hlundin-webrtc, 2015/09/15 09:26:38]

I think you are being overly aggressive against your own code. If you worry
about bugs in your own code, use a DCHECK.

+    all_zero_ = true;
+  }
+  ++count_samples_;
+  if (!zero) {
+    all_zero_ = false;
+  }
+}
+
+bool RepetitionDetector::State::HasValidReport(int sample_rate_hz) const {
+  return (!all_zero_ && static_cast<int>(count_samples_) >=

[hlundin-webrtc, 2015/08/31 13:46:46]

rtc::checked_cast. But I do think it would be better to cast 
rtc::checked_cast<size_t>(min_length_ms_ * sample_rate_hz / 1000).

[minyue-webrtc, 2015/09/03 13:23:58]

Ok, I like it, and hope that it can stay when I move the whole thing to Chromium

[hlundin-webrtc, 2015/09/15 09:26:38]

Acknowledged.

+      min_length_ms_ * sample_rate_hz / 1000);
+}
+
+bool RepetitionDetector::State::AlreadyReported() const {

[hlundin-webrtc, 2015/08/31 13:46:46]

Change name to reported().

[minyue-webrtc, 2015/09/03 13:23:58]

Done.

+  return reported_;
+}
+
+void RepetitionDetector::State::SetReported() {

[hlundin-webrtc, 2015/08/31 13:46:46]

Perhaps change name to set_reported(bool value).

[minyue-webrtc, 2015/09/03 13:23:58]

Done.

+  reported_ = true;
+}
+
+void RepetitionDetector::State::Reset() {
+  count_samples_ = 0;
+  all_zero_ = true;
+  reported_ = false;
+}
+
+RepetitionDetector::RepetitionDetector()
+    : max_look_back_ms_(0),
+      audio_buffer_(nullptr),
+      sample_rate_hz_(0),
+      buffer_size_samples_(0),
+      buffer_end_index_(0) {
+  RegisterRepetitionPatterns(kRepetitionPatterns,
+                             sizeof(kRepetitionPatterns) / sizeof (Pattern));
+}
+
+RepetitionDetector::~RepetitionDetector() {
+  ClearRepetitionPatterns();
+}
+
+void RepetitionDetector::RegisterRepetitionPatterns(const Pattern* patterns,
+                                                    size_t num_patterns) {
+  Pattern pattern;
+  for (size_t idx = 0; idx < num_patterns; idx++) {
+    pattern = patterns[idx];
+    states_.push_back(new State(pattern.id_, pattern.look_back_ms_,
+                                pattern.min_length_ms_));
+    if (pattern.look_back_ms_ > max_look_back_ms_) {
+      max_look_back_ms_ = pattern.look_back_ms_;
+    }
+  }
+}
+
+void RepetitionDetector::ClearRepetitionPatterns() {
+  for (auto state : states_) {

[Andrew MacDonald, 2015/08/28 17:43:42]

How often is this called? You should strive to avoid dynamic memory management
during real-time operation. Can you instead give state a Reset() method or
something? ...wait it _has_ a Reset() method :) Why not call that here?

If this is just for destruction time, you shouldn't need to do this at all. Wrap
these in an RAII type that will clean itself up. If you want a vector-of-state
pointers, use ScopedVector.

[hlundin-webrtc, 2015/08/31 13:46:46]

It's only called in the destructor of RepetitionDetector. Move this code to the
destructor, or use ScopedVector as suggested.

[minyue-webrtc, 2015/09/03 13:23:58]

Done.

+    delete state;
+  }
+  states_.clear();
+  max_look_back_ms_ = 0;
+}
+
+void RepetitionDetector::Reset(size_t bytes_per_sample, int sample_rate_hz) {
+  bytes_per_sample_ = bytes_per_sample;
+  sample_rate_hz_ = sample_rate_hz;
+  int sample_1k = max_look_back_ms_ * sample_rate_hz_;
+  buffer_size_samples_ = sample_1k / 1000 + (sample_1k % 1000 != 0);

[hlundin-webrtc, 2015/08/31 13:46:46]

This is rounding up, right? Consider (sample_1k + 999) / 1000, instead.

[minyue-webrtc, 2015/09/01 10:21:48]

nice!

+  audio_buffer_.reset(new char[buffer_size_samples_ * bytes_per_sample_]());
+  for (auto state : states_) {
+    state->Reset();
+  }
+}
+
+void RepetitionDetector::AddSampleToBuffer(const void* sample) {
+  buffer_end_index_++;

[hlundin-webrtc, 2015/08/31 13:46:46]

buffer_end_index_ is initialized to 0, but it is incremented _before_ the first
samples are added. This seems backwards to me.

[minyue-webrtc, 2015/09/03 13:23:58]

Done.

+  if (buffer_end_index_ == buffer_size_samples_) {
+    buffer_end_index_ = 0;
+  }
+  memcpy(&audio_buffer_[buffer_end_index_ * bytes_per_sample_], sample,
+         bytes_per_sample_);
+}
+
+void RepetitionDetector::Detect(const void* data, size_t bytes_per_sample,
+                                size_t samples_per_channel,
+                                int sample_rate_hz) {
+  DCHECK_GT(states_.size(), 0ul);
+  if (bytes_per_sample != bytes_per_sample_ ||
+      sample_rate_hz != sample_rate_hz_) {
+    Reset(bytes_per_sample, sample_rate_hz);
+  }
+
+  std::unique_ptr<char[]> zero(new char[bytes_per_sample]());

[Andrew MacDonald, 2015/08/31 16:05:31]

You shouldn't need this.

[minyue-webrtc, 2015/09/03 13:23:57]

Done.

+  const char* sample = reinterpret_cast<const char*>(data);

[Andrew MacDonald, 2015/08/31 16:05:31]

No, no, use the type you want.

[minyue-webrtc, 2015/09/01 10:21:48]

Yes, we may use template, but I also add two comments:
1. current way might be easier for multichannel sample
2. Even if we use types, it may not be best to compare values in the fashion of
a==b, since the behavior of == for floating point may be unpredictable.

[ajm, 2015/09/02 05:28:28]

As described above, you should be explicit about your multiple channels.
It's certainly no worse than memcmp! As in another comment, you want to use an
epsilon for floating point comparison.

[minyue-webrtc, 2015/09/03 13:23:58]

Done.

+
+  for (size_t idx = 0; idx < samples_per_channel;
+      ++idx, sample += bytes_per_sample_) {
+    for (auto state : states_) {
+      size_t look_back_samples =
+          rtc::CheckedDivExact(state->look_back_ms() * sample_rate_hz_, 1000);
+      const char* look_back_pointer = audio_buffer_.get() +
+          (buffer_end_index_ + buffer_size_samples_ - look_back_samples + 1) %
+          buffer_size_samples_ * bytes_per_sample_;
+
+      if (memcmp(look_back_pointer, sample, bytes_per_sample) == 0) {

[hlundin-webrtc, 2015/08/31 13:46:46]

This memcmp is to find out if all of |sample| is zero, right? I'm thinking that
there is potentially a lot of overhead involved in allocating a dynamic array
just to compare with.

[Andrew MacDonald, 2015/08/31 16:05:31]

Absolutely. Use the correct types and just compare each value with zero.

Don't use dynamic allocation in functions called for each chunk of audio.

[minyue-webrtc, 2015/09/03 13:23:58]

Done.

+        if (!state->AlreadyReported()) {
+          state->Increment(memcmp(zero.get(), sample, bytes_per_sample) == 0);

[minyue-webrtc, 2015/09/01 10:21:48]

Zero is actually this line. I can move the zero allocation in Reset(), to avoid
dynamic allocation for each frame of audio.

I think memcmp is still better than <T>a == <T>b since if T is floating point,
the behavior may be unclear.

[ajm, 2015/09/02 05:28:28]

How is a == b any less clear than memcmp for floating point?

If you're worried about floating point equality, you should use a small epsilon
around the diff to compare. Consider for example EXPECT_FLOAT_EQ or EXPECT_NEAR
in gtest.

[minyue-webrtc, 2015/09/03 13:23:58]

Done.

+          if (state->HasValidReport(sample_rate_hz)) {
+            ReportRepetition(state->id());
+            state->SetReported();
+          }
+        }
+      } else {
+        state->Reset();
+      }
+    }
+    AddSampleToBuffer(sample);
+  }
+}
+
+}  // namespace webrtc