1 /*
2  * Copyright (C) 2018 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 package com.android.server.wifi.util;
18 
19 import android.util.SparseIntArray;
20 
21 /**
22  * Utilities for Metrics collections.
23  */
24 public class MetricsUtils {
25     /**
26      * A generic bucket containing a start, end, and count. The utility classes will convert to
27      * such a generic bucket which can then be copied into the specific bucket of the proto.
28      */
29     public static class GenericBucket {
30         public long start;
31         public long end;
32         public int count;
33     }
34 
35     /**
36      * Specifies a ~log histogram consisting of two levels of buckets - a set of N big buckets:
37      *
38      * Buckets starts at: B + P * M^i, where i=0, ... , N-1 (N big buckets)
39      * Each big bucket is divided into S sub-buckets
40      *
41      * Each (big) bucket is M times bigger than the previous one.
42      *
43      * The buckets are then:
44      * #0: B + P * M^0 with S buckets each of width (P*M^1-P*M^0)/S
45      * #1: B + P * M^1 with S buckets each of width (P*M^2-P*M^1)/S
46      * ...
47      * #N-1: B + P * M^(N-1) with S buckets each of width (P*M^N-P*M^(N-1))/S
48      */
49     public static class LogHistParms {
LogHistParms(int b, int p, int m, int s, int n)50         public LogHistParms(int b, int p, int m, int s, int n) {
51             this.b = b;
52             this.p = p;
53             this.m = m;
54             this.s = s;
55             this.n = n;
56 
57             // derived values
58             mLog = Math.log(m);
59             bb = new double[n];
60             sbw = new double[n];
61             bb[0] = b + p;
62             sbw[0] = p * (m - 1.0) / (double) s;
63             for (int i = 1; i < n; ++i) {
64                 bb[i] = m * (bb[i - 1] - b) + b;
65                 sbw[i] = m * sbw[i - 1];
66             }
67         }
68 
69         // spec
70         public int b;
71         public int p;
72         public int m;
73         public int s;
74         public int n;
75 
76         // derived
77         public double mLog;
78         public double[] bb; // bucket base
79         public double[] sbw; // sub-bucket width
80     }
81 
82     /**
83      * Adds the input value to the log histogram based on the histogram parameters.
84      */
addValueToLogHistogram(long x, SparseIntArray histogram, LogHistParms hp)85     public static int addValueToLogHistogram(long x, SparseIntArray histogram, LogHistParms hp) {
86         double logArg = (double) (x - hp.b) / (double) hp.p;
87         int bigBucketIndex = -1;
88         if (logArg > 0) {
89             bigBucketIndex = (int) (Math.log(logArg) / hp.mLog);
90         }
91         int subBucketIndex;
92         if (bigBucketIndex < 0) {
93             bigBucketIndex = 0;
94             subBucketIndex = 0;
95         } else if (bigBucketIndex >= hp.n) {
96             bigBucketIndex = hp.n - 1;
97             subBucketIndex = hp.s - 1;
98         } else {
99             subBucketIndex = (int) ((x - hp.bb[bigBucketIndex]) / hp.sbw[bigBucketIndex]);
100             if (subBucketIndex >= hp.s) { // probably a rounding error so move to next big bucket
101                 bigBucketIndex++;
102                 if (bigBucketIndex >= hp.n) {
103                     bigBucketIndex = hp.n - 1;
104                     subBucketIndex = hp.s - 1;
105                 } else {
106                     subBucketIndex = (int) ((x - hp.bb[bigBucketIndex]) / hp.sbw[bigBucketIndex]);
107                 }
108             }
109         }
110         int key = bigBucketIndex * hp.s + subBucketIndex;
111 
112         // note that get() returns 0 if index not there already
113         int newValue = histogram.get(key) + 1;
114         histogram.put(key, newValue);
115 
116         return newValue;
117     }
118 
119     /**
120      * Converts the log histogram (with the specified histogram parameters) to an array of generic
121      * histogram buckets.
122      */
logHistogramToGenericBuckets(SparseIntArray histogram, LogHistParms hp)123     public static GenericBucket[] logHistogramToGenericBuckets(SparseIntArray histogram,
124             LogHistParms hp) {
125         GenericBucket[] protoArray = new GenericBucket[histogram.size()];
126         for (int i = 0; i < histogram.size(); ++i) {
127             int key = histogram.keyAt(i);
128 
129             protoArray[i] = new GenericBucket();
130             protoArray[i].start = (long) (hp.bb[key / hp.s] + hp.sbw[key / hp.s] * (key % hp.s));
131             protoArray[i].end = (long) (protoArray[i].start + hp.sbw[key / hp.s]);
132             protoArray[i].count = histogram.valueAt(i);
133         }
134 
135         return protoArray;
136     }
137 
138     /**
139      * Adds the input value to the histogram based on the lineaer histogram parameters.
140      *
141      * The 'int[] hp' contains a list of bucket limits. The number of buckets is hp.length() + 1
142      * where buckets are:
143      * - < hp[0]
144      * - [hp[0], hp[1])
145      * ...
146      * - >= hp[hp.length() - 1]
147      */
addValueToLinearHistogram(int x, SparseIntArray histogram, int[] hp)148     public static int addValueToLinearHistogram(int x, SparseIntArray histogram, int[] hp) {
149         int bucket = 0;
150         for (int limit : hp) {
151             if (x >= limit) {
152                 bucket++;
153                 continue;
154             }
155             break;
156         }
157 
158         // note that get() returns 0 if index not there already
159         int newValue = histogram.get(bucket) + 1;
160         histogram.put(bucket, newValue);
161 
162         return newValue;
163     }
164 
165     /**
166      * Converts the histogram (with the specified linear histogram parameters) to an array of
167      * generic histogram buckets.
168      */
linearHistogramToGenericBuckets(SparseIntArray histogram, int[] linearHistParams)169     public static GenericBucket[] linearHistogramToGenericBuckets(SparseIntArray histogram,
170             int[] linearHistParams) {
171         GenericBucket[] protoArray = new GenericBucket[histogram.size()];
172         for (int i = 0; i < histogram.size(); ++i) {
173             int bucket = histogram.keyAt(i);
174 
175             protoArray[i] = new GenericBucket();
176             if (bucket == 0) {
177                 protoArray[i].start = Integer.MIN_VALUE;
178                 protoArray[i].end = linearHistParams[0];
179             } else if (bucket != linearHistParams.length) {
180                 protoArray[i].start = linearHistParams[bucket - 1];
181                 protoArray[i].end = linearHistParams[bucket];
182             } else {
183                 protoArray[i].start = linearHistParams[linearHistParams.length - 1];
184                 protoArray[i].end = Integer.MAX_VALUE;
185             }
186             protoArray[i].count = histogram.valueAt(i);
187         }
188 
189         return protoArray;
190     }
191 }
192