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