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