← Back to branch summary

~ubuntu-branches/ubuntu/utopic/hedgewars/utopic

« back to all changes in this revision

Viewing changes to misc/libfreetype/src/base/fttrigon.c

  • Committer: Package Import Robot
  • Author(s): Gianfranco Costamagna
  • Date: 2014-01-02 12:37:23 UTC
  • mfrom: (19.1.5 sid)
  • Revision ID: package-import@ubuntu.com-20140102123723-6pdhmyj8tb5y8xbg
Tags: 0.9.20.3-1
New upstream minor release, suitable for unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
misc/libfreetype/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_UInt32)FT_TRIG_SCALE >> 16;       /* constant */
78
 
    k2 = (FT_UInt32)(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 += (FT_UInt32)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 = (FT_Int32)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 */