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 #ifndef ABSL_CRC_INTERNAL_CRC_H_ 16 #define ABSL_CRC_INTERNAL_CRC_H_ 17 18 #include <cstdint> 19 20 #include "absl/base/config.h" 21 22 // This class implements CRCs (aka Rabin Fingerprints). 23 // Treats the input as a polynomial with coefficients in Z(2), 24 // and finds the remainder when divided by an primitive polynomial 25 // of the appropriate length. 26 27 // A polynomial is represented by the bit pattern formed by its coefficients, 28 // but with the highest order bit not stored. 29 // The highest degree coefficient is stored in the lowest numbered bit 30 // in the lowest addressed byte. Thus, in what follows, the highest degree 31 // coefficient that is stored is in the low order bit of "lo" or "*lo". 32 33 // Hardware acceleration is used when available. 34 35 namespace absl { 36 ABSL_NAMESPACE_BEGIN 37 namespace crc_internal { 38 39 class CRC { 40 public: 41 virtual ~CRC(); 42 43 // Place the CRC of the empty string in "*crc" 44 virtual void Empty(uint32_t* crc) const = 0; 45 46 // If "*crc" is the CRC of bytestring A, place the CRC of 47 // the bytestring formed from the concatenation of A and the "length" 48 // bytes at "bytes" into "*crc". 49 virtual void Extend(uint32_t* crc, const void* bytes, 50 size_t length) const = 0; 51 52 // Equivalent to Extend(crc, bytes, length) where "bytes" 53 // points to an array of "length" zero bytes. 54 virtual void ExtendByZeroes(uint32_t* crc, size_t length) const = 0; 55 56 // Inverse opration of ExtendByZeroes. If `crc` is the CRC value of a string 57 // ending in `length` zero bytes, this returns a CRC value of that string 58 // with those zero bytes removed. 59 virtual void UnextendByZeroes(uint32_t* crc, size_t length) const = 0; 60 61 // If *px is the CRC (as defined by *crc) of some string X, 62 // and y is the CRC of some string Y that is ylen bytes long, set 63 // *px to the CRC of the concatenation of X followed by Y. 64 virtual void Concat(uint32_t* px, uint32_t y, size_t ylen); 65 66 // Apply a non-linear transformation to "*crc" so that 67 // it is safe to CRC the result with the same polynomial without 68 // any reduction of error-detection ability in the outer CRC. 69 // Unscramble() performs the inverse transformation. 70 // It is strongly recommended that CRCs be scrambled before storage or 71 // transmission, and unscrambled at the other end before futher manipulation. 72 virtual void Scramble(uint32_t* crc) const = 0; 73 virtual void Unscramble(uint32_t* crc) const = 0; 74 75 // Crc32c() returns the singleton implementation of CRC for the CRC32C 76 // polynomial. Returns a handle that MUST NOT be destroyed with delete. 77 static CRC* Crc32c(); 78 79 protected: 80 CRC(); // Clients may not call constructor; use Crc32c() instead. 81 82 private: 83 CRC(const CRC&) = delete; 84 CRC& operator=(const CRC&) = delete; 85 }; 86 87 } // namespace crc_internal 88 ABSL_NAMESPACE_END 89 } // namespace absl 90 91 #endif // ABSL_CRC_INTERNAL_CRC_H_ 92