← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/texlive-bin/jaunty-security

« back to all changes in this revision

Viewing changes to build/source/libs/freetype2/src/base/fttrigon.c

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Preining
  • Date: 2008-06-26 23:14:59 UTC
  • mfrom: (2.1.30 intrepid)
  • Revision ID: james.westby@ubuntu.com-20080626231459-y02rjsrgtafu83yr
Tags: 2007.dfsg.2-3
http://bugs.debian.org/482915
add missing source roadmap.fig of roadmap.eps in fontinst documentation
(Closes: #482915) (urgency medium due to RC bug)
(new patch add-missing-fontinst-source)

Show diffs side-by-side

added added

removed removed

Lines of Context:
build/source/libs/freetype2/src/base/fttrigon.c
 
1
/***************************************************************************/
 
2
/*                                                                         */
 
3
/*  fttrigon.c                                                             */
 
4
/*                                                                         */
 
5
/*    FreeType trigonometric functions (body).                             */
 
6
/*                                                                         */
 
7
/*  Copyright 2001, 2002, 2003, 2004, 2005 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
#include <ft2build.h>
 
20
#include FT_INTERNAL_OBJECTS_H
 
21
#include FT_TRIGONOMETRY_H
 
22
 
 
23
 
 
24
  /* the following is 0.2715717684432231 * 2^30 */
 
25
#define FT_TRIG_COSCALE  0x11616E8EUL
 
26
 
 
27
  /* this table was generated for FT_PI = 180L << 16, i.e. degrees */
 
28
#define FT_TRIG_MAX_ITERS  23
 
29
 
 
30
  static const FT_Fixed
 
31
  ft_trig_arctan_table[24] =
 
32
  {
 
33
    4157273L, 2949120L, 1740967L, 919879L, 466945L, 234379L, 117304L,
 
34
    58666L, 29335L, 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
 
35
    57L, 29L, 14L, 7L, 4L, 2L, 1L
 
36
  };
 
37
 
 
38
  /* the Cordic shrink factor, multiplied by 2^32 */
 
39
#define FT_TRIG_SCALE    1166391785UL  /* 0x4585BA38UL */
 
40
 
 
41
 
 
42
#ifdef FT_CONFIG_HAS_INT64
 
43
 
 
44
  /* multiply a given value by the CORDIC shrink factor */
 
45
  static FT_Fixed
 
46
  ft_trig_downscale( FT_Fixed  val )
 
47
  {
 
48
    FT_Fixed  s;
 
49
    FT_Int64  v;
 
50
 
 
51
 
 
52
    s   = val;
 
53
    val = ( val >= 0 ) ? val : -val;
 
54
 
 
55
    v   = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL;
 
56
    val = (FT_Fixed)( v >> 32 );
 
57
 
 
58
    return ( s >= 0 ) ? val : -val;
 
59
  }
 
60
 
 
61
#else /* !FT_CONFIG_HAS_INT64 */
 
62
 
 
63
  /* multiply a given value by the CORDIC shrink factor */
 
64
  static FT_Fixed
 
65
  ft_trig_downscale( FT_Fixed  val )
 
66
  {
 
67
    FT_Fixed   s;
 
68
    FT_UInt32  v1, v2, k1, k2, hi, lo1, lo2, lo3;
 
69
 
 
70
 
 
71
    s   = val;
 
72
    val = ( val >= 0 ) ? val : -val;
 
73
 
 
74
    v1 = (FT_UInt32)val >> 16;
 
75
    v2 = (FT_UInt32)val & 0xFFFFL;
 
76
 
 
77
    k1 = FT_TRIG_SCALE >> 16;       /* constant */
 
78
    k2 = FT_TRIG_SCALE & 0xFFFFL;   /* constant */
 
79
 
 
80
    hi   = k1 * v1;
 
81
    lo1  = k1 * v2 + k2 * v1;       /* can't overflow */
 
82
 
 
83
    lo2  = ( k2 * v2 ) >> 16;
 
84
    lo3  = ( lo1 >= lo2 ) ? lo1 : lo2;
 
85
    lo1 += lo2;
 
86
 
 
87
    hi  += lo1 >> 16;
 
88
    if ( lo1 < lo3 )
 
89
      hi += 0x10000UL;
 
90
 
 
91
    val  = (FT_Fixed)hi;
 
92
 
 
93
    return ( s >= 0 ) ? val : -val;
 
94
  }
 
95
 
 
96
#endif /* !FT_CONFIG_HAS_INT64 */
 
97
 
 
98
 
 
99
  static FT_Int
 
100
  ft_trig_prenorm( FT_Vector*  vec )
 
101
  {
 
102
    FT_Fixed  x, y, z;
 
103
    FT_Int    shift;
 
104
 
 
105
 
 
106
    x = vec->x;
 
107
    y = vec->y;
 
108
 
 
109
    z     = ( ( x >= 0 ) ? x : - x ) | ( (y >= 0) ? y : -y );
 
110
    shift = 0;
 
111
 
 
112
#if 1
 
113
    /* determine msb bit index in `shift' */
 
114
    if ( z >= ( 1L << 16 ) )
 
115
    {
 
116
      z     >>= 16;
 
117
      shift  += 16;
 
118
    }
 
119
    if ( z >= ( 1L << 8 ) )
 
120
    {
 
121
      z     >>= 8;
 
122
      shift  += 8;
 
123
    }
 
124
    if ( z >= ( 1L << 4 ) )
 
125
    {
 
126
      z     >>= 4;
 
127
      shift  += 4;
 
128
    }
 
129
    if ( z >= ( 1L << 2 ) )
 
130
    {
 
131
      z     >>= 2;
 
132
      shift  += 2;
 
133
    }
 
134
    if ( z >= ( 1L << 1 ) )
 
135
    {
 
136
      z    >>= 1;
 
137
      shift += 1;
 
138
    }
 
139
 
 
140
    if ( shift <= 27 )
 
141
    {
 
142
      shift  = 27 - shift;
 
143
      vec->x = x << shift;
 
144
      vec->y = y << shift;
 
145
    }
 
146
    else
 
147
    {
 
148
      shift -= 27;
 
149
      vec->x = x >> shift;
 
150
      vec->y = y >> shift;
 
151
      shift  = -shift;
 
152
    }
 
153
 
 
154
#else /* 0 */
 
155
 
 
156
    if ( z < ( 1L << 27 ) )
 
157
    {
 
158
      do
 
159
      {
 
160
        shift++;
 
161
        z <<= 1;
 
162
      } while ( z < ( 1L << 27 ) );
 
163
      vec->x = x << shift;
 
164
      vec->y = y << shift;
 
165
    }
 
166
    else if ( z > ( 1L << 28 ) )
 
167
    {
 
168
      do
 
169
      {
 
170
        shift++;
 
171
        z >>= 1;
 
172
      } while ( z > ( 1L << 28 ) );
 
173
 
 
174
      vec->x = x >> shift;
 
175
      vec->y = y >> shift;
 
176
      shift  = -shift;
 
177
    }
 
178
 
 
179
#endif /* 0 */
 
180
 
 
181
    return shift;
 
182
  }
 
183
 
 
184
 
 
185
  static void
 
186
  ft_trig_pseudo_rotate( FT_Vector*  vec,
 
187
                         FT_Angle    theta )
 
188
  {
 
189
    FT_Int           i;
 
190
    FT_Fixed         x, y, xtemp;
 
191
    const FT_Fixed  *arctanptr;
 
192
 
 
193
 
 
194
    x = vec->x;
 
195
    y = vec->y;
 
196
 
 
197
    /* Get angle between -90 and 90 degrees */
 
198
    while ( theta <= -FT_ANGLE_PI2 )
 
199
    {
 
200
      x = -x;
 
201
      y = -y;
 
202
      theta += FT_ANGLE_PI;
 
203
    }
 
204
 
 
205
    while ( theta > FT_ANGLE_PI2 )
 
206
    {
 
207
      x = -x;
 
208
      y = -y;
 
209
      theta -= FT_ANGLE_PI;
 
210
    }
 
211
 
 
212
    /* Initial pseudorotation, with left shift */
 
213
    arctanptr = ft_trig_arctan_table;
 
214
 
 
215
    if ( theta < 0 )
 
216
    {
 
217
      xtemp  = x + ( y << 1 );
 
218
      y      = y - ( x << 1 );
 
219
      x      = xtemp;
 
220
      theta += *arctanptr++;
 
221
    }
 
222
    else
 
223
    {
 
224
      xtemp  = x - ( y << 1 );
 
225
      y      = y + ( x << 1 );
 
226
      x      = xtemp;
 
227
      theta -= *arctanptr++;
 
228
    }
 
229
 
 
230
    /* Subsequent pseudorotations, with right shifts */
 
231
    i = 0;
 
232
    do
 
233
    {
 
234
      if ( theta < 0 )
 
235
      {
 
236
        xtemp  = x + ( y >> i );
 
237
        y      = y - ( x >> i );
 
238
        x      = xtemp;
 
239
        theta += *arctanptr++;
 
240
      }
 
241
      else
 
242
      {
 
243
        xtemp  = x - ( y >> i );
 
244
        y      = y + ( x >> i );
 
245
        x      = xtemp;
 
246
        theta -= *arctanptr++;
 
247
      }
 
248
    } while ( ++i < FT_TRIG_MAX_ITERS );
 
249
 
 
250
    vec->x = x;
 
251
    vec->y = y;
 
252
  }
 
253
 
 
254
 
 
255
  static void
 
256
  ft_trig_pseudo_polarize( FT_Vector*  vec )
 
257
  {
 
258
    FT_Fixed         theta;
 
259
    FT_Fixed         yi, i;
 
260
    FT_Fixed         x, y;
 
261
    const FT_Fixed  *arctanptr;
 
262
 
 
263
 
 
264
    x = vec->x;
 
265
    y = vec->y;
 
266
 
 
267
    /* Get the vector into the right half plane */
 
268
    theta = 0;
 
269
    if ( x < 0 )
 
270
    {
 
271
      x = -x;
 
272
      y = -y;
 
273
      theta = 2 * FT_ANGLE_PI2;
 
274
    }
 
275
 
 
276
    if ( y > 0 )
 
277
      theta = - theta;
 
278
 
 
279
    arctanptr = ft_trig_arctan_table;
 
280
 
 
281
    if ( y < 0 )
 
282
    {
 
283
      /* Rotate positive */
 
284
      yi     = y + ( x << 1 );
 
285
      x      = x - ( y << 1 );
 
286
      y      = yi;
 
287
      theta -= *arctanptr++;  /* Subtract angle */
 
288
    }
 
289
    else
 
290
    {
 
291
      /* Rotate negative */
 
292
      yi     = y - ( x << 1 );
 
293
      x      = x + ( y << 1 );
 
294
      y      = yi;
 
295
      theta += *arctanptr++;  /* Add angle */
 
296
    }
 
297
 
 
298
    i = 0;
 
299
    do
 
300
    {
 
301
      if ( y < 0 )
 
302
      {
 
303
        /* Rotate positive */
 
304
        yi     = y + ( x >> i );
 
305
        x      = x - ( y >> i );
 
306
        y      = yi;
 
307
        theta -= *arctanptr++;
 
308
      }
 
309
      else
 
310
      {
 
311
        /* Rotate negative */
 
312
        yi     = y - ( x >> i );
 
313
        x      = x + ( y >> i );
 
314
        y      = yi;
 
315
        theta += *arctanptr++;
 
316
      }
 
317
    } while ( ++i < FT_TRIG_MAX_ITERS );
 
318
 
 
319
    /* round theta */
 
320
    if ( theta >= 0 )
 
321
      theta = FT_PAD_ROUND( theta, 32 );
 
322
    else
 
323
      theta = -FT_PAD_ROUND( -theta, 32 );
 
324
 
 
325
    vec->x = x;
 
326
    vec->y = theta;
 
327
  }
 
328
 
 
329
 
 
330
  /* documentation is in fttrigon.h */
 
331
 
 
332
  FT_EXPORT_DEF( FT_Fixed )
 
333
  FT_Cos( FT_Angle  angle )
 
334
  {
 
335
    FT_Vector  v;
 
336
 
 
337
 
 
338
    v.x = FT_TRIG_COSCALE >> 2;
 
339
    v.y = 0;
 
340
    ft_trig_pseudo_rotate( &v, angle );
 
341
 
 
342
    return v.x / ( 1 << 12 );
 
343
  }
 
344
 
 
345
 
 
346
  /* documentation is in fttrigon.h */
 
347
 
 
348
  FT_EXPORT_DEF( FT_Fixed )
 
349
  FT_Sin( FT_Angle  angle )
 
350
  {
 
351
    return FT_Cos( FT_ANGLE_PI2 - angle );
 
352
  }
 
353
 
 
354
 
 
355
  /* documentation is in fttrigon.h */
 
356
 
 
357
  FT_EXPORT_DEF( FT_Fixed )
 
358
  FT_Tan( FT_Angle  angle )
 
359
  {
 
360
    FT_Vector  v;
 
361
 
 
362
 
 
363
    v.x = FT_TRIG_COSCALE >> 2;
 
364
    v.y = 0;
 
365
    ft_trig_pseudo_rotate( &v, angle );
 
366
 
 
367
    return FT_DivFix( v.y, v.x );
 
368
  }
 
369
 
 
370
 
 
371
  /* documentation is in fttrigon.h */
 
372
 
 
373
  FT_EXPORT_DEF( FT_Angle )
 
374
  FT_Atan2( FT_Fixed  dx,
 
375
            FT_Fixed  dy )
 
376
  {
 
377
    FT_Vector  v;
 
378
 
 
379
 
 
380
    if ( dx == 0 && dy == 0 )
 
381
      return 0;
 
382
 
 
383
    v.x = dx;
 
384
    v.y = dy;
 
385
    ft_trig_prenorm( &v );
 
386
    ft_trig_pseudo_polarize( &v );
 
387
 
 
388
    return v.y;
 
389
  }
 
390
 
 
391
 
 
392
  /* documentation is in fttrigon.h */
 
393
 
 
394
  FT_EXPORT_DEF( void )
 
395
  FT_Vector_Unit( FT_Vector*  vec,
 
396
                  FT_Angle    angle )
 
397
  {
 
398
    vec->x = FT_TRIG_COSCALE >> 2;
 
399
    vec->y = 0;
 
400
    ft_trig_pseudo_rotate( vec, angle );
 
401
    vec->x >>= 12;
 
402
    vec->y >>= 12;
 
403
  }
 
404
 
 
405
 
 
406
  /* these macros return 0 for positive numbers,
 
407
     and -1 for negative ones */
 
408
#define FT_SIGN_LONG( x )   ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) )
 
409
#define FT_SIGN_INT( x )    ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) )
 
410
#define FT_SIGN_INT32( x )  ( (x) >> 31 )
 
411
#define FT_SIGN_INT16( x )  ( (x) >> 15 )
 
412
 
 
413
 
 
414
  /* documentation is in fttrigon.h */
 
415
 
 
416
  FT_EXPORT_DEF( void )
 
417
  FT_Vector_Rotate( FT_Vector*  vec,
 
418
                    FT_Angle    angle )
 
419
  {
 
420
    FT_Int     shift;
 
421
    FT_Vector  v;
 
422
 
 
423
 
 
424
    v.x   = vec->x;
 
425
    v.y   = vec->y;
 
426
 
 
427
    if ( angle && ( v.x != 0 || v.y != 0 ) )
 
428
    {
 
429
      shift = ft_trig_prenorm( &v );
 
430
      ft_trig_pseudo_rotate( &v, angle );
 
431
      v.x = ft_trig_downscale( v.x );
 
432
      v.y = ft_trig_downscale( v.y );
 
433
 
 
434
      if ( shift > 0 )
 
435
      {
 
436
        FT_Int32  half = 1L << ( shift - 1 );
 
437
 
 
438
 
 
439
        vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift;
 
440
        vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift;
 
441
      }
 
442
      else
 
443
      {
 
444
        shift  = -shift;
 
445
        vec->x = v.x << shift;
 
446
        vec->y = v.y << shift;
 
447
      }
 
448
    }
 
449
  }
 
450
 
 
451
 
 
452
  /* documentation is in fttrigon.h */
 
453
 
 
454
  FT_EXPORT_DEF( FT_Fixed )
 
455
  FT_Vector_Length( FT_Vector*  vec )
 
456
  {
 
457
    FT_Int     shift;
 
458
    FT_Vector  v;
 
459
 
 
460
 
 
461
    v = *vec;
 
462
 
 
463
    /* handle trivial cases */
 
464
    if ( v.x == 0 )
 
465
    {
 
466
      return ( v.y >= 0 ) ? v.y : -v.y;
 
467
    }
 
468
    else if ( v.y == 0 )
 
469
    {
 
470
      return ( v.x >= 0 ) ? v.x : -v.x;
 
471
    }
 
472
 
 
473
    /* general case */
 
474
    shift = ft_trig_prenorm( &v );
 
475
    ft_trig_pseudo_polarize( &v );
 
476
 
 
477
    v.x = ft_trig_downscale( v.x );
 
478
 
 
479
    if ( shift > 0 )
 
480
      return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift;
 
481
 
 
482
    return v.x << -shift;
 
483
  }
 
484
 
 
485
 
 
486
  /* documentation is in fttrigon.h */
 
487
 
 
488
  FT_EXPORT_DEF( void )
 
489
  FT_Vector_Polarize( FT_Vector*  vec,
 
490
                      FT_Fixed   *length,
 
491
                      FT_Angle   *angle )
 
492
  {
 
493
    FT_Int     shift;
 
494
    FT_Vector  v;
 
495
 
 
496
 
 
497
    v = *vec;
 
498
 
 
499
    if ( v.x == 0 && v.y == 0 )
 
500
      return;
 
501
 
 
502
    shift = ft_trig_prenorm( &v );
 
503
    ft_trig_pseudo_polarize( &v );
 
504
 
 
505
    v.x = ft_trig_downscale( v.x );
 
506
 
 
507
    *length = ( shift >= 0 ) ? ( v.x >> shift ) : ( v.x << -shift );
 
508
    *angle  = v.y;
 
509
  }
 
510
 
 
511
 
 
512
  /* documentation is in fttrigon.h */
 
513
 
 
514
  FT_EXPORT_DEF( void )
 
515
  FT_Vector_From_Polar( FT_Vector*  vec,
 
516
                        FT_Fixed    length,
 
517
                        FT_Angle    angle )
 
518
  {
 
519
    vec->x = length;
 
520
    vec->y = 0;
 
521
 
 
522
    FT_Vector_Rotate( vec, angle );
 
523
  }
 
524
 
 
525
 
 
526
  /* documentation is in fttrigon.h */
 
527
 
 
528
  FT_EXPORT_DEF( FT_Angle )
 
529
  FT_Angle_Diff( FT_Angle  angle1,
 
530
                 FT_Angle  angle2 )
 
531
  {
 
532
    FT_Angle  delta = angle2 - angle1;
 
533
 
 
534
 
 
535
    delta %= FT_ANGLE_2PI;
 
536
    if ( delta < 0 )
 
537
      delta += FT_ANGLE_2PI;
 
538
 
 
539
    if ( delta > FT_ANGLE_PI )
 
540
      delta -= FT_ANGLE_2PI;
 
541
 
 
542
    return delta;
 
543
  }
 
544
 
 
545
 
 
546
/* END */