src/core/math_func.hpp

   1 /* $Id: math_func.hpp 25347 2013-06-09 12:50:33Z fonsinchen $ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * 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.
   6  * 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.
   7  * 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/>.
   8  */
   9
  10 /** @file math_func.hpp Integer math functions */
  11
  12 #ifndef MATH_FUNC_HPP
  13 #define MATH_FUNC_HPP
  14
  15 /**
  16  * Returns the maximum of two values.
  17  *
  18  * This function returns the greater value of two given values.
  19  * If they are equal the value of a is returned.
  20  *
  21  * @param a The first value
  22  * @param b The second value
  23  * @return The greater value or a if equals
  24  */
  25 template <typename T>
  26 static inline T max(const T a, const T b)
  27 {
  28         return (a >= b) ? a : b;
  29 }
  30
  31 /**
  32  * Returns the minimum of two values.
  33  *
  34  * This function returns the smaller value of two given values.
  35  * If they are equal the value of b is returned.
  36  *
  37  * @param a The first value
  38  * @param b The second value
  39  * @return The smaller value or b if equals
  40  */
  41 template <typename T>
  42 static inline T min(const T a, const T b)
  43 {
  44         return (a < b) ? a : b;
  45 }
  46
  47 /**
  48  * Returns the minimum of two integer.
  49  *
  50  * This function returns the smaller value of two given integers.
  51  *
  52  * @param a The first integer
  53  * @param b The second integer
  54  * @return The smaller value
  55  */
  56 static inline int min(const int a, const int b)
  57 {
  58         return min<int>(a, b);
  59 }
  60
  61 /**
  62  * Returns the minimum of two unsigned integers.
  63  *
  64  * This function returns the smaller value of two given unsigned integers.
  65  *
  66  * @param a The first unsigned integer
  67  * @param b The second unsigned integer
  68  * @return The smaller value
  69  */
  70 static inline uint minu(const uint a, const uint b)
  71 {
  72         return min<uint>(a, b);
  73 }
  74
  75 /**
  76  * Returns the absolute value of (scalar) variable.
  77  *
  78  * @note assumes variable to be signed
  79  * @param a The value we want to unsign
  80  * @return The unsigned value
  81  */
  82 template <typename T>
  83 static inline T abs(const T a)
  84 {
  85         return (a < (T)0) ? -a : a;
  86 }
  87
  88 /**
  89  * Return the smallest multiple of n equal or greater than x
  90  *
  91  * @note n must be a power of 2
  92  * @param x The min value
  93  * @param n The base of the number we are searching
  94  * @return The smallest multiple of n equal or greater than x
  95  */
  96 template <typename T>
  97 static inline T Align(const T x, uint n)
  98 {
  99         assert((n & (n - 1)) == 0 && n != 0);
 100         n--;
 101         return (T)((x + n) & ~((T)n));
 102 }
 103
 104 /**
 105  * Return the smallest multiple of n equal or greater than x
 106  * Applies to pointers only
 107  *
 108  * @note n must be a power of 2
 109  * @param x The min value
 110  * @param n The base of the number we are searching
 111  * @return The smallest multiple of n equal or greater than x
 112  * @see Align()
 113  */
 114 template <typename T>
 115 static inline T *AlignPtr(T *x, uint n)
 116 {
 117         assert_compile(sizeof(size_t) == sizeof(void *));
 118         return (T *)Align((size_t)x, n);
 119 }
 120
 121 /**
 122  * Clamp a value between an interval.
 123  *
 124  * This function returns a value which is between the given interval of
 125  * min and max. If the given value is in this interval the value itself
 126  * is returned otherwise the border of the interval is returned, according
 127  * which side of the interval was 'left'.
 128  *
 129  * @note The min value must be less or equal of max or you get some
 130  *       unexpected results.
 131  * @param a The value to clamp/truncate.
 132  * @param min The minimum of the interval.
 133  * @param max the maximum of the interval.
 134  * @returns A value between min and max which is closest to a.
 135  * @see ClampU(uint, uint, uint)
 136  * @see Clamp(int, int, int)
 137  */
 138 template <typename T>
 139 static inline T Clamp(const T a, const T min, const T max)
 140 {
 141         assert(min <= max);
 142         if (a <= min) return min;
 143         if (a >= max) return max;
 144         return a;
 145 }
 146
 147 /**
 148  * Clamp a value between an interval.
 149  *
 150  * This function returns a value which is between the given interval of
 151  * min and max. If the given value is in this interval the value itself
 152  * is returned otherwise the border of the interval is returned, according
 153  * which side of the interval was 'left'.
 154  *
 155  * @note If the min value is greater than the return value is the average of the min and max.
 156  * @param a The value to clamp/truncate.
 157  * @param min The minimum of the interval.
 158  * @param max the maximum of the interval.
 159  * @returns A value between min and max which is closest to a.
 160  */
 161 template <typename T>
 162 static inline T SoftClamp(const T a, const T min, const T max)
 163 {
 164         if (min > max) return (min + max) / 2;
 165         if (a <= min) return min;
 166         if (a >= max) return max;
 167         return a;
 168 }
 169
 170 /**
 171  * Clamp an integer between an interval.
 172  *
 173  * This function returns a value which is between the given interval of
 174  * min and max. If the given value is in this interval the value itself
 175  * is returned otherwise the border of the interval is returned, according
 176  * which side of the interval was 'left'.
 177  *
 178  * @note The min value must be less or equal of max or you get some
 179  *       unexpected results.
 180  * @param a The value to clamp/truncate.
 181  * @param min The minimum of the interval.
 182  * @param max the maximum of the interval.
 183  * @returns A value between min and max which is closest to a.
 184  * @see ClampU(uint, uint, uint)
 185  */
 186 static inline int Clamp(const int a, const int min, const int max)
 187 {
 188         return Clamp<int>(a, min, max);
 189 }
 190
 191 /**
 192  * Clamp an unsigned integer between an interval.
 193  *
 194  * This function returns a value which is between the given interval of
 195  * min and max. If the given value is in this interval the value itself
 196  * is returned otherwise the border of the interval is returned, according
 197  * which side of the interval was 'left'.
 198  *
 199  * @note The min value must be less or equal of max or you get some
 200  *       unexpected results.
 201  * @param a The value to clamp/truncate.
 202  * @param min The minimum of the interval.
 203  * @param max the maximum of the interval.
 204  * @returns A value between min and max which is closest to a.
 205  * @see Clamp(int, int, int)
 206  */
 207 static inline uint ClampU(const uint a, const uint min, const uint max)
 208 {
 209         return Clamp<uint>(a, min, max);
 210 }
 211
 212 /**
 213  * Reduce a signed 64-bit int to a signed 32-bit one
 214  *
 215  * This function clamps a 64-bit integer to a 32-bit integer.
 216  * If the 64-bit value is smaller than the smallest 32-bit integer
 217  * value 0x80000000 this value is returned (the left one bit is the sign bit).
 218  * If the 64-bit value is greater than the greatest 32-bit integer value 0x7FFFFFFF
 219  * this value is returned. In all other cases the 64-bit value 'fits' in a
 220  * 32-bits integer field and so the value is casted to int32 and returned.
 221  *
 222  * @param a The 64-bit value to clamps
 223  * @return The 64-bit value reduced to a 32-bit value
 224  * @see Clamp(int, int, int)
 225  */
 226 static inline int32 ClampToI32(const int64 a)
 227 {
 228         return (int32)Clamp<int64>(a, INT32_MIN, INT32_MAX);
 229 }
 230
 231 /**
 232  * Reduce an unsigned 64-bit int to an unsigned 16-bit one
 233  *
 234  * @param a The 64-bit value to clamp
 235  * @return The 64-bit value reduced to a 16-bit value
 236  * @see ClampU(uint, uint, uint)
 237  */
 238 static inline uint16 ClampToU16(const uint64 a)
 239 {
 240         /* MSVC thinks, in its infinite wisdom, that int min(int, int) is a better
 241          * match for min(uint64, uint) than uint64 min(uint64, uint64). As such we
 242          * need to cast the UINT16_MAX to prevent MSVC from displaying its
 243          * infinite loads of warnings. */
 244         return (uint16)min<uint64>(a, (uint64)UINT16_MAX);
 245 }
 246
 247 /**
 248  * Returns the (absolute) difference between two (scalar) variables
 249  *
 250  * @param a The first scalar
 251  * @param b The second scalar
 252  * @return The absolute difference between the given scalars
 253  */
 254 template <typename T>
 255 static inline T Delta(const T a, const T b)
 256 {
 257         return (a < b) ? b - a : a - b;
 258 }
 259
 260 /**
 261  * Checks if a value is between a window started at some base point.
 262  *
 263  * This function checks if the value x is between the value of base
 264  * and base+size. If x equals base this returns true. If x equals
 265  * base+size this returns false.
 266  *
 267  * @param x The value to check
 268  * @param base The base value of the interval
 269  * @param size The size of the interval
 270  * @return True if the value is in the interval, false else.
 271  */
 272 template <typename T>
 273 static inline bool IsInsideBS(const T x, const uint base, const uint size)
 274 {
 275         return (uint)(x - base) < size;
 276 }
 277
 278 /**
 279  * Checks if a value is in an interval.
 280  *
 281  * Returns true if a value is in the interval of [min, max).
 282  *
 283  * @param x The value to check
 284  * @param min The minimum of the interval
 285  * @param max The maximum of the interval
 286  * @see IsInsideBS()
 287  */
 288 template <typename T>
 289 static inline bool IsInsideMM(const T x, const uint min, const uint max)
 290 {
 291         return (uint)(x - min) < (max - min);
 292 }
 293
 294 /**
 295  * Type safe swap operation
 296  * @param a variable to swap with b
 297  * @param b variable to swap with a
 298  */
 299 template <typename T>
 300 static inline void Swap(T &a, T &b)
 301 {
 302         T t = a;
 303         a = b;
 304         b = t;
 305 }
 306
 307 /**
 308  * Converts a "fract" value 0..255 to "percent" value 0..100
 309  * @param i value to convert, range 0..255
 310  * @return value in range 0..100
 311  */
 312 static inline uint ToPercent8(uint i)
 313 {
 314         assert(i < 256);
 315         return i * 101 >> 8;
 316 }
 317
 318 /**
 319  * Converts a "fract" value 0..65535 to "percent" value 0..100
 320  * @param i value to convert, range 0..65535
 321  * @return value in range 0..100
 322  */
 323 static inline uint ToPercent16(uint i)
 324 {
 325         assert(i < 65536);
 326         return i * 101 >> 16;
 327 }
 328
 329 int LeastCommonMultiple(int a, int b);
 330 int GreatestCommonDivisor(int a, int b);
 331 int DivideApprox(int a, int b);
 332
 333 /**
 334  * Computes ceil(a / b) for non-negative a and b.
 335  * @param a Numerator
 336  * @param b Denominator
 337  * @return Quotient, rounded up
 338  */
 339 static inline uint CeilDiv(uint a, uint b)
 340 {
 341         return (a + b - 1) / b;
 342 }
 343
 344 /**
 345  * Computes ceil(a / b) for non-negative a and b (templated).
 346  * @param a Numerator
 347  * @param b Denominator
 348  * @return Quotient, rounded up
 349  */
 350 template <typename T>
 351 static inline T CeilDivT(T a, T b)
 352 {
 353         return (a + b - 1) / b;
 354 }
 355
 356 /**
 357  * Computes ceil(a / b) * b for non-negative a and b.
 358  * @param a Numerator
 359  * @param b Denominator
 360  * @return a rounded up to the nearest multiple of b.
 361  */
 362 static inline uint Ceil(uint a, uint b)
 363 {
 364         return CeilDiv(a, b) * b;
 365 }
 366
 367 /**
 368  * Computes ceil(a / b) * b for non-negative a and b (templated).
 369  * @param a Numerator
 370  * @param b Denominator
 371  * @return a rounded up to the nearest multiple of b.
 372  */
 373 template <typename T>
 374 static inline T CeilT(T a, T b)
 375 {
 376         return CeilDivT<T>(a, b) * b;
 377 }
 378
 379 /**
 380  * Computes round(a / b) for signed a and unsigned b.
 381  * @param a Numerator
 382  * @param b Denominator
 383  * @return Quotient, rounded to nearest
 384  */
 385 static inline int RoundDivSU(int a, uint b)
 386 {
 387         if (a > 0) {
 388                 /* 0.5 is rounded to 1 */
 389                 return (a + (int)b / 2) / (int)b;
 390         } else {
 391                 /* -0.5 is rounded to 0 */
 392                 return (a - ((int)b - 1) / 2) / (int)b;
 393         }
 394 }
 395
 396 uint32 IntSqrt(uint32 num);
 397
 398 #endif /* MATH_FUNC_HPP */