1
2 /*
3 * Copyright 2011 Google Inc.
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 "SkClampRange.h"
11
12 /*
13 * returns [0..count] for the number of steps (<= count) for which x0 <= edge
14 * given each step is followed by x0 += dx
15 */
chop(int64_t x0,SkFixed edge,int64_t x1,int64_t dx,int count)16 static int chop(int64_t x0, SkFixed edge, int64_t x1, int64_t dx, int count) {
17 SkASSERT(dx > 0);
18 SkASSERT(count >= 0);
19
20 if (x0 >= edge) {
21 return 0;
22 }
23 if (x1 <= edge) {
24 return count;
25 }
26 int64_t n = (edge - x0 + dx - 1) / dx;
27 SkASSERT(n >= 0);
28 SkASSERT(n <= count);
29 return (int)n;
30 }
31
overflows_fixed(int64_t x)32 static bool overflows_fixed(int64_t x) {
33 return x < -SK_FixedMax || x > SK_FixedMax;
34 }
35
initFor1(SkFixed fx)36 void SkClampRange::initFor1(SkFixed fx) {
37 fCount0 = fCount1 = fCount2 = 0;
38 if (fx <= 0) {
39 fCount0 = 1;
40 } else if (fx < 0xFFFF) {
41 fCount1 = 1;
42 fFx1 = fx;
43 } else {
44 fCount2 = 1;
45 }
46 }
47
init(SkFixed fx0,SkFixed dx0,int count,int v0,int v1)48 void SkClampRange::init(SkFixed fx0, SkFixed dx0, int count, int v0, int v1) {
49 SkASSERT(count > 0);
50
51 fV0 = v0;
52 fV1 = v1;
53 fOverflowed = false;
54
55 // special case 1 == count, as it is slightly common for skia
56 // and avoids us ever calling divide or 64bit multiply
57 if (1 == count) {
58 this->initFor1(fx0);
59 return;
60 }
61
62 int64_t fx = fx0;
63 int64_t dx = dx0;
64 // start with ex equal to the last computed value
65 int64_t ex = fx + (count - 1) * dx;
66 fOverflowed = overflows_fixed(ex);
67
68 if ((uint64_t)(fx | ex) <= 0xFFFF) {
69 fCount0 = fCount2 = 0;
70 fCount1 = count;
71 fFx1 = fx0;
72 return;
73 }
74 if (fx <= 0 && ex <= 0) {
75 fCount1 = fCount2 = 0;
76 fCount0 = count;
77 return;
78 }
79 if (fx >= 0xFFFF && ex >= 0xFFFF) {
80 fCount0 = fCount1 = 0;
81 fCount2 = count;
82 return;
83 }
84
85 int extraCount = 0;
86
87 // now make ex be 1 past the last computed value
88 ex += dx;
89 fOverflowed = overflows_fixed(ex);
90 // now check for over/under flow
91 if (fOverflowed) {
92 int originalCount = count;
93 int64_t ccount;
94 bool swap = dx < 0;
95 if (swap) {
96 dx = -dx;
97 fx = -fx;
98 }
99 ccount = (SK_FixedMax - fx + dx - 1) / dx;
100 if (swap) {
101 dx = -dx;
102 fx = -fx;
103 }
104 SkASSERT(ccount > 0 && ccount <= SK_FixedMax);
105
106 count = (int)ccount;
107 if (0 == count) {
108 this->initFor1(fx0);
109 if (dx > 0) {
110 fCount2 += originalCount - 1;
111 } else {
112 fCount0 += originalCount - 1;
113 }
114 return;
115 }
116 extraCount = originalCount - count;
117 ex = fx + dx * count;
118 }
119
120 bool doSwap = dx < 0;
121
122 if (doSwap) {
123 ex -= dx;
124 fx -= dx;
125 SkTSwap(fx, ex);
126 dx = -dx;
127 }
128
129
130 fCount0 = chop(fx, 0, ex, dx, count);
131 count -= fCount0;
132 fx += fCount0 * dx;
133 SkASSERT(fx >= 0);
134 SkASSERT(fCount0 == 0 || (fx - dx) < 0);
135 fCount1 = chop(fx, 0xFFFF, ex, dx, count);
136 count -= fCount1;
137 fCount2 = count;
138
139 #ifdef SK_DEBUG
140 fx += fCount1 * dx;
141 SkASSERT(fx <= ex);
142 if (fCount2 > 0) {
143 SkASSERT(fx >= 0xFFFF);
144 if (fCount1 > 0) {
145 SkASSERT(fx - dx < 0xFFFF);
146 }
147 }
148 #endif
149
150 if (doSwap) {
151 SkTSwap(fCount0, fCount2);
152 SkTSwap(fV0, fV1);
153 dx = -dx;
154 }
155
156 if (fCount1 > 0) {
157 fFx1 = fx0 + fCount0 * (int)dx;
158 }
159
160 if (dx > 0) {
161 fCount2 += extraCount;
162 } else {
163 fCount0 += extraCount;
164 }
165 }
166
167