]>
Commit | Line | Data |
---|---|---|
2ef2b01e A |
1 | /** @file |
2 | Compiler intrinsic for 64-bit compare, ported from LLVM code. | |
3 | ||
4 | Copyright (c) 2008-2009, Apple Inc. All rights reserved. | |
5 | ||
6 | All rights reserved. This program and the accompanying materials | |
7 | are licensed and made available under the terms and conditions of the BSD License | |
8 | which accompanies this distribution. The full text of the license may be found at | |
9 | http://opensource.org/licenses/bsd-license.php | |
10 | ||
11 | THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, | |
12 | WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. | |
13 | ||
14 | **/ | |
15 | /** | |
16 | University of Illinois/NCSA | |
17 | Open Source License | |
18 | ||
19 | Copyright (c) 2003-2008 University of Illinois at Urbana-Champaign. | |
20 | All rights reserved. | |
21 | ||
22 | Developed by: | |
23 | ||
24 | LLVM Team | |
25 | ||
26 | University of Illinois at Urbana-Champaign | |
27 | ||
28 | http://llvm.org | |
29 | ||
30 | Permission is hereby granted, free of charge, to any person obtaining a copy of | |
31 | this software and associated documentation files (the "Software"), to deal with | |
32 | the Software without restriction, including without limitation the rights to | |
33 | use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies | |
34 | of the Software, and to permit persons to whom the Software is furnished to do | |
35 | so, subject to the following conditions: | |
36 | ||
37 | * Redistributions of source code must retain the above copyright notice, | |
38 | this list of conditions and the following disclaimers. | |
39 | ||
40 | * Redistributions in binary form must reproduce the above copyright notice, | |
41 | this list of conditions and the following disclaimers in the | |
42 | documentation and/or other materials provided with the distribution. | |
43 | ||
44 | * Neither the names of the LLVM Team, University of Illinois at | |
45 | Urbana-Champaign, nor the names of its contributors may be used to | |
46 | endorse or promote products derived from this Software without specific | |
47 | prior written permission. | |
48 | ||
49 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
50 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS | |
51 | FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
52 | CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
53 | LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
54 | OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE | |
55 | SOFTWARE. | |
56 | **/ | |
57 | ||
58 | ||
59 | #include "Llvm_int_lib.h" | |
60 | ||
61 | // Effects: if rem != 0, *rem = a % b | |
62 | // Returns: a / b | |
63 | ||
64 | // Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide | |
65 | ||
66 | UINT64 | |
67 | __udivmoddi4 (UINT64 a, UINT64 b, UINT64* rem) | |
68 | { | |
69 | const unsigned n_uword_bits = sizeof(UINT32) * CHAR_BIT; | |
70 | const unsigned n_udword_bits = sizeof(UINT64) * CHAR_BIT; | |
71 | udwords n; | |
72 | n.all = a; | |
73 | udwords d; | |
74 | d.all = b; | |
75 | udwords q; | |
76 | udwords r; | |
77 | unsigned sr; | |
78 | ||
79 | if (b == 0) { | |
80 | // ASSERT (FALSE); | |
81 | return 0; | |
82 | } | |
83 | ||
84 | // special cases, X is unknown, K != 0 | |
85 | if (n.high == 0) | |
86 | { | |
87 | if (d.high == 0) | |
88 | { | |
89 | // 0 X | |
90 | // --- | |
91 | // 0 X | |
92 | if (rem) | |
93 | *rem = n.low % d.low; | |
94 | return n.low / d.low; | |
95 | } | |
96 | // 0 X | |
97 | // --- | |
98 | // K X | |
99 | if (rem) | |
100 | *rem = n.low; | |
101 | return 0; | |
102 | } | |
103 | // n.high != 0 | |
104 | if (d.low == 0) | |
105 | { | |
106 | if (d.high == 0) | |
107 | { | |
108 | // K X | |
109 | // --- | |
110 | // 0 0 | |
111 | if (rem) | |
112 | *rem = n.high % d.low; | |
113 | return n.high / d.low; | |
114 | } | |
115 | // d.high != 0 | |
116 | if (n.low == 0) | |
117 | { | |
118 | // K 0 | |
119 | // --- | |
120 | // K 0 | |
121 | if (rem) | |
122 | { | |
123 | r.high = n.high % d.high; | |
124 | r.low = 0; | |
125 | *rem = r.all; | |
126 | } | |
127 | return n.high / d.high; | |
128 | } | |
129 | // K K | |
130 | // --- | |
131 | // K 0 | |
132 | if ((d.high & (d.high - 1)) == 0) // if d is a power of 2 | |
133 | { | |
134 | if (rem) | |
135 | { | |
136 | r.low = n.low; | |
137 | r.high = n.high & (d.high - 1); | |
138 | *rem = r.all; | |
139 | } | |
140 | return n.high >> COUNT_TRAILING_ZEROS(d.high); | |
141 | } | |
142 | // K K | |
143 | // --- | |
144 | // K 0 | |
145 | sr = COUNT_LEADING_ZEROS(d.high) - COUNT_LEADING_ZEROS(n.high); | |
146 | // 0 <= sr <= n_uword_bits - 2 or sr large | |
147 | if (sr > n_uword_bits - 2) | |
148 | { | |
149 | if (rem) | |
150 | *rem = n.all; | |
151 | return 0; | |
152 | } | |
153 | ++sr; | |
154 | // 1 <= sr <= n_uword_bits - 1 | |
155 | // q.all = n.all << (n_udword_bits - sr); | |
156 | q.low = 0; | |
157 | q.high = n.low << (n_uword_bits - sr); | |
158 | // r.all = n.all >> sr; | |
159 | r.high = n.high >> sr; | |
160 | r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr); | |
161 | } | |
162 | else // d.low != 0 | |
163 | { | |
164 | if (d.high == 0) | |
165 | { | |
166 | // K X | |
167 | // --- | |
168 | // 0 K | |
169 | if ((d.low & (d.low - 1)) == 0) // if d is a power of 2 | |
170 | { | |
171 | if (rem) | |
172 | *rem = n.low & (d.low - 1); | |
173 | if (d.low == 1) | |
174 | return n.all; | |
175 | unsigned sr = COUNT_TRAILING_ZEROS(d.low); | |
176 | q.high = n.high >> sr; | |
177 | q.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr); | |
178 | return q.all; | |
179 | } | |
180 | // K X | |
181 | // --- | |
182 | // 0 K | |
183 | sr = 1 + n_uword_bits + COUNT_LEADING_ZEROS(d.low) - COUNT_LEADING_ZEROS(n.high); | |
184 | // 2 <= sr <= n_udword_bits - 1 | |
185 | // q.all = n.all << (n_udword_bits - sr); | |
186 | // r.all = n.all >> sr; | |
187 | // if (sr == n_uword_bits) | |
188 | // { | |
189 | // q.low = 0; | |
190 | // q.high = n.low; | |
191 | // r.high = 0; | |
192 | // r.low = n.high; | |
193 | // } | |
194 | // else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1 | |
195 | // { | |
196 | // q.low = 0; | |
197 | // q.high = n.low << (n_uword_bits - sr); | |
198 | // r.high = n.high >> sr; | |
199 | // r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr); | |
200 | // } | |
201 | // else // n_uword_bits + 1 <= sr <= n_udword_bits - 1 | |
202 | // { | |
203 | // q.low = n.low << (n_udword_bits - sr); | |
204 | // q.high = (n.high << (n_udword_bits - sr)) | | |
205 | // (n.low >> (sr - n_uword_bits)); | |
206 | // r.high = 0; | |
207 | // r.low = n.high >> (sr - n_uword_bits); | |
208 | // } | |
209 | q.low = (n.low << (n_udword_bits - sr)) & | |
210 | ((INT32)(n_uword_bits - sr) >> (n_uword_bits-1)); | |
211 | q.high = ((n.low << ( n_uword_bits - sr)) & | |
212 | ((INT32)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) | | |
213 | (((n.high << (n_udword_bits - sr)) | | |
214 | (n.low >> (sr - n_uword_bits))) & | |
215 | ((INT32)(n_uword_bits - sr) >> (n_uword_bits-1))); | |
216 | r.high = (n.high >> sr) & | |
217 | ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1)); | |
218 | r.low = ((n.high >> (sr - n_uword_bits)) & | |
219 | ((INT32)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) | | |
220 | (((n.high << (n_uword_bits - sr)) | | |
221 | (n.low >> sr)) & | |
222 | ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1))); | |
223 | } | |
224 | else | |
225 | { | |
226 | // K X | |
227 | // --- | |
228 | // K K | |
229 | sr = COUNT_LEADING_ZEROS(d.high) - COUNT_LEADING_ZEROS(n.high); | |
230 | // 0 <= sr <= n_uword_bits - 1 or sr large | |
231 | if (sr > n_uword_bits - 1) | |
232 | { | |
233 | if (rem) | |
234 | *rem = n.all; | |
235 | return 0; | |
236 | } | |
237 | ++sr; | |
238 | // 1 <= sr <= n_uword_bits | |
239 | // q.all = n.all << (n_udword_bits - sr); | |
240 | q.low = 0; | |
241 | q.high = n.low << (n_uword_bits - sr); | |
242 | // r.all = n.all >> sr; | |
243 | // if (sr < n_uword_bits) | |
244 | // { | |
245 | // r.high = n.high >> sr; | |
246 | // r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr); | |
247 | // } | |
248 | // else | |
249 | // { | |
250 | // r.high = 0; | |
251 | // r.low = n.high; | |
252 | // } | |
253 | r.high = (n.high >> sr) & | |
254 | ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1)); | |
255 | r.low = (n.high << (n_uword_bits - sr)) | | |
256 | ((n.low >> sr) & | |
257 | ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1))); | |
258 | } | |
259 | } | |
260 | // Not a special case | |
261 | // q and r are initialized with: | |
262 | // q.all = n.all << (n_udword_bits - sr); | |
263 | // r.all = n.all >> sr; | |
264 | // 1 <= sr <= n_udword_bits - 1 | |
265 | UINT32 carry = 0; | |
266 | for (; sr > 0; --sr) | |
267 | { | |
268 | // r:q = ((r:q) << 1) | carry | |
269 | r.high = (r.high << 1) | (r.low >> (n_uword_bits - 1)); | |
270 | r.low = (r.low << 1) | (q.high >> (n_uword_bits - 1)); | |
271 | q.high = (q.high << 1) | (q.low >> (n_uword_bits - 1)); | |
272 | q.low = (q.low << 1) | carry; | |
273 | // carry = 0; | |
274 | // if (r.all >= d.all) | |
275 | // { | |
276 | // r.all -= d.all; | |
277 | // carry = 1; | |
278 | // } | |
279 | const INT64 s = (INT64)(d.all - r.all - 1) >> (n_udword_bits - 1); | |
280 | carry = s & 1; | |
281 | r.all -= d.all & s; | |
282 | } | |
283 | q.all = (q.all << 1) | carry; | |
284 | if (rem) | |
285 | *rem = r.all; | |
286 | return q.all; | |
287 | } |