From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0b-0016f401.pphosted.com (mx0b-0016f401.pphosted.com [67.231.156.173]) by dpdk.org (Postfix) with ESMTP id F3EFC3257; Sun, 14 Apr 2019 07:23:49 +0200 (CEST) Received: from pps.filterd (m0045851.ppops.net [127.0.0.1]) by mx0b-0016f401.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x3E5F4gp029244; Sat, 13 Apr 2019 22:23:48 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=marvell.com; h=from : to : cc : subject : date : message-id : mime-version : content-transfer-encoding : content-type; s=pfpt0818; bh=7RcGWCUXws44cDpEnKzQuFaTR+1xFaEujfdnuDMOGpY=; b=vfm0hieUl/G9iRnLQ8rHeditukOt6HRIzIpp1QnZ9l8EsCUj9+2+fuGG4FmFoyZynat5 k+fiP/HqTmRdKnWrZMozCdfmAahns9Yoyta/cDqTqH43CpMfgVEb6W7uDaGPCBggRtJ0 awd2zxySv5eRPTpFEkM8HG6GYgqVqG3QuWl2cloie19UFpQcjtgoWWgjJa5fz+kMzcDC 1v+SCJKF1/nvSMeCTT3bzZ7hGKZd4A2Y7JBVk26Og4AGO3cZDWNX4b4fZJvwcDpWTQNX E2MPy98K8yNjeLS0gn8XE8fNiEfnkAlc9TmF0dyQCd46ao0uyZVe2SPZV2tXJbPPLLQ6 2w== Received: from sc-exch02.marvell.com ([199.233.58.182]) by mx0b-0016f401.pphosted.com with ESMTP id 2ruf9jsyr7-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Sat, 13 Apr 2019 22:23:48 -0700 Received: from SC-EXCH03.marvell.com (10.93.176.83) by SC-EXCH02.marvell.com (10.93.176.82) with Microsoft SMTP Server (TLS) id 15.0.1367.3; Sat, 13 Apr 2019 22:23:47 -0700 Received: from maili.marvell.com (10.93.176.43) by SC-EXCH03.marvell.com (10.93.176.83) with Microsoft SMTP Server id 15.0.1367.3 via Frontend Transport; Sat, 13 Apr 2019 22:23:47 -0700 Received: from BG-LT7430.marvell.com (unknown [10.28.16.100]) by maili.marvell.com (Postfix) with ESMTP id EF7FB3F703F; Sat, 13 Apr 2019 22:23:44 -0700 (PDT) From: To: CC: , Pavan Nikhilesh , , Stefan Kanthak Date: Sun, 14 Apr 2019 10:52:59 +0530 Message-ID: <20190414052325.15984-1-pbhagavatula@marvell.com> X-Mailer: git-send-email 2.21.0 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-04-14_01:, , signatures=0 Subject: [dpdk-dev] [PATCH] eal: fix large multiple calculation in reciprocal division 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: Sun, 14 Apr 2019 05:23:53 -0000 From: Pavan Nikhilesh Fix large multiple calculation in 64 bit reciprocal division. Fixes: 6d45659eacb8 ("eal: add u64-bit variant for reciprocal divide") Cc: stable@dpdk.org Reported-by: Stefan Kanthak Signed-off-by: Pavan Nikhilesh --- lib/librte_eal/common/rte_reciprocal.c | 76 ++++++-------------------- 1 file changed, 16 insertions(+), 60 deletions(-) diff --git a/lib/librte_eal/common/rte_reciprocal.c b/lib/librte_eal/common/rte_reciprocal.c index f017d0c28..920fbcdbe 100644 --- a/lib/librte_eal/common/rte_reciprocal.c +++ b/lib/librte_eal/common/rte_reciprocal.c @@ -60,72 +60,28 @@ struct rte_reciprocal rte_reciprocal_value(uint32_t d) } /* - * Code taken from Hacker's Delight: - * http://www.hackersdelight.org/hdcodetxt/divlu.c.txt + * Code based on from Hacker's Delight: + * http://www.hackersdelight.org/hdcodetxt/divluh.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) +divlluh(uint64_t x, uint64_t y, uint64_t z) { - 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; + int64_t i; + uint64_t t; + + for (i = 1; i <= 64; i++) { + t = x >> 63; + x = (x << 1) | (y >> 63); + y = y << 1; + if ((x | t) >= z) { + x = x - z; + y = y + 1; + } } - if (r != NULL) - *r = (un21*b + un0 - q0*v) >> s; - return q1*b + q0; + return y; } struct rte_reciprocal_u64 @@ -137,7 +93,7 @@ rte_reciprocal_value_u64(uint64_t d) l = 63 - __builtin_clzll(d); - m = divide_128_div_64_to_64((1ULL << l), 0, d, NULL) << 1; + m = divlluh((1ULL << l), 0, d) << 1; m = (1ULL << l) - d ? m + 2 : 1; R.m = m; -- 2.21.0 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id 0DF48A00E6 for ; Sun, 14 Apr 2019 07:23:57 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 55A8544C3; Sun, 14 Apr 2019 07:23:54 +0200 (CEST) Received: from mx0b-0016f401.pphosted.com (mx0b-0016f401.pphosted.com [67.231.156.173]) by dpdk.org (Postfix) with ESMTP id F3EFC3257; Sun, 14 Apr 2019 07:23:49 +0200 (CEST) Received: from pps.filterd (m0045851.ppops.net [127.0.0.1]) by mx0b-0016f401.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x3E5F4gp029244; Sat, 13 Apr 2019 22:23:48 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=marvell.com; h=from : to : cc : subject : date : message-id : mime-version : content-transfer-encoding : content-type; s=pfpt0818; bh=7RcGWCUXws44cDpEnKzQuFaTR+1xFaEujfdnuDMOGpY=; b=vfm0hieUl/G9iRnLQ8rHeditukOt6HRIzIpp1QnZ9l8EsCUj9+2+fuGG4FmFoyZynat5 k+fiP/HqTmRdKnWrZMozCdfmAahns9Yoyta/cDqTqH43CpMfgVEb6W7uDaGPCBggRtJ0 awd2zxySv5eRPTpFEkM8HG6GYgqVqG3QuWl2cloie19UFpQcjtgoWWgjJa5fz+kMzcDC 1v+SCJKF1/nvSMeCTT3bzZ7hGKZd4A2Y7JBVk26Og4AGO3cZDWNX4b4fZJvwcDpWTQNX E2MPy98K8yNjeLS0gn8XE8fNiEfnkAlc9TmF0dyQCd46ao0uyZVe2SPZV2tXJbPPLLQ6 2w== Received: from sc-exch02.marvell.com ([199.233.58.182]) by mx0b-0016f401.pphosted.com with ESMTP id 2ruf9jsyr7-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Sat, 13 Apr 2019 22:23:48 -0700 Received: from SC-EXCH03.marvell.com (10.93.176.83) by SC-EXCH02.marvell.com (10.93.176.82) with Microsoft SMTP Server (TLS) id 15.0.1367.3; Sat, 13 Apr 2019 22:23:47 -0700 Received: from maili.marvell.com (10.93.176.43) by SC-EXCH03.marvell.com (10.93.176.83) with Microsoft SMTP Server id 15.0.1367.3 via Frontend Transport; Sat, 13 Apr 2019 22:23:47 -0700 Received: from BG-LT7430.marvell.com (unknown [10.28.16.100]) by maili.marvell.com (Postfix) with ESMTP id EF7FB3F703F; Sat, 13 Apr 2019 22:23:44 -0700 (PDT) From: To: CC: , Pavan Nikhilesh , , Stefan Kanthak Date: Sun, 14 Apr 2019 10:52:59 +0530 Message-ID: <20190414052325.15984-1-pbhagavatula@marvell.com> X-Mailer: git-send-email 2.21.0 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="UTF-8" X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-04-14_01:, , signatures=0 Subject: [dpdk-dev] [PATCH] eal: fix large multiple calculation in reciprocal division 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Message-ID: <20190414052259.Y31sDVmfQhR6Ff-kzdaPvhzWrY2Kfo_cA2FDLnk1360@z> From: Pavan Nikhilesh Fix large multiple calculation in 64 bit reciprocal division. Fixes: 6d45659eacb8 ("eal: add u64-bit variant for reciprocal divide") Cc: stable@dpdk.org Reported-by: Stefan Kanthak Signed-off-by: Pavan Nikhilesh --- lib/librte_eal/common/rte_reciprocal.c | 76 ++++++-------------------- 1 file changed, 16 insertions(+), 60 deletions(-) diff --git a/lib/librte_eal/common/rte_reciprocal.c b/lib/librte_eal/common/rte_reciprocal.c index f017d0c28..920fbcdbe 100644 --- a/lib/librte_eal/common/rte_reciprocal.c +++ b/lib/librte_eal/common/rte_reciprocal.c @@ -60,72 +60,28 @@ struct rte_reciprocal rte_reciprocal_value(uint32_t d) } /* - * Code taken from Hacker's Delight: - * http://www.hackersdelight.org/hdcodetxt/divlu.c.txt + * Code based on from Hacker's Delight: + * http://www.hackersdelight.org/hdcodetxt/divluh.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) +divlluh(uint64_t x, uint64_t y, uint64_t z) { - 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; + int64_t i; + uint64_t t; + + for (i = 1; i <= 64; i++) { + t = x >> 63; + x = (x << 1) | (y >> 63); + y = y << 1; + if ((x | t) >= z) { + x = x - z; + y = y + 1; + } } - if (r != NULL) - *r = (un21*b + un0 - q0*v) >> s; - return q1*b + q0; + return y; } struct rte_reciprocal_u64 @@ -137,7 +93,7 @@ rte_reciprocal_value_u64(uint64_t d) l = 63 - __builtin_clzll(d); - m = divide_128_div_64_to_64((1ULL << l), 0, d, NULL) << 1; + m = divlluh((1ULL << l), 0, d) << 1; m = (1ULL << l) - d ? m + 2 : 1; R.m = m; -- 2.21.0