Universidade Federal de Pernambuco

RELATÓRIO PROJETO

TORRE DE HANÓI EM ASSEMBLY

Alunas: Sara Pereira

Professor: Sergio Vanderlei Cavalcante
Sumário:

1) Capítulo 1 ……………Conhecendo a Linguagem e seus aspectos e desafios

2) Capítulo 2 ……………Importância da Tabela ASCII:

3) Capítulo 3 ……………Entendendo a Lógica da Torre de Hanói

4) Capítulo 4 ……………O temido Código

Capítulo 1 Conhecendo a Linguagem e seus aspectos e desafios

A princípio foi um desafio trabalhar com essa linguagem, visto que estávamos
acostumados a programar em linguagens de mais alto nível, como Python, logo,
tivemos que procurar entender a sintaxe do Assembly. Além de que trabalhar com
memória e registradores como o Assembly faz foi algo inusitado do ponto de vista
acadêmico. Assim, decidim noos que trabalharíamos com um compilador online
visto que tive dificuldades em baixar o Nasm.

Assim, conseguimos o nosso primeiro “Hello World” no dia 29/04/2024 e

decidimos ir mais a fundo no contexto da sintaxe do Assembly.

Primeiramente só o fato de termos printado um “Hello World” já foi motivo de

festa, em seguida, decidimos entender como funciona cada trecho dessa código.

Descrição do “Hello World”:

● O section .text sinaliza a declaração da seção do código, sendo o “.text “ o

que contém o código executável.
● O global _start define o símbolo “_start” como global e o ponto de entrada do
programa.
● Os mov edx, len move o comprimento da mensagem para o registrador “edx”
 ● Os mov ecx, msg move o endereço da mensagem para o registrador “ecx”
● Os mov ebx, 1 move o descritor do arquivo para a saída padrão para o
registrador “ebx”.
● Os mov eax, 4 move o número de chamada do sistema para sys_write para
o registrador “eax”.
● O int 0x80 interrompe o programa para chamar syscall para imprimir a
mensagem.
● O mov eax, 1 move o número de chamada de sistema para sys_exit para o
registrador “eax”.
● O section .data declara uma seção de dados
● O msg db ‘Hello, world!’, 0xa define a mensagem ‘hello, World!’ como uma
sequência de bytes e adiciona uma nova linha (0xA)
● O len equ $ - msg calcula o comprimento da mensagem subtraindo o
endereço atual ($ aponta para o final da mensagem e msg para o endereço
inicial)

Esse código definitivamente não é fácil, pois só o fato de termos que usar os
registradores dificulta muito o processo.

Alguns Registradores Importantes:

ECX: Registrador de contagem estendido. É usado para controlar loops e iterações.

Em várias partes dos códigos, ele é usado para armazenar strings que serão
impressas na tela (printar_ecx_0).

EAX: Registrador de acumulador estendido. É usado para armazenar valores de

retorno de funções e outras operações aritméticas. Pode ser usado para armazenar
valores temporários durante a conversão de strings para inteiros
(converter_string_int) e vice-versa (converter_int_string).

EBX: Registrador de base estendida.Pode ser usado como um descritor de arquivo

para especificar a saída padrão durante operações de impressão na tela.

EDX: Registrador de dados estendido. É usado para armazenar valores temporários

e cálculos intermediários. Pode ser frequentemente usado para cálculos de divisão
(converter_int_string).

EDI: Registrador de índice de destino estendido. É usado para armazenar o

endereço de memória onde os resultados devem ser armazenados, como no caso
da conversão de inteiros para strings (converter_int_string).
Algumas diretivas importantes:

Section Directives:
section .data: Esta diretiva define a seção de dados do programa, onde são
armazenadas as variáveis e constantes que serão utilizadas durante a execução.
section .bss: Esta diretiva define a seção BSS (Block Started by Symbol), onde são
armazenadas variáveis não inicializadas, que serão inicializadas durante a
execução do programa.

Data Definition Directives:

db: Esta diretiva é usada para definir bytes na memória. É usada para armazenar
strings e outros tipos de dados que requerem apenas um byte de armazenamento.

Reserve Space Directives:

resb: Esta diretiva reserva espaço na memória para armazenar uma quantidade
específica de bytes não inicializados. É frequentemente usado para definir buffers e
variáveis que serão inicializadas em tempo de execução.

Text Section and Global Directive:

section .text: Esta diretiva define a seção de texto do programa, onde estão
localizadas as instruções de código executáveis.
global _start: Esta diretiva declara que o rótulo _start é global, o que significa que
pode ser acessado de outras partes do programa ou de outros arquivos.
Capítulo 2 Importância da Tabela ASCII:

Importância da Tabela ASCII:

Representação de Caracteres: A tabela ASCII define uma correspondência entre

números e caracteres. Isso permite que os programadores representem letras,
números, símbolos e caracteres especiais em seus programas. Em assembly, por
exemplo, é comum usar números na tabela ASCII para representar caracteres em
instruções de entrada e saída.

Manipulação de Strings: Em assembly, muitas operações envolvem a manipulação

de strings, como impressão na tela, comparação de strings e manipulação de
entradas do usuário. A tabela ASCII fornece uma convenção padrão para
representar e manipular essas strings, tornando mais fácil para os programadores
escreverem código para essas operações.

Codificação de Instruções e Dados: Em muitas arquiteturas de computadores, os

bytes são usados como a menor unidade de dados e instruções. A tabela ASCII
fornece uma maneira de representar caracteres como bytes, o que é essencial para
codificar dados e instruções em programas assembly.
Padrão Internacional: A tabela ASCII é um padrão internacional amplamente
reconhecido para representar caracteres em computadores. Isso significa que os
programadores em todo o mundo podem usar a mesma tabela para representar
caracteres em seus programas, garantindo consistência e interoperabilidade entre
diferentes sistemas e linguagens de programação.
Facilidade de Uso: A tabela ASCII é simples e intuitiva de usar, com os caracteres
mais comuns ocupando posições previsíveis na tabela. Isso facilita para os
programadores trabalharem com caracteres em seus programas sem a necessidade
de memorizar códigos numéricos específicos para cada caractere.
Capítulo 3 Entendendo a Lógica da Torre de Hanói

A próxima etapa é entender a lógica da Torre de Hanói em uma linguagem

mais acessível, como Python.

Nesse código há recursividade.

Assim, a próxima etapa é usar uma linguagem mais baixo nível, como C.

Explicando a Lógica da Torre de Hanói:

Torre de Hanói é um quebra-cabeça que consiste em uma base contendo três

pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem
crescente de diâmetro, de cima para baixo. O problema consiste em passar todos
os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de
maneira que um disco maior nunca fique em cima de outro menor em nenhuma
situação. O número de discos pode variar sendo que o mais simples contém apenas
três.
Atualmente, a Torre de Hanói tem sido tradicionalmente considerada como um
procedimento para avaliação da capacidade de memória de trabalho, e
principalmente de planejamento e solução de problemas.

(https://pt.wikipedia.org/wiki/Torre_de_Hanói)

A maneira mais eficiente de resolver o quebra-cabeça é usando uma estratégia

recursiva. Aqui está um esboço dessa estratégia:

Para mover n discos de A para C (usando B como haste intermediária):

Mova n-1 discos de A para B (usando C como haste intermediária).
Mova o maior disco de A para C.
Mova os n-1 discos de B para C (usando A como haste intermediária).
Capítulo 4 O temido código

Primeiramente, depois de muito estudo, decidi fazer o código começando

com algo que se assemelharia a uma função no Python, e que no Assembly seriam
strings que poderiam ser usadas depois.

Começamos, claro, com “section .data” e depois criamos strings que serão
chamadas posteriormente, entre elas a “pergunta” que vai acompanhada da diretiva
db que pega bytes para serem usados, depois a mensagem e o “0” que significa bit
0, término da mensagem. Isso se repete até “coluna_origem” db “A” que chama a
primeira coluna de “A”, isso também se repete ate “quebra_de_linha” que usa o
número 10 da tabela de ASCII para indicar um backspace.

Depois fomos atrás de algo que armazenaria essas informações:

Tivemos que usar a declaração “.bss” para descrever para qual memória
cada string iria e como armazenaria. A “entrada”, por exemplo, usa a diretiva “resb”
(reserva de bytes), e aloca 3 bytes. Mas por que 3 bytes? Primeiro, a entrada,
segundo as instruções, pode receber até 2 dígitos, e além disso, o enter funciona
com espaço, digamos assim. Logo, cada caracter é 1 byte. A “quant_disc” se refere
ao caracter de discos, só podendo de 1 dígito. E o “len_buffer” recebe 2 bytes de
memória para alocar o comprimento de uma string.

usei o ‘mov ecx, pergunta’ para armazenar a pergunta no registrador ecx,

criei uma função usando o ‘call’ em ‘call printar_ecx_0’ com o objetivo de criar uma
função para printar a string, desde que terminada em 0. Depois, movi para ecx a
entrada em ‘mov ecx, entrada’, depois disso eu criei outra função para ler o input do
usuário, que terá 3 bits mas só será lido 2 em ‘call ler3_2’, depois fiz o mesmo, criei
funções para avaliar a entrada e depois converter string em inteiro. Um pouco
depois, eu movi ‘quant_disc’, mais especificamente seu valor anteriormente
armazenado em edx’. Criei mais funções para ‘torre_de_hanoi’, movi em ‘mov ecx,
concluido’ para o registrador ecx, e criei mais uma função para printar a string que
está em ecx, que termine com 0. Logo após isso, criei uma forma de sair do
programa, usando ‘mov eax, 1’, que é a forma de sair (código da syscall). Em ‘xor
ebx, ebx’, limpei o registrador ebx e em ‘int 0x80’ eu saí do programa.
Tabela de Syscall
 Aqui temos a continuação do código, e vemos que chamei a função
‘Torre_de_hanoi’ e ele usa o ‘cmp byte [quant_disc], 1’ para comparar a quantidade
de discos com 1, usa o ‘je disco_unico’ para se caso tenha apenas um disco e ‘jmp
mais_discos’ para se tiver mais de um.

Obs: ‘je’ = Jump if equal

Depois eu chamei o rótulo ‘disco_unico’ e movi para o registrador ecx o

‘movimento_1’ e a partir disso ele vai imprimir todos os registros com a função
‘printar_ecx_0’ e depois exibe a quantidade de discos totais em ‘printar_n_discos’.
Isso se repete até quando cehgamos em armazenar no ‘ecx’ as colunas e os
movimentos alternados e depois printamos o conteúdo armazenado no registrador
em ‘call printar_ecx’ e depois usamos o ‘jmp fim’ para ir para o fim da função.
 Aqui fizemos a torre de hanoi para mais de um disco, usando o “dec byte
[quant_disc]” usando o “dec” para decrementar (diminuir) a quantidade de disco, o
“push word [quant_disc]” para empilhar o valor da quantidade de disco, e fazemos
isso para a coluna origem que é a “A”, assim como para a auxiliar “B” e a final a “C”,
depois, com o “mov dx, [coluna_B]”, move o valor da coluna auxiliar para o
registrador dx, isso tammbém acontece com a coluna final para o registrador cx.
Depois, move o valor do registrador dx, que tem a “coluna_B”, para a
coluna_C (destino),e depois move do registrador cx, que contém a coluna_C, para a
coluna_B (auxiliar).

Após isso, chama “call torre_de_hanoi” de forma recursiva, e com “pop word
[coluna_C]”, desempilha o valor da coluna_C. e faz isso para todas as colunas
depois, e, depois disso, desempilha a quantidade de discos da pilha. Em “mov ecx,
movimento1”, ele move o valor do movimento 1 para o registrador ecx. Após isso,
ele chama “printar_ecx_0” para imprimir o conteúdo do registrador ecx.
 Com “inc byte [quant_disc]”, incrementamos 1 ao valor da quantidade de
discos, chamamos a função de printar para mostrar a quantidade de discos e
depois, em “dec byte [quant_disc]”, diminuímos em 1 a quantidade de discos. Após
isso, fazemos uma série de movimentos para o registrador ecx tanto do movimento3
quanto das colunas assim como seria para apenas um disco. Após quebrar uma
linha, movemos o valor da coluna_B para o registrador dx, e isso também para a
coluna_A para o cx. Depois movemos o valor do registrador dx para a coluna_A e o
mesmo do cx para a coluna_B, após isso chamamos recursivamente a função
torre_de_hanoi e com o “ret”,em uma seção fim, terminamos essa parte do código.

Aqui convertemos string em inteiro, usando o “mov edx, entrada[0]”, movendo

o primeiro (mais significativo) caractere da string para o registrador edx, após isso,
subtraímos o valor ASCII do caracter “0” do valor em edx, convertendo o caractere
do dígito ASCII para seu valor numérico correspondente. Depois, movemos o
segundo caractere da string para o registrador “eax”. Depois, Compara o valor em
“eax” com 0x0a (o valor hexadecimal para o caractere de nova linha '\n'). Após isso,
em “je um_algarismo”, ele verifica se o valor é igual a 0x0a ( indicando que o
segundo caractere é um /n), mostrando que tem apenas um dígito.
Depois, subtraí o valor ASCII do caractere “0” do valor em eax, convertendo o
segundo caractere de um dígito ASCII para seu valor numérico correspondente, em
“imul edx, 10” multipliquei o valor em “edx” por 10, preparando o edx para a adição
do segundo dígito, passando-o para a casa das dezenas. EM “add edx, aex”,
adicionei o valor em “eax” para “edx”,, fazendo com que “edx” tenha o valor inteiro da
conversão da string em int.
Na seção “um_algarismo” eu chamei o “ret” para retornar a função, que agora
está armazenada em “edx”.
 Aqui eu printo a string que está em “ecx”, usei o “mov eax, 4” para usar a
chamada de sistema “eax=4”, “sys_write” que é usada para escrever dados. Fiz o
mesmo com os outros, porém o “ebx” indicar que a saída é o descritor de arquivo
‘stdout’ (saída padrão) e em “mov edx, 1” significa que vai ser reservado um byte. Em
“int 0x80” ele, no ambiente linux, invocando systcalls executando a interrupção.

Aqui, move o terceiro valor para o registrador “cl”, em “cmp cl, 0x0a” ele
compara o valor do registrador “cl” com o valor de “newline” da tabela ASCII. Após
isso, ele, caso o valor for menor ou igual, não tem mais de dois algarismos,
verificando se é um caractere vazio ou se tem mais de 2. Caso não seja, será
considerada inválida.
 Aqui fazemos a validação da quantidade de caracteres, em “mov al,
entrada[0]”, ele move o primeiro caractere da entrada para o registrador “al”, depois
disso, compara esse caractere com o valor “0x31” da tabela ASCII do número 1 em
decimal em formato de string. Após isso, caso for menor, ele será considerado
inválido. Depois compara o valor no registrador “al” o valor “0x39” que na tabela
ASCII é 9, e caso seja maior será inválido. Após isso, ele move o segundo valor da
entrada para o registrador “dl” e faz a mesma coisa, tendo em “0x0a” uma
comparação com “newline” e caso for, vai para um algarismo de validação. O resto é
igual.
 Nesse caso vemos a questão da validação tendo em “jmp valido” para caso o
valor seja válido ele pule o processo. No entanto, caso não seja, ele faz isso:
movendo o registrador da mensagem para “ecx”, e chama “call printar_ecx_0” para
printar. Após isso, ele move para “ecx” a quebra_de_linha e printa. Após isso, ele
reinicia. Caso for válido, ele chama o “ret”.

Aqui, usei a função para converter inteiro em string,

decrementado/diminuindo o ponteiro “edi”, depois em “xor edx, edx” em zero esse
registrador pois ele vai ser usado em “div”, após isso, eu movo o valor 10 para o
registrador “ecx”, pois estou usando um valor de base 10. Após isso eu divido o valor
“eax” pelo de “ecx”, tendo o resto armazenado em “ecx”. Depois adiciono o valor de
ASCII de 0 para o resto do módulo da divisão, convertendo o dígito para seu valor
correspondente na tabela ASCII. Depois em “mov [edi], dl”, ele armazena o caractere
resultante na posição apontada por “edi”, depois em “test eax, eax” ele testa se o
valor resultante, armazenado em “eax” é zero e se não for, “jnz convertere_int_string”
ele faz a recursão, chamando a função novamente.

Aqui printamos o número de discos, em “ movzx eax, byte [quant_disc]”

movemos o valor da variável quant_disc para o registrador “eax” (8 bits) e preenche
os bits anteriores com 0. Em “lea edi, [len_buffer + 2]”, carregamos o endereço de
memória apontado por EDI, usando um offset de 2, sendo “lea” (loa effective adress)
que carrega o endereço que será apontado como ponto inicial. Depois chama a
função para converter os valores, depois em “mov eax, 4” prepara o registrador com
o número de chamadas de sistemas 4, que significa imprimir (sys_write). Depois
prepara o registrador “ebx” com o número 1 como descritor de arquivo. Em “lea edx,
[edi]” o edx aponta para o endereço de “edi”, que carrega a string convertida em
“edx”, depois em “lea edx, [len_buffer+2]” ele carrega o endereço final no registrador
“edx”. Daí, em “sub edx, ecx” ele calcula o comprimento da string subtraindo os
endereços de início (ecx) e o final (edx), tendo o resultado armazenado em “edx”. Em
“int 0x80” ele faz a interrupção do sistema.
Código Completo:

section .data
pergunta db 'Digite o Número de Discos', 0
movimento_1 db 'Mova o Disco ', 0
movimento_2 db ' até a coluna ', 0
movimento_3 db ' da coluna ', 0
concluido db ' Concluído! ', 0
entrada_invalida db 'Sua entrada é inválida, digite novamente.', 0
coluna_A db 'A', 0
coluna_B db 'B', 0
coluna_C db 'C', 0
quebra_de_linha db 10, 0

section .bss
entrada resb 3
quant_disc resb 1
len_buffer resb 2

section .text
global _start

_start:
inicio:
mov ecx, pergunta
call printar_ecx_0
mov ecx, entrada
call ler_3_2
call avaliar_entrada
call converter_string_int
mov [quant_disc], edx
call torre_de_hanoi
mov ecx, concluido
call printar_ecx_0

mov eax, 1
xor ebx, ebx
int 0x80

torre_de_hanoi:
cmp byte [quant_disc], 1
je disco_unico
jmp mais_discos
disco_unico:
mov ecx, movimento_1
call printar_ecx_0
call printar_n_discos
mov ecx, movimento_3
call printar_ecx_0
mov ecx, coluna_A
call printar_ecx_0
mov ecx, movimento_2
call printar_ecx_0
mov ecx, coluna_C
call printar_ecx_0
 mov ecx, quebra_de_linha
call printar_ecx
jmp fim

mais_discos:
dec byte [quant_disc]
push word [quant_disc]
push word [coluna_A]
push word [coluna_B]
push word [coluna_C]

; Trocando o valor das colunas auxiliar e destino

mov dx, [coluna_B]
mov cx, [coluna_C]
mov [coluna_C], dx
mov [coluna_B], cx

call torre_de_hanoi

pop word [coluna_C]

pop word [coluna_B]
pop word [coluna_A]
pop word [quant_disc]

mov ecx, movimento_1

call printar_ecx_0

inc byte [quant_disc]

call printar_n_discos
dec byte [quant_disc]

mov ecx, movimento_3

call printar_ecx_0

mov ecx, coluna_A

call printar_ecx_0

mov ecx, movimento_2

call printar_ecx_0

mov ecx, coluna_C

call printar_ecx_0

mov ecx, quebra_de_linha

call printar_ecx

mov dx, [coluna_B]

mov cx, [coluna_A]
mov [coluna_A], dx
mov [coluna_B], cx

call torre_de_hanoi

fim:
ret
converter_string_int:
mov edx, entrada[0]
sub edx, '0'
mov eax, entrada[1]

cmp eax, 0x0a

je um_algarismo

sub eax, '0'

imul edx, 10
add edx, eax

um_algarismo:
ret

printar_ecx:
mov eax, 4
mov ebx, 1
mov edx, 1
int 0x80
ret

printar_ecx_0:
printar_loop:
mov al, [ecx]
cmp al, 0
je printar_exit
call printar_ecx
inc ecx
jmp printar_loop

printar_exit:
ret

ler_3_2:
mov eax, 3
mov ebx, 0
mov edx, 2
int 0x80
ret

avaliar_entrada:
mov cl, entrada[2]
cmp cl, 0x0a
jle quantidade_caracteres_valida
jmp invalido

quantidade_caracteres_valida:
mov al, entrada[0]
cmp al, 0x31
jl invalido
cmp al, 0x39
jg invalido

mov dl, entrada[1]

 cmp dl, 0x0a
je um_algarismo_validacao

cmp dl, 0x30

jl invalido
cmp dl, 0x39
jg invalido

um_algarismo_validacao:
jmp valido

invalido:
mov ecx, entrada_invalida
call printar_ecx_0
mov ecx, quebra_de_linha
call printar_ecx
jmp inicio

valido:
ret

converter_int_string:
dec edi
xor edx, edx
mov ecx, 10
div ecx
add dl, '0'
mov [edi], dl
test eax, eax
jnz converter_int_string
ret

printar_n_discos:
movzx eax, byte [quant_disc]
lea edi, [len_buffer + 2]
call converter_int_string

mov eax, 4
mov ebx, 1
lea ecx, [edi]
lea edx, [len_buffer + 2]
sub edx, ecx
int 0x80
ret