Machine-language programming problems

I strongly recommend against looking at the solutions for the problems below until you have attempted the problems. (That's why I put the solutions on separate web pages.) There is no need to print the solutions out now; they'll be here when you come back, at least through the date of the final exam.


Problem #1

Write a VELMA program to count the number of 'space' characters in memory words 10000 through 14000 (semi-inclusive, i.e. including 10000 but not including 14000). Leave the count in R0.

Note: In the ASCII character set, the code for a space is 40 (base 8). Now, we would normally put about three ASCII characters in a 24-bit word, but for the purposes of this problem for now let's just say that each character is in its own word. (We could more appropriately do the more realistic version of this as a PDP-11 problem, which has separate bytes and words and other complications.)

a solution to problem #1


Problem #2

Describe simply what the following program does, and assuming that the initial contents of memory word 2000 is 5, trace the program and state the final contents of R4.

Note: The bitwise AND of an integer with 1 discards all but its least significant bit. If this bit is zero, the number is even; else it is odd.

Note: For ease of reading, the constants 1, 2, and 3 are stored in register 1, 2, and 3, respectively.

        MOV# 1, R1
        MOV# 2, R2
        MOV# 3, R3

        MOV 2000, R4

  LOOP:	BIT R4, R1
	BEQ L2
	MUL R3, R4
	ADD R1, R4
	BR L3
    L2:	DIV R2, R4
    L3:	CMP R1, R4
	BGT LOOP
	HALT

a solution to problem #2


Problem #3

You are probably familiar with the formula   the sum from i=0 to n of i is equal to (n**2 + n) over 2

Suppose that you were sceptical of this formula and no one showed you a proof. You try it for a few cases and it works, but you are having difficulty finding a proof yourself. Before looking harder for a proof you'd like to verify it for a few hundred cases or more, by computer.

Write a program in the VELMA assembly language which verifies this equation (i.e. that the two sides are indeed equal), for 0 <= n < N. N is stored in memory location 500.

The answer should be in R0 when your program HALTs. If overflow occurs at any point in your calculation, your program should HALT with -2 in R0. Otherwise, if it finds a counterexample to this formula, it should HALT with the n counterexample in R0 and with carry set (and overflow clear). If it verifies the formula for all n, 0 <= n < N, it will HALT with -1 in R0.

Your program needn't be especially well-commented but you should explain your use of registers and anything else particularly unclear. Do not assemble your code; leave it in symbolic form.

a solution to problem #3


Problem #4

Here is a VELMA assembly language program.

.ORG 100
MOV X, R2
MUL R2, R2
BVS OVERFLOW
MOV Y, R4
MUL R4, R4
BVS OVERFLOW
SUB R4, R2
MOV R2, W
HALT
OVERFLOW:CLR R0
MOV R0, W
HALT
X:.WORD 22
Y:.WORD 33
W:.WORD 0

(a) Describe simply (in English) what it does (in general, for any values of X and Y).

(b) Assemble the program into unsigned 24-bit octal numbers.

solution to problem #4


Problem #5

Write a subroutine in VELMA assembly language to compute the sum of an array of signed 24-bit numbers (normal VELMA words; i.e. you can use ADD). The calling sequence to add N words starting at location A is:
MOV N, -(R6)
MOV #A, -(R6)   ; (actually this requires two instructions)
JSR ROUTINE
INC R6
INC R6
You return the computed sum in R0. Your subroutine may thus use R0 as a scratch register, but any other registers used must be pushed and restored.

Your subroutine is required to check for overflow. If none of the addition operations overflows, your subroutine must return the sum in R0, and with the V condition code clear. If any of the addition operations overflow, your subroutine must return with the V condition code set, and in that case it doesn't matter what the final contents of R0 is. In the case of overflow, the caller will ignore the returned contents of R0; thus your subroutine may return immediately. (So there would actually be a BVS instruction between the JSR and the ADD in the calling sequence above.)

You need not handle the case of zero-sized arrays; the count (second argument) must be positive. You are not required to handle any kind of incorrect use of your subroutine.

Your program needn't be especially well-commented but you should explain your use of registers and anything else particularly unclear.

Do not assemble your code; leave it in symbolic form.

a solution to problem #5


Problem #6

Write a recursive factorial subroutine in VELMA. It returns its result by leaving it in R0 (and thus it can use R0 as a scratch register without having to save and restore it).

a solution to problem #6


Problem #7

'A' is an array of 308 items (30 in base 8, i.e. 24) starting at memory location 500 (that's also in base 8). Each item consists of two words, representing an x and a y coordinate for a point in the plane. So for example, the x coordinate for A[3] is at memory location 506, and the y coordinate for A[3] is at memory location 507.

'B' is an array of another 308 items starting at memory location 560 (right after 'A') and organized similarly.

The distance between points A[i] and B[i], for a particular i, is

Write a program in the VELMA machine language to find the value of i (from 0 to 30) such that A[i] and B[i] are the closest to each other. The result should be in R0 when you HALT.

Note that you do not have to take square roots to write this program. sqrt(p) < sqrt(q) if and only if p<q. So although finding the actual distance requires taking a square root, comparing distances does not; your register corresponding to a variable min will actually store the square of the minimum distance so far, rather than the actual minimum distance so far.

a solution to problem #7


Problem #8

Write a program in the VELMA machine language to count how many integers in a certain range are prime. An integer greater than one is prime iff it has only two factors: itself and 1. The limits of the range will be stored in registers R3 and R4 before your program is started, and the range is inclusive. For example, if R3 contains 1110 and R4 contains 1910, the answer would be 4, because the prime numbers in that range are (only) 11, 13, 17, and 19. Your program should HALT with the count in R0. If R3 > R4, the count is zero.

a solution to problem #8


[CSC 258 additional problems]
[main course page]