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