Summary: | [MSE] Use correct range end checks in sourceBufferPrivateDidReceiveSample() | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Alicia Boya García <aboya> | ||||||||
Component: | Media | Assignee: | Nobody <webkit-unassigned> | ||||||||
Status: | RESOLVED FIXED | ||||||||||
Severity: | Normal | CC: | calvaris, commit-queue, eocanha, jer.noble, webkit-bug-importer | ||||||||
Priority: | P2 | Keywords: | InRadar | ||||||||
Version: | WebKit Nightly Build | ||||||||||
Hardware: | Unspecified | ||||||||||
OS: | Unspecified | ||||||||||
Attachments: |
|
Description
Alicia Boya García
2017-11-14 13:28:21 PST
Created attachment 326918 [details]
Patch
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. (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. 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. (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)} (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? (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. 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. Created attachment 328100 [details]
Patch
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. 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. Created attachment 328182 [details]
Patch
Comment on attachment 328182 [details] Patch Clearing flags on attachment: 328182 Committed r225442: <https://trac.webkit.org/changeset/225442> All reviewed patches have been landed. Closing bug. |