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

["igodard at pacbell dot net" <gcc-bugzilla at gcc dot gnu dot org>]

------- 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