Add detection for repeated audio in capturing.

content/renderer/media/audio_repetition_detector.cc

+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "content/renderer/media/audio_repetition_detector.h"
+
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/metrics/histogram_macros.h"
+
+namespace content {
+
+namespace {
+// Minimum duration of a repetition.
+const int kMinLengthMs = 1;
+
+// The following variables defines the look back time of repetitions that will
+// be logged. The complexity of the detector is proportional to the number of
+// look back times we keep track.
+const int kMinLookbackTimeMS = 10;

[Henrik Grunell, 2015/10/16 07:59:50]

Nit: Ms

[minyue, 2015/10/16 08:34:42]

Oh, yes

+const int kMaxLookbackTimeMS = 200;
+const int kLookbackTimeStepMS = 10;
+
+// This is used for increasing the efficiency of copying data into the buffer.
+// Input longer than |kMaxFrames| won't be a problem, and will be devided into
+// chunks automatically.
+const size_t kMaxFrames = 480;  // 10 ms * 48 kHz
+
+}  // namespace
+
+AudioRepetitionDetector::AudioRepetitionDetector()
+    : max_look_back_ms_(0),
+      min_length_ms_(kMinLengthMs),

[Henrik Grunell, 2015/10/16 07:59:50]

Can |min_length_ms_| be removed?

[minyue, 2015/10/16 08:34:42]

|min_length_ms_| is important in the algorithm, and it would be good to make it
a member variable.

Actually, there is a unittest on it, and it changes its value to verify that it
functions.

[Henrik Grunell, 2015/10/16 08:44:11]

I meant to use the constant instead since it never changes.
Why does that have to be tested? It's not supposed to change in the code.

[minyue, 2015/10/16 09:27:27]

Sure it is not really subjected to change in current implementation. But it
should be robust to changes in |kMinLengthMs|. Since |kMinLengthMs| is quite
arbitrarily set, it may change in future.

Now back to the test. In the test, the sampling rate is set very low, 1 ms for 1
sample, so that the test can be very clean, with "kMinLengthMs = 1", it means
any 1 sample replication will trigger a report. To make the test cover the case
that shorter repetition won't trigger report, I modified |min_length_ms_|, which
also protect future changes in |kMinLengthMs|.

[Henrik Grunell, 2015/10/16 11:08:11]

I'm not sure I understand why the test has a lower sampling rate. Is it because
of the data chunk size will be large? It's better to not clutter the production
code for test purposes. Let the test handle that.

[minyue, 2015/10/23 12:05:23]

Already covered with offline discussion.

Adding a memo here

With separation of the detector and the UMA reporting mechanism, the detector
does not have min_length_ms_ and max_frames_ any more.

+      sample_rate_(0),
+      buffer_size_frames_(0),
+      buffer_end_index_(0),
+      max_frames_(kMaxFrames) {

[Henrik Grunell, 2015/10/16 07:59:50]

Can |max_frames_| be removed?

[minyue, 2015/10/16 08:34:42]

same as min_length_ms_

[minyue, 2015/10/16 09:27:28]

|kMaxFrames| is set to be the largest possible frame size, that means Detect()
does not need to slice the input sequence to chunks in all cases. But we need to
test cases that the code that performs the slicing works correctly. For that
purpose, I modified |max_frames_| in one test.

[Henrik Grunell, 2015/10/16 11:08:11]

Can you explain why we need to test with some other value than the constant
that's actually used? It's confusing, another design around this would probably
make things clearer.

+  for (int time = kMaxLookbackTimeMS; time >= kMinLookbackTimeMS;
+      time -= kLookbackTimeStepMS)

[Henrik Grunell, 2015/10/16 07:59:50]

Use {} (Since total for block is more than 2 lines.)

Nit: Align "time -= ..." with "int" above.

[minyue, 2015/10/16 08:34:42]

Ok. But why alligning -=, I am not aware that line breaking rule.

[Henrik Grunell, 2015/10/16 08:44:11]

To align the second line with the (.

for (int time = kMaxLookbackTimeMS; time >= kMinLookbackTimeMS;
     time -= kLookbackTimeStepMS)

[minyue, 2015/10/16 09:27:28]

ok. these ;-separated lines seems to me different from arguments to a function,
and therefore, I usually apply a 4-space line-breaking rule. But I may be wrong.

[Henrik Grunell, 2015/10/16 11:08:11]

Align as functions is common practice in Chromium.

[ajm, 2015/10/16 15:54:47]

Just run git cl format and be done with it :)

+    RegisterLookbackTime(time);
+
+  // May be created in the main render thread and used in the audio threads.
+  thread_checker_.DetachFromThread();
+}
+
+AudioRepetitionDetector::~AudioRepetitionDetector() = default;
+
+void AudioRepetitionDetector::Detect(const float* data, size_t num_frames,
+                                     size_t num_channels, int sample_rate) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  DCHECK(!states_.empty());
+
+  if (num_channels != num_channels_ || sample_rate != sample_rate_)
+    Reset(num_channels, sample_rate);
+
+  // The maximum number of frames |audio_buffer_| can take in is |max_frames_|.
+  // Therefore, input data with larger frames needs be divided into chunks.
+  const size_t chunk_size = max_frames_ * num_channels;
+  while (num_frames > max_frames_) {
+    Detect(data, max_frames_, num_channels, sample_rate);
+    data += chunk_size;
+    num_frames -= max_frames_;
+  }
+
+  if (num_frames == 0)
+    return;
+
+  AddFramesToBuffer(data, num_frames);
+
+  for (size_t idx = num_frames; idx > 0; --idx, data += num_channels) {
+    for (State* state : states_) {
+      // Look back position depends on the sample rate. It is rounded down to
+      // the closest integer.
+      const size_t look_back_frames =
+          state->look_back_ms() * sample_rate_ / 1000;
+      // Equal(data, offset) checks if |data| equals the audio frame located
+      // |offset| frames from the end of buffer. Now a full frame has been
+      // inserted to the buffer, and thus |offset| should compensate for it.
+      if (Equal(data, look_back_frames + idx)) {
+        if (!state->reported()) {
+          state->Increment(IsZero(data, num_channels));
+          if (HasValidReport(state)) {
+            ReportRepetition(state->look_back_ms());
+            state->set_reported(true);
+          }
+        }
+      } else {
+        state->Reset();
+      }
+    }
+  }
+}
+
+AudioRepetitionDetector::State::State(int look_back_ms)
+    : look_back_ms_(look_back_ms) {
+  Reset();
+}
+
+void AudioRepetitionDetector::State::Increment(bool zero) {
+  if (0 == count_frames_ && zero) {
+    // If a repetition starts with zeros, we enter the all zero mode until
+    // a non zero is found later. The point is that the beginning zeros should
+    // be counted in the length of the repetition as long as the repetition does
+    // not comprise only zeros.
+    all_zero_ = true;
+  }
+  ++count_frames_;
+  if (!zero)
+    all_zero_ = false;
+}
+
+void AudioRepetitionDetector::State::Reset() {
+  count_frames_ = 0;
+  all_zero_ = true;
+  reported_ = false;
+}
+
+void AudioRepetitionDetector::RegisterLookbackTime(int look_back_ms) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  // States are added in the order of their look back times.
+  auto it = states_.begin();
+  for (; it != states_.end(); ++it) {
+    const int it_look_back = (*it)->look_back_ms();
+    if (it_look_back == look_back_ms)
+      return;
+    if (it_look_back < look_back_ms)
+      break;
+  }
+  states_.insert(it, new State(look_back_ms));
+  if (look_back_ms > max_look_back_ms_) {
+    max_look_back_ms_ = look_back_ms;
+  }
+}
+
+void AudioRepetitionDetector::Reset(size_t num_channels, int sample_rate) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  num_channels_ = num_channels;
+  sample_rate_ = sample_rate;
+
+  // |(xxx + 999) / 1000| is an arithmetic way to round up |xxx / 1000|.
+  buffer_size_frames_ =
+      (max_look_back_ms_ * sample_rate_ + 999) / 1000 + max_frames_;
+
+  audio_buffer_.resize(buffer_size_frames_ * num_channels_);
+  for (State* state : states_)
+    state->Reset();
+}
+
+void AudioRepetitionDetector::AddFramesToBuffer(const float* data,
+                                                size_t num_frames) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  DCHECK_LE(num_frames, buffer_size_frames_);
+  const size_t margin = buffer_size_frames_ - buffer_end_index_;
+  const auto it = audio_buffer_.begin() + buffer_end_index_ * num_channels_;
+  if (num_frames <= margin) {
+    std::copy(data, data + num_frames * num_channels_, it);
+    buffer_end_index_ += num_frames;
+  } else {
+    std::copy(data, data + margin * num_channels_, it);
+    std::copy(data + margin * num_channels_, data + num_frames * num_channels_,
+              audio_buffer_.begin());
+    buffer_end_index_ = num_frames - margin;
+  }
+}
+
+bool AudioRepetitionDetector::Equal(const float* frame,
+                                    int look_back_frames) const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  const size_t look_back_index =
+      (buffer_end_index_ + buffer_size_frames_ - look_back_frames) %
+      buffer_size_frames_ ;
+  auto it = audio_buffer_.begin() + look_back_index * num_channels_;
+  for (size_t channel = 0; channel < num_channels_; ++channel, ++frame, ++it) {
+    if (*frame != *it)
+      return false;
+  }
+  return true;
+}
+
+bool AudioRepetitionDetector::IsZero(const float* frame,
+                                     size_t num_channels) const {
+  for (size_t channel = 0; channel < num_channels; ++channel, ++frame) {
+    if (*frame != 0)
+      return false;
+  }
+  return true;
+}
+
+bool AudioRepetitionDetector::HasValidReport(const State* state) const {
+  return (!state->all_zero() && state->count_frames() >=
+      static_cast<size_t>(min_length_ms_ * sample_rate_ / 1000));
+}
+
+void AudioRepetitionDetector::ReportRepetition(int look_back_ms) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  UMA_HISTOGRAM_CUSTOM_COUNTS(
+      "Media.AudioCapturerRepetition", look_back_ms,
+      kMinLookbackTimeMS, kMaxLookbackTimeMS,
+      (kMaxLookbackTimeMS - kMinLookbackTimeMS) / kLookbackTimeStepMS + 1);
+}
+
+}  // namespace content