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