Line | Count | Source |
1 | | /* mpn_redc_n. Set rp[] <- up[]/R^n mod mp[]. Clobber up[]. |
2 | | mp[] is n limbs; up[] is 2n limbs, the inverse ip[] is n limbs. |
3 | | |
4 | | THIS IS AN INTERNAL FUNCTION WITH A MUTABLE INTERFACE. IT IS ONLY |
5 | | SAFE TO REACH THIS FUNCTION THROUGH DOCUMENTED INTERFACES. |
6 | | |
7 | | Copyright 2009, 2012 Free Software Foundation, Inc. |
8 | | |
9 | | This file is part of the GNU MP Library. |
10 | | |
11 | | The GNU MP Library is free software; you can redistribute it and/or modify |
12 | | it under the terms of either: |
13 | | |
14 | | * the GNU Lesser General Public License as published by the Free |
15 | | Software Foundation; either version 3 of the License, or (at your |
16 | | option) any later version. |
17 | | |
18 | | or |
19 | | |
20 | | * the GNU General Public License as published by the Free Software |
21 | | Foundation; either version 2 of the License, or (at your option) any |
22 | | later version. |
23 | | |
24 | | or both in parallel, as here. |
25 | | |
26 | | The GNU MP Library is distributed in the hope that it will be useful, but |
27 | | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
28 | | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
29 | | for more details. |
30 | | |
31 | | You should have received copies of the GNU General Public License and the |
32 | | GNU Lesser General Public License along with the GNU MP Library. If not, |
33 | | see https://www.gnu.org/licenses/. */ |
34 | | |
35 | | #include "gmp-impl.h" |
36 | | |
37 | | /* |
38 | | TODO |
39 | | |
40 | | * We assume mpn_mulmod_bnm1 is always faster than plain mpn_mul_n (or a |
41 | | future mpn_mulhi) for the range we will be called. Follow up that |
42 | | assumption. |
43 | | |
44 | | * Decrease scratch usage. |
45 | | |
46 | | * Consider removing the residue canonicalisation. |
47 | | */ |
48 | | |
49 | | void |
50 | | mpn_redc_n (mp_ptr rp, mp_ptr up, mp_srcptr mp, mp_size_t n, mp_srcptr ip) |
51 | 2.22M | { |
52 | 2.22M | mp_ptr xp, yp, scratch; |
53 | 2.22M | mp_limb_t cy; |
54 | 2.22M | mp_size_t rn; |
55 | 2.22M | TMP_DECL; |
56 | 2.22M | TMP_MARK; |
57 | | |
58 | 2.22M | ASSERT (n > 8); |
59 | | |
60 | 2.22M | rn = mpn_mulmod_bnm1_next_size (n); |
61 | | |
62 | 2.22M | scratch = TMP_ALLOC_LIMBS (n + rn + mpn_mulmod_bnm1_itch (rn, n, n)); |
63 | | |
64 | 2.22M | xp = scratch; |
65 | 2.22M | mpn_mullo_n (xp, up, ip, n); |
66 | | |
67 | 2.22M | yp = scratch + n; |
68 | 2.22M | mpn_mulmod_bnm1 (yp, rn, xp, n, mp, n, scratch + n + rn); |
69 | | |
70 | 2.22M | ASSERT_ALWAYS (2 * n > rn); /* could handle this */ |
71 | | |
72 | 2.22M | cy = mpn_sub_n (yp + rn, yp, up, 2*n - rn); /* undo wrap around */ |
73 | 2.22M | MPN_DECR_U (yp + 2*n - rn, rn, cy); |
74 | | |
75 | 2.22M | cy = mpn_sub_n (rp, up + n, yp + n, n); |
76 | 2.22M | if (cy != 0) |
77 | 2.11M | mpn_add_n (rp, rp, mp, n); |
78 | | |
79 | 2.22M | TMP_FREE; |
80 | 2.22M | } |