Overflow in TemporalPropagator::getMinPerturbTimes on 32-bit

A minimal test case is forthcoming from Paul Morris.

This is what it looks like:

checkError(lb <= ub, "lb>ub in TemporalPropagator::getMinPerturbTimes");
1055    

In gdb, I see this

(gdb) p lb
$1 = -2147483637
(gdb) p ub
$2 = -2147483639

What version of the product are you using? On what operating system?

Europa-2.4 on Linux

Paul's current analysis:

I haven't fully analyzed this, but I see a problem a problem with the 
changes you made to DistanceGraph.hh

49  #define MAX_LENGTH (TIME_MAX/8)       // Largest length allowed for edge
50  #define MIN_LENGTH (TIME_MIN/8)       // Smallest length allowed for edge

...

57  #define MAX_DISTANCE MAX_INT   // Largest propagated distance for node
58  #define MIN_DISTANCE -MAX_INT   // Smallest propagated distance for node

The logic of the DistanceGraph propagation assumes that if you add an 
allowable length to a possible propagated distance, you cannot get an 
overflow of the basic type involved.

This means with 32-bit machines, we need to define things in a way such that

MAX_LENGTH + MAX_DISTANCE <= MAX_INT

This is not the case here,

MAX_LENGTH + MAX_DISTANCE = MAX_INT + MAX_INT/8

the way things are defined.  That might be the cause of my error, but I 
need to investigate further to confirm.  In any case, though, the above 
is wrong and will potentially cause overflows.

To be safe, you might define MAX_LENGTH and MAX_DISTANCE the same way 
and make them both, say, TIME_MAX/2.

Original issue reported on code.google.com by miata...@gmail.com on 4 Mar 2010 at 4:07

rpgoldman / europa-pso

Overflow in TemporalPropagator::getMinPerturbTimes on 32-bit #67