• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /***************************************************************************/
2 /*                                                                         */
3 /*  ftcalc.c                                                               */
4 /*                                                                         */
5 /*    Arithmetic computations (body).                                      */
6 /*                                                                         */
7 /*  Copyright 1996-2001, 2002, 2003, 2004, 2005, 2006, 2008 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_INTERNAL_CALC_H
38 #include FT_INTERNAL_DEBUG_H
39 #include FT_INTERNAL_OBJECTS_H
40 
41 #ifdef FT_MULFIX_INLINED
42 #undef FT_MulFix
43 #endif
44 
45 /* we need to define a 64-bits data type here */
46 
47 #ifdef FT_LONG64
48 
49   typedef FT_INT64  FT_Int64;
50 
51 #else
52 
53   typedef struct  FT_Int64_
54   {
55     FT_UInt32  lo;
56     FT_UInt32  hi;
57 
58   } FT_Int64;
59 
60 #endif /* FT_LONG64 */
61 
62 
63   /*************************************************************************/
64   /*                                                                       */
65   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
66   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
67   /* messages during execution.                                            */
68   /*                                                                       */
69 #undef  FT_COMPONENT
70 #define FT_COMPONENT  trace_calc
71 
72 
73   /* The following three functions are available regardless of whether */
74   /* FT_LONG64 is defined.                                             */
75 
76   /* documentation is in freetype.h */
77 
78   FT_EXPORT_DEF( FT_Fixed )
FT_RoundFix(FT_Fixed a)79   FT_RoundFix( FT_Fixed  a )
80   {
81     return ( a >= 0 ) ?   ( a + 0x8000L ) & ~0xFFFFL
82                       : -((-a + 0x8000L ) & ~0xFFFFL );
83   }
84 
85 
86   /* documentation is in freetype.h */
87 
88   FT_EXPORT_DEF( FT_Fixed )
FT_CeilFix(FT_Fixed a)89   FT_CeilFix( FT_Fixed  a )
90   {
91     return ( a >= 0 ) ?   ( a + 0xFFFFL ) & ~0xFFFFL
92                       : -((-a + 0xFFFFL ) & ~0xFFFFL );
93   }
94 
95 
96   /* documentation is in freetype.h */
97 
98   FT_EXPORT_DEF( FT_Fixed )
FT_FloorFix(FT_Fixed a)99   FT_FloorFix( FT_Fixed  a )
100   {
101     return ( a >= 0 ) ?   a & ~0xFFFFL
102                       : -((-a) & ~0xFFFFL );
103   }
104 
105 
106 #ifdef FT_CONFIG_OPTION_OLD_INTERNALS
107 
108   /* documentation is in ftcalc.h */
109 
110   FT_EXPORT_DEF( FT_Int32 )
FT_Sqrt32(FT_Int32 x)111   FT_Sqrt32( FT_Int32  x )
112   {
113     FT_UInt32  val, root, newroot, mask;
114 
115 
116     root = 0;
117     mask = (FT_UInt32)0x40000000UL;
118     val  = (FT_UInt32)x;
119 
120     do
121     {
122       newroot = root + mask;
123       if ( newroot <= val )
124       {
125         val -= newroot;
126         root = newroot + mask;
127       }
128 
129       root >>= 1;
130       mask >>= 2;
131 
132     } while ( mask != 0 );
133 
134     return root;
135   }
136 
137 #endif /* FT_CONFIG_OPTION_OLD_INTERNALS */
138 
139 
140 #ifdef FT_LONG64
141 
142 
143   /* documentation is in freetype.h */
144 
145   FT_EXPORT_DEF( FT_Long )
FT_MulDiv(FT_Long a,FT_Long b,FT_Long c)146   FT_MulDiv( FT_Long  a,
147              FT_Long  b,
148              FT_Long  c )
149   {
150     FT_Int   s;
151     FT_Long  d;
152 
153 
154     s = 1;
155     if ( a < 0 ) { a = -a; s = -1; }
156     if ( b < 0 ) { b = -b; s = -s; }
157     if ( c < 0 ) { c = -c; s = -s; }
158 
159     d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c
160                          : 0x7FFFFFFFL );
161 
162     return ( s > 0 ) ? d : -d;
163   }
164 
165 
166 #ifdef TT_USE_BYTECODE_INTERPRETER
167 
168   /* documentation is in ftcalc.h */
169 
170   FT_BASE_DEF( FT_Long )
FT_MulDiv_No_Round(FT_Long a,FT_Long b,FT_Long c)171   FT_MulDiv_No_Round( FT_Long  a,
172                       FT_Long  b,
173                       FT_Long  c )
174   {
175     FT_Int   s;
176     FT_Long  d;
177 
178 
179     s = 1;
180     if ( a < 0 ) { a = -a; s = -1; }
181     if ( b < 0 ) { b = -b; s = -s; }
182     if ( c < 0 ) { c = -c; s = -s; }
183 
184     d = (FT_Long)( c > 0 ? (FT_Int64)a * b / c
185                          : 0x7FFFFFFFL );
186 
187     return ( s > 0 ) ? d : -d;
188   }
189 
190 #endif /* TT_USE_BYTECODE_INTERPRETER */
191 
192 
193   /* documentation is in freetype.h */
194 
195   FT_EXPORT_DEF( FT_Long )
FT_MulFix(FT_Long a,FT_Long b)196   FT_MulFix( FT_Long  a,
197              FT_Long  b )
198   {
199 #ifdef FT_MULFIX_ASSEMBLER
200 
201     return FT_MULFIX_ASSEMBLER( a, b );
202 
203 #else
204 
205     FT_Int   s = 1;
206     FT_Long  c;
207 
208 
209     if ( a < 0 )
210     {
211       a = -a;
212       s = -1;
213     }
214 
215     if ( b < 0 )
216     {
217       b = -b;
218       s = -s;
219     }
220 
221     c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 );
222 
223     return ( s > 0 ) ? c : -c;
224 
225 #endif /* FT_MULFIX_ASSEMBLER */
226   }
227 
228 
229   /* documentation is in freetype.h */
230 
231   FT_EXPORT_DEF( FT_Long )
FT_DivFix(FT_Long a,FT_Long b)232   FT_DivFix( FT_Long  a,
233              FT_Long  b )
234   {
235     FT_Int32   s;
236     FT_UInt32  q;
237 
238     s = 1;
239     if ( a < 0 ) { a = -a; s = -1; }
240     if ( b < 0 ) { b = -b; s = -s; }
241 
242     if ( b == 0 )
243       /* check for division by 0 */
244       q = 0x7FFFFFFFL;
245     else
246       /* compute result directly */
247       q = (FT_UInt32)( ( ( (FT_Int64)a << 16 ) + ( b >> 1 ) ) / b );
248 
249     return ( s < 0 ? -(FT_Long)q : (FT_Long)q );
250   }
251 
252 
253 #else /* !FT_LONG64 */
254 
255 
256   static void
ft_multo64(FT_UInt32 x,FT_UInt32 y,FT_Int64 * z)257   ft_multo64( FT_UInt32  x,
258               FT_UInt32  y,
259               FT_Int64  *z )
260   {
261     FT_UInt32  lo1, hi1, lo2, hi2, lo, hi, i1, i2;
262 
263 
264     lo1 = x & 0x0000FFFFU;  hi1 = x >> 16;
265     lo2 = y & 0x0000FFFFU;  hi2 = y >> 16;
266 
267     lo = lo1 * lo2;
268     i1 = lo1 * hi2;
269     i2 = lo2 * hi1;
270     hi = hi1 * hi2;
271 
272     /* Check carry overflow of i1 + i2 */
273     i1 += i2;
274     hi += (FT_UInt32)( i1 < i2 ) << 16;
275 
276     hi += i1 >> 16;
277     i1  = i1 << 16;
278 
279     /* Check carry overflow of i1 + lo */
280     lo += i1;
281     hi += ( lo < i1 );
282 
283     z->lo = lo;
284     z->hi = hi;
285   }
286 
287 
288   static FT_UInt32
ft_div64by32(FT_UInt32 hi,FT_UInt32 lo,FT_UInt32 y)289   ft_div64by32( FT_UInt32  hi,
290                 FT_UInt32  lo,
291                 FT_UInt32  y )
292   {
293     FT_UInt32  r, q;
294     FT_Int     i;
295 
296 
297     q = 0;
298     r = hi;
299 
300     if ( r >= y )
301       return (FT_UInt32)0x7FFFFFFFL;
302 
303     i = 32;
304     do
305     {
306       r <<= 1;
307       q <<= 1;
308       r  |= lo >> 31;
309 
310       if ( r >= (FT_UInt32)y )
311       {
312         r -= y;
313         q |= 1;
314       }
315       lo <<= 1;
316     } while ( --i );
317 
318     return q;
319   }
320 
321 
322   static void
FT_Add64(FT_Int64 * x,FT_Int64 * y,FT_Int64 * z)323   FT_Add64( FT_Int64*  x,
324             FT_Int64*  y,
325             FT_Int64  *z )
326   {
327     register FT_UInt32  lo, hi;
328 
329 
330     lo = x->lo + y->lo;
331     hi = x->hi + y->hi + ( lo < x->lo );
332 
333     z->lo = lo;
334     z->hi = hi;
335   }
336 
337 
338   /* documentation is in freetype.h */
339 
340   /* The FT_MulDiv function has been optimized thanks to ideas from      */
341   /* Graham Asher.  The trick is to optimize computation when everything */
342   /* fits within 32-bits (a rather common case).                         */
343   /*                                                                     */
344   /*  we compute 'a*b+c/2', then divide it by 'c'. (positive values)     */
345   /*                                                                     */
346   /*  46340 is FLOOR(SQRT(2^31-1)).                                      */
347   /*                                                                     */
348   /*  if ( a <= 46340 && b <= 46340 ) then ( a*b <= 0x7FFEA810 )         */
349   /*                                                                     */
350   /*  0x7FFFFFFF - 0x7FFEA810 = 0x157F0                                  */
351   /*                                                                     */
352   /*  if ( c < 0x157F0*2 ) then ( a*b+c/2 <= 0x7FFFFFFF )                */
353   /*                                                                     */
354   /*  and 2*0x157F0 = 176096                                             */
355   /*                                                                     */
356 
357   FT_EXPORT_DEF( FT_Long )
FT_MulDiv(FT_Long a,FT_Long b,FT_Long c)358   FT_MulDiv( FT_Long  a,
359              FT_Long  b,
360              FT_Long  c )
361   {
362     long  s;
363 
364 
365     /* XXX: this function does not allow 64-bit arguments */
366     if ( a == 0 || b == c )
367       return a;
368 
369     s  = a; a = FT_ABS( a );
370     s ^= b; b = FT_ABS( b );
371     s ^= c; c = FT_ABS( c );
372 
373     if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 )
374       a = ( a * b + ( c >> 1 ) ) / c;
375 
376     else if ( c > 0 )
377     {
378       FT_Int64  temp, temp2;
379 
380 
381       ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp );
382 
383       temp2.hi = 0;
384       temp2.lo = (FT_UInt32)(c >> 1);
385       FT_Add64( &temp, &temp2, &temp );
386       a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c );
387     }
388     else
389       a = 0x7FFFFFFFL;
390 
391     return ( s < 0 ? -a : a );
392   }
393 
394 
395 #ifdef TT_USE_BYTECODE_INTERPRETER
396 
397   FT_BASE_DEF( FT_Long )
FT_MulDiv_No_Round(FT_Long a,FT_Long b,FT_Long c)398   FT_MulDiv_No_Round( FT_Long  a,
399                       FT_Long  b,
400                       FT_Long  c )
401   {
402     long  s;
403 
404 
405     if ( a == 0 || b == c )
406       return a;
407 
408     s  = a; a = FT_ABS( a );
409     s ^= b; b = FT_ABS( b );
410     s ^= c; c = FT_ABS( c );
411 
412     if ( a <= 46340L && b <= 46340L && c > 0 )
413       a = a * b / c;
414 
415     else if ( c > 0 )
416     {
417       FT_Int64  temp;
418 
419 
420       ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp );
421       a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c );
422     }
423     else
424       a = 0x7FFFFFFFL;
425 
426     return ( s < 0 ? -a : a );
427   }
428 
429 #endif /* TT_USE_BYTECODE_INTERPRETER */
430 
431 
432   /* documentation is in freetype.h */
433 
434   FT_EXPORT_DEF( FT_Long )
FT_MulFix(FT_Long a,FT_Long b)435   FT_MulFix( FT_Long  a,
436              FT_Long  b )
437   {
438 #ifdef FT_MULFIX_ASSEMBLER
439 
440     return FT_MULFIX_ASSEMBLER( a, b );
441 
442 #elif 0
443 
444     /*
445      *  This code is nonportable.  See comment below.
446      *
447      *  However, on a platform where right-shift of a signed quantity fills
448      *  the leftmost bits by copying the sign bit, it might be faster.
449      */
450 
451     FT_Long   sa, sb;
452     FT_ULong  ua, ub;
453 
454 
455     if ( a == 0 || b == 0x10000L )
456       return a;
457 
458     /*
459      *  This is a clever way of converting a signed number `a' into its
460      *  absolute value (stored back into `a') and its sign.  The sign is
461      *  stored in `sa'; 0 means `a' was positive or zero, and -1 means `a'
462      *  was negative.  (Similarly for `b' and `sb').
463      *
464      *  Unfortunately, it doesn't work (at least not portably).
465      *
466      *  It makes the assumption that right-shift on a negative signed value
467      *  fills the leftmost bits by copying the sign bit.  This is wrong.
468      *  According to K&R 2nd ed, section `A7.8 Shift Operators' on page 206,
469      *  the result of right-shift of a negative signed value is
470      *  implementation-defined.  At least one implementation fills the
471      *  leftmost bits with 0s (i.e., it is exactly the same as an unsigned
472      *  right shift).  This means that when `a' is negative, `sa' ends up
473      *  with the value 1 rather than -1.  After that, everything else goes
474      *  wrong.
475      */
476     sa = ( a >> ( sizeof ( a ) * 8 - 1 ) );
477     a  = ( a ^ sa ) - sa;
478     sb = ( b >> ( sizeof ( b ) * 8 - 1 ) );
479     b  = ( b ^ sb ) - sb;
480 
481     ua = (FT_ULong)a;
482     ub = (FT_ULong)b;
483 
484     if ( ua <= 2048 && ub <= 1048576L )
485       ua = ( ua * ub + 0x8000U ) >> 16;
486     else
487     {
488       FT_ULong  al = ua & 0xFFFFU;
489 
490 
491       ua = ( ua >> 16 ) * ub +  al * ( ub >> 16 ) +
492            ( ( al * ( ub & 0xFFFFU ) + 0x8000U ) >> 16 );
493     }
494 
495     sa ^= sb,
496     ua  = (FT_ULong)(( ua ^ sa ) - sa);
497 
498     return (FT_Long)ua;
499 
500 #else /* 0 */
501 
502     FT_Long   s;
503     FT_ULong  ua, ub;
504 
505 
506     if ( a == 0 || b == 0x10000L )
507       return a;
508 
509     s  = a; a = FT_ABS( a );
510     s ^= b; b = FT_ABS( b );
511 
512     ua = (FT_ULong)a;
513     ub = (FT_ULong)b;
514 
515     if ( ua <= 2048 && ub <= 1048576L )
516       ua = ( ua * ub + 0x8000UL ) >> 16;
517     else
518     {
519       FT_ULong  al = ua & 0xFFFFUL;
520 
521 
522       ua = ( ua >> 16 ) * ub +  al * ( ub >> 16 ) +
523            ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 );
524     }
525 
526     return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua );
527 
528 #endif /* 0 */
529 
530   }
531 
532 
533   /* documentation is in freetype.h */
534 
535   FT_EXPORT_DEF( FT_Long )
FT_DivFix(FT_Long a,FT_Long b)536   FT_DivFix( FT_Long  a,
537              FT_Long  b )
538   {
539     FT_Int32   s;
540     FT_UInt32  q;
541 
542 
543     /* XXX: this function does not allow 64-bit arguments */
544     s  = (FT_Int32)a; a = FT_ABS( a );
545     s ^= (FT_Int32)b; b = FT_ABS( b );
546 
547     if ( b == 0 )
548     {
549       /* check for division by 0 */
550       q = (FT_UInt32)0x7FFFFFFFL;
551     }
552     else if ( ( a >> 16 ) == 0 )
553     {
554       /* compute result directly */
555       q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b;
556     }
557     else
558     {
559       /* we need more bits; we have to do it by hand */
560       FT_Int64  temp, temp2;
561 
562       temp.hi  = (FT_Int32) (a >> 16);
563       temp.lo  = (FT_UInt32)(a << 16);
564       temp2.hi = 0;
565       temp2.lo = (FT_UInt32)( b >> 1 );
566       FT_Add64( &temp, &temp2, &temp );
567       q = ft_div64by32( temp.hi, temp.lo, (FT_Int32)b );
568     }
569 
570     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
571   }
572 
573 
574 #if 0
575 
576   /* documentation is in ftcalc.h */
577 
578   FT_EXPORT_DEF( void )
579   FT_MulTo64( FT_Int32   x,
580               FT_Int32   y,
581               FT_Int64  *z )
582   {
583     FT_Int32  s;
584 
585 
586     s  = x; x = FT_ABS( x );
587     s ^= y; y = FT_ABS( y );
588 
589     ft_multo64( x, y, z );
590 
591     if ( s < 0 )
592     {
593       z->lo = (FT_UInt32)-(FT_Int32)z->lo;
594       z->hi = ~z->hi + !( z->lo );
595     }
596   }
597 
598 
599   /* apparently, the second version of this code is not compiled correctly */
600   /* on Mac machines with the MPW C compiler..  tsk, tsk, tsk...           */
601 
602 #if 1
603 
604   FT_EXPORT_DEF( FT_Int32 )
605   FT_Div64by32( FT_Int64*  x,
606                 FT_Int32   y )
607   {
608     FT_Int32   s;
609     FT_UInt32  q, r, i, lo;
610 
611 
612     s  = x->hi;
613     if ( s < 0 )
614     {
615       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
616       x->hi = ~x->hi + !x->lo;
617     }
618     s ^= y;  y = FT_ABS( y );
619 
620     /* Shortcut */
621     if ( x->hi == 0 )
622     {
623       if ( y > 0 )
624         q = x->lo / y;
625       else
626         q = 0x7FFFFFFFL;
627 
628       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
629     }
630 
631     r  = x->hi;
632     lo = x->lo;
633 
634     if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */
635       return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL );
636                              /* Return Max/Min Int32 if division overflow. */
637                              /* This includes division by zero!            */
638     q = 0;
639     for ( i = 0; i < 32; i++ )
640     {
641       r <<= 1;
642       q <<= 1;
643       r  |= lo >> 31;
644 
645       if ( r >= (FT_UInt32)y )
646       {
647         r -= y;
648         q |= 1;
649       }
650       lo <<= 1;
651     }
652 
653     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
654   }
655 
656 #else /* 0 */
657 
658   FT_EXPORT_DEF( FT_Int32 )
659   FT_Div64by32( FT_Int64*  x,
660                 FT_Int32   y )
661   {
662     FT_Int32   s;
663     FT_UInt32  q;
664 
665 
666     s  = x->hi;
667     if ( s < 0 )
668     {
669       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
670       x->hi = ~x->hi + !x->lo;
671     }
672     s ^= y;  y = FT_ABS( y );
673 
674     /* Shortcut */
675     if ( x->hi == 0 )
676     {
677       if ( y > 0 )
678         q = ( x->lo + ( y >> 1 ) ) / y;
679       else
680         q = 0x7FFFFFFFL;
681 
682       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
683     }
684 
685     q = ft_div64by32( x->hi, x->lo, y );
686 
687     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
688   }
689 
690 #endif /* 0 */
691 
692 #endif /* 0 */
693 
694 
695 #endif /* FT_LONG64 */
696 
697 
698   /* documentation is in ftglyph.h */
699 
700   FT_EXPORT_DEF( void )
FT_Matrix_Multiply(const FT_Matrix * a,FT_Matrix * b)701   FT_Matrix_Multiply( const FT_Matrix*  a,
702                       FT_Matrix        *b )
703   {
704     FT_Fixed  xx, xy, yx, yy;
705 
706 
707     if ( !a || !b )
708       return;
709 
710     xx = FT_MulFix( a->xx, b->xx ) + FT_MulFix( a->xy, b->yx );
711     xy = FT_MulFix( a->xx, b->xy ) + FT_MulFix( a->xy, b->yy );
712     yx = FT_MulFix( a->yx, b->xx ) + FT_MulFix( a->yy, b->yx );
713     yy = FT_MulFix( a->yx, b->xy ) + FT_MulFix( a->yy, b->yy );
714 
715     b->xx = xx;  b->xy = xy;
716     b->yx = yx;  b->yy = yy;
717   }
718 
719 
720   /* documentation is in ftglyph.h */
721 
722   FT_EXPORT_DEF( FT_Error )
FT_Matrix_Invert(FT_Matrix * matrix)723   FT_Matrix_Invert( FT_Matrix*  matrix )
724   {
725     FT_Pos  delta, xx, yy;
726 
727 
728     if ( !matrix )
729       return FT_Err_Invalid_Argument;
730 
731     /* compute discriminant */
732     delta = FT_MulFix( matrix->xx, matrix->yy ) -
733             FT_MulFix( matrix->xy, matrix->yx );
734 
735     if ( !delta )
736       return FT_Err_Invalid_Argument;  /* matrix can't be inverted */
737 
738     matrix->xy = - FT_DivFix( matrix->xy, delta );
739     matrix->yx = - FT_DivFix( matrix->yx, delta );
740 
741     xx = matrix->xx;
742     yy = matrix->yy;
743 
744     matrix->xx = FT_DivFix( yy, delta );
745     matrix->yy = FT_DivFix( xx, delta );
746 
747     return FT_Err_Ok;
748   }
749 
750 
751   /* documentation is in ftcalc.h */
752 
753   FT_BASE_DEF( void )
FT_Matrix_Multiply_Scaled(const FT_Matrix * a,FT_Matrix * b,FT_Long scaling)754   FT_Matrix_Multiply_Scaled( const FT_Matrix*  a,
755                              FT_Matrix        *b,
756                              FT_Long           scaling )
757   {
758     FT_Fixed  xx, xy, yx, yy;
759 
760     FT_Long   val = 0x10000L * scaling;
761 
762 
763     if ( !a || !b )
764       return;
765 
766     xx = FT_MulDiv( a->xx, b->xx, val ) + FT_MulDiv( a->xy, b->yx, val );
767     xy = FT_MulDiv( a->xx, b->xy, val ) + FT_MulDiv( a->xy, b->yy, val );
768     yx = FT_MulDiv( a->yx, b->xx, val ) + FT_MulDiv( a->yy, b->yx, val );
769     yy = FT_MulDiv( a->yx, b->xy, val ) + FT_MulDiv( a->yy, b->yy, val );
770 
771     b->xx = xx;  b->xy = xy;
772     b->yx = yx;  b->yy = yy;
773   }
774 
775 
776   /* documentation is in ftcalc.h */
777 
778   FT_BASE_DEF( void )
FT_Vector_Transform_Scaled(FT_Vector * vector,const FT_Matrix * matrix,FT_Long scaling)779   FT_Vector_Transform_Scaled( FT_Vector*        vector,
780                               const FT_Matrix*  matrix,
781                               FT_Long           scaling )
782   {
783     FT_Pos   xz, yz;
784 
785     FT_Long  val = 0x10000L * scaling;
786 
787 
788     if ( !vector || !matrix )
789       return;
790 
791     xz = FT_MulDiv( vector->x, matrix->xx, val ) +
792          FT_MulDiv( vector->y, matrix->xy, val );
793 
794     yz = FT_MulDiv( vector->x, matrix->yx, val ) +
795          FT_MulDiv( vector->y, matrix->yy, val );
796 
797     vector->x = xz;
798     vector->y = yz;
799   }
800 
801 
802   /* documentation is in ftcalc.h */
803 
804   FT_BASE_DEF( FT_Int32 )
FT_SqrtFixed(FT_Int32 x)805   FT_SqrtFixed( FT_Int32  x )
806   {
807     FT_UInt32  root, rem_hi, rem_lo, test_div;
808     FT_Int     count;
809 
810 
811     root = 0;
812 
813     if ( x > 0 )
814     {
815       rem_hi = 0;
816       rem_lo = x;
817       count  = 24;
818       do
819       {
820         rem_hi   = ( rem_hi << 2 ) | ( rem_lo >> 30 );
821         rem_lo <<= 2;
822         root   <<= 1;
823         test_div = ( root << 1 ) + 1;
824 
825         if ( rem_hi >= test_div )
826         {
827           rem_hi -= test_div;
828           root   += 1;
829         }
830       } while ( --count );
831     }
832 
833     return (FT_Int32)root;
834   }
835 
836 
837   /* documentation is in ftcalc.h */
838 
839   FT_BASE_DEF( FT_Int )
ft_corner_orientation(FT_Pos in_x,FT_Pos in_y,FT_Pos out_x,FT_Pos out_y)840   ft_corner_orientation( FT_Pos  in_x,
841                          FT_Pos  in_y,
842                          FT_Pos  out_x,
843                          FT_Pos  out_y )
844   {
845     FT_Long  result; /* avoid overflow on 16-bit system */
846 
847 
848     /* deal with the trivial cases quickly */
849     if ( in_y == 0 )
850     {
851       if ( in_x >= 0 )
852         result = out_y;
853       else
854         result = -out_y;
855     }
856     else if ( in_x == 0 )
857     {
858       if ( in_y >= 0 )
859         result = -out_x;
860       else
861         result = out_x;
862     }
863     else if ( out_y == 0 )
864     {
865       if ( out_x >= 0 )
866         result = in_y;
867       else
868         result = -in_y;
869     }
870     else if ( out_x == 0 )
871     {
872       if ( out_y >= 0 )
873         result = -in_x;
874       else
875         result =  in_x;
876     }
877     else /* general case */
878     {
879 #ifdef FT_LONG64
880 
881       FT_Int64  delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x;
882 
883 
884       if ( delta == 0 )
885         result = 0;
886       else
887         result = 1 - 2 * ( delta < 0 );
888 
889 #else
890 
891       FT_Int64  z1, z2;
892 
893 
894       /* XXX: this function does not allow 64-bit arguments */
895       ft_multo64( (FT_Int32)in_x, (FT_Int32)out_y, &z1 );
896       ft_multo64( (FT_Int32)in_y, (FT_Int32)out_x, &z2 );
897 
898       if ( z1.hi > z2.hi )
899         result = +1;
900       else if ( z1.hi < z2.hi )
901         result = -1;
902       else if ( z1.lo > z2.lo )
903         result = +1;
904       else if ( z1.lo < z2.lo )
905         result = -1;
906       else
907         result = 0;
908 
909 #endif
910     }
911 
912     /* XXX: only the sign of return value, +1/0/-1 must be used */
913     return (FT_Int)result;
914   }
915 
916 
917   /* documentation is in ftcalc.h */
918 
919   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)920   ft_corner_is_flat( FT_Pos  in_x,
921                      FT_Pos  in_y,
922                      FT_Pos  out_x,
923                      FT_Pos  out_y )
924   {
925     FT_Pos  ax = in_x;
926     FT_Pos  ay = in_y;
927 
928     FT_Pos  d_in, d_out, d_corner;
929 
930 
931     if ( ax < 0 )
932       ax = -ax;
933     if ( ay < 0 )
934       ay = -ay;
935     d_in = ax + ay;
936 
937     ax = out_x;
938     if ( ax < 0 )
939       ax = -ax;
940     ay = out_y;
941     if ( ay < 0 )
942       ay = -ay;
943     d_out = ax + ay;
944 
945     ax = out_x + in_x;
946     if ( ax < 0 )
947       ax = -ax;
948     ay = out_y + in_y;
949     if ( ay < 0 )
950       ay = -ay;
951     d_corner = ax + ay;
952 
953     return ( d_in + d_out - d_corner ) < ( d_corner >> 4 );
954   }
955 
956 
957 /* END */
958