1 /* libs/corecg/Sk64.cpp
2 **
3 ** Copyright 2006, The Android Open Source Project
4 **
5 ** Licensed under the Apache License, Version 2.0 (the "License");
6 ** you may not use this file except in compliance with the License.
7 ** You may obtain a copy of the License at
8 **
9 ** http://www.apache.org/licenses/LICENSE-2.0
10 **
11 ** Unless required by applicable law or agreed to in writing, software
12 ** distributed under the License is distributed on an "AS IS" BASIS,
13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 ** See the License for the specific language governing permissions and
15 ** limitations under the License.
16 */
17
18 #include "Sk64.h"
19
20 #define shift_left(hi, lo) \
21 hi = (hi << 1) | (lo >> 31); \
22 lo <<= 1
23
24 #define shift_left_bits(hi, lo, bits) \
25 SkASSERT((unsigned)(bits) < 31); \
26 hi = (hi << (bits)) | (lo >> (32 - (bits))); \
27 lo <<= (bits)
28
29 //////////////////////////////////////////////////////////////////////
30
getClzAbs() const31 int Sk64::getClzAbs() const
32 {
33 int32_t hi = fHi;
34 uint32_t lo = fLo;
35
36 // get abs
37 if (hi < 0)
38 {
39 hi = -hi - Sk32ToBool(lo);
40 lo = 0 - lo;
41 }
42 return hi ? SkCLZ(hi) : SkCLZ(lo) + 32;
43 }
44
shiftLeft(unsigned bits)45 void Sk64::shiftLeft(unsigned bits)
46 {
47 SkASSERT(bits <= 63);
48 if (bits == 0)
49 return;
50
51 if (bits >= 32)
52 {
53 fHi = fLo << (bits - 32);
54 fLo = 0;
55 }
56 else
57 {
58 fHi = (fHi << bits) | (fLo >> (32 - bits));
59 fLo <<= bits;
60 }
61 }
62
getShiftRight(unsigned bits) const63 int32_t Sk64::getShiftRight(unsigned bits) const
64 {
65 SkASSERT(bits <= 63);
66
67 if (bits == 0)
68 return fLo;
69
70 if (bits >= 32)
71 return fHi >> (bits - 32);
72 else
73 {
74 #ifdef SK_DEBUG
75 int32_t tmp = fHi >> bits;
76 SkASSERT(tmp == 0 || tmp == -1);
77 #endif
78 return (fHi << (32 - bits)) | (fLo >> bits);
79 }
80 }
81
shiftRight(unsigned bits)82 void Sk64::shiftRight(unsigned bits)
83 {
84 SkASSERT(bits <= 63);
85 if (bits == 0)
86 return;
87
88 if (bits >= 32)
89 {
90 fLo = fHi >> (bits - 32);
91 fHi >>= 31;
92 }
93 else
94 {
95 fLo = (fHi << (32 - bits)) | (fLo >> bits);
96 fHi >>= bits;
97 }
98 }
99
roundRight(unsigned bits)100 void Sk64::roundRight(unsigned bits)
101 {
102 SkASSERT(bits <= 63);
103 if (bits)
104 {
105 Sk64 one;
106 one.set(1);
107 one.shiftLeft(bits - 1);
108 this->add(one);
109 this->shiftRight(bits);
110 }
111 }
112
shiftToMake32() const113 int Sk64::shiftToMake32() const
114 {
115 int32_t hi = fHi;
116 uint32_t lo = fLo;
117
118 if (hi < 0) // make it positive
119 {
120 hi = -hi - Sk32ToBool(lo);
121 lo = 0 - lo;
122 }
123
124 if (hi == 0)
125 return lo >> 31;
126 else
127 return 33 - SkCLZ(hi);
128 }
129
negate()130 void Sk64::negate()
131 {
132 fHi = -fHi - Sk32ToBool(fLo);
133 fLo = 0 - fLo;
134 }
135
abs()136 void Sk64::abs()
137 {
138 if (fHi < 0)
139 {
140 fHi = -fHi - Sk32ToBool(fLo);
141 fLo = 0 - fLo;
142 }
143 }
144
145 ////////////////////////////////////////////////////////////////
146
round_right_16(int32_t hi,uint32_t lo)147 static inline int32_t round_right_16(int32_t hi, uint32_t lo)
148 {
149 uint32_t sum = lo + (1 << 15);
150 hi += (sum < lo);
151 return (hi << 16) | (sum >> 16);
152 }
153
isFixed() const154 SkBool Sk64::isFixed() const
155 {
156 Sk64 tmp = *this;
157 tmp.roundRight(16);
158 return tmp.is32();
159 }
160
getFract() const161 SkFract Sk64::getFract() const
162 {
163 Sk64 tmp = *this;
164 tmp.roundRight(30);
165 return tmp.get32();
166 }
167
sub(const Sk64 & a)168 void Sk64::sub(const Sk64& a)
169 {
170 fHi = fHi - a.fHi - (fLo < a.fLo);
171 fLo = fLo - a.fLo;
172 }
173
rsub(const Sk64 & a)174 void Sk64::rsub(const Sk64& a)
175 {
176 fHi = a.fHi - fHi - (a.fLo < fLo);
177 fLo = a.fLo - fLo;
178 }
179
setMul(int32_t a,int32_t b)180 void Sk64::setMul(int32_t a, int32_t b)
181 {
182 int sa = a >> 31;
183 int sb = b >> 31;
184 // now make them positive
185 a = (a ^ sa) - sa;
186 b = (b ^ sb) - sb;
187
188 uint32_t ah = a >> 16;
189 uint32_t al = a & 0xFFFF;
190 uint32_t bh = b >> 16;
191 uint32_t bl = b & 0xFFFF;
192
193 uint32_t A = ah * bh;
194 uint32_t B = ah * bl + al * bh;
195 uint32_t C = al * bl;
196
197 /* [ A ]
198 [ B ]
199 [ C ]
200 */
201 fLo = C + (B << 16);
202 fHi = A + (B >>16) + (fLo < C);
203
204 if (sa != sb)
205 this->negate();
206 }
207
div(int32_t denom,DivOptions option)208 void Sk64::div(int32_t denom, DivOptions option)
209 {
210 SkASSERT(denom);
211
212 int32_t hi = fHi;
213 uint32_t lo = fLo;
214 int sign = denom ^ hi;
215
216 denom = SkAbs32(denom);
217 if (hi < 0)
218 {
219 hi = -hi - Sk32ToBool(lo);
220 lo = 0 - lo;
221 }
222
223 if (option == kRound_DivOption) // add denom/2
224 {
225 uint32_t newLo = lo + (denom >> 1);
226 hi += (newLo < lo);
227 lo = newLo;
228 }
229
230 if (hi == 0) // fast-case
231 {
232 if (lo < (uint32_t)denom)
233 this->set(0, 0);
234 else
235 {
236 this->set(0, lo / denom);
237 if (sign < 0)
238 this->negate();
239 }
240 return;
241 }
242
243 int bits;
244
245 {
246 int dbits = SkCLZ(denom);
247 int nbits = SkCLZ(hi);
248
249 bits = 32 + dbits - nbits;
250 SkASSERT(bits <= 63);
251 if (bits <= 0)
252 {
253 this->set(0, 0);
254 return;
255 }
256 denom <<= (dbits - 1);
257 shift_left_bits(hi, lo, nbits - 1);
258 }
259
260 int32_t rhi = 0;
261 uint32_t rlo = 0;
262
263 do {
264 shift_left(rhi, rlo);
265 #ifdef SK_CPU_HAS_CONDITIONAL_INSTR
266 if ((uint32_t)denom <= (uint32_t)hi)
267 {
268 hi -= denom;
269 rlo |= 1;
270 }
271 #else
272 int32_t diff = (denom - hi - 1) >> 31;
273 hi -= denom & diff;
274 rlo -= diff;
275 #endif
276 shift_left(hi, lo);
277 } while (--bits >= 0);
278 SkASSERT(rhi >= 0);
279
280 fHi = rhi;
281 fLo = rlo;
282 if (sign < 0)
283 this->negate();
284 }
285
286 #define shift_left_2(a, b, c) \
287 a = (a << 2) | (b >> 30); \
288 b = (b << 2) | (c >> 30); \
289 c <<= 2
290
getSqrt() const291 int32_t Sk64::getSqrt() const
292 {
293 SkASSERT(!this->isNeg());
294
295 uint32_t hi = fHi;
296 uint32_t lo = fLo;
297 uint32_t sqr = 0;
298 uint32_t root = 0;
299 int count = 31;
300
301 do {
302 root <<= 1;
303 shift_left_2(sqr, hi, lo);
304
305 uint32_t testDiv = (root << 1) + 1;
306 if (sqr >= testDiv)
307 {
308 sqr -= testDiv;
309 root++;
310 }
311 } while (--count >= 0);
312 SkASSERT((int32_t)root >= 0);
313
314 return root;
315 }
316
317 #ifdef SkLONGLONG
getLongLong() const318 SkLONGLONG Sk64::getLongLong() const
319 {
320 SkLONGLONG value = fHi;
321 value <<= 32;
322 return value | fLo;
323 }
324 #endif
325
getFixedDiv(const Sk64 & denom) const326 SkFixed Sk64::getFixedDiv(const Sk64& denom) const
327 {
328 Sk64 N = *this;
329 Sk64 D = denom;
330 int32_t sign = SkExtractSign(N.fHi ^ D.fHi);
331 SkFixed result;
332
333 N.abs();
334 D.abs();
335
336 // need to knock D down to just 31 bits
337 // either by rounding it to the right, or shifting N to the left
338 // then we can just call 64/32 div
339
340 int nclz = N.fHi ? SkCLZ(N.fHi) : 32;
341 int dclz = D.fHi ? SkCLZ(D.fHi) : (33 - (D.fLo >> 31));
342
343 int shiftN = nclz - 1;
344 SkASSERT(shiftN >= 0);
345 int shiftD = 33 - dclz;
346 SkASSERT(shiftD >= 0);
347
348 if (shiftD + shiftN < 16)
349 shiftD = 16 - shiftN;
350 else
351 shiftN = 16 - shiftD;
352
353 D.roundRight(shiftD);
354 if (D.isZero())
355 result = SK_MaxS32;
356 else
357 {
358 if (shiftN >= 0)
359 N.shiftLeft(shiftN);
360 else
361 N.roundRight(-shiftN);
362 N.div(D.get32(), Sk64::kTrunc_DivOption);
363 if (N.is32())
364 result = N.get32();
365 else
366 result = SK_MaxS32;
367 }
368 return SkApplySign(result, sign);
369 }
370
371