michael@0: 
michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #include "SkClampRange.h"
michael@0: 
michael@0: /*
michael@0:  *  returns [0..count] for the number of steps (<= count) for which x0 <= edge
michael@0:  *  given each step is followed by x0 += dx
michael@0:  */
michael@0: static int chop(int64_t x0, SkFixed edge, int64_t x1, int64_t dx, int count) {
michael@0:     SkASSERT(dx > 0);
michael@0:     SkASSERT(count >= 0);
michael@0: 
michael@0:     if (x0 >= edge) {
michael@0:         return 0;
michael@0:     }
michael@0:     if (x1 <= edge) {
michael@0:         return count;
michael@0:     }
michael@0:     int64_t n = (edge - x0 + dx - 1) / dx;
michael@0:     SkASSERT(n >= 0);
michael@0:     SkASSERT(n <= count);
michael@0:     return (int)n;
michael@0: }
michael@0: 
michael@0: static bool overflows_fixed(int64_t x) {
michael@0:     return x < -SK_FixedMax || x > SK_FixedMax;
michael@0: }
michael@0: 
michael@0: void SkClampRange::initFor1(SkFixed fx) {
michael@0:     fCount0 = fCount1 = fCount2 = 0;
michael@0:     if (fx <= 0) {
michael@0:         fCount0 = 1;
michael@0:     } else if (fx < 0xFFFF) {
michael@0:         fCount1 = 1;
michael@0:         fFx1 = fx;
michael@0:     } else {
michael@0:         fCount2 = 1;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkClampRange::init(SkFixed fx0, SkFixed dx0, int count, int v0, int v1) {
michael@0:     SkASSERT(count > 0);
michael@0: 
michael@0:     fV0 = v0;
michael@0:     fV1 = v1;
michael@0:     fOverflowed = false;
michael@0: 
michael@0:     // special case 1 == count, as it is slightly common for skia
michael@0:     // and avoids us ever calling divide or 64bit multiply
michael@0:     if (1 == count) {
michael@0:         this->initFor1(fx0);
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     int64_t fx = fx0;
michael@0:     int64_t dx = dx0;
michael@0:     // start with ex equal to the last computed value
michael@0:     int64_t ex = fx + (count - 1) * dx;
michael@0:     fOverflowed = overflows_fixed(ex);
michael@0: 
michael@0:     if ((uint64_t)(fx | ex) <= 0xFFFF) {
michael@0:         fCount0 = fCount2 = 0;
michael@0:         fCount1 = count;
michael@0:         fFx1 = fx0;
michael@0:         return;
michael@0:     }
michael@0:     if (fx <= 0 && ex <= 0) {
michael@0:         fCount1 = fCount2 = 0;
michael@0:         fCount0 = count;
michael@0:         return;
michael@0:     }
michael@0:     if (fx >= 0xFFFF && ex >= 0xFFFF) {
michael@0:         fCount0 = fCount1 = 0;
michael@0:         fCount2 = count;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     int extraCount = 0;
michael@0: 
michael@0:     // now make ex be 1 past the last computed value
michael@0:     ex += dx;
michael@0:     fOverflowed = overflows_fixed(ex);
michael@0:     // now check for over/under flow
michael@0:     if (fOverflowed) {
michael@0:         int originalCount = count;
michael@0:         int64_t ccount;
michael@0:         bool swap = dx < 0;
michael@0:         if (swap) {
michael@0:             dx = -dx;
michael@0:             fx = -fx;
michael@0:         }
michael@0:         ccount = (SK_FixedMax - fx + dx - 1) / dx;
michael@0:         if (swap) {
michael@0:             dx = -dx;
michael@0:             fx = -fx;
michael@0:         }
michael@0:         SkASSERT(ccount > 0 && ccount <= SK_FixedMax);
michael@0: 
michael@0:         count = (int)ccount;
michael@0:         if (0 == count) {
michael@0:             this->initFor1(fx0);
michael@0:             if (dx > 0) {
michael@0:                 fCount2 += originalCount - 1;
michael@0:             } else {
michael@0:                 fCount0 += originalCount - 1;
michael@0:             }
michael@0:             return;
michael@0:         }
michael@0:         extraCount = originalCount - count;
michael@0:         ex = fx + dx * count;
michael@0:     }
michael@0: 
michael@0:     bool doSwap = dx < 0;
michael@0: 
michael@0:     if (doSwap) {
michael@0:         ex -= dx;
michael@0:         fx -= dx;
michael@0:         SkTSwap(fx, ex);
michael@0:         dx = -dx;
michael@0:     }
michael@0: 
michael@0: 
michael@0:     fCount0 = chop(fx, 0, ex, dx, count);
michael@0:     count -= fCount0;
michael@0:     fx += fCount0 * dx;
michael@0:     SkASSERT(fx >= 0);
michael@0:     SkASSERT(fCount0 == 0 || (fx - dx) < 0);
michael@0:     fCount1 = chop(fx, 0xFFFF, ex, dx, count);
michael@0:     count -= fCount1;
michael@0:     fCount2 = count;
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     fx += fCount1 * dx;
michael@0:     SkASSERT(fx <= ex);
michael@0:     if (fCount2 > 0) {
michael@0:         SkASSERT(fx >= 0xFFFF);
michael@0:         if (fCount1 > 0) {
michael@0:             SkASSERT(fx - dx < 0xFFFF);
michael@0:         }
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     if (doSwap) {
michael@0:         SkTSwap(fCount0, fCount2);
michael@0:         SkTSwap(fV0, fV1);
michael@0:         dx = -dx;
michael@0:     }
michael@0: 
michael@0:     if (fCount1 > 0) {
michael@0:         fFx1 = fx0 + fCount0 * (int)dx;
michael@0:     }
michael@0: 
michael@0:     if (dx > 0) {
michael@0:         fCount2 += extraCount;
michael@0:     } else {
michael@0:         fCount0 += extraCount;
michael@0:     }
michael@0: }