1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkMath.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,296 @@
1.4 +/*
1.5 + * Copyright 2008 The Android Open Source Project
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#include "SkMathPriv.h"
1.12 +#include "SkFloatBits.h"
1.13 +#include "SkFloatingPoint.h"
1.14 +#include "SkScalar.h"
1.15 +
1.16 +const uint32_t gIEEENotANumber = 0x7FFFFFFF;
1.17 +const uint32_t gIEEEInfinity = 0x7F800000;
1.18 +const uint32_t gIEEENegativeInfinity = 0xFF800000;
1.19 +
1.20 +#define sub_shift(zeros, x, n) \
1.21 + zeros -= n; \
1.22 + x >>= n
1.23 +
1.24 +int SkCLZ_portable(uint32_t x) {
1.25 + if (x == 0) {
1.26 + return 32;
1.27 + }
1.28 +
1.29 + int zeros = 31;
1.30 + if (x & 0xFFFF0000) {
1.31 + sub_shift(zeros, x, 16);
1.32 + }
1.33 + if (x & 0xFF00) {
1.34 + sub_shift(zeros, x, 8);
1.35 + }
1.36 + if (x & 0xF0) {
1.37 + sub_shift(zeros, x, 4);
1.38 + }
1.39 + if (x & 0xC) {
1.40 + sub_shift(zeros, x, 2);
1.41 + }
1.42 + if (x & 0x2) {
1.43 + sub_shift(zeros, x, 1);
1.44 + }
1.45 +
1.46 + return zeros;
1.47 +}
1.48 +
1.49 +int32_t SkMulDiv(int32_t numer1, int32_t numer2, int32_t denom) {
1.50 + SkASSERT(denom);
1.51 +
1.52 + int64_t tmp = sk_64_mul(numer1, numer2) / denom;
1.53 + return sk_64_asS32(tmp);
1.54 +}
1.55 +
1.56 +SkFixed SkFixedMul_portable(SkFixed a, SkFixed b) {
1.57 +#if defined(SkLONGLONG)
1.58 + return static_cast<SkFixed>((int64_t)a * b >> 16);
1.59 +#else
1.60 + int sa = SkExtractSign(a);
1.61 + int sb = SkExtractSign(b);
1.62 + // now make them positive
1.63 + a = SkApplySign(a, sa);
1.64 + b = SkApplySign(b, sb);
1.65 +
1.66 + uint32_t ah = a >> 16;
1.67 + uint32_t al = a & 0xFFFF;
1.68 + uint32_t bh = b >> 16;
1.69 + uint32_t bl = b & 0xFFFF;
1.70 +
1.71 + uint32_t R = ah * b + al * bh + (al * bl >> 16);
1.72 +
1.73 + return SkApplySign(R, sa ^ sb);
1.74 +#endif
1.75 +}
1.76 +
1.77 +///////////////////////////////////////////////////////////////////////////////
1.78 +
1.79 +#define DIVBITS_ITER(n) \
1.80 + case n: \
1.81 + if ((numer = (numer << 1) - denom) >= 0) \
1.82 + result |= 1 << (n - 1); else numer += denom
1.83 +
1.84 +int32_t SkDivBits(int32_t numer, int32_t denom, int shift_bias) {
1.85 + SkASSERT(denom != 0);
1.86 + if (numer == 0) {
1.87 + return 0;
1.88 + }
1.89 +
1.90 + // make numer and denom positive, and sign hold the resulting sign
1.91 + int32_t sign = SkExtractSign(numer ^ denom);
1.92 + numer = SkAbs32(numer);
1.93 + denom = SkAbs32(denom);
1.94 +
1.95 + int nbits = SkCLZ(numer) - 1;
1.96 + int dbits = SkCLZ(denom) - 1;
1.97 + int bits = shift_bias - nbits + dbits;
1.98 +
1.99 + if (bits < 0) { // answer will underflow
1.100 + return 0;
1.101 + }
1.102 + if (bits > 31) { // answer will overflow
1.103 + return SkApplySign(SK_MaxS32, sign);
1.104 + }
1.105 +
1.106 + denom <<= dbits;
1.107 + numer <<= nbits;
1.108 +
1.109 + SkFixed result = 0;
1.110 +
1.111 + // do the first one
1.112 + if ((numer -= denom) >= 0) {
1.113 + result = 1;
1.114 + } else {
1.115 + numer += denom;
1.116 + }
1.117 +
1.118 + // Now fall into our switch statement if there are more bits to compute
1.119 + if (bits > 0) {
1.120 + // make room for the rest of the answer bits
1.121 + result <<= bits;
1.122 + switch (bits) {
1.123 + DIVBITS_ITER(31); DIVBITS_ITER(30); DIVBITS_ITER(29);
1.124 + DIVBITS_ITER(28); DIVBITS_ITER(27); DIVBITS_ITER(26);
1.125 + DIVBITS_ITER(25); DIVBITS_ITER(24); DIVBITS_ITER(23);
1.126 + DIVBITS_ITER(22); DIVBITS_ITER(21); DIVBITS_ITER(20);
1.127 + DIVBITS_ITER(19); DIVBITS_ITER(18); DIVBITS_ITER(17);
1.128 + DIVBITS_ITER(16); DIVBITS_ITER(15); DIVBITS_ITER(14);
1.129 + DIVBITS_ITER(13); DIVBITS_ITER(12); DIVBITS_ITER(11);
1.130 + DIVBITS_ITER(10); DIVBITS_ITER( 9); DIVBITS_ITER( 8);
1.131 + DIVBITS_ITER( 7); DIVBITS_ITER( 6); DIVBITS_ITER( 5);
1.132 + DIVBITS_ITER( 4); DIVBITS_ITER( 3); DIVBITS_ITER( 2);
1.133 + // we merge these last two together, makes GCC make better ARM
1.134 + default:
1.135 + DIVBITS_ITER( 1);
1.136 + }
1.137 + }
1.138 +
1.139 + if (result < 0) {
1.140 + result = SK_MaxS32;
1.141 + }
1.142 + return SkApplySign(result, sign);
1.143 +}
1.144 +
1.145 +/* www.worldserver.com/turk/computergraphics/FixedSqrt.pdf
1.146 +*/
1.147 +int32_t SkSqrtBits(int32_t x, int count) {
1.148 + SkASSERT(x >= 0 && count > 0 && (unsigned)count <= 30);
1.149 +
1.150 + uint32_t root = 0;
1.151 + uint32_t remHi = 0;
1.152 + uint32_t remLo = x;
1.153 +
1.154 + do {
1.155 + root <<= 1;
1.156 +
1.157 + remHi = (remHi<<2) | (remLo>>30);
1.158 + remLo <<= 2;
1.159 +
1.160 + uint32_t testDiv = (root << 1) + 1;
1.161 + if (remHi >= testDiv) {
1.162 + remHi -= testDiv;
1.163 + root++;
1.164 + }
1.165 + } while (--count >= 0);
1.166 +
1.167 + return root;
1.168 +}
1.169 +
1.170 +///////////////////////////////////////////////////////////////////////////////
1.171 +
1.172 +float SkScalarSinCos(float radians, float* cosValue) {
1.173 + float sinValue = sk_float_sin(radians);
1.174 +
1.175 + if (cosValue) {
1.176 + *cosValue = sk_float_cos(radians);
1.177 + if (SkScalarNearlyZero(*cosValue)) {
1.178 + *cosValue = 0;
1.179 + }
1.180 + }
1.181 +
1.182 + if (SkScalarNearlyZero(sinValue)) {
1.183 + sinValue = 0;
1.184 + }
1.185 + return sinValue;
1.186 +}
1.187 +
1.188 +#define INTERP_SINTABLE
1.189 +#define BUILD_TABLE_AT_RUNTIMEx
1.190 +
1.191 +#define kTableSize 256
1.192 +
1.193 +#ifdef BUILD_TABLE_AT_RUNTIME
1.194 + static uint16_t gSkSinTable[kTableSize];
1.195 +
1.196 + static void build_sintable(uint16_t table[]) {
1.197 + for (int i = 0; i < kTableSize; i++) {
1.198 + double rad = i * 3.141592653589793 / (2*kTableSize);
1.199 + double val = sin(rad);
1.200 + int ival = (int)(val * SK_Fixed1);
1.201 + table[i] = SkToU16(ival);
1.202 + }
1.203 + }
1.204 +#else
1.205 + #include "SkSinTable.h"
1.206 +#endif
1.207 +
1.208 +#define SK_Fract1024SizeOver2PI 0x28BE60 /* floatToFract(1024 / 2PI) */
1.209 +
1.210 +#ifdef INTERP_SINTABLE
1.211 +static SkFixed interp_table(const uint16_t table[], int index, int partial255) {
1.212 + SkASSERT((unsigned)index < kTableSize);
1.213 + SkASSERT((unsigned)partial255 <= 255);
1.214 +
1.215 + SkFixed lower = table[index];
1.216 + SkFixed upper = (index == kTableSize - 1) ? SK_Fixed1 : table[index + 1];
1.217 +
1.218 + SkASSERT(lower < upper);
1.219 + SkASSERT(lower >= 0);
1.220 + SkASSERT(upper <= SK_Fixed1);
1.221 +
1.222 + partial255 += (partial255 >> 7);
1.223 + return lower + ((upper - lower) * partial255 >> 8);
1.224 +}
1.225 +#endif
1.226 +
1.227 +SkFixed SkFixedSinCos(SkFixed radians, SkFixed* cosValuePtr) {
1.228 + SkASSERT(SK_ARRAY_COUNT(gSkSinTable) == kTableSize);
1.229 +
1.230 +#ifdef BUILD_TABLE_AT_RUNTIME
1.231 + static bool gFirstTime = true;
1.232 + if (gFirstTime) {
1.233 + build_sintable(gSinTable);
1.234 + gFirstTime = false;
1.235 + }
1.236 +#endif
1.237 +
1.238 + // make radians positive
1.239 + SkFixed sinValue, cosValue;
1.240 + int32_t cosSign = 0;
1.241 + int32_t sinSign = SkExtractSign(radians);
1.242 + radians = SkApplySign(radians, sinSign);
1.243 + // scale it to 0...1023 ...
1.244 +
1.245 +#ifdef INTERP_SINTABLE
1.246 + radians = SkMulDiv(radians, 2 * kTableSize * 256, SK_FixedPI);
1.247 + int findex = radians & (kTableSize * 256 - 1);
1.248 + int index = findex >> 8;
1.249 + int partial = findex & 255;
1.250 + sinValue = interp_table(gSkSinTable, index, partial);
1.251 +
1.252 + findex = kTableSize * 256 - findex - 1;
1.253 + index = findex >> 8;
1.254 + partial = findex & 255;
1.255 + cosValue = interp_table(gSkSinTable, index, partial);
1.256 +
1.257 + int quad = ((unsigned)radians / (kTableSize * 256)) & 3;
1.258 +#else
1.259 + radians = SkMulDiv(radians, 2 * kTableSize, SK_FixedPI);
1.260 + int index = radians & (kTableSize - 1);
1.261 +
1.262 + if (index == 0) {
1.263 + sinValue = 0;
1.264 + cosValue = SK_Fixed1;
1.265 + } else {
1.266 + sinValue = gSkSinTable[index];
1.267 + cosValue = gSkSinTable[kTableSize - index];
1.268 + }
1.269 + int quad = ((unsigned)radians / kTableSize) & 3;
1.270 +#endif
1.271 +
1.272 + if (quad & 1) {
1.273 + SkTSwap<SkFixed>(sinValue, cosValue);
1.274 + }
1.275 + if (quad & 2) {
1.276 + sinSign = ~sinSign;
1.277 + }
1.278 + if (((quad - 1) & 2) == 0) {
1.279 + cosSign = ~cosSign;
1.280 + }
1.281 +
1.282 + // restore the sign for negative angles
1.283 + sinValue = SkApplySign(sinValue, sinSign);
1.284 + cosValue = SkApplySign(cosValue, cosSign);
1.285 +
1.286 +#ifdef SK_DEBUG
1.287 + if (1) {
1.288 + SkFixed sin2 = SkFixedMul(sinValue, sinValue);
1.289 + SkFixed cos2 = SkFixedMul(cosValue, cosValue);
1.290 + int diff = cos2 + sin2 - SK_Fixed1;
1.291 + SkASSERT(SkAbs32(diff) <= 7);
1.292 + }
1.293 +#endif
1.294 +
1.295 + if (cosValuePtr) {
1.296 + *cosValuePtr = cosValue;
1.297 + }
1.298 + return sinValue;
1.299 +}
