← Back to branch summary

~gabriel1984sibiu/minitube/qt5.6

« back to all changes in this revision

Viewing changes to src/3rdparty/freetype/src/base/ftcalc.c

  • Committer: Grevutiu Gabriel
  • Date: 2017-06-13 08:43:17 UTC
  • Revision ID: gabriel1984sibiu@gmail.com-20170613084317-ek0zqe0u9g3ocvi8
Original upstream code

Show diffs side-by-side

added added

removed removed

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