QTSPIM # Description: # # Problem Statement: Allocate a dynamic array of custom
ID: 3600322 • Letter: Q
Question
QTSPIM
# Description:
#
# Problem Statement: Allocate a dynamic array of custom length to store double precision float values. Read the double precision values one by one from
# the user and store them into the previously declared array. Atlast print the "sum" and "average" of array elements.
#
# In this program there are three subporograms. All the arguments will be passed through stack.
# 1. allocate_array:
# Called from "main".
# IN: None
# OUT: Base Address of the array, Length of the array.
# Function: Takes a valid array length from the user and allocate an array to store double precision float values of the
# user specified length.
# 2. read_double_array:
# Called from "main".
# IN: Base Address of the array, Length of the array.
# OUT: Sum of the array elements, average of array elements.
# Function: This subprogram reads double precision float values from the user one by one and store them in the previously
# decalred array sequentially. It stops taking input from the user when the array is filled. Then it calls another
# subprogram named "get_sum_avg" to get the sum and average of all the elements of the array. It passes the base address
# and the length of the array to the "get_sum_avg" subprogram and gets back "sum" and "average" of all the elements.
# Then it returns the sum and average to the main.
# 3. get_sum_avg:
# Called from "read_double_array" subprogram.
# IN: Base Address of the array, Length of the array.
# OUT: Sum of the array elements, average of array elements.
# Function: This subprogram calculate the sum of all the elements of the array by traversing through the array. Then calculate the
# average by dividing the sum by number of elements. Then it returns the sum and average to the "read_double_array" subprogram.
#
# Main:
# => Call "allocate_array" subprogram to allocate the dynamic array.
# => Store the base address and length of the array into static variables.
# => Call "read_double_array" subprogram. It reads the values one by one from the user, put them in the array. Once It has finish reading
# values call "get_sum_avg" subprogram. To calculate sum and average of the array elements. Return sum and average to "main".
# => Calculate sum and average of array elements and return those to "read_double_array" subprogram.
# => Fetch "sum" and "average" from stack after returning from read_double_array" subprogram and put them into double type static variables.
# => Print sum and average to the console.
#
###########################################################
###########################################################
# Register Usage
# $t0 Holds array base address (temporarily)
# $t1 Holds array length (temporarily)
# $t2
# $t3
# $t4
# $t5
# $t6
# $t7
# $t8
# $t9 temporary register
# $f4|$f5 Holds array sum (double-precision floating-point)
# $f6|$f7 Holds array average (double precision floating-point)
###########################################################
.data
sum_p: .asciiz "Array sum is: "
average_p: .asciiz "Array average is: "
sum: .double 0.0
average: .double 0.0
nextline_p: .asciiz " " #
# declare words to hold dynamic array base and array length
array_pointer_p: .word 0 # holds address dynamic array pointer (address)
array_size_p: .word 0 # hold length of dynamic array (value)
###########################################################
.text
main:
# Allocating space in Stack for IN/OUT argument.
jal allocate_array # Calling "allocate_array" subprogram.
# Load back the returned base address of dynamic array
# Load back the returned length of dynamic array
# Deallocate previously allocated space from stack.
la $t9, array_pointer_p # Store the base address of the array in static variable.
la $t9, array_size_p # Store the length of the array in static variable.
addi $sp, $sp, -24 # Allocate space in stack for IN/OUT arguments. 2-IN(Word)/2-OUT(Double Precision Float)
# Store the base address of array in stack as argument IN.
# Store the length of array in stack as argument IN.
jal read_double_array # Call "read_double_array" subporogram.
# Load back returned sum of array elements from stack
# Load back returned average of array elements from stack
# Deallocate previously allocated space from stack.
la $t9, sum # Store the sum in static variable.
la $t9, average # Store the average in static variable.
li $v0, 4
la $a0, sum_p
syscall
# Print the sum. Sum is of type double so syscode is '3' and argument IN register is $f12.
li $v0, 4
la $a0, nextline_p
syscall
li $v0, 4
la $a0, average_p
syscall
# Print the average. Average is of type double so syscode is '3' and argument IN register is $f12.
mainEnd:
li $v0, 10
syscall # Halt
###########################################################
# allocate_array subprogram
#
# Subprogram description:
# This subprogram receives no argument IN. This subprogram prompts user for array length and validate the array length.
# Then, allocate a dynamic array to hold double precision float values of the specified length. Remember size of a double precision
# float value is 8 bytes. So, to convert the array length/ number of elements into total number of bytes you have to multiply the
# length by 8. After allocating the array, this subprogram should return the base address and the length to the "main" using stack.
#
#
###########################################################
# Arguments IN and OUT of subprogram
# $sp+0 Holds array base address (OUT)
# $sp+4 Holds array length (OUT)
###########################################################
# Register Usage
# $t0
# $t1 Holds array length(Optional)
###########################################################
.data
allocate_array_prompt_p: .asciiz "Enter the array length: "
allocate_array_error_p: .asciiz "Please enter a value greater than 0 "
###########################################################
.text
allocate_array:
li $v0, 4
la $a0, allocate_array_prompt_p # Prompt for array length.
syscall
li $v0, 5 # Read the array length.
syscall
blez $v0, allocate_array_error # Validate array length.
move $t1, $v0
move $a0, $v0 # Allocate dynamic array to store double precision float values.
# Store base address of the dynamic array in stack to return.
# Store length of the dynamic array in stack to return.
allocate_array_end:
jr $ra # jump back to the main
allocate_array_error:
li $v0, 4
la $a0, allocate_array_error_p # Print conditional error message.
syscall
b allocate_array
###########################################################
# read_double_array subprogram
#
# Subprogram description:
# Reads double-precision floating-point numbers into an array. Print a prompt before reading each double number. Once the array is filled it will
# stop reading numbers from the user and call another subprogram named "get_sum_avg" to claculate the sum and average of all the array elements.
# It returns calculated sum and average to the "main".
#
###########################################################
# Arguments IN and OUT of subprogram
# $sp+0 Holds array base address (IN)
# $sp+4 Holds array length (IN)
# $sp+8 Holds Sum of the array elements (OUT)
# $sp+16 Holds average of the array elements (OUT)
# Size of stack increase by 4 bytes to call "get_sum_avg" subprogram from inside of this subprogram.
# $sp+0 Backs up the content of $ra register.
# Size of stack increase by 24 bytes to accomodate IN&OUT arguments of "get_sum_avg" subprogram.
# $sp+0 Holds array base address (IN)
# $sp+4 Holds array length (IN)
# $sp+8 Holds Sum of the array elements (OUT)
# $sp+16 Holds average of the array elements (OUT)
###########################################################
# Register Usage
# $t0 Holds array base address
# $t1 Holds array length/loop countdown
# $f0|$f1 Holds array entry
# $f4|$f5 Holds sum
# $f6|$f7 Holds average
###########################################################
.data
read_double_array_prompt_p: .asciiz "Enter a real number: "
###########################################################
.text
read_double_array:
# save arguments so we do not lose them
lw $t0, 0($sp) # load array base address
lw $t1, 4($sp) # load array length
read_double_array_loop:
blez $t1, read_double_array_sum_avg_calc # while($t1 > 0)
li $v0, 4 # prompt and read a number
la $a0, read_double_array_prompt_p
syscall
# read double-precision floating-point number
# read double-precision floating-point number
# increment array pointer (address) to next two words (each double-precision floating-point number is 8 bytes)
addi $t1, $t1, -1 # decrement array counter (index)
b read_double_array_loop # branch unconditionally back to beginning of the loop
read_double_array_sum_avg_calc:
lw $t0, 0($sp) # load array base address from stack
lw $t1, 4($sp) # load array length from stack
# Allocate space in stack to backup $ra.
# Backing up the current value of $ra in stack.
# Size of stack increase by 24 bytes to accomodate IN&OUT arguments of "get_sum_avg" subprogram.
# store array base address in stack to pass it as an argument IN.
# load array length in stack to pass it as an argument IN.
jal get_sum_avg # Call "get_sum_avg" subporogram.
# Load back returned sum of elements from stack.
# Load back returned average of elements from stack.
# Deallocate previously allocated space for "get_sum_avg" subporogram from stack.
# Load backed up $ra value from stack, so that this subprogram can returned to main.
# Deallocate the space from stack which was allocated to back-up content of $ra.
read_double_array_end:
# Return sum
# Return average
jr $ra # jump back to the main
###########################################################
# get_sum_avg subprogram
#
# Subprogram description:
# Calculate sum and average of an array of doubles. First calculate the sum of all the elemnts of the array by traversing through the array and then calculate
# the average by dividing the sum by length. It returns calculated sum and average to "read_double_array" subprogram.
#
# Remember, to calculate average we need to divide sum (:: double) / (:: integer)
# But there is no type promotion (or widening primitive conversion)in MIPS, which mean as a programmer we have to
# implicitly convert count to double before being able to sum by count.
#
###########################################################
# Arguments IN and OUT of subprogram
# $sp+0 Holds array base address (IN)
# $sp+4 Holds array length (IN)
# $sp+8 Holds array sum {double precision floating-point number} (OUT)
# $sp+16 Holds array average {double precision floating-point number} (OUT)
###########################################################
# Register Usage
# $t0 Holds array index address
# $t1 Holds array length/loop countdown
# $t2 Holds loop countdown
# $f4|$f5 Holds array Sum
# $f6|$f7 Holds array Average
# $f8|$f9 Holds array value/Count
###########################################################
.data
get_sum_avg_invalid_count_p: .asciiz "Invalid count, cannot calculate average "
###########################################################
.text
get_sum_avg:
# save arguments so we do not lose them
# load array base address
# load array length
li.d $f4, 0.0 # initialize sum to zero
li.d $f6, 0.0 # initialize average to zero
move $t2, $t1 # copy length into $t2 so we do not lose it
bgtz $t1, get_sum_avg_valid_count # if($t1 <= 0) then print error message and return 0.0 for both sum and average
li $v0, 4 # print invalid count error message
la $a0, get_sum_avg_invalid_count_p
syscall
b get_sum_avg_end # branch unconditionally to the end of subprogram
get_sum_avg_valid_count:
get_sum_avg_loop:
blez $t2, get_sum_avg_loop_end # while($t2 > 0)
# load array value
# add the number with the sum and put the result back to the sum
# increment array pointer (address) to next two words (each double-precision floating-point number is 8 bytes)
addi $t2, $t2, -1 # decrement array counter (index)
b get_sum_avg_loop # branch unconditionally back to beginning of the loop
get_sum_avg_loop_end:
# move to co-processor 1 from $t1
# convert count to double
# $f6|$f7 <-- $f4|$f5 / $f8|$f9
get_sum_avg_end:
# return sum
# return average
jr $ra # jump back to the "read_double_array" subporogram.
Explanation / Answer
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
public class SemiMagic {
public static boolean isFullSolution(int[][] square) {
// TODO: Complete this method
return false;
}
public static boolean reject(int[][] square) {
// TODO: Complete this method
return false;
}
public static int[][] extend(int[][] square) {
// TODO: Complete this method
return null;
}
public static int[][] next(int[][] square) {
// TODO: Complete this method
return null;
}
static void testIsFullSolution() {
// TODO: Complete this method
}
static void testReject() {
// TODO: Complete this method
}
static void testExtend() {
// TODO: Complete this method
}
static void testNext() {
// TODO: Complete this method
}
/**
* Returns a string representation of a number, padded with enough zeros to
* align properly for the current size square.
* @param num the number to pad
* @param size the size of the square that we are padding to
* @return the padded string of num
*/
static String pad(int num, int size) {
// Determine the max value for a square of this size
int max = size * size;
// Determine the length of the max value
int width = Integer.toString(max).length();
// Convert num to string
String result = Integer.toString(num);
// Pad string with 0s to the desired length
while (result.length() < width) {
result = " " + result;
}
return result;
}
/**
* Prints a square
* @param square the square to print
*/
public static void printSquare(int[][] square) {
if (square == null) {
System.out.println("Null (no solution)");
return;
}
int size = square.length;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(pad(square[i][j], size) + " ");
}
System.out.print(" ");
}
}
/**
* Reads a square of a specified size from a plaintext file
* @param filename the name of the file to read from
* @param size the size of the square in the file
* @return the square
* @throws FileNotFoundException if the named file is not found
*/
public static int[][] readSquare(String filename, int size)
throws FileNotFoundException {
Scanner scanner = new Scanner(new File(filename));
int[][] square = new int[size][size];
int val = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
square[i][j] = scanner.nextInt();
}
}
return square;
}
/**
* Solves the magic square
* @param square the partial solution
* @return the solution, or null if none
*/
public static int[][] solve(int[][] square) {
if (reject(square)) return null;
if (isFullSolution(square)) return square;
int[][] attempt = extend(square);
while (attempt != null) {
int[][] solution;
solution = solve(attempt);
if (solution != null) return solution;
attempt = next(attempt);
}
return null;
}
public static void main(String[] args) {
if (args.length >= 1 && args[0].equals("-t")) {
System.out.println("Running tests...");
testIsFullSolution();
testReject();
testExtend();
testNext();
} else if (args.length >= 1) {
try {
// First get the specified size
int size = Integer.parseInt(args[0]);
int[][] square;
if (args.length >= 2) {
// Read the square from the file
square = readSquare(args[1], size);
} else {
// Initialize to a blank square
square = new int[size][size];
}
System.out.println("Initial square:");
printSquare(square);
System.out.println(" Solution:");
int[][] result = solve(square);
printSquare(result);
} catch (NumberFormatException e) {
// This happens if the first argument isn't an int
System.err.println("First argument must be the size");
} catch (FileNotFoundException e) {
// This happens if the second argument isn't an existing file
System.err.println("File " + args[1] + " not found");
}
} else {
System.err.println("See usage in assignment description");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.