extended-euclide.s 2 KB
Newer Older
Benoit Perrot's avatar
Benoit Perrot committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
### runtime library
	.text
exit:
	li	$v0, 10
	syscall
print:
	li	$v0, 4
	syscall
	jr	$ra
print_int:
	li	$v0, 1
	syscall
	jr	$ra

	.data
eol:
	.asciiz "\n"

### xeucl(a, b, trace)
	.data
Sxeucl_th:			# table header
	.asciiz	"   x\t|   y\t|   g\t|   u\t|   v\t|   w\t|   q\n"
Sxeucl_td1:			# table data, first cell
	.asciiz	"   "
Sxeucl_tdn:			# table data, other cells
	.asciiz	"\t|   "
	
	.text
xeucl:
	li	$s0, 1		# x in $s0
	li	$s1, 0		# y in $s1
	move	$s2, $a0	# g = a in $s2
	li	$s3, 0		# u in $s3
	li	$s4, 1		# v in $s4
	move	$s5, $a1	# w = b in $s5

	move	$s7, $a2	# trace in $s7
	sw	$ra, ($fp)	# return address in ($fp)

	beqz	$s7, Lxeucl_loop
	beqz	$s5, Lxeucl_loop_end
	la	$a0, Sxeucl_th
	jal	print
Lxeucl_loop:
	beqz	$s5, Lxeucl_loop_end
	div	$s6, $s2, $s5	# q = g / w in $s6

	beqz	$s7, Lxeucl_loop_trace_end
Lxeucl_loop_trace:
	la	$a0, Sxeucl_td1	# trace x
	jal	print
	move	$a0, $s0
	jal	print_int
	la	$a0, Sxeucl_tdn	# trace y
	jal	print
	move	$a0, $s1
	jal	print_int
	la	$a0, Sxeucl_tdn	# trace g
	jal	print
	move	$a0, $s2
	jal	print_int
	la	$a0, Sxeucl_tdn	# trace u
	jal	print
	move	$a0, $s3
	jal	print_int
	la	$a0, Sxeucl_tdn	# trace v
	jal	print
	move	$a0, $s4
	jal	print_int
	la	$a0, Sxeucl_tdn	# trace w
	jal	print
	move	$a0, $s5
	jal	print_int
	la	$a0, Sxeucl_tdn	# trace q
	jal	print
	move	$a0, $s6
	jal	print_int

	li	$a0, eol
	jal	print
Lxeucl_loop_trace_end:
	
	mul	$t0, $s6, $s3
	sub	$t1, $s0, $t0
	move	$s0, $s3	#
	move	$s3, $t1	# (x, u) := (u, x - q * u)

	mul	$t0, $s6, $s4
	sub	$t1, $s1, $t0
	move	$s1, $s4	#
	move	$s4, $t1	# (y, v) := (v, y - q * v)

	mul	$t0, $s6, $s5
	sub	$t1, $s2, $t0
	move	$s2, $s5	#
	move	$s5, $t1	# (g, w) := (w, g - q * w)

	j	Lxeucl_loop
	
Lxeucl_loop_end:
	move	$v0, $s0
	move	$v1, $s1
	lw	$ra, ($fp)
	jr	$ra
	
### xeucl(101, 17, 1):		compute and trace extended euclide's algorithm
main:
	li	$a0, 101
	li	$a1, 17
	li	$a2, 1
	jal	xeucl
	move	$s0, $v0
	move	$s1, $v1

 	move	$a0, $s0
 	jal	print_int
 	la	$a0, eol
 	jal	print
 	move	$a0, $s1
 	jal	print_int
	la	$a0, eol
	jal	print
end:		
	j	exit