sysdeps/wordsize-32/divdi3.c

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