[shuffle] Move utils to new structure.
The name `core` was decided fit better with the base language for the
IR. This CL moves the `core/` folder to `utils/` and moves the files
into the correct subdirectories. The build targets and namespaces are
not updated as part of the move and will be fixed up in later CLs.
Bug: tint:1988
Change-Id: I1fc4414c86b28e1669af2d2d07340ecfdd9ba681
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/142361
Reviewed-by: Ben Clayton <bclayton@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
diff --git a/src/tint/utils/math/crc32.h b/src/tint/utils/math/crc32.h
new file mode 100644
index 0000000..022eefd
--- /dev/null
+++ b/src/tint/utils/math/crc32.h
@@ -0,0 +1,81 @@
+// Copyright 2022 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SRC_TINT_UTILS_MATH_CRC32_H_
+#define SRC_TINT_UTILS_MATH_CRC32_H_
+
+#include <stdint.h>
+#include <cstddef>
+
+namespace tint::utils {
+
+constexpr uint32_t kCRC32LUT[] = {
+ 0, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
+ 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
+ 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
+ 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
+ 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
+ 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
+ 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
+ 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
+ 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
+ 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
+ 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
+ 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
+ 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
+ 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
+ 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
+ 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
+ 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
+ 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
+ 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
+ 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
+ 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
+ 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
+ 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
+ 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
+ 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
+ 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
+ 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
+ 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
+ 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
+ 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
+ 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
+ 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d};
+
+/// @returns the CRC32 of the string @p s.
+/// @note this function can be used to calculate the CRC32 of a string literal
+/// at compile time.
+/// @see https://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRC-32_algorithm
+constexpr uint32_t CRC32(const char* s) {
+ uint32_t crc = 0xffffffff;
+ for (auto* p = s; *p != '\0'; ++p) {
+ crc = (crc >> 8) ^ kCRC32LUT[static_cast<uint8_t>(crc) ^ static_cast<uint8_t>(*p)];
+ }
+ return crc ^ 0xffffffff;
+}
+
+/// @returns the CRC32 of the data at @p ptr of size @p size.
+inline uint32_t CRC32(const void* ptr, size_t size) {
+ auto* p = static_cast<const uint8_t*>(ptr);
+ uint32_t crc = 0xffffffff;
+ while (size--) {
+ crc = (crc >> 8) ^ kCRC32LUT[static_cast<uint8_t>(crc) ^ *p++];
+ }
+ return crc ^ 0xffffffff;
+}
+
+} // namespace tint::utils
+
+#endif // SRC_TINT_UTILS_MATH_CRC32_H_
diff --git a/src/tint/utils/math/crc32_test.cc b/src/tint/utils/math/crc32_test.cc
new file mode 100644
index 0000000..f029108
--- /dev/null
+++ b/src/tint/utils/math/crc32_test.cc
@@ -0,0 +1,35 @@
+// Copyright 2022 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "src/tint/utils/math/crc32.h"
+
+#include "gtest/gtest.h"
+
+namespace tint::utils {
+namespace {
+
+TEST(CRC32Test, Compiletime) {
+ static_assert(CRC32("") == 0x00000000u);
+ static_assert(CRC32("hello world") == 0x0d4a1185u);
+ static_assert(CRC32("123456789") == 0xcbf43926u);
+}
+
+TEST(CRC32Test, Runtime) {
+ EXPECT_EQ(CRC32(""), 0x00000000u);
+ EXPECT_EQ(CRC32("hello world"), 0x0d4a1185u);
+ EXPECT_EQ(CRC32("123456789"), 0xcbf43926u);
+}
+
+} // namespace
+} // namespace tint::utils
diff --git a/src/tint/utils/math/hash.h b/src/tint/utils/math/hash.h
new file mode 100644
index 0000000..74f053b
--- /dev/null
+++ b/src/tint/utils/math/hash.h
@@ -0,0 +1,301 @@
+// Copyright 2021 The Tint Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SRC_TINT_UTILS_MATH_HASH_H_
+#define SRC_TINT_UTILS_MATH_HASH_H_
+
+#include <stdint.h>
+#include <cstdio>
+#include <functional>
+#include <string>
+#include <tuple>
+#include <utility>
+#include <variant>
+#include <vector>
+
+#include "src/tint/utils/containers/vector.h"
+#include "src/tint/utils/math/crc32.h"
+
+namespace tint::utils {
+namespace detail {
+
+/// Helper for obtaining a seed bias value for HashCombine with a bit-width
+/// dependent on the size of size_t.
+template <int SIZE_OF_SIZE_T>
+struct HashCombineOffset {};
+
+/// Specialization of HashCombineOffset for size_t == 4.
+template <>
+struct HashCombineOffset<4> {
+ /// @returns the seed bias value for HashCombine()
+ static constexpr inline uint32_t value() {
+ constexpr uint32_t base = 0x7f4a7c16;
+#ifdef TINT_HASH_SEED
+ return base ^ static_cast<uint32_t>(TINT_HASH_SEED);
+#endif
+ return base;
+ }
+};
+
+/// Specialization of HashCombineOffset for size_t == 8.
+template <>
+struct HashCombineOffset<8> {
+ /// @returns the seed bias value for HashCombine()
+ static constexpr inline uint64_t value() {
+ constexpr uint64_t base = 0x9e3779b97f4a7c16;
+#ifdef TINT_HASH_SEED
+ return base ^ static_cast<uint64_t>(TINT_HASH_SEED);
+#endif
+ return base;
+ }
+};
+
+} // namespace detail
+
+/// Forward declarations (see below)
+template <typename... ARGS>
+size_t Hash(const ARGS&... values);
+
+template <typename... ARGS>
+size_t HashCombine(size_t hash, const ARGS&... values);
+
+/// A STL-compatible hasher that does a more thorough job than most implementations of std::hash.
+/// Hasher has been optimized for a better quality hash at the expense of increased computation
+/// costs.
+template <typename T>
+struct Hasher {
+ /// @param value the value to hash
+ /// @returns a hash of the value
+ size_t operator()(const T& value) const { return std::hash<T>()(value); }
+};
+
+/// Hasher specialization for pointers
+/// std::hash<T*> typically uses a reinterpret of the pointer to a size_t.
+/// As most pointers a 4 or 16 byte aligned, this usually results in the LSBs of the hash being 0,
+/// resulting in bad hashes for hashtables. This implementation mixes up those LSBs.
+template <typename T>
+struct Hasher<T*> {
+ /// @param ptr the pointer to hash
+ /// @returns a hash of the pointer
+ size_t operator()(T* ptr) const {
+ auto hash = std::hash<T*>()(ptr);
+#ifdef TINT_HASH_SEED
+ hash ^= static_cast<uint32_t>(TINT_HASH_SEED);
+#endif
+ return hash ^ (hash >> 4);
+ }
+};
+
+/// Hasher specialization for std::vector
+template <typename T>
+struct Hasher<std::vector<T>> {
+ /// @param vector the vector to hash
+ /// @returns a hash of the vector
+ size_t operator()(const std::vector<T>& vector) const {
+ auto hash = Hash(vector.size());
+ for (auto& el : vector) {
+ hash = HashCombine(hash, el);
+ }
+ return hash;
+ }
+};
+
+/// Hasher specialization for utils::Vector
+template <typename T, size_t N>
+struct Hasher<utils::Vector<T, N>> {
+ /// @param vector the Vector to hash
+ /// @returns a hash of the Vector
+ size_t operator()(const utils::Vector<T, N>& vector) const {
+ auto hash = Hash(vector.Length());
+ for (auto& el : vector) {
+ hash = HashCombine(hash, el);
+ }
+ return hash;
+ }
+};
+
+/// Hasher specialization for utils::VectorRef
+template <typename T>
+struct Hasher<utils::VectorRef<T>> {
+ /// @param vector the VectorRef reference to hash
+ /// @returns a hash of the Vector
+ size_t operator()(const utils::VectorRef<T>& vector) const {
+ auto hash = Hash(vector.Length());
+ for (auto& el : vector) {
+ hash = HashCombine(hash, el);
+ }
+ return hash;
+ }
+};
+
+/// Hasher specialization for std::tuple
+template <typename... TYPES>
+struct Hasher<std::tuple<TYPES...>> {
+ /// @param tuple the tuple to hash
+ /// @returns a hash of the tuple
+ size_t operator()(const std::tuple<TYPES...>& tuple) const {
+ return std::apply(Hash<TYPES...>, tuple);
+ }
+};
+
+/// Hasher specialization for std::pair
+template <typename A, typename B>
+struct Hasher<std::pair<A, B>> {
+ /// @param tuple the tuple to hash
+ /// @returns a hash of the tuple
+ size_t operator()(const std::pair<A, B>& tuple) const { return std::apply(Hash<A, B>, tuple); }
+};
+
+/// Hasher specialization for std::variant
+template <typename... TYPES>
+struct Hasher<std::variant<TYPES...>> {
+ /// @param variant the variant to hash
+ /// @returns a hash of the tuple
+ size_t operator()(const std::variant<TYPES...>& variant) const {
+ return std::visit([](auto&& val) { return Hash(val); }, variant);
+ }
+};
+
+/// Hasher specialization for std::string, which also supports hashing of const char* and
+/// std::string_view without first constructing a std::string.
+template <>
+struct Hasher<std::string> {
+ /// @param str the string to hash
+ /// @returns a hash of the string
+ size_t operator()(const std::string& str) const {
+ return std::hash<std::string_view>()(std::string_view(str));
+ }
+
+ /// @param str the string to hash
+ /// @returns a hash of the string
+ size_t operator()(const char* str) const {
+ return std::hash<std::string_view>()(std::string_view(str));
+ }
+
+ /// @param str the string to hash
+ /// @returns a hash of the string
+ size_t operator()(const std::string_view& str) const {
+ return std::hash<std::string_view>()(str);
+ }
+};
+
+/// @returns a hash of the variadic list of arguments.
+/// The returned hash is dependent on the order of the arguments.
+template <typename... ARGS>
+size_t Hash(const ARGS&... args) {
+ if constexpr (sizeof...(ARGS) == 0) {
+ return 0;
+ } else if constexpr (sizeof...(ARGS) == 1) {
+ using T = std::tuple_element_t<0, std::tuple<ARGS...>>;
+ return Hasher<T>()(args...);
+ } else {
+ size_t hash = 102931; // seed with an arbitrary prime
+ return HashCombine(hash, args...);
+ }
+}
+
+/// @returns a hash of the variadic list of arguments.
+/// The returned hash is dependent on the order of the arguments.
+template <typename... ARGS>
+size_t HashCombine(size_t hash, const ARGS&... values) {
+ constexpr size_t offset = utils::detail::HashCombineOffset<sizeof(size_t)>::value();
+ ((hash ^= Hash(values) + (offset ^ (hash >> 2))), ...);
+ return hash;
+}
+
+/// A STL-compatible equal_to implementation that specializes for types.
+template <typename T>
+struct EqualTo {
+ /// @param lhs the left hand side value
+ /// @param rhs the right hand side value
+ /// @returns true if the two values are equal
+ constexpr bool operator()(const T& lhs, const T& rhs) const {
+ return std::equal_to<T>()(lhs, rhs);
+ }
+};
+
+/// A specialization for EqualTo for std::string, which supports additional comparision with
+/// std::string_view and const char*.
+template <>
+struct EqualTo<std::string> {
+ /// @param lhs the left hand side value
+ /// @param rhs the right hand side value
+ /// @returns true if the two values are equal
+ bool operator()(const std::string& lhs, const std::string& rhs) const { return lhs == rhs; }
+
+ /// @param lhs the left hand side value
+ /// @param rhs the right hand side value
+ /// @returns true if the two values are equal
+ bool operator()(const std::string& lhs, const char* rhs) const { return lhs == rhs; }
+
+ /// @param lhs the left hand side value
+ /// @param rhs the right hand side value
+ /// @returns true if the two values are equal
+ bool operator()(const std::string& lhs, std::string_view rhs) const { return lhs == rhs; }
+
+ /// @param lhs the left hand side value
+ /// @param rhs the right hand side value
+ /// @returns true if the two values are equal
+ bool operator()(const char* lhs, const std::string& rhs) const { return lhs == rhs; }
+
+ /// @param lhs the left hand side value
+ /// @param rhs the right hand side value
+ /// @returns true if the two values are equal
+ bool operator()(std::string_view lhs, const std::string& rhs) const { return lhs == rhs; }
+};
+
+/// Wrapper for a hashable type enabling the wrapped value to be used as a key
+/// for an unordered_map or unordered_set.
+template <typename T>
+struct UnorderedKeyWrapper {
+ /// The wrapped value
+ T value;
+ /// The hash of value
+ size_t hash;
+
+ /// Constructor
+ /// @param v the value to wrap
+ explicit UnorderedKeyWrapper(const T& v) : value(v), hash(Hash(v)) {}
+
+ /// Move constructor
+ /// @param v the value to wrap
+ explicit UnorderedKeyWrapper(T&& v) : value(std::move(v)), hash(Hash(value)) {}
+
+ /// @returns true if this wrapper comes before other
+ /// @param other the RHS of the operator
+ bool operator<(const UnorderedKeyWrapper& other) const { return hash < other.hash; }
+
+ /// @returns true if this wrapped value is equal to the other wrapped value
+ /// @param other the RHS of the operator
+ bool operator==(const UnorderedKeyWrapper& other) const { return value == other.value; }
+};
+
+} // namespace tint::utils
+
+namespace std {
+
+/// Custom std::hash specialization for tint::utils::UnorderedKeyWrapper
+template <typename T>
+class hash<tint::utils::UnorderedKeyWrapper<T>> {
+ public:
+ /// @param w the UnorderedKeyWrapper
+ /// @return the hash value
+ inline std::size_t operator()(const tint::utils::UnorderedKeyWrapper<T>& w) const {
+ return w.hash;
+ }
+};
+
+} // namespace std
+
+#endif // SRC_TINT_UTILS_MATH_HASH_H_
diff --git a/src/tint/utils/math/hash_test.cc b/src/tint/utils/math/hash_test.cc
new file mode 100644
index 0000000..7083170
--- /dev/null
+++ b/src/tint/utils/math/hash_test.cc
@@ -0,0 +1,128 @@
+// Copyright 2021 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "src/tint/utils/math/hash.h"
+
+#include <string>
+#include <tuple>
+#include <unordered_map>
+
+#include "gtest/gtest.h"
+#include "src/tint/utils/containers/vector.h"
+
+namespace tint::utils {
+namespace {
+
+TEST(HashTests, Basic) {
+ EXPECT_EQ(Hash(123), Hash(123));
+ EXPECT_EQ(Hash(123, 456), Hash(123, 456));
+ EXPECT_EQ(Hash(123, 456, false), Hash(123, 456, false));
+ EXPECT_EQ(Hash(std::string("hello")), Hash(std::string("hello")));
+}
+
+TEST(HashTests, StdVector) {
+ EXPECT_EQ(Hash(std::vector<int>({})), Hash(std::vector<int>({})));
+ EXPECT_EQ(Hash(std::vector<int>({1, 2, 3})), Hash(std::vector<int>({1, 2, 3})));
+}
+
+TEST(HashTests, TintVector) {
+ EXPECT_EQ(Hash(Vector<int, 0>({})), Hash(Vector<int, 0>({})));
+ EXPECT_EQ(Hash(Vector<int, 0>({1, 2, 3})), Hash(Vector<int, 0>({1, 2, 3})));
+ EXPECT_EQ(Hash(Vector<int, 3>({1, 2, 3})), Hash(Vector<int, 4>({1, 2, 3})));
+ EXPECT_EQ(Hash(Vector<int, 3>({1, 2, 3})), Hash(Vector<int, 2>({1, 2, 3})));
+}
+
+TEST(HashTests, TintVectorRef) {
+ EXPECT_EQ(Hash(VectorRef<int>(Vector<int, 0>({}))), Hash(VectorRef<int>(Vector<int, 0>({}))));
+ EXPECT_EQ(Hash(VectorRef<int>(Vector<int, 0>({1, 2, 3}))),
+ Hash(VectorRef<int>(Vector<int, 0>({1, 2, 3}))));
+ EXPECT_EQ(Hash(VectorRef<int>(Vector<int, 3>({1, 2, 3}))),
+ Hash(VectorRef<int>(Vector<int, 4>({1, 2, 3}))));
+ EXPECT_EQ(Hash(VectorRef<int>(Vector<int, 3>({1, 2, 3}))),
+ Hash(VectorRef<int>(Vector<int, 2>({1, 2, 3}))));
+
+ EXPECT_EQ(Hash(VectorRef<int>(Vector<int, 0>({}))), Hash(Vector<int, 0>({})));
+ EXPECT_EQ(Hash(VectorRef<int>(Vector<int, 0>({1, 2, 3}))), Hash(Vector<int, 0>({1, 2, 3})));
+ EXPECT_EQ(Hash(VectorRef<int>(Vector<int, 3>({1, 2, 3}))), Hash(Vector<int, 4>({1, 2, 3})));
+ EXPECT_EQ(Hash(VectorRef<int>(Vector<int, 3>({1, 2, 3}))), Hash(Vector<int, 2>({1, 2, 3})));
+}
+
+TEST(HashTests, Tuple) {
+ EXPECT_EQ(Hash(std::make_tuple(1)), Hash(std::make_tuple(1)));
+ EXPECT_EQ(Hash(std::make_tuple(1, 2, 3)), Hash(std::make_tuple(1, 2, 3)));
+}
+
+TEST(HashTests, UnorderedKeyWrapper) {
+ using W = UnorderedKeyWrapper<std::vector<int>>;
+
+ std::unordered_map<W, int> m;
+
+ m.emplace(W{{1, 2}}, -1);
+ EXPECT_EQ(m.size(), 1u);
+ EXPECT_EQ(m[W({1, 2})], -1);
+
+ m.emplace(W{{3, 2}}, 1);
+ EXPECT_EQ(m.size(), 2u);
+ EXPECT_EQ(m[W({3, 2})], 1);
+ EXPECT_EQ(m[W({1, 2})], -1);
+
+ m.emplace(W{{100}}, 100);
+ EXPECT_EQ(m.size(), 3u);
+ EXPECT_EQ(m[W({100})], 100);
+ EXPECT_EQ(m[W({3, 2})], 1);
+ EXPECT_EQ(m[W({1, 2})], -1);
+
+ // Reversed vector element order
+ EXPECT_EQ(m[W({2, 3})], 0);
+ EXPECT_EQ(m[W({2, 1})], 0);
+}
+
+TEST(EqualTo, String) {
+ std::string str_a = "hello";
+ std::string str_b = "world";
+ const char* cstr_a = "hello";
+ const char* cstr_b = "world";
+ std::string_view sv_a = "hello";
+ std::string_view sv_b = "world";
+ EXPECT_TRUE(EqualTo<std::string>()(str_a, str_a));
+ EXPECT_TRUE(EqualTo<std::string>()(str_a, cstr_a));
+ EXPECT_TRUE(EqualTo<std::string>()(str_a, sv_a));
+ EXPECT_TRUE(EqualTo<std::string>()(str_a, str_a));
+ EXPECT_TRUE(EqualTo<std::string>()(cstr_a, str_a));
+ EXPECT_TRUE(EqualTo<std::string>()(sv_a, str_a));
+
+ EXPECT_FALSE(EqualTo<std::string>()(str_a, str_b));
+ EXPECT_FALSE(EqualTo<std::string>()(str_a, cstr_b));
+ EXPECT_FALSE(EqualTo<std::string>()(str_a, sv_b));
+ EXPECT_FALSE(EqualTo<std::string>()(str_a, str_b));
+ EXPECT_FALSE(EqualTo<std::string>()(cstr_a, str_b));
+ EXPECT_FALSE(EqualTo<std::string>()(sv_a, str_b));
+
+ EXPECT_FALSE(EqualTo<std::string>()(str_b, str_a));
+ EXPECT_FALSE(EqualTo<std::string>()(str_b, cstr_a));
+ EXPECT_FALSE(EqualTo<std::string>()(str_b, sv_a));
+ EXPECT_FALSE(EqualTo<std::string>()(str_b, str_a));
+ EXPECT_FALSE(EqualTo<std::string>()(cstr_b, str_a));
+ EXPECT_FALSE(EqualTo<std::string>()(sv_b, str_a));
+
+ EXPECT_TRUE(EqualTo<std::string>()(str_b, str_b));
+ EXPECT_TRUE(EqualTo<std::string>()(str_b, cstr_b));
+ EXPECT_TRUE(EqualTo<std::string>()(str_b, sv_b));
+ EXPECT_TRUE(EqualTo<std::string>()(str_b, str_b));
+ EXPECT_TRUE(EqualTo<std::string>()(cstr_b, str_b));
+ EXPECT_TRUE(EqualTo<std::string>()(sv_b, str_b));
+}
+
+} // namespace
+} // namespace tint::utils
diff --git a/src/tint/utils/math/math.h b/src/tint/utils/math/math.h
new file mode 100644
index 0000000..59bd36c
--- /dev/null
+++ b/src/tint/utils/math/math.h
@@ -0,0 +1,103 @@
+// Copyright 2021 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SRC_TINT_UTILS_MATH_MATH_H_
+#define SRC_TINT_UTILS_MATH_MATH_H_
+
+#include <stdint.h>
+
+#include <string>
+#include <type_traits>
+
+namespace tint::utils {
+
+/// @param alignment the next multiple to round `value` to
+/// @param value the value to round to the next multiple of `alignment`
+/// @return `value` rounded to the next multiple of `alignment`
+/// @note `alignment` must be positive. An alignment of zero will cause a DBZ.
+template <typename T>
+inline constexpr T RoundUp(T alignment, T value) {
+ return ((value + alignment - 1) / alignment) * alignment;
+}
+
+/// @param value the value to check whether it is a power-of-two
+/// @returns true if `value` is a power-of-two
+/// @note `value` must be positive if `T` is signed
+template <typename T>
+inline constexpr bool IsPowerOfTwo(T value) {
+ return (value & (value - 1)) == 0;
+}
+
+/// @param value the input value
+/// @returns the base-2 logarithm of @p value
+inline constexpr uint32_t Log2(uint64_t value) {
+#if defined(__clang__) || defined(__GNUC__)
+ return 63 - static_cast<uint32_t>(__builtin_clzll(value));
+#elif defined(_MSC_VER) && !defined(__clang__) && __cplusplus >= 202002L // MSVC and C++20+
+ // note: std::is_constant_evaluated() added in C++20
+ // required here as _BitScanReverse64 is not constexpr
+ if (!std::is_constant_evaluated()) {
+ // NOLINTNEXTLINE(runtime/int)
+ if constexpr (sizeof(unsigned long) == 8) { // 64-bit
+ // NOLINTNEXTLINE(runtime/int)
+ unsigned long first_bit_index = 0;
+ _BitScanReverse64(&first_bit_index, value);
+ return first_bit_index;
+ } else { // 32-bit
+ // NOLINTNEXTLINE(runtime/int)
+ unsigned long first_bit_index = 0;
+ if (_BitScanReverse(&first_bit_index, value >> 32)) {
+ return first_bit_index + 32;
+ }
+ _BitScanReverse(&first_bit_index, value & 0xffffffff);
+ return first_bit_index;
+ }
+ }
+#endif
+
+ // Non intrinsic (slow) path. Supports constexpr evaluation.
+ for (uint64_t clz = 0; clz < 64; clz++) {
+ uint64_t bit = 63 - clz;
+ if (value & (static_cast<uint64_t>(1u) << bit)) {
+ return static_cast<uint32_t>(bit);
+ }
+ }
+ return 64;
+}
+
+/// @param value the input value
+/// @returns the next power of two number greater or equal to @p value
+inline constexpr uint64_t NextPowerOfTwo(uint64_t value) {
+ if (value <= 1) {
+ return 1;
+ } else {
+ return static_cast<uint64_t>(1) << (Log2(value - 1) + 1);
+ }
+}
+
+/// @param value the input value
+/// @returns the largest power of two that `value` is a multiple of
+template <typename T>
+inline std::enable_if_t<std::is_unsigned<T>::value, T> MaxAlignOf(T value) {
+ T pot = 1;
+ while (value && ((value & 1u) == 0)) {
+ pot <<= 1;
+ value >>= 1;
+ }
+ return pot;
+}
+
+} // namespace tint::utils
+
+#endif // SRC_TINT_UTILS_MATH_MATH_H_
diff --git a/src/tint/utils/math/math_test.cc b/src/tint/utils/math/math_test.cc
new file mode 100644
index 0000000..8da26ba
--- /dev/null
+++ b/src/tint/utils/math/math_test.cc
@@ -0,0 +1,145 @@
+// Copyright 2021 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "src/tint/utils/math/math.h"
+
+#include "gtest/gtest.h"
+
+namespace tint::utils {
+namespace {
+
+TEST(MathTests, RoundUp) {
+ EXPECT_EQ(RoundUp(1, 0), 0);
+ EXPECT_EQ(RoundUp(1, 1), 1);
+ EXPECT_EQ(RoundUp(1, 2), 2);
+
+ EXPECT_EQ(RoundUp(1, 1), 1);
+ EXPECT_EQ(RoundUp(2, 1), 2);
+ EXPECT_EQ(RoundUp(3, 1), 3);
+ EXPECT_EQ(RoundUp(4, 1), 4);
+
+ EXPECT_EQ(RoundUp(1, 2), 2);
+ EXPECT_EQ(RoundUp(2, 2), 2);
+ EXPECT_EQ(RoundUp(3, 2), 3);
+ EXPECT_EQ(RoundUp(4, 2), 4);
+
+ EXPECT_EQ(RoundUp(1, 3), 3);
+ EXPECT_EQ(RoundUp(2, 3), 4);
+ EXPECT_EQ(RoundUp(3, 3), 3);
+ EXPECT_EQ(RoundUp(4, 3), 4);
+
+ EXPECT_EQ(RoundUp(1, 4), 4);
+ EXPECT_EQ(RoundUp(2, 4), 4);
+ EXPECT_EQ(RoundUp(3, 4), 6);
+ EXPECT_EQ(RoundUp(4, 4), 4);
+}
+
+TEST(MathTests, IsPowerOfTwo) {
+ EXPECT_EQ(IsPowerOfTwo(1), true);
+ EXPECT_EQ(IsPowerOfTwo(2), true);
+ EXPECT_EQ(IsPowerOfTwo(3), false);
+ EXPECT_EQ(IsPowerOfTwo(4), true);
+ EXPECT_EQ(IsPowerOfTwo(5), false);
+ EXPECT_EQ(IsPowerOfTwo(6), false);
+ EXPECT_EQ(IsPowerOfTwo(7), false);
+ EXPECT_EQ(IsPowerOfTwo(8), true);
+ EXPECT_EQ(IsPowerOfTwo(9), false);
+}
+
+TEST(MathTests, Log2) {
+ EXPECT_EQ(Log2(1), 0u);
+ EXPECT_EQ(Log2(2), 1u);
+ EXPECT_EQ(Log2(3), 1u);
+ EXPECT_EQ(Log2(4), 2u);
+ EXPECT_EQ(Log2(5), 2u);
+ EXPECT_EQ(Log2(6), 2u);
+ EXPECT_EQ(Log2(7), 2u);
+ EXPECT_EQ(Log2(8), 3u);
+ EXPECT_EQ(Log2(9), 3u);
+ EXPECT_EQ(Log2(0x7fffffffu), 30u);
+ EXPECT_EQ(Log2(0x80000000u), 31u);
+ EXPECT_EQ(Log2(0x80000001u), 31u);
+ EXPECT_EQ(Log2(0x7fffffffffffffffu), 62u);
+ EXPECT_EQ(Log2(0x8000000000000000u), 63u);
+
+ static_assert(Log2(1) == 0u);
+ static_assert(Log2(2) == 1u);
+ static_assert(Log2(3) == 1u);
+ static_assert(Log2(4) == 2u);
+ static_assert(Log2(5) == 2u);
+ static_assert(Log2(6) == 2u);
+ static_assert(Log2(7) == 2u);
+ static_assert(Log2(8) == 3u);
+ static_assert(Log2(9) == 3u);
+ static_assert(Log2(0x7fffffffu) == 30u);
+ static_assert(Log2(0x80000000u) == 31u);
+ static_assert(Log2(0x80000001u) == 31u);
+ static_assert(Log2(0x7fffffffffffffffu) == 62u);
+ static_assert(Log2(0x8000000000000000u) == 63u);
+}
+
+TEST(MathTests, NextPowerOfTwo) {
+ EXPECT_EQ(NextPowerOfTwo(0), 1u);
+ EXPECT_EQ(NextPowerOfTwo(1), 1u);
+ EXPECT_EQ(NextPowerOfTwo(2), 2u);
+ EXPECT_EQ(NextPowerOfTwo(3), 4u);
+ EXPECT_EQ(NextPowerOfTwo(4), 4u);
+ EXPECT_EQ(NextPowerOfTwo(5), 8u);
+ EXPECT_EQ(NextPowerOfTwo(6), 8u);
+ EXPECT_EQ(NextPowerOfTwo(7), 8u);
+ EXPECT_EQ(NextPowerOfTwo(8), 8u);
+ EXPECT_EQ(NextPowerOfTwo(9), 16u);
+ EXPECT_EQ(NextPowerOfTwo(0x7fffffffu), 0x80000000u);
+ EXPECT_EQ(NextPowerOfTwo(0x80000000u), 0x80000000u);
+ EXPECT_EQ(NextPowerOfTwo(0x80000001u), 0x100000000u);
+ EXPECT_EQ(NextPowerOfTwo(0x7fffffffffffffffu), 0x8000000000000000u);
+
+ static_assert(NextPowerOfTwo(0) == 1u);
+ static_assert(NextPowerOfTwo(1) == 1u);
+ static_assert(NextPowerOfTwo(2) == 2u);
+ static_assert(NextPowerOfTwo(3) == 4u);
+ static_assert(NextPowerOfTwo(4) == 4u);
+ static_assert(NextPowerOfTwo(5) == 8u);
+ static_assert(NextPowerOfTwo(6) == 8u);
+ static_assert(NextPowerOfTwo(7) == 8u);
+ static_assert(NextPowerOfTwo(8) == 8u);
+ static_assert(NextPowerOfTwo(9) == 16u);
+ static_assert(NextPowerOfTwo(0x7fffffffu) == 0x80000000u);
+ static_assert(NextPowerOfTwo(0x80000000u) == 0x80000000u);
+ static_assert(NextPowerOfTwo(0x80000001u) == 0x100000000u);
+ static_assert(NextPowerOfTwo(0x7fffffffffffffffu) == 0x8000000000000000u);
+}
+
+TEST(MathTests, MaxAlignOf) {
+ EXPECT_EQ(MaxAlignOf(0u), 1u);
+ EXPECT_EQ(MaxAlignOf(1u), 1u);
+ EXPECT_EQ(MaxAlignOf(2u), 2u);
+ EXPECT_EQ(MaxAlignOf(3u), 1u);
+ EXPECT_EQ(MaxAlignOf(4u), 4u);
+ EXPECT_EQ(MaxAlignOf(5u), 1u);
+ EXPECT_EQ(MaxAlignOf(6u), 2u);
+ EXPECT_EQ(MaxAlignOf(7u), 1u);
+ EXPECT_EQ(MaxAlignOf(8u), 8u);
+ EXPECT_EQ(MaxAlignOf(9u), 1u);
+ EXPECT_EQ(MaxAlignOf(10u), 2u);
+ EXPECT_EQ(MaxAlignOf(11u), 1u);
+ EXPECT_EQ(MaxAlignOf(12u), 4u);
+ EXPECT_EQ(MaxAlignOf(13u), 1u);
+ EXPECT_EQ(MaxAlignOf(14u), 2u);
+ EXPECT_EQ(MaxAlignOf(15u), 1u);
+ EXPECT_EQ(MaxAlignOf(16u), 16u);
+}
+
+} // namespace
+} // namespace tint::utils
