ia64/xen-unstable

view xen/common/lib.c @ 9706:3c05406f5e0a

In some cases, say for instance for some bizzare reason
the tree was checked out of CVS, which doens't neccessarily
store file permissions, mkbuildtree may not be executable.
So run them explicitly via bash.

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