[geos-devel] Re: [GEOS] #202: Undefined behavior in Coordinate::hashCode

[GEOS]

#202: Undefined behavior in Coordinate::hashCode
------------------------------------+---------------------------------------
 Reporter:  mloskot                 |        Owner:  geos-devel at 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^(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, &x, sizeof(double));
>    return (arr[0] ^ (((arr[1] >> 16) & 0x000000FF)
>            | ((arr[1] >> 8) & 0x0000FF00)
>            | ((arr[1] << 8) & 0x00FF0000)
>            | ((arr[1] << 16) & 0xFF000000)));
> }
> }}}

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^(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)));
 }
 }}}

-- 
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).