Unnormalized limbs in multiprecision user-defined literals

[ryanavella]

I am encountering unusual behavior where a number does not compare equal to itself after masking with a sufficiently wide bitmask.

Here is a simple reproducer:

#include <cassert>
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

// Comment this out to fix the uint384_t limbs
// vvvvvvvvvvvvv
#define CRASH_ME

namespace Mp = boost::multiprecision;

using uint384_t = Mp::number<Mp::cpp_int_backend<384, 384, Mp::unsigned_magnitude, Mp::unchecked, void>>;
BOOST_MP_DEFINE_SIZED_CPP_INT_LITERAL(384)

template <char... TStr>
constexpr uint384_t operator""_u384()
{
#ifdef CRASH_ME
    return operator""_cppui384 < TStr...>();
#else
    return operator""_cppui384 < TStr...>() + 1 - 1;
#endif
}

int main()
{
    constexpr auto value = 0x00000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111_u384;
    constexpr auto mask  = 0x0000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF_u384;

    constexpr auto masked = value & mask;

    std::cout << std::hex << "value:  0x" << value  << "\n";
    std::cout << std::hex << "masked: 0x" << masked << "\n";
    assert(value == masked);
}

Output:

value:  0x1111111111111111111111111111111111111111111111111111111111111111111111111111111111111
masked: 0x1111111111111111111111111111111111111111111111111111111111111111111111111111111111111
Assertion failed: value == masked, file main.cpp, line 33

Environment

Windows 11 (10.0.26200.8655)

Boost 1.88.0

MSVC 19.40.33813.0 (VS 2022, toolchain version 14.40)

I have not had much luck reproducing this under Linux/GCC, it may be MSVC specific.

[ckormanyos]

Hi @ryanavella thanks for your report and sorry about the somewhat late response. I modified your code slightly (it originally did not compile for me) and I can reproduce the cause of this phenomenon locally.

After the masking operation, the values of value and masked are numerically the same, but they have different sizes. To me this looks like a subtle bug. So I added the bug label to this issue.

Below is your modified reproducer, which also prints out the mismatched sizes of value and masked (11 and 12).

Cc: @jzmaddock

#include <boost/multiprecision/cpp_int.hpp>

#include <iostream>

namespace boost::multiprecision::literals {

#define BOOST_MP_LIT(P, N) BOOST_JOIN(operator "", BOOST_JOIN(P, N))
BOOST_MP_DEFINE_SIZED_CPP_INT_LITERAL(384)
#undef BOOST_MP_LIT

} // namespace boost::multiprecision::literals

namespace Mp = boost::multiprecision;
using namespace boost::multiprecision::literals;

using uint384_t = Mp::number<Mp::cpp_int_backend<384, 384, Mp::unsigned_magnitude, Mp::unchecked, void>, Mp::et_off>;

template <char... TStr>
constexpr uint384_t operator""_u384()
{
    return operator""_cppui384 < TStr...>();
}

int main()
{
    constexpr auto value = 0x00000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111_cppui384;
    constexpr auto mask  = 0x0000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF_cppui384;

    constexpr auto masked = value & mask;

    std::cout << std::hex << "value:  0x" << value  << "\n";
    std::cout << std::hex << "masked: 0x" << masked << "\n";

    const bool result_is_ok { (value == masked) };

    std::cout << "value.backend().size() : " << std::dec << value.backend().size() << std::endl;
    std::cout << "masked.backend().size(): " << std::dec << masked.backend().size() << std::endl;
    std::cout << "result_is_ok           : " << std::boolalpha << result_is_ok << std::endl;

    return (result_is_ok ? 0 : -1);
}

Output:

value:  0x1111111111111111111111111111111111111111111111111111111111111111111111111111111111111
masked: 0x1111111111111111111111111111111111111111111111111111111111111111111111111111111111111
value.backend().size() : 12
masked.backend().size(): 11
result_is_ok           : false

[ckormanyos]

I compiled with the develop branch of Multiprecision and a similar compiler as used in the original report (vc143).

The program compiles and succeeds on GCC for x86_64, as shown in this short link to Godbolt. But is succeeds since on that platform there is a 64-bit limb size and value and masked each round up the limb count to 6, instead of 11 and 12.

[ckormanyos]

When constructing traditionally from string representations without using a suffix, the program behaves as expected and the phenomenon (potential bug) seems to be gone.

#include <boost/multiprecision/cpp_int.hpp>

#include <iomanip>
#include <iostream>

namespace Mp = boost::multiprecision;

using uint384_t = Mp::number<Mp::cpp_int_backend<384, 384, Mp::unsigned_magnitude, Mp::unchecked, void>, Mp::et_off>;

int main()
{
    const uint384_t value("0x00000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111")/*_cppui384*/;
    const uint384_t mask ("0x0000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")/*_cppui384*/;

    const auto masked = value & mask;

    std::cout << std::hex << "value:  0x" << value  << "\n";
    std::cout << std::hex << "masked: 0x" << masked << "\n";

    const bool result_is_ok { (value == masked) };

    std::cout << "value.backend().size() : " << std::dec << value.backend().size() << std::endl;
    std::cout << "masked.backend().size(): " << std::dec << masked.backend().size() << std::endl;
    std::cout << "result_is_ok           : " << std::boolalpha << result_is_ok << std::endl;

    return (result_is_ok ? 0 : -1);
}

Output:

value:  0x1111111111111111111111111111111111111111111111111111111111111111111111111111111111111
masked: 0x1111111111111111111111111111111111111111111111111111111111111111111111111111111111111
value.backend().size() : 11
masked.backend().size(): 11
result_is_ok           : true

[ckormanyos]

OK the root cause is in shriinking the result of the masking operation in normalize().

In make_backend_from_pack in the literals header, both mask and value get created with 12 limbs.

After the actual masking operation, however, masked shrinks to 11 limbs.

This might be a design feature, or a bug. It is certainly unusual for the consumer experience.

[ryanavella]

Are the user defined literals the only way to produce these unnormalized values?

I will want to audit the relevant portions of my code to apply the workarounds where they are needed, and I'd like to confirm that I only need to audit the creation sites of literals.

[ckormanyos]

Are the user defined literals the only way to produce these unnormalized values?

I believe so.

And you're moving in the direction of a possible lasting correction. The existing normalize() method of cpp_int can (or could/should) be made constexpr. Therewith, the constexpr values can be normalized after initialization. Empty limbs will remain physically present, but the limb-count will be normalized, ensuring that the value is identical to expectation regarding tssize().

In the code below, I locally made the normalize() method of cpp_int to have the constexpr attribute. Then I can slightly modify the constexpr macros and it works. See code below.

I can try this fix in a branch within a few days, see if CI/CD likes it and maybe we can repair this bug.

---

This WORKS when normalize() is constexpr.

#include <boost/multiprecision/cpp_int.hpp>

#include <iostream>

namespace boost::multiprecision::literals {

#define BOOST_MP_LIT(P, N) BOOST_JOIN(operator "", BOOST_JOIN(P, N))

   template <char... STR>                                                                                                          
   constexpr boost::multiprecision::number<boost::multiprecision::backends::cpp_int_backend<384, 384, boost::multiprecision::unsigned_magnitude, boost::multiprecision::unchecked, void> > BOOST_MP_LIT(_cppui, 384)()
   {                                                                                                        
      using pt = typename boost::multiprecision::literals::detail::make_packed_value_from_str<STR...>::type;
      using local_backend_type = boost::multiprecision::backends::cpp_int_backend<384, 384, boost::multiprecision::unsigned_magnitude, boost::multiprecision::unchecked, void>;

      auto result { boost::multiprecision::literals::detail::make_backend_from_pack<pt, local_backend_type >::value };

      result.normalize();

      return result;
   }

#undef BOOST_MP_LIT

} // namespace boost::multiprecision::literals

namespace Mp = boost::multiprecision;
using namespace boost::multiprecision::literals;

using uint384_t = Mp::number<Mp::cpp_int_backend<384, 384, Mp::unsigned_magnitude, Mp::unchecked, void>, Mp::et_off>;

template <char... TStr>
constexpr uint384_t operator""_u384()
{
    return operator""_cppui384 < TStr...>();
}

int main()
{
    constexpr auto value = 0x00000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111_cppui384;
    constexpr auto mask  = 0x0000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF_cppui384;

    constexpr auto masked = value & mask;

    std::cout << std::hex << "value:  0x" << value  << "\n";
    std::cout << std::hex << "masked: 0x" << masked << "\n";

    constexpr bool result_is_ok { (value == masked) };

    static_assert(result_is_ok, "Error: unexpected non-equality");

    std::cout << "value.backend().size() : " << std::dec << value.backend().size() << std::endl;
    std::cout << "masked.backend().size(): " << std::dec << masked.backend().size() << std::endl;
    std::cout << "result_is_ok           : " << std::boolalpha << result_is_ok << std::endl;

    return (result_is_ok ? 0 : -1);
}

[ckormanyos]

A potential fix is cycling in #767. We won't quite make it into the July release. So it'll get into the November release if it cycles green and we agree on scope of change.