Nov 96 Challenge
- Jan 96 Challenge
- Feb 96 Challenge
- Mar 96 Challenge
- Apr 96 Challenge
- May 96 Challenge
- Jun 96 Challenge
- Jul 96 Challenge
- Aug 96 Challenge
- Sep 96 Challenge
- Oct 96 Challenge
- Dec 96 Challenge
Volume Number: 12
Issue Number: 11
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Bob Boonstra
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Router Rules
This month’s Challenge is based on a suggestion by Peter Lewis and is motivated
by a real-world problem. A certain university has a B-class IP subnet, let’s call it
199.232.*.* (with apologies to the real-world owner of that subnet). The subnet is
broken down into 256 networks for the various faculties and departments, each one
having 256 IP numbers. So, for example, the computer club might have
199.232.101.*. Our hypothetical university is charged for communications based on
volume, so some of these networks are allowed to talk to the outside world, and others
are not. Outside access is controlled by programming a router with a sequence of rules,
each of which allows or denies access to some subset of IP numbers. A rule consists of a
(mask, value, allow) triplet. For example, say the networks (in hex) 01, 03, 41, 43
are allowed out, and all the rest are barred. The rules could be simply
FF, 01, allow
FF, 03, allow
FF, 41, allow
FF, 43, allow
00, 00, deny
But this could be simplified to
BD, 01, allow
00, 00, deny
Your objective for this Challenge is to quickly generate a small sequence of rules
that allows outside network access to only a specified set of networks. The prototype
for the code you should write is
enum {kDeny=0, kAllow=1};
typedef struct Rule {
long mask;
long value;
long allow; /* 0 == deny, 1== allow */
} Rule;
long RouterRules(
long allowedValues[],
long numAllowedValues,
long numBits,
Rule rulesArray[],
long maxRules
);
The array allowedValues is the set of numAllowedValues networks that are to
be given outside network access. All other networks should be denied access. Instead of
being limited to 8 bits as in the example above, network values have numBits bits.
Your code should generate a sequence of rules that provides access to these networks,
and no others. The rule sequence should be as short as possible and stored in
rulesArray, which is allocated by the caller and is of size maxRules. Your code should
return the number of rules generated, or return -1 if it cannot find a solution no
longer than maxRules.
Rules will be triggered by the router in the order provided by your solution, and
the first rule to fire for a given network will apply. At least one rule must fire for any
possible network value. For example, if numBits==3, and we want to allow access to
networks 0, 2, 3, 6, and 7, you could use the following rules:
3, 1, deny
6, 4, deny
7, 7, allow
To encourage code that generates both fast and short solutions, the ranking will be
based on minimizing the following function of execution time on my 8500/150 and the
number of rules generated:
score = (number of rules generated) + (execution time in seconds) / 2
This will be a native PowerPC Challenge, using the latest CodeWarrior
environment. Solutions may be coded in C, C++, or Pascal.
Two Months Ago Winner
Congratulations to Xan Gregg (Durham, N.C.), for submitting the fastest entry to
the ByteCode Interpreter Programmer’s Challenge, narrowly beating out the
second-place entry by Ernst Munter. The Challenge was to write an interpreter for a
subset of the byte code language implemented by the Java Virtual Machine. The
Challenge rules pointed to the Java Virtual Machine Specification for a description of
the opcodes, with some exclusions about the opcodes and features that were to be
implemented, and with the significant simplifying assumption that the Virtual Machine
need only deal with a single class file. Of the five solutions submitted, three worked
correctly for all test cases, one worked for all but one test case, and the fifth was
acknowledged by the author to be incomplete.
The rules for September permitted the use of assembly language, and Xan was the
only contestant to submit a solution that took advantage of this. After parsing the
header to identify the constants, fields, and methods contained in the class file, the
solution dispatches and executes each opcode. As described by the comments in the code,
the main execution loop contains a table with 32 bytes of PowerPC instructions
implementing each opcode. Opcodes that require more code than will fit into the table
entry overflow to code outside the table. Particular features that you might want to
examine in the code include the implementation of the jump table and the
pseudo-opcode ExitCode used to trigger a return to the calling routine. Congratulations
to Xan on an elegant, efficient, and instructive solution. Several readers commented
that they learned quite a bit about Java from implementing a Virtual Machine.
Congratulations as well to everyone who participated in this more difficult than usual
Challenge!
The table below summarizes the results for each entry, including execution time
in milliseconds, code size, and data size. An asterisk indicates a test case that was not
successfully completed by a solution. Numbers in parenthesis after a person’s name
indicate that person’s cumulative point total for all previous Challenges, not including
this one.
Name Lanugage Test1 Test2 Test3 Test4 Time Code Data
Xan Gregg (92) C/Assembly 31088 12923 24607 45190 113808 10064 171
Ernst Munter (214) C++ 18661 14664 28260 52496 114081 6260 879
Turlough O’Connor C++ 23073 15946 30503 57444 126967 14536 5818
Conor MacNeill C++ 44446 * 43298 84020 * 82536 10909
The test code was contained in standard Java applets, which allowed me to use the
interpreters supplied with the Symantec and Metrowerks environments to confirm
expected results. This also allowed a comparison of the execution time of the mini
Virtual Machines submitted as solutions with the execution time of the commercial
interpreters. Results for the same four test cases used to score the solutions are
presented below for the Applet Viewer provided with Symantec Cafe (version 1.0) and
for the Metrowerks Java interpreter provided with CodeWarrior 9. While the
comparison is not entirely fair because of the simplifying assumptions used in this
Challenge, the table indicates that three of the four solutions were faster than both of