blob: 27c899f4b6c6b55129883a125843291f2db7f63d [file] [log] [blame]
/*
* This file is part of GNU CC.
*
* GNU CC is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published
* by the Free Software Foundation; either version 2, or (at your
* option) any later version.
*
* GNU CC is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public
* License along with GNU CC; see the file COPYING. If not, write
* to the Free Software Foundation, 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
#define W_TYPE_SIZE 32
#define BITS_PER_UNIT 8
typedef unsigned int UWtype;
typedef unsigned int UHWtype;
typedef unsigned long long UDWtype;
typedef unsigned char UQItype;
typedef long SItype;
typedef unsigned long USItype;
typedef long long DItype;
typedef unsigned long long DSItype;
#include "longlong.h"
typedef int word_type;
typedef long Wtype;
typedef long long DWtype;
struct DWstruct { Wtype low, high; };
typedef union {
struct DWstruct s;
DWtype ll;
} DWunion;
const UQItype __clz_tab[256] = {
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
};
DWtype __ashldi3(DWtype u, word_type b)
{
const DWunion uu = {.ll = u};
const word_type bm = (sizeof(Wtype) * BITS_PER_UNIT) - b;
DWunion w;
UWtype carries;
if (b == 0)
return u;
if (bm <= 0) {
w.s.low = 0;
w.s.high = (UWtype) uu.s.low << -bm;
} else {
carries = (UWtype) uu.s.low >> bm;
w.s.low = (UWtype) uu.s.low << b;
w.s.high = ((UWtype) uu.s.high << b) | carries;
}
return w.ll;
}
DWtype __ashrdi3(DWtype u, word_type b)
{
const DWunion uu = {.ll = u};
const word_type bm = (sizeof(Wtype) * BITS_PER_UNIT) - b;
DWunion w;
UWtype carries;
if (b == 0)
return u;
if (bm <= 0) {
w.s.high = uu.s.high >> (sizeof(Wtype) * BITS_PER_UNIT - 1);
w.s.low = uu.s.high >> -bm;
} else {
carries = (UWtype) uu.s.high << bm;
w.s.high = uu.s.high >> b;
w.s.low = ((UWtype) uu.s.low >> b) | carries;
}
return w.ll;
}
DWtype __lshrdi3(DWtype u, word_type b)
{
const DWunion uu = {.ll = u};
const word_type bm = (sizeof(Wtype) * BITS_PER_UNIT) - b;
DWunion w;
UWtype carries;
if (b == 0)
return u;
if (bm <= 0) {
w.s.high = 0;
w.s.low = (UWtype) uu.s.high >> -bm;
} else {
carries = (UWtype) uu.s.high << bm;
w.s.high = (UWtype) uu.s.high >> b;
w.s.low = ((UWtype) uu.s.low >> b) | carries;
}
return w.ll;
}
word_type __cmpdi2(DWtype a, DWtype b)
{
const DWunion au = {.ll = a};
const DWunion bu = {.ll = b};
if (au.s.high < bu.s.high)
return 0;
else if (au.s.high > bu.s.high)
return 2;
if ((UWtype) au.s.low < (UWtype) bu.s.low)
return 0;
else if ((UWtype) au.s.low > (UWtype) bu.s.low)
return 2;
return 1;
}
UDWtype __udivmoddi4(UDWtype n, UDWtype d, UDWtype *rp)
{
const DWunion nn = {.ll = n};
const DWunion dd = {.ll = d};
DWunion rr;
UWtype d0, d1, n0, n1, n2;
UWtype q0, q1;
UWtype b, bm;
DWunion ww;
d0 = dd.s.low;
d1 = dd.s.high;
n0 = nn.s.low;
n1 = nn.s.high;
#if !UDIV_NEEDS_NORMALIZATION
if (d1 == 0) {
if (d0 > n1) {
udiv_qrnnd(q0, n0, n1, n0, d0);
q1 = 0;
} else {
if (d0 == 0)
d0 = 1 / d0; /* Divide intentionally by zero.*/
udiv_qrnnd(q1, n1, 0, n1, d0);
udiv_qrnnd(q0, n0, n1, n0, d0);
/* Remainder in n0. */
}
if (rp != 0) {
rr.s.low = n0;
rr.s.high = 0;
*rp = rr.ll;
}
}
#else /* UDIV_NEEDS_NORMALIZATION */
if (d1 == 0) {
if (d0 > n1) {
count_leading_zeros(bm, d0);
if (bm != 0) {
/* Normalize, i.e. make the most significant
bit of the denominator set. */
d0 = d0 << bm;
n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));
n0 = n0 << bm;
}
udiv_qrnnd(q0, n0, n1, n0, d0);
q1 = 0;
/* Remainder in n0 >> bm. */
} else { /* qq = NN / 0d */
if (d0 == 0)
d0 = 1 / d0; /* Divide intentionally by zero. */
count_leading_zeros(bm, d0);
if (bm == 0) {
/* From (n1 >= d0) /\ (the most significant bit
of d0 is set), conclude (the most significant
bit of n1 is set) /\ (the leading quotient digit
q1 = 1).
This special case is necessary, not an
optimization.(Shifts counts of W_TYPE_SIZE are
undefined.) */
n1 -= d0;
q1 = 1;
} else { /* Normalize. */
b = W_TYPE_SIZE - bm;
d0 = d0 << bm;
n2 = n1 >> b;
n1 = (n1 << bm) | (n0 >> b);
n0 = n0 << bm;
udiv_qrnnd(q1, n1, n2, n1, d0);
}
/* n1 != d0... */
udiv_qrnnd(q0, n0, n1, n0, d0);
}
if (rp != 0) {
rr.s.low = n0 >> bm;
rr.s.high = 0;
*rp = rr.ll;
}
}
#endif /* UDIV_NEEDS_NORMALIZATION */
else {
if (d1 > n1) { /* 00 = nn / DD */
q0 = 0;
q1 = 0;
/* Remainder in n1n0. */
if (rp != 0) {
rr.s.low = n0;
rr.s.high = n1;
*rp = rr.ll;
}
} else { /* 0q = NN / dd */
count_leading_zeros(bm, d1);
if (bm == 0) {
/* From (n1 >= d1) /\ (the most significant bit
of d1 is set), conclude (the most significant
bit of n1 is set) /\ (the quotient digit q0 = 0
or 1).
This special case is necessary,
not an optimization. */
/* The condition on the next line takes
advantage of that n1 >= d1 (true due to program
flow). */
if (n1 > d1 || n0 >= d0) {
q0 = 1;
sub_ddmmss(n1, n0, n1, n0, d1, d0);
} else
q0 = 0;
q1 = 0;
if (rp != 0) {
rr.s.low = n0;
rr.s.high = n1;
*rp = rr.ll;
}
} else {
UWtype m1, m0;
/* Normalize. */
b = W_TYPE_SIZE - bm;
d1 = (d1 << bm) | (d0 >> b);
d0 = d0 << bm;
n2 = n1 >> b;
n1 = (n1 << bm) | (n0 >> b);
n0 = n0 << bm;
udiv_qrnnd(q0, n1, n2, n1, d1);
umul_ppmm(m1, m0, q0, d0);
if (m1 > n1 || (m1 == n1 && m0 > n0)) {
q0--;
sub_ddmmss(m1, m0, m1, m0, d1, d0);
}
q1 = 0;
/* Remainder in (n1n0 - m1m0) >> bm. */
if (rp != 0) {
sub_ddmmss(n1, n0, n1, n0, m1, m0);
rr.s.low = (n1 << b) | (n0 >> bm);
rr.s.high = n1 >> bm;
*rp = rr.ll;
}
}
}
}
ww.s.low = q0;
ww.s.high = q1;
return ww.ll;
}
DWtype __divdi3(DWtype u, DWtype v)
{
word_type c = 0;
DWunion uu = {.ll = u};
DWunion vv = {.ll = v};
DWtype w;
if (uu.s.high < 0)
c = ~c,
uu.ll = -uu.ll;
if (vv.s.high < 0)
c = ~c,
vv.ll = -vv.ll;
w = __udivmoddi4(uu.ll, vv.ll, (UDWtype *) 0);
if (c)
w = -w;
return w;
}
DWtype __negdi2(DWtype u)
{
const DWunion uu = {.ll = u};
const DWunion w = { {.low = -uu.s.low,
.high = -uu.s.high - ((UWtype) -uu.s.low > 0) } };
return w.ll;
}
DWtype __muldi3(DWtype u, DWtype v)
{
const DWunion uu = {.ll = u};
const DWunion vv = {.ll = v};
DWunion w = {.ll = __umulsidi3(uu.s.low, vv.s.low)};
w.s.high += ((UWtype) uu.s.low * (UWtype) vv.s.high
+ (UWtype) uu.s.high * (UWtype) vv.s.low);
return w.ll;
}
DWtype __moddi3(DWtype u, DWtype v)
{
word_type c = 0;
DWunion uu = {.ll = u};
DWunion vv = {.ll = v};
DWtype w;
if (uu.s.high < 0)
c = ~c,
uu.ll = -uu.ll;
if (vv.s.high < 0)
vv.ll = -vv.ll;
(void) __udivmoddi4(uu.ll, vv.ll, (UDWtype *)&w);
if (c)
w = -w;
return w;
}
word_type __ucmpdi2(DWtype a, DWtype b)
{
const DWunion au = {.ll = a};
const DWunion bu = {.ll = b};
if ((UWtype) au.s.high < (UWtype) bu.s.high)
return 0;
else if ((UWtype) au.s.high > (UWtype) bu.s.high)
return 2;
if ((UWtype) au.s.low < (UWtype) bu.s.low)
return 0;
else if ((UWtype) au.s.low > (UWtype) bu.s.low)
return 2;
return 1;
}
UDWtype __udivdi3(UDWtype n, UDWtype d)
{
return __udivmoddi4(n, d, (UDWtype *) 0);
}
UDWtype __umoddi3(UDWtype u, UDWtype v)
{
UDWtype w;
(void) __udivmoddi4(u, v, &w);
return w;
}
static USItype udivmodsi4(USItype num, USItype den, word_type modwanted)
{
USItype bit = 1;
USItype res = 0;
while (den < num && bit && !(den & (1L<<31))) {
den <<= 1;
bit <<= 1;
}
while (bit) {
if (num >= den) {
num -= den;
res |= bit;
}
bit >>= 1;
den >>= 1;
}
if (modwanted)
return num;
return res;
}
SItype __divsi3(SItype a, SItype b)
{
word_type neg = 0;
SItype res;
if (a < 0) {
a = -a;
neg = !neg;
}
if (b < 0) {
b = -b;
neg = !neg;
}
res = udivmodsi4(a, b, 0);
if (neg)
res = -res;
return res;
}
SItype __udivsi3(SItype a, SItype b)
{
return udivmodsi4(a, b, 0);
}
SItype __modsi3(SItype a, SItype b)
{
word_type neg = 0;
SItype res;
if (a < 0) {
a = -a;
neg = 1;
}
if (b < 0)
b = -b;
res = udivmodsi4(a, b, 1);
if (neg)
res = -res;
return res;
}
SItype __mulsi3(SItype a, SItype b)
{
SItype res = 0;
USItype cnt = a;
while (cnt) {
if (cnt & 1)
res += b;
b <<= 1;
cnt >>= 1;
}
return res;
}
SItype __umodsi3(SItype a, SItype b)
{
return udivmodsi4(a, b, 1);
}
int __gcc_bcmp(const unsigned char *s1, const unsigned char *s2, unsigned long size)
{
unsigned char c1;
unsigned char c2;
while (size > 0) {
c1 = *s1++;
c2 = *s2++;
if (c1 != c2)
return c1 - c2;
size--;
}
return 0;
}