From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from NAM01-SN1-obe.outbound.protection.outlook.com (mail-sn1nam01on0073.outbound.protection.outlook.com [104.47.32.73]) by dpdk.org (Postfix) with ESMTP id 4969C1B220 for ; Fri, 26 Jan 2018 06:05:27 +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=gmpIO9aAGcsUfPsf4+0rGXYnm5Vr4A6fUKShsmHd1l4=; b=IZC/Bz9Qrv55HzWcuAqhRvFnqS8bJMkMEVEImixQRw+msuP/Trt0Jan1J0riGt5vHN+Unf5vNYuvNb4CE6iWoXdpZ7YMSZa45V+GNZmQtvmXP815orVmGTvp+35CuWBYU39bTnjxD21k08IK94NIE3tLTFueTgUojzfRV22sRDA= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Pavan.Bhagavatula@cavium.com; Received: from localhost.localdomain (111.93.218.67) by MWHPR07MB3471.namprd07.prod.outlook.com (10.164.192.22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.444.14; Fri, 26 Jan 2018 05:05:23 +0000 From: Pavan Nikhilesh To: thomas@monjalon.net, cristian.dumitrescu@intel.com, stephen@networkplumber.org Cc: dev@dpdk.org, Pavan Nikhilesh Date: Fri, 26 Jan 2018 10:34:50 +0530 Message-Id: <20180126050451.5953-2-pbhagavatula@caviumnetworks.com> X-Mailer: git-send-email 2.14.1 In-Reply-To: <20180126050451.5953-1-pbhagavatula@caviumnetworks.com> References: <1504032378-5483-1-git-send-email-pbhagavatula@caviumnetworks.com> <20180126050451.5953-1-pbhagavatula@caviumnetworks.com> MIME-Version: 1.0 Content-Type: text/plain X-Originating-IP: [111.93.218.67] X-ClientProxiedBy: BM1PR0101CA0012.INDPRD01.PROD.OUTLOOK.COM (10.174.220.22) To MWHPR07MB3471.namprd07.prod.outlook.com (10.164.192.22) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: e9b17029-9454-4345-e1a7-08d5647a6939 X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(4534165)(4627221)(201703031133081)(201702281549075)(5600026)(4604075)(2017052603307)(7153060)(7193020); SRVR:MWHPR07MB3471; X-Microsoft-Exchange-Diagnostics: 1; MWHPR07MB3471; 3:JHf8Quzl6wW4EVBnZWf6u8WeVgBNcbR9YBP6YLjdSnNv7RTw34AtTcSfQaUwL+irt5FkVq1ycgMVLJUZse7VLQ2kK3Kz1Y2NzfNzRtks7Tx01H/IoH5IR8FAxbRugYDx3Jn8QuqcRA7zbXdFbJDkCtJx0Gqes1k9OrAM/mME54JIlBllhh2KicJw0lF4dA79prnxaF7jtpY0tY7tg9/wySm5msWCuTmiTRemPn16izkNg7T/zo53h5pZbHFfxv/9; 25:NTNnNDFJd2CubwavJtCDa4Lj+VvZUp6gVxP1iO/bIkTIZ8zZvy1xwks0tQVjeGwMB5j83dHHdZA0mUdViGsZw2UJZcg6NzJVVX/AAw6VlExcuad5rt4lTBsxiPCnvuiDVArtcGmNx9VnY5ZGODMVpHPNf6KS9L7QuRV1wSDr9V1pswZliE6jnjCYbUW7H7AckxEccyI5Fs84ej1szYih4KDxzozp0HoFg7cgsMYSY69GHqjLR1ToD7fU6I8cbLsQNOUR04re2zenoy/V15raDgfx8JMVfM0cdpl+mtA0u8q+kzWsfdVUg5OvWh5tFvkDbXT0owNKGxXMgxlvvj3uzQ==; 31:rH0zAdZih1MlQQ9IJpUokDvTZcSpPqEIexJzATox1CH4II05x7N7iMKemLkz81x0PGoRtj3aD9OopIqZJwTKz9KWIgNEQ99JDgTYHjT0RGFY3kk+YOu+sQrid0/kuS2DwtcEOFt9Z+VHrFzhnXLEnD+rH3kSXquP1xc65e9eBHiGjkwX5pM+mjBYz+wlyjDxXXIw/JElvnIkddeSabMZK8Z/SpsExxL3MXleEWcDCds= X-MS-TrafficTypeDiagnostic: MWHPR07MB3471: X-Microsoft-Exchange-Diagnostics: 1; MWHPR07MB3471; 20:hhpjQVWYpOQfpYYExCkR7+iMO9V02OhSXpt+9ioTig1/ZD6Gmqrys2RqR0Ia4K3RoJnAncBCJGH5aGkelhSu5iJWk99NGXhchDjD9+PmqC1obJjR9hwpdEl2hAJd/rzcfh9KdnhNd6iA9rwohxUvXdtdB15XzoHDyy6umWi615R/FjoPWuqDQXMsbPdMKsrBBYLAGPNj0LR5PPSpNe/O7Aah1ypys/I4kP75Gu+aVNEfzUVgyibzoIv5TmT4Us1drlZfMDBVkA6UAxud/J4MebbFd0igN7nFTXSVMznIo9/7vak+V+X4JlFuxJlzQ8CPwCWSdd8P1OyVEBWXRq9dndWDxoJ3k5iA0aVpfoSY1BzxPudCWpVr/yqfKC2sVEYuY2gAhn8ZoKbeL4FWMQG4kwrqP/EgtwnYDyWH7CJOZVn6x4k4P/i1Xw5xasaTSw5RM9LR1jEf3e7jUiT2Nwm4Pq2HL4y8yMNcKyoo2uzG6PdXHsh9swkb15leYMeCuG8Otvd1lUzJsbi9D9I9Iw7b1lOTxIsmAjaqniuavQWwocACiFl9dbXyOsM32608NpXzkwhi2JuhfjQ4sWQ9SynO/luZRAnbUc0JhUPYmDHBRLc=; 4:UtNpPDExWVMWUEJHVBmbE8zEM0FBqSXxcJrfMMYxz1c+duzlofqbRfU2e3KL4K9Cc1e+fUC1zIWVP68i205PrJmSQEokuTX10zXXTGpZ4BkJaQ+AVqYIn/3aJI9x6940H8zxRIrra+wttlvi6Hag7kKGCzPADA6rZAhzbYMhidk5YYR1nBxd61fSoYknEngwi33YNxbESIme2k4kb1+TIPv6+TaNMs0kBUNx3m2WACwoQ10cSpXR0/Gg2hoaS/RWm7V/KUj2AACEgyn8QAEFHA== X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(6040501)(2401047)(5005006)(8121501046)(10201501046)(93006095)(3231023)(2400081)(944501161)(3002001)(6041288)(20161123562045)(20161123558120)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(6072148)(201708071742011); SRVR:MWHPR07MB3471; BCL:0; PCL:0; RULEID:; SRVR:MWHPR07MB3471; X-Forefront-PRVS: 05641FD966 X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(6069001)(39850400004)(39380400002)(396003)(346002)(376002)(366004)(199004)(189003)(8676002)(5660300001)(8936002)(36756003)(50466002)(1076002)(26005)(6116002)(2906002)(81156014)(52116002)(42882006)(2950100002)(97736004)(16526019)(6666003)(68736007)(50226002)(81166006)(51416003)(6306002)(76176011)(59450400001)(5009440100003)(186003)(105586002)(6512007)(3846002)(25786009)(6486002)(106356001)(16586007)(316002)(66066001)(53936002)(48376002)(386003)(7736002)(47776003)(966005)(72206003)(305945005)(6506007)(478600001)(107886003)(4326008)(42262002)(562404015); DIR:OUT; SFP:1101; SCL:1; SRVR:MWHPR07MB3471; H:localhost.localdomain; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX: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; MWHPR07MB3471; 23:VRqMVv/9Lb6gC4lUFfFP0fKRCuE+Qx0PRnhHJsLwe?= =?us-ascii?Q?3x+oSMUP9d548jB/ko6sgh5lzXZybJlSk3JcxZBzX2AM376QgVgqnTLBueLu?= =?us-ascii?Q?Eboj27cvhtaaAr7VDhEKwWlGjn9TaLWQi95NAySQGjVj+0WebQI4++S2pnxU?= =?us-ascii?Q?vYYMs6adWL1Q3aCr/DhLrrwgEKOfg2/NofJ7s3h4Si6XEwZjcyxJiO4qX1nA?= =?us-ascii?Q?4od+Cj2mOFsR4gM9tRjUWDyihBVHPH+4I5ZKuNLrNBlsx4oI+d6pmHc0aRCO?= =?us-ascii?Q?Mkx+j0y//skbbeTzGmfkBs8V73hG/+TbH4EoYeLRlHyJMF2yx86J4n2o7ctZ?= =?us-ascii?Q?e5yLs73HB4Gj3MSOKh6LQRNTlB3vt3k8ktfkgQ6F5x0XFhWx6ncqNxrV+7d4?= =?us-ascii?Q?hSy0rVro8ywV2WuezprlH82Y7POZgGtaaIHYC1GLaKdMc4d+cG4XKDzF+QZo?= =?us-ascii?Q?RGjhsYIDHPmoJn1orxBimOjbOWZ3NDwUk7UFLRpLx8ohGVjhLgOdB5kMrYJZ?= =?us-ascii?Q?yd6gOJUBfnD8hr04VYJmH560z4sAHSCTzZm1YQ4C+1pXA+7X/B53o9/h7kDt?= =?us-ascii?Q?YyqVNhWQ9Ixv4KD6EXlzZsGunyv0jtgOmHcRkaGliwkLsObTyPnwfaEnancJ?= =?us-ascii?Q?uaK/3qKRWbf3V52RbV1o4gDEiHCdH6+YSFClvkMp2IMaxcd3TeCVVUyfkMfL?= =?us-ascii?Q?YybKk4nRQpimDrXThlRHATgTY4XNLoQ4ns/POKzSJMj1tpXomoRuVOTvJPtJ?= =?us-ascii?Q?/o33i1dCtWGHVEx0R2pYjhUm34VrhqerOe4jjrmGrGHTGBpw1TWOpK3MciO4?= =?us-ascii?Q?z7iJq7DVd771D3cTCOwjMTp762gu5KvlszfIZq7WQudiZrxme718ll7Seu6c?= =?us-ascii?Q?DCM3FGkujJdeKvWhboHwQ4U3luN93s0VHLBzEx4DZmMjLfIsPF1Dx/TQcX8g?= =?us-ascii?Q?h54Mp1OjkeddhqPpt0FpsG4VvXN1YvtNmqOKsCkDPeLuriC05Pt8QpYCWAf9?= =?us-ascii?Q?ELrRfyB0g6Pegu4VgDBH/AR7KQpXx+DfEqd5SfMO0oqg/Oath4fhiyP/s43I?= =?us-ascii?Q?nxrKl3GXh/0qjutKbbCIKXbWodEP4suukSDMnSiXiLz433oI0Mv9Y/0uHlUr?= =?us-ascii?Q?Tt4R21jM2AowdyAqghKCJAJomdnHnioZ9zqcHB0/kkBDH+AL5GFCSxYSGeZr?= =?us-ascii?Q?vg9QITvYZQ6pvBeqmbtJtYTJM7ImEJohlnTJ9RNNVzxpj4yy7enVlngbnEl/?= =?us-ascii?Q?Fle4t/6bts60iis9iYPCHK3aq8hS2E7TKiHgWYY87mW59SiJfoHMJkzGldTS?= =?us-ascii?B?dz09?= X-Microsoft-Exchange-Diagnostics: 1; MWHPR07MB3471; 6:aKWW0i4OTfJAYQRbNapci+/b8x3x+TzU32CtndeeTsn2QLIea0bOUVo7spCQj5Qa4WBboea/X2TfeZTbyWCRLAOkNcqmnYoXnaGB8zZg/lG8ETZ6JCYuI908SfdHwy1uceCoVV3xbVNvDKge7s5jY3z08mVPEpA0jZecqqYE+wCJtIXBD2ULSYhPln6oE9QEQqpjNjef0T89CH1CUykOvjKb2LfXinu2qcxwFMJgrsjC6uX0mLCj3VChWpunDSTt+4oypkpOxxlMJrXTCmxtX8Ar0wqj14CLJT/uVPaub3jmOqoIHg2F0i2lNDMPCPuAuxvsjBRLUdlEk0v7uwYUvk5VEkbZwcjmOxYScFvEIRM=; 5:VtXIXNJc81Bz39s96Omq1MLbtQLQrcmSzkmBintf6WyDFoBiupB00aYli6VouOavYKjO8csY67aQCBKb9ZoC+32pLMDN7nGZtuLa/5P+L054EdI0YfbJGqR0NgEBqVF3uNf0Mla24PGf1nyUE53+owo8MHgYy6MLoHegkTvp+CQ=; 24:owTWgkxP4ItotPk9wKaStFb5n0+ODf3UdiRUO2OgcBoM5BBAGD3OtcrzJWrmTp0iNdGubz6opkixmfM4xTnFdaLz+PtgnM1/bUdBvoKo8VM=; 7:iN5IMlC31crIw2G/WatDohYcH+8mTc0HsaT/D5rwvcx6t+QcJ9I6tPI56KG+x7FGPKZKA7NeZnqs95JFsNWJD9pukVgQrWx5NnvwsGEhs8/qYNpC96N2KW3n2MhTtMnzlCYnXSBc9X7OffNdC004njIzW6nQPxsQ+mj4qRVyd50LB8HND83pxehD+6QDJm3x4UQ9UUotBonTlvjG074yvtjYa71Aa3F5krdsLDQyno/AqElKgjfIjKTenujz6IhQ SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: caviumnetworks.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 26 Jan 2018 05:05:23.6200 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: e9b17029-9454-4345-e1a7-08d5647a6939 X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 711e4ccf-2e9b-4bcf-a551-4094005b6194 X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR07MB3471 Subject: [dpdk-dev] [PATCH v8 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: Fri, 26 Jan 2018 05:05:27 -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 | 49 ++++++++++++++ lib/librte_eal/common/rte_reciprocal.c | 92 ++++++++++++++++++++++++++ lib/librte_eal/rte_eal_version.map | 4 +- 3 files changed, 144 insertions(+), 1 deletion(-) diff --git a/lib/librte_eal/common/include/rte_reciprocal.h b/lib/librte_eal/common/include/rte_reciprocal.h index 5e21f096f..3492c73ba 100644 --- a/lib/librte_eal/common/include/rte_reciprocal.h +++ b/lib/librte_eal/common/include/rte_reciprocal.h @@ -1,3 +1,6 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2017 Cavium, Inc + */ /* * Reciprocal divide * @@ -29,6 +32,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 +44,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..d81b11db6 100644 --- a/lib/librte_eal/common/rte_reciprocal.c +++ b/lib/librte_eal/common/rte_reciprocal.c @@ -1,3 +1,6 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2017 Cavium, Inc + */ /*- * BSD LICENSE * @@ -70,3 +73,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 730966407..4355322e9 100644 --- a/lib/librte_eal/rte_eal_version.map +++ b/lib/librte_eal/rte_eal_version.map @@ -207,7 +207,9 @@ DPDK_18.02 { rte_hypervisor_get_name; rte_vfio_clear_group; rte_reciprocal_value; -} DPDK_17.11; + rte_reciprocal_value_u64; + +} DPDK_17.11; EXPERIMENTAL { global: -- 2.14.1