GCC Code Coverage Report
Directory: src/ Exec Total Coverage
File: src/utils/mathutils.h Lines: 4 18 22.2 %
Date: 2017-11-29 Branches: 3 12 25.0 %

Line Branch Exec Source
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-2017  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

4
    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
2010
    if (n < 1000)
247
2000
        return CAST_S32(square_roots[n]);
248
10
    return CAST_S32(sqrt(n));
249
}
250
251
#endif  // UTILS_MATHUTILS_H