Function RecursiveMultiplyTop

src/cryptlib/integer.cpp:582–651

// B[N] --- multiplicant

void RecursiveMultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, unsigned int N)
{
    assert(N>=2 && N%2==0);

    if (N==2)
    {
        AtomicMultiply(T, A[0], A[1], B[0], B[1]);
        R[0] = T[2];
        R[1] = T[3];
    }
    else
    {
        const unsigned int N2 = N/2;
        int carry;

        int aComp = Compare(A0, A1, N2);
        int bComp = Compare(B0, B1, N2);

        switch (2*aComp + aComp + bComp)
        {
        case -4:
            Subtract(R0, A1, A0, N2);
            Subtract(R1, B0, B1, N2);
            RecursiveMultiply(T0, T2, R0, R1, N2);
            Subtract(T1, T1, R0, N2);
            carry = -1;
            break;
        case -2:
            Subtract(R0, A1, A0, N2);
            Subtract(R1, B0, B1, N2);
            RecursiveMultiply(T0, T2, R0, R1, N2);
            carry = 0;
            break;
        case 2:
            Subtract(R0, A0, A1, N2);
            Subtract(R1, B1, B0, N2);
            RecursiveMultiply(T0, T2, R0, R1, N2);
            carry = 0;
            break;
        case 4:
            Subtract(R0, A1, A0, N2);
            Subtract(R1, B0, B1, N2);
            RecursiveMultiply(T0, T2, R0, R1, N2);
            Subtract(T1, T1, R1, N2);
            carry = -1;
            break;
        default:
            SetWords(T0, 0, N);
            carry = 0;
        }

        RecursiveMultiply(T2, R0, A1, B1, N2);

        // now T[01] holds (A1-A0)*(B0-B1), T[23] holds A1*B1

        CopyWords(R0, L+N2, N2);
        word c2 = Subtract(R0, R0, L, N2);
        c2 += Subtract(R0, R0, T0, N2);