| OLD | NEW |
|---|
| (Empty) |
| 1 /* mpn_sb_bdiv_qr -- schoolbook Hensel division with precomputed inverse, | |
| 2 returning quotient and remainder. | |
| 3 | |
| 4 Contributed to the GNU project by Niels Möller. | |
| 5 | |
| 6 THE FUNCTIONS IN THIS FILE ARE INTERNAL FUNCTIONS WITH MUTABLE INTERFACES. | |
| 7 IT IS ONLY SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. | |
| 8 | |
| 9 Copyright 2006 Free Software Foundation, Inc. | |
| 10 | |
| 11 This file is part of the GNU MP Library. | |
| 12 | |
| 13 The GNU MP Library is free software; you can redistribute it and/or modify | |
| 14 it under the terms of the GNU Lesser General Public License as published by | |
| 15 the Free Software Foundation; either version 3 of the License, or (at your | |
| 16 option) any later version. | |
| 17 | |
| 18 The GNU MP Library is distributed in the hope that it will be useful, but | |
| 19 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
| 20 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public | |
| 21 License for more details. | |
| 22 | |
| 23 You should have received a copy of the GNU Lesser General Public License | |
| 24 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ | |
| 25 | |
| 26 #include "gmp.h" | |
| 27 #include "gmp-impl.h" | |
| 28 | |
| 29 | |
| 30 /* Computes a binary quotient of size qn = nn - dn. | |
| 31 Output: | |
| 32 | |
| 33 Q = N * D^{-1} mod B^qn, | |
| 34 | |
| 35 R = (N - Q * D) * B^(-qn) | |
| 36 | |
| 37 Stores the dn least significant limbs of R at {np + nn - dn, dn}, | |
| 38 and returns the borrow from the subtraction N - Q*D. | |
| 39 | |
| 40 D must be odd. dinv is (-D)^-1 mod B. */ | |
| 41 | |
| 42 mp_limb_t | |
| 43 mpn_sb_bdiv_qr (mp_ptr qp, | |
| 44 mp_ptr np, mp_size_t nn, | |
| 45 mp_srcptr dp, mp_size_t dn, mp_limb_t dinv) | |
| 46 { | |
| 47 mp_size_t qn; | |
| 48 mp_size_t i; | |
| 49 mp_limb_t rh; | |
| 50 mp_limb_t ql; | |
| 51 | |
| 52 ASSERT (nn > 0); | |
| 53 ASSERT (dn > 0); | |
| 54 ASSERT (nn > dn); | |
| 55 ASSERT (dp[0] & 1); | |
| 56 | |
| 57 qn = nn - dn; | |
| 58 | |
| 59 rh = 0; | |
| 60 | |
| 61 /* To complete the negation, this value is added to q. */ | |
| 62 ql = 1; | |
| 63 while (qn > dn) | |
| 64 { | |
| 65 for (i = 0; i < dn; i++) | |
| 66 { | |
| 67 mp_limb_t q; | |
| 68 | |
| 69 q = dinv * np[i]; | |
| 70 qp[i] = ~q; | |
| 71 | |
| 72 np[i] = mpn_addmul_1 (np + i, dp, dn, q); | |
| 73 } | |
| 74 rh += mpn_add (np + dn, np + dn, qn, np, dn); | |
| 75 ql = mpn_add_1 (qp, qp, dn, ql); | |
| 76 | |
| 77 qp += dn; qn -= dn; | |
| 78 np += dn; nn -= dn; | |
| 79 } | |
| 80 | |
| 81 for (i = 0; i < qn; i++) | |
| 82 { | |
| 83 mp_limb_t q; | |
| 84 | |
| 85 q = dinv * np[i]; | |
| 86 qp[i] = ~q; | |
| 87 | |
| 88 np[i] = mpn_addmul_1 (np + i, dp, dn, q); | |
| 89 } | |
| 90 | |
| 91 rh += mpn_add_n (np + dn, np + dn, np, qn); | |
| 92 ql = mpn_add_1 (qp, qp, qn, ql); | |
| 93 | |
| 94 if (UNLIKELY (ql > 0)) | |
| 95 { | |
| 96 /* q == 0 */ | |
| 97 ASSERT (rh == 0); | |
| 98 return 0; | |
| 99 } | |
| 100 else | |
| 101 { | |
| 102 mp_limb_t cy; | |
| 103 | |
| 104 cy = mpn_sub_n (np + qn, np + qn, dp, dn); | |
| 105 ASSERT (cy >= rh); | |
| 106 return cy - rh; | |
| 107 } | |
| 108 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 3050029:
[gcc] GCC 4.5.0=>4.5.1 (Closed)
Base URL: ssh://git@gitrw.chromium.org:9222/nacl-toolchain.git