/* NET/ROM level 3 low level processing */

#include <stdio.h>
#include "global.h"
#include "mbuf.h"
#include "iface.h"
#include "trace.h"
#include "timer.h"
#include "arp.h"
#include "slip.h"
#include "ax25.h"
#include "netrom.h"
#include "lapb.h"
#include "ip.h"
#include <ctype.h>

struct nrnbr_tab *nrnbr_tab[NRNUMCHAINS];
struct nrroute_tab *nrroute_tab[NRNUMCHAINS];
struct nrnf_tab *nrnf_tab[NRNUMCHAINS];
struct ax25_call *nr_excl[NHASH];

/* netrom level 3 params */
unsigned nr_autofloor = 1;
unsigned nr_maxfail = 1;
unsigned nr_maxqueue = 16;
unsigned nr_maxroutes = 3;
unsigned nr_nfmode = NRNF_NOFILTER;
unsigned nr_tcpip = NRT_NORM;
unsigned nr_ttl = 10;
unsigned obso_init = 6;
unsigned obso_minbc = 5;
char nr_aliasip[] = NR_TCPIP;

struct interface *nr_interface;
struct ax25_addr nr_nodebc;

static struct nrnf_tab *find_nrnf();
static struct ax25_addr *find_nbrif ();
static int alt_route();

/* Send datagrams across a NET/ROM network connection */
void
nr_send3(bp,dest)
struct mbuf *bp;
struct ax25_addr *dest;

{
	struct nr3hdr n3hdr;
	void nr__route();

	n3hdr.source.call[0] = '\0';	/* source call to be filled in */
	memcpy(&n3hdr.dest,dest,sizeof(struct ax25_addr));
	n3hdr.ttl = nr_ttl;

	nr__route(&n3hdr,bp,NULLAXADDR);/* pass off to level 3 routing code */
}

/* Figure out if a call is assigned to one of my NET/ROM
 * interfaces.
 */
int
ismycall(addr)
struct ax25_addr *addr;
{
	register struct interface *ifp;

	if (nr_interface != NULLIF && nr_interface->hwaddr != NULLCHAR)
	    return addreq((struct ax25_addr *)(nr_interface->hwaddr),addr);

	for (ifp = ifaces; ifp != NULLIF; ifp = ifp->next)
	    if (ifp->nriface != NULLNRIFACE &&
		addreq((struct ax25_addr *)(ifp->hwaddr),addr)) {
		return 1;
	    }

	return 0;
}

/* Determine the netrom source call to be used (global or interface) */
struct ax25_addr *
nr_scall (ifp)
struct interface *ifp;

{
	if (nr_interface->hwaddr != NULLCHAR)
	    return (struct ax25_addr *)nr_interface->hwaddr;
	else
	    return (struct ax25_addr *)ifp->hwaddr;
}

/* Route NET/ROM network layer packets.
 * This function is called for NET/ROM packets incoming on AX.25 interfaces.
 */
void
nr_route(axp,bp)
struct ax25_cb *axp;			/* receiving AX.25 connection */
struct mbuf *bp;			/* incoming NET/ROM packet */
{
	struct nr3hdr n3hdr;
	int i;
	char *cp,*putaxaddr();
	struct nrroute_tab *rp;
	char neighbor[3 * AXALEN];

	if (axp->interface->nriface == NULLNRIFACE ||	/* not NET/ROM iface? */
	    !ismycall(&axp->addr.source) ||		/* bad call? */
	    ntohnr3(&n3hdr,&bp) < 0 ||			/* header bad? */
	    valid_addr(&n3hdr.source) != 0) {		/* illegal source? */
		free_p(bp);
		return;
	}

	/* a real NET/ROM does not like to be polled using I(P) frames */
	/* set the pthresh to zero when a connection apparently is from */
	/* a NET/ROM neighbor, to prevent trouble. we will use RR(P). */

	axp->pthresh = 0;

	/* when filtermode "exclusive" is selected, we only want to route */
	/* netrom traffic from nodes in our filter table. check if the */
	/* callsign sending the packet (axp->addr.dest) is in the table. */

	if (nr_nfmode == NRNF_EXCLUSIVE &&
	    find_nrnf(&axp->addr.dest,axp->interface) == NULLNRNFTAB) {
		free_p(bp);		/* not in list, discard packet */
		return;
	}

	/* when we receive something from a node, be certain a route */
	/* exists to that node. if not, create a route from information */
	/* in the incoming packet.  this is done to make sure a retour */
	/* route exists when a response packet has to be sent. */

	if (((rp = find_nrroute(&n3hdr.source)) == NULLNRRTAB ||
	    rp->routes == NULLNRBIND || rp->routes->quality == 0) &&
	    !ismycall(&n3hdr.source) &&
	    axp->addr.ndigis < 3)		/* required by NET/ROM... */
	{
		cp = putaxaddr(neighbor,&axp->addr.dest);
		for (i = 0; i < axp->addr.ndigis; i++){
		    cp[-1] &= ~E;
		    cp = putaxaddr(cp,&axp->addr.digis[i]);
		}
		cp[-1] |= E;

		nr_rt_add(NULLCHAR,		/* don't know alias */
			  &n3hdr.source,	/* dest=source node from l3 hdr */
			  axp->interface,	/* receiving interface */
			  1,			/* a low quality (but >0) */
			  obso_init,
			  neighbor,		/* path to source */
			  0);			/* treat like broadcast info */
	}

	nr__route(&n3hdr,bp,&axp->addr.dest);
}

/* Same, but header already extracted */
/* Used by nr_route(), and also for outgoing NET/ROM packets. */
void
nr__route(hdr,bp,source)
struct nr3hdr *hdr;
struct mbuf *bp;
struct ax25_addr *source;
{
	struct ax25_cb *axp,*find_ax25(),*open_ax25();
	struct ax25 naxhdr;
	struct ax25_addr neighbor,*scall;
	struct mbuf *hbp,*pbp;
	register struct nrnbr_tab *np;
	register struct nrroute_tab *rp;
	int route_tries;
	extern int16 axwindow;
#ifdef OLD_NETROM
	unsigned char nr4head[NR4HLEN];
#endif
	void ax_incom(),nr3_state();

	/* check if the packet is addressed to one of our NET/ROM calls */
	/* if so, bump it up to either NET/ROM level 4, or to IP */
	if (ismycall(&hdr->dest)) {
	    /* trace input from "netrom" fake interface */
	    dump(nr_interface,IF_TRACE_IN,TRACE_NETROM,bp);

	    /* check if it is from me.	if so, it is a routing loop! */
	    if (hdr->source.call[0] == '\0' || ismycall(&hdr->source)){
		free_p(bp);
		return;
	    }

#ifdef OLD_NETROM
	    /* these statements check if the packet is a NET/ROM transport
	       layer packet, or an IP packet passed over the NET/ROM network
	       layer. checks applied are:
	       - first byte does not look like an IP Version/IHL byte
	       - byte 4 is a valid NET/ROM transport layer opcode
	       boy is this awful! who invented this way of sending IP
	       packets over NET/ROM???!!
	       fortunately, a new method is to use NET/ROM opcode 0 to
	       encapsulate an IP packet. the old one is still preserved
	       in the name of backward-compatability. (if OLD_NETROM defined)
	     */
	    if (pullup(&bp,nr4head,NR4HLEN) != NR4HLEN)
		return;			/* very small packet, cannot be valid */
	    if ((hbp = pushdown(bp,NR4HLEN)) == NULLBUF){ /* put the header back on */
		free_p(bp);
		return;
	    }
	    memcpy(hbp->data,nr4head,NR4HLEN);
	    if ((nr4head[0] & 0xf0) != (IPVERSION << 4) &&
		(nr4head[4] & NR4OMASK) <= NR4INFACK){
		nr4recv(hbp);		/* send to NET/ROM transport */
	    } else {
		ip_route(hbp,0);	/* it may be an IP packet */
	    }
#else
	    nr4recv(bp);		/* always send to NET/ROM transport */
#endif
	    return;
	}

	if (--(hdr->ttl) == 0) {  /* the packet's time to live is over! */
	    free_p(bp);
	    return;
	}

	if ((rp = find_nrroute(&hdr->dest)) == NULLNRRTAB) {
	    /* no route, drop the packet */
	    free_p(bp);
	    return;
	}

	route_tries = nr_maxroutes;

	while (route_tries)
	{
	    if (rp->routes == NULLNRBIND) {
		/* This shouldn't happen yet, but might if we add */ 
		/* dead route detection */
		free_p(bp);
		return;
	    }

	    np = rp->routes->via;
	    getaxaddr(&neighbor,np->call);

	    /* check if we are going to send the packet back to the neighbor */
	    /* that just sent it to us. if so, there apparently exists no */
	    /* usable route to the destination from there, and we better try */
	    /* an alternative route */

	    if (source != NULLAXADDR && addreq(source,&neighbor)){
		if (alt_route(rp) < 0)		/* one route only */
		    break;

		route_tries--;
	    } else {
		break;
	    }
	}

	scall = nr_scall(np->interface);	/* get netrom call */

	/* Now check to see if the source call is null.	 That is */
	/* a signal from nr_send that the packet originates here,*/
	/* so we need to insert the callsign of the appropriate	 */
	/* interface.  this will be the global NET/ROM callsign	 */
	/* if available, else the callsign for the interface	 */
	if (hdr->source.call[0] == '\0')
	    memcpy(&hdr->source,scall,AXALEN);

	/* Make sure there is a connection to the neighbor */
	if ((axp = find_ax25(&neighbor,scall)) == NULLAX25 ||
	    (axp->state != CONNECTED && axp->state != SETUP)) {
	    /* Open a new connection or reinitialize old one */
	    atohax25(&naxhdr,np->call,scall);
	    axp = open_ax25(&naxhdr,axwindow,ax_incom,NULLVFP,nr3_state,
						np->interface,(char *)0);
	    if (axp == NULLAX25) {
		free_p(bp);
		return;
	    }
	    axp->pthresh = 0;	/* a real NET/ROM does not like I(P) polls */
	} else {
	    if (len_q(axp->txq) >= nr_maxqueue) { /* check queue length */
		free_p(bp);			/* drop packet if too many */
		alt_route(rp);			/* try alt route next time */
		return;
	    }
	}

	/* allocate and fill PID mbuf */
	if ((pbp = alloc_mbuf(1)) == NULLBUF) {
		free_p(bp);
		return;
	}
	pbp->cnt = 1;
	*pbp->data = (PID_FIRST | PID_LAST | PID_NETROM);

	/* now format network header */
	if ((hbp = htonnr3(hdr)) == NULLBUF) {
		free_p(pbp);
		free_p(bp);
		return;
	}

	append(pbp,hbp);		/* append header to pid */
	/* the data must be copied because AX.25 may continue retransmitting */
	/* it after it has been freed because a local TCB has gone away */
	append(pbp,copy_p(bp,len_mbuf(bp))); /* append data to header */
	free_p(bp);			/* free the original */
	send_ax25(axp,pbp);		/* pass it off to ax25 code */
}

/* initialize fake arp entry for netrom */
void
nr_arp()
{
	int psax25(),setpath();
	struct ax25_call *axc;

	setcall(&nr_nodebc,"NODES-0");
	if ((axc = cr_axcall(ax25_call,&nr_nodebc)) != NULLAXCALL){
		axc->mode  = IP_ARP_CON;
		axc->flags = MULTI_IF | MULTICAST | NETROM_MULTI;
	}

	arp_init(ARP_NETROM,AXALEN,0,0,NULLCHAR,psax25,setpath);
}


/* Perform a nodes broadcast on interface axif */
void
nr_bcnodes(axif)
register struct interface *axif;
{
	struct mbuf *dbp;
	register struct nrroute_tab *rp;
	struct nrnbr_tab *np;
	struct nr_bind *bp;
	struct nr3dest nrdest;
	struct interface *ifp;
	struct ax25_addr *nbr;
	int i,didsend = 0,numdest = 0;
	register char *cp;
	char header[NR3NODEHL];

	/* check if a NET/ROM interface */
	if (axif->nriface == NULLNRIFACE)
		return;

	/* check for special case: when this interface listens only to */
	/* a single neighbor, don't broadcast the routes that are via */
	/* that neighbor (this only wastes bandwidth and results in 0-q */
	/* routes that lateron develop into routing loops) */
	if (nr_nfmode == NRNF_ACCEPT || nr_nfmode == NRNF_EXCLUSIVE)
		nbr = find_nbrif(axif);
	else
		nbr = NULLAXADDR;

	/* prepare the header once for all broadcast packets */
	header[0] = NR3NODESIG;
	memcpy(header+1,axif->nriface->alias,ALEN);

	/* allocate space for the first broadcast packet */
	if ((dbp = alloc_mbuf(NR3NODEHL + NRDESTPERPACK * NRRTDESTLEN)) == NULLBUF)
	    return;

	/* insert header and set startoff point for destinations */
	memcpy(dbp->data,header,NR3NODEHL);
	cp = dbp->data + NR3NODEHL;

	/* now scan through the routing table, finding the best routes */
	/* and their neighbors.	 create destination subpackets and append */
	/* them to the header */
	for (i = 0;i < NRNUMCHAINS;i++) {
	    for (rp = nrroute_tab[i];rp != NULLNRRTAB;rp = rp->next) {
		switch (nr_tcpip)	/* special TCP/IP netrom handling? */
		{
		case NRT_NORM:		/* normal mode (like NET/ROM) */
		    break;		/* transmit everything */

		case NRT_ILNK:		/* interlink mode */
		    if (!strcmp(rp->alias,nr_aliasip)) /* a TCP/IP netrom? */
			break;		/* always broadcast it */

		    if (rp->alias[0] == '#') /* a hidden (interlink) node? */
			continue;	/* then don't broadcast */
		    break;

		default:		/* only-TCP/IP mode */
		    if (strcmp(rp->alias,nr_aliasip)) /* not a TCP/IP netrom? */
			continue;	/* then don't broadcast */
		    break;
		}

		/* check if route exists, and isn't obsolescent */
		/* we don't check if a lower-quality non-obsolescent route */
		/* exists (like it was done before) because broadcasting */
		/* such a route generally creates a routing loop for a node */
		/* that is no longer present... */
		if ((bp = rp->routes) == NULLNRBIND || bp->obsocnt < obso_minbc)
		    continue;		/* no non-obsolescent route */

		/* routes below the automatic-update threshold are not */
		/* broadcast to reduce the length of the broadcast. if */
		/* everybody has the same autofloor these would not be */
		/* accepted anyway... however, 0-quality routes ARE    */
		/* transmitted to cause remote deletion.	       */
		if (bp->quality != 0 && bp->quality < nr_autofloor)
		    continue;		/* don't broadcast it */

		np = bp->via;

		/* insert best neighbor */
		getaxaddr(&nrdest.neighbor,np->call);

		/* forget about this node when the neighbor is the only */
		/* one listening on this interface (see above)		*/
		if (nbr != NULLAXADDR && bp->quality != 0 && addreq(&nrdest.neighbor,nbr))
		    continue;

		/* insert destination from route table */
		nrdest.dest = rp->call;

		/* insert alias from route table */
		strcpy(nrdest.alias,rp->alias);

		/* insert quality from binding */
		nrdest.quality = bp->quality;

		/* insert network format destination subpacket */
		cp = htonnrdest(cp,&nrdest);

		/* see if we have appended as many destinations */
		/* as we can fit into a single broadcast.  If we */
		/* have, go ahead and send them out. */
		if (++numdest >= NRDESTPERPACK) {	/* filled it up */
		    didsend = 1;	/* indicate that we did broadcast */
		    numdest = 0;	/* reset the destination counter */
		    dbp->cnt = NR3NODEHL + NRDESTPERPACK * NRRTDESTLEN;
		    (*axif->output)(axif,(char *)&nr_nodebc,nr_scall(axif),
					 (PID_FIRST | PID_LAST | PID_NETROM),
					 dbp);		/* send it */

		    /* allocate new broadcast packet */
		    if ((dbp = alloc_mbuf(NR3NODEHL + NRDESTPERPACK * NRRTDESTLEN)) == NULLBUF)
			return;

		    /* insert header and set startoff point for destinations */
		    memcpy(dbp->data,header,NR3NODEHL);
		    cp = dbp->data + NR3NODEHL;
		}
	    }
	}

	/* Now, here is something totally weird.  If our interfaces */
	/* have different callsigns than this one, advertise a very */
	/* high quality route to them.	Is this a good idea?  I don't */
	/* know.  However, it allows us to simulate a bunch of NET/ROMs */
	/* hooked together with a diode matrix coupler. */
	if (nr_interface->hwaddr == NULLCHAR)/* only if no global NET/ROM call */
	  for (ifp = ifaces; ifp != NULLIF; ifp = ifp->next) {
	    if (ifp == axif || ifp->nriface == NULLNRIFACE)
		continue;		/* don't bother with ours or no-NET/ROM */
	    if (!addreq((struct ax25_addr *)axif->hwaddr,ifp->hwaddr)) {
		/* both destination and neighbor address */
		memcpy(&nrdest.dest,ifp->hwaddr,AXALEN);
		memcpy(&nrdest.neighbor,ifp->hwaddr,AXALEN);

		/* alias of the interface */
		strcpy(nrdest.alias,ifp->nriface->alias);

		/* and the very highest quality */
		nrdest.quality = 255;

		/* insert network format destination subpacket */
		cp = htonnrdest(cp,&nrdest);

		if (++numdest >= NRDESTPERPACK) {	/* filled it up */
		    didsend = 1;	/* indicate that we did broadcast */
		    numdest = 0;	/* reset the destination counter */
		    dbp->cnt = NR3NODEHL + NRDESTPERPACK * NRRTDESTLEN;
		    (*axif->output)(axif,(char *)&nr_nodebc,nr_scall(axif),
					 (PID_FIRST | PID_LAST | PID_NETROM),
					 dbp);		/* send it */

		    /* allocate new broadcast packet */
		    if ((dbp = alloc_mbuf(NR3NODEHL + NRDESTPERPACK * NRRTDESTLEN)) == NULLBUF)
			return;

		    /* insert header and set startoff point for destinations */
		    memcpy(dbp->data,header,NR3NODEHL);
		    cp = dbp->data + NR3NODEHL;
		}
	    }
	  }

	/* If we have a partly filled packet left over, or we never */
	/* sent one at all, we broadcast: */
	if (!didsend || numdest > 0){
	    dbp->cnt = cp - dbp->data;
	    (*axif->output)(axif,(char *)&nr_nodebc,nr_scall(axif),
				 (PID_FIRST | PID_LAST | PID_NETROM),dbp);
	}
	else
	    free_mbuf(dbp);	/* don't forget to throw it away... */
}


/* This function checks an AX.25 address and interface against
 * the filter table and mode,and returns 1 if the address is to be
 * accepted,and 0 if it is to be filtered out.
 */
static int
accept_bc(addr,ifp)
struct ax25_addr *addr;
struct interface *ifp;
{
	switch (nr_nfmode)		/* filter mode */
	{
	case NRNF_NOFILTER:		/* no filtering in effect */
		break;

	case NRNF_REJECT:		/* reject when in list */
		if (find_nrnf(addr,ifp) != NULLNRNFTAB)
			return 0;	/* reject when found */
		break;

	case NRNF_ACCEPT:		/* accept when in list */
	case NRNF_EXCLUSIVE:		/* same, only traffic from these */
		if (find_nrnf(addr,ifp) == NULLNRNFTAB)
			return 0;	/* reject when not found */
		break;
	}

	return 1;
}

/* check alias in attempt to reject junk sent by the poor souls that
   keep thinking the existing asy interrupt handlers on the PC are
   any good... (especially when an ethernet card is also present) */
static int
nr_aliasok(p)
    register unsigned char *p;		/* ptr to alias field (ALEN chars) */
{
    register int len = ALEN;

    while (len--)			/* scan alias for control chars */
	if (*p >= 0x7f || *p++ < ' ')	/* i.e. bit 7 set, DEL or < ' ' */
	    return 0;

    return 1;				/* all passed, it's okay */
}

/* receive and process node broadcasts. */
void
nr_nodercv(interface,source,bp)
struct interface *interface;
struct ax25_addr *source;
struct mbuf *bp;
{
	int nb_qual;
	char bcalias[ALEN + 1];
	struct nr3dest ds;
	char sbuf[AXALEN*3];
	struct ax25_addr addr;

	/* First, see if this is even a NET/ROM interface: */
	if (interface->nriface == NULLNRIFACE){
		free_p(bp);
		return;
	}

	if (nr_autofloor == 0 ||		/* auto-updates disabled? */
	    valid_addr(source) != 0 ||		/* not a valid source call? */
	    !accept_bc(source,interface)) {	/* check against filter */
		free_p(bp);
		return;
	}

	/* check source node call. it must NOT appear in the exclude list */
	ASSIGN(addr,*source);	    /* get the node call */
	addr.ssid = 0;		    /* discard the SSID */
	if(find_axcall(nr_excl,&addr) != NULLAXCALL) {
		free_p(bp);
		return;
	}

	/* See if it has a routing broadcast signature: */
	if (uchar(pullchar(&bp)) != NR3NODESIG) {
		free_p(bp);
		return;
	}

	/* now try to get the alias */
	if (pullup(&bp,bcalias,ALEN) < ALEN ||
	    !nr_aliasok(bcalias)) {	/* check not really needed here */
		free_p(bp);
		return;
	}

	bcalias[ALEN] = '\0';		/* null terminate */

	/* copy source address and convert to arp format */
	memcpy(sbuf,source->call,ALEN);
	sbuf[ALEN] = (source->ssid | E);/* terminate */

	/* enter the neighbor into our routing table */
	if ((nb_qual = nr_rt_add(bcalias,source,interface,interface->nriface->quality,
				 obso_init,sbuf,0)) < 0) {
		free_p(bp);
		return;
	}

	/* we've digested the header; now digest the actual */ 
	/* routing information */
	while (ntohnrdest(&ds,&bp) == 0) {
	    /* ignore routes below the minimum quality threshhold */
	    /* 0-quality routes are an exception: delete them later */
	    if (ds.quality < nr_autofloor && ds.quality != 0)
		continue;

	    /* when required, ignore routes with no TCP/IP netrom */
	    if (nr_tcpip == NRT_IGN && strcmp(ds.alias,nr_aliasip))
		continue;

	    /* when junk in alias field, ignore it */
	    if (!nr_aliasok(ds.alias))
		continue;

	    /* when unacceptable callsign, ignore it */
	    if (valid_addr(&ds.dest) != 0)
		continue;

	    /* ignore routes to me! */
	    if (ismycall(&ds.dest))
		continue;

	    /* check node call. it must NOT appear in the exclude list */
	    ASSIGN(addr,ds.dest);	/* get the node call */
	    addr.ssid = 0;		/* discard the SSID */
	    if(find_axcall(nr_excl,&addr) != NULLAXCALL)
		continue;

	    /* check if a 0-quality broadcast was received */
	    if (ds.quality == 0) {
		nr_rt_drop(&ds.dest,source,interface); /* drop the route */
		continue;
	    }

	    /* check for loopback paths */
	    if (ismycall(&ds.neighbor))
		ds.quality = 0;		/* set loopback paths to 0 quality */
	    else
		ds.quality = ((ds.quality * nb_qual + 128)
						  / 256) & 0xff;

	    if (nr_rt_add(ds.alias,&ds.dest,interface,ds.quality,
			  obso_init,sbuf,0) < 0)
		break;
	}

	free_p(bp);   /* This will free the mbuf if anything fails above */
}

/* this function is called when state changes on a netrom-initiated */
/* connection (to a neighbor node). when link failed, change route */
void
nr3_state(axp,old,new,msg)
struct ax25_cb *axp;
int old,new,msg;
{
    struct nrnbr_tab *np;
    struct nrroute_tab *rp;
    int16 hashval;

    if (msg == LAPBFAIL){		/* the link failed */
	if ((np = find_nrnbr(&axp->addr.dest,axp->interface)) == NULLNTAB)
	    return;

	/* find all routes using this neighbor and change them */
	for (hashval = 0; hashval < NRNUMCHAINS; hashval++)
	    for (rp = nrroute_tab[hashval]; rp != NULLNRRTAB; rp = rp->next)
		if (rp->routes != NULLNRBIND && rp->routes->via == np)
		    alt_route(rp);

	if (nr_maxfail && ++(np->failcnt) > nr_maxfail) { /* too many failures? */
	    /* drop all routes that use this neighbor, until we hear */
	    /* a broadcast from him again... */

	    nr_rt_drop(NULLAXADDR,&axp->addr.dest,axp->interface);
	}
    }
}

/* take next alternative route to a node */
/* return -1 when only one route, 0 if ok, 1 if still same route */
static int
alt_route (rp)
    register struct nrroute_tab *rp;

{
    register struct nr_bind *bp,*ibp;
    struct nr_bind *org;
    unsigned maxqual;

    /* first check that more than one binding is available */
    if (rp->num_routes < 2)
	return -1;			/* if not, cannot set alt route */

    org = rp->routes;			/* remember original route */

    do {
	/* ok, move first one to the end of the list */
	bp = rp->routes;
	maxqual = bp->quality;
	ibp = rp->routes = bp->next;
	ibp->prev = bp->next = NULLNRBIND;

	do {
	    if (ibp->quality > maxqual)
		maxqual = ibp->quality;
	} while (ibp->next != NULLNRBIND && (ibp = ibp->next) != NULLNRBIND);

	ibp->next = bp;
	bp->prev = ibp;

	/* when we selected a 0-quality route from a list containing
	   better routes, try another alternative (or the old one) */
    } while (rp->routes->quality == 0 && maxqual != 0);

    return (rp->routes == org);		/* check if it has changed */
}


/* The following are utilities for manipulating the routing table */

/* hash function for callsigns.	 Look familiar? */
int16
nrhash(s)
register struct ax25_addr *s;
{
	register char x;

	x = s->call[0] ^ s->call[1] ^ s->call[2] ^
	    s->call[3] ^ s->call[4] ^ s->call[5];
	x ^= s->ssid & SSID;
	return (uchar(x) & 0xfe) % NRNUMCHAINS;
}

/* Find a neighbor table entry.	 Neighbors are determined by
 * their callsign and the interface.  This takes care
 * of the case where the same switch or hosts uses the same
 * callsign on two different channels.	This isn't done by 
 * NET/ROM, but it might be done by stations running *our*
 * software.
 */
struct nrnbr_tab *
find_nrnbr(addr,interface)
register struct ax25_addr *addr;
struct interface *interface;
{
	register struct nrnbr_tab *np;
	struct ax25_addr ncall;

	/* search appropriate hash chain */
	for (np = nrnbr_tab[nrhash(addr)]; np != NULLNTAB; np = np->next) {
	    getaxaddr(&ncall,np->call);
	    if (addreq(&ncall,addr) && np->interface == interface)
		return np;
	}
	return NULLNTAB;
}


/* Find a route table entry */
struct nrroute_tab *
find_nrroute(addr)
register struct ax25_addr *addr;
{
	register struct nrroute_tab *rp;

	/* search appropriate hash chain */
	for (rp = nrroute_tab[nrhash(addr)];rp != NULLNRRTAB;rp = rp->next) {
		if (addreq(&rp->call,addr))
			return rp;
	}
	return NULLNRRTAB;
}

#ifdef NETROM4
/* Find a route table entry by ALIAS */
struct nrroute_tab *
find_nralias(alias)
char *alias;
{
	register struct nrroute_tab *rp;
	int n;

	/* search all hash chains */
	for (n = 0; n < NRNUMCHAINS; n++)
	    for (rp = nrroute_tab[n];rp != NULLNRRTAB;rp = rp->next) {
		if (!strcmp(rp->alias,alias))
			return rp;
	}
	return NULLNRRTAB;
}
#endif

/* Find a binding in a list by its neighbor structure's address */
struct nr_bind *
find_binding(list,neighbor)
struct nr_bind *list;
register struct nrnbr_tab *neighbor;
{
	register struct nr_bind *bp;

	for(bp = list;bp != NULLNRBIND;bp = bp->next)
	    if (bp->via == neighbor)
		return bp;

	return NULLNRBIND;
}

/* Find the worst quality non-permanent binding in a list */
static
struct nr_bind *
find_worst(list)
struct nr_bind *list;
{
	register struct nr_bind *bp;
	struct nr_bind *worst = NULLNRBIND;
	unsigned minqual = 256;	     /* infinity */

	for (bp = list;bp != NULLNRBIND;bp = bp->next)
	    if (!(bp->flags & NRB_PERMANENT) && bp->quality < minqual) {
		 worst = bp;
		 minqual = bp->quality;
	    }

	return worst;
}

/********* netrom route support *********/

/* Add a route to the NET/ROM routing table. Return the quality (or -1). */
int
nr_rt_add(alias,dest,interface,quality,obsocnt,neighbor,permanent)
char *alias;			/* NET/ROM node alias, blank-padded and */
				/* null-terminated */
struct ax25_addr *dest;		/* destination node callsign */
struct interface *interface;	/* NET/ROM interface */
unsigned quality;		/* route quality */
unsigned obsocnt;		/* obsoletion count */
char *neighbor;			/* neighbor node + 2 digis (max) in arp format */
unsigned permanent;		/* 1 if route is permanent (hand-entered) */
{
	register struct nrroute_tab *rp;
	register struct nr_bind *bp;
	register struct nrnbr_tab *np;
	struct nr_bind *ibp;
	int16 rhash,nhash;
	struct ax25_addr ncall;

	/* See if a routing table entry exists for this destination */
	if ((rp = find_nrroute(dest)) == NULLNRRTAB) {
	    if ((rp = (struct nrroute_tab *)calloc(1,sizeof(struct nrroute_tab)))
		      == NULLNRRTAB)
		return -1;
	    else {				/* create a new route table entry */
		ASSIGN(rp->call,*dest);
		rhash = nrhash(dest);
		if ((rp->next = nrroute_tab[rhash]) != NULLNRRTAB)
		    rp->next->prev = rp;
		nrroute_tab[rhash] = rp;	/* link at head of hash chain */
	    }
	}

	/* Set ALIAS when specified, default to <none> */
	if (alias != NULLCHAR)
	    strncpy(rp->alias,alias,6);
	else
	    if (rp->alias[0] == '\0')		/* still empty? */
		strcpy(rp->alias,"      ");	/* default ALIAS = <none> */

	/* See if an entry exists for this neighbor */
	getaxaddr(&ncall,neighbor);

	if ((np = find_nrnbr(&ncall,interface)) == NULLNTAB) {
	    if ((np = (struct nrnbr_tab *)calloc(1,sizeof(struct nrnbr_tab)))
		      == NULLNTAB) {
		if (rp->num_routes == 0) {	/* we just added to table */
		    if (rp->next != NULLNRRTAB)
			rp->next->prev = NULLNRRTAB;
		    nrroute_tab[rhash] = rp->next;
		    free(rp);			/* so get rid of it */
		}
		return -1;
	    } else {				/* create a new neighbor entry */
		memcpy(np->call,neighbor,3 * AXALEN);
		np->interface = interface;
		nhash = nrhash(&ncall);
		np->next = nrnbr_tab[nhash];
		if (np->next != NULLNTAB)
		    np->next->prev = np;
		nrnbr_tab[nhash] = np;
	    }
	} else if (permanent) {			/* force this path to the neighbor */
	    memcpy(np->call,neighbor,3 * AXALEN);
	}

	/* See if there is a binding between the dest and neighbor */
	if ((bp = find_binding(rp->routes,np)) == NULLNRBIND) {
	    if ((bp = (struct nr_bind *)calloc(1,sizeof(struct nr_bind)))
			  == NULLNRBIND) {
		if (rp->num_routes == 0) {	/* we just added to table */
		    if (rp->next != NULLNRRTAB)
			rp->next->prev = NULLNRRTAB;
		    nrroute_tab[rhash] = rp->next;
		    free(rp);			/* so get rid of it */
		}

		if (np->refcnt == 0) {		/* we just added it */
		    if (np->next != NULLNTAB)
			np->next->prev = NULLNTAB;
		    nrnbr_tab[nhash] = np->next;
		    free(np);
		}
		return -1;
	    } else {			/* create a new binding and link it in */
		bp->via = np;		/* goes via this neighbor */

					/* scan binding chain for lower quality */
		for (ibp = rp->routes; ibp != NULLNRBIND; ibp = ibp->next)
		    if (ibp->quality < quality)
			break;
					/* link into chain at proper position */
		if (ibp != NULLNRBIND){ /* just before one with a lower qual */
		    if ((bp->prev = ibp->prev) != NULLNRBIND)
			ibp->prev->next = bp;
		    else
			rp->routes = bp;
		    bp->next = ibp;
		    ibp->prev = bp;
		} else {		/* at end of existing list */
		    if (rp->routes != NULLNRBIND){
			for (ibp = rp->routes; ibp->next != NULLNRBIND; ibp = ibp->next)
			    ;
			ibp->next = bp;
			bp->prev = ibp;
		    } else {
			rp->routes = bp;/* first entry */
		    }
		}
		rp->num_routes++;	/* bump route count */
		np->refcnt++;		/* bump neighbor ref count */
		bp->quality = quality;
		bp->obsocnt = obsocnt;
		if (permanent)
		    bp->flags |= NRB_PERMANENT;
	    }
	} else {			/* already exists */
	    /* Don't allow broadcasts to modify permanent entries */
	    if (permanent || !(bp->flags & NRB_PERMANENT)) {
		bp->quality = quality;
		bp->obsocnt = obsocnt;
		if (permanent)
		    bp->flags |= NRB_PERMANENT; /* make it permanent */

		/* Check if the received route had a better quality than */
		/* the currently effective route, and change route if so */
		/* The route can never be the first (quality would be equal) */
		if (quality > rp->routes->quality) {
		    bp->prev->next = bp->next;
		    if (bp->next != NULLNRBIND)
			bp->next->prev = bp->prev;
		    rp->routes->prev = bp;
		    bp->prev = NULLNRBIND;
		    bp->next = rp->routes;
		    rp->routes = bp;
		}
	    } else {
		quality = bp->quality;	/* readout permanent quality */
	    }
	}

	/* Now, check to see if we have too many bindings, and drop */
	/* the worst if we do */
	if (rp->num_routes > nr_maxroutes) {
	    /* since find_worst never returns permanent entries, the */
	    /* limitation on number of routes is circumvented for    */
	    /* permanent routes */
	    if ((bp = find_worst(rp->routes)) != NULLNRBIND) {
		nr_rnb_drop(rp,bp->via,bp);
	    }
	}

	return quality;
}

/* Drop a route to dest via neighbor */
int
nr_rt_drop(dest,neighbor,interface)
struct ax25_addr *dest,*neighbor;
struct interface *interface;
{
	register struct nrroute_tab *rp;
	struct nrroute_tab *rpnext;
	struct nrnbr_tab *np;
	struct nr_bind *bp;
	int16 hashval;
	int rv = 0;

	if ((np = find_nrnbr(neighbor,interface)) == NULLNTAB)
		return -1;

	if (dest != NULLAXADDR) {
	    if ((rp = find_nrroute(dest)) == NULLNRRTAB)
		return -1;

	    if ((bp = find_binding(rp->routes,np)) == NULLNRBIND)
		return -1;

	    return nr_rnb_drop(rp,np,bp);
	}

	/* NULL dest, drop all automatic routes using this neighbor */
	for (hashval = 0; hashval < NRNUMCHAINS; hashval++) {
	    for (rp = nrroute_tab[hashval]; rp != NULLNRRTAB; rp = rpnext) {
		rpnext = rp->next;

		if (rp->routes != NULLNRBIND &&
		    (bp = find_binding(rp->routes,np)) != NULLNRBIND &&
		    !(bp->flags & NRB_PERMANENT))
		    rv |= nr_rnb_drop(rp,np,bp);
	    }
	}

	return rv;
}

/* drop a route specified by route and neighbor */
int
nr_rnb_drop (rp,np,bp)
register struct nrroute_tab *rp;
register struct nrnbr_tab *np;
register struct nr_bind *bp;

{
	int16 hashval;

	/* drop the binding first */
	if (bp->next != NULLNRBIND)
		bp->next->prev = bp->prev;
	if (bp->prev != NULLNRBIND)
		bp->prev->next = bp->next;
	else
		rp->routes = bp->next;

	free(bp);
	rp->num_routes--;	      /* decrement the number of bindings */
	np->refcnt--;		      /* and the number of neighbor references */

	/* now see if we should drop the route table entry */
	if (rp->num_routes == 0) {
		if (rp->next != NULLNRRTAB)
			rp->next->prev = rp->prev;
		if (rp->prev != NULLNRRTAB)
			rp->prev->next = rp->next;
		else
			nrroute_tab[nrhash(&rp->call)] = rp->next;

		free(rp);
	}

	/* and check to see if this neighbor can be dropped */
	if (np->refcnt == 0) {
		if (np->next != NULLNTAB)
			np->next->prev = np->prev;
		if (np->prev != NULLNTAB)
			np->prev->next = np->next;
		else
			for (hashval = 0; hashval < NRNUMCHAINS; hashval++)
			    if (nrnbr_tab[hashval] == np) {
				nrnbr_tab[hashval] = np->next;
				break;
			    }

		free(np);
	}

	return 0;
}

/********* netrom nodefilter support *********/

/* Find an entry in the filter table */
static
struct nrnf_tab *
find_nrnf(addr,interface)
register struct ax25_addr *addr;
struct interface *interface;
{
	int16 hashval;
	register struct nrnf_tab *fp;

	/* Find appropriate hash chain */
	hashval = nrhash(addr);

	/* search hash chain */
	for (fp = nrnf_tab[hashval];fp != NULLNRNFTAB;fp = fp->next) {
		if (addreq(&fp->neighbor,addr) && fp->interface == interface) {
			return fp;
		}
	}

	return NULLNRNFTAB;
}

/* Check the filter table for occurrence of a certain interface.
 * When there is one single entry with that interface, return the address
 * of the neighbor.  When there are no, or there is more than one entry
 * with that interface, return NULL.
 * Used to base node broadcasts on single/multi neighbor situation.
 */
static
struct ax25_addr *
find_nbrif (interface)
struct interface *interface;
{
	struct ax25_addr *rv = NULLAXADDR;
	int16 hashval;
	register struct nrnf_tab *fp;

	for (hashval = 0; hashval < NRNUMCHAINS; hashval++) {
		for (fp = nrnf_tab[hashval];fp != NULLNRNFTAB;fp = fp->next) {
			if (fp->interface == interface) {
				if (rv != NULLAXADDR)		/* 2nd one! */
					return NULLAXADDR;

				rv = &fp->neighbor;
			}
		}
	}

	return rv;
}

/* Add an entry to the filter table.  Return 0 on success,
 * -1 on failure
 */
int
nr_nfadd(addr,interface)
struct ax25_addr *addr;
struct interface *interface;
{
	struct nrnf_tab *fp;
	int16 hashval;

	if (find_nrnf(addr,interface) != NULLNRNFTAB)
		return 0;     /* already there;it's a no-op */ 

	if ((fp = (struct nrnf_tab *)calloc(1,sizeof(struct nrnf_tab)))
		== NULLNRNFTAB)
		return -1;    /* no storage */

	hashval = nrhash(addr);
	fp->neighbor = *addr;
	fp->interface = interface;
	fp->next = nrnf_tab[hashval];
	if (fp->next != NULLNRNFTAB)
		fp->next->prev = fp;
	nrnf_tab[hashval] = fp;

	return 0;
}

/* Drop a neighbor from the filter table.  Returns 0 on success,
 * -1 on failure.
 */
int
nr_nfdrop(addr,interface)
struct ax25_addr *addr;
struct interface *interface;
{
	struct nrnf_tab *fp;

	if ((fp = find_nrnf(addr,interface)) == NULLNRNFTAB)
		return -1;    /* not in the table */

	if (fp->next != NULLNRNFTAB)
		fp->next->prev = fp->prev;
	if (fp->prev != NULLNRNFTAB)
		fp->prev->next = fp->next;
	else
		nrnf_tab[nrhash(addr)] = fp->next;

	free(fp);

	return 0;
}