qemu

FORK: QEMU emulator
git clone https://git.neptards.moe/neptards/qemu.git
Log | Files | Refs | Submodules | LICENSE

int128.c (3792B)

      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