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 "SkMath.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 a, int64_t b, int64_t* result) {
     22     // Do it the slow way until we have some assembly.
     23     int64_t ua = SkTAbs(a);
     24     int64_t ub = SkTAbs(b);
     25     int zeros = SkCLZ64(ua) + SkCLZ64(ub);
     26     // this is a conservative check: it may return false when in fact it would not have overflowed.
     27     // Hackers Delight uses 34 as its convervative check, but that is for 32x32 multiplies.
     28     // Since we are looking at 64x64 muls, we add 32 to the check.
     29     if (zeros < (32 + 34)) {
     30         return false;
     31     }
     32     *result = a * b;
     33     return true;
     34 }
     35 
     36 /*
     37  *  returns [0..count] for the number of steps (<= count) for which x0 <= edge
     38  *  given each step is followed by x0 += dx
     39  */
     40 static int chop(int64_t x0, SkGradFixed edge, int64_t x1, int64_t dx, int count) {
     41     SkASSERT(dx > 0);
     42     SkASSERT(count >= 0);
     43 
     44     if (x0 >= edge) {
     45         return 0;
     46     }
     47     if (x1 <= edge) {
     48         return count;
     49     }
     50     int64_t n = (edge - x0 + dx - 1) / dx;
     51     SkASSERT(n >= 0);
     52     SkASSERT(n <= count);
     53     return (int)n;
     54 }
     55 
     56 void SkClampRange::initFor1(SkGradFixed fx) {
     57     fCount0 = fCount1 = fCount2 = 0;
     58     if (fx <= 0) {
     59         fCount0 = 1;
     60     } else if (fx < kFracMax_SkGradFixed) {
     61         fCount1 = 1;
     62         fFx1 = fx;
     63     } else {
     64         fCount2 = 1;
     65     }
     66 }
     67 
     68 void SkClampRange::init(SkGradFixed fx0, SkGradFixed dx0, int count, int v0, int v1) {
     69     SkASSERT(count > 0);
     70 
     71     fV0 = v0;
     72     fV1 = v1;
     73 
     74     // special case 1 == count, as it is slightly common for skia
     75     // and avoids us ever calling divide or 64bit multiply
     76     if (1 == count) {
     77         this->initFor1(fx0);
     78         return;
     79     }
     80 
     81     int64_t fx = fx0;
     82     int64_t dx = dx0;
     83 
     84     // start with ex equal to the last computed value
     85     int64_t count_times_dx;
     86     if (!sk_64_smul_check(count - 1, dx, &count_times_dx)) {
     87         // we can't represent the computed end in 32.32, so just draw something (first color)
     88         fCount1 = fCount2 = 0;
     89         fCount0 = count;
     90         return;
     91     }
     92 
     93     int64_t ex = fx + (count - 1) * dx;
     94 
     95     if ((uint64_t)(fx | ex) <= kFracMax_SkGradFixed) {
     96         fCount0 = fCount2 = 0;
     97         fCount1 = count;
     98         fFx1 = fx0;
     99         return;
    100     }
    101     if (fx <= 0 && ex <= 0) {
    102         fCount1 = fCount2 = 0;
    103         fCount0 = count;
    104         return;
    105     }
    106     if (fx >= kFracMax_SkGradFixed && ex >= kFracMax_SkGradFixed) {
    107         fCount0 = fCount1 = 0;
    108         fCount2 = count;
    109         return;
    110     }
    111 
    112     // now make ex be 1 past the last computed value
    113     ex += dx;
    114 
    115     bool doSwap = dx < 0;
    116 
    117     if (doSwap) {
    118         ex -= dx;
    119         fx -= dx;
    120         SkTSwap(fx, ex);
    121         dx = -dx;
    122     }
    123 
    124 
    125     fCount0 = chop(fx, 0, ex, dx, count);
    126     SkASSERT(fCount0 >= 0);
    127     SkASSERT(fCount0 <= count);
    128     count -= fCount0;
    129     fx += fCount0 * dx;
    130     SkASSERT(fx >= 0);
    131     SkASSERT(fCount0 == 0 || (fx - dx) < 0);
    132     fCount1 = chop(fx, kFracMax_SkGradFixed, ex, dx, count);
    133     SkASSERT(fCount1 >= 0);
    134     SkASSERT(fCount1 <= count);
    135     count -= fCount1;
    136     fCount2 = count;
    137 
    138 #ifdef SK_DEBUG
    139     fx += fCount1 * dx;
    140     SkASSERT(fx <= ex);
    141     if (fCount2 > 0) {
    142         SkASSERT(fx >= kFracMax_SkGradFixed);
    143         if (fCount1 > 0) {
    144             SkASSERT(fx - dx < kFracMax_SkGradFixed);
    145         }
    146     }
    147 #endif
    148 
    149     if (doSwap) {
    150         SkTSwap(fCount0, fCount2);
    151         SkTSwap(fV0, fV1);
    152         dx = -dx;
    153     }
    154 
    155     if (fCount1 > 0) {
    156         fFx1 = fx0 + fCount0 * dx;
    157     }
    158 }
    159