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