Add detection for repeated audio in capturing.

content/renderer/media/repetition_detector.cc

Index: content/renderer/media/repetition_detector.cc
diff --git a/content/renderer/media/repetition_detector.cc b/content/renderer/media/repetition_detector.cc
new file mode 100644
index 0000000000000000000000000000000000000000..ad63c8115e0fda8e70bf734a875671dd66e86ce3
--- /dev/null
+++ b/content/renderer/media/repetition_detector.cc
@@ -0,0 +1,183 @@
+// 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/repetition_detector.h"
+
+#include "base/macros.h"  // arraysize

[Henrik Grunell, 2015/09/23 10:36:41]

Remove comments.

[minyue, 2015/09/25 14:40:07]

Done.

+#include "base/metrics/histogram_macros.h"  // UMA_HISTOGRAM_CUSTOM_ENUMERATION
+#include "base/numerics/safe_conversions.h"  // checked_cast
+#include "third_party/webrtc/base/checks.h"  // rtc::CheckedDivExact

[Henrik Grunell, 2015/09/23 10:36:41]

Remove. Use CHECK or DCHECK before division instead.

[minyue, 2015/09/25 14:40:07]

Done.

+
+namespace content {
+
+namespace {
+static const RepetitionDetector::Pattern kRepetitionPatterns[] = {

[Henrik Grunell, 2015/09/23 10:36:41]

Let the user of this class give the repetitions patterns in the constructor
instead, as an std::vector or std::array.

[Henrik Grunell, 2015/09/23 10:36:42]

Empty line before.

[tommi (sloooow) - chröme, 2015/09/25 08:57:14]

no need for static since this is in an anonymous namespace. same for other
globals.

[minyue, 2015/09/25 14:40:07]

I thought about letting user to register the patterns, but I think it is better
make the detector more self-contained, since it is related to UMA. The user may
or may not aware of this, and mess up things.

[minyue, 2015/09/25 14:40:07]

Done.

[minyue, 2015/09/25 14:40:08]

Done.

+    // {id_, look_back_ms_, min_length_ms_}

[Henrik Grunell, 2015/09/23 10:36:42]

Remove this comment. It duplicates info.

[minyue, 2015/09/25 14:40:07]

Done.

+    {1, 10, 10},

[tommi (sloooow) - chröme, 2015/09/25 08:57:14]

is id_ needed?  Looks like it's just pos+1.

[minyue, 2015/09/25 14:40:07]

Yes, indeed, but not necessarily, Imagine that we want to add pos=5 in future.

[tommi (sloooow) - chröme, 2015/09/28 10:28:39]

Sorry, I'm not following... it still looks to me like the id_ member in Pattern
isn't needed.

[minyue, 2015/09/28 14:47:50]

Sorry for being not clear enough. I meant that if we'd, by some reason, add to
the look back time (10 ms, 20, 30, ...) a 5 ms, or 15, 25 ..., we could not make
the id if we only allow id == look back time/10

[tommi (sloooow) - chröme, 2015/09/28 16:13:03]

Ah I see. Thanks.

+    {2, 20, 10},
+    {3, 30, 10},
+    {4, 40, 10},
+    {5, 50, 10},
+    {6, 60, 10},
+    {7, 70, 10},
+    {8, 80, 10},
+    {9, 90, 10},
+    {10, 100, 10},
+    {20, 200, 10},
+};
+static const size_t kMaxFrames = 480;  // 10ms * 48kHz

[Henrik Grunell, 2015/09/23 10:36:41]

Nit: 10 ms * 48 kHz

[Henrik Grunell, 2015/09/23 10:36:42]

Empty line before.

[tommi (sloooow) - chröme, 2015/09/25 08:57:14]

looks like this is assuming a certain sample rate.  What happens if we're
capturing at e.g. 88.2kHz?

[minyue, 2015/09/25 14:40:07]

Done.

[minyue, 2015/09/25 14:40:07]

No it does not assume any sample rate. kMaxFrames can be anything. It is only
used for copying a audio into buffer in a trunk. A frame longer than kMaxFrames
will divided into trunks and processed one-by-one. I added a comment here.

[minyue, 2015/09/25 14:40:08]

Done.

+}

[Henrik Grunell, 2015/09/23 10:36:42]

Empty line before.
Add "  // namespace"

[minyue, 2015/09/25 14:40:07]

Done.

+
+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_frames_ && zero) {

[Henrik Grunell, 2015/09/23 10:36:41]

count_frames_ == 0

[Henrik Grunell, 2015/09/23 10:36:41]

Nit: You can remove {} from single line if blocks if you like.

[minyue, 2015/09/25 14:40:07]

Yes, I generally prefer "0 == xxx" so that mistype of "==" into "=" can be
easily found. Is it necessary to change to "xxx == 0"

[minyue, 2015/09/25 14:40:07]

I am sometimes confused of which one is preferable. To me, one-line is like
temporal, if one adds anything, like lines of comment I just did, it should be
braced in {}.

+    all_zero_ = true;

[tommi (sloooow) - chröme, 2015/09/25 08:57:14]

is there a chance that all_zero_ is true when the function is called?

if not, please add DCHECK(!all_zero_) at the top.  If there is, then all_zero_
could be true even if zero is false or count_frames_ is non-zero.

[minyue, 2015/09/25 14:40:07]

The point is that when we find "0 == 0" as the first sample in a repeat, we do
not know if it will be an all-zero repetition (which we throw away), or this "0
== 0" is part of a valid repetition. So we should count it, but keep |all_zero_|
set until we find a non zero.

I added a comment here.

+  }
+  ++count_frames_;

[tommi (sloooow) - chröme, 2015/09/25 08:57:14]

the class doesn't have any locking. please add a thread checker.

[minyue, 2015/09/25 14:40:08]

Done.

+  if (!zero) {
+    all_zero_ = false;

[Henrik Grunell, 2015/09/23 10:36:42]

Is this correct? |zero| alone will determine what |all_zero_| is set to. The
first if block is useless. This function could be
++count_frames_;
all_zero_ = zero;

[tommi (sloooow) - chröme, 2015/09/25 08:57:14]

it looks like we're checking zero twice, setting all_zero_ to true or false
depending... can we simplify?

[minyue, 2015/09/25 14:40:07]

not really. 
1 2 3 0 1 2 3 0 will be considered all zero, with your proposal, right?

|all_zero_| is used to make sure that the length of
0 1 2 3 0 1 2 3 
is 4 instead of 3, while
0 0 0 0 0 0 0 0
won't be counted.

+  }
+}
+
+bool RepetitionDetector::State::HasValidReport(int sample_rate_hz) const {
+  return (!all_zero_ && count_frames_ >=
+      base::checked_cast<size_t>(min_length_ms_ * sample_rate_hz / 1000));

[tommi (sloooow) - chröme, 2015/09/25 08:57:14]

what benefit does checked_cast provide?

[minyue, 2015/09/25 14:40:07]

not much indeed. Only if min_length_ms_ or sample_rate_hz are mistakenly set
negative. So I think static_cast is enough.

+}
+
+void RepetitionDetector::State::Reset() {
+  count_frames_ = 0;
+  all_zero_ = true;
+  reported_ = false;
+}
+
+RepetitionDetector::RepetitionDetector()
+    : max_look_back_ms_(0),
+      sample_rate_hz_(0),
+      buffer_size_frames_(0),
+      buffer_end_index_(0),
+      max_frames_(kMaxFrames) {
+  RegisterRepetitionPatterns(kRepetitionPatterns,
+                             arraysize(kRepetitionPatterns));
+}
+
+RepetitionDetector::~RepetitionDetector() = default;
+
+void RepetitionDetector::RegisterRepetitionPatterns(const Pattern* patterns,
+                                                    size_t num_patterns) {
+  Pattern pattern;
+  for (size_t idx = 0; idx < num_patterns; idx++) {
+    pattern = patterns[idx];
+    ids_.push_back(pattern.id_);

[Henrik Grunell, 2015/09/23 10:36:42]

Can the ids and states be a map? Or do they need to be separate? What is |ids_|
used for, when the id is in the state already?

[minyue, 2015/09/25 14:40:07]

|ids_| is provided to UMA_HISTOGRAM_CUSTOM_ENUMERATION as the range of values.
It would be cumbersome to create |ids_| every time we call
UMA_HISTOGRAM_CUSTOM_ENUMERATION.

+    states_.push_back(new State(pattern.id_, pattern.look_back_ms_,

[tommi (sloooow) - chröme, 2015/09/25 08:57:14]

+1 on Henrik's comments. it seems strange that we're storing the id twice and
using two arrays for the same information.

[minyue, 2015/09/25 14:40:07]

please refer to my comment above

+                                pattern.min_length_ms_));
+    if (pattern.look_back_ms_ > max_look_back_ms_) {
+      max_look_back_ms_ = pattern.look_back_ms_;
+    }
+  }
+}
+
+void RepetitionDetector::Reset(size_t num_channels, int sample_rate_hz) {
+  num_channels_ = num_channels;
+  sample_rate_hz_ = sample_rate_hz;
+  int sample_1k = max_look_back_ms_ * sample_rate_hz_;

[Henrik Grunell, 2015/09/23 10:36:41]

What does the name mean? One sample? 1k samples?
Nit: Make it const.

[minyue, 2015/09/25 14:40:07]

Yes, it is a bad name, it means sample * 1000. I'd just remove it.

+  // |(sample_1k + 999) / 1000| is an arithmetic way to round up
+  // |sample_1k / 1000|
+  buffer_size_frames_ = (sample_1k + 999) / 1000 + max_frames_;
+  audio_buffer_.resize(buffer_size_frames_ * num_channels_);
+  for (auto state : states_) {
+    state->Reset();
+  }
+}
+
+void RepetitionDetector::AddFramesToBuffer(const float* data,
+                                           size_t num_frames) {
+  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 RepetitionDetector::Equal(const float* frame,
+                               int look_back_frames) const {
+  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 cdx = 0; cdx < num_channels_; ++cdx, ++frame, ++it) {

[Henrik Grunell, 2015/09/23 10:36:42]

What is cdx?

[minyue, 2015/09/25 14:40:07]

i'd rename it.

+    if (*frame != *it) {
+      return false;
+    }
+  }
+  return true;
+}
+
+bool RepetitionDetector::IsZero(const float* frame) const {
+  for (size_t cdx = 0; cdx < num_channels_; ++cdx, ++frame) {
+    if (*frame != 0) {
+      return false;
+    }
+  }
+  return true;
+}
+
+void RepetitionDetector::Detect(const float* data, size_t num_frames,
+                                size_t num_channels, int sample_rate_hz) {
+  DCHECK_GT(states_.size(), 0ul);
+  if (num_channels != num_channels_ || sample_rate_hz != sample_rate_hz_) {
+    Reset(num_channels, sample_rate_hz);
+  }
+
+  while (num_frames > max_frames_) {
+    Detect(data, max_frames_, num_channels, sample_rate_hz);
+    data += max_frames_ * num_channels;
+    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 (auto state : states_) {
+      const size_t look_back_frames =
+          rtc::CheckedDivExact(state->look_back_ms() * sample_rate_hz_, 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));
+          if (state->HasValidReport(sample_rate_hz)) {
+            ReportRepetition(state->id());

[Henrik Grunell, 2015/09/23 10:36:41]

This should be reported at the end of a session as a percentage of repetitions
detected (of all Detect calls), by the user. Keep count of the number of calls
to detect, and the number of detections, then add a function that returns the
percentage. Log it in MSAP. It would be nice to have it per pattern as you did,
but I'm not sure if that can be done with one histogram. And we shouldn't add
more than one.

[minyue, 2015/09/25 14:40:07]

Yes, what to add as UMA in this case is really disputable.

UMA is one-dimensional, meaning reporting a % for each repetition id is not
straightforward.
The only way I can think of is send multiple reports at the end. Something like
id=1 : 3 times
id=2 : 2 times
By this way, we can still tell the relative occurrence of different patterns.
This is not very different from reporting-upon-occurring.

What missing now is no report is made if no repetition happened. So we seems
lack of how often we see repetition from Media.AudioCapturerRepetition alone.
But my idea is
1. This frequency will be very small, and we are most interested in whether
repetition happened and what kind.
2. together with other measures (call time, etc) we can still know of the
absolute probability of repetitions.

If you have better ideas, let's discuss.

+            state->set_reported(true);
+          }
+        }
+      } else {
+        state->Reset();
+      }
+    }
+  }
+}
+
+void RepetitionDetector::ReportRepetition(int id) {
+   UMA_HISTOGRAM_CUSTOM_ENUMERATION(
+      "Media.AudioCapturerRepetition", id, ids_);
+}
+
+}  // namespace content