Fingerprint.h

Go to the documentation of this file.

/*
 * Copyright 2012-present Facebook, Inc.
 *
 * 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.
 */

#pragma once

#include <array>
#include <cstdint>

#include <folly/Range.h>

namespace folly {

namespace detail {

constexpr size_t poly_size(size_t bits) {
  return 1 + (bits - 1) / 64;
}

template <size_t Deg>
using poly_table =
    std::array<std::array<std::array<uint64_t, poly_size(Deg)>, 256>, 8>;

template <int BITS>
struct FingerprintTable {
  static const uint64_t poly[poly_size(BITS)];
  static const poly_table<BITS> table;
};

template <int BITS>
const uint64_t FingerprintTable<BITS>::poly[poly_size(BITS)] = {};
template <int BITS>
const poly_table<BITS> FingerprintTable<BITS>::table = {};

#ifndef _MSC_VER
// MSVC 2015 can't handle these extern specialization declarations,
// but they aren't needed for things to work right, so we just don't
// declare them in the header for MSVC.

#define FOLLY_DECLARE_FINGERPRINT_TABLES(BITS)                  \
  template <>                                                   \
  const uint64_t FingerprintTable<BITS>::poly[poly_size(BITS)]; \
  template <>                                                   \
  const poly_table<BITS> FingerprintTable<BITS>::table

FOLLY_DECLARE_FINGERPRINT_TABLES(64);
FOLLY_DECLARE_FINGERPRINT_TABLES(96);
FOLLY_DECLARE_FINGERPRINT_TABLES(128);

#undef FOLLY_DECLARE_FINGERPRINT_TABLES
#endif

} // namespace detail

template <int BITS>
class Fingerprint {
 public:
  Fingerprint() {
    // Use a non-zero starting value. We'll use (1 << (BITS-1))
    fp_[0] = 1ULL << 63;
    for (int i = 1; i < size(); i++) {
      fp_[i] = 0;
    }
  }

  Fingerprint& update8(uint8_t v) {
    uint8_t out = shlor8(v);
    xortab(detail::FingerprintTable<BITS>::table[0][out]);
    return *this;
  }

  // update32 and update64 are convenience functions to update the fingerprint
  // with 4 and 8 bytes at a time.  They are faster than calling update8
  // in a loop.  They process the bytes in big-endian order.
  Fingerprint& update32(uint32_t v) {
    uint32_t out = shlor32(v);
    for (int i = 0; i < 4; i++) {
      xortab(detail::FingerprintTable<BITS>::table[i][out & 0xff]);
      out >>= 8;
    }
    return *this;
  }

  Fingerprint& update64(uint64_t v) {
    uint64_t out = shlor64(v);
    for (int i = 0; i < 8; i++) {
      xortab(detail::FingerprintTable<BITS>::table[i][out & 0xff]);
      out >>= 8;
    }
    return *this;
  }

  Fingerprint& update(StringPiece str) {
    // TODO(tudorb): We could be smart and do update64 or update32 if aligned
    for (auto c : str) {
      update8(uint8_t(c));
    }
    return *this;
  }

  constexpr static int size() {
    return detail::poly_size(BITS);
  }

  void write(uint64_t* out) const {
    for (int i = 0; i < size(); i++) {
      out[i] = fp_[i];
    }
  }

 private:
  // XOR the fingerprint with a value from one of the tables.
  void xortab(std::array<uint64_t, detail::poly_size(BITS)> const& tab) {
    for (int i = 0; i < size(); i++) {
      fp_[i] ^= tab[i];
    }
  }

  // Helper functions: shift the fingerprint value left by 8/32/64 bits,
  // return the "out" value (the bits that were shifted out), and add "v"
  // in the bits on the right.
  uint8_t shlor8(uint8_t v);
  uint32_t shlor32(uint32_t v);
  uint64_t shlor64(uint64_t v);

  uint64_t fp_[detail::poly_size(BITS)];
};

// Convenience functions

inline uint64_t fingerprint64(StringPiece str) {
  uint64_t fp;
  Fingerprint<64>().update(str).write(&fp);
  return fp;
}

inline void fingerprint96(StringPiece str, uint64_t* msb, uint32_t* lsb) {
  uint64_t fp[2];
  Fingerprint<96>().update(str).write(fp);
  *msb = fp[0];
  *lsb = (uint32_t)(fp[1] >> 32);
}

inline void fingerprint128(StringPiece str, uint64_t* msb, uint64_t* lsb) {
  uint64_t fp[2];
  Fingerprint<128>().update(str).write(fp);
  *msb = fp[0];
  *lsb = fp[1];
}

template <>
inline uint8_t Fingerprint<64>::shlor8(uint8_t v) {
  uint8_t out = (uint8_t)(fp_[0] >> 56);
  fp_[0] = (fp_[0] << 8) | ((uint64_t)v);
  return out;
}

template <>
inline uint32_t Fingerprint<64>::shlor32(uint32_t v) {
  uint32_t out = (uint32_t)(fp_[0] >> 32);
  fp_[0] = (fp_[0] << 32) | ((uint64_t)v);
  return out;
}

template <>
inline uint64_t Fingerprint<64>::shlor64(uint64_t v) {
  uint64_t out = fp_[0];
  fp_[0] = v;
  return out;
}

template <>
inline uint8_t Fingerprint<96>::shlor8(uint8_t v) {
  uint8_t out = (uint8_t)(fp_[0] >> 56);
  fp_[0] = (fp_[0] << 8) | (fp_[1] >> 56);
  fp_[1] = (fp_[1] << 8) | ((uint64_t)v << 32);
  return out;
}

template <>
inline uint32_t Fingerprint<96>::shlor32(uint32_t v) {
  uint32_t out = (uint32_t)(fp_[0] >> 32);
  fp_[0] = (fp_[0] << 32) | (fp_[1] >> 32);
  fp_[1] = ((uint64_t)v << 32);
  return out;
}

template <>
inline uint64_t Fingerprint<96>::shlor64(uint64_t v) {
  uint64_t out = fp_[0];
  fp_[0] = fp_[1] | (v >> 32);
  fp_[1] = v << 32;
  return out;
}

template <>
inline uint8_t Fingerprint<128>::shlor8(uint8_t v) {
  uint8_t out = (uint8_t)(fp_[0] >> 56);
  fp_[0] = (fp_[0] << 8) | (fp_[1] >> 56);
  fp_[1] = (fp_[1] << 8) | ((uint64_t)v);
  return out;
}

template <>
inline uint32_t Fingerprint<128>::shlor32(uint32_t v) {
  uint32_t out = (uint32_t)(fp_[0] >> 32);
  fp_[0] = (fp_[0] << 32) | (fp_[1] >> 32);
  fp_[1] = (fp_[1] << 32) | ((uint64_t)v);
  return out;
}

template <>
inline uint64_t Fingerprint<128>::shlor64(uint64_t v) {
  uint64_t out = fp_[0];
  fp_[0] = fp_[1];
  fp_[1] = v;
  return out;
}

} // namespace folly