Correct C FixedMul() off-by-one errors

The FixedMul() C implementation would produce off by one results, causing constant desyncs on 64 bit builds and builds without an ASM implementation of the function.

This is fixed by shifting instead of dividing, possibly avoiding rounding errors.

The following example program can be used to confirm this issue.

Please note, the right shift in FixedMulWorking below results in undefined behaviour. A better implementation would be

return (fixed_t)(((UINT64)((INT64)a * b)) >> FRACBITS);

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

#define FRACBITS 16
#define FRACUNIT (1<<FRACBITS)

typedef int32_t INT32;
typedef int64_t INT64;
typedef INT32 fixed_t;

fixed_t FixedMul(fixed_t a, fixed_t b)
{
	return (fixed_t)((((INT64)a * b) ) / FRACUNIT);
}

fixed_t FixedMulWorking(fixed_t a, fixed_t b)
{
	return (fixed_t)((((INT64)a * b) ) >> FRACBITS);
}

fixed_t FixedMulAsm(fixed_t a, fixed_t b) // asm
{
    fixed_t ret;
    asm
	(
		 "imull %2;"           // a*b
		 "shrdl %3,%%edx,%0;"  // shift logical right FRACBITS bits
		:"=a" (ret)            // eax is always the result and the first operand (%0,%1)
		:"0" (a), "r" (b)      // and %2 is what we use imull on with what in %1
		, "I" (FRACBITS)       // %3 holds FRACBITS (normally 16)
		:"%cc", "%edx"         // edx and condition codes clobbered
	);
	return ret;
}

int main()
{
    fixed_t a = 16384;
    fixed_t b = -49261;
    printf("FixedMul: %i\n", FixedMul(a, b));
    printf("FixedMulWorking: %i\n", FixedMulWorking(a, b));
    printf("FixedMulAsm: %i\n", FixedMulAsm(a, b));
    return 0;
}

Which returns:

FixedMul: -12315
FixedMulWorking: -12316
FixedMulAsm: -12316

Can also be reproduced with many other numbers, some of them being shown here:

Jesus this is a biggun. I assume you've already tried comparing the FixedDiv implementations as well?

tbh I'm pretty sure the game is compiled with one of the ASM versions by default, but nice find in any case dumb me you weren't necessarily talking about Windows builds

hm, wait, on checking what the answer would be with Windows Calc, I get -12315.25.

So evidently the answer is rounded down with the divide, and rounded up with bitshift. Heh

Can you make a copy of you fork on GitHub so there will be a pull request there?

Continuing my findings with Windows Calc as support...

• (16384 * -49261) >> 16 = -12316
• (16384 * 49261) >> 16 = 12315

@MonsterIestyn from what I saw the x86 asm code didn't get included on 64 bit builds on general due to an ifdef in the header, but I'm talking about Linux builds at least. It's also not necessarily about accuracy but about what the existing builds use for netplay.

With this, 64 bit Linux builds can play just fine against others without desyncing and disconnecting.

@toaster I have not, but I assumed that because it multiplies, and because it didn't have netplay issues, that it doesn't have this issue. I'll check later to confirm and report back.

@Alam I will once I get back home.

Thanks

Yeah, was just learning via Wikipedia that divide != right bit shift precisely because of rounding of negative numbers, funnily enough. The ASM version evidently has been using bit-shifting all this time as far as I can tell, so yeah.

But if this really does fix the netgame issues, that would be great.

Sounds good to me, sounds like it's been through the testing too. It'll be nice to be able to netplay without needing to cross-compile for once.

added 1 commit

• 001e4e11 - Correct C FixedMul() off-by-one errors

Compare with previous version

Apologies for the delay. Thanks to light2yellow, it was pointed out that shifting negative integers was undefined behaviour in C. I have worked around that, and after 3 hours of playing on a 64 bit server with 32 bit clients using the asm code with quite a few people, I can confirm that this fix does indeed work.

Github PR is here https://github.com/STJr/SRB2/pull/259

EDIT: I have also kept the old commit/code for reference in the fixedmul-c-fix-undefined branch

changed the description

changed the description

merged

mentioned in commit 650e0eaf