Introduce a Shuffle for FastRandomContext and use it in wallet and coinselection

1 files changed, 23 insertions, 0 deletions

diff --git a/src/random.h b/src/random.h
index 3d5421eb3e..e7e5eb496a 100644
--- a/src/random.h
+++ b/src/random.h
@@ -130,6 +130,29 @@ public:
     inline uint64_t operator()() { return rand64(); }
 };
 
+/** More efficient than using std::shuffle on a FastRandomContext.
+ *
+ * This is more efficient as std::shuffle will consume entropy in groups of
+ * 64 bits at the time and throw away most.
+ *
+ * This also works around a bug in libstdc++ std::shuffle that may cause
+ * type::operator=(type&&) to be invoked on itself, which the library's
+ * debug mode detects and panics on. This is a known issue, see
+ * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle
+ */
+template<typename I, typename R>
+void Shuffle(I first, I last, R&& rng)
+{
+    while (first != last) {
+        size_t j = rng.randrange(last - first);
+        if (j) {
+            using std::swap;
+            swap(*first, *(first + j));
+        }
+        ++first;
+    }
+}
+
 /* Number of random bytes returned by GetOSRand.
  * When changing this constant make sure to change all call sites, and make
  * sure that the underlying OS APIs for all platforms support the number.