CDA3100 - SUMMER 2018 ASSIGNMENT 6 SUDOKU Objectives: Learn how to write an asse
ID: 3916145 • Letter: C
Question
CDA3100 - SUMMER 2018 ASSIGNMENT 6 SUDOKU
Objectives:
Learn how to write an assembly program that consists of functions, learn the MIPS calling conventions, and learn how to access a two-dimensional array in assembly language. This will also be an exercise in gaming and game strategy solutions.
The Classic Sudoku is a number placing puzzle based on a 9x9 grid with several given numbers. The object is to place the numbers 1 to 9 in the empty squares so that each row, each column and each 3x3 box contains the same number only once. The following is an example of a valid Sudoku puzzle.
(picture this in a sudoku grid format)
2
7
1
9
5
4
6
8
3
5
9
3
6
2
8
1
4
7
4
6
8
1
3
7
2
5
9
7
3
6
4
1
5
8
9
2
1
5
9
8
6
2
3
7
4
8
4
2
3
7
9
5
6
1
9
8
5
2
4
1
7
3
6
6
1
7
5
9
3
4
2
8
3
2
4
7
8
6
9
1
5
Specifications:
1. There will be 2 test files:
a. puzzle1.dat # Valid Puzzle.
b. puzzle2.dat # Invalid Puzzle
2. Use the sample code provided to read in the file name, open the file, and read the file into a character array.
3. The file will consist of 81 consecutive integer numbers separated by one space.
a. The first set of 9 numbers will be row 1st, the second set of 9 numbers will be the 2nd row, the third set of 9 numbers will be the 3rd Row, etc.
b. You can assume that the file will be correct and have exactly 81 numbers with no invalid integers ( i.e. less than 0 or greater than 9).
4. Your Program must incorporate the following:
a. parameter passing and return values
b. preserving register values, as presented in class
c. In addition, you should not have any conditional branch instructions that cross function boundaries.
d. A comment beside each instruction is required in the assembly program (or at a minimum a comment for a small group of related instructions) to help make your code more understandable. You should also have comments at the top of the file indicating your name, this course, and the assignment.
5. Your program must indicate whether the file that was submitted represents a valid solution, or whether there is an error in the row, column, and/or 3x3 quadrant.
Grading
In order to be graded the program must assemble and allow the grader to start the program.
- 10% - Proper declaration of the 2d array and references the array properly
- 10% - Program properly documented
- Contains comments that identifies the programmer - Contains comments that describe how the program works.
- 25% - Program is modular.
~ Has functions with at least one instance of passing parameters using standard calling conventions and preserving registers.
~ Has functions with at least one instance of returning a value using standard calling conventions and preserving registers - 55% - Correct implementation.
~ 10% Identifies valid files and continues to ask for a valid false
~ 15% Identifies valid Sudoku solutions
~ 30% Identifies errors with individual errors in Rows, Columns, or 3x3 Quadrants
input.dat File
SampleCode:
#
##################################################################
# # File: ReadFile.s #
# # Description: Query the user for a file name. We assume it #
# # must be a completepath name since we cannot anticipate where #
# # QTSPIM will expect a local file. # #
# # The routine (OFile) will read in the filename and try to #
# # open it. If cannot it will continue to ask the user for a #
# # valid filename. Once successful, the file point will be #
# # passed back to the calling routine. #
# # Author: Dr. David A. Gaitros #
# # #
# # Date: June 25th, 2018 #
# # Copyright: This code is property of FSU Department of #
# # Computer Science, written by Dr. David A. Gaitros for #
# # the sole use of students taking #
# # courses at the University. Distrubution is not #
# # authorized. #
# ###############################################################
.data
Hello: .asciiz "Hello,Enter a file name: "
NoFile: .asciiz "Error encountered, file did not open "
OkFile: .asciiz "File was opened "
Filen: .space 256 # Set aside 256 Characters
EOL: .byte ' '
sudoku: .space 164
NullCh: .word 0 # Just in case we need a null
character
# After the puzzle.
.align 2 # Align on full word boundar
.text
.globl main
main:
#
#################################################################
# Save the return address ($ra) and call the Open File function (Ofile). #
#
#################################################################
addiu $sp,$sp,-4 # Get space from the stack
sw $ra,0($sp) # Store return address on stack
la $a0,Filen # Load $a0 (parameter) with addres to store filename.
jal OFile # Call Open File
#
#################################################################
# # Save the file pointer in saved register $s1. Restore the return address #
# # and stack pointer.
#
#
##################################################################
move $s1,$v0 # Save Filename pointer to $s1
lw $ra,0($sp) # Restore return address
addiu $sp,$sp,4 # Restore stack pointer
la $a0,OkFile # Get ready to print success message
li $v0,4 # Tell syscall to print a string
syscall
li $v0,14
move $a0,$s1 # pass file pointer
la $a1,sudoku # Where to store the data
li $a2,164 # Size of buffer to read in
syscall
#
#################################################################
# # This code just to make sure we read it in properly.
#
#
#################################################################
li $v0,4
la $a0,sudoku
syscall
jr $ra # Close program
#
##################################################################
# Function to read from standard input a filename and open a file.
#
# Send the address of where to store the filename in $a0.
#
# Return the file pointer in $v0.
#
#
##################################################################
OFile:
move $t1,$a0 # Move address of where we want the file name to go to
Again: # $t1
li $v0,4 # Tell syscall to print a string
la $a0,Hello # Load address of string to print
syscall # Print string
move $a0,$t1 # Load $a0 with the address of where we want the Filename to go.
li $a1,264 # Load max size of string
li $v0,8 # Tell syscall to read a string
syscall # Read a string
#
##################################################################
# # Ok, we have read in a string.. Now we want to scan the string and find a line #
# # feed (the number 10 or hex A) and replace it with binary zeros which is a #
# # null character.
#
#
##################################################################
la $t2,EOL # EOL is the character after the filename
# declaration.
sub $t3,$t2,$t1 # Subtract the address of the EOL from the address of the Filen to get the length
move $t4,$t1 # Put address of filename in $t4
GetB: lb $t5,0($t4) # load byte into $t5
li $s5,10 # Load line feed in $s1
beq $t5,$s5,Done # Go to Done when line feed found
addiu $t4,$t4,1 # Get next byte
j GetB
Done:
li $s5,0 # Load zero (null character) into $s1
sb $s5,0($t4) # Replace the line feed with null character
#
##################################################################
# # Try to open the file, If it works move the file pointer to $v0 and return. #
# # If not, go back and read in another filename.
#
#
#################################################################
li $v0,13 # tell syscall to open a file
move $a0,$t1 # Move address of file in $a0
li $a1,0 # Open for reading
li $a2,0 # No purpose
syscall # Open file
move $s6,$v0
ble $s6,$zero,Again # Bad file, try it again.
move $v0,$s6
jr $ra
#
##################################################################
#
#################################################################
2
7
1
9
5
4
6
8
3
5
9
3
6
2
8
1
4
7
4
6
8
1
3
7
2
5
9
7
3
6
4
1
5
8
9
2
1
5
9
8
6
2
3
7
4
8
4
2
3
7
9
5
6
1
9
8
5
2
4
1
7
3
6
6
1
7
5
9
3
4
2
8
3
2
4
7
8
6
9
1
5
Sample Output: puzzlel.dat file 1112131415161718191 14151617181911 12131 71819111213141516 121311151614191718 1516141819171311121 81917121311161415 131112161415181917 614151917181213111 91718131112151614 Valid Sudoku PuzzleExplanation / Answer
Please find the MIPS Code below for Sudoku Validation Checker:-
isCorrect:
.zero 12
.LC0:
.string "%d"
readPuzzle:
pushq %rbp
movq %rsp, %rbp
subq $32, %rsp
movq %rdi, -24(%rbp)
movl $0, -4(%rbp)
jmp .L2
.L5:
movl $0, -8(%rbp)
jmp .L3
.L4:
movl -8(%rbp), %eax
movslq %eax, %rcx
movl -4(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
salq $2, %rax
leaq sudoku(%rax), %rdx
movq -24(%rbp), %rax
movl $.LC0, %esi
movq %rax, %rdi
movl $0, %eax
call __isoc99_fscanf
addl $1, -8(%rbp)
.L3:
cmpl $8, -8(%rbp)
jle .L4
addl $1, -4(%rbp)
.L2:
cmpl $8, -4(%rbp)
jle .L5
nop
nop
leave
ret
checkNum:
pushq %rbp
movq %rsp, %rbp
movl %edi, -36(%rbp)
movl %esi, -40(%rbp)
movl %edx, -44(%rbp)
movl -36(%rbp), %ecx
movl $1431655766, %edx
movl %ecx, %eax
imull %edx
movl %ecx, %eax
sarl $31, %eax
subl %eax, %edx
movl %edx, %eax
addl %eax, %eax
addl %edx, %eax
movl %eax, -20(%rbp)
movl -40(%rbp), %ecx
movl $1431655766, %edx
movl %ecx, %eax
imull %edx
movl %ecx, %eax
sarl $31, %eax
subl %eax, %edx
movl %edx, %eax
addl %eax, %eax
addl %edx, %eax
movl %eax, -24(%rbp)
movl $1, -4(%rbp)
movl $0, -8(%rbp)
jmp .L7
.L15:
movl -8(%rbp), %eax
movslq %eax, %rcx
movl -36(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl sudoku(,%rax,4), %eax
cmpl %eax, -44(%rbp)
jne .L8
movl $0, -4(%rbp)
.L8:
movl -40(%rbp), %eax
movslq %eax, %rcx
movl -8(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl sudoku(,%rax,4), %eax
cmpl %eax, -44(%rbp)
jne .L9
movl $0, -4(%rbp)
.L9:
movl -20(%rbp), %eax
movl %eax, -12(%rbp)
jmp .L10
.L14:
movl -24(%rbp), %eax
movl %eax, -16(%rbp)
jmp .L11
.L13:
movl -16(%rbp), %eax
movslq %eax, %rcx
movl -12(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl sudoku(,%rax,4), %eax
cmpl %eax, -44(%rbp)
jne .L12
movl $0, -4(%rbp)
.L12:
addl $1, -16(%rbp)
.L11:
cmpl $2, -16(%rbp)
jle .L13
addl $1, -12(%rbp)
.L10:
movl -20(%rbp), %eax
addl $2, %eax
cmpl %eax, -12(%rbp)
jle .L14
addl $1, -8(%rbp)
.L7:
cmpl $8, -8(%rbp)
jle .L15
movl -4(%rbp), %eax
popq %rbp
ret
solver:
pushq %rbp
movq %rsp, %rbp
subq $32, %rsp
movl %edi, -20(%rbp)
movl %esi, -24(%rbp)
movl -24(%rbp), %eax
movslq %eax, %rcx
movl -20(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl sudoku(,%rax,4), %eax
testl %eax, %eax
jne .L18
movl $1, -4(%rbp)
jmp .L19
.L26:
movl -4(%rbp), %edx
movl -24(%rbp), %ecx
movl -20(%rbp), %eax
movl %ecx, %esi
movl %eax, %edi
call checkNum
cmpl $1, %eax
jne .L20
movl -24(%rbp), %eax
movslq %eax, %rcx
movl -20(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
leaq (%rax,%rcx), %rdx
movl -4(%rbp), %eax
movl %eax, sudoku(,%rdx,4)
cmpl $7, -20(%rbp)
jg .L21
movl -20(%rbp), %eax
leal 1(%rax), %edx
movl -24(%rbp), %eax
movl %eax, %esi
movl %edx, %edi
call solver
cmpl $1, %eax
jne .L22
movl $1, %eax
jmp .L23
.L22:
movl -24(%rbp), %eax
movslq %eax, %rcx
movl -20(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl $0, sudoku(,%rax,4)
jmp .L20
.L21:
cmpl $7, -24(%rbp)
jg .L24
movl -24(%rbp), %eax
addl $1, %eax
movl %eax, %esi
movl $0, %edi
call solver
cmpl $1, %eax
jne .L25
movl $1, %eax
jmp .L23
.L25:
movl -24(%rbp), %eax
movslq %eax, %rcx
movl -20(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl $0, sudoku(,%rax,4)
jmp .L20
.L24:
movl $1, %eax
jmp .L23
.L20:
addl $1, -4(%rbp)
.L19:
cmpl $9, -4(%rbp)
jle .L26
jmp .L30
.L18:
cmpl $7, -20(%rbp)
jg .L28
movl -20(%rbp), %eax
leal 1(%rax), %edx
movl -24(%rbp), %eax
movl %eax, %esi
movl %edx, %edi
call solver
jmp .L23
.L28:
cmpl $7, -24(%rbp)
jg .L29
movl -24(%rbp), %eax
addl $1, %eax
movl %eax, %esi
movl $0, %edi
call solver
jmp .L23
.L29:
movl $1, %eax
jmp .L23
.L30:
movl $0, %eax
.L23:
leave
ret
rowChecker:
pushq %rbp
movq %rsp, %rbp
movl $1, -4(%rbp)
movl $0, -8(%rbp)
jmp .L32
.L38:
movq $0, -48(%rbp)
movq $0, -40(%rbp)
movq $0, -32(%rbp)
movq $0, -24(%rbp)
movl $0, -16(%rbp)
movl $0, -12(%rbp)
jmp .L33
.L37:
movl -12(%rbp), %eax
movslq %eax, %rcx
movl -8(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl sudoku(,%rax,4), %eax
subl $1, %eax
cltq
movl -48(%rbp,%rax,4), %eax
testl %eax, %eax
jne .L34
movl -12(%rbp), %eax
movslq %eax, %rcx
movl -8(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl sudoku(,%rax,4), %eax
subl $1, %eax
cltq
movl $1, -48(%rbp,%rax,4)
jmp .L41
.L34:
movl $0, -4(%rbp)
jmp .L36
.L41:
addl $1, -12(%rbp)
.L33:
cmpl $8, -12(%rbp)
jle .L37
.L36:
addl $1, -8(%rbp)
.L32:
cmpl $8, -8(%rbp)
jle .L38
cmpl $1, -4(%rbp)
jne .L39
movl $1, isCorrect(%rip)
.L39:
movl $0, %eax
popq %rbp
ret
columnChecker:
pushq %rbp
movq %rsp, %rbp
movl $0, -4(%rbp)
movl $0, -8(%rbp)
jmp .L43
.L50:
movq $0, -64(%rbp)
movq $0, -56(%rbp)
movq $0, -48(%rbp)
movq $0, -40(%rbp)
movl $0, -32(%rbp)
movl $0, -12(%rbp)
jmp .L44
.L49:
movl -8(%rbp), %eax
movslq %eax, %rcx
movl -12(%rbp), %eax
movslq %eax, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl sudoku(,%rax,4), %eax
movl %eax, -16(%rbp)
movl -16(%rbp), %eax
subl $1, %eax
cltq
movl -64(%rbp,%rax,4), %eax
testl %eax, %eax
jne .L45
movl -16(%rbp), %eax
subl $1, %eax
cltq
movl $1, -64(%rbp,%rax,4)
cmpl $1, -4(%rbp)
jne .L48
jmp .L47
.L45:
movl $1, -4(%rbp)
jmp .L47
.L48:
addl $1, -12(%rbp)
.L44:
cmpl $8, -12(%rbp)
jle .L49
.L47:
addl $1, -8(%rbp)
.L43:
cmpl $8, -8(%rbp)
jle .L50
cmpl $0, -4(%rbp)
jne .L51
movl $1, isCorrect+4(%rip)
.L51:
movl $0, %eax
popq %rbp
ret
check_box:
pushq %rbp
movq %rsp, %rbp
movq %rdi, -88(%rbp)
movq -88(%rbp), %rax
movq %rax, -24(%rbp)
movq -24(%rbp), %rax
movl (%rax), %eax
movl %eax, -28(%rbp)
movq -24(%rbp), %rax
movl 4(%rax), %eax
movl %eax, -32(%rbp)
movl $0, -4(%rbp)
movq $0, -80(%rbp)
movq $0, -72(%rbp)
movq $0, -64(%rbp)
movq $0, -56(%rbp)
movl $0, -48(%rbp)
movl $0, -8(%rbp)
jmp .L54
.L62:
movl $0, -12(%rbp)
jmp .L55
.L58:
movl -12(%rbp), %edx
movl -32(%rbp), %eax
leal (%rdx,%rax), %esi
movl -8(%rbp), %edx
movl -28(%rbp), %eax
addl %edx, %eax
movslq %eax, %rcx
movslq %esi, %rdx
movq %rdx, %rax
salq $3, %rax
addq %rdx, %rax
addq %rcx, %rax
movl sudoku(,%rax,4), %eax
movl %eax, -36(%rbp)
movl -36(%rbp), %eax
subl $1, %eax
cltq
movl -80(%rbp,%rax,4), %eax
cmpl $1, %eax
jne .L56
movl $1, -4(%rbp)
jmp .L57
.L56:
movl -36(%rbp), %eax
subl $1, %eax
cltq
movl $1, -80(%rbp,%rax,4)
addl $1, -12(%rbp)
.L55:
cmpl $2, -12(%rbp)
jle .L58
.L57:
cmpl $1, -4(%rbp)
je .L64
cmpl $0, -4(%rbp)
jne .L61
movl $1, isCorrect+8(%rip)
.L61:
addl $1, -8(%rbp)
.L54:
cmpl $2, -8(%rbp)
jle .L62
jmp .L60
.L64:
nop
.L60:
movl $0, %eax
popq %rbp
ret
.LC1:
.string "Row Checker"
.LC2:
.string "Column"
validate:
pushq %rbp
movq %rsp, %rbp
subq $192, %rsp
leaq -24(%rbp), %rax
movl $.LC1, %ecx
movl $rowChecker, %edx
movl $0, %esi
movq %rax, %rdi
movl $0, %eax
call pthread_create
leaq -32(%rbp), %rax
movl $.LC2, %ecx
movl $columnChecker, %edx
movl $0, %esi
movq %rax, %rdi
movl $0, %eax
call pthread_create
movl $0, -4(%rbp)
movl $0, -8(%rbp)
jmp .L66
.L69:
movl $0, -12(%rbp)
jmp .L67
.L68:
movl -4(%rbp), %eax
cltq
movl -8(%rbp), %edx
movl %edx, -192(%rbp,%rax,8)
movl -4(%rbp), %eax
cltq
movl -12(%rbp), %edx
movl %edx, -188(%rbp,%rax,8)
leaq -192(%rbp), %rax
movl -4(%rbp), %edx
movslq %edx, %rdx
salq $3, %rdx
addq %rax, %rdx
leaq -112(%rbp), %rax
movl -4(%rbp), %ecx
movslq %ecx, %rcx
salq $3, %rcx
addq %rcx, %rax
movq %rdx, %rcx
movl $check_box, %edx
movl $0, %esi
movq %rax, %rdi
movl $0, %eax
call pthread_create
addl $1, -4(%rbp)
addl $3, -12(%rbp)
.L67:
cmpl $6, -12(%rbp)
jle .L68
addl $3, -8(%rbp)
.L66:
cmpl $6, -8(%rbp)
jle .L69
movq -24(%rbp), %rax
movl $0, %esi
movq %rax, %rdi
movl $0, %eax
call pthread_join
movq -32(%rbp), %rax
movl $0, %esi
movq %rax, %rdi
movl $0, %eax
call pthread_join
movl $0, -4(%rbp)
jmp .L70
.L71:
movl -4(%rbp), %eax
cltq
movq -112(%rbp,%rax,8), %rax
movl $0, %esi
movq %rax, %rdi
movl $0, %eax
call pthread_join
addl $1, -4(%rbp)
.L70:
cmpl $8, -4(%rbp)
jle .L71
movl $0, %eax
leave
ret
.LC3:
.string "r"
.LC4:
.string "C:\Users\gmalaker\Desktop\puzzle.dat"
.LC5:
.string "Sudoku is correct"
.LC6:
.string "Sudoku is incorrect"
main:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl $.LC3, %esi
movl $.LC4, %edi
call fopen
movq %rax, -8(%rbp)
movq -8(%rbp), %rax
movq %rax, %rdi
call readPuzzle
call validate
movl isCorrect(%rip), %eax
cmpl $1, %eax
jne .L74
movl isCorrect+4(%rip), %eax
cmpl $1, %eax
jne .L74
movl isCorrect+8(%rip), %eax
cmpl $1, %eax
jne .L74
movl $.LC5, %edi
movl $0, %eax
call printf
jmp .L75
.L74:
movl $.LC6, %edi
movl $0, %eax
call printf
.L75:
movl $0, %eax
leave
ret
Please let me know in case of any clarifications required. Thanks!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.