| 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 | ]
|
|---|
