Merge branch 'blender2.7'
[blender.git] / source / blender / blenlib / intern / math_base_inline.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  *
19  * The Original Code is: some of this file.
20  *
21  * */
22
23 /** \file \ingroup bli
24  */
25
26 #ifndef __MATH_BASE_INLINE_C__
27 #define __MATH_BASE_INLINE_C__
28
29 #include <float.h>
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <limits.h>
33
34 #ifdef __SSE2__
35 #  include <emmintrin.h>
36 #endif
37
38 #include "BLI_math_base.h"
39
40 /* copied from BLI_utildefines.h */
41 #ifdef __GNUC__
42 #  define UNLIKELY(x)     __builtin_expect(!!(x), 0)
43 #else
44 #  define UNLIKELY(x)     (x)
45 #endif
46
47 /* powf is really slow for raising to integer powers. */
48 MINLINE float pow2f(float x)
49 {
50         return x * x;
51 }
52 MINLINE float pow3f(float x)
53 {
54         return pow2f(x) * x;
55 }
56 MINLINE float pow4f(float x)
57 {
58         return pow2f(pow2f(x));
59 }
60 MINLINE float pow7f(float x)
61 {
62         return pow2f(pow3f(x)) * x;
63 }
64
65 MINLINE float sqrt3f(float f)
66 {
67         if      (UNLIKELY(f == 0.0f)) return 0.0f;
68         else if (UNLIKELY(f <  0.0f)) return -(float)(exp(log(-f) / 3.0));
69         else                          return  (float)(exp(log( f) / 3.0));
70 }
71
72 MINLINE double sqrt3d(double d)
73 {
74         if      (UNLIKELY(d == 0.0)) return 0.0;
75         else if (UNLIKELY(d <  0.0)) return -exp(log(-d) / 3.0);
76         else                         return  exp(log( d) / 3.0);
77 }
78
79 MINLINE float sqrtf_signed(float f)
80 {
81         return (f >= 0.0f) ? sqrtf(f) : -sqrtf(-f);
82 }
83
84 MINLINE float saacos(float fac)
85 {
86         if      (UNLIKELY(fac <= -1.0f)) return (float)M_PI;
87         else if (UNLIKELY(fac >=  1.0f)) return 0.0f;
88         else                             return acosf(fac);
89 }
90
91 MINLINE float saasin(float fac)
92 {
93         if      (UNLIKELY(fac <= -1.0f)) return (float)-M_PI / 2.0f;
94         else if (UNLIKELY(fac >=  1.0f)) return (float) M_PI / 2.0f;
95         else                             return asinf(fac);
96 }
97
98 MINLINE float sasqrt(float fac)
99 {
100         if (UNLIKELY(fac <= 0.0f)) return 0.0f;
101         else                       return sqrtf(fac);
102 }
103
104 MINLINE float saacosf(float fac)
105 {
106         if      (UNLIKELY(fac <= -1.0f)) return (float)M_PI;
107         else if (UNLIKELY(fac >=  1.0f)) return 0.0f;
108         else                             return acosf(fac);
109 }
110
111 MINLINE float saasinf(float fac)
112 {
113         if      (UNLIKELY(fac <= -1.0f)) return (float)-M_PI / 2.0f;
114         else if (UNLIKELY(fac >=  1.0f)) return (float) M_PI / 2.0f;
115         else                             return asinf(fac);
116 }
117
118 MINLINE float sasqrtf(float fac)
119 {
120         if (UNLIKELY(fac <= 0.0f)) return 0.0f;
121         else                       return sqrtf(fac);
122 }
123
124 MINLINE float interpf(float target, float origin, float fac)
125 {
126         return (fac * target) + (1.0f - fac) * origin;
127 }
128
129 /* used for zoom values*/
130 MINLINE float power_of_2(float val)
131 {
132         return (float)pow(2.0, ceil(log((double)val) / M_LN2));
133 }
134
135 MINLINE int is_power_of_2_i(int n)
136 {
137         return (n & (n - 1)) == 0;
138 }
139
140 MINLINE int power_of_2_max_i(int n)
141 {
142         if (is_power_of_2_i(n))
143                 return n;
144
145         do {
146                 n = n & (n - 1);
147         } while (!is_power_of_2_i(n));
148
149         return n * 2;
150 }
151
152 MINLINE int power_of_2_min_i(int n)
153 {
154         while (!is_power_of_2_i(n))
155                 n = n & (n - 1);
156
157         return n;
158 }
159
160 MINLINE unsigned int power_of_2_max_u(unsigned int x)
161 {
162         x -= 1;
163         x |= (x >>  1);
164         x |= (x >>  2);
165         x |= (x >>  4);
166         x |= (x >>  8);
167         x |= (x >> 16);
168         return x + 1;
169 }
170
171 MINLINE unsigned power_of_2_min_u(unsigned x)
172 {
173         x |= (x >>  1);
174         x |= (x >>  2);
175         x |= (x >>  4);
176         x |= (x >>  8);
177         x |= (x >> 16);
178         return x - (x >> 1);
179 }
180
181 /* rounding and clamping */
182
183 #define _round_clamp_fl_impl(arg, ty, min, max) { \
184         float r = floorf(arg + 0.5f); \
185         if      (UNLIKELY(r <= (float)min)) return (ty)min; \
186         else if (UNLIKELY(r >= (float)max)) return (ty)max; \
187         else return (ty)r; \
188 }
189
190 #define _round_clamp_db_impl(arg, ty, min, max) { \
191         double r = floor(arg + 0.5); \
192         if      (UNLIKELY(r <= (double)min)) return (ty)min; \
193         else if (UNLIKELY(r >= (double)max)) return (ty)max; \
194         else return (ty)r; \
195 }
196
197 #define _round_fl_impl(arg, ty) { return (ty)floorf(arg + 0.5f); }
198 #define _round_db_impl(arg, ty) { return (ty)floor(arg + 0.5); }
199
200 MINLINE signed char    round_fl_to_char(float a) { _round_fl_impl(a, signed char) }
201 MINLINE unsigned char  round_fl_to_uchar(float a) { _round_fl_impl(a, unsigned char) }
202 MINLINE short          round_fl_to_short(float a) { _round_fl_impl(a, short) }
203 MINLINE unsigned short round_fl_to_ushort(float a) { _round_fl_impl(a, unsigned short) }
204 MINLINE int            round_fl_to_int(float a) { _round_fl_impl(a, int) }
205 MINLINE unsigned int   round_fl_to_uint(float a) { _round_fl_impl(a, unsigned int) }
206
207 MINLINE signed char    round_db_to_char(double a) { _round_db_impl(a, signed char) }
208 MINLINE unsigned char  round_db_to_uchar(double a) { _round_db_impl(a, unsigned char) }
209 MINLINE short          round_db_to_short(double a) { _round_db_impl(a, short) }
210 MINLINE unsigned short round_db_to_ushort(double a) { _round_db_impl(a, unsigned short) }
211 MINLINE int            round_db_to_int(double a) { _round_db_impl(a, int) }
212 MINLINE unsigned int   round_db_to_uint(double a) { _round_db_impl(a, unsigned int) }
213
214 #undef _round_fl_impl
215 #undef _round_db_impl
216
217 MINLINE signed char    round_fl_to_char_clamp(float a) { _round_clamp_fl_impl(a, signed char, SCHAR_MIN, SCHAR_MAX) }
218 MINLINE unsigned char  round_fl_to_uchar_clamp(float a) { _round_clamp_fl_impl(a, unsigned char, 0, UCHAR_MAX) }
219 MINLINE short          round_fl_to_short_clamp(float a) { _round_clamp_fl_impl(a, short, SHRT_MIN, SHRT_MAX) }
220 MINLINE unsigned short round_fl_to_ushort_clamp(float a) { _round_clamp_fl_impl(a, unsigned short, 0, USHRT_MAX) }
221 MINLINE int            round_fl_to_int_clamp(float a) { _round_clamp_fl_impl(a, int, INT_MIN, INT_MAX) }
222 MINLINE unsigned int   round_fl_to_uint_clamp(float a) { _round_clamp_fl_impl(a, unsigned int, 0, UINT_MAX) }
223
224 MINLINE signed char    round_db_to_char_clamp(double a) { _round_clamp_db_impl(a, signed char, SCHAR_MIN, SCHAR_MAX) }
225 MINLINE unsigned char  round_db_to_uchar_clamp(double a) { _round_clamp_db_impl(a, unsigned char, 0, UCHAR_MAX) }
226 MINLINE short          round_db_to_short_clamp(double a) { _round_clamp_db_impl(a, short, SHRT_MIN, SHRT_MAX) }
227 MINLINE unsigned short round_db_to_ushort_clamp(double a) { _round_clamp_db_impl(a, unsigned short, 0, USHRT_MAX) }
228 MINLINE int            round_db_to_int_clamp(double a) { _round_clamp_db_impl(a, int, INT_MIN, INT_MAX) }
229 MINLINE unsigned int   round_db_to_uint_clamp(double a) { _round_clamp_db_impl(a, unsigned int, 0, UINT_MAX) }
230
231 #undef _round_clamp_fl_impl
232 #undef _round_clamp_db_impl
233
234 /* integer division that rounds 0.5 up, particularly useful for color blending
235  * with integers, to avoid gradual darkening when rounding down */
236 MINLINE int divide_round_i(int a, int b)
237 {
238         return (2 * a + b) / (2 * b);
239 }
240
241 /**
242  * Integer division that floors negative result.
243  * \note This works like Python's int division.
244  */
245 MINLINE int divide_floor_i(int a, int b)
246 {
247         int d = a / b;
248         int r = a % b;  /* Optimizes into a single division. */
249         return r ? d - ((a < 0) ^ (b < 0)) : d;
250 }
251
252 /**
253  * modulo that handles negative numbers, works the same as Python's.
254  */
255 MINLINE int mod_i(int i, int n)
256 {
257         return (i % n + n) % n;
258 }
259
260 MINLINE float min_ff(float a, float b)
261 {
262         return (a < b) ? a : b;
263 }
264 MINLINE float max_ff(float a, float b)
265 {
266         return (a > b) ? a : b;
267 }
268
269 MINLINE int min_ii(int a, int b)
270 {
271         return (a < b) ? a : b;
272 }
273 MINLINE int max_ii(int a, int b)
274 {
275         return (b < a) ? a : b;
276 }
277
278 MINLINE float min_fff(float a, float b, float c)
279 {
280         return min_ff(min_ff(a, b), c);
281 }
282 MINLINE float max_fff(float a, float b, float c)
283 {
284         return max_ff(max_ff(a, b), c);
285 }
286
287 MINLINE int min_iii(int a, int b, int c)
288 {
289         return min_ii(min_ii(a, b), c);
290 }
291 MINLINE int max_iii(int a, int b, int c)
292 {
293         return max_ii(max_ii(a, b), c);
294 }
295
296 MINLINE float min_ffff(float a, float b, float c, float d)
297 {
298         return min_ff(min_fff(a, b, c), d);
299 }
300 MINLINE float max_ffff(float a, float b, float c, float d)
301 {
302         return max_ff(max_fff(a, b, c), d);
303 }
304
305 MINLINE int min_iiii(int a, int b, int c, int d)
306 {
307         return min_ii(min_iii(a, b, c), d);
308 }
309 MINLINE int max_iiii(int a, int b, int c, int d)
310 {
311         return max_ii(max_iii(a, b, c), d);
312 }
313
314 MINLINE size_t min_zz(size_t a, size_t b)
315 {
316         return (a < b) ? a : b;
317 }
318 MINLINE size_t max_zz(size_t a, size_t b)
319 {
320         return (b < a) ? a : b;
321 }
322
323 MINLINE int clamp_i(int value, int min, int max)
324 {
325         return min_ii(max_ii(value, min), max);
326 }
327
328 MINLINE float clamp_f(float value, float min, float max)
329 {
330         if (value > max) {
331                 return max;
332         }
333         else if (value < min) {
334                 return min;
335         }
336         return value;
337 }
338
339 MINLINE size_t clamp_z(size_t value, size_t min, size_t max)
340 {
341         return min_zz(max_zz(value, min), max);
342 }
343
344 /**
345  * Almost-equal for IEEE floats, using absolute difference method.
346  *
347  * \param max_diff: the maximum absolute difference.
348  */
349 MINLINE int compare_ff(float a, float b, const float max_diff)
350 {
351         return fabsf(a - b) <= max_diff;
352 }
353
354 /**
355  * Almost-equal for IEEE floats, using their integer representation (mixing ULP and absolute difference methods).
356  *
357  * \param max_diff: is the maximum absolute difference (allows to take care of the near-zero area,
358  *                 where relative difference methods cannot really work).
359  * \param max_ulps: is the 'maximum number of floats + 1' allowed between \a a and \a b to consider them equal.
360  *
361  * \see https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
362  */
363 MINLINE int compare_ff_relative(float a, float b, const float max_diff, const int max_ulps)
364 {
365         union {float f; int i;} ua, ub;
366
367         BLI_assert(sizeof(float) == sizeof(int));
368         BLI_assert(max_ulps < (1 << 22));
369
370         if (fabsf(a - b) <= max_diff) {
371                 return 1;
372         }
373
374         ua.f = a;
375         ub.f = b;
376
377         /* Important to compare sign from integers, since (-0.0f < 0) is false
378          * (though this shall not be an issue in common cases)... */
379         return ((ua.i < 0) != (ub.i < 0)) ? 0 : (abs(ua.i - ub.i) <= max_ulps) ? 1 : 0;
380 }
381
382 MINLINE float signf(float f)
383 {
384         return (f < 0.f) ? -1.f : 1.f;
385 }
386
387 MINLINE int signum_i_ex(float a, float eps)
388 {
389         if (a >  eps) return  1;
390         if (a < -eps) return -1;
391         else          return  0;
392 }
393
394 MINLINE int signum_i(float a)
395 {
396         if (a > 0.0f) return  1;
397         if (a < 0.0f) return -1;
398         else          return  0;
399 }
400
401 /** Returns number of (base ten) *significant* digits of integer part of given float
402  * (negative in case of decimal-only floats, 0.01 returns -1 e.g.). */
403 MINLINE int integer_digits_f(const float f)
404 {
405         return (f == 0.0f) ? 0 : (int)floor(log10(fabs(f))) + 1;
406 }
407
408 /** Returns number of (base ten) *significant* digits of integer part of given double
409  * (negative in case of decimal-only floats, 0.01 returns -1 e.g.). */
410 MINLINE int integer_digits_d(const double d)
411 {
412         return (d == 0.0) ? 0 : (int)floor(log10(fabs(d))) + 1;
413 }
414
415 MINLINE int integer_digits_i(const int i)
416 {
417         return (int)log10((double)i) + 1;
418 }
419
420 /* Internal helpers for SSE2 implementation.
421  *
422  * NOTE: Are to be called ONLY from inside `#ifdef __SSE2__` !!!
423  */
424
425 #ifdef __SSE2__
426
427 /* Calculate initial guess for arg^exp based on float representation
428  * This method gives a constant bias, which can be easily compensated by
429  * multiplicating with bias_coeff.
430  * Gives better results for exponents near 1 (e. g. 4/5).
431  * exp = exponent, encoded as uint32_t
432  * e2coeff = 2^(127/exponent - 127) * bias_coeff^(1/exponent), encoded as
433  * uint32_t
434  *
435  * We hope that exp and e2coeff gets properly inlined
436  */
437 MALWAYS_INLINE __m128 _bli_math_fastpow(const int exp,
438                                         const int e2coeff,
439                                         const __m128 arg)
440 {
441         __m128 ret;
442         ret = _mm_mul_ps(arg, _mm_castsi128_ps(_mm_set1_epi32(e2coeff)));
443         ret = _mm_cvtepi32_ps(_mm_castps_si128(ret));
444         ret = _mm_mul_ps(ret, _mm_castsi128_ps(_mm_set1_epi32(exp)));
445         ret = _mm_castsi128_ps(_mm_cvtps_epi32(ret));
446         return ret;
447 }
448
449 /* Improve x ^ 1.0f/5.0f solution with Newton-Raphson method */
450 MALWAYS_INLINE __m128 _bli_math_improve_5throot_solution(
451     const __m128 old_result,
452     const __m128 x)
453 {
454         __m128 approx2 = _mm_mul_ps(old_result, old_result);
455         __m128 approx4 = _mm_mul_ps(approx2, approx2);
456         __m128 t = _mm_div_ps(x, approx4);
457         __m128 summ = _mm_add_ps(_mm_mul_ps(_mm_set1_ps(4.0f), old_result), t); /* fma */
458         return _mm_mul_ps(summ, _mm_set1_ps(1.0f / 5.0f));
459 }
460
461 /* Calculate powf(x, 2.4). Working domain: 1e-10 < x < 1e+10 */
462 MALWAYS_INLINE __m128 _bli_math_fastpow24(const __m128 arg)
463 {
464         /* max, avg and |avg| errors were calculated in gcc without FMA instructions
465          * The final precision should be better than powf in glibc */
466
467         /* Calculate x^4/5, coefficient 0.994 was constructed manually to minimize
468          * avg error.
469          */
470         /* 0x3F4CCCCD = 4/5 */
471         /* 0x4F55A7FB = 2^(127/(4/5) - 127) * 0.994^(1/(4/5)) */
472         /* error max = 0.17, avg = 0.0018, |avg| = 0.05 */
473         __m128 x = _bli_math_fastpow(0x3F4CCCCD, 0x4F55A7FB, arg);
474         __m128 arg2 = _mm_mul_ps(arg, arg);
475         __m128 arg4 = _mm_mul_ps(arg2, arg2);
476         /* error max = 0.018        avg = 0.0031    |avg| = 0.0031  */
477         x = _bli_math_improve_5throot_solution(x, arg4);
478         /* error max = 0.00021    avg = 1.6e-05    |avg| = 1.6e-05 */
479         x = _bli_math_improve_5throot_solution(x, arg4);
480         /* error max = 6.1e-07    avg = 5.2e-08    |avg| = 1.1e-07 */
481         x = _bli_math_improve_5throot_solution(x, arg4);
482         return _mm_mul_ps(x, _mm_mul_ps(x, x));
483 }
484
485 /* Calculate powf(x, 1.0f / 2.4) */
486 MALWAYS_INLINE __m128 _bli_math_fastpow512(const __m128 arg)
487 {
488         /* 5/12 is too small, so compute the 4th root of 20/12 instead.
489          * 20/12 = 5/3 = 1 + 2/3 = 2 - 1/3. 2/3 is a suitable argument for fastpow.
490          * weighting coefficient: a^-1/2 = 2 a; a = 2^-2/3
491          */
492         __m128 xf = _bli_math_fastpow(0x3f2aaaab, 0x5eb504f3, arg);
493         __m128 xover = _mm_mul_ps(arg, xf);
494         __m128 xfm1 = _mm_rsqrt_ps(xf);
495         __m128 x2 = _mm_mul_ps(arg, arg);
496         __m128 xunder = _mm_mul_ps(x2, xfm1);
497         /* sqrt2 * over + 2 * sqrt2 * under */
498         __m128 xavg = _mm_mul_ps(_mm_set1_ps(1.0f / (3.0f * 0.629960524947437f) * 0.999852f),
499                                  _mm_add_ps(xover, xunder));
500         xavg = _mm_mul_ps(xavg, _mm_rsqrt_ps(xavg));
501         xavg = _mm_mul_ps(xavg, _mm_rsqrt_ps(xavg));
502         return xavg;
503 }
504
505 MALWAYS_INLINE __m128 _bli_math_blend_sse(const __m128 mask,
506                                           const __m128 a,
507                                           const __m128 b)
508 {
509         return _mm_or_ps(_mm_and_ps(mask, a), _mm_andnot_ps(mask, b));
510 }
511
512 #endif  /* __SSE2__ */
513
514 /* Low level conversion functions */
515 MINLINE unsigned char unit_float_to_uchar_clamp(float val)
516 {
517         return (unsigned char)(((val <= 0.0f) ? 0 : ((val > (1.0f - 0.5f / 255.0f)) ? 255 : ((255.0f * val) + 0.5f))));
518 }
519 #define unit_float_to_uchar_clamp(val) ((CHECK_TYPE_INLINE(val, float)), unit_float_to_uchar_clamp(val))
520
521 MINLINE unsigned short unit_float_to_ushort_clamp(float val)
522 {
523         return (unsigned short)((val >= 1.0f - 0.5f / 65535) ? 65535 : (val <= 0.0f) ? 0 : (val * 65535.0f + 0.5f));
524 }
525 #define unit_float_to_ushort_clamp(val) ((CHECK_TYPE_INLINE(val, float)), unit_float_to_ushort_clamp(val))
526
527 MINLINE unsigned char unit_ushort_to_uchar(unsigned short val)
528 {
529         return (unsigned char)(((val) >= 65535 - 128) ? 255 : ((val) + 128) >> 8);
530 }
531 #define unit_ushort_to_uchar(val) ((CHECK_TYPE_INLINE(val, unsigned short)), unit_ushort_to_uchar(val))
532
533 #define unit_float_to_uchar_clamp_v3(v1, v2) {                                              \
534         (v1)[0] = unit_float_to_uchar_clamp((v2[0]));                                           \
535         (v1)[1] = unit_float_to_uchar_clamp((v2[1]));                                           \
536         (v1)[2] = unit_float_to_uchar_clamp((v2[2]));                                           \
537 } ((void)0)
538 #define unit_float_to_uchar_clamp_v4(v1, v2) {                                              \
539         (v1)[0] = unit_float_to_uchar_clamp((v2[0]));                                           \
540         (v1)[1] = unit_float_to_uchar_clamp((v2[1]));                                           \
541         (v1)[2] = unit_float_to_uchar_clamp((v2[2]));                                           \
542         (v1)[3] = unit_float_to_uchar_clamp((v2[3]));                                           \
543 } ((void)0)
544
545 #endif /* __MATH_BASE_INLINE_C__ */