LXR qemu/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 */
  39static 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
  88Int128 int128_divu(Int128 a, Int128 b)
  89{
  90    Int128 q;
  91    divrem128(a, b, &q);
  92    return q;
  93}
  94
  95Int128 int128_remu(Int128 a, Int128 b)
  96{
  97    Int128 q;
  98    return divrem128(a, b, &q);
  99}
 100
 101Int128 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
 124Int128 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
 148