optimized token strings - optimized token hashing
[tinycc/miki.git] / libtcc1.c
blob412629e2678be0edd90ca29172650da20d95dc41
1 /* TCC runtime library.
2 Parts of this code are (c) 2002 Fabrice Bellard
4 Copyright (C) 1987, 1988, 1992, 1994, 1995 Free Software Foundation, Inc.
6 This file is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
11 In addition to the permissions in the GNU General Public License, the
12 Free Software Foundation gives you unlimited permission to link the
13 compiled version of this file into combinations with other programs,
14 and to distribute those combinations without any restriction coming
15 from the use of this file. (The General Public License restrictions
16 do apply in other respects; for example, they cover modification of
17 the file, and distribution when not linked into a combine
18 executable.)
20 This file is distributed in the hope that it will be useful, but
21 WITHOUT ANY WARRANTY; without even the implied warranty of
22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 General Public License for more details.
25 You should have received a copy of the GNU General Public License
26 along with this program; see the file COPYING. If not, write to
27 the Free Software Foundation, 59 Temple Place - Suite 330,
28 Boston, MA 02111-1307, USA.
31 #define W_TYPE_SIZE 32
32 #define BITS_PER_UNIT 8
34 typedef int Wtype;
35 typedef unsigned int UWtype;
36 typedef unsigned int USItype;
37 typedef long long DWtype;
38 typedef unsigned long long UDWtype;
40 struct DWstruct {
41 Wtype low, high;
44 typedef union
46 struct DWstruct s;
47 DWtype ll;
48 } DWunion;
50 typedef long double XFtype;
51 #define WORD_SIZE (sizeof (Wtype) * BITS_PER_UNIT)
52 #define HIGH_WORD_COEFF (((UDWtype) 1) << WORD_SIZE)
54 /* the following deal with IEEE single-precision numbers */
55 #define EXCESS 126
56 #define SIGNBIT 0x80000000
57 #define HIDDEN (1 << 23)
58 #define SIGN(fp) ((fp) & SIGNBIT)
59 #define EXP(fp) (((fp) >> 23) & 0xFF)
60 #define MANT(fp) (((fp) & 0x7FFFFF) | HIDDEN)
61 #define PACK(s,e,m) ((s) | ((e) << 23) | (m))
63 /* the following deal with IEEE double-precision numbers */
64 #define EXCESSD 1022
65 #define HIDDEND (1 << 20)
66 #define EXPD(fp) (((fp.l.upper) >> 20) & 0x7FF)
67 #define SIGND(fp) ((fp.l.upper) & SIGNBIT)
68 #define MANTD(fp) (((((fp.l.upper) & 0xFFFFF) | HIDDEND) << 10) | \
69 (fp.l.lower >> 22))
70 #define HIDDEND_LL ((long long)1 << 52)
71 #define MANTD_LL(fp) ((fp.ll & (HIDDEND_LL-1)) | HIDDEND_LL)
72 #define PACKD_LL(s,e,m) (((long long)((s)+((e)<<20))<<32)|(m))
74 /* the following deal with x86 long double-precision numbers */
75 #define EXCESSLD 16382
76 #define EXPLD(fp) (fp.l.upper & 0x7fff)
77 #define SIGNLD(fp) ((fp.l.upper) & 0x8000)
79 /* only for x86 */
80 union ldouble_long {
81 long double ld;
82 struct {
83 unsigned long long lower;
84 unsigned short upper;
85 } l;
88 union double_long {
89 double d;
90 #if 1
91 struct {
92 unsigned long lower;
93 long upper;
94 } l;
95 #else
96 struct {
97 long upper;
98 unsigned long lower;
99 } l;
100 #endif
101 long long ll;
104 union float_long {
105 float f;
106 long l;
109 /* XXX: use gcc/tcc intrinsic ? */
110 #if defined(__i386__)
111 #define sub_ddmmss(sh, sl, ah, al, bh, bl) \
112 __asm__ ("subl %5,%1\n\tsbbl %3,%0" \
113 : "=r" ((USItype) (sh)), \
114 "=&r" ((USItype) (sl)) \
115 : "0" ((USItype) (ah)), \
116 "g" ((USItype) (bh)), \
117 "1" ((USItype) (al)), \
118 "g" ((USItype) (bl)))
119 #define umul_ppmm(w1, w0, u, v) \
120 __asm__ ("mull %3" \
121 : "=a" ((USItype) (w0)), \
122 "=d" ((USItype) (w1)) \
123 : "%0" ((USItype) (u)), \
124 "rm" ((USItype) (v)))
125 #define udiv_qrnnd(q, r, n1, n0, dv) \
126 __asm__ ("divl %4" \
127 : "=a" ((USItype) (q)), \
128 "=d" ((USItype) (r)) \
129 : "0" ((USItype) (n0)), \
130 "1" ((USItype) (n1)), \
131 "rm" ((USItype) (dv)))
132 #define count_leading_zeros(count, x) \
133 do { \
134 USItype __cbtmp; \
135 __asm__ ("bsrl %1,%0" \
136 : "=r" (__cbtmp) : "rm" ((USItype) (x))); \
137 (count) = __cbtmp ^ 31; \
138 } while (0)
139 #else
140 #error unsupported CPU type
141 #endif
143 /* most of this code is taken from libgcc2.c from gcc */
145 static UDWtype __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
147 DWunion ww;
148 DWunion nn, dd;
149 DWunion rr;
150 UWtype d0, d1, n0, n1, n2;
151 UWtype q0, q1;
152 UWtype b, bm;
154 nn.ll = n;
155 dd.ll = d;
157 d0 = dd.s.low;
158 d1 = dd.s.high;
159 n0 = nn.s.low;
160 n1 = nn.s.high;
162 #if !UDIV_NEEDS_NORMALIZATION
163 if (d1 == 0)
165 if (d0 > n1)
167 /* 0q = nn / 0D */
169 udiv_qrnnd (q0, n0, n1, n0, d0);
170 q1 = 0;
172 /* Remainder in n0. */
174 else
176 /* qq = NN / 0d */
178 if (d0 == 0)
179 d0 = 1 / d0; /* Divide intentionally by zero. */
181 udiv_qrnnd (q1, n1, 0, n1, d0);
182 udiv_qrnnd (q0, n0, n1, n0, d0);
184 /* Remainder in n0. */
187 if (rp != 0)
189 rr.s.low = n0;
190 rr.s.high = 0;
191 *rp = rr.ll;
195 #else /* UDIV_NEEDS_NORMALIZATION */
197 if (d1 == 0)
199 if (d0 > n1)
201 /* 0q = nn / 0D */
203 count_leading_zeros (bm, d0);
205 if (bm != 0)
207 /* Normalize, i.e. make the most significant bit of the
208 denominator set. */
210 d0 = d0 << bm;
211 n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));
212 n0 = n0 << bm;
215 udiv_qrnnd (q0, n0, n1, n0, d0);
216 q1 = 0;
218 /* Remainder in n0 >> bm. */
220 else
222 /* qq = NN / 0d */
224 if (d0 == 0)
225 d0 = 1 / d0; /* Divide intentionally by zero. */
227 count_leading_zeros (bm, d0);
229 if (bm == 0)
231 /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
232 conclude (the most significant bit of n1 is set) /\ (the
233 leading quotient digit q1 = 1).
235 This special case is necessary, not an optimization.
236 (Shifts counts of W_TYPE_SIZE are undefined.) */
238 n1 -= d0;
239 q1 = 1;
241 else
243 /* Normalize. */
245 b = W_TYPE_SIZE - bm;
247 d0 = d0 << bm;
248 n2 = n1 >> b;
249 n1 = (n1 << bm) | (n0 >> b);
250 n0 = n0 << bm;
252 udiv_qrnnd (q1, n1, n2, n1, d0);
255 /* n1 != d0... */
257 udiv_qrnnd (q0, n0, n1, n0, d0);
259 /* Remainder in n0 >> bm. */
262 if (rp != 0)
264 rr.s.low = n0 >> bm;
265 rr.s.high = 0;
266 *rp = rr.ll;
269 #endif /* UDIV_NEEDS_NORMALIZATION */
271 else
273 if (d1 > n1)
275 /* 00 = nn / DD */
277 q0 = 0;
278 q1 = 0;
280 /* Remainder in n1n0. */
281 if (rp != 0)
283 rr.s.low = n0;
284 rr.s.high = n1;
285 *rp = rr.ll;
288 else
290 /* 0q = NN / dd */
292 count_leading_zeros (bm, d1);
293 if (bm == 0)
295 /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
296 conclude (the most significant bit of n1 is set) /\ (the
297 quotient digit q0 = 0 or 1).
299 This special case is necessary, not an optimization. */
301 /* The condition on the next line takes advantage of that
302 n1 >= d1 (true due to program flow). */
303 if (n1 > d1 || n0 >= d0)
305 q0 = 1;
306 sub_ddmmss (n1, n0, n1, n0, d1, d0);
308 else
309 q0 = 0;
311 q1 = 0;
313 if (rp != 0)
315 rr.s.low = n0;
316 rr.s.high = n1;
317 *rp = rr.ll;
320 else
322 UWtype m1, m0;
323 /* Normalize. */
325 b = W_TYPE_SIZE - bm;
327 d1 = (d1 << bm) | (d0 >> b);
328 d0 = d0 << bm;
329 n2 = n1 >> b;
330 n1 = (n1 << bm) | (n0 >> b);
331 n0 = n0 << bm;
333 udiv_qrnnd (q0, n1, n2, n1, d1);
334 umul_ppmm (m1, m0, q0, d0);
336 if (m1 > n1 || (m1 == n1 && m0 > n0))
338 q0--;
339 sub_ddmmss (m1, m0, m1, m0, d1, d0);
342 q1 = 0;
344 /* Remainder in (n1n0 - m1m0) >> bm. */
345 if (rp != 0)
347 sub_ddmmss (n1, n0, n1, n0, m1, m0);
348 rr.s.low = (n1 << b) | (n0 >> bm);
349 rr.s.high = n1 >> bm;
350 *rp = rr.ll;
356 ww.s.low = q0;
357 ww.s.high = q1;
358 return ww.ll;
361 #define __negdi2(a) (-(a))
363 long long __divdi3(long long u, long long v)
365 int c = 0;
366 DWunion uu, vv;
367 DWtype w;
369 uu.ll = u;
370 vv.ll = v;
372 if (uu.s.high < 0) {
373 c = ~c;
374 uu.ll = __negdi2 (uu.ll);
376 if (vv.s.high < 0) {
377 c = ~c;
378 vv.ll = __negdi2 (vv.ll);
380 w = __udivmoddi4 (uu.ll, vv.ll, (UDWtype *) 0);
381 if (c)
382 w = __negdi2 (w);
383 return w;
386 long long __moddi3(long long u, long long v)
388 int c = 0;
389 DWunion uu, vv;
390 DWtype w;
392 uu.ll = u;
393 vv.ll = v;
395 if (uu.s.high < 0) {
396 c = ~c;
397 uu.ll = __negdi2 (uu.ll);
399 if (vv.s.high < 0)
400 vv.ll = __negdi2 (vv.ll);
402 __udivmoddi4 (uu.ll, vv.ll, &w);
403 if (c)
404 w = __negdi2 (w);
405 return w;
408 unsigned long long __udivdi3(unsigned long long u, unsigned long long v)
410 return __udivmoddi4 (u, v, (UDWtype *) 0);
413 unsigned long long __umoddi3(unsigned long long u, unsigned long long v)
415 UDWtype w;
417 __udivmoddi4 (u, v, &w);
418 return w;
421 /* XXX: suppress that and patch tcc to do it */
422 long long __sardi3(long long a, int b)
424 return a >> b;
427 /* XXX: suppress that and patch tcc to do it */
428 unsigned long long __shrdi3(unsigned long long a, int b)
430 return a >> b;
433 /* XXX: suppress that and patch tcc to do it */
434 long long __shldi3(long long a, int b)
436 return a << b;
439 #if defined(__i386__)
440 /* FPU control word for rounding to nearest mode */
441 unsigned short __tcc_fpu_control = 0x137f;
442 /* FPU control word for round to zero mode for int convertion */
443 unsigned short __tcc_int_fpu_control = 0x137f | 0x0c00;
444 #endif
446 /* XXX: suppress that and patch tcc to do it */
447 float __ulltof(unsigned long long a)
449 DWunion uu;
450 XFtype r;
452 uu.ll = a;
453 if (uu.s.high >= 0) {
454 return (float)uu.ll;
455 } else {
456 r = (XFtype)uu.ll;
457 r += 18446744073709551616.0;
458 return (float)r;
462 double __ulltod(unsigned long long a)
464 DWunion uu;
465 XFtype r;
467 uu.ll = a;
468 if (uu.s.high >= 0) {
469 return (double)uu.ll;
470 } else {
471 r = (XFtype)uu.ll;
472 r += 18446744073709551616.0;
473 return (double)r;
477 long double __ulltold(unsigned long long a)
479 DWunion uu;
480 XFtype r;
482 uu.ll = a;
483 if (uu.s.high >= 0) {
484 return (long double)uu.ll;
485 } else {
486 r = (XFtype)uu.ll;
487 r += 18446744073709551616.0;
488 return (long double)r;
492 unsigned long long __fixunssfdi (float a1)
494 register union float_long fl1;
495 register int exp;
496 register unsigned long l;
498 fl1.f = a1;
500 if (fl1.l == 0)
501 return (0);
503 exp = EXP (fl1.l) - EXCESS - 24;
505 l = MANT(fl1.l);
506 if (exp >= 41)
507 return (unsigned long long)-1;
508 else if (exp >= 0)
509 return (unsigned long long)l << exp;
510 else if (exp >= -23)
511 return l >> -exp;
512 else
513 return 0;
516 unsigned long long __fixunsdfdi (double a1)
518 register union double_long dl1;
519 register int exp;
520 register unsigned long long l;
522 dl1.d = a1;
524 if (dl1.ll == 0)
525 return (0);
527 exp = EXPD (dl1) - EXCESSD - 53;
529 l = MANTD_LL(dl1);
531 if (exp >= 12)
532 return (unsigned long long)-1;
533 else if (exp >= 0)
534 return l << exp;
535 else if (exp >= -52)
536 return l >> -exp;
537 else
538 return 0;
541 unsigned long long __fixunsxfdi (long double a1)
543 register union ldouble_long dl1;
544 register int exp;
545 register unsigned long long l;
547 dl1.ld = a1;
549 if (dl1.l.lower == 0 && dl1.l.upper == 0)
550 return (0);
552 exp = EXPLD (dl1) - EXCESSLD - 64;
554 l = dl1.l.lower;
556 if (exp > 0)
557 return (unsigned long long)-1;
558 else if (exp >= -63)
559 return l >> -exp;
560 else
561 return 0;