crc32c.h (7309B)
1 // Copyright 2022 The Abseil Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // ----------------------------------------------------------------------------- 16 // File: crc32c.h 17 // ----------------------------------------------------------------------------- 18 // 19 // This header file defines the API for computing CRC32C values as checksums 20 // for arbitrary sequences of bytes provided as a string buffer. 21 // 22 // The API includes the basic functions for computing such CRC32C values and 23 // some utility functions for performing more efficient mathematical 24 // computations using an existing checksum. 25 #ifndef ABSL_CRC_CRC32C_H_ 26 #define ABSL_CRC_CRC32C_H_ 27 28 #include <cstdint> 29 #include <ostream> 30 31 #include "absl/crc/internal/crc32c_inline.h" 32 #include "absl/strings/str_format.h" 33 #include "absl/strings/string_view.h" 34 35 namespace absl { 36 ABSL_NAMESPACE_BEGIN 37 38 //----------------------------------------------------------------------------- 39 // crc32c_t 40 //----------------------------------------------------------------------------- 41 42 // `crc32c_t` defines a strongly-typed integer for holding a CRC32C value. 43 // 44 // Some operators are intentionally omitted. Only equality operators are defined 45 // so that `crc32c_t` can be directly compared. Methods for putting `crc32c_t` 46 // directly into a set are omitted because this is bug-prone due to checksum 47 // collisions. Use an explicit conversion to the `uint32_t` space for operations 48 // that treat `crc32c_t` as an integer. 49 class crc32c_t final { 50 public: 51 crc32c_t() = default; 52 constexpr explicit crc32c_t(uint32_t crc) : crc_(crc) {} 53 54 crc32c_t(const crc32c_t&) = default; 55 crc32c_t& operator=(const crc32c_t&) = default; 56 57 explicit operator uint32_t() const { return crc_; } 58 59 friend bool operator==(crc32c_t lhs, crc32c_t rhs) { 60 return static_cast<uint32_t>(lhs) == static_cast<uint32_t>(rhs); 61 } 62 63 friend bool operator!=(crc32c_t lhs, crc32c_t rhs) { return !(lhs == rhs); } 64 65 template <typename Sink> 66 friend void AbslStringify(Sink& sink, crc32c_t crc) { 67 absl::Format(&sink, "%08x", static_cast<uint32_t>(crc)); 68 } 69 70 private: 71 uint32_t crc_; 72 }; 73 74 75 namespace crc_internal { 76 // Non-inline code path for `absl::ExtendCrc32c()`. Do not call directly. 77 // Call `absl::ExtendCrc32c()` (defined below) instead. 78 crc32c_t ExtendCrc32cInternal(crc32c_t initial_crc, 79 absl::string_view buf_to_add); 80 } // namespace crc_internal 81 82 // ----------------------------------------------------------------------------- 83 // CRC32C Computation Functions 84 // ----------------------------------------------------------------------------- 85 86 // ExtendCrc32c() 87 // 88 // Computes a CRC32C value from an `initial_crc` CRC32C value including the 89 // `buf_to_add` bytes of an additional buffer. Using this function is more 90 // efficient than computing a CRC32C value for the combined buffer from 91 // scratch. 92 // 93 // Note: `ExtendCrc32c` with an initial_crc of 0 is equivalent to 94 // `ComputeCrc32c`. 95 // 96 // This operation has a runtime cost of O(`buf_to_add.size()`) 97 inline crc32c_t ExtendCrc32c(crc32c_t initial_crc, 98 absl::string_view buf_to_add) { 99 // Approximately 75% of calls have size <= 64. 100 if (buf_to_add.size() <= 64) { 101 uint32_t crc = static_cast<uint32_t>(initial_crc); 102 if (crc_internal::ExtendCrc32cInline(&crc, buf_to_add.data(), 103 buf_to_add.size())) { 104 return crc32c_t{crc}; 105 } 106 } 107 return crc_internal::ExtendCrc32cInternal(initial_crc, buf_to_add); 108 } 109 110 // ComputeCrc32c() 111 // 112 // Returns the CRC32C value of the provided string. 113 inline crc32c_t ComputeCrc32c(absl::string_view buf) { 114 return ExtendCrc32c(crc32c_t{0}, buf); 115 } 116 117 // ExtendCrc32cByZeroes() 118 // 119 // Computes a CRC32C value for a buffer with an `initial_crc` CRC32C value, 120 // where `length` bytes with a value of 0 are appended to the buffer. Using this 121 // function is more efficient than computing a CRC32C value for the combined 122 // buffer from scratch. 123 // 124 // This operation has a runtime cost of O(log(`length`)) 125 crc32c_t ExtendCrc32cByZeroes(crc32c_t initial_crc, size_t length); 126 127 // MemcpyCrc32c() 128 // 129 // Copies `src` to `dest` using `memcpy()` semantics, returning the CRC32C 130 // value of the copied buffer. 131 // 132 // Using `MemcpyCrc32c()` is potentially faster than performing the `memcpy()` 133 // and `ComputeCrc32c()` operations separately. 134 crc32c_t MemcpyCrc32c(void* dest, const void* src, size_t count, 135 crc32c_t initial_crc = crc32c_t{0}); 136 137 // ----------------------------------------------------------------------------- 138 // CRC32C Arithmetic Functions 139 // ----------------------------------------------------------------------------- 140 141 // The following functions perform arithmetic on CRC32C values, which are 142 // generally more efficient than recalculating any given result's CRC32C value. 143 144 // ConcatCrc32c() 145 // 146 // Calculates the CRC32C value of two buffers with known CRC32C values 147 // concatenated together. 148 // 149 // Given a buffer with CRC32C value `crc1` and a buffer with 150 // CRC32C value `crc2` and length, `crc2_length`, returns the CRC32C value of 151 // the concatenation of these two buffers. 152 // 153 // This operation has a runtime cost of O(log(`crc2_length`)). 154 crc32c_t ConcatCrc32c(crc32c_t crc1, crc32c_t crc2, size_t crc2_length); 155 156 // RemoveCrc32cPrefix() 157 // 158 // Calculates the CRC32C value of an existing buffer with a series of bytes 159 // (the prefix) removed from the beginning of that buffer. 160 // 161 // Given the CRC32C value of an existing buffer, `full_string_crc`; The CRC32C 162 // value of a prefix of that buffer, `prefix_crc`; and the length of the buffer 163 // with the prefix removed, `remaining_string_length` , return the CRC32C 164 // value of the buffer with the prefix removed. 165 // 166 // This operation has a runtime cost of O(log(`remaining_string_length`)). 167 crc32c_t RemoveCrc32cPrefix(crc32c_t prefix_crc, crc32c_t full_string_crc, 168 size_t remaining_string_length); 169 // RemoveCrc32cSuffix() 170 // 171 // Calculates the CRC32C value of an existing buffer with a series of bytes 172 // (the suffix) removed from the end of that buffer. 173 // 174 // Given a CRC32C value of an existing buffer `full_string_crc`, the CRC32C 175 // value of the suffix to remove `suffix_crc`, and the length of that suffix 176 // `suffix_len`, returns the CRC32C value of the buffer with suffix removed. 177 // 178 // This operation has a runtime cost of O(log(`suffix_len`)) 179 crc32c_t RemoveCrc32cSuffix(crc32c_t full_string_crc, crc32c_t suffix_crc, 180 size_t suffix_length); 181 182 // operator<< 183 // 184 // Streams the CRC32C value `crc` to the stream `os`. 185 inline std::ostream& operator<<(std::ostream& os, crc32c_t crc) { 186 return os << absl::StreamFormat("%08x", static_cast<uint32_t>(crc)); 187 } 188 189 ABSL_NAMESPACE_END 190 } // namespace absl 191 192 #endif // ABSL_CRC_CRC32C_H_