Linux Kernel
3.7.1
Main Page
Related Pages
Modules
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Groups
Pages
arch
s390
lib
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
= 0
UL
;
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"
(1
UL
) :
"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
= 0
UL
;
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 */
Generated on Thu Jan 10 2013 13:16:57 for Linux Kernel by
1.8.2