Bugs in fixed.h division

[hexagonrecursion]

Pioneer has its own fixed-precision arifmetic implementation. The code can be found in src/fixed.h
Usually we use 32 bits before the "decimal point" and 32 bits after, but StarSystemGenerator uses 16 bits before and 48 after.

The operator/ in fixed.h has multiple bugs.

Using C++20 rules

1. This is undefined behaviour (signed integer overflow) if d is INT64_MIN

   if (d < 0) {
       d = -d;
       isneg = 1;
   }
   

2. This is undefined behaviour (signed integer overflow) if isneg is true and Sint64(quotient_lo) is INT64_MIN

   return (isneg ? -Sint64(quotient_lo) : quotient_lo);
   

   Here is what I find ironic:

   1. Assuming I correctly understand the rules for the ternary operator with mixed types (a very optimistic assumption),
      the code above is equivalent to

      return (isneg ? Uint64(-Sint64(quotient_lo)) : quotient_lo);
      

   2. Assuming I correctly understand what the unary minus does for unsigned types,
      the only difference between Uint64(-Sint64(quotient_lo)) and -quotient_lo is that
      the former trigger undefined behaviour if quotient_lo is exactly 1 << 63

3. remainder can become negative, causing incorrect results. Here is one example, but any value of b such that abs(b.v) > (1 << 62) can be problematic.

   1. Let FRAC be 32
   2. Let a be 0x4000'0000.0000'0000 and b be 0x4000'0000.0000'0001 (Note the "hexadecimal point")
   3. The expected result is 0x0000'0000.ffff'ffff
   4. The actual result is 0

   Here is a proof of concept on godbolt

   d =  0x4000000000000001
   remainder =                   0 quotient_hi =          0x40000000 quotient_lo =                   0
   remainder =                   0 quotient_hi =          0x80000000 quotient_lo =                   0
   remainder =                   0 quotient_hi =         0x100000000 quotient_lo =                   0
   remainder =                   0 quotient_hi =         0x200000000 quotient_lo =                   0
   remainder =                   0 quotient_hi =         0x400000000 quotient_lo =                   0
   remainder =                   0 quotient_hi =         0x800000000 quotient_lo =                   0
   ...
   remainder =                   0 quotient_hi =  0x1000000000000000 quotient_lo =                   0
   remainder =                   0 quotient_hi =  0x2000000000000000 quotient_lo =                   0
   remainder =                   0 quotient_hi =  0x4000000000000000 quotient_lo =                   0
   remainder =                   0 quotient_hi = -0x8000000000000000 quotient_lo =                   0
   remainder =                 0x1 quotient_hi =                   0 quotient_lo =                   0
   remainder =                 0x2 quotient_hi =                   0 quotient_lo =                   0
   remainder =                 0x4 quotient_hi =                   0 quotient_lo =                   0
   remainder =                 0x8 quotient_hi =                   0 quotient_lo =                   0
   ...
   remainder =  0x1000000000000000 quotient_hi =                   0 quotient_lo =                   0
   remainder =  0x2000000000000000 quotient_hi =                   0 quotient_lo =                   0
   remainder =  0x4000000000000000 quotient_hi =                   0 quotient_lo =                   0
   remainder = -0x8000000000000000 quotient_hi =                   0 quotient_lo =                   0
   remainder =                   0 quotient_hi =                   0 quotient_lo =                   0
   ...
   remainder =                   0 quotient_hi =                   0 quotient_lo =                   0
   result = 0
   

4. Most combinarions of a negative a with any b produce incorrect results. It puzzles me greatly that no one noticed. Example:

   1. Let FRAC be 32
   2. Let a be -3.0 and b be 3.0
   3. The expected result is -1.0
   4. The actual result is 0x5555'5554.5555'5555

   Here is a proof of concept on godbolt

   d =                0x3
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffffffd00000000
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffffffa00000000
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffffff400000001
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffffffe800000002
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffffffd000000005
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffffffa00000000a
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffffff4000000015
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffffe800000002a
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffffd0000000055
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffffa00000000aa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffff40000000155
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffffe800000002aa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffffd00000000555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffffa00000000aaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffff400000001555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffe800000002aaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffd000000005555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfffa00000000aaaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfff4000000015555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffe800000002aaaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffd0000000055555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xffa00000000aaaaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xff40000000155555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfe800000002aaaaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfd00000000555555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xfa00000000aaaaaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xf400000001555555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xe800000002aaaaaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0xd000000005555555
   remainder =                0x1 quotient_hi = 0xffffffffffffffff quotient_lo = 0xa00000000aaaaaaa
   remainder =                  0 quotient_hi = 0xffffffffffffffff quotient_lo = 0x4000000015555555
   remainder =                0x1 quotient_hi = 0xfffffffffffffffe quotient_lo = 0x800000002aaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffffffffffd quotient_lo =         0x55555555
   remainder =                0x1 quotient_hi = 0xfffffffffffffffa quotient_lo =         0xaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffffffffff4 quotient_lo =        0x155555555
   remainder =                0x1 quotient_hi = 0xffffffffffffffe8 quotient_lo =        0x2aaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffffffffffd0 quotient_lo =        0x555555555
   remainder =                0x1 quotient_hi = 0xffffffffffffffa0 quotient_lo =        0xaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffffffffff40 quotient_lo =       0x1555555555
   remainder =                0x1 quotient_hi = 0xfffffffffffffe80 quotient_lo =       0x2aaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffffffffd00 quotient_lo =       0x5555555555
   remainder =                0x1 quotient_hi = 0xfffffffffffffa00 quotient_lo =       0xaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffffffff400 quotient_lo =      0x15555555555
   remainder =                0x1 quotient_hi = 0xffffffffffffe800 quotient_lo =      0x2aaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffffffffd000 quotient_lo =      0x55555555555
   remainder =                0x1 quotient_hi = 0xffffffffffffa000 quotient_lo =      0xaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffffffff4000 quotient_lo =     0x155555555555
   remainder =                0x1 quotient_hi = 0xfffffffffffe8000 quotient_lo =     0x2aaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffffffd0000 quotient_lo =     0x555555555555
   remainder =                0x1 quotient_hi = 0xfffffffffffa0000 quotient_lo =     0xaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffffff40000 quotient_lo =    0x1555555555555
   remainder =                0x1 quotient_hi = 0xffffffffffe80000 quotient_lo =    0x2aaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffffffd00000 quotient_lo =    0x5555555555555
   remainder =                0x1 quotient_hi = 0xffffffffffa00000 quotient_lo =    0xaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffffff400000 quotient_lo =   0x15555555555555
   remainder =                0x1 quotient_hi = 0xfffffffffe800000 quotient_lo =   0x2aaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffffd000000 quotient_lo =   0x55555555555555
   remainder =                0x1 quotient_hi = 0xfffffffffa000000 quotient_lo =   0xaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffff4000000 quotient_lo =  0x155555555555555
   remainder =                0x1 quotient_hi = 0xffffffffe8000000 quotient_lo =  0x2aaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffffd0000000 quotient_lo =  0x555555555555555
   remainder =                0x1 quotient_hi = 0xffffffffa0000000 quotient_lo =  0xaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffff40000000 quotient_lo = 0x1555555555555555
   remainder =                0x1 quotient_hi = 0xfffffffe80000000 quotient_lo = 0x2aaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffffd00000000 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xfffffffa00000000 quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffff400000001 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xffffffe800000002 quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffffd000000005 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xffffffa00000000a quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffff4000000015 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xfffffe800000002a quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffffd0000000055 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xfffffa00000000aa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffff40000000155 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xffffe800000002aa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffffd00000000555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xffffa00000000aaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffff400000001555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xfffe800000002aaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfffd000000005555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xfffa00000000aaaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfff4000000015555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xffe800000002aaaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xffd0000000055555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xffa00000000aaaaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xff40000000155555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xfe800000002aaaaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xfd00000000555555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xfa00000000aaaaaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xf400000001555555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xe800000002aaaaaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0xd000000005555555 quotient_lo = 0x5555555555555555
   remainder =                0x1 quotient_hi = 0xa00000000aaaaaaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                  0 quotient_hi = 0x4000000015555555 quotient_lo = 0x5555555555555555
   remainder =                  0 quotient_hi = 0x800000002aaaaaaa quotient_lo = 0xaaaaaaaaaaaaaaaa
   remainder =                0x1 quotient_hi =         0x55555555 quotient_lo = 0x5555555555555554
   remainder =                0x2 quotient_hi =         0xaaaaaaaa quotient_lo = 0xaaaaaaaaaaaaaaa8
   remainder =                0x1 quotient_hi =        0x155555555 quotient_lo = 0x5555555555555551
   remainder =                0x2 quotient_hi =        0x2aaaaaaaa quotient_lo = 0xaaaaaaaaaaaaaaa2
   remainder =                0x1 quotient_hi =        0x555555555 quotient_lo = 0x5555555555555545
   remainder =                0x2 quotient_hi =        0xaaaaaaaaa quotient_lo = 0xaaaaaaaaaaaaaa8a
   remainder =                0x1 quotient_hi =       0x1555555555 quotient_lo = 0x5555555555555515
   remainder =                0x2 quotient_hi =       0x2aaaaaaaaa quotient_lo = 0xaaaaaaaaaaaaaa2a
   remainder =                0x1 quotient_hi =       0x5555555555 quotient_lo = 0x5555555555555455
   remainder =                0x2 quotient_hi =       0xaaaaaaaaaa quotient_lo = 0xaaaaaaaaaaaaa8aa
   remainder =                0x1 quotient_hi =      0x15555555555 quotient_lo = 0x5555555555555155
   remainder =                0x2 quotient_hi =      0x2aaaaaaaaaa quotient_lo = 0xaaaaaaaaaaaaa2aa
   remainder =                0x1 quotient_hi =      0x55555555555 quotient_lo = 0x5555555555554555
   remainder =                0x2 quotient_hi =      0xaaaaaaaaaaa quotient_lo = 0xaaaaaaaaaaaa8aaa
   remainder =                0x1 quotient_hi =     0x155555555555 quotient_lo = 0x5555555555551555
   remainder =                0x2 quotient_hi =     0x2aaaaaaaaaaa quotient_lo = 0xaaaaaaaaaaaa2aaa
   remainder =                0x1 quotient_hi =     0x555555555555 quotient_lo = 0x5555555555545555
   remainder =                0x2 quotient_hi =     0xaaaaaaaaaaaa quotient_lo = 0xaaaaaaaaaaa8aaaa
   remainder =                0x1 quotient_hi =    0x1555555555555 quotient_lo = 0x5555555555515555
   remainder =                0x2 quotient_hi =    0x2aaaaaaaaaaaa quotient_lo = 0xaaaaaaaaaaa2aaaa
   remainder =                0x1 quotient_hi =    0x5555555555555 quotient_lo = 0x5555555555455555
   remainder =                0x2 quotient_hi =    0xaaaaaaaaaaaaa quotient_lo = 0xaaaaaaaaaa8aaaaa
   remainder =                0x1 quotient_hi =   0x15555555555555 quotient_lo = 0x5555555555155555
   remainder =                0x2 quotient_hi =   0x2aaaaaaaaaaaaa quotient_lo = 0xaaaaaaaaaa2aaaaa
   remainder =                0x1 quotient_hi =   0x55555555555555 quotient_lo = 0x5555555554555555
   remainder =                0x2 quotient_hi =   0xaaaaaaaaaaaaaa quotient_lo = 0xaaaaaaaaa8aaaaaa
   remainder =                0x1 quotient_hi =  0x155555555555555 quotient_lo = 0x5555555551555555
   remainder =                0x2 quotient_hi =  0x2aaaaaaaaaaaaaa quotient_lo = 0xaaaaaaaaa2aaaaaa
   remainder =                0x1 quotient_hi =  0x555555555555555 quotient_lo = 0x5555555545555555
   remainder =                0x2 quotient_hi =  0xaaaaaaaaaaaaaaa quotient_lo = 0xaaaaaaaa8aaaaaaa
   remainder =                0x1 quotient_hi = 0x1555555555555555 quotient_lo = 0x5555555515555555
   remainder =                0x2 quotient_hi = 0x2aaaaaaaaaaaaaaa quotient_lo = 0xaaaaaaaa2aaaaaaa
   remainder =                0x1 quotient_hi = 0x5555555555555555 quotient_lo = 0x5555555455555555
   result = 0x5555555455555555
   

Style notes

1. int isneg should be bool isneg

2. To me this code:

   if (sbit) remainder |= 1;
   // shift quotient left 1
   {
       quotient_hi <<= 1;
       if (quotient_lo & (Uint64(1) << 63)) quotient_hi |= 1;
       quotient_lo <<= 1;
   }
   

   Looks as if it ment this:

   if (sbit)
   {
       quotient_hi <<= 1;
       if (quotient_lo & (Uint64(1) << 63)) quotient_hi |= 1;
       quotient_lo <<= 1;
   }
   

   But it actually means:

   if (sbit) {
       remainder |= 1;
   }
   
   // shift quotient left 1
   {
       quotient_hi <<= 1;
       if (quotient_lo & (Uint64(1) << 63)) quotient_hi |= 1;
       quotient_lo <<= 1;
   }
   

Using C++17 rules

Pioneer currently targets the C++17 standard:

pioneer/CMakeLists.txt

Line 5 in 97d7be6

set(CMAKE_CXX_STANDARD 17)

C++17 is much less permissive than C++20 when it comes to <<, >> and unsigned-to-signed conversions:

1. a.v >> (64 - FRAC) is implementation-defined if a.v < 0
2. a.v << FRAC is undefined if a.v < 0
3. quotient_hi <<= 1; is implementation-defined if the mathematical value of quotient_hi * 2 is greater than INT64_MAX (because the defenition of << references unsigned-to-signed conversion)
4. quotient_hi <<= 1; is undefined if quotient_hi < 0
5. Sint64(quotient_lo) is implementation-defined if quotient_lo is greater than INT64_MAX
6. The return statement converts Uint64 to fixedf, which requires an implicit conversion to Sint64. The conversion is implementation-defined if the returned value is greater than INT64_MAX

• 3 and 4 are triggered multiple times for every a except 0.
• 1, 3 and 5 appear to be OK according to the gcc documentation
• 1 appears to be OK in Microsoft C++
• 3 and 5 appear to be OK in Microsoft C++
• Because Clang does not document implementation-defined behaviour, we can only hope and pray it does what gcc does.

Note

I think most of this issues can be fixed by using only Uint64 inside this function.

Safely obtaining the modulus of a signed integer as an unsigned integer

Adapend for out needs:

Uint64 uabs(Sint64 input)
{
    if (input >= 0)
    {
        return static_cast<Uint64>(input);
    }
    else
    {
        return -static_cast<Uint64>(input);
    }
}