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
14SkInterpolatorBase::SkInterpolatorBase() {
15    fStorage    = NULL;
16    fTimes      = NULL;
17    SkDEBUGCODE(fTimesArray = NULL;)
18}
19
20SkInterpolatorBase::~SkInterpolatorBase() {
21    if (fStorage) {
22        sk_free(fStorage);
23    }
24}
25
26void 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
47bool 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
61SkScalar 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
71SkInterpolatorBase::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 = SkScalarMulFloor(fRepeat, totalTime);
81        if (offsetTime >= endTime) {
82            SkScalar fraction = SkScalarFraction(fRepeat);
83            offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
84                SkScalarMulFloor(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 = NULL;
134    SkDEBUGCODE(fScalarsArray = NULL;)
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#ifdef SK_SCALAR_IS_FLOAT
159    0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
160#else
161    SK_Fixed1Third, SK_Fixed1Third, SK_Fixed2Third, SK_Fixed2Third
162#endif
163};
164
165bool SkInterpolator::setKeyFrame(int index, SkMSec time,
166                            const SkScalar values[], const SkScalar blend[4]) {
167    SkASSERT(values != NULL);
168
169    if (blend == NULL) {
170        blend = gIdentityBlend;
171    }
172
173    bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
174                                               sizeof(SkTimeCode));
175    SkASSERT(success);
176    if (success) {
177        SkTimeCode* timeCode = &fTimes[index];
178        timeCode->fTime = time;
179        memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
180        SkScalar* dst = &fValues[fElemCount * index];
181        memcpy(dst, values, fElemCount * sizeof(SkScalar));
182    }
183    return success;
184}
185
186SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
187                                                    SkScalar values[]) const {
188    SkScalar T;
189    int index;
190    SkBool exact;
191    Result result = timeToT(time, &T, &index, &exact);
192    if (values) {
193        const SkScalar* nextSrc = &fValues[index * fElemCount];
194
195        if (exact) {
196            memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
197        } else {
198            SkASSERT(index > 0);
199
200            const SkScalar* prevSrc = nextSrc - fElemCount;
201
202            for (int i = fElemCount - 1; i >= 0; --i) {
203                values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
204            }
205        }
206    }
207    return result;
208}
209
210///////////////////////////////////////////////////////////////////////////////
211
212typedef int Dot14;
213#define Dot14_ONE       (1 << 14)
214#define Dot14_HALF      (1 << 13)
215
216#define Dot14ToFloat(x) ((x) / 16384.f)
217
218static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
219    return (a * b + Dot14_HALF) >> 14;
220}
221
222static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
223    return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
224}
225
226static inline Dot14 pin_and_convert(SkScalar x) {
227    if (x <= 0) {
228        return 0;
229    }
230    if (x >= SK_Scalar1) {
231        return Dot14_ONE;
232    }
233    return SkScalarToFixed(x) >> 2;
234}
235
236SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
237                           SkScalar cx, SkScalar cy) {
238    // pin to the unit-square, and convert to 2.14
239    Dot14 x = pin_and_convert(value);
240
241    if (x == 0) return 0;
242    if (x == Dot14_ONE) return SK_Scalar1;
243
244    Dot14 b = pin_and_convert(bx);
245    Dot14 c = pin_and_convert(cx);
246
247    // Now compute our coefficients from the control points
248    //  t   -> 3b
249    //  t^2 -> 3c - 6b
250    //  t^3 -> 3b - 3c + 1
251    Dot14 A = 3*b;
252    Dot14 B = 3*(c - 2*b);
253    Dot14 C = 3*(b - c) + Dot14_ONE;
254
255    // Now search for a t value given x
256    Dot14   t = Dot14_HALF;
257    Dot14   dt = Dot14_HALF;
258    for (int i = 0; i < 13; i++) {
259        dt >>= 1;
260        Dot14 guess = eval_cubic(t, A, B, C);
261        if (x < guess) {
262            t -= dt;
263        } else {
264            t += dt;
265        }
266    }
267
268    // Now we have t, so compute the coeff for Y and evaluate
269    b = pin_and_convert(by);
270    c = pin_and_convert(cy);
271    A = 3*b;
272    B = 3*(c - 2*b);
273    C = 3*(b - c) + Dot14_ONE;
274    return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
275}
276
277///////////////////////////////////////////////////////////////////////////////
278///////////////////////////////////////////////////////////////////////////////
279
280#ifdef SK_DEBUG
281
282#ifdef SK_SUPPORT_UNITTEST
283    static SkScalar* iset(SkScalar array[3], int a, int b, int c) {
284        array[0] = SkIntToScalar(a);
285        array[1] = SkIntToScalar(b);
286        array[2] = SkIntToScalar(c);
287        return array;
288    }
289#endif
290
291void SkInterpolator::UnitTest() {
292#ifdef SK_SUPPORT_UNITTEST
293    SkInterpolator  inter(3, 2);
294    SkScalar        v1[3], v2[3], v[3], vv[3];
295    Result          result;
296
297    inter.setKeyFrame(0, 100, iset(v1, 10, 20, 30), 0);
298    inter.setKeyFrame(1, 200, iset(v2, 110, 220, 330));
299
300    result = inter.timeToValues(0, v);
301    SkASSERT(result == kFreezeStart_Result);
302    SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
303
304    result = inter.timeToValues(99, v);
305    SkASSERT(result == kFreezeStart_Result);
306    SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
307
308    result = inter.timeToValues(100, v);
309    SkASSERT(result == kNormal_Result);
310    SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
311
312    result = inter.timeToValues(200, v);
313    SkASSERT(result == kNormal_Result);
314    SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
315
316    result = inter.timeToValues(201, v);
317    SkASSERT(result == kFreezeEnd_Result);
318    SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
319
320    result = inter.timeToValues(150, v);
321    SkASSERT(result == kNormal_Result);
322    SkASSERT(memcmp(v, iset(vv, 60, 120, 180), sizeof(v)) == 0);
323
324    result = inter.timeToValues(125, v);
325    SkASSERT(result == kNormal_Result);
326    result = inter.timeToValues(175, v);
327    SkASSERT(result == kNormal_Result);
328#endif
329}
330
331#endif
332
333