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
SkCLZ_portable(uint32_t x)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
SkFixedMul_portable(SkFixed a,SkFixed b)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
SkDivBits(int32_t numer,int32_t denom,int shift_bias)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 */
SkSqrtBits(int32_t x,int count)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
SkScalarSinCos(float radians,float * cosValue)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
build_sintable(uint16_t table[])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
interp_table(const uint16_t table[],int index,int partial255)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
SkFixedSinCos(SkFixed radians,SkFixed * cosValuePtr)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