arch/s390/lib/div64.c

   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 */