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 filter[hash(addr, i)]++; 62 } 63} 64 65int 66MultiBitSel::getCount(Addr addr) const 67{ 68 int count = 0; 69 for (int i=0; i < numHashes; i++) { 70 count += filter[hash(addr, i)]; 71 } 72 return count; 73} 74 75int 76MultiBitSel::hash(Addr addr, int hash_number) const 77{ 78 uint64_t value = bits(addr, std::numeric_limits<Addr>::digits - 1, 79 offsetBits) >> skipBits; 80 const int max_bits = std::numeric_limits<Addr>::digits - offsetBits; 81 int result = 0; 82 int bit, i; 83 84 for (i = 0; i < sizeBits; i++) { 85 bit = (hash_number + numHashes * i) % max_bits; 86 if (value & (1 << bit)) { 87 result += 1 << i; 88 } 89 } 90 91 if (isParallel) { 92 return (result % parFilterSize) + hash_number * parFilterSize; 93 } else { 94 return result % filter.size(); 95 } 96} 97 98} // namespace BloomFilter 99 100BloomFilter::MultiBitSel* 101BloomFilterMultiBitSelParams::create() 102{ 103 return new BloomFilter::MultiBitSel(this); 104} 105 106