/* 64-bit multiplication and division Copyright (C) 1989, 1992-1999,2000,2001,2002,2003,2004,2005 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, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ #include #include #include #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 #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. */ #if defined HAVE_ELF && defined SHARED # include invisible_compat_symbol (libc, __divdi3, GLIBC_2_0); invisible_compat_symbol (libc, __moddi3, GLIBC_2_0); invisible_compat_symbol (libc, __udivdi3, GLIBC_2_0); invisible_compat_symbol (libc, __umoddi3, GLIBC_2_0); #endif