Home | History | Annotate | Download | only in gradients 
      1 /*
      2  * Copyright 2011 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 #include "SkClampRange.h"
      9 #include "SkMathPriv.h"
     10 
     11 static int SkCLZ64(uint64_t value) {
     12     int count = 0;
     13     if (value >> 32) {
     14         value >>= 32;
     15     } else {
     16         count += 32;
     17     }
     18     return count + SkCLZ(SkToU32(value));
     19 }
     20 
     21 static bool sk_64_smul_check(int64_t count, int64_t dx, int64_t* result) {
     22     // Do it the slow way until we have some assembly.
     23     if (dx == std::numeric_limits<int64_t>::min()) {
     24         return false; // SkTAbs overflow
     25     }
     26 
     27     SkASSERT(count >= 0);
     28     uint64_t ucount = static_cast<uint64_t>(count);
     29     uint64_t udx = static_cast<uint64_t>(SkTAbs(dx));
     30     int zeros = SkCLZ64(ucount) + SkCLZ64(udx);
     31     // this is a conservative check: it may return false when in fact it would not have overflowed.
     32     // Hackers Delight uses 34 as its convervative check, but that is for 32x32 multiplies.
     33     // Since we are looking at 64x64 muls, we add 32 to the check.
     34     if (zeros < (32 + 34)) {
     35         return false;
     36     }
     37     *result = count * dx;
     38     return true;
     39 }
     40 
     41 static bool sk_64_sadd_check(int64_t a, int64_t b, int64_t* result) {
     42     if (a > 0) {
     43         if (b > std::numeric_limits<int64_t>::max() - a) {
     44             return false;
     45         }
     46     } else {
     47         if (b < std::numeric_limits<int64_t>::min() - a) {
     48             return false;
     49         }
     50     }
     51 
     52     *result = a + b;
     53     return true;
     54 }
     55 
     56 
     57 /*
     58  *  returns [0..count] for the number of steps (<= count) for which x0 <= edge
     59  *  given each step is followed by x0 += dx
     60  */
     61 static int chop(int64_t x0, SkGradFixed edge, int64_t x1, int64_t dx, int count) {
     62     SkASSERT(dx > 0);
     63     SkASSERT(count >= 0);
     64 
     65     if (x0 >= edge) {
     66         return 0;
     67     }
     68     if (x1 <= edge) {
     69         return count;
     70     }
     71     int64_t n = (edge - x0 + dx - 1) / dx;
     72     SkASSERT(n >= 0);
     73     SkASSERT(n <= count);
     74     return (int)n;
     75 }
     76 
     77 void SkClampRange::initFor1(SkGradFixed fx) {
     78     fCount0 = fCount1 = fCount2 = 0;
     79     if (fx <= 0) {
     80         fCount0 = 1;
     81     } else if (fx < kFracMax_SkGradFixed) {
     82         fCount1 = 1;
     83         fFx1 = fx;
     84     } else {
     85         fCount2 = 1;
     86     }
     87 }
     88 
     89 void SkClampRange::init(SkGradFixed fx0, SkGradFixed dx0, int count, int v0, int v1) {
     90     SkASSERT(count > 0);
     91 
     92     fV0 = v0;
     93     fV1 = v1;
     94 
     95     // special case 1 == count, as it is slightly common for skia
     96     // and avoids us ever calling divide or 64bit multiply
     97     if (1 == count) {
     98         this->initFor1(fx0);
     99         return;
    100     }
    101 
    102     int64_t fx = fx0;
    103     int64_t dx = dx0;
    104 
    105     // start with ex equal to the last computed value
    106     int64_t count_times_dx, ex;
    107     if (!sk_64_smul_check(count - 1, dx, &count_times_dx) ||
    108         !sk_64_sadd_check(fx, count_times_dx, &ex)) {
    109         // we can't represent the computed end in 32.32, so just draw something (first color)
    110         fCount1 = fCount2 = 0;
    111         fCount0 = count;
    112         return;
    113     }
    114 
    115     if ((uint64_t)(fx | ex) <= kFracMax_SkGradFixed) {
    116         fCount0 = fCount2 = 0;
    117         fCount1 = count;
    118         fFx1 = fx0;
    119         return;
    120     }
    121     if (fx <= 0 && ex <= 0) {
    122         fCount1 = fCount2 = 0;
    123         fCount0 = count;
    124         return;
    125     }
    126     if (fx >= kFracMax_SkGradFixed && ex >= kFracMax_SkGradFixed) {
    127         fCount0 = fCount1 = 0;
    128         fCount2 = count;
    129         return;
    130     }
    131 
    132     // now make ex be 1 past the last computed value
    133     ex += dx;
    134 
    135     bool doSwap = dx < 0;
    136 
    137     if (doSwap) {
    138         ex -= dx;
    139         fx -= dx;
    140         SkTSwap(fx, ex);
    141         dx = -dx;
    142     }
    143 
    144 
    145     fCount0 = chop(fx, 0, ex, dx, count);
    146     SkASSERT(fCount0 >= 0);
    147     SkASSERT(fCount0 <= count);
    148     count -= fCount0;
    149     fx += fCount0 * dx;
    150     SkASSERT(fx >= 0);
    151     SkASSERT(fCount0 == 0 || (fx - dx) < 0);
    152     fCount1 = chop(fx, kFracMax_SkGradFixed, ex, dx, count);
    153     SkASSERT(fCount1 >= 0);
    154     SkASSERT(fCount1 <= count);
    155     count -= fCount1;
    156     fCount2 = count;
    157 
    158 #ifdef SK_DEBUG
    159     fx += fCount1 * dx;
    160     SkASSERT(fx <= ex);
    161     if (fCount2 > 0) {
    162         SkASSERT(fx >= kFracMax_SkGradFixed);
    163         if (fCount1 > 0) {
    164             SkASSERT(fx - dx < kFracMax_SkGradFixed);
    165         }
    166     }
    167 #endif
    168 
    169     if (doSwap) {
    170         SkTSwap(fCount0, fCount2);
    171         SkTSwap(fV0, fV1);
    172         dx = -dx;
    173     }
    174 
    175     if (fCount1 > 0) {
    176         fFx1 = fx0 + fCount0 * dx;
    177     }
    178 }
    179