1 /*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "SkiaInterpolator.h"
18
19 #include "include/core/SkScalar.h"
20 #include "include/core/SkTypes.h"
21
22 #include <cstdlib>
23 #include <cstring>
24 #include <log/log.h>
25
26 typedef int Dot14;
27 #define Dot14_ONE (1 << 14)
28 #define Dot14_HALF (1 << 13)
29
30 #define Dot14ToFloat(x) ((x) / 16384.f)
31
Dot14Mul(Dot14 a,Dot14 b)32 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
33 return (a * b + Dot14_HALF) >> 14;
34 }
35
eval_cubic(Dot14 t,Dot14 A,Dot14 B,Dot14 C)36 static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
37 return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
38 }
39
pin_and_convert(float x)40 static inline Dot14 pin_and_convert(float x) {
41 if (x <= 0) {
42 return 0;
43 }
44 if (x >= 1.0f) {
45 return Dot14_ONE;
46 }
47 return static_cast<Dot14>(x * Dot14_ONE);
48 }
49
SkUnitCubicInterp(float value,float bx,float by,float cx,float cy)50 static float SkUnitCubicInterp(float value, float bx, float by, float cx, float cy) {
51 // pin to the unit-square, and convert to 2.14
52 Dot14 x = pin_and_convert(value);
53
54 if (x == 0) return 0.0f;
55 if (x == Dot14_ONE) return 1.0f;
56
57 Dot14 b = pin_and_convert(bx);
58 Dot14 c = pin_and_convert(cx);
59
60 // Now compute our coefficients from the control points
61 // t -> 3b
62 // t^2 -> 3c - 6b
63 // t^3 -> 3b - 3c + 1
64 Dot14 A = 3 * b;
65 Dot14 B = 3 * (c - 2 * b);
66 Dot14 C = 3 * (b - c) + Dot14_ONE;
67
68 // Now search for a t value given x
69 Dot14 t = Dot14_HALF;
70 Dot14 dt = Dot14_HALF;
71 for (int i = 0; i < 13; i++) {
72 dt >>= 1;
73 Dot14 guess = eval_cubic(t, A, B, C);
74 if (x < guess) {
75 t -= dt;
76 } else {
77 t += dt;
78 }
79 }
80
81 // Now we have t, so compute the coeff for Y and evaluate
82 b = pin_and_convert(by);
83 c = pin_and_convert(cy);
84 A = 3 * b;
85 B = 3 * (c - 2 * b);
86 C = 3 * (b - c) + Dot14_ONE;
87 return Dot14ToFloat(eval_cubic(t, A, B, C));
88 }
89
90 ///////////////////////////////////////////////////////////////////////////////////////////////////
91
SkiaInterpolatorBase()92 SkiaInterpolatorBase::SkiaInterpolatorBase() {
93 fStorage = nullptr;
94 fTimes = nullptr;
95 }
96
~SkiaInterpolatorBase()97 SkiaInterpolatorBase::~SkiaInterpolatorBase() {
98 if (fStorage) {
99 free(fStorage);
100 }
101 }
102
reset(int elemCount,int frameCount)103 void SkiaInterpolatorBase::reset(int elemCount, int frameCount) {
104 fFlags = 0;
105 fElemCount = static_cast<uint8_t>(elemCount);
106 fFrameCount = static_cast<int16_t>(frameCount);
107 fRepeat = 1.0f;
108 if (fStorage) {
109 free(fStorage);
110 fStorage = nullptr;
111 fTimes = nullptr;
112 }
113 }
114
115 /* Each value[] run is formatted as:
116 <time (in msec)>
117 <blend>
118 <data[fElemCount]>
119
120 Totaling fElemCount+2 entries per keyframe
121 */
122
getDuration(SkMSec * startTime,SkMSec * endTime) const123 bool SkiaInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const {
124 if (fFrameCount == 0) {
125 return false;
126 }
127
128 if (startTime) {
129 *startTime = fTimes[0].fTime;
130 }
131 if (endTime) {
132 *endTime = fTimes[fFrameCount - 1].fTime;
133 }
134 return true;
135 }
136
ComputeRelativeT(SkMSec time,SkMSec prevTime,SkMSec nextTime,const float blend[4])137 float SkiaInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime, SkMSec nextTime,
138 const float blend[4]) {
139 LOG_FATAL_IF(time < prevTime || time > nextTime);
140
141 float t = (float)(time - prevTime) / (float)(nextTime - prevTime);
142 return blend ? SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
143 }
144
145 // Returns the index of where the item is or the bit not of the index
146 // where the item should go in order to keep arr sorted in ascending order.
binarySearch(const SkTimeCode * arr,int count,SkMSec target)147 int SkiaInterpolatorBase::binarySearch(const SkTimeCode* arr, int count, SkMSec target) {
148 if (count <= 0) {
149 return ~0;
150 }
151
152 int lo = 0;
153 int hi = count - 1;
154
155 while (lo < hi) {
156 int mid = (hi + lo) / 2;
157 SkMSec elem = arr[mid].fTime;
158 if (elem == target) {
159 return mid;
160 } else if (elem < target) {
161 lo = mid + 1;
162 } else {
163 hi = mid;
164 }
165 }
166 // Check to see if target is greater or less than where we stopped
167 if (target < arr[lo].fTime) {
168 return ~lo;
169 }
170 // e.g. it should go at the end.
171 return ~(lo + 1);
172 }
173
timeToT(SkMSec time,float * T,int * indexPtr,bool * exactPtr) const174 SkiaInterpolatorBase::Result SkiaInterpolatorBase::timeToT(SkMSec time, float* T, int* indexPtr,
175 bool* exactPtr) const {
176 LOG_FATAL_IF(fFrameCount <= 0);
177 Result result = kNormal_Result;
178 if (fRepeat != 1.0f) {
179 SkMSec startTime = 0, endTime = 0; // initialize to avoid warning
180 this->getDuration(&startTime, &endTime);
181 SkMSec totalTime = endTime - startTime;
182 SkMSec offsetTime = time - startTime;
183 endTime = SkScalarFloorToInt(fRepeat * totalTime);
184 if (offsetTime >= endTime) {
185 float fraction = SkScalarFraction(fRepeat);
186 offsetTime = fraction == 0 && fRepeat > 0
187 ? totalTime
188 : (SkMSec)SkScalarFloorToInt(fraction * totalTime);
189 result = kFreezeEnd_Result;
190 } else {
191 int mirror = fFlags & kMirror;
192 offsetTime = offsetTime % (totalTime << mirror);
193 if (offsetTime > totalTime) { // can only be true if fMirror is true
194 offsetTime = (totalTime << 1) - offsetTime;
195 }
196 }
197 time = offsetTime + startTime;
198 }
199
200 int index = SkiaInterpolatorBase::binarySearch(fTimes, fFrameCount, time);
201 bool exact = true;
202 if (index < 0) {
203 index = ~index;
204 if (index == 0) {
205 result = kFreezeStart_Result;
206 } else if (index == fFrameCount) {
207 if (fFlags & kReset) {
208 index = 0;
209 } else {
210 index -= 1;
211 }
212 result = kFreezeEnd_Result;
213 } else {
214 // Need to interpolate between two frames.
215 exact = false;
216 }
217 }
218 LOG_FATAL_IF(index >= fFrameCount);
219 const SkTimeCode* nextTime = &fTimes[index];
220 SkMSec nextT = nextTime[0].fTime;
221 if (exact) {
222 *T = 0;
223 } else {
224 SkMSec prevT = nextTime[-1].fTime;
225 *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
226 }
227 *indexPtr = index;
228 *exactPtr = exact;
229 return result;
230 }
231
SkiaInterpolator()232 SkiaInterpolator::SkiaInterpolator() {
233 INHERITED::reset(0, 0);
234 fValues = nullptr;
235 }
236
SkiaInterpolator(int elemCount,int frameCount)237 SkiaInterpolator::SkiaInterpolator(int elemCount, int frameCount) {
238 LOG_FATAL_IF(elemCount <= 0);
239 this->reset(elemCount, frameCount);
240 }
241
reset(int elemCount,int frameCount)242 void SkiaInterpolator::reset(int elemCount, int frameCount) {
243 INHERITED::reset(elemCount, frameCount);
244 size_t numBytes = (sizeof(float) * elemCount + sizeof(SkTimeCode)) * frameCount;
245 fStorage = malloc(numBytes);
246 LOG_ALWAYS_FATAL_IF(!fStorage, "Failed to allocate %zu bytes in %s",
247 numBytes, __func__);
248 fTimes = (SkTimeCode*)fStorage;
249 fValues = (float*)((char*)fStorage + sizeof(SkTimeCode) * frameCount);
250 }
251
252 static const float gIdentityBlend[4] = {0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f};
253
setKeyFrame(int index,SkMSec time,const float values[],const float blend[4])254 bool SkiaInterpolator::setKeyFrame(int index, SkMSec time, const float values[],
255 const float blend[4]) {
256 LOG_FATAL_IF(values == nullptr);
257
258 if (blend == nullptr) {
259 blend = gIdentityBlend;
260 }
261
262 // Verify the time should go after all the frames before index
263 bool success = ~index == SkiaInterpolatorBase::binarySearch(fTimes, index, time);
264 LOG_FATAL_IF(!success);
265 if (success) {
266 SkTimeCode* timeCode = &fTimes[index];
267 timeCode->fTime = time;
268 memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
269 float* dst = &fValues[fElemCount * index];
270 memcpy(dst, values, fElemCount * sizeof(float));
271 }
272 return success;
273 }
274
timeToValues(SkMSec time,float values[]) const275 SkiaInterpolator::Result SkiaInterpolator::timeToValues(SkMSec time, float values[]) const {
276 float T;
277 int index;
278 bool exact;
279 Result result = timeToT(time, &T, &index, &exact);
280 if (values) {
281 const float* nextSrc = &fValues[index * fElemCount];
282
283 if (exact) {
284 memcpy(values, nextSrc, fElemCount * sizeof(float));
285 } else {
286 LOG_FATAL_IF(index <= 0);
287
288 const float* prevSrc = nextSrc - fElemCount;
289
290 for (int i = fElemCount - 1; i >= 0; --i) {
291 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
292 }
293 }
294 }
295 return result;
296 }
297