char *ident="#(@)aclgen 2.02, kissg@sztaki.hu 970621";
/*
 * aclgen 2.02       ftp://ftp.sztaki.hu/pub/provate/kissg/aclgen/
 *
 * Copyleft kissg@sztaki.hu 970621
 *
 * This program makes suboptimized access lists (for Cisco routers)
 * from various input files.
 *
 * This software has NO WARRANTY; use at your own risk.
 *
 * tabstop=4
 */

#include	<stdio.h>
#include	<string.h>
#include	<ctype.h>
#include	<stdlib.h>

/*#define P(x) ()*/
#define P(x) x

/* Tunable parameters */
#define BLKSIZE 510		/* size of allocated 'node' chunks */
#define BUFLEN 256		/* input line */

/* Constants */
#define D_INPUT	0x01
#define D_RAW	0x02
#define D_OPT	0x04
#define D_OPT1	0x10
#define D_OPT2	0x20
#define D_OPT3	0x40
#define D_OPT4	0x80

/* Macros */
#define ALLONE ((unsigned long)0xffffffff)
#define LEFTMASK(n)  ( (n) ? (ADDRESS)(ALLONE<<(32-(n))) : (ADDRESS)0 )
#define RIGHTMASK(n) ( (n) ? (ADDRESS)(ALLONE>>(32-(n))) : (ADDRESS)0 )
#define HIGHBIT(a)   ( ((a) & 0x80000000L) !=0 )
#define INVERT(v)    (YES==(v)?NO:NO==(v)?YES:(v))
#define VALUE(v)     (YES==(v)?"+":NO==(v)?"-":"?")

/* Types */
typedef enum types {UNSPECIFIED=0,NO=1,YES=2} NODETYPE;
typedef unsigned long ADDRESS;
typedef struct node {
	struct node *b[2];
	ADDRESS addr;
	NODETYPE value;
	int level;
} NODE;

/* Global variables */
static NODE root={{NULL,NULL},0,NO,0},
	*freelist=NULL;
static int trace=0;
static int opt_i,opt_p,opt_s;
static char *format="%m %a %w";
static char *str_permit="permit";
static char *str_deny  ="deny  ";
static char *typ[]={"","NO","YES"};
static char *usage="Usage: aclgen [options] [infile]\n"
	"Options:\n"
	"-h    print this message and exit\n"
	"-i    invert input\n"
	"-p    force \"positive\" mode. (no denied subtrees)\n"
	"-s    silent. (suppress warnings)\n"
	"-m permit_string,deny_string\n"
	"      override default modifiers (+,-)\n"
	"-f    format string. It should conatin conversion specifications:\n"
	"     %a address\n"
	"     %w wildcard bits\n"
	"     %k mask\n"
	"     %p prefix\n"
	"     %m modifier\n"
	"     %% %\n"
	"-t N  trace flags\n"
	"      1 show input parsing\n"
	"      2 print raw tree\n"
	"      4 print optimized tree\n"
	" 16-128 debug optimization step 1-4\n";

/* Function prototypes */
static FILE *open_input P((char *));
static void  read_input P((FILE *));
static void  optimize_tree P((NODE *));
static void  positive_tree P((NODE *));
static void  tree_stat P((NODE *, int *));
static void  fill_tree P((NODE *, NODETYPE));
static void  print_tree P((NODE *, int, /*char*/ int , NODE *));
static void  print_acl P((NODE *, char *));
static char *binaddr2dotted P((ADDRESS));
static int   prefix_by_class P((ADDRESS));
static NODE *allocnode P((void));
static void  freetree P((NODE *));
static NODE *setnode P((int,ADDRESS,NODETYPE));

void main(argc,argv)
int argc;
char *argv[];
{
	int cnt[3];
	int c;
	FILE *infile;
	extern char *optarg;
	extern int optind;
	char *p;

	/* Process options */

	cnt[0]=cnt[1]=cnt[2]=0;
	while ((c=getopt(argc,argv,"im:d:pf:hs"))!=EOF) {
		switch(c) {
		 case 'i':	opt_i++;
			break;
		 case 's':	opt_s++;
			break;
		 case 'm':	p=strchr(optarg,',');
			if (NULL==p) {
				printf("%s\n%s",ident,usage);
				exit(1);
			}
			*p++='\0';
			str_permit=optarg;
			str_deny=p;
			break;
		 case 'p':	opt_p++;
			break;
		 case 'f':	format=optarg;
			break;
		 case 't':
			trace|=atoi(optarg);
			break;
		 case 'h':
		 default:
			printf("%s\n%s",ident,usage);
			exit(1);
		}
	}
	if (!strstr(format,"%m") && !opt_p) {
		if (!opt_s) fprintf(stderr,"WARNING: No %%m (modifier)"
			" in format string. Option -p assumed\n");
		opt_p++;
	}

	/* Read input, build raw address tree */

	if (NULL==(infile=open_input(argv[optind]))) {
		fprintf(stderr,"Cannot open input file %s\n",argv[optind]);
		exit(1);
	}
	read_input(infile);

	if (trace & D_RAW) {
		printf("raw tree:\n-----\n");
		print_tree(&root,0,' ',&root);
		tree_stat(&root,cnt);
		printf("n=%d y=%d u=%d\n",cnt[NO],cnt[YES],cnt[UNSPECIFIED]);
		cnt[NO]=cnt[YES]=cnt[UNSPECIFIED]=0;
	}

	/* Optimize tree */

	fill_tree(&root,NO);
/*printf("filled tree:\n");
print_tree(&root,0,' ',&root);*/
	optimize_tree(&root);

	if (trace & D_OPT) {
		printf("-----\noptimized tree:\n");
		print_tree(&root,0,' ',&root);
		tree_stat(&root,cnt);
		printf("n=%d y=%d u=%d\n",cnt[NO],cnt[YES],cnt[UNSPECIFIED]);
		cnt[NO]=cnt[YES]=cnt[UNSPECIFIED]=0;
	}

	/* Print output */

	if (opt_p) positive_tree(&root);
	print_acl(&root,format);
}

/*
 * Read lines of input file and build the raw tree.
 * Input syntax:
 *  [modifier] address
 *  [modifier] address - address
 *  [modifier] address/prefix
 *  [modifier] address mask
 *
 *  Chars from `#' to end of line are ignored.
 *  Empty lines are ignored.
 *  If first char of modifier is `+', `y' or `p' or modifier is missing
 *   `YES' assumed. Other modifiers mean `NO'.
 *  Mask should be contiguous. No matter that wildcards are 1s or 0s.
 */
void read_input(infile)
FILE *infile;
{
	char buffer[BUFLEN],*p;
	unsigned long a[4],b[4];
	int prefix;
	NODETYPE value;
	ADDRESS l1,l2,m;

	while (fgets(buffer,BUFLEN-1,infile)) {
		if ((p=strchr(buffer,'#'))!=NULL) *p='\0';	/* comment discarded */
		p=buffer;
		if ('\0'==*p || '\n'==*p) continue;			/* empty line */
		if ('*'==*p) {
			print_tree(&root,0,' ',&root);
			continue;
		}
		while (isspace(*p)) p++;					/* leading whitespace */
		if (!isdigit(*p)) {
			value = ('y'==*p || 'Y'==*p ||	/* yes */
					 'p'==*p || 'P'==*p ||	/* permit */
					 '+'==*p) ? YES : NO;	/* + */
			while (!isdigit(*p)) p++;
		}
		else value=YES;						/* default: yes */
		if (opt_i) value=INVERT(value);
		if (trace & D_INPUT) {
			printf("%s  ",VALUE(value));
		}

		/*    'address/prefix'  */
		if (sscanf(p,"%lu.%lu.%lu.%lu/%d",a+3,a+2,a+1,a,&prefix)==5) {
			l1=((a[3]<<8|a[2])<<8|a[1])<<8|a[0];
			if (prefix>32) {
				if (!opt_s)
					fprintf(stderr,"WARNING: prefix /%d greater than 32\n",
						prefix);
				prefix=32;
			}
			if (trace & D_INPUT) {
				printf("address/prefix %s/%d\n",binaddr2dotted(l1),prefix);
			}
			if (NULL==setnode(prefix,l1,value)) {
				fprintf(stderr,"No more memory\n");
				exit(1);
			}
		}
		/*    'address - address' range */
		else if (sscanf(p,"%lu.%lu.%lu.%lu - %lu.%lu.%lu.%lu",
			a+3,a+2,a+1,a,b+3,b+2,b+1,b)==8) {
			ADDRESS increment;

			l1=((a[3]<<8|a[2])<<8|a[1])<<8|a[0];
			l2=((b[3]<<8|b[2])<<8|b[1])<<8|b[0];
			prefix=prefix_by_class(l2);
			if ((m=l1^l2) == l2-l1) 	/* accelerate */
				while (m&RIGHTMASK(1)) {
					m>>=1;
					--prefix;
				}
			increment= ~LEFTMASK(prefix)+1;
			if (trace & D_INPUT) {
				printf("range %s",binaddr2dotted(l1));
				printf(" - %s by 0x%.8lx\n",binaddr2dotted(l2),increment);
			}
			for ( ; l1<=l2; l1+=increment)
				if (NULL==setnode(prefix,l1,value)) {
					fprintf(stderr,"No more memory\n");
					exit(1);
				}
		}
		/*    'address mask'  */
		else if (sscanf(p,"%lu.%lu.%lu.%lu %lu.%lu.%lu.%lu",
			a+3,a+2,a+1,a,b+3,b+2,b+1,b)==8) {
			l1=((a[3]<<8|a[2])<<8|a[1])<<8|a[0];
			l2=((b[3]<<8|b[2])<<8|b[1])<<8|b[0];
			if (0==HIGHBIT(l2)) l2=~l2;		/* inverted mask */
			for (prefix=0; HIGHBIT(l2); l2<<=1, prefix++);
			if (l2 && !opt_s) fprintf(stderr,
				"WARNING: invalid mask: %lu.%lu.%lu.%lu\n",
				b[3],b[2],b[1],b[0]);
			/*
			 * We cannot distinguish 0.0.0.0 and 255.255.255.255.
                         * The longer prefix is assumed.
                         */
			if (32==prefix && !l1) {
				prefix=0;
				if (!opt_s) fprintf(stderr,
					"WARNING: mask %lu.%lu.%lu.%lu treated"
					" as 0 significant bits\n",
					b[3],b[2],b[1],b[0]);
			}
			if (trace & D_INPUT) {
				printf("address %s",binaddr2dotted(l1));
				printf(" mask %s\n",binaddr2dotted(LEFTMASK(prefix)));
			}
			if (NULL==setnode(prefix,l1,value)) {
				fprintf(stderr,"No more memory\n");
				exit(1);
			}
		}
		/*   'address'  */
		else if (sscanf(p,"%lu.%lu.%lu.%lu",a+3,a+2,a+1,a)==4) {
			l1=((a[3]<<8|a[2])<<8|a[1])<<8|a[0];
			if (trace & D_INPUT) {
				printf("address %s auto prefix %d\n",
					binaddr2dotted(l1),prefix_by_class(l1));
			}
			if (NULL==setnode(prefix_by_class(l1),l1,value)) {
				fprintf(stderr,"No more memory\n");
				exit(1);
			}
		}
	}
}

/*
 * UNSPECIFIED nodes get their parent's value.
 */
void fill_tree(p, parenttype)
NODE *p;
NODETYPE parenttype;
{
	if (NULL==p) return;
	if (UNSPECIFIED==p->value) p->value=parenttype;
	fill_tree(p->b[0],p->value);
	fill_tree(p->b[1],p->value);
	return;
}

/*
 * Eliminate 'NO' values
 */
void positive_tree(p)
NODE *p;
{
	int i;

	if (NULL==p) return;
	if (NULL==p->b[0] && NULL==p->b[1]) return;
	for (i=0; i<=1; i++) {
		register NODE *b;

		if (NULL==(b=p->b[i])) {
			if (NULL==(b=p->b[i]=allocnode())) {
				fprintf(stderr,"No more memory\n");
				exit(1);
			}
			b->value=p->value;
			b->b[0]=b->b[1]=NULL;
			b->level=p->level+1;
			b->addr=p->addr|((ADDRESS)i<<32-b->level);
		}
		else if (UNSPECIFIED==b->value) b->value=p->value;
	}
	p->value=UNSPECIFIED;
	positive_tree(p->b[0]);
	positive_tree(p->b[1]);
}

/*
 * Minimize the number of specified nodes
 */
void optimize_tree(p)
NODE *p;
{
	register NODE *b0,*b1;	/* child pointers */
	int i;
	NODETYPE t;

	if (NULL==p) return;
	b0=p->b[0];
	b1=p->b[1];
	if (NULL==b0 && NULL==b1) return;	/* no child */

	optimize_tree(b0);
	optimize_tree(b1);

/*
 * 1.
 * special case
 * P:{[B,C],YES}				P:{[B,C],NO}
 * B:{[NULL,D],YES}				B:{[E,NULL],NO}
 * C:{[NULL,NULL],NO}			E:{[NULL,NULL],YES}
 * D:{[NULL,NULL],NO}
 */
	for (i=0; i<=1; i++) {
		register NODE *bs=p->b[i];
		register NODE *bd=p->b[1-i];
		int j;
		NODETYPE t;

		if (NULL!=bs && NULL!=bd && /* if I've 2 children, */
		  p->value==bs->value && /* bs has the same value as me, */
		  bs->value==INVERT(bd->value) && /* bd has different value */
		  NULL==bd->b[0] && NULL==bd->b[1]) { /* and has no child */
			for (j=0; j<=1; j++) {	/* then if bs's */
				register NODE *bj=bs->b[j];

				if (NULL!=bj && NULL==bs->b[1-j] && /* only child */
				  NULL==bj->b[0] && NULL==bj->b[1]) { /* has no child */
				  /* (then he must be inverse of bs) */
					/* Invert the little subtree of bs */
					bs->b[1-j]=bj;
					bs->b[j]=NULL;
					t=bj->value;
					bj->value=bs->value;
					bs->value=t;
					bj->addr ^= 1L<<32-bj->level;
					if (trace & D_OPT1) {
						printf("-opt1/%d-\n",i);
						print_tree(&root,0,'=',p);
					}
					break;
				}
			}
		}
	}

/*
 * 2.
 * If my childrens have the same specified value then I get this value
 * and they will be UNSPECIFIED.
 * A:{[B,C],x}					A:{[B,C],YES}
 * B:{[x,x],YES}				B:{[x,x],UNSPECIFIED}
 * C:{[x,x],YES}				C:{[x,x],UNSPECIFIED}
 */
	if (NULL!=b0 && NULL!=b1 &&
	  (t=b0->value)==b1->value && t!=UNSPECIFIED) { /* 2 similar real children */
		p->value=t;
		b0->value=b1->value=UNSPECIFIED;
		if (trace & D_OPT2) {
			printf("-opt2-\n");
			print_tree(&root,0,'=',p);
		}
	}

/*
 * 3.
 * If my child and me have same value he will be UNSPECIFIED.
 * A:{[B,NULL],YES}				A:{[B,NULL],YES}
 * B:{[x,x],YES}				B:{[x,x],UNSPECIFIED}
 */
	for (i=0; i<=1; i++) {
		register NODE *bi=p->b[i];

		if (NULL!=bi && bi->value==p->value) {
			bi->value=UNSPECIFIED;
			if (trace & D_OPT3) {
				printf("-opt3/%d-\n",i);
				print_tree(&root,0,'=',p);
			}
		}
	}

/*
 * 4.
 * UNSPECIFIED and childless child can be removed.
 * P:{[B,x],x}					P:{[NULL,x],x}
 * B:{[NULL,NULL],UNSPECIFIED}
 */

	for (i=0; i<=1; i++) {
		register NODE *bi=p->b[i];

		if (NULL!=bi && UNSPECIFIED==bi->value &&
			NULL==bi->b[0] && NULL==bi->b[1]) {
			freetree(bi);
			p->b[i]=NULL;
			if (trace & D_OPT4) {
				printf("-opt4/%d-\n",i);
				print_tree(&root,0,'=',p);
			}
		}
    }

	return;
}

/*
 * Count the differrent type nodes
 */
void tree_stat(p, counters)
NODE *p;
int *counters;
{
	if (NULL==p) return;
	tree_stat(p->b[0],counters);
	tree_stat(p->b[1],counters);
	counters[p->value]++;
}

/*
 * Print a graphical representation of the tree
 */
void print_tree(p, level, l, scope)
NODE *p;
int level;
/*char l;*/
int l;
NODE *scope;
{
	if (NULL==p) return;
	print_tree(p->b[1],level+1,'/',scope);
	printf("%c%*s%c%d,%s,%.8lx %s\n",p==scope?'*':' ',
		2*level-1,"",l,p->level,typ[p->value],p->addr,binaddr2dotted(p->addr));
	print_tree(p->b[0],level+1,'\\',scope);
}

/*
 * Print (sub)tree
 */
void print_acl(p, format)
NODE *p;
char *format;
{
	if (NULL==p) return;			/* empty tree */
	print_acl(p->b[0],format);	/* left subtree */
	print_acl(p->b[1],format);	/* right subtree */
	if (YES==p->value || NO==p->value && !opt_p) {
		char buffer[255];
		char *iptr, *optr, *tmp;
		for (iptr=format,optr=buffer; *iptr && optr<buffer+sizeof(buffer)-2; ) {
			if ('%'==(*optr++=*iptr++)) {
				--optr;
				switch (*iptr++) {
				case 'a':			/* address */
					optr+=sprintf(optr,"%s",
						binaddr2dotted(p->addr));
					break;
				case 'm':			/* modifier */
					optr+=sprintf(optr,"%s",
						YES==p->value?str_permit:str_deny);
					break;
				case 'k':			/* mask */
					optr+=sprintf(optr,"%s",
						binaddr2dotted(LEFTMASK(p->level)));
					break;
				case 'w':			/* wildcard */
					optr+=sprintf(optr,"%s",
						binaddr2dotted(RIGHTMASK(32-p->level)));
					break;
				case 'p':			/* prefix */
					optr+=sprintf(optr,"%d",p->level);
					break;
				case '\0':			/* unexpected end of format */
					--iptr;			/* force 'for' loop to break */
					break;
				default:			/* unexpected % sequence */
						*optr++=iptr[-1];
				}
			}
		}
		*optr='\0';
		puts(buffer);
	}
}

/*
 * Convert binary address to dotted decimal string
 */
char *binaddr2dotted(a)
ADDRESS a;
{
	static char buf[16];
	sprintf(buf,"%ld.%ld.%ld.%ld",a>>24&0xff,a>>16&0xff,a>>8&0xff,a&0xff);
	return buf;
}

/*
 * Compute prefix length for classful addresses
 */
int prefix_by_class(addr)
ADDRESS addr;
{
	if ( addr<LEFTMASK(1) && 0==(addr & RIGHTMASK(24)) ) return 8;
	if ( addr<LEFTMASK(2) && 0==(addr & RIGHTMASK(16)) ) return 16;
	if ( addr<LEFTMASK(3) && 0==(addr & RIGHTMASK( 8)) ) return 24;
	return 32;
}

/*
 * Return a pointer to a new node
 * or NULL if no memory left.
 */
NODE *allocnode()
{
	NODE *retval;
	int i;

	/*
	 * Nodes are allocated in BLKSIZE chunks to reduce
	 * malloc() housekeeping overhead
	 */
    if (NULL==freelist) {
		if (NULL==(freelist=
		  (NODE*)malloc((size_t)(BLKSIZE*sizeof(NODE)))))
			return NULL;
		freelist[BLKSIZE-1].b[0]=NULL;
		/* Insert new nodes into free list */
		for (i=BLKSIZE-2; i>=0; i--) freelist[i].b[0]=freelist+i+1;
	}
	/* Get the head of free list */
	retval=freelist;
	freelist=freelist->b[0];
	return retval;
}

/*
 * Put all nodes of subtree *n to the free list
 */
void freetree(n)
NODE *n;
{
	if (NULL==n) return;
	freetree(n->b[0]);
	freetree(n->b[1]);
	n->b[0]=freelist;
	freelist=n;
}

/*
 * Insert new node into the tree
 */
NODE *setnode(prefix, addr, value)
int prefix;
ADDRESS addr;
NODETYPE value;
{
	NODE *p,**pp;
	int level;
	ADDRESS a=addr;

	p=&root;
	level=0;
	prefix++;

	while (1) {
		if (NULL==p) {
			if ((p=allocnode())==NULL) return NULL;
			p->b[0]=p->b[1]=NULL;
			p->level=level;
			p->addr=addr & LEFTMASK(level);
			p->value=UNSPECIFIED;
			*pp=p;
		}

		pp=&p->b[HIGHBIT(a)];
		a<<=1;
		if (--prefix==NULL) break;
		level++;
		p=*pp;
	}
	if (INVERT(p->value)==value && !opt_s)
		fprintf(stderr,"WARNING: %s/%d overwritten (%s -> %s)\n",
			binaddr2dotted(addr),level,VALUE(p->value),VALUE(value));
	p->value=value;
	return p;
}

/*
 * Open input stream
 */
FILE *open_input(filename)
char *filename;
{
	if (NULL==filename) return stdin;
	if (!strcmp(filename,"-")) return stdin;
	return fopen(filename,"r");
}