src/third_party/skia/src/utils/SkInterpolator.cpp

   1
   2 /*
   3  * Copyright 2008 The Android Open Source Project
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8
   9
  10 #include "SkInterpolator.h"
  11 #include "SkMath.h"
  12 #include "SkTSearch.h"
  13
  14 SkInterpolatorBase::SkInterpolatorBase() {
  15     fStorage    = NULL;
  16     fTimes      = NULL;
  17     SkDEBUGCODE(fTimesArray = NULL;)
  18 }
  19
  20 SkInterpolatorBase::~SkInterpolatorBase() {
  21     if (fStorage) {
  22         sk_free(fStorage);
  23     }
  24 }
  25
  26 void SkInterpolatorBase::reset(int elemCount, int frameCount) {
  27     fFlags = 0;
  28     fElemCount = SkToU8(elemCount);
  29     fFrameCount = SkToS16(frameCount);
  30     fRepeat = SK_Scalar1;
  31     if (fStorage) {
  32         sk_free(fStorage);
  33         fStorage = NULL;
  34         fTimes = NULL;
  35         SkDEBUGCODE(fTimesArray = NULL);
  36     }
  37 }
  38
  39 /*  Each value[] run is formated as:
  40         <time (in msec)>
  41         <blend>
  42         <data[fElemCount]>
  43
  44     Totaling fElemCount+2 entries per keyframe
  45 */
  46
  47 bool SkInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const {
  48     if (fFrameCount == 0) {
  49         return false;
  50     }
  51
  52     if (startTime) {
  53         *startTime = fTimes[0].fTime;
  54     }
  55     if (endTime) {
  56         *endTime = fTimes[fFrameCount - 1].fTime;
  57     }
  58     return true;
  59 }
  60
  61 SkScalar SkInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime,
  62                                   SkMSec nextTime, const SkScalar blend[4]) {
  63     SkASSERT(time > prevTime && time < nextTime);
  64
  65     SkScalar t = SkScalarDiv((SkScalar)(time - prevTime),
  66                              (SkScalar)(nextTime - prevTime));
  67     return blend ?
  68             SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
  69 }
  70
  71 SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T,
  72                                         int* indexPtr, SkBool* exactPtr) const {
  73     SkASSERT(fFrameCount > 0);
  74     Result  result = kNormal_Result;
  75     if (fRepeat != SK_Scalar1) {
  76         SkMSec startTime = 0, endTime = 0;  // initialize to avoid warning
  77         this->getDuration(&startTime, &endTime);
  78         SkMSec totalTime = endTime - startTime;
  79         SkMSec offsetTime = time - startTime;
  80         endTime = SkScalarFloorToInt(fRepeat * totalTime);
  81         if (offsetTime >= endTime) {
  82             SkScalar fraction = SkScalarFraction(fRepeat);
  83             offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
  84                 (SkMSec) SkScalarFloorToInt(fraction * totalTime);
  85             result = kFreezeEnd_Result;
  86         } else {
  87             int mirror = fFlags & kMirror;
  88             offsetTime = offsetTime % (totalTime << mirror);
  89             if (offsetTime > totalTime) { // can only be true if fMirror is true
  90                 offsetTime = (totalTime << 1) - offsetTime;
  91             }
  92         }
  93         time = offsetTime + startTime;
  94     }
  95
  96     int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time,
  97                                   sizeof(SkTimeCode));
  98
  99     bool    exact = true;
 100
 101     if (index < 0) {
 102         index = ~index;
 103         if (index == 0) {
 104             result = kFreezeStart_Result;
 105         } else if (index == fFrameCount) {
 106             if (fFlags & kReset) {
 107                 index = 0;
 108             } else {
 109                 index -= 1;
 110             }
 111             result = kFreezeEnd_Result;
 112         } else {
 113             exact = false;
 114         }
 115     }
 116     SkASSERT(index < fFrameCount);
 117     const SkTimeCode* nextTime = &fTimes[index];
 118     SkMSec   nextT = nextTime[0].fTime;
 119     if (exact) {
 120         *T = 0;
 121     } else {
 122         SkMSec prevT = nextTime[-1].fTime;
 123         *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
 124     }
 125     *indexPtr = index;
 126     *exactPtr = exact;
 127     return result;
 128 }
 129
 130
 131 SkInterpolator::SkInterpolator() {
 132     INHERITED::reset(0, 0);
 133     fValues = NULL;
 134     SkDEBUGCODE(fScalarsArray = NULL;)
 135 }
 136
 137 SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
 138     SkASSERT(elemCount > 0);
 139     this->reset(elemCount, frameCount);
 140 }
 141
 142 void SkInterpolator::reset(int elemCount, int frameCount) {
 143     INHERITED::reset(elemCount, frameCount);
 144     fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount +
 145                                 sizeof(SkTimeCode)) * frameCount);
 146     fTimes = (SkTimeCode*) fStorage;
 147     fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount);
 148 #ifdef SK_DEBUG
 149     fTimesArray = (SkTimeCode(*)[10]) fTimes;
 150     fScalarsArray = (SkScalar(*)[10]) fValues;
 151 #endif
 152 }
 153
 154 #define SK_Fixed1Third      (SK_Fixed1/3)
 155 #define SK_Fixed2Third      (SK_Fixed1*2/3)
 156
 157 static const SkScalar gIdentityBlend[4] = {
 158     0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
 159 };
 160
 161 bool SkInterpolator::setKeyFrame(int index, SkMSec time,
 162                             const SkScalar values[], const SkScalar blend[4]) {
 163     SkASSERT(values != NULL);
 164
 165     if (blend == NULL) {
 166         blend = gIdentityBlend;
 167     }
 168
 169     bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
 170                                                sizeof(SkTimeCode));
 171     SkASSERT(success);
 172     if (success) {
 173         SkTimeCode* timeCode = &fTimes[index];
 174         timeCode->fTime = time;
 175         memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
 176         SkScalar* dst = &fValues[fElemCount * index];
 177         memcpy(dst, values, fElemCount * sizeof(SkScalar));
 178     }
 179     return success;
 180 }
 181
 182 SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
 183                                                     SkScalar values[]) const {
 184     SkScalar T;
 185     int index;
 186     SkBool exact;
 187     Result result = timeToT(time, &T, &index, &exact);
 188     if (values) {
 189         const SkScalar* nextSrc = &fValues[index * fElemCount];
 190
 191         if (exact) {
 192             memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
 193         } else {
 194             SkASSERT(index > 0);
 195
 196             const SkScalar* prevSrc = nextSrc - fElemCount;
 197
 198             for (int i = fElemCount - 1; i >= 0; --i) {
 199                 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
 200             }
 201         }
 202     }
 203     return result;
 204 }
 205
 206 ///////////////////////////////////////////////////////////////////////////////
 207
 208 typedef int Dot14;
 209 #define Dot14_ONE       (1 << 14)
 210 #define Dot14_HALF      (1 << 13)
 211
 212 #define Dot14ToFloat(x) ((x) / 16384.f)
 213
 214 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
 215     return (a * b + Dot14_HALF) >> 14;
 216 }
 217
 218 static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
 219     return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
 220 }
 221
 222 static inline Dot14 pin_and_convert(SkScalar x) {
 223     if (x <= 0) {
 224         return 0;
 225     }
 226     if (x >= SK_Scalar1) {
 227         return Dot14_ONE;
 228     }
 229     return SkScalarToFixed(x) >> 2;
 230 }
 231
 232 SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
 233                            SkScalar cx, SkScalar cy) {
 234     // pin to the unit-square, and convert to 2.14
 235     Dot14 x = pin_and_convert(value);
 236
 237     if (x == 0) return 0;
 238     if (x == Dot14_ONE) return SK_Scalar1;
 239
 240     Dot14 b = pin_and_convert(bx);
 241     Dot14 c = pin_and_convert(cx);
 242
 243     // Now compute our coefficients from the control points
 244     //  t   -> 3b
 245     //  t^2 -> 3c - 6b
 246     //  t^3 -> 3b - 3c + 1
 247     Dot14 A = 3*b;
 248     Dot14 B = 3*(c - 2*b);
 249     Dot14 C = 3*(b - c) + Dot14_ONE;
 250
 251     // Now search for a t value given x
 252     Dot14   t = Dot14_HALF;
 253     Dot14   dt = Dot14_HALF;
 254     for (int i = 0; i < 13; i++) {
 255         dt >>= 1;
 256         Dot14 guess = eval_cubic(t, A, B, C);
 257         if (x < guess) {
 258             t -= dt;
 259         } else {
 260             t += dt;
 261         }
 262     }
 263
 264     // Now we have t, so compute the coeff for Y and evaluate
 265     b = pin_and_convert(by);
 266     c = pin_and_convert(cy);
 267     A = 3*b;
 268     B = 3*(c - 2*b);
 269     C = 3*(b - c) + Dot14_ONE;
 270     return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
 271 }