[dpdk-dev] [BUG] Maintainer for lib/librte_eal/common/rte_reciprocal.c?

[Stefan Kanthak]

Hi @ll,

<https://git.dpdk.org/dpdk/plain/MAINTAINERS> does NOT list
a maintainer for lib/librte_eal/common/rte_reciprocal.c

Whoever it is should take a close look at
<https://skanthak.homepage.t-online.de/division.html>,
then fix the most obvious bug plus the many deficiencies of
divide_128_div_64_to_64().

regards
Stefan Kanthak

Re: [dpdk-dev] [BUG] Maintainer forlib/librte_eal/common/rte_reciprocal.c?

[Stefan Kanthak]

"Pavan Nikhilesh Bhagavatula"  wrote Thursday, March 
28, 2019 6:35 AM:


Hi Stefan,

Thanks for the heads up, I am planning to use a modified version of
https://github.com/hcs0/Hackers-Delight/blob/master/divluh.c.txt
for simplicity as we don't require the remainder.


Why don't you refer to the ORIGINAL source
<https://www.hackersdelight.org/hdcodetxt/divluh.c.txt> instead?

BUT: you also shouldn't use these routines, they too show quite bad
implementations of a binary division!
As Don Knuth wrote in volume 2 of TAoCP, hardware implementations
are most often NOT well-suited for implementation in software.

Take a look at the following STRAIGHTFORWARD implementation, both
in ANSI C and x86 assembly (for Microsoft's Visual C compiler):

unsigned long long divide(unsigned long long dividendlow,
 unsigned long long dividendhigh,
 unsigned long long divisor,
 unsigned long long *remainder)
{
#ifndef _M_IX86
   unsigned int shift = 64;

   do
   {
   if (dividendhigh < divisor)
   {
   dividendhigh <<= 1;
   dividendhigh |= dividendlow >> 63;
   dividendlow <<= 1;
   }
   else
   {
   dividendhigh -= divisor;
   dividendhigh <<= 1;
   dividendhigh |= dividendlow >> 63;
   dividendlow <<= 1;
   dividendlow |= 1;
   }
   } while (--shift != 0);

   if (*remainder != NULL)
   remainder = dividendhigh;

   return dividendlow;
#else
   __asm
   {
   moveax, dword ptr dividendlow
   movedx, dword ptr dividendlow+4
   movecx, dword ptr dividendhigh
   movebx, dword ptr dividendhigh+4
   movedi, dword ptr divisor
   movesi, dword ptr divisor+4
   movebp, 64

   NEXT:
   cmpebx, esi
   ja SUBTRACT
   jb SHIFT
   cmpecx, edi
   jb SHIFT

   SUBTRACT:
   subecx, edi
   sbbebx, esi

   SHIFT:
   cmc
   adceax, eax
   adcedx, edx
   adcecx, ecx
   adcebx, ebx
   decebp
   jnzNEXT

   or ebp, remainder
   jz EXIT

   mov[ebp], ecx
   mov[ebp+4], ebx
   EXIT:
   }
#endif
}



-Original Message-
From: dev  On Behalf Of Stefan Kanthak
Sent: Tuesday, March 26, 2019 6:41 AM
To: dev@dpdk.org
Cc: han...@stressinduktion.org
Subject: [dpdk-dev] [BUG] Maintainer for
lib/librte_eal/common/rte_reciprocal.c?

Hi @ll,

<https://git.dpdk.org/dpdk/plain/MAINTAINERS> does NOT list a maintainer
for lib/librte_eal/common/rte_reciprocal.c

Whoever it is should take a close look at <https://skanthak.homepage.t-
online.de/division.html>,
then fix the most obvious bug plus the many deficiencies of
divide_128_div_64_to_64().

regards
Stefan Kanthak

Re: [dpdk-dev] [PATCH] eal: fix large multiple calculation in reciprocal division

[Stefan Kanthak]

Pavan Nikhilesh  wrote Sunday, April 14, 2019 7:22 AM:



From: Pavan Nikhilesh 

Fix large multiple calculation in 64 bit reciprocal division.


This "fix" has a SERIOUS bug, it needs yet another fix.
I recommend to understand code first before you copy it!

[...]


+ int64_t i;


uint i = 64;


+ uint64_t t;
+
+ for (i = 1; i <= 64; i++) {


do {


+ t = x >> 63;


t = (int64_t) x >> 63; // t is either 0ULL or ~0ULL


+ x = (x << 1) | (y >> 63);
+ y = y << 1;
+ if ((x | t) >= z) {
+ x = x - z;
+ y = y + 1;
+ }


} while (--i > 0);

Stefan Kanthak