SkPathOpsTypes.cpp revision 570863f2e22b8ea7d7c504bd15e4f766af097df2
107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 7cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#include "SkFloatBits.h" 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsTypes.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ 11cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com// FIXME: move to SkFloatBits.h 124fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comstatic bool equal_ulps(float a, float b, int epsilon) { 13570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 14570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return false; 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int aBits = SkFloatAs2sCompliment(a); 17570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int bBits = SkFloatAs2sCompliment(b); 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // Find the difference in ULPs. 19570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return aBits < bBits + epsilon && bBits < aBits + epsilon; 20570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 21570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 22570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.comstatic bool not_equal_ulps(float a, float b, int epsilon) { 23570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 24570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return false; 25570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 26570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int aBits = SkFloatAs2sCompliment(a); 27570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int bBits = SkFloatAs2sCompliment(b); 28570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // Find the difference in ULPs. 29570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return aBits >= bBits + epsilon || bBits >= aBits + epsilon; 3007e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com} 3107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com 324fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comstatic bool less_ulps(float a, float b, int epsilon) { 33570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 34570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return false; 35fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 36570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int aBits = SkFloatAs2sCompliment(a); 37570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int bBits = SkFloatAs2sCompliment(b); 38fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // Find the difference in ULPs. 39570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return aBits <= bBits - epsilon; 40570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 41570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 42570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.comstatic bool less_or_equal_ulps(float a, float b, int epsilon) { 43570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 44570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return false; 45570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 46570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int aBits = SkFloatAs2sCompliment(a); 47570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int bBits = SkFloatAs2sCompliment(b); 48570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // Find the difference in ULPs. 49570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return aBits < bBits + epsilon; 50570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 51570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 52570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// equality using the same error term as between 53570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool AlmostBequalUlps(float a, float b) { 54570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 2; 55570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return equal_ulps(a, b, UlpsEpsilon); 56fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 57fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 584fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.combool AlmostEqualUlps(float a, float b) { 5907e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com const int UlpsEpsilon = 16; 604fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return equal_ulps(a, b, UlpsEpsilon); 6107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com} 6207e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com 63570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool NotAlmostEqualUlps(float a, float b) { 64570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 16; 65570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return not_equal_ulps(a, b, UlpsEpsilon); 66570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 67570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 684fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.combool RoughlyEqualUlps(float a, float b) { 6907e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com const int UlpsEpsilon = 256; 704fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return equal_ulps(a, b, UlpsEpsilon); 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 73fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.combool AlmostBetweenUlps(float a, float b, float c) { 74570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 2; 75570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return a <= c ? less_or_equal_ulps(a, b, UlpsEpsilon) && less_or_equal_ulps(b, c, UlpsEpsilon) 76570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com : less_or_equal_ulps(b, a, UlpsEpsilon) && less_or_equal_ulps(c, b, UlpsEpsilon); 77570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 78570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 79570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool AlmostLessUlps(float a, float b) { 80570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 16; 81570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return less_ulps(a, b, UlpsEpsilon); 82570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 83570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 84570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool AlmostLessOrEqualUlps(float a, float b) { 85570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 16; 86570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return less_or_equal_ulps(a, b, UlpsEpsilon); 87fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 88fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 894fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comint UlpsDistance(float a, float b) { 90570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 91570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return SK_MaxS32; 92570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 934fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkFloatIntUnion floatIntA, floatIntB; 944fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com floatIntA.fFloat = a; 954fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com floatIntB.fFloat = b; 964fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // Different signs means they do not match. 974fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { 984fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // Check for equality to make sure +0 == -0 994fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return a == b ? 0 : SK_MaxS32; 1004fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 1014fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // Find the difference in ULPs. 1024fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt); 1034fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com} 1044fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com 10507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// cube root approximation using bit hack for 64-bit float 10607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// adapted from Kahan's cbrt 107cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.comstatic double cbrt_5d(double d) { 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const unsigned int B1 = 715094163; 10907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t = 0.0; 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com unsigned int* pt = (unsigned int*) &t; 11107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com unsigned int* px = (unsigned int*) &d; 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com pt[1] = px[1] / 3 + B1; 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return t; 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// iterative cube root approximation using Halley's method (double) 117cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.comstatic double cbrta_halleyd(const double a, const double R) { 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double a3 = a * a * a; 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double b = a * (a3 + R + R) / (a3 + a3 + R); 12007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return b; 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 12207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 12307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// cube root approximation using 3 iterations of Halley's method (double) 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic double halley_cbrt3d(double d) { 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double a = cbrt_5d(d); 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com a = cbrta_halleyd(a, d); 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com a = cbrta_halleyd(a, d); 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return cbrta_halleyd(a, d); 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 13107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comdouble SkDCubeRoot(double x) { 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_zero_cubed(x)) { 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return 0; 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double result = halley_cbrt3d(fabs(x)); 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (x < 0) { 13707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com result = -result; 13807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 141