GCC Code Coverage Report
Directory: src/ Exec Total Coverage
File: src/utils/mathutils.h Lines: 4 18 22.2 %
Date: 2021-03-17 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-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