#202 closed defect (invalid)
Undefined behavior in Coordinate::hashCode
Reported by: | mloskot | Owned by: | mloskot |
---|---|---|---|
Priority: | major | Milestone: | 3.2.0 |
Component: | Core | Version: | main |
Severity: | Significant | Keywords: | coordinate hash double |
Cc: |
Description (last modified by )
If ./configure fails to detect availability of 64-bit integer, it sets int64 typedef to long int (in file platform.h).
In this case, when in64 is 32-bit wide, undefined behavior occurs in Coordiante::hashDouble() function:
unsigned int Coordinate::hashCode(double d) { int64 f = (int64)(d); return (int)(f^(f>>32)); // <--- UB }
According to the standards C (section 6.5.7/3) and C++ (section 5.8/1):
The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.
This error occur in f>>32, when sizeof(f) == 32.
Simple but not ideal fix could be:
#include <cstring> // std::memcpy int Coordinate::hashDouble(double d) { unsigned int arr[2] = { 0 }; std::memcpy(arr, &d, sizeof(double)); return (arr[0] ^ (((arr[1] >> 16) & 0x000000FF) | ((arr[1] >> 8) & 0x0000FF00) | ((arr[1] << 8) & 0x00FF0000) | ((arr[1] << 16) & 0xFF000000))); }
Change History (13)
comment:1 by , 16 years ago
comment:2 by , 16 years ago
Description: | modified (diff) |
---|
comment:3 by , 16 years ago
Ben,
The doc is C++ ISO/IEC 14882:2003 (6.10 lvalues and rvalues, paragraph 15). Also, chapter 6.5 and paragraph 7 of ISO 9899:1999 defines aliasing rules for C language.
Shortly, the rule is as simple as:
Pointers of different types (say int* and float*) can’t point to the same object
It was very well explained in presentation by Andrey Bokhanko and Alexander Isaev from Intel Labs (PDF)
If standards are too heavy, then Wikipedia is handy, see Type punning article and floating-point example based on your suggestion and commented this way:
this kind of type punning is more dangerous than most
Just to give an example of how dangerous this kind of hack can be, here is my story of finding root of a very strange bug in GDAL that took me hours :-)
comment:5 by , 15 years ago
Milestone: | → 3.1.0 |
---|
comment:6 by , 15 years ago
Owner: | changed from | to
---|
comment:7 by , 15 years ago
It doesn't look like hashCode is even used, unless it's a magical method that gets called implicitly by some other operation? Envelope::hashCode uses the double hashcode, but the envelope method seems unused.
comment:8 by , 15 years ago
Milestone: | 3.1.0 → 3.2.0 |
---|
Defering to 3.2 or when someone finds a use case that exercises this.
comment:9 by , 15 years ago
I think there'd be much more troubles if int64 isn't available. See precision/CommonBits.h or index/quadtree/DoubleBits.h, both used (haschCode isn't).
We might bail out on configure if 64bit integers aren't supported by the platform. Mat: do you actually have a system failing that ?
comment:11 by , 15 years ago
Resolution: | → invalid |
---|---|
Status: | new → closed |
I've had ./configure print a WARNING about undefined behaviour when 64bit integer type isn't found. See r2558.
follow-up: 13 comment:12 by , 13 years ago
Hello,
Is there a way to compile GEOS using cross-mingw32? It has been a while and I would like to know if there has been advancements in this area...
TIA.
comment:13 by , 13 years ago
Replying to jurien:
Hello,
Is there a way to compile GEOS using cross-mingw32? It has been a while and I would like to know if there has been advancements in this area...
TIA.
Sorry... I belive I posted a rather off-topic comment. I get this warning when trying to cross compile geos, and I would like to know if there have been made advancements as the one proposed on the TCK description or everything was left to rely on the warning. If it's the later, what can I expect from a compilation that issued this warning?
TIA.
Mateusz - you mentioned that this violates aliasing rules:
unsigned int HashDouble( double d ) {
}
Can you explain further, or point me to the relevant C/++ docs?
Thanks, Ben
ps-- Your code references &x. Should this not be &d?