[Bug libstdc++/15361] New: bitset<>::_Find_next fails

[Bug libstdc++/15361] New: bitset<>::_Find_next fails

[igodard at pacbell dot net]

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

-- 
           Summary: bitset<>::_Find_next fails
           Product: gcc
           Version: 3.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: igodard at pacbell dot net
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15361

[Bug libstdc++/15361] bitset<>::_Find_next fails

[igodard at pacbell dot net]

------- Additional Comments From igodard at pacbell dot net  2004-05-10 02:26 -------
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

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15361

[Bug libstdc++/15361] bitset<>::_Find_next fails

[pcarlini at suse dot de]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-05-13 16:14:36
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15361

[Bug libstdc++/15361] bitset<>::_Find_next fails

[bkoz at gcc dot gnu dot org]

------- Additional Comments From bkoz at gcc dot gnu dot org  2004-05-13 20:25 -------

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

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15361

[Bug libstdc++/15361] [3.4/3.5 regression] bitset<>::_Find_next fails

[pcarlini at suse dot de]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |3.4.1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15361

[Bug libstdc++/15361] [3.4/3.5 regression] bitset<>::_Find_next fails

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2004-05-14 17:02 -------
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



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15361

[Bug libstdc++/15361] [3.4/3.5 regression] bitset<>::_Find_next fails

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2004-05-14 19:13 -------
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



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15361

[Bug libstdc++/15361] [3.4/3.5 regression] bitset<>::_Find_next fails

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2004-05-14 19:14 -------
Fixed for 3.4.1 and 3.5.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15361