[PPL-devel] Re: Integers as bit arrays

[Brian Hurt]

On Wed, 30 Jul 2003, Roberto Bagnara wrote:

> Good.  For the names, I think the choice belongs to senior GMP
> developer; for the good implementations, what I contributed is
> a possible starting point that Brian can refine at will (I will
> release it under a different license if that helps).

An update on my stuff, for those who care: I'm working on the bitblit
routine.  This is the core function- where most of the work happens.  It's 
prototype is:

void bitblit (
    mp_limb_t * dst,
    unsigned dst_off,
    mp_limb_t * src, 
    unsigned src_off,
    unsigned num_bits) 

Unfortunately, I've set rather high goals for myself: such a routine
should be a) in portable C (I've allowed myself to assume that limbs are a
set of bits- i.e. BCD systems won't work, but nothing else), b) reasonably
efficient, c) handles all corner cases correctly, d) is maintainable
and understandable (i.e. can be used by the assembly language programmers
as a template for needed functionality), and e) special-cases as little as 
possible.

The corner cases and special cases are the problem.  Consider for a moment 
what the value of 1 << GMP_NUMB_BITS is.  On some systems, the result 
would be 0- the 1 would be "shifted off the left" of the word.  Other 
systems, however, mod the shift amount by GMP_NUMB_BITS before starting 
the shifting.  So the above expression would be equal to 
1 << (GMP_NUMB_BITS % GMP_NUMB_BITS) == 1 << 0 == 1.  Opps.  But now every 
time I want to just do x << (GMP_NUMB_BITS - y), I need to make sure that 
y > 0!.  Likewise, x << -1 is a bad idea as well- which means any time I 
want to do x << (y - 1) I also need y > 0.  

This is where I'm getting the explosion of special cases to handle these
corner cases.  But I don't want to have too many special cases- each
special case is another branch, and that starts hurting performance.  Nor 
do I want to do things exceptionally tricky (or exceptionally verbose), as 
this hurts maintainability.  Etc.

I'm getting there- it's just taking a little longer than expected.  Please 
stand by.

Brian