folly/folly/Fingerprint.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * 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
 *
 *     http://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.
 */

/**
 * Compute 64-, 96-, and 128-bit Rabin fingerprints, as described in
 * Michael O. Rabin (1981)
 *   Fingerprinting by Random Polynomials
 *   Center for Research in Computing Technology, Harvard University
 *   Tech Report TR-CSE-03-01
 *
 * The implementation follows the optimization described in
 * Andrei Z. Broder (1993)
 *   Some applications of Rabin's fingerprinting method
 *
 * extended for fingerprints larger than 64 bits, and modified to use
 * 64-bit instead of 32-bit integers for computation.
 *
 * The precomputed tables are in Fingerprint.cpp.
 *
 * Benchmarked on 10/13/2009 on a 2.5GHz quad-core Xeon L5420,
 * - Fingerprint<64>::update64() takes about 12ns
 * - Fingerprint<96>::update64() takes about 30ns
 * - Fingerprint<128>::update128() takes about 30ns
 * (unsurprisingly, Fingerprint<96> and Fingerprint<128> take the
 * same amount of time, as they both use 128-bit operations; the least
 * significant 32 bits of Fingerprint<96> will always be 0)
 */

#pragma once

#include <array>
#include <cstdint>

#include <folly/Range.h>

namespace folly {

detail // namespace detail

/**
 * Compute the Rabin fingerprint.
 *
 * TODO(tudorb): Extend this to allow removing values from the computed
 * fingerprint (so we can fingerprint a sliding window, as in the Rabin-Karp
 * string matching algorithm)
 *
 * update* methods return *this, so you can chain them together:
 * Fingerprint<96>().update8(x).update(str).update64(val).write(output);
 */
template <int BITS>
class Fingerprint { … };

// Convenience functions

/**
 * Return the 64-bit Rabin fingerprint of a string.
 */
inline uint64_t fingerprint64(StringPiece str) { … }

/**
 * Compute the 96-bit Rabin fingerprint of a string.
 * Return the 64 most significant bits in *msb, and the 32 least significant
 * bits in *lsb.
 */
inline void fingerprint96(StringPiece str, uint64_t* msb, uint32_t* lsb) { … }

/**
 * Compute the 128-bit Rabin fingerprint of a string.
 * Return the 64 most significant bits in *msb, and the 64 least significant
 * bits in *lsb.
 */
inline void fingerprint128(StringPiece str, uint64_t* msb, uint64_t* lsb) { … }

template <>
inline uint8_t Fingerprint<64>::shlor8(uint8_t v) { … }

template <>
inline uint32_t Fingerprint<64>::shlor32(uint32_t v) { … }

template <>
inline uint64_t Fingerprint<64>::shlor64(uint64_t v) { … }

template <>
inline uint8_t Fingerprint<96>::shlor8(uint8_t v) { … }

template <>
inline uint32_t Fingerprint<96>::shlor32(uint32_t v) { … }

template <>
inline uint64_t Fingerprint<96>::shlor64(uint64_t v) { … }

template <>
inline uint8_t Fingerprint<128>::shlor8(uint8_t v) { … }

template <>
inline uint32_t Fingerprint<128>::shlor32(uint32_t v) { … }

template <>
inline uint64_t Fingerprint<128>::shlor64(uint64_t v) { … }

} // namespace folly