I have a C code to use DFS to search for single-source-shortest-path:
#include <stdio.h>
int buffer[1025], dist[32], visited[32];
void dfs_sssp(int n, int * graph);
void dfs(int n, int * graph, int u, int cur_dist);
int main()
{
FILE * f;
int n;
// Input
f = fopen("./test.dat", "rb");
fread(buffer, sizeof(buffer), 1, f);
fclose(f);
n = buffer[0];
int * graph = (int *)(buffer + 1);
// DFS
dfs_sssp(n, graph);
// Output
for (int i = 1; i < n; i++)
{
printf("%d ", dist[i]);
}
return 0;
}
void dfs_sssp(int n, int * graph)
{
// Initialization
dist[0] = 0;
visited[0] = 0;
for (int i = 1; i < n; i++)
{
dist[i] = -1;
visited[i] = 0;
}
// Start recursion
dfs(n, graph, 0, 0);
}
void dfs(int n, int * graph, int u, int cur_dist)
{
// Update
visited[u] = 1;
if (dist[u] == -1 || dist[u] > cur_dist)
{
dist[u] = cur_dist;
}
// Traverse every unvisited neighbor
for (int v = 0; v < n; v++)
{
if (visited[v] != 0) continue;
int addr = (u << 5) + v;
if (graph[addr] == -1) continue;
dfs(n, graph, v, cur_dist + graph[addr]);
}
// Restore
visited[u] = 0;
}
and I want to translate it to MIPS32,here is my inplementation:
.data
filename: .asciiz "test.dat"
.align 4
buffer: .space 4100
##### You may add more code HERE if necessary #####
.align 4
dist: .space 128
.align 4
visited: .space 128
.text
main:
# Open file
la $a0, filename # load filename
li $a1, 0 # flag
li $a2, 0 # mode
li $v0, 13 # open file syscall index
syscall
# Read file
move $a0, $v0 # load file description to $a0
la $a1, buffer # buffer address
li $a2, 4100 # buffer size
li $v0, 14 # read file syscall index
syscall
# Close file
li $v0, 16 # close file syscall index
syscall
# Parameters
la $t0, buffer
lw $s0, 0($t0) # set $s0 to n
move $a0, $s0 # set $a0 to n
addi $a1, $t0, 4 # set $a1 to &graph
# Call DFS
jal dfs_sssp
# Print results
li $t0, 1
la $t1, dist
print_entry:
addi $t1, $t1, 4
lw $a0, 0($t1)
li $v0, 1 # print int syscall index
syscall
li $a0, ' '
li $v0, 11 # print char syscall index
syscall
addi $t0, $t0, 1
blt $t0, $s0, print_entry
# Return 0
li $a0, 0
li $v0, 17
syscall
dfs_sssp:
sub $sp, $sp, 8 # allocate stacl space
sw $ra, 4($sp) # save $ra
sw $s0, 0($sp) # save $s0
# Initialization
la $s0, dist # $s0 = &dist
la $s1, visited # $s1 = &visited
addi $t0, $zero, 0 # $t0 = 0
sw $t0, 0($s0) # dist[0] = 0
addi $t0, $zero, 0 # $t0 = 0
sw $t0, 0($s1) # visited[0] = 0
addi $t0, $zero, 1 # $t0 = 1
init_loop:
sll $t1, $t0, 2 # pointer += 4
add $t2, $s0, $t1 # $t2 = &dist[i]
add $t3, $s1, $t1 # $t3 = &visited[i]
addi $t4, $zero, -1 # $t4 = -1
sw $t4, 0($t2) # dist[i] = -1
sw $zero, 0($t3) # visited[i] = 0
addi $t0, $t0, 1 # i++
slt $t6, $t0, $a0 # $t6 = i < n
beqz $t6, init_end # if i >= n, break
j init_loop
init_end:
move $a0, $a0 # $a0 = n n
move $a1, $a1 # $a1 = &graph &graph
move $a2, $zero # $a2 = 0 source u
move $a3, $zero # $a3 = 0 cur_dist
jal dfs
lw $s0, 0($sp) # restore $s0
lw $ra, 4($sp) # restore $ra
add $sp, $sp, 8 # deallocate stack space
jr $ra
dfs:
sub $sp, $sp, 12 # allocate stack space
sw $ra, 8($sp) # save $ra
sw $a2, 4($sp) # save $a2 source u
sw $a3, 0($sp) # save $a3 cur_dist
# Update
sll $t0, $a2, 2 # u << 2
add $t1, $s1, $t0 # $t1 = &visited[u]
addi $t2, $zero, 1 # $t2 = 1
sw $t2, 0($t1) # visited[u] = 1
add $t1, $s0, $t0 # $t1 = &dist[u]
lw $t8, 0($t1) # $t8 = dist[u]
seq $t2, $t8, -1 # $t2 = (dist[u] == -1)
slt $t3, $a3, $t8 # $t3 = (cur_dist < dist[u])
or $t4, $t2, $t3 # $t4 = (dist[u] == -1) || (cur_dist < dist[u])
beq $t4, $zero, jump
sw $a3, 0($t1) # dist[u] = cur_dist
jump:
# Recursion
addi $s7, $zero, 0 # $s7 = 0 v= 0
loop:
sll $t1, $s7, 2 # v << 2
add $t2, $s1, $t1 # $t2 = &visited[v]
lw $t2, 0($t2) # $t2 = visited[v]
sne $t2, $t2, $zero # $t2 = (visited[v] != 0)
beq $t2, 1, continue
sll $t3, $a2, 5 # u << 5
add $t3, $t3, $s7 # u << 5 + v addr
sll $t3, $t3, 2 # addr << 2
add $t3, $t3, $a1 # &graph[addr]
lw $t3, 0($t3) # graph[addr]
seq $t4, $t3, -1 # $t4 = (graph[addr] == -1)
beq $t4, 1, continue
add $t5, $a3, $t3 # $t5 = cur_dist + graph[addr]
move $a2, $s7 # $a2 = v
move $a3, $t5 # $a3 = cur_dist + graph[addr]
sub $sp, $sp, 4 # allocate stack space
sw $s7, 0($sp) # save $s7
jal dfs
lw $s7, 0($sp) # restore $s7
add $sp, $sp, 4 # deallocate stack space
continue:
addi $s7, $s7, 1 # i++
slt $t6, $s7, $a0 # $t6 = i < n
beqz $t6, loop_end # if i >= n, break
j loop
loop_end:
sll $t0, $a2, 2 # u << 2
add $t1, $s1, $t0 # $t1 = &visited[u]
sw $zero, 0($t1) # visited[u] = 0
lw $a3, 0($sp) # restore $a3 cur_dist
lw $a2, 4($sp) # restore $a2 source
lw $ra, 8($sp) # restore $ra
add $sp, $sp, 12 # deallocate stack space
jr $ra
After that, I use Mars to test my assembly code. It could be assembled and run but the result is not correct. I guess there is something wrong when I call "dfs" recursively. Can some kind friends help me point out where is wrong and fix it?
I have tried to debug and compare the code in visual studio step-by-step but the progress just confuse me a lot. In addition, I tried to convert the C code in godbolt, but there is no MIPS32 option and since I am new to assembly code, I cannot understand what the code means in godbolt:
visited:
dist:
.word -1
.word -1
.word -1
.word -1
.word -1
.word -1
dfs(int, int*, int, int):
addiu $sp,$sp,-40
sw $31,36($sp)
sw $fp,32($sp)
move $fp,$sp
sw $4,40($fp)
sw $5,44($fp)
sw $6,48($fp)
sw $7,52($fp)
lui $2,%hi(visited)
lw $3,48($fp)
nop
sll $3,$3,2
addiu $2,$2,%lo(visited)
addu $2,$3,$2
li $3,1 # 0x1
sw $3,0($2)
lui $2,%hi(dist)
lw $3,48($fp)
nop
sll $3,$3,2
addiu $2,$2,%lo(dist)
addu $2,$3,$2
lw $3,0($2)
li $2,-1 # 0xffffffffffffffff
beq $3,$2,$L2
nop
lui $2,%hi(dist)
lw $3,48($fp)
nop
sll $3,$3,2
addiu $2,$2,%lo(dist)
addu $2,$3,$2
lw $3,0($2)
lw $2,52($fp)
nop
slt $2,$2,$3
beq $2,$0,$L3
nop
$L2:
lui $2,%hi(dist)
lw $3,48($fp)
nop
sll $3,$3,2
addiu $2,$2,%lo(dist)
addu $2,$3,$2
lw $3,52($fp)
nop
sw $3,0($2)
$L3:
sw $0,24($fp)
$L8:
lw $3,24($fp)
lw $2,40($fp)
nop
slt $2,$3,$2
beq $2,$0,$L4
nop
lui $2,%hi(visited)
lw $3,24($fp)
nop
sll $3,$3,2
addiu $2,$2,%lo(visited)
addu $2,$3,$2
lw $2,0($2)
nop
bne $2,$0,$L9
nop
lw $2,48($fp)
nop
sll $3,$2,5
lw $2,24($fp)
nop
addu $2,$3,$2
sw $2,28($fp)
lw $2,28($fp)
nop
sll $2,$2,2
lw $3,44($fp)
nop
addu $2,$3,$2
lw $3,0($2)
li $2,-1 # 0xffffffffffffffff
beq $3,$2,$L10
nop
lw $2,28($fp)
nop
sll $2,$2,2
lw $3,44($fp)
nop
addu $2,$3,$2
lw $3,0($2)
lw $2,52($fp)
nop
addu $2,$3,$2
move $7,$2
lw $6,24($fp)
lw $5,44($fp)
lw $4,40($fp)
jal dfs(int, int*, int, int)
nop
b $L6
nop
$L9:
nop
b $L6
nop
$L10:
nop
$L6:
lw $2,24($fp)
nop
addiu $2,$2,1
sw $2,24($fp)
b $L8
nop
$L4:
lui $2,%hi(visited)
lw $3,48($fp)
nop
sll $3,$3,2
addiu $2,$2,%lo(visited)
addu $2,$3,$2
sw $0,0($2)
nop
move $sp,$fp
lw $31,36($sp)
lw $fp,32($sp)
addiu $sp,$sp,40
j $31
nop
