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
17package com.android.server.wifi.util;
18
19import android.util.SparseIntArray;
20
21/**
22 * Utilities for Metrics collections.
23 */
24public 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 {
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     */
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     */
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     */
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     */
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