icao_filter.c

// 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 "beastblackbox.h"

// hash table size, must be a power of two:
#define ICAO_FILTER_SIZE 16384

// Millis between filter expiry flips:
#define MODES_ICAO_FILTER_TTL 5000

#define ICAO_PER_LINE 10

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

// Table for unique ICAO's
static uint32_t icao_db[ICAO_FILTER_SIZE];

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));
    memset(icao_db, 0, sizeof(icao_db));
    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;
    }
}

static void icaoAddtoDB_collision(uint32_t addr, uint32_t hash, int depth) {

	uint32_t h;
	h = icaoHash(hash);

	if(!icao_db[h]) {
	icao_db[h] = addr;
	} else
		if (icao_db[h] != addr) {
		if (depth > 5) {printf("ERROR: hash table is full. Some ICAOs are lost!\n"); return;}
		icaoAddtoDB_collision(addr, h, depth + 1); // Hash collision.
		}

}

void icaoAddtoDB(uint32_t addr) {

	uint32_t h;
	h = icaoHash(addr);

	if(!icao_db[h]) {
	icao_db[h] = addr;
	} else
		if (icao_db[h] != addr) {
		icaoAddtoDB_collision(addr, h, 0); // Hash collision. Try to add with double hash
		}

}

void icaoPrintDB() {
	uint32_t i = 0;
	uint32_t row = 0;
	uint32_t total = 0;

	printf("File contains the following ICAOs:\n\n");

	for(i=0; i<ICAO_FILTER_SIZE; i++) {

	if(icao_db[i]) {
		printf("%06X ",icao_db[i]);
		row++;
		total++;
	}

	if(row==ICAO_PER_LINE) {row=0; printf("\n");}
	}
	printf("\n\n");
	printf("Total found %d unique ICAOs\n", total);
}