|
|
Boost : |
From: Lester Gong (ljmgong_at_[hidden])
Date: 2004-02-02 19:34:22
There is a bug in dynamic_bitset operator<<=().
Calling operator<<=() followed by operator>>=() may shift in non-zero
bits from the left.
For example, this sequence of statements ...
dynamic_bitset<> b(std::string("0110");
b <<= 1; // gives "1100"
b <<= 1; // gives "1000"
b <<= 1; // gives "0000"
b >>= 1; // gives "1000" !!
b >>= 1; // gives "1100" !!
b >>= 1; // gives "0110"
Seems that some stray bits are not cleared when shifted beyond the lhs
of the bitfield.
Attached files:
test_dynamic_bitset.cc Simple program that illustrates bug
test_dynamic_bitset.out Output from simple test program
dynamic_bitset.hpp.patch Patch that seems to fix the bug
bitset_test.hpp.patch
dyn_bitset_unit_tests2.cpp.patch Proposed changes to test programs
that would catch this problem.
-Lester
#include <boost/dynamic_bitset.hpp>
#include <iostream>
#include <string>
using boost::dynamic_bitset;
using std::cout;
using std::endl;
int
main(int argv, char** argc)
{
dynamic_bitset<> b(std::string("0110"));
cout << "Original dynamic_bitset object:" << endl;
cout << b << endl << endl;
cout << "Shift left assignment (3 times):" << endl;
b <<= 1;
cout << b << endl;
b <<= 1;
cout << b << endl;
b <<= 1;
cout << b << endl << endl;
cout << "Shift right assignment (3 times):" << endl;
b >>= 1;
cout << b << endl;
b >>= 1;
cout << b << endl;
b >>= 1;
cout << b << endl;
return 0;
}
Original dynamic_bitset object:
0110
Shift left assignment (3 times):
1100
1000
0000
Shift right assignment (3 times):
1000
1100
0110
*** dynamic_bitset.hpp.orig Mon Feb 2 12:48:52 2004
--- dynamic_bitset.hpp Mon Feb 2 15:25:52 2004
***************
*** 670,676 ****
// div blocks are zero filled at the less significant end
std::fill(this->m_bits, this->m_bits+div, static_cast<block_type>(0));
!
}
--- 670,676 ----
// div blocks are zero filled at the less significant end
std::fill(this->m_bits, this->m_bits+div, static_cast<block_type>(0));
! m_zero_unused_bits();
}
*** bitset_test.hpp.orig Mon Feb 2 13:10:26 2004
--- bitset_test.hpp Mon Feb 2 15:21:34 2004
***************
*** 365,370 ****
--- 365,400 ----
BOOST_CHECK(lhs[I] == prev[I + pos]);
}
+ static void shift_left_assignment_followed_by_shift_right_assignment(const Bitset& b, std::size_t pos)
+ {
+ Bitset lhs(b);
+ Bitset prev(lhs);
+ lhs <<= pos;
+ lhs >>= pos;
+ // Check that zeros replace bits shifted off the end of the bitset.
+ std::size_t N = lhs.size();
+ for (std::size_t I = 0; I < N; ++I)
+ if (I < (N - pos))
+ BOOST_CHECK(lhs[I] == prev[I]);
+ else
+ BOOST_CHECK(lhs[I] == 0);
+ }
+
+ static void shift_right_assignment_followed_by_shift_left_assignment(const Bitset& b, std::size_t pos)
+ {
+ Bitset lhs(b);
+ Bitset prev(lhs);
+ lhs >>= pos;
+ lhs <<= pos;
+ // Check that zeros replace bits shifted off the end of the bitset.
+ std::size_t N = lhs.size();
+ for (std::size_t I = 0; I < N; ++I)
+ if (I >= pos)
+ BOOST_CHECK(lhs[I] == prev[I]);
+ else
+ BOOST_CHECK(lhs[I] == 0);
+ }
+
static void set_all(const Bitset& b)
{
*** dyn_bitset_unit_tests2.cpp.orig Mon Feb 2 13:10:44 2004
--- dyn_bitset_unit_tests2.cpp Mon Feb 2 15:28:26 2004
***************
*** 130,135 ****
--- 130,199 ----
Tests::shift_right_assignment(b, pos);
}
//=====================================================================
+ // Test operator<<= followed by operator>>=
+ { // case pos == 0
+ std::size_t pos = 0;
+ boost::dynamic_bitset<Block> b(std::string("1010"));
+ Tests::shift_left_assignment_followed_by_shift_right_assignment(b, pos);
+ }
+ { // case pos == 1
+ std::size_t pos = 1;
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_left_assignment_followed_by_shift_right_assignment(b, pos);
+ }
+ { // case pos == <half of Block>
+ std::size_t pos = (sizeof(Block) * CHAR_BIT) / 2;
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_left_assignment_followed_by_shift_right_assignment(b, pos);
+ }
+ { // case pos == <full Block>
+ std::size_t pos = sizeof(Block) * CHAR_BIT;
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_left_assignment_followed_by_shift_right_assignment(b, pos);
+ }
+ { // case pos == size()/2
+ std::size_t pos = long_string.size() / 2;
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_left_assignment_followed_by_shift_right_assignment(b, pos);
+ }
+ { // case pos >= n
+ std::size_t pos = long_string.size();
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_left_assignment_followed_by_shift_right_assignment(b, pos);
+ }
+ //=====================================================================
+ // Test operator>>= followed by operator<<=
+ { // case pos == 0
+ std::size_t pos = 0;
+ boost::dynamic_bitset<Block> b(std::string("1010"));
+ Tests::shift_right_assignment_followed_by_shift_left_assignment(b, pos);
+ }
+ { // case pos == 1
+ std::size_t pos = 1;
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_right_assignment_followed_by_shift_left_assignment(b, pos);
+ }
+ { // case pos == <half of Block>
+ std::size_t pos = (sizeof(Block) * CHAR_BIT) / 2;
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_right_assignment_followed_by_shift_left_assignment(b, pos);
+ }
+ { // case pos == <full Block>
+ std::size_t pos = sizeof(Block) * CHAR_BIT;
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_right_assignment_followed_by_shift_left_assignment(b, pos);
+ }
+ { // case pos == size()/2
+ std::size_t pos = long_string.size() / 2;
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_right_assignment_followed_by_shift_left_assignment(b, pos);
+ }
+ { // case pos >= n
+ std::size_t pos = long_string.size();
+ boost::dynamic_bitset<Block> b(long_string);
+ Tests::shift_right_assignment_followed_by_shift_left_assignment(b, pos);
+ }
+ //=====================================================================
// test b.set()
{
boost::dynamic_bitset<Block> b;
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk