1 /***************************************************************************/
2 /* */
3 /* fttrigon.c */
4 /* */
5 /* FreeType trigonometric functions (body). */
6 /* */
7 /* Copyright 2001-2018 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 /* This is a fixed-point CORDIC implementation of trigonometric */
21 /* functions as well as transformations between Cartesian and polar */
22 /* coordinates. The angles are represented as 16.16 fixed-point values */
23 /* in degrees, i.e., the angular resolution is 2^-16 degrees. Note that */
24 /* only vectors longer than 2^16*180/pi (or at least 22 bits) on a */
25 /* discrete Cartesian grid can have the same or better angular */
26 /* resolution. Therefore, to maintain this precision, some functions */
27 /* require an interim upscaling of the vectors, whereas others operate */
28 /* with 24-bit long vectors directly. */
29 /* */
30 /*************************************************************************/
31
32 #include <ft2build.h>
33 #include FT_INTERNAL_OBJECTS_H
34 #include FT_INTERNAL_CALC_H
35 #include FT_TRIGONOMETRY_H
36
37
38 /* the Cordic shrink factor 0.858785336480436 * 2^32 */
39 #define FT_TRIG_SCALE 0xDBD95B16UL
40
41 /* the highest bit in overflow-safe vector components, */
42 /* MSB of 0.858785336480436 * sqrt(0.5) * 2^30 */
43 #define FT_TRIG_SAFE_MSB 29
44
45 /* this table was generated for FT_PI = 180L << 16, i.e. degrees */
46 #define FT_TRIG_MAX_ITERS 23
47
48 static const FT_Angle
49 ft_trig_arctan_table[] =
50 {
308
309 /* documentation is in fttrigon.h */
310
311 FT_EXPORT_DEF( FT_Fixed )
312 FT_Sin( FT_Angle angle )
313 {
314 FT_Vector v;
315
316
317 FT_Vector_Unit( &v, angle );
318
319 return v.y;
320 }
321
322
323 /* documentation is in fttrigon.h */
324
325 FT_EXPORT_DEF( FT_Fixed )
326 FT_Tan( FT_Angle angle )
327 {
328 FT_Vector v;
329
330
331 FT_Vector_Unit( &v, angle );
332
333 return FT_DivFix( v.y, v.x );
334 }
335
336
337 /* documentation is in fttrigon.h */
338
339 FT_EXPORT_DEF( FT_Angle )
340 FT_Atan2( FT_Fixed dx,
341 FT_Fixed dy )
342 {
343 FT_Vector v;
344
345
346 if ( dx == 0 && dy == 0 )
347 return 0;
348
349 v.x = dx;
350 v.y = dy;
351 ft_trig_prenorm( &v );
355 }
356
357
358 /* documentation is in fttrigon.h */
359
360 FT_EXPORT_DEF( void )
361 FT_Vector_Unit( FT_Vector* vec,
362 FT_Angle angle )
363 {
364 if ( !vec )
365 return;
366
367 vec->x = FT_TRIG_SCALE >> 8;
368 vec->y = 0;
369 ft_trig_pseudo_rotate( vec, angle );
370 vec->x = ( vec->x + 0x80L ) >> 8;
371 vec->y = ( vec->y + 0x80L ) >> 8;
372 }
373
374
375 /* these macros return 0 for positive numbers,
376 and -1 for negative ones */
377 #define FT_SIGN_LONG( x ) ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) )
378 #define FT_SIGN_INT( x ) ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) )
379 #define FT_SIGN_INT32( x ) ( (x) >> 31 )
380 #define FT_SIGN_INT16( x ) ( (x) >> 15 )
381
382
383 /* documentation is in fttrigon.h */
384
385 FT_EXPORT_DEF( void )
386 FT_Vector_Rotate( FT_Vector* vec,
387 FT_Angle angle )
388 {
389 FT_Int shift;
390 FT_Vector v;
391
392
393 if ( !vec || !angle )
394 return;
395
396 v = *vec;
397
398 if ( v.x == 0 && v.y == 0 )
399 return;
400
401 shift = ft_trig_prenorm( &v );
402 ft_trig_pseudo_rotate( &v, angle );
403 v.x = ft_trig_downscale( v.x );
404 v.y = ft_trig_downscale( v.y );
405
406 if ( shift > 0 )
407 {
408 FT_Int32 half = (FT_Int32)1L << ( shift - 1 );
409
410
411 vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift;
412 vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift;
413 }
414 else
415 {
416 shift = -shift;
417 vec->x = (FT_Pos)( (FT_ULong)v.x << shift );
418 vec->y = (FT_Pos)( (FT_ULong)v.y << shift );
419 }
420 }
421
422
423 /* documentation is in fttrigon.h */
424
425 FT_EXPORT_DEF( FT_Fixed )
426 FT_Vector_Length( FT_Vector* vec )
427 {
428 FT_Int shift;
429 FT_Vector v;
430
431
432 if ( !vec )
|
1 /****************************************************************************
2 *
3 * fttrigon.c
4 *
5 * FreeType trigonometric functions (body).
6 *
7 * Copyright (C) 2001-2019 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 * This is a fixed-point CORDIC implementation of trigonometric
21 * functions as well as transformations between Cartesian and polar
22 * coordinates. The angles are represented as 16.16 fixed-point values
23 * in degrees, i.e., the angular resolution is 2^-16 degrees. Note that
24 * only vectors longer than 2^16*180/pi (or at least 22 bits) on a
25 * discrete Cartesian grid can have the same or better angular
26 * resolution. Therefore, to maintain this precision, some functions
27 * require an interim upscaling of the vectors, whereas others operate
28 * with 24-bit long vectors directly.
29 *
30 */
31
32 #include <ft2build.h>
33 #include FT_INTERNAL_OBJECTS_H
34 #include FT_INTERNAL_CALC_H
35 #include FT_TRIGONOMETRY_H
36
37
38 /* the Cordic shrink factor 0.858785336480436 * 2^32 */
39 #define FT_TRIG_SCALE 0xDBD95B16UL
40
41 /* the highest bit in overflow-safe vector components, */
42 /* MSB of 0.858785336480436 * sqrt(0.5) * 2^30 */
43 #define FT_TRIG_SAFE_MSB 29
44
45 /* this table was generated for FT_PI = 180L << 16, i.e. degrees */
46 #define FT_TRIG_MAX_ITERS 23
47
48 static const FT_Angle
49 ft_trig_arctan_table[] =
50 {
308
309 /* documentation is in fttrigon.h */
310
311 FT_EXPORT_DEF( FT_Fixed )
312 FT_Sin( FT_Angle angle )
313 {
314 FT_Vector v;
315
316
317 FT_Vector_Unit( &v, angle );
318
319 return v.y;
320 }
321
322
323 /* documentation is in fttrigon.h */
324
325 FT_EXPORT_DEF( FT_Fixed )
326 FT_Tan( FT_Angle angle )
327 {
328 FT_Vector v = { 1 << 24, 0 };
329
330
331 ft_trig_pseudo_rotate( &v, angle );
332
333 return FT_DivFix( v.y, v.x );
334 }
335
336
337 /* documentation is in fttrigon.h */
338
339 FT_EXPORT_DEF( FT_Angle )
340 FT_Atan2( FT_Fixed dx,
341 FT_Fixed dy )
342 {
343 FT_Vector v;
344
345
346 if ( dx == 0 && dy == 0 )
347 return 0;
348
349 v.x = dx;
350 v.y = dy;
351 ft_trig_prenorm( &v );
355 }
356
357
358 /* documentation is in fttrigon.h */
359
360 FT_EXPORT_DEF( void )
361 FT_Vector_Unit( FT_Vector* vec,
362 FT_Angle angle )
363 {
364 if ( !vec )
365 return;
366
367 vec->x = FT_TRIG_SCALE >> 8;
368 vec->y = 0;
369 ft_trig_pseudo_rotate( vec, angle );
370 vec->x = ( vec->x + 0x80L ) >> 8;
371 vec->y = ( vec->y + 0x80L ) >> 8;
372 }
373
374
375 /* documentation is in fttrigon.h */
376
377 FT_EXPORT_DEF( void )
378 FT_Vector_Rotate( FT_Vector* vec,
379 FT_Angle angle )
380 {
381 FT_Int shift;
382 FT_Vector v;
383
384
385 if ( !vec || !angle )
386 return;
387
388 v = *vec;
389
390 if ( v.x == 0 && v.y == 0 )
391 return;
392
393 shift = ft_trig_prenorm( &v );
394 ft_trig_pseudo_rotate( &v, angle );
395 v.x = ft_trig_downscale( v.x );
396 v.y = ft_trig_downscale( v.y );
397
398 if ( shift > 0 )
399 {
400 FT_Int32 half = (FT_Int32)1L << ( shift - 1 );
401
402
403 vec->x = ( v.x + half - ( v.x < 0 ) ) >> shift;
404 vec->y = ( v.y + half - ( v.y < 0 ) ) >> shift;
405 }
406 else
407 {
408 shift = -shift;
409 vec->x = (FT_Pos)( (FT_ULong)v.x << shift );
410 vec->y = (FT_Pos)( (FT_ULong)v.y << shift );
411 }
412 }
413
414
415 /* documentation is in fttrigon.h */
416
417 FT_EXPORT_DEF( FT_Fixed )
418 FT_Vector_Length( FT_Vector* vec )
419 {
420 FT_Int shift;
421 FT_Vector v;
422
423
424 if ( !vec )
|