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
24int 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
38void 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
56int32_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
75void 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
93void 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
106int 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
123void Sk64::negate()
124{
125    fHi = -fHi - Sk32ToBool(fLo);
126    fLo = 0 - fLo;
127}
128
129void Sk64::abs()
130{
131    if (fHi < 0)
132    {
133        fHi = -fHi - Sk32ToBool(fLo);
134        fLo = 0 - fLo;
135    }
136}
137
138////////////////////////////////////////////////////////////////
139
140static 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
147SkBool Sk64::isFixed() const
148{
149    Sk64 tmp = *this;
150    tmp.roundRight(16);
151    return tmp.is32();
152}
153
154SkFract Sk64::getFract() const
155{
156    Sk64 tmp = *this;
157    tmp.roundRight(30);
158    return tmp.get32();
159}
160
161void Sk64::sub(const Sk64& a)
162{
163    fHi = fHi - a.fHi - (fLo < a.fLo);
164    fLo = fLo - a.fLo;
165}
166
167void Sk64::rsub(const Sk64& a)
168{
169    fHi = a.fHi - fHi - (a.fLo < fLo);
170    fLo = a.fLo - fLo;
171}
172
173void 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
201void 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
284int32_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
311    SkLONGLONG Sk64::getLongLong() const
312    {
313        SkLONGLONG value = fHi;
314        value <<= 32;
315        return value | fLo;
316    }
317#endif
318
319SkFixed 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