Skip to content

A
abseil-cpp
Switch branch/tag
  1. 01 Feb, 2023 1 commit
  3. 31 Jan, 2023 1 commit
  5. 30 Jan, 2023 1 commit
  7. 28 Jan, 2023 1 commit
  9. 27 Jan, 2023 3 commits
  11. 26 Jan, 2023 4 commits
  13. 25 Jan, 2023 4 commits
  15. 24 Jan, 2023 3 commits
  17. 23 Jan, 2023 4 commits
  19. 20 Jan, 2023 5 commits
  21. 19 Jan, 2023 6 commits
  23. 18 Jan, 2023 1 commit
  25. 17 Jan, 2023 4 commits
    • extern-ify NullGuard's "(null)" strings to save linker input bytes. · a86f1cec 
      PiperOrigin-RevId: 502689876
Change-Id: If75b00e2e257283b60c41411ef7a60dbd7cd8c6d
      Andy Getzendanner committed
    • Optimize RemoveCrc32cSuffix. · 4b34e197 
      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 committed
    • In sanitizer mode, detect when references become invalidated after reserved growth runs out. · e1c897f0 
      PiperOrigin-RevId: 502625638
Change-Id: I1c06b2162dbdaaa6a36cea503ac6d07cd157b2e2
      Evan Brown committed
    • Tweak the compilation condition for IsHashableTest.PoisonHash · 1fb3830b 
      #1359

PiperOrigin-RevId: 502597369
Change-Id: I5d65ed7e2dbe4b51ebce47f282ead89d91d919cd
      Derek Mauro committed
  27. 13 Jan, 2023 1 commit
  29. 12 Jan, 2023 1 commit