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.

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:

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".