/src/libgmp/mpn/bdiv_qr.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* mpn_bdiv_qr -- Hensel division with precomputed inverse, returning quotient |
2 | | and remainder. |
3 | | |
4 | | Contributed to the GNU project by Torbjorn Granlund. |
5 | | |
6 | | THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES. IT IS ONLY |
7 | | SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST |
8 | | GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE. |
9 | | |
10 | | Copyright 2006, 2007, 2009, 2012 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 | | |
41 | | /* Computes Q = N / D mod B^n, |
42 | | R = N - QD. */ |
43 | | |
44 | | mp_limb_t |
45 | | mpn_bdiv_qr (mp_ptr qp, mp_ptr rp, |
46 | | mp_srcptr np, mp_size_t nn, |
47 | | mp_srcptr dp, mp_size_t dn, |
48 | | mp_ptr tp) |
49 | 1.72k | { |
50 | 1.72k | mp_limb_t di; |
51 | 1.72k | mp_limb_t rh; |
52 | | |
53 | 1.72k | ASSERT (nn > dn); |
54 | 1.72k | if (BELOW_THRESHOLD (dn, DC_BDIV_QR_THRESHOLD) || |
55 | 1.72k | BELOW_THRESHOLD (nn - dn, DC_BDIV_QR_THRESHOLD)) |
56 | 1.72k | { |
57 | 1.72k | MPN_COPY (tp, np, nn); |
58 | 1.72k | binvert_limb (di, dp[0]); di = -di; |
59 | 1.72k | rh = mpn_sbpi1_bdiv_qr (qp, tp, nn, dp, dn, di); |
60 | 1.72k | MPN_COPY (rp, tp + nn - dn, dn); |
61 | 1.72k | } |
62 | 0 | else if (BELOW_THRESHOLD (dn, MU_BDIV_QR_THRESHOLD)) |
63 | 0 | { |
64 | 0 | MPN_COPY (tp, np, nn); |
65 | 0 | binvert_limb (di, dp[0]); di = -di; |
66 | 0 | rh = mpn_dcpi1_bdiv_qr (qp, tp, nn, dp, dn, di); |
67 | 0 | MPN_COPY (rp, tp + nn - dn, dn); |
68 | 0 | } |
69 | 0 | else |
70 | 0 | { |
71 | 0 | rh = mpn_mu_bdiv_qr (qp, rp, np, nn, dp, dn, tp); |
72 | 0 | } |
73 | | |
74 | 1.72k | return rh; |
75 | 1.72k | } |
76 | | |
77 | | mp_size_t |
78 | | mpn_bdiv_qr_itch (mp_size_t nn, mp_size_t dn) |
79 | 1.72k | { |
80 | 1.72k | if (BELOW_THRESHOLD (dn, MU_BDIV_QR_THRESHOLD)) |
81 | 1.72k | return nn; |
82 | 0 | else |
83 | 0 | return mpn_mu_bdiv_qr_itch (nn, dn); |
84 | 1.72k | } |