1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 8ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SkAntiRun_DEFINED 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkAntiRun_DEFINED 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkBlitter.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1505fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com/** Sparse array of run-length-encoded alpha (supersampling coverage) values. 1605fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com Sparseness allows us to independently compose several paths into the 1705fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com same SkAlphaRuns buffer. 1805fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com*/ 1905fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comclass SkAlphaRuns { 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.compublic: 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int16_t* fRuns; 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com uint8_t* fAlpha; 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2505fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com /// Returns true if the scanline contains only a single run, 2605fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com /// of alpha value 0. 27d11f0e0173b349bfac3c98f6d32c10dc7e1ba1famike@reedtribe.org bool empty() const { 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fRuns[0] > 0); 298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fAlpha[0] == 0 && fRuns[fRuns[0]] == 0; 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 31d11f0e0173b349bfac3c98f6d32c10dc7e1ba1famike@reedtribe.org 3205fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com /// Reinitialize for a new scanline. 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void reset(int width); 34fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 35fa57ae7d1ec7404a654e0f32c09b698feec1b7fareed@google.com /** 3605fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * Insert into the buffer a run starting at (x-offsetX): 3705fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * if startAlpha > 0 3805fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * one pixel with value += startAlpha, 3905fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * max 255 4005fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * if middleCount > 0 4105fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * middleCount pixels with value += maxValue 4205fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * if stopAlpha > 0 4305fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * one pixel with value += stopAlpha 44fa57ae7d1ec7404a654e0f32c09b698feec1b7fareed@google.com * Returns the offsetX value that should be passed on the next call, 45fa57ae7d1ec7404a654e0f32c09b698feec1b7fareed@google.com * assuming we're on the same scanline. If the caller is switching 46fa57ae7d1ec7404a654e0f32c09b698feec1b7fareed@google.com * scanlines, then offsetX should be 0 when this is called. 47fa57ae7d1ec7404a654e0f32c09b698feec1b7fareed@google.com */ 489b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SK_ALWAYS_INLINE int add(int x, U8CPU startAlpha, int middleCount, U8CPU stopAlpha, 499b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com U8CPU maxValue, int offsetX) { 509b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkASSERT(middleCount >= 0); 519b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkASSERT(x >= 0 && x + (startAlpha != 0) + middleCount + (stopAlpha != 0) <= fWidth); 529b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 539b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkASSERT(fRuns[offsetX] >= 0); 549b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 559b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com int16_t* runs = fRuns + offsetX; 569b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com uint8_t* alpha = fAlpha + offsetX; 579b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com uint8_t* lastAlpha = alpha; 589b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com x -= offsetX; 599b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 609b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com if (startAlpha) { 619b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkAlphaRuns::Break(runs, alpha, x, 1); 629b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com /* I should be able to just add alpha[x] + startAlpha. 639b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com However, if the trailing edge of the previous span and the leading 649b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com edge of the current span round to the same super-sampled x value, 659b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com I might overflow to 256 with this add, hence the funny subtract (crud). 669b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com */ 679b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com unsigned tmp = alpha[x] + startAlpha; 689b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkASSERT(tmp <= 256); 699b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha[x] = SkToU8(tmp - (tmp >> 8)); // was (tmp >> 7), but that seems wrong if we're trying to catch 256 709b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 719b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs += x + 1; 729b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha += x + 1; 739b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com x = 0; 749b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com lastAlpha += x; // we don't want the +1 759b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkDEBUGCODE(this->validate();) 769b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 779b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 789b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com if (middleCount) { 799b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkAlphaRuns::Break(runs, alpha, x, middleCount); 809b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha += x; 819b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs += x; 829b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com x = 0; 839b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com do { 849b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha[0] = SkToU8(alpha[0] + maxValue); 859b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com int n = runs[0]; 869b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkASSERT(n <= middleCount); 879b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha += n; 889b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs += n; 899b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com middleCount -= n; 909b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } while (middleCount > 0); 919b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkDEBUGCODE(this->validate();) 929b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com lastAlpha = alpha; 939b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 949b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 959b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com if (stopAlpha) { 969b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkAlphaRuns::Break(runs, alpha, x, 1); 979b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha += x; 989b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha[0] = SkToU8(alpha[0] + stopAlpha); 999b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkDEBUGCODE(this->validate();) 1009b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com lastAlpha = alpha; 1019b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 1029b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 1039b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com return SkToS32(lastAlpha - fAlpha); // new offsetX 1049b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 105fa57ae7d1ec7404a654e0f32c09b698feec1b7fareed@google.com 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(void assertValid(int y, int maxStep) const;) 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(void dump() const;) 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10905fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com /** 11005fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * Break the runs in the buffer at offsets x and x+count, properly 11105fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * updating the runs to the right and left. 11205fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * i.e. from the state AAAABBBB, run-length encoded as A4B4, 11305fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * Break(..., 2, 5) would produce AAAABBBB rle as A2A2B3B1. 11405fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * Allows add() to sum another run to some of the new sub-runs. 11505fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * i.e. adding ..CCCCC. would produce AADDEEEB, rle as A2D2E3B1. 11605fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com */ 1179b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com static void Break(int16_t runs[], uint8_t alpha[], int x, int count) { 1189b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkASSERT(count > 0 && x >= 0); 1199b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 1209b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com // SkAlphaRuns::BreakAt(runs, alpha, x); 1219b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com // SkAlphaRuns::BreakAt(&runs[x], &alpha[x], count); 1229b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 1239b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com int16_t* next_runs = runs + x; 1249b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com uint8_t* next_alpha = alpha + x; 1259b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 1269b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com while (x > 0) { 1279b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com int n = runs[0]; 1289b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkASSERT(n > 0); 1299b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 1309b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com if (x < n) { 1319b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha[x] = alpha[0]; 1329b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs[0] = SkToS16(x); 1339b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs[x] = SkToS16(n - x); 1349b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com break; 1359b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 1369b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs += n; 1379b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha += n; 1389b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com x -= n; 1399b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 1409b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 1419b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs = next_runs; 1429b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha = next_alpha; 1439b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com x = count; 1449b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 1459b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com for (;;) { 1469b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com int n = runs[0]; 1479b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com SkASSERT(n > 0); 1489b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com 1499b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com if (x < n) { 1509b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha[x] = alpha[0]; 1519b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs[0] = SkToS16(x); 1529b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs[x] = SkToS16(n - x); 1539b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com break; 1549b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 1559b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com x -= n; 1569b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com if (x <= 0) { 1579b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com break; 1589b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 1599b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com runs += n; 1609b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com alpha += n; 1619b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 1629b8c036eda7ca8dde40e76dcd9378b3ddd629c8bmtklein@google.com } 163d11f0e0173b349bfac3c98f6d32c10dc7e1ba1famike@reedtribe.org 16405fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com /** 16505fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * Cut (at offset x in the buffer) a run into two shorter runs with 16605fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * matching alpha values. 16705fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * Used by the RectClipBlitter to trim a RLE encoding to match the 16805fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com * clipping rectangle. 16905fffdcc912cb9678e03d39529577e2a29b9209etomhudson@google.com */ 170d11f0e0173b349bfac3c98f6d32c10dc7e1ba1famike@reedtribe.org static void BreakAt(int16_t runs[], uint8_t alpha[], int x) { 171d11f0e0173b349bfac3c98f6d32c10dc7e1ba1famike@reedtribe.org while (x > 0) { 1728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int n = runs[0]; 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(n > 0); 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 175d11f0e0173b349bfac3c98f6d32c10dc7e1ba1famike@reedtribe.org if (x < n) { 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com alpha[x] = alpha[0]; 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com runs[0] = SkToS16(x); 1788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com runs[x] = SkToS16(n - x); 1798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com runs += n; 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com alpha += n; 1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com x -= n; 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(int fWidth;) 1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(void validate() const;) 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 193