Practice Exercise 9 Answers
-
Encode the following into binary just as it would be stored in the
CSC-1's memory:
LOD M 0000 0000 0000 0101
AGAIN: ADD K 0011 0000 0000 0110
SHL 1111 0100 0000 0000
JZ AGAIN 1001 0000 0000 0001
HLT 1111 1001 0000 0000
M: NUM 8 0000 0000 0000 1000
K: NUM 10 0000 0000 0000 1010
-
In the CSC-1 only 4 bits are dedicated to the opcode for instructions
that have an operand. The instructions that have no operand, such as SHR,
which implicitly work on the A register, are encoded using the "escape"
mechanism of setting the top 4 bits to 1111 and putting the "real" opcode
into the next 4 bits. Propose a way to allow the inclusion of more
instructions that have an operand. What effect would your proposal have on
the basic fetch/decode/execute cycle?
One way of having more opcodes is to expand the opcode field to 5 bits.
However, this cuts back on the number of bits to specify the operand, down
to 11, giving us only 2048 addressable words of memory. If we could expand
all the registers and all the memory words to 17 bits, that would work, too,
but it is highly unlikely we could do this.
Therefore, our only viable option is to use more than one word to specify
the operand. For those instructions that have an operand, the computer
fetches the next word and uses this as either data or an address. For
operand-less instructions, just one word will suffice. This would make our
object programs longer and it would necessitate a second memory fetch for
many instructions, which would require more time and slow down the programs.
-
Create an assembler skeleton for a piece of C code that uses the <=
comparison. The body of the then and else parts need not be specified.
Here's the C' skeleton
if (a <= b)
/* then code */
else
/* else code */
LOD A ; Need to subtract a-b to compare
SUB B
JZ THEN ; If a = b then do then part
JN THEN ; or if a < b also goto the then part
JMP ELSE ; otherwise do else
THEN: ....
JMP ENDIF ; jump around else part
ELSE: ....
ENDIF: NOP ; serves as target for JMP
Another possibility is to realize that the then and else parts can be
swapped if the condition is negated. The logical negation of a<=b is a>b,
which gives rise to the following:
LOD A ; Need to subtract a-b to compare
SUB B
JP ELSE ; If a>b then do else part
THEN: .... ; Otherwise fall through to then part
JMP ENDIF ; jump around else part
ELSE: ....
ENDIF: NOP ; serves as target for JMP
-
Trace through the following CSC-1 program, whose purpose is to find the
largest element in an array of integers. Show the values of the A,
S, PC and IR registers at the beginning
of each instruction execution. Use symbolic values for the IR register but
show integer values for the others.
0 TOP: LDI 2000 ; bring ARRAY[I] into A reg
1 ADD I ; by first calculating address
2 A2S
3 LDS
4 JN ENDLOOP ; if the element is negative, stop
5 STD TEMP ; save it in TEMP for later reuse
6 SUB MAX ; compare element to current MAX value
7 JP CHANGE ; if it's greater than MAX, then change max
8 JMP NOCHANGE ; else do nothing
9 CHANGE: LOD TEMP ; get element out of TEMP
10 STD MAX ; and copy it into MAX
11 NOCHANGE: LDI 1 ; add 1 to index variable I
12 ADD I ; which sets us up for next round
13 STD I
14 JMP TOP ; keep going! (This is a loop...)
15 ENDLOOP: HLT ; the answer is in memory location MAX
16 =2000
2000 ARRAY: NUM 26 ; this is the array of 3 integer
2001 NUM 47 ; we can see this is the max value!
2002 NUM 17
2003 NUM -1 ; sentinel value signaling the end of the array
2004 I: NUM 0 ; index variable
2005 MAX: NUM 0 ; start out with lowest possible value
2006 TEMP: NUM 0 ; temporary storage place
Time PC IR A S I MAX TEMP
-----------------------------------------------------------------
0 0 LDI 2000 0 0 0 0 0
1 1 ADD I 2000 0 0 0 0
2 2 A2S 2000 0 0 0 0
3 3 LDS 2000 2000 0 0 0
4 4 JN ENDLOOP 26 2000 0 0 0
5 5 STD TEMP 26 2000 0 0 0
6 6 SUB MAX 26 2000 0 0 26
7 7 JP CHANGE 26 2000 0 0 26
8 9 LOD TEMP 26 2000 0 0 26
9 10 STD MAX 26 2000 0 0 26
10 11 LDI 1 26 2000 0 26 26
11 12 ADD I 1 2000 0 26 26
12 13 STD I 1 2000 0 26 26
13 14 JMP TOP 1 2000 1 26 26
14 0 LDI 2000 1 2000 1 26 26
15 1 ADD I 2000 2000 1 26 26
16 2 A2S 2001 2000 1 26 26
17 3 LDS 2001 2001 1 26 26
18 4 JN ENDLOOP 47 2001 1 26 26
19 5 STD TEMP 47 2001 1 26 26
20 6 SUB MAX 47 2001 1 26 47
21 7 JP CHANGE 21 2001 1 26 47
22 9 LOD TEMP 21 2001 1 26 47
23 10 STD MAX 47 2001 1 26 47
24 11 LDI 1 47 2001 1 47 47
25 12 ADD I 1 2001 1 47 47
26 13 STD I 2 2001 1 47 47
27 14 JMP TOP 2 2001 2 47 47
28 0 LDI 2000 2 2001 2 47 47
29 1 ADD I 2000 2001 2 47 47
30 2 A2S 2002 2001 2 47 47
31 3 LDS 2002 2002 2 47 47
32 4 JN ENDLOOP 17 2002 2 47 47
33 5 STD TEMP 17 2002 2 47 47
34 6 SUB MAX -30 2002 2 47 17
35 7 JP CHANGE -30 2002 2 47 17
36 8 JMP NOCHANGE-30 2002 2 47 17
37 11 LDI 1 -30 2002 2 47 17
38 12 ADD I 1 2002 2 47 17
39 13 STD I 3 2002 2 47 17
40 14 JMP TOP 3 2002 3 47 17
41 0 LDI 2000 3 2002 3 47 17
42 1 ADD I 2000 2002 3 47 17
43 2 A2S 2003 2002 3 47 17
44 3 LDS 2003 2003 3 47 17
45 4 JN ENDLOOP -1 2003 3 47 17
46 15 HLT -1 2003 3 47 17
-
Perform a full integer multiplication of 196 x 37 using the scheme shown
at the end of Chapter 9.
196=11000100 37=00100101
counter partial sum multiplier
===========================================================================
00001000 00000000 00000000 00100101
+ 00000000 add 0--------- ^
------------------
00000000 00000000
00000111 (decr) 01001010 (lshift)
not zero 00000001 10001000 (lshift)
---------------------------------------------------------------------------
00000111 00000000 00000000 01001010
+ 00000000 add 0--------- ^
------------------
00000000 00000000
00000110 (decr) 10010100 (lshift)
not zero 00000000 00000000 (lshift)
---------------------------------------------------------------------------
00000110 00000000 00000000 10010100
+ 11000100 add 196------- ^
------------------
00000000 11000100
00000101 (decr) 00101000 (lshift)
not zero 00000001 10001000 (lshift)
---------------------------------------------------------------------------
00000101 00000001 10001000 00101000
+ 00000000 add 0--------- ^
------------------
00000001 10001000
00000100 (decr) 01010000 (lshift)
not zero 00000011 00010000 (lshift)
---------------------------------------------------------------------------
00000100 00000011 00010000 01010000
+ 00000000 add 0--------- ^
------------------
00000011 00010000
00000011 (decr) 10100000 (lshift)
not zero 00000110 00100000 (lshift)
---------------------------------------------------------------------------
00000011 00000110 00100000 10100000
+ 11000100 add 196------- ^
------------------
00000110 11100100
00000010 (decr) 01000000 (lshift)
not zero 00001101 11001000 (lshift)
---------------------------------------------------------------------------
00000010 00001101 11001000 01000000
+ 00000000 add 0--------- ^
------------------
00001101 11001000
00000001 (decr) 10000000 (lshift)
not zero 00011011 10010000 (lshift)
---------------------------------------------------------------------------
00000001 00011011 10010000 10000000
+ 11000100 add 196------- ^
------------------
00011100 01010100
00000000 (decr) 00000000 (lshift)
zero do not shift
---------------------------------------------------------------------------
-
Write a CSC-1 program that performs subtraction (A-B) by forming the 2's
complement of the subtrahend (B) and then adding that to the subtractor (A).
What we need to do is to flip all the bits of B, which can be done using the
NOT instruction, add 1 to get the 2's complement, and then add A, in effect
doing
A + (-B)
The only complication is that we cannot change B in memory so we must flip
its bit and add 1 in a register, or store in memory temporarily. Here's the
program:
NOT B ; Bring in B and flip all bits
ADD ONE ; Add +1 from a memory word
ADD A ; Add A to negative B
The NOT instruction reads a word in from a named memory location and flips
its bits before storing it back into the A register. This program also
needs a special memory word with +1 in it, which can be set up in assembler
as:
ONE: NUM 1 ; "Constant" value 1