media/filters/source_buffer_range.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "media/filters/source_buffer_range.h"
   6
   7 #include <algorithm>
   8
   9 namespace media {
  10
  11 // Comparison operators for std::upper_bound() and std::lower_bound().
  12 static bool CompareTimeDeltaToStreamParserBuffer(
  13     const DecodeTimestamp& decode_timestamp,
  14     const scoped_refptr<StreamParserBuffer>& buffer) {
  15   return decode_timestamp < buffer->GetDecodeTimestamp();
  16 }
  17 static bool CompareStreamParserBufferToTimeDelta(
  18     const scoped_refptr<StreamParserBuffer>& buffer,
  19     const DecodeTimestamp& decode_timestamp) {
  20   return buffer->GetDecodeTimestamp() < decode_timestamp;
  21 }
  22
  23 bool SourceBufferRange::AllowSameTimestamp(
  24     bool prev_is_keyframe, bool current_is_keyframe) {
  25   return prev_is_keyframe || !current_is_keyframe;
  26 }
  27
  28 SourceBufferRange::SourceBufferRange(
  29     GapPolicy gap_policy, const BufferQueue& new_buffers,
  30     DecodeTimestamp media_segment_start_time,
  31     const InterbufferDistanceCB& interbuffer_distance_cb)
  32     : gap_policy_(gap_policy),
  33       keyframe_map_index_base_(0),
  34       next_buffer_index_(-1),
  35       media_segment_start_time_(media_segment_start_time),
  36       interbuffer_distance_cb_(interbuffer_distance_cb),
  37       size_in_bytes_(0) {
  38   CHECK(!new_buffers.empty());
  39   DCHECK(new_buffers.front()->is_key_frame());
  40   DCHECK(!interbuffer_distance_cb.is_null());
  41   AppendBuffersToEnd(new_buffers);
  42 }
  43
  44 SourceBufferRange::~SourceBufferRange() {}
  45
  46 void SourceBufferRange::AppendBuffersToEnd(const BufferQueue& new_buffers) {
  47   DCHECK(buffers_.empty() || CanAppendBuffersToEnd(new_buffers));
  48   DCHECK(media_segment_start_time_ == kNoDecodeTimestamp() ||
  49          media_segment_start_time_ <=
  50              new_buffers.front()->GetDecodeTimestamp());
  51
  52   AdjustEstimatedDurationForNewAppend(new_buffers);
  53
  54   for (BufferQueue::const_iterator itr = new_buffers.begin();
  55        itr != new_buffers.end();
  56        ++itr) {
  57     DCHECK((*itr)->GetDecodeTimestamp() != kNoDecodeTimestamp());
  58     buffers_.push_back(*itr);
  59     DCHECK_GE((*itr)->data_size(), 0);
  60     size_in_bytes_ += (*itr)->data_size();
  61
  62     if ((*itr)->is_key_frame()) {
  63       keyframe_map_.insert(
  64           std::make_pair((*itr)->GetDecodeTimestamp(),
  65                          buffers_.size() - 1 + keyframe_map_index_base_));
  66     }
  67   }
  68 }
  69
  70 void SourceBufferRange::AdjustEstimatedDurationForNewAppend(
  71     const BufferQueue& new_buffers) {
  72   if (buffers_.empty() || new_buffers.empty()) {
  73     return;
  74   }
  75
  76   // If the last of the previously appended buffers contains estimated duration,
  77   // we now refine that estimate by taking the PTS delta from the first new
  78   // buffer being appended.
  79   const auto& last_appended_buffer = buffers_.back();
  80   if (last_appended_buffer->is_duration_estimated()) {
  81     base::TimeDelta timestamp_delta =
  82         new_buffers.front()->timestamp() - last_appended_buffer->timestamp();
  83     DCHECK(timestamp_delta > base::TimeDelta());
  84     if (last_appended_buffer->duration() != timestamp_delta) {
  85       DVLOG(1) << "Replacing estimated duration ("
  86                << last_appended_buffer->duration()
  87                << ") from previous range-end with derived duration ("
  88                << timestamp_delta << ").";
  89       last_appended_buffer->set_duration(timestamp_delta);
  90     }
  91   }
  92 }
  93
  94 void SourceBufferRange::Seek(DecodeTimestamp timestamp) {
  95   DCHECK(CanSeekTo(timestamp));
  96   DCHECK(!keyframe_map_.empty());
  97
  98   KeyframeMap::iterator result = GetFirstKeyframeAtOrBefore(timestamp);
  99   next_buffer_index_ = result->second - keyframe_map_index_base_;
 100   DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
 101 }
 102
 103 void SourceBufferRange::SeekAheadTo(DecodeTimestamp timestamp) {
 104   SeekAhead(timestamp, false);
 105 }
 106
 107 void SourceBufferRange::SeekAheadPast(DecodeTimestamp timestamp) {
 108   SeekAhead(timestamp, true);
 109 }
 110
 111 void SourceBufferRange::SeekAhead(DecodeTimestamp timestamp,
 112                                   bool skip_given_timestamp) {
 113   DCHECK(!keyframe_map_.empty());
 114
 115   KeyframeMap::iterator result =
 116       GetFirstKeyframeAt(timestamp, skip_given_timestamp);
 117
 118   // If there isn't a keyframe after |timestamp|, then seek to end and return
 119   // kNoTimestamp to signal such.
 120   if (result == keyframe_map_.end()) {
 121     next_buffer_index_ = -1;
 122     return;
 123   }
 124   next_buffer_index_ = result->second - keyframe_map_index_base_;
 125   DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
 126 }
 127
 128 void SourceBufferRange::SeekToStart() {
 129   DCHECK(!buffers_.empty());
 130   next_buffer_index_ = 0;
 131 }
 132
 133 SourceBufferRange* SourceBufferRange::SplitRange(DecodeTimestamp timestamp) {
 134   CHECK(!buffers_.empty());
 135
 136   // Find the first keyframe at or after |timestamp|.
 137   KeyframeMap::iterator new_beginning_keyframe =
 138       GetFirstKeyframeAt(timestamp, false);
 139
 140   // If there is no keyframe after |timestamp|, we can't split the range.
 141   if (new_beginning_keyframe == keyframe_map_.end())
 142     return NULL;
 143
 144   // Remove the data beginning at |keyframe_index| from |buffers_| and save it
 145   // into |removed_buffers|.
 146   int keyframe_index =
 147       new_beginning_keyframe->second - keyframe_map_index_base_;
 148   DCHECK_LT(keyframe_index, static_cast<int>(buffers_.size()));
 149   BufferQueue::iterator starting_point = buffers_.begin() + keyframe_index;
 150   BufferQueue removed_buffers(starting_point, buffers_.end());
 151
 152   DecodeTimestamp new_range_start_timestamp = kNoDecodeTimestamp();
 153   if (GetStartTimestamp() < buffers_.front()->GetDecodeTimestamp() &&
 154       timestamp < removed_buffers.front()->GetDecodeTimestamp()) {
 155     // The split is in the gap between |media_segment_start_time_| and
 156     // the first buffer of the new range so we should set the start
 157     // time of the new range to |timestamp| so we preserve part of the
 158     // gap in the new range.
 159     new_range_start_timestamp = timestamp;
 160   }
 161
 162   keyframe_map_.erase(new_beginning_keyframe, keyframe_map_.end());
 163   FreeBufferRange(starting_point, buffers_.end());
 164
 165   // Create a new range with |removed_buffers|.
 166   SourceBufferRange* split_range =
 167       new SourceBufferRange(
 168           gap_policy_, removed_buffers, new_range_start_timestamp,
 169           interbuffer_distance_cb_);
 170
 171   // If the next buffer position is now in |split_range|, update the state of
 172   // this range and |split_range| accordingly.
 173   if (next_buffer_index_ >= static_cast<int>(buffers_.size())) {
 174     split_range->next_buffer_index_ = next_buffer_index_ - keyframe_index;
 175     ResetNextBufferPosition();
 176   }
 177
 178   return split_range;
 179 }
 180
 181 SourceBufferRange::BufferQueue::iterator SourceBufferRange::GetBufferItrAt(
 182     DecodeTimestamp timestamp,
 183     bool skip_given_timestamp) {
 184   return skip_given_timestamp
 185              ? std::upper_bound(buffers_.begin(),
 186                                 buffers_.end(),
 187                                 timestamp,
 188                                 CompareTimeDeltaToStreamParserBuffer)
 189              : std::lower_bound(buffers_.begin(),
 190                                 buffers_.end(),
 191                                 timestamp,
 192                                 CompareStreamParserBufferToTimeDelta);
 193 }
 194
 195 SourceBufferRange::KeyframeMap::iterator
 196 SourceBufferRange::GetFirstKeyframeAt(DecodeTimestamp timestamp,
 197                                       bool skip_given_timestamp) {
 198   return skip_given_timestamp ?
 199       keyframe_map_.upper_bound(timestamp) :
 200       keyframe_map_.lower_bound(timestamp);
 201 }
 202
 203 SourceBufferRange::KeyframeMap::iterator
 204 SourceBufferRange::GetFirstKeyframeAtOrBefore(DecodeTimestamp timestamp) {
 205   KeyframeMap::iterator result = keyframe_map_.lower_bound(timestamp);
 206   // lower_bound() returns the first element >= |timestamp|, so we want the
 207   // previous element if it did not return the element exactly equal to
 208   // |timestamp|.
 209   if (result != keyframe_map_.begin() &&
 210       (result == keyframe_map_.end() || result->first != timestamp)) {
 211     --result;
 212   }
 213   return result;
 214 }
 215
 216 void SourceBufferRange::DeleteAll(BufferQueue* removed_buffers) {
 217   TruncateAt(buffers_.begin(), removed_buffers);
 218 }
 219
 220 bool SourceBufferRange::TruncateAt(
 221     DecodeTimestamp timestamp, BufferQueue* removed_buffers,
 222     bool is_exclusive) {
 223   // Find the place in |buffers_| where we will begin deleting data.
 224   BufferQueue::iterator starting_point =
 225       GetBufferItrAt(timestamp, is_exclusive);
 226   return TruncateAt(starting_point, removed_buffers);
 227 }
 228
 229 size_t SourceBufferRange::DeleteGOPFromFront(BufferQueue* deleted_buffers) {
 230   DCHECK(!FirstGOPContainsNextBufferPosition());
 231   DCHECK(deleted_buffers);
 232
 233   int buffers_deleted = 0;
 234   size_t total_bytes_deleted = 0;
 235
 236   KeyframeMap::iterator front = keyframe_map_.begin();
 237   DCHECK(front != keyframe_map_.end());
 238
 239   // Delete the keyframe at the start of |keyframe_map_|.
 240   keyframe_map_.erase(front);
 241
 242   // Now we need to delete all the buffers that depend on the keyframe we've
 243   // just deleted.
 244   int end_index = keyframe_map_.size() > 0 ?
 245       keyframe_map_.begin()->second - keyframe_map_index_base_ :
 246       buffers_.size();
 247
 248   // Delete buffers from the beginning of the buffered range up until (but not
 249   // including) the next keyframe.
 250   for (int i = 0; i < end_index; i++) {
 251     DCHECK_GE(buffers_.front()->data_size(), 0);
 252     size_t bytes_deleted = buffers_.front()->data_size();
 253     DCHECK_GE(size_in_bytes_, bytes_deleted);
 254     size_in_bytes_ -= bytes_deleted;
 255     total_bytes_deleted += bytes_deleted;
 256     deleted_buffers->push_back(buffers_.front());
 257     buffers_.pop_front();
 258     ++buffers_deleted;
 259   }
 260
 261   // Update |keyframe_map_index_base_| to account for the deleted buffers.
 262   keyframe_map_index_base_ += buffers_deleted;
 263
 264   if (next_buffer_index_ > -1) {
 265     next_buffer_index_ -= buffers_deleted;
 266     DCHECK_GE(next_buffer_index_, 0);
 267   }
 268
 269   // Invalidate media segment start time if we've deleted the first buffer of
 270   // the range.
 271   if (buffers_deleted > 0)
 272     media_segment_start_time_ = kNoDecodeTimestamp();
 273
 274   return total_bytes_deleted;
 275 }
 276
 277 size_t SourceBufferRange::DeleteGOPFromBack(BufferQueue* deleted_buffers) {
 278   DCHECK(!LastGOPContainsNextBufferPosition());
 279   DCHECK(deleted_buffers);
 280
 281   // Remove the last GOP's keyframe from the |keyframe_map_|.
 282   KeyframeMap::iterator back = keyframe_map_.end();
 283   DCHECK_GT(keyframe_map_.size(), 0u);
 284   --back;
 285
 286   // The index of the first buffer in the last GOP is equal to the new size of
 287   // |buffers_| after that GOP is deleted.
 288   size_t goal_size = back->second - keyframe_map_index_base_;
 289   keyframe_map_.erase(back);
 290
 291   size_t total_bytes_deleted = 0;
 292   while (buffers_.size() != goal_size) {
 293     DCHECK_GE(buffers_.back()->data_size(), 0);
 294     size_t bytes_deleted = buffers_.back()->data_size();
 295     DCHECK_GE(size_in_bytes_, bytes_deleted);
 296     size_in_bytes_ -= bytes_deleted;
 297     total_bytes_deleted += bytes_deleted;
 298     // We're removing buffers from the back, so push each removed buffer to the
 299     // front of |deleted_buffers| so that |deleted_buffers| are in nondecreasing
 300     // order.
 301     deleted_buffers->push_front(buffers_.back());
 302     buffers_.pop_back();
 303   }
 304
 305   return total_bytes_deleted;
 306 }
 307
 308 size_t SourceBufferRange::GetRemovalGOP(
 309     DecodeTimestamp start_timestamp, DecodeTimestamp end_timestamp,
 310     size_t total_bytes_to_free, DecodeTimestamp* removal_end_timestamp) {
 311   size_t bytes_removed = 0;
 312
 313   KeyframeMap::iterator gop_itr = GetFirstKeyframeAt(start_timestamp, false);
 314   if (gop_itr == keyframe_map_.end())
 315     return 0;
 316   int keyframe_index = gop_itr->second - keyframe_map_index_base_;
 317   BufferQueue::iterator buffer_itr = buffers_.begin() + keyframe_index;
 318   KeyframeMap::iterator gop_end = keyframe_map_.end();
 319   if (end_timestamp < GetBufferedEndTimestamp())
 320     gop_end = GetFirstKeyframeAtOrBefore(end_timestamp);
 321
 322   // Check if the removal range is within a GOP and skip the loop if so.
 323   // [keyframe]...[start_timestamp]...[end_timestamp]...[keyframe]
 324   KeyframeMap::iterator gop_itr_prev = gop_itr;
 325   if (gop_itr_prev != keyframe_map_.begin() && --gop_itr_prev == gop_end)
 326     gop_end = gop_itr;
 327
 328   while (gop_itr != gop_end && bytes_removed < total_bytes_to_free) {
 329     ++gop_itr;
 330
 331     size_t gop_size = 0;
 332     int next_gop_index = gop_itr == keyframe_map_.end() ?
 333         buffers_.size() : gop_itr->second - keyframe_map_index_base_;
 334     BufferQueue::iterator next_gop_start = buffers_.begin() + next_gop_index;
 335     for (; buffer_itr != next_gop_start; ++buffer_itr) {
 336       DCHECK_GE((*buffer_itr)->data_size(), 0);
 337       gop_size += (*buffer_itr)->data_size();
 338     }
 339
 340     bytes_removed += gop_size;
 341   }
 342   if (bytes_removed > 0) {
 343     *removal_end_timestamp = gop_itr == keyframe_map_.end() ?
 344         GetBufferedEndTimestamp() : gop_itr->first;
 345   }
 346   return bytes_removed;
 347 }
 348
 349 bool SourceBufferRange::FirstGOPEarlierThanMediaTime(
 350     DecodeTimestamp media_time) const {
 351   if (keyframe_map_.size() == 1u)
 352     return (GetEndTimestamp() < media_time);
 353
 354   KeyframeMap::const_iterator second_gop = keyframe_map_.begin();
 355   ++second_gop;
 356   return second_gop->first <= media_time;
 357 }
 358
 359 bool SourceBufferRange::FirstGOPContainsNextBufferPosition() const {
 360   if (!HasNextBufferPosition())
 361     return false;
 362
 363   // If there is only one GOP, it must contain the next buffer position.
 364   if (keyframe_map_.size() == 1u)
 365     return true;
 366
 367   KeyframeMap::const_iterator second_gop = keyframe_map_.begin();
 368   ++second_gop;
 369   return next_buffer_index_ < second_gop->second - keyframe_map_index_base_;
 370 }
 371
 372 bool SourceBufferRange::LastGOPContainsNextBufferPosition() const {
 373   if (!HasNextBufferPosition())
 374     return false;
 375
 376   // If there is only one GOP, it must contain the next buffer position.
 377   if (keyframe_map_.size() == 1u)
 378     return true;
 379
 380   KeyframeMap::const_iterator last_gop = keyframe_map_.end();
 381   --last_gop;
 382   return last_gop->second - keyframe_map_index_base_ <= next_buffer_index_;
 383 }
 384
 385 void SourceBufferRange::FreeBufferRange(
 386     const BufferQueue::iterator& starting_point,
 387     const BufferQueue::iterator& ending_point) {
 388   for (BufferQueue::iterator itr = starting_point;
 389        itr != ending_point; ++itr) {
 390     DCHECK_GE((*itr)->data_size(), 0);
 391     size_t itr_data_size = static_cast<size_t>((*itr)->data_size());
 392     DCHECK_GE(size_in_bytes_, itr_data_size);
 393     size_in_bytes_ -= itr_data_size;
 394   }
 395   buffers_.erase(starting_point, ending_point);
 396 }
 397
 398 bool SourceBufferRange::TruncateAt(
 399     const BufferQueue::iterator& starting_point, BufferQueue* removed_buffers) {
 400   DCHECK(!removed_buffers || removed_buffers->empty());
 401
 402   // Return if we're not deleting anything.
 403   if (starting_point == buffers_.end())
 404     return buffers_.empty();
 405
 406   // Reset the next buffer index if we will be deleting the buffer that's next
 407   // in sequence.
 408   if (HasNextBufferPosition()) {
 409     DecodeTimestamp next_buffer_timestamp = GetNextTimestamp();
 410     if (next_buffer_timestamp == kNoDecodeTimestamp() ||
 411         next_buffer_timestamp >= (*starting_point)->GetDecodeTimestamp()) {
 412       if (HasNextBuffer() && removed_buffers) {
 413         int starting_offset = starting_point - buffers_.begin();
 414         int next_buffer_offset = next_buffer_index_ - starting_offset;
 415         DCHECK_GE(next_buffer_offset, 0);
 416         BufferQueue saved(starting_point + next_buffer_offset, buffers_.end());
 417         removed_buffers->swap(saved);
 418       }
 419       ResetNextBufferPosition();
 420     }
 421   }
 422
 423   // Remove keyframes from |starting_point| onward.
 424   KeyframeMap::iterator starting_point_keyframe =
 425       keyframe_map_.lower_bound((*starting_point)->GetDecodeTimestamp());
 426   keyframe_map_.erase(starting_point_keyframe, keyframe_map_.end());
 427
 428   // Remove everything from |starting_point| onward.
 429   FreeBufferRange(starting_point, buffers_.end());
 430   return buffers_.empty();
 431 }
 432
 433 bool SourceBufferRange::GetNextBuffer(
 434     scoped_refptr<StreamParserBuffer>* out_buffer) {
 435   if (!HasNextBuffer())
 436     return false;
 437
 438   *out_buffer = buffers_[next_buffer_index_];
 439   next_buffer_index_++;
 440   return true;
 441 }
 442
 443 bool SourceBufferRange::HasNextBuffer() const {
 444   return next_buffer_index_ >= 0 &&
 445       next_buffer_index_ < static_cast<int>(buffers_.size());
 446 }
 447
 448 int SourceBufferRange::GetNextConfigId() const {
 449   DCHECK(HasNextBuffer());
 450   // If the next buffer is an audio splice frame, the next effective config id
 451   // comes from the first fade out preroll buffer.
 452   return buffers_[next_buffer_index_]->GetSpliceBufferConfigId(0);
 453 }
 454
 455 DecodeTimestamp SourceBufferRange::GetNextTimestamp() const {
 456   DCHECK(!buffers_.empty());
 457   DCHECK(HasNextBufferPosition());
 458
 459   if (next_buffer_index_ >= static_cast<int>(buffers_.size())) {
 460     return kNoDecodeTimestamp();
 461   }
 462
 463   return buffers_[next_buffer_index_]->GetDecodeTimestamp();
 464 }
 465
 466 bool SourceBufferRange::HasNextBufferPosition() const {
 467   return next_buffer_index_ >= 0;
 468 }
 469
 470 void SourceBufferRange::ResetNextBufferPosition() {
 471   next_buffer_index_ = -1;
 472 }
 473
 474 void SourceBufferRange::AppendRangeToEnd(const SourceBufferRange& range,
 475                                          bool transfer_current_position) {
 476   DCHECK(CanAppendRangeToEnd(range));
 477   DCHECK(!buffers_.empty());
 478
 479   if (transfer_current_position && range.next_buffer_index_ >= 0)
 480     next_buffer_index_ = range.next_buffer_index_ + buffers_.size();
 481
 482   AppendBuffersToEnd(range.buffers_);
 483 }
 484
 485 bool SourceBufferRange::CanAppendRangeToEnd(
 486     const SourceBufferRange& range) const {
 487   return CanAppendBuffersToEnd(range.buffers_);
 488 }
 489
 490 bool SourceBufferRange::CanAppendBuffersToEnd(
 491     const BufferQueue& buffers) const {
 492   DCHECK(!buffers_.empty());
 493   return IsNextInSequence(buffers.front()->GetDecodeTimestamp(),
 494                           buffers.front()->is_key_frame());
 495 }
 496
 497 bool SourceBufferRange::BelongsToRange(DecodeTimestamp timestamp) const {
 498   DCHECK(!buffers_.empty());
 499
 500   return (IsNextInSequence(timestamp, false) ||
 501           (GetStartTimestamp() <= timestamp && timestamp <= GetEndTimestamp()));
 502 }
 503
 504 bool SourceBufferRange::CanSeekTo(DecodeTimestamp timestamp) const {
 505   DecodeTimestamp start_timestamp =
 506       std::max(DecodeTimestamp(), GetStartTimestamp() - GetFudgeRoom());
 507   return !keyframe_map_.empty() && start_timestamp <= timestamp &&
 508       timestamp < GetBufferedEndTimestamp();
 509 }
 510
 511 bool SourceBufferRange::CompletelyOverlaps(
 512     const SourceBufferRange& range) const {
 513   return GetStartTimestamp() <= range.GetStartTimestamp() &&
 514       GetEndTimestamp() >= range.GetEndTimestamp();
 515 }
 516
 517 bool SourceBufferRange::EndOverlaps(const SourceBufferRange& range) const {
 518   return range.GetStartTimestamp() <= GetEndTimestamp() &&
 519       GetEndTimestamp() < range.GetEndTimestamp();
 520 }
 521
 522 DecodeTimestamp SourceBufferRange::GetStartTimestamp() const {
 523   DCHECK(!buffers_.empty());
 524   DecodeTimestamp start_timestamp = media_segment_start_time_;
 525   if (start_timestamp == kNoDecodeTimestamp())
 526     start_timestamp = buffers_.front()->GetDecodeTimestamp();
 527   return start_timestamp;
 528 }
 529
 530 DecodeTimestamp SourceBufferRange::GetEndTimestamp() const {
 531   DCHECK(!buffers_.empty());
 532   return buffers_.back()->GetDecodeTimestamp();
 533 }
 534
 535 DecodeTimestamp SourceBufferRange::GetBufferedEndTimestamp() const {
 536   DCHECK(!buffers_.empty());
 537   base::TimeDelta duration = buffers_.back()->duration();
 538   if (duration == kNoTimestamp() || duration == base::TimeDelta())
 539     duration = GetApproximateDuration();
 540   return GetEndTimestamp() + duration;
 541 }
 542
 543 DecodeTimestamp SourceBufferRange::NextKeyframeTimestamp(
 544     DecodeTimestamp timestamp) {
 545   DCHECK(!keyframe_map_.empty());
 546
 547   if (timestamp < GetStartTimestamp() || timestamp >= GetBufferedEndTimestamp())
 548     return kNoDecodeTimestamp();
 549
 550   KeyframeMap::iterator itr = GetFirstKeyframeAt(timestamp, false);
 551   if (itr == keyframe_map_.end())
 552     return kNoDecodeTimestamp();
 553
 554   // If the timestamp is inside the gap between the start of the media
 555   // segment and the first buffer, then just pretend there is a
 556   // keyframe at the specified timestamp.
 557   if (itr == keyframe_map_.begin() &&
 558       timestamp > media_segment_start_time_ &&
 559       timestamp < itr->first) {
 560     return timestamp;
 561   }
 562
 563   return itr->first;
 564 }
 565
 566 DecodeTimestamp SourceBufferRange::KeyframeBeforeTimestamp(
 567     DecodeTimestamp timestamp) {
 568   DCHECK(!keyframe_map_.empty());
 569
 570   if (timestamp < GetStartTimestamp() || timestamp >= GetBufferedEndTimestamp())
 571     return kNoDecodeTimestamp();
 572
 573   return GetFirstKeyframeAtOrBefore(timestamp)->first;
 574 }
 575
 576 bool SourceBufferRange::IsNextInSequence(
 577     DecodeTimestamp timestamp, bool is_key_frame) const {
 578   DecodeTimestamp end = buffers_.back()->GetDecodeTimestamp();
 579   if (end < timestamp &&
 580       (gap_policy_ == ALLOW_GAPS ||
 581        timestamp <= end + GetFudgeRoom())) {
 582     return true;
 583   }
 584
 585   return timestamp == end && AllowSameTimestamp(
 586       buffers_.back()->is_key_frame(), is_key_frame);
 587 }
 588
 589 base::TimeDelta SourceBufferRange::GetFudgeRoom() const {
 590   // Because we do not know exactly when is the next timestamp, any buffer
 591   // that starts within 2x the approximate duration of a buffer is considered
 592   // within this range.
 593   return 2 * GetApproximateDuration();
 594 }
 595
 596 base::TimeDelta SourceBufferRange::GetApproximateDuration() const {
 597   base::TimeDelta max_interbuffer_distance = interbuffer_distance_cb_.Run();
 598   DCHECK(max_interbuffer_distance != kNoTimestamp());
 599   return max_interbuffer_distance;
 600 }
 601
 602 bool SourceBufferRange::GetBuffersInRange(DecodeTimestamp start,
 603                                           DecodeTimestamp end,
 604                                           BufferQueue* buffers) {
 605   // Find the nearest buffer with a decode timestamp <= start.
 606   const DecodeTimestamp first_timestamp = KeyframeBeforeTimestamp(start);
 607   if (first_timestamp == kNoDecodeTimestamp())
 608     return false;
 609
 610   // Find all buffers involved in the range.
 611   const size_t previous_size = buffers->size();
 612   for (BufferQueue::iterator it = GetBufferItrAt(first_timestamp, false);
 613        it != buffers_.end();
 614        ++it) {
 615     const scoped_refptr<StreamParserBuffer>& buffer = *it;
 616     // Buffers without duration are not supported, so bail if we encounter any.
 617     if (buffer->duration() == kNoTimestamp() ||
 618         buffer->duration() <= base::TimeDelta()) {
 619       return false;
 620     }
 621     if (buffer->end_of_stream() ||
 622         buffer->timestamp() >= end.ToPresentationTime()) {
 623       break;
 624     }
 625
 626     if (buffer->timestamp() + buffer->duration() <= start.ToPresentationTime())
 627       continue;
 628     buffers->push_back(buffer);
 629   }
 630   return previous_size < buffers->size();
 631 }
 632
 633 }  // namespace media