Descrição e análise da implementação em
Assembly MIPS da função itoa
Alana Rocha1, Guilherme Alves2, Guilherme Nunes3 e Luiz Guilherme4
Objetivo e visão geral do documento. Este documento tem o objetivo de analisar detalhadamente
a implementação da função itoa em Assembly MIPS e sua execução no simulador PCSPIM, e é
organizado da seguinte maneira: (seção 1) apresentação da função itoa e sua respectiva
implementação em C, (seção 2) implementação da função itoa em Assembly MIPS com comentários,
(seção 3) relação das porções de código Assembly com os trechos equivalentes do código C e (seção
4) apresentação e descrição do funcionamento do simulador PCSPIM.
1. A função itoa(int)
A obtenção da string correspondente a um valor inteiro é uma requisição muito
comum em qualquer programa e, devido a esta necessidade, fez-se necessário implementar
uma função correspondente e incluí-la na biblioteca padrão C stdlib.h. Tal função tem o
identificador itoa.
A implementação da função itoa é composta basicamente de duas rotinas principais,
a saber: (a) a primeira faz a conversão e armazena os caracteres correspondente ao inteiro
na string de saída em ordem inversa e (b) a segunda faz a inversão dos caracteres na string,
ou seja, coloca os caracteres na ordem correta. A figura 1 apresenta um exemplo gráfico de
entrada e saída para cada uma das rotinas.
int
-512
char*
itoa
2
1
5
char*
-
\0
reverse
-
5
1
2
\0
FIGURA 1. Exemplo de execução das rotinas principais da função itoa para o valor -512.
Pode-se ainda detalhar a implementação da função itoa como segue:
i. O primeiro bloco de instruções é destinado a tratar números negativos da seguinte
maneira: se o valor for negativo, faz-se uma cópia do valor e o armazena na
variável sign e em seguida inverte o sinal do valor a ser convertido.
ii. O segundo bloco é responsável por fazer a conversão propriamente dita: realizase sucessivas divisões por 10 e armazena o valor do quociente para a próxima
iteração, ao resto da operação de divisão é adicionado o valor inteiro
correspondente da tabela ASCII ao caractere ‘0’ e armazenado na posição
correspondente da string [2].
iii. O último bloco de instruções da rotina itoa adiciona o caractere de sinal negativo
na string caso o valor a ser convertido seja negativo, isso é detectado por meio da
variável sign que é previamente salva no início da função.
1
2
3
4
Alana Rocha Santos – 11111BCC01, [email protected]
Guilherme Alves da Silva –11111BCC014, [email protected]
Guilherme Nunes Costa - 11111BCC036, [email protected]
Luiz Guilherme de Souza Pelegrini – 11111BCC024, [email protected]
BCC/2012-2/AOC2/TP
2
iv. Neste estágio a função já fez a conversão, porém armazenou os caracteres na string
em ordem inversa. Para fazer a operação de reordenação dos caracteres chama-se
a rotina reverse que possui um único bloco de instruções. Esse bloco de instruções
basicamente consiste em um lanço que troca os caracteres de lugar na string.
itoa (int, char*) {
.
.
(1)
.
.
.
(2)
.
.
(3)
.
.
. reverse (char*);
}
Trata número negativos
reverse (char*) {
.
.
(4)
.
}
Laço que inverte os
caracteres na string
Laço que faz a conversão
Adiciona o terminador de
string e, se necessário, o
sinal de negativo
FIGURA 2. Estrutura básica do conjunto de instruções das rotinas itoa e reverse.
A seguir é apresentado o código C completo da função itoa retirado de [1]. Observe
que cada rotina de itoa é uma função a parte, ou seja, a primeira rotina corresponde ao
código de void itoa (int, char) e a segunda corresponde ao código de void reverse
(char *s).
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void itoa (int n, char *s) {
int i, sign;
if ((sign = n) > 0) {
n = -n;
}
i = 0;
do {
s[i++] = n % 10 + ‘0’;
} while ((n /= 10) > 0);
if (sign < 0)
s[i++] = ‘-‘;
s[i] = ‘\0’;
reverse(s);
}
void reverse (char *s) {
int c, i, j;
for (i = 0,
j = strlen(s)-1;
i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
2. Implementação em Assembly MIPS
Abaixo apresentamos o código Assembly, com comentários, correspondente as
funções itoa e reverse.
Código
1
2
hello:
3
4
newln:
str:
.data
.ascii "\nDigite um
numero:"
.asciiz "\n"
.space 32
Comentário
BCC/2012-2/AOC2/TP
5
6
7
8
9
reverse:
10 strlen_loop:
11
12
13 end_strlen:
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
reverse_loop:
end_reverse:
3
.text
addi $t2, $a0, -1
lbu $t3, 1($t2)
beqz $t3, end_strlen
t2 <- a0 - 1 ; t2 guarda o índice da string
load byte unsigned
se t3 == 0 então vai para o end_strlen, ou
seja, se a string é vazia
addi $t2, $t2, 1
t2++
lbu $t3, 1($t2)
t3 <- segunda posição da string
bnez $t3, strlen_loop
se t3 != 0 então vai volta para strlen_loop
bge $a0, $t2, end_reverse
se a0 >= t2 então vai para end_reverse ;
esta é a condição de parada do for
lbu $t3, ($a0)
t3 <- a0
lbu $t4, ($t2)
t4 <- t2
sb $t3, ($t2)
t2 <- t3
sb $t4, ($a0)
a0 <- t4
addi $a0, $a0, 1
a0++
addi $t2, $t2, -1
t2-blt $a0, $t2, reverse_loop se a0 < t2 então vai para o reverse_loop
jr $31
volta para o itoa
.globl itoa
itoa:
36
37
38
39
40
41
42
43 non_neg2:
44
sb $t1, 0($a1)
addi $a1, $a1, 1
bnez $a0, itoa_loop
bgez $t0, non_neg2
li $t1, '–'
sb $t1, 0($a1)
addi $a1, $a1, 1
sb $0, 0($a1)
move $a0, $t3
45
46
47
48
49
50
51 main:
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
jal reverse
lw $31, 0($29)
addi $29, $29, 4
jr $31
sp-sp <- ra
t0 <- a0 ; t0 é o sign
t3 <- a1 ; ponteiro pro inicio do string
se a0 >= 0 então vai para non_neg
caso contrário a0 <- -a0
t2 <- 10
a0 <- a0/10
t1 <- a0 % 10
a0 <- a0/10
t1 <- t1 + 48 ; 48 corresponde em ASCII ao
caracter '0'
a1 <- t1
a1++
se a0 != 0
se t0 >= 0 então vai para non_neg2
t1 <- '-'
t1 ++ '-' ; concatenação
a1++
a1 ++ 0 ; concatenação >> finaliza string
a0 <- t3 ; a0 é ponteiro para o início da
string
chama a função de reverso
ra <- sp
sp++
retorna ao main
.globl main
addi $29, $29, -4
sw $31, 0($29)
li $v0, 4
la $a0, hello
syscall
li $v0, 5
syscall
move $a0, $v0
la $a1, str
jal itoa
la $a0, str
li $v0, 4
syscall
la $a0, newln
syscall
lw $31, 0($29)
addi $29, $29, 4
jr $31
sp++
sp <- ra
v0 <- 4
a0 <- &hello
chamada de sistema
v0 <- 5
chamada de sistema
a0 <- v0
a1 <- &str
itoa(a0)
a0 <- &str
v0 <- 4
chamada do sistema
a0 <- &newln
chamada do sistema
ra <- sp
sp-go to ra
non_neg:
itoa_loop:
addi $29, $29, -4
sw $31, 0($29)
move $t0, $a0
move $t3, $a1
bgez $a0, non_neg
sub $a0, $0, $a0
li $t2, 10
div $a0, $t2
mfhi $t1
mflo $a0
addi $t1, $t1, 48
BCC/2012-2/AOC2/TP
4
Funções especiais. Note que no decorrer do código nos deparamos com uma série
de funções não padrão da arquitetura MIPS, tais funções são explicadas a seguir:
lbu – Carrega um byte em um registrador desconsiderando o sinal
beqz – Testa se o valor de um registrador igual a zero
bnez – Testa se o valor de um registrador é diferente de zero
bgez – Testa se o valor de um registrador é maior ou igual a zero
la - Carrega um endereço, de uma variável, em um registrador
li – Carrega um valor imediato em um registrador
3. Relação entre implementações
Nesta esta seção relacionamos cada porção de código Assembly MIPS com o
respectivo código C das funções itoa e reverse.
Label
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Assembly MIPS
Código
.text
addi $t2, $a0, -1
lbu $t3, 1($t2)
beqz $t3, end_strlen
strlen_loop: addi $t2, $t2, 1
lbu $t3, 1($t2)
bnez $t3, strlen_loop
end_strlen:
bge $a0, $t2, end_reverse
reverse_loop: lbu $t3, ($a0)
lbu $t4, ($t2)
sb $t3, ($t2)
sb $t4, ($a0)
addi $a0, $a0, 1
addi $t2, $t2, -1
blt $a0, $t2, reverse_loop
end_reverse: jr $31
Linguagem C
reverse:
void reverse (char *s) {
int c, i, j;
for (i = 0,
j = strlen(s)-1;
i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
FIGURA 3. Função reverse e seus respectivos trechos de código em Assembly.
1
2
3
4
5
6
7
8
9
10
BCC/2012-2/AOC2/TP
Assembly MIPS
Código
Label
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
itoa:
non_neg:
itoa_loop:
non_neg2:
.globl itoa
addi $29, $29, -4
sw $31, 0($29)
move $t0, $a0
move $t3, $a1
bgez $a0, non_neg
sub $a0, $0, $a0
li $t2, 10
div $a0, $t2
mfhi $t1
mflo $a0
addi $t1, $t1, 48
sb $t1, 0($a1)
addi $a1, $a1, 1
bnez $a0, itoa_loop
bgez $t0, non_neg2
li $t1, '–'
sb $t1, 0($a1)
addi $a1, $a1, 1
sb $0, 0($a1)
move $a0, $t3
jal reverse
lw $31, 0($29)
addi $29, $29, 4
jr $31
5
Linguagem C
void itoa (int n, char *s) {
int i, sign;
if ((sign = n) > 0) {
n = -n;
}
i = 0;
do {
s[i++] = n % 10 + ‘0’;
} while ((n /= 10) > 0);
if (sign < 0)
s[i++] = ‘-‘;
s[i] = ‘\0’;
reverse(s);
}
11
12
13
14
15
16
17
18
19
20
21
22
23
24
FIGURA 4. Função itoa e seus respectivos trechos de código em Assembly.
4. O simulador PCSPIM
SPIM é um simulador autônomo que roda programas na arquitetura MIPS32. Ele lê e
executa programas escritos em linguagem assembly. O SPIM também nos fornece um
debugger simples e um conjunto enxuto de serviços operacionais. No entanto, ele não
executa programas em linguagem de máquina. SPIM implementa quase todo o conjunto de
instruções da arquitetura MIPS32, sendo que algumas comparações entre números de ponto
flutuante são omitidas. A arquitetura MIPS inúmeras invariantes que se diferem entre si
(i.e., a MIPS64 tem capacidade para trabalhar com inteiros e endereços de 64 bits cada), o
que significa que o simulador SPIM não irá executar programas em todos os processadores
da arquitetura MIPS.
O programa SPIM é composto de quatro segmentos dispostos na janela principal e
um console. Cada área tem sua importância. A primeira parte, chamada Registers, ficam
os registradores internos do MIPS, independente de serem usados ou não no código aberto.
Seus valores são atualizados a cada instrução executada. Podemos ver os valores sendo
alterados, facilmente, usando um break point na primeira linha do código executando, então,
instrução por instrução.
Na segunda área, Text Segment, fica o código *.asm que foi importado e cada linha
é associada com o endereço onde ela se encontra. Algumas instruções podem ser trocadas
por instruções equivalentes, mas na mesma linha se encontra mais a direita o código original.
A terceira parte, chamada de Data Segment, mostra os segmento de dados do usuário
(DATA), a pilha (STACK) e o segmento de dados do kernel (KERNEL DATA). Elas são
mostradas em duas colunas: o endereço do bloco de memória e o conteúdo do bloco.
O quarto segmento é o Messages, onde o simulador envia mensagens ao usuário. Ao
executar instrução por instrução como é o caso da figura, ele vai mostrando a instrução que
BCC/2012-2/AOC2/TP
6
está sendo executada. E por fim, o console que é a comunicação programa/usuário; onde
irão aparecer comandos de leitura de dados e escrita de resultados.
FIGURA 5. Imagem da execução do arquivo itoa.asm no software PC SPIM.
Referências
[1]
[2]
[3]
[4]
KERNIGHAN, Brian W.; RITCHIE, Dennis M. The C Programming Language. Upper Saddle
River, New Jersey: Prentice hall, 1978. 228 p.
ASCII Corporation. American Standard Code for Information Interchange Table. In: <
http://www.facom.ufu.br/~claudio/Cursos/PP/Docs/full_ASCII_table.pdf>. Acesso em:
26/03/2013.
PATTERSON, D. , HENNESSY, J. L., Organização e Projeto de Computadores: Interface
Hardware/Software, Morgan Kaufmann Series; 4th Edition; 2009;
REED, D. F., MIPS Architecture and Assembly Language Overview. In;
<http://logos.cs.uic.edu/366/notes/mips%20quick%20tutorial.htm>.
Acesso
em:
26/03/2013