[polygon] Valgrind errors when normalizing any angle polygons

Josh Pieper

4 Nov 2010 4 Nov '10

10:54 p.m.

Hello, We have been using the 1.44.0 release of polygon for some internal projects and have come across a number of oddities. The first one I've got is a valgrind error when normalizing polygons with numerically large coordinate values. Using the gmp_override.hpp header does resolve these problems, but my understanding is that it is the intent for the library to merely be numerically imprecise, rather than crash, for coordinates which are too large. Our simplified test case is below, and was compiled on an AMD64 Ubuntu 10.4 system. The first call to Normalize has no problems, but the second call causes valgrind to report both uninitialized memory usage and invalid reads. (I can produce the valgrind log on demand, but it is somewhat large for inclusion in an email). While we have deployed 1.44.0 internally, I tested against the most recent svn version and the problem still exists. Is this merely a mis-use of the API? Regards, Josh Pieper ------------------------ #include #include "boost_polygon/r66294/polygon/polygon.hpp" typedef boost::polygon::point_data BoostPoint; typedef boost::polygon::polygon_data BoostPolygon; typedef boost::polygon::polygon_set_data BoostPolygonSet; typedef boost::polygon::polygon_with_holes_data BoostPolygonWithHoles; typedef std::vector<BoostPolygonWithHoles> BoostPolygonWithHolesVector; template <typename Array> void Normalize(const Array& data, int32_t scale) { std::vector<BoostPoint> points; for (size_t i = 0; i < sizeof(data) / sizeof(*data); i += 2) { points.push_back(BoostPoint(data[i] / scale, data[i + 1] / scale)); } using namespace boost::polygon::operators; BoostPolygonSet poly_set; poly_set |= BoostPolygon(points.begin(), points.end()); BoostPolygonWithHolesVector normal; poly_set.get(normal); } int main() { int32_t data[] = { 0, 0, -1000000, -1000000, 19000000, -1000000, 18292893, 707106, 8292893, -9292893, 8170784, -9440890, 8078584, -9610754, 8000000, -10000000, 8078584, -10389245, 8170784, -10559109, 8292893, -10707106, 18292893, -20707106, 19000000, -19000000, -1000000, -19000000, 0, -20000000, 0, 0, }; Normalize(data, 10); // Fine. Normalize(data, 1); // Crashes. }

Show replies by date

Simonson, Lucanus J

5 Nov 5 Nov

2:28 a.m.

Josh Pieper wrote:

...

Hello,

We have been using the 1.44.0 release of polygon for some internal projects and have come across a number of oddities. The first one I've got is a valgrind error when normalizing polygons with numerically large coordinate values. Using the gmp_override.hpp header does resolve these problems, but my understanding is that it is the intent for the library to merely be numerically imprecise, rather than crash, for coordinates which are too large.

No, I fully expect the library may crash or exhibit other undefined behaviors if coordinates are too large and gmp is not used. If the coordinates are small enough that the numerator and denominator of the line intersection equation fit in the floating point representation without roundoff then the library may work correctly without the need for gmp, but in general I don't advise using the library without gmp. You will quickly find that in order to avoid rounding error issues you want to scale your data up, which won't work if you are trying to keep things within a ~16 bit range.

...

Our simplified test case is below, and was compiled on an AMD64 Ubuntu 10.4 system. The first call to Normalize has no problems, but the second call causes valgrind to report both uninitialized memory usage and invalid reads. (I can produce the valgrind log on demand, but it is somewhat large for inclusion in an email). While we have deployed 1.44.0 internally, I tested against the most recent svn version and the problem still exists.

I just checked into the trunk today a couple changes that should make the library more reliable without the use of gmp. My version number for the checkin is 66403. The sandbox version is older than the 1.44 release. I stopped syncing the sandbox once I merged to the release branch and now do all development on the trunk. Included in this checkin were several fixes for resizing that didn't make it in time for the 1.45 release. If you plan to use resizing you should update.

...

Is this merely a mis-use of the API?

I would say yes, but only because you expected the library to be reliable without using gmp. Right now I can't provide that and make no promises about reliability if gmp is not used. You mentioned a number of oddities but describe only one. What else have you run into? Thanks, Luke

Josh Pieper

9:43 a.m.

New subject: [polygon] Valgrind errors when normalizing any angle polygons

On Thu, Nov 4, 2010 at 10:28 PM, Simonson, Lucanus J wrote:

...

No, I fully expect the library may crash or exhibit other undefined behaviors if coordinates are too large and gmp is not used. If the coordinates are small enough that the numerator and denominator of the line intersection equation fit in the floating point representation without roundoff then the library may work correctly without the need for gmp, but in general I don't advise using the library without gmp. You will quickly find that in order to avoid rounding error issues you want to scale your data up, which won't work if you are trying to keep things within a ~16 bit range.

Would it be worth it to BOOST_ASSERT if data too large for the given types is passed in without gmp enabled? I would expect that an assertion is probably more desirable than undefined behavior. For a platform with a given maximum floating point resolution, what is the maximum integral value that may be used without triggering instability? On this system, a long double has 64 bits of mantissa. Does that mean the gmp-less boost::polygon is limited to 64/4 = 16 bits of resolution? We're using gmp now, so this is purely for my curiosity.

...

I just checked into the trunk today a couple changes that should make the library more reliable without the use of gmp. My version number for the checkin is 66403. The sandbox version is older than the 1.44 release. I stopped syncing the sandbox once I merged to the release branch and now do all development on the trunk. Included in this checkin were several fixes for resizing that didn't make it in time for the 1.45 release. If you plan to use resizing you should update.

...
Is this merely a mis-use of the API?

I would say yes, but only because you expected the library to be reliable without using gmp. Right now I can't provide that and make no promises about reliability if gmp is not used.

Fair enough.

...

You mentioned a number of oddities but describe only one. What else have you run into?

We had hoped to use resizing, ran into the aforementioned problems, then ran into different ones after trying trunk. I believe they were related to using beveled corners, but I still need to reduce our problems to minimal cases. Thanks for the quick reply! Regards, Josh

Simonson, Lucanus J

7:44 p.m.

New subject: [polygon] Valgrind errors when normalizing any angle polygons

Josh Pieper wrote:

...

On Thu, Nov 4, 2010 at 10:28 PM, Simonson, Lucanus J wrote:

...
No, I fully expect the library may crash or exhibit other undefined behaviors if coordinates are too large and gmp is not used. If the coordinates are small enough that the numerator and denominator of the line intersection equation fit in the floating point representation without roundoff then the library may work correctly without the need for gmp, but in general I don't advise using the library without gmp. You will quickly find that in order to avoid rounding error issues you want to scale your data up, which won't work if you are trying to keep things within a ~16 bit range.

Would it be worth it to BOOST_ASSERT if data too large for the given types is passed in without gmp enabled? I would expect that an assertion is probably more desirable than undefined behavior.

It is an interesting idea, I'll think about it. There is a chance the library would succeed for large coordinates, so asserting in cases where it would succeed seems not desirable. Also I don't want to guarentee that it succeed for small coordinates since it wasn't really my intent to make it rubust in that way. Computing the scale of data where problems can occur is a little complex. I don't know how to detect how many bits are in the mantissa of the long double data type at compile time. Is an assert, which is an excpetion better than the valgrind exception or whatever other exception you get? The library is exception safe and you should be able to catch any of them and conclude that there was a precision problem due to not using gmp.

...

For a platform with a given maximum floating point resolution, what is the maximum integral value that may be used without triggering instability? On this system, a long double has 64 bits of mantissa. Does that mean the gmp-less boost::polygon is limited to 64/4 = 16 bits of resolution? We're using gmp now, so this is purely for my curiosity.

x_num = (x11 * dy1 * dx2 - x21 * dy2 * dx1 + y21 * dx1 * dx2 - y11 * dx1 * dx2); d** = scale + 1 Scale + (scale + 1) + (scale + 1) + 1 + 1 + 1 = bits required. If bits required = 64 then 59/3 = your max bit range in the input, so 19 actually. I didn't think long double had a 64 bit mantissa, I thought it was 54. With 54 you get 49/3 = 16 bit range. That is why I said 16 before.

...

...
I just checked into the trunk today a couple changes that should make the library more reliable without the use of gmp. My version number for the checkin is 66403. The sandbox version is older than the 1.44 release. I stopped syncing the sandbox once I merged to the release branch and now do all development on the trunk. Included in this checkin were several fixes for resizing that didn't make it in time for the 1.45 release. If you plan to use resizing you should update.

...
Is this merely a mis-use of the API?

I would say yes, but only because you expected the library to be reliable without using gmp. Right now I can't provide that and make no promises about reliability if gmp is not used.

Fair enough.

Even if you stick to the 16 bit range I don't want to promise 100% robustness. I don't know why it might fail, but that doesn't mean it won't.

...

...
You mentioned a number of oddities but describe only one. What else have you run into?

We had hoped to use resizing, ran into the aforementioned problems, then ran into different ones after trying trunk. I believe they were related to using beveled corners, but I still need to reduce our problems to minimal cases.

I'm looking forward to seeing minimal cases. Beveled corners should work except for the snap rounding issues encountered when edges being convolved result in parallelograms narrower than the grid resolution. This error is bounded to the snapping distance, however. I'm eager to fix any bugs found both for a better 1.46 release and for our own use of the library. Thanks, Luke

Josh Pieper

8 Nov 8 Nov

11:14 a.m.

New subject: [polygon] Valgrind errors when normalizing any angle polygons

On Fri, Nov 5, 2010 at 3:44 PM, Simonson, Lucanus J wrote:

...

I'm looking forward to seeing minimal cases. Beveled corners should work except for the snap rounding issues encountered when edges being convolved result in parallelograms narrower than the grid resolution. This error is bounded to the snapping distance, however. I'm eager to fix any bugs found both for a better 1.46 release and for our own use of the library.

It looks like r66403 introduced an include dependency on "detail/minkowski.hpp", which didn't get checked in. Would you be able to check it in? Regards, Josh

Simonson, Lucanus J

5:07 p.m.

New subject: [polygon] Valgrind errors when normalizing any angle polygons

Josh Pieper wrote:

...

On Fri, Nov 5, 2010 at 3:44 PM, Simonson, Lucanus J wrote:

...
I'm looking forward to seeing minimal cases. Beveled corners should work except for the snap rounding issues encountered when edges being convolved result in parallelograms narrower than the grid resolution. This error is bounded to the snapping distance, however. I'm eager to fix any bugs found both for a better 1.46 release and for our own use of the library.

It looks like r66403 introduced an include dependency on "detail/minkowski.hpp", which didn't get checked in. Would you be able to check it in?

Done. Committed revision 66457. Thanks, Luke

5116

Age (days ago)

5120

Last active (days ago)

List overview

Download

5 comments

2 participants

participants (2)

Josh Pieper
Simonson, Lucanus J