On 01/01/2022 19:03, Bonita Montero wrote:
> Am 01.01.2022 um 19:31 schrieb Michael S:
>
>>> On x86 f.e. the compiler will still use a 32 * 32 multiplication
>>> because it sees that the casted value's upper halves are zero.
>>> And after / grouplen you can safely cast the result to uint32_t.
>
>> It seems like you are confusing x86 with x386, a.k.a. IA32.
>
> x86 is a common synonym for all x86 and descendant CPUs.

Typo?

If you meant 8086 and up, then 8086 is a 16-bit processor, which is
apparently what the OP is using.

On 12/31/21 9:30 PM, Stefan Ram wrote:
> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>> , the exact result for a call with the arguments 2705443,
>> 415131524, and 1256275308 would be 894003, so it would
>
> PS: In the OP, "tempo" has only 16 bits instead of 32.
> I did not take this reduced width into account, and used
> too many test values. "tempo" corresponds to my "b".
> But even when "b" fits into 16 bits, I still get errors:
>
> q=0, p=0, r=2705443, m=4251374074, m_=17136275962, d=2, s=2
> Error found!
> a=2705443 b=6334 c=1736723169: exact_result=9 experimental_result=2

The formula you're using is `a*b/c = ((a/c)*b)+(a%c)*b/c`. This formula
is valid only if (a%c)*b doesn't overflow. The value of the formula
derives from the fact that there's a wide range of values for `a`, `b`,
and `c` for which `a*b` overflows, but `a*b/c` doesn't, and neither does
`(a%c)*b`. However, `a=2705443 b=6334 c=1736723169` is not one of those
sets, as your own code demonstrates by comparing the value of `m` and `m_`.

On Saturday, January 1, 2022 at 7:31:27 PM UTC-5, james...@alumni.caltech.edu wrote:
> On 12/31/21 9:30 PM, Stefan Ram wrote:
....
> The formula you're using is `a*b/c = ((a/c)*b)+(a%c)*b/c`. This formula
> is valid only if (a%c)*b doesn't overflow.

Given what the C standard says about unsigned overflow, that should have
been worded differently: "... if the mathematical value of `(a%c)*b` is
representable in the type being used for the result."

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> The value of the formula
>derives from the fact that there's a wide range of values for `a`, `b`,
>and `c` for which `a*b` overflows, but `a*b/c` doesn't, and neither does
>`(a%c)*b`.

To determine how large a possible increase in the number of values
with the correct result is, I wrote a function "muldiv_naive" with
just "a * b / c" and another function "muldiv_experimental" with
the formula you mentioned above.

Then I calculate three random numbers a, b, c in a loop and count
the number of correct results of the naive approach and with the
formula you mentioned above.

So far, the output of the program shows that the formula you
mentioned above does indeed yield the correct result in about
five times more cases than with the naive approach. But on the
other hand, overall, both find the correct result only in few
cases if all possible 32 bit values are used for a and c and
all possible 16 bit values for b.

main.c

#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#if RAND_MAX != 32767
#error "RAND_MAX != 32767"
#endif

#if UINT16_MAX != 65535
#error "UINT16_MAX != 65535"
#endif

#if UINT32_MAX != 4294967295
#error "UINT32_MAX != 4294967295"
#endif

#define TOP ( ( unsigned long long )UINT32_MAX + 1 )

unsigned long long rand32( void )
{ return
( ( ( ( unsigned long long )rand() >> 5 )<< 30 )+
( ( ( unsigned long long )rand() >> 5 )<< 20 )+
( ( ( unsigned long long )rand() >> 5 )<< 10 )+
( ( ( unsigned long long )rand() >> 5 )<< 0 ))&
( unsigned long long )0xffffffff; }

unsigned long long rand16( void )
{ return
( ( ( ( unsigned long long )rand() >> 5 )<< 10 )+
( ( ( unsigned long long )rand() >> 5 )<< 0 ))&
( unsigned long long )0xffff; }

void the_exact_result_is_not_representable( void ){}

unsigned long long muldiv_exact
( unsigned long long const a,
unsigned long long const b,
unsigned long long const c )
{ return a * b / c; }

uint32_t muldiv_naive
( uint32_t const a,
uint16_t const b,
uint32_t const c )
{ return a * b / c; }

uint32_t muldiv_experimental
( uint32_t const a,
uint16_t const b,
uint32_t const c )
{ const uint32_t q =( uint32_t )( a / c );
const uint32_t p =( uint32_t )( q * b );
const uint32_t r =( uint32_t )( a % c );
const uint32_t m =( uint32_t )( r * b );
const uint32_t d =( uint32_t )( m / c );
const uint32_t s =( uint32_t )( p + d );
return s; }

int main( void )
{ unsigned long long naive_correct = 0;
unsigned long long experimental_correct = 0;
unsigned long long count = 0;
while( count < 100000000 )
{ unsigned long long a = rand32();
unsigned long long b = rand16();
unsigned long long c = rand32();
if( c )
{ unsigned long long const exact_result =
muldiv_exact( a, b, c );
uint32_t const experimental_result =
muldiv_experimental( ( uint32_t )a,( uint16_t )b,( uint32_t )c );
uint32_t const naive_result =
muldiv_naive( ( uint32_t )a,( uint16_t )b,( uint32_t )c );
if( exact_result >= TOP )
the_exact_result_is_not_representable();
else
{ if( naive_result == exact_result )
{ ++naive_correct; }
if( experimental_result == exact_result )
{ ++experimental_correct; }}}
++count; }
printf
( "count=%llu, naive_correct=%llu, experimental_correct=%llu\n",
count, naive_correct, experimental_correct );
printf
( "naive percentage: %g\n",
( double )naive_correct/( double )count * 100. );
printf
( "experimental percentage: %g\n",
( double )experimental_correct/( double )count * 100. ); }

transcript

count=100000000, naive_correct=19178, experimental_correct=120393
naive percentage: 0.019178
experimental percentage: 0.120393

ram@zedat.fu-berlin.de (Stefan Ram) writes:
>count=100000000, naive_correct=19178, experimental_correct=120393
>naive percentage: 0.019178
>experimental percentage: 0.120393

The reduced "model" with values of 8 and 4 bits instead of 32 and 16
bits showed the same qualitative behavior. But it allowed to test all
256 * 16 * 255 = 1044480 possible values instead of just a random
selection, and the two algorithms both yielded correct results much
more often:

transcript

count=1044480, naive_correct=283560, experimental_correct=549663
naive percentage: 27.1484
experimental percentage: 52.6255

.

On 01/01/2022 20:18, Bart wrote:
> On 01/01/2022 19:03, Bonita Montero wrote:
>> Am 01.01.2022 um 19:31 schrieb Michael S:
>>
>>>> On x86 f.e. the compiler will still use a 32 * 32 multiplication
>>>> because it sees that the casted value's upper halves are zero.
>>>> And after / grouplen you can safely cast the result to uint32_t.
>>
>>> It seems like you are confusing x86 with x386, a.k.a. IA32.
>>
>> x86 is a common synonym for all x86 and descendant CPUs.
>
> Typo?
>
> If you meant 8086 and up, then 8086 is a 16-bit processor, which is
> apparently what the OP is using.

Yes, x86 is a common synonym for 80386 and up - either the 32-bit or
64-bit lines. The earlier 16-bit devices are so old that they are
rarely seen as physical devices (emulation with DOSBox and the like is
more common, especially for old games). They are used sometimes in old
embedded systems, and clearly they are still used by hobby users who
like a challenge with old hardware.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

[...]

> One further idea.. after posting it occurred to me that there is
> a technique that is guaranteed to give the right answer as long
> as the result fits in 32 bits:
>
> uint32_t
> ticks2time( uint32_t ticks, uint16_t tempo, uint16_t scale ){
> uint32_t th = ticks >> 16;
> uint32_t th_tempo = th * tempo;
> uint32_t tl = (uint16_t) ticks;
> return
> (th_tempo / scale << 16) +
> ((th_tempo % scale << 16) + tl*tempo) / scale;
> }

I must recant this earlier comment. Haste makes bugs.

On 1/1/22 8:58 PM, Stefan Ram wrote:
....
> To determine how large a possible increase in the number of values
> with the correct result is, I wrote a function "muldiv_naive" with
> just "a * b / c" and another function "muldiv_experimental" with
> the formula you mentioned above.
>
> Then I calculate three random numbers a, b, c in a loop and count
> the number of correct results of the naive approach and with the
> formula you mentioned above.
>
> So far, the output of the program shows that the formula you
> mentioned above does indeed yield the correct result in about
> five times more cases than with the naive approach. But on the
> other hand, overall, both find the correct result only in few
> cases if all possible 32 bit values are used for a and c and
> all possible 16 bit values for b.
>
> main.c
>
> #include <limits.h>
> #include <stdint.h>
> #include <stdio.h>
> #include <stdlib.h>
>
> #if RAND_MAX != 32767
> #error "RAND_MAX != 32767"
> #endif

I couldn't use your code unmodified on my system; it has RAND_MAX ==
2147483647.

> #if UINT16_MAX != 65535
> #error "UINT16_MAX != 65535"
> #endif
>
> #if UINT32_MAX != 4294967295
> #error "UINT32_MAX != 4294967295"
> #endif>
> #define TOP ( ( unsigned long long )UINT32_MAX + 1 )
>
> unsigned long long rand32( void )
> { return
> ( ( ( ( unsigned long long )rand() >> 5 )<< 30 )+
> ( ( ( unsigned long long )rand() >> 5 )<< 20 )+
> ( ( ( unsigned long long )rand() >> 5 )<< 10 )+
> ( ( ( unsigned long long )rand() >> 5 )<< 0 ))&
> ( unsigned long long )0xffffffff; }

It would have made more sense to have this return uint32_t, and to use
uint32_t in the calculations.

There's no need to cast the final constant - it's likely to be the
correct type even without the cast, and if it isn't, it will be
implicitly converted to that type anyway, and has a value that will
survive the conversion unchanged.

> unsigned long long rand16( void )
> { return
> ( ( ( ( unsigned long long )rand() >> 5 )<< 10 )+
> ( ( ( unsigned long long )rand() >> 5 )<< 0 ))&
> ( unsigned long long )0xffff; }

Similarly, that should have use uint16_t. And again, there's no need to
cast the final constant, for the same reasons as in rand32().

> void the_exact_result_is_not_representable( void ){}
>
> unsigned long long muldiv_exact
> ( unsigned long long const a,
> unsigned long long const b,
> unsigned long long const c )
> { return a * b / c; }
>
> uint32_t muldiv_naive
> ( uint32_t const a,
> uint16_t const b,
> uint32_t const c )
> { return a * b / c; }
>
> uint32_t muldiv_experimental
> ( uint32_t const a,
> uint16_t const b,
> uint32_t const c )
> { const uint32_t q =( uint32_t )( a / c );
> const uint32_t p =( uint32_t )( q * b );
> const uint32_t r =( uint32_t )( a % c );
> const uint32_t m =( uint32_t )( r * b );
> const uint32_t d =( uint32_t )( m / c );
> const uint32_t s =( uint32_t )( p + d );

Note: those casts are unnecessary - assigning them to variables with
that type causes the same conversion to occur implicitly.

> return s; }
>
> int main( void )
> { unsigned long long naive_correct = 0;
> unsigned long long experimental_correct = 0;
> unsigned long long count = 0;> while( count < 100000000 )

If your count is going to be that small, unsigned long or even long
would be sufficient, there's no need to use unsigned long long for the
counters above.

> { unsigned long long a = rand32();
> unsigned long long b = rand16();
> unsigned long long c = rand32();

Those should have been defined as uint32_t and uint16_t. The only
consequence of defining them as unsigned long long is that it might make
the arithmetic slower - it won't change the calculated results.

> if( c )
> { unsigned long long const exact_result =
> muldiv_exact( a, b, c );
> uint32_t const experimental_result =
> muldiv_experimental( ( uint32_t )a,( uint16_t )b,( uint32_t )c );
> uint32_t const naive_result =
> muldiv_naive( ( uint32_t )a,( uint16_t )b,( uint32_t )c );

Those casts are all unnecessary, with or without the changes I suggested
above, because the specified conversions occur implicitly even without
those casts.

> if( exact_result >= TOP )
> the_exact_result_is_not_representable();
> else
> { if( naive_result == exact_result )
> { ++naive_correct; }
> if( experimental_result == exact_result )
> { ++experimental_correct; }}}
> ++count; }> printf
> ( "count=%llu, naive_correct=%llu, experimental_correct=%llu\n",
> count, naive_correct, experimental_correct );
> printf
> ( "naive percentage: %g\n",
> ( double )naive_correct/( double )count * 100. );

Simpler:
naive_correct * 100.0 / count;

With that change, the needed conversions will occur implicitly, and
similarly for the next calculation:

> printf
> ( "experimental percentage: %g\n",
> ( double )experimental_correct/( double )count * 100. ); }
>
> transcript
>
> count=100000000, naive_correct=19178, experimental_correct=120393
> naive percentage: 0.019178
> experimental percentage: 0.120393

Note first that the experimental percentage is much higher than the
naive percentage, which is what makes that formula useful. The reason
why the experimental percentage is so small is the second term:
(a%c)*b/c. a%c has a value that can be as high as c-1, so the
multiplication has a good chance of wrapping if c > UINT16_MAX,
rendering the formula invalid.

The OP has only given a few indications of the range of values for grouplen:
1. It's passed through a uint32_t interface, implying that it's at least
possible for it to be > UINT16_MAX.
2. He's said it never changes.
3. He gave 15730 as an example of a real-world value.
4. He indicated that tempo/grouplen is typically about 100. Since tempo
is passed as a uint16_t value, that would imply that grouplen is
normally much smaller than UINT16_MAX.

All in all, it sounds likely ticks, tempo, and grouplen usually (though
not necessarily always) have values that allow the formula a*b/c =
(a/c)*b + (a%c)*b/c to be valid when using a 32-bit type.

2022-01-04 at 00:32 -0500, James Kuyper wrote:
> Simpler:
> naive_correct * 100.0 / count;

I'm not sure if you guys still talk about the original case, but if so,
then there is no FPU on the target system. Ie. floats and doubles are
prohibited. Just sayin'.

> The OP has only given a few indications of the range of values for
> grouplen: 1. It's passed through a uint32_t interface, implying that
> it's at least possible for it to be > UINT16_MAX.
> 2. He's said it never changes.
> 3. He gave 15730 as an example of a real-world value.
> 4. He indicated that tempo/grouplen is typically about 100. Since
> tempo is passed as a uint16_t value, that would imply that grouplen is
> normally much smaller than UINT16_MAX.
>
> All in all, it sounds likely ticks, tempo, and grouplen usually
> (though not necessarily always) have values that allow the formula
> a*b/c = (a/c)*b + (a%c)*b/c to be valid when using a 32-bit type.

That is correct, yes. In fact even the original formula was working
fine on 95%+ of cases: (ticks * tempo) / grouplen

It broke up when I've got a file with an unusually high tempo value:
1090909.

Now, to clarify the context, here's what the values are really:

"grouplen" is a MIDI time division (16-bit):
https://www.recordingblogs.com/wiki/time-division-of-a-midi-file

"tempo" is a MIDI tempo value (24-bit, but usually between 300 and
1000000):
http://midi.teragonaudio.com/tech/midifile/tempo.htm

"ticks" is a MIDI delta-time (up to 28 bits, but usually between 0 and
10*tempo):
http://midi.teragonaudio.com/tech/midifile/vari.htm

Mateusz

Mateusz Viste <mateusz@xyz.invalid> writes:

> [ want to compute the value of '(ticks * tempo) / grouplen' ]
>
> [ that expression ] was working fine on 95%+ of cases
>
> It broke up when I've got a file with an unusually high tempo value:
> 1090909.
>
> Now, to clarify the context, here's what the values are really:
>
> "grouplen" is a MIDI time division (16-bit):
> https://www.recordingblogs.com/wiki/time-division-of-a-midi-file
>
> "tempo" is a MIDI tempo value (24-bit, but usually between 300 and
> 1000000):
> http://midi.teragonaudio.com/tech/midifile/tempo.htm
>
> "ticks" is a MIDI delta-time (up to 28 bits, but usually between 0 and
> 10*tempo):
> http://midi.teragonaudio.com/tech/midifile/vari.htm

Given this additional information -- in particular, that ticks
and tempo have 32 bit types, and grouplen has a 16 bit type -- a
more exact calculation suggests itself:

#include <stdint.h>

uint32_t
ticks2time( uint32_t ticks, uint32_t tempo, uint16_t grouplen ){
uint32_t a = ticks, b = tempo, c = grouplen;
uint32_t aq = a/c, ar = a%c, bq = b/c, br = b%c;
return aq*b + ar*bq + ar*br/c;
}

with the usual comments about precomputing 'bq' and 'br', if that
turns out to be important.

This approach should give correct values in all cases when the
result fits in 32 bits.

On 1/4/22 3:43 AM, Mateusz Viste wrote:
> 2022-01-04 at 00:32 -0500, James Kuyper wrote:
>> Simpler:
>> naive_correct * 100.0 / count;
>
> I'm not sure if you guys still talk about the original case, but if so,
> then there is no FPU on the target system. Ie. floats and doubles are
> prohibited. Just sayin'.

We are talking about the original case, but that line is NOT part of a
proposed solution to your problem. Stephen Ram created a program that
analyzed the results using a proposed solution, and the expression above
is part of the process of displaying the results of that analysis.

>> The OP has only given a few indications of the range of values for
>> grouplen: 1. It's passed through a uint32_t interface, implying that
>> it's at least possible for it to be > UINT16_MAX.
>> 2. He's said it never changes.
>> 3. He gave 15730 as an example of a real-world value.
>> 4. He indicated that tempo/grouplen is typically about 100. Since
>> tempo is passed as a uint16_t value, that would imply that grouplen is
>> normally much smaller than UINT16_MAX.
>>
>> All in all, it sounds likely ticks, tempo, and grouplen usually
>> (though not necessarily always) have values that allow the formula
>> a*b/c = (a/c)*b + (a%c)*b/c to be valid when using a 32-bit type.
>
> That is correct, yes. In fact even the original formula was working
> fine on 95%+ of cases: (ticks * tempo) / grouplen
>
> It broke up when I've got a file with an unusually high tempo value:
> 1090909.
>
> Now, to clarify the context, here's what the values are really:
>
> "grouplen" is a MIDI time division (16-bit):
> https://www.recordingblogs.com/wiki/time-division-of-a-midi-file
>
> "tempo" is a MIDI tempo value (24-bit, but usually between 300 and
> 1000000):
> http://midi.teragonaudio.com/tech/midifile/tempo.htm
>
> "ticks" is a MIDI delta-time (up to 28 bits, but usually between 0 and
> 10*tempo):
> http://midi.teragonaudio.com/tech/midifile/vari.htm

On 12/31/21 5:02 AM, you wrote:
....
> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)

Based upon what you said above, I assume that the arguments to this
function have the wrong types: grouplen should have been uint16_t, while
tempo should have been uint32_t.

What I said above was based upon the assumption that tempo was a 16-bit
type. Therefore, if grouplen was also normally <= UINT16_MAX, then
(ticks%grouplen)*tempo would not normally wrap around. If tempo needs 24
bits, and grouplen needs 16, then that expression can still wrap around.

However, there is an alternative approach that avoids the problem
entirely. I came up with this approach before Stephen Ram mentioned the
apparently well-know formula:

a*b/c == ((a/c)*b)+(a%c)*b/c

While that formula was unknown to me, it's easy to derive from the
better-known formula:

a = (a/c)*c + a%c

I never mentioned my alternative, because if grouplen is a 32-bit type,
it's just as prone to overflow as the one Stephen mentioned, and roughly
twice as complicated. However, since grouplen is actually a 16-bit type,
it completely avoids that problem. Here's how I derived my alternative:

The following expressions should be considered evaluated in an integer
type big enough so that none of the multiplication ever overflows:

a*b/c == ( (a/c)*c + a%c ) * ( (b/c)*c + b%c) / c
== ( (a/c)*(b/c)*c*c + (a/c)*(b%c)*c + (a%c)*(b/c)*c + (a%c)*(b%c)) / c

Now, while (a/c)*c == a is NOT a valid identity for C's integer
arithmetic, (a*c)/c == a is (in the absence of overflow/wraparound).
Therefore:

a*b/c == (a/c)*(b/c)*c + (a/c)*(b%c) + (a%c)*(b/c) + (a%c)*(b%c)/c

Now, if a and b have the type uint32_t, and c has the type uint16_t, and
they happen to have values such that a*(uint64_t)b/c would be
representable in uint32_t, then none of the terms on the right-hand side
will overflow/wraparound uint32_t, and the final result will be
therefore be exactly the same as if evaluated in uint64_t.

uint32_t ticks2time(uint32_t ticks, uint16_t grouplen, uint32_t tempo)
{ uint32_t tiogr = ticks/grouplen;
uint16_t timgr = ticks%grouplen;
uint32_t teogr = tempo/grouplen;
uint16_t temgr = tempo%grouplen;
return tiogr * teogr * grouplen + tiogr*temgr +
timgr*temgr + timgr*temgr/grouplen;
}

2022-01-04 at 10:50 -0500, James Kuyper wrote:
> > uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t
> > tempo)
>
> Based upon what you said above, I assume that the arguments to this
> function have the wrong types: grouplen should have been uint16_t,
> while tempo should have been uint32_t.

You are correct, that's an error I must have introduced while
reformatting the code into a function... My stupid mistake.

> I never mentioned my alternative, because if grouplen is a 32-bit
> type, it's just as prone to overflow as the one Stephen mentioned,
> and roughly twice as complicated. However, since grouplen is actually
> a 16-bit type, it completely avoids that problem. Here's how I
> derived my alternative:
> (...)
> uint32_t ticks2time(uint32_t ticks, uint16_t grouplen, uint32_t
> tempo) {
> uint32_t tiogr = ticks/grouplen;
> uint16_t timgr = ticks%grouplen;
> uint32_t teogr = tempo/grouplen;
> uint16_t temgr = tempo%grouplen;
> return tiogr * teogr * grouplen + tiogr*temgr +
> timgr*temgr + timgr*temgr/grouplen;
> }

That is interesting. It is also interesting to note that this part:
tiogr * teogr * grouplen

expands into that:
(ticks/grouplen) * (tempo/grouplen) * grouplen

....where we can drop two grouplens so it becomes:
(ticks/grouplen) * tempo

After this simplification, your formula becomes almost identical to the
one proposed by Tim 30 minutes earlier. :-)

Mateusz

2022-01-04 at 07:20 -0800, Tim Rentsch wrote:
> Given this additional information -- in particular, that ticks
> and tempo have 32 bit types, and grouplen has a 16 bit type -- a
> more exact calculation suggests itself:
>
> #include <stdint.h>
>
> uint32_t
> ticks2time( uint32_t ticks, uint32_t tempo, uint16_t grouplen ){
> uint32_t a = ticks, b = tempo, c = grouplen;
> uint32_t aq = a/c, ar = a%c, bq = b/c, br = b%c;
> return aq*b + ar*bq + ar*br/c;
> }

That is brilliant. You may be interested to know that James Kuyper
arrived to a very similar solution (even though the path he followed
was different).

You might also like to know that your computation is almost 8x faster
than a computation over 64 bits (the target system is a 16-bit, hence
64-bit are very costly, but still). This even without any
pre-computation. I measured it with the test program pasted below, and
it outputs:

t 500 1090909 15360
Tim = 139809378 after 41 clocks
Cast= 139809378 after 323 clocks

Very nice. Thanks!

------ TEST.C ---------------------------------------------
#include <stdio.h>
#include <stdlib.h>

static unsigned long gettime(void) {
unsigned short hw = 0, lw = 0;
unsigned long r;
_asm {
xor ah, ah
int 0x1a
mov hw, cx
mov lw, dx
}
r = (hw << 16) | lw;
return(r);
}

int main(int argc, char **argv) {
unsigned long ticks = atoi(argv[1]);
unsigned long tempo = atoi(argv[2]);
unsigned short grouplen = atoi(argv[3]);
unsigned short i;
unsigned long r, t0, t1;

if (argc != 4) return(1);

t0 = gettime();
for (i = 1; i++; ) {
unsigned long a = ticks, b = tempo, c = grouplen;
unsigned long aq = a/c, ar = a%c, bq = b/c, br = b%c;
r = aq*b + ar*bq + ar*br/c;
}
t1 = gettime();
printf("Tim = %lu after %lu clocks\n", r, t1 - t0);

t0 = gettime();
for (i = 1; i++; ) {
r = (((unsigned long long)ticks * tempo) / grouplen);
}
t1 = gettime();
printf("Cast= %lu after %lu clocks\n", r, t1 - t0);

return(0);
} -----------------------------------------------------------

Mateusz

On 1/4/22 11:37 AM, Mateusz Viste wrote:
> 2022-01-04 at 10:50 -0500, James Kuyper wrote:
....
>> I never mentioned my alternative, because if grouplen is a 32-bit
>> type, it's just as prone to overflow as the one Stephen mentioned,
>> and roughly twice as complicated. However, since grouplen is actually
>> a 16-bit type, it completely avoids that problem. Here's how I
>> derived my alternative:
>> (...)
>> uint32_t ticks2time(uint32_t ticks, uint16_t grouplen, uint32_t
>> tempo) {
>> uint32_t tiogr = ticks/grouplen;
>> uint16_t timgr = ticks%grouplen;
>> uint32_t teogr = tempo/grouplen;
>> uint16_t temgr = tempo%grouplen;
>> return tiogr * teogr * grouplen + tiogr*temgr +
>> timgr*temgr + timgr*temgr/grouplen;
>> }
>
> That is interesting. It is also interesting to note that this part:
> tiogr * teogr * grouplen
>
> expands into that:
> (ticks/grouplen) * (tempo/grouplen) * grouplen
>
> ...where we can drop two grouplens so it becomes:
> (ticks/grouplen) * tempo

No, you can't drop them. This is integer arithmetic, not real-number
arithmetic. (20/3)*3 == 6*3 == 18, not 20.

> After this simplification, your formula becomes almost identical to the
> one proposed by Tim 30 minutes earlier. :-)

Tim's version doesn't differ from mine by using the invalid
simplification you suggest. Instead, his version combines what I called
tiogr*teogr*grouple and tiogr*temgr into tiogr*(teogr*grouplen + temgr)
which is equivalent ot tiogr*tempo. If ticks*(uint64_t)tempo/grouplen is
representable as a uint32_t, then tiogr*tempo won't wrap, so that's a
valid simplification, one that I didn't notice.

2022-01-04 at 15:01 -0500, James Kuyper wrote:
> > expands into that:
> > (ticks/grouplen) * (tempo/grouplen) * grouplen
> >
> > ...where we can drop two grouplens so it becomes:
> > (ticks/grouplen) * tempo
>
> No, you can't drop them. This is integer arithmetic, not real-number
> arithmetic. (20/3)*3 == 6*3 == 18, not 20.

You are right of course. I wasn't looking carefully enough and missed
that the point was to remove the remainder in this part of the formula.
Thank you for the clarification.

Mateusz

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> On 1/1/22 8:58 PM, Stefan Ram wrote:
[...]
>> unsigned long long rand32( void )
>> { return
>> ( ( ( ( unsigned long long )rand() >> 5 )<< 30 )+
>> ( ( ( unsigned long long )rand() >> 5 )<< 20 )+
>> ( ( ( unsigned long long )rand() >> 5 )<< 10 )+
>> ( ( ( unsigned long long )rand() >> 5 )<< 0 ))&
>> ( unsigned long long )0xffffffff; }
>
> It would have made more sense to have this return uint32_t, and to use
> uint32_t in the calculations.
>
> There's no need to cast the final constant - it's likely to be the
> correct type even without the cast, and if it isn't, it will be
> implicitly converted to that type anyway, and has a value that will
> survive the conversion unchanged.

Or just write the constant as 0xffffffffULL. (Though if you change it
from unsigned long long to one of the uintN_t types it's not that simple.)

[...]

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

pa@see.signature.invalid (Pierre Asselin) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> [ ... ]
>> These identities suggest two alternate formulations:
>>
>> uint32_t
>> ticks2time( uint32_t ticks, uint32_t scale, uint16_t tempo ){
>> return ticks*(tempo/scale) + ticks*(tempo%scale)/scale;
>> }
>>
>> uint32_t
>> ticks2time( uint32_t ticks, uint32_t scale, uint16_t tempo ){
>> return tempo*(ticks/scale) + tempo*(ticks%scale)/scale;
>> }
>
> I was thinking along those lines myself, except, in Tim's first
> formula, using the div() function to compute (tempo/scale) and
> (tempo%scale) together. [...]

These days I expect compilers to be smart enough to see that both
the division and the remainder are being computed, and generate
single instruction that produces both values. And if there is no
such instruction then div() probably doesn't help much.

Mateusz Viste <mateusz@xyz.invalid> writes:

> 2021-12-31 at 18:37 -0500, James Kuyper wrote:
>
>> Calling it ANSI C is not very useful, because that designation is
>> ambiguous.
>
> I was only stating about "my copy of ANSI C". Didn't mean to specify
> any more than that, really.
>
>> uint32_t and uint16_t, both of which are used in your code, were added
>> to the language in C99. So apparently you don't consider C99 a
>> complete atrocity.
>
> My answer was obviously slightly provocative. In truth, I am no puritan
> and I do pick sometime things out of C89, like uint32_t, snprintf() and
> the like. I also appreciate __uint128_t very much, even though it is not
> part of any standard. For practical purposes I find the gnu89 dialect
> to suit me pretty well.

Can you say what you think the downside is of using C99? If
there are parts of C99 you don't like you can always just not
use them.

Also, I'm curious to know what extensions, if any, from the gnu
additions you make use of.

2022-01-21 at 05:51 -0800, Tim Rentsch wrote:
> Can you say what you think the downside is of using C99? If
> there are parts of C99 you don't like you can always just not
> use them.

You are of course right, but that's not really the point. Let me
provide one example. In C99, it is legal to declare a variable that is
not at the top of the scope. Fine, but *I* don't like it, as I find
that it encourages sloppy programming. If I'm allowed to use something
and it appears to be easier on the short term, I will most probably
abuse it. Yes, I am a feeble human. C89 is a way to keep my laziness in
check: all variables have to be at the top of the scope so I can see
them upfront. If it starts to be messy, then it is because my scope
needs to be refactored.

That's only one simple example, but I hope it conveys the larger idea.

> Also, I'm curious to know what extensions, if any, from the gnu
> additions you make use of.

That's an interesting question that I was unable to answer from the top
of my head. It has been so long that I code in gnu89 that I wasn't able
to tell what exactly is non-vanilla-C89 in the set of C features I use.
To answer your question I took a couple of my projects and switched
them from -std=gnu89 to -std=c89 to identify the gnu89 extensions that
I use. Here is the result:

__uint128_t (also uint64_t / uint32_t / uint8_t but it seems gcc
tolerates those even in c89 mode, as long as stdint.h is included)
struct timeval
struct timespec
DT_DIR / DT_REG
PATH_MAX

clock_gettime() / CLOCK_MONOTONIC
select() / fd_set / FD_SET() / FD_ZERO() / FD_ISSET()
strcasecmp()
getaddrinfo() / freeaddrinfo() / struct addrinfo / gai_strerror()
inet_aton()
mrand48()
snprintf() / vsnprintf()
strdup()
realpath()
chroot()
fileno()
popen() / pclose()
setenv() / unsetenv()
vsyslog()

Mateusz

On 21/01/2022 15:59, Mateusz Viste wrote:
> 2022-01-21 at 05:51 -0800, Tim Rentsch wrote:
>> Can you say what you think the downside is of using C99? If
>> there are parts of C99 you don't like you can always just not
>> use them.
>
> You are of course right, but that's not really the point. Let me
> provide one example. In C99, it is legal to declare a variable that is
> not at the top of the scope.
The scope of a variable begins just after the completion of its
declarator. /All/ variables in all varieties of C must be declared at
the top of their scope, since that's where their scope starts.

In C90, local variables can only be declared at the start of a block,
before any statements - but they don't have to be at the top of the
function.

> Fine, but *I* don't like it, as I find
> that it encourages sloppy programming.

That is contrary to what many others find. Personal preferences are, of
course, personal.

> If I'm allowed to use something
> and it appears to be easier on the short term, I will most probably
> abuse it. Yes, I am a feeble human. C89 is a way to keep my laziness in
> check: all variables have to be at the top of the scope so I can see
> them upfront. If it starts to be messy, then it is because my scope
> needs to be refactored.
>
> That's only one simple example, but I hope it conveys the larger idea.
>
>> Also, I'm curious to know what extensions, if any, from the gnu
>> additions you make use of.
>
> That's an interesting question that I was unable to answer from the top
> of my head. It has been so long that I code in gnu89 that I wasn't able
> to tell what exactly is non-vanilla-C89 in the set of C features I use.
> To answer your question I took a couple of my projects and switched
> them from -std=gnu89 to -std=c89 to identify the gnu89 extensions that
> I use. Here is the result:
>
> __uint128_t (also uint64_t / uint32_t / uint8_t but it seems gcc
> tolerates those even in c89 mode, as long as stdint.h is included)

There is nothing in C90 that prevents the existence and use of a header
of that name containing such typedefs.

> struct timeval
> struct timespec
> DT_DIR / DT_REG
> PATH_MAX
>
> clock_gettime() / CLOCK_MONOTONIC
> select() / fd_set / FD_SET() / FD_ZERO() / FD_ISSET()
> strcasecmp()
> getaddrinfo() / freeaddrinfo() / struct addrinfo / gai_strerror()
> inet_aton()
> mrand48()
> snprintf() / vsnprintf()
> strdup()
> realpath()
> chroot()
> fileno()
> popen() / pclose()
> setenv() / unsetenv()
> vsyslog()
>

None of these are, AFAIK, compiler extensions. They are library
functions (and types).

The type "__int128" is a gcc extension. (And if you have __uint128_t,
presumably it is a typedef of "unsigned __int128".)

You might find you are using other gcc extensions without thinking about
it, as a number of features of C99 started off as gcc extensions to C90.

2022-01-21 at 16:19 +0100, David Brown wrote:
> The scope of a variable begins just after the completion of its
> declarator. /All/ variables in all varieties of C must be declared at
> the top of their scope, since that's where their scope starts.
>
> In C90, local variables can only be declared at the start of a block,
> before any statements - but they don't have to be at the top of the
> function.

My wording was not precise, sorry. When I wrote "scope" I meant "block"
indeed.

> > __uint128_t (also uint64_t / uint32_t / uint8_t but it seems gcc
> > tolerates those even in c89 mode, as long as stdint.h is included)
>
> There is nothing in C90 that prevents the existence and use of a
> header of that name containing such typedefs.

But then you could say the same about many other things, like the DT_DIR
definition or even functions like snprintf(). Yet gcc hides then when
called with -std=c89.

> None of these are, AFAIK, compiler extensions. They are library
> functions (and types).
>
> The type "__int128" is a gcc extension. (And if you have __uint128_t,
> presumably it is a typedef of "unsigned __int128".)

Does not look like a typedef, a recursive grep for "uint128" in
/usr/include/ does not yield any result. Not that it matters much, of
course.

> You might find you are using other gcc extensions without thinking
> about it

Entirely possible, yes, since I am not checking every line of my code
against the ANSI/ISO 9899-1990 reference book. :)

Mateusz

On 1/21/22 10:51 AM, Mateusz Viste wrote:
> 2022-01-21 at 16:19 +0100, David Brown wrote:
....
>>> __uint128_t (also uint64_t / uint32_t / uint8_t but it seems gcc
>>> tolerates those even in c89 mode, as long as stdint.h is included)
>>
>> There is nothing in C90 that prevents the existence and use of a
>> header of that name containing such typedefs.
>
> But then you could say the same about many other things, like the DT_DIR
> definition or even functions like snprintf(). Yet gcc hides then when
> called with -std=c89.
In C89, stdint.h was not a standard header. However, if its implemented
as an actual header file (it doesn't have to be), and if that file can
be found in the compiler's normal search path (which it needn't be, in
C89 mode), it should still be opened and could be processed as if it
were a user-written header file. There's no reason for it to contain any
features which would prevent it from being parsed as C89 code. The only
potential problem is that one or more of the typedefs might be for
[unsigned] long long or an extended integer type that the compiler
doesn't support in C89 mode.
This is actually disproportionately likely to work, because many sources
provided C89-compatible versions of stdint.h, for use while waiting for
the rest of C99 to be implemented by their preferred compiler.

snprintf(), on the other hand, is a C standard library function declared
in <stdio.h>, which was introduced in C99, and had a name that was NOT
reserved to the implementation in C89. Therefore, strictly conforming
C89 code could declare and define an identifier with that same name and
external linkage. Therefore, an implementation fully conforming to C89
must not do anything to prevent such code from behaving as required by
the C89 standard. In particular, it must NOT declare that identifier in
<stdio.h>, and it must not link to a version of the C standard library
that contains such a function (unless the linker supports weak
identifiers, with your program's own snprintf() being used instead of
the library version).

On 1/21/22 9:59 AM, Mateusz Viste wrote:
....
> them from -std=gnu89 to -std=c89 to identify the gnu89 extensions that
> I use. Here is the result:
>
> __uint128_t (also uint64_t / uint32_t / uint8_t but it seems gcc
> tolerates those even in c89 mode, as long as stdint.h is included)
> struct timeval
> struct timespec
> DT_DIR / DT_REG
> PATH_MAX
>
> clock_gettime() / CLOCK_MONOTONIC
> select() / fd_set / FD_SET() / FD_ZERO() / FD_ISSET()
> strcasecmp()
> getaddrinfo() / freeaddrinfo() / struct addrinfo / gai_strerror()
> inet_aton()
> mrand48()
> snprintf() / vsnprintf()
> strdup()
> realpath()
> chroot()
> fileno()
> popen() / pclose()
> setenv() / unsetenv()
> vsyslog()

Many (most? all? - I haven't bothered to check.) of those are not gcc
extensions, they're part of the POSIX standard library.

On 21/01/2022 16:51, Mateusz Viste wrote:
> 2022-01-21 at 16:19 +0100, David Brown wrote:
>> The scope of a variable begins just after the completion of its
>> declarator. /All/ variables in all varieties of C must be declared at
>> the top of their scope, since that's where their scope starts.
>>
>> In C90, local variables can only be declared at the start of a block,
>> before any statements - but they don't have to be at the top of the
>> function.
>
> My wording was not precise, sorry. When I wrote "scope" I meant "block"
> indeed.
>
>>> __uint128_t (also uint64_t / uint32_t / uint8_t but it seems gcc
>>> tolerates those even in c89 mode, as long as stdint.h is included)
>>
>> There is nothing in C90 that prevents the existence and use of a
>> header of that name containing such typedefs.
>
> But then you could say the same about many other things, like the DT_DIR
> definition or even functions like snprintf(). Yet gcc hides then when
> called with -std=c89.

You could indeed say that about other things. Some C libraries will
include functions that are not specified in the standards, others limit
themselves more. Some enable functions only if particular C standards
are chosen. To be conforming, a standard header should not define
symbols that are not in the relevant standard version, and not in the
reserved namespaces. For example, you should in a C90 program be able
to #include <stdio.h> without clashing with your own declaration for
snprintf. Not all implementations (compiler and library combinations,
together with flags or other settings) are as conforming as they might
be - in particular, gcc (and common Linux C libraries) is not conforming
by default and enables a fair number of extensions. And the
"-std=gnu89" will enable more of these than "-std=c89".

Identifiers that begin with two underscores, such as "__uint128_t", are
freely available for an implementation to define regardless of standards.

>
>> None of these are, AFAIK, compiler extensions. They are library
>> functions (and types).
>>
>> The type "__int128" is a gcc extension. (And if you have __uint128_t,
>> presumably it is a typedef of "unsigned __int128".)
>

A quick check shows that gcc (at least, the version I looked at and on
x86-64 target) also defines __int128_t and __uint128_t out of the box.
The reference manual only mentions __int128. But gcc pre-defines a
whole range of types starting with two underscores that are not
documented in the user manual, because they are not intended for normal
code - more commonly they provide the bases for typedefs of things like
size_t, uintptr_t, and many other types.

> Does not look like a typedef, a recursive grep for "uint128" in
> /usr/include/ does not yield any result. Not that it matters much, of
> course.

Indeed.

>
>> You might find you are using other gcc extensions without thinking
>> about it
>
> Entirely possible, yes, since I am not checking every line of my code
> against the ANSI/ISO 9899-1990 reference book. :)
>

You can use "-std=c90 -Wpedantic" to give warnings on most non-standard
code. (If you are interested, of course.)

Mateusz Viste <mateusz@xyz.invalid> writes:
>2022-01-21 at 05:51 -0800, Tim Rentsch wrote:
>> Can you say what you think the downside is of using C99? If
>> there are parts of C99 you don't like you can always just not
>> use them.
>
>You are of course right, but that's not really the point. Let me
>provide one example. In C99, it is legal to declare a variable that is
>not at the top of the scope. Fine, but *I* don't like it, as I find
>that it encourages sloppy programming.

That hasn't been my experience.

In fact, there are valid arguments for moving the
declaration closer to the use, particularly in functions
that may exit before using an initialized declaration.

Either via a basic block (stand-alone or as part of a
conditional or looping construct) or using C++/C99 features.