September 1998 Programmer's Challenge

Big Baby

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Tuesday, 1 September 1998

Fifty years ago this past June, the Manchester Mark I prototype computer, also known as "Baby", became operational. Baby was the first computer to store a program electronically, and was also the first computer to store instructions and data in the same memory. Because vacuum tube technology was too immature to store memory reliably, Baby was designed to test memory based on a cathode ray tube. Not much memory, mind you. Baby boasted a full 1K bits of memory, organized as 32 words (or lines) of 32 bits each.

In celebration of the birth of the first stored program computer on June 21, 1948, the Department of Computer Science at the University of Manchester recently reconstructed Baby and ran a programming contest to write the most imaginative program for Baby. Inspired by that contest, your Challenge is to write an assembler and an emulator for an extended ("Big") version of Baby. The prototype for the code you should write is:

#if defined(__cplusplus) extern "C" { #endif #define kMaxInstructions 32 /* may be as large as 1024 in actual test */ typedef UInt32 CRT_memory[kMaxInstructions]; pascal void AssembleBabyProgram( char *program, CRT_memory memory, UInt32 address_bits ); pascal void ExecuteBabyProgram( CRT_memory memory, UInt32 address_bits ); #if defined(__cplusplus) } #endif

Baby has a single general-purpose register, called the Accumulator. The program counter is called the Control Instruction, or CI. The CI is incremented just before the next instruction is fetched, which means that a jump instruction, for example, is coded with a value one less than the actual target address. Baby also has a red light that indicates the program has halted. One interesting thing about Baby is that it lacks an addition instruction — addition is done by subtraction.

Baby’s instruction repertoire is listed below. The function bits (or opcode) associated with each instruction is listed in parentheses after the mnemonic.

Mnemonic Op code (binary) Semantics
STO 110 Store the contents of the Accumulator in the store line.
SUB 001 or 101 Subtract the contents of the store line from the Accumulator. There is no ADD instruction; addition is done indirectly by combining the SUB and the LDN instruction.
LDN 010 Copy the contents of the store line, negated, to the accumulator.
JMP 000 Copy the contents of the store line to the CI (so the store line holds the number of the line one before we want to jump to). In modern terms, this an indirect jump, which uses up an extra store line compared to a direct jump.
JRP 100 Add the contents of the store line to the CI. This looks forward to larger machines, where it would be important to be able to load the same code in different places, and hence would need relative jumps.
CMP 011 Skip the next instruction if the contents of the Accumulator are negative, i.e. a conditional branch.
STP 111 Stop the machine and turn the red light on.
NUM N/A An assembler mnemonic to initialize a store line to a data value.

For example, the following program computes the greatest common divisor of the number in locations 30 and 31:

22 0000 NUM 0 0001 LDN 30 0002 STO 29 0003 LDN 31 0004 STO 31 0005 LDN 31 0006 STO 30 0007 LDN 29 0008 SUB 30 0009 CMP 0010 JRP 27 0011 SUB 31 0012 STO 31 0013 SUB 28 0014 CMP 0015 JMP 00 0016 STP 0027 NUM -3 0028 NUM 2 0029 NUM 0 0030 NUM 3141593 0031 NUM 521

Baby’s instructions are assembled into a 32 bit word by placing the function code associated with the mnemonic into bits 13..15 (numbered with bit 0 as the most significant bit). In the original Baby, the store line associated with the instruction is placed in bits 0..4. Bits 5..12 and 16..31 are not used as part of the instruction, although they can be used as data. The program listed above assembles to the following:

0022 0000:00000000000000000000000000000000 0001:01111000000000100000000000000000 0002:10111000000001100000000000000000 0003:11111000000000100000000000000000 0004:11111000000001100000000000000000 0005:11111000000000100000000000000000 0006:01111000000001100000000000000000 0007:10111000000000100000000000000000 0008:01111000000000010000000000000000 0009:00000000000000110000000000000000 0010:11011000000001000000000000000000 0011:11111000000000010000000000000000 0012:11111000000001100000000000000000 0013:00111000000000010000000000000000 0014:00000000000000110000000000000000 0015:00000000000000000000000000000000 0016:00000000000001110000000000000000 0027:10111111111111111111111111111111 0028:01000000000000000000000000000000 0029:00000000000000000000000000000000 0030:10011011111101111111010000000000 0031:01111010001010000000000000000000

Our contest will make one change to the original Baby: in our extended, Big Baby, machine, the store line is extended from 5 bits (0..4) to address_bits bits (0..address_bits-1). This allows more than 32 words of memory and therefore larger programs.

Your AssembleBabyProgram routine should accept the mnemonic input listed above, pointed to by the program parameter, and assemble them into 32-bit Baby instructions in memory. Your ExecuteBabyProgram routine will be called to execute the program one or more times. Both of your routines will be provided an address_bits parameter that describes the size of memory. You will be asked to assemble more than one program, your assembled programs may be executed more than one time each, and you may be asked to execute a program that has been hand-assembled.

More information about the University of Manchester Baby programming contest can be found at:

<http://www.cs.man.ac.uk/prog98/>

Programming reference documentation for Baby can be found at:
<http://www.cs.man.ac.uk/prog98/ssemref.html> , and at
<ftp://ftp.cs.man.ac.uk/pub/CCS-Archive/misc/progref1.doc>
.

The winner will be the solution that assembles and executes a set of test programs in the minimum amount of time.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, Pascal or, as is our tradition in the month of September, in assembly language. Thanks to Eric Shapiro for suggesting this Challenge.


Test code for this Challenge is now available.


You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".