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