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