114262Sodanrc@yahoo.com.br/* 214262Sodanrc@yahoo.com.br * Copyright (c) 2019 Inria 314262Sodanrc@yahoo.com.br * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 414262Sodanrc@yahoo.com.br * All rights reserved. 514262Sodanrc@yahoo.com.br * 614262Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 714262Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 814262Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 914262Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 1014262Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1114262Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1214262Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1314262Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1414262Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1514262Sodanrc@yahoo.com.br * this software without specific prior written permission. 1614262Sodanrc@yahoo.com.br * 1714262Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1814262Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1914262Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2014262Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2114262Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2214262Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2314262Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2414262Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2514262Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2614262Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2714262Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2814262Sodanrc@yahoo.com.br * 2914262Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 3014262Sodanrc@yahoo.com.br */ 3114262Sodanrc@yahoo.com.br 3214262Sodanrc@yahoo.com.br#include "base/filters/multi_bit_sel_bloom_filter.hh" 3314262Sodanrc@yahoo.com.br 3414262Sodanrc@yahoo.com.br#include <limits> 3514262Sodanrc@yahoo.com.br 3614262Sodanrc@yahoo.com.br#include "base/bitfield.hh" 3714262Sodanrc@yahoo.com.br#include "base/logging.hh" 3814262Sodanrc@yahoo.com.br#include "params/BloomFilterMultiBitSel.hh" 3914262Sodanrc@yahoo.com.br 4014262Sodanrc@yahoo.com.brnamespace BloomFilter { 4114262Sodanrc@yahoo.com.br 4214262Sodanrc@yahoo.com.brMultiBitSel::MultiBitSel(const BloomFilterMultiBitSelParams* p) 4314262Sodanrc@yahoo.com.br : Base(p), numHashes(p->num_hashes), 4414262Sodanrc@yahoo.com.br parFilterSize(p->size / numHashes), 4514262Sodanrc@yahoo.com.br isParallel(p->is_parallel), skipBits(p->skip_bits) 4614262Sodanrc@yahoo.com.br{ 4714262Sodanrc@yahoo.com.br if (p->size % numHashes) { 4814262Sodanrc@yahoo.com.br fatal("Can't divide filter (%d) in %d equal portions", p->size, 4914262Sodanrc@yahoo.com.br numHashes); 5014262Sodanrc@yahoo.com.br } 5114262Sodanrc@yahoo.com.br} 5214262Sodanrc@yahoo.com.br 5314262Sodanrc@yahoo.com.brMultiBitSel::~MultiBitSel() 5414262Sodanrc@yahoo.com.br{ 5514262Sodanrc@yahoo.com.br} 5614262Sodanrc@yahoo.com.br 5714262Sodanrc@yahoo.com.brvoid 5814262Sodanrc@yahoo.com.brMultiBitSel::set(Addr addr) 5914262Sodanrc@yahoo.com.br{ 6014262Sodanrc@yahoo.com.br for (int i = 0; i < numHashes; i++) { 6114264Sodanrc@yahoo.com.br filter[hash(addr, i)]++; 6214262Sodanrc@yahoo.com.br } 6314262Sodanrc@yahoo.com.br} 6414262Sodanrc@yahoo.com.br 6514262Sodanrc@yahoo.com.brint 6614262Sodanrc@yahoo.com.brMultiBitSel::getCount(Addr addr) const 6714262Sodanrc@yahoo.com.br{ 6814262Sodanrc@yahoo.com.br int count = 0; 6914262Sodanrc@yahoo.com.br for (int i=0; i < numHashes; i++) { 7014262Sodanrc@yahoo.com.br count += filter[hash(addr, i)]; 7114262Sodanrc@yahoo.com.br } 7214262Sodanrc@yahoo.com.br return count; 7314262Sodanrc@yahoo.com.br} 7414262Sodanrc@yahoo.com.br 7514262Sodanrc@yahoo.com.brint 7614262Sodanrc@yahoo.com.brMultiBitSel::hash(Addr addr, int hash_number) const 7714262Sodanrc@yahoo.com.br{ 7814262Sodanrc@yahoo.com.br uint64_t value = bits(addr, std::numeric_limits<Addr>::digits - 1, 7914262Sodanrc@yahoo.com.br offsetBits) >> skipBits; 8014262Sodanrc@yahoo.com.br const int max_bits = std::numeric_limits<Addr>::digits - offsetBits; 8114262Sodanrc@yahoo.com.br int result = 0; 8214262Sodanrc@yahoo.com.br int bit, i; 8314262Sodanrc@yahoo.com.br 8414262Sodanrc@yahoo.com.br for (i = 0; i < sizeBits; i++) { 8514262Sodanrc@yahoo.com.br bit = (hash_number + numHashes * i) % max_bits; 8614262Sodanrc@yahoo.com.br if (value & (1 << bit)) { 8714262Sodanrc@yahoo.com.br result += 1 << i; 8814262Sodanrc@yahoo.com.br } 8914262Sodanrc@yahoo.com.br } 9014262Sodanrc@yahoo.com.br 9114262Sodanrc@yahoo.com.br if (isParallel) { 9214262Sodanrc@yahoo.com.br return (result % parFilterSize) + hash_number * parFilterSize; 9314262Sodanrc@yahoo.com.br } else { 9414262Sodanrc@yahoo.com.br return result % filter.size(); 9514262Sodanrc@yahoo.com.br } 9614262Sodanrc@yahoo.com.br} 9714262Sodanrc@yahoo.com.br 9814262Sodanrc@yahoo.com.br} // namespace BloomFilter 9914262Sodanrc@yahoo.com.br 10014262Sodanrc@yahoo.com.brBloomFilter::MultiBitSel* 10114262Sodanrc@yahoo.com.brBloomFilterMultiBitSelParams::create() 10214262Sodanrc@yahoo.com.br{ 10314262Sodanrc@yahoo.com.br return new BloomFilter::MultiBitSel(this); 10414262Sodanrc@yahoo.com.br} 10514262Sodanrc@yahoo.com.br 106