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