1/*
  2 *  __div64_32 implementation for 31 bit.
  3 *
  4 *    Copyright IBM Corp. 2006
  5 *    Author(s): Martin Schwidefsky (schwidefsky@de.ibm.com),
  6 */
  7
  8#include <linux/types.h>
  9#include <linux/module.h>
 10
 11#ifdef CONFIG_MARCH_G5
 12
 13/*
 14 * Function to divide an unsigned 64 bit integer by an unsigned
 15 * 31 bit integer using signed 64/32 bit division.
 16 */
 17static uint32_t __div64_31(uint64_t *n, uint32_t base)
 18{
 19	register uint32_t reg2 asm("2");
 20	register uint32_t reg3 asm("3");
 21	uint32_t *words = (uint32_t *) n;
 22	uint32_t tmp;
 23
 24	/* Special case base==1, remainder = 0, quotient = n */
 25	if (base == 1)
 26		return 0;
 27	/*
 28	 * Special case base==0 will cause a fixed point divide exception
 29	 * on the dr instruction and may not happen anyway. For the
 30	 * following calculation we can assume base > 1. The first
 31	 * signed 64 / 32 bit division with an upper half of 0 will
 32	 * give the correct upper half of the 64 bit quotient.
 33	 */
 34	reg2 = 0UL;
 35	reg3 = words[0];
 36	asm volatile(
 37		"	dr	%0,%2\n"
 38		: "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" );
 39	words[0] = reg3;
 40	reg3 = words[1];
 41	/*
 42	 * To get the lower half of the 64 bit quotient and the 32 bit
 43	 * remainder we have to use a little trick. Since we only have
 44	 * a signed division the quotient can get too big. To avoid this
 45	 * the 64 bit dividend is halved, then the signed division will
 46	 * work. Afterwards the quotient and the remainder are doubled.
 47	 * If the last bit of the dividend has been one the remainder
 48	 * is increased by one then checked against the base. If the
 49	 * remainder has overflown subtract base and increase the
 50	 * quotient. Simple, no ?
 51	 */
 52	asm volatile(
 53		"	nr	%2,%1\n"
 54		"	srdl	%0,1\n"
 55		"	dr	%0,%3\n"
 56		"	alr	%0,%0\n"
 57		"	alr	%1,%1\n"
 58		"	alr	%0,%2\n"
 59		"	clr	%0,%3\n"
 60		"	jl	0f\n"
 61		"	slr	%0,%3\n"
 62		"	ahi	%1,1\n"
 63		"0:\n"
 64		: "+d" (reg2), "+d" (reg3), "=d" (tmp)
 65		: "d" (base), "2" (1UL) : "cc" );
 66	words[1] = reg3;
 67	return reg2;
 68}
 69
 70/*
 71 * Function to divide an unsigned 64 bit integer by an unsigned
 72 * 32 bit integer using the unsigned 64/31 bit division.
 73 */
 74uint32_t __div64_32(uint64_t *n, uint32_t base)
 75{
 76	uint32_t r;
 77
 78	/*
 79	 * If the most significant bit of base is set, divide n by
 80	 * (base/2). That allows to use 64/31 bit division and gives a
 81	 * good approximation of the result: n = (base/2)*q + r. The
 82	 * result needs to be corrected with two simple transformations.
 83	 * If base is already < 2^31-1 __div64_31 can be used directly.
 84	 */
 85	r = __div64_31(n, ((signed) base < 0) ? (base/2) : base);
 86	if ((signed) base < 0) {
 87		uint64_t q = *n;
 88		/*
 89		 * First transformation:
 90		 * n = (base/2)*q + r
 91		 *   = ((base/2)*2)*(q/2) + ((q&1) ? (base/2) : 0) + r
 92		 * Since r < (base/2), r + (base/2) < base.
 93		 * With q1 = (q/2) and r1 = r + ((q&1) ? (base/2) : 0)
 94		 * n = ((base/2)*2)*q1 + r1 with r1 < base.
 95		 */
 96		if (q & 1)
 97			r += base/2;
 98		q >>= 1;
 99		/*
100		 * Second transformation. ((base/2)*2) could have lost the
101		 * last bit.
102		 * n = ((base/2)*2)*q1 + r1
103		 *   = base*q1 - ((base&1) ? q1 : 0) + r1
104		 */
105		if (base & 1) {
106			int64_t rx = r - q;
107			/*
108			 * base is >= 2^31. The worst case for the while
109			 * loop is n=2^64-1 base=2^31+1. That gives a
110			 * maximum for q=(2^64-1)/2^31 = 0x1ffffffff. Since
111			 * base >= 2^31 the loop is finished after a maximum
112			 * of three iterations.
113			 */
114			while (rx < 0) {
115				rx += base;
116				q--;
117			}
118			r = rx;
119		}
120		*n = q;
121	}
122	return r;
123}
124
125#else /* MARCH_G5 */
126
127uint32_t __div64_32(uint64_t *n, uint32_t base)
128{
129	register uint32_t reg2 asm("2");
130	register uint32_t reg3 asm("3");
131	uint32_t *words = (uint32_t *) n;
132
133	reg2 = 0UL;
134	reg3 = words[0];
135	asm volatile(
136		"	dlr	%0,%2\n"
137		: "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" );
138	words[0] = reg3;
139	reg3 = words[1];
140	asm volatile(
141		"	dlr	%0,%2\n"
142		: "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" );
143	words[1] = reg3;
144	return reg2;
145}
146
147#endif /* MARCH_G5 */