PROCEDURAL PROGRAMMING LAB 1

Crypt implements a simple Bit Xor cipher. This produces rather garbled
output and looks quite secure, however it is soon discovered that is
isn't. Two different ways of cracking the cipher are presented in this
report; one using a crib (a section of the original message already
known) and another that can crack messages of about three lines or
greater with no knowledge of the key or original message.

The cipher works using a key, which is bit-Xored with each successive
letter of the message. Since the key is usually substatially shorter
than the message, when the end of the key is reached it 'repeats'. This
is shown here:

Dear santa, please bring ...
@@@@@@@@@@@@@@@@@@@@@@@@ ...
RUDOLFRUDOLFRUDOLFRUDOLF ...
======================== ...
0%=l3;0.`f"9!.?#r76&"!r8 ...

As you can see, the output comes out as gobbledegook (at least, from a
human perspective).

One of the features of this crypt method is that it is self-reversible
(this doesn't make it technically easier to crack, but it saves on code
writing somewhat). This is because of the commutability and associativity
of the Bit Xor operator. In other words:

Xor(Xor(a, b), b) = a

Xor is often available as a primitive (in this program, the Bit.Xor(a, b)
function is imported and use that performs the required function. If it
were not available, some alternative implementations of it are:

NOT (a == b) 
  (where == works on each individual bit, and Not inverts the bits)
(a != b)
  (similar to the above, but technically doesn't use not :-))
ADD (a, SUB(b, NAND(a, b)))
  (where ADD adds its two arguments, SUB subtracts the second from the
  first, and NAND does a bitwise NAND comparison (useful, I guess, for
  implementations based on NAND gates with some sort of full adder. This
  particular one works by preventing carrying, since the subtraction of
  the NAND removes any cases where both bits are high)


MODULE Crypt;

IMPORT Args, Files, Out, Err, Strings, Bit;

CONST
  MaxText = 2048;
  MaxKey = 64;

VAR
  i, N, K: INTEGER;
  text: ARRAY MaxText OF CHAR;
  key, fname: ARRAY MaxKey OF CHAR;
  in: Files.File;

BEGIN
  IF Args.argc < 2 THEN
    Err.String("Usage: crypt key [file]"); Err.Ln;
    HALT(2)
  END;

  (* key is argument 1, K is its length *)
  Args.GetArg(1, key);
  K := Strings.Length(key);

  (* if no file is specified, use stdin; otherwise open the input file *)
  IF Args.argc <= 2 THEN
    in := Files.stdin
  ELSE
    Args.GetArg(2, fname);
    in := Files.Open(fname, "r");
    IF in = NIL THEN
      Err.String("crypt: can't read "); Err.String(fname); Err.Ln;
      HALT(1)
    END
  END;

  (* Input the text; N is its length *)
  N := 0;
  WHILE (N < MaxText) & ~Files.Eof(in) DO
    Files.ReadChar(in, text[N]);
    N := N + 1
  END;

  (* code to crypt the message here. Bit Xors each char with each char of
     the key, and when he end of the key is reached, starts again
     (accomplished by using MOD) *)
  i := 0;
  WHILE i < N DO
    text[i] := CHR(Bit.Xor(ORD(text[i]), ORD(key[i MOD K])));
    i := i + 1
  END;

  (* Write the text on standard output *)
  i := 0;
  WHILE i < N DO
    Out.Char(text[i]);
    i := i + 1
  END
END Crypt.

Next module finds the key, given any section of the original message. For
example, if a file "santa" contains:

Dear Santa, please bring me a new bike for Christmas, love John

and the key is RUDOLF, one could call crib with any of these arguments:

crypt RUDOLF santa | crib Christmas
crypt RUDOLF santa | crib 'a new bike'
crypt RUDOLF santa | crib 'ing me a'

and the key "RUDOLF" would be returned (the pipe indicates that the output
from crypt is being fed in as the last argument of crib).

Note, that due to the (quite necessary) implementation of the crib algorithm,
the crib used must be at least two characters longer than the key being broken
(so with a key of length six, the crib must be at least eight in length). If it
isn't, an error message is returned.

The actual implementation makes use of the same functional code as the crypt
algorithm. This is since one can notice that if part of the original message is
Xored with the correct (lined-up) characters in the original, then the key is
printed on those characters:

Dear Santa, please bring me a new bike for Christmas, love John
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
ristmasChristmasChristmasChristmasChristmasChristmasChristmasCh
===============================================================
dYVIt@xX\          VT@]|K^ERO@{IDH]RmGKY]NUUDOLFRUDO#LSA^’¨¦N�·B[
                                           ^^^^^^^^^

Notice how the key has appeared in the space. Where the key starts and ends can
be determined using how far along the file it is, and noticing where it repeats
(thus the requirement for the crib to be greater than the crypt key, two greater
seems to work fine).

MODULE Crib;

IMPORT Args, Files, Out, Err, Strings, Bit;

CONST
  MaxText = 2048;
  MaxKey = 64;

VAR
  i, N, K, s, j: INTEGER;

  (* i is a loop counter. where it stops is used to determine where the (garbled)
     key segment is in the garbled 'decrypted' message
     letter of the key
     N is the length of the input (encrypted) text
     K is the length of the input crib
     s is another loop counter for the outside loop that shifts the crib along the
     encrypted text. It's also used to determine the first letter of the key given
     the garbled key (example, if key is RUDOLF garbled key might be "UDOLFRUD").
     j is another loop counter, which is also used to determine the length of the
     key *)

  found: BOOLEAN; (* becomes true when the garbled key is found *)
  text: ARRAY MaxText OF CHAR;
  key, crib, fname: ARRAY MaxKey OF CHAR;
  in: Files.File;

BEGIN
  IF Args.argc < 2 THEN
    Err.String("Usage: crib.exe [crib] [file]"); Err.Ln;
    HALT(2)
  END;

  (* crib is argument 1, K is its length *)
  Args.GetArg(1, crib);
  K := Strings.Length(crib);

  (* if no file is specified, use stdin; otherwise open the input file *)
  IF Args.argc <= 2 THEN
    in := Files.stdin
  ELSE
    Args.GetArg(2, fname);
    in := Files.Open(fname, "r");
    IF in = NIL THEN
      Err.String("crib: can't read "); Err.String(fname); Err.Ln;
      HALT(1)
    END
  END;

  (* Input the text; N is its length *)
  N := 0;
  WHILE (N < MaxText) & ~Files.Eof(in) DO
    Files.ReadChar(in, text[N]);
    N := N + 1
  END;

  s := 0;
  found := FALSE; (* initialisation *)
  WHILE (s <= N - K) & ~found DO
  (* the second part of the guard exits the loop on success, the second part exits
     the loop in case of failure (having checked the entire length of the garbled
     message *)
    i := 0;
    WHILE i < K DO
    (* loop Xors a section of the message against the given crib *)
      key[i] := CHR(Bit.Xor(ORD(text[s + i]), ORD(crib[i])));
      i := i + 1
    END;

    j := 1;
    s := s + 1;
    WHILE (j < K) & ~found DO
    (* loop checks for repeats in key[] *)
      j := j + 1;
      found := (key[0] = key[j]) & (key[1] = key[j + 1])
      (* found become true if the first and second characters match j and j + 1
         where j is the loop counter *)
    END
  END;

  IF ~found THEN Out.String("Did not determine key"); Out.Ln
  (* if the first part of the guard was what terminated the loop, error *)
  ELSE
    (* Write the text on standard output *)
    i := 0;
    WHILE i < j DO
    (* the clever bit. i is where in the string the garbled key was found, and
       1 - s is how far in thing started to repeat. This ungarbles the key before
       outputting it *)
      Out.Char(key[(i - s + 1) MOD j]);
      i := i + 1
    END;
  END
END Crib.

Crack1 is quite simple. It checks for characters that are the same, and s chars
away from each other. With any decent sized (3,4 lines or more) message, there are
spaces (and possibly other characters) which are a multiple of the key length away
from each other. Since they will line up with the key, they will be encrypted to
the same character. This program exploits that, checking for similar characters
and recording the distance they are away from each other. Since for multiples of
the key there will be many more matches, the user can determine a likely length of
the key. Note that if the key is actually of length six, this program will
probably produce large numbers of matches for 6, 12, 18 etc. In this case, it is
completely safe to use the largest one, since the second crack program will just
return the key repeated 1, 2, 3 etc. times respectively. Due to the nature of the
encrypting algorithm, this can even be used with the crypt program to still give
correct decryption.

MODULE Crack1;

IMPORT Args, Files, Out, Err;

CONST
  MaxText = 2048;
  MaxKey = 64;
  MaxShift = 30;

VAR
  i, N, s, matches: INTEGER;
  text: ARRAY MaxText OF CHAR;
  fname: ARRAY MaxKey OF CHAR;
  in: Files.File;

BEGIN
  (* if no file is specified, use stdin; otherwise open the input file *)
  IF Args.argc <= 1 THEN
    in := Files.stdin
  ELSE
    Args.GetArg(1, fname);
    in := Files.Open(fname, "r");
    IF in = NIL THEN
      Err.String("crack1: can't read "); Err.String(fname); Err.Ln;
      HALT(1)
    END
  END;

  (* Input the text; N is its length *)
  N := 0;
  WHILE (N < MaxText) & ~Files.Eof(in) DO
    Files.ReadChar(in, text[N]);
    N := N + 1
  END;

  s := 0;
  WHILE s < MaxShift DO
    s := s + 1;
    matches := 0;
    i := 0;
    WHILE i <= N - MaxShift DO
      IF text[i] = text[i + s] THEN matches := matches + 1 END;
      (* self explanatory: if two bits of text are the same character and shifted
         by length s, this loop catches it for that particular value of s *)
      i := i + 1
    END;
    Out.Int(s,0); Out.String(": "); Out.Int(matches,0); Out.Ln
    (* this time it's more convenient to output as we go along *)
  END

END Crack1.

The second crack program takes an encrypted file and an integer guess of the
length of the key, and returns a whole list of junk, from which the required key
can easily be filtered. It works by continuing the exploit of key length shifts,
although this time since we thnk we know the length we can exploit it properly.
The program as before matches characters with one shifted multiples of length K
along, but this time it assumes that if such a repetition occurs, that both
encoded characters were originally spaces. This turns out to be quite likely.
How the key is got from this is shown in the section after this code, containing
typical outputs from all of the programs in this part of the report.

MODULE Crack2;

IMPORT Args, Files, Out, Err, Bit, Conv;

CONST
  MaxText = 2048;
  MaxKey = 64;

VAR
  i, N, K, s, keypart: INTEGER;
  text: ARRAY MaxText OF CHAR;
  key, fname: ARRAY MaxKey OF CHAR;
  in: Files.File;

BEGIN
  IF Args.argc < 2 THEN
    Err.String("Usage: crack2 keylength [file]"); Err.Ln;
    HALT(2)
  END;

  (* key is argument 1, K is its length *)
  Args.GetArg(1, key);
  K := Conv.IntVal(key);

  (* if no file is specified, use stdin; otherwise open the input file *)
  IF Args.argc <= 2 THEN
    in := Files.stdin
  ELSE
    Args.GetArg(2, fname);
    in := Files.Open(fname, "r");
    IF in = NIL THEN
      Err.String("crack2: can't read "); Err.String(fname); Err.Ln;
      HALT(1)
    END
  END;

  (* Input the text; N is its length *)
  N := 0;
  WHILE (N < MaxText) & ~Files.Eof(in) DO
    Files.ReadChar(in, text[N]);
    N := N + 1
  END;

  s := K;
  WHILE s < N DO
  (* we're going to repeat this for multiples of K, i.e. K, 2K, 3K, ... *)
    i := 0;
    WHILE i <= N - K DO
    (* try the shift right the way along the message *)
      IF text[i] = text[i + s] THEN  (* if it matches ... *)
        keypart := Bit.Xor(ORD(" "), ORD(text[i]));
        (* ... assume it was a space, and decode it *)
        IF (keypart > 32) & (keypart <= 127) THEN
        (* get rid of some non-printing characters and junk that get in the way.
           these are very unlikely to be in the key. *)

(*      IF (keypart >= 32) & (keypart <= 127) THEN
   note: temporary fix, since sometimes the output decides there are spaces in
   the key when there aren't. FIXED: REMOVED *)

          Out.Int((i MOD K) + 1,0); Out.String(" "); Out.Char(CHR(keypart));
          Out.Ln
        END;
      END;
    i := i + 1
    END;
    s := s + K
  END

END Crack2.


So, let's try all these programs with some sample output. This is a copy direct
from the shell. The file called "santa" is displayed with cat, then encoded to
file "atnas", which is displayed in the same way. Then a crib is used with the
crib program which is too short, so it fails. I have then tried it with three
valid cribs, which all work. An invalid crib is show lastly.


[root@a178 crypt]# cat santa; echo
Dear Santa, please bring me a new bike for Christmas, love John
[root@a178 crypt]# ./crypt RUDOLF santa > atnas
[root@a178 crypt]# cat atnas; echo
0%=l3;0.`f"9!.?#r76&"!r8!o-f<03o./90d)#4r,=%5&8%<`f>:2*l==*o
[root@a178 crypt]# ./crypt RUDOLF atnas; echo
Dear Santa, please bring me a new bike for Christmas, love John
[root@a178 crypt]# ./crib please atnas; echo; echo this will be too short :-\)
Did not determine key
                                                                                
this will be too short :-)
[root@a178 crypt]# ./crib Christmas atnas; echo
RUDOLF
[root@a178 crypt]# ./crib 'a new bike' atnas; echo
RUDOLF
[root@a178 crypt]# ./crib 'ing me a' atnas; echo
RUDOLF
[root@a178 crypt]# ./crib insidiously atnas; echo
Did not determine key


A longer file is better here, so let's use a boring scientific text. Crack1 returns
the list of possible key lengths, notice 7, 14, 21 (multiples of the key length)
have many more matches. So we give that value to Crack2. Now, this returns a huge
list of matches, so we use some unix commands to sort them by which character of
the key Crack2 thought that letter might be, then count the number of times each
guess occurs, then filter out those with too few letters. By tweaking the

awk '$1 > 7'

one can get the key printed out nicely as shown.


[root@a178 crypt]# cat science; echo
In analysing data from different species such a mouse and human, it is necessary to
describe structures and provide models for structure evolution.  Central examples
of this are protein/RNA secondary structure and genome annotation.  Especially
fruitful examples of this are when sequence evolution is structure dependent, since
observing pure sequence evolution can then be used to predict the unobserved
structure.  At the population level of comparison, a series of new problems have
become central due to recombination and gene conversion.  This leads to a much more
complicated structure representing evolutionary history, but also leads to
difficulties in reconstructing evolution.  On the positive side recombination
increases the possibility of population history, disease gene mapping and provides
challenging problems.
[root@a178 crypt]# ./crypt DETRACT science > ecneics
[root@a178 crypt]# ./crack1 ecneics
1: 31
2: 24
3: 14
4: 23
5: 20
6: 22
7: 58
8: 11
9: 16
10: 22
11: 28
12: 19
13: 17
14: 51
15: 15
16: 25
17: 24
18: 22
19: 22
20: 20
21: 58
22: 21
23: 26
24: 26
25: 26
26: 25
27: 20
28: 66
29: 9
30: 17
[root@a178 crypt]# ./crack2 7 ecneics | sort -n | uniq -c | awk '$1 > 8'
    105 1 D
    190 2 E
    153 3 T
    300 4 R
    136 5 A
     91 6 C
     66 7 T
[root@a178 crypt]# ./crypt DETRACT ecneics; echo
In analysing data from different species such a mouse and human . . .


A few more things. The crib program can be broken by using certain keys, notably
ones that have the same series of characters (one or more) repeated at least three
times. This makes sense given the nature of the crib algorithm. For example:

./crypt APSAPKAP santa | ./crib Christmas

Returns "KAP" as the key. Note that where the S is, any number of characters could
be added rendering this key guess useless.

Another thing to note, is that to protect against this sort of attack, one could
encode a message twice with keys that are co-prime (thus preventing any matchups
giving any sort of information to the cracker). The message can be decrytped at its
rightful place by applying the two keys in any order, again because of the
commutability and associativity of the Xor operation.


PROCEDURAL PROGRAMMING LAB 2


MODULE Planner;

IMPORT In, Out, Err, Conv, Args, Towns, Queue;

VAR verbose: BOOLEAN;		(* Whether to show the algorithm in action *)

VAR
  hflag: BOOLEAN;		(* If true, use the Euclidean heuristic *)
  goal: Towns.town;		(* Goal town (used by heuristic) *)

(* Split -- split a line of text into words *)
PROCEDURE Split(VAR line: ARRAY OF CHAR; 
		VAR words: ARRAY OF Towns.word): INTEGER;
  VAR i, j, n: INTEGER;
BEGIN
  n := 0; i := 0;
  LOOP
    WHILE line[i] = ' ' DO INC(i) END;
    IF line[i] = 0X THEN EXIT END;
    IF line[i] = '{' THEN
      INC(i); j := 0;
      WHILE (line[i] # '}') & (line[i] # 0X) DO
	words[n][j] := line[i];
	INC(i); INC(j)
      END;
      words[n][j] := 0X;
      IF line[i] = '}' THEN INC(i) END
    ELSE
      j := 0;
      WHILE (line[i] # ' ') & (line[i] # 0X) DO
	words[n][j] := line[i];
	INC(i); INC(j)
      END;
      words[n][j] := 0X
    END;
    INC(n)
  END;
  RETURN n
END Split;

(* Now here's our implementation of Dijkstra's algorithm *)

CONST infinity = 1.0E10;	(* Larger than any real distance *)

(* Init -- initialize the search *)
PROCEDURE Init(dst: Towns.town; heur: BOOLEAN);
  VAR i: INTEGER; t: Towns.town;
BEGIN
  FOR i := 0 TO Towns.ntowns-1 DO
    t := Towns.towns[i];
    t.tKnown := FALSE;
    t.tBacklink := NIL;
    t.tDist := infinity
  END; 

  goal := dst;
  hflag := heur;
END Init;

(* Paint -- send command to colour a town *)
PROCEDURE Paint(t: Towns.town; colour: ARRAY OF CHAR);
BEGIN
  IF t # goal THEN
    Out.String("paint {"); Out.String(t.tName); Out.String("} ");
    Out.String(colour); Out.String(" "); Out.Fixed(t.tDist, 0, 1);
    Out.Ln
  END
END Paint;

(* ShowLink -- send command to colour a road *)
PROCEDURE ShowLink(t: Towns.town; colour: ARRAY OF CHAR);
BEGIN
  Out.String("colour {"); Out.String(t.tName); Out.String("} {");
  Out.String(t.tBacklink.tName); Out.String("} ");
  Out.String(colour); Out.Ln
END ShowLink;

(* FindMin -- find unknown town with smallest distance *)
(* REMOVED *)

(* VisitNeighbours -- update distances to neighbours of a town *)
PROCEDURE VisitNeighbours(t: Towns.town);
  VAR r: Towns.road; u: Towns.town; d: REAL;
BEGIN
  r := t.tRoads;
  WHILE r # NIL DO
    u := r.rDest;
    d := t.tDist + r.rLength;

    (* Heuristic: reduce the length of each road by the distance
       it takes us closer to the goal. *)
    IF hflag THEN d := d - Towns.Euclid(t, goal) + Towns.Euclid(u, goal) END;

    IF ~u.tKnown & (d < u.tDist) THEN
      IF verbose & (u.tBacklink # NIL) THEN ShowLink(u, "brown") END;
      IF u.tBacklink = NIL THEN
        Queue.Enqueue(u, d)
      ELSE
        Queue.Requeue(u, d)
      END;
      u.tBacklink := t;
      IF verbose THEN ShowLink(u, "green"); Paint(u, "grey") END;
    END;

    r := r.rNext
  END
END VisitNeighbours;

(* Search -- main search function *)
PROCEDURE Search(VAR sname, dname: Towns.word; heur: BOOLEAN);
  VAR t, src, dst: Towns.town; d: REAL;
BEGIN
  src := Towns.Lookup(sname);
  dst := Towns.Lookup(dname);

  Init(dst, heur);

  src.tDist := 0.0;
  src.tBacklink := src;
  src.tKnown := TRUE;

  Queue.Clear;

  VisitNeighbours(src);
  IF verbose THEN Out.String("pause"); Out.Ln END;

  WHILE ~dst.tKnown DO
    t := Queue.DelMin();
    IF t = NIL THEN
      Out.String("unreachable"); Out.Ln;
      RETURN
    END;
   
    t.tKnown := TRUE;
    IF verbose THEN 
      ShowLink(t, "blue");
      Paint(t, "white")
    END;
    VisitNeighbours(t);
    IF verbose THEN Out.String("pause"); Out.Ln END
  END;

  (* Show the shortest route in yellow *)
  t := dst;
  WHILE t # src DO
    ShowLink(t, "yellow");
    t := t.tBacklink
  END;

  d := dst.tDist;
  IF hflag THEN d := d + Towns.Euclid(src, dst) END;
  Out.String("found "); Out.Fixed(d, 0, 1); Out.Ln
END Search;

(* Main -- main program *)
PROCEDURE Main();
  VAR nwords: INTEGER;
    buf: ARRAY 256 OF CHAR;
    words: ARRAY 10 OF Towns.word;
BEGIN
  verbose := TRUE;
  IF Args.argc > 1 THEN
    Args.GetArg(1, buf);
    IF buf = "-q" THEN verbose := FALSE END
  END;

  LOOP
    In.Line(buf);
    IF ~ In.Done THEN EXIT END;
    nwords := Split(buf, words);

    IF (nwords = 4) & (words[0] = "town") THEN
      Towns.AddTown(words[1], Conv.RealVal(words[2]), Conv.RealVal(words[3]))
    ELSIF (nwords = 4) & (words[0] = "road") THEN
      Towns.AddRoad(words[1], words[2], Conv.RealVal(words[3]))
    ELSIF (nwords = 4) & (words[0] = "search") THEN
      Search(words[1], words[2], (words[3][0] = '1'))
    ELSE
      Err.String("Error: bad command "); Err.String(words[0]); Err.Ln
    END
  END
END Main;

BEGIN
  Main()
END Planner.



MODULE Queue;

IMPORT Towns;

VAR start: Towns.town;

(* Clear -- set the queue to be empty *)
PROCEDURE Clear*;
BEGIN
start := NIL;
END Clear;

(* Enqueue -- add a town to the queue *)
PROCEDURE Enqueue*(t: Towns.town; d: REAL);
BEGIN
  t.tDist := d;
  t.tNext := start;
  IF start = NIL THEN 
    start := t;
    t.tPrev := NIL
  ELSE
    REPEAT
      t.tPrev := t.tNext;
      t.tNext := t.tNext.tNext
    UNTIL (t.tNext = NIL) OR (t.tDist < t.tNext.tDist);
    t.tPrev.tNext := t;
    IF t.tNext # NIL THEN t.tNext.tPrev := t END
  END;
END Enqueue;

(* DelMin -- delete and return the first town in the queue *)
PROCEDURE DelMin*(): Towns.town;
VAR tmp: Towns.town;
BEGIN
  tmp := start;
  IF start # NIL THEN
    start := start.tNext;
    IF start # NIL THEN start.tPrev := NIL END
  END;  (* Try removing the lines in that IF one-by-one to see if it*)
  RETURN tmp;
END DelMin;

(* Requeue -- reduce the distance of a town *)
PROCEDURE Requeue*(t: Towns.town; d: REAL);
BEGIN
  t.tDist := d;
  IF t.tPrev = NIL THEN RETURN END; (* already at the top of the queue *)
  t.tPrev.tNext := t.tNext;
  IF t.tNext # NIL THEN t.tNext.tPrev := t.tPrev END;
  t.tNext := NIL; (* since it's not useful for this bit, setting it is tedious *)
  
  (* t is now removed from the queue, however, its tPrev is still useful *)
  
  WHILE (t.tPrev # NIL) & (t.tDist < t.tPrev.tDist) DO
    t.tPrev := t.tPrev.tPrev
  END;
  IF t.tPrev # NIL THEN
    t.tNext := t.tPrev.tNext;
    t.tPrev.tNext := t;
    IF t.tNext # NIL THEN t.tNext.tPrev := t END
  ELSE
    start.tPrev := t;
    t.tNext := start;
    start := t;
  END;
END Requeue;

PROCEDURE IsEmpty*(): BOOLEAN;
BEGIN
IF start = NIL THEN RETURN TRUE ELSE RETURN FALSE END;
END IsEmpty;

BEGIN
  (* Initialize the queue *)
  IF start # NIL THEN
    REPEAT
      IF start.tPrev # NIL THEN start.tPrev.tNext := NIL END;
      start.tPrev := NIL;
      start := start.tNext
    UNTIL start.tNext = NIL
  END;
END Queue.



Timings using this unix command:

  $ (cat utopia; echo search T1744 T1474 0) | (time ./planner -q >/dev/null)

Time taken to set up the road network:
  user    0m0.580s
Time taken for the original planner program:
  user    0m1.740s (0m1.160s without the road network setup)
Time taken for the improved planner program
  user    0m0.630s (0m0.050s without the road network setup)


Profiling using this unix command:
  $ (cat utopia; echo search T1744 T1474 0) | (obprof ./planner -q >/dev/null)

ORIGINAL PLANNER PROGRAM

Execution profile:
 
     Ticks    Frac     Cumul   Calls   Procedure
 ---------------------------------------------------
  80501762    68.1%    68.1%    1997   Planner.FindMin
  17892180    15.1%    83.3%    2000   Towns.AddTown
   7284618     6.2%    89.5%    7882   Planner.Split
   3812121     3.2%    92.7%   13764   Towns.Find
   3283697     2.8%    95.5%    7883   In.Line
   1806759     1.5%    97.0%  180676   In.Char
    542028     0.5%    97.4%  180676   Files.Eof
    542025     0.5%    97.9%  180675   Files.ReadChar
    521502     0.4%    98.3%  173834   COMPARE
    394796     0.3%    98.7%    1998   Planner.VisitNeighbours
    394027     0.3%    99.0%    5881   Towns.AddRoad
    317628     0.3%    99.3%   11764   Towns.Lookup
    317227     0.3%    99.6%       1   Planner.Main
    170549     0.1%    99.7%    5881   Towns.Euclid
    167977     0.1%    99.8%    9881   Conv.RealVal
     52017     0.0%    99.9%       1   Planner.Init
     44675     0.0%    99.9%       1   Planner.Search
     41286     0.0%   100.0%   13762   NEW
     29643     0.0%   100.0%    9881   Conv.LongRealVal
     17643     0.0%   100.0%    5881   Math.Sqrt
      4015     0.0%   100.0%     313   Out.String
      1872     0.0%   100.0%      52   Planner.ShowLink
       939     0.0%   100.0%     313   Files.WriteString
       265     0.0%   100.0%      53   Out.Ln
       159     0.0%   100.0%      53   Files.WriteLn
        10     0.0%   100.0%       1   Main
         9     0.0%   100.0%       1   Out.Fixed
         7     0.0%   100.0%       1   Files.%main
         5     0.0%   100.0%       1   Args.%main
         4     0.0%   100.0%       1   In.%main
         4     0.0%   100.0%       1   Planner.%main
         3     0.0%   100.0%       1   Args.GetArg
         3     0.0%   100.0%       1   Args.SetArgc
         3     0.0%   100.0%       1   Files.Init
         3     0.0%   100.0%       1   Files.WriteFixed
 
Total of 118141461 clock ticks

IMPROVED PLANNER PROGRAM

Execution profile:
 
     Ticks    Frac     Cumul   Calls   Procedure
 ---------------------------------------------------
  17892180    45.0%    45.0%    2000   Towns.AddTown
   7284618    18.3%    63.3%    7882   Planner.Split
   3812121     9.6%    72.9%   13764   Towns.Find
   3283697     8.3%    81.1%    7883   In.Line
   1996323     5.0%    86.2%    1999   Queue.Enqueue
   1806759     4.5%    90.7%  180676   In.Char
    542028     1.4%    92.1%  180676   Files.Eof
    542025     1.4%    93.4%  180675   Files.ReadChar
    521502     1.3%    94.7%  173834   COMPARE
    406791     1.0%    95.8%    1998   Planner.VisitNeighbours
    394027     1.0%    96.8%    5881   Towns.AddRoad
    317628     0.8%    97.6%   11764   Towns.Lookup
    317227     0.8%    98.3%       1   Planner.Main
    170549     0.4%    98.8%    5881   Towns.Euclid
    167977     0.4%    99.2%    9881   Conv.RealVal
     89938     0.2%    99.4%     500   Queue.Requeue
     52017     0.1%    99.6%       1   Planner.Init
     44677     0.1%    99.7%       1   Planner.Search
     41286     0.1%    99.8%   13762   NEW
     35946     0.1%    99.9%    1997   Queue.DelMin
     29643     0.1%    99.9%    9881   Conv.LongRealVal
     17643     0.0%   100.0%    5881   Math.Sqrt
      4015     0.0%   100.0%     313   Out.String
      1872     0.0%   100.0%      52   Planner.ShowLink
       939     0.0%   100.0%     313   Files.WriteString
       265     0.0%   100.0%      53   Out.Ln
       159     0.0%   100.0%      53   Files.WriteLn
        12     0.0%   100.0%       1   Main
         9     0.0%   100.0%       1   Out.Fixed
         7     0.0%   100.0%       1   Files.%main
         5     0.0%   100.0%       1   Args.%main
         4     0.0%   100.0%       1   In.%main
         4     0.0%   100.0%       1   Planner.%main
         4     0.0%   100.0%       1   Queue.%main
         4     0.0%   100.0%       1   Queue.Clear
         3     0.0%   100.0%       1   Args.GetArg
         3     0.0%   100.0%       1   Args.SetArgc
         3     0.0%   100.0%       1   Files.Init
         3     0.0%   100.0%       1   Files.WriteFixed
 
Total of 39773913 clock ticks

What does all the profiling data mean? Well, we replaced the functionality of
Planner.Findmin with the four Queue functions. Comapring the ticks:

Findmin method:
 80501762 ticks
Queue method:
 21222211 ticks

Questions: the original program is order n^2. The difference between different in
timings for different size towns coroborates this.