From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <Pavan.Bhagavatula@cavium.com>
Received: from NAM01-BY2-obe.outbound.protection.outlook.com
 (mail-by2nam01on0072.outbound.protection.outlook.com [104.47.34.72])
 by dpdk.org (Postfix) with ESMTP id 728A07CE5
 for <dev@dpdk.org>; Mon,  4 Dec 2017 14:23:04 +0100 (CET)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=CAVIUMNETWORKS.onmicrosoft.com; s=selector1-cavium-com;
 h=From:Date:Subject:Message-ID:Content-Type:MIME-Version;
 bh=5gaYvA7p8eIM//6IvJIBhUUXleOjmeDXH0E/3JWJwc4=;
 b=dEQbGdJESla4IXSNvZqQ1uMhIK3aVI+fPBvdIOjANxUQIYOJXRCTfYRlORCgw3YzNEKrNgCORjHyCiKLaRA4TsTnS+eX+QJFDmT/F0wml0YkfrR/02CgO+d79EqWx6EeTjMRnga7X8HeD62uEmRqn4fYllv270kQKOkqHrb9Ie4=
Authentication-Results: spf=none (sender IP is )
 smtp.mailfrom=Pavan.Bhagavatula@cavium.com; 
Received: from Pavan-LT.caveonetworks.com (111.93.218.67) by
 CY4PR07MB3461.namprd07.prod.outlook.com (10.171.252.142) with Microsoft SMTP
 Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id
 15.20.282.5; Mon, 4 Dec 2017 13:23:01 +0000
From: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
To: cristian.dumitrescu@intel.com, stephen@networkplumber.org,
 ktraynor@redhat.com
Cc: dev@dpdk.org,
	Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
Date: Mon,  4 Dec 2017 18:52:30 +0530
Message-Id: <20171204132231.29975-2-pbhagavatula@caviumnetworks.com>
X-Mailer: git-send-email 2.14.1
In-Reply-To: <20171204132231.29975-1-pbhagavatula@caviumnetworks.com>
References: <1504032378-5483-1-git-send-email-pbhagavatula@caviumnetworks.com>
 <20171204132231.29975-1-pbhagavatula@caviumnetworks.com>
MIME-Version: 1.0
Content-Type: text/plain
X-Originating-IP: [111.93.218.67]
X-ClientProxiedBy: DM5PR13CA0042.namprd13.prod.outlook.com (10.168.240.156) To
 CY4PR07MB3461.namprd07.prod.outlook.com (10.171.252.142)
X-MS-PublicTrafficType: Email
X-MS-Office365-Filtering-Correlation-Id: 00c527a4-9e27-487e-2698-08d53b1a25c3
X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0;
 RULEID:(4534020)(4602075)(4627115)(201703031133081)(201702281549075)(5600026)(4604075)(2017052603286);
 SRVR:CY4PR07MB3461; 
X-Microsoft-Exchange-Diagnostics: 1; CY4PR07MB3461;
 3:h8lKneOdRecfggGn5Pn7WB5Yzymb7ewl74SIjnQcKGHed9Cv5AjTvoxWEYp7OtRh1iyhHh4oKhB3bNAkHwscjf39w2VSdEqjvhRURDCxFq6lSZo/aKJyqxLHm7EB2JaRTmq1qieJBTlZN0ErgsaN6WDXQWRi3wrGfYw8pp+6RKJekSA4r0w/o3SAEO6KRYMZ23lCjOySAItoHp6Hb5XzWkrD8kzongrUF8ecSR+cwdt9cV/fz+MHqu0Vf2QqvWcs;
 25:hCz+o4WOsBcBvUYGtUkbigA/Uj7Kn4KYhl8bOUsSY8YE2Z1+8Liy4+2RZDYHTvFuffCEUzbTiIKy8V+BS6VhgmmhW9mENJn2e7A33NT7Ccqn8+Ny9SfmdSg2KCA7dZc5nFyVVevBDl/cfeCyg63k2os7OUZo9RrPKNJjLmdGV0ls1vdxu0RsymOUow/fUZ/VcXfIsu2HGTmOP5xG2xREisUexQV9IAtWKKQfhzh7qh1cqI1IqHYbl6cijAIeDPu+R84mK9Gy/D9cMOGSJBIOKJPKdWGsAvaK3ca18LFdauxi9EVDRAeoTxn6mt067wmmtGOTjomsAw4vFl2t/Z8zKg==;
 31:rwz6logL37G6Yn6puPQ/a9TXNPD29dVmjQJl3j5N+gQIwTD8LH5VDaL2rGtjqyECZuCW6p8AZQwWFzae9arK8suBau+5Jo8OGjNYERX2rBJVBBmtwbFx4eB4d27D6H6T+vy1Gm8nlKJt1+x81cr5IgdjamsBNo5tmqUaJN78B1Ou3Y2aqSv9YupUzZLa0EZ2wASINy3bXl1y5MaNtjNXTXTpjBjQkM3WNgn1aOqitxE=
X-MS-TrafficTypeDiagnostic: CY4PR07MB3461:
X-Microsoft-Exchange-Diagnostics: 1; CY4PR07MB3461;
 20:3EBLitDyJWSEHrvTjaGfqjFyeiwpqN4epymMbdjSohjcmajWn+XZJceGqIUrJNkaqeK/ITwaVwpDjVuUodBJvLuR2pMc/un01HeogxC+DDOahAHU6efsml67BccnN6+r1KtkOXVuO2LrbdAt6cQQVCorZtxGJsInjmFJFKxbOWmJS37Hg5cCxey0VxDGlu1U4Wc81Hg2fSwKsq36hCA7iYwyQC2uHRDURUCdexbkWKDOZ8wvvxlGnYj+BdSCUG+dQIvDLl/zbkncXFMBgF5LHZJ+sy0/coHxtguBc2fOYNw8HmKDM7k7EKZfwvhRhKWyWxqDdlvOR0YR3Z4V68CypLEvcJpIHPV6Eo4Jw1MOr6TWPH6lWEAlBI/x53MThdHvT+HS7iSxVsWMpTRY59CJlllrJlmF8Z/F3rlBrbn7wmCUqRTDaLXY600atL9tYDBxD9erCxeYMJzxhZ6SsDUhGjux7rDVIEQAHanaj8ufudY4TLc6pYMUTkV9CliKRaMqPCWqIcLNMZCjoxDiYmxOUuOYvYrxg0ta7B629l3FfshHpkrHJuJZ5uzCov+pJQdH+lJZE3g4Img/Mv6JKrZkY1cVrRwwNvNqXLxg1Fxu2Eg=;
 4:STgS4zRKv+dm0qpk5dl3WjyFHjxYnkNc248XdnlNMcit3rVncU7q9Mc5fSNPMwkWhSnedAXFd93lwJ9QDQow1Cvb1IpLKCeu7lD3xVWEQ7+axChYnsnVUUcee7LnHXBF1Ckh1yXGZHBgxKNxaaitY7Q3TZDhDwLwxkeLQHy2+qf82cQHXT5kPqef1na2hM44SFtf7EDb9UZ5AT04J4VeiMG58tGUO4czKSP1sNxcyRUQsf1OBleAavRE5s7LEYeiTCCMuBJ93GnBSSDiPciTnQ==
X-Microsoft-Antispam-PRVS: <CY4PR07MB3461869ECCA765498459245E803C0@CY4PR07MB3461.namprd07.prod.outlook.com>
X-Exchange-Antispam-Report-Test: UriScan:;
X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0;
 RULEID:(6040450)(2401047)(8121501046)(5005006)(10201501046)(3231022)(3002001)(93006095)(6041248)(20161123555025)(20161123562025)(20161123560025)(20161123564025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123558100)(6072148)(201708071742011);
 SRVR:CY4PR07MB3461; BCL:0; PCL:0; RULEID:(100000803101)(100110400095);
 SRVR:CY4PR07MB3461; 
X-Forefront-PRVS: 051158ECBB
X-Forefront-Antispam-Report: SFV:NSPM;
 SFS:(10009020)(6009001)(346002)(376002)(366004)(189002)(199003)(76176011)(48376002)(72206003)(3846002)(50466002)(2950100002)(42882006)(7736002)(52116002)(6666003)(51416003)(6116002)(6512007)(16586007)(6306002)(16526018)(53936002)(101416001)(69596002)(68736007)(33646002)(107886003)(5009440100003)(316002)(305945005)(966005)(1076002)(97736004)(5660300001)(4326008)(53416004)(8936002)(189998001)(2906002)(105586002)(106356001)(6486002)(81166006)(81156014)(8676002)(478600001)(6506006)(36756003)(25786009)(50226002)(66066001)(47776003)(42262002)(562404015);
 DIR:OUT; SFP:1101; SCL:1; SRVR:CY4PR07MB3461; H:Pavan-LT.caveonetworks.com;
 FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en; 
Received-SPF: None (protection.outlook.com: cavium.com does not designate
 permitted sender hosts)
X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; CY4PR07MB3461;
 23:YQEkd/dY44W1wooHk23d4nGafqIiPVvxP8YZ3nM3P?=
 =?us-ascii?Q?OsHsXUMdgYqa1tTtpXSH7D/9wemO1XJnLLnyB3in7GQYvNBGBb06YSwVZWmO?=
 =?us-ascii?Q?bftTtKGOs1xEnUpLJM2kYdqg9W/h/wuL7g8XyW3BA+BM2KWc2iYtkCxa+FZe?=
 =?us-ascii?Q?mg4OaLvTPDm5ErKzKTReQvAGm+HnvL/x7yVaFIbKLJyhepaLDMXB1UL2eQ3Z?=
 =?us-ascii?Q?pznVArecuB5JOV2h6nZEc2wYwJjwxn9oXoKLynlderfl6mhFDsnsugQkP4X1?=
 =?us-ascii?Q?mMZtgenRj6CJrZhfdj8bEN6k2iJOStoasqDh9FNT7MEQYMeYPMQUfHNz/A4t?=
 =?us-ascii?Q?PLYslUI8aakNjWT7IUq57s7QXeidDf3Lok4rt3QZ+ElLGHLQm8EJg/rok15P?=
 =?us-ascii?Q?m1wlfeQobtxnmhk9APDbEC8rE197DJk08alAchty7m4LZMb4IT4LHq9EFZYk?=
 =?us-ascii?Q?5bAMCMZn5hicMQtKzS4WwAaNpQz4KdD8+ftE854DSkAsRQOHwj0EEyjslxQE?=
 =?us-ascii?Q?v4tUKUWGX7iIBEv50W43bUOlbxoAzNgD/gAWDU+n33nRxDaVldkQd+dy0oNd?=
 =?us-ascii?Q?UMDCemNx0z3baC6+IwvwO9sDt3qSut6HOj/xSVu8DF0YQDItkP7WXCRLJr8f?=
 =?us-ascii?Q?SHgkTANzp151YWWwOJ0txm5skhFM86/Ku0pWfVVWqlRknvHvc5WhK9HRIxMc?=
 =?us-ascii?Q?zXYgKD+l6AgH3iSY4Rzi2Aimpf782SNFHzyQn/51HAmW+OoNGGKMgtqD81hx?=
 =?us-ascii?Q?YvCJyEH2PHmyWJ7XhEa7UmTr+2pmiA84W/WPLzU38R/qQRDM1NVoevXJdgmb?=
 =?us-ascii?Q?JM9yE8PwyWedQVIrkqR7xqv/3xVMU1mUI/VMP5tzaEbC0/PUTzE0NNMYbrFt?=
 =?us-ascii?Q?oIc5rBqQ0zG6SZL58l7BM1DrU+aH3fom9cLvgPVsTl2eeZGwwpYTSMPQd+iD?=
 =?us-ascii?Q?cvn2LoJDN+G11JUCXsJdlrl1XzcX3gH3rMegrBfmK+hNsLI7eJDanKdk3tQU?=
 =?us-ascii?Q?na6lPrd6WfUlLxGrnm0NsJ0ZdSf/WfnMO8MkRszuo761hg2efYOQq1zmZjA8?=
 =?us-ascii?Q?qFjGnPuQUNnxskIKxdXTrw8DPPZ2e0UXYNmLNsTpsd8o95YkLivpkBCRyR/g?=
 =?us-ascii?Q?jOZSlRJ3DLhNKX3BDs8saNKzD2GtbNxbjDXAKDmPXc4irvHLxrjZt2XQ/8Nh?=
 =?us-ascii?Q?EWt90mQngDJxvb0Di/NSpDX7WTeHR9Uw9+MVZ0j2QwwSb88wVC1K6kmquB7M?=
 =?us-ascii?Q?xLljFOseALyElcqdj4Ej6f+ZqKL+ReReAHfkSdI?=
X-Microsoft-Antispam-Message-Info: OBkwMRKHLMMW0qiUARC/yff/CyKQ/lnyhDI4k0Zc9XeH2z6eoQ5pomPjRZZjSegEJYA1aVz2Qbpsdn6PQ51Xpg==
X-Microsoft-Exchange-Diagnostics: 1; CY4PR07MB3461;
 6:iBY6PpBCLZ4y0gsQwtFs3eiShF9HSan6EOx/5g5AryDbazoTeRxDO/4Byh/cfzR8HEC+bH8v/ybRr5l2XIE3fIsZjzgldTTBJP2Rhmi4Hj0XRQi65NUUCa7b26GUuR//Pcw/YXK3Kw/RzdOi3Aw66HtYAYezaRDLJa5461i+L9a7fUlf6M5+QKayPFtp0KxQY8zox75b0Cfip8Hk9jAeZWxkQhz2d3xG+qlt3LHgqBptUhB22Osm7TCQyU5VZ/xozX/wdk5sEnTBVtryssab7T8Ts1l3yQDnhrEtTldRrq0gAVKv2bdCXHNqNPz7ib1pfcx8UG2T0DdGaOsbpWpKYHGTOMgaQeqDO14oT7IrR08=;
 5:vvA3HxAsj2Au4HaG13RNDeaWL6PCClvjsWIzh90BfOnN3EXCH9zA5Fsaflur6Ab8vL71fMo0DobrZHTbtHpshNh3SfTE5jg3L5FQigLNttogYlqjrAD+zRZBLXzWL5iSbOuMOr3OOqhKaDfRT61FdWy8eHSzlCwNppIOja3mu/M=;
 24:K5DXX3DRxAASPqGwI1iZbJX3soarYDIPoos24fMMQ87wWA3YOGqKe8yLEoASHP4xwxyX8q/oKINlC9w9gaB2CxGnYjcc0FdZmY83xMZqhQk=;
 7:oJjHpbyxCaiP+7B+Gj+L4ghgIPiWmwHL0viNe1m5/Ppnuu40UMMe6GGBpe0B340JdAhMNSd64ANamH5RmFx/bn80NJusT6mEwjgJGbbFbLelTvs1ET7CrdTjaVQxPONELm9o5ckvbjGd7YD447evNGt0lqvmBAIGM+fiKDQsLtIsTidjRJ+9XnAnkqB5FpdHoTEZ2JQDOMMazEUUrOByq7lb5Af8lxZfweWRFpVgKiqBxFwHamXYIJTVDPzh7Ae2
SpamDiagnosticOutput: 1:99
SpamDiagnosticMetadata: NSPM
X-OriginatorOrg: caviumnetworks.com
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Dec 2017 13:23:01.2934 (UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: 00c527a4-9e27-487e-2698-08d53b1a25c3
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 711e4ccf-2e9b-4bcf-a551-4094005b6194
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY4PR07MB3461
Subject: [dpdk-dev] [PATCH v7 2/3] eal: add u64 bit variant for reciprocal
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <http://dpdk.org/ml/options/dev>,
 <mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <http://dpdk.org/ml/listinfo/dev>,
 <mailto:dev-request@dpdk.org?subject=subscribe>
X-List-Received-Date: Mon, 04 Dec 2017 13:23:05 -0000

Currently, rte_reciprocal only supports unsigned 32bit divisors. This
commit adds support for unsigned 64bit divisors.

Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
---
 lib/librte_eal/common/include/rte_reciprocal.h | 46 +++++++++++++
 lib/librte_eal/common/rte_reciprocal.c         | 89 ++++++++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map             |  1 +
 3 files changed, 136 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_reciprocal.h b/lib/librte_eal/common/include/rte_reciprocal.h
index 5e21f096f..c583da189 100644
--- a/lib/librte_eal/common/include/rte_reciprocal.h
+++ b/lib/librte_eal/common/include/rte_reciprocal.h
@@ -29,6 +29,11 @@ struct rte_reciprocal {
 	uint8_t sh1, sh2;
 };
 
+struct rte_reciprocal_u64 {
+	uint64_t m;
+	uint8_t sh1, sh2;
+};
+
 static inline uint32_t rte_reciprocal_divide(uint32_t a, struct rte_reciprocal R)
 {
 	uint32_t t = (uint32_t)(((uint64_t)a * R.m) >> 32);
@@ -36,6 +41,47 @@ static inline uint32_t rte_reciprocal_divide(uint32_t a, struct rte_reciprocal R
 	return (t + ((a - t) >> R.sh1)) >> R.sh2;
 }
 
+static __rte_always_inline uint64_t
+mullhi_u64(uint64_t x, uint64_t y)
+{
+#ifdef __SIZEOF_INT128__
+	__uint128_t xl = x;
+	__uint128_t rl = xl * y;
+
+	return (rl >> 64);
+#else
+	uint64_t u0, u1, v0, v1, k, t;
+	uint64_t w1, w2;
+	uint64_t whi;
+
+	u1 = x >> 32; u0 = x & 0xFFFFFFFF;
+	v1 = y >> 32; v0 = y & 0xFFFFFFFF;
+
+	t = u0*v0;
+	k = t >> 32;
+
+	t = u1*v0 + k;
+	w1 = t & 0xFFFFFFFF;
+	w2 = t >> 32;
+
+	t = u0*v1 + w1;
+	k = t >> 32;
+
+	whi = u1*v1 + w2 + k;
+
+	return whi;
+#endif
+}
+
+static __rte_always_inline uint64_t
+rte_reciprocal_divide_u64(uint64_t a, struct rte_reciprocal_u64 *R)
+{
+	uint64_t t = mullhi_u64(a, R->m);
+
+	return (t + ((a - t) >> R->sh1)) >> R->sh2;
+}
+
 struct rte_reciprocal rte_reciprocal_value(uint32_t d);
+struct rte_reciprocal_u64 rte_reciprocal_value_u64(uint64_t d);
 
 #endif /* _RTE_RECIPROCAL_H_ */
diff --git a/lib/librte_eal/common/rte_reciprocal.c b/lib/librte_eal/common/rte_reciprocal.c
index 652f0237a..8d1fb7bff 100644
--- a/lib/librte_eal/common/rte_reciprocal.c
+++ b/lib/librte_eal/common/rte_reciprocal.c
@@ -70,3 +70,92 @@ struct rte_reciprocal rte_reciprocal_value(uint32_t d)
 
 	return R;
 }
+
+/*
+ * Code taken from Hacker's Delight:
+ * http://www.hackersdelight.org/hdcodetxt/divlu.c.txt
+ * License permits inclusion here per:
+ * http://www.hackersdelight.org/permissions.htm
+ */
+static uint64_t
+divide_128_div_64_to_64(uint64_t u1, uint64_t u0, uint64_t v, uint64_t *r)
+{
+	const uint64_t b = (1ULL << 32); /* Number base (16 bits). */
+	uint64_t un1, un0,           /* Norm. dividend LSD's. */
+		 vn1, vn0,           /* Norm. divisor digits. */
+		 q1, q0,             /* Quotient digits. */
+		 un64, un21, un10,   /* Dividend digit pairs. */
+		 rhat;               /* A remainder. */
+	int s;                       /* Shift amount for norm. */
+
+	/* If overflow, set rem. to an impossible value. */
+	if (u1 >= v) {
+		if (r != NULL)
+			*r = (uint64_t) -1;
+		return (uint64_t) -1;
+	}
+
+	/* Count leading zeros. */
+	s = __builtin_clzll(v);
+	if (s > 0) {
+		v = v << s;
+		un64 = (u1 << s) | ((u0 >> (64 - s)) & (-s >> 31));
+		un10 = u0 << s;
+	} else {
+
+		un64 = u1 | u0;
+		un10 = u0;
+	}
+
+	vn1 = v >> 32;
+	vn0 = v & 0xFFFFFFFF;
+
+	un1 = un10 >> 32;
+	un0 = un10 & 0xFFFFFFFF;
+
+	q1 = un64/vn1;
+	rhat = un64 - q1*vn1;
+again1:
+	if (q1 >= b || q1*vn0 > b*rhat + un1) {
+		q1 = q1 - 1;
+		rhat = rhat + vn1;
+		if (rhat < b)
+			goto again1;
+	}
+
+	un21 = un64*b + un1 - q1*v;
+
+	q0 = un21/vn1;
+	rhat = un21 - q0*vn1;
+again2:
+	if (q0 >= b || q0*vn0 > b*rhat + un0) {
+		q0 = q0 - 1;
+		rhat = rhat + vn1;
+		if (rhat < b)
+			goto again2;
+	}
+
+	if (r != NULL)
+		*r = (un21*b + un0 - q0*v) >> s;
+	return q1*b + q0;
+}
+
+struct rte_reciprocal_u64
+rte_reciprocal_value_u64(uint64_t d)
+{
+	struct rte_reciprocal_u64 R;
+	uint64_t m;
+	int l;
+
+	l = 63 - __builtin_clzll(d);
+
+	m = divide_128_div_64_to_64((1ULL << l), 0, d, NULL) << 1;
+	m = (1ULL << l) - d ? m + 2 : 1;
+	R.m = m;
+
+	R.sh1 = l > 1 ? 1 : l;
+	R.sh2 = (l > 0) ? l : 0;
+	R.sh2 -= R.sh2 && (m == 1) ? 1 : 0;
+
+	return R;
+}
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index d8b968c5c..ad3ce42ff 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -204,6 +204,7 @@ DPDK_18.02 {
 	global:
 
 	rte_reciprocal_value;
+	rte_reciprocal_value_u64;
 
 }  DPDK_17.11;
 
-- 
2.14.1