Merge pull request #7852 from Morph1984/new-uuid

common: Revise and fix the UUID implementation

1 files changed, 167 insertions, 41 deletions

diff --git a/src/common/uuid.cpp b/src/common/uuid.cpp
index d7435a6e9..2b6a530e3 100644
--- a/src/common/uuid.cpp
+++ b/src/common/uuid.cpp
@@ -1,23 +1,25 @@
-// Copyright 2018 yuzu Emulator Project
+// Copyright 2022 yuzu Emulator Project
 // Licensed under GPLv2 or any later version
 // Refer to the license.txt file included.
 
+#include <bit>
+#include <optional>
 #include <random>
 
 #include <fmt/format.h>
 
 #include "common/assert.h"
+#include "common/tiny_mt.h"
 #include "common/uuid.h"
 
 namespace Common {
 
 namespace {
 
-bool IsHexDigit(char c) {
-    return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');
-}
+constexpr size_t RawStringSize = sizeof(UUID) * 2;
+constexpr size_t FormattedStringSize = RawStringSize + 4;
 
-u8 HexCharToByte(char c) {
+std::optional<u8> HexCharToByte(char c) {
     if (c >= '0' && c <= '9') {
         return static_cast<u8>(c - '0');
     }
@@ -28,60 +30,184 @@ u8 HexCharToByte(char c) {
         return static_cast<u8>(c - 'A' + 10);
     }
     ASSERT_MSG(false, "{} is not a hexadecimal digit!", c);
-    return u8{0};
+    return std::nullopt;
 }
 
-} // Anonymous namespace
+std::array<u8, 0x10> ConstructFromRawString(std::string_view raw_string) {
+    std::array<u8, 0x10> uuid;
+
+    for (size_t i = 0; i < RawStringSize; i += 2) {
+        const auto upper = HexCharToByte(raw_string[i]);
+        const auto lower = HexCharToByte(raw_string[i + 1]);
+        if (!upper || !lower) {
+            return {};
+        }
+        uuid[i / 2] = static_cast<u8>((*upper << 4) | *lower);
+    }
+
+    return uuid;
+}
 
-u128 HexStringToU128(std::string_view hex_string) {
-    const size_t length = hex_string.length();
+std::array<u8, 0x10> ConstructFromFormattedString(std::string_view formatted_string) {
+    std::array<u8, 0x10> uuid;
 
-    // Detect "0x" prefix.
-    const bool has_0x_prefix = length > 2 && hex_string[0] == '0' && hex_string[1] == 'x';
-    const size_t offset = has_0x_prefix ? 2 : 0;
+    size_t i = 0;
 
-    // Check length.
-    if (length > 32 + offset) {
-        ASSERT_MSG(false, "hex_string has more than 32 hexadecimal characters!");
-        return INVALID_UUID;
+    // Process the first 8 characters.
+    const auto* str = formatted_string.data();
+
+    for (; i < 4; ++i) {
+        const auto upper = HexCharToByte(*(str++));
+        const auto lower = HexCharToByte(*(str++));
+        if (!upper || !lower) {
+            return {};
+        }
+        uuid[i] = static_cast<u8>((*upper << 4) | *lower);
+    }
+
+    // Process the next 4 characters.
+    ++str;
+
+    for (; i < 6; ++i) {
+        const auto upper = HexCharToByte(*(str++));
+        const auto lower = HexCharToByte(*(str++));
+        if (!upper || !lower) {
+            return {};
+        }
+        uuid[i] = static_cast<u8>((*upper << 4) | *lower);
     }
 
-    u64 lo = 0;
-    u64 hi = 0;
-    for (size_t i = 0; i < length - offset; ++i) {
-        const char c = hex_string[length - 1 - i];
-        if (!IsHexDigit(c)) {
-            ASSERT_MSG(false, "{} is not a hexadecimal digit!", c);
-            return INVALID_UUID;
+    // Process the next 4 characters.
+    ++str;
+
+    for (; i < 8; ++i) {
+        const auto upper = HexCharToByte(*(str++));
+        const auto lower = HexCharToByte(*(str++));
+        if (!upper || !lower) {
+            return {};
         }
-        if (i < 16) {
-            lo |= u64{HexCharToByte(c)} << (i * 4);
+        uuid[i] = static_cast<u8>((*upper << 4) | *lower);
+    }
+
+    // Process the next 4 characters.
+    ++str;
+
+    for (; i < 10; ++i) {
+        const auto upper = HexCharToByte(*(str++));
+        const auto lower = HexCharToByte(*(str++));
+        if (!upper || !lower) {
+            return {};
         }
-        if (i >= 16) {
-            hi |= u64{HexCharToByte(c)} << ((i - 16) * 4);
+        uuid[i] = static_cast<u8>((*upper << 4) | *lower);
+    }
+
+    // Process the last 12 characters.
+    ++str;
+
+    for (; i < 16; ++i) {
+        const auto upper = HexCharToByte(*(str++));
+        const auto lower = HexCharToByte(*(str++));
+        if (!upper || !lower) {
+            return {};
         }
+        uuid[i] = static_cast<u8>((*upper << 4) | *lower);
+    }
+
+    return uuid;
+}
+
+std::array<u8, 0x10> ConstructUUID(std::string_view uuid_string) {
+    const auto length = uuid_string.length();
+
+    if (length == 0) {
+        return {};
+    }
+
+    // Check if the input string contains 32 hexadecimal characters.
+    if (length == RawStringSize) {
+        return ConstructFromRawString(uuid_string);
+    }
+
+    // Check if the input string has the length of a RFC 4122 formatted UUID string.
+    if (length == FormattedStringSize) {
+        return ConstructFromFormattedString(uuid_string);
     }
-    return u128{lo, hi};
+
+    ASSERT_MSG(false, "UUID string has an invalid length of {} characters!", length);
+
+    return {};
+}
+
+} // Anonymous namespace
+
+UUID::UUID(std::string_view uuid_string) : uuid{ConstructUUID(uuid_string)} {}
+
+std::string UUID::RawString() const {
+    return fmt::format("{:02x}{:02x}{:02x}{:02x}{:02x}{:02x}{:02x}{:02x}"
+                       "{:02x}{:02x}{:02x}{:02x}{:02x}{:02x}{:02x}{:02x}",
+                       uuid[0], uuid[1], uuid[2], uuid[3], uuid[4], uuid[5], uuid[6], uuid[7],
+                       uuid[8], uuid[9], uuid[10], uuid[11], uuid[12], uuid[13], uuid[14],
+                       uuid[15]);
+}
+
+std::string UUID::FormattedString() const {
+    return fmt::format("{:02x}{:02x}{:02x}{:02x}"
+                       "-{:02x}{:02x}-{:02x}{:02x}-{:02x}{:02x}-"
+                       "{:02x}{:02x}{:02x}{:02x}{:02x}{:02x}",
+                       uuid[0], uuid[1], uuid[2], uuid[3], uuid[4], uuid[5], uuid[6], uuid[7],
+                       uuid[8], uuid[9], uuid[10], uuid[11], uuid[12], uuid[13], uuid[14],
+                       uuid[15]);
+}
+
+size_t UUID::Hash() const noexcept {
+    u64 upper_hash;
+    u64 lower_hash;
+
+    std::memcpy(&upper_hash, uuid.data(), sizeof(u64));
+    std::memcpy(&lower_hash, uuid.data() + sizeof(u64), sizeof(u64));
+
+    return upper_hash ^ std::rotl(lower_hash, 1);
 }
 
-UUID UUID::Generate() {
+u128 UUID::AsU128() const {
+    u128 uuid_old;
+    std::memcpy(&uuid_old, uuid.data(), sizeof(UUID));
+    return uuid_old;
+}
+
+UUID UUID::MakeRandom() {
     std::random_device device;
-    std::mt19937 gen(device());
-    std::uniform_int_distribution<u64> distribution(1, std::numeric_limits<u64>::max());
-    return UUID{distribution(gen), distribution(gen)};
+
+    return MakeRandomWithSeed(device());
 }
 
-std::string UUID::Format() const {
-    return fmt::format("{:016x}{:016x}", uuid[1], uuid[0]);
+UUID UUID::MakeRandomWithSeed(u32 seed) {
+    // Create and initialize our RNG.
+    TinyMT rng;
+    rng.Initialize(seed);
+
+    UUID uuid;
+
+    // Populate the UUID with random bytes.
+    rng.GenerateRandomBytes(uuid.uuid.data(), sizeof(UUID));
+
+    return uuid;
 }
 
-std::string UUID::FormatSwitch() const {
-    std::array<u8, 16> s{};
-    std::memcpy(s.data(), uuid.data(), sizeof(u128));
-    return fmt::format("{:02x}{:02x}{:02x}{:02x}-{:02x}{:02x}-{:02x}{:02x}-{:02x}{:02x}-{:02x}{"
-                       ":02x}{:02x}{:02x}{:02x}{:02x}",
-                       s[0], s[1], s[2], s[3], s[4], s[5], s[6], s[7], s[8], s[9], s[10], s[11],
-                       s[12], s[13], s[14], s[15]);
+UUID UUID::MakeRandomRFC4122V4() {
+    auto uuid = MakeRandom();
+
+    // According to Proposed Standard RFC 4122 Section 4.4, we must:
+
+    // 1. Set the two most significant bits (bits 6 and 7) of the
+    //    clock_seq_hi_and_reserved to zero and one, respectively.
+    uuid.uuid[8] = 0x80 | (uuid.uuid[8] & 0x3F);
+
+    // 2. Set the four most significant bits (bits 12 through 15) of the
+    //    time_hi_and_version field to the 4-bit version number from Section 4.1.3.
+    uuid.uuid[6] = 0x40 | (uuid.uuid[6] & 0xF);
+
+    return uuid;
 }
 
 } // namespace Common