| /* |
| * This file is part of GNU CC. |
| * |
| * SPDX-License-Identifier: GPL-2.0+ |
| */ |
| |
| typedef unsigned int UWtype; |
| typedef unsigned int UHWtype; |
| typedef unsigned long long UDWtype; |
| #define W_TYPE_SIZE 32 |
| |
| 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; |
| |
| #define BITS_PER_UNIT 8 |
| |
| UDWtype |
| __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp); |
| |
| 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) |
| { |
| if (b == 0) |
| return u; |
| |
| const DWunion uu = {.ll = u}; |
| const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b; |
| DWunion w; |
| |
| if (bm <= 0) |
| { |
| w.s.low = 0; |
| w.s.high = (UWtype) uu.s.low << -bm; |
| } |
| else |
| { |
| const UWtype 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) |
| { |
| if (b == 0) |
| return u; |
| |
| const DWunion uu = {.ll = u}; |
| const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b; |
| DWunion w; |
| |
| if (bm <= 0) |
| { |
| /* w.s.high = 1..1 or 0..0 */ |
| w.s.high = uu.s.high >> (sizeof (Wtype) * BITS_PER_UNIT - 1); |
| w.s.low = uu.s.high >> -bm; |
| } |
| else |
| { |
| const UWtype 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) |
| { |
| if (b == 0) |
| return u; |
| |
| const DWunion uu = {.ll = u}; |
| const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b; |
| DWunion w; |
| |
| if (bm <= 0) |
| { |
| w.s.high = 0; |
| w.s.low = (UWtype) uu.s.high >> -bm; |
| } |
| else |
| { |
| const UWtype 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; |
| |
| 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) |
| { |
| /* 0q = nn / 0D */ |
| |
| udiv_qrnnd (q0, n0, n1, n0, d0); |
| q1 = 0; |
| |
| /* Remainder in n0. */ |
| } |
| else |
| { |
| /* qq = NN / 0d */ |
| |
| 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) |
| { |
| /* 0q = nn / 0D */ |
| |
| 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); |
| |
| /* Remainder in n0 >> bm. */ |
| } |
| |
| 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; |
| } |
| } |
| } |
| } |
| |
| const DWunion ww = {{.low = q0, .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) |
| { |
| while (size > 0) |
| { |
| const unsigned char c1 = *s1++, c2 = *s2++; |
| if (c1 != c2) |
| return c1 - c2; |
| size--; |
| } |
| return 0; |
| } |