// Copyright 2020 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 "cast/streaming/bandwidth_estimator.h"

#include <chrono>
#include <limits>
#include <random>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "platform/api/time.h"
#include "util/chrono_helpers.h"

namespace openscreen {
namespace cast {
namespace {

using openscreen::operator<<;  // For std::chrono::duration gtest pretty-print.

// BandwidthEstimator configuration common to all tests.
constexpr int kMaxPacketsPerTimeslice = 10;
constexpr Clock::duration kTimesliceDuration = milliseconds(10);
constexpr int kTimeslicesPerSecond = seconds(1) / kTimesliceDuration;

// Use a fake, fixed start time.
constexpr Clock::time_point kStartTime =
    Clock::time_point() + Clock::duration(1234567890);

// Range of "fuzz" to add to timestamps in BandwidthEstimatorTest::AddFuzz().
constexpr Clock::duration kMaxFuzzOffset = milliseconds(15);
constexpr int kFuzzLowerBoundClockTicks = (-kMaxFuzzOffset).count();
constexpr int kFuzzUpperBoundClockTicks = kMaxFuzzOffset.count();

class BandwidthEstimatorTest : public testing::Test {
 public:
  BandwidthEstimatorTest()
      : estimator_(kMaxPacketsPerTimeslice, kTimesliceDuration, kStartTime) {}

  BandwidthEstimator* estimator() { return &estimator_; }

  // Returns |t| plus or minus |kMaxFuzzOffset|.
  Clock::time_point AddFuzz(Clock::time_point t) {
    return t + Clock::duration(distribution_(rand_));
  }

 private:
  BandwidthEstimator estimator_;

  // These are used to generate random values for AddFuzz().
  static constexpr std::minstd_rand::result_type kRandSeed =
      kStartTime.time_since_epoch().count();
  std::minstd_rand rand_{kRandSeed};
  std::uniform_int_distribution<int> distribution_{kFuzzLowerBoundClockTicks,
                                                   kFuzzUpperBoundClockTicks};
};

// Tests that, without any data, there won't be any estimates.
TEST_F(BandwidthEstimatorTest, DoesNotEstimateWithoutAnyInput) {
  EXPECT_EQ(0, estimator()->ComputeNetworkBandwidth());
}

// Tests the case where packets are being sent, but the Receiver hasn't provided
// feedback (e.g., due to a network blackout).
TEST_F(BandwidthEstimatorTest, DoesNotEstimateWithoutFeedback) {
  Clock::time_point now = kStartTime;
  for (int i = 0; i < 3; ++i) {
    const Clock::time_point end = now + estimator()->history_window();
    for (; now < end; now += kTimesliceDuration) {
      estimator()->OnBurstComplete(i, now);
      EXPECT_EQ(0, estimator()->ComputeNetworkBandwidth());
    }
    now = end;
  }
}

// Tests the case where packets are being sent, and a connection to the Receiver
// has been confirmed (because RTCP packets are coming in), but the Receiver has
// not successfully received anything.
TEST_F(BandwidthEstimatorTest, DoesNotEstimateIfNothingSuccessfullyReceived) {
  const Clock::duration kRoundTripTime = milliseconds(1);

  Clock::time_point now = kStartTime;
  for (int i = 0; i < 3; ++i) {
    const Clock::time_point end = now + estimator()->history_window();
    for (; now < end; now += kTimesliceDuration) {
      estimator()->OnBurstComplete(i, now);
      estimator()->OnRtcpReceived(now + kRoundTripTime, kRoundTripTime);
      EXPECT_EQ(0, estimator()->ComputeNetworkBandwidth());
    }
    now = end;
  }
}

// Tests that, when the Receiver successfully receives the payload bytes at a
// fixed rate, the network bandwidth estimates are based on the amount of time
// the Sender spent transmitting.
TEST_F(BandwidthEstimatorTest, EstimatesAtVariousBurstSaturations) {
  // These determine how many packets to burst in the simulation below.
  constexpr int kDivisors[] = {
      1,  // Burst 100% of max possible packets.
      2,  // Burst 50% of max possible packets.
      5,  // Burst 20% of max possible packets.
  };

  const Clock::duration kRoundTripTime = milliseconds(1);

  constexpr int kReceivedBytesPerSecond = 256000;
  constexpr int kReceivedBytesPerTimeslice =
      kReceivedBytesPerSecond / kTimeslicesPerSecond;
  static_assert(kReceivedBytesPerSecond % kTimeslicesPerSecond == 0,
                "Test expectations won't account for rounding errors.");

  ASSERT_EQ(0, estimator()->ComputeNetworkBandwidth());

  // Simulate bursting at various rates, and confirm the bandwidth estimate is
  // increasing for each burst rate. The estimate should be increasing because
  // the total time spent transmitting is decreasing (while the same number of
  // bytes are being received).
  Clock::time_point now = kStartTime;
  for (int divisor : kDivisors) {
    SCOPED_TRACE(testing::Message() << "divisor=" << divisor);

    const Clock::time_point end = now + estimator()->history_window();
    for (; now < end; now += kTimesliceDuration) {
      estimator()->OnBurstComplete(kMaxPacketsPerTimeslice / divisor, now);
      const Clock::time_point rtcp_arrival_time = now + kRoundTripTime;
      estimator()->OnPayloadReceived(kReceivedBytesPerTimeslice,
                                     rtcp_arrival_time, kRoundTripTime);
      estimator()->OnRtcpReceived(rtcp_arrival_time, kRoundTripTime);
    }
    now = end;

    const int estimate = estimator()->ComputeNetworkBandwidth();
    EXPECT_EQ(divisor * kReceivedBytesPerSecond * CHAR_BIT, estimate);
  }
}

// Tests that magnitude of the network round trip times, as well as random
// variance in packet arrival times, do not have a significant effect on the
// bandwidth estimates.
TEST_F(BandwidthEstimatorTest, EstimatesIndependentOfFeedbackDelays) {
  constexpr int kFactor = 2;
  constexpr int kPacketsPerBurst = kMaxPacketsPerTimeslice / kFactor;
  static_assert(kMaxPacketsPerTimeslice % kFactor == 0, "wanted exactly half");

  constexpr milliseconds kRoundTripTimes[3] = {milliseconds(1), milliseconds(9),
                                               milliseconds(42)};

  constexpr int kReceivedBytesPerSecond = 2000000;
  constexpr int kReceivedBytesPerTimeslice =
      kReceivedBytesPerSecond / kTimeslicesPerSecond;

  // An arbitrary threshold. Sources of error include anything that would place
  // byte flows outside the history window (e.g., AddFuzz(), or the 42ms round
  // trip time).
  constexpr int kMaxErrorPercent = 3;

  Clock::time_point now = kStartTime;
  for (Clock::duration round_trip_time : kRoundTripTimes) {
    SCOPED_TRACE(testing::Message()
                 << "round_trip_time=" << round_trip_time.count());

    const Clock::time_point end = now + estimator()->history_window();
    for (; now < end; now += kTimesliceDuration) {
      estimator()->OnBurstComplete(kPacketsPerBurst, now);
      const Clock::time_point rtcp_arrival_time =
          AddFuzz(now + round_trip_time);
      estimator()->OnPayloadReceived(kReceivedBytesPerTimeslice,
                                     rtcp_arrival_time, round_trip_time);
      estimator()->OnRtcpReceived(rtcp_arrival_time, round_trip_time);
    }
    now = end;

    constexpr int kExpectedEstimate =
        kFactor * kReceivedBytesPerSecond * CHAR_BIT;
    constexpr int kMaxError = kExpectedEstimate * kMaxErrorPercent / 100;
    EXPECT_NEAR(kExpectedEstimate, estimator()->ComputeNetworkBandwidth(),
                kMaxError);
  }
}

// Tests that both the history tracking internal to BandwidthEstimator, as well
// as its computation of the bandwidth estimate, are both resistant to possible
// integer overflow cases. The internal implementation always clamps to the
// valid range of int.
TEST_F(BandwidthEstimatorTest, ClampsEstimateToMaxInt) {
  constexpr int kPacketsPerBurst = kMaxPacketsPerTimeslice / 5;
  static_assert(kMaxPacketsPerTimeslice % 5 == 0, "wanted exactly 20%");
  const Clock::duration kRoundTripTime = milliseconds(1);

  int last_estimate = estimator()->ComputeNetworkBandwidth();
  ASSERT_EQ(last_estimate, 0);

  // Simulate increasing numbers of bytes received per timeslice until it
  // reaches values near INT_MAX. Along the way, the bandwidth estimates
  // themselves should start clamping and, because of the fuzz added to RTCP
  // arrival times, individual buckets in BandwidthEstimator::FlowTracker will
  // occassionally be clamped too.
  Clock::time_point now = kStartTime;
  for (unsigned int bytes_received_per_timeslice = 1;
       // Not overflowed past INT_MAX.
       static_cast<int>(bytes_received_per_timeslice) > 0;
       bytes_received_per_timeslice *= 2) {
    int int_bytes = static_cast<int>(bytes_received_per_timeslice);
    SCOPED_TRACE(testing::Message()
                 << "bytes_received_per_timeslice=" << int_bytes);

    const Clock::time_point end = now + estimator()->history_window() / 4;
    for (; now < end; now += kTimesliceDuration) {
      estimator()->OnBurstComplete(kPacketsPerBurst, now);
      const Clock::time_point rtcp_arrival_time = AddFuzz(now + kRoundTripTime);
      estimator()->OnPayloadReceived(int_bytes, rtcp_arrival_time,
                                     kRoundTripTime);
      estimator()->OnRtcpReceived(rtcp_arrival_time, kRoundTripTime);
    }
    now = end;

    const int estimate = estimator()->ComputeNetworkBandwidth();
    EXPECT_LE(last_estimate, estimate);
    last_estimate = estimate;
  }

  // Confirm there was a loop iteration at which the estimate reached INT_MAX
  // and then stayed there for successive loop iterations.
  EXPECT_EQ(std::numeric_limits<int>::max(), last_estimate);
}

}  // namespace
}  // namespace cast
}  // namespace openscreen