util/int128.c

/*
 * 128-bit division and remainder for compilers not supporting __int128
 *
 * Copyright (c) 2021 Frédéric Pétrot <frederic.petrot@univ-grenoble-alpes.fr>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include "qemu/osdep.h"
#include "qemu/host-utils.h"
#include "qemu/int128.h"

#ifndef CONFIG_INT128

/*
 * Division and remainder algorithms for 128-bit due to Stefan Kanthak,
 * https://skanthak.homepage.t-online.de/integer.html#udivmodti4
 * Preconditions:
 *     - function should never be called with v equals to 0, it has to
 *       be dealt with beforehand
 *     - quotien pointer must be valid
 */
static Int128 divrem128(Int128 u, Int128 v, Int128 *q)
{
    Int128 qq;
    uint64_t hi, lo, tmp;
    int s = clz64(v.hi);

    if (s == 64) {
        /* we have uu÷0v => let's use divu128 */
        hi = u.hi;
        lo = u.lo;
        tmp = divu128(&lo, &hi, v.lo);
        *q = int128_make128(lo, hi);
        return int128_make128(tmp, 0);
    } else {
        hi = int128_gethi(int128_lshift(v, s));

        if (hi > u.hi) {
            lo = u.lo;
            tmp = u.hi;
            divu128(&lo, &tmp, hi);
            lo = int128_gethi(int128_lshift(int128_make128(lo, 0), s));
        } else { /* prevent overflow */
            lo = u.lo;
            tmp = u.hi - hi;
            divu128(&lo, &tmp, hi);
            lo = int128_gethi(int128_lshift(int128_make128(lo, 1), s));
        }

        qq = int128_make64(lo);

        tmp = lo * v.hi;
        mulu64(&lo, &hi, lo, v.lo);
        hi += tmp;

        if (hi < tmp     /* quotient * divisor >= 2**128 > dividend */
            || hi > u.hi /* quotient * divisor > dividend */
            || (hi == u.hi && lo > u.lo)) {
            qq.lo -= 1;
            mulu64(&lo, &hi, qq.lo, v.lo);
            hi += qq.lo * v.hi;
        }

        *q = qq;
        u.hi -= hi + (u.lo < lo);
        u.lo -= lo;
        return u;
    }
}

Int128 int128_divu(Int128 a, Int128 b)
{
    Int128 q;
    divrem128(a, b, &q);
    return q;
}

Int128 int128_remu(Int128 a, Int128 b)
{
    Int128 q;
    return divrem128(a, b, &q);
}

Int128 int128_divs(Int128 a, Int128 b)
{
    Int128 q;
    bool sgna = !int128_nonneg(a);
    bool sgnb = !int128_nonneg(b);

    if (sgna) {
        a = int128_neg(a);
    }

    if (sgnb) {
        b = int128_neg(b);
    }

    divrem128(a, b, &q);

    if (sgna != sgnb) {
        q = int128_neg(q);
    }

    return q;
}

Int128 int128_rems(Int128 a, Int128 b)
{
    Int128 q, r;
    bool sgna = !int128_nonneg(a);
    bool sgnb = !int128_nonneg(b);

    if (sgna) {
        a = int128_neg(a);
    }

    if (sgnb) {
        b = int128_neg(b);
    }

    r = divrem128(a, b, &q);

    if (sgna) {
        r = int128_neg(r);
    }

    return r;
}

#endif