1 /**
2 * @file lv_math.c
3 *
4 */
5
6 /*********************
7 * INCLUDES
8 *********************/
9 #include "lv_math.h"
10 #include "../core/lv_global.h"
11
12 /*********************
13 * DEFINES
14 *********************/
15 #define rand_seed LV_GLOBAL_DEFAULT()->math_rand_seed
16
17 /**********************
18 * TYPEDEFS
19 **********************/
20
21 #define CUBIC_NEWTON_ITERATIONS 8
22 #define CUBIC_PRECISION_BITS 10 /* 10 or 14 bits recommended, int64_t calculation is used for >14bit precision */
23
24 #if CUBIC_PRECISION_BITS < 10 || CUBIC_PRECISION_BITS > 20
25 #error "cubic precision bits should be in range of [10, 20] for 32bit/64bit calculations."
26 #endif
27
28 /**********************
29 * STATIC PROTOTYPES
30 **********************/
31
32 /**********************
33 * STATIC VARIABLES
34 **********************/
35 static const uint16_t sin0_90_table[] = {
36 0, 572, 1144, 1715, 2286, 2856, 3425, 3993, 4560, 5126, 5690, 6252, 6813, 7371, 7927, 8481,
37 9032, 9580, 10126, 10668, 11207, 11743, 12275, 12803, 13328, 13848, 14365, 14876, 15384, 15886, 16384, 16877,
38 17364, 17847, 18324, 18795, 19261, 19720, 20174, 20622, 21063, 21498, 21926, 22348, 22763, 23170, 23571, 23965,
39 24351, 24730, 25102, 25466, 25822, 26170, 26510, 26842, 27166, 27482, 27789, 28088, 28378, 28660, 28932, 29197,
40 29452, 29698, 29935, 30163, 30382, 30592, 30792, 30983, 31164, 31336, 31499, 31651, 31795, 31928, 32052, 32166,
41 32270, 32365, 32449, 32524, 32588, 32643, 32688, 32723, 32748, 32763, 32768
42 };
43
44 /**********************
45 * MACROS
46 **********************/
47
48 /**********************
49 * GLOBAL FUNCTIONS
50 **********************/
51
lv_trigo_sin(int16_t angle)52 int32_t LV_ATTRIBUTE_FAST_MEM lv_trigo_sin(int16_t angle)
53 {
54 int32_t ret = 0;
55 while(angle < 0) angle += 360;
56 while(angle >= 360) angle -= 360;
57
58 if(angle < 90) {
59 ret = sin0_90_table[angle];
60 }
61 else if(angle >= 90 && angle < 180) {
62 angle = 180 - angle;
63 ret = sin0_90_table[angle];
64 }
65 else if(angle >= 180 && angle < 270) {
66 angle = angle - 180;
67 ret = -sin0_90_table[angle];
68 }
69 else { /*angle >=270*/
70 angle = 360 - angle;
71 ret = -sin0_90_table[angle];
72 }
73
74 if(ret == 32767) return 32768;
75 else if(ret == -32767) return -32768;
76 else return ret;
77 }
78
79 /**
80 * cubic-bezier Reference:
81 *
82 * https://github.com/gre/bezier-easing
83 * https://opensource.apple.com/source/WebCore/WebCore-955.66/platform/graphics/UnitBezier.h
84 *
85 * Copyright (c) 2014 Gaëtan Renaudeau
86 *
87 * Permission is hereby granted, free of charge, to any person
88 * obtaining a copy of this software and associated documentation
89 * files (the "Software"), to deal in the Software without
90 * restriction, including without limitation the rights to use,
91 * copy, modify, merge, publish, distribute, sublicense, and/or sell
92 * copies of the Software, and to permit persons to whom the
93 * Software is furnished to do so, subject to the following
94 * conditions:
95 *
96 * The above copyright notice and this permission notice shall be
97 * included in all copies or substantial portions of the Software.
98 *
99 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
100 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
101 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
102 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
103 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
104 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
105 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
106 * OTHER DEALINGS IN THE SOFTWARE.
107 *
108 */
109
do_cubic_bezier(int32_t t,int32_t a,int32_t b,int32_t c)110 static int32_t do_cubic_bezier(int32_t t, int32_t a, int32_t b, int32_t c)
111 {
112 /*a * t^3 + b * t^2 + c * t*/
113 #if CUBIC_PRECISION_BITS > 14
114 int64_t ret;
115 #else
116 int32_t ret;
117 #endif
118
119 ret = a;
120 ret = (ret * t) >> CUBIC_PRECISION_BITS;
121 ret = ((ret + b) * t) >> CUBIC_PRECISION_BITS;
122 ret = ((ret + c) * t) >> CUBIC_PRECISION_BITS;
123 return ret;
124 }
125
lv_cubic_bezier(int32_t x,int32_t x1,int32_t y1,int32_t x2,int32_t y2)126 int32_t lv_cubic_bezier(int32_t x, int32_t x1, int32_t y1, int32_t x2, int32_t y2)
127 {
128 int32_t ax, bx, cx, ay, by, cy;
129 int32_t tl, tr, t; /*t in cubic-bezier function, used for bisection */
130 int32_t xs; /*x sampled on curve */
131 #if CUBIC_PRECISION_BITS > 14
132 int64_t d; /*slope value at specified t*/
133 #else
134 int32_t d;
135 #endif
136
137 if(x == 0 || x == LV_BEZIER_VAL_MAX) return x;
138
139 /* input is always LV_BEZIER_VAL_SHIFT bit precision */
140
141 #if CUBIC_PRECISION_BITS != LV_BEZIER_VAL_SHIFT
142 x <<= CUBIC_PRECISION_BITS - LV_BEZIER_VAL_SHIFT;
143 x1 <<= CUBIC_PRECISION_BITS - LV_BEZIER_VAL_SHIFT;
144 x2 <<= CUBIC_PRECISION_BITS - LV_BEZIER_VAL_SHIFT;
145 y1 <<= CUBIC_PRECISION_BITS - LV_BEZIER_VAL_SHIFT;
146 y2 <<= CUBIC_PRECISION_BITS - LV_BEZIER_VAL_SHIFT;
147 #endif
148
149 cx = 3 * x1;
150 bx = 3 * (x2 - x1) - cx;
151 ax = (1L << CUBIC_PRECISION_BITS) - cx - bx;
152
153 cy = 3 * y1;
154 by = 3 * (y2 - y1) - cy;
155 ay = (1L << CUBIC_PRECISION_BITS) - cy - by;
156
157 /*Try Newton's method firstly */
158 t = x; /*Make a guess*/
159 for(int i = 0; i < CUBIC_NEWTON_ITERATIONS; i++) {
160 /*Check if x on curve at t matches input x*/
161 xs = do_cubic_bezier(t, ax, bx, cx) - x;
162 if(LV_ABS(xs) <= 1) goto found;
163
164 /* get slop at t, d = 3 * ax * t^2 + 2 * bx + t + cx */
165 d = ax; /* use 64bit operation if needed. */
166 d = (3 * d * t) >> CUBIC_PRECISION_BITS;
167 d = ((d + 2 * bx) * t) >> CUBIC_PRECISION_BITS;
168 d += cx;
169
170 if(LV_ABS(d) <= 1) break;
171
172 d = ((int64_t)xs * (1L << CUBIC_PRECISION_BITS)) / d;
173 if(d == 0) break; /*Reached precision limits*/
174 t -= d;
175 }
176
177 /*Fallback to bisection method for reliability*/
178 tl = 0, tr = 1L << CUBIC_PRECISION_BITS, t = x;
179
180 if(t < tl) {
181 t = tl;
182 goto found;
183 }
184
185 if(t > tr) {
186 t = tr;
187 goto found;
188 }
189
190 while(tl < tr) {
191 xs = do_cubic_bezier(t, ax, bx, cx);
192 if(LV_ABS(xs - x) <= 1) goto found;
193 x > xs ? (tl = t) : (tr = t);
194 t = (tr - tl) / 2 + tl;
195 if(t == tl) break;
196 }
197
198 /*Failed to find suitable t for given x, return a value anyway.*/
199 found:
200 /*Return y at t*/
201 #if CUBIC_PRECISION_BITS != LV_BEZIER_VAL_SHIFT
202 return do_cubic_bezier(t, ay, by, cy) >> (CUBIC_PRECISION_BITS - LV_BEZIER_VAL_SHIFT);
203 #else
204 return do_cubic_bezier(t, ay, by, cy);
205 #endif
206 }
207
lv_sqrt(uint32_t x,lv_sqrt_res_t * q,uint32_t mask)208 void LV_ATTRIBUTE_FAST_MEM lv_sqrt(uint32_t x, lv_sqrt_res_t * q, uint32_t mask)
209 {
210 x = x << 8; /*To get 4 bit precision. (sqrt(256) = 16 = 4 bit)*/
211
212 uint32_t root = 0;
213 uint32_t trial;
214 /*http://ww1.microchip.com/...en/AppNotes/91040a.pdf*/
215 do {
216 trial = root + mask;
217 if(trial * trial <= x) root = trial;
218 mask = mask >> 1;
219 } while(mask);
220
221 q->i = root >> 4;
222 q->f = (root & 0xf) << 4;
223 }
224
225 /*
226 // Alternative Integer Square Root function
227 // Contributors include Arne Steinarson for the basic approximation idea,
228 // Dann Corbit and Mathew Hendry for the first cut at the algorithm,
229 // Lawrence Kirby for the rearrangement, improvements and range optimization
230 // and Paul Hsieh for the round-then-adjust idea.
231 */
lv_sqrt32(uint32_t x)232 int32_t LV_ATTRIBUTE_FAST_MEM lv_sqrt32(uint32_t x)
233 {
234 static const unsigned char sqq_table[] = {
235 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57,
236 59, 61, 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83,
237 84, 86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102,
238 103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118,
239 119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132,
240 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145,
241 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, 156, 157,
242 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
243 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178,
244 179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188,
245 189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197,
246 198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205, 206, 206,
247 207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213, 214, 214, 215,
248 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223,
249 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231,
250 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
251 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246,
252 246, 247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253,
253 253, 254, 254, 255
254 };
255
256 int32_t xn;
257
258 if(x >= 0x10000)
259 if(x >= 0x1000000)
260 if(x >= 0x10000000)
261 if(x >= 0x40000000) {
262 if(x >= 65535UL * 65535UL)
263 return 65535;
264 xn = sqq_table[x >> 24] << 8;
265 }
266 else
267 xn = sqq_table[x >> 22] << 7;
268 else if(x >= 0x4000000)
269 xn = sqq_table[x >> 20] << 6;
270 else
271 xn = sqq_table[x >> 18] << 5;
272 else {
273 if(x >= 0x100000)
274 if(x >= 0x400000)
275 xn = sqq_table[x >> 16] << 4;
276 else
277 xn = sqq_table[x >> 14] << 3;
278 else if(x >= 0x40000)
279 xn = sqq_table[x >> 12] << 2;
280 else
281 xn = sqq_table[x >> 10] << 1;
282
283 goto nr1;
284 }
285 else if(x >= 0x100) {
286 if(x >= 0x1000)
287 if(x >= 0x4000)
288 xn = (sqq_table[x >> 8] >> 0) + 1;
289 else
290 xn = (sqq_table[x >> 6] >> 1) + 1;
291 else if(x >= 0x400)
292 xn = (sqq_table[x >> 4] >> 2) + 1;
293 else
294 xn = (sqq_table[x >> 2] >> 3) + 1;
295
296 goto adj;
297 }
298 else
299 return sqq_table[x] >> 4;
300
301 /* Run two iterations of the standard convergence formula */
302
303 xn = (xn + 1 + x / xn) / 2;
304 nr1:
305 xn = (xn + 1 + x / xn) / 2;
306 adj:
307
308 if(xn * xn > (int32_t)x) /* Correct rounding if necessary */
309 xn--;
310
311 return xn;
312 }
313
lv_atan2(int x,int y)314 uint16_t lv_atan2(int x, int y)
315 {
316 /**
317 * Fast XY vector to integer degree algorithm - Jan 2011 www.RomanBlack.com
318 * Converts any XY values including 0 to a degree value that should be
319 * within +/- 1 degree of the accurate value without needing
320 * large slow trig functions like ArcTan() or ArcCos().
321 * NOTE! at least one of the X or Y values must be non-zero!
322 * This is the full version, for all 4 quadrants and will generate
323 * the angle in integer degrees from 0-360.
324 * Any values of X and Y are usable including negative values provided
325 * they are between -1456 and 1456 so the 16bit multiply does not overflow.
326 */
327 unsigned char negflag;
328 unsigned char tempdegree;
329 unsigned char comp;
330 unsigned int degree; /*this will hold the result*/
331 unsigned int ux;
332 unsigned int uy;
333
334 /*Save the sign flags then remove signs and get XY as unsigned ints*/
335 negflag = 0;
336 if(x < 0) {
337 negflag += 0x01; /*x flag bit*/
338 x = (0 - x); /*is now +*/
339 }
340 ux = x; /*copy to unsigned var before multiply*/
341 if(y < 0) {
342 negflag += 0x02; /*y flag bit*/
343 y = (0 - y); /*is now +*/
344 }
345 uy = y; /*copy to unsigned var before multiply*/
346
347 /*1. Calc the scaled "degrees"*/
348 if(ux > uy) {
349 degree = (uy * 45) / ux; /*degree result will be 0-45 range*/
350 negflag += 0x10; /*octant flag bit*/
351 }
352 else {
353 degree = (ux * 45) / uy; /*degree result will be 0-45 range*/
354 }
355
356 /*2. Compensate for the 4 degree error curve*/
357 comp = 0;
358 tempdegree = degree; /*use an unsigned char for speed!*/
359 if(tempdegree > 22) { /*if top half of range*/
360 if(tempdegree <= 44) comp++;
361 if(tempdegree <= 41) comp++;
362 if(tempdegree <= 37) comp++;
363 if(tempdegree <= 32) comp++; /*max is 4 degrees compensated*/
364 }
365 else { /*else is lower half of range*/
366 if(tempdegree >= 2) comp++;
367 if(tempdegree >= 6) comp++;
368 if(tempdegree >= 10) comp++;
369 if(tempdegree >= 15) comp++; /*max is 4 degrees compensated*/
370 }
371 degree += comp; /*degree is now accurate to +/- 1 degree!*/
372
373 /*Invert degree if it was X>Y octant, makes 0-45 into 90-45*/
374 if(negflag & 0x10) degree = (90 - degree);
375
376 /*3. Degree is now 0-90 range for this quadrant,*/
377 /*need to invert it for whichever quadrant it was in*/
378 if(negflag & 0x02) { /*if -Y*/
379 if(negflag & 0x01) /*if -Y -X*/
380 degree = (180 + degree);
381 else /*else is -Y +X*/
382 degree = (180 - degree);
383 }
384 else { /*else is +Y*/
385 if(negflag & 0x01) /*if +Y -X*/
386 degree = (360 - degree);
387 }
388 return degree;
389 }
390
lv_pow(int64_t base,int8_t exp)391 int64_t lv_pow(int64_t base, int8_t exp)
392 {
393 int64_t result = 1;
394 while(exp) {
395 if(exp & 1)
396 result *= base;
397 exp >>= 1;
398 base *= base;
399 }
400
401 return result;
402 }
403
lv_map(int32_t x,int32_t min_in,int32_t max_in,int32_t min_out,int32_t max_out)404 int32_t lv_map(int32_t x, int32_t min_in, int32_t max_in, int32_t min_out, int32_t max_out)
405 {
406 if(max_in >= min_in && x >= max_in) return max_out;
407 if(max_in >= min_in && x <= min_in) return min_out;
408
409 if(max_in <= min_in && x <= max_in) return max_out;
410 if(max_in <= min_in && x >= min_in) return min_out;
411
412 /**
413 * The equation should be:
414 * ((x - min_in) * delta_out) / delta in) + min_out
415 * To avoid rounding error reorder the operations:
416 * (x - min_in) * (delta_out / delta_min) + min_out
417 */
418
419 int32_t delta_in = max_in - min_in;
420 int32_t delta_out = max_out - min_out;
421
422 return ((x - min_in) * delta_out) / delta_in + min_out;
423 }
424
lv_rand_set_seed(uint32_t seed)425 void lv_rand_set_seed(uint32_t seed)
426 {
427 rand_seed = seed;
428 }
429
lv_rand(uint32_t min,uint32_t max)430 uint32_t lv_rand(uint32_t min, uint32_t max)
431 {
432 /*Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs"*/
433 uint32_t x = rand_seed;
434 x ^= x << 13;
435 x ^= x >> 17;
436 x ^= x << 5;
437 rand_seed = x;
438
439 return (rand_seed % (max - min + 1)) + min;
440 }
441
lv_trigo_cos(int16_t angle)442 int32_t LV_ATTRIBUTE_FAST_MEM lv_trigo_cos(int16_t angle)
443 {
444 return lv_trigo_sin(angle + 90);
445 }
446
lv_bezier3(int32_t t,int32_t u0,uint32_t u1,int32_t u2,int32_t u3)447 int32_t lv_bezier3(int32_t t, int32_t u0, uint32_t u1, int32_t u2, int32_t u3)
448 {
449 LV_UNUSED(u0);
450 LV_UNUSED(u3);
451 return lv_cubic_bezier(t, 341, u1, 683, u2);
452 }
453
454 /**********************
455 * STATIC FUNCTIONS
456 **********************/
457
