src/core/math_func.hpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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/>.
   6  */
   7
   8 /** @file math_func.hpp Integer math functions */
   9
  10 #ifndef MATH_FUNC_HPP
  11 #define MATH_FUNC_HPP
  12
  13 #include "strong_typedef_type.hpp"
  14
  15 /**
  16  * Returns the absolute value of (scalar) variable.
  17  *
  18  * @note assumes variable to be signed
  19  * @param a The value we want to unsign
  20  * @return The unsigned value
  21  */
  22 template <typename T>
  23 constexpr T abs(const T a)
  24 {
  25         return (a < static_cast<T>(0)) ? -a : a;
  26 }
  27
  28 /**
  29  * Return the smallest multiple of n equal or greater than x
  30  *
  31  * @note n must be a power of 2
  32  * @param x The min value
  33  * @param n The base of the number we are searching
  34  * @return The smallest multiple of n equal or greater than x
  35  */
  36 template <typename T>
  37 constexpr T Align(const T x, uint n)
  38 {
  39         assert((n & (n - 1)) == 0 && n != 0);
  40         n--;
  41         return static_cast<T>((x + n) & ~static_cast<T>(n));
  42 }
  43
  44 /**
  45  * Return the smallest multiple of n equal or greater than x
  46  * Applies to pointers only
  47  *
  48  * @note n must be a power of 2
  49  * @param x The min value
  50  * @param n The base of the number we are searching
  51  * @return The smallest multiple of n equal or greater than x
  52  * @see Align()
  53  */
  54 template <typename T>
  55 constexpr T *AlignPtr(T *x, uint n)
  56 {
  57         static_assert(sizeof(uintptr_t) == sizeof(void *));
  58         return reinterpret_cast<T *>(Align(reinterpret_cast<uintptr_t>(x), n));
  59 }
  60
  61 /**
  62  * Clamp a value between an interval.
  63  *
  64  * This function returns a value which is between the given interval of
  65  * min and max. If the given value is in this interval the value itself
  66  * is returned otherwise the border of the interval is returned, according
  67  * which side of the interval was 'left'.
  68  *
  69  * @note The min value must be less or equal of max or you get some
  70  *       unexpected results.
  71  * @param a The value to clamp/truncate.
  72  * @param min The minimum of the interval.
  73  * @param max the maximum of the interval.
  74  * @returns A value between min and max which is closest to a.
  75  * @see ClampU(uint, uint, uint)
  76  * @see Clamp(int, int, int)
  77  */
  78 template <typename T>
  79 constexpr T Clamp(const T a, const T min, const T max)
  80 {
  81         assert(min <= max);
  82         if (a <= min) return min;
  83         if (a >= max) return max;
  84         return a;
  85 }
  86
  87 /**
  88  * Clamp a value between an interval.
  89  *
  90  * This function returns a value which is between the given interval of
  91  * min and max. If the given value is in this interval the value itself
  92  * is returned otherwise the border of the interval is returned, according
  93  * which side of the interval was 'left'.
  94  *
  95  * @note If the min value is greater than the max, return value is the average of the min and max.
  96  * @param a The value to clamp/truncate.
  97  * @param min The minimum of the interval.
  98  * @param max the maximum of the interval.
  99  * @returns A value between min and max which is closest to a.
 100  */
 101 template <typename T>
 102 constexpr T SoftClamp(const T a, const T min, const T max)
 103 {
 104         if (min > max) {
 105                 using U = std::make_unsigned_t<T>;
 106                 return min - (U(min) - max) / 2;
 107         }
 108         if (a <= min) return min;
 109         if (a >= max) return max;
 110         return a;
 111 }
 112
 113 /**
 114  * Clamp an integer between an interval.
 115  *
 116  * This function returns a value which is between the given interval of
 117  * min and max. If the given value is in this interval the value itself
 118  * is returned otherwise the border of the interval is returned, according
 119  * which side of the interval was 'left'.
 120  *
 121  * @note The min value must be less or equal of max or you get some
 122  *       unexpected results.
 123  * @param a The value to clamp/truncate.
 124  * @param min The minimum of the interval.
 125  * @param max the maximum of the interval.
 126  * @returns A value between min and max which is closest to a.
 127  * @see ClampU(uint, uint, uint)
 128  */
 129 constexpr int Clamp(const int a, const int min, const int max)
 130 {
 131         return Clamp<int>(a, min, max);
 132 }
 133
 134 /**
 135  * Clamp an unsigned integer between an interval.
 136  *
 137  * This function returns a value which is between the given interval of
 138  * min and max. If the given value is in this interval the value itself
 139  * is returned otherwise the border of the interval is returned, according
 140  * which side of the interval was 'left'.
 141  *
 142  * @note The min value must be less or equal of max or you get some
 143  *       unexpected results.
 144  * @param a The value to clamp/truncate.
 145  * @param min The minimum of the interval.
 146  * @param max the maximum of the interval.
 147  * @returns A value between min and max which is closest to a.
 148  * @see Clamp(int, int, int)
 149  */
 150 constexpr uint ClampU(const uint a, const uint min, const uint max)
 151 {
 152         return Clamp<uint>(a, min, max);
 153 }
 154
 155 /**
 156  * Clamp the given value down to lie within the requested type.
 157  *
 158  * For example ClampTo<uint8_t> will return a value clamped to the range of 0
 159  * to 255. Anything smaller will become 0, anything larger will become 255.
 160  *
 161  * @param a The 64-bit value to clamp.
 162  * @return The 64-bit value reduced to a value within the given allowed range
 163  * for the return type.
 164  * @see Clamp(int, int, int)
 165  */
 166 template <typename To, typename From, std::enable_if_t<std::is_integral<From>::value, int> = 0>
 167 constexpr To ClampTo(From value)
 168 {
 169         static_assert(std::numeric_limits<To>::is_integer, "Do not clamp from non-integer values");
 170         static_assert(std::numeric_limits<From>::is_integer, "Do not clamp to non-integer values");
 171
 172         if constexpr (sizeof(To) >= sizeof(From) && std::numeric_limits<To>::is_signed == std::numeric_limits<From>::is_signed) {
 173                 /* Same signedness and To type is larger or equal than From type, no clamping is required. */
 174                 return static_cast<To>(value);
 175         }
 176
 177         if constexpr (sizeof(To) > sizeof(From) && std::numeric_limits<To>::is_signed) {
 178                 /* Signed destination and a larger To type, no clamping is required. */
 179                 return static_cast<To>(value);
 180         }
 181
 182         /* Get the bigger of the two types based on essentially the number of bits. */
 183         using BiggerType = typename std::conditional<sizeof(From) >= sizeof(To), From, To>::type;
 184
 185         if constexpr (std::numeric_limits<To>::is_signed) {
 186                 /* The output is a signed number. */
 187                 if constexpr (std::numeric_limits<From>::is_signed) {
 188                         /* Both input and output are signed. */
 189                         return static_cast<To>(std::clamp<BiggerType>(value,
 190                                         std::numeric_limits<To>::lowest(), std::numeric_limits<To>::max()));
 191                 }
 192
 193                 /* The input is unsigned, so skip the minimum check and use unsigned variant of the biggest type as intermediate type. */
 194                 using BiggerUnsignedType = typename std::make_unsigned<BiggerType>::type;
 195                 return static_cast<To>(std::min<BiggerUnsignedType>(std::numeric_limits<To>::max(), value));
 196         }
 197
 198         /* The output is unsigned. */
 199
 200         if constexpr (std::numeric_limits<From>::is_signed) {
 201                 /* Input is signed; account for the negative numbers in the input. */
 202                 if constexpr (sizeof(To) >= sizeof(From)) {
 203                         /* If the output type is larger or equal to the input type, then only clamp the negative numbers. */
 204                         return static_cast<To>(std::max<From>(value, 0));
 205                 }
 206
 207                 /* The output type is smaller than the input type. */
 208                 using BiggerSignedType = typename std::make_signed<BiggerType>::type;
 209                 return static_cast<To>(std::clamp<BiggerSignedType>(value,
 210                                 std::numeric_limits<To>::lowest(), std::numeric_limits<To>::max()));
 211         }
 212
 213         /* The input and output are unsigned, just clamp at the high side. */
 214         return static_cast<To>(std::min<BiggerType>(value, std::numeric_limits<To>::max()));
 215 }
 216
 217 /**
 218  * Specialization of ClampTo for #StrongType::Typedef.
 219  */
 220 template <typename To, typename From, std::enable_if_t<std::is_base_of<StrongTypedefBase, From>::value, int> = 0>
 221 constexpr To ClampTo(From value)
 222 {
 223         return ClampTo<To>(value.base());
 224 }
 225
 226 /**
 227  * Returns the (absolute) difference between two (scalar) variables
 228  *
 229  * @param a The first scalar
 230  * @param b The second scalar
 231  * @return The absolute difference between the given scalars
 232  */
 233 template <typename T>
 234 constexpr T Delta(const T a, const T b)
 235 {
 236         return (a < b) ? b - a : a - b;
 237 }
 238
 239 /**
 240  * Checks if a value is between a window started at some base point.
 241  *
 242  * This function checks if the value x is between the value of base
 243  * and base+size. If x equals base this returns true. If x equals
 244  * base+size this returns false.
 245  *
 246  * @param x The value to check
 247  * @param base The base value of the interval
 248  * @param size The size of the interval
 249  * @return True if the value is in the interval, false else.
 250  */
 251 template <typename T>
 252 constexpr bool IsInsideBS(const T x, const size_t base, const size_t size)
 253 {
 254         return static_cast<size_t>(x - base) < size;
 255 }
 256
 257 /**
 258  * Checks if a value is in an interval.
 259  *
 260  * Returns true if a value is in the interval of [min, max).
 261  *
 262  * @param x The value to check
 263  * @param min The minimum of the interval
 264  * @param max The maximum of the interval
 265  * @see IsInsideBS()
 266  */
 267 template <typename T, std::enable_if_t<std::disjunction_v<std::is_convertible<T, size_t>, std::is_base_of<StrongTypedefBase, T>>, int> = 0>
 268 constexpr bool IsInsideMM(const T x, const size_t min, const size_t max) noexcept
 269 {
 270         if constexpr (std::is_base_of_v<StrongTypedefBase, T>) {
 271                 return static_cast<size_t>(x.base() - min) < (max - min);
 272         } else {
 273                 return static_cast<size_t>(x - min) < (max - min);
 274         }
 275 }
 276
 277 /**
 278  * Type safe swap operation
 279  * @param a variable to swap with b
 280  * @param b variable to swap with a
 281  */
 282 template <typename T>
 283 constexpr void Swap(T &a, T &b)
 284 {
 285         T t = a;
 286         a = b;
 287         b = t;
 288 }
 289
 290 /**
 291  * Converts a "fract" value 0..255 to "percent" value 0..100
 292  * @param i value to convert, range 0..255
 293  * @return value in range 0..100
 294  */
 295 constexpr uint ToPercent8(uint i)
 296 {
 297         assert(i < 256);
 298         return i * 101 >> 8;
 299 }
 300
 301 /**
 302  * Converts a "fract" value 0..65535 to "percent" value 0..100
 303  * @param i value to convert, range 0..65535
 304  * @return value in range 0..100
 305  */
 306 constexpr uint ToPercent16(uint i)
 307 {
 308         assert(i < 65536);
 309         return i * 101 >> 16;
 310 }
 311
 312 int DivideApprox(int a, int b);
 313
 314 /**
 315  * Computes ceil(a / b) for non-negative a and b.
 316  * @param a Numerator
 317  * @param b Denominator
 318  * @return Quotient, rounded up
 319  */
 320 constexpr uint CeilDiv(uint a, uint b)
 321 {
 322         return (a + b - 1) / b;
 323 }
 324
 325 /**
 326  * Computes ceil(a / b) * b for non-negative a and b.
 327  * @param a Numerator
 328  * @param b Denominator
 329  * @return a rounded up to the nearest multiple of b.
 330  */
 331 constexpr uint Ceil(uint a, uint b)
 332 {
 333         return CeilDiv(a, b) * b;
 334 }
 335
 336 /**
 337  * Computes round(a / b) for signed a and unsigned b.
 338  * @param a Numerator
 339  * @param b Denominator
 340  * @return Quotient, rounded to nearest
 341  */
 342 constexpr int RoundDivSU(int a, uint b)
 343 {
 344         if (a > 0) {
 345                 /* 0.5 is rounded to 1 */
 346                 return (a + static_cast<int>(b) / 2) / static_cast<int>(b);
 347         } else {
 348                 /* -0.5 is rounded to 0 */
 349                 return (a - (static_cast<int>(b) - 1) / 2) / static_cast<int>(b);
 350         }
 351 }
 352
 353 /**
 354  * Computes ten to the given power.
 355  * @param power The power of ten to get.
 356  * @return The power of ten.
 357  */
 358 constexpr uint64_t PowerOfTen(int power)
 359 {
 360         assert(power >= 0 && power <= 20 /* digits in uint64_t */);
 361         uint64_t result = 1;
 362         for (int i = 0; i < power; i++) result *= 10;
 363         return result;
 364 }
 365
 366 uint32_t IntSqrt(uint32_t num);
 367
 368 #endif /* MATH_FUNC_HPP */