-
Notifications
You must be signed in to change notification settings - Fork 0
/
heap.s
159 lines (116 loc) · 2.84 KB
/
heap.s
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
.section .data
fmt: .asciz "edi: %d, ecx: %d, ebx: %d, eax: %d\n"
.section .text
heap_build:
pushl %ebp
movl %esp, %ebp
movl 8(,%ebp,), %ecx # Tamanho do vetor
movl 12(,%ebp,), %edi # Endereço do vetor
movl %ecx, %edx
// %ecx = %ecx / 2
sarl $1, %ecx
heap_build_loop:
pushl %edi
pushl %ecx
pushl %edx
call heapify
popl %edx
popl %ecx
popl %edi
decl %ecx
cmp $0, %ecx
jge heap_build_loop
heap_build_end:
popl %ebp
ret
heap_sort:
pushl %ebp
movl %esp, %ebp
movl 8(,%ebp,), %ecx # Tamanho do vetor
movl 12(,%ebp,), %edi # Endereço do vetor
pushl %edi
pushl %ecx
call heap_build
popl %ecx
addl $4, %esp
heap_sort_loop:
// Troca primeiro e ultimo elemento
movl (%edi), %eax
xchgl -4(%edi, %ecx, 4), %eax
movl %eax, (%edi)
decl %ecx
pushl %edi
pushl $0
pushl %ecx
call heapify
popl %ecx
addl $8, %esp
cmp $0, %ecx
jg heap_sort_loop
heap_sort_end:
popl %ebp
ret
heapify:
pushl %ebp
movl %esp, %ebp
movl 8(,%ebp,), %ecx # Tamanho do vetor
movl 12(,%ebp,), %esi # Índice do nó raiz
movl 16(,%ebp,), %edi # Endereço do vetor
// Maior elemento = eax
// Nó pai = esi
movl %esi, %eax
heapify_left:
// Esquerda = 2i + 1
// %ebx = (2 * %esi)
movl %esi, %ebx
sall $1, %ebx # %ebx = ebx * 2
incl %ebx
// Esquerda > Tamanho
cmp %ecx, %ebx
jge heapify_end
// Comparar maior elemento e nó filho
movl (%edi, %ebx, 4), %edx
cmpl (%edi, %eax, 4), %edx
jle heapify_right
movl %ebx, %eax # eax = Maior elemento
heapify_right:
// Direita = 2i + 1
// %ebx = (2 * %esi) + 2
movl %esi, %ebx
sall $1, %ebx # %ebx = ebx * 2
addl $2, %ebx
// Direita > Tamanho
cmpl %ecx, %ebx
jge heapify_swap
// Comparar maior elemento e nó filho
movl (%edi, %ebx, 4), %edx
cmpl (%edi, %eax, 4), %edx
jle heapify_swap
movl %ebx, %eax # eax = Maior elemento
heapify_swap:
cmpl %esi, %eax
je heapify_end
# Troca raiz e maior elemento
movl (%edi, %eax, 4), %edx
xchgl %edx, (%edi, %esi, 4)
movl %edx, (%edi, %eax, 4)
heapify_recursion_call:
pushl %edi # Endereço do vetor
pushl %eax # Indice do maior elemento
pushl %ecx # Tamanho do vetor
call heapify
addl $12, %esp
heapify_end:
popl %ebp
ret
print_reg:
pusha
pushl %eax
push %ebx
push %ecx
push %edi
pushl $fmt
call printf
addl $20, %esp
popa
ret