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