SkLinearBitmapPipeline_tile.h revision fc6c37b981daeece7474ce61070c707c37eefa62
1/* 2 * Copyright 2016 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#ifndef SkLinearBitmapPipeline_tile_DEFINED 9#define SkLinearBitmapPipeline_tile_DEFINED 10 11#include "SkLinearBitmapPipeline_core.h" 12#include "SkPM4f.h" 13#include <algorithm> 14#include <cmath> 15#include <limits> 16 17namespace { 18class XClampStrategy { 19public: 20 XClampStrategy(int32_t max) 21 : fXsMax{SkScalar(max - 0.5f)} 22 , fXMax{SkScalar(max)} { } 23 24 void tileXPoints(Sk4s* xs) { 25 *xs = Sk4s::Min(Sk4s::Max(*xs, 0.0f), fXsMax); 26 SkASSERT(0 <= (*xs)[0] && (*xs)[0] < fXMax); 27 SkASSERT(0 <= (*xs)[1] && (*xs)[1] < fXMax); 28 SkASSERT(0 <= (*xs)[2] && (*xs)[2] < fXMax); 29 SkASSERT(0 <= (*xs)[3] && (*xs)[3] < fXMax); 30 } 31 32 template<typename Next> 33 bool maybeProcessSpan(Span originalSpan, Next* next) { 34 SkASSERT(!originalSpan.isEmpty()); 35 SkPoint start; SkScalar length; int count; 36 std::tie(start, length, count) = originalSpan; 37 SkScalar x = X(start); 38 SkScalar y = Y(start); 39 Span span{{x, y}, length, count}; 40 41 if (span.completelyWithin(0.0f, fXMax)) { 42 next->pointSpan(span); 43 return true; 44 } 45 if (1 == count || 0.0f == length) { 46 return false; 47 } 48 49 SkScalar dx = length / (count - 1); 50 51 // A B C 52 // +-------+-------+-------++-------+-------+-------+ +-------+-------++------ 53 // | *---*|---*---|*---*--||-*---*-|---*---|*---...| |--*---*|---*---||*---*.... 54 // | | | || | | | ... | | || 55 // | | | || | | | | | || 56 // +-------+-------+-------++-------+-------+-------+ +-------+-------++------ 57 // ^ ^ 58 // | xMin xMax-1 | xMax 59 // 60 // *---*---*---... - track of samples. * = sample 61 // 62 // +-+ || 63 // | | - pixels in source space. || - tile border. 64 // +-+ || 65 // 66 // The length from A to B is the length in source space or 4 * dx or (count - 1) * dx 67 // where dx is the distance between samples. There are 5 destination pixels 68 // corresponding to 5 samples specified in the A, B span. The distance from A to the next 69 // span starting at C is 5 * dx, so count * dx. 70 // Remember, count is the number of pixels needed for the destination and the number of 71 // samples. 72 // Overall Strategy: 73 // * Under - for portions of the span < xMin, take the color at pixel {xMin, y} and use it 74 // to fill in the 5 pixel sampled from A to B. 75 // * Middle - for the portion of the span between xMin and xMax sample normally. 76 // * Over - for the portion of the span > xMax, take the color at pixel {xMax-1, y} and 77 // use it to fill in the rest of the destination pixels. 78 if (dx >= 0) { 79 Span leftClamped = span.breakAt(0.0f, dx); 80 if (!leftClamped.isEmpty()) { 81 leftClamped.clampToSinglePixel({0.0f, y}); 82 next->pointSpan(leftClamped); 83 } 84 Span center = span.breakAt(fXMax, dx); 85 if (!center.isEmpty()) { 86 next->pointSpan(center); 87 } 88 if (!span.isEmpty()) { 89 span.clampToSinglePixel({fXMax - 1, y}); 90 next->pointSpan(span); 91 } 92 } else { 93 Span rightClamped = span.breakAt(fXMax, dx); 94 if (!rightClamped.isEmpty()) { 95 rightClamped.clampToSinglePixel({fXMax - 1, y}); 96 next->pointSpan(rightClamped); 97 } 98 Span center = span.breakAt(0.0f, dx); 99 if (!center.isEmpty()) { 100 next->pointSpan(center); 101 } 102 if (!span.isEmpty()) { 103 span.clampToSinglePixel({0.0f, y}); 104 next->pointSpan(span); 105 } 106 } 107 return true; 108 } 109 110private: 111 const Sk4s fXsMax; 112 const SkScalar fXMax; 113}; 114 115class YClampStrategy { 116public: 117 YClampStrategy(int32_t max) 118 : fYMax{SkScalar(max) - 0.5f} 119 , fYsMax{SkScalar(max) - 0.5f} { } 120 121 void tileYPoints(Sk4s* ys) { 122 *ys = Sk4s::Min(Sk4s::Max(*ys, 0.0f), fYsMax); 123 SkASSERT(0 <= (*ys)[0] && (*ys)[0] <= fYMax); 124 SkASSERT(0 <= (*ys)[1] && (*ys)[1] <= fYMax); 125 SkASSERT(0 <= (*ys)[2] && (*ys)[2] <= fYMax); 126 SkASSERT(0 <= (*ys)[3] && (*ys)[3] <= fYMax); 127 } 128 129 SkScalar tileY(SkScalar y) { 130 return std::min(std::max<SkScalar>(0.0f, y), fYMax); 131 } 132 133private: 134 const SkScalar fYMax; 135 const Sk4s fYsMax; 136}; 137 138SkScalar tile_mod(SkScalar x, SkScalar base) { 139 return x - SkScalarFloorToScalar(x / base) * base; 140} 141 142class XRepeatStrategy { 143public: 144 XRepeatStrategy(int32_t max) 145 : fXMax{SkScalar(max)} 146 , fXsMax{SkScalar(max)} 147 , fXsCap{SkScalar(nextafterf(SkScalar(max), 0.0f))} 148 , fXsInvMax{1.0f / SkScalar(max)} { } 149 150 void tileXPoints(Sk4s* xs) { 151 Sk4s divX = *xs * fXsInvMax; 152 Sk4s modX = *xs - divX.floor() * fXsMax; 153 *xs = Sk4s::Min(fXsCap, modX); 154 SkASSERT(0 <= (*xs)[0] && (*xs)[0] < fXMax); 155 SkASSERT(0 <= (*xs)[1] && (*xs)[1] < fXMax); 156 SkASSERT(0 <= (*xs)[2] && (*xs)[2] < fXMax); 157 SkASSERT(0 <= (*xs)[3] && (*xs)[3] < fXMax); 158 } 159 160 template<typename Next> 161 bool maybeProcessSpan(Span originalSpan, Next* next) { 162 SkASSERT(!originalSpan.isEmpty()); 163 SkPoint start; SkScalar length; int count; 164 std::tie(start, length, count) = originalSpan; 165 // Make x and y in range on the tile. 166 SkScalar x = tile_mod(X(start), fXMax); 167 SkScalar y = Y(start); 168 SkScalar dx = length / (count - 1); 169 170 // No need trying to go fast because the steps are larger than a tile or there is one point. 171 if (SkScalarAbs(dx) >= fXMax || count <= 1) { 172 return false; 173 } 174 175 // A B C D Z 176 // +-------+-------+-------++-------+-------+-------++ +-------+-------++------ 177 // | | *---|*---*--||-*---*-|---*---|*---*--|| |--*---*| || 178 // | | | || | | || ... | | || 179 // | | | || | | || | | || 180 // +-------+-------+-------++-------+-------+-------++ +-------+-------++------ 181 // ^^ ^^ ^^ 182 // xMax || xMin xMax || xMin xMax || xMin 183 // 184 // *---*---*---... - track of samples. * = sample 185 // 186 // +-+ || 187 // | | - pixels in source space. || - tile border. 188 // +-+ || 189 // 190 // 191 // The given span starts at A and continues on through several tiles to sample point Z. 192 // The idea is to break this into several spans one on each tile the entire span 193 // intersects. The A to B span only covers a partial tile and has a count of 3 and the 194 // distance from A to B is (count - 1) * dx or 2 * dx. The distance from A to the start of 195 // the next span is count * dx or 3 * dx. Span C to D covers an entire tile has a count 196 // of 5 and a length of 4 * dx. Remember, count is the number of pixels needed for the 197 // destination and the number of samples. 198 // 199 // Overall Strategy: 200 // While the span hangs over the edge of the tile, draw the span covering the tile then 201 // slide the span over to the next tile. 202 203 // The guard could have been count > 0, but then a bunch of math would be done in the 204 // common case. 205 206 Span span({x, y}, length, count); 207 if (dx > 0) { 208 while (!span.isEmpty() && span.endX() >= fXMax) { 209 Span toDraw = span.breakAt(fXMax, dx); 210 next->pointSpan(toDraw); 211 span.offset(-fXMax); 212 } 213 } else { 214 while (!span.isEmpty() && span.endX() < 0.0f) { 215 Span toDraw = span.breakAt(0.0f, dx); 216 next->pointSpan(toDraw); 217 span.offset(fXMax); 218 } 219 } 220 221 // All on a single tile. 222 if (!span.isEmpty()) { 223 next->pointSpan(span); 224 } 225 226 return true; 227 } 228 229private: 230 const SkScalar fXMax; 231 const Sk4s fXsMax; 232 const Sk4s fXsCap; 233 const Sk4s fXsInvMax; 234}; 235 236// The XRepeatUnitScaleStrategy exploits the situation where dx = 1.0. The main advantage is that 237// the relationship between the sample points and the source pixels does not change from tile to 238// repeated tile. This allows the tiler to calculate the span once and re-use it for each 239// repeated tile. This is later exploited by some samplers to avoid converting pixels to linear 240// space allowing the use of memmove to place pixel in the destination. 241class XRepeatUnitScaleStrategy { 242public: 243 XRepeatUnitScaleStrategy(int32_t max) 244 : fXMax{SkScalar(max)} 245 , fXsMax{SkScalar(max)} 246 , fXsCap{SkScalar(nextafterf(SkScalar(max), 0.0f))} 247 , fXsInvMax{1.0f / SkScalar(max)} { } 248 249 void tileXPoints(Sk4s* xs) { 250 Sk4s divX = *xs * fXsInvMax; 251 Sk4s modX = *xs - divX.floor() * fXsMax; 252 *xs = Sk4s::Min(fXsCap, modX); 253 SkASSERT(0 <= (*xs)[0] && (*xs)[0] < fXMax); 254 SkASSERT(0 <= (*xs)[1] && (*xs)[1] < fXMax); 255 SkASSERT(0 <= (*xs)[2] && (*xs)[2] < fXMax); 256 SkASSERT(0 <= (*xs)[3] && (*xs)[3] < fXMax); 257 } 258 259 template<typename Next> 260 bool maybeProcessSpan(Span originalSpan, Next* next) { 261 SkASSERT(!originalSpan.isEmpty()); 262 SkPoint start; SkScalar length; int count; 263 std::tie(start, length, count) = originalSpan; 264 // Make x and y in range on the tile. 265 SkScalar x = tile_mod(X(start), fXMax); 266 SkScalar y = Y(start); 267 268 // No need trying to go fast because the steps are larger than a tile or there is one point. 269 if (fXMax == 1 || count <= 1) { 270 return false; 271 } 272 273 // x should be on the tile. 274 SkASSERT(0.0f <= x && x < fXMax); 275 Span span({x, y}, length, count); 276 277 if (SkScalarFloorToScalar(x) != 0.0f) { 278 Span toDraw = span.breakAt(fXMax, 1.0f); 279 SkASSERT(0.0f <= toDraw.startX() && toDraw.endX() < fXMax); 280 next->pointSpan(toDraw); 281 span.offset(-fXMax); 282 } 283 284 // All of the span could have been on the first tile. If so, then no work to do. 285 if (span.isEmpty()) return true; 286 287 // At this point the span should be aligned to zero. 288 SkASSERT(SkScalarFloorToScalar(span.startX()) == 0.0f); 289 290 // Note: The span length has an unintuitive relation to the tile width. The tile width is 291 // a half open interval [tb, te), but the span is a closed interval [sb, se]. In order to 292 // compare the two, you need to convert the span to a half open interval. This is done by 293 // adding dx to se. So, the span becomes: [sb, se + dx). Hence the + 1.0f below. 294 SkScalar div = (span.length() + 1.0f) / fXMax; 295 int32_t repeatCount = SkScalarFloorToInt(div); 296 Span repeatableSpan{{0.0f, y}, fXMax - 1.0f, SkScalarFloorToInt(fXMax)}; 297 298 // Repeat the center section. 299 SkASSERT(0.0f <= repeatableSpan.startX() && repeatableSpan.endX() < fXMax); 300 if (repeatCount > 0) { 301 next->repeatSpan(repeatableSpan, repeatCount); 302 } 303 304 // Calculate the advance past the center portion. 305 SkScalar advance = SkScalar(repeatCount) * fXMax; 306 307 // There may be some of the span left over. 308 span.breakAt(advance, 1.0f); 309 310 // All on a single tile. 311 if (!span.isEmpty()) { 312 span.offset(-advance); 313 SkASSERT(0.0f <= span.startX() && span.endX() < fXMax); 314 next->pointSpan(span); 315 } 316 317 return true; 318 } 319 320private: 321 const SkScalar fXMax; 322 const Sk4s fXsMax; 323 const Sk4s fXsCap; 324 const Sk4s fXsInvMax; 325}; 326 327class YRepeatStrategy { 328public: 329 YRepeatStrategy(int32_t max) 330 : fYMax{SkScalar(max)} 331 , fYsMax{SkScalar(max)} 332 , fYsInvMax{1.0f / SkScalar(max)} { } 333 334 void tileYPoints(Sk4s* ys) { 335 Sk4s divY = *ys * fYsInvMax; 336 Sk4s modY = *ys - divY.floor() * fYsMax; 337 *ys = modY; 338 SkASSERT(0 <= (*ys)[0] && (*ys)[0] < fYMax); 339 SkASSERT(0 <= (*ys)[1] && (*ys)[1] < fYMax); 340 SkASSERT(0 <= (*ys)[2] && (*ys)[2] < fYMax); 341 SkASSERT(0 <= (*ys)[3] && (*ys)[3] < fYMax); 342 } 343 344 SkScalar tileY(SkScalar y) { 345 SkScalar answer = tile_mod(y, fYMax); 346 SkASSERT(0 <= answer && answer < fYMax); 347 return answer; 348 } 349 350private: 351 const SkScalar fYMax; 352 const Sk4s fYsMax; 353 const Sk4s fYsInvMax; 354}; 355// max = 40 356// mq2[x_] := Abs[(x - 40) - Floor[(x - 40)/80] * 80 - 40] 357class XMirrorStrategy { 358public: 359 XMirrorStrategy(int32_t max) 360 : fXsMax{SkScalar(max)} 361 , fXsCap{SkScalar(nextafterf(SkScalar(max), 0.0f))} 362 , fXsDoubleInvMax{1.0f / (2.0f * SkScalar(max))} { } 363 364 void tileXPoints(Sk4s* xs) { 365 Sk4f bias = *xs - fXsMax; 366 Sk4f div = bias * fXsDoubleInvMax; 367 Sk4f mod = bias - div.floor() * 2.0f * fXsMax; 368 Sk4f unbias = mod - fXsMax; 369 *xs = Sk4f::Min(unbias.abs(), fXsCap); 370 SkASSERT(0 <= (*xs)[0] && (*xs)[0] < fXsMax[0]); 371 SkASSERT(0 <= (*xs)[1] && (*xs)[1] < fXsMax[0]); 372 SkASSERT(0 <= (*xs)[2] && (*xs)[2] < fXsMax[0]); 373 SkASSERT(0 <= (*xs)[3] && (*xs)[3] < fXsMax[0]); 374 } 375 376 template <typename Next> 377 bool maybeProcessSpan(Span originalSpan, Next* next) { return false; } 378 379private: 380 Sk4f fXsMax; 381 Sk4f fXsCap; 382 Sk4f fXsDoubleInvMax; 383}; 384 385class YMirrorStrategy { 386public: 387 YMirrorStrategy(int32_t max) 388 : fYMax{SkScalar(max)} 389 , fYsMax{SkScalar(max)} 390 , fYsCap{nextafterf(SkScalar(max), 0.0f)} 391 , fYsDoubleInvMax{1.0f / (2.0f * SkScalar(max))} { } 392 393 void tileYPoints(Sk4s* ys) { 394 Sk4f bias = *ys - fYsMax; 395 Sk4f div = bias * fYsDoubleInvMax; 396 Sk4f mod = bias - div.floor() * 2.0f * fYsMax; 397 Sk4f unbias = mod - fYsMax; 398 *ys = Sk4f::Min(unbias.abs(), fYsCap); 399 SkASSERT(0 <= (*ys)[0] && (*ys)[0] < fYMax); 400 SkASSERT(0 <= (*ys)[1] && (*ys)[1] < fYMax); 401 SkASSERT(0 <= (*ys)[2] && (*ys)[2] < fYMax); 402 SkASSERT(0 <= (*ys)[3] && (*ys)[3] < fYMax); 403 } 404 405 SkScalar tileY(SkScalar y) { 406 SkScalar bias = y - fYMax; 407 SkScalar div = bias * fYsDoubleInvMax[0]; 408 SkScalar mod = bias - SkScalarFloorToScalar(div) * 2.0f * fYMax; 409 SkScalar unbias = mod - fYMax; 410 SkScalar answer = SkMinScalar(SkScalarAbs(unbias), fYsCap[0]); 411 SkASSERT(0 <= answer && answer < fYMax); 412 return answer; 413 } 414 415private: 416 SkScalar fYMax; 417 Sk4f fYsMax; 418 Sk4f fYsCap; 419 Sk4f fYsDoubleInvMax; 420}; 421 422} // namespace 423#endif // SkLinearBitmapPipeline_tile_DEFINED 424