135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 21cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 31cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Copyright 2011 Google Inc. 41cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * 51cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * Use of this source code is governed by a BSD-style license that can be 61cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger * found in the LICENSE file. 735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger */ 835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 91cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger#include "SkClampRange.h" 1135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 1235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger/* 1335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger * returns [0..count] for the number of steps (<= count) for which x0 <= edge 1435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger * given each step is followed by x0 += dx 1535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger */ 1635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenbergerstatic int chop(int64_t x0, SkFixed edge, int64_t x1, int64_t dx, int count) { 1735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(dx > 0); 1835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(count >= 0); 1935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 2035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (x0 >= edge) { 2135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return 0; 2235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 2335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (x1 <= edge) { 2435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return count; 2535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 2635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger int64_t n = (edge - x0 + dx - 1) / dx; 2735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(n >= 0); 2835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(n <= count); 2935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return (int)n; 3035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger} 3135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 3235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenbergerstatic bool overflows_fixed(int64_t x) { 3335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return x < -SK_FixedMax || x > SK_FixedMax; 3435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger} 3535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 3635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenbergervoid SkClampRange::initFor1(SkFixed fx) { 3735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount0 = fCount1 = fCount2 = 0; 3835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (fx <= 0) { 3935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount0 = 1; 4035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } else if (fx < 0xFFFF) { 4135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount1 = 1; 4235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fFx1 = fx; 4335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } else { 4435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount2 = 1; 4535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 4635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger} 4735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 4835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenbergervoid SkClampRange::init(SkFixed fx0, SkFixed dx0, int count, int v0, int v1) { 4935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(count > 0); 5035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 5135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fV0 = v0; 5235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fV1 = v1; 5335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fOverflowed = false; 5435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 5535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // special case 1 == count, as it is slightly common for skia 5635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // and avoids us ever calling divide or 64bit multiply 5735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (1 == count) { 5835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger this->initFor1(fx0); 5935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return; 6035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 6135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 6235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger int64_t fx = fx0; 6335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger int64_t dx = dx0; 6435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // start with ex equal to the last computed value 6535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger int64_t ex = fx + (count - 1) * dx; 6635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fOverflowed = overflows_fixed(ex); 6735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 6835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if ((uint64_t)(fx | ex) <= 0xFFFF) { 6935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount0 = fCount2 = 0; 7035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount1 = count; 7135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fFx1 = fx0; 7235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return; 7335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 7435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (fx <= 0 && ex <= 0) { 7535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount1 = fCount2 = 0; 7635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount0 = count; 7735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return; 7835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 7935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (fx >= 0xFFFF && ex >= 0xFFFF) { 8035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount0 = fCount1 = 0; 8135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount2 = count; 8235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return; 8335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 8435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 8535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger int extraCount = 0; 8635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 8735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // now make ex be 1 past the last computed value 8835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ex += dx; 8935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fOverflowed = overflows_fixed(ex); 9035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // now check for over/under flow 9135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (fOverflowed) { 9235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger int originalCount = count; 9335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger int64_t ccount; 9435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger bool swap = dx < 0; 9535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (swap) { 9635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger dx = -dx; 9735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fx = -fx; 9835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 9935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ccount = (SK_FixedMax - fx + dx - 1) / dx; 10035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (swap) { 10135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger dx = -dx; 10235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fx = -fx; 10335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 10435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(ccount > 0 && ccount <= SK_FixedMax); 10535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 10635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger count = (int)ccount; 10735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (0 == count) { 10835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger this->initFor1(fx0); 10935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (dx > 0) { 11035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount2 += originalCount - 1; 11135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } else { 11235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount0 += originalCount - 1; 11335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 11435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return; 11535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 11635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger extraCount = originalCount - count; 11735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ex = fx + dx * count; 11835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 11935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 12035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger bool doSwap = dx < 0; 12135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 12235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (doSwap) { 12335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ex -= dx; 12435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fx -= dx; 12535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkTSwap(fx, ex); 12635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger dx = -dx; 12735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 12835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 12935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 13035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount0 = chop(fx, 0, ex, dx, count); 13135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger count -= fCount0; 13235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fx += fCount0 * dx; 13335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(fx >= 0); 13435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(fCount0 == 0 || (fx - dx) < 0); 13535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount1 = chop(fx, 0xFFFF, ex, dx, count); 13635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger count -= fCount1; 13735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount2 = count; 13835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 13935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger#ifdef SK_DEBUG 14035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fx += fCount1 * dx; 14135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(fx <= ex); 14235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (fCount2 > 0) { 14335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(fx >= 0xFFFF); 14435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (fCount1 > 0) { 14535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(fx - dx < 0xFFFF); 14635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 14735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 14835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger#endif 14935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 15035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (doSwap) { 15135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkTSwap(fCount0, fCount2); 15235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkTSwap(fV0, fV1); 15335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger dx = -dx; 15435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 15535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 15635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (fCount1 > 0) { 15735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fFx1 = fx0 + fCount0 * (int)dx; 15835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 15935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 16035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (dx > 0) { 16135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount2 += extraCount; 16235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } else { 16335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger fCount0 += extraCount; 16435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 16535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger} 16635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 167