diff options
author | Niels M?ller <nisse@lysator.liu.se> | 2012-11-01 21:18:45 +0100 |
---|---|---|
committer | Niels M?ller <nisse@lysator.liu.se> | 2012-11-01 21:18:45 +0100 |
commit | db6554c699c958505fe0449e43398e483b83bf42 (patch) | |
tree | 08261c2a054eb0494bfec17fa11752ebe06b68ae /mpz | |
parent | 0941d53ad41f00aa7e0fc13bda40ec5971163650 (diff) | |
download | gmp-db6554c699c958505fe0449e43398e483b83bf42.tar.gz |
mpz_combit rewrite.
Diffstat (limited to 'mpz')
-rw-r--r-- | mpz/combit.c | 87 |
1 files changed, 49 insertions, 38 deletions
diff --git a/mpz/combit.c b/mpz/combit.c index 9a4a71780..7f3c9f212 100644 --- a/mpz/combit.c +++ b/mpz/combit.c @@ -23,56 +23,67 @@ along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ void mpz_combit (mpz_ptr d, mp_bitcnt_t bit_index) { - mp_size_t dsize = ABSIZ(d); + 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)); - if (limb_index >= dsize) - { - dp = MPZ_REALLOC(d, limb_index + 1); - - MPN_ZERO(dp + dsize, limb_index + 1 - dsize); - dsize = limb_index + 1; - } + /* Check for the most common case: Positive input, no realloc or + normalization needed. */ + if (limb_index + 1 < dsize) + dp[limb_index] ^= bit; - if (SIZ(d) >= 0) + /* 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) { - dp[limb_index] ^= bit; - MPN_NORMALIZE (dp, dsize); - SIZ(d) = dsize; + ASSERT (dsize < 0); + dsize = -dsize; + + if (dp[limb_index] & bit) + { + /* We toggle the least significant one bit. Corresponds to + an add, with potential 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 { - mp_limb_t x = -dp[limb_index]; - mp_size_t i; - - /* non-zero limb below us means ones-complement */ - for (i = limb_index-1; i >= 0; i--) - if (dp[i] != 0) - { - x--; /* change twos comp to ones comp */ - break; - } - - if (x & bit) + /* Simple case: Toggle the bit in the absolute value. */ + dsize = ABS(dsize); + if (limb_index < dsize) { - mp_limb_t c; - - /* Clearing the bit increases the magitude. We might need a carry. */ - dp = MPZ_REALLOC(d, dsize + 1); - - __GMPN_ADD_1 (c, dp+limb_index, dp+limb_index, - dsize - limb_index, bit); - dp[dsize] = c; - dsize += c; + 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; + } } else - /* Setting the bit decreases the magnitude */ - mpn_sub_1(dp+limb_index, dp+limb_index, dsize + limb_index, bit); - - MPN_NORMALIZE (dp, dsize); - SIZ(d) = -dsize; + { + 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; + } } } |