#include "lldefs.h"

extern void __ull_divrem_6416 (ulonglong_t *q, ulonglong_t *r, ulonglong_t n, ulonglong_t d);
extern void __ull_divrem_5353 (ulonglong_t *q, ulonglong_t *r, ulonglong_t n, ulonglong_t d);
static void __ull_divrem_6464 (llvalue *aquo, llvalue *arem, llvalue num, llvalue denom);

#define pow2_16	65536	/* 2^16 */
#define pow2_21	2097152	/* 2^(53-32) */

/* Given an unsigned64 number, return the number of left-shifts required
  to normalize it (causing high-order digit to be 1) */
static 
unsigned
ll_firstbit(llvalue number)
{
	unsigned bias = 0;

	if (MSW(number) == 0) {
		if (LSW(number) != 0) {
			bias = 32;
			while ((LSW(number) & 0x80000000) == 0) {
				bias++;
				LSW(number) <<= 1;
			}
		}
	} else {
		while ((MSW(number) & 0x80000000) == 0) {
			bias++;
			MSW(number) <<= 1;
		}
	}

	return bias;
}

/*
* General (i.e., difficult) case of 64-bit unsigned division.
* Use this to handle cases where values are greater than can be 
* represented with 53-bits of double floats.  
* Modified from pl1 library.
*/
static
void
__ull_divrem_6464 (llvalue *aquo, llvalue *arem, llvalue num, llvalue denom)
{
	llvalue quo;
	int n_bias, d_bias;

	/* Shift denom left so its first bit lines up with that of numerator */
	n_bias = ll_firstbit(num);
	d_bias = ll_firstbit(denom);
	if ((d_bias -= n_bias) > 0) {
		denom.ll = __ll_lshift(denom.ll, d_bias);
	}

	/*
 	 * "Long division" just like you did in elementary school, except that
	 * by virtue of doing it in binary, we can guess the next digit simply
	 * by comparing numerator and divisor.
	 * 
	 * quo = 0;
	 * repeat (1 + amount_we_shifted_denom_left) {
	 *	quo <<= 1;
	 *	if (!(num < denom)) {
	 *		num -= denom;
	 *		quo |= 1;
	 *	}
	 *	denom >>= 1;
	 * }
	 */
	MSW(quo) = LSW(quo) = 0;
	while (d_bias-- >= 0) {
		quo.ll = __ll_lshift(quo.ll, 1);

		if (ULL_GE(num, denom)) {
			LL_SUB(num, num, denom);	/* num -= denom */
			LSW(quo) |= 1;
		}
		denom.ll = __ull_rshift(denom.ll, 1);
	}

	*aquo = quo;
	*arem = num;
}


extern longlong_t
__ll_div (longlong_t left, longlong_t right)
{
	llvalue a,b,q,r;
	llvalue ll_2_16, ll_2_53;
	int negate = 0;
	a.ll = left;
	b.ll = right;
	SET_LL(ll_2_16, pow2_16);
	MSW(ll_2_53) = pow2_21; LSW(ll_2_53) = 0;
	if (LL_ISNEG(a)) {
		/* make positive, but later negate the quotient */
		negate = !negate;
		LL_NEG(a,a);
	}
	if (LL_ISNEG(b)) {
		/* make positive, but later negate the quotient */
		negate = !negate;
		LL_NEG(b,b);
	}
	/* dividend is positive */
	if (ULL_LT(b,ll_2_16)) {
		/* divide 64 bits by 16 bits */
		__ull_divrem_6416(&q.ull,&r.ull,a.ull,b.ull);
	} else if (ULL_LE(a,ll_2_53) && ULL_LE(b,ll_2_53)) {
		/* do fp double divide */
		__ull_divrem_5353(&q.ull,&r.ull,a.ull,b.ull);
	} else {
		/* do full 64-bit divide */
		__ull_divrem_6464(&q,&r, a, b);
	}
	if (negate) {
		LL_NEG(q,q);
	}
	return q.ll;
}

extern ulonglong_t
__ull_div (ulonglong_t left, ulonglong_t right)
{
	llvalue a,b,q,r;
	llvalue ll_2_16, ll_2_53;
	a.ull = left;
	b.ull = right;
	SET_LL(ll_2_16, pow2_16);
	MSW(ll_2_53) = pow2_21; LSW(ll_2_53) = 0;
	if (ULL_LT(b,ll_2_16)) {
		__ull_divrem_6416(&q.ull,&r.ull,left,right);
	} else if (ULL_LE(a,ll_2_53) && ULL_LE(b,ll_2_53)) {
		__ull_divrem_5353(&q.ull,&r.ull,left,right);
	} else {
		__ull_divrem_6464(&q,&r,a,b);
	}
	return q.ull;
}

extern longlong_t
__ll_rem (longlong_t left, longlong_t right)
{
	llvalue a,b,q,r;
	llvalue ll_2_16, ll_2_53;
	int negate = 0;
	a.ll = left;
	b.ll = right;
	SET_LL(ll_2_16, pow2_16);
	MSW(ll_2_53) = pow2_21; LSW(ll_2_53) = 0;
	if (LL_ISNEG(a)) {
		/* make positive, but later negate the remainder */
		negate = !negate;
		LL_NEG(a,a);
	}
	if (LL_ISNEG(b)) {
		/* make positive, remainder only depends on sign of num */
		LL_NEG(b,b);
	}
	/* dividend is positive */
	if (ULL_LT(b,ll_2_16)) {
		/* divide 64 bits by 16 bits */
		__ull_divrem_6416(&q.ull,&r.ull,a.ull,b.ull);
	} else if (ULL_LE(a,ll_2_53) && ULL_LE(b,ll_2_53)) {
		/* do fp double divide */
		__ull_divrem_5353(&q.ull,&r.ull,a.ull,b.ull);
	} else {
		/* do full 64-bit divide */
		__ull_divrem_6464(&q,&r, a, b);
	}
	if (negate) {
		LL_NEG(r,r);
	}
	return r.ll;
}

extern ulonglong_t
__ull_rem (ulonglong_t left, ulonglong_t right)
{
	llvalue a,b,q,r;
	llvalue ll_2_16, ll_2_53;
	a.ll = left;
	b.ll = right;
	SET_LL(ll_2_16, pow2_16);
	MSW(ll_2_53) = pow2_21; LSW(ll_2_53) = 0;
	if (ULL_LT(b,ll_2_16)) {
		__ull_divrem_6416(&q.ull,&r.ull,left,right);
	} else if (ULL_LE(a,ll_2_53) && ULL_LE(b,ll_2_53)) {
		__ull_divrem_5353(&q.ull,&r.ull,left,right);
	} else {
		__ull_divrem_6464(&q,&r,a,b);
	}
	return r.ull;
}

extern
longlong_t
__ll_mod (longlong_t left, longlong_t right)
{
	/* mod is similar to rem except that:
	 * 11 rem 5 == 1 == 11 mod 5
	 * 11 rem -5 == 1, 11 mod -5 == -4
	 * -11 rem 5 == -1, -11 mod 5 == 4
	 * -11 rem -5 == -1 == -11 mod -5
	 */
	llvalue b,r;
	b.ll = right;
	r.ll = __ll_rem(left,right);
	if (LL_ISNEG(r) != LL_ISNEG(b)) {
		LL_ADD(r,r,b);
	}
	return r.ll;
}

#define bitsperword	32

#define SHIFT_MASK	0x3f	/* 6 bit mask = 0...0111111 */

/* shift routines */

extern longlong_t
__ll_lshift (longlong_t left, longlong_t right)
{
	llvalue a, b, r, mask;

	a.ll = left;
	b.ll = right;
	/*
	 * shift by negative value or > 32/64 is undefined,
	 * but for compatibility we do what our hardware does,
	 * which is to mask the right value with 6 rightmost bits.
	 */
	SET_LL(mask, SHIFT_MASK);
	LL_AND(b, b, mask);
	/* assert(b.dw.msw == 0); */
	if (b.dw.lsw >= bitsperword) {
		/* everything shifted to msw */
		r.dw.msw = a.dw.lsw << (b.dw.lsw - bitsperword);
		r.dw.lsw = 0;
	} else if (b.dw.lsw > 0) {
		/* lsw shifted, then msw combines lsw and msw */
		r.dw.msw = (a.dw.msw << b.dw.lsw) 
			| (a.dw.lsw >> (bitsperword - b.dw.lsw));
		r.dw.lsw = a.dw.lsw << b.dw.lsw;
	} else {
		/* b == 0 */
		return left;
	}
	return r.ll;
}

/* unsigned long long right-shift */
extern longlong_t
__ull_rshift (ulonglong_t left, longlong_t right)
{
	llvalue a, b, r, mask;

	a.ll = left;
	b.ll = right;
	/*
	 * shift by negative value or > 32/64 is undefined,
	 * but for compatibility we do what our hardware does,
	 * which is to mask the right value with 6 rightmost bits.
	 */
	SET_LL(mask, SHIFT_MASK);
	LL_AND(b, b, mask);
	/* assert(b.dw.msw == 0); */
	if (b.dw.lsw >= bitsperword) {
		/* everything shifted to lsw */
		r.dw.lsw = a.dw.msw >> (b.dw.lsw - bitsperword);
		r.dw.msw = 0;
	} else if (b.dw.lsw > 0) {
                /* msw shifted, then lsw combines lsw and msw */
		r.dw.lsw = (a.dw.lsw >> b.dw.lsw) 
			| (a.dw.msw << (bitsperword - b.dw.lsw));
		r.dw.msw = a.dw.msw >> b.dw.lsw;
	} else {
		/* b == 0 */
		return left;
	}
	return r.ll;
}


/* Signed long long right-shift.
 * For negative values, result is implementation-defined,
 * but for compatibility with 32-bit shift, we fill with sign bit. */
extern longlong_t
__ll_rshift (longlong_t left, longlong_t right)
{
	llvalue a, b, r, mask;

	a.ll = left;
	b.ll = right;
	/*
	 * shift by negative value or > 32/64 is undefined,
	 * but for compatibility we do what our hardware does,
	 * which is to mask the right value with 6 rightmost bits.
	 */
	SET_LL(mask, SHIFT_MASK);
	LL_AND(b, b, mask);
	/* assert(b.dw.msw == 0); */
	if (b.dw.lsw >= bitsperword) {
		/* everything shifted to lsw */
		r.dw.lsw = ((int) a.dw.msw) >> (b.dw.lsw - bitsperword);
		/* return 0 or -1 */
		r.dw.msw = (((int) a.dw.msw < 0) ? -1 : 0);
	} else if (b.dw.lsw > 0) {
                /* msw shifted, then lsw combines lsw and msw */
		r.dw.lsw = (a.dw.lsw >> b.dw.lsw) 
			| (a.dw.msw << (bitsperword - b.dw.lsw));
		r.dw.msw = ((int) a.dw.msw) >> b.dw.lsw;
	} else {
		/* b == 0 */
		return left;
	}
	return r.ll;
}