diff options
Diffstat (limited to 'common/kernel/deterministic_rng.h')
-rw-r--r-- | common/kernel/deterministic_rng.h | 103 |
1 files changed, 103 insertions, 0 deletions
diff --git a/common/kernel/deterministic_rng.h b/common/kernel/deterministic_rng.h new file mode 100644 index 00000000..3aab5a49 --- /dev/null +++ b/common/kernel/deterministic_rng.h @@ -0,0 +1,103 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Claire Xenia Wolf <claire@yosyshq.com> + * Copyright (C) 2018 Serge Bazanski <q3k@q3k.org> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef DETERMINISTIC_RNG_H +#define DETERMINISTIC_RNG_H + +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <vector> + +#include "nextpnr_namespaces.h" + +NEXTPNR_NAMESPACE_BEGIN + +struct DeterministicRNG +{ + uint64_t rngstate; + + DeterministicRNG() : rngstate(0x3141592653589793) {} + + uint64_t rng64() + { + // xorshift64star + // https://arxiv.org/abs/1402.6246 + + uint64_t retval = rngstate * 0x2545F4914F6CDD1D; + + rngstate ^= rngstate >> 12; + rngstate ^= rngstate << 25; + rngstate ^= rngstate >> 27; + + return retval; + } + + int rng() { return rng64() & 0x3fffffff; } + + int rng(int n) + { + assert(n > 0); + + // round up to power of 2 + int m = n - 1; + m |= (m >> 1); + m |= (m >> 2); + m |= (m >> 4); + m |= (m >> 8); + m |= (m >> 16); + m += 1; + + while (1) { + int x = rng64() & (m - 1); + if (x < n) + return x; + } + } + + void rngseed(uint64_t seed) + { + rngstate = seed ? seed : 0x3141592653589793; + for (int i = 0; i < 5; i++) + rng64(); + } + + template <typename Iter> void shuffle(const Iter &begin, const Iter &end) + { + std::size_t size = end - begin; + for (std::size_t i = 0; i != size; i++) { + std::size_t j = i + rng(size - i); + if (j > i) + std::swap(*(begin + i), *(begin + j)); + } + } + + template <typename T> void shuffle(std::vector<T> &a) { shuffle(a.begin(), a.end()); } + + template <typename T> void sorted_shuffle(std::vector<T> &a) + { + std::sort(a.begin(), a.end()); + shuffle(a); + } +}; + +NEXTPNR_NAMESPACE_END + +#endif |