michael@0: 
michael@0: /*
michael@0:  * Copyright 2008 The Android Open Source Project
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 "SkInterpolator.h"
michael@0: #include "SkMath.h"
michael@0: #include "SkTSearch.h"
michael@0: 
michael@0: SkInterpolatorBase::SkInterpolatorBase() {
michael@0:     fStorage    = NULL;
michael@0:     fTimes      = NULL;
michael@0:     SkDEBUGCODE(fTimesArray = NULL;)
michael@0: }
michael@0: 
michael@0: SkInterpolatorBase::~SkInterpolatorBase() {
michael@0:     if (fStorage) {
michael@0:         sk_free(fStorage);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkInterpolatorBase::reset(int elemCount, int frameCount) {
michael@0:     fFlags = 0;
michael@0:     fElemCount = SkToU8(elemCount);
michael@0:     fFrameCount = SkToS16(frameCount);
michael@0:     fRepeat = SK_Scalar1;
michael@0:     if (fStorage) {
michael@0:         sk_free(fStorage);
michael@0:         fStorage = NULL;
michael@0:         fTimes = NULL;
michael@0:         SkDEBUGCODE(fTimesArray = NULL);
michael@0:     }
michael@0: }
michael@0: 
michael@0: /*  Each value[] run is formated as:
michael@0:         <time (in msec)>
michael@0:         <blend>
michael@0:         <data[fElemCount]>
michael@0: 
michael@0:     Totaling fElemCount+2 entries per keyframe
michael@0: */
michael@0: 
michael@0: bool SkInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const {
michael@0:     if (fFrameCount == 0) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     if (startTime) {
michael@0:         *startTime = fTimes[0].fTime;
michael@0:     }
michael@0:     if (endTime) {
michael@0:         *endTime = fTimes[fFrameCount - 1].fTime;
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: SkScalar SkInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime,
michael@0:                                   SkMSec nextTime, const SkScalar blend[4]) {
michael@0:     SkASSERT(time > prevTime && time < nextTime);
michael@0: 
michael@0:     SkScalar t = SkScalarDiv((SkScalar)(time - prevTime),
michael@0:                              (SkScalar)(nextTime - prevTime));
michael@0:     return blend ?
michael@0:             SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
michael@0: }
michael@0: 
michael@0: SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T,
michael@0:                                         int* indexPtr, SkBool* exactPtr) const {
michael@0:     SkASSERT(fFrameCount > 0);
michael@0:     Result  result = kNormal_Result;
michael@0:     if (fRepeat != SK_Scalar1) {
michael@0:         SkMSec startTime = 0, endTime = 0;  // initialize to avoid warning
michael@0:         this->getDuration(&startTime, &endTime);
michael@0:         SkMSec totalTime = endTime - startTime;
michael@0:         SkMSec offsetTime = time - startTime;
michael@0:         endTime = SkScalarFloorToInt(fRepeat * totalTime);
michael@0:         if (offsetTime >= endTime) {
michael@0:             SkScalar fraction = SkScalarFraction(fRepeat);
michael@0:             offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
michael@0:                 (SkMSec) SkScalarFloorToInt(fraction * totalTime);
michael@0:             result = kFreezeEnd_Result;
michael@0:         } else {
michael@0:             int mirror = fFlags & kMirror;
michael@0:             offsetTime = offsetTime % (totalTime << mirror);
michael@0:             if (offsetTime > totalTime) { // can only be true if fMirror is true
michael@0:                 offsetTime = (totalTime << 1) - offsetTime;
michael@0:             }
michael@0:         }
michael@0:         time = offsetTime + startTime;
michael@0:     }
michael@0: 
michael@0:     int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time,
michael@0:                                   sizeof(SkTimeCode));
michael@0: 
michael@0:     bool    exact = true;
michael@0: 
michael@0:     if (index < 0) {
michael@0:         index = ~index;
michael@0:         if (index == 0) {
michael@0:             result = kFreezeStart_Result;
michael@0:         } else if (index == fFrameCount) {
michael@0:             if (fFlags & kReset) {
michael@0:                 index = 0;
michael@0:             } else {
michael@0:                 index -= 1;
michael@0:             }
michael@0:             result = kFreezeEnd_Result;
michael@0:         } else {
michael@0:             exact = false;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(index < fFrameCount);
michael@0:     const SkTimeCode* nextTime = &fTimes[index];
michael@0:     SkMSec   nextT = nextTime[0].fTime;
michael@0:     if (exact) {
michael@0:         *T = 0;
michael@0:     } else {
michael@0:         SkMSec prevT = nextTime[-1].fTime;
michael@0:         *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
michael@0:     }
michael@0:     *indexPtr = index;
michael@0:     *exactPtr = exact;
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: 
michael@0: SkInterpolator::SkInterpolator() {
michael@0:     INHERITED::reset(0, 0);
michael@0:     fValues = NULL;
michael@0:     SkDEBUGCODE(fScalarsArray = NULL;)
michael@0: }
michael@0: 
michael@0: SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
michael@0:     SkASSERT(elemCount > 0);
michael@0:     this->reset(elemCount, frameCount);
michael@0: }
michael@0: 
michael@0: void SkInterpolator::reset(int elemCount, int frameCount) {
michael@0:     INHERITED::reset(elemCount, frameCount);
michael@0:     fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount +
michael@0:                                 sizeof(SkTimeCode)) * frameCount);
michael@0:     fTimes = (SkTimeCode*) fStorage;
michael@0:     fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount);
michael@0: #ifdef SK_DEBUG
michael@0:     fTimesArray = (SkTimeCode(*)[10]) fTimes;
michael@0:     fScalarsArray = (SkScalar(*)[10]) fValues;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: #define SK_Fixed1Third      (SK_Fixed1/3)
michael@0: #define SK_Fixed2Third      (SK_Fixed1*2/3)
michael@0: 
michael@0: static const SkScalar gIdentityBlend[4] = {
michael@0:     0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
michael@0: };
michael@0: 
michael@0: bool SkInterpolator::setKeyFrame(int index, SkMSec time,
michael@0:                             const SkScalar values[], const SkScalar blend[4]) {
michael@0:     SkASSERT(values != NULL);
michael@0: 
michael@0:     if (blend == NULL) {
michael@0:         blend = gIdentityBlend;
michael@0:     }
michael@0: 
michael@0:     bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
michael@0:                                                sizeof(SkTimeCode));
michael@0:     SkASSERT(success);
michael@0:     if (success) {
michael@0:         SkTimeCode* timeCode = &fTimes[index];
michael@0:         timeCode->fTime = time;
michael@0:         memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
michael@0:         SkScalar* dst = &fValues[fElemCount * index];
michael@0:         memcpy(dst, values, fElemCount * sizeof(SkScalar));
michael@0:     }
michael@0:     return success;
michael@0: }
michael@0: 
michael@0: SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
michael@0:                                                     SkScalar values[]) const {
michael@0:     SkScalar T;
michael@0:     int index;
michael@0:     SkBool exact;
michael@0:     Result result = timeToT(time, &T, &index, &exact);
michael@0:     if (values) {
michael@0:         const SkScalar* nextSrc = &fValues[index * fElemCount];
michael@0: 
michael@0:         if (exact) {
michael@0:             memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
michael@0:         } else {
michael@0:             SkASSERT(index > 0);
michael@0: 
michael@0:             const SkScalar* prevSrc = nextSrc - fElemCount;
michael@0: 
michael@0:             for (int i = fElemCount - 1; i >= 0; --i) {
michael@0:                 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: typedef int Dot14;
michael@0: #define Dot14_ONE       (1 << 14)
michael@0: #define Dot14_HALF      (1 << 13)
michael@0: 
michael@0: #define Dot14ToFloat(x) ((x) / 16384.f)
michael@0: 
michael@0: static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
michael@0:     return (a * b + Dot14_HALF) >> 14;
michael@0: }
michael@0: 
michael@0: static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
michael@0:     return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
michael@0: }
michael@0: 
michael@0: static inline Dot14 pin_and_convert(SkScalar x) {
michael@0:     if (x <= 0) {
michael@0:         return 0;
michael@0:     }
michael@0:     if (x >= SK_Scalar1) {
michael@0:         return Dot14_ONE;
michael@0:     }
michael@0:     return SkScalarToFixed(x) >> 2;
michael@0: }
michael@0: 
michael@0: SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
michael@0:                            SkScalar cx, SkScalar cy) {
michael@0:     // pin to the unit-square, and convert to 2.14
michael@0:     Dot14 x = pin_and_convert(value);
michael@0: 
michael@0:     if (x == 0) return 0;
michael@0:     if (x == Dot14_ONE) return SK_Scalar1;
michael@0: 
michael@0:     Dot14 b = pin_and_convert(bx);
michael@0:     Dot14 c = pin_and_convert(cx);
michael@0: 
michael@0:     // Now compute our coefficients from the control points
michael@0:     //  t   -> 3b
michael@0:     //  t^2 -> 3c - 6b
michael@0:     //  t^3 -> 3b - 3c + 1
michael@0:     Dot14 A = 3*b;
michael@0:     Dot14 B = 3*(c - 2*b);
michael@0:     Dot14 C = 3*(b - c) + Dot14_ONE;
michael@0: 
michael@0:     // Now search for a t value given x
michael@0:     Dot14   t = Dot14_HALF;
michael@0:     Dot14   dt = Dot14_HALF;
michael@0:     for (int i = 0; i < 13; i++) {
michael@0:         dt >>= 1;
michael@0:         Dot14 guess = eval_cubic(t, A, B, C);
michael@0:         if (x < guess) {
michael@0:             t -= dt;
michael@0:         } else {
michael@0:             t += dt;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Now we have t, so compute the coeff for Y and evaluate
michael@0:     b = pin_and_convert(by);
michael@0:     c = pin_and_convert(cy);
michael@0:     A = 3*b;
michael@0:     B = 3*(c - 2*b);
michael@0:     C = 3*(b - c) + Dot14_ONE;
michael@0:     return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: 
michael@0: #ifdef SK_SUPPORT_UNITTEST
michael@0:     static SkScalar* iset(SkScalar array[3], int a, int b, int c) {
michael@0:         array[0] = SkIntToScalar(a);
michael@0:         array[1] = SkIntToScalar(b);
michael@0:         array[2] = SkIntToScalar(c);
michael@0:         return array;
michael@0:     }
michael@0: #endif
michael@0: 
michael@0: void SkInterpolator::UnitTest() {
michael@0: #ifdef SK_SUPPORT_UNITTEST
michael@0:     SkInterpolator  inter(3, 2);
michael@0:     SkScalar        v1[3], v2[3], v[3], vv[3];
michael@0:     Result          result;
michael@0: 
michael@0:     inter.setKeyFrame(0, 100, iset(v1, 10, 20, 30), 0);
michael@0:     inter.setKeyFrame(1, 200, iset(v2, 110, 220, 330));
michael@0: 
michael@0:     result = inter.timeToValues(0, v);
michael@0:     SkASSERT(result == kFreezeStart_Result);
michael@0:     SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
michael@0: 
michael@0:     result = inter.timeToValues(99, v);
michael@0:     SkASSERT(result == kFreezeStart_Result);
michael@0:     SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
michael@0: 
michael@0:     result = inter.timeToValues(100, v);
michael@0:     SkASSERT(result == kNormal_Result);
michael@0:     SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
michael@0: 
michael@0:     result = inter.timeToValues(200, v);
michael@0:     SkASSERT(result == kNormal_Result);
michael@0:     SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
michael@0: 
michael@0:     result = inter.timeToValues(201, v);
michael@0:     SkASSERT(result == kFreezeEnd_Result);
michael@0:     SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
michael@0: 
michael@0:     result = inter.timeToValues(150, v);
michael@0:     SkASSERT(result == kNormal_Result);
michael@0:     SkASSERT(memcmp(v, iset(vv, 60, 120, 180), sizeof(v)) == 0);
michael@0: 
michael@0:     result = inter.timeToValues(125, v);
michael@0:     SkASSERT(result == kNormal_Result);
michael@0:     result = inter.timeToValues(175, v);
michael@0:     SkASSERT(result == kNormal_Result);
michael@0: #endif
michael@0: }
michael@0: 
michael@0: #endif