From 4b34e19765c8c03e4066f2226f7fb28d68604a1d Mon Sep 17 00:00:00 2001
From: Abseil Team <absl-team@google.com>
Date: Tue, 17 Jan 2023 12:33:40 -0800
Subject: 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
---
 absl/crc/crc32c.cc | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

(limited to 'absl')

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
-- 
cgit v1.2.3