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