Received: by 2002:ab2:3141:0:b0:1ed:23cc:44d1 with SMTP id i1csp1050858lqg; Sat, 2 Mar 2024 13:05:25 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCXGHMSwDczL1N9YvthOsYXKEydevREjc+y8CWxO4d3YpKaM9OuifkdSYV3nOHFC9BLni/H063nu2YjiGfa6ekV5MBs/5reCwvnFC+vg8w== X-Google-Smtp-Source: AGHT+IEAfU7LqkvoVRtI4XBHOuFTOj0Srq3p4xRYuLQ4xyFzr70+bFVQ1UUKHKoP1y/Lmi/YVafx X-Received: by 2002:a05:6808:201f:b0:3c1:cb2a:b7e with SMTP id q31-20020a056808201f00b003c1cb2a0b7emr6782112oiw.5.1709413525354; Sat, 02 Mar 2024 13:05:25 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1709413525; cv=pass; d=google.com; s=arc-20160816; b=erTqG8O9DVsrNkkhuP/NaBIa+IQiNauxbY94LyU8/twbLpiGWPXWDF0N/ipJfLjfPD /HrxzvXw3NsZDCvzvSLYEnbDKfZlHM9DS0tOFj4q1tIQZ7cPQrjI5zYDdTfedAmQxfGV FuhYgzezLdXgb18K4mVMQJboIEymPQCUJegaQS7yOh26nokmJA23/EOEvFZGM+XQRef4 UegtOce5BkHehb6Admoi9q4nSFwLHfLV74Dj7d6ECwSRk/s1ijyr7SUM9nN8olxMkXEc Ayit55mEL/npfRuakPt0nwQFO2yA59I6ChQb+3Kq03IK866lxiM8S3K080ouFMpZiS7v 1aGA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=in-reply-to:content-disposition:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:references:message-id:subject:cc :to:from:date; bh=bGTVCDaL/A5WqFccUgWC2J3/+gUgQOM8pz2ykGR6zvg=; fh=GF04SddAcWiYfhCPXG70brY8nKzKGtou+R3mq78Phng=; b=lehJE/8yaTsohTrhof4BFa6i0P4AimhGjeleRmEShZBhXy9xXCqPsqs4eYtZVgBT0w j1iHP5YiaP2DQd4z6b/IJQawxGF1mrGj3BQbZcLX+MSVkEjm1bwodDwb+a4UPAu+QQyo QdNdk1bZ3GzumGWrU0SM3QUuKNFSCUeSBZCPoeJTEJNhOrM9rR8hiIequRhEqTWrxQNq glQ+bkp1pGBh4JW8cdwyZ6ZCx4ZwnZAYPPk5VIUUC8eXs6kdEADxl9CRJpJv2EBKWD8O c5dT8tIOi3/bayeHGFZ7iqogaK4w1HCiNU6EyP0U4qRL7LqPGdgRJt4pEtWEkqrh8X+a HSzQ==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; arc=pass (i=1 spf=pass spfdomain=pengutronix.de); spf=pass (google.com: domain of linux-kernel+bounces-89597-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-89597-linux.lists.archive=gmail.com@vger.kernel.org" Return-Path: Received: from sv.mirrors.kernel.org (sv.mirrors.kernel.org. [139.178.88.99]) by mx.google.com with ESMTPS id z67-20020a636546000000b005dc12137745si5728754pgb.151.2024.03.02.13.05.25 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 02 Mar 2024 13:05:25 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-89597-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99; Authentication-Results: mx.google.com; arc=pass (i=1 spf=pass spfdomain=pengutronix.de); spf=pass (google.com: domain of linux-kernel+bounces-89597-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-89597-linux.lists.archive=gmail.com@vger.kernel.org" Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sv.mirrors.kernel.org (Postfix) with ESMTPS id 9E5A3282DC9 for ; Sat, 2 Mar 2024 21:05:24 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id E60E140C1F; Sat, 2 Mar 2024 21:05:18 +0000 (UTC) Received: from metis.whiteo.stw.pengutronix.de (metis.whiteo.stw.pengutronix.de [185.203.201.7]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 95F1417C69 for ; Sat, 2 Mar 2024 21:05:15 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=185.203.201.7 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709413518; cv=none; b=QRQ9kissgAjI3YKtxoxVvHMClalVyBorFoySIHxeIUG292Bm3CkJD8iueInNYCvLRWyEoCpLSHsrgKdns7f2UaZjWTTWiSk+cgaM1t1cbSsgvww3Lm2/ZJhYAgMRLEH93SWvGl9UJGmoN5/BVN0Vr1X3B2TG4p2dCdRMaf/hcJE= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709413518; c=relaxed/simple; bh=pPIJ3yApZLbe54NrsOEjiQdYrpXf6sa/2ELrkOiAhy4=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=JR8+ajN3wJmtf/H/b+xYjg1N/I3jvVt1QN4uKzUtB9lOuc+VWsoGTabvN1yUDAmqhpZYY5OWN2/JLQ+S3gbc6C0/b71b6G+Lk4wNifW/ML+X9899JRDA/dSsQDUD6ls0/Lhz2ZMjZOLfuuwudyqG5C+tsRAxaeBpuRcdBWiQ7gQ= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pengutronix.de; spf=pass smtp.mailfrom=pengutronix.de; arc=none smtp.client-ip=185.203.201.7 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pengutronix.de Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pengutronix.de Received: from drehscheibe.grey.stw.pengutronix.de ([2a0a:edc0:0:c01:1d::a2]) by metis.whiteo.stw.pengutronix.de with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1rgWXg-0005K9-J2; Sat, 02 Mar 2024 22:05:12 +0100 Received: from [2a0a:edc0:0:b01:1d::7b] (helo=bjornoya.blackshift.org) by drehscheibe.grey.stw.pengutronix.de with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1rgWXf-0042Ig-KM; Sat, 02 Mar 2024 22:05:11 +0100 Received: from pengutronix.de (unknown [172.20.34.65]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (prime256v1) server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) (Authenticated sender: mkl-all@blackshift.org) by smtp.blackshift.org (Postfix) with ESMTPSA id 4C01F29C36E; Sat, 2 Mar 2024 21:05:11 +0000 (UTC) Date: Sat, 2 Mar 2024 22:05:09 +0100 From: Marc Kleine-Budde To: Uwe =?utf-8?Q?Kleine-K=C3=B6nig?= Cc: Andrew Morton , Biju Das , linux-kernel@vger.kernel.org, kernel@pengutronix.de Subject: Re: [PATCH] mul_u64_u64_div_u64: Increase precision by conditionally swapping a and b Message-ID: <20240302-deed-greyhound-f0c6c831e4c7-mkl@pengutronix.de> References: <20240302205426.639205-2-u.kleine-koenig@pengutronix.de> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="vdhplgvmqojqydbk" Content-Disposition: inline In-Reply-To: <20240302205426.639205-2-u.kleine-koenig@pengutronix.de> X-SA-Exim-Connect-IP: 2a0a:edc0:0:c01:1d::a2 X-SA-Exim-Mail-From: mkl@pengutronix.de X-SA-Exim-Scanned: No (on metis.whiteo.stw.pengutronix.de); SAEximRunCond expanded to false X-PTX-Original-Recipient: linux-kernel@vger.kernel.org --vdhplgvmqojqydbk Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On 02.03.2024 21:54:27, Uwe Kleine-K=C3=B6nig wrote: > As indicated in the added comment, the algorithm works better if b is > big. As multiplication is commutative, a and b can be swapped. Do this > If a is bigger than b. >=20 > Signed-off-by: Uwe Kleine-K=C3=B6nig > --- > lib/math/div64.c | 17 +++++++++++++++++ > 1 file changed, 17 insertions(+) >=20 > diff --git a/lib/math/div64.c b/lib/math/div64.c > index 55a81782e271..baf6f8681907 100644 > --- a/lib/math/div64.c > +++ b/lib/math/div64.c > @@ -190,6 +190,23 @@ u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 c) > =20 > /* can a * b overflow ? */ > if (ilog2(a) + ilog2(b) > 62) { > + /* > + * Note that the algorithm after the if block below might loose > + * some precision and the result is more exact for b > a. So > + * exchange a and b if a is bigger than b. > + * > + * For example with a =3D 43980465100800, b =3D 100000000, c =3D 10000= 00000 > + * the below calculation doesn't modify b at all because div =3D=3D 0 > + * and then shift becomes 45 + 26 - 62 =3D 9 and so the result > + * becomes 4398035251080. However with a and b swapped the exact > + * result is calculated (i.e. 4398046510080). > + */ > + if (a > b) { > + u64 tmp =3D a; > + a =3D b; > + b =3D tmp; You can use swap() from linux/minmax.h here. Marc > + } > + > /* > * (b * a) / c is equal to > * >=20 > base-commit: 1870cdc0e8dee32e3c221704a2977898ba4c10e8 > --=20 > 2.43.0 >=20 >=20 >=20 --=20 Pengutronix e.K. | Marc Kleine-Budde | Embedded Linux | https://www.pengutronix.de | Vertretung N=C3=BCrnberg | Phone: +49-5121-206917-129 | Amtsgericht Hildesheim, HRA 2686 | Fax: +49-5121-206917-9 | --vdhplgvmqojqydbk Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQEzBAABCgAdFiEEUEC6huC2BN0pvD5fKDiiPnotvG8FAmXjlIIACgkQKDiiPnot vG+MJAf/b7QUr91MOkjnM0RsU4uetTKQ1Kf7OhsaPJHC4wzqeoezIPdDRYUz/3Iz o14MmVROUmCNN2s3qeBau+AERjyzPa0Q/pexoAK47GGE2kiR93P9/DwbPAFyE0Qb Rrdv1pEbc+P+32LcF3gWrNI5tdaW5/PdrIZVbYH/HDHifja+lctvtQFiPbqaoGkU Xi1+GCvoymigqHnN6p8Jt4ZoqDnS75HYBBaEebmfHARSKZ7bsZ/tK6NIcqQsSZMH d4pZDFC+aOwAUucGr6i1Gs9W5Y2icJGI/T4/hYyusliD1DoqTzye5HRvLeidDBUw GHSSIQDjLOW7A/68n/GuHapzx01Mmg== =SOi2 -----END PGP SIGNATURE----- --vdhplgvmqojqydbk--