data range overflow cause infinite loop

[MoreGames]

While testing your algorithm and implementation on a middle large area, I noticed a problem in line

if (rightBound <= right) break; // right < rightBound

(line numer 422) in file LineOfSightScanner.cpp

In the underlying comparison

return o.d*n > o.n*d;

of the Fraction objects, the data range of int is easily exceeded, which can lead to negative numbers where there should be positive ones, which can lead to a comparison result of false instead of true, which can lead to an infinite loop.

I changed n and d of the Fraction class to long long for a simple solution to the problem (ignoring some implicit casts with potential data loss); for sure not the best way.

Maybe you can update your implementation for these cases.

Great work, easy to use, extensive description!

[Ohohcakester]

What's the size of the grid where the overflow occurred?
Does it work if you cast it to a (long long) only during the multiplication?

I believe the largest possible numerator for a fraction is sizeX*sizeY, while the largest possible denominator is sizeY (where sizeX, sizeY are the dimensions of the grid). So while values might overflow during the comparisons, I don't think the actual fractions themselves will overflow.

[MoreGames]

map size was 3840x2560
I didn't analyze the code, but I got example values o.n=3135, o.d=1, n=-1833230664 and d=1469755. It seems there are large numbers possible.

so far yes

[MoreGames]

I did some further tests and there are no problems if the borders are all blocked.
So, all good for me!
Again, great work!

[Ohohcakester]

I think the overflow in the numerator could have come about from the fraction arithmetic. While the final values are guaranteed(?) to be in that range I mentioned before, the values might overflow during arithmetic calculations like multiplications, causing the final stored result to be invalid.

I'll keep this issue open because the issue isn't actually fixed yet. overflow can still occur depending on the map.

A possible fix for this is to temporarily cast to (long long) during arithmetic operations / comparisons etc but continue to store the result as ints.

I'll look into this when I have the time to.

[billkotsias]

Hi @Ohohcakester . Great work! I am interested in using your implementation in a commercial product. Besides fixing these lines:
https://github.com/Ohohcakester/ENLSVG-Pathfinding/blob/master/Pathfinding/Fraction.h#L103-L107
to, say:
return (long long)(o.d)*n < (long long)(o.n)*d;
is there any other dubious place to look for such overflows?
Do the maps need to have blocked boundaries to avoid such issues?

[billkotsias]

@Ohohcakester also this is a bit dubious:
https://github.com/Ohohcakester/ENLSVG-Pathfinding/blob/master/Pathfinding/Fraction.h#L119
You cast the multiplication to (long) with is equal to casting it to (int) (so, no actual casting).
Maybe it should be casted to (long long), and change the following:
inline Fraction(int n, int d) {
inline void init(int n, int d) {
to use long long parameters?