5.4. TOY PROGRAMMING

This section under construction.

Although the TOY machine language contains only 16 different instruction types, it is possible to perform a variety of interesting computations. In fact, any computation that can be done in the Java programming language on your PC can also be done in TOY (provided you give TOY enough main memory and time). This may come as quite a surprising fact; we will justify it later in Chapter 8. Below, we describe each of the instructions in the TOY language.

Memory-register transfer. To transfer data between registers and main memory, we use the load (opcode 8) and store (opcode 9) instructions. These operations are convenient because it is not possible to perform arithmetic operations directly on the contents of main memory. Instead, the data must be first transferred to registers. There are many circumstances where it is not possible to maintain all of our program's variables simultaneously in registers, e.g., if we need to store more than 16 quantities. We overcome the 16 register limitation by storing variables in main memory, and transferring them back and forth to registers using the load and store instructions.

Arithmetic operations. The add and subtract instructions (opcodes 1 and 2) perform the conventional arithmetic operations. In TOY, all arithmetic operations involve 16 bit two's complement integers, as described in Appendix XYZ. Program add.toy treats memory addresses 00 and 01 as storing the input values for variables RA and RB. It then calculates the sum of the two values and puts the result temporarily in register C. Finally, it transfers the contents of register C back to memory, and stores it at memory address 02. It is important to note that memory locations 00 through 02 never get executed in this program; they are treated as data.

00: 0005 5 01: 0008 8 10: 8A00 R[A] <- mem[00] 11: 8b01 r[b] <- mem[01] 12: 1cab r[c] <- r[a] + r[b] 13: 9c02 mem[02] <- r[c] 14: 0000 halt

Upon termination of this program, register C contains the value 000D. If you computed the result 13, start getting adjusted to working with hexadecimal integers. What happens if the result of the arithmetic operations is too large to fit into a 16 bit register. Such overflow is handled by disregarding everything except the rightmost 4 hex digits. So, the result of adding EFFF and 1005 is 0004, since EFFF + 1005 = 10004 in hex and we discard the leading digit. This is the way addition works in Java, except that there are 32 bits in an int instead of the 16 in a TOY word.

Analogously, the program subtract.toy computes 0005 - 0008 = FFFD. The answer FFFD is the hexadecimal equivalent of decimal integer -3 using two's complement integers. (Review Section 5.1 for a description of two's complement notation.)

00: 0005 5 01: 0008 8 10: 8A00 R[A] <- mem[00] 11: 8b01 r[b] <- mem[01] 12: 2cab r[c] <- r[a] - r[b] 13: 9c02 mem[02] <- r[c] 14: 0000 halt

Standard input and standard output. The load and store instructions are also used to access standard input and standard output. The distinguished memory address FF is intercepted by a TOY hardware interrupt: instead of loading or storing information in memory location FF, the data is received from the keyboard or is sent to the screen. Program stdin.toy reads two integers from standard input, and writes their sum to standard output.

10: 8AFF read R[A] from stdin 11: 8BFF read R[B] from stdin 12: 1CAB R[C] <- r[a] + r[b] 13: 9cff write r[c] to stdout 14: 0000 halt

When the program is executed, it pauses until the user types in two integers. As usual, the integers are specified as 4 hexadecimal digits. Then it computes their sum, and prints it to the screen. Program fibonacci.toy prints to standard output the sequence of Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, D, etc.

Program sum.toy reads in a sequence of integers from standard input and prints out their sum. It stops upon reading in the integer 0000. It illustrates a program that can process more information than fits in TOY memory.

Implications of standard input and output. The standard input and standard output facilities of TOY have a profound effect on what the TOY machine is capable of. An obvious feature is to get information in and out of the machine. This information can be data, but it can also be instructions! Booting a computer is copying a sequence of stored instructions (e.g., the operating system) into the machine. The TOY machine only has only a limited memory (256 words plus of a few registers). Nevertheless, it is possible to process more information than this. For example, program average.toy reads in an arbitrary sequence of integers (until it encounters 0000) and prints their sum. Another advantage of standard input is that it offers a crude form of user interaction.

Flow control. So far, we have seen how to use TOY as a calculator. Branch statements enable us to harness the true power of TOY, much like while loops and if-else conditionals enabled us to harness the power of Java. The value of the program counter controls which statement the TOY machine will execute next. Typically, the program counter is incremented at each time step, and the instructions are executed in order, one after the other. The branch if zero and branch if positive instructions (opcodes C and D) enable us to directly change the program counter, thereby altering the flow of control of our programs.

Conspicuously absent from the TOY instruction set is a multiply instruction. To achieve the same effect in software, we describe and implement an algorithm to multiply two integers. The brute force way to compute c = a * b is to set c = 0, and then add a to c, b times. This suggests having a loop that repeats b times. We accomplish this by making a counter variable i that we initialize to b, and then decrement it by one until it reaches 0. We use the branch if positive instruction to detect this event. The program multiply.toy loads two integers from memory locations 0A and 0B into registers A and B, multiplies them together and puts the result in register C, then writes the result back to memory location 0C.

0A: 0003 3 0B: 0009 9 0C: 0000 0 0D: 0000 0 0E: 0001 1 10: 8A0A RA <- mem[0a] a 11: 8b0b rb <- mem[0b] b 12: 8c0d rc <- mem[0d] c=0; 13: 810e r1 <- mem[0e] always 1 14: ca18 if (ra== 0) pc goto 18 while (a !=0) { 15: 1ccb rc <- rc + rb c=c + b; 16: 2aa1 ra <- ra - r1 a=a - 1; 17: c014 pc <- 14 } 18: 9c0c mem[0c] <- rc 19: 0000 halt

The astute reader might notice that our algorithm suffers from a serious performance flaw. The brute force algorithm is inefficient if the values are large. The loop iterates b times, and since b is a 16-bit integer, it can be as large as 32,767. This issue would be much more pronounced on a 64-bit machine where the loop might require a mind-boggling 9,223,372,036,854,775,807 iterations! Fortunately, we can incorporate better algorithmic ideas (as we do below) to rescue this otherwise hopeless task.

TOY idioms. There are several common idioms or pseudo-instructions in TOY that can be used for common programming tasks. Many of these tricks rely on the fact that register 0 always stores the value 0000

Register-to-register transfer. Suppose you want to make register 2 have the same value as register 1. There is no built-in instruction to do this. Relying on the fact that register 0 always contains 0000, we can use the addition instruction to sum up R0 and R1 and put the result in R2.
14: 1201 R[2] <- r[1]
No-op. In a structured programming language like Java (with for and while loops), inserting extra code is easy. In an unstructured language like TOY (where there are line numbers and goto statements), you must be careful about inserting code. A branch statement hardwires in the memory address to jump to; if you insert code, the line numbers of your program may change. To avoid some of this awkwardness, machine language programmers often find it convenient to fill in the program with "useless" statements to act as placeholders. Such statements are called no-ops because they perform no operation. The instruction 1000 is ideal for this purpose since register 0 is always 0 anyway. (The instruction 10xy would also be a no-op for any values of x and y because register 0 always contains 0, regardless of how you might try to change it.
Goto. There is no instruction that directly changes the program counter to the addr. However, it is easy to use the branch if zero instruction with register 0 to achieve the same effect. For example, the instruction C0F0 changes the program counter to F0 since register 0 is always 0.

Logical operators. The logical operations (and, xor, left shift, and right shift) work just like the analogous ones in Java, except using 16-bit two's complement integers.

AND and XOR.

00B5

00E3

3312

00A1

R[1] = 0000 0000 1011 0101 (binary) = 00B5 (hex) R[2] = 0000 0000 1110 0011 (binary) = 00E3 (hex) R[3] = 0000 0000 1010 0001 (binary) = 00A1 (hex)

Shifting. The left shift operator shifts the bits over a certain number of places to the left, padding 0s on the right. For example, if register 2 has the value 00B5 and register 3 has the value 0002, then the instruction 5423 assigns the value 02D4 to register 4. To see why, look at the binary representation.
R[2] = 0000 0000 1011 0101 (binary) = 00B5 (hex) = 181 (dec) R[2] <2 =0000 0010 1101 0100 (binary)=02D4 (hex)=724 (dec)
Note that left shifting by one bit is equivalent to multiplication by 2; left shifting by i bits is equivalent to multiplying by 2ⁱ.
The right shift operator is similar, but the bits get shifted to the right. Leading 0s or 1s are padded on the left, according to the sign bit (the leftmost bit). For example, if register 2 has the value 00B5 and register 3 has the value 0002, then the instruction 6423 assigns the value 002D to register 4. To see why, look at the binary representation.
R[2] = 0000 0000 1011 0101 (binary) = 00B5 (hex) = 181 (dec) R[2] >> 2 = 0000 0000 0010 1101 (binary) = 002D (hex) = 45 (dec)
The value is register 2 is nonnegative so 0s are padded on the left. If, instead, register 2 has the value FF4B, then the result of the right shifting is FFD3. In this case the value in register 2 is negative so 1's are padded on the left.
R[2] = 1111 1111 0100 1011 (binary) = FF4B (hex) = -181 (dec) R[2] >> 2 = 1111 1111 1101 0011 (binary) = FFD3 (hex) = - 45 (dec)
Note that right shifting an integer by 1 bit is equivalent to dividing the integer by 2 and throwing away the remainder. This is true regardless of the sign of the original integer. In general, right shifting an integer by i bits is equivalent to dividing it by 2ⁱ and throwing away any remainder. (Note that this does not exactly agree with integer division by the corresponding power of two since -181/4 = -46 in Java.) This type of shifting is called an arithmetic shift or a signed shift: it preserves the sign for two's complement integers.

Efficient multiplication. Using the bitwise operators, we provide an efficient implementation of multiply.toy. To multiply two 16-bit integers a and b, we let b_i denote the ith bit of b. That is,

b = (b₁₅ × 2¹⁵) + (b₁₄ × 2¹⁴) + ... + (b₁ × 2¹) + (b₀ × 2⁰)

By distributivity, we obtain:

a × b = (a × b₁₅ × 2¹⁵) + ... + (a × b₁ × 2¹) + (a × b₀ × 2⁰)

Thus, to compute a × b, it suffices to add the above 16 terms. Naively, this appears to reduce the problem of performing one multiplication to 32 multiplication, two for each of the 16 terms. Fortunately, each of these 32 multiplications are of a very special type. Recall that a × 2ⁱ is the same as left shifting a by i bits. Second, note that b_i is either 0 or 1; thus term i is either a or 0. Program multiply-fast.toy loops 16 times. In iteration i it computes the ith term and adds it to the running total stored in register C. To gain some perspective, recall the standard grade school algorithm for multiplying two decimal integers. The bitwise procedure we just described is really just the grade school algorithm applied to binary integers.

Load address. The load address instruction (opcode 7) is the most primitive type of assignment statement in the TOY language. The code fragment below initializes register A to 30.

11: 7A30 R[A] <- 0030

When using the load address instruction, we often think of the destination register as storing the memory address of some piece of data. This is especially useful when dealing with arrays. In the C programming language, this type of variable is known as a pointer. However, we can also use the load address instruction to store a small constant into a register, instead of using the load instruction. Note that load address only permits you to assign 8 bit integers (00 through FF) to a register, even though registers are capable of storing 16 bit integers.

Arrays. Arrays are not directly built into the TOY language, but it is possible to achieve the same functionality using the load address, load indirect, and store indirect instructions. We illustrate this technique with two examples. First, we will consider a program that reads in a sequence of integers and prints them in reverse order. Then, we will consider a more sophisticated application of arrays that performs the classic insertion sort algorithm on a sequence of integers.

Reverse. Program reverse.toy reads a sequence of positive integers from standard input, and stops when it encounters the integer 0000. It stores the integers in main memory, starting at address 30. We use the load address instruction to store the address 30. Then, it marches through the elements in reverse order, printing them out to standard input. We use register B to keep track of the number of elements read in. We arrange it so that register 6 contains the memory location of the array element that we are currently reading or writing. To write and read an array element, we use the opcodes A and B, respectively.

10: 7101 R[1] <- 0001 r[1] always 1 11: 7a30 r[a] <- 0030 memory address of array a[] 12: 7b00 r[b] <- 0000 # elements in array=n // read in sequence of positive integers 13: 8cff read r[c] while (read r[c]) { 14: cc19 if (r[c]== 0) goto 19 if (c== 0) break 15: 16ab r[6] <- r[a] + r[b] a + n 16: bc06 mem[r[6]] <- r[c] a[n]=c 17: 1bb1 r[b] <- r[b] + r[1] n++ 18: c013 goto 13 } // print out results in reverse order 19: cb20 if (r[b]== 0) goto 20 while (n !=0) { 1a: 16ab r[6] <- r[a] + r[b] a + n 1b: 2661 r[6] <- r[6] - r[1] a + n - 1 1c: ac06 r[c] <- mem[r[6]] c=a[n-1] 1d: 9cff write r[c] print c 1e: 2bb1 r[b] <- r[b] - r[1] n-- 1f: c019 goto 19 } 20: 0000 halt

The program suffers from one important flaw. Since the TOY machine has only 256 memory locations, it is not possible to store or reverse a list that contains too many elements. In the example above, after the program fills up memory locations 30 through FF, it will wrap around and start writing into memory locations 00 through 0F. Pretty soon, it will start overwriting the lines of the original program 10 through 20. A devious user could exploit this buffer overflow and input integers in such a way that the integers from standard input get interpreted as instructions rather than data. Viruses are often spread by such buffer overflow attacks. Program crazy8.toy is a version of reverse.toy that starts storing the array at memory address 00. Thus, after 16 integers are read in and stored, the program starts overwriting itself. The input below is especially malicious. Entering the 20 integers on standard input enables the user to take control of the machine and have it print out 8888 in an infinite loop. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8888 8810 98FF C011 Functions. In Java it is quite useful to divide a program up into smaller functions. We can do the same in TOY. Below is a TOY program that "calls" a multiply function with two arguments and computers their product. Since all of the variables (registers) are global, we need to agree upon a protocol for calling our function. We'll assume that we want to multiply the integers stored in registers A and B, and store their product in register C. Program multiply-function.toy that calls the multiply function twice to compute x × y × z, once to compute x × y, then again to compute (x × y) × z. It uses the jump and link and jump register instructions that are especially designed for this purpose. Instructions 11 and 14 store the value of the program counter in register 3 before jumping to the function located at F0. This makes it possible to return back to the main program, without hardwiring in the address into the program. Every time the program counter is reset to F0, the old program counter is saved away in register F for future use. Instruction F5 returns from the function by resetting the program counter to the value stored in register F. Note also, that the program counter is incremented before the instruction is executed. Thus, during the first function call register F is 16 and not 15. Be very careful about which variables you are using when writing machine language functions. There is no such thing as a "local variable." Had we continued to use register 2 as the loop counter in the multiplication function, this would have overwritten register 2 in the main program, which was being used to store the quantity b. Horner's method. We can use the multiplication function to evaluate polynomials: given integer coefficients a_n, ..., a₂, a₁, a₀ and an integer x, evaluate the polynomial p(x) = a_n xⁿ + ... + a₂ x² + a₁ x¹ + a₀ x⁰ at the integer x. Polynomial evaluation was one raison d'etre for early machines. It has many applications including studying ballistic motion and converting an integer from its decimal representation to hexadecimal. The brute force algorithm for polynomial evaluation is to sum up the n+1 terms, where term i is the product of a_i and xⁱ. To compute xⁱ we could write a power function that multiplies x by itself i-1 times. Horner's method is a clever alternative that is more efficient and easier to code. The basic idea is to judiciously sequence the way in which terms are multiplied. We can rewrite an order 3 polynomial By distributivity, we obtain: p(x) = a₃ x³ + a₂ x² + a₁ x + a₀ = (((a₃) x + a₂) x + a₁) x + a₀ Similarly, we can rewrite an order 5 polynomial p(x) = a₅ x⁵ + a₄ x⁴ + a₃ x³ + a₂ x² + a₁ x + a₀ = (((((a₅) x + a₄) x + a₃) x + a₂) x + a₁) x + a₀ Using Horner's method, only n multiplications are required to evaluate an order n polynomial. Moreover, we can translate the method directly into Java or TOY code. Program horner.toy is the TOY version. In the TOY version, we call our multiply function every time we want to multiply two integers. We can use horner.toy to convert a decimal integer to its hexadecimal representation. To convert 765₁₀ to hex, we set the input x = A, n = 3, a₂ = 7, a₁ = 6, and a₀ = 5. Since all arithmetic is performed in hex, the program computes the hexadecimal equivalent of 7 × 10² + 6 × 10 + 5 = 02FD. Insertion sort. The program insertion-sort.toy reads in a sequence of positive integers from standard input and insertion sorts them. The program terminates upon reading in a nonpositive integer. Linked lists. // data 01: 0001 the constant 1 02: 00D0 memory address of first node of linked list // initialize 10: 8101 R1 <- mem[01] r1 holds 1 11: 8202 r2 <- mem[02] x=pointer to first node of linked list // traverse the linked list 12: 1421 r4 <- r2 + 1 do { 13: a302 r3 <- mem[r2] k=x.key 14: 93ff print r3 print k to standard output 15: a204 r2 <- mem[r2 + 1] x=x.next 16: d212 if (r2> 0) goto 12 } while (x != null) 17: 0000 halt // data D0: 0001 D4: 0004 D8: 0000 DC: 0000 D1: 00D6 D5: 0000 D9: 0000 DD: 0000 D2: 0000 D6: 0002 DA: 0003 DE: 0000 D3: 0000 D7: 00DA DB: 00D4 DF: 0000 This code will traverse the linked list starting at memory location D0, printing out the integer stored in each "node." It will print out 0001 0002 0003 0004. Throughout the computation R1 is always 1. Indexed addressing is used in instructions A304 and A203 Register R2 is a pointer - it is the memory address of the next node. Register R3 is a pointer to the memory address immediately after R2. At each iteration of the loop we print the contents of the value in memory referenced by R2 and use the value in memory referenced by R3 to determine what memory address R2 will store in the next iteration. For the data given above, register R2 will have the values D0, D6, DA, D4, and 00 in that order. This process is repeated until R2 is 0000, i.e., the end of the linked list. In Java, the keyword null plays the role of 0000 and is used to terminate linked lists. Recursion. You can also do recursion in TOY, but this is rather tricky. Exercises Write a program powers2.toy that prints out all of the positive powers of 2 to standard output. Given an integer x, its Collatz sequence is defined by replacing it with x/2 if x is even, and 3x + 1 is x is odd, and repeating until x is 1. Write a program collatz.toy thats reads an integer x from standard input and prints its Collatz sequence to standard output. Hint: use right shift to perform integer division by two. Write a program sum_1-n.toy that reads in an integer N from standard input and prints out the sum 1 + 2 + 3 + ... + N. Write a program min3.toy that reads in three integers from standard input and print to standard output the smallest one. Write a program max3.toy that reads in three integers from standard input and print to standard output the largest one. Write a program sort3.toy that reads in three integers from standard input and print them out to standard output in ascending order. Write a program chop.toy that reads in an integer N from standard input and prints it out as the sum of powers of 2. For example if N = 012A, then the program should print out 0002 0008 0020 0100 since 012A = 0002 + 0008 + 0020 + 0100. This question tests the difference between load address, load, and load indirect. For each of the following TOY programs, give the contents of registers 1, 2, and 3 upon termination. (a) 10: 7211 (b) 10: 8211 (c) 10: 7211 11: 7110 11: 8110 11: A102 12: 2321 12: 2312 12: 2312 13: 0000 13: 0000 13: 0000 Consider the following TOY program. What is the value of register 3 upon termination? 10: 7101 11: 7207 12: 7301 13: 1333 14: 2221 15: D213 16: 0000 Write a program that reads in one integer a from standard input, and outputs a³. Write a program that reads in an integer a from standard input and prints AAAA to standard output if a = 3 a > 3 a <3 a != 3 a >= 3 a <= 3 Suppose that you load the following into locations 10-17 of TOY, set the PC to 10, and press RUN. 10: 7100 R[1] <- 0000 11: 8fff read rf 12: 9f15 mem[15] <- rf 13: 82ff read r2 14: 1112 r1=R1 + r2 15: c016 pc <- 16 16: 91ff write r1 17: 0000 halt What, if anything, is printed to standard output if 1112 1112 Answer: The TOY programs reads two values from standard input. The first value is placed into memory location 15 where it is eventually executed as code. This inserts a second add instruction. Repeat the previous question with the following data on standard input. C011 C011 1112 1112 Write a program that reads in three integers a, b, and c from standard input, and computes the discriminant d = b² - 4ac. Use the multiplication function described above. Suppose that you load the following into locations 10-17 of TOY, set the PC to 10, and press RUN. The program reads in an integer from standard input and prints out a single integer to standard output. List all input values between 0123 and 3210 for which the program print 0000. 10: 8AFF read R[A] 11: 7101 R[1] <- 1 12: 2ba1 r[b] <- r[a] - 1 13: 3cab r[c] <- r[a] & r[b] 14: 9cff write r[c] 15: 0000 halt Answer: 0200 0400 0800 1000 2000. It returns 1 for all inputs that have at most one 1 in their binary representation, i.e, the hexadecimal integers 0000, 0001, 0002, 0004, 0008, 0010, ..., 8000. Suppose that you load the following into locations 10-1F of TOY, load the following data into locations 30-37, Suppose that you load the following data into memory locations 30 through 37 before pressing RUN. 0001 0002 0003 0004 0004 0003 0002 0001 set the PC to 10, and press RUN. What will be the contents of memory locations 30 through 37 after running the program? 10: 7101 R[1] <- 1 // always 1 11: 7a30 r[a] <- 30 a // base memory address of array a[] 12: 7b08 r[b] <- 8 n // the number of elements n in a[] 13: 130b r[3] <- r[b] i=N 14: c320 15: 1400 r[4] <- 0 j=0 16: 2543 17: c51e 18: 16a4 19: a706 1a: 1717 1b: b706 1c: 1414 1d: c016 1e: 6331 1f: c014 Translate the above TOY program into Java code by filling in the ????. for (int i = N; i > ???? ; i = i ????) for (int j = 0; j Suppose that you load the following into locations 10-1F of TOY, load the following data into locations 30-37, Suppose that you load the following data into memory locations 30 through 37 before pressing RUN. 0001 0002 0003 0004 0004 0003 0002 0001 set the PC to 10, and press RUN. What will be the contents of memory locations 30 through 37 after running the program? Suppose that you load the following into locations 10-1B of TOY, set the PC to 10, and press RUN. Suppose also that the following data is entered from standard input. What value is printed? 1CAB EF00 0000 4321 1234 10: 7101 R[1] <- 1 11: 7230 r[2] <- 30 12: 8aff read r[a] 13: ca17 if (r[a]== 0) goto 17 14: ba02 mem[r[2]] <- r[a] 15: 1221 r[2]++ 16: c012 goto 12 17: 8aff read r[a] 18: 8bff read r[b] 19: ff30 r[f] <- pc; pc <- 30 1a: 9cff write r[c] 1b: 0000 halt Repeat the previous exercise, but with the following data on standard input. 2CAB EF00 0000 4321 1234 The following table shows the contents for the TOY registers and a section of TOY memory. Suppose that you set the program counter to 30 and hit run. What, if anything, is printed to standard output? List the final contents of registers 2 and 3 upon termination. R0: 0000 0000 0000 0000 0000 0000 0000 0000 R8: 0000 0000 0000 0000 0000 0011 0000 0000 20: 0000 0000 0000 0000 0000 0000 0000 0000 28: 0000 005A 0000 0000 0000 0000 0000 0000 30: 7101 7200 8329 1221 1331 A303 D333 92FF 38: 0000 0000 0000 0000 0000 0000 0000 0000 40: 7101 7200 8329 A403 1224 1331 A303 D343 48: 92FF 0000 0000 0000 0000 0000 0000 0000 50: 0003 0000 0005 0000 0004 0052 0000 0000 58: 0001 0060 0000 0058 0000 0000 0000 0000 60: 0002 0050 0000 0000 0000 0000 0000 0000 Suppose that the data for memory locations D0 through E0 is as follows. What is the result of running linked.toy? Answer: 1 2 3 4 5 6 7. Change one word of memory in the previous exercise so that it prints out 1 2 6 7 instead of 1 2 3 4 5 6 7. (linked list deletion) Change three words of memory (overwriting one, and using two more) so that it prints out 1 2 3 4 8 5 6 7. (linked list insertion) Creative Exercises Maximum. Write a program max.toy that reads in a sequence of nonnegative integers from standard input and prints out the maximum one. Stop reading in integers as soon as you encounter a negative integer. Magic swap. Write a TOY code fragment that swaps the contents of registers A and B, without writing to main memory or any other registers. 32-bit integers. Represent a 32-bit two's complement integer in TOY with two consecutive words of memory or registers (big endian or little endian). Explain how to add two 32-bit integers. Gray codes. Write a TOY program graycode.toy that reads in an integer n (between 1 and 15) from standard input and then prints out (i >> 1) ^ i to standard output for i = 2ⁿ - 1 through 0. The resulting sequence is called a Gray code of order n. See Exercise XYZ in Section 5.1. The Visual X-TOY Simulator uses the LCD display to show standard output. It is instructive to watch the alternate standard output (the tape punch card) and see the individual bits (8 per row). Greatest common divisor. Write a program gcd.toy that reads in two integers from standard input and prints their greatest common divisor to standard output. Write a function that assumes that registers A and B contain two input integers, output the value in register C, and returns to the address stored in register F. You may use the following (inefficient) algorithm: while (b > 0) { if (b > a) swap a and b a = a - b } return a One-time pad. Implement a one-time pad in TOY to encrypt and decrypt 256 bit messages. Assume that the key is stored in memory location 30 - 3F and that the input consists of sixteen 16-bit integers. Copyright © 2004, Robert Sedgewick and Kevin Wayne. All rights reserved.