summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2023-01-17 12:33:40 -0800
committerGravatar Copybara-Service <copybara-worker@google.com>2023-01-17 12:34:50 -0800
commit4b34e19765c8c03e4066f2226f7fb28d68604a1d (patch)
treec1a1532a057bd978397f56936f33ea91130743cd /absl
parente1c897f09a3ae4ed76f4c17006eacaadbd8a56f9 (diff)
Optimize RemoveCrc32cSuffix.
The implementation can be optimized to not having to perform an ExtendByZero operation. `RemoveCrc32cSuffix` can simply be implemented as uint32_t result = static_cast<uint32_t>(full_string_crc) ^ static_cast<uint32_t>(suffix_crc); CrcEngine()->UnextendByZeroes(&result, suffix_len); return crc32c_t{result}; Math proof that this change is correct: `ComputeCrc32c` actually computes the following: ConditionedCRC(data) = UnconditionedCRC(data) + StartValue(data) + ~0 with: StartValue(data) = ~0 * x**BitLength(data) mod P (with `+` being a carry-less add, ie an xor). ``UnconditionedCRC` in the context of this description means: no initial or final xor with ~0 and a starting value of zero - ie the result that `CrcEngine()->Extend` would give you with a starting value of 0. Given `full_string_crc` and `suffix_crc` (both conditioned CRCs), xoring them together results in: (1): full_string_crc + suffix_crc = UnconditionedCRC(full_string) + StartValue(full_string) + ~0 + UnconditionedCRC(suffix) + StartValue(suffix) + ~0 Since `+` is carry-less addition (ie an XOR), the two ~0 cancel each other out. (2) full_string_crc + suffix_crc = UnconditionedCRC(full_string) + StartValue(full_string) + UnconditionedCRC(suffix) + StartValue(suffix) We can make use of the fact that: (3) UnconditionedCRC(full_string) + UnConditionedCRC(suffix) = UnconditionedCRC(full_string_with_suffix_replaced_by_zeros). Ie, UnconditionedCRC("AABBB") + UnconditionedCRC("BBB") = UnconditionedCRC("AA\0\0\0") Putting (3) into (2) yields: (4) full_string_crc + suffix_crc = UnconditionedCRC(full_string_with_suffix_replaced_by_zeros) + StartValue(full_string) + StartValue(suffix) Using: (5) UnconditionedCRC(full_string_with_suffix_replaced_by_zeros) = UnconditionedCRC(full_string_without_suffix) * x**Bitlength(suffix) mod P and putting (5) into (4) (6) full_string_crc + suffix_crc = UnconditionedCRC(full_string_without_suffix) * x**Bitlength(suffix) mod P + StartValue(full_string) + StartValue(suffix) Using (7) StartValue(full_string) = ~0 * x ** Bitlength(full_string) mod P and (8) StartValue(suffix) = ~0 * x**BitLength(suffix) mod P Putting (7) and (8) in (6): (9): full_string_crc + suffix_crc = UnconditionedCRC(full_string_without_suffix) * x**(Bitlength(suffix)) mod P + ~0 * x ** Bitlength(full_string) mod P + ~0 * x ** BitLength(suffix) mod P Using: (10) Bitlength(full_string) = Bitlength(full_string_without_suffix) + Bitlength(suffix) And putting (10) in (9): (11) full_string_crc + suffix_crc = UnconditionedCRC(full_string_without_suffix) * x**(Bitlength(suffix)) mod P + ~0 * x ** (Bitlength(full_string_without_suffix) + Bitlength(suffix)) mod P + ~0 * x ** BitLength(suffix) mod P using x**(A+B) = x**A * x**B results in: (12) full_string_crc + suffix_crc = UnconditionedCRC(full_string_without_suffix) * x**(Bitlength(suffix)) mod P + [ ~0 * x ** Bitlength(full_string_without_suffix) * x**Bitlength(suffix)] mod P + ~0 * x ** BitLength(suffix) mod P using A mod P + B mod P + C mod P = (A + B + C) mod P: (this works in carry-less arithmetic) (13) full_string_crc + suffix_crc = [ UnconditionedCRC(full_string_without_suffix) * x**(Bitlength(suffix)) + [ ~0 * x ** Bitlength(full_string_without_suffix) * x**Bitlength(suffix)] + ~0 * x ** BitLength(suffix) ] mod P Factor out x**Bitlength(suffix): (14) full_string_crc + suffix_crc = [ x**(Bitlength(suffix)) * [ UnconditionedCRC(full_string_without_suffix) + ~0 * x ** Bitlength(full_string_without_suffix) + ~0 ] mod P Using: (15) ConditionedCRC(full_string_without_suffix) = [ UnconditionedCRC(full_string_without_suffix) + ~0 * x ** Bitlength(full_string_without_suffix) ] mod P + ~0 = [ UnconditionedCRC(full_string_without_suffix) + ~0 * x ** Bitlength(full_string_without_suffix) + ~0] mod P (~0 is less than x**32, so ~0 mod P = ~0) Putting (15) in (14) results in: full_string_crc + suffix_crc = [ x**(Bitlength(suffix)) * ConditionedCRC(full_string_without_suffix)] mod P Or: (16) ConditionedCRC(full_string_without_suffix) = (full_string_crc + suffix_crc) * x**(-Bitlength(suffix)) mod P A multiplication by x**(-8*bytelength) mod P is implemented by `CrcEngine()->UnextendByZeros`. PiperOrigin-RevId: 502659140 Change-Id: I66b0700d258f948be0885f691370b73d7fad56e3
Diffstat (limited to 'absl')
-rw-r--r--absl/crc/crc32c.cc10
1 files changed, 4 insertions, 6 deletions
diff --git a/absl/crc/crc32c.cc b/absl/crc/crc32c.cc
index 169826f5..468c1b3b 100644
--- a/absl/crc/crc32c.cc
+++ b/absl/crc/crc32c.cc
@@ -89,12 +89,10 @@ crc32c_t MemcpyCrc32c(void* dest, const void* src, size_t count,
// This operation has a runtime cost of O(log(`suffix_len`))
crc32c_t RemoveCrc32cSuffix(crc32c_t full_string_crc, crc32c_t suffix_crc,
size_t suffix_len) {
- crc32c_t crc_with_suffix_zeroed = crc32c_t{
- static_cast<uint32_t>(suffix_crc) ^
- static_cast<uint32_t>(full_string_crc) ^
- static_cast<uint32_t>(ExtendCrc32cByZeroes(crc32c_t{0}, suffix_len))};
- return crc_internal::UnextendCrc32cByZeroes(
- crc_with_suffix_zeroed, suffix_len);
+ uint32_t result = static_cast<uint32_t>(full_string_crc) ^
+ static_cast<uint32_t>(suffix_crc);
+ CrcEngine()->UnextendByZeroes(&result, suffix_len);
+ return crc32c_t{result};
}
ABSL_NAMESPACE_END