bulk_bloom_filter.cc revision 14262
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/bulk_bloom_filter.hh" 3314262Sodanrc@yahoo.com.br 3414262Sodanrc@yahoo.com.br#include <vector> 3514262Sodanrc@yahoo.com.br 3614262Sodanrc@yahoo.com.br#include <limits> 3714262Sodanrc@yahoo.com.br 3814262Sodanrc@yahoo.com.br#include "base/bitfield.hh" 3914262Sodanrc@yahoo.com.br#include "params/BloomFilterBulk.hh" 4014262Sodanrc@yahoo.com.br 4114262Sodanrc@yahoo.com.brnamespace BloomFilter { 4214262Sodanrc@yahoo.com.br 4314262Sodanrc@yahoo.com.brBulk::Bulk(const BloomFilterBulkParams* p) 4414262Sodanrc@yahoo.com.br : Base(p), sectorBits(sizeBits - 1) 4514262Sodanrc@yahoo.com.br{ 4614262Sodanrc@yahoo.com.br} 4714262Sodanrc@yahoo.com.br 4814262Sodanrc@yahoo.com.brBulk::~Bulk() 4914262Sodanrc@yahoo.com.br{ 5014262Sodanrc@yahoo.com.br} 5114262Sodanrc@yahoo.com.br 5214262Sodanrc@yahoo.com.brvoid 5314262Sodanrc@yahoo.com.brBulk::set(Addr addr) 5414262Sodanrc@yahoo.com.br{ 5514262Sodanrc@yahoo.com.br // c0 contains the cache index bits 5614262Sodanrc@yahoo.com.br int c0 = bits(addr, offsetBits + sectorBits - 1, offsetBits); 5714262Sodanrc@yahoo.com.br // c1 contains the lower sectorBits permuted bits 5814262Sodanrc@yahoo.com.br //Address permuted_bits = permute(addr); 5914262Sodanrc@yahoo.com.br int c1 = bits(addr, (offsetBits + 2 * sectorBits) - 1, 6014262Sodanrc@yahoo.com.br offsetBits + sectorBits); 6114262Sodanrc@yahoo.com.br //assert(c0 < (filter_size/2)); 6214262Sodanrc@yahoo.com.br //assert(c0 + (filter_size/2) < filter_size); 6314262Sodanrc@yahoo.com.br //assert(c1 < (filter_size/2)); 6414262Sodanrc@yahoo.com.br // set v0 bit 6514262Sodanrc@yahoo.com.br filter[c0 + (filter.size()/2)] = 1; 6614262Sodanrc@yahoo.com.br // set v1 bit 6714262Sodanrc@yahoo.com.br filter[c1] = 1; 6814262Sodanrc@yahoo.com.br} 6914262Sodanrc@yahoo.com.br 7014262Sodanrc@yahoo.com.brbool 7114262Sodanrc@yahoo.com.brBulk::isSet(Addr addr) const 7214262Sodanrc@yahoo.com.br{ 7314262Sodanrc@yahoo.com.br // c0 contains the cache index bits 7414262Sodanrc@yahoo.com.br const int filter_size = filter.size(); 7514262Sodanrc@yahoo.com.br int c0 = bits(addr, offsetBits + sectorBits - 1, offsetBits); 7614262Sodanrc@yahoo.com.br // c1 contains the lower 10 permuted bits 7714262Sodanrc@yahoo.com.br //Address permuted_bits = permute(addr); 7814262Sodanrc@yahoo.com.br int c1 = bits(addr, (offsetBits + 2 * sectorBits) - 1, 7914262Sodanrc@yahoo.com.br offsetBits + sectorBits); 8014262Sodanrc@yahoo.com.br //assert(c0 < (filter_size/2)); 8114262Sodanrc@yahoo.com.br //assert(c0 + (filter_size/2) < filter_size); 8214262Sodanrc@yahoo.com.br //assert(c1 < (filter_size/2)); 8314262Sodanrc@yahoo.com.br // set v0 bit 8414262Sodanrc@yahoo.com.br std::vector<int> temp_filter(filter.size(), 0); 8514262Sodanrc@yahoo.com.br temp_filter[c0 + (filter_size/2)] = 1; 8614262Sodanrc@yahoo.com.br // set v1 bit 8714262Sodanrc@yahoo.com.br temp_filter[c1] = 1; 8814262Sodanrc@yahoo.com.br 8914262Sodanrc@yahoo.com.br // perform filter intersection. If any c part is 0, no possibility 9014262Sodanrc@yahoo.com.br // of address being in signature. get first c intersection part 9114262Sodanrc@yahoo.com.br bool zero = false; 9214262Sodanrc@yahoo.com.br for (int i = 0; i < filter_size/2; ++i){ 9314262Sodanrc@yahoo.com.br // get intersection of signatures 9414262Sodanrc@yahoo.com.br temp_filter[i] = temp_filter[i] && filter[i]; 9514262Sodanrc@yahoo.com.br zero = zero || temp_filter[i]; 9614262Sodanrc@yahoo.com.br } 9714262Sodanrc@yahoo.com.br zero = !zero; 9814262Sodanrc@yahoo.com.br if (zero) { 9914262Sodanrc@yahoo.com.br // one section is zero, no possiblility of address in signature 10014262Sodanrc@yahoo.com.br // reset bits we just set 10114262Sodanrc@yahoo.com.br temp_filter[c0 + (filter_size / 2)] = 0; 10214262Sodanrc@yahoo.com.br temp_filter[c1] = 0; 10314262Sodanrc@yahoo.com.br return false; 10414262Sodanrc@yahoo.com.br } 10514262Sodanrc@yahoo.com.br 10614262Sodanrc@yahoo.com.br // check second section 10714262Sodanrc@yahoo.com.br zero = false; 10814262Sodanrc@yahoo.com.br for (int i = filter_size / 2; i < filter_size; ++i) { 10914262Sodanrc@yahoo.com.br // get intersection of signatures 11014262Sodanrc@yahoo.com.br temp_filter[i] = temp_filter[i] && filter[i]; 11114262Sodanrc@yahoo.com.br zero = zero || temp_filter[i]; 11214262Sodanrc@yahoo.com.br } 11314262Sodanrc@yahoo.com.br zero = !zero; 11414262Sodanrc@yahoo.com.br if (zero) { 11514262Sodanrc@yahoo.com.br // one section is zero, no possiblility of address in signature 11614262Sodanrc@yahoo.com.br temp_filter[c0 + (filter_size / 2)] = 0; 11714262Sodanrc@yahoo.com.br temp_filter[c1] = 0; 11814262Sodanrc@yahoo.com.br return false; 11914262Sodanrc@yahoo.com.br } 12014262Sodanrc@yahoo.com.br // one section has at least one bit set 12114262Sodanrc@yahoo.com.br temp_filter[c0 + (filter_size / 2)] = 0; 12214262Sodanrc@yahoo.com.br temp_filter[c1] = 0; 12314262Sodanrc@yahoo.com.br return true; 12414262Sodanrc@yahoo.com.br} 12514262Sodanrc@yahoo.com.br 12614262Sodanrc@yahoo.com.brint 12714262Sodanrc@yahoo.com.brBulk::getCount(Addr addr) const 12814262Sodanrc@yahoo.com.br{ 12914262Sodanrc@yahoo.com.br // TODO as in the multi-hashed filters 13014262Sodanrc@yahoo.com.br return 0; 13114262Sodanrc@yahoo.com.br} 13214262Sodanrc@yahoo.com.br 13314262Sodanrc@yahoo.com.brAddr 13414262Sodanrc@yahoo.com.brBulk::hash(Addr addr) const 13514262Sodanrc@yahoo.com.br{ 13614262Sodanrc@yahoo.com.br // permutes the original address bits according to Table 5 13714262Sodanrc@yahoo.com.br Addr part1 = bits(addr, offsetBits + 6, offsetBits), 13814262Sodanrc@yahoo.com.br part2 = bits(addr, offsetBits + 9), 13914262Sodanrc@yahoo.com.br part3 = bits(addr, offsetBits + 11), 14014262Sodanrc@yahoo.com.br part4 = bits(addr, offsetBits + 17), 14114262Sodanrc@yahoo.com.br part5 = bits(addr, offsetBits + 8, offsetBits + 7), 14214262Sodanrc@yahoo.com.br part6 = bits(addr, offsetBits + 10), 14314262Sodanrc@yahoo.com.br part7 = bits(addr, offsetBits + 12), 14414262Sodanrc@yahoo.com.br part8 = bits(addr, offsetBits + 13), 14514262Sodanrc@yahoo.com.br part9 = bits(addr, offsetBits + 16, offsetBits + 15), 14614262Sodanrc@yahoo.com.br part10 = bits(addr, offsetBits + 20, offsetBits + 18), 14714262Sodanrc@yahoo.com.br part11 = bits(addr, offsetBits + 14); 14814262Sodanrc@yahoo.com.br 14914262Sodanrc@yahoo.com.br Addr result = 15014262Sodanrc@yahoo.com.br (part1 << 14) | (part2 << 13) | (part3 << 12) | (part4 << 11) | 15114262Sodanrc@yahoo.com.br (part5 << 9) | (part6 << 8) | (part7 << 7) | (part8 << 6) | 15214262Sodanrc@yahoo.com.br (part9 << 4) | (part10 << 1) | (part11); 15314262Sodanrc@yahoo.com.br 15414262Sodanrc@yahoo.com.br // Select the remaining high-order bits 15514262Sodanrc@yahoo.com.br Addr remaining_bits = bits(addr, std::numeric_limits<Addr>::digits - 1, 15614262Sodanrc@yahoo.com.br offsetBits + 21) << 21; 15714262Sodanrc@yahoo.com.br result = result | remaining_bits; 15814262Sodanrc@yahoo.com.br 15914262Sodanrc@yahoo.com.br return result; 16014262Sodanrc@yahoo.com.br} 16114262Sodanrc@yahoo.com.br 16214262Sodanrc@yahoo.com.br} // namespace BloomFilter 16314262Sodanrc@yahoo.com.br 16414262Sodanrc@yahoo.com.brBloomFilter::Bulk* 16514262Sodanrc@yahoo.com.brBloomFilterBulkParams::create() 16614262Sodanrc@yahoo.com.br{ 16714262Sodanrc@yahoo.com.br return new BloomFilter::Bulk(this); 16814262Sodanrc@yahoo.com.br} 16914262Sodanrc@yahoo.com.br 170