10910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/*
20910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Copyright (C) 2006-2008 The Android Open Source Project
30910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project *
40910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License");
50910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * you may not use this file except in compliance with the License.
60910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * You may obtain a copy of the License at
70910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project *
80910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project *      http://www.apache.org/licenses/LICENSE-2.0
90910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project *
100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Unless required by applicable law or agreed to in writing, software
110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS,
120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * See the License for the specific language governing permissions and
140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * limitations under the License.
150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project */
160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#include "SkPoint.h"
180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkIPoint::rotateCW(SkIPoint* dst) const {
200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT(dst);
210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    // use a tmp in case this == dst
230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    int32_t tmp = fX;
240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->fX = -fY;
250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->fY = tmp;
260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkIPoint::rotateCCW(SkIPoint* dst) const {
290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT(dst);
300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    // use a tmp in case this == dst
320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    int32_t tmp = fX;
330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->fX = fY;
340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->fY = -tmp;
350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project///////////////////////////////////////////////////////////////////////////////
380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenbergervoid SkPoint::setIRectFan(int l, int t, int r, int b, size_t stride) {
4035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    SkASSERT(stride >= sizeof(SkPoint));
4135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
4235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    ((SkPoint*)((intptr_t)this + 0 * stride))->set(SkIntToScalar(l),
4335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger                                                   SkIntToScalar(t));
4435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    ((SkPoint*)((intptr_t)this + 1 * stride))->set(SkIntToScalar(l),
4535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger                                                   SkIntToScalar(b));
4635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    ((SkPoint*)((intptr_t)this + 2 * stride))->set(SkIntToScalar(r),
4735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger                                                   SkIntToScalar(b));
4835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    ((SkPoint*)((intptr_t)this + 3 * stride))->set(SkIntToScalar(r),
4935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger                                                   SkIntToScalar(t));
5035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger}
5135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
5235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenbergervoid SkPoint::setRectFan(SkScalar l, SkScalar t, SkScalar r, SkScalar b,
5335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger                         size_t stride) {
5435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    SkASSERT(stride >= sizeof(SkPoint));
5535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
5635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    ((SkPoint*)((intptr_t)this + 0 * stride))->set(l, t);
5735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    ((SkPoint*)((intptr_t)this + 1 * stride))->set(l, b);
5835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    ((SkPoint*)((intptr_t)this + 2 * stride))->set(r, b);
5935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    ((SkPoint*)((intptr_t)this + 3 * stride))->set(r, t);
6035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger}
6135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkPoint::rotateCW(SkPoint* dst) const {
630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT(dst);
640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    // use a tmp in case this == dst
660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkScalar tmp = fX;
670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->fX = -fY;
680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->fY = tmp;
690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkPoint::rotateCCW(SkPoint* dst) const {
720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT(dst);
730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    // use a tmp in case this == dst
750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkScalar tmp = fX;
760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->fX = fY;
770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->fY = -tmp;
780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkPoint::scale(SkScalar scale, SkPoint* dst) const {
810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT(dst);
820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale));
830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#define kNearlyZero     (SK_Scalar1 / 8092)
860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::normalize() {
880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return this->setLength(fX, fY, SK_Scalar1);
890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setNormalize(SkScalar x, SkScalar y) {
920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return this->setLength(x, y, SK_Scalar1);
930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setLength(SkScalar length) {
960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return this->setLength(fX, fY, length);
970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef SK_SCALAR_IS_FLOAT
1000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
1020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return sk_float_sqrt(dx * dx + dy * dy);
1030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
1040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
10575c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike ReedSkScalar SkPoint::Normalize(SkPoint* pt) {
10675c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed    float mag = SkPoint::Length(pt->fX, pt->fY);
10775c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed    if (mag > kNearlyZero) {
10875c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed        float scale = 1 / mag;
10975c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed        pt->fX *= scale;
11075c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed        pt->fY *= scale;
11175c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed        return mag;
11275c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed    }
11375c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed    return 0;
11475c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed}
11575c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed
1160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setLength(float x, float y, float length) {
1170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    float mag = sk_float_sqrt(x * x + y * y);
1180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (mag > kNearlyZero) {
1190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        length /= mag;
1200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        fX = x * length;
1210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        fY = y * length;
1220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        return true;
1230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
1240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return false;
1250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
1260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#else
1280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#include "Sk64.h"
1300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
1320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    Sk64    tmp1, tmp2;
1330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    tmp1.setMul(dx, dx);
1350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    tmp2.setMul(dy, dy);
1360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    tmp1.add(tmp2);
1370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return tmp1.getSqrt();
1390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
1400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef SK_DEBUGx
1420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic SkFixed fixlen(SkFixed x, SkFixed y) {
1430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    float fx = (float)x;
1440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    float fy = (float)y;
1450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return (int)floorf(sqrtf(fx*fx + fy*fy) + 0.5f);
1470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
1480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif
1490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic inline uint32_t squarefixed(unsigned x) {
1510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    x >>= 16;
1520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return x*x;
1530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
1540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#if 1   // Newton iter for setLength
1560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic inline unsigned invsqrt_iter(unsigned V, unsigned U) {
1580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    unsigned x = V * U >> 14;
1590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    x = x * U >> 14;
1600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    x = (3 << 14) - x;
1610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    x = (U >> 1) * x >> 14;
1620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return x;
1630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
1640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic const uint16_t gInvSqrt14GuessTable[] = {
1660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    0x4000, 0x3c57, 0x393e, 0x3695, 0x3441, 0x3235, 0x3061,
1670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    0x2ebd, 0x2d41, 0x2be7, 0x2aaa, 0x2987, 0x287a, 0x2780,
1680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    0x2698, 0x25be, 0x24f3, 0x2434, 0x2380, 0x22d6, 0x2235,
1690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    0x219d, 0x210c, 0x2083, 0x2000, 0x1f82, 0x1f0b, 0x1e99,
1700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    0x1e2b, 0x1dc2, 0x1d5d, 0x1cfc, 0x1c9f, 0x1c45, 0x1bee,
1710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    0x1b9b, 0x1b4a, 0x1afc, 0x1ab0, 0x1a67, 0x1a20, 0x19dc,
1720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    0x1999, 0x1959, 0x191a, 0x18dd, 0x18a2, 0x1868, 0x1830,
1730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    0x17fa, 0x17c4, 0x1791, 0x175e, 0x172d, 0x16fd, 0x16ce
1740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project};
1750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#define BUILD_INVSQRT_TABLEx
1770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef BUILD_INVSQRT_TABLE
1780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic void build_invsqrt14_guess_table() {
1790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    for (int i = 8; i <= 63; i++) {
1800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        unsigned x = SkToU16((1 << 28) / SkSqrt32(i << 25));
1810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        printf("0x%x, ", x);
1820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
1830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    printf("\n");
1840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
1850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif
1860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic unsigned fast_invsqrt(uint32_t x) {
1880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef BUILD_INVSQRT_TABLE
1890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    unsigned top2 = x >> 25;
1900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT(top2 >= 8 && top2 <= 63);
1910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    static bool gOnce;
1930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (!gOnce) {
1940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        build_invsqrt14_guess_table();
1950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        gOnce = true;
1960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
1970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif
1980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
1990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    unsigned V = x >> 14;   // make V .14
2000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    unsigned top = x >> 25;
2020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT(top >= 8 && top <= 63);
2030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT(top - 8 < SK_ARRAY_COUNT(gInvSqrt14GuessTable));
2040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    unsigned U = gInvSqrt14GuessTable[top - 8];
2050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    U = invsqrt_iter(V, U);
2070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return invsqrt_iter(V, U);
2080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
2090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/*  We "normalize" x,y to be .14 values (so we can square them and stay 32bits.
2110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    Then we Newton-iterate this in .14 space to compute the invser-sqrt, and
2120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    scale by it at the end. The .14 space means we can execute our iterations
2130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    and stay in 32bits as well, making the multiplies much cheaper than calling
2140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkFixedMul.
2150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project*/
2160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
2170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (ox == 0) {
2180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        if (oy == 0) {
2190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            return false;
2200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        }
2210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        this->set(0, SkApplySign(length, SkExtractSign(oy)));
2220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        return true;
2230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
2240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (oy == 0) {
2250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        this->set(SkApplySign(length, SkExtractSign(ox)), 0);
2260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        return true;
2270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
2280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    unsigned x = SkAbs32(ox);
2300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    unsigned y = SkAbs32(oy);
2310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    int zeros = SkCLZ(x | y);
2320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    // make x,y 1.14 values so our fast sqr won't overflow
2340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (zeros > 17) {
2350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        x <<= zeros - 17;
2360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        y <<= zeros - 17;
2370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    } else {
2380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        x >>= 17 - zeros;
2390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        y >>= 17 - zeros;
2400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
2410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkASSERT((x | y) <= 0x7FFF);
2420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    unsigned invrt = fast_invsqrt(x*x + y*y);
2440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    x = x * invrt >> 12;
2460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    y = y * invrt >> 12;
2470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (length != SK_Fixed1) {
2490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        x = SkFixedMul(x, length);
2500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        y = SkFixedMul(y, length);
2510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
2520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    this->set(SkApplySign(x, SkExtractSign(ox)),
2530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project              SkApplySign(y, SkExtractSign(oy)));
2540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return true;
2550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
2560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#else
2570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/*
2580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    Normalize x,y, and then scale them by length.
2590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    The obvious way to do this would be the following:
2610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        S64 tmp1, tmp2;
2620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        tmp1.setMul(x,x);
2630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        tmp2.setMul(y,y);
2640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        tmp1.add(tmp2);
2650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        len = tmp1.getSqrt();
2660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        x' = SkFixedDiv(x, len);
2670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        y' = SkFixedDiv(y, len);
2680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    This is fine, but slower than what we do below.
2690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    The present technique does not compute the starting length, but
2710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    rather fiddles with x,y iteratively, all the while checking its
2720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    magnitude^2 (avoiding a sqrt).
2730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    We normalize by first shifting x,y so that at least one of them
2750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    has bit 31 set (after taking the abs of them).
2760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    Then we loop, refining x,y by squaring them and comparing
2770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    against a very large 1.0 (1 << 28), and then adding or subtracting
2780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    a delta (which itself is reduced by half each time through the loop).
2790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    For speed we want the squaring to be with a simple integer mul. To keep
2800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    that from overflowing we shift our coordinates down until we are dealing
2810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    with at most 15 bits (2^15-1)^2 * 2 says withing 32 bits)
2820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    When our square is close to 1.0, we shift x,y down into fixed range.
2830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project*/
2840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
2850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (ox == 0) {
2860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        if (oy == 0)
2870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            return false;
2880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        this->set(0, SkApplySign(length, SkExtractSign(oy)));
2890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        return true;
2900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
2910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (oy == 0) {
2920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        this->set(SkApplySign(length, SkExtractSign(ox)), 0);
2930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        return true;
2940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
2950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkFixed x = SkAbs32(ox);
2970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkFixed y = SkAbs32(oy);
2980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
2990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    // shift x,y so that the greater of them is 15bits (1.14 fixed point)
3000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    {
3010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        int shift = SkCLZ(x | y);
3020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        // make them .30
3030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        x <<= shift - 1;
3040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        y <<= shift - 1;
3050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
3060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkFixed dx = x;
3080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    SkFixed dy = y;
3090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    for (int i = 0; i < 17; i++) {
3110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        dx >>= 1;
3120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        dy >>= 1;
3130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        U32 len2 = squarefixed(x) + squarefixed(y);
3150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        if (len2 >> 28) {
3160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            x -= dx;
3170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            y -= dy;
3180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        } else {
3190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            x += dx;
3200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            y += dy;
3210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        }
3220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
3230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    x >>= 14;
3240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    y >>= 14;
3250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef SK_DEBUGx    // measure how far we are from unit-length
3270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    {
3280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        static int gMaxError;
3290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        static int gMaxDiff;
3300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        SkFixed len = fixlen(x, y);
3320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        int err = len - SK_Fixed1;
3330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        err = SkAbs32(err);
3340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        if (err > gMaxError) {
3360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            gMaxError = err;
3370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            SkDebugf("gMaxError %d\n", err);
3380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        }
3390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        float fx = SkAbs32(ox)/65536.0f;
3410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        float fy = SkAbs32(oy)/65536.0f;
3420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        float mag = sqrtf(fx*fx + fy*fy);
3430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        fx /= mag;
3440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        fy /= mag;
3450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        SkFixed xx = (int)floorf(fx * 65536 + 0.5f);
3460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        SkFixed yy = (int)floorf(fy * 65536 + 0.5f);
3470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        err = SkMax32(SkAbs32(xx-x), SkAbs32(yy-y));
3480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        if (err > gMaxDiff) {
3490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            gMaxDiff = err;
3500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project            SkDebugf("gMaxDiff %d\n", err);
3510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        }
3520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
3530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif
3540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    x = SkApplySign(x, SkExtractSign(ox));
3560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    y = SkApplySign(y, SkExtractSign(oy));
3570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    if (length != SK_Fixed1) {
3580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        x = SkFixedMul(x, length);
3590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project        y = SkFixedMul(y, length);
3600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    }
3610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    this->set(x, y);
3630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project    return true;
3640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}
3650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif
3660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
3670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif
3680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project
36935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger///////////////////////////////////////////////////////////////////////////////
37035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
37135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek SollenbergerSkScalar SkPoint::distanceToLineSegmentBetweenSqd(const SkPoint& a,
37235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger                                                  const SkPoint& b) const {
37335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    // See comments to distanceToLineBetweenSqd. If the projection of c onto
37435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    // u is between a and b then this returns the same result as that
37535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    // function. Otherwise, it returns the distance to the closer of a and
37635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    // b. Let the projection of v onto u be v'.  There are three cases:
37735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    //    1. v' points opposite to u. c is not between a and b and is closer
37835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    //       to a than b.
37935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    //    2. v' points along u and has magnitude less than y. c is between
38035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    //       a and b and the distance to the segment is the same as distance
38135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    //       to the line ab.
38235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    //    3. v' points along u and has greater magnitude than u. c is not
38335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    //       not between a and b and is closer to b than a.
38435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're
38535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise
38635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to
38735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    // avoid a sqrt to compute |u|.
38835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
38935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    SkVector u = b - a;
39035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    SkVector v = *this - a;
39135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
39235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    SkScalar uLengthSqd = u.lengthSqd();
39335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    SkScalar uDotV = SkPoint::DotProduct(u, v);
39435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
39535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    if (uDotV <= 0) {
39635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger        return v.lengthSqd();
39735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    } else if (uDotV > uLengthSqd) {
39835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger        return b.distanceToSqd(*this);
39935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    } else {
40035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger        SkScalar det = u.cross(v);
40135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger        return SkScalarMulDiv(det, det, uLengthSqd);
40235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger    }
40335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger}
40435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger
405