Criando e Manipulando Matrizes no MIPS

17/01/2022

instrução MIPS LW e SW IF Simples no MIPS

ÍNDICE DE CONTEÚDO

Este post faz parte da série MIPS

Neste artigo vou mostrar para vocês como criar e manipular matrizes de duas dimensões usando o MARS como simulador MIPS. A partir desta base você será capaz de fazer outras operações com matrizes no MIPS. Vai ser divertido! Usarei funções neste artigo então, caso você ainda não tenha lido meus artigos sobre o tema, seria bom fazê-lo antes de começar aqui ta ok?! Bora lá!

Entendendo as Matrizes no MIPS

Antes de começarmos a codificar no MARS vamos dar uma olhada em como a matriz é organizada para a codificação. Na Figura 1 apresento uma matriz com 4 linhas e 4 colunas o que resulta em 16 elementos. Observe que a contagem começa com zero!!! A Figura 2 apresenta uma abstração da Matriz 4×4.

Vou indicar a matriz com a letra m e m[i,j] a posição de cada elemento na matriz: m[0,0] é o cruzamento da linha zero com a coluna zero, m[1,2] é o cruzamento da linha 1 com a coluna2, e assim por diante. Apesar de representarmos as matrizes em duas ou mais dimensões, elas na verdade são uma abstração. Toda a memória é unidimensional!!! Isso signfica que a memória de um computador de 32 bits consiste em uma matriz de bytes começando do índice (endereço) 0 x 0000 0000 e indo até o índice (endereço) 0 x ffff ffff. No entanto, muitos tipos de problemas são muito mais fáceis de resolver se pudermos não apenas pensar em termos de matrizes bidimensionais, mas também expressar nossa solução de uma forma que use diretamente os índices de linha e coluna de uma matriz bidimensional.

As matrizes bidimensionais são frequentemente implementadas da esquerda para a direita e de cima pra baixo, o que é chamado de row-major, ou traduzindo para pt-br: ordem de linha principal. Também é possível implementar como column-major, isto é, de cima para baixo e da esquerda para a direita, portanto, em ordem de coluna principal. As Figuras 4 e 5 ilustram essas duas formas. Em row-major, a linha fica travada até que todas as colunas sejam lidas ou escritas, ai passa-se para a próxima linha, le/escreve as colunas e assim continua até terminar. Em column-major, as colunas ficam travadas e as linhas são lidas ou escritas, até que todas as posições sejam lidas/escritas. Em seguida de cada Figura está o código correspondente.

Os Melhores Treinamentos sobre Sistemas embarcados e IoT

Cursos com professores qualificados para acelerar sua carreira e projetos

MATRÍCULE-SE AGORA

for(int linha=0; linha<tamanho_linha; linha++ ){
   for(int coluna=0, coluna<tamanho_coluna, coluna++){
         // m[i][j]
    }
}

for(int coluna=0; coluna<tamanho_coluna; coluna++ ){
   for(int linha=0, linha<tamanho_linha, linha++){
         // m[i][j]
    }
}

A Figura 3 apresenta como fica a Matriz Bidimensional 4×4 na Memória usando row-major, enquanto a Figura 4 mostra a organização como column-major.

FIGURA 3: COMO FICA A MATRIZ 4×4 NA MEMÓRIA COM ROW-MAJOR

FIGURA 4: COMO FICA A MATRIZ 4×4 NA MEMÓRIA COM COLUMN-MAJOR

A partir daqui já podemos abstrair algumas informações importantes para codificarmos a matriz no MIPS:

L: número total de linhas da matriz (4)
C: número total de colunas da matriz (4)
eL: número de elementos em uma linha (4)
eC: número de elementos em uma coluna (4)
iL: índice da linha
iC: índice da coluna
M: nome da matriz
M[linha][coluna]: um elemento da matriz
bM: endereço base da matriz
aM: endereço de um elemento da matriz
T: tamanho total da matriz (16)

Precisaremos de algumas dessas informações para construir nosso código em MIPS. O que vamos implementar aqui será o row_major.

Definindo a matriz

Bom, a primeira coisa que precisamos fazer em nosso código MIPS é definir a matriz e isso é feito no segmento de dados

.data
         M:		.word 0:16	# inicializa todos os elementos da matriz com zero
         tamanho: 	.word 16	# tamanho da matriz

M é o nome da matriz. Como ela terá 16 elementos (4×4) então colocamos .word 0:16 que já vai inicializar cada elemento da matriz com o valor zero. Você também pode definir aqui o tamanho e as outras abstrações que listamos e usar dentro do seu codigo. Por simplicidade do entendimento, optei por não fazer isto, mas sinta-se livre para otimizar o código e deixá-lo com sua cara!

Outra coisa que quero fazer é pedir para que o usuário digite os valores para essa matriz. Se você não quer fazer isso, basta inicializar a matriz da seguinte forma:

.data
       M:     .word 3, 14, 15, 9
              .word 2, 6, 53, 5
              .word 89, 79, 3, 23
              .word 84, 62, 643, 38

Como vou solicitar os valores, preciso imprimir uma mensagem no console, avisando o usuário. Essas mensagens também devem ser definidas no segmento de dados. Portanto, ficará assim:

.data
			.align 4 # alinhamento de memória
         m1: 		.asciiz "\nDigite um número inteiro:\t"
         m2: 		.asciiz "\nM[linha][coluna]:\t"
         M:		.word 0:16	# inicializa todos os elementos da matriz com zero
         tamanho: 	.word 16	# tamanho da matriz

Não esqueça de colocar .align 4 para que o alinhamento de memória seja feito corretamente!

Função MAIN

Definida a matriz, precisamos agora codificar o programa principal já que farei duas funções aqui: uma para preencher a matriz e outra para imprimi-la. Para facilitar ainda mais, não passarei nenhum parametro nessas funções. Mas, novamente, sintam-se livre para modificar o código!

.text
	main:
		# setando a pilha de chamada de procedimentos
		subu 	$sp, $sp, 32   # o frame de pilha tenm 32 bytes
		sw 	$ra, 20($sp)     # salva o endereço de retorno
		sw 	$fp, 16($sp)     # salva o ponteiro do frame
		addiu 	$sp, $sp, 28  # prepara o ponteiro do frame			
	        
	        jal matriz_preenche
        	jal matriz_imprime 
	       
	        # re-setando a pilha de chamada de procedimentos
		lw 	$ra, 20($sp)       # restaura o endereço
		lw 	$fp, 16($sp)       # restaura o frame pointer
		addiu 	$sp, $sp, 32    # remove do frame		
		j FIM	              # finaliza o programa				
FIM: 
        li $v0, 10        
        syscall

Lembram-se que sempre que trabalhamos com funções precisamos definir as configurações do frame de pilha? Caso ainda não saiba como fazer isto, por favor, leia os seguintes artigos antes de continuar aqui:

Compilando Funções e Procedimentos no MIPS

Basicamente, na função main, inicializamos o frame de pilha, chamamos as funções para preencher e imprimir a matriz e então finalizamos com as configurações do frame de pilha. A linha j FIM chama a finalização correta do programa.

Função para popular a matriz

Como estamos lidando com função, então, aqui novamente precisamos inicializar e finalizar as configurações do frame de pilha. Dei o nome de matriz_preenche à função e ao LOOP para preencher a matriz eu dei o nome de popula_matriz. Dentro da função matriz_preenche a primeira coisa que fazemos é inicializar o frame de pilha.

matriz_preenche:
		# configurações da pilha
		subu  $sp, $sp, 32   # reserva o espaço do frame ($sp)    
		sw    $ra, 20($sp)   # salva o endereço de retorno ($ra)    
		sw    $fp, 16($sp)   # salva o frame pointer ($fp)    
		addiu $fp, $sp, 28   # prepara o frame pointer    
		sw    $a0, 0($fp)    # salva o argumento ($a0)

Em seguida inicializo os registradores do número de linhas, número de colunas, contador da linha, contador da coluna e o registrador que guardará o valor do elemento da matriz.

                li       $t0, 4       # $t0: número de linhas
	       	li       $t1, 4       # $t1: número de colunas
        	move     $s0, $zero   # $s0: contador da linha
	        move     $s1, $zero   # $s1: contador da coluna
	        move     $t2, $zero   # $t2: valor a ser lido/armazenado

O próximo passo é o LOOP! Aqui precisamos fazer o cálculo correto do endereço do elemento da matriz. Cada iteração do LOOP armazenará o valor de $t1 incrementado no próximo elemento da matriz. O deslocamento é calculado a cada iteração: deslocamento = 4 * (linha * número de colunas + coluna)

popula_matriz:    		
		mult     $s0, $t1	# $s2 = linha * numero de colunas 
	        mflo     $s2            # move o resultado da multiplicação do registrador lo para $s2
        	add      $s2, $s2, $s1  # $s2 += contador de coluna
       		sll      $s2, $s2, 2    # $s2 *= 4 (deslocamento 2 bits para a esquerda) para deslocamento de byte

Depois de realizar o cálculo, podemos solicitar ao usuário que digite o valor do elemento

	        li 	$v0, 4		
		la 	$a0, m1		
		syscall						
		li 	$v0, 5		
		syscall			
		move 	$t2, $v0

Digitado no console, já conseguimos pegar o valor e salvá-lo no registrador:

                sw	$t2, M($s2)

Agora temos de incrementar o contador

               addi     $t2, $t2, 1

O próximo passo é verificar se estamos no limite do número de linhas e de colunas. Se ainda não chegamos no final de uma linha, voltamos ao LOOP. Quando chegamos ao final de uma linha, precisamos ir para a próxima linha, até que todas as linhas sejam preenchidas. O mesmo se aplica à coluna. O contador da coluna precisa ser resetado pois ao terminar uma linha passamos por toda as colunas daquela linha e a próxima linha começa na coluna zero.

                addi    $s1, $s1, 1    		        # incrementa contador da coluna
	        bne     $s1, $t1, popula_matriz   	# não é o fim da linha então LOOP
	        move    $s1, $zero     		        # reseta o contador da coluna
        	addi    $s0, $s0, 1    		        # incrementa o contador da linha
	        bne     $s0, $t0, popula_matriz   	# não é o fim da matriz então LOOP

Note que, no primeiro BNE, o desvio só vai acontecer se $s1 não for diferente de $t1, e no segundo BNE, só vai desviar se $s0 for diferente de $t0. Depois disso precisamos finalizar a função corretamente:

	add 	$v0, $s1, $zero   
	jr 	$ra

Função para imprimir a matriz

A função para imprimir a matriz é exatamente igual à função para preencher a matriz. A principal diferença é que aqui não vamos pedir para o usuário digitar nada, vamos apenas pegar os valores que estão armazenados e printar no console.


matriz_imprime:

	# configurações da pilha
	subu  $sp, $sp, 32   # reserva o espaço do frame ($sp)    
	sw    $ra, 20($sp)   # salva o endereço de retorno ($ra)    
	sw    $fp, 16($sp)   # salva o frame pointer ($fp)    
	addiu $fp, $sp, 28   # prepara o frame pointer    
	sw    $a0, 0($fp)    # salva o argumento ($a0)	

	li       $t0, 4       # $t0: número de linhas
       	li       $t1, 4       # $t1: número de colunas
       	move     $s0, $zero   # $s0: contador da linha
        move     $s1, $zero   # $s1: contador da coluna
        move     $t2, $zero   # $t2: valor a ser lido/armazenado
        
	imprime_matriz:    
		# calcula o endereço correto do array
		mult     $s0, $t1	# $s2 = linha * numero de colunas 
	        mflo     $s2            # move o resultado da multiplicação do registrador lo para $s2
        	add      $s2, $s2, $s1  # $s2 += contador de coluna
	        sll      $s2, $s2, 2    # $s2 *= 4 (deslocamento 2 bits para a esquerda) para deslocamento de byte    
	
		# obtem o valor do elemento armazenado
		lw	$t2, M($s2) 		
	
		# imprime no console o valor do elemento da matriz
		li 	$v0, 4   
		la 	$a0, m2
		syscall 	
		li 	$v0,1    
		move 	$a0, $t2
		syscall 
	        
        	# incrementa o contador
        	addi     $t2, $t2, 1 
      
      		addi     $s1, $s1, 1    		# incrementa contador de coluna
		bne      $s1, $t1, imprime_matriz   	# não é o fim da linha então LOOP
		move     $s1, $zero     		# reseta o contador da coluna
		addi     $s0, $s0, 1    		# increment row counter
		bne      $s0, $t0, imprime_matriz  	# não é o fim da matriz então LOOP
		jr $ra
        
       # configurações do procedimento    
	add 	$v0, $s1, $zero # retorna para quem chamou    
	jr 	$ra

Código Completo

Segue aqui o código completinho para você testar no MARS.

.data
			.align 4 # alinhamento de memória
         m1: 		.asciiz "\nDigite um número inteiro:\t"
         m2: 		.asciiz "\nM[linha][coluna]:\t"
         M:		.word 0:16	# inicializa todos os elementos da matriz com zero
         tamanho: 	.word 16	# tamanho da matriz         

.text
	main:
		# setando a pilha de chamada de procedimentos
		subu 	$sp, $sp, 32     # o frame de pilha tenm 32 bytes
		sw 	$ra, 20($sp)     # salva o endereço de retorno
		sw 	$fp, 16($sp)     # salva o ponteiro do frame
		addiu 	$sp, $sp, 28      # prepara o ponteiro do frame			
	        
	        jal matriz_preenche
        	jal matriz_imprime 
	       
	        # re-setando a pilha de chamada de procedimentos
		lw 	$ra, 20($sp)       # restaura o endereço
		lw 	$fp, 16($sp)       # restaura o frame pointer
		addiu 	$sp, $sp, 32       # remove do frame		
		j FIM	                   # finaliza o programa		

matriz_preenche:
		# configurações da pilha
		subu  $sp, $sp, 32   # reserva o espaço do frame ($sp)    
		sw    $ra, 20($sp)   # salva o endereço de retorno ($ra)    
		sw    $fp, 16($sp)   # salva o frame pointer ($fp)    
		addiu $fp, $sp, 28   # prepara o frame pointer    
		sw    $a0, 0($fp)    # salva o argumento ($a0)	

		li       $t0, 4       # $t0: número de linhas
	       	li       $t1, 4       # $t1: número de colunas
        	move     $s0, $zero   # $s0: contador da linha
	        move     $s1, $zero   # $s1: contador da coluna
	        move     $t2, $zero   # $t2: valor a ser lido/armazenado
	        
	popula_matriz:    		
		# Cada iteração de loop armazenará o valor de $t1 incrementado no próximo elemento da matriz
		# O deslocamento é calculado a cada iteração: deslocamento = 4 * (linha * número de colunas + coluna)
	        
		# calcula o endereço correto do array
		mult     $s0, $t1	# $s2 = linha * numero de colunas 
	        mflo     $s2            # move o resultado da multiplicação do registrador lo para $s2
        	add      $s2, $s2, $s1  # $s2 += contador de coluna
       		sll      $s2, $s2, 2    # $s2 *= 4 (deslocamento 2 bits para a esquerda) para deslocamento de byte       
        
	        # solicita que o usuário digite um número inteiro
	        li 	$v0, 4		
		la 	$a0, m1		
		syscall						
		li 	$v0, 5		
		syscall			
		move 	$t2, $v0        
	
		# armazena o valor digitado pelo usuário
		sw	$t2, M($s2) 		
	        
        	# incrementa o contador
	        addi     $t2, $t2, 1 
        
		# Controle de loop: 
		# se incrementarmos além da última coluna, redefinir o contador de coluna 
		# e incrementar o contador de linha
		# se incrementarmos além da última linha, terminaremos. 
        	addi    $s1, $s1, 1    		# incrementa contador da coluna
	        bne     $s1, $t1, popula_matriz   	# não é o fim da linha então LOOP
	        move    $s1, $zero     		# reseta o contador da coluna
        	addi    $s0, $s0, 1    		# incrementa o contador da linha
	        bne     $s0, $t0, popula_matriz   	# não é o fim da matriz então LOOP
	        jr 	$ra
        
	# configurações do procedimento    
	add 	$v0, $s1, $zero # retorna para quem chamou    
	jr 	$ra	
	
matriz_imprime:

	# configurações da pilha
	subu  $sp, $sp, 32   # reserva o espaço do frame ($sp)    
	sw    $ra, 20($sp)   # salva o endereço de retorno ($ra)    
	sw    $fp, 16($sp)   # salva o frame pointer ($fp)    
	addiu $fp, $sp, 28   # prepara o frame pointer    
	sw    $a0, 0($fp)    # salva o argumento ($a0)	

	li       $t0, 4       # $t0: número de linhas
       	li       $t1, 4       # $t1: número de colunas
       	move     $s0, $zero   # $s0: contador da linha
        move     $s1, $zero   # $s1: contador da coluna
        move     $t2, $zero   # $t2: valor a ser lido/armazenado
        
	imprime_matriz:    
		# calcula o endereço correto do array
		mult     $s0, $t1	# $s2 = linha * numero de colunas 
	        mflo     $s2            # move o resultado da multiplicação do registrador lo para $s2
        	add      $s2, $s2, $s1  # $s2 += contador de coluna
	        sll      $s2, $s2, 2    # $s2 *= 4 (deslocamento 2 bits para a esquerda) para deslocamento de byte    
	
		# obtem o valor do elemento armazenado
		lw	$t2, M($s2) 		
	
		# imprime no console o valor do elemento da matriz
		li 	$v0, 4   
		la 	$a0, m2
		syscall 	
		li 	$v0,1    
		move 	$a0, $t2
		syscall 
	        
        	# incrementa o contador
        	addi     $t2, $t2, 1 
      
      		addi     $s1, $s1, 1    		# increment column counter
		bne      $s1, $t1, imprime_matriz   	# not at end of row so loop back
		move     $s1, $zero     		# reset column counter
		addi     $s0, $s0, 1    		# increment row counter
		bne      $s0, $t0, imprime_matriz  	# not at end of matrix so loop back
		jr $ra
        
       # configurações do procedimento    
	add 	$v0, $s1, $zero # retorna para quem chamou    
	jr 	$ra
	
FIM: 
        li $v0, 10        
        syscall

Cheat Sheets (resumo)

Pessoal, eu fiz um resumão sobre MIPS e PIPELINE que estão disponíveis no meu Github. Espero que este material seja útil para vocês. Se gostarem, por favor, compartilhem e deixem uma estrelinha lá pra mim. Seguem os links:

https://github.com/cissagatto/CheatSheetPipelineMIPS32Bits

https://github.com/cissagatto/MIPS32BitsCheatsheet

É isso pessoal! Espero que vocês tenham gostado. Caso não tenham entendido algo, por favor, deixem aqui nos comentários que responderei ok!?? Até o próximo artigo.