src/util/numeric.h

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #pragma once
  21
  22 #include "basic_macros.h"
  23 #include "irrlichttypes.h"
  24 #include "irr_v2d.h"
  25 #include "irr_v3d.h"
  26 #include "irr_aabb3d.h"
  27
  28 #define rangelim(d, min, max) ((d) < (min) ? (min) : ((d) > (max) ? (max) : (d)))
  29 #define myfloor(x) ((x) < 0.0 ? (int)(x) - 1 : (int)(x))
  30 // The naive swap performs better than the xor version
  31 #define SWAP(t, x, y) do { \
  32         t temp = x; \
  33         x = y; \
  34         y = temp; \
  35 } while (0)
  36
  37
  38 inline s16 getContainerPos(s16 p, s16 d)
  39 {
  40         return (p >= 0 ? p : p - d + 1) / d;
  41 }
  42
  43 inline v2s16 getContainerPos(v2s16 p, s16 d)
  44 {
  45         return v2s16(
  46                 getContainerPos(p.X, d),
  47                 getContainerPos(p.Y, d)
  48         );
  49 }
  50
  51 inline v3s16 getContainerPos(v3s16 p, s16 d)
  52 {
  53         return v3s16(
  54                 getContainerPos(p.X, d),
  55                 getContainerPos(p.Y, d),
  56                 getContainerPos(p.Z, d)
  57         );
  58 }
  59
  60 inline v2s16 getContainerPos(v2s16 p, v2s16 d)
  61 {
  62         return v2s16(
  63                 getContainerPos(p.X, d.X),
  64                 getContainerPos(p.Y, d.Y)
  65         );
  66 }
  67
  68 inline v3s16 getContainerPos(v3s16 p, v3s16 d)
  69 {
  70         return v3s16(
  71                 getContainerPos(p.X, d.X),
  72                 getContainerPos(p.Y, d.Y),
  73                 getContainerPos(p.Z, d.Z)
  74         );
  75 }
  76
  77 inline void getContainerPosWithOffset(s16 p, s16 d, s16 &container, s16 &offset)
  78 {
  79         container = (p >= 0 ? p : p - d + 1) / d;
  80         offset = p & (d - 1);
  81 }
  82
  83 inline void getContainerPosWithOffset(const v2s16 &p, s16 d, v2s16 &container, v2s16 &offset)
  84 {
  85         getContainerPosWithOffset(p.X, d, container.X, offset.X);
  86         getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
  87 }
  88
  89 inline void getContainerPosWithOffset(const v3s16 &p, s16 d, v3s16 &container, v3s16 &offset)
  90 {
  91         getContainerPosWithOffset(p.X, d, container.X, offset.X);
  92         getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
  93         getContainerPosWithOffset(p.Z, d, container.Z, offset.Z);
  94 }
  95
  96
  97 inline bool isInArea(v3s16 p, s16 d)
  98 {
  99         return (
 100                 p.X >= 0 && p.X < d &&
 101                 p.Y >= 0 && p.Y < d &&
 102                 p.Z >= 0 && p.Z < d
 103         );
 104 }
 105
 106 inline bool isInArea(v2s16 p, s16 d)
 107 {
 108         return (
 109                 p.X >= 0 && p.X < d &&
 110                 p.Y >= 0 && p.Y < d
 111         );
 112 }
 113
 114 inline bool isInArea(v3s16 p, v3s16 d)
 115 {
 116         return (
 117                 p.X >= 0 && p.X < d.X &&
 118                 p.Y >= 0 && p.Y < d.Y &&
 119                 p.Z >= 0 && p.Z < d.Z
 120         );
 121 }
 122
 123 inline void sortBoxVerticies(v3s16 &p1, v3s16 &p2) {
 124         if (p1.X > p2.X)
 125                 SWAP(s16, p1.X, p2.X);
 126         if (p1.Y > p2.Y)
 127                 SWAP(s16, p1.Y, p2.Y);
 128         if (p1.Z > p2.Z)
 129                 SWAP(s16, p1.Z, p2.Z);
 130 }
 131
 132 inline v3s16 componentwise_min(const v3s16 &a, const v3s16 &b)
 133 {
 134         return v3s16(MYMIN(a.X, b.X), MYMIN(a.Y, b.Y), MYMIN(a.Z, b.Z));
 135 }
 136
 137 inline v3s16 componentwise_max(const v3s16 &a, const v3s16 &b)
 138 {
 139         return v3s16(MYMAX(a.X, b.X), MYMAX(a.Y, b.Y), MYMAX(a.Z, b.Z));
 140 }
 141
 142
 143 /** Returns \p f wrapped to the range [-360, 360]
 144  *
 145  *  See test.cpp for example cases.
 146  *
 147  *  \note This is also used in cases where degrees wrapped to the range [0, 360]
 148  *  is innapropriate (e.g. pitch needs negative values)
 149  *
 150  *  \internal functionally equivalent -- although precision may vary slightly --
 151  *  to fmodf((f), 360.0f) however empirical tests indicate that this approach is
 152  *  faster.
 153  */
 154 inline float modulo360f(float f)
 155 {
 156         int sign;
 157         int whole;
 158         float fraction;
 159
 160         if (f < 0) {
 161                 f = -f;
 162                 sign = -1;
 163         } else {
 164                 sign = 1;
 165         }
 166
 167         whole = f;
 168
 169         fraction = f - whole;
 170         whole %= 360;
 171
 172         return sign * (whole + fraction);
 173 }
 174
 175
 176 /** Returns \p f wrapped to the range [0, 360]
 177   */
 178 inline float wrapDegrees_0_360(float f)
 179 {
 180         float value = modulo360f(f);
 181         return value < 0 ? value + 360 : value;
 182 }
 183
 184
 185 /** Returns \p f wrapped to the range [-180, 180]
 186   */
 187 inline float wrapDegrees_180(float f)
 188 {
 189         float value = modulo360f(f + 180);
 190         if (value < 0)
 191                 value += 360;
 192         return value - 180;
 193 }
 194
 195 /*
 196         Pseudo-random (VC++ rand() sucks)
 197 */
 198 #define MYRAND_RANGE 0xffffffff
 199 u32 myrand();
 200 void mysrand(unsigned int seed);
 201 void myrand_bytes(void *out, size_t len);
 202 int myrand_range(int min, int max);
 203
 204 /*
 205         Miscellaneous functions
 206 */
 207
 208 inline u32 get_bits(u32 x, u32 pos, u32 len)
 209 {
 210         u32 mask = (1 << len) - 1;
 211         return (x >> pos) & mask;
 212 }
 213
 214 inline void set_bits(u32 *x, u32 pos, u32 len, u32 val)
 215 {
 216         u32 mask = (1 << len) - 1;
 217         *x &= ~(mask << pos);
 218         *x |= (val & mask) << pos;
 219 }
 220
 221 inline u32 calc_parity(u32 v)
 222 {
 223         v ^= v >> 16;
 224         v ^= v >> 8;
 225         v ^= v >> 4;
 226         v &= 0xf;
 227         return (0x6996 >> v) & 1;
 228 }
 229
 230 u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed);
 231
 232 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
 233                 f32 camera_fov, f32 range, f32 *distance_ptr=NULL);
 234
 235 s16 adjustDist(s16 dist, float zoom_fov);
 236
 237 /*
 238         Returns nearest 32-bit integer for given floating point number.
 239         <cmath> and <math.h> in VC++ don't provide round().
 240 */
 241 inline s32 myround(f32 f)
 242 {
 243         return (s32)(f < 0.f ? (f - 0.5f) : (f + 0.5f));
 244 }
 245
 246 /*
 247         Returns integer position of node in given floating point position
 248 */
 249 inline v3s16 floatToInt(v3f p, f32 d)
 250 {
 251         return v3s16(
 252                 (p.X + (p.X > 0 ? d / 2 : -d / 2)) / d,
 253                 (p.Y + (p.Y > 0 ? d / 2 : -d / 2)) / d,
 254                 (p.Z + (p.Z > 0 ? d / 2 : -d / 2)) / d);
 255 }
 256
 257 /*
 258         Returns integer position of node in given double precision position
 259  */
 260 inline v3s16 doubleToInt(v3d p, double d)
 261 {
 262         return v3s16(
 263                 (p.X + (p.X > 0 ? d / 2 : -d / 2)) / d,
 264                 (p.Y + (p.Y > 0 ? d / 2 : -d / 2)) / d,
 265                 (p.Z + (p.Z > 0 ? d / 2 : -d / 2)) / d);
 266 }
 267
 268 /*
 269         Returns floating point position of node in given integer position
 270 */
 271 inline v3f intToFloat(v3s16 p, f32 d)
 272 {
 273         return v3f(
 274                 (f32)p.X * d,
 275                 (f32)p.Y * d,
 276                 (f32)p.Z * d
 277         );
 278 }
 279
 280 // Random helper. Usually d=BS
 281 inline aabb3f getNodeBox(v3s16 p, float d)
 282 {
 283         return aabb3f(
 284                 (float)p.X * d - 0.5f * d,
 285                 (float)p.Y * d - 0.5f * d,
 286                 (float)p.Z * d - 0.5f * d,
 287                 (float)p.X * d + 0.5f * d,
 288                 (float)p.Y * d + 0.5f * d,
 289                 (float)p.Z * d + 0.5f * d
 290         );
 291 }
 292
 293
 294 class IntervalLimiter
 295 {
 296 public:
 297         IntervalLimiter() = default;
 298
 299         /*
 300                 dtime: time from last call to this method
 301                 wanted_interval: interval wanted
 302                 return value:
 303                         true: action should be skipped
 304                         false: action should be done
 305         */
 306         bool step(float dtime, float wanted_interval)
 307         {
 308                 m_accumulator += dtime;
 309                 if (m_accumulator < wanted_interval)
 310                         return false;
 311                 m_accumulator -= wanted_interval;
 312                 return true;
 313         }
 314
 315 private:
 316         float m_accumulator = 0.0f;
 317 };
 318
 319
 320 /*
 321         Splits a list into "pages". For example, the list [1,2,3,4,5] split
 322         into two pages would be [1,2,3],[4,5]. This function computes the
 323         minimum and maximum indices of a single page.
 324
 325         length: Length of the list that should be split
 326         page: Page number, 1 <= page <= pagecount
 327         pagecount: The number of pages, >= 1
 328         minindex: Receives the minimum index (inclusive).
 329         maxindex: Receives the maximum index (exclusive).
 330
 331         Ensures 0 <= minindex <= maxindex <= length.
 332 */
 333 inline void paging(u32 length, u32 page, u32 pagecount, u32 &minindex, u32 &maxindex)
 334 {
 335         if (length < 1 || pagecount < 1 || page < 1 || page > pagecount) {
 336                 // Special cases or invalid parameters
 337                 minindex = maxindex = 0;
 338         } else if(pagecount <= length) {
 339                 // Less pages than entries in the list:
 340                 // Each page contains at least one entry
 341                 minindex = (length * (page-1) + (pagecount-1)) / pagecount;
 342                 maxindex = (length * page + (pagecount-1)) / pagecount;
 343         } else {
 344                 // More pages than entries in the list:
 345                 // Make sure the empty pages are at the end
 346                 if (page < length) {
 347                         minindex = page-1;
 348                         maxindex = page;
 349                 } else {
 350                         minindex = 0;
 351                         maxindex = 0;
 352                 }
 353         }
 354 }
 355
 356 inline float cycle_shift(float value, float by = 0, float max = 1)
 357 {
 358     if (value + by < 0)   return value + by + max;
 359     if (value + by > max) return value + by - max;
 360     return value + by;
 361 }
 362
 363 inline bool is_power_of_two(u32 n)
 364 {
 365         return n != 0 && (n & (n - 1)) == 0;
 366 }
 367
 368 // Compute next-higher power of 2 efficiently, e.g. for power-of-2 texture sizes.
 369 // Public Domain: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
 370 inline u32 npot2(u32 orig) {
 371         orig--;
 372         orig |= orig >> 1;
 373         orig |= orig >> 2;
 374         orig |= orig >> 4;
 375         orig |= orig >> 8;
 376         orig |= orig >> 16;
 377         return orig + 1;
 378 }
 379
 380 // Gradual steps towards the target value in a wrapped (circular) system
 381 // using the shorter of both ways
 382 template<typename T>
 383 inline void wrappedApproachShortest(T &current, const T target, const T stepsize,
 384         const T maximum)
 385 {
 386         T delta = target - current;
 387         if (delta < 0)
 388                 delta += maximum;
 389
 390         if (delta > stepsize && maximum - delta > stepsize) {
 391                 current += (delta < maximum / 2) ? stepsize : -stepsize;
 392                 if (current >= maximum)
 393                         current -= maximum;
 394         } else {
 395                 current = target;
 396         }
 397 }