mpz_combit

[Niels Möller]

I've tried rewriting mpz_combit. Two reasons: 1. To reduce overhead int
he common case. 2. I just realized that the common case, for both
positive and negative numbers, is to complement the corresponding bit
of  the absolute value.

Code below (with some additional comments).

 void
 mpz_combit (mpz_ptr d, mp_bitcnt_t bit_index)
 {
   mp_size_t dsize = SIZ(d);
   mp_ptr dp = PTR(d);
 
   mp_size_t limb_index = bit_index / GMP_NUMB_BITS;
   mp_limb_t bit = (CNST_LIMB (1) << (bit_index % GMP_NUMB_BITS));
 
   /* Check for the most common case: Positive input, no realloc or
      normalization needed. */
   if (limb_index + 1 < dsize)    
     dp[limb_index] ^= bit;

The above case is an optimization for the common case. If deleted, it
should still be handled correctly by the common-case code later on.

   /* Check for the hairy case. d < 0, and we have all zero bits to the
      right of the bit to toggle. */
   else if (limb_index < -dsize && mpn_zero_p (dp, limb_index)
            && (dp[limb_index] & (bit - 1)) == 0)
     {      
       ASSERT (dsize < 0);
       dsize = -dsize;
 
       if (dp[limb_index] & bit)
         {
           /* We toggle the least significant one bit.
              Corresponds to an add, with carry propagation, on the
              absolute value. */
           dp = MPZ_REALLOC (d, 1 + dsize);
           dp[dsize] = 0;
           MPN_INCR_U (dp + limb_index, 1 + dsize - limb_index, bit);
           SIZ(d) -= dp[dsize];
         }
       else
         {
           /* We toggle a zero bit, subtract from the absolute value. */
           MPN_DECR_U (dp + limb_index, dsize - limb_index, bit);
           MPN_NORMALIZE (dp, dsize);
           ASSERT (dsize > 0);
           SIZ(d) = -dsize;
         }
     }
   else
     {
       /* Simple case: Toggle the bit in the absolute value. */
       dsize = ABS(dsize);
       if (limb_index < dsize)
         {
           dp[limb_index] ^= bit;
 
           /* Can happen only when limb_index = dsize - 1. Avoid SIZ(d)
              bookkeeping in the common case. */
           if (dp[dsize-1] == 0)
             {
               dsize--;
               MPN_NORMALIZE (dp, dsize);
               SIZ (d) = SIZ (d) >= 0 ? dsize : -dsize;
             }

Here, MPN_NORMALIZE could be called unconditionally. I write it this way
in order to avoid having to check the sign of SIZ (d) in the common
case. Not sure if that optimization is worth the two extra lines of code.

         }
       else
         {
           dp = MPZ_REALLOC (d, limb_index + 1);
           MPN_ZERO(dp + dsize, limb_index - dsize);
           dp[limb_index++] = bit;
           SIZ(d) = SIZ(d) >= 0 ? limb_index : -limb_index;
         }
     }
 }

Another reflection: I think it would make sense to have mpz_combit
return the value of the bit in question. It might also make sense to
have setbit and clrbit return the previous value of the bit (and in that
case, for consistency combit should probably return the *previous* value
of the bit, not the new value). That would be an interface change, of
course.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.