bulk_bloom_filter.cc revision 14263:4a6d5c4a0813
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/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), 81 part7 = bits(addr, offsetBits + 12), 82 part8 = bits(addr, offsetBits + 13), 83 part9 = bits(addr, offsetBits + 16, offsetBits + 15), 84 part10 = bits(addr, offsetBits + 20, offsetBits + 18), 85 part11 = bits(addr, offsetBits + 14); 86 87 Addr result = 88 (part1 << 14) | (part2 << 13) | (part3 << 12) | (part4 << 11) | 89 (part5 << 9) | (part6 << 8) | (part7 << 7) | (part8 << 6) | 90 (part9 << 4) | (part10 << 1) | (part11); 91 92 // Select the remaining high-order bits 93 Addr remaining_bits = bits(addr, std::numeric_limits<Addr>::digits - 1, 94 offsetBits + 21) << 21; 95 result = result | remaining_bits; 96 97 return result; 98} 99 100} // namespace BloomFilter 101 102BloomFilter::Bulk* 103BloomFilterBulkParams::create() 104{ 105 return new BloomFilter::Bulk(this); 106} 107 108