Home | History | Annotate | Download | only in acm2 
      1 /*
      2  *  Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
      3  *
      4  *  Use of this source code is governed by a BSD-style license
      5  *  that can be found in the LICENSE file in the root of the source
      6  *  tree. An additional intellectual property rights grant can be found
      7  *  in the file PATENTS.  All contributing project authors may
      8  *  be found in the AUTHORS file in the root of the source tree.
      9  */
     10 
     11 #include "webrtc/modules/audio_coding/main/acm2/nack.h"
     12 
     13 #include <assert.h>  // For assert.
     14 
     15 #include <algorithm>  // For std::max.
     16 
     17 #include "webrtc/modules/interface/module_common_types.h"
     18 #include "webrtc/system_wrappers/interface/logging.h"
     19 
     20 namespace webrtc {
     21 
     22 namespace acm2 {
     23 
     24 namespace {
     25 
     26 const int kDefaultSampleRateKhz = 48;
     27 const int kDefaultPacketSizeMs = 20;
     28 
     29 }  // namespace
     30 
     31 Nack::Nack(int nack_threshold_packets)
     32     : nack_threshold_packets_(nack_threshold_packets),
     33       sequence_num_last_received_rtp_(0),
     34       timestamp_last_received_rtp_(0),
     35       any_rtp_received_(false),
     36       sequence_num_last_decoded_rtp_(0),
     37       timestamp_last_decoded_rtp_(0),
     38       any_rtp_decoded_(false),
     39       sample_rate_khz_(kDefaultSampleRateKhz),
     40       samples_per_packet_(sample_rate_khz_ * kDefaultPacketSizeMs),
     41       max_nack_list_size_(kNackListSizeLimit) {}
     42 
     43 Nack* Nack::Create(int nack_threshold_packets) {
     44   return new Nack(nack_threshold_packets);
     45 }
     46 
     47 void Nack::UpdateSampleRate(int sample_rate_hz) {
     48   assert(sample_rate_hz > 0);
     49   sample_rate_khz_ = sample_rate_hz / 1000;
     50 }
     51 
     52 void Nack::UpdateLastReceivedPacket(uint16_t sequence_number,
     53                                     uint32_t timestamp) {
     54   // Just record the value of sequence number and timestamp if this is the
     55   // first packet.
     56   if (!any_rtp_received_) {
     57     sequence_num_last_received_rtp_ = sequence_number;
     58     timestamp_last_received_rtp_ = timestamp;
     59     any_rtp_received_ = true;
     60     // If no packet is decoded, to have a reasonable estimate of time-to-play
     61     // use the given values.
     62     if (!any_rtp_decoded_) {
     63       sequence_num_last_decoded_rtp_ = sequence_number;
     64       timestamp_last_decoded_rtp_ = timestamp;
     65     }
     66     return;
     67   }
     68 
     69   if (sequence_number == sequence_num_last_received_rtp_)
     70     return;
     71 
     72   // Received RTP should not be in the list.
     73   nack_list_.erase(sequence_number);
     74 
     75   // If this is an old sequence number, no more action is required, return.
     76   if (IsNewerSequenceNumber(sequence_num_last_received_rtp_, sequence_number))
     77     return;
     78 
     79   UpdateSamplesPerPacket(sequence_number, timestamp);
     80 
     81   UpdateList(sequence_number);
     82 
     83   sequence_num_last_received_rtp_ = sequence_number;
     84   timestamp_last_received_rtp_ = timestamp;
     85   LimitNackListSize();
     86 }
     87 
     88 void Nack::UpdateSamplesPerPacket(uint16_t sequence_number_current_received_rtp,
     89                                   uint32_t timestamp_current_received_rtp) {
     90   uint32_t timestamp_increase = timestamp_current_received_rtp -
     91       timestamp_last_received_rtp_;
     92   uint16_t sequence_num_increase = sequence_number_current_received_rtp -
     93       sequence_num_last_received_rtp_;
     94 
     95   samples_per_packet_ = timestamp_increase / sequence_num_increase;
     96 }
     97 
     98 void Nack::UpdateList(uint16_t sequence_number_current_received_rtp) {
     99   // Some of the packets which were considered late, now are considered missing.
    100   ChangeFromLateToMissing(sequence_number_current_received_rtp);
    101 
    102   if (IsNewerSequenceNumber(sequence_number_current_received_rtp,
    103                             sequence_num_last_received_rtp_ + 1))
    104     AddToList(sequence_number_current_received_rtp);
    105 }
    106 
    107 void Nack::ChangeFromLateToMissing(
    108     uint16_t sequence_number_current_received_rtp) {
    109   NackList::const_iterator lower_bound = nack_list_.lower_bound(
    110       static_cast<uint16_t>(sequence_number_current_received_rtp -
    111                             nack_threshold_packets_));
    112 
    113   for (NackList::iterator it = nack_list_.begin(); it != lower_bound; ++it)
    114     it->second.is_missing = true;
    115 }
    116 
    117 uint32_t Nack::EstimateTimestamp(uint16_t sequence_num) {
    118   uint16_t sequence_num_diff = sequence_num - sequence_num_last_received_rtp_;
    119   return sequence_num_diff * samples_per_packet_ + timestamp_last_received_rtp_;
    120 }
    121 
    122 void Nack::AddToList(uint16_t sequence_number_current_received_rtp) {
    123   assert(!any_rtp_decoded_ || IsNewerSequenceNumber(
    124       sequence_number_current_received_rtp, sequence_num_last_decoded_rtp_));
    125 
    126   // Packets with sequence numbers older than |upper_bound_missing| are
    127   // considered missing, and the rest are considered late.
    128   uint16_t upper_bound_missing = sequence_number_current_received_rtp -
    129       nack_threshold_packets_;
    130 
    131   for (uint16_t n = sequence_num_last_received_rtp_ + 1;
    132       IsNewerSequenceNumber(sequence_number_current_received_rtp, n); ++n) {
    133     bool is_missing = IsNewerSequenceNumber(upper_bound_missing, n);
    134     uint32_t timestamp = EstimateTimestamp(n);
    135     NackElement nack_element(TimeToPlay(timestamp), timestamp, is_missing);
    136     nack_list_.insert(nack_list_.end(), std::make_pair(n, nack_element));
    137   }
    138 }
    139 
    140 void Nack::UpdateEstimatedPlayoutTimeBy10ms() {
    141   while (!nack_list_.empty() &&
    142       nack_list_.begin()->second.time_to_play_ms <= 10)
    143     nack_list_.erase(nack_list_.begin());
    144 
    145   for (NackList::iterator it = nack_list_.begin(); it != nack_list_.end(); ++it)
    146     it->second.time_to_play_ms -= 10;
    147 }
    148 
    149 void Nack::UpdateLastDecodedPacket(uint16_t sequence_number,
    150                                    uint32_t timestamp) {
    151   if (IsNewerSequenceNumber(sequence_number, sequence_num_last_decoded_rtp_) ||
    152       !any_rtp_decoded_) {
    153     sequence_num_last_decoded_rtp_ = sequence_number;
    154     timestamp_last_decoded_rtp_ = timestamp;
    155     // Packets in the list with sequence numbers less than the
    156     // sequence number of the decoded RTP should be removed from the lists.
    157     // They will be discarded by the jitter buffer if they arrive.
    158     nack_list_.erase(nack_list_.begin(), nack_list_.upper_bound(
    159         sequence_num_last_decoded_rtp_));
    160 
    161     // Update estimated time-to-play.
    162     for (NackList::iterator it = nack_list_.begin(); it != nack_list_.end();
    163         ++it)
    164       it->second.time_to_play_ms = TimeToPlay(it->second.estimated_timestamp);
    165   } else {
    166     assert(sequence_number == sequence_num_last_decoded_rtp_);
    167 
    168     // Same sequence number as before. 10 ms is elapsed, update estimations for
    169     // time-to-play.
    170     UpdateEstimatedPlayoutTimeBy10ms();
    171 
    172     // Update timestamp for better estimate of time-to-play, for packets which
    173     // are added to NACK list later on.
    174     timestamp_last_decoded_rtp_ += sample_rate_khz_ * 10;
    175   }
    176   any_rtp_decoded_ = true;
    177 }
    178 
    179 Nack::NackList Nack::GetNackList() const {
    180   return nack_list_;
    181 }
    182 
    183 void Nack::Reset() {
    184   nack_list_.clear();
    185 
    186   sequence_num_last_received_rtp_ = 0;
    187   timestamp_last_received_rtp_ = 0;
    188   any_rtp_received_ = false;
    189   sequence_num_last_decoded_rtp_ = 0;
    190   timestamp_last_decoded_rtp_ = 0;
    191   any_rtp_decoded_ = false;
    192   sample_rate_khz_ = kDefaultSampleRateKhz;
    193   samples_per_packet_ = sample_rate_khz_ * kDefaultPacketSizeMs;
    194 }
    195 
    196 int Nack::SetMaxNackListSize(size_t max_nack_list_size) {
    197   if (max_nack_list_size == 0 || max_nack_list_size > kNackListSizeLimit)
    198     return -1;
    199   max_nack_list_size_ = max_nack_list_size;
    200   LimitNackListSize();
    201   return 0;
    202 }
    203 
    204 void Nack::LimitNackListSize() {
    205   uint16_t limit = sequence_num_last_received_rtp_ -
    206       static_cast<uint16_t>(max_nack_list_size_) - 1;
    207   nack_list_.erase(nack_list_.begin(), nack_list_.upper_bound(limit));
    208 }
    209 
    210 int Nack::TimeToPlay(uint32_t timestamp) const {
    211   uint32_t timestamp_increase = timestamp - timestamp_last_decoded_rtp_;
    212   return timestamp_increase / sample_rate_khz_;
    213 }
    214 
    215 // We don't erase elements with time-to-play shorter than round-trip-time.
    216 std::vector<uint16_t> Nack::GetNackList(int round_trip_time_ms) const {
    217   std::vector<uint16_t> sequence_numbers;
    218   for (NackList::const_iterator it = nack_list_.begin(); it != nack_list_.end();
    219       ++it) {
    220     if (it->second.is_missing &&
    221         it->second.time_to_play_ms > round_trip_time_ms)
    222       sequence_numbers.push_back(it->first);
    223   }
    224   return sequence_numbers;
    225 }
    226 
    227 }  // namespace acm2
    228 
    229 }  // namespace webrtc
    230