ManaPlus
mathutils.h
Go to the documentation of this file.
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  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  if (n < 1000)
248  return CAST_S32(square_roots[n]);
249  return CAST_S32(sqrt(n));
250 }
251 
252 #endif // UTILS_MATHUTILS_H
CAST_U16
#define CAST_U16
Definition: cast.h:29
CAST_S32
#define CAST_S32
Definition: cast.h:30
x
x
Definition: graphics_calcImageRect.hpp:73
constexpr2
#define constexpr2
Definition: localconsts.h:49
A_WARN_UNUSED
#define A_WARN_UNUSED
Definition: localconsts.h:161
constexpr
#define constexpr
Definition: localconsts.h:48
powerOfTwo
int powerOfTwo(const unsigned int input)
Definition: mathutils.h:237
fastSqrt
float fastSqrt(const float x)
Definition: mathutils.h:221
weightedAverage
float weightedAverage(const float n1, const float n2, const float w)
Definition: mathutils.h:226
square_roots
static const uint8_t square_roots[1000]
Definition: mathutils.h:73
fastInvSqrt
float fastInvSqrt(float x)
Definition: mathutils.h:210
getCrc16
uint16_t getCrc16(const std::string &str)
Definition: mathutils.h:186
fastSqrtInt
int fastSqrtInt(const unsigned int n)
Definition: mathutils.h:245
crc_table
static const uint16_t crc_table[256]
Definition: mathutils.h:37
roundDouble
int roundDouble(const double v)
Definition: mathutils.h:232
Generated on Wed Mar 17 2021 19:19:10 for ManaPlus by doxygen 1.9.1