[multiprecision review] Possible use of uninitialised value
Dear All, I decided to try to evaluate the proposed Boost.Multiprecision on the code that I wrote recently when looking at the proposed Delaunay Triangulation / Voronoi Diagram code. Specifically, this function: inline bool delaunay_test(int32_t ax, int32_t ay, int32_t bx, int32_t by, int32_t cx, int32_t cy, int32_t dx, int32_t dy) { // Test whether the quadrilateral ABCD's diagonal AC should be flipped to BD. // This is the Cline & Renka method. // Flip if the sum of the angles ABC and CDA is greater than 180 degrees. // Equivalently, flip if sin(ABC + CDA) < 0. // Trig identity: cos(ABC) * sin(CDA) + sin(ABC) * cos(CDA) < 0 // We can use scalar and vector products to find sin and cos, and simplify // to the following code. // Numerical robustness is important. This code addresses it by performing // exact calculations with large integer types. i64 ax64 = ax, ay64 = ay, bx64 = bx, by64 = by, cx64 = cx, cy64 = cy, dx64 = dx, dy64 = dy; i64 cos_abc = (ax64-bx64)*(cx64-bx64) + (ay64-by64)*(cy64-by64); i64 cos_cda = (cx64-dx64)*(ax64-dx64) + (cy64-dy64)*(ay64-dy64); if (cos_abc >= 0 && cos_cda >= 0) return false; if (cos_abc < 0 && cos_cda < 0) return true; i64 sin_abc = (ax64-bx64)*(cy64-by64) - (cx64-bx64)*(ay64-by64); i64 sin_cda = (cx64-dx64)*(ay64-dy64) - (ax64-dx64)*(cy64-dy64); i128 sin_sum = static_cast<i128>(sin_abc)*cos_cda + static_cast<i128>(cos_abc)*sin_cda; return sin_sum < 0; } Here i64 and i128 are typedefs for appropriate 64- and 128-bit signed integer types. when I try to use boost::multiprecision::cpp_int, I get answers that are only mostly correct. Specifically, sometimes the very first call gives the wrong answer. It is dependent on the number of iterations of my benchmark loop and other factors. valgrind reports the following: ==15713== Conditional jump or move depends on uninitialised value(s) ==15713== at 0x8053B0C: boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>::mp_number<boost::multiprecision::detail::plus, boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, void, void>, boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, void, void>, void, void>(boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::plus, boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, void, void>, boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, void, void>, void, void> const&) (in /home/phil/boost_mp_review/benchmark) As expected, the error is impenetrable. Can anyone guess what is going on? (I seem to get the right answers and no valgrind errors with the fixed-size and no-expression-templates types.) Regards, Phil.
I decided to try to evaluate the proposed Boost.Multiprecision on the code that I wrote recently when looking at the proposed Delaunay Triangulation / Voronoi Diagram code. Specifically, this function:
Phil I need much more information - I just double checked and the cpp_int tests all pass under valgrind - and a cursory test of your function also passes cleanly with valgrind here, so I need: * Compiler and platform. * The arguments passed to delaunay_test in the failed test, or, the complete test program. * The definitions for the typedefs i64 and i128. I'm sorry you're experiencing these issues, but thanks for the interest! Regards, John.
The valgrind error I mentioned previously seems to be due to this code at cpp_int.hpp line 967: result.resize(x); typename cpp_int_backend<MinBits, Signed, Allocator>::const_limb_pointer pa = a.limbs(); typename cpp_int_backend<MinBits, Signed, Allocator>::const_limb_pointer pb = b.limbs(); typename cpp_int_backend<MinBits, Signed, Allocator>::limb_pointer pr = result.limbs(); bool swapped = false; int c = a.compare_unsigned(b); resize() doesn't zero-initialise the new storage. In this particular case, a == result because the expression being evaluated is something like result = result + other. So resizing result is also resizing a. Hence the compare_unsigned looks at the limbs of a that have just been added by the resize, which are undefined. It appears that this could be fixed by zeroing the new limbs in resize(), but that is unnecessary in other cases. Is it even correct that a == result is possible in this code? Regards, Phil.
resize() doesn't zero-initialise the new storage. In this particular case, a == result because the expression being evaluated is something like result = result + other. So resizing result is also resizing a. Hence the compare_unsigned looks at the limbs of a that have just been added by the resize, which are undefined.
It appears that this could be fixed by zeroing the new limbs in resize(), but that is unnecessary in other cases. Is it even correct that a == result is possible in this code?
Yes, inplace subtraction is OK. Here's the fix I'm testing: Index: cpp_int.hpp =================================================================== --- cpp_int.hpp (revision 78943) +++ cpp_int.hpp (working copy) @@ -964,12 +964,16 @@ result.sign(s); return; } + // This isn't used till later, but comparison has to occur before we resize the result, + // as that may also resize a or b if this is an inplace operation: + int c = a.compare_unsigned(b); + // Set up the result vector: result.resize(x); + // Now that a, b, and result are stable, get pointers to their limbs: typename cpp_int_backend<MinBits, Signed, Allocator>::const_limb_pointer pa = a.limbs(); typename cpp_int_backend<MinBits, Signed, Allocator>::const_limb_pointer pb = b.limbs(); typename cpp_int_backend<MinBits, Signed, Allocator>::limb_pointer pr = result.limbs(); bool swapped = false; - int c = a.compare_unsigned(b); if(c < 0) { swap(pa, pb); John.
participants (2)
-
John Maddock -
Phil Endecott