bloom-filter.cpp

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2014-2020,  The University of Memphis
 *
 * This file is part of PSync.
 * See AUTHORS.md for complete list of PSync authors and contributors.
 *
 * PSync is free software: you can redistribute it and/or modify it under the terms
 * of the GNU Lesser General Public License as published by the Free Software Foundation,
 * either version 3 of the License, or (at your option) any later version.
 *
 * PSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE.  See the GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License along with
 * PSync, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
 *

 * This file incorporates work covered by the following copyright and
 * permission notice:

 * The MIT License (MIT)

 * Copyright (c) 2000 Arash Partow

 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
*/

#include "PSync/detail/bloom-filter.hpp"
#include "PSync/detail/util.hpp"

#include <ndn-cxx/util/exception.hpp>

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <limits>

namespace psync {
namespace detail {

// https://github.com/ArashPartow/bloom

static const std::size_t bits_per_char = 0x08;    // 8 bits in 1 char(unsigned)

static const unsigned char bit_mask[bits_per_char] = {
  0x01,  //00000001
  0x02,  //00000010
  0x04,  //00000100
  0x08,  //00001000
  0x10,  //00010000
  0x20,  //00100000
  0x40,  //01000000
  0x80   //10000000
};

class bloom_parameters
{
public:

   bloom_parameters()
   : minimum_size(1),
     maximum_size(std::numeric_limits<unsigned int>::max()),
     minimum_number_of_hashes(1),
     maximum_number_of_hashes(std::numeric_limits<unsigned int>::max()),
     projected_element_count(200),
     false_positive_probability(1.0 / projected_element_count),
     random_seed(0xA5A5A5A55A5A5A5AULL)
   {}

   inline bool operator!()
   {
      return (minimum_size > maximum_size)      ||
             (minimum_number_of_hashes > maximum_number_of_hashes) ||
             (minimum_number_of_hashes < 1)     ||
             (0 == maximum_number_of_hashes)    ||
             (0 == projected_element_count)     ||
             (false_positive_probability < 0.0) ||
             (std::numeric_limits<double>::infinity() == std::abs(false_positive_probability)) ||
             (0 == random_seed)                 ||
             (0xFFFFFFFFFFFFFFFFULL == random_seed);
   }

   // Allowable min/max size of the bloom filter in bits
   unsigned int minimum_size;
   unsigned int maximum_size;

   // Allowable min/max number of hash functions
   unsigned int minimum_number_of_hashes;
   unsigned int maximum_number_of_hashes;

   // The approximate number of elements to be inserted
   // into the bloom filter, should be within one order
   // of magnitude. The default is 200.
   unsigned int projected_element_count;

   // The approximate false positive probability expected
   // from the bloom filter. The default is assumed to be
   // the reciprocal of the projected_element_count.
   double false_positive_probability;

   unsigned long long int random_seed;

   struct optimal_parameters_t
   {
      optimal_parameters_t()
      : number_of_hashes(0),
        table_size(0)
      {}

      unsigned int number_of_hashes;
      unsigned int table_size;
   };

   optimal_parameters_t optimal_parameters;

   bool compute_optimal_parameters()
   {
      /*
        Note:
        The following will attempt to find the number of hash functions
        and minimum amount of storage bits required to construct a bloom
        filter consistent with the user defined false positive probability
        and estimated element insertion count.
      */

      if (!(*this))
         return false;

      double min_m  = std::numeric_limits<double>::infinity();
      double min_k  = 0.0;
      double k      = 1.0;

      while (k < 1000.0)
      {
         const double numerator   = (- k * projected_element_count);
         const double denominator = std::log(1.0 - std::pow(false_positive_probability, 1.0 / k));

         const double curr_m = numerator / denominator;

         if (curr_m < min_m)
         {
            min_m = curr_m;
            min_k = k;
         }

         k += 1.0;
      }

      optimal_parameters_t& optp = optimal_parameters;

      optp.number_of_hashes = static_cast<unsigned int>(min_k);

      optp.table_size = static_cast<unsigned int>(min_m);

      optp.table_size += (((optp.table_size % bits_per_char) != 0) ? (bits_per_char - (optp.table_size % bits_per_char)) : 0);

      if (optp.number_of_hashes < minimum_number_of_hashes)
         optp.number_of_hashes = minimum_number_of_hashes;
      else if (optp.number_of_hashes > maximum_number_of_hashes)
         optp.number_of_hashes = maximum_number_of_hashes;

      if (optp.table_size < minimum_size)
         optp.table_size = minimum_size;
      else if (optp.table_size > maximum_size)
         optp.table_size = maximum_size;

      return true;
   }

};


BloomFilter::BloomFilter(const bloom_parameters& p)
: projected_element_count_(p.projected_element_count),
  inserted_element_count_(0),
  random_seed_((p.random_seed * 0xA5A5A5A5) + 1),
  desired_false_positive_probability_(p.false_positive_probability)
{
  salt_count_ = p.optimal_parameters.number_of_hashes;
  table_size_ = p.optimal_parameters.table_size;

  generate_unique_salt();

  bit_table_.resize(table_size_ / bits_per_char, static_cast<cell_type>(0x00));
}

static bloom_parameters
makeParameters(unsigned int projected_element_count,
               double false_positive_probability)
{
  bloom_parameters p;
  p.projected_element_count = projected_element_count;
  p.false_positive_probability = false_positive_probability;

  if (!p.compute_optimal_parameters()) {
    NDN_THROW(BloomFilter::Error("Bloom filter parameters are not correct!"));
  }
  return p;
}

BloomFilter::BloomFilter(unsigned int projected_element_count,
                         double false_positive_probability)
  : BloomFilter(makeParameters(projected_element_count, false_positive_probability))
{
}

BloomFilter::BloomFilter(unsigned int projected_element_count,
                         double false_positive_probability,
                         const ndn::name::Component& bfName)
  : BloomFilter(projected_element_count, false_positive_probability)
{
  std::vector<cell_type> table(bfName.value_begin(), bfName.value_end());
  if (table.size() != table_size_ / bits_per_char) {
    NDN_THROW(Error("Bloom filter cannot be decoded!"));
  }
  bit_table_ = std::move(table);
}

void
BloomFilter::appendToName(ndn::Name& name) const
{
  name.appendNumber(projected_element_count_);
  name.appendNumber(static_cast<uint64_t>(desired_false_positive_probability_ * 1000));
  name.append(bit_table_.begin(), bit_table_.end());
}

void
BloomFilter::clear()
{
  std::fill(bit_table_.begin(), bit_table_.end(), static_cast<cell_type>(0x00));
  inserted_element_count_ = 0;
}

void
BloomFilter::insert(const std::string& key)
{
  std::size_t bit_index = 0;
  std::size_t bit       = 0;

  for (std::size_t i = 0; i < salt_.size(); ++i)
  {
    compute_indices(murmurHash3(salt_[i], key), bit_index, bit);

    bit_table_[bit_index / bits_per_char] |= bit_mask[bit];
  }

  ++inserted_element_count_;
}

bool
BloomFilter::contains(const std::string& key) const
{
  std::size_t bit_index = 0;
  std::size_t bit       = 0;

  for (std::size_t i = 0; i < salt_.size(); ++i)
  {
    compute_indices(murmurHash3(salt_[i], key), bit_index, bit);

    if ((bit_table_[bit_index / bits_per_char] & bit_mask[bit]) != bit_mask[bit])
    {
      return false;
    }
  }

  return true;
}

void
BloomFilter::compute_indices(const bloom_type& hash, std::size_t& bit_index, std::size_t& bit) const
{
  bit_index = hash % table_size_;
  bit       = bit_index % bits_per_char;
}

void
BloomFilter::generate_unique_salt()
{
  /*
    Note:
    A distinct hash function need not be implementation-wise
    distinct. In the current implementation "seeding" a common
    hash function with different values seems to be adequate.
  */
  const unsigned int predef_salt_count = 128;

  static const bloom_type predef_salt[predef_salt_count] =
                             {
                                0xAAAAAAAA, 0x55555555, 0x33333333, 0xCCCCCCCC,
                                0x66666666, 0x99999999, 0xB5B5B5B5, 0x4B4B4B4B,
                                0xAA55AA55, 0x55335533, 0x33CC33CC, 0xCC66CC66,
                                0x66996699, 0x99B599B5, 0xB54BB54B, 0x4BAA4BAA,
                                0xAA33AA33, 0x55CC55CC, 0x33663366, 0xCC99CC99,
                                0x66B566B5, 0x994B994B, 0xB5AAB5AA, 0xAAAAAA33,
                                0x555555CC, 0x33333366, 0xCCCCCC99, 0x666666B5,
                                0x9999994B, 0xB5B5B5AA, 0xFFFFFFFF, 0xFFFF0000,
                                0xB823D5EB, 0xC1191CDF, 0xF623AEB3, 0xDB58499F,
                                0xC8D42E70, 0xB173F616, 0xA91A5967, 0xDA427D63,
                                0xB1E8A2EA, 0xF6C0D155, 0x4909FEA3, 0xA68CC6A7,
                                0xC395E782, 0xA26057EB, 0x0CD5DA28, 0x467C5492,
                                0xF15E6982, 0x61C6FAD3, 0x9615E352, 0x6E9E355A,
                                0x689B563E, 0x0C9831A8, 0x6753C18B, 0xA622689B,
                                0x8CA63C47, 0x42CC2884, 0x8E89919B, 0x6EDBD7D3,
                                0x15B6796C, 0x1D6FDFE4, 0x63FF9092, 0xE7401432,
                                0xEFFE9412, 0xAEAEDF79, 0x9F245A31, 0x83C136FC,
                                0xC3DA4A8C, 0xA5112C8C, 0x5271F491, 0x9A948DAB,
                                0xCEE59A8D, 0xB5F525AB, 0x59D13217, 0x24E7C331,
                                0x697C2103, 0x84B0A460, 0x86156DA9, 0xAEF2AC68,
                                0x23243DA5, 0x3F649643, 0x5FA495A8, 0x67710DF8,
                                0x9A6C499E, 0xDCFB0227, 0x46A43433, 0x1832B07A,
                                0xC46AFF3C, 0xB9C8FFF0, 0xC9500467, 0x34431BDF,
                                0xB652432B, 0xE367F12B, 0x427F4C1B, 0x224C006E,
                                0x2E7E5A89, 0x96F99AA5, 0x0BEB452A, 0x2FD87C39,
                                0x74B2E1FB, 0x222EFD24, 0xF357F60C, 0x440FCB1E,
                                0x8BBE030F, 0x6704DC29, 0x1144D12F, 0x948B1355,
                                0x6D8FD7E9, 0x1C11A014, 0xADD1592F, 0xFB3C712E,
                                0xFC77642F, 0xF9C4CE8C, 0x31312FB9, 0x08B0DD79,
                                0x318FA6E7, 0xC040D23D, 0xC0589AA7, 0x0CA5C075,
                                0xF874B172, 0x0CF914D5, 0x784D3280, 0x4E8CFEBC,
                                0xC569F575, 0xCDB2A091, 0x2CC016B4, 0x5C5F4421
                             };

  if (salt_count_ <= predef_salt_count)
  {
    std::copy(predef_salt,
              predef_salt + salt_count_,
              std::back_inserter(salt_));

    for (std::size_t i = 0; i < salt_.size(); ++i)
    {
      /*
         Note:
         This is done to integrate the user defined random seed,
         so as to allow for the generation of unique bloom filter
         instances.
      */
      salt_[i] = salt_[i] * salt_[(i + 3) % salt_.size()] + static_cast<bloom_type>(random_seed_);
    }
  }
  else
  {
    std::copy(predef_salt, predef_salt + predef_salt_count, std::back_inserter(salt_));

    srand(static_cast<unsigned int>(random_seed_));

    while (salt_.size() < salt_count_)
    {
      bloom_type current_salt = static_cast<bloom_type>(rand()) * static_cast<bloom_type>(rand());

      if (0 == current_salt)
        continue;

      if (salt_.end() == std::find(salt_.begin(), salt_.end(), current_salt))
      {
        salt_.push_back(current_salt);
      }
    }
  }
}

} // namespace detail
} // namespace psync