1 /* 2 * Copyright 2008 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkMathPriv.h" 9 #include "SkFloatBits.h" 10 #include "SkFloatingPoint.h" 11 #include "SkScalar.h" 12 13 const uint32_t gIEEENotANumber = 0x7FFFFFFF; 14 const uint32_t gIEEEInfinity = 0x7F800000; 15 const uint32_t gIEEENegativeInfinity = 0xFF800000; 16 17 #define sub_shift(zeros, x, n) \ 18 zeros -= n; \ 19 x >>= n 20 21 int SkCLZ_portable(uint32_t x) { 22 if (x == 0) { 23 return 32; 24 } 25 26 int zeros = 31; 27 if (x & 0xFFFF0000) { 28 sub_shift(zeros, x, 16); 29 } 30 if (x & 0xFF00) { 31 sub_shift(zeros, x, 8); 32 } 33 if (x & 0xF0) { 34 sub_shift(zeros, x, 4); 35 } 36 if (x & 0xC) { 37 sub_shift(zeros, x, 2); 38 } 39 if (x & 0x2) { 40 sub_shift(zeros, x, 1); 41 } 42 43 return zeros; 44 } 45 46 SkFixed SkFixedMul_portable(SkFixed a, SkFixed b) { 47 #if defined(SkLONGLONG) 48 return static_cast<SkFixed>((int64_t)a * b >> 16); 49 #else 50 int sa = SkExtractSign(a); 51 int sb = SkExtractSign(b); 52 // now make them positive 53 a = SkApplySign(a, sa); 54 b = SkApplySign(b, sb); 55 56 uint32_t ah = a >> 16; 57 uint32_t al = a & 0xFFFF; 58 uint32_t bh = b >> 16; 59 uint32_t bl = b & 0xFFFF; 60 61 uint32_t R = ah * b + al * bh + (al * bl >> 16); 62 63 return SkApplySign(R, sa ^ sb); 64 #endif 65 } 66 67 /////////////////////////////////////////////////////////////////////////////// 68 69 #define DIVBITS_ITER(n) \ 70 case n: \ 71 if ((numer = (numer << 1) - denom) >= 0) \ 72 result |= 1 << (n - 1); else numer += denom 73 74 int32_t SkDivBits(int32_t numer, int32_t denom, int shift_bias) { 75 SkASSERT(denom != 0); 76 if (numer == 0) { 77 return 0; 78 } 79 80 // make numer and denom positive, and sign hold the resulting sign 81 int32_t sign = SkExtractSign(numer ^ denom); 82 numer = SkAbs32(numer); 83 denom = SkAbs32(denom); 84 85 int nbits = SkCLZ(numer) - 1; 86 int dbits = SkCLZ(denom) - 1; 87 int bits = shift_bias - nbits + dbits; 88 89 if (bits < 0) { // answer will underflow 90 return 0; 91 } 92 if (bits > 31) { // answer will overflow 93 return SkApplySign(SK_MaxS32, sign); 94 } 95 96 denom <<= dbits; 97 numer <<= nbits; 98 99 SkFixed result = 0; 100 101 // do the first one 102 if ((numer -= denom) >= 0) { 103 result = 1; 104 } else { 105 numer += denom; 106 } 107 108 // Now fall into our switch statement if there are more bits to compute 109 if (bits > 0) { 110 // make room for the rest of the answer bits 111 result <<= bits; 112 switch (bits) { 113 DIVBITS_ITER(31); DIVBITS_ITER(30); DIVBITS_ITER(29); 114 DIVBITS_ITER(28); DIVBITS_ITER(27); DIVBITS_ITER(26); 115 DIVBITS_ITER(25); DIVBITS_ITER(24); DIVBITS_ITER(23); 116 DIVBITS_ITER(22); DIVBITS_ITER(21); DIVBITS_ITER(20); 117 DIVBITS_ITER(19); DIVBITS_ITER(18); DIVBITS_ITER(17); 118 DIVBITS_ITER(16); DIVBITS_ITER(15); DIVBITS_ITER(14); 119 DIVBITS_ITER(13); DIVBITS_ITER(12); DIVBITS_ITER(11); 120 DIVBITS_ITER(10); DIVBITS_ITER( 9); DIVBITS_ITER( 8); 121 DIVBITS_ITER( 7); DIVBITS_ITER( 6); DIVBITS_ITER( 5); 122 DIVBITS_ITER( 4); DIVBITS_ITER( 3); DIVBITS_ITER( 2); 123 // we merge these last two together, makes GCC make better ARM 124 default: 125 DIVBITS_ITER( 1); 126 } 127 } 128 129 if (result < 0) { 130 result = SK_MaxS32; 131 } 132 return SkApplySign(result, sign); 133 } 134 135 /* www.worldserver.com/turk/computergraphics/FixedSqrt.pdf 136 */ 137 int32_t SkSqrtBits(int32_t x, int count) { 138 SkASSERT(x >= 0 && count > 0 && (unsigned)count <= 30); 139 140 uint32_t root = 0; 141 uint32_t remHi = 0; 142 uint32_t remLo = x; 143 144 do { 145 root <<= 1; 146 147 remHi = (remHi<<2) | (remLo>>30); 148 remLo <<= 2; 149 150 uint32_t testDiv = (root << 1) + 1; 151 if (remHi >= testDiv) { 152 remHi -= testDiv; 153 root++; 154 } 155 } while (--count >= 0); 156 157 return root; 158 } 159 160 /////////////////////////////////////////////////////////////////////////////// 161 162 float SkScalarSinCos(float radians, float* cosValue) { 163 float sinValue = sk_float_sin(radians); 164 165 if (cosValue) { 166 *cosValue = sk_float_cos(radians); 167 if (SkScalarNearlyZero(*cosValue)) { 168 *cosValue = 0; 169 } 170 } 171 172 if (SkScalarNearlyZero(sinValue)) { 173 sinValue = 0; 174 } 175 return sinValue; 176 } 177 178 #define INTERP_SINTABLE 179 #define BUILD_TABLE_AT_RUNTIMEx 180 181 #define kTableSize 256 182 183 #ifdef BUILD_TABLE_AT_RUNTIME 184 static uint16_t gSkSinTable[kTableSize]; 185 186 static void build_sintable(uint16_t table[]) { 187 for (int i = 0; i < kTableSize; i++) { 188 double rad = i * 3.141592653589793 / (2*kTableSize); 189 double val = sin(rad); 190 int ival = (int)(val * SK_Fixed1); 191 table[i] = SkToU16(ival); 192 } 193 } 194 #else 195 #include "SkSinTable.h" 196 #endif 197 198 #define SK_Fract1024SizeOver2PI 0x28BE60 /* floatToFract(1024 / 2PI) */ 199 200 #ifdef INTERP_SINTABLE 201 static SkFixed interp_table(const uint16_t table[], int index, int partial255) { 202 SkASSERT((unsigned)index < kTableSize); 203 SkASSERT((unsigned)partial255 <= 255); 204 205 SkFixed lower = table[index]; 206 SkFixed upper = (index == kTableSize - 1) ? SK_Fixed1 : table[index + 1]; 207 208 SkASSERT(lower < upper); 209 SkASSERT(lower >= 0); 210 SkASSERT(upper <= SK_Fixed1); 211 212 partial255 += (partial255 >> 7); 213 return lower + ((upper - lower) * partial255 >> 8); 214 } 215 #endif 216 217 SkFixed SkFixedSinCos(SkFixed radians, SkFixed* cosValuePtr) { 218 SkASSERT(SK_ARRAY_COUNT(gSkSinTable) == kTableSize); 219 220 #ifdef BUILD_TABLE_AT_RUNTIME 221 static bool gFirstTime = true; 222 if (gFirstTime) { 223 build_sintable(gSinTable); 224 gFirstTime = false; 225 } 226 #endif 227 228 // make radians positive 229 SkFixed sinValue, cosValue; 230 int32_t cosSign = 0; 231 int32_t sinSign = SkExtractSign(radians); 232 radians = SkApplySign(radians, sinSign); 233 // scale it to 0...1023 ... 234 235 #ifdef INTERP_SINTABLE 236 radians = SkMulDiv(radians, 2 * kTableSize * 256, SK_FixedPI); 237 int findex = radians & (kTableSize * 256 - 1); 238 int index = findex >> 8; 239 int partial = findex & 255; 240 sinValue = interp_table(gSkSinTable, index, partial); 241 242 findex = kTableSize * 256 - findex - 1; 243 index = findex >> 8; 244 partial = findex & 255; 245 cosValue = interp_table(gSkSinTable, index, partial); 246 247 int quad = ((unsigned)radians / (kTableSize * 256)) & 3; 248 #else 249 radians = SkMulDiv(radians, 2 * kTableSize, SK_FixedPI); 250 int index = radians & (kTableSize - 1); 251 252 if (index == 0) { 253 sinValue = 0; 254 cosValue = SK_Fixed1; 255 } else { 256 sinValue = gSkSinTable[index]; 257 cosValue = gSkSinTable[kTableSize - index]; 258 } 259 int quad = ((unsigned)radians / kTableSize) & 3; 260 #endif 261 262 if (quad & 1) { 263 SkTSwap<SkFixed>(sinValue, cosValue); 264 } 265 if (quad & 2) { 266 sinSign = ~sinSign; 267 } 268 if (((quad - 1) & 2) == 0) { 269 cosSign = ~cosSign; 270 } 271 272 // restore the sign for negative angles 273 sinValue = SkApplySign(sinValue, sinSign); 274 cosValue = SkApplySign(cosValue, cosSign); 275 276 #ifdef SK_DEBUG 277 if (1) { 278 SkFixed sin2 = SkFixedMul(sinValue, sinValue); 279 SkFixed cos2 = SkFixedMul(cosValue, cosValue); 280 int diff = cos2 + sin2 - SK_Fixed1; 281 SkASSERT(SkAbs32(diff) <= 7); 282 } 283 #endif 284 285 if (cosValuePtr) { 286 *cosValuePtr = cosValue; 287 } 288 return sinValue; 289 } 290
