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

[Michael Niedermayer]

On Tue, Sep 15, 2009 at 02:55:30AM +0300, Uoti Urpala wrote:
> On Tue, 2009-09-15 at 00:22 +0200, Michael Niedermayer wrote:
> > On Sun, Sep 13, 2009 at 09:30:31PM +0200, Ivan Schreter wrote:
> > > 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?
> 
> 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,

as ivan said, it was a typo ...


> 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).

yes, it works only with files of about 100 years duration
and actually av_rescale_rnd() should be used that should work with the whole
32/32*64bit range and lead to simpler code, 
avoiding code duplication and so on ...


> 
> > > 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.

we already have comparison implemented and it should work with the complete
range or at least close to that
about finding the closest, your suggestion is interresting, one would have
to compare it to using interger.c/h though to make sure the simpler is
choosen. Speed shouldnt matter ...

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

When the tyrant has disposed of foreign enemies by conquest or treaty, and
there is nothing more to fear from them, then he is always stirring up
some war or other, in order that the people may require a leader. -- Plato
-------------- 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/f3ff5c5e/attachment.pgp>