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

[Ivan Schreter]

Uoti Urpala wrote:
> [...]
> What range of values is the comparison supposed to work for? The code
> uses 64-bit types for timestamps, but OTOH the comparison uses this
> function:
>
> + * Convert timestamp to different timebase.
> + *
> + * This function converts the timestamp in such a way that no numerical overflow
> + * can happen. Effectively, it computes ts * tb_to / tb_from.
> + *
> + * @param ts      timestamp to convert (non-negative)
> + * @param tb_from source time base
> + * @param tb_to   destination time base
> + * @return timestamp in destination time base
> + */
> +static int convert_ts(uint64_t ts, AVRational tb_from, AVRational tb_to)
> +{
> +    // this algorithm is copied from NUT spec and works only for non-negative numbers
> +    uint64_t ln = (uint64_t) tb_from.num * (uint64_t) tb_to.den;
> +    uint64_t d1 = tb_from.den;
> +    uint64_t d2 = tb_to.num;
> +    return (ln / d1 * ts + ln % d1 * ts / d1) / d2;
> +}
>
> This takes input timestamp as uint64_t but has return type int, and it
> wouldn't work with a larger return type (the return statement is of the
> form "something/d2", so it cannot possibly correctly return anything
> bigger than UINT64_MAX / d2 - or about 32 bits if d2 is assumed to have
> full 32 bit range).
>   

Sorry, my mistake. Thanks for spotting it. Of course, it must return 
uint64_t.

>   
>>> 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
>>     
>
> I think it should be reasonably simple to implement both comparison and
> finding closest in a way that works at least when timestamp*timebase (as
> a real number) is less than INT64_MAX. The basic idea is that you can
> convert int64_t*int32_t/int32_t into the form int64_t+int32_t/int32_t
> using 64-bit arithmetic, and how to do the comparisons in that form
> should be obvious.
>
> (In case the conversion to mixed fraction form isn't clear: write the
> x*a/b as (y+k*b)*a/b, where y is less than b.)
>   

I'll look into that later. Comparison as such is OK with the code above, 
but finding closest is currently open.

Thanks & regards,

Ivan