/*
 *  Copyright (c) 2014 The WebRTC project authors. All Rights Reserved.
 *
 *  Use of this source code is governed by a BSD-style license
 *  that can be found in the LICENSE file in the root of the source
 *  tree. An additional intellectual property rights grant can be found
 *  in the file PATENTS.  All contributing project authors may
 *  be found in the AUTHORS file in the root of the source tree.
 */

#include "modules/remote_bitrate_estimator/aimd_rate_control.h"

#include <inttypes.h>

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <string>

#include "api/transport/network_types.h"
#include "api/units/data_rate.h"
#include "modules/remote_bitrate_estimator/include/bwe_defines.h"
#include "modules/remote_bitrate_estimator/overuse_detector.h"
#include "rtc_base/checks.h"
#include "rtc_base/experiments/field_trial_parser.h"
#include "rtc_base/logging.h"
#include "rtc_base/numerics/safe_minmax.h"

namespace webrtc {
namespace {

constexpr TimeDelta kDefaultRtt = TimeDelta::Millis<200>();
constexpr double kDefaultBackoffFactor = 0.85;

constexpr char kBweBackOffFactorExperiment[] = "WebRTC-BweBackOffFactor";

bool IsEnabled(const WebRtcKeyValueConfig& field_trials,
               absl::string_view key) {
  return field_trials.Lookup(key).find("Enabled") == 0;
}

double ReadBackoffFactor(const WebRtcKeyValueConfig& key_value_config) {
  std::string experiment_string =
      key_value_config.Lookup(kBweBackOffFactorExperiment);
  double backoff_factor;
  int parsed_values =
      sscanf(experiment_string.c_str(), "Enabled-%lf", &backoff_factor);
  if (parsed_values == 1) {
    if (backoff_factor >= 1.0) {
      RTC_LOG(WARNING) << "Back-off factor must be less than 1.";
    } else if (backoff_factor <= 0.0) {
      RTC_LOG(WARNING) << "Back-off factor must be greater than 0.";
    } else {
      return backoff_factor;
    }
  }
  RTC_LOG(LS_WARNING) << "Failed to parse parameters for AimdRateControl "
                         "experiment from field trial string. Using default.";
  return kDefaultBackoffFactor;
}

}  // namespace

AimdRateControl::AimdRateControl(const WebRtcKeyValueConfig* key_value_config)
    : AimdRateControl(key_value_config, /* send_side =*/false) {}

AimdRateControl::AimdRateControl(const WebRtcKeyValueConfig* key_value_config,
                                 bool send_side)
    : min_configured_bitrate_(congestion_controller::GetMinBitrate()),
      max_configured_bitrate_(DataRate::kbps(30000)),
      current_bitrate_(max_configured_bitrate_),
      latest_estimated_throughput_(current_bitrate_),
      link_capacity_(),
      rate_control_state_(kRcHold),
      time_last_bitrate_change_(Timestamp::MinusInfinity()),
      time_last_bitrate_decrease_(Timestamp::MinusInfinity()),
      time_first_throughput_estimate_(Timestamp::MinusInfinity()),
      bitrate_is_initialized_(false),
      beta_(IsEnabled(*key_value_config, kBweBackOffFactorExperiment)
                ? ReadBackoffFactor(*key_value_config)
                : kDefaultBackoffFactor),
      in_alr_(false),
      rtt_(kDefaultRtt),
      send_side_(send_side),
      in_experiment_(!AdaptiveThresholdExperimentIsDisabled(*key_value_config)),
      no_bitrate_increase_in_alr_(
          IsEnabled(*key_value_config,
                    "WebRTC-DontIncreaseDelayBasedBweInAlr")),
      smoothing_experiment_(
          IsEnabled(*key_value_config, "WebRTC-Audio-BandwidthSmoothing")),
      initial_backoff_interval_("initial_backoff_interval"),
      low_throughput_threshold_("low_throughput", DataRate::Zero()),
      capacity_deviation_ratio_threshold_("cap_thr", 0.2),
      cross_traffic_factor_("cross", 1.0),
      capacity_limit_deviation_factor_("cap_lim", 1) {
  // E.g
  // WebRTC-BweAimdRateControlConfig/initial_backoff_interval:100ms,
  // low_throughput:50kbps/
  ParseFieldTrial({&initial_backoff_interval_, &low_throughput_threshold_},
                  key_value_config->Lookup("WebRTC-BweAimdRateControlConfig"));
  if (initial_backoff_interval_) {
    RTC_LOG(LS_INFO) << "Using aimd rate control with initial back-off interval"
                     << " " << ToString(*initial_backoff_interval_) << ".";
  }
  RTC_LOG(LS_INFO) << "Using aimd rate control with back off factor " << beta_;
  ParseFieldTrial(
      {&capacity_deviation_ratio_threshold_, &cross_traffic_factor_,
       &capacity_limit_deviation_factor_},
      key_value_config->Lookup("WebRTC-Bwe-AimdRateControl-NetworkState"));
}

AimdRateControl::~AimdRateControl() {}

void AimdRateControl::SetStartBitrate(DataRate start_bitrate) {
  current_bitrate_ = start_bitrate;
  latest_estimated_throughput_ = current_bitrate_;
  bitrate_is_initialized_ = true;
}

void AimdRateControl::SetMinBitrate(DataRate min_bitrate) {
  min_configured_bitrate_ = min_bitrate;
  current_bitrate_ = std::max(min_bitrate, current_bitrate_);
}

bool AimdRateControl::ValidEstimate() const {
  return bitrate_is_initialized_;
}

TimeDelta AimdRateControl::GetFeedbackInterval() const {
  // Estimate how often we can send RTCP if we allocate up to 5% of bandwidth
  // to feedback.
  const DataSize kRtcpSize = DataSize::bytes(80);
  const DataRate rtcp_bitrate = current_bitrate_ * 0.05;
  const TimeDelta interval = kRtcpSize / rtcp_bitrate;
  const TimeDelta kMinFeedbackInterval = TimeDelta::ms(200);
  const TimeDelta kMaxFeedbackInterval = TimeDelta::ms(1000);
  return interval.Clamped(kMinFeedbackInterval, kMaxFeedbackInterval);
}

bool AimdRateControl::TimeToReduceFurther(Timestamp at_time,
                                          DataRate estimated_throughput) const {
  const TimeDelta bitrate_reduction_interval =
      rtt_.Clamped(TimeDelta::ms(10), TimeDelta::ms(200));
  if (at_time - time_last_bitrate_change_ >= bitrate_reduction_interval) {
    return true;
  }
  if (ValidEstimate()) {
    // TODO(terelius/holmer): Investigate consequences of increasing
    // the threshold to 0.95 * LatestEstimate().
    const DataRate threshold = 0.5 * LatestEstimate();
    return estimated_throughput < threshold;
  }
  return false;
}

bool AimdRateControl::InitialTimeToReduceFurther(Timestamp at_time) const {
  if (!initial_backoff_interval_) {
    return ValidEstimate() &&
           TimeToReduceFurther(at_time,
                               LatestEstimate() / 2 - DataRate::bps(1));
  }
  // TODO(terelius): We could use the RTT (clamped to suitable limits) instead
  // of a fixed bitrate_reduction_interval.
  if (time_last_bitrate_decrease_.IsInfinite() ||
      at_time - time_last_bitrate_decrease_ >= *initial_backoff_interval_) {
    return true;
  }
  return false;
}

DataRate AimdRateControl::LatestEstimate() const {
  return current_bitrate_;
}

void AimdRateControl::SetRtt(TimeDelta rtt) {
  rtt_ = rtt;
}

DataRate AimdRateControl::Update(const RateControlInput* input,
                                 Timestamp at_time) {
  RTC_CHECK(input);

  // Set the initial bit rate value to what we're receiving the first half
  // second.
  // TODO(bugs.webrtc.org/9379): The comment above doesn't match to the code.
  if (!bitrate_is_initialized_) {
    const TimeDelta kInitializationTime = TimeDelta::seconds(5);
    RTC_DCHECK_LE(kBitrateWindowMs, kInitializationTime.ms());
    if (time_first_throughput_estimate_.IsInfinite()) {
      if (input->estimated_throughput)
        time_first_throughput_estimate_ = at_time;
    } else if (at_time - time_first_throughput_estimate_ >
                   kInitializationTime &&
               input->estimated_throughput) {
      current_bitrate_ = *input->estimated_throughput;
      bitrate_is_initialized_ = true;
    }
  }

  current_bitrate_ = ChangeBitrate(current_bitrate_, *input, at_time);
  return current_bitrate_;
}

void AimdRateControl::SetInApplicationLimitedRegion(bool in_alr) {
  in_alr_ = in_alr;
}

void AimdRateControl::SetEstimate(DataRate bitrate, Timestamp at_time) {
  bitrate_is_initialized_ = true;
  DataRate prev_bitrate = current_bitrate_;
  current_bitrate_ = ClampBitrate(bitrate, bitrate);
  time_last_bitrate_change_ = at_time;
  if (current_bitrate_ < prev_bitrate) {
    time_last_bitrate_decrease_ = at_time;
  }
}

void AimdRateControl::SetNetworkStateEstimate(
    const absl::optional<NetworkStateEstimate>& estimate) {
  network_estimate_ = estimate;
}

double AimdRateControl::GetNearMaxIncreaseRateBpsPerSecond() const {
  RTC_DCHECK(!current_bitrate_.IsZero());
  const TimeDelta kFrameInterval = TimeDelta::seconds(1) / 30;
  DataSize frame_size = current_bitrate_ * kFrameInterval;
  const DataSize kPacketSize = DataSize::bytes(1200);
  double packets_per_frame = std::ceil(frame_size / kPacketSize);
  DataSize avg_packet_size = frame_size / packets_per_frame;

  // Approximate the over-use estimator delay to 100 ms.
  TimeDelta response_time = rtt_ + TimeDelta::ms(100);
  if (in_experiment_)
    response_time = response_time * 2;
  double increase_rate_bps_per_second =
      (avg_packet_size / response_time).bps<double>();
  double kMinIncreaseRateBpsPerSecond = 4000;
  return std::max(kMinIncreaseRateBpsPerSecond, increase_rate_bps_per_second);
}

TimeDelta AimdRateControl::GetExpectedBandwidthPeriod() const {
  const TimeDelta kMinPeriod =
      smoothing_experiment_ ? TimeDelta::ms(500) : TimeDelta::seconds(2);
  const TimeDelta kDefaultPeriod = TimeDelta::seconds(3);
  const TimeDelta kMaxPeriod = TimeDelta::seconds(50);

  double increase_rate_bps_per_second = GetNearMaxIncreaseRateBpsPerSecond();
  if (!last_decrease_)
    return smoothing_experiment_ ? kMinPeriod : kDefaultPeriod;
  double time_to_recover_decrease_seconds =
      last_decrease_->bps() / increase_rate_bps_per_second;
  TimeDelta period = TimeDelta::seconds(time_to_recover_decrease_seconds);
  return period.Clamped(kMinPeriod, kMaxPeriod);
}

DataRate AimdRateControl::ChangeBitrate(DataRate new_bitrate,
                                        const RateControlInput& input,
                                        Timestamp at_time) {
  DataRate estimated_throughput =
      input.estimated_throughput.value_or(latest_estimated_throughput_);
  if (input.estimated_throughput)
    latest_estimated_throughput_ = *input.estimated_throughput;

  // An over-use should always trigger us to reduce the bitrate, even though
  // we have not yet established our first estimate. By acting on the over-use,
  // we will end up with a valid estimate.
  if (!bitrate_is_initialized_ &&
      input.bw_state != BandwidthUsage::kBwOverusing)
    return current_bitrate_;

  ChangeState(input, at_time);

  switch (rate_control_state_) {
    case kRcHold:
      break;

    case kRcIncrease:
      if (estimated_throughput > link_capacity_.UpperBound())
        link_capacity_.Reset();

      // Do not increase the delay based estimate in alr since the estimator
      // will not be able to get transport feedback necessary to detect if
      // the new estimate is correct.
      if (!(send_side_ && in_alr_ && no_bitrate_increase_in_alr_)) {
        if (link_capacity_.has_estimate()) {
          // The link_capacity estimate is reset if the measured throughput
          // is too far from the estimate. We can therefore assume that our
          // target rate is reasonably close to link capacity and use additive
          // increase.
          DataRate additive_increase =
              AdditiveRateIncrease(at_time, time_last_bitrate_change_);
          new_bitrate += additive_increase;
        } else {
          // If we don't have an estimate of the link capacity, use faster ramp
          // up to discover the capacity.
          DataRate multiplicative_increase = MultiplicativeRateIncrease(
              at_time, time_last_bitrate_change_, new_bitrate);
          new_bitrate += multiplicative_increase;
        }
      }

      time_last_bitrate_change_ = at_time;
      break;

    case kRcDecrease:
      if (network_estimate_ && capacity_deviation_ratio_threshold_) {
        // If we have a low variance network estimate, we use it over the
        // acknowledged rate to avoid dropping the bitrate too far. This avoids
        // overcompensating when the send rate is lower than the capacity.
        double deviation_ratio = network_estimate_->link_capacity_std_dev /
                                 network_estimate_->link_capacity;
        if (deviation_ratio < *capacity_deviation_ratio_threshold_) {
          double available_ratio =
              std::max(0.0, 1.0 - network_estimate_->cross_traffic_ratio *
                                      cross_traffic_factor_);
          DataRate available_rate =
              network_estimate_->link_capacity * available_ratio;
          estimated_throughput = std::max(available_rate, estimated_throughput);
        }
      }
      if (estimated_throughput > low_throughput_threshold_) {
        // Set bit rate to something slightly lower than the measured throughput
        // to get rid of any self-induced delay.
        new_bitrate = estimated_throughput * beta_;
        if (new_bitrate > current_bitrate_) {
          // Avoid increasing the rate when over-using.
          if (link_capacity_.has_estimate()) {
            new_bitrate = beta_ * link_capacity_.estimate();
          }
        }
      } else {
        new_bitrate = estimated_throughput;
        if (link_capacity_.has_estimate()) {
          new_bitrate = std::max(new_bitrate, link_capacity_.estimate());
        }
        new_bitrate = std::min(new_bitrate, low_throughput_threshold_.Get());
      }
      new_bitrate = std::min(new_bitrate, current_bitrate_);

      if (bitrate_is_initialized_ && estimated_throughput < current_bitrate_) {
        constexpr double kDegradationFactor = 0.9;
        if (smoothing_experiment_ &&
            new_bitrate < kDegradationFactor * beta_ * current_bitrate_) {
          // If bitrate decreases more than a normal back off after overuse, it
          // indicates a real network degradation. We do not let such a decrease
          // to determine the bandwidth estimation period.
          last_decrease_ = absl::nullopt;
        } else {
          last_decrease_ = current_bitrate_ - new_bitrate;
        }
      }
      if (estimated_throughput < link_capacity_.LowerBound()) {
        // The current throughput is far from the estimated link capacity. Clear
        // the estimate to allow an immediate update in OnOveruseDetected.
        link_capacity_.Reset();
      }

      bitrate_is_initialized_ = true;
      link_capacity_.OnOveruseDetected(estimated_throughput);
      // Stay on hold until the pipes are cleared.
      rate_control_state_ = kRcHold;
      time_last_bitrate_change_ = at_time;
      time_last_bitrate_decrease_ = at_time;
      break;

    default:
      assert(false);
  }
  return ClampBitrate(new_bitrate, estimated_throughput);
}

DataRate AimdRateControl::ClampBitrate(DataRate new_bitrate,
                                       DataRate estimated_throughput) const {
  // Allow the estimate to increase as long as alr is not detected to ensure
  // that there is no BWE values that can make the estimate stuck at a too
  // low bitrate. If an encoder can not produce the bitrate necessary to
  // fully use the capacity, alr will sooner or later trigger.
  if (!(send_side_ && no_bitrate_increase_in_alr_)) {
    // Don't change the bit rate if the send side is too far off.
    // We allow a bit more lag at very low rates to not too easily get stuck if
    // the encoder produces uneven outputs.
    const DataRate max_bitrate =
        1.5 * estimated_throughput + DataRate::kbps(10);
    if (new_bitrate > current_bitrate_ && new_bitrate > max_bitrate) {
      new_bitrate = std::max(current_bitrate_, max_bitrate);
    }
  }

  if (network_estimate_ && capacity_limit_deviation_factor_) {
    DataRate upper_bound = network_estimate_->link_capacity +
                           network_estimate_->link_capacity_std_dev *
                               capacity_limit_deviation_factor_.Value();
    new_bitrate = std::min(new_bitrate, upper_bound);
  }
  new_bitrate = std::max(new_bitrate, min_configured_bitrate_);
  return new_bitrate;
}

DataRate AimdRateControl::MultiplicativeRateIncrease(
    Timestamp at_time,
    Timestamp last_time,
    DataRate current_bitrate) const {
  double alpha = 1.08;
  if (last_time.IsFinite()) {
    auto time_since_last_update = at_time - last_time;
    alpha = pow(alpha, std::min(time_since_last_update.seconds<double>(), 1.0));
  }
  DataRate multiplicative_increase =
      std::max(current_bitrate * (alpha - 1.0), DataRate::bps(1000));
  return multiplicative_increase;
}

DataRate AimdRateControl::AdditiveRateIncrease(Timestamp at_time,
                                               Timestamp last_time) const {
  double time_period_seconds = (at_time - last_time).seconds<double>();
  double data_rate_increase_bps =
      GetNearMaxIncreaseRateBpsPerSecond() * time_period_seconds;
  return DataRate::bps(data_rate_increase_bps);
}

void AimdRateControl::ChangeState(const RateControlInput& input,
                                  Timestamp at_time) {
  switch (input.bw_state) {
    case BandwidthUsage::kBwNormal:
      if (rate_control_state_ == kRcHold) {
        time_last_bitrate_change_ = at_time;
        rate_control_state_ = kRcIncrease;
      }
      break;
    case BandwidthUsage::kBwOverusing:
      if (rate_control_state_ != kRcDecrease) {
        rate_control_state_ = kRcDecrease;
      }
      break;
    case BandwidthUsage::kBwUnderusing:
      rate_control_state_ = kRcHold;
      break;
    default:
      assert(false);
  }
}

}  // namespace webrtc