After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 590919 - gst_util_uint64_scale_int() and friends don't round
gst_util_uint64_scale_int() and friends don't round
Status: RESOLVED FIXED
Product: GStreamer
Classification: Platform
Component: gstreamer (core)
git master
Other Linux
: Normal normal
: 0.10.25
Assigned To: GStreamer Maintainers
GStreamer Maintainers
Depends on:
Blocks: 591934
 
 
Reported: 2009-08-06 09:14 UTC by Kipp
Modified: 2009-08-16 02:09 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
add 1/2 the denominator before doing the division (1.41 KB, patch)
2009-08-06 09:17 UTC, Kipp
rejected Details | Review
demonstrate the problem with truncation (457 bytes, text/plain)
2009-08-06 09:19 UTC, Kipp
  Details
output of demo without rounding patch (580 bytes, text/plain)
2009-08-06 09:20 UTC, Kipp
  Details
output of demo with rounding patch (600 bytes, text/plain)
2009-08-06 09:20 UTC, Kipp
  Details
refactor scale functions to allow re-use of their guts (13.88 KB, patch)
2009-08-11 05:24 UTC, Kipp
committed Details | Review
validation code for refactored scale functions (892 bytes, application/x-compressed-tar)
2009-08-11 05:28 UTC, Kipp
  Details
scale64-aliasing.diff (1.98 KB, patch)
2009-08-11 07:18 UTC, Sebastian Dröge (slomo)
committed Details | Review
revert long division function, remove remainders (8.14 KB, patch)
2009-08-12 08:47 UTC, Kipp
committed Details | Review
export new versions of scale() funcs with three rounding modes (12.58 KB, patch)
2009-08-12 18:11 UTC, Kipp
committed Details | Review
updated validation code. (4.21 KB, application/x-compressed-tar)
2009-08-13 19:17 UTC, Kipp
  Details

Description Kipp 2009-08-06 09:14:50 UTC
The utility functions gst_util_uint64_scale() and gst_util_uint64_scale_int() truncate their results instead of rounding.  This causes drifts in timestamps in pipelines that use these functions to convert repeatedly between offsets and timestamp (which can be needed in elements that preserve internal state, etc.).

The problems this creates are most visible when the sample rate in a stream is such that times of individual samples don't correspond to integer counts of nanoseconds.  For example, power-of-two sample rates like 16384 Hz have this problem becuase 16384^-1 cannot be represented exactly by an integer count of nanoseconds.

The behaviour of the scale-by-ratio functions can be switched to produce rounded results by simply adding 1/2 of the denominator to the numerator product before entering the division stages in the various algorithms.
Comment 1 Kipp 2009-08-06 09:17:01 UTC
Created attachment 139999 [details] [review]
add 1/2 the denominator before doing the division

Patches all three places where the division is implemented.  This should be reviewed by an expert, of course.
Comment 2 Kipp 2009-08-06 09:19:43 UTC
Created attachment 140000 [details]
demonstrate the problem with truncation

This little demo program shows the problem.  An offset counter is set to 10000 and a sample rate of 16384 Hz is selected.  Then a loop is performed in which the offset is converted to a timestamp using gst_util_uint64_scale_int(), and the timestamp is converted back to an offset using gst_util_uint64_scale_int() again.  There is a 1-sample drift per iteration of the loop.
Comment 3 Kipp 2009-08-06 09:20:22 UTC
Created attachment 140001 [details]
output of demo without rounding patch
Comment 4 Kipp 2009-08-06 09:20:55 UTC
Created attachment 140002 [details]
output of demo with rounding patch
Comment 5 Wim Taymans 2009-08-06 17:40:02 UTC
We need rounding down (currently present) and rounding up (not yet present) versions.
Comment 6 Kipp 2009-08-06 17:52:55 UTC
Comparing to floating point operations, the functions currently don't "round", they return floor() --- the largest integer not greater than the result.  The patch makes them return round() --- the nearest integer rounding half-way cases away from 0.  Not covered is the ceil() case.  Is it really true that the current behaviour is correct in some cases?  There is only a difference between floor(), round() and ceil() when the result cannot be represented exactly as an integer, otherwise they all produce the same answer, and when the result cannot be represented exactly as an integer isn't it always preferrable to return the nearest integer to the correct result?  I.e., as with IEEE floating point operations, to always return the exactly-rounded answer (the answer one would get if one had infinite precision and then rounded to the nearest available representable number).
Comment 7 Sebastian Dröge (slomo) 2009-08-06 18:58:32 UTC
We probably want all 3 variants (+3 variants for the gst_util_uint64_scale()).

There are always reasons why you want rounding down, rounding up or rounding to the nearest integer. If you want to prepare such a patch that just adds new functions and doesn't change the current ones that'd be great :)
Comment 8 Kipp 2009-08-06 21:41:30 UTC
Sure, OK, I'll do that.  To avoid duplicating code it will be convenient if the existing functions can be broken up a little bit, e.g. break out the bit that multiplies two 64 bit ints into a 128 bit int, etc..  So I'll go ahead and do that, but it'll make the patch look a little more dramatic than the current version, hope that'll be OK.  Hopefully I'll have that by tomorrow.
Comment 9 Kipp 2009-08-11 05:24:57 UTC
Created attachment 140411 [details] [review]
refactor scale functions to allow re-use of their guts

This is the first of two patches to add rounding and ceiling versions of the existing (truncating) functions _scale() and _scale_int() functions.  This patch refactors the code, moving the wide integer multiplication and division routines into stand-alone functions that can be reused to avoid duplication.  This patch does not modify the exported API.

The division algorithms are replaced with versions that compute and return the remainder as well as the quotient.  The remainder will be required, later, to decide how to round the result, but is not currently used.
Comment 10 Kipp 2009-08-11 05:28:16 UTC
Created attachment 140412 [details]
validation code for refactored scale functions

This is the validation code I used to test the results of the re-worked wide arithmetic functions.  GSL's Mersenne Twister random number generator is used to provide random input to gst_util_uint64_scale() and gst_util_uint64_scale_int(), and the output of both is compared to the correct result as computed by GMP.  No discrepancies have been observed.
Comment 11 Sebastian Dröge (slomo) 2009-08-11 06:31:07 UTC
Looks good at first glance. Could you transform your validation code to a unit test in tests/check/gst/gstutils.c? It's fine to use GMP there as long as you also add a configure check and only compile the GMP code when GMP is available.
Also it would be nice to have a deterministic test additional to the random number multiplication, i.e. some hardcoded integer multiplications.
Comment 12 Sebastian Dröge (slomo) 2009-08-11 07:18:17 UTC
I've committed your patch now and fixed some compiler warnings about aliasing (patch will follow). Please provide any additional patches as incremental patches on top of these two... I'll push everything once the rounding versions are there :)

commit a9154480cab2312e98c818bfeb0f8619fd31e67f
Author: Kipp Cannon <kcannon@ligo.caltech.edu>
Date:   Tue Aug 11 09:10:47 2009 +0200

    gstutils: Refactor gst_util_uint64_scale()
    
    This will later make it possible to provide rounding versions
    of it without much code duplication.
    
    Partially fixes bug #590919.
Comment 13 Sebastian Dröge (slomo) 2009-08-11 07:18:53 UTC
Created attachment 140415 [details] [review]
scale64-aliasing.diff

Fixes some violations of strict-aliasing rules
Comment 14 Sebastian Dröge (slomo) 2009-08-11 07:33:25 UTC
Note that the new code is about 2.5 times slower and a 64 bit machine. The times below are for 20000000 calls of gst_util_uint64_scale() with random 64 bit integers.

It's not good that we're that much slower now although only some refactoring happened...

old:
---------
real	0m2.463s
user	0m2.440s
sys	0m0.012s

real	0m2.426s
user	0m2.396s
sys	0m0.016s

real	0m2.362s
user	0m2.340s
sys	0m0.016s

real	0m2.603s
user	0m2.552s
sys	0m0.004s

new:
---------
real	0m7.482s
user	0m7.344s
sys	0m0.016s

real	0m7.096s
user	0m7.080s
sys	0m0.012s

real	0m7.081s
user	0m7.056s
sys	0m0.016s

real	0m7.091s
user	0m7.064s
sys	0m0.016s
Comment 15 Wim Taymans 2009-08-11 09:51:41 UTC
The 'refactored code' unoptimized the division. This code has been carefully tweaked. I would try to add a new rounding version (with an extra argument to specify the reounding type) then call the existing code if rounding down and try to patch up the result or input parameters with other rounding modes. 
Comment 16 Kipp 2009-08-11 11:08:52 UTC
(In reply to comment #15)
> The 'refactored code' unoptimized the division. This code has been carefully
> tweaked. I would try to add a new rounding version (with an extra argument to
> specify the reounding type) then call the existing code if rounding down and
> try to patch up the result or input parameters with other rounding modes. 

All that is needed now that the previous division function doesn't provide is the remainder.  The previous division code claimed to be inspired by the function on page 152 of Hacker's Delight.  That function, in Hacker's Delight, does compute the remainder, so I assume that somebody who understands how the original long division function worked could figure out how to modify it to return the remainder as well.  I never figured it out, but it sounds like you're familiar with this code, is that something you could do?

It doesn't matter to me what long division function gets used, but I think there should only be one long division function.  It seems silly to introduce a second one just to get the remainder out, and I'd love it if the original one could continue to be used.
Comment 17 Kipp 2009-08-11 20:32:59 UTC
(In reply to comment #16)
> (In reply to comment #15)
> > The 'refactored code' unoptimized the division. This code has been carefully
> > tweaked. I would try to add a new rounding version (with an extra argument to
> > specify the reounding type) then call the existing code if rounding down and
> > try to patch up the result or input parameters with other rounding modes. 
> 
> All that is needed now that the previous division function doesn't provide is
> the remainder.  The previous division code claimed to be inspired by the
> function on page 152 of Hacker's Delight.  That function, in Hacker's Delight,
> does compute the remainder, so I assume that somebody who understands how the
> original long division function worked could figure out how to modify it to
> return the remainder as well.  I never figured it out, but it sounds like
> you're familiar with this code, is that something you could do?
> 
> It doesn't matter to me what long division function gets used, but I think
> there should only be one long division function.  It seems silly to introduce a
> second one just to get the remainder out, and I'd love it if the original one
> could continue to be used.
> 

Oh, no, you're right.  I'm an idiot.  Instead of rounding using the remainder, I can pre-condition the input to the original divide function like I did in the original patch.  Sorry, I'll try again.
Comment 18 Kipp 2009-08-12 08:47:36 UTC
Created attachment 140533 [details] [review]
revert long division function, remove remainders

reverts the 128-bit / 64-bit division function, removes code to compute the remainder from the other division function (not needed for rounding).  this patch should be applied on top of the aliasing patch.
Comment 19 Sebastian Dröge (slomo) 2009-08-12 09:17:16 UTC
Yeah, looks better and is as fast as the original code ;)

I've committed this locally, please provide the rounding functions patch on top of this :)
Comment 20 Kipp 2009-08-12 18:11:33 UTC
Created attachment 140571 [details] [review]
export new versions of scale() funcs with three rounding modes

This exports four new functions that provide two new rounding variants each of gst_util_uint64_scale() and gst_util_uint64_scale_int().  The new functions have _round and _ceil suffixes appended to their names indicating that they return the result rounded to the nearest integer or rounded up to the smallest integer not smaller than the result.
Comment 21 Sebastian Dröge (slomo) 2009-08-13 14:11:19 UTC
Thanks, I'll add some unit tests for the rounding versions too now.

commit e8e4d289acb4e8c373fdbd94c93c3585cf32d256
Author: Kipp Cannon <kcannon@ligo.caltech.edu>
Date:   Thu Aug 13 16:10:31 2009 +0200

    gstutils: Add rounding to nearest and next integer versions of the 64 bit in
    
    Fixes bug #590919.
Comment 22 Kipp 2009-08-13 19:17:09 UTC
Created attachment 140690 [details]
updated validation code.

Here's an updated version of the earlier validation code that tests all 6 functions, and also tries to specifically exercise the different code paths in the scale functions.  I took at how to add it to the unit tests, but I think I don't feel comfortable editing gstreamer's configure/build system to look for GMP, etc..  I think it's best if a gstreamer expert do that.  But if it saves any time, here's this code if it helps.
Comment 23 Sebastian Dröge (slomo) 2009-08-14 09:15:06 UTC
commit 2919e5add82966150586684b3efb43509d971a80
Author: Sebastian Dröge <sebastian.droege@collabora.co.uk>
Date:   Fri Aug 14 11:12:50 2009 +0200

    gstutils: Add special random unit test for 64 scaling functions
    
    This tests 100000 random multiplications/divisions of all scaling
    function variants and compares the result with the result that is
    generated by GMP on the same input.
    
    For this check for GSL and GMP during configure but only use
    it for this single unit test.
    
    Testing functions were provided by Kipp Cannon <kcannon@ligo.caltech.edu>