ANSWERS TO X-TOY EXERCISES
1.
R[1] R[2] R[3]
--------------------
(a) 10: 7211 R[2] <- 11 0011
11: 7110 R[1] <- 10 0010
12: 2321 R[3] <- R[2] - R[1] 0001
13: 0000
(b) 10: 8211 R[2] <- mem[11] 8110
11: 8110 R[1] <- mem[10] 8211
12: 2312 R[3] <- R[1] - R[2] 0101
13: 0000
(c) 10: 7211 R[2] <- 11 0011
11: A120 R[1] <- mem[R[2]] A120
12: 2312 R[3] <- R[1] - R[2] A10F
13: 0000
2. 10: 7101 R[1] <- 1
11: 7207 R[2] <- 7
12: 7301 R[3] <- 1
13: 1333 R[3] <- R[3] + R[3]
14: 2221 R[2]--
15: D213 if (R[2] > 0) goto 13
16: 0000
This program loops 7 times. At each iteration the value of register
3 doubles. Upon termination R[2] = 2^7 = 0080.
3. Here's one possibility.
10: 81FF read R[1] a
11: 82FF read R[2] b
12: 83FF read R[3] c
13: 1A10 R[A] <- R[1] a
14: 1B30 R[B] <- R[3] c
15: FF30 R[F] <- pc; goto 30 ac via function
16: 1AC0 R[A] <- R[C] ac
17: 7B04 R[B] <- 0004 4
18: FF30 R[F] <- pc; goto 30 4ac via function
19: 13C0 R[3] <- R[C] 4ac
1A: 1A10 R[A] <- R[2] b
1B: 1B30 R[B] <- R[2] b
1C: FF30 R[F] <- pc; goto 30 b^2 via function
1D: 23C3 R[3] <- R[C] - R[3] b^2 - 4ac
1E: 0000 halt
4. A complete program that uses this function appears in the Visual
X-TOY simulator as example program gcd.toy.
30: CB38 if (R[B] == 0) goto 38 while (b != 0) {
31: 2DAB R[D] <- R[A] - R[B] if (b >= a) {
32: DD36 if (R[D] > 0) goto 36 // swap and b
33: 1DA0 R[D] <- R[A] temp = a;
34: 1AB0 R[A] <- R[B] a = b;
35: 1BD0 R[B] <- R[D] b = temp;
}
36: 2AAB R[A] <- R[A] - R[B] a -= b;
37: C030 goto 30 }
38: 1CA0 R[C] <- R[A] c = a;
39: EF00 goto R[F] return c;
5. This classic solution exploits the XOR instruction.
R[A] R[B]
---------------------------------
10: 8AFF read R[A] a
11: 8BFF read R[B] b
*12: 4AAB R[A] <- R[A] ^ R[B] a ^ b
*13: 4BBA R[B] <- R[B] ^ R[A] b ^ (a ^ b) = a
*14: 4AAB R[A] <- R[A] ^ R[B] (a ^ b) ^ a = b
15: 9AFF write R[A]
16: 9BFF write R[B]
17: 0000 halt
6. Need 11 bits to address the 2^11 = 2048 words instead of 8 to address
the 2^8 = 256 words. So, "load" and "store" instructions (for example)
have to be redesigned, since they need 4 bits for the opcode, 4 bits
for the destination register, and 11 bits for the address, 3 bits too
many to fit into a 16-bit word.