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 --- 17 unchanged lines hidden (view full) --- 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/bulk_bloom_filter.hh" 33 |
34#include <limits> 35 36#include "base/bitfield.hh" |
37#include "base/logging.hh" |
38#include "params/BloomFilterBulk.hh" 39 40namespace BloomFilter { 41 42Bulk::Bulk(const BloomFilterBulkParams* p) |
43 : MultiBitSel(p), sectorBits(floorLog2(parFilterSize)) |
44{ |
45 fatal_if((numHashes * sectorBits) > 46 (std::numeric_limits<Addr>::digits - offsetBits), 47 "Sectors need more bits than available"); |
48} 49 50Bulk::~Bulk() 51{ 52} 53 |
54int 55Bulk::hash(Addr addr, int hash_number) const |
56{ |
57 addr = permute(addr); |
58 |
59 // Get the sector-based c index 60 int c = bits(addr, (offsetBits + (hash_number + 1) * sectorBits) - 1, 61 offsetBits + hash_number * sectorBits); 62 assert(c < filter.size()/numHashes); |
63 |
64 // Transform the sector-based c index into a filder index (v) 65 c += (numHashes - 1 - hash_number) * (filter.size()/numHashes); 66 assert(c < filter.size()); |
67 |
68 return c; |
69} 70 |
71Addr |
72Bulk::permute(Addr addr) const |
73{ 74 // permutes the original address bits according to Table 5 75 Addr part1 = bits(addr, offsetBits + 6, offsetBits), 76 part2 = bits(addr, offsetBits + 9), 77 part3 = bits(addr, offsetBits + 11), 78 part4 = bits(addr, offsetBits + 17), 79 part5 = bits(addr, offsetBits + 8, offsetBits + 7), 80 part6 = bits(addr, offsetBits + 10), --- 27 unchanged lines hidden --- |