com/android/server/wifi/util/MetricsUtils.java

/*
 * Copyright (C) 2018 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.server.wifi.util;

import android.util.SparseIntArray;

/**
 * Utilities for Metrics collections.
 */
public class MetricsUtils {
    /**
     * A generic bucket containing a start, end, and count. The utility classes will convert to
     * such a generic bucket which can then be copied into the specific bucket of the proto.
     */
    public static class GenericBucket {
        public long start;
        public long end;
        public int count;
    }

    /**
     * Specifies a ~log histogram consisting of two levels of buckets - a set of N big buckets:
     *
     * Buckets starts at: B + P * M^i, where i=0, ... , N-1 (N big buckets)
     * Each big bucket is divided into S sub-buckets
     *
     * Each (big) bucket is M times bigger than the previous one.
     *
     * The buckets are then:
     * #0: B + P * M^0 with S buckets each of width (P*M^1-P*M^0)/S
     * #1: B + P * M^1 with S buckets each of width (P*M^2-P*M^1)/S
     * ...
     * #N-1: B + P * M^(N-1) with S buckets each of width (P*M^N-P*M^(N-1))/S
     */
    public static class LogHistParms {
        public LogHistParms(int b, int p, int m, int s, int n) {
            this.b = b;
            this.p = p;
            this.m = m;
            this.s = s;
            this.n = n;

            // derived values
            mLog = Math.log(m);
            bb = new double[n];
            sbw = new double[n];
            bb[0] = b + p;
            sbw[0] = p * (m - 1.0) / (double) s;
            for (int i = 1; i < n; ++i) {
                bb[i] = m * (bb[i - 1] - b) + b;
                sbw[i] = m * sbw[i - 1];
            }
        }

        // spec
        public int b;
        public int p;
        public int m;
        public int s;
        public int n;

        // derived
        public double mLog;
        public double[] bb; // bucket base
        public double[] sbw; // sub-bucket width
    }

    /**
     * Adds the input value to the log histogram based on the histogram parameters.
     */
    public static int addValueToLogHistogram(long x, SparseIntArray histogram, LogHistParms hp) {
        double logArg = (double) (x - hp.b) / (double) hp.p;
        int bigBucketIndex = -1;
        if (logArg > 0) {
            bigBucketIndex = (int) (Math.log(logArg) / hp.mLog);
        }
        int subBucketIndex;
        if (bigBucketIndex < 0) {
            bigBucketIndex = 0;
            subBucketIndex = 0;
        } else if (bigBucketIndex >= hp.n) {
            bigBucketIndex = hp.n - 1;
            subBucketIndex = hp.s - 1;
        } else {
            subBucketIndex = (int) ((x - hp.bb[bigBucketIndex]) / hp.sbw[bigBucketIndex]);
            if (subBucketIndex >= hp.s) { // probably a rounding error so move to next big bucket
                bigBucketIndex++;
                if (bigBucketIndex >= hp.n) {
                    bigBucketIndex = hp.n - 1;
                    subBucketIndex = hp.s - 1;
                } else {
                    subBucketIndex = (int) ((x - hp.bb[bigBucketIndex]) / hp.sbw[bigBucketIndex]);
                }
            }
        }
        int key = bigBucketIndex * hp.s + subBucketIndex;

        // note that get() returns 0 if index not there already
        int newValue = histogram.get(key) + 1;
        histogram.put(key, newValue);

        return newValue;
    }

    /**
     * Converts the log histogram (with the specified histogram parameters) to an array of generic
     * histogram buckets.
     */
    public static GenericBucket[] logHistogramToGenericBuckets(SparseIntArray histogram,
            LogHistParms hp) {
        GenericBucket[] protoArray = new GenericBucket[histogram.size()];
        for (int i = 0; i < histogram.size(); ++i) {
            int key = histogram.keyAt(i);

            protoArray[i] = new GenericBucket();
            protoArray[i].start = (long) (hp.bb[key / hp.s] + hp.sbw[key / hp.s] * (key % hp.s));
            protoArray[i].end = (long) (protoArray[i].start + hp.sbw[key / hp.s]);
            protoArray[i].count = histogram.valueAt(i);
        }

        return protoArray;
    }

    /**
     * Adds the input value to the histogram based on the lineaer histogram parameters.
     *
     * The 'int[] hp' contains a list of bucket limits. The number of buckets is hp.length() + 1
     * where buckets are:
     * - < hp[0]
     * - [hp[0], hp[1])
     * ...
     * - >= hp[hp.length() - 1]
     */
    public static int addValueToLinearHistogram(int x, SparseIntArray histogram, int[] hp) {
        int bucket = 0;
        for (int limit : hp) {
            if (x >= limit) {
                bucket++;
                continue;
            }
            break;
        }

        // note that get() returns 0 if index not there already
        int newValue = histogram.get(bucket) + 1;
        histogram.put(bucket, newValue);

        return newValue;
    }

    /**
     * Converts the histogram (with the specified linear histogram parameters) to an array of
     * generic histogram buckets.
     */
    public static GenericBucket[] linearHistogramToGenericBuckets(SparseIntArray histogram,
            int[] linearHistParams) {
        GenericBucket[] protoArray = new GenericBucket[histogram.size()];
        for (int i = 0; i < histogram.size(); ++i) {
            int bucket = histogram.keyAt(i);

            protoArray[i] = new GenericBucket();
            if (bucket == 0) {
                protoArray[i].start = Integer.MIN_VALUE;
                protoArray[i].end = linearHistParams[0];
            } else if (bucket != linearHistParams.length) {
                protoArray[i].start = linearHistParams[bucket - 1];
                protoArray[i].end = linearHistParams[bucket];
            } else {
                protoArray[i].start = linearHistParams[linearHistParams.length - 1];
                protoArray[i].end = Integer.MAX_VALUE;
            }
            protoArray[i].count = histogram.valueAt(i);
        }

        return protoArray;
    }
}