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

[Stefan Kanthak]

"Pavan Nikhilesh Bhagavatula" <pbhagavatula at marvell.com> 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
    {
        mov    eax, dword ptr dividendlow
        mov    edx, dword ptr dividendlow+4
        mov    ecx, dword ptr dividendhigh
        mov    ebx, dword ptr dividendhigh+4
        mov    edi, dword ptr divisor
        mov    esi, dword ptr divisor+4
        mov    ebp, 64

    NEXT:
        cmp    ebx, esi
        ja     SUBTRACT
        jb     SHIFT
        cmp    ecx, edi
        jb     SHIFT

    SUBTRACT:
        sub    ecx, edi
        sbb    ebx, esi

    SHIFT:
        cmc
        adc    eax, eax
        adc    edx, edx
        adc    ecx, ecx
        adc    ebx, ebx
        dec    ebp
        jnz    NEXT

        or     ebp, remainder
        jz     EXIT

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


> -----Original Message-----
> From: dev <dev-bounces at dpdk.org> On Behalf Of Stefan Kanthak
> Sent: Tuesday, March 26, 2019 6:41 AM
> To: dev at dpdk.org
> Cc: hannes at 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