media/filters/source_buffer_stream.cc

   1 // Copyright (c) 2012 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_stream.h"
   6
   7 #include <algorithm>
   8 #include <map>
   9 #include <sstream>
  10
  11 #include "base/bind.h"
  12 #include "base/logging.h"
  13 #include "base/trace_event/trace_event.h"
  14 #include "media/base/audio_splicer.h"
  15 #include "media/filters/source_buffer_platform.h"
  16 #include "media/filters/source_buffer_range.h"
  17
  18 namespace media {
  19
  20 // Helper method that returns true if |ranges| is sorted in increasing order,
  21 // false otherwise.
  22 static bool IsRangeListSorted(
  23     const std::list<media::SourceBufferRange*>& ranges) {
  24   DecodeTimestamp prev = kNoDecodeTimestamp();
  25   for (std::list<SourceBufferRange*>::const_iterator itr =
  26        ranges.begin(); itr != ranges.end(); ++itr) {
  27     if (prev != kNoDecodeTimestamp() && prev >= (*itr)->GetStartTimestamp())
  28       return false;
  29     prev = (*itr)->GetEndTimestamp();
  30   }
  31   return true;
  32 }
  33
  34 // Returns an estimate of how far from the beginning or end of a range a buffer
  35 // can be to still be considered in the range, given the |approximate_duration|
  36 // of a buffer in the stream.
  37 // TODO(wolenetz): Once all stream parsers emit accurate frame durations, use
  38 // logic like FrameProcessor (2*last_frame_duration + last_decode_timestamp)
  39 // instead of an overall maximum interbuffer delta for range discontinuity
  40 // detection, and adjust similarly for splice frame discontinuity detection.
  41 // See http://crbug.com/351489 and http://crbug.com/351166.
  42 static base::TimeDelta ComputeFudgeRoom(base::TimeDelta approximate_duration) {
  43   // Because we do not know exactly when is the next timestamp, any buffer
  44   // that starts within 2x the approximate duration of a buffer is considered
  45   // within this range.
  46   return 2 * approximate_duration;
  47 }
  48
  49 // An arbitrarily-chosen number to estimate the duration of a buffer if none
  50 // is set and there's not enough information to get a better estimate.
  51 static int kDefaultBufferDurationInMs = 125;
  52
  53 // The amount of time the beginning of the buffered data can differ from the
  54 // start time in order to still be considered the start of stream.
  55 static base::TimeDelta kSeekToStartFudgeRoom() {
  56   return base::TimeDelta::FromMilliseconds(1000);
  57 }
  58
  59 // Helper method for logging, converts a range into a readable string.
  60 static std::string RangeToString(const SourceBufferRange& range) {
  61   std::stringstream ss;
  62   ss << "[" << range.GetStartTimestamp().InSecondsF()
  63      << ";" << range.GetEndTimestamp().InSecondsF()
  64      << "(" << range.GetBufferedEndTimestamp().InSecondsF() << ")]";
  65   return ss.str();
  66 }
  67
  68 // Helper method for logging, converts a set of ranges into a readable string.
  69 static std::string RangesToString(const SourceBufferStream::RangeList& ranges) {
  70   if (ranges.empty())
  71     return "<EMPTY>";
  72
  73   std::stringstream ss;
  74   for (const auto* range_ptr : ranges) {
  75     if (range_ptr != ranges.front())
  76       ss << " ";
  77     ss << RangeToString(*range_ptr);
  78   }
  79   return ss.str();
  80 }
  81
  82 static SourceBufferRange::GapPolicy TypeToGapPolicy(
  83     SourceBufferStream::Type type) {
  84   switch (type) {
  85     case SourceBufferStream::kAudio:
  86     case SourceBufferStream::kVideo:
  87       return SourceBufferRange::NO_GAPS_ALLOWED;
  88     case SourceBufferStream::kText:
  89       return SourceBufferRange::ALLOW_GAPS;
  90   }
  91
  92   NOTREACHED();
  93   return SourceBufferRange::NO_GAPS_ALLOWED;
  94 }
  95
  96 SourceBufferStream::SourceBufferStream(const AudioDecoderConfig& audio_config,
  97                                        const scoped_refptr<MediaLog>& media_log,
  98                                        bool splice_frames_enabled)
  99     : media_log_(media_log),
 100       current_config_index_(0),
 101       append_config_index_(0),
 102       seek_pending_(false),
 103       end_of_stream_(false),
 104       seek_buffer_timestamp_(kNoTimestamp()),
 105       selected_range_(NULL),
 106       media_segment_start_time_(kNoDecodeTimestamp()),
 107       range_for_next_append_(ranges_.end()),
 108       new_media_segment_(false),
 109       last_appended_buffer_timestamp_(kNoDecodeTimestamp()),
 110       last_appended_buffer_is_keyframe_(false),
 111       last_output_buffer_timestamp_(kNoDecodeTimestamp()),
 112       max_interbuffer_distance_(kNoTimestamp()),
 113       memory_limit_(kSourceBufferAudioMemoryLimit),
 114       config_change_pending_(false),
 115       splice_buffers_index_(0),
 116       pending_buffers_complete_(false),
 117       splice_frames_enabled_(splice_frames_enabled) {
 118   DCHECK(audio_config.IsValidConfig());
 119   audio_configs_.push_back(audio_config);
 120 }
 121
 122 SourceBufferStream::SourceBufferStream(const VideoDecoderConfig& video_config,
 123                                        const scoped_refptr<MediaLog>& media_log,
 124                                        bool splice_frames_enabled)
 125     : media_log_(media_log),
 126       current_config_index_(0),
 127       append_config_index_(0),
 128       seek_pending_(false),
 129       end_of_stream_(false),
 130       seek_buffer_timestamp_(kNoTimestamp()),
 131       selected_range_(NULL),
 132       media_segment_start_time_(kNoDecodeTimestamp()),
 133       range_for_next_append_(ranges_.end()),
 134       new_media_segment_(false),
 135       last_appended_buffer_timestamp_(kNoDecodeTimestamp()),
 136       last_appended_buffer_is_keyframe_(false),
 137       last_output_buffer_timestamp_(kNoDecodeTimestamp()),
 138       max_interbuffer_distance_(kNoTimestamp()),
 139       memory_limit_(kSourceBufferVideoMemoryLimit),
 140       config_change_pending_(false),
 141       splice_buffers_index_(0),
 142       pending_buffers_complete_(false),
 143       splice_frames_enabled_(splice_frames_enabled) {
 144   DCHECK(video_config.IsValidConfig());
 145   video_configs_.push_back(video_config);
 146 }
 147
 148 SourceBufferStream::SourceBufferStream(const TextTrackConfig& text_config,
 149                                        const scoped_refptr<MediaLog>& media_log,
 150                                        bool splice_frames_enabled)
 151     : media_log_(media_log),
 152       current_config_index_(0),
 153       append_config_index_(0),
 154       text_track_config_(text_config),
 155       seek_pending_(false),
 156       end_of_stream_(false),
 157       seek_buffer_timestamp_(kNoTimestamp()),
 158       selected_range_(NULL),
 159       media_segment_start_time_(kNoDecodeTimestamp()),
 160       range_for_next_append_(ranges_.end()),
 161       new_media_segment_(false),
 162       last_appended_buffer_timestamp_(kNoDecodeTimestamp()),
 163       last_appended_buffer_is_keyframe_(false),
 164       last_output_buffer_timestamp_(kNoDecodeTimestamp()),
 165       max_interbuffer_distance_(kNoTimestamp()),
 166       memory_limit_(kSourceBufferAudioMemoryLimit),
 167       config_change_pending_(false),
 168       splice_buffers_index_(0),
 169       pending_buffers_complete_(false),
 170       splice_frames_enabled_(splice_frames_enabled) {
 171 }
 172
 173 SourceBufferStream::~SourceBufferStream() {
 174   while (!ranges_.empty()) {
 175     delete ranges_.front();
 176     ranges_.pop_front();
 177   }
 178 }
 179
 180 void SourceBufferStream::OnNewMediaSegment(
 181     DecodeTimestamp media_segment_start_time) {
 182   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
 183            << " (" << media_segment_start_time.InSecondsF() << ")";
 184   DCHECK(!end_of_stream_);
 185   media_segment_start_time_ = media_segment_start_time;
 186   new_media_segment_ = true;
 187
 188   RangeList::iterator last_range = range_for_next_append_;
 189   range_for_next_append_ = FindExistingRangeFor(media_segment_start_time);
 190
 191   // Only reset |last_appended_buffer_timestamp_| if this new media segment is
 192   // not adjacent to the previous media segment appended to the stream.
 193   if (range_for_next_append_ == ranges_.end() ||
 194       !AreAdjacentInSequence(last_appended_buffer_timestamp_,
 195                              media_segment_start_time)) {
 196     last_appended_buffer_timestamp_ = kNoDecodeTimestamp();
 197     last_appended_buffer_is_keyframe_ = false;
 198     DVLOG(3) << __FUNCTION__ << " next appended buffers will be in a new range";
 199   } else if (last_range != ranges_.end()) {
 200     DCHECK(last_range == range_for_next_append_);
 201     DVLOG(3) << __FUNCTION__ << " next appended buffers will continue range "
 202              << "unless intervening remove makes discontinuity";
 203   }
 204 }
 205
 206 bool SourceBufferStream::Append(const BufferQueue& buffers) {
 207   TRACE_EVENT2("media", "SourceBufferStream::Append",
 208                "stream type", GetStreamTypeName(),
 209                "buffers to append", buffers.size());
 210
 211   DCHECK(!buffers.empty());
 212   DCHECK(media_segment_start_time_ != kNoDecodeTimestamp());
 213   DCHECK(media_segment_start_time_ <= buffers.front()->GetDecodeTimestamp());
 214   DCHECK(!end_of_stream_);
 215
 216   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName() << ": buffers dts=["
 217            << buffers.front()->GetDecodeTimestamp().InSecondsF() << ";"
 218            << buffers.back()->GetDecodeTimestamp().InSecondsF() << "] pts=["
 219            << buffers.front()->timestamp().InSecondsF() << ";"
 220            << buffers.back()->timestamp().InSecondsF() << "(last frame dur="
 221            << buffers.back()->duration().InSecondsF() << ")]";
 222
 223   // New media segments must begin with a keyframe.
 224   // TODO(wolenetz): Relax this requirement. See http://crbug.com/229412.
 225   if (new_media_segment_ && !buffers.front()->is_key_frame()) {
 226     MEDIA_LOG(ERROR, media_log_)
 227         << "Media segment did not begin with key frame.";
 228     return false;
 229   }
 230
 231   // Buffers within a media segment should be monotonically increasing.
 232   if (!IsMonotonicallyIncreasing(buffers))
 233     return false;
 234
 235   if (media_segment_start_time_ < DecodeTimestamp() ||
 236       buffers.front()->GetDecodeTimestamp() < DecodeTimestamp()) {
 237     MEDIA_LOG(ERROR, media_log_)
 238         << "Cannot append a media segment with negative timestamps.";
 239     return false;
 240   }
 241
 242   if (!IsNextTimestampValid(buffers.front()->GetDecodeTimestamp(),
 243                             buffers.front()->is_key_frame())) {
 244     const DecodeTimestamp& dts = buffers.front()->GetDecodeTimestamp();
 245     MEDIA_LOG(ERROR, media_log_)
 246         << "Invalid same timestamp construct detected at"
 247         << " time " << dts.InSecondsF();
 248
 249     return false;
 250   }
 251
 252   UpdateMaxInterbufferDistance(buffers);
 253   SetConfigIds(buffers);
 254
 255   // Save a snapshot of stream state before range modifications are made.
 256   DecodeTimestamp next_buffer_timestamp = GetNextBufferTimestamp();
 257   BufferQueue deleted_buffers;
 258
 259   PrepareRangesForNextAppend(buffers, &deleted_buffers);
 260
 261   // If there's a range for |buffers|, insert |buffers| accordingly. Otherwise,
 262   // create a new range with |buffers|.
 263   if (range_for_next_append_ != ranges_.end()) {
 264     (*range_for_next_append_)->AppendBuffersToEnd(buffers);
 265     last_appended_buffer_timestamp_ = buffers.back()->GetDecodeTimestamp();
 266     last_appended_buffer_is_keyframe_ = buffers.back()->is_key_frame();
 267   } else {
 268     DecodeTimestamp new_range_start_time = std::min(
 269         media_segment_start_time_, buffers.front()->GetDecodeTimestamp());
 270     const BufferQueue* buffers_for_new_range = &buffers;
 271     BufferQueue trimmed_buffers;
 272
 273     // If the new range is not being created because of a new media
 274     // segment, then we must make sure that we start with a key frame.
 275     // This can happen if the GOP in the previous append gets destroyed
 276     // by a Remove() call.
 277     if (!new_media_segment_) {
 278       BufferQueue::const_iterator itr = buffers.begin();
 279
 280       // Scan past all the non-key-frames.
 281       while (itr != buffers.end() && !(*itr)->is_key_frame()) {
 282         ++itr;
 283       }
 284
 285       // If we didn't find a key frame, then update the last appended
 286       // buffer state and return.
 287       if (itr == buffers.end()) {
 288         last_appended_buffer_timestamp_ = buffers.back()->GetDecodeTimestamp();
 289         last_appended_buffer_is_keyframe_ = buffers.back()->is_key_frame();
 290         DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
 291                  << ": new buffers in the middle of media segment depend on"
 292                     "keyframe that has been removed, and contain no keyframes."
 293                     "Skipping further processing.";
 294         DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
 295                  << ": done. ranges_=" << RangesToString(ranges_);
 296         return true;
 297       } else if (itr != buffers.begin()) {
 298         // Copy the first key frame and everything after it into
 299         // |trimmed_buffers|.
 300         trimmed_buffers.assign(itr, buffers.end());
 301         buffers_for_new_range = &trimmed_buffers;
 302       }
 303
 304       new_range_start_time =
 305           buffers_for_new_range->front()->GetDecodeTimestamp();
 306     }
 307
 308     range_for_next_append_ =
 309         AddToRanges(new SourceBufferRange(
 310             TypeToGapPolicy(GetType()),
 311             *buffers_for_new_range, new_range_start_time,
 312             base::Bind(&SourceBufferStream::GetMaxInterbufferDistance,
 313                        base::Unretained(this))));
 314     last_appended_buffer_timestamp_ =
 315         buffers_for_new_range->back()->GetDecodeTimestamp();
 316     last_appended_buffer_is_keyframe_ =
 317         buffers_for_new_range->back()->is_key_frame();
 318   }
 319
 320   new_media_segment_ = false;
 321
 322   MergeWithAdjacentRangeIfNecessary(range_for_next_append_);
 323
 324   // Seek to try to fulfill a previous call to Seek().
 325   if (seek_pending_) {
 326     DCHECK(!selected_range_);
 327     DCHECK(deleted_buffers.empty());
 328     Seek(seek_buffer_timestamp_);
 329   }
 330
 331   if (!deleted_buffers.empty()) {
 332     DecodeTimestamp start_of_deleted =
 333         deleted_buffers.front()->GetDecodeTimestamp();
 334
 335     DCHECK(track_buffer_.empty() ||
 336            track_buffer_.back()->GetDecodeTimestamp() < start_of_deleted)
 337         << "decode timestamp "
 338         << track_buffer_.back()->GetDecodeTimestamp().InSecondsF() << " sec"
 339         << ", start_of_deleted " << start_of_deleted.InSecondsF()<< " sec";
 340
 341     track_buffer_.insert(track_buffer_.end(), deleted_buffers.begin(),
 342                          deleted_buffers.end());
 343     DVLOG(3) << __FUNCTION__ << " Added " << deleted_buffers.size()
 344              << " deleted buffers to track buffer. TB size is now "
 345              << track_buffer_.size();
 346   } else {
 347     DVLOG(3) << __FUNCTION__ << " No deleted buffers for track buffer";
 348   }
 349
 350   // Prune any extra buffers in |track_buffer_| if new keyframes
 351   // are appended to the range covered by |track_buffer_|.
 352   if (!track_buffer_.empty()) {
 353     DecodeTimestamp keyframe_timestamp =
 354         FindKeyframeAfterTimestamp(track_buffer_.front()->GetDecodeTimestamp());
 355     if (keyframe_timestamp != kNoDecodeTimestamp())
 356       PruneTrackBuffer(keyframe_timestamp);
 357   }
 358
 359   SetSelectedRangeIfNeeded(next_buffer_timestamp);
 360
 361   GarbageCollectIfNeeded();
 362
 363   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
 364            << ": done. ranges_=" << RangesToString(ranges_);
 365   DCHECK(IsRangeListSorted(ranges_));
 366   DCHECK(OnlySelectedRangeIsSeeked());
 367   return true;
 368 }
 369
 370 void SourceBufferStream::Remove(base::TimeDelta start, base::TimeDelta end,
 371                                 base::TimeDelta duration) {
 372   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
 373            << " (" << start.InSecondsF() << ", " << end.InSecondsF()
 374            << ", " << duration.InSecondsF() << ")";
 375   DCHECK(start >= base::TimeDelta()) << start.InSecondsF();
 376   DCHECK(start < end) << "start " << start.InSecondsF()
 377                       << " end " << end.InSecondsF();
 378   DCHECK(duration != kNoTimestamp());
 379
 380   DecodeTimestamp start_dts = DecodeTimestamp::FromPresentationTime(start);
 381   DecodeTimestamp end_dts = DecodeTimestamp::FromPresentationTime(end);
 382   DecodeTimestamp remove_end_timestamp =
 383       DecodeTimestamp::FromPresentationTime(duration);
 384   DecodeTimestamp keyframe_timestamp = FindKeyframeAfterTimestamp(end_dts);
 385   if (keyframe_timestamp != kNoDecodeTimestamp()) {
 386     remove_end_timestamp = keyframe_timestamp;
 387   } else if (end_dts < remove_end_timestamp) {
 388     remove_end_timestamp = end_dts;
 389   }
 390
 391   BufferQueue deleted_buffers;
 392   RemoveInternal(start_dts, remove_end_timestamp, false, &deleted_buffers);
 393
 394   if (!deleted_buffers.empty()) {
 395     // Buffers for the current position have been removed.
 396     SetSelectedRangeIfNeeded(deleted_buffers.front()->GetDecodeTimestamp());
 397     if (last_output_buffer_timestamp_ == kNoDecodeTimestamp()) {
 398       // We just removed buffers for the current playback position for this
 399       // stream, yet we also had output no buffer since the last Seek.
 400       // Re-seek to prevent stall.
 401       DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
 402                << ": re-seeking to " << seek_buffer_timestamp_
 403                << " to prevent stall if this time becomes buffered again";
 404       Seek(seek_buffer_timestamp_);
 405     }
 406   }
 407 }
 408
 409 void SourceBufferStream::RemoveInternal(DecodeTimestamp start,
 410                                         DecodeTimestamp end,
 411                                         bool exclude_start,
 412                                         BufferQueue* deleted_buffers) {
 413   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName() << " ("
 414            << start.InSecondsF() << ", " << end.InSecondsF() << ", "
 415            << exclude_start << ")";
 416   DVLOG(3) << __FUNCTION__ << " " << GetStreamTypeName()
 417            << ": before remove ranges_=" << RangesToString(ranges_);
 418
 419   DCHECK(start >= DecodeTimestamp());
 420   DCHECK(start < end) << "start " << start.InSecondsF()
 421                       << " end " << end.InSecondsF();
 422   DCHECK(deleted_buffers);
 423
 424   RangeList::iterator itr = ranges_.begin();
 425
 426   while (itr != ranges_.end()) {
 427     SourceBufferRange* range = *itr;
 428     if (range->GetStartTimestamp() >= end)
 429       break;
 430
 431     // Split off any remaining GOPs starting at or after |end| and add it to
 432     // |ranges_|.
 433     SourceBufferRange* new_range = range->SplitRange(end);
 434     if (new_range) {
 435       itr = ranges_.insert(++itr, new_range);
 436       --itr;
 437
 438       // Update the selected range if the next buffer position was transferred
 439       // to |new_range|.
 440       if (new_range->HasNextBufferPosition())
 441         SetSelectedRange(new_range);
 442     }
 443
 444     // Truncate the current range so that it only contains data before
 445     // the removal range.
 446     BufferQueue saved_buffers;
 447     bool delete_range = range->TruncateAt(start, &saved_buffers, exclude_start);
 448
 449     // Check to see if the current playback position was removed and
 450     // update the selected range appropriately.
 451     if (!saved_buffers.empty()) {
 452       DCHECK(!range->HasNextBufferPosition());
 453       DCHECK(deleted_buffers->empty());
 454
 455       *deleted_buffers = saved_buffers;
 456     }
 457
 458     if (range == selected_range_ && !range->HasNextBufferPosition())
 459       SetSelectedRange(NULL);
 460
 461     // If the current range now is completely covered by the removal
 462     // range then delete it and move on.
 463     if (delete_range) {
 464       DeleteAndRemoveRange(&itr);
 465       continue;
 466     }
 467
 468     // Clear |range_for_next_append_| if we determine that the removal
 469     // operation makes it impossible for the next append to be added
 470     // to the current range.
 471     if (range_for_next_append_ != ranges_.end() &&
 472         *range_for_next_append_ == range &&
 473         last_appended_buffer_timestamp_ != kNoDecodeTimestamp()) {
 474       DecodeTimestamp potential_next_append_timestamp =
 475           last_appended_buffer_timestamp_ +
 476           base::TimeDelta::FromInternalValue(1);
 477
 478       if (!range->BelongsToRange(potential_next_append_timestamp)) {
 479         DVLOG(1) << "Resetting range_for_next_append_ since the next append"
 480                  <<  " can't add to the current range.";
 481         range_for_next_append_ =
 482             FindExistingRangeFor(potential_next_append_timestamp);
 483       }
 484     }
 485
 486     // Move on to the next range.
 487     ++itr;
 488   }
 489
 490   DVLOG(3) << __FUNCTION__ << " " << GetStreamTypeName()
 491            << ": after remove ranges_=" << RangesToString(ranges_);
 492
 493   DCHECK(IsRangeListSorted(ranges_));
 494   DCHECK(OnlySelectedRangeIsSeeked());
 495 }
 496
 497 void SourceBufferStream::ResetSeekState() {
 498   SetSelectedRange(NULL);
 499   track_buffer_.clear();
 500   config_change_pending_ = false;
 501   last_output_buffer_timestamp_ = kNoDecodeTimestamp();
 502   splice_buffers_index_ = 0;
 503   pending_buffer_ = NULL;
 504   pending_buffers_complete_ = false;
 505 }
 506
 507 bool SourceBufferStream::ShouldSeekToStartOfBuffered(
 508     base::TimeDelta seek_timestamp) const {
 509   if (ranges_.empty())
 510     return false;
 511   base::TimeDelta beginning_of_buffered =
 512       ranges_.front()->GetStartTimestamp().ToPresentationTime();
 513   return (seek_timestamp <= beginning_of_buffered &&
 514           beginning_of_buffered < kSeekToStartFudgeRoom());
 515 }
 516
 517 bool SourceBufferStream::IsMonotonicallyIncreasing(
 518     const BufferQueue& buffers) const {
 519   DCHECK(!buffers.empty());
 520   DecodeTimestamp prev_timestamp = last_appended_buffer_timestamp_;
 521   bool prev_is_keyframe = last_appended_buffer_is_keyframe_;
 522   for (BufferQueue::const_iterator itr = buffers.begin();
 523        itr != buffers.end(); ++itr) {
 524     DecodeTimestamp current_timestamp = (*itr)->GetDecodeTimestamp();
 525     bool current_is_keyframe = (*itr)->is_key_frame();
 526     DCHECK(current_timestamp != kNoDecodeTimestamp());
 527     DCHECK((*itr)->duration() >= base::TimeDelta())
 528         << "Packet with invalid duration."
 529         << " pts " << (*itr)->timestamp().InSecondsF()
 530         << " dts " << (*itr)->GetDecodeTimestamp().InSecondsF()
 531         << " dur " << (*itr)->duration().InSecondsF();
 532
 533     if (prev_timestamp != kNoDecodeTimestamp()) {
 534       if (current_timestamp < prev_timestamp) {
 535         MEDIA_LOG(ERROR, media_log_)
 536             << "Buffers did not monotonically increase.";
 537         return false;
 538       }
 539
 540       if (current_timestamp == prev_timestamp &&
 541           !SourceBufferRange::AllowSameTimestamp(prev_is_keyframe,
 542                                                  current_is_keyframe)) {
 543         MEDIA_LOG(ERROR, media_log_) << "Unexpected combination of buffers with"
 544                                      << " the same timestamp detected at "
 545                                      << current_timestamp.InSecondsF();
 546         return false;
 547       }
 548     }
 549
 550     prev_timestamp = current_timestamp;
 551     prev_is_keyframe = current_is_keyframe;
 552   }
 553   return true;
 554 }
 555
 556 bool SourceBufferStream::IsNextTimestampValid(
 557     DecodeTimestamp next_timestamp, bool next_is_keyframe) const {
 558   return (last_appended_buffer_timestamp_ != next_timestamp) ||
 559       new_media_segment_ ||
 560       SourceBufferRange::AllowSameTimestamp(last_appended_buffer_is_keyframe_,
 561                                             next_is_keyframe);
 562 }
 563
 564
 565 bool SourceBufferStream::OnlySelectedRangeIsSeeked() const {
 566   for (RangeList::const_iterator itr = ranges_.begin();
 567        itr != ranges_.end(); ++itr) {
 568     if ((*itr)->HasNextBufferPosition() && (*itr) != selected_range_)
 569       return false;
 570   }
 571   return !selected_range_ || selected_range_->HasNextBufferPosition();
 572 }
 573
 574 void SourceBufferStream::UpdateMaxInterbufferDistance(
 575     const BufferQueue& buffers) {
 576   DCHECK(!buffers.empty());
 577   DecodeTimestamp prev_timestamp = last_appended_buffer_timestamp_;
 578   for (BufferQueue::const_iterator itr = buffers.begin();
 579        itr != buffers.end(); ++itr) {
 580     DecodeTimestamp current_timestamp = (*itr)->GetDecodeTimestamp();
 581     DCHECK(current_timestamp != kNoDecodeTimestamp());
 582
 583     base::TimeDelta interbuffer_distance = (*itr)->duration();
 584     DCHECK(interbuffer_distance >= base::TimeDelta());
 585
 586     if (prev_timestamp != kNoDecodeTimestamp()) {
 587       interbuffer_distance =
 588           std::max(current_timestamp - prev_timestamp, interbuffer_distance);
 589     }
 590
 591     if (interbuffer_distance > base::TimeDelta()) {
 592       if (max_interbuffer_distance_ == kNoTimestamp()) {
 593         max_interbuffer_distance_ = interbuffer_distance;
 594       } else {
 595         max_interbuffer_distance_ =
 596             std::max(max_interbuffer_distance_, interbuffer_distance);
 597       }
 598     }
 599     prev_timestamp = current_timestamp;
 600   }
 601 }
 602
 603 void SourceBufferStream::SetConfigIds(const BufferQueue& buffers) {
 604   for (BufferQueue::const_iterator itr = buffers.begin();
 605        itr != buffers.end(); ++itr) {
 606     (*itr)->SetConfigId(append_config_index_);
 607   }
 608 }
 609
 610 void SourceBufferStream::GarbageCollectIfNeeded() {
 611   // Compute size of |ranges_|.
 612   int ranges_size = 0;
 613   for (RangeList::iterator itr = ranges_.begin(); itr != ranges_.end(); ++itr)
 614     ranges_size += (*itr)->size_in_bytes();
 615
 616   // Return if we're under or at the memory limit.
 617   if (ranges_size <= memory_limit_)
 618     return;
 619
 620   int bytes_to_free = ranges_size - memory_limit_;
 621
 622   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName() << ": Before GC"
 623            << " ranges_size=" << ranges_size
 624            << " ranges_=" << RangesToString(ranges_)
 625            << " memory_limit_=" << memory_limit_;
 626
 627   // Begin deleting after the last appended buffer.
 628   int bytes_freed = FreeBuffersAfterLastAppended(bytes_to_free);
 629
 630   // Begin deleting from the front.
 631   if (bytes_to_free - bytes_freed > 0)
 632     bytes_freed += FreeBuffers(bytes_to_free - bytes_freed, false);
 633
 634   // Begin deleting from the back.
 635   if (bytes_to_free - bytes_freed > 0)
 636     bytes_freed += FreeBuffers(bytes_to_free - bytes_freed, true);
 637
 638   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName() << ": After GC"
 639            << " bytes_freed=" << bytes_freed
 640            << " ranges_=" << RangesToString(ranges_);
 641 }
 642
 643 int SourceBufferStream::FreeBuffersAfterLastAppended(int total_bytes_to_free) {
 644   DecodeTimestamp next_buffer_timestamp = GetNextBufferTimestamp();
 645   if (last_appended_buffer_timestamp_ == kNoDecodeTimestamp() ||
 646       next_buffer_timestamp == kNoDecodeTimestamp() ||
 647       last_appended_buffer_timestamp_ >= next_buffer_timestamp) {
 648     return 0;
 649   }
 650
 651   DecodeTimestamp remove_range_start = last_appended_buffer_timestamp_;
 652   if (last_appended_buffer_is_keyframe_)
 653     remove_range_start += GetMaxInterbufferDistance();
 654
 655   DecodeTimestamp remove_range_start_keyframe = FindKeyframeAfterTimestamp(
 656       remove_range_start);
 657   if (remove_range_start_keyframe != kNoDecodeTimestamp())
 658     remove_range_start = remove_range_start_keyframe;
 659   if (remove_range_start >= next_buffer_timestamp)
 660     return 0;
 661
 662   DecodeTimestamp remove_range_end;
 663   int bytes_freed = GetRemovalRange(
 664       remove_range_start, next_buffer_timestamp, total_bytes_to_free,
 665       &remove_range_end);
 666   if (bytes_freed > 0) {
 667     Remove(remove_range_start.ToPresentationTime(),
 668            remove_range_end.ToPresentationTime(),
 669            next_buffer_timestamp.ToPresentationTime());
 670   }
 671
 672   return bytes_freed;
 673 }
 674
 675 int SourceBufferStream::GetRemovalRange(
 676     DecodeTimestamp start_timestamp, DecodeTimestamp end_timestamp,
 677     int total_bytes_to_free, DecodeTimestamp* removal_end_timestamp) {
 678   DCHECK(start_timestamp >= DecodeTimestamp()) << start_timestamp.InSecondsF();
 679   DCHECK(start_timestamp < end_timestamp)
 680       << "start " << start_timestamp.InSecondsF()
 681       << ", end " << end_timestamp.InSecondsF();
 682
 683   int bytes_to_free = total_bytes_to_free;
 684   int bytes_freed = 0;
 685
 686   for (RangeList::iterator itr = ranges_.begin();
 687        itr != ranges_.end() && bytes_to_free > 0; ++itr) {
 688     SourceBufferRange* range = *itr;
 689     if (range->GetStartTimestamp() >= end_timestamp)
 690       break;
 691     if (range->GetEndTimestamp() < start_timestamp)
 692       continue;
 693
 694     int bytes_removed = range->GetRemovalGOP(
 695         start_timestamp, end_timestamp, bytes_to_free, removal_end_timestamp);
 696     bytes_to_free -= bytes_removed;
 697     bytes_freed += bytes_removed;
 698   }
 699   return bytes_freed;
 700 }
 701
 702 int SourceBufferStream::FreeBuffers(int total_bytes_to_free,
 703                                     bool reverse_direction) {
 704   TRACE_EVENT2("media", "SourceBufferStream::FreeBuffers",
 705                "total bytes to free", total_bytes_to_free,
 706                "reverse direction", reverse_direction);
 707
 708   DCHECK_GT(total_bytes_to_free, 0);
 709   int bytes_to_free = total_bytes_to_free;
 710   int bytes_freed = 0;
 711
 712   // This range will save the last GOP appended to |range_for_next_append_|
 713   // if the buffers surrounding it get deleted during garbage collection.
 714   SourceBufferRange* new_range_for_append = NULL;
 715
 716   while (!ranges_.empty() && bytes_to_free > 0) {
 717     SourceBufferRange* current_range = NULL;
 718     BufferQueue buffers;
 719     int bytes_deleted = 0;
 720
 721     if (reverse_direction) {
 722       current_range = ranges_.back();
 723       if (current_range->LastGOPContainsNextBufferPosition()) {
 724         DCHECK_EQ(current_range, selected_range_);
 725         break;
 726       }
 727       bytes_deleted = current_range->DeleteGOPFromBack(&buffers);
 728     } else {
 729       current_range = ranges_.front();
 730       if (current_range->FirstGOPContainsNextBufferPosition()) {
 731         DCHECK_EQ(current_range, selected_range_);
 732         break;
 733       }
 734       bytes_deleted = current_range->DeleteGOPFromFront(&buffers);
 735     }
 736
 737     // Check to see if we've just deleted the GOP that was last appended.
 738     DecodeTimestamp end_timestamp = buffers.back()->GetDecodeTimestamp();
 739     if (end_timestamp == last_appended_buffer_timestamp_) {
 740       DCHECK(last_appended_buffer_timestamp_ != kNoDecodeTimestamp());
 741       DCHECK(!new_range_for_append);
 742       // Create a new range containing these buffers.
 743       new_range_for_append = new SourceBufferRange(
 744           TypeToGapPolicy(GetType()),
 745           buffers, kNoDecodeTimestamp(),
 746           base::Bind(&SourceBufferStream::GetMaxInterbufferDistance,
 747                      base::Unretained(this)));
 748       range_for_next_append_ = ranges_.end();
 749     } else {
 750       bytes_to_free -= bytes_deleted;
 751       bytes_freed += bytes_deleted;
 752     }
 753
 754     if (current_range->size_in_bytes() == 0) {
 755       DCHECK_NE(current_range, selected_range_);
 756       DCHECK(range_for_next_append_ == ranges_.end() ||
 757              *range_for_next_append_ != current_range);
 758       delete current_range;
 759       reverse_direction ? ranges_.pop_back() : ranges_.pop_front();
 760     }
 761   }
 762
 763   // Insert |new_range_for_append| into |ranges_|, if applicable.
 764   if (new_range_for_append) {
 765     range_for_next_append_ = AddToRanges(new_range_for_append);
 766     DCHECK(range_for_next_append_ != ranges_.end());
 767
 768     // Check to see if we need to merge |new_range_for_append| with the range
 769     // before or after it. |new_range_for_append| is created whenever the last
 770     // GOP appended is encountered, regardless of whether any buffers after it
 771     // are ultimately deleted. Merging is necessary if there were no buffers
 772     // (or very few buffers) deleted after creating |new_range_for_append|.
 773     if (range_for_next_append_ != ranges_.begin()) {
 774       RangeList::iterator range_before_next = range_for_next_append_;
 775       --range_before_next;
 776       MergeWithAdjacentRangeIfNecessary(range_before_next);
 777     }
 778     MergeWithAdjacentRangeIfNecessary(range_for_next_append_);
 779   }
 780   return bytes_freed;
 781 }
 782
 783 void SourceBufferStream::PrepareRangesForNextAppend(
 784     const BufferQueue& new_buffers, BufferQueue* deleted_buffers) {
 785   DCHECK(deleted_buffers);
 786
 787   bool temporarily_select_range = false;
 788   if (!track_buffer_.empty()) {
 789     DecodeTimestamp tb_timestamp = track_buffer_.back()->GetDecodeTimestamp();
 790     DecodeTimestamp seek_timestamp = FindKeyframeAfterTimestamp(tb_timestamp);
 791     if (seek_timestamp != kNoDecodeTimestamp() &&
 792         seek_timestamp < new_buffers.front()->GetDecodeTimestamp() &&
 793         range_for_next_append_ != ranges_.end() &&
 794         (*range_for_next_append_)->BelongsToRange(seek_timestamp)) {
 795       DCHECK(tb_timestamp < seek_timestamp);
 796       DCHECK(!selected_range_);
 797       DCHECK(!(*range_for_next_append_)->HasNextBufferPosition());
 798
 799       // If there are GOPs between the end of the track buffer and the
 800       // beginning of the new buffers, then temporarily seek the range
 801       // so that the buffers between these two times will be deposited in
 802       // |deleted_buffers| as if they were part of the current playback
 803       // position.
 804       // TODO(acolwell): Figure out a more elegant way to do this.
 805       SeekAndSetSelectedRange(*range_for_next_append_, seek_timestamp);
 806       temporarily_select_range = true;
 807     }
 808   }
 809
 810   // Handle splices between the existing buffers and the new buffers.  If a
 811   // splice is generated the timestamp and duration of the first buffer in
 812   // |new_buffers| will be modified.
 813   if (splice_frames_enabled_)
 814     GenerateSpliceFrame(new_buffers);
 815
 816   DecodeTimestamp prev_timestamp = last_appended_buffer_timestamp_;
 817   bool prev_is_keyframe = last_appended_buffer_is_keyframe_;
 818   DecodeTimestamp next_timestamp = new_buffers.front()->GetDecodeTimestamp();
 819   bool next_is_keyframe = new_buffers.front()->is_key_frame();
 820
 821   if (prev_timestamp != kNoDecodeTimestamp() &&
 822       prev_timestamp != next_timestamp) {
 823     // Clean up the old buffers between the last appended buffer and the
 824     // beginning of |new_buffers|.
 825     RemoveInternal(prev_timestamp, next_timestamp, true, deleted_buffers);
 826   }
 827
 828   // Make the delete range exclusive if we are dealing with an allowed same
 829   // timestamp situation. This prevents the first buffer in the current append
 830   // from deleting the last buffer in the previous append if both buffers
 831   // have the same timestamp.
 832   //
 833   // The delete range should never be exclusive if a splice frame was generated
 834   // because we don't generate splice frames for same timestamp situations.
 835   DCHECK(new_buffers.front()->splice_timestamp() !=
 836          new_buffers.front()->timestamp());
 837   const bool exclude_start =
 838       new_buffers.front()->splice_buffers().empty() &&
 839       prev_timestamp == next_timestamp &&
 840       SourceBufferRange::AllowSameTimestamp(prev_is_keyframe, next_is_keyframe);
 841
 842   // Delete the buffers that |new_buffers| overlaps.
 843   DecodeTimestamp start = new_buffers.front()->GetDecodeTimestamp();
 844   DecodeTimestamp end = new_buffers.back()->GetDecodeTimestamp();
 845   base::TimeDelta duration = new_buffers.back()->duration();
 846
 847   // Set end time for remove to include the duration of last buffer. If the
 848   // duration is estimated, use 1 microsecond instead to ensure frames are not
 849   // accidentally removed due to over-estimation.
 850   if (duration != kNoTimestamp() && duration > base::TimeDelta() &&
 851       !new_buffers.back()->is_duration_estimated()) {
 852     end += duration;
 853   } else {
 854     // TODO(chcunningham): Emit warning when 0ms durations are not expected.
 855     // http://crbug.com/312836
 856     end += base::TimeDelta::FromInternalValue(1);
 857   }
 858
 859   RemoveInternal(start, end, exclude_start, deleted_buffers);
 860
 861   // Restore the range seek state if necessary.
 862   if (temporarily_select_range)
 863     SetSelectedRange(NULL);
 864 }
 865
 866 bool SourceBufferStream::AreAdjacentInSequence(
 867     DecodeTimestamp first_timestamp, DecodeTimestamp second_timestamp) const {
 868   return first_timestamp < second_timestamp &&
 869       second_timestamp <=
 870       first_timestamp + ComputeFudgeRoom(GetMaxInterbufferDistance());
 871 }
 872
 873 void SourceBufferStream::PruneTrackBuffer(const DecodeTimestamp timestamp) {
 874   // If we don't have the next timestamp, we don't have anything to delete.
 875   if (timestamp == kNoDecodeTimestamp())
 876     return;
 877
 878   while (!track_buffer_.empty() &&
 879          track_buffer_.back()->GetDecodeTimestamp() >= timestamp) {
 880     track_buffer_.pop_back();
 881   }
 882 }
 883
 884 void SourceBufferStream::MergeWithAdjacentRangeIfNecessary(
 885     const RangeList::iterator& range_with_new_buffers_itr) {
 886   DCHECK(range_with_new_buffers_itr != ranges_.end());
 887
 888   SourceBufferRange* range_with_new_buffers = *range_with_new_buffers_itr;
 889   RangeList::iterator next_range_itr = range_with_new_buffers_itr;
 890   ++next_range_itr;
 891
 892   if (next_range_itr == ranges_.end() ||
 893       !range_with_new_buffers->CanAppendRangeToEnd(**next_range_itr)) {
 894     return;
 895   }
 896
 897   bool transfer_current_position = selected_range_ == *next_range_itr;
 898   DVLOG(3) << __FUNCTION__ << " " << GetStreamTypeName()
 899            << " merging " << RangeToString(*range_with_new_buffers)
 900            << " into " << RangeToString(**next_range_itr);
 901   range_with_new_buffers->AppendRangeToEnd(**next_range_itr,
 902                                            transfer_current_position);
 903   // Update |selected_range_| pointer if |range| has become selected after
 904   // merges.
 905   if (transfer_current_position)
 906     SetSelectedRange(range_with_new_buffers);
 907
 908   if (next_range_itr == range_for_next_append_)
 909     range_for_next_append_ = range_with_new_buffers_itr;
 910
 911   DeleteAndRemoveRange(&next_range_itr);
 912 }
 913
 914 void SourceBufferStream::Seek(base::TimeDelta timestamp) {
 915   DCHECK(timestamp >= base::TimeDelta());
 916   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
 917            << " (" << timestamp.InSecondsF() << ")";
 918   ResetSeekState();
 919
 920   seek_buffer_timestamp_ = timestamp;
 921   seek_pending_ = true;
 922
 923   if (ShouldSeekToStartOfBuffered(timestamp)) {
 924     ranges_.front()->SeekToStart();
 925     SetSelectedRange(ranges_.front());
 926     seek_pending_ = false;
 927     return;
 928   }
 929
 930   DecodeTimestamp seek_dts = DecodeTimestamp::FromPresentationTime(timestamp);
 931
 932   RangeList::iterator itr = ranges_.end();
 933   for (itr = ranges_.begin(); itr != ranges_.end(); ++itr) {
 934     if ((*itr)->CanSeekTo(seek_dts))
 935       break;
 936   }
 937
 938   if (itr == ranges_.end())
 939     return;
 940
 941   SeekAndSetSelectedRange(*itr, seek_dts);
 942   seek_pending_ = false;
 943 }
 944
 945 bool SourceBufferStream::IsSeekPending() const {
 946   return seek_pending_ && !IsEndOfStreamReached();
 947 }
 948
 949 void SourceBufferStream::OnSetDuration(base::TimeDelta duration) {
 950   DecodeTimestamp duration_dts =
 951       DecodeTimestamp::FromPresentationTime(duration);
 952   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
 953            << " (" << duration.InSecondsF() << ")";
 954
 955   RangeList::iterator itr = ranges_.end();
 956   for (itr = ranges_.begin(); itr != ranges_.end(); ++itr) {
 957     if ((*itr)->GetEndTimestamp() > duration_dts)
 958       break;
 959   }
 960   if (itr == ranges_.end())
 961     return;
 962
 963   // Need to partially truncate this range.
 964   if ((*itr)->GetStartTimestamp() < duration_dts) {
 965     bool delete_range = (*itr)->TruncateAt(duration_dts, NULL, false);
 966     if ((*itr == selected_range_) && !selected_range_->HasNextBufferPosition())
 967       SetSelectedRange(NULL);
 968
 969     if (delete_range) {
 970       DeleteAndRemoveRange(&itr);
 971     } else {
 972       ++itr;
 973     }
 974   }
 975
 976   // Delete all ranges that begin after |duration_dts|.
 977   while (itr != ranges_.end()) {
 978     // If we're about to delete the selected range, also reset the seek state.
 979     DCHECK((*itr)->GetStartTimestamp() >= duration_dts);
 980     if (*itr == selected_range_)
 981       ResetSeekState();
 982     DeleteAndRemoveRange(&itr);
 983   }
 984 }
 985
 986 SourceBufferStream::Status SourceBufferStream::GetNextBuffer(
 987     scoped_refptr<StreamParserBuffer>* out_buffer) {
 988   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName();
 989   if (!pending_buffer_.get()) {
 990     const SourceBufferStream::Status status = GetNextBufferInternal(out_buffer);
 991     if (status != SourceBufferStream::kSuccess ||
 992         !SetPendingBuffer(out_buffer)) {
 993       DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName()
 994                << ": no pending buffer, returning status " << status;
 995       return status;
 996     }
 997   }
 998
 999   if (!pending_buffer_->splice_buffers().empty()) {
1000     const SourceBufferStream::Status status =
1001         HandleNextBufferWithSplice(out_buffer);
1002     DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName()
1003              << ": handled next buffer with splice, returning status "
1004              << status;
1005     return status;
1006   }
1007
1008   DCHECK(pending_buffer_->preroll_buffer().get());
1009
1010   const SourceBufferStream::Status status =
1011       HandleNextBufferWithPreroll(out_buffer);
1012   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName()
1013            << ": handled next buffer with preroll, returning status "
1014            << status;
1015   return status;
1016 }
1017
1018 SourceBufferStream::Status SourceBufferStream::HandleNextBufferWithSplice(
1019     scoped_refptr<StreamParserBuffer>* out_buffer) {
1020   const BufferQueue& splice_buffers = pending_buffer_->splice_buffers();
1021   const size_t last_splice_buffer_index = splice_buffers.size() - 1;
1022
1023   // Are there any splice buffers left to hand out?  The last buffer should be
1024   // handed out separately since it represents the first post-splice buffer.
1025   if (splice_buffers_index_ < last_splice_buffer_index) {
1026     // Account for config changes which occur between fade out buffers.
1027     if (current_config_index_ !=
1028         splice_buffers[splice_buffers_index_]->GetConfigId()) {
1029       config_change_pending_ = true;
1030       DVLOG(1) << "Config change (splice buffer config ID does not match).";
1031       return SourceBufferStream::kConfigChange;
1032     }
1033
1034     // Every pre splice buffer must have the same splice_timestamp().
1035     DCHECK(pending_buffer_->splice_timestamp() ==
1036            splice_buffers[splice_buffers_index_]->splice_timestamp());
1037
1038     // No pre splice buffers should have preroll.
1039     DCHECK(!splice_buffers[splice_buffers_index_]->preroll_buffer().get());
1040
1041     *out_buffer = splice_buffers[splice_buffers_index_++];
1042     return SourceBufferStream::kSuccess;
1043   }
1044
1045   // Did we hand out the last pre-splice buffer on the previous call?
1046   if (!pending_buffers_complete_) {
1047     DCHECK_EQ(splice_buffers_index_, last_splice_buffer_index);
1048     pending_buffers_complete_ = true;
1049     config_change_pending_ = true;
1050     DVLOG(1) << "Config change (forced for fade in of splice frame).";
1051     return SourceBufferStream::kConfigChange;
1052   }
1053
1054   // All pre-splice buffers have been handed out and a config change completed,
1055   // so hand out the final buffer for fade in.  Because a config change is
1056   // always issued prior to handing out this buffer, any changes in config id
1057   // have been inherently handled.
1058   DCHECK(pending_buffers_complete_);
1059   DCHECK_EQ(splice_buffers_index_, splice_buffers.size() - 1);
1060   DCHECK(splice_buffers.back()->splice_timestamp() == kNoTimestamp());
1061   *out_buffer = splice_buffers.back();
1062   pending_buffer_ = NULL;
1063
1064   // If the last splice buffer has preroll, hand off to the preroll handler.
1065   return SetPendingBuffer(out_buffer) ? HandleNextBufferWithPreroll(out_buffer)
1066                                       : SourceBufferStream::kSuccess;
1067 }
1068
1069 SourceBufferStream::Status SourceBufferStream::HandleNextBufferWithPreroll(
1070     scoped_refptr<StreamParserBuffer>* out_buffer) {
1071   // Any config change should have already been handled.
1072   DCHECK_EQ(current_config_index_, pending_buffer_->GetConfigId());
1073
1074   // Check if the preroll buffer has already been handed out.
1075   if (!pending_buffers_complete_) {
1076     pending_buffers_complete_ = true;
1077     *out_buffer = pending_buffer_->preroll_buffer();
1078     return SourceBufferStream::kSuccess;
1079   }
1080
1081   // Preroll complete, hand out the final buffer.
1082   *out_buffer = pending_buffer_;
1083   pending_buffer_ = NULL;
1084   return SourceBufferStream::kSuccess;
1085 }
1086
1087 SourceBufferStream::Status SourceBufferStream::GetNextBufferInternal(
1088     scoped_refptr<StreamParserBuffer>* out_buffer) {
1089   CHECK(!config_change_pending_);
1090
1091   if (!track_buffer_.empty()) {
1092     DCHECK(!selected_range_);
1093     scoped_refptr<StreamParserBuffer>& next_buffer = track_buffer_.front();
1094
1095     // If the next buffer is an audio splice frame, the next effective config id
1096     // comes from the first splice buffer.
1097     if (next_buffer->GetSpliceBufferConfigId(0) != current_config_index_) {
1098       config_change_pending_ = true;
1099       DVLOG(1) << "Config change (track buffer config ID does not match).";
1100       return kConfigChange;
1101     }
1102
1103     DVLOG(3) << __FUNCTION__ << " Next buffer coming from track_buffer_";
1104     *out_buffer = next_buffer;
1105     track_buffer_.pop_front();
1106     last_output_buffer_timestamp_ = (*out_buffer)->GetDecodeTimestamp();
1107
1108     // If the track buffer becomes empty, then try to set the selected range
1109     // based on the timestamp of this buffer being returned.
1110     if (track_buffer_.empty())
1111       SetSelectedRangeIfNeeded(last_output_buffer_timestamp_);
1112
1113     return kSuccess;
1114   }
1115
1116   DCHECK(track_buffer_.empty());
1117   if (!selected_range_ || !selected_range_->HasNextBuffer()) {
1118     if (IsEndOfStreamReached()) {
1119       return kEndOfStream;
1120     }
1121     DVLOG(3) << __FUNCTION__ << " " << GetStreamTypeName()
1122              << ": returning kNeedBuffer "
1123              << (selected_range_ ? "(selected range has no next buffer)"
1124                                  : "(no selected range)");
1125     return kNeedBuffer;
1126   }
1127
1128   if (selected_range_->GetNextConfigId() != current_config_index_) {
1129     config_change_pending_ = true;
1130     DVLOG(1) << "Config change (selected range config ID does not match).";
1131     return kConfigChange;
1132   }
1133
1134   CHECK(selected_range_->GetNextBuffer(out_buffer));
1135   last_output_buffer_timestamp_ = (*out_buffer)->GetDecodeTimestamp();
1136   return kSuccess;
1137 }
1138
1139 DecodeTimestamp SourceBufferStream::GetNextBufferTimestamp() {
1140   if (!track_buffer_.empty())
1141     return track_buffer_.front()->GetDecodeTimestamp();
1142
1143   if (!selected_range_)
1144     return kNoDecodeTimestamp();
1145
1146   DCHECK(selected_range_->HasNextBufferPosition());
1147   return selected_range_->GetNextTimestamp();
1148 }
1149
1150 SourceBufferStream::RangeList::iterator
1151 SourceBufferStream::FindExistingRangeFor(DecodeTimestamp start_timestamp) {
1152   for (RangeList::iterator itr = ranges_.begin(); itr != ranges_.end(); ++itr) {
1153     if ((*itr)->BelongsToRange(start_timestamp))
1154       return itr;
1155   }
1156   return ranges_.end();
1157 }
1158
1159 SourceBufferStream::RangeList::iterator
1160 SourceBufferStream::AddToRanges(SourceBufferRange* new_range) {
1161   DecodeTimestamp start_timestamp = new_range->GetStartTimestamp();
1162   RangeList::iterator itr = ranges_.end();
1163   for (itr = ranges_.begin(); itr != ranges_.end(); ++itr) {
1164     if ((*itr)->GetStartTimestamp() > start_timestamp)
1165       break;
1166   }
1167   return ranges_.insert(itr, new_range);
1168 }
1169
1170 SourceBufferStream::RangeList::iterator
1171 SourceBufferStream::GetSelectedRangeItr() {
1172   DCHECK(selected_range_);
1173   RangeList::iterator itr = ranges_.end();
1174   for (itr = ranges_.begin(); itr != ranges_.end(); ++itr) {
1175     if (*itr == selected_range_)
1176       break;
1177   }
1178   DCHECK(itr != ranges_.end());
1179   return itr;
1180 }
1181
1182 void SourceBufferStream::SeekAndSetSelectedRange(
1183     SourceBufferRange* range, DecodeTimestamp seek_timestamp) {
1184   if (range)
1185     range->Seek(seek_timestamp);
1186   SetSelectedRange(range);
1187 }
1188
1189 void SourceBufferStream::SetSelectedRange(SourceBufferRange* range) {
1190   DVLOG(1) << __FUNCTION__ << " " << GetStreamTypeName()
1191            << ": " << selected_range_ << " -> " << range;
1192   if (selected_range_)
1193     selected_range_->ResetNextBufferPosition();
1194   DCHECK(!range || range->HasNextBufferPosition());
1195   selected_range_ = range;
1196 }
1197
1198 Ranges<base::TimeDelta> SourceBufferStream::GetBufferedTime() const {
1199   Ranges<base::TimeDelta> ranges;
1200   for (RangeList::const_iterator itr = ranges_.begin();
1201        itr != ranges_.end(); ++itr) {
1202     ranges.Add((*itr)->GetStartTimestamp().ToPresentationTime(),
1203                (*itr)->GetBufferedEndTimestamp().ToPresentationTime());
1204   }
1205   return ranges;
1206 }
1207
1208 base::TimeDelta SourceBufferStream::GetBufferedDuration() const {
1209   if (ranges_.empty())
1210     return base::TimeDelta();
1211
1212   return ranges_.back()->GetBufferedEndTimestamp().ToPresentationTime();
1213 }
1214
1215 void SourceBufferStream::MarkEndOfStream() {
1216   DCHECK(!end_of_stream_);
1217   end_of_stream_ = true;
1218 }
1219
1220 void SourceBufferStream::UnmarkEndOfStream() {
1221   DCHECK(end_of_stream_);
1222   end_of_stream_ = false;
1223 }
1224
1225 bool SourceBufferStream::IsEndOfStreamReached() const {
1226   if (!end_of_stream_ || !track_buffer_.empty())
1227     return false;
1228
1229   if (ranges_.empty())
1230     return true;
1231
1232   if (seek_pending_) {
1233     base::TimeDelta last_range_end_time =
1234         ranges_.back()->GetBufferedEndTimestamp().ToPresentationTime();
1235     return seek_buffer_timestamp_ >= last_range_end_time;
1236   }
1237
1238   if (!selected_range_)
1239     return true;
1240
1241   return selected_range_ == ranges_.back();
1242 }
1243
1244 const AudioDecoderConfig& SourceBufferStream::GetCurrentAudioDecoderConfig() {
1245   if (config_change_pending_)
1246     CompleteConfigChange();
1247   return audio_configs_[current_config_index_];
1248 }
1249
1250 const VideoDecoderConfig& SourceBufferStream::GetCurrentVideoDecoderConfig() {
1251   if (config_change_pending_)
1252     CompleteConfigChange();
1253   return video_configs_[current_config_index_];
1254 }
1255
1256 const TextTrackConfig& SourceBufferStream::GetCurrentTextTrackConfig() {
1257   return text_track_config_;
1258 }
1259
1260 base::TimeDelta SourceBufferStream::GetMaxInterbufferDistance() const {
1261   if (max_interbuffer_distance_ == kNoTimestamp())
1262     return base::TimeDelta::FromMilliseconds(kDefaultBufferDurationInMs);
1263   return max_interbuffer_distance_;
1264 }
1265
1266 bool SourceBufferStream::UpdateAudioConfig(const AudioDecoderConfig& config) {
1267   DCHECK(!audio_configs_.empty());
1268   DCHECK(video_configs_.empty());
1269   DVLOG(3) << "UpdateAudioConfig.";
1270
1271   if (audio_configs_[0].codec() != config.codec()) {
1272     MEDIA_LOG(ERROR, media_log_) << "Audio codec changes not allowed.";
1273     return false;
1274   }
1275
1276   if (audio_configs_[0].is_encrypted() != config.is_encrypted()) {
1277     MEDIA_LOG(ERROR, media_log_) << "Audio encryption changes not allowed.";
1278     return false;
1279   }
1280
1281   // Check to see if the new config matches an existing one.
1282   for (size_t i = 0; i < audio_configs_.size(); ++i) {
1283     if (config.Matches(audio_configs_[i])) {
1284       append_config_index_ = i;
1285       return true;
1286     }
1287   }
1288
1289   // No matches found so let's add this one to the list.
1290   append_config_index_ = audio_configs_.size();
1291   DVLOG(2) << "New audio config - index: " << append_config_index_;
1292   audio_configs_.resize(audio_configs_.size() + 1);
1293   audio_configs_[append_config_index_] = config;
1294   return true;
1295 }
1296
1297 bool SourceBufferStream::UpdateVideoConfig(const VideoDecoderConfig& config) {
1298   DCHECK(!video_configs_.empty());
1299   DCHECK(audio_configs_.empty());
1300   DVLOG(3) << "UpdateVideoConfig.";
1301
1302   if (video_configs_[0].codec() != config.codec()) {
1303     MEDIA_LOG(ERROR, media_log_) << "Video codec changes not allowed.";
1304     return false;
1305   }
1306
1307   if (video_configs_[0].is_encrypted() != config.is_encrypted()) {
1308     MEDIA_LOG(ERROR, media_log_) << "Video encryption changes not allowed.";
1309     return false;
1310   }
1311
1312   // Check to see if the new config matches an existing one.
1313   for (size_t i = 0; i < video_configs_.size(); ++i) {
1314     if (config.Matches(video_configs_[i])) {
1315       append_config_index_ = i;
1316       return true;
1317     }
1318   }
1319
1320   // No matches found so let's add this one to the list.
1321   append_config_index_ = video_configs_.size();
1322   DVLOG(2) << "New video config - index: " << append_config_index_;
1323   video_configs_.resize(video_configs_.size() + 1);
1324   video_configs_[append_config_index_] = config;
1325   return true;
1326 }
1327
1328 void SourceBufferStream::CompleteConfigChange() {
1329   config_change_pending_ = false;
1330
1331   if (pending_buffer_.get()) {
1332     current_config_index_ =
1333         pending_buffer_->GetSpliceBufferConfigId(splice_buffers_index_);
1334     return;
1335   }
1336
1337   if (!track_buffer_.empty()) {
1338     current_config_index_ = track_buffer_.front()->GetSpliceBufferConfigId(0);
1339     return;
1340   }
1341
1342   if (selected_range_ && selected_range_->HasNextBuffer())
1343     current_config_index_ = selected_range_->GetNextConfigId();
1344 }
1345
1346 void SourceBufferStream::SetSelectedRangeIfNeeded(
1347     const DecodeTimestamp timestamp) {
1348   DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName()
1349            << "(" << timestamp.InSecondsF() << ")";
1350
1351   if (selected_range_) {
1352     DCHECK(track_buffer_.empty());
1353     return;
1354   }
1355
1356   if (!track_buffer_.empty()) {
1357     DCHECK(!selected_range_);
1358     return;
1359   }
1360
1361   DecodeTimestamp start_timestamp = timestamp;
1362
1363   // If the next buffer timestamp is not known then use a timestamp just after
1364   // the timestamp on the last buffer returned by GetNextBuffer().
1365   if (start_timestamp == kNoDecodeTimestamp()) {
1366     if (last_output_buffer_timestamp_ == kNoDecodeTimestamp()) {
1367       DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName()
1368                << " no previous output timestamp";
1369       return;
1370     }
1371
1372     start_timestamp = last_output_buffer_timestamp_ +
1373         base::TimeDelta::FromInternalValue(1);
1374   }
1375
1376   DecodeTimestamp seek_timestamp =
1377       FindNewSelectedRangeSeekTimestamp(start_timestamp);
1378
1379   // If we don't have buffered data to seek to, then return.
1380   if (seek_timestamp == kNoDecodeTimestamp()) {
1381       DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName()
1382                << " couldn't find new selected range seek timestamp";
1383       return;
1384   }
1385
1386   DCHECK(track_buffer_.empty());
1387   SeekAndSetSelectedRange(*FindExistingRangeFor(seek_timestamp),
1388                           seek_timestamp);
1389 }
1390
1391 DecodeTimestamp SourceBufferStream::FindNewSelectedRangeSeekTimestamp(
1392     const DecodeTimestamp start_timestamp) {
1393   DCHECK(start_timestamp != kNoDecodeTimestamp());
1394   DCHECK(start_timestamp >= DecodeTimestamp());
1395
1396   RangeList::iterator itr = ranges_.begin();
1397
1398   for (; itr != ranges_.end(); ++itr) {
1399     if ((*itr)->GetEndTimestamp() >= start_timestamp) {
1400       break;
1401     }
1402   }
1403
1404   if (itr == ranges_.end()) {
1405     DVLOG(2) << __FUNCTION__ << " " << GetStreamTypeName()
1406              << " no buffered data for dts=" << start_timestamp.InSecondsF();
1407     return kNoDecodeTimestamp();
1408   }
1409
1410   // First check for a keyframe timestamp >= |start_timestamp|
1411   // in the current range.
1412   DecodeTimestamp keyframe_timestamp =
1413       (*itr)->NextKeyframeTimestamp(start_timestamp);
1414
1415   if (keyframe_timestamp != kNoDecodeTimestamp())
1416     return keyframe_timestamp;
1417
1418   // If a keyframe was not found then look for a keyframe that is
1419   // "close enough" in the current or next range.
1420   DecodeTimestamp end_timestamp =
1421       start_timestamp + ComputeFudgeRoom(GetMaxInterbufferDistance());
1422   DCHECK(start_timestamp < end_timestamp);
1423
1424   // Make sure the current range doesn't start beyond |end_timestamp|.
1425   if ((*itr)->GetStartTimestamp() >= end_timestamp)
1426     return kNoDecodeTimestamp();
1427
1428   keyframe_timestamp = (*itr)->KeyframeBeforeTimestamp(end_timestamp);
1429
1430   // Check to see if the keyframe is within the acceptable range
1431   // (|start_timestamp|, |end_timestamp|].
1432   if (keyframe_timestamp != kNoDecodeTimestamp() &&
1433       start_timestamp < keyframe_timestamp  &&
1434       keyframe_timestamp <= end_timestamp) {
1435     return keyframe_timestamp;
1436   }
1437
1438   // If |end_timestamp| is within this range, then no other checks are
1439   // necessary.
1440   if (end_timestamp <= (*itr)->GetEndTimestamp())
1441     return kNoDecodeTimestamp();
1442
1443   // Move on to the next range.
1444   ++itr;
1445
1446   // Return early if the next range does not contain |end_timestamp|.
1447   if (itr == ranges_.end() || (*itr)->GetStartTimestamp() >= end_timestamp)
1448     return kNoDecodeTimestamp();
1449
1450   keyframe_timestamp = (*itr)->KeyframeBeforeTimestamp(end_timestamp);
1451
1452   // Check to see if the keyframe is within the acceptable range
1453   // (|start_timestamp|, |end_timestamp|].
1454   if (keyframe_timestamp != kNoDecodeTimestamp() &&
1455       start_timestamp < keyframe_timestamp  &&
1456       keyframe_timestamp <= end_timestamp) {
1457     return keyframe_timestamp;
1458   }
1459
1460   return kNoDecodeTimestamp();
1461 }
1462
1463 DecodeTimestamp SourceBufferStream::FindKeyframeAfterTimestamp(
1464     const DecodeTimestamp timestamp) {
1465   DCHECK(timestamp != kNoDecodeTimestamp());
1466
1467   RangeList::iterator itr = FindExistingRangeFor(timestamp);
1468
1469   if (itr == ranges_.end())
1470     return kNoDecodeTimestamp();
1471
1472   // First check for a keyframe timestamp >= |timestamp|
1473   // in the current range.
1474   return (*itr)->NextKeyframeTimestamp(timestamp);
1475 }
1476
1477 std::string SourceBufferStream::GetStreamTypeName() const {
1478   switch (GetType()) {
1479     case kAudio:
1480       return "AUDIO";
1481     case kVideo:
1482       return "VIDEO";
1483     case kText:
1484       return "TEXT";
1485   }
1486   NOTREACHED();
1487   return "";
1488 }
1489
1490 SourceBufferStream::Type SourceBufferStream::GetType() const {
1491   if (!audio_configs_.empty())
1492     return kAudio;
1493   if (!video_configs_.empty())
1494     return kVideo;
1495   DCHECK_NE(text_track_config_.kind(), kTextNone);
1496   return kText;
1497 }
1498
1499 void SourceBufferStream::DeleteAndRemoveRange(RangeList::iterator* itr) {
1500   DVLOG(1) << __FUNCTION__;
1501
1502   DCHECK(*itr != ranges_.end());
1503   if (**itr == selected_range_) {
1504     DVLOG(1) << __FUNCTION__ << " deleting selected range.";
1505     SetSelectedRange(NULL);
1506   }
1507
1508   if (*itr == range_for_next_append_) {
1509     DVLOG(1) << __FUNCTION__ << " deleting range_for_next_append_.";
1510     range_for_next_append_ = ranges_.end();
1511     last_appended_buffer_timestamp_ = kNoDecodeTimestamp();
1512     last_appended_buffer_is_keyframe_ = false;
1513   }
1514
1515   delete **itr;
1516   *itr = ranges_.erase(*itr);
1517 }
1518
1519 void SourceBufferStream::GenerateSpliceFrame(const BufferQueue& new_buffers) {
1520   DCHECK(!new_buffers.empty());
1521
1522   // Splice frames are only supported for audio.
1523   if (GetType() != kAudio)
1524     return;
1525
1526   // Find the overlapped range (if any).
1527   const base::TimeDelta splice_timestamp = new_buffers.front()->timestamp();
1528   const DecodeTimestamp splice_dts =
1529       DecodeTimestamp::FromPresentationTime(splice_timestamp);
1530   RangeList::iterator range_itr = FindExistingRangeFor(splice_dts);
1531   if (range_itr == ranges_.end())
1532     return;
1533
1534   const DecodeTimestamp max_splice_end_dts =
1535       splice_dts + base::TimeDelta::FromMilliseconds(
1536           AudioSplicer::kCrossfadeDurationInMilliseconds);
1537
1538   // Find all buffers involved before the splice point.
1539   BufferQueue pre_splice_buffers;
1540   if (!(*range_itr)->GetBuffersInRange(
1541           splice_dts, max_splice_end_dts, &pre_splice_buffers)) {
1542     return;
1543   }
1544
1545   // If there are gaps in the timeline, it's possible that we only find buffers
1546   // after the splice point but within the splice range.  For simplicity, we do
1547   // not generate splice frames in this case.
1548   //
1549   // We also do not want to generate splices if the first new buffer replaces an
1550   // existing buffer exactly.
1551   if (pre_splice_buffers.front()->timestamp() >= splice_timestamp)
1552     return;
1553
1554   // If any |pre_splice_buffers| are already splices or preroll, do not generate
1555   // a splice.
1556   for (size_t i = 0; i < pre_splice_buffers.size(); ++i) {
1557     const BufferQueue& original_splice_buffers =
1558         pre_splice_buffers[i]->splice_buffers();
1559     if (!original_splice_buffers.empty()) {
1560       DVLOG(1) << "Can't generate splice: overlapped buffers contain a "
1561                   "pre-existing splice.";
1562       return;
1563     }
1564
1565     if (pre_splice_buffers[i]->preroll_buffer().get()) {
1566       DVLOG(1) << "Can't generate splice: overlapped buffers contain preroll.";
1567       return;
1568     }
1569   }
1570
1571   // Don't generate splice frames which represent less than a millisecond (which
1572   // is frequently the extent of timestamp resolution for poorly encoded media)
1573   // or less than two frames (need at least two to crossfade).
1574   const base::TimeDelta splice_duration =
1575       pre_splice_buffers.back()->timestamp() +
1576       pre_splice_buffers.back()->duration() - splice_timestamp;
1577   const base::TimeDelta minimum_splice_duration = std::max(
1578       base::TimeDelta::FromMilliseconds(1),
1579       base::TimeDelta::FromSecondsD(
1580           2.0 / audio_configs_[append_config_index_].samples_per_second()));
1581   if (splice_duration < minimum_splice_duration) {
1582     DVLOG(1) << "Can't generate splice: not enough samples for crossfade; have "
1583              << splice_duration.InMicroseconds() << " us, but need "
1584              << minimum_splice_duration.InMicroseconds() << " us.";
1585     return;
1586   }
1587
1588   DVLOG(1) << "Generating splice frame @ " << new_buffers.front()->timestamp()
1589            << ", splice duration: " << splice_duration.InMicroseconds()
1590            << " us";
1591   new_buffers.front()->ConvertToSpliceBuffer(pre_splice_buffers);
1592 }
1593
1594 bool SourceBufferStream::SetPendingBuffer(
1595     scoped_refptr<StreamParserBuffer>* out_buffer) {
1596   DCHECK(out_buffer->get());
1597   DCHECK(!pending_buffer_.get());
1598
1599   const bool have_splice_buffers = !(*out_buffer)->splice_buffers().empty();
1600   const bool have_preroll_buffer = !!(*out_buffer)->preroll_buffer().get();
1601
1602   if (!have_splice_buffers && !have_preroll_buffer)
1603     return false;
1604
1605   DCHECK_NE(have_splice_buffers, have_preroll_buffer);
1606   splice_buffers_index_ = 0;
1607   pending_buffer_.swap(*out_buffer);
1608   pending_buffers_complete_ = false;
1609   return true;
1610 }
1611
1612 }  // namespace media