Castable: Optimizations using bloomfilters
Calculate a hashcode for each TypeInfo, use these hashcodes to quickly
eliminate full base class walks for As() and Is(). Use the hashcodes to
optimize IsAnyOf() calls where the result is false.
Benchmarks:
A: base.bench
B: new.bench
Test name | Δ (A → B) | % (A → B)
--------------------------------------+--------------+-----------
ParseWGSL/"particles.wgsl" | -78.84µs | -3.2%
GenerateWGSL/"particles.wgsl" | -11.264µs | -5.8%
GenerateGLSL/"particles.wgsl" | -2.610127ms | -7.2%
GenerateMSL/"simple_compute.wgsl" | -41.187µs | -7.2%
GenerateMSL/"particles.wgsl" | -818.689µs | -7.2%
GenerateGLSL/"simple_compute.wgsl" | -48.362µs | -7.4%
GenerateGLSL/"simple_vertex.wgsl" | -49.992µs | -7.7%
GenerateSPIRV/"simple_compute.wgsl" | -42.869µs | -7.8%
GenerateSPIRV/"particles.wgsl" | -835.423µs | -7.9%
GenerateSPIRV/"simple_fragment.wgsl" | -33.868µs | -8.1%
GenerateGLSL/"simple_fragment.wgsl" | -51.368µs | -8.2%
GenerateSPIRV/"simple_vertex.wgsl" | -39.096µs | -8.3%
GenerateHLSL/"particles.wgsl" | -1.437747ms | -8.3%
GenerateMSL/"simple_vertex.wgsl" | -57.232µs | -8.5%
GenerateHLSL/"simple_compute.wgsl" | -85.981µs | -8.9%
GenerateHLSL/"simple_fragment.wgsl" | -73.095µs | -9.2%
GenerateMSL/"simple_fragment.wgsl" | -61.257µs | -9.3%
GenerateHLSL/"simple_vertex.wgsl" | -76.661µs | -9.4%
Change-Id: Idb03bf871b08274b5b52ef55e41450ed3448a60f
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/76960
Reviewed-by: David Neto <dneto@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
Kokoro: Ben Clayton <bclayton@google.com>
diff --git a/src/BUILD.gn b/src/BUILD.gn
index c12abeb..df04c73 100644
--- a/src/BUILD.gn
+++ b/src/BUILD.gn
@@ -493,6 +493,7 @@
"transform/wrap_arrays_in_structs.h",
"transform/zero_init_workgroup_memory.cc",
"transform/zero_init_workgroup_memory.h",
+ "utils/crc32.h",
"utils/enum_set.h",
"utils/hash.h",
"utils/map.h",
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 23efeb4..2b211d6 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -411,6 +411,7 @@
sem/vector_type.h
sem/void_type.cc
sem/void_type.h
+ utils/crc32.h
utils/enum_set.h
utils/hash.h
utils/map.h
@@ -754,6 +755,7 @@
test_main.cc
traits_test.cc
transform/transform_test.cc
+ utils/crc32_test.cc
utils/defer_test.cc
utils/enum_set_test.cc
utils/hash_test.cc
diff --git a/src/castable.cc b/src/castable.cc
index 7cab369..e63981f 100644
--- a/src/castable.cc
+++ b/src/castable.cc
@@ -22,15 +22,8 @@
const TypeInfo detail::TypeInfoOf<CastableBase>::info{
nullptr,
"CastableBase",
+ tint::TypeInfo::HashCodeOf<CastableBase>(),
+ tint::TypeInfo::HashCodeOf<CastableBase>(),
};
-bool TypeInfo::Is(const TypeInfo& typeinfo) const {
- for (auto* ti = this; ti != nullptr; ti = ti->base) {
- if (ti == &typeinfo) {
- return true;
- }
- }
- return false;
-}
-
} // namespace tint
diff --git a/src/castable.h b/src/castable.h
index 1b30955..280cc17 100644
--- a/src/castable.h
+++ b/src/castable.h
@@ -15,9 +15,12 @@
#ifndef SRC_CASTABLE_H_
#define SRC_CASTABLE_H_
+#include <stdint.h>
+#include <functional>
#include <utility>
#include "src/traits.h"
+#include "src/utils/crc32.h"
#if defined(__clang__)
/// Temporarily disable certain warnings when using Castable API
@@ -41,13 +44,14 @@
namespace tint {
+// Forward declaration
+class CastableBase;
+
namespace detail {
template <typename T>
struct TypeInfoOf;
-} // namespace detail
-// Forward declaration
-class CastableBase;
+} // namespace detail
/// Helper macro to instantiate the TypeInfo<T> template for `CLASS`.
#define TINT_INSTANTIATE_TYPEINFO(CLASS) \
@@ -56,20 +60,77 @@
const tint::TypeInfo tint::detail::TypeInfoOf<CLASS>::info{ \
&tint::detail::TypeInfoOf<CLASS::TrueBase>::info, \
#CLASS, \
+ tint::TypeInfo::HashCodeOf<CLASS>(), \
+ tint::TypeInfo::CombinedHashCodeOf<CLASS>(), \
}; \
TINT_CASTABLE_POP_DISABLE_WARNINGS()
+/// Bit flags that can be passed to the template parameter `FLAGS` of Is() and
+/// As().
+enum CastFlags {
+ /// Disables the static_assert() inside Is(), that compile-time-verifies that
+ /// the cast is possible. This flag may be useful for highly-generic template
+ /// code that needs to compile for template permutations that generate
+ /// impossible casts.
+ kDontErrorOnImpossibleCast = 1,
+};
+
/// TypeInfo holds type information for a Castable type.
struct TypeInfo {
- /// The base class of this type.
+ /// The type of a hash code
+ using HashCode = uint64_t;
+
+ /// The base class of this type
const TypeInfo* base;
/// The type name
const char* name;
+ /// The type hash code
+ const HashCode hashcode;
+ /// The type hash code or'd with the base class' combined hash code
+ const HashCode combined_hashcode;
/// @param type the test type info
/// @returns true if the class with this TypeInfo is of, or derives from the
/// class with the given TypeInfo.
- bool Is(const tint::TypeInfo& type) const;
+ inline bool Is(const tint::TypeInfo* type) const {
+ // Optimization: Check whether the all the bits of the type's hashcode can
+ // be found in the combined_hashcode. If a single bit is missing, then we
+ // can quickly tell that that this TypeInfo does not derive from `type`.
+ if ((combined_hashcode & type->hashcode) != type->hashcode) {
+ return false;
+ }
+
+ // Walk the base types, starting with this TypeInfo, to see if any of the
+ // pointers match `type`.
+ for (auto* ti = this; ti != nullptr; ti = ti->base) {
+ if (ti == type) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /// @returns true if `type` derives from the class `TO`
+ /// @param type the object type to test from, which must be, or derive from
+ /// type `FROM`.
+ /// @see CastFlags
+ template <typename TO, typename FROM, int FLAGS = 0>
+ static inline bool Is(const tint::TypeInfo* type) {
+ constexpr const bool downcast = std::is_base_of<FROM, TO>::value;
+ constexpr const bool upcast = std::is_base_of<TO, FROM>::value;
+ constexpr const bool nocast = std::is_same<FROM, TO>::value;
+ constexpr const bool assert_is_castable =
+ (FLAGS & kDontErrorOnImpossibleCast) == 0;
+
+ static_assert(upcast || downcast || nocast || !assert_is_castable,
+ "impossible cast");
+
+ if (upcast || nocast) {
+ return true;
+ }
+
+ return type->Is(&Of<std::remove_const_t<TO>>());
+ }
/// @returns the static TypeInfo for the type T
template <typename T>
@@ -77,6 +138,36 @@
using NO_CV = typename std::remove_cv<T>::type;
return detail::TypeInfoOf<NO_CV>::info;
}
+
+ /// @returns a compile-time hashcode for the type `T`.
+ /// @note the returned hashcode will have at most 2 bits set, as the hashes
+ /// are expected to be used in bloom-filters which will quickly saturate when
+ /// multiple hashcodes are bitwise-or'd together.
+ template <typename T>
+ static constexpr HashCode HashCodeOf() {
+ /// Use the compiler's "pretty" function name, which includes the template
+ /// type, to obtain a unique hash value.
+#ifdef _MSC_VER
+ constexpr uint32_t crc = utils::CRC32(__FUNCSIG__);
+#else
+ constexpr uint32_t crc = utils::CRC32(__PRETTY_FUNCTION__);
+#endif
+ constexpr uint32_t bit_a = (crc & 63);
+ constexpr uint32_t bit_b = ((crc >> 6) & 63);
+ return (static_cast<HashCode>(1) << bit_a) |
+ (static_cast<HashCode>(1) << bit_b);
+ }
+
+ /// @returns the hashcode of the given type, bitwise-or'd with the hashcodes
+ /// of all base classes.
+ template <typename T>
+ static constexpr HashCode CombinedHashCodeOf() {
+ if constexpr (std::is_same_v<T, CastableBase>) {
+ return HashCodeOf<CastableBase>();
+ } else {
+ return HashCodeOf<T>() | CombinedHashCodeOf<typename T::TrueBase>();
+ }
+ }
};
namespace detail {
@@ -100,40 +191,16 @@
} // namespace detail
-/// Bit flags that can be passed to the template parameter `FLAGS` of Is() and
-/// As().
-enum CastFlags {
- /// Disables the static_assert() inside Is(), that compile-time-verifies that
- /// the cast is possible. This flag may be useful for highly-generic template
- /// code that needs to compile for template permutations that generate
- /// impossible casts.
- kDontErrorOnImpossibleCast = 1,
-};
-
/// @returns true if `obj` is a valid pointer, and is of, or derives from the
/// class `TO`
/// @param obj the object to test from
/// @see CastFlags
template <typename TO, int FLAGS = 0, typename FROM = detail::Infer>
inline bool Is(FROM* obj) {
- constexpr const bool downcast = std::is_base_of<FROM, TO>::value;
- constexpr const bool upcast = std::is_base_of<TO, FROM>::value;
- constexpr const bool nocast = std::is_same<FROM, TO>::value;
- constexpr const bool assert_is_castable =
- (FLAGS & kDontErrorOnImpossibleCast) == 0;
-
- static_assert(upcast || downcast || nocast || !assert_is_castable,
- "impossible cast");
-
if (obj == nullptr) {
return false;
}
-
- if (upcast || nocast) {
- return true;
- }
-
- return obj->TypeInfo().Is(TypeInfo::Of<std::remove_const_t<TO>>());
+ return TypeInfo::Is<TO, FROM, FLAGS>(&obj->TypeInfo());
}
/// @returns true if `obj` is a valid pointer, and is of, or derives from the
@@ -147,19 +214,8 @@
typename FROM = detail::Infer,
typename Pred = detail::Infer>
inline bool Is(FROM* obj, Pred&& pred) {
- constexpr const bool downcast = std::is_base_of<FROM, TO>::value;
- constexpr const bool upcast = std::is_base_of<TO, FROM>::value;
- constexpr const bool nocast = std::is_same<FROM, TO>::value;
- static_assert(upcast || downcast || nocast, "impossible cast");
-
- if (obj == nullptr) {
- return false;
- }
-
- bool is_type = upcast || nocast ||
- obj->TypeInfo().Is(TypeInfo::Of<std::remove_const_t<TO>>());
-
- return is_type && pred(static_cast<std::add_const_t<TO>*>(obj));
+ return Is<TO, FLAGS, FROM>(obj) &&
+ pred(static_cast<std::add_const_t<TO>*>(obj));
}
/// @returns true if `obj` is of, or derives from any of the `TO`
@@ -167,7 +223,20 @@
/// @param obj the object to cast from
template <typename... TO, typename FROM>
inline bool IsAnyOf(FROM* obj) {
- return detail::IsAnyOf<TO...>::Exec(obj);
+ if (!obj) {
+ return false;
+ }
+ // Optimization: Compare the object's combined_hashcode to the bitwise-or of
+ // all the tested type's hashcodes. If there's no intersection of bits in the
+ // two masks, then we can guarantee that the type is not in `TO`.
+ using Helper = detail::IsAnyOf<TO...>;
+ auto* type = &obj->TypeInfo();
+ auto hashcode = type->combined_hashcode;
+ if ((Helper::kHashCodes & hashcode) == 0) {
+ return false;
+ }
+ // Possibly one of the types in `TO`. Continue to testing against each type.
+ return Helper::template Exec<FROM>(type);
}
/// @returns obj dynamically cast to the type `TO` or `nullptr` if
@@ -337,22 +406,30 @@
/// Helper for Castable::IsAnyOf
template <typename TO_FIRST, typename... TO_REST>
struct IsAnyOf {
- /// @param obj castable object to test
+ /// The bitwise-or of all typeinfo hashcodes
+ static constexpr auto kHashCodes =
+ TypeInfo::HashCodeOf<TO_FIRST>() | IsAnyOf<TO_REST...>::kHashCodes;
+
+ /// @param type castable object type to test
/// @returns true if `obj` is of, or derives from any of `[TO_FIRST,
/// ...TO_REST]`
template <typename FROM>
- static bool Exec(FROM* obj) {
- return Is<TO_FIRST>(obj) || IsAnyOf<TO_REST...>::Exec(obj);
+ static bool Exec(const TypeInfo* type) {
+ return TypeInfo::Is<TO_FIRST, FROM>(type) ||
+ IsAnyOf<TO_REST...>::template Exec<FROM>(type);
}
};
/// Terminal specialization
template <typename TO>
struct IsAnyOf<TO> {
- /// @param obj castable object to test
+ /// The bitwise-or of all typeinfo hashcodes
+ static constexpr auto kHashCodes = TypeInfo::HashCodeOf<TO>();
+
+ /// @param type castable object type to test
/// @returns true if `obj` is of, or derives from TO
template <typename FROM>
- static bool Exec(FROM* obj) {
- return Is<TO>(obj);
+ static bool Exec(const TypeInfo* type) {
+ return TypeInfo::Is<TO, FROM>(type);
}
};
} // namespace detail
diff --git a/src/clone_context.cc b/src/clone_context.cc
index bf021c3..31b49cd 100644
--- a/src/clone_context.cc
+++ b/src/clone_context.cc
@@ -84,7 +84,7 @@
// Attempt to clone using the registered replacer functions.
auto& typeinfo = object->TypeInfo();
for (auto& transform : transforms_) {
- if (typeinfo.Is(*transform.typeinfo)) {
+ if (typeinfo.Is(transform.typeinfo)) {
if (auto* transformed = transform.function(object)) {
return transformed;
}
diff --git a/src/clone_context.h b/src/clone_context.h
index fd47a2f..9b55a1f 100644
--- a/src/clone_context.h
+++ b/src/clone_context.h
@@ -277,8 +277,8 @@
using TPtr = traits::ParameterType<F, 0>;
using T = typename std::remove_pointer<TPtr>::type;
for (auto& transform : transforms_) {
- if (transform.typeinfo->Is(TypeInfo::Of<T>()) ||
- TypeInfo::Of<T>().Is(*transform.typeinfo)) {
+ if (transform.typeinfo->Is(&TypeInfo::Of<T>()) ||
+ TypeInfo::Of<T>().Is(transform.typeinfo)) {
TINT_ICE(Clone, Diagnostics())
<< "ReplaceAll() called with a handler for type "
<< TypeInfo::Of<T>().name
diff --git a/src/inspector/inspector.cc b/src/inspector/inspector.cc
index 1b4cede..1767b01 100644
--- a/src/inspector/inspector.cc
+++ b/src/inspector/inspector.cc
@@ -468,7 +468,7 @@
std::vector<ResourceBinding> Inspector::GetTextureResourceBindings(
const std::string& entry_point,
- const tint::TypeInfo& texture_type,
+ const tint::TypeInfo* texture_type,
ResourceBinding::ResourceType resource_type) {
auto* func = FindEntryPointByName(entry_point);
if (!func) {
@@ -500,7 +500,7 @@
std::vector<ResourceBinding> Inspector::GetDepthTextureResourceBindings(
const std::string& entry_point) {
return GetTextureResourceBindings(
- entry_point, TypeInfo::Of<sem::DepthTexture>(),
+ entry_point, &TypeInfo::Of<sem::DepthTexture>(),
ResourceBinding::ResourceType::kDepthTexture);
}
@@ -508,14 +508,14 @@
Inspector::GetDepthMultisampledTextureResourceBindings(
const std::string& entry_point) {
return GetTextureResourceBindings(
- entry_point, TypeInfo::Of<sem::DepthMultisampledTexture>(),
+ entry_point, &TypeInfo::Of<sem::DepthMultisampledTexture>(),
ResourceBinding::ResourceType::kDepthMultisampledTexture);
}
std::vector<ResourceBinding> Inspector::GetExternalTextureResourceBindings(
const std::string& entry_point) {
return GetTextureResourceBindings(
- entry_point, TypeInfo::Of<sem::ExternalTexture>(),
+ entry_point, &TypeInfo::Of<sem::ExternalTexture>(),
ResourceBinding::ResourceType::kExternalTexture);
}
diff --git a/src/inspector/inspector.h b/src/inspector/inspector.h
index be26eb6..0e8d804 100644
--- a/src/inspector/inspector.h
+++ b/src/inspector/inspector.h
@@ -181,7 +181,7 @@
/// @returns vector of all of the bindings for depth textures.
std::vector<ResourceBinding> GetTextureResourceBindings(
const std::string& entry_point,
- const tint::TypeInfo& texture_type,
+ const tint::TypeInfo* texture_type,
ResourceBinding::ResourceType resource_type);
/// @param entry_point name of the entry point to get information about.
diff --git a/src/sem/function.cc b/src/sem/function.cc
index 4e95ff6..919c638 100644
--- a/src/sem/function.cc
+++ b/src/sem/function.cc
@@ -126,11 +126,11 @@
}
Function::VariableBindings Function::TransitivelyReferencedVariablesOfType(
- const tint::TypeInfo& type_info) const {
+ const tint::TypeInfo* type) const {
VariableBindings ret;
for (auto* var : TransitivelyReferencedGlobals()) {
auto* unwrapped_type = var->Type()->UnwrapRef();
- if (unwrapped_type->TypeInfo().Is(type_info)) {
+ if (unwrapped_type->TypeInfo().Is(type)) {
if (auto binding_point = var->Declaration()->BindingPoint()) {
ret.push_back({var, binding_point});
}
diff --git a/src/sem/function.h b/src/sem/function.h
index 75e3a48..460e722 100644
--- a/src/sem/function.h
+++ b/src/sem/function.h
@@ -232,17 +232,17 @@
/// Retrieves any referenced variables of the given type. Note, the variables
/// must be decorated with both binding and group decorations.
- /// @param type_info the type of the variables to find
+ /// @param type the type of the variables to find
/// @returns the referenced variables
VariableBindings TransitivelyReferencedVariablesOfType(
- const tint::TypeInfo& type_info) const;
+ const tint::TypeInfo* type) const;
/// Retrieves any referenced variables of the given type. Note, the variables
/// must be decorated with both binding and group decorations.
/// @returns the referenced variables
template <typename T>
VariableBindings TransitivelyReferencedVariablesOfType() const {
- return TransitivelyReferencedVariablesOfType(TypeInfo::Of<T>());
+ return TransitivelyReferencedVariablesOfType(&TypeInfo::Of<T>());
}
/// Checks if the given entry point is an ancestor
diff --git a/src/utils/crc32.h b/src/utils/crc32.h
new file mode 100644
index 0000000..9c296d0
--- /dev/null
+++ b/src/utils/crc32.h
@@ -0,0 +1,82 @@
+// 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_UTILS_CRC32_H_
+#define SRC_UTILS_CRC32_H_
+
+#include <stdint.h>
+
+namespace tint::utils {
+
+/// @returns the CRC32 of the string `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) {
+ constexpr uint32_t kLUT[] = {
+ 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};
+
+ uint32_t crc = 0xffffffff;
+ for (auto* p = s; *p != '\0'; ++p) {
+ crc =
+ (crc >> 8) ^ kLUT[static_cast<uint8_t>(crc) ^ static_cast<uint8_t>(*p)];
+ }
+ return crc ^ 0xffffffff;
+}
+
+} // namespace tint::utils
+
+#endif // SRC_UTILS_CRC32_H_
diff --git a/src/utils/crc32_test.cc b/src/utils/crc32_test.cc
new file mode 100644
index 0000000..b1b739f
--- /dev/null
+++ b/src/utils/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/utils/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/test/BUILD.gn b/test/BUILD.gn
index b14707a..4812293 100644
--- a/test/BUILD.gn
+++ b/test/BUILD.gn
@@ -340,6 +340,7 @@
tint_unittests_source_set("tint_unittests_utils_src") {
sources = [
+ "../src/utils/crc32_test.cc",
"../src/utils/defer_test.cc",
"../src/utils/enum_set_test.cc",
"../src/utils/hash_test.cc",
