1/*
2 * Copyright 2011 Google Inc.
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 "SkClampRange.h"
9#include "SkMath.h"
10
11static int SkCLZ64(uint64_t value) {
12    int count = 0;
13    if (value >> 32) {
14        value >>= 32;
15    } else {
16        count += 32;
17    }
18    return count + SkCLZ(SkToU32(value));
19}
20
21static bool sk_64_smul_check(int64_t a, int64_t b, int64_t* result) {
22    // Do it the slow way until we have some assembly.
23    int64_t ua = SkTAbs(a);
24    int64_t ub = SkTAbs(b);
25    int zeros = SkCLZ64(ua) + SkCLZ64(ub);
26    // this is a conservative check: it may return false when in fact it would not have overflowed.
27    // Hackers Delight uses 34 as its convervative check, but that is for 32x32 multiplies.
28    // Since we are looking at 64x64 muls, we add 32 to the check.
29    if (zeros < (32 + 34)) {
30        return false;
31    }
32    *result = a * b;
33    return true;
34}
35
36/*
37 *  returns [0..count] for the number of steps (<= count) for which x0 <= edge
38 *  given each step is followed by x0 += dx
39 */
40static int chop(int64_t x0, SkGradFixed edge, int64_t x1, int64_t dx, int count) {
41    SkASSERT(dx > 0);
42    SkASSERT(count >= 0);
43
44    if (x0 >= edge) {
45        return 0;
46    }
47    if (x1 <= edge) {
48        return count;
49    }
50    int64_t n = (edge - x0 + dx - 1) / dx;
51    SkASSERT(n >= 0);
52    SkASSERT(n <= count);
53    return (int)n;
54}
55
56void SkClampRange::initFor1(SkGradFixed fx) {
57    fCount0 = fCount1 = fCount2 = 0;
58    if (fx <= 0) {
59        fCount0 = 1;
60    } else if (fx < kFracMax_SkGradFixed) {
61        fCount1 = 1;
62        fFx1 = fx;
63    } else {
64        fCount2 = 1;
65    }
66}
67
68void SkClampRange::init(SkGradFixed fx0, SkGradFixed dx0, int count, int v0, int v1) {
69    SkASSERT(count > 0);
70
71    fV0 = v0;
72    fV1 = v1;
73
74    // special case 1 == count, as it is slightly common for skia
75    // and avoids us ever calling divide or 64bit multiply
76    if (1 == count) {
77        this->initFor1(fx0);
78        return;
79    }
80
81    int64_t fx = fx0;
82    int64_t dx = dx0;
83
84    // start with ex equal to the last computed value
85    int64_t count_times_dx;
86    if (!sk_64_smul_check(count - 1, dx, &count_times_dx)) {
87        // we can't represent the computed end in 32.32, so just draw something (first color)
88        fCount1 = fCount2 = 0;
89        fCount0 = count;
90        return;
91    }
92
93    int64_t ex = fx + (count - 1) * dx;
94
95    if ((uint64_t)(fx | ex) <= kFracMax_SkGradFixed) {
96        fCount0 = fCount2 = 0;
97        fCount1 = count;
98        fFx1 = fx0;
99        return;
100    }
101    if (fx <= 0 && ex <= 0) {
102        fCount1 = fCount2 = 0;
103        fCount0 = count;
104        return;
105    }
106    if (fx >= kFracMax_SkGradFixed && ex >= kFracMax_SkGradFixed) {
107        fCount0 = fCount1 = 0;
108        fCount2 = count;
109        return;
110    }
111
112    // now make ex be 1 past the last computed value
113    ex += dx;
114
115    bool doSwap = dx < 0;
116
117    if (doSwap) {
118        ex -= dx;
119        fx -= dx;
120        SkTSwap(fx, ex);
121        dx = -dx;
122    }
123
124
125    fCount0 = chop(fx, 0, ex, dx, count);
126    SkASSERT(fCount0 >= 0);
127    SkASSERT(fCount0 <= count);
128    count -= fCount0;
129    fx += fCount0 * dx;
130    SkASSERT(fx >= 0);
131    SkASSERT(fCount0 == 0 || (fx - dx) < 0);
132    fCount1 = chop(fx, kFracMax_SkGradFixed, ex, dx, count);
133    SkASSERT(fCount1 >= 0);
134    SkASSERT(fCount1 <= count);
135    count -= fCount1;
136    fCount2 = count;
137
138#ifdef SK_DEBUG
139    fx += fCount1 * dx;
140    SkASSERT(fx <= ex);
141    if (fCount2 > 0) {
142        SkASSERT(fx >= kFracMax_SkGradFixed);
143        if (fCount1 > 0) {
144            SkASSERT(fx - dx < kFracMax_SkGradFixed);
145        }
146    }
147#endif
148
149    if (doSwap) {
150        SkTSwap(fCount0, fCount2);
151        SkTSwap(fV0, fV1);
152        dx = -dx;
153    }
154
155    if (fCount1 > 0) {
156        fFx1 = fx0 + fCount0 * dx;
157    }
158}
159