diff options
-rw-r--r-- | external/libfixmath/LICENSE | 20 | ||||
-rw-r--r-- | external/libfixmath/fix16.c | 511 | ||||
-rw-r--r-- | external/libfixmath/fix16.h | 333 | ||||
-rw-r--r-- | external/libfixmath/int64.h | 177 | ||||
-rw-r--r-- | readlicense_oo/license/license.xml | 27 | ||||
-rw-r--r-- | solenv/clang-format/excludelist | 3 | ||||
-rw-r--r-- | vcl/Library_vcl.mk | 2 | ||||
-rw-r--r-- | vcl/source/fontsubset/fixmath.c | 13 | ||||
-rw-r--r-- | vcl/source/fontsubset/fixmath.h | 23 | ||||
-rw-r--r-- | vcl/source/fontsubset/sft.cxx | 40 |
10 files changed, 1112 insertions, 37 deletions
diff --git a/external/libfixmath/LICENSE b/external/libfixmath/LICENSE new file mode 100644 index 000000000000..cf0aefe08af4 --- /dev/null +++ b/external/libfixmath/LICENSE @@ -0,0 +1,20 @@ +libfixmath is Copyright (c) 2011-2021 Flatmush <Flatmush@gmail.com>, +Petteri Aimonen <Petteri.Aimonen@gmail.com>, & libfixmath AUTHORS + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/external/libfixmath/fix16.c b/external/libfixmath/fix16.c new file mode 100644 index 000000000000..053f6794f4b2 --- /dev/null +++ b/external/libfixmath/fix16.c @@ -0,0 +1,511 @@ +#include "fix16.h" +#include "int64.h" + + +/* Subtraction and addition with overflow detection. + * The versions without overflow detection are inlined in the header. + */ +#ifndef FIXMATH_NO_OVERFLOW +fix16_t fix16_add(fix16_t a, fix16_t b) +{ + // Use unsigned integers because overflow with signed integers is + // an undefined operation (http://www.airs.com/blog/archives/120). + uint32_t _a = a; + uint32_t _b = b; + uint32_t sum = _a + _b; + + // Overflow can only happen if sign of a == sign of b, and then + // it causes sign of sum != sign of a. + if (!((_a ^ _b) & 0x80000000) && ((_a ^ sum) & 0x80000000)) + return fix16_overflow; + + return sum; +} + +fix16_t fix16_sub(fix16_t a, fix16_t b) +{ + uint32_t _a = a; + uint32_t _b = b; + uint32_t diff = _a - _b; + + // Overflow can only happen if sign of a != sign of b, and then + // it causes sign of diff != sign of a. + if (((_a ^ _b) & 0x80000000) && ((_a ^ diff) & 0x80000000)) + return fix16_overflow; + + return diff; +} + +/* Saturating arithmetic */ +fix16_t fix16_sadd(fix16_t a, fix16_t b) +{ + fix16_t result = fix16_add(a, b); + + if (result == fix16_overflow) + return (a >= 0) ? fix16_maximum : fix16_minimum; + + return result; +} + +fix16_t fix16_ssub(fix16_t a, fix16_t b) +{ + fix16_t result = fix16_sub(a, b); + + if (result == fix16_overflow) + return (a >= 0) ? fix16_maximum : fix16_minimum; + + return result; +} +#endif + + + +/* 64-bit implementation for fix16_mul. Fastest version for e.g. ARM Cortex M3. + * Performs a 32*32 -> 64bit multiplication. The middle 32 bits are the result, + * bottom 16 bits are used for rounding, and upper 16 bits are used for overflow + * detection. + */ + +#if !defined(FIXMATH_NO_64BIT) && !defined(FIXMATH_OPTIMIZE_8BIT) +fix16_t fix16_mul(fix16_t inArg0, fix16_t inArg1) +{ + int64_t product = (int64_t)inArg0 * inArg1; + + #ifndef FIXMATH_NO_OVERFLOW + // The upper 17 bits should all be the same (the sign). + uint32_t upper = (product >> 47); + #endif + + if (product < 0) + { + #ifndef FIXMATH_NO_OVERFLOW + if (~upper) + return fix16_overflow; + #endif + + #ifndef FIXMATH_NO_ROUNDING + // This adjustment is required in order to round -1/2 correctly + product--; + #endif + } + else + { + #ifndef FIXMATH_NO_OVERFLOW + if (upper) + return fix16_overflow; + #endif + } + + #ifdef FIXMATH_NO_ROUNDING + return product >> 16; + #else + fix16_t result = product >> 16; + result += (product & 0x8000) >> 15; + + return result; + #endif +} +#endif + +/* 32-bit implementation of fix16_mul. Potentially fast on 16-bit processors, + * and this is a relatively good compromise for compilers that do not support + * uint64_t. Uses 16*16->32bit multiplications. + */ +#if defined(FIXMATH_NO_64BIT) && !defined(FIXMATH_OPTIMIZE_8BIT) +fix16_t fix16_mul(fix16_t inArg0, fix16_t inArg1) +{ + // Each argument is divided to 16-bit parts. + // AB + // * CD + // ----------- + // BD 16 * 16 -> 32 bit products + // CB + // AD + // AC + // |----| 64 bit product + int32_t A = (inArg0 >> 16), C = (inArg1 >> 16); + uint32_t B = (inArg0 & 0xFFFF), D = (inArg1 & 0xFFFF); + + int32_t AC = A*C; + int32_t AD_CB = A*D + C*B; + uint32_t BD = B*D; + + int32_t product_hi = AC + (AD_CB >> 16); + + // Handle carry from lower 32 bits to upper part of result. + uint32_t ad_cb_temp = AD_CB << 16; + uint32_t product_lo = BD + ad_cb_temp; + if (product_lo < BD) + product_hi++; + +#ifndef FIXMATH_NO_OVERFLOW + // The upper 17 bits should all be the same (the sign). + if (product_hi >> 31 != product_hi >> 15) + return fix16_overflow; +#endif + +#ifdef FIXMATH_NO_ROUNDING + return (product_hi << 16) | (product_lo >> 16); +#else + // Subtracting 0x8000 (= 0.5) and then using signed right shift + // achieves proper rounding to result-1, except in the corner + // case of negative numbers and lowest word = 0x8000. + // To handle that, we also have to subtract 1 for negative numbers. + uint32_t product_lo_tmp = product_lo; + product_lo -= 0x8000; + product_lo -= (uint32_t)product_hi >> 31; + if (product_lo > product_lo_tmp) + product_hi--; + + // Discard the lowest 16 bits. Note that this is not exactly the same + // as dividing by 0x10000. For example if product = -1, result will + // also be -1 and not 0. This is compensated by adding +1 to the result + // and compensating this in turn in the rounding above. + fix16_t result = (product_hi << 16) | (product_lo >> 16); + result += 1; + return result; +#endif +} +#endif + +/* 8-bit implementation of fix16_mul. Fastest on e.g. Atmel AVR. + * Uses 8*8->16bit multiplications, and also skips any bytes that + * are zero. + */ +#if defined(FIXMATH_OPTIMIZE_8BIT) +fix16_t fix16_mul(fix16_t inArg0, fix16_t inArg1) +{ + uint32_t _a = fix_abs(inArg0); + uint32_t _b = fix_abs(inArg1); + + uint8_t va[4] = {_a, (_a >> 8), (_a >> 16), (_a >> 24)}; + uint8_t vb[4] = {_b, (_b >> 8), (_b >> 16), (_b >> 24)}; + + uint32_t low = 0; + uint32_t mid = 0; + + // Result column i depends on va[0..i] and vb[i..0] + + #ifndef FIXMATH_NO_OVERFLOW + // i = 6 + if (va[3] && vb[3]) return fix16_overflow; + #endif + + // i = 5 + if (va[2] && vb[3]) mid += (uint16_t)va[2] * vb[3]; + if (va[3] && vb[2]) mid += (uint16_t)va[3] * vb[2]; + mid <<= 8; + + // i = 4 + if (va[1] && vb[3]) mid += (uint16_t)va[1] * vb[3]; + if (va[2] && vb[2]) mid += (uint16_t)va[2] * vb[2]; + if (va[3] && vb[1]) mid += (uint16_t)va[3] * vb[1]; + + #ifndef FIXMATH_NO_OVERFLOW + if (mid & 0xFF000000) return fix16_overflow; + #endif + mid <<= 8; + + // i = 3 + if (va[0] && vb[3]) mid += (uint16_t)va[0] * vb[3]; + if (va[1] && vb[2]) mid += (uint16_t)va[1] * vb[2]; + if (va[2] && vb[1]) mid += (uint16_t)va[2] * vb[1]; + if (va[3] && vb[0]) mid += (uint16_t)va[3] * vb[0]; + + #ifndef FIXMATH_NO_OVERFLOW + if (mid & 0xFF000000) return fix16_overflow; + #endif + mid <<= 8; + + // i = 2 + if (va[0] && vb[2]) mid += (uint16_t)va[0] * vb[2]; + if (va[1] && vb[1]) mid += (uint16_t)va[1] * vb[1]; + if (va[2] && vb[0]) mid += (uint16_t)va[2] * vb[0]; + + // i = 1 + if (va[0] && vb[1]) low += (uint16_t)va[0] * vb[1]; + if (va[1] && vb[0]) low += (uint16_t)va[1] * vb[0]; + low <<= 8; + + // i = 0 + if (va[0] && vb[0]) low += (uint16_t)va[0] * vb[0]; + + #ifndef FIXMATH_NO_ROUNDING + low += 0x8000; + #endif + mid += (low >> 16); + + #ifndef FIXMATH_NO_OVERFLOW + if (mid & 0x80000000) + return fix16_overflow; + #endif + + fix16_t result = mid; + + /* Figure out the sign of result */ + if ((inArg0 >= 0) != (inArg1 >= 0)) + { + result = -result; + } + + return result; +} +#endif + +#ifndef FIXMATH_NO_OVERFLOW +/* Wrapper around fix16_mul to add saturating arithmetic. */ +fix16_t fix16_smul(fix16_t inArg0, fix16_t inArg1) +{ + fix16_t result = fix16_mul(inArg0, inArg1); + + if (result == fix16_overflow) + { + if ((inArg0 >= 0) == (inArg1 >= 0)) + return fix16_maximum; + else + return fix16_minimum; + } + + return result; +} +#endif + +/* 32-bit implementation of fix16_div. Fastest version for e.g. ARM Cortex M3. + * Performs 32-bit divisions repeatedly to reduce the remainder. For this to + * be efficient, the processor has to have 32-bit hardware division. + */ +#if !defined(FIXMATH_OPTIMIZE_8BIT) +#ifdef __GNUC__ +// Count leading zeros, using processor-specific instruction if available. +#define clz(x) (__builtin_clzl(x) - (8 * sizeof(long) - 32)) +#else +static uint8_t clz(uint32_t x) +{ + uint8_t result = 0; + if (x == 0) return 32; + while (!(x & 0xF0000000)) { result += 4; x <<= 4; } + while (!(x & 0x80000000)) { result += 1; x <<= 1; } + return result; +} +#endif + +fix16_t fix16_div(fix16_t a, fix16_t b) +{ + // This uses a hardware 32/32 bit division multiple times, until we have + // computed all the bits in (a<<17)/b. Usually this takes 1-3 iterations. + + if (b == 0) + return fix16_minimum; + + uint32_t remainder = fix_abs(a); + uint32_t divider = fix_abs(b); + uint64_t quotient = 0; + int bit_pos = 17; + + // Kick-start the division a bit. + // This improves speed in the worst-case scenarios where N and D are large + // It gets a lower estimate for the result by N/(D >> 17 + 1). + if (divider & 0xFFF00000) + { + uint32_t shifted_div = ((divider >> 17) + 1); + quotient = remainder / shifted_div; + uint64_t tmp = ((uint64_t)quotient * (uint64_t)divider) >> 17; + remainder -= (uint32_t)(tmp); + } + + // If the divider is divisible by 2^n, take advantage of it. + while (!(divider & 0xF) && bit_pos >= 4) + { + divider >>= 4; + bit_pos -= 4; + } + + while (remainder && bit_pos >= 0) + { + // Shift remainder as much as we can without overflowing + int shift = clz(remainder); + if (shift > bit_pos) shift = bit_pos; + remainder <<= shift; + bit_pos -= shift; + + uint32_t div = remainder / divider; + remainder = remainder % divider; + quotient += (uint64_t)div << bit_pos; + + #ifndef FIXMATH_NO_OVERFLOW + if (div & ~(0xFFFFFFFF >> bit_pos)) + return fix16_overflow; + #endif + + remainder <<= 1; + bit_pos--; + } + + #ifndef FIXMATH_NO_ROUNDING + // Quotient is always positive so rounding is easy + quotient++; + #endif + + fix16_t result = quotient >> 1; + + // Figure out the sign of the result + if ((a ^ b) & 0x80000000) + { + #ifndef FIXMATH_NO_OVERFLOW + if (result == fix16_minimum) + return fix16_overflow; + #endif + + result = -result; + } + + return result; +} +#endif + +/* Alternative 32-bit implementation of fix16_div. Fastest on e.g. Atmel AVR. + * This does the division manually, and is therefore good for processors that + * do not have hardware division. + */ +#if defined(FIXMATH_OPTIMIZE_8BIT) +fix16_t fix16_div(fix16_t a, fix16_t b) +{ + // This uses the basic binary restoring division algorithm. + // It appears to be faster to do the whole division manually than + // trying to compose a 64-bit divide out of 32-bit divisions on + // platforms without hardware divide. + + if (b == 0) + return fix16_minimum; + + uint32_t remainder = fix_abs(a); + uint32_t divider = fix_abs(b); + + uint32_t quotient = 0; + uint32_t bit = 0x10000; + + /* The algorithm requires D >= R */ + while (divider < remainder) + { + divider <<= 1; + bit <<= 1; + } + + #ifndef FIXMATH_NO_OVERFLOW + if (!bit) + return fix16_overflow; + #endif + + if (divider & 0x80000000) + { + // Perform one step manually to avoid overflows later. + // We know that divider's bottom bit is 0 here. + if (remainder >= divider) + { + quotient |= bit; + remainder -= divider; + } + divider >>= 1; + bit >>= 1; + } + + /* Main division loop */ + while (bit && remainder) + { + if (remainder >= divider) + { + quotient |= bit; + remainder -= divider; + } + + remainder <<= 1; + bit >>= 1; + } + + #ifndef FIXMATH_NO_ROUNDING + if (remainder >= divider) + { + quotient++; + } + #endif + + fix16_t result = quotient; + + /* Figure out the sign of result */ + if ((a ^ b) & 0x80000000) + { + #ifndef FIXMATH_NO_OVERFLOW + if (result == fix16_minimum) + return fix16_overflow; + #endif + + result = -result; + } + + return result; +} +#endif + +#ifndef FIXMATH_NO_OVERFLOW +/* Wrapper around fix16_div to add saturating arithmetic. */ +fix16_t fix16_sdiv(fix16_t inArg0, fix16_t inArg1) +{ + fix16_t result = fix16_div(inArg0, inArg1); + + if (result == fix16_overflow) + { + if ((inArg0 >= 0) == (inArg1 >= 0)) + return fix16_maximum; + else + return fix16_minimum; + } + + return result; +} +#endif + +fix16_t fix16_mod(fix16_t x, fix16_t y) +{ + #ifdef FIXMATH_OPTIMIZE_8BIT + /* The reason we do this, rather than use a modulo operator + * is that if you don't have a hardware divider, this will result + * in faster operations when the angles are close to the bounds. + */ + while(x >= y) x -= y; + while(x <= -y) x += y; + #else + /* Note that in C90, the sign of result of the modulo operation is + * undefined. in C99, it's the same as the dividend (aka numerator). + */ + x %= y; + #endif + + return x; +} + +fix16_t fix16_lerp8(fix16_t inArg0, fix16_t inArg1, uint8_t inFract) +{ + int64_t tempOut = int64_mul_i32_i32(inArg0, (((int32_t)1 << 8) - inFract)); + tempOut = int64_add(tempOut, int64_mul_i32_i32(inArg1, inFract)); + tempOut = int64_shift(tempOut, -8); + return (fix16_t)int64_lo(tempOut); +} + +fix16_t fix16_lerp16(fix16_t inArg0, fix16_t inArg1, uint16_t inFract) +{ + int64_t tempOut = int64_mul_i32_i32(inArg0, (((int32_t)1 << 16) - inFract)); + tempOut = int64_add(tempOut, int64_mul_i32_i32(inArg1, inFract)); + tempOut = int64_shift(tempOut, -16); + return (fix16_t)int64_lo(tempOut); +} + +fix16_t fix16_lerp32(fix16_t inArg0, fix16_t inArg1, uint32_t inFract) +{ + if(inFract == 0) + return inArg0; + int64_t inFract64 = int64_const(0, inFract); + int64_t subbed = int64_sub(int64_const(1,0), inFract64); + int64_t tempOut = int64_mul_i64_i32(subbed, inArg0); + tempOut = int64_add(tempOut, int64_mul_i64_i32(inFract64, inArg1)); + return int64_hi(tempOut); +} diff --git a/external/libfixmath/fix16.h b/external/libfixmath/fix16.h new file mode 100644 index 000000000000..86dbb719d5c8 --- /dev/null +++ b/external/libfixmath/fix16.h @@ -0,0 +1,333 @@ +#ifndef __libfixmath_fix16_h__ +#define __libfixmath_fix16_h__ + +#ifdef __cplusplus +extern "C" +{ +#endif + +/* These options may let the optimizer to remove some calls to the functions. + * Refer to http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html + */ +#ifndef FIXMATH_FUNC_ATTRS +# ifdef __GNUC__ +# if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ > 6) +# define FIXMATH_FUNC_ATTRS __attribute__((leaf, nothrow, const)) +# else +# define FIXMATH_FUNC_ATTRS __attribute__((nothrow, const)) +# endif +# else +# define FIXMATH_FUNC_ATTRS +# endif +#endif + +#include <stdint.h> + +typedef int32_t fix16_t; + +static const fix16_t FOUR_DIV_PI = 0x145F3; /*!< Fix16 value of 4/PI */ +static const fix16_t _FOUR_DIV_PI2 = 0xFFFF9840; /*!< Fix16 value of -4/PI² */ +static const fix16_t X4_CORRECTION_COMPONENT = 0x399A; /*!< Fix16 value of 0.225 */ +static const fix16_t PI_DIV_4 = 0x0000C90F; /*!< Fix16 value of PI/4 */ +static const fix16_t THREE_PI_DIV_4 = 0x00025B2F; /*!< Fix16 value of 3PI/4 */ + +static const fix16_t fix16_maximum = 0x7FFFFFFF; /*!< the maximum value of fix16_t */ +static const fix16_t fix16_minimum = 0x80000000; /*!< the minimum value of fix16_t */ +static const fix16_t fix16_overflow = 0x80000000; /*!< the value used to indicate overflows when FIXMATH_NO_OVERFLOW is not specified */ + +static const fix16_t fix16_pi = 205887; /*!< fix16_t value of pi */ +static const fix16_t fix16_e = 178145; /*!< fix16_t value of e */ +static const fix16_t fix16_one = 0x00010000; /*!< fix16_t value of 1 */ +static const fix16_t fix16_eps = 1; /*!< fix16_t epsilon */ + +/* Conversion functions between fix16_t and float/integer. + * These are inlined to allow compiler to optimize away constant numbers + */ +static inline fix16_t fix16_from_int(int a) { return a * fix16_one; } +static inline float fix16_to_float(fix16_t a) { return (float)a / fix16_one; } +static inline double fix16_to_dbl(fix16_t a) { return (double)a / fix16_one; } + +static inline int fix16_to_int(fix16_t a) +{ +#ifdef FIXMATH_NO_ROUNDING + return (a >> 16); +#else + if (a >= 0) + return (a + (fix16_one >> 1)) / fix16_one; + return (a - (fix16_one >> 1)) / fix16_one; +#endif +} + +static inline fix16_t fix16_from_float(float a) +{ + float temp = a * fix16_one; +#ifndef FIXMATH_NO_ROUNDING + temp += (temp >= 0) ? 0.5f : -0.5f; +#endif + return (fix16_t)temp; +} + +static inline fix16_t fix16_from_dbl(double a) +{ + double temp = a * fix16_one; + /* F16() and F16C() are both rounding allways, so this should as well */ +//#ifndef FIXMATH_NO_ROUNDING + temp += (double)((temp >= 0) ? 0.5f : -0.5f); +//#endif + return (fix16_t)temp; +} + +/* Macro for defining fix16_t constant values. + The functions above can't be used from e.g. global variable initializers, + and their names are quite long also. This macro is useful for constants + springled alongside code, e.g. F16(1.234). + + Note that the argument is evaluated multiple times, and also otherwise + you should only use this for constant values. For runtime-conversions, + use the functions above. +*/ +#define F16(x) ((fix16_t)(((x) >= 0) ? ((x) * 65536.0 + 0.5) : ((x) * 65536.0 - 0.5))) + +static inline fix16_t fix16_abs(fix16_t x) + { return (fix16_t)(x < 0 ? -(uint32_t)x : (uint32_t)x); } +static inline fix16_t fix16_floor(fix16_t x) + { return (x & 0xFFFF0000UL); } +static inline fix16_t fix16_ceil(fix16_t x) + { return (x & 0xFFFF0000UL) + (x & 0x0000FFFFUL ? fix16_one : 0); } +static inline fix16_t fix16_min(fix16_t x, fix16_t y) + { return (x < y ? x : y); } +static inline fix16_t fix16_max(fix16_t x, fix16_t y) + { return (x > y ? x : y); } +static inline fix16_t fix16_clamp(fix16_t x, fix16_t lo, fix16_t hi) + { return fix16_min(fix16_max(x, lo), hi); } + +/* Subtraction and addition with (optional) overflow detection. */ +#ifdef FIXMATH_NO_OVERFLOW + +static inline fix16_t fix16_add(fix16_t inArg0, fix16_t inArg1) { return (inArg0 + inArg1); } +static inline fix16_t fix16_sub(fix16_t inArg0, fix16_t inArg1) { return (inArg0 - inArg1); } + +#else + +extern fix16_t fix16_add(fix16_t a, fix16_t b) FIXMATH_FUNC_ATTRS; +extern fix16_t fix16_sub(fix16_t a, fix16_t b) FIXMATH_FUNC_ATTRS; + +/* Saturating arithmetic */ +extern fix16_t fix16_sadd(fix16_t a, fix16_t b) FIXMATH_FUNC_ATTRS; +extern fix16_t fix16_ssub(fix16_t a, fix16_t b) FIXMATH_FUNC_ATTRS; + +#endif + +/*! Multiplies the two given fix16_t's and returns the result. +*/ +extern fix16_t fix16_mul(fix16_t inArg0, fix16_t inArg1) FIXMATH_FUNC_ATTRS; + +/*! Divides the first given fix16_t by the second and returns the result. +*/ +extern fix16_t fix16_div(fix16_t inArg0, fix16_t inArg1) FIXMATH_FUNC_ATTRS; + +#ifndef FIXMATH_NO_OVERFLOW +/*! Performs a saturated multiplication (overflow-protected) of the two given fix16_t's and returns the result. +*/ +extern fix16_t fix16_smul(fix16_t inArg0, fix16_t inArg1) FIXMATH_FUNC_ATTRS; + +/*! Performs a saturated division (overflow-protected) of the first fix16_t by the second and returns the result. +*/ +extern fix16_t fix16_sdiv(fix16_t inArg0, fix16_t inArg1) FIXMATH_FUNC_ATTRS; +#endif + +/*! Divides the first given fix16_t by the second and returns the result. +*/ +extern fix16_t fix16_mod(fix16_t x, fix16_t y) FIXMATH_FUNC_ATTRS; + + + +/*! Returns the linear interpolation: (inArg0 * (1 - inFract)) + (inArg1 * inFract) +*/ +extern fix16_t fix16_lerp8(fix16_t inArg0, fix16_t inArg1, uint8_t inFract) FIXMATH_FUNC_ATTRS; +extern fix16_t fix16_lerp16(fix16_t inArg0, fix16_t inArg1, uint16_t inFract) FIXMATH_FUNC_ATTRS; +extern fix16_t fix16_lerp32(fix16_t inArg0, fix16_t inArg1, uint32_t inFract) FIXMATH_FUNC_ATTRS; + + + +/*! Returns the sine of the given fix16_t. +*/ +extern fix16_t fix16_sin_parabola(fix16_t inAngle) FIXMATH_FUNC_ATTRS; + +/*! Returns the sine of the given fix16_t. +*/ +extern fix16_t fix16_sin(fix16_t inAngle) FIXMATH_FUNC_ATTRS; + +/*! Returns the cosine of the given fix16_t. +*/ +extern fix16_t fix16_cos(fix16_t inAngle) FIXMATH_FUNC_ATTRS; + +/*! Returns the tangent of the given fix16_t. +*/ +extern fix16_t fix16_tan(fix16_t inAngle) FIXMATH_FUNC_ATTRS; + +/*! Returns the arcsine of the given fix16_t. +*/ +extern fix16_t fix16_asin(fix16_t inValue) FIXMATH_FUNC_ATTRS; + +/*! Returns the arccosine of the given fix16_t. +*/ +extern fix16_t fix16_acos(fix16_t inValue) FIXMATH_FUNC_ATTRS; + +/*! Returns the arctangent of the given fix16_t. +*/ +extern fix16_t fix16_atan(fix16_t inValue) FIXMATH_FUNC_ATTRS; + +/*! Returns the arctangent of inY/inX. +*/ +extern fix16_t fix16_atan2(fix16_t inY, fix16_t inX) FIXMATH_FUNC_ATTRS; + +static const fix16_t fix16_rad_to_deg_mult = 3754936; +static inline fix16_t fix16_rad_to_deg(fix16_t radians) + { return fix16_mul(radians, fix16_rad_to_deg_mult); } + +static const fix16_t fix16_deg_to_rad_mult = 1144; +static inline fix16_t fix16_deg_to_rad(fix16_t degrees) + { return fix16_mul(degrees, fix16_deg_to_rad_mult); } + + + +/*! Returns the square root of the given fix16_t. +*/ +extern fix16_t fix16_sqrt(fix16_t inValue) FIXMATH_FUNC_ATTRS; + +/*! Returns the square of the given fix16_t. +*/ +static inline fix16_t fix16_sq(fix16_t x) + { return fix16_mul(x, x); } + +/*! Returns the exponent (e^) of the given fix16_t. +*/ +extern fix16_t fix16_exp(fix16_t inValue) FIXMATH_FUNC_ATTRS; + +/*! Returns the natural logarithm of the given fix16_t. + */ +extern fix16_t fix16_log(fix16_t inValue) FIXMATH_FUNC_ATTRS; + +/*! Returns the base 2 logarithm of the given fix16_t. + */ +extern fix16_t fix16_log2(fix16_t x) FIXMATH_FUNC_ATTRS; + +/*! Returns the saturated base 2 logarithm of the given fix16_t. + */ +extern fix16_t fix16_slog2(fix16_t x) FIXMATH_FUNC_ATTRS; + +/*! Convert fix16_t value to a string. + * Required buffer length for largest values is 13 bytes. + */ +extern void fix16_to_str(fix16_t value, char *buf, int decimals); + +/*! Convert string to a fix16_t value + * Ignores spaces at beginning and end. Returns fix16_overflow if + * value is too large or there were garbage characters. + */ +extern fix16_t fix16_from_str(const char *buf); + +static inline uint32_t fix_abs(fix16_t in) +{ + if(in == fix16_minimum) + { + // minimum negative number has same representation as + // its absolute value in unsigned + return 0x80000000; + } + else + { + return ((in >= 0)?(in):(-in)); + } +} + + +/** Helper macro for F16C. Replace token with its number of characters/digits. */ +#define FIXMATH_TOKLEN(token) ( sizeof( #token ) - 1 ) + +/** Helper macro for F16C. Handles pow(10, n) for n from 0 to 8. */ +#define FIXMATH_CONSTANT_POW10(times) ( \ + (times == 0) ? 1ULL \ + : (times == 1) ? 10ULL \ + : (times == 2) ? 100ULL \ + : (times == 3) ? 1000ULL \ + : (times == 4) ? 10000ULL \ + : (times == 5) ? 100000ULL \ + : (times == 6) ? 1000000ULL \ + : (times == 7) ? 10000000ULL \ + : 100000000ULL \ +) + + +/** Helper macro for F16C, the type uint64_t is only used at compile time and + * shouldn't be visible in the generated code. + * + * @note We do not use fix16_one instead of 65536ULL, because the + * "use of a const variable in a constant expression is nonstandard in C". + */ +#define FIXMATH_CONVERT_MANTISSA(m) \ +( (unsigned) \ + ( \ + ( \ + ( \ + (uint64_t)( ( ( 1 ## m ## ULL ) - FIXMATH_CONSTANT_POW10(FIXMATH_TOKLEN(m)) ) * FIXMATH_CONSTANT_POW10(5 - FIXMATH_TOKLEN(m)) ) \ + * 100000ULL * 65536ULL \ + ) \ + + 5000000000ULL /* rounding: + 0.5 */ \ + ) \ + / \ + 10000000000LL \ + ) \ +) + + +#define FIXMATH_COMBINE_I_M(i, m) \ +( \ + ( \ + ( i ) \ + << 16 \ + ) \ + | \ + ( \ + FIXMATH_CONVERT_MANTISSA(m) \ + & 0xFFFF \ + ) \ +) + + +/** Create int16_t (Q16.16) constant from separate integer and mantissa part. + * + * Only tested on 32-bit ARM Cortex-M0 / x86 Intel. + * + * This macro is needed when compiling with options like "--fpu=none", + * which forbid all and every use of float and related types and + * would thus make it impossible to have fix16_t constants. + * + * Just replace uses of F16() with F16C() like this: + * F16(123.1234) becomes F16C(123,1234) + * + * @warning Specification of any value outside the mentioned intervals + * WILL result in undefined behavior! + * + * @note Regardless of the specified minimum and maximum values for i and m below, + * the total value of the number represented by i and m MUST be in the interval + * ]-32768.00000:32767.99999[ else usage with this macro will yield undefined behavior. + * + * @param i Signed integer constant with a value in the interval ]-32768:32767[. + * @param m Positive integer constant in the interval ]0:99999[ (fractional part/mantissa). + */ +#define F16C(i, m) \ +( (fix16_t) \ + ( \ + (( #i[0] ) == '-') \ + ? -FIXMATH_COMBINE_I_M((unsigned)( ( (i) * -1) ), m) \ + : FIXMATH_COMBINE_I_M((unsigned)i, m) \ + ) \ +) + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/external/libfixmath/int64.h b/external/libfixmath/int64.h new file mode 100644 index 000000000000..41e0e7a3ba45 --- /dev/null +++ b/external/libfixmath/int64.h @@ -0,0 +1,177 @@ +#ifndef __libfixmath_int64_h__ +#define __libfixmath_int64_h__ + +#ifdef __cplusplus +extern "C" +{ +#endif + +#include <stdint.h> + +#ifndef FIXMATH_NO_64BIT +static inline int64_t int64_const(int32_t hi, uint32_t lo) { return (((int64_t)hi << 32) | lo); } +static inline int64_t int64_from_int32(int32_t x) { return (int64_t)x; } +static inline int32_t int64_hi(int64_t x) { return (x >> 32); } +static inline uint32_t int64_lo(int64_t x) { return (x & ((1ULL << 32) - 1)); } + +static inline int64_t int64_add(int64_t x, int64_t y) { return (x + y); } +static inline int64_t int64_neg(int64_t x) { return (-x); } +static inline int64_t int64_sub(int64_t x, int64_t y) { return (x - y); } +static inline int64_t int64_shift(int64_t x, int8_t y) { return (y < 0 ? (x >> -y) : (x << y)); } + +static inline int64_t int64_mul_i32_i32(int32_t x, int32_t y) { return ((int64_t)x * y); } +static inline int64_t int64_mul_i64_i32(int64_t x, int32_t y) { return (x * y); } + +static inline int64_t int64_div_i64_i32(int64_t x, int32_t y) { return (x / y); } + +static inline int int64_cmp_eq(int64_t x, int64_t y) { return (x == y); } +static inline int int64_cmp_ne(int64_t x, int64_t y) { return (x != y); } +static inline int int64_cmp_gt(int64_t x, int64_t y) { return (x > y); } +static inline int int64_cmp_ge(int64_t x, int64_t y) { return (x >= y); } +static inline int int64_cmp_lt(int64_t x, int64_t y) { return (x < y); } +static inline int int64_cmp_le(int64_t x, int64_t y) { return (x <= y); } +#else + +typedef struct { + int32_t hi; + uint32_t lo; +} _int64_t; + +static inline _int64_t int64_const(int32_t hi, uint32_t lo) { return (_int64_t){ hi, lo }; } +static inline _int64_t int64_from_int32(int32_t x) { return (_int64_t){ (x < 0 ? -1 : 0), x }; } +static inline int32_t int64_hi(_int64_t x) { return x.hi; } +static inline uint32_t int64_lo(_int64_t x) { return x.lo; } + +static inline int int64_cmp_eq(_int64_t x, _int64_t y) { return ((x.hi == y.hi) && (x.lo == y.lo)); } +static inline int int64_cmp_ne(_int64_t x, _int64_t y) { return ((x.hi != y.hi) || (x.lo != y.lo)); } +static inline int int64_cmp_gt(_int64_t x, _int64_t y) { return ((x.hi > y.hi) || ((x.hi == y.hi) && (x.lo > y.lo))); } +static inline int int64_cmp_ge(_int64_t x, _int64_t y) { return ((x.hi > y.hi) || ((x.hi == y.hi) && (x.lo >= y.lo))); } +static inline int int64_cmp_lt(_int64_t x, _int64_t y) { return ((x.hi < y.hi) || ((x.hi == y.hi) && (x.lo < y.lo))); } +static inline int int64_cmp_le(_int64_t x, _int64_t y) { return ((x.hi < y.hi) || ((x.hi == y.hi) && (x.lo <= y.lo))); } + +static inline _int64_t int64_add(_int64_t x, _int64_t y) { + _int64_t ret; + ret.hi = x.hi + y.hi; + ret.lo = x.lo + y.lo; + if((ret.lo < x.lo) || (ret.lo < y.lo)) + ret.hi++; + return ret; +} + +static inline _int64_t int64_neg(_int64_t x) { + _int64_t ret; + ret.hi = ~x.hi; + ret.lo = ~x.lo + 1; + if(ret.lo == 0) + ret.hi++; + return ret; +} + +static inline _int64_t int64_sub(_int64_t x, _int64_t y) { + return int64_add(x, int64_neg(y)); +} + +static inline _int64_t int64_shift(_int64_t x, int8_t y) { + _int64_t ret = {0,0}; + if(y >= 64 || y <= -64) + return (_int64_t){ 0, 0 }; + if(y >= 32) { + ret.hi = (x.lo << (y - 32)); + } + else if(y > 0) { + ret.hi = (x.hi << y) | (x.lo >> (32 - y)); + ret.lo = (x.lo << y); + } + else { + y = -y; + if(y >= 32){ + ret.lo = (x.hi >> (y - 32)); + ret.hi = (x.hi < 0) ? -1 : 0; + } else { + ret.lo = (x.lo >> y) | (x.hi << (32 - y)); + ret.hi = (x.hi >> y); + } + } + return ret; +} + +static inline _int64_t int64_mul_i32_i32(int32_t x, int32_t y) { + int16_t hi[2] = { (x >> 16), (y >> 16) }; + uint16_t lo[2] = { (x & 0xFFFF), (y & 0xFFFF) }; + + int32_t r_hi = hi[0] * hi[1]; + int32_t r_md = (hi[0] * lo[1]) + (hi[1] * lo[0]); + uint32_t r_lo = lo[0] * lo[1]; + + _int64_t r_hilo64 = (_int64_t){ r_hi, r_lo }; + _int64_t r_md64 = int64_shift(int64_from_int32(r_md), 16); + + return int64_add(r_hilo64, r_md64); +} + +static inline _int64_t int64_mul_i64_i32(_int64_t x, int32_t y) { + int neg = ((x.hi ^ y) < 0); + if(x.hi < 0) + x = int64_neg(x); + uint32_t ypos = (y < 0)? (-y) : (y); + + uint32_t _x[4] = { (x.lo & 0xFFFF), (x.lo >> 16), (x.hi & 0xFFFF), (x.hi >> 16) }; + uint32_t _y[2] = { (ypos & 0xFFFF), (ypos >> 16) }; + + uint32_t r[4]; + r[0] = (_x[0] * _y[0]); + r[1] = (_x[1] * _y[0]); + uint32_t temp_r1 = r[1]; + r[1] += (_x[0] * _y[1]); + r[2] = (_x[2] * _y[0]) + (_x[1] * _y[1]); + r[3] = (_x[3] * _y[0]) + (_x[2] * _y[1]); + // Detect carry bit in r[1]. r[0] can't carry, and r[2]/r[3] don't matter. + if(r[1] < temp_r1) + r[3] ++; + + _int64_t middle = int64_shift(int64_const(0, r[1]), 16); + _int64_t ret; + ret.lo = r[0]; + ret.hi = (r[3] << 16) + r[2]; + ret = int64_add(ret, middle); + return (neg ? int64_neg(ret) : ret); +} + +static inline _int64_t int64_div_i64_i32(_int64_t x, int32_t y) { + int neg = ((x.hi ^ y) < 0); + if(x.hi < 0) + x = int64_neg(x); + if(y < 0) + y = -y; + + _int64_t ret = { (x.hi / y) , (x.lo / y) }; + x.hi = x.hi % y; + x.lo = x.lo % y; + + _int64_t _y = int64_from_int32(y); + + _int64_t i; + for(i = int64_from_int32(1); int64_cmp_lt(_y, x); _y = int64_shift(_y, 1), i = int64_shift(i, 1)); + + while(x.hi) { + _y = int64_shift(_y, -1); + i = int64_shift(i, -1); + if(int64_cmp_ge(x, _y)) { + x = int64_sub(x, _y); + ret = int64_add(ret, i); + } + } + + ret = int64_add(ret, int64_from_int32(x.lo / y)); + return (neg ? int64_neg(ret) : ret); +} + +#define int64_t _int64_t + +#endif + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/readlicense_oo/license/license.xml b/readlicense_oo/license/license.xml index f0a2484b8acb..b13a80e0dd8f 100644 --- a/readlicense_oo/license/license.xml +++ b/readlicense_oo/license/license.xml @@ -1884,6 +1884,33 @@ REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.</p> </blockquote> + + <h2>libfixmath</h2> + <p>The following software may be included in this product: libfixmath.</p> + <p>libfixmath code is covered by the MIT license:</p> + <blockquote> + <p>libfixmath is Copyright (c) 2011-2021 Flatmush <Flatmush@gmail.com>, + Petteri Aimonen <Petteri.Aimonen@gmail.com>, & libfixmath AUTHORS</p> + + <p>Permission is hereby granted, free of charge, to any person obtaining a copy + of this software and associated documentation files (the "Software"), to deal + in the Software without restriction, including without limitation the rights + to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + copies of the Software, and to permit persons to whom the Software is + furnished to do so, subject to the following conditions:</p> + + <p>The above copyright notice and this permission notice shall be included in all + copies or substantial portions of the Software.</p> + + <p>THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE.</p> + </blockquote> + <h2>Random123: a Library of Counter-Based Random Number Generators</h2> <p>The following software may be included in this product: Random123: a Library of Counter-Based Random Number Generators. Use of any of this software is governed by the terms of the license below:</p> diff --git a/solenv/clang-format/excludelist b/solenv/clang-format/excludelist index d2adcf0b54c8..bd72bbada39f 100644 --- a/solenv/clang-format/excludelist +++ b/solenv/clang-format/excludelist @@ -3886,6 +3886,9 @@ external/skia/inc/skia_opts.hxx external/skia/source/skia_opts.cxx external/skia/source/skia_opts_internal.hxx external/skia/source/skia_opts_ssse3.cxx +external/libfixmath/fix16.c +external/libfixmath/fix16.h +external/libfixmath/int64.h external/unixODBC/inc/odbc/sql.h external/unixODBC/inc/odbc/sqlext.h external/unixODBC/inc/odbc/sqltypes.h diff --git a/vcl/Library_vcl.mk b/vcl/Library_vcl.mk index d580ff3d2f6a..50aeebcc9c95 100644 --- a/vcl/Library_vcl.mk +++ b/vcl/Library_vcl.mk @@ -40,6 +40,7 @@ $(eval $(call gb_Library_set_precompiled_header,vcl,vcl/inc/pch/precompiled_vcl) $(eval $(call gb_Library_set_include,vcl,\ $$(INCLUDE) \ -I$(SRCDIR)/vcl/inc \ + -I$(SRCDIR)/external/libfixmath \ )) $(eval $(call gb_Library_add_defs,vcl,\ @@ -524,6 +525,7 @@ $(eval $(call gb_Library_add_exception_objects,vcl,\ $(eval $(call gb_Library_add_cobjects,vcl,\ vcl/source/filter/jpeg/transupp \ + vcl/source/fontsubset/fixmath \ )) vcl_headless_code= \ diff --git a/vcl/source/fontsubset/fixmath.c b/vcl/source/fontsubset/fixmath.c new file mode 100644 index 000000000000..1871cb77d88c --- /dev/null +++ b/vcl/source/fontsubset/fixmath.c @@ -0,0 +1,13 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; fill-column: 100 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + */ + +#include "fixmath.h" +#include <fix16.c> + +/* vim:set shiftwidth=4 softtabstop=4 expandtab cinoptions=b1,g0,N-s cinkeys+=0=break: */ diff --git a/vcl/source/fontsubset/fixmath.h b/vcl/source/fontsubset/fixmath.h new file mode 100644 index 000000000000..87aebf279436 --- /dev/null +++ b/vcl/source/fontsubset/fixmath.h @@ -0,0 +1,23 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; fill-column: 100 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + */ + +#pragma once + +#if defined _MSC_VER && !defined __clang__ +#pragma warning(push) +#pragma warning(disable : 4146) +#endif + +#include <fix16.h> + +#if defined _MSC_VER && !defined __clang__ +#pragma warning(pop) +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab cinoptions=b1,g0,N-s cinkeys+=0=break: */ diff --git a/vcl/source/fontsubset/sft.cxx b/vcl/source/fontsubset/sft.cxx index 681e974dc8a2..7115b2251853 100644 --- a/vcl/source/fontsubset/sft.cxx +++ b/vcl/source/fontsubset/sft.cxx @@ -36,6 +36,7 @@ #endif #include <sft.hxx> #include <impfontcharmap.hxx> +#include "fixmath.h" #include "ttcr.hxx" #include "xlat.hxx" #include <rtl/crc.h> @@ -169,47 +170,12 @@ static sal_uInt32 GetUInt32(const sal_uInt8 *ptr, size_t offset) static F16Dot16 fixedMul(F16Dot16 a, F16Dot16 b) { - int sign = (a & 0x80000000) ^ (b & 0x80000000); - if (a < 0) a = o3tl::saturating_toggle_sign(a); - if (b < 0) b = o3tl::saturating_toggle_sign(b); - - unsigned int a1 = a >> 16; - unsigned int b1 = a & 0xFFFF; - unsigned int a2 = b >> 16; - unsigned int b2 = b & 0xFFFF; - - F16Dot16 res = a1 * a2; - - /* if (res > 0x7FFF) assert(!"fixedMul: F16Dot16 overflow"); */ - - res <<= 16; - res += a1 * b2 + b1 * a2 + ((b1 * b2) >> 16); - - return sign ? -res : res; + return fix16_mul(a, b); } static F16Dot16 fixedDiv(F16Dot16 a, F16Dot16 b) { - int sign = (a & 0x80000000) ^ (b & 0x80000000); - if (a < 0) a = -a; - if (b < 0) b = -b; - - unsigned int f = a / b; - unsigned int r = a % b; - - /* if (f > 0x7FFFF) assert(!"fixedDiv: F16Dot16 overflow"); */ - - while (r > 0xFFFF) { - r >>= 1; - b >>= 1; - } - - F16Dot16 res; - if (b == 0) - res = 0x7FFFFFFF; - else - res = (f << 16) + (r << 16) / b; - return sign ? -res : res; + return fix16_div(a, b); } /*- returns a * b / c -*/ |