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 */
__div64_31(uint64_t * n,uint32_t base)17 static 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 */
__div64_32(uint64_t * n,uint32_t base)74 uint32_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
__div64_32(uint64_t * n,uint32_t base)127 uint32_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 */
148