Line data Source code
1 : #line 2 "../src/kernel/none/divll.h"
2 : /* Copyright (C) 2003 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 : /* This file originally adapted from gmp-3.1.1 (from T. Granlund), files
17 : * longlong.h and gmp-impl.h
18 :
19 : Copyright (C) 2000 Free Software Foundation, Inc. */
20 :
21 : #undef LOCAL_HIREMAINDER
22 : #define LOCAL_HIREMAINDER
23 : extern ulong hiremainder;
24 :
25 : #if !defined(INLINE)
26 : extern long divll(ulong x, ulong y);
27 : #else
28 :
29 : #define __GLUE(hi, lo) (((hi) << BITS_IN_HALFULONG) | (lo))
30 : #define __SPLIT(a, b, c) b = HIGHWORD(a); c = LOWWORD(a)
31 : #define __LDIV(a, b, q, r) q = a / b; r = a - q*b
32 : extern ulong hiremainder;
33 :
34 : /* divide (hiremainder * 2^BITS_IN_LONG + n0) by d; assume hiremainder < d.
35 : * Return quotient, set hiremainder to remainder */
36 :
37 : #if defined(__GNUC__) && !defined(DISABLE_INLINE)
38 : #undef LOCAL_HIREMAINDER
39 : #define LOCAL_HIREMAINDER ulong hiremainder
40 :
41 : #define divll(n0, d) \
42 : __extension__ ({ \
43 : ulong __d1, __d0, __q1, __q0, __r1, __r0, __m, __n1, __n0; \
44 : ulong __k, __d; \
45 : \
46 : __n1 = hiremainder; __n0 = n0; __d = d; \
47 : if (__n1 == 0) \
48 : { /* Only one division needed */ \
49 : __LDIV(__n0, __d, __q1, hiremainder); \
50 : } \
51 : else if (__d < LOWMASK) \
52 : { /* Two half-word divisions */ \
53 : __n1 = __GLUE(__n1, HIGHWORD(__n0)); \
54 : __LDIV(__n1, __d, __q1, __r1); \
55 : __n1 = __GLUE(__r1, LOWWORD(__n0)); \
56 : __LDIV(__n1, __d, __q0, hiremainder); \
57 : __q1 = __GLUE(__q1, __q0); \
58 : } \
59 : else \
60 : { /* General case */ \
61 : if (__d & HIGHBIT) \
62 : { \
63 : __k = 0; __SPLIT(__d, __d1, __d0); \
64 : } \
65 : else \
66 : { \
67 : __k = bfffo(__d); \
68 : __n1 = (__n1 << __k) | (__n0 >> (BITS_IN_LONG - __k)); \
69 : __n0 <<= __k; \
70 : __d = __d << __k; __SPLIT(__d, __d1, __d0); \
71 : } \
72 : __LDIV(__n1, __d1, __q1, __r1); \
73 : __m = __q1 * __d0; \
74 : __r1 = __GLUE(__r1, HIGHWORD(__n0)); \
75 : if (__r1 < __m) \
76 : { \
77 : __q1--, __r1 += __d; \
78 : if (__r1 >= __d) /* we didn't get carry when adding to __r1 */ \
79 : if (__r1 < __m) __q1--, __r1 += __d; \
80 : } \
81 : __r1 -= __m; \
82 : __LDIV(__r1, __d1, __q0, __r0); \
83 : __m = __q0 * __d0; \
84 : __r0 = __GLUE(__r0, LOWWORD(__n0)); \
85 : if (__r0 < __m) \
86 : { \
87 : __q0--, __r0 += __d; \
88 : if (__r0 >= __d) \
89 : if (__r0 < __m) __q0--, __r0 += __d; \
90 : } \
91 : hiremainder = (__r0 - __m) >> __k; \
92 : __q1 = __GLUE(__q1, __q0); \
93 : } \
94 : __q1; \
95 : })
96 :
97 : #else /* __GNUC__ */
98 :
99 : INLINE long
100 1621302408 : divll(ulong n0, ulong d)
101 : {
102 : ulong __d1, __d0, __q1, __q0, __r1, __r0, __m, __n1, __n0;
103 : ulong __k, __d;
104 :
105 1621302408 : __n1 = hiremainder; __n0 = n0; __d = d;
106 :
107 1621302408 : if (__n1 == 0)
108 : { /* Only one division needed */
109 844045052 : __LDIV(__n0, __d, __q1, hiremainder);
110 : }
111 777257356 : else if (__d < LOWMASK)
112 : { /* Two half-word divisions */
113 26109957 : __n1 = __GLUE(__n1, HIGHWORD(__n0));
114 26109957 : __LDIV(__n1, __d, __q1, __r1);
115 26109957 : __n1 = __GLUE(__r1, LOWWORD(__n0));
116 26109957 : __LDIV(__n1, __d, __q0, hiremainder);
117 26109957 : __q1 = __GLUE(__q1, __q0);
118 : }
119 : else
120 : { /* General case */
121 751147399 : if (__d & HIGHBIT)
122 : {
123 733700679 : __k = 0; __SPLIT(__d, __d1, __d0);
124 : }
125 : else
126 : {
127 17446720 : __k = bfffo(__d);
128 17446720 : __n1 = (__n1 << __k) | (__n0 >> (BITS_IN_LONG - __k));
129 17446720 : __n0 = __n0 << __k;
130 17446720 : __d = __d << __k; __SPLIT(__d, __d1, __d0);
131 : }
132 751147399 : __LDIV(__n1, __d1, __q1, __r1);
133 751147399 : __m = __q1 * __d0;
134 751147399 : __r1 = __GLUE(__r1, HIGHWORD(__n0));
135 751147399 : if (__r1 < __m)
136 : {
137 135693889 : __q1--, __r1 += __d;
138 135693889 : if (__r1 >= __d) /* we didn't get carry when adding to __r1 */
139 110250525 : if (__r1 < __m) __q1--, __r1 += __d;
140 : }
141 751147399 : __r1 -= __m;
142 751147399 : __LDIV(__r1, __d1, __q0, __r0);
143 751147399 : __m = __q0 * __d0;
144 751147399 : __r0 = __GLUE(__r0, LOWWORD(__n0));
145 751147399 : if (__r0 < __m)
146 : {
147 134769627 : __q0--, __r0 += __d;
148 134769627 : if (__r0 >= __d)
149 98965837 : if (__r0 < __m) __q0--, __r0 += __d;
150 : }
151 751147399 : hiremainder = (__r0 - __m) >> __k;
152 751147399 : __q1 = __GLUE(__q1, __q0);
153 : }
154 1621302408 : return __q1;
155 : }
156 :
157 : #endif /* __GNUC__ */
158 :
159 : #endif
|
