diff options
author | Sybren A. Stüvel <sybren@blender.org> | 2021-09-17 12:53:00 +0300 |
---|---|---|
committer | Sybren A. Stüvel <sybren@blender.org> | 2021-09-17 13:22:00 +0300 |
commit | e1d7ce005f9f9ca84befdd531014d498966f27fc (patch) | |
tree | f518b7fa618a615d4a75f13e983e4f690ee759bd /source | |
parent | 1cd20b0026838c3fb69c0b273db8513f89f31f22 (diff) |
Blenlib: introduce a UUID type
Add `BLI_uuid` and `DNA_uuid_types.h` with a UUID implementation
following RFC4122 (https://datatracker.ietf.org/doc/html/rfc4122.html).
The following features are implemented:
- A struct of 128 bits that can be used in DNA definitions.
- Generation of version 4 UUIDs, that is, purely random ones.
- UUID equality function.
- String to UUID and UUID to string conversion functions that are
compatible with RFC4122.
- C++ stream operator that outputs the UUID as string.
This UUID will be used by the asset system, to uniquely identify asset
catalogs.
Reviewed By: Severin, jacqueslucke
Differential Revision: https://developer.blender.org/D12475
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/CMakeLists.txt | 1 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_session_uuid.h | 7 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_uuid.h | 67 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 3 | ||||
-rw-r--r-- | source/blender/blenlib/intern/uuid.cc | 112 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_uuid_test.cc | 132 | ||||
-rw-r--r-- | source/blender/makesdna/DNA_uuid_types.h | 43 | ||||
-rw-r--r-- | source/blender/makesdna/intern/makesdna.c | 2 |
8 files changed, 367 insertions, 0 deletions
diff --git a/source/blender/CMakeLists.txt b/source/blender/CMakeLists.txt index 8d18cf0ae9a..fbc0ec440cf 100644 --- a/source/blender/CMakeLists.txt +++ b/source/blender/CMakeLists.txt @@ -92,6 +92,7 @@ set(SRC_DNA_INC ${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_texture_types.h ${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_tracking_types.h ${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_userdef_types.h + ${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_uuid_types.h ${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_vec_types.h ${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_vfont_types.h ${CMAKE_CURRENT_SOURCE_DIR}/makesdna/DNA_view2d_types.h diff --git a/source/blender/blenlib/BLI_session_uuid.h b/source/blender/blenlib/BLI_session_uuid.h index 05355a85b39..887044e9b54 100644 --- a/source/blender/blenlib/BLI_session_uuid.h +++ b/source/blender/blenlib/BLI_session_uuid.h @@ -18,6 +18,13 @@ /** \file * \ingroup bli + * + * Functions for generating and handling "Session UUIDs". + * + * Note that these are not true universally-unique identifiers, but only unique during the current + * Blender session. + * + * For true UUIDs, see `BLI_uuid.h`. */ #ifdef __cplusplus diff --git a/source/blender/blenlib/BLI_uuid.h b/source/blender/blenlib/BLI_uuid.h new file mode 100644 index 00000000000..15350849f67 --- /dev/null +++ b/source/blender/blenlib/BLI_uuid.h @@ -0,0 +1,67 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#pragma once + +/** \file + * \ingroup bli + * + * Functions for generating and handling UUID structs according to RFC4122. + * + * Note that these are true UUIDs, not to be confused with the "session uuid" defined in + * `BLI_session_uuid.h`. + */ +#include "DNA_uuid_types.h" + +#include "BLI_compiler_attrs.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * UUID generator for random (version 4) UUIDs. See RFC4122 section 4.4. + * This function is not thread-safe. */ +UUID BLI_uuid_generate_random(void); + +/** Compare two UUIDs, return true iff they are equal. */ +bool BLI_uuid_equal(UUID uuid1, UUID uuid2); + +/** + * Format UUID as string. + * The buffer must be at least 37 bytes (36 bytes for the UUID + terminating 0). + */ +void BLI_uuid_format(char *buffer, UUID uuid) ATTR_NONNULL(); + +/** + * Parse a string as UUID. + * The string MUST be in the format xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx, + * as produced by #BLI_uuid_format(). + * + * Return true if the string could be parsed, and false otherwise. In the latter case, the UUID may + * have been partially updated. + */ +bool BLI_uuid_parse_string(UUID *uuid, const char *buffer) ATTR_NONNULL(); + +#ifdef __cplusplus +} + +# include <ostream> + +/** Output the UUID as formatted ASCII string, see #BLI_uuid_format(). */ +std::ostream &operator<<(std::ostream &stream, UUID uuid); + +#endif diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index f607285c4d0..1eaf007e01b 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -147,6 +147,7 @@ set(SRC intern/time.c intern/timecode.c intern/timeit.cc + intern/uuid.cc intern/uvproject.c intern/voronoi_2d.c intern/voxel.c @@ -310,6 +311,7 @@ set(SRC BLI_utildefines_stack.h BLI_utildefines_variadic.h BLI_utility_mixins.hh + BLI_uuid.h BLI_uvproject.h BLI_vector.hh BLI_vector_adaptor.hh @@ -455,6 +457,7 @@ if(WITH_GTESTS) tests/BLI_string_utf8_test.cc tests/BLI_task_graph_test.cc tests/BLI_task_test.cc + tests/BLI_uuid_test.cc tests/BLI_vector_set_test.cc tests/BLI_vector_test.cc tests/BLI_virtual_array_test.cc diff --git a/source/blender/blenlib/intern/uuid.cc b/source/blender/blenlib/intern/uuid.cc new file mode 100644 index 00000000000..a0fbc1a61ff --- /dev/null +++ b/source/blender/blenlib/intern/uuid.cc @@ -0,0 +1,112 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup bli + */ + +#include "BLI_uuid.h" + +#include <random> +#include <string.h> + +/* Ensure the UUID struct doesn't have any padding, to be compatible with memcmp(). */ +static_assert(sizeof(UUID) == 16, "expect UUIDs to be 128 bit exactly"); + +UUID BLI_uuid_generate_random() +{ + static std::mt19937_64 rng = []() { + std::mt19937_64 rng; + + /* Ensure the RNG really can output 64-bit values. */ + static_assert(rng.min() == 0LL); + static_assert(rng.max() == 0xffffffffffffffffLL); + + struct timespec ts; + timespec_get(&ts, TIME_UTC); + rng.seed(ts.tv_nsec); + + return rng; + }(); + + UUID uuid; + + /* RFC4122 suggests setting certain bits to a fixed value, and then randomizing the remaining + * bits. The opposite is easier to implement, though, so that's what's done here. */ + + /* Read two 64-bit numbers to randomize all 128 bits of the UUID. */ + uint64_t *uuid_as_int64 = reinterpret_cast<uint64_t *>(&uuid); + uuid_as_int64[0] = rng(); + uuid_as_int64[1] = rng(); + + /* Set the most significant four bits to 0b0100 to indicate version 4 (random UUID). */ + uuid.time_hi_and_version &= ~0xF000; + uuid.time_hi_and_version |= 0x4000; + + /* Set the most significant two bits to 0b10 to indicate compatibility with RFC4122. */ + uuid.clock_seq_hi_and_reserved &= ~0x40; + uuid.clock_seq_hi_and_reserved |= 0x80; + + return uuid; +} + +bool BLI_uuid_equal(const UUID uuid1, const UUID uuid2) +{ + return memcmp(&uuid1, &uuid2, sizeof(uuid1)) == 0; +} + +void BLI_uuid_format(char *buffer, const UUID uuid) +{ + sprintf(buffer, + "%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x", + uuid.time_low, + uuid.time_mid, + uuid.time_hi_and_version, + uuid.clock_seq_hi_and_reserved, + uuid.clock_seq_low, + uuid.node[0], + uuid.node[1], + uuid.node[2], + uuid.node[3], + uuid.node[4], + uuid.node[5]); +} + +bool BLI_uuid_parse_string(UUID *uuid, const char *buffer) +{ + const int num_fields_parsed = sscanf(buffer, + "%8x-%4hx-%4hx-%2hhx%2hhx-%2hhx%2hhx%2hhx%2hhx%2hhx%2hhx", + &uuid->time_low, + &uuid->time_mid, + &uuid->time_hi_and_version, + &uuid->clock_seq_hi_and_reserved, + &uuid->clock_seq_low, + &uuid->node[0], + &uuid->node[1], + &uuid->node[2], + &uuid->node[3], + &uuid->node[4], + &uuid->node[5]); + return num_fields_parsed == 11; +} + +std::ostream &operator<<(std::ostream &stream, UUID uuid) +{ + std::string buffer(36, '\0'); + BLI_uuid_format(buffer.data(), uuid); + stream << buffer; + return stream; +} diff --git a/source/blender/blenlib/tests/BLI_uuid_test.cc b/source/blender/blenlib/tests/BLI_uuid_test.cc new file mode 100644 index 00000000000..2c9da920897 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_uuid_test.cc @@ -0,0 +1,132 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +#include "testing/testing.h" +#include <cstring> + +#include "BLI_uuid.h" + +TEST(BLI_uuid, generate_random) +{ + const UUID uuid = BLI_uuid_generate_random(); + + // The 4 MSbits represent the "version" of the UUID. + const uint16_t version = uuid.time_hi_and_version >> 12; + EXPECT_EQ(version, 4); + + // The 2 MSbits should be 0b10, indicating compliance with RFC4122. + const uint8_t reserved = uuid.clock_seq_hi_and_reserved >> 6; + EXPECT_EQ(reserved, 0b10); +} + +TEST(BLI_uuid, generate_many_random) +{ + const UUID first_uuid = BLI_uuid_generate_random(); + + /* Generate lots of UUIDs to get some indication that the randomness is okay. */ + for (int i = 0; i < 1000000; ++i) { + const UUID uuid = BLI_uuid_generate_random(); + EXPECT_FALSE(BLI_uuid_equal(first_uuid, uuid)); + + // Check that the non-random bits are set according to RFC4122. + const uint16_t version = uuid.time_hi_and_version >> 12; + EXPECT_EQ(version, 4); + const uint8_t reserved = uuid.clock_seq_hi_and_reserved >> 6; + EXPECT_EQ(reserved, 0b10); + } +} + +TEST(BLI_uuid, equality) +{ + const UUID uuid1 = BLI_uuid_generate_random(); + const UUID uuid2 = BLI_uuid_generate_random(); + + EXPECT_TRUE(BLI_uuid_equal(uuid1, uuid1)); + EXPECT_FALSE(BLI_uuid_equal(uuid1, uuid2)); +} + +TEST(BLI_uuid, string_formatting) +{ + UUID uuid; + std::string buffer(36, '\0'); + + memset(&uuid, 0, sizeof(uuid)); + BLI_uuid_format(buffer.data(), uuid); + EXPECT_EQ("00000000-0000-0000-0000-000000000000", buffer); + + /* Demo of where the bits end up in the formatted string. */ + uuid.time_low = 1; + uuid.time_mid = 2; + uuid.time_hi_and_version = 3; + uuid.clock_seq_hi_and_reserved = 4; + uuid.clock_seq_low = 5; + uuid.node[0] = 6; + uuid.node[5] = 7; + BLI_uuid_format(buffer.data(), uuid); + EXPECT_EQ("00000001-0002-0003-0405-060000000007", buffer); + + /* Somewhat more complex bit patterns. This is a version 1 UUID generated from Python. */ + const UUID uuid1 = {3540651616, 5282, 4588, 139, 153, 0xf7, 0x73, 0x69, 0x44, 0xdb, 0x8b}; + BLI_uuid_format(buffer.data(), uuid1); + EXPECT_EQ("d30a0e60-14a2-11ec-8b99-f7736944db8b", buffer); + + /* Namespace UUID, example listed in RFC4211. */ + const UUID namespace_dns = { + 0x6ba7b810, 0x9dad, 0x11d1, 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8}; + BLI_uuid_format(buffer.data(), namespace_dns); + EXPECT_EQ("6ba7b810-9dad-11d1-80b4-00c04fd430c8", buffer); +} + +TEST(BLI_uuid, string_parsing_ok) +{ + UUID uuid; + std::string buffer(36, '\0'); + + const bool parsed_ok = BLI_uuid_parse_string(&uuid, "d30a0e60-14a2-11ec-8b99-f7736944db8b"); + EXPECT_TRUE(parsed_ok); + BLI_uuid_format(buffer.data(), uuid); + EXPECT_EQ("d30a0e60-14a2-11ec-8b99-f7736944db8b", buffer); +} + +TEST(BLI_uuid, string_parsing_capitalisation) +{ + UUID uuid; + std::string buffer(36, '\0'); + + /* RFC4122 demands acceptance of upper-case hex digits. */ + const bool parsed_ok = BLI_uuid_parse_string(&uuid, "D30A0E60-14A2-11EC-8B99-F7736944DB8B"); + EXPECT_TRUE(parsed_ok); + BLI_uuid_format(buffer.data(), uuid); + + /* Software should still output lower-case hex digits, though. */ + EXPECT_EQ("d30a0e60-14a2-11ec-8b99-f7736944db8b", buffer); +} + +TEST(BLI_uuid, string_parsing_fail) +{ + UUID uuid; + std::string buffer(36, '\0'); + + const bool parsed_ok = BLI_uuid_parse_string(&uuid, "d30a0e60!14a2-11ec-8b99-f7736944db8b"); + EXPECT_FALSE(parsed_ok); +} + +TEST(BLI_uuid, stream_operator) +{ + std::stringstream ss; + const UUID uuid = {3540651616, 5282, 4588, 139, 153, 0xf7, 0x73, 0x69, 0x44, 0xdb, 0x8b}; + ss << uuid; + EXPECT_EQ(ss.str(), "d30a0e60-14a2-11ec-8b99-f7736944db8b"); +} diff --git a/source/blender/makesdna/DNA_uuid_types.h b/source/blender/makesdna/DNA_uuid_types.h new file mode 100644 index 00000000000..30c8beaa628 --- /dev/null +++ b/source/blender/makesdna/DNA_uuid_types.h @@ -0,0 +1,43 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup DNA + */ + +#pragma once + +#include "DNA_defs.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * \brief Universally Unique Identifier according to RFC4122. + */ +typedef struct UUID { + uint32_t time_low; + uint16_t time_mid; + uint16_t time_hi_and_version; + uint8_t clock_seq_hi_and_reserved; + uint8_t clock_seq_low; + uint8_t node[6]; +} UUID; + +#ifdef __cplusplus +} +#endif diff --git a/source/blender/makesdna/intern/makesdna.c b/source/blender/makesdna/intern/makesdna.c index 061c3462a69..0b7848b6662 100644 --- a/source/blender/makesdna/intern/makesdna.c +++ b/source/blender/makesdna/intern/makesdna.c @@ -141,6 +141,7 @@ static const char *includefiles[] = { "DNA_volume_types.h", "DNA_simulation_types.h", "DNA_pointcache_types.h", + "DNA_uuid_types.h", "DNA_asset_types.h", /* see comment above before editing! */ @@ -1678,6 +1679,7 @@ int main(int argc, char **argv) #include "DNA_texture_types.h" #include "DNA_tracking_types.h" #include "DNA_userdef_types.h" +#include "DNA_uuid_types.h" #include "DNA_vec_types.h" #include "DNA_vfont_types.h" #include "DNA_view2d_types.h" |