/*
 *
 * masks.c -- IP/DECnet/Appletalk access list creator
 *
 *            XNS style lists are not done as the hexidecimal base used
 *            in these protocols makes the access lists trivial to compute
 *            by hand.
 *
 *   October 1989, Joel P. Bion
 *
 *   Copyright (c) 1989, 1990 by cisco Systems, Inc.
 *
 * This "masks" program 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.
 *
 *
 * Code assumptions:
 *        "unsigned" is at least 32 bits long.
 *
 * Calling convention:
 *
 *     Interactive use:
 *
 *               masks
 *            -- It will prompt for usage, and output lists will go to stdout.
 *     or:
 *               masks outfile
 *            -- It will prompt for usage, and output lists will go to outfile.
 *
 *     Non-interactive use:
 *               masks outfile infile
 *            -- Output masks to "outfile." Input masks from "infile" -- no
 *               prompting, and error messages give line numbers.
 */
#include <stdio.h>

#define FALSE 0
#define TRUE 1
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))

#define INTERACTIVE(f) ((f) == stdin)

#define LOWPROT 1
#define APPLETALK 1
#define DECNET 2
#define IP 3
#define QUITPROTOCOL 4
#define HIGHPROT 4
#define MAXINPUT 80

/* Ranges for allowed addresses */
typedef struct _range {
	 unsigned lowr;
	 unsigned highr;
	 struct _range *next;
} range;

/* Head of list of adds. to build masks for (protocol to use + addresses) */
typedef struct _addsneeded {
	int protocol;
	range *range;
} addsneeded;

/* What a mask is */
typedef unsigned maskfield;

/* A single address mask */
typedef struct _mask {
	maskfield start;
	maskfield mask;
	struct _mask *next;
} mask;


/* Information about a particular protocol (Makes core code more general) */
typedef struct _proto_info {
	int maxval;
	int (*getranges)();	/* Routine to get ranges */
	void (*printmask)();    /* Routine to print a mask */
	mask *(*bmask)();        /* Building masks */
	int lowmaskvalue;	/* Low mask value */
	char *defaultdeny;	/* Default deny string  */
} proto_info;



typedef char instr[MAXINPUT];	/* Current input string */
mask *masksfree;		/* Mask free list */
int lineno;			/* Current input line number */
proto_info protocols[HIGHPROT];	/* Array of protocol "templates" */

/*
 * Allocate a mask. Take one off free list if it is already there.
 * Initialize contents.
 */
mask *mask_malloc()
{
	mask *give;

	/* One on free list? */
	if (masksfree != NULL) {
		 give = masksfree;
		 masksfree = masksfree->next;
	}
	/* No -- malloc a new one */
	else
	  if ((give = (mask *) malloc(sizeof(mask))) == NULL) {
		fprintf(stderr,"Failed to allocate memory for a mask!\n");
		exit(1);
	}

	/* Initialize its contents */
	give->next = NULL;
	give->start = 0;
	give->mask = 0;
	return(give);
}

/* Return a mask to the free list */
void free_mask(oldone)
     mask *oldone;
{
	if (oldone != NULL) {
		oldone->next = masksfree;
		masksfree = oldone;
	}
}

/*
 * Merge mask lists. Essentially, plop m2 to the end of m1. Not
 * efficient, but this code doesn't need to be.
 */
mask *merge_masks(m1, m2)
    mask *m1;
    mask *m2;
{
	mask *here, *prev;
	for (here = m1, prev = NULL; (here != NULL);
	     prev = here, here = here->next)
	    ;
	return((prev == NULL) ? (m2) : ((prev->next = m2), m1));
}

/*
 * Return non-zero if the range "s -- e" is completely out of the range
 * of the addresses needed in the list "a". Note that this is NOT
 * simply the inverse of "outrange".
 */
int outrange(a,s,e)
    addsneeded *a;
    maskfield s;
    maskfield e;
{
	range *r;
	for (r = a->range; ((r != NULL) && (r->lowr <= e)); r = r->next) {
		if (((r->lowr >= s) && (r->highr <= e)) ||
		    ((r->lowr <= s) && (r->highr >= s)) ||
		    ((r->lowr <= e) && (r->highr >= e)) ||
		    ((r->lowr <= s) && (r->highr >= e))) {
			return(0);
		}
	}
	return(1);
}
    

/*
 * Return non-zero if the range "s -- e" is completely in the range
 * of the addresses needed in the list "a". Note that this is NOT
 * simply the inverse of "outrange".
 */
int inrange(a,s,e)
    addsneeded *a;
    maskfield s;
    maskfield e;
{
	range *r;
	for (r = a->range; ((r != NULL) && (r->lowr <= e)); r = r->next) {
		if ((r->lowr <= s) && (r->highr >= e)) {
			return(1);
		}
	}
	return(0);
}

/*
 * Build a list of Appletalk masks. Appletalk is easy. Simply return a
 * list of the networks specified!!
 */
mask *b_appletalk_masks(a, start, end)
    addsneeded *a;
    maskfield start;
    maskfield end;
{
	mask *ml = NULL, *m = NULL;
	range *r;

	for (r = a->range; (r != NULL); r = r->next) {
		m = mask_malloc();
		m->start = r->lowr;
		m->mask = 0;
		m->next = ml;
		ml = m;
	}
	return(ml);
}

/*
 * Generalized mask building routine for network addresses up to one
 * hardware word big. "a" is a list of address ranges to "permit". "s"
 * is a lowbound address -- "e" is the highbound address. On the outermost
 * call to this, all possible addresses should be encompassed in the range
 * of "start" to "end".
 */
mask *b_m_level(a, start, end)
    addsneeded *a;
    maskfield start;
    maskfield end;
{
	maskfield s, e;
	mask *ml = NULL, *m = NULL;
	maskfield mplier;
	maskfield os;

	/*
	 * Terminating case. (Two addresses) Check for single entry masks for
	 * start and end
	 */
	if ((end - start) == 1)  {
		for (s = start; s <= end; s++) {
			if (inrange(a, s, s)) {
				m = mask_malloc();
				m->start = s;
				m->mask = 0;
				m->next = ml;
				ml = m;
			}
		}
		return(ml);
	}
	/* 
         * More general case. Approach from start to end in increasing mask
         * "widths" of powers of two. For each, see if mask falls completely
	 * within the allowed range. If it is -- build a mask for it,
         * possibly combining (optimizing) with the previous found mask.
         * If the mask found is completely outside the range -- build no
         * mask for this range. If what is found falls somewhat in the range,
         * but also somewhat out, recurse on this function with this range
         * to approach that "part in/part out" area.
         */
	for (mplier = 1, s = start, e = start + 1, os = s;
	     ((e <= end) && (os <= s));
	     os = s, s = e + 1, mplier <<= 1, e = e + mplier) {
		if (outrange(a,s,e)) {
			continue;
		}
		if (inrange(a,s,e)) {
		  /* Possibly merge last gotten mask with this */ 
			if ((ml != NULL) &&
			    (((ml->start + ml->mask) + 1) == s) &&
			    ((ml->start & ~(((e - s) << 1) + 1)) == ml->start))
			  {
				ml->mask = (((e - s) << 1) + 1);
			} else {
				m = mask_malloc();
				m->start = s;
				m->mask = e - s;
				m->next = ml;
				ml = m;
			}
		} else {
			if (s < e) {
				m = b_m_level(a, s, e);
				ml = merge_masks(m, ml);
			}
		}
	}
	return(ml);
}

/*
 * Simply named routine for building masks which will use the protocol
 * specific info to make the real call.
 */
mask *build_masks(a)
    addsneeded *a;
{
	mask *m;
	m = (protocols[a->protocol].bmask)(a, (maskfield) 0,
					     protocols[a->protocol].maxval);
	return(m);
}

/* Be nice to the user (if they are "interactive") */
void printhi(f)
     FILE *f;
{
   if (INTERACTIVE(f)) {
     printf("This program will help you to build the small set of\n");
     printf("access lists to meet your needs. It understands various protocols.\n");
     printf("Note that it builds a set of PERMISSIVE masks, and does not\n");
     printf("further attempt to optimize by using a set of permits and denys\n");
     printf("together.\n");
   }
}

/* Get a line of input from the input file. Be nice with excess input */
#define INEOF -1
int getline(f, s)
    FILE *f;
    instr s;
{
  int len;
  instr extrastr;
  
	if (fgets(s, MAXINPUT, f) == NULL) {
	  return(INEOF);
	} else {
	  len = strlen(s);
	  if (len > 0) {
	    if (s[len - 1] == '\n') {
	      s[len - 1] = '\0';
	    } else {
	      fprintf(stderr, "Discarding excess input");
	      if (INTERACTIVE(f)) {
		fprintf(stderr,".\n");
	      }
	      else {
		fprintf(stderr, " on line %d.\n", lineno);
	      }
	      for (;;) {
		if (fgets(extrastr, MAXINPUT, f) == NULL) {
		  break;
		}
		if (extrastr[strlen(extrastr) - 1] == '\n') {
		  break;
		}
	      }
	    }
	  }
	  lineno++;
	  return(MAX((len - 1), 0));
	}
}

/* Simpleminded input error message */
void inputerror(f, str)
     FILE *f;
{
  fprintf(stderr, "Input error %s", str); 
  if (INTERACTIVE(f)) {
    fprintf(stderr, ".\n");
  } else {
    fprintf(stderr, " on line %d.\n", lineno);
  }
}

/* Accept the user's choice of a protocol */
void chooseprotocol(f, a)
     FILE *f;
    addsneeded *a;
{
  instr s;
  int len;
  for  (a->protocol = (LOWPROT - 1);
	((a->protocol < LOWPROT) || (a->protocol > HIGHPROT));) {
    if (INTERACTIVE(f)) {
      printf("Choose a protocol:\n");
      printf("\t%d) APPLETALK\n", APPLETALK);
      printf("\t%d) DECNET\n", DECNET);
      printf("\t%d) IP\n", IP);
      printf("\t%d) QUIT\n", QUITPROTOCOL);
      printf("[quit] => ");
    }
    if (((len = getline(f, s)) == 0) || (len == INEOF)) {
      a->protocol = QUITPROTOCOL;
    }
    else {
      if (sscanf(s, "%d", &(a->protocol)) != 1) {
	inputerror(f, "on entering protocol choice");
	if (INTERACTIVE(f)) {
	  a->protocol = LOWPROT - 1;
	} else {
	  fprintf(stderr,"Aborting run.\n");
	  a->protocol = QUITPROTOCOL;
	}
      }
    }
  }
}

/*
 * Take a range given by the user, and place it into an existing range list,
 * merging this new range with any existing ranges with which it may overlap
 * (Simple optimization here leads to big win when building masks).
 */ 
void place_range(a, r)
     addsneeded *a;
     range *r;
{
  range *here, *next;
  int rin = FALSE;
  
  if ((here = a->range) == NULL) {
    a->range = r;
    return;
  }
  for (here = NULL, next = a->range; (next != NULL);
       here = next, next = next->next) {

    /* Fits in cleanly after here? (Allow abutting things to merge) */
    if (r->lowr > (next->highr + 1)) {
	    continue;
    }
	  
    /* Fits in cleanly before here? (Allow abutting things to merge) */
    if (r->highr < (next->lowr - 1)) {
      if (here != NULL)
	here->next = r;
      else
	a->range = r;
      r->next = next;
      return;
    }
    /* Overlaps COMPLETELY any of the next ones (in series)? */
    if (r->highr >= (next->highr - 1)) {
	    rin = TRUE;
	    if (here != NULL)
		here->next = r;
	    else
		a->range = r;
    }
    for (; ((next != NULL) && (r->highr >= (next->highr - 1)));) {
      r->next = next->next;
      r->lowr = MIN(next->lowr, r->lowr);
      r->highr = MAX(next->highr, r->highr);
      free(next);
      next = r->next;
    }

    /* Overlaps the next one at all? */
    if ((next != NULL) && (r->highr >= (next->lowr - 1))) {
      next->lowr = MIN(next->lowr, r->lowr);
      next->highr = MAX(next->highr, r->highr);
      if (rin) {
	      if (here != NULL)
		  here->next = next;
	      else
		  a->range = next;
      }
      free(r);
    }
    return;
  }
  here->next = r;
  r->next = NULL;
}


/* Get a list of IP address ranges. Simpleminded code. */
int get_ip_ranges(f, a)
     FILE *f;
    addsneeded *a;
{
  maskfield lowa, lowb, lowc, lowd, higha, highb, highc, highd;
  int good;
  maskfield lowadd, highadd;

  range *r;
  instr s;
  int len;

  for (;;) {
    for (good = 0; !good; ) {
      good = 1;
      if (INTERACTIVE(f)) {
	printf("Enter a (low-range) IP address (return to stop): ");
      }
      if (((len = getline(f, s)) == INEOF) || (len == 0)) {
	return(1);
      }
      if ((sscanf(s, "%u.%u.%u.%u", &lowa, &lowb, &lowc, &lowd) != 4) ||
	  ((lowa < 0) || (lowa > 255)) ||
	  ((lowb < 0) || (lowb > 255)) ||
	  ((lowc < 0) || (lowc > 255)) ||
	  ((lowd < 0) || (lowd > 255))) {
	inputerror(f, "on entering IP low range");
	if (!INTERACTIVE(f)) {
	  fprintf(stderr,"Aborting run.\n");
	  return(0);
	}
	good = 0;
	continue;
      }
      lowadd = ((lowa << 24) | (lowb << 16) | (lowc << 8) | (lowd));
      if (INTERACTIVE(f)) {
        printf("Enter a (high-range) IP address (return to choose one value): ");
      }
      if ((len = getline(f, s)) == INEOF) {
	return(0);
      }
      if (len == 0) {
	highadd = lowadd;
      } else {
	if ((sscanf(s, "%u.%u.%u.%u", &higha, &highb, &highc, &highd) != 4) ||
	    ((higha < 0) || (higha > 255)) ||
	    ((highb < 0) || (highb > 255)) ||
	    ((highc < 0) || (highc > 255)) ||
	    ((highd < 0) || (highd > 255)) ||
	    ((highadd =
	     ((higha << 24) | (highb << 16) | (highc << 8) | (highd))),
	     highadd < lowadd)) {
		inputerror(f, "on entering IP high range");
		if (!INTERACTIVE(f)) {
			fprintf(stderr,"Aborting run.\n");
			return(0);
	  }
	  good = 0;
	}
      } }
    if ((r = (range *) malloc(sizeof(range))) == NULL) {
      fprintf(stderr, "Cannot allocate range record!\n");
      exit(1);
    }
    r->lowr = lowadd;
    r->highr = highadd;
    place_range(a, r);
  }
}

/* Get a list of appletalk ranges... */
int get_appletalk_ranges(f, a)
     FILE *f;
    addsneeded *a;
{
	maskfield anet;
	int good;

	range *r, *rl;
	instr s;
	int len;

	for (;;) {
		for (good = 0; !good; ) {
			good = 1;
			if (INTERACTIVE(f)) {
				printf("Enter an APPLETALK network (return to stop): ");
			}
			if (((len = getline(f, s)) == INEOF) || (len == 0)) {
				return(1);
			}
			if (sscanf(s, "%u", &anet) != 1) {
				inputerror(f, "on entering APPLETALK network");
				if (!INTERACTIVE(f)) {
					fprintf(stderr,"Aborting run.\n");
					return(0);
				}
				good = 0;
				continue;
			}
		}
		for (r = a->range; ((r != NULL) && (r->lowr != anet)); r = r->next)
		    ;
		if (r == NULL) {
			if ((r = (range *) malloc(sizeof(range))) == NULL) {
				fprintf(stderr, "Cannot allocate range record!\n");
				exit(1);
			}
			r->lowr = anet;
			r->highr = anet;
			r->next = a->range;
			a->range = r;
		}
	}
}

/* Get a list of decnet ranges... */
int get_decnet_ranges(f, a)
     FILE *f;
    addsneeded *a;
{
  maskfield lowa, lown, higha, highn;
  int pval;
  int good;

  range *r;
  instr s;
  int len;

  for (;;) {
    for (good = 0; !good; ) {
      good = 1;
      if (INTERACTIVE(f)) {
	printf("Enter a (low-range) DECNET address (return to stop): ");
      }
      if (((len = getline(f, s)) == INEOF) || (len == 0)) {
	return(1);
      }
      if ((sscanf(s, "%u.%u", &lowa, &lown) != 2) ||
	  ((lowa < 0) || (lowa > 63)) ||
	  ((lown < 0) || (lown > 1023))) {
	inputerror(f, "on entering DECNET low range");
	if (!INTERACTIVE(f)) {
	  fprintf(stderr,"Aborting run.\n");
	  return(0);
	}
	good = 0;
	continue;
      }
      if (INTERACTIVE(f)) {
        printf("Enter a (high-range) DECNET address (return to choose one value): ");
      }
      if ((len = getline(f, s)) == INEOF) {
	return(0);
      }
      if (len == 0) {
	higha = lowa;
	highn = lown;
      } else {
	if ((sscanf(s, "%u.%u", &higha, &highn) != 2) ||
	    ((higha < 0) || (higha > 63) || (higha < lowa)) ||
	    ((highn < 0) || (highn > 1023) ||
	     ((higha == lowa) ? (highn < lown) : (0)))) {
	  inputerror(f, "on entering DECNET high range");
	  if (!INTERACTIVE(f)) {
	    fprintf(stderr,"Aborting run.\n");
	    return(0);
	  }
	  good = 0;
	}
      }
    }
    if ((r = (range *) malloc(sizeof(range))) == NULL) {
      fprintf(stderr, "Cannot allocate range record!\n");
      exit(1);
    }
    r->lowr = lowa*1024 + lown;
    r->highr = higha*1024 + highn;
    place_range(a, r);
  }
}

/* Nice, general call for getting ranges. Will call protocol specific code */
int getranges(f, a)
     FILE *f;
    addsneeded *a;
{
	return((protocols[a->protocol].getranges)(f,a));
}

/* Print out an IP mask */
void ip_print_mask(outf, m)
    FILE *outf;
    mask *m;
{
	fprintf(outf, "%d.%d.%d.%d %d.%d.%d.%d\n",
		((m->start & 0xff000000) >> 24),
		((m->start & 0x00ff0000) >> 16),
		((m->start & 0x0000ff00) >> 8),
		(m->start & 0x000000ff),
		((m->mask & 0xff000000) >> 24),
		((m->mask & 0x00ff0000) >> 16),
		((m->mask & 0x0000ff00) >> 8),
		(m->mask & 0x000000ff));

}

/* Print out a DECnet masks */
void decnet_print_mask(outf, m)
    FILE *outf;
    mask *m;
{
	fprintf(outf,"%d.%d %d.%d\n",
		((m->start & 0xfc00) >> 10),
		(m->start & 0x3ff),
		((m->mask & 0xfc00) >> 10),
		(m->mask & 0x3ff));
}

/* Print out an appletalk mask */
void appletalk_print_mask(outf, m)
    FILE *outf;
    mask *m;
{
	fprintf(outf,"%d\n", m->start);
}

/*
 * Print out a list of masks -- calling the protocol specific routine for
 * each. 
 */
void masks_print(a, mlist, outf)
    addsneeded *a;
     mask *mlist;
    FILE *outf;
{
	mask *m;
	void (*pm)();

	pm = protocols[a->protocol].printmask;
	fprintf(outf, "As an example:\n");
	for (m = mlist; (m != NULL); m = m->next) {
	  fprintf(outf, "access-list %d permit ",
		  protocols[a->protocol].lowmaskvalue);
		(pm)(outf, m);
	}
	fprintf(outf, "access-list %d deny %s\n(The last entry is optional)\n",
		protocols[a->protocol].lowmaskvalue,
		protocols[a->protocol].defaultdeny);
}

/* Sets of routines to initialize the "protocol definition structures" */
void init_ip_protocol()
{
	protocols[IP].maxval = 0xffffffff;
	protocols[IP].getranges = get_ip_ranges;
	protocols[IP].printmask = ip_print_mask;
	protocols[IP].bmask = b_m_level;
	protocols[IP].lowmaskvalue = 1;
	protocols[IP].defaultdeny = "0.0.0.0 255.255.255.255";
}

void init_decnet_protocol()
{
	protocols[DECNET].maxval = 0xffff;
	protocols[DECNET].getranges = get_decnet_ranges;
	protocols[DECNET].printmask = decnet_print_mask;
	protocols[DECNET].bmask = b_m_level;
	protocols[DECNET].lowmaskvalue = 300;
	protocols[DECNET].defaultdeny = "0.0 63.1023";
}

void init_appletalk_protocol()
{
	protocols[APPLETALK].maxval = 0xffffffff;
	protocols[APPLETALK].getranges = get_appletalk_ranges;
	protocols[APPLETALK].printmask = appletalk_print_mask;
	protocols[APPLETALK].bmask = b_appletalk_masks;
	protocols[APPLETALK].lowmaskvalue = 600;
	protocols[APPLETALK].defaultdeny = "-1";
}

/* Initialize the various protocol structures */
void init()
{
	masksfree = NULL;
	lineno = 0;
	init_ip_protocol();
	init_decnet_protocol();
	init_appletalk_protocol();
}

/* Set up arguments, call core processing routines */
int main(argc,argv)
    int argc;
    char **argv;
{
	mask *mlist;
	addsneeded a;
	FILE *inf = stdin;
	FILE *outf = stdout;

	
	if (argc > 1) {
		if ((outf = fopen(argv[1], "w")) == NULL) {
			fprintf(stderr,
				"File %d cannot be opened for writing.\n",
				argv[1]);
			exit(1);
		}
		if (argc > 2) {
			if ((inf = fopen(argv[2], "r")) == NULL) {
				fprintf(stderr,
					"File %d cannot be opened for reading.\n",
					argv[2]);
			}
		}
	}
	init();
	a.range = NULL;
	printhi(inf);
	chooseprotocol(inf, &a);
	if (a.protocol == QUITPROTOCOL) {
		printf("Okay -- bye.\n");
		exit(0);
	}
	if (getranges(inf, &a)) {
	  mlist = build_masks(&a);
	  masks_print(&a, mlist, outf);
	}
}