Skip to content

Laboratório 11 - Recursão com Floodfill

Objetivo

Implementar o algoritmo de Floodfill de forma recursiva em Assembly RISC-V (RV32IM), respeitando estritamente a Application Binary Interface (ABI).

Motivação

O algoritmo de Floodfill (preenchimento por inundação) é um clássico utilizado para determinar a área conectada a um determinado nó. Com aplicações em várias áreas da computação, o seu uso mais notável é na computação gráfica. Historicamente, ele se popularizou na década de 1980 com a criação da ferramenta "Balde de Tinta" (Paint Bucket) em softwares pioneiros de edição de imagem, como o MacPaint (1984).

Por se tratar de uma função recursiva, é estritamente necessário manipular a Pilha de Chamadas (Call Stack) de forma manual e respeitar as regras de salvamento de registradores ditadas pela ABI do RISC-V.

Implementação recursiva baseada em pilha (quatro direções)

A primeira implementação conhecida do flood-fill, implicitamente baseada em pilha, recursiva e de quatro direções, funciona da seguinte maneira:

----------------------------------------------------------
Flood-fill (nó):
----------------------------------------------------------
1. se o nó não for um espaço válido (área livre), retorne.
2.    marque o nó (pinte como visitado).
3.    execute o Flood-fill para os vizinhos do nó.
4.    retorne.
----------------------------------------------------------

Para um aprofundamento teórico e exemplos em pseudocódigo, consulte o artigo da Wikipedia sobre Flood Fill.

Contexto Técnico

Instruçĩes Básicas para o Programa:

  • O programa deve ler a imagem (arquivo .pgm de 64×64 pixels);
  • A imagem deve ser varrida em busca de "áreas livres" (pixels brancos);
  • Deve-se utilizar um algoritmo recursivo de Floodfill para percorrer e pintar a área livre encontrada.
  • O número total de áreas livres encontradas no mapa deve ser impresso na saída padrão (stdout).
  • É obrigatório que essa função respeite as regras da ABI do RISC-V;

Sobre a Imagem de Entrada e seu Formato

O Mapa (imagem) fornecido tem 4096 pixels (64×64) e está representada no formato PGM (tons de cinza com 8 bits por pixel).

  • Pixels com valor 0 (Preto): representam paredes/rochas intransponíveis.
  • Pixels com valor 255 (Branco): representam áreas livres não mapeadas.

Neste exercício o formato do arquivo lido da memória/disco segue um cabeçalho fixo (13 bytes):

P5
64 64
255
[pixels da imagem - 4 096 bytes]

Código Base para Exercício

.data
input_file: .asciz "mapa.pgm"

buffer:       .space 4109   # 13 bytes header + 4096 bytes pixels

.text
.globl _start

_start:
    # 1. Abrir arquivo
    la a0, input_file
    li a1, 0          
    li a2, 0
    li a7, 1024       # syscall open
    ecall
    mv s0, a0         # salva fd em s0

    # 2. Ler arquivo para o buffer
    mv a0, s0
    la a1, buffer
    li a2, 4109
    li a7, 63         # syscall read
    ecall

    # 3. Fechar arquivo
    mv a0, s0
    li a7, 57         # syscall close
    ecall

    # 4. Configurar Canvas 64x64
    li a0, 64
    li a1, 64
    li a7, 2201       # syscall setCanvasSize
    ecall

Exemplo de "setPixel" para colorir um pixel:

li a0, 10    # x coordinate = 10
li a1, 20    # y coordinate = 20
li a2, 0x00FF00FF # Green pixel
li a7, 2200  # syscall setPixel (2200)
ecall

Entrada

Arquivo mapa.pgm 64×64 lido via syscalls de manipulação de arquivo (open, read).

Saída

O programa deve imprimir na saída padrão (stdout) apenas o número total de áreas livres (complexos isolados) encontradas no mapa, seguido de uma quebra de linha (\n).

Important

PS: nome do arquivo para o envio final deve ser exatamente mapa.pgm

Dicas

Regras de ABI e Recursão

  • Sua função floodfill deve receber parâmetros (como coordenada X, coordenada Y, etc.) utilizando os registradores a0-a7.
  • Por ser uma função recursiva (que chama a si mesma), ela deve gerenciar corretamente a pilha.
  • Uso de recursão: Soluções iterativas não serão aceitas.

Canvas

  • Para testar no simulador, carregue seu programa (arquivo .s) e o arquivo de imagem (nome mapa.pgm) simultaneamente.
  • Use o Canvas para debugar! Modifique as áreas visitadas na memória e, ao mesmo tempo, chame a syscall de pintar o pixel de outra cor (ex: cinza ou vermelho) no Canvas para ver o algoritmo "preenchendo" os espaços ao vivo.

Exemplos

Entrada Saída Exemplo
Exemplo 1 1 Exemplo 1.pgm
Exemplo 2 12 Exemplo 2.pgm
Exemplo 3 3 Exemplo 3.pgm

Acessaando o Canvas do Simulador ALE

Pode-se acessar o Canvas para visualizar o preenchimento da área livre em tempo real. Para isso, deve-se clicar na aba 'Canvas' no simulador e acompanhar o preenchimento da imagem durante a execução do algoritmo de Floodfill.

Exemplo de preenchimento no Canvas do Simulador ALE

Exemplo de preenchimento no Canvas do Simulador ALE

Entrega

O report gerado pelo simulador deve ser submetido no Classroom da disciplina, renomeado como {RA}_lab11.report.

Warning

  • Qualquer alteração no arquivo de report será considerado fraude
  • O uso de ferramentas de IA deve ser reportado, indicando como foi utilizado e em quais partes do código.
  • Está é uma atividade individual, o qual deve ser desenvolvido individualmente, qualquer forma de cópia ou plágio será penalizada. Portanto, atividades que apresentarem semelhanças injustificadas serão atribuídas nota zero para todos os envolvidos