1/* 2 * __div64_32 implementation for 31 bit. 3 * 4 * Copyright IBM Corp. 2006 5 * Author(s): Martin Schwidefsky (schwidefsky@de.ibm.com), 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 */ 17static 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 = 0UL; 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" (1UL) : "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 */ 74uint32_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 127uint32_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 = 0UL; 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 */ 148