Adding upstream version 1:115.7.0.upstream/1%115.7.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

5 files changed, 495 insertions, 0 deletions

diff --git a/third_party/libwebrtc/api/numerics/BUILD.gn b/third_party/libwebrtc/api/numerics/BUILD.gn
new file mode 100644
index 0000000000..408dc5b9f1
--- /dev/null
+++ b/third_party/libwebrtc/api/numerics/BUILD.gn
@@ -0,0 +1,41 @@
+# Copyright (c) 2020 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.
+
+import("../../webrtc.gni")
+
+rtc_library("numerics") {
+  visibility = [ "*" ]
+
+  sources = [
+    "samples_stats_counter.cc",
+    "samples_stats_counter.h",
+  ]
+  deps = [
+    "..:array_view",
+    "../../rtc_base:checks",
+    "../../rtc_base:rtc_numerics",
+    "../../rtc_base:timeutils",
+    "../units:timestamp",
+  ]
+  absl_deps = [ "//third_party/abseil-cpp/absl/algorithm:container" ]
+}
+
+if (rtc_include_tests) {
+  rtc_library("numerics_unittests") {
+    visibility = [ "*" ]
+    testonly = true
+
+    sources = [ "samples_stats_counter_unittest.cc" ]
+
+    deps = [
+      ":numerics",
+      "../../test:test_support",
+    ]
+    absl_deps = [ "//third_party/abseil-cpp/absl/algorithm:container" ]
+  }
+}
diff --git a/third_party/libwebrtc/api/numerics/DEPS b/third_party/libwebrtc/api/numerics/DEPS
new file mode 100644
index 0000000000..2d89d57557
--- /dev/null
+++ b/third_party/libwebrtc/api/numerics/DEPS
@@ -0,0 +1,6 @@
+specific_include_rules = {
+  # Some internal headers are allowed even in API headers:
+  "samples_stats_counter\.h": [
+    "+rtc_base/numerics/running_statistics.h",
+  ]
+}
diff --git a/third_party/libwebrtc/api/numerics/samples_stats_counter.cc b/third_party/libwebrtc/api/numerics/samples_stats_counter.cc
new file mode 100644
index 0000000000..4eb0cde299
--- /dev/null
+++ b/third_party/libwebrtc/api/numerics/samples_stats_counter.cc
@@ -0,0 +1,101 @@
+/*
+ *  Copyright (c) 2018 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 "api/numerics/samples_stats_counter.h"
+
+#include <algorithm>
+#include <cmath>
+
+#include "absl/algorithm/container.h"
+#include "rtc_base/time_utils.h"
+
+namespace webrtc {
+
+SamplesStatsCounter::SamplesStatsCounter() = default;
+SamplesStatsCounter::SamplesStatsCounter(size_t expected_samples_count) {
+  samples_.reserve(expected_samples_count);
+}
+
+SamplesStatsCounter::~SamplesStatsCounter() = default;
+SamplesStatsCounter::SamplesStatsCounter(const SamplesStatsCounter&) = default;
+SamplesStatsCounter& SamplesStatsCounter::operator=(
+    const SamplesStatsCounter&) = default;
+SamplesStatsCounter::SamplesStatsCounter(SamplesStatsCounter&&) = default;
+SamplesStatsCounter& SamplesStatsCounter::operator=(SamplesStatsCounter&&) =
+    default;
+
+void SamplesStatsCounter::AddSample(double value) {
+  AddSample(StatsSample{value, Timestamp::Micros(rtc::TimeMicros())});
+}
+
+void SamplesStatsCounter::AddSample(StatsSample sample) {
+  stats_.AddSample(sample.value);
+  samples_.push_back(sample);
+  sorted_ = false;
+}
+
+void SamplesStatsCounter::AddSamples(const SamplesStatsCounter& other) {
+  stats_.MergeStatistics(other.stats_);
+  samples_.insert(samples_.end(), other.samples_.begin(), other.samples_.end());
+  sorted_ = false;
+}
+
+double SamplesStatsCounter::GetPercentile(double percentile) {
+  RTC_DCHECK(!IsEmpty());
+  RTC_CHECK_GE(percentile, 0);
+  RTC_CHECK_LE(percentile, 1);
+  if (!sorted_) {
+    absl::c_sort(samples_, [](const StatsSample& a, const StatsSample& b) {
+      return a.value < b.value;
+    });
+    sorted_ = true;
+  }
+  const double raw_rank = percentile * (samples_.size() - 1);
+  double int_part;
+  double fract_part = std::modf(raw_rank, &int_part);
+  size_t rank = static_cast<size_t>(int_part);
+  if (fract_part >= 1.0) {
+    // It can happen due to floating point calculation error.
+    rank++;
+    fract_part -= 1.0;
+  }
+
+  RTC_DCHECK_GE(rank, 0);
+  RTC_DCHECK_LT(rank, samples_.size());
+  RTC_DCHECK_GE(fract_part, 0);
+  RTC_DCHECK_LT(fract_part, 1);
+  RTC_DCHECK(rank + fract_part == raw_rank);
+
+  const double low = samples_[rank].value;
+  const double high = samples_[std::min(rank + 1, samples_.size() - 1)].value;
+  return low + fract_part * (high - low);
+}
+
+SamplesStatsCounter operator*(const SamplesStatsCounter& counter,
+                              double value) {
+  SamplesStatsCounter out;
+  for (const auto& sample : counter.GetTimedSamples()) {
+    out.AddSample(
+        SamplesStatsCounter::StatsSample{sample.value * value, sample.time});
+  }
+  return out;
+}
+
+SamplesStatsCounter operator/(const SamplesStatsCounter& counter,
+                              double value) {
+  SamplesStatsCounter out;
+  for (const auto& sample : counter.GetTimedSamples()) {
+    out.AddSample(
+        SamplesStatsCounter::StatsSample{sample.value / value, sample.time});
+  }
+  return out;
+}
+
+}  // namespace webrtc
diff --git a/third_party/libwebrtc/api/numerics/samples_stats_counter.h b/third_party/libwebrtc/api/numerics/samples_stats_counter.h
new file mode 100644
index 0000000000..9d72296317
--- /dev/null
+++ b/third_party/libwebrtc/api/numerics/samples_stats_counter.h
@@ -0,0 +1,126 @@
+/*
+ *  Copyright (c) 2018 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.
+ */
+
+#ifndef API_NUMERICS_SAMPLES_STATS_COUNTER_H_
+#define API_NUMERICS_SAMPLES_STATS_COUNTER_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "api/array_view.h"
+#include "api/units/timestamp.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/numerics/running_statistics.h"
+
+namespace webrtc {
+
+// This class extends RunningStatistics by providing GetPercentile() method,
+// while slightly adapting the interface.
+class SamplesStatsCounter {
+ public:
+  struct StatsSample {
+    double value;
+    Timestamp time;
+    // Sample's specific metadata.
+    std::map<std::string, std::string> metadata;
+  };
+
+  SamplesStatsCounter();
+  explicit SamplesStatsCounter(size_t expected_samples_count);
+  ~SamplesStatsCounter();
+  SamplesStatsCounter(const SamplesStatsCounter&);
+  SamplesStatsCounter& operator=(const SamplesStatsCounter&);
+  SamplesStatsCounter(SamplesStatsCounter&&);
+  SamplesStatsCounter& operator=(SamplesStatsCounter&&);
+
+  // Adds sample to the stats in amortized O(1) time.
+  void AddSample(double value);
+  void AddSample(StatsSample sample);
+
+  // Adds samples from another counter.
+  void AddSamples(const SamplesStatsCounter& other);
+
+  // Returns if there are any values in O(1) time.
+  bool IsEmpty() const { return samples_.empty(); }
+  // Returns the amount of samples added into counter in O(1) time.
+  int64_t NumSamples() const { return stats_.Size(); }
+
+  // Returns min in O(1) time. This function may not be called if there are no
+  // samples.
+  double GetMin() const {
+    RTC_DCHECK(!IsEmpty());
+    return *stats_.GetMin();
+  }
+  // Returns max in O(1) time. This function may not be called if there are no
+  // samples.
+  double GetMax() const {
+    RTC_DCHECK(!IsEmpty());
+    return *stats_.GetMax();
+  }
+  // Returns average in O(1) time. This function may not be called if there are
+  // no samples.
+  double GetAverage() const {
+    RTC_DCHECK(!IsEmpty());
+    return *stats_.GetMean();
+  }
+  // Returns variance in O(1) time. This function may not be called if there are
+  // no samples.
+  double GetVariance() const {
+    RTC_DCHECK(!IsEmpty());
+    return *stats_.GetVariance();
+  }
+  // Returns standard deviation in O(1) time. This function may not be called if
+  // there are no samples.
+  double GetStandardDeviation() const {
+    RTC_DCHECK(!IsEmpty());
+    return *stats_.GetStandardDeviation();
+  }
+  // Returns percentile in O(nlogn) on first call and in O(1) after, if no
+  // additions were done. This function may not be called if there are no
+  // samples.
+  //
+  // `percentile` has to be in [0; 1]. 0 percentile is the min in the array and
+  // 1 percentile is the max in the array.
+  double GetPercentile(double percentile);
+  // Returns array view with all samples added into counter. There are no
+  // guarantees of order, so samples can be in different order comparing to in
+  // which they were added into counter. Also return value will be invalidate
+  // after call to any non const method.
+  rtc::ArrayView<const StatsSample> GetTimedSamples() const { return samples_; }
+  std::vector<double> GetSamples() const {
+    std::vector<double> out;
+    out.reserve(samples_.size());
+    for (const auto& sample : samples_) {
+      out.push_back(sample.value);
+    }
+    return out;
+  }
+
+ private:
+  webrtc_impl::RunningStatistics<double> stats_;
+  std::vector<StatsSample> samples_;
+  bool sorted_ = false;
+};
+
+// Multiply all sample values on `value` and return new SamplesStatsCounter
+// with resulted samples. Doesn't change origin SamplesStatsCounter.
+SamplesStatsCounter operator*(const SamplesStatsCounter& counter, double value);
+inline SamplesStatsCounter operator*(double value,
+                                     const SamplesStatsCounter& counter) {
+  return counter * value;
+}
+// Divide all sample values on `value` and return new SamplesStatsCounter with
+// resulted samples. Doesn't change origin SamplesStatsCounter.
+SamplesStatsCounter operator/(const SamplesStatsCounter& counter, double value);
+
+}  // namespace webrtc
+
+#endif  // API_NUMERICS_SAMPLES_STATS_COUNTER_H_
diff --git a/third_party/libwebrtc/api/numerics/samples_stats_counter_unittest.cc b/third_party/libwebrtc/api/numerics/samples_stats_counter_unittest.cc
new file mode 100644
index 0000000000..1f9cabfb29
--- /dev/null
+++ b/third_party/libwebrtc/api/numerics/samples_stats_counter_unittest.cc
@@ -0,0 +1,221 @@
+/*
+ *  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 "api/numerics/samples_stats_counter.h"
+
+#include <math.h>
+
+#include <random>
+#include <vector>
+
+#include "absl/algorithm/container.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace {
+
+SamplesStatsCounter CreateStatsFilledWithIntsFrom1ToN(int n) {
+  std::vector<double> data;
+  for (int i = 1; i <= n; i++) {
+    data.push_back(i);
+  }
+  absl::c_shuffle(data, std::mt19937(std::random_device()()));
+
+  SamplesStatsCounter stats;
+  for (double v : data) {
+    stats.AddSample(v);
+  }
+  return stats;
+}
+
+// Add n samples drawn from uniform distribution in [a;b].
+SamplesStatsCounter CreateStatsFromUniformDistribution(int n,
+                                                       double a,
+                                                       double b) {
+  std::mt19937 gen{std::random_device()()};
+  std::uniform_real_distribution<> dis(a, b);
+
+  SamplesStatsCounter stats;
+  for (int i = 1; i <= n; i++) {
+    stats.AddSample(dis(gen));
+  }
+  return stats;
+}
+
+class SamplesStatsCounterTest : public ::testing::TestWithParam<int> {};
+
+constexpr int SIZE_FOR_MERGE = 10;
+
+}  // namespace
+
+TEST(SamplesStatsCounterTest, FullSimpleTest) {
+  SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(100);
+
+  EXPECT_TRUE(!stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
+  EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
+  EXPECT_NEAR(stats.GetAverage(), 50.5, 1e-6);
+  for (int i = 1; i <= 100; i++) {
+    double p = i / 100.0;
+    EXPECT_GE(stats.GetPercentile(p), i);
+    EXPECT_LT(stats.GetPercentile(p), i + 1);
+  }
+}
+
+TEST(SamplesStatsCounterTest, VarianceAndDeviation) {
+  SamplesStatsCounter stats;
+  stats.AddSample(2);
+  stats.AddSample(2);
+  stats.AddSample(-1);
+  stats.AddSample(5);
+
+  EXPECT_DOUBLE_EQ(stats.GetAverage(), 2.0);
+  EXPECT_DOUBLE_EQ(stats.GetVariance(), 4.5);
+  EXPECT_DOUBLE_EQ(stats.GetStandardDeviation(), sqrt(4.5));
+}
+
+TEST(SamplesStatsCounterTest, FractionPercentile) {
+  SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
+
+  EXPECT_DOUBLE_EQ(stats.GetPercentile(0.5), 3);
+}
+
+TEST(SamplesStatsCounterTest, TestBorderValues) {
+  SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
+
+  EXPECT_GE(stats.GetPercentile(0.01), 1);
+  EXPECT_LT(stats.GetPercentile(0.01), 2);
+  EXPECT_DOUBLE_EQ(stats.GetPercentile(1.0), 5);
+}
+
+TEST(SamplesStatsCounterTest, VarianceFromUniformDistribution) {
+  // Check variance converge to 1/12 for [0;1) uniform distribution.
+  // Acts as a sanity check for NumericStabilityForVariance test.
+  SamplesStatsCounter stats = CreateStatsFromUniformDistribution(1e6, 0, 1);
+
+  EXPECT_NEAR(stats.GetVariance(), 1. / 12, 1e-3);
+}
+
+TEST(SamplesStatsCounterTest, NumericStabilityForVariance) {
+  // Same test as VarianceFromUniformDistribution,
+  // except the range is shifted to [1e9;1e9+1).
+  // Variance should also converge to 1/12.
+  // NB: Although we lose precision for the samples themselves, the fractional
+  //     part still enjoys 22 bits of mantissa and errors should even out,
+  //     so that couldn't explain a mismatch.
+  SamplesStatsCounter stats =
+      CreateStatsFromUniformDistribution(1e6, 1e9, 1e9 + 1);
+
+  EXPECT_NEAR(stats.GetVariance(), 1. / 12, 1e-3);
+}
+
+TEST_P(SamplesStatsCounterTest, AddSamples) {
+  int data[SIZE_FOR_MERGE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  // Split the data in different partitions.
+  // We have 11 distinct tests:
+  //   * Empty merged with full sequence.
+  //   * 1 sample merged with 9 last.
+  //   * 2 samples merged with 8 last.
+  //   [...]
+  //   * Full merged with empty sequence.
+  // All must lead to the same result.
+  SamplesStatsCounter stats0, stats1;
+  for (int i = 0; i < GetParam(); ++i) {
+    stats0.AddSample(data[i]);
+  }
+  for (int i = GetParam(); i < SIZE_FOR_MERGE; ++i) {
+    stats1.AddSample(data[i]);
+  }
+  stats0.AddSamples(stats1);
+
+  EXPECT_EQ(stats0.GetMin(), 0);
+  EXPECT_EQ(stats0.GetMax(), 9);
+  EXPECT_DOUBLE_EQ(stats0.GetAverage(), 4.5);
+  EXPECT_DOUBLE_EQ(stats0.GetVariance(), 8.25);
+  EXPECT_DOUBLE_EQ(stats0.GetStandardDeviation(), sqrt(8.25));
+  EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.1), 0.9);
+  EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.5), 4.5);
+  EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.9), 8.1);
+}
+
+TEST(SamplesStatsCounterTest, MultiplyRight) {
+  SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(10);
+
+  EXPECT_TRUE(!stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
+  EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
+  EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
+
+  SamplesStatsCounter multiplied_stats = stats * 10;
+  EXPECT_TRUE(!multiplied_stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(multiplied_stats.GetMin(), 10.0);
+  EXPECT_DOUBLE_EQ(multiplied_stats.GetMax(), 100.0);
+  EXPECT_DOUBLE_EQ(multiplied_stats.GetAverage(), 55.0);
+  EXPECT_EQ(multiplied_stats.GetSamples().size(), stats.GetSamples().size());
+
+  // Check that origin stats were not modified.
+  EXPECT_TRUE(!stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
+  EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
+  EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
+}
+
+TEST(SamplesStatsCounterTest, MultiplyLeft) {
+  SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(10);
+
+  EXPECT_TRUE(!stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
+  EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
+  EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
+
+  SamplesStatsCounter multiplied_stats = 10 * stats;
+  EXPECT_TRUE(!multiplied_stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(multiplied_stats.GetMin(), 10.0);
+  EXPECT_DOUBLE_EQ(multiplied_stats.GetMax(), 100.0);
+  EXPECT_DOUBLE_EQ(multiplied_stats.GetAverage(), 55.0);
+  EXPECT_EQ(multiplied_stats.GetSamples().size(), stats.GetSamples().size());
+
+  // Check that origin stats were not modified.
+  EXPECT_TRUE(!stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
+  EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
+  EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
+}
+
+TEST(SamplesStatsCounterTest, Divide) {
+  SamplesStatsCounter stats;
+  for (int i = 1; i <= 10; i++) {
+    stats.AddSample(i * 10);
+  }
+
+  EXPECT_TRUE(!stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(stats.GetMin(), 10.0);
+  EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
+  EXPECT_DOUBLE_EQ(stats.GetAverage(), 55.0);
+
+  SamplesStatsCounter divided_stats = stats / 10;
+  EXPECT_TRUE(!divided_stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(divided_stats.GetMin(), 1.0);
+  EXPECT_DOUBLE_EQ(divided_stats.GetMax(), 10.0);
+  EXPECT_DOUBLE_EQ(divided_stats.GetAverage(), 5.5);
+  EXPECT_EQ(divided_stats.GetSamples().size(), stats.GetSamples().size());
+
+  // Check that origin stats were not modified.
+  EXPECT_TRUE(!stats.IsEmpty());
+  EXPECT_DOUBLE_EQ(stats.GetMin(), 10.0);
+  EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
+  EXPECT_DOUBLE_EQ(stats.GetAverage(), 55.0);
+}
+
+INSTANTIATE_TEST_SUITE_P(SamplesStatsCounterTests,
+                         SamplesStatsCounterTest,
+                         ::testing::Range(0, SIZE_FOR_MERGE + 1));
+
+}  // namespace webrtc