12. Exemplos de programação¶
Nos programas de exemplo que se seguem foi suprimido o código de arranque. Para gerar um executável deve juntar-se o código apresentado na secção codigo de arranque deste documento.
12.1. Multiplicação¶
Nos processadores que não dispõem de instrução de multiplicação, esta operação poderá ser realizada por programação. Um algoritmo comummente utilizado baseia-se na aplicação das seguintes expressões:
onde mx representa cada um dos dígitos do multiplicador (m), expresso em binário, com x a variar entre 0 e n - 1, sendo n o número de bits do multiplicador (m). A última expressão é um somatório de parcelas da forma M . 2x . mx. A multiplicação de M por uma potência inteira de 2 (M.2x), pode ser realizada por uma instrução de deslocamento para a esquerda de M. O produto de M.2x por mx, será igual a M.2x se o bit de índice x do multiplicador (m) for igual a um, ou será zero, no caso de mx ser zero. A sequência conjunta destas três ações – deslocamento de M, produto lógico pelo bit mx e adição deste resultado parcial, em somatório, até final – justifica a designação shift-and-add, pela qual o algoritmo é conhecido.
Em linguagem C a operação de multiplicação é indicada pelo operador * como na Listagem 12.1. Ao nível da máquina, esta operação pode ser realizada por uma instrução específica de multiplicação, ou, na sua falta, como no caso do P16, é realizada por uma função auxiliar de multiplicação, numa situação equivalente à do programa da Listagem 12.3.
A utilização de uma função auxiliar, origina um código de chamada como o apresentado na Listagem 12.2.
Na secção .data definem-se as variáveis m e n, que servem como operandos (linhas 28 a 31) e as variáveis p e q que recebem os resultados (linhas 32 a 35).
O código das linhas 2 a 6 diz respeito à invocação da função multiply com as constantes 4 e 7 como argumentos. Estes valores são carregados nos registos R0 e R1 (linhas 2 e 3) como explicado em Afetação com constante. O resultado, devolvido em R0, é guardado na variável q (linhas 5 e 6).
O código das linhas 8 a 14 diz respeito à invocação com da função multiply com os valores das variáveis m e n como argumentos. Estes valores são carregados nos registos R0 e R1 (linhas 8 a 11) e resultado é guardado na variável p (linhas 13 e 14) como explicado em Acesso a valores em memória.
uint8_t m = 20, n = 3;
uint16_t p, q;
int main() {
q = 4 * 7;
p = m * n;
}
|
1 .text
2 mov r0, #4
3 mov r1, #7
4 bl multiply
5 ldr r1, q_addr
6 str r0, [r1]
7
8 ldr r0, m_addr
9 ldrb r0, [r0]
10 ldr r1, n_addr
11 ldrb r1, [r1]
12 bl multiply
13 ldr r1, p_addr
14 str r0, [r1]
15
16 pop pc
17
18m_addr:
19 .word m
20n_addr:
21 .word n
22p_addr:
23 .word p
24q_addr:
25 .word q
26
27 .data
28m:
29 .byte 20
30n:
31 .byte 3
32p:
33 .word 0
34q:
35 .word 0
|
uint8_t m = 20, n = 3;
uint16_t p, q;
int main() {
q = multiply(4, 7);
p = multiply(m, n);
}
|
Na Listagem 12.4 apresenta-se a função multiply que implementa em linguagem C, o algoritmo enunciado acima. Em cada ciclo while é adicionada à variável product uma parcela do somatório.
(As anotações entre < e > junto de parâmetros e variáveis locais servem para indicar os registos que as suportam.)
uint16_t multiply(<r0> uint8_t multiplicand, <r1> uint8_t multiplier)) {
<r2> uint16_t product = 0;
while ( multiplier > 0 ) {
if ( (multiplier & 1) != 0 )
product += multiplicand;
multiplier >>= 1;
multiplicand <<= 1;
}
<r0> return product;
}
A implementação em linguagem assembly da função multiply, apresentada na Listagem 12.5, segue a Convenções de programação de funções. Designadamente, assume que os argumentos da função – multiplicand e multiplier – estão presentes nos registos R0 e R1; o resultado da função – produto de multiplicand por multiplier – produzido em R2 é transferido para R0 antes da função retornar; o registo R2 foi utilizado para suporte à variável local product sem necessidade de ser preservado.
A assunção de que os argumentos estão presentes em R0 e R1 é coerente com a programação realizada na Listagem 12.2.
1multiply:
2 mov r2, #0 ; <r2> int product = 0;
3mul_while:
4 add r1, r1, #0 ; while ( multiplier > 0 )
5 beq mul_return
6 lsr r1, r1, #1 ; if ( (multiplier & 1) != 0 )
7 bcc mul_if_end
8 add r2, r2, r0 ; product += multiplicand;
9mul_if_end:
10 lsl r0, r0, #1 ; multiplicand <<= 1;
11 b mul_while
12mul_return:
13 mov r0, r2
14 mov pc, lr ; <r0> return product;
Código fonte: multiply.s
12.2. Divisão¶
O algoritmo de divisão apresentado é a versão binária do algoritmo normalmente utilizado para dividir com papel e lápis.
Neste algoritmo, o dividendo é percorrido da extremidade esquerda para a direita – do dígito mais significativo para o menos significativo.
Na versão binária, tem um número de passos igual ao número de bits do dividendo. Em cada passo são realizadas as seguintes operações:
É extraido um dígito do dividendo – um bit. Este bit assume peso unitário em cada passo (linhas 5 e 6).
O quociente e o resto obtidos no passo anterior, são promovidos ao peso seguinte (linhas 7 e 8).
É criado um dividendo intermédio formado pelo resto promovido adicionado ao dígito extraído do dividendo (linha 9).
Deste dividendo intermédio é extraido o maior múltiplo possível do divisor (linhas 10 – 12). Na base binária o múltiplo possível é apenas o valor 1.
Esse múltiplo adiciona-se ao quociente e o que fica da extração é o resto (linhas 11 e 12).
Este algoritmo é também designado por shift-and-subtract.
1<r0> uint16_t divide(<r0> uint16_t dividend, <r1> uint16_t divisor) {
2 <r2> uint16_t i = 16;
3 <r3> uint16_t rest = 0, <r4> quocient = 0;
4 do {
5 uint16_t dividend_bit = dividend >> 15;
6 dividend <<= 1;
7 rest <<= 1;
8 quotient <<= 1;
9 rest += dividend_bit;
10 if (rest >= divisor) {
11 rest -= divisor;
12 quotient += 1;
13 }
14 } while (--i > 0);
15 return quotient;
16}
A implementação em linguagem assembly da função divide,
apresentada na Listagem 12.7, segue a Convenções de programação de funções.
Designadamente, assume que os argumentos da função – dividend e divisor –
estão presentes nos registos R0 e R1;
o resultado da função – quociente de dividend por divisor –
produzido em R4 é transferido para R0 antes da função retornar (linha 17).
Sendo uma função folha, deve dar-se preferência aos registos R0-R3 para suporte às variáveis locais.
Os registos R0 e R1 estão ocupados com argumentos. Como as variáveis locais são três,
o registo R4 foi utilizado para suportar a variável local quocient
porque os registos R2 e R3 foram utiizados para as variáveis i e rest.
Segundo as convenções, o conteúdo dos registos R4 e seguintes devem ser preservado, caso estes registos sejam utilizados. O que justifica a realização de PUSH/POP de R4 nas linhas 2 e 18.
1divide:
2 push r4
3 mov r3, #0 ; rest = 0;
4 mov r4, #0 ; quocient = 0;
5 mov r2, #16 ; uint16_t i = 16;
6div_while: ; uint16 dividend_msb = dividend >> 15;
7 lsl r0, r0, #1 ; dividend <<= 1;
8 adc r3, r3, r3 ; rest <<= 1; rest += dividend_bit;
9 lsl r4, r4, #1 ; quotient <<= 1;
10 cmp r3, r1 ; if (rest >= divisor) {
11 blo div_if_end
12 sub r3, r3, r1 ; rest -= divisor;
13 add r4, r4, #1 ; quotient += 1;
14div_if_end:
15 sub r2, r2, #1 ; } while (--i > 0);
16 bne div_while
17 mov r0, r4 ; return quotient;
18 pop r4
19 mov pc, lr
Código fonte: divide.s
12.3. Procurar um valor num array¶
A função search procura value em array com array_size elementos.
Caso encontre, retorna o índice da posição onde encontrou,
caso não encontre, retorna -1.
int16_t search(uint16_t array[], uint8_t array_size, uint16_t value);
Na Listagem 12.8 é apresentado um programa de utilização da função search com duas invocações.
1 uint16_t table1[] = {10, 20, 5, 6, 34, 9};
2 uint16_t table2[] = {11, 22, 33};
3 int16_t p, q;
4
5 int main() {
6 p = search(table1, sizeof table1 / sizeof table1[0], 20);
7 q = search(table2, sizeof table2 / sizeof table2[0], 31);
8 }
Na Listagem 12.9 é apresentada uma tradução do programa da Listagem 12.8
para linguagem assembly. Da linha 30 até à linha 42 apresenta-se a definição
dos arrays table1 e table2 e das variáveis p e q.
A escrita de sucessivos valores como argumento da diretiva .word corresponde
a reservar em memória uma sequência de words iniciadas com esses valores.
As labels table1_end e table2_end são utilizadas como referências
no cálculo da dimensão dos arrays table1 e table2.
A diferença table1_end - table1 é o número de posições de memória
ocupadas pelo array table1. O número de elementos é metade deste valor,
porque cada elemento ocupa duas posições de memória (linhas 6 e 13).
A passagem de um array como argumento de uma função, concretiza-se carregando o endereço da primeira posição do array no registo correspondente ao parâmetro (linhas 5 e 12). Este carregamento utiliza o método descrito em Carregamento de endereço em registo.
1 .text
2main:
3 push lr
4
5 ldr r0, table1_addr
6 mov r1, #(table1_end - table1) / 2
7 mov r2, #20
8 bl search
9 ldr r1, p_addr
10 str r0, [r1]
11
12 ldr r0, table2_addr
13 mov r1, #(table2_end - table2) / 2
14 mov r2, #44
15 bl search
16 ldr r1, q_addr
17 str r0, [r1]
18
19 pop pc
20
21table1_addr:
22 .word table1
23table2_addr:
24 .word table2
25p_addr:
26 .word p
27q_addr:
28 .word q
29
30 .data
31table1:
32 .word 10, 20, 5, 6, 34, 9
33table1_end:
34
35table2:
36 .word 11, 22, 33
37table2_end:
38
39p:
40 .word 0
41q:
42 .word 0
1<r0> int16_t search(<r0> uint16_t array[], <r1> uint8_t array_size, <r2> uint16_t value) {
2 for (<r3> uint8_t i = 0; i < array_size && array[i] != value; ++i)
3 ;
4 if( i < array_size)
5 return i;
6 return -1;
7}
Na Listagem 12.10 os parâmetros da função search
e a variável local i são assinalados com os registos que os suportam.
Por exemplo, na linha 1 <r0> uint16_t array[]
significa que o argumento deste parâmetro é recebido no registo R0.
1search:
2 push r4
3 mov r3, #0 ; i = 0
4search_for:
5 cmp r3, r1 ; i < array_size
6 bhs search_for_end
7 add r4, r3, r3
8 ldr r4, [r0, r4] ; array[i] != value
9 cmp r4, r2
10 beq search_for_end
11 add r3, r3, #1 ; ++i
12 b search_for
13search_for_end:
14 cmp r3, r1 ; if (i < array_size)
15 bhs search_if_end
16 mov r0, r3 ; return i
17 b search_end
18search_if_end:
19 mov r0, #0 ; return -1
20 sub r0, r0, #1
21search_end:
22 pop r4
23 mov pc, lr
Na Listagem 12.11, o registo R3 suporta a variável i que é usada como índice de acesso ao array.
No cálculo do endereço de cada posição a[i], é necessário multiplicar R3 por dois
porque os elementos do array ocupam duas posições de memória.
A instrução add r4, r3, r3 (linha 7) realiza essa multiplicação afetando R4 com R3 * 2.
O registo R4 foi preservado em cumprimento da convenção de Utilização dos registos.
Código fonte: search.s
12.4. Ordenar um array de valores inteiros¶
O programa seguinte realiza a ordenação de um array de números inteiros relativos por ordem crescente, utilizando uma variante do algoritmo de ordenação bubble sort.
1#define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0]))
2
3int16_t array[] = {20, -3, 45, 7, 5, -9, 0, -1, 15, 2};
4
5int main() {
6 sort(array, ARRAY_SIZE(array));
7}
1main:
2 push lr
3 ldr r0, array_addr
4 mov r1, #ARRAY_SIZE
5 bl sort
6 pop pc
7
8array_addr:
9 .word array
10
11
12 .data
13array:
14 .word 20, -3, 45, 7, 5, -9, 0, -1, 15, 2
15array_end:
16
17 .equ ARRAY_SIZE, (array_end - array) / 2
1void sort(<r0> int16_t a[], <r1> uint16_t dim) {
2 <r2> bool swapped;
3 do {
4 swapped = false;
5 for (<r3> uint16_t i = 0; i < dim - 1; i++)
6 if ( a[i] > a[i + 1]) {
7 int aux = a[i];
8 a[i] = a[i + 1];
9 a[i + 1] = aux;
10 swapped = true;
11 };
12 dim--;
13 } while (swapped);
14}
1 .equ false, 0
2 .equ true, !false
3sort:
4 push r4
5 push r5
6 push r6
7 sub r1, r1, #1 ; dim - 1
8sort_do:
9 mov r2, #false ; do {
10 mov r3, #0 ; i = 0
11sort_for:
12 cmp r3, r1 ; i – (dim - 1)
13 bhs sort_for_end ; if (i < dim-1)
14 add r4, r3, r3
15 ldr r5, [r0, r4] ; r5 = a[i]
16 add r4, r4, #2
17 ldr r6, [r0, r4] ; r6 = a[i + 1]
18 cmp r6, r5 ; a[i + 1] - a[i]
19 bge sort_if_end ; if (a[i] < a[i + 1])
20 str r5, [r0, r4] ; troca a[i] com a[i + 1]
21 sub r4, r4, #2
22 str r6, [r0, r4]
23 mov r2, #true ; swap = true
24sort_if_end:
25 add r3, r3, #1 ; i++
26 b sort_for
27sort_for_end:
28 sub r1, r1, #1 ; dim--
29 mov r4, #true
30 cmp r2, r4
31 beq sort_do ; } while (swapped)
32 pop r6
33 pop r5
34 pop r4
35 mov pc, lr ; return
Código fonte: bubble_sort.s
12.5. Chamadas encadeadas de funções¶
12.5.1. Histograma de vogais¶
1
2uint16_t occurrences1[SIZE];
3uint16_t occurrences2[SIZE];
4uint16_t occurrences3[SIZE];
5
6char phrase1[] = "aeiou";
7char phrase2[] = "a ee iii oooo uuuuu";
8
9*/
10{
11 histogram_vowel(phrase1, 15, occurrences1);
12 histogram_vowel(phrase2, 19, occurrences2);
13 histogram_vowel("Hello world", 7, occurrences3);
14}
15*/
1 push lr
2
3 ldr r0, phrase1_addr
4 mov r1, #15
5 ldr r2, occurrences1_addr
6 bl histogram_vowel
7
8 ldr r0, phrase2_addr
9 mov r1, #19
10 ldr r2, occurrences2_addr
11 bl histogram_vowel
12
13 ldr r0, phrase3_addr
14 mov r1, #7
15 ldr r2, occurrences3_addr
16 bl histogram_vowel
17
18 pop pc
19
20phrase1_addr:
21 .word phrase1
22phrase2_addr:
23 .word phrase2
24phrase3_addr:
25 .word phrase3
26
27occurrences1_addr:
28 .word occurrences1
29occurrences2_addr:
30 .word occurrences2
31occurrences3_addr:
32 .word occurrences3
33
34;-------------------------------------------------------------------------------
35 .equ SIZE, 5
36
37occurrences1:
38 .space SIZE * 2
39occurrences2:
40 .space SIZE * 2
41occurrences3:
42 .space SIZE * 2
43
44phrase1:
45 .asciz "aeiou"
46phrase2:
47 .asciz "a ee iii oooo uuuuu"
48phrase3:
49 .asciz "Hello world"
1void histogram_vowel(<r0> <r4> char phrase[], <r1> <r5> uint16_t max_letters,
2 <r2> <r6> uint16_t occurrences[5])
3{
4 for (<r7> uint16_t i = 0; phrase[i] != '\0' && i < max_letters ; i++ ) {
5 <r0> int16_t index = which_vowel(phrase[i];
6 if (index != -1)
7 occurrences[idx]++;
8 }
9}
1histogram_vowel:
2 push lr
3 push r4
4 push r5
5 push r6
6 mov r4, r0
7 mov r5, r1
8 mov r6, r2
9 mov r7, #0 ; i = 0
10 b for_cond
11for:
12 bl which_vowel ; phrase[i] é deixado em R0 no teste da condição do for
13 add r1, r0, #1 ; (if (... != -1) (-1 + 1 == 0)
14 bzs if_end
15 add r0, r0, r0 ; occurrences[idx]++
16 ldr r1, [r6, r0] ; index * 2 = index * sizeof(uint16_t)
17 add r1, r1, #1
18 str r1, [r6, r0]
19if_end:
20 add r7, r7, #1
21for_cond:
22 ldrb r0, [r4, r7] ; for(...; phrase[i] != '\0'
23 sub r0, r0, #0
24 beq for_end
25 cmp r7, r5 ; && i < max_letters; ...)
26 blo for
27for_end:
28 pop r6
29 pop r5
30 pop r4
31 pop pc
1int16_t which_vowel(char letter)
2{
3 switch (letter) {
4 case 'a':
5 return 0;
6 case 'e':
7 return 1;
8 case 'i':
9 return 2;
10 case 'o':
11 return 3;
12 case 'u':
13 return 4;
14 default:
15 return -1;
16 }
17}
1which_vowel:
2case_a:
3 mov r1, #'a' ; case 'a':
4 cmp r0, r1
5 bne case_e
6 mov r0, #0 ; return 0;
7 mov pc, lr
8case_e:
9 mov r1, #'e'
10 cmp r0, r1
11 bne case_i
12 mov r0, #1
13 mov pc, lr
14case_i:
15 mov r1, #'i'
16 cmp r0, r1
17 bne case_o
18 mov r0, #2
19 mov pc, lr
20case_o:
21 mov r1, #'o'
22 cmp r0, r1
23 bne case_u
24 mov r0, #3
25 mov pc, lr
26case_u:
27 mov r1, #'u'
28 cmp r0, r1
29 bne default
30 mov r0, #4
31 mov pc, lr
32default:
33 mov r0, #0 ; return -1
34 sub r0, r0, #1
35 mov pc, lr
Código fonte: vowel.s
12.6. Chamada recursiva¶
1uint16_t a = 8;
2
3uint16_t fa, fb;
4
5int main() {
6 fa = factorial(a);
7 fb = factorial(9);
8}
1 .data
2a:
3 .word 8
4fa:
5 .word 0
6fb:
7 .word 0
8
9 .text
10main:
11 push lr
12
13 ldr r0, a_addr
14 ldr r0, [r0]
15 bl factorial
16 ldr r2, fa_addr
17 str r0, [r2]
18
19 mov r0, #9
20 bl factorial
21 ldr r2, fb_addr
22 str r0, [r2]
23
24 pop pc
25
26a_addr:
27 .word a
28fa_addr:
29 .word fa
30fb_addr:
31 .word fa
1uint16_t factorial(<r0><r4>uint16_t n) {
2 if (n == 0)
3 return 1;
4 else {
5 uint32_t <r1:r0> tmp = n * factorial(n - 1);
6 return tmp < UINT16_MAX ? tmp : UINT16_MAX;
7 }
8}
1factorial:
2 add r0, r0, #0 ; if (n == 0)
3 beq return_1
4 push lr
5 push r4
6 mov r4, r0
7 sub r0, r0, #1 ; factorial(n - 1)
8 bl factorial
9 mov r1, r4
10 bl multiply ; n * factorial(n - 1)
11 add r1, r1, #0 ; tmp > UINT16_MAX ?
12 bzs return_tmp
13 mov r0, #UINT16_MAX & 0xff
14 movt r0, #UINT16_MAX >> 8
15return_tmp:
16 pop r4
17 pop pc
18return_1:
19 mov r0, #1 ; return 1
20 mov pc, lr
Código fonte: factorial.s