grub-0.97/stage2/moddiv.c

/* Header file for libgcc2.c.  */
/* Copyright (C) 2000, 2001, 2004, 2005, 2009
   Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

Under Section 7 of GPL version 3, you are granted additional
permissions described in the GCC Runtime Library Exception, version
3.1, as published by the Free Software Foundation.

You should have received a copy of the GNU General Public License and
a copy of the GCC Runtime Library Exception along with this program;
see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
<http://www.gnu.org/licenses/>.  */

typedef      int SItype __attribute__ ((mode (SI)));
typedef unsigned int USItype    __attribute__ ((mode (SI)));
typedef      int DItype __attribute__ ((mode (DI)));
typedef unsigned int UDItype    __attribute__ ((mode (DI)));

#define BITS_PER_UNIT 8
#define W_TYPE_SIZE (4 * BITS_PER_UNIT)
#define Wtype   SItype
#define DWtype  DItype
#define UWtype  USItype
#define UDWtype UDItype

struct DWstruct {Wtype low, high;};

typedef union
{
  struct DWstruct s;
  DWtype ll;
} DWunion;

#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
  __asm__ ("sub{l} {%5,%1|%1,%5}\n\tsbb{l} {%3,%0|%0,%3}"       \
       : "=r" ((USItype) (sh)),                 \
         "=&r" ((USItype) (sl))                 \
       : "0" ((USItype) (ah)),                  \
         "g" ((USItype) (bh)),                  \
         "1" ((USItype) (al)),                  \
         "g" ((USItype) (bl)))

#define umul_ppmm(w1, w0, u, v) \
  __asm__ ("mul{l} %3"                          \
       : "=a" ((USItype) (w0)),                 \
         "=d" ((USItype) (w1))                  \
       : "%0" ((USItype) (u)),                  \
         "rm" ((USItype) (v)))
#define udiv_qrnnd(q, r, n1, n0, dv) \
  __asm__ ("div{l} %4"                          \
       : "=a" ((USItype) (q)),                  \
         "=d" ((USItype) (r))                   \
       : "0" ((USItype) (n0)),                  \
         "1" ((USItype) (n1)),                  \
         "rm" ((USItype) (dv)))

#define count_leading_zeros(count, x)   ((count) = __builtin_clz (x))

UDWtype
__udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
{
  const DWunion nn = {.ll = n};
  const DWunion dd = {.ll = d};
  DWunion rr;
  UWtype d0, d1, n0, n1, n2;
  UWtype q0, q1;
  UWtype b, bm;

  d0 = dd.s.low;
  d1 = dd.s.high;
  n0 = nn.s.low;
  n1 = nn.s.high;

  if (d1 == 0)
    {
      if (d0 > n1)
    {
      /* 0q = nn / 0D */

      udiv_qrnnd (q0, n0, n1, n0, d0);
      q1 = 0;

      /* Remainder in n0.  */
    }
      else
    {
      /* qq = NN / 0d */

      if (d0 == 0)
        d0 = 1 / d0;    /* Divide intentionally by zero.  */

      udiv_qrnnd (q1, n1, 0, n1, d0);
      udiv_qrnnd (q0, n0, n1, n0, d0);

      /* Remainder in n0.  */
    }

      if (rp != 0)
    {
      rr.s.low = n0;
      rr.s.high = 0;
      *rp = rr.ll;
    }
    }


  else
    {
      if (d1 > n1)
    {
      /* 00 = nn / DD */

      q0 = 0;
      q1 = 0;

      /* Remainder in n1n0.  */
      if (rp != 0)
        {
          rr.s.low = n0;
          rr.s.high = n1;
          *rp = rr.ll;
        }
    }
      else
    {
      /* 0q = NN / dd */

      count_leading_zeros (bm, d1);
      if (bm == 0)
        {
          /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
         conclude (the most significant bit of n1 is set) /\ (the
         quotient digit q0 = 0 or 1).

         This special case is necessary, not an optimization.  */

          /* The condition on the next line takes advantage of that
         n1 >= d1 (true due to program flow).  */
          if (n1 > d1 || n0 >= d0)
        {
          q0 = 1;
          sub_ddmmss (n1, n0, n1, n0, d1, d0);
        }
          else
        q0 = 0;

          q1 = 0;

          if (rp != 0)
        {
          rr.s.low = n0;
          rr.s.high = n1;
          *rp = rr.ll;
        }
        }
      else
        {
          UWtype m1, m0;
          /* Normalize.  */

          b = W_TYPE_SIZE - bm;

          d1 = (d1 << bm) | (d0 >> b);
          d0 = d0 << bm;
          n2 = n1 >> b;
          n1 = (n1 << bm) | (n0 >> b);
          n0 = n0 << bm;

          udiv_qrnnd (q0, n1, n2, n1, d1);
          umul_ppmm (m1, m0, q0, d0);

          if (m1 > n1 || (m1 == n1 && m0 > n0))
        {
          q0--;
          sub_ddmmss (m1, m0, m1, m0, d1, d0);
        }

          q1 = 0;

          /* Remainder in (n1n0 - m1m0) >> bm.  */
          if (rp != 0)
        {
          sub_ddmmss (n1, n0, n1, n0, m1, m0);
          rr.s.low = (n1 << b) | (n0 >> bm);
          rr.s.high = n1 >> bm;
          *rp = rr.ll;
        }
        }
    }
    }

  const DWunion ww = {{.low = q0, .high = q1}};
  return ww.ll;
}

UDWtype
__udivdi3 (UDWtype n, UDWtype d)
{
  return __udivmoddi4 (n, d, (UDWtype *) 0);
}

UDWtype
__umoddi3 (UDWtype u, UDWtype v)
{
  UDWtype w;

  (void) __udivmoddi4 (u, v, &w);

  return w;
}