1/* 2 * arch/s390/lib/div64.c 3 * 4 * __div64_32 implementation for 31 bit. 5 * 6 * Copyright (C) IBM Corp. 2006 7 * Author(s): Martin Schwidefsky (schwidefsky@de.ibm.com), 8 */ 9 10#include <linux/types.h> 11#include <linux/module.h> 12 13#ifdef CONFIG_MARCH_G5 14 15/* 16 * Function to divide an unsigned 64 bit integer by an unsigned 17 * 31 bit integer using signed 64/32 bit division. 18 */ 19static uint32_t __div64_31(uint64_t *n, uint32_t base) 20{ 21 register uint32_t reg2 asm("2"); 22 register uint32_t reg3 asm("3"); 23 uint32_t *words = (uint32_t *) n; 24 uint32_t tmp; 25 26 /* Special case base==1, remainder = 0, quotient = n */ 27 if (base == 1) 28 return 0; 29 /* 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. 35 */ 36 reg2 = 0UL; 37 reg3 = words[0]; 38 asm volatile( 39 " dr %0,%2\n" 40 : "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" ); 41 words[0] = reg3; 42 reg3 = words[1]; 43 /* 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 ? 53 */ 54 asm volatile( 55 " nr %2,%1\n" 56 " srdl %0,1\n" 57 " dr %0,%3\n" 58 " alr %0,%0\n" 59 " alr %1,%1\n" 60 " alr %0,%2\n" 61 " clr %0,%3\n" 62 " jl 0f\n" 63 " slr %0,%3\n" 64 " alr %1,%2\n" 65 "0:\n" 66 : "+d" (reg2), "+d" (reg3), "=d" (tmp) 67 : "d" (base), "2" (1UL) : "cc" ); 68 words[1] = reg3; 69 return reg2; 70} 71 72/* 73 * Function to divide an unsigned 64 bit integer by an unsigned 74 * 32 bit integer using the unsigned 64/31 bit division. 75 */ 76uint32_t __div64_32(uint64_t *n, uint32_t base) 77{ 78 uint32_t r; 79 80 /* 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. 86 */ 87 r = __div64_31(n, ((signed) base < 0) ? (base/2) : base); 88 if ((signed) base < 0) { 89 uint64_t q = *n; 90 /* 91 * First transformation: 92 * n = (base/2)*q + r 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. 97 */ 98 if (q & 1) 99 r += base/2; 100 q >>= 1; 101 /* 102 * Second transformation. ((base/2)*2) could have lost the 103 * last bit. 104 * n = ((base/2)*2)*q1 + r1 105 * = base*q1 - ((base&1) ? q1 : 0) + r1 106 */ 107 if (base & 1) { 108 int64_t rx = r - q; 109 /* 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. 115 */ 116 while (rx < 0) { 117 rx += base; 118 q--; 119 } 120 r = rx; 121 } 122 *n = q; 123 } 124 return r; 125} 126 127#else /* MARCH_G5 */ 128 129uint32_t __div64_32(uint64_t *n, uint32_t base) 130{ 131 register uint32_t reg2 asm("2"); 132 register uint32_t reg3 asm("3"); 133 uint32_t *words = (uint32_t *) n; 134 135 reg2 = 0UL; 136 reg3 = words[0]; 137 asm volatile( 138 " dlr %0,%2\n" 139 : "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" ); 140 words[0] = reg3; 141 reg3 = words[1]; 142 asm volatile( 143 " dlr %0,%2\n" 144 : "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" ); 145 words[1] = reg3; 146 return reg2; 147} 148 149#endif /* MARCH_G5 */ 150