MathTest.cpp revision d6a301e9adfe465cbaf682963b3bd43d7fcebedc 
1/*
2 * Copyright 2011 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "Test.h"
9#include "TestClassDef.h"
10#include "SkColorPriv.h"
11#include "SkEndian.h"
12#include "SkFloatBits.h"
13#include "SkFloatingPoint.h"
14#include "SkMathPriv.h"
15#include "SkPoint.h"
16#include "SkRandom.h"
17
18static void test_clz(skiatest::Reporter* reporter) {
19    REPORTER_ASSERT(reporter, 32 == SkCLZ(0));
20    REPORTER_ASSERT(reporter, 31 == SkCLZ(1));
21    REPORTER_ASSERT(reporter, 1 == SkCLZ(1 << 30));
22    REPORTER_ASSERT(reporter, 0 == SkCLZ(~0U));
23
24    SkRandom rand;
25    for (int i = 0; i < 1000; ++i) {
26        uint32_t mask = rand.nextU();
27        // need to get some zeros for testing, but in some obscure way so the
28        // compiler won't "see" that, and work-around calling the functions.
29        mask >>= (mask & 31);
30        int intri = SkCLZ(mask);
31        int porta = SkCLZ_portable(mask);
32        REPORTER_ASSERT(reporter, intri == porta);
33    }
34}
35
36///////////////////////////////////////////////////////////////////////////////
37
38static float sk_fsel(float pred, float result_ge, float result_lt) {
39    return pred >= 0 ? result_ge : result_lt;
40}
41
42static float fast_floor(float x) {
43//    float big = sk_fsel(x, 0x1.0p+23, -0x1.0p+23);
44    float big = sk_fsel(x, (float)(1 << 23), -(float)(1 << 23));
45    return (float)(x + big) - big;
46}
47
48static float std_floor(float x) {
49    return sk_float_floor(x);
50}
51
52static void test_floor_value(skiatest::Reporter* reporter, float value) {
53    float fast = fast_floor(value);
54    float std = std_floor(value);
55    REPORTER_ASSERT(reporter, std == fast);
56//    SkDebugf("value[%1.9f] std[%g] fast[%g] equal[%d]\n",
57//             value, std, fast, std == fast);
58}
59
60static void test_floor(skiatest::Reporter* reporter) {
61    static const float gVals[] = {
62        0, 1, 1.1f, 1.01f, 1.001f, 1.0001f, 1.00001f, 1.000001f, 1.0000001f
63    };
64
65    for (size_t i = 0; i < SK_ARRAY_COUNT(gVals); ++i) {
66        test_floor_value(reporter, gVals[i]);
67//        test_floor_value(reporter, -gVals[i]);
68    }
69}
70
71///////////////////////////////////////////////////////////////////////////////
72
73// test that SkMul16ShiftRound and SkMulDiv255Round return the same result
74static void test_muldivround(skiatest::Reporter* reporter) {
75#if 0
76    // this "complete" test is too slow, so we test a random sampling of it
77
78    for (int a = 0; a <= 32767; ++a) {
79        for (int b = 0; b <= 32767; ++b) {
80            unsigned prod0 = SkMul16ShiftRound(a, b, 8);
81            unsigned prod1 = SkMulDiv255Round(a, b);
82            SkASSERT(prod0 == prod1);
83        }
84    }
85#endif
86
87    SkRandom rand;
88    for (int i = 0; i < 10000; ++i) {
89        unsigned a = rand.nextU() & 0x7FFF;
90        unsigned b = rand.nextU() & 0x7FFF;
91
92        unsigned prod0 = SkMul16ShiftRound(a, b, 8);
93        unsigned prod1 = SkMulDiv255Round(a, b);
94
95        REPORTER_ASSERT(reporter, prod0 == prod1);
96    }
97}
98
99static float float_blend(int src, int dst, float unit) {
100    return dst + (src - dst) * unit;
101}
102
103static int blend31(int src, int dst, int a31) {
104    return dst + ((src - dst) * a31 * 2114 >> 16);
105    //    return dst + ((src - dst) * a31 * 33 >> 10);
106}
107
108static int blend31_slow(int src, int dst, int a31) {
109    int prod = src * a31 + (31 - a31) * dst + 16;
110    prod = (prod + (prod >> 5)) >> 5;
111    return prod;
112}
113
114static int blend31_round(int src, int dst, int a31) {
115    int prod = (src - dst) * a31 + 16;
116    prod = (prod + (prod >> 5)) >> 5;
117    return dst + prod;
118}
119
120static int blend31_old(int src, int dst, int a31) {
121    a31 += a31 >> 4;
122    return dst + ((src - dst) * a31 >> 5);
123}
124
125// suppress unused code warning
126static int (*blend_functions[])(int, int, int) = {
127    blend31,
128    blend31_slow,
129    blend31_round,
130    blend31_old
131};
132
133static void test_blend31() {
134    int failed = 0;
135    int death = 0;
136    if (false) { // avoid bit rot, suppress warning
137        failed = (*blend_functions[0])(0,0,0);
138    }
139    for (int src = 0; src <= 255; src++) {
140        for (int dst = 0; dst <= 255; dst++) {
141            for (int a = 0; a <= 31; a++) {
142//                int r0 = blend31(src, dst, a);
143//                int r0 = blend31_round(src, dst, a);
144//                int r0 = blend31_old(src, dst, a);
145                int r0 = blend31_slow(src, dst, a);
146
147                float f = float_blend(src, dst, a / 31.f);
148                int r1 = (int)f;
149                int r2 = SkScalarRoundToInt(f);
150
151                if (r0 != r1 && r0 != r2) {
152                    SkDebugf("src:%d dst:%d a:%d result:%d float:%g\n",
153                                  src,   dst, a,        r0,      f);
154                    failed += 1;
155                }
156                if (r0 > 255) {
157                    death += 1;
158                    SkDebugf("death src:%d dst:%d a:%d result:%d float:%g\n",
159                                        src,   dst, a,        r0,      f);
160                }
161            }
162        }
163    }
164    SkDebugf("---- failed %d death %d\n", failed, death);
165}
166
167static void test_blend(skiatest::Reporter* reporter) {
168    for (int src = 0; src <= 255; src++) {
169        for (int dst = 0; dst <= 255; dst++) {
170            for (int a = 0; a <= 255; a++) {
171                int r0 = SkAlphaBlend255(src, dst, a);
172                float f1 = float_blend(src, dst, a / 255.f);
173                int r1 = SkScalarRoundToInt(f1);
174
175                if (r0 != r1) {
176                    float diff = sk_float_abs(f1 - r1);
177                    diff = sk_float_abs(diff - 0.5f);
178                    if (diff > (1 / 255.f)) {
179#ifdef SK_DEBUG
180                        SkDebugf("src:%d dst:%d a:%d result:%d float:%g\n",
181                                 src, dst, a, r0, f1);
182#endif
183                        REPORTER_ASSERT(reporter, false);
184                    }
185                }
186            }
187        }
188    }
189}
190
191static int symmetric_fixmul(int a, int b) {
192    int sa = SkExtractSign(a);
193    int sb = SkExtractSign(b);
194
195    a = SkApplySign(a, sa);
196    b = SkApplySign(b, sb);
197
198    int c = (int)(((int64_t)a * b) >> 16);
199    return SkApplySign(c, sa ^ sb);
200}
201
202static void check_length(skiatest::Reporter* reporter,
203                         const SkPoint& p, SkScalar targetLen) {
204    float x = SkScalarToFloat(p.fX);
205    float y = SkScalarToFloat(p.fY);
206    float len = sk_float_sqrt(x*x + y*y);
207
208    len /= SkScalarToFloat(targetLen);
209
210    REPORTER_ASSERT(reporter, len > 0.999f && len < 1.001f);
211}
212
213static float nextFloat(SkRandom& rand) {
214    SkFloatIntUnion data;
215    data.fSignBitInt = rand.nextU();
216    return data.fFloat;
217}
218
219/*  returns true if a == b as resulting from (int)x. Since it is undefined
220 what to do if the float exceeds 2^32-1, we check for that explicitly.
221 */
222static bool equal_float_native_skia(float x, uint32_t ni, uint32_t si) {
223    if (!(x == x)) {    // NAN
224        return ((int32_t)si) == SK_MaxS32 || ((int32_t)si) == SK_MinS32;
225    }
226    // for out of range, C is undefined, but skia always should return NaN32
227    if (x > SK_MaxS32) {
228        return ((int32_t)si) == SK_MaxS32;
229    }
230    if (x < -SK_MaxS32) {
231        return ((int32_t)si) == SK_MinS32;
232    }
233    return si == ni;
234}
235
236static void assert_float_equal(skiatest::Reporter* reporter, const char op[],
237                               float x, uint32_t ni, uint32_t si) {
238    if (!equal_float_native_skia(x, ni, si)) {
239        SkString desc;
240        uint32_t xi = SkFloat2Bits(x);
241        desc.printf("%s float %g bits %x native %x skia %x\n", op, x, xi, ni, si);
242        reporter->reportFailed(desc);
243    }
244}
245
246static void test_float_cast(skiatest::Reporter* reporter, float x) {
247    int ix = (int)x;
248    int iix = SkFloatToIntCast(x);
249    assert_float_equal(reporter, "cast", x, ix, iix);
250}
251
252static void test_float_floor(skiatest::Reporter* reporter, float x) {
253    int ix = (int)floor(x);
254    int iix = SkFloatToIntFloor(x);
255    assert_float_equal(reporter, "floor", x, ix, iix);
256}
257
258static void test_float_round(skiatest::Reporter* reporter, float x) {
259    double xx = x + 0.5;    // need intermediate double to avoid temp loss
260    int ix = (int)floor(xx);
261    int iix = SkFloatToIntRound(x);
262    assert_float_equal(reporter, "round", x, ix, iix);
263}
264
265static void test_float_ceil(skiatest::Reporter* reporter, float x) {
266    int ix = (int)ceil(x);
267    int iix = SkFloatToIntCeil(x);
268    assert_float_equal(reporter, "ceil", x, ix, iix);
269}
270
271static void test_float_conversions(skiatest::Reporter* reporter, float x) {
272    test_float_cast(reporter, x);
273    test_float_floor(reporter, x);
274    test_float_round(reporter, x);
275    test_float_ceil(reporter, x);
276}
277
278static void test_int2float(skiatest::Reporter* reporter, int ival) {
279    float x0 = (float)ival;
280    float x1 = SkIntToFloatCast(ival);
281    float x2 = SkIntToFloatCast_NoOverflowCheck(ival);
282    REPORTER_ASSERT(reporter, x0 == x1);
283    REPORTER_ASSERT(reporter, x0 == x2);
284}
285
286static void unittest_fastfloat(skiatest::Reporter* reporter) {
287    SkRandom rand;
288    size_t i;
289
290    static const float gFloats[] = {
291        0.f, 1.f, 0.5f, 0.499999f, 0.5000001f, 1.f/3,
292        0.000000001f, 1000000000.f,     // doesn't overflow
293        0.0000000001f, 10000000000.f    // does overflow
294    };
295    for (i = 0; i < SK_ARRAY_COUNT(gFloats); i++) {
296        test_float_conversions(reporter, gFloats[i]);
297        test_float_conversions(reporter, -gFloats[i]);
298    }
299
300    for (int outer = 0; outer < 100; outer++) {
301        rand.setSeed(outer);
302        for (i = 0; i < 100000; i++) {
303            float x = nextFloat(rand);
304            test_float_conversions(reporter, x);
305        }
306
307        test_int2float(reporter, 0);
308        test_int2float(reporter, 1);
309        test_int2float(reporter, -1);
310        for (i = 0; i < 100000; i++) {
311            // for now only test ints that are 24bits or less, since we don't
312            // round (down) large ints the same as IEEE...
313            int ival = rand.nextU() & 0xFFFFFF;
314            test_int2float(reporter, ival);
315            test_int2float(reporter, -ival);
316        }
317    }
318}
319
320static float make_zero() {
321    return sk_float_sin(0);
322}
323
324static void unittest_isfinite(skiatest::Reporter* reporter) {
325    float nan = sk_float_asin(2);
326    float inf = 1.0f / make_zero();
327    float big = 3.40282e+038f;
328
329    REPORTER_ASSERT(reporter, !SkScalarIsNaN(inf));
330    REPORTER_ASSERT(reporter, !SkScalarIsNaN(-inf));
331    REPORTER_ASSERT(reporter, !SkScalarIsFinite(inf));
332    REPORTER_ASSERT(reporter, !SkScalarIsFinite(-inf));
333
334    REPORTER_ASSERT(reporter,  SkScalarIsNaN(nan));
335    REPORTER_ASSERT(reporter, !SkScalarIsNaN(big));
336    REPORTER_ASSERT(reporter, !SkScalarIsNaN(-big));
337    REPORTER_ASSERT(reporter, !SkScalarIsNaN(0));
338
339    REPORTER_ASSERT(reporter, !SkScalarIsFinite(nan));
340    REPORTER_ASSERT(reporter,  SkScalarIsFinite(big));
341    REPORTER_ASSERT(reporter,  SkScalarIsFinite(-big));
342    REPORTER_ASSERT(reporter,  SkScalarIsFinite(0));
343}
344
345static void test_muldiv255(skiatest::Reporter* reporter) {
346    for (int a = 0; a <= 255; a++) {
347        for (int b = 0; b <= 255; b++) {
348            int ab = a * b;
349            float s = ab / 255.0f;
350            int round = (int)floorf(s + 0.5f);
351            int trunc = (int)floorf(s);
352
353            int iround = SkMulDiv255Round(a, b);
354            int itrunc = SkMulDiv255Trunc(a, b);
355
356            REPORTER_ASSERT(reporter, iround == round);
357            REPORTER_ASSERT(reporter, itrunc == trunc);
358
359            REPORTER_ASSERT(reporter, itrunc <= iround);
360            REPORTER_ASSERT(reporter, iround <= a);
361            REPORTER_ASSERT(reporter, iround <= b);
362        }
363    }
364}
365
366static void test_muldiv255ceiling(skiatest::Reporter* reporter) {
367    for (int c = 0; c <= 255; c++) {
368        for (int a = 0; a <= 255; a++) {
369            int product = (c * a + 255);
370            int expected_ceiling = (product + (product >> 8)) >> 8;
371            int webkit_ceiling = (c * a + 254) / 255;
372            REPORTER_ASSERT(reporter, expected_ceiling == webkit_ceiling);
373            int skia_ceiling = SkMulDiv255Ceiling(c, a);
374            REPORTER_ASSERT(reporter, skia_ceiling == webkit_ceiling);
375        }
376    }
377}
378
379static void test_copysign(skiatest::Reporter* reporter) {
380    static const int32_t gTriples[] = {
381        // x, y, expected result
382        0, 0, 0,
383        0, 1, 0,
384        0, -1, 0,
385        1, 0, 1,
386        1, 1, 1,
387        1, -1, -1,
388        -1, 0, 1,
389        -1, 1, 1,
390        -1, -1, -1,
391    };
392    for (size_t i = 0; i < SK_ARRAY_COUNT(gTriples); i += 3) {
393        REPORTER_ASSERT(reporter,
394                        SkCopySign32(gTriples[i], gTriples[i+1]) == gTriples[i+2]);
395        float x = (float)gTriples[i];
396        float y = (float)gTriples[i+1];
397        float expected = (float)gTriples[i+2];
398        REPORTER_ASSERT(reporter, sk_float_copysign(x, y) == expected);
399    }
400
401    SkRandom rand;
402    for (int j = 0; j < 1000; j++) {
403        int ix = rand.nextS();
404        REPORTER_ASSERT(reporter, SkCopySign32(ix, ix) == ix);
405        REPORTER_ASSERT(reporter, SkCopySign32(ix, -ix) == -ix);
406        REPORTER_ASSERT(reporter, SkCopySign32(-ix, ix) == ix);
407        REPORTER_ASSERT(reporter, SkCopySign32(-ix, -ix) == -ix);
408
409        SkScalar sx = rand.nextSScalar1();
410        REPORTER_ASSERT(reporter, SkScalarCopySign(sx, sx) == sx);
411        REPORTER_ASSERT(reporter, SkScalarCopySign(sx, -sx) == -sx);
412        REPORTER_ASSERT(reporter, SkScalarCopySign(-sx, sx) == sx);
413        REPORTER_ASSERT(reporter, SkScalarCopySign(-sx, -sx) == -sx);
414    }
415}
416
417DEF_TEST(Math, reporter) {
418    int         i;
419    SkRandom    rand;
420
421    // these should assert
422#if 0
423    SkToS8(128);
424    SkToS8(-129);
425    SkToU8(256);
426    SkToU8(-5);
427
428    SkToS16(32768);
429    SkToS16(-32769);
430    SkToU16(65536);
431    SkToU16(-5);
432
433    if (sizeof(size_t) > 4) {
434        SkToS32(4*1024*1024);
435        SkToS32(-4*1024*1024);
436        SkToU32(5*1024*1024);
437        SkToU32(-5);
438    }
439#endif
440
441    test_muldiv255(reporter);
442    test_muldiv255ceiling(reporter);
443    test_copysign(reporter);
444
445    {
446        SkScalar x = SK_ScalarNaN;
447        REPORTER_ASSERT(reporter, SkScalarIsNaN(x));
448    }
449
450    for (i = 0; i < 1000; i++) {
451        int value = rand.nextS16();
452        int max = rand.nextU16();
453
454        int clamp = SkClampMax(value, max);
455        int clamp2 = value < 0 ? 0 : (value > max ? max : value);
456        REPORTER_ASSERT(reporter, clamp == clamp2);
457    }
458
459    for (i = 0; i < 10000; i++) {
460        SkPoint p;
461
462        // These random values are being treated as 32-bit-patterns, not as
463        // ints; calling SkIntToScalar() here produces crashes.
464        p.setLength((SkScalar) rand.nextS(),
465                    (SkScalar) rand.nextS(),
466                    SK_Scalar1);
467        check_length(reporter, p, SK_Scalar1);
468        p.setLength((SkScalar) (rand.nextS() >> 13),
469                    (SkScalar) (rand.nextS() >> 13),
470                    SK_Scalar1);
471        check_length(reporter, p, SK_Scalar1);
472    }
473
474    {
475        SkFixed result = SkFixedDiv(100, 100);
476        REPORTER_ASSERT(reporter, result == SK_Fixed1);
477        result = SkFixedDiv(1, SK_Fixed1);
478        REPORTER_ASSERT(reporter, result == 1);
479    }
480
481    unittest_fastfloat(reporter);
482    unittest_isfinite(reporter);
483
484    for (i = 0; i < 10000; i++) {
485        SkFixed numer = rand.nextS();
486        SkFixed denom = rand.nextS();
487        SkFixed result = SkFixedDiv(numer, denom);
488        int64_t check = ((int64_t)numer << 16) / denom;
489
490        (void)SkCLZ(numer);
491        (void)SkCLZ(denom);
492
493        REPORTER_ASSERT(reporter, result != (SkFixed)SK_NaN32);
494        if (check > SK_MaxS32) {
495            check = SK_MaxS32;
496        } else if (check < -SK_MaxS32) {
497            check = SK_MinS32;
498        }
499        REPORTER_ASSERT(reporter, result == (int32_t)check);
500
501        // make them <= 2^24, so we don't overflow in fixmul
502        numer = numer << 8 >> 8;
503        denom = denom << 8 >> 8;
504
505        result = SkFixedMul(numer, denom);
506        SkFixed r2 = symmetric_fixmul(numer, denom);
507        //        SkASSERT(result == r2);
508
509        result = SkFixedMul(numer, numer);
510        r2 = SkFixedSquare(numer);
511        REPORTER_ASSERT(reporter, result == r2);
512    }
513
514    test_blend(reporter);
515
516    if (false) test_floor(reporter);
517
518    // disable for now
519    if (false) test_blend31();  // avoid bit rot, suppress warning
520
521    test_muldivround(reporter);
522    test_clz(reporter);
523}
524
525template <typename T> struct PairRec {
526    T   fYin;
527    T   fYang;
528};
529
530DEF_TEST(TestEndian, reporter) {
531    static const PairRec<uint16_t> g16[] = {
532        { 0x0,      0x0     },
533        { 0xFFFF,   0xFFFF  },
534        { 0x1122,   0x2211  },
535    };
536    static const PairRec<uint32_t> g32[] = {
537        { 0x0,          0x0         },
538        { 0xFFFFFFFF,   0xFFFFFFFF  },
539        { 0x11223344,   0x44332211  },
540    };
541    static const PairRec<uint64_t> g64[] = {
542        { 0x0,      0x0                             },
543        { 0xFFFFFFFFFFFFFFFFULL,  0xFFFFFFFFFFFFFFFFULL  },
544        { 0x1122334455667788ULL,  0x8877665544332211ULL  },
545    };
546
547    REPORTER_ASSERT(reporter, 0x1122 == SkTEndianSwap16<0x2211>::value);
548    REPORTER_ASSERT(reporter, 0x11223344 == SkTEndianSwap32<0x44332211>::value);
549    REPORTER_ASSERT(reporter, 0x1122334455667788ULL == SkTEndianSwap64<0x8877665544332211ULL>::value);
550
551    for (size_t i = 0; i < SK_ARRAY_COUNT(g16); ++i) {
552        REPORTER_ASSERT(reporter, g16[i].fYang == SkEndianSwap16(g16[i].fYin));
553    }
554    for (size_t i = 0; i < SK_ARRAY_COUNT(g32); ++i) {
555        REPORTER_ASSERT(reporter, g32[i].fYang == SkEndianSwap32(g32[i].fYin));
556    }
557    for (size_t i = 0; i < SK_ARRAY_COUNT(g64); ++i) {
558        REPORTER_ASSERT(reporter, g64[i].fYang == SkEndianSwap64(g64[i].fYin));
559    }
560}
561
562template <typename T>
563static void test_divmod(skiatest::Reporter* r) {
564    const struct {
565        T numer;
566        T denom;
567    } kEdgeCases[] = {
568        {(T)17, (T)17},
569        {(T)17, (T)4},
570        {(T)0,  (T)17},
571        // For unsigned T these negatives are just some large numbers.  Doesn't hurt to test them.
572        {(T)-17, (T)-17},
573        {(T)-17, (T)4},
574        {(T)17,  (T)-4},
575        {(T)-17, (T)-4},
576    };
577
578    for (size_t i = 0; i < SK_ARRAY_COUNT(kEdgeCases); i++) {
579        const T numer = kEdgeCases[i].numer;
580        const T denom = kEdgeCases[i].denom;
581        T div, mod;
582        SkTDivMod(numer, denom, &div, &mod);
583        REPORTER_ASSERT(r, numer/denom == div);
584        REPORTER_ASSERT(r, numer%denom == mod);
585    }
586
587    SkRandom rand;
588    for (size_t i = 0; i < 10000; i++) {
589        const T numer = (T)rand.nextS();
590        T denom = 0;
591        while (0 == denom) {
592            denom = (T)rand.nextS();
593        }
594        T div, mod;
595        SkTDivMod(numer, denom, &div, &mod);
596        REPORTER_ASSERT(r, numer/denom == div);
597        REPORTER_ASSERT(r, numer%denom == mod);
598    }
599}
600
601DEF_TEST(divmod_u8, r) {
602    test_divmod<uint8_t>(r);
603}
604
605DEF_TEST(divmod_u16, r) {
606    test_divmod<uint16_t>(r);
607}
608
609DEF_TEST(divmod_u32, r) {
610    test_divmod<uint32_t>(r);
611}
612
613DEF_TEST(divmod_u64, r) {
614    test_divmod<uint64_t>(r);
615}
616
617DEF_TEST(divmod_s8, r) {
618    test_divmod<int8_t>(r);
619}
620
621DEF_TEST(divmod_s16, r) {
622    test_divmod<int16_t>(r);
623}
624
625DEF_TEST(divmod_s32, r) {
626    test_divmod<int32_t>(r);
627}
628
629DEF_TEST(divmod_s64, r) {
630    test_divmod<int64_t>(r);
631}
632