( 1,0 pontos) O seguinte fragmento de código processa dois arrays e produz um valor importante no registrador
\mathrm{v} 0
$\mathrm{a} 0
$ \mathrm{a} 1
a2 e $a3, respectivamente. Acrescente comentários ao código e descreva em uma sentença o que o código faz. Especificamente, o que será retornado em $v0?
sll $a2, $a2, 2
sll $a3, $a3, 2
add $v0, $zero, $zero
add $t0, $zero, $zero
outer: add $t4, $a0, $t0
Iw $t4, 0($t4)
add $t1, $zero, $zero
inner: add $t3, $a1, $t1
Iw $t3, 0($t3)
bne $t3, $t4, skip
addi $v0, $v0, 1
skip: addi $t1, $t1, 4
bne $t1, $a3, inner
addi
$t0, $t0, 4
bne
$t0, $a2, outer
sll $a2, $a2, 2
sll $a3, $a3, 2
add $v0, $zero, $zero
add $t0, $zero, $zero
outer: add $t4, $a0, $t0
Iw $t4, 0($t4)
add $t1, $zero, $zero
inner: add $t3, $a1, $t1
Iw $t3, 0($t3)
bne $t3, $t4, skip
addi $v0, $v0, 1
skip: addi $t1, $t1, 4
bne $t1, $a3, inner
| addi | $t0, $t0, 4 |
| bne | $t0, $a2, outer |
Passo 1
O enunciado dá um fragmento de código em estilo MIPS que processa dois arrays. As informações fornecidas são:
- Cada array tem exatamente
words, indexadas de a . - O endereço base do primeiro array (chamei de A) está em
. - O endereço base do segundo array (chamei de B) está em
. - O tamanho
está em (para A) e em (para B). - O código atual usa registradores temporários
e o registrador de contagem .
O pedido: acrescente comentários ao código e descreva em uma sentença o que o código faz — especificamente, o que será retornado em.
Passo 2
Aqui está o código com comentários linha a linha (cada registrador e número aparece entre
conforme solicitado):
sll
,
,
# multiplica o tamanho de A por 4: converte contador de words para bytes
sll ,
,
# multiplica o tamanho de B por 4: converte contador de words para bytes
add ,
,
# zera o contador de correspondências em $v0
add ,
,
# zera o offset byte para percorrer A
outer: add ,
,
# calcula endereço efetivo de A[i]: base A + offset t0
lw ,
# carrega A[i] em $t4
add ,
,
# zera o offset byte para percorrer B
inner: add ,
,
# calcula endereço efetivo de B[j]: base B + offset t1
lw ,
# carrega B[j] em $t3
bne ,
, skip # se B[j] diferente de A[i], pula incremento
addi ,
,
# se igual, incrementa contador de correspondências
skip: addi ,
,
# t1 += 4 (próxima word de B)
bne ,
, inner # enquanto t1 != tamanho_em_bytes_de_B, repete inner
addi ,
,
# t0 += 4 (próxima word de A)
bne ,
, outer # enquanto t0 != tamanho_em_bytes_de_A, repete outer
sll
add
add
outer: add
lw
add
inner: add
lw
bne
addi
skip: addi
bne
addi
bne
Passo 3
Explanação didática das duas primeiras instruções (
) e por que são necessárias:
- Em MIPS a memória é endereçada por bytes. Cada word tem
bytes. O enunciado guardou em e o número de words ( ), não o número de bytes. - A instrução
sll \(\$a2\), \(\$a2\), 2faz um shift lógico à esquerda porbits: isso equivale a multiplicar por . Portanto: então depois dessa instrução (bytes). O mesmo vale para . - Conclusão prática: as comparações posteriores usam offsets em bytes (0, 4, 8, …), e as instruções
bnecome comparam offsets em bytes.
Passo 4
O que fazem as inicializações e qual o papel de
e
:
add \(\$v0\), \(\$zero\), \(\$zero\)inicializacom . Vamos usar para contar quantas vezes encontramos elementos iguais entre A e B. add \(\$t0\), \(\$zero\), \(\$zero\)inicializacom . é usado como offset em bytes para percorrer A: na iteração tem valor . - Dentro do laço externo,
add \(\$t1\), \(\$zero\), \(\$zero\)inicializacom para cada novo . é o offset em bytes para percorrer B: na iteração tem valor .
Passo 5
Como o carregamento e comparação funcionam (a instrução
lw e o bne):add \(\$t4\), \(\$a0\), \(\$t0\)calcula o endereço de A[i] como base A + offset t0. Em seguidalw \(\$t4\), \(0(\$t4)\)carrega a word de memória nesse endereço para. Assim passa a conter . - De modo análogo,
add \(\$t3\), \(\$a1\), \(\$t1\)elw \(\$t3\), \(0(\$t3)\)carregamem . bne \(\$t3\), \(\$t4\), skiptesta se. Se forem diferentes, pula o incremento. Se forem iguais, a instrução seguinte addi \(\$v0\), \(\$v0\), 1aumenta o contador.
Passo 6
Estrutura de laços (loops) e contagem total de comparações:
- O laço externo percorre
de até (em offsets de bytes ). O laço interno percorre de até . - Para cada par
o código compara com e, se iguais, incrementa . - Número total de comparações realizadas é
. O contador conta quantas dessas comparações resultaram em igualdade.
Passo 7
Observação importante sobre duplicatas e o que exatamente é contado:
- O código não faz distinção de posições já contadas nem elimina duplicatas de valores; ele conta todas as ocorrências par-a-par.
- Ou seja, se um valor
aparece vezes em A e vezes em B, então ele contribui com para o total . - Exemplo pequeno (para entender): se
e , - para
há correspondências (com e ); - para
há ; - para
há mais ; - total
.
- para
Passo 8
Resumo prático de como interpretar o resultado em uma prova:
- Ao ver esse código, você deve reconhecer imediatamente: (1) conversão de contadores de words para bytes via deslocamento à esquerda por 2; (2) uso de offsets em bytes,
e , para indexação; (3) dois laços aninhados que comparam cada par de elementos; (4) incremento de quando um par é igual. - Portanto, sem ter de executar todas as 6,25 milhões de comparações na prova, descreva logicamente que
terminará contendo o número total de pares com tais que .
Passo 9
Uma sentença que descreve o que o código faz (pedida no enunciado):
- O código conta todas as ocorrências onde um elemento de A é igual a um elemento de B, somando 1 para cada par
com , e armazena essa contagem em .