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