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 #ifndef UTIL_NUMERIC_HEADER
  21 #define UTIL_NUMERIC_HEADER
  22
  23 #include "../irrlichttypes.h"
  24 #include "../irr_v2d.h"
  25 #include "../irr_v3d.h"
  26 #include "../irr_aabb3d.h"
  27 #include <list>
  28 #include <map>
  29 #include <vector>
  30 #include <algorithm>
  31
  32
  33 /*
  34  * This class permits to cache getFacePosition call results
  35  * This reduces CPU usage and vector calls
  36  */
  37 class FacePositionCache
  38 {
  39 public:
  40         static std::vector<v3s16> getFacePositions(u16 d);
  41 private:
  42         static void generateFacePosition(u16 d);
  43         static std::map<u16, std::vector<v3s16> > m_cache;
  44 };
  45
  46 class IndentationRaiser
  47 {
  48 public:
  49         IndentationRaiser(u16 *indentation)
  50         {
  51                 m_indentation = indentation;
  52                 (*m_indentation)++;
  53         }
  54         ~IndentationRaiser()
  55         {
  56                 (*m_indentation)--;
  57         }
  58 private:
  59         u16 *m_indentation;
  60 };
  61
  62 inline s16 getContainerPos(s16 p, s16 d)
  63 {
  64         return (p>=0 ? p : p-d+1) / d;
  65 }
  66
  67 inline v2s16 getContainerPos(v2s16 p, s16 d)
  68 {
  69         return v2s16(
  70                 getContainerPos(p.X, d),
  71                 getContainerPos(p.Y, d)
  72         );
  73 }
  74
  75 inline v3s16 getContainerPos(v3s16 p, s16 d)
  76 {
  77         return v3s16(
  78                 getContainerPos(p.X, d),
  79                 getContainerPos(p.Y, d),
  80                 getContainerPos(p.Z, d)
  81         );
  82 }
  83
  84 inline v2s16 getContainerPos(v2s16 p, v2s16 d)
  85 {
  86         return v2s16(
  87                 getContainerPos(p.X, d.X),
  88                 getContainerPos(p.Y, d.Y)
  89         );
  90 }
  91
  92 inline v3s16 getContainerPos(v3s16 p, v3s16 d)
  93 {
  94         return v3s16(
  95                 getContainerPos(p.X, d.X),
  96                 getContainerPos(p.Y, d.Y),
  97                 getContainerPos(p.Z, d.Z)
  98         );
  99 }
 100
 101 inline void getContainerPosWithOffset(s16 p, s16 d, s16 &container, s16 &offset)
 102 {
 103         container = (p >= 0 ? p : p - d + 1) / d;
 104         offset = p & (d - 1);
 105 }
 106
 107 inline void getContainerPosWithOffset(const v2s16 &p, s16 d, v2s16 &container, v2s16 &offset)
 108 {
 109         getContainerPosWithOffset(p.X, d, container.X, offset.X);
 110         getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
 111 }
 112
 113 inline void getContainerPosWithOffset(const v3s16 &p, s16 d, v3s16 &container, v3s16 &offset)
 114 {
 115         getContainerPosWithOffset(p.X, d, container.X, offset.X);
 116         getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
 117         getContainerPosWithOffset(p.Z, d, container.Z, offset.Z);
 118 }
 119
 120
 121 inline bool isInArea(v3s16 p, s16 d)
 122 {
 123         return (
 124                 p.X >= 0 && p.X < d &&
 125                 p.Y >= 0 && p.Y < d &&
 126                 p.Z >= 0 && p.Z < d
 127         );
 128 }
 129
 130 inline bool isInArea(v2s16 p, s16 d)
 131 {
 132         return (
 133                 p.X >= 0 && p.X < d &&
 134                 p.Y >= 0 && p.Y < d
 135         );
 136 }
 137
 138 inline bool isInArea(v3s16 p, v3s16 d)
 139 {
 140         return (
 141                 p.X >= 0 && p.X < d.X &&
 142                 p.Y >= 0 && p.Y < d.Y &&
 143                 p.Z >= 0 && p.Z < d.Z
 144         );
 145 }
 146
 147 #define rangelim(d, min, max) ((d) < (min) ? (min) : ((d)>(max)?(max):(d)))
 148 #define myfloor(x) ((x) > 0.0 ? (int)(x) : (int)(x) - 1)
 149
 150 inline v3s16 arealim(v3s16 p, s16 d)
 151 {
 152         if(p.X < 0)
 153                 p.X = 0;
 154         if(p.Y < 0)
 155                 p.Y = 0;
 156         if(p.Z < 0)
 157                 p.Z = 0;
 158         if(p.X > d-1)
 159                 p.X = d-1;
 160         if(p.Y > d-1)
 161                 p.Y = d-1;
 162         if(p.Z > d-1)
 163                 p.Z = d-1;
 164         return p;
 165 }
 166
 167 #define ARRLEN(x) (sizeof(x) / sizeof((x)[0]))
 168 #define CONTAINS(c, v) (std::find((c).begin(), (c).end(), (v)) != (c).end())
 169
 170 // The naive swap performs better than the xor version
 171 #define SWAP(t, x, y) do { \
 172         t temp = x;            \
 173         x = y;                 \
 174         y = temp;              \
 175 } while (0)
 176
 177 inline void sortBoxVerticies(v3s16 &p1, v3s16 &p2) {
 178         if (p1.X > p2.X)
 179                 SWAP(s16, p1.X, p2.X);
 180         if (p1.Y > p2.Y)
 181                 SWAP(s16, p1.Y, p2.Y);
 182         if (p1.Z > p2.Z)
 183                 SWAP(s16, p1.Z, p2.Z);
 184 }
 185
 186
 187 /** Returns \p f wrapped to the range [-360, 360]
 188  *
 189  *  See test.cpp for example cases.
 190  *
 191  *  \note This is also used in cases where degrees wrapped to the range [0, 360]
 192  *  is innapropriate (e.g. pitch needs negative values)
 193  *
 194  *  \internal functionally equivalent -- although precision may vary slightly --
 195  *  to fmodf((f), 360.0f) however empirical tests indicate that this approach is
 196  *  faster.
 197  */
 198 inline float modulo360f(float f)
 199 {
 200         int sign;
 201         int whole;
 202         float fraction;
 203
 204         if (f < 0) {
 205                 f = -f;
 206                 sign = -1;
 207         } else {
 208                 sign = 1;
 209         }
 210
 211         whole = f;
 212
 213         fraction = f - whole;
 214         whole %= 360;
 215
 216         return sign * (whole + fraction);
 217 }
 218
 219
 220 /** Returns \p f wrapped to the range [0, 360]
 221   */
 222 inline float wrapDegrees_0_360(float f)
 223 {
 224         float value = modulo360f(f);
 225         return value < 0 ? value + 360 : value;
 226 }
 227
 228
 229 /** Returns \p f wrapped to the range [-180, 180]
 230   */
 231 inline float wrapDegrees_180(float f)
 232 {
 233         float value = modulo360f(f + 180);
 234         if (value < 0)
 235                 value += 360;
 236         return value - 180;
 237 }
 238
 239 /*
 240         Pseudo-random (VC++ rand() sucks)
 241 */
 242 #define MYRAND_RANGE 0xffffffff
 243 u32 myrand();
 244 void mysrand(unsigned int seed);
 245 void myrand_bytes(void *out, size_t len);
 246 int myrand_range(int min, int max);
 247
 248 /*
 249         Miscellaneous functions
 250 */
 251
 252 inline u32 get_bits(u32 x, u32 pos, u32 len)
 253 {
 254         u32 mask = (1 << len) - 1;
 255         return (x >> pos) & mask;
 256 }
 257
 258 inline void set_bits(u32 *x, u32 pos, u32 len, u32 val)
 259 {
 260         u32 mask = (1 << len) - 1;
 261         *x &= ~(mask << pos);
 262         *x |= (val & mask) << pos;
 263 }
 264
 265 inline u32 calc_parity(u32 v)
 266 {
 267         v ^= v >> 16;
 268         v ^= v >> 8;
 269         v ^= v >> 4;
 270         v &= 0xf;
 271         return (0x6996 >> v) & 1;
 272 }
 273
 274 u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed);
 275
 276 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
 277                 f32 camera_fov, f32 range, f32 *distance_ptr=NULL);
 278
 279 /*
 280         Some helper stuff
 281 */
 282 #define MYMIN(a,b) ((a)<(b)?(a):(b))
 283 #define MYMAX(a,b) ((a)>(b)?(a):(b))
 284
 285 /*
 286         Returns nearest 32-bit integer for given floating point number.
 287         <cmath> and <math.h> in VC++ don't provide round().
 288 */
 289 inline s32 myround(f32 f)
 290 {
 291         return floor(f + 0.5);
 292 }
 293
 294 /*
 295         Returns integer position of node in given floating point position
 296 */
 297 inline v3s16 floatToInt(v3f p, f32 d)
 298 {
 299         v3s16 p2(
 300                 (p.X + (p.X>0 ? d/2 : -d/2))/d,
 301                 (p.Y + (p.Y>0 ? d/2 : -d/2))/d,
 302                 (p.Z + (p.Z>0 ? d/2 : -d/2))/d);
 303         return p2;
 304 }
 305
 306 /*
 307         Returns floating point position of node in given integer position
 308 */
 309 inline v3f intToFloat(v3s16 p, f32 d)
 310 {
 311         v3f p2(
 312                 (f32)p.X * d,
 313                 (f32)p.Y * d,
 314                 (f32)p.Z * d
 315         );
 316         return p2;
 317 }
 318
 319 // Random helper. Usually d=BS
 320 inline core::aabbox3d<f32> getNodeBox(v3s16 p, float d)
 321 {
 322         return core::aabbox3d<f32>(
 323                 (float)p.X * d - 0.5*d,
 324                 (float)p.Y * d - 0.5*d,
 325                 (float)p.Z * d - 0.5*d,
 326                 (float)p.X * d + 0.5*d,
 327                 (float)p.Y * d + 0.5*d,
 328                 (float)p.Z * d + 0.5*d
 329         );
 330 }
 331
 332 class IntervalLimiter
 333 {
 334 public:
 335         IntervalLimiter():
 336                 m_accumulator(0)
 337         {
 338         }
 339         /*
 340                 dtime: time from last call to this method
 341                 wanted_interval: interval wanted
 342                 return value:
 343                         true: action should be skipped
 344                         false: action should be done
 345         */
 346         bool step(float dtime, float wanted_interval)
 347         {
 348                 m_accumulator += dtime;
 349                 if(m_accumulator < wanted_interval)
 350                         return false;
 351                 m_accumulator -= wanted_interval;
 352                 return true;
 353         }
 354 protected:
 355         float m_accumulator;
 356 };
 357
 358 /*
 359         Splits a list into "pages". For example, the list [1,2,3,4,5] split
 360         into two pages would be [1,2,3],[4,5]. This function computes the
 361         minimum and maximum indices of a single page.
 362
 363         length: Length of the list that should be split
 364         page: Page number, 1 <= page <= pagecount
 365         pagecount: The number of pages, >= 1
 366         minindex: Receives the minimum index (inclusive).
 367         maxindex: Receives the maximum index (exclusive).
 368
 369         Ensures 0 <= minindex <= maxindex <= length.
 370 */
 371 inline void paging(u32 length, u32 page, u32 pagecount, u32 &minindex, u32 &maxindex)
 372 {
 373         if(length < 1 || pagecount < 1 || page < 1 || page > pagecount)
 374         {
 375                 // Special cases or invalid parameters
 376                 minindex = maxindex = 0;
 377         }
 378         else if(pagecount <= length)
 379         {
 380                 // Less pages than entries in the list:
 381                 // Each page contains at least one entry
 382                 minindex = (length * (page-1) + (pagecount-1)) / pagecount;
 383                 maxindex = (length * page + (pagecount-1)) / pagecount;
 384         }
 385         else
 386         {
 387                 // More pages than entries in the list:
 388                 // Make sure the empty pages are at the end
 389                 if(page < length)
 390                 {
 391                         minindex = page-1;
 392                         maxindex = page;
 393                 }
 394                 else
 395                 {
 396                         minindex = 0;
 397                         maxindex = 0;
 398                 }
 399         }
 400 }
 401
 402 inline float cycle_shift(float value, float by = 0, float max = 1)
 403 {
 404     if (value + by < 0) return max + by + value;
 405     if (value + by > max) return value + by - max;
 406     return value + by;
 407 }
 408
 409 inline bool is_power_of_two(u32 n)
 410 {
 411         return n != 0 && (n & (n-1)) == 0;
 412 }
 413
 414 // Compute next-higher power of 2 efficiently, e.g. for power-of-2 texture sizes.
 415 // Public Domain: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
 416 inline u32 npot2(u32 orig) {
 417         orig--;
 418         orig |= orig >> 1;
 419         orig |= orig >> 2;
 420         orig |= orig >> 4;
 421         orig |= orig >> 8;
 422         orig |= orig >> 16;
 423         return orig + 1;
 424 }
 425
 426 #endif