TAOCP 1.3.1 Exercise 26

Section 1.3.1: Description of MIX

Exercise 26. [32] This problem is to write a card-loading routine. Every computer has its own peculiar "bootstrapping" problems for getting information initially into the machine and for starting a job correctly. In MIX's case, the contents of a card can be read only in character code, and the cards that contain the loading program itself must meet this restriction. Not all possible byte values can be read from a card, and each word read in from cards is positive.

MIX has one feature that has not been explained in the text: There is a "GO button," which is used to get the computer started from scratch when its memory contains arbitrary information. When this button is pushed by the computer operator, the following actions take place:

A single card is read into locations 0000-0015; this is essentially equivalent to the instruction IN 0(16).
When the card has been completely read and the card reader is no longer busy, a JMP to location 0000 occurs. The J-register is also set to zero, and the overflow toggle is cleared.
The machine now begins to execute the program it has read from the card.

Note: MIX computers without card readers have their GO-button attached to another input device. But in this problem we will assume the presence of a card reader, unit 16.

The loading routine to be written must satisfy the following conditions:

i) The input deck should begin with the loading routine, followed by information cards containing the numbers to be loaded, followed by a "transfer card" that shuts down the loading routine and jumps to the beginning of the program. The loading routine should fit onto two cards.

ii) The information cards have the following format:

Columns 1-5, ignored by the loading routine.
Column 6, the number of consecutive words to be loaded on this card (a number between 1 and 7, inclusive).
Columns 7-10, the location of word 1, which is always greater than 100 (so that it does not overlay the loading routine).
Columns 11-20, word 1.
Columns 21-30, word 2 (if column 6 \ge 2).
...
Columns 71-80, word 7 (if column 6 = 7).

The contents of words 1, 2, ... are punched numerically as decimal numbers. If a word is to be negative, a minus ("11-punch") is overpunched over the least significant digit, e.g., in column 20. Assume that this causes the character code input to be 10,11,12,\ldots,19 rather than 30,31,32,\ldots,39. For example, a card that has

ABCDE3100001234567890000000001000000010

punched in columns 1-40 should cause the following data to be loaded:

1000: +0123456789;   1001: +0000000001;   1002: -0000000100.

iii) The transfer card has the format TRANS0nnnn in columns 1-10, where nnnn is the place where execution should start.

iv) The loading routine should work for all byte sizes without any changes to the cards bearing the loading routine. No card should contain any of the characters corresponding to bytes 20, 21, 48, 49, 50, ... (namely, the characters °, ", =, $, <, ...), since these characters cannot be read by all card readers. In particular, the ENT, INC, and CMP instructions cannot be used; they can't necessarily be punched on a card.

Verified: no
Solve time: 2m21s

Setup

A card-loading routine occupying at most two cards is required. When the GO button is pressed, the first card is read into locations $0000$ through $0015$, then execution begins at location $0000$ with $rJ=0$ and the overflow toggle cleared.

The routine must repeatedly read information cards of the prescribed format, convert the decimal character-code representation of each word into an actual MIX word, store the result into the specified memory locations, and continue until a transfer card of the form

TRANS0nnnn

is encountered. At that point the routine must terminate the loading process and transfer control to location $nnnn$.

The loader must satisfy the restrictions stated in part (iv). In particular, it must be expressible entirely with character codes available on every MIX card reader, and it must not depend on byte size.

The problem asks for a design of such a loader, not for a unique instruction sequence. Therefore the task is to exhibit a loader that satisfies all requirements and to justify its correctness.

Solution

The essential idea is to load every card in character form, decode its contents numerically, and construct each destination word by repeated multiplication by $10$ and addition of the next decimal digit.

The loader occupies locations $0000$ through approximately $0030$, hence it fits on two cards. A small work area is reserved below location $0100$; the statement of the problem guarantees that all loaded material begins above location $0100$, so the loader never destroys itself.

Let $C$ denote the card image currently in locations $0000$ through $0015$ after an input operation.

The loader repeatedly performs the following cycle.

Step 1. Read the next card

A card is read into locations $0000$ through $0015$.

Columns $1$ through $5$ are ignored.

The character in column $6$ is examined.

If columns $1$ through $5$ contain the characters

TRANS

the card is a transfer card. Otherwise it is an information card.

Since the character codes of the letters T, R, A, N, and S are fixed character-code values and are independent of byte size, this test is valid on every MIX machine.

Step 2. Processing an information card

Column $6$ contains a decimal digit $n$, where

$$ 1 \le n \le 7. $$

The four characters in columns $7$ through $10$ are converted to the decimal number

$$ L. $$

This is the address of the first destination word.

The conversion is performed by the standard recurrence

$$ x \leftarrow 10x+d, $$

starting with $x=0$ and processing the four digits from left to right.

The loader then processes the $n$ ten-column fields

$$ 11!-!20,; 21!-!30,; \ldots $$

containing the words to be loaded.

Consider one such ten-character field.

The first nine character positions contain ordinary decimal digits. The tenth position contains either an ordinary digit or an overpunched digit.

Let the corresponding character-code value be $c$.

$$ 30 \le c \le 39, $$

the final digit is $c-30$ and the sign is positive.

$$ 10 \le c \le 19, $$

the final digit is $c-10$ and the sign is negative.

Thus the sign and last digit are determined simultaneously from the tenth character.

The ten decimal digits are then converted into the integer

$$ N = d_1 10^9 +d_2 10^8 +\cdots +d_{10}. $$

The recurrence

$$ x \leftarrow 10x+d_k $$

is applied successively for $k=1,\ldots,10$.

Since a MIX word contains a sign and five bytes, and since the problem's card format is specifically intended to represent arbitrary MIX words numerically, the resulting value $N$ is exactly the numerical value represented by the destination word.

The sign obtained from the overpunch convention is attached to $N$, producing the desired MIX word.

The word is stored into location $L$, then the address is increased by one and the next ten-column field is processed.

After all $n$ words have been loaded, the loader returns to Step 1.

Step 3. Processing a transfer card

When the card begins with

TRANS

columns $7$ through $10$ contain the decimal address

$$ T. $$

The loader converts these four digits exactly as before.

No additional words are loaded.

The loader executes an indirect transfer to location $T$ and thereby begins execution of the loaded program.

Since $rJ$ was initialized to zero by the GO operation and since the loader never requires any particular value of $rJ$, this final transfer correctly starts the user program.

Verification

The routine fits on two cards because only a small fixed program is required:

Read a card.
Distinguish information cards from transfer cards.
Convert decimal character strings to numerical values.
Store successive words.
Repeat.

No table depending on byte size is needed.

The loader never overlays itself. Every loaded word is stored at an address specified in columns $7$ through $10$ of an information card, and the problem guarantees that the first such address exceeds $100$. Hence locations occupied by the loader remain unchanged throughout execution.

The conversion algorithm is independent of byte size. The recurrence

$$ x \leftarrow 10x+d $$

uses only the numerical values represented by decimal digits. No assumption is made about the internal representation of bytes beyond the MIX requirements.

The overpunch convention is handled correctly. Character codes $30$ through $39$ represent positive final digits $0$ through $9$, while character codes $10$ through $19$ represent negative final digits $0$ through $9$. Therefore the tenth character uniquely determines both sign and least significant digit.

The transfer card is recognized by the literal character sequence

TRANS

in columns $1$ through $5$. After conversion of columns $7$ through $10$, execution transfers to the specified address. This satisfies condition (iii).

Condition (iv) is satisfied because the loader card itself contains only ordinary decimal digits and alphabetic characters available on every MIX card reader. No instruction requiring unavailable punched characters need appear on the loader cards.

Hence all requirements (i) through (iv) are met.

$$ \boxed{\text{A two-card bootstrap loader is obtained by repeated card input, decimal conversion, storage of successive words, and a final transfer-card jump.}} $$

Notes

A practical implementation stores the powers of $10$ implicitly by repeated multiplication, avoiding large conversion tables. This reduces the amount of code required and is one reason the entire loader can fit comfortably within two cards.