Bug 15361 - [3.4/4.0 regression] bitset<>::_Find_next fails
[3.4/4.0 regression] bitset<>::_Find_next fails
Status: RESOLVED FIXED
Product: gcc
Classification: Unclassified
Component: libstdc++
3.4.0
: P2 normal
: 3.4.1
Assigned To: Paolo Carlini
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2004-05-10 02:04 UTC by Ivan Godard
Modified: 2004-09-13 14:15 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2004-05-13 16:14:36


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Ivan Godard 2004-05-10 02:04:21 UTC
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
Comment 1 Ivan Godard 2004-05-10 02:26:50 UTC
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
Comment 2 Benjamin Kosnik 2004-05-13 20:25:26 UTC
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
Comment 3 CVS Commits 2004-05-14 17:02:06 UTC
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

Comment 4 CVS Commits 2004-05-14 19:13:54 UTC
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

Comment 5 Paolo Carlini 2004-05-14 19:14:52 UTC
Fixed for 3.4.1 and 3.5.