/src/libgmp/mpn/toom_eval_dgr3_pm2.c
Line | Count | Source |
1 | | /* mpn_toom_eval_dgr3_pm2 -- Evaluate a degree 3 polynomial in +2 and -2 |
2 | | |
3 | | Contributed to the GNU project by Niels Möller |
4 | | |
5 | | THE FUNCTION IN THIS FILE IS INTERNAL WITH A MUTABLE INTERFACE. IT IS ONLY |
6 | | SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST |
7 | | GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE. |
8 | | |
9 | | Copyright 2009 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 either: |
15 | | |
16 | | * the GNU Lesser General Public License as published by the Free |
17 | | Software Foundation; either version 3 of the License, or (at your |
18 | | option) any later version. |
19 | | |
20 | | or |
21 | | |
22 | | * the GNU General Public License as published by the Free Software |
23 | | Foundation; either version 2 of the License, or (at your option) any |
24 | | later version. |
25 | | |
26 | | or both in parallel, as here. |
27 | | |
28 | | The GNU MP Library is distributed in the hope that it will be useful, but |
29 | | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
30 | | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
31 | | for more details. |
32 | | |
33 | | You should have received copies of the GNU General Public License and the |
34 | | GNU Lesser General Public License along with the GNU MP Library. If not, |
35 | | see https://www.gnu.org/licenses/. */ |
36 | | |
37 | | |
38 | | #include "gmp-impl.h" |
39 | | |
40 | | /* Evaluates a polynomial of degree 3, in the points +2 and -2. */ |
41 | | /* Needs n+1 limbs of temporary storage. */ |
42 | | /* It returns 0 or ~0, depending on the sign of the result xm2. */ |
43 | | unsigned |
44 | | mpn_toom_eval_dgr3_pm2 (mp_ptr xp2, mp_ptr xm2, |
45 | | mp_srcptr xp, mp_size_t n, mp_size_t x3n, mp_ptr tp) |
46 | 1.60k | { |
47 | 1.60k | mp_limb_t cy; |
48 | 1.60k | unsigned neg; |
49 | | |
50 | 1.60k | ASSERT (x3n > 0); |
51 | 1.60k | ASSERT (x3n <= n); |
52 | | |
53 | | /* (x0 + 4 * x2) +/- (2 x1 + 8 x_3) */ |
54 | 1.60k | #if HAVE_NATIVE_mpn_addlsh_n || HAVE_NATIVE_mpn_addlsh2_n |
55 | 1.60k | #if HAVE_NATIVE_mpn_addlsh2_n |
56 | 1.60k | xp2[n] = mpn_addlsh2_n (xp2, xp, xp + 2*n, n); |
57 | | |
58 | 1.60k | cy = mpn_addlsh2_n (tp, xp + n, xp + 3*n, x3n); |
59 | | #else /* HAVE_NATIVE_mpn_addlsh_n */ |
60 | | xp2[n] = mpn_addlsh_n (xp2, xp, xp + 2*n, n, 2); |
61 | | |
62 | | cy = mpn_addlsh_n (tp, xp + n, xp + 3*n, x3n, 2); |
63 | | #endif |
64 | 1.60k | if (x3n < n) |
65 | 1.37k | cy = mpn_add_1 (tp + x3n, xp + n + x3n, n - x3n, cy); |
66 | 1.60k | tp[n] = cy; |
67 | | #else |
68 | | cy = mpn_lshift (tp, xp + 2*n, n, 2); |
69 | | xp2[n] = cy + mpn_add_n (xp2, tp, xp, n); |
70 | | |
71 | | tp[x3n] = mpn_lshift (tp, xp + 3*n, x3n, 2); |
72 | | if (x3n < n) |
73 | | tp[n] = mpn_add (tp, xp + n, n, tp, x3n + 1); |
74 | | else |
75 | | tp[n] += mpn_add_n (tp, xp + n, tp, n); |
76 | | #endif |
77 | 1.60k | mpn_lshift (tp, tp, n+1, 1); |
78 | | |
79 | 1.60k | neg = - (unsigned) (mpn_cmp (xp2, tp, n + 1) < 0); |
80 | | |
81 | | #if HAVE_NATIVE_mpn_add_n_sub_n |
82 | | if (neg) |
83 | | mpn_add_n_sub_n (xp2, xm2, tp, xp2, n + 1); |
84 | | else |
85 | | mpn_add_n_sub_n (xp2, xm2, xp2, tp, n + 1); |
86 | | #else |
87 | 1.60k | if (neg) |
88 | 238 | mpn_sub_n (xm2, tp, xp2, n + 1); |
89 | 1.36k | else |
90 | 1.36k | mpn_sub_n (xm2, xp2, tp, n + 1); |
91 | | |
92 | 1.60k | mpn_add_n (xp2, xp2, tp, n + 1); |
93 | 1.60k | #endif |
94 | | |
95 | 1.60k | ASSERT (xp2[n] < 15); |
96 | 1.60k | ASSERT (xm2[n] < 10); |
97 | | |
98 | 1.60k | return neg; |
99 | 1.60k | } |