From nobody Tue Feb 10 12:59:22 2026 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1660136690; cv=none; d=zohomail.com; s=zohoarc; b=JSnO71xWxo/gL+MPHiR62glrewAMkMTqNceJVHvHzsTYo+fhxP0FTNEphd1ucFWt1I+EGkpDO9+DguaJYGB4TiY7LtN8mEGKRLJRihRLYcIwdFvXOI0mUbAi7NS5LmvyMb4GlAmTCC2UrJJjp9CXhmriqjd+AqITlm5w0gXL6CY= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1660136690; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=+eXohUduyjohEF9ww8ZVus4+1CSV2I4j5kLCxGMy+20=; b=FFxMR80tNCsRqTqcA2cFzH/59EMNi2Gjm1ppD14MF/Emco/YLjJuVWXzOIuyQJ9f1QfFTeKecxGsp+oqlS1EUpsfpEVrCJifSDDraPZeyDTGl024wzunjdOOcR4s9H0XuYE8nVBplqgn47TzEmbwZ4F/h0RAHLR+6aeoHYZbvsY= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1660136690156303.473182218027; Wed, 10 Aug 2022 06:04:50 -0700 (PDT) Received: from localhost ([::1]:43794 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oLlOB-0008Gg-R2 for importer@patchew.org; Wed, 10 Aug 2022 09:04:47 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:46864) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oLl9w-0001rA-HH for qemu-devel@nongnu.org; Wed, 10 Aug 2022 08:50:08 -0400 Received: from us-smtp-delivery-124.mimecast.com ([170.10.133.124]:30339) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oLl9u-0007YY-5B for qemu-devel@nongnu.org; Wed, 10 Aug 2022 08:50:04 -0400 Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-292-k3d5mrr8PmW5IghLuY5pEg-1; Wed, 10 Aug 2022 08:49:59 -0400 Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 4DF3F91B1FA; Wed, 10 Aug 2022 12:49:53 +0000 (UTC) Received: from localhost (unknown [10.39.208.40]) by smtp.corp.redhat.com (Postfix) with ESMTP id 9B041492CA9; Wed, 10 Aug 2022 12:49:51 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1660135801; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=+eXohUduyjohEF9ww8ZVus4+1CSV2I4j5kLCxGMy+20=; b=MrQKRduYwNhwicrbSQZw6wF7P4F23yHLWlpLOMOmiDX3qQRNtMuGzz1Zkd/EUSBOgkkDI9 Rz4K7aFxPk4J2jJaJDJIvQyNlaeXf2ADf6Yflhg0xd/UTfH3FH4BwhI4vg9oZpoxE/QpKb miFnn1CZFMdzbOF0xtKhTcC7ixpvYuc= X-MC-Unique: k3d5mrr8PmW5IghLuY5pEg-1 From: marcandre.lureau@redhat.com To: qemu-devel@nongnu.org Cc: Markus Armbruster , Peter Maydell , Cleber Rosa , Michael Roth , John Snow , Xie Yongji , Paolo Bonzini , =?UTF-8?q?Marc-Andr=C3=A9=20Lureau?= Subject: [PATCH v3 10/16] util: move 256-by-128 division helpers to int128 Date: Wed, 10 Aug 2022 16:48:51 +0400 Message-Id: <20220810124857.1360211-11-marcandre.lureau@redhat.com> In-Reply-To: <20220810124857.1360211-1-marcandre.lureau@redhat.com> References: <20220810124857.1360211-1-marcandre.lureau@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-Scanned-By: MIMEDefang 2.85 on 10.11.54.9 Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=170.10.133.124; envelope-from=marcandre.lureau@redhat.com; helo=us-smtp-delivery-124.mimecast.com X-Spam_score_int: -21 X-Spam_score: -2.2 X-Spam_bar: -- X-Spam_report: (-2.2 / 5.0 requ) BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.082, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, 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+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: pass (identity @redhat.com) X-ZM-MESSAGEID: 1660136692660100002 From: Marc-Andr=C3=A9 Lureau Break a cyclic dependency between int128 and host-utils. Signed-off-by: Marc-Andr=C3=A9 Lureau Reviewed-by: Lucas Mateus Castro --- 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 88d476161c..e8162fb6b0 100644 --- a/include/qemu/host-utils.h +++ b/include/qemu/host-utils.h @@ -32,7 +32,6 @@ =20 #include "qemu/compiler.h" #include "qemu/bswap.h" -#include "qemu/int128.h" =20 #ifdef CONFIG_INT128 static inline void mulu64(uint64_t *plow, uint64_t *phigh, @@ -784,6 +783,4 @@ static inline uint64_t udiv_qrnnd(uint64_t *r, uint64_t= n1, #endif } =20 -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 d2b76ca6ac..823c61edb0 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) =20 +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 fb91bcba82..96d5dc0bed 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 accordingl= y */ - 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 accordingl= y */ - 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_qrnnd - * 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 ed8f25fef1..482c63b655 100644 --- a/util/int128.c +++ b/util/int128.c @@ -145,3 +145,183 @@ Int128 int128_rems(Int128 a, Int128 b) } =20 #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 accordingl= y */ + 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 accordingl= y */ + 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_qrnnd + * 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; + } +} --=20 2.37.1