this can be a move
[xonotic/gmqcc.git] / fold.cpp
1 #include <string.h>
2 #include <math.h>
3
4 #include "fold.h"
5 #include "ast.h"
6 #include "ir.h"
7
8 #include "parser.h"
9
10 #define FOLD_STRING_UNTRANSLATE_HTSIZE 1024
11 #define FOLD_STRING_DOTRANSLATE_HTSIZE 1024
12
13 /* The options to use for inexact and arithmetic exceptions */
14 #define FOLD_ROUNDING SFLOAT_ROUND_NEAREST_EVEN
15 #define FOLD_TINYNESS SFLOAT_TBEFORE
16
17 /*
18  * Comparing float values is an unsafe operation when the operands to the
19  * comparison are floating point values that are inexact. For instance 1/3 is an
20  * inexact value. The FPU is meant to raise exceptions when these sorts of things
21  * happen, including division by zero, underflows and overflows. The C standard
22  * library provides us with the <fenv.h> header to gain access to the floating-
23  * point environment and lets us set the rounding mode and check for these exceptions.
24  * The problem is the standard C library allows an implementation to leave these
25  * stubbed out and does not require they be implemented. Furthermore, depending
26  * on implementations there is no control over the FPU. This is an IEE 754
27  * conforming implementation in software to compensate.
28  */
29 typedef uint32_t sfloat_t;
30
31 union sfloat_cast_t {
32     qcfloat_t f;
33     sfloat_t s;
34 };
35
36 /* Exception flags */
37 enum sfloat_exceptionflags_t {
38     SFLOAT_NOEXCEPT  = 0,
39     SFLOAT_INVALID   = 1,
40     SFLOAT_DIVBYZERO = 4,
41     SFLOAT_OVERFLOW  = 8,
42     SFLOAT_UNDERFLOW = 16,
43     SFLOAT_INEXACT   = 32
44 };
45
46 /* Rounding modes */
47 enum sfloat_roundingmode_t {
48     SFLOAT_ROUND_NEAREST_EVEN,
49     SFLOAT_ROUND_DOWN,
50     SFLOAT_ROUND_UP,
51     SFLOAT_ROUND_TO_ZERO
52 };
53
54 /* Underflow tininess-detection mode */
55 enum sfloat_tdetect_t {
56     SFLOAT_TAFTER,
57     SFLOAT_TBEFORE
58 };
59
60 struct sfloat_state_t {
61     sfloat_roundingmode_t roundingmode;
62     sfloat_exceptionflags_t exceptionflags;
63     sfloat_tdetect_t tiny;
64 };
65
66 /* Counts the number of leading zero bits before the most-significand one bit. */
67 #ifdef _MSC_VER
68 /* MSVC has an intrinsic for this */
69     static GMQCC_INLINE uint32_t sfloat_clz(uint32_t x) {
70         int r = 0;
71         _BitScanForward(&r, x);
72         return r;
73     }
74 #   define SFLOAT_CLZ(X, SUB) \
75         (sfloat_clz((X)) - (SUB))
76 #elif defined(__GNUC__) || defined(__CLANG__)
77 /* Clang and GCC have a builtin for this */
78 #   define SFLOAT_CLZ(X, SUB) \
79         (__builtin_clz((X)) - (SUB))
80 #else
81 /* Native fallback */
82     static GMQCC_INLINE uint32_t sfloat_popcnt(uint32_t x) {
83         x -= ((x >> 1) & 0x55555555);
84         x  = (((x >> 2) & 0x33333333) + (x & 0x33333333));
85         x  = (((x >> 4) + x) & 0x0F0F0F0F);
86         x += x >> 8;
87         x += x >> 16;
88         return x & 0x0000003F;
89     }
90     static GMQCC_INLINE uint32_t sfloat_clz(uint32_t x) {
91         x |= (x >> 1);
92         x |= (x >> 2);
93         x |= (x >> 4);
94         x |= (x >> 8);
95         x |= (x >> 16);
96         return 32 - sfloat_popcnt(x);
97     }
98 #   define SFLOAT_CLZ(X, SUB) \
99         (sfloat_clz((X) - (SUB)))
100 #endif
101
102 /* The value of a NaN */
103 #define SFLOAT_NAN 0xFFFFFFFF
104 /* Test if NaN */
105 #define SFLOAT_ISNAN(A) \
106     (0xFF000000 < (uint32_t)((A) << 1))
107 /* Test if signaling NaN */
108 #define SFLOAT_ISSNAN(A) \
109     (((((A) >> 22) & 0x1FF) == 0x1FE) && ((A) & 0x003FFFFF))
110 /* Raise exception */
111 #define SFLOAT_RAISE(STATE, FLAGS) \
112     ((STATE)->exceptionflags = (sfloat_exceptionflags_t)((STATE)->exceptionflags | (FLAGS)))
113 /*
114  * Shifts `A' right by the number of bits given in `COUNT'. If any non-zero bits
115  * are shifted off they are forced into the least significand bit of the result
116  * by setting it to one. As a result of this, the value of `COUNT' can be
117  * arbitrarily large; if `COUNT' is greater than 32, the result will be either
118  * zero or one, depending on whether `A' is a zero or non-zero. The result is
119  * stored into the value pointed by `Z'.
120  */
121 #define SFLOAT_SHIFT(SIZE, A, COUNT, Z)                                      \
122     *(Z) = ((COUNT) == 0)                                                    \
123         ? 1                                                                  \
124         : (((COUNT) < (SIZE))                                                \
125             ? ((A) >> (COUNT)) | (((A) << ((-(COUNT)) & ((SIZE) - 1))) != 0) \
126             : ((A) != 0))
127
128 /* Extract fractional component */
129 #define SFLOAT_EXTRACT_FRAC(X) \
130     ((uint32_t)((X) & 0x007FFFFF))
131 /* Extract exponent component */
132 #define SFLOAT_EXTRACT_EXP(X) \
133     ((int16_t)((X) >> 23) & 0xFF)
134 /* Extract sign bit */
135 #define SFLOAT_EXTRACT_SIGN(X) \
136     ((X) >> 31)
137 /*
138  * Normalizes the subnormal value represented by the denormalized significand
139  * `SA'. The normalized exponent and significand are stored at the locations
140  * pointed by `Z' and `SZ' respectively.
141  */
142 #define SFLOAT_SUBNORMALIZE(SA, Z, SZ) \
143     (void)(*(SZ) = (SA) << SFLOAT_CLZ((SA), 8), *(Z) = 1 - SFLOAT_CLZ((SA), 8))
144 /*
145  * Packs the sign `SIGN', exponent `EXP' and significand `SIG' into the value
146  * giving the result.
147  *
148  * After the shifting into their proper positions, the fields are added together
149  * to form the result. This means any integer portion of `SIG' will be added
150  * to the exponent. Similarly, because a properly normalized significand will
151  * always have an integer portion equal to one, the exponent input `EXP' should
152  * be one less than the desired result exponent whenever the significant input
153  * `SIG' is a complete, normalized significand.
154  */
155 #define SFLOAT_PACK(SIGN, EXP, SIG) \
156     (sfloat_t)((((uint32_t)(SIGN)) << 31) + (((uint32_t)(EXP)) << 23) + (SIG))
157
158 /*
159  * Takes two values `a' and `b', one of which is a NaN, and returns the appropriate
160  * NaN result. If either `a' or `b' is a signaling NaN than an invalid exception is
161  * raised.
162  */
163 static sfloat_t sfloat_propagate_nan(sfloat_state_t *state, sfloat_t a, sfloat_t b) {
164     bool isnan_a  = SFLOAT_ISNAN(a);
165     bool issnan_a = SFLOAT_ISSNAN(a);
166     bool isnan_b  = SFLOAT_ISNAN(b);
167     bool issnan_b = SFLOAT_ISSNAN(b);
168
169     a |= 0x00400000;
170     b |= 0x00400000;
171
172     if (issnan_a | issnan_b)
173         SFLOAT_RAISE(state, SFLOAT_INVALID);
174     if (isnan_a)
175         return (issnan_a & isnan_b) ? b : a;
176  &nb