[boost] [mp_int] Possible bug in comparison with native types causes overflow_error

Subject: [boost] [mp_int] Possible bug in comparison with native types causes overflow_error
From: Nathan Kitchen (nathan.kitchen_at_[hidden])
Date: 2009-01-09 20:04:27

I'm getting some strange crashes when I try to compare mp_ints with
native types. The code below is sufficient to reproduce it:

#include <stdint.h>
#include <iostream>
#include <boost/mp_math/mp_int.hpp>

using namespace boost::mp_math;
using namespace std;

int main()
{
  mp_int<> a = mp_int<>("0x100000000");
  cout << (1 < a) << endl;

  return 0;
}

The problem appears to be the definition of integral_ops_impl<...,
true>::q (i.e., for signed IntegralT):

  static const typename MpInt::size_type q =
    std::numeric_limits<IntegralT>::digits + (MpInt::valid_bits - 1)
    / MpInt::valid_bits;

In the case where IntegralT=int32_t and digit_type=uint32_t, q is 31.
Contrast this with the definition for unsigned IntegralT:

  static const typename MpInt::size_type q =
    std::numeric_limits<IntegralT>::digits / (MpInt::valid_bits + 1) + 1;

When IntegralT=uint32_t and digit_type=uint32_t, q is 1.

The overflow of operator< comes because the check that verifies that
the MpInt can't fit in an IntegralT is (condition (lhs.size() > q).
This fails for q=31. If the definition of q had the first line
parenthesized:

  static const typename MpInt::size_type q =
    (std::numeric_limits<IntegralT>::digits + MpInt::valid_bits - 1)
    / MpInt::valid_bits;

then q would be 1, and the code branch with the overflow would not be taken.

-- Nathan