Archive

Posts Tagged ‘Programming’

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.

no include path in which to search for limits.h

June 16th, 2011 No comments

Why compiling STLport 5.1.5 using g++-4.4, one might get an error like the following:-

Building CXX object libs/bgt/CMakeFiles/bgt.dir/error.o
In file included from /opt/projects/stl/stlport/limits.h:27,
            from /usr/include/c++/4.4/../4.4.5/climits:43,
            from /opt/projects/stl/stlport/climits:27,
            from /opt/projects/stl/stlport/stl/_algobase.h:42,
            from /opt/projects/stl/stlport/stl/_alloc.h:47,
            from /opt/projects/stl/stlport/stl/_string.h:23,
            from /opt/projects/stl/stlport/stl/_ios_base.h:34,
            from /opt/projects/stl/stlport/stl/_ios.h:23,
            from /opt/projects/stl/stlport/stl/_ostream.h:24,
            from /opt/projects/stl/stlport/ostream:31,
            from /opt/projects/dev/libs/bgt/error.cpp:18:
/usr/include/../include/limits.h:125: error: no include path in which to search for limits.h
In file included from /opt/projects/stl/stlport/stl/_num_put.c:26,
            from /opt/projects/stl/stlport/stl/_num_put.h:183,
            from /opt/projects/stl/stlport/stl/_ostream.c:26,
            from /opt/projects/stl/stlport/stl/_ostream.h:380,
            from /opt/projects/stl/stlport/ostream:31,
            from /opt/projects/dev/libs/bgt/error.cpp:18:
/opt/projects/stl/stlport/stl/_limits.h:148: error: ‘CHAR_BIT’ was not declared in this scope
/opt/projects/stl/stlport/stl/_limits.h:253: error: ‘CHAR_MIN’ was not declared in this scope
..

Looks like it is a bug in the STLport package itself as per the Release notes of STLport.  After updating to STLport-5.2.1, the issue got fixed automatically.

Converting KDevelop3 project to KDevelop4

June 15th, 2011 1 comment
    KDevelop4 has adopted CMake build system over AutoMake build system of KDevelop3. So, projects that are hosted on KDevelop3 environment cannot work seamlessly on KDevelop4 environment, which makes is practically impossible to migrate to KDevelop4 which is far superior in terms of functionality and usability.  Moreover, all latest Ubuntu flavors (Linux Mint 10 x64) give KDevelop4 as the default IDE under KDE.

    CMake is more powerful build system than Automake.  A very nice comparison of CMake and Autotools is found here.  The reason for KDevelop moving over to CMake is described in this article.  CMake also provides some scripts that help one to migrate the KDevelop3 projects to KDevelop4 CMake projects.  Once such script is am2cmake, which is written in Ruby.  If you run this script from the root directory of the KDevelop3 projects folder, the ruby script automatically reads Makefile.am and traverses through the directory to convert Makefile.am to CMakeLists.txt.  But there is a small bug in that.  While running the script on StaticLib directory, one might get the following error message:

converting Makefile.am
Makefile.am PROBLEM: target not found:  libanalyzer_server_a_SOURCES = Admin.cpp Admin.hpp AnalyzerC.cpp AnalyzerC.h     AnalyzerS.cpp AnalyzerS.h CmdInfo.cpp CmdInfo.hpp Config.cpp Config.hpp     Manager.cpp Manager.hpp ModelTask.cpp ModelTask.hpp

The original Makefile.am that was converted is:

INCLUDES = -I$(top_srcdir)/config -I$(top_srcdir)/idls -I$(top_srcdir)/libs \
    -I$(top_srcdir)/libs/bgtLicensing -I$(top_srcdir)/libs/hmm -I$(STL_ROOT)/stlport -I$(DEV_ROOT)/idls/src \
    -I$(TAO_ROOT)/orbsvcs/orbsvcs -I$(TAO_ROOT)/orbsvcs -I$(TAO_ROOT) -I$(ACE_ROOT)
METASOURCES = AUTO
AM_CFLAGS = -Wall -pthread -D_Linux_ -D__STL_CLASS_PARTIAL_SPECIALIZATION -m64
AM_CXXFLAGS = -Wall -pthread -D_Linux_ -D__STL_CLASS_PARTIAL_SPECIALIZATION -m64
lib_LIBRARIES = libanalyzer_server.a
libanalyzer_server_a_SOURCES = Admin.cpp Admin.hpp AnalyzerC.cpp AnalyzerC.h\
    AnalyzerS.cpp AnalyzerS.h CmdInfo.cpp CmdInfo.hpp Config.cpp Config.hpp\
    Manager.cpp Manager.hpp ModelTask.cpp ModelTask.hpp

Basically, while translating the Makefiles for static libs, am2cmake script does not know how to extract the target name from the Makefile.  By applying the below patch the problem was fixed.  Basically, a rule is added to addTarget function to handle lib_LIBRARIES = line from Makefile.am

336a337,339
>       elsif line =~ /^\s*lib_LIBRARIES\s*=\s*(\S+.*)/
>          targets=$1
>          type=StaticLib

[Updated 04/07/2011: A more or less completed script is available here for converting non KDE projects, which should transform all the projects from kdev3  (native c++ projects that are non-kde) to CMakeLists.txt format. Use ruby am2cmake.rb –no-kde to run the script.]

OOPS: Delayed Instantiation

March 17th, 2011 No comments

பலன் கருதி பொருள் ஈட்டல்
நலம் பேணும் நன்முறையாம்
பொருள் சேர்க்கும் நன்மக்கள்
காலத்தே ஈட்டி பலம் கொள்வாரே!

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 0x38
#  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 == 0x38)
#  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 */

FFTW library under Windows Mobile 6 Standard SDK

September 15th, 2008 No comments

FFT (Fast Fourier Transform) is a technique by which one can perform 1D and 2D transforms on discrete data. Typically Discrete Fourier Transform is the primary application of FFT. One implementation of FFT is available at www.fftw.org. FFTW is currently available for multiple platforms including Windows and Linux.

I was looking for a framework to run FFT operation on a Windows Mobile 6 platform in native C++. Unfortunately, there are none. So, I decided to port the framework myself and indeed I was successful too. I have placed the framework at www.sudarsun.in/downloads/FFTW-3.0.1-ARMV4I.zip. It does not contain any documentation. I shall update it ASAP.