/* 64-bit multiplication and division

   Copyright (C) 1989, 1992-2018 Free Software Foundation, Inc.

   This file is part of the GNU C Library.

   The GNU C Library is free software; you can redistribute it and/or

   modify it under the terms of the GNU Lesser General Public

   License as published by the Free Software Foundation; either

   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library 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

   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public

   License along with the GNU C Library; if not, see

   <http://www.gnu.org/licenses/>.  */

#include <endian.h>

#include <stdlib.h>

#include <bits/wordsize.h>

#if __WORDSIZE != 32

#error This is for 32-bit targets only

#endif

typedef unsigned int UQItype	__attribute__ ((mode (QI)));

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 Wtype SItype

#define HWtype SItype

#define DWtype DItype

#define UWtype USItype

#define UHWtype USItype

#define UDWtype UDItype

#define W_TYPE_SIZE 32

#include <stdlib/longlong.h>

#if __BYTE_ORDER == __BIG_ENDIAN

struct DWstruct { Wtype high, low;};

#elif __BYTE_ORDER == __LITTLE_ENDIAN

struct DWstruct { Wtype low, high;};

#else

#error Unhandled endianity

#endif

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

/* Prototypes of exported functions.  */

extern DWtype __divdi3 (DWtype u, DWtype v);

extern DWtype __moddi3 (DWtype u, DWtype v);

extern UDWtype __udivdi3 (UDWtype u, UDWtype v);

extern UDWtype __umoddi3 (UDWtype u, UDWtype v);

static UDWtype

__udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)

{

  DWunion ww;

  DWunion nn, dd;

  DWunion rr;

  UWtype d0, d1, n0, n1, n2;

  UWtype q0, q1;

  UWtype b, bm;

  nn.ll = n;

  dd.ll = d;

  d0 = dd.s.low;

  d1 = dd.s.high;

  n0 = nn.s.low;

  n1 = nn.s.high;

#if !UDIV_NEEDS_NORMALIZATION

  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 /* UDIV_NEEDS_NORMALIZATION */

  if (d1 == 0)

    {

      if (d0 > n1)

	{

	  /* 0q = nn / 0D */

	  count_leading_zeros (bm, d0);

	  if (bm != 0)

	    {

	      /* Normalize, i.e. make the most significant bit of the

		 denominator set.  */

	      d0 = d0 << bm;

	      n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));

	      n0 = n0 << bm;

	    }

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

	  q1 = 0;

	  /* Remainder in n0 >> bm.  */

	}

      else

	{

	  /* qq = NN / 0d */

	  if (d0 == 0)

	    d0 = 1 / d0;	/* Divide intentionally by zero.  */

	  count_leading_zeros (bm, d0);

	  if (bm == 0)

	    {

	      /* From (n1 >= d0) /\ (the most significant bit of d0 is set),

		 conclude (the most significant bit of n1 is set) /\ (the

		 leading quotient digit q1 = 1).

		 This special case is necessary, not an optimization.

		 (Shifts counts of W_TYPE_SIZE are undefined.)  */

	      n1 -= d0;

	      q1 = 1;

	    }

	  else

	    {

	      /* Normalize.  */

	      b = W_TYPE_SIZE - bm;

	      d0 = d0 << bm;

	      n2 = n1 >> b;

	      n1 = (n1 << bm) | (n0 >> b);

	      n0 = n0 << bm;

	      udiv_qrnnd (q1, n1, n2, n1, d0);

	    }

	  /* n1 != d0...  */

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

	  /* Remainder in n0 >> bm.  */

	}

      if (rp != 0)

	{

	  rr.s.low = n0 >> bm;

	  rr.s.high = 0;

	  *rp = rr.ll;

	}

    }

#endif /* UDIV_NEEDS_NORMALIZATION */

  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;

		}

	    }

	}

    }

  ww.s.low = q0;

  ww.s.high = q1;

  return ww.ll;

}

DWtype

__divdi3 (DWtype u, DWtype v)

{

  Wtype c = 0;

  DWtype w;

  if (u < 0)

    {

      c = ~c;

      u = -u;

    }

  if (v < 0)

    {

      c = ~c;

      v = -v;

    }

  w = __udivmoddi4 (u, v, NULL);

  if (c)

    w = -w;

  return w;

}

strong_alias (__divdi3, __divdi3_internal)

DWtype

__moddi3 (DWtype u, DWtype v)

{

  Wtype c = 0;

  DWtype w;

  if (u < 0)

    {

      c = ~c;

      u = -u;

    }

  if (v < 0)

    v = -v;

  __udivmoddi4 (u, v, (UDWtype *) &w);

  if (c)

    w = -w;

  return w;

}

strong_alias (__moddi3, __moddi3_internal)

UDWtype

__udivdi3 (UDWtype u, UDWtype v)

{

  return __udivmoddi4 (u, v, NULL);

}

strong_alias (__udivdi3, __udivdi3_internal)

UDWtype

__umoddi3 (UDWtype u, UDWtype v)

{

  UDWtype w;

  __udivmoddi4 (u, v, &w);

  return w;

}

strong_alias (__umoddi3, __umoddi3_internal)

/* We declare these with compat_symbol so that they are not visible at

   link time.  Programs must use the functions from libgcc.  */

#ifdef SHARED

# include <shlib-compat.h>

compat_symbol (libc, __divdi3, __divdi3, GLIBC_2_0);

compat_symbol (libc, __moddi3, __moddi3, GLIBC_2_0);

compat_symbol (libc, __udivdi3, __udivdi3, GLIBC_2_0);

compat_symbol (libc, __umoddi3, __umoddi3, GLIBC_2_0);

#endif