Mano Examples

Examples of Programming Mano's Basic Computer

Dr. M. Moris Mano describes a basic computer in his textbook,
Computer System Architecture, 3rd edition, 1993.

This computer is a toy computer, but serves to present many of the basic concepts
behind all digital computers and
gives us a good platform to study some key features of assembly language programming.

The sample programs I have included in this tutorial
can be assembled and executed using My Computer Simulator.

GCD as a main program

 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.

Input and Output

The first observation is that this program should continue running until the input character is a flag value, in this a period, '.'. The program will need to do a comparison, but the only way this can be done in Mano's computer is by adding two values and checking the result, which means that we need to add the character just read in to the "negative" of the target character. Thus, the program begins by computing that negative.

The "look for char" operation is implemented using the SKI test. My simulator will make this flag true and put data into the input register, INPR, if there are one or more characters in the Input panel.

This code also assumes that the output register, OUTR, works pretty much instantly. If there was any question, the code should be checking using SKO before it uses the OUT command.

The program uses a pointer, PTR, to point to the next free entry in the array of characters, uses indirect addressing to put the data into the memory location referenced by PTR, and uses the ISZ instruction to update the value in PTR. The result of this ISZ should always be false as long as the array of characters does not overflow the memory. Thus, there are limits to this program. Other than this overflow problem, using ISZ is a rather elegant solution to walking through the memory one word at a time.

This program loads chars from input stream, copies them to output stream, and to memory locations starting at 50, until the target char, ECH, encountered. It will infinite loop if the input stream does not end with a . - period.

 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

Subroutine A - Sum elements, global variables

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       //  , N =  1      DEC 2       //  , N =  2      DEC 4       //  , N =  3      DEC 8       //  , N =  4      DEC 16      //  , N =  5      DEC 32      //  , N =  6      DEC 64      //  , N =  7      DEC 128     //  , N =  8      DEC 256     //  , N =  9      DEC 512     //  , N = 10      DEC 1024    // , N = 11      END START:   call SUBA   write sum   halt SUBA:   sum = 0   for i=0; i for translates this way: ptr = 0 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

Subroutine B - Sum elements, parameters in caller

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       //  , N =  1      DEC 2       //  , N =  2      DEC 4       //  , N =  3      DEC 8       //  , N =  4      DEC 16      //  , N =  5      DEC 32      //  , N =  6      DEC 64      //  , N =  7      DEC 128     //  , N =  8      DEC 256     //  , N =  9      DEC 512     //  , N = 10      DEC 1024    // , N = 11      END

Subroutine C - Sum, parameters in subroutine

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       //  , N =  1      DEC 2       //  , N =  2      DEC 4       //  , N =  3      DEC 8       //  , N =  4      DEC 16      //  , N =  5      DEC 32      //  , N =  6      DEC 64      //  , N =  7      DEC 128     //  , N =  8      DEC 256     //  , N =  9      DEC 512     //  , N = 10      DEC 1024    // , N = 11      END

Subroutine D - Sum, parameters on stack - Coming

 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

Subroutine E - Sum 1 through n recursively

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?