assemblyknuthtaocp

How do the operations LDA, STA, SUB, ADD, MUL and DIV work in Knuth's machine language MIX?

I have been reading the Art of Computer Programming by Donald Knuth Volume 1. Now I finished the first part where all the mathematics were explained and it was quite a pleasure. Unfortunately, on p. 121 he starts explaining this fictional machine language called MIX based on real machine languages in which he will subsequently explain all the algorithms and Mr. Knuth is losing me completely.

I hope there is someone here that 'speaks' a bit of MIX and can help me understand it. Specifically, he lost me where he starts explaining different operations and showing examples (p. 125 onward).

Knuth uses this "instruction format" with the following form:

Picture 1

He also explains what the different bytes mean:

Picture 2

So the right byte is the operation to be performed (e.g., LDA "load register A"). F byte is a modification of the operation code with field specification (L:R) with 8L + R (e.g., C=8 and F=11 yields "load A register with the (1:3) field). Then +/- AA is the address and I the index specification to modify an address.

Well this makes some sort of sense to me. But then Knuth comes with some examples. The first I do understand except for a few bits, but I cannot wrap my head around the last three of the second example and nothing at all from the more difficult operations in example 3 below.

Here is the first example:

Picture 3

LDA 2000 just loads the full word and we see it completely in register A rA. The second one LDA 2000(1:5) loads everything from the second bit (index 1 ) till the end (index 5) and that is why everything except the plus sign is loaded. And the third with LDA 2000(3:5) just loads everything from the third byte till the last. Also LDA 2000(0:3) (fourth example) kind of makes sense. -803 should be copied and the - is taken and the 80 and 3 are placed at the end.

So far so good, in number5, if we follow the same logic, LDA2000(4:4) it only transferring the fourth byte. Which it indeed did to the last position. But then, in LDA 2000(1:1) only the first byte (the sign) should be copied. This is weird. Why is the first value a + instead of a - (I expected only the - to be copied). and why are the other values all 0 and the last a question mark?

Then he gives the second example with the operation STA (store A):

Picture 4

Again, STA 2000, STA 2000(1:5) and STA 2000(5:5) make sense with the same logic. However, then Knuth does STA 2000(2:2). You would expect to have the second byte copied which equals 7 in register A. However somehow someway we end up with - 1 0 3 4 5. I have been looking at these for hours and have no clue how this, or the two example that follow this one (STA 2000(2:3) and STA 2000(0:1)) can result in the contents of the location as displayed.

I hope someone here can shine his light on these last three.

Furthermore, I also have big trouble with the page where he explains the operations ADD, SUB, MUL, and DIV. The third example, see

Picture 5

This third example is my final goal to understand and right now it makes absolutely zero sense at all. This is very frustrating since I do want to continue with his algorithms but if I don't understand MIX I will not be able to understand the rest!

I hope someone out here has had a course on MIX or sees something that I do not see and is willing to share his or her knowledge and insights!

Solution

  • The design is a child of the 1960s, back when bytes had 6 bits and decimal computing was common. Machines had to compete with 10 digit calculators. It must be emphasized that this is a fictional architecture, actually implementing it will be difficult since a byte doesn't have a fixed size. MIX can work in binary where a byte stores 6 bits, you'd get the equivalent of a 31-bit machine: 1 bit for the sign and 5 x 6 bits for the bytes makes up a word. Or can work in decimal where one byte stores two digits (0..99). That doesn't fit in 6 bits (0..63), emphasizing the fictional part of the design.

    It does share another common characteristic of machines back then, memory is only word addressable. Or in other words, you could not address a single byte like you can on all modern processors. So a trick is needed to lift byte values out of a word, that's what the (first:last) modifier does.

    Number the parts of the word from 0 to 5, left to right. 0 is the sign bit, 1 is the MSB (most significant byte), 5 is the LSB (least significant byte). The most important detail is that you have to shift the bytes, the last addressed byte in (first:last) becomes the LSB in the destination.

    So the simple ones to understand are LDA 2000(0:5), copies everything, LDA 2000(1:5), copies everything except the sign bit, LDA 2000(3:5) copies 3 bytes without any shifting since the LSB is copied. As long as last is 5 then nothing particularly special happens.

    LDA 2000(0:0) is easy to understand as well, it only copies the sign bit, none of the bytes.

    LDA 2000(0:3) is where the trouble starts. A picture might help:

    +---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+
  |
  v
+---+---+---+---+---+---+
| 0 | x | x | 1 | 2 | 3 |
+---+---+---+---+---+---+

    (0:3) moves the sign bit and bytes #1 through #3. Note how byte #3 becomes the least significant byte in the destination word. It is this shift that probably causes confusion.

    Perhaps LDA 2000(4:4) becomes clear now as well. Only a single byte is copied, it becomes the LSB in the destination. Same recipe for LDA 2000(1:1), now moving byte #1 to byte #5.