2 * arch/s390/lib/div64.c
4 * __div64_32 implementation for 31 bit.
6 * Copyright (C) IBM Corp. 2006
7 * Author(s): Martin Schwidefsky (schwidefsky@de.ibm.com),
10 #include <linux/types.h>
11 #include <linux/module.h>
13 #ifdef CONFIG_MARCH_G5
16 * Function to divide an unsigned 64 bit integer by an unsigned
17 * 31 bit integer using signed 64/32 bit division.
19 static uint32_t __div64_31(uint64_t *n
, uint32_t base
)
21 register uint32_t reg2
asm("2");
22 register uint32_t reg3
asm("3");
23 uint32_t *words
= (uint32_t *) n
;
26 /* Special case base==1, remainder = 0, quotient = n */
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.
40 : "+d" (reg2
), "+d" (reg3
) : "d" (base
) : "cc" );
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 ?
66 : "+d" (reg2
), "+d" (reg3
), "=d" (tmp
)
67 : "d" (base
), "2" (1UL) : "cc" );
73 * Function to divide an unsigned 64 bit integer by an unsigned
74 * 32 bit integer using the unsigned 64/31 bit division.
76 uint32_t __div64_32(uint64_t *n
, uint32_t base
)
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.
87 r
= __div64_31(n
, ((signed) base
< 0) ? (base
/2) : base
);
88 if ((signed) base
< 0) {
91 * First transformation:
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.
102 * Second transformation. ((base/2)*2) could have lost the
104 * n = ((base/2)*2)*q1 + r1
105 * = base*q1 - ((base&1) ? q1 : 0) + r1
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.
129 uint32_t __div64_32(uint64_t *n
, uint32_t base
)
131 register uint32_t reg2
asm("2");
132 register uint32_t reg3
asm("3");
133 uint32_t *words
= (uint32_t *) n
;
139 : "+d" (reg2
), "+d" (reg3
) : "d" (base
) : "cc" );
144 : "+d" (reg2
), "+d" (reg3
) : "d" (base
) : "cc" );
149 #endif /* MARCH_G5 */
This page took 0.032981 seconds and 5 git commands to generate.