[Util] Add Uuid class for generating, parsing UUIDs This patch adds a Uuid implementation to the util/ directory, based on the Chromium base/ version with significant changes to work with our library types. Some cleanup of dependent methods, like the crypto random bytes functions, is included. Change-Id: Ibe562e700c2156414063f9337deab3546e8db158 Reviewed-on: https://chromium-review.googlesource.com/c/openscreen/+/7256767 Reviewed-by: Muyao Xu <muyaoxu@google.com> Commit-Queue: Jordan Bayles <jophba@chromium.org>
diff --git a/cast/standalone_receiver/cast_service.cc b/cast/standalone_receiver/cast_service.cc index e08b06e..ba6988d 100644 --- a/cast/standalone_receiver/cast_service.cc +++ b/cast/standalone_receiver/cast_service.cc
@@ -80,8 +80,8 @@ OSP_LOG_WARN << "Hardware address for interface " << config.interface.name << " is empty. Generating a random unique_id."; std::array<uint8_t, kCastUniqueIdLength> random_bytes; - GenerateRandomBytes(random_bytes.data(), kCastUniqueIdLength); - info.unique_id = HexEncode(random_bytes.data(), kCastUniqueIdLength); + GenerateRandomBytes(random_bytes); + info.unique_id = HexEncode(random_bytes); } info.friendly_name = config.friendly_name; info.model_name = config.model_name;
diff --git a/util/BUILD.gn b/util/BUILD.gn index bcc4d49..08692b2 100644 --- a/util/BUILD.gn +++ b/util/BUILD.gn
@@ -51,6 +51,7 @@ "stringprintf.h", "trace_logging.h", "url.h", + "uuid.h", "weak_ptr.h", "yet_another_bit_vector.h", ] @@ -80,6 +81,7 @@ "trace_logging/scoped_trace_operations.cc", "trace_logging/scoped_trace_operations.h", "url.cc", + "uuid.cc", "yet_another_bit_vector.cc", ] @@ -138,6 +140,7 @@ "stringprintf_unittest.cc", "trace_logging/scoped_trace_operations_unittest.cc", "url_unittest.cc", + "uuid_unittest.cc", "weak_ptr_unittest.cc", "yet_another_bit_vector_unittest.cc", ]
diff --git a/util/crypto/random_bytes.cc b/util/crypto/random_bytes.cc index fb80de3..99d9b45 100644 --- a/util/crypto/random_bytes.cc +++ b/util/crypto/random_bytes.cc
@@ -11,13 +11,13 @@ std::array<uint8_t, 16> GenerateRandomBytes16() { std::array<uint8_t, 16> result; - GenerateRandomBytes(result.data(), result.size()); + GenerateRandomBytes(result); return result; } -void GenerateRandomBytes(uint8_t* out, int len) { +void GenerateRandomBytes(ByteBuffer out) { // Working cryptography is mandatory for our library to run. - OSP_CHECK(RAND_bytes(out, len) == 1); + OSP_CHECK(RAND_bytes(out.data(), out.size()) == 1); } } // namespace openscreen
diff --git a/util/crypto/random_bytes.h b/util/crypto/random_bytes.h index 0d9ffb9..d3d3e22 100644 --- a/util/crypto/random_bytes.h +++ b/util/crypto/random_bytes.h
@@ -8,10 +8,12 @@ #include <array> #include <cstdint> +#include "platform/base/span.h" + namespace openscreen { std::array<uint8_t, 16> GenerateRandomBytes16(); -void GenerateRandomBytes(uint8_t* out, int len); +void GenerateRandomBytes(ByteBuffer out); } // namespace openscreen
diff --git a/util/crypto/random_bytes_unittest.cc b/util/crypto/random_bytes_unittest.cc index 33d00f5..2fc3329 100644 --- a/util/crypto/random_bytes_unittest.cc +++ b/util/crypto/random_bytes_unittest.cc
@@ -21,7 +21,7 @@ TEST(RandomBytesTest, CanGenerateRandomBytes) { std::array<uint8_t, 4> bytes; - GenerateRandomBytes(bytes.data(), bytes.size()); + GenerateRandomBytes(bytes); NonZero pred; ASSERT_TRUE(std::any_of(bytes.begin(), bytes.end(), pred)); @@ -39,7 +39,7 @@ constexpr int kKeyLength = 100; std::array<std::array<uint8_t, kKeyLength>, kNumKeys> keys; for (int i = 0; i < kNumKeys; ++i) { - GenerateRandomBytes(keys[i].data(), kKeyLength); + GenerateRandomBytes(keys[i]); } std::sort(std::begin(keys), std::end(keys));
diff --git a/util/string_util.h b/util/string_util.h index e624209..3d5d5ad 100644 --- a/util/string_util.h +++ b/util/string_util.h
@@ -13,6 +13,7 @@ #include <vector> // String query and manipulation utilities. +// TODO(jophba): remove nested string_util namespace. namespace openscreen::string_util { namespace internal { @@ -23,33 +24,45 @@ } // namespace internal -// Determines whether the given character is an alphabetic character. +// Determines whether `c` is a valid ASCII alphabetic character code. inline bool ascii_isalpha(unsigned char c) { return (internal::kPropertyBits[c] & 0x01) != 0; } -// Determines whether the given character can be represented as a decimal -// digit character (i.e. {0-9}). +// Determines whether `c` is a valid ASCII decimal digit (i.e. [0-9]). inline bool ascii_isdigit(unsigned char c) { - return c >= '0' && c <= '9'; + return '0' <= c && c <= '9'; } -// Determines whether the given character is printable, including spaces. +// Determines whether `c` is a valid ASCII lower case hexadecimal digit +// (i.e. [a-fA-F0-9]). +inline bool ascii_islowerhex(unsigned char c) { + return ascii_isdigit(c) || ('a' <= c && c <= 'f'); +} + +// Determines whether `c` is a valid ASCII hexadecimal digit (i.e. [a-fA-F0-9]). +inline bool ascii_ishex(unsigned char c) { + return ascii_islowerhex(c) || ('A' <= c && c <= 'F'); +} + +// Determines whether `c` is a valid, printable ASCII digit. inline bool ascii_isprint(unsigned char c) { return c >= 32 && c < 127; } -// Determines whether the given character is a whitespace character (space, -// tab, vertical tab, formfeed, linefeed, or carriage return). +// Determines whether `c` is a whitespace character +// (space, tab, vertical tab, formfeed, linefeed, or carriage return). inline bool ascii_isspace(unsigned char c) { return (internal::kPropertyBits[c] & 0x08) != 0; } +// If `c` is an upper case ASCII character, returns its lower case equivalent. +// Otherwise, returns `c` unchanged. inline char ascii_tolower(unsigned char c) { return internal::kToLower[c]; } -// Converts s to lowercase. +// Converts `s` to lowercase. void AsciiStrToLower(std::string& s); // Creates a lowercase string from a given string_view. @@ -59,7 +72,7 @@ return internal::kToUpper[c]; } -// Converts s to uppercase. +// Converts `s` to uppercase. void AsciiStrToUpper(std::string& s); // Creates a uppercase string from a given string_view. @@ -67,8 +80,7 @@ // Returns whether a given string `text` begins with `prefix`. // -// NOTE: Replace with std::{string,string_view}::starts_with() once C++20 is the -// default. +// TODO(jophba): Replace with std::{string,string_view}::starts_with(). inline bool starts_with(std::string_view text, std::string_view prefix) { return prefix.empty() || (text.size() >= prefix.size() && @@ -77,8 +89,7 @@ // Returns whether a given string `text` ends with `suffix`. // -// NOTE: Replace with std::{string,string_view}::ends_with() once C++20 is the -// default. +// TODO(jophba): Replace with std::{string,string_view}::ends_with(). inline bool ends_with(std::string_view text, std::string_view suffix) { return suffix.empty() || (text.size() >= suffix.size() && memcmp(text.data() + (text.size() - suffix.size()),
diff --git a/util/uuid.cc b/util/uuid.cc new file mode 100644 index 0000000..d249140 --- /dev/null +++ b/util/uuid.cc
@@ -0,0 +1,126 @@ +// Copyright 2025 The Chromium Authors +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "util/uuid.h" + +#include <stddef.h> +#include <stdint.h> + +#include <ostream> + +#include "util/big_endian.h" +#include "util/crypto/random_bytes.h" +#include "util/hashing.h" +#include "util/osp_logging.h" +#include "util/string_util.h" +#include "util/stringprintf.h" + +namespace openscreen { + +namespace { + +constexpr bool IsHyphenPosition(size_t i) { + return i == 8 || i == 13 || i == 18 || i == 23; +} + +// Returns a canonical Uuid string given that `input` is validly formatted +// xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx, such that x is a hexadecimal digit. +// If `strict`, x must be a lower-case hexadecimal digit. +std::string GetCanonicalUuidInternal(std::string_view input, bool strict) { + constexpr size_t kUuidLength = 36; + if (input.length() != kUuidLength) { + return {}; + } + + std::string lowercase; + lowercase.resize(kUuidLength); + for (size_t i = 0; i < input.length(); ++i) { + auto current = input[i]; + if (IsHyphenPosition(i)) { + if (current != '-') { + return {}; + } + lowercase[i] = '-'; + } else { + if (strict ? !string_util::ascii_islowerhex(current) + : !string_util::ascii_ishex(current)) { + return {}; + } + lowercase[i] = static_cast<char>(string_util::ascii_tolower(current)); + } + } + + return lowercase; +} + +} // namespace + +// static +Uuid Uuid::GenerateRandomV4() { + return FormatRandomDataAsV4Impl(GenerateRandomBytes16()); +} + +// static +Uuid Uuid::FormatRandomDataAsV4Impl(ByteView input) { + OSP_CHECK_EQ(input.size(), kGuidV4InputLength); + + auto first_u64 = ReadBigEndian<uint64_t>(input.first(8).data()); + auto second_u64 = ReadBigEndian<uint64_t>(input.last(8).data()); + + // Set the Uuid to version 4 as described in RFC 4122, section 4.4. + // The format of Uuid version 4 must be xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx, + // where y is one of [8, 9, a, b]. + + // Clear the version bits and set the version to 4: + first_u64 &= 0xffffffff'ffff0fffULL; + first_u64 |= 0x00000000'00004000ULL; + + // Clear bit 65 and set bit 64, to set the 'var' field to 0b10 per RFC 9562 + // section 5.4. + second_u64 &= 0x3fffffff'ffffffffULL; + second_u64 |= 0x80000000'00000000ULL; + + Uuid uuid; + uuid.lowercase_ = StringPrintf( + "%08x-%04x-%04x-%04x-%012llx", static_cast<uint32_t>(first_u64 >> 32), + static_cast<uint32_t>((first_u64 >> 16) & 0x0000ffff), + static_cast<uint32_t>(first_u64 & 0x0000ffff), + static_cast<uint32_t>(second_u64 >> 48), + second_u64 & 0x0000ffff'ffffffffULL); + return uuid; +} + +// static +Uuid Uuid::ParseCaseInsensitive(std::string_view input) { + Uuid uuid; + uuid.lowercase_ = GetCanonicalUuidInternal(input, /*strict=*/false); + return uuid; +} + +// static +Uuid Uuid::ParseLowercase(std::string_view input) { + Uuid uuid; + uuid.lowercase_ = GetCanonicalUuidInternal(input, /*strict=*/true); + return uuid; +} + +Uuid::Uuid() = default; +Uuid::Uuid(const Uuid& other) = default; +Uuid::Uuid(Uuid&& other) noexcept = default; +Uuid& Uuid::operator=(const Uuid& other) = default; +Uuid& Uuid::operator=(Uuid&& other) = default; + +const std::string& Uuid::AsLowercaseString() const { + return lowercase_; +} + +std::ostream& operator<<(std::ostream& out, const Uuid& uuid) { + return out << uuid.AsLowercaseString(); +} + +size_t UuidHash::operator()(const Uuid& uuid) const { + return ComputeAggregateHash(uuid.AsLowercaseString()); +} + +} // namespace openscreen
diff --git a/util/uuid.h b/util/uuid.h new file mode 100644 index 0000000..fe90adb --- /dev/null +++ b/util/uuid.h
@@ -0,0 +1,81 @@ +// Copyright 2025 The Chromium Authors +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef UTIL_UUID_H_ +#define UTIL_UUID_H_ + +#include <stdint.h> + +#include <compare> +#include <iosfwd> +#include <string> +#include <string_view> + +#include "platform/base/span.h" + +namespace openscreen { + +// UUID implementation strongly based off of Chromium's base::Uuid +// implementation. Provides securely generated random Uuids as well as parsing +// logic for inputted UUIDs. +class Uuid { + public: + // Length in bytes of the input required to format the input as a Uuid in the + // form of version 4. + static constexpr size_t kGuidV4InputLength = 16; + + // Generate a 128-bit random Uuid in the form of version 4. see RFC 4122, + // section 4.4. The format of Uuid version 4 must be + // xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx, where y is one of [8, 9, a, b]. The + // hexadecimal values "a" through "f" are output as lower case characters. + static Uuid GenerateRandomV4(); + + // Returns a valid Uuid if the input string conforms to the Uuid format, and + // an invalid Uuid otherwise. Accepts both lower case and upper case hex + // characters. + static Uuid ParseCaseInsensitive(std::string_view input); + + // Similar to ParseCaseInsensitive(), but all hexadecimal values "a" through + // "f" must be lower case characters. + static Uuid ParseLowercase(std::string_view input); + + // Constructs an invalid Uuid. + Uuid(); + + Uuid(const Uuid& other); + Uuid(Uuid&& other) noexcept; + Uuid& operator=(const Uuid& other); + Uuid& operator=(Uuid&& other); + + bool is_valid() const { return !lowercase_.empty(); } + + // Returns the Uuid in a lowercase string format if it is valid, and an empty + // string otherwise. The returned value is guaranteed to be parsed by + // ParseLowercase(). + const std::string& AsLowercaseString() const; + + // Invalid Uuids are equal. + friend bool operator==(const Uuid&, const Uuid&) = default; + // Uuids are 128bit chunks of data so must be indistinguishable if equivalent. + friend std::strong_ordering operator<=>(const Uuid&, const Uuid&) = default; + + private: + static Uuid FormatRandomDataAsV4Impl(ByteView input); + + // The lowercase form of the Uuid. Empty for invalid Uuids. + std::string lowercase_; +}; + +// For runtime usage only. Do not store the result of this hash, as it may +// change in the future. +struct UuidHash { + size_t operator()(const Uuid& uuid) const; +}; + +// Stream operator so Uuid objects can be used in logging statements. +std::ostream& operator<<(std::ostream& out, const Uuid& uuid); + +} // namespace openscreen + +#endif // UTIL_UUID_H_
diff --git a/util/uuid_unittest.cc b/util/uuid_unittest.cc new file mode 100644 index 0000000..d71258b --- /dev/null +++ b/util/uuid_unittest.cc
@@ -0,0 +1,194 @@ +// Copyright 2025 The Chromium Authors +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "util/uuid.h" + +#include <stdint.h> + +#include <array> +#include <limits> +#include <set> +#include <unordered_set> + +#include "gtest/gtest.h" +#include "util/string_util.h" + +namespace openscreen { + +namespace { + +// The format of Uuid version 4 must be xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx, +// where y is one of [8, 9, a, b]. +bool IsValidV4(const Uuid& guid) { + const std::string& lowercase = guid.AsLowercaseString(); + return guid.is_valid() && lowercase[14] == '4' && + (lowercase[19] == '8' || lowercase[19] == '9' || + lowercase[19] == 'a' || lowercase[19] == 'b'); +} + +} // namespace + +TEST(UuidTest, UuidBasicUniqueness) { + constexpr int kIterations = 10; + for (int i = 0; i < kIterations; ++i) { + const Uuid guid1 = Uuid::GenerateRandomV4(); + const Uuid guid2 = Uuid::GenerateRandomV4(); + EXPECT_NE(guid1, guid2); + EXPECT_TRUE(guid1.is_valid()); + EXPECT_TRUE(IsValidV4(guid1)); + EXPECT_TRUE(guid2.is_valid()); + EXPECT_TRUE(IsValidV4(guid2)); + } +} + +namespace { + +void TestUuidValidity(std::string_view input, + bool case_insensitive, + bool strict) { + SCOPED_TRACE(input); + { + const Uuid guid = Uuid::ParseCaseInsensitive(input); + EXPECT_EQ(case_insensitive, guid.is_valid()); + } + { + const Uuid guid = Uuid::ParseLowercase(input); + EXPECT_EQ(strict, guid.is_valid()); + } +} + +} // namespace + +TEST(UuidTest, Validity) { + // Empty Uuid is invalid. + EXPECT_FALSE(Uuid().is_valid()); + + enum Parsability { kDoesntParse, kParsesCaseInsensitiveOnly, kAlwaysParses }; + + static constexpr struct { + std::string_view input; + Parsability parsability; + } kUuidValidity[] = { + {"invalid", kDoesntParse}, + {"0123456789ab-cdef-fedc-ba98-76543210", kDoesntParse}, + {"0123456789abcdeffedcba9876543210", kDoesntParse}, + {"01234567-89Zz-ZzZz-ZzZz-Zz9876543210", kDoesntParse}, + {"DEADBEEFDEADBEEFDEADBEEFDEADBEEF", kDoesntParse}, + {"deadbeefWdeadXbeefYdeadZbeefdeadbeef", kDoesntParse}, + {"XXXdeadbeefWdeadXbeefYdeadZbeefdeadbeefXXX", kDoesntParse}, + {"01234567-89aB-cDeF-fEdC-bA9876543210", kParsesCaseInsensitiveOnly}, + {"DEADBEEF-DEAD-BEEF-DEAD-BEEFDEADBEEF", kParsesCaseInsensitiveOnly}, + {"00000000-0000-0000-0000-000000000000", kAlwaysParses}, + {"deadbeef-dead-beef-dead-beefdeadbeef", kAlwaysParses}, + }; + + for (const auto& validity : kUuidValidity) { + const bool case_insensitive = validity.parsability != kDoesntParse; + const bool strict = validity.parsability == kAlwaysParses; + TestUuidValidity(validity.input, case_insensitive, strict); + } +} + +TEST(UuidTest, EqualityAndRoundTrip) { + static constexpr char kCanonicalStr[] = + "deadbeef-dead-4eef-bead-beefdeadbeef"; + + const Uuid from_lower = + Uuid::ParseCaseInsensitive(string_util::AsciiStrToLower(kCanonicalStr)); + EXPECT_EQ(kCanonicalStr, from_lower.AsLowercaseString()); + + const Uuid from_upper = + Uuid::ParseCaseInsensitive(string_util::AsciiStrToUpper(kCanonicalStr)); + EXPECT_EQ(kCanonicalStr, from_upper.AsLowercaseString()); + + EXPECT_EQ(from_lower, from_upper); + + // Invalid Uuids are equal. + EXPECT_EQ(Uuid(), Uuid()); +} + +TEST(UuidTest, UnorderedSet) { + std::unordered_set<Uuid, UuidHash> guid_set; + + static constexpr char kUuid1[] = "01234567-89ab-cdef-fedc-ba9876543210"; + guid_set.insert( + Uuid::ParseCaseInsensitive(string_util::AsciiStrToLower(kUuid1))); + EXPECT_EQ(1u, guid_set.size()); + guid_set.insert( + Uuid::ParseCaseInsensitive(string_util::AsciiStrToUpper(kUuid1))); + EXPECT_EQ(1u, guid_set.size()); + + static constexpr char kUuid2[] = "deadbeef-dead-beef-dead-beefdeadbeef"; + guid_set.insert( + Uuid::ParseCaseInsensitive(string_util::AsciiStrToLower(kUuid2))); + EXPECT_EQ(2u, guid_set.size()); + guid_set.insert( + Uuid::ParseCaseInsensitive(string_util::AsciiStrToUpper(kUuid2))); + EXPECT_EQ(2u, guid_set.size()); +} + +TEST(UuidTest, Set) { + std::set<Uuid> guid_set; + + static constexpr char kUuid1[] = "01234567-89ab-cdef-0123-456789abcdef"; + const Uuid guid1 = Uuid::ParseLowercase(kUuid1); + ASSERT_TRUE(guid1.is_valid()); + guid_set.insert(guid1); + + static constexpr char kUuid2[] = "deadbeef-dead-beef-dead-beefdeadbeef"; + const Uuid guid2 = Uuid::ParseLowercase(kUuid2); + ASSERT_TRUE(guid2.is_valid()); + guid_set.insert(guid2); + + // Test that the order of the Uuids was preserved. + auto it = guid_set.begin(); + EXPECT_EQ(guid1, *it); + ++it; + EXPECT_EQ(guid2, *it); + ++it; + EXPECT_EQ(guid_set.end(), it); +} + +TEST(UuidTest, Compare) { + static constexpr char kUuid[] = "21abd97f-73e8-4b88-9389-a9fee6abda5e"; + static constexpr char kUuidLess[] = "1e0dcaca-9e7c-4f4b-bcc6-e4c02b0c99df"; + static constexpr char kUuidGreater[] = "6eeb1bc8-186b-433c-9d6a-a827bc96b2d4"; + + const Uuid guid = Uuid::ParseLowercase(kUuid); + const Uuid guid_eq = Uuid::ParseLowercase(kUuid); + const Uuid guid_lt = Uuid::ParseLowercase(kUuidLess); + const Uuid guid_gt = Uuid::ParseLowercase(kUuidGreater); + const Uuid guid_invalid = Uuid(); + + EXPECT_TRUE(guid_eq == guid); + EXPECT_FALSE(guid_eq != guid); + EXPECT_FALSE(guid_eq < guid); + EXPECT_TRUE(guid_eq <= guid); + EXPECT_FALSE(guid_eq > guid); + EXPECT_TRUE(guid_eq >= guid); + + EXPECT_FALSE(guid_lt == guid); + EXPECT_TRUE(guid_lt != guid); + EXPECT_TRUE(guid_lt < guid); + EXPECT_TRUE(guid_lt <= guid); + EXPECT_FALSE(guid_lt > guid); + EXPECT_FALSE(guid_lt >= guid); + + EXPECT_FALSE(guid_gt == guid); + EXPECT_TRUE(guid_gt != guid); + EXPECT_FALSE(guid_gt < guid); + EXPECT_FALSE(guid_gt <= guid); + EXPECT_TRUE(guid_gt > guid); + EXPECT_TRUE(guid_gt >= guid); + + // Invalid Uuids are the "least". + EXPECT_FALSE(guid_invalid == guid); + EXPECT_TRUE(guid_invalid != guid); + EXPECT_TRUE(guid_invalid < guid); + EXPECT_TRUE(guid_invalid <= guid); + EXPECT_FALSE(guid_invalid > guid); + EXPECT_FALSE(guid_invalid >= guid); +} + +} // namespace openscreen