1 /*
2
3 Copyright (C) 2015-2018 Night Dive Studios, LLC.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 */
19
20 /*
21 ** fix.c
22 **
23 ** $Header: r:/prj/lib/src/fix/RCS/fix.c 1.21 1994/08/11 12:11:09 dfan Exp $
24 ** $Log: fix.c $
25 * Revision 1.21 1994/08/11 12:11:09 dfan
26 * move some stuff out
27 *
28 * Revision 1.20 1994/03/16 10:29:08 dfan
29 * fix_safe_pyth_dist etc.
30 *
31 * Revision 1.19 1994/03/01 11:28:44 dfan
32 * Do it for fix24's too
33 *
34 * Revision 1.18 1994/03/01 11:27:58 dfan
35 * Don't need quadrant/placing code in fix_atan, and besides,
36 * it's buggy
37 *
38 * Revision 1.17 1994/02/16 17:33:47 dfan
39 * allow arbitrarily small arguments to fix_exp
40 *
41 * Revision 1.16 1993/11/30 13:02:42 dfan
42 * safe fix_mul
43 *
44 * Revision 1.15 1993/11/04 11:06:09 rex
45 * Moved fix_sprintf() stuff out into fixsprnt.c
46 *
47 * Revision 1.14 1993/10/20 13:08:22 dfan
48 * some more fast_pyth_dists
49 *
50 * Revision 1.13 1993/09/17 13:03:30 dfan
51 * fast_pyth_dist
52 *
53 * Revision 1.12 1993/07/30 12:42:55 dfan
54 * fix_exp
55 *
56 * Revision 1.11 1993/06/27 03:09:43 dc
57 * pretty up hexprint formatting, sorry, whoops. etc.
58 *
59 * Revision 1.10 1993/06/27 02:30:24 dc
60 * fix_sprint now returns the buffer string, also added fix_sprint_hex
61 *
62 * Revision 1.9 1993/06/01 14:14:43 dfan
63 * Include trigtab.h, generated by fmaketab
64 * Lose a bit of precision, but now all trig functions work everywhere
65 *
66 * Revision 1.8 1993/04/19 13:31:33 dfan
67 * individual sin & cos functions
68 *
69 * Revision 1.7 1993/03/17 12:46:45 matt
70 * Removed 'const' from sincos declaration so could be ref'd in fix_asm.asm
71 *
72 * Revision 1.6 1993/03/02 10:51:30 dfan
73 * atan2: comparisons of sin should have been unsigned, not signed
74 *
75 * Revision 1.5 1993/02/15 12:15:21 dfan
76 * more fix24 functions
77 *
78 * Revision 1.4 1993/02/15 11:39:57 dfan
79 * fix24 support, not for all fuctions though
80 *
81 * Revision 1.3 1993/01/29 16:37:22 dfan
82 * maybe we shouldn't printf an error message in a library, what say
83 *
84 * Revision 1.2 1993/01/29 11:10:06 dfan
85 * Changed fix_pyth_dist to be straightforward (and twice as fast)
86 * The arctrig functions worked all along
87 *
88 * Revision 1.1 1993/01/22 09:57:39 dfan
89 * Initial revision
90 *
91 */
92
93 #include "fix.h"
94 #include "lg.h"
95 #include "trigtab.h"
96 #include <stdint.h>
97 #include <stdlib.h>
98
fix_mul_3_3_3(fix a,fix b)99 fix fix_mul_3_3_3(fix a, fix b) { return (fix)(((int64_t)(a) * (int64_t)(b)) >> 29); }
100
fix_mul_3_32_16(fix a,fix b)101 fix fix_mul_3_32_16(fix a, fix b) { return (fix)(((int64_t)(a) * (int64_t)(b)) >> 13); }
102
fix_mul_3_16_20(fix a,fix b)103 fix fix_mul_3_16_20(fix a, fix b) { return (fix)(((int64_t)(a) * (int64_t)(b)) >> 33); }
104
fix_mul_16_32_20(fix a,fix b)105 fix fix_mul_16_32_20(fix a, fix b) { return (fix)(((int64_t)(a) * (int64_t)(b)) >> 4); }
106
fix_div_16_16_3(fix a,fix b)107 fix fix_div_16_16_3(fix a, fix b) { return (fix)(((int64_t)a << 29) / (int64_t)b); }
108
109 int gOVResult;
110
fix_mul(fix a,fix b)111 fix fix_mul(fix a, fix b) { return (fix)(((int64_t)(a) * (int64_t)(b)) >> 16); }
112
fast_fix_mul_int(fix a,fix b)113 fix fast_fix_mul_int(fix a, fix b) { return (fix)(((int64_t)(a) * (int64_t)(b)) >> 32); }
114
fix_mul_asm_safe(fix a,fix b)115 fix fix_mul_asm_safe(fix a, fix b) {
116 int64_t intermediate = (int64_t)(a) * (int64_t)(b);
117 // Apparently PowerPC and Motorola 68000 codes differ here
118 // PowerPC will check if the lower 32 bits of the intemerdiate result are
119 // equal to -1 (cmpi 1,r6,-1), while 68K will check if the lower *16* bits of
120 // the intermediate result are equal to -1 (cmp.w #-1,d2). The result should
121 // be the same because bits 31:16 of the intermediate result already are
122 // tested for being equal to -1, but I'm leaving this comment here anyway for
123 // future reference
124 // int16_t d2 = intermediate & 0xFFFF; // 68K code
125 int32_t d2 = intermediate & 0xFFFFFFFF; // PPC code
126 fix result = (fix)(intermediate >> 16);
127 if (result == -1 && d2 != -1) {
128 return 0;
129 }
130 return result;
131 }
132
133 // fix fix_div(fix a, fix b)
fix_div(fix a,fix b)134 fix fix_div(fix a, fix b) {
135 if (b == 0) {
136 gOVResult = 2;
137 fix r = 0x7FFFFFFF;
138 if (a >= 0) {
139 return r;
140 }
141 return -r;
142 }
143 gOVResult = 0;
144 int64_t r64 = ((int64_t)(a) << 16) / (int64_t)(b);
145 int32_t r32 = (int32_t)(r64 & 0xFFFFFFFF);
146 if (r64 != (int64_t)r32) {
147 gOVResult = 1;
148 fix r = 0x7FFFFFFF;
149 if (a >= 0) {
150 return r;
151 }
152 return -r;
153 }
154 return r32;
155 }
156
157 // fix fix_div_int(fix a, fix b)
158 //{
159 // return (fix)(((int64_t)(a) << 16) / (int64_t)(b));
160 //}
fix_div_int(fix a,fix b)161 fix fix_div_int(fix a, fix b) {
162 int64_t r64 = ((int64_t)(a) << 16) / (int64_t)(b);
163 int32_t r32 = (int32_t)((r64 >> 16) & 0xFFFFFFFF);
164 return r32;
165 }
166
167 // fix fix_div_safe_cint(fix a, fix b)
168 //{
169 // return (fix)(((int64_t)(a) << 16) / (int64_t)(b));
170 //}
fix_div_safe_cint(fix a,fix b)171 fix fix_div_safe_cint(fix a, fix b) {
172 int64_t r64 = ((int64_t)(a) << 16) / (int64_t)(b);
173 int32_t r32 = (int32_t)((r64 >> 16) & 0xFFFFFFFF);
174 if ((r64 & 0xFFFF) != 0) {
175 return r32 + 1;
176 }
177 return r32;
178 }
179
180 //----------------------------------------------------------------------------
181 // fix_div: Divide two fixed numbers.
182 //----------------------------------------------------------------------------
183
fix_mul_div(fix m0,fix m1,fix d)184 fix fix_mul_div(fix m0, fix m1, fix d) {
185 // return (fix)(((int64_t)(m0) * (int64_t)(m1)) / (int64_t)(d));
186 int64_t mr = ((int64_t)(m0) * (int64_t)(m1));
187 if (d == 0) {
188 gOVResult = 2;
189 fix r = 0x7FFFFFFF;
190 if (mr >= 0) {
191 return r;
192 }
193 return -r;
194 }
195 gOVResult = 0;
196 int64_t r64 = mr / (int64_t)(d);
197 int32_t r32 = (int32_t)(r64 & 0xFFFFFFFF);
198 if (r64 != (int64_t)r32) {
199 gOVResult = 1;
200 fix r = 0x7FFFFFFF;
201 if (mr >= 0) {
202 return r;
203 }
204 return -r;
205 }
206 return r32;
207 }
208
209 //----------------------------------------------------------------------------
210 // Returns the distance from (0,0) to (a,b)
211 //----------------------------------------------------------------------------
fix_pyth_dist(fix a,fix b)212 fix fix_pyth_dist(fix a, fix b) {
213 gOVResult = 100;
214
215 // @@@should check for overflow!
216 return fix_sqrt(fix_mul(a, a) + fix_mul(b, b));
217 }
218
219 //----------------------------------------------------------------------------
220 // Returns an approximation to the distance from (0,0) to (a,b)
221 //----------------------------------------------------------------------------
fix_fast_pyth_dist(fix a,fix b)222 fix fix_fast_pyth_dist(fix a, fix b) {
223 if (a < 0)
224 a = -a;
225 if (b < 0)
226 b = -b;
227 if (a > b)
228 return (a + b / 2);
229 else
230 return (b + a / 2);
231 }
232
233 //----------------------------------------------------------------------------
234 // We can use the fix function because the difference in scale doesn't matter.
235 //----------------------------------------------------------------------------
long_fast_pyth_dist(int a,int b)236 int long_fast_pyth_dist(int a, int b) { return (fix_fast_pyth_dist(a, b)); }
237
238 //----------------------------------------------------------------------------
239 // This function is safer than the other fix_pyth_dist because we don't
240 // have to worry about overflow.
241 //
242 // Uses algorithm from METAFONT involving reflecting (a,b) through
243 // line from (0,0) to (a,b/2), which keeps a^2+b^2 invariant but
244 // greatly reduces b. When b reaches 0, a is the distance.
245 //
246 // Knuth credits it to Moler & Morrison, IBM Journal of Research and
247 // Development 27 (1983). Good for them.
248 //----------------------------------------------------------------------------
fix_safe_pyth_dist(fix a,fix b)249 fix fix_safe_pyth_dist(fix a, fix b) {
250 fix tmp;
251
252 a = abs(a);
253 b = abs(b); // works fine since they're really longs
254 if (a < b) {
255 tmp = a;
256 a = b;
257 b = tmp;
258 } // now 0 <= b <= a
259 if (a > 0) {
260 if (a > 0x2fffffff) {
261 // ssWarning (("Overflow in
262 // fix_safe_pyth_dist\n")); DebugStr("\pOverflow in fix_safe_pyth_dist");
263 DEBUG("%s: Overflow in fix_safe_pyth_dist", __FUNCTION__);
264 return 0;
265 }
266 for (;;) {
267 // This is a quick way of doing the reflection
268 tmp = fix_div(b, a);
269 tmp = fix_mul(tmp, tmp);
270 if (tmp == 0)
271 break;
272 tmp = fix_div(tmp, tmp + fix_make(4, 0));
273 a += fix_mul(2 * a, tmp);
274 b = fix_mul(b, tmp);
275 }
276 }
277 return a;
278 }
279
280 //----------------------------------------------------------------------------
281 // Computes sin and cos of theta
282 //----------------------------------------------------------------------------
fix_sincos(fixang theta,fix * sin,fix * cos)283 void fix_sincos(fixang theta, fix *sin, fix *cos) {
284 uint8_t baseth, fracth; // high and low bytes of the
285 uint16_t lowsin, lowcos, hisin, hicos; // table lookups
286
287 // divide the angle into high and low bytes
288 // we will do a table lookup with the high byte and
289 // interpolate with the low byte
290 baseth = (uint8_t)(theta >> 8);
291 fracth = (uint8_t)(theta & 0xff);
292
293 // use the identity [cos x = sin (x + PI/2)] to look up
294 // cosines in the sine table
295 lowsin = sintab[baseth];
296 hisin = sintab[baseth + 1];
297 lowcos = sintab[baseth + 64];
298 hicos = sintab[baseth + 65];
299
300 // interpolate between low___ and hi___ according to fracth
301 *sin = ((int16_t)(lowsin + ((((int16_t)hisin - (int16_t)lowsin) * fracth) >> 8))) << 2;
302 *cos = ((int16_t)(lowcos + ((((int16_t)hicos - (int16_t)lowcos) * fracth) >> 8))) << 2;
303
304 return;
305 }
306
307 //----------------------------------------------------------------------------
308 // Computes sin of theta
309 //----------------------------------------------------------------------------
fix_sin(fixang theta)310 fix fix_sin(fixang theta) {
311 uint8_t baseth, fracth;
312 uint16_t lowsin, hisin;
313
314 baseth = (uint8_t)(theta >> 8);
315 fracth = (uint8_t)(theta & 0xff);
316 lowsin = sintab[baseth];
317 hisin = sintab[baseth + 1];
318 return ((int16_t)(lowsin + ((((int16_t)hisin - (int16_t)lowsin) * fracth) >> 8))) << 2;
319 }
320
321 //----------------------------------------------------------------------------
322 // Computes cos of theta
323 //----------------------------------------------------------------------------
fix_cos(fixang theta)324 fix fix_cos(fixang theta) {
325 uint8_t baseth, fracth;
326 uint16_t lowcos, hicos;
327
328 baseth = (uint8_t)(theta >> 8);
329 fracth = (uint8_t)(theta & 0xff);
330 lowcos = sintab[baseth + 64];
331 hicos = sintab[baseth + 65];
332 return ((int16_t)(lowcos + ((((int16_t)hicos - (int16_t)lowcos) * fracth) >> 8))) << 2;
333 }
334
335 //----------------------------------------------------------------------------
336 // Computes sin and cos of theta
337 // Faster than fix_sincos() but not as accurate (does not interpolate)
338 //----------------------------------------------------------------------------
fix_fastsincos(fixang theta,fix * sin,fix * cos)339 void fix_fastsincos(fixang theta, fix *sin, fix *cos) {
340 // use the identity [cos x = sin (x + PI/2)] to look up
341 // cosines in the sine table
342 *sin = (((int16_t)(sintab[theta >> 8])) << 2);
343 *cos = (((int16_t)(sintab[(theta >> 8) + 64])) << 2);
344
345 return;
346 }
347
348 //----------------------------------------------------------------------------
349 // Fast sin of theta
350 //----------------------------------------------------------------------------
fix_fastsin(fixang theta)351 fix fix_fastsin(fixang theta) { return (((int16_t)(sintab[theta >> 8])) << 2); }
352
353 //----------------------------------------------------------------------------
354 // Fast cos of theta
355 //----------------------------------------------------------------------------
fix_fastcos(fixang theta)356 fix fix_fastcos(fixang theta) { return (((int16_t)(sintab[(theta >> 8) + 64])) << 2); }
357
358 //----------------------------------------------------------------------------
359 // Computes the arcsin of x
360 // Assumes -1 <= x <= 1
361 // Returns 0xc000..0x4000 (-PI/2..PI/2)
362 //----------------------------------------------------------------------------
fix_asin(fix x)363 fixang fix_asin(fix x) {
364 uint8_t basex, fracx; // high and low bytes of x
365 fixang lowy, hiy; // table lookups
366
367 // divide x into high and low bytes
368 // lookup with the high byte, interpolate with the low
369 // We shift basex around to make it continuous; see trigtab.h
370
371 basex = (uint8_t)(((x >> 2) >> 8) + 0x40);
372 fracx = (uint8_t)((x >> 2) & 0xff);
373
374 lowy = asintab[basex];
375 hiy = asintab[basex + 1];
376
377 // interpolate between lowy and hiy according to fracx
378 return (lowy + ((((int16_t)hiy - (int16_t)lowy) * fracx) >> 8));
379 }
380
381 //----------------------------------------------------------------------------
382 // Computes the arccos of x
383 // Returns 0x0000..0x8000 (0..PI)
384 //----------------------------------------------------------------------------
fix_acos(fix x)385 fixang fix_acos(fix x) {
386 uint8_t basex, fracx;
387 uint16_t lowy, hiy;
388 fixang asin_answer;
389
390 // acos(x) = PI/2 - asin(x)
391
392 basex = (uint8_t)(((x >> 2) >> 8) + 0x40);
393 fracx = (uint8_t)((x >> 2) & 0xff);
394
395 lowy = asintab[basex];
396 hiy = asintab[basex + 1];
397
398 asin_answer = (lowy + ((((int16_t)hiy - (int16_t)lowy) * fracx) >> 8));
399 return ((fixang)0x4000 - asin_answer);
400 }
401
402 //----------------------------------------------------------------------------
403 // Computes the atan of y/x, in the correct quadrant and everything
404 //----------------------------------------------------------------------------
fix_atan2(fix y,fix x)405 fixang fix_atan2(fix y, fix x) {
406 fix hyp; // hypotenuse
407 fix s, c; // sine, cosine
408 fixang th; // our answer
409
410 // Get special cases out of the way so we don't have to deal
411 // with things like making sure 1 gets converted to 0x7fff and
412 // not 0x8000. Note that we grab the y = x = 0 case here
413 if (y == 0) {
414 if (x >= 0)
415 return 0x0000;
416 else
417 return 0x8000;
418 } else if (x == 0) {
419 if (y >= 0)
420 return 0x4000;
421 else
422 return 0xc000;
423 }
424
425 if ((hyp = fix_pyth_dist(x, y)) == 0) {
426 // printf ("hey, dist was 0\n");
427
428 return 0;
429 }
430
431 // Use fix_asin or fix_acos depending on where we are. We don't want to use
432 // fix_asin if the sin is close to 1 or -1
433 s = fix_div(y, hyp);
434 if ((uint32_t)s < 0x00004000 || (uint32_t)s > 0xffffc000) { // range is good, use asin
435 th = fix_asin(s);
436 if (x < 0) {
437 if (th < 0x4000)
438 th = 0x8000 - th;
439 else
440 th = ~th + 0x8000; // that is, 0xffff - th + 0x8000
441 }
442 } else { // use acos instead
443 c = fix_div(x, hyp);
444 th = fix_acos(c);
445 if (y < 0) {
446 th = ~th; // that is, 0xffff - th
447 }
448 }
449
450 // The above (x < 0) and (y < 0) conditionals should take care of placing us
451 // in the correct quadrant, so we shouldn't need the code below.
452 // Additionally, the code below can cause rounding errors when (th & 0x3fff
453 // == 0). So let's try omitting it.
454
455 #ifdef NO_NEED
456 // set high bits based on what quadrant we are in
457 th &= 0x3fff;
458 th |= (y > 0 ? (x > 0 ? 0x0000 : 0x4000) : (x > 0 ? 0xc000 : 0x8000));
459 #endif
460
461 return th;
462 }
463
fix24_mul(fix24 a,fix24 b)464 fix24 fix24_mul(fix24 a, fix24 b) { return (fix24)(((int64_t)a * (int64_t)b) >> 8); }
465
fix24_div(fix24 a,fix24 b)466 fix24 fix24_div(fix24 a, fix24 b) { return (fix24)(((int64_t)a << 8) / (int64_t)b); }
467
fix_pow(fix x,fix y)468 fix fix_pow(fix x, fix y) {
469 int i;
470 fix ans;
471 fix rh, rl;
472 uint16_t yh, yl;
473
474 ans = FIX_UNIT;
475 yh = (uint16_t)(fix_int(y));
476 yl = fix_frac(y);
477 rh = rl = x;
478
479 // calculate hi part, leave when done
480 for (i = 0; i < 16; ++i) {
481 if (yh & 1)
482 ans = fix_mul(ans, rh);
483 if (yh != 0)
484 rh = fix_mul(rh, rh);
485 yh = yh >> 1;
486 if (yl != 0)
487 rl = fix_sqrt(rl);
488 if (yl & 0x8000)
489 ans = fix_mul(ans, rl);
490 yl = yl << 1;
491 }
492 return ans;
493 }
494
fix64_div(int64_t a,int32_t b)495 int32_t fix64_div(int64_t a, int32_t b) {
496 return (int32_t) (a / b);
497 }
498
fix64_mul(int32_t a,int32_t b)499 int64_t fix64_mul(int32_t a, int32_t b) {
500 return (int64_t)a * (int64_t)b;
501 }
502