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 */ 7c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby#include "SkArenaAlloc.h" 8cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com#include "SkFloatBits.h" 927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark#include "SkOpCoincidence.h" 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsTypes.h" 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 127eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comstatic bool arguments_denormalized(float a, float b, int epsilon) { 13a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com float denormalizedCheck = FLT_EPSILON * epsilon / 2; 14a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return fabsf(a) <= denormalizedCheck && fabsf(b) <= denormalizedCheck; 157eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 167eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ 18cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com// FIXME: move to SkFloatBits.h 19a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.comstatic bool equal_ulps(float a, float b, int epsilon, int depsilon) { 20b669300a9753893ef900207c38aeff2d467764e5caryclark if (arguments_denormalized(a, b, depsilon)) { 21b669300a9753893ef900207c38aeff2d467764e5caryclark return true; 22b669300a9753893ef900207c38aeff2d467764e5caryclark } 23b669300a9753893ef900207c38aeff2d467764e5caryclark int aBits = SkFloatAs2sCompliment(a); 24b669300a9753893ef900207c38aeff2d467764e5caryclark int bBits = SkFloatAs2sCompliment(b); 25b669300a9753893ef900207c38aeff2d467764e5caryclark // Find the difference in ULPs. 26b669300a9753893ef900207c38aeff2d467764e5caryclark return aBits < bBits + epsilon && bBits < aBits + epsilon; 27b669300a9753893ef900207c38aeff2d467764e5caryclark} 28b669300a9753893ef900207c38aeff2d467764e5caryclark 2955888e44171ffd48b591d19256884a969fe4da17caryclarkstatic bool equal_ulps_no_normal_check(float a, float b, int epsilon, int depsilon) { 3055888e44171ffd48b591d19256884a969fe4da17caryclark int aBits = SkFloatAs2sCompliment(a); 3155888e44171ffd48b591d19256884a969fe4da17caryclark int bBits = SkFloatAs2sCompliment(b); 3255888e44171ffd48b591d19256884a969fe4da17caryclark // Find the difference in ULPs. 3355888e44171ffd48b591d19256884a969fe4da17caryclark return aBits < bBits + epsilon && bBits < aBits + epsilon; 3455888e44171ffd48b591d19256884a969fe4da17caryclark} 3555888e44171ffd48b591d19256884a969fe4da17caryclark 36b669300a9753893ef900207c38aeff2d467764e5caryclarkstatic bool equal_ulps_pin(float a, float b, int epsilon, int depsilon) { 37570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 38570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return false; 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 40a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (arguments_denormalized(a, b, depsilon)) { 417eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return true; 427eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 437eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com int aBits = SkFloatAs2sCompliment(a); 447eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com int bBits = SkFloatAs2sCompliment(b); 457eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // Find the difference in ULPs. 467eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return aBits < bBits + epsilon && bBits < aBits + epsilon; 477eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 487eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 497eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comstatic bool d_equal_ulps(float a, float b, int epsilon) { 50570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int aBits = SkFloatAs2sCompliment(a); 51570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int bBits = SkFloatAs2sCompliment(b); 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // Find the difference in ULPs. 53570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return aBits < bBits + epsilon && bBits < aBits + epsilon; 54570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 55570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 56570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.comstatic bool not_equal_ulps(float a, float b, int epsilon) { 57b669300a9753893ef900207c38aeff2d467764e5caryclark if (arguments_denormalized(a, b, epsilon)) { 58b669300a9753893ef900207c38aeff2d467764e5caryclark return false; 59b669300a9753893ef900207c38aeff2d467764e5caryclark } 60b669300a9753893ef900207c38aeff2d467764e5caryclark int aBits = SkFloatAs2sCompliment(a); 61b669300a9753893ef900207c38aeff2d467764e5caryclark int bBits = SkFloatAs2sCompliment(b); 62b669300a9753893ef900207c38aeff2d467764e5caryclark // Find the difference in ULPs. 63b669300a9753893ef900207c38aeff2d467764e5caryclark return aBits >= bBits + epsilon || bBits >= aBits + epsilon; 64b669300a9753893ef900207c38aeff2d467764e5caryclark} 65b669300a9753893ef900207c38aeff2d467764e5caryclark 66b669300a9753893ef900207c38aeff2d467764e5caryclarkstatic bool not_equal_ulps_pin(float a, float b, int epsilon) { 67570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { 68570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return false; 69570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 707eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (arguments_denormalized(a, b, epsilon)) { 717eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return false; 727eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 737eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com int aBits = SkFloatAs2sCompliment(a); 747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com int bBits = SkFloatAs2sCompliment(b); 757eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // Find the difference in ULPs. 767eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return aBits >= bBits + epsilon || bBits >= aBits + epsilon; 777eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 787eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 797eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comstatic bool d_not_equal_ulps(float a, float b, int epsilon) { 80570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int aBits = SkFloatAs2sCompliment(a); 81570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int bBits = SkFloatAs2sCompliment(b); 82570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // Find the difference in ULPs. 83570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return aBits >= bBits + epsilon || bBits >= aBits + epsilon; 8407e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com} 8507e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com 864fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comstatic bool less_ulps(float a, float b, int epsilon) { 877eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (arguments_denormalized(a, b, epsilon)) { 887eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return a <= b - FLT_EPSILON * epsilon; 897eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 90570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int aBits = SkFloatAs2sCompliment(a); 91570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int bBits = SkFloatAs2sCompliment(b); 92fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // Find the difference in ULPs. 93570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return aBits <= bBits - epsilon; 94570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 95570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 96570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.comstatic bool less_or_equal_ulps(float a, float b, int epsilon) { 977eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (arguments_denormalized(a, b, epsilon)) { 987eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return a < b + FLT_EPSILON * epsilon; 997eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 100570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int aBits = SkFloatAs2sCompliment(a); 101570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int bBits = SkFloatAs2sCompliment(b); 102570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // Find the difference in ULPs. 103570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return aBits < bBits + epsilon; 104570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 105570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 106570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com// equality using the same error term as between 107570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool AlmostBequalUlps(float a, float b) { 108570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 2; 109a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); 110a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com} 111a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 112a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.combool AlmostPequalUlps(float a, float b) { 113a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com const int UlpsEpsilon = 8; 114a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); 115fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 116fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 1177eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.combool AlmostDequalUlps(float a, float b) { 1187eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com const int UlpsEpsilon = 16; 1197eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return d_equal_ulps(a, b, UlpsEpsilon); 1207eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 1217eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 1222db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.orgbool AlmostDequalUlps(double a, double b) { 123b9042d206ab8762429c61160383094360fb04c7aCary Clark if (fabs(a) < SK_ScalarMax && fabs(b) < SK_ScalarMax) { 124b9042d206ab8762429c61160383094360fb04c7aCary Clark return AlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 125b9042d206ab8762429c61160383094360fb04c7aCary Clark } 126b9042d206ab8762429c61160383094360fb04c7aCary Clark return fabs(a - b) / SkTMax(fabs(a), fabs(b)) < FLT_EPSILON * 16; 1272db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org} 1282db7fe7d3b7ee875e1099a22f0af17520696f5d7commit-bot@chromium.org 1294fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.combool AlmostEqualUlps(float a, float b) { 13007e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com const int UlpsEpsilon = 16; 131a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon); 13207e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com} 13307e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com 13455888e44171ffd48b591d19256884a969fe4da17caryclarkbool AlmostEqualUlpsNoNormalCheck(float a, float b) { 13555888e44171ffd48b591d19256884a969fe4da17caryclark const int UlpsEpsilon = 16; 13655888e44171ffd48b591d19256884a969fe4da17caryclark return equal_ulps_no_normal_check(a, b, UlpsEpsilon, UlpsEpsilon); 13755888e44171ffd48b591d19256884a969fe4da17caryclark} 13855888e44171ffd48b591d19256884a969fe4da17caryclark 139b669300a9753893ef900207c38aeff2d467764e5caryclarkbool AlmostEqualUlps_Pin(float a, float b) { 140b669300a9753893ef900207c38aeff2d467764e5caryclark const int UlpsEpsilon = 16; 141b669300a9753893ef900207c38aeff2d467764e5caryclark return equal_ulps_pin(a, b, UlpsEpsilon, UlpsEpsilon); 142b669300a9753893ef900207c38aeff2d467764e5caryclark} 143b669300a9753893ef900207c38aeff2d467764e5caryclark 144570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool NotAlmostEqualUlps(float a, float b) { 145570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 16; 146570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return not_equal_ulps(a, b, UlpsEpsilon); 147570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 148570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 149b669300a9753893ef900207c38aeff2d467764e5caryclarkbool NotAlmostEqualUlps_Pin(float a, float b) { 150b669300a9753893ef900207c38aeff2d467764e5caryclark const int UlpsEpsilon = 16; 151b669300a9753893ef900207c38aeff2d467764e5caryclark return not_equal_ulps_pin(a, b, UlpsEpsilon); 152b669300a9753893ef900207c38aeff2d467764e5caryclark} 153b669300a9753893ef900207c38aeff2d467764e5caryclark 1547eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.combool NotAlmostDequalUlps(float a, float b) { 1557eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com const int UlpsEpsilon = 16; 1567eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return d_not_equal_ulps(a, b, UlpsEpsilon); 1577eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 1587eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 1594fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.combool RoughlyEqualUlps(float a, float b) { 16007e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com const int UlpsEpsilon = 256; 161a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com const int DUlpsEpsilon = 1024; 162a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return equal_ulps(a, b, UlpsEpsilon, DUlpsEpsilon); 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 16407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 165fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.combool AlmostBetweenUlps(float a, float b, float c) { 166570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 2; 167570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return a <= c ? less_or_equal_ulps(a, b, UlpsEpsilon) && less_or_equal_ulps(b, c, UlpsEpsilon) 168570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com : less_or_equal_ulps(b, a, UlpsEpsilon) && less_or_equal_ulps(c, b, UlpsEpsilon); 169570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 170570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 171570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool AlmostLessUlps(float a, float b) { 172570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 16; 173570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return less_ulps(a, b, UlpsEpsilon); 174570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 175570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 176570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool AlmostLessOrEqualUlps(float a, float b) { 177570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com const int UlpsEpsilon = 16; 178570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return less_or_equal_ulps(a, b, UlpsEpsilon); 179fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 180fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 1814fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comint UlpsDistance(float a, float b) { 1824fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkFloatIntUnion floatIntA, floatIntB; 1834fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com floatIntA.fFloat = a; 1844fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com floatIntB.fFloat = b; 1854fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // Different signs means they do not match. 1864fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { 1874fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // Check for equality to make sure +0 == -0 1884fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return a == b ? 0 : SK_MaxS32; 1894fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 1904fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // Find the difference in ULPs. 19160e0fee6d4acff638ccc9670c4055aced529a7a0bungeman return SkTAbs(floatIntA.fSignBitInt - floatIntB.fSignBitInt); 1924fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com} 1934fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com 19407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// cube root approximation using bit hack for 64-bit float 19507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// adapted from Kahan's cbrt 196cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.comstatic double cbrt_5d(double d) { 19707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const unsigned int B1 = 715094163; 19807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t = 0.0; 19907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com unsigned int* pt = (unsigned int*) &t; 20007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com unsigned int* px = (unsigned int*) &d; 20107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com pt[1] = px[1] / 3 + B1; 20207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return t; 20307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 20407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 20507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// iterative cube root approximation using Halley's method (double) 206cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.comstatic double cbrta_halleyd(const double a, const double R) { 20707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double a3 = a * a * a; 20807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double b = a * (a3 + R + R) / (a3 + a3 + R); 20907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return b; 21007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 21107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 21207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// cube root approximation using 3 iterations of Halley's method (double) 21307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic double halley_cbrt3d(double d) { 21407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double a = cbrt_5d(d); 21507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com a = cbrta_halleyd(a, d); 21607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com a = cbrta_halleyd(a, d); 21707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return cbrta_halleyd(a, d); 21807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 21907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 22007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comdouble SkDCubeRoot(double x) { 22107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_zero_cubed(x)) { 22207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return 0; 22307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 22407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double result = halley_cbrt3d(fabs(x)); 22507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (x < 0) { 22607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com result = -result; 22707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 22807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 22907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 23027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 23155888e44171ffd48b591d19256884a969fe4da17caryclarkSkOpGlobalState::SkOpGlobalState(SkOpContourHead* head, 232c3cc5fa6de0a8237d9241dbf3e6c0786a9040069Herb Derby SkArenaAlloc* allocator 233dae6b97705fde08958b1a36fa6ce685d28fc692ccaryclark SkDEBUGPARAMS(bool debugSkipAssert) 234d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark SkDEBUGPARAMS(const char* testName)) 23555888e44171ffd48b591d19256884a969fe4da17caryclark : fAllocator(allocator) 23655888e44171ffd48b591d19256884a969fe4da17caryclark , fCoincidence(nullptr) 23727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark , fContourHead(head) 23827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark , fNested(0) 23927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark , fWindingFailed(false) 240ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark , fPhase(SkOpPhase::kIntersecting) 241d4349723fac9c0fd4dcf8c275fb7c756bdfdff7bcaryclark SkDEBUGPARAMS(fDebugTestName(testName)) 24227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkDEBUGPARAMS(fAngleID(0)) 24326ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark SkDEBUGPARAMS(fCoinID(0)) 24427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkDEBUGPARAMS(fContourID(0)) 24527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkDEBUGPARAMS(fPtTID(0)) 24627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkDEBUGPARAMS(fSegmentID(0)) 247ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark SkDEBUGPARAMS(fSpanID(0)) 248ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark SkDEBUGPARAMS(fDebugSkipAssert(debugSkipAssert)) { 24926ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark#if DEBUG_T_SECT_LOOP_COUNT 25026ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark debugResetLoopCounts(); 25126ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark#endif 252ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark#if DEBUG_COIN 253ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark fPreviousFuncName = nullptr; 254ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark#endif 25527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 256