1 |
|
|
/* |
2 |
|
|
* The ManaPlus Client |
3 |
|
|
* Copyright (C) 2009 The Mana World Development Team |
4 |
|
|
* Copyright (C) 2009-2010 The Mana Developers |
5 |
|
|
* Copyright (C) 2011-2019 The ManaPlus Developers |
6 |
|
|
* Copyright (C) 2019-2021 Andrei Karas |
7 |
|
|
* |
8 |
|
|
* This file is part of The ManaPlus Client. |
9 |
|
|
* |
10 |
|
|
* This program is free software; you can redistribute it and/or modify |
11 |
|
|
* it under the terms of the GNU General Public License as published by |
12 |
|
|
* the Free Software Foundation; either version 2 of the License, or |
13 |
|
|
* any later version. |
14 |
|
|
* |
15 |
|
|
* This program is distributed in the hope that it will be useful, |
16 |
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
17 |
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
18 |
|
|
* GNU General Public License for more details. |
19 |
|
|
* |
20 |
|
|
* You should have received a copy of the GNU General Public License |
21 |
|
|
* along with this program. If not, see <http://www.gnu.org/licenses/>. |
22 |
|
|
*/ |
23 |
|
|
|
24 |
|
|
#ifndef UTILS_MATHUTILS_H |
25 |
|
|
#define UTILS_MATHUTILS_H |
26 |
|
|
|
27 |
|
|
#include "utils/cast.h" |
28 |
|
|
|
29 |
|
|
#include <string> |
30 |
|
|
|
31 |
|
|
#ifndef USE_SDL2 |
32 |
|
|
#include <cmath> |
33 |
|
|
#endif // USE_SDL2 |
34 |
|
|
|
35 |
|
|
#include "localconsts.h" |
36 |
|
|
|
37 |
|
|
static constexpr const uint16_t crc_table[256] = |
38 |
|
|
{ |
39 |
|
|
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, |
40 |
|
|
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, |
41 |
|
|
0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, |
42 |
|
|
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, |
43 |
|
|
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, |
44 |
|
|
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, |
45 |
|
|
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, |
46 |
|
|
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, |
47 |
|
|
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, |
48 |
|
|
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, |
49 |
|
|
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, |
50 |
|
|
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, |
51 |
|
|
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, |
52 |
|
|
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, |
53 |
|
|
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, |
54 |
|
|
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, |
55 |
|
|
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, |
56 |
|
|
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, |
57 |
|
|
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, |
58 |
|
|
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, |
59 |
|
|
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, |
60 |
|
|
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, |
61 |
|
|
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, |
62 |
|
|
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, |
63 |
|
|
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, |
64 |
|
|
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, |
65 |
|
|
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, |
66 |
|
|
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, |
67 |
|
|
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, |
68 |
|
|
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, |
69 |
|
|
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, |
70 |
|
|
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0 |
71 |
|
|
}; |
72 |
|
|
|
73 |
|
|
static constexpr const uint8_t square_roots[1000] = |
74 |
|
|
{ |
75 |
|
|
0, 1, 1, 1, 2, 2, 2, 2, 2, 3, |
76 |
|
|
3, 3, 3, 3, 3, 3, 4, 4, 4, 4, |
77 |
|
|
4, 4, 4, 4, 4, 5, 5, 5, 5, 5, |
78 |
|
|
5, 5, 5, 5, 5, 5, 6, 6, 6, 6, |
79 |
|
|
6, 6, 6, 6, 6, 6, 6, 6, 6, 7, |
80 |
|
|
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
81 |
|
|
7, 7, 7, 7, 8, 8, 8, 8, 8, 8, |
82 |
|
|
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, |
83 |
|
|
8, 9, 9, 9, 9, 9, 9, 9, 9, 9, |
84 |
|
|
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, |
85 |
|
|
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, |
86 |
|
|
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, |
87 |
|
|
10, 11, 11, 11, 11, 11, 11, 11, 11, 11, |
88 |
|
|
11, 11, 11, 11, 11, 11, 11, 11, 11, 11, |
89 |
|
|
11, 11, 11, 11, 12, 12, 12, 12, 12, 12, |
90 |
|
|
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, |
91 |
|
|
12, 12, 12, 12, 12, 12, 12, 12, 12, 13, |
92 |
|
|
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, |
93 |
|
|
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, |
94 |
|
|
13, 13, 13, 13, 13, 13, 14, 14, 14, 14, |
95 |
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, |
96 |
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, |
97 |
|
|
14, 14, 14, 14, 14, 15, 15, 15, 15, 15, |
98 |
|
|
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, |
99 |
|
|
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, |
100 |
|
|
15, 15, 15, 15, 15, 15, 16, 16, 16, 16, |
101 |
|
|
16, 16, 16, 16, 16, 16, 16, 16, 16, 16, |
102 |
|
|
16, 16, 16, 16, 16, 16, 16, 16, 16, 16, |
103 |
|
|
16, 16, 16, 16, 16, 16, 16, 16, 16, 17, |
104 |
|
|
17, 17, 17, 17, 17, 17, 17, 17, 17, 17, |
105 |
|
|
17, 17, 17, 17, 17, 17, 17, 17, 17, 17, |
106 |
|
|
17, 17, 17, 17, 17, 17, 17, 17, 17, 17, |
107 |
|
|
17, 17, 17, 17, 18, 18, 18, 18, 18, 18, |
108 |
|
|
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, |
109 |
|
|
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, |
110 |
|
|
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, |
111 |
|
|
18, 19, 19, 19, 19, 19, 19, 19, 19, 19, |
112 |
|
|
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, |
113 |
|
|
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, |
114 |
|
|
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, |
115 |
|
|
20, 20, 20, 20, 20, 20, 20, 20, 20, 20, |
116 |
|
|
20, 20, 20, 20, 20, 20, 20, 20, 20, 20, |
117 |
|
|
20, 20, 20, 20, 20, 20, 20, 20, 20, 20, |
118 |
|
|
20, 20, 20, 20, 20, 20, 20, 20, 20, 20, |
119 |
|
|
20, 21, 21, 21, 21, 21, 21, 21, 21, 21, |
120 |
|
|
21, 21, 21, 21, 21, 21, 21, 21, 21, 21, |
121 |
|
|
21, 21, 21, 21, 21, 21, 21, 21, 21, 21, |
122 |
|
|
21, 21, 21, 21, 21, 21, 21, 21, 21, 21, |
123 |
|
|
21, 21, 21, 21, 22, 22, 22, 22, 22, 22, |
124 |
|
|
22, 22, 22, 22, 22, 22, 22, 22, 22, 22, |
125 |
|
|
22, 22, 22, 22, 22, 22, 22, 22, 22, 22, |
126 |
|
|
22, 22, 22, 22, 22, 22, 22, 22, 22, 22, |
127 |
|
|
22, 22, 22, 22, 22, 22, 22, 22, 22, 23, |
128 |
|
|
23, 23, 23, 23, 23, 23, 23, 23, 23, 23, |
129 |
|
|
23, 23, 23, 23, 23, 23, 23, 23, 23, 23, |
130 |
|
|
23, 23, 23, 23, 23, 23, 23, 23, 23, 23, |
131 |
|
|
23, 23, 23, 23, 23, 23, 23, 23, 23, 23, |
132 |
|
|
23, 23, 23, 23, 23, 23, 24, 24, 24, 24, |
133 |
|
|
24, 24, 24, 24, 24, 24, 24, 24, 24, 24, |
134 |
|
|
24, 24, 24, 24, 24, 24, 24, 24, 24, 24, |
135 |
|
|
24, 24, 24, 24, 24, 24, 24, 24, 24, 24, |
136 |
|
|
24, 24, 24, 24, 24, 24, 24, 24, 24, 24, |
137 |
|
|
24, 24, 24, 24, 24, 25, 25, 25, 25, 25, |
138 |
|
|
25, 25, 25, 25, 25, 25, 25, 25, 25, 25, |
139 |
|
|
25, 25, 25, 25, 25, 25, 25, 25, 25, 25, |
140 |
|
|
25, 25, 25, 25, 25, 25, 25, 25, 25, 25, |
141 |
|
|
25, 25, 25, 25, 25, 25, 25, 25, 25, 25, |
142 |
|
|
25, 25, 25, 25, 25, 25, 26, 26, 26, 26, |
143 |
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, |
144 |
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, |
145 |
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, |
146 |
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, |
147 |
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 27, |
148 |
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, |
149 |
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, |
150 |
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, |
151 |
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, |
152 |
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, |
153 |
|
|
27, 27, 27, 27, 28, 28, 28, 28, 28, 28, |
154 |
|
|
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, |
155 |
|
|
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, |
156 |
|
|
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, |
157 |
|
|
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, |
158 |
|
|
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, |
159 |
|
|
28, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
160 |
|
|
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
161 |
|
|
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
162 |
|
|
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
163 |
|
|
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
164 |
|
|
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, |
165 |
|
|
30, 30, 30, 30, 30, 30, 30, 30, 30, 30, |
166 |
|
|
30, 30, 30, 30, 30, 30, 30, 30, 30, 30, |
167 |
|
|
30, 30, 30, 30, 30, 30, 30, 30, 30, 30, |
168 |
|
|
30, 30, 30, 30, 30, 30, 30, 30, 30, 30, |
169 |
|
|
30, 30, 30, 30, 30, 30, 30, 30, 30, 30, |
170 |
|
|
30, 30, 30, 30, 30, 30, 30, 30, 30, 30, |
171 |
|
|
30, 31, 31, 31, 31, 31, 31, 31, 31, 31, |
172 |
|
|
31, 31, 31, 31, 31, 31, 31, 31, 31, 31, |
173 |
|
|
31, 31, 31, 31, 31, 31, 31, 31, 31, 31, |
174 |
|
|
31, 31, 31, 31, 31, 31, 31, 31, 31, 31 |
175 |
|
|
}; |
176 |
|
|
|
177 |
|
|
inline uint16_t getCrc16(const std::string &str) A_WARN_UNUSED; |
178 |
|
|
constexpr2 inline float fastInvSqrt(float x) A_WARN_UNUSED; |
179 |
|
|
constexpr2 inline float fastSqrt(const float x) A_WARN_UNUSED; |
180 |
|
|
constexpr inline float weightedAverage(const float n1, const float n2, |
181 |
|
|
const float w) A_WARN_UNUSED; |
182 |
|
|
constexpr inline int roundDouble(const double v) A_WARN_UNUSED; |
183 |
|
|
constexpr2 inline int powerOfTwo(const unsigned int input) A_WARN_UNUSED; |
184 |
|
|
constexpr2 inline int fastSqrtInt(const unsigned int n) A_WARN_UNUSED; |
185 |
|
|
|
186 |
|
|
inline uint16_t getCrc16(const std::string &str) |
187 |
|
|
{ |
188 |
|
|
size_t f = str.size(); |
189 |
|
|
uint16_t crc16 = 0xffff; |
190 |
|
|
|
191 |
|
|
while (f != 0) |
192 |
|
|
{ |
193 |
|
|
f --; |
194 |
|
|
crc16 = CAST_U16( |
195 |
|
|
crc_table[(crc16 ^ (str[f])) & 0xff] ^ (crc16 >> 8)); |
196 |
|
|
} |
197 |
|
|
|
198 |
|
|
return crc16; |
199 |
|
|
} |
200 |
|
|
|
201 |
|
|
/* A very fast function to calculate the approximate inverse square root of a |
202 |
|
|
* floating point value and a helper function that uses it for getting the |
203 |
|
|
* normal squareroot. For an explanation of the inverse squareroot function |
204 |
|
|
* read: |
205 |
|
|
* http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf |
206 |
|
|
* |
207 |
|
|
* Unfortunately the original creator of this function seems to be unknown. |
208 |
|
|
*/ |
209 |
|
|
|
210 |
|
|
constexpr2 inline float fastInvSqrt(float x) |
211 |
|
|
{ |
212 |
|
|
union { int i; float x; } tmp = {0U}; |
213 |
|
|
const float xhalf = 0.5F * x; |
214 |
|
|
tmp.x = x; |
215 |
|
|
tmp.i = 0x5f375a86 - (tmp.i >> 1); |
216 |
|
|
x = tmp.x; |
217 |
|
|
x = x * (1.5F - xhalf * x * x); |
218 |
|
|
return x; |
219 |
|
|
} |
220 |
|
|
|
221 |
|
|
constexpr2 inline float fastSqrt(const float x) |
222 |
|
|
{ |
223 |
|
|
return 1.0F / fastInvSqrt(x); |
224 |
|
|
} |
225 |
|
|
|
226 |
|
|
constexpr inline float weightedAverage(const float n1, const float n2, |
227 |
|
|
const float w) |
228 |
|
|
{ |
229 |
|
|
return w < 0.0F ? n1 : (w > 1.0F ? n2 : w * n2 + (1.0F - w) * n1); |
230 |
|
|
} |
231 |
|
|
|
232 |
|
|
constexpr inline int roundDouble(const double v) |
233 |
|
|
{ |
234 |
✓✗✗✗
|
2 |
return (v > 0.0) ? CAST_S32(v + 0.5) : CAST_S32(v - 0.5); |
235 |
|
|
} |
236 |
|
|
|
237 |
|
|
constexpr2 inline int powerOfTwo(const unsigned int input) |
238 |
|
|
{ |
239 |
|
|
unsigned int value = 1; |
240 |
|
|
while (value < input) |
241 |
|
|
value <<= 1; |
242 |
|
|
return value; |
243 |
|
|
} |
244 |
|
|
|
245 |
|
|
constexpr2 inline int fastSqrtInt(const unsigned int n) |
246 |
|
|
{ |
247 |
✓✓ |
1005 |
if (n < 1000) |
248 |
|
1000 |
return CAST_S32(square_roots[n]); |
249 |
|
5 |
return CAST_S32(sqrt(n)); |
250 |
|
|
} |
251 |
|
|
|
252 |
|
|
#endif // UTILS_MATHUTILS_H |