CSCI 162: Marie examples


Marie web interface (github)

Example 0: basic I/O, addition
Example 1: if/else if/else
Example 2: simple loop
Example 3: emulating bit shifts, powers of 2
Example 4: emulating division through shifts and adds
Example 5: emulating null terminated strings
Example 6: simple function calls/returns
Example 7: emulating arrays
Example 8: recursion using a stack we build and maintain
Example 9: self modifying code


Example 0: basic I/O, addition
A program to read two numbers and print their sum:

marie file

        / program to get two values from user
        / add them together, and print result

        / read first value into ACC
        / then copy into variable X
        input
        store   X

        / read second value into ACC
        / then copy into variable Y
        input
        store   Y

        add     X   / ACC = ACC + X
        output      / print result
        halt        / end program

        / local variables, initialized to 0 (using base 10)
X,      dec     0
Y,      dec     0

Example 1: if/else if/else
A program to read and compare two numbers, with different output based on relative values:

  • prints X then Y if X is bigger
  • prints Y then X if Y is bigger
  • just prints X if they are equal

    marie file

            / program to get x,y from user
            / if x < y print x then y
            / else if x > y print y then x
            / else just print x
    
            org         100
            input               / get value for x
            store       X
            input               / get value for y
            store       Y
    
    Test1,  subt        X       / acc = y - x
            skipcond    000     / if negative then x bigger, skip further tests
            jump        Test2
            load        X       / got here if x bigger, print x then y, then done
            output
            load        Y
            output
            jump        Done
    
    Test2,  skipcond    800     / if positive then y bigger, skip further tests
            jump        XYEq    / if here then equal, go to XYeq print section
            load        Y       / got here if y bigger, print y then x, then done
            output
            load        X       / then print y
            output
            jump        Done
    
    XYEq,   load        X       / just print x, then done
            output
    
    Done,   halt
    
    X,      dec         0       / default value for x
    Y,      dec         0       / default value for y
    

    Example 2: simple loop
    A program to get the user to enter an integer less than 10 (repeats until a valid response is given).

    marie file

            / program to get int < 10 from user
            / keep reading til valid value obtained
    
            org         100
    NewVal, input               / get value for x
            store       X
            subt        TooBig  / compute x - toobig
            skipcond    000     / if negative then x ok (less than toobig)
            jump        NewVal  / otherwise go back and try again
    
    Show,   load        X       / got valid value, print x, then done
            output
            halt
    
    X,      dec         0       / default value for x
    TooBig, dec         10      / X must be less than this
    

    Example 3: emulating bit shifts, powers of 2
    A program to get the user to give two integers, X and N, and show the result of shifting X left N bits.

    Since we don't have a shift operation in Marie, we'll use the following algorithm to do it with just addition (adding x to itself doubles x, just like a single shift left).

       int i=0, N, x;
       scanf("%d", &x);
       scanf("%d", &N);
       while (i < N) {
          x += x;
          i++;
       }
       printf("%d", x);
    

    marie file

            / program to get integers X and N then display
            /    results of shifting X left by N bits
            org         100
            input                / get value of X
            store       X
            input                / get value of N
            store       N
    While,  load        N        / compute N-I
            subt        I
            skipcond    800      / if it's positive we're not done
            jump        Done
            load        X        / double X
            add         X
            store       X
            load        I        / increment I
            add         Incr
            store       I
            jump        While    / go back to loop test
    
    Done,   load        X        / we're done, print X
            output
            halt
    
    X,      dec         0        / value being shifted
    N,      dec         0        / number of bits to shift
    I,      dec         0        / loop counter
    Incr,   dec         1        / I += 1 each pass
    

    Example 4: emulating division through shifts and adds
    A program to get the user to give two integers, N and D, and show the result of dividing N by D. Since we don't have a divide operation in Marie we'll just use addition, but we want to be much more efficient than just adding D over and over until we get N.

    We'll use the following algorithm, essentially using bit shifts to get the effect of multiplying D by powers of 2 and adding the results together (like one would in computing the results in binary).
       int answer = 0;
       int N, D;
       scanf("%d", &N);
       scanf("%d", &D);
       int k = N;
       while (k > 0) {
          int pow = 1;
          int j = D;
          while ((j+j) < k) {
             j += j;
             pow += pow;
          }
          k -= j;
          answer += pow;
       }
       if (k < 0) answer--;
       printf("%d", answer);
    

    marie file
            / get two integers, N, D, from user
            / compute and display results of N div D
            org         100
            input
            store       N       / get user value for N
            input
            store       D       / get user value for D
            load        N       / K = N
            store       K
            
    Outer,  load        K       / not done if K is positive
            skipcond    800
            jump        Done    / otherwise we're finished
            load        Incr    / Pow = 1
            store       Pow
            load        D       / J = D
            store       J
    
    Inner,  load        J       / not done if 2J < K
            add         J
            subt        K
            skipcond    000
            jump        AftIn   / leave inner loop
            load        J       / J = 2*J
            add         J
            store       J
            load        Pow     / Pow = 2*Pow
            add         Pow
            store       Pow
            
            jump        Inner   / back to top of inner loop
            
    AftIn,  load        K       / K = K - J
            subt        J
            store       K
            load        Answer  / Answer = Answer + Pow
            add         Pow
            store       Answer
                    
            jump        Outer   / back to top of outer loop
    
    Done,   load        K       / if K < 0 answer--
            skipcond    000
            jump        Disp
            load        Answer
            subt        Incr
    Disp,   load        Answer  / we're done, display the results
            output
            halt
            
    N,      dec         0       / user value for N
    D,      dec         0       / user value for D
    K,      dec         0       / amount of N still left
    J,      dec         0       / current multiple of D
    Pow,    dec         0       / computing powers of 2
    Answer, dec         0       / final result
    Incr,   dec         1       / for ++ --
    

    Example 5: emulating null terminated strings
    A program to print a null terminated string using a loop from the start of the string, and using the address of individual bytes as we iterate.

    Notes:

    marie file

             / print a string through an indirect address
             /    like a pointer
             / ** make sure the output mode is in unicode **
    
    While,   load        AddrMsg   / CurAddr = &(msg[index])
             add         Index
             store       CurAddr
             clear                 / acc = msg[index]
             addi        CurAddr
             skipcond    800       / if msg[index] > null go ahead and print,
             jump        Done      / otherwise we're done
    Print,   output
             load        Index     / index++
             add         Incr
             store       Index
             jump        While     / repeat loop for next char
    
    Done,    halt
    
    MsgSt,   dec         72        / 'H'
             dec         105       / 'i'
    Null,    dec         0         / '\0'
    AddrMsg, hex         D         / addr of MsgSt
    Index,   dec         0         / current index into msg[]
    CurAddr, hex         0         / addr of msg[index]
    Incr,    dec         1         / for ++ 
    

    Example 6: simple function calls/returns
    A program that calls a subroutines (using variables to pass parameters, store local values, and return a value). The key syntax elements are:
      Jns Funcname / used to call the function
      Funcname, hex 000 / used to start the function definition
      JumpI Funcname / used to return from the function

    marie file

            / example of creating, calling, and returning from a function
            /    using variables to pass parameters,
            /    to return values, and as local variables
            input             / get user input, store in var FooParam
            store   FooParam
            JnS     Foo       / call Foo, start running with instruction AFTER foo
            load    FooReturn / retrieve and print whatever is returned
            output
            halt
            
    Foo,    hex     000      / stores address to use when returning from foo
            load    FooParam / get and print passed param
            output
            add     FooLocal / return FooParam + FooLocal
            store   FooReturn
            JumpI   Foo      / return from foo (to the address we stored when foo was called)
    
    FooParam, dec    0       / use to pass a param to foo
    FooLocal, dec    20      / use as "local" variable for foo
    FooReturn, dec   0       / use to return a value from foo
    

    Example 7: emulating arrays
    A program to get an array size from the user, fill the array with user input, then print the array content.

    marie file

                / program to let the user enter an array size,
                / then fill the array with values,
                / then print the array
                
                input               / get array size from user
                store       Size
                
                load        Arr     / copy array address into IndexPos
                store       IndxPos
    GetVal,     load        Size    / if size > index we're not done yet
                subt        Index
                skipcond    800
                jump        Print   / we're done entering, now go print
                input               / get next array element
                storeI      IndxPos / store in arr[index]
                load        IndxPos / IndxPos++
                add         Incr
                store       IndxPos
                load        Index   / Index++
                add         Incr
                store       Index
                jump        GetVal  / return to loop test
                
    Print,      load        Arr     / copy array address into IndexPos
                store       IndxPos
                clear               / Index = 0
                store       Index  
    PrtVal,     load        Size    / if size > index we're not done yet
                subt        Index
                skipcond    800
                halt                / we're finished
                loadI       IndxPos / get/print next element from arr[index]
                output      
                load        IndxPos / IndxPos++
                add         Incr
                store       IndxPos
                load        Index   / Index++
                add         Incr
                store       Index
                jump        PrtVal  / return to loop test            
                
    Index,      hex         0       / current array index
    IndxPos,    hex         28      / address of current array index
    Element,    hex         0       / value of current array element
    Incr,       hex         1       / for ++
    Size,       hex         0       / user chosen array size
    Arr,        hex         28      / address for start of the array storage
    
    Note: the array above uses addresses 28 (hex) through 28+Size.
    If we wanted to have a second array we could add another pair of variables, e.g.

    Size1,      hex         0
    Arr1,       hex         30
    Size2,      hex         0
    Arr2,       hex         0
    
    and once we know the size of array 1 we could compute the start address for array 2 as follows (assuming we want array 2 to be stored right after array 1 in memory):
       load Arr1
       add  Size1
       store Arr2
    

    Example 8: recursion using a stack we build and maintain
    A program to recursively compute a value - maintaining a our own stack to keep track of local variable values, passed parameters, return values, and the return address to use when returning from a function call.

    marie file

    /
    / Recursion example: parameter passing and return value handled through global stack
    /
    / pseudo-code view of program     Uses a global stack for parameter passing
    /                                   - Stack tracks address of bottom of stack
    / int sum(int N)                    - ToS tracks address of next free spot atop stack
    / {                                 - caller pushes its locals* then params to pass, then calls
    /    int result = 0;                - callee pops its params, and pushes result before return
    /    if (N > 0) {                   - caller pops result and its locals* after call returns
    /       result = sum(N-1);          - currently no error checks for stack full/empty
    /       result += N;                * recursive functions must store/restore return addr
    /    }                            Push logic                   load   Val
    /    return result;                 - store value at ToS       storeI ToS
    / }                                   then ToS++               load   ToS
    /                                                              add    Incr
    / int main()                                                   store  ToS
    / {
    /    int N;                       Pop logic                    load   ToS
    /    cin >> N;                      - Tos-- then               subt   Incr
    /    int R = sum(N);                  load value from ToS      store  Tos
    /    cout << R;                                                loadI  ToS
    / }                                                            store  Val
    /
    
    Main,       input
                storeI   ToS     / push N onto stack before call
                load     ToS     / (and increment ToS)
                add      Incr
                store    ToS
                JnS Sum
                load     ToS     / pop final result for output
                subt     Incr    / (after decrementing ToS)
                store    ToS
                loadI    ToS
                output
                halt
    
    Sum,        hex      000     / int sum(int N);
                clear            / set result = 0 (only used for base case)
                store    SumR
                load     ToS     / pop N off stack into local
                subt     Incr    / (after decrementing ToS)
                store    ToS
                loadI    ToS
                store    SumN
                skipcond 800     / if N > 0 skip to body
                Jump     Return  / else we're done (go return 0)
    
    Body,       load     SumN    / push N onto stack so we can get it back after recursive call
                storeI   ToS     / (then increment ToS)
                load     ToS
                add      Incr
                store    ToS
                load     Sum     / push return addr onto stack so we can get it back after call
                storeI   ToS     / (then increment ToS)
                load     ToS
                add      Incr
                store    ToS
                load     SumN    / compute and push N-1 onto stack for param
                subt     Incr    / (then increment ToS)
                storeI   ToS
                load     ToS
                add      Incr
                store    ToS
                JnS Sum          / call sum(N-1)
                load     ToS     / pop result off stack
                subt     Incr    / (after decrementing ToS)
                store    ToS
                loadI    ToS
                store    SumR
                load     ToS     / pop our stored return addr off stack
                subt     Incr    / (after decrementing ToS)
                store    ToS
                loadI    ToS
                store    Sum
                load     ToS     / pop our stored N off stack
                subt     Incr    / (after decrementing ToS)
                store    ToS
                loadI    ToS
                store    SumN
                add      SumR    / compute result = N + result
                store    SumR
    
    Return,     load     SumR    / push result onto stack
                storeI   ToS     / (then increment ToS)
                load     ToS
                add      Incr
                store    ToS
                JumpI Sum        / return
    
    SumR,       hex     0        / local result within Sum
    SumN,       hex     0        / local N within Sum
    Incr,       hex     1        / used for ++, --
    Stack,      hex     43       / base of stack
    ToS,        hex     43       / top element on stack
    
    

    Example 9: self modifying code
    A simple program that overwrites part of its own code as it runs, changing the instructions inside a function then calling the modified function.

    marie file

        / self modifying program:
        /      The foo() function, as defined, prints the value of x.
        /      However, the first two lines of main actually overwrite
        /         part of foo so that it computes and prints x+x instead
        /         of computing and printing 0+x
        /      main calls the modified function to test the results
    
    main,      load instr  / get the new instruction (load x)
               storei addr / overwrite the clear instruction (at addr 7)
               jns foo     / run the modified function, should print 2*x
               halt
    addr,      hex 7
    instr,     hex 100B    / new instruction will be "load x"
    
    foo,       hex 0       / void foo() {
               clear       /    acc = 0;
               add x       /    acc = acc + x;
               output      /    cout << acc;  // i.e. prints x
               jumpi foo   /    return
    x,         hex 5       / }