git.oblomov.eu Git - linux-2.6/blob - arch/arm/lib/udivdi3.c

   1 /* More subroutines needed by GCC output code on some machines.  */
   2 /* Compile this one with gcc.  */
   3 /* Copyright (C) 1989, 92-98, 1999 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* As a special exception, if you link this library with other files,
  23    some of which are compiled with GCC, to produce an executable,
  24    this library does not by itself cause the resulting executable
  25    to be covered by the GNU General Public License.
  26    This exception does not however invalidate any other reasons why
  27    the executable file might be covered by the GNU General Public License.
  28  */
  29 /* support functions required by the kernel. based on code from gcc-2.95.3 */
  30 /* I Molton     29/07/01 */
  31
  32 #include "gcclib.h"
  33 #include "longlong.h"
  34
  35 static const u8 __clz_tab[] =
  36 {
  37   0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  38   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  39   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  40   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  41   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  42   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  43   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  44   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  45 };
  46
  47 u64
  48 __udivmoddi4 (u64 n, u64 d, u64 *rp)
  49 {
  50   DIunion ww;
  51   DIunion nn, dd;
  52   DIunion rr;
  53   u32 d0, d1, n0, n1, n2;
  54   u32 q0, q1;
  55   u32 b, bm;
  56
  57   nn.ll = n;
  58   dd.ll = d;
  59
  60   d0 = dd.s.low;
  61   d1 = dd.s.high;
  62   n0 = nn.s.low;
  63   n1 = nn.s.high;
  64
  65   if (d1 == 0)
  66     {
  67       if (d0 > n1)
  68         {
  69           /* 0q = nn / 0D */
  70
  71           count_leading_zeros (bm, d0);
  72
  73           if (bm != 0)
  74             {
  75               /* Normalize, i.e. make the most significant bit of the
  76                  denominator set.  */
  77
  78               d0 = d0 << bm;
  79               n1 = (n1 << bm) | (n0 >> (SI_TYPE_SIZE - bm));
  80               n0 = n0 << bm;
  81             }
  82
  83           udiv_qrnnd (q0, n0, n1, n0, d0);
  84           q1 = 0;
  85
  86           /* Remainder in n0 >> bm.  */
  87         }
  88       else
  89         {
  90           /* qq = NN / 0d */
  91
  92           if (d0 == 0)
  93             d0 = 1 / d0;        /* Divide intentionally by zero.  */
  94
  95           count_leading_zeros (bm, d0);
  96
  97           if (bm == 0)
  98             {
  99               /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
 100                  conclude (the most significant bit of n1 is set) /\ (the
 101                  leading quotient digit q1 = 1).
 102
 103                  This special case is necessary, not an optimization.
 104                  (Shifts counts of SI_TYPE_SIZE are undefined.)  */
 105
 106               n1 -= d0;
 107               q1 = 1;
 108             }
 109           else
 110             {
 111               /* Normalize.  */
 112
 113               b = SI_TYPE_SIZE - bm;
 114
 115               d0 = d0 << bm;
 116               n2 = n1 >> b;
 117               n1 = (n1 << bm) | (n0 >> b);
 118               n0 = n0 << bm;
 119
 120               udiv_qrnnd (q1, n1, n2, n1, d0);
 121             }
 122
 123           /* n1 != d0...  */
 124
 125           udiv_qrnnd (q0, n0, n1, n0, d0);
 126
 127           /* Remainder in n0 >> bm.  */
 128         }
 129
 130       if (rp != 0)
 131         {
 132           rr.s.low = n0 >> bm;
 133           rr.s.high = 0;
 134           *rp = rr.ll;
 135         }
 136     }
 137   else
 138     {
 139       if (d1 > n1)
 140         {
 141           /* 00 = nn / DD */
 142
 143           q0 = 0;
 144           q1 = 0;
 145
 146           /* Remainder in n1n0.  */
 147           if (rp != 0)
 148             {
 149               rr.s.low = n0;
 150               rr.s.high = n1;
 151               *rp = rr.ll;
 152             }
 153         }
 154       else
 155         {
 156           /* 0q = NN / dd */
 157
 158           count_leading_zeros (bm, d1);
 159           if (bm == 0)
 160             {
 161               /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
 162                  conclude (the most significant bit of n1 is set) /\ (the
 163                  quotient digit q0 = 0 or 1).
 164
 165                  This special case is necessary, not an optimization.  */
 166
 167               /* The condition on the next line takes advantage of that
 168                  n1 >= d1 (true due to program flow).  */
 169               if (n1 > d1 || n0 >= d0)
 170                 {
 171                   q0 = 1;
 172                   sub_ddmmss (n1, n0, n1, n0, d1, d0);
 173                 }
 174               else
 175                 q0 = 0;
 176
 177               q1 = 0;
 178
 179               if (rp != 0)
 180                 {
 181                   rr.s.low = n0;
 182                   rr.s.high = n1;
 183                   *rp = rr.ll;
 184                 }
 185             }
 186           else
 187             {
 188               u32 m1, m0;
 189               /* Normalize.  */
 190
 191               b = SI_TYPE_SIZE - bm;
 192
 193               d1 = (d1 << bm) | (d0 >> b);
 194               d0 = d0 << bm;
 195               n2 = n1 >> b;
 196               n1 = (n1 << bm) | (n0 >> b);
 197               n0 = n0 << bm;
 198
 199               udiv_qrnnd (q0, n1, n2, n1, d1);
 200               umul_ppmm (m1, m0, q0, d0);
 201
 202               if (m1 > n1 || (m1 == n1 && m0 > n0))
 203                 {
 204                   q0--;
 205                   sub_ddmmss (m1, m0, m1, m0, d1, d0);
 206                 }
 207
 208               q1 = 0;
 209
 210               /* Remainder in (n1n0 - m1m0) >> bm.  */
 211               if (rp != 0)
 212                 {
 213                   sub_ddmmss (n1, n0, n1, n0, m1, m0);
 214                   rr.s.low = (n1 << b) | (n0 >> bm);
 215                   rr.s.high = n1 >> bm;
 216                   *rp = rr.ll;
 217                 }
 218             }
 219         }
 220     }
 221
 222   ww.s.low = q0;
 223   ww.s.high = q1;
 224   return ww.ll;
 225 }
 226
 227 u64
 228 __udivdi3 (u64 n, u64 d)
 229 {
 230   return __udivmoddi4 (n, d, (u64 *) 0);
 231 }
 232
 233 u64
 234 __umoddi3 (u64 u, u64 v)
 235 {
 236   u64 w;
 237
 238   (void) __udivmoddi4 (u ,v, &w);
 239
 240   return w;
 241 }
 242