Implement the NackModule as part of the new jitter buffer.

webrtc/modules/video_coding/nack_module.cc

Index: webrtc/modules/video_coding/nack_module.cc
diff --git a/webrtc/modules/video_coding/nack_module.cc b/webrtc/modules/video_coding/nack_module.cc
new file mode 100644
index 0000000000000000000000000000000000000000..08f3aed95d7d7a9b9ff9029ae66b27a2cfc189b0
--- /dev/null
+++ b/webrtc/modules/video_coding/nack_module.cc
@@ -0,0 +1,276 @@
+/*
+ *  Copyright (c) 2016 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 <algorithm>
+#include <limits>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/mod_ops.h"
+#include "webrtc/modules/video_coding/nack_module.h"
+#include "webrtc/modules/utility/include/process_thread.h"
+
+namespace webrtc {
+
+static const uint16_t kMaxNackPackets = 1000;
+static const uint16_t kDefaultRttMs = 100;
+static const uint8_t kMaxNackRetries = 10;
+static const uint8_t kProcessFrequency = 50;
+static const uint8_t kProcessIntervalMs = 1000 / kProcessFrequency;
+
+NackModule::NackInfo::NackInfo()
+    : seq_num(0), send_at_seq_num(0), sent_at_time(-1), retries(0) {}
+
+NackModule::NackInfo::NackInfo(uint16_t seq_num, uint16_t send_at_seq_num)
+    : seq_num(seq_num),
+      send_at_seq_num(send_at_seq_num),
+      sent_at_time(-1),
+      retries(0) {}
+
+NackModule::NackModule(Clock* clock,
+                       VCMNackSender* nack_sender,
+                       VCMKeyFrameRequestSender* keyframe_request_sender)
+    : clock_(clock),
+      nack_sender_(nack_sender),
+      keyframe_request_sender_(keyframe_request_sender),
+      running_(true),
+      initialized_(false),
+      rtt_ms_(kDefaultRttMs),
+      last_seq_num_(0),
+      next_process_time_ms_(-1),
+      reordering_count_(0) {
+  memset(reordering_occurences_, -1, sizeof(reordering_occurences_));
+  memset(reordering_buckets_, 0, sizeof(reordering_buckets_));
+  RTC_DCHECK(clock_);
+  RTC_DCHECK(nack_sender_);
+  RTC_DCHECK(keyframe_request_sender_);
+}
+
+void NackModule::OnReceivedPacket(const VCMPacket& packet) {
+  rtc::CritScope lock(&crit_);
+  if (!running_)
+    return;
+  uint16_t seq_num = packet.seqNum;
+  // TODO(philipel): When the packet includes information whether it is
+  //                 retransmitted or not, use that value instead. For
+  //                 now set it to true, which will cause the reordering
+  //                 statistics to never be updated.
+  bool is_retransmitted = true;
+  bool is_keyframe = packet.isFirstPacket && packet.frameType == kVideoFrameKey;
+
+  if (!initialized_) {
+    last_seq_num_ = seq_num;
+    if (is_keyframe) keyframe_list_.emplace(seq_num);
+    initialized_ = true;
+    return;
+  }
+
+  if (seq_num == last_seq_num_)
+    return;
+
+  if (AheadOf(last_seq_num_, seq_num)) {
+    // An out of order packet has been received.
+    RemovePacketFromNack(seq_num);
+    if (!is_retransmitted)
+      UpdateReorderingStatistics(seq_num);
+    return;
+  } else {
+    AddPacketsToNack(last_seq_num_ + 1, seq_num);
+    last_seq_num_ = seq_num;
+
+    // Keep track of new keyframes.
+    if (is_keyframe)
+      keyframe_list_.emplace(seq_num);
+
+    // And remove old ones so we don't accumulate keyframes.
+    auto it = keyframe_list_.lower_bound(seq_num - kMaxNackPackets);
+    if (it != keyframe_list_.begin())
+      keyframe_list_.erase(keyframe_list_.begin(), it);
+
+    // Are there any nacks that are waiting for this seq_num.
+    std::vector<uint16_t> nack_batch = GetNackBatch(kSeqNumOnly);
+    if (!nack_batch.empty())
+      nack_sender_->SendNack(nack_batch.data(), nack_batch.size());
+  }
+}
+
+void NackModule::ClearUpTo(uint16_t seq_num) {
+  rtc::CritScope lock(&crit_);
+  nack_list_.erase(nack_list_.begin(),
+                   nack_list_.lower_bound(seq_num));
+  keyframe_list_.erase(keyframe_list_.begin(),
+                       keyframe_list_.lower_bound(seq_num));
+}
+
+void NackModule::UpdateRtt(int64_t rtt_ms) {
+  rtc::CritScope lock(&crit_);
+  rtt_ms_ = rtt_ms;
+}
+
+void NackModule::Stop() {
+  rtc::CritScope lock(&crit_);
+  running_ = false;
+}
+
+int64_t NackModule::TimeUntilNextProcess() {
+  rtc::CritScope lock(&crit_);
+  return std::max(next_process_time_ms_ - clock_->TimeInMilliseconds(), 0l);
+}
+
+int32_t NackModule::Process() {
+  rtc::CritScope lock(&crit_);
+  if (!running_)
+    return 0;
+
+  // Update the next_process_time_ms_ in intervals to achieve
+  // the targeted frequency over time. Also add multiple intervals
+  // in case of a skip in time as to not make uneccessary
+  // calls to Process in order to catch up.
+  int64_t now_ms = clock_->TimeInMilliseconds();
+  if (next_process_time_ms_ == -1) {
+    next_process_time_ms_ = now_ms + kProcessIntervalMs;
+  } else {
+    next_process_time_ms_ = next_process_time_ms_ +
+                            kProcessIntervalMs +
+                            (now_ms - next_process_time_ms_) /
+                            kProcessIntervalMs * kProcessIntervalMs;
+  }
+
+  std::vector<uint16_t> nack_batch = GetNackBatch(kTimeOnly);
+  if (!nack_batch.empty() && nack_sender_ != nullptr)
+    nack_sender_->SendNack(nack_batch.data(), nack_batch.size());
+
+  return 0;
+}
+
+bool NackModule::RemovePacketsUntilKeyframe() {
+  while (!keyframe_list_.empty()) {
+    auto it = nack_list_.lower_bound(*keyframe_list_.begin());
+
+    // If this keyframe is so old it does not remove any
+    // packets from the list, remove if from the list of
+    // keyframes and try the next keyframe.
+    if (it == nack_list_.begin()) {
+      keyframe_list_.erase(keyframe_list_.begin());
+      continue;
+    }
+
+    // We have found a keyframe that actually is newer than
+    // atleast one packet in the nack list.
+    nack_list_.erase(nack_list_.begin(), it);
+    return true;
+  }
+  return false;
+}
+
+void NackModule::AddPacketsToNack(uint16_t seq_num_start,
+                                  uint16_t seq_num_end) {
+  // If the nack list is too large, remove packets from the nack list until
+  // the latest first packet of a keyframe. If the list is still too large,
+  // clear it and request a keyframe.
+  uint16_t num_new_nacks = ForwardDiff(seq_num_start, seq_num_end);
+  if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
+    while (RemovePacketsUntilKeyframe() &&
+          nack_list_.size() + num_new_nacks > kMaxNackPackets) {}
+
+    if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
+      nack_list_.clear();
+      keyframe_request_sender_->RequestKeyFrame();
+      return;
+    }
+  }
+
+  for (uint16_t seq_num = seq_num_start; seq_num != seq_num_end; ++seq_num) {
+    NackInfo nack_info(seq_num, seq_num + WaitNumberOfPackets(0.5));
+    RTC_DCHECK(nack_list_.find(seq_num) == nack_list_.end());
+    nack_list_[seq_num] = nack_info;
+  }
+}
+
+void NackModule::RemovePacketFromNack(uint16_t seq_num) {
+  nack_list_.erase(seq_num);
+}
+
+std::vector<uint16_t> NackModule::GetNackBatch(NackFilterOptions options) {
+  bool consider_seq_num = options != kTimeOnly;
+  bool consider_timestamp = options != kSeqNumOnly;
+  int64_t now_ms = clock_->TimeInMilliseconds();
+  std::vector<uint16_t> nack_batch;
+  auto it = nack_list_.begin();
+  while (it != nack_list_.end()) {
+    if (consider_seq_num &&
+        it->second.sent_at_time == -1 &&
+        AheadOrAt(last_seq_num_, it->second.send_at_seq_num)) {
+      nack_batch.emplace_back(it->second.seq_num);
+      ++it->second.retries;
+      it->second.sent_at_time = now_ms;
+      if (it->second.retries >= kMaxNackRetries) {
+        it = nack_list_.erase(it);
+      } else {
+        ++it;
+      }
+      continue;
+    }
+
+    if (consider_timestamp &&
+        it->second.sent_at_time + rtt_ms_ <= now_ms) {
+      nack_batch.emplace_back(it->second.seq_num);
+      ++it->second.retries;
+      it->second.sent_at_time = now_ms;
+      if (it->second.retries >= kMaxNackRetries) {
+        it = nack_list_.erase(it);
+      } else {
+        ++it;
+      }
+      continue;
+    }
+    ++it;
+  }
+  return nack_batch;
+}
+
+void NackModule::UpdateReorderingStatistics(uint16_t seq_num) {
+  RTC_DCHECK(AheadOf(last_seq_num_, seq_num));
+
+  int remove_from_bucket = reordering_occurences_[reordering_index_];
+  if (remove_from_bucket != -1)
+    reordering_buckets_[remove_from_bucket] -= 1;
+
+  uint16_t diff = ReverseDiff(last_seq_num_, seq_num);
+  uint16_t add_to_bucket =
+      std::min(static_cast<uint16_t>(kNumReorderingBuckets - 1),
+               static_cast<uint16_t>(diff - 1));
+  reordering_buckets_[add_to_bucket] += 1;
+  if (reordering_occurences_[reordering_index_] == -1)
+    ++reordering_count_;
+  reordering_occurences_[reordering_index_] = add_to_bucket;
+  reordering_index_ = Add<kMaxReorderedPackets>(reordering_index_, 1);
+}
+
+int NackModule::WaitNumberOfPackets(float probability) const {
+  RTC_DCHECK_GE(probability, 0.f);
+  RTC_DCHECK_LE(probability, 1.f);
+
+  // Until there are enough values we default to 0. Also
+  // protect against divide by zero later in the code.
+  if (reordering_count_ < 20)
+    return 0;
+
+  int bucket = 0;
+  float accumulated_probability = 0;
+  while (accumulated_probability < probability &&
+         bucket < kNumReorderingBuckets) {
+    accumulated_probability +=
+        static_cast<float>(reordering_buckets_[bucket]) / reordering_count_;
+    ++bucket;
+  }
+  return bucket + 1;
+}
+
+}  // namespace webrtc