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
SkCLZ64(uint64_t value)11 static 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
sk_64_smul_check(int64_t count,int64_t dx,int64_t * result)21 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 if (dx == std::numeric_limits<int64_t>::min()) {
24 return false; // SkTAbs overflow
25 }
26
27 SkASSERT(count >= 0);
28 uint64_t ucount = static_cast<uint64_t>(count);
29 uint64_t udx = static_cast<uint64_t>(SkTAbs(dx));
30 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 if (zeros < (32 + 34)) {
35 return false;
36 }
37 *result = count * dx;
38 return true;
39 }
40
sk_64_sadd_check(int64_t a,int64_t b,int64_t * result)41 static bool sk_64_sadd_check(int64_t a, int64_t b, int64_t* result) {
42 if (a > 0) {
43 if (b > std::numeric_limits<int64_t>::max() - a) {
44 return false;
45 }
46 } else {
47 if (b < std::numeric_limits<int64_t>::min() - a) {
48 return false;
49 }
50 }
51
52 *result = a + b;
53 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 */
chop(int64_t x0,SkGradFixed edge,int64_t x1,int64_t dx,int count)61 static int chop(int64_t x0, SkGradFixed edge, int64_t x1, int64_t dx, int count) {
62 SkASSERT(dx > 0);
63 SkASSERT(count >= 0);
64
65 if (x0 >= edge) {
66 return 0;
67 }
68 if (x1 <= edge) {
69 return count;
70 }
71 int64_t n = (edge - x0 + dx - 1) / dx;
72 SkASSERT(n >= 0);
73 SkASSERT(n <= count);
74 return (int)n;
75 }
76
initFor1(SkGradFixed fx)77 void SkClampRange::initFor1(SkGradFixed fx) {
78 fCount0 = fCount1 = fCount2 = 0;
79 if (fx <= 0) {
80 fCount0 = 1;
81 } else if (fx < kFracMax_SkGradFixed) {
82 fCount1 = 1;
83 fFx1 = fx;
84 } else {
85 fCount2 = 1;
86 }
87 }
88
init(SkGradFixed fx0,SkGradFixed dx0,int count,int v0,int v1)89 void SkClampRange::init(SkGradFixed fx0, SkGradFixed dx0, int count, int v0, int v1) {
90 SkASSERT(count > 0);
91
92 fV0 = v0;
93 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 if (1 == count) {
98 this->initFor1(fx0);
99 return;
100 }
101
102 int64_t fx = fx0;
103 int64_t dx = dx0;
104
105 // start with ex equal to the last computed value
106 int64_t count_times_dx, ex;
107 if (!sk_64_smul_check(count - 1, dx, &count_times_dx) ||
108 !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 fCount1 = fCount2 = 0;
111 fCount0 = count;
112 return;
113 }
114
115 if ((uint64_t)(fx | ex) <= kFracMax_SkGradFixed) {
116 fCount0 = fCount2 = 0;
117 fCount1 = count;
118 fFx1 = fx0;
119 return;
120 }
121 if (fx <= 0 && ex <= 0) {
122 fCount1 = fCount2 = 0;
123 fCount0 = count;
124 return;
125 }
126 if (fx >= kFracMax_SkGradFixed && ex >= kFracMax_SkGradFixed) {
127 fCount0 = fCount1 = 0;
128 fCount2 = count;
129 return;
130 }
131
132 // now make ex be 1 past the last computed value
133 ex += dx;
134
135 bool doSwap = dx < 0;
136
137 if (doSwap) {
138 ex -= dx;
139 fx -= dx;
140 SkTSwap(fx, ex);
141 dx = -dx;
142 }
143
144
145 fCount0 = chop(fx, 0, ex, dx, count);
146 SkASSERT(fCount0 >= 0);
147 SkASSERT(fCount0 <= count);
148 count -= fCount0;
149 fx += fCount0 * dx;
150 SkASSERT(fx >= 0);
151 SkASSERT(fCount0 == 0 || (fx - dx) < 0);
152 fCount1 = chop(fx, kFracMax_SkGradFixed, ex, dx, count);
153 SkASSERT(fCount1 >= 0);
154 SkASSERT(fCount1 <= count);
155 count -= fCount1;
156 fCount2 = count;
157
158 #ifdef SK_DEBUG
159 fx += fCount1 * dx;
160 SkASSERT(fx <= ex);
161 if (fCount2 > 0) {
162 SkASSERT(fx >= kFracMax_SkGradFixed);
163 if (fCount1 > 0) {
164 SkASSERT(fx - dx < kFracMax_SkGradFixed);
165 }
166 }
167 #endif
168
169 if (doSwap) {
170 SkTSwap(fCount0, fCount2);
171 SkTSwap(fV0, fV1);
172 dx = -dx;
173 }
174
175 if (fCount1 > 0) {
176 fFx1 = fx0 + fCount0 * dx;
177 }
178 }
179