CS 254 - Computer organization and assembly language programming

Spring/2002

Classes: TR 05:15-06:30 p.m., Maria Sanford  221
Instructor: Dr. Zdravko Markov, MS 203, (860)-832-2711, http://www.cs.ccsu.edu/~markov/, e-mail: markovz@ccsu.edu
Office hours: TR 8:00pm-9:00pm., MW 6:30pm-8:00pm, or by appointment

Catalog data: Prereq.: CS 151 or MATH 471. Concepts of assembler language, machine language, macro-instructions, subroutines, program checkout, interrupt structure of assemblers and use of operating system. No credit given to students with credit for MATH 472. [c]

Prerequisites: CS 151 or MATH 471.

Description: This course is an introduction to computer architecture at the assembly language level. The course is based on the MIPS processor, a simple clean RISC processor whose architecture is easy to learn and understand. The course covers binary representation, elements of machine organization, machine language, MIPS assembly language programming, subroutines, interrupts, and basics of operating systems.

Class Participation: Active participation in class is expected of all students. Regular attendance is also expected. If you must miss a test, try to inform the instructor of this in advance.

Honesty policy: It is expected that all students will conduct themselves in an honest manner (see the CCSU Student handbook), and NEVER claim work which is not their own.  Violating this policy will result in a substantial grade penalty, and may lead to expulsion from the University.  However, students are allowed to discuss projects with others and receive debugging help from others.

Programming: This course teaches assembly programming on a simulator (called SPIM). This is a MIPS machine simulator available as a free software for Unix, DOS, and Windows. There will be 5 programming assignments requiring the use of the SPIM simulator.

Tests: There will be two midterm exams and a final. They will include questions from the textbook, questions from the lectures, and questions from the assignments.

Required textbook: John Waldron, Introduction to RISC Assembly Language Programming, Addison-Wesley, 1999, ISBN 0-201-39828-1.

Required software: SPIM simulator: A free software simulator for running MIPS R2000 assembly language programs available for Unix, DOS, and Windows.

WEB resources:

  • Author's web page of Introduction to RISC Assembly Language Programming: Example programs, lecture slides and other resources
  • Publisher's Web page of  Introduction to RISC Assembly Language Programming, Addison-Wesley.
  • SPIM simulator: A free software simulator for running MIPS R2000 assembly language programs available for Unix, DOS, and Windows.
  • Documentation for the Windows interface to SPIM: postscript or Adobe PDF file.
  • Assemblers, Linkers, and the SPIM Simulator (Adobe PDF file): Appendix A of Hennessy & Patterson, Computer Organization and Design: The Hardware/Software Interface, Second Edition, Morgan Kaufmann Publishers, Inc., 1997.
  • VAX instruction set (Adobe PDF file)
  • MIPS Web Site
  • Ghostscript, Ghostview and GSview
  • Postscript to PDF Converter
  • Grading:

    Grading will be based on three tests (two midterms and a final), 2 assignments and 4 programming projects (see the schedule below for the corresponding point grades). The letter grades will be calculated according to the following table:
     
    A A- B+ B B- C+ C C- D+ D D- F
    95-100 90-94 87-89 84-86 80-83 77-79 74-76 70-73 67-69 64-66 60-63 0-59

    Tentative schedule of classes, assignments and tests:

    1. Computer architecture = Instruction set architecture + Machine organization. Read Ch. 1.
    2. Representing information in computers: number systems, bits, bytes, binary numbers, characters. Read Ch. 2.
    3. Representing numbers in computers: integers and floating point numbers. Computer arithmetic.
    4. MIPS computer organization and the SPIM simulator. Read Ch. 3.
    5. Assignment 1 due (5 pts.). MIPS assembly language programming: syntax and semantics. Read Sections 4.1 - 4.3.
    6. Executing an assembly language program in SPIM: edit, assemble and test cycle. Read Section 4.4.
    7. I/O - read and print numbers: overflow, underflow and range of the numbers in MIPS.
    8. Load, store, move. Read Section 4.5.
    9. Pseudo-instructions. Integer arithmetic. Read Sections 4.6 - 4.9.
    10. Assignment 2 due (5 pts.). More integer arithmetic: convert string to integer and random number generator.
    11. Test 1 (15 pts.): Load, store, move, integer arithmetic, floating point representation (IEEE 754 floating point format).
    12. Control flow structures - branches: leap year example. Read Sections 5.1 - 5.3.
    13. Control flow structures - loops: Euclid's algorithm and string length. Read Sections 5.4 - 5.5.
    14. Using random numbers: Monte Carlo estimation of PI.
    15. Project 1 due (10 pts.). Addressing modes. Implementing arrays. Read Ch. 6.1 - 6.6.
    16. Minimal and maximal element of an array. Read Section 6.7.
    17. Sorting arrays (bubble sort).
    18. Indexed addressing: string manipulation. Read Ch. 6.8 - 6.10.
    19. Project 2 due (10pts.). Logical, shift and rotate instructions: convert integer to bin and hex by using a mask. Read Ch. 7.
    20. Implementing sets by logical instructions.
    21. Using sets: Prime numbers - the sieve of Eratosthenes.
    22. Test 2 (15pts.): Loops and arrays.
    23. Project 3 due (10pts.). Stacks: reversing a character string and reverse polish calculator. Read Sections 8.1 - 8.2
    24. Procedure calls and parameter passing. Read Section 8.1 - 8.5.
    25. Stack frames. Factorial function. Sorting strings by selection sort. Read Section 8.6 - 8.7, Assemblers, Linkers, and the SPIM Simulator.
    26. Linked lists.
    27. Recursive programming: binary trees.
    28. Project 4 due (10pts.). Exceptions and interrupts.
    29. Test 3 (20 pts.): Procedures, and linked lists.

    CS 254 - Class #1

    Computer architecture = Instruction set architecture + Machine organization
    1. Levels of abstraction in describing computers
    2. Computer architecture = Instruction set architecture + Machine organization
    3. Instruction set – the software hardware interface
    4. Levels of computer architecture in more depth
    5. Basic components of the computer
    6. Stored program concept: programs and data, fetch&execute cycle
    Lecture slides (Postscript)

    CS 254 - Class #2

    Representing information in computers
    1. Bits, bytes, words and memory organization
    2. Number systems
    3. Binary and hexadecimal numbers, conversions
    4. Representing textual information - character encoding, lexicographic order.
    Lecture slide (Postscript)

    CS 254 - Class #3

    Representing numbers in computers
    1. Unsigned integers
    2. Signed numbers, two's complement representation, range of integers
    3. Integer arithmetic
    4. Floating point numbers
    Lecture slides (Postscript)

    CS 254 - Class #4

    MIPS computer organization and the SPIM simulator
    1. MIPS processor:
    2. MIPS instruction set (RISC processor), addressing modes:
    3. Memory organization and register usage convention
    4. The SPIM simulator
    Lecture slides (Postscript)

    CS 254 - Class #5

    MIPS assembly language programming
    1. Structure of the program (data segment, text segment)
    2. MIPS assembler syntax (Assemblers, Linkers, and the SPIM Simulator, pages 49-53):
    Lecture slides (Postscript)

    CS 254 - Class #6

    Executing an assembly language program in SPIM
    1. Starting PCSpim: settings
    2. Loading and executing a program
    3. Edit, assemble and test cycle:
    4. The "hello world" program (hello.a)
    # a program that prints "hello world"

             .text
             .globl __start
    __start:
             la $a0, str
             li $v0, 4
             syscall
             li $v0, 10
             syscall

             .data
    str:     .asciiz "hello world\n"

    Lecture slides (Postscript)


    CS 254 - Class #7

    I/O - read and print numbers: overflow, underflow and range of the numbers in MIPS

    1. Read and print integers: overflow and range of the integers

    1.1. The program (slides in Postscript)

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, Ask
             syscall              # Print a prompt

             li $v0, 5
             syscall              # read an integer

    #        add $s0, $v0, $v0    # $s0 = $v0 + $v0 (an overflow may occur here)
             addu $s0, $v0, $v0   # $s0 = $v0 + $v0 (no overflow)

             li $v0, 4
             la $a0, Result
             syscall

             add $a0, $0, $s0     # $a0 = $s0
             li $v0, 1            # Print $a0
             syscall

             li $v0, 4
             la $a0, nl
             syscall              # Print new line

             j __start            # Jump to __start (press Ctrl-C for exit)

             .data
    nl:      .asciiz "\n"
    Ask:     .asciiz "\nEnter an integer number: "
    Result:  .asciiz "This number multiplied by 2 is "

    1.1. Example run (explain the results)

    Enter an integer number: 2
    This number multiplied by 2 is 4

    Enter an integer number: 1073741823
    This number multiplied by 2 is 2147483646

    Enter an integer number: 1073741824
    This number multiplied by 2 is -2147483648 (wrong result or overflow)

    2. Read and print floating point numbers: overflow and underflow

    2.1. The program

             .text
             .globl __start

    __start:  li $v0, 4
             la $a0, Ask
             syscall

             li $v0, 6
             syscall           # read a floating point number

             li $v0, 4
             la $a0, Float
             syscall

             mov.s $f12, $f0   # move the content of $f0 to $f12
             li $v0, 2         # print a floating point number
             syscall

             li $v0, 4
             la $a0, nl
             syscall

             li $v0, 4
             la $a0, Integer
             syscall

             s.s $f0, Num      # Num = $f0
             lw $a0, Num      # $a0 = Num
             li $v0, 1         # print the number as integer
             syscall

             li $v0, 4
             la $a0, nl
             syscall

             j __start         # jump to __start (Press Ctrl-C for exit)

             .data
    Num:     .word 0
    Ask:     .asciiz "\nEnter a floating point number: "
    Float:   .asciiz "Floating point: "
    Integer: .asciiz "Integer: "
    nl:      .asciiz "\n"

    2.2. Example run (explain the results)

    Enter a floating point number: 0
    Foating point: 0.000000
    Integer: 0

    Enter a floating point number: -0
    Foating point: 0.000000
    Integer: -2147483648

    Enter a floating point number: 1
    Foating point: 1.000000
    Integer: 1065353216

    Enter a floating point number: -1
    Foating point: -1.000000
    Integer: -1082130432

    Enter a floating point number: 1e38
    Foating point: 99999996802856925000000000000000000000.000000
    Integer: 2123789977

    Enter a floating point number: 1e39
    Foating point: 1.#INF00
    Integer: 2139095040

    Enter a floating point number: 1e-45
    Foating point: 0.000000
    Integer: 1

    Enter a floating point number: 1e-46
    Foating point: 0.000000
    Integer: 0


    CS 254 - Class #8

    Load and Store: 256-numbering system

    1. Converting a decimal into 256-numbering system

    1.1. The Program

    # Input a number into a four-bytes word and print the individual bytes
    # The program runs into an infinite loop. Press Ctrl-C for exit.

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, Prompt
             syscall            # Print a promt
             li $v0, 5
             syscall            # Read an integer into word A
             sw $v0, A

             lbu $a0, A
             li $v0, 1
             syscall            # Print the first byte of A
             li $v0, 4
             la $a0, B0
             syscall            # Print the string " * 256^0 + "

             lbu $a0, B
             li $v0, 1
             syscall            # Print the second byte of A
             li $v0, 4
             la $a0, B1
             syscall            # Print the string " * 256^1 + "

             lbu $a0, C
             li $v0, 1
             syscall            # Print the third byte of A
             li $v0, 4
             la $a0, B2
             syscall            # Print the string " * 256^2 + "

             lbu $a0, D
             li $v0, 1
             syscall            # Print the fourth byte of A
             li $v0, 4
             la $a0, B3
             syscall           # Print the string " * 256^3\n"

             j __start          # jump to __start

             .data
    A:       .byte 0
    B:       .byte 0
    C:       .byte 0
    D:       .byte 0
    B0:      .asciiz " * 256^0 + "
    B1:      .asciiz " * 256^1 + "
    B2:      .asciiz " * 256^2 + "
    B3:      .asciiz " * 256^3\n"
    Prompt:  .asciiz "Enter a number: "

    1.2. Example run

    Enter a number: 255
    255 * 256^0 + 0 * 256^1 + 0 * 256^2 + 0 * 256^3
    Enter a number: 256
    0 * 256^0 + 1 * 256^1 + 0 * 256^2 + 0 * 256^3
    Enter a number: 65535
    255 * 256^0 + 255 * 256^1 + 0 * 256^2 + 0 * 256^3
    Enter a number: 65536
    0 * 256^0 + 0 * 256^1 + 1 * 256^2 + 0 * 256^3
    Enter a number: -1
    255 * 256^0 + 255 * 256^1 + 255 * 256^2 + 255 * 256^3
    Enter a number: 2147483647
    255 * 256^0 + 255 * 256^1 + 255 * 256^2 + 127 * 256^3
    Enter a number: 2147483648
    0 * 256^0 + 0 * 256^1 + 0 * 256^2 + 128 * 256^3
    Enter a number: -2147483648
    0 * 256^0 + 0 * 256^1 + 0 * 256^2 + 128 * 256^3

    2. Converting to decimal a number in 256 numbering system

    2.1. The Program

    # Input A,B,C,D and print the value of A*256^0+B*256^1+C*256^2+D*256^3
    # The program runs into an infinite loop. Press Ctrl-C for exit.

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, LA
             syscall

             li $v0, 5        # read A
             syscall
             sb $v0, A        # store A in byte 0

             li $v0, 4
             la $a0, LB
             syscall

             li $v0, 5        # read B
             syscall
             sb $v0, B        # store B in byte 1

             li $v0, 4
             la $a0, LC
             syscall

             li $v0, 5        # read C
             syscall
             sb $v0, C        # store C in byte 2

             li $v0, 4
             la $a0, LD
             syscall

             li $v0, 5        # read D
             syscall
             sb $v0, D        # store D in byte 3

             li $v0, 4
             la $a0, Result   # Print the string "A * 256^0 + B * 256^1 + C * 256^2 + D * 256^3 = "
             syscall

             lw $a0, A        # print the word: byte0, byte1, byte2, byte3
             li $v0, 1
             syscall

             li $v0, 4
             la $a0, nl
             syscall

             j __start        # jump to __start

             .data
    A:       .byte 0
    B:       .byte 0
    C:       .byte 0
    D:       .byte 0
    LA:      .asciiz "A="
    LB:      .asciiz "B="
    LC:      .asciiz "C="
    LD:      .asciiz "D="
    Result:  .asciiz "A * 256^0 + B * 256^1 + C * 256^2 + D * 256^3 = "
    nl:      .asciiz "\n"

    2.2. Example run

    A=255
    B=255
    C=255
    D=127
    A * 256^0 + B * 256^1 + C * 256^2 + D * 256^3 = 2147483647
    A=255
    B=255
    C=255
    D=128
    A * 256^0 + B * 256^1 + C * 256^2 + D * 256^3 = -2130706433
    A=0
    B=0
    C=0
    D=256
    A * 256^0 + B * 256^1 + C * 256^2 + D * 256^3 = 0
    A=0
    B=0
    C=0
    D=255
    A * 256^0 + B * 256^1 + C * 256^2 + D * 256^3 = -16777216


    CS 254 - Class #9

    Integer arithmetic: convert Celsius to Fahrenheit

    ##  temp.a ask user for temperature in Celsius,
    ##  convert to Fahrenheit, print the result.
    ##
    ##      v0 - reads in celsius
    ##      t0 - holds Fahrenheit result
    ##      a0 - points to output strings
    ##
    #################################################
    #               text segment                    #
    #################################################

            .text
            .globl __start
    __start:
            la $a0,prompt   # print prompt on terminal
            li $v0,4
            syscall

            li $v0,5        # syscall 5 reads an integer
            syscall

    # We use here two pseudo-instructions - mul and div
            mul $t0,$v0,9   # to convert,multiply by 9,
            div $t0,$t0,5   # divide by 5,then
            add $t0,$t0,32  # add 32

            la $a0,ans1     # print string before result
            li $v0,4
            syscall

            move $a0,$t0    # print  result
            li $v0,1
            syscall

            la $a0,endl     # system call to print
            li $v0,4        # out a newline
            syscall

            li $v0,10
            syscall         # au revoir...

    #################################################
    #               data segment                    #
    #################################################

            .data
    prompt: .asciiz "Enter temperature (Celsius): "
    ans1:   .asciiz "The temperature in Fahrenheit is "
    endl:   .asciiz "\n"


    CS 254 - Class #10

    Convert String to integer

    # Convert a 3-digit decimal string into an integer

             .text
             .globl __start

    __start: la $t0, Num

             lb $v0, 2($t0)       # load the ascii code of digit 0
             addi $v0, $v0, -48   # get the value of digit 0
             add $v1, $0, $v0     # add to the total

             lb $v0, 1($t0)       # load the ascii code of digit 1
             addi $v0, $v0, -48   # get the value of digit 1
             mul $v0, $v0, 10     # multiply by 10
             add $v1, $v1, $v0    # add to the total

             lb $v0, 0($t0)       # load the ascii code of digit 2
             addi $v0, $v0, -48   # get the value of digit 1
             mul $v0, $v0, 100    # multiply by 10
             add $v1, $v1, $v0    # add to the total

             sw $v1, Value        # store the total

            .data
    Num:    .asciiz "256"
    Value:  .word 0

    Random number generator

    #  Random number generator
    #  seed:=(x*seed+y) mod z
    #  Prints an infinite sequence of pseudo-random numbers (press Ctrl-C for exit)

             .text
             .globl __start

    __start: lw $t0, x             # $t0 = x
             lw $t1, seed
             mul $t0, $t0, $t1     # $t0 = x*seed
             lw $t1, y
             add $t0, $t0, $t1     # $t0 = x*seed+y
             lw $t1, z
             div $t0, $t1          # hi = (x*seed+y) mod z
             mfhi $a0              # $a0 = hi
             sw $a0, seed          # seed = $a0
             li $v0, 1
             syscall               # print seed

             li $v0, 4
             la $a0, nl
             syscall               # print new line

             b __start             # goto to __start (set a breakpoint here)

            .data
    x:      .word 31              # an arbitrary constant
    y:      .word 23               # an arbitrary constant
    z:      .word 10000            # the range of random rumbers [0,9999]
    seed:   .word 0                # the initial seed is 0
    nl:     .asciiz "\n"


    CS 254 - Class #11

    Control flow structures - branches: leap year example (draw a flowchart)

    #  Check for leap year
    #  In Gregorian Calendar: "A year is a leap year if it is divisible by 4 with
    #  the exception of century years that are not divisible by 400"
    #  That is: if (Year mod 4 <> 0) then Ordinary
    #           else if (Year mod 100 = 0) and (Year mod 400 <> 0) then Ordinary
    #           else Leap

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, Prompt
             syscall                # Print a prompt

             li $v0, 5
             syscall                # Read an integer
             sw $v0, Year           # and store it in Year

    #  if (Year mod 4 <> 0) then go to Ordinary

             lw $t0, Year
             li $t1, 4
             div $t0, $t1            # hi = year mod 4
             mfhi $t1                # $t1 = hi
             bne $t1, $0, Ordinary   # if $t1 <> 0 go to Ordinary

    # if (Year mod 100 = 0) and (year mod 400 <> 0) then go to Ordinary

    # if (Year mod 100 <> 0) then go to Leap

            li $t1, 100
            div $t0, $t1             # hi = year mod 100
            mfhi $t1                 # $t1 = hi
            bne $t1, $0, Leap        # if $t1 <> 0 go to Leap

    # if (Year mod 400 <> 0) then go to Ordinary

              li $t1, 400
              div $t0, $t1           # hi = year mod 400
              mfhi $t1               # $t1 = hi
              bne $t1, $0, Ordinary  # if $t1 <> 0 go to Ordinary

    Leap:     lw $a0, Year           # Leap year
              li $v0, 1
              syscall               # Print Year
              li $v0, 4
              la $a0, LeapMess
              syscall                # Print " is a leap year\n"
              b End                  # go to End

    Ordinary: lw $a0, Year           # Ordinary year
              li $v0, 1
              syscall                # Print Year
              li $v0, 4
              la $a0, OrdMess
              syscall                # Print " is an ordinary year\n"

    End:      b __start              # go to __start (read another year)

              .data
    Year:     .word 0
    Prompt:   .asciiz "Enter year: "
    LeapMess: .asciiz " is a leap year\n"
    OrdMess:  .asciiz " is an ordinary year\n"


    CS 254 - Class #12

    Control flow structures - loops

    1. Euclid's algorithm. See an applet implementation of Euclid here. More about Euclid can be found here.

    #  Calculate the Greatest Common Divisor (GCD) or two integers
    #  according to the Euclid's algorithm

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, First
             syscall                # Ask for the first integer

             li $v0, 5
             syscall                # Read an integer
             add $t0, $0, $v0       # and store it in $t0

             li $v0, 4
             la $a0, Second
             syscall                # Ask for the second integer

             li $v0, 5
             syscall                # Read an integer
             add $t1, $0, $v0       # and store it in $t1

    # Include here one of the following two versions

    # Version 1: based on integer division

    loop:    div $t0, $t1
             mfhi $t2               # $t2 = $t0 mod $t1
             add $t0, $0, $t1       # $t0 = $t1
             add $t1, $0, $t2       # $t1 = $t2
             bne $t1, $0, loop

    # Version 2: based on subtract

    #loop:    beq $t0, $t1, exit     # if the numbers are equal then exit
    #         bgt $t0, $t1, skip     # subtract the smaller from the bigger
    #         sub $t1, $t1, $t0      # and replace the bigger with the result
    #         b loop                 # then continue
    #skip:    sub $t0, $t0, $t1
    #         b loop

    # end of inclusion

    exit:    li $v0, 4
             la $a0, Ans
             syscall                # Print "The GCD is: "

             add $a0, $0, $t0
             li $v0, 1
             syscall                # Print GCD

             li $v0, 4
             la $a0, nl
             syscall                # Print new line

             b __start              # Go to __start (Press Ctrl-C for exit)

             .data
    First:   .asciiz "Calculating GCD of two integers.\nEnter first integer: "
    Second:  .asciiz "Enter second integer: "
    Ans:     .asciiz "Their GCD is: "
    nl:      .asciiz "\n\n"

    2. Calculating string length

    ## length.a - prints out the length of character
    ## string "str".
    ##
    ##      t0 - holds each byte from string in turn
    ##      t1 - contains count of characters
    ##      t2 - points to the string
    ##
    #################################################
    #               text segment                    #
    #################################################

            .text
            .globl __start
    __start:                # execution starts here
            la $t2,str      # t2 points to the string
            li $t1,0        # t1 holds the count
    nextCh: lb $t0,($t2)    # get a byte from string
            beqz $t0,strEnd # zero means end of string
            add $t1,$t1,1   # increment count
            add $t2,1       # move pointer one character
            j nextCh        # go round the loop again

    strEnd: la $a0,ans      # system call to print
            li $v0,4        # out a message
            syscall

            move $a0,$t1    # system call to print
            li $v0,1        # out the length worked out
            syscall

            la $a0,endl     # system call to print
            li $v0,4        # out a newline
            syscall

            li $v0,10
            syscall         # au revoir...

    #################################################
    #               data segment                    #
    #################################################

            .data
    str:    .asciiz "hello world"
    ans:    .asciiz "Length is "
    endl:   .asciiz "\n"


    CS 254 - Class #14

    Monte Carlo estimation of PI

    #  Generate two random numbers as X and Y coordinates of a point:
    #  ($f1, $f2) in [-1,1] X [-1,1]
    #  Then count the points which fall within the unit circle ($f1^2 + $f2^2 <= 1).
    #  Pi is the quotient of this number and the total number of points generated
    #  multiplied by 4.

            .text
            .globl __start

    __start:

    #--- Initialize counters --------------------------------------------------

             lw $s0, n           # n is the number of points generated
             li $s1, 0           # $s1 counts the points inside the unit circle

    loop:

    #--- Generate a random value (float in [-1,1]) and store it in $f1 --------

             lw $t0, x           # $t0 = x
             lw $t1, seed
             mul $t0, $t0, $t1   # $t0 = x*seed
             lw $t1, y
             addu $t0, $t0, $t1  # $t0 = x*seed+y
             lw $t1, z
             div $t0, $t1        # hi = (x*seed+y) mod z
             mfhi $t1            # $t1 = hi
             sw $t1, seed        # store the new value in seed

             l.s $f1, seed
             cvt.s.w $f1, $f1    # covert integer into float, $f1 = seed

             l.s $f0, z
             cvt.s.w $f0, $f0    # convert integer to float, $f0=z
             div.s $f1, $f1, $f0 # normalize $f1, i.e. $f1 in [0,1]

             add.s $f1, $f1, $f1 # $f1 = $f1*2
             l.s $f0, one        # $f0 = 1.0
             sub.s $f1, $f1, $f0 # $f1 = $f1-1, $f1 in [-1,1]

    #---------------------------------------------------------------------------

             mov.s $f2, $f3      # Put the previous value ($f3) in $f2
             mov.s $f3, $f1      # Store the current one ($f1) in $f3

    #--- $f1 = $f1^2 + $f2^2 ---------------------------------------------------

             mul.s $f1, $f1, $f1 # $f1=$f1^2
             mul.s $f2, $f2, $f2 # $f2=$f2^2
             add.s $f1, $f1, $f2 # $f1=$f1+$f2

    #--- $f1^2 + $f2^2 <= 1 (compare floating point values using integers) -----

             s.s $f1, temp
             lw $t2, temp        # $t2 (integer) = $f1 (float)
             lw $t1, one         # $t1 (integer) = 1.0 (float)

             slt $t0, $t1, $t2
             bne $t0, $0, skip
             addi $s1, $s1, 1
    skip:    addi $s0, $s0, -1
             bne $s0, $0, loop

    # calculate PI = (# of points inside circle) * 4 / n  ----------------------

             add $s1, $s1, $s1   # $s1 = $s1*4
             add $s1, $s1, $s1
             sw $s1, temp
             l.s $f12, temp
             cvt.s.w $f12, $f12
             l.s $f0, n
             cvt.s.w $f0, $f0
             div.s $f12, $f12, $f0

             li $v0, 2
             syscall             # Print the value of Pi

             li $v0, 4
             la $a0, bye         # Print the end message
             syscall
             li $v0, 5
             syscall             # wait for Enter
             li $v0, 10
             syscall             # end of program

    #--------------------------------------------------------------------------
            .data
    x:      .word 311
    y:      .word 171
    z:      .word 65536
    n:      .word 10000
    one:    .float 1.0
    seed:   .word 79
    temp:   .word 0
    bye:    .asciiz "\nPress enter to exit..."


    CS 254 - Class #15

    Implementing arrays

    #  Read and print a sequence of numbers by using arrays.
    #  Questions (memory organization):
    #  1. What hapens if we enter more than 10 numbers (the array has 10 elements)
    #  2. What about moving the array at the end of the data segment?

             .text
             .globl __start

    __start: la $s0, array       # set $s0 to point array[0]
             li $s1, 0           # $s1 = 0 (for counting the array elements)

    loop1:   li $v0, 4
             la $a0, prompt
             syscall             # Print the prompt
             li $v0, 5
             syscall             # Read an integer in $v0
             lw $t0, endmark
             beq $v0, $t0, exit  # if $v0 = endmark then exit loop
             sw $v0, 0($s0)      # store $v0 into the current element
             addi $s0, $s0, 4    # move to the next element
             addi $s1, $s1, 1    # increment the counter
             b loop1

    exit:    li $v0, 4
             la $a0, res
             syscall

             add $a0, $0, $s1
             li $v0, 1
             syscall             # Print the number of elements entered

             li $v0, 4
             la $a0, el
             syscall

             la $s0, array       # set $s0 to point to array[0]

    loop2:   lw $a0, 0($s0)      # $a0 = current element
             li $v0, 1
             syscall             # Print $a0
             li $v0, 4
             la $a0, nl
             syscall
             add $s0, $s0, 4     # move to the next element
             addi $s1, $s1, -1   # decrement element counter
             bne $s1, $0, loop2

             li $v0, 4
             la $a0, bye         # Print the end message
             syscall
             li $v0, 5
             syscall             # wait for Enter

             li $v0, 10
             syscall             # end of program

             .data
    array:   .word 0,0,0,0,0,0,0,0,0,0
    prompt:  .asciiz "Enter an integer (-999 for exit): "
    endmark: .word -999
    res:     .asciiz "You have entered "
    el:      .asciiz " numbers:\n"
    bye:     .asciiz "Press enter to exit..."
    nl:      .asciiz "\n"
    # array: .word 0,0,0,0,0,0,0,0,0,0


    CS 254 - Class #16

    Using arrays: minimal and maximal element

    #  Read an array of numbers and find the minimal and maximal elements

             .text
             .globl __start

    __start:  la $s0, array         # set $s0 to point array[0]
              li $s1, 0             # $s1 = 0 (for counting the array elements)

    loop1:    li $v0, 4
              la $a0, ask
              syscall               # Ask for a number
              li $v0, 5
              syscall               # Read an integer in $v0
              lw $t0, endmark
              beq $v0, $t0, exit    # if $v0 = endmark then exit loop
              sw $v0, 0($s0)        # store $v0 into the current element of the array
              addi $s0, $s0, 4      # move to the next element
              addi $s1, $s1, 1      # increment the counter
              b loop1

    exit:    li $v0, 4
             la $a0, res            # Print "You have entered "
             syscall

             add $a0, $0, $s1
             li $v0, 1
             syscall                # Print the number of elements entered

             li $v0, 4
             la $a0, numb           # Print " numbers.\n"
             syscall

             la $s0, array          # set $s0 to point to array[0]
             lw $t0, 0($s0)         # initialize min ($t0) to array[0]
             lw $t1, 0($s0)         # initialize max ($t1) to array[0]

    loop2:   lw $t3, 0($s0)         # $t3 = current element

             bge $t3, $t0, notmin   # skip if current element >= min
             add $t0, $0, $t3       # update min ($t0)

    notmin:  ble $t3, $t1, notmax   # skip if current element <= max
             add $t1, $0, $t3       # update max ($t1)

    notmax:  add $s0, $s0, 4        # move to the next element
             addi $s1, $s1, -1      # decrement element counter
             bne $s1, $0, loop2

             li $v0, 4
             la $a0, min            # Print "Minimal number = "
             syscall

             add $a0, $0, $t0
             li $v0, 1              # Print the value of min
             syscall

             li $v0, 4
             la $a0, nl
             syscall
     

             li $v0, 4
             la $a0, max            # Print "Maximal number = "
             syscall

             add $a0, $0, $t1
             li $v0, 1              # Print the value of max
             syscall

             li $v0, 4
             la $a0, nl
             syscall

             li $v0, 4
             la $a0, bye            # Print the end message
             syscall
             li $v0, 5
             syscall               # wait for Enter

             li $v0, 10
             syscall                # end of program

             .data
    ask:     .asciiz "Enter an integer (-999 for exit): "
    endmark: .word -999
    res:     .asciiz "You have entered "
    numb:    .asciiz " numbers.\n"
    min:     .asciiz "Minimal number = "
    max:     .asciiz "Maximal number = "
    bye:     .asciiz "Press enter to exit..."
    nl:      .asciiz "\n"
    array:   .word 0                # the array starts here


    CS 254 - Class #17

    Sorting arrays

    #  Bubble sort
    #  Repeatedly swapping pairs of wrongly ordered elements until
    #  all pairs are correctly ordered.

             .text
             .globl __start

    __start: la $s0, array          # set $s0 to point array[0]
             li $s1, 0              # $s1 = 0 (for counting the array elements)

    #  Read in the array elements

    loop1:   li $v0, 4
             la $a0, ask
             syscall                # Ask for a number
             li $v0, 5
             syscall                # Read an integer in $v0
             lw $t0, endmark
             beq $v0, $t0, loop2    # if $v0 = endmark then exit loop
             sw $v0, 0($s0)         # store $v0 into the current element of the array
             addi $s0, $s0, 4       # move to the next element
             addi $s1, $s1, 1       # increment the counter
             b loop1

    # Sort the array by using the bubble sort algorithm

    loop2:  la $s0, array           # set $s0 to point to array[0]
            add $s2, $0, $s1        # $s2 = $s1 (the number of elements)
            add $s2, $s2, -1        # number of swaps = number of elements - 1
            add $t3, $0, $0         # number of swaps ($t3) = 0

    loop3:  lw $t0, 0($s0)          # $t0 = current element
            lw $t1, 4($s0)         # $t1 = next element
            slt $t2, $t1, $t0       # if $t1 < $t0 then $t2 = 1
            beq $t2, $0, skip       # if $t2 = 0 the go to skip

            sw $t0, 4($s0)          # swap the current element and
            sw $t1, 0($s0)          # the next element
            addi $t3, $t3, 1        # increment $t3 (number of swaps)

    skip:   add $s0, $s0, 4         # move to the next element
            addi $s2, $s2, -1       # decrement the element counter
            bgt $s2, $0, loop3      # if $s2 > 0 then go to loop3

            bne $t3, $0, loop2      # if number of swaps > 0 then go to loop2

    # Print the sorted array

             li $v0, 4
             la $a0, sorted         # Print "Sorted: "
             syscall
             la $s0, array
    loop4:   lw $a0, 0($s0)
             li $v0, 1
             syscall
             li $v0, 4
             la $a0, nl
             syscall
             add $s0, $s0, 4
             addi $s1, $s1, -1
             bne $s1, $0, loop4

             li $v0, 4
             la $a0, bye            # Print the end message
             syscall
             li $v0, 5
             syscall                # wait for Enter
             li $v0, 10
             syscall                # end of program

             .data
    ask:     .asciiz "Enter an integer (-999 for exit): "
    endmark: .word -999
    sorted:  .asciiz "Sorted:\n"
    bye:     .asciiz "Press enter to exit..."
    nl:      .asciiz "\n"
    array:   .word 0                # the array starts here


    CS 254 - Class #18

    Indexed addressing: using a pseudo-insturction with base addressing

    1. Counting occurrences of a character in a string

    ## count.a - count the occurrences of a specific
    ## character in string "str".
    ## Indexed addressing used to access array elements.
    ##
    ##      t0 - holds each byte from string in turn
    ##      t1 - index into array
    ##      t2 - count of occurences
    ##      t3 - holds the character to count
    ##

    #################################################
    #               text segment                    #
    #################################################

            .text
            .globl __start
    __start:
            li $t1,0        # $t1 will be the array index
            li $t2,0        # $t2 will be the counter
            lb $t3,char     # and $t3 will hold the char

    loop:   lb $t0,str($t1) # fetch next char
            beqz $t0,strEnd # if it's a null, exit loop
            bne $t0,$t3,con # not null; same as char?
            add $t2,$t2,1   # yes,increment counter
    con:    add $t1,$t1,1   # increase index
            j loop          # and continue

    strEnd:
            la $a0,ans      # system call to print
            li $v0,4        # out a message
            syscall

            move $a0,$t2    # system call to print
            li $v0,1        # out the count worked out
            syscall

            la $a0,endl     # system call to print
            li $v0,4        # out a newline
            syscall

            li $v0,10
            syscall         # au revoir...

    #################################################
    #               data segment                    #
    #################################################

            .data
    str:    .asciiz "abceebceebeebbacacb"
    char:   .asciiz "e"
    ans:    .asciiz "Count is "
    endl:   .asciiz "\n"

    ##
    ## end of file count.a

    2. Reading and copying strings

    #  Reading and copying a string of characters
    #  Converting lower case to upper case

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, ask          # Print "Type a character string: "
             syscall

             la $a0, buffer       # $a0 holds the address of the read buffer
             lw $a1, maxlen       # Max number of chars (including the end of string char)
             li $v0, 8            # Load the service number
             syscall              # Call the operating system

    # Copy the buffer into str and replace lower case letters with upper case letters

             li $t2, 97           # the ASCII code of "a"
             li $t3, 122          # the ASCII code of "z"
             li $t0, 0            # $t0 is the index
    loop:    lb $t1, buffer($t0)  # fetch a char from the buffer
             blt $t1, $t2, skip   # the char is before "a", skip it
             bgt $t1, $t3, skip   # the char is after "z", skip it
             addi $t1, $t1, -32   # convert to upper case
    skip:    sb $t1, str($t0)     # and store it into str
             addi $t0, $t0, 1     # increment index
             bne $t1, $0, loop    # if $t1 <> "end of string" then goto loop

             li $v0, 4
             la $a0, str          # Print str
             syscall

             li $v0, 4
             la $a0, bye          # Print the end message
             syscall
             li $v0, 5
             syscall              # wait for Enter
             li $v0, 10
             syscall              # end of program

             .data
    ask:     .asciiz "Type a character string (<31 chars long): "
    bye:     .asciiz "Press enter to exit..."
    nl:      .asciiz "\n"
    maxlen:  .word 31
    buffer:  .space 31            # allocates 31 bytes of memory in the data segment
    str:     .space 31


    CS 254 - Class #19

    Logical, shift and rotate instructions
     

    1. Convert integer to binary

    # Convert integer to binary
    # Print the binary digits as integers and
    # Convert to string, print the result.

            .text
            .globl __start
    __start:
            la $a0,prompt    # print prompt on terminal
            li $v0,4
            syscall

            li $v0,5         # syscall 5 reads an integer
            syscall
            move $t2,$v0     # $t2 holds hex number

            la $a0,ans1      # print string before result
            li $v0,4
            syscall

            li $t4, 4        # for printing blank after 4 digits

            li $t0, 32       # 32 bits in word
            la $t3,result    # answer string set up here

    loop:   rol $t2,$t2,1    # start with leftmost digit
            and $t1,$t2,1    # mask one binary digit

    # print blank after 4 digits

            div $t0, $t4
            mfhi $t5
            bnez $t5, skip

            la $a0,blank     # print blank
            li $v0,4
            syscall

    skip:   move $a0, $t1    # print digit as integer
            li $v0, 1
            syscall

    # store digit in string

            add $t1,$t1,48   # ASCII '0' is 48
            sb $t1,($t3)     # save in string
            add $t3,$t3,1    # advance destination pointer
            add $t0,$t0,-1   # decrement counter
            bnez $t0,loop    # and continue if counter>0

    # print result as a string on terminal

            la $a0,binstr
            li $v0,4
            syscall

            la $a0,result
            li $v0,4
            syscall

            j __start

    #--------------------------------------------------
            .data
    result: .space 32
            .byte 0
    prompt: .asciiz "\nEnter decimal number: "
    ans1:   .asciiz "Binary is: "
    binstr: .asciiz "\nBinary string: "
    blank:  .asciiz " "

    2. Convert integer to hexadecimal

    ## hex.a ask user for decimal number,
    ##  convert to hex, print the result.
    ##
    ##      t0 - count for 8 digits in word
    ##      t1 - each hex digit in turn
    ##      t2 - number read in
    ##      t3 - address of area used to set up
    ##           answer string
    ##
    #################################################
    #               text segment                    #
    #################################################

            .text
            .globl __start
    __start:
            la $a0,prompt   # print prompt on terminal
            li $v0,4
            syscall

            li $v0,5        # syscall 5 reads an integer
            syscall
            move $t2,$v0    # $t2 holds hex number

            la $a0,ans1     # print string before result
            li $v0,4
            syscall

            li $t0,8        # eight hex digits in word
            la $t3,result   # answer string set up here

    loop:   rol $t2,$t2,4   # start with leftmost digit
            and $t1,$t2,0xf # mask one digit
            ble $t1,9,print # check if 0 to 9
            add $t1,$t1,7   # 7 chars between '9' and 'A'
    print:  add $t1,$t1,48  # ASCII '0' is 48
            sb $t1,($t3)    # save in string
            add $t3,$t3,1   # advance destination pointer
            add $t0,$t0,-1  # decrement counter
            bnez $t0,loop   # and continue if counter>0

            la $a0,result   # print result on terminal
            li $v0,4
            syscall

            li $v0,10
            syscall         # au revoir...

    #################################################
    #               data segment                    #
    #################################################

            .data
    result: .space 8
            .asciiz "\n"
    prompt: .asciiz "Enter decimal number: "
    ans1:   .asciiz "Hexadecimal is "


    CS 254 - Class #20

    Implementing sets by logical instructions

    The Program

    #  Implementing sets (set union, and set membership) by using logical operations
    #  Questions:
    #    1. How are the elements sorted?
    #    2. Why is each element printed just once?
    #    3. What happens when we enter a number > 31 ?

             .text
             .globl __start

    __start: li $t1, 1
             li $s0, 0           # initialize the set to {}

    loop1:   li $v0, 4
             la $a0, prompt      # Print a prompt
             syscall

             li $v0, 5
             syscall             # Read a number in $v0
             bltz $v0, exit

             sllv $s1, $t1, $v0  # set the $v0-th bit in $s1 to 1, one element set - {$v0}
             or $s0, $s0, $s1    # set unition, $s0 = $s0 U {$v0}
             b loop1

    # Print the set $s0

    exit:    li $v0, 4
             la $a0, result      # Print "You have entered:\n"
             syscall

             li $t3, 0           # clear the counter
             li $t4, 32          # the last value

    loop2:   and $t2, $s0, $t1   # check the $t1-the bit in $s0 ($t1 in $s0 ?)
             beq $t2, $0, skip   # if $t1-th bit is zero then go to skip
             li $v0, 1
             add $a0, $0, $t3
             syscall             # Print the counter
             li $v0, 4
             la $a0, nl          # Print new line
             syscall
    skip:    sll $t1, $t1, 1     # shift the 1 one bit left
             addi $t3, $t3, 1    # increment the counter
             bne $t3, $t4, loop2

             li $v0, 4
             la $a0, bye         # Print the end message
             syscall
             li $v0, 5
             syscall             # wait for Enter
             li $v0, 10
             syscall             # end of program

             .data
    prompt:  .asciiz "Enter a number in [0,31] (<0 for exit): "
    result:  .asciiz "You have entered:\n"
    bye:     .asciiz "Press enter to exit..."
    nl:      .asciiz "\n"

    Example run

    Enter a number in [0,31] (<0 for exit): 0
    Enter a number in [0,31] (<0 for exit): 5
    Enter a number in [0,31] (<0 for exit): 1
    Enter a number in [0,31] (<0 for exit): 4
    Enter a number in [0,31] (<0 for exit): 1
    Enter a number in [0,31] (<0 for exit): 0
    Enter a number in [0,31] (<0 for exit): -1
    You have entered:
    0
    1
    4
    5
    Press enter to exit...

    Enter a number in [0,31] (<0 for exit): 45
    Enter a number in [0,31] (<0 for exit): 39
    Enter a number in [0,31] (<0 for exit): 32
    Enter a number in [0,31] (<0 for exit): -1
    You have entered:
    0
    7
    13
    Press enter to exit...


    CS 254 - Class #21

    Prime numbers: the sieve of Eratosthenes
    (more information about the sieve of Eratosthenes can be found here. See also How Many Primes Are There?)

    #  Prime numbers: The sieve of Eratosthenes.
    #  Print the primes in the interval [2,N]:
    #  S = {2,3,4,...,N}
    #  P = 2;
    #  for P = 2 to N do begin
    #    if P in S then begin
    #      I:=2;
    #      while P*I <= N do begin
    #        S = S \ {P*I}
    #        I = I+1
    #      end
    #    end
    #  end
    #  print S

             .text
             .globl __start

    __start: li $s0 0xFFFFFFFF          # S($s0) = {0,1,2,3,4,...,31}
             li $t0, 2                  # P($t0) = 2
             li $t2, 31                 # N($t2) = 31
             li $t1, 1                  # the moving "1"

    loop:    sllv $t3, $t1, $t0         # set the $t0-th bit of $t3 to 1
             and $t3, $s0, $t3          # P in S ?
             beq $t3, $0, skip          # if no, go to skip

             li $t4, 2                  # I($t4) = 2
    loop1:   mul $t5, $t0, $t4          # $t5 = P*I
             bgt $t5, $t2, skip         # if P*I > N then go to skip
             sllv $t3, $t1, $t5         # set the (P*I)-th bit of $t3 to 1
             nor $t3, $t3, $0           # switch the bits in $t3 (1 <-> 0)
             and $s0, $s0, $t3          # S = S \{P*I} (clear the (P*I)-th bit of $s0)
             add $t4, $t4, 1            # I = I+1
             b loop1

    skip:    add $t0, $t0, 1            # P = P + 1
             ble $t0, $t2, loop         # if P <= N then go to loop

             li $v0, 4
             la $a0, result             # Print "The prime numbers in [0,31] are:\n"
             syscall

    # Print the set S($s0), starting from 2

             li $t0, 2
             li $t1, 4

    loop2:   and $t3, $s0, $t1          # $t1 in $s0 ?
             beq $t3, $0, skip2         # if no, go to skip2
             li $v0, 1
             add $a0, $0, $t0
             syscall                    # Print $t1
             li $v0, 4
             la $a0, nl
             syscall                    # Print new line
    skip2:   sll $t1, $t1, 1            # move the "1" in $t1 one bit to the left
             addi $t0, $t0, 1           # increment $t0
             ble $t0, $t2, loop2        # if $t0 <= 31 then go to loop2

             li $v0, 4
             la $a0, bye                # Print the end message
             syscall
             li $v0, 5
             syscall                    # wait for Enter
             li $v0, 10
             syscall                    # end of program

             .data
    result:  .asciiz "The prime numbers in [0,31] are:\n"
    bye:     .asciiz "Press enter to exit..."
    nl:      .asciiz "\n"


    CS 254 - Class #23

    Stacks

    Reversing a character string

    ## reverse.a - reverse the character
    ## string "str".
    ##
    ## t1 - points to the string
    ## t0 - holds each byte from string in turn
    ##
    #################################################
    #        text segment                           #
    #################################################
            .text
            .globl __start

    __start:
            la $t1,str       # a0 points to the string
    nextCh: lb $t0,($t1)     # get a byte from string
            beqz $t0,strEnd  # zero means end of string
            sub $sp,$sp,4    # adjust stack pointer
            sw $t0,($sp)     # PUSH the t0 register
            add $t1,1        # move pointer one character
            j nextCh         # go round the loop again

    strEnd: la $t1,str       # a0 points to the string
    store:  lb $t0,($t1)     # get a byte from string
            beqz $t0,done   # zero means end of string
            lw $t0,($sp)     # POP a value from the stack
            add $sp,$sp,4    # and adjust the pointer
            sb $t0,($t1)     # store in string
            add $t1,1        # move pointer one character
            j store

    done:   la $a0,str       # system call to print
            li $v0,4         # out a message
            syscall

            la $a0,endl      # system call to print
            li $v0,4         # out a newline
            syscall

            li $v0,10
            syscall          # au revoir...

    #################################################
    #       data segment                            #
    #################################################

           .data
    str:   .asciiz "hello world"
    endl:  .asciiz "\n"

    Reverse polish calculator (evaluating expressions in postfix notation)

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, ask        # Print "Type an expression (single digit numbers only): "
             syscall

             la $a0, buffer     # $a0 holds the address of the read buffer
             lw $a1, maxlen     # Max number of chars (including the end of string char)
             li $v0, 8          # Load the service number (read a string)
             syscall            # Call the operating system

             li $t3, 10         # ASCII 10 (LF) is the last char in the string
             lb $t4, timesc     # ASCII "*"
             lb $t5, plusc      # ASCII "+"
             lb $t6, minusc     # ASCII "-"
             lb $t7, overc      # ASCII "/"

    loop:    lb $t0,0($a0)      # get a byte from the string
             beq $t0, $t3, done # check for end
             add $a0, $a0, 1    # move the chars pointer to the next char
             blt $t0, 48, op    # ASCII<48 => not a number, possibly op
             bgt $t0, 57, op    # ASCII>57 => not a number, possibly op
             addi $t0, $t0, -48 # convert an ASCII digit to a numerical value
             sub $sp, $sp, 4    # move the stack pointer
             sw $t0, 0($sp)     # PUSH $t0 into the stack
             b loop

    op:      lw $t2, 0($sp)     # PULL $t2 from stack
             add $sp, $sp, 4
             lw $t1, 0($sp)     # PULL $t1 from stack
             add $sp, $sp, 4
             beq $t0, $t4, times
             beq $t0, $t5, plus
             beq $t0, $t6, minus
             beq $t0, $t7, over
             b loop             # go round the loop again

    times:   mul $t0, $t1, $t2
             b next

    plus:    add $t0, $t1, $t2
             b next

    minus:   sub $t0, $t1, $t2
             b next

    over:    div $t0, $t1, $t2

    next:    sub $sp, $sp, 4    # move the stack pointer
             sw $t0, 0($sp)     # PUSH the result ($t0) into the stack
             b loop

    done:   lw $a0, 0($sp)      # PULL the result from the stack
            li $v0, 1
            syscall             # Print the result

            li $v0, 4
            la $a0, bye         # Print the end message
            syscall
            li $v0, 5
            syscall             # wait for Enter
            li $v0, 10
            syscall             # end of program

            .data
    ask:    .asciiz "Type an expression (single digit numbers only): "
    bye:    .asciiz "\nPress enter to exit...\n"
    maxlen: .word 31
    buffer: .space 31
    timesc: .ascii "*"
    plusc:  .ascii "+"
    minusc: .ascii "-"
    overc:  .ascii "/"


    CS 254 - Class #24

    Procedure calls, parameter passing, saving the return address

    Adding two rational numbers

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, Prompt
             syscall

             li $v0, 5
             syscall                # Read an integer in $v0
             move $a0, $v0          # and store it in $a0
             li $v0, 5
             syscall                # Read an integer in $v0
             move $a1 $v0           # and store it in $a1
             li $v0, 5
             syscall                # Read an integer in $v0
             move $a2, $v0          # and store it in $a2
             li $v0, 5
             syscall               # Read an integer in $v0
             move $a3, $v0          # and store it in $a3

             jal addtwo

             move $s0, $a0          # save $a0

             li $v0, 4
             la $a0, Result
             syscall                # Print the result

             move $a0, $s0          # restore $a0
             li $v0, 1
             syscall                # Print $a0

             li $v0, 4
             la $a0, slash
             syscall

             move $a0, $a1
             li $v0, 1
             syscall                # Print $a1

             li $v0, 4
             la $a0, bye            # Print the end message
             syscall
             li $v0, 5
             syscall                # wait for Enter
             li $v0, 10
             syscall                # end of program

    #------------------------------------------------------------
    #  Add fractions
    #------------------------------------------------------------
    #  Input:  $a0/$a1, $a2/$a3 - two fractions
    #------------------------------------------------------------
    #  Output: $a0/$a1 = $a0/$a1 + $a2/$a3 (in rational numbers)
    #------------------------------------------------------------
    addtwo: sub $sp, $sp, 4
            sw $ra, 0($sp)

            mul $t0, $a0, $a3
            mul $t1, $a2, $a1
            add $t0, $t0, $t1
            mul $t1, $a1, $a3

            move $a0, $t0
            move $a1, $t1

            jal gcd

            div $a0, $a0, $v0
            div $a1, $a1, $v0

            lw $ra, 0($sp)
            add $sp, $sp, 4

            jr $ra

    #--------------------------------------------------
    #  GCD procedure
    #--------------------------------------------------
    #  Input:  $a0, $a1 - two integers
    #--------------------------------------------------
    #  Output: $v0 - the GCD of $a0 and $a1
    #--------------------------------------------------
    gcd:     move $t0, $a0         # move the arguments
             move $t1, $a1         # to temporary variables

    loop:    div $t0, $t1          # $t2 = $t0 mod $t1
             mfhi $t2
             move $t0, $t1         # $t0 = $t1
             move $t1, $t2         # $t1 = $t2
             bne $t1, $0, loop

             move $v0, $t0         # move the return value to $v0

             jr $ra                # return

    #-------------------------------------------------------------------------
             .data
    Prompt:  .asciiz "Enter four integers (A,B,C,D) for A/B and C/D:\n"
    Result:  .asciiz "A/B + C/D = "
    slash:   .asciiz "/"
    bye:     .asciiz "\nPress enter to exit..."


    CS 254 - Class #25

    Stack frames, Factorial function. Slides in PPT

    # main ()
    # {
    #    printf ( fact (10);
    # }

             .text
             .globl __start

    __start: li $a0, 10        # Put argument (10) in $a0
             jal fact          # Call factorial function
             move $a0, $v0     # Move returned value ($v0) in $a0
             li $v0, 1
             syscall           # Print it

             li $v0, 10
             syscall           # end of main program

    # int fact (int n)
    # {
    #   if (n < 1)
    #      return;
    #   else
    #      return (n * fact  (n - 1));
    # }

    fact: subu $sp, $sp, 32    # Stack frame is 32 bytes long
          sw   $ra, 20($sp)    # Save return address
          sw   $fp, 16($sp)    # Save old frame pointer
          addu $fp, $sp, 28    # Set up frame pointer
          sw   $a0, 0($fp)     # Save argument (n)

          lw   $v0, 0($fp)     # Load n
          bgtz $v0, L2         # Branch if n > 0
          li   $v0, 1          # Return 1
          j    L1              # Jump to code to return

    L2:   lw   $v1, 0($fp)     # Load n
          subu $v1, $v1, 1     # Compute n - 1
          move $a0, $v1        # Move value to $a0
          jal  fact

          lw   $v1, 0($fp)     # Load n
          mul  $v0, $v0, $v1   # Computer fact(n-1) * n

    L1:   lw   $ra, 20($sp)    # Restore $ra
          lw   $fp, 16($sp)    # Restore $fp
          addu $sp, $sp, 32    # Pop stack
          j    $ra             # Return to caller
     

    Sorting strings by selection sort

      .text
      .globl __start

    __start: li $v0, 4
             la $a0, prompt         # Print a prompt
             syscall

             la $a0, buffer
             lw $s0, maxlen
             li $s1, 10             # the ASCII code of LF

    # Read the words

    rloop:   li $v0, 8              # read the word
             lw $a1, maxlen
             syscall
             lb $t0, 0($a0)         # load the first char of the word in $t0
             beq $t0, $s1, next     # if LF stop reading and go to sorting
             add $a0, $a0, $s0      # move the pointer to the next word
             b rloop

    # Sorting the words

    next:    sub $a1, $a0, $s0      # $a1 points to the last string
             la $a0, buffer

    ssort:   beq $a0, $a1, print    # if the last word is reached then stop
             jal min                # find the min word
             move $t0, $a0
             move $t1, $v0
             lw $t4, maxlen         # counter ($t4) = maxlen
    swap:    lb $t2, 0($t0)         # swap the current chars
             lb $t3, 0($t1)
             sb $t3, 0($t0)
             sb $t2, 0($t1)
             addi $t0, $t0, 1       # move to the next char
             addi $t1, $t1, 1
             addi $t4, $t4,-1       # decrement the counter ($t4)
             bne $t4, $0, swap
             add $a0, $a0, $s0      # move to the next word
             b ssort

    # Print the sorted words

    print:   li $v0, 4
             la $a0, sorted         # Print "Sorted:\n"
             syscall

             la $a0, buffer

    wloop:   lb $t0, 0($a0)         # load the first char of the word in $t0
             beq $t0, $s1, stop     # if LF then stop
             li $v0, 4              # print the word
             syscall
             add $a0, $a0, $s0      # move the pointer to the next word
             b wloop

    stop:    li $v0, 4
             la $a0, bye
             syscall
             li $v0, 5
             syscall
             li $v0, 10
             syscall  # end of program

    #------------------------------------------------------------------------------
    # min: procedure to find the address of the min element in an array of strings.
    # For each string "maxlen" bytes of memory is allocated.
    # "maxlen" is a word defined in the data segment.
    #------------------------------------------------------------------------------
    # Input:  $a0 - the address of the first string
    #         $a1 - the address of the last stirng
    #------------------------------------------------------------------------------
    # Output: $v0 - the address of the minimal stirng
    #------------------------------------------------------------------------------
    min:     sub $sp, $sp, 20         # Reserve space in stack
             sw $a0, 0($sp)           # Push $a0
             sw $a1, 4($sp)           # Push $a1
             sw $s0, 8($sp)           # Push $s0
             sw $s1, 12($sp)          # Push $s1
             sw $ra, 16($sp)         # Push the return address

             move $s0, $a0            # $s0 will hold the addr of min
             move $s1, $a1            # $s1 points to the last string

    loop1:   move $a1, $s0            # prepare the arguments for strcmp
             jal strcmp               # string at $a0 > string at $s0 ?
             bne $v0, $0, skip        # if yes, go to skip
             move $s0, $a0            # update the address of min
    skip:    lw $t0, maxlen
             add $a0, $a0, $t0        # move the pointer to the next string
             ble $a0, $s1, loop1

             move $v0, $s0            # put the return value in $v0

             lw $a0, 0($sp)           # Pull $a0
             lw $a1, 4($sp)           # Pull $a1
             lw $s0, 8($sp)           # Pull $s0
             lw $s1, 12($sp)          # Pull $s1
             lw $ra, 16($sp)          # Pull the return address
             add $sp, $sp, 20         # Restore the stack pointer

             jr $ra                   # return

    #-------------------------------------------------------------------------------
    #  strcmp: procedure for comparing strings
    #-------------------------------------------------------------------------------
    #  Input:  $a0 - the address of string0
    #          $a1 - the address of string1
    #-------------------------------------------------------------------------------
    #  Output: $v0 = 1 => string0  > string1
    #          $v0 = 0 => string0 <= string1
    #-------------------------------------------------------------------------------
    strcmp:  move $t0, $a0            # get argument $a0
             move $t1, $a1            # get argument $a1
             li $v0, 0                # the default retrun value

    loop2:   lb $t2, 0($t0)           # fetch the current char of string0 to $t2
             lb $t3, 0($t1)           # fetch the current char of string1 to $t3
             beq $t2, $0, ret         # if the end of string0 is reached then return 0
             addi $t0, $t0, 1         # move $t0 to point to the next char of string0
             addi $t1, $t1, 1         # move $t1 to point to the next char of string1
             beq $t2, $t3, loop2      # if $t2 = $t3 then continue

             slt $v0, $t3, $t2        # $v0 = $t2 > $t3

    ret:     jr $ra                   # return

    #------------------------------------------------------------------
            .data
    buffer: .space 10000
    maxlen: .word 32
    prompt: .asciiz "Type words on separate lines (Enter for exit):\n"
    sorted: .asciiz "Sorted:\n"
    bye:    .asciiz "\nPress enter to exit..."


    CS 254 - Class #26

    Linked lists

    Static linked lists

             .data
    bye:     .asciiz "\nPress enter to exit..."
    blank:   .asciiz "\n"
    El1:     .word D1, El2
    El2:     .word D2, El3
    El3:     .word D3, El4
    El4:     .word D4, 0

    D1:      .asciiz "John"
    D2:      .asciiz "Ann"
    D3:      .asciiz "Bill"
    D4:      .asciiz "Jim"

             .text
             .globl __start

    __start:
             la $s1, El1          # $s1 points to the first element
             jal print            # print the list

             li $v0, 4
             la $a0, bye
             syscall
             li $v0, 5
             syscall
             li $v0, 10
             syscall              # end of program

    #------------------------------------------------------------------
    # print - print the linked list ($s1 points to the top of the list)
    #------------------------------------------------------------------
    print:   move $t0, $s1       # $t0 points to the top of the list

    ploop:   beq $t0, $0, ret     # the link field = 0 => end of list
             lw $a0, 0($t0)       # load the data field
             li $v0, 4
             syscall              # print the data
             la $a0, blank
             li $v0, 4
             syscall              # print a blank line
             lw $t0, 4($t0)       # $t0 points to the next element
             b ploop

    ret:     jr $ra               # return

    Creating and printing a linked list

             .text
             .globl __start

    __start: la $s0, heap        # initialize the heap pointer, $s0
             li  $s1, 0          # initialize the top of the list, $s1

    #  Read the numbers and push then into the list

    loop1:   li $v0, 4
             la $a0, ask
             syscall             # Ask for a number
             li $v0, 5
             syscall             # Read an integer in $v0
             lw $t0, endmark
             beq $v0, $t0, exit  # if $v0 = endmark then exit loop
             move $a0, $v0       # $a0 is the argument of push
             jal push            # push $v0 into the list
             jal print           # print the current list
             b loop1

    exit:  # Print the good bye message

             li $v0, 4
             la $a0, bye        # Print the message
             syscall
             li $v0, 5
             syscall            # wait for Enter
             li $v0, 10
             syscall            # end of program

    #------------------------------------------------------------------
    # print - print the linked list ($s1 points to the top of the list)
    #------------------------------------------------------------------
    print:   sub $sp, $sp, 4
             sw $ra, 0($sp)     # save the return address into stack

             move $t0, $s1      # $t0 points to the top of the list
    loop2:   beq $t0, $0, ret   # the link field = 0 => end of the list
             lw $a0, 0($t0)     # load the data field
             li $v0, 1
             syscall            # print the data
             la $a0, blank
             li $v0, 4
             syscall            # print a blank line
             lw $t0, 4($t0)     # $t0 points to the next element
             b loop2

    ret:     la $a0, nl
             li $v0, 4
             syscall            # print a new line

             lw $ra, 0($sp)
             addi $sp, $sp, 4   # restore the return address from stack

             jr $ra             # return

    #------------------------------------------------------------------
    # push - add an element at the top of the list
    #   Input:  $a0 - the element
    #   Output: none
    #------------------------------------------------------------------
    push:    sub $sp, $sp, 4
             sw $ra, 0($sp)     # save the return address into stack
             move $t0, $a0      # save the argument in $t0

             li $a0, 8          # a list element occupies 8 bytes
             jal new            # allocate a block of 8 bytes, $v0 will point to the block

             sw $t0, 0($v0)     # fill the data field
             sw $s1, 4($v0)     # fill the link field
             move $s1, $v0      # update the top of the list

             lw $ra, 0($sp)
             addi $sp, $sp, 4   # restore the return address from stack

             jr $ra             # return

    #------------------------------------------------------------------
    # new - a procedure to allocate memory
    #   Input:  $a0 - the number of bytes to allocate
    #   Output: $v0 - the address of the first byte
    #------------------------------------------------------------------
    new:     move $v0, $s0      # $v0 points to the top of the heap
             add $s0, $s0, $a0  # move the top $a0 bytes up
             jr $ra             # return

    #------------------------------------------------------------------
             .data
    heap:    .space 10000
    ask:     .asciiz "Enter an integer (-999 for exit): "
    endmark: .word -999
    bye:     .asciiz "\nPress enter to exit..."
    blank:   .asciiz " "
    nl:      .asciiz "\n"

    On-line sorting

    # This program uses the procedures "print" and "new" as defined above

             .text
             .globl __start

    __start: la $s0, heap         # initialize the heap pointer, $s0
             li  $s1, 0           # initialize the top of the list, $s1

    #  Read the numbers and push then into the list

    loop1:   li $v0, 4
             la $a0, ask
             syscall              # Ask for a number
             li $v0, 5
             syscall              # Read an integer in $v0
             lw $t0, endmark
             beq $v0, $t0, exit   # if $v0 = endmark then exit loop
             move $a0, $v0        # $a0 is the argument of push

             jal insert           # insert $v0 into the list

             jal print            # print the current list
             b loop1

    exit:    # Print the good bye message

             li $v0, 4
             la $a0, bye          # Print the message
             syscall
             li $v0, 5
             syscall              # wait for Enter
             li $v0, 10
             syscall              # end of program

    #------------------------------------------------------------------
    # insert - insert an element in the list preserving the order
    #   Input:  $a0 - the element to insert
    #   Output: none
    #------------------------------------------------------------------
    insert:  sub $sp, $sp, 4
             sw $ra, 0($sp)        # save the return address into stack
             move $t0, $a0         # save the argument in $t0

             li $a0, 8             # a list element occupies 8 bytes
             jal new               # allocate a block of 8 bytes, $v0 will point to the block

             sw $t0, 0($v0)        # fill the data field of the new element

             beq $s1, $0, insert1  # if the list is empty then go to insert1
             lw $t3, 0($s1)        # fetch the first element in $t3
             bgt $t0, $t3, insert2 # if new  > first then go to insert2

    insert1: # add the new element at the top of the list
             sw $s1, 4($v0)        # update the link field
             move $s1, $v0         # update the top the the list

    insert2: # a loop to find the proper place for the new element
             move $t1, $s1         # $t1 (current element) points to the top of the list
             move $t2, $s1         # $t2 (previous element) points to the top of the list
    loop3:   lw $t3, 0($t1)        # fetch the current element in $t3
             blt $t0, $t3, exit3   # if $t0 < $t3 then exit loop
             move $t2, $t1         # update previous
             lw $t1, 4($t1)        # update current
             bne $t1, $0, loop3

    exit3:   sw $v0, 4($t2)        # connect previous to new
             sw $t1, 4($v0)        # connect new to current

             lw $ra, 0($sp)
             addi $sp, $sp, 4      # restore the return address from stack

             jr $ra                # return

    #------------------------------------------------------------------
             .data
    heap:    .space 10000
    ask:     .asciiz "Enter an integer (-999 for exit): "
    endmark: .word -999
    bye:     .asciiz "\nPress enter to exit..."
    blank:   .asciiz " "
    nl:      .asciiz "\n"


    CS 254 - Class #27

    Recursive programming

    #  Print a binary tree as a horizontal tree

             .text
             .globl __start

    __start: la $a0, node1
             li $a1, 0         # start at position 0
             jal ptree         # print the tree at node1

             li $v0, 4
             la $a0, bye       # Print the good bye message
             syscall
             li $v0, 5
             syscall          # wait for Enter
             li $v0, 10
             syscall           # end of program

    #-----------------------------------------------------------------------------------
    #  ptree - print a binary tree as a horizontal tree
    #   Input:  $a0 - the address of the root
    #   Output: $a1 - the position to print the root
    #-----------------------------------------------------------------------------------
    ptree:   sub $sp, $sp, 12
             sw $a0, 0($sp)    # save $a0 into a local variable
             sw $a1, 4($sp)    # save $a1 into a local variable
             sw $ra, 8($sp)

             beq $a0, $0, ret  # empty node => nothing to print

             jal blanks        # print $a1 blanks

             lw $a0, 0($sp)
             lw $a0, 0($a0)    # fetch the address of the label into $a0
             li $v0, 4
             syscall           # print the label

             la $a0, nl
             li $v0, 4
             syscall           # print new line

             addi $a1, $a1, 1 # increment the offset for the subtrees

             lw $a0, 0($sp)
             lw $a0, 4($a0)    # fetch the address of the left subtree into $a0
             jal ptree         # print the left subtree

             lw $a0, 0($sp)
             lw $a0, 8($a0)    # fetch the address of the right subtree into $a0
             jal ptree         # print the right subtree

    ret:     lw $a0, 0($sp)
             lw $a1, 4($sp)
             lw $ra, 8($sp)
             addi $sp, $sp, 12

             jr $ra

    #-----------------------------------------------------------------------------------
    #  blanks - print a number of blanks
    #    Input:  $a1 - the number of blanks to be printed
    #-----------------------------------------------------------------------------------
    blanks:  move $t1, $a1
    loop:    beq $t1, $0, ret1
             la $a0, blank
             li $v0, 4
             syscall  # print a blank
             addi $t1, $t1, -1 # decrement the counter
             b loop

    ret1:    jr $ra

    #------------------------------------------------------------------
             .data
    node1:   .word label1, node2, node3
    node2:   .word label2, node4, node5
    node3:   .word label3, 0, 0
    node4:   .word label4, 0, 0
    node5:   .word label5, node6, node7
    node6:   .word label6, 0, 0
    node7:   .word label7, 0, 0
    label1:  .asciiz "node1"
    label2:  .asciiz "node2"
    label3:  .asciiz "node3"
    label4:  .asciiz "node4"
    label5:  .asciiz "node5"
    label6:  .asciiz "node6"
    label7:  .asciiz "node7"
    bye:     .asciiz "\nPress enter to exit..."
    blank:   .asciiz "  "
    nl:      .asciiz "\n"


    CS 254 - Class #28

    Exceptions and interrupts

    #  Part I: a user program causing an arithmetic exception
    #  Read an integer and multiply it by 2

             .text
             .globl __start

    __start: li $v0, 4
             la $a0, Ask
             syscall

             li $v0, 5
             syscall            # read an integer in $v0

             add $s0, $v0, $v0   # $s0=$v0+$v0 (an overflow may occur here)

             li $v0, 4
             la $a0, Result
             syscall

             add $a0, $0, $s0   # $a0 = $s0
             li $v0, 1          # print $a0
             syscall

             li $v0, 4
             la $a0, nl
             syscall            # print new line

             j __start          # jump to __start

             .data
    nl:      .asciiz "\n"
    Ask:     .asciiz "\nEnter an integer number: "
    Result:  .asciiz "This number multiplied by 2 makes "
     

    #  Part II: Exception handler
    #  Addapted from:
    #    Hennessy & Patterson, Computer Organization and Design:
    #    The Hardware/Software Interface, Second Edition,
    #    Morgan Kaufmann Publishers, Inc., 1997.

             .ktext 0x80000080
             sw $a0, save0       # Handler is not re-entrant and can’t use
             sw $a1, save1       # stack to save $a0, $a1

    # Don’t need to save $k0/$k1

             mfc0 $k0, $13       # Move Cause into $k0
             mfc0 $k1, $14       # Move EPC into $k1
             sgt $v0, $k0, 0x44  # Ignore interrupts
             bgtz $v0, done

             li $v0, 4
             la $a0, msg1
             syscall

             move $a0, $k0       # Move Cause into $a0
             li $v0, 1
             syscall             # Print the contents of the cause register
             li $v0, 4
             la $a0, nl
             syscall             # print new line

             li $v0, 4
             la $a0, msg2
             syscall

             move $a0, $k1       # Move EPC into $a0
             li $v0, 1
             syscall             # Print the contents EPC
             li $v0, 4
             la $a0, nl
             syscall             # print new line

    done:    lw $a0, save0
             lw $a1, save1
             addiu $k1, $k1, 4   # Do not reexecute the faulting instruction
             rfe                 # Restore interrupt state
             jr $k1

             .kdata
    save0:   .word 0
    save1:   .word 0
    msg1:    .asciiz "An exception occurred\nCause register = "
    msg2:    .asciiz "EPC = "


    Assignment 1

    Do the following number conversions. Show all the work:
    1. Convert -1024 (negative decimal) into 32-bit two's complement number.
    2. Find the largest and the smallest number which can be held in 11 bits using the two’s complement binary representation. Write these numbers in binary, decimal and hexadecimal.
    3. Convert  0001 0001 0101 0000 1101 0000 1011 0000 (unsigned binary) into hexadecimal and decimal. (Use the hexadecimal representation to calculate the decimal value.)
    4. Represent 25 (decimal) into 32-bit floating point number (IEEE 754 single precision).
    5. Represent 1.625 (decimal) into 32-bit floating point number (IEEE 754 single precision).

    Assignment 2

    A. Define a data segment using byte definition of decimal numbers only (.byte) that is equivalent (i.e. creates the same memory image) to the following one:
    .data
    .word 0x12345678
    .word 12345678
    .ascii "hello world!"
    Hint: use the simulator for the conversions and to verify your data segment.

    B. Do the programming examples math2.aand math3.a on pages 46,47,48 of the book.


    Project 1

    Write a program in MIPS to print the sum of two rational numbers (fractions) as a rational number too. The following restrictions apply: Extra credit (2 pts.): Implement integer overflow detection. Identify the possible situations when overflow may occur and include a program code that checks for overflow and  prints a message indicating the values of the operands and the operation that caused overflow. Hint: use instructions that ignore overflow and compare the signs of the operands and the result for addition or check the contents of the hi register for multiplication.

    Project 2

    Write a program in MIPS to sort an array of integer numbers. The numbers are first entered by the user (using fixed count or sentinel loop, see the program from class #15) then the program sorts them in increasing order by using the selection sort method and prints the sorted array. The selection sort method is defined as follows (a[0], a[1], ..., a[n] is the array to be sorted, n>0):
    1. i=0;
    2. let j be the index of the minimal element a[j] among a[i], a[i+1], ..., a[n];
    3. exchange a[i] and a[j];
    4. i=i+1
    5. if i=n then exit else go to step 2;
    Your project report must include the following (all in one ascii text file):
    1. The source code of the program.
    2. The pseudo-code for the algorithm (similar to the one above) with all memory words, registers and strings as used in your program. Include this as a comment.

    Project 3

    Description: Write a program in MIPS to read two strings and compare them. As a result the program should print which one is greater according to the lexicographic order (the order in which words appear in dictionaries). For example (the user input is in italics):
    Type two strings:
    John
    Ann
    John is greater than Ann
    Your project report must include the following (all in one ascii text file) and must be submitted by e-mail.
    1. The source code of the program.
    2. The pseudo-code for the algorithm with all memory words, registers and strings as used in your program. Include this as a comment.
    Extra credit (2 pts.): Extend the program to read a sequence of strings (by using a fixed count or sentinel loop) and print the minimal one.

    Project 4

    Write a MIPS assembly program to tabulate the function pi(N) - the number of prime numbers less than N. Use the sieve of Eratosthenes method to generate prime numbers in the interval [2,N] and determine the maximal N experimentally. Here is an example tabulation of pi(N):

                                     N                        pi(N)
         ----------------------------   -------------------------
                                   10                           4
                                  100                          25
                                1,000                         168
                               10,000                       1,229
                              100,000                       9,592
                            1,000,000                      78,498
                           10,000,000                     664,579
                          100,000,000                   5,761,455
                        1,000,000,000                  50,847,534
                       10,000,000,000                 455,052,511
                      100,000,000,000               4,118,054,813
                    1,000,000,000,000              37,607,912,018
                   10,000,000,000,000             346,065,536,839
                  100,000,000,000,000           3,204,941,750,802
                1,000,000,000,000,000          29,844,570,422,669
               10,000,000,000,000,000         279,238,341,033,925
              100,000,000,000,000,000       2,623,557,157,654,233
            1,000,000,000,000,000,000      24,739,954,287,740,860
           10,000,000,000,000,000,000     234,057,667,276,344,607
          100,000,000,000,000,000,000   2,220,819,602,560,918,840
         ----------------------------   -------------------------

    Note that this tabulation is just an illustration (for more details see How Many Primes Are There?). Using the SPIM simulator you will never be able to find the number of primes for large N's, e.g. greater than 1,000,000.

    The following restrictions apply:

    1. Use a Boolean array to implement the sets (the array elements  might be words, bytes or bits)
    2. Include the pseudocode of your algorithm (as shown in class #21). This is a part of the project and will be graded too.
    3. Use proper increments (e.g. 1,000 if N=30,000) for N in order to print approximately 30 rows in the table.
    Extra credit (5 pts.) will be given to projects tabulating the function pi(N) for large N (near 1,000,000). Hint: to achieve this you have to use a Boolean array of bits.

    Test 2

    Sample problems

    Problem 1: Consider the following data segment definition:
    X:  .word 750, 250, 200, 0

    Write a sequence of MIPS instructions to add together the three data words at label X and to store the sum into the fourth one (the one initialized with 0). Do not use constants in the instructions.

    Problem 2: Consider the following data segment definition:

    string: .asciiz "This is a String"
    upper:  .word 0
    lower:  .word 0
    spaces: .word 0
    Write a sequence of MIPS instructions implementing a loop to count the number of upper case letters, lower case letters and spaces in the string and store the counts in the three memory words correspondingly. Write two versions of the code using:
    a) Base addressing
    b) Index addressing
     
    Problem 3: Consider the following data segment definition:
    string1: .asciiz "this is a string"
    string2: .space 17
    Write a sequence of MIPS instructions to copy the characters of string1 into string2 in reverse order. Hint: you have first to find the length of string1 with a separate loop. Note that string2 must be a correct asciiz string (add “0” at the end).

    Problem 4: Write a program in MIPS to print the ascii table from digit “0” to letter “z”. The output must look like this:

    0 – 48
    1 – 49
    ...
    x – 120
    y – 121
    z – 122
    Problem 5: Consider the following data segment definition:
    array: .word 0, 0, 0, 0, 0, 0
    buffer: .asciiz "Introduction"
            .asciiz "to"
            .asciiz "RISC"
            .asciiz "Assembly"
            .asciiz "Language"
            .asciiz "Programming
    a) Write a sequence of MIPS instructions to store the addresses of the strings in the buffer into the array elements. Do not use loops, just count the characters and include the corresponding offsets as constants in the instructions. Take into account the end of string characters (0) added by asciiz.
    b) Write a loop to print the strings using the array with their addresses.

    Test 3

    Sample problems

    Problem 1: Complete the following program so that it prints 250 and 750 (in this order):
             .text
             .globl __start
    __start: la $a0, X
             la $a1, Y
             jal swap

             lw $a0, X

             li $v0, 1
             syscall
             li $v0, 4
             la $a0, nl
             syscall
             lw $a0, Y
             li $v0, 1
             syscall
            .data
         X: .word 750
         Y: .word 250
        nl: .asciiz ”\n”
    Hint: Write the procedure swap, which is used in the code above. It takes two parameters: $a0 and $a1 – the addresses of two memory words to be swapped.

    Problem 2: Complete the following program so that it prints the sum of the elements of the array (1800):

             .text
             .globl __start
    __start: la $a0, array
             lw $a1, N
             jal total

             move $a0, $v0

             li $v0, 1
             syscall
            .data
     array: .word 750, 250, 500, 300
         N: .word 4
    Hint: Write the procedure total, which takes two parameters: $a0 – the address of the array and $a1 – the number of elements in the array. The subroutine returns the sum of the elements in register $v0.

    Problem 3: Using the data segment below write a sequence of instructions to create a linked list containing elements A, B, C, D, E (in this order).

    Top: .word A
    A:   .word 50,  0
    B:   .word 100, 0
    C:   .word 150, 0
    D:   .word 100, 0
    E:   .word 250, 0
    Problem 4: Consider the following data segment defining a linked list of 5 elements (A,B,C,D,E):
    Top: .word A
    A:   .word 50,  B
    B:   .word 100, C
    C:   .word 150, D
    D:   .word 100, E
    E:   .word 250, 0
    a) Write a sequence of instructions implementing a loop to print the list. Use label Top to start traversing the list.
    b) Write a sequence of instructions to remove B from the list.
    c) Write a sequence of instructions to insert E between B and C and make D the last element in the list.
    d) Write a sequence of instructions to swap C and D by changing the respective links (not the data fields).
    e) Write a loop to remove from the list all elements containing 100 in their data fields.