Discussion :

[mikees]

Bonjour, j'essaye de coder le tri rapide en assembleur mais j'avoue avoir un peu de mal .

voici mon code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 QuickSort.s
 
	.data		# Data declaration section
array:  .word	  2,4,15,10,8,8,7,3 
title:  .asciiz  "Demonstration of QuickSort"
before: .asciiz  "\nString before: "
after:  .asciiz  "\nString  after: "
 
	.text
 
main:			# Start of code section
        li      $v0, 4
        la      $a0, title
        syscall
        la      $a0, before
        syscall
        lw      $a0, array
        syscall
# Call on QuickSort
        lw      $a0, array       # Constant pointer to string
        add     $a1, $a0, 0      # Pointer to left end
        add     $a2, $a0, 25     # Pointer to right end
        jal     QS               # The one call from main
# Print out results
        lw      $a0, after
        li      $v0, 4
        syscall
        lw      $a0, array
        syscall
# End main
        li      $v0, 10
        syscall
##
# Recursive QuickSort
# $a0 -> array (constant) - Global
# $a1 -> left end, $a2 -> right end
##
QS:     sub     $sp, $sp, 16     # \
        sw      $a1, 0($sp)      #  \
        sw      $a2, 4($sp)      #   > Save registers
        sw      $t2, 8($sp)      #  /  
        sw      $ra, 12($sp)     # / and return address
# Basecase
        bge     $a1, $a2, QSret  # Nothing to sort   
# Partition using middle element as pivot
# A[a1..a2] -> A[a1..j-1] | A[j] | A[j+1..a2]
        sub     $t3, $a1, $a0     # index i
        sub     $t4, $a2, $a0     # index j
        add     $t0, $t3, $t4     # t0 = i+j choose middle
        sra     $t0, $t0, 1       # t0 = (i+j) div 2
        add     $t0, $t0, $a0     # t0 -> A[(i+j) div 2]
        lb      $t5, 0($t0)       # t5 = pivot value 
        lb      $t6, 0($a1)       # t6 = A[i] = left element
        sb      $t5, 0($a1)       # Swap them so pivot
        sb      $t6, 0($t0)       # is first element
# 
        move    $t1, $a1         # Initially i -> first (pivot) item a1
        add     $t2, $a2, 1      # Initially j -> just past last item a2
        lb      $t0, 0($a1)      # Pivot value in t0 (in $t5)
# 
loop:
# 
i_loop: add     $t1, $t1, 1      # i=i+1;
        lb      $t5, 0($t1)      # t5 = A[i]
        bgt     $t0, $t5, i_loop # until pivot <= A[i]
j_loop: sub     $t2, $t2, 1      # j=j-1; 
        lb      $t6, 0($t2)      # t6 = A[j]
        blt     $t0, $t6, j_loop # until pivot >= A[j]
# 
        bge     $t1, $t2, test   # if i<j swap
# 
        sb      $t6, 0($t1)      # A[i] and
        sb      $t5, 0($t2)      # A[j]
# 
test:   blt     $t1, $t2, loop   # until i >= j
# 
        lb      $t5, 0($a1)      # swap a[a1] = pivot
        lb      $t6, 0($t2)      # and a[j]
        sb      $t5, 0($t2)      # now a[j] is
        sb      $t6, 0($a1)      # in its final position
# Done with partition
        lw      $a1, 0($sp)
        sub     $a2, $t2, 1
        jal     QS               # Recursive call on left
        add     $a1, $t2, 1
        lw      $a2, 4($sp)
        jal     QS               # Recursive call on right
# 
QSret:  lw      $ra, 12($sp)     # \Replace return address
        lw      $t2, 8($sp)      #  \
        lw      $a2, 4($sp)      #   > and registers
        lw      $a1, 0($sp)      #  /
        add     $sp, $sp, 16     # /
        jr      $ra
## END OF QuickSort.s

quand j'utilise le logiciel xspim pour compîler, il me met une erreur :

Execution interrupted
The following symbols are undefined:
main

Instruction references undefined symbol at 0x00400014
[0x00400014] 0x0c000000 jal 0x00000000 [main] ; 180: jal main

je ne comprends pas .. (je debute en assembleur)

[Alcatîz]

Bonjour !

L'erreur semble se produire à la ligne 180. Je suppose donc qu'elle n'a pas lieu dans ce module (qui fait beaucoup moins de lignes que ça) mais dans un code appelant ?
Sinon, la syntaxe a l'air OK.