The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkMath.cpp

gfx/skia/trunk/src/core/SkMath.cpp

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial