Hello !
Bon, bien évidemment, mon immonde bazar du début était complètement inutilisable, puisqu'il ne prennait pas en compte les boucles.
Je suis donc parti sur autre chose : un interpréteur BF écrit en assembleur. Et bien, ça a été un peu long à débogguer (j'ai voulu faire trop optimisé, résultat j'ai loupé des cas) au niveau des boucles, mais ça marche !
Le code ici:
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137 | format ELF executable 3
entry start
segment readable writeable
cell db 1024 dup(0)
filename db 'prog.bf'
instru db 100000 dup(0)
msg_end db 0xA
segment readable executable
start:
; = Read BF source code =
; === Open the file ===
mov eax, 5
mov ebx, filename
xor ecx, ecx
xor edx, edx
int 0x80
; === Read the file ===
mov eax, 3
mov ebx, 3
mov ecx, instru
mov edx, 100000
int 0x80
; = Go to the interpreter =
mov ecx, 1
mov edi, cell
mov esi, instru
jmp bf_i
bf_sub:
; inc byte [edi]
sub byte [edi], 1
jmp instru_inc
bf_cell_dec:
dec edi
jmp instru_inc
bf_cell_inc:
inc edi
jmp instru_inc
bf_add:
; inc byte [edi]
add byte [edi], 1
instru_inc:
inc esi
bf_i:
cmp byte [esi], ']'
je bf_loop_pop
cmp byte [esi], '['
je bf_loop_push
; Skip the loop in case we are on a 0 cell
jcxz instru_inc
cmp byte [esi], '+'
je bf_add
cmp byte [esi], '-'
je bf_sub
cmp byte [esi], '>'
je bf_cell_inc
cmp byte [esi], '<'
je bf_cell_dec
cmp byte [esi], ','
je bf_in
cmp byte [esi], '.'
je bf_out
cmp byte [esi], 0
je endprog
; Something that's not BF ==> never mind.
jmp instru_inc
bf_out:
mov eax, 4
mov ebx, 1
mov ecx, edi
mov edx, 1
int 0x80
mov ecx, 1
jmp instru_inc
bf_in:
mov eax, 3
mov ebx, 0
mov ecx, edi
mov edx, 1
int 0x80
mov ecx, 1
jmp instru_inc
bf_loop_push:
push esi
push ecx
cmp byte [edi], 0
setne cl
jmp instru_inc
bf_loop_pop:
pop ecx
cmp byte [edi], 0
je no_pop
pop esi
jmp bf_i
no_pop:
pop eax
jmp instru_inc
endprog:
mov eax, 4
mov ebx, 1
mov ecx, msg_end
mov edx, 1
int 0x80
mov eax, 1
xor ebx, ebx
int 0x80
|
Le tout est donc en appel système direct, donc utilisable uniquement sous linux. Par contre, c'est théoriquement directement utilisable sous un i386. Il faut obligatoirement utiliser fasm puisqu'il n'y a aucune section, donc le linker va être perdu.
Il me sort Mandelbrot en environ 23s, donc il y a encore du boulot à faire.
Il marche de la façon suivante:
- edi pointe sur les cases BF (limité à 1Ko pour essayer de rester en L1)
- esi pointe sur le code source BF (limité à une valeur bizarre pour essayer de rester en L3)
A chaque instruction, esi est donc incrémenté : on avance d'une case, donc d'une instruction. Quand on rentre dans une boucle, on stocke l'adresse de la case courante dans la pile, comme ça à la fin de boucle il n'y a plus qu'à dépiler le pointeur et on est repartit. Si la boucle doit être ignorée, elle est "échappée" en mettant ecx à 0 (d'où un petit jcxz et un setne cl), après avoir poussée la valeur précédente d'ecx dans la pile, ce qui permet de gérer les boucles imbriquées.
Il n'y a donc aucune sorte d'optimisation sur les boucles.
Pour les curieux, le programme en lui-même fait 1.4Ko, c'est le tableau d'instructions qui prend tout le reste de la place.
EDIT : le msg_end, c'est un LF pour terminer le programme de façon propre
EDIT 2: Important pour l'utiliser (une fois assemblé) vous devez mettre votre code bf dans le répertoire courant (par exemple celui qui contient l'interpréteur) dans le fichier prog.bf (cette constante est contenue dans la variable filename). Il ne prend aucun argument. J'ai fait ça en attendant de savoir gérer correctement les arguments de taille variables.
EDIT 3: Ce qui est optimisable. Parce que même si les précédents interpréteurs sortaient mandelbrot en environ 20s, on peut faire encore quelques petites choses en assembleur:
- remplacer les add et sub des '+' et '-' par des inc et dec (moins d'opérandes = moins de temps de prélecture avant saut = quelques cycles d'économisés). Actuellement j'ai un problème terrible avec les inc et dec (que je ne comprends pas d'ailleurs) qui fait que je suis obligé de passer par des add et sub
- diminer le nombre de saut:
Pour les non-initiés au langage, tout ce qui commence par 'j' est un saut, comme par exemple:
Sauf qu'en x86, un saut prend énormément de temps. Une addition ou une soustraction prennent 2 cycles. Un comparaison avec une opérande mémoire 4 (si ma mémoire est bonne). Un saut, c'est minimum 7. Et encore, parce qu'il y a une prélecture automatique de l'instruction suivante, qui ne peut se faire que s'il n'y a pas de rupture de séquence. Un saut, c'est une rupture de séquence, donc il est obligé de prendre du temps en plus pour lire la première instructions (les autres bénéficeront de la prélecture automatique), et plus cette instruction a "d'arguments", plus la lecture prend du temps.
- dans le cas ou j'en aurais oublié, quelques optimisations introduites tardivement sur les x86, tel que la "parallélisation" des opérations sur les registres, ainsi que certaines micro-optimisations (je n'en connait aucune à part le xor pour mettre à 0)
EDIT 4 : Modification mineure. Au programme : déplacement de certaines procédures, suppression d'un jump pour '+', écriture d'un align 4 pour le début de l'interpréteur.
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144 | format ELF executable 3
entry start
segment readable writeable
cell db 1024 dup(0)
filename db 'prog.bf'
instru db 100001 dup(0)
msg_end db 0xA
segment readable executable
start:
; = Read BF source code =
; === Open the file ===
mov eax, 5
mov ebx, filename
xor ecx, ecx
xor edx, edx
int 0x80
; === Read the file ===
mov eax, 3
mov ebx, 3
mov ecx, instru
mov edx, 100000
int 0x80
; = Go to the interpreter =
mov ecx, 1
mov edi, cell
mov esi, instru
jmp bf_i
bf_sub:
align 4
sub byte [edi], 1
jmp instru_inc
bf_cell_dec:
dec edi
jmp instru_inc
bf_add:
add byte [edi], 1
dec edi
bf_cell_inc:
inc edi
instru_inc:
inc esi
bf_i:
cmp byte [esi], ']'
je bf_loop_pop
cmp byte [esi], '['
je bf_loop_push
; Skip the loop in case we are on a 0 cell
; jcxz instru_inc
cmp ecx, 0
je instru_inc
cmp byte [esi], '+'
je bf_add
cmp byte [esi], '-'
je bf_sub
cmp byte [esi], '>'
je bf_cell_inc
cmp byte [esi], '<'
je bf_cell_dec
cmp byte [esi], ','
je bf_in
cmp byte [esi], '.'
je bf_out
cmp byte [esi], 0
je endprog
; Something that's not BF ==> never mind.
jmp instru_inc
bf_out:
mov eax, 4
mov ebx, 1
mov ecx, edi
mov edx, 1
int 0x80
mov ecx, 1
jmp instru_inc
bf_loop_push:
push esi
push ecx
cmp byte [edi], 0
setne cl
jmp instru_inc
bf_loop_pop:
pop ecx
cmp byte [edi], 0
je no_pop
; cmove eax, [esp]
pop esi
; cmovne esi, [esp]
; add esp, 4
; je instru_inc
jmp bf_i
no_pop:
pop eax
jmp instru_inc
bf_in:
mov eax, 3
xor ebx, ebx
mov ecx, edi
mov edx, 1
int 0x80
mov ecx, 1
jmp instru_inc
endprog:
mov eax, 4
mov ebx, 1
mov ecx, msg_end
mov edx, 1
int 0x80
mov eax, 1
xor ebx, ebx
int 0x80
|
Mandelbrot en 21.75s, notamment par le remplacement de jcxz (censé être optimisé …) par un combo cmp-je, comme pour le reste.
).
