[boost] Bits and Ints: Intention Request

Subject: [boost] Bits and Ints: Intention Request
From: Murilo Adriano Vasconcelos (muriloufg_at_[hidden])
Date: 2010-07-14 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 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/doc/html/boost_integer/bits_and_ints.html(unformatted)

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