multi_bit_sel_bloom_filter.cc revision 14262:991410960fdb
1/* 2 * Copyright (c) 2019 Inria 3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are 8 * met: redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer; 10 * redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution; 13 * neither the name of the copyright holders nor the names of its 14 * contributors may be used to endorse or promote products derived from 15 * this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 * 29 * Authors: Daniel Carvalho 30 */ 31 32#include "base/filters/multi_bit_sel_bloom_filter.hh" 33 34#include <limits> 35 36#include "base/bitfield.hh" 37#include "base/logging.hh" 38#include "params/BloomFilterMultiBitSel.hh" 39 40namespace BloomFilter { 41 42MultiBitSel::MultiBitSel(const BloomFilterMultiBitSelParams* p) 43 : Base(p), numHashes(p->num_hashes), 44 parFilterSize(p->size / numHashes), 45 isParallel(p->is_parallel), skipBits(p->skip_bits) 46{ 47 if (p->size % numHashes) { 48 fatal("Can't divide filter (%d) in %d equal portions", p->size, 49 numHashes); 50 } 51} 52 53MultiBitSel::~MultiBitSel() 54{ 55} 56 57void 58MultiBitSel::set(Addr addr) 59{ 60 for (int i = 0; i < numHashes; i++) { 61 int idx = hash(addr, i); 62 filter[idx] = 1; 63 } 64} 65 66int 67MultiBitSel::getCount(Addr addr) const 68{ 69 int count = 0; 70 for (int i=0; i < numHashes; i++) { 71 count += filter[hash(addr, i)]; 72 } 73 return count; 74} 75 76int 77MultiBitSel::hash(Addr addr, int hash_number) const 78{ 79 uint64_t value = bits(addr, std::numeric_limits<Addr>::digits - 1, 80 offsetBits) >> skipBits; 81 const int max_bits = std::numeric_limits<Addr>::digits - offsetBits; 82 int result = 0; 83 int bit, i; 84 85 for (i = 0; i < sizeBits; i++) { 86 bit = (hash_number + numHashes * i) % max_bits; 87 if (value & (1 << bit)) { 88 result += 1 << i; 89 } 90 } 91 92 if (isParallel) { 93 return (result % parFilterSize) + hash_number * parFilterSize; 94 } else { 95 return result % filter.size(); 96 } 97} 98 99} // namespace BloomFilter 100 101BloomFilter::MultiBitSel* 102BloomFilterMultiBitSelParams::create() 103{ 104 return new BloomFilter::MultiBitSel(this); 105} 106 107