src/third_party/webrtc/modules/video_coding/main/source/jitter_buffer.cc

   1 /*
   2  *  Copyright (c) 2012 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 #include "webrtc/modules/video_coding/main/source/jitter_buffer.h"
  11
  12 #include <assert.h>
  13
  14 #include <algorithm>
  15 #include <utility>
  16
  17 #include "webrtc/modules/video_coding/main/interface/video_coding.h"
  18 #include "webrtc/modules/video_coding/main/source/frame_buffer.h"
  19 #include "webrtc/modules/video_coding/main/source/inter_frame_delay.h"
  20 #include "webrtc/modules/video_coding/main/source/internal_defines.h"
  21 #include "webrtc/modules/video_coding/main/source/jitter_buffer_common.h"
  22 #include "webrtc/modules/video_coding/main/source/jitter_estimator.h"
  23 #include "webrtc/modules/video_coding/main/source/packet.h"
  24 #include "webrtc/system_wrappers/interface/clock.h"
  25 #include "webrtc/system_wrappers/interface/critical_section_wrapper.h"
  26 #include "webrtc/system_wrappers/interface/event_wrapper.h"
  27 #include "webrtc/system_wrappers/interface/logging.h"
  28 #include "webrtc/system_wrappers/interface/metrics.h"
  29 #include "webrtc/system_wrappers/interface/trace_event.h"
  30
  31 namespace webrtc {
  32
  33 // Use this rtt if no value has been reported.
  34 static const uint32_t kDefaultRtt = 200;
  35
  36 typedef std::pair<uint32_t, VCMFrameBuffer*> FrameListPair;
  37
  38 bool IsKeyFrame(FrameListPair pair) {
  39   return pair.second->FrameType() == kVideoFrameKey;
  40 }
  41
  42 bool HasNonEmptyState(FrameListPair pair) {
  43   return pair.second->GetState() != kStateEmpty;
  44 }
  45
  46 void FrameList::InsertFrame(VCMFrameBuffer* frame) {
  47   insert(rbegin().base(), FrameListPair(frame->TimeStamp(), frame));
  48 }
  49
  50 VCMFrameBuffer* FrameList::FindFrame(uint32_t timestamp) const {
  51   FrameList::const_iterator it = find(timestamp);
  52   if (it == end())
  53     return NULL;
  54   return it->second;
  55 }
  56
  57 VCMFrameBuffer* FrameList::PopFrame(uint32_t timestamp) {
  58   FrameList::iterator it = find(timestamp);
  59   if (it == end())
  60     return NULL;
  61   VCMFrameBuffer* frame = it->second;
  62   erase(it);
  63   return frame;
  64 }
  65
  66 VCMFrameBuffer* FrameList::Front() const {
  67   return begin()->second;
  68 }
  69
  70 VCMFrameBuffer* FrameList::Back() const {
  71   return rbegin()->second;
  72 }
  73
  74 int FrameList::RecycleFramesUntilKeyFrame(FrameList::iterator* key_frame_it,
  75                                           UnorderedFrameList* free_frames) {
  76   int drop_count = 0;
  77   FrameList::iterator it = begin();
  78   while (!empty()) {
  79     // Throw at least one frame.
  80     it->second->Reset();
  81     free_frames->push_back(it->second);
  82     erase(it++);
  83     ++drop_count;
  84     if (it != end() && it->second->FrameType() == kVideoFrameKey) {
  85       *key_frame_it = it;
  86       return drop_count;
  87     }
  88   }
  89   *key_frame_it = end();
  90   return drop_count;
  91 }
  92
  93 int FrameList::CleanUpOldOrEmptyFrames(VCMDecodingState* decoding_state,
  94                                        UnorderedFrameList* free_frames) {
  95   int drop_count = 0;
  96   while (!empty()) {
  97     VCMFrameBuffer* oldest_frame = Front();
  98     bool remove_frame = false;
  99     if (oldest_frame->GetState() == kStateEmpty && size() > 1) {
 100       // This frame is empty, try to update the last decoded state and drop it
 101       // if successful.
 102       remove_frame = decoding_state->UpdateEmptyFrame(oldest_frame);
 103     } else {
 104       remove_frame = decoding_state->IsOldFrame(oldest_frame);
 105     }
 106     if (!remove_frame) {
 107       break;
 108     }
 109     free_frames->push_back(oldest_frame);
 110     ++drop_count;
 111     TRACE_EVENT_INSTANT1("webrtc", "JB::OldOrEmptyFrameDropped", "timestamp",
 112                          oldest_frame->TimeStamp());
 113     erase(begin());
 114   }
 115   return drop_count;
 116 }
 117
 118 void FrameList::Reset(UnorderedFrameList* free_frames) {
 119   while (!empty()) {
 120     begin()->second->Reset();
 121     free_frames->push_back(begin()->second);
 122     erase(begin());
 123   }
 124 }
 125
 126 VCMJitterBuffer::VCMJitterBuffer(Clock* clock, EventFactory* event_factory)
 127     : clock_(clock),
 128       running_(false),
 129       crit_sect_(CriticalSectionWrapper::CreateCriticalSection()),
 130       frame_event_(event_factory->CreateEvent()),
 131       packet_event_(event_factory->CreateEvent()),
 132       max_number_of_frames_(kStartNumberOfFrames),
 133       frame_buffers_(),
 134       free_frames_(),
 135       decodable_frames_(),
 136       incomplete_frames_(),
 137       last_decoded_state_(),
 138       first_packet_since_reset_(true),
 139       incoming_frame_rate_(0),
 140       incoming_frame_count_(0),
 141       time_last_incoming_frame_count_(0),
 142       incoming_bit_count_(0),
 143       incoming_bit_rate_(0),
 144       drop_count_(0),
 145       num_consecutive_old_frames_(0),
 146       num_consecutive_old_packets_(0),
 147       num_packets_(0),
 148       num_duplicated_packets_(0),
 149       num_discarded_packets_(0),
 150       jitter_estimate_(clock),
 151       inter_frame_delay_(clock_->TimeInMilliseconds()),
 152       rtt_ms_(kDefaultRtt),
 153       nack_mode_(kNoNack),
 154       low_rtt_nack_threshold_ms_(-1),
 155       high_rtt_nack_threshold_ms_(-1),
 156       missing_sequence_numbers_(SequenceNumberLessThan()),
 157       nack_seq_nums_(),
 158       max_nack_list_size_(0),
 159       max_packet_age_to_nack_(0),
 160       max_incomplete_time_ms_(0),
 161       decode_error_mode_(kNoErrors),
 162       average_packets_per_frame_(0.0f),
 163       frame_counter_(0) {
 164   memset(frame_buffers_, 0, sizeof(frame_buffers_));
 165
 166   for (int i = 0; i < kStartNumberOfFrames; i++) {
 167     frame_buffers_[i] = new VCMFrameBuffer();
 168     free_frames_.push_back(frame_buffers_[i]);
 169   }
 170 }
 171
 172 VCMJitterBuffer::~VCMJitterBuffer() {
 173   Stop();
 174   for (int i = 0; i < kMaxNumberOfFrames; i++) {
 175     if (frame_buffers_[i]) {
 176       delete frame_buffers_[i];
 177     }
 178   }
 179   delete crit_sect_;
 180 }
 181
 182 void VCMJitterBuffer::CopyFrom(const VCMJitterBuffer& rhs) {
 183   if (this != &rhs) {
 184     crit_sect_->Enter();
 185     rhs.crit_sect_->Enter();
 186     running_ = rhs.running_;
 187     max_number_of_frames_ = rhs.max_number_of_frames_;
 188     incoming_frame_rate_ = rhs.incoming_frame_rate_;
 189     incoming_frame_count_ = rhs.incoming_frame_count_;
 190     time_last_incoming_frame_count_ = rhs.time_last_incoming_frame_count_;
 191     incoming_bit_count_ = rhs.incoming_bit_count_;
 192     incoming_bit_rate_ = rhs.incoming_bit_rate_;
 193     drop_count_ = rhs.drop_count_;
 194     num_consecutive_old_frames_ = rhs.num_consecutive_old_frames_;
 195     num_consecutive_old_packets_ = rhs.num_consecutive_old_packets_;
 196     num_packets_ = rhs.num_packets_;
 197     num_duplicated_packets_ = rhs.num_duplicated_packets_;
 198     num_discarded_packets_ = rhs.num_discarded_packets_;
 199     jitter_estimate_ = rhs.jitter_estimate_;
 200     inter_frame_delay_ = rhs.inter_frame_delay_;
 201     waiting_for_completion_ = rhs.waiting_for_completion_;
 202     rtt_ms_ = rhs.rtt_ms_;
 203     first_packet_since_reset_ = rhs.first_packet_since_reset_;
 204     last_decoded_state_ =  rhs.last_decoded_state_;
 205     decode_error_mode_ = rhs.decode_error_mode_;
 206     assert(max_nack_list_size_ == rhs.max_nack_list_size_);
 207     assert(max_packet_age_to_nack_ == rhs.max_packet_age_to_nack_);
 208     assert(max_incomplete_time_ms_ == rhs.max_incomplete_time_ms_);
 209     receive_statistics_ = rhs.receive_statistics_;
 210     nack_seq_nums_.resize(rhs.nack_seq_nums_.size());
 211     missing_sequence_numbers_ = rhs.missing_sequence_numbers_;
 212     latest_received_sequence_number_ = rhs.latest_received_sequence_number_;
 213     average_packets_per_frame_ = rhs.average_packets_per_frame_;
 214     for (int i = 0; i < kMaxNumberOfFrames; i++) {
 215       if (frame_buffers_[i] != NULL) {
 216         delete frame_buffers_[i];
 217         frame_buffers_[i] = NULL;
 218       }
 219     }
 220     free_frames_.clear();
 221     decodable_frames_.clear();
 222     incomplete_frames_.clear();
 223     int i = 0;
 224     for (UnorderedFrameList::const_iterator it = rhs.free_frames_.begin();
 225          it != rhs.free_frames_.end(); ++it, ++i) {
 226       frame_buffers_[i] = new VCMFrameBuffer;
 227       free_frames_.push_back(frame_buffers_[i]);
 228     }
 229     CopyFrames(&decodable_frames_, rhs.decodable_frames_, &i);
 230     CopyFrames(&incomplete_frames_, rhs.incomplete_frames_, &i);
 231     rhs.crit_sect_->Leave();
 232     crit_sect_->Leave();
 233   }
 234 }
 235
 236 void VCMJitterBuffer::CopyFrames(FrameList* to_list,
 237     const FrameList& from_list, int* index) {
 238   to_list->clear();
 239   for (FrameList::const_iterator it = from_list.begin();
 240        it != from_list.end(); ++it, ++*index) {
 241     frame_buffers_[*index] = new VCMFrameBuffer(*it->second);
 242     to_list->InsertFrame(frame_buffers_[*index]);
 243   }
 244 }
 245
 246 void VCMJitterBuffer::UpdateHistograms() {
 247   if (num_packets_ > 0) {
 248     RTC_HISTOGRAM_PERCENTAGE("WebRTC.Video.DiscardedPacketsInPercent",
 249         num_discarded_packets_ * 100 / num_packets_);
 250     RTC_HISTOGRAM_PERCENTAGE("WebRTC.Video.DuplicatedPacketsInPercent",
 251         num_duplicated_packets_ * 100 / num_packets_);
 252   }
 253 }
 254
 255 void VCMJitterBuffer::Start() {
 256   CriticalSectionScoped cs(crit_sect_);
 257   running_ = true;
 258   incoming_frame_count_ = 0;
 259   incoming_frame_rate_ = 0;
 260   incoming_bit_count_ = 0;
 261   incoming_bit_rate_ = 0;
 262   time_last_incoming_frame_count_ = clock_->TimeInMilliseconds();
 263   receive_statistics_.clear();
 264
 265   num_consecutive_old_frames_ = 0;
 266   num_consecutive_old_packets_ = 0;
 267   num_packets_ = 0;
 268   num_duplicated_packets_ = 0;
 269   num_discarded_packets_ = 0;
 270
 271   // Start in a non-signaled state.
 272   frame_event_->Reset();
 273   packet_event_->Reset();
 274   waiting_for_completion_.frame_size = 0;
 275   waiting_for_completion_.timestamp = 0;
 276   waiting_for_completion_.latest_packet_time = -1;
 277   first_packet_since_reset_ = true;
 278   rtt_ms_ = kDefaultRtt;
 279   last_decoded_state_.Reset();
 280 }
 281
 282 void VCMJitterBuffer::Stop() {
 283   crit_sect_->Enter();
 284   UpdateHistograms();
 285   running_ = false;
 286   last_decoded_state_.Reset();
 287   free_frames_.clear();
 288   decodable_frames_.clear();
 289   incomplete_frames_.clear();
 290   // Make sure all frames are reset and free.
 291   for (int i = 0; i < kMaxNumberOfFrames; i++) {
 292     if (frame_buffers_[i] != NULL) {
 293       static_cast<VCMFrameBuffer*>(frame_buffers_[i])->Reset();
 294       free_frames_.push_back(frame_buffers_[i]);
 295     }
 296   }
 297   crit_sect_->Leave();
 298   // Make sure we wake up any threads waiting on these events.
 299   frame_event_->Set();
 300   packet_event_->Set();
 301 }
 302
 303 bool VCMJitterBuffer::Running() const {
 304   CriticalSectionScoped cs(crit_sect_);
 305   return running_;
 306 }
 307
 308 void VCMJitterBuffer::Flush() {
 309   CriticalSectionScoped cs(crit_sect_);
 310   decodable_frames_.Reset(&free_frames_);
 311   incomplete_frames_.Reset(&free_frames_);
 312   last_decoded_state_.Reset();  // TODO(mikhal): sync reset.
 313   frame_event_->Reset();
 314   packet_event_->Reset();
 315   num_consecutive_old_frames_ = 0;
 316   num_consecutive_old_packets_ = 0;
 317   // Also reset the jitter and delay estimates
 318   jitter_estimate_.Reset();
 319   inter_frame_delay_.Reset(clock_->TimeInMilliseconds());
 320   waiting_for_completion_.frame_size = 0;
 321   waiting_for_completion_.timestamp = 0;
 322   waiting_for_completion_.latest_packet_time = -1;
 323   first_packet_since_reset_ = true;
 324   missing_sequence_numbers_.clear();
 325 }
 326
 327 // Get received key and delta frames
 328 std::map<FrameType, uint32_t> VCMJitterBuffer::FrameStatistics() const {
 329   CriticalSectionScoped cs(crit_sect_);
 330   return receive_statistics_;
 331 }
 332
 333 int VCMJitterBuffer::num_packets() const {
 334   CriticalSectionScoped cs(crit_sect_);
 335   return num_packets_;
 336 }
 337
 338 int VCMJitterBuffer::num_duplicated_packets() const {
 339   CriticalSectionScoped cs(crit_sect_);
 340   return num_duplicated_packets_;
 341 }
 342
 343 int VCMJitterBuffer::num_discarded_packets() const {
 344   CriticalSectionScoped cs(crit_sect_);
 345   return num_discarded_packets_;
 346 }
 347
 348 // Calculate framerate and bitrate.
 349 void VCMJitterBuffer::IncomingRateStatistics(unsigned int* framerate,
 350                                              unsigned int* bitrate) {
 351   assert(framerate);
 352   assert(bitrate);
 353   CriticalSectionScoped cs(crit_sect_);
 354   const int64_t now = clock_->TimeInMilliseconds();
 355   int64_t diff = now - time_last_incoming_frame_count_;
 356   if (diff < 1000 && incoming_frame_rate_ > 0 && incoming_bit_rate_ > 0) {
 357     // Make sure we report something even though less than
 358     // 1 second has passed since last update.
 359     *framerate = incoming_frame_rate_;
 360     *bitrate = incoming_bit_rate_;
 361   } else if (incoming_frame_count_ != 0) {
 362     // We have received frame(s) since last call to this function
 363
 364     // Prepare calculations
 365     if (diff <= 0) {
 366       diff = 1;
 367     }
 368     // we add 0.5f for rounding
 369     float rate = 0.5f + ((incoming_frame_count_ * 1000.0f) / diff);
 370     if (rate < 1.0f) {
 371       rate = 1.0f;
 372     }
 373
 374     // Calculate frame rate
 375     // Let r be rate.
 376     // r(0) = 1000*framecount/delta_time.
 377     // (I.e. frames per second since last calculation.)
 378     // frame_rate = r(0)/2 + r(-1)/2
 379     // (I.e. fr/s average this and the previous calculation.)
 380     *framerate = (incoming_frame_rate_ + static_cast<unsigned int>(rate)) / 2;
 381     incoming_frame_rate_ = static_cast<unsigned int>(rate);
 382
 383     // Calculate bit rate
 384     if (incoming_bit_count_ == 0) {
 385       *bitrate = 0;
 386     } else {
 387       *bitrate = 10 * ((100 * incoming_bit_count_) /
 388                        static_cast<unsigned int>(diff));
 389     }
 390     incoming_bit_rate_ = *bitrate;
 391
 392     // Reset count
 393     incoming_frame_count_ = 0;
 394     incoming_bit_count_ = 0;
 395     time_last_incoming_frame_count_ = now;
 396
 397   } else {
 398     // No frames since last call
 399     time_last_incoming_frame_count_ = clock_->TimeInMilliseconds();
 400     *framerate = 0;
 401     *bitrate = 0;
 402     incoming_frame_rate_ = 0;
 403     incoming_bit_rate_ = 0;
 404   }
 405 }
 406
 407 // Answers the question:
 408 // Will the packet sequence be complete if the next frame is grabbed for
 409 // decoding right now? That is, have we lost a frame between the last decoded
 410 // frame and the next, or is the next
 411 // frame missing one or more packets?
 412 bool VCMJitterBuffer::CompleteSequenceWithNextFrame() {
 413   CriticalSectionScoped cs(crit_sect_);
 414   // Finding oldest frame ready for decoder, check sequence number and size
 415   CleanUpOldOrEmptyFrames();
 416   if (!decodable_frames_.empty()) {
 417     if (decodable_frames_.Front()->GetState() == kStateComplete) {
 418       return true;
 419     }
 420   } else if (incomplete_frames_.size() <= 1) {
 421     // Frame not ready to be decoded.
 422     return true;
 423   }
 424   return false;
 425 }
 426
 427 // Returns immediately or a |max_wait_time_ms| ms event hang waiting for a
 428 // complete frame, |max_wait_time_ms| decided by caller.
 429 bool VCMJitterBuffer::NextCompleteTimestamp(
 430     uint32_t max_wait_time_ms, uint32_t* timestamp) {
 431   crit_sect_->Enter();
 432   if (!running_) {
 433     crit_sect_->Leave();
 434     return false;
 435   }
 436   CleanUpOldOrEmptyFrames();
 437
 438   if (decodable_frames_.empty() ||
 439       decodable_frames_.Front()->GetState() != kStateComplete) {
 440     const int64_t end_wait_time_ms = clock_->TimeInMilliseconds() +
 441         max_wait_time_ms;
 442     int64_t wait_time_ms = max_wait_time_ms;
 443     while (wait_time_ms > 0) {
 444       crit_sect_->Leave();
 445       const EventTypeWrapper ret =
 446         frame_event_->Wait(static_cast<uint32_t>(wait_time_ms));
 447       crit_sect_->Enter();
 448       if (ret == kEventSignaled) {
 449         // Are we shutting down the jitter buffer?
 450         if (!running_) {
 451           crit_sect_->Leave();
 452           return false;
 453         }
 454         // Finding oldest frame ready for decoder.
 455         CleanUpOldOrEmptyFrames();
 456         if (decodable_frames_.empty() ||
 457             decodable_frames_.Front()->GetState() != kStateComplete) {
 458           wait_time_ms = end_wait_time_ms - clock_->TimeInMilliseconds();
 459         } else {
 460           break;
 461         }
 462       } else {
 463         break;
 464       }
 465     }
 466     // Inside |crit_sect_|.
 467   } else {
 468     // We already have a frame, reset the event.
 469     frame_event_->Reset();
 470   }
 471   if (decodable_frames_.empty() ||
 472       decodable_frames_.Front()->GetState() != kStateComplete) {
 473     crit_sect_->Leave();
 474     return false;
 475   }
 476   *timestamp = decodable_frames_.Front()->TimeStamp();
 477   crit_sect_->Leave();
 478   return true;
 479 }
 480
 481 bool VCMJitterBuffer::NextMaybeIncompleteTimestamp(uint32_t* timestamp) {
 482   CriticalSectionScoped cs(crit_sect_);
 483   if (!running_) {
 484     return false;
 485   }
 486   if (decode_error_mode_ == kNoErrors) {
 487     // No point to continue, as we are not decoding with errors.
 488     return false;
 489   }
 490
 491   CleanUpOldOrEmptyFrames();
 492
 493   if (decodable_frames_.empty()) {
 494     return false;
 495   }
 496   VCMFrameBuffer* oldest_frame = decodable_frames_.Front();
 497   // If we have exactly one frame in the buffer, release it only if it is
 498   // complete. We know decodable_frames_ is  not empty due to the previous
 499   // check.
 500   if (decodable_frames_.size() == 1 && incomplete_frames_.empty()
 501       && oldest_frame->GetState() != kStateComplete) {
 502     return false;
 503   }
 504
 505   *timestamp = oldest_frame->TimeStamp();
 506   return true;
 507 }
 508
 509 VCMEncodedFrame* VCMJitterBuffer::ExtractAndSetDecode(uint32_t timestamp) {
 510   CriticalSectionScoped cs(crit_sect_);
 511   if (!running_) {
 512     return NULL;
 513   }
 514   // Extract the frame with the desired timestamp.
 515   VCMFrameBuffer* frame = decodable_frames_.PopFrame(timestamp);
 516   bool continuous = true;
 517   if (!frame) {
 518     frame = incomplete_frames_.PopFrame(timestamp);
 519     if (frame)
 520       continuous = last_decoded_state_.ContinuousFrame(frame);
 521     else
 522       return NULL;
 523   }
 524   TRACE_EVENT_ASYNC_STEP0("webrtc", "Video", timestamp, "Extract");
 525   // Frame pulled out from jitter buffer, update the jitter estimate.
 526   const bool retransmitted = (frame->GetNackCount() > 0);
 527   if (retransmitted) {
 528     jitter_estimate_.FrameNacked();
 529   } else if (frame->Length() > 0) {
 530     // Ignore retransmitted and empty frames.
 531     if (waiting_for_completion_.latest_packet_time >= 0) {
 532       UpdateJitterEstimate(waiting_for_completion_, true);
 533     }
 534     if (frame->GetState() == kStateComplete) {
 535       UpdateJitterEstimate(*frame, false);
 536     } else {
 537       // Wait for this one to get complete.
 538       waiting_for_completion_.frame_size = frame->Length();
 539       waiting_for_completion_.latest_packet_time =
 540           frame->LatestPacketTimeMs();
 541       waiting_for_completion_.timestamp = frame->TimeStamp();
 542     }
 543   }
 544
 545   // The state must be changed to decoding before cleaning up zero sized
 546   // frames to avoid empty frames being cleaned up and then given to the
 547   // decoder. Propagates the missing_frame bit.
 548   frame->PrepareForDecode(continuous);
 549
 550   // We have a frame - update the last decoded state and nack list.
 551   last_decoded_state_.SetState(frame);
 552   DropPacketsFromNackList(last_decoded_state_.sequence_num());
 553
 554   if ((*frame).IsSessionComplete())
 555     UpdateAveragePacketsPerFrame(frame->NumPackets());
 556
 557   return frame;
 558 }
 559
 560 // Release frame when done with decoding. Should never be used to release
 561 // frames from within the jitter buffer.
 562 void VCMJitterBuffer::ReleaseFrame(VCMEncodedFrame* frame) {
 563   CriticalSectionScoped cs(crit_sect_);
 564   VCMFrameBuffer* frame_buffer = static_cast<VCMFrameBuffer*>(frame);
 565   if (frame_buffer) {
 566     free_frames_.push_back(frame_buffer);
 567   }
 568 }
 569
 570 // Gets frame to use for this timestamp. If no match, get empty frame.
 571 VCMFrameBufferEnum VCMJitterBuffer::GetFrame(const VCMPacket& packet,
 572                                              VCMFrameBuffer** frame) {
 573   ++num_packets_;
 574   // Does this packet belong to an old frame?
 575   if (last_decoded_state_.IsOldPacket(&packet)) {
 576     // Account only for media packets.
 577     if (packet.sizeBytes > 0) {
 578       num_discarded_packets_++;
 579       num_consecutive_old_packets_++;
 580     }
 581     // Update last decoded sequence number if the packet arrived late and
 582     // belongs to a frame with a timestamp equal to the last decoded
 583     // timestamp.
 584     last_decoded_state_.UpdateOldPacket(&packet);
 585     DropPacketsFromNackList(last_decoded_state_.sequence_num());
 586
 587     if (num_consecutive_old_packets_ > kMaxConsecutiveOldPackets) {
 588       LOG(LS_WARNING) << num_consecutive_old_packets_ << " consecutive old "
 589                          "packets received. Flushing the jitter buffer.";
 590       Flush();
 591       return kFlushIndicator;
 592     }
 593     return kOldPacket;
 594   }
 595   num_consecutive_old_packets_ = 0;
 596
 597   *frame = incomplete_frames_.FindFrame(packet.timestamp);
 598   if (*frame)
 599     return kNoError;
 600   *frame = decodable_frames_.FindFrame(packet.timestamp);
 601   if (*frame)
 602     return kNoError;
 603
 604   // No match, return empty frame.
 605   *frame = GetEmptyFrame();
 606   VCMFrameBufferEnum ret = kNoError;
 607   if (!*frame) {
 608     // No free frame! Try to reclaim some...
 609     LOG(LS_WARNING) << "Unable to get empty frame; Recycling.";
 610     bool found_key_frame = RecycleFramesUntilKeyFrame();
 611     *frame = GetEmptyFrame();
 612     assert(*frame);
 613     if (!found_key_frame) {
 614       ret = kFlushIndicator;
 615     }
 616   }
 617   (*frame)->Reset();
 618   return ret;
 619 }
 620
 621 int64_t VCMJitterBuffer::LastPacketTime(const VCMEncodedFrame* frame,
 622                                         bool* retransmitted) const {
 623   assert(retransmitted);
 624   CriticalSectionScoped cs(crit_sect_);
 625   const VCMFrameBuffer* frame_buffer =
 626       static_cast<const VCMFrameBuffer*>(frame);
 627   *retransmitted = (frame_buffer->GetNackCount() > 0);
 628   return frame_buffer->LatestPacketTimeMs();
 629 }
 630
 631 VCMFrameBufferEnum VCMJitterBuffer::InsertPacket(const VCMPacket& packet,
 632                                                  bool* retransmitted) {
 633   CriticalSectionScoped cs(crit_sect_);
 634
 635   VCMFrameBuffer* frame = NULL;
 636   const VCMFrameBufferEnum error = GetFrame(packet, &frame);
 637   if (error != kNoError && frame == NULL) {
 638     return error;
 639   }
 640   int64_t now_ms = clock_->TimeInMilliseconds();
 641   // We are keeping track of the first and latest seq numbers, and
 642   // the number of wraps to be able to calculate how many packets we expect.
 643   if (first_packet_since_reset_) {
 644     // Now it's time to start estimating jitter
 645     // reset the delay estimate.
 646     inter_frame_delay_.Reset(now_ms);
 647   }
 648   if (last_decoded_state_.IsOldPacket(&packet)) {
 649     // This packet belongs to an old, already decoded frame, we want to update
 650     // the last decoded sequence number.
 651     last_decoded_state_.UpdateOldPacket(&packet);
 652     drop_count_++;
 653     // Flush if this happens consistently.
 654     num_consecutive_old_frames_++;
 655     if (num_consecutive_old_frames_ > kMaxConsecutiveOldFrames) {
 656       LOG(LS_WARNING) << num_consecutive_old_packets_ << " consecutive old "
 657                          "frames received. Flushing the jitter buffer.";
 658       Flush();
 659       return kFlushIndicator;
 660     }
 661     return kNoError;
 662   }
 663
 664   num_consecutive_old_frames_ = 0;
 665
 666   // Empty packets may bias the jitter estimate (lacking size component),
 667   // therefore don't let empty packet trigger the following updates:
 668   if (packet.frameType != kFrameEmpty) {
 669     if (waiting_for_completion_.timestamp == packet.timestamp) {
 670       // This can get bad if we have a lot of duplicate packets,
 671       // we will then count some packet multiple times.
 672       waiting_for_completion_.frame_size += packet.sizeBytes;
 673       waiting_for_completion_.latest_packet_time = now_ms;
 674     } else if (waiting_for_completion_.latest_packet_time >= 0 &&
 675                waiting_for_completion_.latest_packet_time + 2000 <= now_ms) {
 676       // A packet should never be more than two seconds late
 677       UpdateJitterEstimate(waiting_for_completion_, true);
 678       waiting_for_completion_.latest_packet_time = -1;
 679       waiting_for_completion_.frame_size = 0;
 680       waiting_for_completion_.timestamp = 0;
 681     }
 682   }
 683
 684   VCMFrameBufferStateEnum previous_state = frame->GetState();
 685   // Insert packet.
 686   // Check for first packet. High sequence number will be -1 if neither an empty
 687   // packet nor a media packet has been inserted.
 688   bool first = (frame->GetHighSeqNum() == -1);
 689   FrameData frame_data;
 690   frame_data.rtt_ms = rtt_ms_;
 691   frame_data.rolling_average_packets_per_frame = average_packets_per_frame_;
 692   VCMFrameBufferEnum buffer_return = frame->InsertPacket(packet,
 693                                                          now_ms,
 694                                                          decode_error_mode_,
 695                                                          frame_data);
 696   if (!frame->GetCountedFrame()) {
 697     TRACE_EVENT_ASYNC_BEGIN1("webrtc", "Video", frame->TimeStamp(),
 698                              "timestamp", frame->TimeStamp());
 699   }
 700
 701   if (buffer_return > 0) {
 702     incoming_bit_count_ += packet.sizeBytes << 3;
 703     if (first_packet_since_reset_) {
 704       latest_received_sequence_number_ = packet.seqNum;
 705       first_packet_since_reset_ = false;
 706     } else {
 707       if (IsPacketRetransmitted(packet)) {
 708         frame->IncrementNackCount();
 709       }
 710       if (!UpdateNackList(packet.seqNum) &&
 711           packet.frameType != kVideoFrameKey) {
 712         buffer_return = kFlushIndicator;
 713       }
 714       latest_received_sequence_number_ = LatestSequenceNumber(
 715           latest_received_sequence_number_, packet.seqNum);
 716     }
 717   }
 718
 719   // Is the frame already in the decodable list?
 720   bool update_decodable_list = (previous_state != kStateDecodable &&
 721       previous_state != kStateComplete);
 722   bool continuous = IsContinuous(*frame);
 723   switch (buffer_return) {
 724     case kGeneralError:
 725     case kTimeStampError:
 726     case kSizeError: {
 727       // This frame will be cleaned up later from the frame list.
 728       frame->Reset();
 729       break;
 730     }
 731     case kCompleteSession: {
 732       if (update_decodable_list) {
 733         CountFrame(*frame);
 734         frame->SetCountedFrame(true);
 735         if (continuous) {
 736           // Signal that we have a complete session.
 737           frame_event_->Set();
 738         }
 739       }
 740     }
 741     // Note: There is no break here - continuing to kDecodableSession.
 742     case kDecodableSession: {
 743       *retransmitted = (frame->GetNackCount() > 0);
 744       // Signal that we have a received packet.
 745       packet_event_->Set();
 746       if (!update_decodable_list) {
 747         break;
 748       }
 749       if (continuous) {
 750         if (!first) {
 751           incomplete_frames_.PopFrame(packet.timestamp);
 752         }
 753         decodable_frames_.InsertFrame(frame);
 754         FindAndInsertContinuousFrames(*frame);
 755       } else if (first) {
 756         incomplete_frames_.InsertFrame(frame);
 757       }
 758       break;
 759     }
 760     case kIncomplete: {
 761       // No point in storing empty continuous frames.
 762       if (frame->GetState() == kStateEmpty &&
 763           last_decoded_state_.UpdateEmptyFrame(frame)) {
 764         free_frames_.push_back(frame);
 765         frame->Reset();
 766         frame = NULL;
 767         return kNoError;
 768       } else if (first) {
 769         incomplete_frames_.InsertFrame(frame);
 770       }
 771       // Signal that we have received a packet.
 772       packet_event_->Set();
 773       break;
 774     }
 775     case kNoError:
 776     case kOutOfBoundsPacket:
 777     case kDuplicatePacket: {
 778       ++num_duplicated_packets_;
 779       break;
 780     }
 781     case kFlushIndicator:
 782       return kFlushIndicator;
 783     default: {
 784       assert(false && "JitterBuffer::InsertPacket: Undefined value");
 785     }
 786   }
 787   return buffer_return;
 788 }
 789
 790 bool VCMJitterBuffer::IsContinuousInState(const VCMFrameBuffer& frame,
 791     const VCMDecodingState& decoding_state) const {
 792   if (decode_error_mode_ == kWithErrors)
 793     return true;
 794   // Is this frame (complete or decodable) and continuous?
 795   // kStateDecodable will never be set when decode_error_mode_ is false
 796   // as SessionInfo determines this state based on the error mode (and frame
 797   // completeness).
 798   if ((frame.GetState() == kStateComplete ||
 799        frame.GetState() == kStateDecodable) &&
 800        decoding_state.ContinuousFrame(&frame)) {
 801     return true;
 802   } else {
 803     return false;
 804   }
 805 }
 806
 807 bool VCMJitterBuffer::IsContinuous(const VCMFrameBuffer& frame) const {
 808   if (IsContinuousInState(frame, last_decoded_state_)) {
 809     return true;
 810   }
 811   VCMDecodingState decoding_state;
 812   decoding_state.CopyFrom(last_decoded_state_);
 813   for (FrameList::const_iterator it = decodable_frames_.begin();
 814        it != decodable_frames_.end(); ++it)  {
 815     VCMFrameBuffer* decodable_frame = it->second;
 816     if (IsNewerTimestamp(decodable_frame->TimeStamp(), frame.TimeStamp())) {
 817       break;
 818     }
 819     decoding_state.SetState(decodable_frame);
 820     if (IsContinuousInState(frame, decoding_state)) {
 821       return true;
 822     }
 823   }
 824   return false;
 825 }
 826
 827 void VCMJitterBuffer::FindAndInsertContinuousFrames(
 828     const VCMFrameBuffer& new_frame) {
 829   VCMDecodingState decoding_state;
 830   decoding_state.CopyFrom(last_decoded_state_);
 831   decoding_state.SetState(&new_frame);
 832   // When temporal layers are available, we search for a complete or decodable
 833   // frame until we hit one of the following:
 834   // 1. Continuous base or sync layer.
 835   // 2. The end of the list was reached.
 836   for (FrameList::iterator it = incomplete_frames_.begin();
 837        it != incomplete_frames_.end();)  {
 838     VCMFrameBuffer* frame = it->second;
 839     if (IsNewerTimestamp(new_frame.TimeStamp(), frame->TimeStamp())) {
 840       ++it;
 841       continue;
 842     }
 843     if (IsContinuousInState(*frame, decoding_state)) {
 844       decodable_frames_.InsertFrame(frame);
 845       incomplete_frames_.erase(it++);
 846       decoding_state.SetState(frame);
 847     } else if (frame->TemporalId() <= 0) {
 848       break;
 849     } else {
 850       ++it;
 851     }
 852   }
 853 }
 854
 855 uint32_t VCMJitterBuffer::EstimatedJitterMs() {
 856   CriticalSectionScoped cs(crit_sect_);
 857   // Compute RTT multiplier for estimation.
 858   // low_rtt_nackThresholdMs_ == -1 means no FEC.
 859   double rtt_mult = 1.0f;
 860   if (low_rtt_nack_threshold_ms_ >= 0 &&
 861       static_cast<int>(rtt_ms_) >= low_rtt_nack_threshold_ms_) {
 862     // For RTTs above low_rtt_nack_threshold_ms_ we don't apply extra delay
 863     // when waiting for retransmissions.
 864     rtt_mult = 0.0f;
 865   }
 866   return jitter_estimate_.GetJitterEstimate(rtt_mult);
 867 }
 868
 869 void VCMJitterBuffer::UpdateRtt(uint32_t rtt_ms) {
 870   CriticalSectionScoped cs(crit_sect_);
 871   rtt_ms_ = rtt_ms;
 872   jitter_estimate_.UpdateRtt(rtt_ms);
 873 }
 874
 875 void VCMJitterBuffer::SetNackMode(VCMNackMode mode,
 876                                   int low_rtt_nack_threshold_ms,
 877                                   int high_rtt_nack_threshold_ms) {
 878   CriticalSectionScoped cs(crit_sect_);
 879   nack_mode_ = mode;
 880   if (mode == kNoNack) {
 881     missing_sequence_numbers_.clear();
 882   }
 883   assert(low_rtt_nack_threshold_ms >= -1 && high_rtt_nack_threshold_ms >= -1);
 884   assert(high_rtt_nack_threshold_ms == -1 ||
 885          low_rtt_nack_threshold_ms <= high_rtt_nack_threshold_ms);
 886   assert(low_rtt_nack_threshold_ms > -1 || high_rtt_nack_threshold_ms == -1);
 887   low_rtt_nack_threshold_ms_ = low_rtt_nack_threshold_ms;
 888   high_rtt_nack_threshold_ms_ = high_rtt_nack_threshold_ms;
 889   // Don't set a high start rtt if high_rtt_nack_threshold_ms_ is used, to not
 890   // disable NACK in hybrid mode.
 891   if (rtt_ms_ == kDefaultRtt && high_rtt_nack_threshold_ms_ != -1) {
 892     rtt_ms_ = 0;
 893   }
 894   if (!WaitForRetransmissions()) {
 895     jitter_estimate_.ResetNackCount();
 896   }
 897 }
 898
 899 void VCMJitterBuffer::SetNackSettings(size_t max_nack_list_size,
 900                                       int max_packet_age_to_nack,
 901                                       int max_incomplete_time_ms) {
 902   CriticalSectionScoped cs(crit_sect_);
 903   assert(max_packet_age_to_nack >= 0);
 904   assert(max_incomplete_time_ms_ >= 0);
 905   max_nack_list_size_ = max_nack_list_size;
 906   max_packet_age_to_nack_ = max_packet_age_to_nack;
 907   max_incomplete_time_ms_ = max_incomplete_time_ms;
 908   nack_seq_nums_.resize(max_nack_list_size_);
 909 }
 910
 911 VCMNackMode VCMJitterBuffer::nack_mode() const {
 912   CriticalSectionScoped cs(crit_sect_);
 913   return nack_mode_;
 914 }
 915
 916 int VCMJitterBuffer::NonContinuousOrIncompleteDuration() {
 917   if (incomplete_frames_.empty()) {
 918     return 0;
 919   }
 920   uint32_t start_timestamp = incomplete_frames_.Front()->TimeStamp();
 921   if (!decodable_frames_.empty()) {
 922     start_timestamp = decodable_frames_.Back()->TimeStamp();
 923   }
 924   return incomplete_frames_.Back()->TimeStamp() - start_timestamp;
 925 }
 926
 927 uint16_t VCMJitterBuffer::EstimatedLowSequenceNumber(
 928     const VCMFrameBuffer& frame) const {
 929   assert(frame.GetLowSeqNum() >= 0);
 930   if (frame.HaveFirstPacket())
 931     return frame.GetLowSeqNum();
 932
 933   // This estimate is not accurate if more than one packet with lower sequence
 934   // number is lost.
 935   return frame.GetLowSeqNum() - 1;
 936 }
 937
 938 uint16_t* VCMJitterBuffer::GetNackList(uint16_t* nack_list_size,
 939                                        bool* request_key_frame) {
 940   CriticalSectionScoped cs(crit_sect_);
 941   *request_key_frame = false;
 942   if (nack_mode_ == kNoNack) {
 943     *nack_list_size = 0;
 944     return NULL;
 945   }
 946   if (last_decoded_state_.in_initial_state()) {
 947     VCMFrameBuffer* next_frame =  NextFrame();
 948     const bool first_frame_is_key = next_frame &&
 949         next_frame->FrameType() == kVideoFrameKey &&
 950         next_frame->HaveFirstPacket();
 951     if (!first_frame_is_key) {
 952       bool have_non_empty_frame = decodable_frames_.end() != find_if(
 953           decodable_frames_.begin(), decodable_frames_.end(),
 954           HasNonEmptyState);
 955       if (!have_non_empty_frame) {
 956         have_non_empty_frame = incomplete_frames_.end() != find_if(
 957             incomplete_frames_.begin(), incomplete_frames_.end(),
 958             HasNonEmptyState);
 959       }
 960       bool found_key_frame = RecycleFramesUntilKeyFrame();
 961       if (!found_key_frame) {
 962         *request_key_frame = have_non_empty_frame;
 963         *nack_list_size = 0;
 964         return NULL;
 965       }
 966     }
 967   }
 968   if (TooLargeNackList()) {
 969     *request_key_frame = !HandleTooLargeNackList();
 970   }
 971   if (max_incomplete_time_ms_ > 0) {
 972     int non_continuous_incomplete_duration =
 973         NonContinuousOrIncompleteDuration();
 974     if (non_continuous_incomplete_duration > 90 * max_incomplete_time_ms_) {
 975       LOG_F(LS_WARNING) << "Too long non-decodable duration: "
 976                         << non_continuous_incomplete_duration << " > "
 977                         << 90 * max_incomplete_time_ms_;
 978       FrameList::reverse_iterator rit = find_if(incomplete_frames_.rbegin(),
 979           incomplete_frames_.rend(), IsKeyFrame);
 980       if (rit == incomplete_frames_.rend()) {
 981         // Request a key frame if we don't have one already.
 982         *request_key_frame = true;
 983         *nack_list_size = 0;
 984         return NULL;
 985       } else {
 986         // Skip to the last key frame. If it's incomplete we will start
 987         // NACKing it.
 988         // Note that the estimated low sequence number is correct for VP8
 989         // streams because only the first packet of a key frame is marked.
 990         last_decoded_state_.Reset();
 991         DropPacketsFromNackList(EstimatedLowSequenceNumber(*rit->second));
 992       }
 993     }
 994   }
 995   unsigned int i = 0;
 996   SequenceNumberSet::iterator it = missing_sequence_numbers_.begin();
 997   for (; it != missing_sequence_numbers_.end(); ++it, ++i) {
 998     nack_seq_nums_[i] = *it;
 999   }
1000   *nack_list_size = i;
1001   return &nack_seq_nums_[0];
1002 }
1003
1004 void VCMJitterBuffer::SetDecodeErrorMode(VCMDecodeErrorMode error_mode) {
1005   CriticalSectionScoped cs(crit_sect_);
1006   decode_error_mode_ = error_mode;
1007 }
1008
1009 VCMFrameBuffer* VCMJitterBuffer::NextFrame() const {
1010   if (!decodable_frames_.empty())
1011     return decodable_frames_.Front();
1012   if (!incomplete_frames_.empty())
1013     return incomplete_frames_.Front();
1014   return NULL;
1015 }
1016
1017 bool VCMJitterBuffer::UpdateNackList(uint16_t sequence_number) {
1018   if (nack_mode_ == kNoNack) {
1019     return true;
1020   }
1021   // Make sure we don't add packets which are already too old to be decoded.
1022   if (!last_decoded_state_.in_initial_state()) {
1023     latest_received_sequence_number_ = LatestSequenceNumber(
1024         latest_received_sequence_number_,
1025         last_decoded_state_.sequence_num());
1026   }
1027   if (IsNewerSequenceNumber(sequence_number,
1028                             latest_received_sequence_number_)) {
1029     // Push any missing sequence numbers to the NACK list.
1030     for (uint16_t i = latest_received_sequence_number_ + 1;
1031          IsNewerSequenceNumber(sequence_number, i); ++i) {
1032       missing_sequence_numbers_.insert(missing_sequence_numbers_.end(), i);
1033       TRACE_EVENT_INSTANT1("webrtc", "AddNack", "seqnum", i);
1034     }
1035     if (TooLargeNackList() && !HandleTooLargeNackList()) {
1036       LOG(LS_WARNING) << "Requesting key frame due to too large NACK list.";
1037       return false;
1038     }
1039     if (MissingTooOldPacket(sequence_number) &&
1040         !HandleTooOldPackets(sequence_number)) {
1041       LOG(LS_WARNING) << "Requesting key frame due to missing too old packets";
1042       return false;
1043     }
1044   } else {
1045     missing_sequence_numbers_.erase(sequence_number);
1046     TRACE_EVENT_INSTANT1("webrtc", "RemoveNack", "seqnum", sequence_number);
1047   }
1048   return true;
1049 }
1050
1051 bool VCMJitterBuffer::TooLargeNackList() const {
1052   return missing_sequence_numbers_.size() > max_nack_list_size_;
1053 }
1054
1055 bool VCMJitterBuffer::HandleTooLargeNackList() {
1056   // Recycle frames until the NACK list is small enough. It is likely cheaper to
1057   // request a key frame than to retransmit this many missing packets.
1058   LOG_F(LS_WARNING) << "NACK list has grown too large: "
1059                     << missing_sequence_numbers_.size() << " > "
1060                     << max_nack_list_size_;
1061   bool key_frame_found = false;
1062   while (TooLargeNackList()) {
1063     key_frame_found = RecycleFramesUntilKeyFrame();
1064   }
1065   return key_frame_found;
1066 }
1067
1068 bool VCMJitterBuffer::MissingTooOldPacket(
1069     uint16_t latest_sequence_number) const {
1070   if (missing_sequence_numbers_.empty()) {
1071     return false;
1072   }
1073   const uint16_t age_of_oldest_missing_packet = latest_sequence_number -
1074       *missing_sequence_numbers_.begin();
1075   // Recycle frames if the NACK list contains too old sequence numbers as
1076   // the packets may have already been dropped by the sender.
1077   return age_of_oldest_missing_packet > max_packet_age_to_nack_;
1078 }
1079
1080 bool VCMJitterBuffer::HandleTooOldPackets(uint16_t latest_sequence_number) {
1081   bool key_frame_found = false;
1082   const uint16_t age_of_oldest_missing_packet = latest_sequence_number -
1083       *missing_sequence_numbers_.begin();
1084   LOG_F(LS_WARNING) << "NACK list contains too old sequence numbers: "
1085                     << age_of_oldest_missing_packet << " > "
1086                     << max_packet_age_to_nack_;
1087   while (MissingTooOldPacket(latest_sequence_number)) {
1088     key_frame_found = RecycleFramesUntilKeyFrame();
1089   }
1090   return key_frame_found;
1091 }
1092
1093 void VCMJitterBuffer::DropPacketsFromNackList(
1094     uint16_t last_decoded_sequence_number) {
1095   // Erase all sequence numbers from the NACK list which we won't need any
1096   // longer.
1097   missing_sequence_numbers_.erase(missing_sequence_numbers_.begin(),
1098                                   missing_sequence_numbers_.upper_bound(
1099                                       last_decoded_sequence_number));
1100 }
1101
1102 int64_t VCMJitterBuffer::LastDecodedTimestamp() const {
1103   CriticalSectionScoped cs(crit_sect_);
1104   return last_decoded_state_.time_stamp();
1105 }
1106
1107 void VCMJitterBuffer::RenderBufferSize(uint32_t* timestamp_start,
1108                                        uint32_t* timestamp_end) {
1109   CriticalSectionScoped cs(crit_sect_);
1110   CleanUpOldOrEmptyFrames();
1111   *timestamp_start = 0;
1112   *timestamp_end = 0;
1113   if (decodable_frames_.empty()) {
1114     return;
1115   }
1116   *timestamp_start = decodable_frames_.Front()->TimeStamp();
1117   *timestamp_end = decodable_frames_.Back()->TimeStamp();
1118 }
1119
1120 VCMFrameBuffer* VCMJitterBuffer::GetEmptyFrame() {
1121   if (free_frames_.empty()) {
1122     if (!TryToIncreaseJitterBufferSize()) {
1123       return NULL;
1124     }
1125   }
1126   VCMFrameBuffer* frame = free_frames_.front();
1127   free_frames_.pop_front();
1128   return frame;
1129 }
1130
1131 bool VCMJitterBuffer::TryToIncreaseJitterBufferSize() {
1132   if (max_number_of_frames_ >= kMaxNumberOfFrames)
1133     return false;
1134   VCMFrameBuffer* new_frame = new VCMFrameBuffer();
1135   frame_buffers_[max_number_of_frames_] = new_frame;
1136   free_frames_.push_back(new_frame);
1137   ++max_number_of_frames_;
1138   TRACE_COUNTER1("webrtc", "JBMaxFrames", max_number_of_frames_);
1139   return true;
1140 }
1141
1142 // Recycle oldest frames up to a key frame, used if jitter buffer is completely
1143 // full.
1144 bool VCMJitterBuffer::RecycleFramesUntilKeyFrame() {
1145   // First release incomplete frames, and only release decodable frames if there
1146   // are no incomplete ones.
1147   FrameList::iterator key_frame_it;
1148   bool key_frame_found = false;
1149   int dropped_frames = 0;
1150   dropped_frames += incomplete_frames_.RecycleFramesUntilKeyFrame(
1151       &key_frame_it, &free_frames_);
1152   key_frame_found = key_frame_it != incomplete_frames_.end();
1153   if (dropped_frames == 0) {
1154     dropped_frames += decodable_frames_.RecycleFramesUntilKeyFrame(
1155         &key_frame_it, &free_frames_);
1156     key_frame_found = key_frame_it != decodable_frames_.end();
1157   }
1158   drop_count_ += dropped_frames;
1159   TRACE_EVENT_INSTANT0("webrtc", "JB::RecycleFramesUntilKeyFrame");
1160   if (key_frame_found) {
1161     LOG(LS_INFO) << "Found key frame while dropping frames.";
1162     // Reset last decoded state to make sure the next frame decoded is a key
1163     // frame, and start NACKing from here.
1164     last_decoded_state_.Reset();
1165     DropPacketsFromNackList(EstimatedLowSequenceNumber(*key_frame_it->second));
1166   } else if (decodable_frames_.empty()) {
1167     // All frames dropped. Reset the decoding state and clear missing sequence
1168     // numbers as we're starting fresh.
1169     last_decoded_state_.Reset();
1170     missing_sequence_numbers_.clear();
1171   }
1172   return key_frame_found;
1173 }
1174
1175 // Must be called under the critical section |crit_sect_|.
1176 void VCMJitterBuffer::CountFrame(const VCMFrameBuffer& frame) {
1177   if (!frame.GetCountedFrame()) {
1178     // Ignore ACK frames.
1179     incoming_frame_count_++;
1180   }
1181
1182   if (frame.FrameType() == kVideoFrameKey) {
1183     TRACE_EVENT_ASYNC_STEP0("webrtc", "Video",
1184                             frame.TimeStamp(), "KeyComplete");
1185   } else {
1186     TRACE_EVENT_ASYNC_STEP0("webrtc", "Video",
1187                             frame.TimeStamp(), "DeltaComplete");
1188   }
1189
1190   // Update receive statistics. We count all layers, thus when you use layers
1191   // adding all key and delta frames might differ from frame count.
1192   if (frame.IsSessionComplete()) {
1193     ++receive_statistics_[frame.FrameType()];
1194   }
1195 }
1196
1197 void VCMJitterBuffer::UpdateAveragePacketsPerFrame(int current_number_packets) {
1198   if (frame_counter_ > kFastConvergeThreshold) {
1199     average_packets_per_frame_ = average_packets_per_frame_
1200               * (1 - kNormalConvergeMultiplier)
1201             + current_number_packets * kNormalConvergeMultiplier;
1202   } else if (frame_counter_ > 0) {
1203     average_packets_per_frame_ = average_packets_per_frame_
1204               * (1 - kFastConvergeMultiplier)
1205             + current_number_packets * kFastConvergeMultiplier;
1206     frame_counter_++;
1207   } else {
1208     average_packets_per_frame_ = current_number_packets;
1209     frame_counter_++;
1210   }
1211 }
1212
1213 // Must be called under the critical section |crit_sect_|.
1214 void VCMJitterBuffer::CleanUpOldOrEmptyFrames() {
1215   drop_count_ +=
1216       decodable_frames_.CleanUpOldOrEmptyFrames(&last_decoded_state_,
1217           &free_frames_);
1218   drop_count_ +=
1219       incomplete_frames_.CleanUpOldOrEmptyFrames(&last_decoded_state_,
1220           &free_frames_);
1221   if (!last_decoded_state_.in_initial_state()) {
1222     DropPacketsFromNackList(last_decoded_state_.sequence_num());
1223   }
1224 }
1225
1226 // Must be called from within |crit_sect_|.
1227 bool VCMJitterBuffer::IsPacketRetransmitted(const VCMPacket& packet) const {
1228   return missing_sequence_numbers_.find(packet.seqNum) !=
1229       missing_sequence_numbers_.end();
1230 }
1231
1232 // Must be called under the critical section |crit_sect_|. Should never be
1233 // called with retransmitted frames, they must be filtered out before this
1234 // function is called.
1235 void VCMJitterBuffer::UpdateJitterEstimate(const VCMJitterSample& sample,
1236                                            bool incomplete_frame) {
1237   if (sample.latest_packet_time == -1) {
1238     return;
1239   }
1240   UpdateJitterEstimate(sample.latest_packet_time, sample.timestamp,
1241                        sample.frame_size, incomplete_frame);
1242 }
1243
1244 // Must be called under the critical section crit_sect_. Should never be
1245 // called with retransmitted frames, they must be filtered out before this
1246 // function is called.
1247 void VCMJitterBuffer::UpdateJitterEstimate(const VCMFrameBuffer& frame,
1248                                            bool incomplete_frame) {
1249   if (frame.LatestPacketTimeMs() == -1) {
1250     return;
1251   }
1252   // No retransmitted frames should be a part of the jitter
1253   // estimate.
1254   UpdateJitterEstimate(frame.LatestPacketTimeMs(), frame.TimeStamp(),
1255                        frame.Length(), incomplete_frame);
1256 }
1257
1258 // Must be called under the critical section |crit_sect_|. Should never be
1259 // called with retransmitted frames, they must be filtered out before this
1260 // function is called.
1261 void VCMJitterBuffer::UpdateJitterEstimate(
1262     int64_t latest_packet_time_ms,
1263     uint32_t timestamp,
1264     unsigned int frame_size,
1265     bool incomplete_frame) {
1266   if (latest_packet_time_ms == -1) {
1267     return;
1268   }
1269   int64_t frame_delay;
1270   bool not_reordered = inter_frame_delay_.CalculateDelay(timestamp,
1271                                                       &frame_delay,
1272                                                       latest_packet_time_ms);
1273   // Filter out frames which have been reordered in time by the network
1274   if (not_reordered) {
1275     // Update the jitter estimate with the new samples
1276     jitter_estimate_.UpdateEstimate(frame_delay, frame_size, incomplete_frame);
1277   }
1278 }
1279
1280 bool VCMJitterBuffer::WaitForRetransmissions() {
1281   if (nack_mode_ == kNoNack) {
1282     // NACK disabled -> don't wait for retransmissions.
1283     return false;
1284   }
1285   // Evaluate if the RTT is higher than |high_rtt_nack_threshold_ms_|, and in
1286   // that case we don't wait for retransmissions.
1287   if (high_rtt_nack_threshold_ms_ >= 0 &&
1288       rtt_ms_ >= static_cast<unsigned int>(high_rtt_nack_threshold_ms_)) {
1289     return false;
1290   }
1291   return true;
1292 }
1293 }  // namespace webrtc