1 /* 2 * Copyright 2012 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 #include "SkArenaAlloc.h" 8 #include "SkFloatBits.h" 9 #include "SkOpCoincidence.h" 10 #include "SkPathOpsTypes.h" 11 12 static bool arguments_denormalized(float a, float b, int epsilon) { 13 float denormalizedCheck = FLT_EPSILON * epsilon / 2; 14 return fabsf(a) <= denormalizedCheck && fabsf(b) <= denormalizedCheck; 15 } 16 17 // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ 18 // FIXME: move to SkFloatBits.h 19 static bool equal_ulps(float a, float b, int epsilon, int depsilon) { 20 if (arguments_denormalized(a, b, depsilon)) { 21 return true; 22 } 23 int aBits = SkFloatAs2sCompliment(a); 24 int bBits = SkFloatAs2sCompliment(b); 25 // Find the difference in ULPs. 26 return aBits < bBits + epsilon && bBits < aBits + epsilon; 27 } 28 29 static bool equal_ulps_no_normal_check(float a, float b, int epsilon, int depsilon) { 30 int aBits = SkFloatAs2sCompliment(a); 31 int bBits = SkFloatAs2sCompliment(b); 32 // Find the difference in ULPs. 33 return aBits < bBits + epsilon && bBits < aBits + epsilon; 34 } 35 36 static bool equal_ulps_pin(float a, float b, int epsilon, int depsilon) { 37 if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 38 return false; 39 } 40 if (arguments_denormalized(a, b, depsilon)) { 41 return true; 42 } 43 int aBits = SkFloatAs2sCompliment(a); 44 int bBits = SkFloatAs2sCompliment(b); 45 // Find the difference in ULPs. 46 return aBits < bBits + epsilon && bBits < aBits + epsilon; 47 } 48 49 static bool d_equal_ulps(float a, float b, int epsilon) { 50 int aBits = SkFloatAs2sCompliment(a); 51 int bBits = SkFloatAs2sCompliment(b); 52 // Find the difference in ULPs. 53 return aBits < bBits + epsilon && bBits < aBits + epsilon; 54 } 55 56 static bool not_equal_ulps(float a, float b, int epsilon) { 57 if (arguments_denormalized(a, b, epsilon)) { 58 return false; 59 } 60 int aBits = SkFloatAs2sCompliment(a); 61 int bBits = SkFloatAs2sCompliment(b); 62 // Find the difference in ULPs. 63 return aBits >= bBits + epsilon || bBits >= aBits + epsilon; 64 } 65 66 static bool not_equal_ulps_pin(float a, float b, int epsilon) { 67 if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 68 return false; 69 } 70 if (arguments_denormalized(a, b, epsilon)) { 71 return false; 72 } 73 int aBits = SkFloatAs2sCompliment(a); 74 int bBits = SkFloatAs2sCompliment(b); 75 // Find the difference in ULPs. 76 return aBits >= bBits + epsilon || bBits >= aBits + epsilon; 77 } 78 79 static bool d_not_equal_ulps(float a, float b, int epsilon) { 80 int aBits = SkFloatAs2sCompliment(a); 81 int bBits = SkFloatAs2sCompliment(b); 82 // Find the difference in ULPs. 83 return aBits >= bBits + epsilon || bBits >= aBits + epsilon; 84 } 85 86 static bool less_ulps(float a, float b, int epsilon) { 87 if (arguments_denormalized(a, b, epsilon)) { 88 return a <= b - FLT_EPSILON * epsilon; 89 } 90 int aBits = SkFloatAs2sCompliment(a); 91 int bBits = SkFloatAs2sCompliment(b); 92 // Find the difference in ULPs. 93 return aBits <= bBits - epsilon; 94 } 95 96 static bool less_or_equal_ulps(float a, float b, int epsilon) { 97 if (arguments_denormalized(a, b, epsilon)) { 98 return a < b + FLT_EPSILON * epsilon; 99 } 100 int aBits = SkFloatAs2sCompliment(a); 101 int bBits = SkFloatAs2sCompliment(b); 102 // Find the difference in ULPs. 103 return aBits < bBits + epsilon; 104 } 105 106 // equality using the same error term as between 107 bool AlmostBequalUlps(float a, float b) { 108 const int UlpsEpsilon = 2; 109 return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); 110 } 111 112 bool AlmostPequalUlps(float a, float b) { 113 const int UlpsEpsilon = 8; 114 return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); 115 } 116 117 bool AlmostDequalUlps(float a, float b) { 118 const int UlpsEpsilon = 16; 119 return d_equal_ulps(a, b, UlpsEpsilon); 120 } 121 122 bool AlmostDequalUlps(double a, double b) { 123 return AlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 124 } 125 126 bool AlmostEqualUlps(float a, float b) { 127 const int UlpsEpsilon = 16; 128 return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); 129 } 130 131 bool AlmostEqualUlpsNoNormalCheck(float a, float b) { 132 const int UlpsEpsilon = 16; 133 return equal_ulps_no_normal_check(a, b, UlpsEpsilon, UlpsEpsilon); 134 } 135 136 bool AlmostEqualUlps_Pin(float a, float b) { 137 const int UlpsEpsilon = 16; 138 return equal_ulps_pin(a, b, UlpsEpsilon, UlpsEpsilon); 139 } 140 141 bool NotAlmostEqualUlps(float a, float b) { 142 const int UlpsEpsilon = 16; 143 return not_equal_ulps(a, b, UlpsEpsilon); 144 } 145 146 bool NotAlmostEqualUlps_Pin(float a, float b) { 147 const int UlpsEpsilon = 16; 148 return not_equal_ulps_pin(a, b, UlpsEpsilon); 149 } 150 151 bool NotAlmostDequalUlps(float a, float b) { 152 const int UlpsEpsilon = 16; 153 return d_not_equal_ulps(a, b, UlpsEpsilon); 154 } 155 156 bool RoughlyEqualUlps(float a, float b) { 157 const int UlpsEpsilon = 256; 158 const int DUlpsEpsilon = 1024; 159 return equal_ulps(a, b, UlpsEpsilon, DUlpsEpsilon); 160 } 161 162 bool AlmostBetweenUlps(float a, float b, float c) { 163 const int UlpsEpsilon = 2; 164 return a <= c ? less_or_equal_ulps(a, b, UlpsEpsilon) && less_or_equal_ulps(b, c, UlpsEpsilon) 165 : less_or_equal_ulps(b, a, UlpsEpsilon) && less_or_equal_ulps(c, b, UlpsEpsilon); 166 } 167 168 bool AlmostLessUlps(float a, float b) { 169 const int UlpsEpsilon = 16; 170 return less_ulps(a, b, UlpsEpsilon); 171 } 172 173 bool AlmostLessOrEqualUlps(float a, float b) { 174 const int UlpsEpsilon = 16; 175 return less_or_equal_ulps(a, b, UlpsEpsilon); 176 } 177 178 int UlpsDistance(float a, float b) { 179 SkFloatIntUnion floatIntA, floatIntB; 180 floatIntA.fFloat = a; 181 floatIntB.fFloat = b; 182 // Different signs means they do not match. 183 if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { 184 // Check for equality to make sure +0 == -0 185 return a == b ? 0 : SK_MaxS32; 186 } 187 // Find the difference in ULPs. 188 return SkTAbs(floatIntA.fSignBitInt - floatIntB.fSignBitInt); 189 } 190 191 // cube root approximation using bit hack for 64-bit float 192 // adapted from Kahan's cbrt 193 static double cbrt_5d(double d) { 194 const unsigned int B1 = 715094163; 195 double t = 0.0; 196 unsigned int* pt = (unsigned int*) &t; 197 unsigned int* px = (unsigned int*) &d; 198 pt[1] = px[1] / 3 + B1; 199 return t; 200 } 201 202 // iterative cube root approximation using Halley's method (double) 203 static double cbrta_halleyd(const double a, const double R) { 204 const double a3 = a * a * a; 205 const double b = a * (a3 + R + R) / (a3 + a3 + R); 206 return b; 207 } 208 209 // cube root approximation using 3 iterations of Halley's method (double) 210 static double halley_cbrt3d(double d) { 211 double a = cbrt_5d(d); 212 a = cbrta_halleyd(a, d); 213 a = cbrta_halleyd(a, d); 214 return cbrta_halleyd(a, d); 215 } 216 217 double SkDCubeRoot(double x) { 218 if (approximately_zero_cubed(x)) { 219 return 0; 220 } 221 double result = halley_cbrt3d(fabs(x)); 222 if (x < 0) { 223 result = -result; 224 } 225 return result; 226 } 227 228 SkOpGlobalState::SkOpGlobalState(SkOpContourHead* head, 229 SkArenaAlloc* allocator 230 SkDEBUGPARAMS(bool debugSkipAssert) 231 SkDEBUGPARAMS(const char* testName)) 232 : fAllocator(allocator) 233 , fCoincidence(nullptr) 234 , fContourHead(head) 235 , fNested(0) 236 , fWindingFailed(false) 237 , fPhase(SkOpPhase::kIntersecting) 238 SkDEBUGPARAMS(fDebugTestName(testName)) 239 SkDEBUGPARAMS(fAngleID(0)) 240 SkDEBUGPARAMS(fCoinID(0)) 241 SkDEBUGPARAMS(fContourID(0)) 242 SkDEBUGPARAMS(fPtTID(0)) 243 SkDEBUGPARAMS(fSegmentID(0)) 244 SkDEBUGPARAMS(fSpanID(0)) 245 SkDEBUGPARAMS(fDebugSkipAssert(debugSkipAssert)) { 246 #if DEBUG_T_SECT_LOOP_COUNT 247 debugResetLoopCounts(); 248 #endif 249 #if DEBUG_COIN 250 fPreviousFuncName = nullptr; 251 #endif 252 } 253
