Function DivideThreeWordsByTwo

src/cryptopp/integer.cpp:413–453

// 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=NULL)
{
	CRYPTOPP_UNUSED(dummy);

	// Assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a S
	CRYPTOPP_ASSERT(A[2] < B1 || (A[2]==B1 && A[1] < B0));

	// estimate the quotient: do a 2 S by 1 S divide.
	// Profiling tells us the original second case was dominant, so it was promoted to the first If statement.
	// The code change occurred at Commit dc99266599a0e72d.

	S Q; bool pre = (S(B1+1) == 0);
	if (B1 > 0 && !pre)
		Q = D(A[1], A[2]) / S(B1+1);
	else if (pre)
		Q = A[2];
	else
		Q = D(A[0], A[1]) / B0;

	// 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++;
		CRYPTOPP_ASSERT(Q);	// shouldn't overflow
	}

	return Q;
}

// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1
template <class S, class D>