summaryrefslogtreecommitdiffstats
path: root/skia/corecg
diff options
context:
space:
mode:
authorinitial.commit <initial.commit@0039d316-1c4b-4281-b951-d872f2087c98>2008-07-27 00:09:42 +0000
committerinitial.commit <initial.commit@0039d316-1c4b-4281-b951-d872f2087c98>2008-07-27 00:09:42 +0000
commitae2c20f398933a9e86c387dcc465ec0f71065ffc (patch)
treede668b1411e2ee0b4e49b6d8f8b68183134ac990 /skia/corecg
parent09911bf300f1a419907a9412154760efd0b7abc3 (diff)
downloadchromium_src-ae2c20f398933a9e86c387dcc465ec0f71065ffc.zip
chromium_src-ae2c20f398933a9e86c387dcc465ec0f71065ffc.tar.gz
chromium_src-ae2c20f398933a9e86c387dcc465ec0f71065ffc.tar.bz2
Add skia to the repository.
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@16 0039d316-1c4b-4281-b951-d872f2087c98
Diffstat (limited to 'skia/corecg')
-rw-r--r--skia/corecg/Android.mk40
-rw-r--r--skia/corecg/MODULE_LICENSE_APACHE20
-rw-r--r--skia/corecg/Makefile40
-rw-r--r--skia/corecg/NOTICE201
-rw-r--r--skia/corecg/Sk64.cpp575
-rw-r--r--skia/corecg/SkBuffer.cpp137
-rw-r--r--skia/corecg/SkChunkAlloc.cpp120
-rw-r--r--skia/corecg/SkCordic.cpp301
-rw-r--r--skia/corecg/SkCordic.h37
-rw-r--r--skia/corecg/SkDebug.cpp59
-rw-r--r--skia/corecg/SkDebug_stdio.cpp61
-rw-r--r--skia/corecg/SkFloat.cpp404
-rw-r--r--skia/corecg/SkFloat.h118
-rw-r--r--skia/corecg/SkFloatBits.h43
-rw-r--r--skia/corecg/SkInterpolator.cpp339
-rw-r--r--skia/corecg/SkMath.cpp820
-rw-r--r--skia/corecg/SkMatrix.cpp1678
-rw-r--r--skia/corecg/SkMemory_stdlib.cpp280
-rw-r--r--skia/corecg/SkPoint.cpp334
-rw-r--r--skia/corecg/SkRect.cpp129
-rw-r--r--skia/corecg/SkRegion.cpp1248
-rw-r--r--skia/corecg/SkRegionPriv.h89
-rw-r--r--skia/corecg/SkSinTable.h285
-rw-r--r--skia/corecg/SkTSort.h65
24 files changed, 7403 insertions, 0 deletions
diff --git a/skia/corecg/Android.mk b/skia/corecg/Android.mk
new file mode 100644
index 0000000..ead28bd
--- /dev/null
+++ b/skia/corecg/Android.mk
@@ -0,0 +1,40 @@
+LOCAL_PATH:= $(call my-dir)
+include $(CLEAR_VARS)
+
+LOCAL_ARM_MODE := arm
+
+LOCAL_SRC_FILES:= \
+ Sk64.cpp \
+ SkBuffer.cpp \
+ SkChunkAlloc.cpp \
+ SkCordic.cpp \
+ SkDebug.cpp \
+ SkDebug_stdio.cpp \
+ SkFloat.cpp \
+ SkInterpolator.cpp \
+ SkMath.cpp \
+ SkMatrix.cpp \
+ SkMemory_stdlib.cpp \
+ SkPoint.cpp \
+ SkRect.cpp \
+ SkRegion.cpp
+
+LOCAL_SHARED_LIBRARIES := \
+ libcutils \
+ libutils
+
+LOCAL_C_INCLUDES += \
+ include/corecg
+
+#LOCAL_CFLAGS+=
+#LOCAL_LDFLAGS:=
+
+LOCAL_MODULE:= libcorecg
+
+LOCAL_CFLAGS += -fstrict-aliasing
+
+ifeq ($(TARGET_ARCH),arm)
+ LOCAL_CFLAGS += -fomit-frame-pointer
+endif
+
+include $(BUILD_SHARED_LIBRARY)
diff --git a/skia/corecg/MODULE_LICENSE_APACHE2 b/skia/corecg/MODULE_LICENSE_APACHE2
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/skia/corecg/MODULE_LICENSE_APACHE2
diff --git a/skia/corecg/Makefile b/skia/corecg/Makefile
new file mode 100644
index 0000000..72f2f2a
--- /dev/null
+++ b/skia/corecg/Makefile
@@ -0,0 +1,40 @@
+LOCAL_PATH:= $(call my-dir)
+include $(CLEAR_VARS)
+
+LOCAL_ARM_MODE := arm
+
+LOCAL_SRC_FILES:= \
+ Sk64.cpp \
+ SkBuffer.cpp \
+ SkChunkAlloc.cpp \
+ SkCordic.cpp \
+ SkDebug.cpp \
+ SkDebug_stdio.cpp \
+ SkFloat.cpp \
+ SkInterpolator.cpp \
+ SkMath.cpp \
+ SkMatrix.cpp \
+ SkMemory_stdlib.cpp \
+ SkPoint.cpp \
+ SkRect.cpp \
+ SkRegion.cpp
+
+LOCAL_SHARED_LIBRARIES := \
+ libcutils \
+ libutils
+
+LOCAL_C_INCLUDES += \
+ include/corecg
+
+#LOCAL_CFLAGS+=
+#LOCAL_LDFLAGS:=
+
+LOCAL_MODULE:= libcorecg
+
+LOCAL_CFLAGS += -fstrict-aliasing
+
+ifeq ($(TARGET_ARCH),arm)
+ LOCAL_CFLAGS += -fomit-frame-pointer
+endif
+
+include $(BUILD_SHARED_LIBRARY)
diff --git a/skia/corecg/NOTICE b/skia/corecg/NOTICE
new file mode 100644
index 0000000..29f81d8
--- /dev/null
+++ b/skia/corecg/NOTICE
@@ -0,0 +1,201 @@
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+ 1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+ 2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+ 3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+ 4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+ 6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+ 7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+ 8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+ 9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+ END OF TERMS AND CONDITIONS
+
+ APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "[]"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+ Copyright [yyyy] [name of copyright owner]
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
diff --git a/skia/corecg/Sk64.cpp b/skia/corecg/Sk64.cpp
new file mode 100644
index 0000000..028a4ae
--- /dev/null
+++ b/skia/corecg/Sk64.cpp
@@ -0,0 +1,575 @@
+/* libs/corecg/Sk64.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "Sk64.h"
+
+#define shift_left(hi, lo) \
+ hi = (hi << 1) | (lo >> 31); \
+ lo <<= 1
+
+#define shift_left_bits(hi, lo, bits) \
+ SkASSERT((unsigned)(bits) < 31); \
+ hi = (hi << (bits)) | (lo >> (32 - (bits))); \
+ lo <<= (bits)
+
+//////////////////////////////////////////////////////////////////////
+
+int Sk64::getClzAbs() const
+{
+ int32_t hi = fHi;
+ uint32_t lo = fLo;
+
+ // get abs
+ if (hi < 0)
+ {
+ hi = -hi - Sk32ToBool(lo);
+ lo = 0 - lo;
+ }
+ return hi ? SkCLZ(hi) : SkCLZ(lo) + 32;
+}
+
+void Sk64::shiftLeft(unsigned bits)
+{
+ SkASSERT(bits <= 63);
+ if (bits == 0)
+ return;
+
+ if (bits >= 32)
+ {
+ fHi = fLo << (bits - 32);
+ fLo = 0;
+ }
+ else
+ {
+ fHi = (fHi << bits) | (fLo >> (32 - bits));
+ fLo <<= bits;
+ }
+}
+
+int32_t Sk64::getShiftRight(unsigned bits) const
+{
+ SkASSERT(bits <= 63);
+
+ if (bits == 0)
+ return fLo;
+
+ if (bits >= 32)
+ return fHi >> (bits - 32);
+ else
+ {
+#ifdef SK_DEBUG
+ int32_t tmp = fHi >> bits;
+ SkASSERT(tmp == 0 || tmp == -1);
+#endif
+ return (fHi << (32 - bits)) | (fLo >> bits);
+ }
+}
+
+void Sk64::shiftRight(unsigned bits)
+{
+ SkASSERT(bits <= 63);
+ if (bits == 0)
+ return;
+
+ if (bits >= 32)
+ {
+ fLo = fHi >> (bits - 32);
+ fHi >>= 31;
+ }
+ else
+ {
+ fLo = (fHi << (32 - bits)) | (fLo >> bits);
+ fHi >>= bits;
+ }
+}
+
+void Sk64::roundRight(unsigned bits)
+{
+ SkASSERT(bits <= 63);
+ if (bits)
+ {
+ Sk64 one;
+ one.set(1);
+ one.shiftLeft(bits - 1);
+ this->add(one);
+ this->shiftRight(bits);
+ }
+}
+
+int Sk64::shiftToMake32() const
+{
+ int32_t hi = fHi;
+ uint32_t lo = fLo;
+
+ if (hi < 0) // make it positive
+ {
+ hi = -hi - Sk32ToBool(lo);
+ lo = 0 - lo;
+ }
+
+ if (hi == 0)
+ return lo >> 31;
+ else
+ return 33 - SkCLZ(hi);
+}
+
+void Sk64::negate()
+{
+ fHi = -fHi - Sk32ToBool(fLo);
+ fLo = 0 - fLo;
+}
+
+void Sk64::abs()
+{
+ if (fHi < 0)
+ {
+ fHi = -fHi - Sk32ToBool(fLo);
+ fLo = 0 - fLo;
+ }
+}
+
+////////////////////////////////////////////////////////////////
+
+static inline int32_t round_right_16(int32_t hi, uint32_t lo)
+{
+ uint32_t sum = lo + (1 << 15);
+ hi += (sum < lo);
+ return (hi << 16) | (sum >> 16);
+}
+
+SkBool Sk64::isFixed() const
+{
+ Sk64 tmp = *this;
+ tmp.roundRight(16);
+ return tmp.is32();
+}
+
+SkFract Sk64::getFract() const
+{
+ Sk64 tmp = *this;
+ tmp.roundRight(30);
+ return tmp.get32();
+}
+
+void Sk64::sub(const Sk64& a)
+{
+ fHi = fHi - a.fHi - (fLo < a.fLo);
+ fLo = fLo - a.fLo;
+}
+
+void Sk64::rsub(const Sk64& a)
+{
+ fHi = a.fHi - fHi - (a.fLo < fLo);
+ fLo = a.fLo - fLo;
+}
+
+void Sk64::setMul(int32_t a, int32_t b)
+{
+ int sa = a >> 31;
+ int sb = b >> 31;
+ // now make them positive
+ a = (a ^ sa) - sa;
+ b = (b ^ sb) - sb;
+
+ uint32_t ah = a >> 16;
+ uint32_t al = a & 0xFFFF;
+ uint32_t bh = b >> 16;
+ uint32_t bl = b & 0xFFFF;
+
+ uint32_t A = ah * bh;
+ uint32_t B = ah * bl + al * bh;
+ uint32_t C = al * bl;
+
+ /* [ A ]
+ [ B ]
+ [ C ]
+ */
+ fLo = C + (B << 16);
+ fHi = A + (B >>16) + (fLo < C);
+
+ if (sa != sb)
+ this->negate();
+}
+
+void Sk64::div(int32_t denom, DivOptions option)
+{
+ SkASSERT(denom);
+
+ int32_t hi = fHi;
+ uint32_t lo = fLo;
+ int sign = denom ^ hi;
+
+ denom = SkAbs32(denom);
+ if (hi < 0)
+ {
+ hi = -hi - Sk32ToBool(lo);
+ lo = 0 - lo;
+ }
+
+ if (option == kRound_DivOption) // add denom/2
+ {
+ uint32_t newLo = lo + (denom >> 1);
+ hi += (newLo < lo);
+ lo = newLo;
+ }
+
+ if (hi == 0) // fast-case
+ {
+ if (lo < (uint32_t)denom)
+ this->set(0, 0);
+ else
+ {
+ this->set(0, lo / denom);
+ if (sign < 0)
+ this->negate();
+ }
+ return;
+ }
+
+ int bits;
+
+ {
+ int dbits = SkCLZ(denom);
+ int nbits = SkCLZ(hi);
+
+ bits = 32 + dbits - nbits;
+ SkASSERT(bits <= 63);
+ if (bits <= 0)
+ {
+ this->set(0, 0);
+ return;
+ }
+ denom <<= (dbits - 1);
+ shift_left_bits(hi, lo, nbits - 1);
+ }
+
+ int32_t rhi = 0;
+ uint32_t rlo = 0;
+
+ do {
+ shift_left(rhi, rlo);
+#ifdef SK_CPU_HAS_CONDITIONAL_INSTR
+ if ((uint32_t)denom <= (uint32_t)hi)
+ {
+ hi -= denom;
+ rlo |= 1;
+ }
+#else
+ int32_t diff = (denom - hi - 1) >> 31;
+ hi -= denom & diff;
+ rlo -= diff;
+#endif
+ shift_left(hi, lo);
+ } while (--bits >= 0);
+ SkASSERT(rhi >= 0);
+
+ fHi = rhi;
+ fLo = rlo;
+ if (sign < 0)
+ this->negate();
+}
+
+#define shift_left_2(a, b, c) \
+ a = (a << 2) | (b >> 30); \
+ b = (b << 2) | (c >> 30); \
+ c <<= 2
+
+int32_t Sk64::getSqrt() const
+{
+ SkASSERT(!this->isNeg());
+
+ uint32_t hi = fHi;
+ uint32_t lo = fLo;
+ uint32_t sqr = 0;
+ uint32_t root = 0;
+ int count = 31;
+
+ do {
+ root <<= 1;
+ shift_left_2(sqr, hi, lo);
+
+ uint32_t testDiv = (root << 1) + 1;
+ if (sqr >= testDiv)
+ {
+ sqr -= testDiv;
+ root++;
+ }
+ } while (--count >= 0);
+ SkASSERT((int32_t)root >= 0);
+
+ return root;
+}
+
+#ifdef SkLONGLONG
+ SkLONGLONG Sk64::getLongLong() const
+ {
+ SkLONGLONG value = fHi;
+ value <<= 32;
+ return value | fLo;
+ }
+#endif
+
+SkFixed Sk64::getFixedDiv(const Sk64& denom) const
+{
+ Sk64 N = *this;
+ Sk64 D = denom;
+ int32_t sign = SkExtractSign(N.fHi ^ D.fHi);
+ SkFixed result;
+
+ N.abs();
+ D.abs();
+
+ // need to knock D down to just 31 bits
+ // either by rounding it to the right, or shifting N to the left
+ // then we can just call 64/32 div
+
+ int nclz = N.fHi ? SkCLZ(N.fHi) : 32;
+ int dclz = D.fHi ? SkCLZ(D.fHi) : (33 - (D.fLo >> 31));
+
+ int shiftN = nclz - 1;
+ SkASSERT(shiftN >= 0);
+ int shiftD = 33 - dclz;
+ SkASSERT(shiftD >= 0);
+
+ if (shiftD + shiftN < 16)
+ shiftD = 16 - shiftN;
+ else
+ shiftN = 16 - shiftD;
+
+ D.roundRight(shiftD);
+ if (D.isZero())
+ result = SK_MaxS32;
+ else
+ {
+ if (shiftN >= 0)
+ N.shiftLeft(shiftN);
+ else
+ N.roundRight(-shiftN);
+ N.div(D.get32(), Sk64::kTrunc_DivOption);
+ if (N.is32())
+ result = N.get32();
+ else
+ result = SK_MaxS32;
+ }
+ return SkApplySign(result, sign);
+}
+
+///////////////////////////////////////////////////////////////////////
+
+#ifdef SK_DEBUG
+
+#include "SkRandom.h"
+#include <math.h>
+
+#ifdef SK_SUPPORT_UNITTEST
+struct BoolTable {
+ int8_t zero, pos, neg, toBool, sign;
+};
+
+static void bool_table_test(const Sk64& a, const BoolTable& table)
+{
+ SkASSERT(a.isZero() != a.nonZero());
+
+ SkASSERT(!a.isZero() == !table.zero);
+ SkASSERT(!a.isPos() == !table.pos);
+ SkASSERT(!a.isNeg() == !table.neg);
+ SkASSERT(a.sign() == table.sign);
+}
+
+#ifdef SkLONGLONG
+ static SkLONGLONG asLL(const Sk64& a)
+ {
+ return ((SkLONGLONG)a.fHi << 32) | a.fLo;
+ }
+#endif
+#endif
+
+void Sk64::UnitTest()
+{
+#ifdef SK_SUPPORT_UNITTEST
+ enum BoolTests {
+ kZero_BoolTest,
+ kPos_BoolTest,
+ kNeg_BoolTest
+ };
+ static const BoolTable gBoolTable[] = {
+ { 1, 0, 0, 0, 0 },
+ { 0, 1, 0, 1, 1 },
+ { 0, 0, 1, 1, -1 }
+ };
+
+ Sk64 a, b, c;
+
+ a.fHi = a.fLo = 0;
+ b.set(0);
+ c.setZero();
+ SkASSERT(a == b);
+ SkASSERT(a == c);
+ bool_table_test(a, gBoolTable[kZero_BoolTest]);
+
+ a.fHi = 0; a.fLo = 5;
+ b.set(5);
+ SkASSERT(a == b);
+ SkASSERT(a.is32() && a.get32() == 5 && !a.is64());
+ bool_table_test(a, gBoolTable[kPos_BoolTest]);
+
+ a.fHi = -1; a.fLo = (uint32_t)-5;
+ b.set(-5);
+ SkASSERT(a == b);
+ SkASSERT(a.is32() && a.get32() == -5 && !a.is64());
+ bool_table_test(a, gBoolTable[kNeg_BoolTest]);
+
+ a.setZero();
+ b.set(6);
+ c.set(-6);
+ SkASSERT(a != b && b != c && a != c);
+ SkASSERT(!(a == b) && !(a == b) && !(a == b));
+ SkASSERT(a < b && b > a && a <= b && b >= a);
+ SkASSERT(c < a && a > c && c <= a && a >= c);
+ SkASSERT(c < b && b > c && c <= b && b >= c);
+
+ // Now test add/sub
+
+ SkRandom rand;
+ int i;
+
+ for (i = 0; i < 1000; i++)
+ {
+ int aa = rand.nextS() >> 1;
+ int bb = rand.nextS() >> 1;
+ a.set(aa);
+ b.set(bb);
+ SkASSERT(a.get32() == aa && b.get32() == bb);
+ c = a; c.add(bb);
+ SkASSERT(c.get32() == aa + bb);
+ c = a; c.add(-bb);
+ SkASSERT(c.get32() == aa - bb);
+ c = a; c.add(b);
+ SkASSERT(c.get32() == aa + bb);
+ c = a; c.sub(b);
+ SkASSERT(c.get32() == aa - bb);
+ }
+
+#ifdef SkLONGLONG
+ for (i = 0; i < 1000; i++)
+ {
+ rand.next64(&a); //a.fHi >>= 1; // avoid overflow
+ rand.next64(&b); //b.fHi >>= 1; // avoid overflow
+
+ if (!(i & 3)) // want to explicitly test these cases
+ {
+ a.fLo = 0;
+ b.fLo = 0;
+ }
+ else if (!(i & 7)) // want to explicitly test these cases
+ {
+ a.fHi = 0;
+ b.fHi = 0;
+ }
+
+ SkLONGLONG aa = asLL(a);
+ SkLONGLONG bb = asLL(b);
+
+ SkASSERT((a < b) == (aa < bb));
+ SkASSERT((a <= b) == (aa <= bb));
+ SkASSERT((a > b) == (aa > bb));
+ SkASSERT((a >= b) == (aa >= bb));
+ SkASSERT((a == b) == (aa == bb));
+ SkASSERT((a != b) == (aa != bb));
+
+ c = a; c.add(b);
+ SkASSERT(asLL(c) == aa + bb);
+ c = a; c.sub(b);
+ SkASSERT(asLL(c) == aa - bb);
+ c = a; c.rsub(b);
+ SkASSERT(asLL(c) == bb - aa);
+ c = a; c.negate();
+ SkASSERT(asLL(c) == -aa);
+
+ int bits = rand.nextU() & 63;
+ c = a; c.shiftLeft(bits);
+ SkASSERT(asLL(c) == (aa << bits));
+ c = a; c.shiftRight(bits);
+ SkASSERT(asLL(c) == (aa >> bits));
+ c = a; c.roundRight(bits);
+
+ SkLONGLONG tmp;
+
+ tmp = aa;
+ if (bits > 0)
+ tmp += (SkLONGLONG)1 << (bits - 1);
+ SkASSERT(asLL(c) == (tmp >> bits));
+
+ c.setMul(a.fHi, b.fHi);
+ tmp = (SkLONGLONG)a.fHi * b.fHi;
+ SkASSERT(asLL(c) == tmp);
+ }
+
+
+ for (i = 0; i < 100000; i++)
+ {
+ Sk64 wide;
+ int32_t denom = rand.nextS();
+
+ while (denom == 0)
+ denom = rand.nextS();
+ wide.setMul(rand.nextS(), rand.nextS());
+ SkLONGLONG check = wide.getLongLong();
+
+ wide.div(denom, Sk64::kTrunc_DivOption);
+ check /= denom;
+ SkLONGLONG w = wide.getLongLong();
+
+ SkASSERT(check == w);
+
+#ifdef SK_CAN_USE_FLOATx
+ wide.setMul(rand.nextS(), rand.nextS());
+ wide.abs();
+ denom = wide.getSqrt();
+ int32_t ck = (int32_t)sqrt((double)wide.getLongLong());
+ int diff = denom - ck;
+ SkASSERT(SkAbs32(diff) <= 1);
+
+ wide.setMul(rand.nextS(), rand.nextS());
+ Sk64 dwide;
+ dwide.setMul(rand.nextS(), rand.nextS());
+ SkFixed fixdiv = wide.getFixedDiv(dwide);
+ double dnumer = (double)wide.getLongLong();
+ double ddenom = (double)dwide.getLongLong();
+ double ddiv = dnumer / ddenom;
+ SkFixed dfixdiv;
+ if (ddiv >= (double)SK_MaxS32 / (double)SK_Fixed1)
+ dfixdiv = SK_MaxS32;
+ else if (ddiv <= -(double)SK_MaxS32 / (double)SK_Fixed1)
+ dfixdiv = SK_MinS32;
+ else
+ dfixdiv = SkFloatToFixed(dnumer / ddenom);
+ diff = fixdiv - dfixdiv;
+
+ if (SkAbs32(diff) > 1) {
+ SkDebugf(" %d === numer %g denom %g div %g xdiv %x fxdiv %x\n",
+ i, dnumer, ddenom, ddiv, dfixdiv, fixdiv);
+ }
+// SkASSERT(SkAbs32(diff) <= 1);
+#endif
+ }
+#endif
+#endif
+}
+
+#endif
+
diff --git a/skia/corecg/SkBuffer.cpp b/skia/corecg/SkBuffer.cpp
new file mode 100644
index 0000000..1a8f069
--- /dev/null
+++ b/skia/corecg/SkBuffer.cpp
@@ -0,0 +1,137 @@
+/* libs/corecg/SkBuffer.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkBuffer.h"
+
+////////////////////////////////////////////////////////////////////////////////////////
+
+void SkRBuffer::readNoSizeCheck(void* buffer, size_t size)
+{
+ SkASSERT((fData != 0 && fStop == 0) || fPos + size <= fStop);
+ if (buffer)
+ memcpy(buffer, fPos, size);
+ fPos += size;
+}
+
+const void* SkRBuffer::skip(size_t size)
+{
+ const void* result = fPos;
+ readNoSizeCheck(NULL, size);
+ return result;
+}
+
+size_t SkRBuffer::skipToAlign4()
+{
+ size_t pos = this->pos();
+ size_t n = SkAlign4(pos) - pos;
+ fPos += n;
+ return n;
+}
+
+void* SkWBuffer::skip(size_t size)
+{
+ void* result = fPos;
+ writeNoSizeCheck(NULL, size);
+ return fData == NULL ? NULL : result;
+}
+
+void SkWBuffer::writeNoSizeCheck(const void* buffer, size_t size)
+{
+ SkASSERT(fData == 0 || fStop == 0 || fPos + size <= fStop);
+ if (fData && buffer)
+ memcpy(fPos, buffer, size);
+ fPos += size;
+}
+
+size_t SkWBuffer::padToAlign4()
+{
+ size_t pos = this->pos();
+ size_t n = SkAlign4(pos) - pos;
+
+ if (n && fData)
+ {
+ char* p = fPos;
+ char* stop = p + n;
+ do {
+ *p++ = 0;
+ } while (p < stop);
+ }
+ fPos += n;
+ return n;
+}
+
+#if 0
+#ifdef SK_DEBUG
+ static void AssertBuffer32(const void* buffer)
+ {
+ SkASSERT(buffer);
+ SkASSERT(((size_t)buffer & 3) == 0);
+ }
+#else
+ #define AssertBuffer32(buffer)
+#endif
+
+void* sk_buffer_write_int32(void* buffer, int32_t value)
+{
+ AssertBuffer32(buffer);
+ *(int32_t*)buffer = value;
+ return (char*)buffer + sizeof(int32_t);
+}
+
+void* sk_buffer_write_int32(void* buffer, const int32_t values[], int count)
+{
+ AssertBuffer32(buffer);
+ SkASSERT(count >= 0);
+
+ memcpy((int32_t*)buffer, values, count * sizeof(int32_t));
+ return (char*)buffer + count * sizeof(int32_t);
+}
+
+const void* sk_buffer_read_int32(const void* buffer, int32_t* value)
+{
+ AssertBuffer32(buffer);
+ if (value)
+ *value = *(const int32_t*)buffer;
+ return (const char*)buffer + sizeof(int32_t);
+}
+
+const void* sk_buffer_read_int32(const void* buffer, int32_t values[], int count)
+{
+ AssertBuffer32(buffer);
+ SkASSERT(count >= 0);
+
+ if (values)
+ memcpy(values, (const int32_t*)buffer, count * sizeof(int32_t));
+ return (const char*)buffer + count * sizeof(int32_t);
+}
+
+void* sk_buffer_write_ptr(void* buffer, void* ptr)
+{
+ AssertBuffer32(buffer);
+ *(void**)buffer = ptr;
+ return (char*)buffer + sizeof(void*);
+}
+
+const void* sk_buffer_read_ptr(const void* buffer, void** ptr)
+{
+ AssertBuffer32(buffer);
+ if (ptr)
+ *ptr = *(void**)buffer;
+ return (const char*)buffer + sizeof(void*);
+}
+
+#endif
diff --git a/skia/corecg/SkChunkAlloc.cpp b/skia/corecg/SkChunkAlloc.cpp
new file mode 100644
index 0000000..b9cfd90
--- /dev/null
+++ b/skia/corecg/SkChunkAlloc.cpp
@@ -0,0 +1,120 @@
+/* libs/corecg/SkChunkAlloc.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkChunkAlloc.h"
+
+struct SkChunkAlloc::Block {
+ Block* fNext;
+ size_t fFreeSize;
+ char* fFreePtr;
+ // data[] follows
+
+ void freeChain() { // this can be null
+ Block* block = this;
+ while (block) {
+ Block* next = block->fNext;
+ sk_free(block);
+ block = next;
+ }
+ };
+
+ Block* tail() {
+ Block* block = this;
+ if (block) {
+ for (;;) {
+ Block* next = block->fNext;
+ if (NULL == next) {
+ break;
+ }
+ block = next;
+ }
+ }
+ return block;
+ }
+};
+
+SkChunkAlloc::SkChunkAlloc(size_t minSize)
+ : fBlock(NULL), fMinSize(SkAlign4(minSize)), fPool(NULL), fTotalCapacity(0)
+{
+}
+
+SkChunkAlloc::~SkChunkAlloc() {
+ this->reset();
+}
+
+void SkChunkAlloc::reset() {
+ fBlock->freeChain();
+ fBlock = NULL;
+ fPool->freeChain();
+ fPool = NULL;
+ fTotalCapacity = 0;
+}
+
+void SkChunkAlloc::reuse() {
+ if (fPool && fBlock) {
+ fPool->tail()->fNext = fBlock;
+ }
+ fPool = fBlock;
+ fBlock = NULL;
+ fTotalCapacity = 0;
+}
+
+SkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) {
+ Block* block = fPool;
+
+ if (block && bytes <= block->fFreeSize) {
+ fPool = block->fNext;
+ return block;
+ }
+
+ size_t size = SkMax32((int32_t)bytes, (int32_t)fMinSize);
+
+ block = (Block*)sk_malloc_flags(sizeof(Block) + size,
+ ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0);
+
+ if (block) {
+ // block->fNext = fBlock;
+ block->fFreeSize = size;
+ block->fFreePtr = (char*)block + sizeof(Block);
+
+ fTotalCapacity += size;
+ }
+ return block;
+}
+
+void* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) {
+ bytes = SkAlign4(bytes);
+
+ Block* block = fBlock;
+
+ if (block == NULL || bytes > block->fFreeSize) {
+ block = this->newBlock(bytes, ftype);
+ if (NULL == block) {
+ return NULL;
+ }
+ block->fNext = fBlock;
+ fBlock = block;
+ }
+
+ SkASSERT(block && bytes <= block->fFreeSize);
+ void* ptr = block->fFreePtr;
+
+ block->fFreeSize -= bytes;
+ block->fFreePtr += bytes;
+ return ptr;
+}
+
diff --git a/skia/corecg/SkCordic.cpp b/skia/corecg/SkCordic.cpp
new file mode 100644
index 0000000..accbd95
--- /dev/null
+++ b/skia/corecg/SkCordic.cpp
@@ -0,0 +1,301 @@
+/* libs/corecg/SkCordic.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkCordic.h"
+#include "SkMath.h"
+#include "Sk64.h"
+
+// 0x20000000 equals pi / 4
+const int32_t kATanDegrees[] = { 0x20000000,
+ 0x12E4051D, 0x9FB385B, 0x51111D4, 0x28B0D43, 0x145D7E1, 0xA2F61E, 0x517C55,
+ 0x28BE53, 0x145F2E, 0xA2F98, 0x517CC, 0x28BE6, 0x145F3, 0xA2F9, 0x517C,
+ 0x28BE, 0x145F, 0xA2F, 0x517, 0x28B, 0x145, 0xA2, 0x51, 0x28, 0x14,
+ 0xA, 0x5, 0x2, 0x1 };
+
+const int32_t kFixedInvGain1 = 0x18bde0bb; // 0.607252935
+
+static void SkCircularRotation(int32_t* x0, int32_t* y0, int32_t* z0)
+{
+ int32_t t = 0;
+ int32_t x = *x0;
+ int32_t y = *y0;
+ int32_t z = *z0;
+ const int32_t* tanPtr = kATanDegrees;
+ do {
+ int32_t x1 = y >> t;
+ int32_t y1 = x >> t;
+ int32_t tan = *tanPtr++;
+ if (z >= 0) {
+ x -= x1;
+ y += y1;
+ z -= tan;
+ } else {
+ x += x1;
+ y -= y1;
+ z += tan;
+ }
+ } while (++t < 16); // 30);
+ *x0 = x;
+ *y0 = y;
+ *z0 = z;
+}
+
+SkFixed SkCordicSinCos(SkFixed radians, SkFixed* cosp)
+{
+ int32_t scaledRadians = radians * 0x28be; // scale radians to 65536 / PI()
+ int quadrant = scaledRadians >> 30;
+ quadrant += 1;
+ if (quadrant & 2)
+ scaledRadians = -scaledRadians + 0x80000000;
+ /* |a| <= 90 degrees as a 1.31 number */
+ SkFixed sin = 0;
+ SkFixed cos = kFixedInvGain1;
+ SkCircularRotation(&cos, &sin, &scaledRadians);
+ Sk64 scaled;
+ scaled.setMul(sin, 0x6488d);
+ sin = scaled.fHi;
+ scaled.setMul(cos, 0x6488d);
+ if (quadrant & 2)
+ scaled.fHi = - scaled.fHi;
+ *cosp = scaled.fHi;
+ return sin;
+}
+
+SkFixed SkCordicTan(SkFixed a)
+{
+ int32_t cos;
+ int32_t sin = SkCordicSinCos(a, &cos);
+ return SkFixedDiv(sin, cos);
+}
+
+static int32_t SkCircularVector(int32_t* y0, int32_t* x0, int32_t vecMode)
+{
+ int32_t x = *x0;
+ int32_t y = *y0;
+ int32_t z = 0;
+ int32_t t = 0;
+ const int32_t* tanPtr = kATanDegrees;
+ do {
+ int32_t x1 = y >> t;
+ int32_t y1 = x >> t;
+ int32_t tan = *tanPtr++;
+ if (y < vecMode) {
+ x -= x1;
+ y += y1;
+ z -= tan;
+ } else {
+ x += x1;
+ y -= y1;
+ z += tan;
+ }
+ } while (++t < 16); // 30
+ Sk64 scaled;
+ scaled.setMul(z, 0x6488d); // scale back into the SkScalar space (0x100000000/0x28be)
+ return scaled.fHi;
+}
+
+SkFixed SkCordicASin(SkFixed a) {
+ int32_t sign = SkExtractSign(a);
+ int32_t z = SkFixedAbs(a);
+ if (z >= SK_Fixed1)
+ return SkApplySign(SK_FixedPI>>1, sign);
+ int32_t x = kFixedInvGain1;
+ int32_t y = 0;
+ z *= 0x28be;
+ z = SkCircularVector(&y, &x, z);
+ z = SkApplySign(z, ~sign);
+ return z;
+}
+
+SkFixed SkCordicACos(SkFixed a) {
+ int32_t z = SkCordicASin(a);
+ z = (SK_FixedPI>>1) - z;
+ return z;
+}
+
+SkFixed SkCordicATan2(SkFixed y, SkFixed x) {
+ if ((x | y) == 0)
+ return 0;
+ int32_t xsign = SkExtractSign(x);
+ x = SkFixedAbs(x);
+ int32_t result = SkCircularVector(&y, &x, 0);
+ if (xsign) {
+ int32_t rsign = SkExtractSign(result);
+ if (y == 0)
+ rsign = 0;
+ SkFixed pi = SkApplySign(SK_FixedPI, rsign);
+ result = pi - result;
+ }
+ return result;
+}
+
+const int32_t kATanHDegrees[] = {
+ 0x1661788D, 0xA680D61, 0x51EA6FC, 0x28CBFDD, 0x1460E34,
+ 0xA2FCE8, 0x517D2E, 0x28BE6E, 0x145F32,
+ 0xA2F98, 0x517CC, 0x28BE6, 0x145F3, 0xA2F9, 0x517C,
+ 0x28BE, 0x145F, 0xA2F, 0x517, 0x28B, 0x145, 0xA2, 0x51, 0x28, 0x14,
+ 0xA, 0x5, 0x2, 0x1 };
+
+const int32_t kFixedInvGain2 = 0x31330AAA; // 1.207534495
+
+static void SkHyperbolic(int32_t* x0, int32_t* y0, int32_t* z0, int mode)
+{
+ int32_t t = 1;
+ int32_t x = *x0;
+ int32_t y = *y0;
+ int32_t z = *z0;
+ const int32_t* tanPtr = kATanHDegrees;
+ int k = -3;
+ do {
+ int32_t x1 = y >> t;
+ int32_t y1 = x >> t;
+ int32_t tan = *tanPtr++;
+ int count = 2 + (k >> 31);
+ if (++k == 1)
+ k = -2;
+ do {
+ if (((y >> 31) & mode) | ~((z >> 31) | mode)) {
+ x += x1;
+ y += y1;
+ z -= tan;
+ } else {
+ x -= x1;
+ y -= y1;
+ z += tan;
+ }
+ } while (--count);
+ } while (++t < 30);
+ *x0 = x;
+ *y0 = y;
+ *z0 = z;
+}
+
+SkFixed SkCordicLog(SkFixed a) {
+ a *= 0x28be;
+ int32_t x = a + 0x28BE60DB; // 1.0
+ int32_t y = a - 0x28BE60DB;
+ int32_t z = 0;
+ SkHyperbolic(&x, &y, &z, -1);
+ Sk64 scaled;
+ scaled.setMul(z, 0x6488d);
+ z = scaled.fHi;
+ return z << 1;
+}
+
+SkFixed SkCordicExp(SkFixed a) {
+ int32_t cosh = kFixedInvGain2;
+ int32_t sinh = 0;
+ SkHyperbolic(&cosh, &sinh, &a, 0);
+ return cosh + sinh;
+}
+
+#ifdef SK_DEBUG
+
+#ifdef SK_CAN_USE_FLOAT
+ #include "SkFloatingPoint.h"
+#endif
+
+void SkCordic_UnitTest()
+{
+#if defined(SK_SUPPORT_UNITTEST) && defined(SK_CAN_USE_FLOAT)
+ float val;
+ for (float angle = -720; angle < 720; angle += 30) {
+ float radian = angle * 3.1415925358f / 180.0f;
+ SkFixed f_angle = (int) (radian * 65536.0f);
+ // sincos
+ float sine = sinf(radian);
+ float cosine = cosf(radian);
+ SkFixed f_cosine;
+ SkFixed f_sine = SkCordicSinCos(f_angle, &f_cosine);
+ float sine2 = (float) f_sine / 65536.0f;
+ float cosine2 = (float) f_cosine / 65536.0f;
+ float error = fabsf(sine - sine2);
+ if (error > 0.001)
+ SkDebugf("sin error : angle = %g ; sin = %g ; cordic = %g\n", angle, sine, sine2);
+ error = fabsf(cosine - cosine2);
+ if (error > 0.001)
+ SkDebugf("cos error : angle = %g ; cos = %g ; cordic = %g\n", angle, cosine, cosine2);
+ // tan
+ float _tan = tanf(radian);
+ SkFixed f_tan = SkCordicTan(f_angle);
+ float tan2 = (float) f_tan / 65536.0f;
+ error = fabsf(_tan - tan2);
+ if (error > 0.05 && fabsf(_tan) < 1e6)
+ SkDebugf("tan error : angle = %g ; tan = %g ; cordic = %g\n", angle, _tan, tan2);
+ }
+ for (val = -1; val <= 1; val += .1f) {
+ SkFixed f_val = (int) (val * 65536.0f);
+ // asin
+ float arcsine = asinf(val);
+ SkFixed f_arcsine = SkCordicASin(f_val);
+ float arcsine2 = (float) f_arcsine / 65536.0f;
+ float error = fabsf(arcsine - arcsine2);
+ if (error > 0.001)
+ SkDebugf("asin error : val = %g ; asin = %g ; cordic = %g\n", val, arcsine, arcsine2);
+ }
+#if 1
+ for (val = -1; val <= 1; val += .1f) {
+#else
+ val = .5; {
+#endif
+ SkFixed f_val = (int) (val * 65536.0f);
+ // acos
+ float arccos = acosf(val);
+ SkFixed f_arccos = SkCordicACos(f_val);
+ float arccos2 = (float) f_arccos / 65536.0f;
+ float error = fabsf(arccos - arccos2);
+ if (error > 0.001)
+ SkDebugf("acos error : val = %g ; acos = %g ; cordic = %g\n", val, arccos, arccos2);
+ }
+ // atan2
+#if 1
+ for (val = -1000; val <= 1000; val += 500.f) {
+ for (float val2 = -1000; val2 <= 1000; val2 += 500.f) {
+#else
+ val = 0; {
+ float val2 = -1000; {
+#endif
+ SkFixed f_val = (int) (val * 65536.0f);
+ SkFixed f_val2 = (int) (val2 * 65536.0f);
+ float arctan = atan2f(val, val2);
+ SkFixed f_arctan = SkCordicATan2(f_val, f_val2);
+ float arctan2 = (float) f_arctan / 65536.0f;
+ float error = fabsf(arctan - arctan2);
+ if (error > 0.001)
+ SkDebugf("atan2 error : val = %g ; val2 = %g ; atan2 = %g ; cordic = %g\n", val, val2, arctan, arctan2);
+ }
+ }
+ // log
+#if 1
+ for (val = 0.125f; val <= 8.f; val *= 2.0f) {
+#else
+ val = .5; {
+#endif
+ SkFixed f_val = (int) (val * 65536.0f);
+ // acos
+ float log = logf(val);
+ SkFixed f_log = SkCordicLog(f_val);
+ float log2 = (float) f_log / 65536.0f;
+ float error = fabsf(log - log2);
+ if (error > 0.001)
+ SkDebugf("log error : val = %g ; log = %g ; cordic = %g\n", val, log, log2);
+ }
+ // exp
+#endif
+}
+
+#endif
diff --git a/skia/corecg/SkCordic.h b/skia/corecg/SkCordic.h
new file mode 100644
index 0000000..70c70b5
--- /dev/null
+++ b/skia/corecg/SkCordic.h
@@ -0,0 +1,37 @@
+/* libs/corecg/SkCordic.h
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#ifndef SkCordic_DEFINED
+#define SkCordic_DEFINED
+
+#include "SkTypes.h"
+#include "SkFixed.h"
+
+SkFixed SkCordicACos(SkFixed a);
+SkFixed SkCordicASin(SkFixed a);
+SkFixed SkCordicATan2(SkFixed y, SkFixed x);
+SkFixed SkCordicExp(SkFixed a);
+SkFixed SkCordicLog(SkFixed a);
+SkFixed SkCordicSinCos(SkFixed radians, SkFixed* cosp);
+SkFixed SkCordicTan(SkFixed a);
+
+#ifdef SK_DEBUG
+ void SkCordic_UnitTest();
+#endif
+
+#endif // SkCordic
+
diff --git a/skia/corecg/SkDebug.cpp b/skia/corecg/SkDebug.cpp
new file mode 100644
index 0000000..5d5518d
--- /dev/null
+++ b/skia/corecg/SkDebug.cpp
@@ -0,0 +1,59 @@
+/* libs/corecg/SkDebug.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkTypes.h"
+
+#ifdef SK_DEBUG
+
+int8_t SkToS8(long x)
+{
+ SkASSERT((int8_t)x == x);
+ return (int8_t)x;
+}
+
+uint8_t SkToU8(size_t x)
+{
+ SkASSERT((uint8_t)x == x);
+ return (uint8_t)x;
+}
+
+int16_t SkToS16(long x)
+{
+ SkASSERT((int16_t)x == x);
+ return (int16_t)x;
+}
+
+uint16_t SkToU16(size_t x)
+{
+ SkASSERT((uint16_t)x == x);
+ return (uint16_t)x;
+}
+
+int32_t SkToS32(long x)
+{
+ SkASSERT((int32_t)x == x);
+ return (int32_t)x;
+}
+
+uint32_t SkToU32(size_t x)
+{
+ SkASSERT((uint32_t)x == x);
+ return (uint32_t)x;
+}
+
+#endif
+
diff --git a/skia/corecg/SkDebug_stdio.cpp b/skia/corecg/SkDebug_stdio.cpp
new file mode 100644
index 0000000..6da09af
--- /dev/null
+++ b/skia/corecg/SkDebug_stdio.cpp
@@ -0,0 +1,61 @@
+/* libs/corecg/SkDebug_stdio.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkTypes.h"
+
+static const size_t kBufferSize = 256;
+
+#ifdef ANDROID
+
+#define LOG_TAG "skia"
+#include <utils/Log.h>
+
+void Android_SkDebugf(const char* file, int line, const char* function,
+ const char* format, ...)
+{
+ if (format[0] == '\n' && format[1] == '\0')
+ return;
+ va_list args;
+ va_start(args, format);
+#ifdef HAVE_ANDROID_OS
+ char buffer[kBufferSize + 1];
+ vsnprintf(buffer, kBufferSize, format, args);
+ if (buffer[0] != 0)
+ __android_log_print(ANDROID_LOG_DEBUG, LOG_TAG, "%s", buffer);
+#else
+ android_vprintLog(ANDROID_LOG_DEBUG, NULL, LOG_TAG, format, args);
+#endif
+ va_end(args);
+}
+
+#elif defined(SK_DEBUG)
+
+#include <stdarg.h>
+#include <stdio.h>
+
+void SkDebugf(const char format[], ...)
+{
+ char buffer[kBufferSize + 1];
+ va_list args;
+ va_start(args, format);
+ vsnprintf(buffer, kBufferSize, format, args);
+ va_end(args);
+ fprintf(stderr, buffer);
+}
+
+#endif
+
diff --git a/skia/corecg/SkFloat.cpp b/skia/corecg/SkFloat.cpp
new file mode 100644
index 0000000..bb96947
--- /dev/null
+++ b/skia/corecg/SkFloat.cpp
@@ -0,0 +1,404 @@
+/*
+ * Copyright (C) 2006-2008 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "SkFloat.h"
+#include "SkMath.h"
+
+#define EXP_BIAS (127+23)
+
+static int get_unsigned_exp(uint32_t packed)
+{
+ return (packed << 1 >> 24);
+}
+
+static unsigned get_unsigned_value(uint32_t packed)
+{
+ return (packed << 9 >> 9) | (1 << 23);
+}
+
+static int get_signed_value(int32_t packed)
+{
+ return SkApplySign(get_unsigned_value(packed), SkExtractSign(packed));
+}
+
+/////////////////////////////////////////////////////////////////////////
+
+int SkFloat::GetShift(int32_t packed, int shift)
+{
+ if (packed == 0)
+ return 0;
+
+ int exp = get_unsigned_exp(packed) - EXP_BIAS - shift;
+ int value = get_unsigned_value(packed);
+
+ if (exp >= 0)
+ {
+ if (exp > 8) // overflow
+ value = SK_MaxS32;
+ else
+ value <<= exp;
+ }
+ else
+ {
+ exp = -exp;
+ if (exp > 23) // underflow
+ value = 0;
+ else
+ value >>= exp;
+ }
+ return SkApplySign(value, SkExtractSign(packed));
+}
+
+/////////////////////////////////////////////////////////////////////////////////////
+
+int32_t SkFloat::SetShift(int value, int shift)
+{
+ if (value == 0)
+ return 0;
+
+ // record the sign and make value positive
+ int sign = SkExtractSign(value);
+ value = SkApplySign(value, sign);
+
+ if (value >> 24) // value is too big (has more than 24 bits set)
+ {
+ int bias = 8 - SkCLZ(value);
+ SkASSERT(bias > 0 && bias < 8);
+ value >>= bias;
+ shift += bias;
+ }
+ else
+ {
+ int zeros = SkCLZ(value << 8);
+ SkASSERT(zeros >= 0 && zeros <= 23);
+ value <<= zeros;
+ shift -= zeros;
+ }
+ // now value is left-aligned to 24 bits
+ SkASSERT((value >> 23) == 1);
+
+ shift += EXP_BIAS;
+ if (shift < 0) // underflow
+ return 0;
+ else
+ {
+ if (shift > 255) // overflow
+ {
+ shift = 255;
+ value = 0x00FFFFFF;
+ }
+ int32_t packed = sign << 31; // set the sign-bit
+ packed |= shift << 23; // store the packed exponent
+ packed |= ((unsigned)(value << 9) >> 9); // clear 24th bit of value (its implied)
+
+#ifdef SK_DEBUG
+ {
+ int n;
+
+ n = SkExtractSign(packed);
+ SkASSERT(n == sign);
+ n = get_unsigned_exp(packed);
+ SkASSERT(n == shift);
+ n = get_unsigned_value(packed);
+ SkASSERT(n == value);
+ }
+#endif
+ return packed;
+ }
+}
+
+int32_t SkFloat::Neg(int32_t packed)
+{
+ if (packed)
+ packed = packed ^ (1 << 31);
+ return packed;
+}
+
+int32_t SkFloat::Add(int32_t packed_a, int32_t packed_b)
+{
+ if (packed_a == 0)
+ return packed_b;
+ if (packed_b == 0)
+ return packed_a;
+
+ int exp_a = get_unsigned_exp(packed_a);
+ int exp_b = get_unsigned_exp(packed_b);
+ int exp_diff = exp_a - exp_b;
+
+ int shift_a = 0, shift_b = 0;
+ int exp;
+
+ if (exp_diff >= 0)
+ {
+ if (exp_diff > 24) // B is too small to contribute
+ return packed_a;
+ shift_b = exp_diff;
+ exp = exp_a;
+ }
+ else
+ {
+ exp_diff = -exp_diff;
+ if (exp_diff > 24) // A is too small to contribute
+ return packed_b;
+ shift_a = exp_diff;
+ exp = exp_b;
+ }
+
+ int value_a = get_signed_value(packed_a) >> shift_a;
+ int value_b = get_signed_value(packed_b) >> shift_b;
+
+ return SkFloat::SetShift(value_a + value_b, exp - EXP_BIAS);
+}
+
+#include "Sk64.h"
+
+static inline int32_t mul24(int32_t a, int32_t b)
+{
+ Sk64 tmp;
+
+ tmp.setMul(a, b);
+ tmp.roundRight(24);
+ return tmp.get32();
+}
+
+int32_t SkFloat::Mul(int32_t packed_a, int32_t packed_b)
+{
+ if (packed_a == 0 || packed_b == 0)
+ return 0;
+
+ int exp_a = get_unsigned_exp(packed_a);
+ int exp_b = get_unsigned_exp(packed_b);
+
+ int value_a = get_signed_value(packed_a);
+ int value_b = get_signed_value(packed_b);
+
+ return SkFloat::SetShift(mul24(value_a, value_b), exp_a + exp_b - 2*EXP_BIAS + 24);
+}
+
+int32_t SkFloat::MulInt(int32_t packed, int n)
+{
+ return Mul(packed, SetShift(n, 0));
+}
+
+int32_t SkFloat::Div(int32_t packed_n, int32_t packed_d)
+{
+ SkASSERT(packed_d != 0);
+
+ if (packed_n == 0)
+ return 0;
+
+ int exp_n = get_unsigned_exp(packed_n);
+ int exp_d = get_unsigned_exp(packed_d);
+
+ int value_n = get_signed_value(packed_n);
+ int value_d = get_signed_value(packed_d);
+
+ return SkFloat::SetShift(SkDivBits(value_n, value_d, 24), exp_n - exp_d - 24);
+}
+
+int32_t SkFloat::DivInt(int32_t packed, int n)
+{
+ return Div(packed, SetShift(n, 0));
+}
+
+int32_t SkFloat::Invert(int32_t packed)
+{
+ return Div(packed, SetShift(1, 0));
+}
+
+int32_t SkFloat::Sqrt(int32_t packed)
+{
+ if (packed < 0)
+ {
+ SkASSERT(!"can't sqrt a negative number");
+ return 0;
+ }
+
+ int exp = get_unsigned_exp(packed);
+ int value = get_unsigned_value(packed);
+
+ int nexp = exp - EXP_BIAS;
+ int root = SkSqrtBits(value << (nexp & 1), 26);
+ nexp >>= 1;
+ return SkFloat::SetShift(root, nexp - 11);
+}
+
+#if defined _WIN32 && _MSC_VER >= 1300 // disable warning : unreachable code
+#pragma warning ( push )
+#pragma warning ( disable : 4702 )
+#endif
+
+int32_t SkFloat::CubeRoot(int32_t packed)
+{
+ sk_throw();
+ return 0;
+}
+
+#if defined _WIN32 && _MSC_VER >= 1300
+#pragma warning ( pop )
+#endif
+
+static inline int32_t clear_high_bit(int32_t n)
+{
+ return ((uint32_t)(n << 1)) >> 1;
+}
+
+static inline int int_sign(int32_t a, int32_t b)
+{
+ return a > b ? 1 : (a < b ? -1 : 0);
+}
+
+int SkFloat::Cmp(int32_t packed_a, int32_t packed_b)
+{
+ packed_a = SkApplySign(clear_high_bit(packed_a), SkExtractSign(packed_a));
+ packed_b = SkApplySign(clear_high_bit(packed_b), SkExtractSign(packed_b));
+
+ return int_sign(packed_a, packed_b);
+}
+
+/////////////////////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_DEBUG
+
+#include "SkRandom.h"
+#ifdef SK_CAN_USE_FLOAT
+ #include "SkFloatingPoint.h"
+#endif
+
+void SkFloat::UnitTest()
+{
+#ifdef SK_SUPPORT_UNITTEST
+ SkFloat a, b, c, d;
+ int n;
+
+ a.setZero();
+ n = a.getInt();
+ SkASSERT(n == 0);
+
+ b.setInt(5);
+ n = b.getInt();
+ SkASSERT(n == 5);
+
+ c.setInt(-3);
+ n = c.getInt();
+ SkASSERT(n == -3);
+
+ d.setAdd(c, b);
+ SkDebugf("SkFloat: %d + %d = %d\n", c.getInt(), b.getInt(), d.getInt());
+
+ SkRandom rand;
+
+#ifdef SK_CAN_USE_FLOAT
+ int i;
+ for (i = 0; i < 1000; i++)
+ {
+ float fa, fb;
+ int aa = rand.nextS() >> 14;
+ int bb = rand.nextS() >> 14;
+ a.setInt(aa);
+ b.setInt(bb);
+ SkASSERT(a.getInt() == aa);
+ SkASSERT(b.getInt() == bb);
+
+ c.setAdd(a, b);
+ int cc = c.getInt();
+ SkASSERT(cc == aa + bb);
+
+ c.setSub(a, b);
+ cc = c.getInt();
+ SkASSERT(cc == aa - bb);
+
+ aa >>= 5;
+ bb >>= 5;
+ a.setInt(aa);
+ b.setInt(bb);
+ c.setMul(a, b);
+ cc = c.getInt();
+ SkASSERT(cc == aa * bb);
+ /////////////////////////////////////
+
+ aa = rand.nextS() >> 11;
+ a.setFixed(aa);
+ cc = a.getFixed();
+ SkASSERT(aa == cc);
+
+ bb = rand.nextS() >> 11;
+ b.setFixed(bb);
+ cc = b.getFixed();
+ SkASSERT(bb == cc);
+
+ cc = SkFixedMul(aa, bb);
+ c.setMul(a, b);
+ SkFixed dd = c.getFixed();
+ int diff = cc - dd;
+ SkASSERT(SkAbs32(diff) <= 1);
+
+ fa = (float)aa / 65536.0f;
+ fb = (float)bb / 65536.0f;
+ a.assertEquals(fa);
+ b.assertEquals(fb);
+ fa = a.getFloat();
+ fb = b.getFloat();
+
+ c.assertEquals(fa * fb, 1);
+
+ c.setDiv(a, b);
+ cc = SkFixedDiv(aa, bb);
+ dd = c.getFixed();
+ diff = cc - dd;
+ SkASSERT(SkAbs32(diff) <= 3);
+
+ c.assertEquals(fa / fb, 1);
+
+ SkASSERT((aa == bb) == (a == b));
+ SkASSERT((aa != bb) == (a != b));
+ SkASSERT((aa < bb) == (a < b));
+ SkASSERT((aa <= bb) == (a <= b));
+ SkASSERT((aa > bb) == (a > b));
+ SkASSERT((aa >= bb) == (a >= b));
+
+ if (aa < 0)
+ {
+ aa = -aa;
+ fa = -fa;
+ }
+ a.setFixed(aa);
+ c.setSqrt(a);
+ cc = SkFixedSqrt(aa);
+ dd = c.getFixed();
+ SkASSERT(dd == cc);
+
+ c.assertEquals(sk_float_sqrt(fa), 2);
+
+ // cuberoot
+#if 0
+ a.setInt(1);
+ a.cubeRoot();
+ a.assertEquals(1.0f, 0);
+ a.setInt(8);
+ a.cubeRoot();
+ a.assertEquals(2.0f, 0);
+ a.setInt(27);
+ a.cubeRoot();
+ a.assertEquals(3.0f, 0);
+#endif
+ }
+#endif
+#endif
+}
+
+#endif
diff --git a/skia/corecg/SkFloat.h b/skia/corecg/SkFloat.h
new file mode 100644
index 0000000..2a2abac
--- /dev/null
+++ b/skia/corecg/SkFloat.h
@@ -0,0 +1,118 @@
+/*
+ * Copyright (C) 2006-2008 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SkFloat_DEFINED
+#define SkFloat_DEFINED
+
+#include "SkFixed.h"
+
+class SkFloat {
+public:
+ SkFloat() {}
+
+ void setZero() { fPacked = 0; }
+// void setShift(int value, int shift) { fPacked = SetShift(value, shift); }
+ void setInt(int value) { fPacked = SetShift(value, 0); }
+ void setFixed(SkFixed value) { fPacked = SetShift(value, -16); }
+ void setFract(SkFract value) { fPacked = SetShift(value, -30); }
+
+// int getShift(int shift) const { return GetShift(fPacked, shift); }
+ int getInt() const { return GetShift(fPacked, 0); }
+ SkFixed getFixed() const { return GetShift(fPacked, -16); }
+ SkFract getFract() const { return GetShift(fPacked, -30); }
+
+ void abs() { fPacked = Abs(fPacked); }
+ void negate() { fPacked = Neg(fPacked); }
+
+ void shiftLeft(int bits) { fPacked = Shift(fPacked, bits); }
+ void setShiftLeft(const SkFloat& a, int bits) { fPacked = Shift(a.fPacked, bits); }
+
+ void shiftRight(int bits) { fPacked = Shift(fPacked, -bits); }
+ void setShiftRight(const SkFloat& a, int bits) { fPacked = Shift(a.fPacked, -bits); }
+
+ void add(const SkFloat& a) { fPacked = Add(fPacked, a.fPacked); }
+ void setAdd(const SkFloat& a, const SkFloat& b) { fPacked = Add(a.fPacked, b.fPacked); }
+
+ void sub(const SkFloat& a) { fPacked = Add(fPacked, Neg(a.fPacked)); }
+ void setSub(const SkFloat& a, const SkFloat& b) { fPacked = Add(a.fPacked, Neg(b.fPacked)); }
+
+ void mul(const SkFloat& a) { fPacked = Mul(fPacked, a.fPacked); }
+ void setMul(const SkFloat& a, const SkFloat& b) { fPacked = Mul(a.fPacked, b.fPacked); }
+
+ void div(const SkFloat& a) { fPacked = Div(fPacked, a.fPacked); }
+ void setDiv(const SkFloat& a, const SkFloat& b) { fPacked = Div(a.fPacked, b.fPacked); }
+
+ void sqrt() { fPacked = Sqrt(fPacked); }
+ void setSqrt(const SkFloat& a) { fPacked = Sqrt(a.fPacked); }
+ void cubeRoot() { fPacked = CubeRoot(fPacked); }
+ void setCubeRoot(const SkFloat& a) { fPacked = CubeRoot(a.fPacked); }
+
+ friend bool operator==(const SkFloat& a, const SkFloat& b) { return a.fPacked == b.fPacked; }
+ friend bool operator!=(const SkFloat& a, const SkFloat& b) { return a.fPacked != b.fPacked; }
+ friend bool operator<(const SkFloat& a, const SkFloat& b) { return Cmp(a.fPacked, b.fPacked) < 0; }
+ friend bool operator<=(const SkFloat& a, const SkFloat& b) { return Cmp(a.fPacked, b.fPacked) <= 0; }
+ friend bool operator>(const SkFloat& a, const SkFloat& b) { return Cmp(a.fPacked, b.fPacked) > 0; }
+ friend bool operator>=(const SkFloat& a, const SkFloat& b) { return Cmp(a.fPacked, b.fPacked) >= 0; }
+
+#ifdef SK_DEBUG
+ static void UnitTest();
+
+ void assertEquals(float f, int tolerance = 0)
+ {
+ union {
+ float fFloat;
+ int32_t fPacked;
+ } tmp;
+
+ tmp.fFloat = f;
+ int d = tmp.fPacked - fPacked;
+ SkASSERT(SkAbs32(d) <= tolerance);
+ }
+ float getFloat() const
+ {
+ union {
+ float fFloat;
+ int32_t fPacked;
+ } tmp;
+
+ tmp.fPacked = fPacked;
+ return tmp.fFloat;
+ }
+#endif
+
+private:
+ int32_t fPacked;
+
+ SkFloat(int32_t packed) : fPacked(fPacked) {}
+
+public:
+ static int GetShift(int32_t packed, int shift);
+ static int32_t SetShift(int value, int shift);
+ static int32_t Neg(int32_t);
+ static int32_t Abs(int32_t packed) { return (uint32_t)(packed << 1) >> 1; }
+ static int32_t Shift(int32_t, int bits);
+ static int32_t Add(int32_t, int32_t);
+ static int32_t Mul(int32_t, int32_t);
+ static int32_t MulInt(int32_t, int);
+ static int32_t Div(int32_t, int32_t);
+ static int32_t DivInt(int32_t, int);
+ static int32_t Invert(int32_t);
+ static int32_t Sqrt(int32_t);
+ static int32_t CubeRoot(int32_t);
+ static int Cmp(int32_t, int32_t);
+};
+
+#endif
diff --git a/skia/corecg/SkFloatBits.h b/skia/corecg/SkFloatBits.h
new file mode 100644
index 0000000..012770a
--- /dev/null
+++ b/skia/corecg/SkFloatBits.h
@@ -0,0 +1,43 @@
+#ifndef SkFloatBits_DEFINED
+#define SkFloatBits_DEFINED
+
+#include "SkTypes.h"
+
+/** Convert a sign-bit int (i.e. float interpreted as int) into a 2s compliement
+ int. This also converts -0 (0x80000000) to 0. Doing this to a float allows
+ it to be compared using normal C operators (<, <=, etc.)
+*/
+static inline int32_t SkSignBitTo2sCompliment(int32_t x) {
+ if (x < 0) {
+ x &= 0x7FFFFFFF;
+ x = -x;
+ }
+ return x;
+}
+
+#ifdef SK_CAN_USE_FLOAT
+
+union SkFloatIntUnion {
+ float fFloat;
+ int32_t fSignBitInt;
+};
+
+/** Return the float as a 2s compliment int. Just just be used to compare floats
+ to each other or against positive float-bit-constants (like 0)
+*/
+static int32_t SkFloatAsInt(float x) {
+ SkFloatIntUnion data;
+ data.fFloat = x;
+ return SkSignBitTo2sCompliment(data.fSignBitInt);
+}
+
+#endif
+
+#ifdef SK_SCALAR_IS_FLOAT
+ #define SkScalarAsInt(x) SkFloatAsInt(x)
+#else
+ #define SkScalarAsInt(x) (x)
+#endif
+
+#endif
+
diff --git a/skia/corecg/SkInterpolator.cpp b/skia/corecg/SkInterpolator.cpp
new file mode 100644
index 0000000..61ebf2b
--- /dev/null
+++ b/skia/corecg/SkInterpolator.cpp
@@ -0,0 +1,339 @@
+/*
+ * Copyright (C) 2006-2008 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "SkInterpolator.h"
+#include "SkMath.h"
+#include "SkTSearch.h"
+
+SkInterpolatorBase::SkInterpolatorBase() {
+ fStorage = NULL;
+ fTimes = NULL;
+ SkDEBUGCODE(fTimesArray = NULL;)
+}
+
+SkInterpolatorBase::~SkInterpolatorBase() {
+ if (fStorage) {
+ sk_free(fStorage);
+ }
+}
+
+void SkInterpolatorBase::reset(int elemCount, int frameCount) {
+ fFlags = 0;
+ fElemCount = SkToU8(elemCount);
+ fFrameCount = SkToS16(frameCount);
+ fRepeat = SK_Scalar1;
+ if (fStorage) {
+ sk_free(fStorage);
+ fStorage = NULL;
+ fTimes = NULL;
+ SkDEBUGCODE(fTimesArray = NULL);
+ }
+}
+
+/* Each value[] run is formated as:
+ <time (in msec)>
+ <blend>
+ <data[fElemCount]>
+
+ Totaling fElemCount+2 entries per keyframe
+*/
+
+bool SkInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const {
+ if (fFrameCount == 0) {
+ return false;
+ }
+
+ if (startTime) {
+ *startTime = fTimes[0].fTime;
+ }
+ if (endTime) {
+ *endTime = fTimes[fFrameCount - 1].fTime;
+ }
+ return true;
+}
+
+SkScalar SkInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime,
+ SkMSec nextTime, const SkScalar blend[4]) {
+ SkASSERT(time > prevTime && time < nextTime);
+
+ SkScalar t = SkScalarDiv((SkScalar)(time - prevTime),
+ (SkScalar)(nextTime - prevTime));
+ return blend ?
+ SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
+}
+
+SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T,
+ int* indexPtr, SkBool* exactPtr) const {
+ SkASSERT(fFrameCount > 0);
+ Result result = kNormal_Result;
+ if (fRepeat != SK_Scalar1) {
+ SkMSec startTime, endTime;
+ this->getDuration(&startTime, &endTime);
+ SkMSec totalTime = endTime - startTime;
+ SkMSec offsetTime = time - startTime;
+ endTime = SkScalarMulFloor(fRepeat, totalTime);
+ if (offsetTime >= endTime) {
+ SkScalar fraction = SkScalarFraction(fRepeat);
+ offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
+ SkScalarMulFloor(fraction, totalTime);
+ result = kFreezeEnd_Result;
+ } else {
+ int mirror = fFlags & kMirror;
+ offsetTime = offsetTime % (totalTime << mirror);
+ if (offsetTime > totalTime) { // can only be true if fMirror is true
+ offsetTime = (totalTime << 1) - offsetTime;
+ }
+ }
+ time = offsetTime + startTime;
+ }
+
+ int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time,
+ sizeof(SkTimeCode));
+
+ bool exact = true;
+
+ if (index < 0) {
+ index = ~index;
+ if (index == 0) {
+ result = kFreezeStart_Result;
+ } else if (index == fFrameCount) {
+ if (fFlags & kReset) {
+ index = 0;
+ } else {
+ index -= 1;
+ }
+ result = kFreezeEnd_Result;
+ } else {
+ exact = false;
+ }
+ }
+ SkASSERT(index < fFrameCount);
+ const SkTimeCode* nextTime = &fTimes[index];
+ SkMSec nextT = nextTime[0].fTime;
+ if (exact) {
+ *T = 0;
+ } else {
+ SkMSec prevT = nextTime[-1].fTime;
+ *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
+ }
+ *indexPtr = index;
+ *exactPtr = exact;
+ return result;
+}
+
+
+SkInterpolator::SkInterpolator() {
+ INHERITED::reset(0, 0);
+ fValues = NULL;
+ SkDEBUGCODE(fScalarsArray = NULL;)
+}
+
+SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
+ SkASSERT(elemCount > 0);
+ this->reset(elemCount, frameCount);
+}
+
+void SkInterpolator::reset(int elemCount, int frameCount) {
+ INHERITED::reset(elemCount, frameCount);
+ fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount +
+ sizeof(SkTimeCode)) * frameCount);
+ fTimes = (SkTimeCode*) fStorage;
+ fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount);
+#ifdef SK_DEBUG
+ fTimesArray = (SkTimeCode(*)[10]) fTimes;
+ fScalarsArray = (SkScalar(*)[10]) fValues;
+#endif
+}
+
+#define SK_Fixed1Third (SK_Fixed1/3)
+#define SK_Fixed2Third (SK_Fixed1*2/3)
+
+static const SkScalar gIdentityBlend[4] = {
+#ifdef SK_SCALAR_IS_FLOAT
+ 0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
+#else
+ SK_Fixed1Third, SK_Fixed1Third, SK_Fixed2Third, SK_Fixed2Third
+#endif
+};
+
+bool SkInterpolator::setKeyFrame(int index, SkMSec time,
+ const SkScalar values[], const SkScalar blend[4]) {
+ SkASSERT(values != NULL);
+
+ if (blend == NULL) {
+ blend = gIdentityBlend;
+ }
+
+ bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
+ sizeof(SkTimeCode));
+ SkASSERT(success);
+ if (success) {
+ SkTimeCode* timeCode = &fTimes[index];
+ timeCode->fTime = time;
+ memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
+ SkScalar* dst = &fValues[fElemCount * index];
+ memcpy(dst, values, fElemCount * sizeof(SkScalar));
+ }
+ return success;
+}
+
+SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
+ SkScalar values[]) const {
+ SkScalar T;
+ int index;
+ SkBool exact;
+ Result result = timeToT(time, &T, &index, &exact);
+ if (values) {
+ const SkScalar* nextSrc = &fValues[index * fElemCount];
+
+ if (exact) {
+ memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
+ } else {
+ SkASSERT(index > 0);
+
+ const SkScalar* prevSrc = nextSrc - fElemCount;
+
+ for (int i = fElemCount - 1; i >= 0; --i) {
+ values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
+ }
+ }
+ }
+ return result;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+typedef int Dot14;
+#define Dot14_ONE (1 << 14)
+#define Dot14_HALF (1 << 13)
+
+#define Dot14ToFloat(x) ((x) / 16384.f)
+
+static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
+ return (a * b + Dot14_HALF) >> 14;
+}
+
+static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
+ return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
+}
+
+static inline Dot14 pin_and_convert(SkScalar x) {
+ if (x <= 0) {
+ return 0;
+ }
+ if (x >= SK_Scalar1) {
+ return Dot14_ONE;
+ }
+ return SkScalarToFixed(x) >> 2;
+}
+
+SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
+ SkScalar cx, SkScalar cy) {
+ // pin to the unit-square, and convert to 2.14
+ Dot14 x = pin_and_convert(value);
+
+ if (x == 0) return 0;
+ if (x == Dot14_ONE) return SK_Scalar1;
+
+ Dot14 b = pin_and_convert(bx);
+ Dot14 c = pin_and_convert(cx);
+
+ // Now compute our coefficients from the control points
+ // t -> 3b
+ // t^2 -> 3c - 6b
+ // t^3 -> 3b - 3c + 1
+ Dot14 A = 3*b;
+ Dot14 B = 3*(c - 2*b);
+ Dot14 C = 3*(b - c) + Dot14_ONE;
+
+ // Now search for a t value given x
+ Dot14 t = Dot14_HALF;
+ Dot14 dt = Dot14_HALF;
+ for (int i = 0; i < 13; i++) {
+ dt >>= 1;
+ Dot14 guess = eval_cubic(t, A, B, C);
+ if (x < guess) {
+ t -= dt;
+ } else {
+ t += dt;
+ }
+ }
+
+ // Now we have t, so compute the coeff for Y and evaluate
+ b = pin_and_convert(by);
+ c = pin_and_convert(cy);
+ A = 3*b;
+ B = 3*(c - 2*b);
+ C = 3*(b - c) + Dot14_ONE;
+ return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_DEBUG
+
+#ifdef SK_SUPPORT_UNITTEST
+ static SkScalar* iset(SkScalar array[3], int a, int b, int c) {
+ array[0] = SkIntToScalar(a);
+ array[1] = SkIntToScalar(b);
+ array[2] = SkIntToScalar(c);
+ return array;
+ }
+#endif
+
+void SkInterpolator::UnitTest() {
+#ifdef SK_SUPPORT_UNITTEST
+ SkInterpolator inter(3, 2);
+ SkScalar v1[3], v2[3], v[3], vv[3];
+ Result result;
+
+ inter.setKeyFrame(0, 100, iset(v1, 10, 20, 30), 0);
+ inter.setKeyFrame(1, 200, iset(v2, 110, 220, 330));
+
+ result = inter.timeToValues(0, v);
+ SkASSERT(result == kFreezeStart_Result);
+ SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
+
+ result = inter.timeToValues(99, v);
+ SkASSERT(result == kFreezeStart_Result);
+ SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
+
+ result = inter.timeToValues(100, v);
+ SkASSERT(result == kNormal_Result);
+ SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
+
+ result = inter.timeToValues(200, v);
+ SkASSERT(result == kNormal_Result);
+ SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
+
+ result = inter.timeToValues(201, v);
+ SkASSERT(result == kFreezeEnd_Result);
+ SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
+
+ result = inter.timeToValues(150, v);
+ SkASSERT(result == kNormal_Result);
+ SkASSERT(memcmp(v, iset(vv, 60, 120, 180), sizeof(v)) == 0);
+
+ result = inter.timeToValues(125, v);
+ SkASSERT(result == kNormal_Result);
+ result = inter.timeToValues(175, v);
+ SkASSERT(result == kNormal_Result);
+#endif
+}
+
+#endif
+
diff --git a/skia/corecg/SkMath.cpp b/skia/corecg/SkMath.cpp
new file mode 100644
index 0000000..42ea107
--- /dev/null
+++ b/skia/corecg/SkMath.cpp
@@ -0,0 +1,820 @@
+/*
+ * Copyright (C) 2006-2008 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "SkMath.h"
+#include "SkCordic.h"
+#include "SkFloatingPoint.h"
+#include "Sk64.h"
+#include "SkScalar.h"
+
+#ifdef SK_SCALAR_IS_FLOAT
+ const uint32_t gIEEENotANumber = 0x7FFFFFFF;
+ const uint32_t gIEEEInfinity = 0x7F800000;
+#endif
+
+#define sub_shift(zeros, x, n) \
+ zeros -= n; \
+ x >>= n
+
+int SkCLZ_portable(uint32_t x) {
+ if (x == 0) {
+ return 32;
+ }
+
+#ifdef SK_CPU_HAS_CONDITIONAL_INSTR
+ int zeros = 31;
+ if (x & 0xFFFF0000) {
+ sub_shift(zeros, x, 16);
+ }
+ if (x & 0xFF00) {
+ sub_shift(zeros, x, 8);
+ }
+ if (x & 0xF0) {
+ sub_shift(zeros, x, 4);
+ }
+ if (x & 0xC) {
+ sub_shift(zeros, x, 2);
+ }
+ if (x & 0x2) {
+ sub_shift(zeros, x, 1);
+ }
+#else
+ int zeros = ((x >> 16) - 1) >> 31 << 4;
+ x <<= zeros;
+
+ int nonzero = ((x >> 24) - 1) >> 31 << 3;
+ zeros += nonzero;
+ x <<= nonzero;
+
+ nonzero = ((x >> 28) - 1) >> 31 << 2;
+ zeros += nonzero;
+ x <<= nonzero;
+
+ nonzero = ((x >> 30) - 1) >> 31 << 1;
+ zeros += nonzero;
+ x <<= nonzero;
+
+ zeros += (~x) >> 31;
+#endif
+
+ return zeros;
+}
+
+int32_t SkMulDiv(int32_t numer1, int32_t numer2, int32_t denom) {
+ SkASSERT(denom);
+
+ Sk64 tmp;
+ tmp.setMul(numer1, numer2);
+ tmp.div(denom, Sk64::kTrunc_DivOption);
+ return tmp.get32();
+}
+
+int32_t SkMulShift(int32_t a, int32_t b, unsigned shift) {
+ int sign = SkExtractSign(a ^ b);
+
+ if (shift > 63) {
+ return sign;
+ }
+
+ a = SkAbs32(a);
+ b = SkAbs32(b);
+
+ uint32_t ah = a >> 16;
+ uint32_t al = a & 0xFFFF;
+ uint32_t bh = b >> 16;
+ uint32_t bl = b & 0xFFFF;
+
+ uint32_t A = ah * bh;
+ uint32_t B = ah * bl + al * bh;
+ uint32_t C = al * bl;
+
+ /* [ A ]
+ [ B ]
+ [ C ]
+ */
+ uint32_t lo = C + (B << 16);
+ int32_t hi = A + (B >> 16) + (lo < C);
+
+ if (sign < 0) {
+ hi = -hi - Sk32ToBool(lo);
+ lo = 0 - lo;
+ }
+
+ if (shift == 0) {
+#ifdef SK_DEBUGx
+ SkASSERT(((int32_t)lo >> 31) == hi);
+#endif
+ return lo;
+ } else if (shift >= 32) {
+ return hi >> (shift - 32);
+ } else {
+#ifdef SK_DEBUGx
+ int32_t tmp = hi >> shift;
+ SkASSERT(tmp == 0 || tmp == -1);
+#endif
+ // we want (hi << (32 - shift)) | (lo >> shift) but rounded
+ int roundBit = (lo >> (shift - 1)) & 1;
+ return ((hi << (32 - shift)) | (lo >> shift)) + roundBit;
+ }
+}
+
+SkFixed SkFixedMul_portable(SkFixed a, SkFixed b) {
+#if 0
+ Sk64 tmp;
+
+ tmp.setMul(a, b);
+ tmp.shiftRight(16);
+ return tmp.fLo;
+#elif defined(SkLONGLONG)
+ return (SkLONGLONG)a * b >> 16;
+#else
+ int sa = SkExtractSign(a);
+ int sb = SkExtractSign(b);
+ // now make them positive
+ a = SkApplySign(a, sa);
+ b = SkApplySign(b, sb);
+
+ uint32_t ah = a >> 16;
+ uint32_t al = a & 0xFFFF;
+ uint32_t bh = b >> 16;
+ uint32_t bl = b & 0xFFFF;
+
+ uint32_t R = ah * b + al * bh + (al * bl >> 16);
+
+ return SkApplySign(R, sa ^ sb);
+#endif
+}
+
+SkFract SkFractMul_portable(SkFract a, SkFract b) {
+#if 0
+ Sk64 tmp;
+ tmp.setMul(a, b);
+ return tmp.getFract();
+#elif defined(SkLONGLONG)
+ return (SkLONGLONG)a * b >> 30;
+#else
+ int sa = SkExtractSign(a);
+ int sb = SkExtractSign(b);
+ // now make them positive
+ a = SkApplySign(a, sa);
+ b = SkApplySign(b, sb);
+
+ uint32_t ah = a >> 16;
+ uint32_t al = a & 0xFFFF;
+ uint32_t bh = b >> 16;
+ uint32_t bl = b & 0xFFFF;
+
+ uint32_t A = ah * bh;
+ uint32_t B = ah * bl + al * bh;
+ uint32_t C = al * bl;
+
+ /* [ A ]
+ [ B ]
+ [ C ]
+ */
+ uint32_t Lo = C + (B << 16);
+ uint32_t Hi = A + (B >>16) + (Lo < C);
+
+ SkASSERT((Hi >> 29) == 0); // else overflow
+
+ int32_t R = (Hi << 2) + (Lo >> 30);
+
+ return SkApplySign(R, sa ^ sb);
+#endif
+}
+
+int SkFixedMulCommon(SkFixed a, int b, int bias) {
+ // this function only works if b is 16bits
+ SkASSERT(b == (int16_t)b);
+ SkASSERT(b >= 0);
+
+ int sa = SkExtractSign(a);
+ a = SkApplySign(a, sa);
+ uint32_t ah = a >> 16;
+ uint32_t al = a & 0xFFFF;
+ uint32_t R = ah * b + ((al * b + bias) >> 16);
+ return SkApplySign(R, sa);
+}
+
+#ifdef SK_DEBUGx
+ #define TEST_FASTINVERT
+#endif
+
+SkFixed SkFixedFastInvert(SkFixed x) {
+/* Adapted (stolen) from Mathias' gglRecip()
+*/
+
+ if (x == SK_Fixed1) {
+ return SK_Fixed1;
+ }
+
+ int sign = SkExtractSign(x);
+ uint32_t a = SkApplySign(x, sign);
+
+ if (a <= 2) {
+ return SkApplySign(SK_MaxS32, sign);
+ }
+
+#ifdef TEST_FASTINVERT
+ SkFixed orig = a;
+ uint32_t slow = SkFixedDiv(SK_Fixed1, a);
+#endif
+
+ // normalize a
+ int lz = SkCLZ(a);
+ a = a << lz >> 16;
+
+ // compute 1/a approximation (0.5 <= a < 1.0)
+ uint32_t r = 0x17400 - a; // (2.90625 (~2.914) - 2*a) >> 1
+
+ // Newton-Raphson iteration:
+ // x = r*(2 - a*r) = ((r/2)*(1 - a*r/2))*4
+ r = ( (0x10000 - ((a*r)>>16)) * r ) >> 15;
+ r = ( (0x10000 - ((a*r)>>16)) * r ) >> (30 - lz);
+
+#ifdef TEST_FASTINVERT
+ SkDebugf("SkFixedFastInvert(%x %g) = %x %g Slow[%x %g]\n",
+ orig, orig/65536.,
+ r, r/65536.,
+ slow, slow/65536.);
+#endif
+
+ return SkApplySign(r, sign);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#define DIVBITS_ITER(n) \
+ case n: \
+ if ((numer = (numer << 1) - denom) >= 0) \
+ result |= 1 << (n - 1); else numer += denom
+
+int32_t SkDivBits(int32_t numer, int32_t denom, int shift_bias) {
+ SkASSERT(denom != 0);
+ if (numer == 0) {
+ return 0;
+ }
+
+ // make numer and denom positive, and sign hold the resulting sign
+ int32_t sign = SkExtractSign(numer ^ denom);
+ numer = SkAbs32(numer);
+ denom = SkAbs32(denom);
+
+ int nbits = SkCLZ(numer) - 1;
+ int dbits = SkCLZ(denom) - 1;
+ int bits = shift_bias - nbits + dbits;
+
+ if (bits < 0) { // answer will underflow
+ return 0;
+ }
+ if (bits > 31) { // answer will overflow
+ return SkApplySign(SK_MaxS32, sign);
+ }
+
+ denom <<= dbits;
+ numer <<= nbits;
+
+ SkFixed result = 0;
+
+ // do the first one
+ if ((numer -= denom) >= 0) {
+ result = 1;
+ } else {
+ numer += denom;
+ }
+
+ // Now fall into our switch statement if there are more bits to compute
+ if (bits > 0) {
+ // make room for the rest of the answer bits
+ result <<= bits;
+ switch (bits) {
+ DIVBITS_ITER(31); DIVBITS_ITER(30); DIVBITS_ITER(29);
+ DIVBITS_ITER(28); DIVBITS_ITER(27); DIVBITS_ITER(26);
+ DIVBITS_ITER(25); DIVBITS_ITER(24); DIVBITS_ITER(23);
+ DIVBITS_ITER(22); DIVBITS_ITER(21); DIVBITS_ITER(20);
+ DIVBITS_ITER(19); DIVBITS_ITER(18); DIVBITS_ITER(17);
+ DIVBITS_ITER(16); DIVBITS_ITER(15); DIVBITS_ITER(14);
+ DIVBITS_ITER(13); DIVBITS_ITER(12); DIVBITS_ITER(11);
+ DIVBITS_ITER(10); DIVBITS_ITER( 9); DIVBITS_ITER( 8);
+ DIVBITS_ITER( 7); DIVBITS_ITER( 6); DIVBITS_ITER( 5);
+ DIVBITS_ITER( 4); DIVBITS_ITER( 3); DIVBITS_ITER( 2);
+ // we merge these last two together, makes GCC make better ARM
+ default:
+ DIVBITS_ITER( 1);
+ }
+ }
+
+ if (result < 0) {
+ result = SK_MaxS32;
+ }
+ return SkApplySign(result, sign);
+}
+
+/* mod(float numer, float denom) seems to always return the sign
+ of the numer, so that's what we do too
+*/
+SkFixed SkFixedMod(SkFixed numer, SkFixed denom) {
+ int sn = SkExtractSign(numer);
+ int sd = SkExtractSign(denom);
+
+ numer = SkApplySign(numer, sn);
+ denom = SkApplySign(denom, sd);
+
+ if (numer < denom) {
+ return SkApplySign(numer, sn);
+ } else if (numer == denom) {
+ return 0;
+ } else {
+ SkFixed div = SkFixedDiv(numer, denom);
+ return SkApplySign(SkFixedMul(denom, div & 0xFFFF), sn);
+ }
+}
+
+/* www.worldserver.com/turk/computergraphics/FixedSqrt.pdf
+*/
+int32_t SkSqrtBits(int32_t x, int count) {
+ SkASSERT(x >= 0 && count > 0 && (unsigned)count <= 30);
+
+ uint32_t root = 0;
+ uint32_t remHi = 0;
+ uint32_t remLo = x;
+
+ do {
+ root <<= 1;
+
+ remHi = (remHi<<2) | (remLo>>30);
+ remLo <<= 2;
+
+ uint32_t testDiv = (root << 1) + 1;
+ if (remHi >= testDiv) {
+ remHi -= testDiv;
+ root++;
+ }
+ } while (--count >= 0);
+
+ return root;
+}
+
+int32_t SkCubeRootBits(int32_t value, int bits) {
+ SkASSERT(bits > 0);
+
+ int sign = SkExtractSign(value);
+ value = SkApplySign(value, sign);
+
+ uint32_t root = 0;
+ uint32_t curr = (uint32_t)value >> 30;
+ value <<= 2;
+
+ do {
+ root <<= 1;
+ uint32_t guess = root * root + root;
+ guess = (guess << 1) + guess; // guess *= 3
+ if (guess < curr) {
+ curr -= guess + 1;
+ root |= 1;
+ }
+ curr = (curr << 3) | ((uint32_t)value >> 29);
+ value <<= 3;
+ } while (--bits);
+
+ return SkApplySign(root, sign);
+}
+
+SkFixed SkFixedMean(SkFixed a, SkFixed b) {
+ Sk64 tmp;
+
+ tmp.setMul(a, b);
+ return tmp.getSqrt();
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_SCALAR_IS_FLOAT
+float SkScalarSinCos(float radians, float* cosValue) {
+ float sinValue = sk_float_sin(radians);
+
+ if (cosValue) {
+ *cosValue = sk_float_cos(radians);
+ if (SkScalarNearlyZero(*cosValue)) {
+ *cosValue = 0;
+ }
+ }
+
+ if (SkScalarNearlyZero(sinValue)) {
+ sinValue = 0;
+ }
+ return sinValue;
+}
+#endif
+
+#define INTERP_SINTABLE
+#define BUILD_TABLE_AT_RUNTIMEx
+
+#define kTableSize 256
+
+#ifdef BUILD_TABLE_AT_RUNTIME
+ static uint16_t gSkSinTable[kTableSize];
+
+ static void build_sintable(uint16_t table[]) {
+ for (int i = 0; i < kTableSize; i++) {
+ double rad = i * 3.141592653589793 / (2*kTableSize);
+ double val = sin(rad);
+ int ival = (int)(val * SK_Fixed1);
+ table[i] = SkToU16(ival);
+ }
+ }
+#else
+ #include "SkSinTable.h"
+#endif
+
+#define SK_Fract1024SizeOver2PI 0x28BE60 /* floatToFract(1024 / 2PI) */
+
+#ifdef INTERP_SINTABLE
+static SkFixed interp_table(const uint16_t table[], int index, int partial255) {
+ SkASSERT((unsigned)index < kTableSize);
+ SkASSERT((unsigned)partial255 <= 255);
+
+ SkFixed lower = table[index];
+ SkFixed upper = (index == kTableSize - 1) ? SK_Fixed1 : table[index + 1];
+
+ SkASSERT(lower < upper);
+ SkASSERT(lower >= 0);
+ SkASSERT(upper <= SK_Fixed1);
+
+ partial255 += (partial255 >> 7);
+ return lower + ((upper - lower) * partial255 >> 8);
+}
+#endif
+
+SkFixed SkFixedSinCos(SkFixed radians, SkFixed* cosValuePtr) {
+ SkASSERT(SK_ARRAY_COUNT(gSkSinTable) == kTableSize);
+
+#ifdef BUILD_TABLE_AT_RUNTIME
+ static bool gFirstTime = true;
+ if (gFirstTime) {
+ build_sintable(gSinTable);
+ gFirstTime = false;
+ }
+#endif
+
+ // make radians positive
+ SkFixed sinValue, cosValue;
+ int32_t cosSign = 0;
+ int32_t sinSign = SkExtractSign(radians);
+ radians = SkApplySign(radians, sinSign);
+ // scale it to 0...1023 ...
+
+#ifdef INTERP_SINTABLE
+ radians = SkMulDiv(radians, 2 * kTableSize * 256, SK_FixedPI);
+ int findex = radians & (kTableSize * 256 - 1);
+ int index = findex >> 8;
+ int partial = findex & 255;
+ sinValue = interp_table(gSkSinTable, index, partial);
+
+ findex = kTableSize * 256 - findex - 1;
+ index = findex >> 8;
+ partial = findex & 255;
+ cosValue = interp_table(gSkSinTable, index, partial);
+
+ int quad = ((unsigned)radians / (kTableSize * 256)) & 3;
+#else
+ radians = SkMulDiv(radians, 2 * kTableSize, SK_FixedPI);
+ int index = radians & (kTableSize - 1);
+
+ if (index == 0) {
+ sinValue = 0;
+ cosValue = SK_Fixed1;
+ } else {
+ sinValue = gSkSinTable[index];
+ cosValue = gSkSinTable[kTableSize - index];
+ }
+ int quad = ((unsigned)radians / kTableSize) & 3;
+#endif
+
+ if (quad & 1) {
+ SkTSwap<SkFixed>(sinValue, cosValue);
+ }
+ if (quad & 2) {
+ sinSign = ~sinSign;
+ }
+ if (((quad - 1) & 2) == 0) {
+ cosSign = ~cosSign;
+ }
+
+ // restore the sign for negative angles
+ sinValue = SkApplySign(sinValue, sinSign);
+ cosValue = SkApplySign(cosValue, cosSign);
+
+#ifdef SK_DEBUG
+ if (1) {
+ SkFixed sin2 = SkFixedMul(sinValue, sinValue);
+ SkFixed cos2 = SkFixedMul(cosValue, cosValue);
+ int diff = cos2 + sin2 - SK_Fixed1;
+ SkASSERT(SkAbs32(diff) <= 7);
+ }
+#endif
+
+ if (cosValuePtr) {
+ *cosValuePtr = cosValue;
+ }
+ return sinValue;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+SkFixed SkFixedTan(SkFixed radians) { return SkCordicTan(radians); }
+SkFixed SkFixedASin(SkFixed x) { return SkCordicASin(x); }
+SkFixed SkFixedACos(SkFixed x) { return SkCordicACos(x); }
+SkFixed SkFixedATan2(SkFixed y, SkFixed x) { return SkCordicATan2(y, x); }
+SkFixed SkFixedExp(SkFixed x) { return SkCordicExp(x); }
+SkFixed SkFixedLog(SkFixed x) { return SkCordicLog(x); }
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_DEBUG
+
+#include "SkRandom.h"
+
+#ifdef SkLONGLONG
+static int symmetric_fixmul(int a, int b) {
+ int sa = SkExtractSign(a);
+ int sb = SkExtractSign(b);
+
+ a = SkApplySign(a, sa);
+ b = SkApplySign(b, sb);
+
+#if 1
+ int c = (int)(((SkLONGLONG)a * b) >> 16);
+
+ return SkApplySign(c, sa ^ sb);
+#else
+ SkLONGLONG ab = (SkLONGLONG)a * b;
+ if (sa ^ sb) {
+ ab = -ab;
+ }
+ return ab >> 16;
+#endif
+}
+#endif
+
+#include "SkPoint.h"
+
+#ifdef SK_SUPPORT_UNITTEST
+static void check_length(const SkPoint& p, SkScalar targetLen) {
+ float x = SkScalarToFloat(p.fX);
+ float y = SkScalarToFloat(p.fY);
+ float len = sk_float_sqrt(x*x + y*y);
+
+ len /= SkScalarToFloat(targetLen);
+
+ SkASSERT(len > 0.999f && len < 1.001f);
+}
+#endif
+
+static void test_muldiv255() {
+ for (int a = 0; a <= 255; a++) {
+ for (int b = 0; b <= 255; b++) {
+ int ab = a * b;
+ float s = ab / 255.0f;
+ int round = (int)floorf(s + 0.5f);
+ int trunc = (int)floorf(s);
+
+ int iround = SkMulDiv255Round(a, b);
+ int itrunc = SkMulDiv255Trunc(a, b);
+
+ SkASSERT(iround == round);
+ SkASSERT(itrunc == trunc);
+
+ SkASSERT(itrunc <= iround);
+ SkASSERT(iround <= a);
+ SkASSERT(iround <= b);
+ }
+ }
+}
+
+void SkMath::UnitTest() {
+#ifdef SK_SUPPORT_UNITTEST
+ int i;
+ int32_t x;
+ SkRandom rand;
+
+ SkToS8(127); SkToS8(-128); SkToU8(255);
+ SkToS16(32767); SkToS16(-32768); SkToU16(65535);
+ SkToS32(2*1024*1024); SkToS32(-2*1024*1024); SkToU32(4*1024*1024);
+
+ SkCordic_UnitTest();
+
+ // these should assert
+#if 0
+ SkToS8(128);
+ SkToS8(-129);
+ SkToU8(256);
+ SkToU8(-5);
+
+ SkToS16(32768);
+ SkToS16(-32769);
+ SkToU16(65536);
+ SkToU16(-5);
+
+ if (sizeof(size_t) > 4) {
+ SkToS32(4*1024*1024);
+ SkToS32(-4*1024*1024);
+ SkToU32(5*1024*1024);
+ SkToU32(-5);
+ }
+#endif
+
+ test_muldiv255();
+
+#ifdef SK_DEBUG
+ {
+ SkScalar x = SK_ScalarNaN;
+ SkASSERT(SkScalarIsNaN(x));
+ }
+#endif
+
+ for (i = 1; i <= 10; i++) {
+ x = SkCubeRootBits(i*i*i, 11);
+ SkASSERT(x == i);
+ }
+
+ x = SkFixedSqrt(SK_Fixed1);
+ SkASSERT(x == SK_Fixed1);
+ x = SkFixedSqrt(SK_Fixed1/4);
+ SkASSERT(x == SK_Fixed1/2);
+ x = SkFixedSqrt(SK_Fixed1*4);
+ SkASSERT(x == SK_Fixed1*2);
+
+ x = SkFractSqrt(SK_Fract1);
+ SkASSERT(x == SK_Fract1);
+ x = SkFractSqrt(SK_Fract1/4);
+ SkASSERT(x == SK_Fract1/2);
+ x = SkFractSqrt(SK_Fract1/16);
+ SkASSERT(x == SK_Fract1/4);
+
+ for (i = 1; i < 100; i++) {
+ x = SkFixedSqrt(SK_Fixed1 * i * i);
+ SkASSERT(x == SK_Fixed1 * i);
+ }
+
+ for (i = 0; i < 1000; i++) {
+ int value = rand.nextS16();
+ int max = rand.nextU16();
+
+ int clamp = SkClampMax(value, max);
+ int clamp2 = value < 0 ? 0 : (value > max ? max : value);
+ SkASSERT(clamp == clamp2);
+ }
+
+ for (i = 0; i < 100000; i++) {
+ SkPoint p;
+
+ p.setLength(rand.nextS(), rand.nextS(), SK_Scalar1);
+ check_length(p, SK_Scalar1);
+ p.setLength(rand.nextS() >> 13, rand.nextS() >> 13, SK_Scalar1);
+ check_length(p, SK_Scalar1);
+ }
+
+ {
+ SkFixed result = SkFixedDiv(100, 100);
+ SkASSERT(result == SK_Fixed1);
+ result = SkFixedDiv(1, SK_Fixed1);
+ SkASSERT(result == 1);
+ }
+
+
+
+#ifdef SkLONGLONG
+ for (i = 0; i < 100000; i++) {
+ SkFixed numer = rand.nextS();
+ SkFixed denom = rand.nextS();
+ SkFixed result = SkFixedDiv(numer, denom);
+ SkLONGLONG check = ((SkLONGLONG)numer << 16) / denom;
+
+ (void)SkCLZ(numer);
+ (void)SkCLZ(denom);
+
+ SkASSERT(result != (SkFixed)SK_NaN32);
+ if (check > SK_MaxS32) {
+ check = SK_MaxS32;
+ } else if (check < -SK_MaxS32) {
+ check = SK_MinS32;
+ }
+ SkASSERT(result == (int32_t)check);
+
+ result = SkFractDiv(numer, denom);
+ check = ((SkLONGLONG)numer << 30) / denom;
+
+ SkASSERT(result != (SkFixed)SK_NaN32);
+ if (check > SK_MaxS32) {
+ check = SK_MaxS32;
+ } else if (check < -SK_MaxS32) {
+ check = SK_MinS32;
+ }
+ SkASSERT(result == (int32_t)check);
+
+ // make them <= 2^24, so we don't overflow in fixmul
+ numer = numer << 8 >> 8;
+ denom = denom << 8 >> 8;
+
+ result = SkFixedMul(numer, denom);
+ SkFixed r2 = symmetric_fixmul(numer, denom);
+// SkASSERT(result == r2);
+
+ result = SkFixedMul(numer, numer);
+ r2 = SkFixedSquare(numer);
+ SkASSERT(result == r2);
+
+#ifdef SK_CAN_USE_FLOAT
+ if (numer >= 0 && denom >= 0) {
+ SkFixed mean = SkFixedMean(numer, denom);
+ float fm = sk_float_sqrt(sk_float_abs(SkFixedToFloat(numer) * SkFixedToFloat(denom)));
+ SkFixed mean2 = SkFloatToFixed(fm);
+ int diff = SkAbs32(mean - mean2);
+ SkASSERT(diff <= 1);
+ }
+
+ {
+ SkFixed mod = SkFixedMod(numer, denom);
+ float n = SkFixedToFloat(numer);
+ float d = SkFixedToFloat(denom);
+ float m = sk_float_mod(n, d);
+#if 0
+ SkDebugf("%g mod %g = %g [%g]\n",
+ SkFixedToFloat(numer), SkFixedToFloat(denom),
+ SkFixedToFloat(mod), m);
+#endif
+ SkASSERT(mod == 0 || (mod < 0) == (m < 0)); // ensure the same sign
+ int diff = SkAbs32(mod - SkFloatToFixed(m));
+ SkASSERT((diff >> 7) == 0);
+ }
+#endif
+ }
+#endif
+
+#ifdef SK_CAN_USE_FLOAT
+ for (i = 0; i < 100000; i++) {
+ SkFract x = rand.nextU() >> 1;
+ double xx = (double)x / SK_Fract1;
+ SkFract xr = SkFractSqrt(x);
+ SkFract check = SkFloatToFract(sqrt(xx));
+ SkASSERT(xr == check || xr == check-1 || xr == check+1);
+
+ xr = SkFixedSqrt(x);
+ xx = (double)x / SK_Fixed1;
+ check = SkFloatToFixed(sqrt(xx));
+ SkASSERT(xr == check || xr == check-1);
+
+ xr = SkSqrt32(x);
+ xx = (double)x;
+ check = (int32_t)sqrt(xx);
+ SkASSERT(xr == check || xr == check-1);
+ }
+#endif
+
+#if !defined(SK_SCALAR_IS_FLOAT) && defined(SK_CAN_USE_FLOAT)
+ {
+ SkFixed s, c;
+ s = SkFixedSinCos(0, &c);
+ SkASSERT(s == 0);
+ SkASSERT(c == SK_Fixed1);
+ }
+
+ int maxDiff = 0;
+ for (i = 0; i < 10000; i++) {
+ SkFixed rads = rand.nextS() >> 10;
+ double frads = SkFixedToFloat(rads);
+
+ SkFixed s, c;
+ s = SkScalarSinCos(rads, &c);
+
+ double fs = sin(frads);
+ double fc = cos(frads);
+
+ SkFixed is = SkFloatToFixed(fs);
+ SkFixed ic = SkFloatToFixed(fc);
+
+ maxDiff = SkMax32(maxDiff, SkAbs32(is - s));
+ maxDiff = SkMax32(maxDiff, SkAbs32(ic - c));
+ }
+ SkDebugf("SinCos: maximum error = %d\n", maxDiff);
+#endif
+#endif
+}
+
+#endif
+
diff --git a/skia/corecg/SkMatrix.cpp b/skia/corecg/SkMatrix.cpp
new file mode 100644
index 0000000..78f6688
--- /dev/null
+++ b/skia/corecg/SkMatrix.cpp
@@ -0,0 +1,1678 @@
+/* libs/corecg/SkMatrix.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkMatrix.h"
+#include "Sk64.h"
+#include "SkFloatBits.h"
+
+#ifdef SK_SCALAR_IS_FLOAT
+ #define kMatrix22Elem SK_Scalar1
+#else
+ #define kMatrix22Elem SK_Fract1
+#endif
+
+/* [scale-x skew-x trans-x] [X] [X']
+ [skew-y scale-y trans-y] * [Y] = [Y']
+ [persp-0 persp-1 persp-2] [1] [1 ]
+*/
+
+void SkMatrix::reset() {
+ fMat[kMScaleX] = fMat[kMScaleY] = SK_Scalar1;
+ fMat[kMSkewX] = fMat[kMSkewY] =
+ fMat[kMTransX] = fMat[kMTransY] =
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+ fMat[kMPersp2] = kMatrix22Elem;
+
+ this->setTypeMask(kIdentity_Mask | kRectStaysRect_Mask);
+}
+
+static inline int has_perspective(const SkMatrix& matrix) {
+ return matrix.getType() & SkMatrix::kPerspective_Mask;
+}
+
+// this guy aligns with the masks, so we can compute a mask from a varaible 0/1
+enum {
+ kTranslate_Shift,
+ kScale_Shift,
+ kAffine_Shift,
+ kPerspective_Shift,
+ kRectStaysRect_Shift
+};
+
+#ifdef SK_SCALAR_IS_FLOAT
+ static const int32_t kScalar1Int = 0x3f800000;
+ static const int32_t kPersp1Int = 0x3f800000;
+#else
+ #define scalarAsInt(x) (x)
+ static const int32_t kScalar1Int = (1 << 16);
+ static const int32_t kPersp1Int = (1 << 30);
+#endif
+
+uint8_t SkMatrix::computeTypeMask() const {
+ unsigned mask = 0;
+
+ if (SkScalarAsInt(fMat[kMPersp0]) | SkScalarAsInt(fMat[kMPersp1]) |
+ (SkScalarAsInt(fMat[kMPersp2]) - kPersp1Int)) {
+ mask |= kPerspective_Mask;
+ }
+
+ if (SkScalarAsInt(fMat[kMTransX]) | SkScalarAsInt(fMat[kMTransY])) {
+ mask |= kTranslate_Mask;
+ }
+
+ int m00 = SkScalarAsInt(fMat[SkMatrix::kMScaleX]);
+ int m01 = SkScalarAsInt(fMat[SkMatrix::kMSkewX]);
+ int m10 = SkScalarAsInt(fMat[SkMatrix::kMSkewY]);
+ int m11 = SkScalarAsInt(fMat[SkMatrix::kMScaleY]);
+
+ if (m01 | m10) {
+ mask |= kAffine_Mask;
+ }
+
+ if ((m00 - kScalar1Int) | (m11 - kScalar1Int)) {
+ mask |= kScale_Mask;
+ }
+
+ if ((mask & kPerspective_Mask) == 0) {
+ // map non-zero to 1
+ m00 = m00 != 0;
+ m01 = m01 != 0;
+ m10 = m10 != 0;
+ m11 = m11 != 0;
+
+ // record if the (p)rimary and (s)econdary diagonals are all 0 or
+ // all non-zero (answer is 0 or 1)
+ int dp0 = (m00 | m11) ^ 1; // true if both are 0
+ int dp1 = m00 & m11; // true if both are 1
+ int ds0 = (m01 | m10) ^ 1; // true if both are 0
+ int ds1 = m01 & m10; // true if both are 1
+
+ // return 1 if primary is 1 and secondary is 0 or
+ // primary is 0 and secondary is 1
+ mask |= ((dp0 & ds1) | (dp1 & ds0)) << kRectStaysRect_Shift;
+ }
+
+ return SkToU8(mask);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkMatrix::setTranslate(SkScalar dx, SkScalar dy) {
+ if (SkScalarAsInt(dx) | SkScalarAsInt(dy)) {
+ fMat[kMTransX] = dx;
+ fMat[kMTransY] = dy;
+
+ fMat[kMScaleX] = fMat[kMScaleY] = SK_Scalar1;
+ fMat[kMSkewX] = fMat[kMSkewY] =
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+ fMat[kMPersp2] = kMatrix22Elem;
+
+ this->setTypeMask(kTranslate_Mask | kRectStaysRect_Mask);
+ } else {
+ this->reset();
+ }
+}
+
+bool SkMatrix::preTranslate(SkScalar dx, SkScalar dy) {
+ if (has_perspective(*this)) {
+ SkMatrix m;
+ m.setTranslate(dx, dy);
+ return this->preConcat(m);
+ }
+
+ if (SkScalarAsInt(dx) | SkScalarAsInt(dy)) {
+ fMat[kMTransX] += SkScalarMul(fMat[kMScaleX], dx) +
+ SkScalarMul(fMat[kMSkewX], dy);
+ fMat[kMTransY] += SkScalarMul(fMat[kMSkewY], dx) +
+ SkScalarMul(fMat[kMScaleY], dy);
+
+ this->setTypeMask(kUnknown_Mask);
+ }
+ return true;
+}
+
+bool SkMatrix::postTranslate(SkScalar dx, SkScalar dy) {
+ if (has_perspective(*this)) {
+ SkMatrix m;
+ m.setTranslate(dx, dy);
+ return this->postConcat(m);
+ }
+
+ if (SkScalarAsInt(dx) | SkScalarAsInt(dy)) {
+ fMat[kMTransX] += dx;
+ fMat[kMTransY] += dy;
+ this->setTypeMask(kUnknown_Mask);
+ }
+ return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkMatrix::setScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
+ fMat[kMScaleX] = sx;
+ fMat[kMScaleY] = sy;
+ fMat[kMTransX] = px - SkScalarMul(sx, px);
+ fMat[kMTransY] = py - SkScalarMul(sy, py);
+ fMat[kMPersp2] = kMatrix22Elem;
+
+ fMat[kMSkewX] = fMat[kMSkewY] =
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+
+ this->setTypeMask(kScale_Mask | kTranslate_Mask | kRectStaysRect_Mask);
+}
+
+void SkMatrix::setScale(SkScalar sx, SkScalar sy) {
+ fMat[kMScaleX] = sx;
+ fMat[kMScaleY] = sy;
+ fMat[kMPersp2] = kMatrix22Elem;
+
+ fMat[kMTransX] = fMat[kMTransY] =
+ fMat[kMSkewX] = fMat[kMSkewY] =
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+
+ this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
+}
+
+bool SkMatrix::preScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
+ SkMatrix m;
+ m.setScale(sx, sy, px, py);
+ return this->preConcat(m);
+}
+
+bool SkMatrix::preScale(SkScalar sx, SkScalar sy) {
+ SkMatrix m;
+ m.setScale(sx, sy);
+ return this->preConcat(m);
+}
+
+bool SkMatrix::postScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
+ SkMatrix m;
+ m.setScale(sx, sy, px, py);
+ return this->postConcat(m);
+}
+
+bool SkMatrix::postScale(SkScalar sx, SkScalar sy) {
+ SkMatrix m;
+ m.setScale(sx, sy);
+ return this->postConcat(m);
+}
+
+#ifdef SK_SCALAR_IS_FIXED
+ static inline SkFixed roundidiv(SkFixed numer, int denom) {
+ int ns = numer >> 31;
+ int ds = denom >> 31;
+ numer = (numer ^ ns) - ns;
+ denom = (denom ^ ds) - ds;
+
+ SkFixed answer = (numer + (denom >> 1)) / denom;
+ int as = ns ^ ds;
+ return (answer ^ as) - as;
+ }
+#endif
+
+// this guy perhaps can go away, if we have a fract/high-precision way to
+// scale matrices
+bool SkMatrix::postIDiv(int divx, int divy) {
+ if (divx == 0 || divy == 0) {
+ return false;
+ }
+
+#ifdef SK_SCALAR_IS_FIXED
+ fMat[kMScaleX] = roundidiv(fMat[kMScaleX], divx);
+ fMat[kMSkewX] = roundidiv(fMat[kMSkewX], divx);
+ fMat[kMTransX] = roundidiv(fMat[kMTransX], divx);
+
+ fMat[kMScaleY] = roundidiv(fMat[kMScaleY], divy);
+ fMat[kMSkewY] = roundidiv(fMat[kMSkewY], divy);
+ fMat[kMTransY] = roundidiv(fMat[kMTransY], divy);
+#else
+ const float invX = 1.f / divx;
+ const float invY = 1.f / divy;
+
+ fMat[kMScaleX] *= invX;
+ fMat[kMSkewX] *= invX;
+ fMat[kMTransX] *= invX;
+
+ fMat[kMScaleY] *= invY;
+ fMat[kMSkewY] *= invY;
+ fMat[kMTransY] *= invY;
+#endif
+
+ this->setTypeMask(kUnknown_Mask);
+ return true;
+}
+
+////////////////////////////////////////////////////////////////////////////////////
+
+void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV,
+ SkScalar px, SkScalar py) {
+ const SkScalar oneMinusCosV = SK_Scalar1 - cosV;
+
+ fMat[kMScaleX] = cosV;
+ fMat[kMSkewX] = -sinV;
+ fMat[kMTransX] = SkScalarMul(sinV, py) + SkScalarMul(oneMinusCosV, px);
+
+ fMat[kMSkewY] = sinV;
+ fMat[kMScaleY] = cosV;
+ fMat[kMTransY] = SkScalarMul(-sinV, px) + SkScalarMul(oneMinusCosV, py);
+
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+ fMat[kMPersp2] = kMatrix22Elem;
+
+ this->setTypeMask(kUnknown_Mask);
+}
+
+void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV) {
+ fMat[kMScaleX] = cosV;
+ fMat[kMSkewX] = -sinV;
+ fMat[kMTransX] = 0;
+
+ fMat[kMSkewY] = sinV;
+ fMat[kMScaleY] = cosV;
+ fMat[kMTransY] = 0;
+
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+ fMat[kMPersp2] = kMatrix22Elem;
+
+ this->setTypeMask(kUnknown_Mask);
+}
+
+void SkMatrix::setRotate(SkScalar degrees, SkScalar px, SkScalar py) {
+ SkScalar sinV, cosV;
+ sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
+ this->setSinCos(sinV, cosV, px, py);
+}
+
+void SkMatrix::setRotate(SkScalar degrees) {
+ SkScalar sinV, cosV;
+ sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
+ this->setSinCos(sinV, cosV);
+}
+
+bool SkMatrix::preRotate(SkScalar degrees, SkScalar px, SkScalar py) {
+ SkMatrix m;
+ m.setRotate(degrees, px, py);
+ return this->preConcat(m);
+}
+
+bool SkMatrix::preRotate(SkScalar degrees) {
+ SkMatrix m;
+ m.setRotate(degrees);
+ return this->preConcat(m);
+}
+
+bool SkMatrix::postRotate(SkScalar degrees, SkScalar px, SkScalar py) {
+ SkMatrix m;
+ m.setRotate(degrees, px, py);
+ return this->postConcat(m);
+}
+
+bool SkMatrix::postRotate(SkScalar degrees) {
+ SkMatrix m;
+ m.setRotate(degrees);
+ return this->postConcat(m);
+}
+
+////////////////////////////////////////////////////////////////////////////////////
+
+void SkMatrix::setSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
+ fMat[kMScaleX] = SK_Scalar1;
+ fMat[kMSkewX] = sx;
+ fMat[kMTransX] = SkScalarMul(-sx, py);
+
+ fMat[kMSkewY] = sy;
+ fMat[kMScaleY] = SK_Scalar1;
+ fMat[kMTransY] = SkScalarMul(-sy, px);
+
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+ fMat[kMPersp2] = kMatrix22Elem;
+
+ this->setTypeMask(kUnknown_Mask);
+}
+
+void SkMatrix::setSkew(SkScalar sx, SkScalar sy) {
+ fMat[kMScaleX] = SK_Scalar1;
+ fMat[kMSkewX] = sx;
+ fMat[kMTransX] = 0;
+
+ fMat[kMSkewY] = sy;
+ fMat[kMScaleY] = SK_Scalar1;
+ fMat[kMTransY] = 0;
+
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+ fMat[kMPersp2] = kMatrix22Elem;
+
+ this->setTypeMask(kUnknown_Mask);
+}
+
+bool SkMatrix::preSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
+ SkMatrix m;
+ m.setSkew(sx, sy, px, py);
+ return this->preConcat(m);
+}
+
+bool SkMatrix::preSkew(SkScalar sx, SkScalar sy) {
+ SkMatrix m;
+ m.setSkew(sx, sy);
+ return this->preConcat(m);
+}
+
+bool SkMatrix::postSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
+ SkMatrix m;
+ m.setSkew(sx, sy, px, py);
+ return this->postConcat(m);
+}
+
+bool SkMatrix::postSkew(SkScalar sx, SkScalar sy) {
+ SkMatrix m;
+ m.setSkew(sx, sy);
+ return this->postConcat(m);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+bool SkMatrix::setRectToRect(const SkRect& src, const SkRect& dst,
+ ScaleToFit align)
+{
+ if (src.isEmpty()) {
+ this->reset();
+ return false;
+ }
+
+ if (dst.isEmpty()) {
+ bzero(fMat, 8 * sizeof(SkScalar));
+ this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
+ } else {
+ SkScalar tx, sx = SkScalarDiv(dst.width(), src.width());
+ SkScalar ty, sy = SkScalarDiv(dst.height(), src.height());
+ bool xLarger = false;
+
+ if (align != kFill_ScaleToFit) {
+ if (sx > sy) {
+ xLarger = true;
+ sx = sy;
+ } else {
+ sy = sx;
+ }
+ }
+
+ tx = dst.fLeft - SkScalarMul(src.fLeft, sx);
+ ty = dst.fTop - SkScalarMul(src.fTop, sy);
+ if (align == kCenter_ScaleToFit || align == kEnd_ScaleToFit) {
+ SkScalar diff;
+
+ if (xLarger) {
+ diff = dst.width() - SkScalarMul(src.width(), sy);
+ } else {
+ diff = dst.height() - SkScalarMul(src.height(), sy);
+ }
+
+ if (align == kCenter_ScaleToFit) {
+ diff = SkScalarHalf(diff);
+ }
+
+ if (xLarger) {
+ tx += diff;
+ } else {
+ ty += diff;
+ }
+ }
+
+ fMat[kMScaleX] = sx;
+ fMat[kMScaleY] = sy;
+ fMat[kMTransX] = tx;
+ fMat[kMTransY] = ty;
+ fMat[kMSkewX] = fMat[kMSkewY] =
+ fMat[kMPersp0] = fMat[kMPersp1] = 0;
+
+ this->setTypeMask(kScale_Mask | kTranslate_Mask | kRectStaysRect_Mask);
+ }
+ // shared cleanup
+ fMat[kMPersp2] = kMatrix22Elem;
+ return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_SCALAR_IS_FLOAT
+ static inline int fixmuladdmul(float a, float b, float c, float d,
+ float* result) {
+ *result = a * b + c * d;
+ return true;
+ }
+
+ static inline int fixmuladdmulshiftmul(float a, float b, float c, float d,
+ int /*shift not used*/, float scale, float* result) {
+ *result = (a * b + c * d) * scale;
+ return true;
+ }
+
+ static inline bool rowcol3(const float row[], const float col[],
+ float* result) {
+ *result = row[0] * col[0] + row[1] * col[3] + row[2] * col[6];
+ return true;
+ }
+
+ static inline int negifaddoverflows(float& result, float a, float b) {
+ result = a + b;
+ return 0;
+ }
+#else
+ static inline bool fixmuladdmul(SkFixed a, SkFixed b, SkFixed c, SkFixed d,
+ SkFixed* result) {
+ Sk64 tmp1, tmp2;
+ tmp1.setMul(a, b);
+ tmp2.setMul(c, d);
+ tmp1.add(tmp2);
+ if (tmp1.isFixed()) {
+ *result = tmp1.getFixed();
+ return true;
+ }
+ return false;
+ }
+
+ static inline bool fixmuladdmulshiftmul(SkFixed a, SkFixed b, SkFixed c,
+ SkFixed d, int shift, SkFixed scale, SkFixed* result) {
+ Sk64 tmp1, tmp2;
+ tmp1.setMul(a, b);
+ tmp2.setMul(c, d);
+ tmp1.add(tmp2);
+
+ int32_t hi = SkAbs32(tmp1.fHi);
+ int afterShift = 16;
+ if (hi >> 15) {
+ int clz = 17 - SkCLZ(hi);
+ SkASSERT(clz > 0 && clz <= 16);
+ afterShift -= clz;
+ shift += clz;
+ }
+
+ tmp1.roundRight(shift + 16);
+ SkASSERT(tmp1.is32());
+
+ tmp1.setMul(tmp1.get32(), scale);
+ tmp1.roundRight(afterShift);
+ if (tmp1.is32()) {
+ *result = tmp1.get32();
+ return true;
+ }
+ return false;
+ }
+
+ static inline SkFixed fracmuladdmul(SkFixed a, SkFract b, SkFixed c,
+ SkFract d) {
+ Sk64 tmp1, tmp2;
+ tmp1.setMul(a, b);
+ tmp2.setMul(c, d);
+ tmp1.add(tmp2);
+ return tmp1.getFract();
+ }
+
+ static inline bool rowcol3(const SkFixed row[], const SkFixed col[],
+ SkFixed* result) {
+ Sk64 tmp1, tmp2;
+
+ tmp1.setMul(row[0], col[0]); // N * fixed
+ tmp2.setMul(row[1], col[3]); // N * fixed
+ tmp1.add(tmp2);
+
+ tmp2.setMul(row[2], col[6]); // N * fract
+ tmp2.roundRight(14); // make it fixed
+ tmp1.add(tmp2);
+
+ if (tmp1.isFixed()) {
+ *result = tmp1.getFixed();
+ return true;
+ }
+ return false;
+ }
+
+ static inline int negifaddoverflows(SkFixed& result, SkFixed a, SkFixed b) {
+ SkFixed c = a + b;
+ result = c;
+ return (c ^ a) & (c ^ b);
+ }
+#endif
+
+static void normalize_perspective(SkScalar mat[9]) {
+ if (SkScalarAbs(mat[SkMatrix::kMPersp2]) > kMatrix22Elem) {
+ for (int i = 0; i < 9; i++)
+ mat[i] = SkScalarHalf(mat[i]);
+ }
+}
+
+bool SkMatrix::setConcat(const SkMatrix& a, const SkMatrix& b) {
+ TypeMask aType = a.getType();
+ TypeMask bType = b.getType();
+
+ if (0 == aType) {
+ *this = b;
+ } else if (0 == bType) {
+ *this = a;
+ } else {
+ SkMatrix tmp;
+
+ if ((aType | bType) & kPerspective_Mask) {
+ if (!rowcol3(&a.fMat[0], &b.fMat[0], &tmp.fMat[kMScaleX])) {
+ return false;
+ }
+ if (!rowcol3(&a.fMat[0], &b.fMat[1], &tmp.fMat[kMSkewX])) {
+ return false;
+ }
+ if (!rowcol3(&a.fMat[0], &b.fMat[2], &tmp.fMat[kMTransX])) {
+ return false;
+ }
+
+ if (!rowcol3(&a.fMat[3], &b.fMat[0], &tmp.fMat[kMSkewY])) {
+ return false;
+ }
+ if (!rowcol3(&a.fMat[3], &b.fMat[1], &tmp.fMat[kMScaleY])) {
+ return false;
+ }
+ if (!rowcol3(&a.fMat[3], &b.fMat[2], &tmp.fMat[kMTransY])) {
+ return false;
+ }
+
+ if (!rowcol3(&a.fMat[6], &b.fMat[0], &tmp.fMat[kMPersp0])) {
+ return false;
+ }
+ if (!rowcol3(&a.fMat[6], &b.fMat[1], &tmp.fMat[kMPersp1])) {
+ return false;
+ }
+ if (!rowcol3(&a.fMat[6], &b.fMat[2], &tmp.fMat[kMPersp2])) {
+ return false;
+ }
+
+ normalize_perspective(tmp.fMat);
+ } else { // not perspective
+ if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMScaleX],
+ a.fMat[kMSkewX], b.fMat[kMSkewY], &tmp.fMat[kMScaleX])) {
+ return false;
+ }
+ if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMSkewX],
+ a.fMat[kMSkewX], b.fMat[kMScaleY], &tmp.fMat[kMSkewX])) {
+ return false;
+ }
+ if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMTransX],
+ a.fMat[kMSkewX], b.fMat[kMTransY], &tmp.fMat[kMTransX])) {
+ return false;
+ }
+ if (negifaddoverflows(tmp.fMat[kMTransX], tmp.fMat[kMTransX],
+ a.fMat[kMTransX]) < 0) {
+ return false;
+ }
+
+ if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMScaleX],
+ a.fMat[kMScaleY], b.fMat[kMSkewY], &tmp.fMat[kMSkewY])) {
+ return false;
+ }
+ if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMSkewX],
+ a.fMat[kMScaleY], b.fMat[kMScaleY], &tmp.fMat[kMScaleY])) {
+ return false;
+ }
+ if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMTransX],
+ a.fMat[kMScaleY], b.fMat[kMTransY], &tmp.fMat[kMTransY])) {
+ return false;
+ }
+ if (negifaddoverflows(tmp.fMat[kMTransY], tmp.fMat[kMTransY],
+ a.fMat[kMTransY]) < 0) {
+ return false;
+ }
+
+ tmp.fMat[kMPersp0] = tmp.fMat[kMPersp1] = 0;
+ tmp.fMat[kMPersp2] = kMatrix22Elem;
+ }
+ *this = tmp;
+ }
+ this->setTypeMask(kUnknown_Mask);
+ return true;
+}
+
+bool SkMatrix::preConcat(const SkMatrix& mat) {
+ return this->setConcat(*this, mat);
+}
+
+bool SkMatrix::postConcat(const SkMatrix& mat) {
+ return this->setConcat(mat, *this);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_SCALAR_IS_FLOAT
+ #define SkPerspMul(a, b) SkScalarMul(a, b)
+ #define SkScalarMulShift(a, b, s) SkScalarMul(a, b)
+ static float sk_inv_determinant(const float mat[9], int isPerspective,
+ int* /* (only used in Fixed case) */) {
+ double det;
+
+ if (isPerspective) {
+ det = mat[SkMatrix::kMScaleX] * ((double)mat[SkMatrix::kMScaleY] * mat[SkMatrix::kMPersp2] - (double)mat[SkMatrix::kMTransY] * mat[SkMatrix::kMPersp1]) +
+ mat[SkMatrix::kMSkewX] * ((double)mat[SkMatrix::kMTransY] * mat[SkMatrix::kMPersp0] - (double)mat[SkMatrix::kMSkewY] * mat[SkMatrix::kMPersp2]) +
+ mat[SkMatrix::kMTransX] * ((double)mat[SkMatrix::kMSkewY] * mat[SkMatrix::kMPersp1] - (double)mat[SkMatrix::kMScaleY] * mat[SkMatrix::kMPersp0]);
+ } else {
+ det = (double)mat[SkMatrix::kMScaleX] * mat[SkMatrix::kMScaleY] - (double)mat[SkMatrix::kMSkewX] * mat[SkMatrix::kMSkewY];
+ }
+
+ if (SkScalarNearlyZero((float)det)) {
+ return 0;
+ }
+ return (float)(1.0 / det);
+ }
+#else
+ #define SkPerspMul(a, b) SkFractMul(a, b)
+ #define SkScalarMulShift(a, b, s) SkMulShift(a, b, s)
+ static void set_muladdmul(Sk64* dst, int32_t a, int32_t b, int32_t c,
+ int32_t d) {
+ Sk64 tmp;
+ dst->setMul(a, b);
+ tmp.setMul(c, d);
+ dst->add(tmp);
+ }
+
+ static SkFixed sk_inv_determinant(const SkFixed mat[9], int isPerspective,
+ int* shift) {
+ Sk64 tmp1, tmp2;
+
+ if (isPerspective) {
+ tmp1.setMul(mat[SkMatrix::kMScaleX], fracmuladdmul(mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp2], -mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp1]));
+ tmp2.setMul(mat[SkMatrix::kMSkewX], fracmuladdmul(mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp0], -mat[SkMatrix::kMSkewY], mat[SkMatrix::kMPersp2]));
+ tmp1.add(tmp2);
+ tmp2.setMul(mat[SkMatrix::kMTransX], fracmuladdmul(mat[SkMatrix::kMSkewY], mat[SkMatrix::kMPersp1], -mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp0]));
+ tmp1.add(tmp2);
+ } else {
+ tmp1.setMul(mat[SkMatrix::kMScaleX], mat[SkMatrix::kMScaleY]);
+ tmp2.setMul(mat[SkMatrix::kMSkewX], mat[SkMatrix::kMSkewY]);
+ tmp1.sub(tmp2);
+ }
+
+ int s = tmp1.getClzAbs();
+ *shift = s;
+
+ SkFixed denom;
+ if (s <= 32) {
+ denom = tmp1.getShiftRight(33 - s);
+ } else {
+ denom = (int32_t)tmp1.fLo << (s - 33);
+ }
+
+ if (denom == 0) {
+ return 0;
+ }
+ /** This could perhaps be a special fractdiv function, since both of its
+ arguments are known to have bit 31 clear and bit 30 set (when they
+ are made positive), thus eliminating the need for calling clz()
+ */
+ return SkFractDiv(SK_Fract1, denom);
+ }
+#endif
+
+bool SkMatrix::invert(SkMatrix* inv) const {
+ int isPersp = has_perspective(*this);
+ int shift;
+ SkScalar scale = sk_inv_determinant(fMat, isPersp, &shift);
+
+ if (scale == 0) { // underflow
+ return false;
+ }
+
+ if (inv) {
+ SkMatrix tmp;
+ if (inv == this)
+ inv = &tmp;
+
+ if (isPersp) {
+ shift = 61 - shift;
+ inv->fMat[kMScaleX] = SkScalarMulShift(SkPerspMul(fMat[kMScaleY], fMat[kMPersp2]) - SkPerspMul(fMat[kMTransY], fMat[kMPersp1]), scale, shift);
+ inv->fMat[kMSkewX] = SkScalarMulShift(SkPerspMul(fMat[kMTransX], fMat[kMPersp1]) - SkPerspMul(fMat[kMSkewX], fMat[kMPersp2]), scale, shift);
+ inv->fMat[kMTransX] = SkScalarMulShift(SkScalarMul(fMat[kMSkewX], fMat[kMTransY]) - SkScalarMul(fMat[kMTransX], fMat[kMScaleY]), scale, shift);
+
+ inv->fMat[kMSkewY] = SkScalarMulShift(SkPerspMul(fMat[kMTransY], fMat[kMPersp0]) - SkPerspMul(fMat[kMSkewY], fMat[kMPersp2]), scale, shift);
+ inv->fMat[kMScaleY] = SkScalarMulShift(SkPerspMul(fMat[kMScaleX], fMat[kMPersp2]) - SkPerspMul(fMat[kMTransX], fMat[kMPersp0]), scale, shift);
+ inv->fMat[kMTransY] = SkScalarMulShift(SkScalarMul(fMat[kMTransX], fMat[kMSkewY]) - SkScalarMul(fMat[kMScaleX], fMat[kMTransY]), scale, shift);
+
+ inv->fMat[kMPersp0] = SkScalarMulShift(SkScalarMul(fMat[kMSkewY], fMat[kMPersp1]) - SkScalarMul(fMat[kMScaleY], fMat[kMPersp0]), scale, shift);
+ inv->fMat[kMPersp1] = SkScalarMulShift(SkScalarMul(fMat[kMSkewX], fMat[kMPersp0]) - SkScalarMul(fMat[kMScaleX], fMat[kMPersp1]), scale, shift);
+ inv->fMat[kMPersp2] = SkScalarMulShift(SkScalarMul(fMat[kMScaleX], fMat[kMScaleY]) - SkScalarMul(fMat[kMSkewX], fMat[kMSkewY]), scale, shift);
+#ifdef SK_SCALAR_IS_FIXED
+ if (SkAbs32(inv->fMat[kMPersp2]) > SK_Fixed1) {
+ Sk64 tmp;
+
+ tmp.set(SK_Fract1);
+ tmp.shiftLeft(16);
+ tmp.div(inv->fMat[kMPersp2], Sk64::kRound_DivOption);
+
+ SkFract scale = tmp.get32();
+
+ for (int i = 0; i < 9; i++) {
+ inv->fMat[i] = SkFractMul(inv->fMat[i], scale);
+ }
+ }
+ inv->fMat[kMPersp2] = SkFixedToFract(inv->fMat[kMPersp2]);
+#endif
+ } else { // not perspective
+#ifdef SK_SCALAR_IS_FIXED
+ Sk64 tx, ty;
+ int clzNumer;
+
+ // check the 2x2 for overflow
+ {
+ int32_t value = SkAbs32(fMat[kMScaleY]);
+ value |= SkAbs32(fMat[kMSkewX]);
+ value |= SkAbs32(fMat[kMScaleX]);
+ value |= SkAbs32(fMat[kMSkewY]);
+ clzNumer = SkCLZ(value);
+ if (shift - clzNumer > 31)
+ return false; // overflow
+ }
+
+ set_muladdmul(&tx, fMat[kMSkewX], fMat[kMTransY], -fMat[kMScaleY], fMat[kMTransX]);
+ set_muladdmul(&ty, fMat[kMSkewY], fMat[kMTransX], -fMat[kMScaleX], fMat[kMTransY]);
+ // check tx,ty for overflow
+ clzNumer = SkCLZ(SkAbs32(tx.fHi) | SkAbs32(ty.fHi));
+ if (shift - clzNumer > 14) {
+ return false; // overflow
+ }
+
+ int fixedShift = 61 - shift;
+ int sk64shift = 44 - shift + clzNumer;
+
+ inv->fMat[kMScaleX] = SkMulShift(fMat[kMScaleY], scale, fixedShift);
+ inv->fMat[kMSkewX] = SkMulShift(-fMat[kMSkewX], scale, fixedShift);
+ inv->fMat[kMTransX] = SkMulShift(tx.getShiftRight(33 - clzNumer), scale, sk64shift);
+
+ inv->fMat[kMSkewY] = SkMulShift(-fMat[kMSkewY], scale, fixedShift);
+ inv->fMat[kMScaleY] = SkMulShift(fMat[kMScaleX], scale, fixedShift);
+ inv->fMat[kMTransY] = SkMulShift(ty.getShiftRight(33 - clzNumer), scale, sk64shift);
+#else
+ inv->fMat[kMScaleX] = SkScalarMul(fMat[kMScaleY], scale);
+ inv->fMat[kMSkewX] = SkScalarMul(-fMat[kMSkewX], scale);
+ if (!fixmuladdmulshiftmul(fMat[kMSkewX], fMat[kMTransY], -fMat[kMScaleY], fMat[kMTransX], shift, scale, &inv->fMat[kMTransX])) {
+ return false;
+ }
+
+ inv->fMat[kMSkewY] = SkScalarMul(-fMat[kMSkewY], scale);
+ inv->fMat[kMScaleY] = SkScalarMul(fMat[kMScaleX], scale);
+ if (!fixmuladdmulshiftmul(fMat[kMSkewY], fMat[kMTransX], -fMat[kMScaleX], fMat[kMTransY], shift, scale, &inv->fMat[kMTransY])) {
+ return false;
+ }
+#endif
+ inv->fMat[kMPersp0] = 0;
+ inv->fMat[kMPersp1] = 0;
+ inv->fMat[kMPersp2] = kMatrix22Elem;
+ }
+
+ if (inv == &tmp) {
+ *(SkMatrix*)this = tmp;
+ }
+ inv->setTypeMask(kUnknown_Mask);
+ }
+ return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkMatrix::Identity_pts(const SkMatrix& m, SkPoint dst[],
+ const SkPoint src[], int count) {
+ SkASSERT(m.getType() == 0);
+
+ if (dst != src && count > 0)
+ memcpy(dst, src, count * sizeof(SkPoint));
+}
+
+void SkMatrix::Trans_pts(const SkMatrix& m, SkPoint dst[],
+ const SkPoint src[], int count) {
+ SkASSERT(m.getType() == kTranslate_Mask);
+
+ if (count > 0) {
+ SkScalar tx = m.fMat[kMTransX];
+ SkScalar ty = m.fMat[kMTransY];
+ do {
+ dst->fY = src->fY + ty;
+ dst->fX = src->fX + tx;
+ src += 1;
+ dst += 1;
+ } while (--count);
+ }
+}
+
+void SkMatrix::Scale_pts(const SkMatrix& m, SkPoint dst[],
+ const SkPoint src[], int count) {
+ SkASSERT(m.getType() == kScale_Mask);
+
+ if (count > 0) {
+ SkScalar mx = m.fMat[kMScaleX];
+ SkScalar my = m.fMat[kMScaleY];
+ do {
+ dst->fY = SkScalarMul(src->fY, my);
+ dst->fX = SkScalarMul(src->fX, mx);
+ src += 1;
+ dst += 1;
+ } while (--count);
+ }
+}
+
+void SkMatrix::ScaleTrans_pts(const SkMatrix& m, SkPoint dst[],
+ const SkPoint src[], int count) {
+ SkASSERT(m.getType() == (kScale_Mask | kTranslate_Mask));
+
+ if (count > 0) {
+ SkScalar mx = m.fMat[kMScaleX];
+ SkScalar my = m.fMat[kMScaleY];
+ SkScalar tx = m.fMat[kMTransX];
+ SkScalar ty = m.fMat[kMTransY];
+ do {
+ dst->fY = SkScalarMulAdd(src->fY, my, ty);
+ dst->fX = SkScalarMulAdd(src->fX, mx, tx);
+ src += 1;
+ dst += 1;
+ } while (--count);
+ }
+}
+
+void SkMatrix::Rot_pts(const SkMatrix& m, SkPoint dst[],
+ const SkPoint src[], int count) {
+ SkASSERT((m.getType() & (kPerspective_Mask | kTranslate_Mask)) == 0);
+
+ if (count > 0) {
+ SkScalar mx = m.fMat[kMScaleX];
+ SkScalar my = m.fMat[kMScaleY];
+ SkScalar kx = m.fMat[kMSkewX];
+ SkScalar ky = m.fMat[kMSkewY];
+ do {
+ SkScalar sy = src->fY;
+ SkScalar sx = src->fX;
+ src += 1;
+ dst->fY = SkScalarMul(sx, ky) + SkScalarMul(sy, my);
+ dst->fX = SkScalarMul(sx, mx) + SkScalarMul(sy, kx);
+ dst += 1;
+ } while (--count);
+ }
+}
+
+void SkMatrix::RotTrans_pts(const SkMatrix& m, SkPoint dst[],
+ const SkPoint src[], int count) {
+ SkASSERT((m.getType() & kPerspective_Mask) == 0);
+
+ if (count > 0) {
+ SkScalar mx = m.fMat[kMScaleX];
+ SkScalar my = m.fMat[kMScaleY];
+ SkScalar kx = m.fMat[kMSkewX];
+ SkScalar ky = m.fMat[kMSkewY];
+ SkScalar tx = m.fMat[kMTransX];
+ SkScalar ty = m.fMat[kMTransY];
+ do {
+ SkScalar sy = src->fY;
+ SkScalar sx = src->fX;
+ src += 1;
+ dst->fY = SkScalarMul(sx, ky) + SkScalarMulAdd(sy, my, ty);
+ dst->fX = SkScalarMul(sx, mx) + SkScalarMulAdd(sy, kx, tx);
+ dst += 1;
+ } while (--count);
+ }
+}
+
+void SkMatrix::Persp_pts(const SkMatrix& m, SkPoint dst[],
+ const SkPoint src[], int count) {
+ SkASSERT(m.getType() & kPerspective_Mask);
+
+#ifdef SK_SCALAR_IS_FIXED
+ SkFixed persp2 = SkFractToFixed(m.fMat[kMPersp2]);
+#endif
+
+ if (count > 0) {
+ do {
+ SkScalar sy = src->fY;
+ SkScalar sx = src->fX;
+ src += 1;
+
+ SkScalar x = SkScalarMul(sx, m.fMat[kMScaleX]) +
+ SkScalarMul(sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
+ SkScalar y = SkScalarMul(sx, m.fMat[kMSkewY]) +
+ SkScalarMul(sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
+#ifdef SK_SCALAR_IS_FIXED
+ SkFixed z = SkFractMul(sx, m.fMat[kMPersp0]) +
+ SkFractMul(sy, m.fMat[kMPersp1]) + persp2;
+#else
+ float z = SkScalarMul(sx, m.fMat[kMPersp0]) +
+ SkScalarMulAdd(sy, m.fMat[kMPersp1], m.fMat[kMPersp2]);
+#endif
+ if (z) {
+ z = SkScalarFastInvert(z);
+ }
+
+ dst->fY = SkScalarMul(y, z);
+ dst->fX = SkScalarMul(x, z);
+ dst += 1;
+ } while (--count);
+ }
+}
+
+const SkMatrix::MapPtsProc SkMatrix::gMapPtsProcs[] = {
+ SkMatrix::Identity_pts, SkMatrix::Trans_pts,
+ SkMatrix::Scale_pts, SkMatrix::ScaleTrans_pts,
+ SkMatrix::Rot_pts, SkMatrix::RotTrans_pts,
+ SkMatrix::Rot_pts, SkMatrix::RotTrans_pts,
+ // repeat the persp proc 8 times
+ SkMatrix::Persp_pts, SkMatrix::Persp_pts,
+ SkMatrix::Persp_pts, SkMatrix::Persp_pts,
+ SkMatrix::Persp_pts, SkMatrix::Persp_pts,
+ SkMatrix::Persp_pts, SkMatrix::Persp_pts
+};
+
+void SkMatrix::mapPoints(SkPoint dst[], const SkPoint src[], int count) const {
+ SkASSERT((dst && src && count > 0) || count == 0);
+ // no partial overlap
+ SkASSERT(src == dst || SkAbs32((int32_t)(src - dst)) >= count);
+
+ this->getMapPtsProc()(*this, dst, src, count);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkMatrix::mapVectors(SkPoint dst[], const SkPoint src[], int count) const {
+ if (this->getType() & kPerspective_Mask) {
+ SkPoint origin;
+
+ MapXYProc proc = this->getMapXYProc();
+ proc(*this, 0, 0, &origin);
+
+ for (int i = count - 1; i >= 0; --i) {
+ SkPoint tmp;
+
+ proc(*this, src[i].fX, src[i].fY, &tmp);
+ dst[i].set(tmp.fX - origin.fX, tmp.fY - origin.fY);
+ }
+ } else {
+ SkMatrix tmp = *this;
+
+ tmp.fMat[kMTransX] = tmp.fMat[kMTransY] = 0;
+ tmp.clearTypeMask(kTranslate_Mask);
+ tmp.mapPoints(dst, src, count);
+ }
+}
+
+bool SkMatrix::mapRect(SkRect* dst, const SkRect& src) const {
+ SkASSERT(dst && &src);
+
+ if (this->rectStaysRect()) {
+ this->mapPoints((SkPoint*)dst, (const SkPoint*)&src, 2);
+ dst->sort();
+ return true;
+ } else {
+ SkPoint quad[4];
+
+ src.toQuad(quad);
+ this->mapPoints(quad, quad, 4);
+ dst->set(quad, 4);
+ return false;
+ }
+}
+
+SkScalar SkMatrix::mapRadius(SkScalar radius) const {
+ SkVector vec[2];
+
+ vec[0].set(radius, 0);
+ vec[1].set(0, radius);
+ this->mapVectors(vec, 2);
+
+ SkScalar d0 = vec[0].length();
+ SkScalar d1 = vec[1].length();
+
+ return SkScalarMean(d0, d1);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkMatrix::Persp_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
+ SkPoint* pt) {
+ SkASSERT(m.getType() & kPerspective_Mask);
+
+ SkScalar x = SkScalarMul(sx, m.fMat[kMScaleX]) +
+ SkScalarMul(sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
+ SkScalar y = SkScalarMul(sx, m.fMat[kMSkewY]) +
+ SkScalarMul(sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
+#ifdef SK_SCALAR_IS_FIXED
+ SkFixed z = SkFractMul(sx, m.fMat[kMPersp0]) +
+ SkFractMul(sy, m.fMat[kMPersp1]) +
+ SkFractToFixed(m.fMat[kMPersp2]);
+#else
+ float z = SkScalarMul(sx, m.fMat[kMPersp0]) +
+ SkScalarMul(sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2];
+#endif
+ if (z) {
+ z = SkScalarFastInvert(z);
+ }
+ pt->fX = SkScalarMul(x, z);
+ pt->fY = SkScalarMul(y, z);
+}
+
+#ifdef SK_SCALAR_IS_FIXED
+static SkFixed fixmuladdmul(SkFixed a, SkFixed b, SkFixed c, SkFixed d) {
+ Sk64 tmp, tmp1;
+
+ tmp.setMul(a, b);
+ tmp1.setMul(c, d);
+ return tmp.addGetFixed(tmp1);
+// tmp.add(tmp1);
+// return tmp.getFixed();
+}
+#endif
+
+void SkMatrix::RotTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
+ SkPoint* pt) {
+ SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask)) == kAffine_Mask);
+
+#ifdef SK_SCALAR_IS_FIXED
+ pt->fX = fixmuladdmul(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) +
+ m.fMat[kMTransX];
+ pt->fY = fixmuladdmul(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) +
+ m.fMat[kMTransY];
+#else
+ pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]) +
+ SkScalarMulAdd(sy, m.fMat[kMSkewX], m.fMat[kMTransX]);
+ pt->fY = SkScalarMul(sx, m.fMat[kMSkewY]) +
+ SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]);
+#endif
+}
+
+void SkMatrix::Rot_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
+ SkPoint* pt) {
+ SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask))== kAffine_Mask);
+ SkASSERT(0 == m.fMat[kMTransX]);
+ SkASSERT(0 == m.fMat[kMTransY]);
+
+#ifdef SK_SCALAR_IS_FIXED
+ pt->fX = fixmuladdmul(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]);
+ pt->fY = fixmuladdmul(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]);
+#else
+ pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]) +
+ SkScalarMulAdd(sy, m.fMat[kMSkewX], m.fMat[kMTransX]);
+ pt->fY = SkScalarMul(sx, m.fMat[kMSkewY]) +
+ SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]);
+#endif
+}
+
+void SkMatrix::ScaleTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
+ SkPoint* pt) {
+ SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
+ == kScale_Mask);
+
+ pt->fX = SkScalarMulAdd(sx, m.fMat[kMScaleX], m.fMat[kMTransX]);
+ pt->fY = SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]);
+}
+
+void SkMatrix::Scale_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
+ SkPoint* pt) {
+ SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
+ == kScale_Mask);
+ SkASSERT(0 == m.fMat[kMTransX]);
+ SkASSERT(0 == m.fMat[kMTransY]);
+
+ pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]);
+ pt->fY = SkScalarMul(sy, m.fMat[kMScaleY]);
+}
+
+void SkMatrix::Trans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
+ SkPoint* pt) {
+ SkASSERT(m.getType() == kTranslate_Mask);
+
+ pt->fX = sx + m.fMat[kMTransX];
+ pt->fY = sy + m.fMat[kMTransY];
+}
+
+void SkMatrix::Identity_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
+ SkPoint* pt) {
+ SkASSERT(0 == m.getType());
+
+ pt->fX = sx;
+ pt->fY = sy;
+}
+
+const SkMatrix::MapXYProc SkMatrix::gMapXYProcs[] = {
+ SkMatrix::Identity_xy, SkMatrix::Trans_xy,
+ SkMatrix::Scale_xy, SkMatrix::ScaleTrans_xy,
+ SkMatrix::Rot_xy, SkMatrix::RotTrans_xy,
+ SkMatrix::Rot_xy, SkMatrix::RotTrans_xy,
+ // repeat the persp proc 8 times
+ SkMatrix::Persp_xy, SkMatrix::Persp_xy,
+ SkMatrix::Persp_xy, SkMatrix::Persp_xy,
+ SkMatrix::Persp_xy, SkMatrix::Persp_xy,
+ SkMatrix::Persp_xy, SkMatrix::Persp_xy
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+// if its nearly zero (just made up 26, perhaps it should be bigger or smaller)
+#ifdef SK_SCALAR_IS_FIXED
+ typedef SkFract SkPerspElemType;
+ #define PerspNearlyZero(x) (SkAbs32(x) < (SK_Fract1 >> 26))
+#else
+ typedef float SkPerspElemType;
+ #define PerspNearlyZero(x) SkScalarNearlyZero(x, (1.0f / (1 << 26)))
+#endif
+
+bool SkMatrix::fixedStepInX(SkScalar y, SkFixed* stepX, SkFixed* stepY) const {
+ if (PerspNearlyZero(fMat[kMPersp0])) {
+ if (stepX || stepY) {
+ if (PerspNearlyZero(fMat[kMPersp1]) &&
+ PerspNearlyZero(fMat[kMPersp2] - kMatrix22Elem)) {
+ if (stepX) {
+ *stepX = SkScalarToFixed(fMat[kMScaleX]);
+ }
+ if (stepY) {
+ *stepY = SkScalarToFixed(fMat[kMSkewY]);
+ }
+ } else {
+#ifdef SK_SCALAR_IS_FIXED
+ SkFixed z = SkFractMul(y, fMat[kMPersp1]) +
+ SkFractToFixed(fMat[kMPersp2]);
+#else
+ float z = y * fMat[kMPersp1] + fMat[kMPersp2];
+#endif
+ if (stepX) {
+ *stepX = SkScalarToFixed(SkScalarDiv(fMat[kMScaleX], z));
+ }
+ if (stepY) {
+ *stepY = SkScalarToFixed(SkScalarDiv(fMat[kMSkewY], z));
+ }
+ }
+ }
+ return true;
+ }
+ return false;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#include "SkPerspIter.h"
+
+SkPerspIter::SkPerspIter(const SkMatrix& m, SkScalar x0, SkScalar y0, int count)
+ : fMatrix(m), fSX(x0), fSY(y0), fCount(count) {
+ SkPoint pt;
+
+ SkMatrix::Persp_xy(m, x0, y0, &pt);
+ fX = SkScalarToFixed(pt.fX);
+ fY = SkScalarToFixed(pt.fY);
+}
+
+int SkPerspIter::next() {
+ int n = fCount;
+
+ if (0 == n) {
+ return 0;
+ }
+ SkPoint pt;
+ SkFixed x = fX;
+ SkFixed y = fY;
+ SkFixed dx, dy;
+
+ if (n >= kCount) {
+ n = kCount;
+ fSX += SkIntToScalar(kCount);
+ SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
+ fX = SkScalarToFixed(pt.fX);
+ fY = SkScalarToFixed(pt.fY);
+ dx = (fX - x) >> kShift;
+ dy = (fY - y) >> kShift;
+ } else {
+ fSX += SkIntToScalar(n);
+ SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
+ fX = SkScalarToFixed(pt.fX);
+ fY = SkScalarToFixed(pt.fY);
+ dx = (fX - x) / n;
+ dy = (fY - y) / n;
+ }
+
+ SkFixed* p = fStorage;
+ for (int i = 0; i < n; i++) {
+ *p++ = x; x += dx;
+ *p++ = y; y += dy;
+ }
+
+ fCount -= n;
+ return n;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_SCALAR_IS_FIXED
+
+static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) {
+ SkFixed x = SK_Fixed1, y = SK_Fixed1;
+ SkPoint pt1, pt2;
+ Sk64 w1, w2;
+
+ if (count > 1) {
+ pt1.fX = poly[1].fX - poly[0].fX;
+ pt1.fY = poly[1].fY - poly[0].fY;
+ y = SkPoint::Length(pt1.fX, pt1.fY);
+ if (y == 0) {
+ return false;
+ }
+ switch (count) {
+ case 2:
+ break;
+ case 3:
+ pt2.fX = poly[0].fY - poly[2].fY;
+ pt2.fY = poly[2].fX - poly[0].fX;
+ goto CALC_X;
+ default:
+ pt2.fX = poly[0].fY - poly[3].fY;
+ pt2.fY = poly[3].fX - poly[0].fX;
+ CALC_X:
+ w1.setMul(pt1.fX, pt2.fX);
+ w2.setMul(pt1.fY, pt2.fY);
+ w1.add(w2);
+ w1.div(y, Sk64::kRound_DivOption);
+ if (!w1.is32()) {
+ return false;
+ }
+ x = w1.get32();
+ break;
+ }
+ }
+ pt->set(x, y);
+ return true;
+}
+
+bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst,
+ const SkPoint& scalePt) {
+ // need to check if SkFixedDiv overflows...
+
+ const SkFixed scale = scalePt.fY;
+ dst->fMat[kMScaleX] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale);
+ dst->fMat[kMSkewY] = SkFixedDiv(srcPt[0].fX - srcPt[1].fX, scale);
+ dst->fMat[kMPersp0] = 0;
+ dst->fMat[kMSkewX] = SkFixedDiv(srcPt[1].fX - srcPt[0].fX, scale);
+ dst->fMat[kMScaleY] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale);
+ dst->fMat[kMPersp1] = 0;
+ dst->fMat[kMTransX] = srcPt[0].fX;
+ dst->fMat[kMTransY] = srcPt[0].fY;
+ dst->fMat[kMPersp2] = SK_Fract1;
+ dst->setTypeMask(kUnknown_Mask);
+ return true;
+}
+
+bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst,
+ const SkPoint& scale) {
+ // really, need to check if SkFixedDiv overflow'd
+
+ dst->fMat[kMScaleX] = SkFixedDiv(srcPt[2].fX - srcPt[0].fX, scale.fX);
+ dst->fMat[kMSkewY] = SkFixedDiv(srcPt[2].fY - srcPt[0].fY, scale.fX);
+ dst->fMat[kMPersp0] = 0;
+ dst->fMat[kMSkewX] = SkFixedDiv(srcPt[1].fX - srcPt[0].fX, scale.fY);
+ dst->fMat[kMScaleY] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale.fY);
+ dst->fMat[kMPersp1] = 0;
+ dst->fMat[kMTransX] = srcPt[0].fX;
+ dst->fMat[kMTransY] = srcPt[0].fY;
+ dst->fMat[kMPersp2] = SK_Fract1;
+ dst->setTypeMask(kUnknown_Mask);
+ return true;
+}
+
+bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst,
+ const SkPoint& scale) {
+ SkFract a1, a2;
+ SkFixed x0, y0, x1, y1, x2, y2;
+
+ x0 = srcPt[2].fX - srcPt[0].fX;
+ y0 = srcPt[2].fY - srcPt[0].fY;
+ x1 = srcPt[2].fX - srcPt[1].fX;
+ y1 = srcPt[2].fY - srcPt[1].fY;
+ x2 = srcPt[2].fX - srcPt[3].fX;
+ y2 = srcPt[2].fY - srcPt[3].fY;
+
+ /* check if abs(x2) > abs(y2) */
+ if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) {
+ SkFixed denom = SkMulDiv(x1, y2, x2) - y1;
+ if (0 == denom) {
+ return false;
+ }
+ a1 = SkFractDiv(SkMulDiv(x0 - x1, y2, x2) - y0 + y1, denom);
+ } else {
+ SkFixed denom = x1 - SkMulDiv(y1, x2, y2);
+ if (0 == denom) {
+ return false;
+ }
+ a1 = SkFractDiv(x0 - x1 - SkMulDiv(y0 - y1, x2, y2), denom);
+ }
+
+ /* check if abs(x1) > abs(y1) */
+ if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) {
+ SkFixed denom = y2 - SkMulDiv(x2, y1, x1);
+ if (0 == denom) {
+ return false;
+ }
+ a2 = SkFractDiv(y0 - y2 - SkMulDiv(x0 - x2, y1, x1), denom);
+ } else {
+ SkFixed denom = SkMulDiv(y2, x1, y1) - x2;
+ if (0 == denom) {
+ return false;
+ }
+ a2 = SkFractDiv(SkMulDiv(y0 - y2, x1, y1) - x0 + x2, denom);
+ }
+
+ // need to check if SkFixedDiv overflows...
+ dst->fMat[kMScaleX] = SkFixedDiv(SkFractMul(a2, srcPt[3].fX) +
+ srcPt[3].fX - srcPt[0].fX, scale.fX);
+ dst->fMat[kMSkewY] = SkFixedDiv(SkFractMul(a2, srcPt[3].fY) +
+ srcPt[3].fY - srcPt[0].fY, scale.fX);
+ dst->fMat[kMPersp0] = SkFixedDiv(a2, scale.fX);
+ dst->fMat[kMSkewX] = SkFixedDiv(SkFractMul(a1, srcPt[1].fX) +
+ srcPt[1].fX - srcPt[0].fX, scale.fY);
+ dst->fMat[kMScaleY] = SkFixedDiv(SkFractMul(a1, srcPt[1].fY) +
+ srcPt[1].fY - srcPt[0].fY, scale.fY);
+ dst->fMat[kMPersp1] = SkFixedDiv(a1, scale.fY);
+ dst->fMat[kMTransX] = srcPt[0].fX;
+ dst->fMat[kMTransY] = srcPt[0].fY;
+ dst->fMat[kMPersp2] = SK_Fract1;
+ dst->setTypeMask(kUnknown_Mask);
+ return true;
+}
+
+#else /* Scalar is float */
+
+static inline bool checkForZero(float x) {
+ return x*x == 0;
+}
+
+static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) {
+ float x = 1, y = 1;
+ SkPoint pt1, pt2;
+
+ if (count > 1) {
+ pt1.fX = poly[1].fX - poly[0].fX;
+ pt1.fY = poly[1].fY - poly[0].fY;
+ y = SkPoint::Length(pt1.fX, pt1.fY);
+ if (checkForZero(y)) {
+ return false;
+ }
+ switch (count) {
+ case 2:
+ break;
+ case 3:
+ pt2.fX = poly[0].fY - poly[2].fY;
+ pt2.fY = poly[2].fX - poly[0].fX;
+ goto CALC_X;
+ default:
+ pt2.fX = poly[0].fY - poly[3].fY;
+ pt2.fY = poly[3].fX - poly[0].fX;
+ CALC_X:
+ x = SkScalarDiv(SkScalarMul(pt1.fX, pt2.fX) +
+ SkScalarMul(pt1.fY, pt2.fY), y);
+ break;
+ }
+ }
+ pt->set(x, y);
+ return true;
+}
+
+bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst,
+ const SkPoint& scale) {
+ float invScale = 1 / scale.fY;
+
+ dst->fMat[kMScaleX] = (srcPt[1].fY - srcPt[0].fY) * invScale;
+ dst->fMat[kMSkewY] = (srcPt[0].fX - srcPt[1].fX) * invScale;
+ dst->fMat[kMPersp0] = 0;
+ dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
+ dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
+ dst->fMat[kMPersp1] = 0;
+ dst->fMat[kMTransX] = srcPt[0].fX;
+ dst->fMat[kMTransY] = srcPt[0].fY;
+ dst->fMat[kMPersp2] = 1;
+ dst->setTypeMask(kUnknown_Mask);
+ return true;
+}
+
+bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst,
+ const SkPoint& scale) {
+ float invScale = 1 / scale.fX;
+ dst->fMat[kMScaleX] = (srcPt[2].fX - srcPt[0].fX) * invScale;
+ dst->fMat[kMSkewY] = (srcPt[2].fY - srcPt[0].fY) * invScale;
+ dst->fMat[kMPersp0] = 0;
+
+ invScale = 1 / scale.fY;
+ dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
+ dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
+ dst->fMat[kMPersp1] = 0;
+
+ dst->fMat[kMTransX] = srcPt[0].fX;
+ dst->fMat[kMTransY] = srcPt[0].fY;
+ dst->fMat[kMPersp2] = 1;
+ dst->setTypeMask(kUnknown_Mask);
+ return true;
+}
+
+bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst,
+ const SkPoint& scale) {
+ float a1, a2;
+ float x0, y0, x1, y1, x2, y2;
+
+ x0 = srcPt[2].fX - srcPt[0].fX;
+ y0 = srcPt[2].fY - srcPt[0].fY;
+ x1 = srcPt[2].fX - srcPt[1].fX;
+ y1 = srcPt[2].fY - srcPt[1].fY;
+ x2 = srcPt[2].fX - srcPt[3].fX;
+ y2 = srcPt[2].fY - srcPt[3].fY;
+
+ /* check if abs(x2) > abs(y2) */
+ if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) {
+ float denom = SkScalarMulDiv(x1, y2, x2) - y1;
+ if (checkForZero(denom)) {
+ return false;
+ }
+ a1 = SkScalarDiv(SkScalarMulDiv(x0 - x1, y2, x2) - y0 + y1, denom);
+ } else {
+ float denom = x1 - SkScalarMulDiv(y1, x2, y2);
+ if (checkForZero(denom)) {
+ return false;
+ }
+ a1 = SkScalarDiv(x0 - x1 - SkScalarMulDiv(y0 - y1, x2, y2), denom);
+ }
+
+ /* check if abs(x1) > abs(y1) */
+ if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) {
+ float denom = y2 - SkScalarMulDiv(x2, y1, x1);
+ if (checkForZero(denom)) {
+ return false;
+ }
+ a2 = SkScalarDiv(y0 - y2 - SkScalarMulDiv(x0 - x2, y1, x1), denom);
+ } else {
+ float denom = SkScalarMulDiv(y2, x1, y1) - x2;
+ if (checkForZero(denom)) {
+ return false;
+ }
+ a2 = SkScalarDiv(SkScalarMulDiv(y0 - y2, x1, y1) - x0 + x2, denom);
+ }
+
+ float invScale = 1 / scale.fX;
+ dst->fMat[kMScaleX] = SkScalarMul(SkScalarMul(a2, srcPt[3].fX) +
+ srcPt[3].fX - srcPt[0].fX, invScale);
+ dst->fMat[kMSkewY] = SkScalarMul(SkScalarMul(a2, srcPt[3].fY) +
+ srcPt[3].fY - srcPt[0].fY, invScale);
+ dst->fMat[kMPersp0] = SkScalarMul(a2, invScale);
+ invScale = 1 / scale.fY;
+ dst->fMat[kMSkewX] = SkScalarMul(SkScalarMul(a1, srcPt[1].fX) +
+ srcPt[1].fX - srcPt[0].fX, invScale);
+ dst->fMat[kMScaleY] = SkScalarMul(SkScalarMul(a1, srcPt[1].fY) +
+ srcPt[1].fY - srcPt[0].fY, invScale);
+ dst->fMat[kMPersp1] = SkScalarMul(a1, invScale);
+ dst->fMat[kMTransX] = srcPt[0].fX;
+ dst->fMat[kMTransY] = srcPt[0].fY;
+ dst->fMat[kMPersp2] = 1;
+ dst->setTypeMask(kUnknown_Mask);
+ return true;
+}
+
+#endif
+
+typedef bool (*PolyMapProc)(const SkPoint[], SkMatrix*, const SkPoint&);
+
+/* Taken from Rob Johnson's original sample code in QuickDraw GX
+*/
+bool SkMatrix::setPolyToPoly(const SkPoint src[], const SkPoint dst[],
+ int count) {
+ if ((unsigned)count > 4) {
+ SkDebugf("--- SkMatrix::setPolyToPoly count out of range %d\n", count);
+ return false;
+ }
+
+ if (0 == count) {
+ this->reset();
+ return true;
+ }
+ if (1 == count) {
+ this->setTranslate(dst[0].fX - src[0].fX, dst[0].fY - src[0].fY);
+ return true;
+ }
+
+ SkPoint scale;
+ if (!poly_to_point(&scale, src, count) ||
+ SkScalarNearlyZero(scale.fX) ||
+ SkScalarNearlyZero(scale.fY)) {
+ return false;
+ }
+
+ static const PolyMapProc gPolyMapProcs[] = {
+ SkMatrix::Poly2Proc, SkMatrix::Poly3Proc, SkMatrix::Poly4Proc
+ };
+ PolyMapProc proc = gPolyMapProcs[count - 2];
+
+ SkMatrix tempMap, result;
+ tempMap.setTypeMask(kUnknown_Mask);
+
+ if (!proc(src, &tempMap, scale)) {
+ return false;
+ }
+ if (!tempMap.invert(&result)) {
+ return false;
+ }
+ if (!proc(dst, &tempMap, scale)) {
+ return false;
+ }
+ if (!result.setConcat(tempMap, result)) {
+ return false;
+ }
+ *this = result;
+ return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkMatrix::dump() const {
+ // ensure the fTypeMask is up2date
+ (void)this->getType();
+#ifdef SK_DEBUG
+ int mask = this->computeTypeMask();
+ SkASSERT(mask == fTypeMask);
+#endif
+
+#ifdef SK_CAN_USE_FLOAT
+ SkDebugf("[%8.4f %8.4f %8.4f] [%8.4f %8.4f %8.4f] [%8.4f %8.4f %8.4f] %x\n",
+#ifdef SK_SCALAR_IS_FLOAT
+ fMat[0], fMat[1], fMat[2], fMat[3], fMat[4], fMat[5],
+ fMat[6], fMat[7], fMat[8], fTypeMask);
+#else
+ SkFixedToFloat(fMat[0]), SkFixedToFloat(fMat[1]), SkFixedToFloat(fMat[2]),
+ SkFixedToFloat(fMat[3]), SkFixedToFloat(fMat[4]), SkFixedToFloat(fMat[5]),
+ SkFractToFloat(fMat[6]), SkFractToFloat(fMat[7]), SkFractToFloat(fMat[8]),
+ fTypeMask);
+#endif
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_DEBUG
+
+void SkMatrix::UnitTest() {
+#ifdef SK_SUPPORT_UNITTEST
+ SkMatrix mat, inverse, iden1, iden2;
+
+ mat.reset();
+ mat.setTranslate(SK_Scalar1, SK_Scalar1);
+ mat.invert(&inverse);
+ inverse.dump();
+ iden1.setConcat(mat, inverse);
+ iden1.dump();
+
+ mat.setScale(SkIntToScalar(2), SkIntToScalar(2));
+ mat.invert(&inverse);
+ inverse.dump();
+ iden1.setConcat(mat, inverse);
+ iden1.dump();
+
+ mat.setScale(SK_Scalar1/2, SK_Scalar1/2);
+ mat.invert(&inverse);
+ inverse.dump();
+ iden1.setConcat(mat, inverse);
+ iden1.dump();
+ SkASSERT(iden1.isIdentity());
+
+ mat.setScale(SkIntToScalar(3), SkIntToScalar(5), SkIntToScalar(20), 0);
+ mat.postRotate(SkIntToScalar(25));
+
+ SkASSERT(mat.invert(NULL));
+ mat.invert(&inverse);
+
+ iden1.setConcat(mat, inverse);
+ iden2.setConcat(inverse, mat);
+
+ iden1.dump();
+// SkASSERT(iden1.isIdentity());
+ iden2.dump();
+// SkASSERT(iden2.isIdentity());
+
+ // rectStaysRect test
+ {
+ static const struct {
+ SkScalar m00, m01, m10, m11;
+ bool mStaysRect;
+ }
+ gRectStaysRectSamples[] = {
+ { 0, 0, 0, 0, false },
+ { 0, 0, 0, SK_Scalar1, false },
+ { 0, 0, SK_Scalar1, 0, false },
+ { 0, 0, SK_Scalar1, SK_Scalar1, false },
+ { 0, SK_Scalar1, 0, 0, false },
+ { 0, SK_Scalar1, 0, SK_Scalar1, false },
+ { 0, SK_Scalar1, SK_Scalar1, 0, true },
+ { 0, SK_Scalar1, SK_Scalar1, SK_Scalar1, false },
+ { SK_Scalar1, 0, 0, 0, false },
+ { SK_Scalar1, 0, 0, SK_Scalar1, true },
+ { SK_Scalar1, 0, SK_Scalar1, 0, false },
+ { SK_Scalar1, 0, SK_Scalar1, SK_Scalar1, false },
+ { SK_Scalar1, SK_Scalar1, 0, 0, false },
+ { SK_Scalar1, SK_Scalar1, 0, SK_Scalar1, false },
+ { SK_Scalar1, SK_Scalar1, SK_Scalar1, 0, false },
+ { SK_Scalar1, SK_Scalar1, SK_Scalar1, SK_Scalar1, false }
+ };
+
+ for (size_t i = 0; i < SK_ARRAY_COUNT(gRectStaysRectSamples); i++) {
+ SkMatrix m;
+
+ m.reset();
+ m.set(SkMatrix::kMScaleX, gRectStaysRectSamples[i].m00);
+ m.set(SkMatrix::kMSkewX, gRectStaysRectSamples[i].m01);
+ m.set(SkMatrix::kMSkewY, gRectStaysRectSamples[i].m10);
+ m.set(SkMatrix::kMScaleY, gRectStaysRectSamples[i].m11);
+ SkASSERT(m.rectStaysRect() == gRectStaysRectSamples[i].mStaysRect);
+ }
+ }
+#endif
+}
+
+#endif
diff --git a/skia/corecg/SkMemory_stdlib.cpp b/skia/corecg/SkMemory_stdlib.cpp
new file mode 100644
index 0000000..6ceca33
--- /dev/null
+++ b/skia/corecg/SkMemory_stdlib.cpp
@@ -0,0 +1,280 @@
+/* libs/corecg/SkMemory_stdlib.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkTypes.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+#ifdef SK_DEBUG
+ #define SK_TAG_BLOCKS
+ // #define SK_TRACK_ALLOC // enable to see a printf for every alloc/free
+ // #define SK_CHECK_TAGS // enable to double-check debugging link list
+#endif
+
+#ifdef SK_TAG_BLOCKS
+
+#include "SkThread.h"
+
+// size this (as a multiple of 4) so that the total offset to the internal data
+// is at least a multiple of 8 (since some clients of our malloc may require
+// that.
+static const char kBlockHeaderTag[] = { 's', 'k', 'i', 'a', '1', '2', '3', '4' };
+static const char kBlockTrailerTag[] = { 'a', 'i', 'k', 's' };
+#define kByteFill 0xCD
+#define kDeleteFill 0xEF
+
+static SkMutex gBlockMutex;
+static struct SkBlockHeader* gHeader;
+
+struct SkBlockHeader {
+ SkBlockHeader* fNext;
+#ifdef SK_CHECK_TAGS
+ SkBlockHeader** fTop; // set to verify in debugger that block was alloc'd / freed with same gHeader
+ SkBlockHeader* fPrevious; // set to see in debugger previous block when corruption happens
+#endif
+ size_t fSize;
+ char fHeader[sizeof(kBlockHeaderTag)];
+ // data goes here. The offset to this point must be a multiple of 8
+ char fTrailer[sizeof(kBlockTrailerTag)];
+
+ void* add(size_t realSize)
+ {
+ SkAutoMutexAcquire ac(gBlockMutex);
+ InMutexValidate();
+ fNext = gHeader;
+#ifdef SK_CHECK_TAGS
+ fTop = &gHeader;
+ fPrevious = NULL;
+ if (fNext != NULL)
+ fNext->fPrevious = this;
+#endif
+ gHeader = this;
+ fSize = realSize;
+ memcpy(fHeader, kBlockHeaderTag, sizeof(kBlockHeaderTag));
+ void* result = fTrailer;
+ void* trailer = (char*)result + realSize;
+ memcpy(trailer, kBlockTrailerTag, sizeof(kBlockTrailerTag));
+ return result;
+ }
+
+ static void Dump()
+ {
+ SkAutoMutexAcquire ac(gBlockMutex);
+ InMutexValidate();
+ SkBlockHeader* header = gHeader;
+ int count = 0;
+ size_t size = 0;
+ while (header != NULL) {
+ char scratch[256];
+ char* pos = scratch;
+ size_t size = header->fSize;
+ int* data = (int*)(void*)header->fTrailer;
+ pos += sprintf(pos, "%p 0x%08zx (%7zd) ",
+ data, size, size);
+ size >>= 2;
+ size_t ints = size > 4 ? 4 : size;
+ size_t index;
+ for (index = 0; index < ints; index++)
+ pos += sprintf(pos, "0x%08x ", data[index]);
+ pos += sprintf(pos, " (");
+ for (index = 0; index < ints; index++)
+ pos += sprintf(pos, "%g ", data[index] / 65536.0f);
+ if (ints > 0)
+ --pos;
+ pos += sprintf(pos, ") \"");
+ size_t chars = size > 16 ? 16 : size;
+ char* chPtr = (char*) data;
+ for (index = 0; index < chars; index++) {
+ char ch = chPtr[index];
+ pos += sprintf(pos, "%c", ch >= ' ' && ch < 0x7f ? ch : '?');
+ }
+ pos += sprintf(pos, "\"");
+ SkDebugf("%s\n", scratch);
+ count++;
+ size += header->fSize;
+ header = header->fNext;
+ }
+ SkDebugf("--- count %d size 0x%08x (%zd) ---\n", count, size, size);
+ }
+
+ void remove() const
+ {
+ SkAutoMutexAcquire ac(gBlockMutex);
+ SkBlockHeader** findPtr = &gHeader;
+ do {
+ SkBlockHeader* find = *findPtr;
+ SkASSERT(find != NULL);
+ if (find == this) {
+ *findPtr = fNext;
+ break;
+ }
+ findPtr = &find->fNext;
+ } while (true);
+ InMutexValidate();
+ SkASSERT(memcmp(fHeader, kBlockHeaderTag, sizeof(kBlockHeaderTag)) == 0);
+ const char* trailer = fTrailer + fSize;
+ SkASSERT(memcmp(trailer, kBlockTrailerTag, sizeof(kBlockTrailerTag)) == 0);
+ }
+
+ static void Validate()
+ {
+ SkAutoMutexAcquire ac(gBlockMutex);
+ InMutexValidate();
+ }
+
+private:
+ static void InMutexValidate()
+ {
+ SkBlockHeader* header = gHeader;
+ while (header != NULL) {
+ SkASSERT(memcmp(header->fHeader, kBlockHeaderTag, sizeof(kBlockHeaderTag)) == 0);
+ char* trailer = header->fTrailer + header->fSize;
+ SkASSERT(memcmp(trailer, kBlockTrailerTag, sizeof(kBlockTrailerTag)) == 0);
+ header = header->fNext;
+ }
+ }
+};
+
+void Dump()
+{
+ SkBlockHeader::Dump();
+}
+
+void ValidateHeap()
+{
+ SkBlockHeader::Validate();
+}
+#else
+void Dump() {}
+void ValidateHeap() {}
+#endif
+
+void sk_throw()
+{
+#ifdef ANDROID
+ fprintf(stderr, "throwing...\n");
+#endif
+ SkASSERT(!"sk_throw");
+ abort();
+}
+
+void sk_out_of_memory(void)
+{
+#ifdef ANDROID
+ fprintf(stderr,"- out of memory in SGL -\n");
+#endif
+ SkASSERT(!"sk_out_of_memory");
+ abort();
+}
+
+void* sk_malloc_throw(size_t size)
+{
+ return sk_malloc_flags(size, SK_MALLOC_THROW);
+}
+
+void* sk_realloc_throw(void* addr, size_t size)
+{
+#ifdef SK_TAG_BLOCKS
+ ValidateHeap();
+ if (addr != NULL) {
+ SkBlockHeader* header = (SkBlockHeader*)
+ ((char*)addr - SK_OFFSETOF(SkBlockHeader, fTrailer));
+ header->remove();
+#ifdef SK_TRACK_ALLOC
+ printf("sk_realloc_throw %p oldSize=%zd\n", addr, header->fSize);
+#endif
+ addr = header;
+ }
+ size_t realSize = size;
+ if (size)
+ size += sizeof(SkBlockHeader);
+#endif
+
+ void* p = realloc(addr, size);
+ if (size == 0)
+ {
+ ValidateHeap();
+ return p;
+ }
+
+ if (p == NULL)
+ sk_throw();
+#ifdef SK_TAG_BLOCKS
+ else
+ {
+ SkBlockHeader* header = (SkBlockHeader*) p;
+ p = header->add(realSize);
+#ifdef SK_TRACK_ALLOC
+ printf("sk_realloc_throw %p size=%zd\n", p, realSize);
+#endif
+ }
+#endif
+ ValidateHeap();
+ return p;
+}
+
+void sk_free(void* p)
+{
+ if (p)
+ {
+ ValidateHeap();
+#ifdef SK_TAG_BLOCKS
+ SkBlockHeader* header = (SkBlockHeader*)
+ ((char*)p - SK_OFFSETOF(SkBlockHeader, fTrailer));
+ header->remove();
+#ifdef SK_TRACK_ALLOC
+ printf("sk_free %p size=%zd\n", p, header->fSize);
+#endif
+ size_t size = header->fSize + sizeof(SkBlockHeader);
+ memset(header, kDeleteFill, size);
+ p = header;
+#endif
+ ValidateHeap();
+ free(p);
+ ValidateHeap();
+ }
+}
+
+void* sk_malloc_flags(size_t size, unsigned flags)
+{
+ ValidateHeap();
+#ifdef SK_TAG_BLOCKS
+ size_t realSize = size;
+ size += sizeof(SkBlockHeader);
+#endif
+
+ void* p = malloc(size);
+ if (p == NULL)
+ {
+ if (flags & SK_MALLOC_THROW)
+ sk_throw();
+ }
+#ifdef SK_TAG_BLOCKS
+ else
+ {
+ SkBlockHeader* header = (SkBlockHeader*) p;
+ p = header->add(realSize);
+ memset(p, kByteFill, realSize);
+#ifdef SK_TRACK_ALLOC
+ printf("sk_malloc_flags %p size=%zd\n", p, realSize);
+#endif
+ }
+#endif
+ ValidateHeap();
+ return p;
+}
+
diff --git a/skia/corecg/SkPoint.cpp b/skia/corecg/SkPoint.cpp
new file mode 100644
index 0000000..9d6acdf
--- /dev/null
+++ b/skia/corecg/SkPoint.cpp
@@ -0,0 +1,334 @@
+/*
+ * Copyright (C) 2006-2008 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "SkPoint.h"
+
+void SkIPoint::rotateCW(SkIPoint* dst) const {
+ SkASSERT(dst);
+
+ // use a tmp in case this == dst
+ int32_t tmp = fX;
+ dst->fX = -fY;
+ dst->fY = tmp;
+}
+
+void SkIPoint::rotateCCW(SkIPoint* dst) const {
+ SkASSERT(dst);
+
+ // use a tmp in case this == dst
+ int32_t tmp = fX;
+ dst->fX = fY;
+ dst->fY = -tmp;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkPoint::rotateCW(SkPoint* dst) const {
+ SkASSERT(dst);
+
+ // use a tmp in case this == dst
+ SkScalar tmp = fX;
+ dst->fX = -fY;
+ dst->fY = tmp;
+}
+
+void SkPoint::rotateCCW(SkPoint* dst) const {
+ SkASSERT(dst);
+
+ // use a tmp in case this == dst
+ SkScalar tmp = fX;
+ dst->fX = fY;
+ dst->fY = -tmp;
+}
+
+void SkPoint::scale(SkScalar scale, SkPoint* dst) const {
+ SkASSERT(dst);
+ dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale));
+}
+
+#define kNearlyZero (SK_Scalar1 / 8092)
+
+bool SkPoint::normalize() {
+ return this->setLength(fX, fY, SK_Scalar1);
+}
+
+bool SkPoint::setNormalize(SkScalar x, SkScalar y) {
+ return this->setLength(x, y, SK_Scalar1);
+}
+
+bool SkPoint::setLength(SkScalar length) {
+ return this->setLength(fX, fY, length);
+}
+
+#ifdef SK_SCALAR_IS_FLOAT
+
+SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
+ return sk_float_sqrt(dx * dx + dy * dy);
+}
+
+bool SkPoint::setLength(float x, float y, float length) {
+ float mag = sk_float_sqrt(x * x + y * y);
+ if (mag > kNearlyZero) {
+ length /= mag;
+ fX = x * length;
+ fY = y * length;
+ return true;
+ }
+ return false;
+}
+
+#else
+
+#include "Sk64.h"
+
+SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
+ Sk64 tmp1, tmp2;
+
+ tmp1.setMul(dx, dx);
+ tmp2.setMul(dy, dy);
+ tmp1.add(tmp2);
+
+ return tmp1.getSqrt();
+}
+
+#ifdef SK_DEBUGx
+static SkFixed fixlen(SkFixed x, SkFixed y) {
+ float fx = (float)x;
+ float fy = (float)y;
+
+ return (int)floorf(sqrtf(fx*fx + fy*fy) + 0.5f);
+}
+#endif
+
+static inline uint32_t squarefixed(unsigned x) {
+ x >>= 16;
+ return x*x;
+}
+
+#if 1 // Newton iter for setLength
+
+static inline unsigned invsqrt_iter(unsigned V, unsigned U) {
+ unsigned x = V * U >> 14;
+ x = x * U >> 14;
+ x = (3 << 14) - x;
+ x = (U >> 1) * x >> 14;
+ return x;
+}
+
+static const uint16_t gInvSqrt14GuessTable[] = {
+ 0x4000, 0x3c57, 0x393e, 0x3695, 0x3441, 0x3235, 0x3061,
+ 0x2ebd, 0x2d41, 0x2be7, 0x2aaa, 0x2987, 0x287a, 0x2780,
+ 0x2698, 0x25be, 0x24f3, 0x2434, 0x2380, 0x22d6, 0x2235,
+ 0x219d, 0x210c, 0x2083, 0x2000, 0x1f82, 0x1f0b, 0x1e99,
+ 0x1e2b, 0x1dc2, 0x1d5d, 0x1cfc, 0x1c9f, 0x1c45, 0x1bee,
+ 0x1b9b, 0x1b4a, 0x1afc, 0x1ab0, 0x1a67, 0x1a20, 0x19dc,
+ 0x1999, 0x1959, 0x191a, 0x18dd, 0x18a2, 0x1868, 0x1830,
+ 0x17fa, 0x17c4, 0x1791, 0x175e, 0x172d, 0x16fd, 0x16ce
+};
+
+#define BUILD_INVSQRT_TABLEx
+#ifdef BUILD_INVSQRT_TABLE
+static void build_invsqrt14_guess_table() {
+ for (int i = 8; i <= 63; i++) {
+ unsigned x = SkToU16((1 << 28) / SkSqrt32(i << 25));
+ printf("0x%x, ", x);
+ }
+ printf("\n");
+}
+#endif
+
+static unsigned fast_invsqrt(uint32_t x) {
+#ifdef BUILD_INVSQRT_TABLE
+ unsigned top2 = x >> 25;
+ SkASSERT(top2 >= 8 && top2 <= 63);
+
+ static bool gOnce;
+ if (!gOnce) {
+ build_invsqrt14_guess_table();
+ gOnce = true;
+ }
+#endif
+
+ unsigned V = x >> 14; // make V .14
+
+ unsigned top = x >> 25;
+ SkASSERT(top >= 8 && top <= 63);
+ SkASSERT(top - 8 < SK_ARRAY_COUNT(gInvSqrt14GuessTable));
+ unsigned U = gInvSqrt14GuessTable[top - 8];
+
+ U = invsqrt_iter(V, U);
+ return invsqrt_iter(V, U);
+}
+
+/* We "normalize" x,y to be .14 values (so we can square them and stay 32bits.
+ Then we Newton-iterate this in .14 space to compute the invser-sqrt, and
+ scale by it at the end. The .14 space means we can execute our iterations
+ and stay in 32bits as well, making the multiplies much cheaper than calling
+ SkFixedMul.
+*/
+bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
+ if (ox == 0) {
+ if (oy == 0) {
+ return false;
+ }
+ this->set(0, SkApplySign(length, SkExtractSign(oy)));
+ return true;
+ }
+ if (oy == 0) {
+ this->set(SkApplySign(length, SkExtractSign(ox)), 0);
+ return true;
+ }
+
+ unsigned x = SkAbs32(ox);
+ unsigned y = SkAbs32(oy);
+ int zeros = SkCLZ(x | y);
+
+ // make x,y 1.14 values so our fast sqr won't overflow
+ if (zeros > 17) {
+ x <<= zeros - 17;
+ y <<= zeros - 17;
+ } else {
+ x >>= 17 - zeros;
+ y >>= 17 - zeros;
+ }
+ SkASSERT((x | y) <= 0x7FFF);
+
+ unsigned invrt = fast_invsqrt(x*x + y*y);
+
+ x = x * invrt >> 12;
+ y = y * invrt >> 12;
+
+ if (length != SK_Fixed1) {
+ x = SkFixedMul(x, length);
+ y = SkFixedMul(y, length);
+ }
+ this->set(SkApplySign(x, SkExtractSign(ox)),
+ SkApplySign(y, SkExtractSign(oy)));
+ return true;
+}
+#else
+/*
+ Normalize x,y, and then scale them by length.
+
+ The obvious way to do this would be the following:
+ S64 tmp1, tmp2;
+ tmp1.setMul(x,x);
+ tmp2.setMul(y,y);
+ tmp1.add(tmp2);
+ len = tmp1.getSqrt();
+ x' = SkFixedDiv(x, len);
+ y' = SkFixedDiv(y, len);
+ This is fine, but slower than what we do below.
+
+ The present technique does not compute the starting length, but
+ rather fiddles with x,y iteratively, all the while checking its
+ magnitude^2 (avoiding a sqrt).
+
+ We normalize by first shifting x,y so that at least one of them
+ has bit 31 set (after taking the abs of them).
+ Then we loop, refining x,y by squaring them and comparing
+ against a very large 1.0 (1 << 28), and then adding or subtracting
+ a delta (which itself is reduced by half each time through the loop).
+ For speed we want the squaring to be with a simple integer mul. To keep
+ that from overflowing we shift our coordinates down until we are dealing
+ with at most 15 bits (2^15-1)^2 * 2 says withing 32 bits)
+ When our square is close to 1.0, we shift x,y down into fixed range.
+*/
+bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
+ if (ox == 0) {
+ if (oy == 0)
+ return false;
+ this->set(0, SkApplySign(length, SkExtractSign(oy)));
+ return true;
+ }
+ if (oy == 0) {
+ this->set(SkApplySign(length, SkExtractSign(ox)), 0);
+ return true;
+ }
+
+ SkFixed x = SkAbs32(ox);
+ SkFixed y = SkAbs32(oy);
+
+ // shift x,y so that the greater of them is 15bits (1.14 fixed point)
+ {
+ int shift = SkCLZ(x | y);
+ // make them .30
+ x <<= shift - 1;
+ y <<= shift - 1;
+ }
+
+ SkFixed dx = x;
+ SkFixed dy = y;
+
+ for (int i = 0; i < 17; i++) {
+ dx >>= 1;
+ dy >>= 1;
+
+ U32 len2 = squarefixed(x) + squarefixed(y);
+ if (len2 >> 28) {
+ x -= dx;
+ y -= dy;
+ } else {
+ x += dx;
+ y += dy;
+ }
+ }
+ x >>= 14;
+ y >>= 14;
+
+#ifdef SK_DEBUGx // measure how far we are from unit-length
+ {
+ static int gMaxError;
+ static int gMaxDiff;
+
+ SkFixed len = fixlen(x, y);
+ int err = len - SK_Fixed1;
+ err = SkAbs32(err);
+
+ if (err > gMaxError) {
+ gMaxError = err;
+ SkDebugf("gMaxError %d\n", err);
+ }
+
+ float fx = SkAbs32(ox)/65536.0f;
+ float fy = SkAbs32(oy)/65536.0f;
+ float mag = sqrtf(fx*fx + fy*fy);
+ fx /= mag;
+ fy /= mag;
+ SkFixed xx = (int)floorf(fx * 65536 + 0.5f);
+ SkFixed yy = (int)floorf(fy * 65536 + 0.5f);
+ err = SkMax32(SkAbs32(xx-x), SkAbs32(yy-y));
+ if (err > gMaxDiff) {
+ gMaxDiff = err;
+ SkDebugf("gMaxDiff %d\n", err);
+ }
+ }
+#endif
+
+ x = SkApplySign(x, SkExtractSign(ox));
+ y = SkApplySign(y, SkExtractSign(oy));
+ if (length != SK_Fixed1) {
+ x = SkFixedMul(x, length);
+ y = SkFixedMul(y, length);
+ }
+
+ this->set(x, y);
+ return true;
+}
+#endif
+
+#endif
+
diff --git a/skia/corecg/SkRect.cpp b/skia/corecg/SkRect.cpp
new file mode 100644
index 0000000..f32b27e
--- /dev/null
+++ b/skia/corecg/SkRect.cpp
@@ -0,0 +1,129 @@
+/* libs/corecg/SkRect.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkRect.h"
+
+void SkIRect::join(int32_t left, int32_t top, int32_t right, int32_t bottom)
+{
+ // do nothing if the params are empty
+ if (left >= right || top >= bottom)
+ return;
+
+ // if we are empty, just assign
+ if (fLeft >= fRight || fTop >= fBottom)
+ this->set(left, top, right, bottom);
+ else
+ {
+ if (left < fLeft) fLeft = left;
+ if (top < fTop) fTop = top;
+ if (right > fRight) fRight = right;
+ if (bottom > fBottom) fBottom = bottom;
+ }
+}
+
+void SkIRect::sort()
+{
+ if (fLeft > fRight)
+ SkTSwap<int32_t>(fLeft, fRight);
+ if (fTop > fBottom)
+ SkTSwap<int32_t>(fTop, fBottom);
+}
+
+/////////////////////////////////////////////////////////////////////////////
+
+void SkRect::sort()
+{
+ if (fLeft > fRight)
+ SkTSwap<SkScalar>(fLeft, fRight);
+ if (fTop > fBottom)
+ SkTSwap<SkScalar>(fTop, fBottom);
+}
+
+void SkRect::toQuad(SkPoint quad[4]) const
+{
+ SkASSERT(quad);
+
+ quad[0].set(fLeft, fTop);
+ quad[1].set(fRight, fTop);
+ quad[2].set(fRight, fBottom);
+ quad[3].set(fLeft, fBottom);
+}
+
+void SkRect::set(const SkPoint pts[], int count)
+{
+ SkASSERT((pts && count > 0) || count == 0);
+
+ if (count <= 0)
+ memset(this, 0, sizeof(SkRect));
+ else
+ {
+ SkScalar l, t, r, b;
+
+ l = r = pts[0].fX;
+ t = b = pts[0].fY;
+
+ for (int i = 1; i < count; i++)
+ {
+ SkScalar x = pts[i].fX;
+ SkScalar y = pts[i].fY;
+
+ if (x < l) l = x; else if (x > r) r = x;
+ if (y < t) t = y; else if (y > b) b = y;
+ }
+ this->set(l, t, r, b);
+ }
+}
+
+bool SkRect::intersect(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom)
+{
+ if (left < right && top < bottom && !this->isEmpty() && // check for empties
+ fLeft < right && left < fRight && fTop < bottom && top < fBottom)
+ {
+ if (fLeft < left) fLeft = left;
+ if (fTop < top) fTop = top;
+ if (fRight > right) fRight = right;
+ if (fBottom > bottom) fBottom = bottom;
+ return true;
+ }
+ return false;
+}
+
+bool SkRect::intersect(const SkRect& r)
+{
+ SkASSERT(&r);
+ return this->intersect(r.fLeft, r.fTop, r.fRight, r.fBottom);
+}
+
+void SkRect::join(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom)
+{
+ // do nothing if the params are empty
+ if (left >= right || top >= bottom)
+ return;
+
+ // if we are empty, just assign
+ if (fLeft >= fRight || fTop >= fBottom)
+ this->set(left, top, right, bottom);
+ else
+ {
+ if (left < fLeft) fLeft = left;
+ if (top < fTop) fTop = top;
+ if (right > fRight) fRight = right;
+ if (bottom > fBottom) fBottom = bottom;
+ }
+}
+
+
diff --git a/skia/corecg/SkRegion.cpp b/skia/corecg/SkRegion.cpp
new file mode 100644
index 0000000..a0860b6e
--- /dev/null
+++ b/skia/corecg/SkRegion.cpp
@@ -0,0 +1,1248 @@
+/* libs/corecg/SkRegion.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkRegionPriv.h"
+#include "SkTemplates.h"
+#include "SkThread.h"
+
+SkDEBUGCODE(int32_t gRgnAllocCounter;)
+
+/////////////////////////////////////////////////////////////////////////////////////////////////
+
+/* Pass in a scanline, beginning with the Left value of the pair (i.e. not the Y beginning)
+*/
+static SkRegion::RunType* skip_scanline(const SkRegion::RunType runs[])
+{
+ while (runs[0] != SkRegion::kRunTypeSentinel)
+ {
+ SkASSERT(runs[0] < runs[1]); // valid span
+ runs += 2;
+ }
+ return (SkRegion::RunType*)(runs + 1); // return past the X-sentinel
+}
+
+static SkRegion::RunType* find_y(const SkRegion::RunType runs[], int y)
+{
+ int top = *runs++;
+ if (top <= y)
+ {
+ for (;;)
+ {
+ int bot = *runs++;
+ if (bot > y)
+ {
+ if (bot == SkRegion::kRunTypeSentinel || *runs == SkRegion::kRunTypeSentinel)
+ break;
+ return (SkRegion::RunType*)runs;
+ }
+ top = bot;
+ runs = skip_scanline(runs);
+ }
+ }
+ return NULL;
+}
+
+// returns true if runs are just a rect
+bool SkRegion::ComputeRunBounds(const SkRegion::RunType runs[], int count, SkIRect* bounds)
+{
+ assert_sentinel(runs[0], false); // top
+
+ if (count == kRectRegionRuns)
+ {
+ assert_sentinel(runs[1], false); // bottom
+ assert_sentinel(runs[2], false); // left
+ assert_sentinel(runs[3], false); // right
+ assert_sentinel(runs[4], true);
+ assert_sentinel(runs[5], true);
+
+ SkASSERT(runs[0] < runs[1]); // valid height
+ SkASSERT(runs[2] < runs[3]); // valid width
+
+ bounds->set(runs[2], runs[0], runs[3], runs[1]);
+ return true;
+ }
+
+ int left = SK_MaxS32;
+ int rite = SK_MinS32;
+ int bot;
+
+ bounds->fTop = *runs++;
+ do {
+ bot = *runs++;
+ if (*runs < SkRegion::kRunTypeSentinel)
+ {
+ if (left > *runs)
+ left = *runs;
+ runs = skip_scanline(runs);
+ if (rite < runs[-2])
+ rite = runs[-2];
+ }
+ else
+ runs += 1; // skip X-sentinel
+ } while (runs[0] < SkRegion::kRunTypeSentinel);
+ bounds->fLeft = left;
+ bounds->fRight = rite;
+ bounds->fBottom = bot;
+ return false;
+}
+
+//////////////////////////////////////////////////////////////////////////
+
+SkRegion::SkRegion()
+{
+ fBounds.set(0, 0, 0, 0);
+ fRunHead = SkRegion_gEmptyRunHeadPtr;
+}
+
+SkRegion::SkRegion(const SkRegion& src)
+{
+ fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
+ this->setRegion(src);
+}
+
+SkRegion::SkRegion(const SkIRect& rect)
+{
+ fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
+ this->setRect(rect);
+}
+
+SkRegion::~SkRegion()
+{
+ this->freeRuns();
+}
+
+void SkRegion::freeRuns()
+{
+ if (fRunHead->isComplex())
+ {
+ SkASSERT(fRunHead->fRefCnt >= 1);
+ if (sk_atomic_dec(&fRunHead->fRefCnt) == 1)
+ {
+ //SkASSERT(gRgnAllocCounter > 0);
+ //SkDEBUGCODE(sk_atomic_dec(&gRgnAllocCounter));
+ //SkDEBUGF(("************** gRgnAllocCounter::free %d\n", gRgnAllocCounter));
+ sk_free(fRunHead);
+ }
+ }
+}
+
+void SkRegion::allocateRuns(int count)
+{
+ fRunHead = RunHead::Alloc(count);
+}
+
+SkRegion& SkRegion::operator=(const SkRegion& src)
+{
+ (void)this->setRegion(src);
+ return *this;
+}
+
+void SkRegion::swap(SkRegion& other)
+{
+ SkTSwap<SkIRect>(fBounds, other.fBounds);
+ SkTSwap<RunHead*>(fRunHead, other.fRunHead);
+}
+
+bool SkRegion::setEmpty()
+{
+ this->freeRuns();
+ fBounds.set(0, 0, 0, 0);
+ fRunHead = SkRegion_gEmptyRunHeadPtr;
+ return false;
+}
+
+bool SkRegion::setRect(int32_t left, int32_t top, int32_t right, int32_t bottom)
+{
+ if (left >= right || top >= bottom)
+ return this->setEmpty();
+
+ this->freeRuns();
+ fBounds.set(left, top, right, bottom);
+ fRunHead = SkRegion_gRectRunHeadPtr;
+ return true;
+}
+
+bool SkRegion::setRect(const SkIRect& r)
+{
+ return this->setRect(r.fLeft, r.fTop, r.fRight, r.fBottom);
+}
+
+bool SkRegion::setRegion(const SkRegion& src)
+{
+ if (this != &src)
+ {
+ this->freeRuns();
+
+ fBounds = src.fBounds;
+ fRunHead = src.fRunHead;
+ if (fRunHead->isComplex())
+ sk_atomic_inc(&fRunHead->fRefCnt);
+ }
+ return fRunHead != SkRegion_gEmptyRunHeadPtr;
+}
+
+bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op)
+{
+ SkRegion tmp(rect);
+
+ return this->op(tmp, rgn, op);
+}
+
+bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op)
+{
+ SkRegion tmp(rect);
+
+ return this->op(rgn, tmp, op);
+}
+
+//////////////////////////////////////////////////////////////////////////////////////
+
+int SkRegion::count_runtype_values(int* itop, int* ibot) const
+{
+ if (this == NULL)
+ {
+ *itop = SK_MinS32;
+ *ibot = SK_MaxS32;
+ return 0;
+ }
+
+ int maxT;
+
+ if (this->isRect())
+ maxT = 2;
+ else
+ {
+ SkASSERT(this->isComplex());
+ // skip the top
+ const RunType* runs = fRunHead->readonly_runs() + 1;
+ maxT = 0;
+
+ do {
+ const RunType* next = skip_scanline(runs + 1);
+ SkASSERT(next > runs);
+ int T = (int)(next - runs - 1);
+ if (maxT < T)
+ maxT = T;
+ runs = next;
+ } while (runs[0] < SkRegion::kRunTypeSentinel);
+ }
+ *itop = fBounds.fTop;
+ *ibot = fBounds.fBottom;
+ return maxT;
+}
+
+bool SkRegion::setRuns(RunType runs[], int count)
+{
+ SkDEBUGCODE(this->validate();)
+ SkASSERT(count > 0);
+
+ if (count <= 2)
+ {
+ // SkDEBUGF(("setRuns: empty\n"));
+ assert_sentinel(runs[count-1], true);
+ return this->setEmpty();
+ }
+
+ // trim off any empty spans from the top and bottom
+ // weird I should need this, perhaps op() could be smarter...
+ if (count > kRectRegionRuns)
+ {
+ RunType* stop = runs + count;
+ assert_sentinel(runs[0], false); // top
+ assert_sentinel(runs[1], false); // bottom
+ if (runs[2] == SkRegion::kRunTypeSentinel) // should be first left...
+ {
+ runs += 2; // skip empty initial span
+ runs[0] = runs[-1]; // set new top to prev bottom
+ assert_sentinel(runs[1], false); // bot: a sentinal would mean two in a row
+ assert_sentinel(runs[2], false); // left
+ assert_sentinel(runs[3], false); // right
+ }
+
+ // now check for a trailing empty span
+ assert_sentinel(stop[-1], true);
+ assert_sentinel(stop[-2], true);
+ assert_sentinel(stop[-3], false); // should be last right
+ if (stop[-4] == SkRegion::kRunTypeSentinel) // eek, stop[-3] was a bottom with no x-runs
+ {
+ stop[-3] = SkRegion::kRunTypeSentinel; // kill empty last span
+ stop -= 2;
+ assert_sentinel(stop[-1], true);
+ assert_sentinel(stop[-2], true);
+ assert_sentinel(stop[-3], false);
+ assert_sentinel(stop[-4], false);
+ assert_sentinel(stop[-5], false);
+ }
+ count = (int)(stop - runs);
+ }
+
+ SkASSERT(count >= kRectRegionRuns);
+
+ if (ComputeRunBounds(runs, count, &fBounds))
+ {
+ // SkDEBUGF(("setRuns: rect[%d %d %d %d]\n", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom));
+ return this->setRect(fBounds);
+ }
+
+ // if we get here, we need to become a complex region
+
+ if (!fRunHead->isComplex() || fRunHead->fRunCount != count)
+ {
+#ifdef SK_DEBUGx
+ SkDebugf("setRuns: rgn [");
+ {
+ const RunType* r = runs;
+
+ SkDebugf(" top: %d\n", *r++);
+ while (*r < SkRegion::kRunTypeSentinel)
+ {
+ SkDebugf(" bottom: %d", *r++);
+ while (*r < SkRegion::kRunTypeSentinel)
+ {
+ SkDebugf(" [%d %d]", r[0], r[1]);
+ r += 2;
+ }
+ SkDebugf("\n");
+ }
+ }
+#endif
+ this->freeRuns();
+ this->allocateRuns(count);
+ }
+
+ // must call this before we can write directly into runs()
+ // in case we are sharing the buffer with another region (copy on write)
+ fRunHead = fRunHead->ensureWritable();
+ memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType));
+
+ SkDEBUGCODE(this->validate();)
+
+ return true;
+}
+
+void SkRegion::BuildRectRuns(const SkIRect& bounds,
+ RunType runs[kRectRegionRuns])
+{
+ runs[0] = bounds.fTop;
+ runs[1] = bounds.fBottom;
+ runs[2] = bounds.fLeft;
+ runs[3] = bounds.fRight;
+ runs[4] = kRunTypeSentinel;
+ runs[5] = kRunTypeSentinel;
+}
+
+static SkRegion::RunType* find_scanline(const SkRegion::RunType runs[], int y)
+{
+ SkASSERT(y >= runs[0]); // if this fails, we didn't do a quick check on the boudns
+
+ runs += 1; // skip top-Y
+ for (;;)
+ {
+ if (runs[0] == SkRegion::kRunTypeSentinel)
+ break;
+ if (y < runs[0])
+ return (SkRegion::RunType*)&runs[1];
+ runs = skip_scanline(runs + 1); // skip the Y value before calling
+ }
+ return NULL;
+}
+
+bool SkRegion::contains(int x, int y) const
+{
+ if (!fBounds.contains(x, y))
+ return false;
+
+ if (this->isRect())
+ return true;
+
+ SkASSERT(this->isComplex());
+ const RunType* runs = find_scanline(fRunHead->readonly_runs(), y);
+
+ if (runs)
+ { for (;;)
+ { if (x < runs[0])
+ break;
+ if (x < runs[1])
+ return true;
+ runs += 2;
+ }
+ }
+ return false;
+}
+
+bool SkRegion::contains(const SkIRect& r) const
+{
+ SkRegion tmp(r);
+
+ return this->contains(tmp);
+}
+
+bool SkRegion::contains(const SkRegion& rgn) const
+{
+ if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds))
+ return false;
+
+ if (this->isRect())
+ return true;
+
+ SkRegion tmp;
+
+ tmp.op(*this, rgn, kUnion_Op);
+ return tmp == *this;
+}
+
+const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[], int* count) const
+{
+ SkASSERT(tmpStorage && count);
+ const RunType* runs = tmpStorage;
+
+ if (this->isEmpty())
+ {
+ tmpStorage[0] = kRunTypeSentinel;
+ *count = 1;
+ }
+ else if (this->isRect())
+ {
+ BuildRectRuns(fBounds, tmpStorage);
+ *count = kRectRegionRuns;
+ }
+ else
+ {
+ *count = fRunHead->fRunCount;
+ runs = fRunHead->readonly_runs();
+ }
+ return runs;
+}
+
+/////////////////////////////////////////////////////////////////////////////////////
+
+int operator==(const SkRegion& a, const SkRegion& b)
+{
+ SkDEBUGCODE(a.validate();)
+ SkDEBUGCODE(b.validate();)
+
+ if (&a == &b)
+ return true;
+ if (a.fBounds != b.fBounds)
+ return false;
+
+ const SkRegion::RunHead* ah = a.fRunHead;
+ const SkRegion::RunHead* bh = b.fRunHead;
+
+ // this catches empties and rects being equal
+ if (ah == bh)
+ return true;
+
+ // now we insist that both are complex (but different ptrs)
+ if (!ah->isComplex() || !bh->isComplex())
+ return false;
+
+ return ah->fRunCount == bh->fRunCount &&
+ !memcmp(ah->readonly_runs(), bh->readonly_runs(),
+ ah->fRunCount * sizeof(SkRegion::RunType));
+}
+
+void SkRegion::translate(int dx, int dy, SkRegion* dst) const
+{
+ SkDEBUGCODE(this->validate();)
+
+ if (NULL == dst)
+ return;
+
+ if (this->isEmpty())
+ dst->setEmpty();
+ else if (this->isRect())
+ dst->setRect(fBounds.fLeft + dx, fBounds.fTop + dy,
+ fBounds.fRight + dx, fBounds.fBottom + dy);
+ else
+ {
+ if (this == dst)
+ {
+ dst->fRunHead = dst->fRunHead->ensureWritable();
+ }
+ else
+ {
+ SkRegion tmp;
+ tmp.allocateRuns(fRunHead->fRunCount);
+ tmp.fBounds = fBounds;
+ dst->swap(tmp);
+ }
+
+ dst->fBounds.offset(dx, dy);
+
+ const RunType* sruns = fRunHead->readonly_runs();
+ RunType* druns = dst->fRunHead->writable_runs();
+
+ *druns++ = (SkRegion::RunType)(*sruns++ + dy); // top
+ for (;;)
+ {
+ int bottom = *sruns++;
+ if (bottom == kRunTypeSentinel)
+ break;
+ *druns++ = (SkRegion::RunType)(bottom + dy); // bottom;
+ for (;;)
+ {
+ int x = *sruns++;
+ if (x == kRunTypeSentinel)
+ break;
+ *druns++ = (SkRegion::RunType)(x + dx);
+ *druns++ = (SkRegion::RunType)(*sruns++ + dx);
+ }
+ *druns++ = kRunTypeSentinel; // x sentinel
+ }
+ *druns++ = kRunTypeSentinel; // y sentinel
+
+ SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount);
+ SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount);
+ }
+
+ SkDEBUGCODE(this->validate();)
+}
+
+/////////////////////////////////////////////////////////////////////////////////////
+
+#if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized
+#pragma warning ( push )
+#pragma warning ( disable : 4701 )
+#endif
+
+#ifdef SK_DEBUG
+static void assert_valid_pair(int left, int rite)
+{
+ SkASSERT(left == SkRegion::kRunTypeSentinel || left < rite);
+}
+#else
+ #define assert_valid_pair(left, rite)
+#endif
+
+struct spanRec {
+ const SkRegion::RunType* fA_runs;
+ const SkRegion::RunType* fB_runs;
+ int fA_left, fA_rite, fB_left, fB_rite;
+ int fLeft, fRite, fInside;
+
+ void init(const SkRegion::RunType a_runs[], const SkRegion::RunType b_runs[])
+ {
+ fA_left = *a_runs++;
+ fA_rite = *a_runs++;
+ fB_left = *b_runs++;
+ fB_rite = *b_runs++;
+
+ fA_runs = a_runs;
+ fB_runs = b_runs;
+ }
+
+ bool done() const
+ {
+ SkASSERT(fA_left <= SkRegion::kRunTypeSentinel);
+ SkASSERT(fB_left <= SkRegion::kRunTypeSentinel);
+ return fA_left == SkRegion::kRunTypeSentinel && fB_left == SkRegion::kRunTypeSentinel;
+ }
+
+ void next()
+ {
+ assert_valid_pair(fA_left, fA_rite);
+ assert_valid_pair(fB_left, fB_rite);
+
+ int inside, left, rite SK_INIT_TO_AVOID_WARNING;
+ bool a_flush = false;
+ bool b_flush = false;
+
+ int a_left = fA_left;
+ int a_rite = fA_rite;
+ int b_left = fB_left;
+ int b_rite = fB_rite;
+
+ if (a_left < b_left)
+ {
+ inside = 1;
+ left = a_left;
+ if (a_rite <= b_left) // [...] <...>
+ {
+ rite = a_rite;
+ a_flush = true;
+ }
+ else // [...<..]...> or [...<...>...]
+ rite = a_left = b_left;
+ }
+ else if (b_left < a_left)
+ {
+ inside = 2;
+ left = b_left;
+ if (b_rite <= a_left) // [...] <...>
+ {
+ rite = b_rite;
+ b_flush = true;
+ }
+ else // [...<..]...> or [...<...>...]
+ rite = b_left = a_left;
+ }
+ else // a_left == b_left
+ {
+ inside = 3;
+ left = a_left; // or b_left
+ if (a_rite <= b_rite)
+ {
+ rite = b_left = a_rite;
+ a_flush = true;
+ }
+ if (b_rite <= a_rite)
+ {
+ rite = a_left = b_rite;
+ b_flush = true;
+ }
+ }
+
+ if (a_flush)
+ {
+ a_left = *fA_runs++;
+ a_rite = *fA_runs++;
+ }
+ if (b_flush)
+ {
+ b_left = *fB_runs++;
+ b_rite = *fB_runs++;
+ }
+
+ SkASSERT(left <= rite);
+
+ // now update our state
+ fA_left = a_left;
+ fA_rite = a_rite;
+ fB_left = b_left;
+ fB_rite = b_rite;
+
+ fLeft = left;
+ fRite = rite;
+ fInside = inside;
+ }
+};
+
+static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[],
+ const SkRegion::RunType b_runs[],
+ SkRegion::RunType dst[],
+ int min, int max)
+{
+ spanRec rec;
+ bool firstInterval = true;
+
+ rec.init(a_runs, b_runs);
+
+ while (!rec.done())
+ {
+ rec.next();
+
+ int left = rec.fLeft;
+ int rite = rec.fRite;
+
+ // add left,rite to our dst buffer (checking for coincidence
+ if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) &&
+ left < rite) // skip if equal
+ {
+ if (firstInterval || dst[-1] < left)
+ {
+ *dst++ = (SkRegion::RunType)(left);
+ *dst++ = (SkRegion::RunType)(rite);
+ firstInterval = false;
+ }
+ else // update the right edge
+ dst[-1] = (SkRegion::RunType)(rite);
+ }
+ }
+
+ *dst++ = SkRegion::kRunTypeSentinel;
+ return dst;
+}
+
+#if defined _WIN32 && _MSC_VER >= 1300
+#pragma warning ( pop )
+#endif
+
+static const struct {
+ uint8_t fMin;
+ uint8_t fMax;
+} gOpMinMax[] = {
+ { 1, 1 }, // Difference
+ { 3, 3 }, // Intersection
+ { 1, 3 }, // Union
+ { 1, 2 } // XOR
+};
+
+class RgnOper {
+public:
+ RgnOper(int top, SkRegion::RunType dst[], SkRegion::Op op)
+ {
+ // need to ensure that the op enum lines up with our minmax array
+ SkASSERT(SkRegion::kDifference_Op == 0);
+ SkASSERT(SkRegion::kIntersect_Op == 1);
+ SkASSERT(SkRegion::kUnion_Op == 2);
+ SkASSERT(SkRegion::kXOR_Op == 3);
+ SkASSERT((unsigned)op <= 3);
+
+ fStartDst = dst;
+ fPrevDst = dst + 1;
+ fPrevLen = 0; // will never match a length from operate_on_span
+ fTop = (SkRegion::RunType)(top); // just a first guess, we might update this
+
+ fMin = gOpMinMax[op].fMin;
+ fMax = gOpMinMax[op].fMax;
+ }
+
+ void addSpan(int bottom, const SkRegion::RunType a_runs[], const SkRegion::RunType b_runs[])
+ {
+ SkRegion::RunType* start = fPrevDst + fPrevLen + 1; // skip X values and slot for the next Y
+ SkRegion::RunType* stop = operate_on_span(a_runs, b_runs, start, fMin, fMax);
+ size_t len = stop - start;
+
+ if (fPrevLen == len && !memcmp(fPrevDst, start, len * sizeof(SkRegion::RunType))) // update Y value
+ fPrevDst[-1] = (SkRegion::RunType)(bottom);
+ else // accept the new span
+ {
+ if (len == 1 && fPrevLen == 0) {
+ fTop = (SkRegion::RunType)(bottom); // just update our bottom
+ } else {
+ start[-1] = (SkRegion::RunType)(bottom);
+ fPrevDst = start;
+ fPrevLen = len;
+ }
+ }
+ }
+
+ int flush()
+ {
+ fStartDst[0] = fTop;
+ fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel;
+ return (int)(fPrevDst - fStartDst + fPrevLen + 1);
+ }
+
+ uint8_t fMin, fMax;
+
+private:
+ SkRegion::RunType* fStartDst;
+ SkRegion::RunType* fPrevDst;
+ size_t fPrevLen;
+ SkRegion::RunType fTop;
+};
+
+static int operate( const SkRegion::RunType a_runs[],
+ const SkRegion::RunType b_runs[],
+ SkRegion::RunType dst[],
+ SkRegion::Op op)
+{
+ const SkRegion::RunType sentinel = SkRegion::kRunTypeSentinel;
+
+ int a_top = *a_runs++;
+ int a_bot = *a_runs++;
+ int b_top = *b_runs++;
+ int b_bot = *b_runs++;
+
+ assert_sentinel(a_top, false);
+ assert_sentinel(a_bot, false);
+ assert_sentinel(b_top, false);
+ assert_sentinel(b_bot, false);
+
+ RgnOper oper(SkMin32(a_top, b_top), dst, op);
+
+ bool firstInterval = true;
+ int prevBot = SkRegion::kRunTypeSentinel; // so we fail the first test
+
+ while (a_bot < SkRegion::kRunTypeSentinel || b_bot < SkRegion::kRunTypeSentinel)
+ {
+ int top, bot SK_INIT_TO_AVOID_WARNING;
+ const SkRegion::RunType* run0 = &sentinel;
+ const SkRegion::RunType* run1 = &sentinel;
+ bool a_flush = false;
+ bool b_flush = false;
+ int inside;
+
+ if (a_top < b_top)
+ {
+ inside = 1;
+ top = a_top;
+ run0 = a_runs;
+ if (a_bot <= b_top) // [...] <...>
+ {
+ bot = a_bot;
+ a_flush = true;
+ }
+ else // [...<..]...> or [...<...>...]
+ bot = a_top = b_top;
+ }
+ else if (b_top < a_top)
+ {
+ inside = 2;
+ top = b_top;
+ run1 = b_runs;
+ if (b_bot <= a_top) // [...] <...>
+ {
+ bot = b_bot;
+ b_flush = true;
+ }
+ else // [...<..]...> or [...<...>...]
+ bot = b_top = a_top;
+ }
+ else // a_top == b_top
+ {
+ inside = 3;
+ top = a_top; // or b_top
+ run0 = a_runs;
+ run1 = b_runs;
+ if (a_bot <= b_bot)
+ {
+ bot = b_top = a_bot;
+ a_flush = true;
+ }
+ if (b_bot <= a_bot)
+ {
+ bot = a_top = b_bot;
+ b_flush = true;
+ }
+ }
+
+ if (top > prevBot)
+ oper.addSpan(top, &sentinel, &sentinel);
+
+// if ((unsigned)(inside - oper.fMin) <= (unsigned)(oper.fMax - oper.fMin))
+ {
+ oper.addSpan(bot, run0, run1);
+ firstInterval = false;
+ }
+
+ if (a_flush)
+ {
+ a_runs = skip_scanline(a_runs);
+ a_top = a_bot;
+ a_bot = *a_runs++;
+ if (a_bot == SkRegion::kRunTypeSentinel)
+ a_top = a_bot;
+ }
+ if (b_flush)
+ {
+ b_runs = skip_scanline(b_runs);
+ b_top = b_bot;
+ b_bot = *b_runs++;
+ if (b_bot == SkRegion::kRunTypeSentinel)
+ b_top = b_bot;
+ }
+
+ prevBot = bot;
+ }
+ return oper.flush();
+}
+
+bool SkRegion::op(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op)
+{
+ SkDEBUGCODE(this->validate();)
+
+ SkASSERT((unsigned)op < kOpCount);
+
+ if (kReplace_Op == op)
+ return this->set(rgnbOrig);
+
+ // swith to using pointers, so we can swap them as needed
+ const SkRegion* rgna = &rgnaOrig;
+ const SkRegion* rgnb = &rgnbOrig;
+ // after this point, do not refer to rgnaOrig or rgnbOrig!!!
+
+ // collaps difference and reverse-difference into just difference
+ if (kReverseDifference_Op == op)
+ {
+ SkTSwap<const SkRegion*>(rgna, rgnb);
+ op = kDifference_Op;
+ }
+
+ SkIRect bounds;
+ bool a_empty = rgna->isEmpty();
+ bool b_empty = rgnb->isEmpty();
+ bool a_rect = rgna->isRect();
+ bool b_rect = rgnb->isRect();
+
+ switch (op) {
+ case kDifference_Op:
+ if (a_empty)
+ return this->setEmpty();
+ if (b_empty || !SkIRect::Intersects(rgna->fBounds, rgnb->fBounds))
+ return this->setRegion(*rgna);
+ break;
+
+ case kIntersect_Op:
+ if ((a_empty | b_empty)
+ || !bounds.intersect(rgna->fBounds, rgnb->fBounds))
+ return this->setEmpty();
+ if (a_rect & b_rect)
+ return this->setRect(bounds);
+ break;
+
+ case kUnion_Op:
+ if (a_empty)
+ return this->setRegion(*rgnb);
+ if (b_empty)
+ return this->setRegion(*rgna);
+ if (a_rect && rgna->fBounds.contains(rgnb->fBounds))
+ return this->setRegion(*rgna);
+ if (b_rect && rgnb->fBounds.contains(rgna->fBounds))
+ return this->setRegion(*rgnb);
+ break;
+
+ case kXOR_Op:
+ if (a_empty)
+ return this->setRegion(*rgnb);
+ if (b_empty)
+ return this->setRegion(*rgna);
+ break;
+ default:
+ SkASSERT(!"unknown region op");
+ return !this->isEmpty();
+ }
+
+ RunType tmpA[kRectRegionRuns];
+ RunType tmpB[kRectRegionRuns];
+
+ int a_count, b_count;
+ const RunType* a_runs = rgna->getRuns(tmpA, &a_count);
+ const RunType* b_runs = rgnb->getRuns(tmpB, &b_count);
+
+ int dstCount = 3 * SkMax32(a_count, b_count);
+ SkAutoSTMalloc<32, RunType> array(dstCount);
+
+ int count = operate(a_runs, b_runs, array.get(), op);
+ SkASSERT(count <= dstCount);
+ return this->setRuns(array.get(), count);
+}
+
+//////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+#include "SkBuffer.h"
+
+uint32_t SkRegion::flatten(void* storage) const {
+ if (NULL == storage) {
+ uint32_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount
+ if (!this->isEmpty()) {
+ size += sizeof(fBounds);
+ if (this->isComplex()) {
+ size += fRunHead->fRunCount * sizeof(RunType);
+ }
+ }
+ return size;
+ }
+
+ SkWBuffer buffer(storage);
+
+ if (this->isEmpty()) {
+ buffer.write32(-1);
+ } else {
+ bool isRect = this->isRect();
+
+ buffer.write32(isRect ? 0 : fRunHead->fRunCount);
+ buffer.write(&fBounds, sizeof(fBounds));
+
+ if (!isRect) {
+ buffer.write(fRunHead->readonly_runs(),
+ fRunHead->fRunCount * sizeof(RunType));
+ }
+ }
+ return buffer.pos();
+}
+
+uint32_t SkRegion::unflatten(const void* storage) {
+ SkRBuffer buffer(storage);
+ SkRegion tmp;
+ int32_t count;
+
+ count = buffer.readS32();
+ if (count >= 0) {
+ buffer.read(&tmp.fBounds, sizeof(tmp.fBounds));
+ if (count == 0) {
+ tmp.fRunHead = SkRegion_gRectRunHeadPtr;
+ } else {
+ tmp.allocateRuns(count);
+ buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(RunType));
+ }
+ }
+ this->swap(tmp);
+ return buffer.pos();
+}
+
+//////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_DEBUG
+
+static const SkRegion::RunType* validate_line(const SkRegion::RunType run[], const SkIRect& bounds)
+{
+ // *run is the bottom of the current span
+ SkASSERT(*run > bounds.fTop);
+ SkASSERT(*run <= bounds.fBottom);
+ run += 1;
+
+ // check for empty span
+ if (*run != SkRegion::kRunTypeSentinel)
+ {
+ int prevRite = bounds.fLeft - 1;
+ do {
+ int left = *run++;
+ int rite = *run++;
+ SkASSERT(left < rite);
+ SkASSERT(left > prevRite);
+ SkASSERT(rite <= bounds.fRight);
+ prevRite = rite;
+ } while (*run < SkRegion::kRunTypeSentinel);
+ }
+ return run + 1; // skip sentinel
+}
+
+void SkRegion::validate() const
+{
+ if (this->isEmpty())
+ {
+ // check for explicit empty (the zero rect), so we can compare rects to know when
+ // two regions are equal (i.e. emptyRectA == emptyRectB)
+ // this is stricter than just asserting fBounds.isEmpty()
+ SkASSERT(fBounds.fLeft == 0 && fBounds.fTop == 0 && fBounds.fRight == 0 && fBounds.fBottom == 0);
+ }
+ else
+ {
+ SkASSERT(!fBounds.isEmpty());
+ if (!this->isRect())
+ {
+ SkASSERT(fRunHead->fRefCnt >= 1);
+ SkASSERT(fRunHead->fRunCount >= kRectRegionRuns);
+
+ const RunType* run = fRunHead->readonly_runs();
+ const RunType* stop = run + fRunHead->fRunCount;
+
+ // check that our bounds match our runs
+ {
+ SkIRect bounds;
+ bool isARect = ComputeRunBounds(run, stop - run, &bounds);
+ SkASSERT(!isARect);
+ SkASSERT(bounds == fBounds);
+ }
+
+ SkASSERT(*run == fBounds.fTop);
+ run++;
+ do {
+ run = validate_line(run, fBounds);
+ } while (*run < kRunTypeSentinel);
+ SkASSERT(run + 1 == stop);
+ }
+ }
+}
+
+void SkRegion::dump() const
+{
+ if (this->isEmpty())
+ SkDebugf(" rgn: empty\n");
+ else
+ {
+ SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
+ if (this->isComplex())
+ {
+ const RunType* runs = fRunHead->readonly_runs();
+ for (int i = 0; i < fRunHead->fRunCount; i++)
+ SkDebugf(" %d", runs[i]);
+ }
+ SkDebugf("\n");
+ }
+}
+
+#endif
+
+/////////////////////////////////////////////////////////////////////////////////////
+
+SkRegion::Iterator::Iterator(const SkRegion& rgn) {
+ this->reset(rgn);
+}
+
+bool SkRegion::Iterator::rewind() {
+ if (fRgn) {
+ this->reset(*fRgn);
+ return true;
+ }
+ return false;
+}
+
+void SkRegion::Iterator::reset(const SkRegion& rgn) {
+ fRgn = &rgn;
+ if (rgn.isEmpty()) {
+ fDone = true;
+ } else {
+ fDone = false;
+ if (rgn.isRect()) {
+ fRect = rgn.fBounds;
+ fRuns = NULL;
+ } else {
+ fRuns = rgn.fRunHead->readonly_runs();
+ fRect.set(fRuns[2], fRuns[0], fRuns[3], fRuns[1]);
+ fRuns += 4;
+ }
+ }
+}
+
+void SkRegion::Iterator::next() {
+ if (fDone) {
+ return;
+ }
+
+ if (fRuns == NULL) { // rect case
+ fDone = true;
+ return;
+ }
+
+ const RunType* runs = fRuns;
+
+ if (runs[0] < kRunTypeSentinel) { // valid X value
+ fRect.fLeft = runs[0];
+ fRect.fRight = runs[1];
+ runs += 2;
+ } else { // we're at the end of a line
+ runs += 1;
+ if (runs[0] < kRunTypeSentinel) { // valid Y value
+ if (runs[1] == kRunTypeSentinel) { // empty line
+ fRect.fTop = runs[0];
+ runs += 2;
+ } else {
+ fRect.fTop = fRect.fBottom;
+ }
+
+ fRect.fBottom = runs[0];
+ assert_sentinel(runs[1], false);
+ fRect.fLeft = runs[1];
+ fRect.fRight = runs[2];
+ runs += 3;
+ } else { // end of rgn
+ fDone = true;
+ }
+ }
+ fRuns = runs;
+}
+
+SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip)
+ : fIter(rgn), fClip(clip), fDone(true) {
+ const SkIRect& r = fIter.rect();
+
+ while (!fIter.done()) {
+ if (r.fTop >= clip.fBottom) {
+ break;
+ }
+ if (fRect.intersect(clip, r)) {
+ fDone = false;
+ break;
+ }
+ fIter.next();
+ }
+}
+
+void SkRegion::Cliperator::next() {
+ if (fDone) {
+ return;
+ }
+
+ const SkIRect& r = fIter.rect();
+
+ fDone = true;
+ fIter.next();
+ while (!fIter.done()) {
+ if (r.fTop >= fClip.fBottom) {
+ break;
+ }
+ if (fRect.intersect(fClip, r)) {
+ fDone = false;
+ break;
+ }
+ fIter.next();
+ }
+}
+
+//////////////////////////////////////////////////////////////////////
+
+SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left, int right)
+{
+ SkDEBUGCODE(rgn.validate();)
+
+ const SkIRect& r = rgn.getBounds();
+
+ fDone = true;
+ if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom && right > r.fLeft && left < r.fRight)
+ {
+ if (rgn.isRect())
+ {
+ if (left < r.fLeft)
+ left = r.fLeft;
+ if (right > r.fRight)
+ right = r.fRight;
+
+ fLeft = left;
+ fRight = right;
+ fRuns = NULL; // means we're a rect, not a rgn
+ fDone = false;
+ }
+ else
+ {
+ const SkRegion::RunType* runs = find_y(rgn.fRunHead->readonly_runs(), y);
+ if (runs)
+ {
+ for (;;)
+ {
+ if (runs[0] >= right) // runs[0..1] is to the right of the span, so we're done
+ break;
+ if (runs[1] <= left) // runs[0..1] is to the left of the span, so continue
+ {
+ runs += 2;
+ continue;
+ }
+ // runs[0..1] intersects the span
+ fRuns = runs;
+ fLeft = left;
+ fRight = right;
+ fDone = false;
+ break;
+ }
+ }
+ }
+ }
+}
+
+bool SkRegion::Spanerator::next(int* left, int* right)
+{
+ if (fDone) return false;
+
+ if (fRuns == NULL) // we're a rect
+ {
+ fDone = true; // ok, now we're done
+ if (left) *left = fLeft;
+ if (right) *right = fRight;
+ return true; // this interval is legal
+ }
+
+ const SkRegion::RunType* runs = fRuns;
+
+ if (runs[0] >= fRight)
+ {
+ fDone = true;
+ return false;
+ }
+
+ SkASSERT(runs[1] > fLeft);
+
+ if (left)
+ *left = SkMax32(fLeft, runs[0]);
+ if (right)
+ *right = SkMin32(fRight, runs[1]);
+ fRuns = runs + 2;
+ return true;
+}
+
diff --git a/skia/corecg/SkRegionPriv.h b/skia/corecg/SkRegionPriv.h
new file mode 100644
index 0000000..80e2e83
--- /dev/null
+++ b/skia/corecg/SkRegionPriv.h
@@ -0,0 +1,89 @@
+/* libs/corecg/SkRegionPriv.h
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#ifndef SkRegionPriv_DEFINED
+#define SkRegionPriv_DEFINED
+
+#include "SkRegion.h"
+#include "SkThread.h"
+
+#define assert_sentinel(value, isSentinel) \
+ SkASSERT(((value) == SkRegion::kRunTypeSentinel) == isSentinel)
+
+//SkDEBUGCODE(extern int32_t gRgnAllocCounter;)
+
+struct SkRegion::RunHead {
+ int32_t fRefCnt;
+ int32_t fRunCount;
+
+ static RunHead* Alloc(int count)
+ {
+ //SkDEBUGCODE(sk_atomic_inc(&gRgnAllocCounter);)
+ //SkDEBUGF(("************** gRgnAllocCounter::alloc %d\n", gRgnAllocCounter));
+
+ SkASSERT(count >= SkRegion::kRectRegionRuns);
+
+ RunHead* head = (RunHead*)sk_malloc_throw(sizeof(RunHead) + count * sizeof(RunType));
+ head->fRefCnt = 1;
+ head->fRunCount = count;
+ return head;
+ }
+
+ bool isComplex() const
+ {
+ return this != SkRegion_gEmptyRunHeadPtr && this != SkRegion_gRectRunHeadPtr;
+ }
+
+ SkRegion::RunType* writable_runs()
+ {
+ SkASSERT(this->isComplex());
+ SkASSERT(fRefCnt == 1);
+ return (SkRegion::RunType*)(this + 1);
+ }
+ const SkRegion::RunType* readonly_runs() const
+ {
+ SkASSERT(this->isComplex());
+ return (const SkRegion::RunType*)(this + 1);
+ }
+
+ RunHead* ensureWritable()
+ {
+ SkASSERT(this->isComplex());
+
+ RunHead* writable = this;
+ if (fRefCnt > 1)
+ {
+ // We need to alloc & copy the current region before we call
+ // sk_atomic_dec because it could be freed in the meantime,
+ // otherwise.
+ writable = Alloc(fRunCount);
+ memcpy(writable->writable_runs(), this->readonly_runs(),
+ fRunCount * sizeof(RunType));
+
+ // fRefCount might have changed since we last checked.
+ // If we own the last reference at this point, we need to
+ // free the memory.
+ if (sk_atomic_dec(&fRefCnt) == 1)
+ {
+ sk_free(this);
+ }
+ }
+ return writable;
+ }
+};
+
+#endif
diff --git a/skia/corecg/SkSinTable.h b/skia/corecg/SkSinTable.h
new file mode 100644
index 0000000..eb3a31c
--- /dev/null
+++ b/skia/corecg/SkSinTable.h
@@ -0,0 +1,285 @@
+/* libs/corecg/SkSinTable.h
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#ifndef SkSinTable_DEFINED
+#define SkSinTable_DEFINED
+
+#include "SkTypes.h"
+
+/* Fixed point values (low 16 bits) of sin(radians) for
+ radians in [0...PI/2)
+*/
+static const uint16_t gSkSinTable[256] = {
+ 0x0000,
+ 0x0192,
+ 0x0324,
+ 0x04B6,
+ 0x0648,
+ 0x07DA,
+ 0x096C,
+ 0x0AFE,
+ 0x0C8F,
+ 0x0E21,
+ 0x0FB2,
+ 0x1144,
+ 0x12D5,
+ 0x1466,
+ 0x15F6,
+ 0x1787,
+ 0x1917,
+ 0x1AA7,
+ 0x1C37,
+ 0x1DC7,
+ 0x1F56,
+ 0x20E5,
+ 0x2273,
+ 0x2402,
+ 0x2590,
+ 0x271D,
+ 0x28AA,
+ 0x2A37,
+ 0x2BC4,
+ 0x2D50,
+ 0x2EDB,
+ 0x3066,
+ 0x31F1,
+ 0x337B,
+ 0x3505,
+ 0x368E,
+ 0x3817,
+ 0x399F,
+ 0x3B26,
+ 0x3CAD,
+ 0x3E33,
+ 0x3FB9,
+ 0x413E,
+ 0x42C3,
+ 0x4447,
+ 0x45CA,
+ 0x474D,
+ 0x48CE,
+ 0x4A50,
+ 0x4BD0,
+ 0x4D50,
+ 0x4ECF,
+ 0x504D,
+ 0x51CA,
+ 0x5347,
+ 0x54C3,
+ 0x563E,
+ 0x57B8,
+ 0x5931,
+ 0x5AAA,
+ 0x5C22,
+ 0x5D98,
+ 0x5F0E,
+ 0x6083,
+ 0x61F7,
+ 0x636A,
+ 0x64DC,
+ 0x664D,
+ 0x67BD,
+ 0x692D,
+ 0x6A9B,
+ 0x6C08,
+ 0x6D74,
+ 0x6EDF,
+ 0x7049,
+ 0x71B1,
+ 0x7319,
+ 0x7480,
+ 0x75E5,
+ 0x774A,
+ 0x78AD,
+ 0x7A0F,
+ 0x7B70,
+ 0x7CD0,
+ 0x7E2E,
+ 0x7F8B,
+ 0x80E7,
+ 0x8242,
+ 0x839C,
+ 0x84F4,
+ 0x864B,
+ 0x87A1,
+ 0x88F5,
+ 0x8A48,
+ 0x8B9A,
+ 0x8CEA,
+ 0x8E39,
+ 0x8F87,
+ 0x90D3,
+ 0x921E,
+ 0x9368,
+ 0x94B0,
+ 0x95F6,
+ 0x973C,
+ 0x987F,
+ 0x99C2,
+ 0x9B02,
+ 0x9C42,
+ 0x9D7F,
+ 0x9EBC,
+ 0x9FF6,
+ 0xA12F,
+ 0xA267,
+ 0xA39D,
+ 0xA4D2,
+ 0xA605,
+ 0xA736,
+ 0xA866,
+ 0xA994,
+ 0xAAC0,
+ 0xABEB,
+ 0xAD14,
+ 0xAE3B,
+ 0xAF61,
+ 0xB085,
+ 0xB1A8,
+ 0xB2C8,
+ 0xB3E7,
+ 0xB504,
+ 0xB620,
+ 0xB73A,
+ 0xB852,
+ 0xB968,
+ 0xBA7C,
+ 0xBB8F,
+ 0xBCA0,
+ 0xBDAE,
+ 0xBEBC,
+ 0xBFC7,
+ 0xC0D0,
+ 0xC1D8,
+ 0xC2DE,
+ 0xC3E2,
+ 0xC4E3,
+ 0xC5E4,
+ 0xC6E2,
+ 0xC7DE,
+ 0xC8D8,
+ 0xC9D1,
+ 0xCAC7,
+ 0xCBBB,
+ 0xCCAE,
+ 0xCD9F,
+ 0xCE8D,
+ 0xCF7A,
+ 0xD064,
+ 0xD14D,
+ 0xD233,
+ 0xD318,
+ 0xD3FA,
+ 0xD4DB,
+ 0xD5B9,
+ 0xD695,
+ 0xD770,
+ 0xD848,
+ 0xD91E,
+ 0xD9F2,
+ 0xDAC4,
+ 0xDB94,
+ 0xDC61,
+ 0xDD2D,
+ 0xDDF6,
+ 0xDEBE,
+ 0xDF83,
+ 0xE046,
+ 0xE106,
+ 0xE1C5,
+ 0xE282,
+ 0xE33C,
+ 0xE3F4,
+ 0xE4AA,
+ 0xE55E,
+ 0xE60F,
+ 0xE6BE,
+ 0xE76B,
+ 0xE816,
+ 0xE8BF,
+ 0xE965,
+ 0xEA09,
+ 0xEAAB,
+ 0xEB4B,
+ 0xEBE8,
+ 0xEC83,
+ 0xED1C,
+ 0xEDB2,
+ 0xEE46,
+ 0xEED8,
+ 0xEF68,
+ 0xEFF5,
+ 0xF080,
+ 0xF109,
+ 0xF18F,
+ 0xF213,
+ 0xF294,
+ 0xF314,
+ 0xF391,
+ 0xF40B,
+ 0xF484,
+ 0xF4FA,
+ 0xF56D,
+ 0xF5DE,
+ 0xF64D,
+ 0xF6BA,
+ 0xF724,
+ 0xF78B,
+ 0xF7F1,
+ 0xF853,
+ 0xF8B4,
+ 0xF912,
+ 0xF96E,
+ 0xF9C7,
+ 0xFA1E,
+ 0xFA73,
+ 0xFAC5,
+ 0xFB14,
+ 0xFB61,
+ 0xFBAC,
+ 0xFBF5,
+ 0xFC3B,
+ 0xFC7E,
+ 0xFCBF,
+ 0xFCFE,
+ 0xFD3A,
+ 0xFD74,
+ 0xFDAB,
+ 0xFDE0,
+ 0xFE13,
+ 0xFE43,
+ 0xFE70,
+ 0xFE9B,
+ 0xFEC4,
+ 0xFEEA,
+ 0xFF0E,
+ 0xFF2F,
+ 0xFF4E,
+ 0xFF6A,
+ 0xFF84,
+ 0xFF9C,
+ 0xFFB1,
+ 0xFFC3,
+ 0xFFD3,
+ 0xFFE1,
+ 0xFFEC,
+ 0xFFF4,
+ 0xFFFB,
+ 0xFFFE
+};
+
+#endif
diff --git a/skia/corecg/SkTSort.h b/skia/corecg/SkTSort.h
new file mode 100644
index 0000000..44f05bb
--- /dev/null
+++ b/skia/corecg/SkTSort.h
@@ -0,0 +1,65 @@
+/* libs/corecg/SkTSort.h
+**
+** Copyright 2006, Google Inc.
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#ifndef SkTSort_DEFINED
+#define SkTSort_DEFINED
+
+#include "SkTypes.h"
+
+template <typename T>
+void SkTHeapSort_SiftDown(T array[], int root, int bottom)
+{
+ int root2 = root << 1;
+
+ while (root2 <= bottom)
+ {
+ int maxChild;
+
+ if (root2 == bottom)
+ maxChild = root2;
+ else if (array[root2] > array[root2 + 1])
+ maxChild = root2;
+ else
+ maxChild = root2 + 1;
+
+ if (array[root] < array[maxChild])
+ {
+ SkTSwap<T>(array[root], array[maxChild]);
+ root = maxChild;
+ root2 = root << 1;
+ }
+ else
+ break;
+ }
+}
+
+template <typename T>
+void SkTHeapSort(T array[], int count)
+{
+ int i;
+
+ for (i = count/2 - 1; i >= 0; --i)
+ SkTHeapSort_SiftDown<T>(array, i, count);
+
+ for (i = count - 2; i >= 0; --i)
+ {
+ SkTSwap<T>(array[0], array[i + 1]);
+ SkTHeapSort_SiftDown<T>(array, 0, i);
+ }
+}
+
+#endif
generated by cgit v1.1 at 2025-02-08 18:09:49 +0000