[geos-devel] Re: [GEOS] #202: Undefined behavior in Coordinate::hashCode
#202: Undefined behavior in Coordinate::hashCode +--- Reporter: mloskot |Owner: geos-devel@lists.osgeo.org Type: defect | Status: new Priority: major |Milestone: Component: Core| Version: svn-trunk Severity: Significant | Resolution: Keywords: coordinate hash double | +--- Comment (by bmharper): Thanks Mateusz! I wasn't aware of these issues. -- Ticket URL: http://trac.osgeo.org/geos/ticket/202#comment:4 GEOS http://geos.refractions.net/ GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).___ geos-devel mailing list geos-devel@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/geos-devel
[geos-devel] Re: [GEOS] #202: Undefined behavior in Coordinate::hashCode
#202: Undefined behavior in Coordinate::hashCode
+---
Reporter: mloskot |Owner: geos-devel@lists.osgeo.org
Type: defect | Status: new
Priority: major |Milestone:
Component: Core| Version: svn-trunk
Severity: Significant | Resolution:
Keywords: coordinate hash double |
+---
Comment (by bmharper):
Mateusz - you mentioned that this violates aliasing rules:
unsigned int HashDouble( double d )
{
unsigned int* i = (unsigned int*) d;
return i[0] ^ i[1];
}
Can you explain further, or point me to the relevant C/++ docs?
Thanks,
Ben
ps-- Your code references x. Should this not be d?
--
Ticket URL: http://trac.osgeo.org/geos/ticket/202#comment:1
GEOS http://geos.refractions.net/
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite
(JTS).___
geos-devel mailing list
geos-devel@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/geos-devel
[geos-devel] Re: [GEOS] #202: Undefined behavior in Coordinate::hashCode
#202: Undefined behavior in Coordinate::hashCode
+---
Reporter: mloskot |Owner: geos-devel@lists.osgeo.org
Type: defect | Status: new
Priority: major |Milestone:
Component: Core| Version: svn-trunk
Severity: Significant | Resolution:
Keywords: coordinate hash double |
+---
Old description:
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^(f32)); // --- 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 '''f32''', 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, x, sizeof(double));
return (arr[0] ^ (((arr[1] 16) 0x00FF)
| ((arr[1] 8) 0xFF00)
| ((arr[1] 8) 0x00FF)
| ((arr[1] 16) 0xFF00)));
}
}}}
New description:
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^(f32)); // --- 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 '''f32''', 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) 0x00FF)
| ((arr[1] 8) 0xFF00)
| ((arr[1] 8) 0x00FF)
| ((arr[1] 16) 0xFF00)));
}
}}}
--
Ticket URL: http://trac.osgeo.org/geos/ticket/202#comment:2
GEOS http://geos.refractions.net/
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite
(JTS).___
geos-devel mailing list
geos-devel@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/geos-devel
[geos-devel] Re: [GEOS] #202: Undefined behavior in Coordinate::hashCode
#202: Undefined behavior in Coordinate::hashCode +--- Reporter: mloskot |Owner: geos-devel@lists.osgeo.org Type: defect | Status: new Priority: major |Milestone: Component: Core| Version: svn-trunk Severity: Significant | Resolution: Keywords: coordinate hash double | +--- Comment (by mloskot): 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 ([http://www.ice.gelato.org/oct07/pres_pdf/gelato_ICE07oct_aliasing_isaev_intel.pdf PDF]) If standards are too heavy, then Wikipedia is handy, see [http://en.wikipedia.org/wiki/Type_punning#Floating-point_example 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 [http://trac.osgeo.org/gdal/ticket/2521 my story of finding root of a very strange bug] in GDAL that took me hours :-) -- Ticket URL: http://trac.osgeo.org/geos/ticket/202#comment:3 GEOS http://geos.refractions.net/ GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).___ geos-devel mailing list geos-devel@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/geos-devel
