folly::detail::FingerprintPolynomial< DEG > Class Template Reference

#include <FingerprintPolynomial.h>

Public Member Functions
constexpr	FingerprintPolynomial ()
constexpr	FingerprintPolynomial (const uint64_t(&vals)[size()])
constexpr uint64_t	get (size_t i) const
constexpr void	add (const FingerprintPolynomial< DEG > &other)
constexpr void	mulX ()
constexpr void	mulXmod (const FingerprintPolynomial< DEG > &p)
constexpr void	mulXkmod (int k, const FingerprintPolynomial< DEG > &p)
constexpr void	addXk (int k)
constexpr void	setHigh8Bits (uint8_t val)

Static Public Member Functions
static constexpr int	size ()

Private Attributes
uint64_t	val_ [size()] = {}

Detailed Description

template<int DEG>
class folly::detail::FingerprintPolynomial< DEG >

Representation of a polynomial of degree DEG over GF(2) (that is, with binary coefficients).

Probably of no use outside of Fingerprint code; used by GenerateFingerprintTables and the unittest.

Definition at line 32 of file FingerprintPolynomial.h.

Constructor & Destructor Documentation

template<int DEG>

constexpr folly::detail::FingerprintPolynomial< DEG >::FingerprintPolynomial ( )

inline

Definition at line 38 of file FingerprintPolynomial.h.

{}

template<int DEG>

constexpr folly::detail::FingerprintPolynomial< DEG >::FingerprintPolynomial ( const uint64_t(&)  vals[size()] )

inlineexplicit

Definition at line 40 of file FingerprintPolynomial.h.

                                                                           {
    for (int i = 0; i < size(); i++) {
      val_[i] = vals[i];
    }
  }

Member Function Documentation

template<int DEG>

constexpr void folly::detail::FingerprintPolynomial< DEG >::add ( const FingerprintPolynomial< DEG > &  other )

inline

Definition at line 50 of file FingerprintPolynomial.h.

Referenced by folly::detail::FingerprintPolynomial< BITS-1 >::mulXmod().

                                                              {
    for (int i = 0; i < size(); i++) {
      val_[i] ^= other.val_[i];
    }
  }

template<int DEG>

constexpr void folly::detail::FingerprintPolynomial< DEG >::addXk ( int  k )

inline

Definition at line 107 of file FingerprintPolynomial.h.

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

                              {
    int word_offset = (DEG - k) / 64;
    int bit_offset = 63 - (DEG - k) % 64;
    val_[word_offset] ^= (1ULL << bit_offset);
  }

template<int DEG>

constexpr uint64_t folly::detail::FingerprintPolynomial< DEG >::get ( size_t  i ) const

inline

Definition at line 46 of file FingerprintPolynomial.h.

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

                                         {
    return val_[i];
  }

template<int DEG>

constexpr void folly::detail::FingerprintPolynomial< DEG >::mulX ( )

inline

Definition at line 57 of file FingerprintPolynomial.h.

Referenced by folly::detail::FingerprintPolynomial< BITS-1 >::mulXmod().

                        {
    uint64_t b = 0;
    for (int i = size() - 1; i >= 0; i--) {
      uint64_t nb = val_[i] >> 63;
      val_[i] = (val_[i] << 1) | b;
      b = nb;
    }
  }

template<int DEG>

constexpr void folly::detail::FingerprintPolynomial< DEG >::mulXkmod ( int  k, const FingerprintPolynomial< DEG > &  p  )

inline

Definition at line 100 of file FingerprintPolynomial.h.

                                                                      {
    for (int i = 0; i < k; i++) {
      mulXmod(p);
    }
  }

template<int DEG>

constexpr void folly::detail::FingerprintPolynomial< DEG >::mulXmod ( const FingerprintPolynomial< DEG > &  p )

inline

Definition at line 90 of file FingerprintPolynomial.h.

Referenced by folly::detail::FingerprintPolynomial< BITS-1 >::mulXkmod(), and folly::detail::SlowFingerprint< BITS >::updateBit().

                                                              {
    bool needXOR = (val_[0] & (1ULL << 63));
    val_[0] &= ~(1ULL << 63);
    mulX();
    if (needXOR) {
      add(p);
    }
  }

template<int DEG>

constexpr void folly::detail::FingerprintPolynomial< DEG >::setHigh8Bits ( uint8_t  val )

inline

Definition at line 116 of file FingerprintPolynomial.h.

                                           {
    val_[0] = ((uint64_t)val) << (64 - 8);
    for (int i = 1; i < size(); i++) {
      val_[i] = 0;
    }
  }

template<int DEG>

static constexpr int folly::detail::FingerprintPolynomial< DEG >::size ( )

inlinestatic

Definition at line 34 of file FingerprintPolynomial.h.

Referenced by folly::detail::FingerprintPolynomial< BITS-1 >::add(), folly::detail::FingerprintPolynomial< BITS-1 >::FingerprintPolynomial(), folly::detail::FingerprintPolynomial< BITS-1 >::mulX(), folly::detail::FingerprintPolynomial< BITS-1 >::setHigh8Bits(), and folly::detail::SlowFingerprint< BITS >::write().

                              {
    return 1 + DEG / 64;
  }

Member Data Documentation

template<int DEG>

uint64_t folly::detail::FingerprintPolynomial< DEG >::val_[size()] = {}

private

Definition at line 130 of file FingerprintPolynomial.h.

Referenced by folly::detail::FingerprintPolynomial< BITS-1 >::add(), folly::detail::FingerprintPolynomial< BITS-1 >::addXk(), folly::detail::FingerprintPolynomial< BITS-1 >::FingerprintPolynomial(), folly::detail::FingerprintPolynomial< BITS-1 >::get(), folly::detail::FingerprintPolynomial< BITS-1 >::mulX(), folly::detail::FingerprintPolynomial< BITS-1 >::mulXmod(), and folly::detail::FingerprintPolynomial< BITS-1 >::setHigh8Bits().

---

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

• proxygen/folly/folly/detail/FingerprintPolynomial.h