Function DivideThreeWordsByTwo

extra/yassl/taocrypt/src/integer.cpp:358–388

// do a 3 word by 2 word divide, returns quotient and leaves remainder in A
template <class S, class D>
S DivideThreeWordsByTwo(S* A, S B0, S B1, D* dummy_VC6_WorkAround = 0)
{
    // estimate the quotient: do a 2 S by 1 S divide
    S Q;
    if (S(B1+1) == 0)
        Q = A[2];
    else
        Q = D(A[1], A[2]) / S(B1+1);

    // now subtract Q*B from A
    D p = D::Multiply(B0, Q);
    D u = (D) A[0] - p.GetLowHalf();
    A[0] = u.GetLowHalf();
    u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - 
            D::Multiply(B1, Q);
    A[1] = u.GetLowHalf();
    A[2] += u.GetHighHalf();

    // Q <= actual quotient, so fix it
    while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
    {
        u = (D) A[0] - B0;
        A[0] = u.GetLowHalf();
        u = (D) A[1] - B1 - u.GetHighHalfAsBorrow();
        A[1] = u.GetLowHalf();
        A[2] += u.GetHighHalf();
        Q++;
    }

    return Q;
}


// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1