www.inf.puc-rio.br/~roberto/sb99/lab.html
para ler este texto ;-)
Para nos acostumarmos com algumas ferramentas do ambiente Linux, vamos fazer alguns pequenos programas C para conversão entre bases.
prog.c.
O pico é um editor primitivo e fácil,
similar ao edit do DOS.
O vi é o editor "oficial" do Unix,
muito poderoso mas um pouco difícil no início;
para quem se animar a usar o vi,
temos um pequeno tutorial.
gcc -Wall -o p prog.c
(-Wall faz o compilador ficar mais exigente, gerando
"warnings" para coisas estranhas; -o p dá o nome do
programa executável, p no caso.)
p ou
./p (dependendo da configuração do seu Linux,
ele não procura programas no diretório corrente [problemas de
segurança]; o ./p avisa que você realmente
quer o programa p do diretório corrente).
Agora, escreva (um ou mais) pequenos programas C para resolver as seguintes questões:
a?
A? B? 0?
Como ficam esses valores em octal?
Para completar o laboratório, escreva uma função em C que receba uma string com um número binário e retorne seu valor (cola). Escreva outra função que receba um inteiro e imprima seu valor em binário.
spim,
que simula uma CPU MIPS (usada, por exemplo,
nas workstations Silicon Graphics).
Você pode usar esse programa em casa também;
veja aqui.
Existem versões para Linux e para Windows.
É muito importante que você tenha uma cópia da documentação
do spim.
Você pode pegar essa documentação aqui,
em postscript.
Se o netscape não entender direto esse formato,
salve a página como um arquivo local e
use o programa ghostview para abrí-lo.
Você também pode pegar uma cópia dessa documentação na pasta
518 do Document Center.
No nosso laboratório, o programa xspim
(uma interface de janelas para o spim)
está instalado em /home/super-homem/i1600bp/spim/xspim.
Você pode executá-lo escrevendo tudo isso na linha de comando,
mas é mais fácil criar um "alias" para o programa.
Para isso, edite seu arquivo .tcshrc,
acrescente a linha
alias xspim /home/super-homem/i1600bp/spim/xspimsalve o arquivo, e execute esse novo alias com o comando
source .tcshrc.
Após isso, você pode executar o simulador chamando
direto xspim.
(Você também pode executar o simulador com xspim &.
Assim, ele executará em background e sua janela
de comandos não ficará bloqueada.)
Nosso primeiro programa MIPS está aqui.
(O Netscape as vezes se confunde para mostrar esses arquivos.
Salve-o em um arquivo local e use um editor para ver seu conteúdo;
ou use o comando more nome-do-arquivo
para listá-lo.)
Carregue esse programa no simulador e execute-o.
Recarregue o programa (para "ressetar" o simulador),
e execute-o novamente, passo a passo.
As primeiras instruções executadas são fixas do simulador,
e servem para preparar a chamada ao main, que é o nosso programa.
Após a instrução jal main (um "jump") o controle passa
para o nosso programa,
e você pode acompanhar sua execução passo a passo.
O que o programa faz é uma chamada a uma função do sistema operacional
para imprimir um inteiro na console.
O inteiro a ser impresso deve estar no registrador $a0 (ou $R4).
No registrador $v0 colocamos 1 (código interno para a função
print_int), e então chamamos o sistema operacional com
a instrução syscall.
Agora, modifique o programa para as tarefas abaixo; use os registradores t0-t9 para armazenar valores temporários.
(245+3)*(34+2), e imprimir o resultado.
23+4*8-2, e imprimir o resultado.
lui.
Para fazer contas (por exemplo, para conferir as respostas),
você pode usar o programa xcalc.
Esse programa tem duas rotinas (funções).
A primeira, mostraint,
mostra um inteiro na console (da mesma forma que o programa
da aula passada) e em seguida pula uma linha.
Para isso, ele chama o serviço print_string do sistema,
passando como parâmetro (em $a0, como sempre) o
endereço da string a ser impressa.
Essa string está declarada na seção de dados (.data)
do programa, com o label s1.
(A diretiva .asciiz define uma string na memória,
com um 0 no final.)
A segunda rotina, main, imprime todos os elementos
de um array de 10 inteiros armazenados na memória.
Esse array está definido com o label arr,
também na seção de dados.
(A diretiva .word define uma sequência de palavras
na memória.)
Grosso modo, o que main faz é equivalente a
int *p = arr;
int cont = 0;
while (cont < 10) {
mostraint(*p);
p++;
cont++;
}
O contador cont é armazenado no registrador $s2,
e o ponteiro p em $s1.
A cada elemento impresso, o contador é incrementado e o ponteiro
passa para a próxima posição do array (daí o incremento de 4,
que é o tamanho de cada palavra).
Quando o contador chega em 10, o loop termina.
Após entender como o programa funciona, modifique-o para executar as tarefas abaixo:
arr.
arr.
arr.
arr
pelo seu quadrado.
Equivalente ao código abaixo:
int *p = arr;
int cont = 0;
while (cont < 10) {
*p = (*p)*(*p);
p++;
cont++;
}
Para desligar a máquina: na tela de login do X digitar CTRL-ALT-F1. Antes de desligar a máquina, digitar CTRL-ALT-DEL. Esperar surgir a tela de escolha do sistema operacional. Após surgir essa tela a máquina pode ser desligada.
Examine agora esse novo programa, que manipula strings (arrays de bytes). Modifique o programa para executar as tarefas abaixo:
$a0,
e retornar eventuais resultados no registrador $v0.
Use a pilha sempre que for necessário preservar registradores durante
uma rotina;
em particular, se sua rotina chamar outra,
salve o endereço de retorno na pilha.
Tarefas:
$a0),
retornar o seu comprimento (em $v0).
$a0) e um caracter (em $a1),
retornar a primeira posição na string que contém o caracter dado,
ou 0 se a string não contiver esse caracter.
Para cada uma das tarefas, escreva uma pequena função main
que permita testar sua rotina.
and (&, faz o e lógico bit-a-bit).
Exemplo:
11010011 & 10011101 -> 10010001
or (|, ou).
Exemplo:
11010011 | 10011101 -> 11011111
xor (^, ou exclusivo).
Exemplo:
11010011 ^ 10011101 -> 01001110
not (~).
Exemplo:
~11010011 -> 00101100
shift para esquerda ( << ).
Desloca os bits de uma palavra para a esquerda,
preenchendo os bits da direita com zeros.
Exemplo:
11011100 << 3 -> 11100000
shift para direita ( >> ).
Desloca os bits de uma palavra para a direita;
pode preencher os bits da esquerda com zeros (shift lógico),
ou com o bit de sinal do valor original
(shift aritmético).
(Em C, um shift de valores sem sinal é sempre um shift lógico,
enquanto um shift de valores com sinal tem comportamento não especificado.)
Exemplo:
11011100 >> 2 -> 00110111
Observe que a operação de shift para a esquerda é equivalente a
multiplicar o número por uma potência de 2:
x << n == x*2n
(Compare a situação com o que ocorre quando deslocamos um número decimal
para a esquerda, preenchendo com zeros a sua direita.)
Em muitas CPUs, a operação de multiplicação de inteiros é bem mais
lenta que as operações de soma ou as operações lógicas.
Nessas CPUs, uma técnica de otimização é transformar uma multiplicação
por uma constante em uma sequência equivalente de somas,
subtrações e shifts.
Por exemplo, para multiplicarmos o conteúdo de $a0 por 3,
podemos fazer
sll $t0, $a0, 1 # $t0 = 2*$a0
add $a0, $a0, $t0 # $a0 = $a0+$t0 = $a0+2*$a0=3*$a0
Outro uso bastante frequente de operadores lógicos é para manipularmos
pedaços de palavras.
Muitos sistemas guardam um conjunto de valores booleanos (verdadeiro
ou falso) em uma única palavra, usando um bit por valor
(por exemplo, o 1o bit pode indicar se uma janela tem borda ou não,
o 2o bit indica se ela tem título ou não, etc.).
Para "setarmos" (colocar em 1) o n-ésimo bit de uma palavra w,
podemos executar w = w | (1 << n);
(em C, podemos escrever w |= 1 << n;)
para "resetarmos" o n-ésimo bit,
executamos w = w & ~(1 << n);
para trocarmos o n-ésimo bit (se estiver em 0 vai para 1,
se estiver em 1 vai para 0),
executamos w = w ^ (1 << n);
(observe que ou exclusivo de qualquer bit com 0 dá o próprio bit,
enquanto o ou exclusivo de qualquer bit com 1 dá a negação do bit).
Finalmente, para testarmos o n-ésimo bit de uma palavra w,
observamos que o valor (w & (1 << n)) é zero
se e somente se o bit em questão for zero.
w está em $s0 e n
está em $s1, traduza cada uma das operações acima
para assembler.
$f0, ..., $f31,
e um conjunto próprio de instruções sobre esses registradores,
diferente do conjunto de instruções disponível para os registradores
"normais".
Como primeira tarefa, para se acostumar com esse novo conjunto de instruções,
escreva uma função que receba em $a0
um ponteiro para um array de floats na memória, e em $a1
o número de elementos deste array,
e retorne (em $v0) a soma (representada em ponto flutuante)
dos elementos positivos do array.
Para testar sua função, você pode usar a declaração .float
para declarar um array,
.data
A1: .float 3.5, -10.4, 0.01, 34.0
e a syscall 2 para imprimir seu resultado.
Agora, vamos imaginar que nossa CPU não possui um co-processador.
Então, queremos implementar algumas operações sobre números com ponto
flutuante em software.
A representação de um número em ponto flutuante contém três partes:
o bit mais significativo representa o sinal do número (0 para positivo,
1 para negativo);
os próximos 8 bits representam o expoente na base 2 do número,
representado como excesso 127 (isso é, o expoente real é o número
representado pelos 8 bits menos 127);
e os 23 bits restantes representam a mantissa:
a mantissa real é o inteiro representado por esses 23 bits,
dividido por 2^23, somado de 1.
Assim, um float s1e8m31 representa o número real
((m/2^23)+1) * 2 ^ (e-127), negativo se s for 1.
Como primeiro passo, vamos usar a função monta.
Essa função recebe, em $a0, a "mantissa" do número a ser
representado, multiplicada por 2^23 (para ser sempre um número inteiro).
Em $a1, recebemos o expoente excesso 127;
e em $a2, recebemos o sinal.
A função retorna, em $v0, a representação em ponto flutuante
dos dados recebidos.
Escreva agora uma função para somar dois números representados em ponto flutuante. Para simplificar, vamos assumir que os dois números são positivos, e ignorar casos especiais (Inf, -Inf, etc.). Sua função pode seguir os seguintes passos:
monta para montar o resultado final.
(O sinal é 0, o expoente é o maior expoente entre os dois números,
e a mantissa é a soma das mantissas).
int a[10];
int i;
void f (void) {
a[i]++;
}
int *p;
char c[19];
int a[10];
int f (int i) {
p = &a[i];
return *p + c[i];
}
float b[20][10];
int f (float *a, int i, int j) {
a[i+j] = b[i][j];
return a[i+j]; /* conversao implicita */
}
struct S {
char c;
int i;
float f;
} s1;
float f (void) {
return s1.c + s1.i + s1.f;
}
Quantas instruções MIPS são necessárias para executar
o comando i++, para os casos da
variável int i ser uma global, uma local na pilha
ou uma local em um registrador?
(Ignore possíveis otimizações;
lembre-se que algumas instruções que usamos na verdade são
pseudo-instruções, que correspondem a duas instruções reais.)
Converta ("compile") as seguintes construções em C para assembler:
void f (int *p, int i) {
*p += i;
}
void main (void) {
int a = 0;
f(&a, 15);
print_int(a); /* print_int deve ser implementada via syscall */
}
struct S {
char c;
int i;
float f;
};
int f (struct S *s) {
return s->i + s->f;
}
void main (void) {
struct S s;
s.i = 10;
s.f = 10.0;
print_int(f(&s));
}
typedef struct Stack {
int top;
float val[100];
} Stack;
void push (Stack *s, float v) {
s->val[s->top++] = v;
}
float pop (Stack *s) {
return s->val[--s->top];
}
void main (void) {
Stack s;
s.top = 0;
push(&s, 10);
push(&s, 0);
push(&s, s.top);
print_float(pop(&s));
}
char s[] = "alo alo";
void copy (char *s1, char *s2) {
while ((*s1++ = *s2++)) ;
}
void main (void) {
char buff[20];
char *b1;
copy(buff, s);
b1 = buff+4;
print_string(b1);
}
char a[10][10];
void strcpy (char *s1, char *s2) {
while ((*s1++ = *s2++) != '\0') ;
}
int strlen (char *s) {
int i = 0;
while (*s++) i++;
return i;
}
int main (void) {
char *b[10];
b[0] = "alo alo";
strcpy(a[0], "oi oi");
b[1] = a[1];
strcpy(b[1], &b[0][4]);
b[2] = a[1]+strlen(a[1]);
strcpy(b[2], &a[0][2]);
print_string(b[1]);
return 0;
}
int fat (int n) {
if (n<=1) return 1;
else return n*fat(n-1);
}
void main (void) {
print_int(fat(5));
}
fat(3) é feita.
int fat (int a, int n) {
if (n<=1) return a;
else return fat(n*a, n-1);
}
void main (void) {
print_int(fat(1, 5));
}
fat(20, 3) é feita.
fat para
trocarmos a chamada recursiva por um goto:
int fat (int a, int n) {
init:
if (n<=1) return a;
else {a=n*a; n=n-1; goto init; }
}
Antenção: não codifique essa função do zero;
comece pelo código assembler da versão anterior.
Veja como modificá-lo de modo a tornar as duas implementações as
mais parecidas possíveis entre sí.
(Você acha que é possível automatizarmos essa modificação?)
fat que implementamos,
é possível usarmos um goto para eliminar
a chamada recursiva?
Por que?
main para testar o segundo ítem do
trabalho entregue por seu grupo.
Essa função deve declarar dois arrays de floats,
com os casos a serem testados.
Para cada par de números (um de cada array),
a main deverá chamar a função de vocês,
multiplicar os dois números usando a operação de
multiplicação do co-processador,
e em seguida comparar os resultados.
Para cada par testado, ela deve imprimir uma linha com o resultado
do teste, por exemplo
0.2 x 1.0 = 0.2 OK 1.0 x Inf = Inf OK -1 x 1 = 1 (erro: correto e' -1)
Preencha o array de testes com casos significativos, que testem todos os casos particulares da função de multiplicação.
nm para vermos os
símbolos de um dado arquivo objeto.
Os símbolos são classificados nas seguintes categorias:
Para os códigos D e T,
o nm indica o endereço relativo do símbolo
no arquivo objeto analisado.
Para o C (ou B), ele indica apenas o tamanho a ser alocado
pelo símbolo (por que?).
Para o U, não indica nada (pois o símbolo está indefinido).
Para exemplificar, considere o programa C abaixo:
extern int a,b,c,c1;
int a = 10;
int a1 = 20;
int d,e;
static char s1,s2[10];
static char s3[] = "uma string qualquer, com varios bytes";
int k=300;
void f1 (void) { c = 1; }
static void f2 (void) { d=e; }
void f3 (void) { fext(12); }
Compile esse programa (gcc -c, o -c indica
que a compilação deve parar no código objeto, sem gerar um executável),
e em seguida rode o nm sobre o objeto gerado.
Explique detalhadamente os resultados.