~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/arch/s390/lib/div64.c

Version: ~ [ linux-5.4-rc7 ] ~ [ linux-5.3.11 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.84 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.154 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.201 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.201 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.77 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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  */
 17 static 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  */
 74 uint32_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 
127 uint32_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 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp