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