6488086c24edd4cbb3aaf8ce4ce735e9a9f4d249
2 * Copyright (c) 2019 Inria
3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
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.
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.
29 * Authors: Daniel Carvalho
32 #include "base/filters/bulk_bloom_filter.hh"
38 #include "base/bitfield.hh"
39 #include "params/BloomFilterBulk.hh"
41 namespace BloomFilter
{
43 Bulk::Bulk(const BloomFilterBulkParams
* p
)
44 : Base(p
), sectorBits(sizeBits
- 1)
55 // c0 contains the cache index bits
56 int c0
= bits(addr
, offsetBits
+ sectorBits
- 1, offsetBits
);
57 // c1 contains the lower sectorBits permuted bits
58 //Address permuted_bits = permute(addr);
59 int c1
= bits(addr
, (offsetBits
+ 2 * sectorBits
) - 1,
60 offsetBits
+ sectorBits
);
61 //assert(c0 < (filter_size/2));
62 //assert(c0 + (filter_size/2) < filter_size);
63 //assert(c1 < (filter_size/2));
65 filter
[c0
+ (filter
.size()/2)] = 1;
71 Bulk::isSet(Addr addr
) const
73 // c0 contains the cache index bits
74 const int filter_size
= filter
.size();
75 int c0
= bits(addr
, offsetBits
+ sectorBits
- 1, offsetBits
);
76 // c1 contains the lower 10 permuted bits
77 //Address permuted_bits = permute(addr);
78 int c1
= bits(addr
, (offsetBits
+ 2 * sectorBits
) - 1,
79 offsetBits
+ sectorBits
);
80 //assert(c0 < (filter_size/2));
81 //assert(c0 + (filter_size/2) < filter_size);
82 //assert(c1 < (filter_size/2));
84 std::vector
<int> temp_filter(filter
.size(), 0);
85 temp_filter
[c0
+ (filter_size
/2)] = 1;
89 // perform filter intersection. If any c part is 0, no possibility
90 // of address being in signature. get first c intersection part
92 for (int i
= 0; i
< filter_size
/2; ++i
){
93 // get intersection of signatures
94 temp_filter
[i
] = temp_filter
[i
] && filter
[i
];
95 zero
= zero
|| temp_filter
[i
];
99 // one section is zero, no possiblility of address in signature
100 // reset bits we just set
101 temp_filter
[c0
+ (filter_size
/ 2)] = 0;
106 // check second section
108 for (int i
= filter_size
/ 2; i
< filter_size
; ++i
) {
109 // get intersection of signatures
110 temp_filter
[i
] = temp_filter
[i
] && filter
[i
];
111 zero
= zero
|| temp_filter
[i
];
115 // one section is zero, no possiblility of address in signature
116 temp_filter
[c0
+ (filter_size
/ 2)] = 0;
120 // one section has at least one bit set
121 temp_filter
[c0
+ (filter_size
/ 2)] = 0;
127 Bulk::getCount(Addr addr
) const
129 // TODO as in the multi-hashed filters
134 Bulk::hash(Addr addr
) const
136 // permutes the original address bits according to Table 5
137 Addr part1
= bits(addr
, offsetBits
+ 6, offsetBits
),
138 part2
= bits(addr
, offsetBits
+ 9),
139 part3
= bits(addr
, offsetBits
+ 11),
140 part4
= bits(addr
, offsetBits
+ 17),
141 part5
= bits(addr
, offsetBits
+ 8, offsetBits
+ 7),
142 part6
= bits(addr
, offsetBits
+ 10),
143 part7
= bits(addr
, offsetBits
+ 12),
144 part8
= bits(addr
, offsetBits
+ 13),
145 part9
= bits(addr
, offsetBits
+ 16, offsetBits
+ 15),
146 part10
= bits(addr
, offsetBits
+ 20, offsetBits
+ 18),
147 part11
= bits(addr
, offsetBits
+ 14);
150 (part1
<< 14) | (part2
<< 13) | (part3
<< 12) | (part4
<< 11) |
151 (part5
<< 9) | (part6
<< 8) | (part7
<< 7) | (part8
<< 6) |
152 (part9
<< 4) | (part10
<< 1) | (part11
);
154 // Select the remaining high-order bits
155 Addr remaining_bits
= bits(addr
, std::numeric_limits
<Addr
>::digits
- 1,
156 offsetBits
+ 21) << 21;
157 result
= result
| remaining_bits
;
162 } // namespace BloomFilter
165 BloomFilterBulkParams::create()
167 return new BloomFilter::Bulk(this);