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