folly::Fingerprint< BITS > Class Template Reference

#include <Fingerprint.h>

Public Member Functions
	Fingerprint ()
Fingerprint &	update8 (uint8_t v)
Fingerprint &	update32 (uint32_t v)
Fingerprint &	update64 (uint64_t v)
Fingerprint &	update (StringPiece str)
void	write (uint64_t *out) const

Static Public Member Functions
static constexpr int	size ()

Private Member Functions
void	xortab (std::array< uint64_t, detail::poly_size(BITS)> const &tab)
uint8_t	shlor8 (uint8_t v)
uint32_t	shlor32 (uint32_t v)
uint64_t	shlor64 (uint64_t v)
template<>
uint8_t	shlor8 (uint8_t v)
template<>
uint32_t	shlor32 (uint32_t v)
template<>
uint64_t	shlor64 (uint64_t v)
template<>
uint8_t	shlor8 (uint8_t v)
template<>
uint32_t	shlor32 (uint32_t v)
template<>
uint64_t	shlor64 (uint64_t v)
template<>
uint8_t	shlor8 (uint8_t v)
template<>
uint32_t	shlor32 (uint32_t v)
template<>
uint64_t	shlor64 (uint64_t v)

Private Attributes
uint64_t	fp_ [detail::poly_size(BITS)]

Detailed Description

template<int BITS>
class folly::Fingerprint< BITS >

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);

Definition at line 105 of file Fingerprint.h.

Constructor & Destructor Documentation

template<int BITS>

folly::Fingerprint< BITS >::Fingerprint ( )

inline

Definition at line 107 of file Fingerprint.h.

References i, and folly::size().

                {
    // 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;
    }
  }

Member Function Documentation

template<int BITS>

uint32_t folly::Fingerprint< BITS >::shlor32 ( uint32_t  v )

private

template<>

uint32_t folly::Fingerprint< 64 >::shlor32 ( uint32_t  v )

inlineprivate

Definition at line 232 of file Fingerprint.h.

References uint32_t, uint64_t, and v.

                                                   {
  uint32_t out = (uint32_t)(fp_[0] >> 32);
  fp_[0] = (fp_[0] << 32) | ((uint64_t)v);
  return out;
}

template<>

uint32_t folly::Fingerprint< 96 >::shlor32 ( uint32_t  v )

inlineprivate

Definition at line 254 of file Fingerprint.h.

References uint32_t, and uint64_t.

                                                   {
  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<>

uint32_t folly::Fingerprint< 128 >::shlor32 ( uint32_t  v )

inlineprivate

Definition at line 278 of file Fingerprint.h.

References uint32_t, uint64_t, and 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<int BITS>

uint64_t folly::Fingerprint< BITS >::shlor64 ( uint64_t  v )

private

template<>

uint64_t folly::Fingerprint< 64 >::shlor64 ( uint64_t  v )

inlineprivate

Definition at line 239 of file Fingerprint.h.

References uint64_t, and v.

                                                   {
  uint64_t out = fp_[0];
  fp_[0] = v;
  return out;
}

template<>

uint64_t folly::Fingerprint< 96 >::shlor64 ( uint64_t  v )

inlineprivate

Definition at line 262 of file Fingerprint.h.

References uint64_t.

                                                   {
  uint64_t out = fp_[0];
  fp_[0] = fp_[1] | (v >> 32);
  fp_[1] = v << 32;
  return out;
}

template<>

uint64_t folly::Fingerprint< 128 >::shlor64 ( uint64_t  v )

inlineprivate

Definition at line 286 of file Fingerprint.h.

References uint64_t, and v.

                                                    {
  uint64_t out = fp_[0];
  fp_[0] = fp_[1];
  fp_[1] = v;
  return out;
}

template<int BITS>

uint8_t folly::Fingerprint< BITS >::shlor8 ( uint8_t  v )

private

template<>

uint8_t folly::Fingerprint< 64 >::shlor8 ( uint8_t  v )

inlineprivate

Definition at line 225 of file Fingerprint.h.

References uint64_t, uint8_t, and v.

                                                {
  uint8_t out = (uint8_t)(fp_[0] >> 56);
  fp_[0] = (fp_[0] << 8) | ((uint64_t)v);
  return out;
}

template<>

uint8_t folly::Fingerprint< 96 >::shlor8 ( uint8_t  v )

inlineprivate

Definition at line 246 of file Fingerprint.h.

References uint64_t, and uint8_t.

                                                {
  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<>

uint8_t folly::Fingerprint< 128 >::shlor8 ( uint8_t  v )

inlineprivate

Definition at line 270 of file Fingerprint.h.

References uint64_t, uint8_t, and 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<int BITS>

static constexpr int folly::Fingerprint< BITS >::size ( )

inlinestatic

Return the number of uint64s needed to hold the fingerprint value.

Definition at line 153 of file Fingerprint.h.

References folly::detail::poly_size().

                              {
    return detail::poly_size(BITS);
  }

template<int BITS>

Fingerprint& folly::Fingerprint< BITS >::update ( StringPiece  str )

inline

Definition at line 142 of file Fingerprint.h.

References c, and uint8_t.

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

template<int BITS>

Fingerprint& folly::Fingerprint< BITS >::update32 ( uint32_t  v )

inline

Definition at line 124 of file Fingerprint.h.

References i, and uint32_t.

Referenced by TEST().

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

template<int BITS>

Fingerprint& folly::Fingerprint< BITS >::update64 ( uint64_t  v )

inline

Definition at line 133 of file Fingerprint.h.

References i, and uint64_t.

Referenced by TEST().

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

template<int BITS>

Fingerprint& folly::Fingerprint< BITS >::update8 ( uint8_t  v )

inline

Definition at line 115 of file Fingerprint.h.

References uint8_t.

Referenced by TEST().

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

template<int BITS>

void folly::Fingerprint< BITS >::write ( uint64_t *  out ) const

inline

Write the computed fingeprint to an array of size() uint64_t's. For Fingerprint<64>, size()==1; we write 64 bits in out[0] For Fingerprint<96>, size()==2; we write 64 bits in out[0] and the most significant 32 bits of out[1] For Fingerprint<128>, size()==2; we write 64 bits in out[0] and 64 bits in out[1].

Definition at line 165 of file Fingerprint.h.

References i, and folly::size().

Referenced by folly::fingerprint128(), folly::fingerprint64(), folly::fingerprint96(), and TEST().

                                  {
    for (int i = 0; i < size(); i++) {
      out[i] = fp_[i];
    }
  }

template<int BITS>

void folly::Fingerprint< BITS >::xortab ( std::array< uint64_t, detail::poly_size(BITS)> const &  tab )

inlineprivate

Definition at line 173 of file Fingerprint.h.

References i, folly::size(), uint32_t, uint64_t, and uint8_t.

                                                                    {
    for (int i = 0; i < size(); i++) {
      fp_[i] ^= tab[i];
    }
  }

Member Data Documentation

template<int BITS>

uint64_t folly::Fingerprint< BITS >::fp_[detail::poly_size(BITS)]

private

Definition at line 186 of file Fingerprint.h.

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/Fingerprint.h