Boost.Multiprecision generates incorrect code

[Sam Lunt <samuel.j.lunt@…>]

Comparing two identical functions, one using boost::multiprecision::uint128_t and the other using GCC/Clang builtin unsigned __int128:

auto foo(std::uint64_t lhs, std::uint64_t rhs) -> std::uint64_t
{
    boost::multiprecision::uint128_t a(lhs);
    a *= rhs;
    return static_cast<std::uint64_t>(a >> 64) 
         + static_cast<std::uint64_t>(a);
}

auto bar(std::uint64_t lhs, std::uint64_t rhs) -> std::uint64_t
{
    unsingned __int128 a(lhs);
    a *= rhs;
    return static_cast<std::uint64_t>(a >> 64) 
         + static_cast<std::uint64_t>(a);
}

Comparing the outputs of each function, they return different results for (-1ULL, -1ULL), (-1ULL, 2), (-1ULL, 3), and presumably others. (foo returns 18446744073709551613, 0, and 1, respectively).

Comparing the results to Python's big int type (the builtin int), it seems that the foo results are not correct and the bar results are (this can also be confirmed by hand). This is also confirmed by looking at the disassembly for the each function:

0000000000000000 <foo(unsigned long, unsigned long)>:
   0:	48 89 f0             	mov    %rsi,%rax
   3:	48 f7 e7             	mul    %rdi
   6:	48 83 f8 ff          	cmp    $0xffffffffffffffff,%rax
   a:	48 89 d1             	mov    %rdx,%rcx
   d:	48 83 d9 00          	sbb    $0x0,%rcx
  11:	48 c7 c1 ff ff ff ff 	mov    $0xffffffffffffffff,%rcx
  18:	48 0f 43 c1          	cmovae %rcx,%rax
  1c:	48 01 d0             	add    %rdx,%rax
  1f:	c3                   	retq   

0000000000000020 <bar(unsigned long, unsigned long)>:
  20:	48 89 f0             	mov    %rsi,%rax
  23:	48 f7 e7             	mul    %rdi
  26:	48 01 d0             	add    %rdx,%rax
  29:	c3                   	retq   

These results were consistent when compiling with clang++ (5.0.0) and g++ (6.3.1) and when compiling with optimization enabled and disabled.

[John Maddock]

This was deliberate, but on reflection is a mistake.

The issue is in the narrowing conversion from 128 to 64 bit integer - you are relying on this being truncation, but there's nothing in the standard to specify or guarantee that - instead it's implementation defined behaviour and is permitted to vary by compiler and/or platform. Boost.Multiprecision's default interconversion functions convert a value that would overflow the destination type to the maximum value that type can hold. This part is the mistake for unsigned integers (and only for unsigned integers) which should probably follow the common practice of truncation.

[Sam Lunt <samuel.j.lunt@…>]

Looking at the standard, it seems that conversion to signed type is implementation defined, but for conversion to unsigned, truncation is mandated.

This is from section 4.7.2 and 4.7.3 [conv.integral]:

2. If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source integer (modulo 2ⁿ where n is the number of bits used to represent the unsigned type). [Note: In a two’s complement representation, this conversion is conceptual and there is no change in the bit pattern (if there is no truncation). — end note]

3. If the destination type is signed, the value is unchanged if it can be represented in the destination type; otherwise, the value is implementation-defined.

Is it possible to change the behavior to match the standard? I can image there could be some concern about a behavior change, but I'd wonder how many people are depending on this behavior and how many expect truncation but get saturation.

[Данил Ильиных <woodroof@…>]

Discovered the same bug :( Had to change code to static_cast<uint64_t>(v & 0xfffffffffffffffflu).

[anonymous]

Fixed in develop for all conversions of (signed or unsigned) integers to unsigned.