Laboratório 10 - Convenção de Chamada (ABI) e Integração C/Assembly

Objetivo

Implementar rotinas em Assembly RISC-V (RV32IM) estritamente compatíveis com a Application Binary Interface (ABI) para integração e vinculação (linking) com programas escritos em linguagem C.

Motivação

No desenvolvimento de sistemas de software modernos é comum combinar código de alto nível em C com rotinas de baixo nível escritas em Assembly. Enquanto a linguagem C oferece expressividade para estruturar o fluxo de controle e gerenciar estruturas de dados complexas, o Assembly permite interagir diretamente com o sistema operacional via chamadas de sistema (syscalls) e otimizar rotinas críticas de processamento.

Para que funções escritas em Assembly possam ser chamadas de forma transparente por funções compiladas em C (e vice-versa), ambos os lados devem respeitar um contrato binário padronizado: a Application Binary Interface (ABI). Esse contrato define:

Layout de Memória: Como tipos primitivos, vetores e estruturas (struct) são alinhados e organizados em memória.
Passagem de Argumentos e Retorno: Como parâmetros inteiros e ponteiros são enviados nos registradores a0–a7 e como o valor de retorno é devolvido em a0.
Preservação de Registradores: Quais registradores podem ser livremente modificados pela função chamada (caller-saved: t0–t6, a0–a7) e quais devem obrigatoriamente ter seus valores originais preservados na pilha e restaurados antes do retorno (callee-saved: s0–s11, sp e o endereço de retorno ra).

Neste laboratório, você colocará a ABI do RISC-V em prática implementando uma biblioteca em Assembly que será vinculada diretamente a um programa principal em C (example.c). Para exercitar diferentes padrões de assinatura de função, manipulação de ponteiros, estruturas encadeadas e vetores, a biblioteca é dividida em três módulos práticos:

Funções Utilitárias de Entrada/Saída e Conversão: Implementação das rotinas fundamentais da biblioteca padrão C (puts, gets, atoi, itoa e exit) utilizando syscalls Linux/RISC-V.
Decodificação com Árvore de Huffman: Manipulação de ponteiros e estruturas (struct Node) alocadas pelo código em C para percorrer uma árvore binária e descomprimir uma sequência de bits (referência sobre Codificação de Huffman).
Rotinas Numéricas Auxiliares para o Algoritmo K-Means: Chamadas aninhadas de funções e percorrimento de vetores em memória para cálculo de distância euclidiana (distancia), busca de índice mínimo (min) e cálculo de centróides por média inteira (means) (referência sobre K-Means).

Convenção de Chamada RISC-V (ABI) e Estruturas de Dados

Resumo dos Registradores na ABI (RV32I)

Registradores	Nome ABI	Papel na Convenção de Chamada	Preservação
`x1`	`ra`	Endereço de retorno (Return Address)	Preservado se a função fizer chamadas (`call`)
`x2`	`sp`	Ponteiro de pilha (Stack Pointer)	Callee-saved (deve ser restaurado ao final)
`x8`–`x9`, `x18`–`x27`	`s0`–`s11`	Registradores salvos (Saved registers)	Callee-saved (salvar na pilha antes de usar)
`x10`–`x11`	`a0`–`a1`	Argumentos de função (1º e 2º) e valores de retorno	Caller-saved (temporários)
`x12`–`x17`	`a2`–`a7`	Argumentos de função (3º ao 8º)	Caller-saved (temporários)
`x5`–`x7`, `x28`–`x31`	`t0`–`t6`	Registradores temporários	Caller-saved (temporários)

Representação da Estrutura `Node` em Memória (32 Bits)

Para o exemplo de decodificação de Huffman, o código em C constrói uma árvore binária composta por nós do tipo Node, onde cada ponteiro ocupa 4 bytes (32 bits):

typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

O layout de cada instância de Node em memória possui 12 bytes contíguos:

| Offset +0 (4 bytes) | Offset +4 (4 bytes) | Offset +8 (4 bytes) |
+---------------------+---------------------+---------------------+
|         val         |        *left        |       *right        |
+---------------------+---------------------+---------------------+

val (offset 0): Inteiro de 32 bits. Vale 0 para nós internos da árvore; nos nós folha, armazena o código ASCII do caractere decodificado (val != 0).
left (offset 4): Ponteiro de 32 bits para o filho à esquerda (seguido quando o bit de entrada é '0').
right (offset 8): Ponteiro de 32 bits para o filho à direita (seguido quando o bit de entrada é '1').

Especificação das Funções

Seu arquivo em Assembly deve exportar (via diretiva .globl) todas as nove funções declaradas em biblio.h:

1. Funções Utilitárias da Biblioteca C

void puts(const char *str);
Parâmetros: a0 = endereço de uma string terminada pelo byte nulo ('\0').
Descrição: Calcula o comprimento da string apontada por str (sem incluir o ' \0') e escreve seus caracteres na saída padrão (stdout, descritor 1) seguido obrigatoriamente por um caractere de quebra de linha ('\n', ASCII 10), utilizando a syscall write (a7 = 64).
Retorno: Nenhum (void).
Referência: puts - C++ Reference
char *gets(char *str);
Parâmetros: a0 = endereço do buffer em memória a ser preenchido.
Descrição: Lê caracteres da entrada padrão (stdin, descritor 0) um a um utilizando a syscall read (a7 = 63) e armazena-os no buffer até encontrar um caractere de quebra de linha ('\n', ASCII 10) ou o fim da entrada. O caractere ' \n' não é mantido na string final, sendo substituído pelo byte nulo terminador ('\0', valor 0).
Retorno: Retorna em a0 o endereço original do buffer str.
Referência: gets - C++ Reference
int atoi(const char *str);
Parâmetros: a0 = endereço de uma string terminada por '\0'.
Descrição: Descarta caracteres de espaço em branco iniciais (' ', '\t', '\n', '\v', '\f', '\r'), interpreta um sinal opcional ('+' ou '-') e converte a sequência subsequente de dígitos decimais ('0'–'9') em um inteiro com sinal de 32 bits.
Retorno: Retorna em a0 o valor inteiro convertido.
Referência: atoi - C++ Reference
char *itoa(int value, char *str, int base);
Parâmetros: a0 = valor inteiro a ser convertido (value), a1 = endereço do buffer de destino (str), a2 = base numérica (10 ou 16).
Descrição: Converte value para sua representação textual na base especificada (10 ou 16), finalizando a string com '\0'. Para base 10, valores negativos devem ser precedidos pelo caractere '-'. Para base 16, o valor é tratado como sem sinal (unsigned) utilizando dígitos '0'–'9' e 'A'–'F' (os testes não diferenciam maiúsculas de minúsculas).
Retorno: Retorna em a0 o ponteiro original para o buffer str.
Referência: itoa - C++ Reference
void exit(int code);
Parâmetros: a0 = código de status de encerramento (code).
Descrição: Encerra imediatamente a execução do programa invocando a syscall exit (a7 = 93).
Retorno: Nenhum (void).

2. Exemplo de Manipulação de Estruturas: Decodificação de Huffman

void Huffman(const char *input, char *output, Node *root_node);
Parâmetros:
- a0 (input): Endereço da string contendo a sequência de bits ('0' e '1') terminada em '\0'.
- a1 (output): Endereço do buffer onde a mensagem decodificada deve ser gravada.
- a2 (root_node): Ponteiro para o nó raiz da árvore binária de Huffman.
Descrição: A partir de root_node, lê cada caractere da string input:
- Se o caractere for '0' (ASCII 48), avança para o ponteiro left (4(node)).
- Se o caractere for '1' (ASCII 49), avança para o ponteiro right (8(node)).
- A cada passo, verifica o campo val (0(node)). Enquanto val == 0, o nó é interno e a descida continua com o próximo bit de input. Quando val != 0, atingiu-se um nó folha: o byte correspondente a val deve ser escrito em output, o ponteiro de escrita em output é incrementado e o percurso na árvore reinicia em root_node para o próximo bit.
- Ao encontrar o terminador '\0' em input, grava o byte nulo '\0' ao final de output.
Retorno: Nenhum (void).

3. Exemplo de Chamadas e Vetores: Funções Auxiliares do K-Means

int distancia(int x1, int y1, int x2, int y2);
Parâmetros: a0 = x1, a1 = y1 (coordenadas do primeiro ponto) e a2 = x2, a3 = y2 (coordenadas do segundo ponto).
Retorno: Retorna em a0 a distância inteira calculada.
Descrição: Calcula a distância euclidiana inteira entre os pontos \((x_1, y_1)\) e \((x_2, y_2)\):
```
d = floor(sqrt((x1 - x2)^2 + (y1 - y2)^2))
```
int min(int *posicoes, int tam);
Parâmetros: a0 = ponteiro para o vetor de inteiros posicoes, a1 = número de elementos tam.
Retorno: Retorna em a0 o índice (0 <= idx < tam) onde se encontra o menor valor.
Descrição: Percorre os tam elementos de posicoes (índices 0 a tam - 1) para localizar o índice do menor valor. Em caso de empate entre dois elementos com o mesmo valor mínimo (posicoes[i] <= menor_atual), atualize o índice para o elemento mais recente i.
int means(int *valores, int *posicoes, int tam);
Parâmetros: a0 = vetor base de coordenadas valores, a1 = vetor posicoes contendo os índices selecionados para o grupo (cluster), a2 = quantidade tam de índices válidos em posicoes.
Retorno: Retorna em a0 a média inteira simples dos valores selecionados.
Descrição: Calcula a média aritmética inteira dos elementos de valores cujos índices estão armazenados nas primeiras tam posições do vetor posicoes:
```
media = (valores[posicoes[0]] + valores[posicoes[1]] + ... + valores[posicoes[tam - 1]]) / tam
```
Caso tam == 0, a função deve retornar 0 sem realizar divisão.

Interface de Integração (`biblio.h` e `example.c`)

Durante a correção, seu código em Assembly será compilado e vinculado juntamente com o cabeçalho biblio.h e o arquivo de teste em C example.c. Verifique o código completo de example.c para consultar como cada caso de teste invoca as funções implementadas.

`biblio.h`

typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

void puts ( const char *str );
char *gets ( char *str );
int atoi (const char *str);
char *itoa ( int value, char *str, int base );
void exit(int code);
void Huffman(const char *input, char *output, Node *root_node);
int distancia(int x1, int y1, int x2, int y2);
int min(int *posicoes, int tam);
int means(int *valores, int* posicoes, int tam);

Entradas e Saídas

Entrada (stdin):

1ª linha: Um inteiro op (0 <= op <= 6) indicando a operação a ser executada por run_operation(op).
Linhas seguintes (dependendo de op):
op = 0 ou op = 2: Nenhuma linha adicional.
op = 1: Uma linha de texto a ser lida por gets e impressa por puts.
op = 3: Um número inteiro em base 10 a ser convertido e impresso em hexadecimal (base 16).
op = 4: Duas linhas de texto consecutivas a serem lidas e impressas.
op = 5: Uma string de bits ('0' e '1') a ser decodificada pela árvore de Huffman.
op = 6: Um inteiro indicando o número de iterações do algoritmo K-Means.

Saída (stdout):

A saída correspondente ao caso de teste selecionado por op, finalizada com quebra de linha (\n).

Exemplos

Caso 1 — Leitura e Escrita de String (op = 1)

1
Answer with spaces
--------------------------------
Answer with spaces

Caso 3 — Conversão Decimal para Hexadecimal (op = 3)

3
255
--------------------------------
FF

Caso 5 — Decodificação de Huffman (op = 5)

5
010011010110000110110011101101100100011010110110010101111101101
--------------------------------
you shall not pass

Caso 6 — Iterações do K-Means (op = 6)

6
5
--------------------------------
16

Notas e Dicas

Símbolos Globais: Todos os nomes de funções exigidos devem ser declarados como globais usando a diretiva .globl nome_da_funcao para que o linker consiga resolver as referências chamadas pelo código em C.
Preservação de Registradores (ABI): O código em C compilado utiliza intensamente os registradores salvos s0–s11 para manter variáveis locais (como k, x, y, tam1, tam2, tam3 em run_operation). Se qualquer uma de suas funções em Assembly modificar s0–s11, ela deve salvá-los na pilha no prólogo e restaurá-los antes do ret.
Ponto de Entrada (_start): Como o ponto de entrada _start já está definido no arquivo em C (testing.c / example.c), não defina _start no seu arquivo Assembly para evitar erro de símbolo duplicado na compilação.
Caractere Nulo ('\0'): O caractere '\0' corresponde ao byte nulo de valor 0. Evite usar li a0, '\0', pois alguns montadores interpretam a expressão como o caractere '0' (valor ASCII 48); utilize li a0, 0 ou o registrador zero (sb zero, 0(a1)).
Terminação de Strings: Lembre-se de gravar o byte nulo (0) ao final das strings produzidas em gets, itoa e Huffman antes de retornar ao código em C.

Entrega

Link do Laboratório.

O arquivo report gerado pelo simulador deve ser submetido no Classroom da disciplina, nomeado como {RA}_lab10.report.