[PPL-devel] Re: Integers as bit arrays

Kevin Ryde user42@zip.com.au
Thu, 31 Jul 2003 09:48:32 +1000

Brian Hurt <bhurt@spnz.org> writes:
> 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.

Yep.  ia64 is the only arch I'm aware of which doesn't just take the
low 5 (or 6) bits of the shift.

> But now every 
> time I want to just do x << (GMP_NUMB_BITS - y), I need to make sure that 
> y > 0!.

Yes, you generally end up needing separate loops for shift==0 and
shift!=0.  The former in this case is just a block copy I guess.

Another possibility is to create a mask limb, either 0 or 0xFF..FF,
which can zap the unwanted "x<<32" so its value doesn't matter.

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

You'll probably end up with four cases, based on whether the move is
upwards or downwards (to cope with overlapping src and dst), and on
whether the net shift is zero or non-zero.

For the shifting you should aim to use mpn_lshift and mpn_rshift.
They allow overlaps in their defined direction (see the docs), and are
implemented in assembler.

You'll still have some fiddling about for the first and last limbs no
doubt, but basically you want to get into an lshift, rshift or block
copy.  (Within gmp copying is done with MPN_COPY_INCR and
MPN_COPY_DECR from gmp-impl.h).