From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 ; 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 To: cristian.dumitrescu@intel.com, stephen@networkplumber.org, ktraynor@redhat.com Cc: dev@dpdk.org, Pavan Nikhilesh 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: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 --- 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