util/int128.c

   1 /*
   2  * 128-bit division and remainder for compilers not supporting __int128
   3  *
   4  * Copyright (c) 2021 Frédéric Pétrot <frederic.petrot@univ-grenoble-alpes.fr>
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a copy
   7  * of this software and associated documentation files (the "Software"), to deal
   8  * in the Software without restriction, including without limitation the rights
   9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10  * copies of the Software, and to permit persons to whom the Software is
  11  * furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in
  14  * all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22  * THE SOFTWARE.
  23  */
  24
  25 #include "qemu/osdep.h"
  26 #include "qemu/host-utils.h"
  27 #include "qemu/int128.h"
  28
  29 #ifndef CONFIG_INT128
  30
  31 /*
  32  * Division and remainder algorithms for 128-bit due to Stefan Kanthak,
  33  * https://skanthak.homepage.t-online.de/integer.html#udivmodti4
  34  * Preconditions:
  35  *     - function should never be called with v equals to 0, it has to
  36  *       be dealt with beforehand
  37  *     - quotien pointer must be valid
  38  */
  39 static Int128 divrem128(Int128 u, Int128 v, Int128 *q)
  40 {
  41     Int128 qq;
  42     uint64_t hi, lo, tmp;
  43     int s = clz64(v.hi);
  44
  45     if (s == 64) {
  46         /* we have uu÷0v => let's use divu128 */
  47         hi = u.hi;
  48         lo = u.lo;
  49         tmp = divu128(&lo, &hi, v.lo);
  50         *q = int128_make128(lo, hi);
  51         return int128_make128(tmp, 0);
  52     } else {
  53         hi = int128_gethi(int128_lshift(v, s));
  54
  55         if (hi > u.hi) {
  56             lo = u.lo;
  57             tmp = u.hi;
  58             divu128(&lo, &tmp, hi);
  59             lo = int128_gethi(int128_lshift(int128_make128(lo, 0), s));
  60         } else { /* prevent overflow */
  61             lo = u.lo;
  62             tmp = u.hi - hi;
  63             divu128(&lo, &tmp, hi);
  64             lo = int128_gethi(int128_lshift(int128_make128(lo, 1), s));
  65         }
  66
  67         qq = int128_make64(lo);
  68
  69         tmp = lo * v.hi;
  70         mulu64(&lo, &hi, lo, v.lo);
  71         hi += tmp;
  72
  73         if (hi < tmp     /* quotient * divisor >= 2**128 > dividend */
  74             || hi > u.hi /* quotient * divisor > dividend */
  75             || (hi == u.hi && lo > u.lo)) {
  76             qq.lo -= 1;
  77             mulu64(&lo, &hi, qq.lo, v.lo);
  78             hi += qq.lo * v.hi;
  79         }
  80
  81         *q = qq;
  82         u.hi -= hi + (u.lo < lo);
  83         u.lo -= lo;
  84         return u;
  85     }
  86 }
  87
  88 Int128 int128_divu(Int128 a, Int128 b)
  89 {
  90     Int128 q;
  91     divrem128(a, b, &q);
  92     return q;
  93 }
  94
  95 Int128 int128_remu(Int128 a, Int128 b)
  96 {
  97     Int128 q;
  98     return divrem128(a, b, &q);
  99 }
 100
 101 Int128 int128_divs(Int128 a, Int128 b)
 102 {
 103     Int128 q;
 104     bool sgna = !int128_nonneg(a);
 105     bool sgnb = !int128_nonneg(b);
 106
 107     if (sgna) {
 108         a = int128_neg(a);
 109     }
 110
 111     if (sgnb) {
 112         b = int128_neg(b);
 113     }
 114
 115     divrem128(a, b, &q);
 116
 117     if (sgna != sgnb) {
 118         q = int128_neg(q);
 119     }
 120
 121     return q;
 122 }
 123
 124 Int128 int128_rems(Int128 a, Int128 b)
 125 {
 126     Int128 q, r;
 127     bool sgna = !int128_nonneg(a);
 128     bool sgnb = !int128_nonneg(b);
 129
 130     if (sgna) {
 131         a = int128_neg(a);
 132     }
 133
 134     if (sgnb) {
 135         b = int128_neg(b);
 136     }
 137
 138     r = divrem128(a, b, &q);
 139
 140     if (sgna) {
 141         r = int128_neg(r);
 142     }
 143
 144     return r;
 145 }
 146
 147 #endif