diff options
author | Keith Rothman <537074+litghost@users.noreply.github.com> | 2021-03-12 13:09:44 -0800 |
---|---|---|
committer | Keith Rothman <537074+litghost@users.noreply.github.com> | 2021-03-15 09:05:23 -0700 |
commit | fe4608386eb163c70a75ed84beb07516af378b36 (patch) | |
tree | 05f1371ad44da5a69617f43cf68005cf271be5e1 /common/deterministic_rng.h | |
parent | 035b797ec230aa3d686d9013e0e15d79cd2982c3 (diff) | |
download | nextpnr-fe4608386eb163c70a75ed84beb07516af378b36.tar.gz nextpnr-fe4608386eb163c70a75ed84beb07516af378b36.tar.bz2 nextpnr-fe4608386eb163c70a75ed84beb07516af378b36.zip |
Split nextpnr.h to allow for linear inclusion.
"nextpnr.h" is no longer the god header. Important improvements:
- Functions in log.h can be used without including
BaseCtx/Arch/Context. This means that log_X functions can be called
without included "nextpnr.h"
- NPNR_ASSERT can be used without including "nextpnr.h" by including
"nextpnr_assertions.h". This allows NPNR_ASSERT to be used safely in
any header file.
- Types defined in "archdefs.h" are now available without including
BaseCtx/Arch/Context. This means that utility classes that will be
used inside of BaseCtx/Arch/Context can be defined safely in a
self-contained header.
Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>
Diffstat (limited to 'common/deterministic_rng.h')
-rw-r--r-- | common/deterministic_rng.h | 103 |
1 files changed, 103 insertions, 0 deletions
diff --git a/common/deterministic_rng.h b/common/deterministic_rng.h new file mode 100644 index 00000000..8dc22601 --- /dev/null +++ b/common/deterministic_rng.h @@ -0,0 +1,103 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf <clifford@symbioticeda.com> + * Copyright (C) 2018 Serge Bazanski <q3k@symbioticeda.com> + * + * 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 |