| Summary: | [3.4/4.0 regression] bitset<>::_Find_next fails | ||
|---|---|---|---|
| Product: | gcc | Reporter: | Ivan Godard <igodard> |
| Component: | libstdc++ | Assignee: | Paolo Carlini <paolo.carlini> |
| Status: | RESOLVED FIXED | ||
| Severity: | normal | CC: | gcc-bugs |
| Priority: | P2 | ||
| Version: | 3.4.0 | ||
| Target Milestone: | 3.4.1 | ||
| Host: | Target: | ||
| Build: | Known to work: | ||
| Known to fail: | Last reconfirmed: | 2004-05-13 16:14:36 | |
There seem to be three distinct bugs in this library. Here's the relevant code:
template<size_t _Nw>
size_t
_Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
{
// make bound inclusive
++__prev;
// check out of bounds
if ( __prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD )
return __not_found;
// search first word
size_t __i = _S_whichword(__prev);
_WordT __thisword = _M_w[__i];
// mask off bits below bound
__thisword >>= __prev + 1;
if (__thisword != static_cast<_WordT>(0))
return __i * _GLIBCXX_BITSET_BITS_PER_WORD
+ __builtin_ctzl(__thisword);
1) The function increments prev to get the starting point for the search, but then shifts __thisword by prev + 1. So if (for example) prev was 31 (i.e. that last bit in the first word) the increment would make it 32 and the shiftcount would be 33, which after hardware truncation would be 1. Consequently the first bit in the following word is discarded and will not be reported even if set.
2) The function uses a shift count which is in general larger than the number of bits in a word. This works on some machines (shift count is truncated), will produce an illop exception on others, and will produce zero (or all ones for arithmetic shift) on still others. The code won't port.
3) After the shift the code calls __builtin_ctzl(__thisword); to get the bit number. I assume that this uses a hardware FindFirstOne operation to get the bit number of the leading bit. However, the value returned is just the sum of that bit number and the word index, which ignores the amount of the shift.
All three bugs can be fixed if the line:
__thisword >>= __prev + 1;
is replaced by:
int __shiftcount = __prev & 0x1f; // assumes table is in 32-bit words
// CONFIRM THIS IS ALWAYS TRUE
__thisword = __thisword >> __shiftcount << __shiftcount;
Ivan
Fixing this should be easy enough, so we might as well keep these extensions, I think. Make sure this testcase gets dropped in the testsuite! The bitset coverage is pretty weak. -benjamin Subject: Bug 15361 CVSROOT: /cvs/gcc Module name: gcc Changes by: paolo@gcc.gnu.org 2004-05-14 17:01:50 Modified files: libstdc++-v3 : ChangeLog libstdc++-v3/include/std: std_bitset.h Added files: libstdc++-v3/testsuite/23_containers/bitset/ext: 15361.cc Log message: 2004-05-14 Paolo Carlini <pcarlini@suse.de> Ivan Godard <igodard@pacbell.net> PR libstdc++/15361 * include/std/std_bitset.h (_Base_bitset<_Nw>::_M_do_find_next): Fix. * testsuite/23_containers/bitset/ext/15361.cc: New. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/ChangeLog.diff?cvsroot=gcc&r1=1.2474&r2=1.2475 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/std/std_bitset.h.diff?cvsroot=gcc&r1=1.23&r2=1.24 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/23_containers/bitset/ext/15361.cc.diff?cvsroot=gcc&r1=NONE&r2=1.1 Subject: Bug 15361 CVSROOT: /cvs/gcc Module name: gcc Branch: gcc-3_4-branch Changes by: paolo@gcc.gnu.org 2004-05-14 19:13:47 Modified files: libstdc++-v3 : ChangeLog libstdc++-v3/include/std: std_bitset.h Added files: libstdc++-v3/testsuite/23_containers/bitset/ext: 15361.cc Log message: 2004-05-14 Paolo Carlini <pcarlini@suse.de> Ivan Godard <igodard@pacbell.net> PR libstdc++/15361 * include/std/std_bitset.h (_Base_bitset<_Nw>::_M_do_find_next): Fix. * testsuite/23_containers/bitset/ext/15361.cc: New. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-3_4-branch&r1=1.2224.2.100&r2=1.2224.2.101 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/std/std_bitset.h.diff?cvsroot=gcc&only_with_tag=gcc-3_4-branch&r1=1.21.4.2&r2=1.21.4.3 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/23_containers/bitset/ext/15361.cc.diff?cvsroot=gcc&only_with_tag=gcc-3_4-branch&r1=NONE&r2=1.1.2.1 Fixed for 3.4.1 and 3.5. |
The code: #include <bitset> #include <iostream> using namespace std; int main() { bitset<256> b; b.set(225); b.set(226); cout << b.count() << ":" << b._Find_first() << ":" << b._Find_next(225) << ":" << b.test(225) << ":" << b.test(226) << ":" << b.test(227) << endl; return 0; } produces: ~/ootbc/common/test/src$ a.out 2:225:256:1:1:0 That is, the bitset correctly has two members, and they are correctly 225 and 226, but _Find_next(225) returns end-of-set (256) rather than the next value (226) Ivan