From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pa0-f46.google.com (mail-pa0-f46.google.com [209.85.220.46]) by dpdk.org (Postfix) with ESMTP id 992788D39 for ; Sun, 29 Nov 2015 19:46:46 +0100 (CET) Received: by pacej9 with SMTP id ej9so160649866pac.2 for ; Sun, 29 Nov 2015 10:46:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=networkplumber-org.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; bh=eULW56DxmEVF5w6I47njzmT+SMUJYw+W8tivaNsaIrs=; b=XRr6bSGUJbgwXlmPmu+wq/dsNLxemW8pmiAvVQToaJ4R4O//Y0CrNKx4xuQnvWU4gp KxnTp7ma7Z1gGeLNpQmE1YzyabY1SGKBRsXtIX5mHrvu/udxNs7pki4DKlu4ICrs4NWy NFgWTIhBgIJBM90ACANjAaqJgVyvAAAlXqiWTYSmxCMzn5NdI/kk944UZrwJhVGCFQ0I zziMNg/oWdlSvtg0dIqOmODaYZb45BTDqaYQ4AAuwUEw0/wQ0fQPqr4bvlLAHhAQDOlS C/9am7s6m/3wpCqXDO3V/aybfPUN0tphtgxMoiy3VuHyPy3GTDXI10Cnob8UDwN/hF9w 3HEg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-type:content-transfer-encoding; bh=eULW56DxmEVF5w6I47njzmT+SMUJYw+W8tivaNsaIrs=; b=AGRpDoTPInPmozj3f4BggylaB0GcAhujluEa2YC5pKOVoFNQL1D+Fl1r7KWlIg6YSZ 5Y5yXWrOJF6Zm64rVkTCY7WLeNoUk2yM2vMINepaic1ofP/yatAol/BAFtuxkDqhhNMZ KbuGJ6gdjvSVZz6y0daHqOCT6FCe3ibHyFC0pZcOgovgFo7vAnZifX95eHEEJMrhDwan tyhPa79xizO/RH0uI+9lIlr086rchcH+erg6HeRq+uBgDdhh/IBw3ucNZkPETsxFDRux uPXt3dLd/fN9HkFODnrpMOCMyAuXFzo6PSlr5dN41mBf7EaqIvU2rwUaRGjTmuNv0t/9 Koxg== X-Gm-Message-State: ALoCoQlhYw4q+GthcH0ChXr5lQ+aUQV7rv9LR464kzrGHFi2LZY50II9nEnWrMx8rfx2TxnwdA2y X-Received: by 10.66.155.226 with SMTP id vz2mr85392184pab.18.1448822806026; Sun, 29 Nov 2015 10:46:46 -0800 (PST) Received: from xeon-e3.home.lan (static-50-53-82-155.bvtn.or.frontiernet.net. [50.53.82.155]) by smtp.gmail.com with ESMTPSA id qn5sm46905832pac.41.2015.11.29.10.46.44 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sun, 29 Nov 2015 10:46:45 -0800 (PST) From: Stephen Hemminger To: cristian.dumitrescu@intel.com Date: Sun, 29 Nov 2015 10:46:48 -0800 Message-Id: <1448822809-8350-3-git-send-email-stephen@networkplumber.org> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1448822809-8350-1-git-send-email-stephen@networkplumber.org> References: <1448822809-8350-1-git-send-email-stephen@networkplumber.org> MIME-Version: 1.0 Content-Type: text/plain; charset=yes Content-Transfer-Encoding: 8bit Cc: dev@dpdk.org Subject: [dpdk-dev] [PATCH 2/3] rte_sched: introduce reciprocal divide X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 29 Nov 2015 18:46:47 -0000 This adds (with permission of the original author) reciprocal divide based on algorithm in Linux. Signed-off-by: Stephen Hemminger Signed-off-by: Hannes Frederic Sowa --- lib/librte_sched/Makefile | 6 ++-- lib/librte_sched/rte_reciprocal.c | 72 +++++++++++++++++++++++++++++++++++++++ lib/librte_sched/rte_reciprocal.h | 39 +++++++++++++++++++++ 3 files changed, 115 insertions(+), 2 deletions(-) create mode 100644 lib/librte_sched/rte_reciprocal.c create mode 100644 lib/librte_sched/rte_reciprocal.h diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile index b1cb285..e0a2c6d 100644 --- a/lib/librte_sched/Makefile +++ b/lib/librte_sched/Makefile @@ -48,10 +48,12 @@ LIBABIVER := 1 # # all source are stored in SRCS-y # -SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c rte_approx.c +SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c rte_approx.c \ + rte_reciprocal.c # install includes -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_bitmap.h \ + rte_sched_common.h rte_red.h rte_approx.h rte_reciprocal.h # this lib depends upon: DEPDIRS-$(CONFIG_RTE_LIBRTE_SCHED) += lib/librte_mempool lib/librte_mbuf diff --git a/lib/librte_sched/rte_reciprocal.c b/lib/librte_sched/rte_reciprocal.c new file mode 100644 index 0000000..652f023 --- /dev/null +++ b/lib/librte_sched/rte_reciprocal.c @@ -0,0 +1,72 @@ +/*- + * BSD LICENSE + * + * Copyright(c) Hannes Frederic Sowa + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include + +#include + +#include "rte_reciprocal.h" + +/* find largest set bit. + * portable and slow but does not matter for this usage. + */ +static inline int fls(uint32_t x) +{ + int b; + + for (b = 31; b >= 0; --b) { + if (x & (1u << b)) + return b + 1; + } + + return 0; +} + +struct rte_reciprocal rte_reciprocal_value(uint32_t d) +{ + struct rte_reciprocal R; + uint64_t m; + int l; + + l = fls(d - 1); + m = ((1ULL << 32) * ((1ULL << l) - d)); + m /= d; + + ++m; + R.m = m; + R.sh1 = RTE_MIN(l, 1); + R.sh2 = RTE_MAX(l - 1, 0); + + return R; +} diff --git a/lib/librte_sched/rte_reciprocal.h b/lib/librte_sched/rte_reciprocal.h new file mode 100644 index 0000000..abd1525 --- /dev/null +++ b/lib/librte_sched/rte_reciprocal.h @@ -0,0 +1,39 @@ +/* + * Reciprocal divide + * + * Used with permission from original authors + * Hannes Frederic Sowa and Daniel Borkmann + * + * This algorithm is based on the paper "Division by Invariant + * Integers Using Multiplication" by Torbjörn Granlund and Peter + * L. Montgomery. + * + * The assembler implementation from Agner Fog, which this code is + * based on, can be found here: + * http://www.agner.org/optimize/asmlib.zip + * + * This optimization for A/B is helpful if the divisor B is mostly + * runtime invariant. The reciprocal of B is calculated in the + * slow-path with reciprocal_value(). The fast-path can then just use + * a much faster multiplication operation with a variable dividend A + * to calculate the division A/B. + */ + +#ifndef _RTE_RECIPROCAL_H_ +#define _RTE_RECIPROCAL_H_ + +struct rte_reciprocal { + uint32_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); + + return (t + ((a - t) >> R.sh1)) >> R.sh2; +} + +struct rte_reciprocal rte_reciprocal_value(uint32_t d); + +#endif /* _RTE_RECIPROCAL_H_ */ -- 2.1.4