/src/gmp/mpn/sbpi1_bdiv_q.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* mpn_sbpi1_bdiv_q -- schoolbook Hensel division with precomputed inverse, |
2 | | returning quotient only. |
3 | | |
4 | | Contributed to the GNU project by Niels Möller and Torbjörn Granlund. |
5 | | |
6 | | THE FUNCTIONS IN THIS FILE ARE INTERNAL FUNCTIONS WITH MUTABLE INTERFACES. |
7 | | IT IS ONLY SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS |
8 | | ALMOST GUARANTEED THAT THEY'LL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE. |
9 | | |
10 | | Copyright 2005, 2006, 2009, 2011, 2012, 2017 Free Software Foundation, Inc. |
11 | | |
12 | | This file is part of the GNU MP Library. |
13 | | |
14 | | The GNU MP Library is free software; you can redistribute it and/or modify |
15 | | it under the terms of either: |
16 | | |
17 | | * the GNU Lesser General Public License as published by the Free |
18 | | Software Foundation; either version 3 of the License, or (at your |
19 | | option) any later version. |
20 | | |
21 | | or |
22 | | |
23 | | * the GNU General Public License as published by the Free Software |
24 | | Foundation; either version 2 of the License, or (at your option) any |
25 | | later version. |
26 | | |
27 | | or both in parallel, as here. |
28 | | |
29 | | The GNU MP Library is distributed in the hope that it will be useful, but |
30 | | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
31 | | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
32 | | for more details. |
33 | | |
34 | | You should have received copies of the GNU General Public License and the |
35 | | GNU Lesser General Public License along with the GNU MP Library. If not, |
36 | | see https://www.gnu.org/licenses/. */ |
37 | | |
38 | | #include "gmp-impl.h" |
39 | | |
40 | | /* Computes Q = - U / D mod B^un, destroys U. |
41 | | |
42 | | D must be odd. dinv is (-D)^-1 mod B. |
43 | | |
44 | | */ |
45 | | |
46 | | void |
47 | | mpn_sbpi1_bdiv_q (mp_ptr qp, |
48 | | mp_ptr up, mp_size_t un, |
49 | | mp_srcptr dp, mp_size_t dn, |
50 | | mp_limb_t dinv) |
51 | 0 | { |
52 | 0 | mp_size_t i; |
53 | 0 | mp_limb_t q; |
54 | |
|
55 | 0 | ASSERT (dn > 0); |
56 | 0 | ASSERT (un >= dn); |
57 | 0 | ASSERT ((dp[0] & 1) != 0); |
58 | 0 | ASSERT (-(dp[0] * dinv) == 1); |
59 | 0 | ASSERT (up == qp || !MPN_OVERLAP_P (up, un, qp, un - dn)); |
60 | |
|
61 | 0 | if (un > dn) |
62 | 0 | { |
63 | 0 | mp_limb_t cy, hi; |
64 | 0 | for (i = un - dn - 1, cy = 0; i > 0; i--) |
65 | 0 | { |
66 | 0 | q = dinv * up[0]; |
67 | 0 | hi = mpn_addmul_1 (up, dp, dn, q); |
68 | |
|
69 | 0 | ASSERT (up[0] == 0); |
70 | 0 | *qp++ = q; |
71 | 0 | hi += cy; |
72 | 0 | cy = hi < cy; |
73 | 0 | hi += up[dn]; |
74 | 0 | cy += hi < up[dn]; |
75 | 0 | up[dn] = hi; |
76 | 0 | up++; |
77 | 0 | } |
78 | 0 | q = dinv * up[0]; |
79 | 0 | hi = cy + mpn_addmul_1 (up, dp, dn, q); |
80 | 0 | ASSERT (up[0] == 0); |
81 | 0 | *qp++ = q; |
82 | 0 | up[dn] += hi; |
83 | 0 | up++; |
84 | 0 | } |
85 | 0 | for (i = dn; i > 1; i--) |
86 | 0 | { |
87 | 0 | mp_limb_t q = dinv * up[0]; |
88 | 0 | mpn_addmul_1 (up, dp, i, q); |
89 | 0 | ASSERT (up[0] == 0); |
90 | 0 | *qp++ = q; |
91 | 0 | up++; |
92 | 0 | } |
93 | | |
94 | | /* Final limb */ |
95 | 0 | *qp = dinv * up[0]; |
96 | 0 | } |