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