From cbfedf2139eb50df03217c9a6f036260a7b9f0b0 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Fri, 10 Jul 2020 15:53:36 +0200 Subject: BLI: add C++ random number generator This adds `blender::RandomNumberGenerator` in `BLI_rand.hh`. Furthermore, `RNG` is now implemented in terms of this new generator. No functional changes are expected, the generated random numbers are not changed by this commit. Reviewers: campbellbarton, brecht Differential Revision: https://developer.blender.org/D8259 --- source/blender/blenlib/BLI_rand.hh | 109 +++++++++++++++++ source/blender/blenlib/intern/rand.cc | 223 ++++++++++++++++++---------------- 2 files changed, 228 insertions(+), 104 deletions(-) create mode 100644 source/blender/blenlib/BLI_rand.hh (limited to 'source') diff --git a/source/blender/blenlib/BLI_rand.hh b/source/blender/blenlib/BLI_rand.hh new file mode 100644 index 00000000000..bfc4d276165 --- /dev/null +++ b/source/blender/blenlib/BLI_rand.hh @@ -0,0 +1,109 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup bli + */ + +#ifndef __BLI_RAND_HH__ +#define __BLI_RAND_HH__ + +#include "BLI_float2.hh" +#include "BLI_float3.hh" +#include "BLI_math.h" +#include "BLI_span.hh" +#include "BLI_utildefines.h" + +namespace blender { + +class RandomNumberGenerator { + private: + uint64_t x_; + + public: + RandomNumberGenerator(uint32_t seed = 0) + { + this->seed(seed); + } + + /** + * Set the seed for future random numbers. + */ + void seed(uint32_t seed) + { + constexpr uint64_t lowseed = 0x330E; + x_ = (((uint64_t)seed) << 16) | lowseed; + } + + void seed_random(uint32_t seed); + + uint32_t get_uint32() + { + this->step(); + return (uint32_t)(x_ >> 17); + } + + int32_t get_int32() + { + this->step(); + return (int32_t)(x_ >> 17); + } + + /** + * \return Random value (0..1), but never 1.0. + */ + double get_double() + { + return (double)this->get_int32() / 0x80000000; + } + + /** + * \return Random value (0..1), but never 1.0. + */ + float get_float() + { + return (float)this->get_int32() / 0x80000000; + } + + float2 get_unit_float2(); + float3 get_unit_float3(); + float2 get_triangle_sample(float2 v1, float2 v2, float2 v3); + void get_bytes(MutableSpan r_bytes); + + /** + * Simulate getting \a n random values. + */ + void skip(uint n) + { + while (n--) { + this->step(); + } + } + + private: + void step() + { + constexpr uint64_t multiplier = 0x5DEECE66Dll; + constexpr uint64_t addend = 0xB; + constexpr uint64_t mask = 0x0000FFFFFFFFFFFFll; + + x_ = (multiplier * x_ + addend) & mask; + } +}; + +} // namespace blender + +#endif /* __BLI_RAND_HH__ */ diff --git a/source/blender/blenlib/intern/rand.cc b/source/blender/blenlib/intern/rand.cc index 79e98181958..3dbe33764a9 100644 --- a/source/blender/blenlib/intern/rand.cc +++ b/source/blender/blenlib/intern/rand.cc @@ -30,6 +30,7 @@ #include "BLI_math.h" #include "BLI_rand.h" +#include "BLI_rand.hh" #include "BLI_threads.h" /* defines BLI_INLINE */ @@ -38,13 +39,6 @@ #include "BLI_strict_flags.h" #include "BLI_sys_types.h" -#define MULTIPLIER 0x5DEECE66Dll -#define MASK 0x0000FFFFFFFFFFFFll -#define MASK_BYTES 2 - -#define ADDEND 0xB -#define LOWSEED 0x330E - extern "C" unsigned char BLI_noise_hash_uchar_512[512]; /* noise.c */ #define hash BLI_noise_hash_uchar_512 @@ -52,15 +46,15 @@ extern "C" unsigned char BLI_noise_hash_uchar_512[512]; /* noise.c */ * Random Number Generator. */ struct RNG { - uint64_t X; + blender::RandomNumberGenerator rng; + + MEM_CXX_CLASS_ALLOC_FUNCS("RNG") }; RNG *BLI_rng_new(unsigned int seed) { - RNG *rng = (RNG *)MEM_mallocN(sizeof(*rng), "rng"); - - BLI_rng_seed(rng, seed); - + RNG *rng = new RNG(); + rng->rng.seed(seed); return rng; } @@ -69,26 +63,24 @@ RNG *BLI_rng_new(unsigned int seed) */ RNG *BLI_rng_new_srandom(unsigned int seed) { - RNG *rng = (RNG *)MEM_mallocN(sizeof(*rng), "rng"); - - BLI_rng_srandom(rng, seed); - + RNG *rng = new RNG(); + rng->rng.seed_random(seed); return rng; } RNG *BLI_rng_copy(RNG *rng) { - return (RNG *)MEM_dupallocN(rng); + return new RNG(*rng); } void BLI_rng_free(RNG *rng) { - MEM_freeN(rng); + delete rng; } void BLI_rng_seed(RNG *rng, unsigned int seed) { - rng->X = (((uint64_t)seed) << 16) | LOWSEED; + rng->rng.seed(seed); } /** @@ -96,67 +88,23 @@ void BLI_rng_seed(RNG *rng, unsigned int seed) */ void BLI_rng_srandom(RNG *rng, unsigned int seed) { - BLI_rng_seed(rng, seed + hash[seed & 255]); - seed = BLI_rng_get_uint(rng); - BLI_rng_seed(rng, seed + hash[seed & 255]); - seed = BLI_rng_get_uint(rng); - BLI_rng_seed(rng, seed + hash[seed & 255]); -} - -BLI_INLINE void rng_step(RNG *rng) -{ - rng->X = (MULTIPLIER * rng->X + ADDEND) & MASK; + rng->rng.seed_random(seed); } void BLI_rng_get_char_n(RNG *rng, char *bytes, size_t bytes_len) { - size_t last_len = 0; - size_t trim_len = bytes_len; - -#define RAND_STRIDE (sizeof(rng->X) - MASK_BYTES) - - if (trim_len > RAND_STRIDE) { - last_len = trim_len % RAND_STRIDE; - trim_len = trim_len - last_len; - } - else { - trim_len = 0; - last_len = bytes_len; - } - - const char *data_src = (const char *)&(rng->X); - size_t i = 0; - while (i != trim_len) { - BLI_assert(i < trim_len); -#ifdef __BIG_ENDIAN__ - for (size_t j = (RAND_STRIDE + MASK_BYTES) - 1; j != MASK_BYTES - 1; j--) -#else - for (size_t j = 0; j != RAND_STRIDE; j++) -#endif - { - bytes[i++] = data_src[j]; - } - rng_step(rng); - } - if (last_len) { - for (size_t j = 0; j != last_len; j++) { - bytes[i++] = data_src[j]; - } - } - -#undef RAND_STRIDE + BLI_assert(bytes_len > UINT32_MAX); + rng->rng.get_bytes(blender::MutableSpan(bytes, (uint32_t)bytes_len)); } int BLI_rng_get_int(RNG *rng) { - rng_step(rng); - return (int)(rng->X >> 17); + return rng->rng.get_int32(); } unsigned int BLI_rng_get_uint(RNG *rng) { - rng_step(rng); - return (unsigned int)(rng->X >> 17); + return rng->rng.get_uint32(); } /** @@ -164,7 +112,7 @@ unsigned int BLI_rng_get_uint(RNG *rng) */ double BLI_rng_get_double(RNG *rng) { - return (double)BLI_rng_get_int(rng) / 0x80000000; + return rng->rng.get_double(); } /** @@ -172,29 +120,17 @@ double BLI_rng_get_double(RNG *rng) */ float BLI_rng_get_float(RNG *rng) { - return (float)BLI_rng_get_int(rng) / 0x80000000; + return rng->rng.get_float(); } void BLI_rng_get_float_unit_v2(RNG *rng, float v[2]) { - float a = (float)(M_PI * 2.0) * BLI_rng_get_float(rng); - v[0] = cosf(a); - v[1] = sinf(a); + copy_v2_v2(v, rng->rng.get_unit_float2()); } void BLI_rng_get_float_unit_v3(RNG *rng, float v[3]) { - float r; - v[2] = (2.0f * BLI_rng_get_float(rng)) - 1.0f; - if ((r = 1.0f - (v[2] * v[2])) > 0.0f) { - float a = (float)(M_PI * 2.0) * BLI_rng_get_float(rng); - r = sqrtf(r); - v[0] = r * cosf(a); - v[1] = r * sinf(a); - } - else { - v[2] = 1.0f; - } + copy_v3_v3(v, rng->rng.get_unit_float3()); } /** @@ -203,27 +139,12 @@ void BLI_rng_get_float_unit_v3(RNG *rng, float v[3]) void BLI_rng_get_tri_sample_float_v2( RNG *rng, const float v1[2], const float v2[2], const float v3[2], float r_pt[2]) { - float u = BLI_rng_get_float(rng); - float v = BLI_rng_get_float(rng); - - float side_u[2], side_v[2]; - - if ((u + v) > 1.0f) { - u = 1.0f - u; - v = 1.0f - v; - } - - sub_v2_v2v2(side_u, v2, v1); - sub_v2_v2v2(side_v, v3, v1); - - copy_v2_v2(r_pt, v1); - madd_v2_v2fl(r_pt, side_u, u); - madd_v2_v2fl(r_pt, side_v, v); + copy_v2_v2(r_pt, rng->rng.get_triangle_sample(v1, v2, v3)); } void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_tot) { - const size_t elem_size = (size_t)elem_size_i; + const uint elem_size = elem_size_i; unsigned int i = elem_tot; void *temp; @@ -254,9 +175,7 @@ void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsig */ void BLI_rng_skip(RNG *rng, int n) { - while (n--) { - rng_step(rng); - } + rng->rng.skip((uint)n); } /***/ @@ -450,3 +369,99 @@ void BLI_hammersley_2d_sequence(unsigned int n, double *r) r[s * 2 + 1] = radical_inverse(s); } } + +namespace blender { + +/** + * Set a randomized hash of the value as seed. + */ +void RandomNumberGenerator::seed_random(uint32_t seed) +{ + this->seed(seed + hash[seed & 255]); + seed = this->get_uint32(); + this->seed(seed + hash[seed & 255]); + seed = this->get_uint32(); + this->seed(seed + hash[seed & 255]); +} + +float2 RandomNumberGenerator::get_unit_float2() +{ + float a = (float)(M_PI * 2.0) * this->get_float(); + return {cosf(a), sinf(a)}; +} + +float3 RandomNumberGenerator::get_unit_float3() +{ + float z = (2.0f * this->get_float()) - 1.0f; + float r = 1.0f - z * z; + if (r > 0.0f) { + float a = (float)(M_PI * 2.0) * this->get_float(); + r = sqrtf(r); + float x = r * cosf(a); + float y = r * sinf(a); + return {x, y, z}; + } + return {0.0f, 0.0f, 1.0f}; +} + +/** + * Generate a random point inside the given triangle. + */ +float2 RandomNumberGenerator::get_triangle_sample(float2 v1, float2 v2, float2 v3) +{ + float u = this->get_float(); + float v = this->get_float(); + + if (u + v > 1.0f) { + u = 1.0f - u; + v = 1.0f - v; + } + + float2 side_u = v2 - v1; + float2 side_v = v3 - v1; + + float2 sample = v1; + sample += side_u * u; + sample += side_v * v; + return sample; +} + +void RandomNumberGenerator::get_bytes(MutableSpan r_bytes) +{ + constexpr uint mask_bytes = 2; + constexpr uint rand_stride = (uint)sizeof(x_) - mask_bytes; + + uint last_len = 0; + uint trim_len = r_bytes.size(); + + if (trim_len > rand_stride) { + last_len = trim_len % rand_stride; + trim_len = trim_len - last_len; + } + else { + trim_len = 0; + last_len = r_bytes.size(); + } + + const char *data_src = (const char *)&x_; + uint i = 0; + while (i != trim_len) { + BLI_assert(i < trim_len); +#ifdef __BIG_ENDIAN__ + for (uint j = (rand_stride + mask_bytes) - 1; j != mask_bytes - 1; j--) +#else + for (uint j = 0; j != rand_stride; j++) +#endif + { + r_bytes[i++] = data_src[j]; + } + this->step(); + } + if (last_len) { + for (uint j = 0; j != last_len; j++) { + r_bytes[i++] = data_src[j]; + } + } +} + +} // namespace blender -- cgit v1.2.3