media/filters/source_buffer_range.cc

   1 // Copyright 2014 The Chromium Authors
   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 #include <sstream>
   9 #include <string>
  10
  11 #include "base/logging.h"
  12 #include "media/base/stream_parser_buffer.h"
  13 #include "media/base/timestamp_constants.h"
  14
  15 namespace media {
  16
  17 SourceBufferRange::SourceBufferRange(
  18     GapPolicy gap_policy,
  19     const BufferQueue& new_buffers,
  20     base::TimeDelta range_start_pts,
  21     InterbufferDistanceCB interbuffer_distance_cb)
  22     : gap_policy_(gap_policy),
  23       next_buffer_index_(-1),
  24       interbuffer_distance_cb_(std::move(interbuffer_distance_cb)),
  25       size_in_bytes_(0),
  26       range_start_pts_(range_start_pts),
  27       keyframe_map_index_base_(0) {
  28   DVLOG(3) << __func__;
  29   DCHECK(interbuffer_distance_cb_);
  30   CHECK(!new_buffers.empty());
  31   DCHECK(new_buffers.front()->is_key_frame());
  32   AppendBuffersToEnd(new_buffers, range_start_pts_);
  33 }
  34
  35 SourceBufferRange::~SourceBufferRange() = default;
  36
  37 void SourceBufferRange::DeleteAll(BufferQueue* deleted_buffers) {
  38   DVLOG(1) << __func__;
  39   DVLOG(4) << ToStringForDebugging();
  40
  41   TruncateAt(0u, deleted_buffers);
  42 }
  43
  44 void SourceBufferRange::SeekToStart() {
  45   CHECK(!buffers_.empty());
  46   next_buffer_index_ = 0;
  47 }
  48
  49 bool SourceBufferRange::GetNextBuffer(
  50     scoped_refptr<StreamParserBuffer>* out_buffer) {
  51   if (!HasNextBuffer())
  52     return false;
  53
  54   *out_buffer = buffers_[next_buffer_index_];
  55   next_buffer_index_++;
  56   return true;
  57 }
  58
  59 bool SourceBufferRange::HasNextBuffer() const {
  60   return next_buffer_index_ >= 0 &&
  61       next_buffer_index_ < static_cast<int>(buffers_.size());
  62 }
  63
  64 int SourceBufferRange::GetNextConfigId() const {
  65   CHECK(HasNextBuffer()) << next_buffer_index_;
  66   // If the next buffer is an audio splice frame, the next effective config id
  67   // comes from the first fade out preroll buffer.
  68   return buffers_[next_buffer_index_]->GetConfigId();
  69 }
  70
  71 bool SourceBufferRange::HasNextBufferPosition() const {
  72   return next_buffer_index_ >= 0;
  73 }
  74
  75 void SourceBufferRange::ResetNextBufferPosition() {
  76   next_buffer_index_ = -1;
  77 }
  78
  79 void SourceBufferRange::AppendRangeToEnd(const SourceBufferRange& range,
  80                                          bool transfer_current_position) {
  81   DVLOG(1) << __func__;
  82   DVLOG(4) << ToStringForDebugging();
  83
  84   DCHECK(CanAppendRangeToEnd(range));
  85   DCHECK(!buffers_.empty());
  86
  87   if (transfer_current_position && range.next_buffer_index_ >= 0)
  88     next_buffer_index_ = range.next_buffer_index_ + buffers_.size();
  89
  90   AppendBuffersToEnd(range.buffers_,
  91                      NextRangeStartTimeForAppendRangeToEnd(range));
  92 }
  93
  94 bool SourceBufferRange::CanAppendRangeToEnd(
  95     const SourceBufferRange& range) const {
  96   DVLOG(1) << __func__;
  97   DVLOG(4) << ToStringForDebugging();
  98
  99   return CanAppendBuffersToEnd(range.buffers_,
 100                                NextRangeStartTimeForAppendRangeToEnd(range));
 101 }
 102
 103 void SourceBufferRange::AppendBuffersToEnd(
 104     const BufferQueue& new_buffers,
 105     base::TimeDelta new_buffers_group_start_pts) {
 106   DVLOG(1) << __func__;
 107   DVLOG(4) << ToStringForDebugging();
 108
 109   CHECK(buffers_.empty() ||
 110         CanAppendBuffersToEnd(new_buffers, new_buffers_group_start_pts));
 111
 112   DCHECK(new_buffers_group_start_pts == kNoTimestamp ||
 113          new_buffers.front()->is_key_frame())
 114       << range_start_pts_ << ", " << new_buffers.front()->is_key_frame();
 115
 116   AdjustEstimatedDurationForNewAppend(new_buffers);
 117
 118   for (BufferQueue::const_iterator itr = new_buffers.begin();
 119        itr != new_buffers.end(); ++itr) {
 120     DCHECK((*itr)->timestamp() != kNoTimestamp);
 121     DCHECK((*itr)->GetDecodeTimestamp() != kNoDecodeTimestamp);
 122
 123     buffers_.push_back(*itr);
 124     UpdateEndTime(*itr);
 125     size_in_bytes_ += (*itr)->data_size();
 126
 127     if ((*itr)->is_key_frame()) {
 128       keyframe_map_.insert(std::make_pair(
 129           (*itr)->timestamp(), buffers_.size() - 1 + keyframe_map_index_base_));
 130     }
 131   }
 132
 133   DVLOG(4) << __func__ << " Result: " << ToStringForDebugging();
 134 }
 135
 136 bool SourceBufferRange::AllowableAppendAfterEstimatedDuration(
 137     const BufferQueue& buffers,
 138     base::TimeDelta new_buffers_group_start_pts) const {
 139   if (buffers_.empty() || !buffers_.back()->is_duration_estimated() ||
 140       buffers.empty() || !buffers.front()->is_key_frame()) {
 141     return false;
 142   }
 143
 144   if (new_buffers_group_start_pts == kNoTimestamp) {
 145     return GetBufferedEndTimestamp() == buffers.front()->timestamp();
 146   }
 147
 148   return GetBufferedEndTimestamp() == new_buffers_group_start_pts;
 149 }
 150
 151 bool SourceBufferRange::CanAppendBuffersToEnd(
 152     const BufferQueue& buffers,
 153     base::TimeDelta new_buffers_group_start_pts) const {
 154   DVLOG(1) << __func__;
 155   DVLOG(4) << ToStringForDebugging();
 156
 157   DCHECK(!buffers_.empty());
 158   if (new_buffers_group_start_pts == kNoTimestamp) {
 159     return buffers.front()->is_key_frame()
 160                ? (IsNextInPresentationSequence(buffers.front()->timestamp()) ||
 161                   AllowableAppendAfterEstimatedDuration(
 162                       buffers, new_buffers_group_start_pts))
 163                : IsNextInDecodeSequence(buffers.front()->GetDecodeTimestamp());
 164   }
 165   CHECK(buffers.front()->is_key_frame());
 166   DCHECK(new_buffers_group_start_pts >= GetEndTimestamp());
 167   DCHECK(buffers.front()->timestamp() >= new_buffers_group_start_pts);
 168   return IsNextInPresentationSequence(new_buffers_group_start_pts) ||
 169          AllowableAppendAfterEstimatedDuration(buffers,
 170                                                new_buffers_group_start_pts);
 171 }
 172
 173 void SourceBufferRange::Seek(base::TimeDelta timestamp) {
 174   DVLOG(1) << __func__;
 175   DVLOG(4) << ToStringForDebugging();
 176
 177   DCHECK(CanSeekTo(timestamp));
 178   DCHECK(!keyframe_map_.empty());
 179
 180   auto result = GetFirstKeyframeAtOrBefore(timestamp);
 181   next_buffer_index_ = result->second - keyframe_map_index_base_;
 182   CHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()))
 183       << next_buffer_index_ << ", size = " << buffers_.size();
 184 }
 185
 186 bool SourceBufferRange::CanSeekTo(base::TimeDelta timestamp) const {
 187   DVLOG(1) << __func__;
 188   DVLOG(4) << ToStringForDebugging();
 189
 190   base::TimeDelta start_timestamp =
 191       std::max(base::TimeDelta(), GetStartTimestamp() - GetFudgeRoom());
 192   return !keyframe_map_.empty() && start_timestamp <= timestamp &&
 193          timestamp < GetBufferedEndTimestamp();
 194 }
 195
 196 int SourceBufferRange::GetConfigIdAtTime(base::TimeDelta timestamp) const {
 197   DVLOG(1) << __func__;
 198   DVLOG(4) << ToStringForDebugging();
 199
 200   DCHECK(CanSeekTo(timestamp));
 201   DCHECK(!keyframe_map_.empty());
 202
 203   auto result = GetFirstKeyframeAtOrBefore(timestamp);
 204   CHECK(result != keyframe_map_.end());
 205   size_t buffer_index = result->second - keyframe_map_index_base_;
 206   CHECK_LT(buffer_index, buffers_.size())
 207       << buffer_index << ", size = " << buffers_.size();
 208
 209   return buffers_[buffer_index]->GetConfigId();
 210 }
 211
 212 bool SourceBufferRange::SameConfigThruRange(base::TimeDelta start,
 213                                             base::TimeDelta end) const {
 214   DVLOG(1) << __func__;
 215   DVLOG(4) << ToStringForDebugging();
 216
 217   DCHECK(CanSeekTo(start));
 218   DCHECK(CanSeekTo(end));
 219   DCHECK(start <= end);
 220   DCHECK(!keyframe_map_.empty());
 221
 222   if (start == end)
 223     return true;
 224
 225   auto result = GetFirstKeyframeAtOrBefore(start);
 226   CHECK(result != keyframe_map_.end());
 227   size_t buffer_index = result->second - keyframe_map_index_base_;
 228   CHECK_LT(buffer_index, buffers_.size())
 229       << buffer_index << ", size = " << buffers_.size();
 230
 231   int start_config = buffers_[buffer_index]->GetConfigId();
 232   buffer_index++;
 233   while (buffer_index < buffers_.size() &&
 234          buffers_[buffer_index]->timestamp() <= end) {
 235     if (buffers_[buffer_index]->GetConfigId() != start_config)
 236       return false;
 237     buffer_index++;
 238   }
 239
 240   return true;
 241 }
 242
 243 std::unique_ptr<SourceBufferRange> SourceBufferRange::SplitRange(
 244     base::TimeDelta timestamp) {
 245   DVLOG(1) << __func__;
 246   DVLOG(4) << ToStringForDebugging();
 247
 248   CHECK(!buffers_.empty());
 249
 250   // Find the first keyframe at or after |timestamp|.
 251   auto new_beginning_keyframe = GetFirstKeyframeAt(timestamp, false);
 252
 253   // If there is no keyframe at or after |timestamp|, we can't split the range.
 254   if (new_beginning_keyframe == keyframe_map_.end())
 255     return nullptr;
 256
 257   // Remove the data beginning at |keyframe_index| from |buffers_| and save it
 258   // into |removed_buffers|.
 259   int keyframe_index =
 260       new_beginning_keyframe->second - keyframe_map_index_base_;
 261   CHECK_LT(keyframe_index, static_cast<int>(buffers_.size()));
 262   BufferQueue::iterator starting_point = buffers_.begin() + keyframe_index;
 263   BufferQueue removed_buffers(starting_point, buffers_.end());
 264
 265   base::TimeDelta new_range_start_pts =
 266       std::max(timestamp, GetStartTimestamp());
 267   DCHECK(new_range_start_pts <= removed_buffers.front()->timestamp());
 268
 269   keyframe_map_.erase(new_beginning_keyframe, keyframe_map_.end());
 270   FreeBufferRange(starting_point, buffers_.end());
 271   UpdateEndTimeUsingLastGOP();
 272
 273   // Create a new range with |removed_buffers|.
 274   std::unique_ptr<SourceBufferRange> split_range =
 275       std::make_unique<SourceBufferRange>(gap_policy_, removed_buffers,
 276                                           new_range_start_pts,
 277                                           interbuffer_distance_cb_);
 278
 279   // If the next buffer position is now in |split_range|, update the state of
 280   // this range and |split_range| accordingly.
 281   if (next_buffer_index_ >= static_cast<int>(buffers_.size())) {
 282     split_range->next_buffer_index_ = next_buffer_index_ - keyframe_index;
 283
 284     int split_range_next_buffer_index = split_range->next_buffer_index_;
 285     CHECK_GE(split_range_next_buffer_index, 0);
 286     // Note that a SourceBufferRange's |next_buffer_index_| can be the index
 287     // of a buffer one beyond what is currently in |buffers_|.
 288     CHECK_LE(split_range_next_buffer_index,
 289              static_cast<int>(split_range->buffers_.size()));
 290
 291     ResetNextBufferPosition();
 292   }
 293
 294   return split_range;
 295 }
 296
 297 bool SourceBufferRange::TruncateAt(base::TimeDelta timestamp,
 298                                    BufferQueue* deleted_buffers,
 299                                    bool is_exclusive) {
 300   DVLOG(1) << __func__;
 301   DVLOG(4) << ToStringForDebugging();
 302
 303   // Find the place in |buffers_| where we will begin deleting data, then
 304   // truncate from there.
 305   return TruncateAt(GetBufferIndexAt(timestamp, is_exclusive), deleted_buffers);
 306 }
 307
 308 size_t SourceBufferRange::DeleteGOPFromFront(BufferQueue* deleted_buffers) {
 309   DVLOG(1) << __func__;
 310   DVLOG(4) << ToStringForDebugging();
 311
 312   DCHECK(!buffers_.empty());
 313   DCHECK(!FirstGOPContainsNextBufferPosition());
 314   DCHECK(deleted_buffers);
 315
 316   int buffers_deleted = 0;
 317   size_t total_bytes_deleted = 0;
 318
 319   KeyframeMap::const_iterator front = keyframe_map_.begin();
 320   DCHECK(front != keyframe_map_.end());
 321
 322   // Delete the keyframe at the start of |keyframe_map_|.
 323   keyframe_map_.erase(front);
 324
 325   // Now we need to delete all the buffers that depend on the keyframe we've
 326   // just deleted.
 327   int end_index = keyframe_map_.size() > 0
 328                       ? keyframe_map_.begin()->second - keyframe_map_index_base_
 329                       : buffers_.size();
 330
 331   // Delete buffers from the beginning of the buffered range up until (but not
 332   // including) the next keyframe.
 333   for (int i = 0; i < end_index; i++) {
 334     size_t bytes_deleted = buffers_.front()->data_size();
 335     DCHECK_GE(size_in_bytes_, bytes_deleted);
 336     size_in_bytes_ -= bytes_deleted;
 337     total_bytes_deleted += bytes_deleted;
 338     deleted_buffers->push_back(buffers_.front());
 339     buffers_.pop_front();
 340     ++buffers_deleted;
 341   }
 342
 343   // Update |keyframe_map_index_base_| to account for the deleted buffers.
 344   keyframe_map_index_base_ += buffers_deleted;
 345
 346   if (next_buffer_index_ > -1) {
 347     next_buffer_index_ -= buffers_deleted;
 348     CHECK_GE(next_buffer_index_, 0)
 349         << next_buffer_index_ << ", deleted " << buffers_deleted;
 350   }
 351
 352   // Invalidate range start time if we've deleted the first buffer of the range.
 353   if (buffers_deleted > 0) {
 354     range_start_pts_ = kNoTimestamp;
 355     // Reset the range end time tracking if there are no more buffers in the
 356     // range.
 357     if (buffers_.empty())
 358       highest_frame_ = nullptr;
 359   }
 360
 361   return total_bytes_deleted;
 362 }
 363
 364 size_t SourceBufferRange::DeleteGOPFromBack(BufferQueue* deleted_buffers) {
 365   DVLOG(1) << __func__;
 366   DVLOG(4) << ToStringForDebugging();
 367
 368   DCHECK(!buffers_.empty());
 369   DCHECK(!LastGOPContainsNextBufferPosition());
 370   DCHECK(deleted_buffers);
 371
 372   // Remove the last GOP's keyframe from the |keyframe_map_|.
 373   KeyframeMap::const_iterator back = keyframe_map_.end();
 374   DCHECK_GT(keyframe_map_.size(), 0u);
 375   --back;
 376
 377   // The index of the first buffer in the last GOP is equal to the new size of
 378   // |buffers_| after that GOP is deleted.
 379   size_t goal_size = back->second - keyframe_map_index_base_;
 380   keyframe_map_.erase(back);
 381
 382   size_t total_bytes_deleted = 0;
 383   while (buffers_.size() != goal_size) {
 384     size_t bytes_deleted = buffers_.back()->data_size();
 385     DCHECK_GE(size_in_bytes_, bytes_deleted);
 386     size_in_bytes_ -= bytes_deleted;
 387     total_bytes_deleted += bytes_deleted;
 388     // We're removing buffers from the back, so push each removed buffer to the
 389     // front of |deleted_buffers| so that |deleted_buffers| are in nondecreasing
 390     // order.
 391     deleted_buffers->push_front(buffers_.back());
 392     buffers_.pop_back();
 393   }
 394
 395   UpdateEndTimeUsingLastGOP();
 396
 397   return total_bytes_deleted;
 398 }
 399
 400 size_t SourceBufferRange::GetRemovalGOP(
 401     base::TimeDelta start_timestamp,
 402     base::TimeDelta end_timestamp,
 403     size_t total_bytes_to_free,
 404     base::TimeDelta* removal_end_timestamp) const {
 405   DVLOG(1) << __func__;
 406   DVLOG(4) << ToStringForDebugging();
 407
 408   size_t bytes_removed = 0;
 409
 410   auto gop_itr = GetFirstKeyframeAt(start_timestamp, false);
 411   if (gop_itr == keyframe_map_.end())
 412     return 0;
 413   int keyframe_index = gop_itr->second - keyframe_map_index_base_;
 414   BufferQueue::const_iterator buffer_itr = buffers_.begin() + keyframe_index;
 415   auto gop_end = keyframe_map_.end();
 416   if (end_timestamp < GetBufferedEndTimestamp())
 417     gop_end = GetFirstKeyframeAtOrBefore(end_timestamp);
 418
 419   // Check if the removal range is within a GOP and skip the loop if so.
 420   // [keyframe]...[start_timestamp]...[end_timestamp]...[keyframe]
 421   auto gop_itr_prev = gop_itr;
 422   if (gop_itr_prev != keyframe_map_.begin() && --gop_itr_prev == gop_end)
 423     gop_end = gop_itr;
 424
 425   while (gop_itr != gop_end && bytes_removed < total_bytes_to_free) {
 426     ++gop_itr;
 427
 428     size_t gop_size = 0;
 429     int next_gop_index = gop_itr == keyframe_map_.end()
 430                              ? buffers_.size()
 431                              : gop_itr->second - keyframe_map_index_base_;
 432     BufferQueue::const_iterator next_gop_start =
 433         buffers_.begin() + next_gop_index;
 434     for (; buffer_itr != next_gop_start; ++buffer_itr) {
 435       gop_size += (*buffer_itr)->data_size();
 436     }
 437
 438     bytes_removed += gop_size;
 439   }
 440   if (bytes_removed > 0) {
 441     *removal_end_timestamp = gop_itr == keyframe_map_.end()
 442                                  ? GetBufferedEndTimestamp()
 443                                  : gop_itr->first;
 444   }
 445   return bytes_removed;
 446 }
 447
 448 bool SourceBufferRange::FirstGOPEarlierThanMediaTime(
 449     base::TimeDelta media_time) const {
 450   DVLOG(1) << __func__;
 451   DVLOG(4) << ToStringForDebugging();
 452
 453   if (keyframe_map_.size() == 1u)
 454     return (GetBufferedEndTimestamp() <= media_time);
 455
 456   auto second_gop = keyframe_map_.begin();
 457   ++second_gop;
 458   return second_gop->first <= media_time;
 459 }
 460
 461 bool SourceBufferRange::FirstGOPContainsNextBufferPosition() const {
 462   DVLOG(1) << __func__;
 463   DVLOG(4) << ToStringForDebugging();
 464
 465   if (!HasNextBufferPosition())
 466     return false;
 467
 468   // If there is only one GOP, it must contain the next buffer position.
 469   if (keyframe_map_.size() == 1u)
 470     return true;
 471
 472   auto second_gop = keyframe_map_.begin();
 473   ++second_gop;
 474   return next_buffer_index_ < second_gop->second - keyframe_map_index_base_;
 475 }
 476
 477 bool SourceBufferRange::LastGOPContainsNextBufferPosition() const {
 478   DVLOG(1) << __func__;
 479   DVLOG(4) << ToStringForDebugging();
 480
 481   if (!HasNextBufferPosition())
 482     return false;
 483
 484   // If there is only one GOP, it must contain the next buffer position.
 485   if (keyframe_map_.size() == 1u)
 486     return true;
 487
 488   auto last_gop = keyframe_map_.end();
 489   --last_gop;
 490   return last_gop->second - keyframe_map_index_base_ <= next_buffer_index_;
 491 }
 492
 493 base::TimeDelta SourceBufferRange::GetNextTimestamp() const {
 494   DVLOG(1) << __func__;
 495   DVLOG(4) << ToStringForDebugging();
 496
 497   CHECK(!buffers_.empty()) << next_buffer_index_;
 498   CHECK(HasNextBufferPosition())
 499       << next_buffer_index_ << ", size=" << buffers_.size();
 500
 501   if (next_buffer_index_ >= static_cast<int>(buffers_.size())) {
 502     return kNoTimestamp;
 503   }
 504
 505   return buffers_[next_buffer_index_]->timestamp();
 506 }
 507
 508 base::TimeDelta SourceBufferRange::GetStartTimestamp() const {
 509   DVLOG(1) << __func__;
 510   DVLOG(4) << ToStringForDebugging();
 511
 512   DCHECK(!buffers_.empty());
 513   base::TimeDelta start_timestamp = range_start_pts_;
 514   if (start_timestamp == kNoTimestamp)
 515     start_timestamp = buffers_.front()->timestamp();
 516   return start_timestamp;
 517 }
 518
 519 base::TimeDelta SourceBufferRange::GetEndTimestamp() const {
 520   DVLOG(1) << __func__;
 521   DVLOG(4) << ToStringForDebugging();
 522
 523   DCHECK(!buffers_.empty());
 524   return highest_frame_->timestamp();
 525 }
 526
 527 base::TimeDelta SourceBufferRange::GetBufferedEndTimestamp() const {
 528   DVLOG(1) << __func__;
 529   DVLOG(4) << ToStringForDebugging();
 530
 531   DCHECK(!buffers_.empty());
 532   base::TimeDelta duration = highest_frame_->duration();
 533
 534   // FrameProcessor should protect against unknown buffer durations.
 535   DCHECK_NE(duration, kNoTimestamp);
 536
 537   // Because media::Ranges<base::TimeDelta>::Add() ignores 0 duration ranges,
 538   // report 1 microsecond for the last buffer's duration if it is a 0 duration
 539   // buffer.
 540   if (duration.is_zero())
 541     duration = base::Microseconds(1);
 542
 543   return GetEndTimestamp() + duration;
 544 }
 545
 546 bool SourceBufferRange::BelongsToRange(base::TimeDelta timestamp) const {
 547   DVLOG(1) << __func__;
 548   DVLOG(4) << ToStringForDebugging();
 549
 550   DCHECK(!buffers_.empty());
 551
 552   return (IsNextInPresentationSequence(timestamp) ||
 553           (GetStartTimestamp() <= timestamp && timestamp <= GetEndTimestamp()));
 554 }
 555
 556 base::TimeDelta SourceBufferRange::FindHighestBufferedTimestampAtOrBefore(
 557     base::TimeDelta timestamp) const {
 558   DVLOG(1) << __func__;
 559   DVLOG(4) << ToStringForDebugging();
 560
 561   DCHECK(!buffers_.empty());
 562   DCHECK(BelongsToRange(timestamp));
 563
 564   if (keyframe_map_.begin()->first > timestamp) {
 565     // If the first keyframe in the range starts after |timestamp|, then
 566     // return the range start time (which could be earlier due to coded frame
 567     // group signalling.)
 568     base::TimeDelta range_start = GetStartTimestamp();
 569     DCHECK(timestamp >= range_start) << "BelongsToRange() semantics failed.";
 570     return range_start;
 571   }
 572
 573   if (keyframe_map_.begin()->first == timestamp) {
 574     return timestamp;
 575   }
 576
 577   auto key_iter = GetFirstKeyframeAtOrBefore(timestamp);
 578   DCHECK(key_iter != keyframe_map_.end())
 579       << "BelongsToRange() semantics failed.";
 580   DCHECK(key_iter->first <= timestamp);
 581
 582   // Scan forward in |buffers_| to find the highest frame with timestamp <=
 583   // |timestamp|. Stop once a frame with timestamp > |timestamp| is encountered.
 584   size_t key_index = key_iter->second - keyframe_map_index_base_;
 585   SourceBufferRange::BufferQueue::const_iterator search_iter =
 586       buffers_.begin() + key_index;
 587   CHECK(search_iter != buffers_.end());
 588   base::TimeDelta cur_frame_time = (*search_iter)->timestamp();
 589   base::TimeDelta result = cur_frame_time;
 590   while (true) {
 591     result = std::max(result, cur_frame_time);
 592     search_iter++;
 593     if (search_iter == buffers_.end())
 594       return result;
 595     cur_frame_time = (*search_iter)->timestamp();
 596     if (cur_frame_time > timestamp)
 597       return result;
 598   }
 599
 600   NOTREACHED();
 601   return base::TimeDelta();
 602 }
 603
 604 base::TimeDelta SourceBufferRange::NextKeyframeTimestamp(
 605     base::TimeDelta timestamp) const {
 606   DVLOG(1) << __func__;
 607   DVLOG(4) << ToStringForDebugging();
 608
 609   DCHECK(!keyframe_map_.empty());
 610
 611   if (timestamp < GetStartTimestamp() || timestamp >= GetBufferedEndTimestamp())
 612     return kNoTimestamp;
 613
 614   auto itr = GetFirstKeyframeAt(timestamp, false);
 615   if (itr == keyframe_map_.end())
 616     return kNoTimestamp;
 617
 618   // If the timestamp is inside the gap between the start of the coded frame
 619   // group and the first buffer, then just pretend there is a keyframe at the
 620   // specified timestamp.
 621   if (itr == keyframe_map_.begin() && timestamp > range_start_pts_ &&
 622       timestamp < itr->first) {
 623     return timestamp;
 624   }
 625
 626   return itr->first;
 627 }
 628
 629 base::TimeDelta SourceBufferRange::KeyframeBeforeTimestamp(
 630     base::TimeDelta timestamp) const {
 631   DVLOG(1) << __func__;
 632   DVLOG(4) << ToStringForDebugging();
 633
 634   DCHECK(!keyframe_map_.empty());
 635
 636   if (timestamp < GetStartTimestamp() || timestamp >= GetBufferedEndTimestamp())
 637     return kNoTimestamp;
 638
 639   return GetFirstKeyframeAtOrBefore(timestamp)->first;
 640 }
 641
 642 bool SourceBufferRange::GetBuffersInRange(base::TimeDelta start,
 643                                           base::TimeDelta end,
 644                                           BufferQueue* buffers) const {
 645   DVLOG(1) << __func__;
 646   DVLOG(4) << ToStringForDebugging();
 647
 648   // Find the nearest buffer with a timestamp <= start.
 649   const base::TimeDelta first_timestamp = KeyframeBeforeTimestamp(start);
 650   if (first_timestamp == kNoTimestamp)
 651     return false;
 652
 653   // Find all buffers involved in the range.
 654   const size_t previous_size = buffers->size();
 655   for (BufferQueue::const_iterator it = GetBufferItrAt(first_timestamp, false);
 656        it != buffers_.end(); ++it) {
 657     scoped_refptr<StreamParserBuffer> buffer = *it;
 658     // Buffers without duration are not supported, so bail if we encounter any.
 659     if (buffer->duration() == kNoTimestamp ||
 660         buffer->duration() <= base::TimeDelta()) {
 661       return false;
 662     }
 663     if (buffer->timestamp() >= end)
 664       break;
 665
 666     if (buffer->timestamp() + buffer->duration() <= start)
 667       continue;
 668
 669     buffers->emplace_back(std::move(buffer));
 670   }
 671   return previous_size < buffers->size();
 672 }
 673
 674 void SourceBufferRange::AdjustEstimatedDurationForNewAppend(
 675     const BufferQueue& new_buffers) {
 676   if (buffers_.empty() || new_buffers.empty()) {
 677     return;
 678   }
 679
 680   // Do not adjust estimate for Audio buffers to avoid competing with
 681   // SourceBufferStream::TrimSpliceOverlap()
 682   if (buffers_.front()->type() == StreamParserBuffer::Type::AUDIO) {
 683     return;
 684   }
 685
 686   // If the last of the previously appended buffers contains estimated duration,
 687   // we now refine that estimate by taking the PTS delta from the first new
 688   // buffer being appended.
 689   const auto& last_appended_buffer = buffers_.back();
 690   if (last_appended_buffer->is_duration_estimated()) {
 691     base::TimeDelta timestamp_delta =
 692         new_buffers.front()->timestamp() - last_appended_buffer->timestamp();
 693     DCHECK_GE(timestamp_delta, base::TimeDelta());
 694     if (last_appended_buffer->duration() != timestamp_delta) {
 695       DVLOG(1) << "Replacing estimated duration ("
 696                << last_appended_buffer->duration()
 697                << ") from previous range-end with derived duration ("
 698                << timestamp_delta << ").";
 699       last_appended_buffer->set_duration(timestamp_delta);
 700     }
 701   }
 702 }
 703
 704 void SourceBufferRange::FreeBufferRange(
 705     const BufferQueue::const_iterator& starting_point,
 706     const BufferQueue::const_iterator& ending_point) {
 707   for (BufferQueue::const_iterator itr = starting_point; itr != ending_point;
 708        ++itr) {
 709     size_t itr_data_size = static_cast<size_t>((*itr)->data_size());
 710     DCHECK_GE(size_in_bytes_, itr_data_size);
 711     size_in_bytes_ -= itr_data_size;
 712   }
 713   buffers_.erase(starting_point, ending_point);
 714 }
 715
 716 base::TimeDelta SourceBufferRange::GetFudgeRoom() const {
 717   // Because we do not know exactly when is the next timestamp, any buffer
 718   // that starts within 2x the approximate duration of a buffer is considered
 719   // within this range.
 720   return 2 * GetApproximateDuration();
 721 }
 722
 723 base::TimeDelta SourceBufferRange::GetApproximateDuration() const {
 724   base::TimeDelta max_interbuffer_distance = interbuffer_distance_cb_.Run();
 725   DCHECK(max_interbuffer_distance != kNoTimestamp);
 726   return max_interbuffer_distance;
 727 }
 728
 729 void SourceBufferRange::UpdateEndTime(
 730     scoped_refptr<StreamParserBuffer> new_buffer) {
 731   base::TimeDelta timestamp = new_buffer->timestamp();
 732   base::TimeDelta duration = new_buffer->duration();
 733   DVLOG(1) << __func__ << " timestamp=" << timestamp
 734            << ", duration=" << duration;
 735   DCHECK_NE(timestamp, kNoTimestamp);
 736   DCHECK_GE(timestamp, base::TimeDelta());
 737   DCHECK_GE(duration, base::TimeDelta());
 738
 739   if (!highest_frame_) {
 740     DVLOG(1) << "Updating range end time from <empty> to "
 741              << timestamp.InMicroseconds() << "us, "
 742              << (timestamp + duration).InMicroseconds() << "us";
 743     highest_frame_ = std::move(new_buffer);
 744     return;
 745   }
 746
 747   if (highest_frame_->timestamp() < timestamp ||
 748       (highest_frame_->timestamp() == timestamp &&
 749        highest_frame_->duration() <= duration)) {
 750     DVLOG(1) << "Updating range end time from "
 751              << highest_frame_->timestamp().InMicroseconds() << "us, "
 752              << (highest_frame_->timestamp() + highest_frame_->duration())
 753                     .InMicroseconds()
 754              << "us to " << timestamp.InMicroseconds() << "us, "
 755              << (timestamp + duration).InMicroseconds();
 756     highest_frame_ = std::move(new_buffer);
 757   }
 758 }
 759
 760 bool SourceBufferRange::IsNextInPresentationSequence(
 761     base::TimeDelta timestamp) const {
 762   DCHECK_NE(timestamp, kNoTimestamp);
 763   CHECK(!buffers_.empty());
 764   base::TimeDelta highest_timestamp = highest_frame_->timestamp();
 765   DCHECK_NE(highest_timestamp, kNoTimestamp);
 766   return (highest_timestamp == timestamp ||
 767           (highest_timestamp < timestamp &&
 768            (gap_policy_ == ALLOW_GAPS ||
 769             timestamp <= highest_timestamp + GetFudgeRoom())));
 770 }
 771
 772 bool SourceBufferRange::IsNextInDecodeSequence(
 773     DecodeTimestamp decode_timestamp) const {
 774   CHECK(!buffers_.empty());
 775   DecodeTimestamp end = buffers_.back()->GetDecodeTimestamp();
 776   return (
 777       end == decode_timestamp ||
 778       (end < decode_timestamp && (gap_policy_ == ALLOW_GAPS ||
 779                                   decode_timestamp <= end + GetFudgeRoom())));
 780 }
 781
 782 base::TimeDelta SourceBufferRange::NextRangeStartTimeForAppendRangeToEnd(
 783     const SourceBufferRange& range) const {
 784   DCHECK(!buffers_.empty());
 785   DCHECK(!range.buffers_.empty());
 786
 787   base::TimeDelta next_range_first_buffer_time =
 788       range.buffers_.front()->timestamp();
 789   base::TimeDelta this_range_end_time = GetEndTimestamp();
 790   if (next_range_first_buffer_time < this_range_end_time)
 791     return kNoTimestamp;
 792
 793   base::TimeDelta next_range_start_time = range.GetStartTimestamp();
 794   DCHECK(next_range_start_time <= next_range_first_buffer_time);
 795
 796   if (next_range_start_time >= this_range_end_time)
 797     return next_range_start_time;
 798
 799   return this_range_end_time;
 800 }
 801
 802 size_t SourceBufferRange::GetBufferIndexAt(base::TimeDelta timestamp,
 803                                            bool skip_given_timestamp) const {
 804   DVLOG(1) << __func__;
 805   DVLOG(4) << ToStringForDebugging();
 806
 807   // Find the GOP containing |timestamp| (or trivial buffers_.size() if none
 808   // contain |timestamp|).
 809   auto gop_iter = GetFirstKeyframeAtOrBefore(timestamp);
 810   if (gop_iter == keyframe_map_.end())
 811     return buffers_.size();
 812
 813   // Then scan forward in this GOP in decode sequence for the first frame with
 814   // PTS >= |timestamp| (or strictly > if |skip_given_timestamp| is true). If
 815   // this GOP doesn't contain such a frame, returns the index of the keyframe of
 816   // the next GOP (which could be the index of end() of |buffers_| if this was
 817   // the last GOP in |buffers_|). We do linear scan of the GOP here because we
 818   // don't know the DTS for the searched-for frame, and the PTS sequence within
 819   // a GOP may not match the DTS-sorted sequence of frames within the GOP.
 820   DCHECK_GT(buffers_.size(), 0u);
 821   size_t search_index = gop_iter->second - keyframe_map_index_base_;
 822   SourceBufferRange::BufferQueue::const_iterator search_iter =
 823       buffers_.begin() + search_index;
 824   gop_iter++;
 825
 826   SourceBufferRange::BufferQueue::const_iterator next_gop_start =
 827       gop_iter == keyframe_map_.end()
 828           ? buffers_.end()
 829           : buffers_.begin() + (gop_iter->second - keyframe_map_index_base_);
 830
 831   while (search_iter != next_gop_start) {
 832     if (((*search_iter)->timestamp() > timestamp) ||
 833         (!skip_given_timestamp && (*search_iter)->timestamp() == timestamp)) {
 834       break;
 835     }
 836     search_index++;
 837     search_iter++;
 838   }
 839
 840   return search_index;
 841 }
 842
 843 SourceBufferRange::BufferQueue::const_iterator
 844 SourceBufferRange::GetBufferItrAt(base::TimeDelta timestamp,
 845                                   bool skip_given_timestamp) const {
 846   DVLOG(1) << __func__;
 847   DVLOG(4) << ToStringForDebugging();
 848
 849   return buffers_.begin() + GetBufferIndexAt(timestamp, skip_given_timestamp);
 850 }
 851
 852 SourceBufferRange::KeyframeMap::const_iterator
 853 SourceBufferRange::GetFirstKeyframeAt(base::TimeDelta timestamp,
 854                                       bool skip_given_timestamp) const {
 855   DVLOG(1) << __func__;
 856   DVLOG(4) << ToStringForDebugging();
 857
 858   return skip_given_timestamp ? keyframe_map_.upper_bound(timestamp)
 859                               : keyframe_map_.lower_bound(timestamp);
 860 }
 861
 862 SourceBufferRange::KeyframeMap::const_iterator
 863 SourceBufferRange::GetFirstKeyframeAtOrBefore(base::TimeDelta timestamp) const {
 864   DVLOG(1) << __func__;
 865   DVLOG(4) << ToStringForDebugging();
 866
 867   auto result = keyframe_map_.lower_bound(timestamp);
 868   // lower_bound() returns the first element >= |timestamp|, so we want the
 869   // previous element if it did not return the element exactly equal to
 870   // |timestamp|.
 871   if (result != keyframe_map_.begin() &&
 872       (result == keyframe_map_.end() || result->first != timestamp)) {
 873     --result;
 874   }
 875   return result;
 876 }
 877
 878 bool SourceBufferRange::TruncateAt(const size_t starting_point,
 879                                    BufferQueue* deleted_buffers) {
 880   DVLOG(1) << __func__;
 881   DVLOG(4) << ToStringForDebugging();
 882
 883   CHECK_LE(starting_point, buffers_.size());
 884   DCHECK(!deleted_buffers || deleted_buffers->empty());
 885
 886   // Return if we're not deleting anything.
 887   if (starting_point == buffers_.size())
 888     return buffers_.empty();
 889
 890   // Reset the next buffer index if we will be deleting the buffer that's next
 891   // in sequence.
 892   if (HasNextBufferPosition()) {
 893     if (static_cast<size_t>(next_buffer_index_) >= starting_point) {
 894       if (HasNextBuffer() && deleted_buffers) {
 895         BufferQueue saved(buffers_.begin() + next_buffer_index_,
 896                           buffers_.end());
 897         deleted_buffers->swap(saved);
 898       }
 899       ResetNextBufferPosition();
 900     }
 901   }
 902
 903   const BufferQueue::const_iterator starting_point_iter =
 904       buffers_.begin() + starting_point;
 905
 906   // Remove keyframes from |starting_point| onward.
 907   KeyframeMap::const_iterator starting_point_keyframe =
 908       keyframe_map_.lower_bound((*starting_point_iter)->timestamp());
 909   keyframe_map_.erase(starting_point_keyframe, keyframe_map_.end());
 910
 911   // Remove everything from |starting_point| onward.
 912   FreeBufferRange(starting_point_iter, buffers_.end());
 913
 914   UpdateEndTimeUsingLastGOP();
 915   return buffers_.empty();
 916 }
 917
 918 void SourceBufferRange::UpdateEndTimeUsingLastGOP() {
 919   DVLOG(1) << __func__;
 920   DVLOG(4) << ToStringForDebugging();
 921
 922   if (buffers_.empty()) {
 923     DVLOG(1) << __func__ << " Empty range, resetting range end";
 924     highest_frame_ = nullptr;
 925     return;
 926   }
 927
 928   highest_frame_ = nullptr;
 929
 930   KeyframeMap::const_iterator last_gop = keyframe_map_.end();
 931   CHECK_GT(keyframe_map_.size(), 0u);
 932   --last_gop;
 933
 934   // Iterate through the frames of the last GOP in this range, finding the
 935   // frame with the highest PTS.
 936   for (BufferQueue::const_iterator buffer_itr =
 937            buffers_.begin() + (last_gop->second - keyframe_map_index_base_);
 938        buffer_itr != buffers_.end(); ++buffer_itr) {
 939     UpdateEndTime(*buffer_itr);
 940   }
 941
 942   DVLOG(1) << __func__ << " Updated range end time to "
 943            << highest_frame_->timestamp() << ", "
 944            << highest_frame_->timestamp() + highest_frame_->duration();
 945 }
 946
 947 std::string SourceBufferRange::ToStringForDebugging() const {
 948   std::stringstream result;
 949
 950 #if !defined(NDEBUG) || defined(DCHECK_ALWAYS_ON)
 951   result << "keyframe_map_index_base_=" << keyframe_map_index_base_
 952          << ", buffers.size()=" << buffers_.size()
 953          << ", keyframe_map_.size()=" << keyframe_map_.size()
 954          << ", keyframe_map_:\n";
 955   for (const auto& [time_delta, idx] : keyframe_map_) {
 956     result << "\t pts " << time_delta.InMicroseconds()
 957            << ", unadjusted idx = " << idx << "\n";
 958   }
 959 #endif  // !defined(NDEBUG) || defined(DCHECK_ALWAYS_ON)
 960
 961   return result.str();
 962 }
 963
 964 }  // namespace media