mpz_combit

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

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

Any comments on this code?

Regards,
/Niels

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