1 /*
2  *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
3  *
4  *  Use of this source code is governed by a BSD-style license
5  *  that can be found in the LICENSE file in the root of the source
6  *  tree. An additional intellectual property rights grant can be found
7  *  in the file PATENTS.  All contributing project authors may
8  *  be found in the AUTHORS file in the root of the source tree.
9  */
10 
11 #include "modules/video_coding/histogram.h"
12 
13 #include <algorithm>
14 
15 #include "rtc_base/checks.h"
16 
17 namespace webrtc {
18 namespace video_coding {
Histogram(size_t num_buckets,size_t max_num_values)19 Histogram::Histogram(size_t num_buckets, size_t max_num_values) {
20   RTC_DCHECK_GT(num_buckets, 0);
21   RTC_DCHECK_GT(max_num_values, 0);
22   buckets_.resize(num_buckets);
23   values_.reserve(max_num_values);
24   index_ = 0;
25 }
26 
Add(size_t value)27 void Histogram::Add(size_t value) {
28   value = std::min<size_t>(value, buckets_.size() - 1);
29   if (index_ < values_.size()) {
30     --buckets_[values_[index_]];
31     RTC_DCHECK_LT(values_[index_], buckets_.size());
32     values_[index_] = value;
33   } else {
34     values_.emplace_back(value);
35   }
36 
37   ++buckets_[value];
38   index_ = (index_ + 1) % values_.capacity();
39 }
40 
InverseCdf(float probability) const41 size_t Histogram::InverseCdf(float probability) const {
42   RTC_DCHECK_GE(probability, 0.f);
43   RTC_DCHECK_LE(probability, 1.f);
44   RTC_DCHECK_GT(values_.size(), 0ul);
45 
46   size_t bucket = 0;
47   float accumulated_probability = 0;
48   while (accumulated_probability < probability && bucket < buckets_.size()) {
49     accumulated_probability +=
50         static_cast<float>(buckets_[bucket]) / values_.size();
51     ++bucket;
52   }
53   return bucket;
54 }
55 
NumValues() const56 size_t Histogram::NumValues() const {
57   return values_.size();
58 }
59 
60 }  // namespace video_coding
61 }  // namespace webrtc
62