summaryrefslogtreecommitdiff
path: root/src/core/math_func.hpp
blob: d36dc55f9c8796baf97bf5b6330bcb17a4a70e54 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
/*
 * This file is part of OpenTTD.
 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
 */

/** @file math_func.hpp Integer math functions */

#ifndef MATH_FUNC_HPP
#define MATH_FUNC_HPP

/**
 * Returns the maximum of two values.
 *
 * This function returns the greater value of two given values.
 * If they are equal the value of a is returned.
 *
 * @param a The first value
 * @param b The second value
 * @return The greater value or a if equals
 */
template <typename T>
static inline T max(const T a, const T b)
{
	return (a >= b) ? a : b;
}

/**
 * Returns the minimum of two values.
 *
 * This function returns the smaller value of two given values.
 * If they are equal the value of b is returned.
 *
 * @param a The first value
 * @param b The second value
 * @return The smaller value or b if equals
 */
template <typename T>
static inline T min(const T a, const T b)
{
	return (a < b) ? a : b;
}

/**
 * Returns the minimum of two integer.
 *
 * This function returns the smaller value of two given integers.
 *
 * @param a The first integer
 * @param b The second integer
 * @return The smaller value
 */
static inline int min(const int a, const int b)
{
	return min<int>(a, b);
}

/**
 * Returns the minimum of two unsigned integers.
 *
 * This function returns the smaller value of two given unsigned integers.
 *
 * @param a The first unsigned integer
 * @param b The second unsigned integer
 * @return The smaller value
 */
static inline uint minu(const uint a, const uint b)
{
	return min<uint>(a, b);
}

/**
 * Returns the absolute value of (scalar) variable.
 *
 * @note assumes variable to be signed
 * @param a The value we want to unsign
 * @return The unsigned value
 */
template <typename T>
static inline T abs(const T a)
{
	return (a < (T)0) ? -a : a;
}

/**
 * Return the smallest multiple of n equal or greater than x
 *
 * @note n must be a power of 2
 * @param x The min value
 * @param n The base of the number we are searching
 * @return The smallest multiple of n equal or greater than x
 */
template <typename T>
static inline T Align(const T x, uint n)
{
	assert((n & (n - 1)) == 0 && n != 0);
	n--;
	return (T)((x + n) & ~((T)n));
}

/**
 * Return the smallest multiple of n equal or greater than x
 * Applies to pointers only
 *
 * @note n must be a power of 2
 * @param x The min value
 * @param n The base of the number we are searching
 * @return The smallest multiple of n equal or greater than x
 * @see Align()
 */
template <typename T>
static inline T *AlignPtr(T *x, uint n)
{
	assert_compile(sizeof(size_t) == sizeof(void *));
	return reinterpret_cast<T *>(Align((size_t)x, n));
}

/**
 * Clamp a value between an interval.
 *
 * This function returns a value which is between the given interval of
 * min and max. If the given value is in this interval the value itself
 * is returned otherwise the border of the interval is returned, according
 * which side of the interval was 'left'.
 *
 * @note The min value must be less or equal of max or you get some
 *       unexpected results.
 * @param a The value to clamp/truncate.
 * @param min The minimum of the interval.
 * @param max the maximum of the interval.
 * @returns A value between min and max which is closest to a.
 * @see ClampU(uint, uint, uint)
 * @see Clamp(int, int, int)
 */
template <typename T>
static inline T Clamp(const T a, const T min, const T max)
{
	assert(min <= max);
	if (a <= min) return min;
	if (a >= max) return max;
	return a;
}

/**
 * Clamp an integer between an interval.
 *
 * This function returns a value which is between the given interval of
 * min and max. If the given value is in this interval the value itself
 * is returned otherwise the border of the interval is returned, according
 * which side of the interval was 'left'.
 *
 * @note The min value must be less or equal of max or you get some
 *       unexpected results.
 * @param a The value to clamp/truncate.
 * @param min The minimum of the interval.
 * @param max the maximum of the interval.
 * @returns A value between min and max which is closest to a.
 * @see ClampU(uint, uint, uint)
 */
static inline int Clamp(const int a, const int min, const int max)
{
	return Clamp<int>(a, min, max);
}

/**
 * Clamp an unsigned integer between an interval.
 *
 * This function returns a value which is between the given interval of
 * min and max. If the given value is in this interval the value itself
 * is returned otherwise the border of the interval is returned, according
 * which side of the interval was 'left'.
 *
 * @note The min value must be less or equal of max or you get some
 *       unexpected results.
 * @param a The value to clamp/truncate.
 * @param min The minimum of the interval.
 * @param max the maximum of the interval.
 * @returns A value between min and max which is closest to a.
 * @see Clamp(int, int, int)
 */
static inline uint ClampU(const uint a, const uint min, const uint max)
{
	return Clamp<uint>(a, min, max);
}

/**
 * Reduce a signed 64-bit int to a signed 32-bit one
 *
 * This function clamps a 64-bit integer to a 32-bit integer.
 * If the 64-bit value is smaller than the smallest 32-bit integer
 * value 0x80000000 this value is returned (the left one bit is the sign bit).
 * If the 64-bit value is greater than the greatest 32-bit integer value 0x7FFFFFFF
 * this value is returned. In all other cases the 64-bit value 'fits' in a
 * 32-bits integer field and so the value is casted to int32 and returned.
 *
 * @param a The 64-bit value to clamps
 * @return The 64-bit value reduced to a 32-bit value
 * @see Clamp(int, int, int)
 */
static inline int32 ClampToI32(const int64 a)
{
	return static_cast<int32>(Clamp<int64>(a, INT32_MIN, INT32_MAX));
}

/**
 * Reduce an unsigned 64-bit int to an unsigned 16-bit one
 *
 * @param a The 64-bit value to clamp
 * @return The 64-bit value reduced to a 16-bit value
 * @see ClampU(uint, uint, uint)
 */
static inline uint16 ClampToU16(const uint64 a)
{
	/* MSVC thinks, in its infinite wisdom, that int min(int, int) is a better
	 * match for min(uint64, uint) than uint64 min(uint64, uint64). As such we
	 * need to cast the UINT16_MAX to prevent MSVC from displaying its
	 * infinite loads of warnings. */
	return static_cast<uint16>(min<uint64>(a, static_cast<uint64>(UINT16_MAX)));
}

/**
 * Returns the (absolute) difference between two (scalar) variables
 *
 * @param a The first scalar
 * @param b The second scalar
 * @return The absolute difference between the given scalars
 */
template <typename T>
static inline T Delta(const T a, const T b)
{
	return (a < b) ? b - a : a - b;
}

/**
 * Checks if a value is between a window started at some base point.
 *
 * This function checks if the value x is between the value of base
 * and base+size. If x equals base this returns true. If x equals
 * base+size this returns false.
 *
 * @param x The value to check
 * @param base The base value of the interval
 * @param size The size of the interval
 * @return True if the value is in the interval, false else.
 */
template <typename T>
static inline bool IsInsideBS(const T x, const size_t base, const size_t size)
{
	return (size_t)(x - base) < size;
}

/**
 * Checks if a value is in an interval.
 *
 * Returns true if a value is in the interval of [min, max).
 *
 * @param x The value to check
 * @param min The minimum of the interval
 * @param max The maximum of the interval
 * @see IsInsideBS()
 */
template <typename T>
static inline bool IsInsideMM(const T x, const size_t min, const size_t max)
{
	return (size_t)(x - min) < (max - min);
}

/**
 * Type safe swap operation
 * @param a variable to swap with b
 * @param b variable to swap with a
 */
template <typename T>
static inline void Swap(T &a, T &b)
{
	T t = a;
	a = b;
	b = t;
}

/**
 * Converts a "fract" value 0..255 to "percent" value 0..100
 * @param i value to convert, range 0..255
 * @return value in range 0..100
 */
static inline uint ToPercent8(uint i)
{
	assert(i < 256);
	return i * 101 >> 8;
}

/**
 * Converts a "fract" value 0..65535 to "percent" value 0..100
 * @param i value to convert, range 0..65535
 * @return value in range 0..100
 */
static inline uint ToPercent16(uint i)
{
	assert(i < 65536);
	return i * 101 >> 16;
}

int LeastCommonMultiple(int a, int b);
int GreatestCommonDivisor(int a, int b);
int DivideApprox(int a, int b);

/**
 * Computes ceil(a / b) for non-negative a and b.
 * @param a Numerator
 * @param b Denominator
 * @return Quotient, rounded up
 */
static inline uint CeilDiv(uint a, uint b)
{
	return (a + b - 1) / b;
}

/**
 * Computes ceil(a / b) * b for non-negative a and b.
 * @param a Numerator
 * @param b Denominator
 * @return a rounded up to the nearest multiple of b.
 */
static inline uint Ceil(uint a, uint b)
{
	return CeilDiv(a, b) * b;
}

/**
 * Computes round(a / b) for signed a and unsigned b.
 * @param a Numerator
 * @param b Denominator
 * @return Quotient, rounded to nearest
 */
static inline int RoundDivSU(int a, uint b)
{
	if (a > 0) {
		/* 0.5 is rounded to 1 */
		return (a + static_cast<int>(b) / 2) / static_cast<int>(b);
	} else {
		/* -0.5 is rounded to 0 */
		return (a - (static_cast<int>(b) - 1) / 2) / static_cast<int>(b);
	}
}

/**
 * Computes (a / b) rounded away from zero.
 * @param a Numerator
 * @param b Denominator
 * @return Quotient, rounded away from zero
 */
static inline int DivAwayFromZero(int a, uint b)
{
	const int _b = static_cast<int>(b);
	if (a > 0) {
		return (a + _b - 1) / _b;
	} else {
		/* Note: Behaviour of negative numerator division is truncation toward zero. */
		return (a - _b + 1) / _b;
	}
}

uint32 IntSqrt(uint32 num);

#endif /* MATH_FUNC_HPP */