initial remove-in-parallel

doesn't actually do parallel remove yet

2 files changed, 128 insertions, 0 deletions

diff --git a/toolsrc/include/vcpkg/base/rng.h b/toolsrc/include/vcpkg/base/rng.h
new file mode 100644
index 000000000..1bcab05b3
--- /dev/null
+++ b/toolsrc/include/vcpkg/base/rng.h
@@ -0,0 +1,96 @@
+#pragma once
+
+#include <cstdint>
+#include <limits>
+#include <random>
+
+namespace vcpkg {
+
+    /*
+        NOTE(ubsan): taken from the xoshiro paper
+        initialized from random_device by default
+        actual code is copied from wikipedia, since I wrote that code
+    */
+    struct splitmix64_engine {
+        splitmix64_engine() noexcept;
+
+        constexpr splitmix64_engine(std::uint64_t seed) noexcept
+            : state(seed) {}
+
+        constexpr std::uint64_t operator()() noexcept {
+            state += 0x9E3779B97F4A7C15;
+
+            std::uint64_t result = state;
+            result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
+            result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
+
+            return result ^ (result >> 31);
+        }
+
+        constexpr std::uint64_t max() const noexcept {
+            return std::numeric_limits<std::uint64_t>::max();
+        }
+
+        constexpr std::uint64_t min() const noexcept {
+            return std::numeric_limits<std::uint64_t>::min();
+        }
+
+    private:
+        std::uint64_t state;
+    };
+
+    // Sebastian Vigna's xorshift-based xoshiro xoshiro256** engine
+    // fast and really good
+    // uses the splitmix64_engine to initialize state
+    struct xoshiro256ss_engine {
+        // splitmix64_engine will be initialized with random_device
+        xoshiro256ss_engine() noexcept {
+            splitmix64_engine sm64{};
+
+            for (std::uint64_t& s : this->state) {
+                s = sm64();
+            }
+        }
+
+        constexpr xoshiro256ss_engine(std::uint64_t seed) noexcept : state() {
+            splitmix64_engine sm64{seed};
+
+            for (std::uint64_t& s : this->state) {
+                s = sm64();
+            }
+        }
+
+        constexpr std::uint64_t operator()() noexcept {
+            std::uint64_t const result = rol(state[1] * 5, 7) * 9;
+
+            std::uint64_t const t = state[1] << 17;
+
+            // state[i] = state[i] ^ state[i + 4 mod 4]
+            state[2] ^= state[0];
+            state[3] ^= state[1];
+            state[1] ^= state[2];
+            state[0] ^= state[3];
+
+            state[2] ^= t;
+            state[3] ^= rol(state[3], 45);
+
+            return result;
+        }
+
+        constexpr std::uint64_t max() const noexcept {
+            return std::numeric_limits<std::uint64_t>::max();
+        }
+
+        constexpr std::uint64_t min() const noexcept {
+            return std::numeric_limits<std::uint64_t>::min();
+        }
+    private:
+        // rotate left
+        constexpr std::uint64_t rol(std::uint64_t x, int k) {
+            return (x << k) | (x >> (64 - k));
+        }
+
+        std::uint64_t state[4];
+    };
+
+}
diff --git a/toolsrc/include/vcpkg/base/strings.h b/toolsrc/include/vcpkg/base/strings.h
index d553d1d41..423ea2096 100644
--- a/toolsrc/include/vcpkg/base/strings.h
+++ b/toolsrc/include/vcpkg/base/strings.h
@@ -184,4 +184,36 @@ namespace vcpkg::Strings
     const char* search(StringView haystack, StringView needle);
 
     bool contains(StringView haystack, StringView needle);
+
+    // base 64 encoding with URL and filesafe alphabet (base64url)
+    // based on IETF RFC 4648
+    // ignores padding, since one implicitly knows the length from the size of x
+    template <class Integral>
+    std::string b64url_encode(Integral x) {
+        static_assert(std::is_integral_v<Integral>);
+        auto value = static_cast<std::make_unsigned_t<Integral>>(x);
+
+        // 64 values, plus the implicit \0
+        constexpr static char map[0x41] =
+            /*     0123456789ABCDEF */
+            /*0*/ "ABCDEFGHIJKLMNOP"
+            /*1*/ "QRSTUVWXYZabcdef"
+            /*2*/ "ghijklmnopqrstuv"
+            /*3*/ "wxyz0123456789-_"
+        ;
+
+        constexpr static std::make_unsigned_t<Integral> mask = 0x3F;
+        constexpr static int shift = 5;
+
+        std::string result;
+        // reserve ceiling(number of bits / 3)
+        result.reserve((sizeof(value) * 8 + 2) / 3);
+
+        while (value != 0) {
+            char mapped_value = map[value & mask];
+            result.push_back(mapped_value);
+        }
+
+        return result;
+    }
 }