[dpdk-dev,v8,2/3] eal: add u64 bit variant for reciprocal
Checks
Commit Message
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 | 49 ++++++++++++++
lib/librte_eal/common/rte_reciprocal.c | 92 ++++++++++++++++++++++++++
lib/librte_eal/rte_eal_version.map | 4 +-
3 files changed, 144 insertions(+), 1 deletion(-)
Comments
Hi Pavan,
I am bit late in checking it. (series is already applied)
Just few legal queries.
> --- 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
you have added Cavium's copyright here.
> +
> +/*
> + * 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
> + */
Did you clarify it Cavium's legal team?
The permissions states that you should not add it to another publication
without written permission. DPDK can be considered a publication.
Did you got written permission?
If not please specify Cavium's legal team opinion or take permission
from author. I believe that it is easy to obtain permission for this code.
>>>>>>
"You are free to use, copy, and distribute any of the code on this web
site, whether modified by you or not. You need not give attribution.
This includes the algorithms (some of which appear in Hacker's Delight),
the Hacker's Assistant, and any code submitted by readers. Submitters
implicitly agree to this.
*The textural material and pictures are copyright by the author, and the
usual copyright rules apply. E.g., you may store the material on your
computer and make hard or soft copies for your own use. However, you may
not incorporate this material into another publication without written
permission from the author (which the author may give by email).*
The author has taken care in the preparation of this material, but makes
no expressed or implied warranty of any kind and assumes no
responsibility for errors or omissions. No liability is assumed for
incidental or consequential damages in connection with or arising out of
the use of the information or programs contained herein."
>>>>>>>>>
regards,
Hemant
Hi Hemant,
On Mon, Jan 29, 2018 at 12:12:55PM +0530, Hemant Agrawal wrote:
> Hi Pavan,
> I am bit late in checking it. (series is already applied)
>
> Just few legal queries.
>
> > --- 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
>
> you have added Cavium's copyright here.
>
> > +
> > +/*
> > + * 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
> > + */
>
> Did you clarify it Cavium's legal team?
>
> The permissions states that you should not add it to another publication
> without written permission. DPDK can be considered a publication.
> Did you got written permission?
The link specifically states that only the "The textural material and pictures
are copyright by the author" and "You are free to use, copy, and distribute any
of the code on this web site, whether modified by you or not".
The textural material in this case mean any text/pictures taken from the
Hacker's Delight book.
The linux kernel also uses similar code as seen at
https://github.com/torvalds/linux/blob/master/lib/div64.c.
Let me know if any further clarification are needed.
Regards,
Pavan.
>
> If not please specify Cavium's legal team opinion or take permission from
> author. I believe that it is easy to obtain permission for this code.
>
> >>>>>>
> "You are free to use, copy, and distribute any of the code on this web site,
> whether modified by you or not. You need not give attribution. This includes
> the algorithms (some of which appear in Hacker's Delight), the Hacker's
> Assistant, and any code submitted by readers. Submitters implicitly agree to
> this.
>
> *The textural material and pictures are copyright by the author, and the
> usual copyright rules apply. E.g., you may store the material on your
> computer and make hard or soft copies for your own use. However, you may not
> incorporate this material into another publication without written
> permission from the author (which the author may give by email).*
>
> The author has taken care in the preparation of this material, but makes no
> expressed or implied warranty of any kind and assumes no responsibility for
> errors or omissions. No liability is assumed for incidental or consequential
> damages in connection with or arising out of the use of the information or
> programs contained herein."
> >>>>>>>>>
> regards,
> Hemant
>
On 1/29/2018 1:24 PM, Pavan Nikhilesh wrote:
> Hi Hemant,
>
> On Mon, Jan 29, 2018 at 12:12:55PM +0530, Hemant Agrawal wrote:
>> Hi Pavan,
>> I am bit late in checking it. (series is already applied)
>>
>> Just few legal queries.
>>
>>> --- 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
>>
>> you have added Cavium's copyright here.
>>
>>> +
>>> +/*
>>> + * 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
>>> + */
>>
>> Did you clarify it Cavium's legal team?
>>
>> The permissions states that you should not add it to another publication
>> without written permission. DPDK can be considered a publication.
>> Did you got written permission?
>
> The link specifically states that only the "The textural material and pictures
> are copyright by the author" and "You are free to use, copy, and distribute any
> of the code on this web site, whether modified by you or not".
> The textural material in this case mean any text/pictures taken from the
> Hacker's Delight book.
>
> The linux kernel also uses similar code as seen at
> https://github.com/torvalds/linux/blob/master/lib/div64.c.
>
> Let me know if any further clarification are needed.
Thanks. It is clear now.
>
> Regards,
> Pavan.
>
>>
>> If not please specify Cavium's legal team opinion or take permission from
>> author. I believe that it is easy to obtain permission for this code.
>>
>>>>>>>>
>> "You are free to use, copy, and distribute any of the code on this web site,
>> whether modified by you or not. You need not give attribution. This includes
>> the algorithms (some of which appear in Hacker's Delight), the Hacker's
>> Assistant, and any code submitted by readers. Submitters implicitly agree to
>> this.
>>
>> *The textural material and pictures are copyright by the author, and the
>> usual copyright rules apply. E.g., you may store the material on your
>> computer and make hard or soft copies for your own use. However, you may not
>> incorporate this material into another publication without written
>> permission from the author (which the author may give by email).*
>>
>> The author has taken care in the preparation of this material, but makes no
>> expressed or implied warranty of any kind and assumes no responsibility for
>> errors or omissions. No liability is assumed for incidental or consequential
>> damages in connection with or arising out of the use of the information or
>> programs contained herein."
>>>>>>>>>>>
>> regards,
>> Hemant
>>
>
On 1/26/2018 5:04 AM, Pavan Nikhilesh wrote:
> Currently, rte_reciprocal only supports unsigned 32bit divisors. This
> commit adds support for unsigned 64bit divisors.
>
> Signed-off-by: Pavan Nikhilesh <pbhagavatula@caviumnetworks.com>
<...>
> +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));
Hi Pavan,
This is causing a cppcheck warning [1]. s is `int` and we know here s > 0,
so `-s >> 31` should be 0xffffffff right, what is the point of this operation
instead of using hardcoded value?
[1]
(error) Shifting signed 32-bit value by 31 bits is undefined behaviour
@@ -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_ */
@@ -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;
+}
@@ -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: