Exersice 4 - cs621

MIPS Assembly Language

Code Fibonacci

# Compute several Fibonacci numbers and put in array, then print

.data

fibs:.word   0 : 19         # "array" of words to contain fib values

size: .word  19             # size of "array" (agrees with array declaration)

prompt: .asciiz "How many Fibonacci numbers to generate? (2 <= x <= 19)"

.text

      la   $s0, fibs        # load address of array

      la   $s5, size        # load address of size variable

      lw   $s5, 0($s5)      # load array size

# Optional: user inputs the number of Fibonacci numbers to generate

#pr:   la   $a0, prompt      # load address of prompt for syscall

#      li   $v0, 4           # specify Print String service

#      syscall               # print the prompt string

#      li   $v0, ?????Replace_this_dummy_with_the_correct_numeric_value???????           # specify Read Integer service

#      syscall               # Read the number. After this instruction, the number read is in $v0.

#      bgt  $v0, $s5, pr     # Check boundary on user input -- if invalid, restart

#      blt  $v0, $zero, pr   # Check boundary on user input -- if invalid, restart

#      add  $s5, $v0, $zero  # transfer the number to the desired register

     

      li   $s2, 1           # 1 is the known value of first and second Fib. number

      sw   $s2, 0($s0)      # F[0] = 1

      sw   $s2, 4($s0)      # F[1] = F[0] = 1

      addi $s1, $s5, -2     # Counter for loop, will execute (size-2) times

     

      # Loop to compute each Fibonacci number using the previous two Fib. numbers.

loop: lw   $s3, 0($s0)      # Get value from array F[n-2]

      lw   $s4, 4($s0)      # Get value from array F[n-1]

      add  $s2, $s3, $s4    # F[n] = F[n-1] + F[n-2]

      sw   $s2, 8($s0)      # Store newly computed F[n] in array

      addi $s0, $s0, 4      # increment address to now-known Fib. number storage

      addi $s1, $s1, -1     # decrement loop counter

      bgtz $s1, loop        # repeat while not finished

      # Fibonacci numbers are computed and stored in array. Print them.

      la   $a0, fibs        # first argument for print (array)

      add  $a1, $zero, $s5  # second argument for print (size)

      jal  print            # call print routine.

      # The program is finished. Exit.

      li   $v0, 10          # system call for exit

      syscall               # Exit!                  

###############################################################

# Subroutine to print the numbers on one line.

      .data

space:.asciiz  " "          # space to insert between numbers

head: .asciiz  "The Fibonacci numbers are:\n"

      .text

print:add  $t0, $zero, $a0  # starting address of array of data to be printed

      add  $t1, $zero, $a1  # initialize loop counter to array size

      la   $a0, head        # load address of the print heading string

      li   $v0, 4           # specify Print String service

      syscall               # print the heading string

     

out:  lw   $a0, 0($t0)      # load the integer to be printed (the current Fib. number)

      li   $v0, 1           # specify Print Integer service

      syscall               # print fibonacci number

     

      la   $a0, space       # load address of spacer for syscall

      li   $v0, 4           # specify Print String service

      syscall               # print the spacer string

     

      addi $t0, $t0, 4      # increment address of data to be printed

      addi $t1, $t1, -1     # decrement loop counter

      bgtz $t1, out         # repeat while not finished

     

      jr   $ra              # return from subroutine

# End of subroutine to print the numbers on one line

###############################################################

เป็นการคำนวณเลข Fibonacci

โดยการคำนวณเลข Fibonacci จะทำการคำนวณโดยนำค่าแรกมาเก็บไว้ที่ address แรก และค่าaddress ที่2 เท่ากับค่าแรก ค่า address ที่ 3 เท่ากับ address ที่1 บวกกับ addressที่2 เช่น กำหนดให้ F คือค่า address

F0 = 1

F1 = 1

F2 = F0+F1 = 2

F3 = F1+F2 = 3

F4 = F2+F3 = 5

F5 = F3+F4 = 8

…….

เมื่อคำนวณออกมาแล้วจะได้ผลดังภาพ

Code Row-major

#############################################################################

#  Row-major order traversal of 16 x 16 array of words.

#  Pete Sanderson

#  31 March 2007

#

#  To easily observe the row-oriented order, run the Memory Reference

#  Visualization tool with its default settings over this program.

#  You may, at the same time or separately, run the Data Cache Simulator

#  over this program to observe caching performance.  Compare the results

#  with those of the column-major order traversal algorithm.

#

#  The C/C++/Java-like equivalent of this MIPS program is:

#     int size = 16;

#     int[size][size] data;

#     int value = 0;

#     for (int row = 0; col < size; row++) {

#        for (int col = 0; col < size; col++) }

#           data[row][col] = value;

#           value++;

#        }

#     }

#

#  Note: Program is hard-wired for 16 x 16 matrix.  If you want to change this,

#        three statements need to be changed.

#        1. The array storage size declaration at "data:" needs to be changed from

#           256 (which is 16 * 16) to #columns * #rows.

#        2. The "li" to initialize $t0 needs to be changed to new #rows.

#        3. The "li" to initialize $t1 needs to be changed to new #columns.

#

         .data

data:    .word     0 : 256       # storage for 16x16 matrix of words

         .text

         li       $t0, 16        # $t0 = number of rows

         li       $t1, 16        # $t1 = number of columns

         move     $s0, $zero     # $s0 = row counter

         move     $s1, $zero     # $s1 = column counter

         move     $t2, $zero     # $t2 = the value to be stored

#  Each loop iteration will store incremented $t1 value into next element of matrix.

#  Offset is calculated at each iteration. offset = 4 * (row*#cols+col)

#  Note: no attempt is made to optimize runtime performance!

loop:    mult     $s0, $t1       # $s2 = row * #cols  (two-instruction sequence)

         mflo     $s2            # move multiply result from lo register to $s2

         add      $s2, $s2, $s1  # $s2 += column counter

         sll      $s2, $s2, 2    # $s2 *= 4 (shift left 2 bits) for byte offset

         sw       $t2, data($s2) # store the value in matrix element

         addi     $t2, $t2, 1    # increment value to be stored

#  Loop control: If we increment past last column, reset column counter and increment row counter

#                If we increment past last row, we're finished.

         addi     $s1, $s1, 1    # increment column counter

         bne      $s1, $t1, loop # not at end of row so loop back

         move     $s1, $zero     # reset column counter

         addi     $s0, $s0, 1    # increment row counter

         bne      $s0, $t0, loop # not at end of matrix so loop back

#  We're finished traversing the matrix.

         li       $v0, 10        # system service 10 is exit

         syscall                 # we are outta here.

#######################################################

โปรแกรมจะทำการสร้าง array ขนาด 16x16 ขึ้นมา จากนั้นก็จะทำการกำหนดค่าในarray ให้กับตัวแปร โดยเรียงค่าใน array จากซ้ายไปขวา และบนไปล่าง คือ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20....

ดังภาพ

Code Column-major

################################################################

#

#  Column-major order traversal of 16 x 16 array of words.

#  Pete Sanderson

#  31 March 2007

#

#  To easily observe the column-oriented order, run the Memory Reference

#  Visualization tool with its default settings over this program.

#  You may, at the same time or separately, run the Data Cache Simulator

#  over this program to observe caching performance.  Compare the results

#  with those of the row-major order traversal algorithm.

#

#  The C/C++/Java-like equivalent of this MIPS program is:

#     int size = 16;

#     int[size][size] data;

#     int value = 0;

#     for (int col = 0; col < size; col++) {

#        for (int row = 0; row < size; row++) }

#           data[row][col] = value;

#           value++;

#        }

#     }

#

#  Note: Program is hard-wired for 16 x 16 matrix.  If you want to change this,

#        three statements need to be changed.

#        1. The array storage size declaration at "data:" needs to be changed from

#           256 (which is 16 * 16) to #columns * #rows.

#        2. The "li" to initialize $t0 needs to be changed to the new #rows.

#        3. The "li" to initialize $t1 needs to be changed to the new #columns.

#

         .data

data:    .word     0 : 256       # 16x16 matrix of words

         .text

         li       $t0, 16        # $t0 = number of rows

         li       $t1, 16        # $t1 = number of columns

         move     $s0, $zero     # $s0 = row counter

         move     $s1, $zero     # $s1 = column counter

         move     $t2, $zero     # $t2 = the value to be stored

#  Each loop iteration will store incremented $t1 value into next element of matrix.

#  Offset is calculated at each iteration. offset = 4 * (row*#cols+col)

#  Note: no attempt is made to optimize runtime performance!

loop:    mult     $s0, $t1       # $s2 = row * #cols  (two-instruction sequence)

         mflo     $s2            # move multiply result from lo register to $s2

         add      $s2, $s2, $s1  # $s2 += col counter

         sll      $s2, $s2, 2    # $s2 *= 4 (shift left 2 bits) for byte offset

         sw       $t2, data($s2) # store the value in matrix element

         addi     $t2, $t2, 1    # increment value to be stored

#  Loop control: If we increment past bottom of column, reset row and increment column

#                If we increment past the last column, we're finished.

         addi     $s0, $s0, 1    # increment row counter

         bne      $s0, $t0, loop # not at bottom of column so loop back

         move     $s0, $zero     # reset row counter

         addi     $s1, $s1, 1    # increment column counter

         bne      $s1, $t1, loop # loop back if not at end of matrix (past the last column)

#  We're finished traversing the matrix.

         li       $v0, 10        # system service 10 is exit

         syscall                 # we are outta here.

#######################################################

โปรแกรมจะทำการสร้าง array ขนาด 16x16 ขึ้นมาเช่นเดียวกันกับ Code Row-major จากนั้นก็จะทำการกำหนดค่าในarray ให้กับตัวแปร โดยเรียงค่าใน array จากบนไปล่าง แล้วจึงจากซ้ายไปขวา

คือ           1              8              15

2              9              16

3              10           17

4              11           18

5              12           19

6              13           20

7              14           …..

ดังภาพ

การRun Code Fibonacci (ในบรรทัดที่ 7-24)

บรรทัดที่ 7         la  $s0,  fibs

โปรแกรมจะทำการทำการแบ่งคำสั่งเป็น 2 คำสั่งย่อยและจะทำการหาค่า address แรก หลังจากที่ได้ค่า address แรกที่เก็บไว้ที่ $at แล้วก็ให้นำค่าไปใส่ไว้ที่ $0 ด้วย

บรรทัดที่ 8         la  $s5,  size

Size จะเก็บค่าไว้ 20 จำนวน และโปรแกรมก็จะทำการแบ่งคำสั่งออกเป็น 2 คำสั่งย่อย โดยการหาค่าค่า address แรกมาใส่ไว่ที่ $at จากนั้นจะทำการคำนวณ size ที่ได้ ซึ่งเท่ากับ 20 จำนวน ก็จะทำการบวกขนาดไป 20 ช่อง นำ address แรกที่ได้มา 4 เพราะ 1 word มีค่าเท่ากับ 4 byte จากนั้นจะนำค่ามาใส่ไว้ที่ $s5

บรรทัดที่9          lw  $s5, 0($s5)

$s5 จะเก็บค่า addressของ memory ไว้ จากนั้นจะเอาค่าใน memory ที่ $s5 เก็บไว้ซึ่งเท่ากับ 20 มาเก็บไว้ที่ $s5 อีกครั้ง เพราะฉะนั้น $s5 ในตอนนี้จะเก็บค่า 20 ไว้

บรรทัดที่ 21       li  $s2, 1

ให้ $s2 เป็นค่าเริ่มต้น และเก็บค่า 1

บรรทัดที่ 22       sw  $s2,0($s0)

เป็นการบันทึกค่า $s2 ซึ่งตอนนี้ $s2 จะเก็บค่า 1 อยู่ใน memory ที่ $s0+0 จะเท่ากับการเก็บค่า F(0) = 1

บรรทัดที่ 23       sw  $s2,4($s0)

$s0 จะเก็บค่าaddress อะไรไว้จะต้องบวก 4 เข้าไปด้วยและนำค่าไปเก็บไว้ที่ $s2 เท่ากับว่า F(1) = 1

เมื่อ Run Code Fibonacci ตั้งแต่บรรทัดที่ 7-24 เรียบร้อยแล้ว จะได้ข้อมูลใน Data Segment ดังภาพ

การRun Code Fibonacci (ตั้งแต่บรรทัดที่ 24)

โปรแกรมจะทำการคำนวณค่าตัวเลข Fibonacci ตั้งแต่บรรทัดที่ 24 จนถึงบรรทัดสุดท้าย

จะได้ผลดังภาพ

# Compute summary 1 to n Number
.data
sum: .word 20 # N number
.text
la $s1, sum # load address of n Number
lw $s1, 0($s1) # load array size

addi $s1 , $s1 , 1 # add N number to 1 For loop 1 to n+1
li $s0 , 1 # set start loop is 1
li $s2 , 0 # set temp variable to add is 0

# Loop to compute each addition to n Number
loop: add $s2 , $s2 , $s0 # add number for loop in temp var. => temp += i
addi $s0 , $s0 , 1 # increment loop counter
bne $s0 , $s1 , loop # repeat while not finished

jal print # call print routine.

# The program is finished. Exit.
li $v0, 10 # system call for exit
syscall # Exit!

###############################################################
# Subroutine to print the numbers on one line.
.data
head: .asciiz "Summary : "
head2: .asciiz "\nHello World :)\n "
.text
print:add $t0, $zero, $a0 # starting address of array of data to be printed
add $t1, $zero, $a1 # initialize loop counter to array size
la $a0, head # load address of the print heading string
li $v0, 4 # specify Print String service
syscall # print the heading string

out: add $a0 , $s2 , $zero # load the integer to be printed (summary of 1 to n Number)
li $v0, 1 # specify Print Integer service
syscall # print fibonacci number

out2: la $a0 , head2
li $v0 , 4
syscall

jr $ra # return from subroutine
# End of subroutine to print the numbers on one line
###############################################################
ผลลัพธ์หลังจาก Run โปรแกรม

Code แสดงการหาผลรวม ตั้งแต่ 1-20 และแสดงค่า Hello World

Exersice 3 - cs621

การเขียน โปรแกรมสร้าง Link List ด้วยภาษา C

#include <stdio.h>

#include <stdlib.h>

struct node

{

            int data;

            struct node *next;

};

/*การเพิ่ม โหนดใน Linked List*/

struct node* add(struct node *head, int data)

{

            struct node *tmp;

            if(head == NULL)

{

                        head=(struct node *)malloc(sizeof(struct node));

                        if(head == NULL)

{

                                    printf("Error! memory is not available\n");

                                    exit(0);

                        }

                        head-> data = data;

                        head-> next = head;

                        }

else

{

                        tmp = head;

                        while (tmp-> next != head)

                                    tmp = tmp-> next;

                        tmp-> next = (struct node *)malloc(sizeof(struct node));

                        if(tmp -> next == NULL)

                        {

                                    printf("Error! memory is not available\n");

                                    exit(0);

                        }

                        tmp = tmp-> next;

                        tmp-> data = data;

                        tmp-> next = head;

            }

            return head;

}

/*สร้าง Function สำหรับprint ค่า*/

void printlist(struct node *head)

{

            struct node *current;

            current = head;

            if(current!= NULL)

            {

                        do

                        {

                                    printf("%d\t",current->data);

                                    current = current->next;

                        }

while (current!= head);

                        printf("\n");

            }

            else

                        printf("The list is empty\n");

}

/*การลบ โหนดใน Linked List*/

void destroy(struct node *head)

{

            struct node *current, *tmp;

            current = head->next;

            head->next = NULL;

            while(current != NULL)

{

                        tmp = current->next;

                        free(current);

                        current = tmp;

            }

}

/*ทำการเพิ่มโหนดใน Linked List และเรียกใช้ Function printlist เพื่อแสดงค่าที่อยู่ใน Linked List*/

void main()

{

            struct node *head = NULL;

            head = add(head,1);

            printlist(head);

            head = add(head,20);

            printlist(head);

            head = add(head,10);

            printlist(head);

            head = add(head,5);

            printlist(head);

           

            destroy(head);

            getchar();

            return (head);

}

 ----------------------------------------------------