1 /****************************************************************************
2  *
3  * afangles.c
4  *
5  *   Routines used to compute vector angles with limited accuracy
6  *   and very high speed.  It also contains sorting routines (body).
7  *
8  * Copyright (C) 2003-2020 by
9  * David Turner, Robert Wilhelm, and Werner Lemberg.
10  *
11  * This file is part of the FreeType project, and may only be used,
12  * modified, and distributed under the terms of the FreeType project
13  * license, LICENSE.TXT.  By continuing to use, modify, or distribute
14  * this file you indicate that you have read the license and
15  * understand and accept it fully.
16  *
17  */
18 
19 
20 #include "aftypes.h"
21 
22 
23   /*
24    * We are not using `af_angle_atan' anymore, but we keep the source
25    * code below just in case...
26    */
27 
28 
29 #if 0
30 
31 
32   /*
33    * The trick here is to realize that we don't need a very accurate angle
34    * approximation.  We are going to use the result of `af_angle_atan' to
35    * only compare the sign of angle differences, or check whether its
36    * magnitude is very small.
37    *
38    * The approximation
39    *
40    *   dy * PI / (|dx|+|dy|)
41    *
42    * should be enough, and much faster to compute.
43    */
44   FT_LOCAL_DEF( AF_Angle )
45   af_angle_atan( FT_Fixed  dx,
46                  FT_Fixed  dy )
47   {
48     AF_Angle  angle;
49     FT_Fixed  ax = dx;
50     FT_Fixed  ay = dy;
51 
52 
53     if ( ax < 0 )
54       ax = -ax;
55     if ( ay < 0 )
56       ay = -ay;
57 
58     ax += ay;
59 
60     if ( ax == 0 )
61       angle = 0;
62     else
63     {
64       angle = ( AF_ANGLE_PI2 * dy ) / ( ax + ay );
65       if ( dx < 0 )
66       {
67         if ( angle >= 0 )
68           angle = AF_ANGLE_PI - angle;
69         else
70           angle = -AF_ANGLE_PI - angle;
71       }
72     }
73 
74     return angle;
75   }
76 
77 
78 #elif 0
79 
80 
81   /* the following table has been automatically generated with */
82   /* the `mather.py' Python script                             */
83 
84 #define AF_ATAN_BITS  8
85 
86   static const FT_Byte  af_arctan[1L << AF_ATAN_BITS] =
87   {
88      0,  0,  1,  1,  1,  2,  2,  2,
89      3,  3,  3,  3,  4,  4,  4,  5,
90      5,  5,  6,  6,  6,  7,  7,  7,
91      8,  8,  8,  9,  9,  9, 10, 10,
92     10, 10, 11, 11, 11, 12, 12, 12,
93     13, 13, 13, 14, 14, 14, 14, 15,
94     15, 15, 16, 16, 16, 17, 17, 17,
95     18, 18, 18, 18, 19, 19, 19, 20,
96     20, 20, 21, 21, 21, 21, 22, 22,
97     22, 23, 23, 23, 24, 24, 24, 24,
98     25, 25, 25, 26, 26, 26, 26, 27,
99     27, 27, 28, 28, 28, 28, 29, 29,
100     29, 30, 30, 30, 30, 31, 31, 31,
101     31, 32, 32, 32, 33, 33, 33, 33,
102     34, 34, 34, 34, 35, 35, 35, 35,
103     36, 36, 36, 36, 37, 37, 37, 38,
104     38, 38, 38, 39, 39, 39, 39, 40,
105     40, 40, 40, 41, 41, 41, 41, 42,
106     42, 42, 42, 42, 43, 43, 43, 43,
107     44, 44, 44, 44, 45, 45, 45, 45,
108     46, 46, 46, 46, 46, 47, 47, 47,
109     47, 48, 48, 48, 48, 48, 49, 49,
110     49, 49, 50, 50, 50, 50, 50, 51,
111     51, 51, 51, 51, 52, 52, 52, 52,
112     52, 53, 53, 53, 53, 53, 54, 54,
113     54, 54, 54, 55, 55, 55, 55, 55,
114     56, 56, 56, 56, 56, 57, 57, 57,
115     57, 57, 57, 58, 58, 58, 58, 58,
116     59, 59, 59, 59, 59, 59, 60, 60,
117     60, 60, 60, 61, 61, 61, 61, 61,
118     61, 62, 62, 62, 62, 62, 62, 63,
119     63, 63, 63, 63, 63, 64, 64, 64
120   };
121 
122 
123   FT_LOCAL_DEF( AF_Angle )
af_angle_atan(FT_Fixed dx,FT_Fixed dy)124   af_angle_atan( FT_Fixed  dx,
125                  FT_Fixed  dy )
126   {
127     AF_Angle  angle;
128 
129 
130     /* check trivial cases */
131     if ( dy == 0 )
132     {
133       angle = 0;
134       if ( dx < 0 )
135         angle = AF_ANGLE_PI;
136       return angle;
137     }
138     else if ( dx == 0 )
139     {
140       angle = AF_ANGLE_PI2;
141       if ( dy < 0 )
142         angle = -AF_ANGLE_PI2;
143       return angle;
144     }
145 
146     angle = 0;
147     if ( dx < 0 )
148     {
149       dx = -dx;
150       dy = -dy;
151       angle = AF_ANGLE_PI;
152     }
153 
154     if ( dy < 0 )
155     {
156       FT_Pos  tmp;
157 
158 
159       tmp = dx;
160       dx  = -dy;
161       dy  = tmp;
162       angle -= AF_ANGLE_PI2;
163     }
164 
165     if ( dx == 0 && dy == 0 )
166       return 0;
167 
168     if ( dx == dy )
169       angle += AF_ANGLE_PI4;
170     else if ( dx > dy )
171       angle += af_arctan[FT_DivFix( dy, dx ) >> ( 16 - AF_ATAN_BITS )];
172     else
173       angle += AF_ANGLE_PI2 -
174                af_arctan[FT_DivFix( dx, dy ) >> ( 16 - AF_ATAN_BITS )];
175 
176     if ( angle > AF_ANGLE_PI )
177       angle -= AF_ANGLE_2PI;
178 
179     return angle;
180   }
181 
182 
183 #endif /* 0 */
184 
185 
186   FT_LOCAL_DEF( void )
af_sort_pos(FT_UInt count,FT_Pos * table)187   af_sort_pos( FT_UInt  count,
188                FT_Pos*  table )
189   {
190     FT_UInt  i, j;
191     FT_Pos   swap;
192 
193 
194     for ( i = 1; i < count; i++ )
195     {
196       for ( j = i; j > 0; j-- )
197       {
198         if ( table[j] >= table[j - 1] )
199           break;
200 
201         swap         = table[j];
202         table[j]     = table[j - 1];
203         table[j - 1] = swap;
204       }
205     }
206   }
207 
208 
209   FT_LOCAL_DEF( void )
af_sort_and_quantize_widths(FT_UInt * count,AF_Width table,FT_Pos threshold)210   af_sort_and_quantize_widths( FT_UInt*  count,
211                                AF_Width  table,
212                                FT_Pos    threshold )
213   {
214     FT_UInt      i, j;
215     FT_UInt      cur_idx;
216     FT_Pos       cur_val;
217     FT_Pos       sum;
218     AF_WidthRec  swap;
219 
220 
221     if ( *count == 1 )
222       return;
223 
224     /* sort */
225     for ( i = 1; i < *count; i++ )
226     {
227       for ( j = i; j > 0; j-- )
228       {
229         if ( table[j].org >= table[j - 1].org )
230           break;
231 
232         swap         = table[j];
233         table[j]     = table[j - 1];
234         table[j - 1] = swap;
235       }
236     }
237 
238     cur_idx = 0;
239     cur_val = table[cur_idx].org;
240 
241     /* compute and use mean values for clusters not larger than  */
242     /* `threshold'; this is very primitive and might not yield   */
243     /* the best result, but normally, using reference character  */
244     /* `o', `*count' is 2, so the code below is fully sufficient */
245     for ( i = 1; i < *count; i++ )
246     {
247       if ( table[i].org - cur_val > threshold ||
248            i == *count - 1                    )
249       {
250         sum = 0;
251 
252         /* fix loop for end of array */
253         if ( table[i].org - cur_val <= threshold &&
254              i == *count - 1                     )
255           i++;
256 
257         for ( j = cur_idx; j < i; j++ )
258         {
259           sum         += table[j].org;
260           table[j].org = 0;
261         }
262         table[cur_idx].org = sum / (FT_Pos)j;
263 
264         if ( i < *count - 1 )
265         {
266           cur_idx = i + 1;
267           cur_val = table[cur_idx].org;
268         }
269       }
270     }
271 
272     cur_idx = 1;
273 
274     /* compress array to remove zero values */
275     for ( i = 1; i < *count; i++ )
276     {
277       if ( table[i].org )
278         table[cur_idx++] = table[i];
279     }
280 
281     *count = cur_idx;
282   }
283 
284 
285 /* END */
286