sysdeps/wordsize-32/divdi3.c - nest-cam/v366/glibc - Git at Google

 /* 64-bit multiplication and division
    Copyright (C) 1989, 1992-1999,2000,2001,2002,2003,2004,2005
 	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, write to the Free
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */

 #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.  */
 #if defined HAVE_ELF && defined SHARED && defined DO_VERSIONING
 # 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
	/* 64-bit multiplication and division
	Copyright (C) 1989, 1992-1999,2000,2001,2002,2003,2004,2005
	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, write to the Free
	Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
	02111-1307 USA. */

	#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. */
	#if defined HAVE_ELF && defined SHARED && defined DO_VERSIONING
	# 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