Re: [FFmpeg-devel] [PATCH] lavf/mov: fix hang while seek on a kind of fragmented mp4.
I also think it would be better if we store pts-es in different lists for each track. However, it does NOT match the original design of data structures. Several boxes will be affected. So I am trying to commit this patch to discuss with maintainers. At present, I prefer the last version patch(fall back to linear searching only if needed). I could research more later. Thanks and Regards, Charles Liu Marton Balint 于2019年2月5日周二 上午4:42写道: > > > On Mon, 4 Feb 2019, Michael Niedermayer wrote: > > > On Sat, Feb 02, 2019 at 05:03:25PM +0100, Marton Balint wrote: > >> > >> > >> On Sat, 2 Feb 2019, Charles Liu wrote: > >> > >>> Binary searching would hang if the fragment items do NOT have > timestamp for the specified stream. > >>> > >>> For example, a fmp4 consists of separated 'moof' boxes for each track, > and separated 'sidx' for each segment, but no 'mfra' box. > >>> Then every fragment item only have the timestamp for one of its tracks. > >> > >> I don't see why you are changing the search to be linear. Is it > possible the > >> some of the stream fragmens have NOPTS_VALUE but other don't? In this > case > >> you should keep the binary search and only fall back to linear search if > >> binary search finds an AV_NOPTS_VALUE. See similar code in function > >> mxf_absolute_bodysid_offset of libavformat/mxfdec.c. > > > > The point of binary searching is to achieve O(log n) time > > if there is any linear search this is no longer achieved. > > So its not ideal to have any AV_NOPTS_VALUE in the array that is > > searched. It would be better if the unknown entries are not in the > > array that is used for the search or if their value is monotonized > > once for all searches > > that being ideal at least ... > > Yeah that is true, but that would require maintaining a different array > with pts-es, and getting/updating fragment pts-es are complicated as is. > > Considering that this fixes a hang, I'd rather see the last version of the > patch applied than wait for a more complicated, yet faster implementation. > > Regards, > Marton > ___ > ffmpeg-devel mailing list > ffmpeg-devel@ffmpeg.org > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel > ___ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] lavf/mov: fix hang while seek on a kind of fragmented mp4.
On Mon, 4 Feb 2019, Michael Niedermayer wrote: On Sat, Feb 02, 2019 at 05:03:25PM +0100, Marton Balint wrote: On Sat, 2 Feb 2019, Charles Liu wrote: Binary searching would hang if the fragment items do NOT have timestamp for the specified stream. For example, a fmp4 consists of separated 'moof' boxes for each track, and separated 'sidx' for each segment, but no 'mfra' box. Then every fragment item only have the timestamp for one of its tracks. I don't see why you are changing the search to be linear. Is it possible the some of the stream fragmens have NOPTS_VALUE but other don't? In this case you should keep the binary search and only fall back to linear search if binary search finds an AV_NOPTS_VALUE. See similar code in function mxf_absolute_bodysid_offset of libavformat/mxfdec.c. The point of binary searching is to achieve O(log n) time if there is any linear search this is no longer achieved. So its not ideal to have any AV_NOPTS_VALUE in the array that is searched. It would be better if the unknown entries are not in the array that is used for the search or if their value is monotonized once for all searches that being ideal at least ... Yeah that is true, but that would require maintaining a different array with pts-es, and getting/updating fragment pts-es are complicated as is. Considering that this fixes a hang, I'd rather see the last version of the patch applied than wait for a more complicated, yet faster implementation. Regards, Marton ___ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] lavf/mov: fix hang while seek on a kind of fragmented mp4.
On Sat, Feb 02, 2019 at 05:03:25PM +0100, Marton Balint wrote: > > > On Sat, 2 Feb 2019, Charles Liu wrote: > > >Binary searching would hang if the fragment items do NOT have timestamp for > >the specified stream. > > > >For example, a fmp4 consists of separated 'moof' boxes for each track, and > >separated 'sidx' for each segment, but no 'mfra' box. > >Then every fragment item only have the timestamp for one of its tracks. > > I don't see why you are changing the search to be linear. Is it possible the > some of the stream fragmens have NOPTS_VALUE but other don't? In this case > you should keep the binary search and only fall back to linear search if > binary search finds an AV_NOPTS_VALUE. See similar code in function > mxf_absolute_bodysid_offset of libavformat/mxfdec.c. The point of binary searching is to achieve O(log n) time if there is any linear search this is no longer achieved. So its not ideal to have any AV_NOPTS_VALUE in the array that is searched. It would be better if the unknown entries are not in the array that is used for the search or if their value is monotonized once for all searches that being ideal at least ... Thanks [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB Let us carefully observe those good qualities wherein our enemies excel us and endeavor to excel them, by avoiding what is faulty, and imitating what is excellent in them. -- Plutarch signature.asc Description: PGP signature ___ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
Re: [FFmpeg-devel] [PATCH] lavf/mov: fix hang while seek on a kind of fragmented mp4.
On Sat, 2 Feb 2019, Charles Liu wrote: Binary searching would hang if the fragment items do NOT have timestamp for the specified stream. For example, a fmp4 consists of separated 'moof' boxes for each track, and separated 'sidx' for each segment, but no 'mfra' box. Then every fragment item only have the timestamp for one of its tracks. I don't see why you are changing the search to be linear. Is it possible the some of the stream fragmens have NOPTS_VALUE but other don't? In this case you should keep the binary search and only fall back to linear search if binary search finds an AV_NOPTS_VALUE. See similar code in function mxf_absolute_bodysid_offset of libavformat/mxfdec.c. On the other hand, if either all stream segments have AV_NOPTS_VALUE, or none of them do, then why don't you simply break out of the loop with error? Thanks, Marton Signed-off-by: Charles Liu --- libavformat/mov.c | 21 + 1 file changed, 9 insertions(+), 12 deletions(-) diff --git a/libavformat/mov.c b/libavformat/mov.c index 9b9739f788..ce1130ad07 100644 --- a/libavformat/mov.c +++ b/libavformat/mov.c @@ -1266,9 +1266,8 @@ static int64_t get_frag_time(MOVFragmentIndex *frag_index, static int search_frag_timestamp(MOVFragmentIndex *frag_index, AVStream *st, int64_t timestamp) { -int a, b, m; int64_t frag_time; -int id = -1; +int i, frag = 0, id = -1; if (st) { // If the stream is referenced by any sidx, limit the search @@ -1278,20 +1277,18 @@ static int search_frag_timestamp(MOVFragmentIndex *frag_index, id = st->id; } -a = -1; -b = frag_index->nb_items; - -while (b - a > 1) { -m = (a + b) >> 1; -frag_time = get_frag_time(frag_index, m, id); +for (i = 0; i < frag_index->nb_items; i++) { +frag_time = get_frag_time(frag_index, i, id); if (frag_time != AV_NOPTS_VALUE) { -if (frag_time >= timestamp) -b = m; if (frag_time <= timestamp) -a = m; +frag = i; +else { +break; +} } } -return a; + +return frag; } static int update_frag_index(MOVContext *c, int64_t offset) -- 2.20.1 ___ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel ___ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
[FFmpeg-devel] [PATCH] lavf/mov: fix hang while seek on a kind of fragmented mp4.
Binary searching would hang if the fragment items do NOT have timestamp for the specified stream. For example, a fmp4 consists of separated 'moof' boxes for each track, and separated 'sidx' for each segment, but no 'mfra' box. Then every fragment item only have the timestamp for one of its tracks. Signed-off-by: Charles Liu --- libavformat/mov.c | 21 + 1 file changed, 9 insertions(+), 12 deletions(-) diff --git a/libavformat/mov.c b/libavformat/mov.c index 9b9739f788..ce1130ad07 100644 --- a/libavformat/mov.c +++ b/libavformat/mov.c @@ -1266,9 +1266,8 @@ static int64_t get_frag_time(MOVFragmentIndex *frag_index, static int search_frag_timestamp(MOVFragmentIndex *frag_index, AVStream *st, int64_t timestamp) { -int a, b, m; int64_t frag_time; -int id = -1; +int i, frag = 0, id = -1; if (st) { // If the stream is referenced by any sidx, limit the search @@ -1278,20 +1277,18 @@ static int search_frag_timestamp(MOVFragmentIndex *frag_index, id = st->id; } -a = -1; -b = frag_index->nb_items; - -while (b - a > 1) { -m = (a + b) >> 1; -frag_time = get_frag_time(frag_index, m, id); +for (i = 0; i < frag_index->nb_items; i++) { +frag_time = get_frag_time(frag_index, i, id); if (frag_time != AV_NOPTS_VALUE) { -if (frag_time >= timestamp) -b = m; if (frag_time <= timestamp) -a = m; +frag = i; +else { +break; +} } } -return a; + +return frag; } static int update_frag_index(MOVContext *c, int64_t offset) -- 2.20.1 ___ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel