From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 026D1C19F2A for ; Thu, 4 Aug 2022 16:22:16 +0000 (UTC) Received: from localhost ([::1]:43938 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oJdbz-0005rZ-Q8 for qemu-devel@archiver.kernel.org; Thu, 04 Aug 2022 12:22:15 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:37032) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oJdXr-0003ku-Ey for qemu-devel@nongnu.org; Thu, 04 Aug 2022 12:17:59 -0400 Received: from mail-lj1-x22c.google.com ([2a00:1450:4864:20::22c]:45739) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oJdXo-0007A8-Au for qemu-devel@nongnu.org; Thu, 04 Aug 2022 12:17:59 -0400 Received: by mail-lj1-x22c.google.com with SMTP id y23so335328ljh.12 for ; Thu, 04 Aug 2022 09:17:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=/kC3brX+KWDKBFNwHtRwIUMUfUfHCvGSwA8HznxW5EY=; b=bEWCQOoYE/y0VBEAxYsMY94eSHgVXcuIqv1DMxWuwydf1E43urWk8I6QETevV4gsTN 5r0xmtdQrx882xe1dCpJTHEbUFB9bToPTXFfTZekJscjSsLvpSSLV3VZ4R7o+M3ZDY1R anQ3ihCEZwAqJqol38VV/460PE34Yy6ZISKVdw48qkXL0fNQ2QcnUfG+30PN6/N23Cnq DqPyLnO1GX84X0TNTDaonTfRLA3pj/s7RDmyPkPK8K27ldKbovdgCHj3iiAkhL5CKeZF rn8tq9cvSUXoBo6QOUtYgnxDvcbwDjnIc38riGUZ2yssXa7JXZ5hAZ//eRjC9BfKEujk rWxQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=/kC3brX+KWDKBFNwHtRwIUMUfUfHCvGSwA8HznxW5EY=; b=zCeVpjkIXWOu9N2Sk/N0U034kjiQrTpx2FpxKOIEXicGfJFMviMJyuiAL9w/AvQfHj 4MwA2mw5jGk1CGE2tJ6tkk3aimeSR4KojwyF2Lnf/PSqdYsyURgTLdrJZlUKjuqDp3Ix MtAV+uJh6+nrZA4OgBrlz3TBWc+Tuuuc5Vqp8ErhqDU+YupV3w72YueX2kiDgVFLXEAN aDF9jxTVnO0ri4E/ZJ+q32zcKFo9iY9oxds9qo3oTacaoueiTBGYKNsV8+5YhorqDp8Z VS1gIXyCF9rL+o31JPx/fMvjCLqiQ0lr7hSIfOH8FYFYw7e8VfaITYL990E3Cw/AJNMI 06PQ== X-Gm-Message-State: ACgBeo06Zok2fTmPTHp5eSLyUw9dxXXR+nuMe4adK+zl2s0r5dIBlJCY JFXXnB1YhJpjpZ44GJKoFoL/4QA0JVTwWrpHgT9xEbcMvJs= X-Google-Smtp-Source: AA6agR4cRkfRW0vCTl82clnkel9pjvnnczkHtNC7orrk6DJw2uych0xC8enRbIOUpBKGt0LGumqhUTC12tCZLBUs3Pg= X-Received: by 2002:a2e:b88a:0:b0:25d:aa7b:e6ec with SMTP id r10-20020a2eb88a000000b0025daa7be6ecmr768234ljp.67.1659629871799; Thu, 04 Aug 2022 09:17:51 -0700 (PDT) MIME-Version: 1.0 References: <20220712093528.4144184-1-marcandre.lureau@redhat.com> <20220712093528.4144184-10-marcandre.lureau@redhat.com> In-Reply-To: <20220712093528.4144184-10-marcandre.lureau@redhat.com> From: =?UTF-8?B?TWFyYy1BbmRyw6kgTHVyZWF1?= Date: Thu, 4 Aug 2022 20:17:40 +0400 Message-ID: Subject: Re: [PATCH v2 09/15] util: move 256-by-128 division helpers to int128 To: qemu-devel@nongnu.org, lucas.araujo@eldorado.org.br, Richard Henderson , Daniel Henrique Barboza Content-Type: multipart/alternative; boundary="000000000000f7a33705e56cb0f1" Received-SPF: pass client-ip=2a00:1450:4864:20::22c; envelope-from=marcandre.lureau@gmail.com; helo=mail-lj1-x22c.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+qemu-devel=archiver.kernel.org@nongnu.org Sender: "Qemu-devel" --000000000000f7a33705e56cb0f1 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi On Tue, Jul 12, 2022 at 1:49 PM wrote: > From: Marc-Andr=C3=A9 Lureau > > Break a cyclic dependency between int128 and host-utils. > Anyone to approve that change? (This will allow us to more easily move host-utils & int128 units to a subproject) thanks > > Signed-off-by: Marc-Andr=C3=A9 Lureau > --- > include/qemu/host-utils.h | 3 - > include/qemu/int128.h | 3 + > util/host-utils.c | 180 -------------------------------------- > util/int128.c | 180 ++++++++++++++++++++++++++++++++++++++ > 4 files changed, 183 insertions(+), 183 deletions(-) > > diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h > index 29f3a9987880..fa228a4a86e2 100644 > --- a/include/qemu/host-utils.h > +++ b/include/qemu/host-utils.h > @@ -32,7 +32,6 @@ > > #include "qemu/compiler.h" > #include "qemu/bswap.h" > -#include "qemu/int128.h" > > #ifdef CONFIG_INT128 > static inline void mulu64(uint64_t *plow, uint64_t *phigh, > @@ -785,6 +784,4 @@ static inline uint64_t udiv_qrnnd(uint64_t *r, > uint64_t n1, > #endif > } > > -Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor); > -Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor); > #endif > diff --git a/include/qemu/int128.h b/include/qemu/int128.h > index d2b76ca6acdc..823c61edb0fd 100644 > --- a/include/qemu/int128.h > +++ b/include/qemu/int128.h > @@ -472,4 +472,7 @@ static inline void bswap128s(Int128 *s) > #define INT128_MAX int128_make128(UINT64_MAX, INT64_MAX) > #define INT128_MIN int128_make128(0, INT64_MIN) > > +Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor); > +Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor); > + > #endif /* INT128_H */ > diff --git a/util/host-utils.c b/util/host-utils.c > index fb91bcba823d..96d5dc0bed25 100644 > --- a/util/host-utils.c > +++ b/util/host-utils.c > @@ -266,183 +266,3 @@ void ulshift(uint64_t *plow, uint64_t *phigh, > int32_t shift, bool *overflow) > *plow =3D *plow << shift; > } > } > - > -/* > - * Unsigned 256-by-128 division. > - * Returns the remainder via r. > - * Returns lower 128 bit of quotient. > - * Needs a normalized divisor (most significant bit set to 1). > - * > - * Adapted from include/qemu/host-utils.h udiv_qrnnd, > - * from the GNU Multi Precision Library - longlong.h __udiv_qrnnd > - * (https://gmplib.org/repo/gmp/file/tip/longlong.h) > - * > - * Licensed under the GPLv2/LGPLv3 > - */ > -static Int128 udiv256_qrnnd(Int128 *r, Int128 n1, Int128 n0, Int128 d) > -{ > - Int128 d0, d1, q0, q1, r1, r0, m; > - uint64_t mp0, mp1; > - > - d0 =3D int128_make64(int128_getlo(d)); > - d1 =3D int128_make64(int128_gethi(d)); > - > - r1 =3D int128_remu(n1, d1); > - q1 =3D int128_divu(n1, d1); > - mp0 =3D int128_getlo(q1); > - mp1 =3D int128_gethi(q1); > - mulu128(&mp0, &mp1, int128_getlo(d0)); > - m =3D int128_make128(mp0, mp1); > - r1 =3D int128_make128(int128_gethi(n0), int128_getlo(r1)); > - if (int128_ult(r1, m)) { > - q1 =3D int128_sub(q1, int128_one()); > - r1 =3D int128_add(r1, d); > - if (int128_uge(r1, d)) { > - if (int128_ult(r1, m)) { > - q1 =3D int128_sub(q1, int128_one()); > - r1 =3D int128_add(r1, d); > - } > - } > - } > - r1 =3D int128_sub(r1, m); > - > - r0 =3D int128_remu(r1, d1); > - q0 =3D int128_divu(r1, d1); > - mp0 =3D int128_getlo(q0); > - mp1 =3D int128_gethi(q0); > - mulu128(&mp0, &mp1, int128_getlo(d0)); > - m =3D int128_make128(mp0, mp1); > - r0 =3D int128_make128(int128_getlo(n0), int128_getlo(r0)); > - if (int128_ult(r0, m)) { > - q0 =3D int128_sub(q0, int128_one()); > - r0 =3D int128_add(r0, d); > - if (int128_uge(r0, d)) { > - if (int128_ult(r0, m)) { > - q0 =3D int128_sub(q0, int128_one()); > - r0 =3D int128_add(r0, d); > - } > - } > - } > - r0 =3D int128_sub(r0, m); > - > - *r =3D r0; > - return int128_or(int128_lshift(q1, 64), q0); > -} > - > -/* > - * Unsigned 256-by-128 division. > - * Returns the remainder. > - * Returns quotient via plow and phigh. > - * Also returns the remainder via the function return value. > - */ > -Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor) > -{ > - Int128 dhi =3D *phigh; > - Int128 dlo =3D *plow; > - Int128 rem, dhighest; > - int sh; > - > - if (!int128_nz(divisor) || !int128_nz(dhi)) { > - *plow =3D int128_divu(dlo, divisor); > - *phigh =3D int128_zero(); > - return int128_remu(dlo, divisor); > - } else { > - sh =3D clz128(divisor); > - > - if (int128_ult(dhi, divisor)) { > - if (sh !=3D 0) { > - /* normalize the divisor, shifting the dividend > accordingly */ > - divisor =3D int128_lshift(divisor, sh); > - dhi =3D int128_or(int128_lshift(dhi, sh), > - int128_urshift(dlo, (128 - sh))); > - dlo =3D int128_lshift(dlo, sh); > - } > - > - *phigh =3D int128_zero(); > - *plow =3D udiv256_qrnnd(&rem, dhi, dlo, divisor); > - } else { > - if (sh !=3D 0) { > - /* normalize the divisor, shifting the dividend > accordingly */ > - divisor =3D int128_lshift(divisor, sh); > - dhighest =3D int128_rshift(dhi, (128 - sh)); > - dhi =3D int128_or(int128_lshift(dhi, sh), > - int128_urshift(dlo, (128 - sh))); > - dlo =3D int128_lshift(dlo, sh); > - > - *phigh =3D udiv256_qrnnd(&dhi, dhighest, dhi, divisor); > - } else { > - /* > - * dhi >=3D divisor > - * Since the MSB of divisor is set (sh =3D=3D 0), > - * (dhi - divisor) < divisor > - * > - * Thus, the high part of the quotient is 1, and we can > - * calculate the low part with a single call to udiv_qrn= nd > - * after subtracting divisor from dhi > - */ > - dhi =3D int128_sub(dhi, divisor); > - *phigh =3D int128_one(); > - } > - > - *plow =3D udiv256_qrnnd(&rem, dhi, dlo, divisor); > - } > - > - /* > - * since the dividend/divisor might have been normalized, > - * the remainder might also have to be shifted back > - */ > - rem =3D int128_urshift(rem, sh); > - return rem; > - } > -} > - > -/* > - * Signed 256-by-128 division. > - * Returns quotient via plow and phigh. > - * Also returns the remainder via the function return value. > - */ > -Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor) > -{ > - bool neg_quotient =3D false, neg_remainder =3D false; > - Int128 unsig_hi =3D *phigh, unsig_lo =3D *plow; > - Int128 rem; > - > - if (!int128_nonneg(*phigh)) { > - neg_quotient =3D !neg_quotient; > - neg_remainder =3D !neg_remainder; > - > - if (!int128_nz(unsig_lo)) { > - unsig_hi =3D int128_neg(unsig_hi); > - } else { > - unsig_hi =3D int128_not(unsig_hi); > - unsig_lo =3D int128_neg(unsig_lo); > - } > - } > - > - if (!int128_nonneg(divisor)) { > - neg_quotient =3D !neg_quotient; > - > - divisor =3D int128_neg(divisor); > - } > - > - rem =3D divu256(&unsig_lo, &unsig_hi, divisor); > - > - if (neg_quotient) { > - if (!int128_nz(unsig_lo)) { > - *phigh =3D int128_neg(unsig_hi); > - *plow =3D int128_zero(); > - } else { > - *phigh =3D int128_not(unsig_hi); > - *plow =3D int128_neg(unsig_lo); > - } > - } else { > - *phigh =3D unsig_hi; > - *plow =3D unsig_lo; > - } > - > - if (neg_remainder) { > - return int128_neg(rem); > - } else { > - return rem; > - } > -} > diff --git a/util/int128.c b/util/int128.c > index ed8f25fef161..482c63b6551e 100644 > --- a/util/int128.c > +++ b/util/int128.c > @@ -145,3 +145,183 @@ Int128 int128_rems(Int128 a, Int128 b) > } > > #endif > + > +/* > + * Unsigned 256-by-128 division. > + * Returns the remainder via r. > + * Returns lower 128 bit of quotient. > + * Needs a normalized divisor (most significant bit set to 1). > + * > + * Adapted from include/qemu/host-utils.h udiv_qrnnd, > + * from the GNU Multi Precision Library - longlong.h __udiv_qrnnd > + * (https://gmplib.org/repo/gmp/file/tip/longlong.h) > + * > + * Licensed under the GPLv2/LGPLv3 > + */ > +static Int128 udiv256_qrnnd(Int128 *r, Int128 n1, Int128 n0, Int128 d) > +{ > + Int128 d0, d1, q0, q1, r1, r0, m; > + uint64_t mp0, mp1; > + > + d0 =3D int128_make64(int128_getlo(d)); > + d1 =3D int128_make64(int128_gethi(d)); > + > + r1 =3D int128_remu(n1, d1); > + q1 =3D int128_divu(n1, d1); > + mp0 =3D int128_getlo(q1); > + mp1 =3D int128_gethi(q1); > + mulu128(&mp0, &mp1, int128_getlo(d0)); > + m =3D int128_make128(mp0, mp1); > + r1 =3D int128_make128(int128_gethi(n0), int128_getlo(r1)); > + if (int128_ult(r1, m)) { > + q1 =3D int128_sub(q1, int128_one()); > + r1 =3D int128_add(r1, d); > + if (int128_uge(r1, d)) { > + if (int128_ult(r1, m)) { > + q1 =3D int128_sub(q1, int128_one()); > + r1 =3D int128_add(r1, d); > + } > + } > + } > + r1 =3D int128_sub(r1, m); > + > + r0 =3D int128_remu(r1, d1); > + q0 =3D int128_divu(r1, d1); > + mp0 =3D int128_getlo(q0); > + mp1 =3D int128_gethi(q0); > + mulu128(&mp0, &mp1, int128_getlo(d0)); > + m =3D int128_make128(mp0, mp1); > + r0 =3D int128_make128(int128_getlo(n0), int128_getlo(r0)); > + if (int128_ult(r0, m)) { > + q0 =3D int128_sub(q0, int128_one()); > + r0 =3D int128_add(r0, d); > + if (int128_uge(r0, d)) { > + if (int128_ult(r0, m)) { > + q0 =3D int128_sub(q0, int128_one()); > + r0 =3D int128_add(r0, d); > + } > + } > + } > + r0 =3D int128_sub(r0, m); > + > + *r =3D r0; > + return int128_or(int128_lshift(q1, 64), q0); > +} > + > +/* > + * Unsigned 256-by-128 division. > + * Returns the remainder. > + * Returns quotient via plow and phigh. > + * Also returns the remainder via the function return value. > + */ > +Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor) > +{ > + Int128 dhi =3D *phigh; > + Int128 dlo =3D *plow; > + Int128 rem, dhighest; > + int sh; > + > + if (!int128_nz(divisor) || !int128_nz(dhi)) { > + *plow =3D int128_divu(dlo, divisor); > + *phigh =3D int128_zero(); > + return int128_remu(dlo, divisor); > + } else { > + sh =3D clz128(divisor); > + > + if (int128_ult(dhi, divisor)) { > + if (sh !=3D 0) { > + /* normalize the divisor, shifting the dividend > accordingly */ > + divisor =3D int128_lshift(divisor, sh); > + dhi =3D int128_or(int128_lshift(dhi, sh), > + int128_urshift(dlo, (128 - sh))); > + dlo =3D int128_lshift(dlo, sh); > + } > + > + *phigh =3D int128_zero(); > + *plow =3D udiv256_qrnnd(&rem, dhi, dlo, divisor); > + } else { > + if (sh !=3D 0) { > + /* normalize the divisor, shifting the dividend > accordingly */ > + divisor =3D int128_lshift(divisor, sh); > + dhighest =3D int128_rshift(dhi, (128 - sh)); > + dhi =3D int128_or(int128_lshift(dhi, sh), > + int128_urshift(dlo, (128 - sh))); > + dlo =3D int128_lshift(dlo, sh); > + > + *phigh =3D udiv256_qrnnd(&dhi, dhighest, dhi, divisor); > + } else { > + /* > + * dhi >=3D divisor > + * Since the MSB of divisor is set (sh =3D=3D 0), > + * (dhi - divisor) < divisor > + * > + * Thus, the high part of the quotient is 1, and we can > + * calculate the low part with a single call to udiv_qrn= nd > + * after subtracting divisor from dhi > + */ > + dhi =3D int128_sub(dhi, divisor); > + *phigh =3D int128_one(); > + } > + > + *plow =3D udiv256_qrnnd(&rem, dhi, dlo, divisor); > + } > + > + /* > + * since the dividend/divisor might have been normalized, > + * the remainder might also have to be shifted back > + */ > + rem =3D int128_urshift(rem, sh); > + return rem; > + } > +} > + > +/* > + * Signed 256-by-128 division. > + * Returns quotient via plow and phigh. > + * Also returns the remainder via the function return value. > + */ > +Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor) > +{ > + bool neg_quotient =3D false, neg_remainder =3D false; > + Int128 unsig_hi =3D *phigh, unsig_lo =3D *plow; > + Int128 rem; > + > + if (!int128_nonneg(*phigh)) { > + neg_quotient =3D !neg_quotient; > + neg_remainder =3D !neg_remainder; > + > + if (!int128_nz(unsig_lo)) { > + unsig_hi =3D int128_neg(unsig_hi); > + } else { > + unsig_hi =3D int128_not(unsig_hi); > + unsig_lo =3D int128_neg(unsig_lo); > + } > + } > + > + if (!int128_nonneg(divisor)) { > + neg_quotient =3D !neg_quotient; > + > + divisor =3D int128_neg(divisor); > + } > + > + rem =3D divu256(&unsig_lo, &unsig_hi, divisor); > + > + if (neg_quotient) { > + if (!int128_nz(unsig_lo)) { > + *phigh =3D int128_neg(unsig_hi); > + *plow =3D int128_zero(); > + } else { > + *phigh =3D int128_not(unsig_hi); > + *plow =3D int128_neg(unsig_lo); > + } > + } else { > + *phigh =3D unsig_hi; > + *plow =3D unsig_lo; > + } > + > + if (neg_remainder) { > + return int128_neg(rem); > + } else { > + return rem; > + } > +} > -- > 2.37.0.rc0 > > > --=20 Marc-Andr=C3=A9 Lureau --000000000000f7a33705e56cb0f1 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi


On Tue, Jul 12, 2022 at 1:49 PM <= ;marcandre.lureau@redhat.com= > wrote:
= From: Marc-Andr=C3=A9 Lureau <marcandre.lureau@redhat.com>

Break a cyclic dependency between int128 and host-utils.

Anyone to approve that change? (This will allow us to mor= e easily move host-utils & int128 units to a subproject)
= thanks
=C2=A0

Signed-off-by: Marc-Andr=C3=A9 Lureau <marcandre.lureau@redhat.com>
---
=C2=A0include/qemu/host-utils.h |=C2=A0 =C2=A03 -
=C2=A0include/qemu/int128.h=C2=A0 =C2=A0 =C2=A0|=C2=A0 =C2=A03 +
=C2=A0util/host-utils.c=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| 180 ------------= --------------------------
=C2=A0util/int128.c=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0| 180 ++= ++++++++++++++++++++++++++++++++++++
=C2=A04 files changed, 183 insertions(+), 183 deletions(-)

diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h
index 29f3a9987880..fa228a4a86e2 100644
--- a/include/qemu/host-utils.h
+++ b/include/qemu/host-utils.h
@@ -32,7 +32,6 @@

=C2=A0#include "qemu/compiler.h"
=C2=A0#include "qemu/bswap.h"
-#include "qemu/int128.h"

=C2=A0#ifdef CONFIG_INT128
=C2=A0static inline void mulu64(uint64_t *plow, uint64_t *phigh,
@@ -785,6 +784,4 @@ static inline uint64_t udiv_qrnnd(uint64_t *r, uint64_t= n1,
=C2=A0#endif
=C2=A0}

-Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor);
-Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor);
=C2=A0#endif
diff --git a/include/qemu/int128.h b/include/qemu/int128.h
index d2b76ca6acdc..823c61edb0fd 100644
--- a/include/qemu/int128.h
+++ b/include/qemu/int128.h
@@ -472,4 +472,7 @@ static inline void bswap128s(Int128 *s)
=C2=A0#define INT128_MAX int128_make128(UINT64_MAX, INT64_MAX)
=C2=A0#define INT128_MIN int128_make128(0, INT64_MIN)

+Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor);
+Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor);
+
=C2=A0#endif /* INT128_H */
diff --git a/util/host-utils.c b/util/host-utils.c
index fb91bcba823d..96d5dc0bed25 100644
--- a/util/host-utils.c
+++ b/util/host-utils.c
@@ -266,183 +266,3 @@ void ulshift(uint64_t *plow, uint64_t *phigh, int32_t= shift, bool *overflow)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*plow =3D *plow << shift;
=C2=A0 =C2=A0 =C2=A0}
=C2=A0}
-
-/*
- * Unsigned 256-by-128 division.
- * Returns the remainder via r.
- * Returns lower 128 bit of quotient.
- * Needs a normalized divisor (most significant bit set to 1).
- *
- * Adapted from include/qemu/host-utils.h udiv_qrnnd,
- * from the GNU Multi Precision Library - longlong.h __udiv_qrnnd
- * (https://gmplib.org/repo/gmp/file/tip/longlong.h<= /a>)
- *
- * Licensed under the GPLv2/LGPLv3
- */
-static Int128 udiv256_qrnnd(Int128 *r, Int128 n1, Int128 n0, Int128 d)
-{
-=C2=A0 =C2=A0 Int128 d0, d1, q0, q1, r1, r0, m;
-=C2=A0 =C2=A0 uint64_t mp0, mp1;
-
-=C2=A0 =C2=A0 d0 =3D int128_make64(int128_getlo(d));
-=C2=A0 =C2=A0 d1 =3D int128_make64(int128_gethi(d));
-
-=C2=A0 =C2=A0 r1 =3D int128_remu(n1, d1);
-=C2=A0 =C2=A0 q1 =3D int128_divu(n1, d1);
-=C2=A0 =C2=A0 mp0 =3D int128_getlo(q1);
-=C2=A0 =C2=A0 mp1 =3D int128_gethi(q1);
-=C2=A0 =C2=A0 mulu128(&mp0, &mp1, int128_getlo(d0));
-=C2=A0 =C2=A0 m =3D int128_make128(mp0, mp1);
-=C2=A0 =C2=A0 r1 =3D int128_make128(int128_gethi(n0), int128_getlo(r1)); -=C2=A0 =C2=A0 if (int128_ult(r1, m)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 q1 =3D int128_sub(q1, int128_one());
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 r1 =3D int128_add(r1, d);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_uge(r1, d)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_ult(r1, m)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 q1 =3D int128_sub(= q1, int128_one());
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 r1 =3D int128_add(= r1, d);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-=C2=A0 =C2=A0 }
-=C2=A0 =C2=A0 r1 =3D int128_sub(r1, m);
-
-=C2=A0 =C2=A0 r0 =3D int128_remu(r1, d1);
-=C2=A0 =C2=A0 q0 =3D int128_divu(r1, d1);
-=C2=A0 =C2=A0 mp0 =3D int128_getlo(q0);
-=C2=A0 =C2=A0 mp1 =3D int128_gethi(q0);
-=C2=A0 =C2=A0 mulu128(&mp0, &mp1, int128_getlo(d0));
-=C2=A0 =C2=A0 m =3D int128_make128(mp0, mp1);
-=C2=A0 =C2=A0 r0 =3D int128_make128(int128_getlo(n0), int128_getlo(r0)); -=C2=A0 =C2=A0 if (int128_ult(r0, m)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 q0 =3D int128_sub(q0, int128_one());
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 r0 =3D int128_add(r0, d);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_uge(r0, d)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_ult(r0, m)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 q0 =3D int128_sub(= q0, int128_one());
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 r0 =3D int128_add(= r0, d);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-=C2=A0 =C2=A0 }
-=C2=A0 =C2=A0 r0 =3D int128_sub(r0, m);
-
-=C2=A0 =C2=A0 *r =3D r0;
-=C2=A0 =C2=A0 return int128_or(int128_lshift(q1, 64), q0);
-}
-
-/*
- * Unsigned 256-by-128 division.
- * Returns the remainder.
- * Returns quotient via plow and phigh.
- * Also returns the remainder via the function return value.
- */
-Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor)
-{
-=C2=A0 =C2=A0 Int128 dhi =3D *phigh;
-=C2=A0 =C2=A0 Int128 dlo =3D *plow;
-=C2=A0 =C2=A0 Int128 rem, dhighest;
-=C2=A0 =C2=A0 int sh;
-
-=C2=A0 =C2=A0 if (!int128_nz(divisor) || !int128_nz(dhi)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow=C2=A0 =3D int128_divu(dlo, divisor);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_zero();
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 return int128_remu(dlo, divisor);
-=C2=A0 =C2=A0 } else {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 sh =3D clz128(divisor);
-
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_ult(dhi, divisor)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (sh !=3D 0) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /* normalize the d= ivisor, shifting the dividend accordingly */
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 divisor =3D int128= _lshift(divisor, sh);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dhi =3D int128_or(= int128_lshift(dhi, sh),
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 int128_urshift(dlo, (128 - sh))); -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dlo =3D int128_lsh= ift(dlo, sh);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_zero();
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D udiv256_qrnnd(&rem= , dhi, dlo, divisor);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 } else {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (sh !=3D 0) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /* normalize the d= ivisor, shifting the dividend accordingly */
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 divisor =3D int128= _lshift(divisor, sh);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dhighest =3D int12= 8_rshift(dhi, (128 - sh));
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dhi =3D int128_or(= int128_lshift(dhi, sh),
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 int128_urshift(dlo, (128 - sh))); -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dlo =3D int128_lsh= ift(dlo, sh);
-
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D udiv256= _qrnnd(&dhi, dhighest, dhi, divisor);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 } else {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /*
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* dhi >= =3D divisor
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* Since the = MSB of divisor is set (sh =3D=3D 0),
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* (dhi - div= isor) < divisor
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* Thus, the = high part of the quotient is 1, and we can
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* calculate = the low part with a single call to udiv_qrnnd
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* after subt= racting divisor from dhi
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*/
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dhi =3D int128_sub= (dhi, divisor);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_= one();
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D udiv256_qrnnd(&rem= , dhi, dlo, divisor);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 /*
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* since the dividend/divisor might have = been normalized,
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* the remainder might also have to be sh= ifted back
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*/
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 rem =3D int128_urshift(rem, sh);
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 return rem;
-=C2=A0 =C2=A0 }
-}
-
-/*
- * Signed 256-by-128 division.
- * Returns quotient via plow and phigh.
- * Also returns the remainder via the function return value.
- */
-Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor)
-{
-=C2=A0 =C2=A0 bool neg_quotient =3D false, neg_remainder =3D false;
-=C2=A0 =C2=A0 Int128 unsig_hi =3D *phigh, unsig_lo =3D *plow;
-=C2=A0 =C2=A0 Int128 rem;
-
-=C2=A0 =C2=A0 if (!int128_nonneg(*phigh)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 neg_quotient =3D !neg_quotient;
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 neg_remainder =3D !neg_remainder;
-
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (!int128_nz(unsig_lo)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 unsig_hi =3D int128_neg(unsig_hi= );
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 } else {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 unsig_hi =3D int128_not(unsig_hi= );
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 unsig_lo =3D int128_neg(unsig_lo= );
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-=C2=A0 =C2=A0 }
-
-=C2=A0 =C2=A0 if (!int128_nonneg(divisor)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 neg_quotient =3D !neg_quotient;
-
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 divisor =3D int128_neg(divisor);
-=C2=A0 =C2=A0 }
-
-=C2=A0 =C2=A0 rem =3D divu256(&unsig_lo, &unsig_hi, divisor);
-
-=C2=A0 =C2=A0 if (neg_quotient) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (!int128_nz(unsig_lo)) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_neg(unsig_hi);=
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D int128_zero();
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 } else {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_not(unsig_hi);=
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D int128_neg(unsig_lo);<= br> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
-=C2=A0 =C2=A0 } else {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D unsig_hi;
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D unsig_lo;
-=C2=A0 =C2=A0 }
-
-=C2=A0 =C2=A0 if (neg_remainder) {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 return int128_neg(rem);
-=C2=A0 =C2=A0 } else {
-=C2=A0 =C2=A0 =C2=A0 =C2=A0 return rem;
-=C2=A0 =C2=A0 }
-}
diff --git a/util/int128.c b/util/int128.c
index ed8f25fef161..482c63b6551e 100644
--- a/util/int128.c
+++ b/util/int128.c
@@ -145,3 +145,183 @@ Int128 int128_rems(Int128 a, Int128 b)
=C2=A0}

=C2=A0#endif
+
+/*
+ * Unsigned 256-by-128 division.
+ * Returns the remainder via r.
+ * Returns lower 128 bit of quotient.
+ * Needs a normalized divisor (most significant bit set to 1).
+ *
+ * Adapted from include/qemu/host-utils.h udiv_qrnnd,
+ * from the GNU Multi Precision Library - longlong.h __udiv_qrnnd
+ * (https://gmplib.org/repo/gmp/file/tip/longlong.h<= /a>)
+ *
+ * Licensed under the GPLv2/LGPLv3
+ */
+static Int128 udiv256_qrnnd(Int128 *r, Int128 n1, Int128 n0, Int128 d)
+{
+=C2=A0 =C2=A0 Int128 d0, d1, q0, q1, r1, r0, m;
+=C2=A0 =C2=A0 uint64_t mp0, mp1;
+
+=C2=A0 =C2=A0 d0 =3D int128_make64(int128_getlo(d));
+=C2=A0 =C2=A0 d1 =3D int128_make64(int128_gethi(d));
+
+=C2=A0 =C2=A0 r1 =3D int128_remu(n1, d1);
+=C2=A0 =C2=A0 q1 =3D int128_divu(n1, d1);
+=C2=A0 =C2=A0 mp0 =3D int128_getlo(q1);
+=C2=A0 =C2=A0 mp1 =3D int128_gethi(q1);
+=C2=A0 =C2=A0 mulu128(&mp0, &mp1, int128_getlo(d0));
+=C2=A0 =C2=A0 m =3D int128_make128(mp0, mp1);
+=C2=A0 =C2=A0 r1 =3D int128_make128(int128_gethi(n0), int128_getlo(r1)); +=C2=A0 =C2=A0 if (int128_ult(r1, m)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 q1 =3D int128_sub(q1, int128_one());
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 r1 =3D int128_add(r1, d);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_uge(r1, d)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_ult(r1, m)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 q1 =3D int128_sub(= q1, int128_one());
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 r1 =3D int128_add(= r1, d);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+=C2=A0 =C2=A0 }
+=C2=A0 =C2=A0 r1 =3D int128_sub(r1, m);
+
+=C2=A0 =C2=A0 r0 =3D int128_remu(r1, d1);
+=C2=A0 =C2=A0 q0 =3D int128_divu(r1, d1);
+=C2=A0 =C2=A0 mp0 =3D int128_getlo(q0);
+=C2=A0 =C2=A0 mp1 =3D int128_gethi(q0);
+=C2=A0 =C2=A0 mulu128(&mp0, &mp1, int128_getlo(d0));
+=C2=A0 =C2=A0 m =3D int128_make128(mp0, mp1);
+=C2=A0 =C2=A0 r0 =3D int128_make128(int128_getlo(n0), int128_getlo(r0)); +=C2=A0 =C2=A0 if (int128_ult(r0, m)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 q0 =3D int128_sub(q0, int128_one());
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 r0 =3D int128_add(r0, d);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_uge(r0, d)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_ult(r0, m)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 q0 =3D int128_sub(= q0, int128_one());
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 r0 =3D int128_add(= r0, d);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+=C2=A0 =C2=A0 }
+=C2=A0 =C2=A0 r0 =3D int128_sub(r0, m);
+
+=C2=A0 =C2=A0 *r =3D r0;
+=C2=A0 =C2=A0 return int128_or(int128_lshift(q1, 64), q0);
+}
+
+/*
+ * Unsigned 256-by-128 division.
+ * Returns the remainder.
+ * Returns quotient via plow and phigh.
+ * Also returns the remainder via the function return value.
+ */
+Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor)
+{
+=C2=A0 =C2=A0 Int128 dhi =3D *phigh;
+=C2=A0 =C2=A0 Int128 dlo =3D *plow;
+=C2=A0 =C2=A0 Int128 rem, dhighest;
+=C2=A0 =C2=A0 int sh;
+
+=C2=A0 =C2=A0 if (!int128_nz(divisor) || !int128_nz(dhi)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow=C2=A0 =3D int128_divu(dlo, divisor);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_zero();
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 return int128_remu(dlo, divisor);
+=C2=A0 =C2=A0 } else {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 sh =3D clz128(divisor);
+
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (int128_ult(dhi, divisor)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (sh !=3D 0) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /* normalize the d= ivisor, shifting the dividend accordingly */
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 divisor =3D int128= _lshift(divisor, sh);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dhi =3D int128_or(= int128_lshift(dhi, sh),
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 int128_urshift(dlo, (128 - sh))); +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dlo =3D int128_lsh= ift(dlo, sh);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_zero();
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D udiv256_qrnnd(&rem= , dhi, dlo, divisor);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 } else {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (sh !=3D 0) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /* normalize the d= ivisor, shifting the dividend accordingly */
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 divisor =3D int128= _lshift(divisor, sh);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dhighest =3D int12= 8_rshift(dhi, (128 - sh));
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dhi =3D int128_or(= int128_lshift(dhi, sh),
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 int128_urshift(dlo, (128 - sh))); +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dlo =3D int128_lsh= ift(dlo, sh);
+
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D udiv256= _qrnnd(&dhi, dhighest, dhi, divisor);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 } else {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 /*
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* dhi >= =3D divisor
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* Since the = MSB of divisor is set (sh =3D=3D 0),
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* (dhi - div= isor) < divisor
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* Thus, the = high part of the quotient is 1, and we can
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* calculate = the low part with a single call to udiv_qrnnd
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* after subt= racting divisor from dhi
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*/
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 dhi =3D int128_sub= (dhi, divisor);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_= one();
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D udiv256_qrnnd(&rem= , dhi, dlo, divisor);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 /*
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* since the dividend/divisor might have = been normalized,
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* the remainder might also have to be sh= ifted back
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*/
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 rem =3D int128_urshift(rem, sh);
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 return rem;
+=C2=A0 =C2=A0 }
+}
+
+/*
+ * Signed 256-by-128 division.
+ * Returns quotient via plow and phigh.
+ * Also returns the remainder via the function return value.
+ */
+Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor)
+{
+=C2=A0 =C2=A0 bool neg_quotient =3D false, neg_remainder =3D false;
+=C2=A0 =C2=A0 Int128 unsig_hi =3D *phigh, unsig_lo =3D *plow;
+=C2=A0 =C2=A0 Int128 rem;
+
+=C2=A0 =C2=A0 if (!int128_nonneg(*phigh)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 neg_quotient =3D !neg_quotient;
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 neg_remainder =3D !neg_remainder;
+
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (!int128_nz(unsig_lo)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 unsig_hi =3D int128_neg(unsig_hi= );
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 } else {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 unsig_hi =3D int128_not(unsig_hi= );
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 unsig_lo =3D int128_neg(unsig_lo= );
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+=C2=A0 =C2=A0 }
+
+=C2=A0 =C2=A0 if (!int128_nonneg(divisor)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 neg_quotient =3D !neg_quotient;
+
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 divisor =3D int128_neg(divisor);
+=C2=A0 =C2=A0 }
+
+=C2=A0 =C2=A0 rem =3D divu256(&unsig_lo, &unsig_hi, divisor);
+
+=C2=A0 =C2=A0 if (neg_quotient) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 if (!int128_nz(unsig_lo)) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_neg(unsig_hi);=
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D int128_zero();
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 } else {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D int128_not(unsig_hi);=
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D int128_neg(unsig_lo);<= br> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+=C2=A0 =C2=A0 } else {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 *phigh =3D unsig_hi;
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 *plow =3D unsig_lo;
+=C2=A0 =C2=A0 }
+
+=C2=A0 =C2=A0 if (neg_remainder) {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 return int128_neg(rem);
+=C2=A0 =C2=A0 } else {
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 return rem;
+=C2=A0 =C2=A0 }
+}
--
2.37.0.rc0




--
Marc-Andr=C3=A9 Lureau
--000000000000f7a33705e56cb0f1--