COS ASSIGNMENT #5

Urvashi Balasubramaniam (1020231697)

Collaborating with Kabir Vohra.

Problem 1:
(20 points) Let s be an integer not divisible by 9; s is to be read as
input. You are asked to
compute z = oor(s/9), i.e., the largest integer smaller than or equal
to x.

Write a MIPS program for computing z.

Note that MIPS “division” operation or any oating-point
operations are NOT allowed.

Use “syscall” to read data from input and to print z as output.

HIGH LEVEL PSEUDOCODE:

/* Using xed-point multiplication method. As we can't use divide

by 9, we instead use multiply by 1/9. 1/9 = 0.000111 (repeating) in
binary, so we accept some loss and take the following precision.

Storing 1/9 as a oat will be unhelpful as we can't use oating

point operations. Therefore, convert it to an integer by left shifting
by 32 (multiplying by 2^32).

This is a precision chosen such that will help obtain the oor of the
result easily. The result will be stored as a high and low in two
separate registers, and the high will automatically give us the
result, preventing us from having to right shift by 32 to correct for
the previous shift.

We add 1 to the integer we just formulated, to make up for the

aforementioned loss. Then we multiply this "magic number" with
the user input 'n' to get the oor value.

*/
fi
fl
fl
fl
fl
fl
fl
ALGORITHM:

DONE BEFORE THE PROGRAM (to obtain magic number)

To formulate the "magic number":

Truncate (1/9=) 0.000111, multiply by 2^32 to equivalently right

shift by 32.

Add 1 to this number to account for truncating loss

DONE DURING THE PROGRAM

Print the prompt ("Enter the number..")

Get user input and store it in a variable 'n' (or saved register for
MIPS)

Store the magic number (=477218589) computed above in a

variable (or saved register)

Multiply user input n with magic number

Take the high 32-bits and print it as the oored result

// equivalently, perform a right shift by 32 bits

Print a new line (for formatting)

Exit program

MIPS CODE WITH DOCUMENTATION

.data
prompt: .asciiz "Enter number to divide by 9:"
newline: .asciiz "\n"

.text
main:
li $v0, 4 # syscall instruction to print string
la $a0, prompt # store prompt String in a0 for printing
syscall # print prompt to console
fl
 # getting user input -- assume not divisible by 9
li $v0, 5 # syscall instruction to read int input
syscall
# now properly store the input in s0
move $s0, $v0

j divider

divider:
# n * 1/9 instead of n/9
# 1/9 in binary = 0.000111 (repeating)
# multiply by 2^32 for precision (make it an int)
# ^ equivalent to a left shift of 32
# = 477218588 (magic num), store this
li $s1, 477218589 # +1 to account for loss of precision

# multiply n with magic num

mult $s0, $s1

# right shift by 32 bits (/2^32 to undo the left shift)

# ^ equivalent to taking higher 32 bits (mfhi)
mfhi $t0 # store upper halfword in t0

# print result (in t0)

li $v0, 1 # syscall instruction to print int
move $a0, $t0 # to print contents of t0
syscall

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

# exit program
li $v0, 10 # syscall to exit
syscall
DOCUMENTATION
1. https://chortle.ccsu.edu/assemblytutorial/Chapter-14/
ass14_05.html
2. https://stackover ow.com/questions/19063210/what-is-lower-
and-higher-bits
3. Division in ARM https://stackover ow.com/questions/
19844575/how-to-do-division-in-arm
4. Wikipedia division https://en.wikipedia.org/wiki/
Division_algorithm
5. Wikipedia multiplication https://en.wikipedia.org/wiki/
Multiplication_algorithm
6. computers suck at division (a painful discovery) https://
www.youtube.com/watch?v=ssDBqQ5f5_0&list=LL

OUTPUT (tested on n = 135791, 10, 35724, all correct)

fl
fl
FIGURING OUT THE ALGORITHM (WORKING):
 Problem 2:
(20 points) Write a MIPS program to collect an array of twelve
integers by the user, and then perform Insertion-Sort to sort the
array in non-descending order.

Collect the numbers from the input console using a loop, a

nd store in memory in an array called ARRAY.

Do not store the numbers in di erent non-contiguous locations or

in di erent registers. After sorting, print the sorted array with a
proper message.

HIGH LEVEL PSEUDOCODE:

InsertionSort(ARRAY):

for i = 1 to length(ARRAY) - 1:
key = ARRAY[i] // place key value correctly
j = i-1 // prev index

while j >= 0 and ARRAY[j] > key:

ARRAY[j + 1] = ARRAY[j] // shift elements right
j=j-1

ARRAY[j + 1] = key // place key element in the correct pos

for i = 0 to length(ARRAY) - 1: // output array after sorting

print ARRAY[i]

MIPS CODE
.data
array: .word 8, 3, 5, 9, 1, 6 # sample array of elements (change to
test!)
n: .word 6 # no. of elements in the array
newline: .asciiz "\n" # newline for printing and formatting

.text
.globl main

main:
ff
ff
 # load array base address
la $t0, array # t0 = base address of array
lw $t1, n # t1 = size of array (n)

# Sortinv the array with insertion sort

li $t2, 1 # loop var (i=1)

outerloop:
bge $t2, $t1, print_array # if i >= n, print (end of array)

mul $t3, $t2, 4 # o set = i * 4

add $t4, $t0, $t3 # getting address of array[i]
lw $t5, 0($t4) # key = array[i]
addi $t6, $t2, -1 #j=i-1

innerloop:
blt $t6, 0, insert_key # if j < 0, stop shifting
mul $t7, $t6, 4 # o set= j * 4
add $t8, $t0, $t7 # array[j] address
lw $t9, 0($t8)

ble $t9, $t5, insert_key # if array[j] <= key, stop shifting

sw $t9, 4($t8) # array[j+1] = array[j] (perform right shift)

addi $t6, $t6, -1 # j = j-1
j innerloop # call inner loop

insert_key:
mul $t7, $t6, 4 # o set = j * 4
add $t8, $t0, $t7 # array[j+1]'s address
sw $t5, 4($t8) # array[j+1] = key

addi $t2, $t2, 1 # i++ (loop var increment)

j outerloop # loop (outer)

# output sorted arr!

print_array:
li $t2, 0 # i = 0 (loop var again)

printloop:
ff
ff
ff
 bge $t2, $t1, exit # if i >= n, exit
mul $t3, $t2, 4 # o set = i * 4
add $t4, $t0, $t3
lw $a0, 0($t4)

li $v0, 1 # print int -- syscall instruction

syscall

# newline printing for formatting

li $v0, 4
la $a0, newline
syscall

addi $t2, $t2, 1 # i++

j printloop # loop print

exit:
li $v0, 10 # exit program -- syscall instruction
syscall

DOCUMENTATION
1. Insertion sort algorithm: https://www.geeksforgeeks.org/
insertion-sort-algorithm/
2. Rest is from MIPS documents on classroom.

OUTPUT CHECKING
ff
Input ^ = 1,9,4,6,2,7,4,8,2,39,1,0

Correctly handles duplicates for 12 input numbers.

Input:
2,323487,4,655387124,7,7267444,34823615274,813465134,2,312
349,1782643,11

Works correctly on large numbers!

Works on negative inputs too!
Problem-3:

Code in HLL:

Code in MIPS:

.data
prompt_value: .asciiz "Enter a number: "

# to build array from inputs from user

prompt_target: .asciiz "Enter the target sum: "

pair_message: .asciiz "Pair: ("

# to print the pairs

comma_space: .asciiz ", "

close_bracket: .asciiz ")\n"

no_pairs_msg: .asciiz "No pairs found\n"

newline: .asciiz "\n"

array: .space 64
# 16 integers (16 * 4 bytes)

.text

.globl main

main:

#Input 16 integers into the array

li $t0, 16
li $t1, 0 # Counter i = 0

la $t2, array

input_loop:

beq $t1, $t0, get_target # Once numbers entered, get target sum

li $v0, 4

la $a0, prompt_value

syscall

li $v0, 5

syscall

# Store integer in array

sw $v0, 0($t2)

addi $t2, $t2, 4 # Move to next element (next 4-bits)

addi $t1, $t1, 1

 j input_loop # Repeat loop and Increment counter

get_target:

#Read target sum

li $v0, 4

la $a0, prompt_target

syscall

li $v0, 5

syscall
move $t3, $v0

# Find pairs:

li $t4, 0

li $t6, 0 # Flag to check if pairs found (0 = no pairs)

outer_loop:

bge $t4, 15, check_no_pairs # Stop outer loop at 15th element

addi $t5, $t4, 1 # j = i + 1 (start after i to avoid duplicates)

inner_loop:

bge $t5, 16, increment_outer # Stop inner loop at 16th element

# Load A[i] and A[ j]

la $t2, array

sll $t7, $t4, 2 # Multiply i by 4 (get offset)

add $t2, $t2, $t7

lw $t8, 0($t2) # Load A[i] into $t8

la $t2, array

sll $t7, $t5, 2 # Multiply j by 4 (get offset)

add $t2, $t2, $t7

lw $t9, 0($t2) # Load A[ j] into $t9

add $t7, $t8, $t9 # A[i] + A[ j]

bne $t7, $t3, skip_pair # If sum != target, skip

# Step 4: Print pair

li $t6, 1 # Set flag to indicate at least one pair found

# Print "Pair: ("

li $v0, 4

la $a0, pair_message

syscall

# Print A[i]

li $v0, 1

move $a0, $t8 # Print first number

syscall
 # Print ", "

li $v0, 4

la $a0, comma_space

syscall

# Print A[ j]
li $v0, 1

move $a0, $t9 # Print second number

syscall

# Print ")\n"
li $v0, 4

la $a0, close_bracket

syscall

skip_pair:

addi $t5, $t5, 1 # j++

j inner_loop

increment_outer:

addi $t4, $t4, 1 # i++

j outer_loop

check_no_pairs:
 beq $t6, 1, exit_program # If pairs found, exit normally

# Print "No pairs found"

li $v0, 4

la $a0, no_pairs_msg

syscall

exit_program:

li $v0, 10

syscall

Outputs:

Problem-4:
i. Code in HLL:
Code in MIPS:

.data

prompt1: .asciiz "Enter first 32-bit binary string (A): "

prompt2: .asciiz "Enter second 32-bit binary string (B): "

result1: .asciiz "A in decimal: "

result2: .asciiz "\nB in decimal: "
dot: .asciiz "."

newline: .asciiz "\n"

buffer: .space 256 # Buffer for input

.text
.globl main

main:
# Prompt to get first binary string
li $v0, 4

la $a0, prompt1

syscall

li $v0, 8

la $a0, buffer

li $a1, 34
syscall

la $a0, buffer
jal parse_binary

move $s0, $v0

# Prompt to get second binary string

li $v0, 4

la $a0, prompt2

syscall

li $v0, 8

la $a0, buffer

li $a1, 34

syscall

la $a0, buffer
jal parse_binary
 move $s1, $v0

# Converting first number to decimal and printing:

li $v0, 4

la $a0, result1

syscall

move $a0, $s0

jal float_to_decimal

# Converting second number to decimal and printing:

li $v0, 4
la $a0, result2

syscall

move $a0, $s1

jal float_to_decimal

# Exit program once done

li $v0, 10

syscall

parse_binary:
li $v0, 0
parse_loop:

lb $t1, 0($a0) # Load character

beq $t1, 10, parse_done # Check for newline

beq $t1, 0, parse_done # Check for null terminator

sll $v0, $v0, 1 # Shift result left by 1

addi $t1, $t1, -48

or $v0, $v0, $t1

addi $a0, $a0, 1

j parse_loop

parse_done:

jr $ra

# Convert float to decimal and print

float_to_decimal:

# Extract components of bit string:

move $t0, $a0

# get final exponent:

srl $t1, $t0, 23 # Shift right by 23 bits

andi $t1, $t1, 0xFF # Keep only 8 bits

addi $t1, $t1, -127 # Subtract bias
 # Extracting fraction:

li $t2, 0x007FFFFF

and $t2, $t0, $t2

li $t3, 0x00800000 # Hidden bit

add $t4, $t2, $t3 # Add hidden bit to fraction

# find 2^exponent

li $t5, 1 # Initialize with 1

bltz $t1, negative_exponent

li $t6, 0 # Counter for positive exponent

pos_exp_loop:

beq $t6, $t1, exp_done

sll $t5, $t5, 1 # Multiply by 2

addi $t6, $t6, 1

j pos_exp_loop

negative_exponent:

li $t6, 0 # Counter for negative exponent

neg $t1, $t1 # Make exponent positive for loop

neg_exp_loop:
 beq $t6, $t1, exp_done

srl $t5, $t5, 1 # Divide by 2

addi $t6, $t6, 1

j neg_exp_loop

exp_done:

li $t6, 23 # Number of bits in fraction

li $t7, 0 # Integer part

li $t8, 0 # Fractional part (numerator)

li $t9, 0 # Power of 2 for current bit

# find integer part

mul $t7, $t5, $t4

srl $t7, $t7, 23

# Print integer part

move $a0, $t7

li $v0, 1

syscall

# Print decimal point

li $v0, 4

la $a0, dot

syscall

# find fractional part

mul $t8, $t4, $t5
 sll $t8, $t8, 23

# Print fractional part

move $a0, $t8

li $v0, 1

syscall

li $v0, 4

la $a0, newline
syscall

jr $ra

Outputs:

ii and iii:

Code in HLL:
Code in MIPS:
.data
prompt1: .asciiz "Enter first float (as 32-bit binary): "

prompt2: .asciiz "Enter second float (as 32-bit binary): "

result_msg: .asciiz "Result: "

overflow: .asciiz "Overflow"

underflow: .asciiz "Underflow"

newline: .asciiz "\n"

buffer: .space 33 # 32 bits + null terminator

.text
.globl main

main:

# Prompt to get first binary float input

li $v0, 4

la $a0, prompt1

syscall

li $v0, 8

la $a0, buffer
li $a1, 33

syscall

# binary string to integer representation

la $a0, buffer

jal binary_to_int

move $t0, $v0

# Prompt to get for second binary float input

li $v0, 4

la $a0, prompt2

syscall

li $v0, 8
la $a0, buffer
li $a1, 33

syscall

# binary string to integer representation

la $a0, buffer

jal binary_to_int

move $t1, $v0

# Extract sign, exponent, and mantissa (components) of first float

move $a0, $t0

jal extract_fields

move $s0, $v0 # Sign of A

move $s1, $v1 # Exponent of A

move $s2, $a1 # Mantissa of A (without implicit 1)

# Extract sign, exponent, and mantissa of second float

move $a0, $t1

jal extract_fields

move $s3, $v0 # Sign of B

move $s4, $v1 # Exponent of B

move $s5, $a1 # Mantissa of B (without implicit 1)

# Add implicit 1 to mantissas

beqz $s1, check_b_implicit

li $t2, 0x00800000
 or $s2, $s2, $t2

check_b_implicit:

beqz $s4, mantissas_ready

li $t2, 0x00800000

or $s5, $s5, $t2

mantissas_ready:

# Determine which exponent is larger by minusing

sub $t9, $s1, $s4

bgtz $t9, a_larger

bltz $t9, b_larger

j exponents_equal

a_larger: # if

# Shift mantissa B right by $t9 bits

move $t2, $t9 # $t2 = shift amount

li $t3, 24 # Maximum shift (24 bits)

bge $t2, $t3, zero_b # If shift >= 24, mantissa becomes 0

srlv $s5, $s5, $t2 # Shift right by $t2 bits

move $s4, $s1 # Update exponent B to match A

j exponents_equal

b_larger: # if
 # Shift mantissa A right by $t9 bits (absolute value)

neg $t2, $t9 # $t2 = absolute value of shift

li $t3, 24 # Maximum shift (24 bits)

bge $t2, $t3, zero_a # If shift >= 24, mantissa becomes 0

srlv $s2, $s2, $t2 # Shift right by $t2 bits

move $s1, $s4 # Update exponent A to match B

j exponents_equal

zero_a:

li $s2, 0
j exponents_equal

zero_b:

li $s5, 0

exponents_equal:

# Apply signs to mantissas

beqz $s0, a_positive

neg $s2, $s2 # Negate mantissa A if sign is 1

a_positive:

beqz $s3, b_positive

neg $s5, $s5 # Negate mantissa B if sign is 1

b_positive:

# Add mantissas
 add $t2, $s2, $s5

# Determine sign of result

li $t3, 0

bgez $t2, result_positive

li $t3, 1

neg $t2, $t2

result_positive:

move $s6, $t3

# Check if result is zero

bnez $t2, normalize_start

# if result is zero

li $s6, 0 # Sign = 0

li $s1, 0 # Exponent = 0

li $t2, 0 # Mantissa = 0

j create_result

normalize_start:

# Find position of highest set bit in $t2

li $t5, 31 # Start checking from bit 31

li $t4, 0x80000000 # Mask for highest bit

find_highest_bit:
and $t6, $t2, $t4
 bnez $t6, found_highest_bit

srl $t4, $t4, 1

addi $t5, $t5, -1

j find_highest_bit

found_highest_bit:

li $t7, 23 # position for highest bit

sub $t8, $t5, $t7

bgtz $t8, shift_right # If $t8 > 0, shift right

bltz $t8, shift_left # If $t8 < 0, shift left

j normalization_done # If $t8 = 0, no shift needed

shift_right: # potential for overflow

add $s1, $s1, $t8 # Adjust exponent: add shift amount

srlv $t2, $t2, $t8 # Shift mantissa right by $t8 bits

j normalization_done

shift_left: # potential for underflow

neg $t8, $t8 # Make shift amount positive

sub $s1, $s1, $t8 # Adjust exponent: subtract shift amount (FIXED
LINE)

sllv $t2, $t2, $t8 # Shift mantissa left by $t8 bits

normalization_done:

li $t7, 0x007FFFFF

and $t2, $t2, $t7

# Check for overflow/underflow

li $t7, 255 # Max exponent to check

bge $s1, $t7, overflow_exit

li $t7, 0 # Min exponent to check

ble $s1, $t7, underflow_exit

create_result:
# combine to get the final result

sll $t3, $s6, 31 # Shift sign to bit 31

sll $t4, $s1, 23 # Shift exponent to bits 23-30

or $t3, $t3, $t4 # Combine sign and exponent

or $t0, $t3, $t2 # Combine with mantissa

# Print result

li $v0, 4

la $a0, result_msg

syscall

move $a0, $t0

jal print_binary
 j exit

overflow_exit:

li $v0, 4

la $a0, overflow

syscall
j exit

underflow_exit:
li $v0, 4

la $a0, underflow
syscall

j exit

exit:

li $v0, 10

syscall

binary_to_int:

li $v0, 0 # Initialize result to 0

move $t0, $a0 # Copy string address to $t0

binary_loop:
lb $t1, 0($t0)
 beqz $t1, binary_done

beq $t1, 10, binary_done

sll $v0, $v0, 1

addi $t1, $t1, -48

add $v0, $v0, $t1

addi $t0, $t0, 1

j binary_loop

binary_done:

jr $ra

extract_fields:

srl $v0, $a0, 31

srl $v1, $a0, 23

andi $v1, $v1, 0xFF

# Extract mantissa (bits 0-22)

andi $a1, $a0, 0x007FFFFF

jr $ra

print_binary:
 move $t0, $a0

li $t1, 32

print_binary_loop:

sll $t0, $t0, 1

bgez $t0, print_zero

li $v0, 11

li $a0, 49
syscall

j print_binary_next

print_zero:

li $v0, 11

li $a0, 48

syscall

print_binary_next:

# Decrement counter

addi $t1, $t1, -1

bnez $t1, print_binary_loop

# Print newline
li $v0, 4
 la $a0, newline

syscall

jr $ra

Outputs:

For 2 positives:

For 2 negatives: