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