• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /****************************************************************************
2  *
3  * ftcalc.c
4  *
5  *   Arithmetic computations (body).
6  *
7  * Copyright 1996-2018 by
8  * David Turner, Robert Wilhelm, and Werner Lemberg.
9  *
10  * This file is part of the FreeType project, and may only be used,
11  * modified, and distributed under the terms of the FreeType project
12  * license, LICENSE.TXT.  By continuing to use, modify, or distribute
13  * this file you indicate that you have read the license and
14  * understand and accept it fully.
15  *
16  */
17 
18   /**************************************************************************
19    *
20    * Support for 1-complement arithmetic has been totally dropped in this
21    * release.  You can still write your own code if you need it.
22    *
23    */
24 
25   /**************************************************************************
26    *
27    * Implementing basic computation routines.
28    *
29    * FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(),
30    * and FT_FloorFix() are declared in freetype.h.
31    *
32    */
33 
34 
35 #include <ft2build.h>
36 #include FT_GLYPH_H
37 #include FT_TRIGONOMETRY_H
38 #include FT_INTERNAL_CALC_H
39 #include FT_INTERNAL_DEBUG_H
40 #include FT_INTERNAL_OBJECTS_H
41 
42 
43 #ifdef FT_MULFIX_ASSEMBLER
44 #undef FT_MulFix
45 #endif
46 
47 /* we need to emulate a 64-bit data type if a real one isn't available */
48 
49 #ifndef FT_LONG64
50 
51   typedef struct  FT_Int64_
52   {
53     FT_UInt32  lo;
54     FT_UInt32  hi;
55 
56   } FT_Int64;
57 
58 #endif /* !FT_LONG64 */
59 
60 
61   /**************************************************************************
62    *
63    * The macro FT_COMPONENT is used in trace mode.  It is an implicit
64    * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log
65    * messages during execution.
66    */
67 #undef  FT_COMPONENT
68 #define FT_COMPONENT  trace_calc
69 
70 
71   /* transfer sign, leaving a positive number;                        */
72   /* we need an unsigned value to safely negate INT_MIN (or LONG_MIN) */
73 #define FT_MOVE_SIGN( x, x_unsigned, s ) \
74   FT_BEGIN_STMNT                         \
75     if ( x < 0 )                         \
76     {                                    \
77       x_unsigned = 0U - (x_unsigned);    \
78       s          = -s;                   \
79     }                                    \
80   FT_END_STMNT
81 
82   /* The following three functions are available regardless of whether */
83   /* FT_LONG64 is defined.                                             */
84 
85   /* documentation is in freetype.h */
86 
87   FT_EXPORT_DEF( FT_Fixed )
FT_RoundFix(FT_Fixed a)88   FT_RoundFix( FT_Fixed  a )
89   {
90     return ( ADD_LONG( a, 0x8000L - ( a < 0 ) ) ) & ~0xFFFFL;
91   }
92 
93 
94   /* documentation is in freetype.h */
95 
96   FT_EXPORT_DEF( FT_Fixed )
FT_CeilFix(FT_Fixed a)97   FT_CeilFix( FT_Fixed  a )
98   {
99     return ( ADD_LONG( a, 0xFFFFL ) ) & ~0xFFFFL;
100   }
101 
102 
103   /* documentation is in freetype.h */
104 
105   FT_EXPORT_DEF( FT_Fixed )
FT_FloorFix(FT_Fixed a)106   FT_FloorFix( FT_Fixed  a )
107   {
108     return a & ~0xFFFFL;
109   }
110 
111 #ifndef FT_MSB
112 
113   FT_BASE_DEF ( FT_Int )
FT_MSB(FT_UInt32 z)114   FT_MSB( FT_UInt32 z )
115   {
116     FT_Int  shift = 0;
117 
118 
119     /* determine msb bit index in `shift' */
120     if ( z & 0xFFFF0000UL )
121     {
122       z     >>= 16;
123       shift  += 16;
124     }
125     if ( z & 0x0000FF00UL )
126     {
127       z     >>= 8;
128       shift  += 8;
129     }
130     if ( z & 0x000000F0UL )
131     {
132       z     >>= 4;
133       shift  += 4;
134     }
135     if ( z & 0x0000000CUL )
136     {
137       z     >>= 2;
138       shift  += 2;
139     }
140     if ( z & 0x00000002UL )
141     {
142    /* z     >>= 1; */
143       shift  += 1;
144     }
145 
146     return shift;
147   }
148 
149 #endif /* !FT_MSB */
150 
151 
152   /* documentation is in ftcalc.h */
153 
154   FT_BASE_DEF( FT_Fixed )
FT_Hypot(FT_Fixed x,FT_Fixed y)155   FT_Hypot( FT_Fixed  x,
156             FT_Fixed  y )
157   {
158     FT_Vector  v;
159 
160 
161     v.x = x;
162     v.y = y;
163 
164     return FT_Vector_Length( &v );
165   }
166 
167 
168 #ifdef FT_LONG64
169 
170 
171   /* documentation is in freetype.h */
172 
173   FT_EXPORT_DEF( FT_Long )
FT_MulDiv(FT_Long a_,FT_Long b_,FT_Long c_)174   FT_MulDiv( FT_Long  a_,
175              FT_Long  b_,
176              FT_Long  c_ )
177   {
178     FT_Int     s = 1;
179     FT_UInt64  a, b, c, d;
180     FT_Long    d_;
181 
182 
183     a = (FT_UInt64)a_;
184     b = (FT_UInt64)b_;
185     c = (FT_UInt64)c_;
186 
187     FT_MOVE_SIGN( a_, a, s );
188     FT_MOVE_SIGN( b_, b, s );
189     FT_MOVE_SIGN( c_, c, s );
190 
191     d = c > 0 ? ( a * b + ( c >> 1 ) ) / c
192               : 0x7FFFFFFFUL;
193 
194     d_ = (FT_Long)d;
195 
196     return s < 0 ? NEG_LONG( d_ ) : d_;
197   }
198 
199 
200   /* documentation is in ftcalc.h */
201 
202   FT_BASE_DEF( FT_Long )
FT_MulDiv_No_Round(FT_Long a_,FT_Long b_,FT_Long c_)203   FT_MulDiv_No_Round( FT_Long  a_,
204                       FT_Long  b_,
205                       FT_Long  c_ )
206   {
207     FT_Int     s = 1;
208     FT_UInt64  a, b, c, d;
209     FT_Long    d_;
210 
211 
212     a = (FT_UInt64)a_;
213     b = (FT_UInt64)b_;
214     c = (FT_UInt64)c_;
215 
216     FT_MOVE_SIGN( a_, a, s );
217     FT_MOVE_SIGN( b_, b, s );
218     FT_MOVE_SIGN( c_, c, s );
219 
220     d = c > 0 ? a * b / c
221               : 0x7FFFFFFFUL;
222 
223     d_ = (FT_Long)d;
224 
225     return s < 0 ? NEG_LONG( d_ ) : d_;
226   }
227 
228 
229   /* documentation is in freetype.h */
230 
231   FT_EXPORT_DEF( FT_Long )
FT_MulFix(FT_Long a_,FT_Long b_)232   FT_MulFix( FT_Long  a_,
233              FT_Long  b_ )
234   {
235 #ifdef FT_MULFIX_ASSEMBLER
236 
237     return FT_MULFIX_ASSEMBLER( (FT_Int32)a_, (FT_Int32)b_ );
238 
239 #else
240 
241     FT_Int64  ab = (FT_Int64)a_ * (FT_Int64)b_;
242 
243     /* this requires arithmetic right shift of signed numbers */
244     return (FT_Long)( ( ab + 0x8000L - ( ab < 0 ) ) >> 16 );
245 
246 #endif /* FT_MULFIX_ASSEMBLER */
247   }
248 
249 
250   /* documentation is in freetype.h */
251 
252   FT_EXPORT_DEF( FT_Long )
FT_DivFix(FT_Long a_,FT_Long b_)253   FT_DivFix( FT_Long  a_,
254              FT_Long  b_ )
255   {
256     FT_Int     s = 1;
257     FT_UInt64  a, b, q;
258     FT_Long    q_;
259 
260 
261     a = (FT_UInt64)a_;
262     b = (FT_UInt64)b_;
263 
264     FT_MOVE_SIGN( a_, a, s );
265     FT_MOVE_SIGN( b_, b, s );
266 
267     q = b > 0 ? ( ( a << 16 ) + ( b >> 1 ) ) / b
268               : 0x7FFFFFFFUL;
269 
270     q_ = (FT_Long)q;
271 
272     return s < 0 ? NEG_LONG( q_ ) : q_;
273   }
274 
275 
276 #else /* !FT_LONG64 */
277 
278 
279   static void
ft_multo64(FT_UInt32 x,FT_UInt32 y,FT_Int64 * z)280   ft_multo64( FT_UInt32  x,
281               FT_UInt32  y,
282               FT_Int64  *z )
283   {
284     FT_UInt32  lo1, hi1, lo2, hi2, lo, hi, i1, i2;
285 
286 
287     lo1 = x & 0x0000FFFFU;  hi1 = x >> 16;
288     lo2 = y & 0x0000FFFFU;  hi2 = y >> 16;
289 
290     lo = lo1 * lo2;
291     i1 = lo1 * hi2;
292     i2 = lo2 * hi1;
293     hi = hi1 * hi2;
294 
295     /* Check carry overflow of i1 + i2 */
296     i1 += i2;
297     hi += (FT_UInt32)( i1 < i2 ) << 16;
298 
299     hi += i1 >> 16;
300     i1  = i1 << 16;
301 
302     /* Check carry overflow of i1 + lo */
303     lo += i1;
304     hi += ( lo < i1 );
305 
306     z->lo = lo;
307     z->hi = hi;
308   }
309 
310 
311   static FT_UInt32
ft_div64by32(FT_UInt32 hi,FT_UInt32 lo,FT_UInt32 y)312   ft_div64by32( FT_UInt32  hi,
313                 FT_UInt32  lo,
314                 FT_UInt32  y )
315   {
316     FT_UInt32  r, q;
317     FT_Int     i;
318 
319 
320     if ( hi >= y )
321       return (FT_UInt32)0x7FFFFFFFL;
322 
323     /* We shift as many bits as we can into the high register, perform     */
324     /* 32-bit division with modulo there, then work through the remaining  */
325     /* bits with long division. This optimization is especially noticeable */
326     /* for smaller dividends that barely use the high register.            */
327 
328     i = 31 - FT_MSB( hi );
329     r = ( hi << i ) | ( lo >> ( 32 - i ) ); lo <<= i; /* left 64-bit shift */
330     q = r / y;
331     r -= q * y;   /* remainder */
332 
333     i = 32 - i;   /* bits remaining in low register */
334     do
335     {
336       q <<= 1;
337       r   = ( r << 1 ) | ( lo >> 31 ); lo <<= 1;
338 
339       if ( r >= y )
340       {
341         r -= y;
342         q |= 1;
343       }
344     } while ( --i );
345 
346     return q;
347   }
348 
349 
350   static void
FT_Add64(FT_Int64 * x,FT_Int64 * y,FT_Int64 * z)351   FT_Add64( FT_Int64*  x,
352             FT_Int64*  y,
353             FT_Int64  *z )
354   {
355     FT_UInt32  lo, hi;
356 
357 
358     lo = x->lo + y->lo;
359     hi = x->hi + y->hi + ( lo < x->lo );
360 
361     z->lo = lo;
362     z->hi = hi;
363   }
364 
365 
366   /*  The FT_MulDiv function has been optimized thanks to ideas from     */
367   /*  Graham Asher and Alexei Podtelezhnikov.  The trick is to optimize  */
368   /*  a rather common case when everything fits within 32-bits.          */
369   /*                                                                     */
370   /*  We compute 'a*b+c/2', then divide it by 'c' (all positive values). */
371   /*                                                                     */
372   /*  The product of two positive numbers never exceeds the square of    */
373   /*  its mean values.  Therefore, we always avoid the overflow by       */
374   /*  imposing                                                           */
375   /*                                                                     */
376   /*    (a + b) / 2 <= sqrt(X - c/2)    ,                                */
377   /*                                                                     */
378   /*  where X = 2^32 - 1, the maximum unsigned 32-bit value, and using   */
379   /*  unsigned arithmetic.  Now we replace `sqrt' with a linear function */
380   /*  that is smaller or equal for all values of c in the interval       */
381   /*  [0;X/2]; it should be equal to sqrt(X) and sqrt(3X/4) at the       */
382   /*  endpoints.  Substituting the linear solution and explicit numbers  */
383   /*  we get                                                             */
384   /*                                                                     */
385   /*    a + b <= 131071.99 - c / 122291.84    .                          */
386   /*                                                                     */
387   /*  In practice, we should use a faster and even stronger inequality   */
388   /*                                                                     */
389   /*    a + b <= 131071 - (c >> 16)                                      */
390   /*                                                                     */
391   /*  or, alternatively,                                                 */
392   /*                                                                     */
393   /*    a + b <= 129894 - (c >> 17)    .                                 */
394   /*                                                                     */
395   /*  FT_MulFix, on the other hand, is optimized for a small value of    */
396   /*  the first argument, when the second argument can be much larger.   */
397   /*  This can be achieved by scaling the second argument and the limit  */
398   /*  in the above inequalities.  For example,                           */
399   /*                                                                     */
400   /*    a + (b >> 8) <= (131071 >> 4)                                    */
401   /*                                                                     */
402   /*  covers the practical range of use. The actual test below is a bit  */
403   /*  tighter to avoid the border case overflows.                        */
404   /*                                                                     */
405   /*  In the case of FT_DivFix, the exact overflow check                 */
406   /*                                                                     */
407   /*    a << 16 <= X - c/2                                               */
408   /*                                                                     */
409   /*  is scaled down by 2^16 and we use                                  */
410   /*                                                                     */
411   /*    a <= 65535 - (c >> 17)    .                                      */
412 
413   /* documentation is in freetype.h */
414 
415   FT_EXPORT_DEF( FT_Long )
FT_MulDiv(FT_Long a_,FT_Long b_,FT_Long c_)416   FT_MulDiv( FT_Long  a_,
417              FT_Long  b_,
418              FT_Long  c_ )
419   {
420     FT_Int     s = 1;
421     FT_UInt32  a, b, c;
422 
423 
424     /* XXX: this function does not allow 64-bit arguments */
425 
426     a = (FT_UInt32)a_;
427     b = (FT_UInt32)b_;
428     c = (FT_UInt32)c_;
429 
430     FT_MOVE_SIGN( a_, a, s );
431     FT_MOVE_SIGN( b_, b, s );
432     FT_MOVE_SIGN( c_, c, s );
433 
434     if ( c == 0 )
435       a = 0x7FFFFFFFUL;
436 
437     else if ( a + b <= 129894UL - ( c >> 17 ) )
438       a = ( a * b + ( c >> 1 ) ) / c;
439 
440     else
441     {
442       FT_Int64  temp, temp2;
443 
444 
445       ft_multo64( a, b, &temp );
446 
447       temp2.hi = 0;
448       temp2.lo = c >> 1;
449 
450       FT_Add64( &temp, &temp2, &temp );
451 
452       /* last attempt to ditch long division */
453       a = ( temp.hi == 0 ) ? temp.lo / c
454                            : ft_div64by32( temp.hi, temp.lo, c );
455     }
456 
457     a_ = (FT_Long)a;
458 
459     return s < 0 ? NEG_LONG( a_ ) : a_;
460   }
461 
462 
463   FT_BASE_DEF( FT_Long )
FT_MulDiv_No_Round(FT_Long a_,FT_Long b_,FT_Long c_)464   FT_MulDiv_No_Round( FT_Long  a_,
465                       FT_Long  b_,
466                       FT_Long  c_ )
467   {
468     FT_Int     s = 1;
469     FT_UInt32  a, b, c;
470 
471 
472     /* XXX: this function does not allow 64-bit arguments */
473 
474     a = (FT_UInt32)a_;
475     b = (FT_UInt32)b_;
476     c = (FT_UInt32)c_;
477 
478     FT_MOVE_SIGN( a_, a, s );
479     FT_MOVE_SIGN( b_, b, s );
480     FT_MOVE_SIGN( c_, c, s );
481 
482     if ( c == 0 )
483       a = 0x7FFFFFFFUL;
484 
485     else if ( a + b <= 131071UL )
486       a = a * b / c;
487 
488     else
489     {
490       FT_Int64  temp;
491 
492 
493       ft_multo64( a, b, &temp );
494 
495       /* last attempt to ditch long division */
496       a = ( temp.hi == 0 ) ? temp.lo / c
497                            : ft_div64by32( temp.hi, temp.lo, c );
498     }
499 
500     a_ = (FT_Long)a;
501 
502     return s < 0 ? NEG_LONG( a_ ) : a_;
503   }
504 
505 
506   /* documentation is in freetype.h */
507 
508   FT_EXPORT_DEF( FT_Long )
FT_MulFix(FT_Long a_,FT_Long b_)509   FT_MulFix( FT_Long  a_,
510              FT_Long  b_ )
511   {
512 #ifdef FT_MULFIX_ASSEMBLER
513 
514     return FT_MULFIX_ASSEMBLER( a_, b_ );
515 
516 #elif 0
517 
518     /*
519      * This code is nonportable.  See comment below.
520      *
521      * However, on a platform where right-shift of a signed quantity fills
522      * the leftmost bits by copying the sign bit, it might be faster.
523      */
524 
525     FT_Long    sa, sb;
526     FT_UInt32  a, b;
527 
528 
529     /*
530      * This is a clever way of converting a signed number `a' into its
531      * absolute value (stored back into `a') and its sign.  The sign is
532      * stored in `sa'; 0 means `a' was positive or zero, and -1 means `a'
533      * was negative.  (Similarly for `b' and `sb').
534      *
535      * Unfortunately, it doesn't work (at least not portably).
536      *
537      * It makes the assumption that right-shift on a negative signed value
538      * fills the leftmost bits by copying the sign bit.  This is wrong.
539      * According to K&R 2nd ed, section `A7.8 Shift Operators' on page 206,
540      * the result of right-shift of a negative signed value is
541      * implementation-defined.  At least one implementation fills the
542      * leftmost bits with 0s (i.e., it is exactly the same as an unsigned
543      * right shift).  This means that when `a' is negative, `sa' ends up
544      * with the value 1 rather than -1.  After that, everything else goes
545      * wrong.
546      */
547     sa = ( a_ >> ( sizeof ( a_ ) * 8 - 1 ) );
548     a  = ( a_ ^ sa ) - sa;
549     sb = ( b_ >> ( sizeof ( b_ ) * 8 - 1 ) );
550     b  = ( b_ ^ sb ) - sb;
551 
552     a = (FT_UInt32)a_;
553     b = (FT_UInt32)b_;
554 
555     if ( a + ( b >> 8 ) <= 8190UL )
556       a = ( a * b + 0x8000U ) >> 16;
557     else
558     {
559       FT_UInt32  al = a & 0xFFFFUL;
560 
561 
562       a = ( a >> 16 ) * b + al * ( b >> 16 ) +
563           ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 );
564     }
565 
566     sa ^= sb;
567     a   = ( a ^ sa ) - sa;
568 
569     return (FT_Long)a;
570 
571 #else /* 0 */
572 
573     FT_Int     s = 1;
574     FT_UInt32  a, b;
575 
576 
577     /* XXX: this function does not allow 64-bit arguments */
578 
579     a = (FT_UInt32)a_;
580     b = (FT_UInt32)b_;
581 
582     FT_MOVE_SIGN( a_, a, s );
583     FT_MOVE_SIGN( b_, b, s );
584 
585     if ( a + ( b >> 8 ) <= 8190UL )
586       a = ( a * b + 0x8000UL ) >> 16;
587     else
588     {
589       FT_UInt32  al = a & 0xFFFFUL;
590 
591 
592       a = ( a >> 16 ) * b + al * ( b >> 16 ) +
593           ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 );
594     }
595 
596     a_ = (FT_Long)a;
597 
598     return s < 0 ? NEG_LONG( a_ ) : a_;
599 
600 #endif /* 0 */
601 
602   }
603 
604 
605   /* documentation is in freetype.h */
606 
607   FT_EXPORT_DEF( FT_Long )
FT_DivFix(FT_Long a_,FT_Long b_)608   FT_DivFix( FT_Long  a_,
609              FT_Long  b_ )
610   {
611     FT_Int     s = 1;
612     FT_UInt32  a, b, q;
613     FT_Long    q_;
614 
615 
616     /* XXX: this function does not allow 64-bit arguments */
617 
618     a = (FT_UInt32)a_;
619     b = (FT_UInt32)b_;
620 
621     FT_MOVE_SIGN( a_, a, s );
622     FT_MOVE_SIGN( b_, b, s );
623 
624     if ( b == 0 )
625     {
626       /* check for division by 0 */
627       q = 0x7FFFFFFFUL;
628     }
629     else if ( a <= 65535UL - ( b >> 17 ) )
630     {
631       /* compute result directly */
632       q = ( ( a << 16 ) + ( b >> 1 ) ) / b;
633     }
634     else
635     {
636       /* we need more bits; we have to do it by hand */
637       FT_Int64  temp, temp2;
638 
639 
640       temp.hi  = a >> 16;
641       temp.lo  = a << 16;
642       temp2.hi = 0;
643       temp2.lo = b >> 1;
644 
645       FT_Add64( &temp, &temp2, &temp );
646       q = ft_div64by32( temp.hi, temp.lo, b );
647     }
648 
649     q_ = (FT_Long)q;
650 
651     return s < 0 ? NEG_LONG( q_ ) : q_;
652   }
653 
654 
655 #endif /* !FT_LONG64 */
656 
657 
658   /* documentation is in ftglyph.h */
659 
660   FT_EXPORT_DEF( void )
FT_Matrix_Multiply(const FT_Matrix * a,FT_Matrix * b)661   FT_Matrix_Multiply( const FT_Matrix*  a,
662                       FT_Matrix        *b )
663   {
664     FT_Fixed  xx, xy, yx, yy;
665 
666 
667     if ( !a || !b )
668       return;
669 
670     xx = ADD_LONG( FT_MulFix( a->xx, b->xx ),
671                    FT_MulFix( a->xy, b->yx ) );
672     xy = ADD_LONG( FT_MulFix( a->xx, b->xy ),
673                    FT_MulFix( a->xy, b->yy ) );
674     yx = ADD_LONG( FT_MulFix( a->yx, b->xx ),
675                    FT_MulFix( a->yy, b->yx ) );
676     yy = ADD_LONG( FT_MulFix( a->yx, b->xy ),
677                    FT_MulFix( a->yy, b->yy ) );
678 
679     b->xx = xx;
680     b->xy = xy;
681     b->yx = yx;
682     b->yy = yy;
683   }
684 
685 
686   /* documentation is in ftglyph.h */
687 
688   FT_EXPORT_DEF( FT_Error )
FT_Matrix_Invert(FT_Matrix * matrix)689   FT_Matrix_Invert( FT_Matrix*  matrix )
690   {
691     FT_Pos  delta, xx, yy;
692 
693 
694     if ( !matrix )
695       return FT_THROW( Invalid_Argument );
696 
697     /* compute discriminant */
698     delta = FT_MulFix( matrix->xx, matrix->yy ) -
699             FT_MulFix( matrix->xy, matrix->yx );
700 
701     if ( !delta )
702       return FT_THROW( Invalid_Argument );  /* matrix can't be inverted */
703 
704     matrix->xy = - FT_DivFix( matrix->xy, delta );
705     matrix->yx = - FT_DivFix( matrix->yx, delta );
706 
707     xx = matrix->xx;
708     yy = matrix->yy;
709 
710     matrix->xx = FT_DivFix( yy, delta );
711     matrix->yy = FT_DivFix( xx, delta );
712 
713     return FT_Err_Ok;
714   }
715 
716 
717   /* documentation is in ftcalc.h */
718 
719   FT_BASE_DEF( void )
FT_Matrix_Multiply_Scaled(const FT_Matrix * a,FT_Matrix * b,FT_Long scaling)720   FT_Matrix_Multiply_Scaled( const FT_Matrix*  a,
721                              FT_Matrix        *b,
722                              FT_Long           scaling )
723   {
724     FT_Fixed  xx, xy, yx, yy;
725 
726     FT_Long   val = 0x10000L * scaling;
727 
728 
729     if ( !a || !b )
730       return;
731 
732     xx = ADD_LONG( FT_MulDiv( a->xx, b->xx, val ),
733                    FT_MulDiv( a->xy, b->yx, val ) );
734     xy = ADD_LONG( FT_MulDiv( a->xx, b->xy, val ),
735                    FT_MulDiv( a->xy, b->yy, val ) );
736     yx = ADD_LONG( FT_MulDiv( a->yx, b->xx, val ),
737                    FT_MulDiv( a->yy, b->yx, val ) );
738     yy = ADD_LONG( FT_MulDiv( a->yx, b->xy, val ),
739                    FT_MulDiv( a->yy, b->yy, val ) );
740 
741     b->xx = xx;
742     b->xy = xy;
743     b->yx = yx;
744     b->yy = yy;
745   }
746 
747 
748   /* documentation is in ftcalc.h */
749 
750   FT_BASE_DEF( FT_Bool )
FT_Matrix_Check(const FT_Matrix * matrix)751   FT_Matrix_Check( const FT_Matrix*  matrix )
752   {
753     FT_Matrix  m;
754     FT_Fixed   val[4];
755     FT_Fixed   nonzero_minval, maxval;
756     FT_Fixed   temp1, temp2;
757     FT_UInt    i;
758 
759 
760     if ( !matrix )
761       return 0;
762 
763     val[0] = FT_ABS( matrix->xx );
764     val[1] = FT_ABS( matrix->xy );
765     val[2] = FT_ABS( matrix->yx );
766     val[3] = FT_ABS( matrix->yy );
767 
768     /*
769      * To avoid overflow, we ensure that each value is not larger than
770      *
771      *   int(sqrt(2^31 / 4)) = 23170  ;
772      *
773      * we also check that no value becomes zero if we have to scale.
774      */
775 
776     maxval         = 0;
777     nonzero_minval = FT_LONG_MAX;
778 
779     for ( i = 0; i < 4; i++ )
780     {
781       if ( val[i] > maxval )
782         maxval = val[i];
783       if ( val[i] && val[i] < nonzero_minval )
784         nonzero_minval = val[i];
785     }
786 
787     if ( maxval > 23170 )
788     {
789       FT_Fixed  scale = FT_DivFix( maxval, 23170 );
790 
791 
792       if ( !FT_DivFix( nonzero_minval, scale ) )
793         return 0;    /* value range too large */
794 
795       m.xx = FT_DivFix( matrix->xx, scale );
796       m.xy = FT_DivFix( matrix->xy, scale );
797       m.yx = FT_DivFix( matrix->yx, scale );
798       m.yy = FT_DivFix( matrix->yy, scale );
799     }
800     else
801       m = *matrix;
802 
803     temp1 = FT_ABS( m.xx * m.yy - m.xy * m.yx );
804     temp2 = m.xx * m.xx + m.xy * m.xy + m.yx * m.yx + m.yy * m.yy;
805 
806     if ( temp1 == 0         ||
807          temp2 / temp1 > 50 )
808       return 0;
809 
810     return 1;
811   }
812 
813 
814   /* documentation is in ftcalc.h */
815 
816   FT_BASE_DEF( void )
FT_Vector_Transform_Scaled(FT_Vector * vector,const FT_Matrix * matrix,FT_Long scaling)817   FT_Vector_Transform_Scaled( FT_Vector*        vector,
818                               const FT_Matrix*  matrix,
819                               FT_Long           scaling )
820   {
821     FT_Pos   xz, yz;
822 
823     FT_Long  val = 0x10000L * scaling;
824 
825 
826     if ( !vector || !matrix )
827       return;
828 
829     xz = ADD_LONG( FT_MulDiv( vector->x, matrix->xx, val ),
830                    FT_MulDiv( vector->y, matrix->xy, val ) );
831     yz = ADD_LONG( FT_MulDiv( vector->x, matrix->yx, val ),
832                    FT_MulDiv( vector->y, matrix->yy, val ) );
833 
834     vector->x = xz;
835     vector->y = yz;
836   }
837 
838 
839   /* documentation is in ftcalc.h */
840 
841   FT_BASE_DEF( FT_UInt32 )
FT_Vector_NormLen(FT_Vector * vector)842   FT_Vector_NormLen( FT_Vector*  vector )
843   {
844     FT_Int32   x_ = vector->x;
845     FT_Int32   y_ = vector->y;
846     FT_Int32   b, z;
847     FT_UInt32  x, y, u, v, l;
848     FT_Int     sx = 1, sy = 1, shift;
849 
850 
851     x = (FT_UInt32)x_;
852     y = (FT_UInt32)y_;
853 
854     FT_MOVE_SIGN( x_, x, sx );
855     FT_MOVE_SIGN( y_, y, sy );
856 
857     /* trivial cases */
858     if ( x == 0 )
859     {
860       if ( y > 0 )
861         vector->y = sy * 0x10000;
862       return y;
863     }
864     else if ( y == 0 )
865     {
866       if ( x > 0 )
867         vector->x = sx * 0x10000;
868       return x;
869     }
870 
871     /* Estimate length and prenormalize by shifting so that */
872     /* the new approximate length is between 2/3 and 4/3.   */
873     /* The magic constant 0xAAAAAAAAUL (2/3 of 2^32) helps  */
874     /* achieve this in 16.16 fixed-point representation.    */
875     l = x > y ? x + ( y >> 1 )
876               : y + ( x >> 1 );
877 
878     shift  = 31 - FT_MSB( l );
879     shift -= 15 + ( l >= ( 0xAAAAAAAAUL >> shift ) );
880 
881     if ( shift > 0 )
882     {
883       x <<= shift;
884       y <<= shift;
885 
886       /* re-estimate length for tiny vectors */
887       l = x > y ? x + ( y >> 1 )
888                 : y + ( x >> 1 );
889     }
890     else
891     {
892       x >>= -shift;
893       y >>= -shift;
894       l >>= -shift;
895     }
896 
897     /* lower linear approximation for reciprocal length minus one */
898     b = 0x10000 - (FT_Int32)l;
899 
900     x_ = (FT_Int32)x;
901     y_ = (FT_Int32)y;
902 
903     /* Newton's iterations */
904     do
905     {
906       u = (FT_UInt32)( x_ + ( x_ * b >> 16 ) );
907       v = (FT_UInt32)( y_ + ( y_ * b >> 16 ) );
908 
909       /* Normalized squared length in the parentheses approaches 2^32. */
910       /* On two's complement systems, converting to signed gives the   */
911       /* difference with 2^32 even if the expression wraps around.     */
912       z = -(FT_Int32)( u * u + v * v ) / 0x200;
913       z = z * ( ( 0x10000 + b ) >> 8 ) / 0x10000;
914 
915       b += z;
916 
917     } while ( z > 0 );
918 
919     vector->x = sx < 0 ? -(FT_Pos)u : (FT_Pos)u;
920     vector->y = sy < 0 ? -(FT_Pos)v : (FT_Pos)v;
921 
922     /* Conversion to signed helps to recover from likely wrap around */
923     /* in calculating the prenormalized length, because it gives the */
924     /* correct difference with 2^32 on two's complement systems.     */
925     l = (FT_UInt32)( 0x10000 + (FT_Int32)( u * x + v * y ) / 0x10000 );
926     if ( shift > 0 )
927       l = ( l + ( 1 << ( shift - 1 ) ) ) >> shift;
928     else
929       l <<= -shift;
930 
931     return l;
932   }
933 
934 
935 #if 0
936 
937   /* documentation is in ftcalc.h */
938 
939   FT_BASE_DEF( FT_Int32 )
940   FT_SqrtFixed( FT_Int32  x )
941   {
942     FT_UInt32  root, rem_hi, rem_lo, test_div;
943     FT_Int     count;
944 
945 
946     root = 0;
947 
948     if ( x > 0 )
949     {
950       rem_hi = 0;
951       rem_lo = (FT_UInt32)x;
952       count  = 24;
953       do
954       {
955         rem_hi   = ( rem_hi << 2 ) | ( rem_lo >> 30 );
956         rem_lo <<= 2;
957         root   <<= 1;
958         test_div = ( root << 1 ) + 1;
959 
960         if ( rem_hi >= test_div )
961         {
962           rem_hi -= test_div;
963           root   += 1;
964         }
965       } while ( --count );
966     }
967 
968     return (FT_Int32)root;
969   }
970 
971 #endif /* 0 */
972 
973 
974   /* documentation is in ftcalc.h */
975 
976   FT_BASE_DEF( FT_Int )
ft_corner_orientation(FT_Pos in_x,FT_Pos in_y,FT_Pos out_x,FT_Pos out_y)977   ft_corner_orientation( FT_Pos  in_x,
978                          FT_Pos  in_y,
979                          FT_Pos  out_x,
980                          FT_Pos  out_y )
981   {
982 #ifdef FT_LONG64
983 
984     FT_Int64  delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x;
985 
986 
987     return ( delta > 0 ) - ( delta < 0 );
988 
989 #else
990 
991     FT_Int  result;
992 
993 
994     /* we silently ignore overflow errors, since such large values */
995     /* lead to even more (harmless) rendering errors later on      */
996     if ( ADD_LONG( FT_ABS( in_x ), FT_ABS( out_y ) ) <= 131071L &&
997          ADD_LONG( FT_ABS( in_y ), FT_ABS( out_x ) ) <= 131071L )
998     {
999       FT_Long  z1 = MUL_LONG( in_x, out_y );
1000       FT_Long  z2 = MUL_LONG( in_y, out_x );
1001 
1002 
1003       if ( z1 > z2 )
1004         result = +1;
1005       else if ( z1 < z2 )
1006         result = -1;
1007       else
1008         result = 0;
1009     }
1010     else /* products might overflow 32 bits */
1011     {
1012       FT_Int64  z1, z2;
1013 
1014 
1015       /* XXX: this function does not allow 64-bit arguments */
1016       ft_multo64( (FT_UInt32)in_x, (FT_UInt32)out_y, &z1 );
1017       ft_multo64( (FT_UInt32)in_y, (FT_UInt32)out_x, &z2 );
1018 
1019       if ( z1.hi > z2.hi )
1020         result = +1;
1021       else if ( z1.hi < z2.hi )
1022         result = -1;
1023       else if ( z1.lo > z2.lo )
1024         result = +1;
1025       else if ( z1.lo < z2.lo )
1026         result = -1;
1027       else
1028         result = 0;
1029     }
1030 
1031     /* XXX: only the sign of return value, +1/0/-1 must be used */
1032     return result;
1033 
1034 #endif
1035   }
1036 
1037 
1038   /* documentation is in ftcalc.h */
1039 
1040   FT_BASE_DEF( FT_Int )
ft_corner_is_flat(FT_Pos in_x,FT_Pos in_y,FT_Pos out_x,FT_Pos out_y)1041   ft_corner_is_flat( FT_Pos  in_x,
1042                      FT_Pos  in_y,
1043                      FT_Pos  out_x,
1044                      FT_Pos  out_y )
1045   {
1046     FT_Pos  ax = in_x + out_x;
1047     FT_Pos  ay = in_y + out_y;
1048 
1049     FT_Pos  d_in, d_out, d_hypot;
1050 
1051 
1052     /* The idea of this function is to compare the length of the */
1053     /* hypotenuse with the `in' and `out' length.  The `corner'  */
1054     /* represented by `in' and `out' is flat if the hypotenuse's */
1055     /* length isn't too large.                                   */
1056     /*                                                           */
1057     /* This approach has the advantage that the angle between    */
1058     /* `in' and `out' is not checked.  In case one of the two    */
1059     /* vectors is `dominant', this is, much larger than the      */
1060     /* other vector, we thus always have a flat corner.          */
1061     /*                                                           */
1062     /*                hypotenuse                                 */
1063     /*       x---------------------------x                       */
1064     /*        \                      /                           */
1065     /*         \                /                                */
1066     /*      in  \          /  out                                */
1067     /*           \    /                                          */
1068     /*            o                                              */
1069     /*              Point                                        */
1070 
1071     d_in    = FT_HYPOT(  in_x,  in_y );
1072     d_out   = FT_HYPOT( out_x, out_y );
1073     d_hypot = FT_HYPOT(    ax,    ay );
1074 
1075     /* now do a simple length comparison: */
1076     /*                                    */
1077     /*   d_in + d_out < 17/16 d_hypot     */
1078 
1079     return ( d_in + d_out - d_hypot ) < ( d_hypot >> 4 );
1080   }
1081 
1082 
1083 /* END */
1084