SymmetricMatrix::GetEigen memory corruption

[chpatrick]

I found some memory corruption in the SymmetricMatrix::GetEigen function. I think it's caused by the following line:

UVAtlas/UVAtlas/isochart/SymmetricMatrix.hpp

Line 222 in 0437b92

pEigenValue[i] = pRowHeader[i][i];

In this for loop i goes up to i < dwDimension - 1, but pEigenValue is of size dwMaxRange, and dwMaxRange <= dwDimension.

I have a version that replaces that function with a call to the Eigen library here: chpatrick@d009630

[nh2]

I have a version that replaces that function with a call to the Eigen library here: chpatrick@d009630

This also replaces the O(n^3) sorting (!) algorithm used so far to emit eivenvalues/vector in descending order.

UVAtlas/UVAtlas/isochart/SymmetricMatrix.hpp

Lines 436 to 451 in 0437b92

	// Sort eigenvalues and corresponding vectors.
	for (size_t i = 0; i < dwDimension - 1; i++)
	{
	for (size_t j = i + 1; j < dwDimension; j++)
	{
	if (pEigenValue[j] > pEigenValue[i])
	{
	std::swap(pEigenValue[i], pEigenValue[j]);
	for (size_t k = 0; k < dwDimension; k++)
	{
	std::swap(pRowHeader[k][i], pRowHeader[k][j]);
	}
	}
	}
	}

So far if you called GetEigen() on a 14k-square matrix, just the sorting of the results of at the end would require 14000^3 = 2744000000000 = ~3 Tera-swaps.

[nh2]

This also replaces the O(n^3) sorting (!) algorithm

Embarassingly, I am wrong; Eigen also uses a O(n^3) sort:

https://gitlab.com/libeigen/eigen/-/blob/6cbb3038ac48cb5fe17eba4dfbf26e3e798041f1/Eigen/src/Eigenvalues/SelfAdjointEigenSolver.h#L535-551

// TODO use a better sort algorithm !!

[walbourn]

The test at the start of GetEigen establishes that dwMaxRange >= dwDimension, but you wrote <=.

            if (dwDimension < dwMaxRange
                || dwMaxRange == 0
                || dwDimension == 0)
            {
                return false;
            }

[chpatrick]

No, that check establishes that dwMaxRange <= dwDimension, otherwise it returns false.

The opposite wouldn't make any sense because the goal of this function is to compute only dwMaxRange eigenvalues out of a maximum of dwDimension. The memory corruption is caused by mistakenly copying out dwDimension - 1 many eigenvalues, even if only dwMaxRange were requested (and space allocated for).

[walbourn]

OK, I'll take another look.

I'll also integrate the opt-in use of the Eigen library to my CMakeList.txt, probably through a build option. For my vcpkg port, I should be able to make use of the eigen3 port for the dependency. This is certainly the more robust & reliable thing to use instead of the 'home-rolled' GetEigen the library currently uses, but I don't want to force all users to take another dependency.

[walbourn]

OK, I think the problem is that the algorithm in that header is trying to use pEigenValues as the temporary space as well as the final answer, which is obviously going to fail in some conditions. It looks like in most cases it worked by accident because the allocation within the library of the return eigen vectors gave it sufficient space to not crash IIF it was allocated right after the value:

m_pfEigenValue = new (std::nothrow) float[dwSelectedDimension];
m_pfEigenVector = new (std::nothrow) float[m_dwMatrixDimension * dwSelectedDimension];

[walbourn]

Fixed in this commit

[walbourn]

Added an opt-in build-option to CMake to support using the Eigen library. See this commit