#!/usr/bin/perl -w
use strict;
print "Content-type: text/html\n\n";
print "\<HTML\>\
\<HEAD\>\
\<TITLE\>Quiz\ \#2\<\/TITLE\>\
\<\/HEAD\>\
\<BODY\>\
\<SCRIPT\ type\=\"text\/javascript\"\ src\=\"\.\.\/\.\.\/pagetop\.js\"\>\<\/SCRIPT\>\
\<B\>Connected\:\ An\ Internet\ Encyclopedia\<\/B\>\
\<BR\>\
\<EM\>Quiz\ \#2\<\/EM\>\<BR\>\
\<HR\>\<CENTER\>\
\<B\>Up\:\<\/B\>\
\<A\ HREF\=\"\.\.\/\.\.\/index\.htm\"\>Connected\:\ An\ Internet\ Encyclopedia\<\/A\>\<BR\>\
\<B\>Up\:\<\/B\>\
\<A\ HREF\=\"\.\.\/index\.htm\"\>Programmed\ Instruction\ Course\<\/A\>\<BR\>\
\<B\>Up\:\<\/B\>\
\<A\ HREF\=\"index\.htm\"\>Subnetting\ and\ CIDR\<\/A\>\<BR\>\
\<\/CENTER\>\
\<B\>Prev\:\<\/B\>\ \<A\ HREF\=\"108\.htm\"\>Yet\ Another\ Example\<\/A\>\<BR\>\
\<B\>Next\:\<\/B\>\ \<A\ HREF\=\"201\.htm\"\>Historical\ Development\ of\ IP\ Addressing\<\/A\>\<BR\>\
\<HR\>\<P\>\
\<H3\>Quiz\ \#2\<\/H3\>\<P\>\
";
print "\<TITLE\>";
print "Quiz\ \#2";
print "\<\/TITLE\>";
print "\
\
";


my %FORM;
my $buffer;

if (exists $ENV{"CONTENT_LENGTH"}) {
    read(STDIN, $buffer, $ENV{'CONTENT_LENGTH'});
} elsif (exists $ENV{"QUERY_STRING"}) {
    $buffer = $ENV{"QUERY_STRING"};
}

# Split the name-value pairs
my @pairs = split(/&/, $buffer);

foreach my $pair (@pairs)
{
    my ($name, $value) = split(/=/, $pair);

    # Un-Webify plus signs and %-encoding
    $value =~ tr/+/ /;
    $value =~ s/%([a-fA-F0-9][a-fA-F0-9])/pack("C", hex($1))/eg;

    $FORM{$name} = $value;
}


# Play a little game here so we can tag each quiz with a unique ID value,
# to aid in recreating bugs.

my $quizseed;

if (exists $FORM{"seed"}) {
    $quizseed = $FORM{"seed"};
} else {
    srand;
    $quizseed = int rand 10000000000;
}

srand $quizseed;

# Possible subneting problems:

my @gifs = ('quiz2a.gif', 'quiz2b.gif', 'quiz2c.gif', 'quiz2d.gif', 'quiz2e.gif');
my @problems = ([['Third Floor LAN', 0],
	      ['Second Floor LAN', 0],
	      ['First Floor LAN', 0],
	      ['Basement LAN', 0],
	      ['Remote LAN', 0],
	      ['Backbone', 5],
	      ['WAN', 2]],
	     [['FDDI Ring', 3],
	      ['LAN A', 0],
	      ['LAN B', 0],
	      ['LAN C', 0],
	      ['LAN D', 0]],
	     [['Token Ring A', 0],
	      ['Token Ring B', 0],
	      ['Token Ring C', 0],
	      ['Token Ring D', 0],
	      ['Token Ring E', 0],
	      ['A-C WAN', 2],
	      ['B-D WAN', 2],
	      ['B-E WAN', 2]],
	     [['Ethernet A', 0],
	      ['Ethernet B', 0],
	      ['Ethernet C', 0],
	      ['WAN A', 2],
	      ['WAN B', 2],
	      ['WAN C', 2]],
	     [['Washington', 0],
	      ['London', 0],
	      ['Paris', 0],
	      ['Rome', 0],
	      ['ISDN', 4]],
	     );

my $probnum = int rand ($#gifs + 1);
my $gif = $gifs[$probnum];
my $problem = $problems[$probnum];
my $checkanswers=0;

my @powers = ();

for my $item (@$problem) {
    my $powerof2;

    if ($$item[1] == 0) {
	if (rand() <= 0.5) {
	    $$item[1] = int rand 256;
	} else {
	    $$item[1] = int rand 16;
	}
    }
    $$item[1] = 2 if ($$item[1] < 2);

    for ($powerof2=0; ($$item[1]+2) > (1<<$powerof2); $powerof2++) {}

    $powers[$powerof2]++;
}

my $bits;
my $carry=0;
for ($bits=0; $carry > 1 or $bits < @powers; $bits++) {
    $carry = int (($carry+1) / 2)  if ($carry > 1);
    $carry += $powers[$bits];
}
$bits --;

my @prefix = &randomPrefix(32 - $bits);


sub mask {
    my ($prefixLen) = @_;

    return 0 if ($prefixLen == 0);

    return (0xffffffff << (32-$prefixLen)) & 0xffffffff;
}

sub randomAddress {
    return ((1+(int rand 239)) << 24) | (int rand 1<<24);
}

sub randomPrefix {
    my ($prefixLen) = @_;
    my $prefixAddr = &randomAddress;

    $prefixAddr &= &mask($prefixLen);

    return ($prefixLen, $prefixAddr);
}

sub formatPrefixNoLen {
    my ($prefixLen, $prefixAddr) = @_;
    my $result = "";

    return "0" if ($prefixLen == 0);

    my $limit = 3 - int(($prefixLen-1)/8);

    for (my $i=3; $i >= $limit; $i--) {
	$result .= ($prefixAddr >> (8*$i)) & 255;
	$result .= "." unless ($i == $limit);
    }

    return $result;
}

sub formatPrefix {
    my ($prefixLen, $prefixAddr) = @_;

    return &formatPrefixNoLen($prefixLen, $prefixAddr) . "/$prefixLen";
}

sub formatAddress {
    my ($address, $separator) = @_;
    my @elements;

    if (not defined $separator) {
	$separator = '.';
    }

    for (my $i=0; $i < 4; $i ++) {
	unshift @elements, $address & 0xff;
	$address >>= 8;
    }

    return $elements[0] . $separator . $elements[1] . $separator
	. $elements[2] . $separator . $elements[3];
}

sub contains {
    my ($len1, $addr1, $len2, $addr2) = @_;

    return 0 if ($len1 > $len2);
    return ((&mask($len1) & $addr1) == (&mask($len1) & $addr2));
}

sub parsePrefix {
    my ($userin) = @_;
    my $start = 0;
    my $end = -1;
    my $elementsSeen = 0;
    my @address = (0,0,0,0);
    my $address2;
    my $prefixlen;

    while ((($end = index($userin, ".", $end+1)) != -1) ||
	   (($end = index($userin, "/", $end+1)) != -1)) {
	if ($elementsSeen == 4) {
	    die "Dotted quad portion must contain no more than four numbers";
	    return;
	}
	if ($end-$start == 0) {
	    die "Syntax: A.B.C.D/N";
	    return;
	}
	$address[$elementsSeen] = substr($userin, $start, $end-$start);
	if (($address[$elementsSeen] < 0) || ($address[$elementsSeen] > 255)) {
	    die "Dotted quad elements must be between 0 and 255";
	    return;
	}

	if ($address[$elementsSeen] !~ m:^[0-9]+$:) {
	    die "Syntax: A.B.C.D/N";
	    return;
	}

	if ($address[$elementsSeen]!=0 && $address[$elementsSeen] =~ m:^0:) {
	    die "By convention, leading zeros are not written";
	    return;
	}

	$elementsSeen ++;
	$start = $end+1;

	last if (substr($userin, $end) =~ m:^/:);
    }

#    if ($end == -1 || substr($userin, $end) !~ m:^/:) {
#	die "Missing prefix length";
#	return;
#    }
#    if ($end == length($userin)-1) {
#	die "Missing prefix length";
#	return;
#    }
    $prefixlen = substr($userin,$end+1);

    if ($prefixlen !~ m:^[0-9]+$:) {
	die "Syntax: A.B.C.D/N";
	return;
    }

    if ($prefixlen!=0 && $prefixlen =~ m:^0:) {
	die "By convention, leading zeros are not written";
	return;
    }




    if ($prefixlen < 0) {
	die "Prefix length must be between 0 and 32";
	return;
    } elsif ($prefixlen > 8 && $prefixlen <= 16) {
	if ($elementsSeen < 2) {
	    die "Must specify two bytes of address for a prefix length of $prefixlen";
	    return;
	}
    } elsif ($prefixlen > 16 && $prefixlen <= 24) {
	if ($elementsSeen < 3) {
	    die "Must specify three bytes of address for a prefix length of $prefixlen";
	    return;
	}
    } elsif ($prefixlen > 24 && $prefixlen <= 32) {
	if ($elementsSeen < 4) {
	    die "Must specify four bytes of address for a prefix length of $prefixlen";
	    return;
	}
    } elsif ($prefixlen > 32) {
	die "Prefix length must be between 0 and 32";
	return;
    }

    $address2 = ($address[0]<<24)|($address[1]<<16)
	|($address[2]<<8)|$address[3];

    if (($address2 & &mask($prefixlen)) != $address2) {
	die "Trailing bits not zero";
	return;
    }

    return ($prefixlen, $address2);
}

print "Quiz ID code: subnet-$quizseed
<P>
The address prefix <TT>";

print &formatPrefix(@prefix), "</TT> has been assigned to
the diagrammed network.  Assign address prefixes to each of
the subnets.
<P>
<CENTER><IMG SRC=\"$gif\"></CENTER>
<P>
<CENTER><B>", &formatPrefix(@prefix), "</B></CENTER>
<P>

<SCRIPT>

var baseprefixlen = $prefix[0]
var baseprefix = new Array(", &formatAddress($prefix[1], ','), ")
var basestr = '", &formatPrefix(@prefix), "'

var subnets = new Array()
var subnetlens = new Array()
var subnetstr = new Array()

var ordinal = new Array(\"first\", \"second\", \"third\", \"fourth\")
var address = new Array(0,0,0,0)
var mask = new Array(0,0,0,0)

function Answer(question) {
   document.FORM[question].value = \"\"
   for (var i=1; i<Answer.arguments.length; i++) {
      document.FORM[question].value += Answer.arguments[i]
      if (i < Answer.arguments.length-1) {
          document.FORM[question].value += unescape(\"%0d%0a\")
      }
   }
}

function setmask(prefixlen) {
   if (prefixlen <= 8) {
      mask[0] = (255<<(8-prefixlen))&255
      mask[1] = 0
      mask[2] = 0
      mask[3] = 0
   } else if (prefixlen > 8 && prefixlen <= 16) {
      mask[0] = 255
      mask[1] = (255<<(16-prefixlen))&255
      mask[2] = 0
      mask[3] = 0
   } else if (prefixlen > 16 && prefixlen <= 24) {
      mask[0] = 255
      mask[1] = 255
      mask[2] = (255<<(24-prefixlen))&255
      mask[3] = 0
   } else if (prefixlen > 24 && prefixlen <= 32) {
      mask[0] = 255
      mask[1] = 255
      mask[2] = 255
      mask[3] = (255<<(32-prefixlen))&255
   }
}

function parsePrefix(userin) {
   var start = 0
   var end = -1
   var elementsSeen = 0
   var i

   error = \"\"
   address[0] = 0
   address[1] = 0
   address[2] = 0
   address[3] = 0

   while (((end = userin.indexOf(\".\", end+1)) != -1) ||
          ((end = userin.indexOf(\"/\", end+1)) != -1)) {
      if (elementsSeen == 4) {
         error = \"Dotted quad portion must contain no more than four numbers\"
         return
      }
      if (end-start == 0) {
         error = \"Syntax: A.B.C.D/N\"
         return
      }
      address[elementsSeen] = userin.slice(start,end)
      if ((address[elementsSeen] < 0) || (address[elementsSeen] > 255)) {
         error = \"Dotted quad elements must be between 0 and 255\"
         return
      }

      // Check for NaN on systems that implement it, but do so in a way
      // that works on those that don't
      if ((! (address[elementsSeen] >= 0)) &&
          (! (address[elementsSeen] <= 255))) {
         error = \"Syntax: A.B.C.D/N\"
	 return
      }

      // Check for NaN on systems that don't implement it
      if (address[elementsSeen] == 0 &&
          ((address[elementsSeen].length != 1) ||
           (address[elementsSeen].charAt(0) != \"0\"))) {
         error = \"Syntax: A.B.C.D/N\"
	 return
      }

      if (address[elementsSeen]!=0 && address[elementsSeen].charAt(0)==\"0\") {
         error = \"By convention, leading zeros are not written\"
	 return
      }

      elementsSeen ++
      start = end+1

      if (userin.charAt(end) == \"/\") break
   }

   if (end == -1 || userin.charAt(end) != \"/\") {
      error = \"Missing prefix length\"
      return
   }
   if (end == userin.length-1) {
      error = \"Missing prefix length\"
      return
   }
   prefixlen = userin.slice(end+1)

   // Check for NaN on systems that implement it, but do so in a way
   // that works on those that don't
   if ((! (prefixlen >= 0)) && (! (prefixlen <= 255))) {
      error = \"Syntax: A.B.C.D/N\"
      return
   }

   // Check for NaN on systems that don't implement it
   if (prefixlen == 0 &&
       ((prefixlen.length != 1) ||
        (prefixlen.charAt(0) != \"0\"))) {
      error = \"Syntax: A.B.C.D/N\"
      return
   }

   if (prefixlen!=0 && prefixlen.charAt(0)==\"0\") {
      error = \"By convention, leading zeros are not written\"
      return
   }

   if (prefixlen < 0) {
      document.FORM[output].value = \"Prefix length must be between 0 and 32\"
      return
   } else if (prefixlen <= 8) {
      mask[0] = (255<<(8-prefixlen))&255
      mask[1] = 0
      mask[2] = 0
      mask[3] = 0
   } else if (prefixlen > 8 && prefixlen <= 16) {
      mask[0] = 255
      mask[1] = (255<<(16-prefixlen))&255
      mask[2] = 0
      mask[3] = 0
   } else if (prefixlen > 16 && prefixlen <= 24) {
      mask[0] = 255
      mask[1] = 255
      mask[2] = (255<<(24-prefixlen))&255
      mask[3] = 0
   } else if (prefixlen > 24 && prefixlen <= 32) {
      mask[0] = 255
      mask[1] = 255
      mask[2] = 255
      mask[3] = (255<<(32-prefixlen))&255
   } else {
      document.FORM[output].value = \"Prefix length must be between 0 and 32\"
      return
   }

   for (i=0; i<4; i++) {
      if ((address[i] & mask[i]) != address[i]) {
         error = \"Trailing bits not zero in \"
	 error += ordinal[i] + \" byte\"
         return
      }
   }
}

function doAnswer(index, input, hosts) {
   var userin = document.FORM[input].value

   delete subnets[index]

   if (userin == \"\") {
      document.FORM['Response'].value = \"\"
      document.FORM[input].value = ''
      document.FORM[input].focus()
      return
   }

   parsePrefix(userin)
   if (error != \"\") {
      document.FORM['Response'].value = userin + ' - ' + error
      document.FORM[input].value = ''
      document.FORM[input].focus()
      return
   }

   if (prefixlen < baseprefixlen) {
      document.FORM['Response'].value = userin + ' isn\\'t an extension of '
      document.FORM['Response'].value += basestr
      document.FORM[input].value = ''
      document.FORM[input].focus()
      return
   }

   setmask(baseprefixlen)
   for (i=0; i<4; i++) {
      if ((address[i] & mask[i]) != baseprefix[i]) {
         document.FORM['Response'].value = userin + ' isn\\'t an extension of '
         document.FORM['Response'].value += basestr
         document.FORM[input].value = ''
         document.FORM[input].focus()
         return
      }
   }

   if (((1 << (32-prefixlen)) - 2) < hosts) {
      document.FORM['Response'].value = userin + ' can\\'t support '
      document.FORM['Response'].value += hosts + ' hosts'
      document.FORM[input].value = ''
      document.FORM[input].focus()
      return
   }

   var subnetscount = 0

   checksubnets: for (i=0; i < subnets.length; i++) {
      if (subnets[i]) {
         subnetscount ++

         if (subnetlens[i] < prefixlen) {
            setmask(subnetlens[i])
         } else {
            setmask(prefixlen)
         }
         for (j=0; j<4; j++) {
            if ((address[j] & mask[j]) != (subnets[i][j] & mask[j])) {
               continue checksubnets
            }
         }
         document.FORM['Response'].value = userin + ' overlaps '
         document.FORM['Response'].value += subnetstr[i]
         document.FORM[input].value = ''
         document.FORM[input].focus()
         return
      }
   }

   subnets[index] = new Array(address[0], address[1], address[2], address[3])
   subnetlens[index] = prefixlen
   subnetstr[index] = userin

   if (subnetscount == $#$problem) {
      document.FORM['Response'].value = 'Great!  You\\'ve solved the problem!'
   } else {
      document.FORM['Response'].value = 'OK... keep going'
   }
}

</SCRIPT>

<FORM NAME=\"FORM\" onSubmit=\"return false\">
<TABLE>
<TR><TH><TH>Number of Hosts<TH><TH>Address Prefix\n";

my $wrong = 0;
my @answers = ();

for (my $i=0; $i <= $#$problem; $i ++) {
     my $item = $$problem[$i];
     print "<TR><TD>$$item[0]<TD ALIGN=RIGHT>$$item[1]<TD><TD><INPUT SIZE=25 NAME=\"$$item[0]\" onChange=\"doAnswer($i,'$$item[0]',$$item[1])\">\n";
}

print "<TR><TD COLSPAN=4><TEXTAREA NAME=\"Response\" COLS=64 ROWS=6></TEXTAREA>\n";

print "</TABLE></FORM>\n";

print "\
";
print "\<P\>\<HR\>\
\<CENTER\>\<B\>Next\:\<\/B\>\ \<A\ HREF\=\"201\.htm\"\>Historical\ Development\ of\ IP\ Addressing\<\/A\>\<\/CENTER\>\<HR\>\
\<B\>Connected\:\ An\ Internet\ Encyclopedia\<\/B\>\
\<BR\>\
\<EM\>Quiz\ \#2\<\/EM\>\
\<\/BODY\>\
\<\/HTML\>\
";