
Boost : 
Subject: [boost] Bits and Ints: Intention Request
From: Murilo Adriano Vasconcelos (muriloufg_at_[hidden])
Date: 20100714 15:58:29
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 nonMPL static
version. For example:
// Runtime
int pop_count(uintmax_t value);
// nonMPL 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
 Bitinterleaving and uninterleaving
 Programming utilities for bit and bitmask manipulation
 Sign function
 Transfer of sign
 Clear LeastSignificant 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:
 Runtime GCD
 Runtime LCM
 Functions for getting carry bits from addition and the highhalf of an
integer multiply
 Rounding rightshifts
 Saturating arithmetic operations
 Multiword shifts
 Twoword divide by oneword value
 Bounds Checking
 Power of 2 Crossing
 Find First String of 1Bits 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/doc/html/boost_integer/bits_and_ints.html(unformatted)
References:
http://aggregate.org/MAGIC/
http://graphics.stanford.edu/~seander/bithacks.html
http://bits.stephanbrumme.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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk