3 /* On x86, division of one 64-bit integer by another cannot be
4 done with a single instruction or a short sequence. Thus, GCC
5 implements 64-bit division and remainder operations through
6 function calls. These functions are normally obtained from
7 libgcc, which is automatically included by GCC in any link
10 Some x86-64 machines, however, have a compiler and utilities
11 that can generate 32-bit x86 code without having any of the
12 necessary libraries, including libgcc. Thus, we can make
13 Pintos work on these machines by simply implementing our own
14 64-bit division routines, which are the only routines from
15 libgcc that Pintos requires.
17 Completeness is another reason to include these routines. If
18 Pintos is completely self-contained, then that makes it that
19 much less mysterious. */
21 /* Uses x86 DIVL instruction to divide 64-bit N by 32-bit D to
22 yield a 32-bit quotient. Returns the quotient.
23 Traps with a divide error (#DE) if the quotient does not fit
25 static inline uint32_t
26 divl (uint64_t n, uint32_t d)
28 uint32_t n1 = n >> 32;
34 : "0" (n1), "1" (n0), "rm" (d));
39 /* Returns the number of leading zero bits in X,
40 which must be nonzero. */
44 /* This technique is portable, but there are better ways to do
45 it on particular systems. With sufficiently new enough GCC,
46 you can use __builtin_clz() to take advantage of GCC's
47 knowledge of how to do it. Or you can use the x86 BSR
48 instruction directly. */
75 /* Divides unsigned 64-bit N by unsigned 64-bit D and returns the
78 udiv64 (uint64_t n, uint64_t d)
82 /* Proof of correctness:
84 Let n, d, b, n1, and n0 be defined as in this function.
85 Let [x] be the "floor" of x. Let T = b[n1/d]. Assume d
88 = [n/d - T] + T by (1) below
89 = [(b*n1 + n0)/d - T] + T by definition of n
90 = [(b*n1 + n0)/d - dT/d] + T
91 = [(b(n1 - d[n1/d]) + n0)/d] + T
92 = [(b[n1 % d] + n0)/d] + T, by definition of %
93 which is the expression calculated below.
95 (1) Note that for any real x, integer i: [x] + i = [x + i].
97 To prevent divl() from trapping, [(b[n1 % d] + n0)/d] must
98 be less than b. Assume that [n1 % d] and n0 take their
99 respective maximum values of d - 1 and b - 1:
100 [(b(d - 1) + (b - 1))/d] < b
103 which is a tautology.
105 Therefore, this code is correct and will not trap. */
106 uint64_t b = 1ULL << 32;
107 uint32_t n1 = n >> 32;
111 return divl (b * (n1 % d0) + n0, d0) + b * (n1 / d0);
115 /* Based on the algorithm and proof available from
116 http://www.hackersdelight.org/revisions.pdf. */
121 uint32_t d1 = d >> 32;
123 uint64_t q = divl (n >> 1, (d << s) >> 32) >> (31 - s);
124 return n - (q - 1) * d < d ? q - 1 : q;
129 /* Divides unsigned 64-bit N by unsigned 64-bit D and returns the
132 umod64 (uint64_t n, uint64_t d)
134 return n - d * udiv64 (n, d);
137 /* Divides signed 64-bit N by signed 64-bit D and returns the
140 sdiv64 (int64_t n, int64_t d)
142 uint64_t n_abs = n >= 0 ? (uint64_t) n : -(uint64_t) n;
143 uint64_t d_abs = d >= 0 ? (uint64_t) d : -(uint64_t) d;
144 uint64_t q_abs = udiv64 (n_abs, d_abs);
145 return (n < 0) == (d < 0) ? (int64_t) q_abs : -(int64_t) q_abs;
148 /* Divides signed 64-bit N by signed 64-bit D and returns the
151 smod64 (int64_t n, int64_t d)
153 return n - d * sdiv64 (n, d);
156 /* These are the routines that GCC calls. */
158 long long __divdi3 (long long n, long long d);
159 long long __moddi3 (long long n, long long d);
160 unsigned long long __udivdi3 (unsigned long long n, unsigned long long d);
161 unsigned long long __umoddi3 (unsigned long long n, unsigned long long d);
163 /* Signed 64-bit division. */
165 __divdi3 (long long n, long long d)
167 return sdiv64 (n, d);
170 /* Signed 64-bit remainder. */
172 __moddi3 (long long n, long long d)
174 return smod64 (n, d);
177 /* Unsigned 64-bit division. */
179 __udivdi3 (unsigned long long n, unsigned long long d)
181 return udiv64 (n, d);
184 /* Unsigned 64-bit remainder. */
186 __umoddi3 (unsigned long long n, unsigned long long d)
188 return umod64 (n, d);