sysdeps/wordsize-32/divdi3.c

   1 /* 64-bit multiplication and division
   2    Copyright (C) 1989, 1992-1999, 2000, 2001, 2002
   3    Free Software Foundation, Inc.
   4    This file is part of the GNU C Library.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #include <endian.h>
  22 #include <stdlib.h>
  23 #include <bits/wordsize.h>
  24
  25 #if __WORDSIZE != 32
  26 #error This is for 32-bit targets only
  27 #endif
  28
  29 typedef unsigned int UQItype    __attribute__ ((mode (QI)));
  30 typedef          int SItype     __attribute__ ((mode (SI)));
  31 typedef unsigned int USItype    __attribute__ ((mode (SI)));
  32 typedef          int DItype     __attribute__ ((mode (DI)));
  33 typedef unsigned int UDItype    __attribute__ ((mode (DI)));
  34 #define Wtype SItype
  35 #define HWtype SItype
  36 #define DWtype DItype
  37 #define UWtype USItype
  38 #define UHWtype USItype
  39 #define UDWtype UDItype
  40 #define W_TYPE_SIZE 32
  41
  42 #include <stdlib/longlong.h>
  43
  44 #if __BYTE_ORDER == __BIG_ENDIAN
  45 struct DWstruct { Wtype high, low;};
  46 #elif __BYTE_ORDER == __LITTLE_ENDIAN
  47 struct DWstruct { Wtype low, high;};
  48 #else
  49 #error Unhandled endianity
  50 #endif
  51 typedef union { struct DWstruct s; DWtype ll; } DWunion;
  52
  53 /* Prototypes of exported functions.  */
  54 extern DWtype __divdi3 (DWtype u, DWtype v);
  55 extern DWtype __moddi3 (DWtype u, DWtype v);
  56 extern UDWtype __udivdi3 (UDWtype u, UDWtype v);
  57 extern UDWtype __umoddi3 (UDWtype u, UDWtype v);
  58
  59 static UDWtype
  60 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
  61 {
  62   DWunion ww;
  63   DWunion nn, dd;
  64   DWunion rr;
  65   UWtype d0, d1, n0, n1, n2;
  66   UWtype q0, q1;
  67   UWtype b, bm;
  68
  69   nn.ll = n;
  70   dd.ll = d;
  71
  72   d0 = dd.s.low;
  73   d1 = dd.s.high;
  74   n0 = nn.s.low;
  75   n1 = nn.s.high;
  76
  77 #if !UDIV_NEEDS_NORMALIZATION
  78   if (d1 == 0)
  79     {
  80       if (d0 > n1)
  81         {
  82           /* 0q = nn / 0D */
  83
  84           udiv_qrnnd (q0, n0, n1, n0, d0);
  85           q1 = 0;
  86
  87           /* Remainder in n0.  */
  88         }
  89       else
  90         {
  91           /* qq = NN / 0d */
  92
  93           if (d0 == 0)
  94             d0 = 1 / d0;        /* Divide intentionally by zero.  */
  95
  96           udiv_qrnnd (q1, n1, 0, n1, d0);
  97           udiv_qrnnd (q0, n0, n1, n0, d0);
  98
  99           /* Remainder in n0.  */
 100         }
 101
 102       if (rp != 0)
 103         {
 104           rr.s.low = n0;
 105           rr.s.high = 0;
 106           *rp = rr.ll;
 107         }
 108     }
 109
 110 #else /* UDIV_NEEDS_NORMALIZATION */
 111
 112   if (d1 == 0)
 113     {
 114       if (d0 > n1)
 115         {
 116           /* 0q = nn / 0D */
 117
 118           count_leading_zeros (bm, d0);
 119
 120           if (bm != 0)
 121             {
 122               /* Normalize, i.e. make the most significant bit of the
 123                  denominator set.  */
 124
 125               d0 = d0 << bm;
 126               n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));
 127               n0 = n0 << bm;
 128             }
 129
 130           udiv_qrnnd (q0, n0, n1, n0, d0);
 131           q1 = 0;
 132
 133           /* Remainder in n0 >> bm.  */
 134         }
 135       else
 136         {
 137           /* qq = NN / 0d */
 138
 139           if (d0 == 0)
 140             d0 = 1 / d0;        /* Divide intentionally by zero.  */
 141
 142           count_leading_zeros (bm, d0);
 143
 144           if (bm == 0)
 145             {
 146               /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
 147                  conclude (the most significant bit of n1 is set) /\ (the
 148                  leading quotient digit q1 = 1).
 149
 150                  This special case is necessary, not an optimization.
 151                  (Shifts counts of W_TYPE_SIZE are undefined.)  */
 152
 153               n1 -= d0;
 154               q1 = 1;
 155             }
 156           else
 157             {
 158               /* Normalize.  */
 159
 160               b = W_TYPE_SIZE - bm;
 161
 162               d0 = d0 << bm;
 163               n2 = n1 >> b;
 164               n1 = (n1 << bm) | (n0 >> b);
 165               n0 = n0 << bm;
 166
 167               udiv_qrnnd (q1, n1, n2, n1, d0);
 168             }
 169
 170           /* n1 != d0...  */
 171
 172           udiv_qrnnd (q0, n0, n1, n0, d0);
 173
 174           /* Remainder in n0 >> bm.  */
 175         }
 176
 177       if (rp != 0)
 178         {
 179           rr.s.low = n0 >> bm;
 180           rr.s.high = 0;
 181           *rp = rr.ll;
 182         }
 183     }
 184 #endif /* UDIV_NEEDS_NORMALIZATION */
 185
 186   else
 187     {
 188       if (d1 > n1)
 189         {
 190           /* 00 = nn / DD */
 191
 192           q0 = 0;
 193           q1 = 0;
 194
 195           /* Remainder in n1n0.  */
 196           if (rp != 0)
 197             {
 198               rr.s.low = n0;
 199               rr.s.high = n1;
 200               *rp = rr.ll;
 201             }
 202         }
 203       else
 204         {
 205           /* 0q = NN / dd */
 206
 207           count_leading_zeros (bm, d1);
 208           if (bm == 0)
 209             {
 210               /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
 211                  conclude (the most significant bit of n1 is set) /\ (the
 212                  quotient digit q0 = 0 or 1).
 213
 214                  This special case is necessary, not an optimization.  */
 215
 216               /* The condition on the next line takes advantage of that
 217                  n1 >= d1 (true due to program flow).  */
 218               if (n1 > d1 || n0 >= d0)
 219                 {
 220                   q0 = 1;
 221                   sub_ddmmss (n1, n0, n1, n0, d1, d0);
 222                 }
 223               else
 224                 q0 = 0;
 225
 226               q1 = 0;
 227
 228               if (rp != 0)
 229                 {
 230                   rr.s.low = n0;
 231                   rr.s.high = n1;
 232                   *rp = rr.ll;
 233                 }
 234             }
 235           else
 236             {
 237               UWtype m1, m0;
 238               /* Normalize.  */
 239
 240               b = W_TYPE_SIZE - bm;
 241
 242               d1 = (d1 << bm) | (d0 >> b);
 243               d0 = d0 << bm;
 244               n2 = n1 >> b;
 245               n1 = (n1 << bm) | (n0 >> b);
 246               n0 = n0 << bm;
 247
 248               udiv_qrnnd (q0, n1, n2, n1, d1);
 249               umul_ppmm (m1, m0, q0, d0);
 250
 251               if (m1 > n1 || (m1 == n1 && m0 > n0))
 252                 {
 253                   q0--;
 254                   sub_ddmmss (m1, m0, m1, m0, d1, d0);
 255                 }
 256
 257               q1 = 0;
 258
 259               /* Remainder in (n1n0 - m1m0) >> bm.  */
 260               if (rp != 0)
 261                 {
 262                   sub_ddmmss (n1, n0, n1, n0, m1, m0);
 263                   rr.s.low = (n1 << b) | (n0 >> bm);
 264                   rr.s.high = n1 >> bm;
 265                   *rp = rr.ll;
 266                 }
 267             }
 268         }
 269     }
 270
 271   ww.s.low = q0;
 272   ww.s.high = q1;
 273   return ww.ll;
 274 }
 275
 276 DWtype
 277 __divdi3 (DWtype u, DWtype v)
 278 {
 279   Wtype c = 0;
 280   DWtype w;
 281
 282   if (u < 0)
 283     {
 284       c = ~c;
 285       u = -u;
 286     }
 287   if (v < 0)
 288     {
 289       c = ~c;
 290       v = -v;
 291     }
 292   w = __udivmoddi4 (u, v, NULL);
 293   if (c)
 294     w = -w;
 295   return w;
 296 }
 297 INTDEF(__divdi3)
 298
 299 DWtype
 300 __moddi3 (DWtype u, DWtype v)
 301 {
 302   Wtype c = 0;
 303   DWtype w;
 304
 305   if (u < 0)
 306     {
 307       c = ~c;
 308       u = -u;
 309     }
 310   if (v < 0)
 311     v = -v;
 312   __udivmoddi4 (u, v, &w);
 313   if (c)
 314     w = -w;
 315   return w;
 316 }
 317
 318 UDWtype
 319 __udivdi3 (UDWtype u, UDWtype v)
 320 {
 321   return __udivmoddi4 (u, v, NULL);
 322 }
 323
 324 UDWtype
 325 __umoddi3 (UDWtype u, UDWtype v)
 326 {
 327   UDWtype w;
 328
 329   __udivmoddi4 (u, v, &w);
 330   return w;
 331 }