1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
// Part of dump1090, a Mode S message decoder for RTLSDR devices.
//
// icao_filter.c: hashtable for ICAO addresses
//
// Copyright (c) 2014,2015 Oliver Jowett <oliver@mutability.co.uk>
//
// This file is free software: you may copy, redistribute and/or modify it
// under the terms of the GNU General Public License as published by the
// Free Software Foundation, either version 2 of the License, or (at your
// option) any later version.
//
// This file is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
#include "dump1090.h"
// hash table size, must be a power of two:
#define ICAO_FILTER_SIZE 4096
// Millis between filter expiry flips:
#define MODES_ICAO_FILTER_TTL 60000
// Open-addressed hash table with linear probing.
// We store each address twice to handle Data/Parity
// which need to match on a partial address (top 16 bits only).
// Maintain two tables and switch between them to age out entries.
static uint32_t icao_filter_a[ICAO_FILTER_SIZE];
static uint32_t icao_filter_b[ICAO_FILTER_SIZE];
static uint32_t *icao_filter_active;
static uint32_t icaoHash(uint32_t a)
{
// Jenkins one-at-a-time hash, unrolled for 3 bytes
uint32_t hash = 0;
hash += a & 0xff;
hash += hash << 10;
hash ^= hash >> 6;
hash += (a >> 8) & 0xff;
hash += (hash << 10);
hash ^= (hash >> 6);
hash += (a >> 16) & 0xff;
hash += (hash << 10);
hash ^= (hash >> 6);
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash & (ICAO_FILTER_SIZE-1);
}
void icaoFilterInit()
{
memset(icao_filter_a, 0, sizeof(icao_filter_a));
memset(icao_filter_b, 0, sizeof(icao_filter_b));
icao_filter_active = icao_filter_a;
}
void icaoFilterAdd(uint32_t addr)
{
uint32_t h, h0;
h0 = h = icaoHash(addr);
while (icao_filter_active[h] && icao_filter_active[h] != addr) {
h = (h+1) & (ICAO_FILTER_SIZE-1);
if (h == h0) {
fprintf(stderr, "ICAO hash table full, increase ICAO_FILTER_SIZE\n");
return;
}
}
if (!icao_filter_active[h])
icao_filter_active[h] = addr;
// also add with a zeroed top byte, for handling DF20/21 with Data Parity
h0 = h = icaoHash(addr & 0x00ffff);
while (icao_filter_active[h] && (icao_filter_active[h] & 0x00ffff) != (addr & 0x00ffff)) {
h = (h+1) & (ICAO_FILTER_SIZE-1);
if (h == h0) {
fprintf(stderr, "ICAO hash table full, increase ICAO_FILTER_SIZE\n");
return;
}
}
if (!icao_filter_active[h])
icao_filter_active[h] = addr;
}
int icaoFilterTest(uint32_t addr)
{
uint32_t h, h0;
h0 = h = icaoHash(addr);
while (icao_filter_a[h] && icao_filter_a[h] != addr) {
h = (h+1) & (ICAO_FILTER_SIZE-1);
if (h == h0)
break;
}
if (icao_filter_a[h] == addr)
return 1;
h = h0;
while (icao_filter_b[h] && icao_filter_b[h] != addr) {
h = (h+1) & (ICAO_FILTER_SIZE-1);
if (h == h0)
break;
}
if (icao_filter_b[h] == addr)
return 1;
return 0;
}
uint32_t icaoFilterTestFuzzy(uint32_t partial)
{
uint32_t h, h0;
partial &= 0x00ffff;
h0 = h = icaoHash(partial);
while (icao_filter_a[h] && (icao_filter_a[h] & 0x00ffff) != partial) {
h = (h+1) & (ICAO_FILTER_SIZE-1);
if (h == h0)
break;
}
if ((icao_filter_a[h] & 0x00ffff) == partial)
return icao_filter_a[h];
h = h0;
while (icao_filter_b[h] && (icao_filter_b[h] & 0x00ffff) != partial) {
h = (h+1) & (ICAO_FILTER_SIZE-1);
if (h == h0)
break;
}
if ((icao_filter_b[h] & 0x00ffff) == partial)
return icao_filter_b[h];
return 0;
}
// call this periodically:
void icaoFilterExpire()
{
static uint64_t next_flip = 0;
uint64_t now = mstime();
if (now >= next_flip) {
if (icao_filter_active == icao_filter_a) {
memset(icao_filter_b, 0, sizeof(icao_filter_b));
icao_filter_active = icao_filter_b;
} else {
memset(icao_filter_a, 0, sizeof(icao_filter_a));
icao_filter_active = icao_filter_a;
}
next_flip = now + MODES_ICAO_FILTER_TTL;
}
}
|
