[FFmpeg-cvslog] r19773 - in trunk/libavformat: seek.c seek.h
Uoti Urpala
uoti.urpala
Tue Sep 15 01:55:30 CEST 2009
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.)
More information about the ffmpeg-cvslog
mailing list