content: /*
   * 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;
      }
  }
  