- Boost - lists.boost.org

[dynamic_bitset] bug in to_ulong() in dynamic_bitset.hpp
by Boris Gubenko 05 Jul '08

05 Jul '08

A failure of dynamic_bitset library test dyn_bitset_unit_tests3 on Tru64/cxx and HP-UX/aCC revealed what appears to be a bug in <boost/dynamic_bitset/dynamic_bitset.hpp> introduced after Boost 1.34. The bug affects platforms where 'long' type is larger than 'int'. On both Tru64 and HP-UX, 'int' is a 32-bit type. On Tru64, 'long' is a 64-bit type. On HP-UX, 'long' is a 64-bit type in 64-bit data model (+DD64, which is how Boost testing is done on this platform) and 32-bit type otherwise. The test also fails on other platforms and while I cannot verify it, from the test output it apears that these platforms are affected by the same bug. What fails is the two testcases below in b.to_long() suite in boost/libs/dynamic_bitset/dyn_bitset_unit_tests3.cpp invoked with run_test_cases<unsigned int>() : { std::string str(ul_width - 1, '1'); boost::dynamic_bitset<Block> b(str); Tests::to_ulong(b); } { std::string ul_str(ul_width, '1'); boost::dynamic_bitset<Block> b(ul_str); Tests::to_ulong(b); } The code in <boost/libs/dynamic_bitset/bitset_test.hpp> converts dynamic_bitset<unsigned int> argument to unsigned long and checks that the appropriate bits in the result are set: result_type num = lhs.to_ulong(); // Be sure the number is right if (sz == 0) BOOST_CHECK(num == 0); else { for (std::size_t i = 0; i < sz; ++i) BOOST_CHECK(lhs[i] == (i < n ? nth_bit(num, i) : 0)); } This check fails for the bits in the upper half of the result. Here is an excerpt from dynamic_bitset<Block, Allocator>::to_ulong() function in <boost/dynamic_bitset/dynamic_bitset.hpp> in the trunk: result_type result = 0; for (size_type i = 0; i <= last_block; ++i) { assert((size_type)bits_per_block * i < (size_type)ulong_width); result |= (m_bits[i] << (bits_per_block * i)); } In our case, last_block = 1 and bits_per_block = 32. m_bits[i] has 'unsigned int' type. On the second loop iteration, a 32-bit integer is left-shifted by 32 bit positions. This triggers undefined behaviour. From 5.8 - Shift operators [expr.shift] : "The behavior is undefined if the right operand is [...] greater than or equal to the length in bits of the promoted left operand." With cxx and aCC, such shift results in zeroing of all bits of the left operand. Here is the code from <boost/dynamic_bitset/dynamic_bitset.hpp> in Boost 1.34 : unsigned long result = 0; for (size_type i = 0; i <= last_block; ++i) { assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps unsigned long piece = m_bits[i]; result |= (piece << (bits_per_block * i)); } Here on the second loop iteration, a 64-bit long is left-shifted by 32 bit positions which yields the intended result. x.cpp below illustrates the difference between trunk and Boost 1.34: x.cpp ----- #include <stdio.h> #include <limits.h> int main() { unsigned int m_bits[] = { UINT_MAX, UINT_MAX }; unsigned int bits_per_block = sizeof(int) * CHAR_BIT; unsigned long result = 0; for(int i = 0; i <= 1 ; ++i) { #ifndef Boost_1_34 result |= (m_bits[i] << (bits_per_block * i)); #else unsigned long piece = m_bits[i]; result |= (piece << (bits_per_block * i)); #endif printf("result = %llx\n", result); } } cxxosf.zko.hp.com> cxx x.cpp && a.out result = ffffffff result = ffffffff cxxosf.zko.hp.com> cxx x.cpp -DBoost_1_34 && a.out result = ffffffff result = ffffffffffffffff cxxosf.zko.hp.com> Replacing result |= (m_bits[i] << (bits_per_block * i)); with unsigned long piece = m_bits[i]; result |= (piece << (bits_per_block * i)); on the trunk makes the test succeed: verified on Tru64/cxx and on HP-UX/aCC. In <http://lists.boost.org/Archives/boost/2007/12/131126.php> I said: > It looks like a regression in boost/dynamic_bitset/dynamic_bitset.hpp > introduced in 1.35, but even in 1.34.1, it seems to me that the code in > to_ulong() is relying on undefined behaviour. What I was referring to is the code in 1.34 applying bitwise shift operator to a long operand. It would trigger an undefined behavior in C where "The operands shall have integer type", but it is legal in C++ where "The operands shall be of integral or enumeration type". So, I no longer claim that the code in 1.34 is relying on undefined behaviour. And the last thing: why the bug affects only platforms where 'long' type is larger than 'int'? Because if they are the same, as is the case on VMS or HP-UX in 32-bit data model, last_block = 0 and the single iteration of the for loop just assigns m_bits[0] to the result: the right operand of the shift operator is zero. To fix the problem, I suggest to replace the buggy code in <boost/dynamic_bitset/dynamic_bitset.hpp> in the trunk with that in 1.34. If there are no objections, I can do it. Thanks, Boris

3 3

[math] pow redux and observations
by John Moeller 05 Jul '08

05 Jul '08

I noticed that the trunk now has corrections for pow<N> to reduce template instantiations. However, the "N=1" specialization isn't correct. The second template parameter (bool odd) should be "true," not "false." I could be mistaken that 1 is an odd number, though. :-) As it is now, the whole template would work, but would ignore the 1/false specialization and create a new 1/true specialization that just multiplies "base" by the result of 0/false. Changing 1/false to 1/true will just cause it to return "base," as desired. Note also, please, that positive_power<0,false> returns 1 when base is 0. Since 0^0 is technically undefined, the "N=0" case should probably be handled at a higher level (in power_if_positive, perhaps), and cause an error, just like negative powers of 0. If that is done, the 0/false case could be removed from positive_power.

9 50

[filesystem] Function name changes
by Beman Dawes 05 Jul '08

05 Jul '08

All the changes mentioned below leave the current names in place as synonyms, so will break no existing code. * Change is_regular() to is_regular_file(). Dave Abrahams and several other people, including me, have found that the name of the is_regular() function is too obscure. It was chosen over is_regular_file() for brevity, but isn't holding up well with experience. The status name is already "regular_file" and the term "regular file" is used by the POSIX standard. * Change leaf() to base_name(). * Change branch() to base_path(). In the long thread '[filesystem] "leaf"', several people found the current names obscure or invoking the wrong metaphor. Many alternative names were discussed, with an eye to making the names more obvious, conforming to names such as "basename" used in other programming languages, and/or using names already in use by the STL. Not breaking existing code was also a major concern, given that "basename" is already used in Boost.Filesystem. The mental model for the new names is that for a path, p: p == p.base_path() / p.base_name() Thus if p == "foo/bar/boo.txt", p.base_path() == "foo/bar", and p.base_name() == "boo.txt". * Change basename() to base_name_prefix(). * Change to extension() to base_name_extension(). This change is to avoid confusion with base_name(). The mental model for the new name is that for a path, p: p.base_name() == base_name_prefix(p) + base_name_extension(p) Thus if p == "foo/bar/boo.txt", base_name_prefix(p) == "boo", and base_name_extension(p) == ".txt". Comments? --Beman

10 41

filesystem question
by Emil Dotchevski 05 Jul '08

05 Jul '08

What is the rationale for providing path and wpath types instead of using a single path type? Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode

3 3

libs/dynamic_bitset/bitset_test unmerged changes?
by David Abrahams 05 Jul '08

05 Jul '08

Should these be in the trunk? Index: bitset_test.hpp =================================================================== --- bitset_test.hpp (revision 40672) +++ bitset_test.hpp (working copy) @@ -1006,7 +1006,8 @@ bool did_throw = false; try { - s << b; + static_cast<void> + (s << b); } #if defined BOOST_OLD_IOSTREAMS catch(...) { @@ -1081,7 +1082,8 @@ const std::ios::iostate except = is.exceptions(); bool has_stream_exceptions = true; try { - is >> b; + static_cast<void> + (is >> b); } catch(const std::ios::failure &) { did_throw = true; -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

2 1

Finding algorithms returning ranges?
by Mathias Gaunard 04 Jul '08

04 Jul '08

Finding algorithms (find, find_if, max_element, and others) usually return an iterator to the found position, or the past-the-end iterator. While enough, it can be quite annoying when used with range adaptors and the like. Imagine something like this: auto r = some_range | some adapters...; auto it = max_element(r, comparison_function); if(it != end(r)) { do_something; } Without auto, it is simply unusable. If such algorithms returned the range [found, end), we would be able to write: if(!empty(max_element(some_range | some adapters..., comparison_function)) { do_something; } Particularly, I find it practical to use it with a function like that: optional<typename range_value<Range>::type> deref_opt(const Range& r) { typedef typename range_value<Range>::type T; return empty(r) ? optional<T>() : optional<T>(*begin(r)); } or like that: typename range_value<Range>::type deref_def(const Range& r) { typedef typename range_value<Range>::type T; return empty(r) ? T() : *begin(r); } For compatibility, maybe returning a range type that implicitly converts to the beginning iterator could work. Do people think this is a good idea?

2 1

Re: [boost] Any interest in generic sequence searching through single-pass iterators?
by dpxguard-boost＠yahoo.gr 04 Jul '08

04 Jul '08

Jim Xochellis wrote: > > I have written in my free time the "single_pass_search" C++ template function, which performs generic sequence searching similarly to the std::search STL algorithm. The most important quality of single_pass_search and its main advantage over std::search > > is its capability to search for a sub-sequence in a search-range that is accessed through a pair of single-pass (input) iterators, while std::search requires that the search-range must be accessed via forward iterators at least. Mathias Gaunard wrote: > I guess it could be interesting to overload std::search to work with > input iterators too. > There is no need to give it a different name. Unfortunately, I cannot think of a way to "overload" std::search to work with input iterators, without changing its behavior significantly. Please see the section "Oddities and drawbacks" of the Home/Algorithms/single_pass_search/single_pass_search.html documentation file in the "Boost File Vault", for more details. Best regards, Jim Xochellis ___________________________________________________________ Χρησιμοποιείτε Yahoo!; Βαρεθήκατε τα ενοχλητικά μηνύματα (spam); Το Yahoo! Mail διαθέτει την καλύτερη δυνατή προστασία κατά των ενοχλητικών μηνυμάτων http://login.yahoo.com/config/mail?.intl=gr

1 0

Any interest in generic sequence searching through single-pass iterators?
by dpxguard-boost＠yahoo.gr 04 Jul '08

04 Jul '08

Hi list, I have written in my free time the "single_pass_search" C++ template function, which performs generic sequence searching similarly to the std::search STL algorithm. The most important quality of single_pass_search and its main advantage over std::search is its capability to search for a sub-sequence in a search-range that is accessed through a pair of single-pass (input) iterators, while std::search requires that the search-range must be accessed via forward iterators at least. For example, single_pass_search can easily search a file directly through a pair of istream iterators, while std::search requires the interference of an intermediate container in order to obtain the file data via a pair of forward iterators at least. With data sources like istream, using single_pass_search instead of std::search is by far simpler, more efficient and less memory consuming as well, because the std::search algorithm additionally requires an intermediate container and some stream buffering logic. Anybody interested? For more information, I have uploaded in the "Boost File Vault" the following files: Documentation: Home/Algorithms/single_pass_search/single_pass_search.html Implementation: Home/Algorithms/single_pass_search/single_pass_search.h Example: Home/Algorithms/single_pass_search/Example..cpp Best regards, Jim Xochellis ___________________________________________________________ Χρησιμοποιείτε Yahoo!; Βαρεθήκατε τα ενοχλητικά μηνύματα (spam); Το Yahoo! Mail διαθέτει την καλύτερη δυνατή προστασία κατά των ενοχλητικών μηνυμάτων http://login.yahoo.com/config/mail?.intl=gr

2 1

[1.36.0] Final requirements for directory and file names
by Beman Dawes 04 Jul '08

04 Jul '08

The final requirements for directory and file names are now posted at http://beta.boost.org/development/requirements.html#Directory_structure These are now stable for 1.36.0. Hopefully they will also be stable for quite some time beyond 1.36.0. The inspect program has been updated accordingly. --Beman

7 12

Compile time maths/square root?
by Joseph Gauterin 04 Jul '08

04 Jul '08

Does boost have a library of compile time maths functions? I've only been able to find GCD and LCM algorithms (boost/math/common_factor.hpp) If such a library exists, it would be worth adding a summary of them to /libs/math/doc/html/index.html In paticular, I was looking for a compile time integer square root function.

2 1