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