1676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 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. 7676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org */ 8676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 10676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org#include "SkClampRange.h" 11676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 12676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org/* 13676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org * returns [0..count] for the number of steps (<= count) for which x0 <= edge 14676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org * given each step is followed by x0 += dx 15676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org */ 1613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.comstatic int chop(int64_t x0, SkFixed edge, int64_t x1, int64_t dx, int count) { 17676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(dx > 0); 18676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(count >= 0); 19676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 20676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org if (x0 >= edge) { 21676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org return 0; 22676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 23676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org if (x1 <= edge) { 24676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org return count; 25676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 2613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com int64_t n = (edge - x0 + dx - 1) / dx; 27676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(n >= 0); 28676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(n <= count); 2913659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com return (int)n; 30676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org} 31676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 3213659f1f8d2e705c565203d45870b1afcd47cf98reed@google.comstatic bool overflows_fixed(int64_t x) { 3313659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com return x < -SK_FixedMax || x > SK_FixedMax; 3413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com} 3513659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com 3613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.comvoid SkClampRange::initFor1(SkFixed fx) { 3713659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fCount0 = fCount1 = fCount2 = 0; 3813659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com if (fx <= 0) { 3913659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fCount0 = 1; 4013659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } else if (fx < 0xFFFF) { 4113659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fCount1 = 1; 4213659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fFx1 = fx; 4313659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } else { 4413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fCount2 = 1; 4513659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } 4613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com} 4713659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com 4813659f1f8d2e705c565203d45870b1afcd47cf98reed@google.comvoid SkClampRange::init(SkFixed fx0, SkFixed dx0, int count, int v0, int v1) { 49676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(count > 0); 50676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 51676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fV0 = v0; 52676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fV1 = v1; 53676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 5413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com // special case 1 == count, as it is slightly common for skia 5513659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com // and avoids us ever calling divide or 64bit multiply 5613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com if (1 == count) { 5713659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com this->initFor1(fx0); 5813659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com return; 5963c1ad82fc4232daff1b686cc78bba4c6a42916dreed@google.com } 6063c1ad82fc4232daff1b686cc78bba4c6a42916dreed@google.com 6113659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com int64_t fx = fx0; 6213659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com int64_t dx = dx0; 63676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org // start with ex equal to the last computed value 6413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com int64_t ex = fx + (count - 1) * dx; 65676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 6613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com if ((uint64_t)(fx | ex) <= 0xFFFF) { 67676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount0 = fCount2 = 0; 68676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount1 = count; 6913659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fFx1 = fx0; 70676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org return; 71676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 72676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org if (fx <= 0 && ex <= 0) { 73676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount1 = fCount2 = 0; 74676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount0 = count; 75676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org return; 76676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 77676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org if (fx >= 0xFFFF && ex >= 0xFFFF) { 78676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount0 = fCount1 = 0; 79676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount2 = count; 80676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org return; 81676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 82676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 8313659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com int extraCount = 0; 8413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com 85676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org // now make ex be 1 past the last computed value 86676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org ex += dx; 8713659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com // now check for over/under flow 8833a94e2ba79d41de91d3412d8ae1504c187aacb1reed@google.com if (overflows_fixed(ex)) { 8913659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com int originalCount = count; 9013659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com int64_t ccount; 9113659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com bool swap = dx < 0; 9213659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com if (swap) { 9313659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com dx = -dx; 9413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fx = -fx; 9513659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } 9613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com ccount = (SK_FixedMax - fx + dx - 1) / dx; 9713659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com if (swap) { 9813659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com dx = -dx; 9913659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fx = -fx; 10013659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } 10113659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com SkASSERT(ccount > 0 && ccount <= SK_FixedMax); 10213659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com 10313659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com count = (int)ccount; 10413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com if (0 == count) { 10513659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com this->initFor1(fx0); 10613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com if (dx > 0) { 10713659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fCount2 += originalCount - 1; 10813659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } else { 10913659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fCount0 += originalCount - 1; 11013659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } 11113659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com return; 11213659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } 11313659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com extraCount = originalCount - count; 11413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com ex = fx + dx * count; 11513659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } 116fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 117676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org bool doSwap = dx < 0; 118676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 119676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org if (doSwap) { 120676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org ex -= dx; 121676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fx -= dx; 122676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkTSwap(fx, ex); 123676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org dx = -dx; 124676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 125676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 12613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com 127676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount0 = chop(fx, 0, ex, dx, count); 128676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org count -= fCount0; 129676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fx += fCount0 * dx; 130676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(fx >= 0); 131676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(fCount0 == 0 || (fx - dx) < 0); 132676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount1 = chop(fx, 0xFFFF, ex, dx, count); 133676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org count -= fCount1; 134676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fCount2 = count; 135676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 136676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org#ifdef SK_DEBUG 137676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org fx += fCount1 * dx; 138676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(fx <= ex); 139676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org if (fCount2 > 0) { 140676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(fx >= 0xFFFF); 141676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org if (fCount1 > 0) { 142676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkASSERT(fx - dx < 0xFFFF); 143676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 144676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 145676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org#endif 146676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 147676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org if (doSwap) { 148676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkTSwap(fCount0, fCount2); 149676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org SkTSwap(fV0, fV1); 15063c1ad82fc4232daff1b686cc78bba4c6a42916dreed@google.com dx = -dx; 151676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 152676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org 15363c1ad82fc4232daff1b686cc78bba4c6a42916dreed@google.com if (fCount1 > 0) { 15413659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fFx1 = fx0 + fCount0 * (int)dx; 15513659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } 15613659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com 15713659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com if (dx > 0) { 15813659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fCount2 += extraCount; 15913659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com } else { 16013659f1f8d2e705c565203d45870b1afcd47cf98reed@google.com fCount0 += extraCount; 161676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org } 162676d69b82f2e2c6bf743ff8c7fbb436f36a004e2mike@reedtribe.org} 163