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

1 files changed, 112 insertions, 0 deletions

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;
+}