kern/include/math64.h

   1 /* Copyright (C) 1991-2016, the Linux Kernel authors
   2  *
   3  * This source code is licensed under the GNU General Public License
   4  * Version 2. See the file COPYING for more details.
   5  */
   6
   7 #pragma once
   8
   9 #include <sys/types.h>
  10 #include <arch/div64.h>
  11
  12 #if BITS_PER_LONG == 64
  13
  14 #define div64_long(x, y) div64_s64((x), (y))
  15 #define div64_ul(x, y)   div64_u64((x), (y))
  16
  17 /**
  18  * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder
  19  *
  20  * This is commonly provided by 32bit archs to provide an optimized 64bit
  21  * divide.
  22  */
  23 static inline uint64_t div_u64_rem(uint64_t dividend, uint32_t divisor,
  24                                    uint32_t *remainder)
  25 {
  26         *remainder = dividend % divisor;
  27         return dividend / divisor;
  28 }
  29
  30 /**
  31  * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
  32  */
  33 static inline int64_t div_s64_rem(int64_t dividend, int32_t divisor,
  34                                   int32_t *remainder)
  35 {
  36         *remainder = dividend % divisor;
  37         return dividend / divisor;
  38 }
  39
  40 /**
  41  * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder
  42  */
  43 static inline uint64_t div64_u64_rem(uint64_t dividend, uint64_t divisor,
  44                                      uint64_t *remainder)
  45 {
  46         *remainder = dividend % divisor;
  47         return dividend / divisor;
  48 }
  49
  50 /**
  51  * div64_u64 - unsigned 64bit divide with 64bit divisor
  52  */
  53 static inline uint64_t div64_u64(uint64_t dividend, uint64_t divisor)
  54 {
  55         return dividend / divisor;
  56 }
  57
  58 /**
  59  * div64_s64 - signed 64bit divide with 64bit divisor
  60  */
  61 static inline int64_t div64_s64(int64_t dividend, int64_t divisor)
  62 {
  63         return dividend / divisor;
  64 }
  65
  66 #elif BITS_PER_LONG == 32
  67
  68 #define div64_long(x, y) div_s64((x), (y))
  69 #define div64_ul(x, y)   div_u64((x), (y))
  70
  71 #ifndef div_u64_rem
  72 static inline uint64_t div_u64_rem(uint64_t dividend, uint32_t divisor,
  73                                    uint32_t *remainder)
  74 {
  75         *remainder = do_div(dividend, divisor);
  76         return dividend;
  77 }
  78 #endif
  79
  80 #ifndef div_s64_rem
  81 extern int64_t div_s64_rem(int64_t dividend, int32_t divisor,
  82                            int32_t *remainder);
  83 #endif
  84
  85 #ifndef div64_u64_rem
  86 extern uint64_t div64_u64_rem(uint64_t dividend, uint64_t divisor,
  87                               uint64_t *remainder);
  88 #endif
  89
  90 #ifndef div64_u64
  91 extern uint64_t div64_u64(uint64_t dividend, uint64_t divisor);
  92 #endif
  93
  94 #ifndef div64_s64
  95 extern int64_t div64_s64(int64_t dividend, int64_t divisor);
  96 #endif
  97
  98 #endif /* BITS_PER_LONG */
  99
 100 /**
 101  * div_u64 - unsigned 64bit divide with 32bit divisor
 102  *
 103  * This is the most common 64bit divide and should be used if possible,
 104  * as many 32bit archs can optimize this variant better than a full 64bit
 105  * divide.
 106  */
 107 #ifndef div_u64
 108 static inline uint64_t div_u64(uint64_t dividend, uint32_t divisor)
 109 {
 110         uint32_t remainder;
 111         return div_u64_rem(dividend, divisor, &remainder);
 112 }
 113 #endif
 114
 115 /**
 116  * div_s64 - signed 64bit divide with 32bit divisor
 117  */
 118 #ifndef div_s64
 119 static inline int64_t div_s64(int64_t dividend, int32_t divisor)
 120 {
 121         int32_t remainder;
 122         return div_s64_rem(dividend, divisor, &remainder);
 123 }
 124 #endif
 125
 126 uint32_t iter_div_u64_rem(uint64_t dividend, uint32_t divisor,
 127                           uint64_t *remainder);
 128
 129 static __always_inline uint32_t
 130 __iter_div_u64_rem(uint64_t dividend, uint32_t divisor, uint64_t *remainder)
 131 {
 132         uint32_t ret = 0;
 133
 134         while (dividend >= divisor) {
 135                 /* The following asm() prevents the compiler from
 136                    optimising this loop into a modulo operation.  */
 137                 asm("" : "+rm"(dividend));
 138
 139                 dividend -= divisor;
 140                 ret++;
 141         }
 142
 143         *remainder = dividend;
 144
 145         return ret;
 146 }
 147
 148 #ifndef mul_u32_u32
 149 /*
 150  * Many a GCC version messes this up and generates a 64x64 mult :-(
 151  */
 152 static inline uint64_t mul_u32_u32(uint32_t a, uint32_t b)
 153 {
 154         return (uint64_t)a * b;
 155 }
 156 #endif
 157
 158 #if defined(CONFIG_ARCH_SUPPORTS_INT128) && defined(__SIZEOF_INT128__)
 159
 160 #ifndef mul_u64_u32_shr
 161 static inline uint64_t mul_u64_u32_shr(uint64_t a, uint32_t mul,
 162                                        unsigned int shift)
 163 {
 164         return (uint64_t)(((unsigned __int128)a * mul) >> shift);
 165 }
 166 #endif /* mul_u64_u32_shr */
 167
 168 #ifndef mul_u64_u64_shr
 169 static inline uint64_t mul_u64_u64_shr(uint64_t a, uint64_t mul,
 170                                        unsigned int shift)
 171 {
 172         return (uint64_t)(((unsigned __int128)a * mul) >> shift);
 173 }
 174 #endif /* mul_u64_u64_shr */
 175
 176 #else
 177
 178 #ifndef mul_u64_u32_shr
 179 static inline uint64_t mul_u64_u32_shr(uint64_t a, uint32_t mul,
 180                                        unsigned int shift)
 181 {
 182         uint32_t ah, al;
 183         uint64_t ret;
 184
 185         al = a;
 186         ah = a >> 32;
 187
 188         ret = mul_u32_u32(al, mul) >> shift;
 189         if (ah)
 190                 ret += mul_u32_u32(ah, mul) << (32 - shift);
 191
 192         return ret;
 193 }
 194 #endif /* mul_u64_u32_shr */
 195
 196 #ifndef mul_u64_u64_shr
 197 static inline uint64_t mul_u64_u64_shr(uint64_t a, uint64_t b,
 198                                        unsigned int shift)
 199 {
 200         union {
 201                 uint64_t ll;
 202                 struct {
 203 #ifdef __BIG_ENDIAN
 204                         uint32_t high, low;
 205 #else
 206                         uint32_t low, high;
 207 #endif
 208                 } l;
 209         } rl, rm, rn, rh, a0, b0;
 210         uint64_t c;
 211
 212         a0.ll = a;
 213         b0.ll = b;
 214
 215         rl.ll = mul_u32_u32(a0.l.low, b0.l.low);
 216         rm.ll = mul_u32_u32(a0.l.low, b0.l.high);
 217         rn.ll = mul_u32_u32(a0.l.high, b0.l.low);
 218         rh.ll = mul_u32_u32(a0.l.high, b0.l.high);
 219
 220         /*
 221          * Each of these lines computes a 64-bit intermediate result into "c",
 222          * starting at bits 32-95.  The low 32-bits go into the result of the
 223          * multiplication, the high 32-bits are carried into the next step.
 224          */
 225         rl.l.high = c = (uint64_t)rl.l.high + rm.l.low + rn.l.low;
 226         rh.l.low = c = (c >> 32) + rm.l.high + rn.l.high + rh.l.low;
 227         rh.l.high = (c >> 32) + rh.l.high;
 228
 229         /*
 230          * The 128-bit result of the multiplication is in rl.ll and rh.ll,
 231          * shift it right and throw away the high part of the result.
 232          */
 233         if (shift == 0)
 234                 return rl.ll;
 235         if (shift < 64)
 236                 return (rl.ll >> shift) | (rh.ll << (64 - shift));
 237         return rh.ll >> (shift & 63);
 238 }
 239 #endif /* mul_u64_u64_shr */
 240
 241 #endif
 242
 243 #ifndef mul_u64_u32_div
 244 static inline uint64_t mul_u64_u32_div(uint64_t a, uint32_t mul,
 245                                        uint32_t divisor)
 246 {
 247         union {
 248                 uint64_t ll;
 249                 struct {
 250 #ifdef __BIG_ENDIAN
 251                         uint32_t high, low;
 252 #else
 253                         uint32_t low, high;
 254 #endif
 255                 } l;
 256         } u, rl, rh;
 257
 258         u.ll = a;
 259         rl.ll = mul_u32_u32(u.l.low, mul);
 260         rh.ll = mul_u32_u32(u.l.high, mul) + rl.l.high;
 261
 262         /* Bits 32-63 of the result will be in rh.l.low. */
 263         rl.l.high = do_div(rh.ll, divisor);
 264
 265         /* Bits 0-31 of the result will be in rl.l.low. */
 266         do_div(rl.ll, divisor);
 267
 268         rl.l.high = rh.l.low;
 269         return rl.ll;
 270 }
 271 #endif /* mul_u64_u32_div */