Exercícios básicos de programação em linguagem de montagem do ARM
MC404 1o semestre de 2015

Atualizado em 30/03/2015
Prof. Célio

  1. Considere a instrução do ARM: str r1, [r0]. Descreva os passos para execução dessa instrução tomando como modelo o ciclo de execução de uma instrução e usando o diagrama de blocos da CPU do ARM.
  2. Este exercício deve ser feito usando as recomendações do documento programação estruturada em linguagens de montagem:
    Escreva um trecho de programa contendo apenas uma instrução lógico/aritmética e saltos condicionais apropriados, para verificar se um inteiro com sinal em um registrador é positivo, negativo, par ou ímpar. Desenhe os arcos onde há saltos e verifique se o número de cruzamentos de arcos é mínimo.
  3. Escreva uma subrotina convnb que toma como parâmetro de entrada em r1 um inteiro de 4 bits (nibble) e retorna em r1 a representação ascii-hexadecimal do nibble. Teste-a num laço em que r1 varia de 0 a 15, mostrando no vídeo cada valor retornado.
  4. Escreva uma subrotina getnbs que toma como parâmetro de entrada em r1 um valor binário qualquer e em r0 um apontador para um vetor de bytes na memória RAM. A subrotina deve extrair cada nibble de r1 e armazená-lo no vetor apontado por r0. Teste-a num laço com o valor de r1=0x89abcdef e leia e exiba no vídeo cada byte do vetor.
  5. Escreva um programa que em tempo de montagem preenche um vetor de palavras na memória RAM com os números ímpares 3, 5,..., 63 usando as diretivas .equ, .rept, .word e .endr. Escreva uma rotina showvet para exibir o conteúdo do vetor no vídeo.
    dica: dentro do bloco delimitado por .rpt .endr altere o valor da constante definida via .equ
  6. Calculando o número de bits 1 e número de bits 0 numa palavra de 32 bits
    Escreva uma subrotina (countbits) que toma como parâmetro de entrada em r0 um valor de 32 bits e calcula em r1 o número de bits de r0 iguais a 1 e em r2 o número de bits de r0 iguais a 0 (r1 e r2 são parâmetros de saída). Obs: ela deve conter apenas um laço!.
  7. Escreva uma subrotina mod que toma como parâmetros de entrada dois inteiros sem sinal em r1 e r2 e devolve em 2 registradores da sua escolha o quociente e o resto da divisão de r2 por r1. Sugestão: use as instruçõs udiv e mull (p. 85-86 do manual de instruções)
  8. Verificando se um inteiro de 32 bits é uma potencia de 2
    Escreva uma subrotina pow2 que toma como parâmetro de entrada em r1 um inteiro de 32 bits e devolve em r2 o número do bit correspondente (0..31), caso r1 seja uma potencia de 2 e nesse caso retorna também o flag Z=1, caso contrário se r1 não é uma potencia de 2, retorna Z=0. Após chamar pow2 exiba no vídeo mensagens indicando se o valor passado é ou não uma potencia de dois. Exemplo: se r1=0x80000000 então pow2 deve devolver r2= 31 e Z=1. Este exercício mostra que um dos bits de flag da cpu pode ser usado como parâmetro de saída de uma subrotina.
  9. Generalizando as macros ubfx e sbfx
    Considere as macros ubfx e sbfx vistas em aula: nelas os parâmetros sbit e nbits são constantes. Generalize-as de forma que esses parâmetros estejam contidos em registradores. Sugestão: veja o detalhamento das instruções asr, lsl, lsr, etc p. 76 do manual detalhado de istruções ou procure no google "ARM LSL instruction".
  10. Inserindo, removendo e exibindo bytes num vetor de bytes (representando uma fila)
    • inicialize em tempo de montagem um vetor com N bytes iguais a 0, onde N é uma constante definida via diretiva equ;
    • escreva uma subrotina appendbyte para inserir um byte no final do vetor definido anteriormente, onde o 10 byte do vetor contem o tamanho do vetor (<=255)
      Parâmetros de entrada: em r0 o endereço do vetor e em r1 o byte a ser inserido
      Sugestão: depure com gdb e/ou com a subrotina a seguir.
    • escreva uma subrotina showbytes para exibir no vídeo o conteúdo do vetor de bytes, incluindo o tamanho. Ela deve funcionar mesmo que o tamanho seja 0.
    • escreva uma subrotina removebyte para remover o último elemento do vetor. Parâmetro de entrada: r0= endereço do vetor. Parametro de saída: r1= byte removido Obs: fica mais eficiente decrementar o contador de bytes sem alterar os bytes restantes do vetor. Você deve também tomar o cuidado de não remover de um vetor com 0 bytes.
    • inclua num só programa todos os itens acima: 
         defina um vetor con N=16 bytes
   insira 8 bytes quaisquer no vetor (via appendbyte),
   exiba o conteúdo do vetor(via showbytes),
   num laço: remova cada byte do vetor (removebyte)e  exiba o seu conteúdo (showbytes)
  11. Implementação de conjuntos matemáticos
    Deseja-se implementar um vetor de bytes na memória RAM do Arm como um conjunto matemático, no sentido de que não possui elementos repetidos. Escreva rotinas addtoset, removefromset e isinset para, respectivamente, inserir um elemento no set, remover um elemento do set e verificar se existe um elemento no set.
    addtoset: parâmetro de entrada: r0= endereço do vetor, r1 elemento a ser adicionado.
    Parâmetro de saída: r0= 0 se elemento já existe, r0=-1 caso contrário
    removefromset: parâmetro de entrada: r0=endereço do vetor, r1= valor a ser removido
    Parâmetro de saída: r0=0 se elemento não existe no set, r0=-1 caso contrário
    isinset: parâmetro de entrada: r0= endereço do vetor, r1 elemento a ser verificado.
    Parâmetro de saída: r0=0 se elemento não existe no set, r0=-1 caso contrário
    O set deve ser criado em tempo de montagem com tamanho máximo de M elementos (inicializados co 0 e onde o 1o elemento contem o tamanho corrente do set). M é um parâmetro do programa.
    Que modificações você faria no seu programa caso o conjunto fosse um vetor de palavras (32 bits)?

  12. Substituindo os nibbles de um registrador
    Escreva e teste uma subrotina (subnibble) para substituir sucessivamente cada nibble (4 bits) do registrador r0 por uma constante de 4 bits passada em r1; ro e r1 são parâmetros de entrada; r0 é também parâmetro de saída. Por exemplo: se r0 contem 0xabcdef01 e a constante é 0xf após cada iteração r0 conterá abcdef0f, abcdefff, ..., ffffffff.
    Sugestão: use a instrução bfi (p. 89 do manual de instruções).

  13. Comparação lexicográfica de cadeias de caracteres padrão C
    1. Escreva uma subrotina lexcmp para comparar lexicograficamente duas cadeias de caracteres padrão C, apontadas por r1 e r2 respectivamente (parâmetros de entrada) e devolver em r0 (parâmetro de saída) o valor 0 se as cadeias forem iguais, -1 se a 1a for menor que a segunda e 1 se for maior. Observe que "ab" é menor que "abc", porém "ad" é maior que "abc".
      Este problema é menos trivial do que parece, com várias situações a serem consideradas. O seguinte pseudo-código pode ajudar na obtenção de uma solução que contemple todas as possibilidades (inclusive o caso limite em que as duas cadeias são vazias!; é possível codificá-la com ~20 instruções): 
      l1: obtenha em r3 e r4 um byte de cada cadeia, respectivamente, incrementando os apontadores r1 e r2
    se r3=0 a 1a cadeia é menor que a 2a, a menos que ela tambem tenha terminado (r4=0)
    se r4=0 a 1a cadeia é maior que 2a
    se r3=r4 volte para l1
    se r3>r4 retorne 1 senão retorne -1
    2. Defina as seguintes cadeias de caracteres: 
      ab:  .asciz "ab"
ad:  .asciz "ad"
abc: .asciz "abc"
abc2:.asciz "abc"
abb: .asciz "abb"
z1:  .asciz ""
z2:  .asciz ""
fmt: .asciz "%s : %s = %2d\n"
chame a subrotina lexcmp com diversas combinações para os apontadores r1 e r2
e exiba no vídeo o resultado da comṕaração usando a cadeia de formatação fmt.
Um possível resultado de 5 testes seria:
 ab : abc = -1
abc : abc =  0
abc :  ad = -1
abc : abb =  1
    :     =  0
  14. Calculando o tamanho e mudando zeros não significativos de cadeia padrão C
    (i) Escreva uma subrotina strlen que toma como parâmetro de entrada em r0 o endereço de uma cadeia de caracteres ASCII terminada por um 0 binário e devolve em r1 (parâmetro de saída) o comprimento da cadeia
    (ii) suponha que a cadeia tem apenas caracteres com dígitos decimais: escreva outra subrotina fixstring para substituir os caracteres '0' na frente da cadeia, se existirem, ("leading zeros") pelo caracter branco '  '

  15. Calculando o número de valores iguais a zero, positivos e negativos de um vetor de inteiros
    Escreva uma subrotina para calcular o número de valores iguais a zero, negativos e positivos numa vetor de inteiros com sinal de 32 bits, cujo endereço é passado em r0; a 1a entrada do vetor contem o número de inteiros no vetor (defina o vetor e seu conteúdo em tempo de montagem). O número de valores positivos deve ser devolvido em r1, iguais a zero em r2 e negativos em r3. Teste sua rotina exibindo esses valores no vídeo.

  16. Produto escalar de vetores de inteiros de 32 bits:
    Escreva uma rotina para calcular o produto escalar de dois vetores de inteiros de 32 bits. Parâmetros:
    Entrada: r0 e r1 contêm endereços dos vetores e r2= número de elementos em cada veor.
    Saída: r3= produto escalar.
    Use a instrução: MLA (multiply and accumulate). Observe que não há uma maneira simples de verificar se houve overflow pois os flags C e V não são atualizados (p. 83-84 do manual). A instrução UMLAL (p. 85) também não atualiza os flags mas é simples descobrir se o produto escalar não cabe em 32 bits.

  17. Simulando um botão "toggle" via teclado
    Um botão do tipo "toggle" permite executar ações distintas toda vez que o botão é pressionado. Um exemplo simples é o botão de um cronômetro: quando pressionado dispara o cronômetro, ao ser pressionado novamente para o cronômetro e assim sucessivamente; outros exemplos são: acender/apagar um led ou dispensar/interromper a água de uma máquina de café. O objetivo deste exercício é simular um botão "toggle" através do teclado para ligar/desligar um led (simulado via mensagem para o vídeo), da seguinte forma: 
    l0: exiba a mensagem: "Pressione uma tecla (q para sair): "
    leia uma tecla via scanf
    dependendo do estado do botão exiba uma das mensagens: "led sendo ligado" ou "led sendo desligado"
    mude o estado do botão
    volte para l0

Exercícios mais elaborados:

Obs: se você fizer de forma individual o desafio que o dispensa da 1a prova e os 5 primeiros exercícios a seguir, também ficará dispensado de fazer a 2a prova. Você deverá convencer que em todos os casos obteve uma solução eficiente.
  1. Invertendo os bits de um registrador sem usar a instrução rbit
    Escreva uma subrotina eficiente rbit que toma como parâmetro em r0 um valor qualquer e devolve em r1 o valor de r0 com os bits na ordem inversa, ou seja, com o mesmo efeito da instrução rbit. Por exemplo, se r0=0xaaaaaaaa então o valor devolvido deverá der 0x55555555.
    Obs: a instrução ror não ajuda!

  2. Invertendo os bytes de um registrador sem usar a instrução rev
    (a solução deste problema transforma um inteiro do formato "little endian" para "big endian" ou vice-versa.Ela é importante em aplicações de redes envolvento o protocolo TCP/IP).
    Escreva uma subrotina eficiente revb que toma como parâmetro em r0 um valor qualquer e devolve em r1 o valor de r0 com os bytes na ordem inversa, ou seja, com o mesmo efeito da instrução rev. Por exemplo, se r0=0xaabbccdd então o valor devolvido deverá der 0xddccbbaa.
    Obs: uma solução bastante engenhosa e absolutamente não trivial aparece no diretório mais exemplos. Você deve obter uma solução não relacionada e não tão compacta.

  3. Contando o número de bits entre o bit 1 mais à esquerda e o bit 1 mais à direita de uma palavra
    Escreva uma subrotina eficiente, span, que toma como parâmetro de entrada em r0 um valor qualquer e devolve em r1 o número de bits de r0 entre o bit 1 mais significativo e o bit 1 menos significativo, ou seja à esquerda do bit 1 mais significativo só há bits 0 e à direita do bit 1 menos significativo só há bits 0. Sugestão: use as instruções CLZ e RBIT.

  4. Conversão de inteiro no formato "packed bcd" para binário sem usar instruções de multiplicação
    Um vetor de bytes no formato "bcd compactado" ( "packed binary coded decimal)" tem em cada "nibble" (4 bits) do byte um valor binário entre 0 e 9. Escreva um programa estruturado e eficiente para converter o número decimal armazenado no vetor num valor binário (sem sinal) de 32 bits. Suponha que o tamanho do vetor é <= 5 bytes, o que garante (na maioria dos casos) que o valor convertido cabe em 32 bits. (Use a diretiva .byte para definir o conteúdo do vetor, onde o 10 byte do vetor contém o número de dígitos bcd do vetor (até 10 dígitos)). Use o seguinte algoritmo, exemplificado para um vetor contendo 4 dígitos bcd, d1 d2 d3 d4, onde d1 é o mais significativo (você deve estender o algoritmo para n<=10 dígitos):
    (((d1*10) +d2)*10+d3)*10 +d4= d1*1000 + d2*100 + d3*10 + d4 que é o valor do número usando a notação posicional.
    Observe que basta colocar num laço e acumular os cálculos di*10 + di+1 para obter a conversão desejada:
    (i) usando o poder de endereçamento com deslocamento do ARM é possível multiplicar um valor binário por 10 com apenas 1 soma seguida de uma soma com deslocamento: 
            add r1, r1, r1, lsl #2  @ r1= r1*5
        mov r1, r1, lsl #1  @ r1= (r1*5)*2  @ e se em vez de "mov" usarmos "add", r1*10 pode ser somado a outro valor!
  5. Fatorial recursivo:
    Escreva uma rotina recursiva (factrec) para calcular com precisão de 32 bits o fatorial de um inteiro passado em r0 e devolvendo o fatorial em r1. O parâmetro de entrada deve ser sido lido previamente do teclado via scanf. Caso haja overflow no cálculo a rotina deverá retonar 0.
    Sugestões: (i) use a instrução de multiplicação umull (ii) use r0 como parâmetro em cada chamada recursiva e r1 para acumular o produto. Desta forma apenas o endereço de retorno precisa ser armazenado na pilha.

  6. Gerando a sequencia de Fibonacci em tempo de montagem
    Escreva um programa que em tempo de montagem preenche um vetor de palavras na memória RAM com os primeiros 32 elementos da sequencia de Fibonacci, usando as diretivas .equ, .rept, .word e .endr.
    Dica: use a diretiva .equ para definir duas constantes com os dois primeiros elementos da sequencia e dentro do bloco delimitado por .rept .endr calcule o próximo elemento da sequencia e altere os valores das duas constantes.
    Escreva uma rotina showvet para exibir (em tempo de execução) o conteúdo do vetor no vídeo.

  7. Implementação do comando switch da linguagem C via instrução TBB
    Quando se quer executar k diferentes trechos de programa dependendo do valor de uma variável que pode tomar os valores 0 ...k-1, o comando switch da linguagem C é mais claro do que sucessivos comandos "if-then-else" (exemplo a seguir): 
      switch(step){
     case 0:
       printf ("step 0\n");
       break;
     case 1:
       printf ("step 1\n");
       break;
     case 2:
       printf ("step 2\n");
       break;
     case 3: 
       printf ("step 3\n");
       break;
     case 4: 
       printf ("step 4\n");
       break;
   }
    A instrução TBB (p. 96 do manual) foi criada justamente com esta finalidade. Escreva um programa que realiza a mesma função do exemplo acima. Sugestão: coloque a tabela BranchTable_Byte imediatamente após a instrução TBB e use endereçamento relativo ao PC: TBB [PC, R1]