| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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
|
Abseil Team
Derek Mauro