1 /*
2 * Copyright 2023, The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef MEDIA_HISTOGRAM_H_
18 #define MEDIA_HISTOGRAM_H_
19
20 #include <limits>
21 #include <sstream>
22 #include <string>
23 #include <vector>
24
25 namespace android {
26
27 template<typename T>
28 class MediaHistogram {
29 public:
30 MediaHistogram();
31 void clear();
32 bool setup(size_t bucketCount, T width, T floor = 0);
33 bool setup(const std::vector<T> &bucketLimits);
34 void insert(T sample);
35 size_t size() const;
36 int64_t operator[](int) const;
getMin()37 T getMin() const { return mMin; }
getMax()38 T getMax() const { return mMax; }
getCount()39 T getCount() const { return mCount; }
getSum()40 T getSum() const { return mSum; }
getAvg()41 T getAvg() const { return mSum / (mCount == 0 ? 1 : mCount); }
42 T getPercentile(int) const;
43 std::string emit() const;
44 std::string emitBuckets() const;
45 private:
46 MediaHistogram(const MediaHistogram &); // disallow
47
48 void allocate(size_t bucketCount, bool withBucketLimits);
49
50 T mFloor, mCeiling, mWidth;
51 T mMin, mMax, mSum;
52 int64_t mBelow, mAbove, mCount;
53 std::vector<T> mBuckets;
54 std::vector<T> mBucketLimits;
55 };
56
57 template<typename T>
MediaHistogram()58 MediaHistogram<T>::MediaHistogram() {
59 mWidth = mCeiling = mFloor = -1;
60 clear();
61 }
62
63 template<typename T>
clear()64 void MediaHistogram<T>::clear() {
65 for (int i = 0; i < mBuckets.size(); ++i) {
66 mBuckets[i] = 0;
67 }
68 mMin = std::numeric_limits<T>::max();
69 mMax = std::numeric_limits<T>::min();
70 mSum = 0;
71 mCount = 0;
72 mBelow = mAbove = 0;
73 }
74
75 template<typename T>
setup(size_t bucketCount,T width,T floor)76 bool MediaHistogram<T>::setup(size_t bucketCount, T width, T floor) {
77 if (bucketCount <= 0 || width <= 0) {
78 return false;
79 }
80 allocate(bucketCount, false);
81
82 mWidth = width;
83 mFloor = floor;
84 mCeiling = floor + bucketCount * width;
85 clear();
86 return true;
87 }
88
89 template<typename T>
setup(const std::vector<T> & bucketLimits)90 bool MediaHistogram<T>::setup(const std::vector<T> &bucketLimits) {
91 if (bucketLimits.size() <= 1) {
92 return false;
93 }
94 // The floor is the first bucket limit value, so offset by 1
95 size_t bucketCount = bucketLimits.size() - 1;
96 allocate(bucketCount, true);
97
98 mWidth = -1;
99 mFloor = bucketLimits[0];
100 for (size_t i = 0; i < bucketCount; ++i) {
101 // The floor is the first bucket, so offset by 1
102 mBucketLimits[i] = bucketLimits[i + 1];
103 }
104 mCeiling = bucketLimits[bucketCount];
105 clear();
106 return true;
107 }
108
109 template<typename T>
allocate(size_t bucketCount,bool withBucketLimits)110 void MediaHistogram<T>::allocate(size_t bucketCount, bool withBucketLimits) {
111 assert(bucketCount > 0);
112 if (bucketCount != mBuckets.size()) {
113 mBuckets = std::vector<T>(bucketCount, 0);
114 }
115 if (withBucketLimits && mBucketLimits.size() != bucketCount) {
116 mBucketLimits = std::vector<T>(bucketCount, 0);
117 }
118 }
119
120 template<typename T>
insert(T sample)121 void MediaHistogram<T>::insert(T sample) {
122 // histogram is not set up
123 if (mBuckets.size() == 0) {
124 return;
125 }
126
127 mCount++;
128 mSum += sample;
129 mMin = std::min(mMin, sample);
130 mMax = std::max(mMax, sample);
131
132 if (sample < mFloor) {
133 mBelow++;
134 } else if (sample >= mCeiling) {
135 mAbove++;
136 } else if (mWidth == -1) {
137 // A binary search might be more efficient for large number of buckets, but it is expected
138 // that there will never be a large amount of buckets, so keep the code simple.
139 for (size_t slot = 0; slot < mBucketLimits.size(); ++slot) {
140 if (sample < mBucketLimits[slot]) {
141 mBuckets[slot]++;
142 break;
143 }
144 }
145 } else {
146 int64_t slot = (sample - mFloor) / mWidth;
147 assert(slot < mBuckets.size());
148 mBuckets[slot]++;
149 }
150 return;
151 }
152
153 template<typename T>
size()154 size_t MediaHistogram<T>::size() const {
155 return mBuckets.size() + 1;
156 }
157
158 template<typename T>
159 int64_t MediaHistogram<T>::operator[](int i) const {
160 assert(i >= 0);
161 assert(i <= mBuckets.size());
162 if (i == mBuckets.size()) {
163 return mAbove;
164 }
165 return mBuckets[i];
166 }
167
168 template<typename T>
emit()169 std::string MediaHistogram<T>::emit() const {
170 // emits: floor,width,below{bucket0,bucket1,...., bucketN}above
171 // or.. emits: below{bucket0,bucket1,...., bucketN}above
172 // unconfigured will emit: 0{}0
173 // XXX: is this best representation?
174 std::stringstream ss("");
175 if (mWidth == -1) {
176 ss << mBelow << "{";
177 } else {
178 ss << mFloor << "," << mWidth << "," << mBelow << "{";
179 }
180 for (size_t i = 0; i < mBuckets.size(); i++) {
181 if (i != 0) {
182 ss << ",";
183 }
184 ss << mBuckets[i];
185 }
186 ss << "}" << mAbove;
187 return ss.str();
188 }
189
190 template<typename T>
emitBuckets()191 std::string MediaHistogram<T>::emitBuckets() const {
192 std::stringstream ss("");
193 if (mWidth == -1) {
194 ss << mFloor;
195 for (size_t i = 0; i < mBucketLimits.size(); ++i) {
196 ss << ',' << mBucketLimits[i];
197 }
198 } else {
199 ss << mFloor;
200 for (size_t i = 1; i <= mBuckets.size(); ++i) {
201 ss << ',' << (mFloor + i * mWidth);
202 }
203 }
204 return ss.str();
205 }
206
207 } // android
208
209 #endif // MEDIA_HISTOGRAM_H_