arch/arm/include/asm/div64.h

   1 #ifndef __ASM_ARM_DIV64
   2 #define __ASM_ARM_DIV64
   3
   4 #include <asm/system.h>
   5 #include <linux/types.h>
   6
   7 /*
   8  * The semantics of do_div() are:
   9  *
  10  * uint32_t do_div(uint64_t *n, uint32_t base)
  11  * {
  12  *      uint32_t remainder = *n % base;
  13  *      *n = *n / base;
  14  *      return remainder;
  15  * }
  16  *
  17  * In other words, a 64-bit dividend with a 32-bit divisor producing
  18  * a 64-bit result and a 32-bit remainder.  To accomplish this optimally
  19  * we call a special __do_div64 helper with completely non standard
  20  * calling convention for arguments and results (beware).
  21  */
  22
  23 #ifdef __ARMEB__
  24 #define __xh "r0"
  25 #define __xl "r1"
  26 #else
  27 #define __xl "r0"
  28 #define __xh "r1"
  29 #endif
  30
  31 #define __do_div_asm(n, base)                                   \
  32 ({                                                              \
  33         register unsigned int __base      asm("r4") = base;     \
  34         register unsigned long long __n   asm("r0") = n;        \
  35         register unsigned long long __res asm("r2");            \
  36         register unsigned int __rem       asm(__xh);            \
  37         asm(    __asmeq("%0", __xh)                             \
  38                 __asmeq("%1", "r2")                             \
  39                 __asmeq("%2", "r0")                             \
  40                 __asmeq("%3", "r4")                             \
  41                 "bl     __do_div64"                             \
  42                 : "=r" (__rem), "=r" (__res)                    \
  43                 : "r" (__n), "r" (__base)                       \
  44                 : "ip", "lr", "cc");                            \
  45         n = __res;                                              \
  46         __rem;                                                  \
  47 })
  48
  49 #if __GNUC__ < 4
  50
  51 /*
  52  * gcc versions earlier than 4.0 are simply too problematic for the
  53  * optimized implementation below. First there is gcc PR 15089 that
  54  * tend to trig on more complex constructs, spurious .global __udivsi3
  55  * are inserted even if none of those symbols are referenced in the
  56  * generated code, and those gcc versions are not able to do constant
  57  * propagation on long long values anyway.
  58  */
  59 #define do_div(n, base) __do_div_asm(n, base)
  60
  61 #elif __GNUC__ >= 4
  62
  63 #include <asm/bug.h>
  64
  65 /*
  66  * If the divisor happens to be constant, we determine the appropriate
  67  * inverse at compile time to turn the division into a few inline
  68  * multiplications instead which is much faster. And yet only if compiling
  69  * for ARMv4 or higher (we need umull/umlal) and if the gcc version is
  70  * sufficiently recent to perform proper long long constant propagation.
  71  * (It is unfortunate that gcc doesn't perform all this internally.)
  72  */
  73 #define do_div(n, base)                                                 \
  74 ({                                                                      \
  75         unsigned int __r, __b = (base);                                 \
  76         if (!__builtin_constant_p(__b) || __b == 0 ||                   \
  77             (__LINUX_ARM_ARCH__ < 4 && (__b & (__b - 1)) != 0)) {       \
  78                 /* non-constant divisor (or zero): slow path */         \
  79                 __r = __do_div_asm(n, __b);                             \
  80         } else if ((__b & (__b - 1)) == 0) {                            \
  81                 /* Trivial: __b is constant and a power of 2 */         \
  82                 /* gcc does the right thing with this code.  */         \
  83                 __r = n;                                                \
  84                 __r &= (__b - 1);                                       \
  85                 n /= __b;                                               \
  86         } else {                                                        \
  87                 /* Multiply by inverse of __b: n/b = n*(p/b)/p       */ \
  88                 /* We rely on the fact that most of this code gets   */ \
  89                 /* optimized away at compile time due to constant    */ \
  90                 /* propagation and only a couple inline assembly     */ \
  91                 /* instructions should remain. Better avoid any      */ \
  92                 /* code construct that might prevent that.           */ \
  93                 unsigned long long __res, __x, __t, __m, __n = n;       \
  94                 unsigned int __c, __p, __z = 0;                         \
  95                 /* preserve low part of n for reminder computation */   \
  96                 __r = __n;                                              \
  97                 /* determine number of bits to represent __b */         \
  98                 __p = 1 << __div64_fls(__b);                            \
  99                 /* compute __m = ((__p << 64) + __b - 1) / __b */       \
 100                 __m = (~0ULL / __b) * __p;                              \
 101                 __m += (((~0ULL % __b + 1) * __p) + __b - 1) / __b;     \
 102                 /* compute __res = __m*(~0ULL/__b*__b-1)/(__p << 64) */ \
 103                 __x = ~0ULL / __b * __b - 1;                            \
 104                 __res = (__m & 0xffffffff) * (__x & 0xffffffff);        \
 105                 __res >>= 32;                                           \
 106                 __res += (__m & 0xffffffff) * (__x >> 32);              \
 107                 __t = __res;                                            \
 108                 __res += (__x & 0xffffffff) * (__m >> 32);              \
 109                 __t = (__res < __t) ? (1ULL << 32) : 0;                 \
 110                 __res = (__res >> 32) + __t;                            \
 111                 __res += (__m >> 32) * (__x >> 32);                     \
 112                 __res /= __p;                                           \
 113                 /* Now sanitize and optimize what we've got. */         \
 114                 if (~0ULL % (__b / (__b & -__b)) == 0) {                \
 115                         /* those cases can be simplified with: */       \
 116                         __n /= (__b & -__b);                            \
 117                         __m = ~0ULL / (__b / (__b & -__b));             \
 118                         __p = 1;                                        \
 119                         __c = 1;                                        \
 120                 } else if (__res != __x / __b) {                        \
 121                         /* We can't get away without a correction    */ \
 122                         /* to compensate for bit truncation errors.  */ \
 123                         /* To avoid it we'd need an additional bit   */ \
 124                         /* to represent __m which would overflow it. */ \
 125                         /* Instead we do m=p/b and n/b=(n*m+m)/p.    */ \
 126                         __c = 1;                                        \
 127                         /* Compute __m = (__p << 64) / __b */           \
 128                         __m = (~0ULL / __b) * __p;                      \
 129                         __m += ((~0ULL % __b + 1) * __p) / __b;         \
 130                 } else {                                                \
 131                         /* Reduce __m/__p, and try to clear bit 31   */ \
 132                         /* of __m when possible otherwise that'll    */ \
 133                         /* need extra overflow handling later.       */ \
 134                         unsigned int __bits = -(__m & -__m);            \
 135                         __bits |= __m >> 32;                            \
 136                         __bits = (~__bits) << 1;                        \
 137                         /* If __bits == 0 then setting bit 31 is     */ \
 138                         /* unavoidable.  Simply apply the maximum    */ \
 139                         /* possible reduction in that case.          */ \
 140                         /* Otherwise the MSB of __bits indicates the */ \
 141                         /* best reduction we should apply.           */ \
 142                         if (!__bits) {                                  \
 143                                 __p /= (__m & -__m);                    \
 144                                 __m /= (__m & -__m);                    \
 145                         } else {                                        \
 146                                 __p >>= __div64_fls(__bits);            \
 147                                 __m >>= __div64_fls(__bits);            \
 148                         }                                               \
 149                         /* No correction needed. */                     \
 150                         __c = 0;                                        \
 151                 }                                                       \
 152                 /* Now we have a combination of 2 conditions:        */ \
 153                 /* 1) whether or not we need a correction (__c), and */ \
 154                 /* 2) whether or not there might be an overflow in   */ \
 155                 /*    the cross product (__m & ((1<<63) | (1<<31)))  */ \
 156                 /* Select the best insn combination to perform the   */ \
 157                 /* actual __m * __n / (__p << 64) operation.         */ \
 158                 if (!__c) {                                             \
 159                         asm (   "umull  %Q0, %R0, %1, %Q2\n\t"          \
 160                                 "mov    %Q0, #0"                        \
 161                                 : "=&r" (__res)                         \
 162                                 : "r" (__m), "r" (__n)                  \
 163                                 : "cc" );                               \
 164                 } else if (!(__m & ((1ULL << 63) | (1ULL << 31)))) {    \
 165                         __res = __m;                                    \
 166                         asm (   "umlal  %Q0, %R0, %Q1, %Q2\n\t"         \
 167                                 "mov    %Q0, #0"                        \
 168                                 : "+&r" (__res)                         \
 169                                 : "r" (__m), "r" (__n)                  \
 170                                 : "cc" );                               \
 171                 } else {                                                \
 172                         asm (   "umull  %Q0, %R0, %Q1, %Q2\n\t"         \
 173                                 "cmn    %Q0, %Q1\n\t"                   \
 174                                 "adcs   %R0, %R0, %R1\n\t"              \
 175                                 "adc    %Q0, %3, #0"                    \
 176                                 : "=&r" (__res)                         \
 177                                 : "r" (__m), "r" (__n), "r" (__z)       \
 178                                 : "cc" );                               \
 179                 }                                                       \
 180                 if (!(__m & ((1ULL << 63) | (1ULL << 31)))) {           \
 181                         asm (   "umlal  %R0, %Q0, %R1, %Q2\n\t"         \
 182                                 "umlal  %R0, %Q0, %Q1, %R2\n\t"         \
 183                                 "mov    %R0, #0\n\t"                    \
 184                                 "umlal  %Q0, %R0, %R1, %R2"             \
 185                                 : "+&r" (__res)                         \
 186                                 : "r" (__m), "r" (__n)                  \
 187                                 : "cc" );                               \
 188                 } else {                                                \
 189                         asm (   "umlal  %R0, %Q0, %R2, %Q3\n\t"         \
 190                                 "umlal  %R0, %1, %Q2, %R3\n\t"          \
 191                                 "mov    %R0, #0\n\t"                    \
 192                                 "adds   %Q0, %1, %Q0\n\t"               \
 193                                 "adc    %R0, %R0, #0\n\t"               \
 194                                 "umlal  %Q0, %R0, %R2, %R3"             \
 195                                 : "+&r" (__res), "+&r" (__z)            \
 196                                 : "r" (__m), "r" (__n)                  \
 197                                 : "cc" );                               \
 198                 }                                                       \
 199                 __res /= __p;                                           \
 200                 /* The reminder can be computed with 32-bit regs     */ \
 201                 /* only, and gcc is good at that.                    */ \
 202                 {                                                       \
 203                         unsigned int __res0 = __res;                    \
 204                         unsigned int __b0 = __b;                        \
 205                         __r -= __res0 * __b0;                           \
 206                 }                                                       \
 207                 /* BUG_ON(__r >= __b || __res * __b + __r != n); */     \
 208                 n = __res;                                              \
 209         }                                                               \
 210         __r;                                                            \
 211 })
 212
 213 /* our own fls implementation to make sure constant propagation is fine */
 214 #define __div64_fls(bits)                                               \
 215 ({                                                                      \
 216         unsigned int __left = (bits), __nr = 0;                         \
 217         if (__left & 0xffff0000) __nr += 16, __left >>= 16;             \
 218         if (__left & 0x0000ff00) __nr +=  8, __left >>=  8;             \
 219         if (__left & 0x000000f0) __nr +=  4, __left >>=  4;             \
 220         if (__left & 0x0000000c) __nr +=  2, __left >>=  2;             \
 221         if (__left & 0x00000002) __nr +=  1;                            \
 222         __nr;                                                           \
 223 })
 224
 225 #endif
 226
 227 #endif