Line data Source code
1 : #line 2 "../src/kernel/none/divll_pre.h"
2 : /* Copyright (C) 2014 The PARI group.
3 :
4 : This file is part of the PARI/GP package.
5 :
6 : PARI/GP is free software; you can redistribute it and/or modify it under the
7 : terms of the GNU General Public License as published by the Free Software
8 : Foundation; either version 2 of the License, or (at your option) any later
9 : version. It is distributed in the hope that it will be useful, but WITHOUT
10 : ANY WARRANTY WHATSOEVER.
11 :
12 : Check the License for details. You should have received a copy of it, along
13 : with the package; see the file 'COPYING'. If not, write to the Free Software
14 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
15 :
16 : #undef LOCAL_HIREMAINDER
17 : extern ulong hiremainder;
18 : #if defined(INLINE) && defined(__GNUC__) && !defined(DISABLE_INLINE)
19 : #define LOCAL_HIREMAINDER ulong hiremainder
20 : #else
21 : #define LOCAL_HIREMAINDER
22 : #endif
23 :
24 : #if defined(INLINE) && defined(__GNUC__) && !defined(DISABLE_INLINE)
25 : INLINE ulong /* precompute inverse of n */
26 1531909970 : get_Fl_red(ulong n)
27 : {
28 : LOCAL_HIREMAINDER;
29 1531909970 : n <<= bfffo(n);
30 1531909970 : hiremainder = ~n;
31 1531909970 : return divll(~0UL, n);
32 : }
33 : #else
34 : INLINE ulong /* precompute inverse of n */
35 473487600 : get_Fl_red(ulong n)
36 : {
37 473487600 : ulong q, oldhi = hiremainder;
38 473487600 : n <<= bfffo(n);
39 473487600 : hiremainder = ~n;
40 473487600 : q = divll(~0UL, n);
41 473487600 : hiremainder = oldhi;
42 473487600 : return q;
43 : }
44 : #endif
45 :
46 : INLINE ulong /* requires u1 <= n, n normalised */
47 11006919587 : divll_pre_normalized(ulong u1, ulong u0, ulong n, ulong ninv, ulong *pt_r)
48 : {
49 : ulong q0, q1, r;
50 : LOCAL_HIREMAINDER;
51 : LOCAL_OVERFLOW;
52 11006919587 : q0 = mulll(ninv, u1); q1 = hiremainder;
53 11006919587 : q0 = addll(q0, u0);
54 11006919587 : q1 = addllx(q1+1, u1);
55 11006919587 : r = u0 - q1 * n;
56 11006919587 : if (r > q0)
57 : {
58 7475992683 : r += n; q1--;
59 : }
60 11006919587 : if (r >= n)
61 : {
62 22159935 : r -= n; q1++;
63 : }
64 11006919587 : *pt_r = r; return q1;
65 : }
66 :
67 : INLINE ulong /* requires u1 <= n, n normalised */
68 15540739905 : remll_pre_normalized(ulong u1, ulong u0, ulong n, ulong ninv)
69 : {
70 : ulong q0, q1, r;
71 : LOCAL_HIREMAINDER;
72 : LOCAL_OVERFLOW;
73 15540739905 : q0 = mulll(ninv, u1); q1 = hiremainder;
74 15540739905 : q0 = addll(q0, u0);
75 15540739905 : q1 = addllx(q1, u1);
76 15540739905 : r = u0 - (q1 + 1) * n;
77 15540739905 : if (r >= q0)
78 11064563136 : r += n;
79 15540739905 : return r < n ? r : r - n;
80 : }
81 :
82 : INLINE ulong /* reduce <a_hi, a_lo> mod n */
83 15447762417 : remll_pre(ulong a_hi, ulong a_lo, ulong n, ulong ninv)
84 : {
85 15447762417 : int norm = bfffo(n);
86 15447762417 : int bits = BITS_IN_LONG - norm;
87 15447762417 : ulong sn = n << norm;
88 15447762417 : if (a_hi >= n) /* reduce a_hi first */
89 : {
90 77101589 : const ulong u1 = norm ? a_hi >> bits : 0;
91 77101589 : const ulong u0 = a_hi << norm;
92 77101589 : a_hi = remll_pre_normalized(u1, u0, sn, ninv) >> norm;
93 : }
94 : /* now reduce <a_hi, a_lo> */
95 : {
96 15447800137 : const ulong u1 = ((a_hi << norm) | (norm ? a_lo >> bits: 0));
97 15447800137 : const ulong u0 = a_lo << norm;
98 15447800137 : return remll_pre_normalized(u1, u0, sn, ninv) >> norm;
99 : }
100 : }
101 :
102 : #if !defined(INLINE)
103 : extern ulong divll_pre(ulong a_lo, ulong n, ulong ninv);
104 : #else
105 :
106 : #if defined(__GNUC__) && !defined(DISABLE_INLINE)
107 : #define divll_pre(a, n, ninv) \
108 : __extension__ ({ \
109 : ulong __a = (a); \
110 : ulong __n = (n); \
111 : int norm = bfffo(__n); \
112 : int bits = BITS_IN_LONG - norm; \
113 : ulong r, sn = __n << norm; \
114 : const ulong u1 = ((hiremainder << norm) | (norm ? __a >> bits: 0)); \
115 : const ulong u0 = __a << norm; \
116 : const ulong q = divll_pre_normalized(u1, u0, sn, ninv, &r); \
117 : hiremainder = r>>norm; q; \
118 : })
119 :
120 : #else /* __GNUC__ */
121 : INLINE ulong
122 2163367907 : divll_pre(ulong a_lo, ulong n, ulong ninv)
123 : {
124 2163367907 : int norm = bfffo(n);
125 2163367907 : int bits = BITS_IN_LONG - norm;
126 2163367907 : ulong r, sn = n << norm;
127 2163367907 : const ulong u1 = ((hiremainder << norm) | (norm ? a_lo >> bits: 0));
128 2163367907 : const ulong u0 = a_lo << norm;
129 2163367907 : const ulong q = divll_pre_normalized(u1, u0, sn, ninv, &r);
130 2163367907 : hiremainder = r>>norm; return q;
131 : }
132 : #endif /* __GNUC__ */
133 :
134 : #endif
|
