// Copyright 2018 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "ui/latency/histograms.h"

#include <cmath>
#include <limits>

#include "base/bits.h"
#include "base/time/time.h"
#include "ui/latency/fixed_point.h"

namespace {

// Calculates percentiles in a way that can be shared by different histograms.
ui::PercentileResults PercentilesHelper(
    ui::frame_metrics::BoundaryIterator* boundary_iterator,
    const uint32_t* buckets_begin,
    const uint32_t* buckets_end,
    uint64_t total_samples) {
  ui::PercentileResults result;
  uint64_t boundary_left = 0;
  uint64_t boundary_right = boundary_iterator->Next();

  double thresholds[ui::PercentileResults::kCount];
  for (size_t i = 0; i < ui::PercentileResults::kCount; i++) {
    thresholds[i] = ui::PercentileResults::kPercentiles[i] * total_samples;
  }

  uint64_t accumulator = 0;
  size_t result_index = 0;
  for (const uint32_t* bucket = buckets_begin; bucket < buckets_end; bucket++) {
    accumulator += *bucket;
    // Multiple percentiles might be calculated from the same bucket,
    // so we use a while loop here.
    while (accumulator > thresholds[result_index]) {
      const double overage = accumulator - thresholds[result_index];
      double b0_fraction = overage / (*bucket);
      double b1_fraction = 1.0 - b0_fraction;

      // Use a linear interpolation between two buckets.
      // This assumes the samples are evenly distributed within a bucket.
      // TODO(brianderson): Consider neighboring bucket sizes and fit to a
      //   curve. http://crbug.com/821879
      const double estimate =
          b0_fraction * boundary_left + b1_fraction * boundary_right;
      result.values[result_index] = estimate;
      result_index++;
      if (result_index >= ui::PercentileResults::kCount)
        return result;
    }

    boundary_left = boundary_right;
    boundary_right = boundary_iterator->Next();
  }

  return result;
}

}  // namespace

namespace ui {

constexpr double PercentileResults::kPercentiles[];
constexpr size_t PercentileResults::kCount;

namespace frame_metrics {

constexpr size_t RatioHistogram::kBucketCount;
constexpr size_t VSyncHistogram::kBucketCount;

// Ratio Histogram.
// The distribution of each category of buckets in this historam is
// exponential, however each category is divided into N linear buckets
// depending on how much precision we want for that category. How much
// precision a category gets depends on how often we expect that bucket to be
// used and how important those buckets are.
//
// Most of the precision is allocated for values just > 1 since most ratios,
// when not ~0 will be > 1. And since ratios are likely to be near whole
// numbers (some multiple of the vsync), we only give it a precision of 1/2.
// You can think about the stride of each category as the number of vsyncs of
// precision that category will have.
//
// There will be aliasing, but because of the vsync aligned linear division
// of each category, we won't get a bucket that represents fewer vsyncs than
// its fprevious bucket.
//
// This is in contrast to the default exponential distribution of UMA
// buckets, which result in a constant precision for each bucket and would
// allocate lots of very small buckets near 0 where we don't need the
// precision.

namespace {

constexpr size_t kBucketHalfStrideFirstBucketIndex = 17;

// Within the range [16, 4096), there are 9 categories of buckets that each
// start with a power of 2. Within a category, successive buckets have a fixed
// stride. Across categories, the strides increase exponentionally, encoded
// as powers of 2 in |stride_shift|, which increases linearly.
struct RatioBucketCategory {
  uint8_t first_bucket_index;
  uint8_t stride_shift;
};
using RatioCategoryHelper = std::array<RatioBucketCategory, 9>;
constexpr RatioCategoryHelper kCategories16to4096 = {
    // first_bucket_index of each row below is the previous one + number of
    // buckets. Each entry is {first_bucket_index, stride_shift}.
    {{47, 0},      // [16, 32) stride 1 => 16 buckets.
     {63, 1},      // [32, 64) stride 2 => 16 buckets.
     {79, 3},      // [64, 128) stride 8 => 8 buckets.
     {87, 4},      // [128, 256) stride 16 => 8 buckets.
     {95, 6},      // [256, 512) stride 64 => 4 buckets
     {99, 7},      // [512, 1024) stride 128 => 4 buckets.
     {103, 9},     // [1024, 2048) stride 512 => 2 buckets.
     {105, 10},    // [2048, 4096) stride 1024 => 2 buckets.
     {107, 12}}};  // [4096, 8192) stride 4096 => 1 bucket.

// The delegate RatioBoundary::Percentiles will pass to PercentilesHelper.
struct RatioBoundaryIterator : public BoundaryIterator {
  ~RatioBoundaryIterator() override = default;

  size_t bucket = 0;
  uint64_t boundary = 0;
  RatioCategoryHelper::const_iterator b16to4096 = kCategories16to4096.begin();
  uint64_t next_boundary_to_change_category =
      32 * frame_metrics::kFixedPointMultiplier;

  uint64_t Next() override {
    if (bucket == 0) {
      // The first bucket is [0, 1).
      boundary = 1;
    } else if (bucket < kBucketHalfStrideFirstBucketIndex ||
               bucket >= kCategories16to4096.back().first_bucket_index) {
      // The start and end buckets increase in size by powers of 2.
      boundary *= 2;
    } else if (bucket < kCategories16to4096.front().first_bucket_index) {
      // The 30 buckets before 47 have a stride of .5 and represent the
      // range [1, 16).
      boundary += (frame_metrics::kFixedPointMultiplier / 2);
    } else {
      // The rest of the buckets are defined by kCategories16to4096.
      DCHECK(b16to4096 < kCategories16to4096.end());
      boundary +=
          (frame_metrics::kFixedPointMultiplier << b16to4096->stride_shift);
      // The category changes for every power of 2.
      if (boundary >= next_boundary_to_change_category) {
        next_boundary_to_change_category *= 2;
        b16to4096++;
      }
    }

    bucket++;
    return boundary;
  }
};

}  // namespace

std::unique_ptr<BoundaryIterator> CreateRatioIteratorForTesting() {
  return std::make_unique<RatioBoundaryIterator>();
}

RatioHistogram::RatioHistogram() = default;
RatioHistogram::~RatioHistogram() = default;

void RatioHistogram::AddSample(uint32_t ratio, uint32_t weight) {
  size_t bucket = 0;

  // Precomputed thresholds for the log base 2 of the ratio that help
  // determine which category of buckets the sample should go in.
  constexpr int kLog2HalfStrideStart = kFixedPointShift;
  constexpr int kLog2Cats16to4096Start = kFixedPointShift + 4;  // 2^4 = 16.
  constexpr int kLog2_4096Pow2Start = kFixedPointShift + 12;    // 2^12 = 4096.

  if (ratio == 0) {
    bucket = 0;
  } else {
    int log2 = base::bits::Log2Floor(ratio);
    DCHECK_GE(log2, 0);
    if (log2 < kLog2HalfStrideStart) {
      // [2^-16, 1) pow of 2 strides => 16 buckets. (16x1)
      bucket = 1 + log2;
    } else if (log2 < kLog2Cats16to4096Start) {
      // [1, 16) stride 1/2 => 30 buckets. (2 + 4 + 8 + 16)
      const int first_bucket_index = kBucketHalfStrideFirstBucketIndex;
      const int category_start = kFixedPointMultiplier;
      const int total_shift = kFixedPointShift - 1;  // -1 multiplies by 2.
      const int category_offset = (ratio - category_start) >> total_shift;
      bucket = first_bucket_index + category_offset;
    } else if (log2 < kLog2_4096Pow2Start) {
      // [16, 32) stride 1 => 16 buckets.
      // [32, 64) stride 2 => 16 buckets.
      // [64, 128) stride 8 => 8 buckets.
      // [128, 256) stride 16 => 8 buckets.
      // [256, 512) stride 64 => 4 buckets.
      // [512, 1024) stride 128 => 4 buckets.
      // [1024, 2048) stride 512 => 2 buckets.
      // [2048, 4096) stride 1024 => 2 buckets.
      const int category = log2 - kLog2Cats16to4096Start;
      const int category_start = 1 << log2;
      const int total_shift =
          (kFixedPointShift + kCategories16to4096[category].stride_shift);
      const int category_offset = (ratio - category_start) >> total_shift;
      bucket =
          kCategories16to4096[category].first_bucket_index + category_offset;
    } else {
      // [4096, 2^16) pow of 2 strides => 4 buckets. (4x1)
      const int category_offset = log2 - kLog2_4096Pow2Start;
      bucket = kCategories16to4096.back().first_bucket_index + category_offset;
    }
  }
  DCHECK_LT(bucket, kBucketCount);

  // Verify overflow isn't an issue.
  DCHECK_LT(weight, std::numeric_limits<BucketArray::value_type>::max() -
                        buckets_[bucket]);
  DCHECK_LT(weight, std::numeric_limits<decltype(total_samples_)>::max() -
                        total_samples_);

  buckets_[bucket] += weight;
  total_samples_ += weight;
}

PercentileResults RatioHistogram::ComputePercentiles() const {
  RatioBoundaryIterator i;
  return PercentilesHelper(&i, buckets_.data(),
                           buckets_.data() + buckets_.size(), total_samples_);
}

void RatioHistogram::Reset() {
  total_samples_ = 0;
  buckets_.fill(0);
}

// VSyncHistogram.
namespace {

// The number of buckets in bucket categories 1 through 6.
constexpr std::array<uint8_t, 6> kVSyncBucketCounts = {{12, 16, 16, 16, 31, 6}};

// Some constants used to convert values to bucket categories.
constexpr size_t kVSync1stBucketC0 = 0;
constexpr size_t kVSync1stBucketC1 = kVSync1stBucketC0 + 1;
constexpr size_t kVSync1stBucketC2 = kVSync1stBucketC1 + kVSyncBucketCounts[0];
constexpr size_t kVSync1stBucketC3 = kVSync1stBucketC2 + kVSyncBucketCounts[1];
constexpr size_t kVSync1stBucketC4 = kVSync1stBucketC3 + kVSyncBucketCounts[2];
constexpr size_t kVSync1stBucketC5 = kVSync1stBucketC4 + kVSyncBucketCounts[3];
constexpr size_t kVSync1stBucketC6 = kVSync1stBucketC5 + kVSyncBucketCounts[4];
constexpr size_t kVSyncBucketCountC6 = kVSyncBucketCounts[5];

// This iterates through the microsecond VSync boundaries.
struct VSyncBoundaryIterator : public BoundaryIterator {
  ~VSyncBoundaryIterator() override = default;

  uint8_t category_ = 0;
  uint8_t sub_bucket_ = 0;

  uint64_t Next() override {
    uint32_t boundary = 0;
    switch (category_) {
      case 0:  // Powers of two from 1 to 2048 us @ 50% precision
        boundary = 1 << sub_bucket_;
        break;
      case 1:    // Every 8 Hz from 256 Hz to 128 Hz @ 3-6% precision
      case 2:    // Every 4 Hz from 128 Hz to  64 Hz @ 3-6% precision
      case 3:    // Every 2 Hz from  64 Hz to  32 Hz @ 3-6% precision
      case 4: {  // Every 1 Hz from  32 Hz to   1 Hz @ 3-33% precision
        int hz_start = 256 >> (category_ - 1);
        int hz_stride = 8 >> (category_ - 1);
        int hz = hz_start - hz_stride * sub_bucket_;
        boundary = (base::TimeTicks::kMicrosecondsPerSecond + (hz / 2)) / hz;
        break;
      }
      case 5:  // Powers of two from 1s to 32s @ 50% precision
        boundary =
            static_cast<uint32_t>(base::TimeTicks::kMicrosecondsPerSecond) *
            (1 << sub_bucket_);
        break;
      case 6:  // The last boundary of 64s.
        // Advancing would result in out-of-bounds access of
        // kVSyncBucketCounts, so just return.
        return 64 * base::TimeTicks::kMicrosecondsPerSecond;
      default:
        NOTREACHED();
    }

    if (++sub_bucket_ >= kVSyncBucketCounts[category_]) {
      category_++;
      sub_bucket_ = 0;
    }

    return boundary;
  }
};

}  // namespace

std::unique_ptr<BoundaryIterator> CreateVSyncIteratorForTesting() {
  return std::make_unique<VSyncBoundaryIterator>();
}

VSyncHistogram::VSyncHistogram() = default;
VSyncHistogram::~VSyncHistogram() = default;

// Optimized to minimize the number of memory accesses.
void VSyncHistogram::AddSample(uint32_t microseconds, uint32_t weight) {
  size_t bucket = 0;

  static constexpr int k256HzPeriodInMicroseconds =
      base::TimeTicks::kMicrosecondsPerSecond / 256;

  if (microseconds == 0) {
    // bucket = 0;
  } else if (microseconds < k256HzPeriodInMicroseconds) {
    // Powers of two from 1 to 2048 us @ 50% precision
    bucket = kVSync1stBucketC1 + base::bits::Log2Floor(microseconds);
  } else if (microseconds < base::TimeTicks::kMicrosecondsPerSecond) {
    // [256Hz, 1Hz)
    int hz = base::TimeTicks::kMicrosecondsPerSecond / (microseconds + 0.5);
    DCHECK_LT(hz, 256);
    switch (hz / 32) {
      // Every 1 Hz from 32 Hz to 1 Hz @ 3-33% precision
      case 0:
        bucket = kVSync1stBucketC6 - hz;
        break;
      // Every 2 Hz from 64 Hz to 32 Hz @ 3-6% precision
      case 1:
        bucket = kVSync1stBucketC5 - ((hz - 30) / 2);
        break;
      // Every 4 Hz from 128 Hz to 64 Hz @ 3-6% precision
      case 2:
      case 3:
        bucket = kVSync1stBucketC4 - ((hz - 60) / 4);
        break;
      // Every 8 Hz from 256 Hz to 128 Hz @ 3-6% precision
      case 4:
      case 5:
      case 6:
      case 7:
        bucket = kVSync1stBucketC3 - ((hz - 120) / 8);
        break;
      default:
        NOTREACHED();
        return;
    }
  } else {
    // Powers of two from 1s to 32s @ 50% precision
    int seconds_log2 = base::bits::Log2Floor(
        microseconds / base::TimeTicks::kMicrosecondsPerSecond);
    DCHECK_GE(seconds_log2, 0);
    size_t offset = std::min<size_t>(kVSyncBucketCountC6 - 1, seconds_log2);
    bucket = kVSync1stBucketC6 + offset;
  }

  DCHECK_GE(bucket, 0u);
  DCHECK_LT(bucket, kVSync1stBucketC6 + kVSyncBucketCountC6);
  DCHECK_LT(bucket, kBucketCount);

  // Verify overflow isn't an issue.
  DCHECK_LT(weight, std::numeric_limits<BucketArray::value_type>::max() -
                        buckets_[bucket]);
  DCHECK_LT(weight, std::numeric_limits<decltype(total_samples_)>::max() -
                        total_samples_);

  buckets_[bucket] += weight;
  total_samples_ += weight;
}

PercentileResults VSyncHistogram::ComputePercentiles() const {
  VSyncBoundaryIterator i;
  return PercentilesHelper(&i, buckets_.data(),
                           buckets_.data() + buckets_.size(), total_samples_);
}

void VSyncHistogram::Reset() {
  total_samples_ = 0;
  buckets_.fill(0);
}

}  // namespace frame_metrics
}  // namespace ui