#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>

#include <netdb.h>
#include <arpa/inet.h>
#include <netinet/in.h>

typedef struct _acl_ip_data acl_ip_data;

struct _acl_ip_data {
    struct in_addr addr1;	/* if addr2 non-zero then its a range */
    struct in_addr addr2;
    struct in_addr mask;
    acl_ip_data *next;
};

#if defined(USE_BIN_TREE)
#include "tree.h"
#endif

#if defined(USE_SPLAY_TREE)
#include "splay.h"
#endif

static struct in_addr no_addr;
static struct in_addr any_addr;
static const char *const w_space = " \t\r\n";
static int cmp_count;

static int aclMatchIp(void *dataptr, struct in_addr c);
static int decode_addr(const char *, struct in_addr *, struct in_addr *);
static int safe_inet_addr(const char *buf, struct in_addr *addr);
static char *strtokFile(void);
int foo(acl_ip_data *i);

#if defined(USE_SPLAY_TREE)
static int aclIpNetworkCompare(const void *, splayNode *);
#endif

#if defined(USE_BIN_TREE)
static int bintreeNetworkCompare(void *, void *);
static int bintreeIpNetworkCompare(void *, void *);
#endif

#if defined(USE_BIN_TREE)
static int aclParseIpList(void **curtree);
#else
static int aclParseIpList(void *curlist);
#endif

/*
 * Decode a ascii representation (asc) of a IP adress, and place
 * adress and netmask information in addr and mask.
 * This function should NOT be called if 'asc' is a hostname!
 */
static int
decode_addr(const char *asc, struct in_addr *addr, struct in_addr *mask)
{
    unsigned int a;
    int a1 = 0, a2 = 0, a3 = 0, a4 = 0;
    switch (sscanf(asc, "%d.%d.%d.%d", &a1, &a2, &a3, &a4)) {
    case 4:			/* a dotted quad */
	if (!safe_inet_addr(asc, addr)) {
	    fprintf(stderr, "decode_addr: unsafe IP address: '%s'\n", asc);
	    abort();
	}
	break;
    case 1:			/* a significant bits value for a mask */
	if (a1 >= 0 && a1 < 33) {
	    addr->s_addr = a1 ? htonl(0xfffffffful << (32 - a1)) : 0;
	    break;
	}
    default:
	fprintf(stderr, "decode_addr: Invalid IP address '%s'\n", asc);
	return 0;		/* This is not valid address */
	break;
    }
    if (mask != NULL) {		/* mask == NULL if called to decode a netmask */
	/* Guess netmask */
	a = (unsigned int) ntohl(addr->s_addr);
	if (!(a & 0xFFFFFFFFul))
	    mask->s_addr = htonl(0x00000000ul);
	else if (!(a & 0x00FFFFFF))
	    mask->s_addr = htonl(0xFF000000ul);
	else if (!(a & 0x0000FFFF))
	    mask->s_addr = htonl(0xFFFF0000ul);
	else if (!(a & 0x000000FF))
	    mask->s_addr = htonl(0xFFFFFF00ul);
	else
	    mask->s_addr = htonl(0xFFFFFFFFul);
    }
    return 1;
}


#define SCAN_ACL1       "%[0123456789.]-%[0123456789.]/%[0123456789.]"
#define SCAN_ACL2       "%[0123456789.]-%[0123456789.]"
#define SCAN_ACL3       "%[0123456789.]/%[0123456789.]"
#define SCAN_ACL4       "%[0123456789.]"

static acl_ip_data *
aclParseIpData(const char *t)
{
    static char addr1[256];
    static char addr2[256];
    static char mask[256];
    acl_ip_data *q = calloc(1, sizeof(acl_ip_data));
    /*fprintf(stderr, "aclParseIpData: %s\n", t); */
    if (!strcasecmp(t, "all")) {
	q->addr1.s_addr = 0;
	q->addr2.s_addr = 0;
	q->mask.s_addr = 0;
	return q;
    }
    if (sscanf(t, SCAN_ACL1, addr1, addr2, mask) == 3) {
	(void) 0;
    } else if (sscanf(t, SCAN_ACL2, addr1, addr2) == 2) {
	mask[0] = '\0';
    } else if (sscanf(t, SCAN_ACL3, addr1, mask) == 2) {
	addr2[0] = '\0';
    } else if (sscanf(t, SCAN_ACL4, addr1) == 1) {
	addr2[0] = '\0';
	mask[0] = '\0';
    } else if (sscanf(t, "%[^/]/%s", addr1, mask) == 2) {
	addr2[0] = '\0';
    } else if (sscanf(t, "%s", addr1) == 1) {
	fprintf(stderr, "hostnames not supported\n");
    } else {
	fprintf(stderr, "aclParseIpData: Bad host/IP: '%s'\n", t);
	free(q);
	q = NULL;
	return NULL;
    }
    /* Decode addr1 */
    if (!decode_addr(addr1, &q->addr1, &q->mask)) {
	fprintf(stderr, "aclParseIpData: Ignoring invalid IP acl entry: unknown first address '%s'\n", addr1);
	free(q);
	q = NULL;
	return NULL;
    }
    /* Decode addr2 */
    if (*addr2 && !decode_addr(addr2, &q->addr2, &q->mask)) {
	fprintf(stderr, "aclParseIpData: Ignoring invalid IP acl entry: unknown second address '%s'\n", addr2);
	free(q);
	q = NULL;
	return NULL;
    }
    /* Decode mask */
    if (*mask && !decode_addr(mask, &q->mask, NULL)) {
	fprintf(stderr, "aclParseIpData: Ignoring invalid IP acl entry: unknown netmask '%s'\n", mask);
	free(q);
	q = NULL;
	return NULL;
    }
    q->addr1.s_addr &= q->mask.s_addr;
    q->addr2.s_addr &= q->mask.s_addr;
    /* 1.2.3.4/255.255.255.0  --> 1.2.3.0 */
    return q;
}

/******************/
/* aclParseIpList */
/******************/

#if defined(USE_SPLAY_TREE)
static int
aclParseIpList(void *curlist)
{
    char *t = NULL;
    splayNode **Top = curlist;
    acl_ip_data *q = NULL;
    int n = 0;
    while ((t = strtokFile())) {
	     n++;
	q = aclParseIpData(t);
	while (q != NULL) {
	    *Top = splay_insert(q, *Top, aclIpNetworkCompare);
	    q = q->next;
	}
    }
    return n;
}

#elif defined(USE_BIN_TREE)
static int
aclParseIpList(void **curtree)
{
    tree **Tree;
    char *t = NULL;
    acl_ip_data *q;
    acl_ip_data *x;
    int n = 0;
    Tree = malloc(sizeof(tree *));
    *curtree = Tree;
    tree_init(Tree);
    while ((t = strtokFile())) {
	n++;
	q = aclParseIpData(t);
	while (q != NULL) {
#if DEBUG
fprintf(stderr, "q->addr1 = %s\n", inet_ntoa(q->addr1));
fprintf(stderr, "q->mask  = %s\n", inet_ntoa(q->mask));
fprintf(stderr, "q->addr2 = %s\n", inet_ntoa(q->addr2));
#endif
            x = tree_srch(Tree, bintreeIpNetworkCompare, &q->addr1);
            if (NULL != x) {
                fprintf(stderr, "aclParseIpList: Ignoring duplicate/clashing entry\n"
);
                fprintf(stderr, "--> %s already exists\n", inet_ntoa(x->addr1));
                fprintf(stderr, "--> %s is ignored\n", inet_ntoa(q->addr1));
            } else {
                tree_add(Tree, bintreeNetworkCompare, q, NULL);
            }
	    q = q->next;
	}
    }
    return n;
}

#else
static int
aclParseIpList(void *curlist)
{
    char *t = NULL;
    acl_ip_data **Tail;
    acl_ip_data *q = NULL;
    int n = 0;
    for (Tail = curlist; *Tail; Tail = &((*Tail)->next));
    while ((t = strtokFile())) {
	n++;
	q = aclParseIpData(t);
	*(Tail) = q;
	while (q != NULL) {
	    Tail = &q->next;
	    q = q->next;
	}
    }
    return n;
}

#endif /* USE_SPLAY_TREE */

#if defined(USE_SPLAY_TREE)
static int
aclMatchIp(void *dataptr, struct in_addr c)
{
    splayNode **Top = dataptr;
#if DEBUG
    fprintf(stderr, "aclMatchIp: Looking for match on '%s'\n", inet_ntoa(c));
#endif
    *Top = splay_splay(&c, *Top, aclIpNetworkCompare);
#if DEBUG
    fprintf(stderr, "aclMatchIp: '%s' %s\n",
	inet_ntoa(c), splayLastResult ? "NOT found" : "found");
#endif
    return !splayLastResult;
}

#elif defined(USE_BIN_TREE)
static int
aclMatchIp(void *dataptr, struct in_addr c)
{
    tree ***data = dataptr;
    if (tree_srch(*data, bintreeIpNetworkCompare, &c)) {
#if DEBUG
	fprintf(stderr, "aclMatchIp: '%s' found\n", inet_ntoa(c));
#endif
	return 1;
    }
#if DEBUG
    fprintf(stderr, "aclMatchIp: '%s' NOT found\n", inet_ntoa(c));
#endif
    return 0;
}

#else
static int
aclMatchIp(void *dataptr, struct in_addr c)
{
    acl_ip_data **D = dataptr;
    acl_ip_data *data = *D;
    struct in_addr h;
    unsigned long lh, la1, la2;
    acl_ip_data *first, *prev;

    first = data;		/* remember first element, this will never be moved */
    prev = NULL;		/* previous element in the list */
    while (data) {
	cmp_count++;
	h.s_addr = c.s_addr & data->mask.s_addr;
	if (!data->addr2.s_addr) {
	    if (h.s_addr == data->addr1.s_addr) {
		if (prev != NULL) {
		    /* shift the element just found to the second position
		     * in the list */
		    prev->next = data->next;
		    data->next = first->next;
		    first->next = data;
		}
#if DEBUG
		fprintf(stderr, "aclMatchIp: '%s' found\n", inet_ntoa(c));
#endif
		return 1;
	    }
	} else {
	    /* This is a range check */
	    lh = ntohl(h.s_addr);
	    la1 = ntohl(data->addr1.s_addr);
	    la2 = ntohl(data->addr2.s_addr);
	    if (lh >= la1 && lh <= la2) {
		if (prev != NULL) {
		    /* shift the element just found to the second position
		     * in the list */
		    prev->next = data->next;
		    data->next = first->next;
		    first->next = data;
		}
#if DEBUG
		fprintf(stderr, "aclMatchIp: '%s' found\n", inet_ntoa(c));
#endif
		return 1;
	    }
	}
	prev = data;
	data = data->next;
    }
#if DEBUG
    fprintf(stderr, "aclMatchIp: '%s' NOT found\n", inet_ntoa(c));
#endif
    return 0;
}

#endif /* USE_SPLAY_TREE */











/* compare two network specs
 * 
 * NOTE: this is very similar to aclIpNetworkCompare and it's not yet
 * clear whether this OK. The problem could be with when a network
 * is a subset of the other networks:
 * 
 * 128.1.2.0/255.255.255.128 == 128.1.2.0/255.255.255.0 ?
 * 
 * Currently only the first address of the first network is used.
 */

#if defined(USE_BIN_TREE)
static int
networkCompare(acl_ip_data * net, acl_ip_data * data)
{
    struct in_addr addr;
    acl_ip_data acl_ip;
    int rc = 0;
    memcpy(&acl_ip, net, sizeof(acl_ip));
    addr = acl_ip.addr1;
    addr.s_addr &= data->mask.s_addr;	/* apply netmask */
    if (data->addr2.s_addr == 0) {	/* single address check */
	if (ntohl(addr.s_addr) > ntohl(data->addr1.s_addr))
	    rc = 1;
	else if (ntohl(addr.s_addr) < ntohl(data->addr1.s_addr))
	    rc = -1;
	else
	    rc = 0;
    } else {			/* range address check */
	if (ntohl(addr.s_addr) > ntohl(data->addr2.s_addr))
	    rc = 1;
	else if (ntohl(addr.s_addr) < ntohl(data->addr1.s_addr))
	    rc = -1;
	else
	    rc = 0;
    }
    return rc;
}
#endif /* USE_BIN_TREE */

/* compare an address and a network spec */

#if defined(USE_SPLAY_TREE)
static int
aclIpNetworkCompare(const void *a, splayNode * n)
{
    struct in_addr A = *(struct in_addr *) a;
    acl_ip_data *q = n->data;
    struct in_addr B = q->addr1;
    struct in_addr C = q->addr2;
    int rc = 0;
    cmp_count++;
    A.s_addr &= q->mask.s_addr;	/* apply netmask */
    if (C.s_addr == 0) {	/* single address check */
	if (ntohl(A.s_addr) > ntohl(B.s_addr))
	    rc = 1;
	else if (ntohl(A.s_addr) < ntohl(B.s_addr))
	    rc = -1;
	else
	    rc = 0;
#if DEBUG
fprintf(stderr, "A = %s\n", inet_ntoa(A));
fprintf(stderr, "B = %s\n", inet_ntoa(B));
fprintf(stderr, "rc = %d\n", rc);
#endif
    } else {			/* range address check */
	if (ntohl(A.s_addr) > ntohl(C.s_addr))
	    rc = 1;
	else if (ntohl(A.s_addr) < ntohl(B.s_addr))
	    rc = -1;
	else
	    rc = 0;
    }
    return rc;
}

#elif defined(USE_BIN_TREE)
static int
aclIpNetworkCompare(struct in_addr addr, acl_ip_data * data)
{
    int rc = 0;
    addr.s_addr &= data->mask.s_addr;	/* apply netmask */
    cmp_count++;
    if (data->addr2.s_addr == any_addr.s_addr) {	/* single address check */
	if (ntohl(addr.s_addr) > ntohl(data->addr1.s_addr))
	    rc = 1;
	else if (ntohl(addr.s_addr) < ntohl(data->addr1.s_addr))
	    rc = -1;
	else
	    rc = 0;
#if DEBUG
fprintf(stderr, "addr = %s\n", inet_ntoa(addr));
fprintf(stderr, "data->addr1 = %s\n", inet_ntoa(data->addr1));
fprintf(stderr, "rc = %d\n", rc);
#endif
    } else {			/* range address check */
	if (ntohl(addr.s_addr) > ntohl(data->addr2.s_addr))
	    rc = 1;
	else if (ntohl(addr.s_addr) < ntohl(data->addr1.s_addr))
	    rc = -1;
	else
	    rc = 0;
    }
    return rc;
}

#endif /* USE_SPLAY_TREE || USE_BIN_TREE */


#if USE_BIN_TREE
static int
bintreeNetworkCompare(void *t1, void *t2)
{
    return networkCompare((acl_ip_data *) t1,
	(acl_ip_data *) t2);
}

static int
bintreeIpNetworkCompare(void *t1, void *t2)
{
    struct in_addr addr;
    acl_ip_data *data;
    int r;
    memcpy(&addr, t1, sizeof(addr));
    data = (acl_ip_data *) t2;
    r =  aclIpNetworkCompare(addr, data);
    return r;
}

#endif /* USE_BIN_TREE */

static int
safe_inet_addr(const char *buf, struct in_addr *addr)
{
    static char addrbuf[32];
    int a1 = 0, a2 = 0, a3 = 0, a4 = 0;
    struct in_addr A;
    if (sscanf(buf, "%d.%d.%d.%d", &a1, &a2, &a3, &a4) != 4)
	return 0;
    if (a1 < 0 || a1 > 255)
	return 0;
    if (a2 < 0 || a2 > 255)
	return 0;
    if (a3 < 0 || a3 > 255)
	return 0;
    if (a4 < 0 || a4 > 255)
	return 0;
    sprintf(addrbuf, "%d.%d.%d.%d", a1, a2, a3, a4);
    A.s_addr = inet_addr(addrbuf);
    if (addr)
	addr->s_addr = A.s_addr;
    return 1;
}

FILE *fp = NULL;

static char *
strtokFile(void)
{
    char buf[1024];
    char *t;
    assert(fp != NULL);
    t = fgets(buf, 1024, fp);
    if (t == NULL)
	return NULL;
    strtok(t, w_space);
    return t;
}

int
foo(acl_ip_data *i)
{
    fprintf(stderr, "foo: [%p] %s\n", i, inet_ntoa(i->addr1));
    return 1;
}

void
dump_hist(int *hist, int N)
{
	int i;
	for (i=0; i<N; i++) {
		if (*(hist+i) == 0)
			continue;
		printf("hist[%d] = %d\n", i, *(hist+i));
	}
}

int
main(int argc, char *argv[])
{
    char buf[1024];
    struct in_addr addr;
    void *I = NULL;
    int allowed = 0;
    int denied = 0;
    int read = 0;
    int *hist;
    int NACL;
    safe_inet_addr("255.255.255.255", &no_addr);
    safe_inet_addr("0.0.0.0", &any_addr);
    fp = fopen("ips", "r");
    assert(fp != NULL);
    NACL = aclParseIpList(&I);
    fclose(fp);
    fprintf(stderr, "Loaded %d entries\n", NACL);
    hist = calloc(NACL, sizeof(int));
    while (NULL != fgets(buf, 1024, stdin)) {
	strtok(buf, w_space);
	read++;
	if (0 == safe_inet_addr(buf, &addr))
	    continue;
	cmp_count = 0;
	if (0 == aclMatchIp(&I, addr))
	    denied++;
	else
	    allowed++;
	++*(hist+cmp_count);
    }
    printf("%d read, %d allowed, %d denied\n",
	read, allowed, denied);
    dump_hist(hist, NACL);
    return 0;
}