From 3993093f51544d4eb44efb57c973e29107ea2f7a Mon Sep 17 00:00:00 2001 From: kwolekr Date: Sun, 22 Mar 2015 00:01:46 -0400 Subject: [PATCH] Add support for the PCG32 PRNG algo (and associated script APIs) --- doc/lua_api.txt | 16 +- src/mapgen.cpp | 10 +- src/mg_ore.cpp | 2 +- src/noise.cpp | 101 +++++++++++++ src/noise.h | 71 +++++---- src/script/lua_api/l_noise.cpp | 260 +++++++++++++++++++++------------ src/script/lua_api/l_noise.h | 50 ++++++- src/script/scripting_game.cpp | 1 + src/util/numeric.cpp | 59 ++++---- src/util/numeric.h | 8 +- 10 files changed, 407 insertions(+), 171 deletions(-) diff --git a/doc/lua_api.txt b/doc/lua_api.txt index 81a35976b..fbacb07d9 100644 --- a/doc/lua_api.txt +++ b/doc/lua_api.txt @@ -2515,7 +2515,8 @@ an itemstring, a table or `nil`. Returns taken `ItemStack`. ### `PseudoRandom` -A pseudorandom number generator. +A 16-bit pseudorandom number generator. +Uses a well-known LCG algorithm introduced by K&R. It can be created via `PseudoRandom(seed)`. @@ -2525,6 +2526,19 @@ It can be created via `PseudoRandom(seed)`. * `((max - min) == 32767) or ((max-min) <= 6553))` must be true due to the simple implementation making bad distribution otherwise. +### `PcgRandom` +A 32-bit pseudorandom number generator. +Uses PCG32, an algorithm of the permuted congruential generator family, offering very strong randomness. + +It can be created via `PcgRandom(seed)` or `PcgRandom(seed, sequence)`. + +#### Methods +* `next()`: return next integer random number [`-2147483648`...`2147483647`] +* `next(min, max)`: return next integer random number [`min`...`max`] +* `rand_normal_dist(min, max, num_trials=6)`: return normally distributed random number [`min`...`max`] + * This is only a rough approximation of a normal distribution with mean=(max-min)/2 and variance=1 + * Increasing num_trials improves accuracy of the approximation + ### `PerlinNoise` A perlin noise generator. It can be created via `PerlinNoise(seed, octaves, persistence, scale)` diff --git a/src/mapgen.cpp b/src/mapgen.cpp index fd4fe5bb0..851f018ee 100644 --- a/src/mapgen.cpp +++ b/src/mapgen.cpp @@ -515,14 +515,10 @@ void MapgenParams::load(const Settings &settings) std::string seed_str; const char *seed_name = (&settings == g_settings) ? "fixed_map_seed" : "seed"; - if (settings.getNoEx(seed_name, seed_str) && !seed_str.empty()) { + if (settings.getNoEx(seed_name, seed_str) && !seed_str.empty()) seed = read_seed(seed_str.c_str()); - } else { - seed = ((u64)(myrand() & 0xFFFF) << 0) | - ((u64)(myrand() & 0xFFFF) << 16) | - ((u64)(myrand() & 0xFFFF) << 32) | - ((u64)(myrand() & 0xFFFF) << 48); - } + else + myrand_bytes(&seed, sizeof(seed)); settings.getNoEx("mg_name", mg_name); settings.getS16NoEx("water_level", water_level); diff --git a/src/mg_ore.cpp b/src/mg_ore.cpp index c62f05860..850f25516 100644 --- a/src/mg_ore.cpp +++ b/src/mg_ore.cpp @@ -308,7 +308,7 @@ void OreVein::generate(MMVManip *vm, int mapseed, u32 blockseed, } // randval ranges from -1..1 - float randval = (float)pr.next() / (PSEUDORANDOM_MAX / 2) - 1.f; + float randval = (float)pr.next() / (pr.RANDOM_RANGE / 2) - 1.f; float noiseval = contour(noise->result[index]); float noiseval2 = contour(noise2->result[index]); if (noiseval * noiseval2 + randval * random_factor < nthresh) diff --git a/src/noise.cpp b/src/noise.cpp index 5223450dc..e6a9b7395 100644 --- a/src/noise.cpp +++ b/src/noise.cpp @@ -62,6 +62,107 @@ FlagDesc flagdesc_noiseparams[] = { /////////////////////////////////////////////////////////////////////////////// +PcgRandom::PcgRandom(u64 state, u64 seq) +{ + seed(state, seq); +} + +void PcgRandom::seed(u64 state, u64 seq) +{ + m_state = 0U; + m_inc = (seq << 1u) | 1u; + next(); + m_state += state; + next(); +} + + +u32 PcgRandom::next() +{ + u64 oldstate = m_state; + m_state = oldstate * 6364136223846793005ULL + m_inc; + + u32 xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u; + u32 rot = oldstate >> 59u; + return (xorshifted >> rot) | (xorshifted << ((-rot) & 31)); +} + + +u32 PcgRandom::range(u32 bound) +{ + /* + If the bound is not a multiple of the RNG's range, it may cause bias, + e.g. a RNG has a range from 0 to 3 and we take want a number 0 to 2. + Using rand() % 3, the number 0 would be twice as likely to appear. + With a very large RNG range, the effect becomes less prevalent but + still present. This can be solved by modifying the range of the RNG + to become a multiple of bound by dropping values above the a threshhold. + In our example, threshhold == 4 - 3 = 1 % 3 == 1, so reject 0, thus + making the range 3 with no bias. + + This loop looks dangerous, but will always terminate due to the + RNG's property of uniformity. + */ + u32 threshhold = -bound % bound; + u32 r; + + while ((r = next()) < threshhold); + + return r % bound; +} + + +s32 PcgRandom::range(s32 min, s32 max) +{ + assert(max >= min); + u32 bound = max - min + 1; + return range(bound) + min; +} + + +void PcgRandom::bytes(void *out, size_t len) +{ + u32 r; + u8 *outb = (u8 *)out; + + size_t len_alignment = (uintptr_t)out % sizeof(u32); + if (len_alignment) { + r = next(); + while (len_alignment--) { + *outb = r & 0xFF; + outb++; + r >>= 8; + } + } + + size_t len_dwords = len / sizeof(u32); + while (len_dwords--) { + r = next(); + *(u32 *)outb = next(); + outb += sizeof(u32); + } + + size_t len_remaining = len % sizeof(u32); + if (len_remaining) { + r = next(); + while (len_remaining--) { + *outb = r & 0xFF; + outb++; + r >>= 8; + } + } +} + + +s32 PcgRandom::randNormalDist(s32 min, s32 max, int num_trials) +{ + u32 accum = 0; + for (int i = 0; i != num_trials; i++) + accum += range(min, max); + return ((float)accum / num_trials) + 0.5f; +} + +/////////////////////////////////////////////////////////////////////////////// float noise2d(int x, int y, int seed) { diff --git a/src/noise.h b/src/noise.h index e59e73b23..d2287835e 100644 --- a/src/noise.h +++ b/src/noise.h @@ -30,47 +30,67 @@ #include "irr_v3d.h" #include "util/string.h" -#define PSEUDORANDOM_MAX 32767 - extern FlagDesc flagdesc_noiseparams[]; -class PseudoRandom -{ +// Note: this class is not polymorphic so that its high level of +// optimizability may be preserved in the common use case +class PseudoRandom { public: - PseudoRandom(): m_next(0) - { - } - PseudoRandom(int seed): m_next(seed) + const static u32 RANDOM_RANGE = 32767; + + inline PseudoRandom(int seed=0): + m_next(seed) { } - void seed(int seed) + + inline void seed(int seed) { m_next = seed; } - // Returns 0...PSEUDORANDOM_MAX - int next() + + inline int next() { m_next = m_next * 1103515245 + 12345; - return((unsigned)(m_next/65536) % (PSEUDORANDOM_MAX + 1)); + return (unsigned)(m_next / 65536) % (RANDOM_RANGE + 1); } - int range(int min, int max) + + inline int range(int min, int max) { - if (max-min > (PSEUDORANDOM_MAX + 1) / 10) - { - //dstream<<"WARNING: PseudoRandom::range: max > 32767"< max) - { - assert("Something wrong with random number" == NULL); - //return max; - } - return (next()%(max-min+1))+min; + assert(max >= min); + /* + Here, we ensure the range is not too large relative to RANDOM_MAX, + as otherwise the effects of bias would become noticable. Unlike + PcgRandom, we cannot modify this RNG's range as it would change the + output of this RNG for reverse compatibility. + */ + assert((u32)(max - min) <= (RANDOM_RANGE + 1) / 10); + + return (next() % (max - min + 1)) + min; } + private: int m_next; }; +class PcgRandom { +public: + const static s32 RANDOM_MIN = -0x7fffffff - 1; + const static s32 RANDOM_MAX = 0x7fffffff; + const static u32 RANDOM_RANGE = 0xffffffff; + + PcgRandom(u64 state=0x853c49e6748fea9bULL, u64 seq=0xda3e39cb94b95bdbULL); + void seed(u64 state, u64 seq=0xda3e39cb94b95bdbULL); + u32 next(); + u32 range(u32 bound); + s32 range(s32 min, s32 max); + void bytes(void *out, size_t len); + s32 randNormalDist(s32 min, s32 max, int num_trials=6); + +private: + u64 m_state; + u64 m_inc; +}; + #define NOISE_FLAG_DEFAULTS 0x01 #define NOISE_FLAG_EASED 0x02 #define NOISE_FLAG_ABSVALUE 0x04 @@ -89,7 +109,8 @@ struct NoiseParams { float lacunarity; u32 flags; - NoiseParams() { + NoiseParams() + { offset = 0.0f; scale = 1.0f; spread = v3f(250, 250, 250); diff --git a/src/script/lua_api/l_noise.cpp b/src/script/lua_api/l_noise.cpp index 5a82b6485..bf3dca589 100644 --- a/src/script/lua_api/l_noise.cpp +++ b/src/script/lua_api/l_noise.cpp @@ -23,12 +23,19 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "common/c_content.h" #include "log.h" -// garbage collector -int LuaPerlinNoise::gc_object(lua_State *L) +/////////////////////////////////////// +/* + LuaPerlinNoise +*/ + +LuaPerlinNoise::LuaPerlinNoise(NoiseParams *params) : + np(*params) +{ +} + + +LuaPerlinNoise::~LuaPerlinNoise() { - LuaPerlinNoise *o = *(LuaPerlinNoise **)(lua_touserdata(L, 1)); - delete o; - return 0; } @@ -54,19 +61,6 @@ int LuaPerlinNoise::l_get3d(lua_State *L) } -LuaPerlinNoise::LuaPerlinNoise(NoiseParams *params) : - np(*params) -{ -} - - -LuaPerlinNoise::~LuaPerlinNoise() -{ -} - - -// LuaPerlinNoise(seed, octaves, persistence, scale) -// Creates an LuaPerlinNoise and leaves it on top of stack int LuaPerlinNoise::create_object(lua_State *L) { NO_MAP_LOCK_REQUIRED; @@ -91,14 +85,22 @@ int LuaPerlinNoise::create_object(lua_State *L) } -LuaPerlinNoise* LuaPerlinNoise::checkobject(lua_State *L, int narg) +int LuaPerlinNoise::gc_object(lua_State *L) +{ + LuaPerlinNoise *o = *(LuaPerlinNoise **)(lua_touserdata(L, 1)); + delete o; + return 0; +} + + +LuaPerlinNoise *LuaPerlinNoise::checkobject(lua_State *L, int narg) { NO_MAP_LOCK_REQUIRED; luaL_checktype(L, narg, LUA_TUSERDATA); void *ud = luaL_checkudata(L, narg, className); if (!ud) luaL_typerror(L, narg, className); - return *(LuaPerlinNoise**)ud; // unbox pointer + return *(LuaPerlinNoise **)ud; } @@ -111,7 +113,7 @@ void LuaPerlinNoise::Register(lua_State *L) lua_pushliteral(L, "__metatable"); lua_pushvalue(L, methodtable); - lua_settable(L, metatable); // hide metatable from Lua getmetatable() + lua_settable(L, metatable); lua_pushliteral(L, "__index"); lua_pushvalue(L, methodtable); @@ -121,12 +123,11 @@ void LuaPerlinNoise::Register(lua_State *L) lua_pushcfunction(L, gc_object); lua_settable(L, metatable); - lua_pop(L, 1); // drop metatable + lua_pop(L, 1); - luaL_openlib(L, 0, methods, 0); // fill methodtable - lua_pop(L, 1); // drop methodtable + luaL_openlib(L, 0, methods, 0); + lua_pop(L, 1); - // Can be created from Lua (PerlinNoise(seed, octaves, persistence) lua_register(L, className, create_object); } @@ -138,16 +139,26 @@ const luaL_reg LuaPerlinNoise::methods[] = { {0,0} }; - +/////////////////////////////////////// /* - PerlinNoiseMap - */ + LuaPerlinNoiseMap +*/ -int LuaPerlinNoiseMap::gc_object(lua_State *L) +LuaPerlinNoiseMap::LuaPerlinNoiseMap(NoiseParams *params, int seed, v3s16 size) { - LuaPerlinNoiseMap *o = *(LuaPerlinNoiseMap **)(lua_touserdata(L, 1)); - delete o; - return 0; + m_is3d = size.Z > 1; + np = *params; + try { + noise = new Noise(&np, seed, size.X, size.Y, size.Z); + } catch (InvalidNoiseParamsException &e) { + throw LuaError(e.what()); + } +} + + +LuaPerlinNoiseMap::~LuaPerlinNoiseMap() +{ + delete noise; } @@ -251,26 +262,6 @@ int LuaPerlinNoiseMap::l_get3dMap_flat(lua_State *L) } -LuaPerlinNoiseMap::LuaPerlinNoiseMap(NoiseParams *params, int seed, v3s16 size) -{ - m_is3d = size.Z > 1; - np = *params; - try { - noise = new Noise(&np, seed, size.X, size.Y, size.Z); - } catch (InvalidNoiseParamsException &e) { - throw LuaError(e.what()); - } -} - - -LuaPerlinNoiseMap::~LuaPerlinNoiseMap() -{ - delete noise; -} - - -// LuaPerlinNoiseMap(np, size) -// Creates an LuaPerlinNoiseMap and leaves it on top of stack int LuaPerlinNoiseMap::create_object(lua_State *L) { NoiseParams np; @@ -286,6 +277,14 @@ int LuaPerlinNoiseMap::create_object(lua_State *L) } +int LuaPerlinNoiseMap::gc_object(lua_State *L) +{ + LuaPerlinNoiseMap *o = *(LuaPerlinNoiseMap **)(lua_touserdata(L, 1)); + delete o; + return 0; +} + + LuaPerlinNoiseMap *LuaPerlinNoiseMap::checkobject(lua_State *L, int narg) { luaL_checktype(L, narg, LUA_TUSERDATA); @@ -294,7 +293,7 @@ LuaPerlinNoiseMap *LuaPerlinNoiseMap::checkobject(lua_State *L, int narg) if (!ud) luaL_typerror(L, narg, className); - return *(LuaPerlinNoiseMap **)ud; // unbox pointer + return *(LuaPerlinNoiseMap **)ud; } @@ -307,7 +306,7 @@ void LuaPerlinNoiseMap::Register(lua_State *L) lua_pushliteral(L, "__metatable"); lua_pushvalue(L, methodtable); - lua_settable(L, metatable); // hide metatable from Lua getmetatable() + lua_settable(L, metatable); lua_pushliteral(L, "__index"); lua_pushvalue(L, methodtable); @@ -317,12 +316,11 @@ void LuaPerlinNoiseMap::Register(lua_State *L) lua_pushcfunction(L, gc_object); lua_settable(L, metatable); - lua_pop(L, 1); // drop metatable + lua_pop(L, 1); - luaL_openlib(L, 0, methods, 0); // fill methodtable - lua_pop(L, 1); // drop methodtable + luaL_openlib(L, 0, methods, 0); + lua_pop(L, 1); - // Can be created from Lua (PerlinNoiseMap(np, size) lua_register(L, className, create_object); } @@ -336,32 +334,23 @@ const luaL_reg LuaPerlinNoiseMap::methods[] = { {0,0} }; +/////////////////////////////////////// /* LuaPseudoRandom */ -// garbage collector -int LuaPseudoRandom::gc_object(lua_State *L) -{ - LuaPseudoRandom *o = *(LuaPseudoRandom **)(lua_touserdata(L, 1)); - delete o; - return 0; -} - - -// next(self, min=0, max=32767) -> get next value int LuaPseudoRandom::l_next(lua_State *L) { NO_MAP_LOCK_REQUIRED; LuaPseudoRandom *o = checkobject(L, 1); int min = 0; int max = 32767; - lua_settop(L, 3); // Fill 2 and 3 with nil if they don't exist - if(!lua_isnil(L, 2)) + lua_settop(L, 3); + if (lua_isnumber(L, 2)) min = luaL_checkinteger(L, 2); - if(!lua_isnil(L, 3)) + if (lua_isnumber(L, 3)) max = luaL_checkinteger(L, 3); - if(max < min){ + if (max < min) { errorstream<<"PseudoRandom.next(): max="<m_rnd.RANDOM_MIN; + u32 max = lua_isnumber(L, 3) ? lua_tointeger(L, 3) : o->m_rnd.RANDOM_MAX; + + lua_pushinteger(L, o->m_rnd.range(min, max)); + return 1; } -PseudoRandom& LuaPseudoRandom::getItem() + +int LuaPcgRandom::l_rand_normal_dist(lua_State *L) { - return m_pseudo; + NO_MAP_LOCK_REQUIRED; + + LuaPcgRandom *o = checkobject(L, 1); + u32 min = lua_isnumber(L, 2) ? lua_tointeger(L, 2) : o->m_rnd.RANDOM_MIN; + u32 max = lua_isnumber(L, 3) ? lua_tointeger(L, 3) : o->m_rnd.RANDOM_MAX; + int num_trials = lua_isnumber(L, 4) ? lua_tointeger(L, 4) : 6; + + lua_pushinteger(L, o->m_rnd.randNormalDist(min, max, num_trials)); + return 1; } -// LuaPseudoRandom(seed) -// Creates an LuaPseudoRandom and leaves it on top of stack -int LuaPseudoRandom::create_object(lua_State *L) +int LuaPcgRandom::create_object(lua_State *L) { - int seed = luaL_checknumber(L, 1); - LuaPseudoRandom *o = new LuaPseudoRandom(seed); + lua_Integer seed = luaL_checknumber(L, 1); + LuaPcgRandom *o = lua_isnumber(L, 2) ? + new LuaPcgRandom(seed, lua_tointeger(L, 2)) : + new LuaPcgRandom(seed); *(void **)(lua_newuserdata(L, sizeof(void *))) = o; luaL_getmetatable(L, className); lua_setmetatable(L, -2); @@ -413,17 +475,25 @@ int LuaPseudoRandom::create_object(lua_State *L) } -LuaPseudoRandom* LuaPseudoRandom::checkobject(lua_State *L, int narg) +int LuaPcgRandom::gc_object(lua_State *L) +{ + LuaPcgRandom *o = *(LuaPcgRandom **)(lua_touserdata(L, 1)); + delete o; + return 0; +} + + +LuaPcgRandom *LuaPcgRandom::checkobject(lua_State *L, int narg) { luaL_checktype(L, narg, LUA_TUSERDATA); void *ud = luaL_checkudata(L, narg, className); if (!ud) luaL_typerror(L, narg, className); - return *(LuaPseudoRandom**)ud; // unbox pointer + return *(LuaPcgRandom **)ud; } -void LuaPseudoRandom::Register(lua_State *L) +void LuaPcgRandom::Register(lua_State *L) { lua_newtable(L); int methodtable = lua_gettop(L); @@ -432,7 +502,7 @@ void LuaPseudoRandom::Register(lua_State *L) lua_pushliteral(L, "__metatable"); lua_pushvalue(L, methodtable); - lua_settable(L, metatable); // hide metatable from Lua getmetatable() + lua_settable(L, metatable); lua_pushliteral(L, "__index"); lua_pushvalue(L, methodtable); @@ -442,18 +512,18 @@ void LuaPseudoRandom::Register(lua_State *L) lua_pushcfunction(L, gc_object); lua_settable(L, metatable); - lua_pop(L, 1); // drop metatable + lua_pop(L, 1); - luaL_openlib(L, 0, methods, 0); // fill methodtable - lua_pop(L, 1); // drop methodtable + luaL_openlib(L, 0, methods, 0); + lua_pop(L, 1); - // Can be created from Lua (LuaPseudoRandom(seed)) lua_register(L, className, create_object); } -const char LuaPseudoRandom::className[] = "PseudoRandom"; -const luaL_reg LuaPseudoRandom::methods[] = { - luamethod(LuaPseudoRandom, next), +const char LuaPcgRandom::className[] = "PcgRandom"; +const luaL_reg LuaPcgRandom::methods[] = { + luamethod(LuaPcgRandom, next), + luamethod(LuaPcgRandom, rand_normal_dist), {0,0} }; diff --git a/src/script/lua_api/l_noise.h b/src/script/lua_api/l_noise.h index 3e22ac7a0..56d2d59f8 100644 --- a/src/script/lua_api/l_noise.h +++ b/src/script/lua_api/l_noise.h @@ -64,6 +64,9 @@ class LuaPerlinNoiseMap : public ModApiBase { static const char className[]; static const luaL_reg methods[]; + // Exported functions + + // garbage collector static int gc_object(lua_State *L); static int l_get2dMap(lua_State *L); @@ -104,18 +107,51 @@ private: static int l_next(lua_State *L); public: - LuaPseudoRandom(int seed); - - ~LuaPseudoRandom(); - - const PseudoRandom& getItem() const; - PseudoRandom& getItem(); + LuaPseudoRandom(int seed) : + m_pseudo(seed) {} // LuaPseudoRandom(seed) // Creates an LuaPseudoRandom and leaves it on top of stack static int create_object(lua_State *L); - static LuaPseudoRandom* checkobject(lua_State *L, int narg); + static LuaPseudoRandom *checkobject(lua_State *L, int narg); + + static void Register(lua_State *L); +}; + +/* + LuaPcgRandom +*/ +class LuaPcgRandom : public ModApiBase { +private: + PcgRandom m_rnd; + + static const char className[]; + static const luaL_reg methods[]; + + // Exported functions + + // garbage collector + static int gc_object(lua_State *L); + + // next(self, min=-2147483648, max=2147483647) -> get next value + static int l_next(lua_State *L); + + // rand_normal_dist(self, min=-2147483648, max=2147483647, num_trials=6) -> + // get next normally distributed random value + static int l_rand_normal_dist(lua_State *L); + +public: + LuaPcgRandom(u64 seed) : + m_rnd(seed) {} + LuaPcgRandom(u64 seed, u64 seq) : + m_rnd(seed, seq) {} + + // LuaPcgRandom(seed) + // Creates an LuaPcgRandom and leaves it on top of stack + static int create_object(lua_State *L); + + static LuaPcgRandom *checkobject(lua_State *L, int narg); static void Register(lua_State *L); }; diff --git a/src/script/scripting_game.cpp b/src/script/scripting_game.cpp index e716bc979..5bcd2a33d 100644 --- a/src/script/scripting_game.cpp +++ b/src/script/scripting_game.cpp @@ -92,6 +92,7 @@ void GameScripting::InitializeModApi(lua_State *L, int top) LuaPerlinNoise::Register(L); LuaPerlinNoiseMap::Register(L); LuaPseudoRandom::Register(L); + LuaPcgRandom::Register(L); LuaVoxelManip::Register(L); NodeMetaRef::Register(L); NodeTimerRef::Register(L); diff --git a/src/util/numeric.cpp b/src/util/numeric.cpp index 19f927134..a1f1fd0ab 100644 --- a/src/util/numeric.cpp +++ b/src/util/numeric.cpp @@ -22,6 +22,7 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "log.h" #include "../constants.h" // BS, MAP_BLOCKSIZE +#include "../noise.h" // PseudoRandom, PcgRandom #include #include @@ -115,36 +116,32 @@ void FacePositionCache::generateFacePosition(u16 d) myrand */ -static unsigned long next = 1; +PcgRandom g_pcgrand; -/* RAND_MAX assumed to be 32767 */ -int myrand(void) +u32 myrand() { - next = next * 1103515245 + 12345; - return((unsigned)(next/65536) % 32768); + return g_pcgrand.next(); } -void mysrand(unsigned seed) +void mysrand(unsigned int seed) { - next = seed; + g_pcgrand.seed(seed); +} + +void myrand_bytes(void *out, size_t len) +{ + g_pcgrand.bytes(out, len); } int myrand_range(int min, int max) { - if(max-min > MYRAND_MAX) - { - errorstream<<"WARNING: myrand_range: max-min > MYRAND_MAX"< max) - { - errorstream<<"WARNING: myrand_range: min > max"<> r; - k *= m; - + k *= m; + k ^= k >> r; + k *= m; + h ^= k; - h *= m; + h *= m; } const unsigned char *data2 = (const unsigned char *)data; @@ -178,13 +175,13 @@ u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed) case 1: h ^= (u64)data2[0]; h *= m; } - + h ^= h >> r; h *= m; h ^= h >> r; - + return h; -} +} /* @@ -197,7 +194,7 @@ bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir, f32 camera_fov, f32 range, f32 *distance_ptr) { v3s16 blockpos_nodes = blockpos_b * MAP_BLOCKSIZE; - + // Block center position v3f blockpos( ((float)blockpos_nodes.X + MAP_BLOCKSIZE/2) * BS, @@ -213,7 +210,7 @@ bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir, if(distance_ptr) *distance_ptr = d; - + // If block is far away, it's not in sight if(d > range) return false; @@ -221,7 +218,7 @@ bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir, // Maximum radius of a block. The magic number is // sqrt(3.0) / 2.0 in literal form. f32 block_max_radius = 0.866025403784 * MAP_BLOCKSIZE * BS; - + // If block is (nearly) touching the camera, don't // bother validating further (that is, render it anyway) if(d < block_max_radius) @@ -242,7 +239,7 @@ bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir, // Cosine of the angle between the camera direction // and the block direction (camera_dir is an unit vector) f32 cosangle = dforward / blockpos_adj.getLength(); - + // If block is not in the field of view, skip it if(cosangle < cos(camera_fov / 2)) return false; diff --git a/src/util/numeric.h b/src/util/numeric.h index 42d9a87a9..ccc9fbee4 100644 --- a/src/util/numeric.h +++ b/src/util/numeric.h @@ -239,10 +239,10 @@ inline float wrapDegrees_180(float f) /* Pseudo-random (VC++ rand() sucks) */ -int myrand(void); -void mysrand(unsigned seed); -#define MYRAND_MAX 32767 - +#define MYRAND_RANGE 0xffffffff +u32 myrand(); +void mysrand(unsigned int seed); +void myrand_bytes(void *out, size_t len); int myrand_range(int min, int max); /* -- 2.25.1