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(int bucketCount, T width, T floor = 0);
33 bool setup(const std::vector<T> &bucketLimits);
34 void insert(T sample);
35 size_t size();
36 int64_t operator[](int);
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 bool allocate(int 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(int bucketCount,T width,T floor)76 bool MediaHistogram<T>::setup(int bucketCount, T width, T floor) {
77 if (bucketCount <= 0 || width <= 0) {
78 return false;
79 }
80 if (!allocate(bucketCount, false)) {
81 return false;
82 }
83 mWidth = width;
84 mFloor = floor;
85 mCeiling = floor + bucketCount * width;
86 clear();
87 return true;
88 }
89
90 template<typename T>
setup(const std::vector<T> & bucketLimits)91 bool MediaHistogram<T>::setup(const std::vector<T> &bucketLimits) {
92 if (bucketLimits.size() <= 1) {
93 return false;
94 }
95 int bucketCount = bucketLimits.size() - 1;
96 if (!allocate(bucketCount, true)) {
97 return false;
98 }
99
100 mWidth = -1;
101 mFloor = bucketLimits[0];
102 for (int i = 0; i < bucketCount; ++i) {
103 mBucketLimits[i] = bucketLimits[i + 1];
104 }
105 mCeiling = bucketLimits[bucketCount];
106 clear();
107 return true;
108 }
109
110 template<typename T>
allocate(int bucketCount,bool withBucketLimits)111 bool MediaHistogram<T>::allocate(int bucketCount, bool withBucketLimits) {
112 assert(bucketCount > 0);
113 if (bucketCount != mBuckets.size()) {
114 mBuckets = std::vector<T>(bucketCount, 0);
115 }
116 if (withBucketLimits && mBucketLimits.size() != bucketCount) {
117 mBucketLimits = std::vector<T>(bucketCount, 0);
118 }
119 return true;
120 }
121
122 template<typename T>
insert(T sample)123 void MediaHistogram<T>::insert(T sample) {
124 // histogram is not set up
125 if (mBuckets.size() == 0) {
126 return;
127 }
128
129 mCount++;
130 mSum += sample;
131 if (mMin > sample) mMin = sample;
132 if (mMax < sample) mMax = sample;
133
134 if (sample < mFloor) {
135 mBelow++;
136 } else if (sample >= mCeiling) {
137 mAbove++;
138 } else if (mWidth == -1) {
139 // A binary search might be more efficient for large number of buckets, but it is expected
140 // that there will never be a large amount of buckets, so keep the code simple.
141 for (int slot = 0; slot < mBucketLimits.size(); ++slot) {
142 if (sample < mBucketLimits[slot]) {
143 mBuckets[slot]++;
144 break;
145 }
146 }
147 } else {
148 int64_t slot = (sample - mFloor) / mWidth;
149 assert(slot < mBuckets.size());
150 mBuckets[slot]++;
151 }
152 return;
153 }
154
155 template<typename T>
size()156 size_t MediaHistogram<T>::size() {
157 return mBuckets.size() + 1;
158 }
159
160 template<typename T>
161 int64_t MediaHistogram<T>::operator[](int i) {
162 assert(i >= 0);
163 assert(i <= mBuckets.size());
164 if (i == mBuckets.size()) {
165 return mAbove;
166 }
167 return mBuckets[i];
168 }
169
170 template<typename T>
emit()171 std::string MediaHistogram<T>::emit() const {
172 // emits: floor,width,below{bucket0,bucket1,...., bucketN}above
173 // or.. emits: below{bucket0,bucket1,...., bucketN}above
174 // unconfigured will emit: 0{}0
175 // XXX: is this best representation?
176 std::stringstream ss("");
177 if (mWidth == -1) {
178 ss << mBelow << "{";
179 } else {
180 ss << mFloor << "," << mWidth << "," << mBelow << "{";
181 }
182 for (int i = 0; i < mBuckets.size(); i++) {
183 if (i != 0) {
184 ss << ",";
185 }
186 ss << mBuckets[i];
187 }
188 ss << "}" << mAbove;
189 return ss.str();
190 }
191
192 template<typename T>
emitBuckets()193 std::string MediaHistogram<T>::emitBuckets() const {
194 std::stringstream ss("");
195 if (mWidth == -1) {
196 ss << mFloor;
197 for (int i = 0; i < mBucketLimits.size(); ++i) {
198 ss << ',' << mBucketLimits[i];
199 }
200 } else {
201 ss << mFloor;
202 for (int i = 1; i <= mBuckets.size(); ++i) {
203 ss << ',' << (mFloor + i * mWidth);
204 }
205 }
206 return ss.str();
207 }
208
209 } // android
210
211 #endif // MEDIA_HISTOGRAM_H_