Commit | Line | Data |
---|---|---|
d9f7a745 | 1 | /* |
d9f7a745 MS |
2 | * __div64_32 implementation for 31 bit. |
3 | * | |
a53c8fab | 4 | * Copyright IBM Corp. 2006 |
d9f7a745 MS |
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 | */ | |
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" | |
4fa81ed2 | 62 | " ahi %1,1\n" |
d9f7a745 MS |
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 | */ | |
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 | ||
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 */ |