1/* 2 * Copyright 2008 The Android Open Source Project 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 "SkInterpolator.h" 9 10#include "SkFixed.h" 11#include "SkMath.h" 12#include "SkMalloc.h" 13#include "SkTSearch.h" 14 15SkInterpolatorBase::SkInterpolatorBase() { 16 fStorage = nullptr; 17 fTimes = nullptr; 18 SkDEBUGCODE(fTimesArray = nullptr;) 19} 20 21SkInterpolatorBase::~SkInterpolatorBase() { 22 if (fStorage) { 23 sk_free(fStorage); 24 } 25} 26 27void SkInterpolatorBase::reset(int elemCount, int frameCount) { 28 fFlags = 0; 29 fElemCount = SkToU8(elemCount); 30 fFrameCount = SkToS16(frameCount); 31 fRepeat = SK_Scalar1; 32 if (fStorage) { 33 sk_free(fStorage); 34 fStorage = nullptr; 35 fTimes = nullptr; 36 SkDEBUGCODE(fTimesArray = nullptr); 37 } 38} 39 40/* Each value[] run is formated as: 41 <time (in msec)> 42 <blend> 43 <data[fElemCount]> 44 45 Totaling fElemCount+2 entries per keyframe 46*/ 47 48bool SkInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const { 49 if (fFrameCount == 0) { 50 return false; 51 } 52 53 if (startTime) { 54 *startTime = fTimes[0].fTime; 55 } 56 if (endTime) { 57 *endTime = fTimes[fFrameCount - 1].fTime; 58 } 59 return true; 60} 61 62SkScalar SkInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime, 63 SkMSec nextTime, const SkScalar blend[4]) { 64 SkASSERT(time > prevTime && time < nextTime); 65 66 SkScalar t = (SkScalar)(time - prevTime) / (SkScalar)(nextTime - prevTime); 67 return blend ? 68 SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t; 69} 70 71SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T, 72 int* indexPtr, bool* 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 131SkInterpolator::SkInterpolator() { 132 INHERITED::reset(0, 0); 133 fValues = nullptr; 134 SkDEBUGCODE(fScalarsArray = nullptr;) 135} 136 137SkInterpolator::SkInterpolator(int elemCount, int frameCount) { 138 SkASSERT(elemCount > 0); 139 this->reset(elemCount, frameCount); 140} 141 142void 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 157static const SkScalar gIdentityBlend[4] = { 158 0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f 159}; 160 161bool SkInterpolator::setKeyFrame(int index, SkMSec time, 162 const SkScalar values[], const SkScalar blend[4]) { 163 SkASSERT(values != nullptr); 164 165 if (blend == nullptr) { 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 182SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time, 183 SkScalar values[]) const { 184 SkScalar T; 185 int index; 186 bool 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 208typedef int Dot14; 209#define Dot14_ONE (1 << 14) 210#define Dot14_HALF (1 << 13) 211 212#define Dot14ToFloat(x) ((x) / 16384.f) 213 214static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) { 215 return (a * b + Dot14_HALF) >> 14; 216} 217 218static 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 222static 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 232SkScalar 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} 272