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;
}
}
|