8 files changed, 305 insertions, 27 deletions

diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index b657506b1..788516ded 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -167,6 +167,7 @@ add_library(common STATIC
     threadsafe_queue.h
     time_zone.cpp
     time_zone.h
+    tiny_mt.h
     tree.h
     uint128.h
     uuid.cpp
diff --git a/src/common/alignment.h b/src/common/alignment.h
index fb81f10d8..32d796ffa 100644
--- a/src/common/alignment.h
+++ b/src/common/alignment.h
@@ -42,6 +42,11 @@ requires std::is_integral_v<T>[[nodiscard]] constexpr bool IsAligned(T value, si
     return (value & mask) == 0;
 }
 
+template <typename T, typename U>
+requires std::is_integral_v<T>[[nodiscard]] constexpr T DivideUp(T x, U y) {
+    return (x + (y - 1)) / y;
+}
+
 template <typename T, size_t Align = 16>
 class AlignmentAllocator {
 public:
diff --git a/src/common/cityhash.h b/src/common/cityhash.h
index 022d0f7cb..d74fc7639 100644
--- a/src/common/cityhash.h
+++ b/src/common/cityhash.h
@@ -61,6 +61,7 @@
 
 #pragma once
 
+#include <cstddef>
 #include "common/common_types.h"
 
 namespace Common {
diff --git a/src/common/common_funcs.h b/src/common/common_funcs.h
index 71b64e32a..4ace2cd33 100644
--- a/src/common/common_funcs.h
+++ b/src/common/common_funcs.h
@@ -52,9 +52,13 @@ __declspec(dllimport) void __stdcall DebugBreak(void);
 // Generic function to get last error message.
 // Call directly after the command or use the error num.
 // This function might change the error code.
-// Defined in Misc.cpp.
+// Defined in misc.cpp.
 [[nodiscard]] std::string GetLastErrorMsg();
 
+// Like GetLastErrorMsg(), but passing an explicit error code.
+// Defined in misc.cpp.
+[[nodiscard]] std::string NativeErrorToString(int e);
+
 #define DECLARE_ENUM_FLAG_OPERATORS(type)                                                          \
     [[nodiscard]] constexpr type operator|(type a, type b) noexcept {                              \
         using T = std::underlying_type_t<type>;                                                    \
diff --git a/src/common/fiber.cpp b/src/common/fiber.cpp
index 3c1eefcb7..39532ff58 100644
--- a/src/common/fiber.cpp
+++ b/src/common/fiber.cpp
@@ -116,16 +116,19 @@ void Fiber::Rewind() {
     boost::context::detail::jump_fcontext(impl->rewind_context, this);
 }
 
-void Fiber::YieldTo(std::shared_ptr<Fiber> from, std::shared_ptr<Fiber> to) {
-    ASSERT_MSG(from != nullptr, "Yielding fiber is null!");
-    ASSERT_MSG(to != nullptr, "Next fiber is null!");
-    to->impl->guard.lock();
-    to->impl->previous_fiber = from;
-    auto transfer = boost::context::detail::jump_fcontext(to->impl->context, to.get());
-    ASSERT(from->impl->previous_fiber != nullptr);
-    from->impl->previous_fiber->impl->context = transfer.fctx;
-    from->impl->previous_fiber->impl->guard.unlock();
-    from->impl->previous_fiber.reset();
+void Fiber::YieldTo(std::weak_ptr<Fiber> weak_from, Fiber& to) {
+    to.impl->guard.lock();
+    to.impl->previous_fiber = weak_from.lock();
+
+    auto transfer = boost::context::detail::jump_fcontext(to.impl->context, &to);
+
+    // "from" might no longer be valid if the thread was killed
+    if (auto from = weak_from.lock()) {
+        ASSERT(from->impl->previous_fiber != nullptr);
+        from->impl->previous_fiber->impl->context = transfer.fctx;
+        from->impl->previous_fiber->impl->guard.unlock();
+        from->impl->previous_fiber.reset();
+    }
 }
 
 std::shared_ptr<Fiber> Fiber::ThreadToFiber() {
diff --git a/src/common/fiber.h b/src/common/fiber.h
index f7f587f8c..f2a8ff29a 100644
--- a/src/common/fiber.h
+++ b/src/common/fiber.h
@@ -41,7 +41,7 @@ public:
 
     /// Yields control from Fiber 'from' to Fiber 'to'
     /// Fiber 'from' must be the currently running fiber.
-    static void YieldTo(std::shared_ptr<Fiber> from, std::shared_ptr<Fiber> to);
+    static void YieldTo(std::weak_ptr<Fiber> weak_from, Fiber& to);
     [[nodiscard]] static std::shared_ptr<Fiber> ThreadToFiber();
 
     void SetRewindPoint(std::function<void(void*)>&& rewind_func, void* rewind_param);
diff --git a/src/common/misc.cpp b/src/common/misc.cpp
index 1d5393597..495385b9e 100644
--- a/src/common/misc.cpp
+++ b/src/common/misc.cpp
@@ -12,27 +12,41 @@
 
 #include "common/common_funcs.h"
 
-// Generic function to get last error message.
-// Call directly after the command or use the error num.
-// This function might change the error code.
-std::string GetLastErrorMsg() {
-    static constexpr std::size_t buff_size = 255;
-    char err_str[buff_size];
-
+std::string NativeErrorToString(int e) {
 #ifdef _WIN32
-    FormatMessageA(FORMAT_MESSAGE_FROM_SYSTEM, nullptr, GetLastError(),
-                   MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT), err_str, buff_size, nullptr);
-    return std::string(err_str, buff_size);
-#elif defined(__GLIBC__) && (_GNU_SOURCE || (_POSIX_C_SOURCE < 200112L && _XOPEN_SOURCE < 600))
+    LPSTR err_str;
+
+    DWORD res = FormatMessageA(FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_ALLOCATE_BUFFER |
+                                   FORMAT_MESSAGE_IGNORE_INSERTS,
+                               nullptr, e, MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
+                               reinterpret_cast<LPSTR>(&err_str), 1, nullptr);
+    if (!res) {
+        return "(FormatMessageA failed to format error)";
+    }
+    std::string ret(err_str);
+    LocalFree(err_str);
+    return ret;
+#else
+    char err_str[255];
+#if defined(__GLIBC__) && (_GNU_SOURCE || (_POSIX_C_SOURCE < 200112L && _XOPEN_SOURCE < 600))
     // Thread safe (GNU-specific)
-    const char* str = strerror_r(errno, err_str, buff_size);
+    const char* str = strerror_r(e, err_str, sizeof(err_str));
     return std::string(str);
 #else
     // Thread safe (XSI-compliant)
-    const int success = strerror_r(errno, err_str, buff_size);
-    if (success != 0) {
-        return {};
+    int second_err = strerror_r(e, err_str, sizeof(err_str));
+    if (second_err != 0) {
+        return "(strerror_r failed to format error)";
     }
     return std::string(err_str);
+#endif // GLIBC etc.
+#endif // _WIN32
+}
+
+std::string GetLastErrorMsg() {
+#ifdef _WIN32
+    return NativeErrorToString(GetLastError());
+#else
+    return NativeErrorToString(errno);
 #endif
 }
diff --git a/src/common/tiny_mt.h b/src/common/tiny_mt.h
new file mode 100644
index 000000000..19ae5b7d6
--- /dev/null
+++ b/src/common/tiny_mt.h
@@ -0,0 +1,250 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <array>
+
+#include "common/alignment.h"
+#include "common/common_types.h"
+
+namespace Common {
+
+// Implementation of TinyMT (mersenne twister RNG).
+// Like Nintendo, we will use the sample parameters.
+class TinyMT {
+public:
+    static constexpr std::size_t NumStateWords = 4;
+
+    struct State {
+        std::array<u32, NumStateWords> data{};
+    };
+
+private:
+    static constexpr u32 ParamMat1 = 0x8F7011EE;
+    static constexpr u32 ParamMat2 = 0xFC78FF1F;
+    static constexpr u32 ParamTmat = 0x3793FDFF;
+
+    static constexpr u32 ParamMult = 0x6C078965;
+    static constexpr u32 ParamPlus = 0x0019660D;
+    static constexpr u32 ParamXor = 0x5D588B65;
+
+    static constexpr u32 TopBitmask = 0x7FFFFFFF;
+
+    static constexpr int MinimumInitIterations = 8;
+    static constexpr int NumDiscardedInitOutputs = 8;
+
+    static constexpr u32 XorByShifted27(u32 value) {
+        return value ^ (value >> 27);
+    }
+
+    static constexpr u32 XorByShifted30(u32 value) {
+        return value ^ (value >> 30);
+    }
+
+private:
+    State state{};
+
+private:
+    // Internal API.
+    void FinalizeInitialization() {
+        const u32 state0 = this->state.data[0] & TopBitmask;
+        const u32 state1 = this->state.data[1];
+        const u32 state2 = this->state.data[2];
+        const u32 state3 = this->state.data[3];
+
+        if (state0 == 0 && state1 == 0 && state2 == 0 && state3 == 0) {
+            this->state.data[0] = 'T';
+            this->state.data[1] = 'I';
+            this->state.data[2] = 'N';
+            this->state.data[3] = 'Y';
+        }
+
+        for (int i = 0; i < NumDiscardedInitOutputs; i++) {
+            this->GenerateRandomU32();
+        }
+    }
+
+    u32 GenerateRandomU24() {
+        return (this->GenerateRandomU32() >> 8);
+    }
+
+    static void GenerateInitialValuePlus(TinyMT::State* state, int index, u32 value) {
+        u32& state0 = state->data[(index + 0) % NumStateWords];
+        u32& state1 = state->data[(index + 1) % NumStateWords];
+        u32& state2 = state->data[(index + 2) % NumStateWords];
+        u32& state3 = state->data[(index + 3) % NumStateWords];
+
+        const u32 x = XorByShifted27(state0 ^ state1 ^ state3) * ParamPlus;
+        const u32 y = x + index + value;
+
+        state0 = y;
+        state1 += x;
+        state2 += y;
+    }
+
+    static void GenerateInitialValueXor(TinyMT::State* state, int index) {
+        u32& state0 = state->data[(index + 0) % NumStateWords];
+        u32& state1 = state->data[(index + 1) % NumStateWords];
+        u32& state2 = state->data[(index + 2) % NumStateWords];
+        u32& state3 = state->data[(index + 3) % NumStateWords];
+
+        const u32 x = XorByShifted27(state0 + state1 + state3) * ParamXor;
+        const u32 y = x - index;
+
+        state0 = y;
+        state1 ^= x;
+        state2 ^= y;
+    }
+
+public:
+    constexpr TinyMT() = default;
+
+    // Public API.
+
+    // Initialization.
+    void Initialize(u32 seed) {
+        this->state.data[0] = seed;
+        this->state.data[1] = ParamMat1;
+        this->state.data[2] = ParamMat2;
+        this->state.data[3] = ParamTmat;
+
+        for (int i = 1; i < MinimumInitIterations; i++) {
+            const u32 mixed = XorByShifted30(this->state.data[(i - 1) % NumStateWords]);
+            this->state.data[i % NumStateWords] ^= mixed * ParamMult + i;
+        }
+
+        this->FinalizeInitialization();
+    }
+
+    void Initialize(const u32* seed, int seed_count) {
+        this->state.data[0] = 0;
+        this->state.data[1] = ParamMat1;
+        this->state.data[2] = ParamMat2;
+        this->state.data[3] = ParamTmat;
+
+        {
+            const int num_init_iterations = std::max(seed_count + 1, MinimumInitIterations) - 1;
+
+            GenerateInitialValuePlus(&this->state, 0, seed_count);
+
+            for (int i = 0; i < num_init_iterations; i++) {
+                GenerateInitialValuePlus(&this->state, (i + 1) % NumStateWords,
+                                         (i < seed_count) ? seed[i] : 0);
+            }
+
+            for (int i = 0; i < static_cast<int>(NumStateWords); i++) {
+                GenerateInitialValueXor(&this->state,
+                                        (i + 1 + num_init_iterations) % NumStateWords);
+            }
+        }
+
+        this->FinalizeInitialization();
+    }
+
+    // State management.
+    void GetState(TinyMT::State& out) const {
+        out.data = this->state.data;
+    }
+
+    void SetState(const TinyMT::State& state_) {
+        this->state.data = state_.data;
+    }
+
+    // Random generation.
+    void GenerateRandomBytes(void* dst, std::size_t size) {
+        const uintptr_t start = reinterpret_cast<uintptr_t>(dst);
+        const uintptr_t end = start + size;
+        const uintptr_t aligned_start = Common::AlignUp(start, 4);
+        const uintptr_t aligned_end = Common::AlignDown(end, 4);
+
+        // Make sure we're aligned.
+        if (start < aligned_start) {
+            const u32 rnd = this->GenerateRandomU32();
+            std::memcpy(dst, &rnd, aligned_start - start);
+        }
+
+        // Write as many aligned u32s as we can.
+        {
+            u32* cur_dst = reinterpret_cast<u32*>(aligned_start);
+            u32* const end_dst = reinterpret_cast<u32*>(aligned_end);
+
+            while (cur_dst < end_dst) {
+                *(cur_dst++) = this->GenerateRandomU32();
+            }
+        }
+
+        // Handle any leftover unaligned data.
+        if (aligned_end < end) {
+            const u32 rnd = this->GenerateRandomU32();
+            std::memcpy(reinterpret_cast<void*>(aligned_end), &rnd, end - aligned_end);
+        }
+    }
+
+    u32 GenerateRandomU32() {
+        // Advance state.
+        const u32 x0 =
+            (this->state.data[0] & TopBitmask) ^ this->state.data[1] ^ this->state.data[2];
+        const u32 y0 = this->state.data[3];
+        const u32 x1 = x0 ^ (x0 << 1);
+        const u32 y1 = y0 ^ (y0 >> 1) ^ x1;
+
+        const u32 state0 = this->state.data[1];
+        u32 state1 = this->state.data[2];
+        u32 state2 = x1 ^ (y1 << 10);
+        const u32 state3 = y1;
+
+        if ((y1 & 1) != 0) {
+            state1 ^= ParamMat1;
+            state2 ^= ParamMat2;
+        }
+
+        this->state.data[0] = state0;
+        this->state.data[1] = state1;
+        this->state.data[2] = state2;
+        this->state.data[3] = state3;
+
+        // Temper.
+        const u32 t1 = state0 + (state2 >> 8);
+        u32 t0 = state3 ^ t1;
+
+        if ((t1 & 1) != 0) {
+            t0 ^= ParamTmat;
+        }
+
+        return t0;
+    }
+
+    u64 GenerateRandomU64() {
+        const u32 lo = this->GenerateRandomU32();
+        const u32 hi = this->GenerateRandomU32();
+        return (u64{hi} << 32) | u64{lo};
+    }
+
+    float GenerateRandomF32() {
+        // Floats have 24 bits of mantissa.
+        constexpr u32 MantissaBits = 24;
+        return static_cast<float>(GenerateRandomU24()) * (1.0f / (1U << MantissaBits));
+    }
+
+    double GenerateRandomF64() {
+        // Doubles have 53 bits of mantissa.
+        // The smart way to generate 53 bits of random would be to use 32 bits
+        // from the first rnd32() call, and then 21 from the second.
+        // Nintendo does not. They use (32 - 5) = 27 bits from the first rnd32()
+        // call, and (32 - 6) bits from the second. We'll do what they do, but
+        // There's not a clear reason why.
+        constexpr u32 MantissaBits = 53;
+        constexpr u32 Shift1st = (64 - MantissaBits) / 2;
+        constexpr u32 Shift2nd = (64 - MantissaBits) - Shift1st;
+
+        const u32 first = (this->GenerateRandomU32() >> Shift1st);
+        const u32 second = (this->GenerateRandomU32() >> Shift2nd);
+
+        return (1.0 * first * (u64{1} << (32 - Shift2nd)) + second) *
+               (1.0 / (u64{1} << MantissaBits));
+    }
+};
+
+} // namespace Common