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