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;
crc32c_t(uint32_t crc)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
uint32_t()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>
AbslStringify(Sink & sink,crc32c_t crc)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 // ComputeCrc32c()
87 //
88 // Returns the CRC32C value of the provided string.
89 crc32c_t ComputeCrc32c(absl::string_view buf);
90
91 // ExtendCrc32c()
92 //
93 // Computes a CRC32C value from an `initial_crc` CRC32C value including the
94 // `buf_to_add` bytes of an additional buffer. Using this function is more
95 // efficient than computing a CRC32C value for the combined buffer from
96 // scratch.
97 //
98 // Note: `ExtendCrc32c` with an initial_crc of 0 is equivalent to
99 // `ComputeCrc32c`.
100 //
101 // This operation has a runtime cost of O(`buf_to_add.size()`)
ExtendCrc32c(crc32c_t initial_crc,absl::string_view buf_to_add)102 inline crc32c_t ExtendCrc32c(crc32c_t initial_crc,
103 absl::string_view buf_to_add) {
104 // Approximately 75% of calls have size <= 64.
105 if (buf_to_add.size() <= 64) {
106 uint32_t crc = static_cast<uint32_t>(initial_crc);
107 if (crc_internal::ExtendCrc32cInline(&crc, buf_to_add.data(),
108 buf_to_add.size())) {
109 return crc32c_t{crc};
110 }
111 }
112 return crc_internal::ExtendCrc32cInternal(initial_crc, buf_to_add);
113 }
114
115 // ExtendCrc32cByZeroes()
116 //
117 // Computes a CRC32C value for a buffer with an `initial_crc` CRC32C value,
118 // where `length` bytes with a value of 0 are appended to the buffer. Using this
119 // function is more efficient than computing a CRC32C value for the combined
120 // buffer from scratch.
121 //
122 // This operation has a runtime cost of O(log(`length`))
123 crc32c_t ExtendCrc32cByZeroes(crc32c_t initial_crc, size_t length);
124
125 // MemcpyCrc32c()
126 //
127 // Copies `src` to `dest` using `memcpy()` semantics, returning the CRC32C
128 // value of the copied buffer.
129 //
130 // Using `MemcpyCrc32c()` is potentially faster than performing the `memcpy()`
131 // and `ComputeCrc32c()` operations separately.
132 crc32c_t MemcpyCrc32c(void* dest, const void* src, size_t count,
133 crc32c_t initial_crc = crc32c_t{0});
134
135 // -----------------------------------------------------------------------------
136 // CRC32C Arithmetic Functions
137 // -----------------------------------------------------------------------------
138
139 // The following functions perform arithmetic on CRC32C values, which are
140 // generally more efficient than recalculating any given result's CRC32C value.
141
142 // ConcatCrc32c()
143 //
144 // Calculates the CRC32C value of two buffers with known CRC32C values
145 // concatenated together.
146 //
147 // Given a buffer with CRC32C value `crc1` and a buffer with
148 // CRC32C value `crc2` and length, `crc2_length`, returns the CRC32C value of
149 // the concatenation of these two buffers.
150 //
151 // This operation has a runtime cost of O(log(`crc2_length`)).
152 crc32c_t ConcatCrc32c(crc32c_t crc1, crc32c_t crc2, size_t crc2_length);
153
154 // RemoveCrc32cPrefix()
155 //
156 // Calculates the CRC32C value of an existing buffer with a series of bytes
157 // (the prefix) removed from the beginning of that buffer.
158 //
159 // Given the CRC32C value of an existing buffer, `full_string_crc`; The CRC32C
160 // value of a prefix of that buffer, `prefix_crc`; and the length of the buffer
161 // with the prefix removed, `remaining_string_length` , return the CRC32C
162 // value of the buffer with the prefix removed.
163 //
164 // This operation has a runtime cost of O(log(`remaining_string_length`)).
165 crc32c_t RemoveCrc32cPrefix(crc32c_t prefix_crc, crc32c_t full_string_crc,
166 size_t remaining_string_length);
167 // RemoveCrc32cSuffix()
168 //
169 // Calculates the CRC32C value of an existing buffer with a series of bytes
170 // (the suffix) removed from the end of that buffer.
171 //
172 // Given a CRC32C value of an existing buffer `full_string_crc`, the CRC32C
173 // value of the suffix to remove `suffix_crc`, and the length of that suffix
174 // `suffix_len`, returns the CRC32C value of the buffer with suffix removed.
175 //
176 // This operation has a runtime cost of O(log(`suffix_len`))
177 crc32c_t RemoveCrc32cSuffix(crc32c_t full_string_crc, crc32c_t suffix_crc,
178 size_t suffix_length);
179
180 // operator<<
181 //
182 // Streams the CRC32C value `crc` to the stream `os`.
183 inline std::ostream& operator<<(std::ostream& os, crc32c_t crc) {
184 return os << absl::StreamFormat("%08x", static_cast<uint32_t>(crc));
185 }
186
187 ABSL_NAMESPACE_END
188 } // namespace absl
189
190 #endif // ABSL_CRC_CRC32C_H_
191