Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
2008/7/12 Michael Karcher <[EMAIL PROTECTED]>: > Am Samstag, den 12.07.2008, 16:55 -0500 schrieb James Hawkins: >> > GDI+ uses floating >> > point values for matrix elements so don't you think the result could be >> > slightly different due different calculation algorithms? > As they say: Never compare floating point numbers for equality. So I > understand your point. Especially if unrepresentable values are > involved. Agreed. There could also be issues depending on the compiler used (msvc vs gcc), different CPUs or instruction sets (e.g. using MMX/SSE/SSE2 to optimise the calculations). > Nikolay: Please write a test whether the matrix > 1.0/131072, 2.0/131072, 4.0/131072, -1/131072, 0, 0 > is invertible. According to your criterion, it is *not* invertible, as > the determinant will be 9.0/17179869184, which is way below 1e-5, but > this matrix still *is* invertible. What happens on Windows? The identity matrix would also be a nice test case - for the other GDI and DirectX matrix operations as well. - Reece
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
Michael Karcher wrote: > Am Samstag, den 12.07.2008, 16:55 -0500 schrieb James Hawkins: > > -GdipCreateMatrix2(1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0, > >>> Of course there's only one value of inverted matrix. >>> > Which is not representable as a finite binary fraction. > > >>> GDI+ uses floating >>> point values for matrix elements so don't you think the result could be >>> slightly different due different calculation algorithms? >>> > As they say: Never compare floating point numbers for equality. So I > understand your point. Especially if unrepresentable values are > involved. > > >> If you write and test the results in Windows, you won't have to guess >> what the results will be. >> > Right. Testing against Windows is the only method of verifying whether > Wine does the right things, but floating point arithmetic, which is > inherently prone to rounding errors, should IMHO be accounted for by > allowing slight variances. > > >> No I don't think the results will be >> slightly different. Higher-precision arithmetic doesn't mean more >> slop. >> > What do you mean with higher-precision arithmetic? Floating point > arithmetic *always* means slop, as soon as numbers that can't be written > as finite binary fractions are involved. In this concrete case, I > suspect you are right. There is just one obvious algorithm[1] to invert > a 2x2 Matrix, which is so simple that it cannot be stated in numerically > non-equivalent ways (remember, a+(b+c) is not necessarily equal to (a > +b)+c)), so I would expect the results to be really identical on windows > if the input numbers are small integers. Still, the fractions with nine > in the denominator make me worry. Couldn't we use a matrix with a > determinant of 8 or 16 instead of nine? This would make nice floats you > can definitely compare for equality. > > As a side note: I don't like the implementation of m_equalf, as it > checks for absolute deviation instead of relative deviation. The values > used have the same order of magnitude as 1, so it does not matter for > this test. But: This very criterion is also used in in > GdipIsMatrixInvertible, where I consider it highly questionable, as long > as it is not backed by API tests. > You're absolutely right. m_equalf id used as a temporary solution just to make the test pass with this deviation, which is acceptable in this particular initial data, to show that GdipInvertMatrix works in the main. But check in GdipIsMatrixInvertible should be replaced, I'm fully agreed here. I'll try to choose appropriate method to do so (using Windows test results too of course). > Nikolay: Please write a test whether the matrix > 1.0/131072, 2.0/131072, 4.0/131072, -1/131072, 0, 0 > is invertible. According to your criterion, it is *not* invertible, as > the determinant will be 9.0/17179869184, which is way below 1e-5, but > this matrix still *is* invertible. What happens on Windows? > On Windows it shows the following: 0., 32768.000, 65536.000, -16384.000, 0., 0. So native criterion differs. > Regards, > Michael Karcher > > [1] Which I found (as expected) when looking at dlls/gdiplus/matrix.c >
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
On Sat, Jul 12, 2008 at 4:16 PM, Dan Kegel <[EMAIL PROTECTED]> wrote: > Floating point equality comparisons need an error tolerance. > See e.g. > > http://teaching.idallen.com/cst8110/97s/floating_point.html > http://docs.hp.com/en/B3906-90006/ch03s05.html > http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems > http://search.cpan.org/~dagolden/Test-Number-Delta-1.03/lib/Test/Number/Delta.pm Someone goaded me into finding better links (thanks...), so: http://code.google.com/p/googletest/ is a test framework that gets it right, I think. After peeking at its source, I recalled the magic buzzword: ULP. Searching for floating point comparison ULP finds better links than I found before, e.g. http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm - Dan
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
Am Sonntag, den 13.07.2008, 01:14 +0200 schrieb Michael Karcher: > Am Samstag, den 12.07.2008, 23:56 +0100 schrieb Reece Dunn: > If you are brave enough to really find out what happens (might be > different depending on Windows version, instruction sets available and > things like that), also try the identity matrix scaled by 2^66 and > 2^(-66). The square of 2^66 overflows a 32 bit floating point number. Sorry, forgot denormals. The square of 2^(-66) *is* exactly represenatable as float! Use 2^(-80) to be sure that the square underflows. Regards, Michael Karcher
re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
James wrote: > > GDI+ uses floating point values for matrix elements so >> don't you think the result could be slightly different... > > No I don't think the results will be slightly different. > Higher-precision arithmetic doesn't mean more slop. Floating point equality comparisons need an error tolerance. See e.g. http://teaching.idallen.com/cst8110/97s/floating_point.html http://docs.hp.com/en/B3906-90006/ch03s05.html http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems http://search.cpan.org/~dagolden/Test-Number-Delta-1.03/lib/Test/Number/Delta.pm And testing matrix math routines is even trickier, it helps to have a really good math background there...
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
Am Samstag, den 12.07.2008, 23:56 +0100 schrieb Reece Dunn: > > Nikolay: Please write a test whether the matrix > > 1.0/131072, 2.0/131072, 4.0/131072, -1/131072, 0, 0 > > is invertible. According to your criterion, it is *not* invertible, as > > the determinant will be 9.0/17179869184, which is way below 1e-5, but > > this matrix still *is* invertible. What happens on Windows? > The identity matrix would also be a nice test case - for the other GDI > and DirectX matrix operations as well. Yes. Excellent idea! Determinant is one. Division by one is exact. This should definitely yield exact results. Now, add the identity matrix scaled by a big power of two (like 2^60) and divided by that power of two. Powers of two are as good as a simple one if you are on floating point numbers. If you are brave enough to really find out what happens (might be different depending on Windows version, instruction sets available and things like that), also try the identity matrix scaled by 2^66 and 2^(-66). The square of 2^66 overflows a 32 bit floating point number. So, if you calculate within x87 coprocessor registers, you can invert the matrix. If you store to double variables too. If you store to float variables or calc via SSE or 3Dnow! (overkill for a matrix inversion, I know), matrix inversion probably fails, if no tricks are used. Regards, Michael Karcher
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
Am Samstag, den 12.07.2008, 16:55 -0500 schrieb James Hawkins: > >>> -GdipCreateMatrix2(1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0, > > Of course there's only one value of inverted matrix. Which is not representable as a finite binary fraction. > > GDI+ uses floating > > point values for matrix elements so don't you think the result could be > > slightly different due different calculation algorithms? As they say: Never compare floating point numbers for equality. So I understand your point. Especially if unrepresentable values are involved. > If you write and test the results in Windows, you won't have to guess > what the results will be. Right. Testing against Windows is the only method of verifying whether Wine does the right things, but floating point arithmetic, which is inherently prone to rounding errors, should IMHO be accounted for by allowing slight variances. > No I don't think the results will be > slightly different. Higher-precision arithmetic doesn't mean more > slop. What do you mean with higher-precision arithmetic? Floating point arithmetic *always* means slop, as soon as numbers that can't be written as finite binary fractions are involved. In this concrete case, I suspect you are right. There is just one obvious algorithm[1] to invert a 2x2 Matrix, which is so simple that it cannot be stated in numerically non-equivalent ways (remember, a+(b+c) is not necessarily equal to (a +b)+c)), so I would expect the results to be really identical on windows if the input numbers are small integers. Still, the fractions with nine in the denominator make me worry. Couldn't we use a matrix with a determinant of 8 or 16 instead of nine? This would make nice floats you can definitely compare for equality. As a side note: I don't like the implementation of m_equalf, as it checks for absolute deviation instead of relative deviation. The values used have the same order of magnitude as 1, so it does not matter for this test. But: This very criterion is also used in in GdipIsMatrixInvertible, where I consider it highly questionable, as long as it is not backed by API tests. Nikolay: Please write a test whether the matrix 1.0/131072, 2.0/131072, 4.0/131072, -1/131072, 0, 0 is invertible. According to your criterion, it is *not* invertible, as the determinant will be 9.0/17179869184, which is way below 1e-5, but this matrix still *is* invertible. What happens on Windows? Regards, Michael Karcher [1] Which I found (as expected) when looking at dlls/gdiplus/matrix.c
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
James Hawkins wrote: > On Sat, Jul 12, 2008 at 4:35 PM, Nikolay Sivov <[EMAIL PROTECTED]> wrote: > >> James Hawkins wrote: >> >>> On Sat, Jul 12, 2008 at 4:12 PM, Nikolay Sivov <[EMAIL PROTECTED]> >>> wrote: >>> >>> Changelog: - Make GdipInvertMatrix test pass on native --- dlls/gdiplus/tests/matrix.c | 23 +-- 1 files changed, 17 insertions(+), 6 deletions(-) diff --git a/dlls/gdiplus/tests/matrix.c b/dlls/gdiplus/tests/matrix.c index 16c1517..daf61ea 100644 --- a/dlls/gdiplus/tests/matrix.c +++ b/dlls/gdiplus/tests/matrix.c @@ -27,6 +27,19 @@ #define expect(expected, got) ok(got == expected, "Expected %.8x, got %.8x\n", expected, got) +/* compare matrix data with some tolerance */ +BOOL m_equalf(REAL *m1, REAL *m2) +{ +BOOL ret = TRUE; +INT i; + +for(i = 0; i < 6; i++){ +ret = ret && (fabsf(m1[i] - m2[i]) < 1e-5); +} + +return ret; +} + static void test_constructor_destructor(void) { GpStatus status; @@ -119,12 +132,12 @@ static void test_isinvertible(void) GdipDeleteMatrix(matrix); } +static REAL minverted[] = {1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0}; static void test_invert(void) { GpStatus status; GpMatrix *matrix = NULL; -GpMatrix *inverted = NULL; -BOOL equal; +REAL mdata[6]; /* NULL */ status = GdipInvertMatrix(NULL); @@ -141,11 +154,9 @@ static void test_invert(void) status = GdipInvertMatrix(matrix); expect(Ok, status); -GdipCreateMatrix2(1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0, &inverted); -GdipIsMatrixEqual(matrix, inverted, &equal); -expect(TRUE, equal); +GdipGetMatrixElements(matrix, mdata); +expect(TRUE, m_equalf(mdata, minverted)); >>> Why are you creating a new function that allows tolerance when you >>> control the matrix you're comparing it to? Allowing slop is >>> acceptable in some circumstances, but not in this case, when there is >>> one exact value (or matrix of values) returned. >>> >> Of course there's only one value of inverted matrix. GDI+ uses floating >> point values for matrix elements so don't you think the result could be >> slightly different due different calculation algorithms? >> >> > > If you write and test the results in Windows, you won't have to guess > what the results will be. No I don't think the results will be > slightly different. Higher-precision arithmetic doesn't mean more > slop. > Higher then what? Bitwise comparison of floating point values is useless in most cases. The constant for inverted matrix provided in test is exact product of invert operation. Such difference is acceptable here. The tolerance could be decreased to 1e-7 I think but I don't see any reason for that.
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
On Sat, Jul 12, 2008 at 4:35 PM, Nikolay Sivov <[EMAIL PROTECTED]> wrote: > James Hawkins wrote: >> >> On Sat, Jul 12, 2008 at 4:12 PM, Nikolay Sivov <[EMAIL PROTECTED]> >> wrote: >> >>> >>> Changelog: >>> - Make GdipInvertMatrix test pass on native >>> >>> --- >>> dlls/gdiplus/tests/matrix.c | 23 +-- >>> 1 files changed, 17 insertions(+), 6 deletions(-) >>> >>> diff --git a/dlls/gdiplus/tests/matrix.c b/dlls/gdiplus/tests/matrix.c >>> index 16c1517..daf61ea 100644 >>> --- a/dlls/gdiplus/tests/matrix.c >>> +++ b/dlls/gdiplus/tests/matrix.c >>> @@ -27,6 +27,19 @@ >>> >>> #define expect(expected, got) ok(got == expected, "Expected %.8x, got >>> %.8x\n", expected, got) >>> >>> +/* compare matrix data with some tolerance */ >>> +BOOL m_equalf(REAL *m1, REAL *m2) >>> +{ >>> +BOOL ret = TRUE; >>> +INT i; >>> + >>> +for(i = 0; i < 6; i++){ >>> +ret = ret && (fabsf(m1[i] - m2[i]) < 1e-5); >>> +} >>> + >>> +return ret; >>> +} >>> + >>> static void test_constructor_destructor(void) >>> { >>>GpStatus status; >>> @@ -119,12 +132,12 @@ static void test_isinvertible(void) >>>GdipDeleteMatrix(matrix); >>> } >>> >>> +static REAL minverted[] = {1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, >>> -1.0}; >>> static void test_invert(void) >>> { >>>GpStatus status; >>>GpMatrix *matrix = NULL; >>> -GpMatrix *inverted = NULL; >>> -BOOL equal; >>> +REAL mdata[6]; >>> >>>/* NULL */ >>>status = GdipInvertMatrix(NULL); >>> @@ -141,11 +154,9 @@ static void test_invert(void) >>>status = GdipInvertMatrix(matrix); >>>expect(Ok, status); >>> >>> -GdipCreateMatrix2(1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0, >>> &inverted); >>> -GdipIsMatrixEqual(matrix, inverted, &equal); >>> -expect(TRUE, equal); >>> +GdipGetMatrixElements(matrix, mdata); >>> +expect(TRUE, m_equalf(mdata, minverted)); >>> >>> >> >> Why are you creating a new function that allows tolerance when you >> control the matrix you're comparing it to? Allowing slop is >> acceptable in some circumstances, but not in this case, when there is >> one exact value (or matrix of values) returned. > > Of course there's only one value of inverted matrix. GDI+ uses floating > point values for matrix elements so don't you think the result could be > slightly different due different calculation algorithms? > If you write and test the results in Windows, you won't have to guess what the results will be. No I don't think the results will be slightly different. Higher-precision arithmetic doesn't mean more slop. -- James Hawkins
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
James Hawkins wrote: > On Sat, Jul 12, 2008 at 4:12 PM, Nikolay Sivov <[EMAIL PROTECTED]> wrote: > >> Changelog: >>- Make GdipInvertMatrix test pass on native >> >> --- >> dlls/gdiplus/tests/matrix.c | 23 +-- >> 1 files changed, 17 insertions(+), 6 deletions(-) >> >> diff --git a/dlls/gdiplus/tests/matrix.c b/dlls/gdiplus/tests/matrix.c >> index 16c1517..daf61ea 100644 >> --- a/dlls/gdiplus/tests/matrix.c >> +++ b/dlls/gdiplus/tests/matrix.c >> @@ -27,6 +27,19 @@ >> >> #define expect(expected, got) ok(got == expected, "Expected %.8x, got >> %.8x\n", expected, got) >> >> +/* compare matrix data with some tolerance */ >> +BOOL m_equalf(REAL *m1, REAL *m2) >> +{ >> +BOOL ret = TRUE; >> +INT i; >> + >> +for(i = 0; i < 6; i++){ >> +ret = ret && (fabsf(m1[i] - m2[i]) < 1e-5); >> +} >> + >> +return ret; >> +} >> + >> static void test_constructor_destructor(void) >> { >> GpStatus status; >> @@ -119,12 +132,12 @@ static void test_isinvertible(void) >> GdipDeleteMatrix(matrix); >> } >> >> +static REAL minverted[] = {1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0}; >> static void test_invert(void) >> { >> GpStatus status; >> GpMatrix *matrix = NULL; >> -GpMatrix *inverted = NULL; >> -BOOL equal; >> +REAL mdata[6]; >> >> /* NULL */ >> status = GdipInvertMatrix(NULL); >> @@ -141,11 +154,9 @@ static void test_invert(void) >> status = GdipInvertMatrix(matrix); >> expect(Ok, status); >> >> -GdipCreateMatrix2(1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0, >> &inverted); >> -GdipIsMatrixEqual(matrix, inverted, &equal); >> -expect(TRUE, equal); >> +GdipGetMatrixElements(matrix, mdata); >> +expect(TRUE, m_equalf(mdata, minverted)); >> >> > > Why are you creating a new function that allows tolerance when you > control the matrix you're comparing it to? Allowing slop is > acceptable in some circumstances, but not in this case, when there is > one exact value (or matrix of values) returned. Of course there's only one value of inverted matrix. GDI+ uses floating point values for matrix elements so don't you think the result could be slightly different due different calculation algorithms?
Re: [3/3] gdiplus: Make GdipInvertMatrix test pass on native
On Sat, Jul 12, 2008 at 4:12 PM, Nikolay Sivov <[EMAIL PROTECTED]> wrote: > Changelog: >- Make GdipInvertMatrix test pass on native > > --- > dlls/gdiplus/tests/matrix.c | 23 +-- > 1 files changed, 17 insertions(+), 6 deletions(-) > > diff --git a/dlls/gdiplus/tests/matrix.c b/dlls/gdiplus/tests/matrix.c > index 16c1517..daf61ea 100644 > --- a/dlls/gdiplus/tests/matrix.c > +++ b/dlls/gdiplus/tests/matrix.c > @@ -27,6 +27,19 @@ > > #define expect(expected, got) ok(got == expected, "Expected %.8x, got > %.8x\n", expected, got) > > +/* compare matrix data with some tolerance */ > +BOOL m_equalf(REAL *m1, REAL *m2) > +{ > +BOOL ret = TRUE; > +INT i; > + > +for(i = 0; i < 6; i++){ > +ret = ret && (fabsf(m1[i] - m2[i]) < 1e-5); > +} > + > +return ret; > +} > + > static void test_constructor_destructor(void) > { > GpStatus status; > @@ -119,12 +132,12 @@ static void test_isinvertible(void) > GdipDeleteMatrix(matrix); > } > > +static REAL minverted[] = {1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0}; > static void test_invert(void) > { > GpStatus status; > GpMatrix *matrix = NULL; > -GpMatrix *inverted = NULL; > -BOOL equal; > +REAL mdata[6]; > > /* NULL */ > status = GdipInvertMatrix(NULL); > @@ -141,11 +154,9 @@ static void test_invert(void) > status = GdipInvertMatrix(matrix); > expect(Ok, status); > > -GdipCreateMatrix2(1.0/9.0, 2.0/9.0, 4.0/9.0, -1.0/9.0, -2.0, -1.0, > &inverted); > -GdipIsMatrixEqual(matrix, inverted, &equal); > -expect(TRUE, equal); > +GdipGetMatrixElements(matrix, mdata); > +expect(TRUE, m_equalf(mdata, minverted)); > Why are you creating a new function that allows tolerance when you control the matrix you're comparing it to? Allowing slop is acceptable in some circumstances, but not in this case, when there is one exact value (or matrix of values) returned. -- James Hawkins