/src/libgmp/mpn/sbpi1_divappr_q.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* mpn_sbpi1_divappr_q -- Schoolbook division using the Möller-Granlund 3/2 |
2 | | division algorithm, returning approximate quotient. The quotient returned |
3 | | is either correct, or one too large. |
4 | | |
5 | | Contributed to the GNU project by Torbjorn Granlund. |
6 | | |
7 | | THE FUNCTION IN THIS FILE IS INTERNAL WITH A MUTABLE INTERFACE. IT IS ONLY |
8 | | SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST |
9 | | GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE. |
10 | | |
11 | | Copyright 2007, 2009 Free Software Foundation, Inc. |
12 | | |
13 | | This file is part of the GNU MP Library. |
14 | | |
15 | | The GNU MP Library is free software; you can redistribute it and/or modify |
16 | | it under the terms of either: |
17 | | |
18 | | * the GNU Lesser General Public License as published by the Free |
19 | | Software Foundation; either version 3 of the License, or (at your |
20 | | option) any later version. |
21 | | |
22 | | or |
23 | | |
24 | | * the GNU General Public License as published by the Free Software |
25 | | Foundation; either version 2 of the License, or (at your option) any |
26 | | later version. |
27 | | |
28 | | or both in parallel, as here. |
29 | | |
30 | | The GNU MP Library is distributed in the hope that it will be useful, but |
31 | | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
32 | | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
33 | | for more details. |
34 | | |
35 | | You should have received copies of the GNU General Public License and the |
36 | | GNU Lesser General Public License along with the GNU MP Library. If not, |
37 | | see https://www.gnu.org/licenses/. */ |
38 | | |
39 | | |
40 | | #include "gmp-impl.h" |
41 | | #include "longlong.h" |
42 | | |
43 | | mp_limb_t |
44 | | mpn_sbpi1_divappr_q (mp_ptr qp, |
45 | | mp_ptr np, mp_size_t nn, |
46 | | mp_srcptr dp, mp_size_t dn, |
47 | | mp_limb_t dinv) |
48 | 0 | { |
49 | 0 | mp_limb_t qh; |
50 | 0 | mp_size_t qn, i; |
51 | 0 | mp_limb_t n1, n0; |
52 | 0 | mp_limb_t d1, d0; |
53 | 0 | mp_limb_t cy, cy1; |
54 | 0 | mp_limb_t q; |
55 | 0 | mp_limb_t flag; |
56 | |
|
57 | 0 | ASSERT (dn > 2); |
58 | 0 | ASSERT (nn >= dn); |
59 | 0 | ASSERT ((dp[dn-1] & GMP_NUMB_HIGHBIT) != 0); |
60 | |
|
61 | 0 | np += nn; |
62 | |
|
63 | 0 | qn = nn - dn; |
64 | 0 | if (qn + 1 < dn) |
65 | 0 | { |
66 | 0 | dp += dn - (qn + 1); |
67 | 0 | dn = qn + 1; |
68 | 0 | } |
69 | |
|
70 | 0 | qh = mpn_cmp (np - dn, dp, dn) >= 0; |
71 | 0 | if (qh != 0) |
72 | 0 | mpn_sub_n (np - dn, np - dn, dp, dn); |
73 | |
|
74 | 0 | qp += qn; |
75 | |
|
76 | 0 | dn -= 2; /* offset dn by 2 for main division loops, |
77 | | saving two iterations in mpn_submul_1. */ |
78 | 0 | d1 = dp[dn + 1]; |
79 | 0 | d0 = dp[dn + 0]; |
80 | |
|
81 | 0 | np -= 2; |
82 | |
|
83 | 0 | n1 = np[1]; |
84 | |
|
85 | 0 | for (i = qn - (dn + 2); i >= 0; i--) |
86 | 0 | { |
87 | 0 | np--; |
88 | 0 | if (UNLIKELY (n1 == d1) && np[1] == d0) |
89 | 0 | { |
90 | 0 | q = GMP_NUMB_MASK; |
91 | 0 | mpn_submul_1 (np - dn, dp, dn + 2, q); |
92 | 0 | n1 = np[1]; /* update n1, last loop's value will now be invalid */ |
93 | 0 | } |
94 | 0 | else |
95 | 0 | { |
96 | 0 | udiv_qr_3by2 (q, n1, n0, n1, np[1], np[0], d1, d0, dinv); |
97 | |
|
98 | 0 | cy = mpn_submul_1 (np - dn, dp, dn, q); |
99 | |
|
100 | 0 | cy1 = n0 < cy; |
101 | 0 | n0 = (n0 - cy) & GMP_NUMB_MASK; |
102 | 0 | cy = n1 < cy1; |
103 | 0 | n1 -= cy1; |
104 | 0 | np[0] = n0; |
105 | |
|
106 | 0 | if (UNLIKELY (cy != 0)) |
107 | 0 | { |
108 | 0 | n1 += d1 + mpn_add_n (np - dn, np - dn, dp, dn + 1); |
109 | 0 | q--; |
110 | 0 | } |
111 | 0 | } |
112 | |
|
113 | 0 | *--qp = q; |
114 | 0 | } |
115 | |
|
116 | 0 | flag = ~CNST_LIMB(0); |
117 | |
|
118 | 0 | if (dn >= 0) |
119 | 0 | { |
120 | 0 | for (i = dn; i > 0; i--) |
121 | 0 | { |
122 | 0 | np--; |
123 | 0 | if (UNLIKELY (n1 >= (d1 & flag))) |
124 | 0 | { |
125 | 0 | q = GMP_NUMB_MASK; |
126 | 0 | cy = mpn_submul_1 (np - dn, dp, dn + 2, q); |
127 | |
|
128 | 0 | if (UNLIKELY (n1 != cy)) |
129 | 0 | { |
130 | 0 | if (n1 < (cy & flag)) |
131 | 0 | { |
132 | 0 | q--; |
133 | 0 | mpn_add_n (np - dn, np - dn, dp, dn + 2); |
134 | 0 | } |
135 | 0 | else |
136 | 0 | flag = 0; |
137 | 0 | } |
138 | 0 | n1 = np[1]; |
139 | 0 | } |
140 | 0 | else |
141 | 0 | { |
142 | 0 | udiv_qr_3by2 (q, n1, n0, n1, np[1], np[0], d1, d0, dinv); |
143 | |
|
144 | 0 | cy = mpn_submul_1 (np - dn, dp, dn, q); |
145 | |
|
146 | 0 | cy1 = n0 < cy; |
147 | 0 | n0 = (n0 - cy) & GMP_NUMB_MASK; |
148 | 0 | cy = n1 < cy1; |
149 | 0 | n1 -= cy1; |
150 | 0 | np[0] = n0; |
151 | |
|
152 | 0 | if (UNLIKELY (cy != 0)) |
153 | 0 | { |
154 | 0 | n1 += d1 + mpn_add_n (np - dn, np - dn, dp, dn + 1); |
155 | 0 | q--; |
156 | 0 | } |
157 | 0 | } |
158 | |
|
159 | 0 | *--qp = q; |
160 | | |
161 | | /* Truncate operands. */ |
162 | 0 | dn--; |
163 | 0 | dp++; |
164 | 0 | } |
165 | |
|
166 | 0 | np--; |
167 | 0 | if (UNLIKELY (n1 >= (d1 & flag))) |
168 | 0 | { |
169 | 0 | q = GMP_NUMB_MASK; |
170 | 0 | cy = mpn_submul_1 (np, dp, 2, q); |
171 | |
|
172 | 0 | if (UNLIKELY (n1 != cy)) |
173 | 0 | { |
174 | 0 | if (n1 < (cy & flag)) |
175 | 0 | { |
176 | 0 | q--; |
177 | 0 | add_ssaaaa (np[1], np[0], np[1], np[0], dp[1], dp[0]); |
178 | 0 | } |
179 | 0 | else |
180 | 0 | flag = 0; |
181 | 0 | } |
182 | 0 | n1 = np[1]; |
183 | 0 | } |
184 | 0 | else |
185 | 0 | { |
186 | 0 | udiv_qr_3by2 (q, n1, n0, n1, np[1], np[0], d1, d0, dinv); |
187 | |
|
188 | 0 | np[1] = n1; |
189 | 0 | np[0] = n0; |
190 | 0 | } |
191 | |
|
192 | 0 | *--qp = q; |
193 | 0 | } |
194 | |
|
195 | 0 | ASSERT_ALWAYS (np[1] == n1); |
196 | | |
197 | 0 | return qh; |
198 | 0 | } |