1 | Brainfuck Self Interpreter: by Clive Gifford
|
---|
2 |
|
---|
3 | Version 1: 01 December 2006 (one trip between code and data per op)
|
---|
4 | Version 2: 16 December 2006 (virtual codes for various combinations)
|
---|
5 |
|
---|
6 | Credits
|
---|
7 |
|
---|
8 | A large section of code to load the input to the interpreter is copied
|
---|
9 | from the the 423 byte dbfi interpreter as described in the November 2003
|
---|
10 | paper "A Very Small Interpeter" by Oleg Mazonka and Daniel B Cristofani
|
---|
11 |
|
---|
12 | Goals
|
---|
13 |
|
---|
14 | The goal for this interpreter was to be efficient rather than small and
|
---|
15 | particularly to allow as many copies of itself as possible to be "stacked"
|
---|
16 | up with something else on top / In other words to achieve a low "eigenratio"
|
---|
17 | (See http eigenratios dot blogspot dot com for more information)
|
---|
18 |
|
---|
19 | The main idea of the first version was to only make one round trip between
|
---|
20 | the emulated code and emulated data for each instruction executed instead
|
---|
21 | of multiple round trips which is what Daniel and Oleg's version does
|
---|
22 |
|
---|
23 | The second version does more pre processing of the guest program in order
|
---|
24 | to map several common sequences to virtual codes thus reducing the memory
|
---|
25 | footprint and also further reducing the number of round trips between the
|
---|
26 | emulated code and data
|
---|
27 |
|
---|
28 | Other info:
|
---|
29 |
|
---|
30 | The input must consist of valid brainfuck code (to be interpreted) which
|
---|
31 | must always be followed by an exclamation mark and then any associated data
|
---|
32 | Input can also include "comments" (if desired) except for exclamation mark
|
---|
33 |
|
---|
34 | If you are stacking multiple copies of this interpreter then each additional
|
---|
35 | level also has to appear in the input with a trailing exclamation mark and
|
---|
36 | then we finally have the input for the very top level to finish things off
|
---|
37 |
|
---|
38 | The underlying brainfuck machine determines the possible range of values in
|
---|
39 | the data cell values and what happens if an attempt is made to go outside the
|
---|
40 | supported range but this interpreter does not more than 8 bit data itself
|
---|
41 |
|
---|
42 | Loops in the emulated code can be nested up to the maximum cell value in the
|
---|
43 | underlying machine and this interpreter requires that at least 17 levels of
|
---|
44 | nesting is supported
|
---|
45 |
|
---|
46 | Behaviour on end of input is also inherited from the next level down
|
---|
47 |
|
---|
48 | >>>> leave a little extra space before the program code
|
---|
49 | + start in left hand cell of first program code pair
|
---|
50 | [
|
---|
51 | ->>> clear flag and move to the starting position
|
---|
52 | ++>+>+++++++ setup differences and read char as per dbfi
|
---|
53 | [<++++>>++<-]++>>+>+> (by Daniel B Cristofani)
|
---|
54 | +++++[>++>++++++<<-]
|
---|
55 | +>>>,<++
|
---|
56 | [
|
---|
57 | [>[->>]<[>>]<<-] see section 3 of dbfi paper
|
---|
58 | <[<]<+>>[>]>
|
---|
59 | [ see section 4 of dbfi paper
|
---|
60 | <+>-
|
---|
61 | [[<+>-]>] see section 5 of dbfi paper
|
---|
62 | < see section 6 of dbfi paper
|
---|
63 | [
|
---|
64 | [[-]<] scan left and zero the differences
|
---|
65 | ++<- see section 7 of dbfi paper
|
---|
66 | [
|
---|
67 | <+++++++++>[<->-]>>
|
---|
68 | ]
|
---|
69 | >>
|
---|
70 | ]
|
---|
71 | ]
|
---|
72 | <<
|
---|
73 | ]
|
---|
74 |
|
---|
75 | a three way switch to handle possibilities and adjust positioning
|
---|
76 |
|
---|
77 | >[-]+<< set "done" flag and position to value
|
---|
78 | [
|
---|
79 | -- 2 means last decode was for a valid instruction
|
---|
80 | [ so if we still have something left now it was a 9
|
---|
81 | [-] originally (meaning input should be ignored)
|
---|
82 | >>- <<<+> so all we do is set the "more input" flag
|
---|
83 | ]
|
---|
84 | >>
|
---|
85 | [
|
---|
86 | -
|
---|
87 | <<<<[>+<-] for valid input move everything right one
|
---|
88 |
|
---|
89 | start of processing to find and recode certain combinations of codes
|
---|
90 |
|
---|
91 | +<<+ set flags to indicate we want to process
|
---|
92 | the last two instructions in the loop below
|
---|
93 | [
|
---|
94 | -> clear flag and move to instruction
|
---|
95 | [<+>>>>>>+<<<<<-] double copy instruction and then
|
---|
96 | <[>+<-]>>>>>> restore original before moving to copy
|
---|
97 |
|
---|
98 | map relevant codes to values giving unique pairwise sums and also
|
---|
99 | set a flag if we see the end of a loop
|
---|
100 |
|
---|
101 | >+<
|
---|
102 | [
|
---|
103 | -[
|
---|
104 | -[
|
---|
105 | -[
|
---|
106 | -[
|
---|
107 | -[
|
---|
108 | -[
|
---|
109 | -[
|
---|
110 | -[
|
---|
111 | [-]
|
---|
112 | >-<
|
---|
113 | ]>[-<<+++++++>>] <
|
---|
114 | ]
|
---|
115 | ]
|
---|
116 | ]>[-]<
|
---|
117 | ]>[-<<+++>>]<
|
---|
118 | ]>[-<<+>>]<
|
---|
119 | ]>[-]<
|
---|
120 | ]>[-<<<<<<<+>>>>>>>]< set flag if it is end of loop
|
---|
121 | ]>[-]<
|
---|
122 | <<<< goto next instruction flag
|
---|
123 | ]
|
---|
124 |
|
---|
125 | add values from above together to get unique sum
|
---|
126 |
|
---|
127 | >>>[<<+>>-]
|
---|
128 | <+<
|
---|
129 |
|
---|
130 | setup a switch to figure out what it means
|
---|
131 |
|
---|
132 | [
|
---|
133 | -[
|
---|
134 | -[
|
---|
135 | -[
|
---|
136 | -[
|
---|
137 | -[
|
---|
138 | -[
|
---|
139 | -[
|
---|
140 | -[
|
---|
141 | -[
|
---|
142 | -[
|
---|
143 | [-]
|
---|
144 | >-<<<[-]<<+>> change code 8 (add 1) to 9 (add 2)
|
---|
145 | ]
|
---|
146 | ]
|
---|
147 | ]
|
---|
148 | ]>[-]<
|
---|
149 | ]>[-<<<[-]<<+++++++>>>]< change code 4 (left) to 11 (left 2)
|
---|
150 | ]
|
---|
151 | ]
|
---|
152 | ]>[-]<
|
---|
153 | ]>[-<<<[-]<<+++++++>>>]< change code 3 (right) to 10 (right 2)
|
---|
154 | ]
|
---|
155 | ]>[-]<
|
---|
156 |
|
---|
157 | clear flag set if second to last was end of loop
|
---|
158 | and go to similar flag for last instruction
|
---|
159 |
|
---|
160 | <<<<<[-]>>
|
---|
161 | [
|
---|
162 | -
|
---|
163 | <<<[>+>>+<<<-]>[<+>-]>> copy third to last instruction
|
---|
164 |
|
---|
165 | if it is the start of a loop then we can (in some cases)
|
---|
166 | collapse the last three instructions to single virtual code
|
---|
167 |
|
---|
168 | [
|
---|
169 | -[
|
---|
170 | -[
|
---|
171 | [-]
|
---|
172 | >>
|
---|
173 | ]
|
---|
174 | >
|
---|
175 | [ Now we are ready to check what code is in the loop (must be at least 1)
|
---|
176 | <<[<+>>+<-]>[<+>-]+<<
|
---|
177 | -
|
---|
178 | [
|
---|
179 | -[
|
---|
180 | -[
|
---|
181 | -[
|
---|
182 | -[
|
---|
183 | -[
|
---|
184 | -[
|
---|
185 | -[
|
---|
186 | -[
|
---|
187 | -[
|
---|
188 | -
|
---|
189 | <+> fall through & code as 16 (double skip left)
|
---|
190 | ]<+++++++++++++>>[-]>->-<< code as 15 (double skip right)
|
---|
191 | ]
|
---|
192 | ]
|
---|
193 | ]>>[->>>>>]<<
|
---|
194 | ]>>[-<<<++++++++++++>>[-]>>-]<< code as 14 (zero)
|
---|
195 | ]>>[->>>>>]<<
|
---|
196 | ]>>[-<<<+++++++++++>>[-]>>-]<< code as 13 (skip left)
|
---|
197 | ]>>[-<<<++++++++++>>[-]>>-]<< code as 12 (skip right)
|
---|
198 | ]
|
---|
199 | ]>>[->>>>>]<<
|
---|
200 | ]
|
---|
201 | <
|
---|
202 | ]
|
---|
203 | ]>[>>]<
|
---|
204 | <<
|
---|
205 | ]
|
---|
206 | >>+>>>
|
---|
207 | ]
|
---|
208 | <<
|
---|
209 | ]
|
---|
210 | >> [->+>] << end of input so clear "done" and set data mark and
|
---|
211 | finally position to a zero cell ready for next phase
|
---|
212 |
|
---|
213 | < move to "more input" flag
|
---|
214 |
|
---|
215 | ]
|
---|
216 |
|
---|
217 | <<[<<]>> go to the first instruction
|
---|
218 |
|
---|
219 | ******** MAIN INTERPRETER LOOPS STARTS HERE ********
|
---|
220 |
|
---|
221 | [ start on current instruction code
|
---|
222 | setup a big switch statement to decode instructions
|
---|
223 | [<+>>+<-] move/copy instruction code and set "done" flag to
|
---|
224 | +<- start with '(i less 1) (1) (i) for i = instruction
|
---|
225 | [
|
---|
226 | -[
|
---|
227 | -[
|
---|
228 | -[
|
---|
229 | -[
|
---|
230 | -[
|
---|
231 | -[
|
---|
232 | -[
|
---|
233 | -[
|
---|
234 | -[
|
---|
235 | -[
|
---|
236 | -[
|
---|
237 | -[
|
---|
238 | -[
|
---|
239 | -[
|
---|
240 | - can't be anything but 1 so bracketing not needed
|
---|
241 | >->> [>>] >> [>>]< [<-<<-<] <[<<] << [<<]< double skip left (code 16)
|
---|
242 | ]
|
---|
243 | >[->> [>>] >> [>>]< [>+>>+>] <[<<] << [<<]]< double skip right (code 15)
|
---|
244 | ]
|
---|
245 | >[->> [>>] >> [>>] <[-]< [<<] << [<<]]< zero (code 14)
|
---|
246 | ]
|
---|
247 | >[->> [>>] >> [>>]< [<-<] <[<<] << [<<]]< skip left (code 13)
|
---|
248 | ]
|
---|
249 | >[->> [>>] >> [>>]< [>+>] <[<<] << [<<]]< skip right (code 12)
|
---|
250 | ]
|
---|
251 | >[->> [>>] >> [>>]< <-<<-< <[<<] << [<<]]< double move left (code 11)
|
---|
252 | ]
|
---|
253 | >[->> [>>] >> [>>] +>>+ [<<] << [<<]]< double move right (code 10)
|
---|
254 | ]
|
---|
255 | >[->> [>>] >> [>>]< ++ <[<<] << [<<]]< add 2 (code 9)
|
---|
256 | ]
|
---|
257 | >[->> [>>] >> [>>]< + <[<<] << [<<]]< increment
|
---|
258 | ]
|
---|
259 | >[->> [>>] >> [>>]< , <[<<] << [<<]]< input
|
---|
260 | ]
|
---|
261 | >[->> [>>] >> [>>]< - <[<<] << [<<]]< decrement
|
---|
262 | ]
|
---|
263 | >[->> [>>] >> [>>]< . <[<<] << [<<]]< output
|
---|
264 | ]
|
---|
265 | >[->> [>>] >> [>>] <<-<< [<<] << [<<]]< move left
|
---|
266 | ]
|
---|
267 | >[->> [>>] >> [>>] + [<<] << [<<]]< move right
|
---|
268 | ]
|
---|
269 | >
|
---|
270 | [- left hand bracket
|
---|
271 | >> [>>] >> [>>]< move to data cell
|
---|
272 | [>+>>+<<<-]> make double copy and move to first
|
---|
273 | [<+>-] restore original data cell value
|
---|
274 | >>[<<+>>[-]]+ This and the following achieves
|
---|
275 | <<[>>-<<-] x = not x
|
---|
276 | >> go to flag cell (0 or 1)
|
---|
277 |
|
---|
278 | Some tricky stuff here: set up (not flag) also so we can later choose
|
---|
279 | appropriate instruction sequence to get back to code area in one pass
|
---|
280 | In one case we set flags at the other end (data greater than 0) but
|
---|
281 | for the other we just go back without setting any flags (data equals 0)
|
---|
282 |
|
---|
283 | [<<+>>>>+<<-] make two copies of flag
|
---|
284 | >>[<<+>>-]
|
---|
285 | <<[>>+<<-]+ This and the following achieves
|
---|
286 | >>[<<->>-]<< x = not x
|
---|
287 |
|
---|
288 | << so we now have (data) '(flag) (?) (not flag)
|
---|
289 |
|
---|
290 | [ if flag set then
|
---|
291 | -<< [<<] << [<<]< clear and return to code section where we save
|
---|
292 | << << ++ a 2 meaning we need (later) to match left bracket
|
---|
293 | >> stop in zero cell for now
|
---|
294 | ]
|
---|
295 |
|
---|
296 | >> if we executed code above then now at switch flag
|
---|
297 | else it will put us ready to return from data area
|
---|
298 |
|
---|
299 | [-<<<<<<[<<]<<[<<]<] move back to switch flag without setting anything
|
---|
300 |
|
---|
301 | >
|
---|
302 | ]
|
---|
303 | <
|
---|
304 | ]
|
---|
305 | >
|
---|
306 | [- right hand bracket
|
---|
307 | >> [>>] >> [>>]< move to data cell
|
---|
308 | [>+>>+<<<-]> make double copy and move to first
|
---|
309 | [[<+>-]>>[-]+<<] restore data from one then zero second and set flag
|
---|
310 | >> go to flag cell (0 or 1)
|
---|
311 |
|
---|
312 | Some tricky stuff here: set up (not flag) also so we can later choose
|
---|
313 | appropriate instruction sequence to get back to code area in one pass
|
---|
314 | In one case we set flags at the other end (data greater than 0) but
|
---|
315 | for the other we just go back without setting any flags (data equals 0)
|
---|
316 |
|
---|
317 | [<<+>>>>+<<-] make two copes of flag
|
---|
318 | >>[<<+>>-]
|
---|
319 | <<[>>+<<-]+ This and the following achieves
|
---|
320 | >>[<<->>-]<< x = not x
|
---|
321 |
|
---|
322 | << so we now have (data) '(flag) (?) (not flag)
|
---|
323 |
|
---|
324 | [ if flag set then
|
---|
325 | -<< [<<] << [<<]< clear and return to code section where we save
|
---|
326 | << << + a 1 meaning we need (later) to match right bracket
|
---|
327 | >> stop in zero cell for now
|
---|
328 | ]
|
---|
329 |
|
---|
330 | >> if we executed code above then now at switch flag
|
---|
331 | else it will put us ready to return from data area
|
---|
332 |
|
---|
333 | [-<<<<<<[<<]<<[<<]<] move back to switch flag without setting anything
|
---|
334 |
|
---|
335 | >
|
---|
336 | ]
|
---|
337 |
|
---|
338 | >[<+>-] restore original instruction code
|
---|
339 |
|
---|
340 | *** We are positioned in the cell immediately to the right of the ***
|
---|
341 | *** instruction that has just been "executed" in the switch above ***
|
---|
342 | *** The following code is to handle finding matching brackets ***
|
---|
343 | *** because code above has only set a cell value to 1 or 2 to show ***
|
---|
344 | *** what kind of loop scanning is required (1=scan left 2=right) ***
|
---|
345 |
|
---|
346 | << << << position to cell showing if matching required
|
---|
347 | [ if non zero we need to find a matching bracket
|
---|
348 | >> + set up "done" flag for switch and
|
---|
349 | << - decrement switch value so now is 0 or 1
|
---|
350 | [ if 1 we are looking for matching right bracket
|
---|
351 | - >> - >> + clear switch value & "done" & set level to 1
|
---|
352 | [ while level is more than 0
|
---|
353 | >>>[-<+>>+<] make double copy of instruction code
|
---|
354 | +<- set flag and prepare for switch
|
---|
355 | [
|
---|
356 | -[
|
---|
357 | [-] clear whatever is left of code
|
---|
358 | > - < do nothing except clear flag
|
---|
359 | ]
|
---|
360 | > [- <<< + >>>] < increment level
|
---|
361 | ]
|
---|
362 | > [- <<< - >>>] decrement level
|
---|
363 |
|
---|
364 | >[-<+>]<< restore instruction code
|
---|
365 |
|
---|
366 | << go to level
|
---|
367 | [>>+<<-] if level then move right one instruction
|
---|
368 | >>
|
---|
369 | ]
|
---|
370 | << << << go back to switch value cell
|
---|
371 | ]
|
---|
372 | >> go to switch done flag and if still set then
|
---|
373 | [ we must be looking for a matching left bracket
|
---|
374 | - << + clear switch value & "done" & set level to 1
|
---|
375 | [ repeat while level is more than 0
|
---|
376 | >>>[-<+>>+<] make double copy of instruction code
|
---|
377 | +<- set flag and prepare for switch
|
---|
378 | [
|
---|
379 | -[
|
---|
380 | [-] clear whatever is left of code
|
---|
381 | > - < do nothing except clear flag
|
---|
382 | ]
|
---|
383 | > [- <<< - >>>] < decrement level
|
---|
384 | ]
|
---|
385 | > [- <<< + >>>] increment level
|
---|
386 |
|
---|
387 | >[-<+>]<< restore instruction code
|
---|
388 |
|
---|
389 | << go to level
|
---|
390 | [<<+>>-] if level then move left one instruction
|
---|
391 | <<
|
---|
392 | ]
|
---|
393 | ]
|
---|
394 | ]
|
---|
395 |
|
---|
396 | >> >> >>
|
---|
397 |
|
---|
398 | > move forward to next instruction
|
---|
399 | ]
|
---|