/*
 *  Copyright (c) 2013 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/remote_bitrate_estimator_abs_send_time.h"

#include <math.h>

#include <algorithm>
#include <memory>
#include <utility>

#include "api/transport/field_trial_based_config.h"
#include "api/units/data_rate.h"
#include "api/units/data_size.h"
#include "api/units/time_delta.h"
#include "api/units/timestamp.h"
#include "modules/remote_bitrate_estimator/include/bwe_defines.h"
#include "modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
#include "rtc_base/checks.h"
#include "rtc_base/logging.h"
#include "system_wrappers/include/metrics.h"

namespace webrtc {
namespace {

constexpr TimeDelta kMinClusterDelta = TimeDelta::Millis(1);
constexpr TimeDelta kInitialProbingInterval = TimeDelta::Seconds(2);
constexpr int kTimestampGroupLengthMs = 5;
constexpr int kAbsSendTimeInterArrivalUpshift = 8;
constexpr int kInterArrivalShift =
    RTPHeaderExtension::kAbsSendTimeFraction + kAbsSendTimeInterArrivalUpshift;
constexpr int kMinClusterSize = 4;
constexpr int kMaxProbePackets = 15;
constexpr int kExpectedNumberOfProbes = 3;
constexpr double kTimestampToMs =
    1000.0 / static_cast<double>(1 << kInterArrivalShift);

absl::optional<DataRate> OptionalRateFromOptionalBps(
    absl::optional<int> bitrate_bps) {
  if (bitrate_bps) {
    return DataRate::BitsPerSec(*bitrate_bps);
  } else {
    return absl::nullopt;
  }
}

template <typename K, typename V>
std::vector<K> Keys(const std::map<K, V>& map) {
  std::vector<K> keys;
  keys.reserve(map.size());
  for (const auto& kv_pair : map) {
    keys.push_back(kv_pair.first);
  }
  return keys;
}

}  // namespace

RemoteBitrateEstimatorAbsSendTime::~RemoteBitrateEstimatorAbsSendTime() =
    default;

bool RemoteBitrateEstimatorAbsSendTime::IsWithinClusterBounds(
    TimeDelta send_delta,
    const Cluster& cluster_aggregate) {
  if (cluster_aggregate.count == 0)
    return true;
  TimeDelta cluster_mean =
      cluster_aggregate.send_mean / cluster_aggregate.count;
  return (send_delta - cluster_mean).Abs() < TimeDelta::Micros(2'500);
}

void RemoteBitrateEstimatorAbsSendTime::MaybeAddCluster(
    const Cluster& cluster_aggregate,
    std::list<Cluster>& clusters) {
  if (cluster_aggregate.count < kMinClusterSize ||
      cluster_aggregate.send_mean <= TimeDelta::Zero() ||
      cluster_aggregate.recv_mean <= TimeDelta::Zero()) {
    return;
  }

  Cluster cluster;
  cluster.send_mean = cluster_aggregate.send_mean / cluster_aggregate.count;
  cluster.recv_mean = cluster_aggregate.recv_mean / cluster_aggregate.count;
  cluster.mean_size = cluster_aggregate.mean_size / cluster_aggregate.count;
  cluster.count = cluster_aggregate.count;
  cluster.num_above_min_delta = cluster_aggregate.num_above_min_delta;
  clusters.push_back(cluster);
}

RemoteBitrateEstimatorAbsSendTime::RemoteBitrateEstimatorAbsSendTime(
    RemoteBitrateObserver* observer,
    Clock* clock)
    : clock_(clock), observer_(observer), remote_rate_(field_trials_) {
  RTC_DCHECK(clock_);
  RTC_DCHECK(observer_);
  RTC_LOG(LS_INFO) << "RemoteBitrateEstimatorAbsSendTime: Instantiating.";
}

std::list<RemoteBitrateEstimatorAbsSendTime::Cluster>
RemoteBitrateEstimatorAbsSendTime::ComputeClusters() const {
  std::list<Cluster> clusters;
  Cluster cluster_aggregate;
  Timestamp prev_send_time = Timestamp::MinusInfinity();
  Timestamp prev_recv_time = Timestamp::MinusInfinity();
  for (const Probe& probe : probes_) {
    if (prev_send_time.IsFinite()) {
      TimeDelta send_delta = probe.send_time - prev_send_time;
      TimeDelta recv_delta = probe.recv_time - prev_recv_time;
      if (send_delta >= kMinClusterDelta && recv_delta >= kMinClusterDelta) {
        ++cluster_aggregate.num_above_min_delta;
      }
      if (!IsWithinClusterBounds(send_delta, cluster_aggregate)) {
        MaybeAddCluster(cluster_aggregate, clusters);
        cluster_aggregate = Cluster();
      }
      cluster_aggregate.send_mean += send_delta;
      cluster_aggregate.recv_mean += recv_delta;
      cluster_aggregate.mean_size += probe.payload_size;
      ++cluster_aggregate.count;
    }
    prev_send_time = probe.send_time;
    prev_recv_time = probe.recv_time;
  }
  MaybeAddCluster(cluster_aggregate, clusters);
  return clusters;
}

const RemoteBitrateEstimatorAbsSendTime::Cluster*
RemoteBitrateEstimatorAbsSendTime::FindBestProbe(
    const std::list<Cluster>& clusters) const {
  DataRate highest_probe_bitrate = DataRate::Zero();
  const Cluster* best = nullptr;
  for (const auto& cluster : clusters) {
    if (cluster.send_mean == TimeDelta::Zero() ||
        cluster.recv_mean == TimeDelta::Zero()) {
      continue;
    }
    if (cluster.num_above_min_delta > cluster.count / 2 &&
        (cluster.recv_mean - cluster.send_mean <= TimeDelta::Millis(2) &&
         cluster.send_mean - cluster.recv_mean <= TimeDelta::Millis(5))) {
      DataRate probe_bitrate =
          std::min(cluster.SendBitrate(), cluster.RecvBitrate());
      if (probe_bitrate > highest_probe_bitrate) {
        highest_probe_bitrate = probe_bitrate;
        best = &cluster;
      }
    } else {
      RTC_LOG(LS_INFO) << "Probe failed, sent at "
                       << cluster.SendBitrate().bps() << " bps, received at "
                       << cluster.RecvBitrate().bps()
                       << " bps. Mean send delta: " << cluster.send_mean.ms()
                       << " ms, mean recv delta: " << cluster.recv_mean.ms()
                       << " ms, num probes: " << cluster.count;
      break;
    }
  }
  return best;
}

RemoteBitrateEstimatorAbsSendTime::ProbeResult
RemoteBitrateEstimatorAbsSendTime::ProcessClusters(Timestamp now) {
  std::list<Cluster> clusters = ComputeClusters();
  if (clusters.empty()) {
    // If we reach the max number of probe packets and still have no clusters,
    // we will remove the oldest one.
    if (probes_.size() >= kMaxProbePackets)
      probes_.pop_front();
    return ProbeResult::kNoUpdate;
  }

  if (const Cluster* best = FindBestProbe(clusters)) {
    DataRate probe_bitrate = std::min(best->SendBitrate(), best->RecvBitrate());
    // Make sure that a probe sent on a lower bitrate than our estimate can't
    // reduce the estimate.
    if (IsBitrateImproving(probe_bitrate)) {
      RTC_LOG(LS_INFO) << "Probe successful, sent at "
                       << best->SendBitrate().bps() << " bps, received at "
                       << best->RecvBitrate().bps()
                       << " bps. Mean send delta: " << best->send_mean.ms()
                       << " ms, mean recv delta: " << best->recv_mean.ms()
                       << " ms, num probes: " << best->count;
      remote_rate_.SetEstimate(probe_bitrate, now);
      return ProbeResult::kBitrateUpdated;
    }
  }

  // Not probing and received non-probe packet, or finished with current set
  // of probes.
  if (clusters.size() >= kExpectedNumberOfProbes)
    probes_.clear();
  return ProbeResult::kNoUpdate;
}

bool RemoteBitrateEstimatorAbsSendTime::IsBitrateImproving(
    DataRate probe_bitrate) const {
  bool initial_probe =
      !remote_rate_.ValidEstimate() && probe_bitrate > DataRate::Zero();
  bool bitrate_above_estimate = remote_rate_.ValidEstimate() &&
                                probe_bitrate > remote_rate_.LatestEstimate();
  return initial_probe || bitrate_above_estimate;
}

void RemoteBitrateEstimatorAbsSendTime::IncomingPacket(
    int64_t arrival_time_ms,
    size_t payload_size,
    const RTPHeader& header) {
  if (!header.extension.hasAbsoluteSendTime) {
    RTC_LOG(LS_WARNING)
        << "RemoteBitrateEstimatorAbsSendTimeImpl: Incoming packet "
           "is missing absolute send time extension!";
    return;
  }
  IncomingPacketInfo(Timestamp::Millis(arrival_time_ms),
                     header.extension.absoluteSendTime,
                     DataSize::Bytes(payload_size), header.ssrc);
}

void RemoteBitrateEstimatorAbsSendTime::IncomingPacketInfo(
    Timestamp arrival_time,
    uint32_t send_time_24bits,
    DataSize payload_size,
    uint32_t ssrc) {
  RTC_CHECK(send_time_24bits < (1ul << 24));
  if (!uma_recorded_) {
    RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram, BweNames::kReceiverAbsSendTime,
                              BweNames::kBweNamesMax);
    uma_recorded_ = true;
  }
  // Shift up send time to use the full 32 bits that inter_arrival works with,
  // so wrapping works properly.
  uint32_t timestamp = send_time_24bits << kAbsSendTimeInterArrivalUpshift;
  Timestamp send_time =
      Timestamp::Millis(static_cast<int64_t>(timestamp) * kTimestampToMs);

  Timestamp now = clock_->CurrentTime();
  // TODO(holmer): SSRCs are only needed for REMB, should be broken out from
  // here.

  // Check if incoming bitrate estimate is valid, and if it needs to be reset.
  absl::optional<uint32_t> incoming_bitrate =
      incoming_bitrate_.Rate(arrival_time.ms());
  if (incoming_bitrate) {
    incoming_bitrate_initialized_ = true;
  } else if (incoming_bitrate_initialized_) {
    // Incoming bitrate had a previous valid value, but now not enough data
    // point are left within the current window. Reset incoming bitrate
    // estimator so that the window size will only contain new data points.
    incoming_bitrate_.Reset();
    incoming_bitrate_initialized_ = false;
  }
  incoming_bitrate_.Update(payload_size.bytes(), arrival_time.ms());

  if (first_packet_time_.IsInfinite()) {
    first_packet_time_ = now;
  }

  uint32_t ts_delta = 0;
  int64_t t_delta = 0;
  int size_delta = 0;
  bool update_estimate = false;
  DataRate target_bitrate = DataRate::Zero();

  TimeoutStreams(now);
  RTC_DCHECK(inter_arrival_);
  RTC_DCHECK(estimator_);
  ssrcs_.insert_or_assign(ssrc, now);

  // For now only try to detect probes while we don't have a valid estimate.
  // We currently assume that only packets larger than 200 bytes are paced by
  // the sender.
  static constexpr DataSize kMinProbePacketSize = DataSize::Bytes(200);
  if (payload_size > kMinProbePacketSize &&
      (!remote_rate_.ValidEstimate() ||
       now - first_packet_time_ < kInitialProbingInterval)) {
    // TODO(holmer): Use a map instead to get correct order?
    if (total_probes_received_ < kMaxProbePackets) {
      TimeDelta send_delta = TimeDelta::Millis(-1);
      TimeDelta recv_delta = TimeDelta::Millis(-1);
      if (!probes_.empty()) {
        send_delta = send_time - probes_.back().send_time;
        recv_delta = arrival_time - probes_.back().recv_time;
      }
      RTC_LOG(LS_INFO) << "Probe packet received: send time=" << send_time.ms()
                       << " ms, recv time=" << arrival_time.ms()
                       << " ms, send delta=" << send_delta.ms()
                       << " ms, recv delta=" << recv_delta.ms() << " ms.";
    }
    probes_.emplace_back(send_time, arrival_time, payload_size);
    ++total_probes_received_;
    // Make sure that a probe which updated the bitrate immediately has an
    // effect by calling the OnReceiveBitrateChanged callback.
    if (ProcessClusters(now) == ProbeResult::kBitrateUpdated)
      update_estimate = true;
  }
  if (inter_arrival_->ComputeDeltas(timestamp, arrival_time.ms(), now.ms(),
                                    payload_size.bytes(), &ts_delta, &t_delta,
                                    &size_delta)) {
    double ts_delta_ms = (1000.0 * ts_delta) / (1 << kInterArrivalShift);
    estimator_->Update(t_delta, ts_delta_ms, size_delta, detector_.State(),
                       arrival_time.ms());
    detector_.Detect(estimator_->offset(), ts_delta_ms,
                     estimator_->num_of_deltas(), arrival_time.ms());
  }

  if (!update_estimate) {
    // Check if it's time for a periodic update or if we should update because
    // of an over-use.
    if (last_update_.IsInfinite() ||
        now.ms() - last_update_.ms() >
            remote_rate_.GetFeedbackInterval().ms()) {
      update_estimate = true;
    } else if (detector_.State() == BandwidthUsage::kBwOverusing) {
      absl::optional<uint32_t> incoming_rate =
          incoming_bitrate_.Rate(arrival_time.ms());
      if (incoming_rate && remote_rate_.TimeToReduceFurther(
                               now, DataRate::BitsPerSec(*incoming_rate))) {
        update_estimate = true;
      }
    }
  }

  if (update_estimate) {
    // The first overuse should immediately trigger a new estimate.
    // We also have to update the estimate immediately if we are overusing
    // and the target bitrate is too high compared to what we are receiving.
    const RateControlInput input(
        detector_.State(),
        OptionalRateFromOptionalBps(incoming_bitrate_.Rate(arrival_time.ms())));
    target_bitrate = remote_rate_.Update(input, now);
    update_estimate = remote_rate_.ValidEstimate();
  }

  if (update_estimate) {
    last_update_ = now;
    observer_->OnReceiveBitrateChanged(Keys(ssrcs_),
                                       target_bitrate.bps<uint32_t>());
  }
}

TimeDelta RemoteBitrateEstimatorAbsSendTime::Process() {
  return TimeDelta::PlusInfinity();
}

void RemoteBitrateEstimatorAbsSendTime::TimeoutStreams(Timestamp now) {
  for (auto it = ssrcs_.begin(); it != ssrcs_.end();) {
    if (now - it->second > TimeDelta::Millis(kStreamTimeOutMs)) {
      ssrcs_.erase(it++);
    } else {
      ++it;
    }
  }
  if (ssrcs_.empty()) {
    // We can't update the estimate if we don't have any active streams.
    inter_arrival_ = std::make_unique<InterArrival>(
        (kTimestampGroupLengthMs << kInterArrivalShift) / 1000, kTimestampToMs);
    estimator_ = std::make_unique<OveruseEstimator>();
    // We deliberately don't reset the first_packet_time_ms_ here for now since
    // we only probe for bandwidth in the beginning of a call right now.
  }
}

void RemoteBitrateEstimatorAbsSendTime::OnRttUpdate(int64_t avg_rtt_ms,
                                                    int64_t /*max_rtt_ms*/) {
  remote_rate_.SetRtt(TimeDelta::Millis(avg_rtt_ms));
}

void RemoteBitrateEstimatorAbsSendTime::RemoveStream(uint32_t ssrc) {
  ssrcs_.erase(ssrc);
}

DataRate RemoteBitrateEstimatorAbsSendTime::LatestEstimate() const {
  // Currently accessed only from the worker thread (see Call::GetStats()).
  if (!remote_rate_.ValidEstimate() || ssrcs_.empty()) {
    return DataRate::Zero();
  }
  return remote_rate_.LatestEstimate();
}

}  // namespace webrtc