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

[Uoti Urpala]

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

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