Bits and Ints: Intention Request
Hi, I am working on GSoC Bits and Ints project wich is a library with functions for integral data types. The motivation for this library is to provide integer algorithms and utilities optimized by doing binary manipulations so that it uses less CPU cycles, memory access and conditional branches. This library contains some classical integer algorithms such as population count, reversing bits, sign extension and bit interleaving. Would be great to Boost to incorporate this library because its functions can be used on a widely types of applications that needs to perform fast operations on integral types. Since one of slowest operations perfomed by the CPU is conditional braching (it involves pipelining, recaching, etc) this library avoid it. For the runtime versions, conditional branch is not used (if, switch, for, while, etc). Other motivation to adopt this library is the integration with Boost.MPL. Almost every function implemented have it MPL and non-MPL static version. For example: // Runtime int pop_count(uintmax_t value); // non-MPL metafunction template <uintmax_t Value> struct static_pop_count {}; // MPL template <typename IC> struct pop_count : integral_c<int, static_pop_count<IC::value>::value> {}; The contents of this library is inside of boost/integer folder and can be viewed in [0]. The static and MPL compatible metafunctions are declared on headers with static_ prefix. The partial documentation can be viewed in [1]. What already is implemented (underlined are out of proposal) - Sign extension from a length of m bits to a length of n - Bit reversal - Bit-interleaving and uninterleaving - Programming utilities for bit and bitmask manipulation - Sign function - Transfer of sign - Clear Least-Significant Nonzero Bit - Round Up or Down to Next Power of 2 - Count Trailing Zeros - Population Count - *Integer Log2* - *Count Leading Zeros* - Compile time MPL compatible abs - Compile time MPL compatible lcm - Compile time MPL compatible gcd - Safe average functions - Swap without a temporary - Templated class is_integral_constant<> My plan is to implement these functions: - Run-time GCD - Run-time LCM - Functions for getting carry bits from addition and the high-half of an integer multiply - Rounding right-shifts - Saturating arithmetic operations - Multi-word shifts - Two-word divide by one-word value - Bounds Checking - Power of 2 Crossing - Find First String of 1-Bits of a Given Length - Incrementing a Reversed Integer - Decoding a “Zero Means 2n” Field - Integer Log Base 10 I want to know wich functions you think that it is interesting to implement in this library. Also, comments and suggestions are appreciated. [0] - http://svn.boost.org/svn/boost/sandbox/SOC/2010/bits_and_ints/boost/integer/ [1] - http://svn.boost.org/svn/boost/sandbox/SOC/2010/bits_and_ints/libs/integer/d...) References: http://aggregate.org/MAGIC/ http://graphics.stanford.edu/~seander/bithacks.html http://bits.stephan-brumme.com/ http://www.boost.org/doc/libs/1_35_0/libs/integer/index.html Hacker's Delight / Henry S. Warren, Jr Regards, -- Murilo Adriano Vasconcelos http://murilo.wordpress.com
hi,
- *Count Leading Zeros*
as for: template <typename T> inline int count_leading_zeros(T value) { #ifndef BOOST_HAS_NO_INT64_T return __builtin_clzll(value) - (64 - (sizeof(T) << 3)); #else return __builtin_clz(value) - (32 - (sizeof(T) << 3)); #endif } __builtin_clz comes in different versions for unsigned int, unsigned long and unsigned long long. i think the safest way to make use of the correct version is by using template specialization ... maybe similar to [1] ... i am also not sure, how it will behave for signed types ... but it is great to see an ilog2 implementation ... cheers, tim [1] http://tim.klingt.org/git?p=boost_heap.git;a=blob;f=boost/heap/detail/ilog2.... -- tim@klingt.org http://tim.klingt.org Cheat your landlord if you can and must, but do not try to shortchange the Muse. It cannot be done. You can't fake quality any more than you can fake a good meal. William S. Burroughs
I did that way because GCC do not have those __builtin functions for 16-bit and 8-bit integral types. So, that way I implemented it works for 64, 32, 16 an 8-bit *unsigned* integral values. 2010/7/14 Tim Blechmann <tim@klingt.org>
hi,
- *Count Leading Zeros*
as for:
template <typename T> inline int count_leading_zeros(T value) { #ifndef BOOST_HAS_NO_INT64_T return __builtin_clzll(value) - (64 - (sizeof(T) << 3)); #else return __builtin_clz(value) - (32 - (sizeof(T) << 3)); #endif }
__builtin_clz comes in different versions for unsigned int, unsigned long and unsigned long long. i think the safest way to make use of the correct version is by using template specialization ... maybe similar to [1] ... i am also not sure, how it will behave for signed types ...
but it is great to see an ilog2 implementation ...
=)
cheers, tim
[1]
http://tim.klingt.org/git?p=boost_heap.git;a=blob;f=boost/heap/detail/ilog2....
-- tim@klingt.org http://tim.klingt.org
Cheat your landlord if you can and must, but do not try to shortchange the Muse. It cannot be done. You can't fake quality any more than you can fake a good meal. William S. Burroughs
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Best, -- Murilo Adriano Vasconcelos http://murilo.wordpress.com
But maybe it can be a good point to use enable_if<> to for 8 and 16-bit integrals specializations and use the correct __builtin for the others like: template <typename T> inline int count_leading_zeros(T value) { #ifndef BOOST_HAS_NO_INT64_T return __builtin_clzll(value) - (64 - (sizeof(T) << 3)); #else return __builtin_clz(value) - (32 - (sizeof(T) << 3)); #endif } template<> inline int count_leading_zeros(unsigned int value) { return __builtin_clz(value); } template<> inline int count_leading_zeros(unsigned long int value) { return __builtin_clzl(value); } template<> inline int count_leading_zeros(unsigned long long int value) { return __builtin_clzll(value); } What do you think? 2010/7/14 Murilo Adriano Vasconcelos <muriloufg@gmail.com>
I did that way because GCC do not have those __builtin functions for 16-bit and 8-bit integral types. So, that way I implemented it works for 64, 32, 16 an 8-bit *unsigned* integral values.
2010/7/14 Tim Blechmann <tim@klingt.org>
hi,
- *Count Leading Zeros*
as for:
template <typename T> inline int count_leading_zeros(T value) { #ifndef BOOST_HAS_NO_INT64_T return __builtin_clzll(value) - (64 - (sizeof(T) << 3)); #else return __builtin_clz(value) - (32 - (sizeof(T) << 3)); #endif }
__builtin_clz comes in different versions for unsigned int, unsigned long and unsigned long long. i think the safest way to make use of the correct version is by using template specialization ... maybe similar to [1] ... i am also not sure, how it will behave for signed types ...
but it is great to see an ilog2 implementation ...
=)
cheers, tim
[1]
http://tim.klingt.org/git?p=boost_heap.git;a=blob;f=boost/heap/detail/ilog2....
-- tim@klingt.org http://tim.klingt.org
Cheat your landlord if you can and must, but do not try to shortchange the Muse. It cannot be done. You can't fake quality any more than you can fake a good meal. William S. Burroughs
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Best,
-- Murilo Adriano Vasconcelos http://murilo.wordpress.com
-- Murilo Adriano Vasconcelos http://murilo.wordpress.com
Murillo, please don't top post. ----- Original Message ----- From: "Murilo Adriano Vasconcelos" <muriloufg@gmail.com> To: <boost@lists.boost.org> Sent: Wednesday, July 14, 2010 10:43 PM Subject: Re: [boost] Bits and Ints: Intention Request
But maybe it can be a good point to use enable_if<> to for 8 and 16-bit integrals specializations and use the correct __builtin for the others like:
template <typename T> inline int count_leading_zeros(T value) { #ifndef BOOST_HAS_NO_INT64_T return __builtin_clzll(value) - (64 - (sizeof(T) << 3)); #else return __builtin_clz(value) - (32 - (sizeof(T) << 3)); #endif }
I gess the above code should be replace by the following one, when GNUC is defined, isn't it?
template<> inline int count_leading_zeros(unsigned int value) { return __builtin_clz(value); }
template<> inline int count_leading_zeros(unsigned long int value) { return __builtin_clzl(value); }
template<> inline int count_leading_zeros(unsigned long long int value) { return __builtin_clzll(value); }
What do you think?
Instead of function template specialization you can just use overloading. So the you can remove the 'template<>' Best, Vicente
Hi, 2010/7/14 vicente.botet <vicente.botet@wanadoo.fr>
Murillo, please don't top post. ----- Original Message ----- From: "Murilo Adriano Vasconcelos" <muriloufg@gmail.com> To: <boost@lists.boost.org> Sent: Wednesday, July 14, 2010 10:43 PM Subject: Re: [boost] Bits and Ints: Intention Request
But maybe it can be a good point to use enable_if<> to for 8 and 16-bit integrals specializations and use the correct __builtin for the others
like:
template <typename T> inline int count_leading_zeros(T value) { #ifndef BOOST_HAS_NO_INT64_T return __builtin_clzll(value) - (64 - (sizeof(T) << 3)); #else return __builtin_clz(value) - (32 - (sizeof(T) << 3)); #endif }
I gess the above code should be replace by the following one, when GNUC is defined, isn't it?
template<> inline int count_leading_zeros(unsigned int value) { return __builtin_clz(value); }
template<> inline int count_leading_zeros(unsigned long int value) { return __builtin_clzl(value); }
template<> inline int count_leading_zeros(unsigned long long int value) { return __builtin_clzll(value); }
What do you think?
Instead of function template specialization you can just use overloading. So the you can remove the 'template<>'
If `value` don't matches exacly with the parameter type (for example uint8_t or uint16_t) we will receive one error because calling `count_leading_zeros` with this parameter type is ambiguous. So we can do something like this: https://svn.boost.org/trac/boost/browser/sandbox/SOC/2010/bits_and_ints/boos... 32 to 51) Or create overloads for uint8_t and uint16_t. inline int count_leading_zeros(uint8_t value); inline int count_leading_zeros(uint16_t value);
Best, Vicente
Best, -- Murilo Adriano Vasconcelos http://murilo.wordpress.com
participants (3)
-
Murilo Adriano Vasconcelos -
Tim Blechmann -
vicente.botet