1/*
2 * Copyright 2008 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 "include/core/SkShader.h"
9#include "include/private/SkTo.h"
10#include "src/core/SkBitmapProcState.h"
11#include "src/core/SkUtils.h"
12
13/*
14 * The decal_ functions require that
15 * 1. dx > 0
16 * 2. [fx, fx+dx, fx+2dx, fx+3dx, ... fx+(count-1)dx] are all <= maxX
17 *
18 * In addition, we use SkFractionalInt to keep more fractional precision than
19 * just SkFixed, so we will abort the decal_ call if dx is very small, since
20 * the decal_ function just operates on SkFixed. If that were changed, we could
21 * skip the very_small test here.
22 */
23static inline bool can_truncate_to_fixed_for_decal(SkFixed fx,
24 SkFixed dx,
25 int count, unsigned max) {
26 SkASSERT(count > 0);
27
28 // if decal_ kept SkFractionalInt precision, this would just be dx <= 0
29 // I just made up the 1/256. Just don't want to perceive accumulated error
30 // if we truncate frDx and lose its low bits.
31 if (dx <= SK_Fixed1 / 256) {
32 return false;
33 }
34
35 // Note: it seems the test should be (fx <= max && lastFx <= max); but
36 // historically it's been a strict inequality check, and changing produces
37 // unexpected diffs. Further investigation is needed.
38
39 // We cast to unsigned so we don't have to check for negative values, which
40 // will now appear as very large positive values, and thus fail our test!
41 if ((unsigned)SkFixedFloorToInt(fx) >= max) {
42 return false;
43 }
44
45 // Promote to 64bit (48.16) to avoid overflow.
46 const uint64_t lastFx = fx + sk_64_mul(dx, count - 1);
47
48 return SkTFitsIn<int32_t>(lastFx) && (unsigned)SkFixedFloorToInt(SkTo<int32_t>(lastFx)) < max;
49}
50
51// When not filtering, we store 32-bit y, 16-bit x, 16-bit x, 16-bit x, ...
52// When filtering we write out 32-bit encodings, pairing 14.4 x0 with 14-bit x1.
53
54// The clamp routines may try to fall into one of these unclamped decal fast-paths.
55// (Only clamp works in the right coordinate space to check for decal.)
56static void decal_nofilter_scale(uint32_t dst[], SkFixed fx, SkFixed dx, int count) {
57 // can_truncate_to_fixed_for_decal() checked only that stepping fx+=dx count-1
58 // times doesn't overflow fx, so we take unusual care not to step count times.
59 for (; count > 2; count -= 2) {
60 *dst++ = pack_two_shorts( (fx + 0) >> 16,
61 (fx + dx) >> 16);
62 fx += dx+dx;
63 }
64
65 SkASSERT(count <= 2);
66 switch (count) {
67 case 2: ((uint16_t*)dst)[1] = SkToU16((fx + dx) >> 16);
68 case 1: ((uint16_t*)dst)[0] = SkToU16((fx + 0) >> 16);
69 }
70}
71
72// A generic implementation for unfiltered scale+translate, templated on tiling method.
73template <unsigned (*tilex)(SkFixed, int), unsigned (*tiley)(SkFixed, int), bool tryDecal>
74static void nofilter_scale(const SkBitmapProcState& s,
75 uint32_t xy[], int count, int x, int y) {
76 SkASSERT(s.fInvMatrix.isScaleTranslate());
77
78 // Write out our 32-bit y, and get our intial fx.
79 SkFractionalInt fx;
80 {
81 const SkBitmapProcStateAutoMapper mapper(s, x, y);
82 *xy++ = tiley(mapper.fixedY(), s.fPixmap.height() - 1);
83 fx = mapper.fractionalIntX();
84 }
85
86 const unsigned maxX = s.fPixmap.width() - 1;
87 if (0 == maxX) {
88 // If width == 1, all the x-values must refer to that pixel, and must be zero.
89 memset(xy, 0, count * sizeof(uint16_t));
90 return;
91 }
92
93 const SkFractionalInt dx = s.fInvSxFractionalInt;
94
95 if (tryDecal) {
96 const SkFixed fixedFx = SkFractionalIntToFixed(fx);
97 const SkFixed fixedDx = SkFractionalIntToFixed(dx);
98
99 if (can_truncate_to_fixed_for_decal(fixedFx, fixedDx, count, maxX)) {
100 decal_nofilter_scale(xy, fixedFx, fixedDx, count);
101 return;
102 }
103 }
104
105 // Remember, each x-coordinate is 16-bit.
106 for (; count >= 2; count -= 2) {
107 *xy++ = pack_two_shorts(tilex(SkFractionalIntToFixed(fx ), maxX),
108 tilex(SkFractionalIntToFixed(fx + dx), maxX));
109 fx += dx+dx;
110 }
111
112 auto xx = (uint16_t*)xy;
113 while (count --> 0) {
114 *xx++ = tilex(SkFractionalIntToFixed(fx), maxX);
115 fx += dx;
116 }
117}
118
119template <unsigned (*tilex)(SkFixed, int), unsigned (*tiley)(SkFixed, int)>
120static void nofilter_affine(const SkBitmapProcState& s,
121 uint32_t xy[], int count, int x, int y) {
122 SkASSERT(!s.fInvMatrix.hasPerspective());
123
124 const SkBitmapProcStateAutoMapper mapper(s, x, y);
125
126 SkFractionalInt fx = mapper.fractionalIntX(),
127 fy = mapper.fractionalIntY(),
128 dx = s.fInvSxFractionalInt,
129 dy = s.fInvKyFractionalInt;
130 int maxX = s.fPixmap.width () - 1,
131 maxY = s.fPixmap.height() - 1;
132
133 while (count --> 0) {
134 *xy++ = (tiley(SkFractionalIntToFixed(fy), maxY) << 16)
135 | (tilex(SkFractionalIntToFixed(fx), maxX) );
136 fx += dx;
137 fy += dy;
138 }
139}
140
141// used when both tilex and tiley are clamp
142// Extract the high four fractional bits from fx, the lerp parameter when filtering.
143static unsigned extract_low_bits_clamp_clamp(SkFixed fx, int /*max*/) {
144 // If we're already scaled up to by max like clamp/decal,
145 // just grab the high four fractional bits.
146 return (fx >> 12) & 0xf;
147}
148
149//used when one of tilex and tiley is not clamp
150static unsigned extract_low_bits_general(SkFixed fx, int max) {
151 // In repeat or mirror fx is in [0,1], so scale up by max first.
152 // TODO: remove the +1 here and the -1 at the call sites...
153 return extract_low_bits_clamp_clamp((fx & 0xffff) * (max+1), max);
154}
155
156template <unsigned (*tile)(SkFixed, int), unsigned (*extract_low_bits)(SkFixed, int)>
157static uint32_t pack(SkFixed f, unsigned max, SkFixed one) {
158 uint32_t packed = tile(f, max); // low coordinate in high bits
159 packed = (packed << 4) | extract_low_bits(f, max); // (lerp weight _is_ coord fractional part)
160 packed = (packed << 14) | tile((f + one), max); // high coordinate in low bits
161 return packed;
162}
163
164template <unsigned (*tilex)(SkFixed, int), unsigned (*tiley)(SkFixed, int), unsigned (*extract_low_bits)(SkFixed, int), bool tryDecal>
165static void filter_scale(const SkBitmapProcState& s,
166 uint32_t xy[], int count, int x, int y) {
167 SkASSERT(s.fInvMatrix.isScaleTranslate());
168
169 const unsigned maxX = s.fPixmap.width() - 1;
170 const SkFractionalInt dx = s.fInvSxFractionalInt;
171 SkFractionalInt fx;
172 {
173 const SkBitmapProcStateAutoMapper mapper(s, x, y);
174 const unsigned maxY = s.fPixmap.height() - 1;
175 // compute our two Y values up front
176 *xy++ = pack<tiley, extract_low_bits>(mapper.fixedY(), maxY, s.fFilterOneY);
177 // now initialize fx
178 fx = mapper.fractionalIntX();
179 }
180
181 // For historical reasons we check both ends are < maxX rather than <= maxX.
182 // TODO: try changing this? See also can_truncate_to_fixed_for_decal().
183 if (tryDecal &&
184 (unsigned)SkFractionalIntToInt(fx ) < maxX &&
185 (unsigned)SkFractionalIntToInt(fx + dx*(count-1)) < maxX) {
186 while (count --> 0) {
187 SkFixed fixedFx = SkFractionalIntToFixed(fx);
188 SkASSERT((fixedFx >> (16 + 14)) == 0);
189 *xy++ = (fixedFx >> 12 << 14) | ((fixedFx >> 16) + 1);
190 fx += dx;
191 }
192 return;
193 }
194
195 while (count --> 0) {
196 *xy++ = pack<tilex, extract_low_bits>(SkFractionalIntToFixed(fx), maxX, s.fFilterOneX);
197 fx += dx;
198 }
199}
200
201template <unsigned (*tilex)(SkFixed, int), unsigned (*tiley)(SkFixed, int), unsigned (*extract_low_bits)(SkFixed, int)>
202static void filter_affine(const SkBitmapProcState& s,
203 uint32_t xy[], int count, int x, int y) {
204 SkASSERT(!s.fInvMatrix.hasPerspective());
205
206 const SkBitmapProcStateAutoMapper mapper(s, x, y);
207
208 SkFixed oneX = s.fFilterOneX,
209 oneY = s.fFilterOneY;
210
211 SkFractionalInt fx = mapper.fractionalIntX(),
212 fy = mapper.fractionalIntY(),
213 dx = s.fInvSxFractionalInt,
214 dy = s.fInvKyFractionalInt;
215 unsigned maxX = s.fPixmap.width () - 1,
216 maxY = s.fPixmap.height() - 1;
217 while (count --> 0) {
218 *xy++ = pack<tiley, extract_low_bits>(SkFractionalIntToFixed(fy), maxY, oneY);
219 *xy++ = pack<tilex, extract_low_bits>(SkFractionalIntToFixed(fx), maxX, oneX);
220
221 fy += dy;
222 fx += dx;
223 }
224}
225
226// Helper to ensure that when we shift down, we do it w/o sign-extension
227// so the caller doesn't have to manually mask off the top 16 bits.
228static inline unsigned SK_USHIFT16(unsigned x) {
229 return x >> 16;
230}
231
232static unsigned repeat(SkFixed fx, int max) {
233 SkASSERT(max < 65535);
234 return SK_USHIFT16((unsigned)(fx & 0xFFFF) * (max + 1));
235}
236static unsigned mirror(SkFixed fx, int max) {
237 SkASSERT(max < 65535);
238 // s is 0xFFFFFFFF if we're on an odd interval, or 0 if an even interval
239 SkFixed s = SkLeftShift(fx, 15) >> 31;
240
241 // This should be exactly the same as repeat(fx ^ s, max) from here on.
242 return SK_USHIFT16( ((fx ^ s) & 0xFFFF) * (max + 1) );
243}
244
245static unsigned clamp(SkFixed fx, int max) {
246 return SkTPin(fx >> 16, 0, max);
247}
248
249static const SkBitmapProcState::MatrixProc ClampX_ClampY_Procs[] = {
250 nofilter_scale <clamp, clamp, true>, filter_scale <clamp, clamp, extract_low_bits_clamp_clamp, true>,
251 nofilter_affine<clamp, clamp>, filter_affine<clamp, clamp, extract_low_bits_clamp_clamp>,
252};
253static const SkBitmapProcState::MatrixProc RepeatX_RepeatY_Procs[] = {
254 nofilter_scale <repeat, repeat, false>, filter_scale <repeat, repeat, extract_low_bits_general, false>,
255 nofilter_affine<repeat, repeat>, filter_affine<repeat, repeat, extract_low_bits_general>
256};
257static const SkBitmapProcState::MatrixProc MirrorX_MirrorY_Procs[] = {
258 nofilter_scale <mirror, mirror, false>, filter_scale <mirror, mirror, extract_low_bits_general, false>,
259 nofilter_affine<mirror, mirror>, filter_affine<mirror, mirror, extract_low_bits_general>,
260};
261
262
263///////////////////////////////////////////////////////////////////////////////
264// This next chunk has some specializations for unfiltered translate-only matrices.
265
266static inline U16CPU int_clamp(int x, int n) {
267 if (x < 0) { x = 0; }
268 if (x >= n) { x = n - 1; }
269 return x;
270}
271
272/* returns 0...(n-1) given any x (positive or negative).
273
274 As an example, if n (which is always positive) is 5...
275
276 x: -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8
277 returns: 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3
278 */
279static inline int sk_int_mod(int x, int n) {
280 SkASSERT(n > 0);
281 if ((unsigned)x >= (unsigned)n) {
282 if (x < 0) {
283 x = n + ~(~x % n);
284 } else {
285 x = x % n;
286 }
287 }
288 return x;
289}
290
291static inline U16CPU int_repeat(int x, int n) {
292 return sk_int_mod(x, n);
293}
294
295static inline U16CPU int_mirror(int x, int n) {
296 x = sk_int_mod(x, 2 * n);
297 if (x >= n) {
298 x = n + ~(x - n);
299 }
300 return x;
301}
302
303static void fill_sequential(uint16_t xptr[], int pos, int count) {
304 while (count --> 0) {
305 *xptr++ = pos++;
306 }
307}
308
309static void fill_backwards(uint16_t xptr[], int pos, int count) {
310 while (count --> 0) {
311 SkASSERT(pos >= 0);
312 *xptr++ = pos--;
313 }
314}
315
316template< U16CPU (tiley)(int x, int n) >
317static void clampx_nofilter_trans(const SkBitmapProcState& s,
318 uint32_t xy[], int count, int x, int y) {
319 SkASSERT(s.fInvMatrix.isTranslate());
320
321 const SkBitmapProcStateAutoMapper mapper(s, x, y);
322 *xy++ = tiley(mapper.intY(), s.fPixmap.height());
323 int xpos = mapper.intX();
324
325 const int width = s.fPixmap.width();
326 if (1 == width) {
327 // all of the following X values must be 0
328 memset(xy, 0, count * sizeof(uint16_t));
329 return;
330 }
331
332 uint16_t* xptr = reinterpret_cast<uint16_t*>(xy);
333 int n;
334
335 // fill before 0 as needed
336 if (xpos < 0) {
337 n = -xpos;
338 if (n > count) {
339 n = count;
340 }
341 memset(xptr, 0, n * sizeof(uint16_t));
342 count -= n;
343 if (0 == count) {
344 return;
345 }
346 xptr += n;
347 xpos = 0;
348 }
349
350 // fill in 0..width-1 if needed
351 if (xpos < width) {
352 n = width - xpos;
353 if (n > count) {
354 n = count;
355 }
356 fill_sequential(xptr, xpos, n);
357 count -= n;
358 if (0 == count) {
359 return;
360 }
361 xptr += n;
362 }
363
364 // fill the remaining with the max value
365 sk_memset16(xptr, width - 1, count);
366}
367
368template< U16CPU (tiley)(int x, int n) >
369static void repeatx_nofilter_trans(const SkBitmapProcState& s,
370 uint32_t xy[], int count, int x, int y) {
371 SkASSERT(s.fInvMatrix.isTranslate());
372
373 const SkBitmapProcStateAutoMapper mapper(s, x, y);
374 *xy++ = tiley(mapper.intY(), s.fPixmap.height());
375 int xpos = mapper.intX();
376
377 const int width = s.fPixmap.width();
378 if (1 == width) {
379 // all of the following X values must be 0
380 memset(xy, 0, count * sizeof(uint16_t));
381 return;
382 }
383
384 uint16_t* xptr = reinterpret_cast<uint16_t*>(xy);
385 int start = sk_int_mod(xpos, width);
386 int n = width - start;
387 if (n > count) {
388 n = count;
389 }
390 fill_sequential(xptr, start, n);
391 xptr += n;
392 count -= n;
393
394 while (count >= width) {
395 fill_sequential(xptr, 0, width);
396 xptr += width;
397 count -= width;
398 }
399
400 if (count > 0) {
401 fill_sequential(xptr, 0, count);
402 }
403}
404
405template< U16CPU (tiley)(int x, int n) >
406static void mirrorx_nofilter_trans(const SkBitmapProcState& s,
407 uint32_t xy[], int count, int x, int y) {
408 SkASSERT(s.fInvMatrix.isTranslate());
409
410 const SkBitmapProcStateAutoMapper mapper(s, x, y);
411 *xy++ = tiley(mapper.intY(), s.fPixmap.height());
412 int xpos = mapper.intX();
413
414 const int width = s.fPixmap.width();
415 if (1 == width) {
416 // all of the following X values must be 0
417 memset(xy, 0, count * sizeof(uint16_t));
418 return;
419 }
420
421 uint16_t* xptr = reinterpret_cast<uint16_t*>(xy);
422 // need to know our start, and our initial phase (forward or backward)
423 bool forward;
424 int n;
425 int start = sk_int_mod(xpos, 2 * width);
426 if (start >= width) {
427 start = width + ~(start - width);
428 forward = false;
429 n = start + 1; // [start .. 0]
430 } else {
431 forward = true;
432 n = width - start; // [start .. width)
433 }
434 if (n > count) {
435 n = count;
436 }
437 if (forward) {
438 fill_sequential(xptr, start, n);
439 } else {
440 fill_backwards(xptr, start, n);
441 }
442 forward = !forward;
443 xptr += n;
444 count -= n;
445
446 while (count >= width) {
447 if (forward) {
448 fill_sequential(xptr, 0, width);
449 } else {
450 fill_backwards(xptr, width - 1, width);
451 }
452 forward = !forward;
453 xptr += width;
454 count -= width;
455 }
456
457 if (count > 0) {
458 if (forward) {
459 fill_sequential(xptr, 0, count);
460 } else {
461 fill_backwards(xptr, width - 1, count);
462 }
463 }
464}
465
466
467///////////////////////////////////////////////////////////////////////////////
468// The main entry point to the file, choosing between everything above.
469
470SkBitmapProcState::MatrixProc SkBitmapProcState::chooseMatrixProc(bool translate_only_matrix) {
471 SkASSERT(!fInvMatrix.hasPerspective());
472 SkASSERT(fTileModeX != SkTileMode::kDecal);
473
474 if( fTileModeX == fTileModeY ) {
475 // Check for our special case translate methods when there is no scale/affine/perspective.
476 if (translate_only_matrix && kNone_SkFilterQuality == fFilterQuality) {
477 switch (fTileModeX) {
478 default: SkASSERT(false);
479 case SkTileMode::kClamp: return clampx_nofilter_trans<int_clamp>;
480 case SkTileMode::kRepeat: return repeatx_nofilter_trans<int_repeat>;
481 case SkTileMode::kMirror: return mirrorx_nofilter_trans<int_mirror>;
482 }
483 }
484
485 // The arrays are all [ nofilter, filter ].
486 int index = fFilterQuality > kNone_SkFilterQuality ? 1 : 0;
487 if (!fInvMatrix.isScaleTranslate()) {
488 index |= 2;
489 }
490
491 if (fTileModeX == SkTileMode::kClamp) {
492 // clamp gets special version of filterOne, working in non-normalized space (allowing decal)
493 fFilterOneX = SK_Fixed1;
494 fFilterOneY = SK_Fixed1;
495 return ClampX_ClampY_Procs[index];
496 }
497
498 // all remaining procs use this form for filterOne, putting them into normalized space.
499 fFilterOneX = SK_Fixed1 / fPixmap.width();
500 fFilterOneY = SK_Fixed1 / fPixmap.height();
501
502 if (fTileModeX == SkTileMode::kRepeat) {
503 return RepeatX_RepeatY_Procs[index];
504 }
505
506 return MirrorX_MirrorY_Procs[index];
507 }
508
509 SkASSERT(fTileModeX == fTileModeY);
510 return nullptr;
511}
512