[FFmpeg-cvslog] r19773 - in trunk/libavformat: seek.c seek.h

[Michael Niedermayer]

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>