I have this little function:

/* converts an amount of ticks into human time (micro-seconds)
* timeunits: number of ticks to convert into actual time
* tempo : the time length (in microseconds) of grouplen ticks
*/
uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
{ return ticks * tempo / grouplen;
}

In practical situations the end result of this computation is
guaranteed to always fit inside an uint32_t, but the above formula
overflows easily in the (ticks * tempo) part.

The easy & stupid way to avoid this overflow would be this:

return ticks * (tempo / grouplen);

....but it's obviously not a good solution, since it may loose a lot of
resolution. The hacky compromise that I currently use is this:

return ticks * (((tempo << 3) / grouplen) >> 3);

It works fine in my practical tests, so I might just as well be done
with it, but I wonder if there is a cleaner approach to such seemingly
simple problem?

I should also add that this part of the program is performance
critical, so I cannot afford branching or any other expensive
computations. It's also worth noting that "grouplen" is guaranteed to
be a positive number that never changes across the calls of the
function (which, in truth, is not even a function, but it was easier to
format it as such for this exercise).

Mateusz

Mateusz Viste <mateusz@xyz.invalid> writes:
>uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
....
>In practical situations the end result of this computation is
>guaranteed to always fit inside an uint32_t, but the above formula
>overflows easily in the (ticks * tempo) part.

See the section

Multiplication

on the Web page

INT32-C. Ensure that operations on signed integers do not result in overflow

.

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Mateusz Viste <mateusz@xyz.invalid> writes:
>>uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> ...
>>In practical situations the end result of this computation is
>>guaranteed to always fit inside an uint32_t, but the above formula
>>overflows easily in the (ticks * tempo) part.
>
> See the section
>
> Multiplication
>
> on the Web page
>
> INT32-C. Ensure that operations on signed integers do not result in
> overflow

What web page? I found a document (by searching for these words) but
that was all about detecting signed integer overflow. The OP does not
want to detect the overflow (technically, the wrapping since the types
are unsigned), but to get the right result even though the intermediate
calculation wraps.

Detecting the wrapping might be a first step, but the OP has a rough and
ready solution already, so anything that complicated is not going to be
suitable.

--
Ben.

Mateusz Viste <mateusz@xyz.invalid> writes:

> I have this little function:
>
> /* converts an amount of ticks into human time (micro-seconds)
> * timeunits: number of ticks to convert into actual time
> * tempo : the time length (in microseconds) of grouplen ticks
> */
> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> {
> return ticks * tempo / grouplen;
> }
>
> In practical situations the end result of this computation is
> guaranteed to always fit inside an uint32_t, but the above formula
> overflows easily in the (ticks * tempo) part.

There's a technical detail here which is that in C unsigned arithmetic
can't overflow. Arithmetic overflow is reserved for serious undefined
situation. Unsigned arithmetic just "wraps round" in a defined manner.

But there's nothing unclear about your question: the result is always <=
UINT32_MAX, but ticks * tempo isn't. You want to know how to calculate
the result correctly in all cases.

Interesting question. The obvious way is to use a wider type for the
multiplication (uint_least64_t) but that's probably not what you want.

> The easy & stupid way to avoid this overflow would be this:
>
> return ticks * (tempo / grouplen);
>
> ...but it's obviously not a good solution, since it may loose a lot of
> resolution. The hacky compromise that I currently use is this:
>
> return ticks * (((tempo << 3) / grouplen) >> 3);

I don't think this helps. I think that (when tempo << 3 does not wrap)
you get the same result as the original. Maybe I'm missing something.

> It works fine in my practical tests, so I might just as well be done
> with it, but I wonder if there is a cleaner approach to such seemingly
> simple problem?

I feel there should be a way, but I can't think of one right now.

> I should also add that this part of the program is performance
> critical, so I cannot afford branching or any other expensive
> computations. It's also worth noting that "grouplen" is guaranteed to
> be a positive number that never changes across the calls of the
> function (which, in truth, is not even a function, but it was easier to
> format it as such for this exercise).

Since grouplen does not change, can you find, at the start, gl1 and gl2,
ideally close to the square root of grouplen, so that you can use

(ticks / gl1) * (tempo / gl2)

instead? Obviously you may not be able to find such numbers, but there
may be constraints on grouplen that make this work.

> Mateusz
>

--
Ben.

Am 31.12.2021 um 11:02 schrieb Mateusz Viste:

> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> {
> return ticks * tempo / grouplen;
return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);

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.

On Friday, 31 December 2021 at 14:53:24 UTC+2, Bonita Montero wrote:
> Am 31.12.2021 um 11:02 schrieb Mateusz Viste:
>
> > uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> > {
> > return ticks * tempo / grouplen;
> return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);
>
> 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.

I suspect that minority of programmers work on code that should
run on x86 right now. OP did not indicate that they are among such.

> And after / grouplen you can safely cast the result to uint32_t.

2021-12-31 at 12:33 +0000, Ben Bacarisse wrote:
> There's a technical detail here which is that in C unsigned arithmetic
> can't overflow. Arithmetic overflow is reserved for serious undefined
> situation. Unsigned arithmetic just "wraps round" in a defined
> manner.

Can you provide the source please? I know that what you describe is the
standard behavior of all C compilers (that I know), but I could not
find the definition of multiplicative wrapping in the ISO 9899:1990
(yes, this is ANSI C). All I did find is this:

G.2 Undefined behavior
The behavior in the following circumstances is undefined:
(...)
-- An arithmetic operation is invalid (such as division or modulus by
0) or produces a result that cannot be represented in the space
provided (such as overflow or underflow)

> Interesting question. The obvious way is to use a wider type for the
> multiplication (uint_least64_t) but that's probably not what you want.

I should have mentioned that this runs on a 16-bit CPU. Doing 32-bit
multiplications is hard enough already, emulating 64-long types would
have a disastrous effect on performances. I also do not have access to
an FPU.

> > return ticks * (((tempo << 3) / grouplen) >> 3);
>
> I don't think this helps. I think that (when tempo << 3 does not
> wrap) you get the same result as the original. Maybe I'm missing
> something.

I'm sorry, you are correct of course. I copied the code wrong when
typing the message and misplaced one set of parenthesis. Here's the
actual hack I use:

return (ticks * (((tempo << 3) / grouplen))) >> 3;

> I feel there should be a way, but I can't think of one right now.

So we're on the same page.

On top of what I have already described, here is a short test program I
used to exhibit the problem and test for solutions:

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

int main(int argc, char **argv) {
if (argc != 4) {
printf("usage: %s ticks tempo grouplen\n", argv[0]);
} else {
uint32_t r1, r2, r3, r4;
uint32_t ticks = atoi(argv[1]);
uint32_t tempo = atoi(argv[2]);
uint32_t grouplen = atoi(argv[3]);

r1 = ticks * tempo / grouplen;
r2 = ticks * (tempo / grouplen);
r3 = (ticks * (((tempo << 3) / grouplen))) >> 3;
r4 = (uint64_t)ticks * (uint64_t)tempo / grouplen;

printf("r1 = %u\nr2 = %u\nr3 = %u\nr4 = %u\n", r1, r2, r3, r4);
}
return 0;
}

And here how it runs with a set of real-life values that initially
borked my program:

../mul 9120 1090909 15370
r1 = 88429 <-- oops very bad
r2 = 638400 <-- more or less fine, but not very precise
r3 = 646380 <-- still not perfect, but acceptable precision
r4 = 647305 <-- perfect but slow

> Since grouplen does not change, can you find, at the start, gl1 and
> gl2, ideally close to the square root of grouplen, so that you can use
>
> (ticks / gl1) * (tempo / gl2)

I'm not sure I understand the goal here... Won't I still loose lots of
precision due to integer div rounding?

Mateusz

Am 31.12.2021 um 14:10 schrieb Öö Tiib:
> On Friday, 31 December 2021 at 14:53:24 UTC+2, Bonita Montero wrote:
>> Am 31.12.2021 um 11:02 schrieb Mateusz Viste:
>>
>>> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
>>> {
>>> return ticks * tempo / grouplen;
>> return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);
>>
>> 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.
>
> I suspect that minority of programmers work on code that should
> run on x86 right now. OP did not indicate that they are among such.

There are a lot of CPUs that have Vx * Vx = V2x multiplications.
ARM also.

2021-12-31 at 13:53 +0100, Bonita Montero wrote:
> Am 31.12.2021 um 11:02 schrieb Mateusz Viste:
>
> > uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t
> > tempo) {
> > return ticks * tempo / grouplen;
> return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);
>
> 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.

I should have mentioned what CPU I run this on, my bad. It is an Intel
80C86. 7 MHz, no FPU. Using 64 bits in any way is not really an option.

The machine is this one specifically: https://youtu.be/8ssDGBTssUI?t=97

Mateusz

On Friday, December 31, 2021 at 12:03:00 PM UTC+2, Mateusz Viste wrote:
> I have this little function:
>
> /* converts an amount of ticks into human time (micro-seconds)
> * timeunits: number of ticks to convert into actual time
> * tempo : the time length (in microseconds) of grouplen ticks
> */
> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> {
> return ticks * tempo / grouplen;
> }
>
> In practical situations the end result of this computation is
> guaranteed to always fit inside an uint32_t, but the above formula
> overflows easily in the (ticks * tempo) part.
>
> The easy & stupid way to avoid this overflow would be this:
>
> return ticks * (tempo / grouplen);
>
> ...but it's obviously not a good solution, since it may loose a lot of
> resolution. The hacky compromise that I currently use is this:
>
> return ticks * (((tempo << 3) / grouplen) >> 3);
>
> It works fine in my practical tests, so I might just as well be done
> with it, but I wonder if there is a cleaner approach to such seemingly
> simple problem?
>
> I should also add that this part of the program is performance
> critical, so I cannot afford branching or any other expensive
> computations. It's also worth noting that "grouplen" is guaranteed to
> be a positive number that never changes across the calls of the
> function (which, in truth, is not even a function, but it was easier to
> format it as such for this exercise).
>
> Mateusz

Couple of questions:
1. You said that grouplen never changes. Does it imply that tempo could change?
2. What is maximal expected value of ticks?
3. If the result is for human consumption, how could it be performance-critical? Humans are sloooooow.

Am 31.12.2021 um 14:31 schrieb Mateusz Viste:

> I should have mentioned what CPU I run this on, my bad. It is an Intel
> 80C86. 7 MHz, no FPU. Using 64 bits in any way is not really an option.

If a * b overflows you have no option other than using 64 bits if you
want to have an exact result.

Mateusz Viste <mateusz@xyz.invalid> wrote:
>2021-12-31 at 12:33 +0000, Ben Bacarisse wrote:
>>There's a technical detail here which is that in C unsigned arithmetic
>>can't overflow. Arithmetic overflow is reserved for serious undefined
>>situation. Unsigned arithmetic just "wraps round" in a defined
>>manner.
>Can you provide the source please? I know that what you describe is the

|A computation involving unsigned operands can never overflow,
|because a result that cannot be represented by the resulting
|unsigned integer type is reduced modulo the number that is
|one greater than the largest value that can be represented by
|the resulting type.
n2310, 6.2.5p9

2021-12-31 at 05:37 -0800, Michael S wrote:
> Couple of questions:
> 1. You said that grouplen never changes. Does it imply that tempo
> could change?

Yes, tempo can change during a song play.

> 2. What is maximal expected value of ticks?

Hard to say as there is no theoretical limit. In practice I have never
seen any value above like 10 * tempo, and tempo maxes out at about
2'000'000 (which translates to 30 BPM in the MIDI world). So we could
say that ticks is not expected to go above 20'000'000.

> 3. If the result is for human consumption, how could it be
> performance-critical? Humans are sloooooow.

Not when it comes to hearing frequencies and rhythm. The code is a MIDI
scheduler that computes the timing of individual MIDI notes. A
millisecond resolution is fine, but anything less starts to sound
laggy. This is why I compute everything in microseconds (as does MIDI
itself). One of the options I was pondering was to convert all values
into 1/10th of milliseconds and do computations on this... But it's an
even uglier approach than what I do now.

Mateusz

2021-12-31 at 13:41 GMT, Stefan Ram wrote:
> |A computation involving unsigned operands can never overflow,
> |because a result that cannot be represented by the resulting
> |unsigned integer type is reduced modulo the number that is
> |one greater than the largest value that can be represented by
> |the resulting type.
> n2310, 6.2.5p9

Had missed that one, thanks!

(In my ANSI C copy it is at 6.1.2.5, p23)

Mateusz

On Friday, December 31, 2021 at 3:55:35 PM UTC+2, Mateusz Viste wrote:
> 2021-12-31 at 05:37 -0800, Michael S wrote:
> > Couple of questions:
> > 1. You said that grouplen never changes. Does it imply that tempo
> > could change?
> Yes, tempo can change during a song play.

Then it's tough.
Still, if we can divide it into two parts, something like
void SetTempo(uint32_t grouplen, uint16_t tempo) that calculates
A = tempo/grouplen
B = ((tempo%grouplen) * 128)/grouplen
and
uint32_t ticks2time(uint32_t ticks) that uses A and B
and if SetTempo() is called many times less often than ticks2time() then situation could be improved.

> > 2. What is maximal expected value of ticks?
> Hard to say as there is no theoretical limit. In practice I have never
> seen any value above like 10 * tempo, and tempo maxes out at about
> 2'000'000 (which translates to 30 BPM in the MIDI world). So we could
> say that ticks is not expected to go above 20'000'000.

So, multiplication of ticks by number B in range 0:127 is o.k.

> > 3. If the result is for human consumption, how could it be
> > performance-critical? Humans are sloooooow.
> Not when it comes to hearing frequencies and rhythm. The code is a MIDI
> scheduler that computes the timing of individual MIDI notes. A
> millisecond resolution is fine, but anything less starts to sound
> laggy. This is why I compute everything in microseconds (as does MIDI
> itself). One of the options I was pondering was to convert all values
> into 1/10th of milliseconds and do computations on this... But it's an
> even uglier approach than what I do now.

I still don't understand, but so be it.

>
> Mateusz

2021-12-31 at 06:12 -0800, Michael S wrote:
> On Friday, December 31, 2021 at 3:55:35 PM UTC+2, Mateusz Viste wrote:
> > 2021-12-31 at 05:37 -0800, Michael S wrote:
> > > Couple of questions:
> > > 1. You said that grouplen never changes. Does it imply that tempo
> > > could change?
> > Yes, tempo can change during a song play.
>
> Then it's tough.

There are many constraints, yes.

> Still, if we can divide it into two parts, something like
> void SetTempo(uint32_t grouplen, uint16_t tempo) that calculates
> A = tempo/grouplen
> B = ((tempo%grouplen) * 128)/grouplen
> and
> uint32_t ticks2time(uint32_t ticks) that uses A and B
> and if SetTempo() is called many times less often than ticks2time()
> then situation could be improved.

You mean this, right?

uint32_t A = tempo / grouplen;
uint32_t B = (tempo % grouplen) * 128 / grouplen;
return ticks * A + (ticks * B) / 128;

another way to express it would be this:

return ticks * (tempo / grouplen) +
((ticks * (((tempo % grouplen) << 7) / grouplen)) >> 7);

This is close to my solution with bit shifting, but if I get it right
yours is more resilient to wraparounds as it only shifts a remainder
and not the whole tempo. Thanks for the pointer!

> I still don't understand, but so be it.

Another way to say it would be that the CPU is so slow that it
struggles with its current tasks so it doesn't have much time to fiddle
around with too much math (esp. 32-bit math). :)

Mateusz

On 2021-12-31, Mateusz Viste <mateusz@xyz.invalid> wrote:
> I have this little function:
>
> /* converts an amount of ticks into human time (micro-seconds)
> * timeunits: number of ticks to convert into actual time

There is no timeunits parameter; is that ticks?

> * tempo : the time length (in microseconds) of grouplen ticks
> */
> uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
> {
> return ticks * tempo / grouplen;
> }

Ticks are often longer than a microsecond, so it can be
resonably expected that tempo / grouplen > 1.

E.g. a 1000 Hz timer interrupt produces 1000 us ticks. We multiply
by 1000 to go from ticks to seconds. If ticks can go to UINT32_MAX,
then we cannot go to microseconds in 32 bit.

Therefore, this calculation has an inherent global overflow problem,
even if you address the local overflow in the multiplication.

We need:

(uint64_t) ticks * tempo / grouplen;

Computer Associates (of Accpac: see
https://en.wikipedia.org/wiki/Sage_300#History) used this as an interview
question all the time 30 years ago: how to do this kind of scaling
without overflow when the fraction is <= 1. E.g. for calculating
a percentage: X * 100 / Y, where X <= Y.

(Someone in management had used a calculation like this in displaying
free memory in the application years before that or something and were
super proud of their achievement, like that they are Knuth-level talent
and only such others should ever be hired.)

The trick is simply to scale the fraction X/Y down to make it smaller,
so that the multiplication has the headroom for avoiding overflow.

If we knew gcd(X, Y), we could divide X and Y by that to get an exact
equivalent in lowest terms; but that might be enough to eliminate the
overflow. Or even to do anything at all: what if gcd(X, Y) == 1?

What you can do is right shift X and Y until you have enough headroom
for the multiplication:

/* while the multiplication overflows, scale the fraction down */

while (ticks * tempo < ticks) {
ticks /= 2; /* compiles to a right shift */
grouplen /= 2;
}

/* [here, handle grouplen having vanished to zero] */

return ticks * tempo / grouplen;

> The easy & stupid way to avoid this overflow would be this:

> return ticks * (tempo / grouplen);

If the fraction is greater than 1 but grouplen isn't a divisor of
tempo, it's can be horribly inaccurate.

> ...but it's obviously not a good solution, since it may loose a lot of
> resolution. The hacky compromise that I currently use is this:

That will be completely useless in integer math if the fraction is < 1,
because then tempo / guardian is always zero, and it can be horribly
inaccurate when the fraction is > 1.

Supose tempo were *almost* twice grouplen, like 511/256. That
evaluates to 1. It's almost 100% off.

>
> return ticks * (((tempo << 3) / grouplen) >> 3);

So, if if a fixed shift works, you still want to do the multiplication
first, then division, for a better approximation.

return ticks * (tempo / 8) / (grouplen / 8);

I.e. same as pre-scaling the fraction:

tempo /= 8;
grouplen /= 8; /* could be zero! */
return ticks * tempo / grouplen;

This will only work if you know that the ticks value is always small
enough relative to tempo that three bits of headroom is enough.

E.g in our 511/256 example, after scaling by / 8 we get X * 63 / 64.
It's off, but nowhere near as much.

> computations. It's also worth noting that "grouplen" is guaranteed to
> be a positive number that never changes across the calls of the
> function (which, in truth, is not even a function, but it was easier to
> format it as such for this exercise).

OK, so then there may be a way to check somewhere else that the scaled
value grouplen / 8 is nonzero, to avoid division by zero, without
doing that for every calculation.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

On 31/12/2021 14:24, Mateusz Viste wrote:

> I'm sorry, you are correct of course. I copied the code wrong when
> typing the message and misplaced one set of parenthesis. Here's the
> actual hack I use:
>
> return (ticks * (((tempo << 3) / grouplen))) >> 3;
>
Hacks like that are common and, IMHO, entirely reasonable on limited
power small systems. I've used them regularly.

The risk, however, is that you make mistakes about when things can
overflow - particularly if something changes. It can all work fine for
a while until someone changes a scaling constant or range limits
somewhere else in the program, and you've got a silent bug.

Often you can reduce that risk by having the value "3" here calculated
automatically from the ranges, or at least defined in the same place as
any other relevant constants along with suitable comments. If you can,
it is a good idea to use static assertions to get compile-time failures
if something is going to go wrong:

_Static_assert(MAX_TICKS * ((tempo << 3) / grouplen)) < 0x100000000,
"Check that multiplication does not overflow");

"_Static_assert" was introduced in C11, but you can use macro-based
equivalents prior to that. I can post a useable definition if you need one.

On 2021-12-31, Mateusz Viste <mateusz@xyz.invalid> wrote:
> Not when it comes to hearing frequencies and rhythm. The code is a MIDI
> scheduler that computes the timing of individual MIDI notes. A
> millisecond resolution is fine, but anything less starts to sound
> laggy.

If you stand 3 meters away from your guitar amp stack, it takes 9
milliseconds to hear it due to speed of sound in air.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

2021-12-31 at 16:17 +0100, David Brown wrote:
> > return (ticks * (((tempo << 3) / grouplen))) >> 3;
> >
> Hacks like that are common and, IMHO, entirely reasonable on limited
> power small systems. I've used them regularly.

Ah, so I didn't invent anything... again.
Good, so it's not as stupid as I initially thought then.

> Often you can reduce that risk by having the value "3" here calculated
> automatically from the ranges, or at least defined in the same place
> as any other relevant constants along with suitable comments. If you
> can, it is a good idea to use static assertions to get compile-time
> failures if something is going to go wrong

Good idea. Thanks!

Mateusz

2021-12-31 at 15:19 -0000, Kaz Kylheku wrote:
> On 2021-12-31, Mateusz Viste <mateusz@xyz.invalid> wrote:
> > Not when it comes to hearing frequencies and rhythm. The code is a
> > MIDI scheduler that computes the timing of individual MIDI notes. A
> > millisecond resolution is fine, but anything less starts to sound
> > laggy.
>
> If you stand 3 meters away from your guitar amp stack, it takes 9
> milliseconds to hear it due to speed of sound in air.

Sure, lag is fine (in this context), but jitter is not.

I guess I should have said "sounds jitterish" in lieu of "sounds laggy".
Semantics. :)

Mateusz

2021-12-31 at 15:13 -0000, Kaz Kylheku wrote:
> There is no timeunits parameter; is that ticks?

Yes. I reworked the message a few times before posting to make it as
clear as possible, and of course added mistakes along the way...

> Ticks are often longer than a microsecond, so it can be
> resonably expected that tempo / grouplen > 1.

Actually, ticks are not a unit of time. Tempo is a unit of time
(in MIDI terms it's the length, in microseconds, of a quarter note).
Grouplen is the number of "ticks" (also called "unit time") in a quarter
note (which is also called a "beat").

But this does not matter anyway and I do not want to bore you to death.
In any case you are correct that tempo is likely to be greater than
grouplen, even though in theory it does not have to. Usually there's at
least a 100:1 relation between tempo and grouplen.

> E.g. a 1000 Hz timer interrupt produces 1000 us ticks. We multiply
> by 1000 to go from ticks to seconds. If ticks can go to UINT32_MAX,
> then we cannot go to microseconds in 32 bit.
>
> Therefore, this calculation has an inherent global overflow problem,
> even if you address the local overflow in the multiplication.

Nah, it works just fine. :)

The end result is a number of microseconds that represents the
delta-time of a MIDI note (that is "when will the next note occur").
2^32 microseconds is 71 minutes. I know no MIDI file that has such long
pauses in between notes. Sure, one could craft such abomination, but it
is not my ambition to cover such edge cases.

> What you can do is right shift X and Y until you have enough headroom
> for the multiplication:
>
> /* while the multiplication overflows, scale the fraction down */
> while (ticks * tempo < ticks) {
> ticks /= 2; /* compiles to a right shift */
> grouplen /= 2;
> }

Yes, that would be a good solution, if there was no time constraints.
The above loop is rich on branching and may lead to many
multiplications... That's a lot of cycles (for a 4 MHz CPU).

> > return ticks * (tempo / grouplen);
>
> If the fraction is greater than 1 but grouplen isn't a divisor of
> tempo, it's can be horribly inaccurate.

Yes, it is true. Fortunately in practice tempo is much higher than
grouplen, so the practical accuracy of this computation on "normal"
MIDI files is around 92-98%. Not perfect, but hard to hear. I then
added my bit-shifting hack which bumped accuracy to 98-99% - but with
some theoretical risk of introducing new overflows. Hence I was curious
what other people do in similar circumstances.

> > return ticks * (((tempo << 3) / grouplen) >> 3);
>
> So, if if a fixed shift works, you still want to do the multiplication
> first, then division, for a better approximation.
>
> return ticks * (tempo / 8) / (grouplen / 8);

I didn't thought of that, it's actually pretty neat - and
straightforward, too! With the only risk being that the CPU will burn
in flames if grouplen happens to be < 8 (but that's easy to check out of
the critical loop since grouplen never changes).

> > computations. It's also worth noting that "grouplen" is guaranteed
> > to be a positive number that never changes across the calls of the
> > function (which, in truth, is not even a function, but it was
> > easier to format it as such for this exercise).
>
> OK, so then there may be a way to check somewhere else that the scaled
> value grouplen / 8 is nonzero, to avoid division by zero, without
> doing that for every calculation.

Precisely, yes. I will do tests. Thank you for your input!

Mateusz

=?UTF-8?B?w5bDtiBUaWli?= <ootiib@hot.ee> writes:
>On Friday, 31 December 2021 at 14:53:24 UTC+2, Bonita Montero wrote:
>> Am 31.12.2021 um 11:02 schrieb Mateusz Viste:
>>
>> > uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t tempo)
>> > {
>> > return ticks * tempo / grouplen;
>> return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);
>>
>> 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.
>
>I suspect that minority of programmers work on code that should
>run on x86 right now. OP did not indicate that they are among such.

Indeed, and the OP subsequently clarified that it is a 16-bit
microcontroller.

2021-12-31 at 16:16 GMT, Scott Lurndal wrote:
> =?UTF-8?B?w5bDtiBUaWli?= <ootiib@hot.ee> writes:
> >On Friday, 31 December 2021 at 14:53:24 UTC+2, Bonita Montero wrote:
> >
> >> Am 31.12.2021 um 11:02 schrieb Mateusz Viste:
> >>
> >> > uint32_t ticks2time(uint32_t ticks, uint32_t grouplen, uint16_t
> >> > tempo) {
> >> > return ticks * tempo / grouplen;
> >> return (uint32_t)((uint64_t)ticks * (uint64_t)tempo / grouplen);
> >>
> >> 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.
> >
> >I suspect that minority of programmers work on code that should
> >run on x86 right now. OP did not indicate that they are among such.
> >
>
> Indeed, and the OP subsequently clarified that it is a 16-bit
> microcontroller.

Did not.
I said "16-bit Intel 80C86". You can't be more "x86" than that. :)

Mateusz

On 12/31/21 11:00 AM, Mateusz Viste wrote:
> 2021-12-31 at 15:13 -0000, Kaz Kylheku wrote:
>> There is no timeunits parameter; is that ticks?
>
> Yes. I reworked the message a few times before posting to make it as
> clear as possible, and of course added mistakes along the way...
>
>> Ticks are often longer than a microsecond, so it can be
>> resonably expected that tempo / grouplen > 1.
>
> Actually, ticks are not a unit of time. Tempo is a unit of time
> (in MIDI terms it's the length, in microseconds, of a quarter note).
> Grouplen is the number of "ticks" (also called "unit time") in a quarter
> note (which is also called a "beat").
>
> But this does not matter anyway and I do not want to bore you to death.
> In any case you are correct that tempo is likely to be greater than
> grouplen, even though in theory it does not have to. Usually there's at
> least a 100:1 relation between tempo and grouplen.
>
>> E.g. a 1000 Hz timer interrupt produces 1000 us ticks. We multiply
>> by 1000 to go from ticks to seconds. If ticks can go to UINT32_MAX,
>> then we cannot go to microseconds in 32 bit.
>>
>> Therefore, this calculation has an inherent global overflow problem,
>> even if you address the local overflow in the multiplication.
>
> Nah, it works just fine. :)
>
> The end result is a number of microseconds that represents the
> delta-time of a MIDI note (that is "when will the next note occur").
> 2^32 microseconds is 71 minutes. I know no MIDI file that has such long
> pauses in between notes. Sure, one could craft such abomination, but it
> is not my ambition to cover such edge cases.
>
>> What you can do is right shift X and Y until you have enough headroom
>> for the multiplication:
>>
>> /* while the multiplication overflows, scale the fraction down */
>> while (ticks * tempo < ticks) {
>> ticks /= 2; /* compiles to a right shift */
>> grouplen /= 2;
>> }
>
> Yes, that would be a good solution, if there was no time constraints.
> The above loop is rich on branching and may lead to many
> multiplications... That's a lot of cycles (for a 4 MHz CPU).
>
>>> return ticks * (tempo / grouplen);
>>
>> If the fraction is greater than 1 but grouplen isn't a divisor of
>> tempo, it's can be horribly inaccurate.
>
> Yes, it is true. Fortunately in practice tempo is much higher than
> grouplen, so the practical accuracy of this computation on "normal"
> MIDI files is around 92-98%. Not perfect, but hard to hear. I then
> added my bit-shifting hack which bumped accuracy to 98-99% - but with
> some theoretical risk of introducing new overflows. Hence I was curious
> what other people do in similar circumstances.
>
>>> return ticks * (((tempo << 3) / grouplen) >> 3);
>>
>> So, if if a fixed shift works, you still want to do the multiplication
>> first, then division, for a better approximation.
>>
>> return ticks * (tempo / 8) / (grouplen / 8);
>
> I didn't thought of that, it's actually pretty neat - and
> straightforward, too! With the only risk being that the CPU will burn
> in flames if grouplen happens to be < 8 (but that's easy to check out of
> the critical loop since grouplen never changes).
>
>>> computations. It's also worth noting that "grouplen" is guaranteed
>>> to be a positive number that never changes across the calls of the
>>> function (which, in truth, is not even a function, but it was
>>> easier to format it as such for this exercise).
>>
>> OK, so then there may be a way to check somewhere else that the scaled
>> value grouplen / 8 is nonzero, to avoid division by zero, without
>> doing that for every calculation.
>
> Precisely, yes. I will do tests. Thank you for your input!
>
>
> Mateusz
>

One thought is that if tempo and grouplen don't change often, that you
could precompute an n and k such that

k = (tempo << n) / grouplen

and

MAX_TICKS * k

doesn't overflow.

Then you compute (ticks * k) >> n for your result.