| /* 64-bit multiplication and division |
| Copyright (C) 1989, 1992-2014 Free Software Foundation, Inc. |
| This file is part of the GNU C Library. |
| |
| The GNU C Library is free software; you can redistribute it and/or |
| modify it under the terms of the GNU Lesser General Public |
| License as published by the Free Software Foundation; either |
| version 2.1 of the License, or (at your option) any later version. |
| |
| The GNU C Library 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 |
| Lesser General Public License for more details. |
| |
| You should have received a copy of the GNU Lesser General Public |
| License along with the GNU C Library; if not, see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include <endian.h> |
| #include <stdlib.h> |
| #include <bits/wordsize.h> |
| |
| #if __WORDSIZE != 32 |
| #error This is for 32-bit targets only |
| #endif |
| |
| typedef unsigned int UQItype __attribute__ ((mode (QI))); |
| typedef int SItype __attribute__ ((mode (SI))); |
| typedef unsigned int USItype __attribute__ ((mode (SI))); |
| typedef int DItype __attribute__ ((mode (DI))); |
| typedef unsigned int UDItype __attribute__ ((mode (DI))); |
| #define Wtype SItype |
| #define HWtype SItype |
| #define DWtype DItype |
| #define UWtype USItype |
| #define UHWtype USItype |
| #define UDWtype UDItype |
| #define W_TYPE_SIZE 32 |
| |
| #include <stdlib/longlong.h> |
| |
| #if __BYTE_ORDER == __BIG_ENDIAN |
| struct DWstruct { Wtype high, low;}; |
| #elif __BYTE_ORDER == __LITTLE_ENDIAN |
| struct DWstruct { Wtype low, high;}; |
| #else |
| #error Unhandled endianity |
| #endif |
| typedef union { struct DWstruct s; DWtype ll; } DWunion; |
| |
| /* Prototypes of exported functions. */ |
| extern DWtype __divdi3 (DWtype u, DWtype v); |
| extern DWtype __moddi3 (DWtype u, DWtype v); |
| extern UDWtype __udivdi3 (UDWtype u, UDWtype v); |
| extern UDWtype __umoddi3 (UDWtype u, UDWtype v); |
| |
| static UDWtype |
| __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp) |
| { |
| DWunion ww; |
| DWunion nn, dd; |
| DWunion rr; |
| UWtype d0, d1, n0, n1, n2; |
| UWtype q0, q1; |
| UWtype b, bm; |
| |
| nn.ll = n; |
| dd.ll = d; |
| |
| 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; |
| } |
| } |
| } |
| } |
| |
| ww.s.low = q0; |
| ww.s.high = q1; |
| return ww.ll; |
| } |
| |
| DWtype |
| __divdi3 (DWtype u, DWtype v) |
| { |
| Wtype c = 0; |
| DWtype w; |
| |
| if (u < 0) |
| { |
| c = ~c; |
| u = -u; |
| } |
| if (v < 0) |
| { |
| c = ~c; |
| v = -v; |
| } |
| w = __udivmoddi4 (u, v, NULL); |
| if (c) |
| w = -w; |
| return w; |
| } |
| strong_alias (__divdi3, __divdi3_internal) |
| |
| DWtype |
| __moddi3 (DWtype u, DWtype v) |
| { |
| Wtype c = 0; |
| DWtype w; |
| |
| if (u < 0) |
| { |
| c = ~c; |
| u = -u; |
| } |
| if (v < 0) |
| v = -v; |
| __udivmoddi4 (u, v, (UDWtype *) &w); |
| if (c) |
| w = -w; |
| return w; |
| } |
| strong_alias (__moddi3, __moddi3_internal) |
| |
| UDWtype |
| __udivdi3 (UDWtype u, UDWtype v) |
| { |
| return __udivmoddi4 (u, v, NULL); |
| } |
| strong_alias (__udivdi3, __udivdi3_internal) |
| |
| UDWtype |
| __umoddi3 (UDWtype u, UDWtype v) |
| { |
| UDWtype w; |
| |
| __udivmoddi4 (u, v, &w); |
| return w; |
| } |
| strong_alias (__umoddi3, __umoddi3_internal) |
| |
| /* We declare these with compat_symbol so that they are not visible at |
| link time. Programs must use the functions from libgcc. */ |
| #ifdef SHARED |
| # include <shlib-compat.h> |
| compat_symbol (libc, __divdi3, __divdi3, GLIBC_2_0); |
| compat_symbol (libc, __moddi3, __moddi3, GLIBC_2_0); |
| compat_symbol (libc, __udivdi3, __udivdi3, GLIBC_2_0); |
| compat_symbol (libc, __umoddi3, __umoddi3, GLIBC_2_0); |
| #endif |