[Resultado do Desafio] Assembly para a arquitetura RX

- por Sergio Prado

Categorias: Desafios Tags: ,

E acabou o tempo para a submissão de respostas para o primeiro desafio do ano.

A idéia do desafio era escrever uma rotina em Assembly para a arquitetura RX da Renesas.

Em específico, a rotina em Assembly deveria ordenar de forma crescente um vetor de número inteiros positivos de 32 bits. Todos que enviassem uma resposta correta ganhariam 5 pontos, e aqueles que, além da resposta correta, enviassem um código que gerasse a menor quantidade possível de instruções de máquina ganhariam 10 pontos e esta belezura aqui!

Bom, recebi poucas submissões. Imagino que o pessoal esteja de férias, tomando água de coco, e neste momento ninguém quer saber dos desafios do Sergio Prado, muito menos de programação em Assembly! :-)

Das submissões que recebi, duas estavam corretas, e vou apresentá-las aqui para vocês.

A primeira submissão foi do ilustríssimo Fábio Pereira, autor de diversos livros de microcontroladores, muito bem escritos e didáticos, que muitos de nós (incluindo eu) já utilizamos em nossos estudos.

O Fábio implementou basicamente um Bubble Sort em Assembly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

.GLB    _asm_sort
        .SECTION P,CODE
 
; This is the asm_sort subroutine. It sorts an integer array (pointed to by R1 with size defined by R2) in ascending order
; Due to CCRX compiler calling convention, we need to move R1 to R5 and R2 to R6 in order to satisfy Sergio Prado's contest rules
; Warning: this subroutine does not preserve any CPU register! In order to be used within a real application, one must store
; R5 - R11 onto stack and restore them before returning from subroutine
; Note that there is not check for a zero element array!
_asm_sort:
        .STACK  _asm_sort = 00000000h
        ; first we need to config the proper registers (R5 and R6)
        ; MOV.L R1,R5           ; copy the array pointer to R5
        ; MOV.L R2,R6           ; copy the number of elements to R6
        ; now the sorting code
        ; R7 has the sorting status (0=no element exchanged, 1=array element exchanged)
        ; R8 has the current element pointer (within the array)
        ; R9 has the next element pointer (within the array)
        ; R10 and R11 are temporary registers
REPEAT:
        MOV.L #0,R8             ; set current element as zero
        MOV.L #1,R9             ; next element starts as one
        MOV.L #0,R7             ; clear R7 (sorting is done)
REPEAT2:
        ; start one sorting iteration
        MOV.L [R8,R5],R10       ; R10 has the current element
        MOV.L [R9,R5],R11       ; R11 has the next element
        CMP     R11,R10         ; compare current and next element
        BLTU NEXT_ELEMENT       ; branch to NEXT_ELEMENT if current element is lower than next element
        ; if R11 is lower than R10 (next element is lower than current element)
        MOV.L R11,[R8,R5]       ; move next element to current element
        MOV.L R10,[R9,R5]       ; move current element to next element
        MOV.L #1,R7             ; signal an exchange was done
        ; proceed to the next element
NEXT_ELEMENT:
        ADD #1,R8               ; increment current element pointer
        ADD #1,R9               ; increment next element pointer
        CMP R6,R9               ; compare next element pointer to max elements
        BLTU.B REPEAT2          ; branch to REPEAT2 if R6
        ; RTS ; return if no exchange was done
.END

O Assembly dele gerou um código de máquina de 36 bytes:

$ ./asrx.exe -isa=rxv1 -listfile=out.lst sort.s
RX Family Assembler V2.04.00.01 [14 Jul 2015]
Copyright (C) 2008, 2015 Renesas Electronics Corporation
All rights reserved.
macro processing now
assembler processing now
TOTAL ERROR(S)    00000
TOTAL WARNING(S)  00000
TOTAL LINE(S)     00042   LINES
CODE     0000000036(00000024H)  P

Na descrição do desafio, eu pedi para assumir que o registrador R5 teria o endereço de memória inicial dos elementos a serem ordenados e o registrador R6 teria a quantidade de elementos a serem ordenados.

Porém, como a convenção de chamadas do compilador da Renesas passa os parâmetros nos registradores R1 e R2, para testar a rotina Assembly com um código em C seria necessário fazer uma cópia dos registradores R1 e R2 para R5 e R6, respectivamente.

Como estas linhas não fazem parte do algoritmo, elas foram comentadas para não impactar no tamanho do código de máquina gerado (vide linhas 12 e 13 no código do Fábio). O mesmo vale para a instrução de retorno (RTS) na linha 39.

O segundo participante que submeteu uma resposta correta foi o George Tavares. Ele utilizou o algoritmo Gnome Sort e a implementação dele também ficou bacana e muito bem documentada:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

;-------------------------------------------------------------------------------
;   FILE        :sort2.src                                                      |
;   DATE        :2016-01-05                                                     |
;   AUTHOR      : George Tavares                                                |
;   DESCRIPTION :Implementação da rotina de sort para plataforma RX             |
; Usei o algoritmo Gnome Sort, baseado em trocas,que apresenta o codigo conciso |
; https://en.wikipedia.org/wiki/Gnome_sort . A ideia consiste em ir             |
; retrocedendo no array a partir da última posição e ao encontrar um par        |
; invertido, desinverter e voltar para frente no array para ver se precisa      |
; trocar os elementos posteriores que já passou.                                |
; Este e o pseudo codigo:                                                       |
; procedure gnomeSort(a[]):                                                     |
;     pos := length(a)                                                          |
;     while pos > 0 :                                                           |
;         if (pos == length(a) or a[pos] >= a[pos-1]):                          |
;             pos := pos - 1                                                    |
;         else:                                                                 |
;             swap a[pos] and a[pos-1]                                          |
;             pos := pos + 1                                                    |
;                                                                               |
;   CPU TYPE    :RX                                                             |
;   REGISTER MAP:                                                               |
;                                                                               |
;    R5 - Ponteiro do array (input)                                             |
;    R6 - Número de elementos do array (input)                                  |
;    R15 - Contador de laço do array (posição atual)                            |
;    R4 - Apontador para a posição anterior do array                            |
;    R8 - Valor do elemento da posição atual                                    |
;    R3 - Valor do elemento da posição anterior                                 |
;                                                                               |
;-------------------------------------------------------------------------------
 
;         .GLB    _sort2
         .SECTION   P,CODE
 
;-----------------------------------------------------------------------
;  _sort2:
;-----------------------------------------------------------------------
;                                 _sort2:
 
;MOV.L          R1,R5           ; Testei a rotina a partir de uma chamada C, como os parametros vinha em R1 e R2
;MOV.L          R2,R6           ; Movi eles para R5 e R6, conforme a descricao do problema. Desconsiderar essas instrucoes
 
MOV.L           R6,R15          ; Esse eh contador do laço (começamos no final do array)
 
__LACO_CALC:
SUB             #1H,R15         ; Decrementamos o contador de posição  do array, para ir ao item anterior  
 
__LACO_CHECK:
BZ.B            __EXIT          ; Se chegou no inicio do array (zero), vamos para a saída
 
ADD             #-01H,R15,R4    ; Guardamos em R4 o ponteiro da posição anterior do array
 
MOV.L           [R4,R5],R3      ; E lemos o elemento anterior em R3 (notação indexada).  
 
CMP             R6,R15          ; Se ultrapassamos no último item do array, não tem item  para comparar                                
BEQ.S           __TRAMPOLINE    ; Ae seguimos para o item anterior do array
                                ; Neste ponto usamos uma estratégia para economizar um byte
                                ; A instrução BEQ.B __LACO_CALC ocuparia dois bytes , porém a 
                                ; arquitetura possui a instrução BEQ.S, que ocupa um byte. essa
                                ; instrução permite deslocamento de ate 10 bytes (positivos).
                                ; Então fazemos o branch usando essa intrução para o trampolim.
                                ; A checagem do Branch com Carry (BC) tambem é verdade para situação de igual (BEQ)
                                ; Assim fazemos o branch para o trampolim, que por sua vez fará o branch para 
                                ; o __LACO_CALC que é o objetivo.
 
MOV.L           [R15,R5],R8     ; Lemos o elemento atual do array para o R8 (usando notação indexada)
                                ; Aqui temos R3 e R8 com os valores do array que estamos comparando
 
CMP             R3,R8           ; Comparamos os valores do elemento atual e do elemento anterior 
 
__TRAMPOLINE:
BC.B            __LACO_CALC     ; Se estiverem na ordem correta vamos seguir no array (pode ter chegado aqui pelo trampolim descrito acima)
 
MOV.L           R8,[R4,R5]      ; Como estão fora da ordem correta, é hora do SWAP. o R8, vai para a posição de memória que estava o R3 (posição anterior)
MOV.L           R3,[R15,R5]     ; E o R3 vai para a posição de memória que estava o R8  ( posição atual)
 
ADD             #1H,R15         ; Aqui avançamo uma posição, a fim de validar as posições posteriores se estão fora de ordem devido a essa reordenação
BRA.B           __LACO_CHECK    ; E reiniciamos  laço
 
__EXIT:	
 
;RTS                            ; Retorno de funcao. Acho que essa tambem nao conta como algoritmo
 
.END

O Assembly do George gerou um código de máquina de 32 bytes!

./asrx.exe -isa=rxv1 -listfile=out.lst sort.s
RX Family Assembler V2.04.00.01 [14 Jul 2015]
Copyright (C) 2008, 2015 Renesas Electronics Corporation
All rights reserved.
macro processing now
assembler processing now
TOTAL ERROR(S)    00000
TOTAL WARNING(S)  00000
TOTAL LINE(S)     00094   LINES
CODE     0000000032(00000020H)  P

Portanto, parabéns George! Por 4 bytes, você foi o ganhador da placa e dos 10 pontos! Afinal, neste nosso universo, 4 bytes em Assembly podem fazer muita diferença, não é verdade? :)

Parabéns ao Fábio também pelos 5 pontos e o segundo lugar no desafio. Espero que vocês, e todas as outras pessoas que participaram, tenham gostado de aprender um pouco sobre uma arquitetura diferente e pouco utilizada no Brasil.

Como prometi, irei manter um ranking de pontuação geral dos desafios do ano. E este é o ranking atual:

1. George Tavares – 10 pontos
2. Fábio Pereira – 5 pontos

O próximo desafio será divulgado na semana que vem.

Até lá!

Sergio Prado

Sem Comentários

Nenhum comentário até agora... é a sua chance de ser o primeiro a comentar!

Faça um Comentário

Navegue
Creative Commons Este trabalho de Sergio Prado é licenciado pelo
Creative Commons BY-NC-SA 3.0.