180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SkAntiRun_DEFINED 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkAntiRun_DEFINED 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkBlitter.h" 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/** Sparse array of run-length-encoded alpha (supersampling coverage) values. 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sparseness allows us to independently compose several paths into the 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru same SkAlphaRuns buffer. 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkAlphaRuns { 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int16_t* fRuns; 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint8_t* fAlpha; 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /// Returns true if the scanline contains only a single run, 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /// of alpha value 0. 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool empty() const { 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fRuns[0] > 0); 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return fAlpha[0] == 0 && fRuns[fRuns[0]] == 0; 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /// Reinitialize for a new scanline. 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void reset(int width); 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Insert into the buffer a run starting at (x-offsetX): 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * if startAlpha > 0 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * one pixel with value += startAlpha, 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * max 255 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * if middleCount > 0 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * middleCount pixels with value += maxValue 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * if stopAlpha > 0 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * one pixel with value += stopAlpha 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Returns the offsetX value that should be passed on the next call, 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * assuming we're on the same scanline. If the caller is switching 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * scanlines, then offsetX should be 0 when this is called. 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 48910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SK_ALWAYS_INLINE int add(int x, U8CPU startAlpha, int middleCount, U8CPU stopAlpha, 49910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger U8CPU maxValue, int offsetX) { 50910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkASSERT(middleCount >= 0); 51910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkASSERT(x >= 0 && x + (startAlpha != 0) + middleCount + (stopAlpha != 0) <= fWidth); 52910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 53910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkASSERT(fRuns[offsetX] >= 0); 54910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 55910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger int16_t* runs = fRuns + offsetX; 56910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger uint8_t* alpha = fAlpha + offsetX; 57910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger uint8_t* lastAlpha = alpha; 58910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger x -= offsetX; 59910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 60910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger if (startAlpha) { 61910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkAlphaRuns::Break(runs, alpha, x, 1); 62910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger /* I should be able to just add alpha[x] + startAlpha. 63910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger However, if the trailing edge of the previous span and the leading 64910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger edge of the current span round to the same super-sampled x value, 65910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger I might overflow to 256 with this add, hence the funny subtract (crud). 66910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger */ 67910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger unsigned tmp = alpha[x] + startAlpha; 68910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkASSERT(tmp <= 256); 69910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha[x] = SkToU8(tmp - (tmp >> 8)); // was (tmp >> 7), but that seems wrong if we're trying to catch 256 70910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 71910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs += x + 1; 72910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha += x + 1; 73910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger x = 0; 74910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger lastAlpha += x; // we don't want the +1 75910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkDEBUGCODE(this->validate();) 76910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 77910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 78910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger if (middleCount) { 79910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkAlphaRuns::Break(runs, alpha, x, middleCount); 80910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha += x; 81910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs += x; 82910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger x = 0; 83910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger do { 84910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha[0] = SkToU8(alpha[0] + maxValue); 85910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger int n = runs[0]; 86910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkASSERT(n <= middleCount); 87910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha += n; 88910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs += n; 89910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger middleCount -= n; 90910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } while (middleCount > 0); 91910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkDEBUGCODE(this->validate();) 92910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger lastAlpha = alpha; 93910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 94910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 95910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger if (stopAlpha) { 96910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkAlphaRuns::Break(runs, alpha, x, 1); 97910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha += x; 98910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha[0] = SkToU8(alpha[0] + stopAlpha); 99910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkDEBUGCODE(this->validate();) 100910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger lastAlpha = alpha; 101910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 102910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 103910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger return SkToS32(lastAlpha - fAlpha); // new offsetX 104910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGCODE(void assertValid(int y, int maxStep) const;) 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGCODE(void dump() const;) 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Break the runs in the buffer at offsets x and x+count, properly 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * updating the runs to the right and left. 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * i.e. from the state AAAABBBB, run-length encoded as A4B4, 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Break(..., 2, 5) would produce AAAABBBB rle as A2A2B3B1. 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Allows add() to sum another run to some of the new sub-runs. 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * i.e. adding ..CCCCC. would produce AADDEEEB, rle as A2D2E3B1. 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 117910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger static void Break(int16_t runs[], uint8_t alpha[], int x, int count) { 118910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkASSERT(count > 0 && x >= 0); 119910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 120910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger // SkAlphaRuns::BreakAt(runs, alpha, x); 121910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger // SkAlphaRuns::BreakAt(&runs[x], &alpha[x], count); 122910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 123910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger int16_t* next_runs = runs + x; 124910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger uint8_t* next_alpha = alpha + x; 125910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 126910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger while (x > 0) { 127910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger int n = runs[0]; 128910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkASSERT(n > 0); 129910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 130910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger if (x < n) { 131910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha[x] = alpha[0]; 132910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs[0] = SkToS16(x); 133910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs[x] = SkToS16(n - x); 134910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger break; 135910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 136910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs += n; 137910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha += n; 138910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger x -= n; 139910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 140910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 141910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs = next_runs; 142910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha = next_alpha; 143910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger x = count; 144910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 145910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger for (;;) { 146910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger int n = runs[0]; 147910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger SkASSERT(n > 0); 148910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 149910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger if (x < n) { 150910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha[x] = alpha[0]; 151910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs[0] = SkToS16(x); 152910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs[x] = SkToS16(n - x); 153910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger break; 154910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 155910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger x -= n; 156910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger if (x <= 0) { 157910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger break; 158910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 159910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger runs += n; 160910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger alpha += n; 161910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 162910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger } 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Cut (at offset x in the buffer) a run into two shorter runs with 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * matching alpha values. 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Used by the RectClipBlitter to trim a RLE encoding to match the 16880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * clipping rectangle. 16980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 17080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static void BreakAt(int16_t runs[], uint8_t alpha[], int x) { 17180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (x > 0) { 17280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int n = runs[0]; 17380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(n > 0); 17480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (x < n) { 17680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru alpha[x] = alpha[0]; 17780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru runs[0] = SkToS16(x); 17880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru runs[x] = SkToS16(n - x); 17980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 18080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 18180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru runs += n; 18280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru alpha += n; 18380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru x -= n; 18480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 18580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 18680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 18880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGCODE(int fWidth;) 18980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGCODE(void validate() const;) 19080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 19180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 193