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