Archive

Posts Tagged ‘win32’

Hash Overflow due to 64 bit upcasting

October 28th, 2011 No comments
    Lately, I had to debug the following piece of code, where it caused overflow on the hash bucket design.  The code worked perfectly on a Windows machine while compiled for Win32, but failed to work on a Linux Mint x64 machine.  The code is listed below, which basically calculates hash value of an input 32 bit unsigned number, limiting the hash value to 2^10 (1Meg).

hash = ( fpArray*2654404609 )>>12; // Calculate the hash and limit the value to 2^20 (1 Meg)

   When the input value for fpArray was 1724463449 (0x66C93959), the hash value generated was 1779068547 (0x6A0A6E83), which is more than (0x000FFFFF) to cause the hash bucket overflow.

unsigned hash = fpArray * 2654404609;
hash = hash >> 12;

    When I rewrote the code like the above, the value of hash was 2800236889 (0xA6E83959).  Upon shifting right by 12 yields 638651 (0x0009BEBB), which is the correct and expected hash value.

    Overall, the first snippet of code appears to be correct.  Do you see a problem there?  I couldn’t find the issue, until I recalled the 32bit vs 64bit difference.  If you carefully look at the multiplier 2654404609 (0x9E370001), although appears to be a valid 32 bit number, what is the default assignment of type to this number by the compiler?  If it was assigned 64bits, what would happen to the results?  To validate this, I changed the 2nd snippet as the following.

unsigned long hash = (unsigned long)fpArray * 2654404609;
hash = hash >> 12;
unsigned h2 = (unsigned)hash;

    Now, when the input is the same 1724463449 (0x66C93959), the value of hash becomes 4577423727077636441 (0x3F8646A0A6E83959) and upon right shifting by 12 bits yields 1117535089618563 (0x0003F8646A0A6E83). Followed by downcasting to unsigned yield 1779068547 (0x6A0A6E83). Bingo!

    So, what is happening here? While performing (fpArray * 2654404609), the computation is upcasted to 64bit computation by the 64 bit compiler.  So, what is the solution? Just put a “U” at the end of the constant.

hash = ( fpArray*2654404609U )>>12; // Calculate the hash and limit the value to 2^20 (1 Meg)
(or)
const unsigned multipler = 2654404609; // here U suffix is not needed as the constant is explicitly made unsigned
hash = ( fpArray * multiplier ) >> 12;

    Now, the computation will happen with 32 bit numbers to get the expected outputs.

Lessons Learned here:

  1. While using constants, beware of the upcasting and downcasting. So use proper suffixes like U, L, F etc.
  2. Instead of using constants directly in expressions, use them as constant variables.
  3. Be conscious about the compiler type and the assumptions made by the compiler in different build modes.
Tags: , , , , , , , , , , , , , , ,

ACE 5.6.7 does not compile with STLport in Win32 environment

June 14th, 2010 No comments

ACE 5.6.7 does not compile with STLport in Windows environment (I used vc9 on Windows Server 2008) because of the following header in ACE (ACE_wrappers/ace/checked_iterator.h), which wrongly assumes the existence of stdext::checked_array_iterator in the iterator header.  A PRF is already submitted in the ACE mailing list (http://www.archivum.info/comp.soft-sys.ace/2008-07/00026/%5Bace-users%5D-Checked_iterator.h-problem-with-STLport..html)

# if defined (_MSC_VER) && (_MSC_FULL_VER >= 140050000)
// Checked iterators are currently only supported in MSVC++ 8 or better.
#  include <iterator>
# endif  /* _MSC_VER >= 1400 */

# if defined (_MSC_VER) && (_MSC_FULL_VER >= 140050000)
template <typename PTR>
stdext::checked_array_iterator<PTR>
ACE_make_checked_array_iterator (PTR buf, size_t len)
{
return stdext::checked_array_iterator (buf, len);
}
# else
template <typename PTR>
PTR
ACE_make_checked_array_iterator (PTR buf, size_t /* len */)
{
// Checked iterators are unsupported.  Just return the pointer to
// the buffer itself.
return buf;
}
# endif  /* _MSC_VER >= 1400 */

#endif  /* ACE_CHECKED_ITERATOR_H */

I need to develop a solution to it.  The easiest way to find a solution is to use some macro explicitly set by the STLport header, which is not set by any other STL libraries.  I chose to use the _STLP_ITERATOR macro set by “stl/stlport/iterator” header.

#ifndef _STLP_ITERATOR
#define _STLP_ITERATOR

# ifndef _STLP_OUTERMOST_HEADER_ID
#  define _STLP_OUTERMOST_HEADER_ID 0×38
#  include <stl/_prolog.h>
# endif

# ifdef _STLP_PRAGMA_ONCE
#  pragma once
# endif

#if defined (_STLP_IMPORT_VENDOR_STD)
# include _STLP_NATIVE_HEADER(iterator)
#endif /* IMPORT */

# ifndef _STLP_INTERNAL_ITERATOR_H
#  include <stl/_iterator.h>
# endif

# ifndef _STLP_INTERNAL_STREAM_ITERATOR_H
#  include <stl/_stream_iterator.h>
# endif

# if (_STLP_OUTERMOST_HEADER_ID == 0×38)
#  include <stl/_epilog.h>
#  undef _STLP_OUTERMOST_HEADER_ID
# endif

#endif /* _STLP_ITERATOR */

The solution is the following, where I have added the !defined(_STLP_ITERATOR) condition along with the check for Visual Studio compiler version.

# if !defined(_STLP_ITERATOR) && defined (_MSC_VER) && (_MSC_FULL_VER >= 140050000)
// Checked iterators are currently only supported in MSVC++ 8 or better.
#  include <iterator>
# endif  /* _MSC_VER >= 1400 */

# if defined (_MSC_VER) && (_MSC_FULL_VER >= 140050000)
template <typename PTR>
stdext::checked_array_iterator <PTR>
ACE_make_checked_array_iterator (PTR buf, size_t len)
{
return stdext::checked_array_iterator (buf, len);
}
# else
template <typename PTR>
PTR
ACE_make_checked_array_iterator (PTR buf, size_t /* len */)
{
// Checked iterators are unsupported. Just return the pointer to
// the buffer itself.
return buf;
}
#
endif  /* _MSC_VER >= 1400 */

#endif
/* ACE_CHECKED_ITERATOR_H */

Tags: , , , , , , , , , , ,

Get MAC address using C++

July 4th, 2009 No comments

There is a Simple way to capture the MAC address of the machine in Win32 environment. In Win32, UUID (version 1) uses MAC address & timestamp as the seeds for generating the UUID.  In the UUID string, the last 6 bytes are the MAC address of the machine.  UuidCreateSequential() is the Win32 API which is used to capture the MAC address via the UUID generated by it.

#include <rpc.h>      // for UUID, UuidCreateSequential
#include <cstring>    // for memcpy
#include <algorithm>  // for std::swap

unsigned __int64
MACAddress( void ) const
{
    UUID u;
    ::UuidCreateSequential( &u );

    u.Data4[0] = u.Data4[1] = 0;

    std::swap( u.Data4[0], u.Data4[7] );
    std::swap( u.Data4[1], u.Data4[6] );
    std::swap( u.Data4[2], u.Data4[5] );
    std::swap( u.Data4[3], u.Data4[4] );

    unsigned __int64 code;
    ::memcpy( &code, &u.Data4, sizeof(u.Data4) );

    return code;
}   // MACAddress

Let me share another hack. If you want to generate strings which do not repeat themselves, you could use UuidCreate() Win32 API, which generates unique UUIDs everytime the function is called.  The UUID thus obtained can be converted to a number or a string depending upon the need, which guarantees non-repeatable ids.

Tags: , , , , , ,