folly::detail::SlowFingerprint< BITS > Class Template Reference

#include <SlowFingerprint.h>

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

Private Member Functions
void	updateBit (bool bit)
void	updateLSB (uint64_t val, int bits)

Private Attributes
const FingerprintPolynomial< BITS-1 >	poly_
FingerprintPolynomial< BITS-1 >	fp_

Detailed Description

template<int BITS>
class folly::detail::SlowFingerprint< BITS >

Slow, one-bit-at-a-time implementation of the Rabin fingerprint.

This is useful as a reference implementation to test the Broder optimization for correctness in the unittest; it's probably too slow for any real use.

Definition at line 33 of file SlowFingerprint.h.

Constructor & Destructor Documentation

template<int BITS>

folly::detail::SlowFingerprint< BITS >::SlowFingerprint ( )

inline

Definition at line 35 of file SlowFingerprint.h.

References folly::detail::FingerprintPolynomial< DEG >::addXk(), and folly::detail::SlowFingerprint< BITS >::fp_.

                    : poly_(FingerprintTable<BITS>::poly) {
    // Use the same starting value as Fingerprint, (1 << (BITS-1))
    fp_.addXk(BITS - 1);
  }

Member Function Documentation

template<int BITS>

SlowFingerprint& folly::detail::SlowFingerprint< BITS >::update ( const folly::StringPiece  str )

inline

Definition at line 55 of file SlowFingerprint.h.

References i, folly::Range< Iter >::size(), folly::Range< Iter >::start(), and folly::detail::SlowFingerprint< BITS >::update8().

                                                      {
    const char* p = str.start();
    for (int i = str.size(); i != 0; p++, i--) {
      update8(static_cast<uint8_t>(*p));
    }
    return *this;
  }

template<int BITS>

SlowFingerprint& folly::detail::SlowFingerprint< BITS >::update32 ( uint32_t  v )

inline

Definition at line 45 of file SlowFingerprint.h.

References folly::detail::SlowFingerprint< BITS >::updateLSB().

                                        {
    updateLSB(v, 32);
    return *this;
  }

template<int BITS>

SlowFingerprint& folly::detail::SlowFingerprint< BITS >::update64 ( uint64_t  v )

inline

Definition at line 50 of file SlowFingerprint.h.

References folly::detail::SlowFingerprint< BITS >::updateLSB().

Referenced by TEST().

                                        {
    updateLSB(v, 64);
    return *this;
  }

template<int BITS>

SlowFingerprint& folly::detail::SlowFingerprint< BITS >::update8 ( uint8_t  v )

inline

Definition at line 40 of file SlowFingerprint.h.

References folly::detail::SlowFingerprint< BITS >::updateLSB().

Referenced by folly::detail::SlowFingerprint< BITS >::update().

                                      {
    updateLSB(v, 8);
    return *this;
  }

template<int BITS>

void folly::detail::SlowFingerprint< BITS >::updateBit ( bool  bit )

inlineprivate

Definition at line 70 of file SlowFingerprint.h.

References folly::detail::FingerprintPolynomial< DEG >::addXk(), folly::detail::SlowFingerprint< BITS >::fp_, folly::detail::FingerprintPolynomial< DEG >::mulXmod(), and folly::detail::SlowFingerprint< BITS >::poly_.

Referenced by folly::detail::SlowFingerprint< BITS >::updateLSB().

                           {
    fp_.mulXmod(poly_);
    if (bit) {
      fp_.addXk(0);
    }
  }

template<int BITS>

void folly::detail::SlowFingerprint< BITS >::updateLSB ( uint64_t  val, int  bits  )

inlineprivate

Definition at line 77 of file SlowFingerprint.h.

References folly::detail::SlowFingerprint< BITS >::updateBit().

Referenced by folly::detail::SlowFingerprint< BITS >::update32(), folly::detail::SlowFingerprint< BITS >::update64(), and folly::detail::SlowFingerprint< BITS >::update8().

                                         {
    val <<= (64 - bits);
    for (; bits != 0; --bits) {
      updateBit(val & (1ULL << 63));
      val <<= 1;
    }
  }

template<int BITS>

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

inline

Definition at line 63 of file SlowFingerprint.h.

References folly::detail::SlowFingerprint< BITS >::fp_, folly::detail::FingerprintPolynomial< DEG >::get(), i, and folly::detail::FingerprintPolynomial< DEG >::size().

Referenced by TEST().

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

Member Data Documentation

template<int BITS>

FingerprintPolynomial<BITS - 1> folly::detail::SlowFingerprint< BITS >::fp_

private

Definition at line 86 of file SlowFingerprint.h.

Referenced by folly::detail::SlowFingerprint< BITS >::SlowFingerprint(), folly::detail::SlowFingerprint< BITS >::updateBit(), and folly::detail::SlowFingerprint< BITS >::write().

template<int BITS>

const FingerprintPolynomial<BITS - 1> folly::detail::SlowFingerprint< BITS >::poly_

private

Definition at line 85 of file SlowFingerprint.h.

Referenced by folly::detail::SlowFingerprint< BITS >::updateBit().

---

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

• proxygen/folly/folly/detail/SlowFingerprint.h