div64.c
/*
* 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);