Function SubatomicDivide

src/cryptlib/integer.cpp:821–856

do a 3 word by 2 word divide, returns quotient and leaves remainder in A

// do a 3 word by 2 word divide, returns quotient and leaves remainder in A
static word SubatomicDivide(word *A, word B0, word B1)
{
    // assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a word
    assert(A[2] < B1 || (A[2]==B1 && A[1] < B0));

    dword_union p, u;
    word Q;

    // estimate the quotient: do a 2 word by 1 word divide
    if (B1+1 == 0)
        Q = A[2];
    else
        Q = word(MAKE_DWORD(A[1], A[2]) / (B1+1));

    // now subtract Q*B from A
    p.dw = (dword) B0*Q;
    u.dw = (dword) A[0] - p.low;
    A[0] = u.low;
    u.dw = (dword) A[1] - p.high - (word)(0-u.high) - (dword)B1*Q;
    A[1] = u.low;
    A[2] += u.high;

    // Q <= actual quotient, so fix it
    while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
    {
        u.dw = (dword) A[0] - B0;
        A[0] = u.low;
        u.dw = (dword) A[1] - B1 - (word)(0-u.high);
        A[1] = u.low;
        A[2] += u.high;
        Q++;
        assert(Q);  // shouldn't overflow
    }

    return Q;
}

// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1
static inline void AtomicDivide(word &Q0, word &Q1, const word *A, word B0, word B1)