multprec.cpp: _MP_Rem has apparently nonsense memory read

[BillyONeal]

Consider this line:

STL/stl/src/multprec.cpp

Line 133 in 5be7d49

if (qh < maxVal && qh * v[n - 2] <= (rh << shift) + u[j + n - 2]) {

This is reported as buggy by PREfast:

warning C6385: Reading invalid data from 'v': the readable size is '16' bytes, but '-8' bytes may be read.

I think PREfast may be correct (because v is an unsigned long long[2]) but don't understand this well enough right now to figure out why this might be OK; if it is OK, we should replace v[n - 2] with v[0] since 2 is the only value of n that doesn't trigger underflow here.

[statementreply]

It appears to me that _MP_Rem was originally written for multi-precision _MP_arr v, but was modified to deal with the case of n == 2 only. The only call site in _Next_linear_congruential_value ensures that n can't be 1.

STL/stl/inc/random

Line 408 in 5be7d49

static_assert(0 == _Mx || (_Ax < _Mx && _Cx < _Mx), "invalid template argument for linear_congruential_engine");

STL/stl/inc/random

Lines 327 to 337 in 5be7d49

	} else if _CONSTEXPR_IF (_Cx <= ULLONG_MAX && static_cast<_Uint>(_Mx - 1) <= (ULLONG_MAX - _Cx) / _Ax) {
	// unsigned long long is sufficient to store intermediate calculation
	const auto _Mul = static_cast<unsigned long long>(_Prev) * _Ax + _Cx;
	return static_cast<_Uint>(_Mul % _Mx);
	} else { // no intermediate integral type fits; fall back to multiprecision
	_MP_arr _Wx;
	_MP_Mul(_Wx, _Prev, _Ax);
	_MP_Add(_Wx, _Cx);
	_MP_Rem(_Wx, _Mx);
	return static_cast<_Uint>(_MP_Get(_Wx));
	}

When _Mx fits in the lower half of unsigned long long, static_cast<_Uint>(_Mx - 1) <= (ULLONG_MAX - _Cx) / _Ax must be true.

[StephanTLavavej]

My #5436 is making multprec.cpp retained for bincompat only.

I see a few things we could do here:

• Suppress this warning forever (until vNext when we can remove the code).
• Update the _Analysis_assume_ to record the assumption that n == 2, as @statementreply explained 5 years ago.
• Reimplement these functions with _Unsigned128 to dramatically shrink the file.
  • We'd have to map between the different representations of _MP_arr and _Unsigned128.

[StephanTLavavej]

I'll try to reimplement.