Add base types for path ops

src/pathops/SkPathOpsTypes.h

Index: src/pathops/SkPathOpsTypes.h
===================================================================
--- src/pathops/SkPathOpsTypes.h	(revision 0)
+++ src/pathops/SkPathOpsTypes.h	(revision 0)
@@ -0,0 +1,254 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#ifndef SkPathOpsTypes_DEFINED
+#define SkPathOpsTypes_DEFINED
+
+#include <float.h>  // for FLT_EPSILON
+#include <math.h>   // for fabs, sqrt
+
+#include "SkFloatingPoint.h"
+#include "SkPathOpsDebug.h"
+#include "SkScalar.h"
+
+// FIXME: move these into SkTypes.h
+template <typename T> inline T SkTMax(T a, T b) {
+    if (a < b)

[whunt, 2013/03/22 18:16:06]

min and max can be performance critical operations.  I'd really recommend using
std::min and std::max in the general case if you can help it as that compiler is
mostly likely to recognize those and produce optimal code.  If SSE is enabled
you really want something like (for double):
_mm_cvtsd_f64(_mm_max_sd(_mm_set_sd(a), _mm_set_sd(b)))
although to be honest this sequence is not as efficient as it could be because
_mm_set_sd has the semantic of clearing the high bits of the SSE register even
though we don't actually need it to.  Because the double registers and SSE
registers are are the same the conversations are noops.

[caryclark, 2013/03/22 19:38:51]

Noted.

+        a = b;
+    return a;
+}
+
+template <typename T> inline T SkTMin(T a, T b) {
+    if (a > b)
+        a = b;
+    return a;
+}
+
+// FIXME: move this into SkFloatingPoint.h
+#define sk_double_isnan(a) sk_float_isnan(a)
+
+// FIXME: move this into SkPaths.h or just use the equivalent in SkRegion.h
+enum SkPathOp {
+    kDifference_PathOp,  //!< subtract the op region from the first region
+    kIntersect_PathOp,   //!< intersect the two regions
+    kUnion_PathOp,       //!< union (inclusive-or) the two regions
+    kXOR_PathOp,         //!< exclusive-or the two regions
+    /** subtract the first region from the op region */
+    kReverseDifference_PathOp,  // FIXME: unsupported
+    kReplace_PathOp      //!< replace the dst region with the op region FIXME: unsupported
+};
+
+enum SkPathOpsMask {
+    kWinding_PathOpsMask = -1,
+    kNo_PathOpsMask = 0,
+    kEvenOdd_PathOpsMask = 1
+};
+
+extern bool AlmostEqualUlps(float A, float B);
+inline bool AlmostEqualUlps(double A, double B) {
+    return AlmostEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
+}
+
+// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
+// DBL_EPSILON == 2.22045e-16
+const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
+const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
+const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
+const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON);
+const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
+const double DBL_EPSILON_ERR = DBL_EPSILON * 4;  // FIXME: tune -- allow a few bits of error
+const double ROUGH_EPSILON = FLT_EPSILON * 64;
+const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
+
+inline bool approximately_zero(double x) {
+    return fabs(x) < FLT_EPSILON;
+}
+
+inline bool precisely_zero(double x) {
+    return fabs(x) < DBL_EPSILON_ERR;
+}
+
+inline bool approximately_zero(float x) {
+    return fabs(x) < FLT_EPSILON;
+}
+
+inline bool approximately_zero_cubed(double x) {
+    return fabs(x) < FLT_EPSILON_CUBED;
+}
+
+inline bool approximately_zero_half(double x) {
+    return fabs(x) < FLT_EPSILON_HALF;
+}
+
+inline bool approximately_zero_squared(double x) {
+    return fabs(x) < FLT_EPSILON_SQUARED;
+}
+
+inline bool approximately_zero_sqrt(double x) {
+    return fabs(x) < FLT_EPSILON_SQRT;
+}
+
+inline bool approximately_zero_inverse(double x) {
+    return fabs(x) > FLT_EPSILON_INVERSE;
+}
+
+// OPTIMIZATION: if called multiple times with the same denom, we want to pass 1/y instead
+inline bool approximately_zero_when_compared_to(double x, double y) {
+    return x == 0 || fabs(x / y) < FLT_EPSILON;
+}
+
+// Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
+// AlmostEqualUlps instead.
+inline bool approximately_equal(double x, double y) {
+    return approximately_zero(x - y);
+}
+
+inline bool precisely_equal(double x, double y) {
+    return precisely_zero(x - y);
+}
+
+inline bool approximately_equal_half(double x, double y) {
+    return approximately_zero_half(x - y);
+}
+
+inline bool approximately_equal_squared(double x, double y) {
+    return approximately_equal(x, y);
+}
+
+inline bool approximately_greater(double x, double y) {
+    return x - FLT_EPSILON >= y;
+}
+
+inline bool approximately_greater_or_equal(double x, double y) {
+    return x + FLT_EPSILON > y;
+}
+
+inline bool approximately_lesser(double x, double y) {
+    return x + FLT_EPSILON <= y;
+}
+
+inline bool approximately_lesser_or_equal(double x, double y) {
+    return x - FLT_EPSILON < y;
+}
+
+inline double approximately_pin(double x) {
+    return approximately_zero(x) ? 0 : x;
+}
+
+inline float approximately_pin(float x) {
+    return approximately_zero(x) ? 0 : x;
+}
+
+inline bool approximately_greater_than_one(double x) {
+    return x > 1 - FLT_EPSILON;
+}
+
+inline bool precisely_greater_than_one(double x) {
+    return x > 1 - DBL_EPSILON_ERR;
+}
+
+inline bool approximately_less_than_zero(double x) {
+    return x < FLT_EPSILON;
+}
+
+inline bool precisely_less_than_zero(double x) {
+    return x < DBL_EPSILON_ERR;
+}
+
+inline bool approximately_negative(double x) {
+    return x < FLT_EPSILON;
+}
+
+inline bool precisely_negative(double x) {
+    return x < DBL_EPSILON_ERR;
+}
+
+inline bool approximately_one_or_less(double x) {
+    return x < 1 + FLT_EPSILON;
+}
+
+inline bool approximately_positive(double x) {
+    return x > -FLT_EPSILON;
+}
+
+inline bool approximately_positive_squared(double x) {
+    return x > -(FLT_EPSILON_SQUARED);
+}
+
+inline bool approximately_zero_or_more(double x) {
+    return x > -FLT_EPSILON;
+}
+
+inline bool approximately_between(double a, double b, double c) {
+    return a <= c ? approximately_negative(a - b) && approximately_negative(b - c)
+            : approximately_negative(b - a) && approximately_negative(c - b);
+}
+
+// returns true if (a <= b <= c) || (a >= b >= c)
+inline bool between(double a, double b, double c) {
+    SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0));
+    return (a - b) * (c - b) <= 0;
+}
+
+inline bool more_roughly_equal(double x, double y) {
+    return fabs(x - y) < MORE_ROUGH_EPSILON;
+}
+
+inline bool roughly_equal(double x, double y) {
+    return fabs(x - y) < ROUGH_EPSILON;
+}
+
+struct SkDPoint;
+struct SkDVector;
+struct SkDLine;
+struct SkDQuad;
+struct SkDTriangle;
+struct SkDCubic;
+struct SkDRect;
+
+inline double SkDInterp(double A, double B, double t) {
+    return A + (B - A) * t;
+}
+
+double SkDCubeRoot(double x);
+
+/* Returns -1 if negative, 0 if zero, 1 if positive
+*/
+inline int SkDSign(double x) {
+    return (x > 0) - (x < 0);
+}
+
+/* Returns 0 if negative, 1 if zero, 2 if positive
+*/
+inline int SKDSide(double x) {
+    return (x > 0) + (x >= 0);
+}
+
+/* Returns 1 if negative, 2 if zero, 4 if positive
+*/
+inline int SkDSideBit(double x) {
+    return 1 << SKDSide(x);
+}
+
+/* Given the set [0, 1, 2, 3], and two of the four members, compute an XOR mask
+   that computes the other two. Note that:
+
+   one ^ two == 3 for (0, 3), (1, 2)
+   one ^ two <  3 for (0, 1), (0, 2), (1, 3), (2, 3)
+   3 - (one ^ two) is either 0, 1, or 2
+   1 >> 3 - (one ^ two) is either 0 or 1
+thus:
+   returned == 2 for (0, 3), (1, 2)
+   returned == 3 for (0, 1), (0, 2), (1, 3), (2, 3)
+given that:
+   (0, 3) ^ 2 -> (2, 1)  (1, 2) ^ 2 -> (3, 0)
+   (0, 1) ^ 3 -> (3, 2)  (0, 2) ^ 3 -> (3, 1)  (1, 3) ^ 3 -> (2, 0)  (2, 3) ^ 3 -> (1, 0)
+*/
+inline int SkOtherTwo(int one, int two) {
+    return 1 >> 3 - (one ^ two) ^ 3;

[whunt, 2013/03/22 18:16:06]

I believe:
((one ^ two) & 1) + 1
will yield you the same result in fewer ops.  The existing solution should be 5
ops: two xor, one sub, one shift and one mov (to set the 1 that gets shifted). 
This solution should be 3: xor, and and inc

requirements (by my understanding):
[0,1] = 2
[0,2] = 1
[0,3] = 1 or 2
[1,2] = 1 or 2
[1,3] = 1
[2,3] = 2

a ^ b:
[0,1] = 1
[0,2] = 2
[0,3] = 3
[1,2] = 3
[1,3] = 2
[2,3] = 1

(a ^ b) & 1:
[0,1] = 1
[0,2] = 0
[0,3] = 1
[1,2] = 1
[1,3] = 0
[2,3] = 1

((a ^ b) & 1) + 1:
[0,1] = 2
[0,2] = 1
[0,3] = 2
[1,2] = 2
[1,3] = 1
[2,3] = 2

[caryclark, 2013/03/22 19:38:51]

This function is no longer used. It's been removed.

[whunt, 2013/03/22 19:50:10]

Sad =(, it was an interesting bit-twiddling problem.

+}
+
+#endif