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