[FFmpeg-cvslog] r19773 - in trunk/libavformat: seek.c seek.h
Michael Niedermayer
michaelni
Tue Sep 15 00:22:56 CEST 2009
On Sun, Sep 13, 2009 at 09:30:31PM +0200, Ivan Schreter wrote:
> Hi Michael,
>
> Michael Niedermayer wrote:
>> On Sun, Sep 06, 2009 at 04:49:51PM +0200, Ivan Schreter wrote:
>>
>>> Michael Niedermayer wrote:
>>>
>>>> On Sat, Sep 05, 2009 at 09:31:01PM +0200, schreter wrote:
>>>> [...]
>>>>> static int compare_ts(int64_t ts_a, AVRational tb_a, int64_t ts_b,
>>>>> AVRational tb_b)
>>>>> {
>>>>> @@ -95,9 +63,9 @@ static int compare_ts(int64_t ts_a, AVRa
>>>>> if (ts_a == INT64_MIN)
>>>>> return ts_a < ts_b ? -1 : 0;
>>>>> if (ts_a == INT64_MAX)
>>>>> - return ts_a > ts_b ? 1 : 0;
>>>>> + return ts_a > ts_b ? 1 : 0;
>>>>> if (ts_b == INT64_MIN)
>>>>> - return ts_a > ts_b ? 1 : 0;
>>>>> + return ts_a > ts_b ? 1 : 0;
>>>>> if (ts_b == INT64_MAX)
>>>>> return ts_a < ts_b ? -1 : 0;
>>>>> @@ -105,7 +73,7 @@ static int compare_ts(int64_t ts_a, AVRa
>>>>> b = ts_b * tb_b.num * tb_a.den;
>>>>> res = a - b;
>>>>> - if (res == 0)
>>>>> + if (!res)
>>>>> return 0;
>>>>> else
>>>>> return (res >> 63) | 1;
>>>>>
>>>> [...]
>>
>> you multiply 2 32bit values and a 64 bit value, this needs 128bit but it
>> doesnt have that amount
>> i belive i quoted code that does work when when suggested this, if not i
>> can now if needed ...
>>
>
> Yes, that's the only problem when it overflows. I assumed noone will use
> such wild timestamps and yet wilder timebases, obviously wrongly.
>
> Attached is a patch that fixes it for timestamp comparison by using
> comparison routine from NUT spec. A bit more expensive, but so what... I
> hope it is more to your liking. OK so or any further comments?
>
> There is one issue remaining: how to determine which timestamp from two
> timestamps in timebase tb_a is actually closer to target timestamp in
> another timebase tb_b (routine find_closer_ts). I used a distance routine,
> which multiplies the distances by numerators and denumerators of respective
> timebases to have a comparable value. This suffers from the possible
> overflow problem as well. Any idea how to solve this? It is also in the
> attached patch (as TODO, I already changed the rest of the code below to
> use find_closer_ts instead of possibly overflowing distance).
finding the closests is an interresting problem, its very easy to show that
you can find the 2 closest trivially (like in a<b<X b is closer similarly in
X<b<a, so just one on each side of X can remain)
One solution would be to simply work with arbitrary precission integers by
using integer.c/h from libavutil but that isnt compiled or used currently
but i guess it could be a solution until something nicer is found
[...]
> @@ -69,14 +88,31 @@
> if (ts_b == INT64_MAX)
> return ts_a < ts_b ? -1 : 0;
>
> - a = ts_a * tb_a.num * tb_b.den;
> - b = ts_b * tb_b.num * tb_a.den;
> + // convert_ts only works for positive numbers, handle special cases correctly
>
> - res = a - b;
> - if (!res)
> - return 0;
> - else
> - return (res >> 63) | 1;
> + // Note: Just converting the sign in convert_ts back and forth for negative
> + // numbers wouldn't work, as rounding would go in different direction for negative
> + // numbers, thus the result of the comparison of converted timestamps would not be
> + // exact anymore. Therefore, two branches below.
use unsigned numbers then, that should avoid the if/else
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
Asymptotically faster algorithms should always be preferred if you have
asymptotical amounts of data
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-cvslog/attachments/20090915/475d5a43/attachment.pgp>
More information about the ffmpeg-cvslog
mailing list