Re: [boost] [dynamic_bitset] bug in to_ulong() in dynamic_bitset.hpp

From: Gennaro Prota (gennaro.prota_at_[hidden])
Date: 2008-07-05 13:46:08

{I'm reposting this (with slight changes); the original version 
doesn't seem to have made it in the moderation queue}

Boris Gubenko wrote:
>   A failure of dynamic_bitset library test dyn_bitset_unit_tests3
>   on Tru64/cxx and HP-UX/aCC revealed what appears to be a bug in
>   <boost/dynamic_bitset/dynamic_bitset.hpp> introduced after
>   Boost 1.34.

Sigh... it was introduced in the passage from rev. 1.10 to rev. 1.11
(see
<http://boost.cvs.sourceforge.net/boost/boost/boost/dynamic_bitset/dynamic_bitset.hpp>).

>   The bug affects platforms where 'long' type is larger than 'int'.
>   On both Tru64 and HP-UX, 'int' is a 32-bit type. On Tru64, 'long'
>   is a 64-bit type. On HP-UX, 'long' is a 64-bit type in 64-bit data
>   model (+DD64, which is how Boost testing is done on this platform)
>   and 32-bit type otherwise.
> 
>   The test also fails on other platforms and while I cannot verify it,
>   from the test output it apears that these platforms are affected by
>   the same bug.
> 
>   What fails is the two testcases below in b.to_long() suite in
>   boost/libs/dynamic_bitset/dyn_bitset_unit_tests3.cpp invoked with
>   run_test_cases<unsigned int>() :
> 
>   {
>     std::string str(ul_width - 1, '1');
>     boost::dynamic_bitset<Block> b(str);
>     Tests::to_ulong(b);
>   }
>   {
>     std::string ul_str(ul_width, '1');
>     boost::dynamic_bitset<Block> b(ul_str);
>     Tests::to_ulong(b);
>   }
> 
>   The code in <boost/libs/dynamic_bitset/bitset_test.hpp> converts
>   dynamic_bitset<unsigned int> argument to unsigned long and checks
>   that the appropriate bits in the result are set:
> 
>       result_type num = lhs.to_ulong();
>       // Be sure the number is right
>       if (sz == 0)
>         BOOST_CHECK(num == 0);
>       else {
>         for (std::size_t i = 0; i < sz; ++i)
>           BOOST_CHECK(lhs[i] == (i < n ? nth_bit(num, i) : 0));
>       }
> 
>   This check fails for the bits in the upper half of the result.
> 
>   Here is an excerpt from dynamic_bitset<Block, Allocator>::to_ulong()
>   function in <boost/dynamic_bitset/dynamic_bitset.hpp> in the trunk:
> 
>   result_type result = 0;
>   for (size_type i = 0; i <= last_block; ++i) {
>     assert((size_type)bits_per_block * i < (size_type)ulong_width);
>     result |= (m_bits[i] << (bits_per_block * i));
>   }
> 
>   In our case, last_block = 1 and bits_per_block = 32. m_bits[i] has
>   'unsigned int' type.
> 
>   On the second loop iteration, a 32-bit integer is left-shifted by 32 bit
>   positions. This triggers undefined behaviour. From 5.8 - Shift operators
>   [expr.shift] : "The behavior is undefined if the right operand is [...]
>   greater than or equal to the length in bits of the promoted left
>   operand." With cxx and aCC, such shift results in zeroing of all bits
>   of the left operand.

Yeah. I'm well aware of this; you can see e.g. that operator <<= and 
operator >>= have comments, aimed at maintainers, whose purpose is 
exactly to prevent the introduction of such undefined behavior. And 
even in the code above, the intent of the assert was to check that I 
wouldn't incur in that error; but, the issue is, the assert assumes 
I'll shift an unsigned long, which I'm not doing (except when Block 
happens to be unsigned long). Of course using an intermediate unsigned 
long variable ('piece') does the trick, as would a static_cast<> of 
m_bits[i].

>   Here is the code from <boost/dynamic_bitset/dynamic_bitset.hpp> in Boost
>   1.34 :
> 
>   unsigned long result = 0;
>   for (size_type i = 0; i <= last_block; ++i) {
>     assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps
>     unsigned long piece = m_bits[i];
>     result |= (piece << (bits_per_block * i));
>   }
> 
>   Here on the second loop iteration, a 64-bit long is left-shifted by 32
>   bit positions which yields the intended result.

Yes.

[...]

>   To fix the problem, I suggest to replace the buggy code in
>   <boost/dynamic_bitset/dynamic_bitset.hpp> in the trunk with that
>   in 1.34. If there are no objections, I can do it.

Yes, but please use the "result_type" typedef (or drop it altogether,
if you prefer that).

Thanks for looking into this,

-- 
      \|||/                Gennaro Prota   -   For hire
      (o o)           https://sourceforge.net/projects/breeze/
--ooO-(_)-Ooo-----