ni...@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.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
http://gmplib.org/mailman/listinfo/gmp-devel
