Faulty Multiplication (Buffer based)

[awsdert]

I got bored and started writing a bignum style library for fun, I got all the basic math working fine but am having difficulty getting a faster multiplication function to work, the full file is here:
https://ideone.com/Edz7Ay (online compiler)
The problem code is here:

// Karatsuba Algorithm
uint vmul2_(uintptr_t TBEG, uintptr_t TEND, uchar i, uintptr_t SBEG, uintptr_t SEND, schar s1, schar s2, uintptr_t NBEG, uintptr_t NEND, schar n1, schar n2)
{
    if (!SBEG || !SEND || !NBEG || !NEND)
        return 0;
    uchar x1 = (SBEG == SEND) ? 0 : *((uchar*)(SBEG += i ? s1 : s2));
    uchar y1 = (NBEG == NEND) ? 0 : *((uchar*)(NBEG += i ? n1 : n2));
    i ^= 1;
    uchar x2 = (SBEG == SEND) ? 0 : *((uchar*)(SBEG += i ? s1 : s2));
    uchar y2 = (NBEG == NEND) ? 0 : *((uchar*)(NBEG += i ? n1 : n2));
    i ^= 1;
    ushort A = x1 * y1;
    ushort B = x2 * y2;
    uint   C = (x1 + x2) * (y1 + y2);
    uint   K = C - A - B;
    uint   R = 100 + K * 10 + B;
    uint   M = 0;
    if (SBEG != SEND || NBEG != NEND)
        M = vmul2_((TBEG == TEND) ? TBEG : (TBEG+2), TEND, i, SBEG, SEND, s1, s2, NBEG, NEND, n1, n2);
    M += R;
    (void)getIntEndianEx(&n1, &n2);
    vadd_(TBEG, TEND, 1, 1, (uintptr_t)(&M), (uintptr_t)END_OF_VAR(M), n1, n2);
    return R;
}
void* vmul2(void* SRC, void *SRCEND, char srcEndian, void *NUM, void *NUMEND, char numEndian)
{
    if (!SRC || !SRCEND || !NUM || !NUMEND)
        return NULL;
    schar s1, s2, n1, n2;
    uintptr_t SEND, SBEG = vsh_endian(SRC, SRCEND, &SEND, &s1, &s2, srcEndian);
    uintptr_t srcSize = ((SBEG < SEND) ? SEND - SBEG : SBEG - SEND) + 1;
    uintptr_t NEND, NBEG = vsh_endian(NUM, NUMEND, &NEND, &n1, &n2, numEndian);
    if (is0(SRC, SRCEND, srcEndian) || is0(NUM, NUMEND, numEndian))
    {
        memset(SRC, 0, srcSize);
        return SRC;
    }
    uchar *tmp = calloc(srcSize, 1);
    uintptr_t TBEG = (uintptr_t)tmp, TEND = TBEG + (srcSize - 1);
    if (!tmp) return NULL;
    (void)vmul2_(TBEG, TEND, 1, SBEG, SEND, s1, s2, NBEG, NEND, n1, n2);
    vcpy(SRC, SRCEND, srcEndian, tmp, (void*)TEND, 'l');
    free(tmp);
    return SRC;
}

[awsdert]

minor modification to vmul2_ after I realised it was starting from the second byte of SRC and NUM

uint vmul2_(uintptr_t TBEG, uintptr_t TEND, uchar i, uintptr_t SBEG, uintptr_t SEND, schar s1, schar s2, uintptr_t NBEG, uintptr_t NEND, schar n1, schar n2)
{
    if (!SBEG || !SEND || !NBEG || !NEND)
        return 0;
    uchar x1 = (SBEG == SEND) ? 0 : *((uchar*)(SBEG));
    uchar y1 = (NBEG == NEND) ? 0 : *((uchar*)(NBEG));
    i ^= 1;
    uchar x2 = (SBEG == SEND) ? 0 : *((uchar*)(SBEG += i ? s1 : s2));
    uchar y2 = (NBEG == NEND) ? 0 : *((uchar*)(NBEG += i ? n1 : n2));
    i ^= 1;
    ushort A = x1 * y1;
    ushort B = x2 * y2;
    uint   C = (x1 + x2) * (y1 + y2);
    uint   K = C - A - B;
    uint   R = 100 + K * 10 + B;
    uint   M = 0;
    if (SBEG != SEND) SBEG += i ? s1 : s2;
    if (NBEG != NEND) NBEG += i ? n1 : n2;
    if (SBEG != SEND || NBEG != NEND)
        M = vmul2_((TBEG == TEND) ? TBEG : (TBEG+1), TEND, i, SBEG, SEND, s1, s2, NBEG, NEND, n1, n2);
    M += R;
    (void)getIntEndianEx(&n1, &n2);
    vadd_(TBEG, TEND, 1, 1, (uintptr_t)(&M), (uintptr_t)END_OF_VAR(M), n1, n2);
    return R;
}

[awsdert]

I found an better psuedocode on the net to write my algorithm on and I now have this:

void*
NOTHROW STDCALL
vmul(void* SRC, size_t srcSize, char srcEndian, void *NUM, size_t numSize, char numEndian)
{
    if (!SRC || !srcSize || !NUM || !numSize) return NULL;
    if (is0(SRC, srcSize, srcEndian) || is0(NUM, numSize, numEndian))
        return memset(SRC, 0, srcSize);
    uchar *tmp = calloc(srcSize, 1);
    if (!tmp) return NULL;
    schar s1, s2, n1, n2;
    uintptr_t TEND, TBEG = vendian((uintptr_t)tmp, srcSize, &TEND, &s1, &s2, srcEndian);
    uintptr_t SEND, SBEG = vendian((uintptr_t)SRC, srcSize, &SEND, &s1, &s2, srcEndian);
    uintptr_t NEND, NBEG = vendian((uintptr_t)NUM, numSize, &NEND, &n1, &n2, numEndian);
    uchar i = 1, bit, shift = CHAR_BIT - 1, *num = (uchar*)NBEG;
loop:
    for (bit = 1; bit; bit <<= 1, vshl_(SBEG, SEND, shift, 1, s1, s2))
        if (*num & bit) (void)vadd_(TBEG, TEND, s1, s2, SBEG, SEND, s1, s2);
    if (NBEG == NEND)
    {
        (void)memcpy(SRC, tmp, srcSize);
        free(tmp);
        return SRC;
    }
    num = (uchar*)(NBEG += i ? n1 : n2);
    i ^= 1;
    goto loop;
}
uintptr_t
NOTHROW STDCALL
vmul_karatsuba(
    uintptr_t SRC, size_t srcSize, char srcEndian,
    uintptr_t NUM, size_t numSize, char numEndian)
{
//#error "Bug causing write to BEFORE buffer"
    if (!srcSize || !numSize) return 0;
    size_t srcSize2 = srcSize / 2;
    size_t numSize2 = numSize / 2;
    uchar si = 1, ni = 1;
    schar s1, s2, s3,s4, n1, n2,n3,n4;
    void *SCPY = malloc(srcSize);
    if (!SCPY) return 0;
    void *NCPY = malloc(numSize);
    if (!NCPY)
    {
        free(SCPY);
        return 0;
    }
    uintptr_t SHIGH, SLOW = vendian(SRC, srcSize2, &SHIGH, &s1, &s2, srcEndian), SEND = SHIGH;
    uintptr_t NHIGH, NLOW = vendian(NUM, numSize2, &NHIGH, &n1, &n2, numEndian), NEND = NHIGH;
    uintptr_t SCHIGH, SCLOW = vendian((uintptr_t)SCPY, srcSize2, &SCHIGH, &s1, &s2, srcEndian);
    uintptr_t NCHIGH, NCLOW = vendian((uintptr_t)NCPY, numSize2, &NCHIGH, &n1, &n2, numEndian);
    s3 = -s1;
    s4 = -s2;
    while (srcSize-- > srcSize2)
    {
         SHIGH += si ? s3 : s4;
        SCHIGH += si ? s3 : s4;
        si ^= 1;
    }
    n3 = -n1;
    n4 = -n2;
    while (numSize-- > numSize2)
    {
         NHIGH += ni ? n3 : n4;
        NCHIGH += ni ? n3 : n4;
        ni ^= 1;
    }
    uintptr_t z0 = vmul_karatsuba(SCLOW,  srcSize2, srcEndian, NCLOW,  numSize2, numEndian);
    uintptr_t z2 = vmul_karatsuba(SCHIGH, srcSize2, srcEndian, NCHIGH, numSize2, numEndian);
    vadd_(SLOW, SHIGH + si ? s3 : s4, s1, s2, SHIGH, SEND, s1, s2);
    vadd_(NLOW, NHIGH + ni ? n3 : n4, n1, n2, NHIGH, NEND, n1, n2);
    uintptr_t z1 = vmul_karatsuba(SLOW, srcSize2, srcEndian, NUM, numSize2, numEndian);
    free(SCPY);
    free(NCPY);
//    return (z2 * 10 ^ (2 * srcSize2)) + ((z1 - z2 - z0) * 10 ^ (srcSize2)) + (z0);
    return (uintptr_t)vadd(
        vadd(
            vmul(
                vsub(
                    vsub((void*)z1, srcSize2, srcEndian, (void*)z2, srcSize2, srcEndian),
                    srcSize2, srcEndian, (void*)z0, srcSize2, srcEndian),
                srcSize2, srcEndian, &srcSize2, sizeof(size_t), getIntEndian()),
            srcSize2, srcEndian, (void*)z0, srcSize2, srcEndian),
        srcSize2, srcEndian, vmul((void*)z2, srcSize2, srcEndian, &srcSize, sizeof(size_t), getIntEndian()), srcSize2, srcEndian);
}

You can see the output at the link I posted, I modified the normal math functions to use labels instead to stop Microsoft VC complaining about loops with constant expressions and somehow broke my multiplication function, I would take a look at it myself but I have some things to do now so figured best to just post it and see if anyone posts an explanation of what went wrong on either or both functions by the time I get back.

[Elkvis]

goto loop;

NO!

How can a goto possibly be better than a while(1) loop or a for( ; ; ) loop? Do not use goto here!

[Salem]

Post links to your source material.

Post complete code - you know, so we can just copy/paste/compile/run and see exactly what you're doing.

We don't have the time to guess what your missing functions do, craft a main(), make wild guesses as to what your test data might be, only to perhaps discover that it "works for me".

[awsdert]

Refer to link in top post Salem, that is all the code there is

[Elkvis]

Where are vadd_ and vcpy, vsh_endian, etc defined? How do you expect anyone to help you, if they can't build it and try for themselves, or at least see the code and reason how it works?

[awsdert]

LIKE I SAID, the link above has ALL the code in ONE file, it is an online compiler so you can see the output directly, the main function is at the bottom next to the output.

[awsdert]

Be back in couple hours, got somewhere to be.

[GReaper]

Why is it written like this? Ouch, my eyes!!! Where did you learn that programming style from?!

[awsdert]

??? What's wrong with it?

[awsdert]

*sigh* didn't realise I had the setting for the file at the 1st link to be C90, had to create a new file with C99 setting, here it is: https://ideone.com/twTxVo.
I'm a little confused as to why ideone.com is spitting out a different output to Microsoft VC, I get a correct result with VC but not GCC which ideone.com is using.
Anyone wanna take a look and see if they can spot the issue? If you can't explain but can fix it then please post it and I can at least try to learn from the changes you made.

[laserlight]

I modified the normal math functions to use labels instead to stop Microsoft VC complaining about loops with constant expressions
(...)
??? What's wrong with it?

I am surprised that MSVC was unable to recognise a while (1) or while (true) as a deliberate infinite loop, but if it is that stupid, then instead of using a goto with a label, use for (;;). That said, it seems unlikely that such a change in itself "broke my multiplication function". Hopefully you are using version control so that you can compare the difference to see what regression was actually introduced.

[awsdert]

Erm, no I'm not as it's just a single file, well either way the multiplication function works under VC so I just need to find out what's GCC's problem with it (and hopefully make it cross-compiler simultaneously).

[Elkvis]

I'm a little confused as to why ideone.com is spitting out a different output to Microsoft VC

VC is not known for being especially standards-compliant, when it comes to compiling C code.

I get a correct result with VC but not GCC which ideone.com is using.

Your code probably (unknowingly) relies on something that the Microsoft compiler does differently, compared to GCC. I would suggest not using VC to build C code. What version of VC are you using? It appears that ideone.com uses gcc 4.9.2, based on the FAQ. It's likely that gcc is applying a more correct standard to your code than VC, regardless of the version of VC that you're using.