64bit integer overflow in 3 days

[Joerg-Cyril.Hoehle at t-systems.com]

Hi,

You believe that 64bit integers give you plenty of room and time to avoid
trouble like Y2k and Y2033, don't you?

The trouble is, these large data types make using other large numbers
more attractive than they used to be, e.g. counting time in 100
nanosecond units, representing one second as 10000000.

Combining large numbers will cause an overflow sooner than you think.

Specifically, the pattern X * numerator / denominator is troublesome.

Let's analyse winealsa:AudioClock_GetPosition:
        QueryPerformanceCounter(&stamp);
        QueryPerformanceFrequency(&frequency);
        *qpctime = (stamp.QuadPart * (INT64)10000000) / frequency.QuadPart;

QueryPerformanceCounter (QPC) returns time in an unspecified unit
(frequency) and needs to convert that into 100 nanosecond units.

Graphically, with g - garbage bits, s - shifted, X - valid bits:
    6         5         4         3         2         1
4321098765432109876543210987654321098765432109876543210987654321
<<< shift left, multiply                 divide, shift right >>>

Assuming QPC returns 64 valid bits:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX QPC

Multiply with (INT64)10000000 (log2 ~ 23):
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXsssssssssssssssssssssss *10000000
Divide by frequency (happens to be 10000000 too):
gggggggggggggggggggggggXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX /10000000 (100ns)

You start to see how the number of valid bits already shrunk a lot.

Now you don't care about nanoseconds, you want seconds. Divide again:
ggggggggggggggggggggggggggggggggggggggggggggggXXXXXXXXXXXXXXXXXX /10000000 (seconds)

Ouch, only 18bits left to express seconds! How many days is that?

(/ (ash 1 18) 3600.0 24) -> ~3.03

So after 3 days in Wine, mmdevapi's GetPosition clock has wrapped.

3 days is not much compared to over 50000 years that 64 bit integers
allow to express with 100 nanosecond units, isn't it?

I don't know if GetPosition is related to bug #26968 where a user reports
that foobar stops playing audio after 4-7 days, but you get a clue.

Cross-check:
0x40000 is 1^18 seconds ~ 3 days
0x2625A000000 same in 100 nanosecond units
0x16BCC41E900000000 the * (INT64)10000000 part in winealsa
  ^1 bit unsigned overflow (more with signed integers)
0x6BCC41E900000000 clipped
0xB4DAD65435 after /10000000, a value already reached after ~21 hours
There are even less bits, because LARGE_INTEGER is signed.

There are several instances of that X * p / q pattern in Wine.  Examples:

ntdll/threadpool.c:queue_current_time:
    return now.QuadPart * 1000 / freq.QuadPart;
ntdll/kernel_main.c:GetTickCount64:
    return counter.QuadPart * 1000 / frequency.QuadPart;
IOW, GetTickCount64 does not offer 64 valid bits.

ntdll/time.c:monotonic_counter:
    return mach_absolute_time() * timebase.numer / timebase.denom / 100;
This means that on MacOS, QPC may overflow even earlier because it does not
offer 64 valid bits.

I've prepared a few patches to fix some of these.  Generally, I don't know
what to recommend.  Use double floating point intermediates and loose 11 bits
for the exponent but at least get the magnitude right?

Regards,
	Jörg Höhle