# [PPL-devel] Re: Integers as bit arrays

Brian Hurt bhurt@spnz.org
Wed, 30 Jul 2003 17:37:00 -0500 (CDT)

```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

```