Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
div64.c
Go to the documentation of this file.
1 /*
2  * __div64_32 implementation for 31 bit.
3  *
4  * Copyright IBM Corp. 2006
5  * Author(s): Martin Schwidefsky ([email protected]),
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"
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  */
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 
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 */