Back to index

glibc  2.9
divdi3.c
Go to the documentation of this file.
00001 /* 64-bit multiplication and division
00002    Copyright (C) 1989, 1992-1999,2000,2001,2002,2003,2004,2005
00003        Free Software Foundation, Inc.
00004    This file is part of the GNU C Library.
00005 
00006    The GNU C Library is free software; you can redistribute it and/or
00007    modify it under the terms of the GNU Lesser General Public
00008    License as published by the Free Software Foundation; either
00009    version 2.1 of the License, or (at your option) any later version.
00010 
00011    The GNU C Library is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014    Lesser General Public License for more details.
00015 
00016    You should have received a copy of the GNU Lesser General Public
00017    License along with the GNU C Library; if not, write to the Free
00018    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00019    02111-1307 USA.  */
00020 
00021 #include <endian.h>
00022 #include <stdlib.h>
00023 #include <bits/wordsize.h>
00024 
00025 #if __WORDSIZE != 32
00026 #error This is for 32-bit targets only
00027 #endif
00028 
00029 typedef unsigned int UQItype       __attribute__ ((mode (QI)));
00030 typedef          int SItype __attribute__ ((mode (SI)));
00031 typedef unsigned int USItype       __attribute__ ((mode (SI)));
00032 typedef          int DItype __attribute__ ((mode (DI)));
00033 typedef unsigned int UDItype       __attribute__ ((mode (DI)));
00034 #define Wtype SItype
00035 #define HWtype SItype
00036 #define DWtype DItype
00037 #define UWtype USItype
00038 #define UHWtype USItype
00039 #define UDWtype UDItype
00040 #define W_TYPE_SIZE 32
00041 
00042 #include <stdlib/longlong.h>
00043 
00044 #if __BYTE_ORDER == __BIG_ENDIAN
00045 struct DWstruct { Wtype high, low;};
00046 #elif __BYTE_ORDER == __LITTLE_ENDIAN
00047 struct DWstruct { Wtype low, high;};
00048 #else
00049 #error Unhandled endianity
00050 #endif
00051 typedef union { struct DWstruct s; DWtype ll; } DWunion;
00052 
00053 /* Prototypes of exported functions.  */
00054 extern DWtype __divdi3 (DWtype u, DWtype v);
00055 extern DWtype __moddi3 (DWtype u, DWtype v);
00056 extern UDWtype __udivdi3 (UDWtype u, UDWtype v);
00057 extern UDWtype __umoddi3 (UDWtype u, UDWtype v);
00058 
00059 static UDWtype
00060 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
00061 {
00062   DWunion ww;
00063   DWunion nn, dd;
00064   DWunion rr;
00065   UWtype d0, d1, n0, n1, n2;
00066   UWtype q0, q1;
00067   UWtype b, bm;
00068 
00069   nn.ll = n;
00070   dd.ll = d;
00071 
00072   d0 = dd.s.low;
00073   d1 = dd.s.high;
00074   n0 = nn.s.low;
00075   n1 = nn.s.high;
00076 
00077 #if !UDIV_NEEDS_NORMALIZATION
00078   if (d1 == 0)
00079     {
00080       if (d0 > n1)
00081        {
00082          /* 0q = nn / 0D */
00083 
00084          udiv_qrnnd (q0, n0, n1, n0, d0);
00085          q1 = 0;
00086 
00087          /* Remainder in n0.  */
00088        }
00089       else
00090        {
00091          /* qq = NN / 0d */
00092 
00093          if (d0 == 0)
00094            d0 = 1 / d0;     /* Divide intentionally by zero.  */
00095 
00096          udiv_qrnnd (q1, n1, 0, n1, d0);
00097          udiv_qrnnd (q0, n0, n1, n0, d0);
00098 
00099          /* Remainder in n0.  */
00100        }
00101 
00102       if (rp != 0)
00103        {
00104          rr.s.low = n0;
00105          rr.s.high = 0;
00106          *rp = rr.ll;
00107        }
00108     }
00109 
00110 #else /* UDIV_NEEDS_NORMALIZATION */
00111 
00112   if (d1 == 0)
00113     {
00114       if (d0 > n1)
00115        {
00116          /* 0q = nn / 0D */
00117 
00118          count_leading_zeros (bm, d0);
00119 
00120          if (bm != 0)
00121            {
00122              /* Normalize, i.e. make the most significant bit of the
00123                denominator set.  */
00124 
00125              d0 = d0 << bm;
00126              n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));
00127              n0 = n0 << bm;
00128            }
00129 
00130          udiv_qrnnd (q0, n0, n1, n0, d0);
00131          q1 = 0;
00132 
00133          /* Remainder in n0 >> bm.  */
00134        }
00135       else
00136        {
00137          /* qq = NN / 0d */
00138 
00139          if (d0 == 0)
00140            d0 = 1 / d0;     /* Divide intentionally by zero.  */
00141 
00142          count_leading_zeros (bm, d0);
00143 
00144          if (bm == 0)
00145            {
00146              /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
00147                conclude (the most significant bit of n1 is set) /\ (the
00148                leading quotient digit q1 = 1).
00149 
00150                This special case is necessary, not an optimization.
00151                (Shifts counts of W_TYPE_SIZE are undefined.)  */
00152 
00153              n1 -= d0;
00154              q1 = 1;
00155            }
00156          else
00157            {
00158              /* Normalize.  */
00159 
00160              b = W_TYPE_SIZE - bm;
00161 
00162              d0 = d0 << bm;
00163              n2 = n1 >> b;
00164              n1 = (n1 << bm) | (n0 >> b);
00165              n0 = n0 << bm;
00166 
00167              udiv_qrnnd (q1, n1, n2, n1, d0);
00168            }
00169 
00170          /* n1 != d0...  */
00171 
00172          udiv_qrnnd (q0, n0, n1, n0, d0);
00173 
00174          /* Remainder in n0 >> bm.  */
00175        }
00176 
00177       if (rp != 0)
00178        {
00179          rr.s.low = n0 >> bm;
00180          rr.s.high = 0;
00181          *rp = rr.ll;
00182        }
00183     }
00184 #endif /* UDIV_NEEDS_NORMALIZATION */
00185 
00186   else
00187     {
00188       if (d1 > n1)
00189        {
00190          /* 00 = nn / DD */
00191 
00192          q0 = 0;
00193          q1 = 0;
00194 
00195          /* Remainder in n1n0.  */
00196          if (rp != 0)
00197            {
00198              rr.s.low = n0;
00199              rr.s.high = n1;
00200              *rp = rr.ll;
00201            }
00202        }
00203       else
00204        {
00205          /* 0q = NN / dd */
00206 
00207          count_leading_zeros (bm, d1);
00208          if (bm == 0)
00209            {
00210              /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
00211                conclude (the most significant bit of n1 is set) /\ (the
00212                quotient digit q0 = 0 or 1).
00213 
00214                This special case is necessary, not an optimization.  */
00215 
00216              /* The condition on the next line takes advantage of that
00217                n1 >= d1 (true due to program flow).  */
00218              if (n1 > d1 || n0 >= d0)
00219               {
00220                 q0 = 1;
00221                 sub_ddmmss (n1, n0, n1, n0, d1, d0);
00222               }
00223              else
00224               q0 = 0;
00225 
00226              q1 = 0;
00227 
00228              if (rp != 0)
00229               {
00230                 rr.s.low = n0;
00231                 rr.s.high = n1;
00232                 *rp = rr.ll;
00233               }
00234            }
00235          else
00236            {
00237              UWtype m1, m0;
00238              /* Normalize.  */
00239 
00240              b = W_TYPE_SIZE - bm;
00241 
00242              d1 = (d1 << bm) | (d0 >> b);
00243              d0 = d0 << bm;
00244              n2 = n1 >> b;
00245              n1 = (n1 << bm) | (n0 >> b);
00246              n0 = n0 << bm;
00247 
00248              udiv_qrnnd (q0, n1, n2, n1, d1);
00249              umul_ppmm (m1, m0, q0, d0);
00250 
00251              if (m1 > n1 || (m1 == n1 && m0 > n0))
00252               {
00253                 q0--;
00254                 sub_ddmmss (m1, m0, m1, m0, d1, d0);
00255               }
00256 
00257              q1 = 0;
00258 
00259              /* Remainder in (n1n0 - m1m0) >> bm.  */
00260              if (rp != 0)
00261               {
00262                 sub_ddmmss (n1, n0, n1, n0, m1, m0);
00263                 rr.s.low = (n1 << b) | (n0 >> bm);
00264                 rr.s.high = n1 >> bm;
00265                 *rp = rr.ll;
00266               }
00267            }
00268        }
00269     }
00270 
00271   ww.s.low = q0;
00272   ww.s.high = q1;
00273   return ww.ll;
00274 }
00275 
00276 DWtype
00277 __divdi3 (DWtype u, DWtype v)
00278 {
00279   Wtype c = 0;
00280   DWtype w;
00281 
00282   if (u < 0)
00283     {
00284       c = ~c;
00285       u = -u;
00286     }
00287   if (v < 0)
00288     {
00289       c = ~c;
00290       v = -v;
00291     }
00292   w = __udivmoddi4 (u, v, NULL);
00293   if (c)
00294     w = -w;
00295   return w;
00296 }
00297 strong_alias (__divdi3, __divdi3_internal)
00298 
00299 DWtype
00300 __moddi3 (DWtype u, DWtype v)
00301 {
00302   Wtype c = 0;
00303   DWtype w;
00304 
00305   if (u < 0)
00306     {
00307       c = ~c;
00308       u = -u;
00309     }
00310   if (v < 0)
00311     v = -v;
00312   __udivmoddi4 (u, v, (UDWtype *) &w);
00313   if (c)
00314     w = -w;
00315   return w;
00316 }
00317 strong_alias (__moddi3, __moddi3_internal)
00318 
00319 UDWtype
00320 __udivdi3 (UDWtype u, UDWtype v)
00321 {
00322   return __udivmoddi4 (u, v, NULL);
00323 }
00324 strong_alias (__udivdi3, __udivdi3_internal)
00325 
00326 UDWtype
00327 __umoddi3 (UDWtype u, UDWtype v)
00328 {
00329   UDWtype w;
00330 
00331   __udivmoddi4 (u, v, &w);
00332   return w;
00333 }
00334 strong_alias (__umoddi3, __umoddi3_internal)
00335 
00336 /* We declare these with compat_symbol so that they are not visible at
00337    link time.  Programs must use the functions from libgcc.  */
00338 #if defined HAVE_ELF && defined SHARED && defined DO_VERSIONING
00339 # include <shlib-compat.h>
00340 compat_symbol (libc, __divdi3, __divdi3, GLIBC_2_0);
00341 compat_symbol (libc, __moddi3, __moddi3, GLIBC_2_0);
00342 compat_symbol (libc, __udivdi3, __udivdi3, GLIBC_2_0);
00343 compat_symbol (libc, __umoddi3, __umoddi3, GLIBC_2_0);
00344 #endif