Cant make value propagate through carry

Making a little C++ large precision class, and everything seems to work decent, but the add, if I add 0xffffffff and 0x04 together I get 0xffff0003 when I should get 0x0100000003. Here is the function with the issue:

mpfl operator+(const mpfl &lhs, const mpfl &rhs)
{
    unsigned long i;
    mpfl ret(0);
    mpfl trhs(rhs);
    for (i = lhs.nbytes; i >= 0; i--)
    {
        if (
            (unsigned short)lhs.data[i].data + (unsigned short)trhs.data[i].data
            > (unsigned short)255
        ) {
            if (i > 0)
            {
                ret.data[i].carry = 1;
                ret.data[0].carry = 0;
            }
            else
            {
                ret.data[0].carry = 1;
            }
        }
        else
            ret.data[i].carry = 0;
        ret.data[i].data = lhs.data[i].data + trhs.data[i].data;
        if (i < lhs.nbytes)
        {
            if (ret.data[i].data == 255 && ret.data[i + 1].carry == 1)
                increment(&trhs, i + 1);
            ret.data[i].data += ret.data[i + 1].carry;
        }
        if (i == 0) break;
    }
    return ret;
}

Here are links to the full source (github made this easier since there is a lot of it)

header: https://github.com/phyrrus9/mpfl/blob/master/mpfl.h
class: https://github.com/phyrrus9/mpfl/blob/master/mpfl.cpp
driver: https://github.com/phyrrus9/mpfl/blob/master/main.cpp

Solution 1:

Your code is very messy to me. I did (long)num classes many times before (floating,fixed,uint,templated,...) so here are some hints:

Try to setup ALU architecture similar to real HW implementation.

Most algorithms are written for such environment. It will clean and speed up your code. In some cases I use asm for this but if you want to be not CPU dependent you can use this class of mine

ALU source in C++:

//---------------------------------------------------------------------------
//--- ALU32 class 2.01 ------------------------------------------------------
//---------------------------------------------------------------------------
#ifndef _ALU32_h
#define _ALU32_h
//---------------------------------------------------------------------------
//#define _ALU32_no_asm
//---------------------------------------------------------------------------
class ALU32
    {
public:
    BYTE cy;
    ALU32() { cy=0; }
    void sar(DWORD &c); // msb -> [msb...lsb] -> cy     shift arithmetic right
    void shl(DWORD &c); // cy  <- [msb...lsb] <- 0      shift left
    void shr(DWORD &c); // 0   -> [msb...lsb] -> cy     shift right
    void rcl(DWORD &c); // cy  <- [msb...lsb] <- cy     shift through carry left
    void rcr(DWORD &c); // cy  -> [msb...lsb] -> cy     shift through carry lright
    void inc(DWORD &c);                                     
    void dec(DWORD &c);                                     
    void add(DWORD &c,DWORD a,DWORD b);                     
    void sub(DWORD &c,DWORD a,DWORD b);                     
    void adc(DWORD &c,DWORD a,DWORD b);                     
    void sbc(DWORD &c,DWORD a,DWORD b);                     
    void mul(DWORD &ch,DWORD &cl,DWORD a,DWORD b);          // (ch,cl) = a*b
    void div(DWORD &c,DWORD &d,DWORD ah,DWORD al,DWORD b);  // c = a/b d =a%b
    };
//---------------------------------------------------------------------------
void ALU32::inc(DWORD &c) { if (c==0xFFFFFFFF) cy=1; else cy=0; c++; }
void ALU32::dec(DWORD &c) { if (c==0x00000000) cy=1; else cy=0; c--; }
//---------------------------------------------------------------------------
void ALU32::sar(DWORD &c)
    {
    cy=c&1;
    c=((c>>1)&0x7FFFFFFF)|(c&0x80000000);
    }
//---------------------------------------------------------------------------
void ALU32::shl(DWORD &c)
    {
    cy=c>>31;
    c=(c<<1)&0xFFFFFFFE;
    }
//---------------------------------------------------------------------------
void ALU32::shr(DWORD &c)
    {
    cy=c&1;
    c=(c>>1)&0x7FFFFFFF;
    }
//---------------------------------------------------------------------------
void ALU32::rcl(DWORD &c)
    {
    DWORD cy0=cy;
    cy=c>>31;
    c=((c<<1)&0xFFFFFFFE)|cy0;
    }
//---------------------------------------------------------------------------
void ALU32::rcr(DWORD &c)
    {
    DWORD cy0=cy;
    cy=c&1;
    c=((c>>1)&0x7FFFFFFF)|(cy0<<31);
    }
//---------------------------------------------------------------------------
void ALU32::add(DWORD &c,DWORD a,DWORD b)
    {
    c=a+b;
    cy=DWORD(((a &1)+(b &1)   )>> 1);
    cy=DWORD(((a>>1)+(b>>1)+cy)>>31);
    }
//---------------------------------------------------------------------------
void ALU32::sub(DWORD &c,DWORD a,DWORD b)
    {
    c=a-b;
    if (a<b) cy=1; else cy=0;
    }
//---------------------------------------------------------------------------
void ALU32::adc(DWORD &c,DWORD a,DWORD b)
    {
    c=a+b+cy;
    cy=DWORD(((a &1)+(b &1)+cy)>> 1);
    cy=DWORD(((a>>1)+(b>>1)+cy)>>31);
    }
//---------------------------------------------------------------------------
void ALU32::sbc(DWORD &c,DWORD a,DWORD b)
    {
    c=a-b-cy;
    if (cy) { if (a<=b) cy=1; else cy=0; }
    else    { if (a< b) cy=1; else cy=0; }
    }
//---------------------------------------------------------------------------
void ALU32::mul(DWORD &ch,DWORD &cl,DWORD a,DWORD b)
    {
    #ifdef _ALU32_no_asm
    const int _h=1; // this is MSW,LSW order platform dependent So swap 0,1 if your platform is different
    const int _l=0;
    union _u
        {
        DWORD u32;
        WORD u16[2];
        } u;
    DWORD al,ah,bl,bh;
    DWORD c0,c1,c2;
    // separate 2^16 base digits
    u.u32=a; al=u.u16[_l]; ah=u.u16[_h];
    u.u32=b; bl=u.u16[_l]; bh=u.u16[_h];
    // multiplication (al+ah<<16)*(bl+bh<<16) = al*bl + al*bh<<16 + ah*bl<<16 + ah*bh<<32
    c0=(al*bl);
    add(c1,al*bh,ah*bl);
    c2=(ah*bh)+(cy<<16);
    // add subresults
    add(c0,c0,(c1<<16)&0xFFFF0000); c1=((c1>>16)&0x0000FFFF)+cy;
    add(c1,c1,c2);
    // construct result from (c3,c2,c1,c0)
    ch=c1;
    cl=c0;
    #else
    DWORD _a,_b,_cl,_ch;
    _a=a;
    _b=b;
    asm {
        mov eax,_a
        mov ebx,_b
        mul ebx     // H(edx),L(eax) = eax * ebx
        mov _cl,eax
        mov _ch,edx
        }
    cl=_cl;
    ch=_ch;
    #endif
    }
//---------------------------------------------------------------------------
void ALU32::div(DWORD &c,DWORD &d,DWORD ah,DWORD al,DWORD b)
    {
    #ifdef _ALU32_no_asm
    DWORD ch,cl,bh,bl,h,l,mh,ml;
    int e;
    // edge cases
    if (!b ){ c=0xFFFFFFFF; d=0xFFFFFFFF; cy=1; return; }
    if (!ah){ c=al/b;       d=al%b;       cy=0; return; }
    // align a,b for binary long division m is the shifted mask of b lsb
    for (bl=b,bh=0,mh=0,ml=1;bh<0x80000000;)
        {
        e=0; if (ah>bh) e=+1;   // e = cmp a,b {-1,0,+1}
        else if (ah<bh) e=-1;
        else if (al>bl) e=+1;
        else if (al<bl) e=-1;
        if (e<=0) break;        // a<=b ?
        shl(bl); rcl(bh);       // b<<=1
        shl(ml); rcl(mh);       // m<<=1
        }
    // binary long division
    for (ch=0,cl=0;;)
        {
        sub(l,al,bl);           // a-b
        sbc(h,ah,bh);
        if (cy)                 // a<b ?
            {
            if (ml==1) break;
            shr(mh); rcr(ml);   // m>>=1
            shr(bh); rcr(bl);   // b>>=1
            continue;
            }
        al=l; ah=h;             // a>=b ?
        add(cl,cl,ml);          // c+=m
        adc(ch,ch,mh);
        }
    cy=0; c=cl; d=al;
    if ((ch)||(ah)) cy=1;       // overflow
    #else
    DWORD _al,_ah,_b,_c,_d;
    _al=al;
    _ah=ah;
    _b=b;
    asm {
        mov eax,_al
        mov edx,_ah
        mov ebx,_b
        div ebx
        mov _c,eax  // eax = H(edx),L(eax) / ebx
        mov _d,edx  // edx = H(edx),L(eax) % ebx
        }
    c=_c;
    d=_d;
    #endif
    }
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

mul and div are switchable between fast CPU assembly and slower C++ implementation with the #define _ALU32_no_asm
DWORD is 32 bit unsigned int and can be defined like typedef unsigned __int32 DWORD;

So now if you want to add two arrays (fixed size N)

It can be done like this:
```
ALU32 alu;
DWORD a[N],b[N],c[N]; // a[0] is LSB and a[N-1] is MSB

alu.add(c[0],a[0],b[0]);
for (int i=1;i<N;i++) alu.adc(c[i],a[i],b[i]);
// here c[] = a[] + b[]
```
it is a good idea to use the biggest base you can to improve speed. If you still need 8 bit ALU this can be also easily rewritten and even simplified due to direct access to carry. You can use 16 or 32 bit variables and extract 9th bit as carry directly from sub-results (looks like you are doing it).
Your problem (copied from comment)

My bet is that your problem is here:
```
if (i<lhs.nbytes)
        {
        if (ret.data[i].data == 255 && ret.data[i + 1].carry == 1) increment(&trhs, i + 1);
        ret.data[i].data += ret.data[i + 1].carry;
        }
```
carry should be applied always but the first time (you do it always but the last time). This also reveals other possibility how is your number stored?
- data[0] is the LSB or MSB (low/most significant bit/byte...)?
You have to start adding from lowest digits
- so either you just applying carry the other way around
- or you are adding from highest to lowest digits
but booth are incorrect.

PS. in case you need 32 bit ALU style multiplication without asm in pure C/C++ see this link (but after last update the code here already contains such mul,div):

Building a logarithm function in C without using float type

Cant make value propagate through carry

Solution 1:

Related

Recent Posts