Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: How to avoid an overflow during multiplication?
Date: Tue, 04 Jan 2022 07:20:02 -0800
Organization: A noiseless patient Spider
Lines: 40
Message-ID: <86bl0ry1ct.fsf@linuxsc.com>
References: <sqmkg9$157v$1@gioia.aioe.org> <muldiv-20211231201955@ram.dialup.fu-berlin.de> <sqo611$vte$1@dont-email.me> <unsigned-char-20220101012417@ram.dialup.fu-berlin.de> <sqo86f$a7j$1@dont-email.me> <uint32_t-20220101030736@ram.dialup.fu-berlin.de> <PS-20220101032942@ram.dialup.fu-berlin.de> <sqqroj$4ef$1@dont-email.me> <formula-20220102025135@ram.dialup.fu-berlin.de> <sr0m4h$vu3$1@dont-email.me> <sr11bc$1thv$2@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="2bc79595ad25cbbea7e3c7177d1db1a2"; logging-data="25376"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19gIqX1hoCZX8Xet6fo4fo8xKTRL+0DRyM="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:Rc0tqWOjjOxjMPkjBLSxcp7jy08= sha1:3WEBGKiB2xysWVRQcDRZyclIQbs=
Xref: csiph.com comp.lang.c:164270

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.