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 // If "*crc" is the CRC of bytestring A, place the CRC of 44 // the bytestring formed from the concatenation of A and the "length" 45 // bytes at "bytes" into "*crc". 46 virtual void Extend(uint32_t* crc, const void* bytes, 47 size_t length) const = 0; 48 49 // Equivalent to Extend(crc, bytes, length) where "bytes" 50 // points to an array of "length" zero bytes. 51 virtual void ExtendByZeroes(uint32_t* crc, size_t length) const = 0; 52 53 // Inverse operation of ExtendByZeroes. If `crc` is the CRC value of a string 54 // ending in `length` zero bytes, this returns a CRC value of that string 55 // with those zero bytes removed. 56 virtual void UnextendByZeroes(uint32_t* crc, size_t length) const = 0; 57 58 // Apply a non-linear transformation to "*crc" so that 59 // it is safe to CRC the result with the same polynomial without 60 // any reduction of error-detection ability in the outer CRC. 61 // Unscramble() performs the inverse transformation. 62 // It is strongly recommended that CRCs be scrambled before storage or 63 // transmission, and unscrambled at the other end before further manipulation. 64 virtual void Scramble(uint32_t* crc) const = 0; 65 virtual void Unscramble(uint32_t* crc) const = 0; 66 67 // Crc32c() returns the singleton implementation of CRC for the CRC32C 68 // polynomial. Returns a handle that MUST NOT be destroyed with delete. 69 static CRC* Crc32c(); 70 71 protected: 72 CRC(); // Clients may not call constructor; use Crc32c() instead. 73 74 private: 75 CRC(const CRC&) = delete; 76 CRC& operator=(const CRC&) = delete; 77 }; 78 79 } // namespace crc_internal 80 ABSL_NAMESPACE_END 81 } // namespace absl 82 83 #endif // ABSL_CRC_INTERNAL_CRC_H_ 84