chromium/third_party/abseil-cpp/absl/crc/internal/crc_internal.h

// Copyright 2022 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef ABSL_CRC_INTERNAL_CRC_INTERNAL_H_
#define ABSL_CRC_INTERNAL_CRC_INTERNAL_H_

#include <cstdint>
#include <memory>
#include <vector>

#include "absl/base/internal/raw_logging.h"
#include "absl/crc/internal/crc.h"

namespace absl {
ABSL_NAMESPACE_BEGIN

namespace crc_internal {

// Prefetch constants used in some Extend() implementations
constexpr int kPrefetchHorizon = …;  // Prefetch this far
// Shorter prefetch distance for smaller buffers
constexpr int kPrefetchHorizonMedium = …;
static_assert …;

// We require the Scramble() function:
//  - to be reversible (Unscramble() must exist)
//  - to be non-linear in the polynomial's Galois field (so the CRC of a
//    scrambled CRC is not linearly affected by the scrambled CRC, even if
//    using the same polynomial)
//  - not to be its own inverse.  Preferably, if X=Scramble^N(X) and N!=0, then
//    N is large.
//  - to be fast.
//  - not to change once defined.
// We introduce non-linearity in two ways:
//     Addition of a constant.
//         - The carries introduce non-linearity; we use bits of an irrational
//           (phi) to make it unlikely that we introduce no carries.
//     Rotate by a constant number of bits.
//         - We use floor(degree/2)+1, which does not divide the degree, and
//           splits the bits nearly evenly, which makes it less likely the
//           halves will be the same or one will be all zeroes.
// We do both things to improve the chances of non-linearity in the face of
// bit patterns with low numbers of bits set, while still being fast.
// Below is the constant that we add.  The bits are the first 128 bits of the
// fractional part of phi, with a 1 ored into the bottom bit to maximize the
// cycle length of repeated adds.
constexpr uint64_t kScrambleHi = …;
constexpr uint64_t kScrambleLo = …;

class CRCImpl : public CRC { … };

// This is the 32-bit implementation.  It handles all sizes from 8 to 32.
class CRC32 : public CRCImpl { … };

// Helpers

// Return a bit mask containing len 1-bits.
// Requires 0 < len <= sizeof(T)
template <typename T>
T MaskOfLength(int len) { … }

// Rotate low-order "width" bits of "in" right by "r" bits,
// setting other bits in word to arbitrary values.
template <typename T>
T RotateRight(T in, int width, int r) { … }

// RoundUp<N>(p) returns the lowest address >= p aligned to an N-byte
// boundary.  Requires that N is a power of 2.
template <int alignment>
const uint8_t* RoundUp(const uint8_t* p) { … }

// Return a newly created CRC32AcceleratedX86ARMCombined if we can use Intel's
// or ARM's CRC acceleration for a given polynomial.  Return nullptr otherwise.
CRCImpl* TryNewCRC32AcceleratedX86ARMCombined();

// Return all possible hardware accelerated implementations. For testing only.
std::vector<std::unique_ptr<CRCImpl>> NewCRC32AcceleratedX86ARMCombinedAll();

}  // namespace crc_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_CRC_INTERNAL_CRC_INTERNAL_H_