usr/src/grub/grub-0.97/stage2/moddiv.c

   1 /* Header file for libgcc2.c.  */
   2 /* Copyright (C) 2000, 2001, 2004, 2005, 2009
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 Under Section 7 of GPL version 3, you are granted additional
  18 permissions described in the GCC Runtime Library Exception, version
  19 3.1, as published by the Free Software Foundation.
  20
  21 You should have received a copy of the GNU General Public License and
  22 a copy of the GCC Runtime Library Exception along with this program;
  23 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 <http://www.gnu.org/licenses/>.  */
  25
  26 typedef          int SItype     __attribute__ ((mode (SI)));
  27 typedef unsigned int USItype    __attribute__ ((mode (SI)));
  28 typedef          int DItype     __attribute__ ((mode (DI)));
  29 typedef unsigned int UDItype    __attribute__ ((mode (DI)));
  30
  31 #define BITS_PER_UNIT 8
  32 #define W_TYPE_SIZE (4 * BITS_PER_UNIT)
  33 #define Wtype   SItype
  34 #define DWtype  DItype
  35 #define UWtype  USItype
  36 #define UDWtype UDItype
  37
  38 struct DWstruct {Wtype low, high;};
  39
  40 typedef union
  41 {
  42   struct DWstruct s;
  43   DWtype ll;
  44 } DWunion;
  45
  46 #define sub_ddmmss(sh, sl, ah, al, bh, bl) \
  47   __asm__ ("sub{l} {%5,%1|%1,%5}\n\tsbb{l} {%3,%0|%0,%3}"               \
  48            : "=r" ((USItype) (sh)),                                     \
  49              "=&r" ((USItype) (sl))                                     \
  50            : "0" ((USItype) (ah)),                                      \
  51              "g" ((USItype) (bh)),                                      \
  52              "1" ((USItype) (al)),                                      \
  53              "g" ((USItype) (bl)))
  54
  55 #define umul_ppmm(w1, w0, u, v) \
  56   __asm__ ("mul{l} %3"                                                  \
  57            : "=a" ((USItype) (w0)),                                     \
  58              "=d" ((USItype) (w1))                                      \
  59            : "%0" ((USItype) (u)),                                      \
  60              "rm" ((USItype) (v)))
  61 #define udiv_qrnnd(q, r, n1, n0, dv) \
  62   __asm__ ("div{l} %4"                                                  \
  63            : "=a" ((USItype) (q)),                                      \
  64              "=d" ((USItype) (r))                                       \
  65            : "0" ((USItype) (n0)),                                      \
  66              "1" ((USItype) (n1)),                                      \
  67              "rm" ((USItype) (dv)))
  68
  69 #define count_leading_zeros(count, x)   ((count) = __builtin_clz (x))
  70
  71 UDWtype
  72 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
  73 {
  74   const DWunion nn = {.ll = n};
  75   const DWunion dd = {.ll = d};
  76   DWunion rr;
  77   UWtype d0, d1, n0, n1, n2;
  78   UWtype q0, q1;
  79   UWtype b, bm;
  80
  81   d0 = dd.s.low;
  82   d1 = dd.s.high;
  83   n0 = nn.s.low;
  84   n1 = nn.s.high;
  85
  86   if (d1 == 0)
  87     {
  88       if (d0 > n1)
  89         {
  90           /* 0q = nn / 0D */
  91
  92           udiv_qrnnd (q0, n0, n1, n0, d0);
  93           q1 = 0;
  94
  95           /* Remainder in n0.  */
  96         }
  97       else
  98         {
  99           /* qq = NN / 0d */
 100
 101           if (d0 == 0)
 102             d0 = 1 / d0;        /* Divide intentionally by zero.  */
 103
 104           udiv_qrnnd (q1, n1, 0, n1, d0);
 105           udiv_qrnnd (q0, n0, n1, n0, d0);
 106
 107           /* Remainder in n0.  */
 108         }
 109
 110       if (rp != 0)
 111         {
 112           rr.s.low = n0;
 113           rr.s.high = 0;
 114           *rp = rr.ll;
 115         }
 116     }
 117
 118
 119   else
 120     {
 121       if (d1 > n1)
 122         {
 123           /* 00 = nn / DD */
 124
 125           q0 = 0;
 126           q1 = 0;
 127
 128           /* Remainder in n1n0.  */
 129           if (rp != 0)
 130             {
 131               rr.s.low = n0;
 132               rr.s.high = n1;
 133               *rp = rr.ll;
 134             }
 135         }
 136       else
 137         {
 138           /* 0q = NN / dd */
 139
 140           count_leading_zeros (bm, d1);
 141           if (bm == 0)
 142             {
 143               /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
 144                  conclude (the most significant bit of n1 is set) /\ (the
 145                  quotient digit q0 = 0 or 1).
 146
 147                  This special case is necessary, not an optimization.  */
 148
 149               /* The condition on the next line takes advantage of that
 150                  n1 >= d1 (true due to program flow).  */
 151               if (n1 > d1 || n0 >= d0)
 152                 {
 153                   q0 = 1;
 154                   sub_ddmmss (n1, n0, n1, n0, d1, d0);
 155                 }
 156               else
 157                 q0 = 0;
 158
 159               q1 = 0;
 160
 161               if (rp != 0)
 162                 {
 163                   rr.s.low = n0;
 164                   rr.s.high = n1;
 165                   *rp = rr.ll;
 166                 }
 167             }
 168           else
 169             {
 170               UWtype m1, m0;
 171               /* Normalize.  */
 172
 173               b = W_TYPE_SIZE - bm;
 174
 175               d1 = (d1 << bm) | (d0 >> b);
 176               d0 = d0 << bm;
 177               n2 = n1 >> b;
 178               n1 = (n1 << bm) | (n0 >> b);
 179               n0 = n0 << bm;
 180
 181               udiv_qrnnd (q0, n1, n2, n1, d1);
 182               umul_ppmm (m1, m0, q0, d0);
 183
 184               if (m1 > n1 || (m1 == n1 && m0 > n0))
 185                 {
 186                   q0--;
 187                   sub_ddmmss (m1, m0, m1, m0, d1, d0);
 188                 }
 189
 190               q1 = 0;
 191
 192               /* Remainder in (n1n0 - m1m0) >> bm.  */
 193               if (rp != 0)
 194                 {
 195                   sub_ddmmss (n1, n0, n1, n0, m1, m0);
 196                   rr.s.low = (n1 << b) | (n0 >> bm);
 197                   rr.s.high = n1 >> bm;
 198                   *rp = rr.ll;
 199                 }
 200             }
 201         }
 202     }
 203
 204   const DWunion ww = {{.low = q0, .high = q1}};
 205   return ww.ll;
 206 }
 207
 208 UDWtype
 209 __udivdi3 (UDWtype n, UDWtype d)
 210 {
 211   return __udivmoddi4 (n, d, (UDWtype *) 0);
 212 }
 213
 214 UDWtype
 215 __umoddi3 (UDWtype u, UDWtype v)
 216 {
 217   UDWtype w;
 218
 219   (void) __udivmoddi4 (u, v, &w);
 220
 221   return w;
 222 }