/root/src/xen/xen/common/lib.c
Line | Count | Source (jump to first uncovered line) |
1 | | |
2 | | #include <xen/ctype.h> |
3 | | #include <xen/lib.h> |
4 | | #include <xen/types.h> |
5 | | #include <xen/init.h> |
6 | | #include <asm/byteorder.h> |
7 | | |
8 | | /* for ctype.h */ |
9 | | const unsigned char _ctype[] = { |
10 | | _C,_C,_C,_C,_C,_C,_C,_C, /* 0-7 */ |
11 | | _C,_C|_S,_C|_S,_C|_S,_C|_S,_C|_S,_C,_C, /* 8-15 */ |
12 | | _C,_C,_C,_C,_C,_C,_C,_C, /* 16-23 */ |
13 | | _C,_C,_C,_C,_C,_C,_C,_C, /* 24-31 */ |
14 | | _S|_SP,_P,_P,_P,_P,_P,_P,_P, /* 32-39 */ |
15 | | _P,_P,_P,_P,_P,_P,_P,_P, /* 40-47 */ |
16 | | _D,_D,_D,_D,_D,_D,_D,_D, /* 48-55 */ |
17 | | _D,_D,_P,_P,_P,_P,_P,_P, /* 56-63 */ |
18 | | _P,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U, /* 64-71 */ |
19 | | _U,_U,_U,_U,_U,_U,_U,_U, /* 72-79 */ |
20 | | _U,_U,_U,_U,_U,_U,_U,_U, /* 80-87 */ |
21 | | _U,_U,_U,_P,_P,_P,_P,_P, /* 88-95 */ |
22 | | _P,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L, /* 96-103 */ |
23 | | _L,_L,_L,_L,_L,_L,_L,_L, /* 104-111 */ |
24 | | _L,_L,_L,_L,_L,_L,_L,_L, /* 112-119 */ |
25 | | _L,_L,_L,_P,_P,_P,_P,_C, /* 120-127 */ |
26 | | 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 128-143 */ |
27 | | 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 144-159 */ |
28 | | _S|_SP,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P, /* 160-175 */ |
29 | | _P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P, /* 176-191 */ |
30 | | _U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U, /* 192-207 */ |
31 | | _U,_U,_U,_U,_U,_U,_U,_P,_U,_U,_U,_U,_U,_U,_U,_L, /* 208-223 */ |
32 | | _L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L, /* 224-239 */ |
33 | | _L,_L,_L,_L,_L,_L,_L,_P,_L,_L,_L,_L,_L,_L,_L,_L}; /* 240-255 */ |
34 | | |
35 | | /* |
36 | | * A couple of 64 bit operations ported from FreeBSD. |
37 | | * The code within the '#if BITS_PER_LONG == 32' block below, and no other |
38 | | * code in this file, is distributed under the following licensing terms |
39 | | * This is the modified '3-clause' BSD license with the obnoxious |
40 | | * advertising clause removed, as permitted by University of California. |
41 | | * |
42 | | * Copyright (c) 1992, 1993 |
43 | | * The Regents of the University of California. All rights reserved. |
44 | | * |
45 | | * This software was developed by the Computer Systems Engineering group |
46 | | * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and |
47 | | * contributed to Berkeley. |
48 | | * |
49 | | * Redistribution and use in source and binary forms, with or without |
50 | | * modification, are permitted provided that the following conditions |
51 | | * are met: |
52 | | * 1. Redistributions of source code must retain the above copyright |
53 | | * notice, this list of conditions and the following disclaimer. |
54 | | * 2. Redistributions in binary form must reproduce the above copyright |
55 | | * notice, this list of conditions and the following disclaimer in the |
56 | | * documentation and/or other materials provided with the distribution. |
57 | | * 3. Neither the name of the University nor the names of its contributors |
58 | | * may be used to endorse or promote products derived from this software |
59 | | * without specific prior written permission. |
60 | | * |
61 | | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
62 | | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
63 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
64 | | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
65 | | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
66 | | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
67 | | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
68 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
69 | | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
70 | | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
71 | | * SUCH DAMAGE. |
72 | | */ |
73 | | #if BITS_PER_LONG == 32 |
74 | | |
75 | | /* |
76 | | * Depending on the desired operation, we view a `long long' (aka quad_t) in |
77 | | * one or more of the following formats. |
78 | | */ |
79 | | union uu { |
80 | | s64 q; /* as a (signed) quad */ |
81 | | s64 uq; /* as an unsigned quad */ |
82 | | long sl[2]; /* as two signed longs */ |
83 | | unsigned long ul[2]; /* as two unsigned longs */ |
84 | | }; |
85 | | |
86 | | #ifdef __BIG_ENDIAN |
87 | | #define _QUAD_HIGHWORD 0 |
88 | | #define _QUAD_LOWWORD 1 |
89 | | #else /* __LITTLE_ENDIAN */ |
90 | | #define _QUAD_HIGHWORD 1 |
91 | | #define _QUAD_LOWWORD 0 |
92 | | #endif |
93 | | |
94 | | /* |
95 | | * Define high and low longwords. |
96 | | */ |
97 | | #define H _QUAD_HIGHWORD |
98 | | #define L _QUAD_LOWWORD |
99 | | |
100 | | /* |
101 | | * Total number of bits in a quad_t and in the pieces that make it up. |
102 | | * These are used for shifting, and also below for halfword extraction |
103 | | * and assembly. |
104 | | */ |
105 | | #define CHAR_BIT 8 /* number of bits in a char */ |
106 | | #define QUAD_BITS (sizeof(s64) * CHAR_BIT) |
107 | | #define LONG_BITS (sizeof(long) * CHAR_BIT) |
108 | | #define HALF_BITS (sizeof(long) * CHAR_BIT / 2) |
109 | | |
110 | | /* |
111 | | * Extract high and low shortwords from longword, and move low shortword of |
112 | | * longword to upper half of long, i.e., produce the upper longword of |
113 | | * ((quad_t)(x) << (number_of_bits_in_long/2)). (`x' must actually be |
114 | | * unsigned long.) |
115 | | * |
116 | | * These are used in the multiply code, to split a longword into upper |
117 | | * and lower halves, and to reassemble a product as a quad_t, shifted left |
118 | | * (sizeof(long)*CHAR_BIT/2). |
119 | | */ |
120 | | #define HHALF(x) ((x) >> HALF_BITS) |
121 | | #define LHALF(x) ((x) & ((1 << HALF_BITS) - 1)) |
122 | | #define LHUP(x) ((x) << HALF_BITS) |
123 | | |
124 | | /* |
125 | | * Multiprecision divide. This algorithm is from Knuth vol. 2 (2nd ed), |
126 | | * section 4.3.1, pp. 257--259. |
127 | | */ |
128 | | #define B (1 << HALF_BITS) /* digit base */ |
129 | | |
130 | | /* Combine two `digits' to make a single two-digit number. */ |
131 | | #define COMBINE(a, b) (((unsigned long)(a) << HALF_BITS) | (b)) |
132 | | |
133 | | /* select a type for digits in base B */ |
134 | | typedef unsigned long digit; |
135 | | |
136 | | /* |
137 | | * Shift p[0]..p[len] left `sh' bits, ignoring any bits that |
138 | | * `fall out' the left (there never will be any such anyway). |
139 | | * We may assume len >= 0. NOTE THAT THIS WRITES len+1 DIGITS. |
140 | | */ |
141 | | static void shl(register digit *p, register int len, register int sh) |
142 | | { |
143 | | register int i; |
144 | | |
145 | | for (i = 0; i < len; i++) |
146 | | p[i] = LHALF(p[i] << sh) | (p[i + 1] >> (HALF_BITS - sh)); |
147 | | p[i] = LHALF(p[i] << sh); |
148 | | } |
149 | | |
150 | | /* |
151 | | * __qdivrem(u, v, rem) returns u/v and, optionally, sets *rem to u%v. |
152 | | * |
153 | | * We do this in base 2-sup-HALF_BITS, so that all intermediate products |
154 | | * fit within unsigned long. As a consequence, the maximum length dividend |
155 | | * and divisor are 4 `digits' in this base (they are shorter if they have |
156 | | * leading zeros). |
157 | | */ |
158 | | u64 __qdivrem(u64 uq, u64 vq, u64 *arq) |
159 | | { |
160 | | union uu tmp; |
161 | | digit *u, *v, *q; |
162 | | register digit v1, v2; |
163 | | unsigned long qhat, rhat, t; |
164 | | int m, n, d, j, i; |
165 | | digit uspace[5], vspace[5], qspace[5]; |
166 | | |
167 | | /* |
168 | | * Take care of special cases: divide by zero, and u < v. |
169 | | */ |
170 | | if (vq == 0) { |
171 | | /* divide by zero. */ |
172 | | static volatile const unsigned int zero = 0; |
173 | | |
174 | | tmp.ul[H] = tmp.ul[L] = 1 / zero; |
175 | | if (arq) |
176 | | *arq = uq; |
177 | | return (tmp.q); |
178 | | } |
179 | | if (uq < vq) { |
180 | | if (arq) |
181 | | *arq = uq; |
182 | | return (0); |
183 | | } |
184 | | u = &uspace[0]; |
185 | | v = &vspace[0]; |
186 | | q = &qspace[0]; |
187 | | |
188 | | /* |
189 | | * Break dividend and divisor into digits in base B, then |
190 | | * count leading zeros to determine m and n. When done, we |
191 | | * will have: |
192 | | * u = (u[1]u[2]...u[m+n]) sub B |
193 | | * v = (v[1]v[2]...v[n]) sub B |
194 | | * v[1] != 0 |
195 | | * 1 < n <= 4 (if n = 1, we use a different division algorithm) |
196 | | * m >= 0 (otherwise u < v, which we already checked) |
197 | | * m + n = 4 |
198 | | * and thus |
199 | | * m = 4 - n <= 2 |
200 | | */ |
201 | | tmp.uq = uq; |
202 | | u[0] = 0; |
203 | | u[1] = HHALF(tmp.ul[H]); |
204 | | u[2] = LHALF(tmp.ul[H]); |
205 | | u[3] = HHALF(tmp.ul[L]); |
206 | | u[4] = LHALF(tmp.ul[L]); |
207 | | tmp.uq = vq; |
208 | | v[1] = HHALF(tmp.ul[H]); |
209 | | v[2] = LHALF(tmp.ul[H]); |
210 | | v[3] = HHALF(tmp.ul[L]); |
211 | | v[4] = LHALF(tmp.ul[L]); |
212 | | for (n = 4; v[1] == 0; v++) { |
213 | | if (--n == 1) { |
214 | | unsigned long rbj; /* r*B+u[j] (not root boy jim) */ |
215 | | digit q1, q2, q3, q4; |
216 | | |
217 | | /* |
218 | | * Change of plan, per exercise 16. |
219 | | * r = 0; |
220 | | * for j = 1..4: |
221 | | * q[j] = floor((r*B + u[j]) / v), |
222 | | * r = (r*B + u[j]) % v; |
223 | | * We unroll this completely here. |
224 | | */ |
225 | | t = v[2]; /* nonzero, by definition */ |
226 | | q1 = u[1] / t; |
227 | | rbj = COMBINE(u[1] % t, u[2]); |
228 | | q2 = rbj / t; |
229 | | rbj = COMBINE(rbj % t, u[3]); |
230 | | q3 = rbj / t; |
231 | | rbj = COMBINE(rbj % t, u[4]); |
232 | | q4 = rbj / t; |
233 | | if (arq) |
234 | | *arq = rbj % t; |
235 | | tmp.ul[H] = COMBINE(q1, q2); |
236 | | tmp.ul[L] = COMBINE(q3, q4); |
237 | | return (tmp.q); |
238 | | } |
239 | | } |
240 | | |
241 | | /* |
242 | | * By adjusting q once we determine m, we can guarantee that |
243 | | * there is a complete four-digit quotient at &qspace[1] when |
244 | | * we finally stop. |
245 | | */ |
246 | | for (m = 4 - n; u[1] == 0; u++) |
247 | | m--; |
248 | | for (i = 4 - m; --i >= 0;) |
249 | | q[i] = 0; |
250 | | q += 4 - m; |
251 | | |
252 | | /* |
253 | | * Here we run Program D, translated from MIX to C and acquiring |
254 | | * a few minor changes. |
255 | | * |
256 | | * D1: choose multiplier 1 << d to ensure v[1] >= B/2. |
257 | | */ |
258 | | d = 0; |
259 | | for (t = v[1]; t < B / 2; t <<= 1) |
260 | | d++; |
261 | | if (d > 0) { |
262 | | shl(&u[0], m + n, d); /* u <<= d */ |
263 | | shl(&v[1], n - 1, d); /* v <<= d */ |
264 | | } |
265 | | /* |
266 | | * D2: j = 0. |
267 | | */ |
268 | | j = 0; |
269 | | v1 = v[1]; /* for D3 -- note that v[1..n] are constant */ |
270 | | v2 = v[2]; /* for D3 */ |
271 | | do { |
272 | | register digit uj0, uj1, uj2; |
273 | | |
274 | | /* |
275 | | * D3: Calculate qhat (\^q, in TeX notation). |
276 | | * Let qhat = min((u[j]*B + u[j+1])/v[1], B-1), and |
277 | | * let rhat = (u[j]*B + u[j+1]) mod v[1]. |
278 | | * While rhat < B and v[2]*qhat > rhat*B+u[j+2], |
279 | | * decrement qhat and increase rhat correspondingly. |
280 | | * Note that if rhat >= B, v[2]*qhat < rhat*B. |
281 | | */ |
282 | | uj0 = u[j + 0]; /* for D3 only -- note that u[j+...] change */ |
283 | | uj1 = u[j + 1]; /* for D3 only */ |
284 | | uj2 = u[j + 2]; /* for D3 only */ |
285 | | if (uj0 == v1) { |
286 | | qhat = B; |
287 | | rhat = uj1; |
288 | | goto qhat_too_big; |
289 | | } else { |
290 | | unsigned long nn = COMBINE(uj0, uj1); |
291 | | |
292 | | qhat = nn / v1; |
293 | | rhat = nn % v1; |
294 | | } |
295 | | while (v2 * qhat > COMBINE(rhat, uj2)) { |
296 | | qhat_too_big: |
297 | | qhat--; |
298 | | if ((rhat += v1) >= B) |
299 | | break; |
300 | | } |
301 | | /* |
302 | | * D4: Multiply and subtract. |
303 | | * The variable `t' holds any borrows across the loop. |
304 | | * We split this up so that we do not require v[0] = 0, |
305 | | * and to eliminate a final special case. |
306 | | */ |
307 | | for (t = 0, i = n; i > 0; i--) { |
308 | | t = u[i + j] - v[i] * qhat - t; |
309 | | u[i + j] = LHALF(t); |
310 | | t = (B - HHALF(t)) & (B - 1); |
311 | | } |
312 | | t = u[j] - t; |
313 | | u[j] = LHALF(t); |
314 | | /* |
315 | | * D5: test remainder. |
316 | | * There is a borrow if and only if HHALF(t) is nonzero; |
317 | | * in that (rare) case, qhat was too large (by exactly 1). |
318 | | * Fix it by adding v[1..n] to u[j..j+n]. |
319 | | */ |
320 | | if (HHALF(t)) { |
321 | | qhat--; |
322 | | for (t = 0, i = n; i > 0; i--) { /* D6: add back. */ |
323 | | t += u[i + j] + v[i]; |
324 | | u[i + j] = LHALF(t); |
325 | | t = HHALF(t); |
326 | | } |
327 | | u[j] = LHALF(u[j] + t); |
328 | | } |
329 | | q[j] = qhat; |
330 | | } while (++j <= m); /* D7: loop on j. */ |
331 | | |
332 | | /* |
333 | | * If caller wants the remainder, we have to calculate it as |
334 | | * u[m..m+n] >> d (this is at most n digits and thus fits in |
335 | | * u[m+1..m+n], but we may need more source digits). |
336 | | */ |
337 | | if (arq) { |
338 | | if (d) { |
339 | | for (i = m + n; i > m; --i) |
340 | | u[i] = (u[i] >> d) | |
341 | | LHALF(u[i - 1] << (HALF_BITS - d)); |
342 | | u[i] = 0; |
343 | | } |
344 | | tmp.ul[H] = COMBINE(uspace[1], uspace[2]); |
345 | | tmp.ul[L] = COMBINE(uspace[3], uspace[4]); |
346 | | *arq = tmp.q; |
347 | | } |
348 | | |
349 | | tmp.ul[H] = COMBINE(qspace[1], qspace[2]); |
350 | | tmp.ul[L] = COMBINE(qspace[3], qspace[4]); |
351 | | return (tmp.q); |
352 | | } |
353 | | |
354 | | /* |
355 | | * Divide two signed quads. |
356 | | * Truncates towards zero, as required by C99. |
357 | | */ |
358 | | s64 __divdi3(s64 a, s64 b) |
359 | | { |
360 | | u64 ua, ub, uq; |
361 | | int neg = (a < 0) ^ (b < 0); |
362 | | ua = (a < 0) ? -(u64)a : a; |
363 | | ub = (b < 0) ? -(u64)b : b; |
364 | | uq = __qdivrem(ua, ub, (u64 *)0); |
365 | | return (neg ? -uq : uq); |
366 | | } |
367 | | |
368 | | |
369 | | /* |
370 | | * Divide two unsigned quads. |
371 | | */ |
372 | | u64 __udivdi3(u64 a, u64 b) |
373 | | { |
374 | | return __qdivrem(a, b, (u64 *)0); |
375 | | } |
376 | | |
377 | | /* |
378 | | * Remainder of unsigned quad division |
379 | | */ |
380 | | u64 __umoddi3(u64 a, u64 b) |
381 | | { |
382 | | u64 rem; |
383 | | __qdivrem(a, b, &rem); |
384 | | return rem; |
385 | | } |
386 | | |
387 | | /* |
388 | | * Remainder of signed quad division. |
389 | | * Truncates towards zero, as required by C99: |
390 | | * 11 % 5 = 1 |
391 | | * -11 % 5 = -1 |
392 | | * 11 % -5 = 1 |
393 | | * -11 % -5 = 1 |
394 | | */ |
395 | | s64 __moddi3(s64 a, s64 b) |
396 | | { |
397 | | u64 ua, ub, urem; |
398 | | int neg = (a < 0); |
399 | | ua = neg ? -(u64)a : a; |
400 | | ub = (b < 0) ? -(u64)b : b; |
401 | | __qdivrem(ua, ub, &urem); |
402 | | return (neg ? -urem : urem); |
403 | | } |
404 | | |
405 | | /* |
406 | | * Quotient and remainder of unsigned long long division |
407 | | */ |
408 | | s64 __ldivmod_helper(s64 a, s64 b, s64 *r) |
409 | | { |
410 | | u64 ua, ub, rem, quot; |
411 | | |
412 | | ua = ABS(a); |
413 | | ub = ABS(b); |
414 | | quot = __qdivrem(ua, ub, &rem); |
415 | | if ( a < 0 ) |
416 | | *r = -rem; |
417 | | else |
418 | | *r = rem; |
419 | | if ( (a < 0) ^ (b < 0) ) |
420 | | return -quot; |
421 | | else |
422 | | return quot; |
423 | | } |
424 | | #endif /* BITS_PER_LONG == 32 */ |
425 | | |
426 | | /* Compute with 96 bit intermediate result: (a*b)/c */ |
427 | | uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c) |
428 | 0 | { |
429 | 0 | #ifdef CONFIG_X86 |
430 | 0 | asm ( "mul %%rdx; div %%rcx" : "=a" (a) : "0" (a), "d" (b), "c" (c) ); |
431 | 0 | return a; |
432 | 0 | #else |
433 | | union { |
434 | | uint64_t ll; |
435 | | struct { |
436 | | #ifdef WORDS_BIGENDIAN |
437 | | uint32_t high, low; |
438 | | #else |
439 | | uint32_t low, high; |
440 | | #endif |
441 | | } l; |
442 | | } u, res; |
443 | | uint64_t rl, rh; |
444 | | |
445 | | u.ll = a; |
446 | | rl = (uint64_t)u.l.low * (uint64_t)b; |
447 | | rh = (uint64_t)u.l.high * (uint64_t)b; |
448 | | rh += (rl >> 32); |
449 | | res.l.high = rh / c; |
450 | | res.l.low = (((rh % c) << 32) + (rl & 0xffffffff)) / c; |
451 | | return res.ll; |
452 | | #endif |
453 | 0 | } |
454 | | |
455 | | unsigned long long parse_size_and_unit(const char *s, const char **ps) |
456 | 0 | { |
457 | 0 | unsigned long long ret; |
458 | 0 | const char *s1; |
459 | 0 |
|
460 | 0 | ret = simple_strtoull(s, &s1, 0); |
461 | 0 |
|
462 | 0 | switch ( *s1 ) |
463 | 0 | { |
464 | 0 | case 'T': case 't': |
465 | 0 | ret <<= 10; |
466 | 0 | /* fallthrough */ |
467 | 0 | case 'G': case 'g': |
468 | 0 | ret <<= 10; |
469 | 0 | /* fallthrough */ |
470 | 0 | case 'M': case 'm': |
471 | 0 | ret <<= 10; |
472 | 0 | /* fallthrough */ |
473 | 0 | case 'K': case 'k': |
474 | 0 | ret <<= 10; |
475 | 0 | /* fallthrough */ |
476 | 0 | case 'B': case 'b': |
477 | 0 | s1++; |
478 | 0 | break; |
479 | 0 | default: |
480 | 0 | ret <<= 10; /* default to kB */ |
481 | 0 | break; |
482 | 0 | } |
483 | 0 |
|
484 | 0 | if ( ps != NULL ) |
485 | 0 | *ps = s1; |
486 | 0 |
|
487 | 0 | return ret; |
488 | 0 | } |
489 | | |
490 | | typedef void (*ctor_func_t)(void); |
491 | | extern const ctor_func_t __ctors_start[], __ctors_end[]; |
492 | | |
493 | | void __init init_constructors(void) |
494 | 1 | { |
495 | 1 | const ctor_func_t *f; |
496 | 1 | for ( f = __ctors_start; f < __ctors_end; ++f ) |
497 | 0 | (*f)(); |
498 | 1 | |
499 | 1 | /* Putting this here seems as good (or bad) as any other place. */ |
500 | 1 | BUILD_BUG_ON(sizeof(size_t) != sizeof(ssize_t)); |
501 | 1 | } |
502 | | |
503 | | /* |
504 | | * Local variables: |
505 | | * mode: C |
506 | | * c-file-style: "BSD" |
507 | | * c-basic-offset: 4 |
508 | | * tab-width: 4 |
509 | | * indent-tabs-mode: nil |
510 | | * End: |
511 | | */ |