Examples of Programming
|
Links on this page:
|
Dr. M. Moris Mano describes a basic computer in his
textbook, This computer is a toy computer, but serves to present
many of the basic concepts The sample programs I have included in this tutorial |
Other Links: |
Code |
Pseudo-code |
Nearer assembly language |
Comments |
// Greatest common divisor // code, following Stallings // 9th, pg 706, without // testing for 0 on A or B // Some interesting test cases: // decimal inputs, hex result // 2100, 882 --> 2a // 1972, 1218 --> 3a // 3264, 5280 --> 60 // 3248, 5264 --> 70 ORG 20 LOOP LDA AVAL CMA INC // GET -A ADD BVAL // B-A SZA BUN CONT BUN DONE CONT SNA BUN BIGA LDA BVAL // DO A - B CMA INC ADD AVAL STA AVAL // A > B BUN LOOP BIGA STA BVAL // B > A BUN LOOP DONE LDA BVAL STA RET HLT ORG 40 AVAL DEC 3248 BVAL DEC 5264 RET DEC 0 |
while a != b if a < b b = b - a else a = a - b end else end while return b |
LOOP: compute b - a if result is 0, go to DONE if result < 0, go to BIGA store result in b go to LOOP BIGA: compute a - b store result in a go to LOOP DONE: put b into result halt // code for A - B: LDA BVAL // AC <- B CMA // AC <- B' INC // AC <-- (B'+1) // so, AC <-- (-B) ADD AVAL // AC <- (-B + A) |
Because Mano's Basic Computer only has very
limited arithmetic and branching capabilities, the code for
calculating a subtraction operation and the code for
branching get rather convoluted. The computer uses 2's
complement to represent negative numbers, so a subtraction
operation is implemented as follows: a - b = -b + a = (b' + 1) + a Where b' is the bitwise complement of b. Generally, assembly languages implement "goto" statements rather then structured programming concepts such as "if/then/else" and "while" loops. However, it is a good idea to simulate the logic of those structures in the assembly language as nearly as possible, which we have tried to do in the "Nearer" code - the third column. When the "nearer" code refers to a result, the assembly language program is actually moving or testing the value in the AC register. An additional limitation of this machine is that it only has "test and skip next instruction if true" branching, which complicates the overall structure of the code. Most real computers allow branching instructions to go nearly anywhere, giving much more compact code. |
Code |
Pseudo-code |
Nearer assembly language |
ORG 10 LDA ECH // calculates 2's comp CMA // 1's comp INC // 2's comp STA ECH // stores 2's of target FST SKI // look for input BUN FST // no input CLA // clear AC INP // input to AC OUT // ouput char STA PTR I // store char ISZ PTR // inc location ADD ECH // is it target? SZA // quit if target BUN FST // next char END HLT // quit ECH HEX 2E // end character "." PTR HEX 50 // store chars here END |
do get char write char store char in array while char != '.' |
LOOP: look for char get char write char store char in array if char != '.' go to LOOP halt |
For convenience, we will call the caller code "main". In all these cases, the subroutine will take 5 values and add them up, returning the result to main.
Code |
Pseudo-code |
Nearer assembly language |
ORG
10 BSA SUBA // call subroutine LDA SUM OUT // output result HLT SUBA HEX 0 // return address LDA NUMB CMA INC STA CNT // put -NUMB to CNT LDA DATP STA PTR CLA // so we can do it again LOOP ADD PTR I // add next value to AC ISZ PTR // point at next element ISZ CNT // increment counter BUN LOOP // loop if cnt != 0 STA SUM // done, sum <- AC BUN SUBA I // return, indirect ORG 30 // temp vars here NUMB DEC 5 // number to add up DATP HEX DATA // start of array SUM HEX 0 // result PTR HEX 0 // current location CNT HEX 0 // countup counter ORG 40 // data here DATA DEC 1 // [0], N = 1 DEC 2 // [1], N = 2 DEC 4 // [2], N = 3 DEC 8 // [3], N = 4 DEC 16 // [4], N = 5 DEC 32 // [5], N = 6 DEC 64 // [6], N = 7 DEC 128 // [7], N = 8 DEC 256 // [8], N = 9 DEC 512 // [9], N = 10 DEC 1024 // [10], N = 11 END |
START: call SUBA write sum halt SUBA: sum = 0 for i=0; i<numb; i++ sum += DATA[i] end for return DATA: <data here>
for i= -numb; i!=0; i++ sum += DATA[ptr] ptr ++ end for |
START: call SUBA write SUM halt SUBA: return address CNT <- -NUMB PTR <- DATA AC <- 0 LOOP: AC += [PTR] PTR ++ CNT ++ if CNT != 0 goto LOOP store AC to SUM return indirect Variables (local/global) NUMB // input to sub DATP // input SUM // output PTR // local to sub CNT // local Data (input to sub) [PTR] means the data at memory location PTR |
The only difference between this and Subroutine
A is that the input and output parameters are located after
the BSA call in the main program, and the subroutine accesses
those parameters using indirect addressing, and uses the ISZ
command to walk through the parameter list one at a time.
Eventually, the final ISZ is used to point to the next line of
code in the main program, the line to which the subroutine should
return.
Overall, this is one way to avoid the use of global variables. In
this case, the subroutine uses the return address to get at the
parameters, and the variables PTR and CNT should be considered
local variables. The location SUBA, the start of the subroutine,
must, of course, be known to main.
Code |
ORG
10 BSA SUBA // call subroutine DEC 5 // 1st param, number to add up HEX DATA // 2nd param, start of array SUM HEX 0 // 3rd param, result LDA SUM OUT // output result HLT // subroutine's local variables: PTR HEX 0 // current location CNT HEX 0 // countup counter SUBA HEX 0 // return address // start of subroutine body LDA SUBA I // first parameter, number to add CMA INC STA CNT // put -NUMB to CNT ISZ SUBA // point at second parameter LDA SUBA I // get ptr to data STA PTR CLA // so we can do it again LOOP ADD PTR I // add next value to AC ISZ PTR // point at next element ISZ CNT // increment counter BUN LOOP // loop if cnt != 0 ISZ SUBA // point to 3rd parameter STA SUBA I // done, 3rd param <- AC ISZ SUBA // point to return location BUN SUBA I // return, indirect ORG 40 // data here DATA DEC 1 // [0], N = 1 DEC 2 // [1], N = 2 DEC 4 // [2], N = 3 DEC 8 // [3], N = 4 DEC 16 // [4], N = 5 DEC 32 // [5], N = 6 DEC 64 // [6], N = 7 DEC 128 // [7], N = 8 DEC 256 // [8], N = 9 DEC 512 // [9], N = 10 DEC 1024 // [10], N = 11 END |
In this version, main will load the parameters into the local space of the subroutine, getting the values from main's local variable space. Then the value returned will be available to main in the AC register, so this subroutine will be acting more like what we traditionally call a function.
The code uses the variable SUBP to hold the address of the subroutine so that the parameters can be put after that location using indirect addressing, walking through the parameter list using the ISZ command on the PARP variable. We do not want to use PARP as the only variable pointing to SUBA because we might wish to call SUBA more than once, and because of the ISZ operations, PARP will not always point to the SUBA starting address.
The parameters are all accessed relative to the location of the
start of the subroutine, SUBA.
Code |
ORG
10 LDA SUBP // get address of sub start STA PARP // place to put parameters ISZ PARP // skip return address location ISZ PARP // skip first instruction, BUN CODE LDA NUMB // 1st parameter, number STA PARP I // 1st parameter in sub ISZ PARP // go to second parameter, data pointer LDA DATP STA PARP I // store second parameter BSA SUBA // call subroutine STA SUM OUT // output result HLT // data local to main: SUBP HEX SUBA // address of subroutine PARP HEX 0 NUMB DEC 5 // 1st param, number to add up DATP HEX DATA // 2nd param, start of array SUM HEX 0 // 3rd param, result // subroutine's local variables: SUBA HEX 0 // return address BUN CODE LOCN HEX 0 // local copy of n, 1st param LOCD HEX 0 // local copy of datap, 2nd param PTR HEX 0 // current location CNT HEX 0 // countup counter // start of subroutine body CODE LDA LOCN // first parameter, number to add CMA INC STA CNT // put -NUMB to CNT LDA LOCD // get ptr to data, 2nd param STA PTR CLA // so we can do it again LOOP ADD PTR I // add next value to AC ISZ PTR // point at next element ISZ CNT // increment counter BUN LOOP // loop if cnt != 0 BUN SUBA I // return, indirect ORG 40 // data here DATA DEC 1 // [0], N = 1 DEC 2 // [1], N = 2 DEC 4 // [2], N = 3 DEC 8 // [3], N = 4 DEC 16 // [4], N = 5 DEC 32 // [5], N = 6 DEC 64 // [6], N = 7 DEC 128 // [7], N = 8 DEC 256 // [8], N = 9 DEC 512 // [9], N = 10 DEC 1024 // [10], N = 11 END |
Code |
Pseudo-code |
Nearer
assembly language |
//
Recursive function using stack // sum 1 through n // f(n) = n + f(n-1) for n > 0 // = 0 for n = 0 // = ? for n < 0 // main program ORG 10 LDA TARGET // AC <-- n BSA RSUM // AC <-- f(n) OUT // write n, in hex HLT TARGET DEC 20 // subroutine |
main n = 20 write (rsum(20)) end main |
main AC <-- n call RSUM write AC (rsum(n)) end main n given value 20 |
This is an illustration of using a stack to implement recursive
function calls.
The program must assume that the values in the local variables and the AC will be corrupted by the function call, so any information this instantiation of the subroutine needs should be saved on the stack before the call, and restored from the stack afterwards. In this case, that information is the return address (which will always need to be saved) and the value of the parameter n. Thus, before the recursive call, these two pieces of information must be pushed onto the stack, and when the subroutine returns, two calls to pop the information from the stack are required.
The stacking subroutines (STKPUSH and STKPOP) can be found on the Utilities page of my notes.
A program this complex should have a number of test cases, which I have provided below, and since the output of the simulator is in hex, I have provided both decimal and hex results.
n f(n) dec f(n)
hex n f(n)
dec f(n) hex
1
1 1
11 66 42
2
3 3
12 78
4e
3
6 6
13 91
5b
4
10 a
14 105 69
5
15 f
15 120 79
6
21 15
16 136
88
7
28 1c
17 153
99
8
36 24
18 171 ab
9
45 2d
19 190 be
10
55
37 20
210 d2
A question for the interested reader: since this computer
uses 16-bit 2's complement, it can only hold positive numbers up
to 215-1, so what is the biggest value of n for which
this program will work correctly, ie, not result in an overflow?
Code |
Pseudo-code |
Nearer assembly language |
// Recursive function using
stack // sum 1 through n // f(n) = n + f(n-1) for n > 0 // = 0 for n = 0 // = ? for n < 0 // main program ORG 10 LDA TARGET // AC <-- n BSA RSUM // AC <-- f(n) OUT // write n, in hex HLT TARGET DEC 20 // subroutine RSUM HEX 0 // return address SZA // n = 0? BUN RSUMA // n <> 0, so continue BUN RSUM I // n = 0 so return 0 in AC RSUMT HEX 0 // local, transient, storage RSUMA STA RSUMT // temp <-- n BSA STKPUSH // stack <-- n LDA RSUM // AC <-- return address BSA STKPUSH // stack <-- return address LDA RSUMT // AC <-- n ADD NEGONE // AC <-- (n-1) BSA RSUM // AC <-- f(n-1) STA RSUMT // temp <-- f(n-1) BSA STKPOP // AC <-- return address STA RSUM // ret location <-- return address BSA STKPOP // AC <-- n ADD RSUMT // AC <-- n + f(n-1) BUN RSUM I // return |
main n = 20 write (rsum(20)) end main function rsum (int n) if (n=0) return 0 return n + rsum (n-1) end function |
main AC <-- n call RSUM write AC (rsum(n)) end main n given value 20 rsum: return address AC = 0? no - continue yes - return 0 temp: word continue: temp <-- AC (n) stack AC (n) stack return address AC <-- temp AC <-- n-1 call rsum // get f(n-1) temp <-- AC (f(n-1)) pop to return address pop n to AC add f(n-1) to n (in AC) return |
Code |
Pseudo-code |
Nearer
assembly language |
ORG 10 LDA ECH // calculates 2's comp CMA // 1's comp INC // 2's comp STA ECH // stores 2's of target FST SKI // look for input BUN FST // no input CLA // clear AC INP // input to AC OUT // ouput char STA PTR I // store char ISZ PTR // inc location ADD ECH // is it target? SZA // quit if target BUN FST // next char END HLT // quit ECH HEX 2E // end character "." PTR HEX 50 // store chars here END |
do get char write char store char in array while char != '.' |
LOOP: look for char get char write char store char in array if char != '.' go to LOOP halt |