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/h3_bloom_filter.hh"
33
34#include <limits>
35
36#include "base/bitfield.hh"
37#include "base/logging.hh"
38#include "params/BloomFilterH3.hh"
39
40namespace BloomFilter {
41
42static int H3Matrix[64][16] = {
43    { 33268410,   395488709,  311024285,  456111753,
44      181495008,  119997521,  220697869,  433891432,
45      755927921,  515226970,  719448198,  349842774,
46      269183649,  463275672,  429800228,  521598937,  },
47
48    { 628677802,  820947732,  809435975,  1024657192,
49      887631270,  412050215,  391365090,  324227279,
50      318338329,  1038393087, 489807930,  387366128,
51      518096428,  324184340,  429376066,  447109279,  },
52
53    { 599747653,  404960623,  103933604,  946416030,
54      656460913,  925957005,  1047665689, 163552053,
55      88359290,   841315415,  899833584,  1067336680,
56      348549994,  464045876,  270252128,  829897652,  },
57
58    { 215495230,  966696438,  82589012,   750102795,
59      909780866,  920285789,  769759214,  331966823,
60      939936006,  439950703,  883794828,  1009277508,
61      61634610,   741444350,  98689608,   524144422,  },
62
63    { 93868534,   196958667,  774076619,  327921978,
64      122538783,  879785030,  690748527,  3498564,
65      83163077,   1027963025, 582088444,  466152216,
66      312424878,  550064499,  646612667,  561099434,  },
67
68    { 1002047931, 395477707,  821317480,  890482112,
69      697094476,  263813044,  840275189,  469664185,
70      795625845,  211504898,  99204277,   1004491153,
71      725930417,  1064479221, 893834767,  839719181,  },
72
73    { 278507126,  985111995,  706462983,  1042178726,
74      123281719,  963778122,  500881056,  726291104,
75      134293026,  568379664,  317050609,  533470307,
76      1022365922, 197645211,  315125721,  634827678,  },
77
78    { 219227366,  553960647,  870169525,  322232839,
79      508322497,  648672696,  249405795,  883596102,
80      476433133,  541372919,  646647793,  1042679515,
81      43242483,   600187508,  499866821,  135713210,  },
82
83    { 52837162,   96966684,   401840460,  1071661176,
84      733560065,  150035417,  341319946,  811582750,
85      636173904,  519054065,  196321433,  1028294565,
86      882204070,  522965093,  48884074,   117810166,  },
87
88    { 650860353,  789534698,  328813544,  473250022,
89      143128306,  173196006,  846958825,  174632187,
90      683273509,  405459497,  787235556,  773873501,
91      240110267,  426797736,  92043842,   711789240,  },
92
93    { 586637493,  5059646,    398035664,  6686087,
94      498300175,  948278148,  681227731,  592751744,
95      572019677,  558044722,  589368271,  695745538,
96      1073416749, 529192035,  550984939,  1070620580, },
97
98    { 102904663,  647598516,  758863940,  313426443,
99      76504114,   1050747783, 708436441,  563815069,
100      224107668,  875925186,  167675944,  926209739,
101      279737287,  1040288182, 768184312,  371708956,  },
102
103    { 683968868,  1027427757, 180781926,  742898864,
104      624078545,  645659833,  577225838,  987150210,
105      723410002,  224013421,  993286634,  33188488,
106      247264323,  888018697,  38048664,   189037096,  },
107
108    { 475612146,  426739285,  873726278,  529192871,
109      607715202,  388486246,  987001312,  474493980,
110      259747270,  417465536,  217062395,  392858482,
111      563810075,  137852805,  1051814153, 72895217,   },
112
113    { 71277086,   785496675,  500608842,  89633426,
114      274085706,  248467935,  838061983,  48106147,
115      773662506,  49545328,   9071573,    100739031,
116      602018002,  904371654,  534132064,  332211304,  },
117
118    { 401893602,  735125342,  775548339,  210224843,
119      256081130,  482894412,  350801633,  1035713633,
120      429458128,  327281409,  739927752,  359327650,
121      886942880,  847691759,  752417993,  359445596,  },
122
123    { 267472014,  1050659620, 1068232362, 1049684368,
124      17130239,   690524969,  793224378,  14455158,
125      423092885,  873853424,  430535778,  7867877,
126      309731959,  370260786,  862353083,  403906850,  },
127
128    { 993077283,  218812656,  389234651,  393202875,
129      413116501,  263300295,  470013158,  592730725,
130      441847172,  732392823,  407574059,  875664777,
131      271347307,  792954404,  554774761,  1022424300, },
132
133    { 675919719,  637054073,  784720745,  149714381,
134      813144874,  502525801,  635436670,  1003196587,
135      160786091,  947509775,  969788637,  26854073,
136      257964369,  63898568,   539767732,  772364518,  },
137
138    { 943076868,  1021732472, 697575075,  15843624,
139      617573396,  534113303,  122953324,  964873912,
140      942995378,  87830944,   1012914818, 455484661,
141      592160054,  599844284,  810394353,  836812568,  },
142
143    { 688992674,  279465370,  731582262,  687883235,
144      438178468,  80493001,   342701501,  663561405,
145      23360106,   531315007,  508931618,  36294623,
146      231216223,  840438413,  255665680,  663205938,  },
147
148    { 857265418,  552630887,  8173237,    792122963,
149      210140052,  823124938,  667709953,  751538219,
150      991957789,  462064153,  19070176,   726604748,
151      714567823,  151147895,  1012619677, 697114353,  },
152
153    { 467105652,  683256174,  702387467,  28730434,
154      549942998,  48712701,   960519696,  1008345587,
155      679267717,  370932249,  880419471,  352141567,
156      331640403,  598772468,  95160685,   812053015,  },
157
158    { 1053491323, 430526562,  1014938507, 109685515,
159      765949103,  177288303,  1034642653, 485421658,
160      71850281,   981034542,  61620389,   601367920,
161      504420930,  220599168,  583051998,  158735752,  },
162
163    { 103033901,  522494916,  658494760,  959206022,
164      931348143,  834510661,  21542994,   189699884,
165      679327018,  171983002,  96774168,   456133168,
166      543103352,  923945936,  970074188,  643658485,  },
167
168    { 566379913,  805798263,  840662512,  820206124,
169      796507494,  223712542,  118811519,  662246595,
170      809326534,  416471323,  748027186,  161169753,
171      739149488,  276330378,  924837051,  964873733,  },
172
173    { 585882743,  135502711,  3386031,    625631285,
174      1068193307, 270342640,  432739484,  556606453,
175      826419155,  1038540977, 158000202,  69109538,
176      207087256,  298111218,  678046259,  184611498,  },
177
178    { 305310710,  46237988,   855726974,  735975153,
179      930663798,  425764232,  104362407,  391371443,
180      867622101,  71645091,   61824734,   661902640,
181      293738633,  309416189,  281710675,  879317360,  },
182
183    { 398146324,  398293087,  689145387,  1038451703,
184      521637478,  516134620,  314658937,  830334981,
185      583400300,  340083705,  68029852,   675389876,
186      994635780,  788959180,  406967042,  74403607,   },
187
188    { 69463153,   744427484,  191639960,  590927798,
189      969916795,  546846769,  728756758,  889355646,
190      520855076,  136068426,  776132410,  189663815,
191      252051082,  533662856,  362198652,  1026161384, },
192
193    { 584984279,  1004834381, 568439705,  834508761,
194      21812513,   670870173,  1052043300, 341868768,
195      473755574,  124339439,  36193947,   437997647,
196      137419489,  58705193,   337793711,  340738909,  },
197
198    { 898051466,  512792906,  234874060,  655358775,
199      683745319,  671676404,  428888546,  639928192,
200      672697722,  176477579,  747020991,  758211282,
201      443045009,  205395173,  1016944273, 5584717,    },
202
203    { 156038300,  138620174,  588466825,  1061494056,
204      1013672100, 1064257198, 881417791,  839470738,
205      83519030,   100875683,  237486447,  461483733,
206      681527127,  777996147,  574635362,  815974538,  },
207
208    { 184168473,  519509808,  62531892,   51821173,
209      43787358,   385711644,  141325169,  36069511,
210      584183031,  571372909,  671503175,  226486781,
211      194932686,  1045460970, 753718579,  331442433,  },
212
213    { 73065106,   1015327221, 630916840,  1058053470,
214      306737587,  296343219,  907194989,  920172546,
215      224516225,  818625553,  551143849,  634570650,
216      432966225,  756438259,  939564853,  767999933,  },
217
218    { 884775648,  394862257,  446787794,  219833788,
219      727195727,  728122304,  249888353,  732947974,
220      289908868,  448282580,  618161877,  898939716,
221      739554163,  860631799,  1058977530, 86916736,   },
222
223    { 143850006,  352708694,  200194048,  979764914,
224      629404175,  546279766,  72106714,   860980514,
225      313190585,  897143111,  308425797,  953791785,
226      349924906,  221457005,  950588925,  908254505,  },
227
228    { 950032043,  829868728,  68623614,   714624605,
229      69760597,   297275854,  355894016,  985369737,
230      882852618,  864071289,  958512902,  950910111,
231      991368991,  829645051,  434698210,  771350575,  },
232
233    { 552695074,  319195551,  80297396,   496413831,
234      944046531,  621525571,  617653363,  416729825,
235      441842808,  9847464,    99420657,   1033914550,
236      812966458,  937053011,  673390195,  934577365,  },
237
238    { 1034695843, 190969665,  332900185,  51897434,
239      523888639,  883512843,  146908572,  506785674,
240      565814307,  692255649,  314052926,  826386588,
241      430691325,  866927620,  413880214,  936474339,  },
242
243    { 129380164,  741739952,  1013703462, 494392795,
244      957214600,  1010879043, 931790677,  94551922,
245      988065869,  120637871,  882506912,  395075379,
246      210570485,  812422692,  910383687,  817722285,  },
247
248    { 51850866,   283408630,  1053047202, 858940389,
249      818507731,  477082181,  353546901,  993324368,
250      407093779,  231608253,  1067319867, 73159811,
251      429792535,  971320614,  565699344,  718823399,  },
252
253    { 408185106,  491493570,  596050720,  310776444,
254      703628192,  454438809,  523988035,  728512200,
255      686012353,  976339656,  72816924,   116926720,
256      165866591,  452043792,  866943072,  968545481,  },
257
258    { 443231195,  905907843,  1061421320, 746360489,
259      1043120338, 1069659155, 463359031,  688303227,
260      186550710,  155347339,  1044842421, 1005904570,
261      69332909,   706951903,  422513657,  882038450,  },
262
263    { 430990623,  946501980,  742556791,  278398643,
264      183759217,  659404315,  279754382,  1069347846,
265      843746517,  222777670,  990835599,  548741637,
266      129220580,  1392170,    1032654091, 894058935,  },
267
268    { 452042227,  751640705,  259481376,  765824585,
269      145991469,  1013683228, 1055491225, 536379588,
270      392593350,  913368594,  1029429776, 226857786,
271      31505342,   1054416381, 32341741,   687106649,  },
272
273    { 404750944,  811417027,  869530820,  773491060,
274      810901282,  979340397,  1036910290, 461764404,
275      834235095,  765695033,  604692390,  452158120,
276      928988098,  442719218,  1024059719, 167723114,  },
277
278    { 974245177,  1046377300, 1003424287, 787349855,
279      336314155,  875074696,  1018462718, 890313003,
280      367376809,  86355556,   1020618772, 890710345,
281      444741481,  373230261,  767064947,  840920177,  },
282
283    { 719581124,  431808156,  138301690,  668222575,
284      497413494,  740492013,  485033226,  125301442,
285      831265111,  879071459,  341690480,  152975256,
286      850330086,  717444507,  694225877,  785340566,  },
287
288    { 1032766252, 140959364,  737474726,  1062767538,
289      364464647,  331414723,  356152634,  642832379,
290      158733632,  374691640,  285504811,  345349905,
291      876599880,  476392727,  479589210,  606376325,  },
292
293    { 174997730,  778177086,  319164313,  163614456,
294      10331364,   599358958,  8331663,    237538058,
295      159173957,  174533880,  65588684,   878222844,
296      424467599,  901803515,  187504218,  776690353,  },
297
298    { 803856182,  965850321,  694948067,  218315960,
299      358416571,  683713254,  178069303,  428076035,
300      686176454,  579553217,  357306738,  315018080,
301      886852373,  568563910,  896839725,  257416821,  },
302
303    { 401650013,  183289141,  497957228,  879734476,
304      265024455,  825794561,  889237440,  323359863,
305      100258491,  991414783,  313986632,  85847250,
306      362520248,  276103512,  1041630342, 525981595,  },
307
308    { 487732740,  46201705,   990837834,  62744493,
309      1067364756, 58015363,   690846283,  680262648,
310      997278956,  469357861,  432164624,  996763915,
311      211907847,  167824295,  144928194,  454839915,  },
312
313    { 41404232,   514493300,  259546924,  578217256,
314      972345130,  123299213,  346040332,  1014668104,
315      520910639,  579955198,  36627803,   179072921,
316      547684341,  598950511,  269497394,  854352266,  },
317
318    { 603906768,  100863318,  708837659,  204175569,
319      375560904,  908375384,  28314106,   6303733,
320      175283124,  749851198,  308667367,  415293931,
321      225365403,  1032188331, 977112710,  819705229,  },
322
323    { 399767123,  697985692,  356790426,  643687584,
324      298624218,  185095167,  381653926,  876816342,
325      296720023,  2205879,    235816616,  521850105,
326      622753786,  1021421218, 726349744,  256504902,  },
327
328    { 851245024,  1022500222, 511909628,  313809625,
329      99776025,   39710175,   798739932,  741832408,
330      140631966,  898295927,  607660421,  870669312,
331      1051422478, 789055529,  669113756,  681943450,  },
332
333    { 853872755,  491465269,  503341472,  98019440,
334      258267420,  335602837,  320687824,  1053324395,
335      24932389,   955011453,  934255131,  435625663,
336      501568768,  238967025,  549987406,  248619780,  },
337
338    { 411151284,  576471205,  757985419,  544137226,
339      968135693,  877548443,  194586894,  74882373,
340      248353663,  21207540,   273789651,  853653916,
341      861267970,  533253322,  3739570,    661358586,  },
342
343    { 271430986,  71390029,   257643671,  949329860,
344      348156406,  251939238,  445808698,  48269799,
345      907589462,  105677619,  635451508,  20805932,
346      464874661,  7542147,    243619464,  288304568,  },
347
348    { 368215982,  530288964,  770090421,  660961164,
349      614935537,  630760399,  931299233,  794519275,
350      779918979,  401746493,  561237006,  1027202224,
351      258968003,  339508073,  1050610516, 1064307013, },
352
353    { 1039172162, 448331205,  928997884,  49813151,
354      198712120,  992335354,  671024050,  879525220,
355      745915336,  1038822580, 138669665,  917958819,
356      681422342,  792868818,  924762727,  816386174,  },
357
358    { 515190336,  313808618,  441296783,  1022120897,
359      792325033,  354387581,  59273006,   280075434,
360      411357221,  665274694,  4054464,    1059046246,
361      394261773,  848616745,  15446017,   517723271,  },
362};
363
364H3::H3(const BloomFilterH3Params* p)
365    : MultiBitSel(p)
366{
367    fatal_if(numHashes > 16, "There are only 16 H3 functions implemented.");
368}
369
370H3::~H3()
371{
372}
373
374int
375H3::hash(Addr addr, int hash_number) const
376{
377    uint64_t val =
378        bits(addr, std::numeric_limits<Addr>::digits - 1, offsetBits);
379    int result = 0;
380
381    for (int i = 0; (i < 64) && val; i++, val >>= 1) {
382        if (val & 1) {
383            result ^= H3Matrix[i][hash_number];
384        }
385    }
386
387    if (isParallel) {
388        return (result % parFilterSize) + hash_number * parFilterSize;
389    } else {
390        return result % filter.size();
391    }
392}
393
394} // namespace BloomFilter
395
396BloomFilter::H3*
397BloomFilterH3Params::create()
398{
399    return new BloomFilter::H3(this);
400}
401
402