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