Commit f09326a1a6d09cee2e6c60034acd86af4c94c06f
2014-08-20T00:08:38
[base] Use unsigned calculation in `FT_MulDiv'. * src/base/ftcalc.c (FT_MulDiv): Updated to expand 32-bit range.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
diff --git a/ChangeLog b/ChangeLog
index 8f25f1e..cff13e3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2014-08-19 Alexei Podtelezhnikov <apodtele@gmail.com>
+
+ [base] Use unsigned calculation in `FT_MulDiv'.
+
+ * src/base/ftcalc.c (FT_MulDiv): Updated to expand 32-bit range.
+
2014-08-18 Alexei Podtelezhnikov <apodtele@gmail.com>
[base] Remove truncation in `FT_DivFix'.
diff --git a/src/base/ftcalc.c b/src/base/ftcalc.c
index 27e9e07..9c72a76 100644
--- a/src/base/ftcalc.c
+++ b/src/base/ftcalc.c
@@ -358,11 +358,9 @@
}
- /* documentation is in freetype.h */
-
- /* The FT_MulDiv function has been optimized thanks to ideas from */
- /* Graham Asher and Alexei Podtelezhnikov. The trick is to optimize */
- /* a rather common case when everything fits within 32-bits. */
+ /* The FT_MulDiv function has been optimized thanks to ideas from */
+ /* Graham Asher and Alexei Podtelezhnikov. The trick is to optimize */
+ /* a rather common case when everything fits within 32-bits. */
/* */
/* We compute 'a*b+c/2', then divide it by 'c'. (positive values) */
/* */
@@ -371,17 +369,24 @@
/* */
/* ( a + b ) / 2 <= sqrt( X - c/2 ) */
/* */
- /* where X = 2^31 - 1. Now we replace sqrt with a linear function */
- /* that is smaller or equal in the entire range of c from 0 to X; */
- /* it should be equal to sqrt(X) and sqrt(X/2) at the range termini. */
+ /* where X = 2^32 - 1, the maximun unsigned 32-bit value, and using */
+ /* unsigned arithmetic. Now we replace sqrt with a linear function */
+ /* that is smaller or equal in the entire range of c from 0 to X/2; */
+ /* it should be equal to sqrt(X) and sqrt(3X/4) at the termini. */
/* Substituting the linear solution and explicit numbers we get */
/* */
- /* a + b <= 92681.9 - c / 79108.95 */
+ /* a + b <= 131071.99 - c / 122291.84 */
+ /* */
+ /* In practice we should use a faster and even stronger inequality */
/* */
- /* In practice we use a faster and even stronger inequality */
+ /* a + b <= 131071 - (c >> 16) */
/* */
- /* a + b <= 92681 - (c >> 16) */
+ /* or, alternatively, */
/* */
+ /* a + b <= 129895 - (c >> 17) */
+ /* */
+
+ /* documentation is in freetype.h */
FT_EXPORT_DEF( FT_Long )
FT_MulDiv( FT_Long a,
@@ -402,8 +407,8 @@
if ( c == 0 )
a = 0x7FFFFFFFL;
- else if ( (FT_ULong)a + (FT_ULong)b <= 92681UL - ( c >> 16 ) )
- a = ( a * b + ( c >> 1 ) ) / c;
+ else if ( (FT_ULong)a + b <= 129895UL - ( c >> 17 ) )
+ a = ( (FT_ULong)a * b + ( c >> 1 ) ) / c;
else
{
@@ -440,8 +445,8 @@
if ( c == 0 )
a = 0x7FFFFFFFL;
- else if ( (FT_ULong)a + (FT_ULong)b <= 92681UL )
- a = a * b / c;
+ else if ( (FT_ULong)a + b <= 131071UL )
+ a = (FT_ULong)a * b / c;
else
{