sysdeps/wordsize-32/divdi3.c

   1 /* 64-bit multiplication and division
   2    Copyright (C) 1989, 1992-1999,2000,2001,2002,2003,2004,2005,2012
   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, see
  18    <http://www.gnu.org/licenses/>.  */
  19
  20 #include <endian.h>
  21 #include <stdlib.h>
  22 #include <bits/wordsize.h>
  23
  24 #if __WORDSIZE != 32
  25 #error This is for 32-bit targets only
  26 #endif
  27
  28 typedef unsigned int UQItype    __attribute__ ((mode (QI)));
  29 typedef          int SItype     __attribute__ ((mode (SI)));
  30 typedef unsigned int USItype    __attribute__ ((mode (SI)));
  31 typedef          int DItype     __attribute__ ((mode (DI)));
  32 typedef unsigned int UDItype    __attribute__ ((mode (DI)));
  33 #define Wtype SItype
  34 #define HWtype SItype
  35 #define DWtype DItype
  36 #define UWtype USItype
  37 #define UHWtype USItype
  38 #define UDWtype UDItype
  39 #define W_TYPE_SIZE 32
  40
  41 #include <stdlib/longlong.h>
  42
  43 #if __BYTE_ORDER == __BIG_ENDIAN
  44 struct DWstruct { Wtype high, low;};
  45 #elif __BYTE_ORDER == __LITTLE_ENDIAN
  46 struct DWstruct { Wtype low, high;};
  47 #else
  48 #error Unhandled endianity
  49 #endif
  50 typedef union { struct DWstruct s; DWtype ll; } DWunion;
  51
  52 /* Prototypes of exported functions.  */
  53 extern DWtype __divdi3 (DWtype u, DWtype v);
  54 extern DWtype __moddi3 (DWtype u, DWtype v);
  55 extern UDWtype __udivdi3 (UDWtype u, UDWtype v);
  56 extern UDWtype __umoddi3 (UDWtype u, UDWtype v);
  57
  58 static UDWtype
  59 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
  60 {
  61   DWunion ww;
  62   DWunion nn, dd;
  63   DWunion rr;
  64   UWtype d0, d1, n0, n1, n2;
  65   UWtype q0, q1;
  66   UWtype b, bm;
  67
  68   nn.ll = n;
  69   dd.ll = d;
  70
  71   d0 = dd.s.low;
  72   d1 = dd.s.high;
  73   n0 = nn.s.low;
  74   n1 = nn.s.high;
  75
  76 #if !UDIV_NEEDS_NORMALIZATION
  77   if (d1 == 0)
  78     {
  79       if (d0 > n1)
  80         {
  81           /* 0q = nn / 0D */
  82
  83           udiv_qrnnd (q0, n0, n1, n0, d0);
  84           q1 = 0;
  85
  86           /* Remainder in n0.  */
  87         }
  88       else
  89         {
  90           /* qq = NN / 0d */
  91
  92           if (d0 == 0)
  93             d0 = 1 / d0;        /* Divide intentionally by zero.  */
  94
  95           udiv_qrnnd (q1, n1, 0, n1, d0);
  96           udiv_qrnnd (q0, n0, n1, n0, d0);
  97
  98           /* Remainder in n0.  */
  99         }
 100
 101       if (rp != 0)
 102         {
 103           rr.s.low = n0;
 104           rr.s.high = 0;
 105           *rp = rr.ll;
 106         }
 107     }
 108
 109 #else /* UDIV_NEEDS_NORMALIZATION */
 110
 111   if (d1 == 0)
 112     {
 113       if (d0 > n1)
 114         {
 115           /* 0q = nn / 0D */
 116
 117           count_leading_zeros (bm, d0);
 118
 119           if (bm != 0)
 120             {
 121               /* Normalize, i.e. make the most significant bit of the
 122                  denominator set.  */
 123
 124               d0 = d0 << bm;
 125               n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));
 126               n0 = n0 << bm;
 127             }
 128
 129           udiv_qrnnd (q0, n0, n1, n0, d0);
 130           q1 = 0;
 131
 132           /* Remainder in n0 >> bm.  */
 133         }
 134       else
 135         {
 136           /* qq = NN / 0d */
 137
 138           if (d0 == 0)
 139             d0 = 1 / d0;        /* Divide intentionally by zero.  */
 140
 141           count_leading_zeros (bm, d0);
 142
 143           if (bm == 0)
 144             {
 145               /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
 146                  conclude (the most significant bit of n1 is set) /\ (the
 147                  leading quotient digit q1 = 1).
 148
 149                  This special case is necessary, not an optimization.
 150                  (Shifts counts of W_TYPE_SIZE are undefined.)  */
 151
 152               n1 -= d0;
 153               q1 = 1;
 154             }
 155           else
 156             {
 157               /* Normalize.  */
 158
 159               b = W_TYPE_SIZE - bm;
 160
 161               d0 = d0 << bm;
 162               n2 = n1 >> b;
 163               n1 = (n1 << bm) | (n0 >> b);
 164               n0 = n0 << bm;
 165
 166               udiv_qrnnd (q1, n1, n2, n1, d0);
 167             }
 168
 169           /* n1 != d0...  */
 170
 171           udiv_qrnnd (q0, n0, n1, n0, d0);
 172
 173           /* Remainder in n0 >> bm.  */
 174         }
 175
 176       if (rp != 0)
 177         {
 178           rr.s.low = n0 >> bm;
 179           rr.s.high = 0;
 180           *rp = rr.ll;
 181         }
 182     }
 183 #endif /* UDIV_NEEDS_NORMALIZATION */
 184
 185   else
 186     {
 187       if (d1 > n1)
 188         {
 189           /* 00 = nn / DD */
 190
 191           q0 = 0;
 192           q1 = 0;
 193
 194           /* Remainder in n1n0.  */
 195           if (rp != 0)
 196             {
 197               rr.s.low = n0;
 198               rr.s.high = n1;
 199               *rp = rr.ll;
 200             }
 201         }
 202       else
 203         {
 204           /* 0q = NN / dd */
 205
 206           count_leading_zeros (bm, d1);
 207           if (bm == 0)
 208             {
 209               /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
 210                  conclude (the most significant bit of n1 is set) /\ (the
 211                  quotient digit q0 = 0 or 1).
 212
 213                  This special case is necessary, not an optimization.  */
 214
 215               /* The condition on the next line takes advantage of that
 216                  n1 >= d1 (true due to program flow).  */
 217               if (n1 > d1 || n0 >= d0)
 218                 {
 219                   q0 = 1;
 220                   sub_ddmmss (n1, n0, n1, n0, d1, d0);
 221                 }
 222               else
 223                 q0 = 0;
 224
 225               q1 = 0;
 226
 227               if (rp != 0)
 228                 {
 229                   rr.s.low = n0;
 230                   rr.s.high = n1;
 231                   *rp = rr.ll;
 232                 }
 233             }
 234           else
 235             {
 236               UWtype m1, m0;
 237               /* Normalize.  */
 238
 239               b = W_TYPE_SIZE - bm;
 240
 241               d1 = (d1 << bm) | (d0 >> b);
 242               d0 = d0 << bm;
 243               n2 = n1 >> b;
 244               n1 = (n1 << bm) | (n0 >> b);
 245               n0 = n0 << bm;
 246
 247               udiv_qrnnd (q0, n1, n2, n1, d1);
 248               umul_ppmm (m1, m0, q0, d0);
 249
 250               if (m1 > n1 || (m1 == n1 && m0 > n0))
 251                 {
 252                   q0--;
 253                   sub_ddmmss (m1, m0, m1, m0, d1, d0);
 254                 }
 255
 256               q1 = 0;
 257
 258               /* Remainder in (n1n0 - m1m0) >> bm.  */
 259               if (rp != 0)
 260                 {
 261                   sub_ddmmss (n1, n0, n1, n0, m1, m0);
 262                   rr.s.low = (n1 << b) | (n0 >> bm);
 263                   rr.s.high = n1 >> bm;
 264                   *rp = rr.ll;
 265                 }
 266             }
 267         }
 268     }
 269
 270   ww.s.low = q0;
 271   ww.s.high = q1;
 272   return ww.ll;
 273 }
 274
 275 DWtype
 276 __divdi3 (DWtype u, DWtype v)
 277 {
 278   Wtype c = 0;
 279   DWtype w;
 280
 281   if (u < 0)
 282     {
 283       c = ~c;
 284       u = -u;
 285     }
 286   if (v < 0)
 287     {
 288       c = ~c;
 289       v = -v;
 290     }
 291   w = __udivmoddi4 (u, v, NULL);
 292   if (c)
 293     w = -w;
 294   return w;
 295 }
 296 strong_alias (__divdi3, __divdi3_internal)
 297
 298 DWtype
 299 __moddi3 (DWtype u, DWtype v)
 300 {
 301   Wtype c = 0;
 302   DWtype w;
 303
 304   if (u < 0)
 305     {
 306       c = ~c;
 307       u = -u;
 308     }
 309   if (v < 0)
 310     v = -v;
 311   __udivmoddi4 (u, v, (UDWtype *) &w);
 312   if (c)
 313     w = -w;
 314   return w;
 315 }
 316 strong_alias (__moddi3, __moddi3_internal)
 317
 318 UDWtype
 319 __udivdi3 (UDWtype u, UDWtype v)
 320 {
 321   return __udivmoddi4 (u, v, NULL);
 322 }
 323 strong_alias (__udivdi3, __udivdi3_internal)
 324
 325 UDWtype
 326 __umoddi3 (UDWtype u, UDWtype v)
 327 {
 328   UDWtype w;
 329
 330   __udivmoddi4 (u, v, &w);
 331   return w;
 332 }
 333 strong_alias (__umoddi3, __umoddi3_internal)
 334
 335 /* We declare these with compat_symbol so that they are not visible at
 336    link time.  Programs must use the functions from libgcc.  */
 337 #if defined SHARED && defined DO_VERSIONING
 338 # include <shlib-compat.h>
 339 compat_symbol (libc, __divdi3, __divdi3, GLIBC_2_0);
 340 compat_symbol (libc, __moddi3, __moddi3, GLIBC_2_0);
 341 compat_symbol (libc, __udivdi3, __udivdi3, GLIBC_2_0);
 342 compat_symbol (libc, __umoddi3, __umoddi3, GLIBC_2_0);
 343 #endif