Bug 179690 – [MSE] Use correct range end checks in sourceBufferPrivateDidReceiveSample()

• Component: Media
• Status: RESOLVED FIXED

[Alicia Boya García]

The Coded Frame Processing algorithm as defined in
https://www.w3.org/TR/media-source/#sourcebuffer-coded-frame-processing states:

1.14. Remove existing coded frames in track buffer:
 -> If highest end timestamp for track buffer is not set:
       [...]
 -> If highest end timestamp for track buffer is set and less than or 
    equal to presentation timestamp:
       Remove all coded frames from track buffer that have a 
       presentation timestamp greater than or equal to highest end 
       timestamp and less than frame end timestamp.

Note the removal range is closed-open [a, b). WebKit is actually removing
frames using an open-closed range (a, b], which causes frames not to be removed
in situations where they should and frames to be removed in situations when
they should not.

[Alicia Boya García]

Created attachment 326918 [details]
Patch

[Jer Noble]

Thanks for writing these tests. But I'm curious what the behavior of this change is when faced with appends like:

// PTS, duration
[0, 2]
[2, 2]
[1, 2]

I would argue that the correct results would be:

buffered.length == 1
buffered.start(0) == 1
buffered.end(0) == 3

I'm not sure what this patch's results would be, as it stands.

[Jer Noble]

(In reply to Jer Noble from comment #2)
> Thanks for writing these tests. But I'm curious what the behavior of this
> change is when faced with appends like:
> 
> // PTS, duration
> [0, 2]
> [2, 2]
> [1, 2]
> 
> I would argue that the correct results would be:
> 
> buffered.length == 1
> buffered.start(0) == 1
> buffered.end(0) == 3
> 
> I'm not sure what this patch's results would be, as it stands.

I modified the test from your patch to issue appends in the order I specified above, and when run against ToT (i.e., without your fix), it gets:

{PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
{PTS({1000/1000 = 1.000000}), DTS({1000/1000 = 1.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
EXPECTED (sourceBuffer.buffered.length == '1') OK
EXPECTED (sourceBuffer.buffered.start(0) == '0') OK
EXPECTED (sourceBuffer.buffered.end(0) == '3') OK

So it removes the second sample, but not the first, and leaves overlapping samples in the track buffer, which I think is incorrect.

[Jer Noble]

So I think I remember why we no longer seem to use the SampleIsLessThanMediaTimeComparator objects. We used to, when this was originally implemented, by using std::lower_bound(m_samples.begin(), m_samples.end(), SampleIsGreaterThanMediaTimeComparator).  But std::lower_bound doesn't actually do a binary search; it can't, because map::iterators aren't random access.  map::lower_bound does do a binary search, but it can't take a comparator, because it can't guarantee that the map is sorted in comparator order.  So we re-wrote all the algorithms to use the map::lower_bound (et. all.) algorithms, since those are O(log(n)) rather than the O(n) of the std::lower_bound functions.

I think we can still implement this using the map functions though, even accounting for duration.

Given a sample whose PTS is /pS/ and whose duration is /d/ and whose presentation end time is /pS/ + /d/ = /pE/, the end of the removal range is the first sample whose PTS > /pE/, and the start of the removal range is the first sample whose /pE'/ > /pS/.  Finding the end of the range is easy, it's map.upper_bound(/pE/). Finding the start is harder, because it requires a comparator.  But because our sample map is (supposed to be) non-overlapping, we can just find the first sample whose PTS > /ps/, and then look at the previous sample. If its PTS + duration > /pS/, the previous sample is the start, otherwise the current sample is.

[Alicia Boya García]

(In reply to Jer Noble from comment #2)
> Thanks for writing these tests. But I'm curious what the behavior of this
> change is when faced with appends like:
> 
> // PTS, duration
> [0, 2]
> [2, 2]
> [1, 2]
> 
> I would argue that the correct results would be:
> 
> buffered.length == 1
> buffered.start(0) == 1
> buffered.end(0) == 3
> 
> I'm not sure what this patch's results would be, as it stands.

It would produce the results the spec says, whether good or bad...

In this case it would depend on whether the DTSs are consecutive so the frames are considered part of the same Coded Frame Group.

If they are all part of the same Coded Frame Group, none of the conditions would evaluate true so no frames would be deleted:

1.13. If last decode timestamp for track buffer is unset (false) ...
1.14.a. If highest end timestamp for track buffer is not set (false).
1.14.b. If highest end timestamp for track buffer is set (true) and less than or equal to presentation timestamp (false).

{PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
{PTS({2000/1000 = 2.000000}), DTS({1000/1000 = 1.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
{PTS({1000/1000 = 1.000000}), DTS({2000/1000 = 2.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}

If at least the last frame starts a new Coded Frame Group (e.g. by having a lesser DTS than the previous one):

1.13. (enters in the condition but the frame is not removed because its PTS is not within the 1 microsecond window [PTS, PTS+1µs) ).
1.14.a. If highest end timestamp for track buffer is not set: (true)
  Remove all coded frames from track buffer that have a presentation timestamp greater than or equal to presentation timestamp and less than frame end timestamp. (removes the previous frame)
1.14.b. If highest end timestamp for track buffer is set (false) ...

{PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}
{PTS({1000/1000 = 1.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 = 2.000000}), flags(1), generation(0)}

[Jer Noble]

(In reply to Alicia Boya García from comment #5)
> (In reply to Jer Noble from comment #2)
> > Thanks for writing these tests. But I'm curious what the behavior of this
> > change is when faced with appends like:
> > 
> > // PTS, duration
> > [0, 2]
> > [2, 2]
> > [1, 2]
> > 
> > I would argue that the correct results would be:
> > 
> > buffered.length == 1
> > buffered.start(0) == 1
> > buffered.end(0) == 3
> > 
> > I'm not sure what this patch's results would be, as it stands.
> 
> It would produce the results the spec says, whether good or bad...
> 
> In this case it would depend on whether the DTSs are consecutive so the
> frames are considered part of the same Coded Frame Group.
> 
> If they are all part of the same Coded Frame Group, none of the conditions
> would evaluate true so no frames would be deleted:
> 
> 1.13. If last decode timestamp for track buffer is unset (false) ...
> 1.14.a. If highest end timestamp for track buffer is not set (false).
> 1.14.b. If highest end timestamp for track buffer is set (true) and less
> than or equal to presentation timestamp (false).
> 
> {PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 =
> 2.000000}), flags(1), generation(0)}
> {PTS({2000/1000 = 2.000000}), DTS({1000/1000 = 1.000000}),
> duration({2000/1000 = 2.000000}), flags(1), generation(0)}
> {PTS({1000/1000 = 1.000000}), DTS({2000/1000 = 2.000000}),
> duration({2000/1000 = 2.000000}), flags(1), generation(0)}
> 
> If at least the last frame starts a new Coded Frame Group (e.g. by having a
> lesser DTS than the previous one):
> 
> 1.13. (enters in the condition but the frame is not removed because its PTS
> is not within the 1 microsecond window [PTS, PTS+1µs) ).
> 1.14.a. If highest end timestamp for track buffer is not set: (true)
>   Remove all coded frames from track buffer that have a presentation
> timestamp greater than or equal to presentation timestamp and less than
> frame end timestamp. (removes the previous frame)
> 1.14.b. If highest end timestamp for track buffer is set (false) ...
> 
> {PTS({0/1000 = 0.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000 =
> 2.000000}), flags(1), generation(0)}
> {PTS({1000/1000 = 1.000000}), DTS({0/1000 = 0.000000}), duration({2000/1000
> = 2.000000}), flags(1), generation(0)}

Yuck. I really don't like the idea of having overlapping samples in this case. I would propose that we willfully violate the spec in this case in one of two ways:

Option 1: Remove the overlapping sample.  This obeys (I believe) the spirit of the specification and ensures that no samples can overlap inside the track buffer.

Option 2: Truncate the duration of the overlapping sample.  This solves the overlapping sample problem without actually removing the sample itself.  Has the possible benefit of matching GStreamer's behavior, where duration is ignored anyway.

Option 1 would be easier to implement; it's a cross platform change to the sample append code.

Option 2 would require changes to MediaSample and all its derived classes to add a new virtual "setDuration()" method.

WDYT?

[Alicia Boya García]

(In reply to Jer Noble from comment #6)

I'd argue for removing samples over modifying them, unless we have a convincing use case for doing otherwise.

[Alicia Boya García]

If we are going to diverge from spec-defined behavior, here is an idea: drop
all three removal steps (1.13, 1.14a and 1.14b) and replace them with this
single one:

Remove every existing frame in the track buffer whose presentation range
intersects with the range [PTS+1µs, PTS+DUR-1µs).

I think that is much simpler to understand and makes for more user-predictable
behavior yet still takes JS float conversion effects into account and
algorithmic complexity need not be affected... the most common case should be
still easy to keep O(1) and there should be no much problem in getting the
O(log(n)) search to work (just look at presentation end for the upper bound,
which should be no problem since the ordering of samples is the same whether we
consider PTS or presentation end because both values are monotonically
increasing...).

This simple rule should handle all the real cases that are handled by the
current approach just fine and fix those that are unspecified by the current
MSE spec.

[Alicia Boya García]

Created attachment 328100 [details]
Patch

[Jer Noble]

Comment on attachment 328100 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=328100&action=review

r=me with nit:

> Tools/TestWebKitAPI/Tests/WebCore/SampleMap.cpp:-232
> -TEST_F(SampleMapTest, findSamplesWithinPresentationRange)
> -{
> -    auto& presentationMap = map.presentationOrder();
> -    auto iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(0, 1), MediaTime(1, 1));
> -    EXPECT_EQ(MediaTime(1, 1), iterator_range.first->second->presentationTime());
> -    EXPECT_EQ(MediaTime(2, 1), iterator_range.second->second->presentationTime());
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(1, 2), MediaTime(3, 2));
> -    EXPECT_EQ(MediaTime(1, 1), iterator_range.first->second->presentationTime());
> -    EXPECT_EQ(MediaTime(2, 1), iterator_range.second->second->presentationTime());
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(9, 1), MediaTime(21, 1));
> -    EXPECT_EQ(MediaTime(11, 1), iterator_range.first->second->presentationTime());
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.second);
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(-1, 1), MediaTime(0, 1));
> -    EXPECT_EQ(MediaTime(0, 1), iterator_range.first->second->presentationTime());
> -    EXPECT_EQ(MediaTime(1, 1), iterator_range.second->second->presentationTime());
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(10, 1), MediaTime(21, 2));
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.first);
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.second);
> -
> -    iterator_range = presentationMap.findSamplesWithinPresentationRange(MediaTime(20, 1), MediaTime(21, 1));
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.first);
> -    EXPECT_TRUE(presentationMap.end() == iterator_range.second);
> -}
> -

Please restore this test (with the new name and possibly new values) before landing.

[Alicia Boya García]

On an unrelated note...

Following the conversation from earlier, I've been experimenting with a new frame removal algorithm for some time, but I found it to be non-trivial because of unrelated bugs popping out from many parts of the code and the underlying libraries.

This patch is the same as before, with that test file fixed by removing the references to the deleted function.

Efforts to improve on the algorithm proposed by the W3C can be tracked in a different bugzilla issue.

[Alicia Boya García]

Created attachment 328182 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 328182 [details]
Patch

Clearing flags on attachment: 328182

Committed r225442: <https://trac.webkit.org/changeset/225442>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/35812250>