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
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 a,int64_t b,int64_t * result)21 static 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 */
chop(int64_t x0,SkGradFixed edge,int64_t x1,int64_t dx,int count)40 static 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
initFor1(SkGradFixed fx)56 void 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
init(SkGradFixed fx0,SkGradFixed dx0,int count,int v0,int v1)68 void 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